| 1 |
// Copyright (c) 2020 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_replace_irrelevant_ids.h" |
| 16 |
|
| 17 |
#include "source/fuzz/fuzzer_util.h" |
| 18 |
#include "source/fuzz/id_use_descriptor.h" |
| 19 |
#include "source/fuzz/transformation_replace_irrelevant_id.h" |
| 20 |
|
| 21 |
namespace spvtools { |
| 22 |
namespace fuzz { |
| 23 |
|
| 24 |
// A fuzzer pass that, for every use of an id that has been recorded as |
| 25 |
// irrelevant, randomly decides whether to replace it with another id of the |
| 26 |
// same type. |
| 27 |
FuzzerPassReplaceIrrelevantIds::FuzzerPassReplaceIrrelevantIds( |
| 28 |
opt::IRContext* ir_context, TransformationContext* transformation_context, |
| 29 |
FuzzerContext* fuzzer_context, |
| 30 |
protobufs::TransformationSequence* transformations) |
| 31 |
: FuzzerPass(ir_context, transformation_context, fuzzer_context, |
| 32 |
transformations) {} |
| 33 |
|
| 34 |
FuzzerPassReplaceIrrelevantIds::~FuzzerPassReplaceIrrelevantIds() = default; |
| 35 |
|
| 36 |
void FuzzerPassReplaceIrrelevantIds::Apply() { |
| 37 |
// Keep track of the irrelevant ids. This includes all the ids that are |
| 38 |
// irrelevant according to the fact manager and that are still present in the |
| 39 |
// module (some of them may have been removed by previously-run |
| 40 |
// transformations). |
| 41 |
std::vector<uint32_t> irrelevant_ids; |
| 42 |
|
| 43 |
// Keep a map from the type ids of irrelevant ids to all the ids with that |
| 44 |
// type. |
| 45 |
std::unordered_map<uint32_t, std::vector<uint32_t>> types_to_ids; |
| 46 |
|
| 47 |
// Find all the irrelevant ids that still exist in the module and all the |
| 48 |
// types for which irrelevant ids exist. |
| 49 |
for (auto id : |
| 50 |
GetTransformationContext()->GetFactManager()->GetIrrelevantIds()) { |
| 51 |
// Check that the id still exists in the module. |
| 52 |
auto declaration = GetIRContext()->get_def_use_mgr()->GetDef(id); |
| 53 |
if (!declaration) { |
| 54 |
continue; |
| 55 |
} |
| 56 |
|
| 57 |
irrelevant_ids.push_back(id); |
| 58 |
|
| 59 |
// If the type of this id has not been seen before, add a mapping from this |
| 60 |
// type id to an empty list in |types_to_ids|. The list will be filled later |
| 61 |
// on. |
| 62 |
if (types_to_ids.count(declaration->type_id()) == 0) { |
| 63 |
types_to_ids.insert({declaration->type_id(), {}}); |
| 64 |
} |
| 65 |
} |
| 66 |
|
| 67 |
// If no irrelevant ids were found, return. |
| 68 |
if (irrelevant_ids.empty()) { |
| 69 |
return; |
| 70 |
} |
| 71 |
|
| 72 |
// For every type for which we have at least one irrelevant id, record all ids |
| 73 |
// in the module which have that type. Skip ids of OpFunction instructions as |
| 74 |
// we cannot use these as replacements. |
| 75 |
for (const auto& pair : GetIRContext()->get_def_use_mgr()->id_to_defs()) { |
| 76 |
uint32_t type_id = pair.second->type_id(); |
| 77 |
if (pair.second->opcode() != SpvOpFunction && type_id && |
| 78 |
types_to_ids.count(type_id)) { |
| 79 |
types_to_ids[type_id].push_back(pair.first); |
| 80 |
} |
| 81 |
} |
| 82 |
|
| 83 |
// Keep a list of all the transformations to perform. We avoid applying the |
| 84 |
// transformations while traversing the uses since applying the transformation |
| 85 |
// invalidates all analyses, and we want to avoid invalidating and recomputing |
| 86 |
// them every time. |
| 87 |
std::vector<TransformationReplaceIrrelevantId> transformations_to_apply; |
| 88 |
|
| 89 |
// Loop through all the uses of irrelevant ids, check that the id can be |
| 90 |
// replaced and randomly decide whether to apply the transformation. |
| 91 |
for (auto irrelevant_id : irrelevant_ids) { |
| 92 |
uint32_t type_id = |
| 93 |
GetIRContext()->get_def_use_mgr()->GetDef(irrelevant_id)->type_id(); |
| 94 |
|
| 95 |
GetIRContext()->get_def_use_mgr()->ForEachUse( |
| 96 |
irrelevant_id, [this, &irrelevant_id, &type_id, &types_to_ids, |
| 97 |
&transformations_to_apply](opt::Instruction* use_inst, |
| 98 |
uint32_t use_index) { |
| 99 |
// Randomly decide whether to consider this use. |
| 100 |
if (!GetFuzzerContext()->ChoosePercentage( |
| 101 |
GetFuzzerContext()->GetChanceOfReplacingIrrelevantId())) { |
| 102 |
return; |
| 103 |
} |
| 104 |
|
| 105 |
// The id must be used as an input operand. |
| 106 |
if (use_index < use_inst->NumOperands() - use_inst->NumInOperands()) { |
| 107 |
// The id is used as an output operand, so we cannot replace this |
| 108 |
// usage. |
| 109 |
return; |
| 110 |
} |
| 111 |
|
| 112 |
// Get the input operand index for this use, from the absolute operand |
| 113 |
// index. |
| 114 |
uint32_t in_index = |
| 115 |
fuzzerutil::InOperandIndexFromOperandIndex(*use_inst, use_index); |
| 116 |
|
| 117 |
// Only go ahead if this id use can be replaced in principle. |
| 118 |
if (!fuzzerutil::IdUseCanBeReplaced(GetIRContext(), |
| 119 |
*GetTransformationContext(), |
| 120 |
use_inst, in_index)) { |
| 121 |
return; |
| 122 |
} |
| 123 |
|
| 124 |
// Find out which ids could be used to replace this use. |
| 125 |
std::vector<uint32_t> available_replacement_ids; |
| 126 |
|
| 127 |
for (auto replacement_id : types_to_ids[type_id]) { |
| 128 |
// It would be pointless to replace an id with itself. |
| 129 |
if (replacement_id == irrelevant_id) { |
| 130 |
continue; |
| 131 |
} |
| 132 |
|
| 133 |
// We cannot replace a variable initializer with a non-constant. |
| 134 |
if (TransformationReplaceIrrelevantId:: |
| 135 |
AttemptsToReplaceVariableInitializerWithNonConstant( |
| 136 |
*use_inst, *GetIRContext()->get_def_use_mgr()->GetDef( |
| 137 |
replacement_id))) { |
| 138 |
continue; |
| 139 |
} |
| 140 |
|
| 141 |
// Only consider this replacement if the use point is within a basic |
| 142 |
// block and the id is available at the use point. |
| 143 |
// |
| 144 |
// There might be opportunities for replacing a non-block use of an |
| 145 |
// irrelevant id - such as the initializer of a global variable - |
| 146 |
// with another id, but it would require some care (e.g. to ensure |
| 147 |
// that the replacement id is defined earlier) and does not seem |
| 148 |
// worth doing. |
| 149 |
if (GetIRContext()->get_instr_block(use_inst) && |
| 150 |
fuzzerutil::IdIsAvailableAtUse(GetIRContext(), use_inst, |
| 151 |
in_index, replacement_id)) { |
| 152 |
available_replacement_ids.push_back(replacement_id); |
| 153 |
} |
| 154 |
} |
| 155 |
|
| 156 |
// Only go ahead if there is at least one id with which this use can |
| 157 |
// be replaced. |
| 158 |
if (available_replacement_ids.empty()) { |
| 159 |
return; |
| 160 |
} |
| 161 |
|
| 162 |
// Choose the replacement id randomly. |
| 163 |
uint32_t replacement_id = |
| 164 |
available_replacement_ids[GetFuzzerContext()->RandomIndex( |
| 165 |
available_replacement_ids)]; |
| 166 |
|
| 167 |
// Add this replacement to the list of transformations to apply. |
| 168 |
transformations_to_apply.emplace_back( |
| 169 |
TransformationReplaceIrrelevantId( |
| 170 |
MakeIdUseDescriptorFromUse(GetIRContext(), use_inst, |
| 171 |
in_index), |
| 172 |
replacement_id)); |
| 173 |
}); |
| 174 |
} |
| 175 |
|
| 176 |
// Apply all the transformations. |
| 177 |
for (const auto& transformation : transformations_to_apply) { |
| 178 |
ApplyTransformation(transformation); |
| 179 |
} |
| 180 |
} |
| 181 |
|
| 182 |
} // namespace fuzz |
| 183 |
} // namespace spvtools |