source/fuzz/transformation_add_function.cpp

// 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/fuzz/transformation_add_function.h"

#include "source/fuzz/fuzzer_util.h"
#include "source/fuzz/instruction_message.h"

namespace spvtools {
namespace fuzz {

TransformationAddFunction::TransformationAddFunction(
    protobufs::TransformationAddFunction message)
    : message_(std::move(message)) {}

TransformationAddFunction::TransformationAddFunction(
    const std::vector<protobufs::Instruction>& instructions) {
  for (auto& instruction : instructions) {
    *message_.add_instruction() = instruction;
  }
  message_.set_is_livesafe(false);
}

TransformationAddFunction::TransformationAddFunction(
    const std::vector<protobufs::Instruction>& instructions,
    uint32_t loop_limiter_variable_id, uint32_t loop_limit_constant_id,
    const std::vector<protobufs::LoopLimiterInfo>& loop_limiters,
    uint32_t kill_unreachable_return_value_id,
    const std::vector<protobufs::AccessChainClampingInfo>&
        access_chain_clampers) {
  for (auto& instruction : instructions) {
    *message_.add_instruction() = instruction;
  }
  message_.set_is_livesafe(true);
  message_.set_loop_limiter_variable_id(loop_limiter_variable_id);
  message_.set_loop_limit_constant_id(loop_limit_constant_id);
  for (auto& loop_limiter : loop_limiters) {
    *message_.add_loop_limiter_info() = loop_limiter;
  }
  message_.set_kill_unreachable_return_value_id(
      kill_unreachable_return_value_id);
  for (auto& access_clamper : access_chain_clampers) {
    *message_.add_access_chain_clamping_info() = access_clamper;
  }
}

bool TransformationAddFunction::IsApplicable(
    opt::IRContext* ir_context,
    const TransformationContext& transformation_context) const {
  // This transformation may use a lot of ids, all of which need to be fresh
  // and distinct.  This set tracks them.
  std::set<uint32_t> ids_used_by_this_transformation;

  // Ensure that all result ids in the new function are fresh and distinct.
  for (auto& instruction : message_.instruction()) {
    if (instruction.result_id()) {
      if (!CheckIdIsFreshAndNotUsedByThisTransformation(
              instruction.result_id(), ir_context,
              &ids_used_by_this_transformation)) {
        return false;
      }
    }
  }

  if (message_.is_livesafe()) {
    // Ensure that all ids provided for making the function livesafe are fresh
    // and distinct.
    if (!CheckIdIsFreshAndNotUsedByThisTransformation(
            message_.loop_limiter_variable_id(), ir_context,
            &ids_used_by_this_transformation)) {
      return false;
    }
    for (auto& loop_limiter_info : message_.loop_limiter_info()) {
      if (!CheckIdIsFreshAndNotUsedByThisTransformation(
              loop_limiter_info.load_id(), ir_context,
              &ids_used_by_this_transformation)) {
        return false;
      }
      if (!CheckIdIsFreshAndNotUsedByThisTransformation(
              loop_limiter_info.increment_id(), ir_context,
              &ids_used_by_this_transformation)) {
        return false;
      }
      if (!CheckIdIsFreshAndNotUsedByThisTransformation(
              loop_limiter_info.compare_id(), ir_context,
              &ids_used_by_this_transformation)) {
        return false;
      }
      if (!CheckIdIsFreshAndNotUsedByThisTransformation(
              loop_limiter_info.logical_op_id(), ir_context,
              &ids_used_by_this_transformation)) {
        return false;
      }
    }
    for (auto& access_chain_clamping_info :
         message_.access_chain_clamping_info()) {
      for (auto& pair : access_chain_clamping_info.compare_and_select_ids()) {
        if (!CheckIdIsFreshAndNotUsedByThisTransformation(
                pair.first(), ir_context, &ids_used_by_this_transformation)) {
          return false;
        }
        if (!CheckIdIsFreshAndNotUsedByThisTransformation(
                pair.second(), ir_context, &ids_used_by_this_transformation)) {
          return false;
        }
      }
    }
  }

  // Because checking all the conditions for a function to be valid is a big
  // job that the SPIR-V validator can already do, a "try it and see" approach
  // is taken here.

  // We first clone the current module, so that we can try adding the new
  // function without risking wrecking |ir_context|.
  auto cloned_module = fuzzerutil::CloneIRContext(ir_context);

  // We try to add a function to the cloned module, which may fail if
  // |message_.instruction| is not sufficiently well-formed.
  if (!TryToAddFunction(cloned_module.get())) {
    return false;
  }

  // Check whether the cloned module is still valid after adding the function.
  // If it is not, the transformation is not applicable.
  if (!fuzzerutil::IsValid(cloned_module.get(),
                           transformation_context.GetValidatorOptions(),
                           fuzzerutil::kSilentMessageConsumer)) {
    return false;
  }

  if (message_.is_livesafe()) {
    if (!TryToMakeFunctionLivesafe(cloned_module.get(),
                                   transformation_context)) {
      return false;
    }
    // After making the function livesafe, we check validity of the module
    // again.  This is because the turning of OpKill, OpUnreachable and OpReturn
    // instructions into branches changes control flow graph reachability, which
    // has the potential to make the module invalid when it was otherwise valid.
    // It is simpler to rely on the validator to guard against this than to
    // consider all scenarios when making a function livesafe.
    if (!fuzzerutil::IsValid(cloned_module.get(),
                             transformation_context.GetValidatorOptions(),
                             fuzzerutil::kSilentMessageConsumer)) {
      return false;
    }
  }
  return true;
}

void TransformationAddFunction::Apply(
    opt::IRContext* ir_context,
    TransformationContext* transformation_context) const {
  // Add the function to the module.  As the transformation is applicable, this
  // should succeed.
  bool success = TryToAddFunction(ir_context);
  assert(success && "The function should be successfully added.");
  (void)(success);  // Keep release builds happy (otherwise they may complain
                    // that |success| is not used).

  if (message_.is_livesafe()) {
    // Make the function livesafe, which also should succeed.
    success = TryToMakeFunctionLivesafe(ir_context, *transformation_context);
    assert(success && "It should be possible to make the function livesafe.");
    (void)(success);  // Keep release builds happy.
  }
  ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);

