LiveRangeEdit.h revision 296417
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 75239462Sdim /// Remattable - Values defined by remattable instructions as identified by 76234285Sdim /// tii.isTriviallyReMaterializable(). 77239462Sdim SmallPtrSet<const VNInfo*,4> Remattable; 78234285Sdim 79239462Sdim /// Rematted - Values that were actually rematted, and so need to have their 80234285Sdim /// live range trimmed or entirely removed. 81239462Sdim SmallPtrSet<const VNInfo*,4> Rematted; 82234285Sdim 83239462Sdim /// scanRemattable - Identify the Parent values that may rematerialize. 84234285Sdim void scanRemattable(AliasAnalysis *aa); 85234285Sdim 86234285Sdim /// allUsesAvailableAt - Return true if all registers used by OrigMI at 87234285Sdim /// OrigIdx are also available with the same value at UseIdx. 88234285Sdim bool allUsesAvailableAt(const MachineInstr *OrigMI, SlotIndex OrigIdx, 89249423Sdim SlotIndex UseIdx) const; 90234285Sdim 91234285Sdim /// foldAsLoad - If LI has a single use and a single def that can be folded as 92234285Sdim /// a load, eliminate the register by folding the def into the use. 93234285Sdim bool foldAsLoad(LiveInterval *LI, SmallVectorImpl<MachineInstr*> &Dead); 94234285Sdim 95261991Sdim typedef SetVector<LiveInterval*, 96261991Sdim SmallVector<LiveInterval*, 8>, 97261991Sdim SmallPtrSet<LiveInterval*, 8> > ToShrinkSet; 98261991Sdim /// Helper for eliminateDeadDefs. 99261991Sdim void eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink); 100261991Sdim 101261991Sdim /// MachineRegisterInfo callback to notify when new virtual 102261991Sdim /// registers are created. 103276479Sdim void MRI_NoteNewVirtualRegister(unsigned VReg) override; 104261991Sdim 105288943Sdim /// \brief Check if MachineOperand \p MO is a last use/kill either in the 106288943Sdim /// main live range of \p LI or in one of the matching subregister ranges. 107288943Sdim bool useIsKill(const LiveInterval &LI, const MachineOperand &MO) const; 108288943Sdim 109234285Sdimpublic: 110234285Sdim /// Create a LiveRangeEdit for breaking down parent into smaller pieces. 111234285Sdim /// @param parent The register being spilled or split. 112234285Sdim /// @param newRegs List to receive any new registers created. This needn't be 113234285Sdim /// empty initially, any existing registers are ignored. 114234285Sdim /// @param MF The MachineFunction the live range edit is taking place in. 115234285Sdim /// @param lis The collection of all live intervals in this function. 116234285Sdim /// @param vrm Map of virtual registers to physical registers for this 117234285Sdim /// function. If NULL, no virtual register map updates will 118234285Sdim /// be done. This could be the case if called before Regalloc. 119280031Sdim LiveRangeEdit(LiveInterval *parent, SmallVectorImpl<unsigned> &newRegs, 120280031Sdim MachineFunction &MF, LiveIntervals &lis, VirtRegMap *vrm, 121276479Sdim Delegate *delegate = nullptr) 122280031Sdim : Parent(parent), NewRegs(newRegs), MRI(MF.getRegInfo()), LIS(lis), 123280031Sdim VRM(vrm), TII(*MF.getSubtarget().getInstrInfo()), 124280031Sdim TheDelegate(delegate), FirstNew(newRegs.size()), 125280031Sdim ScannedRemattable(false) { 126280031Sdim MRI.setDelegate(this); 127280031Sdim } 128234285Sdim 129288943Sdim ~LiveRangeEdit() override { MRI.resetDelegate(this); } 130261991Sdim 131239462Sdim LiveInterval &getParent() const { 132239462Sdim assert(Parent && "No parent LiveInterval"); 133239462Sdim return *Parent; 134239462Sdim } 135239462Sdim unsigned getReg() const { return getParent().reg; } 136234285Sdim 137234285Sdim /// Iterator for accessing the new registers added by this edit. 138261991Sdim typedef SmallVectorImpl<unsigned>::const_iterator iterator; 139239462Sdim iterator begin() const { return NewRegs.begin()+FirstNew; } 140239462Sdim iterator end() const { return NewRegs.end(); } 141239462Sdim unsigned size() const { return NewRegs.size()-FirstNew; } 142234285Sdim bool empty() const { return size() == 0; } 143261991Sdim unsigned get(unsigned idx) const { return NewRegs[idx+FirstNew]; } 144234285Sdim 145261991Sdim ArrayRef<unsigned> regs() const { 146239462Sdim return makeArrayRef(NewRegs).slice(FirstNew); 147234285Sdim } 148234285Sdim 149261991Sdim /// createEmptyIntervalFrom - Create a new empty interval based on OldReg. 150261991Sdim LiveInterval &createEmptyIntervalFrom(unsigned OldReg); 151261991Sdim 152234285Sdim /// createFrom - Create a new virtual register based on OldReg. 153261991Sdim unsigned createFrom(unsigned OldReg); 154234285Sdim 155234285Sdim /// create - Create a new register with the same class and original slot as 156234285Sdim /// parent. 157261991Sdim LiveInterval &createEmptyInterval() { 158261991Sdim return createEmptyIntervalFrom(getReg()); 159261991Sdim } 160261991Sdim 161261991Sdim unsigned create() { 162234285Sdim return createFrom(getReg()); 163234285Sdim } 164234285Sdim 165234285Sdim /// anyRematerializable - Return true if any parent values may be 166234285Sdim /// rematerializable. 167234285Sdim /// This function must be called before any rematerialization is attempted. 168234285Sdim bool anyRematerializable(AliasAnalysis*); 169234285Sdim 170234285Sdim /// checkRematerializable - Manually add VNI to the list of rematerializable 171234285Sdim /// values if DefMI may be rematerializable. 172234285Sdim bool checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI, 173234285Sdim AliasAnalysis*); 174234285Sdim 175234285Sdim /// Remat - Information needed to rematerialize at a specific location. 176234285Sdim struct Remat { 177234285Sdim VNInfo *ParentVNI; // parent_'s value at the remat location. 178234285Sdim MachineInstr *OrigMI; // Instruction defining ParentVNI. 179276479Sdim explicit Remat(VNInfo *ParentVNI) : ParentVNI(ParentVNI), OrigMI(nullptr) {} 180234285Sdim }; 181234285Sdim 182234285Sdim /// canRematerializeAt - Determine if ParentVNI can be rematerialized at 183234285Sdim /// UseIdx. It is assumed that parent_.getVNINfoAt(UseIdx) == ParentVNI. 184234285Sdim /// When cheapAsAMove is set, only cheap remats are allowed. 185234285Sdim bool canRematerializeAt(Remat &RM, 186234285Sdim SlotIndex UseIdx, 187234285Sdim bool cheapAsAMove); 188234285Sdim 189234285Sdim /// rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an 190234285Sdim /// instruction into MBB before MI. The new instruction is mapped, but 191234285Sdim /// liveness is not updated. 192234285Sdim /// Return the SlotIndex of the new instruction. 193234285Sdim SlotIndex rematerializeAt(MachineBasicBlock &MBB, 194234285Sdim MachineBasicBlock::iterator MI, 195234285Sdim unsigned DestReg, 196234285Sdim const Remat &RM, 197234285Sdim const TargetRegisterInfo&, 198234285Sdim bool Late = false); 199234285Sdim 200234285Sdim /// markRematerialized - explicitly mark a value as rematerialized after doing 201234285Sdim /// it manually. 202234285Sdim void markRematerialized(const VNInfo *ParentVNI) { 203239462Sdim Rematted.insert(ParentVNI); 204234285Sdim } 205234285Sdim 206234285Sdim /// didRematerialize - Return true if ParentVNI was rematerialized anywhere. 207234285Sdim bool didRematerialize(const VNInfo *ParentVNI) const { 208239462Sdim return Rematted.count(ParentVNI); 209234285Sdim } 210234285Sdim 211234285Sdim /// eraseVirtReg - Notify the delegate that Reg is no longer in use, and try 212234285Sdim /// to erase it from LIS. 213234285Sdim void eraseVirtReg(unsigned Reg); 214234285Sdim 215234285Sdim /// eliminateDeadDefs - Try to delete machine instructions that are now dead 216234285Sdim /// (allDefsAreDead returns true). This may cause live intervals to be trimmed 217234285Sdim /// and further dead efs to be eliminated. 218234285Sdim /// RegsBeingSpilled lists registers currently being spilled by the register 219234285Sdim /// allocator. These registers should not be split into new intervals 220234285Sdim /// as currently those new intervals are not guaranteed to spill. 221234285Sdim void eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead, 222251662Sdim ArrayRef<unsigned> RegsBeingSpilled = None); 223234285Sdim 224234285Sdim /// calculateRegClassAndHint - Recompute register class and hint for each new 225234285Sdim /// register. 226234285Sdim void calculateRegClassAndHint(MachineFunction&, 227261991Sdim const MachineLoopInfo&, 228261991Sdim const MachineBlockFrequencyInfo&); 229234285Sdim}; 230234285Sdim 231234285Sdim} 232234285Sdim 233234285Sdim#endif 234