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 <algorithm>
  23 #include <iostream>
  24 using namespace llvm;
  25
  26 //===----------------------------------------------------------------------===//
  27 //  ImmediateDominators Implementation
  28 //===----------------------------------------------------------------------===//
  29 //
  30 // Immediate Dominators construction - This pass constructs immediate dominator
  31 // information for a flow-graph based on the algorithm described in this
  32 // document:
  33 //
  34 //   A Fast Algorithm for Finding Dominators in a Flowgraph
  35 //   T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
  36 //
  37 // This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and
  38 // LINK, but it turns out that the theoretically slower O(n*log(n))
  39 // implementation is actually faster than the "efficient" algorithm (even for
  40 // large CFGs) because the constant overheads are substantially smaller.  The
  41 // lower-complexity version can be enabled with the following #define:
  42 //
  43 #define BALANCE_IDOM_TREE 0
  44 //
  45 //===----------------------------------------------------------------------===//
  46
  47 static RegisterPass<ImmediateDominators>
  48 C("idom", "Immediate Dominators Construction", true);
  49
  50 unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
  51                                       unsigned N) {
  52   VInfo.Semi = ++N;
  53   VInfo.Label = V;
  54
  55   Vertex.push_back(V);        // Vertex[n] = V;
  56   //Info[V].Ancestor = 0;     // Ancestor[n] = 0
  57   //Child[V] = 0;             // Child[v] = 0
  58   VInfo.Size = 1;             // Size[v] = 1
  59
  60   for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
  61     InfoRec &SuccVInfo = Info[*SI];
  62     if (SuccVInfo.Semi == 0) {
  63       SuccVInfo.Parent = V;
  64       N = DFSPass(*SI, SuccVInfo, N);
  65     }
  66   }
  67   return N;
  68 }
  69
  70 void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) {
  71   BasicBlock *VAncestor = VInfo.Ancestor;
  72   InfoRec &VAInfo = Info[VAncestor];
  73   if (VAInfo.Ancestor == 0)
  74     return;
  75
  76   Compress(VAncestor, VAInfo);
  77
  78   BasicBlock *VAncestorLabel = VAInfo.Label;
  79   BasicBlock *VLabel = VInfo.Label;
  80   if (Info[VAncestorLabel].Semi < Info[VLabel].Semi)
  81     VInfo.Label = VAncestorLabel;
  82
  83   VInfo.Ancestor = VAInfo.Ancestor;
  84 }
  85
  86 BasicBlock *ImmediateDominators::Eval(BasicBlock *V) {
  87   InfoRec &VInfo = Info[V];
  88 #if !BALANCE_IDOM_TREE
  89   // Higher-complexity but faster implementation
  90   if (VInfo.Ancestor == 0)
  91     return V;
  92   Compress(V, VInfo);
  93   return VInfo.Label;
  94 #else
  95   // Lower-complexity but slower implementation
  96   if (VInfo.Ancestor == 0)
  97     return VInfo.Label;
  98   Compress(V, VInfo);
  99   BasicBlock *VLabel = VInfo.Label;
 100
 101   BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label;
 102   if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi)
 103     return VLabel;
 104   else
 105     return VAncestorLabel;
 106 #endif
 107 }
 108
 109 void ImmediateDominators::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
 110 #if !BALANCE_IDOM_TREE
 111   // Higher-complexity but faster implementation
 112   WInfo.Ancestor = V;
 113 #else
 114   // Lower-complexity but slower implementation
 115   BasicBlock *WLabel = WInfo.Label;
 116   unsigned WLabelSemi = Info[WLabel].Semi;
 117   BasicBlock *S = W;
 118   InfoRec *SInfo = &Info[S];
 119
 120   BasicBlock *SChild = SInfo->Child;
 121   InfoRec *SChildInfo = &Info[SChild];
 122
 123   while (WLabelSemi < Info[SChildInfo->Label].Semi) {
 124     BasicBlock *SChildChild = SChildInfo->Child;
 125     if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) {
 126       SChildInfo->Ancestor = S;
 127       SInfo->Child = SChild = SChildChild;
 128       SChildInfo = &Info[SChild];
 129     } else {
 130       SChildInfo->Size = SInfo->Size;
 131       S = SInfo->Ancestor = SChild;
 132       SInfo = SChildInfo;
 133       SChild = SChildChild;
 134       SChildInfo = &Info[SChild];
 135     }
 136   }
 137
 138   InfoRec &VInfo = Info[V];
 139   SInfo->Label = WLabel;
 140
 141   assert(V != W && "The optimization here will not work in this case!");
 142   unsigned WSize = WInfo.Size;
 143   unsigned VSize = (VInfo.Size += WSize);
 144
 145   if (VSize < 2*WSize)
 146     std::swap(S, VInfo.Child);
 147
 148   while (S) {
 149     SInfo = &Info[S];
 150     SInfo->Ancestor = V;
 151     S = SInfo->Child;
 152   }
 153 #endif
 154 }
 155
 156
 157
 158 bool ImmediateDominators::runOnFunction(Function &F) {
 159   IDoms.clear();     // Reset from the last time we were run...
 160   BasicBlock *Root = &F.getEntryBlock();
 161   Roots.clear();
 162   Roots.push_back(Root);
 163
 164   Vertex.push_back(0);
 165
 166   // Step #1: Number blocks in depth-first order and initialize variables used
 167   // in later stages of the algorithm.
 168   unsigned N = 0;
 169   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
 170     N = DFSPass(Roots[i], Info[Roots[i]], 0);
 171
 172   for (unsigned i = N; i >= 2; --i) {
 173     BasicBlock *W = Vertex[i];
 174     InfoRec &WInfo = Info[W];
 175
 176     // Step #2: Calculate the semidominators of all vertices
 177     for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI)
 178       if (Info.count(*PI)) {  // Only if this predecessor is reachable!
 179         unsigned SemiU = Info[Eval(*PI)].Semi;
 180         if (SemiU < WInfo.Semi)
 181           WInfo.Semi = SemiU;
 182       }
 183
 184     Info[Vertex[WInfo.Semi]].Bucket.push_back(W);
 185
 186     BasicBlock *WParent = WInfo.Parent;
 187     Link(WParent, W, WInfo);
 188
 189     // Step #3: Implicitly define the immediate dominator of vertices
 190     std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket;
 191     while (!WParentBucket.empty()) {
 192       BasicBlock *V = WParentBucket.back();
 193       WParentBucket.pop_back();
 194       BasicBlock *U = Eval(V);
 195       IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent;
 196     }
 197   }
 198
 199   // Step #4: Explicitly define the immediate dominator of each vertex
 200   for (unsigned i = 2; i <= N; ++i) {
 201     BasicBlock *W = Vertex[i];
 202     BasicBlock *&WIDom = IDoms[W];
 203     if (WIDom != Vertex[Info[W].Semi])
 204       WIDom = IDoms[WIDom];
 205   }
 206
 207   // Free temporary memory used to construct idom's
 208   Info.clear();
 209   std::vector<BasicBlock*>().swap(Vertex);
 210
 211   return false;
 212 }
 213
 214 /// dominates - Return true if A dominates B.
 215 ///
 216 bool ImmediateDominatorsBase::dominates(BasicBlock *A, BasicBlock *B) const {
 217   assert(A && B && "Null pointers?");
 218
 219   // Walk up the dominator tree from B to determine if A dom B.
 220   while (A != B && B)
 221     B = get(B);
 222   return A == B;
 223 }
 224
 225 void ImmediateDominatorsBase::print(std::ostream &o, const Module* ) const {
 226   Function *F = getRoots()[0]->getParent();
 227   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
 228     o << "  Immediate Dominator For Basic Block:";
 229     WriteAsOperand(o, I, false);
 230     o << " is:";
 231     if (BasicBlock *ID = get(I))
 232       WriteAsOperand(o, ID, false);
 233     else
 234       o << " <<exit node>>";
 235     o << "\n";
 236   }
 237   o << "\n";
 238 }
 239
 240
 241
 242 //===----------------------------------------------------------------------===//
 243 //  DominatorSet Implementation
 244 //===----------------------------------------------------------------------===//
 245
 246 static RegisterPass<DominatorSet>
 247 B("domset", "Dominator Set Construction", true);
 248
 249 // dominates - Return true if A dominates B.  This performs the special checks
 250 // necessary if A and B are in the same basic block.
 251 //
 252 bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const {
 253   BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
 254   if (BBA != BBB) return dominates(BBA, BBB);
 255
 256   // Loop through the basic block until we find A or B.
 257   BasicBlock::iterator I = BBA->begin();
 258   for (; &*I != A && &*I != B; ++I) /*empty*/;
 259
 260   if(!IsPostDominators) {
 261     // A dominates B if it is found first in the basic block.
 262     return &*I == A;
 263   } else {
 264     // A post-dominates B if B is found first in the basic block.
 265     return &*I == B;
 266   }
 267 }
 268
 269
 270 // runOnFunction - This method calculates the forward dominator sets for the
 271 // specified function.
 272 //
 273 bool DominatorSet::runOnFunction(Function &F) {
 274   BasicBlock *Root = &F.getEntryBlock();
 275   Roots.clear();
 276   Roots.push_back(Root);
 277   assert(pred_begin(Root) == pred_end(Root) &&
 278          "Root node has predecessors in function!");
 279
 280   ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
 281   Doms.clear();
 282   if (Roots.empty()) return false;
 283
 284   // Root nodes only dominate themselves.
 285   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
 286     Doms[Roots[i]].insert(Roots[i]);
 287
 288   // Loop over all of the blocks in the function, calculating dominator sets for
 289   // each function.
 290   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 291     if (BasicBlock *IDom = ID[I]) {   // Get idom if block is reachable
 292       DomSetType &DS = Doms[I];
 293       assert(DS.empty() && "Domset already filled in for this block?");
 294       DS.insert(I);  // Blocks always dominate themselves
 295
 296       // Insert all dominators into the set...
 297       while (IDom) {
 298         // If we have already computed the dominator sets for our immediate
 299         // dominator, just use it instead of walking all the way up to the root.
 300         DomSetType &IDS = Doms[IDom];
 301         if (!IDS.empty()) {
 302           DS.insert(IDS.begin(), IDS.end());
 303           break;
 304         } else {
 305           DS.insert(IDom);
 306           IDom = ID[IDom];
 307         }
 308       }
 309     } else {
 310       // Ensure that every basic block has at least an empty set of nodes.  This
 311       // is important for the case when there is unreachable blocks.
 312       Doms[I];
 313     }
 314
 315   return false;
 316 }
 317
 318 namespace llvm {
 319 static std::ostream &operator<<(std::ostream &o,
 320                                 const std::set<BasicBlock*> &BBs) {
 321   for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
 322        I != E; ++I)
 323     if (*I)
 324       WriteAsOperand(o, *I, false);
 325     else
 326       o << " <<exit node>>";
 327   return o;
 328 }
 329 }
 330
 331 void DominatorSetBase::print(std::ostream &o, const Module* ) const {
 332   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 333     o << "  DomSet For BB: ";
 334     if (I->first)
 335       WriteAsOperand(o, I->first, false);
 336     else
 337       o << " <<exit node>>";
 338     o << " is:\t" << I->second << "\n";
 339   }
 340 }
 341
 342 //===----------------------------------------------------------------------===//
 343 //  DominatorTree Implementation
 344 //===----------------------------------------------------------------------===//
 345
 346 static RegisterPass<DominatorTree>
 347 E("domtree", "Dominator Tree Construction", true);
 348
 349 // DominatorTreeBase::reset - Free all of the tree node memory.
 350 //
 351 void DominatorTreeBase::reset() {
 352   for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
 353     delete I->second;
 354   Nodes.clear();
 355   RootNode = 0;
 356 }
 357
 358 void DominatorTreeBase::Node::setIDom(Node *NewIDom) {
 359   assert(IDom && "No immediate dominator?");
 360   if (IDom != NewIDom) {
 361     std::vector<Node*>::iterator I =
 362       std::find(IDom->Children.begin(), IDom->Children.end(), this);
 363     assert(I != IDom->Children.end() &&
 364            "Not in immediate dominator children set!");
 365     // I am no longer your child...
 366     IDom->Children.erase(I);
 367
 368     // Switch to new dominator
 369     IDom = NewIDom;
 370     IDom->Children.push_back(this);
 371   }
 372 }
 373
 374 DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) {
 375   Node *&BBNode = Nodes[BB];
 376   if (BBNode) return BBNode;
 377
 378   // Haven't calculated this node yet?  Get or calculate the node for the
 379   // immediate dominator.
 380   BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
 381   Node *IDomNode = getNodeForBlock(IDom);
 382
 383   // Add a new tree node for this BasicBlock, and link it as a child of
 384   // IDomNode
 385   return BBNode = IDomNode->addChild(new Node(BB, IDomNode));
 386 }
 387
 388 void DominatorTree::calculate(const ImmediateDominators &ID) {
 389   assert(Roots.size() == 1 && "DominatorTree should have 1 root block!");
 390   BasicBlock *Root = Roots[0];
 391   Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root...
 392
 393   Function *F = Root->getParent();
 394   // Loop over all of the reachable blocks in the function...
 395   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
 396     if (BasicBlock *ImmDom = ID.get(I)) {  // Reachable block.
 397       Node *&BBNode = Nodes[I];
 398       if (!BBNode) {  // Haven't calculated this node yet?
 399         // Get or calculate the node for the immediate dominator
 400         Node *IDomNode = getNodeForBlock(ImmDom);
 401
 402         // Add a new tree node for this BasicBlock, and link it as a child of
 403         // IDomNode
 404         BBNode = IDomNode->addChild(new Node(I, IDomNode));
 405       }
 406     }
 407 }
 408
 409 static std::ostream &operator<<(std::ostream &o,
 410                                 const DominatorTreeBase::Node *Node) {
 411   if (Node->getBlock())
 412     WriteAsOperand(o, Node->getBlock(), false);
 413   else
 414     o << " <<exit node>>";
 415   return o << "\n";
 416 }
 417
 418 static void PrintDomTree(const DominatorTreeBase::Node *N, std::ostream &o,
 419                          unsigned Lev) {
 420   o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
 421   for (DominatorTreeBase::Node::const_iterator I = N->begin(), E = N->end();
 422        I != E; ++I)
 423     PrintDomTree(*I, o, Lev+1);
 424 }
 425
 426 void DominatorTreeBase::print(std::ostream &o, const Module* ) const {
 427   o << "=============================--------------------------------\n"
 428     << "Inorder Dominator Tree:\n";
 429   PrintDomTree(getRootNode(), o, 1);
 430 }
 431
 432
 433 //===----------------------------------------------------------------------===//
 434 //  DominanceFrontier Implementation
 435 //===----------------------------------------------------------------------===//
 436
 437 static RegisterPass<DominanceFrontier>
 438 G("domfrontier", "Dominance Frontier Construction", true);
 439
 440 const DominanceFrontier::DomSetType &
 441 DominanceFrontier::calculate(const DominatorTree &DT,
 442                              const DominatorTree::Node *Node) {
 443   // Loop over CFG successors to calculate DFlocal[Node]
 444   BasicBlock *BB = Node->getBlock();
 445   DomSetType &S = Frontiers[BB];       // The new set to fill in...
 446
 447   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
 448        SI != SE; ++SI) {
 449     // Does Node immediately dominate this successor?
 450     if (DT[*SI]->getIDom() != Node)
 451       S.insert(*SI);
 452   }
 453
 454   // At this point, S is DFlocal.  Now we union in DFup's of our children...
 455   // Loop through and visit the nodes that Node immediately dominates (Node's
 456   // children in the IDomTree)
 457   //
 458   for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
 459        NI != NE; ++NI) {
 460     DominatorTree::Node *IDominee = *NI;
 461     const DomSetType &ChildDF = calculate(DT, IDominee);
 462
 463     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
 464     for (; CDFI != CDFE; ++CDFI) {
 465       if (!Node->properlyDominates(DT[*CDFI]))
 466         S.insert(*CDFI);
 467     }
 468   }
 469
 470   return S;
 471 }
 472
 473 void DominanceFrontierBase::print(std::ostream &o, const Module* ) const {
 474   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 475     o << "  DomFrontier for BB";
 476     if (I->first)
 477       WriteAsOperand(o, I->first, false);
 478     else
 479       o << " <<exit node>>";
 480     o << " is:\t" << I->second << "\n";
 481   }
 482 }
 483
 484 //===----------------------------------------------------------------------===//
 485 // ETOccurrence Implementation
 486 //===----------------------------------------------------------------------===//
 487
 488 void ETOccurrence::Splay() {
 489   ETOccurrence *father;
 490   ETOccurrence *grandfather;
 491   int occdepth;
 492   int fatherdepth;
 493
 494   while (Parent) {
 495     occdepth = Depth;
 496
 497     father = Parent;
 498     fatherdepth = Parent->Depth;
 499     grandfather = father->Parent;
 500
 501     // If we have no grandparent, a single zig or zag will do.
 502     if (!grandfather) {
 503       setDepthAdd(fatherdepth);
 504       MinOccurrence = father->MinOccurrence;
 505       Min = father->Min;
 506
 507       // See what we have to rotate
 508       if (father->Left == this) {
 509         // Zig
 510         father->setLeft(Right);
 511         setRight(father);
 512         if (father->Left)
 513           father->Left->setDepthAdd(occdepth);
 514       } else {
 515         // Zag
 516         father->setRight(Left);
 517         setLeft(father);
 518         if (father->Right)
 519           father->Right->setDepthAdd(occdepth);
 520       }
 521       father->setDepth(-occdepth);
 522       Parent = NULL;
 523
 524       father->recomputeMin();
 525       return;
 526     }
 527
 528     // If we have a grandfather, we need to do some
 529     // combination of zig and zag.
 530     int grandfatherdepth = grandfather->Depth;
 531
 532     setDepthAdd(fatherdepth + grandfatherdepth);
 533     MinOccurrence = grandfather->MinOccurrence;
 534     Min = grandfather->Min;
 535
 536     ETOccurrence *greatgrandfather = grandfather->Parent;
 537
 538     if (grandfather->Left == father) {
 539       if (father->Left == this) {
 540         // Zig zig
 541         grandfather->setLeft(father->Right);
 542         father->setLeft(Right);
 543         setRight(father);
 544         father->setRight(grandfather);
 545
 546         father->setDepth(-occdepth);
 547
 548         if (father->Left)
 549           father->Left->setDepthAdd(occdepth);
 550
 551         grandfather->setDepth(-fatherdepth);
 552         if (grandfather->Left)
 553           grandfather->Left->setDepthAdd(fatherdepth);
 554       } else {
 555         // Zag zig
 556         grandfather->setLeft(Right);
 557         father->setRight(Left);
 558         setLeft(father);
 559         setRight(grandfather);
 560
 561         father->setDepth(-occdepth);
 562         if (father->Right)
 563           father->Right->setDepthAdd(occdepth);
 564         grandfather->setDepth(-occdepth - fatherdepth);
 565         if (grandfather->Left)
 566           grandfather->Left->setDepthAdd(occdepth + fatherdepth);
 567       }
 568     } else {
 569       if (father->Left == this) {
 570         // Zig zag
 571         grandfather->setRight(Left);
 572         father->setLeft(Right);
 573         setLeft(grandfather);
 574         setRight(father);
 575
 576         father->setDepth(-occdepth);
 577         if (father->Left)
 578           father->Left->setDepthAdd(occdepth);
 579         grandfather->setDepth(-occdepth - fatherdepth);
 580         if (grandfather->Right)
 581           grandfather->Right->setDepthAdd(occdepth + fatherdepth);
 582       } else {              // Zag Zag
 583         grandfather->setRight(father->Left);
 584         father->setRight(Left);
 585         setLeft(father);
 586         father->setLeft(grandfather);
 587
 588         father->setDepth(-occdepth);
 589         if (father->Right)
 590           father->Right->setDepthAdd(occdepth);
 591         grandfather->setDepth(-fatherdepth);
 592         if (grandfather->Right)
 593           grandfather->Right->setDepthAdd(fatherdepth);
 594       }
 595     }
 596
 597     // Might need one more rotate depending on greatgrandfather.
 598     setParent(greatgrandfather);
 599     if (greatgrandfather) {
 600       if (greatgrandfather->Left == grandfather)
 601         greatgrandfather->Left = this;
 602       else
 603         greatgrandfather->Right = this;
 604
 605     }
 606     grandfather->recomputeMin();
 607     father->recomputeMin();
 608   }
 609 }
 610
 611 //===----------------------------------------------------------------------===//
 612 // ETNode implementation
 613 //===----------------------------------------------------------------------===//
 614
 615 void ETNode::Split() {
 616   ETOccurrence *right, *left;
 617   ETOccurrence *rightmost = RightmostOcc;
 618   ETOccurrence *parent;
 619
 620   // Update the occurrence tree first.
 621   RightmostOcc->Splay();
 622
 623   // Find the leftmost occurrence in the rightmost subtree, then splay
 624   // around it.
 625   for (right = rightmost->Right; right->Left; right = right->Left);
 626
 627   right->Splay();
 628
 629   // Start splitting
 630   right->Left->Parent = NULL;
 631   parent = ParentOcc;
 632   parent->Splay();
 633   ParentOcc = NULL;
 634
 635   left = parent->Left;
 636   parent->Right->Parent = NULL;
 637
 638   right->setLeft(left);
 639
 640   right->recomputeMin();
 641
 642   rightmost->Splay();
 643   rightmost->Depth = 0;
 644   rightmost->Min = 0;
 645
 646   delete parent;
 647
 648   // Now update *our* tree
 649
 650   if (Father->Son == this)
 651     Father->Son = Right;
 652
 653   if (Father->Son == this)
 654     Father->Son = NULL;
 655   else {
 656     Left->Right = Right;
 657     Right->Left = Left;
 658   }
 659   Left = Right = NULL;
 660   Father = NULL;
 661 }
 662
 663 void ETNode::setFather(ETNode *NewFather) {
 664   ETOccurrence *rightmost;
 665   ETOccurrence *leftpart;
 666   ETOccurrence *NewFatherOcc;
 667   ETOccurrence *temp;
 668
 669   // First update the path in the splay tree
 670   NewFatherOcc = new ETOccurrence(NewFather);
 671
 672   rightmost = NewFather->RightmostOcc;
 673   rightmost->Splay();
 674
 675   leftpart = rightmost->Left;
 676
 677   temp = RightmostOcc;
 678   temp->Splay();
 679
 680   NewFatherOcc->setLeft(leftpart);
 681   NewFatherOcc->setRight(temp);
 682
 683   temp->Depth++;
 684   temp->Min++;
 685   NewFatherOcc->recomputeMin();
 686
 687   rightmost->setLeft(NewFatherOcc);
 688
 689   if (NewFatherOcc->Min + rightmost->Depth < rightmost->Min) {
 690     rightmost->Min = NewFatherOcc->Min + rightmost->Depth;
 691     rightmost->MinOccurrence = NewFatherOcc->MinOccurrence;
 692   }
 693
 694   delete ParentOcc;
 695   ParentOcc = NewFatherOcc;
 696
 697   // Update *our* tree
 698   ETNode *left;
 699   ETNode *right;
 700
 701   Father = NewFather;
 702   right = Father->Son;
 703
 704   if (right)
 705     left = right->Left;
 706   else
 707     left = right = this;
 708
 709   left->Right = this;
 710   right->Left = this;
 711   Left = left;
 712   Right = right;
 713
 714   Father->Son = this;
 715 }
 716
 717 bool ETNode::Below(ETNode *other) {
 718   ETOccurrence *up = other->RightmostOcc;
 719   ETOccurrence *down = RightmostOcc;
 720
 721   if (this == other)
 722     return true;
 723
 724   up->Splay();
 725
 726   ETOccurrence *left, *right;
 727   left = up->Left;
 728   right = up->Right;
 729
 730   if (!left)
 731     return false;
 732
 733   left->Parent = NULL;
 734
 735   if (right)
 736     right->Parent = NULL;
 737
 738   down->Splay();
 739
 740   if (left == down || left->Parent != NULL) {
 741     if (right)
 742       right->Parent = up;
 743     up->setLeft(down);
 744   } else {
 745     left->Parent = up;
 746
 747     // If the two occurrences are in different trees, put things
 748     // back the way they were.
 749     if (right && right->Parent != NULL)
 750       up->setRight(down);
 751     else
 752       up->setRight(right);
 753     return false;
 754   }
 755
 756   if (down->Depth <= 0)
 757     return false;
 758
 759   return !down->Right || down->Right->Min + down->Depth >= 0;
 760 }
 761
 762 ETNode *ETNode::NCA(ETNode *other) {
 763   ETOccurrence *occ1 = RightmostOcc;
 764   ETOccurrence *occ2 = other->RightmostOcc;
 765
 766   ETOccurrence *left, *right, *ret;
 767   ETOccurrence *occmin;
 768   int mindepth;
 769
 770   if (this == other)
 771     return this;
 772
 773   occ1->Splay();
 774   left = occ1->Left;
 775   right = occ1->Right;
 776
 777   if (left)
 778     left->Parent = NULL;
 779
 780   if (right)
 781     right->Parent = NULL;
 782   occ2->Splay();
 783
 784   if (left == occ2 || (left && left->Parent != NULL)) {
 785     ret = occ2->Right;
 786
 787     occ1->setLeft(occ2);
 788     if (right)
 789       right->Parent = occ1;
 790   } else {
 791     ret = occ2->Left;
 792
 793     occ1->setRight(occ2);
 794     if (left)
 795       left->Parent = occ1;
 796   }
 797
 798   if (occ2->Depth > 0) {
 799     occmin = occ1;
 800     mindepth = occ1->Depth;
 801   } else {
 802     occmin = occ2;
 803     mindepth = occ2->Depth + occ1->Depth;
 804   }
 805
 806   if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth)
 807     return ret->MinOccurrence->OccFor;
 808   else
 809     return occmin->OccFor;
 810 }
 811
 812 void ETNode::assignDFSNumber(int num) {
 813   std::vector<ETNode *>  workStack;
 814   std::set<ETNode *> visitedNodes;
 815
 816   workStack.push_back(this);
 817   visitedNodes.insert(this);
 818   this->DFSNumIn = num++;
 819
 820   while (!workStack.empty()) {
 821     ETNode  *Node = workStack.back();
 822
 823     // If this is leaf node then set DFSNumOut and pop the stack
 824     if (!Node->Son) {
 825       Node->DFSNumOut = num++;
 826       workStack.pop_back();
 827       continue;
 828     }
 829
 830     ETNode *son = Node->Son;
 831
 832     // Visit Node->Son first
 833     if (visitedNodes.count(son) == 0) {
 834       son->DFSNumIn = num++;
 835       workStack.push_back(son);
 836       visitedNodes.insert(son);
 837       continue;
 838     }
 839
 840     bool visitChild = false;
 841     // Visit remaining children
 842     for (ETNode *s = son->Right;  s != son && !visitChild; s = s->Right) {
 843       if (visitedNodes.count(s) == 0) {
 844         visitChild = true;
 845         s->DFSNumIn = num++;
 846         workStack.push_back(s);
 847           visitedNodes.insert(s);
 848       }
 849     }
 850
 851     if (!visitChild) {
 852       // If we reach here means all children are visited
 853       Node->DFSNumOut = num++;
 854       workStack.pop_back();
 855     }
 856   }
 857 }
 858
 859 //===----------------------------------------------------------------------===//
 860 // ETForest implementation
 861 //===----------------------------------------------------------------------===//
 862
 863 static RegisterPass<ETForest>
 864 D("etforest", "ET Forest Construction", true);
 865
 866 void ETForestBase::reset() {
 867   for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
 868     delete I->second;
 869   Nodes.clear();
 870 }
 871
 872 void ETForestBase::updateDFSNumbers()
 873 {
 874   int dfsnum = 0;
 875   // Iterate over all nodes in depth first order.
 876   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
 877     for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
 878            E = df_end(Roots[i]); I != E; ++I) {
 879       BasicBlock *BB = *I;
 880       if (!getNode(BB)->hasFather())
 881         getNode(BB)->assignDFSNumber(dfsnum);
 882   }
 883   SlowQueries = 0;
 884   DFSInfoValid = true;
 885 }
 886
 887 ETNode *ETForest::getNodeForBlock(BasicBlock *BB) {
 888   ETNode *&BBNode = Nodes[BB];
 889   if (BBNode) return BBNode;
 890
 891   // Haven't calculated this node yet?  Get or calculate the node for the
 892   // immediate dominator.
 893   BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
 894
 895   // If we are unreachable, we may not have an immediate dominator.
 896   if (!IDom)
 897     return BBNode = new ETNode(BB);
 898   else {
 899     ETNode *IDomNode = getNodeForBlock(IDom);
 900
 901     // Add a new tree node for this BasicBlock, and link it as a child of
 902     // IDomNode
 903     BBNode = new ETNode(BB);
 904     BBNode->setFather(IDomNode);
 905     return BBNode;
 906   }
 907 }
 908
 909 void ETForest::calculate(const ImmediateDominators &ID) {
 910   assert(Roots.size() == 1 && "ETForest should have 1 root block!");
 911   BasicBlock *Root = Roots[0];
 912   Nodes[Root] = new ETNode(Root); // Add a node for the root
 913
 914   Function *F = Root->getParent();
 915   // Loop over all of the reachable blocks in the function...
 916   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
 917     if (BasicBlock *ImmDom = ID.get(I)) {  // Reachable block.
 918       ETNode *&BBNode = Nodes[I];
 919       if (!BBNode) {  // Haven't calculated this node yet?
 920         // Get or calculate the node for the immediate dominator
 921         ETNode *IDomNode =  getNodeForBlock(ImmDom);
 922
 923         // Add a new ETNode for this BasicBlock, and set it's parent
 924         // to it's immediate dominator.
 925         BBNode = new ETNode(I);
 926         BBNode->setFather(IDomNode);
 927       }
 928     }
 929
 930   // Make sure we've got nodes around for every block
 931   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
 932     ETNode *&BBNode = Nodes[I];
 933     if (!BBNode)
 934       BBNode = new ETNode(I);
 935   }
 936
 937   updateDFSNumbers ();
 938 }
 939
 940 //===----------------------------------------------------------------------===//
 941 // ETForestBase Implementation
 942 //===----------------------------------------------------------------------===//
 943
 944 void ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
 945   ETNode *&BBNode = Nodes[BB];
 946   assert(!BBNode && "BasicBlock already in ET-Forest");
 947
 948   BBNode = new ETNode(BB);
 949   BBNode->setFather(getNode(IDom));
 950   DFSInfoValid = false;
 951 }
 952
 953 void ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) {
 954   assert(getNode(BB) && "BasicBlock not in ET-Forest");
 955   assert(getNode(newIDom) && "IDom not in ET-Forest");
 956
 957   ETNode *Node = getNode(BB);
 958   if (Node->hasFather()) {
 959     if (Node->getFather()->getData<BasicBlock>() == newIDom)
 960       return;
 961     Node->Split();
 962   }
 963   Node->setFather(getNode(newIDom));
 964   DFSInfoValid= false;
 965 }
 966
 967 void ETForestBase::print(std::ostream &o, const Module *) const {
 968   o << "=============================--------------------------------\n";
 969   o << "ET Forest:\n";
 970   o << "DFS Info ";
 971   if (DFSInfoValid)
 972     o << "is";
 973   else
 974     o << "is not";
 975   o << " up to date\n";
 976
 977   Function *F = getRoots()[0]->getParent();
 978   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
 979     o << "  DFS Numbers For Basic Block:";
 980     WriteAsOperand(o, I, false);
 981     o << " are:";
 982     if (ETNode *EN = getNode(I)) {
 983       o << "In: " << EN->getDFSNumIn();
 984       o << " Out: " << EN->getDFSNumOut() << "\n";
 985     } else {
 986       o << "No associated ETNode";
 987     }
 988     o << "\n";
 989   }
 990   o << "\n";
 991 }
 992
 993 DEFINING_FILE_FOR(DominatorSet)