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