/src/spirv-tools/source/opt/propagator.h
Line | Count | Source |
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 | 1.89M | Edge(BasicBlock* b1, BasicBlock* b2) : source(b1), dest(b2) { |
35 | 1.89M | assert(source && "CFG edges cannot have a null source block."); |
36 | 1.89M | assert(dest && "CFG edges cannot have a null destination block."); |
37 | 1.89M | } |
38 | | BasicBlock* source; |
39 | | BasicBlock* dest; |
40 | 13.7M | bool operator<(const Edge& o) const { |
41 | 13.7M | return std::make_pair(source->id(), dest->id()) < |
42 | 13.7M | std::make_pair(o.source->id(), o.dest->id()); |
43 | 13.7M | } |
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() == spv::Op::OpStore) { |
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() == spv::Op::OpConstant) { |
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 | 13.5k | : 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 | 3.76M | 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 | 1.91M | PropStatus Status(Instruction* inst) const { |
208 | 1.91M | return statuses_.find(inst)->second; |
209 | 1.91M | } |
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 | 3.34M | bool ShouldSimulateAgain(Instruction* instr) const { |
231 | 3.34M | return do_not_simulate_.find(instr) == do_not_simulate_.end(); |
232 | 3.34M | } |
233 | | |
234 | | // Add |instr| to the set of instructions not to simulate again. |
235 | 1.50M | void DontSimulateAgain(Instruction* instr) { do_not_simulate_.insert(instr); } |
236 | | |
237 | | // Returns true if |block| has been simulated already. |
238 | 2.59M | bool BlockHasBeenSimulated(BasicBlock* block) const { |
239 | 2.59M | return simulated_blocks_.find(block) != simulated_blocks_.end(); |
240 | 2.59M | } |
241 | | |
242 | | // Marks block |block| as simulated. |
243 | 275k | void MarkBlockSimulated(BasicBlock* block) { |
244 | 275k | simulated_blocks_.insert(block); |
245 | 275k | } |
246 | | |
247 | | // Marks |edge| as executable. Returns false if the edge was already marked |
248 | | // as executable. |
249 | 723k | bool MarkEdgeExecutable(const Edge& edge) { |
250 | 723k | return executable_edges_.insert(edge).second; |
251 | 723k | } |
252 | | |
253 | | // Returns true if |edge| has been marked as executable. |
254 | 624k | bool IsEdgeExecutable(const Edge& edge) const { |
255 | 624k | return executable_edges_.find(edge) != executable_edges_.end(); |
256 | 624k | } |
257 | | |
258 | | // Returns a pointer to the def-use manager for |ctx_|. |
259 | 2.74M | analysis::DefUseManager* get_def_use_mgr() const { |
260 | 2.74M | return ctx_->get_def_use_mgr(); |
261 | 2.74M | } |
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_ |