diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index 2a9a95d..6843eb8 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -104,6 +104,7 @@
         fuzzer_pass_propagate_instructions_up.h
         fuzzer_pass_push_ids_through_variables.h
         fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.h
+        fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h
         fuzzer_pass_replace_copy_memories_with_loads_stores.h
         fuzzer_pass_replace_copy_objects_with_stores_loads.h
         fuzzer_pass_replace_irrelevant_ids.h
@@ -197,6 +198,7 @@
         transformation_record_synonymous_constants.h
         transformation_replace_add_sub_mul_with_carrying_extended.h
         transformation_replace_boolean_constant_with_constant_binary.h
+        transformation_replace_branch_from_dead_block_with_exit.h
         transformation_replace_constant_with_uniform.h
         transformation_replace_copy_memory_with_load_store.h
         transformation_replace_copy_object_with_store_load.h
@@ -288,6 +290,7 @@
         fuzzer_pass_propagate_instructions_up.cpp
         fuzzer_pass_push_ids_through_variables.cpp
         fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.cpp
+        fuzzer_pass_replace_branches_from_dead_blocks_with_exits.cpp
         fuzzer_pass_replace_copy_memories_with_loads_stores.cpp
         fuzzer_pass_replace_copy_objects_with_stores_loads.cpp
         fuzzer_pass_replace_irrelevant_ids.cpp
@@ -379,6 +382,7 @@
         transformation_record_synonymous_constants.cpp
         transformation_replace_add_sub_mul_with_carrying_extended.cpp
         transformation_replace_boolean_constant_with_constant_binary.cpp
+        transformation_replace_branch_from_dead_block_with_exit.cpp
         transformation_replace_constant_with_uniform.cpp
         transformation_replace_copy_memory_with_load_store.cpp
         transformation_replace_copy_object_with_store_load.cpp
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 7d9c9c4..218c059 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -72,6 +72,7 @@
 #include "source/fuzz/fuzzer_pass_propagate_instructions_up.h"
 #include "source/fuzz/fuzzer_pass_push_ids_through_variables.h"
 #include "source/fuzz/fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.h"
+#include "source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h"
 #include "source/fuzz/fuzzer_pass_replace_copy_memories_with_loads_stores.h"
 #include "source/fuzz/fuzzer_pass_replace_copy_objects_with_stores_loads.h"
 #include "source/fuzz/fuzzer_pass_replace_irrelevant_ids.h"
@@ -282,6 +283,8 @@
     MaybeAddRepeatedPass<FuzzerPassPushIdsThroughVariables>(&pass_instances);
     MaybeAddRepeatedPass<FuzzerPassReplaceAddsSubsMulsWithCarryingExtended>(
         &pass_instances);
