1 //=== llvm/Analysis/DominatorInternals.h - 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 #ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
11 #define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
13 #include "llvm/Analysis/Dominators.h"
14 #include "llvm/ADT/DenseMap.h"
15 #include "llvm/ADT/SmallPtrSet.h"
16 //===----------------------------------------------------------------------===//
18 // DominatorTree construction - This pass constructs immediate dominator
19 // information for a flow-graph based on the algorithm described in this
22 // A Fast Algorithm for Finding Dominators in a Flowgraph
23 // T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
25 // This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and
26 // LINK, but it turns out that the theoretically slower O(n*log(n))
27 // implementation is actually faster than the "efficient" algorithm (even for
28 // large CFGs) because the constant overheads are substantially smaller. The
29 // lower-complexity version can be enabled with the following #define:
31 #define BALANCE_IDOM_TREE 0
33 //===----------------------------------------------------------------------===//
37 template<class GraphT>
38 unsigned DFSPass(DominatorTreeBase& DT, typename GraphT::NodeType* V,
40 // This is more understandable as a recursive algorithm, but we can't use the
41 // recursive algorithm due to stack depth issues. Keep it here for
42 // documentation purposes.
44 InfoRec &VInfo = DT.Info[DT.Roots[i]];
48 Vertex.push_back(V); // Vertex[n] = V;
49 //Info[V].Ancestor = 0; // Ancestor[n] = 0
50 //Info[V].Child = 0; // Child[v] = 0
51 VInfo.Size = 1; // Size[v] = 1
53 for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
54 InfoRec &SuccVInfo = DT.Info[*SI];
55 if (SuccVInfo.Semi == 0) {
57 N = DTDFSPass(DT, *SI, N);
61 std::vector<std::pair<typename GraphT::NodeType*,
62 typename GraphT::ChildIteratorType> > Worklist;
63 Worklist.push_back(std::make_pair(V, GraphT::child_begin(V)));
64 while (!Worklist.empty()) {
65 typename GraphT::NodeType* BB = Worklist.back().first;
66 typename GraphT::ChildIteratorType NextSucc = Worklist.back().second;
68 // First time we visited this BB?
69 if (NextSucc == GraphT::child_begin(BB)) {
70 DominatorTree::InfoRec &BBInfo = DT.Info[BB];
74 DT.Vertex.push_back(BB); // Vertex[n] = V;
75 //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0
76 //BBInfo[V].Child = 0; // Child[v] = 0
77 BBInfo.Size = 1; // Size[v] = 1
80 // If we are done with this block, remove it from the worklist.
81 if (NextSucc == GraphT::child_end(BB)) {
86 // Increment the successor number for the next time we get to it.
87 ++Worklist.back().second;
89 // Visit the successor next, if it isn't already visited.
90 typename GraphT::NodeType* Succ = *NextSucc;
92 DominatorTree::InfoRec &SuccVInfo = DT.Info[Succ];
93 if (SuccVInfo.Semi == 0) {
94 SuccVInfo.Parent = BB;
95 Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ)));
102 template<class GraphT>
103 void Compress(DominatorTreeBase& DT, typename GraphT::NodeType *VIn) {
104 std::vector<typename GraphT::NodeType*> Work;
105 SmallPtrSet<typename GraphT::NodeType*, 32> Visited;
106 typename GraphT::NodeType* VInAncestor = DT.Info[VIn].Ancestor;
107 DominatorTreeBase::InfoRec &VInVAInfo = DT.Info[VInAncestor];
109 if (VInVAInfo.Ancestor != 0)
112 while (!Work.empty()) {
113 typename GraphT::NodeType* V = Work.back();
114 DominatorTree::InfoRec &VInfo = DT.Info[V];
115 typename GraphT::NodeType* VAncestor = VInfo.Ancestor;
116 DominatorTreeBase::InfoRec &VAInfo = DT.Info[VAncestor];
118 // Process Ancestor first
119 if (Visited.insert(VAncestor) &&
120 VAInfo.Ancestor != 0) {
121 Work.push_back(VAncestor);
126 // Update VInfo based on Ancestor info
127 if (VAInfo.Ancestor == 0)
129 typename GraphT::NodeType* VAncestorLabel = VAInfo.Label;
130 typename GraphT::NodeType* VLabel = VInfo.Label;
131 if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi)
132 VInfo.Label = VAncestorLabel;
133 VInfo.Ancestor = VAInfo.Ancestor;
137 template<class GraphT>
138 typename GraphT::NodeType* Eval(DominatorTreeBase& DT,
139 typename GraphT::NodeType *V) {
140 DominatorTreeBase::InfoRec &VInfo = DT.Info[V];
141 #if !BALANCE_IDOM_TREE
142 // Higher-complexity but faster implementation
143 if (VInfo.Ancestor == 0)
145 Compress<GraphT>(DT, V);
148 // Lower-complexity but slower implementation
149 if (VInfo.Ancestor == 0)
151 Compress<GraphT>(DT, V);
152 GraphT::NodeType* VLabel = VInfo.Label;
154 GraphT::NodeType* VAncestorLabel = DT.Info[VInfo.Ancestor].Label;
155 if (DT.Info[VAncestorLabel].Semi >= DT.Info[VLabel].Semi)
158 return VAncestorLabel;
162 template<class GraphT>
163 void Link(DominatorTreeBase& DT, typename GraphT::NodeType* V,
164 typename GraphT::NodeType* W, DominatorTreeBase::InfoRec &WInfo) {
165 #if !BALANCE_IDOM_TREE
166 // Higher-complexity but faster implementation
169 // Lower-complexity but slower implementation
170 GraphT::NodeType* WLabel = WInfo.Label;
171 unsigned WLabelSemi = DT.Info[WLabel].Semi;
172 GraphT::NodeType* S = W;
173 InfoRec *SInfo = &DT.Info[S];
175 GraphT::NodeType* SChild = SInfo->Child;
176 InfoRec *SChildInfo = &DT.Info[SChild];
178 while (WLabelSemi < DT.Info[SChildInfo->Label].Semi) {
179 GraphT::NodeType* SChildChild = SChildInfo->Child;
180 if (SInfo->Size+DT.Info[SChildChild].Size >= 2*SChildInfo->Size) {
181 SChildInfo->Ancestor = S;
182 SInfo->Child = SChild = SChildChild;
183 SChildInfo = &DT.Info[SChild];
185 SChildInfo->Size = SInfo->Size;
186 S = SInfo->Ancestor = SChild;
188 SChild = SChildChild;
189 SChildInfo = &DT.Info[SChild];
193 DominatorTreeBase::InfoRec &VInfo = DT.Info[V];
194 SInfo->Label = WLabel;
196 assert(V != W && "The optimization here will not work in this case!");
197 unsigned WSize = WInfo.Size;
198 unsigned VSize = (VInfo.Size += WSize);
201 std::swap(S, VInfo.Child);