1 //===- LiveRangeEdit.h - Basic tools for split and spill --------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // The LiveRangeEdit class represents changes done to a virtual register when it 10 // is spilled or split. 11 // 12 // The parent register is never changed. Instead, a number of new virtual 13 // registers are created and added to the newRegs vector. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #ifndef LLVM_CODEGEN_LIVERANGEEDIT_H 18 #define LLVM_CODEGEN_LIVERANGEEDIT_H 19 20 #include "llvm/ADT/ArrayRef.h" 21 #include "llvm/ADT/None.h" 22 #include "llvm/ADT/SetVector.h" 23 #include "llvm/ADT/SmallPtrSet.h" 24 #include "llvm/ADT/SmallVector.h" 25 #include "llvm/Analysis/AliasAnalysis.h" 26 #include "llvm/CodeGen/LiveInterval.h" 27 #include "llvm/CodeGen/MachineBasicBlock.h" 28 #include "llvm/CodeGen/MachineFunction.h" 29 #include "llvm/CodeGen/MachineRegisterInfo.h" 30 #include "llvm/CodeGen/SlotIndexes.h" 31 #include "llvm/CodeGen/TargetSubtargetInfo.h" 32 #include <cassert> 33 34 namespace llvm { 35 36 class LiveIntervals; 37 class MachineBlockFrequencyInfo; 38 class MachineInstr; 39 class MachineLoopInfo; 40 class MachineOperand; 41 class TargetInstrInfo; 42 class TargetRegisterInfo; 43 class VirtRegMap; 44 45 class LiveRangeEdit : private MachineRegisterInfo::Delegate { 46 public: 47 /// Callback methods for LiveRangeEdit owners. 48 class Delegate { 49 virtual void anchor(); 50 51 public: 52 virtual ~Delegate() = default; 53 54 /// Called immediately before erasing a dead machine instruction. LRE_WillEraseInstruction(MachineInstr * MI)55 virtual void LRE_WillEraseInstruction(MachineInstr *MI) {} 56 57 /// Called when a virtual register is no longer used. Return false to defer 58 /// its deletion from LiveIntervals. LRE_CanEraseVirtReg(unsigned)59 virtual bool LRE_CanEraseVirtReg(unsigned) { return true; } 60 61 /// Called before shrinking the live range of a virtual register. LRE_WillShrinkVirtReg(unsigned)62 virtual void LRE_WillShrinkVirtReg(unsigned) {} 63 64 /// Called after cloning a virtual register. 65 /// This is used for new registers representing connected components of Old. LRE_DidCloneVirtReg(unsigned New,unsigned Old)66 virtual void LRE_DidCloneVirtReg(unsigned New, unsigned Old) {} 67 }; 68 69 private: 70 LiveInterval *Parent; 71 SmallVectorImpl<unsigned> &NewRegs; 72 MachineRegisterInfo &MRI; 73 LiveIntervals &LIS; 74 VirtRegMap *VRM; 75 const TargetInstrInfo &TII; 76 Delegate *const TheDelegate; 77 78 /// FirstNew - Index of the first register added to NewRegs. 79 const unsigned FirstNew; 80 81 /// ScannedRemattable - true when remattable values have been identified. 82 bool ScannedRemattable = false; 83 84 /// DeadRemats - The saved instructions which have already been dead after 85 /// rematerialization but not deleted yet -- to be done in postOptimization. 86 SmallPtrSet<MachineInstr *, 32> *DeadRemats; 87 88 /// Remattable - Values defined by remattable instructions as identified by 89 /// tii.isTriviallyReMaterializable(). 90 SmallPtrSet<const VNInfo *, 4> Remattable; 91 92 /// Rematted - Values that were actually rematted, and so need to have their 93 /// live range trimmed or entirely removed. 94 SmallPtrSet<const VNInfo *, 4> Rematted; 95 96 /// scanRemattable - Identify the Parent values that may rematerialize. 97 void scanRemattable(AliasAnalysis *aa); 98 99 /// allUsesAvailableAt - Return true if all registers used by OrigMI at 100 /// OrigIdx are also available with the same value at UseIdx. 101 bool allUsesAvailableAt(const MachineInstr *OrigMI, SlotIndex OrigIdx, 102 SlotIndex UseIdx) const; 103 104 /// foldAsLoad - If LI has a single use and a single def that can be folded as 105 /// a load, eliminate the register by folding the def into the use. 106 bool foldAsLoad(LiveInterval *LI, SmallVectorImpl<MachineInstr *> &Dead); 107 108 using ToShrinkSet = SetVector<LiveInterval *, SmallVector<LiveInterval *, 8>, 109 SmallPtrSet<LiveInterval *, 8>>; 110 111 /// Helper for eliminateDeadDefs. 112 void eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink, 113 AliasAnalysis *AA); 114 115 /// MachineRegisterInfo callback to notify when new virtual 116 /// registers are created. 117 void MRI_NoteNewVirtualRegister(unsigned VReg) override; 118 119 /// Check if MachineOperand \p MO is a last use/kill either in the 120 /// main live range of \p LI or in one of the matching subregister ranges. 121 bool useIsKill(const LiveInterval &LI, const MachineOperand &MO) const; 122 123 /// Create a new empty interval based on OldReg. 124 LiveInterval &createEmptyIntervalFrom(unsigned OldReg, bool createSubRanges); 125 126 public: 127 /// Create a LiveRangeEdit for breaking down parent into smaller pieces. 128 /// @param parent The register being spilled or split. 129 /// @param newRegs List to receive any new registers created. This needn't be 130 /// empty initially, any existing registers are ignored. 131 /// @param MF The MachineFunction the live range edit is taking place in. 132 /// @param lis The collection of all live intervals in this function. 133 /// @param vrm Map of virtual registers to physical registers for this 134 /// function. If NULL, no virtual register map updates will 135 /// be done. This could be the case if called before Regalloc. 136 /// @param deadRemats The collection of all the instructions defining an 137 /// original reg and are dead after remat. 138 LiveRangeEdit(LiveInterval *parent, SmallVectorImpl<unsigned> &newRegs, 139 MachineFunction &MF, LiveIntervals &lis, VirtRegMap *vrm, 140 Delegate *delegate = nullptr, 141 SmallPtrSet<MachineInstr *, 32> *deadRemats = nullptr) Parent(parent)142 : Parent(parent), NewRegs(newRegs), MRI(MF.getRegInfo()), LIS(lis), 143 VRM(vrm), TII(*MF.getSubtarget().getInstrInfo()), TheDelegate(delegate), 144 FirstNew(newRegs.size()), DeadRemats(deadRemats) { 145 MRI.setDelegate(this); 146 } 147 ~LiveRangeEdit()148 ~LiveRangeEdit() override { MRI.resetDelegate(this); } 149 getParent()150 LiveInterval &getParent() const { 151 assert(Parent && "No parent LiveInterval"); 152 return *Parent; 153 } 154 getReg()155 unsigned getReg() const { return getParent().reg; } 156 157 /// Iterator for accessing the new registers added by this edit. 158 using iterator = SmallVectorImpl<unsigned>::const_iterator; begin()159 iterator begin() const { return NewRegs.begin() + FirstNew; } end()160 iterator end() const { return NewRegs.end(); } size()161 unsigned size() const { return NewRegs.size() - FirstNew; } empty()162 bool empty() const { return size() == 0; } get(unsigned idx)163 unsigned get(unsigned idx) const { return NewRegs[idx + FirstNew]; } 164 165 /// pop_back - It allows LiveRangeEdit users to drop new registers. 166 /// The context is when an original def instruction of a register is 167 /// dead after rematerialization, we still want to keep it for following 168 /// rematerializations. We save the def instruction in DeadRemats, 169 /// and replace the original dst register with a new dummy register so 170 /// the live range of original dst register can be shrinked normally. 171 /// We don't want to allocate phys register for the dummy register, so 172 /// we want to drop it from the NewRegs set. pop_back()173 void pop_back() { NewRegs.pop_back(); } 174 regs()175 ArrayRef<unsigned> regs() const { 176 return makeArrayRef(NewRegs).slice(FirstNew); 177 } 178 179 /// createFrom - Create a new virtual register based on OldReg. 180 unsigned createFrom(unsigned OldReg); 181 182 /// create - Create a new register with the same class and original slot as 183 /// parent. createEmptyInterval()184 LiveInterval &createEmptyInterval() { 185 return createEmptyIntervalFrom(getReg(), true); 186 } 187 create()188 unsigned create() { return createFrom(getReg()); } 189 190 /// anyRematerializable - Return true if any parent values may be 191 /// rematerializable. 192 /// This function must be called before any rematerialization is attempted. 193 bool anyRematerializable(AliasAnalysis *); 194 195 /// checkRematerializable - Manually add VNI to the list of rematerializable 196 /// values if DefMI may be rematerializable. 197 bool checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI, 198 AliasAnalysis *); 199 200 /// Remat - Information needed to rematerialize at a specific location. 201 struct Remat { 202 VNInfo *ParentVNI; // parent_'s value at the remat location. 203 MachineInstr *OrigMI = nullptr; // Instruction defining OrigVNI. It contains 204 // the real expr for remat. 205 RematRemat206 explicit Remat(VNInfo *ParentVNI) : ParentVNI(ParentVNI) {} 207 }; 208 209 /// canRematerializeAt - Determine if ParentVNI can be rematerialized at 210 /// UseIdx. It is assumed that parent_.getVNINfoAt(UseIdx) == ParentVNI. 211 /// When cheapAsAMove is set, only cheap remats are allowed. 212 bool canRematerializeAt(Remat &RM, VNInfo *OrigVNI, SlotIndex UseIdx, 213 bool cheapAsAMove); 214 215 /// rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an 216 /// instruction into MBB before MI. The new instruction is mapped, but 217 /// liveness is not updated. 218 /// Return the SlotIndex of the new instruction. 219 SlotIndex rematerializeAt(MachineBasicBlock &MBB, 220 MachineBasicBlock::iterator MI, unsigned DestReg, 221 const Remat &RM, const TargetRegisterInfo &, 222 bool Late = false); 223 224 /// markRematerialized - explicitly mark a value as rematerialized after doing 225 /// it manually. markRematerialized(const VNInfo * ParentVNI)226 void markRematerialized(const VNInfo *ParentVNI) { 227 Rematted.insert(ParentVNI); 228 } 229 230 /// didRematerialize - Return true if ParentVNI was rematerialized anywhere. didRematerialize(const VNInfo * ParentVNI)231 bool didRematerialize(const VNInfo *ParentVNI) const { 232 return Rematted.count(ParentVNI); 233 } 234 235 /// eraseVirtReg - Notify the delegate that Reg is no longer in use, and try 236 /// to erase it from LIS. 237 void eraseVirtReg(unsigned Reg); 238 239 /// eliminateDeadDefs - Try to delete machine instructions that are now dead 240 /// (allDefsAreDead returns true). This may cause live intervals to be trimmed 241 /// and further dead efs to be eliminated. 242 /// RegsBeingSpilled lists registers currently being spilled by the register 243 /// allocator. These registers should not be split into new intervals 244 /// as currently those new intervals are not guaranteed to spill. 245 void eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead, 246 ArrayRef<unsigned> RegsBeingSpilled = None, 247 AliasAnalysis *AA = nullptr); 248 249 /// calculateRegClassAndHint - Recompute register class and hint for each new 250 /// register. 251 void calculateRegClassAndHint(MachineFunction &, const MachineLoopInfo &, 252 const MachineBlockFrequencyInfo &); 253 }; 254 255 } // end namespace llvm 256 257 #endif // LLVM_CODEGEN_LIVERANGEEDIT_H 258