source/fuzz/transformation_composite_construct.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_composite_construct.h"
  16
  17 #include "source/fuzz/data_descriptor.h"
  18 #include "source/fuzz/fuzzer_util.h"
  19 #include "source/fuzz/instruction_descriptor.h"
  20 #include "source/opt/instruction.h"
  21
  22 namespace spvtools {
  23 namespace fuzz {
  24
  25 TransformationCompositeConstruct::TransformationCompositeConstruct(
  26     protobufs::TransformationCompositeConstruct message)
  27     : message_(std::move(message)) {}
  28
  29 TransformationCompositeConstruct::TransformationCompositeConstruct(
  30     uint32_t composite_type_id, std::vector<uint32_t> component,
  31     const protobufs::InstructionDescriptor& instruction_to_insert_before,
  32     uint32_t fresh_id) {
  33   message_.set_composite_type_id(composite_type_id);
  34   for (auto a_component : component) {
  35     message_.add_component(a_component);
  36   }
  37   *message_.mutable_instruction_to_insert_before() =
  38       instruction_to_insert_before;
  39   message_.set_fresh_id(fresh_id);
  40 }
  41
  42 bool TransformationCompositeConstruct::IsApplicable(
  43     opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
  44   if (!fuzzerutil::IsFreshId(ir_context, message_.fresh_id())) {
  45     // We require the id for the composite constructor to be unused.
  46     return false;
  47   }
  48
  49   auto insert_before =
  50       FindInstruction(message_.instruction_to_insert_before(), ir_context);
  51   if (!insert_before) {
  52     // The instruction before which the composite should be inserted was not
  53     // found.
  54     return false;
  55   }
  56
  57   auto composite_type =
  58       ir_context->get_type_mgr()->GetType(message_.composite_type_id());
  59
  60   if (!fuzzerutil::IsCompositeType(composite_type)) {
  61     // The type must actually be a composite.
  62     return false;
  63   }
  64
  65   // If the type is an array, matrix, struct or vector, the components need to
  66   // be suitable for constructing something of that type.
  67   if (composite_type->AsArray() &&
  68       !ComponentsForArrayConstructionAreOK(ir_context,
  69                                            *composite_type->AsArray())) {
  70     return false;
  71   }
  72   if (composite_type->AsMatrix() &&
  73       !ComponentsForMatrixConstructionAreOK(ir_context,
  74                                             *composite_type->AsMatrix())) {
  75     return false;
  76   }
  77   if (composite_type->AsStruct() &&
  78       !ComponentsForStructConstructionAreOK(ir_context,
  79                                             *composite_type->AsStruct())) {
  80     return false;
  81   }
  82   if (composite_type->AsVector() &&
  83       !ComponentsForVectorConstructionAreOK(ir_context,
  84                                             *composite_type->AsVector())) {
  85     return false;
  86   }
  87
  88   // Now check whether every component being used to initialize the composite is
  89   // available at the desired program point.
  90   for (auto component : message_.component()) {
  91     auto* inst = ir_context->get_def_use_mgr()->GetDef(component);
  92     if (!inst) {
  93       return false;
  94     }
  95
  96     if (!fuzzerutil::IdIsAvailableBeforeInstruction(ir_context, insert_before,
  97                                                     component)) {
  98       return false;
  99     }
 100   }
 101
 102   return true;
 103 }
 104
 105 void TransformationCompositeConstruct::Apply(
 106     opt::IRContext* ir_context,
 107     TransformationContext* transformation_context) const {
 108   // Use the base and offset information from the transformation to determine
 109   // where in the module a new instruction should be inserted.
 110   auto insert_before_inst =
 111       FindInstruction(message_.instruction_to_insert_before(), ir_context);
 112   auto destination_block = ir_context->get_instr_block(insert_before_inst);
 113   auto insert_before = fuzzerutil::GetIteratorForInstruction(
 114       destination_block, insert_before_inst);
 115
 116   // Prepare the input operands for an OpCompositeConstruct instruction.
 117   opt::Instruction::OperandList in_operands;
 118   for (auto& component_id : message_.component()) {
 119     in_operands.push_back({SPV_OPERAND_TYPE_ID, {component_id}});
 120   }
 121
 122   // Insert an OpCompositeConstruct instruction.
 123   auto new_instruction = MakeUnique<opt::Instruction>(
 124       ir_context, spv::Op::OpCompositeConstruct, message_.composite_type_id(),
 125       message_.fresh_id(), in_operands);
 126   auto new_instruction_ptr = new_instruction.get();
 127   insert_before.InsertBefore(std::move(new_instruction));
 128   ir_context->get_def_use_mgr()->AnalyzeInstDefUse(new_instruction_ptr);
 129   ir_context->set_instr_block(new_instruction_ptr, destination_block);
 130
 131   fuzzerutil::UpdateModuleIdBound(ir_context, message_.fresh_id());
 132
 133   // No analyses need to be invalidated since the transformation is local to a
 134   // block and the def-use and instruction-to-block mappings have been updated.
 135
 136   AddDataSynonymFacts(ir_context, transformation_context);
 137 }
 138
 139 bool TransformationCompositeConstruct::ComponentsForArrayConstructionAreOK(
 140     opt::IRContext* ir_context, const opt::analysis::Array& array_type) const {
 141   if (array_type.length_info().words[0] !=
 142       opt::analysis::Array::LengthInfo::kConstant) {
 143     // We only handle constant-sized arrays.
 144     return false;
 145   }
 146   if (array_type.length_info().words.size() != 2) {
 147     // We only handle the case where the array size can be captured in a single
 148     // word.
 149     return false;
 150   }
 151   // Get the array size.
 152   auto array_size = array_type.length_info().words[1];
 153   if (static_cast<uint32_t>(message_.component().size()) != array_size) {
 154     // The number of components must match the array size.
 155     return false;
 156   }
 157   // Check that each component is the result id of an instruction whose type is
 158   // the array's element type.
 159   for (auto component_id : message_.component()) {
 160     auto inst = ir_context->get_def_use_mgr()->GetDef(component_id);
 161     if (inst == nullptr || !inst->type_id()) {
 162       // The component does not correspond to an instruction with a result
 163       // type.
 164       return false;
 165     }
 166     auto component_type = ir_context->get_type_mgr()->GetType(inst->type_id());
 167     assert(component_type);
 168     if (component_type != array_type.element_type()) {
 169       // The component's type does not match the array's element type.
 170       return false;
 171     }
 172   }
 173   return true;
 174 }
 175
 176 bool TransformationCompositeConstruct::ComponentsForMatrixConstructionAreOK(
 177     opt::IRContext* ir_context,
 178     const opt::analysis::Matrix& matrix_type) const {
 179   if (static_cast<uint32_t>(message_.component().size()) !=
 180       matrix_type.element_count()) {
 181     // The number of components must match the number of columns of the matrix.
 182     return false;
 183   }
 184   // Check that each component is the result id of an instruction whose type is
 185   // the matrix's column type.
 186   for (auto component_id : message_.component()) {
 187     auto inst = ir_context->get_def_use_mgr()->GetDef(component_id);
 188     if (inst == nullptr || !inst->type_id()) {
 189       // The component does not correspond to an instruction with a result
 190       // type.
 191       return false;
 192     }
 193     auto component_type = ir_context->get_type_mgr()->GetType(inst->type_id());
 194     assert(component_type);
 195     if (component_type != matrix_type.element_type()) {
 196       // The component's type does not match the matrix's column type.
 197       return false;
 198     }
 199   }
 200   return true;
 201 }
 202
 203 bool TransformationCompositeConstruct::ComponentsForStructConstructionAreOK(
 204     opt::IRContext* ir_context,
 205     const opt::analysis::Struct& struct_type) const {
 206   if (static_cast<uint32_t>(message_.component().size()) !=
 207       struct_type.element_types().size()) {
 208     // The number of components must match the number of fields of the struct.
 209     return false;
 210   }
 211   // Check that each component is the result id of an instruction those type
 212   // matches the associated field type.
 213   for (uint32_t field_index = 0;
 214        field_index < struct_type.element_types().size(); field_index++) {
 215     auto inst = ir_context->get_def_use_mgr()->GetDef(
 216         message_.component()[field_index]);
 217     if (inst == nullptr || !inst->type_id()) {
 218       // The component does not correspond to an instruction with a result
 219       // type.
 220       return false;
 221     }
 222     auto component_type = ir_context->get_type_mgr()->GetType(inst->type_id());
 223     assert(component_type);
 224     if (component_type != struct_type.element_types()[field_index]) {
 225       // The component's type does not match the corresponding field type.
 226       return false;
 227     }
 228   }
 229   return true;
 230 }
 231
 232 bool TransformationCompositeConstruct::ComponentsForVectorConstructionAreOK(
 233     opt::IRContext* ir_context,
 234     const opt::analysis::Vector& vector_type) const {
 235   uint32_t base_element_count = 0;
 236   auto element_type = vector_type.element_type();
 237   for (auto& component_id : message_.component()) {
 238     auto inst = ir_context->get_def_use_mgr()->GetDef(component_id);
 239     if (inst == nullptr || !inst->type_id()) {
 240       // The component does not correspond to an instruction with a result
 241       // type.
 242       return false;
 243     }
 244     auto component_type = ir_context->get_type_mgr()->GetType(inst->type_id());
 245     assert(component_type);
 246     if (component_type == element_type) {
 247       base_element_count++;
 248     } else if (component_type->AsVector() &&
 249                component_type->AsVector()->element_type() == element_type) {
 250       base_element_count += component_type->AsVector()->element_count();
 251     } else {
 252       // The component was not appropriate; e.g. no type corresponding to the
 253       // given id was found, or the type that was found was not compatible
 254       // with the vector being constructed.
 255       return false;
 256     }
 257   }
 258   // The number of components provided (when vector components are flattened
 259   // out) needs to match the length of the vector being constructed.
 260   return base_element_count == vector_type.element_count();
 261 }
 262
 263 protobufs::Transformation TransformationCompositeConstruct::ToMessage() const {
 264   protobufs::Transformation result;
 265   *result.mutable_composite_construct() = message_;
 266   return result;
 267 }
 268
 269 std::unordered_set<uint32_t> TransformationCompositeConstruct::GetFreshIds()
 270     const {
 271   return {message_.fresh_id()};
 272 }
 273
 274 void TransformationCompositeConstruct::AddDataSynonymFacts(
 275     opt::IRContext* ir_context,
 276     TransformationContext* transformation_context) const {
 277   // If the result id of the composite we are constructing is irrelevant (e.g.
 278   // because it is in a dead block) then we do not make any synonyms.
 279   if (transformation_context->GetFactManager()->IdIsIrrelevant(
 280           message_.fresh_id())) {
 281     return;
 282   }
 283
 284   // Inform the fact manager that we now have new synonyms: every component of
 285   // the composite is synonymous with the id used to construct that component
 286   // (so long as it is legitimate to create a synonym from that id), except in
 287   // the case of a vector where a single vector id can span multiple components.
 288   auto composite_type =
 289       ir_context->get_type_mgr()->GetType(message_.composite_type_id());
 290   uint32_t index = 0;
 291   for (auto component : message_.component()) {
 292     auto component_type = ir_context->get_type_mgr()->GetType(
 293         ir_context->get_def_use_mgr()->GetDef(component)->type_id());
 294     // Whether the component is a vector being packed into a vector determines
 295     // how we should keep track of the indices associated with components.
 296     const bool packing_vector_into_vector =
 297         composite_type->AsVector() && component_type->AsVector();
 298     if (!fuzzerutil::CanMakeSynonymOf(
 299             ir_context, *transformation_context,
 300             *ir_context->get_def_use_mgr()->GetDef(component))) {
 301       // We can't make a synonym of this component, so we skip on to the next
 302       // component.  In the case where we're packing a vector into a vector we
 303       // have to skip as many components of the resulting vectors as there are
 304       // elements of the component vector.
 305       index += packing_vector_into_vector
 306                    ? component_type->AsVector()->element_count()
 307                    : 1;
 308       continue;
 309     }
 310     if (packing_vector_into_vector) {
 311       // The case where the composite being constructed is a vector and the
 312       // component provided for construction is also a vector is special.  It
 313       // requires adding a synonym fact relating each element of the sub-vector
 314       // to the corresponding element of the composite being constructed.
 315       assert(component_type->AsVector()->element_type() ==
 316              composite_type->AsVector()->element_type());
 317       assert(component_type->AsVector()->element_count() <
 318              composite_type->AsVector()->element_count());
 319       for (uint32_t subvector_index = 0;
 320            subvector_index < component_type->AsVector()->element_count();
 321            subvector_index++) {
 322         transformation_context->GetFactManager()->AddFactDataSynonym(
 323             MakeDataDescriptor(component, {subvector_index}),
 324             MakeDataDescriptor(message_.fresh_id(), {index}));
 325         index++;
 326       }
 327     } else {
 328       // The other cases are simple: the component is made directly synonymous
 329       // with the element of the composite being constructed.
 330       transformation_context->GetFactManager()->AddFactDataSynonym(
 331           MakeDataDescriptor(component, {}),
 332           MakeDataDescriptor(message_.fresh_id(), {index}));
 333       index++;
 334     }
 335   }
 336 }
 337
 338 }  // namespace fuzz
 339 }  // namespace spvtools