  assert(spv::Op(message_.instruction(0).opcode()) == spv::Op::OpFunction &&
         "The first instruction of an 'add function' transformation must be "
         "OpFunction.");

  if (message_.is_livesafe()) {
    // Inform the fact manager that the function is livesafe.
    transformation_context->GetFactManager()->AddFactFunctionIsLivesafe(
        message_.instruction(0).result_id());
  } else {
    // Inform the fact manager that all blocks in the function are dead.
    for (auto& inst : message_.instruction()) {
      if (spv::Op(inst.opcode()) == spv::Op::OpLabel) {
        transformation_context->GetFactManager()->AddFactBlockIsDead(
            inst.result_id());
      }
    }
  }

  // Record the fact that all pointer parameters and variables declared in the
  // function should be regarded as having irrelevant values.  This allows other
  // passes to store arbitrarily to such variables, and to pass them freely as
  // parameters to other functions knowing that it is OK if they get
  // over-written.
  for (auto& instruction : message_.instruction()) {
    switch (spv::Op(instruction.opcode())) {
      case spv::Op::OpFunctionParameter:
        if (ir_context->get_def_use_mgr()
                ->GetDef(instruction.result_type_id())
                ->opcode() == spv::Op::OpTypePointer) {
          transformation_context->GetFactManager()
              ->AddFactValueOfPointeeIsIrrelevant(instruction.result_id());
        }
        break;
      case spv::Op::OpVariable:
        transformation_context->GetFactManager()
            ->AddFactValueOfPointeeIsIrrelevant(instruction.result_id());
        break;
      default:
        break;
    }
  }
}

protobufs::Transformation TransformationAddFunction::ToMessage() const {
  protobufs::Transformation result;
  *result.mutable_add_function() = message_;
  return result;
}

bool TransformationAddFunction::TryToAddFunction(
    opt::IRContext* ir_context) const {
  // This function returns false if |message_.instruction| was not well-formed
  // enough to actually create a function and add it to |ir_context|.

  // A function must have at least some instructions.
  if (message_.instruction().empty()) {
    return false;
  }

  // A function must start with OpFunction.
  auto function_begin = message_.instruction(0);
  if (spv::Op(function_begin.opcode()) != spv::Op::OpFunction) {
    return false;
  }

  // Make a function, headed by the OpFunction instruction.
  std::unique_ptr<opt::Function> new_function = MakeUnique<opt::Function>(
      InstructionFromMessage(ir_context, function_begin));

  // Keeps track of which instruction protobuf message we are currently
  // considering.
  uint32_t instruction_index = 1;
  const auto num_instructions =
      static_cast<uint32_t>(message_.instruction().size());

  // Iterate through all function parameter instructions, adding parameters to
  // the new function.
  while (instruction_index < num_instructions &&
         spv::Op(message_.instruction(instruction_index).opcode()) ==
             spv::Op::OpFunctionParameter) {
    new_function->AddParameter(InstructionFromMessage(
        ir_context, message_.instruction(instruction_index)));
    instruction_index++;
  }

  // After the parameters, there needs to be a label.
  if (instruction_index == num_instructions ||
      spv::Op(message_.instruction(instruction_index).opcode()) !=
          spv::Op::OpLabel) {
    return false;
  }

  // Iterate through the instructions block by block until the end of the
  // function is reached.
  while (instruction_index < num_instructions &&
         spv::Op(message_.instruction(instruction_index).opcode()) !=
             spv::Op::OpFunctionEnd) {
    // Invariant: we should always be at a label instruction at this point.
    assert(spv::Op(message_.instruction(instruction_index).opcode()) ==
           spv::Op::OpLabel);

    // Make a basic block using the label instruction.
    std::unique_ptr<opt::BasicBlock> block =
        MakeUnique<opt::BasicBlock>(InstructionFromMessage(
            ir_context, message_.instruction(instruction_index)));

    // Consider successive instructions until we hit another label or the end
    // of the function, adding each such instruction to the block.
    instruction_index++;
    while (instruction_index < num_instructions &&
           spv::Op(message_.instruction(instruction_index).opcode()) !=
               spv::Op::OpFunctionEnd &&
           spv::Op(message_.instruction(instruction_index).opcode()) !=
               spv::Op::OpLabel) {
      block->AddInstruction(InstructionFromMessage(
          ir_context, message_.instruction(instruction_index)));
      instruction_index++;
    }
    // Add the block to the new function.
    new_function->AddBasicBlock(std::move(block));
  }
  // Having considered all the blocks, we should be at the last instruction and
  // it needs to be OpFunctionEnd.
  if (instruction_index != num_instructions - 1 ||
      spv::Op(message_.instruction(instruction_index).opcode()) !=
          spv::Op::OpFunctionEnd) {
    return false;
  }
  // Set the function's final instruction, add the function to the module and
  // report success.
  new_function->SetFunctionEnd(InstructionFromMessage(
      ir_context, message_.instruction(instruction_index)));
  ir_context->AddFunction(std::move(new_function));

  ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);

