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