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