| 1 |
// Copyright (c) 2019 Google LLC |
| 2 |
// |
| 3 |
// Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 |
// you may not use this file except in compliance with the License. |
| 5 |
// You may obtain a copy of the License at |
| 6 |
// |
| 7 |
// http://www.apache.org/licenses/LICENSE-2.0 |
| 8 |
// |
| 9 |
// Unless required by applicable law or agreed to in writing, software |
| 10 |
// distributed under the License is distributed on an "AS IS" BASIS, |
| 11 |
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 |
// See the License for the specific language governing permissions and |
| 13 |
// limitations under the License. |
| 14 |
|
| 15 |
#include "source/fuzz/fuzzer_pass_construct_composites.h" |
| 16 |
|
| 17 |
#include <memory> |
| 18 |
|
| 19 |
#include "source/fuzz/fuzzer_util.h" |
| 20 |
#include "source/fuzz/transformation_composite_construct.h" |
| 21 |
|
| 22 |
namespace spvtools { |
| 23 |
namespace fuzz { |
| 24 |
|
| 25 |
FuzzerPassConstructComposites::FuzzerPassConstructComposites( |
| 26 |
opt::IRContext* ir_context, TransformationContext* transformation_context, |
| 27 |
FuzzerContext* fuzzer_context, |
| 28 |
protobufs::TransformationSequence* transformations) |
| 29 |
: FuzzerPass(ir_context, transformation_context, fuzzer_context, |
| 30 |
transformations) {} |
| 31 |
|
| 32 |
FuzzerPassConstructComposites::~FuzzerPassConstructComposites() = default; |
| 33 |
|
| 34 |
void FuzzerPassConstructComposites::Apply() { |
| 35 |
// Gather up the ids of all composite types, but skip block-/buffer |
| 36 |
// block-decorated struct types. |
| 37 |
std::vector<uint32_t> composite_type_ids; |
| 38 |
for (auto& inst : GetIRContext()->types_values()) { |
| 39 |
if (fuzzerutil::IsCompositeType( |
| 40 |
GetIRContext()->get_type_mgr()->GetType(inst.result_id())) && |
| 41 |
!fuzzerutil::HasBlockOrBufferBlockDecoration(GetIRContext(), |
| 42 |
inst.result_id())) { |
| 43 |
composite_type_ids.push_back(inst.result_id()); |
| 44 |
} |
| 45 |
} |
| 46 |
|
| 47 |
ForEachInstructionWithInstructionDescriptor( |
| 48 |
[this, &composite_type_ids]( |
| 49 |
opt::Function* function, opt::BasicBlock* block, |
| 50 |
opt::BasicBlock::iterator inst_it, |
| 51 |
const protobufs::InstructionDescriptor& instruction_descriptor) |
| 52 |
-> void { |
| 53 |
// Check whether it is legitimate to insert a composite construction |
| 54 |
// before the instruction. |
| 55 |
if (!fuzzerutil::CanInsertOpcodeBeforeInstruction( |
| 56 |
SpvOpCompositeConstruct, inst_it)) { |
| 57 |
return; |
| 58 |
} |
| 59 |
|
| 60 |
// Randomly decide whether to try inserting an object copy here. |
| 61 |
if (!GetFuzzerContext()->ChoosePercentage( |
| 62 |
GetFuzzerContext()->GetChanceOfConstructingComposite())) { |
| 63 |
return; |
| 64 |
} |
| 65 |
|
| 66 |
// For each instruction that is available at this program point (i.e. an |
| 67 |
// instruction that is global or whose definition strictly dominates the |
| 68 |
// program point) and suitable for making a synonym of, associate it |
| 69 |
// with the id of its result type. |
| 70 |
TypeIdToInstructions type_id_to_available_instructions; |
| 71 |
auto available_instructions = FindAvailableInstructions( |
| 72 |
function, block, inst_it, |
| 73 |
[this](opt::IRContext* ir_context, opt::Instruction* inst) { |
| 74 |
if (!inst->result_id() || !inst->type_id()) { |
| 75 |
return false; |
| 76 |
} |
| 77 |
|
| 78 |
// If the id is irrelevant, we can use it since it will not |
| 79 |
// participate in DataSynonym fact. Otherwise, we should be able |
| 80 |
// to produce a synonym out of the id. |
| 81 |
return GetTransformationContext() |
| 82 |
->GetFactManager() |
| 83 |
->IdIsIrrelevant(inst->result_id()) || |
| 84 |
fuzzerutil::CanMakeSynonymOf( |
| 85 |
ir_context, *GetTransformationContext(), inst); |
| 86 |
}); |
| 87 |
for (auto instruction : available_instructions) { |
| 88 |
RecordAvailableInstruction(instruction, |
| 89 |
&type_id_to_available_instructions); |
| 90 |
} |
| 91 |
|
| 92 |
// At this point, |composite_type_ids| captures all the composite types |
| 93 |
// we could try to create, while |type_id_to_available_instructions| |
| 94 |
// captures all the available result ids we might use, organized by |
| 95 |
// type. |
| 96 |
|
| 97 |
// Now we try to find a composite that we can construct. We might not |
| 98 |
// manage, if there is a paucity of available ingredients in the module |
| 99 |
// (e.g. if our only available composite was a boolean vector and we had |
| 100 |
// no instructions generating boolean result types available). |
| 101 |
// |
| 102 |
// If we succeed, |chosen_composite_type| will end up being non-zero, |
| 103 |
// and |constructor_arguments| will end up giving us result ids suitable |
| 104 |
// for constructing a composite of that type. Otherwise these variables |
| 105 |
// will remain 0 and null respectively. |
| 106 |
uint32_t chosen_composite_type = 0; |
| 107 |
std::vector<uint32_t> constructor_arguments; |
| 108 |
|
| 109 |
// Initially, all composite type ids are available for us to try. Keep |
| 110 |
// trying until we run out of options. |
| 111 |
auto composites_to_try_constructing = composite_type_ids; |
| 112 |
while (!composites_to_try_constructing.empty()) { |
| 113 |
// Remove a composite type from the composite types left for us to |
| 114 |
// try. |
| 115 |
auto next_composite_to_try_constructing = |
| 116 |
GetFuzzerContext()->RemoveAtRandomIndex( |
| 117 |
&composites_to_try_constructing); |
| 118 |
|
| 119 |
// Now try to construct a composite of this type, using an appropriate |
| 120 |
// helper method depending on the kind of composite type. |
| 121 |
auto composite_type_inst = GetIRContext()->get_def_use_mgr()->GetDef( |
| 122 |
next_composite_to_try_constructing); |
| 123 |
switch (composite_type_inst->opcode()) { |
| 124 |
case SpvOpTypeArray: |
| 125 |
constructor_arguments = FindComponentsToConstructArray( |
| 126 |
*composite_type_inst, type_id_to_available_instructions); |
| 127 |
break; |
| 128 |
case SpvOpTypeMatrix: |
| 129 |
constructor_arguments = FindComponentsToConstructMatrix( |
| 130 |
*composite_type_inst, type_id_to_available_instructions); |
| 131 |
break; |
| 132 |
case SpvOpTypeStruct: |
| 133 |
constructor_arguments = FindComponentsToConstructStruct( |
| 134 |
*composite_type_inst, type_id_to_available_instructions); |
| 135 |
break; |
| 136 |
case SpvOpTypeVector: |
| 137 |
constructor_arguments = FindComponentsToConstructVector( |
| 138 |
*composite_type_inst, type_id_to_available_instructions); |
| 139 |
break; |
| 140 |
default: |
| 141 |
assert(false && |
| 142 |
"The space of possible composite types should be covered " |
| 143 |
"by the above cases."); |
| 144 |
break; |
| 145 |
} |
| 146 |
if (!constructor_arguments.empty()) { |
| 147 |
// We succeeded! Note the composite type we finally settled on, and |
| 148 |
// exit from the loop. |
| 149 |
chosen_composite_type = next_composite_to_try_constructing; |
| 150 |
break; |
| 151 |
} |
| 152 |
} |
| 153 |
|
| 154 |
if (!chosen_composite_type) { |
| 155 |
// We did not manage to make a composite; return 0 to indicate that no |
| 156 |
// instructions were added. |
| 157 |
assert(constructor_arguments.empty()); |
| 158 |
return; |
| 159 |
} |
| 160 |
assert(!constructor_arguments.empty()); |
| 161 |
|
| 162 |
// Make and apply a transformation. |
| 163 |
ApplyTransformation(TransformationCompositeConstruct( |
| 164 |
chosen_composite_type, constructor_arguments, |
| 165 |
instruction_descriptor, GetFuzzerContext()->GetFreshId())); |
| 166 |
}); |
| 167 |
} |
| 168 |
|
| 169 |
void FuzzerPassConstructComposites::RecordAvailableInstruction( |
| 170 |
opt::Instruction* inst, |
| 171 |
TypeIdToInstructions* type_id_to_available_instructions) { |
| 172 |
if (type_id_to_available_instructions->count(inst->type_id()) == 0) { |
| 173 |
(*type_id_to_available_instructions)[inst->type_id()] = {}; |
| 174 |
} |
| 175 |
type_id_to_available_instructions->at(inst->type_id()).push_back(inst); |
| 176 |
} |
| 177 |
|
| 178 |
std::vector<uint32_t> |
| 179 |
FuzzerPassConstructComposites::FindComponentsToConstructArray( |
| 180 |
const opt::Instruction& array_type_instruction, |
| 181 |
const TypeIdToInstructions& type_id_to_available_instructions) { |
| 182 |
assert(array_type_instruction.opcode() == SpvOpTypeArray && |
| 183 |
"Precondition: instruction must be an array type."); |
| 184 |
|
| 185 |
// Get the element type for the array. |
| 186 |
auto element_type_id = array_type_instruction.GetSingleWordInOperand(0); |
| 187 |
|
| 188 |
// Get all instructions at our disposal that compute something of this element |
| 189 |
// type. |
| 190 |
auto available_instructions = |
| 191 |
type_id_to_available_instructions.find(element_type_id); |
| 192 |
|
| 193 |
if (available_instructions == type_id_to_available_instructions.cend()) { |
| 194 |
// If there are not any instructions available that compute the element type |
| 195 |
// of the array then we are not in a position to construct a composite with |
| 196 |
// this array type. |
| 197 |
return {}; |
| 198 |
} |
| 199 |
|
| 200 |
uint32_t array_length = |
| 201 |
GetIRContext() |
| 202 |
->get_def_use_mgr() |
| 203 |
->GetDef(array_type_instruction.GetSingleWordInOperand(1)) |
| 204 |
->GetSingleWordInOperand(0); |
| 205 |
|
| 206 |
std::vector<uint32_t> result; |
| 207 |
for (uint32_t index = 0; index < array_length; index++) { |
| 208 |
result.push_back(available_instructions |
| 209 |
->second[GetFuzzerContext()->RandomIndex( |
| 210 |
available_instructions->second)] |
| 211 |
->result_id()); |
| 212 |
} |
| 213 |
return result; |
| 214 |
} |
| 215 |
|
| 216 |
std::vector<uint32_t> |
| 217 |
FuzzerPassConstructComposites::FindComponentsToConstructMatrix( |
| 218 |
const opt::Instruction& matrix_type_instruction, |
| 219 |
const TypeIdToInstructions& type_id_to_available_instructions) { |
| 220 |
assert(matrix_type_instruction.opcode() == SpvOpTypeMatrix && |
| 221 |
"Precondition: instruction must be a matrix type."); |
| 222 |
|
| 223 |
// Get the element type for the matrix. |
| 224 |
auto element_type_id = matrix_type_instruction.GetSingleWordInOperand(0); |
| 225 |
|
| 226 |
// Get all instructions at our disposal that compute something of this element |
| 227 |
// type. |
| 228 |
auto available_instructions = |
| 229 |
type_id_to_available_instructions.find(element_type_id); |
| 230 |
|
| 231 |
if (available_instructions == type_id_to_available_instructions.cend()) { |
| 232 |
// If there are not any instructions available that compute the element type |
| 233 |
// of the matrix then we are not in a position to construct a composite with |
| 234 |
// this matrix type. |
| 235 |
return {}; |
| 236 |
} |
| 237 |
std::vector<uint32_t> result; |
| 238 |
for (uint32_t index = 0; |
| 239 |
index < matrix_type_instruction.GetSingleWordInOperand(1); index++) { |
| 240 |
result.push_back(available_instructions |
| 241 |
->second[GetFuzzerContext()->RandomIndex( |
| 242 |
available_instructions->second)] |
| 243 |
->result_id()); |
| 244 |
} |
| 245 |
return result; |
| 246 |
} |
| 247 |
|
| 248 |
std::vector<uint32_t> |
| 249 |
FuzzerPassConstructComposites::FindComponentsToConstructStruct( |
| 250 |
const opt::Instruction& struct_type_instruction, |
| 251 |
const TypeIdToInstructions& type_id_to_available_instructions) { |
| 252 |
assert(struct_type_instruction.opcode() == SpvOpTypeStruct && |
| 253 |
"Precondition: instruction must be a struct type."); |
| 254 |
std::vector<uint32_t> result; |
| 255 |
// Consider the type of each field of the struct. |
| 256 |
for (uint32_t in_operand_index = 0; |
| 257 |
in_operand_index < struct_type_instruction.NumInOperands(); |
| 258 |
in_operand_index++) { |
| 259 |
auto element_type_id = |
| 260 |
struct_type_instruction.GetSingleWordInOperand(in_operand_index); |
| 261 |
// Find the instructions at our disposal that compute something of the field |
| 262 |
// type. |
| 263 |
auto available_instructions = |
| 264 |
type_id_to_available_instructions.find(element_type_id); |
| 265 |
if (available_instructions == type_id_to_available_instructions.cend()) { |
| 266 |
// If there are no such instructions, we cannot construct a composite of |
| 267 |
// this struct type. |
| 268 |
return {}; |
| 269 |
} |
| 270 |
result.push_back(available_instructions |
| 271 |
->second[GetFuzzerContext()->RandomIndex( |
| 272 |
available_instructions->second)] |
| 273 |
->result_id()); |
| 274 |
} |
| 275 |
return result; |
| 276 |
} |
| 277 |
|
| 278 |
std::vector<uint32_t> |
| 279 |
FuzzerPassConstructComposites::FindComponentsToConstructVector( |
| 280 |
const opt::Instruction& vector_type_instruction, |
| 281 |
const TypeIdToInstructions& type_id_to_available_instructions) { |
| 282 |
assert(vector_type_instruction.opcode() == SpvOpTypeVector && |
| 283 |
"Precondition: instruction must be a vector type."); |
| 284 |
|
| 285 |
// Get details of the type underlying the vector, and the width of the vector, |
| 286 |
// for convenience. |
| 287 |
auto element_type_id = vector_type_instruction.GetSingleWordInOperand(0); |
| 288 |
auto element_type = GetIRContext()->get_type_mgr()->GetType(element_type_id); |
| 289 |
auto element_count = vector_type_instruction.GetSingleWordInOperand(1); |
| 290 |
|
| 291 |
// Collect a mapping, from type id to width, for scalar/vector types that are |
| 292 |
// smaller in width than |vector_type|, but that have the same underlying |
| 293 |
// type. For example, if |vector_type| is vec4, the mapping will be: |
| 294 |
// { float -> 1, vec2 -> 2, vec3 -> 3 } |
| 295 |
// The mapping will have missing entries if some of these types do not exist. |
| 296 |
|
| 297 |
std::map<uint32_t, uint32_t> smaller_vector_type_id_to_width; |
| 298 |
// Add the underlying type. This id must exist, in order for |vector_type| to |
| 299 |
// exist. |
| 300 |
smaller_vector_type_id_to_width[element_type_id] = 1; |
| 301 |
|
| 302 |
// Now add every vector type with width at least 2, and less than the width of |
| 303 |
// |vector_type|. |
| 304 |
for (uint32_t width = 2; width < element_count; width++) { |
| 305 |
opt::analysis::Vector smaller_vector_type(element_type, width); |
| 306 |
auto smaller_vector_type_id = |
| 307 |
GetIRContext()->get_type_mgr()->GetId(&smaller_vector_type); |
| 308 |
// We might find that there is no declared type of this smaller width. |
| 309 |
// For example, a module can declare vec4 without having declared vec2 or |
| 310 |
// vec3. |
| 311 |
if (smaller_vector_type_id) { |
| 312 |
smaller_vector_type_id_to_width[smaller_vector_type_id] = width; |
| 313 |
} |
| 314 |
} |
| 315 |
|
| 316 |
// Now we know the types that are available to us, we set about populating a |
| 317 |
// vector of the right length. We do this by deciding, with no order in mind, |
| 318 |
// which instructions we will use to populate the vector, and subsequently |
| 319 |
// randomly choosing an order. This is to avoid biasing construction of |
| 320 |
// vectors with smaller vectors to the left and scalars to the right. That is |
| 321 |
// a concern because, e.g. in the case of populating a vec4, if we populate |
| 322 |
// the constructor instructions left-to-right, we can always choose a vec3 to |
| 323 |
// construct the first three elements, but can only choose a vec3 to construct |
| 324 |
// the last three elements if we chose a float to construct the first element |
| 325 |
// (otherwise there will not be space left for a vec3). |
| 326 |
|
| 327 |
uint32_t vector_slots_used = 0; |
| 328 |
// The instructions we will use to construct the vector, in no particular |
| 329 |
// order at this stage. |
| 330 |
std::vector<opt::Instruction*> instructions_to_use; |
| 331 |
|
| 332 |
while (vector_slots_used < element_count) { |
| 333 |
std::vector<opt::Instruction*> instructions_to_choose_from; |
| 334 |
for (auto& entry : smaller_vector_type_id_to_width) { |
| 335 |
if (entry.second > |
| 336 |
std::min(element_count - 1, element_count - vector_slots_used)) { |
| 337 |
continue; |
| 338 |
} |
| 339 |
auto available_instructions = |
| 340 |
type_id_to_available_instructions.find(entry.first); |
| 341 |
if (available_instructions == type_id_to_available_instructions.cend()) { |
| 342 |
continue; |
| 343 |
} |
| 344 |
instructions_to_choose_from.insert(instructions_to_choose_from.end(), |
| 345 |
available_instructions->second.begin(), |
| 346 |
available_instructions->second.end()); |
| 347 |
} |
| 348 |
if (instructions_to_choose_from.empty()) { |
| 349 |
// We may get unlucky and find that there are not any instructions to |
| 350 |
// choose from. In this case we give up constructing a composite of this |
| 351 |
// vector type. It might be that we could construct the composite in |
| 352 |
// another manner, so we could opt to retry a few times here, but it is |
| 353 |
// simpler to just give up on the basis that this will not happen |
| 354 |
// frequently. |
| 355 |
return {}; |
| 356 |
} |
| 357 |
auto instruction_to_use = |
| 358 |
instructions_to_choose_from[GetFuzzerContext()->RandomIndex( |
| 359 |
instructions_to_choose_from)]; |
| 360 |
instructions_to_use.push_back(instruction_to_use); |
| 361 |
auto chosen_type = |
| 362 |
GetIRContext()->get_type_mgr()->GetType(instruction_to_use->type_id()); |
| 363 |
if (chosen_type->AsVector()) { |
| 364 |
assert(chosen_type->AsVector()->element_type() == element_type); |
| 365 |
assert(chosen_type->AsVector()->element_count() < element_count); |
| 366 |
assert(chosen_type->AsVector()->element_count() <= |
| 367 |
element_count - vector_slots_used); |
| 368 |
vector_slots_used += chosen_type->AsVector()->element_count(); |
| 369 |
} else { |
| 370 |
assert(chosen_type == element_type); |
| 371 |
vector_slots_used += 1; |
| 372 |
} |
| 373 |
} |
| 374 |
assert(vector_slots_used == element_count); |
| 375 |
|
| 376 |
std::vector<uint32_t> result; |
| 377 |
std::vector<uint32_t> operands; |
| 378 |
while (!instructions_to_use.empty()) { |
| 379 |
auto index = GetFuzzerContext()->RandomIndex(instructions_to_use); |
| 380 |
result.push_back(instructions_to_use[index]->result_id()); |
| 381 |
instructions_to_use.erase(instructions_to_use.begin() + index); |
| 382 |
} |
| 383 |
assert(result.size() > 1); |
| 384 |
return result; |
| 385 |
} |
| 386 |
|
| 387 |
} // namespace fuzz |
| 388 |
} // namespace spvtools |