diff --git a/source/fuzz/transformation_duplicate_region_with_selection.cpp b/source/fuzz/transformation_duplicate_region_with_selection.cpp
index 3b264df..2d03968 100644
--- a/source/fuzz/transformation_duplicate_region_with_selection.cpp
+++ b/source/fuzz/transformation_duplicate_region_with_selection.cpp
@@ -47,7 +47,8 @@
 }
 
 bool TransformationDuplicateRegionWithSelection::IsApplicable(
-    opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
+    opt::IRContext* ir_context,
+    const TransformationContext& transformation_context) const {
   // Instruction with the id |condition_id| must exist and must be of a bool
   // type.
   auto bool_instr =
@@ -189,9 +190,6 @@
   }
 
   // Get the maps from the protobuf.
-  // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3786):
-  //     Consider additionally providing overflow ids to make this
-  //     transformation more applicable when shrinking.
   std::map<uint32_t, uint32_t> original_label_to_duplicate_label =
       fuzzerutil::RepeatedUInt32PairToMap(
           message_.original_label_to_duplicate_label());
@@ -204,44 +202,44 @@
       fuzzerutil::RepeatedUInt32PairToMap(message_.original_id_to_phi_id());
 
   for (auto block : region_set) {
-    auto label =
-        ir_context->get_def_use_mgr()->GetDef(block->id())->result_id();
     // The label of every block in the region must be present in the map
-    // |original_label_to_duplicate_label|.
-    if (original_label_to_duplicate_label.count(label) == 0) {
-      return false;
-    }
-    auto duplicate_label = original_label_to_duplicate_label[label];
-    // Each id assigned to labels in the region must be distinct and fresh.
-    if (!duplicate_label ||
-        !CheckIdIsFreshAndNotUsedByThisTransformation(
-            duplicate_label, ir_context, &ids_used_by_this_transformation)) {
-      return false;
+    // |original_label_to_duplicate_label|, unless overflow ids are present.
+    if (original_label_to_duplicate_label.count(block->id()) == 0) {
+      if (!transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
+        return false;
+      }
+    } else {
+      auto duplicate_label = original_label_to_duplicate_label[block->id()];
+      // Each id assigned to labels in the region must be distinct and fresh.
+      if (!duplicate_label ||
+          !CheckIdIsFreshAndNotUsedByThisTransformation(
+              duplicate_label, ir_context, &ids_used_by_this_transformation)) {
+        return false;
+      }
     }
     for (auto instr : *block) {
       if (!instr.HasResultId()) {
         continue;
       }
       // Every instruction with a result id in the region must be present in the
-      // map |original_id_to_duplicate_id|.
+      // map |original_id_to_duplicate_id|, unless overflow ids are present.
       if (original_id_to_duplicate_id.count(instr.result_id()) == 0) {
-        return false;
-      }
-      auto duplicate_id = original_id_to_duplicate_id[instr.result_id()];
-      // Id assigned to this result id in the region must be distinct and fresh.
-      if (!duplicate_id ||
-          !CheckIdIsFreshAndNotUsedByThisTransformation(
-              duplicate_id, ir_context, &ids_used_by_this_transformation)) {
-        return false;
+        if (!transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
+          return false;
+        }
+      } else {
+        auto duplicate_id = original_id_to_duplicate_id[instr.result_id()];
+        // Id assigned to this result id in the region must be distinct and
+        // fresh.
+        if (!duplicate_id ||
+            !CheckIdIsFreshAndNotUsedByThisTransformation(
+                duplicate_id, ir_context, &ids_used_by_this_transformation)) {
+          return false;
+        }
       }
       if (&instr == &*exit_block->tail() ||
           fuzzerutil::IdIsAvailableBeforeInstruction(
               ir_context, &*exit_block->tail(), instr.result_id())) {
-        // Every instruction with a result id available at the end of the region
-        // must be present in the map |original_id_to_phi_id|.
-        if (original_id_to_phi_id.count(instr.result_id()) == 0) {
-          return false;
-        }
         // Using pointers with OpPhi requires capability VariablePointers.
         // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3787):
         //     Consider not adding OpPhi instructions for the pointers which are
@@ -252,13 +250,23 @@
                 SpvCapabilityVariablePointers)) {
           return false;
         }
-        auto phi_id = original_id_to_phi_id[instr.result_id()];
-        // Id assigned to this result id in the region must be distinct and
-        // fresh.
-        if (!phi_id ||
-            !CheckIdIsFreshAndNotUsedByThisTransformation(
-                phi_id, ir_context, &ids_used_by_this_transformation)) {
-          return false;
+
+        // Every instruction with a result id available at the end of the region
+        // must be present in the map |original_id_to_phi_id|, unless overflow
+        // ids are present.
+        if (original_id_to_phi_id.count(instr.result_id()) == 0) {
+          if (!transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
+            return false;
+          }
+        } else {
+          auto phi_id = original_id_to_phi_id[instr.result_id()];
+          // Id assigned to this result id in the region must be distinct and
+          // fresh.
+          if (!phi_id ||
+              !CheckIdIsFreshAndNotUsedByThisTransformation(
+                  phi_id, ir_context, &ids_used_by_this_transformation)) {
+            return false;
+          }
         }
       }
     }
@@ -267,7 +275,8 @@
 }
 
 void TransformationDuplicateRegionWithSelection::Apply(
-    opt::IRContext* ir_context, TransformationContext* /*unused*/) const {
+    opt::IRContext* ir_context,
+    TransformationContext* transformation_context) const {
   fuzzerutil::UpdateModuleIdBound(ir_context, message_.new_entry_fresh_id());
   fuzzerutil::UpdateModuleIdBound(ir_context, message_.merge_label_fresh_id());
 
@@ -304,6 +313,35 @@
   std::map<uint32_t, uint32_t> original_id_to_phi_id =
       fuzzerutil::RepeatedUInt32PairToMap(message_.original_id_to_phi_id());
 
+  // Use oveflow ids to fill in any required ids that are missing from these
+  // maps.
+  for (auto block : region_blocks) {
+    if (original_label_to_duplicate_label.count(block->id()) == 0) {
+      original_label_to_duplicate_label.insert(
+          {block->id(),
+           transformation_context->GetOverflowIdSource()->GetNextOverflowId()});
+    }
+    for (auto instr : *block) {
+      if (!instr.HasResultId()) {
+        continue;
+      }
+      if (original_id_to_duplicate_id.count(instr.result_id()) == 0) {
+        original_id_to_duplicate_id.insert(
+            {instr.result_id(), transformation_context->GetOverflowIdSource()
+                                    ->GetNextOverflowId()});
+      }
+      if (&instr == &*exit_block->tail() ||
+          fuzzerutil::IdIsAvailableBeforeInstruction(
+              ir_context, &*exit_block->tail(), instr.result_id())) {
+        if (original_id_to_phi_id.count(instr.result_id()) == 0) {
+          original_id_to_phi_id.insert(
+              {instr.result_id(), transformation_context->GetOverflowIdSource()
+                                      ->GetNextOverflowId()});
+        }
+      }
+    }
+  }
+
   // Before adding duplicate blocks, we need to update the OpPhi instructions in
   // the successors of the |exit_block|. We know that the execution of the
   // transformed region will end in |merge_block|. Hence, we need to change all
diff --git a/test/fuzz/transformation_duplicate_region_with_selection_test.cpp b/test/fuzz/transformation_duplicate_region_with_selection_test.cpp
index 6398f88..d63cfdf 100644
--- a/test/fuzz/transformation_duplicate_region_with_selection_test.cpp
+++ b/test/fuzz/transformation_duplicate_region_with_selection_test.cpp
@@ -14,6 +14,7 @@
 
 #include "source/fuzz/transformation_duplicate_region_with_selection.h"
 
+#include "source/fuzz/counter_overflow_id_source.h"
 #include "test/fuzz/fuzz_test_util.h"
 
 namespace spvtools {
@@ -504,6 +505,7 @@
   ASSERT_FALSE(
       transformation_bad_7.IsApplicable(context.get(), transformation_context));
 
+#ifndef NDEBUG
   // Bad: Instruction with id 15 is from the original region and is available
   // at the end of the region but it is not present in the
   // |original_id_to_phi_id|.
@@ -511,8 +513,9 @@
       TransformationDuplicateRegionWithSelection(
           500, 19, 501, 800, 800, {{800, 100}}, {{13, 201}, {15, 202}},
           {{13, 301}});
-  ASSERT_FALSE(
-      transformation_bad_8.IsApplicable(context.get(), transformation_context));
+  ASSERT_DEATH(
+      transformation_bad_8.IsApplicable(context.get(), transformation_context),
+      "Bad attempt to query whether overflow ids are available.");
 
   // Bad: Instruction with id 15 is from the original region but it is
   // not present in the |original_id_to_duplicate_id|.
@@ -520,8 +523,10 @@
       TransformationDuplicateRegionWithSelection(500, 19, 501, 800, 800,
                                                  {{800, 100}}, {{13, 201}},
                                                  {{13, 301}, {15, 302}});
-  ASSERT_FALSE(
-      transformation_bad_9.IsApplicable(context.get(), transformation_context));
+  ASSERT_DEATH(
+      transformation_bad_9.IsApplicable(context.get(), transformation_context),
+      "Bad attempt to query whether overflow ids are available.");
+#endif
 
   // Bad: |condition_id| does not refer to the valid instruction.
   TransformationDuplicateRegionWithSelection transformation_bad_10 =
@@ -1740,6 +1745,130 @@
       transformation_bad.IsApplicable(context.get(), transformation_context));
 }
 
