lib/Analysis/PostDominators.cpp

   1 //===- PostDominators.cpp - Post-Dominator Calculation --------------------===//
   2 //
   3 // This file implements the post-dominator construction algorithms.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/Analysis/PostDominators.h"
   8 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
   9 #include "llvm/Support/CFG.h"
  10 #include "Support/DepthFirstIterator.h"
  11 #include "Support/SetOperations.h"
  12
  13 //===----------------------------------------------------------------------===//
  14 //  PostDominatorSet Implementation
  15 //===----------------------------------------------------------------------===//
  16
  17 static RegisterAnalysis<PostDominatorSet>
  18 B("postdomset", "Post-Dominator Set Construction", true);
  19
  20 // Postdominator set construction.  This converts the specified function to only
  21 // have a single exit node (return stmt), then calculates the post dominance
  22 // sets for the function.
  23 //
  24 bool PostDominatorSet::runOnFunction(Function &F) {
  25   Doms.clear();   // Reset from the last time we were run...
  26   // Since we require that the unify all exit nodes pass has been run, we know
  27   // that there can be at most one return instruction in the function left.
  28   // Get it.
  29   //
  30   Root = getAnalysis<UnifyFunctionExitNodes>().getExitNode();
  31
  32   if (Root == 0) {  // No exit node for the function?  Postdomsets are all empty
  33     for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
  34       Doms[FI] = DomSetType();
  35     return false;
  36   }
  37
  38   bool Changed;
  39   do {
  40     Changed = false;
  41
  42     std::set<const BasicBlock*> Visited;
  43     DomSetType WorkingSet;
  44     idf_iterator<BasicBlock*> It = idf_begin(Root), End = idf_end(Root);
  45     for ( ; It != End; ++It) {
  46       BasicBlock *BB = *It;
  47       succ_iterator PI = succ_begin(BB), PEnd = succ_end(BB);
  48       if (PI != PEnd) {                // Is there SOME predecessor?
  49         // Loop until we get to a successor that has had it's dom set filled
  50         // in at least once.  We are guaranteed to have this because we are
  51         // traversing the graph in DFO and have handled start nodes specially.
  52         //
  53         while (Doms[*PI].size() == 0) ++PI;
  54         WorkingSet = Doms[*PI];
  55
  56         for (++PI; PI != PEnd; ++PI) { // Intersect all of the successor sets
  57           DomSetType &PredSet = Doms[*PI];
  58           if (PredSet.size())
  59             set_intersect(WorkingSet, PredSet);
  60         }
  61       } else if (BB != Root) {
  62         // If this isn't the root basic block and it has no successors, it must
  63         // be an non-returning block.  Fib a bit by saying that the root node
  64         // postdominates this unreachable node.  This isn't exactly true,
  65         // because there is no path from this node to the root node, but it is
  66         // sorta true because any paths to the exit node would have to go
  67         // through this node.
  68         //
  69         // This allows for postdominator properties to be built for code that
  70         // doesn't return in a reasonable manner.
  71         //
  72         WorkingSet = Doms[Root];
  73       }
  74
  75       WorkingSet.insert(BB);           // A block always dominates itself
  76       DomSetType &BBSet = Doms[BB];
  77       if (BBSet != WorkingSet) {
  78         BBSet.swap(WorkingSet);        // Constant time operation!
  79         Changed = true;                // The sets changed.
  80       }
  81       WorkingSet.clear();              // Clear out the set for next iteration
  82     }
  83   } while (Changed);
  84   return false;
  85 }
  86
  87 // getAnalysisUsage - This obviously provides a post-dominator set, but it also
  88 // requires the UnifyFunctionExitNodes pass.
  89 //
  90 void PostDominatorSet::getAnalysisUsage(AnalysisUsage &AU) const {
  91   AU.setPreservesAll();
  92   AU.addRequired<UnifyFunctionExitNodes>();
  93 }
  94
  95 //===----------------------------------------------------------------------===//
  96 //  ImmediatePostDominators Implementation
  97 //===----------------------------------------------------------------------===//
  98
  99 static RegisterAnalysis<ImmediatePostDominators>
 100 D("postidom", "Immediate Post-Dominators Construction", true);
 101
 102 //===----------------------------------------------------------------------===//
 103 //  PostDominatorTree Implementation
 104 //===----------------------------------------------------------------------===//
 105
 106 static RegisterAnalysis<PostDominatorTree>
 107 F("postdomtree", "Post-Dominator Tree Construction", true);
 108
 109 void PostDominatorTree::calculate(const PostDominatorSet &DS) {
 110   Nodes[Root] = new Node(Root, 0);   // Add a node for the root...
 111
 112   if (Root) {
 113     // Iterate over all nodes in depth first order...
 114     for (idf_iterator<BasicBlock*> I = idf_begin(Root), E = idf_end(Root);
 115          I != E; ++I) {
 116       BasicBlock *BB = *I;
 117       const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
 118       unsigned DomSetSize = Dominators.size();
 119       if (DomSetSize == 1) continue;  // Root node... IDom = null
 120
 121       // Loop over all dominators of this node.  This corresponds to looping
 122       // over nodes in the dominator chain, looking for a node whose dominator
 123       // set is equal to the current nodes, except that the current node does
 124       // not exist in it.  This means that it is one level higher in the dom
 125       // chain than the current node, and it is our idom!  We know that we have
 126       // already added a DominatorTree node for our idom, because the idom must
 127       // be a predecessor in the depth first order that we are iterating through
 128       // the function.
 129       //
 130       DominatorSet::DomSetType::const_iterator I = Dominators.begin();
 131       DominatorSet::DomSetType::const_iterator End = Dominators.end();
 132       for (; I != End; ++I) {   // Iterate over dominators...
 133         // All of our dominators should form a chain, where the number
 134         // of elements in the dominator set indicates what level the
 135         // node is at in the chain.  We want the node immediately
 136         // above us, so it will have an identical dominator set,
 137         // except that BB will not dominate it... therefore it's
 138         // dominator set size will be one less than BB's...
 139         //
 140         if (DS.getDominators(*I).size() == DomSetSize - 1) {
 141           // We know that the immediate dominator should already have a node,
 142           // because we are traversing the CFG in depth first order!
 143           //
 144           Node *IDomNode = Nodes[*I];
 145           assert(IDomNode && "No node for IDOM?");
 146
 147           // Add a new tree node for this BasicBlock, and link it as a child of
 148           // IDomNode
 149           Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
 150           break;
 151         }
 152       }
 153     }
 154   }
 155 }
 156
 157 //===----------------------------------------------------------------------===//
 158 //  PostDominanceFrontier Implementation
 159 //===----------------------------------------------------------------------===//
 160
 161 static RegisterAnalysis<PostDominanceFrontier>
 162 H("postdomfrontier", "Post-Dominance Frontier Construction", true);
 163
 164 const DominanceFrontier::DomSetType &
 165 PostDominanceFrontier::calculate(const PostDominatorTree &DT,
 166                                  const DominatorTree::Node *Node) {
 167   // Loop over CFG successors to calculate DFlocal[Node]
 168   BasicBlock *BB = Node->getNode();
 169   DomSetType &S = Frontiers[BB];       // The new set to fill in...
 170   if (!Root) return S;
 171
 172   for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB);
 173        SI != SE; ++SI) {
 174     // Does Node immediately dominate this predeccessor?
 175     if (DT[*SI]->getIDom() != Node)
 176       S.insert(*SI);
 177   }
 178
 179   // At this point, S is DFlocal.  Now we union in DFup's of our children...
 180   // Loop through and visit the nodes that Node immediately dominates (Node's
 181   // children in the IDomTree)
 182   //
 183   for (PostDominatorTree::Node::const_iterator
 184          NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) {
 185     DominatorTree::Node *IDominee = *NI;
 186     const DomSetType &ChildDF = calculate(DT, IDominee);
 187
 188     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
 189     for (; CDFI != CDFE; ++CDFI) {
 190       if (!Node->dominates(DT[*CDFI]))
 191         S.insert(*CDFI);
 192     }
 193   }
 194
 195   return S;
 196 }
 197
 198 // stub - a dummy function to make linking work ok.
 199 void PostDominanceFrontier::stub() {
 200 }