source/fuzz/transformation_access_chain.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 "source/fuzz/transformation_access_chain.h"
  16
  17 #include <vector>
  18
  19 #include "source/fuzz/fuzzer_util.h"
  20 #include "source/fuzz/instruction_descriptor.h"
  21
  22 namespace spvtools {
  23 namespace fuzz {
  24
  25 TransformationAccessChain::TransformationAccessChain(
  26     protobufs::TransformationAccessChain message)
  27     : message_(std::move(message)) {}
  28
  29 TransformationAccessChain::TransformationAccessChain(
  30     uint32_t fresh_id, uint32_t pointer_id,
  31     const std::vector<uint32_t>& index_id,
  32     const protobufs::InstructionDescriptor& instruction_to_insert_before,
  33     const std::vector<std::pair<uint32_t, uint32_t>>& fresh_ids_for_clamping) {
  34   message_.set_fresh_id(fresh_id);
  35   message_.set_pointer_id(pointer_id);
  36   for (auto id : index_id) {
  37     message_.add_index_id(id);
  38   }
  39   *message_.mutable_instruction_to_insert_before() =
  40       instruction_to_insert_before;
  41   for (auto clamping_ids_pair : fresh_ids_for_clamping) {
  42     protobufs::UInt32Pair pair;
  43     pair.set_first(clamping_ids_pair.first);
  44     pair.set_second(clamping_ids_pair.second);
  45     *message_.add_fresh_ids_for_clamping() = pair;
  46   }
  47 }
  48
  49 bool TransformationAccessChain::IsApplicable(
  50     opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
  51   // Keep track of the fresh ids used to make sure that they are distinct.
  52   std::set<uint32_t> fresh_ids_used;
  53
  54   // The result id must be fresh.
  55   if (!CheckIdIsFreshAndNotUsedByThisTransformation(
  56           message_.fresh_id(), ir_context, &fresh_ids_used)) {
  57     return false;
  58   }
  59   // The pointer id must exist and have a type.
  60   auto pointer = ir_context->get_def_use_mgr()->GetDef(message_.pointer_id());
  61   if (!pointer || !pointer->type_id()) {
  62     return false;
  63   }
  64   // The type must indeed be a pointer.
  65   auto pointer_type = ir_context->get_def_use_mgr()->GetDef(pointer->type_id());
  66   if (pointer_type->opcode() != spv::Op::OpTypePointer) {
  67     return false;
  68   }
  69
  70   // The described instruction to insert before must exist and be a suitable
  71   // point where an OpAccessChain instruction could be inserted.
  72   auto instruction_to_insert_before =
  73       FindInstruction(message_.instruction_to_insert_before(), ir_context);
  74   if (!instruction_to_insert_before) {
  75     return false;
  76   }
  77   if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(
  78           spv::Op::OpAccessChain, instruction_to_insert_before)) {
  79     return false;
  80   }
  81
  82   // Do not allow making an access chain from a null or undefined pointer, as
  83   // we do not want to allow accessing such pointers.  This might be acceptable
  84   // in dead blocks, but we conservatively avoid it.
  85   switch (pointer->opcode()) {
  86     case spv::Op::OpConstantNull:
  87     case spv::Op::OpUndef:
  88       assert(
  89           false &&
  90           "Access chains should not be created from null/undefined pointers");
  91       return false;
  92     default:
  93       break;
  94   }
  95
  96   // The pointer on which the access chain is to be based needs to be available
  97   // (according to dominance rules) at the insertion point.
  98   if (!fuzzerutil::IdIsAvailableBeforeInstruction(
  99           ir_context, instruction_to_insert_before, message_.pointer_id())) {
 100     return false;
 101   }
 102
 103   // We now need to use the given indices to walk the type structure of the
 104   // base type of the pointer, making sure that (a) the indices correspond to
 105   // integers, and (b) these integer values are in-bounds.
 106
 107   // Start from the base type of the pointer.
 108   uint32_t subobject_type_id = pointer_type->GetSingleWordInOperand(1);
 109
 110   int id_pairs_used = 0;
 111
 112   // Consider the given index ids in turn.
 113   for (auto index_id : message_.index_id()) {
 114     // The index value will correspond to the value of the index if the object
 115     // is a struct, otherwise the value 0 will be used.
 116     uint32_t index_value;
 117
 118     // Check whether the object is a struct.
 119     if (ir_context->get_def_use_mgr()->GetDef(subobject_type_id)->opcode() ==
 120         spv::Op::OpTypeStruct) {
 121       // It is a struct: we need to retrieve the integer value.
 122
 123       bool successful;
 124       std::tie(successful, index_value) =
 125           GetStructIndexValue(ir_context, index_id, subobject_type_id);
 126
 127       if (!successful) {
 128         return false;
 129       }
 130     } else {
 131       // It is not a struct: the index will need clamping.
 132
 133       if (message_.fresh_ids_for_clamping().size() <= id_pairs_used) {
 134         // We don't have enough ids
 135         return false;
 136       }
 137
 138       // Get two new ids to use and update the amount used.
 139       protobufs::UInt32Pair fresh_ids =
 140           message_.fresh_ids_for_clamping()[id_pairs_used++];
 141
 142       // Valid ids need to have been given
 143       if (fresh_ids.first() == 0 || fresh_ids.second() == 0) {
 144         return false;
 145       }
 146
 147       // Check that the ids are actually fresh and not already used by this
 148       // transformation.
 149       if (!CheckIdIsFreshAndNotUsedByThisTransformation(
 150               fresh_ids.first(), ir_context, &fresh_ids_used) ||
 151           !CheckIdIsFreshAndNotUsedByThisTransformation(
 152               fresh_ids.second(), ir_context, &fresh_ids_used)) {
 153         return false;
 154       }
 155
 156       if (!ValidIndexToComposite(ir_context, index_id, subobject_type_id)) {
 157         return false;
 158       }
 159
 160       // Perform the clamping using the fresh ids at our disposal.
 161       auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);
 162
 163       uint32_t bound = fuzzerutil::GetBoundForCompositeIndex(
 164           *ir_context->get_def_use_mgr()->GetDef(subobject_type_id),
 165           ir_context);
 166
 167       // The module must have an integer constant of value bound-1 of the same
 168       // type as the index.
 169       if (!fuzzerutil::MaybeGetIntegerConstantFromValueAndType(
 170               ir_context, bound - 1, index_instruction->type_id())) {
 171         return false;
 172       }
 173
 174       // The module must have the definition of bool type to make a comparison.
 175       if (!fuzzerutil::MaybeGetBoolType(ir_context)) {
 176         return false;
 177       }
 178
 179       // The index is not necessarily a constant, so we may not know its value.
 180       // We can use index 0 because the components of a non-struct composite
 181       // all have the same type, and index 0 is always in bounds.
 182       index_value = 0;
 183     }
 184
 185     // Try to walk down the type using this index.  This will yield 0 if the
 186     // type is not a composite or the index is out of bounds, and the id of
 187     // the next type otherwise.
 188     subobject_type_id = fuzzerutil::WalkOneCompositeTypeIndex(
 189         ir_context, subobject_type_id, index_value);
 190     if (!subobject_type_id) {
 191       // Either the type was not a composite (so that too many indices were
 192       // provided), or the index was out of bounds.
 193       return false;
 194     }
 195   }
 196   // At this point, |subobject_type_id| is the type of the value targeted by
 197   // the new access chain.  The result type of the access chain should be a
 198   // pointer to this type, with the same storage class as for the original
 199   // pointer.  Such a pointer type needs to exist in the module.
 200   //
 201   // We do not use the type manager to look up this type, due to problems
 202   // associated with pointers to isomorphic structs being regarded as the same.
 203   return fuzzerutil::MaybeGetPointerType(
 204              ir_context, subobject_type_id,
 205              static_cast<spv::StorageClass>(
 206                  pointer_type->GetSingleWordInOperand(0))) != 0;
 207 }
 208
 209 void TransformationAccessChain::Apply(
 210     opt::IRContext* ir_context,
 211     TransformationContext* transformation_context) const {
 212   // The operands to the access chain are the pointer followed by the indices.
 213   // The result type of the access chain is determined by where the indices
 214   // lead.  We thus push the pointer to a sequence of operands, and then follow
 215   // the indices, pushing each to the operand list and tracking the type
 216   // obtained by following it.  Ultimately this yields the type of the
 217   // component reached by following all the indices, and the result type is
 218   // a pointer to this component type.
 219   opt::Instruction::OperandList operands;
 220
 221   // Add the pointer id itself.
 222   operands.push_back({SPV_OPERAND_TYPE_ID, {message_.pointer_id()}});
 223
 224   // Start walking the indices, starting with the pointer's base type.
 225   auto pointer_type = ir_context->get_def_use_mgr()->GetDef(
 226       ir_context->get_def_use_mgr()->GetDef(message_.pointer_id())->type_id());
 227   uint32_t subobject_type_id = pointer_type->GetSingleWordInOperand(1);
 228
 229   uint32_t id_pairs_used = 0;
 230
 231   opt::Instruction* instruction_to_insert_before =
 232       FindInstruction(message_.instruction_to_insert_before(), ir_context);
 233   opt::BasicBlock* enclosing_block =
 234       ir_context->get_instr_block(instruction_to_insert_before);
 235
 236   // Go through the index ids in turn.
 237   for (auto index_id : message_.index_id()) {
 238     uint32_t index_value;
 239
 240     // Actual id to be used in the instruction: the original id
 241     // or the clamped one.
 242     uint32_t new_index_id;
 243
 244     // Check whether the object is a struct.
 245     if (ir_context->get_def_use_mgr()->GetDef(subobject_type_id)->opcode() ==
 246         spv::Op::OpTypeStruct) {
 247       // It is a struct: we need to retrieve the integer value.
 248
 249       index_value =
 250           GetStructIndexValue(ir_context, index_id, subobject_type_id).second;
 251
 252       new_index_id = index_id;
 253
 254     } else {
 255       // It is not a struct: the index will need clamping.
 256
 257       // Get two new ids to use and update the amount used.
 258       protobufs::UInt32Pair fresh_ids =
 259           message_.fresh_ids_for_clamping()[id_pairs_used++];
 260
 261       // Perform the clamping using the fresh ids at our disposal.
 262       // The module will not be changed if |add_clamping_instructions| is not
 263       // set.
 264       auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);
 265
 266       uint32_t bound = fuzzerutil::GetBoundForCompositeIndex(
 267           *ir_context->get_def_use_mgr()->GetDef(subobject_type_id),
 268           ir_context);
 269
 270       auto bound_minus_one_id =
 271           fuzzerutil::MaybeGetIntegerConstantFromValueAndType(
 272               ir_context, bound - 1, index_instruction->type_id());
 273
 274       assert(bound_minus_one_id &&
 275              "A constant of value bound - 1 and the same type as the index "
 276              "must exist as a precondition.");
 277
 278       uint32_t bool_type_id = fuzzerutil::MaybeGetBoolType(ir_context);
 279
 280       assert(bool_type_id &&
 281              "An OpTypeBool instruction must exist as a precondition.");
 282
 283       auto int_type_inst =
 284           ir_context->get_def_use_mgr()->GetDef(index_instruction->type_id());
 285
 286       // Clamp the integer and add the corresponding instructions in the module
 287       // if |add_clamping_instructions| is set.
 288
 289       // Compare the index with the bound via an instruction of the form:
 290       //   %fresh_ids.first = OpULessThanEqual %bool %int_id %bound_minus_one.
 291       fuzzerutil::UpdateModuleIdBound(ir_context, fresh_ids.first());
 292       auto comparison_instruction = MakeUnique<opt::Instruction>(
 293           ir_context, spv::Op::OpULessThanEqual, bool_type_id,
 294           fresh_ids.first(),
 295           opt::Instruction::OperandList(
 296               {{SPV_OPERAND_TYPE_ID, {index_instruction->result_id()}},
 297                {SPV_OPERAND_TYPE_ID, {bound_minus_one_id}}}));
 298       auto comparison_instruction_ptr = comparison_instruction.get();
 299       instruction_to_insert_before->InsertBefore(
 300           std::move(comparison_instruction));
 301       ir_context->get_def_use_mgr()->AnalyzeInstDefUse(
 302           comparison_instruction_ptr);
 303       ir_context->set_instr_block(comparison_instruction_ptr, enclosing_block);
 304
 305       // Select the index if in-bounds, otherwise one less than the bound:
 306       //   %fresh_ids.second = OpSelect %int_type %fresh_ids.first %int_id
 307       //                           %bound_minus_one
 308       fuzzerutil::UpdateModuleIdBound(ir_context, fresh_ids.second());
 309       auto select_instruction = MakeUnique<opt::Instruction>(
 310           ir_context, spv::Op::OpSelect, int_type_inst->result_id(),
 311           fresh_ids.second(),
 312           opt::Instruction::OperandList(
 313               {{SPV_OPERAND_TYPE_ID, {fresh_ids.first()}},
 314                {SPV_OPERAND_TYPE_ID, {index_instruction->result_id()}},
 315                {SPV_OPERAND_TYPE_ID, {bound_minus_one_id}}}));
 316       auto select_instruction_ptr = select_instruction.get();
 317       instruction_to_insert_before->InsertBefore(std::move(select_instruction));
 318       ir_context->get_def_use_mgr()->AnalyzeInstDefUse(select_instruction_ptr);
 319       ir_context->set_instr_block(select_instruction_ptr, enclosing_block);
 320
 321       new_index_id = fresh_ids.second();
 322
 323       index_value = 0;
 324     }
 325
 326     // Add the correct index id to the operands.
 327     operands.push_back({SPV_OPERAND_TYPE_ID, {new_index_id}});
 328
 329     // Walk to the next type in the composite object using this index.
 330     subobject_type_id = fuzzerutil::WalkOneCompositeTypeIndex(
 331         ir_context, subobject_type_id, index_value);
 332   }
 333   // The access chain's result type is a pointer to the composite component
 334   // that was reached after following all indices.  The storage class is that
 335   // of the original pointer.
 336   uint32_t result_type = fuzzerutil::MaybeGetPointerType(
 337       ir_context, subobject_type_id,
 338       static_cast<spv::StorageClass>(pointer_type->GetSingleWordInOperand(0)));
 339
 340   // Add the access chain instruction to the module, and update the module's
 341   // id bound.
 342   fuzzerutil::UpdateModuleIdBound(ir_context, message_.fresh_id());
 343   auto access_chain_instruction =
 344       MakeUnique<opt::Instruction>(ir_context, spv::Op::OpAccessChain,
 345                                    result_type, message_.fresh_id(), operands);
 346   auto access_chain_instruction_ptr = access_chain_instruction.get();
 347   instruction_to_insert_before->InsertBefore(
 348       std::move(access_chain_instruction));
 349   ir_context->get_def_use_mgr()->AnalyzeInstDefUse(
 350       access_chain_instruction_ptr);
 351   ir_context->set_instr_block(access_chain_instruction_ptr, enclosing_block);
 352
 353   // If the base pointer's pointee value was irrelevant, the same is true of
 354   // the pointee value of the result of this access chain.
 355   if (transformation_context->GetFactManager()->PointeeValueIsIrrelevant(
 356           message_.pointer_id())) {
 357     transformation_context->GetFactManager()->AddFactValueOfPointeeIsIrrelevant(
 358         message_.fresh_id());
 359   }
 360 }
 361
 362 protobufs::Transformation TransformationAccessChain::ToMessage() const {
 363   protobufs::Transformation result;
 364   *result.mutable_access_chain() = message_;
 365   return result;
 366 }
 367
 368 std::pair<bool, uint32_t> TransformationAccessChain::GetStructIndexValue(
 369     opt::IRContext* ir_context, uint32_t index_id,
 370     uint32_t object_type_id) const {
 371   assert(ir_context->get_def_use_mgr()->GetDef(object_type_id)->opcode() ==
 372              spv::Op::OpTypeStruct &&
 373          "Precondition: the type must be a struct type.");
 374   if (!ValidIndexToComposite(ir_context, index_id, object_type_id)) {
 375     return {false, 0};
 376   }
 377   auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);
 378
 379   uint32_t bound = fuzzerutil::GetBoundForCompositeIndex(
 380       *ir_context->get_def_use_mgr()->GetDef(object_type_id), ir_context);
 381
 382   // Ensure that the index given must represent a constant.
 383   assert(spvOpcodeIsConstant(index_instruction->opcode()) &&
 384          "A non-constant index should already have been rejected.");
 385
 386   // The index must be in bounds.
 387   uint32_t value = index_instruction->GetSingleWordInOperand(0);
 388
 389   if (value >= bound) {
 390     return {false, 0};
 391   }
 392
 393   return {true, value};
 394 }
 395
 396 bool TransformationAccessChain::ValidIndexToComposite(
 397     opt::IRContext* ir_context, uint32_t index_id, uint32_t object_type_id) {
 398   auto object_type_def = ir_context->get_def_use_mgr()->GetDef(object_type_id);
 399   // The object being indexed must be a composite.
 400   if (!spvOpcodeIsComposite(object_type_def->opcode())) {
 401     return false;
 402   }
 403
 404   // Get the defining instruction of the index.
 405   auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);
 406   if (!index_instruction) {
 407     return false;
 408   }
 409
 410   // The index type must be 32-bit integer.
 411   auto index_type =
 412       ir_context->get_def_use_mgr()->GetDef(index_instruction->type_id());
 413   if (index_type->opcode() != spv::Op::OpTypeInt ||
 414       index_type->GetSingleWordInOperand(0) != 32) {
 415     return false;
 416   }
 417
 418   // If the object being traversed is a struct, the id must correspond to an
 419   // in-bound constant.
 420   if (object_type_def->opcode() == spv::Op::OpTypeStruct) {
 421     if (!spvOpcodeIsConstant(index_instruction->opcode())) {
 422       return false;
 423     }
 424   }
 425   return true;
 426 }
 427
 428 std::unordered_set<uint32_t> TransformationAccessChain::GetFreshIds() const {
 429   std::unordered_set<uint32_t> result = {message_.fresh_id()};
 430   for (auto& fresh_ids_for_clamping : message_.fresh_ids_for_clamping()) {
 431     result.insert(fresh_ids_for_clamping.first());
 432     result.insert(fresh_ids_for_clamping.second());
 433   }
 434   return result;
 435 }
 436
 437 }  // namespace fuzz
 438 }  // namespace spvtools