Add fuzzer pass to replace ids with synonyms (#2857)

If the fuzzer's fact manager knows that ids A and B are synonymous, it
can replace a use of A with a use of B, so long as various conditions
hold (e.g. the definition of B must dominate the use of A, and it is
not legal to replace a use of an OpConstant in a struct's access chain
with a synonym that is not an OpConstant).

This change adds a fuzzer pass to sprinke such synonym replacements
through the module.

19 files changed, 1063 insertions, 21 deletions

diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index c0592b34..2262c6d9 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -34,6 +34,7 @@ if(SPIRV_BUILD_FUZZER)
         fuzzer_pass_add_dead_breaks.h
         fuzzer_pass_add_dead_continues.h
         fuzzer_pass_add_useful_constructs.h
+        fuzzer_pass_apply_id_synonyms.h
         fuzzer_pass_copy_objects.h
         fuzzer_pass_obfuscate_constants.h
         fuzzer_pass_permute_blocks.h
@@ -58,6 +59,7 @@ if(SPIRV_BUILD_FUZZER)
         transformation_move_block_down.h
         transformation_replace_boolean_constant_with_constant_binary.h
         transformation_replace_constant_with_uniform.h
+          transformation_replace_id_with_synonym.h
         transformation_split_block.h
         uniform_buffer_element_descriptor.h
         ${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.h
@@ -70,6 +72,7 @@ if(SPIRV_BUILD_FUZZER)
         fuzzer_pass_add_dead_breaks.cpp
         fuzzer_pass_add_dead_continues.cpp
         fuzzer_pass_add_useful_constructs.cpp
+        fuzzer_pass_apply_id_synonyms.cpp
         fuzzer_pass_copy_objects.cpp
         fuzzer_pass_obfuscate_constants.cpp
         fuzzer_pass_permute_blocks.cpp
@@ -93,6 +96,7 @@ if(SPIRV_BUILD_FUZZER)
         transformation_move_block_down.cpp
         transformation_replace_boolean_constant_with_constant_binary.cpp
         transformation_replace_constant_with_uniform.cpp
+        transformation_replace_id_with_synonym.cpp
         transformation_split_block.cpp
         uniform_buffer_element_descriptor.cpp
         ${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.cc
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 9d2a7c74..3b034938 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -22,6 +22,7 @@
 #include "source/fuzz/fuzzer_pass_add_dead_breaks.h"
 #include "source/fuzz/fuzzer_pass_add_dead_continues.h"
 #include "source/fuzz/fuzzer_pass_add_useful_constructs.h"
+#include "source/fuzz/fuzzer_pass_apply_id_synonyms.h"
 #include "source/fuzz/fuzzer_pass_copy_objects.h"
 #include "source/fuzz/fuzzer_pass_obfuscate_constants.h"
 #include "source/fuzz/fuzzer_pass_permute_blocks.h"
@@ -111,6 +112,9 @@ Fuzzer::FuzzerResultStatus Fuzzer::Run(
   FuzzerPassCopyObjects(ir_context.get(), &fact_manager, &fuzzer_context,
                         transformation_sequence_out)
       .Apply();
+  FuzzerPassApplyIdSynonyms(ir_context.get(), &fact_manager, &fuzzer_context,
+                            transformation_sequence_out)
+      .Apply();
   FuzzerPassSplitBlocks(ir_context.get(), &fact_manager, &fuzzer_context,
                         transformation_sequence_out)
       .Apply();
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index e9398d5f..8d097b09 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -29,6 +29,7 @@ const uint32_t kDefaultChanceOfAddingDeadContinue = 20;
 const uint32_t kDefaultChanceOfCopyingObject = 20;
 const uint32_t kDefaultChanceOfMovingBlockDown = 25;
 const uint32_t kDefaultChanceOfObfuscatingConstant = 20;
+const uint32_t kDefaultChanceOfReplacingIdWithSynonym = 20;
 const uint32_t kDefaultChanceOfSplittingBlock = 20;
 
 // Default functions for controlling how deep to go during recursive
@@ -52,6 +53,8 @@ FuzzerContext::FuzzerContext(RandomGenerator* random_generator,
       chance_of_copying_object_(kDefaultChanceOfCopyingObject),
       chance_of_moving_block_down_(kDefaultChanceOfMovingBlockDown),
       chance_of_obfuscating_constant_(kDefaultChanceOfObfuscatingConstant),
+      chance_of_replacing_id_with_synonym_(
+          kDefaultChanceOfReplacingIdWithSynonym),
       chance_of_splitting_block_(kDefaultChanceOfSplittingBlock),
       go_deeper_in_constant_obfuscation_(
           kDefaultGoDeeperInConstantObfuscation) {}
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index ed6a3551..90d87566 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -66,6 +66,9 @@ class FuzzerContext {
   uint32_t GetChanceOfObfuscatingConstant() {
     return chance_of_obfuscating_constant_;
   }
+  uint32_t GetChanceOfReplacingIdWithSynonym() {
+    return chance_of_replacing_id_with_synonym_;
+  }
   uint32_t GetChanceOfSplittingBlock() { return chance_of_splitting_block_; }
 
   // Functions to control how deeply to recurse.
@@ -87,6 +90,7 @@ class FuzzerContext {
   uint32_t chance_of_copying_object_;
   uint32_t chance_of_moving_block_down_;
   uint32_t chance_of_obfuscating_constant_;
+  uint32_t chance_of_replacing_id_with_synonym_;
   uint32_t chance_of_splitting_block_;
 
   // Functions to determine with what probability to go deeper when generating
diff --git a/source/fuzz/fuzzer_pass_add_dead_breaks.cpp b/source/fuzz/fuzzer_pass_add_dead_breaks.cpp
index d8380d3e..fa6b0988 100644
--- a/source/fuzz/fuzzer_pass_add_dead_breaks.cpp
+++ b/source/fuzz/fuzzer_pass_add_dead_breaks.cpp
@@ -47,9 +47,9 @@ void FuzzerPassAddDeadBreaks::Apply() {
     // ones that turn out to be no good.
     for (auto& block : function) {
       for (auto merge_block_id : merge_block_ids) {
-        // TODO(afd): right now we completely ignore OpPhi instructions at
-        //  merge blocks.  This will lead to interesting opportunities being
-        //  missed.
+        // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2856): right
+        //  now we completely ignore OpPhi instructions at merge blocks.  This
+        //  will lead to interesting opportunities being missed.
         auto candidate_transformation = TransformationAddDeadBreak(
             block.id(), merge_block_id, GetFuzzerContext()->ChooseEven(), {});
         if (candidate_transformation.IsApplicable(GetIRContext(),
diff --git a/source/fuzz/fuzzer_pass_add_dead_continues.cpp b/source/fuzz/fuzzer_pass_add_dead_continues.cpp
index ac4c72f7..51bcb91e 100644
--- a/source/fuzz/fuzzer_pass_add_dead_continues.cpp
+++ b/source/fuzz/fuzzer_pass_add_dead_continues.cpp
@@ -36,9 +36,9 @@ void FuzzerPassAddDeadContinues::Apply() {
       // node turns out to be inappropriate (e.g. by not being in a loop) the
       // precondition for the transformation will fail and it will be ignored.
       //
-      // TODO(afd): right now we completely ignore OpPhi instructions at
-      //  merge blocks.  This will lead to interesting opportunities being
-      //  missed.
+      // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2856): right
+      //  now we completely ignore OpPhi instructions at continue targets.
+      //  This will lead to interesting opportunities being missed.
       auto candidate_transformation = TransformationAddDeadContinue(
           block.id(), GetFuzzerContext()->ChooseEven(), {});
       // Probabilistically decide whether to apply the transformation in the
diff --git a/source/fuzz/fuzzer_pass_apply_id_synonyms.cpp b/source/fuzz/fuzzer_pass_apply_id_synonyms.cpp
new file mode 100644
index 00000000..703f6f27
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_apply_id_synonyms.cpp
@@ -0,0 +1,108 @@
+// Copyright (c) 2019 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_apply_id_synonyms.h"
+
+#include "source/fuzz/id_use_descriptor.h"
+#include "source/fuzz/transformation_replace_id_with_synonym.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassApplyIdSynonyms::FuzzerPassApplyIdSynonyms(
+    opt::IRContext* ir_context, FactManager* fact_manager,
+    FuzzerContext* fuzzer_context,
+    protobufs::TransformationSequence* transformations)
+    : FuzzerPass(ir_context, fact_manager, fuzzer_context, transformations) {}
+
+FuzzerPassApplyIdSynonyms::~FuzzerPassApplyIdSynonyms() = default;
+
+void FuzzerPassApplyIdSynonyms::Apply() {
+  std::vector<TransformationReplaceIdWithSynonym> transformations_to_apply;
+
+  for (auto id_with_known_synonyms :
+       GetFactManager()->GetIdsForWhichSynonymsAreKnown()) {
+    GetIRContext()->get_def_use_mgr()->ForEachUse(
+        id_with_known_synonyms,
+        [this, id_with_known_synonyms, &transformations_to_apply](
+            opt::Instruction* use_inst, uint32_t use_index) -> void {
+          auto block_containing_use = GetIRContext()->get_instr_block(use_inst);
+          // The use might not be in a block; e.g. it could be a decoration.
+          if (!block_containing_use) {
+            return;
+          }
+          if (!GetFuzzerContext()->ChoosePercentage(
+                  GetFuzzerContext()->GetChanceOfReplacingIdWithSynonym())) {
+            return;
+          }
+
+          std::vector<const protobufs::DataDescriptor*> synonyms_to_try;
+          for (auto& data_descriptor :
+               GetFactManager()->GetSynonymsForId(id_with_known_synonyms)) {
+            synonyms_to_try.push_back(&data_descriptor);
+          }
+          while (!synonyms_to_try.empty()) {
+            auto synonym_index =
+                GetFuzzerContext()->RandomIndex(synonyms_to_try);
+            auto synonym_to_try = synonyms_to_try[synonym_index];
+            synonyms_to_try.erase(synonyms_to_try.begin() + synonym_index);
+            assert(synonym_to_try->index().empty() &&
+                   "Right now we only support id == id synonyms; supporting "
+                   "e.g. id == index-into-vector will come later");
+
+            if (!TransformationReplaceIdWithSynonym::
+                    ReplacingUseWithSynonymIsOk(GetIRContext(), use_inst,
+                                                use_index, *synonym_to_try)) {
+              continue;
+            }
+
+            // |use_index| is the absolute index of the operand.  We require
+            // the index of the operand restricted to input operands only, so
+            // we subtract the number of non-input operands from |use_index|.
+            uint32_t number_of_non_input_operands =
+                use_inst->NumOperands() - use_inst->NumInOperands();
+            TransformationReplaceIdWithSynonym replace_id_transformation(
+                transformation::MakeIdUseDescriptorFromUse(
+                    GetIRContext(), use_inst,
+                    use_index - number_of_non_input_operands),
+                *synonym_to_try, 0);
+            // The transformation should be applicable by construction.
+            assert(replace_id_transformation.IsApplicable(GetIRContext(),
+                                                          *GetFactManager()));
+            // We cannot actually apply the transformation here, as this would
+            // change the analysis results that are being depended on for usage
+            // iteration.  We instead store them up and apply them at the end
+            // of the method.
+            transformations_to_apply.push_back(replace_id_transformation);
+            break;
+          }
+        });
+  }
+
+  for (auto& replace_id_transformation : transformations_to_apply) {
+    // Even though replacing id uses with synonyms may lead to new instructions
+    // (to compute indices into composites), as these instructions will generate
+    // ids, their presence should not affect the id use descriptors that were
+    // computed during the creation of transformations. Thus transformations
+    // should not disable one another.
+    assert(replace_id_transformation.IsApplicable(GetIRContext(),
+                                                  *GetFactManager()));
+    replace_id_transformation.Apply(GetIRContext(), GetFactManager());
+    *GetTransformations()->add_transformation() =
+        replace_id_transformation.ToMessage();
+  }
+}
+
+}  // namespace fuzz
+}  // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_apply_id_synonyms.h b/source/fuzz/fuzzer_pass_apply_id_synonyms.h
new file mode 100644
index 00000000..1a0748eb
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_apply_id_synonyms.h
@@ -0,0 +1,42 @@
+// Copyright (c) 2019 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_APPLY_ID_SYNONYMS_
+#define SOURCE_FUZZ_FUZZER_PASS_APPLY_ID_SYNONYMS_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// A pass that replaces ids with other ids, or accesses into structures, that
+// are known to hold the same values.
+class FuzzerPassApplyIdSynonyms : public FuzzerPass {
+ public:
+  FuzzerPassApplyIdSynonyms(opt::IRContext* ir_context,
+                            FactManager* fact_manager,
+                            FuzzerContext* fuzzer_context,
+                            protobufs::TransformationSequence* transformations);
+
+  ~FuzzerPassApplyIdSynonyms() override;
+
+  void Apply() override;
+};
+
+}  // namespace fuzz
+}  // namespace spvtools
+
+#endif  // SOURCE_FUZZ_FUZZER_PASS_APPLY_ID_SYNONYMS_
diff --git a/source/fuzz/id_use_descriptor.cpp b/source/fuzz/id_use_descriptor.cpp
index 33d2ca08..8693a7d1 100644
--- a/source/fuzz/id_use_descriptor.cpp
+++ b/source/fuzz/id_use_descriptor.cpp
@@ -78,5 +78,33 @@ protobufs::IdUseDescriptor transformation::MakeIdUseDescriptor(
   return result;
 }
 
+protobufs::IdUseDescriptor transformation::MakeIdUseDescriptorFromUse(
+    opt::IRContext* context, opt::Instruction* inst,
+    uint32_t in_operand_index) {
+  auto in_operand = inst->GetInOperand(in_operand_index);
+  assert(in_operand.type == SPV_OPERAND_TYPE_ID);
+  auto id_of_interest = in_operand.words[0];
+
+  auto block = context->get_instr_block(inst);
+  uint32_t base_instruction_result_id = block->id();
+  uint32_t num_opcodes_to_ignore = 0;
+  for (auto& inst_in_block : *block) {
+    if (inst_in_block.HasResultId()) {
+      base_instruction_result_id = inst_in_block.result_id();
+      num_opcodes_to_ignore = 0;
+    }
+    if (&inst_in_block == inst) {
+      return MakeIdUseDescriptor(id_of_interest, inst->opcode(),
+                                 in_operand_index, base_instruction_result_id,
+                                 num_opcodes_to_ignore);
+    }
+    if (inst_in_block.opcode() == inst->opcode()) {
+      num_opcodes_to_ignore++;
+    }
+  }
+  assert(false && "No matching instruction was found.");
+  return protobufs::IdUseDescriptor();
+}
+
 }  // namespace fuzz
 }  // namespace spvtools
diff --git a/source/fuzz/id_use_descriptor.h b/source/fuzz/id_use_descriptor.h
index 63016c5d..1657cb92 100644
--- a/source/fuzz/id_use_descriptor.h
+++ b/source/fuzz/id_use_descriptor.h
@@ -35,6 +35,12 @@ protobufs::IdUseDescriptor MakeIdUseDescriptor(
     uint32_t in_operand_index, uint32_t base_instruction_result_id,
     uint32_t num_opcodes_to_ignore);
 
+// Given an id use, represented by the instruction |inst| that uses the id, and
+// the input operand index |in_operand_index| associated with the usage, returns
+// an IdUseDescriptor that represents the use.
+protobufs::IdUseDescriptor MakeIdUseDescriptorFromUse(
+    opt::IRContext* context, opt::Instruction* inst, uint32_t in_operand_index);
+
 }  // namespace transformation
 }  // namespace fuzz
 }  // namespace spvtools
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index 4e8dcac3..7ee81afd 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -172,6 +172,7 @@ message Transformation {
     TransformationReplaceConstantWithUniform replace_constant_with_uniform = 11;
     TransformationAddDeadContinue add_dead_continue = 12;
     TransformationCopyObject copy_object = 13;
+    TransformationReplaceIdWithSynonym replace_id_with_synonym = 14;
     // Add additional option using the next available number.
   }
 }
@@ -325,6 +326,28 @@ message TransformationMoveBlockDown {
   uint32 block_id = 1;
 }
 
+message TransformationReplaceBooleanConstantWithConstantBinary {
+
+  // A transformation to capture replacing a use of a boolean constant with
+  // binary operation on two constant values
+
+  // A descriptor for the boolean constant id we would like to replace
+  IdUseDescriptor id_use_descriptor = 1;
+
+  // Id for the constant to be used on the LHS of the comparision
+  uint32 lhs_id = 2;
+
+  // Id for the constant to be used on the RHS of the comparision
+  uint32 rhs_id = 3;
+
+  // Opcode for binary operator
+  uint32 opcode = 4;
+
+  // Id that will store the result of the binary operation instruction
+  uint32 fresh_id_for_binary_operation = 5;
+
+}
+
 message TransformationReplaceConstantWithUniform {
 
   // Replaces a use of a constant id with the the result of a load from an
@@ -344,26 +367,21 @@ message TransformationReplaceConstantWithUniform {
 
 }
 
-message TransformationReplaceBooleanConstantWithConstantBinary {
+message TransformationReplaceIdWithSynonym {
 
-  // A transformation to capture replacing a use of a boolean constant with
-  // binary operation on two constant values
+  // Replaces an id use with something known to be synonymous with that id use,
+  // e.g. because it was obtained via applying OpCopyObject
 
-  // A descriptor for the boolean constant id we would like to replace
+  // Identifies the id use that is to be replaced
   IdUseDescriptor id_use_descriptor = 1;
 
-  // Id for the constant to be used on the LHS of the comparision
-  uint32 lhs_id = 2;
-
-  // Id for the constant to be used on the RHS of the comparision
-  uint32 rhs_id = 3;
-
-  // Opcode for binary operator
-  uint32 opcode = 4;
-
-  // Id that will store the result of the binary operation instruction
-  uint32 fresh_id_for_binary_operation = 5;
+  // Identifies the data with which the id use is expected to be synonymous
+  DataDescriptor data_descriptor = 2;
 
+  // In the case that a temporary is required to express the synonym (e.g. to
+  // obtain an element of a vector, provides a fresh id for the temporary;
+  // should be set to 0 if no temporary is required
+  uint32 fresh_id_for_temporary = 3;
 }
 
 message TransformationSplitBlock {
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index bf2cdcd0..65966f35 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -29,6 +29,7 @@
 #include "transformation_move_block_down.h"
 #include "transformation_replace_boolean_constant_with_constant_binary.h"
 #include "transformation_replace_constant_with_uniform.h"
+#include "transformation_replace_id_with_synonym.h"
 #include "transformation_split_block.h"
 
 namespace spvtools {
@@ -72,6 +73,9 @@ std::unique_ptr<Transformation> Transformation::FromMessage(
         kReplaceConstantWithUniform:
       return MakeUnique<TransformationReplaceConstantWithUniform>(
           message.replace_constant_with_uniform());
+    case protobufs::Transformation::TransformationCase::kReplaceIdWithSynonym:
+      return MakeUnique<TransformationReplaceIdWithSynonym>(
+          message.replace_id_with_synonym());
     case protobufs::Transformation::TransformationCase::kSplitBlock:
       return MakeUnique<TransformationSplitBlock>(message.split_block());
     case protobufs::Transformation::TRANSFORMATION_NOT_SET:
diff --git a/source/fuzz/transformation_replace_id_with_synonym.cpp b/source/fuzz/transformation_replace_id_with_synonym.cpp
new file mode 100644
index 00000000..a8874808
--- /dev/null
+++ b/source/fuzz/transformation_replace_id_with_synonym.cpp
@@ -0,0 +1,155 @@
+// Copyright (c) 2019 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_id_with_synonym.h"
+
+#include <algorithm>
+
+#include "source/fuzz/data_descriptor.h"
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/id_use_descriptor.h"
+
+namespace spvtools {
+namespace fuzz {
+
+TransformationReplaceIdWithSynonym::TransformationReplaceIdWithSynonym(
+    const spvtools::fuzz::protobufs::TransformationReplaceIdWithSynonym&
+        message)
+    : message_(message) {}
+
+TransformationReplaceIdWithSynonym::TransformationReplaceIdWithSynonym(
+    protobufs::IdUseDescriptor id_use_descriptor,
+    protobufs::DataDescriptor data_descriptor,
+    uint32_t fresh_id_for_temporary) {
+  assert(fresh_id_for_temporary == 0 && data_descriptor.index().size() == 0 &&
+         "At present we do not support making an id that is synonymous with an "
+         "index into a composite.");
+  *message_.mutable_id_use_descriptor() = std::move(id_use_descriptor);
+  *message_.mutable_data_descriptor() = std::move(data_descriptor);
+  message_.set_fresh_id_for_temporary(fresh_id_for_temporary);
+}
+
+bool TransformationReplaceIdWithSynonym::IsApplicable(
+    spvtools::opt::IRContext* context,
+    const spvtools::fuzz::FactManager& fact_manager) const {
+  auto id_of_interest = message_.id_use_descriptor().id_of_interest();
+
+  // Does the fact manager know about the synonym?
+  if (fact_manager.GetIdsForWhichSynonymsAreKnown().count(id_of_interest) ==
+      0) {
+    return false;
+  }
+
+  auto available_synonyms = fact_manager.GetSynonymsForId(id_of_interest);
+  if (std::find_if(available_synonyms.begin(), available_synonyms.end(),
+                   [this](protobufs::DataDescriptor dd) -> bool {
+                     return DataDescriptorEquals()(&dd,
+                                                   &message_.data_descriptor());
+                   }) == available_synonyms.end()) {
+    return false;
+  }
+
+  auto use_instruction =
+      transformation::FindInstruction(message_.id_use_descriptor(), context);
+  if (!use_instruction) {
+    return false;
+  }
+
+  if (!ReplacingUseWithSynonymIsOk(
+          context, use_instruction,
+          message_.id_use_descriptor().in_operand_index(),
+          message_.data_descriptor())) {
+    return false;
+  }
+
+  assert(message_.fresh_id_for_temporary() == 0);
+  assert(message_.data_descriptor().index().empty());
+
+  return true;
+}
+
+void TransformationReplaceIdWithSynonym::Apply(
+    spvtools::opt::IRContext* context,
+    spvtools::fuzz::FactManager* /*unused*/) const {
+  assert(message_.data_descriptor().index().empty());
+  auto instruction_to_change =
+      transformation::FindInstruction(message_.id_use_descriptor(), context);
+  instruction_to_change->SetInOperand(
+      message_.id_use_descriptor().in_operand_index(),
+      {message_.data_descriptor().object()});
+  context->InvalidateAnalysesExceptFor(opt::IRContext::Analysis::kAnalysisNone);
+}
+
+protobufs::Transformation TransformationReplaceIdWithSynonym::ToMessage()
+    const {
+  protobufs::Transformation result;
+  *result.mutable_replace_id_with_synonym() = message_;
+  return result;
+}
+
+bool TransformationReplaceIdWithSynonym::ReplacingUseWithSynonymIsOk(
+    opt::IRContext* context, opt::Instruction* use_instruction,
+    uint32_t use_in_operand_index, const protobufs::DataDescriptor& synonym) {
+  auto defining_instruction =
+      context->get_def_use_mgr()->GetDef(synonym.object());
+
+  if (use_instruction == defining_instruction) {
+    // If we have an instruction:
+    //   %a = OpCopyObject %t %b
+    // then we know %a and %b are synonymous, but we do *not* want to turn
+    // this into:
+    //   %a = OpCopyObject %t %a
+    // We require this special case because an instruction dominates itself.
+    return false;
+  }
+
+  if (use_instruction->opcode() == SpvOpAccessChain &&
+      use_in_operand_index > 0) {
+    // This is an access chain index.  If the object being accessed has
+    // pointer-to-struct type then we cannot replace the use with a synonym, as
+    // the use needs to be an OpConstant.
+    auto object_being_accessed = context->get_def_use_mgr()->GetDef(
+        use_instruction->GetSingleWordInOperand(0));
+    auto pointer_type =
+        context->get_type_mgr()->GetType(object_being_accessed->type_id());
+    assert(pointer_type->AsPointer());
+    if (pointer_type->AsPointer()->pointee_type()->AsStruct()) {
+      return false;
+    }
+  }
+
+  // We now need to check that replacing the use with the synonym will respect
+  // dominance rules - i.e. the synonym needs to dominate the use.
+  auto dominator_analysis = context->GetDominatorAnalysis(
+      context->get_instr_block(use_instruction)->GetParent());
+  if (use_instruction->opcode() == SpvOpPhi) {
+    // In the case where the use is an operand to OpPhi, it is actually the
+    // *parent* block associated with the operand that must be dominated by the
+    // synonym.
+    auto parent_block =
+        use_instruction->GetSingleWordInOperand(use_in_operand_index + 1);
+    if (!dominator_analysis->Dominates(
+            context->get_instr_block(defining_instruction)->id(),
+            parent_block)) {
+      return false;
+    }
+  } else if (!dominator_analysis->Dominates(defining_instruction,
+                                            use_instruction)) {
+    return false;
+  }
+  return true;
+}
+
+}  // namespace fuzz
+}  // namespace spvtools
diff --git a/source/fuzz/transformation_replace_id_with_synonym.h b/source/fuzz/transformation_replace_id_with_synonym.h
new file mode 100644
index 00000000..d0f233e3
--- /dev/null
+++ b/source/fuzz/transformation_replace_id_with_synonym.h
@@ -0,0 +1,72 @@
+// Copyright (c) 2019 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_ID_WITH_SYNONYM_H_
+#define SOURCE_FUZZ_TRANSFORMATION_REPLACE_ID_WITH_SYNONYM_H_
+
+#include "source/fuzz/fact_manager.h"
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/fuzz/transformation.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+class TransformationReplaceIdWithSynonym : public Transformation {
+ public:
+  explicit TransformationReplaceIdWithSynonym(
+      const protobufs::TransformationReplaceIdWithSynonym& message);
+
+  TransformationReplaceIdWithSynonym(
+      protobufs::IdUseDescriptor id_use_descriptor,
+      protobufs::DataDescriptor data_descriptor,
+      uint32_t fresh_id_for_temporary);
+
+  // - The fact manager must know that the id identified by
+  //   |message_.id_use_descriptor| is synonomous with
+  //   |message_.data_descriptor|.
+  // - Replacing the id in |message_.id_use_descriptor| by the synonym in
+  //   |message_.data_descriptor| must respect SPIR-V's rules about uses being
+  //   dominated by their definitions.
+  // - The id must not be an index into an access chain whose base object has
+  //   struct type, as such indices must be constants.
+  // - |fresh_id_for_temporary| must be 0.
+  // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2855): the
+  //  motivation for the temporary is to support the case where an id is
+  //  synonymous with an element of a composite.  Until support for that is
+  //  implemented, 0 records that no temporary is needed.
+  bool IsApplicable(opt::IRContext* context,
+                    const FactManager& fact_manager) const override;
+
+  // Replaces the use identified by |message_.id_use_descriptor| with the
+  // synonymous id identified by |message_.data_descriptor|.
+  // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2855): in due
+  //  course it will also be necessary to add an additional instruction to pull
+  //  the synonym out of a composite.
+  void Apply(opt::IRContext* context, FactManager* fact_manager) const override;
+
+  protobufs::Transformation ToMessage() const override;
+
+  static bool ReplacingUseWithSynonymIsOk(
+      opt::IRContext* context, opt::Instruction* use_instruction,
+      uint32_t use_in_operand_index, const protobufs::DataDescriptor& synonym);
+
+ private:
+  protobufs::TransformationReplaceIdWithSynonym message_;
+};
+
+}  // namespace fuzz
+}  // namespace spvtools
+
+#endif  // SOURCE_FUZZ_TRANSFORMATION_REPLACE_ID_WITH_SYNONYM_H_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index 6a101ddc..8929cd05 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -34,6 +34,7 @@ if (${SPIRV_BUILD_FUZZER})
           transformation_move_block_down_test.cpp
           transformation_replace_boolean_constant_with_constant_binary_test.cpp
           transformation_replace_constant_with_uniform_test.cpp
+          transformation_replace_id_with_synonym_test.cpp
           transformation_split_block_test.cpp
           uniform_buffer_element_descriptor_test.cpp)
 
diff --git a/test/fuzz/fuzz_test_util.cpp b/test/fuzz/fuzz_test_util.cpp
index e2b95189..bc6d4ee6 100644
--- a/test/fuzz/fuzz_test_util.cpp
+++ b/test/fuzz/fuzz_test_util.cpp
@@ -16,6 +16,8 @@
 
 #include <iostream>
 
+#include "tools/io.h"
+
 namespace spvtools {
 namespace fuzz {
 
@@ -89,5 +91,19 @@ std::string ToString(spv_target_env env, const std::vector<uint32_t>& binary) {
   return result;
 }
 
+void DumpShader(opt::IRContext* context, const char* filename) {
+  std::vector<uint32_t> binary;
+  context->module()->ToBinary(&binary, false);
+  DumpShader(binary, filename);
+}
+
+void DumpShader(const std::vector<uint32_t>& binary, const char* filename) {
+  auto write_file_succeeded =
+      WriteFile(filename, "wb", &binary[0], binary.size());
+  if (!write_file_succeeded) {
+    std::cerr << "Failed to dump shader" << std::endl;
+  }
+}
+
 }  // namespace fuzz
 }  // namespace spvtools
diff --git a/test/fuzz/fuzz_test_util.h b/test/fuzz/fuzz_test_util.h
index 88a0b205..93f37e56 100644
--- a/test/fuzz/fuzz_test_util.h
+++ b/test/fuzz/fuzz_test_util.h
@@ -93,6 +93,13 @@ const spvtools::MessageConsumer kConsoleMessageConsumer =
   }
 };
 
+// Dumps the SPIRV-V module in |context| to file |filename|. Useful for
+// interactive debugging.
+void DumpShader(opt::IRContext* context, const char* filename);
+
+// Dumps |binary| to file |filename|. Useful for interactive debugging.
+void DumpShader(const std::vector<uint32_t>& binary, const char* filename);
+
 }  // namespace fuzz
 }  // namespace spvtools
 
