X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FBreakCriticalEdges.cpp;h=632aa2b723b953f8d464b23c3e5b3e0333a78261;hb=2de2319124a74b2afff8a0cb1a272dc00b98e273;hp=d4e186cabb2cb1cbba40b356aca74a1b18b7cb21;hpb=3a15503c82a804fcca47b5490e8fb42735ca4131;p=oota-llvm.git diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp index d4e186cabb2..632aa2b723b 100644 --- a/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -16,6 +16,7 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "break-crit-edges" #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Analysis/Dominators.h" @@ -25,20 +26,21 @@ #include "llvm/Type.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" using namespace llvm; -namespace { - Statistic<> NumBroken("break-crit-edges", "Number of blocks inserted"); +STATISTIC(NumBroken, "Number of blocks inserted"); +namespace { struct VISIBILITY_HIDDEN BreakCriticalEdges : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + BreakCriticalEdges() : FunctionPass(&ID) {} + virtual bool runOnFunction(Function &F); virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addPreserved(); - AU.addPreserved(); - AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -47,13 +49,14 @@ namespace { AU.addPreservedID(LoopSimplifyID); } }; - - RegisterPass X("break-crit-edges", - "Break critical edges in CFG"); } +char BreakCriticalEdges::ID = 0; +static RegisterPass +X("break-crit-edges", "Break critical edges in CFG"); + // Publically exposed interface to pass... -const PassInfo *llvm::BreakCriticalEdgesID = X.getPassInfo(); +const PassInfo *const llvm::BreakCriticalEdgesID = &X; FunctionPass *llvm::createBreakCriticalEdgesPass() { return new BreakCriticalEdges(); } @@ -84,7 +87,8 @@ bool BreakCriticalEdges::runOnFunction(Function &F) { // Critical edges are edges from a block with multiple successors to a block // with multiple predecessors. // -bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) { +bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, + bool AllowIdenticalEdges) { assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); if (TI->getNumSuccessors() == 1) return false; @@ -93,34 +97,51 @@ bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) { // If there is more than one predecessor, this is a critical edge... assert(I != E && "No preds, but we have an edge to the block?"); + const BasicBlock *FirstPred = *I; ++I; // Skip one edge due to the incoming arc from TI. - return I != E; + if (!AllowIdenticalEdges) + return I != E; + + // If AllowIdenticalEdges is true, then we allow this edge to be considered + // non-critical iff all preds come from TI's block. + while (I != E) { + if (*I != FirstPred) + return true; + // Note: leave this as is until no one ever compiles with either gcc 4.0.1 + // or Xcode 2. This seems to work around the pred_iterator assert in PR 2207 + E = pred_end(*I); + ++I; + } + return false; } -// SplitCriticalEdge - If this edge is a critical edge, insert a new node to -// split the critical edge. This will update DominatorSet, ImmediateDominator, -// DominatorTree, and DominatorFrontier information if it is available, thus -// calling this pass will not invalidate either of them. This returns true if -// the edge was split, false otherwise. +/// SplitCriticalEdge - If this edge is a critical edge, insert a new node to +/// split the critical edge. This will update DominatorTree and +/// DominatorFrontier information if it is available, thus calling this pass +/// will not invalidate any of them. This returns true if the edge was split, +/// false otherwise. This ensures that all edges to that dest go to one block +/// instead of each going to a different block. // -bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { - if (!isCriticalEdge(TI, SuccNum)) return false; +bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P, + bool MergeIdenticalEdges) { + if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return false; BasicBlock *TIBB = TI->getParent(); BasicBlock *DestBB = TI->getSuccessor(SuccNum); // Create a new basic block, linking it into the CFG. - BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." + - DestBB->getName() + "_crit_edge"); + BasicBlock *NewBB = BasicBlock::Create(TI->getContext(), + TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); // Create our unconditional branch... - new BranchInst(DestBB, NewBB); + BranchInst::Create(DestBB, NewBB); - // Branch to the new block, breaking the edge... + // Branch to the new block, breaking the edge. TI->setSuccessor(SuccNum, NewBB); // Insert the block into the function... right after the block TI lives in. Function &F = *TIBB->getParent(); - F.getBasicBlockList().insert(TIBB->getNext(), NewBB); - + Function::iterator FBBI = TIBB; + F.getBasicBlockList().insert(++FBBI, NewBB); + // If there are any PHI nodes in DestBB, we need to update them so that they // merge incoming values from NewBB instead of from TIBB. // @@ -132,6 +153,23 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { int BBIdx = PN->getBasicBlockIndex(TIBB); PN->setIncomingBlock(BBIdx, NewBB); } + + // If there are any other edges from TIBB to DestBB, update those to go + // through the split block, making those edges non-critical as well (and + // reducing the number of phi entries in the DestBB if relevant). + if (MergeIdenticalEdges) { + for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) { + if (TI->getSuccessor(i) != DestBB) continue; + + // Remove an entry for TIBB from DestBB phi nodes. + DestBB->removePredecessor(TIBB); + + // We found another edge to DestBB, go to NewBB instead. + TI->setSuccessor(i, NewBB); + } + } + + // If we don't have a pass object, we can't update anything... if (P == 0) return true; @@ -147,94 +185,25 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { if (*I != NewBB) OtherPreds.push_back(*I); - // NewBBDominatesDestBB is valid if OtherPreds is empty, otherwise it isn't - // yet computed. bool NewBBDominatesDestBB = true; - // Should we update DominatorSet information? - if (DominatorSet *DS = P->getAnalysisToUpdate()) { - // The blocks that dominate the new one are the blocks that dominate TIBB - // plus the new block itself. - DominatorSet::DomSetType DomSet = DS->getDominators(TIBB); - DomSet.insert(NewBB); // A block always dominates itself. - DS->addBasicBlock(NewBB, DomSet); - - // If NewBBDominatesDestBB hasn't been computed yet, do so with DS. - if (!OtherPreds.empty()) { - while (!OtherPreds.empty() && NewBBDominatesDestBB) { - NewBBDominatesDestBB = DS->dominates(DestBB, OtherPreds.back()); - OtherPreds.pop_back(); - } - OtherPreds.clear(); - } - - // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it - // doesn't dominate anything. If NewBB does dominates DestBB, then it - // dominates everything that DestBB dominates. - if (NewBBDominatesDestBB) { - for (DominatorSet::iterator I = DS->begin(), E = DS->end(); I != E; ++I) - if (I->second.count(DestBB)) - I->second.insert(NewBB); - } - } - - // Should we update ImmediateDominator information? - if (ImmediateDominators *ID = P->getAnalysisToUpdate()) { - // TIBB is the new immediate dominator for NewBB. - ID->addNewBlock(NewBB, TIBB); - - // If NewBBDominatesDestBB hasn't been computed yet, do so with ID. - if (!OtherPreds.empty()) { - while (!OtherPreds.empty() && NewBBDominatesDestBB) { - NewBBDominatesDestBB = ID->dominates(DestBB, OtherPreds.back()); - OtherPreds.pop_back(); - } - OtherPreds.clear(); - } - - // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it - // doesn't dominate anything. - if (NewBBDominatesDestBB) - ID->setImmediateDominator(DestBB, NewBB); - } - - // Update the forest? - if (ETForest *EF = P->getAnalysisToUpdate()) { - // NewBB is dominated by TIBB. - EF->addNewBlock(NewBB, TIBB); - - // If NewBBDominatesDestBB hasn't been computed yet, do so with EF. - if (!OtherPreds.empty()) { - while (!OtherPreds.empty() && NewBBDominatesDestBB) { - NewBBDominatesDestBB = EF->dominates(DestBB, OtherPreds.back()); - OtherPreds.pop_back(); - } - OtherPreds.clear(); - } - - // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it - // doesn't dominate anything. - if (NewBBDominatesDestBB) - EF->setImmediateDominator(DestBB, NewBB); - } - // Should we update DominatorTree information? - if (DominatorTree *DT = P->getAnalysisToUpdate()) { - DominatorTree::Node *TINode = DT->getNode(TIBB); + if (DominatorTree *DT = P->getAnalysisIfAvailable()) { + DomTreeNode *TINode = DT->getNode(TIBB); // The new block is not the immediate dominator for any other nodes, but // TINode is the immediate dominator for the new node. // if (TINode) { // Don't break unreachable code! - DominatorTree::Node *NewBBNode = DT->createNewNode(NewBB, TINode); - DominatorTree::Node *DestBBNode = 0; + DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB); + DomTreeNode *DestBBNode = 0; // If NewBBDominatesDestBB hasn't been computed yet, do so with DT. if (!OtherPreds.empty()) { DestBBNode = DT->getNode(DestBB); while (!OtherPreds.empty() && NewBBDominatesDestBB) { - if (DominatorTree::Node *OPNode = DT->getNode(OtherPreds.back())) - NewBBDominatesDestBB = DestBBNode->dominates(OPNode); + if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back())) + NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode); OtherPreds.pop_back(); } OtherPreds.clear(); @@ -250,12 +219,12 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { } // Should we update DominanceFrontier information? - if (DominanceFrontier *DF = P->getAnalysisToUpdate()) { + if (DominanceFrontier *DF = P->getAnalysisIfAvailable()) { // If NewBBDominatesDestBB hasn't been computed yet, do so with DF. if (!OtherPreds.empty()) { // FIXME: IMPLEMENT THIS! - assert(0 && "Requiring domfrontiers but not idom/domtree/domset." - " not implemented yet!"); + llvm_unreachable("Requiring domfrontiers but not idom/domtree/domset." + " not implemented yet!"); } // Since the new block is dominated by its only predecessor TIBB, @@ -265,8 +234,15 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { DominanceFrontier::DomSetType NewDFSet; if (NewBBDominatesDestBB) { DominanceFrontier::iterator I = DF->find(DestBB); - if (I != DF->end()) + if (I != DF->end()) { DF->addBasicBlock(NewBB, I->second); + + if (I->second.count(DestBB)) { + // However NewBB's frontier does not include DestBB. + DominanceFrontier::iterator NF = DF->find(NewBB); + DF->removeFromFrontier(NF, DestBB); + } + } else DF->addBasicBlock(NewBB, DominanceFrontier::DomSetType()); } else { @@ -277,20 +253,20 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { } // Update LoopInfo if it is around. - if (LoopInfo *LI = P->getAnalysisToUpdate()) { + if (LoopInfo *LI = P->getAnalysisIfAvailable()) { // If one or the other blocks were not in a loop, the new block is not // either, and thus LI doesn't need to be updated. if (Loop *TIL = LI->getLoopFor(TIBB)) if (Loop *DestLoop = LI->getLoopFor(DestBB)) { if (TIL == DestLoop) { // Both in the same loop, the NewBB joins loop. - DestLoop->addBasicBlockToLoop(NewBB, *LI); + DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); } else if (TIL->contains(DestLoop->getHeader())) { // Edge from an outer loop to an inner loop. Add to the outer loop. - TIL->addBasicBlockToLoop(NewBB, *LI); + TIL->addBasicBlockToLoop(NewBB, LI->getBase()); } else if (DestLoop->contains(TIL->getHeader())) { // Edge from an inner loop to an outer loop. Add to the outer loop. - DestLoop->addBasicBlockToLoop(NewBB, *LI); + DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); } else { // Edge from two loops with no containment relation. Because these // are natural loops, we know that the destination block must be the @@ -299,7 +275,7 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { assert(DestLoop->getHeader() == DestBB && "Should not create irreducible loops!"); if (Loop *P = DestLoop->getParentLoop()) - P->addBasicBlockToLoop(NewBB, *LI); + P->addBasicBlockToLoop(NewBB, LI->getBase()); } } }