spirv-fuzz: Fix OpPhi handling in DuplicateRegionWithSelection (#4065)

Avoid generating OpPhi on void types, and allow the transformation to
take place on regions that produce pointer and sampled image result
ids if such ids are not used after the region.

Fixes #3787.

3 files changed, 313 insertions, 58 deletions

diff --git a/source/fuzz/transformation_duplicate_region_with_selection.cpp b/source/fuzz/transformation_duplicate_region_with_selection.cpp
index 07758cd3..2ac6259d 100644
--- a/source/fuzz/transformation_duplicate_region_with_selection.cpp
+++ b/source/fuzz/transformation_duplicate_region_with_selection.cpp
@@ -209,7 +209,7 @@ bool TransformationDuplicateRegionWithSelection::IsApplicable(
         return false;
       }
     } else {
-      auto duplicate_label = original_label_to_duplicate_label[block->id()];
+      auto duplicate_label = original_label_to_duplicate_label.at(block->id());
       // Each id assigned to labels in the region must be distinct and fresh.
       if (!duplicate_label ||
           !CheckIdIsFreshAndNotUsedByThisTransformation(
@@ -217,7 +217,7 @@ bool TransformationDuplicateRegionWithSelection::IsApplicable(
         return false;
       }
     }
-    for (auto instr : *block) {
+    for (auto& instr : *block) {
       if (!instr.HasResultId()) {
         continue;
       }
@@ -228,7 +228,7 @@ bool TransformationDuplicateRegionWithSelection::IsApplicable(
           return false;
         }
       } else {
-        auto duplicate_id = original_id_to_duplicate_id[instr.result_id()];
+        auto duplicate_id = original_id_to_duplicate_id.at(instr.result_id());
         // Id assigned to this result id in the region must be distinct and
         // fresh.
         if (!duplicate_id ||
@@ -237,43 +237,48 @@ bool TransformationDuplicateRegionWithSelection::IsApplicable(
           return false;
         }
       }
-      if (&instr == &*exit_block->tail() ||
-          fuzzerutil::IdIsAvailableBeforeInstruction(
-              ir_context, &*exit_block->tail(), instr.result_id())) {
-        // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3787):
-        //     Consider not adding OpPhi instructions for the pointers and
-        //     sampled images which are unused after the region, so that the
-        //     transformation could be still applicable.
-
-        // Using pointers with OpPhi requires capability VariablePointers.
-        if (ir_context->get_def_use_mgr()->GetDef(instr.type_id())->opcode() ==
-                SpvOpTypePointer &&
-            !ir_context->get_feature_mgr()->HasCapability(
-                SpvCapabilityVariablePointers)) {
-          return false;
-        }
-
-        // OpTypeSampledImage cannot be the result type of an OpPhi instruction.
-        if (ir_context->get_def_use_mgr()->GetDef(instr.type_id())->opcode() ==
-            SpvOpTypeSampledImage) {
-          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()) {
+      // If the instruction is available at the end of the region then we would
+      // like to be able to add an OpPhi instruction at the merge point of the
+      // duplicated region to capture the values computed by both duplicates of
+      // the instruction, so that this is also available after the region.  We
+      // do this not just for instructions that are already used after the
+      // region, but for all instructions so that the phi is available to future
+      // transformations.
+      if (AvailableAfterRegion(instr, exit_block, ir_context)) {
+        if (!ValidOpPhiArgument(instr, ir_context)) {
+          // The instruction cannot be used as an OpPhi argument.  This is a
+          // blocker if there are uses of the instruction after the region.
+          // Otherwise we can simply avoid generating an OpPhi for this
+          // instruction and its duplicate.
+          if (!ir_context->get_def_use_mgr()->WhileEachUser(
+                  &instr,
+                  [ir_context,
+                   &region_set](opt::Instruction* use_instr) -> bool {
+                    opt::BasicBlock* use_block =
+                        ir_context->get_instr_block(use_instr);
+                    return use_block == nullptr ||
+                           region_set.count(use_block) > 0;
+                  })) {
             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;
+          // 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.at(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;
+            }
           }
         }
       }
@@ -329,7 +334,7 @@ void TransformationDuplicateRegionWithSelection::Apply(
           {block->id(),
            transformation_context->GetOverflowIdSource()->GetNextOverflowId()});
     }
-    for (auto instr : *block) {
+    for (auto& instr : *block) {
       if (!instr.HasResultId()) {
         continue;
       }
@@ -338,9 +343,8 @@ void TransformationDuplicateRegionWithSelection::Apply(
             {instr.result_id(), transformation_context->GetOverflowIdSource()
                                     ->GetNextOverflowId()});
       }
-      if (&instr == &*exit_block->tail() ||
-          fuzzerutil::IdIsAvailableBeforeInstruction(
-              ir_context, &*exit_block->tail(), instr.result_id())) {
+      if (AvailableAfterRegion(instr, exit_block, ir_context) &&
+          ValidOpPhiArgument(instr, ir_context)) {
         if (original_id_to_phi_id.count(instr.result_id()) == 0) {
           original_id_to_phi_id.insert(
               {instr.result_id(), transformation_context->GetOverflowIdSource()
@@ -414,12 +418,12 @@ void TransformationDuplicateRegionWithSelection::Apply(
     }
 
     fuzzerutil::UpdateModuleIdBound(
-        ir_context, original_label_to_duplicate_label[block->id()]);
+        ir_context, original_label_to_duplicate_label.at(block->id()));
 
     std::unique_ptr<opt::BasicBlock> duplicated_block =
         MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
             ir_context, SpvOpLabel, 0,
-            original_label_to_duplicate_label[block->id()],
+            original_label_to_duplicate_label.at(block->id()),
             opt::Instruction::OperandList()));
 
     for (auto& instr : *block) {
@@ -444,8 +448,10 @@ void TransformationDuplicateRegionWithSelection::Apply(
       duplicated_block->AddInstruction(
           std::unique_ptr<opt::Instruction>(cloned_instr));
 
-      fuzzerutil::UpdateModuleIdBound(
-          ir_context, original_id_to_duplicate_id[instr.result_id()]);
+      if (instr.HasResultId()) {
+        fuzzerutil::UpdateModuleIdBound(
+            ir_context, original_id_to_duplicate_id.at(instr.result_id()));
+      }
 
       // If an id from the original region was used in this instruction,
       // replace it with the value from |original_id_to_duplicate_id|.
@@ -456,8 +462,7 @@ void TransformationDuplicateRegionWithSelection::Apply(
            original_label_to_duplicate_label](uint32_t* op) {
             if (original_id_to_duplicate_id.count(*op) != 0) {
               *op = original_id_to_duplicate_id.at(*op);
-            }
-            if (original_label_to_duplicate_label.count(*op) != 0) {
+            } else if (original_label_to_duplicate_label.count(*op) != 0) {
               *op = original_label_to_duplicate_label.at(*op);
             }
           });
@@ -484,26 +489,27 @@ void TransformationDuplicateRegionWithSelection::Apply(
 
   for (auto& block : region_blocks) {
     for (auto& instr : *block) {
-      if (instr.result_id() != 0 &&
-          (&instr == &*exit_block->tail() ||
-           fuzzerutil::IdIsAvailableBeforeInstruction(
-               ir_context, &*exit_block->tail(), instr.result_id()))) {
-        // Add the OpPhi instruction for every result id that is
-        // available at the end of the region (the last instruction
-        // of the |exit_block|)
+      if (instr.result_id() == 0) {
+        continue;
+      }
+      if (AvailableAfterRegion(instr, exit_block, ir_context) &&
+          ValidOpPhiArgument(instr, ir_context)) {
+        // Add an OpPhi instruction for every result id that is available at
+        // the end of the region, as long as the result id is valid for use
+        // with OpPhi.
         merge_block->AddInstruction(MakeUnique<opt::Instruction>(
             ir_context, SpvOpPhi, instr.type_id(),
-            original_id_to_phi_id[instr.result_id()],
+            original_id_to_phi_id.at(instr.result_id()),
             opt::Instruction::OperandList({
                 {SPV_OPERAND_TYPE_ID, {instr.result_id()}},
                 {SPV_OPERAND_TYPE_ID, {exit_block->id()}},
                 {SPV_OPERAND_TYPE_ID,
-                 {original_id_to_duplicate_id[instr.result_id()]}},
+                 {original_id_to_duplicate_id.at(instr.result_id())}},
                 {SPV_OPERAND_TYPE_ID, {duplicated_exit_block->id()}},
             })));
 
         fuzzerutil::UpdateModuleIdBound(
-            ir_context, original_id_to_phi_id[instr.result_id()]);
+            ir_context, original_id_to_phi_id.at(instr.result_id()));
 
         // If the instruction has been remapped by an OpPhi, look
         // for all its uses outside of the region and outside of the
@@ -544,7 +550,8 @@ void TransformationDuplicateRegionWithSelection::Apply(
           {{SPV_OPERAND_TYPE_ID, {message_.condition_id()}},
            {SPV_OPERAND_TYPE_ID, {message_.entry_block_id()}},
            {SPV_OPERAND_TYPE_ID,
-            {original_label_to_duplicate_label[message_.entry_block_id()]}}})));
+            {original_label_to_duplicate_label.at(
+                message_.entry_block_id())}}})));
 
   // Move the terminator of |exit_block| to the end of
   // |merge_block|.
@@ -678,5 +685,38 @@ TransformationDuplicateRegionWithSelection::GetFreshIds() const {
   return result;
 }
 
+bool TransformationDuplicateRegionWithSelection::AvailableAfterRegion(
+    const opt::Instruction& instr, opt::BasicBlock* exit_block,
+    opt::IRContext* ir_context) {
+  opt::Instruction* final_instruction_in_region = &*exit_block->tail();
+  return &instr == final_instruction_in_region ||
+         fuzzerutil::IdIsAvailableBeforeInstruction(
+             ir_context, final_instruction_in_region, instr.result_id());
+}
+
+bool TransformationDuplicateRegionWithSelection::ValidOpPhiArgument(
+    const opt::Instruction& instr, opt::IRContext* ir_context) {
+  opt::Instruction* instr_type =
+      ir_context->get_def_use_mgr()->GetDef(instr.type_id());
+
+  // It is invalid to apply OpPhi to void-typed values.
+  if (instr_type->opcode() == SpvOpTypeVoid) {
+    return false;
+  }
+
+  // Using pointers with OpPhi requires capability VariablePointers.
+  if (instr_type->opcode() == SpvOpTypePointer &&
+      !ir_context->get_feature_mgr()->HasCapability(
+          SpvCapabilityVariablePointers)) {
+    return false;
+  }
+
+  // OpTypeSampledImage cannot be the result type of an OpPhi instruction.
+  if (instr_type->opcode() == SpvOpTypeSampledImage) {
+    return false;
+  }
+  return true;
+}
+
 }  // namespace fuzz
 }  // namespace spvtools
diff --git a/source/fuzz/transformation_duplicate_region_with_selection.h b/source/fuzz/transformation_duplicate_region_with_selection.h
index d6f0ad9a..a2b9a433 100644
--- a/source/fuzz/transformation_duplicate_region_with_selection.h
+++ b/source/fuzz/transformation_duplicate_region_with_selection.h
@@ -66,6 +66,17 @@ class TransformationDuplicateRegionWithSelection : public Transformation {
       opt::IRContext* ir_context, opt::BasicBlock* entry_block,
       opt::BasicBlock* exit_block);
 
+  // Returns true if and only if |instr| is available at the end of the region
+  // for which |exit_block| is the final block.
+  static bool AvailableAfterRegion(const opt::Instruction& instr,
+                                   opt::BasicBlock* exit_block,
+                                   opt::IRContext* ir_context);
+
+  // Returns true if and only if |instr| is valid as an argument to an OpPhi
+  // instruction.
+  static bool ValidOpPhiArgument(const opt::Instruction& instr,
+                                 opt::IRContext* ir_context);
+
   std::unordered_set<uint32_t> GetFreshIds() const override;
 
   protobufs::Transformation ToMessage() const override;
diff --git a/test/fuzz/transformation_duplicate_region_with_selection_test.cpp b/test/fuzz/transformation_duplicate_region_with_selection_test.cpp
index f3738e74..31fb9a2f 100644
--- a/test/fuzz/transformation_duplicate_region_with_selection_test.cpp
+++ b/test/fuzz/transformation_duplicate_region_with_selection_test.cpp
@@ -1334,6 +1334,9 @@ TEST(TransformationDuplicateRegionWithSelectionTest,
                OpBranch %50
          %50 = OpLabel
          %51 = OpCopyObject %7 %12
+               OpBranch %52
+         %52 = OpLabel
+         %53 = OpCopyObject %7 %51
                OpReturn
                OpFunctionEnd
     )";
@@ -2275,6 +2278,207 @@ TEST(TransformationDuplicateRegionWithSelectionTest,
                    .IsApplicable(context.get(), transformation_context));
 }
 
+TEST(TransformationDuplicateRegionWithSelectionTest,
+     DoNotProduceOpPhiWithVoidType) {
+  std::string reference_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
+         %10 = OpTypeBool
+         %11 = OpConstantTrue %10
+          %4 = OpFunction %2 None %3
+         %12 = OpLabel
+               OpBranch %5
+          %5 = OpLabel
+          %8 = OpFunctionCall %2 %6
+               OpReturn
+               OpFunctionEnd
+          %6 = OpFunction %2 None %3
+          %7 = OpLabel
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  const auto env = SPV_ENV_UNIVERSAL_1_4;
+  const auto consumer = nullptr;
+  const auto context =
+      BuildModule(env, consumer, reference_shader, kFuzzAssembleOption);
+  spvtools::ValidatorOptions validator_options;
+  ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+                                               kConsoleMessageConsumer));
+  TransformationContext transformation_context(
+      MakeUnique<FactManager>(context.get()), validator_options);
+
+  TransformationDuplicateRegionWithSelection transformation(
+      100, 11, 101, 5, 5, {{5, 102}}, {{8, 103}}, {});
+  ASSERT_TRUE(
+      transformation.IsApplicable(context.get(), transformation_context));
+  ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
+  ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+                                               kConsoleMessageConsumer));
+
+  std::string expected_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
+         %10 = OpTypeBool
+         %11 = OpConstantTrue %10
+          %4 = OpFunction %2 None %3
+         %12 = OpLabel
+               OpBranch %100
+        %100 = OpLabel
+               OpSelectionMerge %101 None
+               OpBranchConditional %11 %5 %102
+          %5 = OpLabel
+          %8 = OpFunctionCall %2 %6
+               OpBranch %101
+        %102 = OpLabel
+        %103 = OpFunctionCall %2 %6
+               OpBranch %101
+        %101 = OpLabel
+               OpReturn
+               OpFunctionEnd
+          %6 = OpFunction %2 None %3
+          %7 = OpLabel
+               OpReturn
+               OpFunctionEnd
+        )";
+
+  ASSERT_TRUE(IsEqual(env, expected_shader, context.get()));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest,
+     DoNotProduceOpPhiWithDisallowedType) {
+  std::string reference_shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 320
+               OpDecorate %13 DescriptorSet 0
+               OpDecorate %13 Binding 0
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeFloat 32
+          %7 = OpTypeVector %6 2
+          %8 = OpTypePointer Function %7
+         %10 = OpTypeImage %6 2D 0 0 0 1 Unknown
+         %11 = OpTypeSampledImage %10
+         %12 = OpTypePointer UniformConstant %11
+         %13 = OpVariable %12 UniformConstant
+         %15 = OpConstant %6 1
+         %16 = OpConstantComposite %7 %15 %15
+         %17 = OpTypeVector %6 4
+         %19 = OpTypeInt 32 0
+         %20 = OpConstant %19 0
+         %22 = OpTypePointer Function %6
+         %90 = OpTypeBool
+         %91 = OpConstantTrue %90
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+          %9 = OpVariable %8 Function
+               OpBranch %81
+         %81 = OpLabel
+         %14 = OpLoad %11 %13
+         %18 = OpImageSampleImplicitLod %17 %14 %16
+         %21 = OpCompositeExtract %6 %18 0
+         %23 = OpAccessChain %22 %9 %20
+               OpStore %23 %21
+               OpBranch %80
+         %80 = OpLabel
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  const auto env = SPV_ENV_UNIVERSAL_1_3;
+  const auto consumer = nullptr;
+  const auto context =
+      BuildModule(env, consumer, reference_shader, kFuzzAssembleOption);
+  spvtools::ValidatorOptions validator_options;
+  ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+                                               kConsoleMessageConsumer));
+  TransformationContext transformation_context(
+      MakeUnique<FactManager>(context.get()), validator_options);
+
+  TransformationDuplicateRegionWithSelection transformation(
+      100, 91, 101, 81, 81, {{81, 102}},
+      {{14, 103}, {18, 104}, {21, 105}, {23, 106}}, {{18, 107}, {21, 108}});
+  ASSERT_TRUE(
+      transformation.IsApplicable(context.get(), transformation_context));
+  ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
+  ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+                                               kConsoleMessageConsumer));
+
+  std::string expected_shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 320
+               OpDecorate %13 DescriptorSet 0
+               OpDecorate %13 Binding 0
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeFloat 32
+          %7 = OpTypeVector %6 2
+          %8 = OpTypePointer Function %7
+         %10 = OpTypeImage %6 2D 0 0 0 1 Unknown
+         %11 = OpTypeSampledImage %10
+         %12 = OpTypePointer UniformConstant %11
+         %13 = OpVariable %12 UniformConstant
+         %15 = OpConstant %6 1
+         %16 = OpConstantComposite %7 %15 %15
+         %17 = OpTypeVector %6 4
+         %19 = OpTypeInt 32 0
+         %20 = OpConstant %19 0
+         %22 = OpTypePointer Function %6
+         %90 = OpTypeBool
+         %91 = OpConstantTrue %90
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+          %9 = OpVariable %8 Function
+               OpBranch %100
+        %100 = OpLabel
+               OpSelectionMerge %101 None
+               OpBranchConditional %91 %81 %102
+         %81 = OpLabel
+         %14 = OpLoad %11 %13
+         %18 = OpImageSampleImplicitLod %17 %14 %16
+         %21 = OpCompositeExtract %6 %18 0
+         %23 = OpAccessChain %22 %9 %20
+               OpStore %23 %21
+               OpBranch %101
+        %102 = OpLabel
+        %103 = OpLoad %11 %13
+        %104 = OpImageSampleImplicitLod %17 %103 %16
+        %105 = OpCompositeExtract %6 %104 0
+        %106 = OpAccessChain %22 %9 %20
+               OpStore %106 %105
+               OpBranch %101
+        %101 = OpLabel
+        %107 = OpPhi %17 %18 %81 %104 %102
+        %108 = OpPhi %6 %21 %81 %105 %102
+               OpBranch %80
+         %80 = OpLabel
+               OpReturn
+               OpFunctionEnd
+        )";
+
+  ASSERT_TRUE(IsEqual(env, expected_shader, context.get()));
+}
+
 }  // namespace
 }  // namespace fuzz
 }  // namespace spvtools