diff --git a/test/fuzz/fuzzer_shrinker_test.cpp b/test/fuzz/fuzzer_shrinker_test.cpp
index 85f41bc0..3796bbfb 100644
--- a/test/fuzz/fuzzer_shrinker_test.cpp
+++ b/test/fuzz/fuzzer_shrinker_test.cpp
@@ -158,6 +158,7 @@ void RunFuzzerAndShrinker(const std::string& shader,
 
   std::vector<uint32_t> binary_in;
   SpirvTools t(env);
+  t.SetMessageConsumer(kConsoleMessageConsumer);
   ASSERT_TRUE(t.Assemble(shader, &binary_in, kFuzzAssembleOption));
   ASSERT_TRUE(t.Validate(binary_in));
 
diff --git a/test/fuzz/transformation_replace_id_with_synonym_test.cpp b/test/fuzz/transformation_replace_id_with_synonym_test.cpp
new file mode 100644
index 00000000..d3a23449
--- /dev/null
+++ b/test/fuzz/transformation_replace_id_with_synonym_test.cpp
@@ -0,0 +1,569 @@
+// Copyright (c) 2019 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_id_with_synonym.h"
+#include "source/fuzz/data_descriptor.h"
+#include "source/fuzz/id_use_descriptor.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+// The following shader was obtained from this GLSL, which was then optimized
+// with spirv-opt -O and manually edited to include some uses of OpCopyObject
+// (to introduce id synonyms).
+//
+// #version 310 es
+//
+// precision highp int;
+// precision highp float;
+//
+// layout(set = 0, binding = 0) uniform buf {
+//   int a;
+//   int b;
+//   int c;
+// };
+//
+// layout(location = 0) out vec4 color;
+//
+// void main() {
+//   int x = a;
+//   float f = 0.0;
+//   while (x < b) {
+//     switch(x % 4) {
+//       case 0:
+//         color[0] = f;
+//         break;
+//       case 1:
+//         color[1] = f;
+//         break;
+//       case 2:
+//         color[2] = f;
+//         break;
+//       case 3:
+//         color[3] = f;
+//         break;
+//       default:
+//         break;
+//     }
+//     if (x > c) {
+//       x++;
+//     } else {
+//       x += 2;
+//     }
+//   }
+//   color[0] += color[1] + float(x);
+// }
+const std::string kComplexShader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main" %42
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 310
+               OpName %4 "main"
+               OpName %9 "buf"
+               OpMemberName %9 0 "a"
+               OpMemberName %9 1 "b"
+               OpMemberName %9 2 "c"
+               OpName %11 ""
+               OpName %42 "color"
+               OpMemberDecorate %9 0 Offset 0
+               OpMemberDecorate %9 1 Offset 4
+               OpMemberDecorate %9 2 Offset 8
+               OpDecorate %9 Block
+               OpDecorate %11 DescriptorSet 0
+               OpDecorate %11 Binding 0
+               OpDecorate %42 Location 0
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %9 = OpTypeStruct %6 %6 %6
+         %10 = OpTypePointer Uniform %9
+         %11 = OpVariable %10 Uniform
+         %12 = OpConstant %6 0
+         %13 = OpTypePointer Uniform %6
+         %16 = OpTypeFloat 32
+         %19 = OpConstant %16 0
+         %26 = OpConstant %6 1
+         %29 = OpTypeBool
+         %32 = OpConstant %6 4
+         %40 = OpTypeVector %16 4
+         %41 = OpTypePointer Output %40
+         %42 = OpVariable %41 Output
+         %44 = OpTypeInt 32 0
+         %45 = OpConstant %44 0
+         %46 = OpTypePointer Output %16
+         %50 = OpConstant %44 1
+         %54 = OpConstant %44 2
+         %58 = OpConstant %44 3
+         %64 = OpConstant %6 2
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+        %209 = OpCopyObject %6 %12
+         %14 = OpAccessChain %13 %11 %12
+         %15 = OpLoad %6 %14
+        %200 = OpCopyObject %6 %15
+               OpBranch %20
+         %20 = OpLabel
+         %84 = OpPhi %6 %15 %5 %86 %69
+         %27 = OpAccessChain %13 %11 %26
+         %28 = OpLoad %6 %27
+        %207 = OpCopyObject %6 %84
+        %201 = OpCopyObject %6 %15
+         %30 = OpSLessThan %29 %84 %28
+               OpLoopMerge %22 %69 None
+               OpBranchConditional %30 %21 %22
+         %21 = OpLabel
+         %33 = OpSMod %6 %84 %32
+        %208 = OpCopyObject %6 %33
+               OpSelectionMerge %39 None
+               OpSwitch %33 %38 0 %34 1 %35 2 %36 3 %37
+         %38 = OpLabel
+        %202 = OpCopyObject %6 %15
+               OpBranch %39
+         %34 = OpLabel
+        %210 = OpCopyObject %16 %19
+         %47 = OpAccessChain %46 %42 %45
+               OpStore %47 %19
+               OpBranch %39
+         %35 = OpLabel
+         %51 = OpAccessChain %46 %42 %50
+               OpStore %51 %19
+               OpBranch %39
+         %36 = OpLabel
+        %204 = OpCopyObject %44 %54
+         %55 = OpAccessChain %46 %42 %54
+        %203 = OpCopyObject %46 %55
+               OpStore %55 %19
+               OpBranch %39
+         %37 = OpLabel
+         %59 = OpAccessChain %46 %42 %58
+               OpStore %59 %19
+               OpBranch %39
+         %39 = OpLabel
+        %300 = OpIAdd %6 %15 %15
+         %65 = OpAccessChain %13 %11 %64
+         %66 = OpLoad %6 %65
+         %67 = OpSGreaterThan %29 %84 %66
+               OpSelectionMerge %69 None
+               OpBranchConditional %67 %68 %72
+         %68 = OpLabel
+         %71 = OpIAdd %6 %84 %26
+               OpBranch %69
+         %72 = OpLabel
+         %74 = OpIAdd %6 %84 %64
+        %205 = OpCopyObject %6 %74
+               OpBranch %69
+         %69 = OpLabel
+         %86 = OpPhi %6 %71 %68 %74 %72
+        %301 = OpPhi %6 %71 %68 %15 %72
+               OpBranch %20
+         %22 = OpLabel
+         %75 = OpAccessChain %46 %42 %50
+         %76 = OpLoad %16 %75
+         %78 = OpConvertSToF %16 %84
+         %80 = OpAccessChain %46 %42 %45
+        %206 = OpCopyObject %16 %78
+         %81 = OpLoad %16 %80
+         %79 = OpFAdd %16 %76 %78
+         %82 = OpFAdd %16 %81 %79
+               OpStore %80 %82
+               OpReturn
+               OpFunctionEnd
+)";
+
+protobufs::Fact MakeFact(uint32_t id, uint32_t copy_id) {
+  protobufs::FactIdSynonym id_synonym_fact;
+  id_synonym_fact.set_id(id);
+  id_synonym_fact.mutable_data_descriptor()->set_object(copy_id);
+  protobufs::Fact result;
+  *result.mutable_id_synonym_fact() = id_synonym_fact;
+  return result;
+}
+
+// Equips the fact manager with synonym facts for the above shader.
+void SetUpIdSynonyms(FactManager* fact_manager, opt::IRContext* context) {
+  fact_manager->AddFact(MakeFact(15, 200), context);
+  fact_manager->AddFact(MakeFact(15, 201), context);
+  fact_manager->AddFact(MakeFact(15, 202), context);
+  fact_manager->AddFact(MakeFact(55, 203), context);
+  fact_manager->AddFact(MakeFact(54, 204), context);
+  fact_manager->AddFact(MakeFact(74, 205), context);
+  fact_manager->AddFact(MakeFact(78, 206), context);
+  fact_manager->AddFact(MakeFact(84, 207), context);
+  fact_manager->AddFact(MakeFact(33, 208), context);
+  fact_manager->AddFact(MakeFact(12, 209), context);
+  fact_manager->AddFact(MakeFact(19, 210), context);
+}
+
+TEST(TransformationReplaceIdWithSynonymTest, IllegalTransformations) {
+  const auto env = SPV_ENV_UNIVERSAL_1_3;
+  const auto consumer = nullptr;
+  const auto context =
+      BuildModule(env, consumer, kComplexShader, kFuzzAssembleOption);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  FactManager fact_manager;
+  SetUpIdSynonyms(&fact_manager, context.get());
+
+  // %202 cannot replace %15 as in-operand 0 of %300, since %202 does not
+  // dominate %300.
+  auto synonym_does_not_dominate_use = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(15, SpvOpIAdd, 0, 300, 0),
+      MakeDataDescriptor(202, {}), 0);
+  ASSERT_FALSE(
+      synonym_does_not_dominate_use.IsApplicable(context.get(), fact_manager));
+
+  // %202 cannot replace %15 as in-operand 2 of %301, since this is the OpPhi's
+  // incoming value for block %72, and %202 does not dominate %72.
+  auto synonym_does_not_dominate_use_op_phi =
+      TransformationReplaceIdWithSynonym(
+          transformation::MakeIdUseDescriptor(15, SpvOpPhi, 2, 301, 0),
+          MakeDataDescriptor(202, {}), 0);
+  ASSERT_FALSE(synonym_does_not_dominate_use_op_phi.IsApplicable(context.get(),
+                                                                 fact_manager));
+
+  // %200 is not a synonym for %84
+  auto id_in_use_is_not_synonymous = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(84, SpvOpSGreaterThan, 0, 67, 0),
+      MakeDataDescriptor(200, {}), 0);
+  ASSERT_FALSE(
+      id_in_use_is_not_synonymous.IsApplicable(context.get(), fact_manager));
+
+  // %86 is not a synonym for anything (and in particular not for %74)
+  auto id_has_no_synonyms = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(86, SpvOpPhi, 2, 84, 0),
+      MakeDataDescriptor(74, {}), 0);
+  ASSERT_FALSE(id_has_no_synonyms.IsApplicable(context.get(), fact_manager));
+
+  // This would lead to %207 = 'OpCopyObject %type %207' if it were allowed
+  auto synonym_use_is_in_synonym_definition =
+      TransformationReplaceIdWithSynonym(
+          transformation::MakeIdUseDescriptor(84, SpvOpCopyObject, 0, 207, 0),
+          MakeDataDescriptor(207, {}), 0);
+  ASSERT_FALSE(synonym_use_is_in_synonym_definition.IsApplicable(context.get(),
+                                                                 fact_manager));
+
+  // The id use descriptor does not lead to a use (%84 is not used in the
+  // definition of %207)
+  auto bad_id_use_descriptor = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(84, SpvOpCopyObject, 0, 200, 0),
+      MakeDataDescriptor(207, {}), 0);
+  ASSERT_FALSE(bad_id_use_descriptor.IsApplicable(context.get(), fact_manager));
+
+  // This replacement would lead to an access chain into a struct using a
+  // non-constant index.
+  auto bad_access_chain = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(12, SpvOpAccessChain, 1, 14, 0),
+      MakeDataDescriptor(209, {}), 0);
+  ASSERT_FALSE(bad_access_chain.IsApplicable(context.get(), fact_manager));
+}
+
+TEST(TransformationReplaceIdWithSynonymTest, LegalTransformations) {
+  const auto env = SPV_ENV_UNIVERSAL_1_3;
+  const auto consumer = nullptr;
+  const auto context =
+      BuildModule(env, consumer, kComplexShader, kFuzzAssembleOption);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  FactManager fact_manager;
+  SetUpIdSynonyms(&fact_manager, context.get());
+
+  auto global_constant_synonym = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(19, SpvOpStore, 1, 47, 0),
+      MakeDataDescriptor(210, {}), 0);
+  ASSERT_TRUE(
+      global_constant_synonym.IsApplicable(context.get(), fact_manager));
+  global_constant_synonym.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  auto replace_vector_access_chain_index = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(54, SpvOpAccessChain, 1, 55, 0),
+      MakeDataDescriptor(204, {}), 0);
+  ASSERT_TRUE(replace_vector_access_chain_index.IsApplicable(context.get(),
+                                                             fact_manager));
+  replace_vector_access_chain_index.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // This is an interesting case because it replaces something that is being
+  // copied with something that is already a synonym.
+  auto regular_replacement = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(15, SpvOpCopyObject, 0, 202, 0),
+      MakeDataDescriptor(201, {}), 0);
+  ASSERT_TRUE(regular_replacement.IsApplicable(context.get(), fact_manager));
+  regular_replacement.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  auto regular_replacement2 = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(55, SpvOpStore, 0, 203, 0),
+      MakeDataDescriptor(203, {}), 0);
+  ASSERT_TRUE(regular_replacement2.IsApplicable(context.get(), fact_manager));
+  regular_replacement2.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  auto good_op_phi = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(74, SpvOpPhi, 2, 86, 0),
+      MakeDataDescriptor(205, {}), 0);
+  ASSERT_TRUE(good_op_phi.IsApplicable(context.get(), fact_manager));
+  good_op_phi.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  const std::string after_transformation = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main" %42
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 310
+               OpName %4 "main"
+               OpName %9 "buf"
+               OpMemberName %9 0 "a"
+               OpMemberName %9 1 "b"
+               OpMemberName %9 2 "c"
+               OpName %11 ""
+               OpName %42 "color"
+               OpMemberDecorate %9 0 Offset 0
+               OpMemberDecorate %9 1 Offset 4
+               OpMemberDecorate %9 2 Offset 8
+               OpDecorate %9 Block
+               OpDecorate %11 DescriptorSet 0
+               OpDecorate %11 Binding 0
+               OpDecorate %42 Location 0
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %9 = OpTypeStruct %6 %6 %6
+         %10 = OpTypePointer Uniform %9
+         %11 = OpVariable %10 Uniform
+         %12 = OpConstant %6 0
+         %13 = OpTypePointer Uniform %6
+         %16 = OpTypeFloat 32
+         %19 = OpConstant %16 0
+         %26 = OpConstant %6 1
+         %29 = OpTypeBool
+         %32 = OpConstant %6 4
+         %40 = OpTypeVector %16 4
+         %41 = OpTypePointer Output %40
+         %42 = OpVariable %41 Output
+         %44 = OpTypeInt 32 0
+         %45 = OpConstant %44 0
+         %46 = OpTypePointer Output %16
+         %50 = OpConstant %44 1
+         %54 = OpConstant %44 2
+         %58 = OpConstant %44 3
+         %64 = OpConstant %6 2
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+        %209 = OpCopyObject %6 %12
+         %14 = OpAccessChain %13 %11 %12
+         %15 = OpLoad %6 %14
+        %200 = OpCopyObject %6 %15
+               OpBranch %20
+         %20 = OpLabel
+         %84 = OpPhi %6 %15 %5 %86 %69
+         %27 = OpAccessChain %13 %11 %26
+         %28 = OpLoad %6 %27
+        %207 = OpCopyObject %6 %84
+        %201 = OpCopyObject %6 %15
+         %30 = OpSLessThan %29 %84 %28
+               OpLoopMerge %22 %69 None
+               OpBranchConditional %30 %21 %22
+         %21 = OpLabel
+         %33 = OpSMod %6 %84 %32
+        %208 = OpCopyObject %6 %33
+               OpSelectionMerge %39 None
+               OpSwitch %33 %38 0 %34 1 %35 2 %36 3 %37
+         %38 = OpLabel
+        %202 = OpCopyObject %6 %201
+               OpBranch %39
+         %34 = OpLabel
+        %210 = OpCopyObject %16 %19
+         %47 = OpAccessChain %46 %42 %45
+               OpStore %47 %210
+               OpBranch %39
+         %35 = OpLabel
+         %51 = OpAccessChain %46 %42 %50
+               OpStore %51 %19
+               OpBranch %39
+         %36 = OpLabel
+        %204 = OpCopyObject %44 %54
+         %55 = OpAccessChain %46 %42 %204
+        %203 = OpCopyObject %46 %55
+               OpStore %203 %19
+               OpBranch %39
+         %37 = OpLabel
+         %59 = OpAccessChain %46 %42 %58
+               OpStore %59 %19
+               OpBranch %39
+         %39 = OpLabel
+        %300 = OpIAdd %6 %15 %15
+         %65 = OpAccessChain %13 %11 %64
+         %66 = OpLoad %6 %65
+         %67 = OpSGreaterThan %29 %84 %66
+               OpSelectionMerge %69 None
+               OpBranchConditional %67 %68 %72
+         %68 = OpLabel
+         %71 = OpIAdd %6 %84 %26
+               OpBranch %69
+         %72 = OpLabel
+         %74 = OpIAdd %6 %84 %64
+        %205 = OpCopyObject %6 %74
+               OpBranch %69
+         %69 = OpLabel
+         %86 = OpPhi %6 %71 %68 %205 %72
+        %301 = OpPhi %6 %71 %68 %15 %72
+               OpBranch %20
+         %22 = OpLabel
+         %75 = OpAccessChain %46 %42 %50
+         %76 = OpLoad %16 %75
+         %78 = OpConvertSToF %16 %84
+         %80 = OpAccessChain %46 %42 %45
+        %206 = OpCopyObject %16 %78
+         %81 = OpLoad %16 %80
+         %79 = OpFAdd %16 %76 %78
+         %82 = OpFAdd %16 %81 %79
+               OpStore %80 %82
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationReplaceIdWithSynonymTest, SynonymsOfVariables) {
+  // The following SPIR-V comes from this GLSL, with object copies added:
+  //
+  // #version 310 es
+  //
+  // precision highp int;
+  //
+  // int g;
+  //
+  // void main() {
+  //   int l;
+  //   l = g;
+  //   g = l;
+  // }
+  const 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 %8 "l"
+               OpName %10 "g"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypePointer Function %6
+          %9 = OpTypePointer Private %6
+         %10 = OpVariable %9 Private
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+          %8 = OpVariable %7 Function
+        %100 = OpCopyObject %9 %10
+        %101 = OpCopyObject %7 %8
+         %11 = OpLoad %6 %10
+               OpStore %8 %11
+         %12 = OpLoad %6 %8
+               OpStore %10 %12
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  const auto env = SPV_ENV_UNIVERSAL_1_3;
+  const auto consumer = nullptr;
+  const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  FactManager fact_manager;
+
+  fact_manager.AddFact(MakeFact(10, 100), context.get());
+  fact_manager.AddFact(MakeFact(8, 101), context.get());
+
+  // Replace %10 with %100 in:
+  // %11 = OpLoad %6 %10
+  auto replacement1 = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(10, SpvOpLoad, 0, 11, 0),
+      MakeDataDescriptor(100, {}), 0);
+  ASSERT_TRUE(replacement1.IsApplicable(context.get(), fact_manager));
+  replacement1.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %8 with %101 in:
+  // OpStore %8 %11
+  auto replacement2 = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(8, SpvOpStore, 0, 11, 0),
+      MakeDataDescriptor(101, {}), 0);
+  ASSERT_TRUE(replacement2.IsApplicable(context.get(), fact_manager));
+  replacement2.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %8 with %101 in:
+  // %12 = OpLoad %6 %8
+  auto replacement3 = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(8, SpvOpLoad, 0, 12, 0),
+      MakeDataDescriptor(101, {}), 0);
+  ASSERT_TRUE(replacement3.IsApplicable(context.get(), fact_manager));
+  replacement3.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %10 with %100 in:
+  // OpStore %10 %12
+  auto replacement4 = TransformationReplaceIdWithSynonym(
+      transformation::MakeIdUseDescriptor(10, SpvOpStore, 0, 12, 0),
+      MakeDataDescriptor(100, {}), 0);
+  ASSERT_TRUE(replacement4.IsApplicable(context.get(), fact_manager));
+  replacement4.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  const std::string after_transformation = 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 %8 "l"
+               OpName %10 "g"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypePointer Function %6
+          %9 = OpTypePointer Private %6
+         %10 = OpVariable %9 Private
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+          %8 = OpVariable %7 Function
+        %100 = OpCopyObject %9 %10
+        %101 = OpCopyObject %7 %8
+         %11 = OpLoad %6 %100
+               OpStore %101 %11
+         %12 = OpLoad %6 %101
+               OpStore %100 %12
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+}  // namespace
+}  // namespace fuzz
+}  // namespace spvtools