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