source/fuzz/transformation_vector_shuffle.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/transformation_vector_shuffle.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 TransformationVectorShuffle::TransformationVectorShuffle(
  24     protobufs::TransformationVectorShuffle message)
  25     : message_(std::move(message)) {}
  26
  27 TransformationVectorShuffle::TransformationVectorShuffle(
  28     const protobufs::InstructionDescriptor& instruction_to_insert_before,
  29     uint32_t fresh_id, uint32_t vector1, uint32_t vector2,
  30     const std::vector<uint32_t>& component) {
  31   *message_.mutable_instruction_to_insert_before() =
  32       instruction_to_insert_before;
  33   message_.set_fresh_id(fresh_id);
  34   message_.set_vector1(vector1);
  35   message_.set_vector2(vector2);
  36   for (auto a_component : component) {
  37     message_.add_component(a_component);
  38   }
  39 }
  40
  41 bool TransformationVectorShuffle::IsApplicable(
  42     opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
  43   // The fresh id must not already be in use.
  44   if (!fuzzerutil::IsFreshId(ir_context, message_.fresh_id())) {
  45     return false;
  46   }
  47   // The instruction before which the shuffle will be inserted must exist.
  48   auto instruction_to_insert_before =
  49       FindInstruction(message_.instruction_to_insert_before(), ir_context);
  50   if (!instruction_to_insert_before) {
  51     return false;
  52   }
  53   // The first vector must be an instruction with a type id
  54   auto vector1_instruction =
  55       ir_context->get_def_use_mgr()->GetDef(message_.vector1());
  56   if (!vector1_instruction || !vector1_instruction->type_id()) {
  57     return false;
  58   }
  59   // The second vector must be an instruction with a type id
  60   auto vector2_instruction =
  61       ir_context->get_def_use_mgr()->GetDef(message_.vector2());
  62   if (!vector2_instruction || !vector2_instruction->type_id()) {
  63     return false;
  64   }
  65   auto vector1_type =
  66       ir_context->get_type_mgr()->GetType(vector1_instruction->type_id());
  67   // The first vector instruction's type must actually be a vector type.
  68   if (!vector1_type->AsVector()) {
  69     return false;
  70   }
  71   auto vector2_type =
  72       ir_context->get_type_mgr()->GetType(vector2_instruction->type_id());
  73   // The second vector instruction's type must actually be a vector type.
  74   if (!vector2_type->AsVector()) {
  75     return false;
  76   }
  77   // The element types of the vectors must be the same.
  78   if (vector1_type->AsVector()->element_type() !=
  79       vector2_type->AsVector()->element_type()) {
  80     return false;
  81   }
  82   uint32_t combined_size = vector1_type->AsVector()->element_count() +
  83                            vector2_type->AsVector()->element_count();
  84   for (auto a_compoment : message_.component()) {
  85     // 0xFFFFFFFF is used to represent an undefined component.  Unless
  86     // undefined, a component must be less than the combined size of the
  87     // vectors.
  88     if (a_compoment != 0xFFFFFFFF && a_compoment >= combined_size) {
  89       return false;
  90     }
  91   }
  92   // The module must already declare an appropriate type in which to store the
  93   // result of the shuffle.
  94   if (!GetResultTypeId(ir_context, *vector1_type->AsVector()->element_type())) {
  95     return false;
  96   }
  97   // Each of the vectors used in the shuffle must be available at the insertion
  98   // point.
  99   for (auto used_instruction : {vector1_instruction, vector2_instruction}) {
 100     if (auto block = ir_context->get_instr_block(used_instruction)) {
 101       if (!ir_context->GetDominatorAnalysis(block->GetParent())
 102                ->Dominates(used_instruction, instruction_to_insert_before)) {
 103         return false;
 104       }
 105     }
 106   }
 107
 108   // It must be legitimate to insert an OpVectorShuffle before the identified
 109   // instruction.
 110   return fuzzerutil::CanInsertOpcodeBeforeInstruction(
 111       spv::Op::OpVectorShuffle, instruction_to_insert_before);
 112 }
 113
 114 void TransformationVectorShuffle::Apply(
 115     opt::IRContext* ir_context,
 116     TransformationContext* transformation_context) const {
 117   // Make input operands for a shuffle instruction - these comprise the two
 118   // vectors being shuffled, followed by the integer literal components.
 119   opt::Instruction::OperandList shuffle_operands = {
 120       {SPV_OPERAND_TYPE_ID, {message_.vector1()}},
 121       {SPV_OPERAND_TYPE_ID, {message_.vector2()}}};
 122   for (auto a_component : message_.component()) {
 123     shuffle_operands.push_back(
 124         {SPV_OPERAND_TYPE_LITERAL_INTEGER, {a_component}});
 125   }
 126
 127   uint32_t result_type_id = GetResultTypeId(
 128       ir_context,
 129       *GetVectorType(ir_context, message_.vector1())->element_type());
 130
 131   // Add a shuffle instruction right before the instruction identified by
 132   // |message_.instruction_to_insert_before|.
 133   auto insert_before =
 134       FindInstruction(message_.instruction_to_insert_before(), ir_context);
 135   opt::Instruction* new_instruction =
 136       insert_before->InsertBefore(MakeUnique<opt::Instruction>(
 137           ir_context, spv::Op::OpVectorShuffle, result_type_id,
 138           message_.fresh_id(), shuffle_operands));
 139   fuzzerutil::UpdateModuleIdBound(ir_context, message_.fresh_id());
 140   // Inform the def-use manager about the new instruction and record its basic
 141   // block.
 142   ir_context->get_def_use_mgr()->AnalyzeInstDefUse(new_instruction);
 143   ir_context->set_instr_block(new_instruction,
 144                               ir_context->get_instr_block(insert_before));
 145
 146   AddDataSynonymFacts(ir_context, transformation_context);
 147 }
 148
 149 protobufs::Transformation TransformationVectorShuffle::ToMessage() const {
 150   protobufs::Transformation result;
 151   *result.mutable_vector_shuffle() = message_;
 152   return result;
 153 }
 154
 155 uint32_t TransformationVectorShuffle::GetResultTypeId(
 156     opt::IRContext* ir_context, const opt::analysis::Type& element_type) const {
 157   opt::analysis::Vector result_type(
 158       &element_type, static_cast<uint32_t>(message_.component_size()));
 159   return ir_context->get_type_mgr()->GetId(&result_type);
 160 }
 161
 162 opt::analysis::Vector* TransformationVectorShuffle::GetVectorType(
 163     opt::IRContext* ir_context, uint32_t id_of_vector) {
 164   return ir_context->get_type_mgr()
 165       ->GetType(ir_context->get_def_use_mgr()->GetDef(id_of_vector)->type_id())
 166       ->AsVector();
 167 }
 168
 169 std::unordered_set<uint32_t> TransformationVectorShuffle::GetFreshIds() const {
 170   return {message_.fresh_id()};
 171 }
 172
 173 void TransformationVectorShuffle::AddDataSynonymFacts(
 174     opt::IRContext* ir_context,
 175     TransformationContext* transformation_context) const {
 176   // If the new instruction is irrelevant (because it is in a dead block), it
 177   // cannot participate in any DataSynonym fact.
 178   if (transformation_context->GetFactManager()->IdIsIrrelevant(
 179           message_.fresh_id())) {
 180     return;
 181   }
 182
 183   // Add synonym facts relating the defined elements of the shuffle result to
 184   // the vector components that they come from.
 185   for (uint32_t component_index = 0;
 186        component_index < static_cast<uint32_t>(message_.component_size());
 187        component_index++) {
 188     uint32_t component = message_.component(component_index);
 189     if (component == 0xFFFFFFFF) {
 190       // This component is undefined, we do not introduce a synonym.
 191       continue;
 192     }
 193     // This describes the element of the result vector associated with
 194     // |component_index|.
 195     protobufs::DataDescriptor descriptor_for_result_component =
 196         MakeDataDescriptor(message_.fresh_id(), {component_index});
 197
 198     protobufs::DataDescriptor descriptor_for_source_component;
 199
 200     // Get a data descriptor for the component of the input vector to which
 201     // |component| refers.
 202     if (component <
 203         GetVectorType(ir_context, message_.vector1())->element_count()) {
 204       // Check that the first vector can participate in data synonym facts.
 205       if (!fuzzerutil::CanMakeSynonymOf(
 206               ir_context, *transformation_context,
 207               *ir_context->get_def_use_mgr()->GetDef(message_.vector1()))) {
 208         continue;
 209       }
 210       descriptor_for_source_component =
 211           MakeDataDescriptor(message_.vector1(), {component});
 212     } else {
 213       // Check that the second vector can participate in data synonym facts.
 214       if (!fuzzerutil::CanMakeSynonymOf(
 215               ir_context, *transformation_context,
 216               *ir_context->get_def_use_mgr()->GetDef(message_.vector2()))) {
 217         continue;
 218       }
 219       auto index_into_vector_2 =
 220           component -
 221           GetVectorType(ir_context, message_.vector1())->element_count();
 222       assert(
 223           index_into_vector_2 <
 224               GetVectorType(ir_context, message_.vector2())->element_count() &&
 225           "Vector shuffle index is out of bounds.");
 226       descriptor_for_source_component =
 227           MakeDataDescriptor(message_.vector2(), {index_into_vector_2});
 228     }
 229
 230     // Add a fact relating this input vector component with the associated
 231     // result component.
 232     transformation_context->GetFactManager()->AddFactDataSynonym(
 233         descriptor_for_result_component, descriptor_for_source_component);
 234   }
 235 }
 236
 237 }  // namespace fuzz
 238 }  // namespace spvtools