lib/VMCore/Dominators.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/Analysis/SimplifyCFG.h"   // To get cfg::UnifyAllExitNodes
   9 #include "llvm/Support/DepthFirstIterator.h"
  10 #include "llvm/Support/STLExtras.h"
  11 #include "llvm/Method.h"
  12 #include <algorithm>
  13
  14 //===----------------------------------------------------------------------===//
  15 //  Helper Template
  16 //===----------------------------------------------------------------------===//
  17
  18 // set_intersect - Identical to set_intersection, except that it works on
  19 // set<>'s and is nicer to use.  Functionally, this iterates through S1,
  20 // removing elements that are not contained in S2.
  21 //
  22 template <class Ty, class Ty2>
  23 void set_intersect(set<Ty> &S1, const set<Ty2> &S2) {
  24   for (typename set<Ty>::iterator I = S1.begin(); I != S1.end();) {
  25     const Ty &E = *I;
  26     ++I;
  27     if (!S2.count(E)) S1.erase(E);   // Erase element if not in S2
  28   }
  29 }
  30
  31 //===----------------------------------------------------------------------===//
  32 //  DominatorBase Implementation
  33 //===----------------------------------------------------------------------===//
  34
  35 bool cfg::DominatorBase::isPostDominator() const {
  36   // Root can be null if there is no exit node from the CFG and is postdom set
  37   return Root == 0 || Root != Root->getParent()->front();
  38 }
  39
  40
  41 //===----------------------------------------------------------------------===//
  42 //  DominatorSet Implementation
  43 //===----------------------------------------------------------------------===//
  44
  45 // DominatorSet ctor - Build either the dominator set or the post-dominator
  46 // set for a method...
  47 //
  48 cfg::DominatorSet::DominatorSet(const Method *M) : DominatorBase(M->front()) {
  49   calcForwardDominatorSet(M);
  50 }
  51
  52 // calcForwardDominatorSet - This method calculates the forward dominator sets
  53 // for the specified method.
  54 //
  55 void cfg::DominatorSet::calcForwardDominatorSet(const Method *M) {
  56   assert(Root && M && "Can't build dominator set of null method!");
  57   assert(Root->use_size() == 0 && "Root node has predecessors in method!");
  58   bool Changed;
  59   do {
  60     Changed = false;
  61
  62     DomSetType WorkingSet;
  63     df_iterator<const Method*> It = df_begin(M), End = df_end(M);
  64     for ( ; It != End; ++It) {
  65       const BasicBlock *BB = *It;
  66       pred_const_iterator PI = pred_begin(BB), PEnd = pred_end(BB);
  67       if (PI != PEnd) {                // Is there SOME predecessor?
  68         // Loop until we get to a predecessor that has had it's dom set filled
  69         // in at least once.  We are guaranteed to have this because we are
  70         // traversing the graph in DFO and have handled start nodes specially.
  71         //
  72         while (Doms[*PI].size() == 0) ++PI;
  73         WorkingSet = Doms[*PI];
  74
  75         for (++PI; PI != PEnd; ++PI) { // Intersect all of the predecessor sets
  76           DomSetType &PredSet = Doms[*PI];
  77           if (PredSet.size())
  78             set_intersect(WorkingSet, PredSet);
  79         }
  80       }
  81
  82       WorkingSet.insert(BB);           // A block always dominates itself
  83       DomSetType &BBSet = Doms[BB];
  84       if (BBSet != WorkingSet) {
  85         BBSet.swap(WorkingSet);        // Constant time operation!
  86         Changed = true;                // The sets changed.
  87       }
  88       WorkingSet.clear();              // Clear out the set for next iteration
  89     }
  90   } while (Changed);
  91 }
  92
  93 // Postdominator set constructor.  This ctor converts the specified method to
  94 // only have a single exit node (return stmt), then calculates the post
  95 // dominance sets for the method.
  96 //
  97 cfg::DominatorSet::DominatorSet(Method *M, bool PostDomSet)
  98   : DominatorBase(M->front()) {
  99   if (!PostDomSet) { calcForwardDominatorSet(M); return; }
 100
 101   Root = cfg::UnifyAllExitNodes(M);
 102   if (Root == 0) {  // No exit node for the method?  Postdomsets are all empty
 103     for (Method::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI)
 104       Doms[*MI] = DomSetType();
 105     return;
 106   }
 107
 108   bool Changed;
 109   do {
 110     Changed = false;
 111
 112     set<const BasicBlock*> Visited;
 113     DomSetType WorkingSet;
 114     idf_iterator<const BasicBlock*> It = idf_begin(Root), End = idf_end(Root);
 115     for ( ; It != End; ++It) {
 116       const BasicBlock *BB = *It;
 117       succ_const_iterator PI = succ_begin(BB), PEnd = succ_end(BB);
 118       if (PI != PEnd) {                // Is there SOME predecessor?
 119         // Loop until we get to a successor that has had it's dom set filled
 120         // in at least once.  We are guaranteed to have this because we are
 121         // traversing the graph in DFO and have handled start nodes specially.
 122         //
 123         while (Doms[*PI].size() == 0) ++PI;
 124         WorkingSet = Doms[*PI];
 125
 126         for (++PI; PI != PEnd; ++PI) { // Intersect all of the successor sets
 127           DomSetType &PredSet = Doms[*PI];
 128           if (PredSet.size())
 129             set_intersect(WorkingSet, PredSet);
 130         }
 131       }
 132
 133       WorkingSet.insert(BB);           // A block always dominates itself
 134       DomSetType &BBSet = Doms[BB];
 135       if (BBSet != WorkingSet) {
 136         BBSet.swap(WorkingSet);        // Constant time operation!
 137         Changed = true;                // The sets changed.
 138       }
 139       WorkingSet.clear();              // Clear out the set for next iteration
 140     }
 141   } while (Changed);
 142 }
 143
 144
 145 //===----------------------------------------------------------------------===//
 146 //  ImmediateDominators Implementation
 147 //===----------------------------------------------------------------------===//
 148
 149 // calcIDoms - Calculate the immediate dominator mapping, given a set of
 150 // dominators for every basic block.
 151 void cfg::ImmediateDominators::calcIDoms(const DominatorSet &DS) {
 152   // Loop over all of the nodes that have dominators... figuring out the IDOM
 153   // for each node...
 154   //
 155   for (DominatorSet::const_iterator DI = DS.begin(), DEnd = DS.end();
 156        DI != DEnd; ++DI) {
 157     const BasicBlock *BB = DI->first;
 158     const DominatorSet::DomSetType &Dominators = DI->second;
 159     unsigned DomSetSize = Dominators.size();
 160     if (DomSetSize == 1) continue;  // Root node... IDom = null
 161
 162     // Loop over all dominators of this node.  This corresponds to looping over
 163     // nodes in the dominator chain, looking for a node whose dominator set is
 164     // equal to the current nodes, except that the current node does not exist
 165     // in it.  This means that it is one level higher in the dom chain than the
 166     // current node, and it is our idom!
 167     //
 168     DominatorSet::DomSetType::const_iterator I = Dominators.begin();
 169     DominatorSet::DomSetType::const_iterator End = Dominators.end();
 170     for (; I != End; ++I) {   // Iterate over dominators...
 171       // All of our dominators should form a chain, where the number of elements
 172       // in the dominator set indicates what level the node is at in the chain.
 173       // We want the node immediately above us, so it will have an identical
 174       // dominator set, except that BB will not dominate it... therefore it's
 175       // dominator set size will be one less than BB's...
 176       //
 177       if (DS.getDominators(*I).size() == DomSetSize - 1) {
 178         IDoms[BB] = *I;
 179         break;
 180       }
 181     }
 182   }
 183 }
 184
 185
 186 //===----------------------------------------------------------------------===//
 187 //  DominatorTree Implementation
 188 //===----------------------------------------------------------------------===//
 189
 190 // DominatorTree dtor - Free all of the tree node memory.
 191 //
 192 cfg::DominatorTree::~DominatorTree() {
 193   for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
 194     delete I->second;
 195 }
 196
 197
 198 cfg::DominatorTree::DominatorTree(const ImmediateDominators &IDoms)
 199   : DominatorBase(IDoms.getRoot()) {
 200   const Method *M = Root->getParent();
 201
 202   Nodes[Root] = new Node(Root, 0);   // Add a node for the root...
 203
 204   // Iterate over all nodes in depth first order...
 205   for (df_iterator<const Method*> I = df_begin(M), E = df_end(M); I != E; ++I) {
 206     const BasicBlock *BB = *I, *IDom = IDoms[*I];
 207
 208     if (IDom != 0) {   // Ignore the root node and other nasty nodes
 209       // We know that the immediate dominator should already have a node,
 210       // because we are traversing the CFG in depth first order!
 211       //
 212       assert(Nodes[IDom] && "No node for IDOM?");
 213       Node *IDomNode = Nodes[IDom];
 214
 215       // Add a new tree node for this BasicBlock, and link it as a child of
 216       // IDomNode
 217       Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
 218     }
 219   }
 220 }
 221
 222 void cfg::DominatorTree::calculate(const DominatorSet &DS) {
 223   Nodes[Root] = new Node(Root, 0);   // Add a node for the root...
 224
 225   if (!isPostDominator()) {
 226     // Iterate over all nodes in depth first order...
 227     for (df_iterator<const BasicBlock*> I = df_begin(Root), E = df_end(Root);
 228          I != E; ++I) {
 229       const BasicBlock *BB = *I;
 230       const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
 231       unsigned DomSetSize = Dominators.size();
 232       if (DomSetSize == 1) continue;  // Root node... IDom = null
 233
 234       // Loop over all dominators of this node. This corresponds to looping over
 235       // nodes in the dominator chain, looking for a node whose dominator set is
 236       // equal to the current nodes, except that the current node does not exist
 237       // in it. This means that it is one level higher in the dom chain than the
 238       // current node, and it is our idom!  We know that we have already added
 239       // a DominatorTree node for our idom, because the idom must be a
 240       // predecessor in the depth first order that we are iterating through the
 241       // method.
 242       //
 243       DominatorSet::DomSetType::const_iterator I = Dominators.begin();
 244       DominatorSet::DomSetType::const_iterator End = Dominators.end();
 245       for (; I != End; ++I) {   // Iterate over dominators...
 246         // All of our dominators should form a chain, where the number of
 247         // elements in the dominator set indicates what level the node is at in
 248         // the chain.  We want the node immediately above us, so it will have
 249         // an identical dominator set, except that BB will not dominate it...
 250         // therefore it's dominator set size will be one less than BB's...
 251         //
 252         if (DS.getDominators(*I).size() == DomSetSize - 1) {
 253           // We know that the immediate dominator should already have a node,
 254           // because we are traversing the CFG in depth first order!
 255           //
 256           Node *IDomNode = Nodes[*I];
 257           assert(IDomNode && "No node for IDOM?");
 258
 259           // Add a new tree node for this BasicBlock, and link it as a child of
 260           // IDomNode
 261           Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
 262           break;
 263         }
 264       }
 265     }
 266   } else if (Root) {
 267     // Iterate over all nodes in depth first order...
 268     for (idf_iterator<const BasicBlock*> I = idf_begin(Root), E = idf_end(Root);
 269          I != E; ++I) {
 270       const BasicBlock *BB = *I;
 271       const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
 272       unsigned DomSetSize = Dominators.size();
 273       if (DomSetSize == 1) continue;  // Root node... IDom = null
 274
 275       // Loop over all dominators of this node.  This corresponds to looping
 276       // over nodes in the dominator chain, looking for a node whose dominator
 277       // set is equal to the current nodes, except that the current node does
 278       // not exist in it.  This means that it is one level higher in the dom
 279       // chain than the current node, and it is our idom!  We know that we have
 280       // already added a DominatorTree node for our idom, because the idom must
 281       // be a predecessor in the depth first order that we are iterating through
 282       // the method.
 283       //
 284       DominatorSet::DomSetType::const_iterator I = Dominators.begin();
 285       DominatorSet::DomSetType::const_iterator End = Dominators.end();
 286       for (; I != End; ++I) {   // Iterate over dominators...
 287         // All of our dominators should form a chain, where the number of elements
 288         // in the dominator set indicates what level the node is at in the chain.
 289         // We want the node immediately above us, so it will have an identical
 290         // dominator set, except that BB will not dominate it... therefore it's
 291         // dominator set size will be one less than BB's...
 292         //
 293         if (DS.getDominators(*I).size() == DomSetSize - 1) {
 294           // We know that the immediate dominator should already have a node,
 295           // because we are traversing the CFG in depth first order!
 296           //
 297           Node *IDomNode = Nodes[*I];
 298           assert(IDomNode && "No node for IDOM?");
 299
 300           // Add a new tree node for this BasicBlock, and link it as a child of
 301           // IDomNode
 302           Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
 303           break;
 304         }
 305       }
 306     }
 307   }
 308 }
 309
 310
 311
 312 //===----------------------------------------------------------------------===//
 313 //  DominanceFrontier Implementation
 314 //===----------------------------------------------------------------------===//
 315
 316 const cfg::DominanceFrontier::DomSetType &
 317 cfg::DominanceFrontier::calcDomFrontier(const DominatorTree &DT,
 318                                         const DominatorTree::Node *Node) {
 319   // Loop over CFG successors to calculate DFlocal[Node]
 320   const BasicBlock *BB = Node->getNode();
 321   DomSetType &S = Frontiers[BB];       // The new set to fill in...
 322
 323   for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
 324        SI != SE; ++SI) {
 325     // Does Node immediately dominate this successor?
 326     if (DT[*SI]->getIDom() != Node)
 327       S.insert(*SI);
 328   }
 329
 330   // At this point, S is DFlocal.  Now we union in DFup's of our children...
 331   // Loop through and visit the nodes that Node immediately dominates (Node's
 332   // children in the IDomTree)
 333   //
 334   for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
 335        NI != NE; ++NI) {
 336     DominatorTree::Node *IDominee = *NI;
 337     const DomSetType &ChildDF = calcDomFrontier(DT, IDominee);
 338
 339     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
 340     for (; CDFI != CDFE; ++CDFI) {
 341       if (!Node->dominates(DT[*CDFI]))
 342         S.insert(*CDFI);
 343     }
 344   }
 345
 346   return S;
 347 }
 348
 349 const cfg::DominanceFrontier::DomSetType &
 350 cfg::DominanceFrontier::calcPostDomFrontier(const DominatorTree &DT,
 351                                             const DominatorTree::Node *Node) {
 352   // Loop over CFG successors to calculate DFlocal[Node]
 353   const BasicBlock *BB = Node->getNode();
 354   DomSetType &S = Frontiers[BB];       // The new set to fill in...
 355   if (!Root) return S;
 356
 357   for (pred_const_iterator SI = pred_begin(BB), SE = pred_end(BB);
 358        SI != SE; ++SI) {
 359     // Does Node immediately dominate this predeccessor?
 360     if (DT[*SI]->getIDom() != Node)
 361       S.insert(*SI);
 362   }
 363
 364   // At this point, S is DFlocal.  Now we union in DFup's of our children...
 365   // Loop through and visit the nodes that Node immediately dominates (Node's
 366   // children in the IDomTree)
 367   //
 368   for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
 369        NI != NE; ++NI) {
 370     DominatorTree::Node *IDominee = *NI;
 371     const DomSetType &ChildDF = calcPostDomFrontier(DT, IDominee);
 372
 373     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
 374     for (; CDFI != CDFE; ++CDFI) {
 375       if (!Node->dominates(DT[*CDFI]))
 376         S.insert(*CDFI);
 377     }
 378   }
 379
 380   return S;
 381 }