// Copyright (c) 2018 Google LLC.

//

// Licensed under the Apache License, Version 2.0 (the "License");

// you may not use this file except in compliance with the License.

// You may obtain a copy of the License at

//

//     http://www.apache.org/licenses/LICENSE-2.0

//

// Unless required by applicable law or agreed to in writing, software

// distributed under the License is distributed on an "AS IS" BASIS,

// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

// See the License for the specific language governing permissions and

// limitations under the License.

// This file implements the SSA rewriting algorithm proposed in

//

//      Simple and Efficient Construction of Static Single Assignment Form.

//      Braun M., Buchwald S., Hack S., Leißa R., Mallon C., Zwinkau A. (2013)

//      In: Jhala R., De Bosschere K. (eds)

//      Compiler Construction. CC 2013.

//      Lecture Notes in Computer Science, vol 7791.

//      Springer, Berlin, Heidelberg

//

//      https://link.springer.com/chapter/10.1007/978-3-642-37051-9_6

//

// In contrast to common eager algorithms based on dominance and dominance

// frontier information, this algorithm works backwards from load operations.

//

// When a target variable is loaded, it queries the variable's reaching

// definition.  If the reaching definition is unknown at the current location,

// it searches backwards in the CFG, inserting Phi instructions at join points

// in the CFG along the way until it finds the desired store instruction.

//

// The algorithm avoids repeated lookups using memoization.

//

// For reducible CFGs, which are a superset of the structured CFGs in SPIRV,

// this algorithm is proven to produce minimal SSA.  That is, it inserts the

// minimal number of Phi instructions required to ensure the SSA property, but

// some Phi instructions may be dead

// (https://en.wikipedia.org/wiki/Static_single_assignment_form).

#include "source/opt/ssa_rewrite_pass.h"

#include <memory>

#include <sstream>

#include "source/opcode.h"

#include "source/opt/cfg.h"

#include "source/opt/mem_pass.h"

#include "source/opt/types.h"

// Debug logging (0: Off, 1-N: Verbosity level).  Replace this with the

// implementation done for

// https://github.com/KhronosGroup/SPIRV-Tools/issues/1351

// #define SSA_REWRITE_DEBUGGING_LEVEL 3

#ifdef SSA_REWRITE_DEBUGGING_LEVEL

#include <ostream>

#else

#define SSA_REWRITE_DEBUGGING_LEVEL 0

#endif

