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 "llvm/Assembly/Writer.h"
12 #include "Support/DepthFirstIterator.h"
13 #include "Support/STLExtras.h"
14 #include "Support/SetOperations.h"
18 //===----------------------------------------------------------------------===//
19 // DominatorSet Implementation
20 //===----------------------------------------------------------------------===//
22 static RegisterAnalysis<DominatorSet>
23 A("domset", "Dominator Set Construction");
24 static RegisterAnalysis<PostDominatorSet>
25 B("postdomset", "Post-Dominator Set Construction");
27 AnalysisID DominatorSet::ID = A;
28 AnalysisID PostDominatorSet::ID = B;
30 // dominates - Return true if A dominates B. This performs the special checks
31 // neccesary if A and B are in the same basic block.
33 bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const {
34 BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
35 if (BBA != BBB) return dominates(BBA, BBB);
37 // Loop through the basic block until we find A or B.
38 BasicBlock::iterator I = BBA->begin();
39 for (; &*I != A && &*I != B; ++I) /*empty*/;
41 // A dominates B if it is found first in the basic block...
45 // runOnFunction - This method calculates the forward dominator sets for the
46 // specified function.
48 bool DominatorSet::runOnFunction(Function &F) {
49 Doms.clear(); // Reset from the last time we were run...
50 Root = &F.getEntryNode();
51 assert(pred_begin(Root) == pred_end(Root) &&
52 "Root node has predecessors in function!");
58 DomSetType WorkingSet;
59 df_iterator<Function*> It = df_begin(&F), End = df_end(&F);
60 for ( ; It != End; ++It) {
62 pred_iterator PI = pred_begin(BB), PEnd = pred_end(BB);
63 if (PI != PEnd) { // Is there SOME predecessor?
64 // Loop until we get to a predecessor that has had it's dom set filled
65 // in at least once. We are guaranteed to have this because we are
66 // traversing the graph in DFO and have handled start nodes specially.
68 while (Doms[*PI].size() == 0) ++PI;
69 WorkingSet = Doms[*PI];
71 for (++PI; PI != PEnd; ++PI) { // Intersect all of the predecessor sets
72 DomSetType &PredSet = Doms[*PI];
74 set_intersect(WorkingSet, PredSet);
78 WorkingSet.insert(BB); // A block always dominates itself
79 DomSetType &BBSet = Doms[BB];
80 if (BBSet != WorkingSet) {
81 BBSet.swap(WorkingSet); // Constant time operation!
82 Changed = true; // The sets changed.
84 WorkingSet.clear(); // Clear out the set for next iteration
91 // Postdominator set construction. This converts the specified function to only
92 // have a single exit node (return stmt), then calculates the post dominance
93 // sets for the function.
95 bool PostDominatorSet::runOnFunction(Function &F) {
96 Doms.clear(); // Reset from the last time we were run...
97 // Since we require that the unify all exit nodes pass has been run, we know
98 // that there can be at most one return instruction in the function left.
101 Root = getAnalysis<UnifyFunctionExitNodes>().getExitNode();
103 if (Root == 0) { // No exit node for the function? Postdomsets are all empty
104 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
105 Doms[FI] = DomSetType();
113 set<const BasicBlock*> Visited;
114 DomSetType WorkingSet;
115 idf_iterator<BasicBlock*> It = idf_begin(Root), End = idf_end(Root);
116 for ( ; It != End; ++It) {
117 BasicBlock *BB = *It;
118 succ_iterator PI = succ_begin(BB), PEnd = succ_end(BB);
119 if (PI != PEnd) { // Is there SOME predecessor?
120 // Loop until we get to a successor that has had it's dom set filled
121 // in at least once. We are guaranteed to have this because we are
122 // traversing the graph in DFO and have handled start nodes specially.
124 while (Doms[*PI].size() == 0) ++PI;
125 WorkingSet = Doms[*PI];
127 for (++PI; PI != PEnd; ++PI) { // Intersect all of the successor sets
128 DomSetType &PredSet = Doms[*PI];
130 set_intersect(WorkingSet, PredSet);
134 WorkingSet.insert(BB); // A block always dominates itself
135 DomSetType &BBSet = Doms[BB];
136 if (BBSet != WorkingSet) {
137 BBSet.swap(WorkingSet); // Constant time operation!
138 Changed = true; // The sets changed.
140 WorkingSet.clear(); // Clear out the set for next iteration
146 // getAnalysisUsage - This obviously provides a post-dominator set, but it also
147 // requires the UnifyFunctionExitNodes pass.
149 void PostDominatorSet::getAnalysisUsage(AnalysisUsage &AU) const {
150 AU.setPreservesAll();
151 AU.addRequired(UnifyFunctionExitNodes::ID);
154 static ostream &operator<<(ostream &o, const set<BasicBlock*> &BBs) {
155 for (set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
158 WriteAsOperand(o, *I, false);
164 void DominatorSetBase::print(std::ostream &o) const {
165 for (const_iterator I = begin(), E = end(); I != E; ++I)
166 o << "=============================--------------------------------\n"
167 << "\nDominator Set For Basic Block\n" << I->first
168 << "-------------------------------\n" << I->second << "\n";
171 //===----------------------------------------------------------------------===//
172 // ImmediateDominators Implementation
173 //===----------------------------------------------------------------------===//
175 static RegisterAnalysis<ImmediateDominators>
176 C("idom", "Immediate Dominators Construction");
177 static RegisterAnalysis<ImmediatePostDominators>
178 D("postidom", "Immediate Post-Dominators Construction");
180 AnalysisID ImmediateDominators::ID = C;
181 AnalysisID ImmediatePostDominators::ID = D;
183 // calcIDoms - Calculate the immediate dominator mapping, given a set of
184 // dominators for every basic block.
185 void ImmediateDominatorsBase::calcIDoms(const DominatorSetBase &DS) {
186 // Loop over all of the nodes that have dominators... figuring out the IDOM
189 for (DominatorSet::const_iterator DI = DS.begin(), DEnd = DS.end();
191 BasicBlock *BB = DI->first;
192 const DominatorSet::DomSetType &Dominators = DI->second;
193 unsigned DomSetSize = Dominators.size();
194 if (DomSetSize == 1) continue; // Root node... IDom = null
196 // Loop over all dominators of this node. This corresponds to looping over
197 // nodes in the dominator chain, looking for a node whose dominator set is
198 // equal to the current nodes, except that the current node does not exist
199 // in it. This means that it is one level higher in the dom chain than the
200 // current node, and it is our idom!
202 DominatorSet::DomSetType::const_iterator I = Dominators.begin();
203 DominatorSet::DomSetType::const_iterator End = Dominators.end();
204 for (; I != End; ++I) { // Iterate over dominators...
205 // All of our dominators should form a chain, where the number of elements
206 // in the dominator set indicates what level the node is at in the chain.
207 // We want the node immediately above us, so it will have an identical
208 // dominator set, except that BB will not dominate it... therefore it's
209 // dominator set size will be one less than BB's...
211 if (DS.getDominators(*I).size() == DomSetSize - 1) {
219 void ImmediateDominatorsBase::print(ostream &o) const {
220 for (const_iterator I = begin(), E = end(); I != E; ++I)
221 o << "=============================--------------------------------\n"
222 << "\nImmediate Dominator For Basic Block\n" << *I->first
223 << "is: \n" << *I->second << "\n";
227 //===----------------------------------------------------------------------===//
228 // DominatorTree Implementation
229 //===----------------------------------------------------------------------===//
231 static RegisterAnalysis<DominatorTree>
232 E("domtree", "Dominator Tree Construction");
233 static RegisterAnalysis<PostDominatorTree>
234 F("postdomtree", "Post-Dominator Tree Construction");
236 AnalysisID DominatorTree::ID = E;
237 AnalysisID PostDominatorTree::ID = F;
239 // DominatorTreeBase::reset - Free all of the tree node memory.
241 void DominatorTreeBase::reset() {
242 for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
248 void DominatorTree::calculate(const DominatorSet &DS) {
249 Nodes[Root] = new Node(Root, 0); // Add a node for the root...
251 // Iterate over all nodes in depth first order...
252 for (df_iterator<BasicBlock*> I = df_begin(Root), E = df_end(Root);
255 const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
256 unsigned DomSetSize = Dominators.size();
257 if (DomSetSize == 1) continue; // Root node... IDom = null
259 // Loop over all dominators of this node. This corresponds to looping over
260 // nodes in the dominator chain, looking for a node whose dominator set is
261 // equal to the current nodes, except that the current node does not exist
262 // in it. This means that it is one level higher in the dom chain than the
263 // current node, and it is our idom! We know that we have already added
264 // a DominatorTree node for our idom, because the idom must be a
265 // predecessor in the depth first order that we are iterating through the
268 DominatorSet::DomSetType::const_iterator I = Dominators.begin();
269 DominatorSet::DomSetType::const_iterator End = Dominators.end();
270 for (; I != End; ++I) { // Iterate over dominators...
271 // All of our dominators should form a chain, where the number of
272 // elements in the dominator set indicates what level the node is at in
273 // the chain. We want the node immediately above us, so it will have
274 // an identical dominator set, except that BB will not dominate it...
275 // therefore it's dominator set size will be one less than BB's...
277 if (DS.getDominators(*I).size() == DomSetSize - 1) {
278 // We know that the immediate dominator should already have a node,
279 // because we are traversing the CFG in depth first order!
281 Node *IDomNode = Nodes[*I];
282 assert(IDomNode && "No node for IDOM?");
284 // Add a new tree node for this BasicBlock, and link it as a child of
286 Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
294 void PostDominatorTree::calculate(const PostDominatorSet &DS) {
295 Nodes[Root] = new Node(Root, 0); // Add a node for the root...
298 // Iterate over all nodes in depth first order...
299 for (idf_iterator<BasicBlock*> I = idf_begin(Root), E = idf_end(Root);
302 const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
303 unsigned DomSetSize = Dominators.size();
304 if (DomSetSize == 1) continue; // Root node... IDom = null
306 // Loop over all dominators of this node. This corresponds to looping
307 // over nodes in the dominator chain, looking for a node whose dominator
308 // set is equal to the current nodes, except that the current node does
309 // not exist in it. This means that it is one level higher in the dom
310 // chain than the current node, and it is our idom! We know that we have
311 // already added a DominatorTree node for our idom, because the idom must
312 // be a predecessor in the depth first order that we are iterating through
315 DominatorSet::DomSetType::const_iterator I = Dominators.begin();
316 DominatorSet::DomSetType::const_iterator End = Dominators.end();
317 for (; I != End; ++I) { // Iterate over dominators...
318 // All of our dominators should form a chain, where the number
319 // of elements in the dominator set indicates what level the
320 // node is at in the chain. We want the node immediately
321 // above us, so it will have an identical dominator set,
322 // except that BB will not dominate it... therefore it's
323 // dominator set size will be one less than BB's...
325 if (DS.getDominators(*I).size() == DomSetSize - 1) {
326 // We know that the immediate dominator should already have a node,
327 // because we are traversing the CFG in depth first order!
329 Node *IDomNode = Nodes[*I];
330 assert(IDomNode && "No node for IDOM?");
332 // Add a new tree node for this BasicBlock, and link it as a child of
334 Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
342 static ostream &operator<<(ostream &o, const DominatorTreeBase::Node *Node) {
343 return o << Node->getNode()
344 << "\n------------------------------------------\n";
347 static void PrintDomTree(const DominatorTreeBase::Node *N, ostream &o,
349 o << "Level #" << Lev << ": " << N;
350 for (DominatorTreeBase::Node::const_iterator I = N->begin(), E = N->end();
352 PrintDomTree(*I, o, Lev+1);
356 void DominatorTreeBase::print(std::ostream &o) const {
357 o << "=============================--------------------------------\n"
358 << "Inorder Dominator Tree:\n";
359 PrintDomTree(Nodes.find(getRoot())->second, o, 1);
363 //===----------------------------------------------------------------------===//
364 // DominanceFrontier Implementation
365 //===----------------------------------------------------------------------===//
367 static RegisterAnalysis<DominanceFrontier>
368 G("domfrontier", "Dominance Frontier Construction");
369 static RegisterAnalysis<PostDominanceFrontier>
370 H("postdomfrontier", "Post-Dominance Frontier Construction");
372 AnalysisID DominanceFrontier::ID = G;
373 AnalysisID PostDominanceFrontier::ID = H;
375 const DominanceFrontier::DomSetType &
376 DominanceFrontier::calculate(const DominatorTree &DT,
377 const DominatorTree::Node *Node) {
378 // Loop over CFG successors to calculate DFlocal[Node]
379 BasicBlock *BB = Node->getNode();
380 DomSetType &S = Frontiers[BB]; // The new set to fill in...
382 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
384 // Does Node immediately dominate this successor?
385 if (DT[*SI]->getIDom() != Node)
389 // At this point, S is DFlocal. Now we union in DFup's of our children...
390 // Loop through and visit the nodes that Node immediately dominates (Node's
391 // children in the IDomTree)
393 for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
395 DominatorTree::Node *IDominee = *NI;
396 const DomSetType &ChildDF = calculate(DT, IDominee);
398 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
399 for (; CDFI != CDFE; ++CDFI) {
400 if (!Node->dominates(DT[*CDFI]))
408 const DominanceFrontier::DomSetType &
409 PostDominanceFrontier::calculate(const PostDominatorTree &DT,
410 const DominatorTree::Node *Node) {
411 // Loop over CFG successors to calculate DFlocal[Node]
412 BasicBlock *BB = Node->getNode();
413 DomSetType &S = Frontiers[BB]; // The new set to fill in...
416 for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB);
418 // Does Node immediately dominate this predeccessor?
419 if (DT[*SI]->getIDom() != Node)
423 // At this point, S is DFlocal. Now we union in DFup's of our children...
424 // Loop through and visit the nodes that Node immediately dominates (Node's
425 // children in the IDomTree)
427 for (PostDominatorTree::Node::const_iterator
428 NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) {
429 DominatorTree::Node *IDominee = *NI;
430 const DomSetType &ChildDF = calculate(DT, IDominee);
432 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
433 for (; CDFI != CDFE; ++CDFI) {
434 if (!Node->dominates(DT[*CDFI]))
442 void DominanceFrontierBase::print(std::ostream &o) const {
443 for (const_iterator I = begin(), E = end(); I != E; ++I) {
444 o << "=============================--------------------------------\n"
445 << "\nDominance Frontier For Basic Block\n";
446 WriteAsOperand(o, I->first, false);
447 o << " is: \n" << I->second << "\n";