1 //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // BreakCriticalEdges pass - Break all of the critical edges in the CFG by 11 // inserting a dummy basic block. This pass may be "required" by passes that 12 // cannot deal with critical edges. For this usage, the structure type is 13 // forward declared. This pass obviously invalidates the CFG, but can update 14 // dominator trees. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #define DEBUG_TYPE "break-crit-edges" 19 #include "llvm/Transforms/Scalar.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/ADT/Statistic.h" 22 #include "llvm/Analysis/Dominators.h" 23 #include "llvm/Analysis/LoopInfo.h" 24 #include "llvm/Analysis/ProfileInfo.h" 25 #include "llvm/IR/Function.h" 26 #include "llvm/IR/Instructions.h" 27 #include "llvm/IR/Type.h" 28 #include "llvm/Support/CFG.h" 29 #include "llvm/Support/ErrorHandling.h" 30 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 31 using namespace llvm; 32 33 STATISTIC(NumBroken, "Number of blocks inserted"); 34 35 namespace { 36 struct BreakCriticalEdges : public FunctionPass { 37 static char ID; // Pass identification, replacement for typeid 38 BreakCriticalEdges() : FunctionPass(ID) { 39 initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry()); 40 } 41 42 virtual bool runOnFunction(Function &F); 43 44 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 45 AU.addPreserved<DominatorTree>(); 46 AU.addPreserved<LoopInfo>(); 47 AU.addPreserved<ProfileInfo>(); 48 49 // No loop canonicalization guarantees are broken by this pass. 50 AU.addPreservedID(LoopSimplifyID); 51 } 52 }; 53 } 54 55 char BreakCriticalEdges::ID = 0; 56 INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges", 57 "Break critical edges in CFG", false, false) 58 59 // Publicly exposed interface to pass... 60 char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID; 61 FunctionPass *llvm::createBreakCriticalEdgesPass() { 62 return new BreakCriticalEdges(); 63 } 64 65 // runOnFunction - Loop over all of the edges in the CFG, breaking critical 66 // edges as they are found. 67 // 68 bool BreakCriticalEdges::runOnFunction(Function &F) { 69 bool Changed = false; 70 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 71 TerminatorInst *TI = I->getTerminator(); 72 if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI)) 73 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 74 if (SplitCriticalEdge(TI, i, this)) { 75 ++NumBroken; 76 Changed = true; 77 } 78 } 79 80 return Changed; 81 } 82 83 //===----------------------------------------------------------------------===// 84 // Implementation of the external critical edge manipulation functions 85 //===----------------------------------------------------------------------===// 86 87 // isCriticalEdge - Return true if the specified edge is a critical edge. 88 // Critical edges are edges from a block with multiple successors to a block 89 // with multiple predecessors. 90 // 91 bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, 92 bool AllowIdenticalEdges) { 93 assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); 94 if (TI->getNumSuccessors() == 1) return false; 95 96 const BasicBlock *Dest = TI->getSuccessor(SuccNum); 97 const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest); 98 99 // If there is more than one predecessor, this is a critical edge... 100 assert(I != E && "No preds, but we have an edge to the block?"); 101 const BasicBlock *FirstPred = *I; 102 ++I; // Skip one edge due to the incoming arc from TI. 103 if (!AllowIdenticalEdges) 104 return I != E; 105 106 // If AllowIdenticalEdges is true, then we allow this edge to be considered 107 // non-critical iff all preds come from TI's block. 108 while (I != E) { 109 const BasicBlock *P = *I; 110 if (P != FirstPred) 111 return true; 112 // Note: leave this as is until no one ever compiles with either gcc 4.0.1 113 // or Xcode 2. This seems to work around the pred_iterator assert in PR 2207 114 E = pred_end(P); 115 ++I; 116 } 117 return false; 118 } 119 120 /// createPHIsForSplitLoopExit - When a loop exit edge is split, LCSSA form 121 /// may require new PHIs in the new exit block. This function inserts the 122 /// new PHIs, as needed. Preds is a list of preds inside the loop, SplitBB 123 /// is the new loop exit block, and DestBB is the old loop exit, now the 124 /// successor of SplitBB. 125 static void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds, 126 BasicBlock *SplitBB, 127 BasicBlock *DestBB) { 128 // SplitBB shouldn't have anything non-trivial in it yet. 129 assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() || 130 SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!"); 131 132 // For each PHI in the destination block. 133 for (BasicBlock::iterator I = DestBB->begin(); 134 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 135 unsigned Idx = PN->getBasicBlockIndex(SplitBB); 136 Value *V = PN->getIncomingValue(Idx); 137 138 // If the input is a PHI which already satisfies LCSSA, don't create 139 // a new one. 140 if (const PHINode *VP = dyn_cast<PHINode>(V)) 141 if (VP->getParent() == SplitBB) 142 continue; 143 144 // Otherwise a new PHI is needed. Create one and populate it. 145 PHINode *NewPN = 146 PHINode::Create(PN->getType(), Preds.size(), "split", 147 SplitBB->isLandingPad() ? 148 SplitBB->begin() : SplitBB->getTerminator()); 149 for (unsigned i = 0, e = Preds.size(); i != e; ++i) 150 NewPN->addIncoming(V, Preds[i]); 151 152 // Update the original PHI. 153 PN->setIncomingValue(Idx, NewPN); 154 } 155 } 156 157 /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to 158 /// split the critical edge. This will update DominatorTree information if it 159 /// is available, thus calling this pass will not invalidate either of them. 160 /// This returns the new block if the edge was split, null otherwise. 161 /// 162 /// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the 163 /// specified successor will be merged into the same critical edge block. 164 /// This is most commonly interesting with switch instructions, which may 165 /// have many edges to any one destination. This ensures that all edges to that 166 /// dest go to one block instead of each going to a different block, but isn't 167 /// the standard definition of a "critical edge". 168 /// 169 /// It is invalid to call this function on a critical edge that starts at an 170 /// IndirectBrInst. Splitting these edges will almost always create an invalid 171 /// program because the address of the new block won't be the one that is jumped 172 /// to. 173 /// 174 BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, 175 Pass *P, bool MergeIdenticalEdges, 176 bool DontDeleteUselessPhis, 177 bool SplitLandingPads) { 178 if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0; 179 180 assert(!isa<IndirectBrInst>(TI) && 181 "Cannot split critical edge from IndirectBrInst"); 182 183 BasicBlock *TIBB = TI->getParent(); 184 BasicBlock *DestBB = TI->getSuccessor(SuccNum); 185 186 // Splitting the critical edge to a landing pad block is non-trivial. Don't do 187 // it in this generic function. 188 if (DestBB->isLandingPad()) return 0; 189 190 // Create a new basic block, linking it into the CFG. 191 BasicBlock *NewBB = BasicBlock::Create(TI->getContext(), 192 TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); 193 // Create our unconditional branch. 194 BranchInst *NewBI = BranchInst::Create(DestBB, NewBB); 195 NewBI->setDebugLoc(TI->getDebugLoc()); 196 197 // Branch to the new block, breaking the edge. 198 TI->setSuccessor(SuccNum, NewBB); 199 200 // Insert the block into the function... right after the block TI lives in. 201 Function &F = *TIBB->getParent(); 202 Function::iterator FBBI = TIBB; 203 F.getBasicBlockList().insert(++FBBI, NewBB); 204 205 // If there are any PHI nodes in DestBB, we need to update them so that they 206 // merge incoming values from NewBB instead of from TIBB. 207 { 208 unsigned BBIdx = 0; 209 for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { 210 // We no longer enter through TIBB, now we come in through NewBB. 211 // Revector exactly one entry in the PHI node that used to come from 212 // TIBB to come from NewBB. 213 PHINode *PN = cast<PHINode>(I); 214 215 // Reuse the previous value of BBIdx if it lines up. In cases where we 216 // have multiple phi nodes with *lots* of predecessors, this is a speed 217 // win because we don't have to scan the PHI looking for TIBB. This 218 // happens because the BB list of PHI nodes are usually in the same 219 // order. 220 if (PN->getIncomingBlock(BBIdx) != TIBB) 221 BBIdx = PN->getBasicBlockIndex(TIBB); 222 PN->setIncomingBlock(BBIdx, NewBB); 223 } 224 } 225 226 // If there are any other edges from TIBB to DestBB, update those to go 227 // through the split block, making those edges non-critical as well (and 228 // reducing the number of phi entries in the DestBB if relevant). 229 if (MergeIdenticalEdges) { 230 for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) { 231 if (TI->getSuccessor(i) != DestBB) continue; 232 233 // Remove an entry for TIBB from DestBB phi nodes. 234 DestBB->removePredecessor(TIBB, DontDeleteUselessPhis); 235 236 // We found another edge to DestBB, go to NewBB instead. 237 TI->setSuccessor(i, NewBB); 238 } 239 } 240 241 242 243 // If we don't have a pass object, we can't update anything... 244 if (P == 0) return NewBB; 245 246 DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>(); 247 LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>(); 248 ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>(); 249 250 // If we have nothing to update, just return. 251 if (DT == 0 && LI == 0 && PI == 0) 252 return NewBB; 253 254 // Now update analysis information. Since the only predecessor of NewBB is 255 // the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate 256 // anything, as there are other successors of DestBB. However, if all other 257 // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a 258 // loop header) then NewBB dominates DestBB. 259 SmallVector<BasicBlock*, 8> OtherPreds; 260 261 // If there is a PHI in the block, loop over predecessors with it, which is 262 // faster than iterating pred_begin/end. 263 if (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 264 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 265 if (PN->getIncomingBlock(i) != NewBB) 266 OtherPreds.push_back(PN->getIncomingBlock(i)); 267 } else { 268 for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); 269 I != E; ++I) { 270 BasicBlock *P = *I; 271 if (P != NewBB) 272 OtherPreds.push_back(P); 273 } 274 } 275 276 bool NewBBDominatesDestBB = true; 277 278 // Should we update DominatorTree information? 279 if (DT) { 280 DomTreeNode *TINode = DT->getNode(TIBB); 281 282 // The new block is not the immediate dominator for any other nodes, but 283 // TINode is the immediate dominator for the new node. 284 // 285 if (TINode) { // Don't break unreachable code! 286 DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB); 287 DomTreeNode *DestBBNode = 0; 288 289 // If NewBBDominatesDestBB hasn't been computed yet, do so with DT. 290 if (!OtherPreds.empty()) { 291 DestBBNode = DT->getNode(DestBB); 292 while (!OtherPreds.empty() && NewBBDominatesDestBB) { 293 if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back())) 294 NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode); 295 OtherPreds.pop_back(); 296 } 297 OtherPreds.clear(); 298 } 299 300 // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it 301 // doesn't dominate anything. 302 if (NewBBDominatesDestBB) { 303 if (!DestBBNode) DestBBNode = DT->getNode(DestBB); 304 DT->changeImmediateDominator(DestBBNode, NewBBNode); 305 } 306 } 307 } 308 309 // Update LoopInfo if it is around. 310 if (LI) { 311 if (Loop *TIL = LI->getLoopFor(TIBB)) { 312 // If one or the other blocks were not in a loop, the new block is not 313 // either, and thus LI doesn't need to be updated. 314 if (Loop *DestLoop = LI->getLoopFor(DestBB)) { 315 if (TIL == DestLoop) { 316 // Both in the same loop, the NewBB joins loop. 317 DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 318 } else if (TIL->contains(DestLoop)) { 319 // Edge from an outer loop to an inner loop. Add to the outer loop. 320 TIL->addBasicBlockToLoop(NewBB, LI->getBase()); 321 } else if (DestLoop->contains(TIL)) { 322 // Edge from an inner loop to an outer loop. Add to the outer loop. 323 DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 324 } else { 325 // Edge from two loops with no containment relation. Because these 326 // are natural loops, we know that the destination block must be the 327 // header of its loop (adding a branch into a loop elsewhere would 328 // create an irreducible loop). 329 assert(DestLoop->getHeader() == DestBB && 330 "Should not create irreducible loops!"); 331 if (Loop *P = DestLoop->getParentLoop()) 332 P->addBasicBlockToLoop(NewBB, LI->getBase()); 333 } 334 } 335 // If TIBB is in a loop and DestBB is outside of that loop, split the 336 // other exit blocks of the loop that also have predecessors outside 337 // the loop, to maintain a LoopSimplify guarantee. 338 if (!TIL->contains(DestBB) && 339 P->mustPreserveAnalysisID(LoopSimplifyID)) { 340 assert(!TIL->contains(NewBB) && 341 "Split point for loop exit is contained in loop!"); 342 343 // Update LCSSA form in the newly created exit block. 344 if (P->mustPreserveAnalysisID(LCSSAID)) 345 createPHIsForSplitLoopExit(TIBB, NewBB, DestBB); 346 347 // For each unique exit block... 348 // FIXME: This code is functionally equivalent to the corresponding 349 // loop in LoopSimplify. 350 SmallVector<BasicBlock *, 4> ExitBlocks; 351 TIL->getExitBlocks(ExitBlocks); 352 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 353 // Collect all the preds that are inside the loop, and note 354 // whether there are any preds outside the loop. 355 SmallVector<BasicBlock *, 4> Preds; 356 bool HasPredOutsideOfLoop = false; 357 BasicBlock *Exit = ExitBlocks[i]; 358 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); 359 I != E; ++I) { 360 BasicBlock *P = *I; 361 if (TIL->contains(P)) { 362 if (isa<IndirectBrInst>(P->getTerminator())) { 363 Preds.clear(); 364 break; 365 } 366 Preds.push_back(P); 367 } else { 368 HasPredOutsideOfLoop = true; 369 } 370 } 371 // If there are any preds not in the loop, we'll need to split 372 // the edges. The Preds.empty() check is needed because a block 373 // may appear multiple times in the list. We can't use 374 // getUniqueExitBlocks above because that depends on LoopSimplify 375 // form, which we're in the process of restoring! 376 if (!Preds.empty() && HasPredOutsideOfLoop) { 377 if (!Exit->isLandingPad()) { 378 BasicBlock *NewExitBB = 379 SplitBlockPredecessors(Exit, Preds, "split", P); 380 if (P->mustPreserveAnalysisID(LCSSAID)) 381 createPHIsForSplitLoopExit(Preds, NewExitBB, Exit); 382 } else if (SplitLandingPads) { 383 SmallVector<BasicBlock*, 8> NewBBs; 384 SplitLandingPadPredecessors(Exit, Preds, 385 ".split1", ".split2", 386 P, NewBBs); 387 if (P->mustPreserveAnalysisID(LCSSAID)) 388 createPHIsForSplitLoopExit(Preds, NewBBs[0], Exit); 389 } 390 } 391 } 392 } 393 // LCSSA form was updated above for the case where LoopSimplify is 394 // available, which means that all predecessors of loop exit blocks 395 // are within the loop. Without LoopSimplify form, it would be 396 // necessary to insert a new phi. 397 assert((!P->mustPreserveAnalysisID(LCSSAID) || 398 P->mustPreserveAnalysisID(LoopSimplifyID)) && 399 "SplitCriticalEdge doesn't know how to update LCCSA form " 400 "without LoopSimplify!"); 401 } 402 } 403 404 // Update ProfileInfo if it is around. 405 if (PI) 406 PI->splitEdge(TIBB, DestBB, NewBB, MergeIdenticalEdges); 407 408 return NewBB; 409 } 410
