54#define DEBUG_TYPE "phi-node-elimination"
58class PHIEliminationImpl {
59 const CodeGenOptions *Opts =
nullptr;
75 bool AllEdgesCritical);
92 using BBVRegPair = std::pair<unsigned, Register>;
96 VRegPHIUse VRegPHIUseCount;
106 using LoweredPHIMap =
108 LoweredPHIMap LoweredPHIs;
112 std::vector<SparseBitVector<>> LiveOutSets;
128 SI = SIWrapper ? &SIWrapper->getSI() :
nullptr;
129 LIS = LISWrapper ? &LISWrapper->getLIS() :
nullptr;
130 MLI = MLIWrapper ? &MLIWrapper->getLI() :
nullptr;
131 MDT = MDTWrapper ? &MDTWrapper->getDomTree() :
nullptr;
132 PDT = PDTWrapper ? &PDTWrapper->getPostDomTree() :
nullptr;
133 MBPI = MBPIWrapper ? &MBPIWrapper->getMBPI() :
nullptr;
156 PHIEliminationImpl Impl(
this);
172 PHIEliminationImpl Impl(MF, MFAM);
187STATISTIC(NumCriticalEdgesSplit,
"Number of critical edges split");
190char PHIElimination::ID = 0;
195 "Eliminate PHI nodes for register allocation",
false,
204void PHIElimination::getAnalysisUsage(
AnalysisUsage &AU)
const {
223 MachineDomTreeUpdater::UpdateStrategy::Lazy);
228 if (Opts->phi_elim_edge_splitting && LIS) {
249 SI->removeMachineInstrFromMaps(*
DefMI);
255 for (
auto &
I : LoweredPHIs) {
257 SI->removeMachineInstrFromMaps(*
I.first);
258 MF.deleteMachineInstr(
I.first);
270 LIS->shrinkToUses(SR,
Reg);
272 PHISrcRegsToShrink.clear();
275 VRegPHIUseCount.clear();
277 MF.getProperties().setNoPHIs();
286 for (
auto I =
MBB.begin();
I != Position;) {
287 if (!
I->isDebugInstr()) {
321 if (
Pred->succ_size() < 2) {
322 AllEdgesCritical =
false;
328 LowerPHINode(
MBB, LastPHIIt, AllEdgesCritical);
338 if (!DI.isImplicitDef())
356 bool AllEdgesCritical) {
371 bool EliminateNow =
true;
372 bool reusedIncoming =
false;
383 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
390 if (AllEdgesCritical)
391 Entry = &LoweredPHIs[MPhi];
392 if (Entry && *Entry) {
394 IncomingReg = *
Entry;
395 reusedIncoming =
true;
403 EliminateNow =
false;
404 *
Entry = IncomingReg;
409 PHICopy =
TII->createPHIDestinationCopy(
426 DestCopyIndex =
SI->insertMachineInstrInMaps(*PHICopy);
430 "Expected a valid SlotIndex if LIS is available.");
435 LiveInterval &IncomingLI = LIS->getOrCreateEmptyInterval(IncomingReg);
439 IncomingLI.
getNextValue(MBBStartIndex, LIS->getVNInfoAllocator());
441 MBBStartIndex, DestCopyIndex.
getRegSlot(), IncomingVNI));
445 assert(!DestLI.
empty() &&
"PHIs should have non-empty LiveIntervals.");
458 for (
auto LR : ToUpdate) {
459 auto DestSegment = LR->find(MBBStartIndex);
460 assert(DestSegment != LR->end() &&
461 "PHI destination must be live in block");
463 if (LR->endIndex().isDead()) {
467 VNInfo *OrigDestVNI = LR->getVNInfoAt(DestSegment->start);
468 assert(OrigDestVNI &&
"PHI destination should be live at block entry.");
469 LR->removeSegment(DestSegment->start, DestSegment->start.getDeadSlot());
470 LR->createDeadDef(NewStart, LIS->getVNInfoAllocator());
471 LR->removeValNo(OrigDestVNI);
478 if (DestSegment->start > NewStart) {
479 VNInfo *VNI = LR->getVNInfoAt(DestSegment->start);
480 assert(VNI &&
"value should be defined for known segment");
483 }
else if (DestSegment->start < NewStart) {
484 assert(DestSegment->start >= MBBStartIndex);
486 LR->removeSegment(DestSegment->start, NewStart);
488 VNInfo *DestVNI = LR->getVNInfoAt(NewStart);
489 assert(DestVNI &&
"PHI destination should be live at its definition.");
490 DestVNI->
def = NewStart;
497 --VRegPHIUseCount[BBVRegPair(
507 for (
int i = NumSrcs - 1; i >= 0; --i) {
513 "Machine PHI Operands must all be virtual registers!");
522 if (!MBBsInsertedInto.
insert(&opBlock).second)
526 if (SrcRegDef &&
TII->isUnspillableTerminator(SrcRegDef)) {
529 "Expected operand 0 to be a reg def!");
533 "Expected a single use from UnspillableTerminator");
539 LiveInterval &IncomingLI = LIS->getOrCreateEmptyInterval(IncomingReg);
541 IncomingLI.
getNextValue(DefIdx, LIS->getVNInfoAllocator());
544 LIS->removeInterval(SrcReg);
557 if (!reusedIncoming && IncomingReg) {
564 TII->get(TargetOpcode::IMPLICIT_DEF), IncomingReg);
569 ImpDefs.insert(
DefMI);
573 NewSrcInstr =
TII->createPHISourceCopy(opBlock, InsertPos,
nullptr,
574 SrcReg, SrcSubReg, IncomingReg);
578 if (
SI && NewSrcInstr)
579 SI->insertMachineInstrInMaps(*NewSrcInstr);
585 "Expected SI to be available to insert new MI if LIS is available");
586 LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
590 !VRegPHIUseCount[BBVRegPair(opBlock.
getNumber(), SrcReg)]) {
593 PHISrcRegsToShrink.insert(SrcReg);
597 SlotIndex startIdx = LIS->getMBBStartIdx(Succ);
601 if (VNI && VNI->
def != startIdx) {
611 if (
Term->readsRegister(SrcReg,
nullptr))
615 if (KillInst == opBlock.
end()) {
618 if (reusedIncoming || !IncomingReg) {
620 KillInst = InsertPos;
621 while (KillInst != opBlock.
begin()) {
623 if (KillInst->isDebugInstr())
625 if (KillInst->readsRegister(SrcReg,
nullptr))
630 KillInst = std::prev(InsertPos);
633 assert(KillInst->readsRegister(SrcReg,
nullptr) &&
634 "Cannot find kill instruction");
636 SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
638 LIS->getMBBEndIdx(&opBlock));
647 SI->removeMachineInstrFromMaps(*MPhi);
648 MF.deleteMachineInstr(MPhi);
657 for (
const auto &
MBB : MF) {
658 for (
const auto &BBI :
MBB) {
661 for (
unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
662 if (!BBI.getOperand(i).isUndef()) {
663 ++VRegPHIUseCount[BBVRegPair(
664 BBI.getOperand(i + 1).getMBB()->getNumber(),
665 BBI.getOperand(i).getReg())];
680 bool IsLoopHeader = CurLoop && &
MBB == CurLoop->
getHeader();
684 BBI != BBE && BBI->isPHI(); ++BBI) {
685 for (
unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
694 if (PreMBB == &
MBB && !Opts->phi_elim_split_all_critical_edges)
697 if (IsLoopHeader && PreLoop == CurLoop &&
698 !Opts->phi_elim_split_all_critical_edges)
707 bool ShouldSplit = isLiveOutPastPHIs(
Reg, PreMBB);
708 if (!ShouldSplit && Opts->phi_elim_live_out_early_exit)
725 ShouldSplit && !LIS->isLiveInToMBB(LIS->getInterval(
Reg), &
MBB);
728 if (!ShouldSplit && CurLoop != PreLoop) {
730 dbgs() <<
"Split wouldn't help, maybe avoid loop copies?\n";
732 dbgs() <<
"PreLoop: " << *PreLoop;
734 dbgs() <<
"CurLoop: " << *CurLoop;
740 ShouldSplit = PreLoop && !PreLoop->
contains(CurLoop);
742 if (!ShouldSplit && !Opts->phi_elim_split_all_critical_edges)
744 if (LiveOutSets.empty())
745 computeLiveOutSets(MF);
756 MBFI->onEdgeSplit(*PreMBB, *NewBB, *MBPI);
760 ++NumCriticalEdgesSplit;
766void PHIEliminationImpl::computeLiveOutSets(
const MachineFunction &MF) {
771 if (!LIS->hasInterval(
Reg))
781bool PHIEliminationImpl::isLiveOutPastPHIs(
Register Reg,
788 if (LIS->isLiveInToMBB(LI,
SI))
MachineInstrBuilder MachineInstrBuilder & DefMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
const AArch64InstrInfo MachineBasicBlock::iterator InsertPt
const AArch64InstrInfo & TII
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
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.
static bool isImplicitlyDefined(Register VirtReg, const MachineRegisterInfo &MRI)
Return true if all defs of VirtReg are implicit-defs.
static void moveDebugInstructionsAfter(MachineBasicBlock &MBB, MachineBasicBlock::iterator Position)
Move debug instructions preceding Position to immediately after it.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
MachineRegisterInfo & MRI
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
A live range for subregisters.
LiveInterval - This class represents the liveness of a register, or stack slot.
bool hasSubRanges() const
Returns true if subregister liveness information is available.
iterator_range< subrange_iterator > subranges()
LLVM_ABI iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
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.
LLVM_ABI 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 this loop.
BlockT * getHeader() const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
const MachineBlockFrequencyInfo & getMBFI() const
unsigned pred_size() 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...
LLVM_ABI iterator SkipPHIsLabelsAndDebug(iterator I, Register Reg=Register(), bool SkipPseudoOp=true)
Return the first instruction in MBB after I that is not a PHI, label or debug.
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
unsigned succ_size() const
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineBasicBlock * SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P, MachineDomTreeUpdater *MDTU=nullptr)
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
MachineInstrBundleIterator< MachineInstr > iterator
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Analysis pass which computes a MachineDominatorTree.
Analysis pass which computes a MachineDominatorTree.
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.
Properties which a MachineFunction may have at a given point in time.
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.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
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
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.
const MachineOperand & getOperand(unsigned i) const
LLVM_ABI MachineInstrBundleIterator< MachineInstr > eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
Analysis pass that exposes the MachineLoopInfo for a machine function.
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 setIsDead(bool Val=true)
LLVM_ABI void setReg(Register Reg)
Change the register this operand corresponds to.
Register getReg() const
getReg - Returns the register number.
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
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.
LLVM_ABI LLVM_READONLY MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
LLVM_ABI Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
bool use_empty(Register RegNo) const
use_empty - Return true if there are no instructions using the specified register.
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
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.
bool isValid() const
Returns true if this is a valid index.
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.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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.
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
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.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
MachineBasicBlock::iterator findPHICopyInsertPoint(MachineBasicBlock *MBB, MachineBasicBlock *SuccMBB, Register SrcReg)
findPHICopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg when following the CFG...
LLVM_ABI char & PHIEliminationID
PHIElimination - This pass eliminates machine instruction PHI nodes by inserting copy instructions.
IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It, then continue decrementing it while it points to a debug instruction.
LLVM_ABI 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.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
MCRegisterClass TargetRegisterClass
This represents a simple continuous liveness interval for a value.