1 //===- DominatorSet.cpp - Dominator Set Calculation --------------*- C++ -*--=//
3 // This file provides a simple class to calculate the dominator set of a
6 //===----------------------------------------------------------------------===//
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"
17 //===----------------------------------------------------------------------===//
18 // DominatorSet Implementation
19 //===----------------------------------------------------------------------===//
21 AnalysisID DominatorSet::ID(AnalysisID::create<DominatorSet>(), true);
22 AnalysisID PostDominatorSet::ID(AnalysisID::create<PostDominatorSet>(), true);
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.
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);
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*/;
35 // A dominates B if it is found first in the basic block...
39 // runOnFunction - This method calculates the forward dominator sets for the
40 // specified function.
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!");
52 DomSetType WorkingSet;
53 df_iterator<Function*> It = df_begin(&F), End = df_end(&F);
54 for ( ; It != End; ++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.
62 while (Doms[*PI].size() == 0) ++PI;
63 WorkingSet = Doms[*PI];
65 for (++PI; PI != PEnd; ++PI) { // Intersect all of the predecessor sets
66 DomSetType &PredSet = Doms[*PI];
68 set_intersect(WorkingSet, PredSet);
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.
78 WorkingSet.clear(); // Clear out the set for next iteration
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.
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.
95 Root = getAnalysis<UnifyFunctionExitNodes>().getExitNode();
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();
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.
118 while (Doms[*PI].size() == 0) ++PI;
119 WorkingSet = Doms[*PI];
121 for (++PI; PI != PEnd; ++PI) { // Intersect all of the successor sets
122 DomSetType &PredSet = Doms[*PI];
124 set_intersect(WorkingSet, PredSet);
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.
134 WorkingSet.clear(); // Clear out the set for next iteration
140 // getAnalysisUsage - This obviously provides a post-dominator set, but it also
141 // requires the UnifyFunctionExitNodes pass.
143 void PostDominatorSet::getAnalysisUsage(AnalysisUsage &AU) const {
144 AU.setPreservesAll();
146 AU.addRequired(UnifyFunctionExitNodes::ID);
150 //===----------------------------------------------------------------------===//
151 // ImmediateDominators Implementation
152 //===----------------------------------------------------------------------===//
154 AnalysisID ImmediateDominators::ID(AnalysisID::create<ImmediateDominators>(), true);
155 AnalysisID ImmediatePostDominators::ID(AnalysisID::create<ImmediatePostDominators>(), true);
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
163 for (DominatorSet::const_iterator DI = DS.begin(), DEnd = DS.end();
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
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!
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...
185 if (DS.getDominators(*I).size() == DomSetSize - 1) {
194 //===----------------------------------------------------------------------===//
195 // DominatorTree Implementation
196 //===----------------------------------------------------------------------===//
198 AnalysisID DominatorTree::ID(AnalysisID::create<DominatorTree>(), true);
199 AnalysisID PostDominatorTree::ID(AnalysisID::create<PostDominatorTree>(), true);
201 // DominatorTreeBase::reset - Free all of the tree node memory.
203 void DominatorTreeBase::reset() {
204 for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
210 void DominatorTree::calculate(const DominatorSet &DS) {
211 Nodes[Root] = new Node(Root, 0); // Add a node for the root...
213 // Iterate over all nodes in depth first order...
214 for (df_iterator<BasicBlock*> I = df_begin(Root), E = df_end(Root);
217 const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
218 unsigned DomSetSize = Dominators.size();
219 if (DomSetSize == 1) continue; // Root node... IDom = null
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
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...
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!
243 Node *IDomNode = Nodes[*I];
244 assert(IDomNode && "No node for IDOM?");
246 // Add a new tree node for this BasicBlock, and link it as a child of
248 Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
256 void PostDominatorTree::calculate(const PostDominatorSet &DS) {
257 Nodes[Root] = new Node(Root, 0); // Add a node for the root...
260 // Iterate over all nodes in depth first order...
261 for (idf_iterator<BasicBlock*> I = idf_begin(Root), E = idf_end(Root);
264 const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
265 unsigned DomSetSize = Dominators.size();
266 if (DomSetSize == 1) continue; // Root node... IDom = null
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
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...
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!
291 Node *IDomNode = Nodes[*I];
292 assert(IDomNode && "No node for IDOM?");
294 // Add a new tree node for this BasicBlock, and link it as a child of
296 Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
306 //===----------------------------------------------------------------------===//
307 // DominanceFrontier Implementation
308 //===----------------------------------------------------------------------===//
310 AnalysisID DominanceFrontier::ID(AnalysisID::create<DominanceFrontier>(), true);
311 AnalysisID PostDominanceFrontier::ID(AnalysisID::create<PostDominanceFrontier>(), true);
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...
320 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
322 // Does Node immediately dominate this successor?
323 if (DT[*SI]->getIDom() != Node)
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)
331 for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
333 DominatorTree::Node *IDominee = *NI;
334 const DomSetType &ChildDF = calculate(DT, IDominee);
336 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
337 for (; CDFI != CDFE; ++CDFI) {
338 if (!Node->dominates(DT[*CDFI]))
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...
354 for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB);
356 // Does Node immediately dominate this predeccessor?
357 if (DT[*SI]->getIDom() != Node)
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)
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);
370 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
371 for (; CDFI != CDFE; ++CDFI) {
372 if (!Node->dominates(DT[*CDFI]))