source/fuzz/transformation_access_chain.cpp

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

#include <vector>

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

namespace spvtools {
namespace fuzz {

TransformationAccessChain::TransformationAccessChain(
    const spvtools::fuzz::protobufs::TransformationAccessChain& message)
    : message_(message) {}

TransformationAccessChain::TransformationAccessChain(
    uint32_t fresh_id, uint32_t pointer_id,
    const std::vector<uint32_t>& index_id,
    const protobufs::InstructionDescriptor& instruction_to_insert_before,
    const std::vector<std::pair<uint32_t, uint32_t>>& fresh_ids_for_clamping) {
  message_.set_fresh_id(fresh_id);
  message_.set_pointer_id(pointer_id);
  for (auto id : index_id) {
    message_.add_index_id(id);
  }
  *message_.mutable_instruction_to_insert_before() =
      instruction_to_insert_before;
  for (auto clamping_ids_pair : fresh_ids_for_clamping) {
    protobufs::UInt32Pair pair;
    pair.set_first(clamping_ids_pair.first);
    pair.set_second(clamping_ids_pair.second);
    *message_.add_fresh_ids_for_clamping() = pair;
  }
}

bool TransformationAccessChain::IsApplicable(
    opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
  // Keep track of the fresh ids used to make sure that they are distinct.
  std::set<uint32_t> fresh_ids_used;

  // The result id must be fresh.
  if (!CheckIdIsFreshAndNotUsedByThisTransformation(
          message_.fresh_id(), ir_context, &fresh_ids_used)) {
    return false;
  }
  // The pointer id must exist and have a type.
  auto pointer = ir_context->get_def_use_mgr()->GetDef(message_.pointer_id());
  if (!pointer || !pointer->type_id()) {
    return false;
  }
  // The type must indeed be a pointer.
  auto pointer_type = ir_context->get_def_use_mgr()->GetDef(pointer->type_id());
  if (pointer_type->opcode() != SpvOpTypePointer) {
    return false;
  }

  // The described instruction to insert before must exist and be a suitable
  // point where an OpAccessChain instruction could be inserted.
  auto instruction_to_insert_before =
      FindInstruction(message_.instruction_to_insert_before(), ir_context);
  if (!instruction_to_insert_before) {
    return false;
  }
  if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(
          SpvOpAccessChain, instruction_to_insert_before)) {
    return false;
  }

  // Do not allow making an access chain from a null or undefined pointer, as
  // we do not want to allow accessing such pointers.  This might be acceptable
  // in dead blocks, but we conservatively avoid it.
  switch (pointer->opcode()) {
    case SpvOpConstantNull:
    case SpvOpUndef:
      assert(
          false &&
          "Access chains should not be created from null/undefined pointers");
      return false;
    default:
      break;
  }

  // The pointer on which the access chain is to be based needs to be available
  // (according to dominance rules) at the insertion point.
  if (!fuzzerutil::IdIsAvailableBeforeInstruction(
          ir_context, instruction_to_insert_before, message_.pointer_id())) {
    return false;
  }

  // We now need to use the given indices to walk the type structure of the
  // base type of the pointer, making sure that (a) the indices correspond to
  // integers, and (b) these integer values are in-bounds.

  // Start from the base type of the pointer.
  uint32_t subobject_type_id = pointer_type->GetSingleWordInOperand(1);

  int id_pairs_used = 0;

  // Consider the given index ids in turn.
  for (auto index_id : message_.index_id()) {
    // The index value will correspond to the value of the index if the object
    // is a struct, otherwise the value 0 will be used.
    uint32_t index_value;

    // Check whether the object is a struct.
    if (ir_context->get_def_use_mgr()->GetDef(subobject_type_id)->opcode() ==
        SpvOpTypeStruct) {
      // It is a struct: we need to retrieve the integer value.

      bool successful;
      std::tie(successful, index_value) =
          GetIndexValue(ir_context, index_id, subobject_type_id);

      if (!successful) {
        return false;
      }
    } else {
      // It is not a struct: the index will need clamping.

      if (message_.fresh_ids_for_clamping().size() <= id_pairs_used) {
        // We don't have enough ids
        return false;
      }

      // Get two new ids to use and update the amount used.
      protobufs::UInt32Pair fresh_ids =
          message_.fresh_ids_for_clamping()[id_pairs_used++];

      // Valid ids need to have been given
      if (fresh_ids.first() == 0 || fresh_ids.second() == 0) {
        return false;
      }

      // Check that the ids are actually fresh and not already used by this
      // transformation.
      if (!CheckIdIsFreshAndNotUsedByThisTransformation(
              fresh_ids.first(), ir_context, &fresh_ids_used) ||
          !CheckIdIsFreshAndNotUsedByThisTransformation(
              fresh_ids.second(), ir_context, &fresh_ids_used)) {
        return false;
      }

      if (!ValidIndexToComposite(ir_context, index_id, subobject_type_id)) {
        return false;
      }

      // Perform the clamping using the fresh ids at our disposal.
      auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);

      uint32_t bound = fuzzerutil::GetBoundForCompositeIndex(
          *ir_context->get_def_use_mgr()->GetDef(subobject_type_id),
          ir_context);

      // The module must have an integer constant of value bound-1 of the same
      // type as the index.
      if (!fuzzerutil::MaybeGetIntegerConstantFromValueAndType(
              ir_context, bound - 1, index_instruction->type_id())) {
        return false;
      }

      // The module must have the definition of bool type to make a comparison.
      if (!fuzzerutil::MaybeGetBoolType(ir_context)) {
        return false;
      }

      // The index is not necessarily a constant, so we may not know its value.
      // We can use index 0 because the components of a non-struct composite
      // all have the same type, and index 0 is always in bounds.
      index_value = 0;
    }

