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