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 // This file implements the SSA rewriting algorithm proposed in
16 //
17 // Simple and Efficient Construction of Static Single Assignment Form.
18 // Braun M., Buchwald S., Hack S., Leißa R., Mallon C., Zwinkau A. (2013)
19 // In: Jhala R., De Bosschere K. (eds)
20 // Compiler Construction. CC 2013.
21 // Lecture Notes in Computer Science, vol 7791.
22 // Springer, Berlin, Heidelberg
23 //
24 // https://link.springer.com/chapter/10.1007/978-3-642-37051-9_6
25 //
26 // In contrast to common eager algorithms based on dominance and dominance
27 // frontier information, this algorithm works backwards from load operations.
28 //
29 // When a target variable is loaded, it queries the variable's reaching
30 // definition. If the reaching definition is unknown at the current location,
31 // it searches backwards in the CFG, inserting Phi instructions at join points
32 // in the CFG along the way until it finds the desired store instruction.
33 //
34 // The algorithm avoids repeated lookups using memoization.
35 //
36 // For reducible CFGs, which are a superset of the structured CFGs in SPIRV,
37 // this algorithm is proven to produce minimal SSA. That is, it inserts the
38 // minimal number of Phi instructions required to ensure the SSA property, but
39 // some Phi instructions may be dead
40 // (https://en.wikipedia.org/wiki/Static_single_assignment_form).
41
42 #include "source/opt/ssa_rewrite_pass.h"
43
44 #include <memory>
45 #include <sstream>
46
47 #include "source/opcode.h"
48 #include "source/opt/cfg.h"
49 #include "source/opt/mem_pass.h"
50 #include "source/opt/types.h"
51 #include "source/util/make_unique.h"
52
53 // Debug logging (0: Off, 1-N: Verbosity level). Replace this with the
54 // implementation done for
55 // https://github.com/KhronosGroup/SPIRV-Tools/issues/1351
56 // #define SSA_REWRITE_DEBUGGING_LEVEL 3
57
58 #ifdef SSA_REWRITE_DEBUGGING_LEVEL
59 #include <ostream>
60 #else
61 #define SSA_REWRITE_DEBUGGING_LEVEL 0
62 #endif
63
64 namespace spvtools {
65 namespace opt {
66
67 namespace {
68 const uint32_t kStoreValIdInIdx = 1;
69 const uint32_t kVariableInitIdInIdx = 1;
70 const uint32_t kDebugDeclareOperandVariableIdx = 5;
71 } // namespace
72
PrettyPrint(const CFG * cfg) const73 std::string SSARewriter::PhiCandidate::PrettyPrint(const CFG* cfg) const {
74 std::ostringstream str;
75 str << "%" << result_id_ << " = Phi[%" << var_id_ << ", BB %" << bb_->id()
76 << "](";
77 if (phi_args_.size() > 0) {
78 uint32_t arg_ix = 0;
79 for (uint32_t pred_label : cfg->preds(bb_->id())) {
80 uint32_t arg_id = phi_args_[arg_ix++];
81 str << "[%" << arg_id << ", bb(%" << pred_label << ")] ";
82 }
83 }
84 str << ")";
85 if (copy_of_ != 0) {
86 str << " [COPY OF " << copy_of_ << "]";
87 }
88 str << ((is_complete_) ? " [COMPLETE]" : " [INCOMPLETE]");
89
90 return str.str();
91 }
92
CreatePhiCandidate(uint32_t var_id,BasicBlock * bb)93 SSARewriter::PhiCandidate& SSARewriter::CreatePhiCandidate(uint32_t var_id,
94 BasicBlock* bb) {
95 // TODO(1841): Handle id overflow.
96 uint32_t phi_result_id = pass_->context()->TakeNextId();
97 auto result = phi_candidates_.emplace(
98 phi_result_id, PhiCandidate(var_id, phi_result_id, bb));
99 PhiCandidate& phi_candidate = result.first->second;
100 return phi_candidate;
101 }
102
ReplacePhiUsersWith(const PhiCandidate & phi_to_remove,uint32_t repl_id)103 void SSARewriter::ReplacePhiUsersWith(const PhiCandidate& phi_to_remove,
104 uint32_t repl_id) {
105 for (uint32_t user_id : phi_to_remove.users()) {
106 PhiCandidate* user_phi = GetPhiCandidate(user_id);
107 BasicBlock* bb = pass_->context()->get_instr_block(user_id);
108 if (user_phi) {
109 // If the user is a Phi candidate, replace all arguments that refer to
110 // |phi_to_remove.result_id()| with |repl_id|.
111 for (uint32_t& arg : user_phi->phi_args()) {
112 if (arg == phi_to_remove.result_id()) {
113 arg = repl_id;
114 }
115 }
116 } else if (bb->id() == user_id) {
117 // The phi candidate is the definition of the variable at basic block
118 // |bb|. We must change this to the replacement.
119 WriteVariable(phi_to_remove.var_id(), bb, repl_id);
120 } else {
121 // For regular loads, traverse the |load_replacement_| table looking for
122 // instances of |phi_to_remove|.
123 for (auto& it : load_replacement_) {
124 if (it.second == phi_to_remove.result_id()) {
125 it.second = repl_id;
126 }
127 }
128 }
129 }
130 }
131
TryRemoveTrivialPhi(PhiCandidate * phi_candidate)132 uint32_t SSARewriter::TryRemoveTrivialPhi(PhiCandidate* phi_candidate) {
133 uint32_t same_id = 0;
134 for (uint32_t arg_id : phi_candidate->phi_args()) {
135 if (arg_id == same_id || arg_id == phi_candidate->result_id()) {
136 // This is a self-reference operand or a reference to the same value ID.
137 continue;
138 }
139 if (same_id != 0) {
140 // This Phi candidate merges at least two values. Therefore, it is not
141 // trivial.
142 assert(phi_candidate->copy_of() == 0 &&
143 "Phi candidate transitioning from copy to non-copy.");
144 return phi_candidate->result_id();
145 }
146 same_id = arg_id;
147 }
148
149 // The previous logic has determined that this Phi candidate |phi_candidate|
150 // is trivial. It is essentially the copy operation phi_candidate->phi_result
151 // = Phi(same, same, same, ...). Since it is not necessary, we can re-route
152 // all the users of |phi_candidate->phi_result| to all its users, and remove
153 // |phi_candidate|.
154
155 // Mark the Phi candidate as a trivial copy of |same_id|, so it won't be
156 // generated.
157 phi_candidate->MarkCopyOf(same_id);
158
159 assert(same_id != 0 && "Completed Phis cannot have %0 in their arguments");
160
161 // Since |phi_candidate| always produces |same_id|, replace all the users of
162 // |phi_candidate| with |same_id|.
163 ReplacePhiUsersWith(*phi_candidate, same_id);
164
165 return same_id;
166 }
167
AddPhiOperands(PhiCandidate * phi_candidate)168 uint32_t SSARewriter::AddPhiOperands(PhiCandidate* phi_candidate) {
169 assert(phi_candidate->phi_args().size() == 0 &&
170 "Phi candidate already has arguments");
171
172 bool found_0_arg = false;
173 for (uint32_t pred : pass_->cfg()->preds(phi_candidate->bb()->id())) {
174 BasicBlock* pred_bb = pass_->cfg()->block(pred);
175
176 // If |pred_bb| is not sealed, use %0 to indicate that
177 // |phi_candidate| needs to be completed after the whole CFG has
178 // been processed.
179 //
180 // Note that we cannot call GetReachingDef() in these cases
181 // because this would generate an empty Phi candidate in
182 // |pred_bb|. When |pred_bb| is later processed, a new definition
183 // for |phi_candidate->var_id_| will be lost because
184 // |phi_candidate| will still be reached by the empty Phi.
185 //
186 // Consider:
187 //
188 // BB %23:
189 // %38 = Phi[%i](%int_0[%1], %39[%25])
190 //
191 // ...
192 //
193 // BB %25: [Starts unsealed]
194 // %39 = Phi[%i]()
195 // %34 = ...
196 // OpStore %i %34 -> Currdef(%i) at %25 is %34
197 // OpBranch %23
198 //
199 // When we first create the Phi in %38, we add an operandless Phi in
200 // %39 to hold the unknown reaching def for %i.
201 //
202 // But then, when we go to complete %39 at the end. The reaching def
203 // for %i in %25's predecessor is %38 itself. So we miss the fact
204 // that %25 has a def for %i that should be used.
205 //
206 // By making the argument %0, we make |phi_candidate| incomplete,
207 // which will cause it to be completed after the whole CFG has
208 // been scanned.
209 uint32_t arg_id = IsBlockSealed(pred_bb)
210 ? GetReachingDef(phi_candidate->var_id(), pred_bb)
211 : 0;
212 phi_candidate->phi_args().push_back(arg_id);
213
214 if (arg_id == 0) {
215 found_0_arg = true;
216 } else {
217 // If this argument is another Phi candidate, add |phi_candidate| to the
218 // list of users for the defining Phi.
219 PhiCandidate* defining_phi = GetPhiCandidate(arg_id);
220 if (defining_phi && defining_phi != phi_candidate) {
221 defining_phi->AddUser(phi_candidate->result_id());
222 }
223 }
224 }
225
226 // If we could not fill-in all the arguments of this Phi, mark it incomplete
227 // so it gets completed after the whole CFG has been processed.
228 if (found_0_arg) {
229 phi_candidate->MarkIncomplete();
230 incomplete_phis_.push(phi_candidate);
231 return phi_candidate->result_id();
232 }
233
234 // Try to remove |phi_candidate|, if it's trivial.
235 uint32_t repl_id = TryRemoveTrivialPhi(phi_candidate);
236 if (repl_id == phi_candidate->result_id()) {
237 // |phi_candidate| is complete and not trivial. Add it to the
238 // list of Phi candidates to generate.
239 phi_candidate->MarkComplete();
240 phis_to_generate_.push_back(phi_candidate);
241 }
242
243 return repl_id;
244 }
245
GetValueAtBlock(uint32_t var_id,BasicBlock * bb)246 uint32_t SSARewriter::GetValueAtBlock(uint32_t var_id, BasicBlock* bb) {
247 assert(bb != nullptr);
248 const auto& bb_it = defs_at_block_.find(bb);
249 if (bb_it != defs_at_block_.end()) {
250 const auto& current_defs = bb_it->second;
251 const auto& var_it = current_defs.find(var_id);
252 if (var_it != current_defs.end()) {
253 return var_it->second;
254 }
255 }
256 return 0;
257 }
258
GetReachingDef(uint32_t var_id,BasicBlock * bb)259 uint32_t SSARewriter::GetReachingDef(uint32_t var_id, BasicBlock* bb) {
260 // If |var_id| has a definition in |bb|, return it.
261 uint32_t val_id = GetValueAtBlock(var_id, bb);
262 if (val_id != 0) return val_id;
263
264 // Otherwise, look up the value for |var_id| in |bb|'s predecessors.
265 auto& predecessors = pass_->cfg()->preds(bb->id());
266 if (predecessors.size() == 1) {
267 // If |bb| has exactly one predecessor, we look for |var_id|'s definition
268 // there.
269 val_id = GetReachingDef(var_id, pass_->cfg()->block(predecessors[0]));
270 } else if (predecessors.size() > 1) {
271 // If there is more than one predecessor, this is a join block which may
272 // require a Phi instruction. This will act as |var_id|'s current
273 // definition to break potential cycles.
274 PhiCandidate& phi_candidate = CreatePhiCandidate(var_id, bb);
275
276 // Set the value for |bb| to avoid an infinite recursion.
277 WriteVariable(var_id, bb, phi_candidate.result_id());
278 val_id = AddPhiOperands(&phi_candidate);
279 }
280
281 // If we could not find a store for this variable in the path from the root
282 // of the CFG, the variable is not defined, so we use undef.
283 if (val_id == 0) {
284 val_id = pass_->GetUndefVal(var_id);
285 if (val_id == 0) {
286 return 0;
287 }
288 }
289
290 WriteVariable(var_id, bb, val_id);
291
292 return val_id;
293 }
294
SealBlock(BasicBlock * bb)295 void SSARewriter::SealBlock(BasicBlock* bb) {
296 auto result = sealed_blocks_.insert(bb);
297 (void)result;
298 assert(result.second == true &&
299 "Tried to seal the same basic block more than once.");
300 }
301
ProcessStore(Instruction * inst,BasicBlock * bb)302 void SSARewriter::ProcessStore(Instruction* inst, BasicBlock* bb) {
303 auto opcode = inst->opcode();
304 assert((opcode == SpvOpStore || opcode == SpvOpVariable) &&
305 "Expecting a store or a variable definition instruction.");
306
307 uint32_t var_id = 0;
308 uint32_t val_id = 0;
309 if (opcode == SpvOpStore) {
310 (void)pass_->GetPtr(inst, &var_id);
311 val_id = inst->GetSingleWordInOperand(kStoreValIdInIdx);
312 } else if (inst->NumInOperands() >= 2) {
313 var_id = inst->result_id();
314 val_id = inst->GetSingleWordInOperand(kVariableInitIdInIdx);
315 }
316 if (pass_->IsTargetVar(var_id)) {
317 WriteVariable(var_id, bb, val_id);
318 pass_->context()->get_debug_info_mgr()->AddDebugValueIfVarDeclIsVisible(
319 inst, var_id, val_id, inst, &decls_invisible_to_value_assignment_);
320
321 #if SSA_REWRITE_DEBUGGING_LEVEL > 1
322 std::cerr << "\tFound store '%" << var_id << " = %" << val_id << "': "
323 << inst->PrettyPrint(SPV_BINARY_TO_TEXT_OPTION_FRIENDLY_NAMES)
324 << "\n";
325 #endif
326 }
327 }
328
ProcessLoad(Instruction * inst,BasicBlock * bb)329 bool SSARewriter::ProcessLoad(Instruction* inst, BasicBlock* bb) {
330 // Get the pointer that we are using to load from.
331 uint32_t var_id = 0;
332 (void)pass_->GetPtr(inst, &var_id);
333
334 // Get the immediate reaching definition for |var_id|.
335 //
336 // In the presence of variable pointers, the reaching definition may be
337 // another pointer. For example, the following fragment:
338 //
339 // %2 = OpVariable %_ptr_Input_float Input
340 // %11 = OpVariable %_ptr_Function__ptr_Input_float Function
341 // OpStore %11 %2
342 // %12 = OpLoad %_ptr_Input_float %11
343 // %13 = OpLoad %float %12
344 //
345 // corresponds to the pseudo-code:
346 //
347 // layout(location = 0) in flat float *%2
348 // float %13;
349 // float *%12;
350 // float **%11;
351 // *%11 = %2;
352 // %12 = *%11;
353 // %13 = *%12;
354 //
355 // which ultimately, should correspond to:
356 //
357 // %13 = *%2;
358 //
359 // During rewriting, the pointer %12 is found to be replaceable by %2 (i.e.,
360 // load_replacement_[12] is 2). However, when processing the load
361 // %13 = *%12, the type of %12's reaching definition is another float
362 // pointer (%2), instead of a float value.
363 //
364 // When this happens, we need to continue looking up the reaching definition
365 // chain until we get to a float value or a non-target var (i.e. a variable
366 // that cannot be SSA replaced, like %2 in this case since it is a function
367 // argument).
368 analysis::DefUseManager* def_use_mgr = pass_->context()->get_def_use_mgr();
369 analysis::TypeManager* type_mgr = pass_->context()->get_type_mgr();
370 analysis::Type* load_type = type_mgr->GetType(inst->type_id());
371 uint32_t val_id = 0;
372 bool found_reaching_def = false;
373 while (!found_reaching_def) {
374 if (!pass_->IsTargetVar(var_id)) {
375 // If the variable we are loading from is not an SSA target (globals,
376 // function parameters), do nothing.
377 return true;
378 }
379
380 val_id = GetReachingDef(var_id, bb);
381 if (val_id == 0) {
382 return false;
383 }
384
385 // If the reaching definition is a pointer type different than the type of
386 // the instruction we are analyzing, then it must be a reference to another
387 // pointer (otherwise, this would be invalid SPIRV). We continue
388 // de-referencing it by making |val_id| be |var_id|.
389 //
390 // NOTE: if there is no reaching definition instruction, it means |val_id|
391 // is an undef.
392 Instruction* reaching_def_inst = def_use_mgr->GetDef(val_id);
393 if (reaching_def_inst &&
394 !type_mgr->GetType(reaching_def_inst->type_id())->IsSame(load_type)) {
395 var_id = val_id;
396 } else {
397 found_reaching_def = true;
398 }
399 }
400
401 // Schedule a replacement for the result of this load instruction with
402 // |val_id|. After all the rewriting decisions are made, every use of
403 // this load will be replaced with |val_id|.
404 uint32_t load_id = inst->result_id();
405 assert(load_replacement_.count(load_id) == 0);
406 load_replacement_[load_id] = val_id;
407 PhiCandidate* defining_phi = GetPhiCandidate(val_id);
408 if (defining_phi) {
409 defining_phi->AddUser(load_id);
410 }
411
412 #if SSA_REWRITE_DEBUGGING_LEVEL > 1
413 std::cerr << "\tFound load: "
414 << inst->PrettyPrint(SPV_BINARY_TO_TEXT_OPTION_FRIENDLY_NAMES)
415 << " (replacement for %" << load_id << " is %" << val_id << ")\n";
416 #endif
417
418 return true;
419 }
420
PrintPhiCandidates() const421 void SSARewriter::PrintPhiCandidates() const {
422 std::cerr << "\nPhi candidates:\n";
423 for (const auto& phi_it : phi_candidates_) {
424 std::cerr << "\tBB %" << phi_it.second.bb()->id() << ": "
425 << phi_it.second.PrettyPrint(pass_->cfg()) << "\n";
426 }
427 std::cerr << "\n";
428 }
429
PrintReplacementTable() const430 void SSARewriter::PrintReplacementTable() const {
431 std::cerr << "\nLoad replacement table\n";
432 for (const auto& it : load_replacement_) {
433 std::cerr << "\t%" << it.first << " -> %" << it.second << "\n";
434 }
435 std::cerr << "\n";
436 }
437
GenerateSSAReplacements(BasicBlock * bb)438 bool SSARewriter::GenerateSSAReplacements(BasicBlock* bb) {
439 #if SSA_REWRITE_DEBUGGING_LEVEL > 1
440 std::cerr << "Generating SSA replacements for block: " << bb->id() << "\n";
441 std::cerr << bb->PrettyPrint(SPV_BINARY_TO_TEXT_OPTION_FRIENDLY_NAMES)
442 << "\n";
443 #endif
444
445 for (auto& inst : *bb) {
446 auto opcode = inst.opcode();
447 if (opcode == SpvOpStore || opcode == SpvOpVariable) {
448 ProcessStore(&inst, bb);
449 } else if (inst.opcode() == SpvOpLoad) {
450 if (!ProcessLoad(&inst, bb)) {
451 return false;
452 }
453 }
454 }
455
456 // Seal |bb|. This means that all the stores in it have been scanned and
457 // it's ready to feed them into its successors.
458 SealBlock(bb);
459
460 #if SSA_REWRITE_DEBUGGING_LEVEL > 1
461 PrintPhiCandidates();
462 PrintReplacementTable();
463 std::cerr << "\n\n";
464 #endif
465 return true;
466 }
467
GetReplacement(std::pair<uint32_t,uint32_t> repl)468 uint32_t SSARewriter::GetReplacement(std::pair<uint32_t, uint32_t> repl) {
469 uint32_t val_id = repl.second;
470 auto it = load_replacement_.find(val_id);
471 while (it != load_replacement_.end()) {
472 val_id = it->second;
473 it = load_replacement_.find(val_id);
474 }
475 return val_id;
476 }
477
GetPhiArgument(const PhiCandidate * phi_candidate,uint32_t ix)478 uint32_t SSARewriter::GetPhiArgument(const PhiCandidate* phi_candidate,
479 uint32_t ix) {
480 assert(phi_candidate->IsReady() &&
481 "Tried to get the final argument from an incomplete/trivial Phi");
482
483 uint32_t arg_id = phi_candidate->phi_args()[ix];
484 while (arg_id != 0) {
485 PhiCandidate* phi_user = GetPhiCandidate(arg_id);
486 if (phi_user == nullptr || phi_user->IsReady()) {
487 // If the argument is not a Phi or it's a Phi candidate ready to be
488 // emitted, return it.
489 return arg_id;
490 }
491 arg_id = phi_user->copy_of();
492 }
493
494 assert(false &&
495 "No Phi candidates in the copy-of chain are ready to be generated");
496
497 return 0;
498 }
499
ApplyReplacements()500 bool SSARewriter::ApplyReplacements() {
501 bool modified = false;
502
503 #if SSA_REWRITE_DEBUGGING_LEVEL > 2
504 std::cerr << "\n\nApplying replacement decisions to IR\n\n";
505 PrintPhiCandidates();
506 PrintReplacementTable();
507 std::cerr << "\n\n";
508 #endif
509
510 // Add Phi instructions from completed Phi candidates.
511 std::vector<Instruction*> generated_phis;
512 for (const PhiCandidate* phi_candidate : phis_to_generate_) {
513 #if SSA_REWRITE_DEBUGGING_LEVEL > 2
514 std::cerr << "Phi candidate: " << phi_candidate->PrettyPrint(pass_->cfg())
515 << "\n";
516 #endif
517
518 assert(phi_candidate->is_complete() &&
519 "Tried to instantiate a Phi instruction from an incomplete Phi "
520 "candidate");
521
522 auto* local_var = pass_->get_def_use_mgr()->GetDef(phi_candidate->var_id());
523
524 // Build the vector of operands for the new OpPhi instruction.
525 uint32_t type_id = pass_->GetPointeeTypeId(local_var);
526 std::vector<Operand> phi_operands;
527 uint32_t arg_ix = 0;
528 std::unordered_map<uint32_t, uint32_t> already_seen;
529 for (uint32_t pred_label : pass_->cfg()->preds(phi_candidate->bb()->id())) {
530 uint32_t op_val_id = GetPhiArgument(phi_candidate, arg_ix++);
531 if (already_seen.count(pred_label) == 0) {
532 phi_operands.push_back(
533 {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {op_val_id}});
534 phi_operands.push_back(
535 {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {pred_label}});
536 already_seen[pred_label] = op_val_id;
537 } else {
538 // It is possible that there are two edges from the same parent block.
539 // Since the OpPhi can have only one entry for each parent, we have to
540 // make sure the two edges are consistent with each other.
541 assert(already_seen[pred_label] == op_val_id &&
542 "Inconsistent value for duplicate edges.");
543 }
544 }
545
546 // Generate a new OpPhi instruction and insert it in its basic
547 // block.
548 std::unique_ptr<Instruction> phi_inst(
549 new Instruction(pass_->context(), SpvOpPhi, type_id,
550 phi_candidate->result_id(), phi_operands));
551 generated_phis.push_back(phi_inst.get());
552 pass_->get_def_use_mgr()->AnalyzeInstDef(&*phi_inst);
553 pass_->context()->set_instr_block(&*phi_inst, phi_candidate->bb());
554 auto insert_it = phi_candidate->bb()->begin();
555 insert_it = insert_it.InsertBefore(std::move(phi_inst));
556 pass_->context()->get_decoration_mgr()->CloneDecorations(
557 phi_candidate->var_id(), phi_candidate->result_id(),
558 {SpvDecorationRelaxedPrecision});
559
560 // Add DebugValue for the new OpPhi instruction.
561 insert_it->SetDebugScope(local_var->GetDebugScope());
562 pass_->context()->get_debug_info_mgr()->AddDebugValueIfVarDeclIsVisible(
563 &*insert_it, phi_candidate->var_id(), phi_candidate->result_id(),
564 &*insert_it, &decls_invisible_to_value_assignment_);
565
566 modified = true;
567 }
568
569 // Scan uses for all inserted Phi instructions. Do this separately from the
570 // registration of the Phi instruction itself to avoid trying to analyze
571 // uses of Phi instructions that have not been registered yet.
572 for (Instruction* phi_inst : generated_phis) {
573 pass_->get_def_use_mgr()->AnalyzeInstUse(&*phi_inst);
574 }
575
576 #if SSA_REWRITE_DEBUGGING_LEVEL > 1
577 std::cerr << "\n\nReplacing the result of load instructions with the "
578 "corresponding SSA id\n\n";
579 #endif
580
581 // Apply replacements from the load replacement table.
582 for (auto& repl : load_replacement_) {
583 uint32_t load_id = repl.first;
584 uint32_t val_id = GetReplacement(repl);
585 Instruction* load_inst =
586 pass_->context()->get_def_use_mgr()->GetDef(load_id);
587
588 #if SSA_REWRITE_DEBUGGING_LEVEL > 2
589 std::cerr << "\t"
590 << load_inst->PrettyPrint(
591 SPV_BINARY_TO_TEXT_OPTION_FRIENDLY_NAMES)
592 << " (%" << load_id << " -> %" << val_id << ")\n";
593 #endif
594
595 // Remove the load instruction and replace all the uses of this load's
596 // result with |val_id|. Kill any names or decorates using the load's
597 // result before replacing to prevent incorrect replacement in those
598 // instructions.
599 pass_->context()->KillNamesAndDecorates(load_id);
600 pass_->context()->ReplaceAllUsesWith(load_id, val_id);
601 pass_->context()->KillInst(load_inst);
602 modified = true;
603 }
604
605 return modified;
606 }
607
FinalizePhiCandidate(PhiCandidate * phi_candidate)608 void SSARewriter::FinalizePhiCandidate(PhiCandidate* phi_candidate) {
609 assert(phi_candidate->phi_args().size() > 0 &&
610 "Phi candidate should have arguments");
611
612 uint32_t ix = 0;
613 for (uint32_t pred : pass_->cfg()->preds(phi_candidate->bb()->id())) {
614 BasicBlock* pred_bb = pass_->cfg()->block(pred);
615 uint32_t& arg_id = phi_candidate->phi_args()[ix++];
616 if (arg_id == 0) {
617 // If |pred_bb| is still not sealed, it means it's unreachable. In this
618 // case, we just use Undef as an argument.
619 arg_id = IsBlockSealed(pred_bb)
620 ? GetReachingDef(phi_candidate->var_id(), pred_bb)
621 : pass_->GetUndefVal(phi_candidate->var_id());
622 }
623 }
624
625 // This candidate is now completed.
626 phi_candidate->MarkComplete();
627
628 // If |phi_candidate| is not trivial, add it to the list of Phis to
629 // generate.
630 if (TryRemoveTrivialPhi(phi_candidate) == phi_candidate->result_id()) {
631 // If we could not remove |phi_candidate|, it means that it is complete
632 // and not trivial. Add it to the list of Phis to generate.
633 assert(!phi_candidate->copy_of() && "A completed Phi cannot be trivial.");
634 phis_to_generate_.push_back(phi_candidate);
635 }
636 }
637
FinalizePhiCandidates()638 void SSARewriter::FinalizePhiCandidates() {
639 #if SSA_REWRITE_DEBUGGING_LEVEL > 1
640 std::cerr << "Finalizing Phi candidates:\n\n";
641 PrintPhiCandidates();
642 std::cerr << "\n";
643 #endif
644
645 // Now, complete the collected candidates.
646 while (incomplete_phis_.size() > 0) {
647 PhiCandidate* phi_candidate = incomplete_phis_.front();
648 incomplete_phis_.pop();
649 FinalizePhiCandidate(phi_candidate);
650 }
651 }
652
AddDebugValuesForInvisibleDebugDecls(Function * fp)653 Pass::Status SSARewriter::AddDebugValuesForInvisibleDebugDecls(Function* fp) {
654 // For the cases the value assignment is invisible to DebugDeclare e.g.,
655 // the argument passing for an inlined function.
656 //
657 // Before inlining foo(int x):
658 // a = 3;
659 // foo(3);
660 // After inlining:
661 // a = 3; // we want to specify "DebugValue: %x = %int_3"
662 // foo and x disappeared!
663 //
664 // We want to specify the value for the variable using |defs_at_block_[bb]|,
665 // where |bb| is the basic block contains the decl.
666 DominatorAnalysis* dom_tree = pass_->context()->GetDominatorAnalysis(fp);
667 Pass::Status status = Pass::Status::SuccessWithoutChange;
668 for (auto* decl : decls_invisible_to_value_assignment_) {
669 uint32_t var_id =
670 decl->GetSingleWordOperand(kDebugDeclareOperandVariableIdx);
671 auto* var = pass_->get_def_use_mgr()->GetDef(var_id);
672 if (var->opcode() == SpvOpFunctionParameter) continue;
673
674 auto* bb = pass_->context()->get_instr_block(decl);
675 uint32_t value_id = GetValueAtBlock(var_id, bb);
676 Instruction* value = nullptr;
677 if (value_id) value = pass_->get_def_use_mgr()->GetDef(value_id);
678
679 // If |value| is defined before the function body, it dominates |decl|.
680 // If |value| dominates |decl|, we can set it as DebugValue.
681 if (value && (pass_->context()->get_instr_block(value) == nullptr ||
682 dom_tree->Dominates(value, decl))) {
683 if (!pass_->context()->get_debug_info_mgr()->AddDebugValueForDecl(
684 decl, value->result_id())) {
685 return Pass::Status::Failure;
686 }
687 } else {
688 // If |value| in the same basic block does not dominate |decl|, we can
689 // assign the value in the immediate dominator.
690 value_id = GetValueAtBlock(var_id, dom_tree->ImmediateDominator(bb));
691 if (value_id &&
692 !pass_->context()->get_debug_info_mgr()->AddDebugValueForDecl(
693 decl, value_id)) {
694 return Pass::Status::Failure;
695 }
696 }
697
698 // DebugDeclares of target variables will be removed by
699 // SSARewritePass::Process().
700 if (!pass_->IsTargetVar(var_id)) {
701 pass_->context()->get_debug_info_mgr()->KillDebugDeclares(var_id);
702 }
703 status = Pass::Status::SuccessWithChange;
704 }
705 return status;
706 }
707
RewriteFunctionIntoSSA(Function * fp)708 Pass::Status SSARewriter::RewriteFunctionIntoSSA(Function* fp) {
709 #if SSA_REWRITE_DEBUGGING_LEVEL > 0
710 std::cerr << "Function before SSA rewrite:\n"
711 << fp->PrettyPrint(0) << "\n\n\n";
712 #endif
713
714 // Collect variables that can be converted into SSA IDs.
715 pass_->CollectTargetVars(fp);
716
717 // Generate all the SSA replacements and Phi candidates. This will
718 // generate incomplete and trivial Phis.
719 bool succeeded = pass_->cfg()->WhileEachBlockInReversePostOrder(
720 fp->entry().get(), [this](BasicBlock* bb) {
721 if (!GenerateSSAReplacements(bb)) {
722 return false;
723 }
724 return true;
725 });
726
727 if (!succeeded) {
728 return Pass::Status::Failure;
729 }
730
731 // Remove trivial Phis and add arguments to incomplete Phis.
732 FinalizePhiCandidates();
733
734 // Finally, apply all the replacements in the IR.
735 bool modified = ApplyReplacements();
736
737 auto status = AddDebugValuesForInvisibleDebugDecls(fp);
738 if (status == Pass::Status::SuccessWithChange ||
739 status == Pass::Status::Failure) {
740 return status;
741 }
742
743 #if SSA_REWRITE_DEBUGGING_LEVEL > 0
744 std::cerr << "\n\n\nFunction after SSA rewrite:\n"
745 << fp->PrettyPrint(0) << "\n";
746 #endif
747
748 return modified ? Pass::Status::SuccessWithChange
749 : Pass::Status::SuccessWithoutChange;
750 }
751
Process()752 Pass::Status SSARewritePass::Process() {
753 Status status = Status::SuccessWithoutChange;
754 for (auto& fn : *get_module()) {
755 status =
756 CombineStatus(status, SSARewriter(this).RewriteFunctionIntoSSA(&fn));
757 // Kill DebugDeclares for target variables.
758 for (auto var_id : seen_target_vars_) {
759 context()->get_debug_info_mgr()->KillDebugDeclares(var_id);
760 }
761 if (status == Status::Failure) {
762 break;
763 }
764 }
765 return status;
766 }
767
768 } // namespace opt
769 } // namespace spvtools
770