1 // Copyright (c) 2020 Vasyl Teliman
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_wrap_regions_in_selections.h"
16
17 #include "source/fuzz/fuzzer_context.h"
18 #include "source/fuzz/instruction_descriptor.h"
19 #include "source/fuzz/transformation_split_block.h"
20 #include "source/fuzz/transformation_wrap_region_in_selection.h"
21
22 namespace spvtools {
23 namespace fuzz {
24
FuzzerPassWrapRegionsInSelections(opt::IRContext * ir_context,TransformationContext * transformation_context,FuzzerContext * fuzzer_context,protobufs::TransformationSequence * transformations)25 FuzzerPassWrapRegionsInSelections::FuzzerPassWrapRegionsInSelections(
26 opt::IRContext* ir_context, TransformationContext* transformation_context,
27 FuzzerContext* fuzzer_context,
28 protobufs::TransformationSequence* transformations)
29 : FuzzerPass(ir_context, transformation_context, fuzzer_context,
30 transformations) {}
31
Apply()32 void FuzzerPassWrapRegionsInSelections::Apply() {
33 for (auto& function : *GetIRContext()->module()) {
34 if (!GetFuzzerContext()->ChoosePercentage(
35 GetFuzzerContext()->GetChanceOfWrappingRegionInSelection())) {
36 continue;
37 }
38
39 // It is easier to select an element at random from a vector than from an
40 // instruction list.
41 std::vector<opt::BasicBlock*> header_block_candidates;
42 for (auto& block : function) {
43 header_block_candidates.push_back(&block);
44 }
45
46 if (header_block_candidates.empty()) {
47 continue;
48 }
49
50 // Try to get a header block candidate that will increase the chances of the
51 // transformation being applicable.
52 auto* header_block_candidate = MaybeGetHeaderBlockCandidate(
53 header_block_candidates[GetFuzzerContext()->RandomIndex(
54 header_block_candidates)]);
55 if (!header_block_candidate) {
56 continue;
57 }
58
59 std::vector<opt::BasicBlock*> merge_block_candidates;
60 for (auto& block : function) {
61 if (GetIRContext()->GetDominatorAnalysis(&function)->StrictlyDominates(
62 header_block_candidate, &block) &&
63 GetIRContext()
64 ->GetPostDominatorAnalysis(&function)
65 ->StrictlyDominates(&block, header_block_candidate)) {
66 merge_block_candidates.push_back(&block);
67 }
68 }
69
70 if (merge_block_candidates.empty()) {
71 continue;
72 }
73
74 // Try to get a merge block candidate that will increase the chances of the
75 // transformation being applicable.
76 auto* merge_block_candidate = MaybeGetMergeBlockCandidate(
77 merge_block_candidates[GetFuzzerContext()->RandomIndex(
78 merge_block_candidates)]);
79 if (!merge_block_candidate) {
80 continue;
81 }
82
83 if (!TransformationWrapRegionInSelection::IsApplicableToBlockRange(
84 GetIRContext(), header_block_candidate->id(),
85 merge_block_candidate->id())) {
86 continue;
87 }
88
89 // This boolean constant will be used as a condition for the
90 // OpBranchConditional instruction. We mark it as irrelevant to be able to
91 // replace it with a more interesting value later.
92 auto branch_condition = GetFuzzerContext()->ChooseEven();
93 FindOrCreateBoolConstant(branch_condition, true);
94
95 ApplyTransformation(TransformationWrapRegionInSelection(
96 header_block_candidate->id(), merge_block_candidate->id(),
97 branch_condition));
98 }
99 }
100
101 opt::BasicBlock*
MaybeGetHeaderBlockCandidate(opt::BasicBlock * header_block_candidate)102 FuzzerPassWrapRegionsInSelections::MaybeGetHeaderBlockCandidate(
103 opt::BasicBlock* header_block_candidate) {
104 // Try to create a preheader if |header_block_candidate| is a loop header.
105 if (header_block_candidate->IsLoopHeader()) {
106 // GetOrCreateSimpleLoopPreheader only supports reachable blocks.
107 return GetIRContext()->cfg()->preds(header_block_candidate->id()).size() ==
108 1
109 ? nullptr
110 : GetOrCreateSimpleLoopPreheader(header_block_candidate->id());
111 }
112
113 // Try to split |header_block_candidate| if it's already a header block.
114 if (header_block_candidate->GetMergeInst()) {
115 SplitBlockAfterOpPhiOrOpVariable(header_block_candidate->id());
116 }
117
118 return header_block_candidate;
119 }
120
MaybeGetMergeBlockCandidate(opt::BasicBlock * merge_block_candidate)121 opt::BasicBlock* FuzzerPassWrapRegionsInSelections::MaybeGetMergeBlockCandidate(
122 opt::BasicBlock* merge_block_candidate) {
123 // If |merge_block_candidate| is a merge block of some construct, try to split
124 // it and return a newly created block.
125 if (GetIRContext()->GetStructuredCFGAnalysis()->IsMergeBlock(
126 merge_block_candidate->id())) {
127 // We can't split a merge block if it's also a loop header.
128 return merge_block_candidate->IsLoopHeader()
129 ? nullptr
130 : SplitBlockAfterOpPhiOrOpVariable(merge_block_candidate->id());
131 }
132
133 return merge_block_candidate;
134 }
135
136 } // namespace fuzz
137 } // namespace spvtools
138