    // Try to walk down the type using this index.  This will yield 0 if the
    // type is not a composite or the index is out of bounds, and the id of
    // the next type otherwise.
    subobject_type_id = fuzzerutil::WalkOneCompositeTypeIndex(
        ir_context, subobject_type_id, index_value);
    if (!subobject_type_id) {
      // Either the type was not a composite (so that too many indices were
      // provided), or the index was out of bounds.
      return false;
    }
  }
  // At this point, |subobject_type_id| is the type of the value targeted by
  // the new access chain.  The result type of the access chain should be a
  // pointer to this type, with the same storage class as for the original
  // pointer.  Such a pointer type needs to exist in the module.
  //
  // We do not use the type manager to look up this type, due to problems
  // associated with pointers to isomorphic structs being regarded as the same.
  return fuzzerutil::MaybeGetPointerType(
             ir_context, subobject_type_id,
             static_cast<SpvStorageClass>(
                 pointer_type->GetSingleWordInOperand(0))) != 0;
}

void TransformationAccessChain::Apply(
    opt::IRContext* ir_context,
    TransformationContext* transformation_context) const {
  // The operands to the access chain are the pointer followed by the indices.
  // The result type of the access chain is determined by where the indices
  // lead.  We thus push the pointer to a sequence of operands, and then follow
  // the indices, pushing each to the operand list and tracking the type
  // obtained by following it.  Ultimately this yields the type of the
  // component reached by following all the indices, and the result type is
  // a pointer to this component type.
  opt::Instruction::OperandList operands;

  // Add the pointer id itself.
  operands.push_back({SPV_OPERAND_TYPE_ID, {message_.pointer_id()}});

  // Start walking the indices, starting with the pointer's base type.
  auto pointer_type = ir_context->get_def_use_mgr()->GetDef(
      ir_context->get_def_use_mgr()->GetDef(message_.pointer_id())->type_id());
  uint32_t subobject_type_id = pointer_type->GetSingleWordInOperand(1);

  uint32_t id_pairs_used = 0;

  // Go through the index ids in turn.
  for (auto index_id : message_.index_id()) {
    uint32_t index_value;

    // Actual id to be used in the instruction: the original id
    // or the clamped one.
    uint32_t new_index_id;

    // Check whether the object is a struct.
    if (ir_context->get_def_use_mgr()->GetDef(subobject_type_id)->opcode() ==
        SpvOpTypeStruct) {
      // It is a struct: we need to retrieve the integer value.

      index_value =
          GetIndexValue(ir_context, index_id, subobject_type_id).second;

      new_index_id = index_id;

    } else {
      // It is not a struct: the index will need clamping.

      // Get two new ids to use and update the amount used.
      protobufs::UInt32Pair fresh_ids =
          message_.fresh_ids_for_clamping()[id_pairs_used++];

      // Perform the clamping using the fresh ids at our disposal.
      // The module will not be changed if |add_clamping_instructions| is not
      // set.
      auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);

      uint32_t bound = fuzzerutil::GetBoundForCompositeIndex(
          *ir_context->get_def_use_mgr()->GetDef(subobject_type_id),
          ir_context);

      auto bound_minus_one_id =
          fuzzerutil::MaybeGetIntegerConstantFromValueAndType(
              ir_context, bound - 1, index_instruction->type_id());

      assert(bound_minus_one_id &&
             "A constant of value bound - 1 and the same type as the index "
             "must exist as a precondition.");

      uint32_t bool_type_id = fuzzerutil::MaybeGetBoolType(ir_context);

      assert(bool_type_id &&
             "An OpTypeBool instruction must exist as a precondition.");

      auto int_type_inst =
          ir_context->get_def_use_mgr()->GetDef(index_instruction->type_id());

      // Clamp the integer and add the corresponding instructions in the module
      // if |add_clamping_instructions| is set.
      auto instruction_to_insert_before =
          FindInstruction(message_.instruction_to_insert_before(), ir_context);

      // Compare the index with the bound via an instruction of the form:
      //   %fresh_ids.first = OpULessThanEqual %bool %int_id %bound_minus_one.
      fuzzerutil::UpdateModuleIdBound(ir_context, fresh_ids.first());
      instruction_to_insert_before->InsertBefore(MakeUnique<opt::Instruction>(
          ir_context, SpvOpULessThanEqual, bool_type_id, fresh_ids.first(),
          opt::Instruction::OperandList(
              {{SPV_OPERAND_TYPE_ID, {index_instruction->result_id()}},
               {SPV_OPERAND_TYPE_ID, {bound_minus_one_id}}})));

      // Select the index if in-bounds, otherwise one less than the bound:
      //   %fresh_ids.second = OpSelect %int_type %fresh_ids.first %int_id
      //                           %bound_minus_one
      fuzzerutil::UpdateModuleIdBound(ir_context, fresh_ids.second());
      instruction_to_insert_before->InsertBefore(MakeUnique<opt::Instruction>(
          ir_context, SpvOpSelect, int_type_inst->result_id(),
          fresh_ids.second(),
          opt::Instruction::OperandList(
              {{SPV_OPERAND_TYPE_ID, {fresh_ids.first()}},
               {SPV_OPERAND_TYPE_ID, {index_instruction->result_id()}},
               {SPV_OPERAND_TYPE_ID, {bound_minus_one_id}}})));

      new_index_id = fresh_ids.second();

      index_value = 0;
    }

    // Add the correct index id to the operands.
    operands.push_back({SPV_OPERAND_TYPE_ID, {new_index_id}});

    // Walk to the next type in the composite object using this index.
    subobject_type_id = fuzzerutil::WalkOneCompositeTypeIndex(
        ir_context, subobject_type_id, index_value);
  }
  // The access chain's result type is a pointer to the composite component
  // that was reached after following all indices.  The storage class is that
  // of the original pointer.
  uint32_t result_type = fuzzerutil::MaybeGetPointerType(
      ir_context, subobject_type_id,
      static_cast<SpvStorageClass>(pointer_type->GetSingleWordInOperand(0)));

  // Add the access chain instruction to the module, and update the module's
  // id bound.
  fuzzerutil::UpdateModuleIdBound(ir_context, message_.fresh_id());
  FindInstruction(message_.instruction_to_insert_before(), ir_context)
      ->InsertBefore(MakeUnique<opt::Instruction>(
          ir_context, SpvOpAccessChain, result_type, message_.fresh_id(),
          operands));

  // Conservatively invalidate all analyses.
  ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);

  // If the base pointer's pointee value was irrelevant, the same is true of
  // the pointee value of the result of this access chain.
  if (transformation_context->GetFactManager()->PointeeValueIsIrrelevant(
          message_.pointer_id())) {
    transformation_context->GetFactManager()->AddFactValueOfPointeeIsIrrelevant(
        message_.fresh_id());
  }
}

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

