Coverage Report

Created: 2025-06-13 06:49

/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_