1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
|
//===- llvm/Analysis/DominatorSet.h - Dominator Set Calculation --*- C++ -*--=//
//
// This file defines the following classes:
// 1. DominatorSet: Calculates the [reverse] dominator set for a method
// 2. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
// and their immediate dominator.
// 3. DominatorTree: Represent the ImmediateDominator as an explicit tree
// structure.
// 4. DominanceFrontier: Calculate and hold the dominance frontier for a
// method.
//
// These data structures are listed in increasing order of complexity. It
// takes longer to calculate the dominator frontier, for example, than the
// ImmediateDominator mapping.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_DOMINATORS_H
#define LLVM_DOMINATORS_H
#include <set>
#include <map>
#include <vector>
class Method;
class BasicBlock;
namespace cfg {
//===----------------------------------------------------------------------===//
//
// DominatorBase - Base class that other, more interesting dominator analyses
// inherit from.
//
class DominatorBase {
protected:
const BasicBlock *Root;
inline DominatorBase(const BasicBlock *root = 0) : Root(root) {}
public:
inline const BasicBlock *getRoot() const { return Root; }
bool isPostDominator() const; // Returns true if analysis based of postdoms
};
//===----------------------------------------------------------------------===//
//
// DominatorSet - Maintain a set<const BasicBlock*> for every basic block in a
// method, that represents the blocks that dominate the block.
//
class DominatorSet : public DominatorBase {
public:
typedef std::set<const BasicBlock*> DomSetType; // Dom set for a bb
// Map of dom sets
typedef std::map<const BasicBlock*, DomSetType> DomSetMapType;
private:
DomSetMapType Doms;
void calcForwardDominatorSet(const Method *M);
public:
// DominatorSet ctor - Build either the dominator set or the post-dominator
// set for a method... Building the postdominator set may require the analysis
// routine to modify the method so that there is only a single return in the
// method.
//
DominatorSet(const Method *M);
DominatorSet( Method *M, bool PostDomSet);
// Accessor interface:
typedef DomSetMapType::const_iterator const_iterator;
inline const_iterator begin() const { return Doms.begin(); }
inline const_iterator end() const { return Doms.end(); }
inline const_iterator find(const BasicBlock* B) const { return Doms.find(B); }
// getDominators - Return the set of basic blocks that dominate the specified
// block.
//
inline const DomSetType &getDominators(const BasicBlock *BB) const {
const_iterator I = find(BB);
assert(I != end() && "BB not in method!");
return I->second;
}
// dominates - Return true if A dominates B.
//
inline bool dominates(const BasicBlock *A, const BasicBlock *B) const {
return getDominators(B).count(A) != 0;
}
};
//===----------------------------------------------------------------------===//
//
// ImmediateDominators - Calculate the immediate dominator for each node in a
// method.
//
class ImmediateDominators : public DominatorBase {
std::map<const BasicBlock*, const BasicBlock*> IDoms;
void calcIDoms(const DominatorSet &DS);
public:
// ImmediateDominators ctor - Calculate the idom mapping, for a method, or
// from a dominator set calculated for something else...
//
inline ImmediateDominators(const DominatorSet &DS)
: DominatorBase(DS.getRoot()) {
calcIDoms(DS); // Can be used to make rev-idoms
}
// Accessor interface:
typedef std::map<const BasicBlock*, const BasicBlock*> IDomMapType;
typedef IDomMapType::const_iterator const_iterator;
inline const_iterator begin() const { return IDoms.begin(); }
inline const_iterator end() const { return IDoms.end(); }
inline const_iterator find(const BasicBlock* B) const { return IDoms.find(B);}
// operator[] - Return the idom for the specified basic block. The start
// node returns null, because it does not have an immediate dominator.
//
inline const BasicBlock *operator[](const BasicBlock *BB) const {
std::map<const BasicBlock*, const BasicBlock*>::const_iterator I =
IDoms.find(BB);
return I != IDoms.end() ? I->second : 0;
}
};
//===----------------------------------------------------------------------===//
//
// DominatorTree - Calculate the immediate dominator tree for a method.
//
class DominatorTree : public DominatorBase {
class Node2;
public:
typedef Node2 Node;
private:
std::map<const BasicBlock*, Node*> Nodes;
void calculate(const DominatorSet &DS);
typedef std::map<const BasicBlock*, Node*> NodeMapType;
public:
class Node2 : public std::vector<Node*> {
friend class DominatorTree;
const BasicBlock *TheNode;
Node2 * const IDom;
public:
inline const BasicBlock *getNode() const { return TheNode; }
inline Node2 *getIDom() const { return IDom; }
inline const std::vector<Node*> &getChildren() const { return *this; }
// dominates - Returns true iff this dominates N. Note that this is not a
// constant time operation!
inline bool dominates(const Node2 *N) const {
const Node2 *IDom;
while ((IDom = N->getIDom()) != 0 && IDom != this)
N = IDom; // Walk up the tree
return IDom != 0;
}
private:
inline Node2(const BasicBlock *node, Node *iDom)
: TheNode(node), IDom(iDom) {}
inline Node2 *addChild(Node *C) { push_back(C); return C; }
};
public:
// DominatorTree ctors - Compute a dominator tree, given various amounts of
// previous knowledge...
inline DominatorTree(const DominatorSet &DS) : DominatorBase(DS.getRoot()) {
calculate(DS);
}
DominatorTree(const ImmediateDominators &IDoms);
~DominatorTree();
inline const Node *operator[](const BasicBlock *BB) const {
NodeMapType::const_iterator i = Nodes.find(BB);
return (i != Nodes.end()) ? i->second : 0;
}
};
//===----------------------------------------------------------------------===//
//
// DominanceFrontier - Calculate the dominance frontiers for a method.
//
class DominanceFrontier : public DominatorBase {
public:
typedef std::set<const BasicBlock*> DomSetType; // Dom set for a bb
typedef std::map<const BasicBlock*, DomSetType> DomSetMapType; // Dom set map
private:
DomSetMapType Frontiers;
const DomSetType &calcDomFrontier(const DominatorTree &DT,
const DominatorTree::Node *Node);
const DomSetType &calcPostDomFrontier(const DominatorTree &DT,
const DominatorTree::Node *Node);
public:
DominanceFrontier(const DominatorSet &DS) : DominatorBase(DS.getRoot()) {
const DominatorTree DT(DS);
if (isPostDominator())
calcPostDomFrontier(DT, DT[Root]);
else
calcDomFrontier(DT, DT[Root]);
}
DominanceFrontier(const ImmediateDominators &ID)
: DominatorBase(ID.getRoot()) {
const DominatorTree DT(ID);
if (isPostDominator())
calcPostDomFrontier(DT, DT[Root]);
else
calcDomFrontier(DT, DT[Root]);
}
DominanceFrontier(const DominatorTree &DT) : DominatorBase(DT.getRoot()) {
if (isPostDominator())
calcPostDomFrontier(DT, DT[Root]);
else
calcDomFrontier(DT, DT[Root]);
}
// Accessor interface:
typedef DomSetMapType::const_iterator const_iterator;
inline const_iterator begin() const { return Frontiers.begin(); }
inline const_iterator end() const { return Frontiers.end(); }
inline const_iterator find(const BasicBlock* B) const { return Frontiers.find(B);}
};
} // End namespace cfg
#endif
|
