// Copyright (c) 2020 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.

#include "source/opt/debug_info_manager.h"

#include <cassert>

#include "source/opt/ir_context.h"

// Constants for OpenCL.DebugInfo.100 extension instructions.

static const uint32_t kOpLineOperandLineIndex = 1;
static const uint32_t kLineOperandIndexDebugFunction = 7;
static const uint32_t kLineOperandIndexDebugLexicalBlock = 5;
static const uint32_t kDebugFunctionOperandFunctionIndex = 13;
static const uint32_t kDebugFunctionOperandParentIndex = 9;
static const uint32_t kDebugTypeCompositeOperandParentIndex = 9;
static const uint32_t kDebugLexicalBlockOperandParentIndex = 7;
static const uint32_t kDebugInlinedAtOperandInlinedIndex = 6;
static const uint32_t kDebugExpressOperandOperationIndex = 4;
static const uint32_t kDebugDeclareOperandLocalVariableIndex = 4;
static const uint32_t kDebugDeclareOperandVariableIndex = 5;
static const uint32_t kDebugValueOperandLocalVariableIndex = 4;
static const uint32_t kDebugValueOperandExpressionIndex = 6;
static const uint32_t kDebugValueOperandIndexesIndex = 7;
static const uint32_t kDebugOperationOperandOperationIndex = 4;
static const uint32_t kOpVariableOperandStorageClassIndex = 2;
static const uint32_t kDebugLocalVariableOperandParentIndex = 9;
static const uint32_t kExtInstInstructionInIdx = 1;
static const uint32_t kDebugGlobalVariableOperandFlagsIndex = 12;
static const uint32_t kDebugLocalVariableOperandFlagsIndex = 10;
static const uint32_t kDebugLocalVariableOperandArgNumberIndex = 11;

