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