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