+    MaybeAddRepeatedPass<FuzzerPassReplaceBranchesFromDeadBlocksWithExits>(
+        &pass_instances);
     MaybeAddRepeatedPass<FuzzerPassReplaceCopyMemoriesWithLoadsStores>(
         &pass_instances);
     MaybeAddRepeatedPass<FuzzerPassReplaceCopyObjectsWithStoresLoads>(
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 1250cba..3f0d10e 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -114,6 +114,8 @@
 const std::pair<uint32_t, uint32_t> kChanceOfPushingIdThroughVariable = {5, 50};
 const std::pair<uint32_t, uint32_t>
     kChanceOfReplacingAddSubMulWithCarryingExtended = {20, 70};
+const std::pair<uint32_t, uint32_t>
+    kChanceOfReplacingBranchFromDeadBlockWithExit = {10, 65};
 const std::pair<uint32_t, uint32_t> kChanceOfReplacingCopyMemoryWithLoadStore =
     {20, 90};
 const std::pair<uint32_t, uint32_t> kChanceOfReplacingCopyObjectWithStoreLoad =
@@ -304,6 +306,8 @@
       ChooseBetweenMinAndMax(kChanceOfPushingIdThroughVariable);
   chance_of_replacing_add_sub_mul_with_carrying_extended_ =
       ChooseBetweenMinAndMax(kChanceOfReplacingAddSubMulWithCarryingExtended);
+  chance_of_replacing_branch_from_dead_block_with_exit_ =
+      ChooseBetweenMinAndMax(kChanceOfReplacingBranchFromDeadBlockWithExit);
   chance_of_replacing_copy_memory_with_load_store_ =
       ChooseBetweenMinAndMax(kChanceOfReplacingCopyMemoryWithLoadStore);
   chance_of_replacing_copyobject_with_store_load_ =
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 01a92f7..147c66d 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -276,6 +276,9 @@
   uint32_t GetChanceOfReplacingAddSubMulWithCarryingExtended() {
     return chance_of_replacing_add_sub_mul_with_carrying_extended_;
   }
+  uint32_t GetChanceOfReplacingBranchFromDeadBlockWithExit() {
+    return chance_of_replacing_branch_from_dead_block_with_exit_;
+  }
   uint32_t GetChanceOfReplacingCopyMemoryWithLoadStore() {
     return chance_of_replacing_copy_memory_with_load_store_;
   }
@@ -470,6 +473,7 @@
   uint32_t chance_of_propagating_instructions_up_;
   uint32_t chance_of_pushing_id_through_variable_;
   uint32_t chance_of_replacing_add_sub_mul_with_carrying_extended_;
+  uint32_t chance_of_replacing_branch_from_dead_block_with_exit_;
   uint32_t chance_of_replacing_copy_memory_with_load_store_;
   uint32_t chance_of_replacing_copyobject_with_store_load_;
   uint32_t chance_of_replacing_id_with_synonym_;
diff --git a/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.cpp b/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.cpp
new file mode 100644
index 0000000..200aaad
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.cpp
@@ -0,0 +1,132 @@
+// 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/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h"
+
+#include <algorithm>
+#include <vector>
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassReplaceBranchesFromDeadBlocksWithExits::
+    FuzzerPassReplaceBranchesFromDeadBlocksWithExits(
+        opt::IRContext* ir_context,
+        TransformationContext* transformation_context,
+        FuzzerContext* fuzzer_context,
+        protobufs::TransformationSequence* transformations)
+    : FuzzerPass(ir_context, transformation_context, fuzzer_context,
+                 transformations) {}
+
+FuzzerPassReplaceBranchesFromDeadBlocksWithExits::
+    ~FuzzerPassReplaceBranchesFromDeadBlocksWithExits() = default;
+
+void FuzzerPassReplaceBranchesFromDeadBlocksWithExits::Apply() {
+  // OpKill can only be used as a terminator in a function that is guaranteed
+  // to be executed with the Fragment execution model.  We conservatively only
+  // allow OpKill if every entry point in the module has the Fragment execution
+  // model.
+  auto fragment_execution_model_guaranteed =
+      std::all_of(GetIRContext()->module()->entry_points().begin(),
+                  GetIRContext()->module()->entry_points().end(),
+                  [](const opt::Instruction& entry_point) -> bool {
+                    return entry_point.GetSingleWordInOperand(0) ==
+                           SpvExecutionModelFragment;
+                  });
+
+  // Transformations of this type can disable one another.  To avoid ordering
+  // bias, we therefore build a set of candidate transformations to apply, and
+  // subsequently apply them in a random order, skipping any that cease to be
+  // applicable.
+  std::vector<TransformationReplaceBranchFromDeadBlockWithExit>
+      candidate_transformations;
+
+  // Consider every block in every function.
+  for (auto& function : *GetIRContext()->module()) {
+    for (auto& block : function) {
+      // Probabilistically decide whether to skip this block.
+      if (GetFuzzerContext()->ChoosePercentage(
+              GetFuzzerContext()
+                  ->GetChanceOfReplacingBranchFromDeadBlockWithExit())) {
+        continue;
+      }
+      // Check whether the block is suitable for having its terminator replaced.
+      if (!TransformationReplaceBranchFromDeadBlockWithExit::BlockIsSuitable(
+              GetIRContext(), *GetTransformationContext(), block)) {
+        continue;
+      }
+      // We can always use OpUnreachable to replace a block's terminator.
+      // Whether we can use OpKill depends on the execution model, and which of
+      // OpReturn and OpReturnValue we can use depends on the return type of the
+      // enclosing function.
+      std::vector<SpvOp> opcodes = {SpvOpUnreachable};
+      if (fragment_execution_model_guaranteed) {
+        opcodes.emplace_back(SpvOpKill);
+      }
+      auto function_return_type =
+          GetIRContext()->get_type_mgr()->GetType(function.type_id());
+      if (function_return_type->AsVoid()) {
+        opcodes.emplace_back(SpvOpReturn);
+      } else if (fuzzerutil::CanCreateConstant(*function_return_type)) {
+        // For simplicity we only allow OpReturnValue if the function return
+        // type is a type for which we can create a constant.  This allows us a
+        // zero of the given type as a default return value.
+        opcodes.emplace_back(SpvOpReturnValue);
+      }
+      // Choose one of the available terminator opcodes at random and create a
+      // candidate transformation.
+      auto opcode = opcodes[GetFuzzerContext()->RandomIndex(opcodes)];
+      candidate_transformations.emplace_back(
+          TransformationReplaceBranchFromDeadBlockWithExit(
+              block.id(), opcode,
+              opcode == SpvOpReturnValue
+                  ? FindOrCreateZeroConstant(function.type_id(), true)
+                  : 0));
+    }
+  }
+
+  // Process the candidate transformations in a random order.
+  while (!candidate_transformations.empty()) {
+    // Transformations of this type can disable one another.  For example,
+    // suppose we have dead blocks A, B, C, D arranged as follows:
+    //
+    //         A         |
+    //        / \        |
+    //       B   C       |
+    //        \ /        |
+    //         D         |
+    //
+    // Here we can replace the terminator of either B or C with an early exit,
+    // because D has two predecessors.  But if we replace the terminator of B,
+    // say, we get:
+    //
+    //         A         |
+    //        / \        |
+    //       B   C       |
+    //          /        |
+    //         D         |
+    //
+    // and now it is no longer OK to replace the terminator of C as D only has
+    // one predecessor and we do not want to make D unreachable in the control
+    // flow graph.
+    MaybeApplyTransformation(
+        GetFuzzerContext()->RemoveAtRandomIndex(&candidate_transformations));
+  }
+}
+
+}  // namespace fuzz
+}  // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h b/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h
new file mode 100644
index 0000000..62164b3
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h
@@ -0,0 +1,41 @@
+// 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_FUZZER_PASS_REPLACE_BRANCHES_FROM_DEAD_BLOCKS_WITH_EXITS_H_
+#define SOURCE_FUZZ_FUZZER_PASS_REPLACE_BRANCHES_FROM_DEAD_BLOCKS_WITH_EXITS_H_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// Fuzzer pass that, under the right conditions, replaces branch instructions
+// from dead blocks with non-branching "exit" terminators, such as OpKill and
+// OpReturn.
+class FuzzerPassReplaceBranchesFromDeadBlocksWithExits : public FuzzerPass {
+ public:
+  FuzzerPassReplaceBranchesFromDeadBlocksWithExits(
+      opt::IRContext* ir_context, TransformationContext* transformation_context,
+      FuzzerContext* fuzzer_context,
+      protobufs::TransformationSequence* transformations);
+
+  ~FuzzerPassReplaceBranchesFromDeadBlocksWithExits() override;
+
+  void Apply() override;
+};
+
+}  // namespace fuzz
+}  // namespace spvtools
+
+#endif  // SOURCE_FUZZ_FUZZER_PASS_REPLACE_BRANCHES_FROM_DEAD_BLOCKS_WITH_EXITS_H_
diff --git a/source/fuzz/pass_management/repeated_pass_instances.h b/source/fuzz/pass_management/repeated_pass_instances.h
index 8d2c0f8..6809d07 100644
--- a/source/fuzz/pass_management/repeated_pass_instances.h
+++ b/source/fuzz/pass_management/repeated_pass_instances.h
@@ -58,6 +58,7 @@
 #include "source/fuzz/fuzzer_pass_propagate_instructions_up.h"
 #include "source/fuzz/fuzzer_pass_push_ids_through_variables.h"
 #include "source/fuzz/fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.h"
