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