X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FCodeGen%2FPHIElimination.cpp;h=b104eb4590877e8bf3238fc85215658495340871;hp=bf2b95fd299ce8ce7bbb0091d50dc830a568e31c;hb=d628f19f5df9e4033adce5af969049e90a90ae5d;hpb=36f54480f83d47404aceea5d41f8f6b95da2d00b diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp index bf2b95fd299..b104eb45908 100644 --- a/lib/CodeGen/PHIElimination.cpp +++ b/lib/CodeGen/PHIElimination.cpp @@ -40,6 +40,11 @@ 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 @@ -61,7 +66,7 @@ namespace { /// bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); void LowerPHINode(MachineBasicBlock &MBB, - MachineBasicBlock::iterator AfterPHIsIt); + 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 @@ -111,6 +116,7 @@ INITIALIZE_PASS_END(PHIElimination, "phi-node-elimination", void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -129,7 +135,7 @@ bool PHIElimination::runOnMachineFunction(MachineFunction &MF) { // Split critical edges to help the coalescer. This does not yet support // updating LiveIntervals, so we disable it. - if (!DisableEdgeSplitting && LV && !LIS) { + if (!DisableEdgeSplitting && (LV || LIS)) { MachineLoopInfo *MLI = getAnalysisIfAvailable(); for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) Changed |= SplitPHIEdges(MF, *I, MLI); @@ -157,8 +163,8 @@ bool PHIElimination::runOnMachineFunction(MachineFunction &MF) { // Clean up the lowered PHI instructions. for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end(); I != E; ++I) { - if (LIS) - LIS->RemoveMachineInstrFromMaps(I->first); + if (LIS) + LIS->RemoveMachineInstrFromMaps(I->first); MF.DeleteMachineInstr(I->first); } @@ -166,9 +172,6 @@ bool PHIElimination::runOnMachineFunction(MachineFunction &MF) { ImpDefs.clear(); VRegPHIUseCount.clear(); - if (LIS) - MF.verify(this, "After PHI elimination"); - return Changed; } @@ -182,10 +185,11 @@ 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 AfterPHIsIt = MBB.SkipPHIsAndLabels(MBB.begin()); + MachineBasicBlock::iterator LastPHIIt = + std::prev(MBB.SkipPHIsAndLabels(MBB.begin())); while (MBB.front().isPHI()) - LowerPHINode(MBB, AfterPHIsIt); + LowerPHINode(MBB, LastPHIIt); return true; } @@ -215,8 +219,11 @@ static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, /// LowerPHINode - Lower the PHI node at the top of the specified block, /// void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, - MachineBasicBlock::iterator AfterPHIsIt) { + MachineBasicBlock::iterator LastPHIIt) { ++NumLowered; + + 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()); @@ -260,7 +267,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); @@ -299,39 +306,40 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, // Update LiveIntervals for the new copy or implicit def. if (LIS) { - MachineInstr *NewInstr = prior(AfterPHIsIt); - LIS->InsertMachineInstrInMaps(NewInstr); + MachineInstr *NewInstr = std::prev(AfterPHIsIt); + SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(NewInstr); SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB); - SlotIndex DestCopyIndex = LIS->getInstructionIndex(NewInstr); if (IncomingReg) { // Add the region from the beginning of MBB to the copy instruction to // IncomingReg's live interval. - LiveInterval &IncomingLI = LIS->getOrCreateInterval(IncomingReg); + LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg); VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex); if (!IncomingVNI) IncomingVNI = IncomingLI.getNextValue(MBBStartIndex, LIS->getVNInfoAllocator()); - IncomingLI.addRange(LiveRange(MBBStartIndex, - DestCopyIndex.getRegSlot(), - IncomingVNI)); + IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex, + DestCopyIndex.getRegSlot(), + IncomingVNI)); } - LiveInterval &DestLI = LIS->getOrCreateInterval(DestReg); - if (NewInstr->getOperand(0).isDead()) { + 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.removeRange(MBBStartIndex, MBBStartIndex.getDeadSlot()); + 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.removeRange(MBBStartIndex, DestCopyIndex.getRegSlot()); + 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(); @@ -436,7 +444,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"); @@ -452,7 +460,7 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, if (LIS) { if (NewSrcInstr) { LIS->InsertMachineInstrInMaps(NewSrcInstr); - LIS->addLiveRangeToEndOfBlock(IncomingReg, NewSrcInstr); + LIS->addSegmentToEndOfBlock(IncomingReg, NewSrcInstr); } if (!SrcUndef && @@ -462,7 +470,11 @@ void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, bool isLiveOut = false; for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(), SE = opBlock.succ_end(); SI != SE; ++SI) { - if (SrcLI.liveAt(LIS->getMBBStartIdx(*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; } @@ -492,15 +504,15 @@ 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"); SlotIndex LastUseIndex = LIS->getInstructionIndex(KillInst); - SrcLI.removeRange(LastUseIndex.getRegSlot(), - LIS->getMBBEndIdx(&opBlock)); + SrcLI.removeSegment(LastUseIndex.getRegSlot(), + LIS->getMBBEndIdx(&opBlock)); } } } @@ -550,10 +562,10 @@ bool PHIElimination::SplitPHIEdges(MachineFunction &MF, // 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) + if (PreMBB == &MBB && !SplitAllCriticalEdges) continue; const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : 0; - if (IsLoopHeader && PreLoop == CurLoop) + if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges) continue; // LV doesn't consider a phi use live-out, so isLiveOut only returns true @@ -562,7 +574,7 @@ 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)) + if (!isLiveOutPastPHIs(Reg, PreMBB) && !SplitAllCriticalEdges) continue; DEBUG(dbgs() << PrintReg(Reg) << " live-out before critical edge BB#" @@ -577,7 +589,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); + bool ShouldSplit = !isLiveIn(Reg, &MBB) || SplitAllCriticalEdges; // Check for a loop exiting edge. if (!ShouldSplit && CurLoop != PreLoop) { @@ -595,7 +607,7 @@ bool PHIElimination::SplitPHIEdges(MachineFunction &MF, if (!ShouldSplit) 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;