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
|
// slang-ir-dominators.h
#pragma once
#include "../core/slang-basic.h"
namespace Slang
{
struct IRBlock;
struct IRGlobalValueWithCode;
struct IRInst;
/// The computed dominator tree for an IR control flow graph.
struct IRDominatorTree : public RefObject
{
/// The function or other code-bearing value for which the dominator tree was computed.
IRGlobalValueWithCode* code;
/// Does the first block dominate the second?
///
/// A block A dominates block B iff every control-flow path
/// that starts at the entry block of the CFG and passes
/// through B must first pass through A.
///
bool dominates(IRBlock* dominator, IRBlock* dominated);
bool dominates(IRInst* dominator, IRInst* dominated);
/// Does the first block properly dominate the second?
///
/// Block A properly dominates block B iff A dominates B
/// and A != B.
///
bool properlyDominates(IRBlock* dominator, IRBlock* dominated);
/// Does the first block immediately dominate the second?
///
/// Block A immediately dominates block B iff A dominates B
/// and for any block X that dominates B, X also dominates A.
///
bool immediatelyDominates(IRBlock* dominator, IRBlock* dominated);
/// Get the immediate dominator (idom) of a block.
///
/// This is the parent of `block` in the dominator tree.
IRBlock* getImmediateDominator(IRBlock* block);
/// An iterable collection of the blocks dominated by a specific block
struct DominatedList;
/// Get the blocks that a block immediately dominates.
///
/// These are the children of the block in the dominator tree.
DominatedList getImmediatelyDominatedBlocks(IRBlock* block);
/// Get the blocks that a block properly dominates.
///
/// These are the descendents of the block in the dominator tree.
DominatedList getProperlyDominatedBlocks(IRBlock* block);
/// Is `block` unrechable in the control flow graph?
bool isUnreachable(IRBlock* block);
struct DominatedList
{
public:
DominatedList();
struct Iterator
{
public:
Iterator();
IRBlock* operator*() const;
void operator++();
bool operator==(Iterator const& that) const;
bool operator!=(Iterator const& that) const;
private:
friend struct DominatedList;
Iterator(IRDominatorTree* tree, Int index);
IRDominatorTree* mTree;
Int mIndex;
};
Iterator begin() const;
Iterator end() const;
Count getCount() const { return Count(mEnd - mBegin); }
private:
friend struct IRDominatorTree;
DominatedList(IRDominatorTree* tree, Int begin, Int end);
IRDominatorTree* mTree;
Int mBegin;
Int mEnd;
};
private:
//
// The layout of an `IRDominatorTree` uses a dense array for all of the nodes in the CFG.
// We therefore need a way to map an `IRBlock*` pointer over to an index in this array:
//
/// Map a block to its index in the `nodes` array
Int getBlockIndex(IRBlock* block);
/// Dictionary used to accelerate `getBlockIndex`
Dictionary<IRBlock*, Int> mapBlockToIndex;
/// Reachability information for the CFG
HashSet<IRBlock*> reachableSet;
//
// In order to accelerate queries on the tree structure, we will order the tree nodes
// carefully, so that all of the descendants of a node are contiguous, with all of
// the immediate children coming first.
//
// Each node thus needs to remember its parent (immediate dominator), and the range
// of indices that represent children and descendents (respectively), with the knowledge
// that the first child and first descendent share the same index.
//
/// Information about one node in the dominator tree
struct Node
{
/// The block associated with this tree node
IRBlock* block;
/// Index of the parent node or -1 if no parent
Int parent;
/// Index of first descendent
Int beginDescendents;
/// "One after the end" value for range of child node indices.
Int endChildren;
/// "One after the end" value for range of descendent node indices.
Int endDescendents;
};
/// Storage for the dominator tree itself
List<Node> nodes;
/// Value to use for invalid node indices (e.g.,
/// when a node has no parent).
static const Int kInvalidIndex = -1;
//
// The `DominatedList` type needs direct access to all of this
// data in order to provide iteration.
//
friend struct DominatedList;
friend struct DominatedList::Iterator;
//
// The context type we will use to compute the dominator tree
// also needs to be able to access all the fields to initialze
// an `IRDominatorTree`
//
friend struct DominatorTreeComputationContext;
// TODO: we should probably build/store a postdominator
// tree in the same structure, just to make life simpler.
};
RefPtr<IRDominatorTree> computeDominatorTree(IRGlobalValueWithCode* code);
void computePostorder(IRGlobalValueWithCode* code, List<IRBlock*>& outOrder);
void computePostorder(
IRGlobalValueWithCode* code,
List<IRBlock*>& outOrder,
HashSet<IRBlock*>& outReachableSet);
void computePostorderOnReverseCFG(IRGlobalValueWithCode* code, List<IRBlock*>& outOrder);
inline List<IRBlock*> getPostorder(IRGlobalValueWithCode* code)
{
List<IRBlock*> result;
computePostorder(code, result);
return result;
}
inline List<IRBlock*> getPostorderOnReverseCFG(IRGlobalValueWithCode* code)
{
List<IRBlock*> result;
computePostorderOnReverseCFG(code, result);
return result;
}
inline List<IRBlock*> getReversePostorder(IRGlobalValueWithCode* code)
{
List<IRBlock*> result;
computePostorder(code, result);
result.reverse();
return result;
}
inline List<IRBlock*> getReversePostorderOnReverseCFG(IRGlobalValueWithCode* code)
{
List<IRBlock*> result;
computePostorderOnReverseCFG(code, result);
result.reverse();
return result;
}
} // namespace Slang
|
