spirv-fuzz: Manage available instructions efficiently (#4177)
Introduces a data structure for efficient management of available
instructions in the fuzzer.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index d3aa9f1..804fcf0 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -37,6 +37,7 @@
set(SPIRV_TOOLS_FUZZ_SOURCES
added_function_reducer.h
+ available_instructions.h
call_graph.h
comparator_deep_blocks_first.h
counter_overflow_id_source.h
@@ -229,6 +230,7 @@
${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.h
added_function_reducer.cpp
+ available_instructions.cpp
call_graph.cpp
counter_overflow_id_source.cpp
data_descriptor.cpp
diff --git a/source/fuzz/available_instructions.cpp b/source/fuzz/available_instructions.cpp
new file mode 100644
index 0000000..e25ed90
--- /dev/null
+++ b/source/fuzz/available_instructions.cpp
@@ -0,0 +1,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 (!fuzzerutil::BlockIsReachableInItsFunction(ir_context, &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
diff --git a/source/fuzz/available_instructions.h b/source/fuzz/available_instructions.h
new file mode 100644
index 0000000..5c0b417
--- /dev/null
+++ b/source/fuzz/available_instructions.h
@@ -0,0 +1,111 @@
+// 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.
+
+#ifndef SOURCE_FUZZ_AVAILABLE_INSTRUCTIONS_H_
+#define SOURCE_FUZZ_AVAILABLE_INSTRUCTIONS_H_
+
+#include <unordered_map>
+#include <vector>
+
+#include "source/opt/instruction.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// A class for allowing efficient querying of the instruction that satisfy a
+// particular predicate that are available before a given instruction.
+// Availability information is only computed for instructions in *reachable*
+// basic blocks.
+class AvailableInstructions {
+ public:
+ // The outer class captures availability information for a whole module, and
+ // each instance of this inner class captures availability for a particular
+ // instruction.
+ class AvailableBeforeInstruction {
+ public:
+ AvailableBeforeInstruction(
+ const AvailableInstructions& available_instructions,
+ opt::Instruction* inst);
+
+ // Returns the number of instructions that are available before the
+ // instruction associated with this class.
+ uint32_t size() const;
+
+ // Returns true if and only if |size()| is 0.
+ bool empty() const;
+
+ // Requires |index| < |size()|. Returns the ith available instruction.
+ opt::Instruction* operator[](uint32_t index) const;
+
+ private:
+ // A references to an instance of the outer class.
+ const AvailableInstructions& available_instructions_;
+
+ // The instruction for which availability information is captured.
+ opt::Instruction* inst_;
+
+ // A cache to improve the efficiency of the [] operator. The [] operator
+ // requires walking the instruction's dominator tree to find an instruction
+ // at a particular index, which is a linear time operation. By inserting all
+ // instructions that are traversed during this search into a cache, future
+ // lookups will take constant time unless they require traversing the
+ // dominator tree more deeply.
+ mutable std::unordered_map<uint32_t, opt::Instruction*> index_cache;
+ };
+
+ // Constructs availability instructions for |ir_context|, where instructions
+ // are only available if they satisfy |predicate|.
+ AvailableInstructions(
+ opt::IRContext* ir_context,
+ const std::function<bool(opt::IRContext*, opt::Instruction*)>& predicate);
+
+ // Yields instruction availability for |inst|.
+ AvailableBeforeInstruction GetAvailableBeforeInstruction(
+ opt::Instruction* inst) const;
+
+ private:
+ // The module in which all instructions are contained.
+ opt::IRContext* ir_context_;
+
+ // The global instructions that satisfy the predicate.
+ std::vector<opt::Instruction*> available_globals_;
+
+ // Per function, the parameters that satisfy the predicate.
+ std::unordered_map<opt::Function*, std::vector<opt::Instruction*>>
+ available_params_;
+
+ // The number of instructions that satisfy the predicate and that are
+ // available at the entry to a block. For the entry block of a function this
+ // is the number of available globals + the number of available function
+ // parameters. For any other block it is the number of available instructions
+ // for the blocks immediate dominator + the number of instructions generated
+ // by the immediate dominator.
+ std::unordered_map<opt::BasicBlock*, uint32_t> num_available_at_block_entry_;
+
+ // For each block this records those instructions in the block that satisfy
+ // the predicate.
+ std::unordered_map<opt::BasicBlock*, std::vector<opt::Instruction*>>
+ generated_by_block_;
+
+ // For each instruction this records how many instructions satisfying the
+ // predicate are available before the instruction.
+ std::unordered_map<opt::Instruction*, uint32_t>
+ num_available_before_instruction_;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_AVAILABLE_INSTRUCTIONS_H_
diff --git a/source/fuzz/fuzzer_pass_add_composite_extract.cpp b/source/fuzz/fuzzer_pass_add_composite_extract.cpp
index 132a49d..46cb42e 100644
--- a/source/fuzz/fuzzer_pass_add_composite_extract.cpp
+++ b/source/fuzz/fuzzer_pass_add_composite_extract.cpp
@@ -14,6 +14,7 @@
#include "source/fuzz/fuzzer_pass_add_composite_extract.h"
+#include "source/fuzz/available_instructions.h"
#include "source/fuzz/fuzzer_context.h"
#include "source/fuzz/fuzzer_util.h"
#include "source/fuzz/instruction_descriptor.h"
@@ -41,14 +42,16 @@
}
}
- // We don't want to invalidate the module every time we apply this
- // transformation since rebuilding DominatorAnalysis can be expensive, so we
- // collect up the transformations we wish to apply and apply them all later.
- std::vector<TransformationCompositeExtract> transformations;
+ AvailableInstructions available_composites(
+ GetIRContext(), [](opt::IRContext* ir_context, opt::Instruction* inst) {
+ return inst->type_id() && inst->result_id() &&
+ fuzzerutil::IsCompositeType(
+ ir_context->get_type_mgr()->GetType(inst->type_id()));
+ });
ForEachInstructionWithInstructionDescriptor(
- [this, &composite_synonyms, &transformations](
- opt::Function* function, opt::BasicBlock* block,
+ [this, &available_composites, &composite_synonyms](
+ opt::Function* /*unused*/, opt::BasicBlock* /*unused*/,
opt::BasicBlock::iterator inst_it,
const protobufs::InstructionDescriptor& instruction_descriptor) {
if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(SpvOpCompositeExtract,
@@ -61,14 +64,6 @@
return;
}
- auto available_composites = FindAvailableInstructions(
- function, block, inst_it,
- [](opt::IRContext* ir_context, opt::Instruction* inst) {
- return inst->type_id() && inst->result_id() &&
- fuzzerutil::IsCompositeType(
- ir_context->get_type_mgr()->GetType(inst->type_id()));
- });
-
std::vector<const protobufs::DataDescriptor*> available_synonyms;
for (const auto* dd : composite_synonyms) {
if (fuzzerutil::IdIsAvailableBeforeInstruction(
@@ -77,18 +72,21 @@
}
}
- if (available_synonyms.empty() && available_composites.empty()) {
+ auto candidate_composites =
+ available_composites.GetAvailableBeforeInstruction(&*inst_it);
+
+ if (available_synonyms.empty() && candidate_composites.empty()) {
return;
}
uint32_t composite_id = 0;
std::vector<uint32_t> indices;
- if (available_synonyms.empty() || (!available_composites.empty() &&
+ if (available_synonyms.empty() || (!candidate_composites.empty() &&
GetFuzzerContext()->ChooseEven())) {
const auto* inst =
- available_composites[GetFuzzerContext()->RandomIndex(
- available_composites)];
+ candidate_composites[GetFuzzerContext()->RandomIndex(
+ candidate_composites)];
composite_id = inst->result_id();
auto type_id = inst->type_id();
@@ -153,14 +151,10 @@
assert(composite_id != 0 && !indices.empty() &&
"Composite object should have been chosen correctly");
- transformations.emplace_back(instruction_descriptor,
- GetFuzzerContext()->GetFreshId(),
- composite_id, indices);
+ ApplyTransformation(TransformationCompositeExtract(
+ instruction_descriptor, GetFuzzerContext()->GetFreshId(),
+ composite_id, indices));
});
-
- for (const auto& transformation : transformations) {
- ApplyTransformation(transformation);
- }
}
} // namespace fuzz
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index 2e93293..56fbed8 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -17,6 +17,7 @@
set(SOURCES
fuzz_test_util.h
+ available_instructions_test.cpp
call_graph_test.cpp
comparator_deep_blocks_first_test.cpp
data_synonym_transformation_test.cpp
diff --git a/test/fuzz/available_instructions_test.cpp b/test/fuzz/available_instructions_test.cpp
new file mode 100644
index 0000000..dc8a3b5
--- /dev/null
+++ b/test/fuzz/available_instructions_test.cpp
@@ -0,0 +1,328 @@
+// 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 "gtest/gtest.h"
+#include "source/fuzz/fuzzer_util.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(AvailableInstructionsTest, BasicTest) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFloat 32
+ %9 = OpTypePointer Function %8
+ %10 = OpTypeFunction %6 %7 %9
+ %15 = OpTypeVector %8 2
+ %16 = OpTypePointer Private %15
+ %17 = OpVariable %16 Private
+ %18 = OpConstant %8 1
+ %19 = OpConstant %8 2
+ %20 = OpConstantComposite %15 %18 %19
+ %21 = OpTypeVector %8 4
+ %22 = OpTypePointer Private %21
+ %23 = OpVariable %22 Private
+ %24 = OpConstant %8 10
+ %25 = OpConstant %8 20
+ %26 = OpConstant %8 30
+ %27 = OpConstant %8 40
+ %28 = OpConstantComposite %21 %24 %25 %26 %27
+ %31 = OpTypeInt 32 0
+ %32 = OpConstant %31 0
+ %33 = OpTypePointer Private %8
+ %41 = OpTypeBool
+ %46 = OpConstant %6 1
+ %54 = OpConstant %6 10
+ %57 = OpConstant %31 3
+ %61 = OpConstant %6 0
+ %66 = OpConstant %6 3
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %55 = OpVariable %7 Function
+ %56 = OpVariable %9 Function
+ %65 = OpVariable %7 Function
+ %68 = OpVariable %7 Function
+ OpStore %17 %20
+ OpStore %23 %28
+ OpStore %55 %54
+ %58 = OpAccessChain %33 %23 %57
+ %59 = OpLoad %8 %58
+ OpStore %56 %59
+ %60 = OpFunctionCall %6 %13 %55 %56
+ %100 = OpCopyObject %21 %28
+ %62 = OpSGreaterThan %41 %60 %61
+ OpSelectionMerge %64 None
+ OpBranchConditional %62 %63 %67
+ %63 = OpLabel
+ OpStore %65 %66
+ %101 = OpCopyObject %21 %28
+ OpBranch %64
+ %67 = OpLabel
+ OpStore %68 %61
+ OpBranch %69
+ %69 = OpLabel
+ OpLoopMerge %71 %72 None
+ OpBranch %73
+ %73 = OpLabel
+ %74 = OpLoad %6 %68
+ %75 = OpSLessThan %41 %74 %54
+ OpBranchConditional %75 %70 %71
+ %70 = OpLabel
+ %76 = OpLoad %6 %65
+ %77 = OpIAdd %6 %76 %46
+ OpStore %65 %77
+ OpBranch %72
+ %72 = OpLabel
+ %78 = OpLoad %6 %68
+ %79 = OpIAdd %6 %78 %46
+ OpStore %68 %79
+ OpBranch %69
+ %71 = OpLabel
+ %102 = OpCopyObject %21 %28
+ OpBranch %64
+ %64 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %13 = OpFunction %6 None %10
+ %11 = OpFunctionParameter %7
+ %12 = OpFunctionParameter %9
+ %14 = OpLabel
+ %29 = OpVariable %7 Function
+ %30 = OpLoad %6 %11
+ %34 = OpAccessChain %33 %17 %32
+ %35 = OpLoad %8 %34
+ %36 = OpConvertFToS %6 %35
+ %37 = OpIAdd %6 %30 %36
+ OpStore %29 %37
+ %38 = OpLoad %6 %11
+ %39 = OpLoad %8 %12
+ %40 = OpConvertFToS %6 %39
+ %42 = OpSLessThan %41 %38 %40
+ %103 = OpCopyObject %21 %28
+ OpSelectionMerge %44 None
+ OpBranchConditional %42 %43 %48
+ %43 = OpLabel
+ %45 = OpLoad %6 %29
+ %47 = OpIAdd %6 %45 %46
+ OpStore %29 %47
+ OpBranch %44
+ %48 = OpLabel
+ %49 = OpLoad %6 %29
+ %50 = OpISub %6 %49 %46
+ OpStore %29 %50
+ OpBranch %44
+ %44 = OpLabel
+ %51 = OpLoad %6 %29
+ OpReturnValue %51
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ spvtools::ValidatorOptions validator_options;
+ ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+ kConsoleMessageConsumer));
+
+ opt::Instruction* i1 = context->get_def_use_mgr()->GetDef(55);
+ opt::Instruction* i2 = context->get_def_use_mgr()->GetDef(101);
+ opt::Instruction* i3 = &*context->cfg()->block(67)->begin();
+ opt::Instruction* i4 = context->get_def_use_mgr()->GetDef(74);
+ opt::Instruction* i5 = context->get_def_use_mgr()->GetDef(102);
+ opt::Instruction* i6 = context->get_def_use_mgr()->GetDef(30);
+ opt::Instruction* i7 = context->get_def_use_mgr()->GetDef(47);
+ opt::Instruction* i8 = context->get_def_use_mgr()->GetDef(50);
+ opt::Instruction* i9 = context->get_def_use_mgr()->GetDef(51);
+
+ {
+ AvailableInstructions no_instructions(
+ context.get(),
+ [](opt::IRContext*, opt::Instruction*) -> bool { return false; });
+ for (auto i : {i1, i2, i3, i4, i5, i6, i7, i8, i9}) {
+ auto available = no_instructions.GetAvailableBeforeInstruction(i);
+ ASSERT_EQ(0, available.size());
+ ASSERT_TRUE(available.empty());
+ }
+ }
+ {
+ AvailableInstructions all_instructions(
+ context.get(),
+ [](opt::IRContext*, opt::Instruction*) -> bool { return true; });
+ {
+ auto available = all_instructions.GetAvailableBeforeInstruction(i1);
+ ASSERT_FALSE(available.empty());
+ ASSERT_EQ(30, available.size());
+ ASSERT_EQ(SpvOpTypeVoid, available[0]->opcode());
+ ASSERT_EQ(SpvOpVariable, available[15]->opcode());
+ }
+ {
+ auto available = all_instructions.GetAvailableBeforeInstruction(i2);
+ ASSERT_FALSE(available.empty());
+ ASSERT_EQ(46, available.size());
+ ASSERT_EQ(SpvOpTypeVoid, available[0]->opcode());
+ ASSERT_EQ(SpvOpTypePointer, available[3]->opcode());
+ ASSERT_EQ(SpvOpVariable, available[15]->opcode());
+ ASSERT_EQ(SpvOpFunctionCall, available[40]->opcode());
+ ASSERT_EQ(SpvOpStore, available[45]->opcode());
+ }
+ {
+ auto available = all_instructions.GetAvailableBeforeInstruction(i3);
+ ASSERT_FALSE(available.empty());
+ ASSERT_EQ(45, available.size());
+ ASSERT_EQ(SpvOpTypeVoid, available[0]->opcode());
+ ASSERT_EQ(SpvOpTypePointer, available[3]->opcode());
+ ASSERT_EQ(SpvOpVariable, available[15]->opcode());
+ ASSERT_EQ(SpvOpFunctionCall, available[40]->opcode());
+ ASSERT_EQ(SpvOpBranchConditional, available[44]->opcode());
+ }
+ {
+ auto available = all_instructions.GetAvailableBeforeInstruction(i6);
+ ASSERT_FALSE(available.empty());
+ ASSERT_EQ(33, available.size());
+ ASSERT_EQ(SpvOpTypeVoid, available[0]->opcode());
+ ASSERT_EQ(SpvOpTypeFloat, available[4]->opcode());
+ ASSERT_EQ(SpvOpTypePointer, available[8]->opcode());
+ ASSERT_EQ(SpvOpConstantComposite, available[12]->opcode());
+ ASSERT_EQ(SpvOpConstant, available[16]->opcode());
+ ASSERT_EQ(SpvOpFunctionParameter, available[30]->opcode());
+ ASSERT_EQ(SpvOpFunctionParameter, available[31]->opcode());
+ ASSERT_EQ(SpvOpVariable, available[32]->opcode());
+ }
+ }
+ {
+ AvailableInstructions vector_instructions(
+ context.get(),
+ [](opt::IRContext* ir_context, opt::Instruction* inst) -> bool {
+ return inst->type_id() != 0 && ir_context->get_type_mgr()
+ ->GetType(inst->type_id())
+ ->AsVector() != nullptr;
+ });
+ {
+ auto available = vector_instructions.GetAvailableBeforeInstruction(i4);
+ ASSERT_FALSE(available.empty());
+ ASSERT_EQ(3, available.size());
+ ASSERT_EQ(SpvOpConstantComposite, available[0]->opcode());
+ ASSERT_EQ(SpvOpConstantComposite, available[1]->opcode());
+ ASSERT_EQ(SpvOpCopyObject, available[2]->opcode());
+ }
+ {
+ auto available = vector_instructions.GetAvailableBeforeInstruction(i5);
+ ASSERT_FALSE(available.empty());
+ ASSERT_EQ(3, available.size());
+ ASSERT_EQ(SpvOpConstantComposite, available[0]->opcode());
+ ASSERT_EQ(SpvOpConstantComposite, available[1]->opcode());
+ ASSERT_EQ(SpvOpCopyObject, available[2]->opcode());
+ }
+ {
+ auto available = vector_instructions.GetAvailableBeforeInstruction(i6);
+ ASSERT_FALSE(available.empty());
+ ASSERT_EQ(2, available.size());
+ ASSERT_EQ(SpvOpConstantComposite, available[0]->opcode());
+ ASSERT_EQ(SpvOpConstantComposite, available[1]->opcode());
+ }
+ }
+ {
+ AvailableInstructions integer_add_instructions(
+ context.get(), [](opt::IRContext*, opt::Instruction* inst) -> bool {
+ return inst->opcode() == SpvOpIAdd;
+ });
+ {
+ auto available =
+ integer_add_instructions.GetAvailableBeforeInstruction(i7);
+ ASSERT_FALSE(available.empty());
+ ASSERT_EQ(1, available.size());
+ ASSERT_EQ(SpvOpIAdd, available[0]->opcode());
+ }
+ {
+ auto available =
+ integer_add_instructions.GetAvailableBeforeInstruction(i8);
+ ASSERT_FALSE(available.empty());
+ ASSERT_EQ(1, available.size());
+ ASSERT_EQ(SpvOpIAdd, available[0]->opcode());
+ }
+ {
+ auto available =
+ integer_add_instructions.GetAvailableBeforeInstruction(i9);
+ ASSERT_FALSE(available.empty());
+ ASSERT_EQ(1, available.size());
+ ASSERT_EQ(SpvOpIAdd, available[0]->opcode());
+ }
+ }
+}
+
+TEST(AvailableInstructionsTest, UnreachableBlock) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 320
+ OpName %4 "main"
+ OpName %8 "x"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ OpStore %8 %9
+ %12 = OpLoad %6 %8
+ OpReturn
+ %10 = OpLabel
+ %11 = OpLoad %6 %8
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ spvtools::ValidatorOptions validator_options;
+ ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+ kConsoleMessageConsumer));
+
+ AvailableInstructions all_instructions(
+ context.get(),
+ [](opt::IRContext*, opt::Instruction*) -> bool { return true; });
+ ASSERT_EQ(7, all_instructions
+ .GetAvailableBeforeInstruction(
+ context->get_def_use_mgr()->GetDef(12))
+ .size());
+
+#ifndef NDEBUG
+ ASSERT_DEATH(all_instructions.GetAvailableBeforeInstruction(
+ context->get_def_use_mgr()->GetDef(11)),
+ "Availability can only be queried for reachable instructions.");
+#endif
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
diff --git a/utils/check_copyright.py b/utils/check_copyright.py
index b15bc20..1bc39f6 100755
--- a/utils/check_copyright.py
+++ b/utils/check_copyright.py
@@ -36,7 +36,8 @@
'André Perez Maselco',
'Vasyl Teliman',
'Advanced Micro Devices, Inc.',
- 'Stefano Milizia']
+ 'Stefano Milizia',
+ 'Alastair F. Donaldson']
CURRENT_YEAR='2020'
YEARS = '(2014-2016|2015-2016|2015-2020|2016|2016-2017|2017|2017-2019|2018|2019|2020|2021)'
