X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPHIElimination.cpp;h=2c937926d0a7eac09f9a263459102e82c97e21b6;hb=c0bfd317a3e6752dbb1ea042beb9f42d8e55ebfc;hp=dcd907229528c8be6b3e077147e4dbe1fde851c7;hpb=331de11a0acc6a095b98914b5f05ff242c9d7819;p=oota-llvm.git diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp index dcd90722952..2c937926d0a 100644 --- a/lib/CodeGen/PHIElimination.cpp +++ b/lib/CodeGen/PHIElimination.cpp @@ -13,7 +13,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "phielim" #include "llvm/CodeGen/Passes.h" #include "PHIEliminationUtils.h" #include "llvm/ADT/STLExtras.h" @@ -30,11 +29,14 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include using namespace llvm; +#define DEBUG_TYPE "phielim" + static cl::opt DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), cl::Hidden, cl::desc("Disable critical edge splitting " @@ -45,6 +47,10 @@ SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false), cl::Hidden, cl::desc("Split all critical edges during " "PHI elimination")); +static cl::opt 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.")); + namespace { class PHIElimination : public MachineFunctionPass { MachineRegisterInfo *MRI; // Machine register information @@ -57,8 +63,8 @@ namespace { initializePHIEliminationPass(*PassRegistry::getPassRegistry()); } - virtual bool runOnMachineFunction(MachineFunction &Fn); - virtual void getAnalysisUsage(AnalysisUsage &AU) const; + bool runOnMachineFunction(MachineFunction &Fn) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; private: /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions @@ -82,8 +88,8 @@ namespace { // 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); + bool isLiveIn(unsigned Reg, const MachineBasicBlock *MBB); + bool isLiveOutPastPHIs(unsigned Reg, const MachineBasicBlock *MBB); typedef std::pair BBVRegPair; typedef DenseMap VRegPHIUse; @@ -137,21 +143,19 @@ bool PHIElimination::runOnMachineFunction(MachineFunction &MF) { // 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, MLI); + for (auto &MBB : MF) + Changed |= SplitPHIEdges(MF, MBB, MLI); } // Populate VRegPHIUseCount analyzePHINodes(MF); // Eliminate PHI instructions by inserting copies into predecessor blocks. - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) - Changed |= EliminatePHINodes(MF, *I); + for (auto &MBB : MF) + Changed |= EliminatePHINodes(MF, MBB); // Remove dead IMPLICIT_DEF instructions. - for (SmallPtrSet::iterator I = ImpDefs.begin(), - E = ImpDefs.end(); I != E; ++I) { - MachineInstr *DefMI = *I; + for (MachineInstr *DefMI : ImpDefs) { unsigned DefReg = DefMI->getOperand(0).getReg(); if (MRI->use_nodbg_empty(DefReg)) { if (LIS) @@ -186,7 +190,7 @@ bool PHIElimination::EliminatePHINodes(MachineFunction &MF, // Get an iterator to the first instruction after the last PHI node (this may // also be the end of the basic block). MachineBasicBlock::iterator LastPHIIt = - prior(MBB.SkipPHIsAndLabels(MBB.begin())); + std::prev(MBB.SkipPHIsAndLabels(MBB.begin())); while (MBB.front().isPHI()) LowerPHINode(MBB, LastPHIIt); @@ -198,9 +202,8 @@ bool PHIElimination::EliminatePHINodes(MachineFunction &MF, /// This includes registers with no defs. static bool isImplicitlyDefined(unsigned VirtReg, const MachineRegisterInfo *MRI) { - for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(VirtReg), - DE = MRI->def_end(); DI != DE; ++DI) - if (!DI->isImplicitDef()) + for (MachineInstr &DI : MRI->def_instructions(VirtReg)) + if (!DI.isImplicitDef()) return false; return true; } @@ -222,7 +225,7 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, MachineBasicBlock::iterator LastPHIIt) { ++NumLowered; - MachineBasicBlock::iterator AfterPHIsIt = llvm::next(LastPHIIt); + MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt); // Unlink the PHI node from the basic block, but don't delete the PHI yet. MachineInstr *MPhi = MBB.remove(MBB.begin()); @@ -240,7 +243,7 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, // Insert a register to register copy at the top of the current block (but // after any remaining phi nodes) which copies the new incoming register // into the phi node destination. - const TargetInstrInfo *TII = MF.getTarget().getInstrInfo(); + const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo(); if (isSourceDefinedByImplicitDef(MPhi, MRI)) // If all sources of a PHI node are implicit_def, just emit an // implicit_def instead of a copy. @@ -267,7 +270,7 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, // Update live variable information if there is any. if (LV) { - MachineInstr *PHICopy = prior(AfterPHIsIt); + MachineInstr *PHICopy = std::prev(AfterPHIsIt); if (IncomingReg) { LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg); @@ -306,7 +309,7 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, // Update LiveIntervals for the new copy or implicit def. if (LIS) { - MachineInstr *NewInstr = prior(AfterPHIsIt); + MachineInstr *NewInstr = std::prev(AfterPHIsIt); SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(NewInstr); SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB); @@ -369,7 +372,7 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, // 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. - if (!MBBsInsertedInto.insert(&opBlock)) + if (!MBBsInsertedInto.insert(&opBlock).second) continue; // If the copy has already been emitted, we're done. // Find a safe location to insert the copy, this may be the first terminator @@ -378,7 +381,7 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, findPHICopyInsertPoint(&opBlock, &MBB, SrcReg); // Insert the copy. - MachineInstr *NewSrcInstr = 0; + MachineInstr *NewSrcInstr = nullptr; if (!reusedIncoming && IncomingReg) { if (SrcUndef) { // The source register is undefined, so there is no need for a real @@ -444,7 +447,7 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, } } else { // We just inserted this copy. - KillInst = prior(InsertPos); + KillInst = std::prev(InsertPos); } } assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction"); @@ -504,7 +507,7 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, } } else { // We just inserted this copy. - KillInst = prior(InsertPos); + KillInst = std::prev(InsertPos); } } assert(KillInst->readsRegister(SrcReg) && @@ -532,22 +535,23 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, /// used later to determine when the vreg is killed in the BB. /// void 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())]; + 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 PHIElimination::SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB, MachineLoopInfo *MLI) { - if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad()) + if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad()) return false; // Quick exit for basic blocks without PHIs. - const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : 0; + const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr; bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader(); bool Changed = false; @@ -564,7 +568,7 @@ bool PHIElimination::SplitPHIEdges(MachineFunction &MF, // out-of-line blocks into the loop which is very bad for code placement. if (PreMBB == &MBB && !SplitAllCriticalEdges) continue; - const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : 0; + const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr; if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges) continue; @@ -574,12 +578,14 @@ bool PHIElimination::SplitPHIEdges(MachineFunction &MF, // 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) + bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB); + if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit) continue; - - DEBUG(dbgs() << PrintReg(Reg) << " live-out before critical edge BB#" - << PreMBB->getNumber() << " -> BB#" << MBB.getNumber() - << ": " << *BBI); + if (ShouldSplit) { + 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 @@ -589,7 +595,7 @@ bool PHIElimination::SplitPHIEdges(MachineFunction &MF, // 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; + ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB); // Check for a loop exiting edge. if (!ShouldSplit && CurLoop != PreLoop) { @@ -604,10 +610,10 @@ bool PHIElimination::SplitPHIEdges(MachineFunction &MF, // Split unless this edge is entering CurLoop from an outer loop. ShouldSplit = PreLoop && !PreLoop->contains(CurLoop); } - if (!ShouldSplit) + if (!ShouldSplit && !SplitAllCriticalEdges) continue; if (!PreMBB->SplitCriticalEdge(&MBB, this)) { - DEBUG(dbgs() << "Failed to split ciritcal edge.\n"); + DEBUG(dbgs() << "Failed to split critical edge.\n"); continue; } Changed = true; @@ -617,7 +623,7 @@ bool PHIElimination::SplitPHIEdges(MachineFunction &MF, return Changed; } -bool PHIElimination::isLiveIn(unsigned Reg, MachineBasicBlock *MBB) { +bool PHIElimination::isLiveIn(unsigned Reg, const MachineBasicBlock *MBB) { assert((LV || LIS) && "isLiveIn() requires either LiveVariables or LiveIntervals"); if (LIS) @@ -626,7 +632,8 @@ bool PHIElimination::isLiveIn(unsigned Reg, MachineBasicBlock *MBB) { return LV->isLiveIn(Reg, *MBB); } -bool PHIElimination::isLiveOutPastPHIs(unsigned Reg, MachineBasicBlock *MBB) { +bool PHIElimination::isLiveOutPastPHIs(unsigned Reg, + const MachineBasicBlock *MBB) { assert((LV || LIS) && "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals"); // LiveVariables considers uses in PHIs to be in the predecessor basic block, @@ -636,11 +643,9 @@ bool PHIElimination::isLiveOutPastPHIs(unsigned Reg, MachineBasicBlock *MBB) { // 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))) + for (const MachineBasicBlock *SI : MBB->successors()) + if (LI.liveAt(LIS->getMBBStartIdx(SI))) return true; - } return false; } else { return LV->isLiveOut(Reg, *MBB);