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