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 LV->setPHIJoin(IncomingReg);
337 bool IsPHICopyAfterOldKill =
false;
339 if (reusedIncoming && (OldKill =
VI.findKill(&
MBB))) {
351 IsPHICopyAfterOldKill =
true;
360 if (IsPHICopyAfterOldKill) {
362 LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
371 if (!OldKill || IsPHICopyAfterOldKill)
372 LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
378 LV->removeVirtualRegistersKilled(*MPhi);
382 LV->addVirtualRegisterDead(DestReg, *PHICopy);
383 LV->removeVirtualRegisterDead(DestReg, *MPhi);
389 SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
395 LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
399 LIS->getVNInfoAllocator());
406 assert(!DestLI.
empty() &&
"PHIs should have nonempty LiveIntervals.");
412 assert(OrigDestVNI &&
"PHI destination should be live at block entry.");
415 LIS->getVNInfoAllocator());
422 assert(DestVNI &&
"PHI destination should be live at its definition.");
430 --VRegPHIUseCount[BBVRegPair(
439 for (
int i = NumSrcs - 1; i >= 0; --i) {
445 "Machine PHI Operands must all be virtual registers!");
454 if (!MBBsInsertedInto.
insert(&opBlock).second)
458 if (SrcRegDef &&
TII->isUnspillableTerminator(SrcRegDef)) {
461 "Expected operand 0 to be a reg def!");
465 "Expected a single use from UnspillableTerminator");
486 if (!reusedIncoming && IncomingReg) {
492 TII->get(TargetOpcode::IMPLICIT_DEF),
498 ImpDefs.insert(
DefMI);
502 NewSrcInstr =
TII->createPHISourceCopy(opBlock, InsertPos,
nullptr,
503 SrcReg, SrcSubReg, IncomingReg);
510 if (LV && !SrcUndef &&
511 !VRegPHIUseCount[BBVRegPair(opBlock.
getNumber(), SrcReg)] &&
512 !LV->isLiveOut(SrcReg, opBlock)) {
532 if (
Term->readsRegister(SrcReg))
536 if (KillInst == opBlock.
end()) {
539 if (reusedIncoming || !IncomingReg) {
541 KillInst = InsertPos;
542 while (KillInst != opBlock.
begin()) {
544 if (KillInst->isDebugInstr())
546 if (KillInst->readsRegister(SrcReg))
551 KillInst = NewSrcInstr;
554 assert(KillInst->readsRegister(SrcReg) &&
"Cannot find kill instruction");
557 LV->addVirtualRegisterKilled(SrcReg, *KillInst);
560 unsigned opBlockNum = opBlock.
getNumber();
561 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
566 LIS->InsertMachineInstrInMaps(*NewSrcInstr);
567 LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
571 !VRegPHIUseCount[BBVRegPair(opBlock.
getNumber(), SrcReg)]) {
576 SlotIndex startIdx = LIS->getMBBStartIdx(Succ);
580 if (VNI && VNI->
def != startIdx) {
590 if (
Term->readsRegister(SrcReg))
594 if (KillInst == opBlock.
end()) {
597 if (reusedIncoming || !IncomingReg) {
599 KillInst = InsertPos;
600 while (KillInst != opBlock.
begin()) {
602 if (KillInst->isDebugInstr())
604 if (KillInst->readsRegister(SrcReg))
609 KillInst = std::prev(InsertPos);
612 assert(KillInst->readsRegister(SrcReg) &&
613 "Cannot find kill instruction");
615 SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
617 LIS->getMBBEndIdx(&opBlock));
624 if (reusedIncoming || !IncomingReg) {
626 LIS->RemoveMachineInstrFromMaps(*MPhi);
636 for (
const auto &
MBB : MF) {
637 for (
const auto &BBI :
MBB) {
640 for (
unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
641 if (!BBI.getOperand(i).isUndef()) {
642 ++VRegPHIUseCount[BBVRegPair(
643 BBI.getOperand(i + 1).getMBB()->getNumber(),
644 BBI.getOperand(i).getReg())];
659 bool IsLoopHeader = CurLoop && &
MBB == CurLoop->
getHeader();
661 bool Changed =
false;
663 BBI != BBE && BBI->isPHI(); ++BBI) {
664 for (
unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
685 bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
702 ShouldSplit = ShouldSplit && !isLiveIn(Reg, &
MBB);
705 if (!ShouldSplit && CurLoop != PreLoop) {
707 dbgs() <<
"Split wouldn't help, maybe avoid loop copies?\n";
709 dbgs() <<
"PreLoop: " << *PreLoop;
711 dbgs() <<
"CurLoop: " << *CurLoop;
717 ShouldSplit = PreLoop && !PreLoop->
contains(CurLoop);
726 ++NumCriticalEdgesSplit;
734 "isLiveIn() requires either LiveVariables or LiveIntervals");
736 return LIS->isLiveInToMBB(LIS->getInterval(Reg),
MBB);
738 return LV->isLiveIn(Reg, *
MBB);
741bool PHIElimination::isLiveOutPastPHIs(
Register Reg,
744 "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
753 if (LI.
liveAt(LIS->getMBBStartIdx(SI)))
757 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 addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
bool liveAt(SlotIndex index) const
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
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 segment from this 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 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.
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
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.
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.