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