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