third_party/SPIRV-Tools/source/fuzz/fuzzer_pass_construct_composites.cpp - SwiftShader - Git at Google

 // Copyright (c) 2019 Google LLC
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 #include "source/fuzz/fuzzer_pass_construct_composites.h"

 #include <memory>

 #include "source/fuzz/fuzzer_util.h"
 #include "source/fuzz/transformation_composite_construct.h"

 namespace spvtools {
 namespace fuzz {

 FuzzerPassConstructComposites::FuzzerPassConstructComposites(
     opt::IRContext* ir_context, TransformationContext* transformation_context,
     FuzzerContext* fuzzer_context,
     protobufs::TransformationSequence* transformations)
     : FuzzerPass(ir_context, transformation_context, fuzzer_context,
                  transformations) {}

 FuzzerPassConstructComposites::~FuzzerPassConstructComposites() = default;

 void FuzzerPassConstructComposites::Apply() {
   // Gather up the ids of all composite types, but skip block-/buffer
   // block-decorated struct types.
   std::vector<uint32_t> composite_type_ids;
   for (auto& inst : GetIRContext()->types_values()) {
     if (fuzzerutil::IsCompositeType(
             GetIRContext()->get_type_mgr()->GetType(inst.result_id())) &&
         !fuzzerutil::HasBlockOrBufferBlockDecoration(GetIRContext(),
                                                      inst.result_id())) {
       composite_type_ids.push_back(inst.result_id());
     }
   }

   ForEachInstructionWithInstructionDescriptor(
       [this, &composite_type_ids](
           opt::Function* function, opt::BasicBlock* block,
           opt::BasicBlock::iterator inst_it,
           const protobufs::InstructionDescriptor& instruction_descriptor)
           -> void {
         // Check whether it is legitimate to insert a composite construction
         // before the instruction.
         if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(
                 SpvOpCompositeConstruct, inst_it)) {
           return;
         }

         // Randomly decide whether to try inserting an object copy here.
         if (!GetFuzzerContext()->ChoosePercentage(
                 GetFuzzerContext()->GetChanceOfConstructingComposite())) {
           return;
         }

         // For each instruction that is available at this program point (i.e. an
         // instruction that is global or whose definition strictly dominates the
         // program point) and suitable for making a synonym of, associate it
         // with the id of its result type.
         TypeIdToInstructions type_id_to_available_instructions;
         auto available_instructions = FindAvailableInstructions(
             function, block, inst_it,
             [this](opt::IRContext* ir_context, opt::Instruction* inst) {
               if (!inst->result_id() || !inst->type_id()) {
                 return false;
               }

               // If the id is irrelevant, we can use it since it will not
               // participate in DataSynonym fact. Otherwise, we should be able
               // to produce a synonym out of the id.
               return GetTransformationContext()
                          ->GetFactManager()
                          ->IdIsIrrelevant(inst->result_id()) ||
                      fuzzerutil::CanMakeSynonymOf(
                          ir_context, *GetTransformationContext(), inst);
             });
         for (auto instruction : available_instructions) {
           RecordAvailableInstruction(instruction,
                                      &type_id_to_available_instructions);
         }

         // At this point, |composite_type_ids| captures all the composite types
         // we could try to create, while |type_id_to_available_instructions|
         // captures all the available result ids we might use, organized by
         // type.

         // Now we try to find a composite that we can construct.  We might not
         // manage, if there is a paucity of available ingredients in the module
         // (e.g. if our only available composite was a boolean vector and we had
         // no instructions generating boolean result types available).
         //
         // If we succeed, |chosen_composite_type| will end up being non-zero,
         // and |constructor_arguments| will end up giving us result ids suitable
         // for constructing a composite of that type.  Otherwise these variables
         // will remain 0 and null respectively.
         uint32_t chosen_composite_type = 0;
         std::vector<uint32_t> constructor_arguments;

         // Initially, all composite type ids are available for us to try.  Keep
         // trying until we run out of options.
         auto composites_to_try_constructing = composite_type_ids;
         while (!composites_to_try_constructing.empty()) {
           // Remove a composite type from the composite types left for us to
           // try.
           auto next_composite_to_try_constructing =
               GetFuzzerContext()->RemoveAtRandomIndex(
                   &composites_to_try_constructing);

           // Now try to construct a composite of this type, using an appropriate
           // helper method depending on the kind of composite type.
           auto composite_type_inst = GetIRContext()->get_def_use_mgr()->GetDef(
               next_composite_to_try_constructing);
           switch (composite_type_inst->opcode()) {
             case SpvOpTypeArray:
               constructor_arguments = FindComponentsToConstructArray(
                   *composite_type_inst, type_id_to_available_instructions);
               break;
             case SpvOpTypeMatrix:
               constructor_arguments = FindComponentsToConstructMatrix(
                   *composite_type_inst, type_id_to_available_instructions);
               break;
             case SpvOpTypeStruct:
               constructor_arguments = FindComponentsToConstructStruct(
                   *composite_type_inst, type_id_to_available_instructions);
               break;
             case SpvOpTypeVector:
               constructor_arguments = FindComponentsToConstructVector(
                   *composite_type_inst, type_id_to_available_instructions);
               break;
             default:
               assert(false &&
                      "The space of possible composite types should be covered "
                      "by the above cases.");
               break;
           }
           if (!constructor_arguments.empty()) {
             // We succeeded!  Note the composite type we finally settled on, and
             // exit from the loop.
             chosen_composite_type = next_composite_to_try_constructing;
             break;
           }
         }

         if (!chosen_composite_type) {
           // We did not manage to make a composite; return 0 to indicate that no
           // instructions were added.
           assert(constructor_arguments.empty());
           return;
         }
         assert(!constructor_arguments.empty());

         // Make and apply a transformation.
         ApplyTransformation(TransformationCompositeConstruct(
             chosen_composite_type, constructor_arguments,
             instruction_descriptor, GetFuzzerContext()->GetFreshId()));
       });
 }

 void FuzzerPassConstructComposites::RecordAvailableInstruction(
     opt::Instruction* inst,
     TypeIdToInstructions* type_id_to_available_instructions) {
   if (type_id_to_available_instructions->count(inst->type_id()) == 0) {
     (*type_id_to_available_instructions)[inst->type_id()] = {};
   }
   type_id_to_available_instructions->at(inst->type_id()).push_back(inst);
 }

 std::vector<uint32_t>
 FuzzerPassConstructComposites::FindComponentsToConstructArray(
     const opt::Instruction& array_type_instruction,
     const TypeIdToInstructions& type_id_to_available_instructions) {
   assert(array_type_instruction.opcode() == SpvOpTypeArray &&
          "Precondition: instruction must be an array type.");

   // Get the element type for the array.
   auto element_type_id = array_type_instruction.GetSingleWordInOperand(0);

   // Get all instructions at our disposal that compute something of this element
   // type.
   auto available_instructions =
       type_id_to_available_instructions.find(element_type_id);

   if (available_instructions == type_id_to_available_instructions.cend()) {
     // If there are not any instructions available that compute the element type
     // of the array then we are not in a position to construct a composite with
     // this array type.
     return {};
   }

   uint32_t array_length =
       GetIRContext()
           ->get_def_use_mgr()
           ->GetDef(array_type_instruction.GetSingleWordInOperand(1))
           ->GetSingleWordInOperand(0);

   std::vector<uint32_t> result;
   for (uint32_t index = 0; index < array_length; index++) {
     result.push_back(available_instructions
                          ->second[GetFuzzerContext()->RandomIndex(
                              available_instructions->second)]
                          ->result_id());
   }
   return result;
 }

 std::vector<uint32_t>
 FuzzerPassConstructComposites::FindComponentsToConstructMatrix(
     const opt::Instruction& matrix_type_instruction,
     const TypeIdToInstructions& type_id_to_available_instructions) {
   assert(matrix_type_instruction.opcode() == SpvOpTypeMatrix &&
          "Precondition: instruction must be a matrix type.");

   // Get the element type for the matrix.
   auto element_type_id = matrix_type_instruction.GetSingleWordInOperand(0);

   // Get all instructions at our disposal that compute something of this element
   // type.
   auto available_instructions =
       type_id_to_available_instructions.find(element_type_id);

   if (available_instructions == type_id_to_available_instructions.cend()) {
     // If there are not any instructions available that compute the element type
     // of the matrix then we are not in a position to construct a composite with
     // this matrix type.
     return {};
   }
   std::vector<uint32_t> result;
   for (uint32_t index = 0;
        index < matrix_type_instruction.GetSingleWordInOperand(1); index++) {
     result.push_back(available_instructions
                          ->second[GetFuzzerContext()->RandomIndex(
                              available_instructions->second)]
                          ->result_id());
   }
   return result;
 }

 std::vector<uint32_t>
 FuzzerPassConstructComposites::FindComponentsToConstructStruct(
     const opt::Instruction& struct_type_instruction,
     const TypeIdToInstructions& type_id_to_available_instructions) {
   assert(struct_type_instruction.opcode() == SpvOpTypeStruct &&
          "Precondition: instruction must be a struct type.");
   std::vector<uint32_t> result;
   // Consider the type of each field of the struct.
   for (uint32_t in_operand_index = 0;
        in_operand_index < struct_type_instruction.NumInOperands();
        in_operand_index++) {
     auto element_type_id =
         struct_type_instruction.GetSingleWordInOperand(in_operand_index);
     // Find the instructions at our disposal that compute something of the field
     // type.
     auto available_instructions =
         type_id_to_available_instructions.find(element_type_id);
     if (available_instructions == type_id_to_available_instructions.cend()) {
       // If there are no such instructions, we cannot construct a composite of
       // this struct type.
       return {};
     }
     result.push_back(available_instructions
                          ->second[GetFuzzerContext()->RandomIndex(
                              available_instructions->second)]
                          ->result_id());
   }
   return result;
 }

 std::vector<uint32_t>
 FuzzerPassConstructComposites::FindComponentsToConstructVector(
     const opt::Instruction& vector_type_instruction,
     const TypeIdToInstructions& type_id_to_available_instructions) {
   assert(vector_type_instruction.opcode() == SpvOpTypeVector &&
          "Precondition: instruction must be a vector type.");

   // Get details of the type underlying the vector, and the width of the vector,
   // for convenience.
   auto element_type_id = vector_type_instruction.GetSingleWordInOperand(0);
   auto element_type = GetIRContext()->get_type_mgr()->GetType(element_type_id);
   auto element_count = vector_type_instruction.GetSingleWordInOperand(1);

   // Collect a mapping, from type id to width, for scalar/vector types that are
   // smaller in width than |vector_type|, but that have the same underlying
   // type.  For example, if |vector_type| is vec4, the mapping will be:
   //   { float -> 1, vec2 -> 2, vec3 -> 3 }
   // The mapping will have missing entries if some of these types do not exist.

   std::map<uint32_t, uint32_t> smaller_vector_type_id_to_width;
   // Add the underlying type.  This id must exist, in order for |vector_type| to
   // exist.
   smaller_vector_type_id_to_width[element_type_id] = 1;

   // Now add every vector type with width at least 2, and less than the width of
   // |vector_type|.
   for (uint32_t width = 2; width < element_count; width++) {
     opt::analysis::Vector smaller_vector_type(element_type, width);
     auto smaller_vector_type_id =
         GetIRContext()->get_type_mgr()->GetId(&smaller_vector_type);
     // We might find that there is no declared type of this smaller width.
     // For example, a module can declare vec4 without having declared vec2 or
     // vec3.
     if (smaller_vector_type_id) {
       smaller_vector_type_id_to_width[smaller_vector_type_id] = width;
     }
   }

   // Now we know the types that are available to us, we set about populating a
   // vector of the right length.  We do this by deciding, with no order in mind,
   // which instructions we will use to populate the vector, and subsequently
   // randomly choosing an order.  This is to avoid biasing construction of
   // vectors with smaller vectors to the left and scalars to the right.  That is
   // a concern because, e.g. in the case of populating a vec4, if we populate
   // the constructor instructions left-to-right, we can always choose a vec3 to
   // construct the first three elements, but can only choose a vec3 to construct
   // the last three elements if we chose a float to construct the first element
   // (otherwise there will not be space left for a vec3).

   uint32_t vector_slots_used = 0;
   // The instructions we will use to construct the vector, in no particular
   // order at this stage.
   std::vector<opt::Instruction*> instructions_to_use;

   while (vector_slots_used < element_count) {
     std::vector<opt::Instruction*> instructions_to_choose_from;
     for (auto& entry : smaller_vector_type_id_to_width) {
       if (entry.second >
           std::min(element_count - 1, element_count - vector_slots_used)) {
         continue;
       }
       auto available_instructions =
           type_id_to_available_instructions.find(entry.first);
       if (available_instructions == type_id_to_available_instructions.cend()) {
         continue;
       }
       instructions_to_choose_from.insert(instructions_to_choose_from.end(),
                                          available_instructions->second.begin(),
                                          available_instructions->second.end());
     }
     if (instructions_to_choose_from.empty()) {
       // We may get unlucky and find that there are not any instructions to
       // choose from.  In this case we give up constructing a composite of this
       // vector type.  It might be that we could construct the composite in
       // another manner, so we could opt to retry a few times here, but it is
       // simpler to just give up on the basis that this will not happen
       // frequently.
       return {};
     }
     auto instruction_to_use =
         instructions_to_choose_from[GetFuzzerContext()->RandomIndex(
             instructions_to_choose_from)];
     instructions_to_use.push_back(instruction_to_use);
     auto chosen_type =
         GetIRContext()->get_type_mgr()->GetType(instruction_to_use->type_id());
     if (chosen_type->AsVector()) {
       assert(chosen_type->AsVector()->element_type() == element_type);
       assert(chosen_type->AsVector()->element_count() < element_count);
       assert(chosen_type->AsVector()->element_count() <=
              element_count - vector_slots_used);
       vector_slots_used += chosen_type->AsVector()->element_count();
     } else {
       assert(chosen_type == element_type);
       vector_slots_used += 1;
     }
   }
   assert(vector_slots_used == element_count);

   std::vector<uint32_t> result;
   std::vector<uint32_t> operands;
   while (!instructions_to_use.empty()) {
     auto index = GetFuzzerContext()->RandomIndex(instructions_to_use);
     result.push_back(instructions_to_use[index]->result_id());
     instructions_to_use.erase(instructions_to_use.begin() + index);
   }
   assert(result.size() > 1);
   return result;
 }

 }  // namespace fuzz
 }  // namespace spvtools
	// Copyright (c) 2019 Google LLC
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	#include "source/fuzz/fuzzer_pass_construct_composites.h"

	#include <memory>

	#include "source/fuzz/fuzzer_util.h"
	#include "source/fuzz/transformation_composite_construct.h"

	namespace spvtools {
	namespace fuzz {

	FuzzerPassConstructComposites::FuzzerPassConstructComposites(
	opt::IRContext* ir_context, TransformationContext* transformation_context,
	FuzzerContext* fuzzer_context,
	protobufs::TransformationSequence* transformations)
	: FuzzerPass(ir_context, transformation_context, fuzzer_context,
	transformations) {}

	FuzzerPassConstructComposites::~FuzzerPassConstructComposites() = default;

	void FuzzerPassConstructComposites::Apply() {
	// Gather up the ids of all composite types, but skip block-/buffer
	// block-decorated struct types.
	std::vector<uint32_t> composite_type_ids;
	for (auto& inst : GetIRContext()->types_values()) {
	if (fuzzerutil::IsCompositeType(
	GetIRContext()->get_type_mgr()->GetType(inst.result_id())) &&
	!fuzzerutil::HasBlockOrBufferBlockDecoration(GetIRContext(),
	inst.result_id())) {
	composite_type_ids.push_back(inst.result_id());
	}
	}

	ForEachInstructionWithInstructionDescriptor(
	[this, &composite_type_ids](
	opt::Function* function, opt::BasicBlock* block,
	opt::BasicBlock::iterator inst_it,
	const protobufs::InstructionDescriptor& instruction_descriptor)
	-> void {
	// Check whether it is legitimate to insert a composite construction
	// before the instruction.
	if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(
	SpvOpCompositeConstruct, inst_it)) {
	return;
	}

	// Randomly decide whether to try inserting an object copy here.
	if (!GetFuzzerContext()->ChoosePercentage(
	GetFuzzerContext()->GetChanceOfConstructingComposite())) {
	return;
	}

	// For each instruction that is available at this program point (i.e. an
	// instruction that is global or whose definition strictly dominates the
	// program point) and suitable for making a synonym of, associate it
	// with the id of its result type.
	TypeIdToInstructions type_id_to_available_instructions;
	auto available_instructions = FindAvailableInstructions(
	function, block, inst_it,
	[this](opt::IRContext* ir_context, opt::Instruction* inst) {
	if (!inst->result_id() \|\| !inst->type_id()) {
	return false;
	}

	// If the id is irrelevant, we can use it since it will not
	// participate in DataSynonym fact. Otherwise, we should be able
	// to produce a synonym out of the id.
	return GetTransformationContext()
	->GetFactManager()
	->IdIsIrrelevant(inst->result_id()) \|\|
	fuzzerutil::CanMakeSynonymOf(
	ir_context, *GetTransformationContext(), inst);
	});
	for (auto instruction : available_instructions) {
	RecordAvailableInstruction(instruction,
	&type_id_to_available_instructions);
	}

	// At this point, \|composite_type_ids\| captures all the composite types
	// we could try to create, while \|type_id_to_available_instructions\|
	// captures all the available result ids we might use, organized by
	// type.

	// Now we try to find a composite that we can construct. We might not
	// manage, if there is a paucity of available ingredients in the module
	// (e.g. if our only available composite was a boolean vector and we had
	// no instructions generating boolean result types available).
	//
	// If we succeed, \|chosen_composite_type\| will end up being non-zero,
	// and \|constructor_arguments\| will end up giving us result ids suitable
	// for constructing a composite of that type. Otherwise these variables
	// will remain 0 and null respectively.
	uint32_t chosen_composite_type = 0;
	std::vector<uint32_t> constructor_arguments;

	// Initially, all composite type ids are available for us to try. Keep
	// trying until we run out of options.
	auto composites_to_try_constructing = composite_type_ids;
	while (!composites_to_try_constructing.empty()) {
	// Remove a composite type from the composite types left for us to
	// try.
	auto next_composite_to_try_constructing =
	GetFuzzerContext()->RemoveAtRandomIndex(
	&composites_to_try_constructing);

	// Now try to construct a composite of this type, using an appropriate
	// helper method depending on the kind of composite type.
	auto composite_type_inst = GetIRContext()->get_def_use_mgr()->GetDef(
	next_composite_to_try_constructing);
	switch (composite_type_inst->opcode()) {
	case SpvOpTypeArray:
	constructor_arguments = FindComponentsToConstructArray(
	*composite_type_inst, type_id_to_available_instructions);
	break;
	case SpvOpTypeMatrix:
	constructor_arguments = FindComponentsToConstructMatrix(
	*composite_type_inst, type_id_to_available_instructions);
	break;
	case SpvOpTypeStruct:
	constructor_arguments = FindComponentsToConstructStruct(
	*composite_type_inst, type_id_to_available_instructions);
	break;
	case SpvOpTypeVector:
	constructor_arguments = FindComponentsToConstructVector(
	*composite_type_inst, type_id_to_available_instructions);
	break;
	default:
	assert(false &&
	"The space of possible composite types should be covered "
	"by the above cases.");
	break;
	}
	if (!constructor_arguments.empty()) {
	// We succeeded! Note the composite type we finally settled on, and
	// exit from the loop.
	chosen_composite_type = next_composite_to_try_constructing;
	break;
	}
	}

	if (!chosen_composite_type) {
	// We did not manage to make a composite; return 0 to indicate that no
	// instructions were added.
	assert(constructor_arguments.empty());
	return;
	}
	assert(!constructor_arguments.empty());

	// Make and apply a transformation.
	ApplyTransformation(TransformationCompositeConstruct(
	chosen_composite_type, constructor_arguments,
	instruction_descriptor, GetFuzzerContext()->GetFreshId()));
	});
	}

	void FuzzerPassConstructComposites::RecordAvailableInstruction(
	opt::Instruction* inst,
	TypeIdToInstructions* type_id_to_available_instructions) {
	if (type_id_to_available_instructions->count(inst->type_id()) == 0) {
	(*type_id_to_available_instructions)[inst->type_id()] = {};
	}
	type_id_to_available_instructions->at(inst->type_id()).push_back(inst);
	}

	std::vector<uint32_t>
	FuzzerPassConstructComposites::FindComponentsToConstructArray(
	const opt::Instruction& array_type_instruction,
	const TypeIdToInstructions& type_id_to_available_instructions) {
	assert(array_type_instruction.opcode() == SpvOpTypeArray &&
	"Precondition: instruction must be an array type.");

	// Get the element type for the array.
	auto element_type_id = array_type_instruction.GetSingleWordInOperand(0);

	// Get all instructions at our disposal that compute something of this element
	// type.
	auto available_instructions =
	type_id_to_available_instructions.find(element_type_id);

	if (available_instructions == type_id_to_available_instructions.cend()) {
	// If there are not any instructions available that compute the element type
	// of the array then we are not in a position to construct a composite with
	// this array type.
	return {};
	}

	uint32_t array_length =
	GetIRContext()
	->get_def_use_mgr()
	->GetDef(array_type_instruction.GetSingleWordInOperand(1))
	->GetSingleWordInOperand(0);

	std::vector<uint32_t> result;
	for (uint32_t index = 0; index < array_length; index++) {
	result.push_back(available_instructions
	->second[GetFuzzerContext()->RandomIndex(
	available_instructions->second)]
	->result_id());
	}
	return result;
	}

	std::vector<uint32_t>
	FuzzerPassConstructComposites::FindComponentsToConstructMatrix(
	const opt::Instruction& matrix_type_instruction,
	const TypeIdToInstructions& type_id_to_available_instructions) {
	assert(matrix_type_instruction.opcode() == SpvOpTypeMatrix &&
	"Precondition: instruction must be a matrix type.");

	// Get the element type for the matrix.
	auto element_type_id = matrix_type_instruction.GetSingleWordInOperand(0);

	// Get all instructions at our disposal that compute something of this element
	// type.
	auto available_instructions =
	type_id_to_available_instructions.find(element_type_id);

	if (available_instructions == type_id_to_available_instructions.cend()) {
	// If there are not any instructions available that compute the element type
	// of the matrix then we are not in a position to construct a composite with
	// this matrix type.
	return {};
	}
	std::vector<uint32_t> result;
	for (uint32_t index = 0;
	index < matrix_type_instruction.GetSingleWordInOperand(1); index++) {
	result.push_back(available_instructions
	->second[GetFuzzerContext()->RandomIndex(
	available_instructions->second)]
	->result_id());
	}
	return result;
	}

	std::vector<uint32_t>
	FuzzerPassConstructComposites::FindComponentsToConstructStruct(
	const opt::Instruction& struct_type_instruction,
	const TypeIdToInstructions& type_id_to_available_instructions) {
	assert(struct_type_instruction.opcode() == SpvOpTypeStruct &&
	"Precondition: instruction must be a struct type.");
	std::vector<uint32_t> result;
	// Consider the type of each field of the struct.
	for (uint32_t in_operand_index = 0;
	in_operand_index < struct_type_instruction.NumInOperands();
	in_operand_index++) {
	auto element_type_id =
	struct_type_instruction.GetSingleWordInOperand(in_operand_index);
	// Find the instructions at our disposal that compute something of the field
	// type.
	auto available_instructions =
	type_id_to_available_instructions.find(element_type_id);
	if (available_instructions == type_id_to_available_instructions.cend()) {
	// If there are no such instructions, we cannot construct a composite of
	// this struct type.
	return {};
	}
	result.push_back(available_instructions
	->second[GetFuzzerContext()->RandomIndex(
	available_instructions->second)]
	->result_id());
	}
	return result;
	}

	std::vector<uint32_t>
	FuzzerPassConstructComposites::FindComponentsToConstructVector(
	const opt::Instruction& vector_type_instruction,
	const TypeIdToInstructions& type_id_to_available_instructions) {
	assert(vector_type_instruction.opcode() == SpvOpTypeVector &&
	"Precondition: instruction must be a vector type.");

	// Get details of the type underlying the vector, and the width of the vector,
	// for convenience.
	auto element_type_id = vector_type_instruction.GetSingleWordInOperand(0);
	auto element_type = GetIRContext()->get_type_mgr()->GetType(element_type_id);
	auto element_count = vector_type_instruction.GetSingleWordInOperand(1);

	// Collect a mapping, from type id to width, for scalar/vector types that are
	// smaller in width than \|vector_type\|, but that have the same underlying
	// type. For example, if \|vector_type\| is vec4, the mapping will be:
	// { float -> 1, vec2 -> 2, vec3 -> 3 }
	// The mapping will have missing entries if some of these types do not exist.

	std::map<uint32_t, uint32_t> smaller_vector_type_id_to_width;
	// Add the underlying type. This id must exist, in order for \|vector_type\| to
	// exist.
	smaller_vector_type_id_to_width[element_type_id] = 1;

	// Now add every vector type with width at least 2, and less than the width of
	// \|vector_type\|.
	for (uint32_t width = 2; width < element_count; width++) {
	opt::analysis::Vector smaller_vector_type(element_type, width);
	auto smaller_vector_type_id =
	GetIRContext()->get_type_mgr()->GetId(&smaller_vector_type);
	// We might find that there is no declared type of this smaller width.
	// For example, a module can declare vec4 without having declared vec2 or
	// vec3.
	if (smaller_vector_type_id) {
	smaller_vector_type_id_to_width[smaller_vector_type_id] = width;
	}
	}

	// Now we know the types that are available to us, we set about populating a
	// vector of the right length. We do this by deciding, with no order in mind,
	// which instructions we will use to populate the vector, and subsequently
	// randomly choosing an order. This is to avoid biasing construction of
	// vectors with smaller vectors to the left and scalars to the right. That is
	// a concern because, e.g. in the case of populating a vec4, if we populate
	// the constructor instructions left-to-right, we can always choose a vec3 to
	// construct the first three elements, but can only choose a vec3 to construct
	// the last three elements if we chose a float to construct the first element
	// (otherwise there will not be space left for a vec3).

	uint32_t vector_slots_used = 0;
	// The instructions we will use to construct the vector, in no particular
	// order at this stage.
	std::vector<opt::Instruction*> instructions_to_use;

	while (vector_slots_used < element_count) {
	std::vector<opt::Instruction*> instructions_to_choose_from;
	for (auto& entry : smaller_vector_type_id_to_width) {
	if (entry.second >
	std::min(element_count - 1, element_count - vector_slots_used)) {
	continue;
	}
	auto available_instructions =
	type_id_to_available_instructions.find(entry.first);
	if (available_instructions == type_id_to_available_instructions.cend()) {
	continue;
	}
	instructions_to_choose_from.insert(instructions_to_choose_from.end(),
	available_instructions->second.begin(),
	available_instructions->second.end());
	}
	if (instructions_to_choose_from.empty()) {
	// We may get unlucky and find that there are not any instructions to
	// choose from. In this case we give up constructing a composite of this
	// vector type. It might be that we could construct the composite in
	// another manner, so we could opt to retry a few times here, but it is
	// simpler to just give up on the basis that this will not happen
	// frequently.
	return {};
	}
	auto instruction_to_use =
	instructions_to_choose_from[GetFuzzerContext()->RandomIndex(
	instructions_to_choose_from)];
	instructions_to_use.push_back(instruction_to_use);
	auto chosen_type =
	GetIRContext()->get_type_mgr()->GetType(instruction_to_use->type_id());
	if (chosen_type->AsVector()) {
	assert(chosen_type->AsVector()->element_type() == element_type);
	assert(chosen_type->AsVector()->element_count() < element_count);
	assert(chosen_type->AsVector()->element_count() <=
	element_count - vector_slots_used);
	vector_slots_used += chosen_type->AsVector()->element_count();
	} else {
	assert(chosen_type == element_type);
	vector_slots_used += 1;
	}
	}
	assert(vector_slots_used == element_count);

	std::vector<uint32_t> result;
	std::vector<uint32_t> operands;
	while (!instructions_to_use.empty()) {
	auto index = GetFuzzerContext()->RandomIndex(instructions_to_use);
	result.push_back(instructions_to_use[index]->result_id());
	instructions_to_use.erase(instructions_to_use.begin() + index);
	}
	assert(result.size() > 1);
	return result;
	}

	} // namespace fuzz
	} // namespace spvtools