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_duplicate_regions_with_selections.h"
16
17 #include "source/fuzz/fuzzer_util.h"
18 #include "source/fuzz/transformation_duplicate_region_with_selection.h"
19
20 namespace spvtools {
21 namespace fuzz {
22
23 FuzzerPassDuplicateRegionsWithSelections::
FuzzerPassDuplicateRegionsWithSelections(opt::IRContext * ir_context,TransformationContext * transformation_context,FuzzerContext * fuzzer_context,protobufs::TransformationSequence * transformations)24 FuzzerPassDuplicateRegionsWithSelections(
25 opt::IRContext* ir_context,
26 TransformationContext* transformation_context,
27 FuzzerContext* fuzzer_context,
28 protobufs::TransformationSequence* transformations)
29 : FuzzerPass(ir_context, transformation_context, fuzzer_context,
30 transformations) {}
31
Apply()32 void FuzzerPassDuplicateRegionsWithSelections::Apply() {
33 // Iterate over all of the functions in the module.
34 for (auto& function : *GetIRContext()->module()) {
35 // Randomly decide whether to apply the transformation.
36 if (!GetFuzzerContext()->ChoosePercentage(
37 GetFuzzerContext()->GetChanceOfDuplicatingRegionWithSelection())) {
38 continue;
39 }
40 std::vector<opt::BasicBlock*> candidate_entry_blocks;
41 for (auto& block : function) {
42 // We don't consider the first block to be the entry block, since it
43 // could contain OpVariable instructions that would require additional
44 // operations to be reassigned.
45 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3778):
46 // Consider extending this fuzzer pass to allow the first block to be
47 // used in duplication.
48 if (&block == &*function.begin()) {
49 continue;
50 }
51 candidate_entry_blocks.push_back(&block);
52 }
53 if (candidate_entry_blocks.empty()) {
54 continue;
55 }
56 // Randomly choose the entry block.
57 auto entry_block = candidate_entry_blocks[GetFuzzerContext()->RandomIndex(
58 candidate_entry_blocks)];
59 auto dominator_analysis = GetIRContext()->GetDominatorAnalysis(&function);
60 auto postdominator_analysis =
61 GetIRContext()->GetPostDominatorAnalysis(&function);
62 std::vector<opt::BasicBlock*> candidate_exit_blocks;
63 for (auto postdominates_entry_block = entry_block;
64 postdominates_entry_block != nullptr;
65 postdominates_entry_block = postdominator_analysis->ImmediateDominator(
66 postdominates_entry_block)) {
67 // The candidate exit block must be dominated by the entry block and the
68 // entry block must be post-dominated by the candidate exit block. Ignore
69 // the block if it heads a selection construct or a loop construct.
70 if (dominator_analysis->Dominates(entry_block,
71 postdominates_entry_block) &&
72 !postdominates_entry_block->GetMergeInst()) {
73 candidate_exit_blocks.push_back(postdominates_entry_block);
74 }
75 }
76 if (candidate_exit_blocks.empty()) {
77 continue;
78 }
79 // Randomly choose the exit block.
80 auto exit_block = candidate_exit_blocks[GetFuzzerContext()->RandomIndex(
81 candidate_exit_blocks)];
82
83 auto region_blocks =
84 TransformationDuplicateRegionWithSelection::GetRegionBlocks(
85 GetIRContext(), entry_block, exit_block);
86
87 // Construct |original_label_to_duplicate_label| by iterating over all
88 // blocks in the region. Construct |original_id_to_duplicate_id| and
89 // |original_id_to_phi_id| by iterating over all instructions in each block.
90 std::map<uint32_t, uint32_t> original_label_to_duplicate_label;
91 std::map<uint32_t, uint32_t> original_id_to_duplicate_id;
92 std::map<uint32_t, uint32_t> original_id_to_phi_id;
93 for (auto& block : region_blocks) {
94 original_label_to_duplicate_label[block->id()] =
95 GetFuzzerContext()->GetFreshId();
96 for (auto& instr : *block) {
97 if (instr.result_id()) {
98 original_id_to_duplicate_id[instr.result_id()] =
99 GetFuzzerContext()->GetFreshId();
100 auto final_instruction = &*exit_block->tail();
101 // &*exit_block->tail() is the final instruction of the region.
102 // The instruction is available at the end of the region if and only
103 // if it is available before this final instruction or it is the final
104 // instruction.
105 if ((&instr == final_instruction ||
106 fuzzerutil::IdIsAvailableBeforeInstruction(
107 GetIRContext(), final_instruction, instr.result_id()))) {
108 original_id_to_phi_id[instr.result_id()] =
109 GetFuzzerContext()->GetFreshId();
110 }
111 }
112 }
113 }
114 // Randomly decide between value "true" or "false" for a bool constant.
115 // Make sure the transformation has access to a bool constant to be used
116 // while creating conditional construct.
117 auto condition_id =
118 FindOrCreateBoolConstant(GetFuzzerContext()->ChooseEven(), true);
119
120 TransformationDuplicateRegionWithSelection transformation =
121 TransformationDuplicateRegionWithSelection(
122 GetFuzzerContext()->GetFreshId(), condition_id,
123 GetFuzzerContext()->GetFreshId(), entry_block->id(),
124 exit_block->id(), original_label_to_duplicate_label,
125 original_id_to_duplicate_id, original_id_to_phi_id);
126 MaybeApplyTransformation(transformation);
127 }
128 }
129 } // namespace fuzz
130 } // namespace spvtools
131