source/fuzz/fuzzer_pass.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.h"
  16
  17 #include <set>
  18
  19 #include "source/fuzz/fuzzer_util.h"
  20 #include "source/fuzz/id_use_descriptor.h"
  21 #include "source/fuzz/instruction_descriptor.h"
  22 #include "source/fuzz/transformation_add_constant_boolean.h"
  23 #include "source/fuzz/transformation_add_constant_composite.h"
  24 #include "source/fuzz/transformation_add_constant_null.h"
  25 #include "source/fuzz/transformation_add_constant_scalar.h"
  26 #include "source/fuzz/transformation_add_global_undef.h"
  27 #include "source/fuzz/transformation_add_global_variable.h"
  28 #include "source/fuzz/transformation_add_local_variable.h"
  29 #include "source/fuzz/transformation_add_loop_preheader.h"
  30 #include "source/fuzz/transformation_add_type_boolean.h"
  31 #include "source/fuzz/transformation_add_type_float.h"
  32 #include "source/fuzz/transformation_add_type_function.h"
  33 #include "source/fuzz/transformation_add_type_int.h"
  34 #include "source/fuzz/transformation_add_type_matrix.h"
  35 #include "source/fuzz/transformation_add_type_pointer.h"
  36 #include "source/fuzz/transformation_add_type_struct.h"
  37 #include "source/fuzz/transformation_add_type_vector.h"
  38 #include "source/fuzz/transformation_split_block.h"
  39
  40 namespace spvtools {
  41 namespace fuzz {
  42
  43 FuzzerPass::FuzzerPass(opt::IRContext* ir_context,
  44                        TransformationContext* transformation_context,
  45                        FuzzerContext* fuzzer_context,
  46                        protobufs::TransformationSequence* transformations,
  47                        bool ignore_inapplicable_transformations)
  48     : ir_context_(ir_context),
  49       transformation_context_(transformation_context),
  50       fuzzer_context_(fuzzer_context),
  51       transformations_(transformations),
  52       ignore_inapplicable_transformations_(
  53           ignore_inapplicable_transformations) {}
  54
  55 FuzzerPass::~FuzzerPass() = default;
  56
  57 std::vector<opt::Instruction*> FuzzerPass::FindAvailableInstructions(
  58     opt::Function* function, opt::BasicBlock* block,
  59     const opt::BasicBlock::iterator& inst_it,
  60     std::function<bool(opt::IRContext*, opt::Instruction*)>
  61         instruction_is_relevant) const {
  62   // TODO(afd) The following is (relatively) simple, but may end up being
  63   //  prohibitively inefficient, as it walks the whole dominator tree for
  64   //  every instruction that is considered.
  65
  66   std::vector<opt::Instruction*> result;
  67   // Consider all global declarations
  68   for (auto& global : GetIRContext()->module()->types_values()) {
  69     if (instruction_is_relevant(GetIRContext(), &global)) {
  70       result.push_back(&global);
  71     }
  72   }
  73
  74   // Consider all function parameters
  75   function->ForEachParam(
  76       [this, &instruction_is_relevant, &result](opt::Instruction* param) {
  77         if (instruction_is_relevant(GetIRContext(), param)) {
  78           result.push_back(param);
  79         }
  80       });
  81
  82   // Consider all previous instructions in this block
  83   for (auto prev_inst_it = block->begin(); prev_inst_it != inst_it;
  84        ++prev_inst_it) {
  85     if (instruction_is_relevant(GetIRContext(), &*prev_inst_it)) {
  86       result.push_back(&*prev_inst_it);
  87     }
  88   }
  89
  90   // Walk the dominator tree to consider all instructions from dominating
  91   // blocks
  92   auto dominator_analysis = GetIRContext()->GetDominatorAnalysis(function);
  93   for (auto next_dominator = dominator_analysis->ImmediateDominator(block);
  94        next_dominator != nullptr;
  95        next_dominator =
  96            dominator_analysis->ImmediateDominator(next_dominator)) {
  97     for (auto& dominating_inst : *next_dominator) {
  98       if (instruction_is_relevant(GetIRContext(), &dominating_inst)) {
  99         result.push_back(&dominating_inst);
 100       }
 101     }
 102   }
 103   return result;
 104 }
 105
 106 void FuzzerPass::ForEachInstructionWithInstructionDescriptor(
 107     opt::Function* function,
 108     std::function<
 109         void(opt::BasicBlock* block, opt::BasicBlock::iterator inst_it,
 110              const protobufs::InstructionDescriptor& instruction_descriptor)>
 111         action) {
 112   // Consider only reachable blocks. We do this in a separate loop to avoid
 113   // recomputing the dominator analysis every time |action| changes the
 114   // module.
 115   std::vector<opt::BasicBlock*> reachable_blocks;
 116
 117   for (auto& block : *function) {
 118     if (GetIRContext()->IsReachable(block)) {
 119       reachable_blocks.push_back(&block);
 120     }
 121   }
 122
 123   for (auto* block : reachable_blocks) {
 124     // We now consider every instruction in the block, randomly deciding
 125     // whether to apply a transformation before it.
 126
 127     // In order for transformations to insert new instructions, they need to
 128     // be able to identify the instruction to insert before.  We describe an
 129     // instruction via its opcode, 'opc', a base instruction 'base' that has a
 130     // result id, and the number of instructions with opcode 'opc' that we
 131     // should skip when searching from 'base' for the desired instruction.
 132     // (An instruction that has a result id is represented by its own opcode,
 133     // itself as 'base', and a skip-count of 0.)
 134     std::vector<std::tuple<uint32_t, spv::Op, uint32_t>>
 135         base_opcode_skip_triples;
 136
 137     // The initial base instruction is the block label.
 138     uint32_t base = block->id();
 139
 140     // Counts the number of times we have seen each opcode since we reset the
 141     // base instruction.
 142     std::map<spv::Op, uint32_t> skip_count;
 143
 144     // Consider every instruction in the block.  The label is excluded: it is
 145     // only necessary to consider it as a base in case the first instruction
 146     // in the block does not have a result id.
 147     for (auto inst_it = block->begin(); inst_it != block->end(); ++inst_it) {
 148       if (inst_it->HasResultId()) {
 149         // In the case that the instruction has a result id, we use the
 150         // instruction as its own base, and clear the skip counts we have
 151         // collected.
 152         base = inst_it->result_id();
 153         skip_count.clear();
 154       }
 155       const spv::Op opcode = inst_it->opcode();
 156
 157       // Invoke the provided function, which might apply a transformation.
 158       action(block, inst_it,
 159              MakeInstructionDescriptor(
 160                  base, opcode,
 161                  skip_count.count(opcode) ? skip_count.at(opcode) : 0));
 162
 163       if (!inst_it->HasResultId()) {
 164         skip_count[opcode] =
 165             skip_count.count(opcode) ? skip_count.at(opcode) + 1 : 1;
 166       }
 167     }
 168   }
 169 }
 170
 171 void FuzzerPass::ForEachInstructionWithInstructionDescriptor(
 172     std::function<
 173         void(opt::Function* function, opt::BasicBlock* block,
 174              opt::BasicBlock::iterator inst_it,
 175              const protobufs::InstructionDescriptor& instruction_descriptor)>
 176         action) {
 177   // Consider every block in every function.
 178   for (auto& function : *GetIRContext()->module()) {
 179     ForEachInstructionWithInstructionDescriptor(
 180         &function,
 181         [&action, &function](
 182             opt::BasicBlock* block, opt::BasicBlock::iterator inst_it,
 183             const protobufs::InstructionDescriptor& instruction_descriptor) {
 184           action(&function, block, inst_it, instruction_descriptor);
 185         });
 186   }
 187 }
 188
 189 void FuzzerPass::ApplyTransformation(const Transformation& transformation) {
 190   if (ignore_inapplicable_transformations_) {
 191     // If an applicable-by-construction transformation turns out to be
 192     // inapplicable, this is a bug in the fuzzer. However, when deploying the
 193     // fuzzer at scale for finding bugs in SPIR-V processing tools it is
 194     // desirable to silently ignore such bugs. This code path caters for that
 195     // scenario.
 196     if (!transformation.IsApplicable(GetIRContext(),
 197                                      *GetTransformationContext())) {
 198       return;
 199     }
 200   } else {
 201     // This code path caters for debugging bugs in the fuzzer, where an
 202     // applicable-by-construction transformation turns out to be inapplicable.
 203     assert(transformation.IsApplicable(GetIRContext(),
 204                                        *GetTransformationContext()) &&
 205            "Transformation should be applicable by construction.");
 206   }
 207   transformation.Apply(GetIRContext(), GetTransformationContext());
 208   auto transformation_message = transformation.ToMessage();
 209   assert(transformation_message.transformation_case() !=
 210              protobufs::Transformation::TRANSFORMATION_NOT_SET &&
 211          "Bad transformation.");
 212   *GetTransformations()->add_transformation() =
 213       std::move(transformation_message);
 214 }
 215
 216 bool FuzzerPass::MaybeApplyTransformation(
 217     const Transformation& transformation) {
 218   if (transformation.IsApplicable(GetIRContext(),
 219                                   *GetTransformationContext())) {
 220     transformation.Apply(GetIRContext(), GetTransformationContext());
 221     auto transformation_message = transformation.ToMessage();
 222     assert(transformation_message.transformation_case() !=
 223                protobufs::Transformation::TRANSFORMATION_NOT_SET &&
 224            "Bad transformation.");
 225     *GetTransformations()->add_transformation() =
 226         std::move(transformation_message);
 227     return true;
 228   }
 229   return false;
 230 }
 231
 232 uint32_t FuzzerPass::FindOrCreateBoolType() {
 233   if (auto existing_id = fuzzerutil::MaybeGetBoolType(GetIRContext())) {
 234     return existing_id;
 235   }
 236   auto result = GetFuzzerContext()->GetFreshId();
 237   ApplyTransformation(TransformationAddTypeBoolean(result));
 238   return result;
 239 }
 240
 241 uint32_t FuzzerPass::FindOrCreateIntegerType(uint32_t width, bool is_signed) {
 242   opt::analysis::Integer int_type(width, is_signed);
 243   auto existing_id = GetIRContext()->get_type_mgr()->GetId(&int_type);
 244   if (existing_id) {
 245     return existing_id;
 246   }
 247   auto result = GetFuzzerContext()->GetFreshId();
 248   ApplyTransformation(TransformationAddTypeInt(result, width, is_signed));
 249   return result;
 250 }
 251
 252 uint32_t FuzzerPass::FindOrCreateFloatType(uint32_t width) {
 253   opt::analysis::Float float_type(width);
 254   auto existing_id = GetIRContext()->get_type_mgr()->GetId(&float_type);
 255   if (existing_id) {
 256     return existing_id;
 257   }
 258   auto result = GetFuzzerContext()->GetFreshId();
 259   ApplyTransformation(TransformationAddTypeFloat(result, width));
 260   return result;
 261 }
 262
 263 uint32_t FuzzerPass::FindOrCreateFunctionType(
 264     uint32_t return_type_id, const std::vector<uint32_t>& argument_id) {
 265   // FindFunctionType has a single argument for OpTypeFunction operands
 266   // so we will have to copy them all in this vector
 267   std::vector<uint32_t> type_ids(argument_id.size() + 1);
 268   type_ids[0] = return_type_id;
 269   std::copy(argument_id.begin(), argument_id.end(), type_ids.begin() + 1);
 270
 271   // Check if type exists
 272   auto existing_id = fuzzerutil::FindFunctionType(GetIRContext(), type_ids);
 273   if (existing_id) {
 274     return existing_id;
 275   }
 276
 277   auto result = GetFuzzerContext()->GetFreshId();
 278   ApplyTransformation(
 279       TransformationAddTypeFunction(result, return_type_id, argument_id));
 280   return result;
 281 }
 282
 283 uint32_t FuzzerPass::FindOrCreateVectorType(uint32_t component_type_id,
 284                                             uint32_t component_count) {
 285   assert(component_count >= 2 && component_count <= 4 &&
 286          "Precondition: component count must be in range [2, 4].");
 287   opt::analysis::Type* component_type =
 288       GetIRContext()->get_type_mgr()->GetType(component_type_id);
 289   assert(component_type && "Precondition: the component type must exist.");
 290   opt::analysis::Vector vector_type(component_type, component_count);
 291   auto existing_id = GetIRContext()->get_type_mgr()->GetId(&vector_type);
 292   if (existing_id) {
 293     return existing_id;
 294   }
 295   auto result = GetFuzzerContext()->GetFreshId();
 296   ApplyTransformation(
 297       TransformationAddTypeVector(result, component_type_id, component_count));
 298   return result;
 299 }
 300
 301 uint32_t FuzzerPass::FindOrCreateMatrixType(uint32_t column_count,
 302                                             uint32_t row_count) {
 303   assert(column_count >= 2 && column_count <= 4 &&
 304          "Precondition: column count must be in range [2, 4].");
 305   assert(row_count >= 2 && row_count <= 4 &&
 306          "Precondition: row count must be in range [2, 4].");
 307   uint32_t column_type_id =
 308       FindOrCreateVectorType(FindOrCreateFloatType(32), row_count);
 309   opt::analysis::Type* column_type =
 310       GetIRContext()->get_type_mgr()->GetType(column_type_id);
 311   opt::analysis::Matrix matrix_type(column_type, column_count);
 312   auto existing_id = GetIRContext()->get_type_mgr()->GetId(&matrix_type);
 313   if (existing_id) {
 314     return existing_id;
 315   }
 316   auto result = GetFuzzerContext()->GetFreshId();
 317   ApplyTransformation(
 318       TransformationAddTypeMatrix(result, column_type_id, column_count));
 319   return result;
 320 }
 321
 322 uint32_t FuzzerPass::FindOrCreateStructType(
 323     const std::vector<uint32_t>& component_type_ids) {
 324   if (auto existing_id =
 325           fuzzerutil::MaybeGetStructType(GetIRContext(), component_type_ids)) {
 326     return existing_id;
 327   }
 328   auto new_id = GetFuzzerContext()->GetFreshId();
 329   ApplyTransformation(TransformationAddTypeStruct(new_id, component_type_ids));
 330   return new_id;
 331 }
 332
 333 uint32_t FuzzerPass::FindOrCreatePointerType(uint32_t base_type_id,
 334                                              spv::StorageClass storage_class) {
 335   // We do not use the type manager here, due to problems related to isomorphic
 336   // but distinct structs not being regarded as different.
 337   auto existing_id = fuzzerutil::MaybeGetPointerType(
 338       GetIRContext(), base_type_id, storage_class);
 339   if (existing_id) {
 340     return existing_id;
 341   }
 342   auto result = GetFuzzerContext()->GetFreshId();
 343   ApplyTransformation(
 344       TransformationAddTypePointer(result, storage_class, base_type_id));
 345   return result;
 346 }
 347
 348 uint32_t FuzzerPass::FindOrCreatePointerToIntegerType(
 349     uint32_t width, bool is_signed, spv::StorageClass storage_class) {
 350   return FindOrCreatePointerType(FindOrCreateIntegerType(width, is_signed),
 351                                  storage_class);
 352 }
 353
 354 uint32_t FuzzerPass::FindOrCreateIntegerConstant(
 355     const std::vector<uint32_t>& words, uint32_t width, bool is_signed,
 356     bool is_irrelevant) {
 357   auto int_type_id = FindOrCreateIntegerType(width, is_signed);
 358   if (auto constant_id = fuzzerutil::MaybeGetScalarConstant(
 359           GetIRContext(), *GetTransformationContext(), words, int_type_id,
 360           is_irrelevant)) {
 361     return constant_id;
 362   }
 363   auto result = GetFuzzerContext()->GetFreshId();
 364   ApplyTransformation(TransformationAddConstantScalar(result, int_type_id,
 365                                                       words, is_irrelevant));
 366   return result;
 367 }
 368
 369 uint32_t FuzzerPass::FindOrCreateFloatConstant(
 370     const std::vector<uint32_t>& words, uint32_t width, bool is_irrelevant) {
 371   auto float_type_id = FindOrCreateFloatType(width);
 372   if (auto constant_id = fuzzerutil::MaybeGetScalarConstant(
 373           GetIRContext(), *GetTransformationContext(), words, float_type_id,
 374           is_irrelevant)) {
 375     return constant_id;
 376   }
 377   auto result = GetFuzzerContext()->GetFreshId();
 378   ApplyTransformation(TransformationAddConstantScalar(result, float_type_id,
 379                                                       words, is_irrelevant));
 380   return result;
 381 }
 382
 383 uint32_t FuzzerPass::FindOrCreateBoolConstant(bool value, bool is_irrelevant) {
 384   auto bool_type_id = FindOrCreateBoolType();
 385   if (auto constant_id = fuzzerutil::MaybeGetScalarConstant(
 386           GetIRContext(), *GetTransformationContext(), {value ? 1u : 0u},
 387           bool_type_id, is_irrelevant)) {
 388     return constant_id;
 389   }
 390   auto result = GetFuzzerContext()->GetFreshId();
 391   ApplyTransformation(
 392       TransformationAddConstantBoolean(result, value, is_irrelevant));
 393   return result;
 394 }
 395
 396 uint32_t FuzzerPass::FindOrCreateConstant(const std::vector<uint32_t>& words,
 397                                           uint32_t type_id,
 398                                           bool is_irrelevant) {
 399   assert(type_id && "Constant's type id can't be 0.");
 400
 401   const auto* type = GetIRContext()->get_type_mgr()->GetType(type_id);
 402   assert(type && "Type does not exist.");
 403
 404   if (type->AsBool()) {
 405     assert(words.size() == 1);
 406     return FindOrCreateBoolConstant(words[0], is_irrelevant);
 407   } else if (const auto* integer = type->AsInteger()) {
 408     return FindOrCreateIntegerConstant(words, integer->width(),
 409                                        integer->IsSigned(), is_irrelevant);
 410   } else if (const auto* floating = type->AsFloat()) {
 411     return FindOrCreateFloatConstant(words, floating->width(), is_irrelevant);
 412   }
 413
 414   // This assertion will fail in debug build but not in release build
 415   // so we return 0 to make compiler happy.
 416   assert(false && "Constant type is not supported");
 417   return 0;
 418 }
 419
 420 uint32_t FuzzerPass::FindOrCreateCompositeConstant(
 421     const std::vector<uint32_t>& component_ids, uint32_t type_id,
 422     bool is_irrelevant) {
 423   if (auto existing_constant = fuzzerutil::MaybeGetCompositeConstant(
 424           GetIRContext(), *GetTransformationContext(), component_ids, type_id,
 425           is_irrelevant)) {
 426     return existing_constant;
 427   }
 428   uint32_t result = GetFuzzerContext()->GetFreshId();
 429   ApplyTransformation(TransformationAddConstantComposite(
 430       result, type_id, component_ids, is_irrelevant));
 431   return result;
 432 }
 433
 434 uint32_t FuzzerPass::FindOrCreateGlobalUndef(uint32_t type_id) {
 435   for (auto& inst : GetIRContext()->types_values()) {
 436     if (inst.opcode() == spv::Op::OpUndef && inst.type_id() == type_id) {
 437       return inst.result_id();
 438     }
 439   }
 440   auto result = GetFuzzerContext()->GetFreshId();
 441   ApplyTransformation(TransformationAddGlobalUndef(result, type_id));
 442   return result;
 443 }
 444
 445 uint32_t FuzzerPass::FindOrCreateNullConstant(uint32_t type_id) {
 446   // Find existing declaration
 447   opt::analysis::NullConstant null_constant(
 448       GetIRContext()->get_type_mgr()->GetType(type_id));
 449   auto existing_constant =
 450       GetIRContext()->get_constant_mgr()->FindConstant(&null_constant);
 451
 452   // Return if found
 453   if (existing_constant) {
 454     return GetIRContext()
 455         ->get_constant_mgr()
 456         ->GetDefiningInstruction(existing_constant)
 457         ->result_id();
 458   }
 459
 460   // Create new if not found
 461   auto result = GetFuzzerContext()->GetFreshId();
 462   ApplyTransformation(TransformationAddConstantNull(result, type_id));
 463   return result;
 464 }
 465
 466 std::pair<std::vector<uint32_t>, std::map<uint32_t, std::vector<uint32_t>>>
 467 FuzzerPass::GetAvailableBasicTypesAndPointers(
 468     spv::StorageClass storage_class) const {
 469   // Records all of the basic types available in the module.
 470   std::set<uint32_t> basic_types;
 471
 472   // For each basic type, records all the associated pointer types that target
 473   // the basic type and that have |storage_class| as their storage class.
 474   std::map<uint32_t, std::vector<uint32_t>> basic_type_to_pointers;
 475
 476   for (auto& inst : GetIRContext()->types_values()) {
 477     // For each basic type that we come across, record type, and the fact that
 478     // we cannot yet have seen any pointers that use the basic type as its
 479     // pointee type.
 480     //
 481     // For pointer types with basic pointee types, associate the pointer type
 482     // with the basic type.
 483     switch (inst.opcode()) {
 484       case spv::Op::OpTypeBool:
 485       case spv::Op::OpTypeFloat:
 486       case spv::Op::OpTypeInt:
 487       case spv::Op::OpTypeMatrix:
 488       case spv::Op::OpTypeVector:
 489         // These are all basic types.
 490         basic_types.insert(inst.result_id());
 491         basic_type_to_pointers.insert({inst.result_id(), {}});
 492         break;
 493       case spv::Op::OpTypeArray:
 494         // An array type is basic if its base type is basic.
 495         if (basic_types.count(inst.GetSingleWordInOperand(0))) {
 496           basic_types.insert(inst.result_id());
 497           basic_type_to_pointers.insert({inst.result_id(), {}});
 498         }
 499         break;
 500       case spv::Op::OpTypeStruct: {
 501         // A struct type is basic if it does not have the Block/BufferBlock
 502         // decoration, and if all of its members are basic.
 503         if (!fuzzerutil::HasBlockOrBufferBlockDecoration(GetIRContext(),
 504                                                          inst.result_id())) {
 505           bool all_members_are_basic_types = true;
 506           for (uint32_t i = 0; i < inst.NumInOperands(); i++) {
 507             if (!basic_types.count(inst.GetSingleWordInOperand(i))) {
 508               all_members_are_basic_types = false;
 509               break;
 510             }
 511           }
 512           if (all_members_are_basic_types) {
 513             basic_types.insert(inst.result_id());
 514             basic_type_to_pointers.insert({inst.result_id(), {}});
 515           }
 516         }
 517         break;
 518       }
 519       case spv::Op::OpTypePointer: {
 520         // We are interested in the pointer if its pointee type is basic and it
 521         // has the right storage class.
 522         auto pointee_type = inst.GetSingleWordInOperand(1);
 523         if (spv::StorageClass(inst.GetSingleWordInOperand(0)) ==
 524                 storage_class &&
 525             basic_types.count(pointee_type)) {
 526           // The pointer has the desired storage class, and its pointee type is
 527           // a basic type, so we are interested in it.  Associate it with its
 528           // basic type.
 529           basic_type_to_pointers.at(pointee_type).push_back(inst.result_id());
 530         }
 531         break;
 532       }
 533       default:
 534         break;
 535     }
 536   }
 537   return {{basic_types.begin(), basic_types.end()}, basic_type_to_pointers};
 538 }
 539
 540 uint32_t FuzzerPass::FindOrCreateZeroConstant(
 541     uint32_t scalar_or_composite_type_id, bool is_irrelevant) {
 542   auto type_instruction =
 543       GetIRContext()->get_def_use_mgr()->GetDef(scalar_or_composite_type_id);
 544   assert(type_instruction && "The type instruction must exist.");
 545   switch (type_instruction->opcode()) {
 546     case spv::Op::OpTypeBool:
 547       return FindOrCreateBoolConstant(false, is_irrelevant);
 548     case spv::Op::OpTypeFloat: {
 549       auto width = type_instruction->GetSingleWordInOperand(0);
 550       auto num_words = (width + 32 - 1) / 32;
 551       return FindOrCreateFloatConstant(std::vector<uint32_t>(num_words, 0),
 552                                        width, is_irrelevant);
 553     }
 554     case spv::Op::OpTypeInt: {
 555       auto width = type_instruction->GetSingleWordInOperand(0);
 556       auto num_words = (width + 32 - 1) / 32;
 557       return FindOrCreateIntegerConstant(
 558           std::vector<uint32_t>(num_words, 0), width,
 559           type_instruction->GetSingleWordInOperand(1), is_irrelevant);
 560     }
 561     case spv::Op::OpTypeArray: {
 562       auto component_type_id = type_instruction->GetSingleWordInOperand(0);
 563       auto num_components =
 564           fuzzerutil::GetArraySize(*type_instruction, GetIRContext());
 565       return FindOrCreateCompositeConstant(
 566           std::vector<uint32_t>(
 567               num_components,
 568               FindOrCreateZeroConstant(component_type_id, is_irrelevant)),
 569           scalar_or_composite_type_id, is_irrelevant);
 570     }
 571     case spv::Op::OpTypeMatrix:
 572     case spv::Op::OpTypeVector: {
 573       auto component_type_id = type_instruction->GetSingleWordInOperand(0);
 574       auto num_components = type_instruction->GetSingleWordInOperand(1);
 575       return FindOrCreateCompositeConstant(
 576           std::vector<uint32_t>(
 577               num_components,
 578               FindOrCreateZeroConstant(component_type_id, is_irrelevant)),
 579           scalar_or_composite_type_id, is_irrelevant);
 580     }
 581     case spv::Op::OpTypeStruct: {
 582       assert(!fuzzerutil::HasBlockOrBufferBlockDecoration(
 583                  GetIRContext(), scalar_or_composite_type_id) &&
 584              "We do not construct constants of struct types decorated with "
 585              "Block or BufferBlock.");
 586       std::vector<uint32_t> field_zero_ids;
 587       for (uint32_t index = 0; index < type_instruction->NumInOperands();
 588            index++) {
 589         field_zero_ids.push_back(FindOrCreateZeroConstant(
 590             type_instruction->GetSingleWordInOperand(index), is_irrelevant));
 591       }
 592       return FindOrCreateCompositeConstant(
 593           field_zero_ids, scalar_or_composite_type_id, is_irrelevant);
 594     }
 595     default:
 596       assert(false && "Unknown type.");
 597       return 0;
 598   }
 599 }
 600
 601 void FuzzerPass::MaybeAddUseToReplace(
 602     opt::Instruction* use_inst, uint32_t use_index, uint32_t replacement_id,
 603     std::vector<std::pair<protobufs::IdUseDescriptor, uint32_t>>*
 604         uses_to_replace) {
 605   // Only consider this use if it is in a block
 606   if (!GetIRContext()->get_instr_block(use_inst)) {
 607     return;
 608   }
 609
 610   // Get the index of the operand restricted to input operands.
 611   uint32_t in_operand_index =
 612       fuzzerutil::InOperandIndexFromOperandIndex(*use_inst, use_index);
 613   auto id_use_descriptor =
 614       MakeIdUseDescriptorFromUse(GetIRContext(), use_inst, in_operand_index);
 615   uses_to_replace->emplace_back(
 616       std::make_pair(id_use_descriptor, replacement_id));
 617 }
 618
 619 opt::BasicBlock* FuzzerPass::GetOrCreateSimpleLoopPreheader(
 620     uint32_t header_id) {
 621   auto header_block = fuzzerutil::MaybeFindBlock(GetIRContext(), header_id);
 622
 623   assert(header_block && header_block->IsLoopHeader() &&
 624          "|header_id| should be the label id of a loop header");
 625
 626   auto predecessors = GetIRContext()->cfg()->preds(header_id);
 627
 628   assert(predecessors.size() >= 2 &&
 629          "The block |header_id| should be reachable.");
 630
 631   auto function = header_block->GetParent();
 632
 633   if (predecessors.size() == 2) {
 634     // The header has a single out-of-loop predecessor, which could be a
 635     // preheader.
 636
 637     opt::BasicBlock* maybe_preheader;
 638
 639     if (GetIRContext()->GetDominatorAnalysis(function)->Dominates(
 640             header_id, predecessors[0])) {
 641       // The first predecessor is the back-edge block, because the header
 642       // dominates it, so the second one is out of the loop.
 643       maybe_preheader = &*function->FindBlock(predecessors[1]);
 644     } else {
 645       // The first predecessor is out of the loop.
 646       maybe_preheader = &*function->FindBlock(predecessors[0]);
 647     }
 648
 649     // |maybe_preheader| is a preheader if it branches unconditionally to
 650     // the header. We also require it not to be a loop header.
 651     if (maybe_preheader->terminator()->opcode() == spv::Op::OpBranch &&
 652         !maybe_preheader->IsLoopHeader()) {
 653       return maybe_preheader;
 654     }
 655   }
 656
 657   // We need to add a preheader.
 658
 659   // Get a fresh id for the preheader.
 660   uint32_t preheader_id = GetFuzzerContext()->GetFreshId();
 661
 662   // Get a fresh id for each OpPhi instruction, if there is more than one
 663   // out-of-loop predecessor.
 664   std::vector<uint32_t> phi_ids;
 665   if (predecessors.size() > 2) {
 666     header_block->ForEachPhiInst(
 667         [this, &phi_ids](opt::Instruction* /* unused */) {
 668           phi_ids.push_back(GetFuzzerContext()->GetFreshId());
 669         });
 670   }
 671
 672   // Add the preheader.
 673   ApplyTransformation(
 674       TransformationAddLoopPreheader(header_id, preheader_id, phi_ids));
 675
 676   // Make the newly-created preheader the new entry block.
 677   return &*function->FindBlock(preheader_id);
 678 }
 679
 680 opt::BasicBlock* FuzzerPass::SplitBlockAfterOpPhiOrOpVariable(
 681     uint32_t block_id) {
 682   auto block = fuzzerutil::MaybeFindBlock(GetIRContext(), block_id);
 683   assert(block && "|block_id| must be a block label");
 684   assert(!block->IsLoopHeader() && "|block_id| cannot be a loop header");
 685
 686   // Find the first non-OpPhi and non-OpVariable instruction.
 687   auto non_phi_or_var_inst = &*block->begin();
 688   while (non_phi_or_var_inst->opcode() == spv::Op::OpPhi ||
 689          non_phi_or_var_inst->opcode() == spv::Op::OpVariable) {
 690     non_phi_or_var_inst = non_phi_or_var_inst->NextNode();
 691   }
 692
 693   // Split the block.
 694   uint32_t new_block_id = GetFuzzerContext()->GetFreshId();
 695   ApplyTransformation(TransformationSplitBlock(
 696       MakeInstructionDescriptor(GetIRContext(), non_phi_or_var_inst),
 697       new_block_id));
 698
 699   // We need to return the newly-created block.
 700   return &*block->GetParent()->FindBlock(new_block_id);
 701 }
 702
 703 uint32_t FuzzerPass::FindOrCreateLocalVariable(
 704     uint32_t pointer_type_id, uint32_t function_id,
 705     bool pointee_value_is_irrelevant) {
 706   auto pointer_type = GetIRContext()->get_type_mgr()->GetType(pointer_type_id);
 707   // No unused variables in release mode.
 708   (void)pointer_type;
 709   assert(pointer_type && pointer_type->AsPointer() &&
 710          pointer_type->AsPointer()->storage_class() ==
 711              spv::StorageClass::Function &&
 712          "The pointer_type_id must refer to a defined pointer type with "
 713          "storage class Function");
 714   auto function = fuzzerutil::FindFunction(GetIRContext(), function_id);
 715   assert(function && "The function must be defined.");
 716
 717   // First we try to find a suitable existing variable.
 718   // All of the local variable declarations are located in the first block.
 719   for (auto& instruction : *function->begin()) {
 720     if (instruction.opcode() != spv::Op::OpVariable) {
 721       continue;
 722     }
 723     // The existing OpVariable must have type |pointer_type_id|.
 724     if (instruction.type_id() != pointer_type_id) {
 725       continue;
 726     }
 727     // Check if the found variable is marked with PointeeValueIsIrrelevant
 728     // according to |pointee_value_is_irrelevant|.
 729     if (GetTransformationContext()->GetFactManager()->PointeeValueIsIrrelevant(
 730             instruction.result_id()) != pointee_value_is_irrelevant) {
 731       continue;
 732     }
 733     return instruction.result_id();
 734   }
 735
 736   // No such variable was found. Apply a transformation to get one.
 737   uint32_t pointee_type_id = fuzzerutil::GetPointeeTypeIdFromPointerType(
 738       GetIRContext(), pointer_type_id);
 739   uint32_t result_id = GetFuzzerContext()->GetFreshId();
 740   ApplyTransformation(TransformationAddLocalVariable(
 741       result_id, pointer_type_id, function_id,
 742       FindOrCreateZeroConstant(pointee_type_id, pointee_value_is_irrelevant),
 743       pointee_value_is_irrelevant));
 744   return result_id;
 745 }
 746
 747 uint32_t FuzzerPass::FindOrCreateGlobalVariable(
 748     uint32_t pointer_type_id, bool pointee_value_is_irrelevant) {
 749   auto pointer_type = GetIRContext()->get_type_mgr()->GetType(pointer_type_id);
 750   // No unused variables in release mode.
 751   (void)pointer_type;
 752   assert(
 753       pointer_type && pointer_type->AsPointer() &&
 754       (pointer_type->AsPointer()->storage_class() ==
 755            spv::StorageClass::Private ||
 756        pointer_type->AsPointer()->storage_class() ==
 757            spv::StorageClass::Workgroup) &&
 758       "The pointer_type_id must refer to a defined pointer type with storage "
 759       "class Private or Workgroup");
 760
 761   // First we try to find a suitable existing variable.
 762   for (auto& instruction : GetIRContext()->module()->types_values()) {
 763     if (instruction.opcode() != spv::Op::OpVariable) {
 764       continue;
 765     }
 766     // The existing OpVariable must have type |pointer_type_id|.
 767     if (instruction.type_id() != pointer_type_id) {
 768       continue;
 769     }
 770     // Check if the found variable is marked with PointeeValueIsIrrelevant
 771     // according to |pointee_value_is_irrelevant|.
 772     if (GetTransformationContext()->GetFactManager()->PointeeValueIsIrrelevant(
 773             instruction.result_id()) != pointee_value_is_irrelevant) {
 774       continue;
 775     }
 776     return instruction.result_id();
 777   }
 778
 779   // No such variable was found. Apply a transformation to get one.
 780   uint32_t pointee_type_id = fuzzerutil::GetPointeeTypeIdFromPointerType(
 781       GetIRContext(), pointer_type_id);
 782   auto storage_class = fuzzerutil::GetStorageClassFromPointerType(
 783       GetIRContext(), pointer_type_id);
 784   uint32_t result_id = GetFuzzerContext()->GetFreshId();
 785
 786   // A variable with storage class Workgroup shouldn't have an initializer.
 787   if (storage_class == spv::StorageClass::Workgroup) {
 788     ApplyTransformation(TransformationAddGlobalVariable(
 789         result_id, pointer_type_id, spv::StorageClass::Workgroup, 0,
 790         pointee_value_is_irrelevant));
 791   } else {
 792     ApplyTransformation(TransformationAddGlobalVariable(
 793         result_id, pointer_type_id, spv::StorageClass::Private,
 794         FindOrCreateZeroConstant(pointee_type_id, pointee_value_is_irrelevant),
 795         pointee_value_is_irrelevant));
 796   }
 797   return result_id;
 798 }
 799
 800 }  // namespace fuzz
 801 }  // namespace spvtools