namespace spvtools {
namespace opt {
namespace analysis {
namespace {

void SetInlinedOperand(Instruction* dbg_inlined_at, uint32_t inlined_operand) {
  assert(dbg_inlined_at);
  assert(dbg_inlined_at->GetOpenCL100DebugOpcode() ==
         OpenCLDebugInfo100DebugInlinedAt);
  if (dbg_inlined_at->NumOperands() <= kDebugInlinedAtOperandInlinedIndex) {
    dbg_inlined_at->AddOperand(
        {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {inlined_operand}});
  } else {
    dbg_inlined_at->SetOperand(kDebugInlinedAtOperandInlinedIndex,
                               {inlined_operand});
  }
}

uint32_t GetInlinedOperand(Instruction* dbg_inlined_at) {
  assert(dbg_inlined_at);
  assert(dbg_inlined_at->GetOpenCL100DebugOpcode() ==
         OpenCLDebugInfo100DebugInlinedAt);
  if (dbg_inlined_at->NumOperands() <= kDebugInlinedAtOperandInlinedIndex)
    return kNoInlinedAt;
  return dbg_inlined_at->GetSingleWordOperand(
      kDebugInlinedAtOperandInlinedIndex);
}

bool IsEmptyDebugExpression(Instruction* instr) {
  return instr->GetOpenCL100DebugOpcode() ==
             OpenCLDebugInfo100DebugExpression &&
         instr->NumOperands() == kDebugExpressOperandOperationIndex;
}

}  // namespace

DebugInfoManager::DebugInfoManager(IRContext* c) : context_(c) {
  AnalyzeDebugInsts(*c->module());
}

Instruction* DebugInfoManager::GetDbgInst(uint32_t id) {
  auto dbg_inst_it = id_to_dbg_inst_.find(id);
  return dbg_inst_it == id_to_dbg_inst_.end() ? nullptr : dbg_inst_it->second;
}

void DebugInfoManager::RegisterDbgInst(Instruction* inst) {
  assert(
      inst->NumInOperands() != 0 &&
      context()->get_feature_mgr()->GetExtInstImportId_OpenCL100DebugInfo() ==
          inst->GetInOperand(0).words[0] &&
      "Given instruction is not a debug instruction");
  id_to_dbg_inst_[inst->result_id()] = inst;
}

void DebugInfoManager::RegisterDbgFunction(Instruction* inst) {
  assert(inst->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugFunction &&
         "inst is not a DebugFunction");
  auto fn_id = inst->GetSingleWordOperand(kDebugFunctionOperandFunctionIndex);
  // Do not register function that has been optimized away
  auto fn_inst = GetDbgInst(fn_id);
  if (fn_inst != nullptr) {
    assert(GetDbgInst(fn_id)->GetOpenCL100DebugOpcode() ==
           OpenCLDebugInfo100DebugInfoNone);
    return;
  }
  assert(
      fn_id_to_dbg_fn_.find(fn_id) == fn_id_to_dbg_fn_.end() &&
      "Register DebugFunction for a function that already has DebugFunction");
  fn_id_to_dbg_fn_[fn_id] = inst;
}

void DebugInfoManager::RegisterDbgDeclare(uint32_t var_id,
                                          Instruction* dbg_declare) {
  assert(dbg_declare->GetOpenCL100DebugOpcode() ==
             OpenCLDebugInfo100DebugDeclare ||
         dbg_declare->GetOpenCL100DebugOpcode() ==
             OpenCLDebugInfo100DebugValue);
  auto dbg_decl_itr = var_id_to_dbg_decl_.find(var_id);
  if (dbg_decl_itr == var_id_to_dbg_decl_.end()) {
    var_id_to_dbg_decl_[var_id] = {dbg_declare};
  } else {
    dbg_decl_itr->second.insert(dbg_declare);
  }
}

uint32_t DebugInfoManager::CreateDebugInlinedAt(const Instruction* line,
                                                const DebugScope& scope) {
  if (context()->get_feature_mgr()->GetExtInstImportId_OpenCL100DebugInfo() ==
      0)
    return kNoInlinedAt;

  uint32_t line_number = 0;
  if (line == nullptr) {
    auto* lexical_scope_inst = GetDbgInst(scope.GetLexicalScope());
    if (lexical_scope_inst == nullptr) return kNoInlinedAt;
    OpenCLDebugInfo100Instructions debug_opcode =
        lexical_scope_inst->GetOpenCL100DebugOpcode();
    switch (debug_opcode) {
      case OpenCLDebugInfo100DebugFunction:
        line_number = lexical_scope_inst->GetSingleWordOperand(
            kLineOperandIndexDebugFunction);
        break;
      case OpenCLDebugInfo100DebugLexicalBlock:
        line_number = lexical_scope_inst->GetSingleWordOperand(
            kLineOperandIndexDebugLexicalBlock);
        break;
      case OpenCLDebugInfo100DebugTypeComposite:
      case OpenCLDebugInfo100DebugCompilationUnit:
        assert(false &&
               "DebugTypeComposite and DebugCompilationUnit are lexical "
               "scopes, but we inline functions into a function or a block "
               "of a function, not into a struct/class or a global scope.");
        break;
      default:
        assert(false &&
               "Unreachable. a debug extension instruction for a "
               "lexical scope must be DebugFunction, DebugTypeComposite, "
               "DebugLexicalBlock, or DebugCompilationUnit.");
        break;
    }
  } else {
    line_number = line->GetSingleWordOperand(kOpLineOperandLineIndex);
  }

  uint32_t result_id = context()->TakeNextId();
  std::unique_ptr<Instruction> inlined_at(new Instruction(
      context(), SpvOpExtInst, context()->get_type_mgr()->GetVoidTypeId(),
      result_id,
      {
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID,
           {context()
                ->get_feature_mgr()
                ->GetExtInstImportId_OpenCL100DebugInfo()}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_EXTENSION_INSTRUCTION_NUMBER,
           {static_cast<uint32_t>(OpenCLDebugInfo100DebugInlinedAt)}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER, {line_number}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {scope.GetLexicalScope()}},
      }));
  // |scope| already has DebugInlinedAt. We put the existing DebugInlinedAt
  // into the Inlined operand of this new DebugInlinedAt.
  if (scope.GetInlinedAt() != kNoInlinedAt) {
    inlined_at->AddOperand(
        {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {scope.GetInlinedAt()}});
  }
  RegisterDbgInst(inlined_at.get());
  if (context()->AreAnalysesValid(IRContext::Analysis::kAnalysisDefUse))
    context()->get_def_use_mgr()->AnalyzeInstDefUse(inlined_at.get());
  context()->module()->AddExtInstDebugInfo(std::move(inlined_at));
  return result_id;
}

DebugScope DebugInfoManager::BuildDebugScope(
    const DebugScope& callee_instr_scope,
    DebugInlinedAtContext* inlined_at_ctx) {
  return DebugScope(callee_instr_scope.GetLexicalScope(),
                    BuildDebugInlinedAtChain(callee_instr_scope.GetInlinedAt(),
                                             inlined_at_ctx));
}

uint32_t DebugInfoManager::BuildDebugInlinedAtChain(
    uint32_t callee_inlined_at, DebugInlinedAtContext* inlined_at_ctx) {
  if (inlined_at_ctx->GetScopeOfCallInstruction().GetLexicalScope() ==
      kNoDebugScope)
    return kNoInlinedAt;

  // Reuse the already generated DebugInlinedAt chain if exists.
  uint32_t already_generated_chain_head_id =
      inlined_at_ctx->GetDebugInlinedAtChain(callee_inlined_at);
  if (already_generated_chain_head_id != kNoInlinedAt) {
    return already_generated_chain_head_id;
  }

  const uint32_t new_dbg_inlined_at_id =
      CreateDebugInlinedAt(inlined_at_ctx->GetLineOfCallInstruction(),
                           inlined_at_ctx->GetScopeOfCallInstruction());
  if (new_dbg_inlined_at_id == kNoInlinedAt) return kNoInlinedAt;

  if (callee_inlined_at == kNoInlinedAt) {
    inlined_at_ctx->SetDebugInlinedAtChain(kNoInlinedAt, new_dbg_inlined_at_id);
    return new_dbg_inlined_at_id;
  }

  uint32_t chain_head_id = kNoInlinedAt;
  uint32_t chain_iter_id = callee_inlined_at;
  Instruction* last_inlined_at_in_chain = nullptr;
  do {
    Instruction* new_inlined_at_in_chain = CloneDebugInlinedAt(
        chain_iter_id, /* insert_before */ last_inlined_at_in_chain);
    assert(new_inlined_at_in_chain != nullptr);

    // Set DebugInlinedAt of the new scope as the head of the chain.
    if (chain_head_id == kNoInlinedAt)
      chain_head_id = new_inlined_at_in_chain->result_id();

    // Previous DebugInlinedAt of the chain must point to the new
    // DebugInlinedAt as its Inlined operand to build a recursive
    // chain.
    if (last_inlined_at_in_chain != nullptr) {
      SetInlinedOperand(last_inlined_at_in_chain,
                        new_inlined_at_in_chain->result_id());
    }
    last_inlined_at_in_chain = new_inlined_at_in_chain;

    chain_iter_id = GetInlinedOperand(new_inlined_at_in_chain);
  } while (chain_iter_id != kNoInlinedAt);

  // Put |new_dbg_inlined_at_id| into the end of the chain.
  SetInlinedOperand(last_inlined_at_in_chain, new_dbg_inlined_at_id);

  // Keep the new chain information that will be reused it.
  inlined_at_ctx->SetDebugInlinedAtChain(callee_inlined_at, chain_head_id);
  return chain_head_id;
}

Instruction* DebugInfoManager::GetDebugOperationWithDeref() {
  if (deref_operation_ != nullptr) return deref_operation_;

  uint32_t result_id = context()->TakeNextId();
  std::unique_ptr<Instruction> deref_operation(new Instruction(
      context(), SpvOpExtInst, context()->get_type_mgr()->GetVoidTypeId(),
      result_id,
      {
          {SPV_OPERAND_TYPE_ID,
           {context()
                ->get_feature_mgr()
                ->GetExtInstImportId_OpenCL100DebugInfo()}},
          {SPV_OPERAND_TYPE_EXTENSION_INSTRUCTION_NUMBER,
           {static_cast<uint32_t>(OpenCLDebugInfo100DebugOperation)}},
          {SPV_OPERAND_TYPE_CLDEBUG100_DEBUG_OPERATION,
           {static_cast<uint32_t>(OpenCLDebugInfo100Deref)}},
      }));

  // Add to the front of |ext_inst_debuginfo_|.
  deref_operation_ =
      context()->module()->ext_inst_debuginfo_begin()->InsertBefore(
          std::move(deref_operation));

  RegisterDbgInst(deref_operation_);
  if (context()->AreAnalysesValid(IRContext::Analysis::kAnalysisDefUse))
    context()->get_def_use_mgr()->AnalyzeInstDefUse(deref_operation_);
  return deref_operation_;
}

Instruction* DebugInfoManager::DerefDebugExpression(Instruction* dbg_expr) {
  assert(dbg_expr->GetOpenCL100DebugOpcode() ==
         OpenCLDebugInfo100DebugExpression);
  std::unique_ptr<Instruction> deref_expr(dbg_expr->Clone(context()));
  deref_expr->SetResultId(context()->TakeNextId());
  deref_expr->InsertOperand(
      kDebugExpressOperandOperationIndex,
      {SPV_OPERAND_TYPE_ID, {GetDebugOperationWithDeref()->result_id()}});
  auto* deref_expr_instr =
      context()->ext_inst_debuginfo_end()->InsertBefore(std::move(deref_expr));
  AnalyzeDebugInst(deref_expr_instr);
  if (context()->AreAnalysesValid(IRContext::Analysis::kAnalysisDefUse))
    context()->get_def_use_mgr()->AnalyzeInstDefUse(deref_expr_instr);
  return deref_expr_instr;
}

Instruction* DebugInfoManager::GetDebugInfoNone() {
  if (debug_info_none_inst_ != nullptr) return debug_info_none_inst_;

  uint32_t result_id = context()->TakeNextId();
  std::unique_ptr<Instruction> dbg_info_none_inst(new Instruction(
      context(), SpvOpExtInst, context()->get_type_mgr()->GetVoidTypeId(),
      result_id,
      {
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID,
           {context()
                ->get_feature_mgr()
                ->GetExtInstImportId_OpenCL100DebugInfo()}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_EXTENSION_INSTRUCTION_NUMBER,
           {static_cast<uint32_t>(OpenCLDebugInfo100DebugInfoNone)}},
      }));

