1234285Sdim//===---- LiveRangeEdit.h - Basic tools for split and spill -----*- C++ -*-===// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// The LiveRangeEdit class represents changes done to a virtual register when it 11234285Sdim// is spilled or split. 12234285Sdim// 13234285Sdim// The parent register is never changed. Instead, a number of new virtual 14234285Sdim// registers are created and added to the newRegs vector. 15234285Sdim// 16234285Sdim//===----------------------------------------------------------------------===// 17234285Sdim 18234285Sdim#ifndef LLVM_CODEGEN_LIVERANGEEDIT_H 19234285Sdim#define LLVM_CODEGEN_LIVERANGEEDIT_H 20234285Sdim 21234285Sdim#include "llvm/ADT/ArrayRef.h" 22263508Sdim#include "llvm/ADT/SetVector.h" 23234285Sdim#include "llvm/ADT/SmallPtrSet.h" 24234285Sdim#include "llvm/CodeGen/LiveInterval.h" 25263508Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 26234285Sdim#include "llvm/Target/TargetMachine.h" 27234285Sdim 28234285Sdimnamespace llvm { 29234285Sdim 30234285Sdimclass AliasAnalysis; 31234285Sdimclass LiveIntervals; 32263508Sdimclass MachineBlockFrequencyInfo; 33234285Sdimclass MachineLoopInfo; 34234285Sdimclass VirtRegMap; 35234285Sdim 36263508Sdimclass LiveRangeEdit : private MachineRegisterInfo::Delegate { 37234285Sdimpublic: 38234285Sdim /// Callback methods for LiveRangeEdit owners. 39234285Sdim class Delegate { 40234285Sdim virtual void anchor(); 41234285Sdim public: 42234285Sdim /// Called immediately before erasing a dead machine instruction. 43234285Sdim virtual void LRE_WillEraseInstruction(MachineInstr *MI) {} 44234285Sdim 45234285Sdim /// Called when a virtual register is no longer used. Return false to defer 46234285Sdim /// its deletion from LiveIntervals. 47234285Sdim virtual bool LRE_CanEraseVirtReg(unsigned) { return true; } 48234285Sdim 49234285Sdim /// Called before shrinking the live range of a virtual register. 50234285Sdim virtual void LRE_WillShrinkVirtReg(unsigned) {} 51234285Sdim 52234285Sdim /// Called after cloning a virtual register. 53234285Sdim /// This is used for new registers representing connected components of Old. 54234285Sdim virtual void LRE_DidCloneVirtReg(unsigned New, unsigned Old) {} 55234285Sdim 56234285Sdim virtual ~Delegate() {} 57234285Sdim }; 58234285Sdim 59234285Sdimprivate: 60239462Sdim LiveInterval *Parent; 61263508Sdim SmallVectorImpl<unsigned> &NewRegs; 62234285Sdim MachineRegisterInfo &MRI; 63234285Sdim LiveIntervals &LIS; 64234285Sdim VirtRegMap *VRM; 65234285Sdim const TargetInstrInfo &TII; 66239462Sdim Delegate *const TheDelegate; 67234285Sdim 68239462Sdim /// FirstNew - Index of the first register added to NewRegs. 69239462Sdim const unsigned FirstNew; 70234285Sdim 71239462Sdim /// ScannedRemattable - true when remattable values have been identified. 72239462Sdim bool ScannedRemattable; 73234285Sdim 74239462Sdim /// Remattable - Values defined by remattable instructions as identified by 75234285Sdim /// tii.isTriviallyReMaterializable(). 76239462Sdim SmallPtrSet<const VNInfo*,4> Remattable; 77234285Sdim 78239462Sdim /// Rematted - Values that were actually rematted, and so need to have their 79234285Sdim /// live range trimmed or entirely removed. 80239462Sdim SmallPtrSet<const VNInfo*,4> Rematted; 81234285Sdim 82239462Sdim /// scanRemattable - Identify the Parent values that may rematerialize. 83234285Sdim void scanRemattable(AliasAnalysis *aa); 84234285Sdim 85234285Sdim /// allUsesAvailableAt - Return true if all registers used by OrigMI at 86234285Sdim /// OrigIdx are also available with the same value at UseIdx. 87234285Sdim bool allUsesAvailableAt(const MachineInstr *OrigMI, SlotIndex OrigIdx, 88249423Sdim SlotIndex UseIdx) const; 89234285Sdim 90234285Sdim /// foldAsLoad - If LI has a single use and a single def that can be folded as 91234285Sdim /// a load, eliminate the register by folding the def into the use. 92234285Sdim bool foldAsLoad(LiveInterval *LI, SmallVectorImpl<MachineInstr*> &Dead); 93234285Sdim 94263508Sdim typedef SetVector<LiveInterval*, 95263508Sdim SmallVector<LiveInterval*, 8>, 96263508Sdim SmallPtrSet<LiveInterval*, 8> > ToShrinkSet; 97263508Sdim /// Helper for eliminateDeadDefs. 98263508Sdim void eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink); 99263508Sdim 100263508Sdim /// MachineRegisterInfo callback to notify when new virtual 101263508Sdim /// registers are created. 102263508Sdim void MRI_NoteNewVirtualRegister(unsigned VReg); 103263508Sdim 104234285Sdimpublic: 105234285Sdim /// Create a LiveRangeEdit for breaking down parent into smaller pieces. 106234285Sdim /// @param parent The register being spilled or split. 107234285Sdim /// @param newRegs List to receive any new registers created. This needn't be 108234285Sdim /// empty initially, any existing registers are ignored. 109234285Sdim /// @param MF The MachineFunction the live range edit is taking place in. 110234285Sdim /// @param lis The collection of all live intervals in this function. 111234285Sdim /// @param vrm Map of virtual registers to physical registers for this 112234285Sdim /// function. If NULL, no virtual register map updates will 113234285Sdim /// be done. This could be the case if called before Regalloc. 114239462Sdim LiveRangeEdit(LiveInterval *parent, 115263508Sdim SmallVectorImpl<unsigned> &newRegs, 116234285Sdim MachineFunction &MF, 117234285Sdim LiveIntervals &lis, 118234285Sdim VirtRegMap *vrm, 119234285Sdim Delegate *delegate = 0) 120239462Sdim : Parent(parent), NewRegs(newRegs), 121234285Sdim MRI(MF.getRegInfo()), LIS(lis), VRM(vrm), 122234285Sdim TII(*MF.getTarget().getInstrInfo()), 123239462Sdim TheDelegate(delegate), 124239462Sdim FirstNew(newRegs.size()), 125263508Sdim ScannedRemattable(false) { MRI.setDelegate(this); } 126234285Sdim 127263508Sdim ~LiveRangeEdit() { MRI.resetDelegate(this); } 128263508Sdim 129239462Sdim LiveInterval &getParent() const { 130239462Sdim assert(Parent && "No parent LiveInterval"); 131239462Sdim return *Parent; 132239462Sdim } 133239462Sdim unsigned getReg() const { return getParent().reg; } 134234285Sdim 135234285Sdim /// Iterator for accessing the new registers added by this edit. 136263508Sdim typedef SmallVectorImpl<unsigned>::const_iterator iterator; 137239462Sdim iterator begin() const { return NewRegs.begin()+FirstNew; } 138239462Sdim iterator end() const { return NewRegs.end(); } 139239462Sdim unsigned size() const { return NewRegs.size()-FirstNew; } 140234285Sdim bool empty() const { return size() == 0; } 141263508Sdim unsigned get(unsigned idx) const { return NewRegs[idx+FirstNew]; } 142234285Sdim 143263508Sdim ArrayRef<unsigned> regs() const { 144239462Sdim return makeArrayRef(NewRegs).slice(FirstNew); 145234285Sdim } 146234285Sdim 147263508Sdim /// createEmptyIntervalFrom - Create a new empty interval based on OldReg. 148263508Sdim LiveInterval &createEmptyIntervalFrom(unsigned OldReg); 149263508Sdim 150234285Sdim /// createFrom - Create a new virtual register based on OldReg. 151263508Sdim unsigned createFrom(unsigned OldReg); 152234285Sdim 153234285Sdim /// create - Create a new register with the same class and original slot as 154234285Sdim /// parent. 155263508Sdim LiveInterval &createEmptyInterval() { 156263508Sdim return createEmptyIntervalFrom(getReg()); 157263508Sdim } 158263508Sdim 159263508Sdim unsigned create() { 160234285Sdim return createFrom(getReg()); 161234285Sdim } 162234285Sdim 163234285Sdim /// anyRematerializable - Return true if any parent values may be 164234285Sdim /// rematerializable. 165234285Sdim /// This function must be called before any rematerialization is attempted. 166234285Sdim bool anyRematerializable(AliasAnalysis*); 167234285Sdim 168234285Sdim /// checkRematerializable - Manually add VNI to the list of rematerializable 169234285Sdim /// values if DefMI may be rematerializable. 170234285Sdim bool checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI, 171234285Sdim AliasAnalysis*); 172234285Sdim 173234285Sdim /// Remat - Information needed to rematerialize at a specific location. 174234285Sdim struct Remat { 175234285Sdim VNInfo *ParentVNI; // parent_'s value at the remat location. 176234285Sdim MachineInstr *OrigMI; // Instruction defining ParentVNI. 177234285Sdim explicit Remat(VNInfo *ParentVNI) : ParentVNI(ParentVNI), OrigMI(0) {} 178234285Sdim }; 179234285Sdim 180234285Sdim /// canRematerializeAt - Determine if ParentVNI can be rematerialized at 181234285Sdim /// UseIdx. It is assumed that parent_.getVNINfoAt(UseIdx) == ParentVNI. 182234285Sdim /// When cheapAsAMove is set, only cheap remats are allowed. 183234285Sdim bool canRematerializeAt(Remat &RM, 184234285Sdim SlotIndex UseIdx, 185234285Sdim bool cheapAsAMove); 186234285Sdim 187234285Sdim /// rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an 188234285Sdim /// instruction into MBB before MI. The new instruction is mapped, but 189234285Sdim /// liveness is not updated. 190234285Sdim /// Return the SlotIndex of the new instruction. 191234285Sdim SlotIndex rematerializeAt(MachineBasicBlock &MBB, 192234285Sdim MachineBasicBlock::iterator MI, 193234285Sdim unsigned DestReg, 194234285Sdim const Remat &RM, 195234285Sdim const TargetRegisterInfo&, 196234285Sdim bool Late = false); 197234285Sdim 198234285Sdim /// markRematerialized - explicitly mark a value as rematerialized after doing 199234285Sdim /// it manually. 200234285Sdim void markRematerialized(const VNInfo *ParentVNI) { 201239462Sdim Rematted.insert(ParentVNI); 202234285Sdim } 203234285Sdim 204234285Sdim /// didRematerialize - Return true if ParentVNI was rematerialized anywhere. 205234285Sdim bool didRematerialize(const VNInfo *ParentVNI) const { 206239462Sdim return Rematted.count(ParentVNI); 207234285Sdim } 208234285Sdim 209234285Sdim /// eraseVirtReg - Notify the delegate that Reg is no longer in use, and try 210234285Sdim /// to erase it from LIS. 211234285Sdim void eraseVirtReg(unsigned Reg); 212234285Sdim 213234285Sdim /// eliminateDeadDefs - Try to delete machine instructions that are now dead 214234285Sdim /// (allDefsAreDead returns true). This may cause live intervals to be trimmed 215234285Sdim /// and further dead efs to be eliminated. 216234285Sdim /// RegsBeingSpilled lists registers currently being spilled by the register 217234285Sdim /// allocator. These registers should not be split into new intervals 218234285Sdim /// as currently those new intervals are not guaranteed to spill. 219234285Sdim void eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead, 220251662Sdim ArrayRef<unsigned> RegsBeingSpilled = None); 221234285Sdim 222234285Sdim /// calculateRegClassAndHint - Recompute register class and hint for each new 223234285Sdim /// register. 224234285Sdim void calculateRegClassAndHint(MachineFunction&, 225263508Sdim const MachineLoopInfo&, 226263508Sdim const MachineBlockFrequencyInfo&); 227234285Sdim}; 228234285Sdim 229234285Sdim} 230234285Sdim 231234285Sdim#endif 232