  return true;
}

bool TransformationAddFunction::TryToMakeFunctionLivesafe(
    opt::IRContext* ir_context,
    const TransformationContext& transformation_context) const {
  assert(message_.is_livesafe() && "Precondition: is_livesafe must hold.");

  // Get a pointer to the added function.
  opt::Function* added_function = nullptr;
  for (auto& function : *ir_context->module()) {
    if (function.result_id() == message_.instruction(0).result_id()) {
      added_function = &function;
      break;
    }
  }
  assert(added_function && "The added function should have been found.");

  if (!TryToAddLoopLimiters(ir_context, added_function)) {
    // Adding loop limiters did not work; bail out.
    return false;
  }

  // Consider all the instructions in the function, and:
  // - attempt to replace OpKill and OpUnreachable with return instructions
  // - attempt to clamp access chains to be within bounds
  // - check that OpFunctionCall instructions are only to livesafe functions
  for (auto& block : *added_function) {
    for (auto& inst : block) {
      switch (inst.opcode()) {
        case spv::Op::OpKill:
        case spv::Op::OpUnreachable:
          if (!TryToTurnKillOrUnreachableIntoReturn(ir_context, added_function,
                                                    &inst)) {
            return false;
          }
          break;
        case spv::Op::OpAccessChain:
        case spv::Op::OpInBoundsAccessChain:
          if (!TryToClampAccessChainIndices(ir_context, &inst)) {
            return false;
          }
          break;
        case spv::Op::OpFunctionCall:
          // A livesafe function my only call other livesafe functions.
          if (!transformation_context.GetFactManager()->FunctionIsLivesafe(
                  inst.GetSingleWordInOperand(0))) {
            return false;
          }
        default:
          break;
      }
    }
  }
  return true;
}

uint32_t TransformationAddFunction::GetBackEdgeBlockId(
    opt::IRContext* ir_context, uint32_t loop_header_block_id) {
  const auto* loop_header_block =
      ir_context->cfg()->block(loop_header_block_id);
  assert(loop_header_block && "|loop_header_block_id| is invalid");

  for (auto pred : ir_context->cfg()->preds(loop_header_block_id)) {
    if (ir_context->GetDominatorAnalysis(loop_header_block->GetParent())
            ->Dominates(loop_header_block_id, pred)) {
      return pred;
    }
  }

  return 0;
}

