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