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_opselects_with_conditional_branches.h"
16
17 #include "source/fuzz/fuzzer_util.h"
18 #include "source/fuzz/instruction_descriptor.h"
19 #include "source/fuzz/transformation_replace_opselect_with_conditional_branch.h"
20 #include "source/fuzz/transformation_split_block.h"
21
22 namespace spvtools {
23 namespace fuzz {
24
25 FuzzerPassReplaceOpSelectsWithConditionalBranches::
FuzzerPassReplaceOpSelectsWithConditionalBranches(opt::IRContext * ir_context,TransformationContext * transformation_context,FuzzerContext * fuzzer_context,protobufs::TransformationSequence * transformations)26 FuzzerPassReplaceOpSelectsWithConditionalBranches(
27 opt::IRContext* ir_context,
28 TransformationContext* transformation_context,
29 FuzzerContext* fuzzer_context,
30 protobufs::TransformationSequence* transformations)
31 : FuzzerPass(ir_context, transformation_context, fuzzer_context,
32 transformations) {}
33
34 FuzzerPassReplaceOpSelectsWithConditionalBranches::
35 ~FuzzerPassReplaceOpSelectsWithConditionalBranches() = default;
36
Apply()37 void FuzzerPassReplaceOpSelectsWithConditionalBranches::Apply() {
38 // Keep track of the instructions that we want to replace. We need to collect
39 // them in a vector, since it's not safe to modify the module while iterating
40 // over it.
41 std::vector<uint32_t> replaceable_opselect_instruction_ids;
42
43 // Loop over all the instructions in the module.
44 for (auto& function : *GetIRContext()->module()) {
45 for (auto& block : function) {
46 // We cannot split loop headers, so we don't need to consider instructions
47 // in loop headers that are also merge blocks (since they would need to be
48 // split).
49 if (block.IsLoopHeader() &&
50 GetIRContext()->GetStructuredCFGAnalysis()->IsMergeBlock(
51 block.id())) {
52 continue;
53 }
54
55 for (auto& instruction : block) {
56 // We only care about OpSelect instructions.
57 if (instruction.opcode() != SpvOpSelect) {
58 continue;
59 }
60
61 // Randomly choose whether to consider this instruction for replacement.
62 if (!GetFuzzerContext()->ChoosePercentage(
63 GetFuzzerContext()
64 ->GetChanceOfReplacingOpselectWithConditionalBranch())) {
65 continue;
66 }
67
68 // If the selector does not have scalar boolean type (i.e., it is a
69 // boolean vector) then ignore this OpSelect.
70 if (GetIRContext()
71 ->get_def_use_mgr()
72 ->GetDef(fuzzerutil::GetTypeId(
73 GetIRContext(), instruction.GetSingleWordInOperand(0)))
74 ->opcode() != SpvOpTypeBool) {
75 continue;
76 }
77
78 // If the block is a loop header and we need to split it, the
79 // transformation cannot be applied because loop headers cannot be
80 // split. We can break out of this loop because the transformation can
81 // only be applied to at most the first instruction in a loop header.
82 if (block.IsLoopHeader() && InstructionNeedsSplitBefore(&instruction)) {
83 break;
84 }
85
86 // If the instruction separates an OpSampledImage from its use, the
87 // block cannot be split around it and the instruction cannot be
88 // replaced.
89 if (fuzzerutil::
90 SplittingBeforeInstructionSeparatesOpSampledImageDefinitionFromUse(
91 &block, &instruction)) {
92 continue;
93 }
94
95 // We can apply the transformation to this instruction.
96 replaceable_opselect_instruction_ids.push_back(instruction.result_id());
97 }
98 }
99 }
100
101 // Apply the transformations, splitting the blocks containing the
102 // instructions, if necessary.
103 for (uint32_t instruction_id : replaceable_opselect_instruction_ids) {
104 auto instruction =
105 GetIRContext()->get_def_use_mgr()->GetDef(instruction_id);
106
107 // If the instruction requires the block containing it to be split before
108 // it, split the block.
109 if (InstructionNeedsSplitBefore(instruction)) {
110 ApplyTransformation(TransformationSplitBlock(
111 MakeInstructionDescriptor(GetIRContext(), instruction),
112 GetFuzzerContext()->GetFreshId()));
113 }
114
115 // Decide whether to have two branches or just one.
116 bool two_branches = GetFuzzerContext()->ChoosePercentage(
117 GetFuzzerContext()
118 ->GetChanceOfAddingBothBranchesWhenReplacingOpSelect());
119
120 // If there will be only one branch, decide whether it will be the true
121 // branch or the false branch.
122 bool true_branch_id_zero =
123 !two_branches &&
124 GetFuzzerContext()->ChoosePercentage(
125 GetFuzzerContext()
126 ->GetChanceOfAddingTrueBranchWhenReplacingOpSelect());
127 bool false_branch_id_zero = !two_branches && !true_branch_id_zero;
128
129 uint32_t true_branch_id =
130 true_branch_id_zero ? 0 : GetFuzzerContext()->GetFreshId();
131 uint32_t false_branch_id =
132 false_branch_id_zero ? 0 : GetFuzzerContext()->GetFreshId();
133
134 ApplyTransformation(TransformationReplaceOpSelectWithConditionalBranch(
135 instruction_id, true_branch_id, false_branch_id));
136 }
137 }
138
139 bool FuzzerPassReplaceOpSelectsWithConditionalBranches::
InstructionNeedsSplitBefore(opt::Instruction * instruction)140 InstructionNeedsSplitBefore(opt::Instruction* instruction) {
141 assert(instruction && instruction->opcode() == SpvOpSelect &&
142 "The instruction must be OpSelect.");
143
144 auto block = GetIRContext()->get_instr_block(instruction);
145 assert(block && "The instruction must be contained in a block.");
146
147 // We need to split the block if the instruction is not the first in its
148 // block.
149 if (instruction->unique_id() != block->begin()->unique_id()) {
150 return true;
151 }
152
153 // We need to split the block if it is a merge block.
154 if (GetIRContext()->GetStructuredCFGAnalysis()->IsMergeBlock(block->id())) {
155 return true;
156 }
157
158 // We need to split the block if it has more than one predecessor.
159 if (GetIRContext()->cfg()->preds(block->id()).size() != 1) {
160 return true;
161 }
162
163 // We need to split the block if its predecessor is a header or it does not
164 // branch unconditionally to the block.
165 auto predecessor = GetIRContext()->get_instr_block(
166 GetIRContext()->cfg()->preds(block->id())[0]);
167 return predecessor->MergeBlockIdIfAny() ||
168 predecessor->terminator()->opcode() != SpvOpBranch;
169 }
170
171 } // namespace fuzz
172 } // namespace spvtools
173