// Copyright (c) 2019 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/eliminate_dead_members_pass.h"

#include "ir_builder.h"

#include "source/opt/ir_context.h"

namespace spvtools {

namespace opt {

namespace {

constexpr uint32_t kRemovedMember = 0xFFFFFFFF;

constexpr uint32_t kSpecConstOpOpcodeIdx = 0;

constexpr uint32_t kArrayElementTypeIdx = 0;

}  // namespace

Pass::Status EliminateDeadMembersPass::Process() {

  if (!context()->get_feature_mgr()->HasCapability(spv::Capability::Shader)) {

    return Status::SuccessWithoutChange;

  }

  FindLiveMembers();

  return RemoveDeadMembers();

}

void EliminateDeadMembersPass::FindLiveMembers() {

  // Until we have implemented the rewriting of OpSpecConsantOp instructions,

  // we have to mark them as fully used just to be safe.

  for (auto& inst : get_module()->types_values()) {

    if (inst.opcode() == spv::Op::OpSpecConstantOp) {

      switch (spv::Op(inst.GetSingleWordInOperand(kSpecConstOpOpcodeIdx))) {

        case spv::Op::OpCompositeExtract:

          MarkMembersAsLiveForExtract(&inst);

          break;

        case spv::Op::OpCompositeInsert:

          // Nothing specific to do.

          break;

        case spv::Op::OpAccessChain:

        case spv::Op::OpInBoundsAccessChain:

        case spv::Op::OpPtrAccessChain:

        case spv::Op::OpInBoundsPtrAccessChain:

          assert(false && "Not implemented yet.");

          break;

        default:

          break;

      }

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

      switch (spv::StorageClass(inst.GetSingleWordInOperand(0))) {

        case spv::StorageClass::Input:

        case spv::StorageClass::Output:

          MarkPointeeTypeAsFullUsed(inst.type_id());

          break;

        default:

          // Ignore structured buffers as layout(offset) qualifiers cannot be

          // applied to structure fields

          if (inst.IsVulkanStorageBufferVariable())

            MarkPointeeTypeAsFullUsed(inst.type_id());

          break;

      }

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

      uint32_t storage_class = inst.GetSingleWordInOperand(0);

      if (storage_class == uint32_t(spv::StorageClass::PhysicalStorageBuffer)) {

        MarkTypeAsFullyUsed(inst.GetSingleWordInOperand(1));

      }

    }

  }

  for (const Function& func : *get_module()) {

    FindLiveMembers(func);

  }

}

void EliminateDeadMembersPass::FindLiveMembers(const Function& function) {

  function.ForEachInst(

      [this](const Instruction* inst) { FindLiveMembers(inst); });

}

void EliminateDeadMembersPass::FindLiveMembers(const Instruction* inst) {

  switch (inst->opcode()) {

    case spv::Op::OpStore:

      MarkMembersAsLiveForStore(inst);

      break;

    case spv::Op::OpCopyMemory:

    case spv::Op::OpCopyMemorySized:

      MarkMembersAsLiveForCopyMemory(inst);

      break;

    case spv::Op::OpCompositeExtract:

      MarkMembersAsLiveForExtract(inst);

      break;

    case spv::Op::OpAccessChain:

    case spv::Op::OpInBoundsAccessChain:

    case spv::Op::OpPtrAccessChain:

    case spv::Op::OpInBoundsPtrAccessChain:

      MarkMembersAsLiveForAccessChain(inst);

      break;

    case spv::Op::OpReturnValue:

      // This should be an issue only if we are returning from the entry point.

      // However, for now I will keep it more conservative because functions are

      // often inlined leaving only the entry points.

      MarkOperandTypeAsFullyUsed(inst, 0);

      break;

    case spv::Op::OpArrayLength:

      MarkMembersAsLiveForArrayLength(inst);

      break;

    case spv::Op::OpLoad:

    case spv::Op::OpCompositeInsert:

    case spv::Op::OpCompositeConstruct:

      break;

    default:

      // This path is here for safety.  All instructions that can reference

      // structs in a function body should be handled above.  However, this will

      // keep the pass valid, but not optimal, as new instructions get added

      // or if something was missed.

      MarkStructOperandsAsFullyUsed(inst);

      break;

  }

}

void EliminateDeadMembersPass::MarkMembersAsLiveForStore(

    const Instruction* inst) {

  // We should only have to mark the members as live if the store is to

  // memory that is read outside of the shader.  Other passes can remove all

  // store to memory that is not visible outside of the shader, so we do not

  // complicate the code for now.

  assert(inst->opcode() == spv::Op::OpStore);

  uint32_t object_id = inst->GetSingleWordInOperand(1);

  Instruction* object_inst = context()->get_def_use_mgr()->GetDef(object_id);

  uint32_t object_type_id = object_inst->type_id();

  MarkTypeAsFullyUsed(object_type_id);

}

void EliminateDeadMembersPass::MarkTypeAsFullyUsed(uint32_t type_id) {

  Instruction* type_inst = get_def_use_mgr()->GetDef(type_id);

  assert(type_inst != nullptr);

  switch (type_inst->opcode()) {

    case spv::Op::OpTypeStruct:

      // Mark every member and its type as fully used.

      for (uint32_t i = 0; i < type_inst->NumInOperands(); ++i) {

        used_members_[type_id].insert(i);

        MarkTypeAsFullyUsed(type_inst->GetSingleWordInOperand(i));

      }

      break;

    case spv::Op::OpTypeArray:

    case spv::Op::OpTypeRuntimeArray:

      MarkTypeAsFullyUsed(

          type_inst->GetSingleWordInOperand(kArrayElementTypeIdx));

      break;

    default:

      break;

  }

}

void EliminateDeadMembersPass::MarkPointeeTypeAsFullUsed(uint32_t ptr_type_id) {

  Instruction* ptr_type_inst = get_def_use_mgr()->GetDef(ptr_type_id);

  assert(ptr_type_inst->opcode() == spv::Op::OpTypePointer);

  MarkTypeAsFullyUsed(ptr_type_inst->GetSingleWordInOperand(1));

}

void EliminateDeadMembersPass::MarkMembersAsLiveForCopyMemory(

    const Instruction* inst) {

  uint32_t target_id = inst->GetSingleWordInOperand(0);

  Instruction* target_inst = get_def_use_mgr()->GetDef(target_id);

  uint32_t pointer_type_id = target_inst->type_id();

  Instruction* pointer_type_inst = get_def_use_mgr()->GetDef(pointer_type_id);

  uint32_t type_id = pointer_type_inst->GetSingleWordInOperand(1);

  MarkTypeAsFullyUsed(type_id);

}

void EliminateDeadMembersPass::MarkMembersAsLiveForExtract(

    const Instruction* inst) {

  assert(inst->opcode() == spv::Op::OpCompositeExtract ||

         (inst->opcode() == spv::Op::OpSpecConstantOp &&

          spv::Op(inst->GetSingleWordInOperand(kSpecConstOpOpcodeIdx)) ==

              spv::Op::OpCompositeExtract));

  uint32_t first_operand =

      (inst->opcode() == spv::Op::OpSpecConstantOp ? 1 : 0);

  uint32_t composite_id = inst->GetSingleWordInOperand(first_operand);

  Instruction* composite_inst = get_def_use_mgr()->GetDef(composite_id);

  uint32_t type_id = composite_inst->type_id();

  for (uint32_t i = first_operand + 1; i < inst->NumInOperands(); ++i) {

    Instruction* type_inst = get_def_use_mgr()->GetDef(type_id);

    uint32_t member_idx = inst->GetSingleWordInOperand(i);

    switch (type_inst->opcode()) {

      case spv::Op::OpTypeStruct:

        used_members_[type_id].insert(member_idx);

        type_id = type_inst->GetSingleWordInOperand(member_idx);

        break;

      case spv::Op::OpTypeArray:

      case spv::Op::OpTypeRuntimeArray:

      case spv::Op::OpTypeVector:

      case spv::Op::OpTypeMatrix:

      case spv::Op::OpTypeCooperativeMatrixNV:

      case spv::Op::OpTypeCooperativeMatrixKHR:

      case spv::Op::OpTypeVectorIdEXT:

        type_id = type_inst->GetSingleWordInOperand(0);

        break;

      default:

        assert(false);

    }

  }

}

void EliminateDeadMembersPass::MarkMembersAsLiveForAccessChain(

    const Instruction* inst) {

  assert(inst->opcode() == spv::Op::OpAccessChain ||

         inst->opcode() == spv::Op::OpInBoundsAccessChain ||

         inst->opcode() == spv::Op::OpPtrAccessChain ||

         inst->opcode() == spv::Op::OpInBoundsPtrAccessChain);

  uint32_t pointer_id = inst->GetSingleWordInOperand(0);

  Instruction* pointer_inst = get_def_use_mgr()->GetDef(pointer_id);

  uint32_t pointer_type_id = pointer_inst->type_id();

  Instruction* pointer_type_inst = get_def_use_mgr()->GetDef(pointer_type_id);

  uint32_t type_id = pointer_type_inst->GetSingleWordInOperand(1);

  analysis::ConstantManager* const_mgr = context()->get_constant_mgr();

  // For a pointer access chain, we need to skip the |element| index.  It is not

  // a reference to the member of a struct, and it does not change the type.

  uint32_t i = (inst->opcode() == spv::Op::OpAccessChain ||

                        inst->opcode() == spv::Op::OpInBoundsAccessChain

                    ? 1

                    : 2);

  for (; i < inst->NumInOperands(); ++i) {

    Instruction* type_inst = get_def_use_mgr()->GetDef(type_id);

    switch (type_inst->opcode()) {

      case spv::Op::OpTypeStruct: {

        const analysis::IntConstant* member_idx =

            const_mgr->FindDeclaredConstant(inst->GetSingleWordInOperand(i))

                ->AsIntConstant();

        assert(member_idx);

        uint32_t index =

            static_cast<uint32_t>(member_idx->GetZeroExtendedValue());

        used_members_[type_id].insert(index);

        type_id = type_inst->GetSingleWordInOperand(index);

      } break;

      case spv::Op::OpTypeArray:

      case spv::Op::OpTypeRuntimeArray:

      case spv::Op::OpTypeVector:

      case spv::Op::OpTypeMatrix:

      case spv::Op::OpTypeCooperativeMatrixNV:

      case spv::Op::OpTypeCooperativeMatrixKHR:

      case spv::Op::OpTypeVectorIdEXT:

        type_id = type_inst->GetSingleWordInOperand(0);

        break;

      default:

        assert(false);

    }

  }

}

void EliminateDeadMembersPass::MarkOperandTypeAsFullyUsed(

    const Instruction* inst, uint32_t in_idx) {

  uint32_t op_id = inst->GetSingleWordInOperand(in_idx);

  Instruction* op_inst = get_def_use_mgr()->GetDef(op_id);

  MarkTypeAsFullyUsed(op_inst->type_id());

}

void EliminateDeadMembersPass::MarkMembersAsLiveForArrayLength(

    const Instruction* inst) {

  assert(inst->opcode() == spv::Op::OpArrayLength);

  uint32_t object_id = inst->GetSingleWordInOperand(0);

  Instruction* object_inst = get_def_use_mgr()->GetDef(object_id);

  uint32_t pointer_type_id = object_inst->type_id();

  Instruction* pointer_type_inst = get_def_use_mgr()->GetDef(pointer_type_id);

  uint32_t type_id = pointer_type_inst->GetSingleWordInOperand(1);

  used_members_[type_id].insert(inst->GetSingleWordInOperand(1));

}

Pass::Status EliminateDeadMembersPass::RemoveDeadMembers() {

  bool modified = false;

  // First update all of the OpTypeStruct instructions.

  get_module()->ForEachInst([&modified, this](Instruction* inst) {

    switch (inst->opcode()) {

      case spv::Op::OpTypeStruct:

        modified |= UpdateOpTypeStruct(inst);

        break;

      default:

        break;

    }

  });

  // Now update all of the instructions that reference the OpTypeStructs.

  Pass::Status status = Status::SuccessWithoutChange;

  bool success = get_module()->WhileEachInst([&modified, &status,

                                              this](Instruction* inst) {

    switch (inst->opcode()) {

      case spv::Op::OpMemberName:

        modified |= UpdateOpMemberNameOrDecorate(inst);

        break;

      case spv::Op::OpMemberDecorate:

        modified |= UpdateOpMemberNameOrDecorate(inst);

        break;

      case spv::Op::OpGroupMemberDecorate:

        modified |= UpdateOpGroupMemberDecorate(inst);

        break;

      case spv::Op::OpSpecConstantComposite:

      case spv::Op::OpConstantComposite:

      case spv::Op::OpCompositeConstruct:

        modified |= UpdateConstantComposite(inst);

        break;

      case spv::Op::OpAccessChain:

      case spv::Op::OpInBoundsAccessChain:

      case spv::Op::OpPtrAccessChain:

      case spv::Op::OpInBoundsPtrAccessChain: {

        Pass::Status s = UpdateAccessChain(inst);

        if (s == Status::Failure) {

          status = Status::Failure;

          return false;

        }

        if (s == Status::SuccessWithChange) {

          modified = true;

        }

        break;

      }

      case spv::Op::OpCompositeExtract:

        modified |= UpdateCompsiteExtract(inst);

        break;

      case spv::Op::OpCompositeInsert:

        modified |= UpdateCompositeInsert(inst);

        break;

      case spv::Op::OpArrayLength:

        modified |= UpdateOpArrayLength(inst);

        break;

      case spv::Op::OpSpecConstantOp:

        switch (spv::Op(inst->GetSingleWordInOperand(kSpecConstOpOpcodeIdx))) {

          case spv::Op::OpCompositeExtract:

            modified |= UpdateCompsiteExtract(inst);

            break;

          case spv::Op::OpCompositeInsert:

            modified |= UpdateCompositeInsert(inst);

            break;

          case spv::Op::OpAccessChain:

          case spv::Op::OpInBoundsAccessChain:

          case spv::Op::OpPtrAccessChain:

          case spv::Op::OpInBoundsPtrAccessChain:

            assert(false && "Not implemented yet.");

            break;

          default:

            break;

        }

        break;

      default:

        break;

    }

    return true;

  });

  if (!success || status == Status::Failure) {

    return Status::Failure;

  }

  return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;

}

bool EliminateDeadMembersPass::UpdateOpTypeStruct(Instruction* inst) {

  assert(inst->opcode() == spv::Op::OpTypeStruct);

  const auto& live_members = used_members_[inst->result_id()];

  if (live_members.size() == inst->NumInOperands()) {

    return false;

  }

  Instruction::OperandList new_operands;

  for (uint32_t idx : live_members) {

    new_operands.emplace_back(inst->GetInOperand(idx));

  }

  inst->SetInOperands(std::move(new_operands));

  context()->UpdateDefUse(inst);

  return true;

}

bool EliminateDeadMembersPass::UpdateOpMemberNameOrDecorate(Instruction* inst) {

  assert(inst->opcode() == spv::Op::OpMemberName ||

         inst->opcode() == spv::Op::OpMemberDecorate);

  uint32_t type_id = inst->GetSingleWordInOperand(0);

  auto live_members = used_members_.find(type_id);

  if (live_members == used_members_.end()) {

    return false;

  }

  uint32_t orig_member_idx = inst->GetSingleWordInOperand(1);

  uint32_t new_member_idx = GetNewMemberIndex(type_id, orig_member_idx);

  if (new_member_idx == kRemovedMember) {

    context()->KillInst(inst);

    return true;

  }

  if (new_member_idx == orig_member_idx) {

    return false;

  }

  inst->SetInOperand(1, {new_member_idx});

  return true;

}

bool EliminateDeadMembersPass::UpdateOpGroupMemberDecorate(Instruction* inst) {

  assert(inst->opcode() == spv::Op::OpGroupMemberDecorate);

  bool modified = false;

  Instruction::OperandList new_operands;

  new_operands.emplace_back(inst->GetInOperand(0));

  for (uint32_t i = 1; i < inst->NumInOperands(); i += 2) {

    uint32_t type_id = inst->GetSingleWordInOperand(i);

    uint32_t member_idx = inst->GetSingleWordInOperand(i + 1);

    uint32_t new_member_idx = GetNewMemberIndex(type_id, member_idx);

    if (new_member_idx == kRemovedMember) {

      modified = true;

      continue;

    }

    new_operands.emplace_back(inst->GetOperand(i));

    if (new_member_idx != member_idx) {

      new_operands.emplace_back(

          Operand({SPV_OPERAND_TYPE_LITERAL_INTEGER, {new_member_idx}}));

      modified = true;

    } else {

      new_operands.emplace_back(inst->GetOperand(i + 1));

    }

  }

  if (!modified) {

    return false;

  }

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

    context()->KillInst(inst);

    return true;

  }

