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