bool TransformationAddFunction::TryToAddLoopLimiters(
    opt::IRContext* ir_context, opt::Function* added_function) const {
  // Collect up all the loop headers so that we can subsequently add loop
  // limiting logic.
  std::vector<opt::BasicBlock*> loop_headers;
  for (auto& block : *added_function) {
    if (block.IsLoopHeader()) {
      loop_headers.push_back(&block);
    }
  }

  if (loop_headers.empty()) {
    // There are no loops, so no need to add any loop limiters.
    return true;
  }

  // Check that the module contains appropriate ingredients for declaring and
  // manipulating a loop limiter.

  auto loop_limit_constant_id_instr =
      ir_context->get_def_use_mgr()->GetDef(message_.loop_limit_constant_id());
  if (!loop_limit_constant_id_instr ||
      loop_limit_constant_id_instr->opcode() != spv::Op::OpConstant) {
    // The loop limit constant id instruction must exist and have an
    // appropriate opcode.
    return false;
  }

  auto loop_limit_type = ir_context->get_def_use_mgr()->GetDef(
      loop_limit_constant_id_instr->type_id());
  if (loop_limit_type->opcode() != spv::Op::OpTypeInt ||
      loop_limit_type->GetSingleWordInOperand(0) != 32) {
    // The type of the loop limit constant must be 32-bit integer.  It
    // doesn't actually matter whether the integer is signed or not.
    return false;
  }

  // Find the id of the "unsigned int" type.
  opt::analysis::Integer unsigned_int_type(32, false);
  uint32_t unsigned_int_type_id =
      ir_context->get_type_mgr()->GetId(&unsigned_int_type);
  if (!unsigned_int_type_id) {
    // Unsigned int is not available; we need this type in order to add loop
    // limiters.
    return false;
  }
  auto registered_unsigned_int_type =
      ir_context->get_type_mgr()->GetRegisteredType(&unsigned_int_type);

  // Look for 0 of type unsigned int.
  opt::analysis::IntConstant zero(registered_unsigned_int_type->AsInteger(),
                                  {0});
  auto registered_zero = ir_context->get_constant_mgr()->FindConstant(&zero);
  if (!registered_zero) {
    // We need 0 in order to be able to initialize loop limiters.
    return false;
  }
  uint32_t zero_id = ir_context->get_constant_mgr()
                         ->GetDefiningInstruction(registered_zero)
                         ->result_id();

  // Look for 1 of type unsigned int.
  opt::analysis::IntConstant one(registered_unsigned_int_type->AsInteger(),
                                 {1});
  auto registered_one = ir_context->get_constant_mgr()->FindConstant(&one);
  if (!registered_one) {
    // We need 1 in order to be able to increment loop limiters.
    return false;
  }
  uint32_t one_id = ir_context->get_constant_mgr()
                        ->GetDefiningInstruction(registered_one)
                        ->result_id();

  // Look for pointer-to-unsigned int type.
  opt::analysis::Pointer pointer_to_unsigned_int_type(
      registered_unsigned_int_type, spv::StorageClass::Function);
  uint32_t pointer_to_unsigned_int_type_id =
      ir_context->get_type_mgr()->GetId(&pointer_to_unsigned_int_type);
  if (!pointer_to_unsigned_int_type_id) {
    // We need pointer-to-unsigned int in order to declare the loop limiter
    // variable.
    return false;
  }

  // Look for bool type.
  opt::analysis::Bool bool_type;
  uint32_t bool_type_id = ir_context->get_type_mgr()->GetId(&bool_type);
  if (!bool_type_id) {
    // We need bool in order to compare the loop limiter's value with the loop
    // limit constant.
    return false;
  }

  // Declare the loop limiter variable at the start of the function's entry
  // block, via an instruction of the form:
  //   %loop_limiter_var = spv::Op::OpVariable %ptr_to_uint Function %zero
  added_function->begin()->begin()->InsertBefore(MakeUnique<opt::Instruction>(
      ir_context, spv::Op::OpVariable, pointer_to_unsigned_int_type_id,
      message_.loop_limiter_variable_id(),
      opt::Instruction::OperandList({{SPV_OPERAND_TYPE_STORAGE_CLASS,
                                      {uint32_t(spv::StorageClass::Function)}},
                                     {SPV_OPERAND_TYPE_ID, {zero_id}}})));
  // Update the module's id bound since we have added the loop limiter
  // variable id.
  fuzzerutil::UpdateModuleIdBound(ir_context,
                                  message_.loop_limiter_variable_id());

  // Consider each loop in turn.
  for (auto loop_header : loop_headers) {
    // Look for the loop's back-edge block.  This is a predecessor of the loop
    // header that is dominated by the loop header.
    const auto back_edge_block_id =
        GetBackEdgeBlockId(ir_context, loop_header->id());
    if (!back_edge_block_id) {
      // The loop's back-edge block must be unreachable.  This means that the
      // loop cannot iterate, so there is no need to make it lifesafe; we can
      // move on from this loop.
      continue;
    }

    // If the loop's merge block is unreachable, then there are no constraints
    // on where the merge block appears in relation to the blocks of the loop.
    // This means we need to be careful when adding a branch from the back-edge
    // block to the merge block: the branch might make the loop merge reachable,
    // and it might then be dominated by the loop header and possibly by other
    // blocks in the loop. Since a block needs to appear before those blocks it
    // strictly dominates, this could make the module invalid. To avoid this
    // problem we bail out in the case where the loop header does not dominate
    // the loop merge.
    if (!ir_context->GetDominatorAnalysis(added_function)
             ->Dominates(loop_header->id(), loop_header->MergeBlockId())) {
      return false;
    }

    // Go through the sequence of loop limiter infos and find the one
    // corresponding to this loop.
    bool found = false;
    protobufs::LoopLimiterInfo loop_limiter_info;
    for (auto& info : message_.loop_limiter_info()) {
      if (info.loop_header_id() == loop_header->id()) {
        loop_limiter_info = info;
        found = true;
        break;
      }
    }
    if (!found) {
      // We don't have loop limiter info for this loop header.
      return false;
    }

    // The back-edge block either has the form:
    //
    // (1)
    //
    // %l = OpLabel
    //      ... instructions ...
    //      OpBranch %loop_header
    //
    // (2)
    //
    // %l = OpLabel
    //      ... instructions ...
    //      OpBranchConditional %c %loop_header %loop_merge
    //
    // (3)
    //
    // %l = OpLabel
    //      ... instructions ...
    //      OpBranchConditional %c %loop_merge %loop_header
    //
    // We turn these into the following:
    //
    // (1)
    //
    //  %l = OpLabel
    //       ... instructions ...
    // %t1 = OpLoad %uint32 %loop_limiter
    // %t2 = OpIAdd %uint32 %t1 %one
    //       OpStore %loop_limiter %t2
    // %t3 = OpUGreaterThanEqual %bool %t1 %loop_limit
    //       OpBranchConditional %t3 %loop_merge %loop_header
    //
    // (2)
    //
    //  %l = OpLabel
    //       ... instructions ...
    // %t1 = OpLoad %uint32 %loop_limiter
    // %t2 = OpIAdd %uint32 %t1 %one
    //       OpStore %loop_limiter %t2
    // %t3 = OpULessThan %bool %t1 %loop_limit
    // %t4 = OpLogicalAnd %bool %c %t3
    //       OpBranchConditional %t4 %loop_header %loop_merge
    //
    // (3)
    //
    //  %l = OpLabel
    //       ... instructions ...
    // %t1 = OpLoad %uint32 %loop_limiter
    // %t2 = OpIAdd %uint32 %t1 %one
    //       OpStore %loop_limiter %t2
    // %t3 = OpUGreaterThanEqual %bool %t1 %loop_limit
    // %t4 = OpLogicalOr %bool %c %t3
    //       OpBranchConditional %t4 %loop_merge %loop_header

    auto back_edge_block = ir_context->cfg()->block(back_edge_block_id);
    auto back_edge_block_terminator = back_edge_block->terminator();
    bool compare_using_greater_than_equal;
    if (back_edge_block_terminator->opcode() == spv::Op::OpBranch) {
      compare_using_greater_than_equal = true;
    } else {
      assert(back_edge_block_terminator->opcode() ==
             spv::Op::OpBranchConditional);
      assert(((back_edge_block_terminator->GetSingleWordInOperand(1) ==
                   loop_header->id() &&
               back_edge_block_terminator->GetSingleWordInOperand(2) ==
                   loop_header->MergeBlockId()) ||
              (back_edge_block_terminator->GetSingleWordInOperand(2) ==
                   loop_header->id() &&
               back_edge_block_terminator->GetSingleWordInOperand(1) ==
                   loop_header->MergeBlockId())) &&
             "A back edge edge block must branch to"
             " either the loop header or merge");
      compare_using_greater_than_equal =
          back_edge_block_terminator->GetSingleWordInOperand(1) ==
          loop_header->MergeBlockId();
    }

    std::vector<std::unique_ptr<opt::Instruction>> new_instructions;

    // Add a load from the loop limiter variable, of the form:
    //   %t1 = OpLoad %uint32 %loop_limiter
    new_instructions.push_back(MakeUnique<opt::Instruction>(
        ir_context, spv::Op::OpLoad, unsigned_int_type_id,
        loop_limiter_info.load_id(),
        opt::Instruction::OperandList(
            {{SPV_OPERAND_TYPE_ID, {message_.loop_limiter_variable_id()}}})));

    // Increment the loaded value:
    //   %t2 = OpIAdd %uint32 %t1 %one
    new_instructions.push_back(MakeUnique<opt::Instruction>(
        ir_context, spv::Op::OpIAdd, unsigned_int_type_id,
        loop_limiter_info.increment_id(),
        opt::Instruction::OperandList(
            {{SPV_OPERAND_TYPE_ID, {loop_limiter_info.load_id()}},
             {SPV_OPERAND_TYPE_ID, {one_id}}})));

    // Store the incremented value back to the loop limiter variable:
    //   OpStore %loop_limiter %t2
    new_instructions.push_back(MakeUnique<opt::Instruction>(
        ir_context, spv::Op::OpStore, 0, 0,
        opt::Instruction::OperandList(
            {{SPV_OPERAND_TYPE_ID, {message_.loop_limiter_variable_id()}},
             {SPV_OPERAND_TYPE_ID, {loop_limiter_info.increment_id()}}})));

    // Compare the loaded value with the loop limit; either:
    //   %t3 = OpUGreaterThanEqual %bool %t1 %loop_limit
    // or
    //   %t3 = OpULessThan %bool %t1 %loop_limit
    new_instructions.push_back(MakeUnique<opt::Instruction>(
        ir_context,
        compare_using_greater_than_equal ? spv::Op::OpUGreaterThanEqual
                                         : spv::Op::OpULessThan,
        bool_type_id, loop_limiter_info.compare_id(),
        opt::Instruction::OperandList(
            {{SPV_OPERAND_TYPE_ID, {loop_limiter_info.load_id()}},
             {SPV_OPERAND_TYPE_ID, {message_.loop_limit_constant_id()}}})));

    if (back_edge_block_terminator->opcode() == spv::Op::OpBranchConditional) {
      new_instructions.push_back(MakeUnique<opt::Instruction>(
          ir_context,
          compare_using_greater_than_equal ? spv::Op::OpLogicalOr
                                           : spv::Op::OpLogicalAnd,
          bool_type_id, loop_limiter_info.logical_op_id(),
          opt::Instruction::OperandList(
              {{SPV_OPERAND_TYPE_ID,
                {back_edge_block_terminator->GetSingleWordInOperand(0)}},
               {SPV_OPERAND_TYPE_ID, {loop_limiter_info.compare_id()}}})));
    }

    // Add the new instructions at the end of the back edge block, before the
    // terminator and any loop merge instruction (as the back edge block can
    // be the loop header).
    if (back_edge_block->GetLoopMergeInst()) {
      back_edge_block->GetLoopMergeInst()->InsertBefore(
          std::move(new_instructions));
    } else {
      back_edge_block_terminator->InsertBefore(std::move(new_instructions));
    }

    if (back_edge_block_terminator->opcode() == spv::Op::OpBranchConditional) {
      back_edge_block_terminator->SetInOperand(
          0, {loop_limiter_info.logical_op_id()});
    } else {
      assert(back_edge_block_terminator->opcode() == spv::Op::OpBranch &&
             "Back-edge terminator must be OpBranch or OpBranchConditional");

      // Check that, if the merge block starts with OpPhi instructions, suitable
      // ids have been provided to give these instructions a value corresponding
      // to the new incoming edge from the back edge block.
      auto merge_block = ir_context->cfg()->block(loop_header->MergeBlockId());
      if (!fuzzerutil::PhiIdsOkForNewEdge(ir_context, back_edge_block,
                                          merge_block,
                                          loop_limiter_info.phi_id())) {
        return false;
      }

      // Augment OpPhi instructions at the loop merge with the given ids.
      uint32_t phi_index = 0;
      for (auto& inst : *merge_block) {
        if (inst.opcode() != spv::Op::OpPhi) {
          break;
        }
        assert(phi_index <
                   static_cast<uint32_t>(loop_limiter_info.phi_id().size()) &&
               "There should be at least one phi id per OpPhi instruction.");
        inst.AddOperand(
            {SPV_OPERAND_TYPE_ID, {loop_limiter_info.phi_id(phi_index)}});
        inst.AddOperand({SPV_OPERAND_TYPE_ID, {back_edge_block_id}});
        phi_index++;
      }

      // Add the new edge, by changing OpBranch to OpBranchConditional.
      back_edge_block_terminator->SetOpcode(spv::Op::OpBranchConditional);
      back_edge_block_terminator->SetInOperands(opt::Instruction::OperandList(
          {{SPV_OPERAND_TYPE_ID, {loop_limiter_info.compare_id()}},
           {SPV_OPERAND_TYPE_ID, {loop_header->MergeBlockId()}},
           {SPV_OPERAND_TYPE_ID, {loop_header->id()}}}));
    }

    // Update the module's id bound with respect to the various ids that
    // have been used for loop limiter manipulation.
    fuzzerutil::UpdateModuleIdBound(ir_context, loop_limiter_info.load_id());
    fuzzerutil::UpdateModuleIdBound(ir_context,
                                    loop_limiter_info.increment_id());
    fuzzerutil::UpdateModuleIdBound(ir_context, loop_limiter_info.compare_id());
    fuzzerutil::UpdateModuleIdBound(ir_context,
                                    loop_limiter_info.logical_op_id());
  }
  return true;
}

