1 //===---- LiveRangeEdit.h - Basic tools for split and spill -----*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // The LiveRangeEdit class represents changes done to a virtual register when it 11 // is spilled or split. 12 // 13 // The parent register is never changed. Instead, a number of new virtual 14 // registers are created and added to the newRegs vector. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #ifndef LLVM_CODEGEN_LIVERANGEEDIT_H 19 #define LLVM_CODEGEN_LIVERANGEEDIT_H 20 21 #include "llvm/ADT/ArrayRef.h" 22 #include "llvm/ADT/SmallPtrSet.h" 23 #include "llvm/CodeGen/LiveInterval.h" 24 25 namespace llvm { 26 27 class AliasAnalysis; 28 class LiveIntervals; 29 class MachineLoopInfo; 30 class MachineRegisterInfo; 31 class VirtRegMap; 32 33 class LiveRangeEdit { 34 public: 35 /// Callback methods for LiveRangeEdit owners. 36 struct Delegate { 37 /// Called immediately before erasing a dead machine instruction. LRE_WillEraseInstructionDelegate38 virtual void LRE_WillEraseInstruction(MachineInstr *MI) {} 39 40 /// Called when a virtual register is no longer used. Return false to defer 41 /// its deletion from LiveIntervals. LRE_CanEraseVirtRegDelegate42 virtual bool LRE_CanEraseVirtReg(unsigned) { return true; } 43 44 /// Called before shrinking the live range of a virtual register. LRE_WillShrinkVirtRegDelegate45 virtual void LRE_WillShrinkVirtReg(unsigned) {} 46 47 /// Called after cloning a virtual register. 48 /// This is used for new registers representing connected components of Old. LRE_DidCloneVirtRegDelegate49 virtual void LRE_DidCloneVirtReg(unsigned New, unsigned Old) {} 50 ~DelegateDelegate51 virtual ~Delegate() {} 52 }; 53 54 private: 55 LiveInterval &parent_; 56 SmallVectorImpl<LiveInterval*> &newRegs_; 57 Delegate *const delegate_; 58 const SmallVectorImpl<LiveInterval*> *uselessRegs_; 59 60 /// firstNew_ - Index of the first register added to newRegs_. 61 const unsigned firstNew_; 62 63 /// scannedRemattable_ - true when remattable values have been identified. 64 bool scannedRemattable_; 65 66 /// remattable_ - Values defined by remattable instructions as identified by 67 /// tii.isTriviallyReMaterializable(). 68 SmallPtrSet<const VNInfo*,4> remattable_; 69 70 /// rematted_ - Values that were actually rematted, and so need to have their 71 /// live range trimmed or entirely removed. 72 SmallPtrSet<const VNInfo*,4> rematted_; 73 74 /// scanRemattable - Identify the parent_ values that may rematerialize. 75 void scanRemattable(LiveIntervals &lis, 76 const TargetInstrInfo &tii, 77 AliasAnalysis *aa); 78 79 /// allUsesAvailableAt - Return true if all registers used by OrigMI at 80 /// OrigIdx are also available with the same value at UseIdx. 81 bool allUsesAvailableAt(const MachineInstr *OrigMI, SlotIndex OrigIdx, 82 SlotIndex UseIdx, LiveIntervals &lis); 83 84 /// foldAsLoad - If LI has a single use and a single def that can be folded as 85 /// a load, eliminate the register by folding the def into the use. 86 bool foldAsLoad(LiveInterval *LI, SmallVectorImpl<MachineInstr*> &Dead, 87 MachineRegisterInfo&, LiveIntervals&, const TargetInstrInfo&); 88 89 public: 90 /// Create a LiveRangeEdit for breaking down parent into smaller pieces. 91 /// @param parent The register being spilled or split. 92 /// @param newRegs List to receive any new registers created. This needn't be 93 /// empty initially, any existing registers are ignored. 94 /// @param uselessRegs List of registers that can't be used when 95 /// rematerializing values because they are about to be removed. 96 LiveRangeEdit(LiveInterval &parent, 97 SmallVectorImpl<LiveInterval*> &newRegs, 98 Delegate *delegate = 0, 99 const SmallVectorImpl<LiveInterval*> *uselessRegs = 0) parent_(parent)100 : parent_(parent), newRegs_(newRegs), 101 delegate_(delegate), 102 uselessRegs_(uselessRegs), 103 firstNew_(newRegs.size()), 104 scannedRemattable_(false) {} 105 getParent()106 LiveInterval &getParent() const { return parent_; } getReg()107 unsigned getReg() const { return parent_.reg; } 108 109 /// Iterator for accessing the new registers added by this edit. 110 typedef SmallVectorImpl<LiveInterval*>::const_iterator iterator; begin()111 iterator begin() const { return newRegs_.begin()+firstNew_; } end()112 iterator end() const { return newRegs_.end(); } size()113 unsigned size() const { return newRegs_.size()-firstNew_; } empty()114 bool empty() const { return size() == 0; } get(unsigned idx)115 LiveInterval *get(unsigned idx) const { return newRegs_[idx+firstNew_]; } 116 regs()117 ArrayRef<LiveInterval*> regs() const { 118 return makeArrayRef(newRegs_).slice(firstNew_); 119 } 120 121 /// FIXME: Temporary accessors until we can get rid of 122 /// LiveIntervals::AddIntervalsForSpills getNewVRegs()123 SmallVectorImpl<LiveInterval*> *getNewVRegs() { return &newRegs_; } getUselessVRegs()124 const SmallVectorImpl<LiveInterval*> *getUselessVRegs() { 125 return uselessRegs_; 126 } 127 128 /// createFrom - Create a new virtual register based on OldReg. 129 LiveInterval &createFrom(unsigned OldReg, LiveIntervals&, VirtRegMap&); 130 131 /// create - Create a new register with the same class and original slot as 132 /// parent. create(LiveIntervals & LIS,VirtRegMap & VRM)133 LiveInterval &create(LiveIntervals &LIS, VirtRegMap &VRM) { 134 return createFrom(getReg(), LIS, VRM); 135 } 136 137 /// anyRematerializable - Return true if any parent values may be 138 /// rematerializable. 139 /// This function must be called before any rematerialization is attempted. 140 bool anyRematerializable(LiveIntervals&, const TargetInstrInfo&, 141 AliasAnalysis*); 142 143 /// checkRematerializable - Manually add VNI to the list of rematerializable 144 /// values if DefMI may be rematerializable. 145 bool checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI, 146 const TargetInstrInfo&, AliasAnalysis*); 147 148 /// Remat - Information needed to rematerialize at a specific location. 149 struct Remat { 150 VNInfo *ParentVNI; // parent_'s value at the remat location. 151 MachineInstr *OrigMI; // Instruction defining ParentVNI. RematRemat152 explicit Remat(VNInfo *ParentVNI) : ParentVNI(ParentVNI), OrigMI(0) {} 153 }; 154 155 /// canRematerializeAt - Determine if ParentVNI can be rematerialized at 156 /// UseIdx. It is assumed that parent_.getVNINfoAt(UseIdx) == ParentVNI. 157 /// When cheapAsAMove is set, only cheap remats are allowed. 158 bool canRematerializeAt(Remat &RM, 159 SlotIndex UseIdx, 160 bool cheapAsAMove, 161 LiveIntervals &lis); 162 163 /// rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an 164 /// instruction into MBB before MI. The new instruction is mapped, but 165 /// liveness is not updated. 166 /// Return the SlotIndex of the new instruction. 167 SlotIndex rematerializeAt(MachineBasicBlock &MBB, 168 MachineBasicBlock::iterator MI, 169 unsigned DestReg, 170 const Remat &RM, 171 LiveIntervals&, 172 const TargetInstrInfo&, 173 const TargetRegisterInfo&, 174 bool Late = false); 175 176 /// markRematerialized - explicitly mark a value as rematerialized after doing 177 /// it manually. markRematerialized(const VNInfo * ParentVNI)178 void markRematerialized(const VNInfo *ParentVNI) { 179 rematted_.insert(ParentVNI); 180 } 181 182 /// didRematerialize - Return true if ParentVNI was rematerialized anywhere. didRematerialize(const VNInfo * ParentVNI)183 bool didRematerialize(const VNInfo *ParentVNI) const { 184 return rematted_.count(ParentVNI); 185 } 186 187 /// eraseVirtReg - Notify the delegate that Reg is no longer in use, and try 188 /// to erase it from LIS. 189 void eraseVirtReg(unsigned Reg, LiveIntervals &LIS); 190 191 /// eliminateDeadDefs - Try to delete machine instructions that are now dead 192 /// (allDefsAreDead returns true). This may cause live intervals to be trimmed 193 /// and further dead efs to be eliminated. 194 void eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead, 195 LiveIntervals&, VirtRegMap&, 196 const TargetInstrInfo&); 197 198 /// calculateRegClassAndHint - Recompute register class and hint for each new 199 /// register. 200 void calculateRegClassAndHint(MachineFunction&, LiveIntervals&, 201 const MachineLoopInfo&); 202 }; 203 204 } 205 206 #endif 207