LLVM API Documentation

PostDominators.cpp

Go to the documentation of this file.
00001 //===- PostDominators.cpp - Post-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 the post-dominator construction algorithms.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/Analysis/PostDominators.h"
00015 #include "llvm/Instructions.h"
00016 #include "llvm/Support/CFG.h"
00017 #include "llvm/ADT/DepthFirstIterator.h"
00018 #include "llvm/ADT/SetOperations.h"
00019 #include <iostream>
00020 using namespace llvm;
00021 
00022 //===----------------------------------------------------------------------===//
00023 //  ImmediatePostDominators Implementation
00024 //===----------------------------------------------------------------------===//
00025 
00026 static RegisterAnalysis<ImmediatePostDominators>
00027 D("postidom", "Immediate Post-Dominators Construction", true);
00028 
00029 unsigned ImmediatePostDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
00030                                           unsigned N) {
00031   VInfo.Semi = ++N;
00032   VInfo.Label = V;
00033   
00034   Vertex.push_back(V);        // Vertex[n] = V;
00035                               //Info[V].Ancestor = 0;     // Ancestor[n] = 0
00036                               //Child[V] = 0;             // Child[v] = 0
00037   VInfo.Size = 1;             // Size[v] = 1
00038   
00039   // For PostDominators, we want to walk predecessors rather than successors
00040   // as we do in forward Dominators.
00041   for (pred_iterator PI = pred_begin(V), PE = pred_end(V); PI != PE; ++PI) {
00042     InfoRec &SuccVInfo = Info[*PI];
00043     if (SuccVInfo.Semi == 0) {
00044       SuccVInfo.Parent = V;
00045       N = DFSPass(*PI, SuccVInfo, N);
00046     }
00047   }
00048   return N;
00049 }
00050 
00051 void ImmediatePostDominators::Compress(BasicBlock *V, InfoRec &VInfo) {
00052   BasicBlock *VAncestor = VInfo.Ancestor;
00053   InfoRec &VAInfo = Info[VAncestor];
00054   if (VAInfo.Ancestor == 0)
00055     return;
00056   
00057   Compress(VAncestor, VAInfo);
00058   
00059   BasicBlock *VAncestorLabel = VAInfo.Label;
00060   BasicBlock *VLabel = VInfo.Label;
00061   if (Info[VAncestorLabel].Semi < Info[VLabel].Semi)
00062     VInfo.Label = VAncestorLabel;
00063   
00064   VInfo.Ancestor = VAInfo.Ancestor;
00065 }
00066 
00067 BasicBlock *ImmediatePostDominators::Eval(BasicBlock *V) {
00068   InfoRec &VInfo = Info[V];
00069 
00070   // Higher-complexity but faster implementation
00071   if (VInfo.Ancestor == 0)
00072     return V;
00073   Compress(V, VInfo);
00074   return VInfo.Label;
00075 }
00076 
00077 void ImmediatePostDominators::Link(BasicBlock *V, BasicBlock *W, 
00078                                    InfoRec &WInfo) {
00079   // Higher-complexity but faster implementation
00080   WInfo.Ancestor = V;
00081 }
00082 
00083 bool ImmediatePostDominators::runOnFunction(Function &F) {
00084   IDoms.clear();     // Reset from the last time we were run...
00085   Roots.clear();
00086 
00087   // Step #0: Scan the function looking for the root nodes of the post-dominance
00088   // relationships.  These blocks, which have no successors, end with return and
00089   // unwind instructions.
00090   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
00091     if (succ_begin(I) == succ_end(I))
00092       Roots.push_back(I);
00093   
00094   Vertex.push_back(0);
00095   
00096   // Step #1: Number blocks in depth-first order and initialize variables used
00097   // in later stages of the algorithm.
00098   unsigned N = 0;
00099   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
00100     N = DFSPass(Roots[i], Info[Roots[i]], N);
00101   
00102   for (unsigned i = N; i >= 2; --i) {
00103     BasicBlock *W = Vertex[i];
00104     InfoRec &WInfo = Info[W];
00105     
00106     // Step #2: Calculate the semidominators of all vertices
00107     for (succ_iterator SI = succ_begin(W), SE = succ_end(W); SI != SE; ++SI)
00108       if (Info.count(*SI)) {  // Only if this predecessor is reachable!
00109         unsigned SemiU = Info[Eval(*SI)].Semi;
00110         if (SemiU < WInfo.Semi)
00111           WInfo.Semi = SemiU;
00112       }
00113         
00114     Info[Vertex[WInfo.Semi]].Bucket.push_back(W);
00115     
00116     BasicBlock *WParent = WInfo.Parent;
00117     Link(WParent, W, WInfo);
00118     
00119     // Step #3: Implicitly define the immediate dominator of vertices
00120     std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket;
00121     while (!WParentBucket.empty()) {
00122       BasicBlock *V = WParentBucket.back();
00123       WParentBucket.pop_back();
00124       BasicBlock *U = Eval(V);
00125       IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent;
00126     }
00127   }
00128   
00129   // Step #4: Explicitly define the immediate dominator of each vertex
00130   for (unsigned i = 2; i <= N; ++i) {
00131     BasicBlock *W = Vertex[i];
00132     BasicBlock *&WIDom = IDoms[W];
00133     if (WIDom != Vertex[Info[W].Semi])
00134       WIDom = IDoms[WIDom];
00135   }
00136   
00137   // Free temporary memory used to construct idom's
00138   Info.clear();
00139   std::vector<BasicBlock*>().swap(Vertex);
00140   
00141   return false;
00142 }
00143 
00144 //===----------------------------------------------------------------------===//
00145 //  PostDominatorSet Implementation
00146 //===----------------------------------------------------------------------===//
00147 
00148 static RegisterAnalysis<PostDominatorSet>
00149 B("postdomset", "Post-Dominator Set Construction", true);
00150 
00151 // Postdominator set construction.  This converts the specified function to only
00152 // have a single exit node (return stmt), then calculates the post dominance
00153 // sets for the function.
00154 //
00155 bool PostDominatorSet::runOnFunction(Function &F) {
00156   // Scan the function looking for the root nodes of the post-dominance
00157   // relationships.  These blocks end with return and unwind instructions.
00158   // While we are iterating over the function, we also initialize all of the
00159   // domsets to empty.
00160   Roots.clear();
00161   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
00162     if (succ_begin(I) == succ_end(I))
00163       Roots.push_back(I);
00164 
00165   // If there are no exit nodes for the function, postdomsets are all empty.
00166   // This can happen if the function just contains an infinite loop, for
00167   // example.
00168   ImmediatePostDominators &IPD = getAnalysis<ImmediatePostDominators>();
00169   Doms.clear();   // Reset from the last time we were run...
00170   if (Roots.empty()) return false;
00171 
00172   // If we have more than one root, we insert an artificial "null" exit, which
00173   // has "virtual edges" to each of the real exit nodes.
00174   //if (Roots.size() > 1)
00175   //  Doms[0].insert(0);
00176 
00177   // Root nodes only dominate themselves.
00178   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
00179     Doms[Roots[i]].insert(Roots[i]);
00180   
00181   // Loop over all of the blocks in the function, calculating dominator sets for
00182   // each function.
00183   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
00184     if (BasicBlock *IPDom = IPD[I]) {   // Get idom if block is reachable
00185       DomSetType &DS = Doms[I];
00186       assert(DS.empty() && "PostDomset already filled in for this block?");
00187       DS.insert(I);  // Blocks always dominate themselves
00188 
00189       // Insert all dominators into the set...
00190       while (IPDom) {
00191         // If we have already computed the dominator sets for our immediate post
00192         // dominator, just use it instead of walking all the way up to the root.
00193         DomSetType &IPDS = Doms[IPDom];
00194         if (!IPDS.empty()) {
00195           DS.insert(IPDS.begin(), IPDS.end());
00196           break;
00197         } else {
00198           DS.insert(IPDom);
00199           IPDom = IPD[IPDom];
00200         }
00201       }
00202     } else {
00203       // Ensure that every basic block has at least an empty set of nodes.  This
00204       // is important for the case when there is unreachable blocks.
00205       Doms[I];
00206     }
00207 
00208   return false;
00209 }
00210 
00211 //===----------------------------------------------------------------------===//
00212 //  PostDominatorTree Implementation
00213 //===----------------------------------------------------------------------===//
00214 
00215 static RegisterAnalysis<PostDominatorTree>
00216 F("postdomtree", "Post-Dominator Tree Construction", true);
00217 
00218 DominatorTreeBase::Node *PostDominatorTree::getNodeForBlock(BasicBlock *BB) {
00219   Node *&BBNode = Nodes[BB];
00220   if (BBNode) return BBNode;
00221   
00222   // Haven't calculated this node yet?  Get or calculate the node for the
00223   // immediate postdominator.
00224   BasicBlock *IPDom = getAnalysis<ImmediatePostDominators>()[BB];
00225   Node *IPDomNode = getNodeForBlock(IPDom);
00226   
00227   // Add a new tree node for this BasicBlock, and link it as a child of
00228   // IDomNode
00229   return BBNode = IPDomNode->addChild(new Node(BB, IPDomNode));
00230 }
00231 
00232 void PostDominatorTree::calculate(const ImmediatePostDominators &IPD) {
00233   if (Roots.empty()) return;
00234 
00235   // Add a node for the root.  This node might be the actual root, if there is
00236   // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0)
00237   // which postdominates all real exits if there are multiple exit blocks.
00238   BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0;
00239   Nodes[Root] = RootNode = new Node(Root, 0);
00240   
00241   Function *F = Roots[0]->getParent();
00242   // Loop over all of the reachable blocks in the function...
00243   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
00244     if (BasicBlock *ImmPostDom = IPD.get(I)) {  // Reachable block.
00245       Node *&BBNode = Nodes[I];
00246       if (!BBNode) {  // Haven't calculated this node yet?
00247                       // Get or calculate the node for the immediate dominator
00248         Node *IPDomNode = getNodeForBlock(ImmPostDom);
00249         
00250         // Add a new tree node for this BasicBlock, and link it as a child of
00251         // IDomNode
00252         BBNode = IPDomNode->addChild(new Node(I, IPDomNode));
00253       }
00254     }
00255 }
00256 
00257 //===----------------------------------------------------------------------===//
00258 // PostETForest Implementation
00259 //===----------------------------------------------------------------------===//
00260 
00261 static RegisterAnalysis<PostETForest>
00262 G("postetforest", "Post-ET-Forest Construction", true);
00263 
00264 ETNode *PostETForest::getNodeForBlock(BasicBlock *BB) {
00265   ETNode *&BBNode = Nodes[BB];
00266   if (BBNode) return BBNode;
00267 
00268   // Haven't calculated this node yet?  Get or calculate the node for the
00269   // immediate dominator.
00270   BasicBlock *IDom = getAnalysis<ImmediatePostDominators>()[BB];
00271 
00272   // If we are unreachable, we may not have an immediate dominator.
00273   if (!IDom)
00274     return BBNode = new ETNode(BB);
00275   else {
00276     ETNode *IDomNode = getNodeForBlock(IDom);
00277     
00278     // Add a new tree node for this BasicBlock, and link it as a child of
00279     // IDomNode
00280     BBNode = new ETNode(BB);
00281     BBNode->setFather(IDomNode);
00282     return BBNode;
00283   }
00284 }
00285 
00286 void PostETForest::calculate(const ImmediatePostDominators &ID) {
00287   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
00288     Nodes[Roots[i]] = new ETNode(Roots[i]); // Add a node for the root
00289 
00290   // Iterate over all nodes in inverse depth first order.
00291   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
00292     for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]),
00293            E = idf_end(Roots[i]); I != E; ++I) {
00294     BasicBlock *BB = *I;
00295     ETNode *&BBNode = Nodes[BB];
00296     if (!BBNode) {  
00297       ETNode *IDomNode =  NULL;
00298 
00299       if (ID.get(BB))
00300         IDomNode = getNodeForBlock(ID.get(BB));
00301 
00302       // Add a new ETNode for this BasicBlock, and set it's parent
00303       // to it's immediate dominator.
00304       BBNode = new ETNode(BB);
00305       if (IDomNode)          
00306         BBNode->setFather(IDomNode);
00307     }
00308   }
00309 
00310   int dfsnum = 0;
00311   // Iterate over all nodes in depth first order...
00312   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
00313     for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]),
00314            E = idf_end(Roots[i]); I != E; ++I) {
00315         if (!getNodeForBlock(*I)->hasFather())
00316           getNodeForBlock(*I)->assignDFSNumber(dfsnum);
00317     }
00318   DFSInfoValid = true;
00319 }
00320 
00321 //===----------------------------------------------------------------------===//
00322 //  PostDominanceFrontier Implementation
00323 //===----------------------------------------------------------------------===//
00324 
00325 static RegisterAnalysis<PostDominanceFrontier>
00326 H("postdomfrontier", "Post-Dominance Frontier Construction", true);
00327 
00328 const DominanceFrontier::DomSetType &
00329 PostDominanceFrontier::calculate(const PostDominatorTree &DT,
00330                                  const DominatorTree::Node *Node) {
00331   // Loop over CFG successors to calculate DFlocal[Node]
00332   BasicBlock *BB = Node->getBlock();
00333   DomSetType &S = Frontiers[BB];       // The new set to fill in...
00334   if (getRoots().empty()) return S;
00335 
00336   if (BB)
00337     for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB);
00338          SI != SE; ++SI)
00339       // Does Node immediately dominate this predecessor?
00340       if (DT[*SI]->getIDom() != Node)
00341         S.insert(*SI);
00342 
00343   // At this point, S is DFlocal.  Now we union in DFup's of our children...
00344   // Loop through and visit the nodes that Node immediately dominates (Node's
00345   // children in the IDomTree)
00346   //
00347   for (PostDominatorTree::Node::const_iterator
00348          NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) {
00349     DominatorTree::Node *IDominee = *NI;
00350     const DomSetType &ChildDF = calculate(DT, IDominee);
00351 
00352     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
00353     for (; CDFI != CDFE; ++CDFI) {
00354       if (!Node->properlyDominates(DT[*CDFI]))
00355         S.insert(*CDFI);
00356     }
00357   }
00358 
00359   return S;
00360 }
00361 
00362 // Ensure that this .cpp file gets linked when PostDominators.h is used.
00363 DEFINING_FILE_FOR(PostDominanceFrontier)