1321369Sdim//===- LiveRangeEdit.h - Basic tools for split and spill --------*- C++ -*-===// 2234285Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6234285Sdim// 7234285Sdim//===----------------------------------------------------------------------===// 8234285Sdim// 9234285Sdim// The LiveRangeEdit class represents changes done to a virtual register when it 10234285Sdim// is spilled or split. 11234285Sdim// 12234285Sdim// The parent register is never changed. Instead, a number of new virtual 13234285Sdim// registers are created and added to the newRegs vector. 14234285Sdim// 15234285Sdim//===----------------------------------------------------------------------===// 16234285Sdim 17234285Sdim#ifndef LLVM_CODEGEN_LIVERANGEEDIT_H 18234285Sdim#define LLVM_CODEGEN_LIVERANGEEDIT_H 19234285Sdim 20234285Sdim#include "llvm/ADT/ArrayRef.h" 21321369Sdim#include "llvm/ADT/None.h" 22261991Sdim#include "llvm/ADT/SetVector.h" 23234285Sdim#include "llvm/ADT/SmallPtrSet.h" 24321369Sdim#include "llvm/ADT/SmallVector.h" 25296417Sdim#include "llvm/Analysis/AliasAnalysis.h" 26234285Sdim#include "llvm/CodeGen/LiveInterval.h" 27321369Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 28321369Sdim#include "llvm/CodeGen/MachineFunction.h" 29261991Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 30321369Sdim#include "llvm/CodeGen/SlotIndexes.h" 31327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 32321369Sdim#include <cassert> 33234285Sdim 34234285Sdimnamespace llvm { 35234285Sdim 36234285Sdimclass LiveIntervals; 37261991Sdimclass MachineBlockFrequencyInfo; 38321369Sdimclass MachineInstr; 39234285Sdimclass MachineLoopInfo; 40321369Sdimclass MachineOperand; 41321369Sdimclass TargetInstrInfo; 42321369Sdimclass TargetRegisterInfo; 43234285Sdimclass VirtRegMap; 44234285Sdim 45261991Sdimclass LiveRangeEdit : private MachineRegisterInfo::Delegate { 46234285Sdimpublic: 47234285Sdim /// Callback methods for LiveRangeEdit owners. 48234285Sdim class Delegate { 49234285Sdim virtual void anchor(); 50321369Sdim 51234285Sdim public: 52321369Sdim virtual ~Delegate() = default; 53321369Sdim 54234285Sdim /// Called immediately before erasing a dead machine instruction. 55234285Sdim virtual void LRE_WillEraseInstruction(MachineInstr *MI) {} 56234285Sdim 57234285Sdim /// Called when a virtual register is no longer used. Return false to defer 58234285Sdim /// its deletion from LiveIntervals. 59234285Sdim virtual bool LRE_CanEraseVirtReg(unsigned) { return true; } 60234285Sdim 61234285Sdim /// Called before shrinking the live range of a virtual register. 62234285Sdim virtual void LRE_WillShrinkVirtReg(unsigned) {} 63234285Sdim 64234285Sdim /// Called after cloning a virtual register. 65234285Sdim /// This is used for new registers representing connected components of Old. 66234285Sdim virtual void LRE_DidCloneVirtReg(unsigned New, unsigned Old) {} 67234285Sdim }; 68234285Sdim 69234285Sdimprivate: 70239462Sdim LiveInterval *Parent; 71261991Sdim SmallVectorImpl<unsigned> &NewRegs; 72234285Sdim MachineRegisterInfo &MRI; 73234285Sdim LiveIntervals &LIS; 74234285Sdim VirtRegMap *VRM; 75234285Sdim const TargetInstrInfo &TII; 76239462Sdim Delegate *const TheDelegate; 77234285Sdim 78239462Sdim /// FirstNew - Index of the first register added to NewRegs. 79239462Sdim const unsigned FirstNew; 80234285Sdim 81239462Sdim /// ScannedRemattable - true when remattable values have been identified. 82321369Sdim bool ScannedRemattable = false; 83234285Sdim 84309124Sdim /// DeadRemats - The saved instructions which have already been dead after 85309124Sdim /// rematerialization but not deleted yet -- to be done in postOptimization. 86309124Sdim SmallPtrSet<MachineInstr *, 32> *DeadRemats; 87309124Sdim 88239462Sdim /// Remattable - Values defined by remattable instructions as identified by 89234285Sdim /// tii.isTriviallyReMaterializable(). 90321369Sdim SmallPtrSet<const VNInfo *, 4> Remattable; 91234285Sdim 92239462Sdim /// Rematted - Values that were actually rematted, and so need to have their 93234285Sdim /// live range trimmed or entirely removed. 94321369Sdim SmallPtrSet<const VNInfo *, 4> Rematted; 95234285Sdim 96239462Sdim /// scanRemattable - Identify the Parent values that may rematerialize. 97234285Sdim void scanRemattable(AliasAnalysis *aa); 98234285Sdim 99234285Sdim /// allUsesAvailableAt - Return true if all registers used by OrigMI at 100234285Sdim /// OrigIdx are also available with the same value at UseIdx. 101234285Sdim bool allUsesAvailableAt(const MachineInstr *OrigMI, SlotIndex OrigIdx, 102249423Sdim SlotIndex UseIdx) const; 103234285Sdim 104234285Sdim /// foldAsLoad - If LI has a single use and a single def that can be folded as 105234285Sdim /// a load, eliminate the register by folding the def into the use. 106321369Sdim bool foldAsLoad(LiveInterval *LI, SmallVectorImpl<MachineInstr *> &Dead); 107234285Sdim 108321369Sdim using ToShrinkSet = SetVector<LiveInterval *, SmallVector<LiveInterval *, 8>, 109321369Sdim SmallPtrSet<LiveInterval *, 8>>; 110321369Sdim 111261991Sdim /// Helper for eliminateDeadDefs. 112309124Sdim void eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink, 113309124Sdim AliasAnalysis *AA); 114261991Sdim 115261991Sdim /// MachineRegisterInfo callback to notify when new virtual 116261991Sdim /// registers are created. 117276479Sdim void MRI_NoteNewVirtualRegister(unsigned VReg) override; 118261991Sdim 119341825Sdim /// Check if MachineOperand \p MO is a last use/kill either in the 120288943Sdim /// main live range of \p LI or in one of the matching subregister ranges. 121288943Sdim bool useIsKill(const LiveInterval &LI, const MachineOperand &MO) const; 122288943Sdim 123341825Sdim /// Create a new empty interval based on OldReg. 124341825Sdim LiveInterval &createEmptyIntervalFrom(unsigned OldReg, bool createSubRanges); 125341825Sdim 126234285Sdimpublic: 127234285Sdim /// Create a LiveRangeEdit for breaking down parent into smaller pieces. 128234285Sdim /// @param parent The register being spilled or split. 129234285Sdim /// @param newRegs List to receive any new registers created. This needn't be 130234285Sdim /// empty initially, any existing registers are ignored. 131234285Sdim /// @param MF The MachineFunction the live range edit is taking place in. 132234285Sdim /// @param lis The collection of all live intervals in this function. 133234285Sdim /// @param vrm Map of virtual registers to physical registers for this 134234285Sdim /// function. If NULL, no virtual register map updates will 135234285Sdim /// be done. This could be the case if called before Regalloc. 136309124Sdim /// @param deadRemats The collection of all the instructions defining an 137309124Sdim /// original reg and are dead after remat. 138280031Sdim LiveRangeEdit(LiveInterval *parent, SmallVectorImpl<unsigned> &newRegs, 139280031Sdim MachineFunction &MF, LiveIntervals &lis, VirtRegMap *vrm, 140309124Sdim Delegate *delegate = nullptr, 141309124Sdim SmallPtrSet<MachineInstr *, 32> *deadRemats = nullptr) 142280031Sdim : Parent(parent), NewRegs(newRegs), MRI(MF.getRegInfo()), LIS(lis), 143309124Sdim VRM(vrm), TII(*MF.getSubtarget().getInstrInfo()), TheDelegate(delegate), 144321369Sdim FirstNew(newRegs.size()), DeadRemats(deadRemats) { 145280031Sdim MRI.setDelegate(this); 146280031Sdim } 147234285Sdim 148288943Sdim ~LiveRangeEdit() override { MRI.resetDelegate(this); } 149261991Sdim 150239462Sdim LiveInterval &getParent() const { 151321369Sdim assert(Parent && "No parent LiveInterval"); 152321369Sdim return *Parent; 153239462Sdim } 154321369Sdim 155239462Sdim unsigned getReg() const { return getParent().reg; } 156234285Sdim 157234285Sdim /// Iterator for accessing the new registers added by this edit. 158321369Sdim using iterator = SmallVectorImpl<unsigned>::const_iterator; 159321369Sdim iterator begin() const { return NewRegs.begin() + FirstNew; } 160239462Sdim iterator end() const { return NewRegs.end(); } 161321369Sdim unsigned size() const { return NewRegs.size() - FirstNew; } 162234285Sdim bool empty() const { return size() == 0; } 163321369Sdim unsigned get(unsigned idx) const { return NewRegs[idx + FirstNew]; } 164234285Sdim 165309124Sdim /// pop_back - It allows LiveRangeEdit users to drop new registers. 166309124Sdim /// The context is when an original def instruction of a register is 167309124Sdim /// dead after rematerialization, we still want to keep it for following 168309124Sdim /// rematerializations. We save the def instruction in DeadRemats, 169309124Sdim /// and replace the original dst register with a new dummy register so 170309124Sdim /// the live range of original dst register can be shrinked normally. 171309124Sdim /// We don't want to allocate phys register for the dummy register, so 172309124Sdim /// we want to drop it from the NewRegs set. 173309124Sdim void pop_back() { NewRegs.pop_back(); } 174309124Sdim 175261991Sdim ArrayRef<unsigned> regs() const { 176239462Sdim return makeArrayRef(NewRegs).slice(FirstNew); 177234285Sdim } 178234285Sdim 179234285Sdim /// createFrom - Create a new virtual register based on OldReg. 180261991Sdim unsigned createFrom(unsigned OldReg); 181234285Sdim 182234285Sdim /// create - Create a new register with the same class and original slot as 183234285Sdim /// parent. 184261991Sdim LiveInterval &createEmptyInterval() { 185341825Sdim return createEmptyIntervalFrom(getReg(), true); 186261991Sdim } 187261991Sdim 188321369Sdim unsigned create() { return createFrom(getReg()); } 189234285Sdim 190234285Sdim /// anyRematerializable - Return true if any parent values may be 191234285Sdim /// rematerializable. 192234285Sdim /// This function must be called before any rematerialization is attempted. 193321369Sdim bool anyRematerializable(AliasAnalysis *); 194234285Sdim 195234285Sdim /// checkRematerializable - Manually add VNI to the list of rematerializable 196234285Sdim /// values if DefMI may be rematerializable. 197234285Sdim bool checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI, 198321369Sdim AliasAnalysis *); 199234285Sdim 200234285Sdim /// Remat - Information needed to rematerialize at a specific location. 201234285Sdim struct Remat { 202321369Sdim VNInfo *ParentVNI; // parent_'s value at the remat location. 203321369Sdim MachineInstr *OrigMI = nullptr; // Instruction defining OrigVNI. It contains 204321369Sdim // the real expr for remat. 205321369Sdim 206321369Sdim explicit Remat(VNInfo *ParentVNI) : ParentVNI(ParentVNI) {} 207234285Sdim }; 208234285Sdim 209234285Sdim /// canRematerializeAt - Determine if ParentVNI can be rematerialized at 210234285Sdim /// UseIdx. It is assumed that parent_.getVNINfoAt(UseIdx) == ParentVNI. 211234285Sdim /// When cheapAsAMove is set, only cheap remats are allowed. 212309124Sdim bool canRematerializeAt(Remat &RM, VNInfo *OrigVNI, SlotIndex UseIdx, 213234285Sdim bool cheapAsAMove); 214234285Sdim 215234285Sdim /// rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an 216234285Sdim /// instruction into MBB before MI. The new instruction is mapped, but 217234285Sdim /// liveness is not updated. 218234285Sdim /// Return the SlotIndex of the new instruction. 219234285Sdim SlotIndex rematerializeAt(MachineBasicBlock &MBB, 220321369Sdim MachineBasicBlock::iterator MI, unsigned DestReg, 221321369Sdim const Remat &RM, const TargetRegisterInfo &, 222234285Sdim bool Late = false); 223234285Sdim 224234285Sdim /// markRematerialized - explicitly mark a value as rematerialized after doing 225234285Sdim /// it manually. 226234285Sdim void markRematerialized(const VNInfo *ParentVNI) { 227239462Sdim Rematted.insert(ParentVNI); 228234285Sdim } 229234285Sdim 230234285Sdim /// didRematerialize - Return true if ParentVNI was rematerialized anywhere. 231234285Sdim bool didRematerialize(const VNInfo *ParentVNI) const { 232239462Sdim return Rematted.count(ParentVNI); 233234285Sdim } 234234285Sdim 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. 251321369Sdim void calculateRegClassAndHint(MachineFunction &, const MachineLoopInfo &, 252321369Sdim const MachineBlockFrequencyInfo &); 253234285Sdim}; 254234285Sdim 255321369Sdim} // end namespace llvm 256234285Sdim 257321369Sdim#endif // LLVM_CODEGEN_LIVERANGEEDIT_H 258