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