Debian Codegraph @

third_party/spirv-tools/source/fuzz/fuzzer_pass_add_opphi_synonyms.cpp

raw
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