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