LLVM API Documentation
00001 //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source 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 #include "llvm/Transforms/Scalar.h" 00020 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00021 #include "llvm/Analysis/Dominators.h" 00022 #include "llvm/Analysis/LoopInfo.h" 00023 #include "llvm/Function.h" 00024 #include "llvm/Instructions.h" 00025 #include "llvm/Type.h" 00026 #include "llvm/Support/CFG.h" 00027 #include "llvm/Support/Visibility.h" 00028 #include "llvm/ADT/Statistic.h" 00029 using namespace llvm; 00030 00031 namespace { 00032 Statistic<> NumBroken("break-crit-edges", "Number of blocks inserted"); 00033 00034 struct VISIBILITY_HIDDEN BreakCriticalEdges : public FunctionPass { 00035 virtual bool runOnFunction(Function &F); 00036 00037 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00038 AU.addPreserved<ETForest>(); 00039 AU.addPreserved<DominatorSet>(); 00040 AU.addPreserved<ImmediateDominators>(); 00041 AU.addPreserved<DominatorTree>(); 00042 AU.addPreserved<DominanceFrontier>(); 00043 AU.addPreserved<LoopInfo>(); 00044 00045 // No loop canonicalization guarantees are broken by this pass. 00046 AU.addPreservedID(LoopSimplifyID); 00047 } 00048 }; 00049 00050 RegisterOpt<BreakCriticalEdges> X("break-crit-edges", 00051 "Break critical edges in CFG"); 00052 } 00053 00054 // Publically exposed interface to pass... 00055 const PassInfo *llvm::BreakCriticalEdgesID = X.getPassInfo(); 00056 FunctionPass *llvm::createBreakCriticalEdgesPass() { 00057 return new BreakCriticalEdges(); 00058 } 00059 00060 // runOnFunction - Loop over all of the edges in the CFG, breaking critical 00061 // edges as they are found. 00062 // 00063 bool BreakCriticalEdges::runOnFunction(Function &F) { 00064 bool Changed = false; 00065 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 00066 TerminatorInst *TI = I->getTerminator(); 00067 if (TI->getNumSuccessors() > 1) 00068 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 00069 if (SplitCriticalEdge(TI, i, this)) { 00070 ++NumBroken; 00071 Changed = true; 00072 } 00073 } 00074 00075 return Changed; 00076 } 00077 00078 //===----------------------------------------------------------------------===// 00079 // Implementation of the external critical edge manipulation functions 00080 //===----------------------------------------------------------------------===// 00081 00082 // isCriticalEdge - Return true if the specified edge is a critical edge. 00083 // Critical edges are edges from a block with multiple successors to a block 00084 // with multiple predecessors. 00085 // 00086 bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) { 00087 assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); 00088 if (TI->getNumSuccessors() == 1) return false; 00089 00090 const BasicBlock *Dest = TI->getSuccessor(SuccNum); 00091 pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); 00092 00093 // If there is more than one predecessor, this is a critical edge... 00094 assert(I != E && "No preds, but we have an edge to the block?"); 00095 ++I; // Skip one edge due to the incoming arc from TI. 00096 return I != E; 00097 } 00098 00099 // SplitCriticalEdge - If this edge is a critical edge, insert a new node to 00100 // split the critical edge. This will update DominatorSet, ImmediateDominator, 00101 // DominatorTree, and DominatorFrontier information if it is available, thus 00102 // calling this pass will not invalidate either of them. This returns true if 00103 // the edge was split, false otherwise. 00104 // 00105 bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { 00106 if (!isCriticalEdge(TI, SuccNum)) return false; 00107 BasicBlock *TIBB = TI->getParent(); 00108 BasicBlock *DestBB = TI->getSuccessor(SuccNum); 00109 00110 // Create a new basic block, linking it into the CFG. 00111 BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." + 00112 DestBB->getName() + "_crit_edge"); 00113 // Create our unconditional branch... 00114 new BranchInst(DestBB, NewBB); 00115 00116 // Branch to the new block, breaking the edge... 00117 TI->setSuccessor(SuccNum, NewBB); 00118 00119 // Insert the block into the function... right after the block TI lives in. 00120 Function &F = *TIBB->getParent(); 00121 F.getBasicBlockList().insert(TIBB->getNext(), NewBB); 00122 00123 // If there are any PHI nodes in DestBB, we need to update them so that they 00124 // merge incoming values from NewBB instead of from TIBB. 00125 // 00126 for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { 00127 PHINode *PN = cast<PHINode>(I); 00128 // We no longer enter through TIBB, now we come in through NewBB. Revector 00129 // exactly one entry in the PHI node that used to come from TIBB to come 00130 // from NewBB. 00131 int BBIdx = PN->getBasicBlockIndex(TIBB); 00132 PN->setIncomingBlock(BBIdx, NewBB); 00133 } 00134 00135 // If we don't have a pass object, we can't update anything... 00136 if (P == 0) return true; 00137 00138 // Now update analysis information. These are the analyses that we are 00139 // currently capable of updating... 00140 // 00141 00142 // Should we update DominatorSet information? 00143 if (DominatorSet *DS = P->getAnalysisToUpdate<DominatorSet>()) { 00144 // The blocks that dominate the new one are the blocks that dominate TIBB 00145 // plus the new block itself. 00146 DominatorSet::DomSetType DomSet = DS->getDominators(TIBB); 00147 DomSet.insert(NewBB); // A block always dominates itself. 00148 DS->addBasicBlock(NewBB, DomSet); 00149 } 00150 00151 // Should we update ImmediateDominator information? 00152 if (ImmediateDominators *ID = P->getAnalysisToUpdate<ImmediateDominators>()) { 00153 // TIBB is the new immediate dominator for NewBB. NewBB doesn't dominate 00154 // anything. 00155 ID->addNewBlock(NewBB, TIBB); 00156 } 00157 00158 // Update the forest? 00159 if (ETForest *EF = P->getAnalysisToUpdate<ETForest>()) 00160 EF->addNewBlock(NewBB, TIBB); 00161 00162 // Should we update DominatorTree information? 00163 if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) { 00164 DominatorTree::Node *TINode = DT->getNode(TIBB); 00165 00166 // The new block is not the immediate dominator for any other nodes, but 00167 // TINode is the immediate dominator for the new node. 00168 // 00169 if (TINode) // Don't break unreachable code! 00170 DT->createNewNode(NewBB, TINode); 00171 } 00172 00173 // Should we update DominanceFrontier information? 00174 if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) { 00175 // Since the new block is dominated by its only predecessor TIBB, 00176 // it cannot be in any block's dominance frontier. Its dominance 00177 // frontier is {DestBB}. 00178 DominanceFrontier::DomSetType NewDFSet; 00179 NewDFSet.insert(DestBB); 00180 DF->addBasicBlock(NewBB, NewDFSet); 00181 } 00182 00183 // Update LoopInfo if it is around. 00184 if (LoopInfo *LI = P->getAnalysisToUpdate<LoopInfo>()) { 00185 // If one or the other blocks were not in a loop, the new block is not 00186 // either, and thus LI doesn't need to be updated. 00187 if (Loop *TIL = LI->getLoopFor(TIBB)) 00188 if (Loop *DestLoop = LI->getLoopFor(DestBB)) { 00189 if (TIL == DestLoop) { 00190 // Both in the same loop, the NewBB joins loop. 00191 DestLoop->addBasicBlockToLoop(NewBB, *LI); 00192 } else if (TIL->contains(DestLoop->getHeader())) { 00193 // Edge from an outer loop to an inner loop. Add to the outer lopo. 00194 TIL->addBasicBlockToLoop(NewBB, *LI); 00195 } else if (DestLoop->contains(TIL->getHeader())) { 00196 // Edge from an inner loop to an outer loop. Add to the outer lopo. 00197 DestLoop->addBasicBlockToLoop(NewBB, *LI); 00198 } else { 00199 // Edge from two loops with no containment relation. Because these 00200 // are natural loops, we know that the destination block must be the 00201 // header of its loop (adding a branch into a loop elsewhere would 00202 // create an irreducible loop). 00203 assert(DestLoop->getHeader() == DestBB && 00204 "Should not create irreducible loops!"); 00205 if (Loop *P = DestLoop->getParentLoop()) 00206 P->addBasicBlockToLoop(NewBB, *LI); 00207 } 00208 } 00209 00210 } 00211 return true; 00212 }