Debian Codegraph @

third_party/spirv-tools/source/opt/propagator.h

raw
1 // Copyright (c) 2017 Google Inc.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef SOURCE_OPT_PROPAGATOR_H_
16 #define SOURCE_OPT_PROPAGATOR_H_
17
18 #include <functional>
19 #include <queue>
20 #include <set>
21 #include <unordered_map>
22 #include <unordered_set>
23 #include <utility>
24 #include <vector>
25
26 #include "source/opt/ir_context.h"
27 #include "source/opt/module.h"
28
29 namespace spvtools {
30 namespace opt {
31
32 // Represents a CFG control edge.
33 struct Edge {
34 Edge(BasicBlock* b1, BasicBlock* b2) : source(b1), dest(b2) {
35 assert(source && "CFG edges cannot have a null source block.");
36 assert(dest && "CFG edges cannot have a null destination block.");
37 }
38 BasicBlock* source;
39 BasicBlock* dest;
40 bool operator<(const Edge& o) const {
41 return std::make_pair(source->id(), dest->id()) <
42 std::make_pair(o.source->id(), o.dest->id());
43 }
44 };
45
46 // This class implements a generic value propagation algorithm based on the
47 // conditional constant propagation algorithm proposed in
48 //
49 // Constant propagation with conditional branches,
50 // Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
51 //
52 // A Propagation Engine for GCC
53 // Diego Novillo, GCC Summit 2005
54 // http://ols.fedoraproject.org/GCC/Reprints-2005/novillo-Reprint.pdf
55 //
56 // The purpose of this implementation is to act as a common framework for any
57 // transformation that needs to propagate values from statements producing new
58 // values to statements using those values. Simulation proceeds as follows:
59 //
60 // 1- Initially, all edges of the CFG are marked not executable and the CFG
61 // worklist is seeded with all the statements in the entry basic block.
62 //
63 // 2- Every instruction I is simulated by calling a pass-provided function
64 // |visit_fn|. This function is responsible for three things:
65 //
66 // (a) Keep a value table of interesting values. This table maps SSA IDs to
67 // their values. For instance, when implementing constant propagation,
68 // given a store operation 'OpStore %f %int_3', |visit_fn| should assign
69 // the value 3 to the table slot for %f.
70 //
71 // In general, |visit_fn| will need to use the value table to replace its
72 // operands, fold the result and decide whether a new value needs to be
73 // stored in the table. |visit_fn| should only create a new mapping in
74 // the value table if all the operands in the instruction are known and
75 // present in the value table.
76 //
77 // (b) Return a status indicator to direct the propagator logic. Once the
78 // instruction is simulated, the propagator needs to know whether this
79 // instruction produced something interesting. This is indicated via
80 // |visit_fn|'s return value:
81 //
82 // SSAPropagator::kNotInteresting: Instruction I produces nothing of
83 // interest and does not affect any of the work lists. The
84 // propagator will visit the statement again if any of its operands
85 // produce an interesting value in the future.
86 //
87 // |visit_fn| should always return this value when it is not sure
88 // whether the instruction will produce an interesting value in the
89 // future or not. For instance, for constant propagation, an OpIAdd
90 // instruction may produce a constant if its two operands are
91 // constant, but the first time we visit the instruction, we still
92 // may not have its operands in the value table.
93 //
94 // SSAPropagator::kVarying: The value produced by I cannot be determined
95 // at compile time. Further simulation of I is not required. The
96 // propagator will not visit this instruction again. Additionally,
97 // the propagator will add all the instructions at the end of SSA
98 // def-use edges to be simulated again.
99 //
100 // If I is a basic block terminator, it will mark all outgoing edges
101 // as executable so they are traversed one more time. Eventually
102 // the kVarying attribute will be spread out to all the data and
103 // control dependents for I.
104 //
105 // It is important for propagation to use kVarying as a bottom value
106 // for the propagation lattice. It should never be possible for an
107 // instruction to return kVarying once and kInteresting on a second
108 // visit. Otherwise, propagation would not stabilize.
109 //
110 // SSAPropagator::kInteresting: Instruction I produces a value that can
111 // be computed at compile time. In this case, |visit_fn| should
112 // create a new mapping between I's result ID and the produced
113 // value. Much like the kNotInteresting case, the propagator will
114 // visit this instruction again if any of its operands changes.
115 // This is useful when the statement changes from one interesting
116 // state to another.
117 //
118 // (c) For conditional branches, |visit_fn| may decide which edge to take out
119 // of I's basic block. For example, if the operand for an OpSwitch is
120 // known to take a specific constant value, |visit_fn| should figure out
121 // the destination basic block and pass it back by setting the second
122 // argument to |visit_fn|.
123 //
124 // At the end of propagation, values in the value table are guaranteed to be
125 // stable and can be replaced in the IR.
126 //
127 // 3- The propagator keeps two work queues. Instructions are only added to
128 // these queues if they produce an interesting or varying value. None of this
129 // should be handled by |visit_fn|. The propagator keeps track of this
130 // automatically (see SSAPropagator::Simulate for implementation).
131 //
132 // CFG blocks: contains the queue of blocks to be simulated.
133 // Blocks are added to this queue if their incoming edges are
134 // executable.
135 //
136 // SSA Edges: An SSA edge is a def-use edge between a value-producing
137 // instruction and its use instruction. The SSA edges list
138 // contains the statements at the end of a def-use edge that need
139 // to be re-visited when an instruction produces a kVarying or
140 // kInteresting result.
141 //
142 // 4- Simulation terminates when all work queues are drained.
143 //
144 //
145 // EXAMPLE: Basic constant store propagator.
146 //
147 // Suppose we want to propagate all constant assignments of the form "OpStore
148 // %id %cst" where "%id" is some variable and "%cst" an OpConstant. The
149 // following code builds a table |values| where every id that was assigned a
150 // constant value is mapped to the constant value it was assigned.
151 //
152 // auto ctx = BuildModule(...);
153 // std::map<uint32_t, uint32_t> values;
154 // const auto visit_fn = [&ctx, &values](Instruction* instr,
155 // BasicBlock** dest_bb) {
156 // if (instr->opcode() == SpvOpStore) {
157 // uint32_t rhs_id = instr->GetSingleWordOperand(1);
158 // Instruction* rhs_def = ctx->get_def_use_mgr()->GetDef(rhs_id);
159 // if (rhs_def->opcode() == SpvOpConstant) {
160 // uint32_t val = rhs_def->GetSingleWordOperand(2);
161 // values[rhs_id] = val;
162 // return SSAPropagator::kInteresting;
163 // }
164 // }
165 // return SSAPropagator::kVarying;
166 // };
167 // SSAPropagator propagator(ctx.get(), &cfg, visit_fn);
168 // propagator.Run(&fn);
169 //
170 // Given the code:
171 //
172 // %int_4 = OpConstant %int 4
173 // %int_3 = OpConstant %int 3
174 // %int_1 = OpConstant %int 1
175 // OpStore %x %int_4
176 // OpStore %y %int_3
177 // OpStore %z %int_1
178 //
179 // After SSAPropagator::Run returns, the |values| map will contain the entries:
180 // values[%x] = 4, values[%y] = 3, and, values[%z] = 1.
181 class SSAPropagator {
182 public:
183 // Lattice values used for propagation. See class documentation for
184 // a description.
185 enum PropStatus { kNotInteresting, kInteresting, kVarying };
186
187 using VisitFunction = std::function<PropStatus(Instruction*, BasicBlock**)>;
188
189 SSAPropagator(IRContext* context, const VisitFunction& visit_fn)
190 : ctx_(context), visit_fn_(visit_fn) {}
191
192 // Runs the propagator on function |fn|. Returns true if changes were made to
193 // the function. Otherwise, it returns false.
194 bool Run(Function* fn);
195
196 // Returns true if the |i|th argument for |phi| comes through a CFG edge that
197 // has been marked executable. |i| should be an index value accepted by
198 // Instruction::GetSingleWordOperand.
199 bool IsPhiArgExecutable(Instruction* phi, uint32_t i) const;
200
201 // Returns true if |inst| has a recorded status. This will be true once |inst|
202 // has been simulated once.
203 bool HasStatus(Instruction* inst) const { return statuses_.count(inst); }
204
205 // Returns the current propagation status of |inst|. Assumes
206 // |HasStatus(inst)| returns true.
207 PropStatus Status(Instruction* inst) const {
208 return statuses_.find(inst)->second;
209 }
210
211 // Records the propagation status |status| for |inst|. Returns true if the
212 // status for |inst| has changed or set was set for the first time.
213 bool SetStatus(Instruction* inst, PropStatus status);
214
215 private:
216 // Initialize processing.
217 void Initialize(Function* fn);
218
219 // Simulate the execution |block| by calling |visit_fn_| on every instruction
220 // in it.
221 bool Simulate(BasicBlock* block);
222
223 // Simulate the execution of |instr| by replacing all the known values in
224 // every operand and determining whether the result is interesting for
225 // propagation. This invokes the callback function |visit_fn_| to determine
226 // the value computed by |instr|.
227 bool Simulate(Instruction* instr);
228
229 // Returns true if |instr| should be simulated again.
230 bool ShouldSimulateAgain(Instruction* instr) const {
231 return do_not_simulate_.find(instr) == do_not_simulate_.end();
232 }
233
234 // Add |instr| to the set of instructions not to simulate again.
235 void DontSimulateAgain(Instruction* instr) { do_not_simulate_.insert(instr); }
236
237 // Returns true if |block| has been simulated already.
238 bool BlockHasBeenSimulated(BasicBlock* block) const {
239 return simulated_blocks_.find(block) != simulated_blocks_.end();
240 }
241
242 // Marks block |block| as simulated.
243 void MarkBlockSimulated(BasicBlock* block) {
244 simulated_blocks_.insert(block);
245 }
246
247 // Marks |edge| as executable. Returns false if the edge was already marked
248 // as executable.
249 bool MarkEdgeExecutable(const Edge& edge) {
250 return executable_edges_.insert(edge).second;
251 }
252
253 // Returns true if |edge| has been marked as executable.
254 bool IsEdgeExecutable(const Edge& edge) const {
255 return executable_edges_.find(edge) != executable_edges_.end();
256 }
257
258 // Returns a pointer to the def-use manager for |ctx_|.
259 analysis::DefUseManager* get_def_use_mgr() const {
260 return ctx_->get_def_use_mgr();
261 }
262
263 // If the CFG edge |e| has not been executed, this function adds |e|'s
264 // destination block to the work list.
265 void AddControlEdge(const Edge& e);
266
267 // Adds all the instructions that use the result of |instr| to the SSA edges
268 // work list. If |instr| produces no result id, this does nothing.
269 void AddSSAEdges(Instruction* instr);
270
271 // IR context to use.
272 IRContext* ctx_;
273
274 // Function that visits instructions during simulation. The output of this
275 // function is used to determine if the simulated instruction produced a value
276 // interesting for propagation. The function is responsible for keeping
277 // track of interesting values by storing them in some user-provided map.
278 VisitFunction visit_fn_;
279
280 // SSA def-use edges to traverse. Each entry is a destination statement for an
281 // SSA def-use edge as returned by |def_use_manager_|.
282 std::queue<Instruction*> ssa_edge_uses_;
283
284 // Blocks to simulate.
285 std::queue<BasicBlock*> blocks_;
286
287 // Blocks simulated during propagation.
288 std::unordered_set<BasicBlock*> simulated_blocks_;
289
290 // Set of instructions that should not be simulated again because they have
291 // been found to be in the kVarying state.
292 std::unordered_set<Instruction*> do_not_simulate_;
293
294 // Map between a basic block and its predecessor edges.
295 // TODO(dnovillo): Move this to CFG and always build them. Alternately,
296 // move it to IRContext and build CFG preds/succs on-demand.
297 std::unordered_map<BasicBlock*, std::vector<Edge>> bb_preds_;
298
299 // Map between a basic block and its successor edges.
300 // TODO(dnovillo): Move this to CFG and always build them. Alternately,
301 // move it to IRContext and build CFG preds/succs on-demand.
302 std::unordered_map<BasicBlock*, std::vector<Edge>> bb_succs_;
303
304 // Set of executable CFG edges.
305 std::set<Edge> executable_edges_;
306
307 // Tracks instruction propagation status.
308 std::unordered_map<Instruction*, SSAPropagator::PropStatus> statuses_;
309 };
310
311 std::ostream& operator<<(std::ostream& str,
312 const SSAPropagator::PropStatus& status);
313
314 } // namespace opt
315 } // namespace spvtools
316
317 #endif // SOURCE_OPT_PROPAGATOR_H_