// 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/reduce/remove_unused_struct_member_reduction_opportunity_finder.h"

#include <map>
#include <set>

#include "source/reduce/remove_struct_member_reduction_opportunity.h"

namespace spvtools {
namespace reduce {

std::vector<std::unique_ptr<ReductionOpportunity>>
RemoveUnusedStructMemberReductionOpportunityFinder::GetAvailableOpportunities(
    opt::IRContext* context, uint32_t target_function) const {
  if (target_function) {
    // Removing an unused struct member is a global change, as struct types are
    // global.  We thus do not consider such opportunities if we are targeting
    // a specific function.
    return {};
  }

  std::vector<std::unique_ptr<ReductionOpportunity>> result;

  // We track those struct members that are never accessed.  We do this by
  // associating a member index to all the structs that have this member index
  // but do not use it.  This representation is designed to allow reduction
  // opportunities to be provided in a useful manner, so that opportunities
  // associated with the same struct are unlikely to be adjacent.
  std::map<uint32_t, std::set<opt::Instruction*>> unused_member_to_structs;

  // Consider every struct type in the module.
  for (auto& type_or_value : context->types_values()) {
    if (type_or_value.opcode() != SpvOpTypeStruct) {
      continue;
    }

    // Initially, we assume that *every* member of the struct is unused.  We
    // then refine this based on observed uses.
    std::set<uint32_t> unused_members;
    for (uint32_t i = 0; i < type_or_value.NumInOperands(); i++) {
      unused_members.insert(i);
    }

    // A separate reduction pass deals with removal of names.  If a struct
    // member is still named, we treat it as being used.
    context->get_def_use_mgr()->ForEachUse(
        &type_or_value,
        [&unused_members](opt::Instruction* user, uint32_t /*operand_index*/) {
          switch (user->opcode()) {
            case SpvOpMemberName:
              unused_members.erase(user->GetSingleWordInOperand(1));
              break;
            default:
              break;
          }
        });

    for (uint32_t member : unused_members) {
      if (!unused_member_to_structs.count(member)) {
        unused_member_to_structs.insert(
            {member, std::set<opt::Instruction*>()});
      }
      unused_member_to_structs.at(member).insert(&type_or_value);
    }
  }

  // We now go through every instruction that might index into a struct, and
  // refine our tracking of which struct members are used based on the struct
  // indexing we observe.  We cannot just go through all uses of a struct type
  // because the type is not necessarily even referenced, e.g. when walking
  // arrays of structs.
  for (auto& function : *context->module()) {
    for (auto& block : function) {
      for (auto& inst : block) {
        switch (inst.opcode()) {
          // For each indexing operation we observe, we invoke a helper to
          // remove from our map those struct indices that are found to be used.
          // The way the helper is invoked depends on whether the instruction
          // uses literal or id indices, and the offset into the instruction's
          // input operands from which index operands are provided.
          case SpvOpAccessChain:
          case SpvOpInBoundsAccessChain: {
            auto composite_type_id =
                context->get_def_use_mgr()
                    ->GetDef(context->get_def_use_mgr()
                                 ->GetDef(inst.GetSingleWordInOperand(0))
                                 ->type_id())
                    ->GetSingleWordInOperand(1);
            MarkAccessedMembersAsUsed(context, composite_type_id, 1, false,
                                      inst, &unused_member_to_structs);
          } break;
          case SpvOpPtrAccessChain:
          case SpvOpInBoundsPtrAccessChain: {
            auto composite_type_id =
                context->get_def_use_mgr()
                    ->GetDef(context->get_def_use_mgr()
                                 ->GetDef(inst.GetSingleWordInOperand(1))
                                 ->type_id())
                    ->GetSingleWordInOperand(1);
            MarkAccessedMembersAsUsed(context, composite_type_id, 2, false,
                                      inst, &unused_member_to_structs);
          } break;
          case SpvOpCompositeExtract: {
            auto composite_type_id =
                context->get_def_use_mgr()
                    ->GetDef(inst.GetSingleWordInOperand(0))
                    ->type_id();
            MarkAccessedMembersAsUsed(context, composite_type_id, 1, true, inst,
                                      &unused_member_to_structs);
          } break;
          case SpvOpCompositeInsert: {
            auto composite_type_id =
                context->get_def_use_mgr()
                    ->GetDef(inst.GetSingleWordInOperand(1))
                    ->type_id();
            MarkAccessedMembersAsUsed(context, composite_type_id, 2, true, inst,
                                      &unused_member_to_structs);
          } break;
          default:
            break;
        }
      }
    }
  }

  // We now know those struct indices that are unsed, and we make a reduction
  // opportunity for each of them. By mapping each relevant member index to the
  // structs in which it is unsed, we will group all opportunities to remove
  // member k of a struct (for some k) together.  This reduces the likelihood
  // that opportunities to remove members from the same struct will be adjacent,
  // which is good because such opportunities mutually disable one another.
  for (auto& entry : unused_member_to_structs) {
    for (auto struct_type : entry.second) {
      result.push_back(MakeUnique<RemoveStructMemberReductionOpportunity>(
          struct_type, entry.first));
    }
  }
  return result;
}

void RemoveUnusedStructMemberReductionOpportunityFinder::
    MarkAccessedMembersAsUsed(
        opt::IRContext* context, uint32_t composite_type_id,
        uint32_t first_index_in_operand, bool literal_indices,
        const opt::Instruction& composite_access_instruction,
        std::map<uint32_t, std::set<opt::Instruction*>>*
            unused_member_to_structs) const {
  uint32_t next_type = composite_type_id;
  for (uint32_t i = first_index_in_operand;
       i < composite_access_instruction.NumInOperands(); i++) {
    auto type_inst = context->get_def_use_mgr()->GetDef(next_type);
    switch (type_inst->opcode()) {
      case SpvOpTypeArray:
      case SpvOpTypeMatrix:
      case SpvOpTypeRuntimeArray:
      case SpvOpTypeVector:
        next_type = type_inst->GetSingleWordInOperand(0);
        break;
      case SpvOpTypeStruct: {
        uint32_t index_operand =
            composite_access_instruction.GetSingleWordInOperand(i);
        uint32_t member = literal_indices ? index_operand
                                          : context->get_def_use_mgr()
                                                ->GetDef(index_operand)
                                                ->GetSingleWordInOperand(0);
        // Remove the struct type from the struct types associated with this
        // member index, but only if a set of struct types is known to be
        // associated with this member index.
        if (unused_member_to_structs->count(member)) {
          unused_member_to_structs->at(member).erase(type_inst);
        }
        next_type = type_inst->GetSingleWordInOperand(member);
      } break;
      default:
        assert(0 && "Unknown composite type.");
        break;
    }
  }
}

std::string RemoveUnusedStructMemberReductionOpportunityFinder::GetName()
    const {
  return "RemoveUnusedStructMemberReductionOpportunityFinder";
}

}  // namespace reduce
}  // namespace spvtools