lib/Analysis/PostDominators.cpp

   1 //===- DominatorSet.cpp - Dominator Set Calculation --------------*- C++ -*--=//
   2 //
   3 // This file provides a simple class to calculate the dominator set of a method.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/Analysis/Dominators.h"
   8 #include "llvm/CFG.h"
   9 #include "llvm/Tools/STLExtras.h"
  10 #include <algorithm>
  11
  12 //===----------------------------------------------------------------------===//
  13 //  Helper Template
  14 //===----------------------------------------------------------------------===//
  15
  16 // set_intersect - Identical to set_intersection, except that it works on
  17 // set<>'s and is nicer to use.  Functionally, this iterates through S1,
  18 // removing elements that are not contained in S2.
  19 //
  20 template <class Ty, class Ty2>
  21 void set_intersect(set<Ty> &S1, const set<Ty2> &S2) {
  22   for (typename set<Ty>::iterator I = S1.begin(); I != S1.end();) {
  23     const Ty &E = *I;
  24     ++I;
  25     if (!S2.count(E)) S1.erase(E);   // Erase element if not in S2
  26   }
  27 }
  28
  29
  30 //===----------------------------------------------------------------------===//
  31 //  DominatorSet Implementation
  32 //===----------------------------------------------------------------------===//
  33
  34 // DominatorSet ctor - Build either the dominator set or the post-dominator
  35 // set for a method...
  36 //
  37 cfg::DominatorSet::DominatorSet(const Method *M, bool PostDomSet)
  38   : Root(M->front()) {
  39   assert(Root && M && "Can't build dominator set of null method!");
  40   bool Changed;
  41   do {
  42     Changed = false;
  43
  44     DomSetType WorkingSet;
  45     df_const_iterator It = df_begin(M), End = df_end(M);
  46     for ( ; It != End; ++It) {
  47       const BasicBlock *BB = *It;
  48       pred_const_iterator PI = pred_begin(BB), PEnd = pred_end(BB);
  49       if (PI != PEnd) {                // Is there SOME predecessor?
  50         // Loop until we get to a predecessor that has had it's dom set filled
  51         // in at least once.  We are guaranteed to have this because we are
  52         // traversing the graph in DFO and have handled start nodes specially.
  53         //
  54         while (Doms[*PI].size() == 0) ++PI;
  55         WorkingSet = Doms[*PI];
  56
  57         for (++PI; PI != PEnd; ++PI) { // Intersect all of the predecessor sets
  58           DomSetType &PredSet = Doms[*PI];
  59           if (PredSet.size())
  60             set_intersect(WorkingSet, PredSet);
  61         }
  62       }
  63
  64       WorkingSet.insert(BB);           // A block always dominates itself
  65       DomSetType &BBSet = Doms[BB];
  66       if (BBSet != WorkingSet) {
  67         BBSet.swap(WorkingSet);        // Constant time operation!
  68         Changed = true;                // The sets changed.
  69       }
  70       WorkingSet.clear();              // Clear out the set for next iteration
  71     }
  72   } while (Changed);
  73
  74 }
  75
  76
  77 //===----------------------------------------------------------------------===//
  78 //  ImmediateDominators Implementation
  79 //===----------------------------------------------------------------------===//
  80
  81 // calcIDoms - Calculate the immediate dominator mapping, given a set of
  82 // dominators for every basic block.
  83 void cfg::ImmediateDominators::calcIDoms(const DominatorSet &DS) {
  84   // Loop over all of the nodes that have dominators... figuring out the IDOM
  85   // for each node...
  86   //
  87   for (DominatorSet::const_iterator DI = DS.begin(), DEnd = DS.end();
  88        DI != DEnd; ++DI) {
  89     const BasicBlock *BB = DI->first;
  90     const DominatorSet::DomSetType &Dominators = DI->second;
  91     unsigned DomSetSize = Dominators.size();
  92     if (DomSetSize == 1) continue;  // Root node... IDom = null
  93
  94     // Loop over all dominators of this node.  This corresponds to looping over
  95     // nodes in the dominator chain, looking for a node whose dominator set is
  96     // equal to the current nodes, except that the current node does not exist
  97     // in it.  This means that it is one level higher in the dom chain than the
  98     // current node, and it is our idom!
  99     //
 100     DominatorSet::DomSetType::const_iterator I = Dominators.begin();
 101     DominatorSet::DomSetType::const_iterator End = Dominators.end();
 102     for (; I != End; ++I) {   // Iterate over dominators...
 103       // All of our dominators should form a chain, where the number of elements
 104       // in the dominator set indicates what level the node is at in the chain.
 105       // We want the node immediately above us, so it will have an identical
 106       // dominator set, except that BB will not dominate it... therefore it's
 107       // dominator set size will be one less than BB's...
 108       //
 109       if (DS.getDominators(*I).size() == DomSetSize - 1) {
 110         IDoms[BB] = *I;
 111         break;
 112       }
 113     }
 114   }
 115 }
 116
 117
 118 //===----------------------------------------------------------------------===//
 119 //  DominatorTree Implementation
 120 //===----------------------------------------------------------------------===//
 121
 122 // DominatorTree dtor - Free all of the tree node memory.
 123 //
 124 cfg::DominatorTree::~DominatorTree() {
 125   for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
 126     delete I->second;
 127 }
 128
 129
 130 cfg::DominatorTree::DominatorTree(const ImmediateDominators &IDoms)
 131   : Root(IDoms.getRoot()) {
 132   assert(Root && Root->getParent() && "No method for IDoms?");
 133   const Method *M = Root->getParent();
 134
 135   Nodes[Root] = new Node(Root, 0);   // Add a node for the root...
 136
 137   // Iterate over all nodes in depth first order...
 138   for (df_const_iterator I = df_begin(M), E = df_end(M); I != E; ++I) {
 139     const BasicBlock *BB = *I, *IDom = IDoms[*I];
 140
 141     if (IDom != 0) {   // Ignore the root node and other nasty nodes
 142       // We know that the immediate dominator should already have a node,
 143       // because we are traversing the CFG in depth first order!
 144       //
 145       assert(Nodes[IDom] && "No node for IDOM?");
 146       Node *IDomNode = Nodes[IDom];
 147
 148       // Add a new tree node for this BasicBlock, and link it as a child of
 149       // IDomNode
 150       Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
 151     }
 152   }
 153 }
 154
 155 void cfg::DominatorTree::calculate(const DominatorSet &DS) {
 156   Root = DS.getRoot();
 157   assert(Root && Root->getParent() && "No method for IDoms?");
 158   const Method *M = Root->getParent();
 159   Nodes[Root] = new Node(Root, 0);   // Add a node for the root...
 160
 161   // Iterate over all nodes in depth first order...
 162   for (df_const_iterator I = df_begin(M), E = df_end(M); I != E; ++I) {
 163     const BasicBlock *BB = *I;
 164     const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
 165     unsigned DomSetSize = Dominators.size();
 166     if (DomSetSize == 1) continue;  // Root node... IDom = null
 167
 168     // Loop over all dominators of this node.  This corresponds to looping over
 169     // nodes in the dominator chain, looking for a node whose dominator set is
 170     // equal to the current nodes, except that the current node does not exist
 171     // in it.  This means that it is one level higher in the dom chain than the
 172     // current node, and it is our idom!  We know that we have already added
 173     // a DominatorTree node for our idom, because the idom must be a
 174     // predecessor in the depth first order that we are iterating through the
 175     // method.
 176     //
 177     DominatorSet::DomSetType::const_iterator I = Dominators.begin();
 178     DominatorSet::DomSetType::const_iterator End = Dominators.end();
 179     for (; I != End; ++I) {   // Iterate over dominators...
 180       // All of our dominators should form a chain, where the number of elements
 181       // in the dominator set indicates what level the node is at in the chain.
 182       // We want the node immediately above us, so it will have an identical
 183       // dominator set, except that BB will not dominate it... therefore it's
 184       // dominator set size will be one less than BB's...
 185       //
 186       if (DS.getDominators(*I).size() == DomSetSize - 1) {
 187         // We know that the immediate dominator should already have a node,
 188         // because we are traversing the CFG in depth first order!
 189         //
 190         Node *IDomNode = Nodes[*I];
 191         assert(Nodes[*I] && "No node for IDOM?");
 192
 193         // Add a new tree node for this BasicBlock, and link it as a child of
 194         // IDomNode
 195         Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
 196         break;
 197       }
 198     }
 199   }
 200 }
 201
 202
 203
 204 //===----------------------------------------------------------------------===//
 205 //  DominanceFrontier Implementation
 206 //===----------------------------------------------------------------------===//
 207
 208 const cfg::DominanceFrontier::DomSetType &
 209 cfg::DominanceFrontier::calcDomFrontier(const DominatorTree &DT,
 210                                         const DominatorTree::Node *Node) {
 211   // Loop over CFG successors to calculate DFlocal[Node]
 212   const BasicBlock *BB = Node->getNode();
 213   DomSetType &S = Frontiers[BB];       // The new set to fill in...
 214
 215   for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
 216        SI != SE; ++SI) {
 217     // Does Node immediately dominate this successor?
 218     if (DT[*SI]->getIDom() != Node)
 219       S.insert(*SI);
 220   }
 221
 222   // At this point, S is DFlocal.  Now we union in DFup's of our children...
 223   // Loop through and visit the nodes that Node immediately dominates (Node's
 224   // children in the IDomTree)
 225   //
 226   for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
 227        NI != NE; ++NI) {
 228     DominatorTree::Node *IDominee = *NI;
 229     const DomSetType &ChildDF = calcDomFrontier(DT, IDominee);
 230
 231     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
 232     for (; CDFI != CDFE; ++CDFI) {
 233       if (!Node->dominates(DT[*CDFI]))
 234         S.insert(*CDFI);
 235     }
 236   }
 237
 238   return S;
 239 }