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