47#define DEBUG_TYPE "phi-node-elimination"
52 "during PHI elimination"));
61 cl::desc(
"Do not use an early exit if isLiveOutPastPHIs returns true."));
105 using BBVRegPair = std::pair<unsigned, Register>;
109 VRegPHIUse VRegPHIUseCount;
115 using LoweredPHIMap =
117 LoweredPHIMap LoweredPHIs;
123STATISTIC(NumCriticalEdgesSplit,
"Number of critical edges split");
126char PHIElimination::ID = 0;
131 "Eliminate PHI nodes for register allocation",
137void PHIElimination::getAnalysisUsage(
AnalysisUsage &AU)
const {
149 LV = getAnalysisIfAvailable<LiveVariables>();
150 LIS = getAnalysisIfAvailable<LiveIntervals>();
152 bool Changed =
false;
158 std::vector<SparseBitVector<>> LiveInSets;
160 LiveInSets.resize(MF.
size());
171 while (AliveBlockItr != EndItr) {
172 unsigned BlockNum = *(AliveBlockItr++);
173 LiveInSets[BlockNum].set(
Index);
178 if (
VI.Kills.size() > 1 ||
179 (!
VI.Kills.empty() &&
VI.Kills.front()->getParent() != DefMBB))
180 for (
auto *
MI :
VI.Kills)
181 LiveInSets[
MI->getParent()->getNumber()].set(
Index);
187 Changed |= SplitPHIEdges(MF,
MBB, MLI, (LV ? &LiveInSets :
nullptr));
198 Changed |= EliminatePHINodes(MF,
MBB);
203 if (
MRI->use_nodbg_empty(DefReg)) {
205 LIS->RemoveMachineInstrFromMaps(*
DefMI);
211 for (
auto &
I : LoweredPHIs) {
213 LIS->RemoveMachineInstrFromMaps(*
I.first);
214 MF.deleteMachineInstr(
I.first);
219 if (
auto *MDT = getAnalysisIfAvailable<MachineDominatorTree>())
220 MDT->getBase().recalculate(MF);
224 VRegPHIUseCount.clear();
226 MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
243 LowerPHINode(
MBB, LastPHIIt);
253 if (!DI.isImplicitDef())
285 unsigned IncomingReg = 0;
286 bool reusedIncoming =
false;
297 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
301 unsigned &entry = LoweredPHIs[MPhi];
305 reusedIncoming =
true;
315 IncomingReg, DestReg);
334 bool IsPHICopyAfterOldKill =
false;
336 if (reusedIncoming && (OldKill =
VI.findKill(&
MBB))) {
348 IsPHICopyAfterOldKill =
true;
357 if (IsPHICopyAfterOldKill) {
359 LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
368 if (!OldKill || IsPHICopyAfterOldKill)
369 LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
375 LV->removeVirtualRegistersKilled(*MPhi);
379 LV->addVirtualRegisterDead(DestReg, *PHICopy);
380 LV->removeVirtualRegisterDead(DestReg, *MPhi);
386 SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
392 LiveInterval &IncomingLI = LIS->getOrCreateEmptyInterval(IncomingReg);
396 LIS->getVNInfoAllocator());
403 assert(!DestLI.
empty() &&
"PHIs should have non-empty LiveIntervals.");
411 for (
auto LR : ToUpdate) {
412 auto DestSegment = LR->find(MBBStartIndex);
413 assert(DestSegment != LR->end() &&
414 "PHI destination must be live in block");
416 if (LR->endIndex().isDead()) {
420 VNInfo *OrigDestVNI = LR->getVNInfoAt(DestSegment->start);
421 assert(OrigDestVNI &&
"PHI destination should be live at block entry.");
422 LR->removeSegment(DestSegment->start, DestSegment->start.getDeadSlot());
423 LR->createDeadDef(NewStart, LIS->getVNInfoAllocator());
424 LR->removeValNo(OrigDestVNI);
431 if (DestSegment->start > NewStart) {
432 VNInfo *VNI = LR->getVNInfoAt(DestSegment->start);
433 assert(VNI &&
"value should be defined for known segment");
436 }
else if (DestSegment->start < NewStart) {
437 assert(DestSegment->start >= MBBStartIndex);
439 LR->removeSegment(DestSegment->start, NewStart);
441 VNInfo *DestVNI = LR->getVNInfoAt(NewStart);
442 assert(DestVNI &&
"PHI destination should be live at its definition.");
443 DestVNI->
def = NewStart;
450 --VRegPHIUseCount[BBVRegPair(
459 for (
int i = NumSrcs - 1; i >= 0; --i) {
465 "Machine PHI Operands must all be virtual registers!");
474 if (!MBBsInsertedInto.
insert(&opBlock).second)
478 if (SrcRegDef &&
TII->isUnspillableTerminator(SrcRegDef)) {
481 "Expected operand 0 to be a reg def!");
485 "Expected a single use from UnspillableTerminator");
506 if (!reusedIncoming && IncomingReg) {
512 TII->get(TargetOpcode::IMPLICIT_DEF),
518 ImpDefs.insert(
DefMI);
522 NewSrcInstr =
TII->createPHISourceCopy(opBlock, InsertPos,
nullptr,
523 SrcReg, SrcSubReg, IncomingReg);
530 if (LV && !SrcUndef &&
531 !VRegPHIUseCount[BBVRegPair(opBlock.
getNumber(), SrcReg)] &&
532 !LV->isLiveOut(SrcReg, opBlock)) {
552 if (
Term->readsRegister(SrcReg))
556 if (KillInst == opBlock.
end()) {
559 if (reusedIncoming || !IncomingReg) {
561 KillInst = InsertPos;
562 while (KillInst != opBlock.
begin()) {
564 if (KillInst->isDebugInstr())
566 if (KillInst->readsRegister(SrcReg))
571 KillInst = NewSrcInstr;
574 assert(KillInst->readsRegister(SrcReg) &&
"Cannot find kill instruction");
577 LV->addVirtualRegisterKilled(SrcReg, *KillInst);
580 unsigned opBlockNum = opBlock.
getNumber();
581 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
586 LIS->InsertMachineInstrInMaps(*NewSrcInstr);
587 LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
591 !VRegPHIUseCount[BBVRegPair(opBlock.
getNumber(), SrcReg)]) {
596 SlotIndex startIdx = LIS->getMBBStartIdx(Succ);
600 if (VNI && VNI->
def != startIdx) {
610 if (
Term->readsRegister(SrcReg))
614 if (KillInst == opBlock.
end()) {
617 if (reusedIncoming || !IncomingReg) {
619 KillInst = InsertPos;
620 while (KillInst != opBlock.
begin()) {
622 if (KillInst->isDebugInstr())
624 if (KillInst->readsRegister(SrcReg))
629 KillInst = std::prev(InsertPos);
632 assert(KillInst->readsRegister(SrcReg) &&
633 "Cannot find kill instruction");
635 SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
637 LIS->getMBBEndIdx(&opBlock));
640 LIS->getMBBEndIdx(&opBlock));
648 if (reusedIncoming || !IncomingReg) {
650 LIS->RemoveMachineInstrFromMaps(*MPhi);
660 for (
const auto &
MBB : MF) {
661 for (
const auto &BBI :
MBB) {
664 for (
unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
665 if (!BBI.getOperand(i).isUndef()) {
666 ++VRegPHIUseCount[BBVRegPair(
667 BBI.getOperand(i + 1).getMBB()->getNumber(),
668 BBI.getOperand(i).getReg())];
683 bool IsLoopHeader = CurLoop && &
MBB == CurLoop->
getHeader();
685 bool Changed =
false;
687 BBI != BBE && BBI->isPHI(); ++BBI) {
688 for (
unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
709 bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
726 ShouldSplit = ShouldSplit && !isLiveIn(Reg, &
MBB);
729 if (!ShouldSplit && CurLoop != PreLoop) {
731 dbgs() <<
"Split wouldn't help, maybe avoid loop copies?\n";
733 dbgs() <<
"PreLoop: " << *PreLoop;
735 dbgs() <<
"CurLoop: " << *CurLoop;
741 ShouldSplit = PreLoop && !PreLoop->
contains(CurLoop);
750 ++NumCriticalEdgesSplit;
758 "isLiveIn() requires either LiveVariables or LiveIntervals");
760 return LIS->isLiveInToMBB(LIS->getInterval(Reg),
MBB);
762 return LV->isLiveIn(Reg, *
MBB);
765bool PHIElimination::isLiveOutPastPHIs(
Register Reg,
768 "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
777 if (LI.
liveAt(LIS->getMBBStartIdx(SI)))
781 return LV->isLiveOut(Reg, *
MBB);
unsigned const MachineRegisterInfo * MRI
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineInstrBuilder MachineInstrBuilder & DefMI
Unify divergent function exit nodes
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
const HexagonInstrInfo * TII
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.
Eliminate PHI nodes for register allocation
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."))
static bool isImplicitlyDefined(unsigned VirtReg, const MachineRegisterInfo &MRI)
Return true if all defs of VirtReg are implicit-defs.
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 cl::opt< bool > SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false), cl::Hidden, cl::desc("Split all critical edges during " "PHI elimination"))
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
This file defines the SmallPtrSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Represent the analysis usage information of a pass.
LiveInterval - This class represents the liveness of a register, or stack slot.
iterator_range< subrange_iterator > subranges()
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
bool liveAt(SlotIndex index) const
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified interval from this live range.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
bool isEHPad() const
Returns true if the block is a landing pad.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
unsigned succ_size() const
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...
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Location of a PHI instruction that is also a debug-info variable value, for the duration of register ...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void deleteMachineInstr(MachineInstr *MI)
DeleteMachineInstr - Delete the given MachineInstr.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
DenseMap< unsigned, DebugPHIRegallocPos > DebugPHIPositions
Map of debug instruction numbers to the position of their PHI instructions during register allocation...
Representation of each machine instruction.
bool isImplicitDef() const
const MachineBasicBlock * getParent() const
unsigned getNumOperands() const
Retuns the total number of operands.
unsigned peekDebugInstrNum() const
Examine the instruction number of this MachineInstr.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
const MachineOperand & getOperand(unsigned i) const
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineBasicBlock * getMBB() const
void setReg(Register Reg)
Change the register this operand corresponds to.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Wrapper class representing virtual and physical registers.
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
SlotIndex - An opaque wrapper around machine indexes.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
SparseBitVectorIterator iterator
TargetInstrInfo - Interface to description of machine instruction set.
virtual const TargetInstrInfo * getInstrInfo() const
VNInfo - Value Number Information.
SlotIndex def
The index of the defining instruction.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
void initializePHIEliminationPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
char & PHIEliminationID
PHIElimination - This pass eliminates machine instruction PHI nodes by inserting copy instructions.
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...
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.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
This represents a simple continuous liveness interval for a value.
VarInfo - This represents the regions where a virtual register is live in the program.
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.