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 unsigned DominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo,
  67                                       unsigned N) {
  68   // This is more understandable as a recursive algorithm, but we can't use the
  69   // recursive algorithm due to stack depth issues.  Keep it here for
  70   // documentation purposes.
  71 #if 0
  72   VInfo.Semi = ++N;
  73   VInfo.Label = V;
  74
  75   Vertex.push_back(V);        // Vertex[n] = V;
  76   //Info[V].Ancestor = 0;     // Ancestor[n] = 0
  77   //Info[V].Child = 0;        // Child[v] = 0
  78   VInfo.Size = 1;             // Size[v] = 1
  79
  80   for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
  81     InfoRec &SuccVInfo = Info[*SI];
  82     if (SuccVInfo.Semi == 0) {
  83       SuccVInfo.Parent = V;
  84       N = DFSPass(*SI, SuccVInfo, N);
  85     }
  86   }
  87 #else
  88   std::vector<std::pair<BasicBlock*, unsigned> > Worklist;
  89   Worklist.push_back(std::make_pair(V, 0U));
  90   while (!Worklist.empty()) {
  91     BasicBlock *BB = Worklist.back().first;
  92     unsigned NextSucc = Worklist.back().second;
  93
  94     // First time we visited this BB?
  95     if (NextSucc == 0) {
  96       InfoRec &BBInfo = Info[BB];
  97       BBInfo.Semi = ++N;
  98       BBInfo.Label = BB;
  99
 100       Vertex.push_back(BB);       // Vertex[n] = V;
 101       //BBInfo[V].Ancestor = 0;   // Ancestor[n] = 0
 102       //BBInfo[V].Child = 0;      // Child[v] = 0
 103       BBInfo.Size = 1;            // Size[v] = 1
 104     }
 105
 106     // If we are done with this block, remove it from the worklist.
 107     if (NextSucc == BB->getTerminator()->getNumSuccessors()) {
 108       Worklist.pop_back();
 109       continue;
 110     }
 111
 112     // Otherwise, increment the successor number for the next time we get to it.
 113     ++Worklist.back().second;
 114
 115     // Visit the successor next, if it isn't already visited.
 116     BasicBlock *Succ = BB->getTerminator()->getSuccessor(NextSucc);
 117
 118     InfoRec &SuccVInfo = Info[Succ];
 119     if (SuccVInfo.Semi == 0) {
 120       SuccVInfo.Parent = BB;
 121       Worklist.push_back(std::make_pair(Succ, 0U));
 122     }
 123   }
 124 #endif
 125   return N;
 126 }
 127
 128 void DominatorTree::Compress(BasicBlock *VIn) {
 129
 130   std::vector<BasicBlock *> Work;
 131   std::set<BasicBlock *> Visited;
 132   InfoRec &VInInfo = Info[VIn];
 133   BasicBlock *VInAncestor = VInInfo.Ancestor;
 134   InfoRec &VInVAInfo = Info[VInAncestor];
 135
 136   if (VInVAInfo.Ancestor != 0)
 137     Work.push_back(VIn);
 138
 139   while (!Work.empty()) {
 140     BasicBlock *V = Work.back();
 141     InfoRec &VInfo = Info[V];
 142     BasicBlock *VAncestor = VInfo.Ancestor;
 143     InfoRec &VAInfo = Info[VAncestor];
 144
 145     // Process Ancestor first
 146     if (Visited.count(VAncestor) == 0 && VAInfo.Ancestor != 0) {
 147       Work.push_back(VAncestor);
 148       Visited.insert(VAncestor);
 149       continue;
 150     }
 151     Work.pop_back();
 152
 153     // Update VINfo based on Ancestor info
 154     if (VAInfo.Ancestor == 0)
 155       continue;
 156     BasicBlock *VAncestorLabel = VAInfo.Label;
 157     BasicBlock *VLabel = VInfo.Label;
 158     if (Info[VAncestorLabel].Semi < Info[VLabel].Semi)
 159       VInfo.Label = VAncestorLabel;
 160     VInfo.Ancestor = VAInfo.Ancestor;
 161   }
 162 }
 163
 164 BasicBlock *DominatorTree::Eval(BasicBlock *V) {
 165   InfoRec &VInfo = Info[V];
 166 #if !BALANCE_IDOM_TREE
 167   // Higher-complexity but faster implementation
 168   if (VInfo.Ancestor == 0)
 169     return V;
 170   Compress(V);
 171   return VInfo.Label;
 172 #else
 173   // Lower-complexity but slower implementation
 174   if (VInfo.Ancestor == 0)
 175     return VInfo.Label;
 176   Compress(V);
 177   BasicBlock *VLabel = VInfo.Label;
 178
 179   BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label;
 180   if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi)
 181     return VLabel;
 182   else
 183     return VAncestorLabel;
 184 #endif
 185 }
 186
 187 void DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
 188 #if !BALANCE_IDOM_TREE
 189   // Higher-complexity but faster implementation
 190   WInfo.Ancestor = V;
 191 #else
 192   // Lower-complexity but slower implementation
 193   BasicBlock *WLabel = WInfo.Label;
 194   unsigned WLabelSemi = Info[WLabel].Semi;
 195   BasicBlock *S = W;
 196   InfoRec *SInfo = &Info[S];
 197
 198   BasicBlock *SChild = SInfo->Child;
 199   InfoRec *SChildInfo = &Info[SChild];
 200
 201   while (WLabelSemi < Info[SChildInfo->Label].Semi) {
 202     BasicBlock *SChildChild = SChildInfo->Child;
 203     if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) {
 204       SChildInfo->Ancestor = S;
 205       SInfo->Child = SChild = SChildChild;
 206       SChildInfo = &Info[SChild];
 207     } else {
 208       SChildInfo->Size = SInfo->Size;
 209       S = SInfo->Ancestor = SChild;
 210       SInfo = SChildInfo;
 211       SChild = SChildChild;
 212       SChildInfo = &Info[SChild];
 213     }
 214   }
 215
 216   InfoRec &VInfo = Info[V];
 217   SInfo->Label = WLabel;
 218
 219   assert(V != W && "The optimization here will not work in this case!");
 220   unsigned WSize = WInfo.Size;
 221   unsigned VSize = (VInfo.Size += WSize);
 222
 223   if (VSize < 2*WSize)
 224     std::swap(S, VInfo.Child);
 225
 226   while (S) {
 227     SInfo = &Info[S];
 228     SInfo->Ancestor = V;
 229     S = SInfo->Child;
 230   }
 231 #endif
 232 }
 233
 234 void DominatorTree::calculate(Function& F) {
 235   BasicBlock* Root = Roots[0];
 236
 237   // Add a node for the root...
 238   DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0);
 239
 240   Vertex.push_back(0);
 241
 242   // Step #1: Number blocks in depth-first order and initialize variables used
 243   // in later stages of the algorithm.
 244   unsigned N = 0;
 245   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
 246     N = DFSPass(Roots[i], Info[Roots[i]], 0);
 247
 248   for (unsigned i = N; i >= 2; --i) {
 249     BasicBlock *W = Vertex[i];
 250     InfoRec &WInfo = Info[W];
 251
 252     // Step #2: Calculate the semidominators of all vertices
 253     for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI)
 254       if (Info.count(*PI)) {  // Only if this predecessor is reachable!
 255         unsigned SemiU = Info[Eval(*PI)].Semi;
 256         if (SemiU < WInfo.Semi)
 257           WInfo.Semi = SemiU;
 258       }
 259
 260     Info[Vertex[WInfo.Semi]].Bucket.push_back(W);
 261
 262     BasicBlock *WParent = WInfo.Parent;
 263     Link(WParent, W, WInfo);
 264
 265     // Step #3: Implicitly define the immediate dominator of vertices
 266     std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket;
 267     while (!WParentBucket.empty()) {
 268       BasicBlock *V = WParentBucket.back();
 269       WParentBucket.pop_back();
 270       BasicBlock *U = Eval(V);
 271       IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent;
 272     }
 273   }
 274
 275   // Step #4: Explicitly define the immediate dominator of each vertex
 276   for (unsigned i = 2; i <= N; ++i) {
 277     BasicBlock *W = Vertex[i];
 278     BasicBlock *&WIDom = IDoms[W];
 279     if (WIDom != Vertex[Info[W].Semi])
 280       WIDom = IDoms[WIDom];
 281   }
 282
 283   // Loop over all of the reachable blocks in the function...
 284   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 285     if (BasicBlock *ImmDom = getIDom(I)) {  // Reachable block.
 286       DomTreeNode *&BBNode = DomTreeNodes[I];
 287       if (!BBNode) {  // Haven't calculated this node yet?
 288         // Get or calculate the node for the immediate dominator
 289         DomTreeNode *IDomNode = getNodeForBlock(ImmDom);
 290
 291         // Add a new tree node for this BasicBlock, and link it as a child of
 292         // IDomNode
 293         DomTreeNode *C = new DomTreeNode(I, IDomNode);
 294         DomTreeNodes[I] = C;
 295         BBNode = IDomNode->addChild(C);
 296       }
 297     }
 298
 299   // Free temporary memory used to construct idom's
 300   Info.clear();
 301   IDoms.clear();
 302   std::vector<BasicBlock*>().swap(Vertex);
 303
 304   updateDFSNumbers();
 305 }
 306
 307 void DominatorTreeBase::updateDFSNumbers()
 308 {
 309   int dfsnum = 0;
 310   // Iterate over all nodes in depth first order.
 311   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
 312     for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
 313            E = df_end(Roots[i]); I != E; ++I) {
 314       BasicBlock *BB = *I;
 315       DomTreeNode *BBNode = getNode(BB);
 316       if (BBNode) {
 317         if (!BBNode->getIDom())
 318           BBNode->assignDFSNumber(dfsnum);
 319       }
 320   }
 321   SlowQueries = 0;
 322   DFSInfoValid = true;
 323 }
 324
 325 /// isReachableFromEntry - Return true if A is dominated by the entry
 326 /// block of the function containing it.
 327 const bool DominatorTreeBase::isReachableFromEntry(BasicBlock* A) {
 328   return dominates(&A->getParent()->getEntryBlock(), A);
 329 }
 330
 331 // dominates - Return true if A dominates B. THis performs the
 332 // special checks necessary if A and B are in the same basic block.
 333 bool DominatorTreeBase::dominates(Instruction *A, Instruction *B) {
 334   BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
 335   if (BBA != BBB) return dominates(BBA, BBB);
 336
 337   // It is not possible to determine dominance between two PHI nodes
 338   // based on their ordering.
 339   if (isa<PHINode>(A) && isa<PHINode>(B))
 340     return false;
 341
 342   // Loop through the basic block until we find A or B.
 343   BasicBlock::iterator I = BBA->begin();
 344   for (; &*I != A && &*I != B; ++I) /*empty*/;
 345
 346   if(!IsPostDominators) {
 347     // A dominates B if it is found first in the basic block.
 348     return &*I == A;
 349   } else {
 350     // A post-dominates B if B is found first in the basic block.
 351     return &*I == B;
 352   }
 353 }
 354
 355 // DominatorTreeBase::reset - Free all of the tree node memory.
 356 //
 357 void DominatorTreeBase::reset() {
 358   for (DomTreeNodeMapType::iterator I = DomTreeNodes.begin(),
 359          E = DomTreeNodes.end(); I != E; ++I)
 360     delete I->second;
 361   DomTreeNodes.clear();
 362   IDoms.clear();
 363   Roots.clear();
 364   Vertex.clear();
 365   RootNode = 0;
 366 }
 367
 368 /// findNearestCommonDominator - Find nearest common dominator basic block
 369 /// for basic block A and B. If there is no such block then return NULL.
 370 BasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A,
 371                                                           BasicBlock *B) {
 372
 373   assert (!isPostDominator()
 374           && "This is not implemented for post dominators");
 375   assert (A->getParent() == B->getParent()
 376           && "Two blocks are not in same function");
 377
 378   // If either A or B is a entry block then it is nearest common dominator.
 379   BasicBlock &Entry  = A->getParent()->getEntryBlock();
 380   if (A == &Entry || B == &Entry)
 381     return &Entry;
 382
 383   // If B dominates A then B is nearest common dominator.
 384   if (dominates(B,A))
 385     return B;
 386
 387   // If A dominates B then A is nearest common dominator.
 388   if (dominates(A,B))
 389     return A;
 390
 391   DomTreeNode *NodeA = getNode(A);
 392   DomTreeNode *NodeB = getNode(B);
 393
 394   // Collect NodeA dominators set.
 395   SmallPtrSet<DomTreeNode*, 16> NodeADoms;
 396   NodeADoms.insert(NodeA);
 397   DomTreeNode *IDomA = NodeA->getIDom();
 398   while(IDomA) {
 399     NodeADoms.insert(IDomA);
 400     IDomA = IDomA->getIDom();
 401   }
 402
 403   // Walk NodeB immediate dominators chain and find common dominator node.
 404   DomTreeNode *IDomB = NodeB->getIDom();
 405   while(IDomB) {
 406     if (NodeADoms.count(IDomB) != 0)
 407       return IDomB->getBlock();
 408
 409     IDomB = IDomB->getIDom();
 410   }
 411
 412   return NULL;
 413 }
 414
 415 /// assignDFSNumber - Assign In and Out numbers while walking dominator tree
 416 /// in dfs order.
 417 void DomTreeNode::assignDFSNumber(int num) {
 418   std::vector<DomTreeNode *>  workStack;
 419   std::set<DomTreeNode *> visitedNodes;
 420
 421   workStack.push_back(this);
 422   visitedNodes.insert(this);
 423   this->DFSNumIn = num++;
 424
 425   while (!workStack.empty()) {
 426     DomTreeNode  *Node = workStack.back();
 427
 428     bool visitChild = false;
 429     for (std::vector<DomTreeNode*>::iterator DI = Node->begin(),
 430            E = Node->end(); DI != E && !visitChild; ++DI) {
 431       DomTreeNode *Child = *DI;
 432       if (visitedNodes.count(Child) == 0) {
 433         visitChild = true;
 434         Child->DFSNumIn = num++;
 435         workStack.push_back(Child);
 436         visitedNodes.insert(Child);
 437       }
 438     }
 439     if (!visitChild) {
 440       // If we reach here means all children are visited
 441       Node->DFSNumOut = num++;
 442       workStack.pop_back();
 443     }
 444   }
 445 }
 446
 447 void DomTreeNode::setIDom(DomTreeNode *NewIDom) {
 448   assert(IDom && "No immediate dominator?");
 449   if (IDom != NewIDom) {
 450     std::vector<DomTreeNode*>::iterator I =
 451       std::find(IDom->Children.begin(), IDom->Children.end(), this);
 452     assert(I != IDom->Children.end() &&
 453            "Not in immediate dominator children set!");
 454     // I am no longer your child...
 455     IDom->Children.erase(I);
 456
 457     // Switch to new dominator
 458     IDom = NewIDom;
 459     IDom->Children.push_back(this);
 460   }
 461 }
 462
 463 DomTreeNode *DominatorTree::getNodeForBlock(BasicBlock *BB) {
 464   DomTreeNode *&BBNode = DomTreeNodes[BB];
 465   if (BBNode) return BBNode;
 466
 467   // Haven't calculated this node yet?  Get or calculate the node for the
 468   // immediate dominator.
 469   BasicBlock *IDom = getIDom(BB);
 470   DomTreeNode *IDomNode = getNodeForBlock(IDom);
 471
 472   // Add a new tree node for this BasicBlock, and link it as a child of
 473   // IDomNode
 474   DomTreeNode *C = new DomTreeNode(BB, IDomNode);
 475   DomTreeNodes[BB] = C;
 476   return BBNode = IDomNode->addChild(C);
 477 }
 478
 479 static std::ostream &operator<<(std::ostream &o,
 480                                 const DomTreeNode *Node) {
 481   if (Node->getBlock())
 482     WriteAsOperand(o, Node->getBlock(), false);
 483   else
 484     o << " <<exit node>>";
 485   return o << "\n";
 486 }
 487
 488 static void PrintDomTree(const DomTreeNode *N, std::ostream &o,
 489                          unsigned Lev) {
 490   o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
 491   for (DomTreeNode::const_iterator I = N->begin(), E = N->end();
 492        I != E; ++I)
 493     PrintDomTree(*I, o, Lev+1);
 494 }
 495
 496 void DominatorTreeBase::print(std::ostream &o, const Module* ) const {
 497   o << "=============================--------------------------------\n"
 498     << "Inorder Dominator Tree:\n";
 499   PrintDomTree(getRootNode(), o, 1);
 500 }
 501
 502 void DominatorTreeBase::dump() {
 503   print (llvm::cerr);
 504 }
 505
 506 bool DominatorTree::runOnFunction(Function &F) {
 507   reset();     // Reset from the last time we were run...
 508   Roots.push_back(&F.getEntryBlock());
 509   calculate(F);
 510   return false;
 511 }
 512
 513 //===----------------------------------------------------------------------===//
 514 //  DominanceFrontier Implementation
 515 //===----------------------------------------------------------------------===//
 516
 517 char DominanceFrontier::ID = 0;
 518 static RegisterPass<DominanceFrontier>
 519 G("domfrontier", "Dominance Frontier Construction", true);
 520
 521 namespace {
 522   class DFCalculateWorkObject {
 523   public:
 524     DFCalculateWorkObject(BasicBlock *B, BasicBlock *P,
 525                           const DomTreeNode *N,
 526                           const DomTreeNode *PN)
 527     : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
 528     BasicBlock *currentBB;
 529     BasicBlock *parentBB;
 530     const DomTreeNode *Node;
 531     const DomTreeNode *parentNode;
 532   };
 533 }
 534
 535 const DominanceFrontier::DomSetType &
 536 DominanceFrontier::calculate(const DominatorTree &DT,
 537                              const DomTreeNode *Node) {
 538   BasicBlock *BB = Node->getBlock();
 539   DomSetType *Result = NULL;
 540
 541   std::vector<DFCalculateWorkObject> workList;
 542   SmallPtrSet<BasicBlock *, 32> visited;
 543
 544   workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL));
 545   do {
 546     DFCalculateWorkObject *currentW = &workList.back();
 547     assert (currentW && "Missing work object.");
 548
 549     BasicBlock *currentBB = currentW->currentBB;
 550     BasicBlock *parentBB = currentW->parentBB;
 551     const DomTreeNode *currentNode = currentW->Node;
 552     const DomTreeNode *parentNode = currentW->parentNode;
 553     assert (currentBB && "Invalid work object. Missing current Basic Block");
 554     assert (currentNode && "Invalid work object. Missing current Node");
 555     DomSetType &S = Frontiers[currentBB];
 556
 557     // Visit each block only once.
 558     if (visited.count(currentBB) == 0) {
 559       visited.insert(currentBB);
 560
 561       // Loop over CFG successors to calculate DFlocal[currentNode]
 562       for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB);
 563            SI != SE; ++SI) {
 564         // Does Node immediately dominate this successor?
 565         if (DT[*SI]->getIDom() != currentNode)
 566           S.insert(*SI);
 567       }
 568     }
 569
 570     // At this point, S is DFlocal.  Now we union in DFup's of our children...
 571     // Loop through and visit the nodes that Node immediately dominates (Node's
 572     // children in the IDomTree)
 573     bool visitChild = false;
 574     for (DomTreeNode::const_iterator NI = currentNode->begin(),
 575            NE = currentNode->end(); NI != NE; ++NI) {
 576       DomTreeNode *IDominee = *NI;
 577       BasicBlock *childBB = IDominee->getBlock();
 578       if (visited.count(childBB) == 0) {
 579         workList.push_back(DFCalculateWorkObject(childBB, currentBB,
 580                                                  IDominee, currentNode));
 581         visitChild = true;
 582       }
 583     }
 584
 585     // If all children are visited or there is any child then pop this block
 586     // from the workList.
 587     if (!visitChild) {
 588
 589       if (!parentBB) {
 590         Result = &S;
 591         break;
 592       }
 593
 594       DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
 595       DomSetType &parentSet = Frontiers[parentBB];
 596       for (; CDFI != CDFE; ++CDFI) {
 597         if (!DT.properlyDominates(parentNode, DT[*CDFI]))
 598           parentSet.insert(*CDFI);
 599       }
 600       workList.pop_back();
 601     }
 602
 603   } while (!workList.empty());
 604
 605   return *Result;
 606 }
 607
 608 void DominanceFrontierBase::print(std::ostream &o, const Module* ) const {
 609   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 610     o << "  DomFrontier for BB";
 611     if (I->first)
 612       WriteAsOperand(o, I->first, false);
 613     else
 614       o << " <<exit node>>";
 615     o << " is:\t" << I->second << "\n";
 616   }
 617 }
 618
 619 void DominanceFrontierBase::dump() {
 620   print (llvm::cerr);
 621 }
 622
 623
 624 //===----------------------------------------------------------------------===//
 625 // ETOccurrence Implementation
 626 //===----------------------------------------------------------------------===//
 627
 628 void ETOccurrence::Splay() {
 629   ETOccurrence *father;
 630   ETOccurrence *grandfather;
 631   int occdepth;
 632   int fatherdepth;
 633
 634   while (Parent) {
 635     occdepth = Depth;
 636
 637     father = Parent;
 638     fatherdepth = Parent->Depth;
 639     grandfather = father->Parent;
 640
 641     // If we have no grandparent, a single zig or zag will do.
 642     if (!grandfather) {
 643       setDepthAdd(fatherdepth);
 644       MinOccurrence = father->MinOccurrence;
 645       Min = father->Min;
 646
 647       // See what we have to rotate
 648       if (father->Left == this) {
 649         // Zig
 650         father->setLeft(Right);
 651         setRight(father);
 652         if (father->Left)
 653           father->Left->setDepthAdd(occdepth);
 654       } else {
 655         // Zag
 656         father->setRight(Left);
 657         setLeft(father);
 658         if (father->Right)
 659           father->Right->setDepthAdd(occdepth);
 660       }
 661       father->setDepth(-occdepth);
 662       Parent = NULL;
 663
 664       father->recomputeMin();
 665       return;
 666     }
 667
 668     // If we have a grandfather, we need to do some
 669     // combination of zig and zag.
 670     int grandfatherdepth = grandfather->Depth;
 671
 672     setDepthAdd(fatherdepth + grandfatherdepth);
 673     MinOccurrence = grandfather->MinOccurrence;
 674     Min = grandfather->Min;
 675
 676     ETOccurrence *greatgrandfather = grandfather->Parent;
 677
 678     if (grandfather->Left == father) {
 679       if (father->Left == this) {
 680         // Zig zig
 681         grandfather->setLeft(father->Right);
 682         father->setLeft(Right);
 683         setRight(father);
 684         father->setRight(grandfather);
 685
 686         father->setDepth(-occdepth);
 687
 688         if (father->Left)
 689           father->Left->setDepthAdd(occdepth);
 690
 691         grandfather->setDepth(-fatherdepth);
 692         if (grandfather->Left)
 693           grandfather->Left->setDepthAdd(fatherdepth);
 694       } else {
 695         // Zag zig
 696         grandfather->setLeft(Right);
 697         father->setRight(Left);
 698         setLeft(father);
 699         setRight(grandfather);
 700
 701         father->setDepth(-occdepth);
 702         if (father->Right)
 703           father->Right->setDepthAdd(occdepth);
 704         grandfather->setDepth(-occdepth - fatherdepth);
 705         if (grandfather->Left)
 706           grandfather->Left->setDepthAdd(occdepth + fatherdepth);
 707       }
 708     } else {
 709       if (father->Left == this) {
 710         // Zig zag
 711         grandfather->setRight(Left);
 712         father->setLeft(Right);
 713         setLeft(grandfather);
 714         setRight(father);
 715
 716         father->setDepth(-occdepth);
 717         if (father->Left)
 718           father->Left->setDepthAdd(occdepth);
 719         grandfather->setDepth(-occdepth - fatherdepth);
 720         if (grandfather->Right)
 721           grandfather->Right->setDepthAdd(occdepth + fatherdepth);
 722       } else {              // Zag Zag
 723         grandfather->setRight(father->Left);
 724         father->setRight(Left);
 725         setLeft(father);
 726         father->setLeft(grandfather);
 727
 728         father->setDepth(-occdepth);
 729         if (father->Right)
 730           father->Right->setDepthAdd(occdepth);
 731         grandfather->setDepth(-fatherdepth);
 732         if (grandfather->Right)
 733           grandfather->Right->setDepthAdd(fatherdepth);
 734       }
 735     }
 736
 737     // Might need one more rotate depending on greatgrandfather.
 738     setParent(greatgrandfather);
 739     if (greatgrandfather) {
 740       if (greatgrandfather->Left == grandfather)
 741         greatgrandfather->Left = this;
 742       else
 743         greatgrandfather->Right = this;
 744
 745     }
 746     grandfather->recomputeMin();
 747     father->recomputeMin();
 748   }
 749 }
 750
 751 //===----------------------------------------------------------------------===//
 752 // ETNode implementation
 753 //===----------------------------------------------------------------------===//
 754
 755 void ETNode::Split() {
 756   ETOccurrence *right, *left;
 757   ETOccurrence *rightmost = RightmostOcc;
 758   ETOccurrence *parent;
 759
 760   // Update the occurrence tree first.
 761   RightmostOcc->Splay();
 762
 763   // Find the leftmost occurrence in the rightmost subtree, then splay
 764   // around it.
 765   for (right = rightmost->Right; right->Left; right = right->Left);
 766
 767   right->Splay();
 768
 769   // Start splitting
 770   right->Left->Parent = NULL;
 771   parent = ParentOcc;
 772   parent->Splay();
 773   ParentOcc = NULL;
 774
 775   left = parent->Left;
 776   parent->Right->Parent = NULL;
 777
 778   right->setLeft(left);
 779
 780   right->recomputeMin();
 781
 782   rightmost->Splay();
 783   rightmost->Depth = 0;
 784   rightmost->Min = 0;
 785
 786   delete parent;
 787
 788   // Now update *our* tree
 789
 790   if (Father->Son == this)
 791     Father->Son = Right;
 792
 793   if (Father->Son == this)
 794     Father->Son = NULL;
 795   else {
 796     Left->Right = Right;
 797     Right->Left = Left;
 798   }
 799   Left = Right = NULL;
 800   Father = NULL;
 801 }
 802
 803 void ETNode::setFather(ETNode *NewFather) {
 804   ETOccurrence *rightmost;
 805   ETOccurrence *leftpart;
 806   ETOccurrence *NewFatherOcc;
 807   ETOccurrence *temp;
 808
 809   // First update the path in the splay tree
 810   NewFatherOcc = new ETOccurrence(NewFather);
 811
 812   rightmost = NewFather->RightmostOcc;
 813   rightmost->Splay();
 814
 815   leftpart = rightmost->Left;
 816
 817   temp = RightmostOcc;
 818   temp->Splay();
 819
 820   NewFatherOcc->setLeft(leftpart);
 821   NewFatherOcc->setRight(temp);
 822
 823   temp->Depth++;
 824   temp->Min++;
 825   NewFatherOcc->recomputeMin();
 826
 827   rightmost->setLeft(NewFatherOcc);
 828
 829   if (NewFatherOcc->Min + rightmost->Depth < rightmost->Min) {
 830     rightmost->Min = NewFatherOcc->Min + rightmost->Depth;
 831     rightmost->MinOccurrence = NewFatherOcc->MinOccurrence;
 832   }
 833
 834   delete ParentOcc;
 835   ParentOcc = NewFatherOcc;
 836
 837   // Update *our* tree
 838   ETNode *left;
 839   ETNode *right;
 840
 841   Father = NewFather;
 842   right = Father->Son;
 843
 844   if (right)
 845     left = right->Left;
 846   else
 847     left = right = this;
 848
 849   left->Right = this;
 850   right->Left = this;
 851   Left = left;
 852   Right = right;
 853
 854   Father->Son = this;
 855 }
 856
 857 bool ETNode::Below(ETNode *other) {
 858   ETOccurrence *up = other->RightmostOcc;
 859   ETOccurrence *down = RightmostOcc;
 860
 861   if (this == other)
 862     return true;
 863
 864   up->Splay();
 865
 866   ETOccurrence *left, *right;
 867   left = up->Left;
 868   right = up->Right;
 869
 870   if (!left)
 871     return false;
 872
 873   left->Parent = NULL;
 874
 875   if (right)
 876     right->Parent = NULL;
 877
 878   down->Splay();
 879
 880   if (left == down || left->Parent != NULL) {
 881     if (right)
 882       right->Parent = up;
 883     up->setLeft(down);
 884   } else {
 885     left->Parent = up;
 886
 887     // If the two occurrences are in different trees, put things
 888     // back the way they were.
 889     if (right && right->Parent != NULL)
 890       up->setRight(down);
 891     else
 892       up->setRight(right);
 893     return false;
 894   }
 895
 896   if (down->Depth <= 0)
 897     return false;
 898
 899   return !down->Right || down->Right->Min + down->Depth >= 0;
 900 }
 901
 902 ETNode *ETNode::NCA(ETNode *other) {
 903   ETOccurrence *occ1 = RightmostOcc;
 904   ETOccurrence *occ2 = other->RightmostOcc;
 905
 906   ETOccurrence *left, *right, *ret;
 907   ETOccurrence *occmin;
 908   int mindepth;
 909
 910   if (this == other)
 911     return this;
 912
 913   occ1->Splay();
 914   left = occ1->Left;
 915   right = occ1->Right;
 916
 917   if (left)
 918     left->Parent = NULL;
 919
 920   if (right)
 921     right->Parent = NULL;
 922   occ2->Splay();
 923
 924   if (left == occ2 || (left && left->Parent != NULL)) {
 925     ret = occ2->Right;
 926
 927     occ1->setLeft(occ2);
 928     if (right)
 929       right->Parent = occ1;
 930   } else {
 931     ret = occ2->Left;
 932
 933     occ1->setRight(occ2);
 934     if (left)
 935       left->Parent = occ1;
 936   }
 937
 938   if (occ2->Depth > 0) {
 939     occmin = occ1;
 940     mindepth = occ1->Depth;
 941   } else {
 942     occmin = occ2;
 943     mindepth = occ2->Depth + occ1->Depth;
 944   }
 945
 946   if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth)
 947     return ret->MinOccurrence->OccFor;
 948   else
 949     return occmin->OccFor;
 950 }
 951
 952 void ETNode::assignDFSNumber(int num) {
 953   std::vector<ETNode *>  workStack;
 954   std::set<ETNode *> visitedNodes;
 955
 956   workStack.push_back(this);
 957   visitedNodes.insert(this);
 958   this->DFSNumIn = num++;
 959
 960   while (!workStack.empty()) {
 961     ETNode  *Node = workStack.back();
 962
 963     // If this is leaf node then set DFSNumOut and pop the stack
 964     if (!Node->Son) {
 965       Node->DFSNumOut = num++;
 966       workStack.pop_back();
 967       continue;
 968     }
 969
 970     ETNode *son = Node->Son;
 971
 972     // Visit Node->Son first
 973     if (visitedNodes.count(son) == 0) {
 974       son->DFSNumIn = num++;
 975       workStack.push_back(son);
 976       visitedNodes.insert(son);
 977       continue;
 978     }
 979
 980     bool visitChild = false;
 981     // Visit remaining children
 982     for (ETNode *s = son->Right;  s != son && !visitChild; s = s->Right) {
 983       if (visitedNodes.count(s) == 0) {
 984         visitChild = true;
 985         s->DFSNumIn = num++;
 986         workStack.push_back(s);
 987         visitedNodes.insert(s);
 988       }
 989     }
 990
 991     if (!visitChild) {
 992       // If we reach here means all children are visited
 993       Node->DFSNumOut = num++;
 994       workStack.pop_back();
 995     }
 996   }
 997 }
 998
 999 //===----------------------------------------------------------------------===//
