1 //===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This pass performs several transformations to transform natural loops into a
11 // simpler form, which makes subsequent analyses and transformations simpler and
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.
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.
24 // This pass also guarantees that loops will have exactly one backedge.
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
30 // This pass obviously modifies the CFG, but updates loop information and
31 // dominator information.
33 //===----------------------------------------------------------------------===//
35 #include "llvm/Transforms/Scalar.h"
36 #include "llvm/Constant.h"
37 #include "llvm/iTerminators.h"
38 #include "llvm/iPHINode.h"
39 #include "llvm/Function.h"
40 #include "llvm/Type.h"
41 #include "llvm/Analysis/Dominators.h"
42 #include "llvm/Analysis/LoopInfo.h"
43 #include "llvm/Support/CFG.h"
44 #include "Support/SetOperations.h"
45 #include "Support/Statistic.h"
46 #include "Support/DepthFirstIterator.h"
51 NumInserted("loopsimplify", "Number of pre-header or exit blocks inserted");
53 struct LoopSimplify : public FunctionPass {
54 virtual bool runOnFunction(Function &F);
56 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
57 // We need loop information to identify the loops...
58 AU.addRequired<LoopInfo>();
59 AU.addRequired<DominatorSet>();
60 AU.addRequired<DominatorTree>();
62 AU.addPreserved<LoopInfo>();
63 AU.addPreserved<DominatorSet>();
64 AU.addPreserved<ImmediateDominators>();
65 AU.addPreserved<DominatorTree>();
66 AU.addPreserved<DominanceFrontier>();
67 AU.addPreservedID(BreakCriticalEdgesID); // No crit edges added....
70 bool ProcessLoop(Loop *L);
71 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix,
72 const std::vector<BasicBlock*> &Preds);
73 void RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
74 void InsertPreheaderForLoop(Loop *L);
75 void InsertUniqueBackedgeBlock(Loop *L);
77 void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB,
78 std::vector<BasicBlock*> &PredBlocks);
81 RegisterOpt<LoopSimplify>
82 X("loopsimplify", "Canonicalize natural loops", true);
85 // Publically exposed interface to pass...
86 const PassInfo *llvm::LoopSimplifyID = X.getPassInfo();
87 Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
89 /// runOnFunction - Run down all loops in the CFG (recursively, but we could do
90 /// it in any convenient order) inserting preheaders...
92 bool LoopSimplify::runOnFunction(Function &F) {
94 LoopInfo &LI = getAnalysis<LoopInfo>();
96 for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I)
97 Changed |= ProcessLoop(*I);
103 /// ProcessLoop - Walk the loop structure in depth first order, ensuring that
104 /// all loops have preheaders.
106 bool LoopSimplify::ProcessLoop(Loop *L) {
107 bool Changed = false;
109 // Check to see that no blocks (other than the header) in the loop have
110 // predecessors that are not in the loop. This is not valid for natural
111 // loops, but can occur if the blocks are unreachable. Since they are
112 // unreachable we can just shamelessly destroy their terminators to make them
113 // not branch into the loop!
114 assert(L->getBlocks()[0] == L->getHeader() &&
115 "Header isn't first block in loop?");
116 for (unsigned i = 1, e = L->getBlocks().size(); i != e; ++i) {
117 BasicBlock *LoopBB = L->getBlocks()[i];
119 for (pred_iterator PI = pred_begin(LoopBB), E = pred_end(LoopBB);
121 if (!L->contains(*PI)) {
122 // This predecessor is not in the loop. Kill its terminator!
123 BasicBlock *DeadBlock = *PI;
124 for (succ_iterator SI = succ_begin(DeadBlock), E = succ_end(DeadBlock);
126 (*SI)->removePredecessor(DeadBlock); // Remove PHI node entries
128 // Delete the dead terminator.
129 DeadBlock->getInstList().pop_back();
132 if (LoopBB->getParent()->getReturnType() != Type::VoidTy)
133 RetVal = Constant::getNullValue(LoopBB->getParent()->getReturnType());
134 new ReturnInst(RetVal, DeadBlock);
135 goto Retry; // We just invalidated the pred_iterator. Retry.
139 // Does the loop already have a preheader? If so, don't modify the loop...
140 if (L->getLoopPreheader() == 0) {
141 InsertPreheaderForLoop(L);
146 // Next, check to make sure that all exit nodes of the loop only have
147 // predecessors that are inside of the loop. This check guarantees that the
148 // loop preheader/header will dominate the exit blocks. If the exit block has
149 // predecessors from outside of the loop, split the edge now.
150 for (unsigned i = 0, e = L->getExitBlocks().size(); i != e; ++i) {
151 BasicBlock *ExitBlock = L->getExitBlocks()[i];
152 for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
154 if (!L->contains(*PI)) {
155 RewriteLoopExitBlock(L, ExitBlock);
162 // The preheader may have more than two predecessors at this point (from the
163 // preheader and from the backedges). To simplify the loop more, insert an
164 // extra back-edge block in the loop so that there is exactly one backedge.
165 if (L->getNumBackEdges() != 1) {
166 InsertUniqueBackedgeBlock(L);
171 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
172 Changed |= ProcessLoop(*I);
176 /// SplitBlockPredecessors - Split the specified block into two blocks. We want
177 /// to move the predecessors specified in the Preds list to point to the new
178 /// block, leaving the remaining predecessors pointing to BB. This method
179 /// updates the SSA PHINode's, but no other analyses.
181 BasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB,
183 const std::vector<BasicBlock*> &Preds) {
185 // Create new basic block, insert right before the original block...
186 BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB->getParent(), BB);
188 // The preheader first gets an unconditional branch to the loop header...
189 BranchInst *BI = new BranchInst(BB, NewBB);
191 // For every PHI node in the block, insert a PHI node into NewBB where the
192 // incoming values from the out of loop edges are moved to NewBB. We have two
193 // possible cases here. If the loop is dead, we just insert dummy entries
194 // into the PHI nodes for the new edge. If the loop is not dead, we move the
195 // incoming edges in BB into new PHI nodes in NewBB.
197 if (!Preds.empty()) { // Is the loop not obviously dead?
198 // Check to see if the values being merged into the new block need PHI
199 // nodes. If so, insert them.
200 for (BasicBlock::iterator I = BB->begin();
201 PHINode *PN = dyn_cast<PHINode>(I); ++I) {
203 // Check to see if all of the values coming in are the same. If so, we
204 // don't need to create a new PHI node.
205 Value *InVal = PN->getIncomingValueForBlock(Preds[0]);
206 for (unsigned i = 1, e = Preds.size(); i != e; ++i)
207 if (InVal != PN->getIncomingValueForBlock(Preds[i])) {
212 // If the values coming into the block are not the same, we need a PHI.
214 // Create the new PHI node, insert it into NewBB at the end of the block
215 PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI);
217 // Move all of the edges from blocks outside the loop to the new PHI
218 for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
219 Value *V = PN->removeIncomingValue(Preds[i]);
220 NewPHI->addIncoming(V, Preds[i]);
224 // Remove all of the edges coming into the PHI nodes from outside of the
226 for (unsigned i = 0, e = Preds.size(); i != e; ++i)
227 PN->removeIncomingValue(Preds[i], false);
230 // Add an incoming value to the PHI node in the loop for the preheader
232 PN->addIncoming(InVal, NewBB);
235 // Now that the PHI nodes are updated, actually move the edges from
236 // Preds to point to NewBB instead of BB.
238 for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
239 TerminatorInst *TI = Preds[i]->getTerminator();
240 for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s)
241 if (TI->getSuccessor(s) == BB)
242 TI->setSuccessor(s, NewBB);
245 } else { // Otherwise the loop is dead...
246 for (BasicBlock::iterator I = BB->begin();
247 PHINode *PN = dyn_cast<PHINode>(I); ++I)
248 // Insert dummy values as the incoming value...
249 PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB);
254 // ChangeExitBlock - This recursive function is used to change any exit blocks
255 // that use OldExit to use NewExit instead. This is recursive because children
256 // may need to be processed as well.
258 static void ChangeExitBlock(Loop *L, BasicBlock *OldExit, BasicBlock *NewExit) {
259 if (L->hasExitBlock(OldExit)) {
260 L->changeExitBlock(OldExit, NewExit);
261 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
262 ChangeExitBlock(*I, OldExit, NewExit);
267 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
268 /// preheader, this method is called to insert one. This method has two phases:
269 /// preheader insertion and analysis updating.
271 void LoopSimplify::InsertPreheaderForLoop(Loop *L) {
272 BasicBlock *Header = L->getHeader();
274 // Compute the set of predecessors of the loop that are not in the loop.
275 std::vector<BasicBlock*> OutsideBlocks;
276 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
278 if (!L->contains(*PI)) // Coming in from outside the loop?
279 OutsideBlocks.push_back(*PI); // Keep track of it...
281 // Split out the loop pre-header
283 SplitBlockPredecessors(Header, ".preheader", OutsideBlocks);
285 //===--------------------------------------------------------------------===//
286 // Update analysis results now that we have performed the transformation
289 // We know that we have loop information to update... update it now.
290 if (Loop *Parent = L->getParentLoop())
291 Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>());
293 // If the header for the loop used to be an exit node for another loop, then
294 // we need to update this to know that the loop-preheader is now the exit
295 // node. Note that the only loop that could have our header as an exit node
296 // is a sibling loop, ie, one with the same parent loop, or one if it's
299 LoopInfo::iterator ParentLoops, ParentLoopsE;
300 if (Loop *Parent = L->getParentLoop()) {
301 ParentLoops = Parent->begin();
302 ParentLoopsE = Parent->end();
303 } else { // Must check top-level loops...
304 ParentLoops = getAnalysis<LoopInfo>().begin();
305 ParentLoopsE = getAnalysis<LoopInfo>().end();
308 // Loop over all sibling loops, performing the substitution (recursively to
309 // include child loops)...
310 for (; ParentLoops != ParentLoopsE; ++ParentLoops)
311 ChangeExitBlock(*ParentLoops, Header, NewBB);
313 DominatorSet &DS = getAnalysis<DominatorSet>(); // Update dominator info
314 DominatorTree &DT = getAnalysis<DominatorTree>();
317 // Update the dominator tree information.
318 // The immediate dominator of the preheader is the immediate dominator of
320 DominatorTree::Node *PHDomTreeNode =
321 DT.createNewNode(NewBB, DT.getNode(Header)->getIDom());
323 // Change the header node so that PNHode is the new immediate dominator
324 DT.changeImmediateDominator(DT.getNode(Header), PHDomTreeNode);
327 // The blocks that dominate NewBB are the blocks that dominate Header,
328 // minus Header, plus NewBB.
329 DominatorSet::DomSetType DomSet = DS.getDominators(Header);
330 DomSet.erase(Header); // Header does not dominate us...
331 DS.addBasicBlock(NewBB, DomSet);
333 // The newly created basic block dominates all nodes dominated by Header.
334 for (df_iterator<DominatorTree::Node*> DFI = df_begin(PHDomTreeNode),
335 E = df_end(PHDomTreeNode); DFI != E; ++DFI)
336 DS.addDominator((*DFI)->getBlock(), NewBB);
339 // Update immediate dominator information if we have it...
340 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) {
341 // Whatever i-dominated the header node now immediately dominates NewBB
342 ID->addNewBlock(NewBB, ID->get(Header));
344 // The preheader now is the immediate dominator for the header node...
345 ID->setImmediateDominator(Header, NewBB);
348 // Update dominance frontier information...
349 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) {
350 // The DF(NewBB) is just (DF(Header)-Header), because NewBB dominates
351 // everything that Header does, and it strictly dominates Header in
353 assert(DF->find(Header) != DF->end() && "Header node doesn't have DF set?");
354 DominanceFrontier::DomSetType NewDFSet = DF->find(Header)->second;
355 NewDFSet.erase(Header);
356 DF->addBasicBlock(NewBB, NewDFSet);
358 // Now we must loop over all of the dominance frontiers in the function,
359 // replacing occurrences of Header with NewBB in some cases. If a block
360 // dominates a (now) predecessor of NewBB, but did not strictly dominate
361 // Header, it will have Header in it's DF set, but should now have NewBB in
363 for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) {
364 // Get all of the dominators of the predecessor...
365 const DominatorSet::DomSetType &PredDoms =
366 DS.getDominators(OutsideBlocks[i]);
367 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(),
368 PDE = PredDoms.end(); PDI != PDE; ++PDI) {
369 BasicBlock *PredDom = *PDI;
370 // If the loop header is in DF(PredDom), then PredDom didn't dominate
371 // the header but did dominate a predecessor outside of the loop. Now
372 // we change this entry to include the preheader in the DF instead of
374 DominanceFrontier::iterator DFI = DF->find(PredDom);
375 assert(DFI != DF->end() && "No dominance frontier for node?");
376 if (DFI->second.count(Header)) {
377 DF->removeFromFrontier(DFI, Header);
378 DF->addToFrontier(DFI, NewBB);
385 void LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
386 DominatorSet &DS = getAnalysis<DominatorSet>();
387 assert(std::find(L->getExitBlocks().begin(), L->getExitBlocks().end(), Exit)
388 != L->getExitBlocks().end() && "Not a current exit block!");
390 std::vector<BasicBlock*> LoopBlocks;
391 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I)
393 LoopBlocks.push_back(*I);
395 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?");
396 BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks);
398 // Update Loop Information - we know that the new block will be in the parent
400 if (Loop *Parent = L->getParentLoop())
401 Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>());
403 // Replace any instances of Exit with NewBB in this and any nested loops...
404 for (df_iterator<Loop*> I = df_begin(L), E = df_end(L); I != E; ++I)
405 if (I->hasExitBlock(Exit))
406 I->changeExitBlock(Exit, NewBB); // Update exit block information
408 // Update dominator information (set, immdom, domtree, and domfrontier)
409 UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks);
412 /// InsertUniqueBackedgeBlock - This method is called when the specified loop
413 /// has more than one backedge in it. If this occurs, revector all of these
414 /// backedges to target a new basic block and have that block branch to the loop
415 /// header. This ensures that loops have exactly one backedge.
417 void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) {
418 assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
420 // Get information about the loop
421 BasicBlock *Preheader = L->getLoopPreheader();
422 BasicBlock *Header = L->getHeader();
423 Function *F = Header->getParent();
425 // Figure out which basic blocks contain back-edges to the loop header.
426 std::vector<BasicBlock*> BackedgeBlocks;
427 for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I)
428 if (*I != Preheader) BackedgeBlocks.push_back(*I);
430 // Create and insert the new backedge block...
431 BasicBlock *BEBlock = new BasicBlock(Header->getName()+".backedge", F);
432 BranchInst *BETerminator = new BranchInst(Header, BEBlock);
434 // Move the new backedge block to right after the last backedge block.
435 Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos;
436 F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock);
438 // Now that the block has been inserted into the function, create PHI nodes in
439 // the backedge block which correspond to any PHI nodes in the header block.
440 for (BasicBlock::iterator I = Header->begin();
441 PHINode *PN = dyn_cast<PHINode>(I); ++I) {
442 PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".be",
444 NewPN->op_reserve(2*BackedgeBlocks.size());
446 // Loop over the PHI node, moving all entries except the one for the
447 // preheader over to the new PHI node.
448 unsigned PreheaderIdx = ~0U;
449 bool HasUniqueIncomingValue = true;
450 Value *UniqueValue = 0;
451 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
452 BasicBlock *IBB = PN->getIncomingBlock(i);
453 Value *IV = PN->getIncomingValue(i);
454 if (IBB == Preheader) {
457 NewPN->addIncoming(IV, IBB);
458 if (HasUniqueIncomingValue) {
459 if (UniqueValue == 0)
461 else if (UniqueValue != IV)
462 HasUniqueIncomingValue = false;
467 // Delete all of the incoming values from the old PN except the preheader's
468 assert(PreheaderIdx != ~0U && "PHI has no preheader entry??");
469 if (PreheaderIdx != 0) {
470 PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx));
471 PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx));
473 PN->op_erase(PN->op_begin()+2, PN->op_end());
475 // Finally, add the newly constructed PHI node as the entry for the BEBlock.
476 PN->addIncoming(NewPN, BEBlock);
478 // As an optimization, if all incoming values in the new PhiNode (which is a
479 // subset of the incoming values of the old PHI node) have the same value,
480 // eliminate the PHI Node.
481 if (HasUniqueIncomingValue) {
482 NewPN->replaceAllUsesWith(UniqueValue);
483 BEBlock->getInstList().erase(NewPN);
487 // Now that all of the PHI nodes have been inserted and adjusted, modify the
488 // backedge blocks to just to the BEBlock instead of the header.
489 for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) {
490 TerminatorInst *TI = BackedgeBlocks[i]->getTerminator();
491 for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op)
492 if (TI->getSuccessor(Op) == Header)
493 TI->setSuccessor(Op, BEBlock);
496 //===--- Update all analyses which we must preserve now -----------------===//
498 // Update Loop Information - we know that this block is now in the current
499 // loop and all parent loops.
500 L->addBasicBlockToLoop(BEBlock, getAnalysis<LoopInfo>());
502 // Replace any instances of Exit with NewBB in this and any nested loops...
503 for (df_iterator<Loop*> I = df_begin(L), E = df_end(L); I != E; ++I)
504 if (I->hasExitBlock(Header))
505 I->changeExitBlock(Header, BEBlock); // Update exit block information
507 // Update dominator information (set, immdom, domtree, and domfrontier)
508 UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks);
511 /// UpdateDomInfoForRevectoredPreds - This method is used to update the four
512 /// different kinds of dominator information (dominator sets, immediate
513 /// dominators, dominator trees, and dominance frontiers) after a new block has
514 /// been added to the CFG.
516 /// This only supports the case when an existing block (known as "NewBBSucc"),
517 /// had some of its predecessors factored into a new basic block. This
518 /// transformation inserts a new basic block ("NewBB"), with a single
519 /// unconditional branch to NewBBSucc, and moves some predecessors of
520 /// "NewBBSucc" to now branch to NewBB. These predecessors are listed in
521 /// PredBlocks, even though they are the same as
522 /// pred_begin(NewBB)/pred_end(NewBB).
524 void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB,
525 std::vector<BasicBlock*> &PredBlocks) {
526 assert(!PredBlocks.empty() && "No predblocks??");
527 assert(succ_begin(NewBB) != succ_end(NewBB) &&
528 ++succ_begin(NewBB) == succ_end(NewBB) &&
529 "NewBB should have a single successor!");
530 BasicBlock *NewBBSucc = *succ_begin(NewBB);
531 DominatorSet &DS = getAnalysis<DominatorSet>();
533 // Update dominator information... The blocks that dominate NewBB are the
534 // intersection of the dominators of predecessors, plus the block itself.
536 DominatorSet::DomSetType NewBBDomSet = DS.getDominators(PredBlocks[0]);
537 for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i)
538 set_intersect(NewBBDomSet, DS.getDominators(PredBlocks[i]));
539 NewBBDomSet.insert(NewBB); // All blocks dominate themselves...
540 DS.addBasicBlock(NewBB, NewBBDomSet);
542 // The newly inserted basic block will dominate existing basic blocks iff the
543 // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate
544 // the non-pred blocks, then they all must be the same block!
546 bool NewBBDominatesNewBBSucc = true;
548 BasicBlock *OnePred = PredBlocks[0];
549 for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i)
550 if (PredBlocks[i] != OnePred) {
551 NewBBDominatesNewBBSucc = false;
555 if (NewBBDominatesNewBBSucc)
556 for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
558 if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) {
559 NewBBDominatesNewBBSucc = false;
564 // The other scenario where the new block can dominate its successors are when
565 // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc
567 if (!NewBBDominatesNewBBSucc) {
568 NewBBDominatesNewBBSucc = true;
569 for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
571 if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) {
572 NewBBDominatesNewBBSucc = false;
577 // If NewBB dominates some blocks, then it will dominate all blocks that
579 if (NewBBDominatesNewBBSucc) {
580 BasicBlock *PredBlock = PredBlocks[0];
581 Function *F = NewBB->getParent();
582 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
583 if (DS.dominates(NewBBSucc, I))
584 DS.addDominator(I, NewBB);
587 // Update immediate dominator information if we have it...
588 BasicBlock *NewBBIDom = 0;
589 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) {
590 // To find the immediate dominator of the new exit node, we trace up the
591 // immediate dominators of a predecessor until we find a basic block that
592 // dominates the exit block.
594 BasicBlock *Dom = PredBlocks[0]; // Some random predecessor...
595 while (!NewBBDomSet.count(Dom)) { // Loop until we find a dominator...
596 assert(Dom != 0 && "No shared dominator found???");
600 // Set the immediate dominator now...
601 ID->addNewBlock(NewBB, Dom);
602 NewBBIDom = Dom; // Reuse this if calculating DominatorTree info...
604 // If NewBB strictly dominates other blocks, we need to update their idom's
605 // now. The only block that need adjustment is the NewBBSucc block, whose
606 // idom should currently be set to PredBlocks[0].
607 if (NewBBDominatesNewBBSucc) {
608 assert(ID->get(NewBBSucc) == PredBlocks[0] &&
609 "Immediate dominator update code broken!");
610 ID->setImmediateDominator(NewBBSucc, NewBB);
614 // Update DominatorTree information if it is active.
615 if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
616 // If we don't have ImmediateDominator info around, calculate the idom as
618 DominatorTree::Node *NewBBIDomNode;
620 NewBBIDomNode = DT->getNode(NewBBIDom);
622 NewBBIDomNode = DT->getNode(PredBlocks[0]); // Random pred
623 while (!NewBBDomSet.count(NewBBIDomNode->getBlock())) {
624 NewBBIDomNode = NewBBIDomNode->getIDom();
625 assert(NewBBIDomNode && "No shared dominator found??");
629 // Create the new dominator tree node... and set the idom of NewBB.
630 DominatorTree::Node *NewBBNode = DT->createNewNode(NewBB, NewBBIDomNode);
632 // If NewBB strictly dominates other blocks, then it is now the immediate
633 // dominator of NewBBSucc. Update the dominator tree as appropriate.
634 if (NewBBDominatesNewBBSucc) {
635 DominatorTree::Node *NewBBSuccNode = DT->getNode(NewBBSucc);
636 assert(NewBBSuccNode->getIDom()->getBlock() == PredBlocks[0] &&
637 "Immediate tree update code broken!");
638 DT->changeImmediateDominator(NewBBSuccNode, NewBBNode);
642 // Update dominance frontier information...
643 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) {
644 // If NewBB dominates NewBBSucc, then the global dominance frontiers are not
645 // changed. DF(NewBB) is now going to be the DF(PredBlocks[0]) without the
646 // stuff that the new block does not dominate a predecessor of.
647 if (NewBBDominatesNewBBSucc) {
648 DominanceFrontier::iterator DFI = DF->find(PredBlocks[0]);
649 if (DFI != DF->end()) {
650 DominanceFrontier::DomSetType Set = DFI->second;
651 // Filter out stuff in Set that we do not dominate a predecessor of.
652 for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
653 E = Set.end(); SetI != E;) {
654 bool DominatesPred = false;
655 for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
657 if (DS.dominates(NewBB, *PI))
658 DominatesPred = true;
665 DF->addBasicBlock(NewBB, Set);
669 // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate
670 // NewBBSucc, but it does dominate itself (and there is an edge (NewBB ->
671 // NewBBSucc)). NewBBSucc is the single successor of NewBB.
672 DominanceFrontier::DomSetType NewDFSet;
673 NewDFSet.insert(NewBBSucc);
674 DF->addBasicBlock(NewBB, NewDFSet);
676 // Now we must loop over all of the dominance frontiers in the function,
677 // replacing occurrences of NewBBSucc with NewBB in some cases. All
678 // blocks that dominate a block in PredBlocks and contained NewBBSucc in
679 // their dominance frontier must be updated to contain NewBB instead.
681 for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) {
682 BasicBlock *Pred = PredBlocks[i];
683 // Get all of the dominators of the predecessor...
684 const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred);
685 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(),
686 PDE = PredDoms.end(); PDI != PDE; ++PDI) {
687 BasicBlock *PredDom = *PDI;
689 // If the NewBBSucc node is in DF(PredDom), then PredDom didn't
690 // dominate NewBBSucc but did dominate a predecessor of it. Now we
691 // change this entry to include NewBB in the DF instead of NewBBSucc.
692 DominanceFrontier::iterator DFI = DF->find(PredDom);
693 assert(DFI != DF->end() && "No dominance frontier for node?");
694 if (DFI->second.count(NewBBSucc)) {
695 DF->removeFromFrontier(DFI, NewBBSucc);
696 DF->addToFrontier(DFI, NewBB);