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/UnifyFunctionExitNodes.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::runOnFunction(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       BasicBlock *BB = *It;
  52       pred_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 *F) {
  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<UnifyFunctionExitNodes>().getExitNode();
  89
  90   if (Root == 0) {  // No exit node for the function?  Postdomsets are all empty
  91     for (Function::iterator FI = F->begin(), FE = F->end(); FI != FE; ++FI)
  92       Doms[*FI] = 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       BasicBlock *BB = *It;
 105       succ_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 // getAnalysisUsage - This obviously provides a dominator set, but it also
 133 // uses the UnifyFunctionExitNodes pass if building post-dominators
 134 //
 135 void cfg::DominatorSet::getAnalysisUsage(AnalysisUsage &AU) const {
 136   AU.setPreservesAll();
 137   if (isPostDominator()) {
 138     AU.addProvided(PostDomID);
 139     AU.addRequired(UnifyFunctionExitNodes::ID);
 140   } else {
 141     AU.addProvided(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     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 Function *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 Function*> 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       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       // function.
 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       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 function.
 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   BasicBlock *BB = Node->getNode();
 336   DomSetType &S = Frontiers[BB];       // The new set to fill in...
 337
 338   for (succ_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   BasicBlock *BB = Node->getNode();
 369   DomSetType &S = Frontiers[BB];       // The new set to fill in...
 370   if (!Root) return S;
 371
 372   for (pred_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 }