LLVM API Documentation
00001 //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // BreakCriticalEdges pass - Break all of the critical edges in the CFG by 00011 // inserting a dummy basic block. This pass may be "required" by passes that 00012 // cannot deal with critical edges. For this usage, the structure type is 00013 // forward declared. This pass obviously invalidates the CFG, but can update 00014 // forward dominator (set, immediate dominators, tree, and frontier) 00015 // information. 00016 // 00017 //===----------------------------------------------------------------------===// 00018 00019 #define DEBUG_TYPE "break-crit-edges" 00020 #include "llvm/Transforms/Scalar.h" 00021 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00022 #include "llvm/Analysis/Dominators.h" 00023 #include "llvm/Analysis/LoopInfo.h" 00024 #include "llvm/Function.h" 00025 #include "llvm/Instructions.h" 00026 #include "llvm/Type.h" 00027 #include "llvm/Support/CFG.h" 00028 #include "llvm/Support/Compiler.h" 00029 #include "llvm/Support/ErrorHandling.h" 00030 #include "llvm/ADT/SmallVector.h" 00031 #include "llvm/ADT/Statistic.h" 00032 using namespace llvm; 00033 00034 STATISTIC(NumBroken, "Number of blocks inserted"); 00035 00036 namespace { 00037 struct VISIBILITY_HIDDEN BreakCriticalEdges : public FunctionPass { 00038 static char ID; // Pass identification, replacement for typeid 00039 BreakCriticalEdges() : FunctionPass(&ID) {} 00040 00041 virtual bool runOnFunction(Function &F); 00042 00043 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00044 AU.addPreserved<DominatorTree>(); 00045 AU.addPreserved<DominanceFrontier>(); 00046 AU.addPreserved<LoopInfo>(); 00047 00048 // No loop canonicalization guarantees are broken by this pass. 00049 AU.addPreservedID(LoopSimplifyID); 00050 } 00051 }; 00052 } 00053 00054 char BreakCriticalEdges::ID = 0; 00055 static RegisterPass<BreakCriticalEdges> 00056 X("break-crit-edges", "Break critical edges in CFG"); 00057 00058 // Publically exposed interface to pass... 00059 const PassInfo *const llvm::BreakCriticalEdgesID = &X; 00060 FunctionPass *llvm::createBreakCriticalEdgesPass() { 00061 return new BreakCriticalEdges(); 00062 } 00063 00064 // runOnFunction - Loop over all of the edges in the CFG, breaking critical 00065 // edges as they are found. 00066 // 00067 bool BreakCriticalEdges::runOnFunction(Function &F) { 00068 bool Changed = false; 00069 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 00070 TerminatorInst *TI = I->getTerminator(); 00071 if (TI->getNumSuccessors() > 1) 00072 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 00073 if (SplitCriticalEdge(TI, i, this)) { 00074 ++NumBroken; 00075 Changed = true; 00076 } 00077 } 00078 00079 return Changed; 00080 } 00081 00082 //===----------------------------------------------------------------------===// 00083 // Implementation of the external critical edge manipulation functions 00084 //===----------------------------------------------------------------------===// 00085 00086 // isCriticalEdge - Return true if the specified edge is a critical edge. 00087 // Critical edges are edges from a block with multiple successors to a block 00088 // with multiple predecessors. 00089 // 00090 bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, 00091 bool AllowIdenticalEdges) { 00092 assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); 00093 if (TI->getNumSuccessors() == 1) return false; 00094 00095 const BasicBlock *Dest = TI->getSuccessor(SuccNum); 00096 pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); 00097 00098 // If there is more than one predecessor, this is a critical edge... 00099 assert(I != E && "No preds, but we have an edge to the block?"); 00100 const BasicBlock *FirstPred = *I; 00101 ++I; // Skip one edge due to the incoming arc from TI. 00102 if (!AllowIdenticalEdges) 00103 return I != E; 00104 00105 // If AllowIdenticalEdges is true, then we allow this edge to be considered 00106 // non-critical iff all preds come from TI's block. 00107 while (I != E) { 00108 if (*I != FirstPred) 00109 return true; 00110 // Note: leave this as is until no one ever compiles with either gcc 4.0.1 00111 // or Xcode 2. This seems to work around the pred_iterator assert in PR 2207 00112 E = pred_end(*I); 00113 ++I; 00114 } 00115 return false; 00116 } 00117 00118 /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to 00119 /// split the critical edge. This will update DominatorTree and 00120 /// DominatorFrontier information if it is available, thus calling this pass 00121 /// will not invalidate any of them. This returns true if the edge was split, 00122 /// false otherwise. This ensures that all edges to that dest go to one block 00123 /// instead of each going to a different block. 00124 // 00125 bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P, 00126 bool MergeIdenticalEdges) { 00127 if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return false; 00128 BasicBlock *TIBB = TI->getParent(); 00129 BasicBlock *DestBB = TI->getSuccessor(SuccNum); 00130 00131 // Create a new basic block, linking it into the CFG. 00132 BasicBlock *NewBB = BasicBlock::Create(TI->getContext(), 00133 TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); 00134 // Create our unconditional branch... 00135 BranchInst::Create(DestBB, NewBB); 00136 00137 // Branch to the new block, breaking the edge. 00138 TI->setSuccessor(SuccNum, NewBB); 00139 00140 // Insert the block into the function... right after the block TI lives in. 00141 Function &F = *TIBB->getParent(); 00142 Function::iterator FBBI = TIBB; 00143 F.getBasicBlockList().insert(++FBBI, NewBB); 00144 00145 // If there are any PHI nodes in DestBB, we need to update them so that they 00146 // merge incoming values from NewBB instead of from TIBB. 00147 // 00148 for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { 00149 PHINode *PN = cast<PHINode>(I); 00150 // We no longer enter through TIBB, now we come in through NewBB. Revector 00151 // exactly one entry in the PHI node that used to come from TIBB to come 00152 // from NewBB. 00153 int BBIdx = PN->getBasicBlockIndex(TIBB); 00154 PN->setIncomingBlock(BBIdx, NewBB); 00155 } 00156 00157 // If there are any other edges from TIBB to DestBB, update those to go 00158 // through the split block, making those edges non-critical as well (and 00159 // reducing the number of phi entries in the DestBB if relevant). 00160 if (MergeIdenticalEdges) { 00161 for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) { 00162 if (TI->getSuccessor(i) != DestBB) continue; 00163 00164 // Remove an entry for TIBB from DestBB phi nodes. 00165 DestBB->removePredecessor(TIBB); 00166 00167 // We found another edge to DestBB, go to NewBB instead. 00168 TI->setSuccessor(i, NewBB); 00169 } 00170 } 00171 00172 00173 00174 // If we don't have a pass object, we can't update anything... 00175 if (P == 0) return true; 00176 00177 // Now update analysis information. Since the only predecessor of NewBB is 00178 // the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate 00179 // anything, as there are other successors of DestBB. However, if all other 00180 // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a 00181 // loop header) then NewBB dominates DestBB. 00182 SmallVector<BasicBlock*, 8> OtherPreds; 00183 00184 for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E; ++I) 00185 if (*I != NewBB) 00186 OtherPreds.push_back(*I); 00187 00188 bool NewBBDominatesDestBB = true; 00189 00190 // Should we update DominatorTree information? 00191 if (DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>()) { 00192 DomTreeNode *TINode = DT->getNode(TIBB); 00193 00194 // The new block is not the immediate dominator for any other nodes, but 00195 // TINode is the immediate dominator for the new node. 00196 // 00197 if (TINode) { // Don't break unreachable code! 00198 DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB); 00199 DomTreeNode *DestBBNode = 0; 00200 00201 // If NewBBDominatesDestBB hasn't been computed yet, do so with DT. 00202 if (!OtherPreds.empty()) { 00203 DestBBNode = DT->getNode(DestBB); 00204 while (!OtherPreds.empty() && NewBBDominatesDestBB) { 00205 if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back())) 00206 NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode); 00207 OtherPreds.pop_back(); 00208 } 00209 OtherPreds.clear(); 00210 } 00211 00212 // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it 00213 // doesn't dominate anything. 00214 if (NewBBDominatesDestBB) { 00215 if (!DestBBNode) DestBBNode = DT->getNode(DestBB); 00216 DT->changeImmediateDominator(DestBBNode, NewBBNode); 00217 } 00218 } 00219 } 00220 00221 // Should we update DominanceFrontier information? 00222 if (DominanceFrontier *DF = P->getAnalysisIfAvailable<DominanceFrontier>()) { 00223 // If NewBBDominatesDestBB hasn't been computed yet, do so with DF. 00224 if (!OtherPreds.empty()) { 00225 // FIXME: IMPLEMENT THIS! 00226 llvm_unreachable("Requiring domfrontiers but not idom/domtree/domset." 00227 " not implemented yet!"); 00228 } 00229 00230 // Since the new block is dominated by its only predecessor TIBB, 00231 // it cannot be in any block's dominance frontier. If NewBB dominates 00232 // DestBB, its dominance frontier is the same as DestBB's, otherwise it is 00233 // just {DestBB}. 00234 DominanceFrontier::DomSetType NewDFSet; 00235 if (NewBBDominatesDestBB) { 00236 DominanceFrontier::iterator I = DF->find(DestBB); 00237 if (I != DF->end()) { 00238 DF->addBasicBlock(NewBB, I->second); 00239 00240 if (I->second.count(DestBB)) { 00241 // However NewBB's frontier does not include DestBB. 00242 DominanceFrontier::iterator NF = DF->find(NewBB); 00243 DF->removeFromFrontier(NF, DestBB); 00244 } 00245 } 00246 else 00247 DF->addBasicBlock(NewBB, DominanceFrontier::DomSetType()); 00248 } else { 00249 DominanceFrontier::DomSetType NewDFSet; 00250 NewDFSet.insert(DestBB); 00251 DF->addBasicBlock(NewBB, NewDFSet); 00252 } 00253 } 00254 00255 // Update LoopInfo if it is around. 00256 if (LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>()) { 00257 // If one or the other blocks were not in a loop, the new block is not 00258 // either, and thus LI doesn't need to be updated. 00259 if (Loop *TIL = LI->getLoopFor(TIBB)) 00260 if (Loop *DestLoop = LI->getLoopFor(DestBB)) { 00261 if (TIL == DestLoop) { 00262 // Both in the same loop, the NewBB joins loop. 00263 DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 00264 } else if (TIL->contains(DestLoop->getHeader())) { 00265 // Edge from an outer loop to an inner loop. Add to the outer loop. 00266 TIL->addBasicBlockToLoop(NewBB, LI->getBase()); 00267 } else if (DestLoop->contains(TIL->getHeader())) { 00268 // Edge from an inner loop to an outer loop. Add to the outer loop. 00269 DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 00270 } else { 00271 // Edge from two loops with no containment relation. Because these 00272 // are natural loops, we know that the destination block must be the 00273 // header of its loop (adding a branch into a loop elsewhere would 00274 // create an irreducible loop). 00275 assert(DestLoop->getHeader() == DestBB && 00276 "Should not create irreducible loops!"); 00277 if (Loop *P = DestLoop->getParentLoop()) 00278 P->addBasicBlockToLoop(NewBB, LI->getBase()); 00279 } 00280 } 00281 } 00282 return true; 00283 }