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