Debian Codegraph @

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

raw
1 // Copyright (c) 2018 Google LLC.
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_SSA_REWRITE_PASS_H_
16 #define SOURCE_OPT_SSA_REWRITE_PASS_H_
17
18 #include <queue>
19 #include <string>
20 #include <unordered_map>
21 #include <unordered_set>
22 #include <utility>
23 #include <vector>
24
25 #include "source/opt/basic_block.h"
26 #include "source/opt/ir_context.h"
27 #include "source/opt/mem_pass.h"
28
29 namespace spvtools {
30 namespace opt {
31
32 // Utility class for passes that need to rewrite a function into SSA. This
33 // converts load/store operations on function-local variables into SSA IDs,
34 // which allows them to be the target of optimizing transformations.
35 //
36 // Store and load operations to these variables are converted into
37 // operations on SSA IDs. Phi instructions are added when needed. See the
38 // SSA construction paper for algorithmic details
39 // (https://link.springer.com/chapter/10.1007/978-3-642-37051-9_6)
40 class SSARewriter {
41 public:
42 SSARewriter(MemPass* pass) : pass_(pass) {}
43
44 // Rewrites SSA-target variables in function |fp| into SSA. This is the
45 // entry point for the SSA rewrite algorithm. SSA-target variables are
46 // locally defined variables that meet the criteria set by IsSSATargetVar.
47 //
48 // Returns whether the function was modified or not, and whether or not the
49 // rewrite was successful.
50 Pass::Status RewriteFunctionIntoSSA(Function* fp);
51
52 private:
53 class PhiCandidate {
54 public:
55 explicit PhiCandidate(uint32_t var, uint32_t result, BasicBlock* block)
56 : var_id_(var),
57 result_id_(result),
58 bb_(block),
59 phi_args_(),
60 copy_of_(0),
61 is_complete_(false),
62 users_() {}
63
64 uint32_t var_id() const { return var_id_; }
65 uint32_t result_id() const { return result_id_; }
66 BasicBlock* bb() const { return bb_; }
67 std::vector<uint32_t>& phi_args() { return phi_args_; }
68 const std::vector<uint32_t>& phi_args() const { return phi_args_; }
69 uint32_t copy_of() const { return copy_of_; }
70 bool is_complete() const { return is_complete_; }
71 std::vector<uint32_t>& users() { return users_; }
72 const std::vector<uint32_t>& users() const { return users_; }
73
74 // Marks this phi candidate as a trivial copy of |orig_id|.
75 void MarkCopyOf(uint32_t orig_id) { copy_of_ = orig_id; }
76
77 // Marks this phi candidate as incomplete.
78 void MarkIncomplete() { is_complete_ = false; }
79
80 // Marks this phi candidate as complete.
81 void MarkComplete() { is_complete_ = true; }
82
83 // Returns true if this Phi candidate is ready to be emitted.
84 bool IsReady() const { return is_complete() && copy_of() == 0; }
85
86 // Pretty prints this Phi candidate into a string and returns it. |cfg| is
87 // needed to lookup basic block predecessors.
88 std::string PrettyPrint(const CFG* cfg) const;
89
90 // Registers |operand_id| as a user of this Phi candidate.
91 void AddUser(uint32_t operand_id) { users_.push_back(operand_id); }
92
93 private:
94 // Variable ID that this Phi is merging.
95 uint32_t var_id_;
96
97 // SSA ID generated by this Phi (i.e., this is the result ID of the eventual
98 // Phi instruction).
99 uint32_t result_id_;
100
101 // Basic block to hold this Phi.
102 BasicBlock* bb_;
103
104 // Vector of operands for every predecessor block of |bb|. This vector is
105 // organized so that the Ith slot contains the argument coming from the Ith
106 // predecessor of |bb|.
107 std::vector<uint32_t> phi_args_;
108
109 // If this Phi is a trivial copy of another Phi, this is the ID of the
110 // original. If this is 0, it means that this is not a trivial Phi.
111 uint32_t copy_of_;
112
113 // False, if this Phi candidate has no arguments or at least one argument is
114 // %0.
115 bool is_complete_;
116
117 // List of all users for this Phi instruction. Each element is the result ID
118 // of the load instruction replaced by this Phi, or the result ID of a Phi
119 // candidate that has this Phi in its list of operands.
120 std::vector<uint32_t> users_;
121 };
122
123 // Type used to keep track of store operations in each basic block.
124 typedef std::unordered_map<BasicBlock*,
125 std::unordered_map<uint32_t, uint32_t>>
126 BlockDefsMap;
127
128 // Generates all the SSA rewriting decisions for basic block |bb|. This
129 // populates the Phi candidate table (|phi_candidate_|) and the load
130 // replacement table (|load_replacement_). Returns true if successful.
131 bool GenerateSSAReplacements(BasicBlock* bb);
132
133 // Seals block |bb|. Sealing a basic block means |bb| and all its
134 // predecessors of |bb| have been scanned for loads/stores.
135 void SealBlock(BasicBlock* bb);
136
137 // Returns true if |bb| has been sealed.
138 bool IsBlockSealed(BasicBlock* bb) { return sealed_blocks_.count(bb) != 0; }
139
140 // Returns the Phi candidate with result ID |id| if it exists in the table
141 // |phi_candidates_|. If no such Phi candidate exists, it returns nullptr.
142 PhiCandidate* GetPhiCandidate(uint32_t id) {
143 auto it = phi_candidates_.find(id);
144 return (it != phi_candidates_.end()) ? &it->second : nullptr;
145 }
146
147 // Replaces all the users of Phi candidate |phi_cand| to be users of
148 // |repl_id|.
149 void ReplacePhiUsersWith(const PhiCandidate& phi_cand, uint32_t repl_id);
150
151 // Returns the value ID that should replace the load ID in the given
152 // replacement pair |repl|. The replacement is a pair (|load_id|, |val_id|).
153 // If |val_id| is itself replaced by another value in the table, this function
154 // will look the replacement for |val_id| until it finds one that is not
155 // itself replaced. For instance, given:
156 //
157 // %34 = OpLoad %float %f1
158 // OpStore %t %34
159 // %36 = OpLoad %float %t
160 //
161 // Assume that %f1 is reached by a Phi candidate %42, the load
162 // replacement table will have the following entries:
163 //
164 // %34 -> %42
165 // %36 -> %34
166 //
167 // So, when looking for the replacement for %36, we should not use
168 // %34. Rather, we should use %42. To do this, the chain of
169 // replacements must be followed until we reach an element that has
170 // no replacement.
171 uint32_t GetReplacement(std::pair<uint32_t, uint32_t> repl);
172
173 // Returns the argument at index |ix| from |phi_candidate|. If argument |ix|
174 // comes from a trivial Phi, it follows the copy-of chain from that trivial
175 // Phi until it finds the original Phi candidate.
176 //
177 // This is only valid after all Phi candidates have been completed. It can
178 // only be called when generating the IR for these Phis.
179 uint32_t GetPhiArgument(const PhiCandidate* phi_candidate, uint32_t ix);
180
181 // Applies all the SSA replacement decisions. This replaces loads/stores to
182 // SSA target variables with their corresponding SSA IDs, and inserts Phi
183 // instructions for them.
184 bool ApplyReplacements();
185
186 // Registers a definition for variable |var_id| in basic block |bb| with
187 // value |val_id|.
188 void WriteVariable(uint32_t var_id, BasicBlock* bb, uint32_t val_id) {
189 defs_at_block_[bb][var_id] = val_id;
190 if (auto* pc = GetPhiCandidate(val_id)) {
191 pc->AddUser(bb->id());
192 }
193 }
194
195 // Returns the value of |var_id| at |bb| if |defs_at_block_| contains it.
196 // Otherwise, returns 0.
197 uint32_t GetValueAtBlock(uint32_t var_id, BasicBlock* bb);
198
199 // Processes the store operation |inst| in basic block |bb|. This extracts
200 // the variable ID being stored into, determines whether the variable is an
201 // SSA-target variable, and, if it is, it stores its value in the
202 // |defs_at_block_| map.
203 void ProcessStore(Instruction* inst, BasicBlock* bb);
204
205 // Processes the load operation |inst| in basic block |bb|. This extracts
206 // the variable ID being stored into, determines whether the variable is an
207 // SSA-target variable, and, if it is, it reads its reaching definition by
208 // calling |GetReachingDef|. Returns true if successful.
209 bool ProcessLoad(Instruction* inst, BasicBlock* bb);
210
211 // Reads the current definition for variable |var_id| in basic block |bb|.
212 // If |var_id| is not defined in block |bb| it walks up the predecessors of
213 // |bb|, creating new Phi candidates along the way, if needed.
214 //
215 // It returns the value for |var_id| from the RHS of the current reaching
216 // definition for |var_id|.
217 uint32_t GetReachingDef(uint32_t var_id, BasicBlock* bb);
218
219 // Adds arguments to |phi_candidate| by getting the reaching definition of
220 // |phi_candidate|'s variable on each of the predecessors of its basic
221 // block. After populating the argument list, it determines whether all its
222 // arguments are the same. If so, it returns the ID of the argument that
223 // this Phi copies.
224 uint32_t AddPhiOperands(PhiCandidate* phi_candidate);
225
226 // Creates a Phi candidate instruction for variable |var_id| in basic block
227 // |bb|.
228 //
229 // Since the rewriting algorithm may remove Phi candidates when it finds
230 // them to be trivial, we avoid the expense of creating actual Phi
231 // instructions by keeping a pool of Phi candidates (|phi_candidates_|)
232 // during rewriting.
233 //
234 // Once the candidate Phi is created, it returns its ID.
235 PhiCandidate& CreatePhiCandidate(uint32_t var_id, BasicBlock* bb);
236
237 // Attempts to remove a trivial Phi candidate |phi_cand|. Trivial Phis are
238 // those that only reference themselves and one other value |val| any number
239 // of times. This will try to remove any other Phis that become trivial
240 // after |phi_cand| is removed.
241 //
242 // If |phi_cand| is trivial, it returns the SSA ID for the value that should
243 // replace it. Otherwise, it returns the SSA ID for |phi_cand|.
244 uint32_t TryRemoveTrivialPhi(PhiCandidate* phi_cand);
245
246 // Finalizes |phi_candidate| by replacing every argument that is still %0
247 // with its reaching definition.
248 void FinalizePhiCandidate(PhiCandidate* phi_candidate);
249
250 // Finalizes processing of Phi candidates. Once the whole function has been
251 // scanned for loads and stores, the CFG will still have some incomplete and
252 // trivial Phis. This will add missing arguments and remove trivial Phi
253 // candidates.
254 void FinalizePhiCandidates();
255
256 // Adds DebugValues for DebugDeclares in
257 // |decls_invisible_to_value_assignment_|. Returns whether the function was
258 // modified or not, and whether or not the conversion was successful.
259 Pass::Status AddDebugValuesForInvisibleDebugDecls(Function* fp);
260
261 // Prints the table of Phi candidates to std::cerr.
262 void PrintPhiCandidates() const;
263
264 // Prints the load replacement table to std::cerr.
265 void PrintReplacementTable() const;
266
267 // Map holding the value of every SSA-target variable at every basic block
268 // where the variable is stored. defs_at_block_[block][var_id] = val_id
269 // means that there is a store or Phi instruction for variable |var_id| at
270 // basic block |block| with value |val_id|.
271 BlockDefsMap defs_at_block_;
272
273 // Map, indexed by Phi ID, holding all the Phi candidates created during SSA
274 // rewriting. |phi_candidates_[id]| returns the Phi candidate whose result
275 // is |id|.
276 std::unordered_map<uint32_t, PhiCandidate> phi_candidates_;
277
278 // Queue of incomplete Phi candidates. These are Phi candidates created at
279 // unsealed blocks. They need to be completed before they are instantiated
280 // in ApplyReplacements.
281 std::queue<PhiCandidate*> incomplete_phis_;
282
283 // List of completed Phi candidates. These are the only candidates that
284 // will become real Phi instructions.
285 std::vector<PhiCandidate*> phis_to_generate_;
286
287 // SSA replacement table. This maps variable IDs, resulting from a load
288 // operation, to the value IDs that will replace them after SSA rewriting.
289 // After all the rewriting decisions are made, a final scan through the IR
290 // is done to replace all uses of the original load ID with the value ID.
291 std::unordered_map<uint32_t, uint32_t> load_replacement_;
292
293 // Set of blocks that have been sealed already.
294 std::unordered_set<BasicBlock*> sealed_blocks_;
295
296 // Memory pass requesting the SSA rewriter.
297 MemPass* pass_;
298
299 // Set of DebugDeclare instructions that are not added as DebugValue because
300 // they are invisible to the store or phi instructions.
301 std::unordered_set<Instruction*> decls_invisible_to_value_assignment_;
302 };
303
304 class SSARewritePass : public MemPass {
305 public:
306 SSARewritePass() = default;
307
308 const char* name() const override { return "ssa-rewrite"; }
309 Status Process() override;
310 };
311
312 } // namespace opt
313 } // namespace spvtools
314
315 #endif // SOURCE_OPT_SSA_REWRITE_PASS_H_