LiveRangeEdit.h revision 309124
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" 22261991Sdim#include "llvm/ADT/SetVector.h" 23234285Sdim#include "llvm/ADT/SmallPtrSet.h" 24296417Sdim#include "llvm/Analysis/AliasAnalysis.h" 25234285Sdim#include "llvm/CodeGen/LiveInterval.h" 26261991Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 27234285Sdim#include "llvm/Target/TargetMachine.h" 28280031Sdim#include "llvm/Target/TargetSubtargetInfo.h" 29234285Sdim 30234285Sdimnamespace llvm { 31234285Sdim 32234285Sdimclass LiveIntervals; 33261991Sdimclass MachineBlockFrequencyInfo; 34234285Sdimclass MachineLoopInfo; 35234285Sdimclass VirtRegMap; 36234285Sdim 37261991Sdimclass LiveRangeEdit : private MachineRegisterInfo::Delegate { 38234285Sdimpublic: 39234285Sdim /// Callback methods for LiveRangeEdit owners. 40234285Sdim class Delegate { 41234285Sdim virtual void anchor(); 42234285Sdim public: 43234285Sdim /// Called immediately before erasing a dead machine instruction. 44234285Sdim virtual void LRE_WillEraseInstruction(MachineInstr *MI) {} 45234285Sdim 46234285Sdim /// Called when a virtual register is no longer used. Return false to defer 47234285Sdim /// its deletion from LiveIntervals. 48234285Sdim virtual bool LRE_CanEraseVirtReg(unsigned) { return true; } 49234285Sdim 50234285Sdim /// Called before shrinking the live range of a virtual register. 51234285Sdim virtual void LRE_WillShrinkVirtReg(unsigned) {} 52234285Sdim 53234285Sdim /// Called after cloning a virtual register. 54234285Sdim /// This is used for new registers representing connected components of Old. 55234285Sdim virtual void LRE_DidCloneVirtReg(unsigned New, unsigned Old) {} 56234285Sdim 57234285Sdim virtual ~Delegate() {} 58234285Sdim }; 59234285Sdim 60234285Sdimprivate: 61239462Sdim LiveInterval *Parent; 62261991Sdim SmallVectorImpl<unsigned> &NewRegs; 63234285Sdim MachineRegisterInfo &MRI; 64234285Sdim LiveIntervals &LIS; 65234285Sdim VirtRegMap *VRM; 66234285Sdim const TargetInstrInfo &TII; 67239462Sdim Delegate *const TheDelegate; 68234285Sdim 69239462Sdim /// FirstNew - Index of the first register added to NewRegs. 70239462Sdim const unsigned FirstNew; 71234285Sdim 72239462Sdim /// ScannedRemattable - true when remattable values have been identified. 73239462Sdim bool ScannedRemattable; 74234285Sdim 75309124Sdim /// DeadRemats - The saved instructions which have already been dead after 76309124Sdim /// rematerialization but not deleted yet -- to be done in postOptimization. 77309124Sdim SmallPtrSet<MachineInstr *, 32> *DeadRemats; 78309124Sdim 79239462Sdim /// Remattable - Values defined by remattable instructions as identified by 80234285Sdim /// tii.isTriviallyReMaterializable(). 81239462Sdim SmallPtrSet<const VNInfo*,4> Remattable; 82234285Sdim 83239462Sdim /// Rematted - Values that were actually rematted, and so need to have their 84234285Sdim /// live range trimmed or entirely removed. 85239462Sdim SmallPtrSet<const VNInfo*,4> Rematted; 86234285Sdim 87239462Sdim /// scanRemattable - Identify the Parent values that may rematerialize. 88234285Sdim void scanRemattable(AliasAnalysis *aa); 89234285Sdim 90234285Sdim /// allUsesAvailableAt - Return true if all registers used by OrigMI at 91234285Sdim /// OrigIdx are also available with the same value at UseIdx. 92234285Sdim bool allUsesAvailableAt(const MachineInstr *OrigMI, SlotIndex OrigIdx, 93249423Sdim SlotIndex UseIdx) const; 94234285Sdim 95234285Sdim /// foldAsLoad - If LI has a single use and a single def that can be folded as 96234285Sdim /// a load, eliminate the register by folding the def into the use. 97234285Sdim bool foldAsLoad(LiveInterval *LI, SmallVectorImpl<MachineInstr*> &Dead); 98234285Sdim 99261991Sdim typedef SetVector<LiveInterval*, 100261991Sdim SmallVector<LiveInterval*, 8>, 101261991Sdim SmallPtrSet<LiveInterval*, 8> > ToShrinkSet; 102261991Sdim /// Helper for eliminateDeadDefs. 103309124Sdim void eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink, 104309124Sdim AliasAnalysis *AA); 105261991Sdim 106261991Sdim /// MachineRegisterInfo callback to notify when new virtual 107261991Sdim /// registers are created. 108276479Sdim void MRI_NoteNewVirtualRegister(unsigned VReg) override; 109261991Sdim 110288943Sdim /// \brief Check if MachineOperand \p MO is a last use/kill either in the 111288943Sdim /// main live range of \p LI or in one of the matching subregister ranges. 112288943Sdim bool useIsKill(const LiveInterval &LI, const MachineOperand &MO) const; 113288943Sdim 114234285Sdimpublic: 115234285Sdim /// Create a LiveRangeEdit for breaking down parent into smaller pieces. 116234285Sdim /// @param parent The register being spilled or split. 117234285Sdim /// @param newRegs List to receive any new registers created. This needn't be 118234285Sdim /// empty initially, any existing registers are ignored. 119234285Sdim /// @param MF The MachineFunction the live range edit is taking place in. 120234285Sdim /// @param lis The collection of all live intervals in this function. 121234285Sdim /// @param vrm Map of virtual registers to physical registers for this 122234285Sdim /// function. If NULL, no virtual register map updates will 123234285Sdim /// be done. This could be the case if called before Regalloc. 124309124Sdim /// @param deadRemats The collection of all the instructions defining an 125309124Sdim /// original reg and are dead after remat. 126280031Sdim LiveRangeEdit(LiveInterval *parent, SmallVectorImpl<unsigned> &newRegs, 127280031Sdim MachineFunction &MF, LiveIntervals &lis, VirtRegMap *vrm, 128309124Sdim Delegate *delegate = nullptr, 129309124Sdim SmallPtrSet<MachineInstr *, 32> *deadRemats = nullptr) 130280031Sdim : Parent(parent), NewRegs(newRegs), MRI(MF.getRegInfo()), LIS(lis), 131309124Sdim VRM(vrm), TII(*MF.getSubtarget().getInstrInfo()), TheDelegate(delegate), 132309124Sdim FirstNew(newRegs.size()), ScannedRemattable(false), 133309124Sdim DeadRemats(deadRemats) { 134280031Sdim MRI.setDelegate(this); 135280031Sdim } 136234285Sdim 137288943Sdim ~LiveRangeEdit() override { MRI.resetDelegate(this); } 138261991Sdim 139239462Sdim LiveInterval &getParent() const { 140239462Sdim assert(Parent && "No parent LiveInterval"); 141239462Sdim return *Parent; 142239462Sdim } 143239462Sdim unsigned getReg() const { return getParent().reg; } 144234285Sdim 145234285Sdim /// Iterator for accessing the new registers added by this edit. 146261991Sdim typedef SmallVectorImpl<unsigned>::const_iterator iterator; 147239462Sdim iterator begin() const { return NewRegs.begin()+FirstNew; } 148239462Sdim iterator end() const { return NewRegs.end(); } 149239462Sdim unsigned size() const { return NewRegs.size()-FirstNew; } 150234285Sdim bool empty() const { return size() == 0; } 151261991Sdim unsigned get(unsigned idx) const { return NewRegs[idx+FirstNew]; } 152234285Sdim 153309124Sdim /// pop_back - It allows LiveRangeEdit users to drop new registers. 154309124Sdim /// The context is when an original def instruction of a register is 155309124Sdim /// dead after rematerialization, we still want to keep it for following 156309124Sdim /// rematerializations. We save the def instruction in DeadRemats, 157309124Sdim /// and replace the original dst register with a new dummy register so 158309124Sdim /// the live range of original dst register can be shrinked normally. 159309124Sdim /// We don't want to allocate phys register for the dummy register, so 160309124Sdim /// we want to drop it from the NewRegs set. 161309124Sdim void pop_back() { NewRegs.pop_back(); } 162309124Sdim 163261991Sdim ArrayRef<unsigned> regs() const { 164239462Sdim return makeArrayRef(NewRegs).slice(FirstNew); 165234285Sdim } 166234285Sdim 167261991Sdim /// createEmptyIntervalFrom - Create a new empty interval based on OldReg. 168261991Sdim LiveInterval &createEmptyIntervalFrom(unsigned OldReg); 169261991Sdim 170234285Sdim /// createFrom - Create a new virtual register based on OldReg. 171261991Sdim unsigned createFrom(unsigned OldReg); 172234285Sdim 173234285Sdim /// create - Create a new register with the same class and original slot as 174234285Sdim /// parent. 175261991Sdim LiveInterval &createEmptyInterval() { 176261991Sdim return createEmptyIntervalFrom(getReg()); 177261991Sdim } 178261991Sdim 179261991Sdim unsigned create() { 180234285Sdim return createFrom(getReg()); 181234285Sdim } 182234285Sdim 183234285Sdim /// anyRematerializable - Return true if any parent values may be 184234285Sdim /// rematerializable. 185234285Sdim /// This function must be called before any rematerialization is attempted. 186234285Sdim bool anyRematerializable(AliasAnalysis*); 187234285Sdim 188234285Sdim /// checkRematerializable - Manually add VNI to the list of rematerializable 189234285Sdim /// values if DefMI may be rematerializable. 190234285Sdim bool checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI, 191234285Sdim AliasAnalysis*); 192234285Sdim 193234285Sdim /// Remat - Information needed to rematerialize at a specific location. 194234285Sdim struct Remat { 195234285Sdim VNInfo *ParentVNI; // parent_'s value at the remat location. 196309124Sdim MachineInstr *OrigMI; // Instruction defining OrigVNI. It contains the 197309124Sdim // real expr for remat. 198276479Sdim explicit Remat(VNInfo *ParentVNI) : ParentVNI(ParentVNI), OrigMI(nullptr) {} 199234285Sdim }; 200234285Sdim 201234285Sdim /// canRematerializeAt - Determine if ParentVNI can be rematerialized at 202234285Sdim /// UseIdx. It is assumed that parent_.getVNINfoAt(UseIdx) == ParentVNI. 203234285Sdim /// When cheapAsAMove is set, only cheap remats are allowed. 204309124Sdim bool canRematerializeAt(Remat &RM, VNInfo *OrigVNI, SlotIndex UseIdx, 205234285Sdim bool cheapAsAMove); 206234285Sdim 207234285Sdim /// rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an 208234285Sdim /// instruction into MBB before MI. The new instruction is mapped, but 209234285Sdim /// liveness is not updated. 210234285Sdim /// Return the SlotIndex of the new instruction. 211234285Sdim SlotIndex rematerializeAt(MachineBasicBlock &MBB, 212234285Sdim MachineBasicBlock::iterator MI, 213234285Sdim unsigned DestReg, 214234285Sdim const Remat &RM, 215234285Sdim const TargetRegisterInfo&, 216234285Sdim bool Late = false); 217234285Sdim 218234285Sdim /// markRematerialized - explicitly mark a value as rematerialized after doing 219234285Sdim /// it manually. 220234285Sdim void markRematerialized(const VNInfo *ParentVNI) { 221239462Sdim Rematted.insert(ParentVNI); 222234285Sdim } 223234285Sdim 224234285Sdim /// didRematerialize - Return true if ParentVNI was rematerialized anywhere. 225234285Sdim bool didRematerialize(const VNInfo *ParentVNI) const { 226239462Sdim return Rematted.count(ParentVNI); 227234285Sdim } 228234285Sdim 229309124Sdim void markDeadRemat(MachineInstr *inst) { 230309124Sdim // DeadRemats is an optional field. 231309124Sdim if (DeadRemats) 232309124Sdim DeadRemats->insert(inst); 233309124Sdim } 234309124Sdim 235234285Sdim /// eraseVirtReg - Notify the delegate that Reg is no longer in use, and try 236234285Sdim /// to erase it from LIS. 237234285Sdim void eraseVirtReg(unsigned Reg); 238234285Sdim 239234285Sdim /// eliminateDeadDefs - Try to delete machine instructions that are now dead 240234285Sdim /// (allDefsAreDead returns true). This may cause live intervals to be trimmed 241234285Sdim /// and further dead efs to be eliminated. 242234285Sdim /// RegsBeingSpilled lists registers currently being spilled by the register 243234285Sdim /// allocator. These registers should not be split into new intervals 244234285Sdim /// as currently those new intervals are not guaranteed to spill. 245309124Sdim void eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead, 246309124Sdim ArrayRef<unsigned> RegsBeingSpilled = None, 247309124Sdim AliasAnalysis *AA = nullptr); 248234285Sdim 249234285Sdim /// calculateRegClassAndHint - Recompute register class and hint for each new 250234285Sdim /// register. 251234285Sdim void calculateRegClassAndHint(MachineFunction&, 252261991Sdim const MachineLoopInfo&, 253261991Sdim const MachineBlockFrequencyInfo&); 254234285Sdim}; 255234285Sdim 256234285Sdim} 257234285Sdim 258234285Sdim#endif 259