Go to the documentation of this file.
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;
122 STATISTIC(NumLowered,
"Number of phis lowered");
123 STATISTIC(NumCriticalEdgesSplit,
"Number of critical edges split");
124 STATISTIC(NumReused,
"Number of reused lowered phis");
131 "Eliminate PHI nodes for register allocation",
137 void 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);
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();
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());
400 IncomingLI.
addSegment(LiveInterval::Segment(MBBStartIndex,
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);
741 bool 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 succ_size() const
This is an optimization pass for GlobalISel generic memory operations.
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,...
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
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.
Reg
All possible values of the reg field in the ModR/M byte.
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.
unsigned peekDebugInstrNum() const
Examine the instruction number of this MachineInstr.
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
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.
Represent the analysis usage information of a pass.
void initializePHIEliminationPass(PassRegistry &)
void deleteMachineInstr(MachineInstr *MI)
DeleteMachineInstr - Delete the given MachineInstr.
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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
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)
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
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())
StandardInstrumentations SI(Debug, VerifyEach)
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.
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.
Location of a PHI instruction that is also a debug-info variable value, for the duration of register ...
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."))
DenseMap< unsigned, DebugPHIRegallocPos > DebugPHIPositions
Map of debug instruction numbers to the position of their PHI instructions during register allocation...
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.
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.