  // Add to the front of |ext_inst_debuginfo_|.
  debug_info_none_inst_ =
      context()->module()->ext_inst_debuginfo_begin()->InsertBefore(
          std::move(dbg_info_none_inst));

  RegisterDbgInst(debug_info_none_inst_);
  if (context()->AreAnalysesValid(IRContext::Analysis::kAnalysisDefUse))
    context()->get_def_use_mgr()->AnalyzeInstDefUse(debug_info_none_inst_);
  return debug_info_none_inst_;
}

Instruction* DebugInfoManager::GetEmptyDebugExpression() {
  if (empty_debug_expr_inst_ != nullptr) return empty_debug_expr_inst_;

  uint32_t result_id = context()->TakeNextId();
  std::unique_ptr<Instruction> empty_debug_expr(new Instruction(
      context(), SpvOpExtInst, context()->get_type_mgr()->GetVoidTypeId(),
      result_id,
      {
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID,
           {context()
                ->get_feature_mgr()
                ->GetExtInstImportId_OpenCL100DebugInfo()}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_EXTENSION_INSTRUCTION_NUMBER,
           {static_cast<uint32_t>(OpenCLDebugInfo100DebugExpression)}},
      }));

  // Add to the front of |ext_inst_debuginfo_|.
  empty_debug_expr_inst_ =
      context()->module()->ext_inst_debuginfo_begin()->InsertBefore(
          std::move(empty_debug_expr));

