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