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