+#include "source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h"
 #include "source/fuzz/fuzzer_pass_replace_copy_memories_with_loads_stores.h"
 #include "source/fuzz/fuzzer_pass_replace_copy_objects_with_stores_loads.h"
 #include "source/fuzz/fuzzer_pass_replace_irrelevant_ids.h"
@@ -150,6 +151,7 @@
   REPEATED_PASS_INSTANCE(PropagateInstructionsUp);
   REPEATED_PASS_INSTANCE(PushIdsThroughVariables);
   REPEATED_PASS_INSTANCE(ReplaceAddsSubsMulsWithCarryingExtended);
+  REPEATED_PASS_INSTANCE(ReplaceBranchesFromDeadBlocksWithExits);
   REPEATED_PASS_INSTANCE(ReplaceCopyMemoriesWithLoadsStores);
   REPEATED_PASS_INSTANCE(ReplaceCopyObjectsWithStoresLoads);
   REPEATED_PASS_INSTANCE(ReplaceLoadsStoresWithCopyMemories);
diff --git a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
index a6f024b..060c743 100644
--- a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
+++ b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
@@ -63,10 +63,12 @@
     // - Dead blocks are great for adding function calls
     // - Dead blocks are also great for adding loads and stores
     // - The guard associated with a dead block can be obfuscated
-    return RandomOrderAndNonNull({pass_instances_->GetAddFunctionCalls(),
-                                  pass_instances_->GetAddLoads(),
-                                  pass_instances_->GetAddStores(),
-                                  pass_instances_->GetObfuscateConstants()});
+    // - Branches from dead blocks may be replaced with exits
+    return RandomOrderAndNonNull(
+        {pass_instances_->GetAddFunctionCalls(), pass_instances_->GetAddLoads(),
+         pass_instances_->GetAddStores(),
+         pass_instances_->GetObfuscateConstants(),
+         pass_instances_->GetReplaceBranchesFromDeadBlocksWithExits()});
   }
   if (&pass == pass_instances_->GetAddDeadBreaks()) {
     // - The guard of the dead break is a good candidate for obfuscation
@@ -189,9 +191,12 @@
     // - 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_->GetMergeFunctionReturns()});
+    // - Donated dead functions may allow branches to be replaced with exits
+    return RandomOrderAndNonNull(
+        {pass_instances_->GetAddFunctionCalls(),
+         pass_instances_->GetReplaceIrrelevantIds(),
+         pass_instances_->GetMergeFunctionReturns(),
+         pass_instances_->GetReplaceBranchesFromDeadBlocksWithExits()});
   }
   if (&pass == pass_instances_->GetDuplicateRegionsWithSelections()) {
     // - Parts of duplicated regions can be outlined
@@ -274,6 +279,11 @@
     // No obvious follow-on passes
     return {};
   }
+  if (&pass == pass_instances_->GetReplaceBranchesFromDeadBlocksWithExits()) {
+    // - Changing a branch to OpReturnValue introduces an irrelevant id, which
+    //   can be replaced
+    return RandomOrderAndNonNull({pass_instances_->GetReplaceIrrelevantIds()});
+  }
   if (&pass == pass_instances_->GetReplaceCopyMemoriesWithLoadsStores()) {
     // No obvious follow-on passes
     return {};
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index 20ab98e..e99d5f0 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -553,6 +553,7 @@
     TransformationWrapRegionInSelection wrap_region_in_selection = 79;
     TransformationAddEarlyTerminatorWrapper add_early_terminator_wrapper = 80;
     TransformationPropagateInstructionDown propagate_instruction_down = 81;
+    TransformationReplaceBranchFromDeadBlockWithExit replace_branch_from_dead_block_with_exit = 82;
     // Add additional option using the next available number.
   }
 }
@@ -1863,6 +1864,24 @@
 
 }
 
