| 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_add_opphi_synonyms.h" |
| 16 |
|
| 17 |
#include "source/fuzz/fuzzer_util.h" |
| 18 |
#include "source/fuzz/transformation_add_opphi_synonym.h" |
| 19 |
|
| 20 |
namespace spvtools { |
| 21 |
namespace fuzz { |
| 22 |
|
| 23 |
FuzzerPassAddOpPhiSynonyms::FuzzerPassAddOpPhiSynonyms( |
| 24 |
opt::IRContext* ir_context, TransformationContext* transformation_context, |
| 25 |
FuzzerContext* fuzzer_context, |
| 26 |
protobufs::TransformationSequence* transformations) |
| 27 |
: FuzzerPass(ir_context, transformation_context, fuzzer_context, |
| 28 |
transformations) {} |
| 29 |
|
| 30 |
FuzzerPassAddOpPhiSynonyms::~FuzzerPassAddOpPhiSynonyms() = default; |
| 31 |
|
| 32 |
void FuzzerPassAddOpPhiSynonyms::Apply() { |
| 33 |
// Get a list of synonymous ids with the same type that can be used in the |
| 34 |
// same OpPhi instruction. |
| 35 |
auto equivalence_classes = GetIdEquivalenceClasses(); |
| 36 |
|
| 37 |
// Make a list of references, to avoid copying sets unnecessarily. |
| 38 |
std::vector<std::set<uint32_t>*> equivalence_class_pointers; |
| 39 |
for (auto& set : equivalence_classes) { |
| 40 |
equivalence_class_pointers.push_back(&set); |
| 41 |
} |
| 42 |
|
| 43 |
// Keep a list of transformations to apply at the end. |
| 44 |
std::vector<TransformationAddOpPhiSynonym> transformations_to_apply; |
| 45 |
|
| 46 |
for (auto& function : *GetIRContext()->module()) { |
| 47 |
for (auto& block : function) { |
| 48 |
// Randomly decide whether to consider this block. |
| 49 |
if (!GetFuzzerContext()->ChoosePercentage( |
| 50 |
GetFuzzerContext()->GetChanceOfAddingOpPhiSynonym())) { |
| 51 |
continue; |
| 52 |
} |
| 53 |
|
| 54 |
// The block must not be dead. |
| 55 |
if (GetTransformationContext()->GetFactManager()->BlockIsDead( |
| 56 |
block.id())) { |
| 57 |
continue; |
| 58 |
} |
| 59 |
|
| 60 |
// The block must have at least one predecessor. |
| 61 |
size_t num_preds = GetIRContext()->cfg()->preds(block.id()).size(); |
| 62 |
if (num_preds == 0) { |
| 63 |
continue; |
| 64 |
} |
| 65 |
|
| 66 |
std::set<uint32_t>* chosen_equivalence_class = nullptr; |
| 67 |
|
| 68 |
if (num_preds > 1) { |
| 69 |
// If the block has more than one predecessor, prioritise sets with at |
| 70 |
// least 2 ids available at some predecessor. |
| 71 |
chosen_equivalence_class = MaybeFindSuitableEquivalenceClassRandomly( |
| 72 |
equivalence_class_pointers, block.id(), 2); |
| 73 |
} |
| 74 |
|
| 75 |
// If a set was not already chosen, choose one with at least one available |
| 76 |
// id. |
| 77 |
if (!chosen_equivalence_class) { |
| 78 |
chosen_equivalence_class = MaybeFindSuitableEquivalenceClassRandomly( |
| 79 |
equivalence_class_pointers, block.id(), 1); |
| 80 |
} |
| 81 |
|
| 82 |
// If no suitable set was found, we cannot apply the transformation to |
| 83 |
// this block. |
| 84 |
if (!chosen_equivalence_class) { |
| 85 |
continue; |
| 86 |
} |
| 87 |
|
| 88 |
// Initialise the map from predecessor labels to ids. |
| 89 |
std::map<uint32_t, uint32_t> preds_to_ids; |
| 90 |
|
| 91 |
// Keep track of the ids used and of the id of a predecessor with at least |
| 92 |
// two ids to choose from. This is to ensure that, if possible, at least |
| 93 |
// two distinct ids will be used. |
| 94 |
std::set<uint32_t> ids_chosen; |
| 95 |
uint32_t pred_with_alternatives = 0; |
| 96 |
|
| 97 |
// Choose an id for each predecessor. |
| 98 |
for (uint32_t pred_id : GetIRContext()->cfg()->preds(block.id())) { |
| 99 |
auto suitable_ids = GetSuitableIds(*chosen_equivalence_class, pred_id); |
| 100 |
assert(!suitable_ids.empty() && |
| 101 |
"We must be able to find at least one suitable id because the " |
| 102 |
"equivalence class was chosen among suitable ones."); |
| 103 |
|
| 104 |
// If this predecessor has more than one id to choose from and it is the |
| 105 |
// first one of this kind that we found, remember its id. |
| 106 |
if (suitable_ids.size() > 1 && !pred_with_alternatives) { |
| 107 |
pred_with_alternatives = pred_id; |
| 108 |
} |
| 109 |
|
| 110 |
uint32_t chosen_id = |
| 111 |
suitable_ids[GetFuzzerContext()->RandomIndex(suitable_ids)]; |
| 112 |
|
| 113 |
// Add this id to the set of ids chosen. |
| 114 |
ids_chosen.emplace(chosen_id); |
| 115 |
|
| 116 |
// Add the pair (predecessor, chosen id) to the map. |
| 117 |
preds_to_ids[pred_id] = chosen_id; |
| 118 |
} |
| 119 |
|
| 120 |
// If: |
| 121 |
// - the block has more than one predecessor |
| 122 |
// - at least one predecessor has more than one alternative |
| 123 |
// - the same id has been chosen by all the predecessors |
| 124 |
// then choose another one for the predecessor with more than one |
| 125 |
// alternative. |
| 126 |
if (num_preds > 1 && pred_with_alternatives != 0 && |
| 127 |
ids_chosen.size() == 1) { |
| 128 |
auto suitable_ids = |
| 129 |
GetSuitableIds(*chosen_equivalence_class, pred_with_alternatives); |
| 130 |
uint32_t chosen_id = |
| 131 |
GetFuzzerContext()->RemoveAtRandomIndex(&suitable_ids); |
| 132 |
if (chosen_id == preds_to_ids[pred_with_alternatives]) { |
| 133 |
chosen_id = GetFuzzerContext()->RemoveAtRandomIndex(&suitable_ids); |
| 134 |
} |
| 135 |
|
| 136 |
preds_to_ids[pred_with_alternatives] = chosen_id; |
| 137 |
} |
| 138 |
|
| 139 |
// Add the transformation to the list of transformations to apply. |
| 140 |
transformations_to_apply.emplace_back(block.id(), preds_to_ids, |
| 141 |
GetFuzzerContext()->GetFreshId()); |
| 142 |
} |
| 143 |
} |
| 144 |
|
| 145 |
// Apply the transformations. |
| 146 |
for (const auto& transformation : transformations_to_apply) { |
| 147 |
ApplyTransformation(transformation); |
| 148 |
} |
| 149 |
} |
| 150 |
|
| 151 |
std::vector<std::set<uint32_t>> |
| 152 |
FuzzerPassAddOpPhiSynonyms::GetIdEquivalenceClasses() { |
| 153 |
std::vector<std::set<uint32_t>> id_equivalence_classes; |
| 154 |
|
| 155 |
// Keep track of all the ids that have already be assigned to a class. |
| 156 |
std::set<uint32_t> already_in_a_class; |
| 157 |
|
| 158 |
for (const auto& pair : GetIRContext()->get_def_use_mgr()->id_to_defs()) { |
| 159 |
// Exclude ids that have already been assigned to a class. |
| 160 |
if (already_in_a_class.count(pair.first)) { |
| 161 |
continue; |
| 162 |
} |
| 163 |
|
| 164 |
// Exclude irrelevant ids. |
| 165 |
if (GetTransformationContext()->GetFactManager()->IdIsIrrelevant( |
| 166 |
pair.first)) { |
| 167 |
continue; |
| 168 |
} |
| 169 |
|
| 170 |
// Exclude ids having a type that is not allowed by the transformation. |
| 171 |
if (!TransformationAddOpPhiSynonym::CheckTypeIsAllowed( |
| 172 |
GetIRContext(), pair.second->type_id())) { |
| 173 |
continue; |
| 174 |
} |
| 175 |
|
| 176 |
// Exclude OpFunction and OpUndef instructions, because: |
| 177 |
// - OpFunction does not yield a value; |
| 178 |
// - OpUndef yields an undefined value at each use, so it should never be a |
| 179 |
// synonym of another id. |
| 180 |
if (pair.second->opcode() == SpvOpFunction || |
| 181 |
pair.second->opcode() == SpvOpUndef) { |
| 182 |
continue; |
| 183 |
} |
| 184 |
|
| 185 |
// We need a new equivalence class for this id. |
| 186 |
std::set<uint32_t> new_equivalence_class; |
| 187 |
|
| 188 |
// Add this id to the class. |
| 189 |
new_equivalence_class.emplace(pair.first); |
| 190 |
already_in_a_class.emplace(pair.first); |
| 191 |
|
| 192 |
// Add all the synonyms with the same type to this class. |
| 193 |
for (auto synonym : |
| 194 |
GetTransformationContext()->GetFactManager()->GetSynonymsForId( |
| 195 |
pair.first)) { |
| 196 |
// The synonym must be a plain id - it cannot be an indexed access into a |
| 197 |
// composite. |
| 198 |
if (synonym->index_size() > 0) { |
| 199 |
continue; |
| 200 |
} |
| 201 |
|
| 202 |
// The synonym must not be irrelevant. |
| 203 |
if (GetTransformationContext()->GetFactManager()->IdIsIrrelevant( |
| 204 |
synonym->object())) { |
| 205 |
continue; |
| 206 |
} |
| 207 |
|
| 208 |
auto synonym_def = |
| 209 |
GetIRContext()->get_def_use_mgr()->GetDef(synonym->object()); |
| 210 |
// The synonym must exist and have the same type as the id we are |
| 211 |
// considering. |
| 212 |
if (!synonym_def || synonym_def->type_id() != pair.second->type_id()) { |
| 213 |
continue; |
| 214 |
} |
| 215 |
|
| 216 |
// We can add this synonym to the new equivalence class. |
| 217 |
new_equivalence_class.emplace(synonym->object()); |
| 218 |
already_in_a_class.emplace(synonym->object()); |
| 219 |
} |
| 220 |
|
| 221 |
// Add the new equivalence class to the list of equivalence classes. |
| 222 |
id_equivalence_classes.emplace_back(std::move(new_equivalence_class)); |
| 223 |
} |
| 224 |
|
| 225 |
return id_equivalence_classes; |
| 226 |
} |
| 227 |
|
| 228 |
bool FuzzerPassAddOpPhiSynonyms::EquivalenceClassIsSuitableForBlock( |
| 229 |
const std::set<uint32_t>& equivalence_class, uint32_t block_id, |
| 230 |
uint32_t distinct_ids_required) { |
| 231 |
bool at_least_one_id_for_each_pred = true; |
| 232 |
|
| 233 |
// Keep a set of the suitable ids found. |
| 234 |
std::set<uint32_t> suitable_ids_found; |
| 235 |
|
| 236 |
// Loop through all the predecessors of the block. |
| 237 |
for (auto pred_id : GetIRContext()->cfg()->preds(block_id)) { |
| 238 |
// Find the last instruction in the predecessor block. |
| 239 |
auto last_instruction = |
| 240 |
GetIRContext()->get_instr_block(pred_id)->terminator(); |
| 241 |
|
| 242 |
// Initially assume that there is not a suitable id for this predecessor. |
| 243 |
bool at_least_one_suitable_id_found = false; |
| 244 |
for (uint32_t id : equivalence_class) { |
| 245 |
if (fuzzerutil::IdIsAvailableBeforeInstruction(GetIRContext(), |
| 246 |
last_instruction, id)) { |
| 247 |
// We have found a suitable id. |
| 248 |
at_least_one_suitable_id_found = true; |
| 249 |
suitable_ids_found.emplace(id); |
| 250 |
|
| 251 |
// If we have already found enough distinct suitable ids, we don't need |
| 252 |
// to check the remaining ones for this predecessor. |
| 253 |
if (suitable_ids_found.size() >= distinct_ids_required) { |
| 254 |
break; |
| 255 |
} |
| 256 |
} |
| 257 |
} |
| 258 |
// If no suitable id was found for this predecessor, this equivalence class |
| 259 |
// is not suitable and we don't need to check the other predecessors. |
| 260 |
if (!at_least_one_suitable_id_found) { |
| 261 |
at_least_one_id_for_each_pred = false; |
| 262 |
break; |
| 263 |
} |
| 264 |
} |
| 265 |
|
| 266 |
// The equivalence class is suitable if at least one suitable id was found for |
| 267 |
// each predecessor and we have found at least |distinct_ids_required| |
| 268 |
// distinct suitable ids in general. |
| 269 |
return at_least_one_id_for_each_pred && |
| 270 |
suitable_ids_found.size() >= distinct_ids_required; |
| 271 |
} |
| 272 |
|
| 273 |
std::vector<uint32_t> FuzzerPassAddOpPhiSynonyms::GetSuitableIds( |
| 274 |
const std::set<uint32_t>& ids, uint32_t pred_id) { |
| 275 |
// Initialise an empty vector of suitable ids. |
| 276 |
std::vector<uint32_t> suitable_ids; |
| 277 |
|
| 278 |
// Get the predecessor block. |
| 279 |
auto predecessor = fuzzerutil::MaybeFindBlock(GetIRContext(), pred_id); |
| 280 |
|
| 281 |
// Loop through the ids to find the suitable ones. |
| 282 |
for (uint32_t id : ids) { |
| 283 |
if (fuzzerutil::IdIsAvailableBeforeInstruction( |
| 284 |
GetIRContext(), predecessor->terminator(), id)) { |
| 285 |
suitable_ids.push_back(id); |
| 286 |
} |
| 287 |
} |
| 288 |
|
| 289 |
return suitable_ids; |
| 290 |
} |
| 291 |
|
| 292 |
std::set<uint32_t>* |
| 293 |
FuzzerPassAddOpPhiSynonyms::MaybeFindSuitableEquivalenceClassRandomly( |
| 294 |
const std::vector<std::set<uint32_t>*>& candidates, uint32_t block_id, |
| 295 |
uint32_t distinct_ids_required) { |
| 296 |
auto remaining_candidates = candidates; |
| 297 |
while (!remaining_candidates.empty()) { |
| 298 |
// Choose one set randomly and return it if it is suitable. |
| 299 |
auto chosen = |
| 300 |
GetFuzzerContext()->RemoveAtRandomIndex(&remaining_candidates); |
| 301 |
if (EquivalenceClassIsSuitableForBlock(*chosen, block_id, |
| 302 |
distinct_ids_required)) { |
| 303 |
return chosen; |
| 304 |
} |
| 305 |
} |
| 306 |
|
| 307 |
// No suitable sets were found. |
| 308 |
return nullptr; |
| 309 |
} |
| 310 |
|
| 311 |
} // namespace fuzz |
| 312 |
} // namespace spvtools |