X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPHIElimination.cpp;h=c8d0819ad13c07511c3080ca5a2917e1bb9737e4;hb=482018007c06507ec667f420ccbccb3d134acc3b;hp=11566c2d866bc4208b3a042572c976a7c3a82b45;hpb=e008384508342a2dec110eafaa87d93614976990;p=oota-llvm.git diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp index 11566c2d866..c8d0819ad13 100644 --- a/lib/CodeGen/PHIElimination.cpp +++ b/lib/CodeGen/PHIElimination.cpp @@ -13,54 +13,134 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "phielim" -#include "PHIElimination.h" -#include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/Passes.h" +#include "PHIEliminationUtils.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Function.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/Statistic.h" +#include "llvm/IR/Function.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" #include -#include using namespace llvm; -STATISTIC(NumAtomic, "Number of atomic phis lowered"); +#define DEBUG_TYPE "phielim" + +static cl::opt +DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), + cl::Hidden, cl::desc("Disable critical edge splitting " + "during PHI elimination")); + +static cl::opt +SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false), + cl::Hidden, cl::desc("Split all critical edges during " + "PHI elimination")); + +namespace { + class PHIElimination : public MachineFunctionPass { + MachineRegisterInfo *MRI; // Machine register information + LiveVariables *LV; + LiveIntervals *LIS; + + public: + static char ID; // Pass identification, replacement for typeid + PHIElimination() : MachineFunctionPass(ID) { + initializePHIEliminationPass(*PassRegistry::getPassRegistry()); + } + + bool runOnMachineFunction(MachineFunction &Fn) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; + + private: + /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions + /// in predecessor basic blocks. + /// + bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); + void LowerPHINode(MachineBasicBlock &MBB, + MachineBasicBlock::iterator LastPHIIt); + + /// analyzePHINodes - Gather information about the PHI nodes in + /// here. In particular, we want to map the number of uses of a virtual + /// register which is used in a PHI node. We map that to the BB the + /// vreg is coming from. This is used later to determine when the vreg + /// is killed in the BB. + /// + void analyzePHINodes(const MachineFunction& Fn); + + /// Split critical edges where necessary for good coalescer performance. + bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB, + MachineLoopInfo *MLI); + + // These functions are temporary abstractions around LiveVariables and + // LiveIntervals, so they can go away when LiveVariables does. + bool isLiveIn(unsigned Reg, MachineBasicBlock *MBB); + bool isLiveOutPastPHIs(unsigned Reg, MachineBasicBlock *MBB); + + typedef std::pair BBVRegPair; + typedef DenseMap VRegPHIUse; + + VRegPHIUse VRegPHIUseCount; + + // Defs of PHI sources which are implicit_def. + SmallPtrSet ImpDefs; + + // Map reusable lowered PHI node -> incoming join register. + typedef DenseMap LoweredPHIMap; + LoweredPHIMap LoweredPHIs; + }; +} + +STATISTIC(NumLowered, "Number of phis lowered"); +STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split"); STATISTIC(NumReused, "Number of reused lowered phis"); char PHIElimination::ID = 0; -static RegisterPass -X("phi-node-elimination", "Eliminate PHI nodes for register allocation"); +char& llvm::PHIEliminationID = PHIElimination::ID; -char &llvm::PHIEliminationID = PHIElimination::ID; +INITIALIZE_PASS_BEGIN(PHIElimination, "phi-node-elimination", + "Eliminate PHI nodes for register allocation", + false, false) +INITIALIZE_PASS_DEPENDENCY(LiveVariables) +INITIALIZE_PASS_END(PHIElimination, "phi-node-elimination", + "Eliminate PHI nodes for register allocation", false, false) -void llvm::PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { +void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved(); - AU.addRequired(); + AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); - AU.addPreservedID(MachineLoopInfoID); + AU.addPreserved(); MachineFunctionPass::getAnalysisUsage(AU); } -bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &MF) { +bool PHIElimination::runOnMachineFunction(MachineFunction &MF) { MRI = &MF.getRegInfo(); - MLI = getAnalysisIfAvailable(); + LV = getAnalysisIfAvailable(); + LIS = getAnalysisIfAvailable(); bool Changed = false; - // Split critical edges to help the coalescer - if (LiveVariables *LV = getAnalysisIfAvailable()) + // This pass takes the function out of SSA form. + MRI->leaveSSA(); + + // Split critical edges to help the coalescer. This does not yet support + // updating LiveIntervals, so we disable it. + if (!DisableEdgeSplitting && (LV || LIS)) { + MachineLoopInfo *MLI = getAnalysisIfAvailable(); for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) - Changed |= SplitPHIEdges(MF, *I, *LV); + Changed |= SplitPHIEdges(MF, *I, MLI); + } // Populate VRegPHIUseCount analyzePHINodes(MF); @@ -74,14 +154,20 @@ bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &MF) { E = ImpDefs.end(); I != E; ++I) { MachineInstr *DefMI = *I; unsigned DefReg = DefMI->getOperand(0).getReg(); - if (MRI->use_nodbg_empty(DefReg)) + if (MRI->use_nodbg_empty(DefReg)) { + if (LIS) + LIS->RemoveMachineInstrFromMaps(DefMI); DefMI->eraseFromParent(); + } } // Clean up the lowered PHI instructions. for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end(); - I != E; ++I) + I != E; ++I) { + if (LIS) + LIS->RemoveMachineInstrFromMaps(I->first); MF.DeleteMachineInstr(I->first); + } LoweredPHIs.clear(); ImpDefs.clear(); @@ -93,18 +179,29 @@ bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &MF) { /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in /// predecessor basic blocks. /// -bool llvm::PHIElimination::EliminatePHINodes(MachineFunction &MF, +bool PHIElimination::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { if (MBB.empty() || !MBB.front().isPHI()) return false; // Quick exit for basic blocks without PHIs. // Get an iterator to the first instruction after the last PHI node (this may // also be the end of the basic block). - MachineBasicBlock::iterator AfterPHIsIt = SkipPHIsAndLabels(MBB, MBB.begin()); + MachineBasicBlock::iterator LastPHIIt = + std::prev(MBB.SkipPHIsAndLabels(MBB.begin())); while (MBB.front().isPHI()) - LowerAtomicPHINode(MBB, AfterPHIsIt); + LowerPHINode(MBB, LastPHIIt); + + return true; +} +/// isImplicitlyDefined - Return true if all defs of VirtReg are implicit-defs. +/// This includes registers with no defs. +static bool isImplicitlyDefined(unsigned VirtReg, + const MachineRegisterInfo *MRI) { + for (MachineInstr &DI : MRI->def_instructions(VirtReg)) + if (!DI.isImplicitDef()) + return false; return true; } @@ -112,75 +209,27 @@ bool llvm::PHIElimination::EliminatePHINodes(MachineFunction &MF, /// are implicit_def's. static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, const MachineRegisterInfo *MRI) { - for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) { - unsigned SrcReg = MPhi->getOperand(i).getReg(); - const MachineInstr *DefMI = MRI->getVRegDef(SrcReg); - if (!DefMI || !DefMI->isImplicitDef()) + for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) + if (!isImplicitlyDefined(MPhi->getOperand(i).getReg(), MRI)) return false; - } return true; } -// FindCopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg -// when following the CFG edge to SuccMBB. This needs to be after any def of -// SrcReg, but before any subsequent point where control flow might jump out of -// the basic block. -MachineBasicBlock::iterator -llvm::PHIElimination::FindCopyInsertPoint(MachineBasicBlock &MBB, - MachineBasicBlock &SuccMBB, - unsigned SrcReg) { - // Handle the trivial case trivially. - if (MBB.empty()) - return MBB.begin(); - - // Usually, we just want to insert the copy before the first terminator - // instruction. However, for the edge going to a landing pad, we must insert - // the copy before the call/invoke instruction. - if (!SuccMBB.isLandingPad()) - return MBB.getFirstTerminator(); - - // Discover any defs/uses in this basic block. - SmallPtrSet DefUsesInMBB; - for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg), - RE = MRI->reg_end(); RI != RE; ++RI) { - MachineInstr *DefUseMI = &*RI; - if (DefUseMI->getParent() == &MBB) - DefUsesInMBB.insert(DefUseMI); - } - MachineBasicBlock::iterator InsertPoint; - if (DefUsesInMBB.empty()) { - // No defs. Insert the copy at the start of the basic block. - InsertPoint = MBB.begin(); - } else if (DefUsesInMBB.size() == 1) { - // Insert the copy immediately after the def/use. - InsertPoint = *DefUsesInMBB.begin(); - ++InsertPoint; - } else { - // Insert the copy immediately after the last def/use. - InsertPoint = MBB.end(); - while (!DefUsesInMBB.count(&*--InsertPoint)) {} - ++InsertPoint; - } +/// LowerPHINode - Lower the PHI node at the top of the specified block, +/// +void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, + MachineBasicBlock::iterator LastPHIIt) { + ++NumLowered; - // Make sure the copy goes after any phi nodes however. - return SkipPHIsAndLabels(MBB, InsertPoint); -} + MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt); -/// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, -/// under the assuption that it needs to be lowered in a way that supports -/// atomic execution of PHIs. This lowering method is always correct all of the -/// time. -/// -void llvm::PHIElimination::LowerAtomicPHINode( - MachineBasicBlock &MBB, - MachineBasicBlock::iterator AfterPHIsIt) { - ++NumAtomic; // Unlink the PHI node from the basic block, but don't delete the PHI yet. MachineInstr *MPhi = MBB.remove(MBB.begin()); unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2; unsigned DestReg = MPhi->getOperand(0).getReg(); + assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs"); bool isDead = MPhi->getOperand(0).isDead(); // Create a new register for the incoming PHI arguments. @@ -206,7 +255,7 @@ void llvm::PHIElimination::LowerAtomicPHINode( IncomingReg = entry; reusedIncoming = true; ++NumReused; - DEBUG(dbgs() << "Reusing %reg" << IncomingReg << " for " << *MPhi); + DEBUG(dbgs() << "Reusing " << PrintReg(IncomingReg) << " for " << *MPhi); } else { const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC); @@ -217,15 +266,13 @@ void llvm::PHIElimination::LowerAtomicPHINode( } // Update live variable information if there is any. - LiveVariables *LV = getAnalysisIfAvailable(); if (LV) { - MachineInstr *PHICopy = prior(AfterPHIsIt); + MachineInstr *PHICopy = std::prev(AfterPHIsIt); if (IncomingReg) { LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg); // Increment use count of the newly created virtual register. - VI.NumUses++; LV->setPHIJoin(IncomingReg); // When we are reusing the incoming register, it may already have been @@ -257,6 +304,48 @@ void llvm::PHIElimination::LowerAtomicPHINode( } } + // Update LiveIntervals for the new copy or implicit def. + if (LIS) { + MachineInstr *NewInstr = std::prev(AfterPHIsIt); + SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(NewInstr); + + SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB); + if (IncomingReg) { + // Add the region from the beginning of MBB to the copy instruction to + // IncomingReg's live interval. + LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg); + VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex); + if (!IncomingVNI) + IncomingVNI = IncomingLI.getNextValue(MBBStartIndex, + LIS->getVNInfoAllocator()); + IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex, + DestCopyIndex.getRegSlot(), + IncomingVNI)); + } + + LiveInterval &DestLI = LIS->getInterval(DestReg); + assert(DestLI.begin() != DestLI.end() && + "PHIs should have nonempty LiveIntervals."); + if (DestLI.endIndex().isDead()) { + // A dead PHI's live range begins and ends at the start of the MBB, but + // the lowered copy, which will still be dead, needs to begin and end at + // the copy instruction. + VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex); + assert(OrigDestVNI && "PHI destination should be live at block entry."); + DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot()); + DestLI.createDeadDef(DestCopyIndex.getRegSlot(), + LIS->getVNInfoAllocator()); + DestLI.removeValNo(OrigDestVNI); + } else { + // Otherwise, remove the region from the beginning of MBB to the copy + // instruction from DestReg's live interval. + DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot()); + VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot()); + assert(DestVNI && "PHI destination should be live at its definition."); + DestVNI->def = DestCopyIndex.getRegSlot(); + } + } + // Adjust the VRegPHIUseCount map to account for the removal of this PHI node. for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(), @@ -267,6 +356,9 @@ void llvm::PHIElimination::LowerAtomicPHINode( SmallPtrSet MBBsInsertedInto; for (int i = NumSrcs - 1; i >= 0; --i) { unsigned SrcReg = MPhi->getOperand(i*2+1).getReg(); + unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg(); + bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() || + isImplicitlyDefined(SrcReg, MRI); assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && "Machine PHI Operands must all be virtual registers!"); @@ -274,14 +366,6 @@ void llvm::PHIElimination::LowerAtomicPHINode( // path the PHI. MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB(); - // If source is defined by an implicit def, there is no need to insert a - // copy. - MachineInstr *DefMI = MRI->getVRegDef(SrcReg); - if (DefMI->isImplicitDef()) { - ImpDefs.insert(DefMI); - continue; - } - // Check to make sure we haven't already emitted the copy for this block. // This can happen because PHI nodes may have multiple entries for the same // basic block. @@ -291,61 +375,77 @@ void llvm::PHIElimination::LowerAtomicPHINode( // Find a safe location to insert the copy, this may be the first terminator // in the block (or end()). MachineBasicBlock::iterator InsertPos = - FindCopyInsertPoint(opBlock, MBB, SrcReg); + findPHICopyInsertPoint(&opBlock, &MBB, SrcReg); // Insert the copy. - if (!reusedIncoming && IncomingReg) - BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), - TII->get(TargetOpcode::COPY), IncomingReg).addReg(SrcReg); - - // Now update live variable information if we have it. Otherwise we're done - if (!LV) continue; - - // We want to be able to insert a kill of the register if this PHI (aka, the - // copy we just inserted) is the last use of the source value. Live - // variable analysis conservatively handles this by saying that the value is - // live until the end of the block the PHI entry lives in. If the value - // really is dead at the PHI copy, there will be no successor blocks which - // have the value live-in. - - // Also check to see if this register is in use by another PHI node which - // has not yet been eliminated. If so, it will be killed at an appropriate - // point later. - - // Is it used by any PHI instructions in this block? - bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]; - - // Okay, if we now know that the value is not live out of the block, we can - // add a kill marker in this block saying that it kills the incoming value! - if (!ValueIsUsed && !LV->isLiveOut(SrcReg, opBlock)) { + MachineInstr *NewSrcInstr = nullptr; + if (!reusedIncoming && IncomingReg) { + if (SrcUndef) { + // The source register is undefined, so there is no need for a real + // COPY, but we still need to ensure joint dominance by defs. + // Insert an IMPLICIT_DEF instruction. + NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), + TII->get(TargetOpcode::IMPLICIT_DEF), + IncomingReg); + + // Clean up the old implicit-def, if there even was one. + if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg)) + if (DefMI->isImplicitDef()) + ImpDefs.insert(DefMI); + } else { + NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), + TII->get(TargetOpcode::COPY), IncomingReg) + .addReg(SrcReg, 0, SrcSubReg); + } + } + + // We only need to update the LiveVariables kill of SrcReg if this was the + // last PHI use of SrcReg to be lowered on this CFG edge and it is not live + // out of the predecessor. We can also ignore undef sources. + if (LV && !SrcUndef && + !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] && + !LV->isLiveOut(SrcReg, opBlock)) { + // We want to be able to insert a kill of the register if this PHI (aka, + // the copy we just inserted) is the last use of the source value. Live + // variable analysis conservatively handles this by saying that the value + // is live until the end of the block the PHI entry lives in. If the value + // really is dead at the PHI copy, there will be no successor blocks which + // have the value live-in. + + // Okay, if we now know that the value is not live out of the block, we + // can add a kill marker in this block saying that it kills the incoming + // value! + // In our final twist, we have to decide which instruction kills the - // register. In most cases this is the copy, however, the first - // terminator instruction at the end of the block may also use the value. - // In this case, we should mark *it* as being the killing block, not the - // copy. - MachineBasicBlock::iterator KillInst; - MachineBasicBlock::iterator Term = opBlock.getFirstTerminator(); - if (Term != opBlock.end() && Term->readsRegister(SrcReg)) { - KillInst = Term; - - // Check that no other terminators use values. -#ifndef NDEBUG - for (MachineBasicBlock::iterator TI = llvm::next(Term); - TI != opBlock.end(); ++TI) { - assert(!TI->readsRegister(SrcReg) && - "Terminator instructions cannot use virtual registers unless" - "they are the first terminator in a block!"); + // register. In most cases this is the copy, however, terminator + // instructions at the end of the block may also use the value. In this + // case, we should mark the last such terminator as being the killing + // block, not the copy. + MachineBasicBlock::iterator KillInst = opBlock.end(); + MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator(); + for (MachineBasicBlock::iterator Term = FirstTerm; + Term != opBlock.end(); ++Term) { + if (Term->readsRegister(SrcReg)) + KillInst = Term; + } + + if (KillInst == opBlock.end()) { + // No terminator uses the register. + + if (reusedIncoming || !IncomingReg) { + // We may have to rewind a bit if we didn't insert a copy this time. + KillInst = FirstTerm; + while (KillInst != opBlock.begin()) { + --KillInst; + if (KillInst->isDebugValue()) + continue; + if (KillInst->readsRegister(SrcReg)) + break; + } + } else { + // We just inserted this copy. + KillInst = std::prev(InsertPos); } -#endif - } else if (reusedIncoming || !IncomingReg) { - // We may have to rewind a bit if we didn't insert a copy this time. - KillInst = Term; - while (KillInst != opBlock.begin()) - if ((--KillInst)->readsRegister(SrcReg)) - break; - } else { - // We just inserted this copy. - KillInst = prior(InsertPos); } assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction"); @@ -356,11 +456,74 @@ void llvm::PHIElimination::LowerAtomicPHINode( unsigned opBlockNum = opBlock.getNumber(); LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum); } + + if (LIS) { + if (NewSrcInstr) { + LIS->InsertMachineInstrInMaps(NewSrcInstr); + LIS->addSegmentToEndOfBlock(IncomingReg, NewSrcInstr); + } + + if (!SrcUndef && + !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) { + LiveInterval &SrcLI = LIS->getInterval(SrcReg); + + bool isLiveOut = false; + for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(), + SE = opBlock.succ_end(); SI != SE; ++SI) { + SlotIndex startIdx = LIS->getMBBStartIdx(*SI); + VNInfo *VNI = SrcLI.getVNInfoAt(startIdx); + + // Definitions by other PHIs are not truly live-in for our purposes. + if (VNI && VNI->def != startIdx) { + isLiveOut = true; + break; + } + } + + if (!isLiveOut) { + MachineBasicBlock::iterator KillInst = opBlock.end(); + MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator(); + for (MachineBasicBlock::iterator Term = FirstTerm; + Term != opBlock.end(); ++Term) { + if (Term->readsRegister(SrcReg)) + KillInst = Term; + } + + if (KillInst == opBlock.end()) { + // No terminator uses the register. + + if (reusedIncoming || !IncomingReg) { + // We may have to rewind a bit if we didn't just insert a copy. + KillInst = FirstTerm; + while (KillInst != opBlock.begin()) { + --KillInst; + if (KillInst->isDebugValue()) + continue; + if (KillInst->readsRegister(SrcReg)) + break; + } + } else { + // We just inserted this copy. + KillInst = std::prev(InsertPos); + } + } + assert(KillInst->readsRegister(SrcReg) && + "Cannot find kill instruction"); + + SlotIndex LastUseIndex = LIS->getInstructionIndex(KillInst); + SrcLI.removeSegment(LastUseIndex.getRegSlot(), + LIS->getMBBEndIdx(&opBlock)); + } + } + } } // Really delete the PHI instruction now, if it is not in the LoweredPHIs map. - if (reusedIncoming || !IncomingReg) + if (reusedIncoming || !IncomingReg) { + if (LIS) + LIS->RemoveMachineInstrFromMaps(MPhi); MF.DeleteMachineInstr(MPhi); + } } /// analyzePHINodes - Gather information about the PHI nodes in here. In @@ -368,40 +531,119 @@ void llvm::PHIElimination::LowerAtomicPHINode( /// used in a PHI node. We map that to the BB the vreg is coming from. This is /// used later to determine when the vreg is killed in the BB. /// -void llvm::PHIElimination::analyzePHINodes(const MachineFunction& MF) { - for (MachineFunction::const_iterator I = MF.begin(), E = MF.end(); - I != E; ++I) - for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); - BBI != BBE && BBI->isPHI(); ++BBI) - for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) - ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(), - BBI->getOperand(i).getReg())]; +void PHIElimination::analyzePHINodes(const MachineFunction& MF) { + for (const auto &MBB : MF) + for (const auto &BBI : MBB) { + if (!BBI.isPHI()) + break; + for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) + ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(), + BBI.getOperand(i).getReg())]; + } } -bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF, - MachineBasicBlock &MBB, - LiveVariables &LV) { +bool PHIElimination::SplitPHIEdges(MachineFunction &MF, + MachineBasicBlock &MBB, + MachineLoopInfo *MLI) { if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad()) return false; // Quick exit for basic blocks without PHIs. + const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr; + bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader(); + bool Changed = false; - for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end(); + for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end(); BBI != BBE && BBI->isPHI(); ++BBI) { for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { unsigned Reg = BBI->getOperand(i).getReg(); MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB(); - // We break edges when registers are live out from the predecessor block - // (not considering PHI nodes). If the register is live in to this block - // anyway, we would gain nothing from splitting. + // Is there a critical edge from PreMBB to MBB? + if (PreMBB->succ_size() == 1) + continue; + // Avoid splitting backedges of loops. It would introduce small // out-of-line blocks into the loop which is very bad for code placement. - if (PreMBB != &MBB && - !LV.isLiveIn(Reg, MBB) && LV.isLiveOut(Reg, *PreMBB)) { - if (!(MLI->getLoopFor(PreMBB) == MLI->getLoopFor(&MBB) && - MLI->isLoopHeader(&MBB))) - Changed |= PreMBB->SplitCriticalEdge(&MBB, this) != 0; + if (PreMBB == &MBB && !SplitAllCriticalEdges) + continue; + const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr; + if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges) + continue; + + // LV doesn't consider a phi use live-out, so isLiveOut only returns true + // when the source register is live-out for some other reason than a phi + // use. That means the copy we will insert in PreMBB won't be a kill, and + // there is a risk it may not be coalesced away. + // + // If the copy would be a kill, there is no need to split the edge. + if (!isLiveOutPastPHIs(Reg, PreMBB) && !SplitAllCriticalEdges) + continue; + + DEBUG(dbgs() << PrintReg(Reg) << " live-out before critical edge BB#" + << PreMBB->getNumber() << " -> BB#" << MBB.getNumber() + << ": " << *BBI); + + // If Reg is not live-in to MBB, it means it must be live-in to some + // other PreMBB successor, and we can avoid the interference by splitting + // the edge. + // + // If Reg *is* live-in to MBB, the interference is inevitable and a copy + // is likely to be left after coalescing. If we are looking at a loop + // exiting edge, split it so we won't insert code in the loop, otherwise + // don't bother. + bool ShouldSplit = !isLiveIn(Reg, &MBB) || SplitAllCriticalEdges; + + // Check for a loop exiting edge. + if (!ShouldSplit && CurLoop != PreLoop) { + DEBUG({ + dbgs() << "Split wouldn't help, maybe avoid loop copies?\n"; + if (PreLoop) dbgs() << "PreLoop: " << *PreLoop; + if (CurLoop) dbgs() << "CurLoop: " << *CurLoop; + }); + // This edge could be entering a loop, exiting a loop, or it could be + // both: Jumping directly form one loop to the header of a sibling + // loop. + // Split unless this edge is entering CurLoop from an outer loop. + ShouldSplit = PreLoop && !PreLoop->contains(CurLoop); + } + if (!ShouldSplit) + continue; + if (!PreMBB->SplitCriticalEdge(&MBB, this)) { + DEBUG(dbgs() << "Failed to split critical edge.\n"); + continue; } + Changed = true; + ++NumCriticalEdgesSplit; } } - return true; + return Changed; +} + +bool PHIElimination::isLiveIn(unsigned Reg, MachineBasicBlock *MBB) { + assert((LV || LIS) && + "isLiveIn() requires either LiveVariables or LiveIntervals"); + if (LIS) + return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB); + else + return LV->isLiveIn(Reg, *MBB); +} + +bool PHIElimination::isLiveOutPastPHIs(unsigned Reg, MachineBasicBlock *MBB) { + assert((LV || LIS) && + "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals"); + // LiveVariables considers uses in PHIs to be in the predecessor basic block, + // so that a register used only in a PHI is not live out of the block. In + // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than + // in the predecessor basic block, so that a register used only in a PHI is live + // out of the block. + if (LIS) { + const LiveInterval &LI = LIS->getInterval(Reg); + for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), + SE = MBB->succ_end(); SI != SE; ++SI) { + if (LI.liveAt(LIS->getMBBStartIdx(*SI))) + return true; + } + return false; + } else { + return LV->isLiveOut(Reg, *MBB); + } }