25#define DEBUG_TYPE "regalloc"
27STATISTIC(NumDCEDeleted,
"Number of instructions deleted by DCE");
28STATISTIC(NumDCEFoldedLoads,
"Number of single use loads folded after DCE");
29STATISTIC(NumFracRanges,
"Number of live ranges fractured by DCE");
30STATISTIC(NumReMaterialization,
"Number of instructions rematerialized");
32void LiveRangeEdit::Delegate::anchor() { }
34LiveInterval &LiveRangeEdit::createEmptyIntervalFrom(
Register OldReg,
35 bool createSubRanges) {
36 Register VReg = MRI.cloneVirtualRegister(OldReg);
38 VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
40 LiveInterval &LI = LIS.createEmptyInterval(VReg);
41 if (Parent && !Parent->isSpillable())
43 if (createSubRanges) {
47 LiveInterval &OldLI = LIS.getInterval(OldReg);
49 for (LiveInterval::SubRange &S : OldLI.
subranges())
56 Register VReg = MRI.cloneVirtualRegister(OldReg);
58 VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
66 if (Parent && !Parent->isSpillable())
67 LIS.getInterval(VReg).markNotSpillable();
71void LiveRangeEdit::scanRemattable() {
84 Remattable.insert(OrigVNI);
86 ScannedRemattable =
true;
90 if (!ScannedRemattable)
92 return !Remattable.empty();
97 assert(ScannedRemattable &&
"Call anyRematerializable first");
100 if (!Remattable.count(OrigVNI))
104 assert(RM.OrigMI &&
"No defining instruction for remattable value");
117 bool Late,
unsigned SubIdx,
119 assert(RM.OrigMI &&
"Invalid remat");
120 TII.reMaterialize(
MBB,
MI, DestReg, SubIdx, *RM.OrigMI, tri);
124 (*--
MI).clearRegisterDeads(DestReg);
125 Rematted.insert(RM.ParentVNI);
126 ++NumReMaterialization;
128 bool EarlyClobber =
MI->getOperand(0).isEarlyClobber();
130 return LIS.ReplaceMachineInstrInMaps(*ReplaceIndexMI, *
MI)
131 .getRegSlot(EarlyClobber);
132 return LIS.getSlotIndexes()->insertMachineInstrInMaps(*
MI, Late).getRegSlot(
137 if (TheDelegate && TheDelegate->LRE_CanEraseVirtReg(Reg))
138 LIS.removeInterval(Reg);
151 if (!
MI->canFoldAsLoad())
154 }
else if (!MO.isUndef()) {
169 DefMI, LIS.getInstructionIndex(*
UseMI), LIS, MRI, TII))
174 bool SawStore =
true;
179 <<
" into single use: " << *
UseMI);
181 SmallVector<unsigned, 8>
Ops;
185 MachineInstr *FoldMI = TII.foldMemoryOperand(*
UseMI,
Ops, *
DefMI, &LIS);
189 LIS.ReplaceMachineInstrInMaps(*
UseMI, *FoldMI);
200bool LiveRangeEdit::useIsKill(
const LiveInterval &LI,
201 const MachineOperand &MO)
const {
203 SlotIndex Idx = LIS.getInstructionIndex(
MI).getRegSlot();
206 const TargetRegisterInfo &
TRI = *MRI.getTargetRegisterInfo();
208 LaneBitmask LaneMask =
TRI.getSubRegIndexLaneMask(
SubReg);
209 for (
const LiveInterval::SubRange &S : LI.
subranges()) {
210 if ((S.LaneMask & LaneMask).any() && S.Query(Idx).isKill())
217void LiveRangeEdit::eliminateDeadDef(MachineInstr *
MI, ToShrinkSet &ToShrink) {
218 assert(
MI->allDefsAreDead() &&
"Def isn't really dead");
219 SlotIndex Idx = LIS.getInstructionIndex(*MI).
getRegSlot();
222 if (
MI->isBundled()) {
224 LLVM_DEBUG(
dbgs() <<
"Won't delete dead bundled inst: " << Idx <<
'\t'
230 if (
MI->isInlineAsm()) {
236 bool SawStore =
false;
237 if (!
MI->isSafeToMove(SawStore)) {
246 bool ReadsPhysRegs =
false;
247 bool isOrigDef =
false;
253 if (VRM &&
MI->getOperand(0).isReg() &&
MI->getOperand(0).isDef() &&
254 MI->getDesc().getNumDefs() == 1) {
255 Dest =
MI->getOperand(0).getReg();
256 DestSubReg =
MI->getOperand(0).getSubReg();
257 Register Original = VRM->getOriginal(Dest);
258 LiveInterval &OrigLI = LIS.getInterval(Original);
268 bool HasLiveVRegUses =
false;
271 for (
const MachineOperand &MO :
MI->operands()) {
278 ReadsPhysRegs =
true;
283 LiveInterval &LI = LIS.getInterval(
Reg);
289 if ((
MI->readsVirtualRegister(
Reg) &&
290 (MO.
isDef() || TII.isCopyInstr(*
MI))) ||
291 (MO.
readsReg() && (MRI.hasOneNonDBGUse(
Reg) || useIsKill(LI, MO))))
292 ToShrink.insert(&LI);
294 HasLiveVRegUses =
true;
299 TheDelegate->LRE_WillShrinkVirtReg(LI.
reg());
300 LIS.removeVRegDefAt(LI, Idx);
314 MI->setDesc(TII.get(TargetOpcode::KILL));
316 for (
unsigned i =
MI->getNumOperands(); i; --i) {
317 const MachineOperand &MO =
MI->getOperand(i-1);
320 MI->removeOperand(i-1);
322 MI->dropMemRefs(*
MI->getMF());
333 if (isOrigDef && DeadRemats && !HasLiveVRegUses &&
334 TII.isReMaterializable(*
MI)) {
335 LiveInterval &NewLI = createEmptyIntervalFrom(Dest,
false);
341 const TargetRegisterInfo *
TRI = MRI.getTargetRegisterInfo();
343 Alloc,
TRI->getSubRegIndexLaneMask(DestSubReg));
345 SR->getNextValue(Idx,
Alloc)));
349 DeadRemats->insert(
MI);
350 const TargetRegisterInfo &
TRI = *MRI.getTargetRegisterInfo();
351 MI->substituteRegister(Dest, NewLI.
reg(), 0,
TRI);
355 TheDelegate->LRE_WillEraseInstruction(
MI);
356 LIS.RemoveMachineInstrFromMaps(*
MI);
357 MI->eraseFromParent();
365 if (LIS.hasInterval(
Reg) && MRI.reg_nodbg_empty(
Reg)) {
366 ToShrink.remove(&LIS.getInterval(
Reg));
374 ToShrinkSet ToShrink;
378 while (!Dead.empty())
379 eliminateDeadDef(Dead.pop_back_val(), ToShrink);
381 if (ToShrink.
empty())
386 if (foldAsLoad(LI, Dead))
390 TheDelegate->LRE_WillShrinkVirtReg(VReg);
391 if (!LIS.shrinkToUses(LI, &Dead))
404 LIS.splitSeparateComponents(*LI, SplitLIs);
405 if (!SplitLIs.
empty())
413 if (Original != VReg && Original != 0)
414 VRM->setIsSplitFromReg(SplitLI->reg(), Original);
416 TheDelegate->LRE_DidCloneVirtReg(SplitLI->reg(), VReg);
424LiveRangeEdit::MRI_NoteNewVirtualRegister(
Register VReg) {
428 NewRegs.push_back(VReg);
435 if (MRI.recomputeRegClass(LI.
reg()))
439 <<
TRI->getRegClassName(MRI.getRegClass(LI.
reg())) <<
'\n';
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
const HexagonInstrInfo * TII
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Register const TargetRegisterInfo * TRI
Promote Memory to Register
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LiveInterval - This class represents the liveness of a register, or stack slot.
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
iterator_range< subrange_iterator > subranges()
SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)
Creates a new empty subregister live range.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
LiveInterval & getInterval(Register Reg)
bool isKill() const
Return true if the live-in value is killed by this instruction.
void eraseVirtReg(Register Reg)
eraseVirtReg - Notify the delegate that Reg is no longer in use, and try to erase it from LIS.
bool canRematerializeAt(Remat &RM, VNInfo *OrigVNI, SlotIndex UseIdx)
canRematerializeAt - Determine if ParentVNI can be rematerialized at UseIdx.
Register get(unsigned idx) const
Register createFrom(Register OldReg)
createFrom - Create a new virtual register based on OldReg.
void calculateRegClassAndHint(MachineFunction &, VirtRegAuxInfo &)
calculateRegClassAndHint - Recompute register class and hint for each new register.
const LiveInterval & getParent() const
SlotIndex rematerializeAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register DestReg, const Remat &RM, const TargetRegisterInfo &, bool Late=false, unsigned SubIdx=0, MachineInstr *ReplaceIndexMI=nullptr)
rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an instruction into MBB before...
void eliminateDeadDefs(SmallVectorImpl< MachineInstr * > &Dead, ArrayRef< Register > RegsBeingSpilled={})
eliminateDeadDefs - Try to delete machine instructions that are now dead (allDefsAreDead returns true...
void pop_back()
pop_back - It allows LiveRangeEdit users to drop new registers.
bool anyRematerializable()
anyRematerializable - Return true if any parent values may be rematerializable.
LLVM_ABI iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
LLVM_ABI void RenumberValues()
RenumberValues - Renumber all values in order of appearance and remove unused values.
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
MachineInstrBundleIterator< MachineInstr > iterator
void moveAdditionalCallInfo(const MachineInstr *Old, const MachineInstr *New)
Move the call site info from Old to \New call site info.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Representation of each machine instruction.
LLVM_ABI std::pair< bool, bool > readsWritesVirtualRegister(Register Reg, SmallVectorImpl< unsigned > *Ops=nullptr) const
Return a pair of bools (reads, writes) indicating if this instruction reads or writes Reg.
LLVM_ABI bool isSafeToMove(bool &SawStore) const
Return true if it is safe to move this instruction.
LLVM_ABI const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
LLVM_ABI void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
LLVM_ABI bool shouldUpdateAdditionalCallInfo() const
Return true if copying, moving, or erasing this instruction requires updating additional call info (s...
LLVM_ABI bool addRegisterDead(Register Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI defined a register without a use.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Register getReg() const
getReg - Returns the register number.
Wrapper class representing virtual and physical registers.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
bool empty() const
Determine if the SetVector is empty or not.
value_type pop_back_val()
SlotIndex - An opaque wrapper around machine indexes.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
VNInfo - Value Number Information.
BumpPtrAllocator Allocator
SlotIndex def
The index of the defining instruction.
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.
static bool allUsesAvailableAt(const MachineInstr *MI, SlotIndex UseIdx, const LiveIntervals &LIS, const MachineRegisterInfo &MRI, const TargetInstrInfo &TII)
void calculateSpillWeightAndHint(LiveInterval &LI)
(re)compute li's spill weight and allocation hint.
Register getOriginal(Register VirtReg) const
getOriginal - Return the original virtual register that VirtReg descends from through splitting.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Remat - Information needed to rematerialize at a specific location.