  RegisterDbgInst(empty_debug_expr_inst_);
  if (context()->AreAnalysesValid(IRContext::Analysis::kAnalysisDefUse))
    context()->get_def_use_mgr()->AnalyzeInstDefUse(empty_debug_expr_inst_);
  return empty_debug_expr_inst_;
}

Instruction* DebugInfoManager::GetDebugInlinedAt(uint32_t dbg_inlined_at_id) {
  auto* inlined_at = GetDbgInst(dbg_inlined_at_id);
  if (inlined_at == nullptr) return nullptr;
  if (inlined_at->GetOpenCL100DebugOpcode() !=
      OpenCLDebugInfo100DebugInlinedAt) {
    return nullptr;
  }
  return inlined_at;
}

Instruction* DebugInfoManager::CloneDebugInlinedAt(uint32_t clone_inlined_at_id,
                                                   Instruction* insert_before) {
  auto* inlined_at = GetDebugInlinedAt(clone_inlined_at_id);
  if (inlined_at == nullptr) return nullptr;
  std::unique_ptr<Instruction> new_inlined_at(inlined_at->Clone(context()));
  new_inlined_at->SetResultId(context()->TakeNextId());
  RegisterDbgInst(new_inlined_at.get());
  if (context()->AreAnalysesValid(IRContext::Analysis::kAnalysisDefUse))
    context()->get_def_use_mgr()->AnalyzeInstDefUse(new_inlined_at.get());
  if (insert_before != nullptr)
    return insert_before->InsertBefore(std::move(new_inlined_at));
  return context()->module()->ext_inst_debuginfo_end()->InsertBefore(
      std::move(new_inlined_at));
}

bool DebugInfoManager::IsVariableDebugDeclared(uint32_t variable_id) {
  auto dbg_decl_itr = var_id_to_dbg_decl_.find(variable_id);
  return dbg_decl_itr != var_id_to_dbg_decl_.end();
}

void DebugInfoManager::KillDebugDeclares(uint32_t variable_id) {
  auto dbg_decl_itr = var_id_to_dbg_decl_.find(variable_id);
  if (dbg_decl_itr != var_id_to_dbg_decl_.end()) {
    // We intentionally copy the list of DebugDeclare instructions because
    // context()->KillInst(dbg_decl) will update |var_id_to_dbg_decl_|. If we
    // directly use |dbg_decl_itr->second|, it accesses a dangling pointer.
    auto copy_dbg_decls = dbg_decl_itr->second;

    for (auto* dbg_decl : copy_dbg_decls) {
      context()->KillInst(dbg_decl);
    }
    var_id_to_dbg_decl_.erase(dbg_decl_itr);
  }
}

