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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
// Copyright (c) 2021 Alastair F. Donaldson
//
// 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/available_instructions.h"
#include "source/fuzz/fuzzer_util.h"
namespace spvtools {
namespace fuzz {
AvailableInstructions::AvailableInstructions(
opt::IRContext* ir_context,
const std::function<bool(opt::IRContext*, opt::Instruction*)>& predicate)
: ir_context_(ir_context) {
// Consider all global declarations
for (auto& global : ir_context->module()->types_values()) {
if (predicate(ir_context, &global)) {
available_globals_.push_back(&global);
}
}
// Consider every function
for (auto& function : *ir_context->module()) {
// Identify those function parameters that satisfy the predicate.
std::vector<opt::Instruction*> available_params_for_function;
function.ForEachParam(
[&predicate, ir_context,
&available_params_for_function](opt::Instruction* param) {
if (predicate(ir_context, param)) {
available_params_for_function.push_back(param);
}
});
// Consider every reachable block in the function.
auto dominator_analysis = ir_context->GetDominatorAnalysis(&function);
for (auto& block : function) {
if (!ir_context->IsReachable(block)) {
// The block is not reachable.
continue;
}
if (&block == &*function.begin()) {
// The function entry block is special: only the relevant globals and
// function parameters are available at its entry point.
num_available_at_block_entry_.insert(
{&block,
static_cast<uint32_t>(available_params_for_function.size() +
available_globals_.size())});
} else {
// |block| is not the entry block and is reachable, so it must have an
// immediate dominator. The number of instructions available on entry to
// |block| is thus the number of instructions available on entry to the
// immediate dominator + the number of instructions generated_by_block
// by the immediate dominator.
auto immediate_dominator =
dominator_analysis->ImmediateDominator(&block);
assert(immediate_dominator != nullptr &&
"The block is reachable so should have an immediate dominator.");
assert(generated_by_block_.count(immediate_dominator) != 0 &&
"Immediate dominator should have already been processed.");
assert(num_available_at_block_entry_.count(immediate_dominator) != 0 &&
"Immediate dominator should have already been processed.");
num_available_at_block_entry_.insert(
{&block,
static_cast<uint32_t>(
generated_by_block_.at(immediate_dominator).size()) +
num_available_at_block_entry_.at(immediate_dominator)});
}
// Now consider each instruction in the block.
std::vector<opt::Instruction*> generated_by_block;
for (auto& inst : block) {
assert(num_available_at_block_entry_.count(&block) != 0 &&
"Block should have already been processed.");
// The number of available instructions before |inst| is the number
// available at the start of the block + the number of relevant
// instructions generated by the block so far.
num_available_before_instruction_.insert(
{&inst, num_available_at_block_entry_.at(&block) +
static_cast<uint32_t>(generated_by_block.size())});
if (predicate(ir_context, &inst)) {
// This instruction satisfies the predicate, so note that it is
// generated by |block|.
generated_by_block.push_back(&inst);
}
}
generated_by_block_.emplace(&block, std::move(generated_by_block));
}
available_params_.emplace(&function,
std::move(available_params_for_function));
}
}
AvailableInstructions::AvailableBeforeInstruction
AvailableInstructions::GetAvailableBeforeInstruction(
opt::Instruction* inst) const {
assert(num_available_before_instruction_.count(inst) != 0 &&
"Availability can only be queried for reachable instructions.");
return {*this, inst};
}
AvailableInstructions::AvailableBeforeInstruction::AvailableBeforeInstruction(
const AvailableInstructions& available_instructions, opt::Instruction* inst)
: available_instructions_(available_instructions), inst_(inst) {}
uint32_t AvailableInstructions::AvailableBeforeInstruction::size() const {
return available_instructions_.num_available_before_instruction_.at(inst_);
}
bool AvailableInstructions::AvailableBeforeInstruction::empty() const {
return size() == 0;
}
opt::Instruction* AvailableInstructions::AvailableBeforeInstruction::operator[](
uint32_t index) const {
assert(index < size() && "Index out of bounds.");
// First, check the cache to see whether we can return the available
// instruction in constant time.
auto cached_result = index_cache.find(index);
if (cached_result != index_cache.end()) {
return cached_result->second;
}
// Next check whether the index falls into the global region.
if (index < available_instructions_.available_globals_.size()) {
auto result = available_instructions_.available_globals_[index];
index_cache.insert({index, result});
return result;
}
auto block = available_instructions_.ir_context_->get_instr_block(inst_);
auto function = block->GetParent();
// Next check whether the index falls into the available instructions that
// correspond to function parameters.
if (index <
available_instructions_.available_globals_.size() +
available_instructions_.available_params_.at(function).size()) {
auto result = available_instructions_.available_params_.at(
function)[index - available_instructions_.available_globals_.size()];
index_cache.insert({index, result});
return result;
}
auto dominator_analysis =
available_instructions_.ir_context_->GetDominatorAnalysis(function);
// Now the expensive part (which is why we have the cache): walk the dominator
// tree backwards starting from the block containing |inst_| until we get to
// the block in which the instruction corresponding to |index| exists.
for (auto* ancestor = block; true;
ancestor = dominator_analysis->ImmediateDominator(ancestor)) {
uint32_t num_available_at_ancestor_entry =
available_instructions_.num_available_at_block_entry_.at(ancestor);
if (index_cache.count(num_available_at_ancestor_entry) == 0) {
// This is the first time we have traversed this block, so we populate the
// cache with the index of each instruction, so that if a future index
// query relates to indices associated with this block we can return the
// result in constant time.
auto& generated_by_ancestor =
available_instructions_.generated_by_block_.at(ancestor);
for (uint32_t local_index = 0; local_index < generated_by_ancestor.size();
local_index++) {
index_cache.insert({num_available_at_ancestor_entry + local_index,
generated_by_ancestor[local_index]});
}
}
if (index >= num_available_at_ancestor_entry) {
// This block contains the instruction we want, so by now it will be in
// the cache.
return index_cache.at(index);
}
assert(ancestor != &*function->begin() &&
"By construction we should find a block associated with the index.");
}
assert(false && "Unreachable.");
return nullptr;
}
} // namespace fuzz
} // namespace spvtools
|
