X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FBreakCriticalEdges.cpp;h=616b066b5ab140543399a0cd1f5049a7e0790ef6;hb=2bc2a08b1bf6b5dcbfa515acc85999d6f884ec1a;hp=d683a2c5aaec1e54316041b3b4bcb941d388a017;hpb=f5a86f45e75ec744c203270ffa03659eb0a220c1;p=oota-llvm.git diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp index d683a2c5aae..616b066b5ab 100644 --- a/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -11,8 +11,7 @@ // 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. // //===----------------------------------------------------------------------===// @@ -36,13 +35,14 @@ STATISTIC(NumBroken, "Number of blocks inserted"); namespace { struct BreakCriticalEdges : public FunctionPass { static char ID; // Pass identification, replacement for typeid - BreakCriticalEdges() : FunctionPass(&ID) {} + BreakCriticalEdges() : FunctionPass(ID) { + initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry()); + } virtual bool runOnFunction(Function &F); virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved(); - AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -53,11 +53,11 @@ namespace { } char BreakCriticalEdges::ID = 0; -static RegisterPass -X("break-crit-edges", "Break critical edges in CFG"); +INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges", + "Break critical edges in CFG", false, false) // Publically exposed interface to pass... -const PassInfo *const llvm::BreakCriticalEdgesID = &X; +char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID; FunctionPass *llvm::createBreakCriticalEdgesPass() { return new BreakCriticalEdges(); } @@ -69,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; @@ -94,7 +94,7 @@ bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, 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?"); @@ -106,11 +106,12 @@ bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, // 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) + 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(*I); + E = pred_end(P); ++I; } return false; @@ -149,22 +150,36 @@ static void CreatePHIsForSplitLoopExit(SmallVectorImpl &Preds, } /// 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. -// +/// 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 = BasicBlock::Create(TI->getContext(), TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); - // Create our unconditional branch... + // Create our unconditional branch. BranchInst::Create(DestBB, NewBB); // Branch to the new block, breaking the edge. @@ -177,16 +192,47 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, // 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). @@ -206,6 +252,14 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, // If we don't have a pass object, we can't update anything... 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; // Now update analysis information. Since the only predecessor of NewBB is // the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate @@ -214,14 +268,25 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, // loop header) then NewBB dominates DestBB. SmallVector OtherPreds; - for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E; ++I) - if (*I != NewBB) - OtherPreds.push_back(*I); - + // 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->getAnalysisIfAvailable()) { + if (DT) { DomTreeNode *TINode = DT->getNode(TIBB); // The new block is not the immediate dominator for any other nodes, but @@ -251,42 +316,8 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, } } - // Should we update DominanceFrontier information? - if (DominanceFrontier *DF = P->getAnalysisIfAvailable()) { - // If NewBBDominatesDestBB hasn't been computed yet, do so with DF. - if (!OtherPreds.empty()) { - // FIXME: IMPLEMENT THIS! - llvm_unreachable("Requiring domfrontiers but not idom/domtree/domset." - " not implemented yet!"); - } - - // Since the new block is dominated by its only predecessor TIBB, - // it cannot be in any block's dominance frontier. If NewBB dominates - // DestBB, its dominance frontier is the same as DestBB's, otherwise it is - // just {DestBB}. - DominanceFrontier::DomSetType NewDFSet; - if (NewBBDominatesDestBB) { - DominanceFrontier::iterator I = DF->find(DestBB); - 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 { - DominanceFrontier::DomSetType NewDFSet; - NewDFSet.insert(DestBB); - DF->addBasicBlock(NewBB, NewDFSet); - } - } - // Update LoopInfo if it is around. - if (LoopInfo *LI = P->getAnalysisIfAvailable()) { + 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. @@ -294,10 +325,10 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, if (TIL == DestLoop) { // Both in the same loop, the NewBB joins loop. DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); - } else if (TIL->contains(DestLoop->getHeader())) { + } 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->getHeader())) { + } 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 { @@ -336,11 +367,13 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, bool HasPredOutsideOfLoop = false; BasicBlock *Exit = ExitBlocks[i]; for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); - I != E; ++I) - if (TIL->contains(*I)) - Preds.push_back(*I); + 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 @@ -367,9 +400,8 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, } // Update ProfileInfo if it is around. - if (ProfileInfo *PI = P->getAnalysisIfAvailable()) { - PI->splitEdge(TIBB,DestBB,NewBB,MergeIdenticalEdges); - } + if (PI) + PI->splitEdge(TIBB, DestBB, NewBB, MergeIdenticalEdges); return NewBB; }