  inst->SetInOperands(std::move(new_operands));

  context()->UpdateDefUse(inst);

  return true;

}

bool EliminateDeadMembersPass::UpdateConstantComposite(Instruction* inst) {

  assert(inst->opcode() == spv::Op::OpSpecConstantComposite ||

         inst->opcode() == spv::Op::OpConstantComposite ||

         inst->opcode() == spv::Op::OpCompositeConstruct);

  uint32_t type_id = inst->type_id();

  bool modified = false;

  Instruction::OperandList new_operands;

  for (uint32_t i = 0; i < inst->NumInOperands(); ++i) {

    uint32_t new_idx = GetNewMemberIndex(type_id, i);

    if (new_idx == kRemovedMember) {

      modified = true;

    } else {

      new_operands.emplace_back(inst->GetInOperand(i));

    }

  }

  inst->SetInOperands(std::move(new_operands));

  context()->UpdateDefUse(inst);

  return modified;

}

Pass::Status EliminateDeadMembersPass::UpdateAccessChain(Instruction* inst) {

  assert(inst->opcode() == spv::Op::OpAccessChain ||

         inst->opcode() == spv::Op::OpInBoundsAccessChain ||

         inst->opcode() == spv::Op::OpPtrAccessChain ||

         inst->opcode() == spv::Op::OpInBoundsPtrAccessChain);

  uint32_t pointer_id = inst->GetSingleWordInOperand(0);

  Instruction* pointer_inst = get_def_use_mgr()->GetDef(pointer_id);

  uint32_t pointer_type_id = pointer_inst->type_id();

  Instruction* pointer_type_inst = get_def_use_mgr()->GetDef(pointer_type_id);

  uint32_t type_id = pointer_type_inst->GetSingleWordInOperand(1);

  analysis::ConstantManager* const_mgr = context()->get_constant_mgr();

  Instruction::OperandList new_operands;

  bool modified = false;

  new_operands.emplace_back(inst->GetInOperand(0));

  // For pointer access chains we want to copy the element operand.

  if (inst->opcode() == spv::Op::OpPtrAccessChain ||

      inst->opcode() == spv::Op::OpInBoundsPtrAccessChain) {

    new_operands.emplace_back(inst->GetInOperand(1));

  }

  for (uint32_t i = static_cast<uint32_t>(new_operands.size());

       i < inst->NumInOperands(); ++i) {

    Instruction* type_inst = get_def_use_mgr()->GetDef(type_id);

    switch (type_inst->opcode()) {

      case spv::Op::OpTypeStruct: {

        const analysis::IntConstant* member_idx =

            const_mgr->FindDeclaredConstant(inst->GetSingleWordInOperand(i))

                ->AsIntConstant();

        assert(member_idx);

        uint32_t orig_member_idx =

            static_cast<uint32_t>(member_idx->GetZeroExtendedValue());

        uint32_t new_member_idx = GetNewMemberIndex(type_id, orig_member_idx);

        assert(new_member_idx != kRemovedMember);

        if (orig_member_idx != new_member_idx) {

          InstructionBuilder ir_builder(

              context(), inst,

              IRContext::kAnalysisDefUse |

                  IRContext::kAnalysisInstrToBlockMapping);

          Instruction* const_inst = ir_builder.GetUintConstant(new_member_idx);

          if (!const_inst) {

            return Status::Failure;

          }

          uint32_t const_id = const_inst->result_id();

          new_operands.emplace_back(Operand({SPV_OPERAND_TYPE_ID, {const_id}}));

          modified = true;

        } else {

          new_operands.emplace_back(inst->GetInOperand(i));

        }

        // The type will have already been rewritten, so use the new member

        // index.

        type_id = type_inst->GetSingleWordInOperand(new_member_idx);

      } break;

      case spv::Op::OpTypeArray:

      case spv::Op::OpTypeRuntimeArray:

      case spv::Op::OpTypeVector:

      case spv::Op::OpTypeMatrix:

      case spv::Op::OpTypeCooperativeMatrixNV:

      case spv::Op::OpTypeCooperativeMatrixKHR:

      case spv::Op::OpTypeVectorIdEXT:

        new_operands.emplace_back(inst->GetInOperand(i));

        type_id = type_inst->GetSingleWordInOperand(0);

        break;

      default:

        assert(false);

        break;

    }

  }

  if (!modified) {

    return Status::SuccessWithoutChange;

  }

  inst->SetInOperands(std::move(new_operands));

  context()->UpdateDefUse(inst);

  return Status::SuccessWithChange;

}

uint32_t EliminateDeadMembersPass::GetNewMemberIndex(uint32_t type_id,

                                                     uint32_t member_idx) {

  auto live_members = used_members_.find(type_id);

  if (live_members == used_members_.end()) {

    return member_idx;

  }

  auto current_member = live_members->second.find(member_idx);

  if (current_member == live_members->second.end()) {

    return kRemovedMember;

  }

  return static_cast<uint32_t>(

      std::distance(live_members->second.begin(), current_member));

}

bool EliminateDeadMembersPass::UpdateCompsiteExtract(Instruction* inst) {

  assert(inst->opcode() == spv::Op::OpCompositeExtract ||

         (inst->opcode() == spv::Op::OpSpecConstantOp &&

          spv::Op(inst->GetSingleWordInOperand(kSpecConstOpOpcodeIdx)) ==

              spv::Op::OpCompositeExtract));

  uint32_t first_operand = 0;

  if (inst->opcode() == spv::Op::OpSpecConstantOp) {

    first_operand = 1;

  }

  uint32_t object_id = inst->GetSingleWordInOperand(first_operand);

  Instruction* object_inst = get_def_use_mgr()->GetDef(object_id);

  uint32_t type_id = object_inst->type_id();

  Instruction::OperandList new_operands;

  bool modified = false;

  for (uint32_t i = 0; i < first_operand + 1; i++) {

    new_operands.emplace_back(inst->GetInOperand(i));

  }

  for (uint32_t i = first_operand + 1; i < inst->NumInOperands(); ++i) {

    uint32_t member_idx = inst->GetSingleWordInOperand(i);

    uint32_t new_member_idx = GetNewMemberIndex(type_id, member_idx);

    assert(new_member_idx != kRemovedMember);

    if (member_idx != new_member_idx) {

      modified = true;

    }

    new_operands.emplace_back(

        Operand({SPV_OPERAND_TYPE_LITERAL_INTEGER, {new_member_idx}}));

    Instruction* type_inst = get_def_use_mgr()->GetDef(type_id);

    switch (type_inst->opcode()) {

      case spv::Op::OpTypeStruct:

        // The type will have already been rewritten, so use the new member

        // index.

        type_id = type_inst->GetSingleWordInOperand(new_member_idx);

        break;

      case spv::Op::OpTypeArray:

      case spv::Op::OpTypeRuntimeArray:

      case spv::Op::OpTypeVector:

      case spv::Op::OpTypeMatrix:

      case spv::Op::OpTypeCooperativeMatrixNV:

      case spv::Op::OpTypeCooperativeMatrixKHR:

      case spv::Op::OpTypeVectorIdEXT:

        type_id = type_inst->GetSingleWordInOperand(0);

        break;

      default:

        assert(false);

    }

  }

  if (!modified) {

    return false;

  }

  inst->SetInOperands(std::move(new_operands));

  context()->UpdateDefUse(inst);

  return true;

}

bool EliminateDeadMembersPass::UpdateCompositeInsert(Instruction* inst) {

  assert(inst->opcode() == spv::Op::OpCompositeInsert ||

         (inst->opcode() == spv::Op::OpSpecConstantOp &&

          spv::Op(inst->GetSingleWordInOperand(kSpecConstOpOpcodeIdx)) ==

              spv::Op::OpCompositeInsert));

  uint32_t first_operand = 0;

  if (inst->opcode() == spv::Op::OpSpecConstantOp) {

    first_operand = 1;

  }

  uint32_t composite_id = inst->GetSingleWordInOperand(first_operand + 1);

  Instruction* composite_inst = get_def_use_mgr()->GetDef(composite_id);

  uint32_t type_id = composite_inst->type_id();

  Instruction::OperandList new_operands;

  bool modified = false;

  for (uint32_t i = 0; i < first_operand + 2; ++i) {

    new_operands.emplace_back(inst->GetInOperand(i));

  }

  for (uint32_t i = first_operand + 2; i < inst->NumInOperands(); ++i) {

    uint32_t member_idx = inst->GetSingleWordInOperand(i);

    uint32_t new_member_idx = GetNewMemberIndex(type_id, member_idx);

    if (new_member_idx == kRemovedMember) {

      context()->KillInst(inst);

      return true;

    }

    if (member_idx != new_member_idx) {

      modified = true;

    }

    new_operands.emplace_back(

        Operand({SPV_OPERAND_TYPE_LITERAL_INTEGER, {new_member_idx}}));

    Instruction* type_inst = get_def_use_mgr()->GetDef(type_id);

    switch (type_inst->opcode()) {

      case spv::Op::OpTypeStruct:

        // The type will have already been rewritten, so use the new member

        // index.

        type_id = type_inst->GetSingleWordInOperand(new_member_idx);

        break;

      case spv::Op::OpTypeArray:

      case spv::Op::OpTypeRuntimeArray:

      case spv::Op::OpTypeVector:

      case spv::Op::OpTypeMatrix:

      case spv::Op::OpTypeCooperativeMatrixNV:

      case spv::Op::OpTypeCooperativeMatrixKHR:

      case spv::Op::OpTypeVectorIdEXT:

        type_id = type_inst->GetSingleWordInOperand(0);

        break;

      default:

        assert(false);

    }

  }

  if (!modified) {

    return false;

  }

  inst->SetInOperands(std::move(new_operands));

  context()->UpdateDefUse(inst);

  return true;

}

bool EliminateDeadMembersPass::UpdateOpArrayLength(Instruction* inst) {

  uint32_t struct_id = inst->GetSingleWordInOperand(0);

  Instruction* struct_inst = get_def_use_mgr()->GetDef(struct_id);

  uint32_t pointer_type_id = struct_inst->type_id();

  Instruction* pointer_type_inst = get_def_use_mgr()->GetDef(pointer_type_id);

  uint32_t type_id = pointer_type_inst->GetSingleWordInOperand(1);

  uint32_t member_idx = inst->GetSingleWordInOperand(1);

  uint32_t new_member_idx = GetNewMemberIndex(type_id, member_idx);

  assert(new_member_idx != kRemovedMember);

  if (member_idx == new_member_idx) {

    return false;

  }

  inst->SetInOperand(1, {new_member_idx});

  context()->UpdateDefUse(inst);

  return true;

}

void EliminateDeadMembersPass::MarkStructOperandsAsFullyUsed(

    const Instruction* inst) {

  if (inst->type_id() != 0) {

    MarkTypeAsFullyUsed(inst->type_id());

  }

  inst->ForEachInId([this](const uint32_t* id) {

    Instruction* instruction = get_def_use_mgr()->GetDef(*id);

    if (instruction->type_id() != 0) {

      MarkTypeAsFullyUsed(instruction->type_id());

    } else if (spvOpcodeGeneratesType(instruction->opcode())) {

      // Some instructions take a type as an operand, such as the Message Type

      // of OpAbortKHR or the Base Type of OpUntypedAccessChainKHR.

      MarkTypeAsFullyUsed(instruction->result_id());

    }

  });

}

}  // namespace opt

}  // namespace spvtools