LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 using namespace llvm;
00024 
00025 //===----------------------------------------------------------------------===//
00026 //  ImmediateDominators Implementation
00027 //===----------------------------------------------------------------------===//
00028 //
00029 // Immediate Dominators construction - This pass constructs immediate dominator
00030 // information for a flow-graph based on the algorithm described in this
00031 // document:
00032 //
00033 //   A Fast Algorithm for Finding Dominators in a Flowgraph
00034 //   T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
00035 //
00036 // This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and
00037 // LINK, but it turns out that the theoretically slower O(n*log(n))
00038 // implementation is actually faster than the "efficient" algorithm (even for
00039 // large CFGs) because the constant overheads are substantially smaller.  The
00040 // lower-complexity version can be enabled with the following #define:
00041 //
00042 #define BALANCE_IDOM_TREE 0
00043 //
00044 //===----------------------------------------------------------------------===//
00045 
00046 static RegisterAnalysis<ImmediateDominators>
00047 C("idom", "Immediate Dominators Construction", true);
00048 
00049 unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
00050                                       unsigned N) {
00051   VInfo.Semi = ++N;
00052   VInfo.Label = V;
00053 
00054   Vertex.push_back(V);        // Vertex[n] = V;
00055   //Info[V].Ancestor = 0;     // Ancestor[n] = 0
00056   //Child[V] = 0;             // Child[v] = 0
00057   VInfo.Size = 1;             // Size[v] = 1
00058 
00059   for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
00060     InfoRec &SuccVInfo = Info[*SI];
00061     if (SuccVInfo.Semi == 0) {
00062       SuccVInfo.Parent = V;
00063       N = DFSPass(*SI, SuccVInfo, N);
00064     }
00065   }
00066   return N;
00067 }
00068 
00069 void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) {
00070   BasicBlock *VAncestor = VInfo.Ancestor;
00071   InfoRec &VAInfo = Info[VAncestor];
00072   if (VAInfo.Ancestor == 0)
00073     return;
00074 
00075   Compress(VAncestor, VAInfo);
00076 
00077   BasicBlock *VAncestorLabel = VAInfo.Label; 
00078   BasicBlock *VLabel = VInfo.Label;
00079   if (Info[VAncestorLabel].Semi < Info[VLabel].Semi)
00080     VInfo.Label = VAncestorLabel;
00081 
00082   VInfo.Ancestor = VAInfo.Ancestor;
00083 }
00084 
00085 BasicBlock *ImmediateDominators::Eval(BasicBlock *V) {
00086   InfoRec &VInfo = Info[V];
00087 #if !BALANCE_IDOM_TREE
00088   // Higher-complexity but faster implementation
00089   if (VInfo.Ancestor == 0)
00090     return V;
00091   Compress(V, VInfo);
00092   return VInfo.Label;
00093 #else
00094   // Lower-complexity but slower implementation
00095   if (VInfo.Ancestor == 0)
00096     return VInfo.Label;
00097   Compress(V, VInfo);
00098   BasicBlock *VLabel = VInfo.Label;
00099 
00100   BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label;
00101   if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi)
00102     return VLabel;
00103   else
00104     return VAncestorLabel;
00105 #endif
00106 }
00107 
00108 void ImmediateDominators::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
00109 #if !BALANCE_IDOM_TREE
00110   // Higher-complexity but faster implementation
00111   WInfo.Ancestor = V;
00112 #else
00113   // Lower-complexity but slower implementation
00114   BasicBlock *WLabel = WInfo.Label;
00115   unsigned WLabelSemi = Info[WLabel].Semi;
00116   BasicBlock *S = W;
00117   InfoRec *SInfo = &Info[S];
00118   
00119   BasicBlock *SChild = SInfo->Child;
00120   InfoRec *SChildInfo = &Info[SChild];
00121   
00122   while (WLabelSemi < Info[SChildInfo->Label].Semi) {
00123     BasicBlock *SChildChild = SChildInfo->Child;
00124     if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) {
00125       SChildInfo->Ancestor = S;
00126       SInfo->Child = SChild = SChildChild;
00127       SChildInfo = &Info[SChild];
00128     } else {
00129       SChildInfo->Size = SInfo->Size;
00130       S = SInfo->Ancestor = SChild;
00131       SInfo = SChildInfo;
00132       SChild = SChildChild;
00133       SChildInfo = &Info[SChild];
00134     }
00135   }
00136   
00137   InfoRec &VInfo = Info[V];
00138   SInfo->Label = WLabel;
00139   
00140   assert(V != W && "The optimization here will not work in this case!");
00141   unsigned WSize = WInfo.Size;
00142   unsigned VSize = (VInfo.Size += WSize);
00143   
00144   if (VSize < 2*WSize)
00145     std::swap(S, VInfo.Child);
00146   
00147   while (S) {
00148     SInfo = &Info[S];
00149     SInfo->Ancestor = V;
00150     S = SInfo->Child;
00151   }
00152 #endif
00153 }
00154 
00155 
00156 
00157 bool ImmediateDominators::runOnFunction(Function &F) {
00158   IDoms.clear();     // Reset from the last time we were run...
00159   BasicBlock *Root = &F.getEntryBlock();
00160   Roots.clear();
00161   Roots.push_back(Root);
00162 
00163   Vertex.push_back(0);
00164   
00165   // Step #1: Number blocks in depth-first order and initialize variables used
00166   // in later stages of the algorithm.
00167   unsigned N = 0;
00168   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
00169     N = DFSPass(Roots[i], Info[Roots[i]], 0);
00170 
00171   for (unsigned i = N; i >= 2; --i) {
00172     BasicBlock *W = Vertex[i];
00173     InfoRec &WInfo = Info[W];
00174 
00175     // Step #2: Calculate the semidominators of all vertices
00176     for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI)
00177       if (Info.count(*PI)) {  // Only if this predecessor is reachable!
00178         unsigned SemiU = Info[Eval(*PI)].Semi;
00179         if (SemiU < WInfo.Semi)
00180           WInfo.Semi = SemiU;
00181       }
00182     
00183     Info[Vertex[WInfo.Semi]].Bucket.push_back(W);
00184 
00185     BasicBlock *WParent = WInfo.Parent;
00186     Link(WParent, W, WInfo);
00187 
00188     // Step #3: Implicitly define the immediate dominator of vertices
00189     std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket;
00190     while (!WParentBucket.empty()) {
00191       BasicBlock *V = WParentBucket.back();
00192       WParentBucket.pop_back();
00193       BasicBlock *U = Eval(V);
00194       IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent;
00195     }
00196   }
00197 
00198   // Step #4: Explicitly define the immediate dominator of each vertex
00199   for (unsigned i = 2; i <= N; ++i) {
00200     BasicBlock *W = Vertex[i];
00201     BasicBlock *&WIDom = IDoms[W];
00202     if (WIDom != Vertex[Info[W].Semi])
00203       WIDom = IDoms[WIDom];
00204   }
00205 
00206   // Free temporary memory used to construct idom's
00207   Info.clear();
00208   std::vector<BasicBlock*>().swap(Vertex);
00209 
00210   return false;
00211 }
00212 
00213 void ImmediateDominatorsBase::print(std::ostream &o) const {
00214   Function *F = getRoots()[0]->getParent();
00215   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
00216     o << "  Immediate Dominator For Basic Block:";
00217     WriteAsOperand(o, I, false);
00218     o << " is:";
00219     if (BasicBlock *ID = get(I))
00220       WriteAsOperand(o, ID, false);
00221     else
00222       o << " <<exit node>>";
00223     o << "\n";
00224   }
00225   o << "\n";
00226 }
00227 
00228 
00229 
00230 //===----------------------------------------------------------------------===//
00231 //  DominatorSet Implementation
00232 //===----------------------------------------------------------------------===//
00233 
00234 static RegisterAnalysis<DominatorSet>
00235 B("domset", "Dominator Set Construction", true);
00236 
00237 // dominates - Return true if A dominates B.  This performs the special checks
00238 // necessary if A and B are in the same basic block.
00239 //
00240 bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const {
00241   BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
00242   if (BBA != BBB) return dominates(BBA, BBB);
00243   
00244   // Loop through the basic block until we find A or B.
00245   BasicBlock::iterator I = BBA->begin();
00246   for (; &*I != A && &*I != B; ++I) /*empty*/;
00247   
00248   // A dominates B if it is found first in the basic block...
00249   return &*I == A;
00250 }
00251 
00252 
00253 // runOnFunction - This method calculates the forward dominator sets for the
00254 // specified function.
00255 //
00256 bool DominatorSet::runOnFunction(Function &F) {
00257   BasicBlock *Root = &F.getEntryBlock();
00258   Roots.clear();
00259   Roots.push_back(Root);
00260   assert(pred_begin(Root) == pred_end(Root) &&
00261    "Root node has predecessors in function!");
00262 
00263   ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
00264   Doms.clear();
00265   if (Roots.empty()) return false;
00266 
00267   // Root nodes only dominate themselves.
00268   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
00269     Doms[Roots[i]].insert(Roots[i]);
00270 
00271   // Loop over all of the blocks in the function, calculating dominator sets for
00272   // each function.
00273   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
00274     if (BasicBlock *IDom = ID[I]) {   // Get idom if block is reachable
00275       DomSetType &DS = Doms[I];
00276       assert(DS.empty() && "Domset already filled in for this block?");
00277       DS.insert(I);  // Blocks always dominate themselves
00278       
00279       // Insert all dominators into the set... 
00280       while (IDom) {
00281         // If we have already computed the dominator sets for our immediate
00282         // dominator, just use it instead of walking all the way up to the root.
00283         DomSetType &IDS = Doms[IDom];
00284         if (!IDS.empty()) {
00285           DS.insert(IDS.begin(), IDS.end());
00286           break;
00287         } else {
00288           DS.insert(IDom);
00289           IDom = ID[IDom];
00290         }
00291       }
00292     } else {
00293       // Ensure that every basic block has at least an empty set of nodes.  This
00294       // is important for the case when there is unreachable blocks.
00295       Doms[I];
00296     }
00297 
00298   return false;
00299 }
00300 
00301 void DominatorSet::stub() {}
00302 
00303 namespace llvm {
00304 static std::ostream &operator<<(std::ostream &o,
00305                                 const std::set<BasicBlock*> &BBs) {
00306   for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
00307        I != E; ++I)
00308     if (*I)
00309       WriteAsOperand(o, *I, false);
00310     else
00311       o << " <<exit node>>";
00312   return o;
00313 }
00314 }
00315 
00316 void DominatorSetBase::print(std::ostream &o) const {
00317   for (const_iterator I = begin(), E = end(); I != E; ++I) {
00318     o << "  DomSet For BB: ";
00319     if (I->first)
00320       WriteAsOperand(o, I->first, false);
00321     else
00322       o << " <<exit node>>";
00323     o << " is:\t" << I->second << "\n";
00324   }
00325 }
00326 
00327 //===----------------------------------------------------------------------===//
00328 //  DominatorTree Implementation
00329 //===----------------------------------------------------------------------===//
00330 
00331 static RegisterAnalysis<DominatorTree>
00332 E("domtree", "Dominator Tree Construction", true);
00333 
00334 // DominatorTreeBase::reset - Free all of the tree node memory.
00335 //
00336 void DominatorTreeBase::reset() { 
00337   for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
00338     delete I->second;
00339   Nodes.clear();
00340   RootNode = 0;
00341 }
00342 
00343 void DominatorTreeBase::Node::setIDom(Node *NewIDom) {
00344   assert(IDom && "No immediate dominator?");
00345   if (IDom != NewIDom) {
00346     std::vector<Node*>::iterator I =
00347       std::find(IDom->Children.begin(), IDom->Children.end(), this);
00348     assert(I != IDom->Children.end() &&
00349            "Not in immediate dominator children set!");
00350     // I am no longer your child...
00351     IDom->Children.erase(I);
00352 
00353     // Switch to new dominator
00354     IDom = NewIDom;
00355     IDom->Children.push_back(this);
00356   }
00357 }
00358 
00359 DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) {
00360   Node *&BBNode = Nodes[BB];
00361   if (BBNode) return BBNode;
00362 
00363   // Haven't calculated this node yet?  Get or calculate the node for the
00364   // immediate dominator.
00365   BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
00366   Node *IDomNode = getNodeForBlock(IDom);
00367     
00368   // Add a new tree node for this BasicBlock, and link it as a child of
00369   // IDomNode
00370   return BBNode = IDomNode->addChild(new Node(BB, IDomNode));
00371 }
00372 
00373 void DominatorTree::calculate(const ImmediateDominators &ID) {
00374   assert(Roots.size() == 1 && "DominatorTree should have 1 root block!");
00375   BasicBlock *Root = Roots[0];
00376   Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root...
00377 
00378   Function *F = Root->getParent();
00379   // Loop over all of the reachable blocks in the function...
00380   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
00381     if (BasicBlock *ImmDom = ID.get(I)) {  // Reachable block.
00382       Node *&BBNode = Nodes[I];
00383       if (!BBNode) {  // Haven't calculated this node yet?
00384         // Get or calculate the node for the immediate dominator
00385         Node *IDomNode = getNodeForBlock(ImmDom);
00386 
00387         // Add a new tree node for this BasicBlock, and link it as a child of
00388         // IDomNode
00389         BBNode = IDomNode->addChild(new Node(I, IDomNode));
00390       }
00391     }
00392 }
00393 
00394 static std::ostream &operator<<(std::ostream &o,
00395                                 const DominatorTreeBase::Node *Node) {
00396   if (Node->getBlock())
00397     WriteAsOperand(o, Node->getBlock(), false);
00398   else
00399     o << " <<exit node>>";
00400   return o << "\n";
00401 }
00402 
00403 static void PrintDomTree(const DominatorTreeBase::Node *N, std::ostream &o,
00404                          unsigned Lev) {
00405   o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
00406   for (DominatorTreeBase::Node::const_iterator I = N->begin(), E = N->end(); 
00407        I != E; ++I)
00408     PrintDomTree(*I, o, Lev+1);
00409 }
00410 
00411 void DominatorTreeBase::print(std::ostream &o) const {
00412   o << "=============================--------------------------------\n"
00413     << "Inorder Dominator Tree:\n";
00414   PrintDomTree(getRootNode(), o, 1);
00415 }
00416 
00417 
00418 //===----------------------------------------------------------------------===//
00419 //  DominanceFrontier Implementation
00420 //===----------------------------------------------------------------------===//
00421 
00422 static RegisterAnalysis<DominanceFrontier>
00423 G("domfrontier", "Dominance Frontier Construction", true);
00424 
00425 const DominanceFrontier::DomSetType &
00426 DominanceFrontier::calculate(const DominatorTree &DT, 
00427                              const DominatorTree::Node *Node) {
00428   // Loop over CFG successors to calculate DFlocal[Node]
00429   BasicBlock *BB = Node->getBlock();
00430   DomSetType &S = Frontiers[BB];       // The new set to fill in...
00431 
00432   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
00433        SI != SE; ++SI) {
00434     // Does Node immediately dominate this successor?
00435     if (DT[*SI]->getIDom() != Node)
00436       S.insert(*SI);
00437   }
00438 
00439   // At this point, S is DFlocal.  Now we union in DFup's of our children...
00440   // Loop through and visit the nodes that Node immediately dominates (Node's
00441   // children in the IDomTree)
00442   //
00443   for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
00444        NI != NE; ++NI) {
00445     DominatorTree::Node *IDominee = *NI;
00446     const DomSetType &ChildDF = calculate(DT, IDominee);
00447 
00448     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
00449     for (; CDFI != CDFE; ++CDFI) {
00450       if (!Node->dominates(DT[*CDFI]))
00451   S.insert(*CDFI);
00452     }
00453   }
00454 
00455   return S;
00456 }
00457 
00458 void DominanceFrontierBase::print(std::ostream &o) const {
00459   for (const_iterator I = begin(), E = end(); I != E; ++I) {
00460     o << "  DomFrontier for BB";
00461     if (I->first)
00462       WriteAsOperand(o, I->first, false);
00463     else
00464       o << " <<exit node>>";
00465     o << " is:\t" << I->second << "\n";
00466   }
00467 }
00468