Go to the documentation of this file.
49 #define DEBUG_TYPE "phi-node-elimination"
54 "during PHI elimination"));
63 cl::desc(
"Do not use an early exit if isLiveOutPastPHIs returns true."));
107 using BBVRegPair = std::pair<unsigned, Register>;
110 VRegPHIUse VRegPHIUseCount;
116 using LoweredPHIMap =
118 LoweredPHIMap LoweredPHIs;
123 STATISTIC(NumLowered,
"Number of phis lowered");
124 STATISTIC(NumCriticalEdgesSplit,
"Number of critical edges split");
125 STATISTIC(NumReused,
"Number of reused lowered phis");
132 "Eliminate PHI nodes for register allocation",
138 void PHIElimination::getAnalysisUsage(
AnalysisUsage &AU)
const {
150 LV = getAnalysisIfAvailable<LiveVariables>();
151 LIS = getAnalysisIfAvailable<LiveIntervals>();
153 bool Changed =
false;
159 std::vector<SparseBitVector<>> LiveInSets;
161 LiveInSets.resize(MF.
size());
172 while (AliveBlockItr != EndItr) {
173 unsigned BlockNum = *(AliveBlockItr++);
174 LiveInSets[BlockNum].set(
Index);
179 if (
VI.Kills.size() > 1 ||
180 (!
VI.Kills.empty() &&
VI.Kills.front()->getParent() != DefMBB))
181 for (
auto *
MI :
VI.Kills)
182 LiveInSets[
MI->getParent()->getNumber()].set(
Index);
188 Changed |= SplitPHIEdges(MF,
MBB, MLI, (LV ? &LiveInSets :
nullptr));
199 Changed |= EliminatePHINodes(MF,
MBB);
206 LIS->RemoveMachineInstrFromMaps(*
DefMI);
212 for (
auto &
I : LoweredPHIs) {
214 LIS->RemoveMachineInstrFromMaps(*
I.first);
215 MF.DeleteMachineInstr(
I.first);
220 if (
auto *MDT = getAnalysisIfAvailable<MachineDominatorTree>())
221 MDT->getBase().recalculate(MF);
225 VRegPHIUseCount.clear();
244 LowerPHINode(
MBB, LastPHIIt);
254 if (!DI.isImplicitDef())
286 unsigned IncomingReg = 0;
287 bool reusedIncoming =
false;
298 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
302 unsigned &
entry = LoweredPHIs[MPhi];
306 reusedIncoming =
true;
316 IncomingReg, DestReg);
325 LV->setPHIJoin(IncomingReg);
328 bool IsPHICopyAfterOldKill =
false;
330 if (reusedIncoming && (OldKill =
VI.findKill(&
MBB))) {
342 IsPHICopyAfterOldKill =
true;
351 if (IsPHICopyAfterOldKill) {
353 LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
362 if (!OldKill || IsPHICopyAfterOldKill)
363 LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
369 LV->removeVirtualRegistersKilled(*MPhi);
373 LV->addVirtualRegisterDead(DestReg, *PHICopy);
374 LV->removeVirtualRegisterDead(DestReg, *MPhi);
380 SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
386 LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
390 LIS->getVNInfoAllocator());
391 IncomingLI.
addSegment(LiveInterval::Segment(MBBStartIndex,
397 assert(!DestLI.
empty() &&
"PHIs should have nonempty LiveIntervals.");
403 assert(OrigDestVNI &&
"PHI destination should be live at block entry.");
406 LIS->getVNInfoAllocator());
413 assert(DestVNI &&
"PHI destination should be live at its definition.");
426 for (
int i = NumSrcs - 1;
i >= 0; --
i) {
432 "Machine PHI Operands must all be virtual registers!");
441 if (!MBBsInsertedInto.
insert(&opBlock).second)
445 if (SrcRegDef &&
TII->isUnspillableTerminator(SrcRegDef)) {
448 "Expected operand 0 to be a reg def!");
452 "Expected a single use from UnspillableTerminator");
464 if (!reusedIncoming && IncomingReg) {
470 TII->get(TargetOpcode::IMPLICIT_DEF),
476 ImpDefs.insert(
DefMI);
480 SrcReg, SrcSubReg, IncomingReg);
487 if (LV && !SrcUndef &&
488 !VRegPHIUseCount[BBVRegPair(opBlock.
getNumber(), SrcReg)] &&
489 !LV->isLiveOut(SrcReg, opBlock)) {
510 if (
Term->readsRegister(SrcReg))
514 if (KillInst == opBlock.
end()) {
517 if (reusedIncoming || !IncomingReg) {
519 KillInst = FirstTerm;
520 while (KillInst != opBlock.
begin()) {
522 if (KillInst->isDebugInstr())
524 if (KillInst->readsRegister(SrcReg))
529 KillInst = NewSrcInstr;
532 assert(KillInst->readsRegister(SrcReg) &&
"Cannot find kill instruction");
535 LV->addVirtualRegisterKilled(SrcReg, *KillInst);
538 unsigned opBlockNum = opBlock.
getNumber();
539 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
544 LIS->InsertMachineInstrInMaps(*NewSrcInstr);
545 LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
549 !VRegPHIUseCount[BBVRegPair(opBlock.
getNumber(), SrcReg)]) {
554 SlotIndex startIdx = LIS->getMBBStartIdx(Succ);
558 if (VNI && VNI->
def != startIdx) {
569 if (
Term->readsRegister(SrcReg))
573 if (KillInst == opBlock.
end()) {
576 if (reusedIncoming || !IncomingReg) {
578 KillInst = FirstTerm;
579 while (KillInst != opBlock.
begin()) {
581 if (KillInst->isDebugInstr())
583 if (KillInst->readsRegister(SrcReg))
588 KillInst = std::prev(InsertPos);
591 assert(KillInst->readsRegister(SrcReg) &&
592 "Cannot find kill instruction");
594 SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
596 LIS->getMBBEndIdx(&opBlock));
603 if (reusedIncoming || !IncomingReg) {
605 LIS->RemoveMachineInstrFromMaps(*MPhi);
615 for (
const auto &
MBB : MF)
616 for (
const auto &BBI :
MBB) {
619 for (
unsigned i = 1,
e = BBI.getNumOperands();
i !=
e;
i += 2)
620 ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(
i+1).getMBB()->getNumber(),
621 BBI.getOperand(
i).getReg())];
633 bool IsLoopHeader = CurLoop && &
MBB == CurLoop->
getHeader();
635 bool Changed =
false;
637 BBI != BBE && BBI->isPHI(); ++BBI) {
638 for (
unsigned i = 1,
e = BBI->getNumOperands();
i !=
e;
i += 2) {
659 bool ShouldSplit = isLiveOutPastPHIs(
Reg, PreMBB);
676 ShouldSplit = ShouldSplit && !isLiveIn(
Reg, &
MBB);
679 if (!ShouldSplit && CurLoop != PreLoop) {
681 dbgs() <<
"Split wouldn't help, maybe avoid loop copies?\n";
683 dbgs() <<
"PreLoop: " << *PreLoop;
685 dbgs() <<
"CurLoop: " << *CurLoop;
691 ShouldSplit = PreLoop && !PreLoop->
contains(CurLoop);
700 ++NumCriticalEdgesSplit;
708 "isLiveIn() requires either LiveVariables or LiveIntervals");
710 return LIS->isLiveInToMBB(LIS->getInterval(
Reg),
MBB);
712 return LV->isLiveIn(
Reg, *
MBB);
715 bool PHIElimination::isLiveOutPastPHIs(
Register Reg,
718 "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
727 if (LI.
liveAt(LIS->getMBBStartIdx(
SI)))
731 return LV->isLiveOut(
Reg, *
MBB);
unsigned succ_size() const
bool isImplicitDef() const
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
virtual const TargetInstrInfo * getInstrInfo() const
char & PHIEliminationID
PHIElimination - This pass eliminates machine instruction PHI nodes by inserting copy instructions.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
static bool allPhiOperandsUndefined(const MachineInstr &MPhi, const MachineRegisterInfo &MRI)
Return true if all sources of the phi node are implicit_def's, or undef's.
SlotIndex def
The index of the defining instruction.
static bool isImplicitlyDefined(unsigned VirtReg, const MachineRegisterInfo &MRI)
Return true if all defs of VirtReg are implicit-defs.
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static cl::opt< bool > DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), cl::Hidden, cl::desc("Disable critical edge splitting " "during PHI elimination"))
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
TargetInstrInfo - Interface to description of machine instruction set.
bool liveAt(SlotIndex index) const
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
VarInfo - This represents the regions where a virtual register is live in the program.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const MachineOperand & getOperand(unsigned i) const
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
void DeleteMachineInstr(MachineInstr *MI)
DeleteMachineInstr - Delete the given MachineInstr.
Represent the analysis usage information of a pass.
void initializePHIEliminationPass(PassRegistry &)
const HexagonInstrInfo * TII
MachineOperand class - Representation of each machine instruction operand.
STATISTIC(NumFunctions, "Total number of functions")
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
LiveInterval - This class represents the liveness of a register, or stack slot.
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
SlotIndex - An opaque wrapper around machine indexes.
bool use_empty(Register RegNo) const
use_empty - Return true if there are no instructions using the specified register.
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Eliminate PHI nodes for register allocation
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE, "Eliminate PHI nodes for register allocation", false, false) INITIALIZE_PASS_END(PHIElimination
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Representation of each machine instruction.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
iterator_range< typename GraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
iterator_range< def_instr_iterator > def_instructions(Register Reg) const
initializer< Ty > init(const Ty &Val)
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Register getReg() const
getReg - Returns the register number.
should just be implemented with a CLZ instruction Since there are other e that share this it would be best to implement this in a target independent as zero is the default value for the binary encoder e add r0 add r5 Register operands should be distinct That when the encoding does not require two syntactical operands to refer to the same register
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
MachineBasicBlock * getMBB() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
SparseBitVectorIterator iterator
iterator_range< succ_iterator > successors()
bool isEHPad() const
Returns true if the block is a landing pad.
MachineBasicBlock::iterator findPHICopyInsertPoint(MachineBasicBlock *MBB, MachineBasicBlock *SuccMBB, unsigned SrcReg)
findPHICopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg when following the CFG...
const MachineBasicBlock * getParent() const
this could be done in SelectionDAGISel along with other special for
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
unsigned getSubReg() const
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
BlockT * getHeader() const
VNInfo - Value Number Information.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
void setReg(Register Reg)
Change the register this operand corresponds to.
MachineInstrBuilder MachineInstrBuilder & DefMI
unsigned getNumOperands() const
Retuns the total number of operands.
static cl::opt< bool > NoPhiElimLiveOutEarlyExit("no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden, cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."))
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
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.
MachineBasicBlock * SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P, std::vector< SparseBitVector<>> *LiveInSets=nullptr)
Split the critical edge from this block to the given successor block, and return the newly created bl...
print Instructions which execute on loop entry
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.