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