X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FBreakCriticalEdges.cpp;h=616b066b5ab140543399a0cd1f5049a7e0790ef6;hb=2bc2a08b1bf6b5dcbfa515acc85999d6f884ec1a;hp=cc822dae86adbfa8764621a1db4bd1e43b38619d;hpb=a4f0b3a084d120cfc5b5bb06f64b222f5cb72740;p=oota-llvm.git diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp index cc822dae86a..616b066b5ab 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. // //===----------------------------------------------------------------------===// // @@ -11,48 +11,53 @@ // inserting a dummy basic block. This pass may be "required" by passes that // cannot deal with critical edges. For this usage, the structure type is // forward declared. This pass obviously invalidates the CFG, but can update -// forward dominator (set, immediate dominators, tree, and frontier) -// information. +// dominator trees. // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "break-crit-edges" #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ProfileInfo.h" #include "llvm/Function.h" #include "llvm/Instructions.h" #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; +STATISTIC(NumBroken, "Number of blocks inserted"); + namespace { - Statistic<> NumBroken("break-crit-edges", "Number of blocks inserted"); + struct BreakCriticalEdges : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + BreakCriticalEdges() : FunctionPass(ID) { + initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry()); + } - struct VISIBILITY_HIDDEN BreakCriticalEdges : public FunctionPass { virtual bool runOnFunction(Function &F); virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addPreserved(); - AU.addPreserved(); - AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); AU.addPreserved(); + AU.addPreserved(); // No loop canonicalization guarantees are broken by this pass. AU.addPreservedID(LoopSimplifyID); } }; - - RegisterOpt X("break-crit-edges", - "Break critical edges in CFG"); } +char BreakCriticalEdges::ID = 0; +INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges", + "Break critical edges in CFG", false, false) + // Publically exposed interface to pass... -const PassInfo *llvm::BreakCriticalEdgesID = X.getPassInfo(); +char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID; FunctionPass *llvm::createBreakCriticalEdgesPass() { return new BreakCriticalEdges(); } @@ -64,7 +69,7 @@ bool BreakCriticalEdges::runOnFunction(Function &F) { bool Changed = false; for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { TerminatorInst *TI = I->getTerminator(); - if (TI->getNumSuccessors() > 1) + if (TI->getNumSuccessors() > 1 && !isa(TI)) for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) if (SplitCriticalEdge(TI, i, this)) { ++NumBroken; @@ -83,118 +88,249 @@ 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; const BasicBlock *Dest = TI->getSuccessor(SuccNum); - pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); + const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest); // 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) { + const BasicBlock *P = *I; + if (P != 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(P); + ++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. -// -bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { - if (!isCriticalEdge(TI, SuccNum)) return false; +/// CreatePHIsForSplitLoopExit - When a loop exit edge is split, LCSSA form +/// may require new PHIs in the new exit block. This function inserts the +/// new PHIs, as needed. Preds is a list of preds inside the loop, SplitBB +/// is the new loop exit block, and DestBB is the old loop exit, now the +/// successor of SplitBB. +static void CreatePHIsForSplitLoopExit(SmallVectorImpl &Preds, + BasicBlock *SplitBB, + BasicBlock *DestBB) { + // SplitBB shouldn't have anything non-trivial in it yet. + assert(SplitBB->getFirstNonPHI() == SplitBB->getTerminator() && + "SplitBB has non-PHI nodes!"); + + // For each PHI in the destination block... + for (BasicBlock::iterator I = DestBB->begin(); + PHINode *PN = dyn_cast(I); ++I) { + unsigned Idx = PN->getBasicBlockIndex(SplitBB); + Value *V = PN->getIncomingValue(Idx); + // If the input is a PHI which already satisfies LCSSA, don't create + // a new one. + if (const PHINode *VP = dyn_cast(V)) + if (VP->getParent() == SplitBB) + continue; + // Otherwise a new PHI is needed. Create one and populate it. + PHINode *NewPN = PHINode::Create(PN->getType(), "split", + SplitBB->getTerminator()); + for (unsigned i = 0, e = Preds.size(); i != e; ++i) + NewPN->addIncoming(V, Preds[i]); + // Update the original PHI. + PN->setIncomingValue(Idx, NewPN); + } +} + +/// SplitCriticalEdge - If this edge is a critical edge, insert a new node to +/// split the critical edge. This will update DominatorTree information if it +/// is available, thus calling this pass will not invalidate either of them. +/// This returns the new block if the edge was split, null otherwise. +/// +/// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the +/// specified successor will be merged into the same critical edge block. +/// This is most commonly interesting with switch instructions, which may +/// have many edges to any one destination. This ensures that all edges to that +/// dest go to one block instead of each going to a different block, but isn't +/// the standard definition of a "critical edge". +/// +/// It is invalid to call this function on a critical edge that starts at an +/// IndirectBrInst. Splitting these edges will almost always create an invalid +/// program because the address of the new block won't be the one that is jumped +/// to. +/// +BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, + Pass *P, bool MergeIdenticalEdges) { + if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0; + + assert(!isa(TI) && + "Cannot split critical edge from IndirectBrInst"); + 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"); - // Create our unconditional branch... - new BranchInst(DestBB, NewBB); + BasicBlock *NewBB = BasicBlock::Create(TI->getContext(), + TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); + // Create our unconditional branch. + 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. - // - for (BasicBlock::iterator I = DestBB->begin(); isa(I); ++I) { - PHINode *PN = cast(I); - // We no longer enter through TIBB, now we come in through NewBB. Revector - // exactly one entry in the PHI node that used to come from TIBB to come - // from NewBB. - int BBIdx = PN->getBasicBlockIndex(TIBB); - PN->setIncomingBlock(BBIdx, NewBB); + if (PHINode *APHI = dyn_cast(DestBB->begin())) { + // This conceptually does: + // foreach (PHINode *PN in DestBB) + // PN->setIncomingBlock(PN->getIncomingBlock(TIBB), NewBB); + // but is optimized for two cases. + + if (APHI->getNumIncomingValues() <= 8) { // Small # preds case. + unsigned BBIdx = 0; + for (BasicBlock::iterator I = DestBB->begin(); isa(I); ++I) { + // We no longer enter through TIBB, now we come in through NewBB. + // Revector exactly one entry in the PHI node that used to come from + // TIBB to come from NewBB. + PHINode *PN = cast(I); + + // Reuse the previous value of BBIdx if it lines up. In cases where we + // have multiple phi nodes with *lots* of predecessors, this is a speed + // win because we don't have to scan the PHI looking for TIBB. This + // happens because the BB list of PHI nodes are usually in the same + // order. + if (PN->getIncomingBlock(BBIdx) != TIBB) + BBIdx = PN->getBasicBlockIndex(TIBB); + PN->setIncomingBlock(BBIdx, NewBB); + } + } else { + // However, the foreach loop is slow for blocks with lots of predecessors + // because PHINode::getIncomingBlock is O(n) in # preds. Instead, walk + // the user list of TIBB to find the PHI nodes. + SmallPtrSet UpdatedPHIs; + + for (Value::use_iterator UI = TIBB->use_begin(), E = TIBB->use_end(); + UI != E; ) { + Value::use_iterator Use = UI++; + if (PHINode *PN = dyn_cast(*Use)) { + // Remove one entry from each PHI. + if (PN->getParent() == DestBB && UpdatedPHIs.insert(PN)) + PN->setOperand(Use.getOperandNo(), 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; - - // Now update analysis information. These are the analyses that we are - // currently capable of updating... - // - - // 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 (P == 0) return NewBB; + + DominatorTree *DT = P->getAnalysisIfAvailable(); + LoopInfo *LI = P->getAnalysisIfAvailable(); + ProfileInfo *PI = P->getAnalysisIfAvailable(); + + // If we have nothing to update, just return. + if (DT == 0 && LI == 0 && PI == 0) + return NewBB; - // Should we update ImmediateDominator information? - if (ImmediateDominators *ID = P->getAnalysisToUpdate()) { - // TIBB is the new immediate dominator for NewBB. NewBB doesn't dominate - // anything. - ID->addNewBlock(NewBB, TIBB); - } + // Now update analysis information. Since the only predecessor of NewBB is + // the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate + // anything, as there are other successors of DestBB. However, if all other + // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a + // loop header) then NewBB dominates DestBB. + SmallVector OtherPreds; - // Update the forest? - if (ETForest *EF = P->getAnalysisToUpdate()) - EF->addNewBlock(NewBB, TIBB); + // If there is a PHI in the block, loop over predecessors with it, which is + // faster than iterating pred_begin/end. + if (PHINode *PN = dyn_cast(DestBB->begin())) { + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + if (PN->getIncomingBlock(i) != NewBB) + OtherPreds.push_back(PN->getIncomingBlock(i)); + } else { + for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); + I != E; ++I) { + BasicBlock *P = *I; + if (P != NewBB) + OtherPreds.push_back(P); + } + } + bool NewBBDominatesDestBB = true; + // Should we update DominatorTree information? - if (DominatorTree *DT = P->getAnalysisToUpdate()) { - DominatorTree::Node *TINode = DT->getNode(TIBB); + if (DT) { + 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! - DT->createNewNode(NewBB, TINode); + if (TINode) { // Don't break unreachable code! + 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 (DomTreeNode *OPNode = DT->getNode(OtherPreds.back())) + NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode); + OtherPreds.pop_back(); + } + OtherPreds.clear(); + } + + // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it + // doesn't dominate anything. + if (NewBBDominatesDestBB) { + if (!DestBBNode) DestBBNode = DT->getNode(DestBB); + DT->changeImmediateDominator(DestBBNode, NewBBNode); + } + } } - // Should we update DominanceFrontier information? - if (DominanceFrontier *DF = P->getAnalysisToUpdate()) { - // Since the new block is dominated by its only predecessor TIBB, - // it cannot be in any block's dominance frontier. Its dominance - // frontier is {DestBB}. - DominanceFrontier::DomSetType NewDFSet; - NewDFSet.insert(DestBB); - DF->addBasicBlock(NewBB, NewDFSet); - } - // Update LoopInfo if it is around. - if (LoopInfo *LI = P->getAnalysisToUpdate()) { - // 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 (LI) { + if (Loop *TIL = LI->getLoopFor(TIBB)) { + // 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 *DestLoop = LI->getLoopFor(DestBB)) { if (TIL == DestLoop) { // Both in the same loop, the NewBB joins loop. - DestLoop->addBasicBlockToLoop(NewBB, *LI); - } else if (TIL->contains(DestLoop->getHeader())) { - // Edge from an outer loop to an inner loop. Add to the outer lopo. - TIL->addBasicBlockToLoop(NewBB, *LI); - } else if (DestLoop->contains(TIL->getHeader())) { - // Edge from an inner loop to an outer loop. Add to the outer lopo. - DestLoop->addBasicBlockToLoop(NewBB, *LI); + DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); + } else if (TIL->contains(DestLoop)) { + // Edge from an outer loop to an inner loop. Add to the outer loop. + TIL->addBasicBlockToLoop(NewBB, LI->getBase()); + } else if (DestLoop->contains(TIL)) { + // Edge from an inner loop to an outer loop. Add to the outer loop. + 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 @@ -203,10 +339,69 @@ 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()); } } - + // If TIBB is in a loop and DestBB is outside of that loop, split the + // other exit blocks of the loop that also have predecessors outside + // the loop, to maintain a LoopSimplify guarantee. + if (!TIL->contains(DestBB) && + P->mustPreserveAnalysisID(LoopSimplifyID)) { + assert(!TIL->contains(NewBB) && + "Split point for loop exit is contained in loop!"); + + // Update LCSSA form in the newly created exit block. + if (P->mustPreserveAnalysisID(LCSSAID)) { + SmallVector OrigPred; + OrigPred.push_back(TIBB); + CreatePHIsForSplitLoopExit(OrigPred, NewBB, DestBB); + } + + // For each unique exit block... + SmallVector ExitBlocks; + TIL->getExitBlocks(ExitBlocks); + for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { + // Collect all the preds that are inside the loop, and note + // whether there are any preds outside the loop. + SmallVector Preds; + bool HasPredOutsideOfLoop = false; + BasicBlock *Exit = ExitBlocks[i]; + for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); + I != E; ++I) { + BasicBlock *P = *I; + if (TIL->contains(P)) + Preds.push_back(P); + else + HasPredOutsideOfLoop = true; + } + // If there are any preds not in the loop, we'll need to split + // the edges. The Preds.empty() check is needed because a block + // may appear multiple times in the list. We can't use + // getUniqueExitBlocks above because that depends on LoopSimplify + // form, which we're in the process of restoring! + if (!Preds.empty() && HasPredOutsideOfLoop) { + BasicBlock *NewExitBB = + SplitBlockPredecessors(Exit, Preds.data(), Preds.size(), + "split", P); + if (P->mustPreserveAnalysisID(LCSSAID)) + CreatePHIsForSplitLoopExit(Preds, NewExitBB, Exit); + } + } + } + // LCSSA form was updated above for the case where LoopSimplify is + // available, which means that all predecessors of loop exit blocks + // are within the loop. Without LoopSimplify form, it would be + // necessary to insert a new phi. + assert((!P->mustPreserveAnalysisID(LCSSAID) || + P->mustPreserveAnalysisID(LoopSimplifyID)) && + "SplitCriticalEdge doesn't know how to update LCCSA form " + "without LoopSimplify!"); + } } - return true; + + // Update ProfileInfo if it is around. + if (PI) + PI->splitEdge(TIBB, DestBB, NewBB, MergeIdenticalEdges); + + return NewBB; }