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