uint32_t DebugInfoManager::GetParentScope(uint32_t child_scope) {
  auto dbg_scope_itr = id_to_dbg_inst_.find(child_scope);
  assert(dbg_scope_itr != id_to_dbg_inst_.end());
  OpenCLDebugInfo100Instructions debug_opcode =
      dbg_scope_itr->second->GetOpenCL100DebugOpcode();
  uint32_t parent_scope = kNoDebugScope;
  switch (debug_opcode) {
    case OpenCLDebugInfo100DebugFunction:
      parent_scope = dbg_scope_itr->second->GetSingleWordOperand(
          kDebugFunctionOperandParentIndex);
      break;
    case OpenCLDebugInfo100DebugLexicalBlock:
      parent_scope = dbg_scope_itr->second->GetSingleWordOperand(
          kDebugLexicalBlockOperandParentIndex);
      break;
    case OpenCLDebugInfo100DebugTypeComposite:
      parent_scope = dbg_scope_itr->second->GetSingleWordOperand(
          kDebugTypeCompositeOperandParentIndex);
      break;
    case OpenCLDebugInfo100DebugCompilationUnit:
      // DebugCompilationUnit does not have a parent scope.
      break;
    default:
      assert(false &&
             "Unreachable. A debug scope instruction must be "
             "DebugFunction, DebugTypeComposite, DebugLexicalBlock, "
             "or DebugCompilationUnit.");
      break;
  }
  return parent_scope;
}

bool DebugInfoManager::IsAncestorOfScope(uint32_t scope, uint32_t ancestor) {
  uint32_t ancestor_scope_itr = scope;
  while (ancestor_scope_itr != kNoDebugScope) {
    if (ancestor == ancestor_scope_itr) return true;
    ancestor_scope_itr = GetParentScope(ancestor_scope_itr);
  }
  return false;
}

Instruction* DebugInfoManager::GetDebugLocalVariableFromDeclare(
    Instruction* dbg_declare) {
  assert(dbg_declare);
  uint32_t dbg_local_var_id =
      dbg_declare->GetSingleWordOperand(kDebugDeclareOperandLocalVariableIndex);
  auto dbg_local_var_itr = id_to_dbg_inst_.find(dbg_local_var_id);
  assert(dbg_local_var_itr != id_to_dbg_inst_.end());
  return dbg_local_var_itr->second;
}

bool DebugInfoManager::IsFunctionParameter(Instruction* dbg_local_var) const {
  // If a DebugLocalVariable has ArgNumber operand, it is a function parameter.
  return dbg_local_var->NumOperands() >
         kDebugLocalVariableOperandArgNumberIndex;
}

bool DebugInfoManager::IsLocalVariableVisibleToInstr(Instruction* dbg_local_var,
                                                     uint32_t instr_scope_id) {
  if (instr_scope_id == kNoDebugScope) return false;

  uint32_t decl_scope_id = dbg_local_var->GetSingleWordOperand(
      kDebugLocalVariableOperandParentIndex);

  // If the scope of DebugDeclare is an ancestor scope of the instruction's
  // scope, the local variable is visible to the instruction.
  return IsAncestorOfScope(instr_scope_id, decl_scope_id);
}

Instruction* DebugInfoManager::AddDebugValueWithIndex(
    uint32_t dbg_local_var_id, uint32_t value_id, uint32_t expr_id,
    uint32_t index_id, Instruction* insert_before) {
  uint32_t result_id = context()->TakeNextId();
  if (!result_id) return nullptr;
  std::unique_ptr<Instruction> new_dbg_value(new Instruction(
      context(), SpvOpExtInst, context()->get_type_mgr()->GetVoidTypeId(),
      result_id,
      {
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID,
           {context()
                ->get_feature_mgr()
                ->GetExtInstImportId_OpenCL100DebugInfo()}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_EXTENSION_INSTRUCTION_NUMBER,
           {static_cast<uint32_t>(OpenCLDebugInfo100DebugValue)}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {dbg_local_var_id}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {value_id}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID,
           {expr_id == 0 ? GetEmptyDebugExpression()->result_id() : expr_id}},
      }));
  if (index_id) {
    new_dbg_value->AddOperand(
        {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {index_id}});
  }

  Instruction* added_dbg_value =
      insert_before->InsertBefore(std::move(new_dbg_value));
  AnalyzeDebugInst(added_dbg_value);
  if (context()->AreAnalysesValid(IRContext::Analysis::kAnalysisDefUse))
    context()->get_def_use_mgr()->AnalyzeInstDefUse(added_dbg_value);
  if (context()->AreAnalysesValid(
          IRContext::Analysis::kAnalysisInstrToBlockMapping)) {
    auto insert_blk = context()->get_instr_block(insert_before);
    context()->set_instr_block(added_dbg_value, insert_blk);
  }
  return added_dbg_value;
}

