spirv-fuzz: Skip unreachable blocks (#3729)
Fixes #3722, fixes #3713, fixes #3714.
diff --git a/source/fuzz/fuzzer_pass.cpp b/source/fuzz/fuzzer_pass.cpp
index a6a698e..926fc52 100644
--- a/source/fuzz/fuzzer_pass.cpp
+++ b/source/fuzz/fuzzer_pass.cpp
@@ -107,7 +107,20 @@
action) {
// Consider every block in every function.
for (auto& function : *GetIRContext()->module()) {
+ // Consider only reachable blocks. We do this in a separate loop to avoid
+ // recomputing the dominator analysis every time |action| changes the
+ // module.
+ std::vector<opt::BasicBlock*> reachable_blocks;
+
+ const auto* dominator_analysis =
+ GetIRContext()->GetDominatorAnalysis(&function);
for (auto& block : function) {
+ if (dominator_analysis->IsReachable(&block)) {
+ reachable_blocks.push_back(&block);
+ }
+ }
+
+ for (auto* block : reachable_blocks) {
// We now consider every instruction in the block, randomly deciding
// whether to apply a transformation before it.
@@ -122,7 +135,7 @@
base_opcode_skip_triples;
// The initial base instruction is the block label.
- uint32_t base = block.id();
+ uint32_t base = block->id();
// Counts the number of times we have seen each opcode since we reset the
// base instruction.
@@ -131,7 +144,7 @@
// Consider every instruction in the block. The label is excluded: it is
// only necessary to consider it as a base in case the first instruction
// in the block does not have a result id.
- for (auto inst_it = block.begin(); inst_it != block.end(); ++inst_it) {
+ for (auto inst_it = block->begin(); inst_it != block->end(); ++inst_it) {
if (inst_it->HasResultId()) {
// In the case that the instruction has a result id, we use the
// instruction as its own base, and clear the skip counts we have
@@ -142,7 +155,7 @@
const SpvOp opcode = inst_it->opcode();
// Invoke the provided function, which might apply a transformation.
- action(&function, &block, inst_it,
+ action(&function, block, inst_it,
MakeInstructionDescriptor(
base, opcode,
skip_count.count(opcode) ? skip_count.at(opcode) : 0));
diff --git a/source/fuzz/fuzzer_pass.h b/source/fuzz/fuzzer_pass.h
index 1e6992a..8d75c63 100644
--- a/source/fuzz/fuzzer_pass.h
+++ b/source/fuzz/fuzzer_pass.h
@@ -70,9 +70,9 @@
std::function<bool(opt::IRContext*, opt::Instruction*)>
instruction_is_relevant) const;
- // A helper method that iterates through each instruction in each block, at
- // all times tracking an instruction descriptor that allows the latest
- // instruction to be located even if it has no result id.
+ // A helper method that iterates through each instruction in each reachable
+ // block, at all times tracking an instruction descriptor that allows the
+ // latest instruction to be located even if it has no result id.
//
// The code to manipulate the instruction descriptor is a bit fiddly. The
// point of this method is to avoiding having to duplicate it in multiple
diff --git a/source/fuzz/fuzzer_util.cpp b/source/fuzz/fuzzer_util.cpp
index 001cd86..2502da7 100644
--- a/source/fuzz/fuzzer_util.cpp
+++ b/source/fuzz/fuzzer_util.cpp
@@ -503,6 +503,9 @@
bool IdIsAvailableAtUse(opt::IRContext* context,
opt::Instruction* use_instruction,
uint32_t use_input_operand_index, uint32_t id) {
+ assert(context->get_instr_block(use_instruction) &&
+ "|use_instruction| must be in a basic block");
+
auto defining_instruction = context->get_def_use_mgr()->GetDef(id);
auto enclosing_function =
context->get_instr_block(use_instruction)->GetParent();
@@ -521,6 +524,12 @@
return false;
}
auto dominator_analysis = context->GetDominatorAnalysis(enclosing_function);
+ if (!dominator_analysis->IsReachable(
+ context->get_instr_block(use_instruction)) ||
+ !dominator_analysis->IsReachable(context->get_instr_block(id))) {
+ // Skip unreachable blocks.
+ return false;
+ }
if (use_instruction->opcode() == SpvOpPhi) {
// In the case where the use is an operand to OpPhi, it is actually the
// *parent* block associated with the operand that must be dominated by
@@ -536,6 +545,9 @@
bool IdIsAvailableBeforeInstruction(opt::IRContext* context,
opt::Instruction* instruction,
uint32_t id) {
+ assert(context->get_instr_block(instruction) &&
+ "|instruction| must be in a basic block");
+
auto defining_instruction = context->get_def_use_mgr()->GetDef(id);
auto enclosing_function = context->get_instr_block(instruction)->GetParent();
// If the id a function parameter, it needs to be associated with the
@@ -552,8 +564,12 @@
// The instruction is not available right before its own definition.
return false;
}
- return context->GetDominatorAnalysis(enclosing_function)
- ->Dominates(defining_instruction, instruction);
+ const auto* dominator_analysis =
+ context->GetDominatorAnalysis(enclosing_function);
+ return dominator_analysis->IsReachable(
+ context->get_instr_block(instruction)) &&
+ dominator_analysis->IsReachable(context->get_instr_block(id)) &&
+ dominator_analysis->Dominates(defining_instruction, instruction);
}
bool InstructionIsFunctionParameter(opt::Instruction* instruction,
diff --git a/source/fuzz/fuzzer_util.h b/source/fuzz/fuzzer_util.h
index 5f1e3f7..b4b9057 100644
--- a/source/fuzz/fuzzer_util.h
+++ b/source/fuzz/fuzzer_util.h
@@ -188,13 +188,14 @@
// Checks whether |id| is available (according to dominance rules) at the use
// point defined by input operand |use_input_operand_index| of
-// |use_instruction|.
+// |use_instruction|. |use_instruction| must be a in some basic block.
bool IdIsAvailableAtUse(opt::IRContext* context,
opt::Instruction* use_instruction,
uint32_t use_input_operand_index, uint32_t id);
// Checks whether |id| is available (according to dominance rules) at the
-// program point directly before |instruction|.
+// program point directly before |instruction|. |instruction| must be in some
+// basic block.
bool IdIsAvailableBeforeInstruction(opt::IRContext* context,
opt::Instruction* instruction, uint32_t id);
diff --git a/source/fuzz/transformation_add_opphi_synonym.cpp b/source/fuzz/transformation_add_opphi_synonym.cpp
index 3436dd7..0eee881 100644
--- a/source/fuzz/transformation_add_opphi_synonym.cpp
+++ b/source/fuzz/transformation_add_opphi_synonym.cpp
@@ -110,9 +110,6 @@
// the predecessors list of |block|.
assert(pred_block && "Could not find one of the predecessor blocks.");
- // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3722): This
- // function always returns false if the block is unreachable, so it may
- // need to be refactored.
if (!fuzzerutil::IdIsAvailableBeforeInstruction(
ir_context, pred_block->terminator(), id)) {
return false;
diff --git a/source/fuzz/transformation_add_parameter.cpp b/source/fuzz/transformation_add_parameter.cpp
index d0b80eb..42d68ae 100644
--- a/source/fuzz/transformation_add_parameter.cpp
+++ b/source/fuzz/transformation_add_parameter.cpp
@@ -76,12 +76,6 @@
}
// If the id of the value of the map is not available before the caller,
// return false.
- // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3722):
- // This can potentially trigger a bug if the caller is in an
- // unreachable block. fuzzerutil::IdIsAvailableBeforeInstruction uses
- // dominator analysis to check that value_id is available and the
- // domination rules are not defined for unreachable blocks.
- // The following code should be refactored.
if (!fuzzerutil::IdIsAvailableBeforeInstruction(ir_context, instr,
value_id)) {
return false;
diff --git a/source/fuzz/transformation_replace_irrelevant_id.cpp b/source/fuzz/transformation_replace_irrelevant_id.cpp
index 25a2fc4..5ac182a 100644
--- a/source/fuzz/transformation_replace_irrelevant_id.cpp
+++ b/source/fuzz/transformation_replace_irrelevant_id.cpp
@@ -77,9 +77,6 @@
}
// The id must be available to use at the use point.
- // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3722):
- // IdIsAvailable at use always returns false if the instruction is in an
- // unreachable block, so it might need to be fixed.
return fuzzerutil::IdIsAvailableAtUse(
ir_context, use_instruction,
message_.id_use_descriptor().in_operand_index(),
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index 3d2b569..5bdb42c 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -28,6 +28,7 @@
fuzzer_pass_donate_modules_test.cpp
fuzzer_pass_outline_functions_test.cpp
instruction_descriptor_test.cpp
+ fuzzer_pass_test.cpp
replayer_test.cpp
transformation_access_chain_test.cpp
transformation_add_constant_boolean_test.cpp
diff --git a/test/fuzz/fuzzer_pass_test.cpp b/test/fuzz/fuzzer_pass_test.cpp
new file mode 100644
index 0000000..ee22632
--- /dev/null
+++ b/test/fuzz/fuzzer_pass_test.cpp
@@ -0,0 +1,103 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// 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_add_opphi_synonyms.h"
+#include "source/fuzz/pseudo_random_generator.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+class FuzzerPassMock : public FuzzerPass {
+ public:
+ FuzzerPassMock(opt::IRContext* ir_context,
+ TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, transformation_context, fuzzer_context,
+ transformations) {}
+
+ ~FuzzerPassMock() override = default;
+
+ const std::unordered_set<uint32_t>& GetReachedInstructions() const {
+ return reached_ids_;
+ }
+
+ void Apply() override {
+ ForEachInstructionWithInstructionDescriptor(
+ [this](opt::Function* /*unused*/, opt::BasicBlock* /*unused*/,
+ opt::BasicBlock::iterator inst_it,
+ const protobufs::InstructionDescriptor& /*unused*/) {
+ if (inst_it->result_id()) {
+ reached_ids_.insert(inst_it->result_id());
+ }
+ });
+ }
+
+ private:
+ std::unordered_set<uint32_t> reached_ids_;
+};
+
+TEST(FuzzerPassTest, ForEachInstructionWithInstructionDescriptor) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeFloat 32
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %7 = OpUndef %6
+ OpReturn
+ %8 = OpLabel
+ %9 = OpUndef %6
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ // Check that %5 is reachable and %8 is unreachable as expected.
+ const auto* dominator_analysis =
+ context->GetDominatorAnalysis(context->GetFunction(4));
+ ASSERT_TRUE(dominator_analysis->IsReachable(5));
+ ASSERT_FALSE(dominator_analysis->IsReachable(8));
+
+ PseudoRandomGenerator prng(0);
+ FuzzerContext fuzzer_context(&prng, 100);
+ protobufs::TransformationSequence transformations;
+ FuzzerPassMock fuzzer_pass_mock(context.get(), &transformation_context,
+ &fuzzer_context, &transformations);
+ fuzzer_pass_mock.Apply();
+
+ ASSERT_TRUE(fuzzer_pass_mock.GetReachedInstructions().count(7));
+ ASSERT_FALSE(fuzzer_pass_mock.GetReachedInstructions().count(9));
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
