// Copyright (c) 2017 Google Inc.
//
// 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 "dead_variable_elimination.h"

#include "reflect.h"

namespace spvtools {
namespace opt {

// This optimization removes global variables that are not needed because they
// are definitely not accessed.
Pass::Status DeadVariableElimination::Process(spvtools::ir::Module* module) {
  // The algorithm will compute the reference count for every global variable.
  // Anything with a reference count of 0 will then be deleted.  For variables
  // that might have references that are not explicit in this module, we use the
  // value kMustKeep as the reference count.
  InitializeProcessing(module);

  //  Decoration manager to help organize decorations.
  analysis::DecorationManager decoration_manager(module);

  std::vector<uint32_t> ids_to_remove;

  // Get the reference count for all of the global OpVariable instructions.
  for (auto& inst : module->types_values()) {
    if (inst.opcode() != SpvOp::SpvOpVariable) {
      continue;
    }

    size_t count = 0;
    uint32_t result_id = inst.result_id();

    // Check the linkage.  If it is exported, it could be reference somewhere
    // else, so we must keep the variable around.
    decoration_manager.ForEachDecoration(
        result_id, SpvDecorationLinkageAttributes,
        [&count](const ir::Instruction& linkage_instruction) {
          uint32_t last_operand = linkage_instruction.NumOperands() - 1;
          if (linkage_instruction.GetSingleWordOperand(last_operand) ==
              SpvLinkageTypeExport) {
            count = kMustKeep;
          }
        });

    if (count != kMustKeep) {
      // If we don't have to keep the instruction for other reasons, then look
      // at the uses and count the number of real references.
      if (analysis::UseList* uses = get_def_use_mgr()->GetUses(result_id)) {
        count = std::count_if(
            uses->begin(), uses->end(), [](const analysis::Use& u) {
              return (!ir::IsAnnotationInst(u.inst->opcode()) &&
                  u.inst->opcode() != SpvOpName);
            });
      }
    }
    reference_count_[result_id] = count;
    if (count == 0) {
      ids_to_remove.push_back(result_id);
    }
  }

  // Remove all of the variables that have a reference count of 0.
  bool modified = false;
  if (!ids_to_remove.empty()) {
    modified = true;
    for (auto result_id : ids_to_remove) {
      DeleteVariable(result_id);
    }
  }
  return (modified ? Status::SuccessWithChange : Status::SuccessWithoutChange);
}

void DeadVariableElimination::DeleteVariable(uint32_t result_id) {
  ir::Instruction* inst = get_def_use_mgr()->GetDef(result_id);
  assert(inst->opcode() == SpvOpVariable &&
      "Should not be trying to delete anything other than an OpVariable.");

  // Look for an initializer that references another variable.  We need to know
  // if that variable can be deleted after the reference is removed.
  if (inst->NumOperands() == 4) {
    ir::Instruction* initializer =
        get_def_use_mgr()->GetDef(inst->GetSingleWordOperand(3));

    // TODO: Handle OpSpecConstantOP which might be defined in terms of other
    // variables.  Will probably require a unified dead code pass that does all
    // instruction types.  (Issue 906)
    if (initializer->opcode() == SpvOpVariable) {
      uint32_t initializer_id = initializer->result_id();
      size_t& count = reference_count_[initializer_id];
      if (count != kMustKeep) {
        --count;
      }

      if (count == 0) {
        DeleteVariable(initializer_id);
      }
    }
  }
  this->KillNamesAndDecorates(result_id);
  get_def_use_mgr()->KillDef(result_id);
}
}  // namespace opt
}  // namespace spvtools