void DebugInfoManager::AddDebugValueIfVarDeclIsVisible(
    Instruction* scope_and_line, uint32_t variable_id, uint32_t value_id,
    Instruction* insert_pos) {
  auto dbg_decl_itr = var_id_to_dbg_decl_.find(variable_id);
  if (dbg_decl_itr == var_id_to_dbg_decl_.end()) return;

  uint32_t instr_scope_id = scope_and_line->GetDebugScope().GetLexicalScope();
  for (auto* dbg_decl_or_val : dbg_decl_itr->second) {
    // If it declares a function parameter, the store instruction for the
    // function parameter can exist out of the function parameter's scope
    // because of the function inlining. We always add DebugValue for a
    // function parameter next to the DebugDeclare regardless of the scope.
    auto* dbg_local_var = GetDebugLocalVariableFromDeclare(dbg_decl_or_val);
    bool is_function_param = IsFunctionParameter(dbg_local_var);
    if (!is_function_param &&
        !IsLocalVariableVisibleToInstr(dbg_local_var, instr_scope_id))
      continue;

    // Avoid inserting the new DebugValue between OpPhi or OpVariable
    // instructions.
    Instruction* insert_before = is_function_param ? dbg_decl_or_val->NextNode()
                                                   : insert_pos->NextNode();
    while (insert_before->opcode() == SpvOpPhi ||
           insert_before->opcode() == SpvOpVariable) {
      insert_before = insert_before->NextNode();
    }

    uint32_t index_id = 0;
    if (dbg_decl_or_val->NumOperands() > kDebugValueOperandIndexesIndex) {
      index_id =
          dbg_decl_or_val->GetSingleWordOperand(kDebugValueOperandIndexesIndex);
    }

    Instruction* added_dbg_value =
        AddDebugValueWithIndex(dbg_decl_or_val->GetSingleWordOperand(
                                   kDebugValueOperandLocalVariableIndex),
                               value_id, 0, index_id, insert_before);
    assert(added_dbg_value != nullptr);
    added_dbg_value->UpdateDebugInfoFrom(is_function_param ? dbg_decl_or_val
                                                           : scope_and_line);
    AnalyzeDebugInst(added_dbg_value);
  }
}

uint32_t DebugInfoManager::GetVariableIdOfDebugValueUsedForDeclare(
    Instruction* inst) {
  if (inst->GetOpenCL100DebugOpcode() != OpenCLDebugInfo100DebugValue) return 0;

  auto* expr =
      GetDbgInst(inst->GetSingleWordOperand(kDebugValueOperandExpressionIndex));
  if (expr == nullptr) return 0;
  if (expr->NumOperands() != kDebugExpressOperandOperationIndex + 1) return 0;

  auto* operation = GetDbgInst(
      expr->GetSingleWordOperand(kDebugExpressOperandOperationIndex));
  if (operation == nullptr) return 0;
  if (operation->GetSingleWordOperand(kDebugOperationOperandOperationIndex) !=
      OpenCLDebugInfo100Deref) {
    return 0;
  }

  uint32_t var_id =
      inst->GetSingleWordOperand(kDebugDeclareOperandVariableIndex);
  if (!context()->AreAnalysesValid(IRContext::Analysis::kAnalysisDefUse)) {
    assert(false &&
           "Checking a DebugValue can be used for declare needs DefUseManager");
    return 0;
  }

  auto* var = context()->get_def_use_mgr()->GetDef(var_id);
  if (var->opcode() == SpvOpVariable &&
      SpvStorageClass(var->GetSingleWordOperand(
          kOpVariableOperandStorageClassIndex)) == SpvStorageClassFunction) {
    return var_id;
  }
  return 0;
}

bool DebugInfoManager::IsDebugDeclare(Instruction* instr) {
  if (!instr->IsOpenCL100DebugInstr()) return false;
  return instr->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugDeclare ||
         GetVariableIdOfDebugValueUsedForDeclare(instr) != 0;
}

void DebugInfoManager::ReplaceAllUsesInDebugScopeWithPredicate(
    uint32_t before, uint32_t after,
    const std::function<bool(Instruction*)>& predicate) {
  auto scope_id_to_users_itr = scope_id_to_users_.find(before);
  if (scope_id_to_users_itr != scope_id_to_users_.end()) {
    for (Instruction* inst : scope_id_to_users_itr->second) {
      if (predicate(inst)) inst->UpdateLexicalScope(after);
    }
    scope_id_to_users_[after] = scope_id_to_users_itr->second;
    scope_id_to_users_.erase(scope_id_to_users_itr);
  }
  auto inlinedat_id_to_users_itr = inlinedat_id_to_users_.find(before);
  if (inlinedat_id_to_users_itr != inlinedat_id_to_users_.end()) {
    for (Instruction* inst : inlinedat_id_to_users_itr->second) {
      if (predicate(inst)) inst->UpdateDebugInlinedAt(after);
    }
    inlinedat_id_to_users_[after] = inlinedat_id_to_users_itr->second;
    inlinedat_id_to_users_.erase(inlinedat_id_to_users_itr);
  }
}

