source/fuzz/fuzzer_pass_construct_composites.cpp

   1 // Copyright (c) 2019 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/fuzzer_pass_construct_composites.h"
  16
  17 #include <memory>
  18
  19 #include "source/fuzz/available_instructions.h"
  20 #include "source/fuzz/fuzzer_util.h"
  21 #include "source/fuzz/transformation_composite_construct.h"
  22
  23 namespace spvtools {
  24 namespace fuzz {
  25
  26 FuzzerPassConstructComposites::FuzzerPassConstructComposites(
  27     opt::IRContext* ir_context, TransformationContext* transformation_context,
  28     FuzzerContext* fuzzer_context,
  29     protobufs::TransformationSequence* transformations,
  30     bool ignore_inapplicable_transformations)
  31     : FuzzerPass(ir_context, transformation_context, fuzzer_context,
  32                  transformations, ignore_inapplicable_transformations) {}
  33
  34 void FuzzerPassConstructComposites::Apply() {
  35   // Gather up the ids of all composite types, but skip block-/buffer
  36   // block-decorated struct types.
  37   std::vector<uint32_t> composite_type_ids;
  38   for (auto& inst : GetIRContext()->types_values()) {
  39     if (fuzzerutil::IsCompositeType(
  40             GetIRContext()->get_type_mgr()->GetType(inst.result_id())) &&
  41         !fuzzerutil::HasBlockOrBufferBlockDecoration(GetIRContext(),
  42                                                      inst.result_id())) {
  43       composite_type_ids.push_back(inst.result_id());
  44     }
  45   }
  46
  47   if (composite_type_ids.empty()) {
  48     // There are no composite types, so this fuzzer pass cannot do anything.
  49     return;
  50   }
  51
  52   AvailableInstructions available_composite_constituents(
  53       GetIRContext(),
  54       [this](opt::IRContext* ir_context, opt::Instruction* inst) -> bool {
  55         if (!inst->result_id() || !inst->type_id()) {
  56           return false;
  57         }
  58
  59         // If the id is irrelevant, we can use it since it will not
  60         // participate in DataSynonym fact. Otherwise, we should be able
  61         // to produce a synonym out of the id.
  62         return GetTransformationContext()->GetFactManager()->IdIsIrrelevant(
  63                    inst->result_id()) ||
  64                fuzzerutil::CanMakeSynonymOf(ir_context,
  65                                             *GetTransformationContext(), *inst);
  66       });
  67
  68   ForEachInstructionWithInstructionDescriptor(
  69       [this, &available_composite_constituents, &composite_type_ids](
  70           opt::Function* /*unused*/, opt::BasicBlock* /*unused*/,
  71           opt::BasicBlock::iterator inst_it,
  72           const protobufs::InstructionDescriptor& instruction_descriptor)
  73           -> void {
  74         // Randomly decide whether to try inserting a composite construction
  75         // here.
  76         if (!GetFuzzerContext()->ChoosePercentage(
  77                 GetFuzzerContext()->GetChanceOfConstructingComposite())) {
  78           return;
  79         }
  80
  81         // Check whether it is legitimate to insert a composite construction
  82         // before the instruction.
  83         if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(
  84                 spv::Op::OpCompositeConstruct, inst_it)) {
  85           return;
  86         }
  87
  88         // For each instruction that is available at this program point (i.e. an
  89         // instruction that is global or whose definition strictly dominates the
  90         // program point) and suitable for making a synonym of, associate it
  91         // with the id of its result type.
  92         TypeIdToInstructions type_id_to_available_instructions;
  93         auto available_instructions =
  94             available_composite_constituents.GetAvailableBeforeInstruction(
  95                 &*inst_it);
  96         for (uint32_t available_instruction_index = 0;
  97              available_instruction_index < available_instructions.size();
  98              available_instruction_index++) {
  99           opt::Instruction* inst =
 100               available_instructions[available_instruction_index];
 101           type_id_to_available_instructions[inst->type_id()].push_back(
 102               inst->result_id());
 103         }
 104
 105         // At this point, |composite_type_ids| captures all the composite types
 106         // we could try to create, while |type_id_to_available_instructions|
 107         // captures all the available result ids we might use, organized by
 108         // type.
 109
 110         // Now we choose a composite type to construct, building it from
 111         // available constituent components and using zero constants if suitable
 112         // components are not available.
 113
 114         std::vector<uint32_t> constructor_arguments;
 115         uint32_t chosen_composite_type =
 116             composite_type_ids[GetFuzzerContext()->RandomIndex(
 117                 composite_type_ids)];
 118
 119         // Construct a composite of this type, using an appropriate helper
 120         // method depending on the kind of composite type.
 121         auto composite_type_inst =
 122             GetIRContext()->get_def_use_mgr()->GetDef(chosen_composite_type);
 123         switch (composite_type_inst->opcode()) {
 124           case spv::Op::OpTypeArray:
 125             constructor_arguments = FindComponentsToConstructArray(
 126                 *composite_type_inst, type_id_to_available_instructions);
 127             break;
 128           case spv::Op::OpTypeMatrix:
 129             constructor_arguments = FindComponentsToConstructMatrix(
 130                 *composite_type_inst, type_id_to_available_instructions);
 131             break;
 132           case spv::Op::OpTypeStruct:
 133             constructor_arguments = FindComponentsToConstructStruct(
 134                 *composite_type_inst, type_id_to_available_instructions);
 135             break;
 136           case spv::Op::OpTypeVector:
 137             constructor_arguments = FindComponentsToConstructVector(
 138                 *composite_type_inst, type_id_to_available_instructions);
 139             break;
 140           default:
 141             assert(false &&
 142                    "The space of possible composite types should be covered "
 143                    "by the above cases.");
 144             break;
 145         }
 146         assert(!constructor_arguments.empty());
 147
 148         // Make and apply a transformation.
 149         ApplyTransformation(TransformationCompositeConstruct(
 150             chosen_composite_type, constructor_arguments,
 151             instruction_descriptor, GetFuzzerContext()->GetFreshId()));
 152       });
 153 }
 154
 155 std::vector<uint32_t>
 156 FuzzerPassConstructComposites::FindComponentsToConstructArray(
 157     const opt::Instruction& array_type_instruction,
 158     const TypeIdToInstructions& type_id_to_available_instructions) {
 159   assert(array_type_instruction.opcode() == spv::Op::OpTypeArray &&
 160          "Precondition: instruction must be an array type.");
 161
 162   // Get the element type for the array.
 163   auto element_type_id = array_type_instruction.GetSingleWordInOperand(0);
 164
 165   // Get all instructions at our disposal that compute something of this element
 166   // type.
 167   auto available_instructions =
 168       type_id_to_available_instructions.find(element_type_id);
 169
 170   uint32_t array_length =
 171       GetIRContext()
 172           ->get_def_use_mgr()
 173           ->GetDef(array_type_instruction.GetSingleWordInOperand(1))
 174           ->GetSingleWordInOperand(0);
 175
 176   std::vector<uint32_t> result;
 177   for (uint32_t index = 0; index < array_length; index++) {
 178     if (available_instructions == type_id_to_available_instructions.cend()) {
 179       // No suitable instructions are available, so use a zero constant
 180       result.push_back(FindOrCreateZeroConstant(element_type_id, true));
 181     } else {
 182       result.push_back(
 183           available_instructions->second[GetFuzzerContext()->RandomIndex(
 184               available_instructions->second)]);
 185     }
 186   }
 187   return result;
 188 }
 189
 190 std::vector<uint32_t>
 191 FuzzerPassConstructComposites::FindComponentsToConstructMatrix(
 192     const opt::Instruction& matrix_type_instruction,
 193     const TypeIdToInstructions& type_id_to_available_instructions) {
 194   assert(matrix_type_instruction.opcode() == spv::Op::OpTypeMatrix &&
 195          "Precondition: instruction must be a matrix type.");
 196
 197   // Get the element type for the matrix.
 198   auto element_type_id = matrix_type_instruction.GetSingleWordInOperand(0);
 199
 200   // Get all instructions at our disposal that compute something of this element
 201   // type.
 202   auto available_instructions =
 203       type_id_to_available_instructions.find(element_type_id);
 204
 205   std::vector<uint32_t> result;
 206   for (uint32_t index = 0;
 207        index < matrix_type_instruction.GetSingleWordInOperand(1); index++) {
 208     if (available_instructions == type_id_to_available_instructions.cend()) {
 209       // No suitable components are available, so use a zero constant.
 210       result.push_back(FindOrCreateZeroConstant(element_type_id, true));
 211     } else {
 212       result.push_back(
 213           available_instructions->second[GetFuzzerContext()->RandomIndex(
 214               available_instructions->second)]);
 215     }
 216   }
 217   return result;
 218 }
 219
 220 std::vector<uint32_t>
 221 FuzzerPassConstructComposites::FindComponentsToConstructStruct(
 222     const opt::Instruction& struct_type_instruction,
 223     const TypeIdToInstructions& type_id_to_available_instructions) {
 224   assert(struct_type_instruction.opcode() == spv::Op::OpTypeStruct &&
 225          "Precondition: instruction must be a struct type.");
 226   std::vector<uint32_t> result;
 227   // Consider the type of each field of the struct.
 228   for (uint32_t in_operand_index = 0;
 229        in_operand_index < struct_type_instruction.NumInOperands();
 230        in_operand_index++) {
 231     auto element_type_id =
 232         struct_type_instruction.GetSingleWordInOperand(in_operand_index);
 233     // Find the instructions at our disposal that compute something of the field
 234     // type.
 235     auto available_instructions =
 236         type_id_to_available_instructions.find(element_type_id);
 237     if (available_instructions == type_id_to_available_instructions.cend()) {
 238       // No suitable component is available for this element type, so use a zero
 239       // constant.
 240       result.push_back(FindOrCreateZeroConstant(element_type_id, true));
 241     } else {
 242       result.push_back(
 243           available_instructions->second[GetFuzzerContext()->RandomIndex(
 244               available_instructions->second)]);
 245     }
 246   }
 247   return result;
 248 }
 249
 250 std::vector<uint32_t>
 251 FuzzerPassConstructComposites::FindComponentsToConstructVector(
 252     const opt::Instruction& vector_type_instruction,
 253     const TypeIdToInstructions& type_id_to_available_instructions) {
 254   assert(vector_type_instruction.opcode() == spv::Op::OpTypeVector &&
 255          "Precondition: instruction must be a vector type.");
 256
 257   // Get details of the type underlying the vector, and the width of the vector,
 258   // for convenience.
 259   auto element_type_id = vector_type_instruction.GetSingleWordInOperand(0);
 260   auto element_type = GetIRContext()->get_type_mgr()->GetType(element_type_id);
 261   auto element_count = vector_type_instruction.GetSingleWordInOperand(1);
 262
 263   // Collect a mapping, from type id to width, for scalar/vector types that are
 264   // smaller in width than |vector_type|, but that have the same underlying
 265   // type.  For example, if |vector_type| is vec4, the mapping will be:
 266   //   { float -> 1, vec2 -> 2, vec3 -> 3 }
 267   // The mapping will have missing entries if some of these types do not exist.
 268
 269   std::map<uint32_t, uint32_t> smaller_vector_type_id_to_width;
 270   // Add the underlying type.  This id must exist, in order for |vector_type| to
 271   // exist.
 272   smaller_vector_type_id_to_width[element_type_id] = 1;
 273
 274   // Now add every vector type with width at least 2, and less than the width of
 275   // |vector_type|.
 276   for (uint32_t width = 2; width < element_count; width++) {
 277     opt::analysis::Vector smaller_vector_type(element_type, width);
 278     auto smaller_vector_type_id =
 279         GetIRContext()->get_type_mgr()->GetId(&smaller_vector_type);
 280     // We might find that there is no declared type of this smaller width.
 281     // For example, a module can declare vec4 without having declared vec2 or
 282     // vec3.
 283     if (smaller_vector_type_id) {
 284       smaller_vector_type_id_to_width[smaller_vector_type_id] = width;
 285     }
 286   }
 287
 288   // Now we know the types that are available to us, we set about populating a
 289   // vector of the right length.  We do this by deciding, with no order in mind,
 290   // which instructions we will use to populate the vector, and subsequently
 291   // randomly choosing an order.  This is to avoid biasing construction of
 292   // vectors with smaller vectors to the left and scalars to the right.  That is
 293   // a concern because, e.g. in the case of populating a vec4, if we populate
 294   // the constructor instructions left-to-right, we can always choose a vec3 to
 295   // construct the first three elements, but can only choose a vec3 to construct
 296   // the last three elements if we chose a float to construct the first element
 297   // (otherwise there will not be space left for a vec3).
 298
 299   uint32_t vector_slots_used = 0;
 300
 301   // The instructions result ids we will use to construct the vector, in no
 302   // particular order at this stage.
 303   std::vector<uint32_t> result;
 304
 305   while (vector_slots_used < element_count) {
 306     std::vector<uint32_t> instructions_to_choose_from;
 307     for (auto& entry : smaller_vector_type_id_to_width) {
 308       if (entry.second >
 309           std::min(element_count - 1, element_count - vector_slots_used)) {
 310         continue;
 311       }
 312       auto available_instructions =
 313           type_id_to_available_instructions.find(entry.first);
 314       if (available_instructions == type_id_to_available_instructions.cend()) {
 315         continue;
 316       }
 317       instructions_to_choose_from.insert(instructions_to_choose_from.end(),
 318                                          available_instructions->second.begin(),
 319                                          available_instructions->second.end());
 320     }
 321     // If there are no instructions to choose from then use a zero constant,
 322     // otherwise select one of the instructions at random.
 323     uint32_t id_of_instruction_to_use =
 324         instructions_to_choose_from.empty()
 325             ? FindOrCreateZeroConstant(element_type_id, true)
 326             : instructions_to_choose_from[GetFuzzerContext()->RandomIndex(
 327                   instructions_to_choose_from)];
 328     opt::Instruction* instruction_to_use =
 329         GetIRContext()->get_def_use_mgr()->GetDef(id_of_instruction_to_use);
 330     result.push_back(instruction_to_use->result_id());
 331     auto chosen_type =
 332         GetIRContext()->get_type_mgr()->GetType(instruction_to_use->type_id());
 333     if (chosen_type->AsVector()) {
 334       assert(chosen_type->AsVector()->element_type() == element_type);
 335       assert(chosen_type->AsVector()->element_count() < element_count);
 336       assert(chosen_type->AsVector()->element_count() <=
 337              element_count - vector_slots_used);
 338       vector_slots_used += chosen_type->AsVector()->element_count();
 339     } else {
 340       assert(chosen_type == element_type);
 341       vector_slots_used += 1;
 342     }
 343   }
 344   assert(vector_slots_used == element_count);
 345
 346   GetFuzzerContext()->Shuffle(&result);
 347   return result;
 348 }
 349
 350 }  // namespace fuzz
 351 }  // namespace spvtools