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