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