Add "split block" transformation. (#2633)
With this pass, the fuzzer can split blocks in the input module. This
is mainly useful in order to give other (future) transformations more
opportunities to apply.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index af25904..a4cbf8e 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -30,17 +30,23 @@
fuzzer.h
fuzzer_context.h
fuzzer_pass.h
+ fuzzer_pass_split_blocks.h
+ fuzzer_util.h
protobufs/spirvfuzz_protobufs.h
pseudo_random_generator.h
random_generator.h
+ transformation_split_block.h
${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.h
fact_manager.cpp
fuzzer.cpp
fuzzer_context.cpp
fuzzer_pass.cpp
+ fuzzer_pass_split_blocks.cpp
+ fuzzer_util.cpp
pseudo_random_generator.cpp
random_generator.cpp
+ transformation_split_block.cpp
${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.cc
)
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 2f28d79..559602c 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -19,6 +19,7 @@
#include "source/fuzz/fact_manager.h"
#include "source/fuzz/fuzzer_context.h"
+#include "source/fuzz/fuzzer_pass_split_blocks.h"
#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
#include "source/fuzz/pseudo_random_generator.h"
#include "source/opt/build_module.h"
@@ -50,7 +51,8 @@
Fuzzer::FuzzerResultStatus Fuzzer::Run(
const std::vector<uint32_t>& binary_in,
const protobufs::FactSequence& initial_facts,
- std::vector<uint32_t>* binary_out, protobufs::TransformationSequence*,
+ std::vector<uint32_t>* binary_out,
+ protobufs::TransformationSequence* transformation_sequence_out,
spv_const_fuzzer_options options) const {
// Check compatibility between the library version being linked with and the
// header files being used.
@@ -95,9 +97,10 @@
return Fuzzer::FuzzerResultStatus::kInitialFactsInvalid;
}
- // Fuzzer passes will be created and applied here and will populate the
- // output sequence of transformations. Currently there are no passes.
- // TODO(afd) Implement fuzzer passes and invoke them here.
+ // Apply some semantics-preserving passes.
+ FuzzerPassSplitBlocks(ir_context.get(), &fact_manager, &fuzzer_context,
+ transformation_sequence_out)
+ .Apply();
// Encode the module as a binary.
ir_context->module()->ToBinary(binary_out, false);
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 11de612..959f25a 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -17,9 +17,20 @@
namespace spvtools {
namespace fuzz {
+namespace {
+// Default probabilities for applying various transformations.
+// All values are percentages.
+// Keep them in alphabetical order.
+
+const uint32_t kDefaultChanceOfSplittingBlock = 20;
+
+} // namespace
+
FuzzerContext::FuzzerContext(RandomGenerator* random_generator,
uint32_t min_fresh_id)
- : random_generator_(random_generator), next_fresh_id_(min_fresh_id) {}
+ : random_generator_(random_generator),
+ next_fresh_id_(min_fresh_id),
+ chance_of_splitting_block_(kDefaultChanceOfSplittingBlock) {}
FuzzerContext::~FuzzerContext() = default;
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 5ab0f6f..fbd9c45 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -39,11 +39,19 @@
// or to have been issued before.
uint32_t GetFreshId();
+ // Probabilities associated with applying various transformations.
+ // Keep them in alphabetical order.
+ uint32_t GetChanceOfSplittingBlock() { return chance_of_splitting_block_; }
+
private:
// The source of randomness.
RandomGenerator* random_generator_;
// The next fresh id to be issued.
uint32_t next_fresh_id_;
+
+ // Probabilities associated with applying various transformations.
+ // Keep them in alphabetical order.
+ uint32_t chance_of_splitting_block_;
};
} // namespace fuzz
diff --git a/source/fuzz/fuzzer_pass_split_blocks.cpp b/source/fuzz/fuzzer_pass_split_blocks.cpp
new file mode 100644
index 0000000..9d400c8
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_split_blocks.cpp
@@ -0,0 +1,91 @@
+// Copyright (c) 2019 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_split_blocks.h"
+
+#include <utility>
+#include <vector>
+
+#include "source/fuzz/transformation_split_block.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassSplitBlocks::FuzzerPassSplitBlocks(
+ opt::IRContext* ir_context, FactManager* fact_manager,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, fact_manager, fuzzer_context, transformations) {}
+
+FuzzerPassSplitBlocks::~FuzzerPassSplitBlocks() = default;
+
+void FuzzerPassSplitBlocks::Apply() {
+ // Consider each block in the module.
+ for (auto& function : *GetIRContext()->module()) {
+ for (auto& block : function) {
+ // Probabilistically decide whether to try to split this block.
+ if (GetFuzzerContext()->GetRandomGenerator()->RandomPercentage() >
+ GetFuzzerContext()->GetChanceOfSplittingBlock()) {
+ continue;
+ }
+ // We are going to try to split this block. We now need to choose where
+ // to split it. We do this by finding a base instruction that has a
+ // result id, and an offset from that base instruction. We would like
+ // offsets to be as small as possible and ideally 0 - we only need offsets
+ // because not all instructions can be identified by a result id (e.g.
+ // OpStore instructions cannot).
+ std::vector<std::pair<uint32_t, uint32_t>> base_offset_pairs;
+ // The initial base instruction is the block label.
+ uint32_t base = block.id();
+ uint32_t offset = 0;
+ // 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 : block) {
+ if (inst.HasResultId()) {
+ // In the case that the instruction has a result id, we use the
+ // instruction as its own base, with zero offset.
+ base = inst.result_id();
+ offset = 0;
+ } else {
+ // The instruction does not have a result id, so we need to identify
+ // it via the latest instruction that did have a result id (base), and
+ // an incremented offset.
+ offset++;
+ }
+ base_offset_pairs.emplace_back(base, offset);
+ }
+ // Having identified all the places we might be able to split the block,
+ // we choose one of them.
+ auto base_offset = base_offset_pairs
+ [GetFuzzerContext()->GetRandomGenerator()->RandomUint32(
+ static_cast<uint32_t>(base_offset_pairs.size()))];
+ auto message = transformation::MakeTransformationSplitBlock(
+ base_offset.first, base_offset.second,
+ GetFuzzerContext()->GetFreshId());
+ // If the position we have chosen turns out to be a valid place to split
+ // the block, we apply the split. Otherwise the block just doesn't get
+ // split.
+ if (transformation::IsApplicable(message, GetIRContext(),
+ *GetFactManager())) {
+ transformation::Apply(message, GetIRContext(), GetFactManager());
+ *GetTransformations()->add_transformation()->mutable_split_block() =
+ message;
+ }
+ }
+ }
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_split_blocks.h b/source/fuzz/fuzzer_pass_split_blocks.h
new file mode 100644
index 0000000..951022b
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_split_blocks.h
@@ -0,0 +1,39 @@
+// Copyright (c) 2019 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.
+
+#ifndef SOURCE_FUZZ_FUZZER_PASS_SPLIT_BLOCKS_
+#define SOURCE_FUZZ_FUZZER_PASS_SPLIT_BLOCKS_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// A fuzzer pass for splitting blocks in the module, to create more blocks; this
+// can be very useful for giving other passes a chance to apply.
+class FuzzerPassSplitBlocks : public FuzzerPass {
+ public:
+ FuzzerPassSplitBlocks(opt::IRContext* ir_context, FactManager* fact_manager,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassSplitBlocks() override;
+
+ void Apply() override;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // #define SOURCE_FUZZ_FUZZER_PASS_SPLIT_BLOCKS_
diff --git a/source/fuzz/fuzzer_util.cpp b/source/fuzz/fuzzer_util.cpp
new file mode 100644
index 0000000..645c121
--- /dev/null
+++ b/source/fuzz/fuzzer_util.cpp
@@ -0,0 +1,36 @@
+// Copyright (c) 2019 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_util.h"
+
+namespace spvtools {
+namespace fuzz {
+
+namespace fuzzerutil {
+
+bool IsFreshId(opt::IRContext* context, uint32_t id) {
+ return !context->get_def_use_mgr()->GetDef(id);
+}
+
+void UpdateModuleIdBound(opt::IRContext* context, uint32_t id) {
+ // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2541) consider the
+ // case where the maximum id bound is reached.
+ context->module()->SetIdBound(
+ std::max(context->module()->id_bound(), id + 1));
+}
+
+} // namespace fuzzerutil
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_util.h b/source/fuzz/fuzzer_util.h
new file mode 100644
index 0000000..30d870b
--- /dev/null
+++ b/source/fuzz/fuzzer_util.h
@@ -0,0 +1,38 @@
+// Copyright (c) 2019 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.
+
+#ifndef SOURCE_FUZZ_FUZZER_UTIL_H_
+#define SOURCE_FUZZ_FUZZER_UTIL_H_
+
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// Provides global utility methods for use by the fuzzer
+namespace fuzzerutil {
+
+// Returns true if and only if the module does not define the given id.
+bool IsFreshId(opt::IRContext* context, uint32_t id);
+
+// Updates the module's id bound if needed so that it is large enough to
+// account for the given id.
+void UpdateModuleIdBound(opt::IRContext* context, uint32_t id);
+
+} // namespace fuzzerutil
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_FUZZER_UTIL_H_
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index e87819a..8f1975b 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -34,5 +34,31 @@
}
message Transformation {
+ oneof transformation {
+ TransformationSplitBlock split_block = 1;
+ }
// Currently there are no transformations.
}
+
+message TransformationSplitBlock {
+
+ // A transformation that splits a basic block into two basic blocks.
+
+ // The result id of an instruction.
+ uint32 result_id = 1;
+
+ // An offset, such that the block containing |result_id_| should be split
+ // right before the instruction |offset_| instructions after |result_id_|.
+ uint32 offset = 2;
+
+ // An id that must not yet be used by the module to which this transformation
+ // is applied. Rather than having the transformation choose a suitable id on
+ // application, we require the id to be given upfront in order to facilitate
+ // reducing fuzzed shaders by removing transformations. The reason is that
+ // future transformations may refer to the fresh id introduced by this
+ // transformation, and if we end up changing what that id is, due to removing
+ // earlier transformations, it may inhibit later transformations from
+ // applying.
+ uint32 fresh_id = 3;
+
+}
diff --git a/source/fuzz/pseudo_random_generator.cpp b/source/fuzz/pseudo_random_generator.cpp
index 773b89d..9643264 100644
--- a/source/fuzz/pseudo_random_generator.cpp
+++ b/source/fuzz/pseudo_random_generator.cpp
@@ -12,10 +12,10 @@
// See the License for the specific language governing permissions and
// limitations under the License.
-#include <cassert>
-
#include "source/fuzz/pseudo_random_generator.h"
+#include <cassert>
+
namespace spvtools {
namespace fuzz {
diff --git a/source/fuzz/transformation_split_block.cpp b/source/fuzz/transformation_split_block.cpp
new file mode 100644
index 0000000..943bed0
--- /dev/null
+++ b/source/fuzz/transformation_split_block.cpp
@@ -0,0 +1,183 @@
+// Copyright (c) 2019 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/transformation_split_block.h"
+
+#include <utility>
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/util/make_unique.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace transformation {
+
+using opt::BasicBlock;
+using opt::IRContext;
+using opt::Instruction;
+using opt::Operand;
+
+namespace {
+
+// Returns:
+// - (true, block->end()) if the relevant instruction is in this block
+// but inapplicable
+// - (true, it) if 'it' is an iterator for the relevant instruction
+// - (false, _) otherwise.
+std::pair<bool, BasicBlock::iterator> FindInstToSplitBefore(
+ const protobufs::TransformationSplitBlock& message, BasicBlock* block) {
+ // There are three possibilities:
+ // (1) the transformation wants to split at some offset from the block's
+ // label.
+ // (2) the transformation wants to split at some offset from a
+ // non-label instruction inside the block.
+ // (3) the split associated with this transformation has nothing to do with
+ // this block
+ if (message.result_id() == block->id()) {
+ // Case (1).
+ if (message.offset() == 0) {
+ // The offset is not allowed to be 0: this would mean splitting before the
+ // block's label.
+ // By returning (true, block->end()), we indicate that we did find the
+ // instruction (so that it is not worth searching further for it), but
+ // that splitting will not be possible.
+ return {true, block->end()};
+ }
+ // Conceptually, the first instruction in the block is [label + 1].
+ // We thus start from 1 when applying the offset.
+ auto inst_it = block->begin();
+ for (uint32_t i = 1; i < message.offset() && inst_it != block->end(); i++) {
+ ++inst_it;
+ }
+ // This is either the desired instruction, or the end of the block.
+ return {true, inst_it};
+ }
+ for (auto inst_it = block->begin(); inst_it != block->end(); ++inst_it) {
+ if (message.result_id() == inst_it->result_id()) {
+ // Case (2): we have found the base instruction; we now apply the offset.
+ for (uint32_t i = 0; i < message.offset() && inst_it != block->end();
+ i++) {
+ ++inst_it;
+ }
+ // This is either the desired instruction, or the end of the block.
+ return {true, inst_it};
+ }
+ }
+ // Case (3).
+ return {false, block->end()};
+}
+
+} // namespace
+
+bool IsApplicable(const protobufs::TransformationSplitBlock& message,
+ IRContext* context, const FactManager& /*unused*/) {
+ if (!fuzzerutil::IsFreshId(context, message.fresh_id())) {
+ // We require the id for the new block to be unused.
+ return false;
+ }
+ // Consider every block in every function.
+ for (auto& function : *context->module()) {
+ for (auto& block : function) {
+ auto maybe_split_before = FindInstToSplitBefore(message, &block);
+ if (!maybe_split_before.first) {
+ continue;
+ }
+ if (maybe_split_before.second == block.end()) {
+ // The base instruction was found, but the offset was inappropriate.
+ return false;
+ }
+ if (block.IsLoopHeader()) {
+ // We cannot split a loop header block: back-edges would become invalid.
+ return false;
+ }
+ auto split_before = maybe_split_before.second;
+ if (split_before->PreviousNode() &&
+ split_before->PreviousNode()->opcode() == SpvOpSelectionMerge) {
+ // We cannot split directly after a selection merge: this would separate
+ // the merge from its associated branch or switch operation.
+ return false;
+ }
+ if (split_before->opcode() == SpvOpVariable) {
+ // We cannot split directly after a variable; variables in a function
+ // must be contiguous in the entry block.
+ return false;
+ }
+ if (split_before->opcode() == SpvOpPhi &&
+ split_before->NumInOperands() != 2) {
+ // We cannot split before an OpPhi unless the OpPhi has exactly one
+ // associated incoming edge.
+ return false;
+ }
+ return true;
+ }
+ }
+ return false;
+}
+
+void Apply(const protobufs::TransformationSplitBlock& message,
+ IRContext* context, FactManager* /*unused*/) {
+ for (auto& function : *context->module()) {
+ for (auto& block : function) {
+ auto maybe_split_before = FindInstToSplitBefore(message, &block);
+ if (!maybe_split_before.first) {
+ continue;
+ }
+ assert(maybe_split_before.second != block.end() &&
+ "If the transformation is applicable, we should have an "
+ "instruction to split on.");
+ // We need to make sure the module's id bound is large enough to add the
+ // fresh id.
+ fuzzerutil::UpdateModuleIdBound(context, message.fresh_id());
+ // Split the block.
+ auto new_bb = block.SplitBasicBlock(context, message.fresh_id(),
+ maybe_split_before.second);
+ // The split does not automatically add a branch between the two parts of
+ // the original block, so we add one.
+ block.AddInstruction(MakeUnique<Instruction>(
+ context, SpvOpBranch, 0, 0,
+ std::initializer_list<Operand>{Operand(
+ spv_operand_type_t::SPV_OPERAND_TYPE_ID, {message.fresh_id()})}));
+ // If we split before OpPhi instructions, we need to update their
+ // predecessor operand so that the block they used to be inside is now the
+ // predecessor.
+ new_bb->ForEachPhiInst([&block](Instruction* phi_inst) {
+ // The following assertion is a sanity check. It is guaranteed to hold
+ // if IsApplicable holds.
+ assert(phi_inst->NumInOperands() == 2 &&
+ "We can only split a block before an OpPhi if block has exactly "
+ "one predecessor.");
+ phi_inst->SetInOperand(1, {block.id()});
+ });
+ // Invalidate all analyses
+ context->InvalidateAnalysesExceptFor(IRContext::Analysis::kAnalysisNone);
+ return;
+ }
+ }
+ assert(0 &&
+ "Should be unreachable: it should have been possible to apply this "
+ "transformation.");
+}
+
+protobufs::TransformationSplitBlock MakeTransformationSplitBlock(
+ uint32_t result_id, uint32_t offset, uint32_t fresh_id) {
+ protobufs::TransformationSplitBlock result;
+ result.set_result_id(result_id);
+ result.set_offset(offset);
+ result.set_fresh_id(fresh_id);
+ return result;
+}
+
+} // namespace transformation
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/transformation_split_block.h b/source/fuzz/transformation_split_block.h
new file mode 100644
index 0000000..9ae419b
--- /dev/null
+++ b/source/fuzz/transformation_split_block.h
@@ -0,0 +1,52 @@
+// Copyright (c) 2019 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.
+
+#ifndef SOURCE_FUZZ_TRANSFORMATION_SPLIT_BLOCK_H_
+#define SOURCE_FUZZ_TRANSFORMATION_SPLIT_BLOCK_H_
+
+#include "source/fuzz/fact_manager.h"
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace transformation {
+
+// - |result_id| must be the result id of an instruction 'base' in some
+// block 'blk'.
+// - 'blk' must contain an instruction 'inst' located |offset| instructions
+// after 'inst' (if |offset| = 0 then 'inst' = 'base').
+// - Splitting 'blk' at 'inst', so that all instructions from 'inst' onwards
+// appear in a new block that 'blk' directly jumps to must be valid.
+// - |fresh_id| must not be used by the module.
+bool IsApplicable(const protobufs::TransformationSplitBlock& message,
+ opt::IRContext* context, const FactManager& fact_manager);
+
+// - A new block with label |fresh_id| is inserted right after 'blk' in
+// program order.
+// - All instructions of 'blk' from 'inst' onwards are moved into the new
+// block.
+// - 'blk' is made to jump unconditionally to the new block.
+void Apply(const protobufs::TransformationSplitBlock& message,
+ opt::IRContext* context, FactManager* fact_manager);
+
+// Creates a protobuf message representing a block-splitting transformation.
+protobufs::TransformationSplitBlock MakeTransformationSplitBlock(
+ uint32_t result_id, uint32_t offset, uint32_t fresh_id);
+
+} // namespace transformation
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_TRANSFORMATION_SPLIT_BLOCK_H_
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 5def389..3dca430 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -186,6 +186,7 @@
add_subdirectory(link)
add_subdirectory(opt)
add_subdirectory(reduce)
+add_subdirectory(fuzz)
add_subdirectory(tools)
add_subdirectory(util)
add_subdirectory(val)
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
new file mode 100644
index 0000000..9165026
--- /dev/null
+++ b/test/fuzz/CMakeLists.txt
@@ -0,0 +1,27 @@
+# Copyright (c) 2019 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.
+
+if (${SPIRV_BUILD_FUZZER})
+
+ set(SOURCES
+ fuzz_test_util.h
+
+ fuzz_test_util.cpp
+ transformation_split_block_test.cpp)
+
+ add_spvtools_unittest(TARGET fuzz
+ SRCS ${SOURCES}
+ LIBS SPIRV-Tools-fuzz
+ )
+endif()
diff --git a/test/fuzz/fuzz_test_util.cpp b/test/fuzz/fuzz_test_util.cpp
new file mode 100644
index 0000000..545512f
--- /dev/null
+++ b/test/fuzz/fuzz_test_util.cpp
@@ -0,0 +1,89 @@
+// Copyright (c) 2019 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 "test/fuzz/fuzz_test_util.h"
+
+#include <iostream>
+
+namespace spvtools {
+namespace fuzz {
+
+bool IsEqual(const spv_target_env env,
+ const std::vector<uint32_t>& expected_binary,
+ const std::vector<uint32_t>& actual_binary) {
+ if (expected_binary == actual_binary) {
+ return true;
+ }
+ SpirvTools t(env);
+ std::string expected_disassembled;
+ std::string actual_disassembled;
+ if (!t.Disassemble(expected_binary, &expected_disassembled,
+ kFuzzDisassembleOption)) {
+ return false;
+ }
+ if (!t.Disassemble(actual_binary, &actual_disassembled,
+ kFuzzDisassembleOption)) {
+ return false;
+ }
+ // Using expect gives us a string diff if the strings are not the same.
+ EXPECT_EQ(expected_disassembled, actual_disassembled);
+ // We then return the result of the equality comparison, to be used by an
+ // assertion in the test root function.
+ return expected_disassembled == actual_disassembled;
+}
+
+bool IsEqual(const spv_target_env env, const std::string& expected_text,
+ const std::vector<uint32_t>& actual_binary) {
+ std::vector<uint32_t> expected_binary;
+ SpirvTools t(env);
+ if (!t.Assemble(expected_text, &expected_binary, kFuzzAssembleOption)) {
+ return false;
+ }
+ return IsEqual(env, expected_binary, actual_binary);
+}
+
+bool IsEqual(const spv_target_env env, const std::string& expected_text,
+ const opt::IRContext* actual_ir) {
+ std::vector<uint32_t> actual_binary;
+ actual_ir->module()->ToBinary(&actual_binary, false);
+ return IsEqual(env, expected_text, actual_binary);
+}
+
+bool IsEqual(const spv_target_env env, const opt::IRContext* ir_1,
+ const opt::IRContext* ir_2) {
+ std::vector<uint32_t> binary_1;
+ ir_1->module()->ToBinary(&binary_1, false);
+ std::vector<uint32_t> binary_2;
+ ir_2->module()->ToBinary(&binary_2, false);
+ return IsEqual(env, binary_1, binary_2);
+}
+
+bool IsValid(spv_target_env env, const opt::IRContext* ir) {
+ std::vector<uint32_t> binary;
+ ir->module()->ToBinary(&binary, false);
+ SpirvTools t(env);
+ return t.Validate(binary);
+}
+
+std::string ToString(spv_target_env env, const opt::IRContext* ir) {
+ std::vector<uint32_t> binary;
+ ir->module()->ToBinary(&binary, false);
+ SpirvTools t(env);
+ std::string result;
+ t.Disassemble(binary, &result, kFuzzDisassembleOption);
+ return result;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/test/fuzz/fuzz_test_util.h b/test/fuzz/fuzz_test_util.h
new file mode 100644
index 0000000..202622c
--- /dev/null
+++ b/test/fuzz/fuzz_test_util.h
@@ -0,0 +1,65 @@
+// Copyright (c) 2019 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.
+
+#ifndef TEST_FUZZ_FUZZ_TEST_UTIL_H_
+#define TEST_FUZZ_FUZZ_TEST_UTIL_H_
+
+#include "gtest/gtest.h"
+
+#include "source/opt/build_module.h"
+#include "source/opt/ir_context.h"
+#include "spirv-tools/libspirv.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// Returns true if and only if the given binaries are bit-wise equal.
+bool IsEqual(spv_target_env env, const std::vector<uint32_t>& expected_binary,
+ const std::vector<uint32_t>& actual_binary);
+
+// Assembles the given text and returns true if and only if the resulting binary
+// is bit-wise equal to the given binary.
+bool IsEqual(spv_target_env env, const std::string& expected_text,
+ const std::vector<uint32_t>& actual_binary);
+
+// Assembles the given text and turns the given IR into binary, then returns
+// true if and only if the resulting binaries are bit-wise equal.
+bool IsEqual(spv_target_env env, const std::string& expected_text,
+ const opt::IRContext* actual_ir);
+
+// Turns the given IRs into binaries, then returns true if and only if the
+// resulting binaries are bit-wise equal.
+bool IsEqual(spv_target_env env, const opt::IRContext* ir_1,
+ const opt::IRContext* ir_2);
+
+// Assembles the given IR context and returns true if and only if
+// the resulting binary is valid.
+bool IsValid(spv_target_env env, const opt::IRContext* ir);
+
+// Assembles the given IR context, then returns its disassembly as a string.
+// Useful for debugging.
+std::string ToString(spv_target_env env, const opt::IRContext* ir);
+
+// Assembly options for writing fuzzer tests. It simplifies matters if
+// numeric ids do not change.
+const uint32_t kFuzzAssembleOption =
+ SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS;
+// Disassembly options for writing fuzzer tests.
+const uint32_t kFuzzDisassembleOption =
+ SPV_BINARY_TO_TEXT_OPTION_NO_HEADER | SPV_BINARY_TO_TEXT_OPTION_INDENT;
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // TEST_FUZZ_FUZZ_TEST_UTIL_H_
diff --git a/test/fuzz/transformation_split_block_test.cpp b/test/fuzz/transformation_split_block_test.cpp
new file mode 100644
index 0000000..976e81a
--- /dev/null
+++ b/test/fuzz/transformation_split_block_test.cpp
@@ -0,0 +1,773 @@
+// Copyright (c) 2019 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/transformation_split_block.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(TransformationSplitBlockTest, NotApplicable) {
+ // The SPIR-V in this test came from the following fragment shader, with
+ // local store elimination applied to get some OpPhi instructions.
+ //
+ // void main() {
+ // int x;
+ // int i;
+ // for (i = 0; i < 100; i++) {
+ // x += i;
+ // }
+ // }
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "i"
+ OpName %19 "x"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %19 RelaxedPrecision
+ OpDecorate %22 RelaxedPrecision
+ OpDecorate %25 RelaxedPrecision
+ OpDecorate %26 RelaxedPrecision
+ OpDecorate %27 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 0
+ %16 = OpConstant %6 100
+ %17 = OpTypeBool
+ %24 = OpConstant %6 1
+ %28 = OpUndef %6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %19 = OpVariable %7 Function
+ OpStore %8 %9
+ OpBranch %10
+ %10 = OpLabel
+ %27 = OpPhi %6 %28 %5 %22 %13
+ %26 = OpPhi %6 %9 %5 %25 %13
+ OpLoopMerge %12 %13 None
+ OpBranch %14
+ %14 = OpLabel
+ %18 = OpSLessThan %17 %26 %16
+ OpBranchConditional %18 %11 %12
+ %11 = OpLabel
+ %22 = OpIAdd %6 %27 %26
+ OpStore %19 %22
+ OpBranch %13
+ %13 = OpLabel
+ %25 = OpIAdd %6 %26 %24
+ OpStore %8 %25
+ OpBranch %10
+ %12 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ // No split before OpVariable
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(8, 0, 100), context.get(),
+ fact_manager));
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(8, 1, 100), context.get(),
+ fact_manager));
+
+ // No split before OpLabel
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(14, 0, 100), context.get(),
+ fact_manager));
+
+ // No split if base instruction is outside a function
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(1, 0, 100), context.get(),
+ fact_manager));
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(1, 4, 100), context.get(),
+ fact_manager));
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(1, 35, 100), context.get(),
+ fact_manager));
+
+ // No split if block is loop header
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(27, 0, 100), context.get(),
+ fact_manager));
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(27, 1, 100), context.get(),
+ fact_manager));
+
+ // No split if base instruction does not exist
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(88, 0, 100), context.get(),
+ fact_manager));
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(88, 22, 100), context.get(),
+ fact_manager));
+
+ // No split if offset is too large (goes into another block)
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(18, 3, 100), context.get(),
+ fact_manager));
+
+ // No split if id in use
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(18, 0, 27), context.get(),
+ fact_manager));
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(18, 0, 14), context.get(),
+ fact_manager));
+}
+
+TEST(TransformationSplitBlockTest, SplitBlockSeveralTimes) {
+ // The SPIR-V in this test came from the following fragment shader:
+ //
+ // void main() {
+ // int a;
+ // int b;
+ // a = 1;
+ // b = a;
+ // a = b;
+ // b = 2;
+ // b++;
+ // }
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "a"
+ OpName %10 "b"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %10 RelaxedPrecision
+ OpDecorate %11 RelaxedPrecision
+ OpDecorate %12 RelaxedPrecision
+ OpDecorate %14 RelaxedPrecision
+ OpDecorate %15 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %13 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpStore %8 %9
+ %11 = OpLoad %6 %8
+ OpStore %10 %11
+ %12 = OpLoad %6 %10
+ OpStore %8 %12
+ OpStore %10 %13
+ %14 = OpLoad %6 %10
+ %15 = OpIAdd %6 %14 %9
+ OpStore %10 %15
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ auto split_1 = transformation::MakeTransformationSplitBlock(5, 3, 100);
+ ASSERT_TRUE(
+ transformation::IsApplicable(split_1, context.get(), fact_manager));
+ transformation::Apply(split_1, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_split_1 = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "a"
+ OpName %10 "b"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %10 RelaxedPrecision
+ OpDecorate %11 RelaxedPrecision
+ OpDecorate %12 RelaxedPrecision
+ OpDecorate %14 RelaxedPrecision
+ OpDecorate %15 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %13 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpBranch %100
+ %100 = OpLabel
+ OpStore %8 %9
+ %11 = OpLoad %6 %8
+ OpStore %10 %11
+ %12 = OpLoad %6 %10
+ OpStore %8 %12
+ OpStore %10 %13
+ %14 = OpLoad %6 %10
+ %15 = OpIAdd %6 %14 %9
+ OpStore %10 %15
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, after_split_1, context.get()));
+
+ auto split_2 = transformation::MakeTransformationSplitBlock(11, 1, 101);
+ ASSERT_TRUE(
+ transformation::IsApplicable(split_2, context.get(), fact_manager));
+ transformation::Apply(split_2, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_split_2 = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "a"
+ OpName %10 "b"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %10 RelaxedPrecision
+ OpDecorate %11 RelaxedPrecision
+ OpDecorate %12 RelaxedPrecision
+ OpDecorate %14 RelaxedPrecision
+ OpDecorate %15 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %13 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpBranch %100
+ %100 = OpLabel
+ OpStore %8 %9
+ %11 = OpLoad %6 %8
+ OpBranch %101
+ %101 = OpLabel
+ OpStore %10 %11
+ %12 = OpLoad %6 %10
+ OpStore %8 %12
+ OpStore %10 %13
+ %14 = OpLoad %6 %10
+ %15 = OpIAdd %6 %14 %9
+ OpStore %10 %15
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, after_split_2, context.get()));
+
+ auto split_3 = transformation::MakeTransformationSplitBlock(14, 0, 102);
+ ASSERT_TRUE(
+ transformation::IsApplicable(split_3, context.get(), fact_manager));
+ transformation::Apply(split_3, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_split_3 = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "a"
+ OpName %10 "b"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %10 RelaxedPrecision
+ OpDecorate %11 RelaxedPrecision
+ OpDecorate %12 RelaxedPrecision
+ OpDecorate %14 RelaxedPrecision
+ OpDecorate %15 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %13 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpBranch %100
+ %100 = OpLabel
+ OpStore %8 %9
+ %11 = OpLoad %6 %8
+ OpBranch %101
+ %101 = OpLabel
+ OpStore %10 %11
+ %12 = OpLoad %6 %10
+ OpStore %8 %12
+ OpStore %10 %13
+ OpBranch %102
+ %102 = OpLabel
+ %14 = OpLoad %6 %10
+ %15 = OpIAdd %6 %14 %9
+ OpStore %10 %15
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, after_split_3, context.get()));
+}
+
+TEST(TransformationSplitBlockTest, SplitBlockBeforeSelectBranch) {
+ // The SPIR-V in this test came from the following fragment shader:
+ //
+ // void main() {
+ // int x, y;
+ // x = 2;
+ // if (x < y) {
+ // y = 3;
+ // } else {
+ // y = 4;
+ // }
+ // }
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "x"
+ OpName %11 "y"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %10 RelaxedPrecision
+ OpDecorate %11 RelaxedPrecision
+ OpDecorate %12 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %13 = OpTypeBool
+ %17 = OpConstant %6 3
+ %19 = OpConstant %6 4
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %11 = OpVariable %7 Function
+ OpStore %8 %9
+ %10 = OpLoad %6 %8
+ %12 = OpLoad %6 %11
+ %14 = OpSLessThan %13 %10 %12
+ OpSelectionMerge %16 None
+ OpBranchConditional %14 %15 %18
+ %15 = OpLabel
+ OpStore %11 %17
+ OpBranch %16
+ %18 = OpLabel
+ OpStore %11 %19
+ OpBranch %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ // Illegal to split between the merge and the conditional branch.
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(14, 2, 100), context.get(),
+ fact_manager));
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(12, 3, 100), context.get(),
+ fact_manager));
+
+ auto split = transformation::MakeTransformationSplitBlock(14, 1, 100);
+ ASSERT_TRUE(transformation::IsApplicable(split, context.get(), fact_manager));
+ transformation::Apply(split, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_split = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "x"
+ OpName %11 "y"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %10 RelaxedPrecision
+ OpDecorate %11 RelaxedPrecision
+ OpDecorate %12 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %13 = OpTypeBool
+ %17 = OpConstant %6 3
+ %19 = OpConstant %6 4
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %11 = OpVariable %7 Function
+ OpStore %8 %9
+ %10 = OpLoad %6 %8
+ %12 = OpLoad %6 %11
+ %14 = OpSLessThan %13 %10 %12
+ OpBranch %100
+ %100 = OpLabel
+ OpSelectionMerge %16 None
+ OpBranchConditional %14 %15 %18
+ %15 = OpLabel
+ OpStore %11 %17
+ OpBranch %16
+ %18 = OpLabel
+ OpStore %11 %19
+ OpBranch %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, after_split, context.get()));
+}
+
+TEST(TransformationSplitBlockTest, SplitBlockBeforeSwitchBranch) {
+ // The SPIR-V in this test came from the following fragment shader:
+ //
+ // void main() {
+ // int x, y;
+ // switch (y) {
+ // case 1:
+ // x = 2;
+ // case 2:
+ // break;
+ // case 3:
+ // x = 4;
+ // default:
+ // x = 6;
+ // }
+ // }
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "y"
+ OpName %15 "x"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %9 RelaxedPrecision
+ OpDecorate %15 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %16 = OpConstant %6 2
+ %18 = OpConstant %6 4
+ %19 = OpConstant %6 6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %15 = OpVariable %7 Function
+ %9 = OpLoad %6 %8
+ OpSelectionMerge %14 None
+ OpSwitch %9 %13 1 %10 2 %11 3 %12
+ %13 = OpLabel
+ OpStore %15 %19
+ OpBranch %14
+ %10 = OpLabel
+ OpStore %15 %16
+ OpBranch %11
+ %11 = OpLabel
+ OpBranch %14
+ %12 = OpLabel
+ OpStore %15 %18
+ OpBranch %13
+ %14 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ // Illegal to split between the merge and the conditional branch.
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(9, 2, 100), context.get(),
+ fact_manager));
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(15, 3, 100), context.get(),
+ fact_manager));
+
+ auto split = transformation::MakeTransformationSplitBlock(9, 1, 100);
+ ASSERT_TRUE(transformation::IsApplicable(split, context.get(), fact_manager));
+ transformation::Apply(split, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_split = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "y"
+ OpName %15 "x"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %9 RelaxedPrecision
+ OpDecorate %15 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %16 = OpConstant %6 2
+ %18 = OpConstant %6 4
+ %19 = OpConstant %6 6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %15 = OpVariable %7 Function
+ %9 = OpLoad %6 %8
+ OpBranch %100
+ %100 = OpLabel
+ OpSelectionMerge %14 None
+ OpSwitch %9 %13 1 %10 2 %11 3 %12
+ %13 = OpLabel
+ OpStore %15 %19
+ OpBranch %14
+ %10 = OpLabel
+ OpStore %15 %16
+ OpBranch %11
+ %11 = OpLabel
+ OpBranch %14
+ %12 = OpLabel
+ OpStore %15 %18
+ OpBranch %13
+ %14 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, after_split, context.get()));
+}
+
+TEST(TransformationSplitBlockTest, NoSplitDuringOpPhis) {
+ // The SPIR-V in this test came from the following fragment shader, with
+ // local store elimination applied to get some OpPhi instructions.
+ //
+ // void main() {
+ // int x;
+ // int i;
+ // for (i = 0; i < 100; i++) {
+ // x += i;
+ // }
+ // }
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "i"
+ OpName %19 "x"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %19 RelaxedPrecision
+ OpDecorate %22 RelaxedPrecision
+ OpDecorate %25 RelaxedPrecision
+ OpDecorate %26 RelaxedPrecision
+ OpDecorate %27 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 0
+ %16 = OpConstant %6 100
+ %17 = OpTypeBool
+ %24 = OpConstant %6 1
+ %28 = OpUndef %6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %19 = OpVariable %7 Function
+ OpStore %8 %9
+ OpBranch %10
+ %10 = OpLabel
+ %27 = OpPhi %6 %28 %5 %22 %13
+ %26 = OpPhi %6 %9 %5 %25 %13
+ OpBranch %50
+ %50 = OpLabel
+ OpLoopMerge %12 %13 None
+ OpBranch %14
+ %14 = OpLabel
+ %18 = OpSLessThan %17 %26 %16
+ OpBranchConditional %18 %11 %12
+ %11 = OpLabel
+ %22 = OpIAdd %6 %27 %26
+ OpStore %19 %22
+ OpBranch %13
+ %13 = OpLabel
+ %25 = OpIAdd %6 %26 %24
+ OpStore %8 %25
+ OpBranch %50
+ %12 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ // We cannot split before OpPhi instructions, since the number of incoming
+ // blocks may not appropriately match after splitting.
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(26, 0, 100), context.get(),
+ fact_manager));
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(27, 0, 100), context.get(),
+ fact_manager));
+ ASSERT_FALSE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(27, 1, 100), context.get(),
+ fact_manager));
+}
+
+TEST(TransformationSplitBlockTest, SplitOpPhiWithSinglePredecessor) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "x"
+ OpName %10 "y"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %10 RelaxedPrecision
+ OpDecorate %11 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpStore %8 %9
+ %11 = OpLoad %6 %8
+ OpBranch %20
+ %20 = OpLabel
+ %21 = OpPhi %6 %11 %5
+ OpStore %10 %21
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ ASSERT_TRUE(transformation::IsApplicable(
+ transformation::MakeTransformationSplitBlock(21, 0, 100), context.get(),
+ fact_manager));
+ auto split = transformation::MakeTransformationSplitBlock(20, 1, 100);
+ ASSERT_TRUE(transformation::IsApplicable(split, context.get(), fact_manager));
+ transformation::Apply(split, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_split = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "x"
+ OpName %10 "y"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %10 RelaxedPrecision
+ OpDecorate %11 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpStore %8 %9
+ %11 = OpLoad %6 %8
+ OpBranch %20
+ %20 = OpLabel
+ OpBranch %100
+ %100 = OpLabel
+ %21 = OpPhi %6 %11 %20
+ OpStore %10 %21
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, after_split, context.get()));
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