bool TransformationAddFunction::TryToTurnKillOrUnreachableIntoReturn(
    opt::IRContext* ir_context, opt::Function* added_function,
    opt::Instruction* kill_or_unreachable_inst) const {
  assert((kill_or_unreachable_inst->opcode() == spv::Op::OpKill ||
          kill_or_unreachable_inst->opcode() == spv::Op::OpUnreachable) &&
         "Precondition: instruction must be OpKill or OpUnreachable.");

  // Get the function's return type.
  auto function_return_type_inst =
      ir_context->get_def_use_mgr()->GetDef(added_function->type_id());

  if (function_return_type_inst->opcode() == spv::Op::OpTypeVoid) {
    // The function has void return type, so change this instruction to
    // OpReturn.
    kill_or_unreachable_inst->SetOpcode(spv::Op::OpReturn);
  } else {
    // The function has non-void return type, so change this instruction
    // to OpReturnValue, using the value id provided with the
    // transformation.

    // We first check that the id, %id, provided with the transformation
    // specifically to turn OpKill and OpUnreachable instructions into
    // OpReturnValue %id has the same type as the function's return type.
    if (ir_context->get_def_use_mgr()
            ->GetDef(message_.kill_unreachable_return_value_id())
            ->type_id() != function_return_type_inst->result_id()) {
      return false;
    }
    kill_or_unreachable_inst->SetOpcode(spv::Op::OpReturnValue);
    kill_or_unreachable_inst->SetInOperands(
        {{SPV_OPERAND_TYPE_ID, {message_.kill_unreachable_return_value_id()}}});
  }
  return true;
}

