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_add_loop_to_create_int_constant_synonym.h"
16 #include "source/fuzz/fuzzer_util.h"
17
18 namespace spvtools {
19 namespace fuzz {
20 namespace {
21 uint32_t kMaxNumOfIterations = 32;
22 }
23
24 TransformationAddLoopToCreateIntConstantSynonym::
TransformationAddLoopToCreateIntConstantSynonym(protobufs::TransformationAddLoopToCreateIntConstantSynonym message)25 TransformationAddLoopToCreateIntConstantSynonym(
26 protobufs::TransformationAddLoopToCreateIntConstantSynonym message)
27 : message_(std::move(message)) {}
28
29 TransformationAddLoopToCreateIntConstantSynonym::
TransformationAddLoopToCreateIntConstantSynonym(uint32_t constant_id,uint32_t initial_val_id,uint32_t step_val_id,uint32_t num_iterations_id,uint32_t block_after_loop_id,uint32_t syn_id,uint32_t loop_id,uint32_t ctr_id,uint32_t temp_id,uint32_t eventual_syn_id,uint32_t incremented_ctr_id,uint32_t cond_id,uint32_t additional_block_id)30 TransformationAddLoopToCreateIntConstantSynonym(
31 uint32_t constant_id, uint32_t initial_val_id, uint32_t step_val_id,
32 uint32_t num_iterations_id, uint32_t block_after_loop_id,
33 uint32_t syn_id, uint32_t loop_id, uint32_t ctr_id, uint32_t temp_id,
34 uint32_t eventual_syn_id, uint32_t incremented_ctr_id, uint32_t cond_id,
35 uint32_t additional_block_id) {
36 message_.set_constant_id(constant_id);
37 message_.set_initial_val_id(initial_val_id);
38 message_.set_step_val_id(step_val_id);
39 message_.set_num_iterations_id(num_iterations_id);
40 message_.set_block_after_loop_id(block_after_loop_id);
41 message_.set_syn_id(syn_id);
42 message_.set_loop_id(loop_id);
43 message_.set_ctr_id(ctr_id);
44 message_.set_temp_id(temp_id);
45 message_.set_eventual_syn_id(eventual_syn_id);
46 message_.set_incremented_ctr_id(incremented_ctr_id);
47 message_.set_cond_id(cond_id);
48 message_.set_additional_block_id(additional_block_id);
49 }
50
IsApplicable(opt::IRContext * ir_context,const TransformationContext & transformation_context) const51 bool TransformationAddLoopToCreateIntConstantSynonym::IsApplicable(
52 opt::IRContext* ir_context,
53 const TransformationContext& transformation_context) const {
54 // Check that |message_.constant_id|, |message_.initial_val_id| and
55 // |message_.step_val_id| are existing constants, and that their values are
56 // not irrelevant.
57 auto constant = ir_context->get_constant_mgr()->FindDeclaredConstant(
58 message_.constant_id());
59 auto initial_val = ir_context->get_constant_mgr()->FindDeclaredConstant(
60 message_.initial_val_id());
61 auto step_val = ir_context->get_constant_mgr()->FindDeclaredConstant(
62 message_.step_val_id());
63
64 if (!constant || !initial_val || !step_val) {
65 return false;
66 }
67 if (transformation_context.GetFactManager()->IdIsIrrelevant(
68 message_.constant_id()) ||
69 transformation_context.GetFactManager()->IdIsIrrelevant(
70 message_.initial_val_id()) ||
71 transformation_context.GetFactManager()->IdIsIrrelevant(
72 message_.step_val_id())) {
73 return false;
74 }
75
76 // Check that the type of |constant| is integer scalar or vector with integer
77 // components.
78 if (!constant->AsIntConstant() &&
79 (!constant->AsVectorConstant() ||
80 !constant->type()->AsVector()->element_type()->AsInteger())) {
81 return false;
82 }
83
84 // Check that the component bit width of |constant| is <= 64.
85 // Consider the width of the constant if it is an integer, of a single
86 // component if it is a vector.
87 uint32_t bit_width =
88 constant->AsIntConstant()
89 ? constant->type()->AsInteger()->width()
90 : constant->type()->AsVector()->element_type()->AsInteger()->width();
91 if (bit_width > 64) {
92 return false;
93 }
94
95 auto constant_def =
96 ir_context->get_def_use_mgr()->GetDef(message_.constant_id());
97 auto initial_val_def =
98 ir_context->get_def_use_mgr()->GetDef(message_.initial_val_id());
99 auto step_val_def =
100 ir_context->get_def_use_mgr()->GetDef(message_.step_val_id());
101
102 // Check that |constant|, |initial_val| and |step_val| have the same type,
103 // with possibly different signedness.
104 if (!fuzzerutil::TypesAreEqualUpToSign(ir_context, constant_def->type_id(),
105 initial_val_def->type_id()) ||
106 !fuzzerutil::TypesAreEqualUpToSign(ir_context, constant_def->type_id(),
107 step_val_def->type_id())) {
108 return false;
109 }
110
111 // |message_.num_iterations_id| must be a non-irrelevant integer constant with
112 // bit width 32.
113 auto num_iterations = ir_context->get_constant_mgr()->FindDeclaredConstant(
114 message_.num_iterations_id());
115
116 if (!num_iterations || !num_iterations->AsIntConstant() ||
117 num_iterations->type()->AsInteger()->width() != 32 ||
118 transformation_context.GetFactManager()->IdIsIrrelevant(
119 message_.num_iterations_id())) {
120 return false;
121 }
122
123 // Check that the number of iterations is > 0 and <= 32.
124 uint32_t num_iterations_value =
125 num_iterations->AsIntConstant()->GetU32BitValue();
126
127 if (num_iterations_value == 0 || num_iterations_value > kMaxNumOfIterations) {
128 return false;
129 }
130
131 // Check that the module contains 32-bit signed integer scalar constants of
132 // value 0 and 1.
133 if (!fuzzerutil::MaybeGetIntegerConstant(ir_context, transformation_context,
134 {0}, 32, true, false)) {
135 return false;
136 }
137
138 if (!fuzzerutil::MaybeGetIntegerConstant(ir_context, transformation_context,
139 {1}, 32, true, false)) {
140 return false;
141 }
142
143 // Check that the module contains the Bool type.
144 if (!fuzzerutil::MaybeGetBoolType(ir_context)) {
145 return false;
146 }
147
148 // Check that the equation C = I - S * N is satisfied.
149
150 // Collect the components in vectors (if the constants are scalars, these
151 // vectors will contain the constants themselves).
152 std::vector<const opt::analysis::Constant*> c_components;
153 std::vector<const opt::analysis::Constant*> i_components;
154 std::vector<const opt::analysis::Constant*> s_components;
155 if (constant->AsIntConstant()) {
156 c_components.emplace_back(constant);
157 i_components.emplace_back(initial_val);
158 s_components.emplace_back(step_val);
159 } else {
160 // It is a vector: get all the components.
161 c_components = constant->AsVectorConstant()->GetComponents();
162 i_components = initial_val->AsVectorConstant()->GetComponents();
163 s_components = step_val->AsVectorConstant()->GetComponents();
164 }
165
166 // Check the value of the components satisfy the equation.
167 for (uint32_t i = 0; i < c_components.size(); i++) {
168 // Use 64-bits integers to be able to handle constants of any width <= 64.
169 uint64_t c_value = c_components[i]->AsIntConstant()->GetZeroExtendedValue();
170 uint64_t i_value = i_components[i]->AsIntConstant()->GetZeroExtendedValue();
171 uint64_t s_value = s_components[i]->AsIntConstant()->GetZeroExtendedValue();
172
173 uint64_t result = i_value - s_value * num_iterations_value;
174
175 // Use bit shifts to ignore the first bits in excess (if there are any). By
176 // shifting left, we discard the first |64 - bit_width| bits. By shifting
177 // right, we move the bits back to their correct position.
178 result = (result << (64 - bit_width)) >> (64 - bit_width);
179
180 if (c_value != result) {
181 return false;
182 }
183 }
184
185 // Check that |message_.block_after_loop_id| is the label of a block.
186 auto block =
187 fuzzerutil::MaybeFindBlock(ir_context, message_.block_after_loop_id());
188
189 // Check that the block exists and has a single predecessor.
190 if (!block || ir_context->cfg()->preds(block->id()).size() != 1) {
191 return false;
192 }
193
194 // Check that the block is not dead. If it is then the new loop would be
195 // dead and the data it computes would be irrelevant, so we would not be able
196 // to make a synonym.
197 if (transformation_context.GetFactManager()->BlockIsDead(block->id())) {
198 return false;
199 }
200
201 // Check that the block is not a merge block.
202 if (ir_context->GetStructuredCFGAnalysis()->IsMergeBlock(block->id())) {
203 return false;
204 }
205
206 // Check that the block is not a continue block.
207 if (ir_context->GetStructuredCFGAnalysis()->IsContinueBlock(block->id())) {
208 return false;
209 }
210
211 // Check that the block is not a loop header.
212 if (block->IsLoopHeader()) {
213 return false;
214 }
215
216 // Check all the fresh ids.
217 std::set<uint32_t> fresh_ids_used;
218 for (uint32_t id : {message_.syn_id(), message_.loop_id(), message_.ctr_id(),
219 message_.temp_id(), message_.eventual_syn_id(),
220 message_.incremented_ctr_id(), message_.cond_id()}) {
221 if (!id || !CheckIdIsFreshAndNotUsedByThisTransformation(id, ir_context,
222 &fresh_ids_used)) {
223 return false;
224 }
225 }
226
227 // Check the additional block id if it is non-zero.
228 return !message_.additional_block_id() ||
229 CheckIdIsFreshAndNotUsedByThisTransformation(
230 message_.additional_block_id(), ir_context, &fresh_ids_used);
231 }
232
Apply(opt::IRContext * ir_context,TransformationContext * transformation_context) const233 void TransformationAddLoopToCreateIntConstantSynonym::Apply(
234 opt::IRContext* ir_context,
235 TransformationContext* transformation_context) const {
236 // Find 32-bit signed integer constants 0 and 1.
237 uint32_t const_0_id = fuzzerutil::MaybeGetIntegerConstant(
238 ir_context, *transformation_context, {0}, 32, true, false);
239 auto const_0_def = ir_context->get_def_use_mgr()->GetDef(const_0_id);
240 uint32_t const_1_id = fuzzerutil::MaybeGetIntegerConstant(
241 ir_context, *transformation_context, {1}, 32, true, false);
242
243 // Retrieve the instruction defining the initial value constant.
244 auto initial_val_def =
245 ir_context->get_def_use_mgr()->GetDef(message_.initial_val_id());
246
247 // Retrieve the block before which we want to insert the loop.
248 auto block_after_loop =
249 ir_context->get_instr_block(message_.block_after_loop_id());
250
251 // Find the predecessor of the block.
252 uint32_t pred_id =
253 ir_context->cfg()->preds(message_.block_after_loop_id())[0];
254
255 // Get the id for the last block in the new loop. It will be
256 // |message_.additional_block_id| if this is non_zero, |message_.loop_id|
257 // otherwise.
258 uint32_t last_loop_block_id = message_.additional_block_id()
259 ? message_.additional_block_id()
260 : message_.loop_id();
261
262 // Create the loop header block.
263 std::unique_ptr<opt::BasicBlock> loop_block =
264 MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
265 ir_context, SpvOpLabel, 0, message_.loop_id(),
266 opt::Instruction::OperandList{}));
267
268 // Add OpPhi instructions to retrieve the current value of the counter and of
269 // the temporary variable that will be decreased at each operation.
270 loop_block->AddInstruction(MakeUnique<opt::Instruction>(
271 ir_context, SpvOpPhi, const_0_def->type_id(), message_.ctr_id(),
272 opt::Instruction::OperandList{
273 {SPV_OPERAND_TYPE_ID, {const_0_id}},
274 {SPV_OPERAND_TYPE_ID, {pred_id}},
275 {SPV_OPERAND_TYPE_ID, {message_.incremented_ctr_id()}},
276 {SPV_OPERAND_TYPE_ID, {last_loop_block_id}}}));
277
278 loop_block->AddInstruction(MakeUnique<opt::Instruction>(
279 ir_context, SpvOpPhi, initial_val_def->type_id(), message_.temp_id(),
280 opt::Instruction::OperandList{
281 {SPV_OPERAND_TYPE_ID, {message_.initial_val_id()}},
282 {SPV_OPERAND_TYPE_ID, {pred_id}},
283 {SPV_OPERAND_TYPE_ID, {message_.eventual_syn_id()}},
284 {SPV_OPERAND_TYPE_ID, {last_loop_block_id}}}));
285
286 // Collect the other instructions in a list. These will be added to an
287 // additional block if |message_.additional_block_id| is defined, to the loop
288 // header otherwise.
289 std::vector<std::unique_ptr<opt::Instruction>> other_instructions;
290
291 // Add an instruction to subtract the step value from the temporary value.
292 // The value of this id will converge to the constant in the last iteration.
293 other_instructions.push_back(MakeUnique<opt::Instruction>(
294 ir_context, SpvOpISub, initial_val_def->type_id(),
295 message_.eventual_syn_id(),
296 opt::Instruction::OperandList{
297 {SPV_OPERAND_TYPE_ID, {message_.temp_id()}},
298 {SPV_OPERAND_TYPE_ID, {message_.step_val_id()}}}));
299
300 // Add an instruction to increment the counter.
301 other_instructions.push_back(MakeUnique<opt::Instruction>(
302 ir_context, SpvOpIAdd, const_0_def->type_id(),
303 message_.incremented_ctr_id(),
304 opt::Instruction::OperandList{{SPV_OPERAND_TYPE_ID, {message_.ctr_id()}},
305 {SPV_OPERAND_TYPE_ID, {const_1_id}}}));
306
307 // Add an instruction to decide whether the condition holds.
308 other_instructions.push_back(MakeUnique<opt::Instruction>(
309 ir_context, SpvOpSLessThan, fuzzerutil::MaybeGetBoolType(ir_context),
310 message_.cond_id(),
311 opt::Instruction::OperandList{
312 {SPV_OPERAND_TYPE_ID, {message_.incremented_ctr_id()}},
313 {SPV_OPERAND_TYPE_ID, {message_.num_iterations_id()}}}));
314
315 // Define the OpLoopMerge instruction for the loop header. The merge block is
316 // the existing block, the continue block is the last block in the loop
317 // (either the loop itself or the additional block).
318 std::unique_ptr<opt::Instruction> merge_inst = MakeUnique<opt::Instruction>(
319 ir_context, SpvOpLoopMerge, 0, 0,
320 opt::Instruction::OperandList{
321 {SPV_OPERAND_TYPE_ID, {message_.block_after_loop_id()}},
322 {SPV_OPERAND_TYPE_ID, {last_loop_block_id}},
323 {SPV_OPERAND_TYPE_LOOP_CONTROL, {SpvLoopControlMaskNone}}});
324
325 // Define a conditional branch instruction, branching to the loop header if
326 // the condition holds, and to the existing block otherwise. This instruction
327 // will be added to the last block in the loop.
328 std::unique_ptr<opt::Instruction> conditional_branch =
329 MakeUnique<opt::Instruction>(
330 ir_context, SpvOpBranchConditional, 0, 0,
331 opt::Instruction::OperandList{
332 {SPV_OPERAND_TYPE_ID, {message_.cond_id()}},
333 {SPV_OPERAND_TYPE_ID, {message_.loop_id()}},
334 {SPV_OPERAND_TYPE_ID, {message_.block_after_loop_id()}}});
335
336 if (message_.additional_block_id()) {
337 // If an id for the additional block is specified, create an additional
338 // block, containing the instructions in the list and a branching
339 // instruction.
340
341 std::unique_ptr<opt::BasicBlock> additional_block =
342 MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
343 ir_context, SpvOpLabel, 0, message_.additional_block_id(),
344 opt::Instruction::OperandList{}));
345
346 for (auto& instruction : other_instructions) {
347 additional_block->AddInstruction(std::move(instruction));
348 }
349
350 additional_block->AddInstruction(std::move(conditional_branch));
351
352 // Add the merge instruction to the header.
353 loop_block->AddInstruction(std::move(merge_inst));
354
355 // Add an unconditional branch from the header to the additional block.
356 loop_block->AddInstruction(MakeUnique<opt::Instruction>(
357 ir_context, SpvOpBranch, 0, 0,
358 opt::Instruction::OperandList{
359 {SPV_OPERAND_TYPE_ID, {message_.additional_block_id()}}}));
360
361 // Insert the two loop blocks before the existing block.
362 block_after_loop->GetParent()->InsertBasicBlockBefore(std::move(loop_block),
363 block_after_loop);
364 block_after_loop->GetParent()->InsertBasicBlockBefore(
365 std::move(additional_block), block_after_loop);
366 } else {
367 // If no id for an additional block is specified, the loop will only be made
368 // up of one block, so we need to add all the instructions to it.
369
370 for (auto& instruction : other_instructions) {
371 loop_block->AddInstruction(std::move(instruction));
372 }
373
374 // Add the merge and conditional branch instructions.
375 loop_block->AddInstruction(std::move(merge_inst));
376 loop_block->AddInstruction(std::move(conditional_branch));
377
378 // Insert the header before the existing block.
379 block_after_loop->GetParent()->InsertBasicBlockBefore(std::move(loop_block),
380 block_after_loop);
381 }
382
383 // Update the branching instructions leading to this block.
384 ir_context->get_def_use_mgr()->ForEachUse(
385 message_.block_after_loop_id(),
386 [this](opt::Instruction* instruction, uint32_t operand_index) {
387 assert(instruction->opcode() != SpvOpLoopMerge &&
388 instruction->opcode() != SpvOpSelectionMerge &&
389 "The block should not be referenced by OpLoopMerge or "
390 "OpSelectionMerge, by construction.");
391 // Replace all uses of the label inside branch instructions.
392 if (instruction->opcode() == SpvOpBranch ||
393 instruction->opcode() == SpvOpBranchConditional ||
394 instruction->opcode() == SpvOpSwitch) {
395 instruction->SetOperand(operand_index, {message_.loop_id()});
396 }
397 });
398
399 // Update all the OpPhi instructions in the block after the loop: its
400 // predecessor is now the last block in the loop.
401 block_after_loop->ForEachPhiInst(
402 [last_loop_block_id](opt::Instruction* phi_inst) {
403 // Since the block only had one predecessor, the id of the predecessor
404 // is input operand 1.
405 phi_inst->SetInOperand(1, {last_loop_block_id});
406 });
407
408 // Add a new OpPhi instruction at the beginning of the block after the loop,
409 // defining the synonym of the constant. The type id will be the same as
410 // |message_.initial_value_id|, since this is the value that is decremented in
411 // the loop.
412 block_after_loop->begin()->InsertBefore(MakeUnique<opt::Instruction>(
413 ir_context, SpvOpPhi, initial_val_def->type_id(), message_.syn_id(),
414 opt::Instruction::OperandList{
415 {SPV_OPERAND_TYPE_ID, {message_.eventual_syn_id()}},
416 {SPV_OPERAND_TYPE_ID, {last_loop_block_id}}}));
417
418 // Update the module id bound with all the fresh ids used.
419 for (uint32_t id : {message_.syn_id(), message_.loop_id(), message_.ctr_id(),
420 message_.temp_id(), message_.eventual_syn_id(),
421 message_.incremented_ctr_id(), message_.cond_id(),
422 message_.cond_id(), message_.additional_block_id()}) {
423 fuzzerutil::UpdateModuleIdBound(ir_context, id);
424 }
425
426 // Since we changed the structure of the module, we need to invalidate all the
427 // analyses.
428 ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
429
430 // Record that |message_.syn_id| is synonymous with |message_.constant_id|.
431 transformation_context->GetFactManager()->AddFactDataSynonym(
432 MakeDataDescriptor(message_.syn_id(), {}),
433 MakeDataDescriptor(message_.constant_id(), {}));
434 }
435
436 protobufs::Transformation
ToMessage() const437 TransformationAddLoopToCreateIntConstantSynonym::ToMessage() const {
438 protobufs::Transformation result;
439 *result.mutable_add_loop_to_create_int_constant_synonym() = message_;
440 return result;
441 }
442
443 std::unordered_set<uint32_t>
GetFreshIds() const444 TransformationAddLoopToCreateIntConstantSynonym::GetFreshIds() const {
445 return {message_.syn_id(), message_.loop_id(),
446 message_.ctr_id(), message_.temp_id(),
447 message_.eventual_syn_id(), message_.incremented_ctr_id(),
448 message_.cond_id(), message_.additional_block_id()};
449 }
450
451 } // namespace fuzz
452 } // namespace spvtools
453