1 // Copyright (c) 2019 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_permute_blocks.h"
16
17 #include "source/fuzz/transformation_move_block_down.h"
18
19 namespace spvtools {
20 namespace fuzz {
21
FuzzerPassPermuteBlocks(opt::IRContext * ir_context,TransformationContext * transformation_context,FuzzerContext * fuzzer_context,protobufs::TransformationSequence * transformations)22 FuzzerPassPermuteBlocks::FuzzerPassPermuteBlocks(
23 opt::IRContext* ir_context, TransformationContext* transformation_context,
24 FuzzerContext* fuzzer_context,
25 protobufs::TransformationSequence* transformations)
26 : FuzzerPass(ir_context, transformation_context, fuzzer_context,
27 transformations) {}
28
Apply()29 void FuzzerPassPermuteBlocks::Apply() {
30 // For now we do something very simple: we randomly decide whether to move a
31 // block, and for each block that we do move, we push it down as far as we
32 // legally can.
33 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2635): it would be
34 // nice to randomly sample from the set of legal block permutations and then
35 // encode the chosen permutation via a series of move-block-down
36 // transformations. This should be possible but will require some thought.
37
38 for (auto& function : *GetIRContext()->module()) {
39 std::vector<uint32_t> block_ids;
40 // Collect all block ids for the function before messing with block
41 // ordering.
42 for (auto& block : function) {
43 block_ids.push_back(block.id());
44 }
45 // Now consider each block id. We consider block ids in reverse, because
46 // e.g. in code generated from the following:
47 //
48 // if (...) {
49 // A
50 // B
51 // } else {
52 // C
53 // }
54 //
55 // block A cannot be moved down, but B has freedom to move and that movement
56 // would provide more freedom for A to move.
57 for (auto id = block_ids.rbegin(); id != block_ids.rend(); ++id) {
58 // Randomly decide whether to ignore the block id.
59 if (!GetFuzzerContext()->ChoosePercentage(
60 GetFuzzerContext()->GetChanceOfMovingBlockDown())) {
61 continue;
62 }
63 // Keep pushing the block down, until pushing down fails.
64 // The loop is guaranteed to terminate because a block cannot be pushed
65 // down indefinitely.
66 while (true) {
67 TransformationMoveBlockDown transformation(*id);
68 if (!MaybeApplyTransformation(transformation)) {
69 break;
70 }
71 }
72 }
73 }
74 }
75
76 } // namespace fuzz
77 } // namespace spvtools
78