// 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.

#include "source/opt/vector_dce.h"

#include <utility>

namespace spvtools {
namespace opt {
namespace {

const uint32_t kExtractCompositeIdInIdx = 0;
const uint32_t kInsertObjectIdInIdx = 0;
const uint32_t kInsertCompositeIdInIdx = 1;

}  // namespace

Pass::Status VectorDCE::Process() {
  bool modified = false;
  for (Function& function : *get_module()) {
    modified |= VectorDCEFunction(&function);
  }
  return (modified ? Status::SuccessWithChange : Status::SuccessWithoutChange);
}

bool VectorDCE::VectorDCEFunction(Function* function) {
  LiveComponentMap live_components;
  FindLiveComponents(function, &live_components);
  return RewriteInstructions(function, live_components);
}

void VectorDCE::FindLiveComponents(Function* function,
                                   LiveComponentMap* live_components) {
  std::vector<WorkListItem> work_list;

  // Prime the work list.  We will assume that any instruction that does
  // not result in a vector is live.
  //
  // Extending to structures and matrices is not as straight forward because of
  // the nesting.  We cannot simply us a bit vector to keep track of which
  // components are live because of arbitrary nesting of structs.
  function->ForEachInst(
      [&work_list, this, live_components](Instruction* current_inst) {
        if (current_inst->IsCommonDebugInstr()) {
          return;
        }
        if (!HasVectorOrScalarResult(current_inst) ||
            !context()->IsCombinatorInstruction(current_inst)) {
          MarkUsesAsLive(current_inst, all_components_live_, live_components,
                         &work_list);
        }
      });

  // Process the work list propagating liveness.
  for (uint32_t i = 0; i < work_list.size(); i++) {
    WorkListItem current_item = work_list[i];
    Instruction* current_inst = current_item.instruction;

    switch (current_inst->opcode()) {
      case SpvOpCompositeExtract:
        MarkExtractUseAsLive(current_inst, current_item.components,
                             live_components, &work_list);
        break;
      case SpvOpCompositeInsert:
        MarkInsertUsesAsLive(current_item, live_components, &work_list);
        break;
      case SpvOpVectorShuffle:
        MarkVectorShuffleUsesAsLive(current_item, live_components, &work_list);
        break;
      case SpvOpCompositeConstruct:
        MarkCompositeContructUsesAsLive(current_item, live_components,
                                        &work_list);
        break;
      default:
        if (current_inst->IsScalarizable()) {
          MarkUsesAsLive(current_inst, current_item.components, live_components,
                         &work_list);
        } else {
          MarkUsesAsLive(current_inst, all_components_live_, live_components,
                         &work_list);
        }
        break;
    }
  }
}

void VectorDCE::MarkExtractUseAsLive(const Instruction* current_inst,
                                     const utils::BitVector& live_elements,
                                     LiveComponentMap* live_components,
                                     std::vector<WorkListItem>* work_list) {
  analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
  uint32_t operand_id =
      current_inst->GetSingleWordInOperand(kExtractCompositeIdInIdx);
  Instruction* operand_inst = def_use_mgr->GetDef(operand_id);

  if (HasVectorOrScalarResult(operand_inst)) {
    WorkListItem new_item;
    new_item.instruction = operand_inst;
    if (current_inst->NumInOperands() < 2) {
      new_item.components = live_elements;
    } else {
      new_item.components.Set(current_inst->GetSingleWordInOperand(1));
    }
    AddItemToWorkListIfNeeded(new_item, live_components, work_list);
  }
}

void VectorDCE::MarkInsertUsesAsLive(
    const VectorDCE::WorkListItem& current_item,
    LiveComponentMap* live_components,
    std::vector<VectorDCE::WorkListItem>* work_list) {
  analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();

  if (current_item.instruction->NumInOperands() > 2) {
    uint32_t insert_position =
        current_item.instruction->GetSingleWordInOperand(2);

    // Add the elements of the composite object that are used.
    uint32_t operand_id = current_item.instruction->GetSingleWordInOperand(
        kInsertCompositeIdInIdx);
    Instruction* operand_inst = def_use_mgr->GetDef(operand_id);

    WorkListItem new_item;
    new_item.instruction = operand_inst;
    new_item.components = current_item.components;
    new_item.components.Clear(insert_position);

    AddItemToWorkListIfNeeded(new_item, live_components, work_list);

    // Add the element being inserted if it is used.
    if (current_item.components.Get(insert_position)) {
      uint32_t obj_operand_id =
          current_item.instruction->GetSingleWordInOperand(
              kInsertObjectIdInIdx);
      Instruction* obj_operand_inst = def_use_mgr->GetDef(obj_operand_id);
      WorkListItem new_item_for_obj;
      new_item_for_obj.instruction = obj_operand_inst;
      new_item_for_obj.components.Set(0);
      AddItemToWorkListIfNeeded(new_item_for_obj, live_components, work_list);
    }
  } else {
    // If there are no indices, then this is a copy of the object being
    // inserted.
    uint32_t object_id =
        current_item.instruction->GetSingleWordInOperand(kInsertObjectIdInIdx);
    Instruction* object_inst = def_use_mgr->GetDef(object_id);

    WorkListItem new_item;
    new_item.instruction = object_inst;
    new_item.components = current_item.components;
    AddItemToWorkListIfNeeded(new_item, live_components, work_list);
  }
}

void VectorDCE::MarkVectorShuffleUsesAsLive(
    const WorkListItem& current_item,
    VectorDCE::LiveComponentMap* live_components,
    std::vector<WorkListItem>* work_list) {
  analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();

  WorkListItem first_operand;
  first_operand.instruction =
      def_use_mgr->GetDef(current_item.instruction->GetSingleWordInOperand(0));
  WorkListItem second_operand;
  second_operand.instruction =
      def_use_mgr->GetDef(current_item.instruction->GetSingleWordInOperand(1));

  analysis::TypeManager* type_mgr = context()->get_type_mgr();
  analysis::Vector* first_type =
      type_mgr->GetType(first_operand.instruction->type_id())->AsVector();
  uint32_t size_of_first_operand = first_type->element_count();

  for (uint32_t in_op = 2; in_op < current_item.instruction->NumInOperands();
       ++in_op) {
    uint32_t index = current_item.instruction->GetSingleWordInOperand(in_op);
    if (current_item.components.Get(in_op - 2)) {
      if (index < size_of_first_operand) {
        first_operand.components.Set(index);
      } else {
        second_operand.components.Set(index - size_of_first_operand);
      }
    }
  }

  AddItemToWorkListIfNeeded(first_operand, live_components, work_list);
  AddItemToWorkListIfNeeded(second_operand, live_components, work_list);
}

void VectorDCE::MarkCompositeContructUsesAsLive(
    VectorDCE::WorkListItem work_item,
    VectorDCE::LiveComponentMap* live_components,
    std::vector<VectorDCE::WorkListItem>* work_list) {
  analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
  analysis::TypeManager* type_mgr = context()->get_type_mgr();

  uint32_t current_component = 0;
  Instruction* current_inst = work_item.instruction;
  uint32_t num_in_operands = current_inst->NumInOperands();
  for (uint32_t i = 0; i < num_in_operands; ++i) {
    uint32_t id = current_inst->GetSingleWordInOperand(i);
    Instruction* op_inst = def_use_mgr->GetDef(id);

    if (HasScalarResult(op_inst)) {
      WorkListItem new_work_item;
      new_work_item.instruction = op_inst;
      if (work_item.components.Get(current_component)) {
        new_work_item.components.Set(0);
      }
      AddItemToWorkListIfNeeded(new_work_item, live_components, work_list);
      current_component++;
    } else {
      assert(HasVectorResult(op_inst));
      WorkListItem new_work_item;
      new_work_item.instruction = op_inst;
      uint32_t op_vector_size =
          type_mgr->GetType(op_inst->type_id())->AsVector()->element_count();

      for (uint32_t op_vector_idx = 0; op_vector_idx < op_vector_size;
           op_vector_idx++, current_component++) {
        if (work_item.components.Get(current_component)) {
          new_work_item.components.Set(op_vector_idx);
        }
      }
      AddItemToWorkListIfNeeded(new_work_item, live_components, work_list);
    }
  }
}

void VectorDCE::MarkUsesAsLive(
    Instruction* current_inst, const utils::BitVector& live_elements,
    LiveComponentMap* live_components,
    std::vector<VectorDCE::WorkListItem>* work_list) {
  analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();

  current_inst->ForEachInId([&work_list, &live_elements, this, live_components,
                             def_use_mgr](uint32_t* operand_id) {
    Instruction* operand_inst = def_use_mgr->GetDef(*operand_id);

    if (HasVectorResult(operand_inst)) {
      WorkListItem new_item;
      new_item.instruction = operand_inst;
      new_item.components = live_elements;
      AddItemToWorkListIfNeeded(new_item, live_components, work_list);
    } else if (HasScalarResult(operand_inst)) {
      WorkListItem new_item;
      new_item.instruction = operand_inst;
      new_item.components.Set(0);
      AddItemToWorkListIfNeeded(new_item, live_components, work_list);
    }
  });
}

bool VectorDCE::HasVectorOrScalarResult(const Instruction* inst) const {
  return HasScalarResult(inst) || HasVectorResult(inst);
}

bool VectorDCE::HasVectorResult(const Instruction* inst) const {
  analysis::TypeManager* type_mgr = context()->get_type_mgr();
  if (inst->type_id() == 0) {
    return false;
  }

  const analysis::Type* current_type = type_mgr->GetType(inst->type_id());
  switch (current_type->kind()) {
    case analysis::Type::kVector:
      return true;
    default:
      return false;
  }
}

bool VectorDCE::HasScalarResult(const Instruction* inst) const {
  analysis::TypeManager* type_mgr = context()->get_type_mgr();
  if (inst->type_id() == 0) {
    return false;
  }

  const analysis::Type* current_type = type_mgr->GetType(inst->type_id());
  switch (current_type->kind()) {
    case analysis::Type::kBool:
    case analysis::Type::kInteger:
    case analysis::Type::kFloat:
      return true;
    default:
      return false;
  }
}

bool VectorDCE::RewriteInstructions(
    Function* function, const VectorDCE::LiveComponentMap& live_components) {
  bool modified = false;

  // Kill DebugValue in the middle of the instruction iteration will result
  // in accessing a dangling pointer. We keep dead DebugValue instructions
  // in |dead_dbg_value| to kill them once after the iteration.
  std::vector<Instruction*> dead_dbg_value;

  function->ForEachInst([&modified, this, live_components,
                         &dead_dbg_value](Instruction* current_inst) {
    if (!context()->IsCombinatorInstruction(current_inst)) {
      return;
    }

    auto live_component = live_components.find(current_inst->result_id());
    if (live_component == live_components.end()) {
      // If this instruction is not in live_components then it does not
      // produce a vector, or it is never referenced and ADCE will remove
      // it.  No point in trying to differentiate.
      return;
    }

    // If no element in the current instruction is used replace it with an
    // OpUndef.
    if (live_component->second.Empty()) {
      modified = true;
      MarkDebugValueUsesAsDead(current_inst, &dead_dbg_value);
      uint32_t undef_id = this->Type2Undef(current_inst->type_id());
      context()->KillNamesAndDecorates(current_inst);
      context()->ReplaceAllUsesWith(current_inst->result_id(), undef_id);
      context()->KillInst(current_inst);
      return;
    }

    switch (current_inst->opcode()) {
      case SpvOpCompositeInsert:
        modified |= RewriteInsertInstruction(
            current_inst, live_component->second, &dead_dbg_value);
        break;
      case SpvOpCompositeConstruct:
        // TODO: The members that are not live can be replaced by an undef
        // or constant. This will remove uses of those values, and possibly
        // create opportunities for ADCE.
        break;
      default:
        // Do nothing.
        break;
    }
  });
  for (auto* i : dead_dbg_value) context()->KillInst(i);
  return modified;
}

bool VectorDCE::RewriteInsertInstruction(
    Instruction* current_inst, const utils::BitVector& live_components,
    std::vector<Instruction*>* dead_dbg_value) {
  // If the value being inserted is not live, then we can skip the insert.

  if (current_inst->NumInOperands() == 2) {
    // If there are no indices, then this is the same as a copy.
    context()->KillNamesAndDecorates(current_inst->result_id());
    uint32_t object_id =
        current_inst->GetSingleWordInOperand(kInsertObjectIdInIdx);
    context()->ReplaceAllUsesWith(current_inst->result_id(), object_id);
    return true;
  }

  uint32_t insert_index = current_inst->GetSingleWordInOperand(2);
  if (!live_components.Get(insert_index)) {
    MarkDebugValueUsesAsDead(current_inst, dead_dbg_value);
    context()->KillNamesAndDecorates(current_inst->result_id());
    uint32_t composite_id =
        current_inst->GetSingleWordInOperand(kInsertCompositeIdInIdx);
    context()->ReplaceAllUsesWith(current_inst->result_id(), composite_id);
    return true;
  }

  // If the values already in the composite are not used, then replace it with
  // an undef.
  utils::BitVector temp = live_components;
  temp.Clear(insert_index);
  if (temp.Empty()) {
    context()->ForgetUses(current_inst);
    uint32_t undef_id = Type2Undef(current_inst->type_id());
    current_inst->SetInOperand(kInsertCompositeIdInIdx, {undef_id});
    context()->AnalyzeUses(current_inst);
    return true;
  }

  return false;
}

void VectorDCE::MarkDebugValueUsesAsDead(
    Instruction* composite, std::vector<Instruction*>* dead_dbg_value) {
  context()->get_def_use_mgr()->ForEachUser(
      composite, [&dead_dbg_value](Instruction* use) {
        if (use->GetCommonDebugOpcode() == CommonDebugInfoDebugValue)
          dead_dbg_value->push_back(use);
      });
}

void VectorDCE::AddItemToWorkListIfNeeded(
    WorkListItem work_item, VectorDCE::LiveComponentMap* live_components,
    std::vector<WorkListItem>* work_list) {
  Instruction* current_inst = work_item.instruction;
  auto it = live_components->find(current_inst->result_id());
  if (it == live_components->end()) {
    live_components->emplace(
        std::make_pair(current_inst->result_id(), work_item.components));
    work_list->emplace_back(work_item);
  } else {
    if (it->second.Or(work_item.components)) {
      work_list->emplace_back(work_item);
    }
  }
}

}  // namespace opt
}  // namespace spvtools