1000 // ETForest implementation
1001 //===----------------------------------------------------------------------===//
1002
1003 char ETForest::ID = 0;
1004 static RegisterPass<ETForest>
1005 D("etforest", "ET Forest Construction", true);
1006
1007 void ETForestBase::reset() {
1008   for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
1009     delete I->second;
1010   Nodes.clear();
1011 }
1012
1013 void ETForestBase::updateDFSNumbers()
1014 {
1015   int dfsnum = 0;
1016   // Iterate over all nodes in depth first order.
1017   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
1018     for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
1019            E = df_end(Roots[i]); I != E; ++I) {
1020       BasicBlock *BB = *I;
1021       ETNode *ETN = getNode(BB);
1022       if (ETN && !ETN->hasFather())
1023         ETN->assignDFSNumber(dfsnum);
1024   }
1025   SlowQueries = 0;
1026   DFSInfoValid = true;
1027 }
1028
1029 // dominates - Return true if A dominates B. THis performs the
1030 // special checks necessary if A and B are in the same basic block.
1031 bool ETForestBase::dominates(Instruction *A, Instruction *B) {
1032   BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
1033   if (BBA != BBB) return dominates(BBA, BBB);
1034
1035   // It is not possible to determine dominance between two PHI nodes
1036   // based on their ordering.
1037   if (isa<PHINode>(A) && isa<PHINode>(B))
1038     return false;
1039
1040   // Loop through the basic block until we find A or B.
1041   BasicBlock::iterator I = BBA->begin();
1042   for (; &*I != A && &*I != B; ++I) /*empty*/;
1043
1044   if(!IsPostDominators) {
1045     // A dominates B if it is found first in the basic block.
1046     return &*I == A;
1047   } else {
1048     // A post-dominates B if B is found first in the basic block.
1049     return &*I == B;
1050   }
1051 }
1052
1053 /// isReachableFromEntry - Return true if A is dominated by the entry
1054 /// block of the function containing it.
1055 const bool ETForestBase::isReachableFromEntry(BasicBlock* A) {
1056   return dominates(&A->getParent()->getEntryBlock(), A);
1057 }
1058
1059 // FIXME : There is no need to make getNodeForBlock public. Fix
1060 // predicate simplifier.
1061 ETNode *ETForest::getNodeForBlock(BasicBlock *BB) {
1062   ETNode *&BBNode = Nodes[BB];
1063   if (BBNode) return BBNode;
1064
1065   // Haven't calculated this node yet?  Get or calculate the node for the
1066   // immediate dominator.
1067   DomTreeNode *node= getAnalysis<DominatorTree>().getNode(BB);
1068
1069   // If we are unreachable, we may not have an immediate dominator.
1070   if (!node || !node->getIDom())
1071     return BBNode = new ETNode(BB);
1072   else {
1073     ETNode *IDomNode = getNodeForBlock(node->getIDom()->getBlock());
1074
1075     // Add a new tree node for this BasicBlock, and link it as a child of
1076     // IDomNode
1077     BBNode = new ETNode(BB);
1078     BBNode->setFather(IDomNode);
1079     return BBNode;
1080   }
1081 }
1082
1083 void ETForest::calculate(const DominatorTree &DT) {
1084   assert(Roots.size() == 1 && "ETForest should have 1 root block!");
1085   BasicBlock *Root = Roots[0];
1086   Nodes[Root] = new ETNode(Root); // Add a node for the root
1087
1088   Function *F = Root->getParent();
1089   // Loop over all of the reachable blocks in the function...
1090   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
1091     DomTreeNode* node = DT.getNode(I);
1092     if (node && node->getIDom()) {  // Reachable block.
1093       BasicBlock* ImmDom = node->getIDom()->getBlock();
1094       ETNode *&BBNode = Nodes[I];
1095       if (!BBNode) {  // Haven't calculated this node yet?
1096         // Get or calculate the node for the immediate dominator
1097         ETNode *IDomNode =  getNodeForBlock(ImmDom);
1098
1099         // Add a new ETNode for this BasicBlock, and set it's parent
1100         // to it's immediate dominator.
1101         BBNode = new ETNode(I);
1102         BBNode->setFather(IDomNode);
1103       }
1104     }
1105   }
1106
1107   // Make sure we've got nodes around for every block
1108   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
1109     ETNode *&BBNode = Nodes[I];
1110     if (!BBNode)
1111       BBNode = new ETNode(I);
1112   }
1113
1114   updateDFSNumbers ();
1115 }
1116
1117 //===----------------------------------------------------------------------===//
1118 // ETForestBase Implementation
1119 //===----------------------------------------------------------------------===//
1120
1121 void ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
1122   ETNode *&BBNode = Nodes[BB];
1123   assert(!BBNode && "BasicBlock already in ET-Forest");
1124
1125   BBNode = new ETNode(BB);
1126   BBNode->setFather(getNode(IDom));
1127   DFSInfoValid = false;
1128 }
1129
1130 void ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) {
1131   assert(getNode(BB) && "BasicBlock not in ET-Forest");
1132   assert(getNode(newIDom) && "IDom not in ET-Forest");
1133
1134   ETNode *Node = getNode(BB);
1135   if (Node->hasFather()) {
1136     if (Node->getFather()->getData<BasicBlock>() == newIDom)
1137       return;
1138     Node->Split();
1139   }
1140   Node->setFather(getNode(newIDom));
1141   DFSInfoValid= false;
1142 }
1143
1144 void ETForestBase::print(std::ostream &o, const Module *) const {
1145   o << "=============================--------------------------------\n";
1146   o << "ET Forest:\n";
1147   o << "DFS Info ";
1148   if (DFSInfoValid)
1149     o << "is";
1150   else
1151     o << "is not";
1152   o << " up to date\n";
1153
1154   Function *F = getRoots()[0]->getParent();
1155   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
1156     o << "  DFS Numbers For Basic Block:";
1157     WriteAsOperand(o, I, false);
1158     o << " are:";
1159     if (ETNode *EN = getNode(I)) {
1160       o << "In: " << EN->getDFSNumIn();
1161       o << " Out: " << EN->getDFSNumOut() << "\n";
1162     } else {
1163       o << "No associated ETNode";
1164     }
1165     o << "\n";
1166   }
1167   o << "\n";
1168 }
1169
1170 void ETForestBase::dump() {
1171   print (llvm::cerr);
1172 }