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