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 namespace llvm {
00308 static std::ostream &operator<<(std::ostream &o,
00309                                 const std::set<BasicBlock*> &BBs) {
00310   for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
00311        I != E; ++I)
00312     if (*I)
00313       WriteAsOperand(o, *I, false);
00314     else
00315       o << " <<exit node>>";
00316   return o;
00317 }
00318 }
00319 
00320 void DominatorSetBase::print(std::ostream &o, const Module* ) const {
00321   for (const_iterator I = begin(), E = end(); I != E; ++I) {
00322     o << "  DomSet For BB: ";
00323     if (I->first)
00324       WriteAsOperand(o, I->first, false);
00325     else
00326       o << " <<exit node>>";
00327     o << " is:\t" << I->second << "\n";
00328   }
00329 }
00330 
00331 //===----------------------------------------------------------------------===//
00332 //  DominatorTree Implementation
00333 //===----------------------------------------------------------------------===//
00334 
00335 static RegisterAnalysis<DominatorTree>
00336 E("domtree", "Dominator Tree Construction", true);
00337 
00338 // DominatorTreeBase::reset - Free all of the tree node memory.
00339 //
00340 void DominatorTreeBase::reset() {
00341   for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
00342     delete I->second;
00343   Nodes.clear();
00344   RootNode = 0;
00345 }
00346 
00347 void DominatorTreeBase::Node::setIDom(Node *NewIDom) {
00348   assert(IDom && "No immediate dominator?");
00349   if (IDom != NewIDom) {
00350     std::vector<Node*>::iterator I =
00351       std::find(IDom->Children.begin(), IDom->Children.end(), this);
00352     assert(I != IDom->Children.end() &&
00353            "Not in immediate dominator children set!");
00354     // I am no longer your child...
00355     IDom->Children.erase(I);
00356 
00357     // Switch to new dominator
00358     IDom = NewIDom;
00359     IDom->Children.push_back(this);
00360   }
00361 }
00362 
00363 DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) {
00364   Node *&BBNode = Nodes[BB];
00365   if (BBNode) return BBNode;
00366 
00367   // Haven't calculated this node yet?  Get or calculate the node for the
00368   // immediate dominator.
00369   BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
00370   Node *IDomNode = getNodeForBlock(IDom);
00371 
00372   // Add a new tree node for this BasicBlock, and link it as a child of
00373   // IDomNode
00374   return BBNode = IDomNode->addChild(new Node(BB, IDomNode));
00375 }
00376 
00377 void DominatorTree::calculate(const ImmediateDominators &ID) {
00378   assert(Roots.size() == 1 && "DominatorTree should have 1 root block!");
00379   BasicBlock *Root = Roots[0];
00380   Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root...
00381 
00382   Function *F = Root->getParent();
00383   // Loop over all of the reachable blocks in the function...
00384   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
00385     if (BasicBlock *ImmDom = ID.get(I)) {  // Reachable block.
00386       Node *&BBNode = Nodes[I];
00387       if (!BBNode) {  // Haven't calculated this node yet?
00388         // Get or calculate the node for the immediate dominator
00389         Node *IDomNode = getNodeForBlock(ImmDom);
00390 
00391         // Add a new tree node for this BasicBlock, and link it as a child of
00392         // IDomNode
00393         BBNode = IDomNode->addChild(new Node(I, IDomNode));
00394       }
00395     }
00396 }
00397 
00398 static std::ostream &operator<<(std::ostream &o,
00399                                 const DominatorTreeBase::Node *Node) {
00400   if (Node->getBlock())
00401     WriteAsOperand(o, Node->getBlock(), false);
00402   else
00403     o << " <<exit node>>";
00404   return o << "\n";
00405 }
00406 
00407 static void PrintDomTree(const DominatorTreeBase::Node *N, std::ostream &o,
00408                          unsigned Lev) {
00409   o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
00410   for (DominatorTreeBase::Node::const_iterator I = N->begin(), E = N->end();
00411        I != E; ++I)
00412     PrintDomTree(*I, o, Lev+1);
00413 }
00414 
00415 void DominatorTreeBase::print(std::ostream &o, const Module* ) const {
00416   o << "=============================--------------------------------\n"
00417     << "Inorder Dominator Tree:\n";
00418   PrintDomTree(getRootNode(), o, 1);
00419 }
00420 
00421 
00422 //===----------------------------------------------------------------------===//
00423 //  DominanceFrontier Implementation
00424 //===----------------------------------------------------------------------===//
00425 
00426 static RegisterAnalysis<DominanceFrontier>
00427 G("domfrontier", "Dominance Frontier Construction", true);
00428 
00429 const DominanceFrontier::DomSetType &
00430 DominanceFrontier::calculate(const DominatorTree &DT,
00431                              const DominatorTree::Node *Node) {
00432   // Loop over CFG successors to calculate DFlocal[Node]
00433   BasicBlock *BB = Node->getBlock();
00434   DomSetType &S = Frontiers[BB];       // The new set to fill in...
00435 
00436   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
00437        SI != SE; ++SI) {
00438     // Does Node immediately dominate this successor?
00439     if (DT[*SI]->getIDom() != Node)
00440       S.insert(*SI);
00441   }
00442 
00443   // At this point, S is DFlocal.  Now we union in DFup's of our children...
00444   // Loop through and visit the nodes that Node immediately dominates (Node's
00445   // children in the IDomTree)
00446   //
00447   for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
00448        NI != NE; ++NI) {
00449     DominatorTree::Node *IDominee = *NI;
00450     const DomSetType &ChildDF = calculate(DT, IDominee);
00451 
00452     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
00453     for (; CDFI != CDFE; ++CDFI) {
00454       if (!Node->properlyDominates(DT[*CDFI]))
00455         S.insert(*CDFI);
00456     }
00457   }
00458 
00459   return S;
00460 }
00461 
00462 void DominanceFrontierBase::print(std::ostream &o, const Module* ) const {
00463   for (const_iterator I = begin(), E = end(); I != E; ++I) {
00464     o << "  DomFrontier for BB";
00465     if (I->first)
00466       WriteAsOperand(o, I->first, false);
00467     else
00468       o << " <<exit node>>";
00469     o << " is:\t" << I->second << "\n";
00470   }
00471 }
00472 
00473 //===----------------------------------------------------------------------===//
00474 // ETOccurrence Implementation
00475 //===----------------------------------------------------------------------===//
00476 
00477 void ETOccurrence::Splay() {
00478   ETOccurrence *father;
00479   ETOccurrence *grandfather;
00480   int occdepth;
00481   int fatherdepth;
00482   
00483   while (Parent) {
00484     occdepth = Depth;
00485     
00486     father = Parent;
00487     fatherdepth = Parent->Depth;
00488     grandfather = father->Parent;
00489     
00490     // If we have no grandparent, a single zig or zag will do.
00491     if (!grandfather) {
00492       setDepthAdd(fatherdepth);
00493       MinOccurrence = father->MinOccurrence;
00494       Min = father->Min;
00495       
00496       // See what we have to rotate
00497       if (father->Left == this) {
00498         // Zig
00499         father->setLeft(Right);
00500         setRight(father);
00501         if (father->Left)
00502           father->Left->setDepthAdd(occdepth);
00503       } else {
00504         // Zag
00505         father->setRight(Left);
00506         setLeft(father);
00507         if (father->Right)
00508           father->Right->setDepthAdd(occdepth);
00509       }
00510       father->setDepth(-occdepth);
00511       Parent = NULL;
00512       
00513       father->recomputeMin();
00514       return;
00515     }
00516     
00517     // If we have a grandfather, we need to do some
00518     // combination of zig and zag.
00519     int grandfatherdepth = grandfather->Depth;
00520     
00521     setDepthAdd(fatherdepth + grandfatherdepth);
00522     MinOccurrence = grandfather->MinOccurrence;
00523     Min = grandfather->Min;
00524     
00525     ETOccurrence *greatgrandfather = grandfather->Parent;
00526     
00527     if (grandfather->Left == father) {
00528       if (father->Left == this) {
00529         // Zig zig
00530         grandfather->setLeft(father->Right);
00531         father->setLeft(Right);
00532         setRight(father);
00533         father->setRight(grandfather);
00534         
00535         father->setDepth(-occdepth);
00536         
00537         if (father->Left)
00538           father->Left->setDepthAdd(occdepth);
00539         
00540         grandfather->setDepth(-fatherdepth);
00541         if (grandfather->Left)
00542           grandfather->Left->setDepthAdd(fatherdepth);
00543       } else {
00544         // Zag zig
00545         grandfather->setLeft(Right);
00546         father->setRight(Left);
00547         setLeft(father);
00548         setRight(grandfather);
00549         
00550         father->setDepth(-occdepth);
00551         if (father->Right)
00552           father->Right->setDepthAdd(occdepth);
00553         grandfather->setDepth(-occdepth - fatherdepth);
00554         if (grandfather->Left)
00555           grandfather->Left->setDepthAdd(occdepth + fatherdepth);
00556       }
00557     } else {
00558       if (father->Left == this) {
00559         // Zig zag
00560         grandfather->setRight(Left);
00561         father->setLeft(Right);
00562         setLeft(grandfather);
00563         setRight(father);
00564         
00565         father->setDepth(-occdepth);
00566         if (father->Left)
00567           father->Left->setDepthAdd(occdepth);
00568         grandfather->setDepth(-occdepth - fatherdepth);
00569         if (grandfather->Right)
00570           grandfather->Right->setDepthAdd(occdepth + fatherdepth);
00571       } else {              // Zag Zag
00572         grandfather->setRight(father->Left);
00573         father->setRight(Left);
00574         setLeft(father);
00575         father->setLeft(grandfather);
00576         
00577         father->setDepth(-occdepth);
00578         if (father->Right)
00579           father->Right->setDepthAdd(occdepth);
00580         grandfather->setDepth(-fatherdepth);
00581         if (grandfather->Right)
00582           grandfather->Right->setDepthAdd(fatherdepth);
00583       }
00584     }
00585     
00586     // Might need one more rotate depending on greatgrandfather.
00587     setParent(greatgrandfather);
00588     if (greatgrandfather) {
00589       if (greatgrandfather->Left == grandfather)
00590         greatgrandfather->Left = this;
00591       else
00592         greatgrandfather->Right = this;
00593       
00594     }
00595     grandfather->recomputeMin();
00596     father->recomputeMin();
00597   }
00598 }
00599 
00600 //===----------------------------------------------------------------------===//
00601 // ETNode implementation
00602 //===----------------------------------------------------------------------===//
00603 
00604 void ETNode::Split() {
00605   ETOccurrence *right, *left;
00606   ETOccurrence *rightmost = RightmostOcc;
00607   ETOccurrence *parent;
00608 
00609   // Update the occurrence tree first.
00610   RightmostOcc->Splay();
00611 
00612   // Find the leftmost occurrence in the rightmost subtree, then splay
00613   // around it.
00614   for (right = rightmost->Right; right->Left; right = right->Left);
00615 
00616   right->Splay();
00617 
00618   // Start splitting
00619   right->Left->Parent = NULL;
00620   parent = ParentOcc;
00621   parent->Splay();
00622   ParentOcc = NULL;
00623 
00624   left = parent->Left;
00625   parent->Right->Parent = NULL;
00626 
00627   right->setLeft(left);
00628 
00629   right->recomputeMin();
00630 
00631   rightmost->Splay();
00632   rightmost->Depth = 0;
00633   rightmost->Min = 0;
00634 
00635   delete parent;
00636 
00637   // Now update *our* tree
00638 
00639   if (Father->Son == this)
00640     Father->Son = Right;
00641 
00642   if (Father->Son == this)
00643     Father->Son = NULL;
00644   else {
00645     Left->Right = Right;
00646     Right->Left = Left;
00647   }
00648   Left = Right = NULL;
00649   Father = NULL;
00650 }
00651 
00652 void ETNode::setFather(ETNode *NewFather) {
00653   ETOccurrence *rightmost;
00654   ETOccurrence *leftpart;
00655   ETOccurrence *NewFatherOcc;
00656   ETOccurrence *temp;
00657 
00658   // First update the path in the splay tree
00659   NewFatherOcc = new ETOccurrence(NewFather);
00660 
00661   rightmost = NewFather->RightmostOcc;
00662   rightmost->Splay();
00663 
00664   leftpart = rightmost->Left;
00665 
00666   temp = RightmostOcc;
00667   temp->Splay();
00668 
00669   NewFatherOcc->setLeft(leftpart);
00670   NewFatherOcc->setRight(temp);
00671 
00672   temp->Depth++;
00673   temp->Min++;
00674   NewFatherOcc->recomputeMin();
00675 
00676   rightmost->setLeft(NewFatherOcc);
00677 
00678   if (NewFatherOcc->Min + rightmost->Depth < rightmost->Min) {
00679     rightmost->Min = NewFatherOcc->Min + rightmost->Depth;
00680     rightmost->MinOccurrence = NewFatherOcc->MinOccurrence;
00681   }
00682 
00683   delete ParentOcc;
00684   ParentOcc = NewFatherOcc;
00685 
00686   // Update *our* tree
00687   ETNode *left;
00688   ETNode *right;
00689 
00690   Father = NewFather;
00691   right = Father->Son;
00692 
00693   if (right)
00694     left = right->Left;
00695   else
00696     left = right = this;
00697 
00698   left->Right = this;
00699   right->Left = this;
00700   Left = left;
00701   Right = right;
00702 
00703   Father->Son = this;
00704 }
00705 
00706 bool ETNode::Below(ETNode *other) {
00707   ETOccurrence *up = other->RightmostOcc;
00708   ETOccurrence *down = RightmostOcc;
00709 
00710   if (this == other)
00711     return true;
00712 
00713   up->Splay();
00714 
00715   ETOccurrence *left, *right;
00716   left = up->Left;
00717   right = up->Right;
00718 
00719   if (!left)
00720     return false;
00721 
00722   left->Parent = NULL;
00723 
00724   if (right)
00725     right->Parent = NULL;
00726 
00727   down->Splay();
00728 
00729   if (left == down || left->Parent != NULL) {
00730     if (right)
00731       right->Parent = up;
00732     up->setLeft(down);
00733   } else {
00734     left->Parent = up;
00735 
00736     // If the two occurrences are in different trees, put things
00737     // back the way they were.
00738     if (right && right->Parent != NULL)
00739       up->setRight(down);
00740     else
00741       up->setRight(right);
00742     return false;
00743   }
00744 
00745   if (down->Depth <= 0)
00746     return false;
00747 
00748   return !down->Right || down->Right->Min + down->Depth >= 0;
00749 }
00750 
00751 ETNode *ETNode::NCA(ETNode *other) {
00752   ETOccurrence *occ1 = RightmostOcc;
00753   ETOccurrence *occ2 = other->RightmostOcc;
00754   
00755   ETOccurrence *left, *right, *ret;
00756   ETOccurrence *occmin;
00757   int mindepth;
00758   
00759   if (this == other)
00760     return this;
00761   
00762   occ1->Splay();
00763   left = occ1->Left;
00764   right = occ1->Right;
00765   
00766   if (left)
00767     left->Parent = NULL;
00768   
00769   if (right)
00770     right->Parent = NULL;
00771   occ2->Splay();
00772 
00773   if (left == occ2 || (left && left->Parent != NULL)) {
00774     ret = occ2->Right;
00775     
00776     occ1->setLeft(occ2);
00777     if (right)
00778       right->Parent = occ1;
00779   } else {
00780     ret = occ2->Left;
00781     
00782     occ1->setRight(occ2);
00783     if (left)
00784       left->Parent = occ1;
00785   }
00786 
00787   if (occ2->Depth > 0) {
00788     occmin = occ1;
00789     mindepth = occ1->Depth;
00790   } else {
00791     occmin = occ2;
00792     mindepth = occ2->Depth + occ1->Depth;
00793   }
00794   
00795   if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth)
00796     return ret->MinOccurrence->OccFor;
00797   else
00798     return occmin->OccFor;
00799 }
00800 
00801 //===----------------------------------------------------------------------===//
00802 // ETForest implementation
00803 //===----------------------------------------------------------------------===//
00804 
00805 static RegisterAnalysis<ETForest>
00806 D("etforest", "ET Forest Construction", true);
00807 
00808 void ETForestBase::reset() {
00809   for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
00810     delete I->second;
00811   Nodes.clear();
00812 }
00813 
00814 void ETForestBase::updateDFSNumbers()
00815 {
00816   int dfsnum = 0;
00817   // Iterate over all nodes in depth first order.
00818   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
00819     for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
00820            E = df_end(Roots[i]); I != E; ++I) {
00821       BasicBlock *BB = *I;
00822       if (!getNode(BB)->hasFather())
00823         getNode(BB)->assignDFSNumber(dfsnum);    
00824   }
00825   SlowQueries = 0;
00826   DFSInfoValid = true;
00827 }
00828 
00829 ETNode *ETForest::getNodeForBlock(BasicBlock *BB) {
00830   ETNode *&BBNode = Nodes[BB];
00831   if (BBNode) return BBNode;
00832 
00833   // Haven't calculated this node yet?  Get or calculate the node for the
00834   // immediate dominator.
00835   BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
00836 
00837   // If we are unreachable, we may not have an immediate dominator.
00838   if (!IDom)
00839     return BBNode = new ETNode(BB);
00840   else {
00841     ETNode *IDomNode = getNodeForBlock(IDom);
00842     
00843     // Add a new tree node for this BasicBlock, and link it as a child of
00844     // IDomNode
00845     BBNode = new ETNode(BB);
00846     BBNode->setFather(IDomNode);
00847     return BBNode;
00848   }
00849 }
00850 
00851 void ETForest::calculate(const ImmediateDominators &ID) {
00852   assert(Roots.size() == 1 && "ETForest should have 1 root block!");
00853   BasicBlock *Root = Roots[0];
00854   Nodes[Root] = new ETNode(Root); // Add a node for the root
00855 
00856   Function *F = Root->getParent();
00857   // Loop over all of the reachable blocks in the function...
00858   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
00859     if (BasicBlock *ImmDom = ID.get(I)) {  // Reachable block.
00860       ETNode *&BBNode = Nodes[I];
00861       if (!BBNode) {  // Haven't calculated this node yet?
00862         // Get or calculate the node for the immediate dominator
00863         ETNode *IDomNode =  getNodeForBlock(ImmDom);
00864 
00865         // Add a new ETNode for this BasicBlock, and set it's parent
00866         // to it's immediate dominator.
00867         BBNode = new ETNode(I);
00868         BBNode->setFather(IDomNode);
00869       }
00870     }
00871 
00872   // Make sure we've got nodes around for every block
00873   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
00874     ETNode *&BBNode = Nodes[I];
00875     if (!BBNode)
00876       BBNode = new ETNode(I);
00877   }
00878 
00879   updateDFSNumbers ();
00880 }
00881 
00882 //===----------------------------------------------------------------------===//
00883 // ETForestBase Implementation
00884 //===----------------------------------------------------------------------===//
00885 
00886 void ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
00887   ETNode *&BBNode = Nodes[BB];
00888   assert(!BBNode && "BasicBlock already in ET-Forest");
00889 
00890   BBNode = new ETNode(BB);
00891   BBNode->setFather(getNode(IDom));
00892   DFSInfoValid = false;
00893 }
00894 
00895 void ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) {
00896   assert(getNode(BB) && "BasicBlock not in ET-Forest");
00897   assert(getNode(newIDom) && "IDom not in ET-Forest");
00898   
00899   ETNode *Node = getNode(BB);
00900   if (Node->hasFather()) {
00901     if (Node->getFather()->getData<BasicBlock>() == newIDom)
00902       return;
00903     Node->Split();
00904   }
00905   Node->setFather(getNode(newIDom));
00906   DFSInfoValid= false;
00907 }
00908 
00909 void ETForestBase::print(std::ostream &o, const Module *) const {
00910   o << "=============================--------------------------------\n";
00911   o << "ET Forest:\n";
00912   o << "DFS Info ";
00913   if (DFSInfoValid)
00914     o << "is";
00915   else
00916     o << "is not";
00917   o << " up to date\n";
00918 
00919   Function *F = getRoots()[0]->getParent();
00920   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
00921     o << "  DFS Numbers For Basic Block:";
00922     WriteAsOperand(o, I, false);
00923     o << " are:";
00924     if (ETNode *EN = getNode(I)) {
00925       o << "In: " << EN->getDFSNumIn();
00926       o << " Out: " << EN->getDFSNumOut() << "\n";
00927     } else {
00928       o << "No associated ETNode";
00929     }
00930     o << "\n";
00931   }
00932   o << "\n";
00933 }
00934 
00935 DEFINING_FILE_FOR(DominatorSet)