source/fuzz/transformation_composite_insert.cpp

   1 // Copyright (c) 2020 Google LLC
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 #include "transformation_composite_insert.h"
  16
  17 #include "source/fuzz/fuzzer_util.h"
  18 #include "source/fuzz/instruction_descriptor.h"
  19
  20 namespace spvtools {
  21 namespace fuzz {
  22
  23 TransformationCompositeInsert::TransformationCompositeInsert(
  24     protobufs::TransformationCompositeInsert message)
  25     : message_(std::move(message)) {}
  26
  27 TransformationCompositeInsert::TransformationCompositeInsert(
  28     const protobufs::InstructionDescriptor& instruction_to_insert_before,
  29     uint32_t fresh_id, uint32_t composite_id, uint32_t object_id,
  30     const std::vector<uint32_t>& index) {
  31   *message_.mutable_instruction_to_insert_before() =
  32       instruction_to_insert_before;
  33   message_.set_fresh_id(fresh_id);
  34   message_.set_composite_id(composite_id);
  35   message_.set_object_id(object_id);
  36   for (auto an_index : index) {
  37     message_.add_index(an_index);
  38   }
  39 }
  40
  41 bool TransformationCompositeInsert::IsApplicable(
  42     opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
  43   // |message_.fresh_id| must be fresh.
  44   if (!fuzzerutil::IsFreshId(ir_context, message_.fresh_id())) {
  45     return false;
  46   }
  47
  48   // |message_.composite_id| must refer to an existing composite value.
  49   auto composite =
  50       ir_context->get_def_use_mgr()->GetDef(message_.composite_id());
  51
  52   if (!IsCompositeInstructionSupported(ir_context, composite)) {
  53     return false;
  54   }
  55
  56   // The indices in |message_.index| must be suitable for indexing into
  57   // |composite->type_id()|.
  58   auto component_to_be_replaced_type_id = fuzzerutil::WalkCompositeTypeIndices(
  59       ir_context, composite->type_id(), message_.index());
  60   if (component_to_be_replaced_type_id == 0) {
  61     return false;
  62   }
  63
  64   // The instruction having the id of |message_.object_id| must be defined.
  65   auto object_instruction =
  66       ir_context->get_def_use_mgr()->GetDef(message_.object_id());
  67   if (object_instruction == nullptr || object_instruction->type_id() == 0) {
  68     return false;
  69   }
  70
  71   // We ignore pointers for now.
  72   auto object_instruction_type =
  73       ir_context->get_type_mgr()->GetType(object_instruction->type_id());
  74   if (object_instruction_type->AsPointer() != nullptr) {
  75     return false;
  76   }
  77
  78   // The type id of the object having |message_.object_id| and the type id of
  79   // the component of the composite at index |message_.index| must be the same.
  80   if (component_to_be_replaced_type_id != object_instruction->type_id()) {
  81     return false;
  82   }
  83
  84   // |message_.instruction_to_insert_before| must be a defined instruction.
  85   auto instruction_to_insert_before =
  86       FindInstruction(message_.instruction_to_insert_before(), ir_context);
  87   if (instruction_to_insert_before == nullptr) {
  88     return false;
  89   }
  90
  91   // |message_.composite_id| and |message_.object_id| must be available before
  92   // the |message_.instruction_to_insert_before|.
  93   if (!fuzzerutil::IdIsAvailableBeforeInstruction(
  94           ir_context, instruction_to_insert_before, message_.composite_id())) {
  95     return false;
  96   }
  97   if (!fuzzerutil::IdIsAvailableBeforeInstruction(
  98           ir_context, instruction_to_insert_before, message_.object_id())) {
  99     return false;
 100   }
 101
 102   // It must be possible to insert an OpCompositeInsert before this
 103   // instruction.
 104   return fuzzerutil::CanInsertOpcodeBeforeInstruction(
 105       spv::Op::OpCompositeInsert, instruction_to_insert_before);
 106 }
 107
 108 void TransformationCompositeInsert::Apply(
 109     opt::IRContext* ir_context,
 110     TransformationContext* transformation_context) const {
 111   // |message_.struct_fresh_id| must be fresh.
 112   assert(fuzzerutil::IsFreshId(ir_context, message_.fresh_id()) &&
 113          "|message_.fresh_id| must be fresh");
 114
 115   std::vector<uint32_t> index =
 116       fuzzerutil::RepeatedFieldToVector(message_.index());
 117   opt::Instruction::OperandList in_operands;
 118   in_operands.push_back({SPV_OPERAND_TYPE_ID, {message_.object_id()}});
 119   in_operands.push_back({SPV_OPERAND_TYPE_ID, {message_.composite_id()}});
 120   for (auto i : index) {
 121     in_operands.push_back({SPV_OPERAND_TYPE_LITERAL_INTEGER, {i}});
 122   }
 123   auto composite_type_id =
 124       fuzzerutil::GetTypeId(ir_context, message_.composite_id());
 125
 126   auto insert_before =
 127       FindInstruction(message_.instruction_to_insert_before(), ir_context);
 128   auto new_instruction = MakeUnique<opt::Instruction>(
 129       ir_context, spv::Op::OpCompositeInsert, composite_type_id,
 130       message_.fresh_id(), std::move(in_operands));
 131   auto new_instruction_ptr = new_instruction.get();
 132   insert_before->InsertBefore(std::move(new_instruction));
 133
 134   fuzzerutil::UpdateModuleIdBound(ir_context, message_.fresh_id());
 135
 136   // Inform the def-use manager about the new instruction and record its basic
 137   // block.
 138   ir_context->get_def_use_mgr()->AnalyzeInstDefUse(new_instruction_ptr);
 139   ir_context->set_instr_block(new_instruction_ptr,
 140                               ir_context->get_instr_block(insert_before));
 141
 142   // Add data synonym facts that arise from the insertion.
 143   AddDataSynonymFacts(ir_context, transformation_context);
 144 }
 145
 146 protobufs::Transformation TransformationCompositeInsert::ToMessage() const {
 147   protobufs::Transformation result;
 148   *result.mutable_composite_insert() = message_;
 149   return result;
 150 }
 151
 152 bool TransformationCompositeInsert::IsCompositeInstructionSupported(
 153     opt::IRContext* ir_context, opt::Instruction* instruction) {
 154   if (instruction == nullptr) {
 155     return false;
 156   }
 157   if (instruction->result_id() == 0 || instruction->type_id() == 0) {
 158     return false;
 159   }
 160   auto composite_type =
 161       ir_context->get_type_mgr()->GetType(instruction->type_id());
 162   if (!fuzzerutil::IsCompositeType(composite_type)) {
 163     return false;
 164   }
 165
 166   // Empty composites are not supported.
 167   auto instruction_type_inst =
 168       ir_context->get_def_use_mgr()->GetDef(instruction->type_id());
 169   if (fuzzerutil::GetBoundForCompositeIndex(*instruction_type_inst,
 170                                             ir_context) == 0) {
 171     return false;
 172   }
 173   return true;
 174 }
 175
 176 std::unordered_set<uint32_t> TransformationCompositeInsert::GetFreshIds()
 177     const {
 178   return {message_.fresh_id()};
 179 }
 180
 181 void TransformationCompositeInsert::AddDataSynonymFacts(
 182     opt::IRContext* ir_context,
 183     TransformationContext* transformation_context) const {
 184   // If the result id arising from the insertion is irrelevant then do not add
 185   // any data synonym facts.  (The result id can be irrelevant if the insertion
 186   // occurs in a dead block.)
 187   if (transformation_context->GetFactManager()->IdIsIrrelevant(
 188           message_.fresh_id())) {
 189     return;
 190   }
 191
 192   // So long as the |message_.composite_id| is suitable for participating in
 193   // synonyms, every every element of the insertion result except for at the
 194   // index being inserted into is synonymous with the corresponding element of
 195   // |message_.composite_id|.  In that case, for every index that is a prefix of
 196   // |index|, the components different from the one that contains the inserted
 197   // object are synonymous with corresponding elements in the original
 198   // composite.
 199   uint32_t current_node_type_id =
 200       fuzzerutil::GetTypeId(ir_context, message_.composite_id());
 201   std::vector<uint32_t> current_index;
 202
 203   std::vector<uint32_t> index =
 204       fuzzerutil::RepeatedFieldToVector(message_.index());
 205
 206   for (uint32_t current_level : index) {
 207     auto current_node_type_inst =
 208         ir_context->get_def_use_mgr()->GetDef(current_node_type_id);
 209     uint32_t index_to_skip = current_level;
 210     uint32_t num_of_components = fuzzerutil::GetBoundForCompositeIndex(
 211         *current_node_type_inst, ir_context);
 212
 213     // Update the current_node_type_id.
 214     current_node_type_id = fuzzerutil::WalkOneCompositeTypeIndex(
 215         ir_context, current_node_type_id, index_to_skip);
 216
 217     for (uint32_t i = 0; i < num_of_components; i++) {
 218       if (i == index_to_skip) {
 219         continue;
 220       }
 221       current_index.push_back(i);
 222       if (fuzzerutil::CanMakeSynonymOf(ir_context, *transformation_context,
 223                                        *ir_context->get_def_use_mgr()->GetDef(
 224                                            message_.composite_id()))) {
 225         transformation_context->GetFactManager()->AddFactDataSynonym(
 226             MakeDataDescriptor(message_.fresh_id(), current_index),
 227             MakeDataDescriptor(message_.composite_id(), current_index));
 228       }
 229       current_index.pop_back();
 230     }
 231     // Store the prefix of the |index|.
 232     current_index.push_back(current_level);
 233   }
 234   // If the object being inserted supports synonym creation then it is
 235   // synonymous with the result of the insert instruction at the given index.
 236   if (fuzzerutil::CanMakeSynonymOf(
 237           ir_context, *transformation_context,
 238           *ir_context->get_def_use_mgr()->GetDef(message_.object_id()))) {
 239     transformation_context->GetFactManager()->AddFactDataSynonym(
 240         MakeDataDescriptor(message_.object_id(), {}),
 241         MakeDataDescriptor(message_.fresh_id(), index));
 242   }
 243 }
 244
 245 }  // namespace fuzz
 246 }  // namespace spvtools