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