void DebugInfoManager::ClearDebugScopeAndInlinedAtUses(Instruction* inst) {
  auto scope_id_to_users_itr = scope_id_to_users_.find(inst->result_id());
  if (scope_id_to_users_itr != scope_id_to_users_.end()) {
    scope_id_to_users_.erase(scope_id_to_users_itr);
  }
  auto inlinedat_id_to_users_itr =
      inlinedat_id_to_users_.find(inst->result_id());
  if (inlinedat_id_to_users_itr != inlinedat_id_to_users_.end()) {
    inlinedat_id_to_users_.erase(inlinedat_id_to_users_itr);
  }
}

void DebugInfoManager::AnalyzeDebugInst(Instruction* inst) {
  if (inst->GetDebugScope().GetLexicalScope() != kNoDebugScope) {
    auto& users = scope_id_to_users_[inst->GetDebugScope().GetLexicalScope()];
    users.insert(inst);
  }
  if (inst->GetDebugInlinedAt() != kNoInlinedAt) {
    auto& users = inlinedat_id_to_users_[inst->GetDebugInlinedAt()];
    users.insert(inst);
  }

  if (!inst->IsOpenCL100DebugInstr()) return;

  RegisterDbgInst(inst);

  if (inst->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugFunction) {
    assert(GetDebugFunction(inst->GetSingleWordOperand(
               kDebugFunctionOperandFunctionIndex)) == nullptr &&
           "Two DebugFunction instruction exists for a single OpFunction.");
    RegisterDbgFunction(inst);
  }

  if (deref_operation_ == nullptr &&
      inst->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugOperation &&
      inst->GetSingleWordOperand(kDebugOperationOperandOperationIndex) ==
          OpenCLDebugInfo100Deref) {
    deref_operation_ = inst;
  }

  if (debug_info_none_inst_ == nullptr &&
      inst->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugInfoNone) {
    debug_info_none_inst_ = inst;
  }

  if (empty_debug_expr_inst_ == nullptr && IsEmptyDebugExpression(inst)) {
    empty_debug_expr_inst_ = inst;
  }

  if (inst->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugDeclare) {
    uint32_t var_id =
        inst->GetSingleWordOperand(kDebugDeclareOperandVariableIndex);
    RegisterDbgDeclare(var_id, inst);
  }

  if (uint32_t var_id = GetVariableIdOfDebugValueUsedForDeclare(inst)) {
    RegisterDbgDeclare(var_id, inst);
  }
}

void DebugInfoManager::ConvertDebugGlobalToLocalVariable(
    Instruction* dbg_global_var, Instruction* local_var) {
  if (dbg_global_var->GetOpenCL100DebugOpcode() !=
      OpenCLDebugInfo100DebugGlobalVariable) {
    return;
  }
  assert(local_var->opcode() == SpvOpVariable ||
         local_var->opcode() == SpvOpFunctionParameter);

  // Convert |dbg_global_var| to DebugLocalVariable
  dbg_global_var->SetInOperand(kExtInstInstructionInIdx,
                               {OpenCLDebugInfo100DebugLocalVariable});
  auto flags = dbg_global_var->GetSingleWordOperand(
      kDebugGlobalVariableOperandFlagsIndex);
  for (uint32_t i = dbg_global_var->NumInOperands() - 1;
       i >= kDebugLocalVariableOperandFlagsIndex; --i) {
    dbg_global_var->RemoveOperand(i);
  }
  dbg_global_var->SetOperand(kDebugLocalVariableOperandFlagsIndex, {flags});
  context()->ForgetUses(dbg_global_var);
  context()->AnalyzeUses(dbg_global_var);

  // Create a DebugDeclare
  std::unique_ptr<Instruction> new_dbg_decl(new Instruction(
      context(), SpvOpExtInst, context()->get_type_mgr()->GetVoidTypeId(),
      context()->TakeNextId(),
      {
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID,
           {context()
                ->get_feature_mgr()
                ->GetExtInstImportId_OpenCL100DebugInfo()}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_EXTENSION_INSTRUCTION_NUMBER,
           {static_cast<uint32_t>(OpenCLDebugInfo100DebugDeclare)}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID,
           {dbg_global_var->result_id()}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID, {local_var->result_id()}},
          {spv_operand_type_t::SPV_OPERAND_TYPE_ID,
           {GetEmptyDebugExpression()->result_id()}},
      }));
  auto* added_dbg_decl =
      local_var->NextNode()->InsertBefore(std::move(new_dbg_decl));
  if (context()->AreAnalysesValid(IRContext::Analysis::kAnalysisDefUse))
    context()->get_def_use_mgr()->AnalyzeInstDefUse(added_dbg_decl);
  if (context()->AreAnalysesValid(
          IRContext::Analysis::kAnalysisInstrToBlockMapping)) {
    auto insert_blk = context()->get_instr_block(local_var);
    context()->set_instr_block(added_dbg_decl, insert_blk);
  }
}