bool TransformationAddFunction::TryToClampAccessChainIndices(
    opt::IRContext* ir_context, opt::Instruction* access_chain_inst) const {
  assert((access_chain_inst->opcode() == spv::Op::OpAccessChain ||
          access_chain_inst->opcode() == spv::Op::OpInBoundsAccessChain) &&
         "Precondition: instruction must be OpAccessChain or "
         "OpInBoundsAccessChain.");

  // Find the AccessChainClampingInfo associated with this access chain.
  const protobufs::AccessChainClampingInfo* access_chain_clamping_info =
      nullptr;
  for (auto& clamping_info : message_.access_chain_clamping_info()) {
    if (clamping_info.access_chain_id() == access_chain_inst->result_id()) {
      access_chain_clamping_info = &clamping_info;
      break;
    }
  }
  if (!access_chain_clamping_info) {
    // No access chain clamping information was found; the function cannot be
    // made livesafe.
    return false;
  }

  // Check that there is a (compare_id, select_id) pair for every
  // index associated with the instruction.
  if (static_cast<uint32_t>(
          access_chain_clamping_info->compare_and_select_ids().size()) !=
      access_chain_inst->NumInOperands() - 1) {
    return false;
  }

  // Walk the access chain, clamping each index to be within bounds if it is
  // not a constant.
  auto base_object = ir_context->get_def_use_mgr()->GetDef(
      access_chain_inst->GetSingleWordInOperand(0));
  assert(base_object && "The base object must exist.");
  auto pointer_type =
      ir_context->get_def_use_mgr()->GetDef(base_object->type_id());
  assert(pointer_type && pointer_type->opcode() == spv::Op::OpTypePointer &&
         "The base object must have pointer type.");
  auto should_be_composite_type = ir_context->get_def_use_mgr()->GetDef(
      pointer_type->GetSingleWordInOperand(1));

  // Consider each index input operand in turn (operand 0 is the base object).
  for (uint32_t index = 1; index < access_chain_inst->NumInOperands();
       index++) {
    // We are going to turn:
    //
    // %result = OpAccessChain %type %object ... %index ...
    //
    // into:
    //
    // %t1 = OpULessThanEqual %bool %index %bound_minus_one
    // %t2 = OpSelect %int_type %t1 %index %bound_minus_one
    // %result = OpAccessChain %type %object ... %t2 ...
    //
    // ... unless %index is already a constant.

    // Get the bound for the composite being indexed into; e.g. the number of
    // columns of matrix or the size of an array.
    uint32_t bound = fuzzerutil::GetBoundForCompositeIndex(
        *should_be_composite_type, ir_context);

    // Get the instruction associated with the index and figure out its integer
    // type.
    const uint32_t index_id = access_chain_inst->GetSingleWordInOperand(index);
    auto index_inst = ir_context->get_def_use_mgr()->GetDef(index_id);
    auto index_type_inst =
        ir_context->get_def_use_mgr()->GetDef(index_inst->type_id());
    assert(index_type_inst->opcode() == spv::Op::OpTypeInt);
    assert(index_type_inst->GetSingleWordInOperand(0) == 32);
    opt::analysis::Integer* index_int_type =
        ir_context->get_type_mgr()
            ->GetType(index_type_inst->result_id())
            ->AsInteger();

    if (index_inst->opcode() != spv::Op::OpConstant ||
        index_inst->GetSingleWordInOperand(0) >= bound) {
      // The index is either non-constant or an out-of-bounds constant, so we
      // need to clamp it.
      assert(should_be_composite_type->opcode() != spv::Op::OpTypeStruct &&
             "Access chain indices into structures are required to be "
             "constants.");
      opt::analysis::IntConstant bound_minus_one(index_int_type, {bound - 1});
      if (!ir_context->get_constant_mgr()->FindConstant(&bound_minus_one)) {
        // We do not have an integer constant whose value is |bound| -1.
        return false;
      }

      opt::analysis::Bool bool_type;
      uint32_t bool_type_id = ir_context->get_type_mgr()->GetId(&bool_type);
      if (!bool_type_id) {
        // Bool type is not declared; we cannot do a comparison.
        return false;
      }

      uint32_t bound_minus_one_id =
          ir_context->get_constant_mgr()
              ->GetDefiningInstruction(&bound_minus_one)
              ->result_id();

      uint32_t compare_id =
          access_chain_clamping_info->compare_and_select_ids(index - 1).first();
      uint32_t select_id =
          access_chain_clamping_info->compare_and_select_ids(index - 1)
              .second();
      std::vector<std::unique_ptr<opt::Instruction>> new_instructions;

      // Compare the index with the bound via an instruction of the form:
      //   %t1 = OpULessThanEqual %bool %index %bound_minus_one
      new_instructions.push_back(MakeUnique<opt::Instruction>(
          ir_context, spv::Op::OpULessThanEqual, bool_type_id, compare_id,
          opt::Instruction::OperandList(
              {{SPV_OPERAND_TYPE_ID, {index_inst->result_id()}},
               {SPV_OPERAND_TYPE_ID, {bound_minus_one_id}}})));

      // Select the index if in-bounds, otherwise one less than the bound:
      //   %t2 = OpSelect %int_type %t1 %index %bound_minus_one
      new_instructions.push_back(MakeUnique<opt::Instruction>(
          ir_context, spv::Op::OpSelect, index_type_inst->result_id(),
          select_id,
          opt::Instruction::OperandList(
              {{SPV_OPERAND_TYPE_ID, {compare_id}},
               {SPV_OPERAND_TYPE_ID, {index_inst->result_id()}},
               {SPV_OPERAND_TYPE_ID, {bound_minus_one_id}}})));

      // Add the new instructions before the access chain
      access_chain_inst->InsertBefore(std::move(new_instructions));

      // Replace %index with %t2.
      access_chain_inst->SetInOperand(index, {select_id});
      fuzzerutil::UpdateModuleIdBound(ir_context, compare_id);
      fuzzerutil::UpdateModuleIdBound(ir_context, select_id);
    }
    should_be_composite_type =
        FollowCompositeIndex(ir_context, *should_be_composite_type, index_id);
  }
  return true;
}

