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
|
// Copyright (c) 2021 Google LLC.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef SOURCE_OPT_CONTROL_DEPENDENCE_H_
#define SOURCE_OPT_CONTROL_DEPENDENCE_H_
#include <algorithm>
#include <cstdint>
#include <functional>
#include <ostream>
#include <unordered_map>
#include <vector>
#include "source/opt/cfg.h"
#include "source/opt/dominator_analysis.h"
namespace spvtools {
namespace opt {
class ControlDependence {
public:
// The label of the source of this dependence, i.e. the block on which the
// target is dependent on.
// A |source_bb_id| of 0 represents an "entry" dependence, meaning that the
// execution of |target_bb_id| is only dependent on entry to the function.
uint32_t source_bb_id() const { return source_bb_id_; }
// The label of the target of this dependence, i.e. the block which is
// dependent on the source.
uint32_t target_bb_id() const { return target_bb_id_; }
// The label of the target of the *branch* for this dependence.
// Equal to the ID of the entry block for entry dependences.
//
// For example, for the partial CFG pictured below:
// 1 ---> 2 ---> 4 ---> 6
// \ \ ^
// \-> 3 \-> 5 -----/
// Block 6 is control dependent on block 1, but this dependence comes from the
// branch 1 -> 2, so in this case the branch target ID would be 2.
uint32_t branch_target_bb_id() const { return branch_target_bb_id_; }
// Create a direct control dependence from BB ID |source| to |target|.
ControlDependence(uint32_t source, uint32_t target)
: source_bb_id_(source),
target_bb_id_(target),
branch_target_bb_id_(target) {}
// Create a control dependence from BB ID |source| to |target| through the
// branch from |source| to |branch_target|.
ControlDependence(uint32_t source, uint32_t target, uint32_t branch_target)
: source_bb_id_(source),
target_bb_id_(target),
branch_target_bb_id_(branch_target) {}
// Gets the ID of the conditional value for the branch corresponding to this
// control dependence. This is the first input operand for both
// OpConditionalBranch and OpSwitch.
// Returns 0 for entry dependences.
uint32_t GetConditionID(const CFG& cfg) const;
bool operator==(const ControlDependence& other) const;
bool operator!=(const ControlDependence& other) const {
return !(*this == other);
}
// Comparison operators, ordered lexicographically. Total ordering.
bool operator<(const ControlDependence& other) const;
bool operator>(const ControlDependence& other) const { return other < *this; }
bool operator<=(const ControlDependence& other) const {
return !(*this > other);
}
bool operator>=(const ControlDependence& other) const {
return !(*this < other);
}
private:
uint32_t source_bb_id_;
uint32_t target_bb_id_;
uint32_t branch_target_bb_id_;
};
// Prints |dep| to |os| in a human-readable way. For example,
// 1->2 (target_bb_id = branch_target_bb_id = 2)
// 3->4 through 5 (target_bb_id = 4, branch_target_bb_id = 5)
std::ostream& operator<<(std::ostream& os, const ControlDependence& dep);
// Represents the control dependence graph. A basic block is control dependent
// on another if the result of that block (e.g. the condition of a conditional
// branch) influences whether it is executed or not. More formally, a block A is
// control dependent on B iff:
// 1. there exists a path from A to the exit node that does *not* go through B
// (i.e., A does not postdominate B), and
// 2. there exists a path B -> b_1 -> ... -> b_n -> A such that A post-dominates
// all nodes b_i.
class ControlDependenceAnalysis {
public:
// Map basic block labels to control dependencies/dependents.
// Not guaranteed to be in any particular order.
using ControlDependenceList = std::vector<ControlDependence>;
using ControlDependenceListMap =
std::unordered_map<uint32_t, ControlDependenceList>;
// 0, the label number for the pseudo entry block.
// All control dependences on the pseudo entry block are of type kEntry, and
// vice versa.
static constexpr uint32_t kPseudoEntryBlock = 0;
// Build the control dependence graph for the given control flow graph |cfg|
// and corresponding post-dominator analysis |pdom|.
void ComputeControlDependenceGraph(const CFG& cfg,
const PostDominatorAnalysis& pdom);
// Get the list of the nodes that depend on a block.
// Return value is not guaranteed to be in any particular order.
const ControlDependenceList& GetDependenceTargets(uint32_t block) const {
return forward_nodes_.at(block);
}
// Get the list of the nodes on which a block depends on.
// Return value is not guaranteed to be in any particular order.
const ControlDependenceList& GetDependenceSources(uint32_t block) const {
return reverse_nodes_.at(block);
}
// Runs the function |f| on each block label in the CDG. If any iteration
// returns false, immediately stops iteration and returns false. Otherwise
// returns true. Nodes are iterated in some undefined order, including the
// pseudo-entry block.
bool WhileEachBlockLabel(std::function<bool(uint32_t)> f) const {
for (const auto& entry : forward_nodes_) {
if (!f(entry.first)) {
return false;
}
}
return true;
}
// Runs the function |f| on each block label in the CDG. Nodes are iterated in
// some undefined order, including the pseudo-entry block.
void ForEachBlockLabel(std::function<void(uint32_t)> f) const {
WhileEachBlockLabel([&f](uint32_t label) {
f(label);
return true;
});
}
// Returns true if the block |id| exists in the control dependence graph.
// This can be false even if the block exists in the function when it is part
// of an infinite loop, since it is not part of the post-dominator tree.
bool HasBlock(uint32_t id) const { return forward_nodes_.count(id) > 0; }
// Returns true if block |a| is dependent on block |b|.
bool IsDependent(uint32_t a, uint32_t b) const {
if (!HasBlock(a)) return false;
// BBs tend to have more dependents (targets) than they are dependent on
// (sources), so search sources.
const ControlDependenceList& a_sources = GetDependenceSources(a);
return std::find_if(a_sources.begin(), a_sources.end(),
[b](const ControlDependence& dep) {
return dep.source_bb_id() == b;
}) != a_sources.end();
}
private:
// Computes the post-dominance frontiers (i.e. the reverse CDG) for each node
// in the post-dominator tree. Only modifies reverse_nodes_; forward_nodes_ is
// not modified.
void ComputePostDominanceFrontiers(const CFG& cfg,
const PostDominatorAnalysis& pdom);
// Computes the post-dominance frontier for a specific node |pdom_node| in the
// post-dominator tree. Result is placed in reverse_nodes_[pdom_node.id()].
void ComputePostDominanceFrontierForNode(const CFG& cfg,
const PostDominatorAnalysis& pdom,
uint32_t function_entry,
const DominatorTreeNode& pdom_node);
// Computes the forward graph (forward_nodes_) from the reverse graph
// (reverse_nodes_).
void ComputeForwardGraphFromReverse();
ControlDependenceListMap forward_nodes_;
ControlDependenceListMap reverse_nodes_;
};
} // namespace opt
} // namespace spvtools
#endif // SOURCE_OPT_CONTROL_DEPENDENCE_H_
|
