| 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 |
|
| 73 |
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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 421 |
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 |
|
| 430 |
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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |