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