void DebugInfoManager::AnalyzeDebugInsts(Module& module) {
  deref_operation_ = nullptr;
  debug_info_none_inst_ = nullptr;
  empty_debug_expr_inst_ = nullptr;
  module.ForEachInst([this](Instruction* cpi) { AnalyzeDebugInst(cpi); });

  // Move |empty_debug_expr_inst_| to the beginning of the debug instruction
  // list.
  if (empty_debug_expr_inst_ != nullptr &&
      empty_debug_expr_inst_->PreviousNode() != nullptr &&
      empty_debug_expr_inst_->PreviousNode()->IsOpenCL100DebugInstr()) {
    empty_debug_expr_inst_->InsertBefore(
        &*context()->module()->ext_inst_debuginfo_begin());
  }

  // Move |debug_info_none_inst_| to the beginning of the debug instruction
  // list.
  if (debug_info_none_inst_ != nullptr &&
      debug_info_none_inst_->PreviousNode() != nullptr &&
      debug_info_none_inst_->PreviousNode()->IsOpenCL100DebugInstr()) {
    debug_info_none_inst_->InsertBefore(
        &*context()->module()->ext_inst_debuginfo_begin());
  }
}

void DebugInfoManager::ClearDebugInfo(Instruction* instr) {
  auto scope_id_to_users_itr =
      scope_id_to_users_.find(instr->GetDebugScope().GetLexicalScope());
  if (scope_id_to_users_itr != scope_id_to_users_.end()) {
    scope_id_to_users_itr->second.erase(instr);
  }
  auto inlinedat_id_to_users_itr =
      inlinedat_id_to_users_.find(instr->GetDebugInlinedAt());
  if (inlinedat_id_to_users_itr != inlinedat_id_to_users_.end()) {
    inlinedat_id_to_users_itr->second.erase(instr);
  }

  if (instr == nullptr || !instr->IsOpenCL100DebugInstr()) {
    return;
  }

  id_to_dbg_inst_.erase(instr->result_id());

  if (instr->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugFunction) {
    auto fn_id =
        instr->GetSingleWordOperand(kDebugFunctionOperandFunctionIndex);
    fn_id_to_dbg_fn_.erase(fn_id);
  }

  if (instr->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugDeclare ||
      instr->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugValue) {
    auto var_or_value_id =
        instr->GetSingleWordOperand(kDebugDeclareOperandVariableIndex);
    auto dbg_decl_itr = var_id_to_dbg_decl_.find(var_or_value_id);
    if (dbg_decl_itr != var_id_to_dbg_decl_.end()) {
      dbg_decl_itr->second.erase(instr);
    }
  }

  if (deref_operation_ == instr) {
    deref_operation_ = nullptr;
    for (auto dbg_instr_itr = context()->module()->ext_inst_debuginfo_begin();
         dbg_instr_itr != context()->module()->ext_inst_debuginfo_end();
         ++dbg_instr_itr) {
      if (instr != &*dbg_instr_itr &&
          dbg_instr_itr->GetOpenCL100DebugOpcode() ==
              OpenCLDebugInfo100DebugOperation &&
          dbg_instr_itr->GetSingleWordOperand(
              kDebugOperationOperandOperationIndex) ==
              OpenCLDebugInfo100Deref) {
        deref_operation_ = &*dbg_instr_itr;
        break;
      }
    }
  }

  if (debug_info_none_inst_ == instr) {
    debug_info_none_inst_ = nullptr;
    for (auto dbg_instr_itr = context()->module()->ext_inst_debuginfo_begin();
         dbg_instr_itr != context()->module()->ext_inst_debuginfo_end();
         ++dbg_instr_itr) {
      if (instr != &*dbg_instr_itr &&
          dbg_instr_itr->GetOpenCL100DebugOpcode() ==
              OpenCLDebugInfo100DebugInfoNone) {
        debug_info_none_inst_ = &*dbg_instr_itr;
        break;
      }
    }
  }

  if (empty_debug_expr_inst_ == instr) {
    empty_debug_expr_inst_ = nullptr;
    for (auto dbg_instr_itr = context()->module()->ext_inst_debuginfo_begin();
         dbg_instr_itr != context()->module()->ext_inst_debuginfo_end();
         ++dbg_instr_itr) {
      if (instr != &*dbg_instr_itr && IsEmptyDebugExpression(&*dbg_instr_itr)) {
        empty_debug_expr_inst_ = &*dbg_instr_itr;
        break;
      }
    }
  }
}

}  // namespace analysis
}  // namespace opt
}  // namespace spvtools