lib/VMCore/Dominators.cpp

   1 //===- Dominators.cpp - Dominator Calculation -----------------------------===//
   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 file implements simple dominator construction algorithms for finding
  11 // forward dominators.  Postdominators are available in libanalysis, but are not
  12 // included in libvmcore, because it's not needed.  Forward dominators are
  13 // needed to support the Verifier pass.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Analysis/Dominators.h"
  18 #include "llvm/Support/CFG.h"
  19 #include "llvm/Assembly/Writer.h"
  20 #include "llvm/ADT/DepthFirstIterator.h"
  21 #include "llvm/ADT/SetOperations.h"
  22 #include "llvm/ADT/SmallPtrSet.h"
  23 #include "llvm/Instructions.h"
  24 #include "llvm/Support/Streams.h"
  25 #include <algorithm>
  26 using namespace llvm;
  27
  28 namespace llvm {
  29 static std::ostream &operator<<(std::ostream &o,
  30                                 const std::set<BasicBlock*> &BBs) {
  31   for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
  32        I != E; ++I)
  33     if (*I)
  34       WriteAsOperand(o, *I, false);
  35     else
  36       o << " <<exit node>>";
  37   return o;
  38 }
  39 }
  40
  41 //===----------------------------------------------------------------------===//
  42 //  DominatorTree Implementation
  43 //===----------------------------------------------------------------------===//
  44 //
  45 // DominatorTree construction - This pass constructs immediate dominator
  46 // information for a flow-graph based on the algorithm described in this
  47 // document:
  48 //
  49 //   A Fast Algorithm for Finding Dominators in a Flowgraph
  50 //   T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
  51 //
  52 // This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and
  53 // LINK, but it turns out that the theoretically slower O(n*log(n))
  54 // implementation is actually faster than the "efficient" algorithm (even for
  55 // large CFGs) because the constant overheads are substantially smaller.  The
  56 // lower-complexity version can be enabled with the following #define:
  57 //
  58 #define BALANCE_IDOM_TREE 0
  59 //
  60 //===----------------------------------------------------------------------===//
  61
  62 char DominatorTree::ID = 0;
  63 static RegisterPass<DominatorTree>
  64 E("domtree", "Dominator Tree Construction", true);
  65
  66 // NewBB is split and now it has one successor. Update dominator tree to
  67 // reflect this change.
  68 void DominatorTree::splitBlock(BasicBlock *NewBB) {
  69
  70   assert(NewBB->getTerminator()->getNumSuccessors() == 1
  71          && "NewBB should have a single successor!");
  72   BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
  73
  74   std::vector<BasicBlock*> PredBlocks;
  75   for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB);
  76        PI != PE; ++PI)
  77       PredBlocks.push_back(*PI);
  78
  79   assert(!PredBlocks.empty() && "No predblocks??");
  80
  81   // The newly inserted basic block will dominate existing basic blocks iff the
  82   // PredBlocks dominate all of the non-pred blocks.  If all predblocks dominate
  83   // the non-pred blocks, then they all must be the same block!
  84   //
  85   bool NewBBDominatesNewBBSucc = true;
  86   {
  87     BasicBlock *OnePred = PredBlocks[0];
  88     unsigned i = 1, e = PredBlocks.size();
  89     for (i = 1; !isReachableFromEntry(OnePred); ++i) {
  90       assert(i != e && "Didn't find reachable pred?");
  91       OnePred = PredBlocks[i];
  92     }
  93
  94     for (; i != e; ++i)
  95       if (PredBlocks[i] != OnePred && isReachableFromEntry(OnePred)){
  96         NewBBDominatesNewBBSucc = false;
  97         break;
  98       }
  99
 100     if (NewBBDominatesNewBBSucc)
 101       for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
 102            PI != E; ++PI)
 103         if (*PI != NewBB && !dominates(NewBBSucc, *PI)) {
 104           NewBBDominatesNewBBSucc = false;
 105           break;
 106         }
 107   }
 108
 109   // The other scenario where the new block can dominate its successors are when
 110   // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc
 111   // already.
 112   if (!NewBBDominatesNewBBSucc) {
 113     NewBBDominatesNewBBSucc = true;
 114     for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
 115          PI != E; ++PI)
 116       if (*PI != NewBB && !dominates(NewBBSucc, *PI)) {
 117         NewBBDominatesNewBBSucc = false;
 118         break;
 119       }
 120   }
 121
 122
 123   // Find NewBB's immediate dominator and create new dominator tree node for
 124   // NewBB.
 125   BasicBlock *NewBBIDom = 0;
 126   unsigned i = 0;
 127   for (i = 0; i < PredBlocks.size(); ++i)
 128     if (isReachableFromEntry(PredBlocks[i])) {
 129       NewBBIDom = PredBlocks[i];
 130       break;
 131     }
 132   assert(i != PredBlocks.size() && "No reachable preds?");
 133   for (i = i + 1; i < PredBlocks.size(); ++i) {
 134     if (isReachableFromEntry(PredBlocks[i]))
 135       NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
 136   }
 137   assert(NewBBIDom && "No immediate dominator found??");
 138
 139   // Create the new dominator tree node... and set the idom of NewBB.
 140   DomTreeNode *NewBBNode = addNewBlock(NewBB, NewBBIDom);
 141
 142   // If NewBB strictly dominates other blocks, then it is now the immediate
 143   // dominator of NewBBSucc.  Update the dominator tree as appropriate.
 144   if (NewBBDominatesNewBBSucc) {
 145     DomTreeNode *NewBBSuccNode = getNode(NewBBSucc);
 146     changeImmediateDominator(NewBBSuccNode, NewBBNode);
 147   }
 148 }
 149
 150 unsigned DominatorTree::DFSPass(BasicBlock *V, unsigned N) {
 151   // This is more understandable as a recursive algorithm, but we can't use the
 152   // recursive algorithm due to stack depth issues.  Keep it here for
 153   // documentation purposes.
 154 #if 0
 155   InfoRec &VInfo = Info[Roots[i]];
 156   VInfo.Semi = ++N;
 157   VInfo.Label = V;
 158
 159   Vertex.push_back(V);        // Vertex[n] = V;
 160   //Info[V].Ancestor = 0;     // Ancestor[n] = 0
 161   //Info[V].Child = 0;        // Child[v] = 0
 162   VInfo.Size = 1;             // Size[v] = 1
 163
 164   for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
 165     InfoRec &SuccVInfo = Info[*SI];
 166     if (SuccVInfo.Semi == 0) {
 167       SuccVInfo.Parent = V;
 168       N = DFSPass(*SI, N);
 169     }
 170   }
 171 #else
 172   std::vector<std::pair<BasicBlock*, unsigned> > Worklist;
 173   Worklist.push_back(std::make_pair(V, 0U));
 174   while (!Worklist.empty()) {
 175     BasicBlock *BB = Worklist.back().first;
 176     unsigned NextSucc = Worklist.back().second;
 177
 178     // First time we visited this BB?
 179     if (NextSucc == 0) {
 180       InfoRec &BBInfo = Info[BB];
 181       BBInfo.Semi = ++N;
 182       BBInfo.Label = BB;
 183
 184       Vertex.push_back(BB);       // Vertex[n] = V;
 185       //BBInfo[V].Ancestor = 0;   // Ancestor[n] = 0
 186       //BBInfo[V].Child = 0;      // Child[v] = 0
 187       BBInfo.Size = 1;            // Size[v] = 1
 188     }
 189
 190     // If we are done with this block, remove it from the worklist.
 191     if (NextSucc == BB->getTerminator()->getNumSuccessors()) {
 192       Worklist.pop_back();
 193       continue;
 194     }
 195
 196     // Otherwise, increment the successor number for the next time we get to it.
 197     ++Worklist.back().second;
 198
 199     // Visit the successor next, if it isn't already visited.
 200     BasicBlock *Succ = BB->getTerminator()->getSuccessor(NextSucc);
 201
 202     InfoRec &SuccVInfo = Info[Succ];
 203     if (SuccVInfo.Semi == 0) {
 204       SuccVInfo.Parent = BB;
 205       Worklist.push_back(std::make_pair(Succ, 0U));
 206     }
 207   }
 208 #endif
 209   return N;
 210 }
 211
 212 void DominatorTree::Compress(BasicBlock *VIn) {
 213
 214   std::vector<BasicBlock *> Work;
 215   SmallPtrSet<BasicBlock *, 32> Visited;
 216   BasicBlock *VInAncestor = Info[VIn].Ancestor;
 217   InfoRec &VInVAInfo = Info[VInAncestor];
 218
 219   if (VInVAInfo.Ancestor != 0)
 220     Work.push_back(VIn);
 221
 222   while (!Work.empty()) {
 223     BasicBlock *V = Work.back();
 224     InfoRec &VInfo = Info[V];
 225     BasicBlock *VAncestor = VInfo.Ancestor;
 226     InfoRec &VAInfo = Info[VAncestor];
 227
 228     // Process Ancestor first
 229     if (Visited.insert(VAncestor) &&
 230         VAInfo.Ancestor != 0) {
 231       Work.push_back(VAncestor);
 232       continue;
 233     }
 234     Work.pop_back();
 235
 236     // Update VInfo based on Ancestor info
 237     if (VAInfo.Ancestor == 0)
 238       continue;
 239     BasicBlock *VAncestorLabel = VAInfo.Label;
 240     BasicBlock *VLabel = VInfo.Label;
 241     if (Info[VAncestorLabel].Semi < Info[VLabel].Semi)
 242       VInfo.Label = VAncestorLabel;
 243     VInfo.Ancestor = VAInfo.Ancestor;
 244   }
 245 }
 246
 247 BasicBlock *DominatorTree::Eval(BasicBlock *V) {
 248   InfoRec &VInfo = Info[V];
 249 #if !BALANCE_IDOM_TREE
 250   // Higher-complexity but faster implementation
 251   if (VInfo.Ancestor == 0)
 252     return V;
 253   Compress(V);
 254   return VInfo.Label;
 255 #else
 256   // Lower-complexity but slower implementation
 257   if (VInfo.Ancestor == 0)
 258     return VInfo.Label;
 259   Compress(V);
 260   BasicBlock *VLabel = VInfo.Label;
 261
 262   BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label;
 263   if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi)
 264     return VLabel;
 265   else
 266     return VAncestorLabel;
 267 #endif
 268 }
 269
 270 void DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
 271 #if !BALANCE_IDOM_TREE
 272   // Higher-complexity but faster implementation
 273   WInfo.Ancestor = V;
 274 #else
 275   // Lower-complexity but slower implementation
 276   BasicBlock *WLabel = WInfo.Label;
 277   unsigned WLabelSemi = Info[WLabel].Semi;
 278   BasicBlock *S = W;
 279   InfoRec *SInfo = &Info[S];
 280
 281   BasicBlock *SChild = SInfo->Child;
 282   InfoRec *SChildInfo = &Info[SChild];
 283
 284   while (WLabelSemi < Info[SChildInfo->Label].Semi) {
 285     BasicBlock *SChildChild = SChildInfo->Child;
 286     if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) {
 287       SChildInfo->Ancestor = S;
 288       SInfo->Child = SChild = SChildChild;
 289       SChildInfo = &Info[SChild];
 290     } else {
 291       SChildInfo->Size = SInfo->Size;
 292       S = SInfo->Ancestor = SChild;
 293       SInfo = SChildInfo;
 294       SChild = SChildChild;
 295       SChildInfo = &Info[SChild];
 296     }
 297   }
 298
 299   InfoRec &VInfo = Info[V];
 300   SInfo->Label = WLabel;
 301
 302   assert(V != W && "The optimization here will not work in this case!");
 303   unsigned WSize = WInfo.Size;
 304   unsigned VSize = (VInfo.Size += WSize);
 305
 306   if (VSize < 2*WSize)
 307     std::swap(S, VInfo.Child);
 308
 309   while (S) {
 310     SInfo = &Info[S];
 311     SInfo->Ancestor = V;
 312     S = SInfo->Child;
 313   }
 314 #endif
 315 }
 316
 317 void DominatorTree::calculate(Function &F) {
 318   BasicBlock* Root = Roots[0];
 319
 320   // Add a node for the root...
 321   DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0);
 322
 323   Vertex.push_back(0);
 324
 325   // Step #1: Number blocks in depth-first order and initialize variables used
 326   // in later stages of the algorithm.
 327   unsigned N = DFSPass(Root, 0);
 328
 329   for (unsigned i = N; i >= 2; --i) {
 330     BasicBlock *W = Vertex[i];
 331     InfoRec &WInfo = Info[W];
 332
 333     // Step #2: Calculate the semidominators of all vertices
 334     for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI)
 335       if (Info.count(*PI)) {  // Only if this predecessor is reachable!
 336         unsigned SemiU = Info[Eval(*PI)].Semi;
 337         if (SemiU < WInfo.Semi)
 338           WInfo.Semi = SemiU;
 339       }
 340
 341     Info[Vertex[WInfo.Semi]].Bucket.push_back(W);
 342
 343     BasicBlock *WParent = WInfo.Parent;
 344     Link(WParent, W, WInfo);
 345
 346     // Step #3: Implicitly define the immediate dominator of vertices
 347     std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket;
 348     while (!WParentBucket.empty()) {
 349       BasicBlock *V = WParentBucket.back();
 350       WParentBucket.pop_back();
 351       BasicBlock *U = Eval(V);
 352       IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent;
 353     }
 354   }
 355
 356   // Step #4: Explicitly define the immediate dominator of each vertex
 357   for (unsigned i = 2; i <= N; ++i) {
 358     BasicBlock *W = Vertex[i];
 359     BasicBlock *&WIDom = IDoms[W];
 360     if (WIDom != Vertex[Info[W].Semi])
 361       WIDom = IDoms[WIDom];
 362   }
 363
 364   // Loop over all of the reachable blocks in the function...
 365   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 366     if (BasicBlock *ImmDom = getIDom(I)) {  // Reachable block.
 367       DomTreeNode *BBNode = DomTreeNodes[I];
 368       if (BBNode) continue;  // Haven't calculated this node yet?
 369
 370       // Get or calculate the node for the immediate dominator
 371       DomTreeNode *IDomNode = getNodeForBlock(ImmDom);
 372
 373       // Add a new tree node for this BasicBlock, and link it as a child of
 374       // IDomNode
 375       DomTreeNode *C = new DomTreeNode(I, IDomNode);
 376       DomTreeNodes[I] = IDomNode->addChild(C);
 377     }
 378
 379   // Free temporary memory used to construct idom's
 380   Info.clear();
 381   IDoms.clear();
 382   std::vector<BasicBlock*>().swap(Vertex);
 383
 384   updateDFSNumbers();
 385 }
 386
 387 void DominatorTreeBase::updateDFSNumbers() {
 388   int dfsnum = 0;
 389   // Iterate over all nodes in depth first order.
 390   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
 391     for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
 392            E = df_end(Roots[i]); I != E; ++I) {
 393       BasicBlock *BB = *I;
 394       DomTreeNode *BBNode = getNode(BB);
 395       if (BBNode) {
 396         if (!BBNode->getIDom())
 397           BBNode->assignDFSNumber(dfsnum);
 398       }
 399   }
 400   SlowQueries = 0;
 401   DFSInfoValid = true;
 402 }
 403
 404 /// isReachableFromEntry - Return true if A is dominated by the entry
 405 /// block of the function containing it.
 406 const bool DominatorTreeBase::isReachableFromEntry(BasicBlock* A) {
 407   assert (!isPostDominator()
 408           && "This is not implemented for post dominators");
 409   return dominates(&A->getParent()->getEntryBlock(), A);
 410 }
 411
 412 // dominates - Return true if A dominates B. THis performs the
 413 // special checks necessary if A and B are in the same basic block.
 414 bool DominatorTreeBase::dominates(Instruction *A, Instruction *B) {
 415   BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
 416   if (BBA != BBB) return dominates(BBA, BBB);
 417
 418   // It is not possible to determine dominance between two PHI nodes
 419   // based on their ordering.
 420   if (isa<PHINode>(A) && isa<PHINode>(B))
 421     return false;
 422
 423   // Loop through the basic block until we find A or B.
 424   BasicBlock::iterator I = BBA->begin();
 425   for (; &*I != A && &*I != B; ++I) /*empty*/;
 426
 427   if(!IsPostDominators) {
 428     // A dominates B if it is found first in the basic block.
 429     return &*I == A;
 430   } else {
 431     // A post-dominates B if B is found first in the basic block.
 432     return &*I == B;
 433   }
 434 }
 435
 436 // DominatorTreeBase::reset - Free all of the tree node memory.
 437 //
 438 void DominatorTreeBase::reset() {
 439   for (DomTreeNodeMapType::iterator I = DomTreeNodes.begin(),
 440          E = DomTreeNodes.end(); I != E; ++I)
 441     delete I->second;
 442   DomTreeNodes.clear();
 443   IDoms.clear();
 444   Roots.clear();
 445   Vertex.clear();
 446   RootNode = 0;
 447 }
 448
 449 /// findNearestCommonDominator - Find nearest common dominator basic block
 450 /// for basic block A and B. If there is no such block then return NULL.
 451 BasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A,
 452                                                           BasicBlock *B) {
 453
 454   assert (!isPostDominator()
 455           && "This is not implemented for post dominators");
 456   assert (A->getParent() == B->getParent()
 457           && "Two blocks are not in same function");
 458
 459   // If either A or B is a entry block then it is nearest common dominator.
 460   BasicBlock &Entry  = A->getParent()->getEntryBlock();
 461   if (A == &Entry || B == &Entry)
 462     return &Entry;
 463
 464   // If B dominates A then B is nearest common dominator.
 465   if (dominates(B,A))
 466     return B;
 467
 468   // If A dominates B then A is nearest common dominator.
 469   if (dominates(A,B))
 470     return A;
 471
 472   DomTreeNode *NodeA = getNode(A);
 473   DomTreeNode *NodeB = getNode(B);
 474
 475   // Collect NodeA dominators set.
 476   SmallPtrSet<DomTreeNode*, 16> NodeADoms;
 477   NodeADoms.insert(NodeA);
 478   DomTreeNode *IDomA = NodeA->getIDom();
 479   while(IDomA) {
 480     NodeADoms.insert(IDomA);
 481     IDomA = IDomA->getIDom();
 482   }
 483
 484   // Walk NodeB immediate dominators chain and find common dominator node.
 485   DomTreeNode *IDomB = NodeB->getIDom();
 486   while(IDomB) {
 487     if (NodeADoms.count(IDomB) != 0)
 488       return IDomB->getBlock();
 489
 490     IDomB = IDomB->getIDom();
 491   }
 492
 493   return NULL;
 494 }
 495
 496 /// assignDFSNumber - Assign In and Out numbers while walking dominator tree
 497 /// in dfs order.
 498 void DomTreeNode::assignDFSNumber(int num) {
 499   std::vector<DomTreeNode *>  workStack;
 500   SmallPtrSet<DomTreeNode *, 32> Visited;
 501
 502   workStack.push_back(this);
 503   Visited.insert(this);
 504   this->DFSNumIn = num++;
 505
 506   while (!workStack.empty()) {
 507     DomTreeNode  *Node = workStack.back();
 508
 509     bool visitChild = false;
 510     for (std::vector<DomTreeNode*>::iterator DI = Node->begin(),
 511            E = Node->end(); DI != E && !visitChild; ++DI) {
 512       DomTreeNode *Child = *DI;
 513       if (!Visited.insert(Child))
 514         continue;
 515
 516       visitChild = true;
 517       Child->DFSNumIn = num++;
 518       workStack.push_back(Child);
 519     }
 520     if (!visitChild) {
 521       // If we reach here means all children are visited
 522       Node->DFSNumOut = num++;
 523       workStack.pop_back();
 524     }
 525   }
 526 }
 527
 528 void DomTreeNode::setIDom(DomTreeNode *NewIDom) {
 529   assert(IDom && "No immediate dominator?");
 530   if (IDom != NewIDom) {
 531     std::vector<DomTreeNode*>::iterator I =
 532       std::find(IDom->Children.begin(), IDom->Children.end(), this);
 533     assert(I != IDom->Children.end() &&
 534            "Not in immediate dominator children set!");
 535     // I am no longer your child...
 536     IDom->Children.erase(I);
 537
 538     // Switch to new dominator
 539     IDom = NewIDom;
 540     IDom->Children.push_back(this);
 541   }
 542 }
 543
 544 DomTreeNode *DominatorTree::getNodeForBlock(BasicBlock *BB) {
 545   DomTreeNode *&BBNode = DomTreeNodes[BB];
 546   if (BBNode) return BBNode;
 547
 548   // Haven't calculated this node yet?  Get or calculate the node for the
 549   // immediate dominator.
 550   BasicBlock *IDom = getIDom(BB);
 551   DomTreeNode *IDomNode = getNodeForBlock(IDom);
 552
 553   // Add a new tree node for this BasicBlock, and link it as a child of
 554   // IDomNode
 555   DomTreeNode *C = new DomTreeNode(BB, IDomNode);
 556   return DomTreeNodes[BB] = IDomNode->addChild(C);
 557 }
 558
 559 static std::ostream &operator<<(std::ostream &o,
 560                                 const DomTreeNode *Node) {
 561   if (Node->getBlock())
 562     WriteAsOperand(o, Node->getBlock(), false);
 563   else
 564     o << " <<exit node>>";
 565   return o << "\n";
 566 }
 567
 568 static void PrintDomTree(const DomTreeNode *N, std::ostream &o,
 569                          unsigned Lev) {
 570   o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
 571   for (DomTreeNode::const_iterator I = N->begin(), E = N->end();
 572        I != E; ++I)
 573     PrintDomTree(*I, o, Lev+1);
 574 }
 575
 576 void DominatorTreeBase::print(std::ostream &o, const Module* ) const {
 577   o << "=============================--------------------------------\n"
 578     << "Inorder Dominator Tree:\n";
 579   PrintDomTree(getRootNode(), o, 1);
 580 }
 581
 582 void DominatorTreeBase::dump() {
 583   print (llvm::cerr);
 584 }
 585
 586 bool DominatorTree::runOnFunction(Function &F) {
 587   reset();     // Reset from the last time we were run...
 588   Roots.push_back(&F.getEntryBlock());
 589   calculate(F);
 590   return false;
 591 }
 592
 593 //===----------------------------------------------------------------------===//
 594 //  DominanceFrontier Implementation
 595 //===----------------------------------------------------------------------===//
 596
 597 char DominanceFrontier::ID = 0;
 598 static RegisterPass<DominanceFrontier>
 599 G("domfrontier", "Dominance Frontier Construction", true);
 600
 601 // NewBB is split and now it has one successor. Update dominace frontier to
 602 // reflect this change.
 603 void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
 604
 605   assert(NewBB->getTerminator()->getNumSuccessors() == 1
 606          && "NewBB should have a single successor!");
 607   BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
 608
 609   std::vector<BasicBlock*> PredBlocks;
 610   for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB);
 611        PI != PE; ++PI)
 612       PredBlocks.push_back(*PI);
 613
 614   if (PredBlocks.empty())
 615     // If NewBB does not have any predecessors then it is a entry block.
 616     // In this case, NewBB and its successor NewBBSucc dominates all
 617     // other blocks.
 618     return;
 619
 620   DominatorTree &DT = getAnalysis<DominatorTree>();
 621   bool NewBBDominatesNewBBSucc = true;
 622   if (!DT.dominates(NewBB, NewBBSucc))
 623     NewBBDominatesNewBBSucc = false;
 624
 625   // NewBBSucc inherites original NewBB frontier.
 626   DominanceFrontier::iterator NewBBI = find(NewBB);
 627   if (NewBBI != end()) {
 628     DominanceFrontier::DomSetType NewBBSet = NewBBI->second;
 629     DominanceFrontier::DomSetType NewBBSuccSet;
 630     NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end());
 631     addBasicBlock(NewBBSucc, NewBBSuccSet);
 632   }
 633
 634   // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
 635   // DF(PredBlocks[0]) without the stuff that the new block does not dominate
 636   // a predecessor of.
 637   if (NewBBDominatesNewBBSucc) {
 638     DominanceFrontier::iterator DFI = find(PredBlocks[0]);
 639     if (DFI != end()) {
 640       DominanceFrontier::DomSetType Set = DFI->second;
 641       // Filter out stuff in Set that we do not dominate a predecessor of.
 642       for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
 643              E = Set.end(); SetI != E;) {
 644         bool DominatesPred = false;
 645         for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
 646              PI != E; ++PI)
 647           if (DT.dominates(NewBB, *PI))
 648             DominatesPred = true;
 649         if (!DominatesPred)
 650           Set.erase(SetI++);
 651         else
 652           ++SetI;
 653       }
 654
 655       if (NewBBI != end()) {
 656         DominanceFrontier::DomSetType NewBBSet = NewBBI->second;
 657         NewBBSet.insert(Set.begin(), Set.end());
 658       } else
 659         addBasicBlock(NewBB, Set);
 660     }
 661
 662   } else {
 663     // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate
 664     // NewBBSucc, but it does dominate itself (and there is an edge (NewBB ->
 665     // NewBBSucc)).  NewBBSucc is the single successor of NewBB.
 666     DominanceFrontier::DomSetType NewDFSet;
 667     NewDFSet.insert(NewBBSucc);
 668     addBasicBlock(NewBB, NewDFSet);
 669   }
 670
 671   // Now we must loop over all of the dominance frontiers in the function,
 672   // replacing occurrences of NewBBSucc with NewBB in some cases.  All
 673   // blocks that dominate a block in PredBlocks and contained NewBBSucc in
 674   // their dominance frontier must be updated to contain NewBB instead.
 675   //
 676   for (Function::iterator FI = NewBB->getParent()->begin(),
 677          FE = NewBB->getParent()->end(); FI != FE; ++FI) {
 678     DominanceFrontier::iterator DFI = find(FI);
 679     if (DFI == end()) continue;  // unreachable block.
 680
 681     // Only consider dominators of NewBBSucc
 682     if (!DFI->second.count(NewBBSucc)) continue;
 683
 684     bool BlockDominatesAny = false;
 685     for (std::vector<BasicBlock*>::const_iterator BI = PredBlocks.begin(),
 686            BE = PredBlocks.end(); BI != BE; ++BI) {
 687       if (DT.dominates(FI, *BI)) {
 688         BlockDominatesAny = true;
 689         break;
 690       }
 691     }
 692
 693     if (BlockDominatesAny) {
 694       // If NewBBSucc should not stay in our dominator frontier, remove it.
 695       // We remove it unless there is a predecessor of NewBBSucc that we
 696       // dominate, but we don't strictly dominate NewBBSucc.
 697       bool ShouldRemove = true;
 698       if ((BasicBlock*)FI == NewBBSucc
 699           || !DT.dominates(FI, NewBBSucc)) {
 700         // Okay, we know that PredDom does not strictly dominate NewBBSucc.
 701         // Check to see if it dominates any predecessors of NewBBSucc.
 702         for (pred_iterator PI = pred_begin(NewBBSucc),
 703                E = pred_end(NewBBSucc); PI != E; ++PI)
 704           if (DT.dominates(FI, *PI)) {
 705             ShouldRemove = false;
 706             break;
 707           }
 708
 709         if (ShouldRemove)
 710           removeFromFrontier(DFI, NewBBSucc);
 711         addToFrontier(DFI, NewBB);
 712
 713         break;
 714       }
 715     }
 716   }
 717 }
 718
 719 namespace {
 720   class DFCalculateWorkObject {
 721   public:
 722     DFCalculateWorkObject(BasicBlock *B, BasicBlock *P,
 723                           const DomTreeNode *N,
 724                           const DomTreeNode *PN)
 725     : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
 726     BasicBlock *currentBB;
 727     BasicBlock *parentBB;
 728     const DomTreeNode *Node;
 729     const DomTreeNode *parentNode;
 730   };
 731 }
 732
 733 const DominanceFrontier::DomSetType &
 734 DominanceFrontier::calculate(const DominatorTree &DT,
 735                              const DomTreeNode *Node) {
 736   BasicBlock *BB = Node->getBlock();
 737   DomSetType *Result = NULL;
 738
 739   std::vector<DFCalculateWorkObject> workList;
 740   SmallPtrSet<BasicBlock *, 32> visited;
 741
 742   workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL));
 743   do {
 744     DFCalculateWorkObject *currentW = &workList.back();
 745     assert (currentW && "Missing work object.");
 746
 747     BasicBlock *currentBB = currentW->currentBB;
 748     BasicBlock *parentBB = currentW->parentBB;
 749     const DomTreeNode *currentNode = currentW->Node;
 750     const DomTreeNode *parentNode = currentW->parentNode;
 751     assert (currentBB && "Invalid work object. Missing current Basic Block");
 752     assert (currentNode && "Invalid work object. Missing current Node");
 753     DomSetType &S = Frontiers[currentBB];
 754
 755     // Visit each block only once.
 756     if (visited.count(currentBB) == 0) {
 757       visited.insert(currentBB);
 758
 759       // Loop over CFG successors to calculate DFlocal[currentNode]
 760       for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB);
 761            SI != SE; ++SI) {
 762         // Does Node immediately dominate this successor?
 763         if (DT[*SI]->getIDom() != currentNode)
 764           S.insert(*SI);
 765       }
 766     }
 767
 768     // At this point, S is DFlocal.  Now we union in DFup's of our children...
 769     // Loop through and visit the nodes that Node immediately dominates (Node's
 770     // children in the IDomTree)
 771     bool visitChild = false;
 772     for (DomTreeNode::const_iterator NI = currentNode->begin(),
 773            NE = currentNode->end(); NI != NE; ++NI) {
 774       DomTreeNode *IDominee = *NI;
 775       BasicBlock *childBB = IDominee->getBlock();
 776       if (visited.count(childBB) == 0) {
 777         workList.push_back(DFCalculateWorkObject(childBB, currentBB,
 778                                                  IDominee, currentNode));
 779         visitChild = true;
 780       }
 781     }
 782
 783     // If all children are visited or there is any child then pop this block
 784     // from the workList.
 785     if (!visitChild) {
 786
 787       if (!parentBB) {
 788         Result = &S;
 789         break;
 790       }
 791
 792       DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
 793       DomSetType &parentSet = Frontiers[parentBB];
 794       for (; CDFI != CDFE; ++CDFI) {
 795         if (!DT.properlyDominates(parentNode, DT[*CDFI]))
 796           parentSet.insert(*CDFI);
 797       }
 798       workList.pop_back();
 799     }
 800
 801   } while (!workList.empty());
 802
 803   return *Result;
 804 }
 805
 806 void DominanceFrontierBase::print(std::ostream &o, const Module* ) const {
 807   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 808     o << "  DomFrontier for BB";
 809     if (I->first)
 810       WriteAsOperand(o, I->first, false);
 811     else
 812       o << " <<exit node>>";
 813     o << " is:\t" << I->second << "\n";
 814   }
 815 }
 816
 817 void DominanceFrontierBase::dump() {
 818   print (llvm::cerr);
 819 }