namespace spvtools {

namespace opt {

namespace {

constexpr uint32_t kStoreValIdInIdx = 1;

constexpr uint32_t kVariableInitIdInIdx = 1;

}  // namespace

std::string SSARewriter::PhiCandidate::PrettyPrint(const CFG* cfg) const {

  std::ostringstream str;

  str << "%" << result_id_ << " = Phi[%" << var_id_ << ", BB %" << bb_->id()

      << "](";

  if (phi_args_.size() > 0) {

    uint32_t arg_ix = 0;

    for (uint32_t pred_label : cfg->preds(bb_->id())) {

      uint32_t arg_id = phi_args_[arg_ix++];

      str << "[%" << arg_id << ", bb(%" << pred_label << ")] ";

    }

  }

  str << ")";

  if (copy_of_ != 0) {

    str << "  [COPY OF " << copy_of_ << "]";

  }

  str << ((is_complete_) ? "  [COMPLETE]" : "  [INCOMPLETE]");

  return str.str();

}

SSARewriter::PhiCandidate* SSARewriter::CreatePhiCandidate(uint32_t var_id,

                                                           BasicBlock* bb) {

  uint32_t phi_result_id = pass_->context()->TakeNextId();

  if (phi_result_id == 0) {

    return nullptr;

  }

  auto result = phi_candidates_.emplace(

      phi_result_id, PhiCandidate(var_id, phi_result_id, bb));

  PhiCandidate* phi_candidate = &result.first->second;

  return phi_candidate;

}

void SSARewriter::ReplacePhiUsersWith(const PhiCandidate& phi_to_remove,

                                      uint32_t repl_id) {

  for (uint32_t user_id : phi_to_remove.users()) {

    PhiCandidate* user_phi = GetPhiCandidate(user_id);

    BasicBlock* bb = pass_->context()->get_instr_block(user_id);

    if (user_phi) {

      // If the user is a Phi candidate, replace all arguments that refer to

      // |phi_to_remove.result_id()| with |repl_id|.

      for (uint32_t& arg : user_phi->phi_args()) {

        if (arg == phi_to_remove.result_id()) {

          arg = repl_id;

        }

      }

    } else if (bb->id() == user_id) {

      // The phi candidate is the definition of the variable at basic block

      // |bb|.  We must change this to the replacement.

      WriteVariable(phi_to_remove.var_id(), bb, repl_id);

    } else {

      // For regular loads, traverse the |load_replacement_| table looking for

      // instances of |phi_to_remove|.

      for (auto& it : load_replacement_) {

        if (it.second == phi_to_remove.result_id()) {

          it.second = repl_id;

        }

      }

    }

  }

}

uint32_t SSARewriter::TryRemoveTrivialPhi(PhiCandidate* phi_candidate) {

  uint32_t same_id = 0;

  for (uint32_t arg_id : phi_candidate->phi_args()) {

    if (arg_id == same_id || arg_id == phi_candidate->result_id()) {

      // This is a self-reference operand or a reference to the same value ID.

      continue;

    }

    if (same_id != 0) {

      // This Phi candidate merges at least two values.  Therefore, it is not

      // trivial.

      assert(phi_candidate->copy_of() == 0 &&

             "Phi candidate transitioning from copy to non-copy.");

      return phi_candidate->result_id();

    }

    same_id = arg_id;

  }

  // The previous logic has determined that this Phi candidate |phi_candidate|

  // is trivial.  It is essentially the copy operation phi_candidate->phi_result

  // = Phi(same, same, same, ...).  Since it is not necessary, we can re-route

  // all the users of |phi_candidate->phi_result| to all its users, and remove

  // |phi_candidate|.

  // Mark the Phi candidate as a trivial copy of |same_id|, so it won't be

  // generated.

  phi_candidate->MarkCopyOf(same_id);

  assert(same_id != 0 && "Completed Phis cannot have %0 in their arguments");

  // Since |phi_candidate| always produces |same_id|, replace all the users of

  // |phi_candidate| with |same_id|.

  ReplacePhiUsersWith(*phi_candidate, same_id);

  return same_id;

}

uint32_t SSARewriter::AddPhiOperands(PhiCandidate* phi_candidate) {

  assert(phi_candidate->phi_args().size() == 0 &&

         "Phi candidate already has arguments");

  bool found_0_arg = false;

  for (uint32_t pred : pass_->cfg()->preds(phi_candidate->bb()->id())) {

    BasicBlock* pred_bb = pass_->cfg()->block(pred);

    // If |pred_bb| is not sealed, use %0 to indicate that

    // |phi_candidate| needs to be completed after the whole CFG has

    // been processed.

    //

    // Note that we cannot call GetReachingDef() in these cases

    // because this would generate an empty Phi candidate in

    // |pred_bb|.  When |pred_bb| is later processed, a new definition

    // for |phi_candidate->var_id_| will be lost because

    // |phi_candidate| will still be reached by the empty Phi.

    //

    // Consider:

    //

    //       BB %23:

    //           %38 = Phi[%i](%int_0[%1], %39[%25])

    //

    //           ...

    //

    //       BB %25: [Starts unsealed]

    //       %39 = Phi[%i]()

    //       %34 = ...

    //       OpStore %i %34    -> Currdef(%i) at %25 is %34

    //       OpBranch %23

    //

    // When we first create the Phi in %38, we add an operandless Phi in

    // %39 to hold the unknown reaching def for %i.

    //

    // But then, when we go to complete %39 at the end.  The reaching def

    // for %i in %25's predecessor is %38 itself.  So we miss the fact

    // that %25 has a def for %i that should be used.

    //

    // By making the argument %0, we make |phi_candidate| incomplete,

    // which will cause it to be completed after the whole CFG has

    // been scanned.

    uint32_t arg_id = IsBlockSealed(pred_bb)

                          ? GetReachingDef(phi_candidate->var_id(), pred_bb)

                          : 0;

    phi_candidate->phi_args().push_back(arg_id);

    if (arg_id == 0) {

      found_0_arg = true;

    } else {

      // If this argument is another Phi candidate, add |phi_candidate| to the

      // list of users for the defining Phi.

      PhiCandidate* defining_phi = GetPhiCandidate(arg_id);

      if (defining_phi && defining_phi != phi_candidate) {

        defining_phi->AddUser(phi_candidate->result_id());

      }

    }

  }

  // If we could not fill-in all the arguments of this Phi, mark it incomplete

  // so it gets completed after the whole CFG has been processed.

  if (found_0_arg) {

    phi_candidate->MarkIncomplete();

    incomplete_phis_.push(phi_candidate);

    return phi_candidate->result_id();

  }

  // Try to remove |phi_candidate|, if it's trivial.

  uint32_t repl_id = TryRemoveTrivialPhi(phi_candidate);

  if (repl_id == phi_candidate->result_id()) {

    // |phi_candidate| is complete and not trivial.  Add it to the

    // list of Phi candidates to generate.

    phi_candidate->MarkComplete();

    phis_to_generate_.push_back(phi_candidate);

  }

  return repl_id;

}

uint32_t SSARewriter::GetValueAtBlock(uint32_t var_id, BasicBlock* bb) {

  assert(bb != nullptr);

  const auto& bb_it = defs_at_block_.find(bb);

  if (bb_it != defs_at_block_.end()) {

    const auto& current_defs = bb_it->second;

    const auto& var_it = current_defs.find(var_id);

    if (var_it != current_defs.end()) {

      return var_it->second;

    }

  }

  return 0;

}

uint32_t SSARewriter::GetReachingDef(uint32_t var_id, BasicBlock* bb) {

  // If |var_id| has a definition in |bb|, return it.

  uint32_t val_id = GetValueAtBlock(var_id, bb);

  if (val_id != 0) return val_id;

  // Otherwise, look up the value for |var_id| in |bb|'s predecessors.

  auto& predecessors = pass_->cfg()->preds(bb->id());

  if (predecessors.size() == 1) {

    // If |bb| has exactly one predecessor, we look for |var_id|'s definition

    // there.

    val_id = GetReachingDef(var_id, pass_->cfg()->block(predecessors[0]));

  } else if (predecessors.size() > 1) {

    // If there is more than one predecessor, this is a join block which may

    // require a Phi instruction.  This will act as |var_id|'s current

    // definition to break potential cycles.

    PhiCandidate* phi_candidate = CreatePhiCandidate(var_id, bb);

    if (phi_candidate == nullptr) return 0;

    // Set the value for |bb| to avoid an infinite recursion.

    WriteVariable(var_id, bb, phi_candidate->result_id());

    val_id = AddPhiOperands(phi_candidate);

  }

  // If we could not find a store for this variable in the path from the root

  // of the CFG, the variable is not defined, so we use undef.

  if (val_id == 0) {

    val_id = pass_->GetUndefVal(var_id);

    if (val_id == 0) {

      return 0;

    }

  }

  WriteVariable(var_id, bb, val_id);

  return val_id;

}

void SSARewriter::SealBlock(BasicBlock* bb) {

  auto result = sealed_blocks_.insert(bb);

  (void)result;

  assert(result.second == true &&

         "Tried to seal the same basic block more than once.");

}

void SSARewriter::ProcessStore(Instruction* inst, BasicBlock* bb) {

  auto opcode = inst->opcode();

  assert((opcode == spv::Op::OpStore || opcode == spv::Op::OpVariable) &&

         "Expecting a store or a variable definition instruction.");

  uint32_t var_id = 0;

  uint32_t val_id = 0;

  if (opcode == spv::Op::OpStore) {

    (void)pass_->GetPtr(inst, &var_id);

    val_id = inst->GetSingleWordInOperand(kStoreValIdInIdx);

  } else if (inst->NumInOperands() >= 2) {

    var_id = inst->result_id();

    val_id = inst->GetSingleWordInOperand(kVariableInitIdInIdx);

  }

  if (pass_->IsTargetVar(var_id)) {

    WriteVariable(var_id, bb, val_id);

    pass_->context()->get_debug_info_mgr()->AddDebugValueForVariable(

        inst, var_id, val_id, inst);

#if SSA_REWRITE_DEBUGGING_LEVEL > 1

    std::cerr << "\tFound store '%" << var_id << " = %" << val_id << "': "

              << inst->PrettyPrint(SPV_BINARY_TO_TEXT_OPTION_FRIENDLY_NAMES)

              << "\n";

#endif

  }

}

bool SSARewriter::ProcessLoad(Instruction* inst, BasicBlock* bb) {

  // Get the pointer that we are using to load from.

  uint32_t var_id = 0;

  (void)pass_->GetPtr(inst, &var_id);

  // Get the immediate reaching definition for |var_id|.

  //

  // In the presence of variable pointers, the reaching definition may be

  // another pointer.  For example, the following fragment:

  //

  //  %2 = OpVariable %_ptr_Input_float Input

  // %11 = OpVariable %_ptr_Function__ptr_Input_float Function

  //       OpStore %11 %2

  // %12 = OpLoad %_ptr_Input_float %11

  // %13 = OpLoad %float %12

  //

  // corresponds to the pseudo-code:

  //

  // layout(location = 0) in flat float *%2

  // float %13;

  // float *%12;

  // float **%11;

  // *%11 = %2;

  // %12 = *%11;

  // %13 = *%12;

  //

  // which ultimately, should correspond to:

  //

  // %13 = *%2;

  //

  // During rewriting, the pointer %12 is found to be replaceable by %2 (i.e.,

  // load_replacement_[12] is 2). However, when processing the load

  // %13 = *%12, the type of %12's reaching definition is another float

  // pointer (%2), instead of a float value.

  //

  // When this happens, we need to continue looking up the reaching definition

  // chain until we get to a float value or a non-target var (i.e. a variable

  // that cannot be SSA replaced, like %2 in this case since it is a function

  // argument).

  analysis::DefUseManager* def_use_mgr = pass_->context()->get_def_use_mgr();

  analysis::TypeManager* type_mgr = pass_->context()->get_type_mgr();

  analysis::Type* load_type = type_mgr->GetType(inst->type_id());

  uint32_t val_id = 0;

  bool found_reaching_def = false;

  while (!found_reaching_def) {

    if (!pass_->IsTargetVar(var_id)) {

      // If the variable we are loading from is not an SSA target (globals,

      // function parameters), do nothing.

      return true;

    }

    val_id = GetReachingDef(var_id, bb);

    if (val_id == 0) {

      return false;

    }

    // If the reaching definition is a pointer type different than the type of

    // the instruction we are analyzing, then it must be a reference to another

    // pointer (otherwise, this would be invalid SPIRV).  We continue

    // de-referencing it by making |val_id| be |var_id|.

    //

    // NOTE: if there is no reaching definition instruction, it means |val_id|

    // is an undef.

    Instruction* reaching_def_inst = def_use_mgr->GetDef(val_id);

    if (reaching_def_inst &&

        !type_mgr->GetType(reaching_def_inst->type_id())->IsSame(load_type)) {

      var_id = val_id;

    } else {

      found_reaching_def = true;

    }

  }

  // Schedule a replacement for the result of this load instruction with

  // |val_id|. After all the rewriting decisions are made, every use of

  // this load will be replaced with |val_id|.

  uint32_t load_id = inst->result_id();

  assert(load_replacement_.count(load_id) == 0);

  load_replacement_[load_id] = val_id;

  PhiCandidate* defining_phi = GetPhiCandidate(val_id);

  if (defining_phi) {

    defining_phi->AddUser(load_id);

  }

#if SSA_REWRITE_DEBUGGING_LEVEL > 1

  std::cerr << "\tFound load: "

            << inst->PrettyPrint(SPV_BINARY_TO_TEXT_OPTION_FRIENDLY_NAMES)

            << " (replacement for %" << load_id << " is %" << val_id << ")\n";

#endif

  return true;

}

void SSARewriter::PrintPhiCandidates() const {

  std::cerr << "\nPhi candidates:\n";

  for (const auto& phi_it : phi_candidates_) {

    std::cerr << "\tBB %" << phi_it.second.bb()->id() << ": "

              << phi_it.second.PrettyPrint(pass_->cfg()) << "\n";

  }

  std::cerr << "\n";

}

void SSARewriter::PrintReplacementTable() const {

  std::cerr << "\nLoad replacement table\n";

  for (const auto& it : load_replacement_) {

    std::cerr << "\t%" << it.first << " -> %" << it.second << "\n";

  }

  std::cerr << "\n";

}

bool SSARewriter::GenerateSSAReplacements(BasicBlock* bb) {

#if SSA_REWRITE_DEBUGGING_LEVEL > 1

  std::cerr << "Generating SSA replacements for block: " << bb->id() << "\n";

  std::cerr << bb->PrettyPrint(SPV_BINARY_TO_TEXT_OPTION_FRIENDLY_NAMES)

            << "\n";

#endif

  for (auto& inst : *bb) {

    auto opcode = inst.opcode();

    if (opcode == spv::Op::OpStore || opcode == spv::Op::OpVariable) {

      ProcessStore(&inst, bb);

    } else if (inst.opcode() == spv::Op::OpLoad) {

      if (!ProcessLoad(&inst, bb)) {

        return false;

      }

    }

  }

  // Seal |bb|. This means that all the stores in it have been scanned and

  // it's ready to feed them into its successors.

  SealBlock(bb);

#if SSA_REWRITE_DEBUGGING_LEVEL > 1

  PrintPhiCandidates();

  PrintReplacementTable();

  std::cerr << "\n\n";

#endif

  return true;

}

uint32_t SSARewriter::GetReplacement(std::pair<uint32_t, uint32_t> repl) {

  uint32_t val_id = repl.second;

  auto it = load_replacement_.find(val_id);

  while (it != load_replacement_.end()) {

    val_id = it->second;

    it = load_replacement_.find(val_id);

  }

  return val_id;

}

uint32_t SSARewriter::GetPhiArgument(const PhiCandidate* phi_candidate,

                                     uint32_t ix) {

  assert(phi_candidate->IsReady() &&

         "Tried to get the final argument from an incomplete/trivial Phi");

  uint32_t arg_id = phi_candidate->phi_args()[ix];

  while (arg_id != 0) {

    PhiCandidate* phi_user = GetPhiCandidate(arg_id);

    if (phi_user == nullptr || phi_user->IsReady()) {

      // If the argument is not a Phi or it's a Phi candidate ready to be

      // emitted, return it.

      return arg_id;

    }

    arg_id = phi_user->copy_of();

  }

  if (pass_->context()->id_overflow()) {

    return 0;

  }

  assert(false &&

         "No Phi candidates in the copy-of chain are ready to be generated");

  return 0;

}

bool SSARewriter::ApplyReplacements() {

  bool modified = false;

#if SSA_REWRITE_DEBUGGING_LEVEL > 2

  std::cerr << "\n\nApplying replacement decisions to IR\n\n";

  PrintPhiCandidates();

  PrintReplacementTable();

  std::cerr << "\n\n";

#endif

  // Add Phi instructions from completed Phi candidates.

  std::vector<Instruction*> generated_phis;

  for (const PhiCandidate* phi_candidate : phis_to_generate_) {

#if SSA_REWRITE_DEBUGGING_LEVEL > 2

    std::cerr << "Phi candidate: " << phi_candidate->PrettyPrint(pass_->cfg())

              << "\n";

#endif

    assert(phi_candidate->is_complete() &&

           "Tried to instantiate a Phi instruction from an incomplete Phi "

           "candidate");

    auto* local_var = pass_->get_def_use_mgr()->GetDef(phi_candidate->var_id());

    // Build the vector of operands for the new OpPhi instruction.

    uint32_t type_id = pass_->GetPointeeTypeId(local_var);

    std::vector<Operand> phi_operands;

    uint32_t arg_ix = 0;

    std::unordered_map<uint32_t, uint32_t> already_seen;

    for (uint32_t pred_label : pass_->cfg()->preds(phi_candidate->bb()->id())) {

      uint32_t op_val_id = GetPhiArgument(phi_candidate, arg_ix++);

      if (already_seen.count(pred_label) == 0) {

        phi_operands.push_back(

            {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {op_val_id}});

        phi_operands.push_back(

            {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {pred_label}});

        already_seen[pred_label] = op_val_id;

      } else {

        // It is possible that there are two edges from the same parent block.

        // Since the OpPhi can have only one entry for each parent, we have to

        // make sure the two edges are consistent with each other.

        assert(already_seen[pred_label] == op_val_id &&

               "Inconsistent value for duplicate edges.");

      }

    }

    // Generate a new OpPhi instruction and insert it in its basic

    // block.

    std::unique_ptr<Instruction> phi_inst(

        new Instruction(pass_->context(), spv::Op::OpPhi, type_id,

                        phi_candidate->result_id(), phi_operands));

    generated_phis.push_back(phi_inst.get());

    pass_->get_def_use_mgr()->AnalyzeInstDef(&*phi_inst);

    pass_->context()->set_instr_block(&*phi_inst, phi_candidate->bb());

    auto insert_it = phi_candidate->bb()->begin();

    insert_it = insert_it.InsertBefore(std::move(phi_inst));

    pass_->context()->get_decoration_mgr()->CloneDecorations(

        phi_candidate->var_id(), phi_candidate->result_id(),

        {spv::Decoration::RelaxedPrecision});

    // Add DebugValue for the new OpPhi instruction.

    insert_it->SetDebugScope(local_var->GetDebugScope());

    pass_->context()->get_debug_info_mgr()->AddDebugValueForVariable(

        &*insert_it, phi_candidate->var_id(), phi_candidate->result_id(),

        &*insert_it);

    modified = true;

  }

  // Scan uses for all inserted Phi instructions. Do this separately from the

  // registration of the Phi instruction itself to avoid trying to analyze

  // uses of Phi instructions that have not been registered yet.

  for (Instruction* phi_inst : generated_phis) {

    pass_->get_def_use_mgr()->AnalyzeInstUse(&*phi_inst);

  }

#if SSA_REWRITE_DEBUGGING_LEVEL > 1

  std::cerr << "\n\nReplacing the result of load instructions with the "

               "corresponding SSA id\n\n";

#endif

  // Apply replacements from the load replacement table.

  for (auto& repl : load_replacement_) {

    uint32_t load_id = repl.first;

    uint32_t val_id = GetReplacement(repl);

    Instruction* load_inst =

        pass_->context()->get_def_use_mgr()->GetDef(load_id);

#if SSA_REWRITE_DEBUGGING_LEVEL > 2

    std::cerr << "\t"

              << load_inst->PrettyPrint(

                     SPV_BINARY_TO_TEXT_OPTION_FRIENDLY_NAMES)

              << "  (%" << load_id << " -> %" << val_id << ")\n";

#endif

    // Remove the load instruction and replace all the uses of this load's

    // result with |val_id|.  Kill any names or decorates using the load's

    // result before replacing to prevent incorrect replacement in those

    // instructions.

    pass_->context()->KillNamesAndDecorates(load_id);

    pass_->context()->ReplaceAllUsesWith(load_id, val_id);

    pass_->context()->KillInst(load_inst);

    modified = true;

  }

  return modified;

}

void SSARewriter::FinalizePhiCandidate(PhiCandidate* phi_candidate) {

  assert(phi_candidate->phi_args().size() > 0 &&

         "Phi candidate should have arguments");

  uint32_t ix = 0;

  for (uint32_t pred : pass_->cfg()->preds(phi_candidate->bb()->id())) {

    BasicBlock* pred_bb = pass_->cfg()->block(pred);

    uint32_t& arg_id = phi_candidate->phi_args()[ix++];

    if (arg_id == 0) {

      // If |pred_bb| is still not sealed, it means it's unreachable. In this

      // case, we just use Undef as an argument.

      arg_id = IsBlockSealed(pred_bb)

                   ? GetReachingDef(phi_candidate->var_id(), pred_bb)

                   : pass_->GetUndefVal(phi_candidate->var_id());

    }

  }

  // This candidate is now completed.

  phi_candidate->MarkComplete();

  // If |phi_candidate| is not trivial, add it to the list of Phis to

  // generate.

  if (TryRemoveTrivialPhi(phi_candidate) == phi_candidate->result_id()) {

    // If we could not remove |phi_candidate|, it means that it is complete

    // and not trivial. Add it to the list of Phis to generate.

    assert(!phi_candidate->copy_of() && "A completed Phi cannot be trivial.");

    phis_to_generate_.push_back(phi_candidate);

  }

}

void SSARewriter::FinalizePhiCandidates() {

#if SSA_REWRITE_DEBUGGING_LEVEL > 1

  std::cerr << "Finalizing Phi candidates:\n\n";

  PrintPhiCandidates();

  std::cerr << "\n";

#endif

  // Now, complete the collected candidates.

  while (incomplete_phis_.size() > 0) {

    PhiCandidate* phi_candidate = incomplete_phis_.front();

    incomplete_phis_.pop();

    FinalizePhiCandidate(phi_candidate);

  }

}

Pass::Status SSARewriter::RewriteFunctionIntoSSA(Function* fp) {

#if SSA_REWRITE_DEBUGGING_LEVEL > 0

  std::cerr << "Function before SSA rewrite:\n"

            << fp->PrettyPrint(0) << "\n\n\n";

#endif

  // Collect variables that can be converted into SSA IDs.

  pass_->CollectTargetVars(fp);

  // Generate all the SSA replacements and Phi candidates. This will

  // generate incomplete and trivial Phis.

  bool succeeded = pass_->cfg()->WhileEachBlockInReversePostOrder(

      fp->entry().get(), [this](BasicBlock* bb) {

        if (!GenerateSSAReplacements(bb)) {

          return false;

        }

        return true;

      });

  if (!succeeded || pass_->context()->id_overflow()) {

    return Pass::Status::Failure;

  }

  // Remove trivial Phis and add arguments to incomplete Phis.

  FinalizePhiCandidates();

  if (pass_->context()->id_overflow()) {

    return Pass::Status::Failure;

  }

  // Finally, apply all the replacements in the IR.

  bool modified = ApplyReplacements();

  if (pass_->context()->id_overflow()) {

    return Pass::Status::Failure;

  }

#if SSA_REWRITE_DEBUGGING_LEVEL > 0

  std::cerr << "\n\n\nFunction after SSA rewrite:\n"

            << fp->PrettyPrint(0) << "\n";

#endif

  return modified ? Pass::Status::SuccessWithChange

                  : Pass::Status::SuccessWithoutChange;

}

Pass::Status SSARewritePass::Process() {

  Status status = Status::SuccessWithoutChange;

  for (auto& fn : *get_module()) {

    if (fn.IsDeclaration()) {

      continue;

    }

    status =

        CombineStatus(status, SSARewriter(this).RewriteFunctionIntoSSA(&fn));

    if (status == Status::Failure || context()->id_overflow()) {

      return Status::Failure;

    }

    // Kill DebugDeclares for target variables.

    for (auto var_id : seen_target_vars_) {

      context()->get_debug_info_mgr()->KillDebugDeclares(var_id);

    }

  }

  return status;

}

}  // namespace opt

}  // namespace spvtools