lib/VMCore/DominatorCalculation.h

   1 //==- DominatorCalculation.h - Dominator Calculation -------------*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Owen Anderson and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLVM_VMCORE_DOMINATOR_CALCULATION_H
  11 #define LLVM_VMCORE_DOMINATOR_CALCULATION_H
  12
  13 #include "llvm/Analysis/Dominators.h"
  14
  15 //===----------------------------------------------------------------------===//
  16 //
  17 // DominatorTree construction - This pass constructs immediate dominator
  18 // information for a flow-graph based on the algorithm described in this
  19 // document:
  20 //
  21 //   A Fast Algorithm for Finding Dominators in a Flowgraph
  22 //   T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
  23 //
  24 // This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and
  25 // LINK, but it turns out that the theoretically slower O(n*log(n))
  26 // implementation is actually faster than the "efficient" algorithm (even for
  27 // large CFGs) because the constant overheads are substantially smaller.  The
  28 // lower-complexity version can be enabled with the following #define:
  29 //
  30 #define BALANCE_IDOM_TREE 0
  31 //
  32 //===----------------------------------------------------------------------===//
  33
  34 namespace llvm {
  35
  36 void DTCompress(DominatorTree& DT, BasicBlock *VIn) {
  37
  38   std::vector<BasicBlock *> Work;
  39   SmallPtrSet<BasicBlock *, 32> Visited;
  40   BasicBlock *VInAncestor = DT.Info[VIn].Ancestor;
  41   DominatorTree::InfoRec &VInVAInfo = DT.Info[VInAncestor];
  42
  43   if (VInVAInfo.Ancestor != 0)
  44     Work.push_back(VIn);
  45
  46   while (!Work.empty()) {
  47     BasicBlock *V = Work.back();
  48     DominatorTree::InfoRec &VInfo = DT.Info[V];
  49     BasicBlock *VAncestor = VInfo.Ancestor;
  50     DominatorTree::InfoRec &VAInfo = DT.Info[VAncestor];
  51
  52     // Process Ancestor first
  53     if (Visited.insert(VAncestor) &&
  54         VAInfo.Ancestor != 0) {
  55       Work.push_back(VAncestor);
  56       continue;
  57     }
  58     Work.pop_back();
  59
  60     // Update VInfo based on Ancestor info
  61     if (VAInfo.Ancestor == 0)
  62       continue;
  63     BasicBlock *VAncestorLabel = VAInfo.Label;
  64     BasicBlock *VLabel = VInfo.Label;
  65     if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi)
  66       VInfo.Label = VAncestorLabel;
  67     VInfo.Ancestor = VAInfo.Ancestor;
  68   }
  69 }
  70
  71 BasicBlock *DTEval(DominatorTree& DT, BasicBlock *V) {
  72   DominatorTree::InfoRec &VInfo = DT.Info[V];
  73 #if !BALANCE_IDOM_TREE
  74   // Higher-complexity but faster implementation
  75   if (VInfo.Ancestor == 0)
  76     return V;
  77   DTCompress(DT, V);
  78   return VInfo.Label;
  79 #else
  80   // Lower-complexity but slower implementation
  81   if (VInfo.Ancestor == 0)
  82     return VInfo.Label;
  83   DTCompress(DT, V);
  84   BasicBlock *VLabel = VInfo.Label;
  85
  86   BasicBlock *VAncestorLabel = DT.Info[VInfo.Ancestor].Label;
  87   if (DT.Info[VAncestorLabel].Semi >= DT.Info[VLabel].Semi)
  88     return VLabel;
  89   else
  90     return VAncestorLabel;
  91 #endif
  92 }
  93
  94 void DTLink(DominatorTree& DT, BasicBlock *V, BasicBlock *W,
  95             DominatorTree::InfoRec &WInfo) {
  96 #if !BALANCE_IDOM_TREE
  97   // Higher-complexity but faster implementation
  98   WInfo.Ancestor = V;
  99 #else
 100   // Lower-complexity but slower implementation
 101   BasicBlock *WLabel = WInfo.Label;
 102   unsigned WLabelSemi = Info[WLabel].Semi;
 103   BasicBlock *S = W;
 104   InfoRec *SInfo = &Info[S];
 105
 106   BasicBlock *SChild = SInfo->Child;
 107   InfoRec *SChildInfo = &Info[SChild];
 108
 109   while (WLabelSemi < Info[SChildInfo->Label].Semi) {
 110     BasicBlock *SChildChild = SChildInfo->Child;
 111     if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) {
 112       SChildInfo->Ancestor = S;
 113       SInfo->Child = SChild = SChildChild;
 114       SChildInfo = &Info[SChild];
 115     } else {
 116       SChildInfo->Size = SInfo->Size;
 117       S = SInfo->Ancestor = SChild;
 118       SInfo = SChildInfo;
 119       SChild = SChildChild;
 120       SChildInfo = &Info[SChild];
 121     }
 122   }
 123
 124   InfoRec &VInfo = Info[V];
 125   SInfo->Label = WLabel;
 126
 127   assert(V != W && "The optimization here will not work in this case!");
 128   unsigned WSize = WInfo.Size;
 129   unsigned VSize = (VInfo.Size += WSize);
 130
 131   if (VSize < 2*WSize)
 132     std::swap(S, VInfo.Child);
 133
 134   while (S) {
 135     SInfo = &Info[S];
 136     SInfo->Ancestor = V;
 137     S = SInfo->Child;
 138   }
 139 #endif
 140 }
 141
 142 void DTcalculate(DominatorTree& DT, Function &F) {
 143   BasicBlock* Root = DT.Roots[0];
 144
 145   // Add a node for the root...
 146   DT.DomTreeNodes[Root] = DT.RootNode = new DomTreeNode(Root, 0);
 147
 148   DT.Vertex.push_back(0);
 149
 150   // Step #1: Number blocks in depth-first order and initialize variables used
 151   // in later stages of the algorithm.
 152   unsigned N = DT.DFSPass(Root, 0);
 153
 154   for (unsigned i = N; i >= 2; --i) {
 155     BasicBlock *W = DT.Vertex[i];
 156     DominatorTree::InfoRec &WInfo = DT.Info[W];
 157
 158     // Step #2: Calculate the semidominators of all vertices
 159     for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI)
 160       if (DT.Info.count(*PI)) {  // Only if this predecessor is reachable!
 161         unsigned SemiU = DT.Info[DTEval(DT, *PI)].Semi;
 162         if (SemiU < WInfo.Semi)
 163           WInfo.Semi = SemiU;
 164       }
 165
 166     DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W);
 167
 168     BasicBlock *WParent = WInfo.Parent;
 169     DTLink(DT, WParent, W, WInfo);
 170
 171     // Step #3: Implicitly define the immediate dominator of vertices
 172     std::vector<BasicBlock*> &WParentBucket = DT.Info[WParent].Bucket;
 173     while (!WParentBucket.empty()) {
 174       BasicBlock *V = WParentBucket.back();
 175       WParentBucket.pop_back();
 176       BasicBlock *U = DTEval(DT, V);
 177       DT.IDoms[V] = DT.Info[U].Semi < DT.Info[V].Semi ? U : WParent;
 178     }
 179   }
 180
 181   // Step #4: Explicitly define the immediate dominator of each vertex
 182   for (unsigned i = 2; i <= N; ++i) {
 183     BasicBlock *W = DT.Vertex[i];
 184     BasicBlock *&WIDom = DT.IDoms[W];
 185     if (WIDom != DT.Vertex[DT.Info[W].Semi])
 186       WIDom = DT.IDoms[WIDom];
 187   }
 188
 189   // Loop over all of the reachable blocks in the function...
 190   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 191     if (BasicBlock *ImmDom = DT.getIDom(I)) {  // Reachable block.
 192       DomTreeNode *BBNode = DT.DomTreeNodes[I];
 193       if (BBNode) continue;  // Haven't calculated this node yet?
 194
 195       // Get or calculate the node for the immediate dominator
 196       DomTreeNode *IDomNode = DT.getNodeForBlock(ImmDom);
 197
 198       // Add a new tree node for this BasicBlock, and link it as a child of
 199       // IDomNode
 200       DomTreeNode *C = new DomTreeNode(I, IDomNode);
 201       DT.DomTreeNodes[I] = IDomNode->addChild(C);
 202     }
 203
 204   // Free temporary memory used to construct idom's
 205   DT.Info.clear();
 206   DT.IDoms.clear();
 207   std::vector<BasicBlock*>().swap(DT.Vertex);
 208
 209   DT.updateDFSNumbers();
 210 }
 211
 212 }
 213 #endif