Debian Codegraph @

third_party/spirv-tools/source/fuzz/transformation_replace_opselect_with_conditional_branch.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/transformation_replace_opselect_with_conditional_branch.h"
16
17 #include "source/fuzz/fuzzer_util.h"
18
19 namespace spvtools {
20 namespace fuzz {
21 TransformationReplaceOpSelectWithConditionalBranch::
22 TransformationReplaceOpSelectWithConditionalBranch(
23 const spvtools::fuzz::protobufs::
24 TransformationReplaceOpSelectWithConditionalBranch& message)
25 : message_(message) {}
26
27 TransformationReplaceOpSelectWithConditionalBranch::
28 TransformationReplaceOpSelectWithConditionalBranch(
29 uint32_t select_id, uint32_t true_block_id, uint32_t false_block_id) {
30 message_.set_select_id(select_id);
31 message_.set_true_block_id(true_block_id);
32 message_.set_false_block_id(false_block_id);
33 }
34
35 bool TransformationReplaceOpSelectWithConditionalBranch::IsApplicable(
36 opt::IRContext* ir_context,
37 const TransformationContext& /* unused */) const {
38 assert((message_.true_block_id() || message_.false_block_id()) &&
39 "At least one of the ids must be non-zero.");
40
41 // Check that the non-zero ids are fresh.
42 std::set<uint32_t> used_ids;
43 for (uint32_t id : {message_.true_block_id(), message_.false_block_id()}) {
44 if (id && !CheckIdIsFreshAndNotUsedByThisTransformation(id, ir_context,
45 &used_ids)) {
46 return false;
47 }
48 }
49
50 auto instruction =
51 ir_context->get_def_use_mgr()->GetDef(message_.select_id());
52
53 // The instruction must exist and it must be an OpSelect instruction.
54 if (!instruction || instruction->opcode() != SpvOpSelect) {
55 return false;
56 }
57
58 // Check that the condition is a scalar boolean.
59 auto condition = ir_context->get_def_use_mgr()->GetDef(
60 instruction->GetSingleWordInOperand(0));
61 assert(condition && "The condition should always exist in a valid module.");
62
63 auto condition_type =
64 ir_context->get_type_mgr()->GetType(condition->type_id());
65 if (!condition_type->AsBool()) {
66 return false;
67 }
68
69 auto block = ir_context->get_instr_block(instruction);
70 assert(block && "The block containing the instruction must be found");
71
72 // The instruction must be the first in its block.
73 if (instruction->unique_id() != block->begin()->unique_id()) {
74 return false;
75 }
76
77 // The block must not be a merge block.
78 if (ir_context->GetStructuredCFGAnalysis()->IsMergeBlock(block->id())) {
79 return false;
80 }
81
82 // The block must have exactly one predecessor.
83 auto predecessors = ir_context->cfg()->preds(block->id());
84 if (predecessors.size() != 1) {
85 return false;
86 }
87
88 uint32_t pred_id = predecessors[0];
89 auto predecessor = ir_context->get_instr_block(pred_id);
90
91 // The predecessor must not be the header of a construct and it must end with
92 // OpBranch.
93 if (predecessor->GetMergeInst() != nullptr ||
94 predecessor->terminator()->opcode() != SpvOpBranch) {
95 return false;
96 }
97
98 return true;
99 }
100
101 void TransformationReplaceOpSelectWithConditionalBranch::Apply(
102 opt::IRContext* ir_context, TransformationContext* /* unused */) const {
103 auto instruction =
104 ir_context->get_def_use_mgr()->GetDef(message_.select_id());
105
106 auto block = ir_context->get_instr_block(instruction);
107
108 auto predecessor =
109 ir_context->get_instr_block(ir_context->cfg()->preds(block->id())[0]);
110
111 // Create a new block for each non-zero id in {|message_.true_branch_id|,
112 // |message_.false_branch_id|}. Make each newly-created block branch
113 // unconditionally to the instruction block.
114 for (uint32_t id : {message_.true_block_id(), message_.false_block_id()}) {
115 if (id) {
116 fuzzerutil::UpdateModuleIdBound(ir_context, id);
117
118 // Create the new block.
119 auto new_block = MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
120 ir_context, SpvOpLabel, 0, id, opt::Instruction::OperandList{}));
121
122 // Add an unconditional branch from the new block to the instruction
123 // block.
124 new_block->AddInstruction(MakeUnique<opt::Instruction>(
125 ir_context, SpvOpBranch, 0, 0,
126 opt::Instruction::OperandList{{SPV_OPERAND_TYPE_ID, {block->id()}}}));
127
128 // Insert the new block right after the predecessor of the instruction
129 // block.
130 block->GetParent()->InsertBasicBlockBefore(std::move(new_block), block);
131 }
132 }
133
134 // Delete the OpBranch instruction from the predecessor.
135 ir_context->KillInst(predecessor->terminator());
136
137 // Add an OpSelectionMerge instruction to the predecessor block, where the
138 // merge block is the instruction block.
139 predecessor->AddInstruction(MakeUnique<opt::Instruction>(
140 ir_context, SpvOpSelectionMerge, 0, 0,
141 opt::Instruction::OperandList{{SPV_OPERAND_TYPE_ID, {block->id()}},
142 {SPV_OPERAND_TYPE_SELECTION_CONTROL,
143 {SpvSelectionControlMaskNone}}}));
144
145 // |if_block| will be the true block, if it has been created, the instruction
146 // block otherwise.
147 uint32_t if_block =
148 message_.true_block_id() ? message_.true_block_id() : block->id();
149
150 // |else_block| will be the false block, if it has been created, the
151 // instruction block otherwise.
152 uint32_t else_block =
153 message_.false_block_id() ? message_.false_block_id() : block->id();
154
155 assert(if_block != else_block &&
156 "|if_block| and |else_block| should always be different, if the "
157 "transformation is applicable.");
158
159 // Add a conditional branching instruction to the predecessor, branching to
160 // |if_block| if the condition is true and to |if_false| otherwise.
161 predecessor->AddInstruction(MakeUnique<opt::Instruction>(
162 ir_context, SpvOpBranchConditional, 0, 0,
163 opt::Instruction::OperandList{
164 {SPV_OPERAND_TYPE_ID, {instruction->GetSingleWordInOperand(0)}},
165 {SPV_OPERAND_TYPE_ID, {if_block}},
166 {SPV_OPERAND_TYPE_ID, {else_block}}}));
167
168 // |if_pred| will be the true block, if it has been created, the existing
169 // predecessor otherwise.
170 uint32_t if_pred =
171 message_.true_block_id() ? message_.true_block_id() : predecessor->id();
172
173 // |else_pred| will be the false block, if it has been created, the existing
174 // predecessor otherwise.
175 uint32_t else_pred =
176 message_.false_block_id() ? message_.false_block_id() : predecessor->id();
177
178 // Replace the OpSelect instruction in the merge block with an OpPhi.
179 // This: OpSelect %type %cond %if %else
180 // will become: OpPhi %type %if %if_pred %else %else_pred
181 instruction->SetOpcode(SpvOpPhi);
182 std::vector<opt::Operand> operands;
183
184 operands.emplace_back(instruction->GetInOperand(1));
185 operands.emplace_back(opt::Operand{SPV_OPERAND_TYPE_ID, {if_pred}});
186
187 operands.emplace_back(instruction->GetInOperand(2));
188 operands.emplace_back(opt::Operand{SPV_OPERAND_TYPE_ID, {else_pred}});
189
190 instruction->SetInOperands(std::move(operands));
191
192 // Invalidate all analyses, since the structure of the module was changed.
193 ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
194 }
195
196 protobufs::Transformation
197 TransformationReplaceOpSelectWithConditionalBranch::ToMessage() const {
198 protobufs::Transformation result;
199 *result.mutable_replace_opselect_with_conditional_branch() = message_;
200 return result;
201 }
202
203 std::unordered_set<uint32_t>
204 TransformationReplaceOpSelectWithConditionalBranch::GetFreshIds() const {
205 return {message_.true_block_id(), message_.false_block_id()};
206 }
207
208 } // namespace fuzz
209 } // namespace spvtools