lib/Analysis/PostDominators.cpp

   1 //===- PostDominators.cpp - Post-Dominator Calculation --------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the post-dominator construction algorithms.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/PostDominators.h"
  15 #include "llvm/Instructions.h"
  16 #include "llvm/Support/CFG.h"
  17 #include "llvm/ADT/DepthFirstIterator.h"
  18 #include "llvm/ADT/SetOperations.h"
  19 using namespace llvm;
  20
  21 //===----------------------------------------------------------------------===//
  22 //  PostDominatorTree Implementation
  23 //===----------------------------------------------------------------------===//
  24
  25 char PostDominatorTree::ID = 0;
  26 char PostDominanceFrontier::ID = 0;
  27 static RegisterPass<PostDominatorTree>
  28 F("postdomtree", "Post-Dominator Tree Construction", true);
  29
  30 unsigned PostDominatorTree::DFSPass(BasicBlock *V, unsigned N) {
  31   std::vector<BasicBlock *> workStack;
  32   SmallPtrSet<BasicBlock *, 32> Visited;
  33   workStack.push_back(V);
  34
  35   do {
  36     BasicBlock *currentBB = workStack.back();
  37     InfoRec &CurVInfo = Info[currentBB];
  38
  39     // Visit each block only once.
  40     if (Visited.insert(currentBB)) {
  41       CurVInfo.Semi = ++N;
  42       CurVInfo.Label = currentBB;
  43
  44       Vertex.push_back(currentBB);  // Vertex[n] = current;
  45       // Info[currentBB].Ancestor = 0;
  46       // Ancestor[n] = 0
  47       // Child[currentBB] = 0;
  48       CurVInfo.Size = 1;       // Size[currentBB] = 1
  49     }
  50
  51     // Visit children
  52     bool visitChild = false;
  53     for (pred_iterator PI = pred_begin(currentBB), PE = pred_end(currentBB);
  54          PI != PE && !visitChild; ++PI) {
  55       InfoRec &SuccVInfo = Info[*PI];
  56       if (SuccVInfo.Semi == 0) {
  57         SuccVInfo.Parent = currentBB;
  58         if (!Visited.count(*PI)) {
  59           workStack.push_back(*PI);
  60           visitChild = true;
  61         }
  62       }
  63     }
  64
  65     // If all children are visited or if this block has no child then pop this
  66     // block out of workStack.
  67     if (!visitChild)
  68       workStack.pop_back();
  69
  70   } while (!workStack.empty());
  71
  72   return N;
  73 }
  74
  75 void PostDominatorTree::Compress(BasicBlock *V, InfoRec &VInfo) {
  76   BasicBlock *VAncestor = VInfo.Ancestor;
  77   InfoRec &VAInfo = Info[VAncestor];
  78   if (VAInfo.Ancestor == 0)
  79     return;
  80
  81   Compress(VAncestor, VAInfo);
  82
  83   BasicBlock *VAncestorLabel = VAInfo.Label;
  84   BasicBlock *VLabel = VInfo.Label;
  85   if (Info[VAncestorLabel].Semi < Info[VLabel].Semi)
  86     VInfo.Label = VAncestorLabel;
  87
  88   VInfo.Ancestor = VAInfo.Ancestor;
  89 }
  90
  91 BasicBlock *PostDominatorTree::Eval(BasicBlock *V) {
  92   InfoRec &VInfo = Info[V];
  93
  94   // Higher-complexity but faster implementation
  95   if (VInfo.Ancestor == 0)
  96     return V;
  97   Compress(V, VInfo);
  98   return VInfo.Label;
  99 }
 100
 101 void PostDominatorTree::Link(BasicBlock *V, BasicBlock *W,
 102                                    InfoRec &WInfo) {
 103   // Higher-complexity but faster implementation
 104   WInfo.Ancestor = V;
 105 }
 106
 107 void PostDominatorTree::calculate(Function &F) {
 108   // Step #0: Scan the function looking for the root nodes of the post-dominance
 109   // relationships.  These blocks, which have no successors, end with return and
 110   // unwind instructions.
 111   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 112     TerminatorInst *Insn = I->getTerminator();
 113     if (Insn->getNumSuccessors() == 0) {
 114       // Unreachable block is not a root node.
 115       if (!isa<UnreachableInst>(Insn))
 116         Roots.push_back(I);
 117     }
 118
 119     // Prepopulate maps so that we don't get iterator invalidation issues later.
 120     IDoms[I] = 0;
 121     DomTreeNodes[I] = 0;
 122   }
 123
 124   Vertex.push_back(0);
 125
 126   // Step #1: Number blocks in depth-first order and initialize variables used
 127   // in later stages of the algorithm.
 128   unsigned N = 0;
 129   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
 130     N = DFSPass(Roots[i], N);
 131
 132   for (unsigned i = N; i >= 2; --i) {
 133     BasicBlock *W = Vertex[i];
 134     InfoRec &WInfo = Info[W];
 135
 136     // Step #2: Calculate the semidominators of all vertices
 137     for (succ_iterator SI = succ_begin(W), SE = succ_end(W); SI != SE; ++SI)
 138       if (Info.count(*SI)) {  // Only if this predecessor is reachable!
 139         unsigned SemiU = Info[Eval(*SI)].Semi;
 140         if (SemiU < WInfo.Semi)
 141           WInfo.Semi = SemiU;
 142       }
 143
 144     Info[Vertex[WInfo.Semi]].Bucket.push_back(W);
 145
 146     BasicBlock *WParent = WInfo.Parent;
 147     Link(WParent, W, WInfo);
 148
 149     // Step #3: Implicitly define the immediate dominator of vertices
 150     std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket;
 151     while (!WParentBucket.empty()) {
 152       BasicBlock *V = WParentBucket.back();
 153       WParentBucket.pop_back();
 154       BasicBlock *U = Eval(V);
 155       IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent;
 156     }
 157   }
 158
 159   // Step #4: Explicitly define the immediate dominator of each vertex
 160   for (unsigned i = 2; i <= N; ++i) {
 161     BasicBlock *W = Vertex[i];
 162     BasicBlock *&WIDom = IDoms[W];
 163     if (WIDom != Vertex[Info[W].Semi])
 164       WIDom = IDoms[WIDom];
 165   }
 166
 167   if (Roots.empty()) return;
 168
 169   // Add a node for the root.  This node might be the actual root, if there is
 170   // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0)
 171   // which postdominates all real exits if there are multiple exit blocks.
 172   BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0;
 173   DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0);
 174
 175   // Loop over all of the reachable blocks in the function...
 176   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 177     if (BasicBlock *ImmPostDom = getIDom(I)) {  // Reachable block.
 178       DomTreeNode *&BBNode = DomTreeNodes[I];
 179       if (!BBNode) {  // Haven't calculated this node yet?
 180                       // Get or calculate the node for the immediate dominator
 181         DomTreeNode *IPDomNode = getNodeForBlock(ImmPostDom);
 182
 183         // Add a new tree node for this BasicBlock, and link it as a child of
 184         // IDomNode
 185         DomTreeNode *C = new DomTreeNode(I, IPDomNode);
 186         DomTreeNodes[I] = C;
 187         BBNode = IPDomNode->addChild(C);
 188       }
 189     }
 190
 191   // Free temporary memory used to construct idom's
 192   IDoms.clear();
 193   Info.clear();
 194   std::vector<BasicBlock*>().swap(Vertex);
 195
 196   int dfsnum = 0;
 197   // Iterate over all nodes in depth first order...
 198   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
 199     for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]),
 200            E = idf_end(Roots[i]); I != E; ++I) {
 201       if (!getNodeForBlock(*I)->getIDom())
 202         getNodeForBlock(*I)->assignDFSNumber(dfsnum);
 203     }
 204   DFSInfoValid = true;
 205 }
 206
 207
 208 DomTreeNode *PostDominatorTree::getNodeForBlock(BasicBlock *BB) {
 209   DomTreeNode *&BBNode = DomTreeNodes[BB];
 210   if (BBNode) return BBNode;
 211
 212   // Haven't calculated this node yet?  Get or calculate the node for the
 213   // immediate postdominator.
 214   BasicBlock *IPDom = getIDom(BB);
 215   DomTreeNode *IPDomNode = getNodeForBlock(IPDom);
 216
 217   // Add a new tree node for this BasicBlock, and link it as a child of
 218   // IDomNode
 219   DomTreeNode *C = new DomTreeNode(BB, IPDomNode);
 220   DomTreeNodes[BB] = C;
 221   return BBNode = IPDomNode->addChild(C);
 222 }
 223
 224 //===----------------------------------------------------------------------===//
 225 //  PostDominanceFrontier Implementation
 226 //===----------------------------------------------------------------------===//
 227
 228 static RegisterPass<PostDominanceFrontier>
 229 H("postdomfrontier", "Post-Dominance Frontier Construction", true);
 230
 231 const DominanceFrontier::DomSetType &
 232 PostDominanceFrontier::calculate(const PostDominatorTree &DT,
 233                                  const DomTreeNode *Node) {
 234   // Loop over CFG successors to calculate DFlocal[Node]
 235   BasicBlock *BB = Node->getBlock();
 236   DomSetType &S = Frontiers[BB];       // The new set to fill in...
 237   if (getRoots().empty()) return S;
 238
 239   if (BB)
 240     for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB);
 241          SI != SE; ++SI) {
 242       // Does Node immediately dominate this predecessor?
 243       DomTreeNode *SINode = DT[*SI];
 244       if (SINode && SINode->getIDom() != Node)
 245         S.insert(*SI);
 246     }
 247
 248   // At this point, S is DFlocal.  Now we union in DFup's of our children...
 249   // Loop through and visit the nodes that Node immediately dominates (Node's
 250   // children in the IDomTree)
 251   //
 252   for (DomTreeNode::const_iterator
 253          NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) {
 254     DomTreeNode *IDominee = *NI;
 255     const DomSetType &ChildDF = calculate(DT, IDominee);
 256
 257     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
 258     for (; CDFI != CDFE; ++CDFI) {
 259       if (!DT.properlyDominates(Node, DT[*CDFI]))
 260         S.insert(*CDFI);
 261     }
 262   }
 263
 264   return S;
 265 }
 266
 267 // Ensure that this .cpp file gets linked when PostDominators.h is used.
 268 DEFINING_FILE_FOR(PostDominanceFrontier)