1 //==- PostDominatorCalculation.h - Post-Dominator Calculation ----*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Owen Anderson and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // PostDominatorTree calculation implementation.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_ANALYSIS_POST_DOMINATOR_CALCULATION_H
14 #define LLVM_ANALYSIS_POST_DOMINATOR_CALCULATION_H
16 #include "llvm/Analysis/PostDominators.h"
20 void PDTCompress(PostDominatorTree& PDT, BasicBlock *V,
21 PostDominatorTree::InfoRec &VInfo) {
22 BasicBlock *VAncestor = VInfo.Ancestor;
23 PostDominatorTree::InfoRec &VAInfo = PDT.Info[VAncestor];
24 if (VAInfo.Ancestor == 0)
27 PDTCompress(PDT, VAncestor, VAInfo);
29 BasicBlock *VAncestorLabel = VAInfo.Label;
30 BasicBlock *VLabel = VInfo.Label;
31 if (PDT.Info[VAncestorLabel].Semi < PDT.Info[VLabel].Semi)
32 VInfo.Label = VAncestorLabel;
34 VInfo.Ancestor = VAInfo.Ancestor;
37 BasicBlock *PDTEval(PostDominatorTree& PDT, BasicBlock *V) {
38 PostDominatorTree::InfoRec &VInfo = PDT.Info[V];
40 // Higher-complexity but faster implementation
41 if (VInfo.Ancestor == 0)
43 PDTCompress(PDT, V, VInfo);
47 void PDTLink(PostDominatorTree& PDT, BasicBlock *V, BasicBlock *W,
48 PostDominatorTree::InfoRec &WInfo) {
49 // Higher-complexity but faster implementation
53 void PDTcalculate(PostDominatorTree& PDT, Function &F) {
54 // Step #0: Scan the function looking for the root nodes of the post-dominance
55 // relationships. These blocks, which have no successors, end with return and
56 // unwind instructions.
57 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
58 TerminatorInst *Insn = I->getTerminator();
59 if (Insn->getNumSuccessors() == 0) {
60 // Unreachable block is not a root node.
61 if (!isa<UnreachableInst>(Insn))
62 PDT.Roots.push_back(I);
65 // Prepopulate maps so that we don't get iterator invalidation issues later.
67 PDT.DomTreeNodes[I] = 0;
70 PDT.Vertex.push_back(0);
72 // Step #1: Number blocks in depth-first order and initialize variables used
73 // in later stages of the algorithm.
75 for (unsigned i = 0, e = PDT.Roots.size(); i != e; ++i)
76 N = PDT.DFSPass(PDT.Roots[i], N);
78 for (unsigned i = N; i >= 2; --i) {
79 BasicBlock *W = PDT.Vertex[i];
80 PostDominatorTree::InfoRec &WInfo = PDT.Info[W];
82 // Step #2: Calculate the semidominators of all vertices
83 for (succ_iterator SI = succ_begin(W), SE = succ_end(W); SI != SE; ++SI)
84 if (PDT.Info.count(*SI)) { // Only if this predecessor is reachable!
85 unsigned SemiU = PDT.Info[PDTEval(PDT, *SI)].Semi;
86 if (SemiU < WInfo.Semi)
90 PDT.Info[PDT.Vertex[WInfo.Semi]].Bucket.push_back(W);
92 BasicBlock *WParent = WInfo.Parent;
93 PDTLink(PDT, WParent, W, WInfo);
95 // Step #3: Implicitly define the immediate dominator of vertices
96 std::vector<BasicBlock*> &WParentBucket = PDT.Info[WParent].Bucket;
97 while (!WParentBucket.empty()) {
98 BasicBlock *V = WParentBucket.back();
99 WParentBucket.pop_back();
100 BasicBlock *U = PDTEval(PDT, V);
101 PDT.IDoms[V] = PDT.Info[U].Semi < PDT.Info[V].Semi ? U : WParent;
105 // Step #4: Explicitly define the immediate dominator of each vertex
106 for (unsigned i = 2; i <= N; ++i) {
107 BasicBlock *W = PDT.Vertex[i];
108 BasicBlock *&WIDom = PDT.IDoms[W];
109 if (WIDom != PDT.Vertex[PDT.Info[W].Semi])
110 WIDom = PDT.IDoms[WIDom];
113 if (PDT.Roots.empty()) return;
115 // Add a node for the root. This node might be the actual root, if there is
116 // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0)
117 // which postdominates all real exits if there are multiple exit blocks.
118 BasicBlock *Root = PDT.Roots.size() == 1 ? PDT.Roots[0] : 0;
119 PDT.DomTreeNodes[Root] = PDT.RootNode = new DomTreeNode(Root, 0);
121 // Loop over all of the reachable blocks in the function...
122 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
123 if (BasicBlock *ImmPostDom = PDT.getIDom(I)) { // Reachable block.
124 DomTreeNode *&BBNode = PDT.DomTreeNodes[I];
125 if (!BBNode) { // Haven't calculated this node yet?
126 // Get or calculate the node for the immediate dominator
127 DomTreeNode *IPDomNode = PDT.getNodeForBlock(ImmPostDom);
129 // Add a new tree node for this BasicBlock, and link it as a child of
131 DomTreeNode *C = new DomTreeNode(I, IPDomNode);
132 PDT.DomTreeNodes[I] = C;
133 BBNode = IPDomNode->addChild(C);
137 // Free temporary memory used to construct idom's
140 std::vector<BasicBlock*>().swap(PDT.Vertex);
142 // Start out with the DFS numbers being invalid. Let them be computed if
144 PDT.DFSInfoValid = false;