+TEST(TransformationDuplicateRegionWithSelectionTest, OverflowIds) {
+  // This test checks that the transformation correctly uses overflow ids, when
+  // they are both needed and provided.
+
+  std::string shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 310
+               OpName %4 "main"
+               OpName %6 "fun("
+               OpName %10 "s"
+               OpName %17 "b"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %8 = OpTypeInt 32 1
+          %9 = OpTypePointer Function %8
+         %11 = OpConstant %8 0
+         %13 = OpConstant %8 2
+         %15 = OpTypeBool
+         %16 = OpTypePointer Function %15
+         %18 = OpConstantTrue %15
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %17 = OpVariable %16 Function
+               OpStore %17 %18
+         %19 = OpFunctionCall %2 %6
+               OpReturn
+               OpFunctionEnd
+          %6 = OpFunction %2 None %3
+          %7 = OpLabel
+         %10 = OpVariable %9 Function
+               OpBranch %50
+         %50 = OpLabel
+               OpStore %10 %11
+         %12 = OpLoad %8 %10
+         %14 = OpIAdd %8 %12 %13
+               OpStore %10 %14
+               OpKill
+               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;
+  auto overflow_ids_unique_ptr = MakeUnique<CounterOverflowIdSource>(1000);
+  auto overflow_ids_ptr = overflow_ids_unique_ptr.get();
+  TransformationContext transformation_context(
+      MakeUnique<FactManager>(context.get()), validator_options,
+      std::move(overflow_ids_unique_ptr));
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // The mappings do not provide sufficient ids, thus overflow ids are required.
+  TransformationDuplicateRegionWithSelection transformation_good_1 =
+      TransformationDuplicateRegionWithSelection(500, 18, 501, 50, 50, {},
+                                                 {{12, 201}}, {{14, 302}});
+  ASSERT_TRUE(transformation_good_1.IsApplicable(context.get(),
+                                                 transformation_context));
+  ApplyAndCheckFreshIds(transformation_good_1, context.get(),
+                        &transformation_context,
+                        overflow_ids_ptr->GetIssuedOverflowIds());
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  std::string expected_shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 310
+               OpName %4 "main"
+               OpName %6 "fun("
+               OpName %10 "s"
+               OpName %17 "b"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %8 = OpTypeInt 32 1
+          %9 = OpTypePointer Function %8
+         %11 = OpConstant %8 0
+         %13 = OpConstant %8 2
+         %15 = OpTypeBool
+         %16 = OpTypePointer Function %15
+         %18 = OpConstantTrue %15
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %17 = OpVariable %16 Function
+               OpStore %17 %18
+         %19 = OpFunctionCall %2 %6
+               OpReturn
+               OpFunctionEnd
+          %6 = OpFunction %2 None %3
+          %7 = OpLabel
+         %10 = OpVariable %9 Function
+               OpBranch %500
+        %500 = OpLabel
+               OpSelectionMerge %501 None
+               OpBranchConditional %18 %50 %1000
+         %50 = OpLabel
+               OpStore %10 %11
+         %12 = OpLoad %8 %10
+         %14 = OpIAdd %8 %12 %13
+               OpStore %10 %14
+               OpBranch %501
+       %1000 = OpLabel
+               OpStore %10 %11
+        %201 = OpLoad %8 %10
+       %1002 = OpIAdd %8 %201 %13
+               OpStore %10 %1002
+               OpBranch %501
+        %501 = OpLabel
+       %1001 = OpPhi %8 %12 %50 %201 %1000
+        %302 = OpPhi %8 %14 %50 %1002 %1000
+               OpKill
+               OpFunctionEnd
+        )";
+
+  ASSERT_TRUE(IsEqual(env, expected_shader, context.get()));
+}
+
 }  // namespace
 }  // namespace fuzz
 }  // namespace spvtools