LoopSimplify.cpp revision b576c94c15af9a440f69d9d03c2afead7971118c
1//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass performs several transformations to transform natural loops into a 11// simpler form, which makes subsequent analyses and transformations simpler and 12// more effective. 13// 14// Loop pre-header insertion guarantees that there is a single, non-critical 15// entry edge from outside of the loop to the loop header. This simplifies a 16// number of analyses and transformations, such as LICM. 17// 18// Loop exit-block insertion guarantees that all exit blocks from the loop 19// (blocks which are outside of the loop that have predecessors inside of the 20// loop) are dominated by the loop header. This simplifies transformations such 21// as store-sinking that are built into LICM. 22// 23// This pass also guarantees that loops will have exactly one backedge. 24// 25// Note that the simplifycfg pass will clean up blocks which are split out but 26// end up being unnecessary, so usage of this pass should not pessimize 27// generated code. 28// 29// This pass obviously modifies the CFG, but updates loop information and 30// dominator information. 31// 32//===----------------------------------------------------------------------===// 33 34#include "llvm/Transforms/Scalar.h" 35#include "llvm/Analysis/Dominators.h" 36#include "llvm/Analysis/LoopInfo.h" 37#include "llvm/Function.h" 38#include "llvm/iTerminators.h" 39#include "llvm/iPHINode.h" 40#include "llvm/Constant.h" 41#include "llvm/Support/CFG.h" 42#include "Support/SetOperations.h" 43#include "Support/Statistic.h" 44#include "Support/DepthFirstIterator.h" 45 46namespace { 47 Statistic<> 48 NumInserted("loopsimplify", "Number of pre-header blocks inserted"); 49 50 struct LoopSimplify : public FunctionPass { 51 virtual bool runOnFunction(Function &F); 52 53 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 54 // We need loop information to identify the loops... 55 AU.addRequired<LoopInfo>(); 56 AU.addRequired<DominatorSet>(); 57 58 AU.addPreserved<LoopInfo>(); 59 AU.addPreserved<DominatorSet>(); 60 AU.addPreserved<ImmediateDominators>(); 61 AU.addPreserved<DominatorTree>(); 62 AU.addPreserved<DominanceFrontier>(); 63 AU.addPreservedID(BreakCriticalEdgesID); // No crit edges added.... 64 } 65 private: 66 bool ProcessLoop(Loop *L); 67 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix, 68 const std::vector<BasicBlock*> &Preds); 69 void RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 70 void InsertPreheaderForLoop(Loop *L); 71 void InsertUniqueBackedgeBlock(Loop *L); 72 73 void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 74 std::vector<BasicBlock*> &PredBlocks); 75 }; 76 77 RegisterOpt<LoopSimplify> 78 X("loopsimplify", "Canonicalize natural loops", true); 79} 80 81// Publically exposed interface to pass... 82const PassInfo *LoopSimplifyID = X.getPassInfo(); 83Pass *createLoopSimplifyPass() { return new LoopSimplify(); } 84 85 86/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 87/// it in any convenient order) inserting preheaders... 88/// 89bool LoopSimplify::runOnFunction(Function &F) { 90 bool Changed = false; 91 LoopInfo &LI = getAnalysis<LoopInfo>(); 92 93 for (unsigned i = 0, e = LI.getTopLevelLoops().size(); i != e; ++i) 94 Changed |= ProcessLoop(LI.getTopLevelLoops()[i]); 95 96 return Changed; 97} 98 99 100/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 101/// all loops have preheaders. 102/// 103bool LoopSimplify::ProcessLoop(Loop *L) { 104 bool Changed = false; 105 106 // Does the loop already have a preheader? If so, don't modify the loop... 107 if (L->getLoopPreheader() == 0) { 108 InsertPreheaderForLoop(L); 109 NumInserted++; 110 Changed = true; 111 } 112 113 // Regardless of whether or not we added a preheader to the loop we must 114 // guarantee that the preheader dominates all exit nodes. If there are any 115 // exit nodes not dominated, split them now. 116 DominatorSet &DS = getAnalysis<DominatorSet>(); 117 BasicBlock *Header = L->getHeader(); 118 for (unsigned i = 0, e = L->getExitBlocks().size(); i != e; ++i) 119 if (!DS.dominates(Header, L->getExitBlocks()[i])) { 120 RewriteLoopExitBlock(L, L->getExitBlocks()[i]); 121 assert(DS.dominates(Header, L->getExitBlocks()[i]) && 122 "RewriteLoopExitBlock failed?"); 123 NumInserted++; 124 Changed = true; 125 } 126 127 // The preheader may have more than two predecessors at this point (from the 128 // preheader and from the backedges). To simplify the loop more, insert an 129 // extra back-edge block in the loop so that there is exactly one backedge. 130 if (L->getNumBackEdges() != 1) { 131 InsertUniqueBackedgeBlock(L); 132 NumInserted++; 133 Changed = true; 134 } 135 136 const std::vector<Loop*> &SubLoops = L->getSubLoops(); 137 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 138 Changed |= ProcessLoop(SubLoops[i]); 139 return Changed; 140} 141 142/// SplitBlockPredecessors - Split the specified block into two blocks. We want 143/// to move the predecessors specified in the Preds list to point to the new 144/// block, leaving the remaining predecessors pointing to BB. This method 145/// updates the SSA PHINode's, but no other analyses. 146/// 147BasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB, 148 const char *Suffix, 149 const std::vector<BasicBlock*> &Preds) { 150 151 // Create new basic block, insert right before the original block... 152 BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB); 153 154 // The preheader first gets an unconditional branch to the loop header... 155 BranchInst *BI = new BranchInst(BB); 156 NewBB->getInstList().push_back(BI); 157 158 // For every PHI node in the block, insert a PHI node into NewBB where the 159 // incoming values from the out of loop edges are moved to NewBB. We have two 160 // possible cases here. If the loop is dead, we just insert dummy entries 161 // into the PHI nodes for the new edge. If the loop is not dead, we move the 162 // incoming edges in BB into new PHI nodes in NewBB. 163 // 164 if (!Preds.empty()) { // Is the loop not obviously dead? 165 for (BasicBlock::iterator I = BB->begin(); 166 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 167 168 // Create the new PHI node, insert it into NewBB at the end of the block 169 PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI); 170 171 // Move all of the edges from blocks outside the loop to the new PHI 172 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 173 Value *V = PN->removeIncomingValue(Preds[i]); 174 NewPHI->addIncoming(V, Preds[i]); 175 } 176 177 // Add an incoming value to the PHI node in the loop for the preheader 178 // edge 179 PN->addIncoming(NewPHI, NewBB); 180 } 181 182 // Now that the PHI nodes are updated, actually move the edges from 183 // Preds to point to NewBB instead of BB. 184 // 185 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 186 TerminatorInst *TI = Preds[i]->getTerminator(); 187 for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) 188 if (TI->getSuccessor(s) == BB) 189 TI->setSuccessor(s, NewBB); 190 } 191 192 } else { // Otherwise the loop is dead... 193 for (BasicBlock::iterator I = BB->begin(); 194 PHINode *PN = dyn_cast<PHINode>(I); ++I) 195 // Insert dummy values as the incoming value... 196 PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB); 197 } 198 return NewBB; 199} 200 201// ChangeExitBlock - This recursive function is used to change any exit blocks 202// that use OldExit to use NewExit instead. This is recursive because children 203// may need to be processed as well. 204// 205static void ChangeExitBlock(Loop *L, BasicBlock *OldExit, BasicBlock *NewExit) { 206 if (L->hasExitBlock(OldExit)) { 207 L->changeExitBlock(OldExit, NewExit); 208 const std::vector<Loop*> &SubLoops = L->getSubLoops(); 209 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 210 ChangeExitBlock(SubLoops[i], OldExit, NewExit); 211 } 212} 213 214 215/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 216/// preheader, this method is called to insert one. This method has two phases: 217/// preheader insertion and analysis updating. 218/// 219void LoopSimplify::InsertPreheaderForLoop(Loop *L) { 220 BasicBlock *Header = L->getHeader(); 221 222 // Compute the set of predecessors of the loop that are not in the loop. 223 std::vector<BasicBlock*> OutsideBlocks; 224 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 225 PI != PE; ++PI) 226 if (!L->contains(*PI)) // Coming in from outside the loop? 227 OutsideBlocks.push_back(*PI); // Keep track of it... 228 229 // Split out the loop pre-header 230 BasicBlock *NewBB = 231 SplitBlockPredecessors(Header, ".preheader", OutsideBlocks); 232 233 //===--------------------------------------------------------------------===// 234 // Update analysis results now that we have performed the transformation 235 // 236 237 // We know that we have loop information to update... update it now. 238 if (Loop *Parent = L->getParentLoop()) 239 Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 240 241 // If the header for the loop used to be an exit node for another loop, then 242 // we need to update this to know that the loop-preheader is now the exit 243 // node. Note that the only loop that could have our header as an exit node 244 // is a sibling loop, ie, one with the same parent loop, or one if it's 245 // children. 246 // 247 const std::vector<Loop*> *ParentSubLoops; 248 if (Loop *Parent = L->getParentLoop()) 249 ParentSubLoops = &Parent->getSubLoops(); 250 else // Must check top-level loops... 251 ParentSubLoops = &getAnalysis<LoopInfo>().getTopLevelLoops(); 252 253 // Loop over all sibling loops, performing the substitution (recursively to 254 // include child loops)... 255 for (unsigned i = 0, e = ParentSubLoops->size(); i != e; ++i) 256 ChangeExitBlock((*ParentSubLoops)[i], Header, NewBB); 257 258 DominatorSet &DS = getAnalysis<DominatorSet>(); // Update dominator info 259 { 260 // The blocks that dominate NewBB are the blocks that dominate Header, 261 // minus Header, plus NewBB. 262 DominatorSet::DomSetType DomSet = DS.getDominators(Header); 263 DomSet.insert(NewBB); // We dominate ourself 264 DomSet.erase(Header); // Header does not dominate us... 265 DS.addBasicBlock(NewBB, DomSet); 266 267 // The newly created basic block dominates all nodes dominated by Header. 268 for (Function::iterator I = Header->getParent()->begin(), 269 E = Header->getParent()->end(); I != E; ++I) 270 if (DS.dominates(Header, I)) 271 DS.addDominator(I, NewBB); 272 } 273 274 // Update immediate dominator information if we have it... 275 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 276 // Whatever i-dominated the header node now immediately dominates NewBB 277 ID->addNewBlock(NewBB, ID->get(Header)); 278 279 // The preheader now is the immediate dominator for the header node... 280 ID->setImmediateDominator(Header, NewBB); 281 } 282 283 // Update DominatorTree information if it is active. 284 if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 285 // The immediate dominator of the preheader is the immediate dominator of 286 // the old header. 287 // 288 DominatorTree::Node *HeaderNode = DT->getNode(Header); 289 DominatorTree::Node *PHNode = DT->createNewNode(NewBB, 290 HeaderNode->getIDom()); 291 292 // Change the header node so that PNHode is the new immediate dominator 293 DT->changeImmediateDominator(HeaderNode, PHNode); 294 } 295 296 // Update dominance frontier information... 297 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 298 // The DF(NewBB) is just (DF(Header)-Header), because NewBB dominates 299 // everything that Header does, and it strictly dominates Header in 300 // addition. 301 assert(DF->find(Header) != DF->end() && "Header node doesn't have DF set?"); 302 DominanceFrontier::DomSetType NewDFSet = DF->find(Header)->second; 303 NewDFSet.erase(Header); 304 DF->addBasicBlock(NewBB, NewDFSet); 305 306 // Now we must loop over all of the dominance frontiers in the function, 307 // replacing occurrences of Header with NewBB in some cases. If a block 308 // dominates a (now) predecessor of NewBB, but did not strictly dominate 309 // Header, it will have Header in it's DF set, but should now have NewBB in 310 // its set. 311 for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) { 312 // Get all of the dominators of the predecessor... 313 const DominatorSet::DomSetType &PredDoms = 314 DS.getDominators(OutsideBlocks[i]); 315 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 316 PDE = PredDoms.end(); PDI != PDE; ++PDI) { 317 BasicBlock *PredDom = *PDI; 318 // If the loop header is in DF(PredDom), then PredDom didn't dominate 319 // the header but did dominate a predecessor outside of the loop. Now 320 // we change this entry to include the preheader in the DF instead of 321 // the header. 322 DominanceFrontier::iterator DFI = DF->find(PredDom); 323 assert(DFI != DF->end() && "No dominance frontier for node?"); 324 if (DFI->second.count(Header)) { 325 DF->removeFromFrontier(DFI, Header); 326 DF->addToFrontier(DFI, NewBB); 327 } 328 } 329 } 330 } 331} 332 333void LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 334 DominatorSet &DS = getAnalysis<DominatorSet>(); 335 assert(!DS.dominates(L->getHeader(), Exit) && 336 "Loop already dominates exit block??"); 337 assert(std::find(L->getExitBlocks().begin(), L->getExitBlocks().end(), Exit) 338 != L->getExitBlocks().end() && "Not a current exit block!"); 339 340 std::vector<BasicBlock*> LoopBlocks; 341 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 342 if (L->contains(*I)) 343 LoopBlocks.push_back(*I); 344 345 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 346 BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks); 347 348 // Update Loop Information - we know that the new block will be in the parent 349 // loop of L. 350 if (Loop *Parent = L->getParentLoop()) 351 Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 352 353 // Replace any instances of Exit with NewBB in this and any nested loops... 354 for (df_iterator<Loop*> I = df_begin(L), E = df_end(L); I != E; ++I) 355 if (I->hasExitBlock(Exit)) 356 I->changeExitBlock(Exit, NewBB); // Update exit block information 357 358 // Update dominator information (set, immdom, domtree, and domfrontier) 359 UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks); 360} 361 362/// InsertUniqueBackedgeBlock - This method is called when the specified loop 363/// has more than one backedge in it. If this occurs, revector all of these 364/// backedges to target a new basic block and have that block branch to the loop 365/// header. This ensures that loops have exactly one backedge. 366/// 367void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) { 368 assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 369 370 // Get information about the loop 371 BasicBlock *Preheader = L->getLoopPreheader(); 372 BasicBlock *Header = L->getHeader(); 373 Function *F = Header->getParent(); 374 375 // Figure out which basic blocks contain back-edges to the loop header. 376 std::vector<BasicBlock*> BackedgeBlocks; 377 for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 378 if (*I != Preheader) BackedgeBlocks.push_back(*I); 379 380 // Create and insert the new backedge block... 381 BasicBlock *BEBlock = new BasicBlock(Header->getName()+".backedge", F); 382 Instruction *BETerminator = new BranchInst(Header); 383 BEBlock->getInstList().push_back(BETerminator); 384 385 // Move the new backedge block to right after the last backedge block. 386 Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 387 F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 388 389 // Now that the block has been inserted into the function, create PHI nodes in 390 // the backedge block which correspond to any PHI nodes in the header block. 391 for (BasicBlock::iterator I = Header->begin(); 392 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 393 PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".be", 394 BETerminator); 395 NewPN->op_reserve(2*BackedgeBlocks.size()); 396 397 // Loop over the PHI node, moving all entries except the one for the 398 // preheader over to the new PHI node. 399 unsigned PreheaderIdx = ~0U; 400 bool HasUniqueIncomingValue = true; 401 Value *UniqueValue = 0; 402 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 403 BasicBlock *IBB = PN->getIncomingBlock(i); 404 Value *IV = PN->getIncomingValue(i); 405 if (IBB == Preheader) { 406 PreheaderIdx = i; 407 } else { 408 NewPN->addIncoming(IV, IBB); 409 if (HasUniqueIncomingValue) { 410 if (UniqueValue == 0) 411 UniqueValue = IV; 412 else if (UniqueValue != IV) 413 HasUniqueIncomingValue = false; 414 } 415 } 416 } 417 418 // Delete all of the incoming values from the old PN except the preheader's 419 assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 420 if (PreheaderIdx != 0) { 421 PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 422 PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 423 } 424 PN->op_erase(PN->op_begin()+2, PN->op_end()); 425 426 // Finally, add the newly constructed PHI node as the entry for the BEBlock. 427 PN->addIncoming(NewPN, BEBlock); 428 429 // As an optimization, if all incoming values in the new PhiNode (which is a 430 // subset of the incoming values of the old PHI node) have the same value, 431 // eliminate the PHI Node. 432 if (HasUniqueIncomingValue) { 433 NewPN->replaceAllUsesWith(UniqueValue); 434 BEBlock->getInstList().erase(NewPN); 435 } 436 } 437 438 // Now that all of the PHI nodes have been inserted and adjusted, modify the 439 // backedge blocks to just to the BEBlock instead of the header. 440 for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 441 TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 442 for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 443 if (TI->getSuccessor(Op) == Header) 444 TI->setSuccessor(Op, BEBlock); 445 } 446 447 //===--- Update all analyses which we must preserve now -----------------===// 448 449 // Update Loop Information - we know that this block is now in the current 450 // loop and all parent loops. 451 L->addBasicBlockToLoop(BEBlock, getAnalysis<LoopInfo>()); 452 453 // Replace any instances of Exit with NewBB in this and any nested loops... 454 for (df_iterator<Loop*> I = df_begin(L), E = df_end(L); I != E; ++I) 455 if (I->hasExitBlock(Header)) 456 I->changeExitBlock(Header, BEBlock); // Update exit block information 457 458 // Update dominator information (set, immdom, domtree, and domfrontier) 459 UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks); 460} 461 462/// UpdateDomInfoForRevectoredPreds - This method is used to update the four 463/// different kinds of dominator information (dominator sets, immediate 464/// dominators, dominator trees, and dominance frontiers) after a new block has 465/// been added to the CFG. 466/// 467/// This only supports the case when an existing block (known as "Exit"), had 468/// some of its predecessors factored into a new basic block. This 469/// transformation inserts a new basic block ("NewBB"), with a single 470/// unconditional branch to Exit, and moves some predecessors of "Exit" to now 471/// branch to NewBB. These predecessors are listed in PredBlocks, even though 472/// they are the same as pred_begin(NewBB)/pred_end(NewBB). 473/// 474void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 475 std::vector<BasicBlock*> &PredBlocks) { 476 assert(succ_begin(NewBB) != succ_end(NewBB) && 477 ++succ_begin(NewBB) == succ_end(NewBB) && 478 "NewBB should have a single successor!"); 479 DominatorSet &DS = getAnalysis<DominatorSet>(); 480 481 // Update dominator information... The blocks that dominate NewBB are the 482 // intersection of the dominators of predecessors, plus the block itself. 483 // The newly created basic block does not dominate anything except itself. 484 // 485 DominatorSet::DomSetType NewBBDomSet = DS.getDominators(PredBlocks[0]); 486 for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i) 487 set_intersect(NewBBDomSet, DS.getDominators(PredBlocks[i])); 488 NewBBDomSet.insert(NewBB); // All blocks dominate themselves... 489 DS.addBasicBlock(NewBB, NewBBDomSet); 490 491 // Update immediate dominator information if we have it... 492 BasicBlock *NewBBIDom = 0; 493 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 494 // This block does not strictly dominate anything, so it is not an immediate 495 // dominator. To find the immediate dominator of the new exit node, we 496 // trace up the immediate dominators of a predecessor until we find a basic 497 // block that dominates the exit block. 498 // 499 BasicBlock *Dom = PredBlocks[0]; // Some random predecessor... 500 while (!NewBBDomSet.count(Dom)) { // Loop until we find a dominator... 501 assert(Dom != 0 && "No shared dominator found???"); 502 Dom = ID->get(Dom); 503 } 504 505 // Set the immediate dominator now... 506 ID->addNewBlock(NewBB, Dom); 507 NewBBIDom = Dom; // Reuse this if calculating DominatorTree info... 508 } 509 510 // Update DominatorTree information if it is active. 511 if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 512 // NewBB doesn't dominate anything, so just create a node and link it into 513 // its immediate dominator. If we don't have ImmediateDominator info 514 // around, calculate the idom as above. 515 DominatorTree::Node *NewBBIDomNode; 516 if (NewBBIDom) { 517 NewBBIDomNode = DT->getNode(NewBBIDom); 518 } else { 519 NewBBIDomNode = DT->getNode(PredBlocks[0]); // Random pred 520 while (!NewBBDomSet.count(NewBBIDomNode->getBlock())) { 521 NewBBIDomNode = NewBBIDomNode->getIDom(); 522 assert(NewBBIDomNode && "No shared dominator found??"); 523 } 524 } 525 526 // Create the new dominator tree node... 527 DT->createNewNode(NewBB, NewBBIDomNode); 528 } 529 530 // Update dominance frontier information... 531 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 532 // DF(NewBB) is {Exit} because NewBB does not strictly dominate Exit, but it 533 // does dominate itself (and there is an edge (NewBB -> Exit)). Exit is the 534 // single successor of NewBB. 535 DominanceFrontier::DomSetType NewDFSet; 536 BasicBlock *Exit = *succ_begin(NewBB); 537 NewDFSet.insert(Exit); 538 DF->addBasicBlock(NewBB, NewDFSet); 539 540 // Now we must loop over all of the dominance frontiers in the function, 541 // replacing occurrences of Exit with NewBB in some cases. All blocks that 542 // dominate a block in PredBlocks and contained Exit in their dominance 543 // frontier must be updated to contain NewBB instead. This only occurs if 544 // there is more than one block in PredBlocks. 545 // 546 if (PredBlocks.size() > 1) { 547 for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) { 548 BasicBlock *Pred = PredBlocks[i]; 549 // Get all of the dominators of the predecessor... 550 const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred); 551 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 552 PDE = PredDoms.end(); PDI != PDE; ++PDI) { 553 BasicBlock *PredDom = *PDI; 554 555 // If the Exit node is in DF(PredDom), then PredDom didn't dominate 556 // Exit but did dominate a predecessor of it. Now we change this 557 // entry to include NewBB in the DF instead of Exit. 558 DominanceFrontier::iterator DFI = DF->find(PredDom); 559 assert(DFI != DF->end() && "No dominance frontier for node?"); 560 if (DFI->second.count(Exit)) { 561 DF->removeFromFrontier(DFI, Exit); 562 DF->addToFrontier(DFI, NewBB); 563 } 564 } 565 } 566 } 567 } 568} 569