Go to the documentation of this file.
25 #define DEBUG_TYPE "regalloc"
27 STATISTIC(NumDCEDeleted,
"Number of instructions deleted by DCE");
28 STATISTIC(NumDCEFoldedLoads,
"Number of single use loads folded after DCE");
29 STATISTIC(NumFracRanges,
"Number of live ranges fractured by DCE");
31 void LiveRangeEdit::Delegate::anchor() { }
34 bool createSubRanges) {
42 if (createSubRanges) {
74 ScannedRemattable =
true;
77 Remattable.insert(VNI);
95 ScannedRemattable =
true;
99 if (!ScannedRemattable)
101 return !Remattable.empty();
112 if (!MO.isReg() || !MO.getReg() || !MO.readsReg())
138 if (MO.getSubReg()) {
142 if ((SR.LaneMask & LM).none())
144 if (!SR.liveAt(UseIdx))
158 assert(ScannedRemattable &&
"Call anyRematerializable first");
161 if (!Remattable.count(OrigVNI))
166 assert(
RM.OrigMI &&
"No defining instruction for remattable value");
186 assert(
RM.OrigMI &&
"Invalid remat");
191 (*--
MI).getOperand(0).setIsDead(
false);
192 Rematted.insert(
RM.ParentVNI);
211 if (!
MI->canFoldAsLoad())
214 }
else if (!MO.isUndef()) {
234 bool SawStore =
true;
239 <<
" into single use: " << *
UseMI);
270 if ((
S.LaneMask & LaneMask).any() &&
S.Query(Idx).isKill())
277 void LiveRangeEdit::eliminateDeadDef(
MachineInstr *
MI, ToShrinkSet &ToShrink,
279 assert(
MI->allDefsAreDead() &&
"Def isn't really dead");
283 if (
MI->isBundled()) {
287 if (
MI->isInlineAsm()) {
293 bool SawStore =
false;
294 if (!
MI->isSafeToMove(
nullptr, SawStore)) {
303 bool ReadsPhysRegs =
false;
304 bool isOrigDef =
false;
309 if (VRM &&
MI->getOperand(0).isReg() &&
MI->getOperand(0).isDef() &&
310 MI->getDesc().getNumDefs() == 1) {
311 Dest =
MI->getOperand(0).getReg();
323 bool HasLiveVRegUses =
false;
333 ReadsPhysRegs =
true;
344 if ((
MI->readsVirtualRegister(
Reg) && (
MI->isCopy() || MO.
isDef())) ||
346 ToShrink.insert(&LI);
348 HasLiveVRegUses =
true;
356 RegsToErase.push_back(
Reg);
368 MI->setDesc(TII.
get(TargetOpcode::KILL));
370 for (
unsigned i =
MI->getNumOperands();
i; --
i) {
374 MI->removeOperand(
i-1);
386 if (isOrigDef && DeadRemats && !HasLiveVRegUses &&
388 LiveInterval &NewLI = createEmptyIntervalFrom(Dest,
false);
392 DeadRemats->insert(
MI);
394 MI->substituteRegister(Dest, NewLI.
reg(), 0,
TRI);
395 MI->getOperand(0).setIsDead(
true);
400 MI->eraseFromParent();
407 for (
unsigned i = 0,
e = RegsToErase.size();
i !=
e; ++
i) {
423 while (!
Dead.empty())
424 eliminateDeadDef(
Dead.pop_back_val(), ToShrink,
AA);
426 if (ToShrink.
empty())
431 if (foldAsLoad(LI,
Dead))
433 unsigned VReg = LI->
reg();
450 if (!SplitLIs.empty())
458 if (Original != VReg && Original != 0)
469 LiveRangeEdit::MRI_NoteNewVirtualRegister(
Register VReg) {
473 NewRegs.push_back(VReg);
478 for (
unsigned I = 0, Size =
size();
I < Size; ++
I) {
Remat - Information needed to rematerialize at a specific location.
bool checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI, AAResults *)
checkRematerializable - Manually add VNI to the list of rematerializable values if DefMI may be remat...
bool addRegisterDead(Register Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI defined a register without a use.
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder & UseMI
SlotIndexes * getSlotIndexes() const
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
void calculateRegClassAndHint(MachineFunction &, VirtRegAuxInfo &)
calculateRegClassAndHint - Recompute register class and hint for each new register.
SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)
Creates a new empty subregister live range.
bool isSafeToMove(AAResults *AA, bool &SawStore) const
Return true if it is safe to move this instruction.
bool recomputeRegClass(Register Reg)
recomputeRegClass - Try to find a legal super-class of Reg's register class that still satisfies the ...
virtual bool LRE_CanEraseVirtReg(Register)
Called when a virtual register is no longer used.
Register createFrom(Register OldReg)
createFrom - Create a new virtual register based on OldReg.
bool isSpillable() const
isSpillable - Can this interval be spilled?
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.
Register getOriginal(Register VirtReg) const
getOriginal - Return the original virtual register that VirtReg descends from through splitting.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
Reg
All possible values of the reg field in the ModR/M byte.
const TargetRegisterInfo * getTargetRegisterInfo() const
SlotIndex def
The index of the defining instruction.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
void moveCallSiteInfo(const MachineInstr *Old, const MachineInstr *New)
Move the call site info from Old to \New call site info.
void removeInterval(Register Reg)
Interval removal.
void eliminateDeadDefs(SmallVectorImpl< MachineInstr * > &Dead, ArrayRef< Register > RegsBeingSpilled=None, AAResults *AA=nullptr)
eliminateDeadDefs - Try to delete machine instructions that are now dead (allDefsAreDead returns true...
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
virtual void LRE_WillEraseInstruction(MachineInstr *MI)
Called immediately before erasing a dead machine instruction.
void calculateSpillWeightAndHint(LiveInterval &LI)
(re)compute li's spill weight and allocation hint.
unsigned const TargetRegisterInfo * TRI
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Register get(unsigned idx) const
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
bool anyRematerializable(AAResults *)
anyRematerializable - Return true if any parent values may be rematerializable.
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
iterator_range< reg_nodbg_iterator > reg_nodbg_operands(Register Reg) const
MachineOperand class - Representation of each machine instruction operand.
bool shouldUpdateCallSiteInfo() const
Return true if copying, moving, or erasing this instruction requires updating Call Site Info (see cop...
STATISTIC(NumFunctions, "Total number of functions")
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
void eraseVirtReg(Register Reg)
eraseVirtReg - Notify the delegate that Reg is no longer in use, and try to erase it from LIS.
LiveInterval - This class represents the liveness of a register, or stack slot.
SlotIndex - An opaque wrapper around machine indexes.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool empty() const
Determine if the SetVector is empty or not.
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
void setIsSplitFromReg(Register virtReg, Register SReg)
records virtReg is a split live interval from SReg.
void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void RenumberValues()
RenumberValues - Renumber all values in order of appearance and remove unused values.
SlotIndex ReplaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Representation of each machine instruction.
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
Allocate memory in an ever growing pool, as if by bump-pointer.
void pop_back()
pop_back - It allows LiveRangeEdit users to drop new registers.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
virtual bool isAsCheapAsAMove(const MachineInstr &MI) const
Return true if the instruction is as cheap as a move instruction.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.
bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses.
bool canRematerializeAt(Remat &RM, VNInfo *OrigVNI, SlotIndex UseIdx, bool cheapAsAMove)
canRematerializeAt - Determine if ParentVNI can be rematerialized at UseIdx.
Register getReg() const
getReg - Returns the register number.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
LiveInterval & getInterval(Register Reg)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
SlotIndex rematerializeAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned DestReg, const Remat &RM, const TargetRegisterInfo &, bool Late=false)
rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an instruction into MBB before...
constexpr bool none() const
bool hasOneNonDBGUse(Register RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register.
virtual void reMaterialize(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register DestReg, unsigned SubIdx, const MachineInstr &Orig, const TargetRegisterInfo &TRI) const
Re-issue the specified 'original' instruction at the specific location targeting a new destination re...
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
LiveInterval & createEmptyInterval(Register Reg)
Interval creation.
A live range for subregisters.
Wrapper class representing virtual and physical registers.
unsigned getSubReg() const
bool isTriviallyReMaterializable(const MachineInstr &MI, AAResults *AA=nullptr) const
Return true if the instruction is trivially rematerializable, meaning it has no side effects and requ...
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
bool allUsesAvailableAt(const MachineInstr *OrigMI, SlotIndex OrigIdx, SlotIndex UseIdx) const
allUsesAvailableAt - Return true if all registers used by OrigMI at OrigIdx are also available with t...
const LiveInterval & getParent() const
virtual bool isIgnorableUse(const MachineOperand &MO) const
Given MO is a PhysReg use return if it can be ignored for the purpose of instruction rematerializatio...
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
virtual void LRE_DidCloneVirtReg(Register New, Register Old)
Called after cloning a virtual register.
VNInfo - Value Number Information.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
MachineInstr * foldMemoryOperand(MachineInstr &MI, ArrayRef< unsigned > Ops, int FI, LiveIntervals *LIS=nullptr, VirtRegMap *VRM=nullptr) const
Attempt to fold a load or store of the specified stack slot into the specified machine instruction fo...
void RemoveMachineInstrFromMaps(MachineInstr &MI)
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
MachineInstrBuilder MachineInstrBuilder & DefMI
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
bool hasInterval(Register Reg) const
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions.
virtual void LRE_WillShrinkVirtReg(Register)
Called before shrinking the live range of a virtual register.
A vector that has set insertion semantics.
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.
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
LLVM_NODISCARD T pop_back_val()
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
iterator_range< mop_iterator > operands()
bool isKill() const
Return true if the live-in value is killed by this instruction.
VNInfo::Allocator & getVNInfoAllocator()
iterator_range< subrange_iterator > subranges()