1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
// Copyright (c) 2020 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h"
#include <algorithm>
#include <vector>
#include "source/fuzz/fuzzer_util.h"
#include "source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h"
namespace spvtools {
namespace fuzz {
FuzzerPassReplaceBranchesFromDeadBlocksWithExits::
FuzzerPassReplaceBranchesFromDeadBlocksWithExits(
opt::IRContext* ir_context,
TransformationContext* transformation_context,
FuzzerContext* fuzzer_context,
protobufs::TransformationSequence* transformations,
bool ignore_inapplicable_transformations)
: FuzzerPass(ir_context, transformation_context, fuzzer_context,
transformations, ignore_inapplicable_transformations) {}
void FuzzerPassReplaceBranchesFromDeadBlocksWithExits::Apply() {
// OpKill can only be used as a terminator in a function that is guaranteed
// to be executed with the Fragment execution model. We conservatively only
// allow OpKill if every entry point in the module has the Fragment execution
// model.
auto fragment_execution_model_guaranteed =
std::all_of(GetIRContext()->module()->entry_points().begin(),
GetIRContext()->module()->entry_points().end(),
[](const opt::Instruction& entry_point) -> bool {
return entry_point.GetSingleWordInOperand(0) ==
SpvExecutionModelFragment;
});
// Transformations of this type can disable one another. To avoid ordering
// bias, we therefore build a set of candidate transformations to apply, and
// subsequently apply them in a random order, skipping any that cease to be
// applicable.
std::vector<TransformationReplaceBranchFromDeadBlockWithExit>
candidate_transformations;
// Consider every block in every function.
for (auto& function : *GetIRContext()->module()) {
for (auto& block : function) {
// Probabilistically decide whether to skip this block.
if (GetFuzzerContext()->ChoosePercentage(
GetFuzzerContext()
->GetChanceOfReplacingBranchFromDeadBlockWithExit())) {
continue;
}
// Check whether the block is suitable for having its terminator replaced.
if (!TransformationReplaceBranchFromDeadBlockWithExit::BlockIsSuitable(
GetIRContext(), *GetTransformationContext(), block)) {
continue;
}
// We can always use OpUnreachable to replace a block's terminator.
// Whether we can use OpKill depends on the execution model, and which of
// OpReturn and OpReturnValue we can use depends on the return type of the
// enclosing function.
std::vector<SpvOp> opcodes = {SpvOpUnreachable};
if (fragment_execution_model_guaranteed) {
opcodes.emplace_back(SpvOpKill);
}
auto function_return_type =
GetIRContext()->get_type_mgr()->GetType(function.type_id());
if (function_return_type->AsVoid()) {
opcodes.emplace_back(SpvOpReturn);
} else if (fuzzerutil::CanCreateConstant(GetIRContext(),
function.type_id())) {
// For simplicity we only allow OpReturnValue if the function return
// type is a type for which we can create a constant. This allows us a
// zero of the given type as a default return value.
opcodes.emplace_back(SpvOpReturnValue);
}
// Choose one of the available terminator opcodes at random and create a
// candidate transformation.
auto opcode = opcodes[GetFuzzerContext()->RandomIndex(opcodes)];
candidate_transformations.emplace_back(
TransformationReplaceBranchFromDeadBlockWithExit(
block.id(), opcode,
opcode == SpvOpReturnValue
? FindOrCreateZeroConstant(function.type_id(), true)
: 0));
}
}
// Process the candidate transformations in a random order.
while (!candidate_transformations.empty()) {
// Transformations of this type can disable one another. For example,
// suppose we have dead blocks A, B, C, D arranged as follows:
//
// A |
// / \ |
// B C |
// \ / |
// D |
//
// Here we can replace the terminator of either B or C with an early exit,
// because D has two predecessors. But if we replace the terminator of B,
// say, we get:
//
// A |
// / \ |
// B C |
// / |
// D |
//
// and now it is no longer OK to replace the terminator of C as D only has
// one predecessor and we do not want to make D unreachable in the control
// flow graph.
MaybeApplyTransformation(
GetFuzzerContext()->RemoveAtRandomIndex(&candidate_transformations));
}
}
} // namespace fuzz
} // namespace spvtools
|
