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