+message TransformationReplaceBranchFromDeadBlockWithExit {
+
+  // Given a dead block that ends with OpBranch, replaces OpBranch with an
+  // "exit" instruction; one of OpReturn/OpReturnValue, OpKill (in a fragment
+  // shader) or OpUnreachable.
+
+  // The dead block whose terminator is to be replaced.
+  uint32 block_id = 1;
+
+  // The opcode of the new terminator.
+  uint32 opcode = 2;
+
+  // Ignored unless opcode is OpReturnValue, in which case this field provides
+  // a suitable result id to be returned.
+  uint32 return_value_id = 3;
+
+}
+
 message TransformationReplaceParameterWithGlobal {
 
   // Removes parameter with result id |parameter_id| from its function
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index cc3d010..28903a2 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -76,6 +76,7 @@
 #include "source/fuzz/transformation_record_synonymous_constants.h"
 #include "source/fuzz/transformation_replace_add_sub_mul_with_carrying_extended.h"
 #include "source/fuzz/transformation_replace_boolean_constant_with_constant_binary.h"
+#include "source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h"
 #include "source/fuzz/transformation_replace_constant_with_uniform.h"
 #include "source/fuzz/transformation_replace_copy_memory_with_load_store.h"
 #include "source/fuzz/transformation_replace_copy_object_with_store_load.h"
@@ -283,6 +284,10 @@
       return MakeUnique<TransformationReplaceBooleanConstantWithConstantBinary>(
           message.replace_boolean_constant_with_constant_binary());
     case protobufs::Transformation::TransformationCase::
+        kReplaceBranchFromDeadBlockWithExit:
+      return MakeUnique<TransformationReplaceBranchFromDeadBlockWithExit>(
+          message.replace_branch_from_dead_block_with_exit());
+    case protobufs::Transformation::TransformationCase::
         kReplaceConstantWithUniform:
       return MakeUnique<TransformationReplaceConstantWithUniform>(
           message.replace_constant_with_uniform());
diff --git a/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.cpp b/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.cpp
new file mode 100644
index 0000000..561e8b6
--- /dev/null
+++ b/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.cpp
@@ -0,0 +1,169 @@
+// 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_replace_branch_from_dead_block_with_exit.h"
+
+#include "source/fuzz/fuzzer_util.h"
+
+namespace spvtools {
+namespace fuzz {
+
+TransformationReplaceBranchFromDeadBlockWithExit::
+    TransformationReplaceBranchFromDeadBlockWithExit(
+        const spvtools::fuzz::protobufs::
+            TransformationReplaceBranchFromDeadBlockWithExit& message)
+    : message_(message) {}
+
+TransformationReplaceBranchFromDeadBlockWithExit::
+    TransformationReplaceBranchFromDeadBlockWithExit(uint32_t block_id,
+                                                     SpvOp opcode,
+                                                     uint32_t return_value_id) {
+  message_.set_block_id(block_id);
+  message_.set_opcode(opcode);
+  message_.set_return_value_id(return_value_id);
+}
+
+bool TransformationReplaceBranchFromDeadBlockWithExit::IsApplicable(
+    opt::IRContext* ir_context,
+    const TransformationContext& transformation_context) const {
+  // The block whose terminator is to be changed must exist.
+  auto block = ir_context->get_instr_block(message_.block_id());
+  if (!block) {
+    return false;
+  }
+  if (!BlockIsSuitable(ir_context, transformation_context, *block)) {
+    return false;
+  }
+  auto function_return_type_id = block->GetParent()->type_id();
+  switch (message_.opcode()) {
+    case SpvOpKill:
+      for (auto& entry_point : ir_context->module()->entry_points()) {
+        if (entry_point.GetSingleWordInOperand(0) !=
+            SpvExecutionModelFragment) {
+          // OpKill is only allowed in a fragment shader.  This is a
+          // conservative check: if the module contains a non-fragment entry
+          // point then adding an OpKill might lead to OpKill being used in a
+          // non-fragment shader.
+          return false;
+        }
+      }
+      break;
+    case SpvOpReturn:
+      if (ir_context->get_def_use_mgr()
+              ->GetDef(function_return_type_id)
+              ->opcode() != SpvOpTypeVoid) {
+        // OpReturn is only allowed in a function with void return type.
+        return false;
+      }
+      break;
+    case SpvOpReturnValue: {
+      // If the terminator is to be changed to OpReturnValue, with
+      // |message_.return_value_id| being the value that will be returned, then
+      // |message_.return_value_id| must have a compatible type and be available
+      // at the block terminator.
+      auto return_value =
+          ir_context->get_def_use_mgr()->GetDef(message_.return_value_id());
+      if (!return_value || return_value->type_id() != function_return_type_id) {
+        return false;
+      }
+      if (!fuzzerutil::IdIsAvailableBeforeInstruction(
+              ir_context, block->terminator(), message_.return_value_id())) {
+        return false;
+      }
+      break;
+    }
+    default:
+      assert(message_.opcode() == SpvOpUnreachable &&
+             "Invalid early exit opcode.");
+      break;
+  }
+  return true;
+}
+
+void TransformationReplaceBranchFromDeadBlockWithExit::Apply(
+    opt::IRContext* ir_context, TransformationContext* /*unused*/) const {
+  // If the successor block has OpPhi instructions then arguments related to
+  // |message_.block_id| need to be removed from these instruction.
+  auto block = ir_context->get_instr_block(message_.block_id());
+  assert(block->terminator()->opcode() == SpvOpBranch &&
+         "Precondition: the block must end with OpBranch.");
+  auto successor = ir_context->get_instr_block(
+      block->terminator()->GetSingleWordInOperand(0));
+  successor->ForEachPhiInst([block](opt::Instruction* phi_inst) {
+    opt::Instruction::OperandList new_phi_in_operands;
+    for (uint32_t i = 0; i < phi_inst->NumInOperands(); i += 2) {
+      if (phi_inst->GetSingleWordInOperand(i + 1) == block->id()) {
+        continue;
+      }
+      new_phi_in_operands.emplace_back(phi_inst->GetInOperand(i));
+      new_phi_in_operands.emplace_back(phi_inst->GetInOperand(i + 1));
+    }
+    assert(new_phi_in_operands.size() == phi_inst->NumInOperands() - 2);
+    phi_inst->SetInOperands(std::move(new_phi_in_operands));
+  });
+
+  // Rewrite the terminator of |message_.block_id|.
+  opt::Instruction::OperandList new_terminator_in_operands;
+  if (message_.opcode() == SpvOpReturnValue) {
+    new_terminator_in_operands.push_back(
+        {SPV_OPERAND_TYPE_TYPE_ID, {message_.return_value_id()}});
+  }
+  auto terminator = block->terminator();
+  terminator->SetOpcode(static_cast<SpvOp>(message_.opcode()));
+  terminator->SetInOperands(std::move(new_terminator_in_operands));
+  ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+}
+
+std::unordered_set<uint32_t>
+TransformationReplaceBranchFromDeadBlockWithExit::GetFreshIds() const {
+  return std::unordered_set<uint32_t>();
+}
+
+protobufs::Transformation
+TransformationReplaceBranchFromDeadBlockWithExit::ToMessage() const {
+  protobufs::Transformation result;
+  *result.mutable_replace_branch_from_dead_block_with_exit() = message_;
+  return result;
+}
+
+bool TransformationReplaceBranchFromDeadBlockWithExit::BlockIsSuitable(
+    opt::IRContext* ir_context,
+    const TransformationContext& transformation_context,
+    const opt::BasicBlock& block) {
+  // The block must be dead.
+  if (!transformation_context.GetFactManager()->BlockIsDead(block.id())) {
+    return false;
+  }
+  // The block's terminator must be OpBranch.
+  if (block.terminator()->opcode() != SpvOpBranch) {
+    return false;
+  }
+  if (ir_context->GetStructuredCFGAnalysis()->IsInContinueConstruct(
+          block.id())) {
+    // Early exits from continue constructs are not allowed as they would break
+    // the SPIR-V structured control flow rules.
+    return false;
+  }
+  // We only allow changing OpBranch to an early terminator if the target of the
+  // OpBranch has at least one other predecessor.
+  auto successor = ir_context->get_instr_block(
+      block.terminator()->GetSingleWordInOperand(0));
+  if (ir_context->cfg()->preds(successor->id()).size() < 2) {
+    return false;
+  }
+  return true;
+}
+
+}  // namespace fuzz
+}  // namespace spvtools
diff --git a/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h b/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h
new file mode 100644
index 0000000..e1418c9
--- /dev/null
+++ b/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h
@@ -0,0 +1,84 @@
+// 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_REPLACE_BRANCH_FROM_DEAD_BLOCK_WITH_EXIT_H_
+#define SOURCE_FUZZ_TRANSFORMATION_REPLACE_BRANCH_FROM_DEAD_BLOCK_WITH_EXIT_H_
+
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/fuzz/transformation.h"
+#include "source/fuzz/transformation_context.h"
+#include "source/opt/basic_block.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+class TransformationReplaceBranchFromDeadBlockWithExit : public Transformation {
+ public:
+  explicit TransformationReplaceBranchFromDeadBlockWithExit(
+      const protobufs::TransformationReplaceBranchFromDeadBlockWithExit&
+          message);
+
+  TransformationReplaceBranchFromDeadBlockWithExit(uint32_t block_id,
+                                                   SpvOp opcode,
+                                                   uint32_t return_value_id);
+
+  // - |message_.block_id| must be the id of a dead block that is not part of
+  //   a continue construct
+  // - |message_.block_id| must end with OpBranch
+  // - The successor of |message_.block_id| must have at least one other
+  //   predecessor
+  // - |message_.opcode()| must be one of OpKill, OpReturn, OpReturnValue and
+  //   OpUnreachable
+  // - |message_.opcode()| can only be OpKill the module's entry points all
+  //   have Fragment execution mode
+  // - |message_.opcode()| can only be OpReturn if the return type of the
+  //   function containing the block is void
+  // - If |message_.opcode()| is OpReturnValue then |message_.return_value_id|
+  //   must be an id that is available at the block terminator and that matches
+  //   the return type of the enclosing function
+  bool IsApplicable(
+      opt::IRContext* ir_context,
+      const TransformationContext& transformation_context) const override;
+
+  // Changes the terminator of |message_.block_id| to have opcode
+  // |message_.opcode|, additionally with input operand
+  // |message_.return_value_id| in the case that |message_.opcode| is
+  // OpReturnValue.
+  //
+  // If |message_.block_id|'s successor starts with OpPhi instructions these are
+  // updated so that they no longer refer to |message_.block_id|.
+  void Apply(opt::IRContext* ir_context,
+             TransformationContext* transformation_context) const override;
+
+  std::unordered_set<uint32_t> GetFreshIds() const override;
+
+  protobufs::Transformation ToMessage() const override;
+
+  // Returns true if and only if |block| meets the criteria for having its
+  // terminator replaced with an early exit (see IsApplicable for details of the
+  // criteria.)
+  static bool BlockIsSuitable(
+      opt::IRContext* ir_context,
+      const TransformationContext& transformation_context,
+      const opt::BasicBlock& block);
+
+ private:
+  protobufs::TransformationReplaceBranchFromDeadBlockWithExit message_;
+};
+
+}  // namespace fuzz
+}  // namespace spvtools
+
+#endif  // SOURCE_FUZZ_TRANSFORMATION_REPLACE_BRANCH_FROM_DEAD_BLOCK_WITH_EXIT_H_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index c42bd2d..d586425 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -92,6 +92,7 @@
           transformation_push_id_through_variable_test.cpp
           transformation_replace_add_sub_mul_with_carrying_extended_test.cpp
           transformation_replace_boolean_constant_with_constant_binary_test.cpp
