LLVM API Documentation

Dominators.cpp

Go to the documentation of this file.
00001 //===- Dominators.cpp - Dominator Calculation -----------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements simple dominator construction algorithms for finding
00011 // forward dominators.  Postdominators are available in libanalysis, but are not
00012 // included in libvmcore, because it's not needed.  Forward dominators are
00013 // needed to support the Verifier pass.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #include "llvm/Analysis/Dominators.h"
00018 #include "llvm/Support/CFG.h"
00019 #include "llvm/Assembly/Writer.h"
00020 #include "llvm/ADT/DepthFirstIterator.h"
00021 #include "llvm/ADT/SetOperations.h"
00022 #include <algorithm>
00023 #include <iostream>
00024 using namespace llvm;
00025 
00026 //===----------------------------------------------------------------------===//
00027 //  ImmediateDominators Implementation
00028 //===----------------------------------------------------------------------===//
00029 //
00030 // Immediate Dominators construction - This pass constructs immediate dominator
00031 // information for a flow-graph based on the algorithm described in this
00032 // document:
00033 //
00034 //   A Fast Algorithm for Finding Dominators in a Flowgraph
00035 //   T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
00036 //
00037 // This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and
00038 // LINK, but it turns out that the theoretically slower O(n*log(n))
00039 // implementation is actually faster than the "efficient" algorithm (even for
00040 // large CFGs) because the constant overheads are substantially smaller.  The
00041 // lower-complexity version can be enabled with the following #define:
00042 //
00043 #define BALANCE_IDOM_TREE 0
00044 //
00045 //===----------------------------------------------------------------------===//
00046 
00047 static RegisterAnalysis<ImmediateDominators>
00048 C("idom", "Immediate Dominators Construction", true);
00049 
00050 unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
00051                                       unsigned N) {
00052   VInfo.Semi = ++N;
00053   VInfo.Label = V;
00054 
00055   Vertex.push_back(V);        // Vertex[n] = V;
00056   //Info[V].Ancestor = 0;     // Ancestor[n] = 0
00057   //Child[V] = 0;             // Child[v] = 0
00058   VInfo.Size = 1;             // Size[v] = 1
00059 
00060   for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
00061     InfoRec &SuccVInfo = Info[*SI];
00062     if (SuccVInfo.Semi == 0) {
00063       SuccVInfo.Parent = V;
00064       N = DFSPass(*SI, SuccVInfo, N);
00065     }
00066   }
00067   return N;
00068 }
00069 
00070 void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) {
00071   BasicBlock *VAncestor = VInfo.Ancestor;
00072   InfoRec &VAInfo = Info[VAncestor];
00073   if (VAInfo.Ancestor == 0)
00074     return;
00075 
00076   Compress(VAncestor, VAInfo);
00077 
00078   BasicBlock *VAncestorLabel = VAInfo.Label;
00079   BasicBlock *VLabel = VInfo.Label;
00080   if (Info[VAncestorLabel].Semi < Info[VLabel].Semi)
00081     VInfo.Label = VAncestorLabel;
00082 
00083   VInfo.Ancestor = VAInfo.Ancestor;
00084 }
00085 
00086 BasicBlock *ImmediateDominators::Eval(BasicBlock *V) {
00087   InfoRec &VInfo = Info[V];
00088 #if !BALANCE_IDOM_TREE
00089   // Higher-complexity but faster implementation
00090   if (VInfo.Ancestor == 0)
00091     return V;
00092   Compress(V, VInfo);
00093   return VInfo.Label;
00094 #else
00095   // Lower-complexity but slower implementation
00096   if (VInfo.Ancestor == 0)
00097     return VInfo.Label;
00098   Compress(V, VInfo);
00099   BasicBlock *VLabel = VInfo.Label;
00100 
00101   BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label;
00102   if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi)
00103     return VLabel;
00104   else
00105     return VAncestorLabel;
00106 #endif
00107 }
00108 
00109 void ImmediateDominators::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
00110 #if !BALANCE_IDOM_TREE
00111   // Higher-complexity but faster implementation
00112   WInfo.Ancestor = V;
00113 #else
00114   // Lower-complexity but slower implementation
00115   BasicBlock *WLabel = WInfo.Label;
00116   unsigned WLabelSemi = Info[WLabel].Semi;
00117   BasicBlock *S = W;
00118   InfoRec *SInfo = &Info[S];
00119 
00120   BasicBlock *SChild = SInfo->Child;
00121   InfoRec *SChildInfo = &Info[SChild];
00122 
00123   while (WLabelSemi < Info[SChildInfo->Label].Semi) {
00124     BasicBlock *SChildChild = SChildInfo->Child;
00125     if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) {
00126       SChildInfo->Ancestor = S;
00127       SInfo->Child = SChild = SChildChild;
00128       SChildInfo = &Info[SChild];
00129     } else {
00130       SChildInfo->Size = SInfo->Size;
00131       S = SInfo->Ancestor = SChild;
00132       SInfo = SChildInfo;
00133       SChild = SChildChild;
00134       SChildInfo = &Info[SChild];
00135     }
00136   }
00137 
00138   InfoRec &VInfo = Info[V];
00139   SInfo->Label = WLabel;
00140 
00141   assert(V != W && "The optimization here will not work in this case!");
00142   unsigned WSize = WInfo.Size;
00143   unsigned VSize = (VInfo.Size += WSize);
00144 
00145   if (VSize < 2*WSize)
00146     std::swap(S, VInfo.Child);
00147 
00148   while (S) {
00149     SInfo = &Info[S];
00150     SInfo->Ancestor = V;
00151     S = SInfo->Child;
00152   }
00153 #endif
00154 }
00155 
00156 
00157 
00158 bool ImmediateDominators::runOnFunction(Function &F) {
00159   IDoms.clear();     // Reset from the last time we were run...
00160   BasicBlock *Root = &F.getEntryBlock();
00161   Roots.clear();
00162   Roots.push_back(Root);
00163 
00164   Vertex.push_back(0);
00165 
00166   // Step #1: Number blocks in depth-first order and initialize variables used
00167   // in later stages of the algorithm.
00168   unsigned N = 0;
00169   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
00170     N = DFSPass(Roots[i], Info[Roots[i]], 0);
00171 
00172   for (unsigned i = N; i >= 2; --i) {
00173     BasicBlock *W = Vertex[i];
00174     InfoRec &WInfo = Info[W];
00175 
00176     // Step #2: Calculate the semidominators of all vertices
00177     for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI)
00178       if (Info.count(*PI)) {  // Only if this predecessor is reachable!
00179         unsigned SemiU = Info[Eval(*PI)].Semi;
00180         if (SemiU < WInfo.Semi)
00181           WInfo.Semi = SemiU;
00182       }
00183 
00184     Info[Vertex[WInfo.Semi]].Bucket.push_back(W);
00185 
00186     BasicBlock *WParent = WInfo.Parent;
00187     Link(WParent, W, WInfo);
00188 
00189     // Step #3: Implicitly define the immediate dominator of vertices
00190     std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket;
00191     while (!WParentBucket.empty()) {
00192       BasicBlock *V = WParentBucket.back();
00193       WParentBucket.pop_back();
00194       BasicBlock *U = Eval(V);
00195       IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent;
00196     }
00197   }
00198 
00199   // Step #4: Explicitly define the immediate dominator of each vertex
00200   for (unsigned i = 2; i <= N; ++i) {
00201     BasicBlock *W = Vertex[i];
00202     BasicBlock *&WIDom = IDoms[W];
00203     if (WIDom != Vertex[Info[W].Semi])
00204       WIDom = IDoms[WIDom];
00205   }
00206 
00207   // Free temporary memory used to construct idom's
00208   Info.clear();
00209   std::vector<BasicBlock*>().swap(Vertex);
00210 
00211   return false;
00212 }
00213 
00214 void ImmediateDominatorsBase::print(std::ostream &o, const Module* ) const {
00215   Function *F = getRoots()[0]->getParent();
00216   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
00217     o << "  Immediate Dominator For Basic Block:";
00218     WriteAsOperand(o, I, false);
00219     o << " is:";
00220     if (BasicBlock *ID = get(I))
00221       WriteAsOperand(o, ID, false);
00222     else
00223       o << " <<exit node>>";
00224     o << "\n";
00225   }
00226   o << "\n";
00227 }
00228 
00229 
00230 
00231 //===----------------------------------------------------------------------===//
00232 //  DominatorSet Implementation
00233 //===----------------------------------------------------------------------===//
00234 
00235 static RegisterAnalysis<DominatorSet>
00236 B("domset", "Dominator Set Construction", true);
00237 
00238 // dominates - Return true if A dominates B.  This performs the special checks
00239 // necessary if A and B are in the same basic block.
00240 //
00241 bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const {
00242   BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
00243   if (BBA != BBB) return dominates(BBA, BBB);
00244 
00245   // Loop through the basic block until we find A or B.
00246   BasicBlock::iterator I = BBA->begin();
00247   for (; &*I != A && &*I != B; ++I) /*empty*/;
00248 
00249   if(!IsPostDominators) {
00250     // A dominates B if it is found first in the basic block.
00251     return &*I == A;
00252   } else {
00253     // A post-dominates B if B is found first in the basic block.
00254     return &*I == B;
00255   }
00256 }
00257 
00258 
00259 // runOnFunction - This method calculates the forward dominator sets for the
00260 // specified function.
00261 //
00262 bool DominatorSet::runOnFunction(Function &F) {
00263   BasicBlock *Root = &F.getEntryBlock();
00264   Roots.clear();
00265   Roots.push_back(Root);
00266   assert(pred_begin(Root) == pred_end(Root) &&
00267          "Root node has predecessors in function!");
00268 
00269   ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
00270   Doms.clear();
00271   if (Roots.empty()) return false;
00272 
00273   // Root nodes only dominate themselves.
00274   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
00275     Doms[Roots[i]].insert(Roots[i]);
00276 
00277   // Loop over all of the blocks in the function, calculating dominator sets for
00278   // each function.
00279   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
00280     if (BasicBlock *IDom = ID[I]) {   // Get idom if block is reachable
00281       DomSetType &DS = Doms[I];
00282       assert(DS.empty() && "Domset already filled in for this block?");
00283       DS.insert(I);  // Blocks always dominate themselves
00284 
00285       // Insert all dominators into the set...
00286       while (IDom) {
00287         // If we have already computed the dominator sets for our immediate
00288         // dominator, just use it instead of walking all the way up to the root.
00289         DomSetType &IDS = Doms[IDom];
00290         if (!IDS.empty()) {
00291           DS.insert(IDS.begin(), IDS.end());
00292           break;
00293         } else {
00294           DS.insert(IDom);
00295           IDom = ID[IDom];
00296         }
00297       }
00298     } else {
00299       // Ensure that every basic block has at least an empty set of nodes.  This
00300       // is important for the case when there is unreachable blocks.
00301       Doms[I];
00302     }
00303 
00304   return false;
00305 }
00306 
00307 void DominatorSet::stub() {}
00308 
00309 namespace llvm {
00310 static std::ostream &operator<<(std::ostream &o,
00311                                 const std::set<BasicBlock*> &BBs) {
00312   for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
00313        I != E; ++I)
00314     if (*I)
00315       WriteAsOperand(o, *I, false);
00316     else
00317       o << " <<exit node>>";
00318   return o;
00319 }
00320 }
00321 
00322 void DominatorSetBase::print(std::ostream &o, const Module* ) const {
00323   for (const_iterator I = begin(), E = end(); I != E; ++I) {
00324     o << "  DomSet For BB: ";
00325     if (I->first)
00326       WriteAsOperand(o, I->first, false);
00327     else
00328       o << " <<exit node>>";
00329     o << " is:\t" << I->second << "\n";
00330   }
00331 }
00332 
00333 //===----------------------------------------------------------------------===//
00334 //  DominatorTree Implementation
00335 //===----------------------------------------------------------------------===//
00336 
00337 static RegisterAnalysis<DominatorTree>
00338 E("domtree", "Dominator Tree Construction", true);
00339 
00340 // DominatorTreeBase::reset - Free all of the tree node memory.
00341 //
00342 void DominatorTreeBase::reset() {
00343   for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
00344     delete I->second;
00345   Nodes.clear();
00346   RootNode = 0;
00347 }
00348 
00349 void DominatorTreeBase::Node::setIDom(Node *NewIDom) {
00350   assert(IDom && "No immediate dominator?");
00351   if (IDom != NewIDom) {
00352     std::vector<Node*>::iterator I =
00353       std::find(IDom->Children.begin(), IDom->Children.end(), this);
00354     assert(I != IDom->Children.end() &&
00355            "Not in immediate dominator children set!");
00356     // I am no longer your child...
00357     IDom->Children.erase(I);
00358 
00359     // Switch to new dominator
00360     IDom = NewIDom;
00361     IDom->Children.push_back(this);
00362   }
00363 }
00364 
00365 DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) {
00366   Node *&BBNode = Nodes[BB];
00367   if (BBNode) return BBNode;
00368 
00369   // Haven't calculated this node yet?  Get or calculate the node for the
00370   // immediate dominator.
00371   BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
00372   Node *IDomNode = getNodeForBlock(IDom);
00373 
00374   // Add a new tree node for this BasicBlock, and link it as a child of
00375   // IDomNode
00376   return BBNode = IDomNode->addChild(new Node(BB, IDomNode));
00377 }
00378 
00379 void DominatorTree::calculate(const ImmediateDominators &ID) {
00380   assert(Roots.size() == 1 && "DominatorTree should have 1 root block!");
00381   BasicBlock *Root = Roots[0];
00382   Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root...
00383 
00384   Function *F = Root->getParent();
00385   // Loop over all of the reachable blocks in the function...
00386   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
00387     if (BasicBlock *ImmDom = ID.get(I)) {  // Reachable block.
00388       Node *&BBNode = Nodes[I];
00389       if (!BBNode) {  // Haven't calculated this node yet?
00390         // Get or calculate the node for the immediate dominator
00391         Node *IDomNode = getNodeForBlock(ImmDom);
00392 
00393         // Add a new tree node for this BasicBlock, and link it as a child of
00394         // IDomNode
00395         BBNode = IDomNode->addChild(new Node(I, IDomNode));
00396       }
00397     }
00398 }
00399 
00400 static std::ostream &operator<<(std::ostream &o,
00401                                 const DominatorTreeBase::Node *Node) {
00402   if (Node->getBlock())
00403     WriteAsOperand(o, Node->getBlock(), false);
00404   else
00405     o << " <<exit node>>";
00406   return o << "\n";
00407 }
00408 
00409 static void PrintDomTree(const DominatorTreeBase::Node *N, std::ostream &o,
00410                          unsigned Lev) {
00411   o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
00412   for (DominatorTreeBase::Node::const_iterator I = N->begin(), E = N->end();
00413        I != E; ++I)
00414     PrintDomTree(*I, o, Lev+1);
00415 }
00416 
00417 void DominatorTreeBase::print(std::ostream &o, const Module* ) const {
00418   o << "=============================--------------------------------\n"
00419     << "Inorder Dominator Tree:\n";
00420   PrintDomTree(getRootNode(), o, 1);
00421 }
00422 
00423 
00424 //===----------------------------------------------------------------------===//
00425 //  DominanceFrontier Implementation
00426 //===----------------------------------------------------------------------===//
00427 
00428 static RegisterAnalysis<DominanceFrontier>
00429 G("domfrontier", "Dominance Frontier Construction", true);
00430 
00431 const DominanceFrontier::DomSetType &
00432 DominanceFrontier::calculate(const DominatorTree &DT,
00433                              const DominatorTree::Node *Node) {
00434   // Loop over CFG successors to calculate DFlocal[Node]
00435   BasicBlock *BB = Node->getBlock();
00436   DomSetType &S = Frontiers[BB];       // The new set to fill in...
00437 
00438   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
00439        SI != SE; ++SI) {
00440     // Does Node immediately dominate this successor?
00441     if (DT[*SI]->getIDom() != Node)
00442       S.insert(*SI);
00443   }
00444 
00445   // At this point, S is DFlocal.  Now we union in DFup's of our children...
00446   // Loop through and visit the nodes that Node immediately dominates (Node's
00447   // children in the IDomTree)
00448   //
00449   for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
00450        NI != NE; ++NI) {
00451     DominatorTree::Node *IDominee = *NI;
00452     const DomSetType &ChildDF = calculate(DT, IDominee);
00453 
00454     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
00455     for (; CDFI != CDFE; ++CDFI) {
00456       if (!Node->properlyDominates(DT[*CDFI]))
00457         S.insert(*CDFI);
00458     }
00459   }
00460 
00461   return S;
00462 }
00463 
00464 void DominanceFrontierBase::print(std::ostream &o, const Module* ) const {
00465   for (const_iterator I = begin(), E = end(); I != E; ++I) {
00466     o << "  DomFrontier for BB";
00467     if (I->first)
00468       WriteAsOperand(o, I->first, false);
00469     else
00470       o << " <<exit node>>";
00471     o << " is:\t" << I->second << "\n";
00472   }
00473 }
00474 
00475 //===----------------------------------------------------------------------===//
00476 // ETOccurrence Implementation
00477 //===----------------------------------------------------------------------===//
00478 
00479 void ETOccurrence::Splay() {
00480   ETOccurrence *father;
00481   ETOccurrence *grandfather;
00482   int occdepth;
00483   int fatherdepth;
00484   
00485   while (Parent) {
00486     occdepth = Depth;
00487     
00488     father = Parent;
00489     fatherdepth = Parent->Depth;
00490     grandfather = father->Parent;
00491     
00492     // If we have no grandparent, a single zig or zag will do.
00493     if (!grandfather) {
00494       setDepthAdd(fatherdepth);
00495       MinOccurrence = father->MinOccurrence;
00496       Min = father->Min;
00497       
00498       // See what we have to rotate
00499       if (father->Left == this) {
00500         // Zig
00501         father->setLeft(Right);
00502         setRight(father);
00503         if (father->Left)
00504           father->Left->setDepthAdd(occdepth);
00505       } else {
00506         // Zag
00507         father->setRight(Left);
00508         setLeft(father);
00509         if (father->Right)
00510           father->Right->setDepthAdd(occdepth);
00511       }
00512       father->setDepth(-occdepth);
00513       Parent = NULL;
00514       
00515       father->recomputeMin();
00516       return;
00517     }
00518     
00519     // If we have a grandfather, we need to do some
00520     // combination of zig and zag.
00521     int grandfatherdepth = grandfather->Depth;
00522     
00523     setDepthAdd(fatherdepth + grandfatherdepth);
00524     MinOccurrence = grandfather->MinOccurrence;
00525     Min = grandfather->Min;
00526     
00527     ETOccurrence *greatgrandfather = grandfather->Parent;
00528     
00529     if (grandfather->Left == father) {
00530       if (father->Left == this) {
00531         // Zig zig
00532         grandfather->setLeft(father->Right);
00533         father->setLeft(Right);
00534         setRight(father);
00535         father->setRight(grandfather);
00536         
00537         father->setDepth(-occdepth);
00538         
00539         if (father->Left)
00540           father->Left->setDepthAdd(occdepth);
00541         
00542         grandfather->setDepth(-fatherdepth);
00543         if (grandfather->Left)
00544           grandfather->Left->setDepthAdd(fatherdepth);
00545       } else {
00546         // Zag zig
00547         grandfather->setLeft(Right);
00548         father->setRight(Left);
00549         setLeft(father);
00550         setRight(grandfather);
00551         
00552         father->setDepth(-occdepth);
00553         if (father->Right)
00554           father->Right->setDepthAdd(occdepth);
00555         grandfather->setDepth(-occdepth - fatherdepth);
00556         if (grandfather->Left)
00557           grandfather->Left->setDepthAdd(occdepth + fatherdepth);
00558       }
00559     } else {
00560       if (father->Left == this) {
00561         // Zig zag
00562         grandfather->setRight(Left);
00563         father->setLeft(Right);
00564         setLeft(grandfather);
00565         setRight(father);
00566         
00567         father->setDepth(-occdepth);
00568         if (father->Left)
00569           father->Left->setDepthAdd(occdepth);
00570         grandfather->setDepth(-occdepth - fatherdepth);
00571         if (grandfather->Right)
00572           grandfather->Right->setDepthAdd(occdepth + fatherdepth);
00573       } else {              // Zag Zag
00574         grandfather->setRight(father->Left);
00575         father->setRight(Left);
00576         setLeft(father);
00577         father->setLeft(grandfather);
00578         
00579         father->setDepth(-occdepth);
00580         if (father->Right)
00581           father->Right->setDepthAdd(occdepth);
00582         grandfather->setDepth(-fatherdepth);
00583         if (grandfather->Right)
00584           grandfather->Right->setDepthAdd(fatherdepth);
00585       }
00586     }
00587     
00588     // Might need one more rotate depending on greatgrandfather.
00589     setParent(greatgrandfather);
00590     if (greatgrandfather) {
00591       if (greatgrandfather->Left == grandfather)
00592         greatgrandfather->Left = this;
00593       else
00594         greatgrandfather->Right = this;
00595       
00596     }
00597     grandfather->recomputeMin();
00598     father->recomputeMin();
00599   }
00600 }
00601 
00602 //===----------------------------------------------------------------------===//
00603 // ETNode implementation
00604 //===----------------------------------------------------------------------===//
00605 
00606 void ETNode::Split() {
00607   ETOccurrence *right, *left;
00608   ETOccurrence *rightmost = RightmostOcc;
00609   ETOccurrence *parent;
00610 
00611   // Update the occurrence tree first.
00612   RightmostOcc->Splay();
00613 
00614   // Find the leftmost occurrence in the rightmost subtree, then splay
00615   // around it.
00616   for (right = rightmost->Right; right->Left; right = right->Left);
00617 
00618   right->Splay();
00619 
00620   // Start splitting
00621   right->Left->Parent = NULL;
00622   parent = ParentOcc;
00623   parent->Splay();
00624   ParentOcc = NULL;
00625 
00626   left = parent->Left;
00627   parent->Right->Parent = NULL;
00628 
00629   right->setLeft(left);
00630 
00631   right->recomputeMin();
00632 
00633   rightmost->Splay();
00634   rightmost->Depth = 0;
00635   rightmost->Min = 0;
00636 
00637   delete parent;
00638 
00639   // Now update *our* tree
00640 
00641   if (Father->Son == this)
00642     Father->Son = Right;
00643 
00644   if (Father->Son == this)
00645     Father->Son = NULL;
00646   else {
00647     Left->Right = Right;
00648     Right->Left = Left;
00649   }
00650   Left = Right = NULL;
00651   Father = NULL;
00652 }
00653 
00654 void ETNode::setFather(ETNode *NewFather) {
00655   ETOccurrence *rightmost;
00656   ETOccurrence *leftpart;
00657   ETOccurrence *NewFatherOcc;
00658   ETOccurrence *temp;
00659 
00660   // First update the path in the splay tree
00661   NewFatherOcc = new ETOccurrence(NewFather);
00662 
00663   rightmost = NewFather->RightmostOcc;
00664   rightmost->Splay();
00665 
00666   leftpart = rightmost->Left;
00667 
00668   temp = RightmostOcc;
00669   temp->Splay();
00670 
00671   NewFatherOcc->setLeft(leftpart);
00672   NewFatherOcc->setRight(temp);
00673 
00674   temp->Depth++;
00675   temp->Min++;
00676   NewFatherOcc->recomputeMin();
00677 
00678   rightmost->setLeft(NewFatherOcc);
00679 
00680   if (NewFatherOcc->Min + rightmost->Depth < rightmost->Min) {
00681     rightmost->Min = NewFatherOcc->Min + rightmost->Depth;
00682     rightmost->MinOccurrence = NewFatherOcc->MinOccurrence;
00683   }
00684 
00685   delete ParentOcc;
00686   ParentOcc = NewFatherOcc;
00687 
00688   // Update *our* tree
00689   ETNode *left;
00690   ETNode *right;
00691 
00692   Father = NewFather;
00693   right = Father->Son;
00694 
00695   if (right)
00696     left = right->Left;
00697   else
00698     left = right = this;
00699 
00700   left->Right = this;
00701   right->Left = this;
00702   Left = left;
00703   Right = right;
00704 
00705   Father->Son = this;
00706 }
00707 
00708 bool ETNode::Below(ETNode *other) {
00709   ETOccurrence *up = other->RightmostOcc;
00710   ETOccurrence *down = RightmostOcc;
00711 
00712   if (this == other)
00713     return true;
00714 
00715   up->Splay();
00716 
00717   ETOccurrence *left, *right;
00718   left = up->Left;
00719   right = up->Right;
00720 
00721   if (!left)
00722     return false;
00723 
00724   left->Parent = NULL;
00725 
00726   if (right)
00727     right->Parent = NULL;
00728 
00729   down->Splay();
00730 
00731   if (left == down || left->Parent != NULL) {
00732     if (right)
00733       right->Parent = up;
00734     up->setLeft(down);
00735   } else {
00736     left->Parent = up;
00737 
00738     // If the two occurrences are in different trees, put things
00739     // back the way they were.
00740     if (right && right->Parent != NULL)
00741       up->setRight(down);
00742     else
00743       up->setRight(right);
00744     return false;
00745   }
00746 
00747   if (down->Depth <= 0)
00748     return false;
00749 
00750   return !down->Right || down->Right->Min + down->Depth >= 0;
00751 }
00752 
00753 ETNode *ETNode::NCA(ETNode *other) {
00754   ETOccurrence *occ1 = RightmostOcc;
00755   ETOccurrence *occ2 = other->RightmostOcc;
00756   
00757   ETOccurrence *left, *right, *ret;
00758   ETOccurrence *occmin;
00759   int mindepth;
00760   
00761   if (this == other)
00762     return this;
00763   
00764   occ1->Splay();
00765   left = occ1->Left;
00766   right = occ1->Right;
00767   
00768   if (left)
00769     left->Parent = NULL;
00770   
00771   if (right)
00772     right->Parent = NULL;
00773   occ2->Splay();
00774 
00775   if (left == occ2 || (left && left->Parent != NULL)) {
00776     ret = occ2->Right;
00777     
00778     occ1->setLeft(occ2);
00779     if (right)
00780       right->Parent = occ1;
00781   } else {
00782     ret = occ2->Left;
00783     
00784     occ1->setRight(occ2);
00785     if (left)
00786       left->Parent = occ1;
00787   }
00788 
00789   if (occ2->Depth > 0) {
00790     occmin = occ1;
00791     mindepth = occ1->Depth;
00792   } else {
00793     occmin = occ2;
00794     mindepth = occ2->Depth + occ1->Depth;
00795   }
00796   
00797   if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth)
00798     return ret->MinOccurrence->OccFor;
00799   else
00800     return occmin->OccFor;
00801 }
00802 
00803 //===----------------------------------------------------------------------===//
00804 // ETForest implementation
00805 //===----------------------------------------------------------------------===//
00806 
00807 static RegisterAnalysis<ETForest>
00808 D("etforest", "ET Forest Construction", true);
00809 
00810 void ETForestBase::reset() {
00811   for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
00812     delete I->second;
00813   Nodes.clear();
00814 }
00815 
00816 void ETForestBase::updateDFSNumbers()
00817 {
00818   int dfsnum = 0;
00819   // Iterate over all nodes in depth first order.
00820   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
00821     for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
00822            E = df_end(Roots[i]); I != E; ++I) {
00823       BasicBlock *BB = *I;
00824       if (!getNode(BB)->hasFather())
00825         getNode(BB)->assignDFSNumber(dfsnum);    
00826   }
00827   SlowQueries = 0;
00828   DFSInfoValid = true;
00829 }
00830 
00831 ETNode *ETForest::getNodeForBlock(BasicBlock *BB) {
00832   ETNode *&BBNode = Nodes[BB];
00833   if (BBNode) return BBNode;
00834 
00835   // Haven't calculated this node yet?  Get or calculate the node for the
00836   // immediate dominator.
00837   BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
00838 
00839   // If we are unreachable, we may not have an immediate dominator.
00840   if (!IDom)
00841     return BBNode = new ETNode(BB);
00842   else {
00843     ETNode *IDomNode = getNodeForBlock(IDom);
00844     
00845     // Add a new tree node for this BasicBlock, and link it as a child of
00846     // IDomNode
00847     BBNode = new ETNode(BB);
00848     BBNode->setFather(IDomNode);
00849     return BBNode;
00850   }
00851 }
00852 
00853 void ETForest::calculate(const ImmediateDominators &ID) {
00854   assert(Roots.size() == 1 && "ETForest should have 1 root block!");
00855   BasicBlock *Root = Roots[0];
00856   Nodes[Root] = new ETNode(Root); // Add a node for the root
00857 
00858   Function *F = Root->getParent();
00859   // Loop over all of the reachable blocks in the function...
00860   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
00861     if (BasicBlock *ImmDom = ID.get(I)) {  // Reachable block.
00862       ETNode *&BBNode = Nodes[I];
00863       if (!BBNode) {  // Haven't calculated this node yet?
00864         // Get or calculate the node for the immediate dominator
00865         ETNode *IDomNode =  getNodeForBlock(ImmDom);
00866 
00867         // Add a new ETNode for this BasicBlock, and set it's parent
00868         // to it's immediate dominator.
00869         BBNode = new ETNode(I);
00870         BBNode->setFather(IDomNode);
00871       }
00872     }
00873 
00874   // Make sure we've got nodes around for every block
00875   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
00876     ETNode *&BBNode = Nodes[I];
00877     if (!BBNode)
00878       BBNode = new ETNode(I);
00879   }
00880 
00881   updateDFSNumbers ();
00882 }
00883 
00884 //===----------------------------------------------------------------------===//
00885 // ETForestBase Implementation
00886 //===----------------------------------------------------------------------===//
00887 
00888 void ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
00889   ETNode *&BBNode = Nodes[BB];
00890   assert(!BBNode && "BasicBlock already in ET-Forest");
00891 
00892   BBNode = new ETNode(BB);
00893   BBNode->setFather(getNode(IDom));
00894   DFSInfoValid = false;
00895 }
00896 
00897 void ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) {
00898   assert(getNode(BB) && "BasicBlock not in ET-Forest");
00899   assert(getNode(newIDom) && "IDom not in ET-Forest");
00900   
00901   ETNode *Node = getNode(BB);
00902   if (Node->hasFather()) {
00903     if (Node->getFather()->getData<BasicBlock>() == newIDom)
00904       return;
00905     Node->Split();
00906   }
00907   Node->setFather(getNode(newIDom));
00908   DFSInfoValid= false;
00909 }
00910 
00911 void ETForestBase::print(std::ostream &o, const Module *) const {
00912   o << "=============================--------------------------------\n";
00913   o << "ET Forest:\n";
00914   o << "DFS Info ";
00915   if (DFSInfoValid)
00916     o << "is";
00917   else
00918     o << "is not";
00919   o << " up to date\n";
00920 
00921   Function *F = getRoots()[0]->getParent();
00922   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
00923     o << "  DFS Numbers For Basic Block:";
00924     WriteAsOperand(o, I, false);
00925     o << " are:";
00926     if (ETNode *EN = getNode(I)) {
00927       o << "In: " << EN->getDFSNumIn();
00928       o << " Out: " << EN->getDFSNumOut() << "\n";
00929     } else {
00930       o << "No associated ETNode";
00931     }
00932     o << "\n";
00933   }
00934   o << "\n";
00935 }