opt::Instruction* TransformationAddFunction::FollowCompositeIndex(
    opt::IRContext* ir_context, const opt::Instruction& composite_type_inst,
    uint32_t index_id) {
  uint32_t sub_object_type_id;
  switch (composite_type_inst.opcode()) {
    case spv::Op::OpTypeArray:
    case spv::Op::OpTypeRuntimeArray:
      sub_object_type_id = composite_type_inst.GetSingleWordInOperand(0);
      break;
    case spv::Op::OpTypeMatrix:
    case spv::Op::OpTypeVector:
      sub_object_type_id = composite_type_inst.GetSingleWordInOperand(0);
      break;
    case spv::Op::OpTypeStruct: {
      auto index_inst = ir_context->get_def_use_mgr()->GetDef(index_id);
      assert(index_inst->opcode() == spv::Op::OpConstant);
      assert(ir_context->get_def_use_mgr()
                 ->GetDef(index_inst->type_id())
                 ->opcode() == spv::Op::OpTypeInt);
      assert(ir_context->get_def_use_mgr()
                 ->GetDef(index_inst->type_id())
                 ->GetSingleWordInOperand(0) == 32);
      uint32_t index_value = index_inst->GetSingleWordInOperand(0);
      sub_object_type_id =
          composite_type_inst.GetSingleWordInOperand(index_value);
      break;
    }
    default:
      assert(false && "Unknown composite type.");
      sub_object_type_id = 0;
      break;
  }
  assert(sub_object_type_id && "No sub-object found.");
  return ir_context->get_def_use_mgr()->GetDef(sub_object_type_id);
}

std::unordered_set<uint32_t> TransformationAddFunction::GetFreshIds() const {
  std::unordered_set<uint32_t> result;
  for (auto& instruction : message_.instruction()) {
    result.insert(instruction.result_id());
  }
  if (message_.is_livesafe()) {
    result.insert(message_.loop_limiter_variable_id());
    for (auto& loop_limiter_info : message_.loop_limiter_info()) {
      result.insert(loop_limiter_info.load_id());
      result.insert(loop_limiter_info.increment_id());
      result.insert(loop_limiter_info.compare_id());
      result.insert(loop_limiter_info.logical_op_id());
    }
    for (auto& access_chain_clamping_info :
         message_.access_chain_clamping_info()) {
      for (auto& pair : access_chain_clamping_info.compare_and_select_ids()) {
        result.insert(pair.first());
        result.insert(pair.second());
      }
    }
  }
  return result;
}

}  // namespace fuzz
}  // namespace spvtools