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