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