std::pair<bool, uint32_t> TransformationAccessChain::GetIndexValue(
    opt::IRContext* ir_context, uint32_t index_id,
    uint32_t object_type_id) const {
  if (!ValidIndexToComposite(ir_context, index_id, object_type_id)) {
    return {false, 0};
  }
  auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);

  uint32_t bound = fuzzerutil::GetBoundForCompositeIndex(
      *ir_context->get_def_use_mgr()->GetDef(object_type_id), ir_context);

  // The index must be a constant
  if (!spvOpcodeIsConstant(index_instruction->opcode())) {
    return {false, 0};
  }

  // The index must be in bounds.
  uint32_t value = index_instruction->GetSingleWordInOperand(0);

  if (value >= bound) {
    return {false, 0};
  }

  return {true, value};
}

bool TransformationAccessChain::ValidIndexToComposite(
    opt::IRContext* ir_context, uint32_t index_id, uint32_t object_type_id) {
  auto object_type_def = ir_context->get_def_use_mgr()->GetDef(object_type_id);
  // The object being indexed must be a composite.
  if (!spvOpcodeIsComposite(object_type_def->opcode())) {
    return false;
  }

  // Get the defining instruction of the index.
  auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);
  if (!index_instruction) {
    return false;
  }

  // The index type must be 32-bit integer.
  auto index_type =
      ir_context->get_def_use_mgr()->GetDef(index_instruction->type_id());
  if (index_type->opcode() != SpvOpTypeInt ||
      index_type->GetSingleWordInOperand(0) != 32) {
    return false;
  }

  // If the object being traversed is a struct, the id must correspond to an
  // in-bound constant.
  if (object_type_def->opcode() == SpvOpTypeStruct) {
    if (!spvOpcodeIsConstant(index_instruction->opcode())) {
      return false;
    }
  }
  return true;
}

std::unordered_set<uint32_t> TransformationAccessChain::GetFreshIds() const {
  std::unordered_set<uint32_t> result = {message_.fresh_id()};
  for (auto& fresh_ids_for_clamping : message_.fresh_ids_for_clamping()) {
    result.insert(fresh_ids_for_clamping.first());
    result.insert(fresh_ids_for_clamping.second());
  }
  return result;
}

}  // namespace fuzz
}  // namespace spvtools