+          transformation_replace_branch_from_dead_block_with_exit_test.cpp
           transformation_replace_copy_object_with_store_load_test.cpp
           transformation_replace_constant_with_uniform_test.cpp
           transformation_replace_copy_memory_with_load_store_test.cpp
diff --git a/test/fuzz/transformation_replace_branch_from_dead_block_with_exit_test.cpp b/test/fuzz/transformation_replace_branch_from_dead_block_with_exit_test.cpp
new file mode 100644
index 0000000..ee1252d
--- /dev/null
+++ b/test/fuzz/transformation_replace_branch_from_dead_block_with_exit_test.cpp
@@ -0,0 +1,560 @@
+// 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_replace_branch_from_dead_block_with_exit.h"
+
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(TransformationReplaceBranchFromDeadBlockWithExitTest, BasicTest) {
+  std::string shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 320
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeBool
+          %7 = OpConstantFalse %6
+         %12 = OpTypeInt 32 1
+         %13 = OpTypePointer Function %12
+         %15 = OpConstant %12 1
+         %17 = OpConstant %12 2
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %14 = OpVariable %13 Function
+               OpSelectionMerge %9 None
+               OpBranchConditional %7 %8 %21
+          %8 = OpLabel
+               OpSelectionMerge %11 None
+               OpBranchConditional %7 %10 %16
+         %10 = OpLabel
+               OpStore %14 %15
+               OpBranch %20
+         %20 = OpLabel
+               OpBranch %11
+         %16 = OpLabel
+               OpStore %14 %17
+               OpBranch %11
+         %11 = OpLabel
+               OpBranch %9
+         %21 = OpLabel
+               OpBranch %9
+          %9 = OpLabel
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  const auto env = SPV_ENV_UNIVERSAL_1_4;
+  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);
+
+  transformation_context.GetFactManager()->AddFactBlockIsDead(8);
+  transformation_context.GetFactManager()->AddFactBlockIsDead(10);
+  transformation_context.GetFactManager()->AddFactBlockIsDead(11);
+  transformation_context.GetFactManager()->AddFactBlockIsDead(16);
+  transformation_context.GetFactManager()->AddFactBlockIsDead(20);
+
+  // Bad: 4 is not a block
+  ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(4, SpvOpKill, 0)
+                   .IsApplicable(context.get(), transformation_context));
+  // Bad: 200 does not exist
+  ASSERT_FALSE(
+      TransformationReplaceBranchFromDeadBlockWithExit(200, SpvOpKill, 0)
+          .IsApplicable(context.get(), transformation_context));
+  // Bad: 21 is not a dead block
+  ASSERT_FALSE(
+      TransformationReplaceBranchFromDeadBlockWithExit(21, SpvOpKill, 0)
+          .IsApplicable(context.get(), transformation_context));
+  // Bad: terminator of 8 is not OpBranch
+  ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(8, SpvOpKill, 0)
+                   .IsApplicable(context.get(), transformation_context));
+  // Bad: 10's successor only has 10 as a predecessor
+  ASSERT_FALSE(
+      TransformationReplaceBranchFromDeadBlockWithExit(10, SpvOpKill, 0)
+          .IsApplicable(context.get(), transformation_context));
+
+#ifndef NDEBUG
+  ASSERT_DEATH(
+      TransformationReplaceBranchFromDeadBlockWithExit(20, SpvOpSwitch, 0)
+          .IsApplicable(context.get(), transformation_context),
+      "Invalid early exit opcode.");
+#endif
+
+  auto transformation1 =
+      TransformationReplaceBranchFromDeadBlockWithExit(20, SpvOpKill, 0);
+  auto transformation2 =
+      TransformationReplaceBranchFromDeadBlockWithExit(16, SpvOpKill, 0);
+  ASSERT_TRUE(
+      transformation1.IsApplicable(context.get(), transformation_context));
+  ASSERT_TRUE(
+      transformation2.IsApplicable(context.get(), transformation_context));
+
+  ApplyAndCheckFreshIds(transformation1, context.get(),
+                        &transformation_context);
+  // Applying transformation 1 should disable transformation 2
+  ASSERT_FALSE(
+      transformation2.IsApplicable(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 %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 320
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeBool
+          %7 = OpConstantFalse %6
+         %12 = OpTypeInt 32 1
+         %13 = OpTypePointer Function %12
+         %15 = OpConstant %12 1
+         %17 = OpConstant %12 2
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %14 = OpVariable %13 Function
+               OpSelectionMerge %9 None
+               OpBranchConditional %7 %8 %21
+          %8 = OpLabel
+               OpSelectionMerge %11 None
+               OpBranchConditional %7 %10 %16
+         %10 = OpLabel
+               OpStore %14 %15
+               OpBranch %20
+         %20 = OpLabel
+               OpKill
+         %16 = OpLabel
+               OpStore %14 %17
+               OpBranch %11
+         %11 = OpLabel
+               OpBranch %9
+         %21 = OpLabel
+               OpBranch %9
+          %9 = OpLabel
+               OpReturn
+               OpFunctionEnd
+  )";
+  ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationReplaceBranchFromDeadBlockWithExitTest,
+     VertexShaderWithLoopInContinueConstruct) {
+  std::string shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Vertex %4 "main"
+               OpSource ESSL 320
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypeFunction %6
+         %12 = OpTypePointer Function %6
+         %14 = OpConstant %6 0
+         %22 = OpConstant %6 10
+         %23 = OpTypeBool
+         %26 = OpConstant %6 1
+         %40 = OpConstant %6 100
+         %48 = OpConstantFalse %23
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+               OpSelectionMerge %50 None
+               OpBranchConditional %48 %49 %50
+         %49 = OpLabel
+         %51 = OpFunctionCall %6 %10
+               OpBranch %50
+         %50 = OpLabel
+               OpReturn
+               OpFunctionEnd
+         %10 = OpFunction %6 None %7
+         %11 = OpLabel
+         %13 = OpVariable %12 Function
+         %15 = OpVariable %12 Function
+         %33 = OpVariable %12 Function
+               OpStore %33 %14
+               OpBranch %34
+         %34 = OpLabel
+               OpLoopMerge %36 %37 None
+               OpBranch %38
+         %38 = OpLabel
+         %39 = OpLoad %6 %33
+         %41 = OpSLessThan %23 %39 %40
+               OpBranchConditional %41 %35 %36
+         %35 = OpLabel
+               OpSelectionMerge %202 None
+               OpBranchConditional %48 %200 %201
+        %200 = OpLabel
+               OpBranch %202
+        %201 = OpLabel
+        %400 = OpCopyObject %6 %14
+               OpBranch %202
+        %202 = OpLabel
+               OpBranch %37
+         %37 = OpLabel
+               OpStore %13 %14
+               OpStore %15 %14
+               OpBranch %16
+         %16 = OpLabel
+               OpLoopMerge %18 %19 None
+               OpBranch %20
+         %20 = OpLabel
+               OpSelectionMerge %102 None
+               OpBranchConditional %48 %100 %101
+        %100 = OpLabel
+               OpBranch %102
+        %101 = OpLabel
+               OpBranch %102
+        %102 = OpLabel
+         %21 = OpLoad %6 %15
+         %24 = OpSLessThan %23 %21 %22
+               OpBranchConditional %24 %17 %18
+         %17 = OpLabel
+               OpSelectionMerge %302 None
+               OpBranchConditional %48 %300 %301
+        %300 = OpLabel
+               OpBranch %302
+        %301 = OpLabel
+               OpBranch %302
+        %302 = OpLabel
+         %25 = OpLoad %6 %13
+         %27 = OpIAdd %6 %25 %26
+               OpStore %13 %27
+               OpBranch %19
+         %19 = OpLabel
+         %28 = OpLoad %6 %15
+         %29 = OpIAdd %6 %28 %26
+               OpStore %15 %29
+               OpBranch %16
+         %18 = OpLabel
+         %30 = OpLoad %6 %13
+         %42 = OpCopyObject %6 %30
+         %43 = OpLoad %6 %33
+         %44 = OpIAdd %6 %43 %42
+               OpStore %33 %44
+               OpBranch %34
+         %36 = OpLabel
+         %45 = OpLoad %6 %33
+               OpReturnValue %45
+               OpFunctionEnd
+  )";
+
+  const auto env = SPV_ENV_UNIVERSAL_1_4;
+  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);
+
+  for (auto block : {16, 17,  18,  19,  20,  34,  35,  36,  37,  38,
+                     49, 100, 101, 102, 200, 201, 202, 300, 301, 302}) {
+    transformation_context.GetFactManager()->AddFactBlockIsDead(block);
+  }
+
+  // Bad: OpKill not allowed in vertex shader
+  ASSERT_FALSE(
+      TransformationReplaceBranchFromDeadBlockWithExit(201, SpvOpKill, 0)
+          .IsApplicable(context.get(), transformation_context));
+
+  // Bad: OpReturn is not allowed in function that expects a returned value.
+  ASSERT_FALSE(
+      TransformationReplaceBranchFromDeadBlockWithExit(200, SpvOpReturn, 0)
+          .IsApplicable(context.get(), transformation_context));
+
+  // Bad: Return value id does not exist
+  ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(
+                   201, SpvOpReturnValue, 1000)
+                   .IsApplicable(context.get(), transformation_context));
+
+  // Bad: Return value id does not have a type
+  ASSERT_FALSE(
+      TransformationReplaceBranchFromDeadBlockWithExit(200, SpvOpReturnValue, 6)
+          .IsApplicable(context.get(), transformation_context));
+
+  // Bad: Return value id does not have the right type
+  ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(
+                   201, SpvOpReturnValue, 48)
+                   .IsApplicable(context.get(), transformation_context));
+
+  // Bad: Return value id is not available
+  ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(
+                   200, SpvOpReturnValue, 400)
+                   .IsApplicable(context.get(), transformation_context));
+
+  // Bad: Early exit now allowed in continue construct
+  ASSERT_FALSE(
+      TransformationReplaceBranchFromDeadBlockWithExit(101, SpvOpUnreachable, 0)
+          .IsApplicable(context.get(), transformation_context));
+
+  // Bad: Early exit now allowed in continue construct (again)
+  ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(
+                   300, SpvOpReturnValue, 14)
+                   .IsApplicable(context.get(), transformation_context));
+
+  auto transformation1 = TransformationReplaceBranchFromDeadBlockWithExit(
+      200, SpvOpUnreachable, 0);
+  auto transformation2 = TransformationReplaceBranchFromDeadBlockWithExit(
+      201, SpvOpReturnValue, 400);
+
+  ASSERT_TRUE(
+      transformation1.IsApplicable(context.get(), transformation_context));
+  ASSERT_TRUE(
+      transformation2.IsApplicable(context.get(), transformation_context));
+
+  ApplyAndCheckFreshIds(transformation2, context.get(),
+                        &transformation_context);
+  ASSERT_FALSE(
+      transformation1.IsApplicable(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 Vertex %4 "main"
+               OpSource ESSL 320
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypeFunction %6
+         %12 = OpTypePointer Function %6
+         %14 = OpConstant %6 0
+         %22 = OpConstant %6 10
+         %23 = OpTypeBool
+         %26 = OpConstant %6 1
+         %40 = OpConstant %6 100
+         %48 = OpConstantFalse %23
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+               OpSelectionMerge %50 None
+               OpBranchConditional %48 %49 %50
+         %49 = OpLabel
+         %51 = OpFunctionCall %6 %10
+               OpBranch %50
+         %50 = OpLabel
+               OpReturn
+               OpFunctionEnd
+         %10 = OpFunction %6 None %7
+         %11 = OpLabel
+         %13 = OpVariable %12 Function
+         %15 = OpVariable %12 Function
+         %33 = OpVariable %12 Function
+               OpStore %33 %14
+               OpBranch %34
+         %34 = OpLabel
+               OpLoopMerge %36 %37 None
+               OpBranch %38
+         %38 = OpLabel
+         %39 = OpLoad %6 %33
+         %41 = OpSLessThan %23 %39 %40
+               OpBranchConditional %41 %35 %36
+         %35 = OpLabel
+               OpSelectionMerge %202 None
+               OpBranchConditional %48 %200 %201
+        %200 = OpLabel
+               OpBranch %202
+        %201 = OpLabel
+        %400 = OpCopyObject %6 %14
+               OpReturnValue %400
+        %202 = OpLabel
+               OpBranch %37
+         %37 = OpLabel
+               OpStore %13 %14
+               OpStore %15 %14
+               OpBranch %16
+         %16 = OpLabel
+               OpLoopMerge %18 %19 None
+               OpBranch %20
+         %20 = OpLabel
+               OpSelectionMerge %102 None
+               OpBranchConditional %48 %100 %101
+        %100 = OpLabel
+               OpBranch %102
+        %101 = OpLabel
+               OpBranch %102
+        %102 = OpLabel
+         %21 = OpLoad %6 %15
+         %24 = OpSLessThan %23 %21 %22
+               OpBranchConditional %24 %17 %18
+         %17 = OpLabel
+               OpSelectionMerge %302 None
+               OpBranchConditional %48 %300 %301
+        %300 = OpLabel
+               OpBranch %302
+        %301 = OpLabel
+               OpBranch %302
+        %302 = OpLabel
+         %25 = OpLoad %6 %13
+         %27 = OpIAdd %6 %25 %26
+               OpStore %13 %27
+               OpBranch %19
+         %19 = OpLabel
+         %28 = OpLoad %6 %15
+         %29 = OpIAdd %6 %28 %26
+               OpStore %15 %29
+               OpBranch %16
+         %18 = OpLabel
+         %30 = OpLoad %6 %13
+         %42 = OpCopyObject %6 %30
+         %43 = OpLoad %6 %33
+         %44 = OpIAdd %6 %43 %42
+               OpStore %33 %44
+               OpBranch %34
+         %36 = OpLabel
+         %45 = OpLoad %6 %33
+               OpReturnValue %45
+               OpFunctionEnd
+  )";
+  ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationReplaceBranchFromDeadBlockWithExitTest, OpPhi) {
+  std::string shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 320
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeBool
+          %7 = OpConstantFalse %6
+         %12 = OpTypeInt 32 1
+         %13 = OpTypePointer Function %12
+         %15 = OpConstant %12 1
+         %17 = OpConstant %12 2
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %14 = OpVariable %13 Function
+               OpSelectionMerge %9 None
+               OpBranchConditional %7 %8 %21
+          %8 = OpLabel
+               OpSelectionMerge %11 None
+               OpBranchConditional %7 %10 %16
+         %10 = OpLabel
+               OpStore %14 %15
+               OpBranch %20
+         %20 = OpLabel
+         %48 = OpCopyObject %12 %15
+               OpBranch %11
+         %16 = OpLabel
+               OpStore %14 %17
+         %49 = OpCopyObject %12 %17
+               OpBranch %11
+         %11 = OpLabel
+         %50 = OpPhi %12 %48 %20 %49 %16
+               OpBranch %9
+         %21 = OpLabel
+               OpBranch %9
+          %9 = OpLabel
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  const auto env = SPV_ENV_UNIVERSAL_1_4;
+  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);
+
+  transformation_context.GetFactManager()->AddFactBlockIsDead(8);
+  transformation_context.GetFactManager()->AddFactBlockIsDead(10);
+  transformation_context.GetFactManager()->AddFactBlockIsDead(11);
+  transformation_context.GetFactManager()->AddFactBlockIsDead(16);
+  transformation_context.GetFactManager()->AddFactBlockIsDead(20);
+
+  auto transformation1 =
+      TransformationReplaceBranchFromDeadBlockWithExit(20, SpvOpKill, 0);
+  auto transformation2 =
+      TransformationReplaceBranchFromDeadBlockWithExit(16, SpvOpKill, 0);
+  ASSERT_TRUE(
+      transformation1.IsApplicable(context.get(), transformation_context));
+  ASSERT_TRUE(
+      transformation2.IsApplicable(context.get(), transformation_context));
+
+  ApplyAndCheckFreshIds(transformation1, context.get(),
+                        &transformation_context);
+  // Applying transformation 1 should disable transformation 2
+  ASSERT_FALSE(
+      transformation2.IsApplicable(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 %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 320
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeBool
+          %7 = OpConstantFalse %6
+         %12 = OpTypeInt 32 1
+         %13 = OpTypePointer Function %12
+         %15 = OpConstant %12 1
+         %17 = OpConstant %12 2
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %14 = OpVariable %13 Function
+               OpSelectionMerge %9 None
+               OpBranchConditional %7 %8 %21
+          %8 = OpLabel
+               OpSelectionMerge %11 None
+               OpBranchConditional %7 %10 %16
+         %10 = OpLabel
+               OpStore %14 %15
+               OpBranch %20
+         %20 = OpLabel
+         %48 = OpCopyObject %12 %15
+               OpKill
+         %16 = OpLabel
+               OpStore %14 %17
+         %49 = OpCopyObject %12 %17
+               OpBranch %11
+         %11 = OpLabel
+         %50 = OpPhi %12 %49 %16
+               OpBranch %9
+         %21 = OpLabel
+               OpBranch %9
+          %9 = OpLabel
+               OpReturn
+               OpFunctionEnd
+  )";
+  ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+}  // namespace
+}  // namespace fuzz
+}  // namespace spvtools