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();
106 bool LiveRangeEdit::allUsesAvailableAt(
const MachineInstr *OrigMI,
142 assert(ScannedRemattable &&
"Call anyRematerializable first");
145 if (!Remattable.count(OrigVNI))
150 assert(
RM.OrigMI &&
"No defining instruction for remattable value");
158 if (!allUsesAvailableAt(
RM.OrigMI, DefIdx, UseIdx))
170 assert(
RM.OrigMI &&
"Invalid remat");
175 (*--
MI).getOperand(0).setIsDead(
false);
176 Rematted.insert(
RM.ParentVNI);
195 if (!
MI->canFoldAsLoad())
218 bool SawStore =
true;
223 <<
" into single use: " << *
UseMI);
254 if ((
S.LaneMask & LaneMask).any() &&
S.Query(Idx).isKill())
261 void LiveRangeEdit::eliminateDeadDef(
MachineInstr *
MI, ToShrinkSet &ToShrink,
263 assert(
MI->allDefsAreDead() &&
"Def isn't really dead");
267 if (
MI->isBundled()) {
271 if (
MI->isInlineAsm()) {
277 bool SawStore =
false;
278 if (!
MI->isSafeToMove(
nullptr, SawStore)) {
287 bool ReadsPhysRegs =
false;
288 bool isOrigDef =
false;
293 if (VRM &&
MI->getOperand(0).isReg() &&
MI->getOperand(0).isDef() &&
294 MI->getDesc().getNumDefs() == 1) {
295 Dest =
MI->getOperand(0).getReg();
309 MOE =
MI->operands_end(); MOI != MOE; ++MOI) {
316 ReadsPhysRegs =
true;
317 else if (MOI->isDef())
327 if ((
MI->readsVirtualRegister(
Reg) && (
MI->isCopy() || MOI->isDef())) ||
329 ToShrink.insert(&LI);
337 RegsToErase.push_back(
Reg);
349 MI->setDesc(TII.
get(TargetOpcode::KILL));
351 for (
unsigned i =
MI->getNumOperands();
i; --
i) {
355 MI->RemoveOperand(
i-1);
365 LiveInterval &NewLI = createEmptyIntervalFrom(Dest,
false);
369 DeadRemats->insert(
MI);
371 MI->substituteRegister(Dest, NewLI.
reg(), 0,
TRI);
372 MI->getOperand(0).setIsDead(
true);
377 MI->eraseFromParent();
384 for (
unsigned i = 0,
e = RegsToErase.size();
i !=
e; ++
i) {
400 while (!
Dead.empty())
401 eliminateDeadDef(
Dead.pop_back_val(), ToShrink, AA);
403 if (ToShrink.
empty())
409 if (foldAsLoad(LI,
Dead))
411 unsigned VReg = LI->
reg();
421 bool BeingSpilled =
false;
422 for (
unsigned i = 0,
e = RegsBeingSpilled.
size();
i !=
e; ++
i) {
423 if (VReg == RegsBeingSpilled[
i]) {
429 if (BeingSpilled)
continue;
435 if (!SplitLIs.empty())
443 if (Original != VReg && Original != 0)
454 LiveRangeEdit::MRI_NoteNewVirtualRegister(
Register VReg) {
458 NewRegs.push_back(VReg);
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 class represents lattice values for constants.
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.
void pop_back()
Remove the last element of the SetVector.
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.
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.
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.
const MachineOperand & getOperand(unsigned i) const
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.
LiveInterval & getParent() const
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.
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...
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 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
unsigned getNumOperands() const
Retuns the total number of operands.
size_t size() const
size - Get the array size.
const T & back() const
Return the last element of the SetVector.
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.
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
bool isKill() const
Return true if the live-in value is killed by this instruction.
VNInfo::Allocator & getVNInfoAllocator()
iterator_range< subrange_iterator > subranges()