spirv-fuzz: Merge the return instructions in a function (#3838)
This PR introduces TransformationMergeFunctionReturns, which changes
a function so that it only has one reachable return statement.
Fixes #3655.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index 61c9fb3..ef699a7 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -91,6 +91,7 @@
fuzzer_pass_interchange_zero_like_constants.h
fuzzer_pass_make_vector_operations_dynamic.h
fuzzer_pass_merge_blocks.h
+ fuzzer_pass_merge_function_returns.h
fuzzer_pass_mutate_pointers.h
fuzzer_pass_obfuscate_constants.h
fuzzer_pass_outline_functions.h
@@ -180,6 +181,7 @@
transformation_load.h
transformation_make_vector_operation_dynamic.h
transformation_merge_blocks.h
+ transformation_merge_function_returns.h
transformation_move_block_down.h
transformation_move_instruction_down.h
transformation_mutate_pointer.h
@@ -269,6 +271,7 @@
fuzzer_pass_interchange_zero_like_constants.cpp
fuzzer_pass_make_vector_operations_dynamic.cpp
fuzzer_pass_merge_blocks.cpp
+ fuzzer_pass_merge_function_returns.cpp
fuzzer_pass_mutate_pointers.cpp
fuzzer_pass_obfuscate_constants.cpp
fuzzer_pass_outline_functions.cpp
@@ -356,6 +359,7 @@
transformation_load.cpp
transformation_make_vector_operation_dynamic.cpp
transformation_merge_blocks.cpp
+ transformation_merge_function_returns.cpp
transformation_move_block_down.cpp
transformation_move_instruction_down.cpp
transformation_mutate_pointer.cpp
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 37260ca..7d82884 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -60,6 +60,7 @@
#include "source/fuzz/fuzzer_pass_invert_comparison_operators.h"
#include "source/fuzz/fuzzer_pass_make_vector_operations_dynamic.h"
#include "source/fuzz/fuzzer_pass_merge_blocks.h"
+#include "source/fuzz/fuzzer_pass_merge_function_returns.h"
#include "source/fuzz/fuzzer_pass_mutate_pointers.h"
#include "source/fuzz/fuzzer_pass_obfuscate_constants.h"
#include "source/fuzz/fuzzer_pass_outline_functions.h"
@@ -269,6 +270,7 @@
MaybeAddRepeatedPass<FuzzerPassMakeVectorOperationsDynamic>(
&pass_instances);
MaybeAddRepeatedPass<FuzzerPassMergeBlocks>(&pass_instances);
+ MaybeAddRepeatedPass<FuzzerPassMergeFunctionReturns>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassMutatePointers>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassOutlineFunctions>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassPermuteBlocks>(&pass_instances);
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 5151117..34f25cd 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -99,6 +99,7 @@
const std::pair<uint32_t, uint32_t> kChanceOfMakingVectorOperationDynamic = {
20, 90};
const std::pair<uint32_t, uint32_t> kChanceOfMergingBlocks = {20, 95};
+const std::pair<uint32_t, uint32_t> kChanceOfMergingFunctionReturns = {20, 90};
const std::pair<uint32_t, uint32_t> kChanceOfMovingBlockDown = {20, 50};
const std::pair<uint32_t, uint32_t> kChanceOfMutatingPointer = {20, 90};
const std::pair<uint32_t, uint32_t> kChanceOfObfuscatingConstant = {10, 90};
@@ -277,6 +278,8 @@
chance_of_making_vector_operation_dynamic_ =
ChooseBetweenMinAndMax(kChanceOfMakingVectorOperationDynamic);
chance_of_merging_blocks_ = ChooseBetweenMinAndMax(kChanceOfMergingBlocks);
+ chance_of_merging_function_returns_ =
+ ChooseBetweenMinAndMax(kChanceOfMergingFunctionReturns);
chance_of_moving_block_down_ =
ChooseBetweenMinAndMax(kChanceOfMovingBlockDown);
chance_of_mutating_pointer_ =
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 213d51b..4436b2b 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -244,6 +244,9 @@
return chance_of_making_vector_operation_dynamic_;
}
uint32_t GetChanceOfMergingBlocks() { return chance_of_merging_blocks_; }
+ uint32_t GetChanceOfMergingFunctionReturns() {
+ return chance_of_merging_function_returns_;
+ }
uint32_t GetChanceOfMovingBlockDown() { return chance_of_moving_block_down_; }
uint32_t GetChanceOfMutatingPointer() { return chance_of_mutating_pointer_; }
uint32_t GetChanceOfObfuscatingConstant() {
@@ -452,6 +455,7 @@
uint32_t chance_of_making_donor_livesafe_;
uint32_t chance_of_making_vector_operation_dynamic_;
uint32_t chance_of_merging_blocks_;
+ uint32_t chance_of_merging_function_returns_;
uint32_t chance_of_moving_block_down_;
uint32_t chance_of_mutating_pointer_;
uint32_t chance_of_obfuscating_constant_;
diff --git a/source/fuzz/fuzzer_pass_merge_function_returns.cpp b/source/fuzz/fuzzer_pass_merge_function_returns.cpp
new file mode 100644
index 0000000..7130e43
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_merge_function_returns.cpp
@@ -0,0 +1,257 @@
+// Copyright (c) 2020 Stefano Milizia
+//
+// 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_merge_function_returns.h"
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/instruction_descriptor.h"
+#include "source/fuzz/transformation_merge_function_returns.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassMergeFunctionReturns::FuzzerPassMergeFunctionReturns(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, transformation_context, fuzzer_context,
+ transformations) {}
+
+FuzzerPassMergeFunctionReturns::~FuzzerPassMergeFunctionReturns() = default;
+
+void FuzzerPassMergeFunctionReturns::Apply() {
+ for (auto& function : *GetIRContext()->module()) {
+ // Randomly decide whether to consider this function.
+ if (GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()->GetChanceOfMergingFunctionReturns())) {
+ continue;
+ }
+
+ // Only consider functions that have early returns.
+ if (!function.HasEarlyReturn()) {
+ continue;
+ }
+
+ // Get the return blocks.
+ auto return_blocks = fuzzerutil::GetReachableReturnBlocks(
+ GetIRContext(), function.result_id());
+
+ // Only go ahead if there is more than one reachable return block.
+ if (return_blocks.size() <= 1) {
+ continue;
+ }
+
+ // Make sure that OpConstantTrue and OpConstantFalse are in the module.
+ FindOrCreateBoolConstant(true, false);
+ FindOrCreateBoolConstant(false, false);
+
+ // Collect the ids available after the entry block of the function.
+ auto ids_available_after_entry_block =
+ GetTypesToIdsAvailableAfterEntryBlock(&function);
+
+ // If the entry block does not branch unconditionally to another block,
+ // split it.
+ if (function.entry()->terminator()->opcode() != SpvOpBranch) {
+ SplitBlockAfterOpPhiOrOpVariable(function.entry()->id());
+ }
+
+ // Collect the merge blocks of the function whose corresponding loops
+ // contain return blocks.
+ auto merge_blocks = GetMergeBlocksOfLoopsContainingBlocks(return_blocks);
+
+ // Split the merge blocks, if they contain instructions different from
+ // OpLabel, OpPhi and OpBranch. Collect the new ids of merge blocks.
+ std::vector<uint32_t> actual_merge_blocks;
+ for (uint32_t merge_block : merge_blocks) {
+ opt::BasicBlock* block = GetIRContext()->get_instr_block(merge_block);
+
+ // We don't need to split blocks that are already suitable (they only
+ // contain OpLabel, OpPhi or OpBranch instructions).
+ if (GetIRContext()
+ ->get_instr_block(merge_block)
+ ->WhileEachInst([](opt::Instruction* inst) {
+ return inst->opcode() == SpvOpLabel ||
+ inst->opcode() == SpvOpPhi ||
+ inst->opcode() == SpvOpBranch;
+ })) {
+ actual_merge_blocks.emplace_back(merge_block);
+ continue;
+ }
+
+ // If the merge block is also a loop header, we need to add a preheader,
+ // which will be the new merge block.
+ if (block->IsLoopHeader()) {
+ actual_merge_blocks.emplace_back(
+ GetOrCreateSimpleLoopPreheader(merge_block)->id());
+ continue;
+ }
+
+ // If the merge block is not a loop header, we must split it after the
+ // last OpPhi instruction. The merge block will be the first of the pair
+ // of blocks obtained after splitting, and it keeps the original id.
+ SplitBlockAfterOpPhiOrOpVariable(merge_block);
+ actual_merge_blocks.emplace_back(merge_block);
+ }
+
+ // Get the ids needed by the transformation.
+ uint32_t outer_header_id = GetFuzzerContext()->GetFreshId();
+ uint32_t outer_return_id = GetFuzzerContext()->GetFreshId();
+
+ bool function_is_void =
+ GetIRContext()->get_type_mgr()->GetType(function.type_id())->AsVoid();
+
+ // We only need a return value if the function is not void.
+ uint32_t return_val_id =
+ function_is_void ? 0 : GetFuzzerContext()->GetFreshId();
+
+ // We only need a placeholder for the return value if the function is not
+ // void and there is at least one relevant merge block.
+ uint32_t returnable_val_id = 0;
+ if (!function_is_void && !actual_merge_blocks.empty()) {
+ // If there is an id of the suitable type, choose one at random.
+ if (ids_available_after_entry_block.count(function.type_id())) {
+ const auto& candidates =
+ ids_available_after_entry_block[function.type_id()];
+ returnable_val_id =
+ candidates[GetFuzzerContext()->RandomIndex(candidates)];
+ } else {
+ // If there is no id, add a global OpUndef.
+ uint32_t suitable_id = FindOrCreateGlobalUndef(function.type_id());
+ // Add the new id to the map of available ids.
+ ids_available_after_entry_block.emplace(
+ function.type_id(), std::vector<uint32_t>({suitable_id}));
+ returnable_val_id = suitable_id;
+ }
+ }
+
+ // Collect all the ids needed for merge blocks.
+ auto merge_blocks_info = GetInfoNeededForMergeBlocks(
+ actual_merge_blocks, &ids_available_after_entry_block);
+
+ // Apply the transformation if it is applicable (it could be inapplicable if
+ // adding new predecessors to merge blocks breaks dominance rules).
+ MaybeApplyTransformation(TransformationMergeFunctionReturns(
+ function.result_id(), outer_header_id, outer_return_id, return_val_id,
+ returnable_val_id, merge_blocks_info));
+ }
+}
+
+std::map<uint32_t, std::vector<uint32_t>>
+FuzzerPassMergeFunctionReturns::GetTypesToIdsAvailableAfterEntryBlock(
+ opt::Function* function) const {
+ std::map<uint32_t, std::vector<uint32_t>> result;
+ // Consider all global declarations
+ for (auto& global : GetIRContext()->module()->types_values()) {
+ if (global.HasResultId() && global.type_id()) {
+ if (!result.count(global.type_id())) {
+ result.emplace(global.type_id(), std::vector<uint32_t>());
+ }
+ result[global.type_id()].emplace_back(global.result_id());
+ }
+ }
+
+ // Consider all function parameters
+ function->ForEachParam([&result](opt::Instruction* param) {
+ if (param->HasResultId() && param->type_id()) {
+ if (!result.count(param->type_id())) {
+ result.emplace(param->type_id(), std::vector<uint32_t>());
+ }
+
+ result[param->type_id()].emplace_back(param->result_id());
+ }
+ });
+
+ // Consider all the instructions in the entry block.
+ for (auto& inst : *function->entry()) {
+ if (inst.HasResultId() && inst.type_id()) {
+ if (!result.count(inst.type_id())) {
+ result.emplace(inst.type_id(), std::vector<uint32_t>());
+ }
+ result[inst.type_id()].emplace_back(inst.result_id());
+ }
+ }
+
+ return result;
+}
+
+std::set<uint32_t>
+FuzzerPassMergeFunctionReturns::GetMergeBlocksOfLoopsContainingBlocks(
+ const std::set<uint32_t>& blocks) const {
+ std::set<uint32_t> result;
+ for (uint32_t block : blocks) {
+ uint32_t merge_block =
+ GetIRContext()->GetStructuredCFGAnalysis()->LoopMergeBlock(block);
+
+ while (merge_block != 0 && !result.count(merge_block)) {
+ // Add a new entry.
+ result.emplace(merge_block);
+
+ // Walk up the loop tree.
+ block = merge_block;
+ merge_block = GetIRContext()->GetStructuredCFGAnalysis()->LoopMergeBlock(
+ merge_block);
+ }
+ }
+
+ return result;
+}
+
+std::vector<protobufs::ReturnMergingInfo>
+FuzzerPassMergeFunctionReturns::GetInfoNeededForMergeBlocks(
+ const std::vector<uint32_t>& merge_blocks,
+ std::map<uint32_t, std::vector<uint32_t>>*
+ ids_available_after_entry_block) {
+ std::vector<protobufs::ReturnMergingInfo> result;
+ for (uint32_t merge_block : merge_blocks) {
+ protobufs::ReturnMergingInfo info;
+ info.set_merge_block_id(merge_block);
+ info.set_is_returning_id(this->GetFuzzerContext()->GetFreshId());
+ info.set_maybe_return_val_id(this->GetFuzzerContext()->GetFreshId());
+
+ // Add all the ids needed for the OpPhi instructions.
+ this->GetIRContext()
+ ->get_instr_block(merge_block)
+ ->ForEachPhiInst([this, &info, &ids_available_after_entry_block](
+ opt::Instruction* phi_inst) {
+ protobufs::UInt32Pair entry;
+ entry.set_first(phi_inst->result_id());
+
+ // If there is an id of the suitable type, choose one at random.
+ if (ids_available_after_entry_block->count(phi_inst->type_id())) {
+ auto& candidates =
+ ids_available_after_entry_block->at(phi_inst->type_id());
+ entry.set_second(
+ candidates[this->GetFuzzerContext()->RandomIndex(candidates)]);
+ } else {
+ // If there is no id, add a global OpUndef.
+ uint32_t suitable_id =
+ this->FindOrCreateGlobalUndef(phi_inst->type_id());
+ // Add the new id to the map of available ids.
+ ids_available_after_entry_block->emplace(
+ phi_inst->type_id(), std::vector<uint32_t>({suitable_id}));
+ entry.set_second(suitable_id);
+ }
+
+ // Add the entry to the list.
+ *info.add_opphi_to_suitable_id() = entry;
+ });
+
+ result.emplace_back(info);
+ }
+
+ return result;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_merge_function_returns.h b/source/fuzz/fuzzer_pass_merge_function_returns.h
new file mode 100644
index 0000000..0fa505c
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_merge_function_returns.h
@@ -0,0 +1,61 @@
+// Copyright (c) 2020 Stefano Milizia
+//
+// 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_MERGE_FUNCTION_RETURNS_H_
+#define SOURCE_FUZZ_FUZZER_PASS_MERGE_FUNCTION_RETURNS_H_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// A fuzzer pass for changing functions in the module so that they don't have an
+// early return.
+class FuzzerPassMergeFunctionReturns : public FuzzerPass {
+ public:
+ FuzzerPassMergeFunctionReturns(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassMergeFunctionReturns();
+
+ void Apply() override;
+
+ private:
+ // Returns a map from type ids to a list of ids with that type and which are
+ // available at the end of the entry block of |function|.
+ std::map<uint32_t, std::vector<uint32_t>>
+ GetTypesToIdsAvailableAfterEntryBlock(opt::Function* function) const;
+
+ // Returns the set of all the loop merge blocks whose corresponding loops
+ // contain at least one of the blocks in |blocks|.
+ std::set<uint32_t> GetMergeBlocksOfLoopsContainingBlocks(
+ const std::set<uint32_t>& blocks) const;
+
+ // Returns a list of ReturnMergingInfo messages, containing the information
+ // needed by the transformation for each of the relevant merge blocks.
+ // If a new id is created (because |ids_available_after_entry_block| does not
+ // have an entry for the corresponding type), a new entry is added to
+ // |ids_available_after_entry_block|, mapping its type to a singleton set
+ // containing it.
+ std::vector<protobufs::ReturnMergingInfo> GetInfoNeededForMergeBlocks(
+ const std::vector<uint32_t>& merge_blocks,
+ std::map<uint32_t, std::vector<uint32_t>>*
+ ids_available_after_entry_block);
+};
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_FUZZER_PASS_MERGE_FUNCTION_RETURNS_H_
diff --git a/source/fuzz/fuzzer_util.cpp b/source/fuzz/fuzzer_util.cpp
index 7944d23..48aee58 100644
--- a/source/fuzz/fuzzer_util.cpp
+++ b/source/fuzz/fuzzer_util.cpp
@@ -437,6 +437,28 @@
return result;
}
+uint32_t GetLoopFromMergeBlock(opt::IRContext* ir_context,
+ uint32_t merge_block_id) {
+ uint32_t result = 0;
+ ir_context->get_def_use_mgr()->WhileEachUse(
+ merge_block_id,
+ [ir_context, &result](opt::Instruction* use_instruction,
+ uint32_t use_index) -> bool {
+ switch (use_instruction->opcode()) {
+ case SpvOpLoopMerge:
+ // The merge block operand is the first operand in OpLoopMerge.
+ if (use_index == 0) {
+ result = ir_context->get_instr_block(use_instruction)->id();
+ return false;
+ }
+ return true;
+ default:
+ return true;
+ }
+ });
+ return result;
+}
+
uint32_t FindFunctionType(opt::IRContext* ir_context,
const std::vector<uint32_t>& type_ids) {
// Look through the existing types for a match.
@@ -1673,6 +1695,23 @@
}
}
+std::set<uint32_t> GetReachableReturnBlocks(opt::IRContext* ir_context,
+ uint32_t function_id) {
+ auto function = ir_context->GetFunction(function_id);
+ assert(function && "The function |function_id| must exist.");
+
+ std::set<uint32_t> result;
+
+ ir_context->cfg()->ForEachBlockInPostOrder(function->entry().get(),
+ [&result](opt::BasicBlock* block) {
+ if (block->IsReturn()) {
+ result.emplace(block->id());
+ }
+ });
+
+ return result;
+}
+
} // namespace fuzzerutil
} // namespace fuzz
} // namespace spvtools
diff --git a/source/fuzz/fuzzer_util.h b/source/fuzz/fuzzer_util.h
index 981d229..c7e55e2 100644
--- a/source/fuzz/fuzzer_util.h
+++ b/source/fuzz/fuzzer_util.h
@@ -164,6 +164,11 @@
// Returns true if and only if |block_id| is a merge block or continue target
bool IsMergeOrContinue(opt::IRContext* ir_context, uint32_t block_id);
+// Returns the id of the header of the loop corresponding to the given loop
+// merge block. Returns 0 if |merge_block_id| is not a loop merge block.
+uint32_t GetLoopFromMergeBlock(opt::IRContext* ir_context,
+ uint32_t merge_block_id);
+
// Returns the result id of an instruction of the form:
// %id = OpTypeFunction |type_ids|
// or 0 if no such instruction exists.
@@ -547,6 +552,12 @@
// (called using OpExtInst) have not been considered.
bool InstructionHasNoSideEffects(const opt::Instruction& instruction);
+// Returns a set of the ids of all the return blocks that are reachable from
+// the entry block of |function_id|.
+// Assumes that the function exists in the module.
+std::set<uint32_t> GetReachableReturnBlocks(opt::IRContext* ir_context,
+ uint32_t function_id);
+
} // namespace fuzzerutil
} // namespace fuzz
} // namespace spvtools
diff --git a/source/fuzz/pass_management/repeated_pass_instances.h b/source/fuzz/pass_management/repeated_pass_instances.h
index ed55741..51ff2ae 100644
--- a/source/fuzz/pass_management/repeated_pass_instances.h
+++ b/source/fuzz/pass_management/repeated_pass_instances.h
@@ -47,6 +47,7 @@
#include "source/fuzz/fuzzer_pass_invert_comparison_operators.h"
#include "source/fuzz/fuzzer_pass_make_vector_operations_dynamic.h"
#include "source/fuzz/fuzzer_pass_merge_blocks.h"
+#include "source/fuzz/fuzzer_pass_merge_function_returns.h"
#include "source/fuzz/fuzzer_pass_mutate_pointers.h"
#include "source/fuzz/fuzzer_pass_obfuscate_constants.h"
#include "source/fuzz/fuzzer_pass_outline_functions.h"
@@ -137,6 +138,7 @@
REPEATED_PASS_INSTANCE(InvertComparisonOperators);
REPEATED_PASS_INSTANCE(MakeVectorOperationsDynamic);
REPEATED_PASS_INSTANCE(MergeBlocks);
+ REPEATED_PASS_INSTANCE(MergeFunctionReturns);
REPEATED_PASS_INSTANCE(MutatePointers);
REPEATED_PASS_INSTANCE(ObfuscateConstants);
REPEATED_PASS_INSTANCE(OutlineFunctions);
diff --git a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
index 8597de2..8894353 100644
--- a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
+++ b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
@@ -188,8 +188,10 @@
if (&pass == pass_instances_->GetDonateModules()) {
// - New functions in the module can be called
// - Donated dead functions produce irrelevant ids, which can be replaced
+ // - Donated functions are good candidates for having their returns merged
return RandomOrderAndNonNull({pass_instances_->GetAddFunctionCalls(),
- pass_instances_->GetReplaceIrrelevantIds()});
+ pass_instances_->GetReplaceIrrelevantIds(),
+ pass_instances_->GetMergeFunctionReturns()});
}
if (&pass == pass_instances_->GetDuplicateRegionsWithSelections()) {
// - Parts of duplicated regions can be outlined
@@ -221,6 +223,11 @@
// different way
return RandomOrderAndNonNull({pass_instances_->GetSplitBlocks()});
}
+ if (&pass == pass_instances_->GetMergeFunctionReturns()) {
+ // - Functions without early returns are more likely to be able to be
+ // inlined.
+ return RandomOrderAndNonNull({pass_instances_->GetInlineFunctions()});
+ }
if (&pass == pass_instances_->GetMutatePointers()) {
// - This creates irrelevant ids, which can be replaced
return RandomOrderAndNonNull({pass_instances_->GetReplaceIrrelevantIds()});
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index de2f843..bebe848 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -381,6 +381,58 @@
uint32 value_to_copy_id = 7;
}
+message ReturnMergingInfo {
+ // TransformationMergeFunctionReturns needs to modify each merge block of
+ // loops containing return instructions, by:
+ // - adding instructions to decide whether the function is returning
+ // - adding instructions to pass on the return value of the function,
+ // if it is returning
+ // - changing the branch instruction (which must be an unconditional branch)
+ // to a conditional branch that, if the function is returning, branches to
+ // the merge block of the innermost loop that contains this merge block
+ // (which can be the new merge block introduced by the transformation).
+ //
+ // One such merge block of the form:
+ // %block = OpLabel
+ // %phi1 = OpPhi %type1 %val1_1 %pred1 %val1_2 %pred2
+ // %phi2 = OpPhi %type2 %val2_1 %pred1 %val2_2 %pred2
+ // OpBranch %next
+ //
+ // is transformed into:
+ // %block = OpLabel
+ // %is_returning_id = OpPhi %bool %false %pred1 %false %pred2 %true %ret_bb1 %is_bb2_returning %mer_bb2
+ // %maybe_return_val_id = OpPhi %return_type %any_returnable_val %pred1 %any_returnable_val %pred2
+ // %ret_val1 %ret_bb1 %ret_val2 %mer_bb2
+ // %phi1 = OpPhi %type1 %val1_1 %pred1 %val1_2 %pred2
+ // %any_suitable_id_1 %ret_bb1 %any_suitable_id_1 %mer_bb2
+ // %phi2 = OpPhi %type2 %val2_1 %pred1 %val2_2 %pred2
+ // %any_suitable_id_1 %ret_bb1 %any_suitable_id_1 %mer_bb2
+ // OpBranchConditional %is_returning_id %innermost_loop_merge %next
+ //
+ // where %ret_bb1 is a block that originally contains a return instruction and %mer_bb2 is the merge block of an inner
+ // loop, from where the function might be returning.
+ //
+ // Note that the block is required to only have OpLabel, OpPhi or OpBranch instructions.
+
+ // The id of the merge block that needs to be modified.
+ uint32 merge_block_id = 1;
+
+ // A fresh id for a boolean OpPhi whose value will be true iff the function
+ // is returning. This will be used to decide whether to break out of the loop
+ // or to use the original branch of the function. This value will also be
+ // used by the merge block of the enclosing loop (if there is one) if the
+ // function is returning from this block.
+ uint32 is_returning_id = 2;
+
+ // A fresh id that will get the value being returned, if the function is
+ // returning. If the function return type is void, this is ignored.
+ uint32 maybe_return_val_id = 3;
+
+ // A mapping from each existing OpPhi id to a suitable id of the same type
+ // available to use before the instruction.
+ repeated UInt32Pair opphi_to_suitable_id = 4;
+}
+
message LoopLimiterInfo {
// Structure capturing the information required to manipulate a loop limiter
@@ -1489,6 +1541,65 @@
}
+message TransformationMergeFunctionReturns {
+
+ // A transformation that modifies a function so that it does not return early,
+ // so it only has one return statement (ignoring unreachable blocks).
+ //
+ // The function is enclosed inside an outer loop, that is only executed once,
+ // and whose merge block is the new return block of the function.
+ //
+ // Each return instruction is replaced by:
+ // OpBranch %innermost_loop_merge
+ // where %innermost_loop_merge is the innermost loop containing the return
+ // instruction.
+ //
+ // Each merge block whose associated loop contains return instructions is
+ // changed so that it branches to the merge block of the loop containing it,
+ // as explained in the comments to the ReturnMergingInfo message.
+ //
+ // The new return block (the merge block of the new outer loop) will be of
+ // the following form (if the return type is not void):
+ // %outer_return_id = OpLabel
+ // %return_val_id = OpPhi %return_type %val1 %block_1 %val2 %block_2 ...
+ // OpReturnValue %return_val_id
+ // where %block_k is either a return block that, in the original function, is
+ // outside of any loops, or the merge block of a loop that contains return
+ // instructions and is not, originally, nested inside another loop, and
+ // %block_k is the corresponding return value.
+ // If the function has void type, there will be no OpPhi instruction and the
+ // last instruction will be OpReturn.
+
+ // The id of the function to which the transformation is being applied.
+ uint32 function_id = 1;
+
+ // A fresh id for the header of the new outer loop.
+ uint32 outer_header_id = 2;
+
+ // A fresh id for the new return block of the function,
+ // i.e. the merge block of the new outer loop.
+ uint32 outer_return_id = 3;
+
+ // A fresh id for the value that will be returned.
+ // This is ignored if the function has void return type.
+ uint32 return_val_id = 4;
+
+ // An existing id of the same type as the return value, which is
+ // available to use at the end of the entry block.
+ // This is ignored if the function has void return type or if no
+ // loops in the function contain a return instruction.
+ // If the function is not void, the transformation will add an
+ // OpPhi instruction to each merge block whose associated loop
+ // contains at least a return instruction. The value associated
+ // with existing predecessors from which the function cannot be
+ // returning will be this id, used as a placeholder.
+ uint32 any_returnable_val_id = 5;
+
+ // The information needed to modify the merge blocks of
+ // loops containing return instructions.
+ repeated ReturnMergingInfo return_merging_info = 6;
+}
+
message TransformationMoveBlockDown {
// A transformation that moves a basic block to be one position lower in
diff --git a/source/fuzz/transformation_flatten_conditional_branch.h b/source/fuzz/transformation_flatten_conditional_branch.h
index 2edbb46..fd8c1f5 100644
--- a/source/fuzz/transformation_flatten_conditional_branch.h
+++ b/source/fuzz/transformation_flatten_conditional_branch.h
@@ -12,8 +12,8 @@
// See the License for the specific language governing permissions and
// limitations under the License.
-#ifndef SOURCE_FUZZ_TRANSFORMATION_FLATTEN_CONDITIONAL_BRANCH_H
-#define SOURCE_FUZZ_TRANSFORMATION_FLATTEN_CONDITIONAL_BRANCH_H
+#ifndef SOURCE_FUZZ_TRANSFORMATION_FLATTEN_CONDITIONAL_BRANCH_H_
+#define SOURCE_FUZZ_TRANSFORMATION_FLATTEN_CONDITIONAL_BRANCH_H_
#include "source/fuzz/transformation.h"
@@ -119,4 +119,4 @@
} // namespace fuzz
} // namespace spvtools
-#endif // SOURCE_FUZZ_TRANSFORMATION_FLATTEN_CONDITIONAL_BRANCH_H
+#endif // SOURCE_FUZZ_TRANSFORMATION_FLATTEN_CONDITIONAL_BRANCH_H_
diff --git a/source/fuzz/transformation_merge_function_returns.cpp b/source/fuzz/transformation_merge_function_returns.cpp
new file mode 100644
index 0000000..390adb3
--- /dev/null
+++ b/source/fuzz/transformation_merge_function_returns.cpp
@@ -0,0 +1,816 @@
+// Copyright (c) 2020 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/fuzz/transformation_merge_function_returns.h"
+
+#include "source/fuzz/comparator_deep_blocks_first.h"
+#include "source/fuzz/fuzzer_util.h"
+
+namespace spvtools {
+namespace fuzz {
+
+TransformationMergeFunctionReturns::TransformationMergeFunctionReturns(
+ const protobufs::TransformationMergeFunctionReturns& message)
+ : message_(message) {}
+
+TransformationMergeFunctionReturns::TransformationMergeFunctionReturns(
+ uint32_t function_id, uint32_t outer_header_id, uint32_t outer_return_id,
+ uint32_t return_val_id, uint32_t any_returnable_val_id,
+ const std::vector<protobufs::ReturnMergingInfo>& returns_merging_info) {
+ message_.set_function_id(function_id);
+ message_.set_outer_header_id(outer_header_id);
+ message_.set_outer_return_id(outer_return_id);
+ message_.set_return_val_id(return_val_id);
+ message_.set_any_returnable_val_id(any_returnable_val_id);
+ for (const auto& return_merging_info : returns_merging_info) {
+ *message_.add_return_merging_info() = return_merging_info;
+ }
+}
+
+bool TransformationMergeFunctionReturns::IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const {
+ auto function = ir_context->GetFunction(message_.function_id());
+ // The function must exist.
+ if (!function) {
+ return false;
+ }
+
+ // The entry block must end in an unconditional branch.
+ if (function->entry()->terminator()->opcode() != SpvOpBranch) {
+ return false;
+ }
+
+ // The module must contain an OpConstantTrue instruction.
+ if (!fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
+ true, false)) {
+ return false;
+ }
+
+ // The module must contain an OpConstantFalse instruction.
+ if (!fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
+ false, false)) {
+ return false;
+ }
+
+ // Check that the fresh ids provided are fresh and distinct.
+ std::set<uint32_t> used_fresh_ids;
+ for (uint32_t id : {message_.outer_header_id(), message_.outer_return_id()}) {
+ if (!id || !CheckIdIsFreshAndNotUsedByThisTransformation(id, ir_context,
+ &used_fresh_ids)) {
+ return false;
+ }
+ }
+
+ // Check the additional fresh id required if the function is not void.
+ auto function_type = ir_context->get_type_mgr()->GetType(function->type_id());
+ assert(function_type && "The function type should always exist.");
+
+ if (!function_type->AsVoid() &&
+ (!message_.return_val_id() ||
+ !CheckIdIsFreshAndNotUsedByThisTransformation(
+ message_.return_val_id(), ir_context, &used_fresh_ids))) {
+ return false;
+ }
+
+ // Get a map from the types for which ids are available at the end of the
+ // entry block to one of the ids with that type. We compute this here to avoid
+ // potentially doing it multiple times later on.
+ auto types_to_available_ids =
+ GetTypesToIdAvailableAfterEntryBlock(ir_context);
+
+ // Get the reachable return blocks.
+ auto return_blocks =
+ fuzzerutil::GetReachableReturnBlocks(ir_context, message_.function_id());
+
+ // Map each merge block of loops containing reachable return blocks to the
+ // corresponding returning predecessors (all the blocks that, at the end of
+ // the transformation, will branch to the merge block because the function is
+ // returning).
+ std::map<uint32_t, std::set<uint32_t>> merge_blocks_to_returning_preds;
+ for (uint32_t block : return_blocks) {
+ uint32_t merge_block =
+ ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(block);
+
+ while (merge_block != 0) {
+ // If we have seen this merge block before, update the corresponding set
+ // and break out of the loop.
+ if (merge_blocks_to_returning_preds.count(merge_block)) {
+ merge_blocks_to_returning_preds[merge_block].emplace(block);
+ break;
+ }
+
+ // If we have not seen this merge block before, add a new entry and walk
+ // up the loop tree.
+ merge_blocks_to_returning_preds.emplace(merge_block,
+ std::set<uint32_t>({block}));
+
+ // Walk up the loop tree.
+ block = merge_block;
+ merge_block =
+ ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(merge_block);
+ }
+ }
+
+ // Instructions in the relevant merge blocks must be restricted to OpLabel,
+ // OpPhi and OpBranch.
+ for (const auto& merge_block_entry : merge_blocks_to_returning_preds) {
+ uint32_t merge_block = merge_block_entry.first;
+ bool all_instructions_allowed =
+ ir_context->get_instr_block(merge_block)
+ ->WhileEachInst([](opt::Instruction* inst) {
+ return inst->opcode() == SpvOpLabel ||
+ inst->opcode() == SpvOpPhi ||
+ inst->opcode() == SpvOpBranch;
+ });
+ if (!all_instructions_allowed) {
+ return false;
+ }
+ }
+
+ auto merge_blocks_to_info = GetMappingOfMergeBlocksToInfo();
+
+ // For each relevant merge block, check that the correct ids are available.
+ for (const auto& merge_block_entry : merge_blocks_to_returning_preds) {
+ if (!CheckThatTheCorrectIdsAreGivenForMergeBlock(
+ merge_block_entry.first, merge_blocks_to_info,
+ types_to_available_ids, function_type->AsVoid(), ir_context,
+ transformation_context, &used_fresh_ids)) {
+ return false;
+ }
+ }
+
+ // If the function has a non-void return type, and there are merge loops which
+ // contain return instructions, we need to check that either:
+ // - |message_.any_returnable_val_id| exists. In this case, it must have the
+ // same type as the return type of the function and be available at the end
+ // of the entry block.
+ // - a suitable id, available at the end of the entry block can be found in
+ // the module.
+ if (!function_type->AsVoid() && !merge_blocks_to_returning_preds.empty()) {
+ auto returnable_val_def =
+ ir_context->get_def_use_mgr()->GetDef(message_.any_returnable_val_id());
+ if (!returnable_val_def) {
+ // Check if a suitable id can be found in the module.
+ if (types_to_available_ids.count(function->type_id()) == 0) {
+ return false;
+ }
+ } else if (returnable_val_def->type_id() != function->type_id()) {
+ return false;
+ } else if (!fuzzerutil::IdIsAvailableBeforeInstruction(
+ ir_context, function->entry()->terminator(),
+ message_.any_returnable_val_id())) {
+ // The id must be available at the end of the entry block.
+ return false;
+ }
+ }
+
+ // Check that adding new predecessors to the relevant merge blocks does not
+ // render any instructions invalid (each id definition must still dominate
+ // each of its uses).
+ if (!CheckDefinitionsStillDominateUsesAfterAddingNewPredecessors(
+ ir_context, function, merge_blocks_to_returning_preds)) {
+ return false;
+ }
+
+ return true;
+}
+
+void TransformationMergeFunctionReturns::Apply(
+ opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const {
+ auto function = ir_context->GetFunction(message_.function_id());
+ auto function_type = ir_context->get_type_mgr()->GetType(function->type_id());
+
+ // Get a map from the types for which ids are available at the end of the
+ // entry block to one of the ids with that type. We compute this here to avoid
+ // potentially doing it multiple times later on.
+ auto types_to_available_ids =
+ GetTypesToIdAvailableAfterEntryBlock(ir_context);
+
+ uint32_t bool_type = fuzzerutil::MaybeGetBoolType(ir_context);
+
+ uint32_t constant_true = fuzzerutil::MaybeGetBoolConstant(
+ ir_context, *transformation_context, true, false);
+
+ uint32_t constant_false = fuzzerutil::MaybeGetBoolConstant(
+ ir_context, *transformation_context, false, false);
+
+ // Get the reachable return blocks.
+ auto return_blocks =
+ fuzzerutil::GetReachableReturnBlocks(ir_context, message_.function_id());
+
+ // Keep a map from the relevant merge blocks to a mapping from each of the
+ // returning predecessors to the corresponding pair (return value,
+ // boolean specifying whether the function is returning). Returning
+ // predecessors are blocks in the loop (not further nested inside loops),
+ // which either return or are merge blocks of nested loops containing return
+ // instructions.
+ std::map<uint32_t, std::map<uint32_t, std::pair<uint32_t, uint32_t>>>
+ merge_blocks_to_returning_predecessors;
+
+ // Initialise the map, mapping each relevant merge block to an empty map.
+ for (uint32_t ret_block_id : return_blocks) {
+ uint32_t merge_block_id =
+ ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(ret_block_id);
+
+ while (merge_block_id != 0 &&
+ !merge_blocks_to_returning_predecessors.count(merge_block_id)) {
+ merge_blocks_to_returning_predecessors.emplace(
+ merge_block_id, std::map<uint32_t, std::pair<uint32_t, uint32_t>>());
+ merge_block_id = ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(
+ merge_block_id);
+ }
+ }
+
+ // Get a reference to an instruction with the same type id as the function's
+ // return type, if the type of the function is not void and ther are loops
+ // containing return instructions.
+ uint32_t returnable_val_id = 0;
+ if (!function_type->AsVoid() &&
+ !merge_blocks_to_returning_predecessors.empty()) {
+ // If |message.any_returnable_val_id| can be found in the module, use it.
+ // Otherwise, use another suitable id found in the module.
+ auto returnable_val_def =
+ ir_context->get_def_use_mgr()->GetDef(message_.any_returnable_val_id());
+ returnable_val_id = returnable_val_def
+ ? returnable_val_def->result_id()
+ : types_to_available_ids[function->type_id()];
+ }
+
+ // Keep a map from all the new predecessors of the merge block of the new
+ // outer loop, to the related return value ids.
+ std::map<uint32_t, uint32_t> outer_merge_predecessors;
+
+ // Adjust the return blocks and add the related information to the map or
+ // |outer_merge_predecessors| set.
+ for (uint32_t ret_block_id : return_blocks) {
+ auto ret_block = ir_context->get_instr_block(ret_block_id);
+
+ // Get the return value id (if the function is not void).
+ uint32_t ret_val_id =
+ function_type->AsVoid()
+ ? 0
+ : ret_block->terminator()->GetSingleWordInOperand(0);
+
+ uint32_t merge_block_id =
+ ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(ret_block_id);
+
+ // Add a new entry to the map corresponding to the merge block of the
+ // innermost enclosing loop (or that of the new outer loop if there is no
+ // enclosing loop).
+ if (merge_block_id != 0) {
+ merge_blocks_to_returning_predecessors[merge_block_id].emplace(
+ ret_block_id,
+ std::pair<uint32_t, uint32_t>(ret_val_id, constant_true));
+ } else {
+ // If there is no enclosing loop, the block will branch to the merge block
+ // of the new outer loop.
+ merge_block_id = message_.outer_return_id();
+ outer_merge_predecessors.emplace(ret_block_id, ret_val_id);
+ }
+
+ // Replace the return instruction with an unconditional branch.
+ ret_block->terminator()->SetOpcode(SpvOpBranch);
+ ret_block->terminator()->SetInOperands(
+ {{SPV_OPERAND_TYPE_RESULT_ID, {merge_block_id}}});
+ }
+
+ // Get a list of all the relevant merge blocks.
+ std::vector<uint32_t> merge_blocks;
+ merge_blocks.reserve(merge_blocks_to_returning_predecessors.size());
+ for (const auto& entry : merge_blocks_to_returning_predecessors) {
+ merge_blocks.emplace_back(entry.first);
+ }
+
+ // Sort the list so that deeper merge blocks come first.
+ // We need to consider deeper merge blocks first so that, when a merge block
+ // is considered, all the merge blocks enclosed by the corresponding loop have
+ // already been considered and, thus, the mapping from this merge block to the
+ // returning predecessors is complete.
+ std::sort(merge_blocks.begin(), merge_blocks.end(),
+ ComparatorDeepBlocksFirst(ir_context));
+
+ auto merge_blocks_to_info = GetMappingOfMergeBlocksToInfo();
+
+ // Adjust the merge blocks and add the related information to the map or
+ // |outer_merge_predecessors| set.
+ for (uint32_t merge_block_id : merge_blocks) {
+ // Get the info corresponding to |merge_block| from the map, if a
+ // corresponding entry exists. Otherwise use overflow ids and find suitable
+ // ids in the module.
+ protobufs::ReturnMergingInfo* info =
+ merge_blocks_to_info.count(merge_block_id)
+ ? &merge_blocks_to_info[merge_block_id]
+ : nullptr;
+
+ uint32_t is_returning_id =
+ info ? info->is_returning_id()
+ : transformation_context->GetOverflowIdSource()
+ ->GetNextOverflowId();
+
+ uint32_t maybe_return_val_id = 0;
+ if (!function_type->AsVoid()) {
+ maybe_return_val_id = info ? info->maybe_return_val_id()
+ : transformation_context->GetOverflowIdSource()
+ ->GetNextOverflowId();
+ }
+
+ // Map from existing OpPhi to overflow ids. If there is no mapping, get an
+ // empty map.
+ auto phi_to_id = info ? fuzzerutil::RepeatedUInt32PairToMap(
+ *merge_blocks_to_info[merge_block_id]
+ .mutable_opphi_to_suitable_id())
+ : std::map<uint32_t, uint32_t>();
+
+ // Get a reference to the info related to the returning predecessors.
+ const auto& returning_preds =
+ merge_blocks_to_returning_predecessors[merge_block_id];
+
+ // Get a set of the original predecessors.
+ auto preds_list = ir_context->cfg()->preds(merge_block_id);
+ auto preds = std::set<uint32_t>(preds_list.begin(), preds_list.end());
+
+ auto merge_block = ir_context->get_instr_block(merge_block_id);
+
+ // Adjust the existing OpPhi instructions.
+ merge_block->ForEachPhiInst([&preds, &returning_preds, &phi_to_id,
+ &types_to_available_ids](
+ opt::Instruction* inst) {
+ // We need a placeholder value id. If |phi_to_id| contains a mapping
+ // for this instruction, we use the given id, otherwise a suitable id
+ // for the instruction's type from |types_to_available_ids|.
+ uint32_t placeholder_val_id =
+ phi_to_id.count(inst->result_id())
+ ? phi_to_id[inst->result_id()]
+ : types_to_available_ids[inst->type_id()];
+ assert(placeholder_val_id &&
+ "We should always be able to find a suitable if the "
+ "transformation is applicable.");
+
+ // Add a pair of operands (placeholder id, new predecessor) for each
+ // new predecessor of the merge block.
+ for (const auto& entry : returning_preds) {
+ // A returning predecessor may already be a predecessor of the
+ // block. In that case, we should not add new operands.
+ // Each entry is in the form (predecessor, {return val, is returning}).
+ if (!preds.count(entry.first)) {
+ inst->AddOperand({SPV_OPERAND_TYPE_RESULT_ID, {placeholder_val_id}});
+ inst->AddOperand({SPV_OPERAND_TYPE_RESULT_ID, {entry.first}});
+ }
+ }
+ });
+
+ // If the function is not void, add a new OpPhi instructions to collect the
+ // return value from the returning predecessors.
+ if (!function_type->AsVoid()) {
+ opt::Instruction::OperandList operand_list;
+
+ // Add two operands (return value, predecessor) for each returning
+ // predecessor.
+ for (auto entry : returning_preds) {
+ // Each entry is in the form (predecessor, {return value,
+ // is returning}).
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_RESULT_ID, {entry.second.first}});
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_RESULT_ID, {entry.first}});
+ }
+
+ // Add two operands for each original predecessor from which the function
+ // does not return.
+ for (uint32_t original_pred : preds) {
+ // Only add operands if the function cannot be returning from this
+ // block.
+ if (returning_preds.count(original_pred)) {
+ continue;
+ }
+
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_RESULT_ID, {returnable_val_id}});
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_RESULT_ID, {original_pred}});
+ }
+
+ // Insert the instruction.
+ merge_block->begin()->InsertBefore(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpPhi, function->type_id(), maybe_return_val_id,
+ std::move(operand_list)));
+
+ fuzzerutil::UpdateModuleIdBound(ir_context, maybe_return_val_id);
+ }
+
+ // Add an OpPhi instruction deciding whether the function is returning.
+ {
+ opt::Instruction::OperandList operand_list;
+
+ // Add two operands (return value, is returning) for each returning
+ // predecessor.
+ for (auto entry : returning_preds) {
+ // Each entry is in the form (predecessor, {return value,
+ // is returning}).
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_RESULT_ID, {entry.second.second}});
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_RESULT_ID, {entry.first}});
+ }
+
+ // Add two operands for each original predecessor from which the function
+ // does not return.
+ for (uint32_t original_pred : preds) {
+ // Only add operands if the function cannot be returning from this
+ // block.
+ if (returning_preds.count(original_pred)) {
+ continue;
+ }
+
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_RESULT_ID, {constant_false}});
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_RESULT_ID, {original_pred}});
+ }
+
+ // Insert the instruction.
+ merge_block->begin()->InsertBefore(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpPhi, bool_type, is_returning_id,
+ std::move(operand_list)));
+
+ fuzzerutil::UpdateModuleIdBound(ir_context, is_returning_id);
+ }
+
+ // Change the branching instruction of the block.
+ assert(merge_block->terminator()->opcode() == SpvOpBranch &&
+ "Each block should branch unconditionally to the next.");
+
+ // Add a new entry to the map corresponding to the merge block of the
+ // innermost enclosing loop (or that of the new outer loop if there is no
+ // enclosing loop).
+ uint32_t enclosing_merge =
+ ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(merge_block_id);
+ if (enclosing_merge == 0) {
+ enclosing_merge = message_.outer_return_id();
+ outer_merge_predecessors.emplace(merge_block_id, maybe_return_val_id);
+ } else {
+ merge_blocks_to_returning_predecessors[enclosing_merge].emplace(
+ merge_block_id,
+ std::pair<uint32_t, uint32_t>(maybe_return_val_id, is_returning_id));
+ }
+
+ // Get the current successor.
+ uint32_t original_succ =
+ merge_block->terminator()->GetSingleWordInOperand(0);
+ // Leave the instruction as it is if the block already branches to the merge
+ // block of the enclosing loop.
+ if (original_succ == enclosing_merge) {
+ continue;
+ }
+
+ // The block should branch to |enclosing_merge| if |is_returning_id| is
+ // true, to |original_succ| otherwise.
+ merge_block->terminator()->SetOpcode(SpvOpBranchConditional);
+ merge_block->terminator()->SetInOperands(
+ {{SPV_OPERAND_TYPE_RESULT_ID, {is_returning_id}},
+ {SPV_OPERAND_TYPE_RESULT_ID, {enclosing_merge}},
+ {SPV_OPERAND_TYPE_RESULT_ID, {original_succ}}});
+ }
+
+ assert(function->entry()->terminator()->opcode() == SpvOpBranch &&
+ "The entry block should branch unconditionally to another block.");
+ uint32_t block_after_entry =
+ function->entry()->terminator()->GetSingleWordInOperand(0);
+
+ // Create the header for the new outer loop.
+ auto outer_loop_header =
+ MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpLabel, 0, message_.outer_header_id(),
+ opt::Instruction::OperandList()));
+
+ fuzzerutil::UpdateModuleIdBound(ir_context, message_.outer_header_id());
+
+ // Add the instruction: OpLoopMerge %outer_return_id %outer_header_id None
+ // The header is the continue block of the outer loop.
+ outer_loop_header->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpLoopMerge, 0, 0,
+ opt::Instruction::OperandList{
+ {SPV_OPERAND_TYPE_RESULT_ID, {message_.outer_return_id()}},
+ {SPV_OPERAND_TYPE_RESULT_ID, {message_.outer_header_id()}},
+ {SPV_OPERAND_TYPE_LOOP_CONTROL, {SpvLoopControlMaskNone}}}));
+
+ // Add conditional branch:
+ // OpBranchConditional %true %block_after_entry %outer_header_id
+ // This will always branch to %block_after_entry, but it also creates a back
+ // edge for the loop (which is never traversed).
+ outer_loop_header->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpBranchConditional, 0, 0,
+ opt::Instruction::OperandList{
+ {SPV_OPERAND_TYPE_RESULT_ID, {constant_true}},
+ {SPV_OPERAND_TYPE_RESULT_ID, {block_after_entry}},
+ {SPV_OPERAND_TYPE_LOOP_CONTROL, {message_.outer_header_id()}}}));
+
+ // Insert the header right after the entry block.
+ function->InsertBasicBlockAfter(std::move(outer_loop_header),
+ function->entry().get());
+
+ // Update the branching instruction of the entry block.
+ function->entry()->terminator()->SetInOperands(
+ {{SPV_OPERAND_TYPE_RESULT_ID, {message_.outer_header_id()}}});
+
+ // Create the merge block for the loop (and return block for the function).
+ auto outer_return_block =
+ MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpLabel, 0, message_.outer_return_id(),
+ opt::Instruction::OperandList()));
+
+ fuzzerutil::UpdateModuleIdBound(ir_context, message_.outer_return_id());
+
+ // If the function is not void, insert an instruction to collect the return
+ // value from the predecessors and an OpReturnValue instruction.
+ if (!function_type->AsVoid()) {
+ opt::Instruction::OperandList operand_list;
+
+ // Add two operands (return value, predecessor) for each predecessor.
+ for (auto entry : outer_merge_predecessors) {
+ // Each entry is in the form (predecessor, return value).
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_RESULT_ID, {entry.second}});
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_RESULT_ID, {entry.first}});
+ }
+
+ // Insert the OpPhi instruction.
+ outer_return_block->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpPhi, function->type_id(), message_.return_val_id(),
+ std::move(operand_list)));
+
+ fuzzerutil::UpdateModuleIdBound(ir_context, message_.return_val_id());
+
+ // Insert the OpReturnValue instruction.
+ outer_return_block->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpReturnValue, 0, 0,
+ opt::Instruction::OperandList{
+ {SPV_OPERAND_TYPE_RESULT_ID, {message_.return_val_id()}}}));
+ } else {
+ // Insert an OpReturn instruction (the function is void).
+ outer_return_block->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpReturn, 0, 0, opt::Instruction::OperandList{}));
+ }
+
+ // Insert the new return block at the end of the function.
+ function->AddBasicBlock(std::move(outer_return_block));
+
+ // All analyses must be invalidated because the structure of the module was
+ // changed.
+ ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+}
+
+std::unordered_set<uint32_t> TransformationMergeFunctionReturns::GetFreshIds()
+ const {
+ std::unordered_set<uint32_t> result;
+ result.emplace(message_.outer_header_id());
+ result.emplace(message_.outer_return_id());
+ // |message_.return_val_info| can be 0 if the function is void.
+ if (message_.return_val_id()) {
+ result.emplace(message_.return_val_id());
+ }
+
+ for (auto merging_info : message_.return_merging_info()) {
+ result.emplace(merging_info.is_returning_id());
+ // |maybe_return_val_id| can be 0 if the function is void.
+ if (merging_info.maybe_return_val_id()) {
+ result.emplace(merging_info.maybe_return_val_id());
+ }
+ }
+
+ return result;
+}
+
+protobufs::Transformation TransformationMergeFunctionReturns::ToMessage()
+ const {
+ return protobufs::Transformation();
+}
+
+std::map<uint32_t, protobufs::ReturnMergingInfo>
+TransformationMergeFunctionReturns::GetMappingOfMergeBlocksToInfo() const {
+ std::map<uint32_t, protobufs::ReturnMergingInfo> result;
+ for (const auto& info : message_.return_merging_info()) {
+ result.emplace(info.merge_block_id(), info);
+ }
+ return result;
+}
+
+std::map<uint32_t, uint32_t>
+TransformationMergeFunctionReturns::GetTypesToIdAvailableAfterEntryBlock(
+ opt::IRContext* ir_context) const {
+ std::map<uint32_t, uint32_t> result;
+ // Consider all global declarations
+ for (auto& global : ir_context->module()->types_values()) {
+ if (global.HasResultId() && global.type_id()) {
+ result.emplace(global.type_id(), global.result_id());
+ }
+ }
+
+ auto function = ir_context->GetFunction(message_.function_id());
+ assert(function && "The function must exist.");
+
+ // Consider all function parameters
+ function->ForEachParam([&result](opt::Instruction* param) {
+ if (param->HasResultId() && param->type_id()) {
+ result.emplace(param->type_id(), param->result_id());
+ }
+ });
+
+ // Consider all the instructions in the entry block.
+ for (auto& inst : *function->entry()) {
+ if (inst.HasResultId() && inst.type_id()) {
+ result.emplace(inst.type_id(), inst.result_id());
+ }
+ }
+
+ return result;
+}
+
+bool TransformationMergeFunctionReturns::
+ CheckDefinitionsStillDominateUsesAfterAddingNewPredecessors(
+ opt::IRContext* ir_context, const opt::Function* function,
+ const std::map<uint32_t, std::set<uint32_t>>&
+ merge_blocks_to_new_predecessors) {
+ for (const auto& merge_block_entry : merge_blocks_to_new_predecessors) {
+ uint32_t merge_block = merge_block_entry.first;
+ const auto& returning_preds = merge_block_entry.second;
+
+ // Find a list of blocks in which there might be problematic definitions.
+ // These are all the blocks that dominate the merge block but do not
+ // dominate all of the new predecessors.
+ std::vector<opt::BasicBlock*> problematic_blocks;
+
+ auto dominator_analysis = ir_context->GetDominatorAnalysis(function);
+
+ // Start from the immediate dominator of the merge block.
+ auto current_block = dominator_analysis->ImmediateDominator(merge_block);
+ assert(current_block &&
+ "Each merge block should have at least one dominator.");
+
+ for (uint32_t pred : returning_preds) {
+ while (!dominator_analysis->Dominates(current_block->id(), pred)) {
+ // The current block does not dominate all of the new predecessor
+ // blocks, so it might be problematic.
+ problematic_blocks.emplace_back(current_block);
+
+ // Walk up the dominator tree.
+ current_block = dominator_analysis->ImmediateDominator(current_block);
+ assert(current_block &&
+ "We should be able to find a dominator for all the blocks, "
+ "since they must all be dominated at least by the header.");
+ }
+ }
+
+ // Identify the loop header corresponding to the merge block.
+ uint32_t loop_header =
+ fuzzerutil::GetLoopFromMergeBlock(ir_context, merge_block);
+
+ // For all the ids defined in blocks inside |problematic_blocks|, check that
+ // all their uses are either:
+ // - inside the loop (or in the loop header). If this is the case, the path
+ // from the definition to the use does not go through the merge block, so
+ // adding new predecessor to it is not a problem.
+ // - inside an OpPhi instruction in the merge block. If this is the case,
+ // the definition does not need to dominate the merge block.
+ for (auto block : problematic_blocks) {
+ assert((block->id() == loop_header ||
+ ir_context->GetStructuredCFGAnalysis()->ContainingLoop(
+ block->id()) == loop_header) &&
+ "The problematic blocks should all be inside the loop (also "
+ "considering the header).");
+ bool dominance_rules_maintained =
+ block->WhileEachInst([ir_context, loop_header,
+ merge_block](opt::Instruction* instruction) {
+ // Instruction without a result id do not cause any problems.
+ if (!instruction->HasResultId()) {
+ return true;
+ }
+
+ // Check that all the uses of the id are inside the loop.
+ return ir_context->get_def_use_mgr()->WhileEachUse(
+ instruction->result_id(),
+ [ir_context, loop_header, merge_block](
+ opt::Instruction* inst_use, uint32_t /* unused */) {
+ uint32_t block_use =
+ ir_context->get_instr_block(inst_use)->id();
+
+ // The usage is OK if it is inside the loop (including the
+ // header).
+ if (block_use == loop_header ||
+ ir_context->GetStructuredCFGAnalysis()->ContainingLoop(
+ block_use)) {
+ return true;
+ }
+
+ // The usage is OK if it is inside an OpPhi instruction in the
+ // merge block.
+ return block_use == merge_block &&
+ inst_use->opcode() == SpvOpPhi;
+ });
+ });
+
+ // If not all instructions in the block satisfy the requirement, the
+ // transformation is not applicable.
+ if (!dominance_rules_maintained) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+bool TransformationMergeFunctionReturns::
+ CheckThatTheCorrectIdsAreGivenForMergeBlock(
+ uint32_t merge_block,
+ const std::map<uint32_t, protobufs::ReturnMergingInfo>&
+ merge_blocks_to_info,
+ const std::map<uint32_t, uint32_t>& types_to_available_id,
+ bool function_is_void, opt::IRContext* ir_context,
+ const TransformationContext& transformation_context,
+ std::set<uint32_t>* used_fresh_ids) {
+ // A map from OpPhi ids to ids of the same type available at the beginning
+ // of the merge block.
+ std::map<uint32_t, uint32_t> phi_to_id;
+
+ if (merge_blocks_to_info.count(merge_block) > 0) {
+ // If the map contains an entry for the merge block, check that the fresh
+ // ids are fresh and distinct.
+ auto info = merge_blocks_to_info.at(merge_block);
+ if (!info.is_returning_id() ||
+ !CheckIdIsFreshAndNotUsedByThisTransformation(
+ info.is_returning_id(), ir_context, used_fresh_ids)) {
+ return false;
+ }
+
+ if (!function_is_void &&
+ (!info.maybe_return_val_id() ||
+ !CheckIdIsFreshAndNotUsedByThisTransformation(
+ info.maybe_return_val_id(), ir_context, used_fresh_ids))) {
+ return false;
+ }
+
+ // Get the mapping from OpPhis to suitable ids.
+ phi_to_id = fuzzerutil::RepeatedUInt32PairToMap(
+ *info.mutable_opphi_to_suitable_id());
+ } else {
+ // If the map does not contain an entry for the merge block, check that
+ // overflow ids are available.
+ if (!transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
+ return false;
+ }
+ }
+
+ // For each OpPhi instruction, check that a suitable placeholder id is
+ // available.
+ bool suitable_info_for_phi =
+ ir_context->get_instr_block(merge_block)
+ ->WhileEachPhiInst([ir_context, &phi_to_id,
+ &types_to_available_id](opt::Instruction* inst) {
+ if (phi_to_id.count(inst->result_id()) > 0) {
+ // If there exists a mapping for this instruction and the
+ // placeholder id exists in the module, check that it has the
+ // correct type and it is available before the instruction.
+ auto placeholder_def = ir_context->get_def_use_mgr()->GetDef(
+ phi_to_id[inst->result_id()]);
+ if (placeholder_def) {
+ if (inst->type_id() != placeholder_def->type_id()) {
+ return false;
+ }
+ if (!fuzzerutil::IdIsAvailableBeforeInstruction(
+ ir_context, inst, placeholder_def->result_id())) {
+ return false;
+ }
+
+ return true;
+ }
+ }
+
+ // If there is no mapping, check if there is a suitable id
+ // available at the end of the entry block.
+ return types_to_available_id.count(inst->type_id()) > 0;
+ });
+
+ if (!suitable_info_for_phi) {
+ return false;
+ }
+
+ return true;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/transformation_merge_function_returns.h b/source/fuzz/transformation_merge_function_returns.h
new file mode 100644
index 0000000..4b29936
--- /dev/null
+++ b/source/fuzz/transformation_merge_function_returns.h
@@ -0,0 +1,115 @@
+// Copyright (c) 2020 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SOURCE_FUZZ_TRANSFORMATION_MERGE_FUNCTION_RETURNS_
+#define SOURCE_FUZZ_TRANSFORMATION_MERGE_FUNCTION_RETURNS_
+
+#include "source/fuzz/transformation.h"
+
+namespace spvtools {
+namespace fuzz {
+class TransformationMergeFunctionReturns : public Transformation {
+ public:
+ explicit TransformationMergeFunctionReturns(
+ const protobufs::TransformationMergeFunctionReturns& message);
+
+ TransformationMergeFunctionReturns(
+ uint32_t function_id, uint32_t outer_header_id, uint32_t outer_return_id,
+ uint32_t return_val_id, uint32_t any_returnable_val_id,
+ const std::vector<protobufs::ReturnMergingInfo>& returns_merging_info);
+
+ // - |message_.function_id| is the id of a function.
+ // - The entry block of |message_.function_id| branches unconditionally to
+ // another block.
+ // - |message_.any_returnable_val_id| is an id whose type is the same as the
+ // return type of the function and which is available at the end of the
+ // entry block. If this id is not found in the module, the transformation
+ // will try to find a suitable one.
+ // If the function is void, or no loops in the function contain return
+ // statements, this id will be ignored.
+ // - Merge blocks of reachable loops that contain return statements only
+ // consist of OpLabel, OpPhi or OpBranch instructions.
+ // - The model contains OpConstantTrue and OpConstantFalse instructions.
+ // - For all merge blocks of reachable loops that contain return statements,
+ // either:
+ // - a mapping is provided in |message_.return_merging_info|, all of the
+ // corresponding fresh ids are valid and, for each OpPhi instruction in
+ // the block, there is a mapping to an available id of the same type in
+ // |opphi_to_suitable_id| or a suitable id, available at the end of the
+ // entry block, can be found in the module.
+ // - there is no mapping, but overflow ids are available and, for every
+ // OpPhi instruction in the merge blocks that need to be modified, a
+ // suitable id, available at the end of the entry block, can be found.
+ // - The addition of new predecessors to the relevant merge blocks does not
+ // cause any id use to be invalid (i.e. every id must dominate all its uses
+ // even after the transformation has added new branches).
+ // - All of the fresh ids that are provided and needed by the transformation
+ // are valid.
+ bool IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const override;
+
+ // Changes the function so that there is only one reachable return
+ // instruction. The function is enclosed by an outer loop, whose merge block
+ // is the new return block. All existing return statements are replaced by
+ // branch instructions to the merge block of the loop enclosing them, and
+ // OpPhi instructions are used to keep track of the return value and of
+ // whether the function is returning.
+ void Apply(opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const override;
+
+ std::unordered_set<uint32_t> GetFreshIds() const override;
+
+ protobufs::Transformation ToMessage() const override;
+
+ private:
+ // Returns a map from merge block ids to the corresponding info in
+ // |message_.return_merging_info|.
+ std::map<uint32_t, protobufs::ReturnMergingInfo>
+ GetMappingOfMergeBlocksToInfo() const;
+
+ // Returns a map from type ids to an id with that type and which is available
+ // at the end of the entry block of |message_.function_id|.
+ // Assumes that the function exists.
+ std::map<uint32_t, uint32_t> GetTypesToIdAvailableAfterEntryBlock(
+ opt::IRContext* ir_context) const;
+
+ // Returns true if adding new predecessors to the given loop merge blocks
+ // does not render any instructions invalid (each id definition must still
+ // dominate all of its uses). The loop merge blocks and corresponding new
+ // predecessors to consider are given in |merge_blocks_to_new_predecessors|.
+ // All of the new predecessors are assumed to be inside the loop associated
+ // with the corresponding loop merge block.
+ static bool CheckDefinitionsStillDominateUsesAfterAddingNewPredecessors(
+ opt::IRContext* ir_context, const opt::Function* function,
+ const std::map<uint32_t, std::set<uint32_t>>&
+ merge_blocks_to_new_predecessors);
+
+ // Returns true if the required ids for |merge_block| are provided in the
+ // |merge_blocks_to_info| map, or if ids of the suitable type can be found.
+ static bool CheckThatTheCorrectIdsAreGivenForMergeBlock(
+ uint32_t merge_block,
+ const std::map<uint32_t, protobufs::ReturnMergingInfo>&
+ merge_blocks_to_info,
+ const std::map<uint32_t, uint32_t>& types_to_available_id,
+ bool function_is_void, opt::IRContext* ir_context,
+ const TransformationContext& transformation_context,
+ std::set<uint32_t>* used_fresh_ids);
+
+ protobufs::TransformationMergeFunctionReturns message_;
+};
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_TRANSFORMATION_MERGE_FUNCTION_RETURNS_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index 924addb..e287d8d 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -75,6 +75,7 @@
transformation_load_test.cpp
transformation_make_vector_operation_dynamic_test.cpp
transformation_merge_blocks_test.cpp
+ transformation_merge_function_returns_test.cpp
transformation_move_block_down_test.cpp
transformation_move_instruction_down_test.cpp
transformation_mutate_pointer_test.cpp
diff --git a/test/fuzz/transformation_merge_function_returns_test.cpp b/test/fuzz/transformation_merge_function_returns_test.cpp
new file mode 100644
index 0000000..2c8d949
--- /dev/null
+++ b/test/fuzz/transformation_merge_function_returns_test.cpp
@@ -0,0 +1,1784 @@
+// Copyright (c) 2020 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/fuzz/transformation_merge_function_returns.h"
+
+#include "source/fuzz/counter_overflow_id_source.h"
+#include "source/fuzz/fuzzer_util.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+protobufs::ReturnMergingInfo MakeReturnMergingInfo(
+ uint32_t merge_block_id, uint32_t is_returning_id,
+ uint32_t maybe_return_val_id,
+ std::map<uint32_t, uint32_t> opphi_to_suitable_id) {
+ protobufs::ReturnMergingInfo result;
+ result.set_merge_block_id(merge_block_id);
+ result.set_is_returning_id(is_returning_id);
+ result.set_maybe_return_val_id(maybe_return_val_id);
+ *result.mutable_opphi_to_suitable_id() =
+ fuzzerutil::MapToRepeatedUInt32Pair(opphi_to_suitable_id);
+ return result;
+}
+
+TEST(TransformationMergeFunctionReturnsTest, SimpleInapplicable) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypeFunction %5
+ %7 = OpTypeFloat 32
+ %8 = OpTypeFunction %7
+ %9 = OpTypeBool
+ %10 = OpConstantTrue %9
+ %11 = OpConstantFalse %9
+ %12 = OpConstant %5 0
+ %13 = OpConstant %5 1
+ %2 = OpFunction %3 None %4
+ %14 = OpLabel
+ %15 = OpFunctionCall %3 %16
+ %17 = OpFunctionCall %3 %18
+ %19 = OpFunctionCall %3 %20
+ %21 = OpFunctionCall %7 %22
+ OpReturn
+ OpFunctionEnd
+ %16 = OpFunction %3 None %4
+ %23 = OpLabel
+ OpSelectionMerge %24 None
+ OpBranchConditional %10 %25 %26
+ %25 = OpLabel
+ OpReturn
+ %26 = OpLabel
+ OpReturn
+ %24 = OpLabel
+ OpUnreachable
+ OpFunctionEnd
+ %18 = OpFunction %3 None %4
+ %27 = OpLabel
+ OpBranch %28
+ %28 = OpLabel
+ OpLoopMerge %29 %30 None
+ OpBranch %31
+ %31 = OpLabel
+ OpBranchConditional %10 %32 %29
+ %32 = OpLabel
+ OpReturn
+ %30 = OpLabel
+ OpBranch %28
+ %29 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %20 = OpFunction %3 None %4
+ %33 = OpLabel
+ OpBranch %34
+ %34 = OpLabel
+ OpLoopMerge %35 %36 None
+ OpBranch %37
+ %37 = OpLabel
+ OpBranchConditional %10 %38 %35
+ %38 = OpLabel
+ OpReturn
+ %36 = OpLabel
+ OpBranch %34
+ %35 = OpLabel
+ %39 = OpFunctionCall %3 %18
+ OpReturn
+ OpFunctionEnd
+ %22 = OpFunction %7 None %8
+ %40 = OpLabel
+ OpBranch %51
+ %51 = OpLabel
+ OpLoopMerge %41 %53 None
+ OpBranchConditional %10 %42 %41
+ %42 = OpLabel
+ %43 = OpConvertSToF %7 %12
+ OpReturnValue %43
+ %41 = OpLabel
+ %44 = OpConvertSToF %7 %13
+ OpReturnValue %44
+ %53 = OpLabel
+ OpBranch %51
+ OpFunctionEnd
+ %45 = OpFunction %5 None %6
+ %46 = OpLabel
+ OpBranch %52
+ %52 = OpLabel
+ %47 = OpConvertSToF %7 %13
+ OpLoopMerge %48 %54 None
+ OpBranchConditional %10 %49 %48
+ %49 = OpLabel
+ OpReturnValue %12
+ %48 = OpLabel
+ %50 = OpCopyObject %5 %12
+ OpReturnValue %13
+ %54 = OpLabel
+ OpBranch %52
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ // Function %1 does not exist.
+ ASSERT_FALSE(TransformationMergeFunctionReturns(1, 100, 101, 0, 0, {{}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // The entry block (%22) of function %15 does not branch unconditionally to
+ // the following block.
+ ASSERT_FALSE(TransformationMergeFunctionReturns(16, 100, 101, 0, 0, {{}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Block %28 is the merge block of a loop containing a return instruction, but
+ // it contains an OpReturn instruction (so, it contains instructions that are
+ // not OpLabel, OpPhi or OpBranch).
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 18, 100, 101, 0, 0, {{MakeReturnMergingInfo(29, 102, 0, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Block %34 is the merge block of a loop containing a return instruction, but
+ // it contains an OpFunctionCall instruction (so, it contains instructions
+ // that are not OpLabel, OpPhi or OpBranch).
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 20, 100, 101, 0, 0, {{MakeReturnMergingInfo(35, 102, 0, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Id %1000 cannot be found in the module and there is no id of the correct
+ // type (float) available at the end of the entry block of function %21.
+ ASSERT_FALSE(TransformationMergeFunctionReturns(22, 100, 101, 102, 1000, {{}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Id %47 is of type float, while function %45 has return type int.
+ ASSERT_FALSE(TransformationMergeFunctionReturns(45, 100, 101, 102, 47, {{}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Id %50 is not available at the end of the entry block of function %45.
+ ASSERT_FALSE(TransformationMergeFunctionReturns(45, 100, 101, 102, 50, {{}})
+ .IsApplicable(context.get(), transformation_context));
+}
+
+TEST(TransformationMergeFunctionReturnsTest, MissingBooleans) {
+ {
+ // OpConstantTrue is missing.
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ OpName %3 "A("
+ OpDecorate %3 RelaxedPrecision
+ OpDecorate %4 RelaxedPrecision
+ %5 = OpTypeVoid
+ %6 = OpTypeFunction %5
+ %7 = OpTypeInt 32 1
+ %8 = OpTypeFunction %7
+ %9 = OpTypeBool
+ %10 = OpConstantFalse %9
+ %11 = OpConstant %7 1
+ %12 = OpConstant %7 2
+ %2 = OpFunction %5 None %6
+ %13 = OpLabel
+ %4 = OpFunctionCall %7 %3
+ OpReturn
+ OpFunctionEnd
+ %3 = OpFunction %7 None %8
+ %14 = OpLabel
+ OpBranch %15
+ %15 = OpLabel
+ OpSelectionMerge %16 None
+ OpBranchConditional %10 %17 %16
+ %17 = OpLabel
+ OpReturnValue %11
+ %16 = OpLabel
+ OpReturnValue %12
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context =
+ BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ ASSERT_FALSE(TransformationMergeFunctionReturns(3, 100, 101, 0, 0, {{}})
+ .IsApplicable(context.get(), transformation_context));
+ }
+ {
+ // OpConstantFalse is missing.
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ OpName %3 "A("
+ OpDecorate %3 RelaxedPrecision
+ OpDecorate %4 RelaxedPrecision
+ %5 = OpTypeVoid
+ %6 = OpTypeFunction %5
+ %7 = OpTypeInt 32 1
+ %8 = OpTypeFunction %7
+ %9 = OpTypeBool
+ %10 = OpConstantTrue %9
+ %11 = OpConstant %7 1
+ %12 = OpConstant %7 2
+ %2 = OpFunction %5 None %6
+ %13 = OpLabel
+ %4 = OpFunctionCall %7 %3
+ OpReturn
+ OpFunctionEnd
+ %3 = OpFunction %7 None %8
+ %14 = OpLabel
+ OpBranch %15
+ %15 = OpLabel
+ OpSelectionMerge %16 None
+ OpBranchConditional %10 %17 %16
+ %17 = OpLabel
+ OpReturnValue %11
+ %16 = OpLabel
+ OpReturnValue %12
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context =
+ BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ ASSERT_FALSE(TransformationMergeFunctionReturns(3, 100, 101, 0, 0, {{}})
+ .IsApplicable(context.get(), transformation_context));
+ }
+}
+
+TEST(TransformationMergeFunctionReturnsTest, InvalidIds) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypeFunction %5
+ %42 = OpTypeFloat 32
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %9 = OpConstantFalse %7
+ %10 = OpConstant %5 0
+ %11 = OpConstant %5 1
+ %2 = OpFunction %3 None %4
+ %12 = OpLabel
+ %13 = OpFunctionCall %5 %14
+ %15 = OpFunctionCall %3 %16
+ OpReturn
+ OpFunctionEnd
+ %17 = OpFunction %3 None %4
+ %18 = OpLabel
+ OpBranch %19
+ %19 = OpLabel
+ OpLoopMerge %20 %21 None
+ OpBranch %22
+ %22 = OpLabel
+ OpBranchConditional %8 %23 %20
+ %23 = OpLabel
+ OpReturn
+ %21 = OpLabel
+ OpBranch %19
+ %20 = OpLabel
+ OpBranch %24
+ %24 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %14 = OpFunction %5 None %6
+ %25 = OpLabel
+ OpBranch %26
+ %26 = OpLabel
+ OpLoopMerge %27 %28 None
+ OpBranch %29
+ %29 = OpLabel
+ OpBranchConditional %8 %30 %27
+ %30 = OpLabel
+ OpReturnValue %10
+ %28 = OpLabel
+ OpBranch %26
+ %27 = OpLabel
+ OpBranch %33
+ %33 = OpLabel
+ OpReturnValue %11
+ OpFunctionEnd
+ %16 = OpFunction %3 None %4
+ %34 = OpLabel
+ OpBranch %35
+ %35 = OpLabel
+ OpLoopMerge %36 %37 None
+ OpBranch %38
+ %38 = OpLabel
+ %43 = OpConvertSToF %42 %10
+ OpBranchConditional %8 %39 %36
+ %39 = OpLabel
+ OpReturn
+ %37 = OpLabel
+ %44 = OpConvertSToF %42 %10
+ OpBranch %35
+ %36 = OpLabel
+ %31 = OpPhi %42 %43 %38
+ %32 = OpPhi %5 %11 %38
+ OpBranch %40
+ %40 = OpLabel
+ %41 = OpFunctionCall %3 %17
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ // Fresh id %100 is used twice.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 17, 100, 100, 0, 0, {{MakeReturnMergingInfo(20, 101, 0, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Fresh id %100 is used twice.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 17, 100, 101, 0, 0, {{MakeReturnMergingInfo(20, 100, 0, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %0 cannot be a fresh id for the new merge block.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 17, 100, 0, 0, 0, {{MakeReturnMergingInfo(20, 101, 0, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %0 cannot be a fresh id for the new header block.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 17, 0, 100, 0, 0, {{MakeReturnMergingInfo(20, 101, 0, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %0 cannot be a fresh id for the new |is_returning| instruction in an
+ // existing merge block.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 17, 100, 101, 0, 0, {{MakeReturnMergingInfo(20, 0, 0, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %0 cannot be a fresh id for the new |return_val| instruction in the new
+ // return block.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 14, 100, 101, 0, 10, {{MakeReturnMergingInfo(27, 102, 103, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %0 cannot be a fresh id for the new |maybe_return_val| instruction in an
+ // existing merge block, inside a non-void function.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 14, 100, 101, 102, 10, {{MakeReturnMergingInfo(27, 103, 0, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Fresh id %102 is repeated.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 14, 100, 101, 102, 10, {{MakeReturnMergingInfo(27, 102, 104, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Id %11 (type int) does not have the correct type (float) for OpPhi
+ // instruction %31.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 16, 100, 101, 0, 0,
+ {{MakeReturnMergingInfo(36, 103, 104, {{{31, 11}, {32, 11}}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Id %11 (type int) does not have the correct type (float) for OpPhi
+ // instruction %31.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 16, 100, 101, 0, 0,
+ {{MakeReturnMergingInfo(36, 102, 0, {{{31, 11}, {32, 11}}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Id %43 is not available at the end of the entry block.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 16, 100, 101, 0, 0,
+ {{MakeReturnMergingInfo(36, 102, 0, {{{31, 44}, {32, 11}}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // There is not a mapping for id %31 (float OpPhi instruction in a loop merge
+ // block) and no suitable id is available at the end of the entry block.
+ ASSERT_FALSE(TransformationMergeFunctionReturns(
+ 16, 100, 101, 0, 0,
+ {{MakeReturnMergingInfo(36, 102, 0, {{{32, 11}}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Id %1000 cannot be found in the module and no suitable id for OpPhi %31 is
+ // available at the end of the entry block.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 16, 100, 101, 0, 0,
+ {{MakeReturnMergingInfo(36, 102, 0, {{{31, 1000}, {32, 11}}})}})
+ .IsApplicable(context.get(), transformation_context));
+}
+
+TEST(TransformationMergeFunctionReturnsTest, Simple) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypeFunction %5
+ %7 = OpTypeFloat 32
+ %8 = OpTypeFunction %7 %7
+ %9 = OpTypeFunction %7
+ %10 = OpTypeBool
+ %11 = OpConstantTrue %10
+ %40 = OpConstantFalse %10
+ %12 = OpConstant %5 1
+ %2 = OpFunction %3 None %4
+ %13 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %14 = OpFunction %3 None %4
+ %15 = OpLabel
+ OpBranch %16
+ %16 = OpLabel
+ OpSelectionMerge %17 None
+ OpBranchConditional %11 %18 %17
+ %18 = OpLabel
+ OpReturn
+ %17 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %19 = OpFunction %5 None %6
+ %20 = OpLabel
+ OpBranch %21
+ %21 = OpLabel
+ OpSelectionMerge %22 None
+ OpBranchConditional %11 %23 %24
+ %23 = OpLabel
+ OpReturnValue %12
+ %24 = OpLabel
+ %25 = OpIAdd %5 %12 %12
+ OpReturnValue %25
+ %22 = OpLabel
+ OpUnreachable
+ OpFunctionEnd
+ %26 = OpFunction %7 None %8
+ %27 = OpFunctionParameter %7
+ %28 = OpLabel
+ OpBranch %29
+ %29 = OpLabel
+ OpSelectionMerge %30 None
+ OpBranchConditional %11 %31 %30
+ %31 = OpLabel
+ %32 = OpFAdd %7 %27 %27
+ OpReturnValue %32
+ %30 = OpLabel
+ OpReturnValue %27
+ OpFunctionEnd
+ %33 = OpFunction %7 None %9
+ %34 = OpLabel
+ %35 = OpConvertSToF %7 %12
+ OpBranch %36
+ %36 = OpLabel
+ OpSelectionMerge %37 None
+ OpBranchConditional %11 %38 %37
+ %38 = OpLabel
+ %39 = OpFAdd %7 %35 %35
+ OpReturnValue %39
+ %37 = OpLabel
+ OpReturnValue %35
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ // The 0s are allowed because the function's return type is void.
+ auto transformation1 =
+ TransformationMergeFunctionReturns(14, 100, 101, 0, 0, {{}});
+ ASSERT_TRUE(
+ transformation1.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation1, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // %12 is available at the end of the entry block of %19 (it is a global
+ // variable).
+ ASSERT_TRUE(TransformationMergeFunctionReturns(19, 110, 111, 112, 12, {{}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %1000 cannot be found in the module, but there is a suitable id available
+ // at the end of the entry block (%12).
+ auto transformation2 =
+ TransformationMergeFunctionReturns(19, 110, 111, 112, 1000, {{}});
+ ASSERT_TRUE(
+ transformation2.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation2, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // %27 is available at the end of the entry block of %26 (it is a function
+ // parameter).
+ ASSERT_TRUE(TransformationMergeFunctionReturns(26, 120, 121, 122, 27, {{}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %1000 cannot be found in the module, but there is a suitable id available
+ // at the end of the entry block (%27).
+ auto transformation3 =
+ TransformationMergeFunctionReturns(26, 120, 121, 122, 1000, {{}});
+ ASSERT_TRUE(
+ transformation3.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation3, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // %35 is available at the end of the entry block of %33 (it is in the entry
+ // block).
+ ASSERT_TRUE(TransformationMergeFunctionReturns(26, 130, 131, 132, 27, {{}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %1000 cannot be found in the module, but there is a suitable id available
+ // at the end of the entry block (%35).
+ auto transformation4 =
+ TransformationMergeFunctionReturns(33, 130, 131, 132, 1000, {{}});
+ ASSERT_TRUE(
+ transformation4.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation4, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_transformations = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypeFunction %5
+ %7 = OpTypeFloat 32
+ %8 = OpTypeFunction %7 %7
+ %9 = OpTypeFunction %7
+ %10 = OpTypeBool
+ %11 = OpConstantTrue %10
+ %40 = OpConstantFalse %10
+ %12 = OpConstant %5 1
+ %2 = OpFunction %3 None %4
+ %13 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %14 = OpFunction %3 None %4
+ %15 = OpLabel
+ OpBranch %100
+ %100 = OpLabel
+ OpLoopMerge %101 %100 None
+ OpBranchConditional %11 %16 %100
+ %16 = OpLabel
+ OpSelectionMerge %17 None
+ OpBranchConditional %11 %18 %17
+ %18 = OpLabel
+ OpBranch %101
+ %17 = OpLabel
+ OpBranch %101
+ %101 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %19 = OpFunction %5 None %6
+ %20 = OpLabel
+ OpBranch %110
+ %110 = OpLabel
+ OpLoopMerge %111 %110 None
+ OpBranchConditional %11 %21 %110
+ %21 = OpLabel
+ OpSelectionMerge %22 None
+ OpBranchConditional %11 %23 %24
+ %23 = OpLabel
+ OpBranch %111
+ %24 = OpLabel
+ %25 = OpIAdd %5 %12 %12
+ OpBranch %111
+ %22 = OpLabel
+ OpUnreachable
+ %111 = OpLabel
+ %112 = OpPhi %5 %12 %23 %25 %24
+ OpReturnValue %112
+ OpFunctionEnd
+ %26 = OpFunction %7 None %8
+ %27 = OpFunctionParameter %7
+ %28 = OpLabel
+ OpBranch %120
+ %120 = OpLabel
+ OpLoopMerge %121 %120 None
+ OpBranchConditional %11 %29 %120
+ %29 = OpLabel
+ OpSelectionMerge %30 None
+ OpBranchConditional %11 %31 %30
+ %31 = OpLabel
+ %32 = OpFAdd %7 %27 %27
+ OpBranch %121
+ %30 = OpLabel
+ OpBranch %121
+ %121 = OpLabel
+ %122 = OpPhi %7 %27 %30 %32 %31
+ OpReturnValue %122
+ OpFunctionEnd
+ %33 = OpFunction %7 None %9
+ %34 = OpLabel
+ %35 = OpConvertSToF %7 %12
+ OpBranch %130
+ %130 = OpLabel
+ OpLoopMerge %131 %130 None
+ OpBranchConditional %11 %36 %130
+ %36 = OpLabel
+ OpSelectionMerge %37 None
+ OpBranchConditional %11 %38 %37
+ %38 = OpLabel
+ %39 = OpFAdd %7 %35 %35
+ OpBranch %131
+ %37 = OpLabel
+ OpBranch %131
+ %131 = OpLabel
+ %132 = OpPhi %7 %35 %37 %39 %38
+ OpReturnValue %132
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformations, context.get()));
+}
+
+TEST(TransformationMergeFunctionReturnsTest, NestedLoops) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypeFunction %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %9 = OpConstantFalse %7
+ %10 = OpConstant %5 2
+ %11 = OpConstant %5 1
+ %12 = OpConstant %5 3
+ %2 = OpFunction %3 None %4
+ %13 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %14 = OpFunction %5 None %6
+ %15 = OpLabel
+ OpBranch %16
+ %16 = OpLabel
+ OpLoopMerge %17 %16 None
+ OpBranchConditional %8 %18 %16
+ %18 = OpLabel
+ OpLoopMerge %19 %20 None
+ OpBranchConditional %8 %19 %21
+ %19 = OpLabel
+ OpBranch %17
+ %21 = OpLabel
+ OpReturnValue %12
+ %17 = OpLabel
+ OpBranch %22
+ %20 = OpLabel
+ OpBranch %18
+ %22 = OpLabel
+ OpLoopMerge %23 %24 None
+ OpBranch %25
+ %25 = OpLabel
+ OpBranchConditional %8 %26 %23
+ %26 = OpLabel
+ OpSelectionMerge %27 None
+ OpBranchConditional %9 %28 %27
+ %28 = OpLabel
+ OpBranch %29
+ %29 = OpLabel
+ OpLoopMerge %30 %29 None
+ OpBranchConditional %8 %30 %29
+ %30 = OpLabel
+ OpLoopMerge %31 %32 None
+ OpBranch %33
+ %33 = OpLabel
+ OpBranchConditional %9 %34 %31
+ %34 = OpLabel
+ OpReturnValue %10
+ %32 = OpLabel
+ OpBranch %30
+ %31 = OpLabel
+ %35 = OpPhi %5 %11 %33
+ %36 = OpPhi %5 %10 %33
+ OpBranch %37
+ %37 = OpLabel
+ OpReturnValue %35
+ %27 = OpLabel
+ OpBranch %24
+ %24 = OpLabel
+ OpBranch %22
+ %23 = OpLabel
+ OpBranch %38
+ %38 = OpLabel
+ OpReturnValue %12
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ auto transformation = TransformationMergeFunctionReturns(
+ 14, 100, 101, 102, 11,
+ {{MakeReturnMergingInfo(19, 103, 104, {{}}),
+ MakeReturnMergingInfo(17, 105, 106, {{}}),
+ MakeReturnMergingInfo(31, 107, 108, {{{35, 10}, {36, 12}}}),
+ MakeReturnMergingInfo(23, 109, 110, {})}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypeFunction %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %9 = OpConstantFalse %7
+ %10 = OpConstant %5 2
+ %11 = OpConstant %5 1
+ %12 = OpConstant %5 3
+ %2 = OpFunction %3 None %4
+ %13 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %14 = OpFunction %5 None %6
+ %15 = OpLabel
+ OpBranch %100
+ %100 = OpLabel
+ OpLoopMerge %101 %100 None
+ OpBranchConditional %8 %16 %100
+ %16 = OpLabel
+ OpLoopMerge %17 %16 None
+ OpBranchConditional %8 %18 %16
+ %18 = OpLabel
+ OpLoopMerge %19 %20 None
+ OpBranchConditional %8 %19 %21
+ %19 = OpLabel
+ %103 = OpPhi %7 %8 %21 %9 %18
+ %104 = OpPhi %5 %12 %21 %11 %18
+ OpBranch %17
+ %21 = OpLabel
+ OpBranch %19
+ %17 = OpLabel
+ %105 = OpPhi %7 %103 %19
+ %106 = OpPhi %5 %104 %19
+ OpBranchConditional %105 %101 %22
+ %20 = OpLabel
+ OpBranch %18
+ %22 = OpLabel
+ OpLoopMerge %23 %24 None
+ OpBranch %25
+ %25 = OpLabel
+ OpBranchConditional %8 %26 %23
+ %26 = OpLabel
+ OpSelectionMerge %27 None
+ OpBranchConditional %9 %28 %27
+ %28 = OpLabel
+ OpBranch %29
+ %29 = OpLabel
+ OpLoopMerge %30 %29 None
+ OpBranchConditional %8 %30 %29
+ %30 = OpLabel
+ OpLoopMerge %31 %32 None
+ OpBranch %33
+ %33 = OpLabel
+ OpBranchConditional %9 %34 %31
+ %34 = OpLabel
+ OpBranch %31
+ %32 = OpLabel
+ OpBranch %30
+ %31 = OpLabel
+ %107 = OpPhi %7 %8 %34 %9 %33
+ %108 = OpPhi %5 %10 %34 %11 %33
+ %35 = OpPhi %5 %11 %33 %10 %34
+ %36 = OpPhi %5 %10 %33 %12 %34
+ OpBranchConditional %107 %23 %37
+ %37 = OpLabel
+ OpBranch %23
+ %27 = OpLabel
+ OpBranch %24
+ %24 = OpLabel
+ OpBranch %22
+ %23 = OpLabel
+ %109 = OpPhi %7 %107 %31 %8 %37 %9 %25
+ %110 = OpPhi %5 %108 %31 %35 %37 %11 %25
+ OpBranchConditional %109 %101 %38
+ %38 = OpLabel
+ OpBranch %101
+ %101 = OpLabel
+ %102 = OpPhi %5 %106 %17 %110 %23 %12 %38
+ OpReturnValue %102
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationMergeFunctionReturnsTest, OverflowIds) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypeFunction %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %9 = OpConstantFalse %7
+ %10 = OpConstant %5 1
+ %2 = OpFunction %3 None %4
+ %11 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %12 = OpFunction %5 None %6
+ %13 = OpLabel
+ OpBranch %14
+ %14 = OpLabel
+ %15 = OpIAdd %5 %10 %10
+ OpLoopMerge %16 %17 None
+ OpBranch %18
+ %18 = OpLabel
+ OpBranchConditional %8 %19 %16
+ %19 = OpLabel
+ OpSelectionMerge %20 None
+ OpBranchConditional %9 %21 %20
+ %21 = OpLabel
+ OpReturnValue %10
+ %20 = OpLabel
+ OpBranch %17
+ %17 = OpLabel
+ OpBranchConditional %8 %14 %16
+ %16 = OpLabel
+ %22 = OpPhi %5 %15 %17 %10 %18
+ OpBranch %23
+ %23 = OpLabel
+ OpReturnValue %22
+ OpFunctionEnd
+ %24 = OpFunction %3 None %4
+ %25 = OpLabel
+ OpBranch %26
+ %26 = OpLabel
+ OpLoopMerge %27 %28 None
+ OpBranch %29
+ %29 = OpLabel
+ OpBranchConditional %8 %30 %27
+ %30 = OpLabel
+ OpSelectionMerge %31 None
+ OpBranchConditional %9 %32 %31
+ %32 = OpLabel
+ OpReturn
+ %31 = OpLabel
+ OpBranch %28
+ %28 = OpLabel
+ OpBranch %26
+ %27 = OpLabel
+ %33 = OpPhi %5 %10 %29
+ OpBranch %34
+ %34 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ auto overflow_ids_unique_ptr = MakeUnique<CounterOverflowIdSource>(1000);
+ auto overflow_ids_ptr = overflow_ids_unique_ptr.get();
+ TransformationContext transformation_context_with_overflow_ids(
+ MakeUnique<FactManager>(context.get()), validator_options,
+ std::move(overflow_ids_unique_ptr));
+
+ // No mapping from merge block %16 to fresh ids is given, so overflow ids are
+ // needed.
+ auto transformation1 =
+ TransformationMergeFunctionReturns(12, 100, 101, 102, 10, {{}});
+
+#ifndef NDEBUG
+ ASSERT_DEATH(
+ transformation1.IsApplicable(context.get(), transformation_context),
+ "Bad attempt to query whether overflow ids are available.");
+#endif
+
+ ASSERT_TRUE(transformation1.IsApplicable(
+ context.get(), transformation_context_with_overflow_ids));
+ ApplyAndCheckFreshIds(transformation1, context.get(),
+ &transformation_context_with_overflow_ids,
+ overflow_ids_ptr->GetIssuedOverflowIds());
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // No mapping from merge block %27 to fresh ids is given, so overflow ids are
+ // needed.
+ auto transformation2 =
+ TransformationMergeFunctionReturns(24, 110, 111, 0, 0, {{}});
+
+#ifndef NDEBUG
+ ASSERT_DEATH(
+ transformation2.IsApplicable(context.get(), transformation_context),
+ "Bad attempt to query whether overflow ids are available.");
+#endif
+
+ ASSERT_TRUE(transformation2.IsApplicable(
+ context.get(), transformation_context_with_overflow_ids));
+ ApplyAndCheckFreshIds(transformation2, context.get(),
+ &transformation_context_with_overflow_ids, {1002});
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_transformations = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypeFunction %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %9 = OpConstantFalse %7
+ %10 = OpConstant %5 1
+ %2 = OpFunction %3 None %4
+ %11 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %12 = OpFunction %5 None %6
+ %13 = OpLabel
+ OpBranch %100
+ %100 = OpLabel
+ OpLoopMerge %101 %100 None
+ OpBranchConditional %8 %14 %100
+ %14 = OpLabel
+ %15 = OpIAdd %5 %10 %10
+ OpLoopMerge %16 %17 None
+ OpBranch %18
+ %18 = OpLabel
+ OpBranchConditional %8 %19 %16
+ %19 = OpLabel
+ OpSelectionMerge %20 None
+ OpBranchConditional %9 %21 %20
+ %21 = OpLabel
+ OpBranch %16
+ %20 = OpLabel
+ OpBranch %17
+ %17 = OpLabel
+ OpBranchConditional %8 %14 %16
+ %16 = OpLabel
+ %1000 = OpPhi %7 %8 %21 %9 %17 %9 %18
+ %1001 = OpPhi %5 %10 %21 %10 %17 %10 %18
+ %22 = OpPhi %5 %15 %17 %10 %18 %10 %21
+ OpBranchConditional %1000 %101 %23
+ %23 = OpLabel
+ OpBranch %101
+ %101 = OpLabel
+ %102 = OpPhi %5 %1001 %16 %22 %23
+ OpReturnValue %102
+ OpFunctionEnd
+ %24 = OpFunction %3 None %4
+ %25 = OpLabel
+ OpBranch %110
+ %110 = OpLabel
+ OpLoopMerge %111 %110 None
+ OpBranchConditional %8 %26 %110
+ %26 = OpLabel
+ OpLoopMerge %27 %28 None
+ OpBranch %29
+ %29 = OpLabel
+ OpBranchConditional %8 %30 %27
+ %30 = OpLabel
+ OpSelectionMerge %31 None
+ OpBranchConditional %9 %32 %31
+ %32 = OpLabel
+ OpBranch %27
+ %31 = OpLabel
+ OpBranch %28
+ %28 = OpLabel
+ OpBranch %26
+ %27 = OpLabel
+ %1002 = OpPhi %7 %8 %32 %9 %29
+ %33 = OpPhi %5 %10 %29 %10 %32
+ OpBranchConditional %1002 %111 %34
+ %34 = OpLabel
+ OpBranch %111
+ %111 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformations, context.get()));
+}
+
+TEST(TransformationMergeFunctionReturnsTest, MissingIdsForOpPhi) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpConstantFalse %5
+ %8 = OpTypeInt 32 1
+ %9 = OpTypeFunction %3 %8
+ %10 = OpTypeFloat 32
+ %2 = OpFunction %3 None %4
+ %11 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %12 = OpFunction %3 None %9
+ %13 = OpFunctionParameter %8
+ %14 = OpLabel
+ %15 = OpConvertSToF %10 %13
+ OpBranch %16
+ %16 = OpLabel
+ OpLoopMerge %17 %18 None
+ OpBranch %19
+ %19 = OpLabel
+ OpBranchConditional %6 %20 %17
+ %20 = OpLabel
+ OpSelectionMerge %21 None
+ OpBranchConditional %7 %22 %21
+ %22 = OpLabel
+ OpReturn
+ %21 = OpLabel
+ OpBranch %18
+ %18 = OpLabel
+ OpBranch %16
+ %17 = OpLabel
+ %23 = OpPhi %8 %13 %19
+ %24 = OpPhi %10 %15 %19
+ %25 = OpPhi %5 %6 %19
+ OpBranch %26
+ %26 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ // This test checks whether the transformation is able to find suitable ids
+ // to use in existing OpPhi instructions if they are not provided in the
+ // corresponding mapping.
+
+ auto transformation = TransformationMergeFunctionReturns(
+ 12, 101, 102, 0, 0,
+ {{MakeReturnMergingInfo(17, 103, 0, {{{25, 7}, {35, 8}}})}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpConstantFalse %5
+ %8 = OpTypeInt 32 1
+ %9 = OpTypeFunction %3 %8
+ %10 = OpTypeFloat 32
+ %2 = OpFunction %3 None %4
+ %11 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %12 = OpFunction %3 None %9
+ %13 = OpFunctionParameter %8
+ %14 = OpLabel
+ %15 = OpConvertSToF %10 %13
+ OpBranch %101
+ %101 = OpLabel
+ OpLoopMerge %102 %101 None
+ OpBranchConditional %6 %16 %101
+ %16 = OpLabel
+ OpLoopMerge %17 %18 None
+ OpBranch %19
+ %19 = OpLabel
+ OpBranchConditional %6 %20 %17
+ %20 = OpLabel
+ OpSelectionMerge %21 None
+ OpBranchConditional %7 %22 %21
+ %22 = OpLabel
+ OpBranch %17
+ %21 = OpLabel
+ OpBranch %18
+ %18 = OpLabel
+ OpBranch %16
+ %17 = OpLabel
+ %103 = OpPhi %5 %6 %22 %7 %19
+ %23 = OpPhi %8 %13 %19 %13 %22
+ %24 = OpPhi %10 %15 %19 %15 %22
+ %25 = OpPhi %5 %6 %19 %7 %22
+ OpBranchConditional %103 %102 %26
+ %26 = OpLabel
+ OpBranch %102
+ %102 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationMergeFunctionReturnsTest, RespectDominanceRules1) {
+ // An id defined in a loop is used in the corresponding merge block. After the
+ // transformation, the id will not dominate the merge block anymore. This is
+ // only OK if the use is inside an OpPhi instruction. (Note that there is also
+ // another condition for this transformation that forbids non-OpPhi
+ // instructions in relevant merge blocks, but that case is also considered
+ // here for completeness).
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpConstantFalse %5
+ %2 = OpFunction %3 None %4
+ %8 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ OpLoopMerge %10 %11 None
+ OpBranch %12
+ %12 = OpLabel
+ OpSelectionMerge %13 None
+ OpBranchConditional %7 %13 %14
+ %14 = OpLabel
+ OpReturn
+ %13 = OpLabel
+ %15 = OpCopyObject %5 %7
+ OpBranch %11
+ %11 = OpLabel
+ OpBranchConditional %7 %9 %10
+ %10 = OpLabel
+ %16 = OpCopyObject %5 %15
+ OpBranch %17
+ %17 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %18 = OpFunction %3 None %4
+ %19 = OpLabel
+ OpBranch %20
+ %20 = OpLabel
+ OpLoopMerge %21 %22 None
+ OpBranch %23
+ %23 = OpLabel
+ OpSelectionMerge %24 None
+ OpBranchConditional %7 %24 %25
+ %25 = OpLabel
+ OpReturn
+ %24 = OpLabel
+ %26 = OpCopyObject %5 %7
+ OpBranch %22
+ %22 = OpLabel
+ OpBranchConditional %7 %20 %21
+ %21 = OpLabel
+ %27 = OpPhi %5 %26 %22
+ OpBranch %28
+ %28 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ // In function %2, the definition of id %15 will not dominate its use in
+ // instruction %16 (inside merge block %10) after a new branch from return
+ // block %14 is added.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 2, 100, 101, 0, 0, {{MakeReturnMergingInfo(10, 102, 103, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // In function %18, The definition of id %26 will still dominate its use in
+ // instruction %27 (inside merge block %21), because %27 is an OpPhi
+ // instruction.
+ auto transformation = TransformationMergeFunctionReturns(
+ 18, 100, 101, 0, 0, {{MakeReturnMergingInfo(21, 102, 103, {{}})}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpConstantFalse %5
+ %2 = OpFunction %3 None %4
+ %8 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ OpLoopMerge %10 %11 None
+ OpBranch %12
+ %12 = OpLabel
+ OpSelectionMerge %13 None
+ OpBranchConditional %7 %13 %14
+ %14 = OpLabel
+ OpReturn
+ %13 = OpLabel
+ %15 = OpCopyObject %5 %7
+ OpBranch %11
+ %11 = OpLabel
+ OpBranchConditional %7 %9 %10
+ %10 = OpLabel
+ %16 = OpCopyObject %5 %15
+ OpBranch %17
+ %17 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %18 = OpFunction %3 None %4
+ %19 = OpLabel
+ OpBranch %100
+ %100 = OpLabel
+ OpLoopMerge %101 %100 None
+ OpBranchConditional %6 %20 %100
+ %20 = OpLabel
+ OpLoopMerge %21 %22 None
+ OpBranch %23
+ %23 = OpLabel
+ OpSelectionMerge %24 None
+ OpBranchConditional %7 %24 %25
+ %25 = OpLabel
+ OpBranch %21
+ %24 = OpLabel
+ %26 = OpCopyObject %5 %7
+ OpBranch %22
+ %22 = OpLabel
+ OpBranchConditional %7 %20 %21
+ %21 = OpLabel
+ %102 = OpPhi %5 %6 %25 %7 %22
+ %27 = OpPhi %5 %26 %22 %6 %25
+ OpBranchConditional %102 %101 %28
+ %28 = OpLabel
+ OpBranch %101
+ %101 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationMergeFunctionReturnsTest, RespectDominanceRules2) {
+ // An id defined in a loop is used after the corresponding merge block. After
+ // the transformation, the id will not dominate its use anymore, regardless of
+ // the kind of instruction in which it is used.
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpConstantFalse %5
+ %2 = OpFunction %3 None %4
+ %8 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ OpLoopMerge %10 %11 None
+ OpBranch %12
+ %12 = OpLabel
+ OpSelectionMerge %13 None
+ OpBranchConditional %7 %13 %14
+ %14 = OpLabel
+ OpReturn
+ %13 = OpLabel
+ %15 = OpCopyObject %5 %7
+ OpBranch %11
+ %11 = OpLabel
+ OpBranchConditional %7 %9 %10
+ %10 = OpLabel
+ OpBranch %16
+ %16 = OpLabel
+ %17 = OpCopyObject %5 %15
+ OpReturn
+ OpFunctionEnd
+ %18 = OpFunction %3 None %4
+ %19 = OpLabel
+ OpBranch %20
+ %20 = OpLabel
+ OpLoopMerge %21 %22 None
+ OpBranch %23
+ %23 = OpLabel
+ OpSelectionMerge %24 None
+ OpBranchConditional %7 %24 %25
+ %25 = OpLabel
+ OpReturn
+ %24 = OpLabel
+ %26 = OpCopyObject %5 %7
+ OpBranch %22
+ %22 = OpLabel
+ OpBranchConditional %7 %20 %21
+ %21 = OpLabel
+ OpBranch %27
+ %27 = OpLabel
+ %28 = OpPhi %5 %26 %21
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ // In function %2, the definition of id %15 will not dominate its use in
+ // instruction %17 (inside block %16) after a new branch from return
+ // block %14 to merge block %10 is added.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 2, 100, 101, 0, 0, {{MakeReturnMergingInfo(10, 102, 103, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // In function %18, the definition of id %26 will not dominate its use in
+ // instruction %28 (inside block %27) after a new branch from return
+ // block %25 to merge block %21 is added.
+ ASSERT_FALSE(TransformationMergeFunctionReturns(
+ 2, 100, 101, 0, 0,
+ {{MakeReturnMergingInfo(10, 102, 0, {{}}),
+ MakeReturnMergingInfo(21, 103, 0, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+}
+
+TEST(TransformationMergeFunctionReturnsTest, RespectDominanceRules3) {
+ // An id defined in a loop is used inside the loop.
+ // Changes to the predecessors of the merge block do not affect the validity
+ // of the uses of such id.
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpConstantFalse %5
+ %2 = OpFunction %3 None %4
+ %8 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ OpLoopMerge %10 %11 None
+ OpBranch %12
+ %12 = OpLabel
+ OpSelectionMerge %13 None
+ OpBranchConditional %7 %13 %14
+ %14 = OpLabel
+ OpReturn
+ %13 = OpLabel
+ %15 = OpCopyObject %5 %7
+ OpSelectionMerge %16 None
+ OpBranchConditional %7 %16 %17
+ %17 = OpLabel
+ %18 = OpPhi %5 %15 %13
+ %19 = OpCopyObject %5 %15
+ OpBranch %16
+ %16 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ OpBranchConditional %7 %9 %10
+ %10 = OpLabel
+ OpBranch %20
+ %20 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ // In function %2, the definition of id %15 will still dominate its use in
+ // instructions %18 and %19 after the transformation is applied, because the
+ // fact that the id definition dominates the uses does not depend on it
+ // dominating the merge block.
+ auto transformation = TransformationMergeFunctionReturns(
+ 2, 100, 101, 0, 0, {{MakeReturnMergingInfo(10, 102, 103, {{}})}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpConstantFalse %5
+ %2 = OpFunction %3 None %4
+ %8 = OpLabel
+ OpBranch %100
+ %100 = OpLabel
+ OpLoopMerge %101 %100 None
+ OpBranchConditional %6 %9 %100
+ %9 = OpLabel
+ OpLoopMerge %10 %11 None
+ OpBranch %12
+ %12 = OpLabel
+ OpSelectionMerge %13 None
+ OpBranchConditional %7 %13 %14
+ %14 = OpLabel
+ OpBranch %10
+ %13 = OpLabel
+ %15 = OpCopyObject %5 %7
+ OpSelectionMerge %16 None
+ OpBranchConditional %7 %16 %17
+ %17 = OpLabel
+ %18 = OpPhi %5 %15 %13
+ %19 = OpCopyObject %5 %15
+ OpBranch %16
+ %16 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ OpBranchConditional %7 %9 %10
+ %10 = OpLabel
+ %102 = OpPhi %5 %6 %14 %7 %11
+ OpBranchConditional %102 %101 %20
+ %20 = OpLabel
+ OpBranch %101
+ %101 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationMergeFunctionReturnsTest, RespectDominanceRules4) {
+ // An id defined in a loop, which contain 2 return statements, is used after
+ // the loop. We can only apply the transformation if the id dominates all of
+ // the return blocks.
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpConstantFalse %5
+ %2 = OpFunction %3 None %4
+ %8 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ OpLoopMerge %10 %11 None
+ OpBranch %12
+ %12 = OpLabel
+ %13 = OpCopyObject %5 %7
+ OpSelectionMerge %14 None
+ OpBranchConditional %7 %14 %15
+ %15 = OpLabel
+ OpReturn
+ %14 = OpLabel
+ OpSelectionMerge %16 None
+ OpBranchConditional %7 %16 %17
+ %17 = OpLabel
+ OpReturn
+ %16 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ OpBranchConditional %7 %9 %10
+ %10 = OpLabel
+ OpBranch %18
+ %18 = OpLabel
+ %19 = OpCopyObject %5 %13
+ OpReturn
+ OpFunctionEnd
+ %20 = OpFunction %3 None %4
+ %21 = OpLabel
+ OpBranch %22
+ %22 = OpLabel
+ OpLoopMerge %23 %24 None
+ OpBranch %25
+ %25 = OpLabel
+ OpSelectionMerge %26 None
+ OpBranchConditional %7 %26 %27
+ %27 = OpLabel
+ OpReturn
+ %26 = OpLabel
+ %28 = OpCopyObject %5 %7
+ OpSelectionMerge %29 None
+ OpBranchConditional %7 %29 %30
+ %30 = OpLabel
+ OpReturn
+ %29 = OpLabel
+ OpBranch %24
+ %24 = OpLabel
+ OpBranchConditional %7 %22 %23
+ %23 = OpLabel
+ OpBranch %31
+ %31 = OpLabel
+ %32 = OpCopyObject %5 %28
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ // In function %2, the definition of id %13 will still dominate its use in
+ // instruction %19 after the transformation is applied, because %13 dominates
+ // all of the return blocks.
+ auto transformation = TransformationMergeFunctionReturns(
+ 2, 100, 101, 0, 0, {{MakeReturnMergingInfo(10, 102, 103, {{}})}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // In function %20, the definition of id %28 will not dominate its use in
+ // instruction %32 after the transformation is applied, because %28 dominates
+ // only one of the return blocks.
+ ASSERT_FALSE(
+ TransformationMergeFunctionReturns(
+ 20, 100, 101, 0, 0, {{MakeReturnMergingInfo(23, 102, 103, {{}})}})
+ .IsApplicable(context.get(), transformation_context));
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpConstantFalse %5
+ %2 = OpFunction %3 None %4
+ %8 = OpLabel
+ OpBranch %100
+ %100 = OpLabel
+ OpLoopMerge %101 %100 None
+ OpBranchConditional %6 %9 %100
+ %9 = OpLabel
+ OpLoopMerge %10 %11 None
+ OpBranch %12
+ %12 = OpLabel
+ %13 = OpCopyObject %5 %7
+ OpSelectionMerge %14 None
+ OpBranchConditional %7 %14 %15
+ %15 = OpLabel
+ OpBranch %10
+ %14 = OpLabel
+ OpSelectionMerge %16 None
+ OpBranchConditional %7 %16 %17
+ %17 = OpLabel
+ OpBranch %10
+ %16 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ OpBranchConditional %7 %9 %10
+ %10 = OpLabel
+ %102 = OpPhi %5 %6 %15 %6 %17 %7 %11
+ OpBranchConditional %102 %101 %18
+ %18 = OpLabel
+ %19 = OpCopyObject %5 %13
+ OpBranch %101
+ %101 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %20 = OpFunction %3 None %4
+ %21 = OpLabel
+ OpBranch %22
+ %22 = OpLabel
+ OpLoopMerge %23 %24 None
+ OpBranch %25
+ %25 = OpLabel
+ OpSelectionMerge %26 None
+ OpBranchConditional %7 %26 %27
+ %27 = OpLabel
+ OpReturn
+ %26 = OpLabel
+ %28 = OpCopyObject %5 %7
+ OpSelectionMerge %29 None
+ OpBranchConditional %7 %29 %30
+ %30 = OpLabel
+ OpReturn
+ %29 = OpLabel
+ OpBranch %24
+ %24 = OpLabel
+ OpBranchConditional %7 %22 %23
+ %23 = OpLabel
+ OpBranch %31
+ %31 = OpLabel
+ %32 = OpCopyObject %5 %28
+ OpReturn
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
\ No newline at end of file
