| 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_donate_modules.h" |
| 16 |
|
| 17 |
#include <map> |
| 18 |
#include <queue> |
| 19 |
#include <set> |
| 20 |
|
| 21 |
#include "source/fuzz/call_graph.h" |
| 22 |
#include "source/fuzz/instruction_message.h" |
| 23 |
#include "source/fuzz/transformation_add_constant_boolean.h" |
| 24 |
#include "source/fuzz/transformation_add_constant_composite.h" |
| 25 |
#include "source/fuzz/transformation_add_constant_null.h" |
| 26 |
#include "source/fuzz/transformation_add_constant_scalar.h" |
| 27 |
#include "source/fuzz/transformation_add_function.h" |
| 28 |
#include "source/fuzz/transformation_add_global_undef.h" |
| 29 |
#include "source/fuzz/transformation_add_global_variable.h" |
| 30 |
#include "source/fuzz/transformation_add_spec_constant_op.h" |
| 31 |
#include "source/fuzz/transformation_add_type_array.h" |
| 32 |
#include "source/fuzz/transformation_add_type_boolean.h" |
| 33 |
#include "source/fuzz/transformation_add_type_float.h" |
| 34 |
#include "source/fuzz/transformation_add_type_function.h" |
| 35 |
#include "source/fuzz/transformation_add_type_int.h" |
| 36 |
#include "source/fuzz/transformation_add_type_matrix.h" |
| 37 |
#include "source/fuzz/transformation_add_type_pointer.h" |
| 38 |
#include "source/fuzz/transformation_add_type_struct.h" |
| 39 |
#include "source/fuzz/transformation_add_type_vector.h" |
| 40 |
|
| 41 |
namespace spvtools { |
| 42 |
namespace fuzz { |
| 43 |
|
| 44 |
FuzzerPassDonateModules::FuzzerPassDonateModules( |
| 45 |
opt::IRContext* ir_context, TransformationContext* transformation_context, |
| 46 |
FuzzerContext* fuzzer_context, |
| 47 |
protobufs::TransformationSequence* transformations, |
| 48 |
const std::vector<fuzzerutil::ModuleSupplier>& donor_suppliers) |
| 49 |
: FuzzerPass(ir_context, transformation_context, fuzzer_context, |
| 50 |
transformations), |
| 51 |
donor_suppliers_(donor_suppliers) {} |
| 52 |
|
| 53 |
FuzzerPassDonateModules::~FuzzerPassDonateModules() = default; |
| 54 |
|
| 55 |
void FuzzerPassDonateModules::Apply() { |
| 56 |
// If there are no donor suppliers, this fuzzer pass is a no-op. |
| 57 |
if (donor_suppliers_.empty()) { |
| 58 |
return; |
| 59 |
} |
| 60 |
|
| 61 |
// Donate at least one module, and probabilistically decide when to stop |
| 62 |
// donating modules. |
| 63 |
do { |
| 64 |
// Choose a donor supplier at random, and get the module that it provides. |
| 65 |
std::unique_ptr<opt::IRContext> donor_ir_context = donor_suppliers_.at( |
| 66 |
GetFuzzerContext()->RandomIndex(donor_suppliers_))(); |
| 67 |
assert(donor_ir_context != nullptr && "Supplying of donor failed"); |
| 68 |
assert( |
| 69 |
fuzzerutil::IsValid(donor_ir_context.get(), |
| 70 |
GetTransformationContext()->GetValidatorOptions(), |
| 71 |
fuzzerutil::kSilentMessageConsumer) && |
| 72 |
"The donor module must be valid"); |
| 73 |
// Donate the supplied module. |
| 74 |
// |
| 75 |
// Randomly decide whether to make the module livesafe (see |
| 76 |
// FactFunctionIsLivesafe); doing so allows it to be used for live code |
| 77 |
// injection but restricts its behaviour to allow this, and means that its |
| 78 |
// functions cannot be transformed as if they were arbitrary dead code. |
| 79 |
bool make_livesafe = GetFuzzerContext()->ChoosePercentage( |
| 80 |
GetFuzzerContext()->ChanceOfMakingDonorLivesafe()); |
| 81 |
DonateSingleModule(donor_ir_context.get(), make_livesafe); |
| 82 |
} while (GetFuzzerContext()->ChoosePercentage( |
| 83 |
GetFuzzerContext()->GetChanceOfDonatingAdditionalModule())); |
| 84 |
} |
| 85 |
|
| 86 |
void FuzzerPassDonateModules::DonateSingleModule( |
| 87 |
opt::IRContext* donor_ir_context, bool make_livesafe) { |
| 88 |
// Check that the donated module has capabilities, supported by the recipient |
| 89 |
// module. |
| 90 |
for (const auto& capability_inst : donor_ir_context->capabilities()) { |
| 91 |
auto capability = |
| 92 |
static_cast<SpvCapability>(capability_inst.GetSingleWordInOperand(0)); |
| 93 |
if (!GetIRContext()->get_feature_mgr()->HasCapability(capability)) { |
| 94 |
return; |
| 95 |
} |
| 96 |
} |
| 97 |
|
| 98 |
// The ids used by the donor module may very well clash with ids defined in |
| 99 |
// the recipient module. Furthermore, some instructions defined in the donor |
| 100 |
// module will be equivalent to instructions defined in the recipient module, |
| 101 |
// and it is not always legal to re-declare equivalent instructions. For |
| 102 |
// example, OpTypeVoid cannot be declared twice. |
| 103 |
// |
| 104 |
// To handle this, we maintain a mapping from an id used in the donor module |
| 105 |
// to the corresponding id that will be used by the donated code when it |
| 106 |
// appears in the recipient module. |
| 107 |
// |
| 108 |
// This mapping is populated in two ways: |
| 109 |
// (1) by mapping a donor instruction's result id to the id of some equivalent |
| 110 |
// existing instruction in the recipient (e.g. this has to be done for |
| 111 |
// OpTypeVoid) |
| 112 |
// (2) by mapping a donor instruction's result id to a freshly chosen id that |
| 113 |
// is guaranteed to be different from any id already used by the recipient |
| 114 |
// (or from any id already chosen to handle a previous donor id) |
| 115 |
std::map<uint32_t, uint32_t> original_id_to_donated_id; |
| 116 |
|
| 117 |
HandleExternalInstructionImports(donor_ir_context, |
| 118 |
&original_id_to_donated_id); |
| 119 |
HandleTypesAndValues(donor_ir_context, &original_id_to_donated_id); |
| 120 |
HandleFunctions(donor_ir_context, &original_id_to_donated_id, make_livesafe); |
| 121 |
|
| 122 |
// TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3115) Handle some |
| 123 |
// kinds of decoration. |
| 124 |
} |
| 125 |
|
| 126 |
SpvStorageClass FuzzerPassDonateModules::AdaptStorageClass( |
| 127 |
SpvStorageClass donor_storage_class) { |
| 128 |
switch (donor_storage_class) { |
| 129 |
case SpvStorageClassFunction: |
| 130 |
case SpvStorageClassPrivate: |
| 131 |
case SpvStorageClassWorkgroup: |
| 132 |
// We leave these alone |
| 133 |
return donor_storage_class; |
| 134 |
case SpvStorageClassInput: |
| 135 |
case SpvStorageClassOutput: |
| 136 |
case SpvStorageClassUniform: |
| 137 |
case SpvStorageClassUniformConstant: |
| 138 |
case SpvStorageClassPushConstant: |
| 139 |
case SpvStorageClassImage: |
| 140 |
case SpvStorageClassStorageBuffer: |
| 141 |
// We change these to Private |
| 142 |
return SpvStorageClassPrivate; |
| 143 |
default: |
| 144 |
// Handle other cases on demand. |
| 145 |
assert(false && "Currently unsupported storage class."); |
| 146 |
return SpvStorageClassMax; |
| 147 |
} |
| 148 |
} |
| 149 |
|
| 150 |
void FuzzerPassDonateModules::HandleExternalInstructionImports( |
| 151 |
opt::IRContext* donor_ir_context, |
| 152 |
std::map<uint32_t, uint32_t>* original_id_to_donated_id) { |
| 153 |
// Consider every external instruction set import in the donor module. |
| 154 |
for (auto& donor_import : donor_ir_context->module()->ext_inst_imports()) { |
| 155 |
const auto& donor_import_name_words = donor_import.GetInOperand(0).words; |
| 156 |
// Look for an identical import in the recipient module. |
| 157 |
for (auto& existing_import : GetIRContext()->module()->ext_inst_imports()) { |
| 158 |
const auto& existing_import_name_words = |
| 159 |
existing_import.GetInOperand(0).words; |
| 160 |
if (donor_import_name_words == existing_import_name_words) { |
| 161 |
// A matching import has found. Map the result id for the donor import |
| 162 |
// to the id of the existing import, so that when donor instructions |
| 163 |
// rely on the import they will be rewritten to use the existing import. |
| 164 |
original_id_to_donated_id->insert( |
| 165 |
{donor_import.result_id(), existing_import.result_id()}); |
| 166 |
break; |
| 167 |
} |
| 168 |
} |
| 169 |
// TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3116): At present |
| 170 |
// we do not handle donation of instruction imports, i.e. we do not allow |
| 171 |
// the donor to import instruction sets that the recipient did not already |
| 172 |
// import. It might be a good idea to allow this, but it requires some |
| 173 |
// thought. |
| 174 |
assert(original_id_to_donated_id->count(donor_import.result_id()) && |
| 175 |
"Donation of imports is not yet supported."); |
| 176 |
} |
| 177 |
} |
| 178 |
|
| 179 |
void FuzzerPassDonateModules::HandleTypesAndValues( |
| 180 |
opt::IRContext* donor_ir_context, |
| 181 |
std::map<uint32_t, uint32_t>* original_id_to_donated_id) { |
| 182 |
// Consider every type/global/constant/undef in the module. |
| 183 |
for (auto& type_or_value : donor_ir_context->module()->types_values()) { |
| 184 |
HandleTypeOrValue(type_or_value, original_id_to_donated_id); |
| 185 |
} |
| 186 |
} |
| 187 |
|
| 188 |
void FuzzerPassDonateModules::HandleTypeOrValue( |
| 189 |
const opt::Instruction& type_or_value, |
| 190 |
std::map<uint32_t, uint32_t>* original_id_to_donated_id) { |
| 191 |
// The type/value instruction generates a result id, and we need to associate |
| 192 |
// the donor's result id with a new result id. That new result id will either |
| 193 |
// be the id of some existing instruction, or a fresh id. This variable |
| 194 |
// captures it. |
| 195 |
uint32_t new_result_id; |
| 196 |
|
| 197 |
// Decide how to handle each kind of instruction on a case-by-case basis. |
| 198 |
// |
| 199 |
// Because the donor module is required to be valid, when we encounter a |
| 200 |
// type comprised of component types (e.g. an aggregate or pointer), we know |
| 201 |
// that its component types will have been considered previously, and that |
| 202 |
// |original_id_to_donated_id| will already contain an entry for them. |
| 203 |
switch (type_or_value.opcode()) { |
| 204 |
case SpvOpTypeImage: |
| 205 |
case SpvOpTypeSampledImage: |
| 206 |
case SpvOpTypeSampler: |
| 207 |
// We do not donate types and variables that relate to images and |
| 208 |
// samplers, so we skip these types and subsequently skip anything that |
| 209 |
// depends on them. |
| 210 |
return; |
| 211 |
case SpvOpTypeVoid: { |
| 212 |
// Void has to exist already in order for us to have an entry point. |
| 213 |
// Get the existing id of void. |
| 214 |
opt::analysis::Void void_type; |
| 215 |
new_result_id = GetIRContext()->get_type_mgr()->GetId(&void_type); |
| 216 |
assert(new_result_id && |
| 217 |
"The module being transformed will always have 'void' type " |
| 218 |
"declared."); |
| 219 |
} break; |
| 220 |
case SpvOpTypeBool: { |
| 221 |
// Bool cannot be declared multiple times, so use its existing id if |
| 222 |
// present, or add a declaration of Bool with a fresh id if not. |
| 223 |
opt::analysis::Bool bool_type; |
| 224 |
auto bool_type_id = GetIRContext()->get_type_mgr()->GetId(&bool_type); |
| 225 |
if (bool_type_id) { |
| 226 |
new_result_id = bool_type_id; |
| 227 |
} else { |
| 228 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 229 |
ApplyTransformation(TransformationAddTypeBoolean(new_result_id)); |
| 230 |
} |
| 231 |
} break; |
| 232 |
case SpvOpTypeInt: { |
| 233 |
// Int cannot be declared multiple times with the same width and |
| 234 |
// signedness, so check whether an existing identical Int type is |
| 235 |
// present and use its id if so. Otherwise add a declaration of the |
| 236 |
// Int type used by the donor, with a fresh id. |
| 237 |
const uint32_t width = type_or_value.GetSingleWordInOperand(0); |
| 238 |
const bool is_signed = |
| 239 |
static_cast<bool>(type_or_value.GetSingleWordInOperand(1)); |
| 240 |
opt::analysis::Integer int_type(width, is_signed); |
| 241 |
auto int_type_id = GetIRContext()->get_type_mgr()->GetId(&int_type); |
| 242 |
if (int_type_id) { |
| 243 |
new_result_id = int_type_id; |
| 244 |
} else { |
| 245 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 246 |
ApplyTransformation( |
| 247 |
TransformationAddTypeInt(new_result_id, width, is_signed)); |
| 248 |
} |
| 249 |
} break; |
| 250 |
case SpvOpTypeFloat: { |
| 251 |
// Similar to SpvOpTypeInt. |
| 252 |
const uint32_t width = type_or_value.GetSingleWordInOperand(0); |
| 253 |
opt::analysis::Float float_type(width); |
| 254 |
auto float_type_id = GetIRContext()->get_type_mgr()->GetId(&float_type); |
| 255 |
if (float_type_id) { |
| 256 |
new_result_id = float_type_id; |
| 257 |
} else { |
| 258 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 259 |
ApplyTransformation(TransformationAddTypeFloat(new_result_id, width)); |
| 260 |
} |
| 261 |
} break; |
| 262 |
case SpvOpTypeVector: { |
| 263 |
// It is not legal to have two Vector type declarations with identical |
| 264 |
// element types and element counts, so check whether an existing |
| 265 |
// identical Vector type is present and use its id if so. Otherwise add |
| 266 |
// a declaration of the Vector type used by the donor, with a fresh id. |
| 267 |
|
| 268 |
// When considering the vector's component type id, we look up the id |
| 269 |
// use in the donor to find the id to which this has been remapped. |
| 270 |
uint32_t component_type_id = original_id_to_donated_id->at( |
| 271 |
type_or_value.GetSingleWordInOperand(0)); |
| 272 |
auto component_type = |
| 273 |
GetIRContext()->get_type_mgr()->GetType(component_type_id); |
| 274 |
assert(component_type && "The base type should be registered."); |
| 275 |
auto component_count = type_or_value.GetSingleWordInOperand(1); |
| 276 |
opt::analysis::Vector vector_type(component_type, component_count); |
| 277 |
auto vector_type_id = GetIRContext()->get_type_mgr()->GetId(&vector_type); |
| 278 |
if (vector_type_id) { |
| 279 |
new_result_id = vector_type_id; |
| 280 |
} else { |
| 281 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 282 |
ApplyTransformation(TransformationAddTypeVector( |
| 283 |
new_result_id, component_type_id, component_count)); |
| 284 |
} |
| 285 |
} break; |
| 286 |
case SpvOpTypeMatrix: { |
| 287 |
// Similar to SpvOpTypeVector. |
| 288 |
uint32_t column_type_id = original_id_to_donated_id->at( |
| 289 |
type_or_value.GetSingleWordInOperand(0)); |
| 290 |
auto column_type = |
| 291 |
GetIRContext()->get_type_mgr()->GetType(column_type_id); |
| 292 |
assert(column_type && column_type->AsVector() && |
| 293 |
"The column type should be a registered vector type."); |
| 294 |
auto column_count = type_or_value.GetSingleWordInOperand(1); |
| 295 |
opt::analysis::Matrix matrix_type(column_type, column_count); |
| 296 |
auto matrix_type_id = GetIRContext()->get_type_mgr()->GetId(&matrix_type); |
| 297 |
if (matrix_type_id) { |
| 298 |
new_result_id = matrix_type_id; |
| 299 |
} else { |
| 300 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 301 |
ApplyTransformation(TransformationAddTypeMatrix( |
| 302 |
new_result_id, column_type_id, column_count)); |
| 303 |
} |
| 304 |
|
| 305 |
} break; |
| 306 |
case SpvOpTypeArray: { |
| 307 |
// It is OK to have multiple structurally identical array types, so |
| 308 |
// we go ahead and add a remapped version of the type declared by the |
| 309 |
// donor. |
| 310 |
uint32_t component_type_id = type_or_value.GetSingleWordInOperand(0); |
| 311 |
if (!original_id_to_donated_id->count(component_type_id)) { |
| 312 |
// We did not donate the component type of this array type, so we |
| 313 |
// cannot donate the array type. |
| 314 |
return; |
| 315 |
} |
| 316 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 317 |
ApplyTransformation(TransformationAddTypeArray( |
| 318 |
new_result_id, original_id_to_donated_id->at(component_type_id), |
| 319 |
original_id_to_donated_id->at( |
| 320 |
type_or_value.GetSingleWordInOperand(1)))); |
| 321 |
} break; |
| 322 |
case SpvOpTypeRuntimeArray: { |
| 323 |
// A runtime array is allowed as the final member of an SSBO. During |
| 324 |
// donation we turn runtime arrays into fixed-size arrays. For dead |
| 325 |
// code donations this is OK because the array is never indexed into at |
| 326 |
// runtime, so it does not matter what its size is. For live-safe code, |
| 327 |
// all accesses are made in-bounds, so this is also OK. |
| 328 |
// |
| 329 |
// The special OpArrayLength instruction, which works on runtime arrays, |
| 330 |
// is rewritten to yield the fixed length that is used for the array. |
| 331 |
|
| 332 |
uint32_t component_type_id = type_or_value.GetSingleWordInOperand(0); |
| 333 |
if (!original_id_to_donated_id->count(component_type_id)) { |
| 334 |
// We did not donate the component type of this runtime array type, so |
| 335 |
// we cannot donate it as a fixed-size array. |
| 336 |
return; |
| 337 |
} |
| 338 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 339 |
ApplyTransformation(TransformationAddTypeArray( |
| 340 |
new_result_id, original_id_to_donated_id->at(component_type_id), |
| 341 |
FindOrCreateIntegerConstant( |
| 342 |
{GetFuzzerContext()->GetRandomSizeForNewArray()}, 32, false, |
| 343 |
false))); |
| 344 |
} break; |
| 345 |
case SpvOpTypeStruct: { |
| 346 |
// Similar to SpvOpTypeArray. |
| 347 |
std::vector<uint32_t> member_type_ids; |
| 348 |
for (uint32_t i = 0; i < type_or_value.NumInOperands(); i++) { |
| 349 |
auto component_type_id = type_or_value.GetSingleWordInOperand(i); |
| 350 |
if (!original_id_to_donated_id->count(component_type_id)) { |
| 351 |
// We did not donate every member type for this struct type, so we |
| 352 |
// cannot donate the struct type. |
| 353 |
return; |
| 354 |
} |
| 355 |
member_type_ids.push_back( |
| 356 |
original_id_to_donated_id->at(component_type_id)); |
| 357 |
} |
| 358 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 359 |
ApplyTransformation( |
| 360 |
TransformationAddTypeStruct(new_result_id, member_type_ids)); |
| 361 |
} break; |
| 362 |
case SpvOpTypePointer: { |
| 363 |
// Similar to SpvOpTypeArray. |
| 364 |
uint32_t pointee_type_id = type_or_value.GetSingleWordInOperand(1); |
| 365 |
if (!original_id_to_donated_id->count(pointee_type_id)) { |
| 366 |
// We did not donate the pointee type for this pointer type, so we |
| 367 |
// cannot donate the pointer type. |
| 368 |
return; |
| 369 |
} |
| 370 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 371 |
ApplyTransformation(TransformationAddTypePointer( |
| 372 |
new_result_id, |
| 373 |
AdaptStorageClass(static_cast<SpvStorageClass>( |
| 374 |
type_or_value.GetSingleWordInOperand(0))), |
| 375 |
original_id_to_donated_id->at(pointee_type_id))); |
| 376 |
} break; |
| 377 |
case SpvOpTypeFunction: { |
| 378 |
// It is not OK to have multiple function types that use identical ids |
| 379 |
// for their return and parameter types. We thus go through all |
| 380 |
// existing function types to look for a match. We do not use the |
| 381 |
// type manager here because we want to regard two function types that |
| 382 |
// are structurally identical but that differ with respect to the |
| 383 |
// actual ids used for pointer types as different. |
| 384 |
// |
| 385 |
// Example: |
| 386 |
// |
| 387 |
// %1 = OpTypeVoid |
| 388 |
// %2 = OpTypeInt 32 0 |
| 389 |
// %3 = OpTypePointer Function %2 |
| 390 |
// %4 = OpTypePointer Function %2 |
| 391 |
// %5 = OpTypeFunction %1 %3 |
| 392 |
// %6 = OpTypeFunction %1 %4 |
| 393 |
// |
| 394 |
// We regard %5 and %6 as distinct function types here, even though |
| 395 |
// they both have the form "uint32* -> void" |
| 396 |
|
| 397 |
std::vector<uint32_t> return_and_parameter_types; |
| 398 |
for (uint32_t i = 0; i < type_or_value.NumInOperands(); i++) { |
| 399 |
uint32_t return_or_parameter_type = |
| 400 |
type_or_value.GetSingleWordInOperand(i); |
| 401 |
if (!original_id_to_donated_id->count(return_or_parameter_type)) { |
| 402 |
// We did not donate every return/parameter type for this function |
| 403 |
// type, so we cannot donate the function type. |
| 404 |
return; |
| 405 |
} |
| 406 |
return_and_parameter_types.push_back( |
| 407 |
original_id_to_donated_id->at(return_or_parameter_type)); |
| 408 |
} |
| 409 |
uint32_t existing_function_id = fuzzerutil::FindFunctionType( |
| 410 |
GetIRContext(), return_and_parameter_types); |
| 411 |
if (existing_function_id) { |
| 412 |
new_result_id = existing_function_id; |
| 413 |
} else { |
| 414 |
// No match was found, so add a remapped version of the function type |
| 415 |
// to the module, with a fresh id. |
| 416 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 417 |
std::vector<uint32_t> argument_type_ids; |
| 418 |
for (uint32_t i = 1; i < type_or_value.NumInOperands(); i++) { |
| 419 |
argument_type_ids.push_back(original_id_to_donated_id->at( |
| 420 |
type_or_value.GetSingleWordInOperand(i))); |
| 421 |
} |
| 422 |
ApplyTransformation(TransformationAddTypeFunction( |
| 423 |
new_result_id, |
| 424 |
original_id_to_donated_id->at( |
| 425 |
type_or_value.GetSingleWordInOperand(0)), |
| 426 |
argument_type_ids)); |
| 427 |
} |
| 428 |
} break; |
| 429 |
case SpvOpSpecConstantOp: { |
| 430 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 431 |
auto type_id = original_id_to_donated_id->at(type_or_value.type_id()); |
| 432 |
auto opcode = static_cast<SpvOp>(type_or_value.GetSingleWordInOperand(0)); |
| 433 |
|
| 434 |
// Make sure we take into account |original_id_to_donated_id| when |
| 435 |
// computing operands for OpSpecConstantOp. |
| 436 |
opt::Instruction::OperandList operands; |
| 437 |
for (uint32_t i = 1; i < type_or_value.NumInOperands(); ++i) { |
| 438 |
const auto& operand = type_or_value.GetInOperand(i); |
| 439 |
auto data = |
| 440 |
operand.type == SPV_OPERAND_TYPE_ID |
| 441 |
? opt::Operand::OperandData{original_id_to_donated_id->at( |
| 442 |
operand.words[0])} |
| 443 |
: operand.words; |
| 444 |
|
| 445 |
operands.push_back({operand.type, std::move(data)}); |
| 446 |
} |
| 447 |
|
| 448 |
ApplyTransformation(TransformationAddSpecConstantOp( |
| 449 |
new_result_id, type_id, opcode, std::move(operands))); |
| 450 |
} break; |
| 451 |
case SpvOpSpecConstantTrue: |
| 452 |
case SpvOpSpecConstantFalse: |
| 453 |
case SpvOpConstantTrue: |
| 454 |
case SpvOpConstantFalse: { |
| 455 |
// It is OK to have duplicate definitions of True and False, so add |
| 456 |
// these to the module, using a remapped Bool type. |
| 457 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 458 |
auto value = type_or_value.opcode() == SpvOpConstantTrue || |
| 459 |
type_or_value.opcode() == SpvOpSpecConstantTrue; |
| 460 |
ApplyTransformation( |
| 461 |
TransformationAddConstantBoolean(new_result_id, value, false)); |
| 462 |
} break; |
| 463 |
case SpvOpSpecConstant: |
| 464 |
case SpvOpConstant: { |
| 465 |
// It is OK to have duplicate constant definitions, so add this to the |
| 466 |
// module using a remapped result type. |
| 467 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 468 |
std::vector<uint32_t> data_words; |
| 469 |
type_or_value.ForEachInOperand([&data_words](const uint32_t* in_operand) { |
| 470 |
data_words.push_back(*in_operand); |
| 471 |
}); |
| 472 |
ApplyTransformation(TransformationAddConstantScalar( |
| 473 |
new_result_id, original_id_to_donated_id->at(type_or_value.type_id()), |
| 474 |
data_words, false)); |
| 475 |
} break; |
| 476 |
case SpvOpSpecConstantComposite: |
| 477 |
case SpvOpConstantComposite: { |
| 478 |
assert(original_id_to_donated_id->count(type_or_value.type_id()) && |
| 479 |
"Composite types for which it is possible to create a constant " |
| 480 |
"should have been donated."); |
| 481 |
|
| 482 |
// It is OK to have duplicate constant composite definitions, so add |
| 483 |
// this to the module using remapped versions of all consituent ids and |
| 484 |
// the result type. |
| 485 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 486 |
std::vector<uint32_t> constituent_ids; |
| 487 |
type_or_value.ForEachInId([&constituent_ids, &original_id_to_donated_id]( |
| 488 |
const uint32_t* constituent_id) { |
| 489 |
assert(original_id_to_donated_id->count(*constituent_id) && |
| 490 |
"The constants used to construct this composite should " |
| 491 |
"have been donated."); |
| 492 |
constituent_ids.push_back( |
| 493 |
original_id_to_donated_id->at(*constituent_id)); |
| 494 |
}); |
| 495 |
ApplyTransformation(TransformationAddConstantComposite( |
| 496 |
new_result_id, original_id_to_donated_id->at(type_or_value.type_id()), |
| 497 |
constituent_ids, false)); |
| 498 |
} break; |
| 499 |
case SpvOpConstantNull: { |
| 500 |
if (!original_id_to_donated_id->count(type_or_value.type_id())) { |
| 501 |
// We did not donate the type associated with this null constant, so |
| 502 |
// we cannot donate the null constant. |
| 503 |
return; |
| 504 |
} |
| 505 |
|
| 506 |
// It is fine to have multiple OpConstantNull instructions of the same |
| 507 |
// type, so we just add this to the recipient module. |
| 508 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 509 |
ApplyTransformation(TransformationAddConstantNull( |
| 510 |
new_result_id, |
| 511 |
original_id_to_donated_id->at(type_or_value.type_id()))); |
| 512 |
} break; |
| 513 |
case SpvOpVariable: { |
| 514 |
if (!original_id_to_donated_id->count(type_or_value.type_id())) { |
| 515 |
// We did not donate the pointer type associated with this variable, |
| 516 |
// so we cannot donate the variable. |
| 517 |
return; |
| 518 |
} |
| 519 |
|
| 520 |
// This is a global variable that could have one of various storage |
| 521 |
// classes. However, we change all global variable pointer storage |
| 522 |
// classes (such as Uniform, Input and Output) to private when donating |
| 523 |
// pointer types, with the exception of the Workgroup storage class. |
| 524 |
// |
| 525 |
// Thus this variable's pointer type is guaranteed to have storage class |
| 526 |
// Private or Workgroup. |
| 527 |
// |
| 528 |
// We add a global variable with either Private or Workgroup storage |
| 529 |
// class, using remapped versions of the result type and initializer ids |
| 530 |
// for the global variable in the donor. |
| 531 |
// |
| 532 |
// We regard the added variable as having an irrelevant value. This |
| 533 |
// means that future passes can add stores to the variable in any |
| 534 |
// way they wish, and pass them as pointer parameters to functions |
| 535 |
// without worrying about whether their data might get modified. |
| 536 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 537 |
uint32_t remapped_pointer_type = |
| 538 |
original_id_to_donated_id->at(type_or_value.type_id()); |
| 539 |
uint32_t initializer_id; |
| 540 |
SpvStorageClass storage_class = |
| 541 |
static_cast<SpvStorageClass>(type_or_value.GetSingleWordInOperand( |
| 542 |
0)) == SpvStorageClassWorkgroup |
| 543 |
? SpvStorageClassWorkgroup |
| 544 |
: SpvStorageClassPrivate; |
| 545 |
if (type_or_value.NumInOperands() == 1) { |
| 546 |
// The variable did not have an initializer. Initialize it to zero |
| 547 |
// if it has Private storage class (to limit problems associated with |
| 548 |
// uninitialized data), and leave it uninitialized if it has Workgroup |
| 549 |
// storage class (as Workgroup variables cannot have initializers). |
| 550 |
|
| 551 |
// TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3275): we |
| 552 |
// could initialize Workgroup variables at the start of an entry |
| 553 |
// point, and should do so if their uninitialized nature proves |
| 554 |
// problematic. |
| 555 |
initializer_id = storage_class == SpvStorageClassWorkgroup |
| 556 |
? 0 |
| 557 |
: FindOrCreateZeroConstant( |
| 558 |
fuzzerutil::GetPointeeTypeIdFromPointerType( |
| 559 |
GetIRContext(), remapped_pointer_type), |
| 560 |
false); |
| 561 |
} else { |
| 562 |
// The variable already had an initializer; use its remapped id. |
| 563 |
initializer_id = original_id_to_donated_id->at( |
| 564 |
type_or_value.GetSingleWordInOperand(1)); |
| 565 |
} |
| 566 |
ApplyTransformation( |
| 567 |
TransformationAddGlobalVariable(new_result_id, remapped_pointer_type, |
| 568 |
storage_class, initializer_id, true)); |
| 569 |
} break; |
| 570 |
case SpvOpUndef: { |
| 571 |
if (!original_id_to_donated_id->count(type_or_value.type_id())) { |
| 572 |
// We did not donate the type associated with this undef, so we cannot |
| 573 |
// donate the undef. |
| 574 |
return; |
| 575 |
} |
| 576 |
|
| 577 |
// It is fine to have multiple Undef instructions of the same type, so |
| 578 |
// we just add this to the recipient module. |
| 579 |
new_result_id = GetFuzzerContext()->GetFreshId(); |
| 580 |
ApplyTransformation(TransformationAddGlobalUndef( |
| 581 |
new_result_id, |
| 582 |
original_id_to_donated_id->at(type_or_value.type_id()))); |
| 583 |
} break; |
| 584 |
default: { |
| 585 |
assert(0 && "Unknown type/value."); |
| 586 |
new_result_id = 0; |
| 587 |
} break; |
| 588 |
} |
| 589 |
|
| 590 |
// Update the id mapping to associate the instruction's result id with its |
| 591 |
// corresponding id in the recipient. |
| 592 |
original_id_to_donated_id->insert({type_or_value.result_id(), new_result_id}); |
| 593 |
} |
| 594 |
|
| 595 |
void FuzzerPassDonateModules::HandleFunctions( |
| 596 |
opt::IRContext* donor_ir_context, |
| 597 |
std::map<uint32_t, uint32_t>* original_id_to_donated_id, |
| 598 |
bool make_livesafe) { |
| 599 |
// Get the ids of functions in the donor module, topologically sorted |
| 600 |
// according to the donor's call graph. |
| 601 |
auto topological_order = |
| 602 |
CallGraph(donor_ir_context).GetFunctionsInTopologicalOrder(); |
| 603 |
|
| 604 |
// Donate the functions in reverse topological order. This ensures that a |
| 605 |
// function gets donated before any function that depends on it. This allows |
| 606 |
// donation of the functions to be separated into a number of transformations, |
| 607 |
// each adding one function, such that every prefix of transformations leaves |
| 608 |
// the module valid. |
| 609 |
for (auto function_id = topological_order.rbegin(); |
| 610 |
function_id != topological_order.rend(); ++function_id) { |
| 611 |
// Find the function to be donated. |
| 612 |
opt::Function* function_to_donate = nullptr; |
| 613 |
for (auto& function : *donor_ir_context->module()) { |
| 614 |
if (function.result_id() == *function_id) { |
| 615 |
function_to_donate = &function; |
| 616 |
break; |
| 617 |
} |
| 618 |
} |
| 619 |
assert(function_to_donate && "Function to be donated was not found."); |
| 620 |
|
| 621 |
if (!original_id_to_donated_id->count( |
| 622 |
function_to_donate->DefInst().GetSingleWordInOperand(1))) { |
| 623 |
// We were not able to donate this function's type, so we cannot donate |
| 624 |
// the function. |
| 625 |
continue; |
| 626 |
} |
| 627 |
|
| 628 |
// We will collect up protobuf messages representing the donor function's |
| 629 |
// instructions here, and use them to create an AddFunction transformation. |
| 630 |
std::vector<protobufs::Instruction> donated_instructions; |
| 631 |
|
| 632 |
// This set tracks the ids of those instructions for which donation was |
| 633 |
// completely skipped: neither the instruction nor a substitute for it was |
| 634 |
// donated. |
| 635 |
std::set<uint32_t> skipped_instructions; |
| 636 |
|
| 637 |
// Consider every instruction of the donor function. |
| 638 |
function_to_donate->ForEachInst( |
| 639 |
[this, &donated_instructions, donor_ir_context, |
| 640 |
&original_id_to_donated_id, |
| 641 |
&skipped_instructions](const opt::Instruction* instruction) { |
| 642 |
if (instruction->opcode() == SpvOpArrayLength) { |
| 643 |
// We treat OpArrayLength specially. |
| 644 |
HandleOpArrayLength(*instruction, original_id_to_donated_id, |
| 645 |
&donated_instructions); |
| 646 |
} else if (!CanDonateInstruction(donor_ir_context, *instruction, |
| 647 |
*original_id_to_donated_id, |
| 648 |
skipped_instructions)) { |
| 649 |
// This is an instruction that we cannot directly donate. |
| 650 |
HandleDifficultInstruction(*instruction, original_id_to_donated_id, |
| 651 |
&donated_instructions, |
| 652 |
&skipped_instructions); |
| 653 |
} else { |
| 654 |
PrepareInstructionForDonation(*instruction, donor_ir_context, |
| 655 |
original_id_to_donated_id, |
| 656 |
&donated_instructions); |
| 657 |
} |
| 658 |
}); |
| 659 |
|
| 660 |
// If |make_livesafe| is true, try to add the function in a livesafe manner. |
| 661 |
// Otherwise (if |make_lifesafe| is false or an attempt to make the function |
| 662 |
// livesafe has failed), add the function in a non-livesafe manner. |
| 663 |
if (!make_livesafe || |
| 664 |
!MaybeAddLivesafeFunction(*function_to_donate, donor_ir_context, |
| 665 |
*original_id_to_donated_id, |
| 666 |
donated_instructions)) { |
| 667 |
ApplyTransformation(TransformationAddFunction(donated_instructions)); |
| 668 |
} |
| 669 |
} |
| 670 |
} |
| 671 |
|
| 672 |
bool FuzzerPassDonateModules::CanDonateInstruction( |
| 673 |
opt::IRContext* donor_ir_context, const opt::Instruction& instruction, |
| 674 |
const std::map<uint32_t, uint32_t>& original_id_to_donated_id, |
| 675 |
const std::set<uint32_t>& skipped_instructions) const { |
| 676 |
if (instruction.type_id() && |
| 677 |
!original_id_to_donated_id.count(instruction.type_id())) { |
| 678 |
// We could not donate the result type of this instruction, so we cannot |
| 679 |
// donate the instruction. |
| 680 |
return false; |
| 681 |
} |
| 682 |
|
| 683 |
// Now consider instructions we specifically want to skip because we do not |
| 684 |
// yet support them. |
| 685 |
switch (instruction.opcode()) { |
| 686 |
case SpvOpAtomicLoad: |
| 687 |
case SpvOpAtomicStore: |
| 688 |
case SpvOpAtomicExchange: |
| 689 |
case SpvOpAtomicCompareExchange: |
| 690 |
case SpvOpAtomicCompareExchangeWeak: |
| 691 |
case SpvOpAtomicIIncrement: |
| 692 |
case SpvOpAtomicIDecrement: |
| 693 |
case SpvOpAtomicIAdd: |
| 694 |
case SpvOpAtomicISub: |
| 695 |
case SpvOpAtomicSMin: |
| 696 |
case SpvOpAtomicUMin: |
| 697 |
case SpvOpAtomicSMax: |
| 698 |
case SpvOpAtomicUMax: |
| 699 |
case SpvOpAtomicAnd: |
| 700 |
case SpvOpAtomicOr: |
| 701 |
case SpvOpAtomicXor: |
| 702 |
// We conservatively ignore all atomic instructions at present. |
| 703 |
// TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3276): Consider |
| 704 |
// being less conservative here. |
| 705 |
case SpvOpImageSampleImplicitLod: |
| 706 |
case SpvOpImageSampleExplicitLod: |
| 707 |
case SpvOpImageSampleDrefImplicitLod: |
| 708 |
case SpvOpImageSampleDrefExplicitLod: |
| 709 |
case SpvOpImageSampleProjImplicitLod: |
| 710 |
case SpvOpImageSampleProjExplicitLod: |
| 711 |
case SpvOpImageSampleProjDrefImplicitLod: |
| 712 |
case SpvOpImageSampleProjDrefExplicitLod: |
| 713 |
case SpvOpImageFetch: |
| 714 |
case SpvOpImageGather: |
| 715 |
case SpvOpImageDrefGather: |
| 716 |
case SpvOpImageRead: |
| 717 |
case SpvOpImageWrite: |
| 718 |
case SpvOpImageSparseSampleImplicitLod: |
| 719 |
case SpvOpImageSparseSampleExplicitLod: |
| 720 |
case SpvOpImageSparseSampleDrefImplicitLod: |
| 721 |
case SpvOpImageSparseSampleDrefExplicitLod: |
| 722 |
case SpvOpImageSparseSampleProjImplicitLod: |
| 723 |
case SpvOpImageSparseSampleProjExplicitLod: |
| 724 |
case SpvOpImageSparseSampleProjDrefImplicitLod: |
| 725 |
case SpvOpImageSparseSampleProjDrefExplicitLod: |
| 726 |
case SpvOpImageSparseFetch: |
| 727 |
case SpvOpImageSparseGather: |
| 728 |
case SpvOpImageSparseDrefGather: |
| 729 |
case SpvOpImageSparseRead: |
| 730 |
case SpvOpImageSampleFootprintNV: |
| 731 |
case SpvOpImage: |
| 732 |
case SpvOpImageQueryFormat: |
| 733 |
case SpvOpImageQueryLevels: |
| 734 |
case SpvOpImageQueryLod: |
| 735 |
case SpvOpImageQueryOrder: |
| 736 |
case SpvOpImageQuerySamples: |
| 737 |
case SpvOpImageQuerySize: |
| 738 |
case SpvOpImageQuerySizeLod: |
| 739 |
case SpvOpSampledImage: |
| 740 |
// We ignore all instructions related to accessing images, since we do not |
| 741 |
// donate images. |
| 742 |
return false; |
| 743 |
case SpvOpLoad: |
| 744 |
switch (donor_ir_context->get_def_use_mgr() |
| 745 |
->GetDef(instruction.type_id()) |
| 746 |
->opcode()) { |
| 747 |
case SpvOpTypeImage: |
| 748 |
case SpvOpTypeSampledImage: |
| 749 |
case SpvOpTypeSampler: |
| 750 |
// Again, we ignore instructions that relate to accessing images. |
| 751 |
return false; |
| 752 |
default: |
| 753 |
break; |
| 754 |
} |
| 755 |
default: |
| 756 |
break; |
| 757 |
} |
| 758 |
|
| 759 |
// Examine each id input operand to the instruction. If it turns out that we |
| 760 |
// have skipped any of these operands then we cannot donate the instruction. |
| 761 |
bool result = true; |
| 762 |
instruction.WhileEachInId( |
| 763 |
[donor_ir_context, &original_id_to_donated_id, &result, |
| 764 |
&skipped_instructions](const uint32_t* in_id) -> bool { |
| 765 |
if (!original_id_to_donated_id.count(*in_id)) { |
| 766 |
// We do not have a mapped result id for this id operand. That either |
| 767 |
// means that it is a forward reference (which is OK), that we skipped |
| 768 |
// the instruction that generated it (which is not OK), or that it is |
| 769 |
// the id of a function or global value that we did not donate (which |
| 770 |
// is not OK). We check for the latter two cases. |
| 771 |
if (skipped_instructions.count(*in_id) || |
| 772 |
// A function or global value does not have an associated basic |
| 773 |
// block. |
| 774 |
!donor_ir_context->get_instr_block(*in_id)) { |
| 775 |
result = false; |
| 776 |
return false; |
| 777 |
} |
| 778 |
} |
| 779 |
return true; |
| 780 |
}); |
| 781 |
return result; |
| 782 |
} |
| 783 |
|
| 784 |
bool FuzzerPassDonateModules::IsBasicType( |
| 785 |
const opt::Instruction& instruction) const { |
| 786 |
switch (instruction.opcode()) { |
| 787 |
case SpvOpTypeArray: |
| 788 |
case SpvOpTypeBool: |
| 789 |
case SpvOpTypeFloat: |
| 790 |
case SpvOpTypeInt: |
| 791 |
case SpvOpTypeMatrix: |
| 792 |
case SpvOpTypeStruct: |
| 793 |
case SpvOpTypeVector: |
| 794 |
return true; |
| 795 |
default: |
| 796 |
return false; |
| 797 |
} |
| 798 |
} |
| 799 |
|
| 800 |
void FuzzerPassDonateModules::HandleOpArrayLength( |
| 801 |
const opt::Instruction& instruction, |
| 802 |
std::map<uint32_t, uint32_t>* original_id_to_donated_id, |
| 803 |
std::vector<protobufs::Instruction>* donated_instructions) const { |
| 804 |
assert(instruction.opcode() == SpvOpArrayLength && |
| 805 |
"Precondition: instruction must be OpArrayLength."); |
| 806 |
uint32_t donated_variable_id = |
| 807 |
original_id_to_donated_id->at(instruction.GetSingleWordInOperand(0)); |
| 808 |
auto donated_variable_instruction = |
| 809 |
GetIRContext()->get_def_use_mgr()->GetDef(donated_variable_id); |
| 810 |
auto pointer_to_struct_instruction = |
| 811 |
GetIRContext()->get_def_use_mgr()->GetDef( |
| 812 |
donated_variable_instruction->type_id()); |
| 813 |
assert(pointer_to_struct_instruction->opcode() == SpvOpTypePointer && |
| 814 |
"Type of variable must be pointer."); |
| 815 |
auto donated_struct_type_instruction = |
| 816 |
GetIRContext()->get_def_use_mgr()->GetDef( |
| 817 |
pointer_to_struct_instruction->GetSingleWordInOperand(1)); |
| 818 |
assert(donated_struct_type_instruction->opcode() == SpvOpTypeStruct && |
| 819 |
"Pointee type of pointer used by OpArrayLength must be struct."); |
| 820 |
assert(donated_struct_type_instruction->NumInOperands() == |
| 821 |
instruction.GetSingleWordInOperand(1) + 1 && |
| 822 |
"OpArrayLength must refer to the final member of the given " |
| 823 |
"struct."); |
| 824 |
uint32_t fixed_size_array_type_id = |
| 825 |
donated_struct_type_instruction->GetSingleWordInOperand( |
| 826 |
donated_struct_type_instruction->NumInOperands() - 1); |
| 827 |
auto fixed_size_array_type_instruction = |
| 828 |
GetIRContext()->get_def_use_mgr()->GetDef(fixed_size_array_type_id); |
| 829 |
assert(fixed_size_array_type_instruction->opcode() == SpvOpTypeArray && |
| 830 |
"The donated array type must be fixed-size."); |
| 831 |
auto array_size_id = |
| 832 |
fixed_size_array_type_instruction->GetSingleWordInOperand(1); |
| 833 |
|
| 834 |
if (instruction.result_id() && |
| 835 |
!original_id_to_donated_id->count(instruction.result_id())) { |
| 836 |
original_id_to_donated_id->insert( |
| 837 |
{instruction.result_id(), GetFuzzerContext()->GetFreshId()}); |
| 838 |
} |
| 839 |
|
| 840 |
donated_instructions->push_back(MakeInstructionMessage( |
| 841 |
SpvOpCopyObject, original_id_to_donated_id->at(instruction.type_id()), |
| 842 |
original_id_to_donated_id->at(instruction.result_id()), |
| 843 |
opt::Instruction::OperandList({{SPV_OPERAND_TYPE_ID, {array_size_id}}}))); |
| 844 |
} |
| 845 |
|
| 846 |
void FuzzerPassDonateModules::HandleDifficultInstruction( |
| 847 |
const opt::Instruction& instruction, |
| 848 |
std::map<uint32_t, uint32_t>* original_id_to_donated_id, |
| 849 |
std::vector<protobufs::Instruction>* donated_instructions, |
| 850 |
std::set<uint32_t>* skipped_instructions) { |
| 851 |
if (!instruction.result_id()) { |
| 852 |
// It does not generate a result id, so it can be ignored. |
| 853 |
return; |
| 854 |
} |
| 855 |
if (!original_id_to_donated_id->count(instruction.type_id())) { |
| 856 |
// We cannot handle this instruction's result type, so we need to skip it |
| 857 |
// all together. |
| 858 |
skipped_instructions->insert(instruction.result_id()); |
| 859 |
return; |
| 860 |
} |
| 861 |
|
| 862 |
// We now attempt to replace the instruction with an OpCopyObject. |
| 863 |
// TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3278): We could do |
| 864 |
// something more refined here - we could check which operands to the |
| 865 |
// instruction could not be donated and replace those operands with |
| 866 |
// references to other ids (such as constants), so that we still get an |
| 867 |
// instruction with the opcode and easy-to-handle operands of the donor |
| 868 |
// instruction. |
| 869 |
auto remapped_type_id = original_id_to_donated_id->at(instruction.type_id()); |
| 870 |
if (!IsBasicType( |
| 871 |
*GetIRContext()->get_def_use_mgr()->GetDef(remapped_type_id))) { |
| 872 |
// The instruction has a non-basic result type, so we cannot replace it with |
| 873 |
// an object copy of a constant. We thus skip it completely. |
| 874 |
// TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3279): We could |
| 875 |
// instead look for an available id of the right type and generate an |
| 876 |
// OpCopyObject of that id. |
| 877 |
skipped_instructions->insert(instruction.result_id()); |
| 878 |
return; |
| 879 |
} |
| 880 |
|
| 881 |
// We are going to add an OpCopyObject instruction. Add a mapping for the |
| 882 |
// result id of the original instruction if does not already exist (it may |
| 883 |
// exist in the case that it has been forward-referenced). |
| 884 |
if (!original_id_to_donated_id->count(instruction.result_id())) { |
| 885 |
original_id_to_donated_id->insert( |
| 886 |
{instruction.result_id(), GetFuzzerContext()->GetFreshId()}); |
| 887 |
} |
| 888 |
|
| 889 |
// We find or add a zero constant to the receiving module for the type in |
| 890 |
// question, and add an OpCopyObject instruction that copies this zero. |
| 891 |
// |
| 892 |
// We mark the constant as irrelevant so that we can replace it with a |
| 893 |
// more interesting value later. |
| 894 |
auto zero_constant = FindOrCreateZeroConstant(remapped_type_id, true); |
| 895 |
donated_instructions->push_back(MakeInstructionMessage( |
| 896 |
SpvOpCopyObject, remapped_type_id, |
| 897 |
original_id_to_donated_id->at(instruction.result_id()), |
| 898 |
opt::Instruction::OperandList({{SPV_OPERAND_TYPE_ID, {zero_constant}}}))); |
| 899 |
} |
| 900 |
|
| 901 |
void FuzzerPassDonateModules::PrepareInstructionForDonation( |
| 902 |
const opt::Instruction& instruction, opt::IRContext* donor_ir_context, |
| 903 |
std::map<uint32_t, uint32_t>* original_id_to_donated_id, |
| 904 |
std::vector<protobufs::Instruction>* donated_instructions) { |
| 905 |
// Get the instruction's input operands into donation-ready form, |
| 906 |
// remapping any id uses in the process. |
| 907 |
opt::Instruction::OperandList input_operands; |
| 908 |
|
| 909 |
// Consider each input operand in turn. |
| 910 |
for (uint32_t in_operand_index = 0; |
| 911 |
in_operand_index < instruction.NumInOperands(); in_operand_index++) { |
| 912 |
std::vector<uint32_t> operand_data; |
| 913 |
const opt::Operand& in_operand = instruction.GetInOperand(in_operand_index); |
| 914 |
// Check whether this operand is an id. |
| 915 |
if (spvIsIdType(in_operand.type)) { |
| 916 |
// This is an id operand - it consists of a single word of data, |
| 917 |
// which needs to be remapped so that it is replaced with the |
| 918 |
// donated form of the id. |
| 919 |
auto operand_id = in_operand.words[0]; |
| 920 |
if (!original_id_to_donated_id->count(operand_id)) { |
| 921 |
// This is a forward reference. We will choose a corresponding |
| 922 |
// donor id for the referenced id and update the mapping to |
| 923 |
// reflect it. |
| 924 |
|
| 925 |
// Keep release compilers happy because |donor_ir_context| is only used |
| 926 |
// in this assertion. |
| 927 |
(void)(donor_ir_context); |
| 928 |
assert((donor_ir_context->get_def_use_mgr() |
| 929 |
->GetDef(operand_id) |
| 930 |
->opcode() == SpvOpLabel || |
| 931 |
instruction.opcode() == SpvOpPhi) && |
| 932 |
"Unsupported forward reference."); |
| 933 |
original_id_to_donated_id->insert( |
| 934 |
{operand_id, GetFuzzerContext()->GetFreshId()}); |
| 935 |
} |
| 936 |
operand_data.push_back(original_id_to_donated_id->at(operand_id)); |
| 937 |
} else { |
| 938 |
// For non-id operands, we just add each of the data words. |
| 939 |
for (auto word : in_operand.words) { |
| 940 |
operand_data.push_back(word); |
| 941 |
} |
| 942 |
} |
| 943 |
input_operands.push_back({in_operand.type, operand_data}); |
| 944 |
} |
| 945 |
|
| 946 |
if (instruction.opcode() == SpvOpVariable && |
| 947 |
instruction.NumInOperands() == 1) { |
| 948 |
// This is an uninitialized local variable. Initialize it to zero. |
| 949 |
input_operands.push_back( |
| 950 |
{SPV_OPERAND_TYPE_ID, |
| 951 |
{FindOrCreateZeroConstant( |
| 952 |
fuzzerutil::GetPointeeTypeIdFromPointerType( |
| 953 |
GetIRContext(), |
| 954 |
original_id_to_donated_id->at(instruction.type_id())), |
| 955 |
false)}}); |
| 956 |
} |
| 957 |
|
| 958 |
if (instruction.result_id() && |
| 959 |
!original_id_to_donated_id->count(instruction.result_id())) { |
| 960 |
original_id_to_donated_id->insert( |
| 961 |
{instruction.result_id(), GetFuzzerContext()->GetFreshId()}); |
| 962 |
} |
| 963 |
|
| 964 |
// Remap the result type and result id (if present) of the |
| 965 |
// instruction, and turn it into a protobuf message. |
| 966 |
donated_instructions->push_back(MakeInstructionMessage( |
| 967 |
instruction.opcode(), |
| 968 |
instruction.type_id() |
| 969 |
? original_id_to_donated_id->at(instruction.type_id()) |
| 970 |
: 0, |
| 971 |
instruction.result_id() |
| 972 |
? original_id_to_donated_id->at(instruction.result_id()) |
| 973 |
: 0, |
| 974 |
input_operands)); |
| 975 |
} |
| 976 |
|
| 977 |
bool FuzzerPassDonateModules::CreateLoopLimiterInfo( |
| 978 |
opt::IRContext* donor_ir_context, const opt::BasicBlock& loop_header, |
| 979 |
const std::map<uint32_t, uint32_t>& original_id_to_donated_id, |
| 980 |
protobufs::LoopLimiterInfo* out) { |
| 981 |
assert(loop_header.IsLoopHeader() && "|loop_header| is not a loop header"); |
| 982 |
|
| 983 |
// Grab the loop header's id, mapped to its donated value. |
| 984 |
out->set_loop_header_id(original_id_to_donated_id.at(loop_header.id())); |
| 985 |
|
| 986 |
// Get fresh ids that will be used to load the loop limiter, increment |
| 987 |
// it, compare it with the loop limit, and an id for a new block that |
| 988 |
// will contain the loop's original terminator. |
| 989 |
out->set_load_id(GetFuzzerContext()->GetFreshId()); |
| 990 |
out->set_increment_id(GetFuzzerContext()->GetFreshId()); |
| 991 |
out->set_compare_id(GetFuzzerContext()->GetFreshId()); |
| 992 |
out->set_logical_op_id(GetFuzzerContext()->GetFreshId()); |
| 993 |
|
| 994 |
// We are creating a branch from the back-edge block to the merge block. Thus, |
| 995 |
// if merge block has any OpPhi instructions, we might need to adjust |
| 996 |
// them. |
| 997 |
|
| 998 |
// Note that the loop might have an unreachable back-edge block. This means |
| 999 |
// that the loop can't iterate, so we don't need to adjust anything. |
| 1000 |
const auto back_edge_block_id = TransformationAddFunction::GetBackEdgeBlockId( |
| 1001 |
donor_ir_context, loop_header.id()); |
| 1002 |
if (!back_edge_block_id) { |
| 1003 |
return true; |
| 1004 |
} |
| 1005 |
|
| 1006 |
auto* back_edge_block = donor_ir_context->cfg()->block(back_edge_block_id); |
| 1007 |
assert(back_edge_block && "|back_edge_block_id| is invalid"); |
| 1008 |
|
| 1009 |
const auto* merge_block = |
| 1010 |
donor_ir_context->cfg()->block(loop_header.MergeBlockId()); |
| 1011 |
assert(merge_block && "Loop header has invalid merge block id"); |
| 1012 |
|
| 1013 |
// We don't need to adjust anything if there is already a branch from |
| 1014 |
// the back-edge block to the merge block. |
| 1015 |
if (back_edge_block->IsSuccessor(merge_block)) { |
| 1016 |
return true; |
| 1017 |
} |
| 1018 |
|
| 1019 |
// Adjust OpPhi instructions in the |merge_block|. |
| 1020 |
for (const auto& inst : *merge_block) { |
| 1021 |
if (inst.opcode() != SpvOpPhi) { |
| 1022 |
break; |
| 1023 |
} |
| 1024 |
|
| 1025 |
// There is no simple way to ensure that a chosen operand for the OpPhi |
| 1026 |
// instruction will never cause any problems (e.g. if we choose an |
| 1027 |
// integer id, it might have a zero value when we branch from the back |
| 1028 |
// edge block. This might cause a division by 0 later in the function.). |
| 1029 |
// Thus, we ignore possible problems and proceed as follows: |
| 1030 |
// - if any of the existing OpPhi operands dominates the back-edge |
| 1031 |
// block - use it |
| 1032 |
// - if OpPhi has a basic type (see IsBasicType method) - create |
| 1033 |
// a zero constant |
| 1034 |
// - otherwise, we can't add a livesafe function. |
| 1035 |
uint32_t suitable_operand_id = 0; |
| 1036 |
for (uint32_t i = 0; i < inst.NumInOperands(); i += 2) { |
| 1037 |
auto dependency_inst_id = inst.GetSingleWordInOperand(i); |
| 1038 |
|
| 1039 |
if (fuzzerutil::IdIsAvailableBeforeInstruction( |
| 1040 |
donor_ir_context, back_edge_block->terminator(), |
| 1041 |
dependency_inst_id)) { |
| 1042 |
suitable_operand_id = original_id_to_donated_id.at(dependency_inst_id); |
| 1043 |
break; |
| 1044 |
} |
| 1045 |
} |
| 1046 |
|
| 1047 |
if (suitable_operand_id == 0 && |
| 1048 |
IsBasicType( |
| 1049 |
*donor_ir_context->get_def_use_mgr()->GetDef(inst.type_id()))) { |
| 1050 |
// We mark this constant as irrelevant so that we can replace it |
| 1051 |
// with more interesting value later. |
| 1052 |
suitable_operand_id = FindOrCreateZeroConstant( |
| 1053 |
original_id_to_donated_id.at(inst.type_id()), true); |
| 1054 |
} |
| 1055 |
|
| 1056 |
if (suitable_operand_id == 0) { |
| 1057 |
return false; |
| 1058 |
} |
| 1059 |
|
| 1060 |
out->add_phi_id(suitable_operand_id); |
| 1061 |
} |
| 1062 |
|
| 1063 |
return true; |
| 1064 |
} |
| 1065 |
|
| 1066 |
bool FuzzerPassDonateModules::MaybeAddLivesafeFunction( |
| 1067 |
const opt::Function& function_to_donate, opt::IRContext* donor_ir_context, |
| 1068 |
const std::map<uint32_t, uint32_t>& original_id_to_donated_id, |
| 1069 |
const std::vector<protobufs::Instruction>& donated_instructions) { |
| 1070 |
// Various types and constants must be in place for a function to be made |
| 1071 |
// live-safe. Add them if not already present. |
| 1072 |
FindOrCreateBoolType(); // Needed for comparisons |
| 1073 |
FindOrCreatePointerToIntegerType( |
| 1074 |
32, false, SpvStorageClassFunction); // Needed for adding loop limiters |
| 1075 |
FindOrCreateIntegerConstant({0}, 32, false, |
| 1076 |
false); // Needed for initializing loop limiters |
| 1077 |
FindOrCreateIntegerConstant({1}, 32, false, |
| 1078 |
false); // Needed for incrementing loop limiters |
| 1079 |
|
| 1080 |
// Get a fresh id for the variable that will be used as a loop limiter. |
| 1081 |
const uint32_t loop_limiter_variable_id = GetFuzzerContext()->GetFreshId(); |
| 1082 |
// Choose a random loop limit, and add the required constant to the |
| 1083 |
// module if not already there. |
| 1084 |
const uint32_t loop_limit = FindOrCreateIntegerConstant( |
| 1085 |
{GetFuzzerContext()->GetRandomLoopLimit()}, 32, false, false); |
| 1086 |
|
| 1087 |
// Consider every loop header in the function to donate, and create a |
| 1088 |
// structure capturing the ids to be used for manipulating the loop |
| 1089 |
// limiter each time the loop is iterated. |
| 1090 |
std::vector<protobufs::LoopLimiterInfo> loop_limiters; |
| 1091 |
for (auto& block : function_to_donate) { |
| 1092 |
if (block.IsLoopHeader()) { |
| 1093 |
protobufs::LoopLimiterInfo loop_limiter; |
| 1094 |
|
| 1095 |
if (!CreateLoopLimiterInfo(donor_ir_context, block, |
| 1096 |
original_id_to_donated_id, &loop_limiter)) { |
| 1097 |
return false; |
| 1098 |
} |
| 1099 |
|
| 1100 |
loop_limiters.emplace_back(std::move(loop_limiter)); |
| 1101 |
} |
| 1102 |
} |
| 1103 |
|
| 1104 |
// Consider every access chain in the function to donate, and create a |
| 1105 |
// structure containing the ids necessary to clamp the access chain |
| 1106 |
// indices to be in-bounds. |
| 1107 |
std::vector<protobufs::AccessChainClampingInfo> access_chain_clamping_info; |
| 1108 |
for (auto& block : function_to_donate) { |
| 1109 |
for (auto& inst : block) { |
| 1110 |
switch (inst.opcode()) { |
| 1111 |
case SpvOpAccessChain: |
| 1112 |
case SpvOpInBoundsAccessChain: { |
| 1113 |
protobufs::AccessChainClampingInfo clamping_info; |
| 1114 |
clamping_info.set_access_chain_id( |
| 1115 |
original_id_to_donated_id.at(inst.result_id())); |
| 1116 |
|
| 1117 |
auto base_object = donor_ir_context->get_def_use_mgr()->GetDef( |
| 1118 |
inst.GetSingleWordInOperand(0)); |
| 1119 |
assert(base_object && "The base object must exist."); |
| 1120 |
auto pointer_type = donor_ir_context->get_def_use_mgr()->GetDef( |
| 1121 |
base_object->type_id()); |
| 1122 |
assert(pointer_type && pointer_type->opcode() == SpvOpTypePointer && |
| 1123 |
"The base object must have pointer type."); |
| 1124 |
|
| 1125 |
auto should_be_composite_type = |
| 1126 |
donor_ir_context->get_def_use_mgr()->GetDef( |
| 1127 |
pointer_type->GetSingleWordInOperand(1)); |
| 1128 |
|
| 1129 |
// Walk the access chain, creating fresh ids to facilitate |
| 1130 |
// clamping each index. For simplicity we do this for every |
| 1131 |
// index, even though constant indices will not end up being |
| 1132 |
// clamped. |
| 1133 |
for (uint32_t index = 1; index < inst.NumInOperands(); index++) { |
| 1134 |
auto compare_and_select_ids = |
| 1135 |
clamping_info.add_compare_and_select_ids(); |
| 1136 |
compare_and_select_ids->set_first(GetFuzzerContext()->GetFreshId()); |
| 1137 |
compare_and_select_ids->set_second( |
| 1138 |
GetFuzzerContext()->GetFreshId()); |
| 1139 |
|
| 1140 |
// Get the bound for the component being indexed into. |
| 1141 |
uint32_t bound; |
| 1142 |
if (should_be_composite_type->opcode() == SpvOpTypeRuntimeArray) { |
| 1143 |
// The donor is indexing into a runtime array. We do not |
| 1144 |
// donate runtime arrays. Instead, we donate a corresponding |
| 1145 |
// fixed-size array for every runtime array. We should thus |
| 1146 |
// find that donor composite type's result id maps to a fixed- |
| 1147 |
// size array. |
| 1148 |
auto fixed_size_array_type = |
| 1149 |
GetIRContext()->get_def_use_mgr()->GetDef( |
| 1150 |
original_id_to_donated_id.at( |
| 1151 |
should_be_composite_type->result_id())); |
| 1152 |
assert(fixed_size_array_type->opcode() == SpvOpTypeArray && |
| 1153 |
"A runtime array type in the donor should have been " |
| 1154 |
"replaced by a fixed-sized array in the recipient."); |
| 1155 |
// The size of this fixed-size array is a suitable bound. |
| 1156 |
bound = fuzzerutil::GetBoundForCompositeIndex( |
| 1157 |
*fixed_size_array_type, GetIRContext()); |
| 1158 |
} else { |
| 1159 |
bound = fuzzerutil::GetBoundForCompositeIndex( |
| 1160 |
*should_be_composite_type, donor_ir_context); |
| 1161 |
} |
| 1162 |
const uint32_t index_id = inst.GetSingleWordInOperand(index); |
| 1163 |
auto index_inst = |
| 1164 |
donor_ir_context->get_def_use_mgr()->GetDef(index_id); |
| 1165 |
auto index_type_inst = donor_ir_context->get_def_use_mgr()->GetDef( |
| 1166 |
index_inst->type_id()); |
| 1167 |
assert(index_type_inst->opcode() == SpvOpTypeInt); |
| 1168 |
opt::analysis::Integer* index_int_type = |
| 1169 |
donor_ir_context->get_type_mgr() |
| 1170 |
->GetType(index_type_inst->result_id()) |
| 1171 |
->AsInteger(); |
| 1172 |
if (index_inst->opcode() != SpvOpConstant) { |
| 1173 |
// We will have to clamp this index, so we need a constant |
| 1174 |
// whose value is one less than the bound, to compare |
| 1175 |
// against and to use as the clamped value. |
| 1176 |
FindOrCreateIntegerConstant({bound - 1}, 32, |
| 1177 |
index_int_type->IsSigned(), false); |
| 1178 |
} |
| 1179 |
should_be_composite_type = |
| 1180 |
TransformationAddFunction::FollowCompositeIndex( |
| 1181 |
donor_ir_context, *should_be_composite_type, index_id); |
| 1182 |
} |
| 1183 |
access_chain_clamping_info.push_back(clamping_info); |
| 1184 |
break; |
| 1185 |
} |
| 1186 |
default: |
| 1187 |
break; |
| 1188 |
} |
| 1189 |
} |
| 1190 |
} |
| 1191 |
|
| 1192 |
// If |function_to_donate| has non-void return type and contains an |
| 1193 |
// OpKill/OpUnreachable instruction, then a value is needed in order to turn |
| 1194 |
// these into instructions of the form OpReturnValue %value_id. |
| 1195 |
uint32_t kill_unreachable_return_value_id = 0; |
| 1196 |
auto function_return_type_inst = |
| 1197 |
donor_ir_context->get_def_use_mgr()->GetDef(function_to_donate.type_id()); |
| 1198 |
if (function_return_type_inst->opcode() != SpvOpTypeVoid && |
| 1199 |
fuzzerutil::FunctionContainsOpKillOrUnreachable(function_to_donate)) { |
| 1200 |
kill_unreachable_return_value_id = FindOrCreateZeroConstant( |
| 1201 |
original_id_to_donated_id.at(function_return_type_inst->result_id()), |
| 1202 |
false); |
| 1203 |
} |
| 1204 |
|
| 1205 |
// Add the function in a livesafe manner. |
| 1206 |
ApplyTransformation(TransformationAddFunction( |
| 1207 |
donated_instructions, loop_limiter_variable_id, loop_limit, loop_limiters, |
| 1208 |
kill_unreachable_return_value_id, access_chain_clamping_info)); |
| 1209 |
return true; |
| 1210 |
} |
| 1211 |
|
| 1212 |
} // namespace fuzz |
| 1213 |
} // namespace spvtools |