diff --git a/source/fuzz/fuzzer_pass_apply_id_synonyms.cpp b/source/fuzz/fuzzer_pass_apply_id_synonyms.cpp
index fe1a92b..6ff42ca 100644
--- a/source/fuzz/fuzzer_pass_apply_id_synonyms.cpp
+++ b/source/fuzz/fuzzer_pass_apply_id_synonyms.cpp
@@ -14,7 +14,11 @@
 
 #include "source/fuzz/fuzzer_pass_apply_id_synonyms.h"
 
+#include "source/fuzz/data_descriptor.h"
+#include "source/fuzz/fuzzer_util.h"
 #include "source/fuzz/id_use_descriptor.h"
+#include "source/fuzz/instruction_descriptor.h"
+#include "source/fuzz/transformation_composite_extract.h"
 #include "source/fuzz/transformation_replace_id_with_synonym.h"
 
 namespace spvtools {
@@ -29,90 +33,113 @@
 FuzzerPassApplyIdSynonyms::~FuzzerPassApplyIdSynonyms() = default;
 
 void FuzzerPassApplyIdSynonyms::Apply() {
-  std::vector<TransformationReplaceIdWithSynonym> transformations_to_apply;
-
   for (auto id_with_known_synonyms :
        GetFactManager()->GetIdsForWhichSynonymsAreKnown(GetIRContext())) {
+    // Gather up all uses of |id_with_known_synonym|, and then subsequently
+    // iterate over these uses.  We use this separation because, when
+    // considering a given use, we might apply a transformation that will
+    // invalidate the def-use manager.
+    std::vector<std::pair<opt::Instruction*, uint32_t>> uses;
     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;
-          }
-
-          // |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 use_in_operand_index =
-              use_index - use_inst->NumOperands() + use_inst->NumInOperands();
-
-          std::vector<const protobufs::DataDescriptor*> synonyms_to_try;
-          for (auto& data_descriptor : GetFactManager()->GetSynonymsForId(
-                   id_with_known_synonyms, GetIRContext())) {
-            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);
-
-            if (!TransformationReplaceIdWithSynonym::
-                    ReplacingUseWithSynonymIsOk(GetIRContext(), use_inst,
-                                                use_in_operand_index,
-                                                *synonym_to_try)) {
-              continue;
-            }
-
-            // At present, we generate direct id synonyms (through
-            // OpCopyObject), which require no indices, and id synonyms that
-            // require a single index (through OpCompositeConstruct).
-            assert(synonym_to_try->index_size() <= 1);
-
-            // If an index is required, then we need to extract an element
-            // from a composite (e.g. through OpCompositeExtract), and this
-            // requires a fresh result id.
-            auto fresh_id_for_temporary =
-                synonym_to_try->index().empty()
-                    ? 0
-                    : GetFuzzerContext()->GetFreshId();
-
-            TransformationReplaceIdWithSynonym replace_id_transformation(
-                MakeIdUseDescriptorFromUse(GetIRContext(), use_inst,
-                                           use_in_operand_index),
-                *synonym_to_try, fresh_id_for_temporary);
-
-            // 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;
-          }
+        [&uses](opt::Instruction* use_inst, uint32_t use_index) -> void {
+          uses.emplace_back(
+              std::pair<opt::Instruction*, uint32_t>(use_inst, use_index));
         });
-  }
 
-  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();
+    for (auto& use : uses) {
+      auto use_inst = use.first;
+      auto use_index = use.second;
+      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) {
+        continue;
+      }
+      if (!GetFuzzerContext()->ChoosePercentage(
+              GetFuzzerContext()->GetChanceOfReplacingIdWithSynonym())) {
+        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 use_in_operand_index =
+          use_index - use_inst->NumOperands() + use_inst->NumInOperands();
+      if (!TransformationReplaceIdWithSynonym::UseCanBeReplacedWithSynonym(
+              GetIRContext(), use_inst, use_in_operand_index)) {
+        continue;
+      }
+
+      std::vector<const protobufs::DataDescriptor*> synonyms_to_try;
+      for (auto& data_descriptor : GetFactManager()->GetSynonymsForId(
+               id_with_known_synonyms, GetIRContext())) {
+        protobufs::DataDescriptor descriptor_for_this_id =
+            MakeDataDescriptor(id_with_known_synonyms, {});
+        if (DataDescriptorEquals()(data_descriptor, &descriptor_for_this_id)) {
+          // Exclude the fact that the id is synonymous with itself.
+          continue;
+        }
+        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);
+
+        if (synonym_to_try->index_size() > 0 &&
+            use_inst->opcode() == SpvOpPhi) {
+          // We are trying to replace an operand to an OpPhi.  This means
+          // we cannot use a composite synonym, because that requires
+          // extracting a component from a composite and we cannot insert
+          // an extract instruction before an OpPhi.
+          //
+          // TODO(afd): We could consider inserting the extract instruction
+          //  into the relevant parent block of the OpPhi.
+          continue;
+        }
+
+        if (!TransformationReplaceIdWithSynonym::IdsIsAvailableAtUse(
+                GetIRContext(), use_inst, use_in_operand_index,
+                synonym_to_try->object())) {
+          continue;
+        }
+
+        // We either replace the use with an id known to be synonymous, or
+        // an id that will hold the result of extracting a synonym from a
+        // composite.
+        uint32_t id_with_which_to_replace_use;
+        if (synonym_to_try->index_size() == 0) {
+          id_with_which_to_replace_use = synonym_to_try->object();
+        } else {
+          id_with_which_to_replace_use = GetFuzzerContext()->GetFreshId();
+          protobufs::InstructionDescriptor instruction_to_insert_before =
+              MakeInstructionDescriptor(GetIRContext(), use_inst);
+          TransformationCompositeExtract composite_extract_transformation(
+              instruction_to_insert_before, id_with_which_to_replace_use,
+              synonym_to_try->object(),
+              fuzzerutil::RepeatedFieldToVector(synonym_to_try->index()));
+          assert(composite_extract_transformation.IsApplicable(
+                     GetIRContext(), *GetFactManager()) &&
+                 "Transformation should be applicable by construction.");
+          composite_extract_transformation.Apply(GetIRContext(),
+                                                 GetFactManager());
+          *GetTransformations()->add_transformation() =
+              composite_extract_transformation.ToMessage();
+        }
+
+        TransformationReplaceIdWithSynonym replace_id_transformation(
+            MakeIdUseDescriptorFromUse(GetIRContext(), use_inst,
+                                       use_in_operand_index),
+            id_with_which_to_replace_use);
+
+        // The transformation should be applicable by construction.
+        assert(replace_id_transformation.IsApplicable(GetIRContext(),
+                                                      *GetFactManager()));
+        replace_id_transformation.Apply(GetIRContext(), GetFactManager());
+        *GetTransformations()->add_transformation() =
+            replace_id_transformation.ToMessage();
+        break;
+      }
+    }
   }
 }
 
diff --git a/source/fuzz/id_use_descriptor.cpp b/source/fuzz/id_use_descriptor.cpp
index 105c310..a8c23fa 100644
--- a/source/fuzz/id_use_descriptor.cpp
+++ b/source/fuzz/id_use_descriptor.cpp
@@ -53,29 +53,9 @@
     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,
-          MakeInstructionDescriptor(base_instruction_result_id, inst->opcode(),
-                                    num_opcodes_to_ignore),
-          in_operand_index);
-    }
-    if (inst_in_block.opcode() == inst->opcode()) {
-      num_opcodes_to_ignore++;
-    }
-  }
-  assert(false && "No matching instruction was found.");
-  return protobufs::IdUseDescriptor();
+  return MakeIdUseDescriptor(in_operand.words[0],
+                             MakeInstructionDescriptor(context, inst),
+                             in_operand_index);
 }
 
 }  // namespace fuzz
diff --git a/source/fuzz/instruction_descriptor.cpp b/source/fuzz/instruction_descriptor.cpp
index 2b4217a..c0cc5e5 100644
--- a/source/fuzz/instruction_descriptor.cpp
+++ b/source/fuzz/instruction_descriptor.cpp
@@ -72,7 +72,7 @@
   const SpvOp opcode =
       inst_it->opcode();    // The opcode of the instruction being described.
   uint32_t skip_count = 0;  // The number of these opcodes we have skipped when
-                            // searching backwards.
+  // searching backwards.
 
   // Consider instructions in the block in reverse order, starting from
   // |inst_it|.
@@ -101,5 +101,27 @@
   return MakeInstructionDescriptor(block.id(), opcode, skip_count);
 }
 
+protobufs::InstructionDescriptor MakeInstructionDescriptor(
+    opt::IRContext* context, opt::Instruction* inst) {
+  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 MakeInstructionDescriptor(base_instruction_result_id,
+                                       inst->opcode(), num_opcodes_to_ignore);
+    }
+    if (inst_in_block.opcode() == inst->opcode()) {
+      num_opcodes_to_ignore++;
+    }
+  }
+  assert(false && "No matching instruction was found.");
+  return protobufs::InstructionDescriptor();
+}
+
 }  // namespace fuzz
 }  // namespace spvtools
diff --git a/source/fuzz/instruction_descriptor.h b/source/fuzz/instruction_descriptor.h
index c0febca..2ccd15a 100644
--- a/source/fuzz/instruction_descriptor.h
+++ b/source/fuzz/instruction_descriptor.h
@@ -43,6 +43,10 @@
     const opt::BasicBlock& block,
     const opt::BasicBlock::const_iterator& inst_it);
 
+// Returns an InstructionDescriptor that describes the given instruction |inst|.
+protobufs::InstructionDescriptor MakeInstructionDescriptor(
+    opt::IRContext* context, opt::Instruction* inst);
+
 }  // namespace fuzz
 }  // namespace spvtools
 
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index 17984f9..b33c2e5 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -432,19 +432,15 @@
 
 message TransformationReplaceIdWithSynonym {
 
-  // Replaces an id use with something known to be synonymous with that id use,
-  // e.g. because it was obtained via applying OpCopyObject
+  // Replaces a use of an id with an id that is known to be synonymous, e.g.
+  // because it was obtained via applying OpCopyObject
 
-  // Identifies the id use that is to be replaced
+  // The id use that is to be replaced
   IdUseDescriptor id_use_descriptor = 1;
 
-  // Identifies the data with which the id use is expected to be synonymous
-  DataDescriptor data_descriptor = 2;
+  // The synonymous id
+  uint32 synonymous_id = 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 TransformationSetFunctionControl {
diff --git a/source/fuzz/transformation_replace_id_with_synonym.cpp b/source/fuzz/transformation_replace_id_with_synonym.cpp
index bd2f734..79ba012 100644
--- a/source/fuzz/transformation_replace_id_with_synonym.cpp
+++ b/source/fuzz/transformation_replace_id_with_synonym.cpp
@@ -31,22 +31,21 @@
     : 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().empty()));
+    protobufs::IdUseDescriptor id_use_descriptor, uint32_t synonymous_id) {
   *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);
+  message_.set_synonymous_id(synonymous_id);
 }
 
 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.IsSynonymous(
-          MakeDataDescriptor(message_.id_use_descriptor().id_of_interest(), {}),
-          message_.data_descriptor(), context)) {
+  auto data_descriptor_for_synonymous_id =
+      MakeDataDescriptor(message_.synonymous_id(), {});
+  if (!fact_manager.IsSynonymous(MakeDataDescriptor(id_of_interest, {}),
+                                 data_descriptor_for_synonymous_id, context)) {
     return false;
   }
 
@@ -57,34 +56,18 @@
     return false;
   }
 
-  // Is it legitimate to replace the use identified by the id use descriptor
-  // with a synonym?
-  if (!ReplacingUseWithSynonymIsOk(
+  // Is the use suitable for being replaced in principle?
+  if (!UseCanBeReplacedWithSynonym(
           context, use_instruction,
-          message_.id_use_descriptor().in_operand_index(),
-          message_.data_descriptor())) {
+          message_.id_use_descriptor().in_operand_index())) {
     return false;
   }
 
-  if (message_.fresh_id_for_temporary() == 0) {
-    if (!message_.data_descriptor().index().empty()) {
-      // If we have no id to use as a temporary variable, we should not have any
-      // indices to extract from.
-      return false;
-    }
-  } else {
-    if (!fuzzerutil::IsFreshId(context, message_.fresh_id_for_temporary())) {
-      // The id to be used as a temporary needs to be fresh.
-      return false;
-    }
-    if (message_.data_descriptor().index_size() != 1) {
-      // At present we support just a single index to allow extracting directly
-      // from a composite.
-      return false;
-    }
-  }
-
-  return true;
+  // The transformation is applicable if the synonymous id is available at the
+  // use point.
+  return IdsIsAvailableAtUse(context, use_instruction,
+                             message_.id_use_descriptor().in_operand_index(),
+                             message_.synonymous_id());
 }
 
 void TransformationReplaceIdWithSynonym::Apply(
@@ -92,77 +75,9 @@
     spvtools::fuzz::FactManager* /*unused*/) const {
   auto instruction_to_change =
       FindInstructionContainingUse(message_.id_use_descriptor(), context);
-
-  // Ultimately we are going to replace the id use identified in the
-  // transformation with |replacement_id|, which will either be the synonym's
-  // id, or the id of a temporary used to extract the synonym from a composite.
-  uint32_t replacement_id;
-
-  if (message_.fresh_id_for_temporary()) {
-    // The transformation having a temporary variable means that we need to
-    // extract the synonym from a composite.
-
-    uint32_t type_id_of_id_to_be_replaced =
-        context->get_def_use_mgr()
-            ->GetDef(message_.id_use_descriptor().id_of_interest())
-            ->type_id();
-    opt::analysis::Type* type_of_id_to_be_replaced =
-        context->get_type_mgr()->GetType(type_id_of_id_to_be_replaced);
-    opt::analysis::Type* type_of_composite = context->get_type_mgr()->GetType(
-        context->get_def_use_mgr()
-            ->GetDef(message_.data_descriptor().object())
-            ->type_id());
-
-    // Intuitively we want to make an OpCompositeExtract instruction, to get the
-    // synonym out of the composite. But in the case of a vector, the synonym
-    // might involve multiple vector indices; e.g. the y and z components of a
-    // vec4 might be synonymous with a vec2, and in that case OpCompositeExtract
-    // doesn't give us what we want; we need to use OpVectorShuffle instead.
-    std::unique_ptr<opt::Instruction> new_instruction;
-    if (type_of_composite->AsVector() &&
-        type_of_composite->AsVector()->element_type() !=
-            type_of_id_to_be_replaced) {
-      // We need to extract a vector from inside a vector, so we will need to
-      // use OpVectorShuffle.
-
-      assert(type_of_id_to_be_replaced->AsVector());
-      assert(type_of_id_to_be_replaced->AsVector()->element_type() ==
-             type_of_composite->AsVector()->element_type());
-      opt::Instruction::OperandList shuffle_operands = {
-          {SPV_OPERAND_TYPE_ID, {message_.data_descriptor().object()}},
-          {SPV_OPERAND_TYPE_ID, {message_.data_descriptor().object()}}};
-      for (uint32_t i = 0;
-           i < type_of_id_to_be_replaced->AsVector()->element_count(); i++) {
-        shuffle_operands.push_back({SPV_OPERAND_TYPE_LITERAL_INTEGER,
-                                    {message_.data_descriptor().index(0) + i}});
-      }
-      new_instruction = MakeUnique<opt::Instruction>(
-          context, SpvOpVectorShuffle, type_id_of_id_to_be_replaced,
-          message_.fresh_id_for_temporary(), shuffle_operands);
-    } else {
-      // We are either extracting from a non-vector, or extracting a scalar from
-      // a vector, so we can use OpCompositeExtract.
-      opt::Instruction::OperandList extract_operands = {
-          {SPV_OPERAND_TYPE_ID, {message_.data_descriptor().object()}},
-          {SPV_OPERAND_TYPE_LITERAL_INTEGER,
-           {message_.data_descriptor().index(0)}}};
-      new_instruction = MakeUnique<opt::Instruction>(
-          context, SpvOpCompositeExtract, type_id_of_id_to_be_replaced,
-          message_.fresh_id_for_temporary(), extract_operands);
-    }
-    instruction_to_change->InsertBefore(std::move(new_instruction));
-
-    // The replacement id is the temporary variable we used to extract the
-    // synonym from a composite.
-    replacement_id = message_.fresh_id_for_temporary();
-    fuzzerutil::UpdateModuleIdBound(context, replacement_id);
-  } else {
-    // The replacement id is the synonym's id.
-    replacement_id = message_.data_descriptor().object();
-  }
-
   instruction_to_change->SetInOperand(
-      message_.id_use_descriptor().in_operand_index(), {replacement_id});
+      message_.id_use_descriptor().in_operand_index(),
+      {message_.synonymous_id()});
   context->InvalidateAnalysesExceptFor(opt::IRContext::Analysis::kAnalysisNone);
 }
 
@@ -173,22 +88,33 @@
   return result;
 }
 
-bool TransformationReplaceIdWithSynonym::ReplacingUseWithSynonymIsOk(
+bool TransformationReplaceIdWithSynonym::IdsIsAvailableAtUse(
     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.
+    uint32_t use_input_operand_index, uint32_t id) {
+  if (!context->get_instr_block(id)) {
+    return true;
+  }
+  auto defining_instruction = context->get_def_use_mgr()->GetDef(id);
+  if (defining_instruction == use_instruction) {
     return false;
   }
+  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_input_operand_index + 1);
+    return dominator_analysis->Dominates(
+        context->get_instr_block(defining_instruction)->id(), parent_block);
+  }
+  return dominator_analysis->Dominates(defining_instruction, use_instruction);
+}
 
+bool TransformationReplaceIdWithSynonym::UseCanBeReplacedWithSynonym(
+    opt::IRContext* context, opt::Instruction* use_instruction,
+    uint32_t use_in_operand_index) {
   if (use_instruction->opcode() == SpvOpAccessChain &&
       use_in_operand_index > 0) {
     // This is an access chain index.  If the (sub-)object being accessed by the
@@ -262,31 +188,6 @@
       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.
-  // This is only relevant if the defining instruction is in a block; if it is
-  // not in a block then it is at global scope, and so replacing the use with it
-  // is fine.
-  if (context->get_instr_block(defining_instruction)) {
-    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;
 }
 
diff --git a/source/fuzz/transformation_replace_id_with_synonym.h b/source/fuzz/transformation_replace_id_with_synonym.h
index f9d797a..c21673d 100644
--- a/source/fuzz/transformation_replace_id_with_synonym.h
+++ b/source/fuzz/transformation_replace_id_with_synonym.h
@@ -29,40 +29,46 @@
       const protobufs::TransformationReplaceIdWithSynonym& message);
 
   TransformationReplaceIdWithSynonym(
-      protobufs::IdUseDescriptor id_use_descriptor,
-      protobufs::DataDescriptor data_descriptor,
-      uint32_t fresh_id_for_temporary);
+      protobufs::IdUseDescriptor id_use_descriptor, uint32_t synonymous_id);
 
   // - 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
+  //   |message_.synonymous_id|.
+  // - Replacing the id in |message_.id_use_descriptor| by
+  //   |message_.synonymous_id| 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.
   // - The id must not be a pointer argument to a function call (because the
   //   synonym might not be a memory object declaration).
   // - |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.
+  // synonymous id identified by |message_.synonymous_id|.
   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);
+  // Checks whether the |id| is available (according to dominance rules) at the
+  // use point defined by input operand |use_input_operand_index| of
+  // |use_instruction|.
+  static bool IdsIsAvailableAtUse(opt::IRContext* context,
+                                  opt::Instruction* use_instruction,
+                                  uint32_t use_input_operand_index,
+                                  uint32_t id);
+
+  // Checks whether various conditions hold related to the acceptability of
+  // replacing the id use at |use_in_operand_index| of |use_instruction| with
+  // a synonym.  In particular, this checks that:
+  // - the id use is not an index into a struct field in an OpAccessChain - such
+  //   indices must be constants, so it is dangerous to replace them.
+  // - the id use is not a pointer function call argument, on which there are
+  //   restrictions that make replacement problematic.
+  static bool UseCanBeReplacedWithSynonym(opt::IRContext* context,
+                                          opt::Instruction* use_instruction,
+                                          uint32_t use_in_operand_index);
 
  private:
   protobufs::TransformationReplaceIdWithSynonym message_;
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index 2a17090..b38f35e 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -17,6 +17,7 @@
   set(SOURCES
           fuzz_test_util.h
 
+          data_synonym_transformation_test.cpp
           equivalence_relation_test.cpp
           fact_manager_test.cpp
           fuzz_test_util.cpp
@@ -37,6 +38,7 @@
           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_set_function_control_test.cpp
           transformation_set_loop_control_test.cpp
           transformation_set_memory_operands_mask_test.cpp
diff --git a/test/fuzz/data_synonym_transformation_test.cpp b/test/fuzz/data_synonym_transformation_test.cpp
new file mode 100644
index 0000000..21ea068
--- /dev/null
+++ b/test/fuzz/data_synonym_transformation_test.cpp
@@ -0,0 +1,1122 @@
+// 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/data_descriptor.h"
+#include "source/fuzz/id_use_descriptor.h"
+#include "source/fuzz/instruction_descriptor.h"
+#include "source/fuzz/transformation_composite_extract.h"
+#include "source/fuzz/transformation_replace_id_with_synonym.h"
+#include "source/fuzz/transformation_vector_shuffle.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+// This file captures tests that check correctness of the collective use of a
+// number of transformations that relate to data synonyms.
+
+protobufs::Fact MakeSynonymFact(uint32_t first_id,
+                                std::vector<uint32_t>&& first_indices,
+                                uint32_t second_id,
+                                std::vector<uint32_t>&& second_indices) {
+  protobufs::FactDataSynonym data_synonym_fact;
+  *data_synonym_fact.mutable_data1() =
+      MakeDataDescriptor(first_id, std::move(first_indices));
+  *data_synonym_fact.mutable_data2() =
+      MakeDataDescriptor(second_id, std::move(second_indices));
+  protobufs::Fact result;
+  *result.mutable_data_synonym_fact() = data_synonym_fact;
+  return result;
+}
+
+TEST(DataSynonymTransformationTest, ArrayCompositeSynonyms) {
+  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 %11 "A"
+               OpName %20 "B"
+               OpName %31 "g"
+               OpName %35 "h"
+               OpDecorate %11 RelaxedPrecision
+               OpDecorate %22 RelaxedPrecision
+               OpDecorate %27 RelaxedPrecision
+               OpDecorate %35 RelaxedPrecision
+               OpDecorate %36 RelaxedPrecision
+               OpDecorate %40 RelaxedPrecision
+               OpDecorate %41 RelaxedPrecision
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypeInt 32 0
+          %8 = OpConstant %7 3
+          %9 = OpTypeArray %6 %8
+         %10 = OpTypePointer Function %9
+         %12 = OpConstant %6 0
+         %13 = OpConstant %6 3
+         %14 = OpTypePointer Function %6
+         %16 = OpTypeFloat 32
+         %17 = OpConstant %7 4
+         %18 = OpTypeArray %16 %17
+         %19 = OpTypePointer Function %18
+         %24 = OpTypePointer Function %16
+         %28 = OpConstant %16 42
+         %30 = OpConstant %6 2
+         %34 = OpConstant %6 1
+         %38 = OpConstant %6 42
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %11 = OpVariable %10 Function
+         %20 = OpVariable %19 Function
+         %31 = OpVariable %24 Function
+         %35 = OpVariable %14 Function
+         %15 = OpAccessChain %14 %11 %12
+         %21 = OpAccessChain %14 %11 %12
+         %22 = OpLoad %6 %21
+        %100 = OpCompositeConstruct %9 %12 %13 %22
+               OpStore %15 %13
+         %23 = OpConvertSToF %16 %22
+         %25 = OpAccessChain %24 %20 %12
+               OpStore %25 %23
+         %26 = OpAccessChain %14 %11 %12
+         %27 = OpLoad %6 %26
+         %29 = OpAccessChain %24 %20 %27
+               OpStore %29 %28
+         %32 = OpLoad %16 %31
+        %101 = OpCompositeConstruct %18 %28 %23 %32 %23
+         %50 = OpCopyObject %16 %23
+         %51 = OpCopyObject %16 %23
+         %33 = OpAccessChain %24 %20 %30
+               OpStore %33 %28
+               OpStore %33 %32
+         %36 = OpLoad %6 %35
+         %37 = OpAccessChain %14 %11 %34
+               OpStore %37 %36
+         %39 = OpAccessChain %14 %11 %12
+         %40 = OpLoad %6 %39
+         %41 = OpIAdd %6 %38 %40
+         %42 = OpAccessChain %14 %11 %30
+               OpStore %42 %41
+               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(MakeSynonymFact(12, {}, 100, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(13, {}, 100, {1}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(22, {}, 100, {2}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(28, {}, 101, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(23, {}, 101, {1}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(32, {}, 101, {2}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(23, {}, 101, {3}), context.get());
+
+  // Replace %12 with %100[0] in '%25 = OpAccessChain %24 %20 %12'
+  auto instruction_descriptor_1 =
+      MakeInstructionDescriptor(25, SpvOpAccessChain, 0);
+  auto good_extract_1 =
+      TransformationCompositeExtract(instruction_descriptor_1, 102, 100, {0});
+  // Bad: id already in use
+  auto bad_extract_1 = TransformationCompositeExtract(
+      MakeInstructionDescriptor(25, SpvOpAccessChain, 0), 25, 100, {0});
+  ASSERT_TRUE(good_extract_1.IsApplicable(context.get(), fact_manager));
+  ASSERT_FALSE(bad_extract_1.IsApplicable(context.get(), fact_manager));
+  good_extract_1.Apply(context.get(), &fact_manager);
+  auto replacement_1 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(12, instruction_descriptor_1, 1), 102);
+  ASSERT_TRUE(replacement_1.IsApplicable(context.get(), fact_manager));
+  replacement_1.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %13 with %100[1] in 'OpStore %15 %13'
+  auto instruction_descriptor_2 = MakeInstructionDescriptor(100, SpvOpStore, 0);
+  auto good_extract_2 =
+      TransformationCompositeExtract(instruction_descriptor_2, 103, 100, {1});
+  // No bad example provided here.
+  ASSERT_TRUE(good_extract_2.IsApplicable(context.get(), fact_manager));
+  good_extract_2.Apply(context.get(), &fact_manager);
+  auto replacement_2 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(13, instruction_descriptor_2, 1), 103);
+  ASSERT_TRUE(replacement_2.IsApplicable(context.get(), fact_manager));
+  replacement_2.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %22 with %100[2] in '%23 = OpConvertSToF %16 %22'
+  auto instruction_descriptor_3 =
+      MakeInstructionDescriptor(23, SpvOpConvertSToF, 0);
+  auto good_extract_3 =
+      TransformationCompositeExtract(instruction_descriptor_3, 104, 100, {2});
+  ASSERT_TRUE(good_extract_3.IsApplicable(context.get(), fact_manager));
+  good_extract_3.Apply(context.get(), &fact_manager);
+  auto replacement_3 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(22, instruction_descriptor_3, 0), 104);
+  // Bad: wrong input operand index
+  auto bad_replacement_3 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(22, instruction_descriptor_3, 1), 104);
+  ASSERT_TRUE(replacement_3.IsApplicable(context.get(), fact_manager));
+  ASSERT_FALSE(bad_replacement_3.IsApplicable(context.get(), fact_manager));
+  replacement_3.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %28 with %101[0] in 'OpStore %33 %28'
+  auto instruction_descriptor_4 = MakeInstructionDescriptor(33, SpvOpStore, 0);
+  auto good_extract_4 =
+      TransformationCompositeExtract(instruction_descriptor_4, 105, 101, {0});
+  // Bad: instruction descriptor does not identify an appropriate instruction
+  auto bad_extract_4 = TransformationCompositeExtract(
+      MakeInstructionDescriptor(33, SpvOpCopyObject, 0), 105, 101, {0});
+  ASSERT_TRUE(good_extract_4.IsApplicable(context.get(), fact_manager));
+  ASSERT_FALSE(bad_extract_4.IsApplicable(context.get(), fact_manager));
+  good_extract_4.Apply(context.get(), &fact_manager);
+  auto replacement_4 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(28, instruction_descriptor_4, 1), 105);
+  ASSERT_TRUE(replacement_4.IsApplicable(context.get(), fact_manager));
+  replacement_4.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %23 with %101[1] in '%50 = OpCopyObject %16 %23'
+  auto instruction_descriptor_5 =
+      MakeInstructionDescriptor(50, SpvOpCopyObject, 0);
+  auto good_extract_5 =
+      TransformationCompositeExtract(instruction_descriptor_5, 106, 101, {1});
+  ASSERT_TRUE(good_extract_5.IsApplicable(context.get(), fact_manager));
+  good_extract_5.Apply(context.get(), &fact_manager);
+  auto replacement_5 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(23, instruction_descriptor_5, 0), 106);
+  // Bad: wrong synonym fact being used
+  auto bad_replacement_5 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(23, instruction_descriptor_5, 0), 105);
+  ASSERT_TRUE(replacement_5.IsApplicable(context.get(), fact_manager));
+  ASSERT_FALSE(bad_replacement_5.IsApplicable(context.get(), fact_manager));
+  replacement_5.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %32 with %101[2] in 'OpStore %33 %32'
+  auto instruction_descriptor_6 = MakeInstructionDescriptor(33, SpvOpStore, 1);
+  auto good_extract_6 =
+      TransformationCompositeExtract(instruction_descriptor_6, 107, 101, {2});
+  // Bad: id 1001 does not exist
+  auto bad_extract_6 =
+      TransformationCompositeExtract(instruction_descriptor_6, 107, 1001, {2});
+  ASSERT_TRUE(good_extract_6.IsApplicable(context.get(), fact_manager));
+  ASSERT_FALSE(bad_extract_6.IsApplicable(context.get(), fact_manager));
+  good_extract_6.Apply(context.get(), &fact_manager);
+  auto replacement_6 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(32, instruction_descriptor_6, 1), 107);
+  ASSERT_TRUE(replacement_6.IsApplicable(context.get(), fact_manager));
+  replacement_6.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %23 with %101[3] in '%51 = OpCopyObject %16 %23'
+  auto instruction_descriptor_7 =
+      MakeInstructionDescriptor(51, SpvOpCopyObject, 0);
+  auto good_extract_7 =
+      TransformationCompositeExtract(instruction_descriptor_7, 108, 101, {3});
+  ASSERT_TRUE(good_extract_7.IsApplicable(context.get(), fact_manager));
+  good_extract_7.Apply(context.get(), &fact_manager);
+  auto replacement_7 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(23, instruction_descriptor_7, 0), 108);
+  // Bad: use id 0 is invalid
+  auto bad_replacement_7 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(0, instruction_descriptor_7, 0), 108);
+  ASSERT_TRUE(replacement_7.IsApplicable(context.get(), fact_manager));
+  ASSERT_FALSE(bad_replacement_7.IsApplicable(context.get(), fact_manager));
+  replacement_7.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 %11 "A"
+               OpName %20 "B"
+               OpName %31 "g"
+               OpName %35 "h"
+               OpDecorate %11 RelaxedPrecision
+               OpDecorate %22 RelaxedPrecision
+               OpDecorate %27 RelaxedPrecision
+               OpDecorate %35 RelaxedPrecision
+               OpDecorate %36 RelaxedPrecision
+               OpDecorate %40 RelaxedPrecision
+               OpDecorate %41 RelaxedPrecision
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypeInt 32 0
+          %8 = OpConstant %7 3
+          %9 = OpTypeArray %6 %8
+         %10 = OpTypePointer Function %9
+         %12 = OpConstant %6 0
+         %13 = OpConstant %6 3
+         %14 = OpTypePointer Function %6
+         %16 = OpTypeFloat 32
+         %17 = OpConstant %7 4
+         %18 = OpTypeArray %16 %17
+         %19 = OpTypePointer Function %18
+         %24 = OpTypePointer Function %16
+         %28 = OpConstant %16 42
+         %30 = OpConstant %6 2
+         %34 = OpConstant %6 1
+         %38 = OpConstant %6 42
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %11 = OpVariable %10 Function
+         %20 = OpVariable %19 Function
+         %31 = OpVariable %24 Function
+         %35 = OpVariable %14 Function
+         %15 = OpAccessChain %14 %11 %12
+         %21 = OpAccessChain %14 %11 %12
+         %22 = OpLoad %6 %21
+        %100 = OpCompositeConstruct %9 %12 %13 %22
+        %103 = OpCompositeExtract %6 %100 1
+               OpStore %15 %103
+        %104 = OpCompositeExtract %6 %100 2
+         %23 = OpConvertSToF %16 %104
+        %102 = OpCompositeExtract %6 %100 0
+         %25 = OpAccessChain %24 %20 %102
+               OpStore %25 %23
+         %26 = OpAccessChain %14 %11 %12
+         %27 = OpLoad %6 %26
+         %29 = OpAccessChain %24 %20 %27
+               OpStore %29 %28
+         %32 = OpLoad %16 %31
+        %101 = OpCompositeConstruct %18 %28 %23 %32 %23
+        %106 = OpCompositeExtract %16 %101 1
+         %50 = OpCopyObject %16 %106
+        %108 = OpCompositeExtract %16 %101 3
+         %51 = OpCopyObject %16 %108
+         %33 = OpAccessChain %24 %20 %30
+        %105 = OpCompositeExtract %16 %101 0
+               OpStore %33 %105
+        %107 = OpCompositeExtract %16 %101 2
+               OpStore %33 %107
+         %36 = OpLoad %6 %35
+         %37 = OpAccessChain %14 %11 %34
+               OpStore %37 %36
+         %39 = OpAccessChain %14 %11 %12
+         %40 = OpLoad %6 %39
+         %41 = OpIAdd %6 %38 %40
+         %42 = OpAccessChain %14 %11 %30
+               OpStore %42 %41
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(DataSynonymTransformationTest, MatrixCompositeSynonyms) {
+  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 %10 "m"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeFloat 32
+          %7 = OpTypeVector %6 4
+         %50 = OpUndef %7
+          %8 = OpTypeMatrix %7 3
+          %9 = OpTypePointer Function %8
+         %11 = OpTypeInt 32 1
+         %12 = OpConstant %11 0
+         %13 = OpConstant %6 1
+         %14 = OpConstantComposite %7 %13 %13 %13 %13
+         %15 = OpTypePointer Function %7
+         %17 = OpConstant %11 1
+         %18 = OpConstant %6 2
+         %19 = OpConstantComposite %7 %18 %18 %18 %18
+         %21 = OpConstant %11 2
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %10 = OpVariable %9 Function
+         %16 = OpAccessChain %15 %10 %12
+               OpStore %16 %14
+         %20 = OpAccessChain %15 %10 %17
+               OpStore %20 %19
+         %22 = OpAccessChain %15 %10 %12
+         %23 = OpLoad %7 %22
+         %24 = OpAccessChain %15 %10 %17
+         %25 = OpLoad %7 %24
+        %100 = OpCompositeConstruct %8 %23 %25 %50
+         %26 = OpFAdd %7 %23 %25
+         %27 = OpAccessChain %15 %10 %21
+               OpStore %27 %26
+               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(MakeSynonymFact(23, {}, 100, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(25, {}, 100, {1}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(50, {}, 100, {2}), context.get());
+
+  // Replace %23 with %100[0] in '%26 = OpFAdd %7 %23 %25'
+  auto instruction_descriptor_1 = MakeInstructionDescriptor(26, SpvOpFAdd, 0);
+  auto extract_1 =
+      TransformationCompositeExtract(instruction_descriptor_1, 101, 100, {0});
+  ASSERT_TRUE(extract_1.IsApplicable(context.get(), fact_manager));
+  extract_1.Apply(context.get(), &fact_manager);
+  auto replacement_1 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(23, instruction_descriptor_1, 0), 101);
+  ASSERT_TRUE(replacement_1.IsApplicable(context.get(), fact_manager));
+  replacement_1.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %25 with %100[1] in '%26 = OpFAdd %7 %23 %25'
+  auto instruction_descriptor_2 = MakeInstructionDescriptor(26, SpvOpFAdd, 0);
+  auto extract_2 =
+      TransformationCompositeExtract(instruction_descriptor_2, 102, 100, {1});
+  ASSERT_TRUE(extract_2.IsApplicable(context.get(), fact_manager));
+  extract_2.Apply(context.get(), &fact_manager);
+  auto replacement_2 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(25, instruction_descriptor_2, 1), 102);
+  ASSERT_TRUE(replacement_2.IsApplicable(context.get(), fact_manager));
+  replacement_2.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 %10 "m"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeFloat 32
+          %7 = OpTypeVector %6 4
+         %50 = OpUndef %7
+          %8 = OpTypeMatrix %7 3
+          %9 = OpTypePointer Function %8
+         %11 = OpTypeInt 32 1
+         %12 = OpConstant %11 0
+         %13 = OpConstant %6 1
+         %14 = OpConstantComposite %7 %13 %13 %13 %13
+         %15 = OpTypePointer Function %7
+         %17 = OpConstant %11 1
+         %18 = OpConstant %6 2
+         %19 = OpConstantComposite %7 %18 %18 %18 %18
+         %21 = OpConstant %11 2
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %10 = OpVariable %9 Function
+         %16 = OpAccessChain %15 %10 %12
+               OpStore %16 %14
+         %20 = OpAccessChain %15 %10 %17
+               OpStore %20 %19
+         %22 = OpAccessChain %15 %10 %12
+         %23 = OpLoad %7 %22
+         %24 = OpAccessChain %15 %10 %17
+         %25 = OpLoad %7 %24
+        %100 = OpCompositeConstruct %8 %23 %25 %50
+        %101 = OpCompositeExtract %7 %100 0
+        %102 = OpCompositeExtract %7 %100 1
+         %26 = OpFAdd %7 %101 %102
+         %27 = OpAccessChain %15 %10 %21
+               OpStore %27 %26
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(DataSynonymTransformationTest, StructCompositeSynonyms) {
+  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 %9 "Inner"
+               OpMemberName %9 0 "a"
+               OpMemberName %9 1 "b"
+               OpName %11 "i1"
+               OpName %17 "i2"
+               OpName %31 "Point"
+               OpMemberName %31 0 "x"
+               OpMemberName %31 1 "y"
+               OpMemberName %31 2 "z"
+               OpName %32 "Outer"
+               OpMemberName %32 0 "c"
+               OpMemberName %32 1 "d"
+               OpName %34 "o1"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypeFloat 32
+          %8 = OpTypeVector %7 2
+          %9 = OpTypeStruct %6 %8
+         %10 = OpTypePointer Function %9
+         %12 = OpConstant %6 1
+         %13 = OpConstant %7 2
+         %14 = OpConstant %7 3
+         %15 = OpConstantComposite %8 %13 %14
+         %16 = OpConstantComposite %9 %12 %15
+         %18 = OpConstant %6 0
+         %19 = OpTypePointer Function %6
+         %24 = OpTypePointer Function %8
+         %27 = OpConstant %7 4
+         %31 = OpTypeStruct %7 %7 %7
+         %32 = OpTypeStruct %9 %31
+         %33 = OpTypePointer Function %32
+         %36 = OpConstant %7 10
+         %37 = OpTypeInt 32 0
+         %38 = OpConstant %37 0
+         %39 = OpTypePointer Function %7
+         %42 = OpConstant %37 1
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %11 = OpVariable %10 Function
+         %17 = OpVariable %10 Function
+         %34 = OpVariable %33 Function
+        %101 = OpCompositeConstruct %31 %27 %36 %27
+               OpStore %11 %16
+         %20 = OpAccessChain %19 %11 %18
+         %21 = OpLoad %6 %20
+         %22 = OpIAdd %6 %21 %12
+        %102 = OpCompositeConstruct %9 %22 %15
+         %23 = OpAccessChain %19 %17 %18
+               OpStore %23 %22
+         %25 = OpAccessChain %24 %17 %12
+         %26 = OpLoad %8 %25
+         %28 = OpCompositeConstruct %8 %27 %27
+         %29 = OpFAdd %8 %26 %28
+         %30 = OpAccessChain %24 %17 %12
+               OpStore %30 %29
+         %35 = OpLoad %9 %11
+         %40 = OpAccessChain %39 %11 %12 %38
+         %41 = OpLoad %7 %40
+         %43 = OpAccessChain %39 %11 %12 %42
+         %44 = OpLoad %7 %43
+         %45 = OpCompositeConstruct %31 %36 %41 %44
+        %100 = OpCompositeConstruct %32 %16 %45
+         %46 = OpCompositeConstruct %32 %35 %45
+               OpStore %34 %46
+               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(MakeSynonymFact(16, {}, 100, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(45, {}, 100, {1}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(27, {}, 101, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(36, {}, 101, {1}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(27, {}, 101, {2}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(22, {}, 102, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(15, {}, 102, {1}), context.get());
+
+  // Replace %45 with %100[1] in '%46 = OpCompositeConstruct %32 %35 %45'
+  auto instruction_descriptor_1 =
+      MakeInstructionDescriptor(46, SpvOpCompositeConstruct, 0);
+  auto extract_1 =
+      TransformationCompositeExtract(instruction_descriptor_1, 201, 100, {1});
+  ASSERT_TRUE(extract_1.IsApplicable(context.get(), fact_manager));
+  extract_1.Apply(context.get(), &fact_manager);
+  auto replacement_1 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(45, instruction_descriptor_1, 1), 201);
+  ASSERT_TRUE(replacement_1.IsApplicable(context.get(), fact_manager));
+  replacement_1.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace second occurrence of %27 with %101[0] in '%28 =
+  // OpCompositeConstruct %8 %27 %27'
+  auto instruction_descriptor_2 =
+      MakeInstructionDescriptor(28, SpvOpCompositeConstruct, 0);
+  auto extract_2 =
+      TransformationCompositeExtract(instruction_descriptor_2, 202, 101, {0});
+  ASSERT_TRUE(extract_2.IsApplicable(context.get(), fact_manager));
+  extract_2.Apply(context.get(), &fact_manager);
+  auto replacement_2 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(27, instruction_descriptor_2, 1), 202);
+  ASSERT_TRUE(replacement_2.IsApplicable(context.get(), fact_manager));
+  replacement_2.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %36 with %101[1] in '%45 = OpCompositeConstruct %31 %36 %41 %44'
+  auto instruction_descriptor_3 =
+      MakeInstructionDescriptor(45, SpvOpCompositeConstruct, 0);
+  auto extract_3 =
+      TransformationCompositeExtract(instruction_descriptor_3, 203, 101, {1});
+  ASSERT_TRUE(extract_3.IsApplicable(context.get(), fact_manager));
+  extract_3.Apply(context.get(), &fact_manager);
+  auto replacement_3 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(36, instruction_descriptor_3, 0), 203);
+  ASSERT_TRUE(replacement_3.IsApplicable(context.get(), fact_manager));
+  replacement_3.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace first occurrence of %27 with %101[2] in '%28 = OpCompositeConstruct
+  // %8 %27 %27'
+  auto instruction_descriptor_4 =
+      MakeInstructionDescriptor(28, SpvOpCompositeConstruct, 0);
+  auto extract_4 =
+      TransformationCompositeExtract(instruction_descriptor_4, 204, 101, {2});
+  ASSERT_TRUE(extract_4.IsApplicable(context.get(), fact_manager));
+  extract_4.Apply(context.get(), &fact_manager);
+  auto replacement_4 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(27, instruction_descriptor_4, 0), 204);
+  ASSERT_TRUE(replacement_4.IsApplicable(context.get(), fact_manager));
+  replacement_4.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %22 with %102[0] in 'OpStore %23 %22'
+  auto instruction_descriptor_5 = MakeInstructionDescriptor(23, SpvOpStore, 0);
+  auto extract_5 =
+      TransformationCompositeExtract(instruction_descriptor_5, 205, 102, {0});
+  ASSERT_TRUE(extract_5.IsApplicable(context.get(), fact_manager));
+  extract_5.Apply(context.get(), &fact_manager);
+  auto replacement_5 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(22, instruction_descriptor_5, 1), 205);
+  ASSERT_TRUE(replacement_5.IsApplicable(context.get(), fact_manager));
+  replacement_5.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 %9 "Inner"
+               OpMemberName %9 0 "a"
+               OpMemberName %9 1 "b"
+               OpName %11 "i1"
+               OpName %17 "i2"
+               OpName %31 "Point"
+               OpMemberName %31 0 "x"
+               OpMemberName %31 1 "y"
+               OpMemberName %31 2 "z"
+               OpName %32 "Outer"
+               OpMemberName %32 0 "c"
+               OpMemberName %32 1 "d"
+               OpName %34 "o1"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypeFloat 32
+          %8 = OpTypeVector %7 2
+          %9 = OpTypeStruct %6 %8
+         %10 = OpTypePointer Function %9
+         %12 = OpConstant %6 1
+         %13 = OpConstant %7 2
+         %14 = OpConstant %7 3
+         %15 = OpConstantComposite %8 %13 %14
+         %16 = OpConstantComposite %9 %12 %15
+         %18 = OpConstant %6 0
+         %19 = OpTypePointer Function %6
+         %24 = OpTypePointer Function %8
+         %27 = OpConstant %7 4
+         %31 = OpTypeStruct %7 %7 %7
+         %32 = OpTypeStruct %9 %31
+         %33 = OpTypePointer Function %32
+         %36 = OpConstant %7 10
+         %37 = OpTypeInt 32 0
+         %38 = OpConstant %37 0
+         %39 = OpTypePointer Function %7
+         %42 = OpConstant %37 1
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %11 = OpVariable %10 Function
+         %17 = OpVariable %10 Function
+         %34 = OpVariable %33 Function
+        %101 = OpCompositeConstruct %31 %27 %36 %27
+               OpStore %11 %16
+         %20 = OpAccessChain %19 %11 %18
+         %21 = OpLoad %6 %20
+         %22 = OpIAdd %6 %21 %12
+        %102 = OpCompositeConstruct %9 %22 %15
+         %23 = OpAccessChain %19 %17 %18
+        %205 = OpCompositeExtract %6 %102 0
+               OpStore %23 %205
+         %25 = OpAccessChain %24 %17 %12
+         %26 = OpLoad %8 %25
+        %202 = OpCompositeExtract %7 %101 0
+        %204 = OpCompositeExtract %7 %101 2
+         %28 = OpCompositeConstruct %8 %204 %202
+         %29 = OpFAdd %8 %26 %28
+         %30 = OpAccessChain %24 %17 %12
+               OpStore %30 %29
+         %35 = OpLoad %9 %11
+         %40 = OpAccessChain %39 %11 %12 %38
+         %41 = OpLoad %7 %40
+         %43 = OpAccessChain %39 %11 %12 %42
+         %44 = OpLoad %7 %43
+        %203 = OpCompositeExtract %7 %101 1
+         %45 = OpCompositeConstruct %31 %203 %41 %44
+        %100 = OpCompositeConstruct %32 %16 %45
+        %201 = OpCompositeExtract %31 %100 1
+         %46 = OpCompositeConstruct %32 %35 %201
+               OpStore %34 %46
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(DataSynonymTransformationTest, VectorCompositeSynonyms) {
+  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 "f"
+               OpName %12 "v2"
+               OpName %18 "v3"
+               OpName %23 "v4"
+               OpName %32 "b"
+               OpName %36 "bv2"
+               OpName %41 "bv3"
+               OpName %50 "bv4"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeFloat 32
+          %7 = OpTypePointer Function %6
+          %9 = OpConstant %6 42
+         %10 = OpTypeVector %6 2
+         %11 = OpTypePointer Function %10
+         %16 = OpTypeVector %6 3
+         %17 = OpTypePointer Function %16
+         %21 = OpTypeVector %6 4
+         %22 = OpTypePointer Function %21
+         %30 = OpTypeBool
+         %31 = OpTypePointer Function %30
+         %33 = OpConstantFalse %30
+         %34 = OpTypeVector %30 2
+         %35 = OpTypePointer Function %34
+         %37 = OpConstantTrue %30
+         %38 = OpConstantComposite %34 %37 %37
+         %39 = OpTypeVector %30 3
+         %40 = OpTypePointer Function %39
+         %48 = OpTypeVector %30 4
+         %49 = OpTypePointer Function %48
+         %51 = OpTypeInt 32 0
+         %52 = OpConstant %51 2
+         %55 = OpConstant %6 0
+         %57 = OpConstant %51 1
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+          %8 = OpVariable %7 Function
+         %12 = OpVariable %11 Function
+         %18 = OpVariable %17 Function
+         %23 = OpVariable %22 Function
+         %32 = OpVariable %31 Function
+         %36 = OpVariable %35 Function
+         %41 = OpVariable %40 Function
+         %50 = OpVariable %49 Function
+               OpStore %8 %9
+         %13 = OpLoad %6 %8
+         %14 = OpLoad %6 %8
+         %15 = OpCompositeConstruct %10 %13 %14
+               OpStore %12 %15
+         %19 = OpLoad %10 %12
+         %20 = OpVectorShuffle %16 %19 %19 0 0 1
+               OpStore %18 %20
+         %24 = OpLoad %16 %18
+         %25 = OpLoad %6 %8
+         %26 = OpCompositeExtract %6 %24 0
+         %27 = OpCompositeExtract %6 %24 1
+         %28 = OpCompositeExtract %6 %24 2
+         %29 = OpCompositeConstruct %21 %26 %27 %28 %25
+               OpStore %23 %29
+               OpStore %32 %33
+               OpStore %36 %38
+         %42 = OpLoad %30 %32
+         %43 = OpLoad %34 %36
+         %44 = OpVectorShuffle %34 %43 %43 0 0
+         %45 = OpCompositeExtract %30 %44 0
+         %46 = OpCompositeExtract %30 %44 1
+         %47 = OpCompositeConstruct %39 %42 %45 %46
+               OpStore %41 %47
+         %53 = OpAccessChain %7 %23 %52
+         %54 = OpLoad %6 %53
+
+        %100 = OpCompositeConstruct %21 %20 %54
+        %101 = OpCompositeConstruct %21 %15 %19
+        %102 = OpCompositeConstruct %16 %27 %15
+        %103 = OpCompositeConstruct %48 %33 %47
+        %104 = OpCompositeConstruct %34 %42 %45
+        %105 = OpCompositeConstruct %39 %38 %46
+
+         %86 = OpCopyObject %30 %33
+         %56 = OpFOrdNotEqual %30 %54 %55
+         %80 = OpCopyObject %16 %20
+         %58 = OpAccessChain %7 %18 %57
+         %59 = OpLoad %6 %58
+         %60 = OpFOrdNotEqual %30 %59 %55
+         %61 = OpLoad %34 %36
+         %62 = OpLogicalAnd %30 %45 %46
+         %63 = OpLogicalOr %30 %45 %46
+         %64 = OpCompositeConstruct %48 %56 %60 %62 %63
+               OpStore %12 %15
+         %81 = OpVectorShuffle %16 %19 %19 0 0 1
+         %82 = OpCompositeConstruct %21 %26 %27 %28 %25
+         %83 = OpCopyObject %10 %15
+         %84 = OpCopyObject %39 %47
+               OpStore %50 %64
+         %85 = OpCopyObject %30 %42
+               OpStore %36 %38
+               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(MakeSynonymFact(20, {0}, 100, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(20, {1}, 100, {1}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(20, {2}, 100, {2}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(54, {}, 100, {3}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(15, {0}, 101, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(15, {1}, 101, {1}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(19, {0}, 101, {2}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(19, {1}, 101, {3}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(27, {}, 102, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(15, {0}, 102, {1}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(15, {1}, 102, {2}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(33, {}, 103, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(47, {0}, 103, {1}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(47, {1}, 103, {2}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(47, {2}, 103, {3}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(42, {}, 104, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(45, {}, 104, {1}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(38, {0}, 105, {0}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(38, {1}, 105, {1}), context.get());
+  fact_manager.AddFact(MakeSynonymFact(46, {}, 105, {2}), context.get());
+
+  // Replace %20 with %100[0:2] in '%80 = OpCopyObject %16 %20'
+  auto instruction_descriptor_1 =
+      MakeInstructionDescriptor(80, SpvOpCopyObject, 0);
+  auto shuffle_1 = TransformationVectorShuffle(instruction_descriptor_1, 200,
+                                               100, 100, {0, 1, 2});
+  ASSERT_TRUE(shuffle_1.IsApplicable(context.get(), fact_manager));
+  shuffle_1.Apply(context.get(), &fact_manager);
+  auto replacement_1 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(20, instruction_descriptor_1, 0), 200);
+  ASSERT_TRUE(replacement_1.IsApplicable(context.get(), fact_manager));
+  replacement_1.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %54 with %100[3] in '%56 = OpFOrdNotEqual %30 %54 %55'
+  auto instruction_descriptor_2 =
+      MakeInstructionDescriptor(56, SpvOpFOrdNotEqual, 0);
+  auto extract_2 =
+      TransformationCompositeExtract(instruction_descriptor_2, 201, 100, {3});
+
+  ASSERT_TRUE(extract_2.IsApplicable(context.get(), fact_manager));
+  extract_2.Apply(context.get(), &fact_manager);
+  auto replacement_2 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(54, instruction_descriptor_2, 0), 201);
+  ASSERT_TRUE(replacement_2.IsApplicable(context.get(), fact_manager));
+  replacement_2.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %15 with %101[0:1] in 'OpStore %12 %15'
+  auto instruction_descriptor_3 = MakeInstructionDescriptor(64, SpvOpStore, 0);
+  auto shuffle_3 = TransformationVectorShuffle(instruction_descriptor_3, 202,
+                                               101, 101, {0, 1});
+  ASSERT_TRUE(shuffle_3.IsApplicable(context.get(), fact_manager));
+  shuffle_3.Apply(context.get(), &fact_manager);
+  auto replacement_3 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(15, instruction_descriptor_3, 1), 202);
+  ASSERT_TRUE(replacement_3.IsApplicable(context.get(), fact_manager));
+  replacement_3.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %19 with %101[2:3] in '%81 = OpVectorShuffle %16 %19 %19 0 0 1'
+  auto instruction_descriptor_4 =
+      MakeInstructionDescriptor(81, SpvOpVectorShuffle, 0);
+  auto shuffle_4 = TransformationVectorShuffle(instruction_descriptor_4, 203,
+                                               101, 101, {2, 3});
+  ASSERT_TRUE(shuffle_4.IsApplicable(context.get(), fact_manager));
+  shuffle_4.Apply(context.get(), &fact_manager);
+  auto replacement_4 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(19, instruction_descriptor_4, 0), 203);
+  ASSERT_TRUE(replacement_4.IsApplicable(context.get(), fact_manager));
+  replacement_4.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %27 with %102[0] in '%82 = OpCompositeConstruct %21 %26 %27 %28
+  // %25'
+  auto instruction_descriptor_5 =
+      MakeInstructionDescriptor(82, SpvOpCompositeConstruct, 0);
+  auto extract_5 =
+      TransformationCompositeExtract(instruction_descriptor_5, 204, 102, {0});
+
+  ASSERT_TRUE(extract_5.IsApplicable(context.get(), fact_manager));
+  extract_5.Apply(context.get(), &fact_manager);
+  auto replacement_5 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(27, instruction_descriptor_5, 1), 204);
+  ASSERT_TRUE(replacement_5.IsApplicable(context.get(), fact_manager));
+  replacement_5.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %15 with %102[1:2] in '%83 = OpCopyObject %10 %15'
+  auto instruction_descriptor_6 =
+      MakeInstructionDescriptor(83, SpvOpCopyObject, 0);
+  auto shuffle_6 = TransformationVectorShuffle(instruction_descriptor_6, 205,
+                                               102, 102, {1, 2});
+  ASSERT_TRUE(shuffle_6.IsApplicable(context.get(), fact_manager));
+  shuffle_6.Apply(context.get(), &fact_manager);
+  auto replacement_6 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(15, instruction_descriptor_6, 0), 205);
+  ASSERT_TRUE(replacement_6.IsApplicable(context.get(), fact_manager));
+  replacement_6.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %33 with %103[0] in '%86 = OpCopyObject %30 %33'
+  auto instruction_descriptor_7 =
+      MakeInstructionDescriptor(86, SpvOpCopyObject, 0);
+  auto extract_7 =
+      TransformationCompositeExtract(instruction_descriptor_7, 206, 103, {0});
+  ASSERT_TRUE(extract_7.IsApplicable(context.get(), fact_manager));
+  extract_7.Apply(context.get(), &fact_manager);
+  auto replacement_7 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(33, instruction_descriptor_7, 0), 206);
+  ASSERT_TRUE(replacement_7.IsApplicable(context.get(), fact_manager));
+  replacement_7.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %47 with %103[1:3] in '%84 = OpCopyObject %39 %47'
+  auto instruction_descriptor_8 =
+      MakeInstructionDescriptor(84, SpvOpCopyObject, 0);
+  auto shuffle_8 = TransformationVectorShuffle(instruction_descriptor_8, 207,
+                                               103, 103, {1, 2, 3});
+  ASSERT_TRUE(shuffle_8.IsApplicable(context.get(), fact_manager));
+  shuffle_8.Apply(context.get(), &fact_manager);
+  auto replacement_8 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(47, instruction_descriptor_8, 0), 207);
+  ASSERT_TRUE(replacement_8.IsApplicable(context.get(), fact_manager));
+  replacement_8.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %42 with %104[0] in '%85 = OpCopyObject %30 %42'
+  auto instruction_descriptor_9 =
+      MakeInstructionDescriptor(85, SpvOpCopyObject, 0);
+  auto extract_9 =
+      TransformationCompositeExtract(instruction_descriptor_9, 208, 104, {0});
+  ASSERT_TRUE(extract_9.IsApplicable(context.get(), fact_manager));
+  extract_9.Apply(context.get(), &fact_manager);
+  auto replacement_9 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(42, instruction_descriptor_9, 0), 208);
+  ASSERT_TRUE(replacement_9.IsApplicable(context.get(), fact_manager));
+  replacement_9.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %45 with %104[1] in '%63 = OpLogicalOr %30 %45 %46'
+  auto instruction_descriptor_10 =
+      MakeInstructionDescriptor(63, SpvOpLogicalOr, 0);
+  auto extract_10 =
+      TransformationCompositeExtract(instruction_descriptor_10, 209, 104, {1});
+  ASSERT_TRUE(extract_10.IsApplicable(context.get(), fact_manager));
+  extract_10.Apply(context.get(), &fact_manager);
+  auto replacement_10 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(45, instruction_descriptor_10, 0), 209);
+  ASSERT_TRUE(replacement_10.IsApplicable(context.get(), fact_manager));
+  replacement_10.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %38 with %105[0:1] in 'OpStore %36 %38'
+  auto instruction_descriptor_11 = MakeInstructionDescriptor(85, SpvOpStore, 0);
+  auto shuffle_11 = TransformationVectorShuffle(instruction_descriptor_11, 210,
+                                                105, 105, {0, 1});
+  ASSERT_TRUE(shuffle_11.IsApplicable(context.get(), fact_manager));
+  shuffle_11.Apply(context.get(), &fact_manager);
+  auto replacement_11 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(38, instruction_descriptor_11, 1), 210);
+  ASSERT_TRUE(replacement_11.IsApplicable(context.get(), fact_manager));
+  replacement_11.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replace %46 with %105[2] in '%62 = OpLogicalAnd %30 %45 %46'
+  auto instruction_descriptor_12 =
+      MakeInstructionDescriptor(62, SpvOpLogicalAnd, 0);
+  auto extract_12 =
+      TransformationCompositeExtract(instruction_descriptor_12, 211, 105, {2});
+  ASSERT_TRUE(extract_12.IsApplicable(context.get(), fact_manager));
+  extract_12.Apply(context.get(), &fact_manager);
+  auto replacement_12 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(46, instruction_descriptor_12, 1), 211);
+  ASSERT_TRUE(replacement_12.IsApplicable(context.get(), fact_manager));
+  replacement_12.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 "f"
+               OpName %12 "v2"
+               OpName %18 "v3"
+               OpName %23 "v4"
+               OpName %32 "b"
+               OpName %36 "bv2"
+               OpName %41 "bv3"
+               OpName %50 "bv4"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeFloat 32
+          %7 = OpTypePointer Function %6
+          %9 = OpConstant %6 42
+         %10 = OpTypeVector %6 2
+         %11 = OpTypePointer Function %10
+         %16 = OpTypeVector %6 3
+         %17 = OpTypePointer Function %16
+         %21 = OpTypeVector %6 4
+         %22 = OpTypePointer Function %21
+         %30 = OpTypeBool
+         %31 = OpTypePointer Function %30
+         %33 = OpConstantFalse %30
+         %34 = OpTypeVector %30 2
+         %35 = OpTypePointer Function %34
+         %37 = OpConstantTrue %30
+         %38 = OpConstantComposite %34 %37 %37
+         %39 = OpTypeVector %30 3
+         %40 = OpTypePointer Function %39
+         %48 = OpTypeVector %30 4
+         %49 = OpTypePointer Function %48
+         %51 = OpTypeInt 32 0
+         %52 = OpConstant %51 2
+         %55 = OpConstant %6 0
+         %57 = OpConstant %51 1
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+          %8 = OpVariable %7 Function
+         %12 = OpVariable %11 Function
+         %18 = OpVariable %17 Function
+         %23 = OpVariable %22 Function
+         %32 = OpVariable %31 Function
+         %36 = OpVariable %35 Function
+         %41 = OpVariable %40 Function
+         %50 = OpVariable %49 Function
+               OpStore %8 %9
+         %13 = OpLoad %6 %8
+         %14 = OpLoad %6 %8
+         %15 = OpCompositeConstruct %10 %13 %14
+               OpStore %12 %15
+         %19 = OpLoad %10 %12
+         %20 = OpVectorShuffle %16 %19 %19 0 0 1
+               OpStore %18 %20
+         %24 = OpLoad %16 %18
+         %25 = OpLoad %6 %8
+         %26 = OpCompositeExtract %6 %24 0
+         %27 = OpCompositeExtract %6 %24 1
+         %28 = OpCompositeExtract %6 %24 2
+         %29 = OpCompositeConstruct %21 %26 %27 %28 %25
+               OpStore %23 %29
+               OpStore %32 %33
+               OpStore %36 %38
+         %42 = OpLoad %30 %32
+         %43 = OpLoad %34 %36
+         %44 = OpVectorShuffle %34 %43 %43 0 0
+         %45 = OpCompositeExtract %30 %44 0
+         %46 = OpCompositeExtract %30 %44 1
+         %47 = OpCompositeConstruct %39 %42 %45 %46
+               OpStore %41 %47
+         %53 = OpAccessChain %7 %23 %52
+         %54 = OpLoad %6 %53
+
+        %100 = OpCompositeConstruct %21 %20 %54
+        %101 = OpCompositeConstruct %21 %15 %19
+        %102 = OpCompositeConstruct %16 %27 %15
+        %103 = OpCompositeConstruct %48 %33 %47
+        %104 = OpCompositeConstruct %34 %42 %45
+        %105 = OpCompositeConstruct %39 %38 %46
+
+        %206 = OpCompositeExtract %30 %103 0
+         %86 = OpCopyObject %30 %206
+        %201 = OpCompositeExtract %6 %100 3
+         %56 = OpFOrdNotEqual %30 %201 %55
+        %200 = OpVectorShuffle %16 %100 %100 0 1 2
+         %80 = OpCopyObject %16 %200
+         %58 = OpAccessChain %7 %18 %57
+         %59 = OpLoad %6 %58
+         %60 = OpFOrdNotEqual %30 %59 %55
+         %61 = OpLoad %34 %36
+        %211 = OpCompositeExtract %30 %105 2
+         %62 = OpLogicalAnd %30 %45 %211
+        %209 = OpCompositeExtract %30 %104 1
+         %63 = OpLogicalOr %30 %209 %46
+         %64 = OpCompositeConstruct %48 %56 %60 %62 %63
+        %202 = OpVectorShuffle %10 %101 %101 0 1
+               OpStore %12 %202
+        %203 = OpVectorShuffle %10 %101 %101 2 3
+         %81 = OpVectorShuffle %16 %203 %19 0 0 1
+        %204 = OpCompositeExtract %6 %102 0
+         %82 = OpCompositeConstruct %21 %26 %204 %28 %25
+        %205 = OpVectorShuffle %10 %102 %102 1 2
+         %83 = OpCopyObject %10 %205
+        %207 = OpVectorShuffle %39 %103 %103 1 2 3
+         %84 = OpCopyObject %39 %207
+               OpStore %50 %64
+        %208 = OpCompositeExtract %30 %104 0
+         %85 = OpCopyObject %30 %208
+        %210 = OpVectorShuffle %34 %105 %105 0 1
+               OpStore %36 %210
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+}  // namespace
+}  // namespace fuzz
+}  // namespace spvtools
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 0000000..75e117a
--- /dev/null
+++ b/test/fuzz/transformation_replace_id_with_synonym_test.cpp
@@ -0,0 +1,1213 @@
+// 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 "source/fuzz/instruction_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 MakeSynonymFact(uint32_t first, uint32_t second) {
+  protobufs::FactDataSynonym data_synonym_fact;
+  *data_synonym_fact.mutable_data1() = MakeDataDescriptor(first, {});
+  *data_synonym_fact.mutable_data2() = MakeDataDescriptor(second, {});
+  protobufs::Fact result;
+  *result.mutable_data_synonym_fact() = data_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(MakeSynonymFact(15, 200), context);
+  fact_manager->AddFact(MakeSynonymFact(15, 201), context);
+  fact_manager->AddFact(MakeSynonymFact(15, 202), context);
+  fact_manager->AddFact(MakeSynonymFact(55, 203), context);
+  fact_manager->AddFact(MakeSynonymFact(54, 204), context);
+  fact_manager->AddFact(MakeSynonymFact(74, 205), context);
+  fact_manager->AddFact(MakeSynonymFact(78, 206), context);
+  fact_manager->AddFact(MakeSynonymFact(84, 207), context);
+  fact_manager->AddFact(MakeSynonymFact(33, 208), context);
+  fact_manager->AddFact(MakeSynonymFact(12, 209), context);
+  fact_manager->AddFact(MakeSynonymFact(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(
+      MakeIdUseDescriptor(15, MakeInstructionDescriptor(300, SpvOpIAdd, 0), 0),
+      202);
+  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(
+          MakeIdUseDescriptor(15, MakeInstructionDescriptor(301, SpvOpPhi, 0),
+                              2),
+          202);
+  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(
+      MakeIdUseDescriptor(
+          84, MakeInstructionDescriptor(67, SpvOpSGreaterThan, 0), 0),
+      200);
+  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(
+      MakeIdUseDescriptor(86, MakeInstructionDescriptor(84, SpvOpPhi, 0), 2),
+      74);
+  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(
+          MakeIdUseDescriptor(
+              84, MakeInstructionDescriptor(207, SpvOpCopyObject, 0), 0),
+          207);
+  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(
+      MakeIdUseDescriptor(
+          84, MakeInstructionDescriptor(200, SpvOpCopyObject, 0), 0),
+      207);
+  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(
+      MakeIdUseDescriptor(
+          12, MakeInstructionDescriptor(14, SpvOpAccessChain, 0), 1),
+      209);
+  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(
+      MakeIdUseDescriptor(19, MakeInstructionDescriptor(47, SpvOpStore, 0), 1),
+      210);
+  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(
+      MakeIdUseDescriptor(
+          54, MakeInstructionDescriptor(55, SpvOpAccessChain, 0), 1),
+      204);
+  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(
+      MakeIdUseDescriptor(
+          15, MakeInstructionDescriptor(202, SpvOpCopyObject, 0), 0),
+      201);
+  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(
+      MakeIdUseDescriptor(55, MakeInstructionDescriptor(203, SpvOpStore, 0), 0),
+      203);
+  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(
+      MakeIdUseDescriptor(74, MakeInstructionDescriptor(86, SpvOpPhi, 0), 2),
+      205);
+  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(MakeSynonymFact(10, 100), context.get());
+  fact_manager.AddFact(MakeSynonymFact(8, 101), context.get());
+
+  // Replace %10 with %100 in:
+  // %11 = OpLoad %6 %10
+  auto replacement1 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(10, MakeInstructionDescriptor(11, SpvOpLoad, 0), 0),
+      100);
+  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(
+      MakeIdUseDescriptor(8, MakeInstructionDescriptor(11, SpvOpStore, 0), 0),
+      101);
+  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(
+      MakeIdUseDescriptor(8, MakeInstructionDescriptor(12, SpvOpLoad, 0), 0),
+      101);
+  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(
+      MakeIdUseDescriptor(10, MakeInstructionDescriptor(12, SpvOpStore, 0), 0),
+      100);
+  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()));
+}
+
+TEST(TransformationReplaceIdWithSynonymTest,
+     SynonymOfVariableNoGoodInFunctionCall) {
+  // The following SPIR-V comes from this GLSL, with an object copy added:
+  //
+  // #version 310 es
+  //
+  // precision highp int;
+  //
+  // void foo(int x) { }
+  //
+  // void main() {
+  //   int a;
+  //   a = 2;
+  //   foo(a);
+  // }
+  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 %10 "foo(i1;"
+               OpName %9 "x"
+               OpName %12 "a"
+               OpName %14 "param"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypePointer Function %6
+          %8 = OpTypeFunction %2 %7
+         %13 = OpConstant %6 2
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %12 = OpVariable %7 Function
+         %14 = OpVariable %7 Function
+               OpStore %12 %13
+         %15 = OpLoad %6 %12
+               OpStore %14 %15
+        %100 = OpCopyObject %7 %14
+         %16 = OpFunctionCall %2 %10 %14
+               OpReturn
+               OpFunctionEnd
+         %10 = OpFunction %2 None %8
+          %9 = OpFunctionParameter %7
+         %11 = OpLabel
+               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(MakeSynonymFact(14, 100), context.get());
+
+  // Replace %14 with %100 in:
+  // %16 = OpFunctionCall %2 %10 %14
+  auto replacement = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          14, MakeInstructionDescriptor(16, SpvOpFunctionCall, 0), 1),
+      100);
+  ASSERT_FALSE(replacement.IsApplicable(context.get(), fact_manager));
+}
+
+TEST(TransformationReplaceIdWithSynonymTest, SynonymsOfAccessChainIndices) {
+  // The following SPIR-V comes from this GLSL, with object copies added:
+  //
+  // #version 310 es
+  //
+  // precision highp float;
+  // precision highp int;
+  //
+  // struct S {
+  //   int[3] a;
+  //   vec4 b;
+  //   bool c;
+  // } d;
+  //
+  // float[20] e;
+  //
+  // struct T {
+  //   float f;
+  //   S g;
+  // } h;
+  //
+  // T[4] i;
+  //
+  // void main() {
+  //   d.a[2] = 10;
+  //   d.b[3] = 11.0;
+  //   d.c = false;
+  //   e[17] = 12.0;
+  //   h.f = 13.0;
+  //   h.g.a[1] = 14;
+  //   h.g.b[0] = 15.0;
+  //   h.g.c = true;
+  //   i[0].f = 16.0;
+  //   i[1].g.a[0] = 17;
+  //   i[2].g.b[1] = 18.0;
+  //   i[3].g.c = true;
+  // }
+  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 %13 "S"
+               OpMemberName %13 0 "a"
+               OpMemberName %13 1 "b"
+               OpMemberName %13 2 "c"
+               OpName %15 "d"
+               OpName %31 "e"
+               OpName %35 "T"
+               OpMemberName %35 0 "f"
+               OpMemberName %35 1 "g"
+               OpName %37 "h"
+               OpName %50 "i"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypeInt 32 0
+          %8 = OpConstant %7 3
+          %9 = OpTypeArray %6 %8
+         %10 = OpTypeFloat 32
+         %11 = OpTypeVector %10 4
+         %12 = OpTypeBool
+         %13 = OpTypeStruct %9 %11 %12
+         %14 = OpTypePointer Private %13
+         %15 = OpVariable %14 Private
+         %16 = OpConstant %6 0
+         %17 = OpConstant %6 2
+         %18 = OpConstant %6 10
+         %19 = OpTypePointer Private %6
+         %21 = OpConstant %6 1
+         %22 = OpConstant %10 11
+         %23 = OpTypePointer Private %10
+         %25 = OpConstantFalse %12
+         %26 = OpTypePointer Private %12
+         %28 = OpConstant %7 20
+         %29 = OpTypeArray %10 %28
+         %30 = OpTypePointer Private %29
+         %31 = OpVariable %30 Private
+         %32 = OpConstant %6 17
+         %33 = OpConstant %10 12
+         %35 = OpTypeStruct %10 %13
+         %36 = OpTypePointer Private %35
+         %37 = OpVariable %36 Private
+         %38 = OpConstant %10 13
+         %40 = OpConstant %6 14
+         %42 = OpConstant %10 15
+         %43 = OpConstant %7 0
+         %45 = OpConstantTrue %12
+         %47 = OpConstant %7 4
+         %48 = OpTypeArray %35 %47
+         %49 = OpTypePointer Private %48
+         %50 = OpVariable %49 Private
+         %51 = OpConstant %10 16
+         %54 = OpConstant %10 18
+         %55 = OpConstant %7 1
+         %57 = OpConstant %6 3
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+
+         %100 = OpCopyObject %6 %16 ; 0
+         %101 = OpCopyObject %6 %21 ; 1
+         %102 = OpCopyObject %6 %17 ; 2
+         %103 = OpCopyObject %6 %57 ; 3
+         %104 = OpCopyObject %6 %18 ; 10
+         %105 = OpCopyObject %6 %40 ; 14
+         %106 = OpCopyObject %6 %32 ; 17
+         %107 = OpCopyObject %7 %43 ; 0
+         %108 = OpCopyObject %7 %55 ; 1
+         %109 = OpCopyObject %7  %8 ; 3
+         %110 = OpCopyObject %7 %47 ; 4
+         %111 = OpCopyObject %7 %28 ; 20
+         %112 = OpCopyObject %12 %45 ; true
+
+         %20 = OpAccessChain %19 %15 %16 %17
+               OpStore %20 %18
+         %24 = OpAccessChain %23 %15 %21 %8
+               OpStore %24 %22
+         %27 = OpAccessChain %26 %15 %17
+               OpStore %27 %25
+         %34 = OpAccessChain %23 %31 %32
+               OpStore %34 %33
+         %39 = OpAccessChain %23 %37 %16
+               OpStore %39 %38
+         %41 = OpAccessChain %19 %37 %21 %16 %21
+               OpStore %41 %40
+         %44 = OpAccessChain %23 %37 %21 %21 %43
+               OpStore %44 %42
+         %46 = OpAccessChain %26 %37 %21 %17
+               OpStore %46 %45
+         %52 = OpAccessChain %23 %50 %16 %16
+               OpStore %52 %51
+         %53 = OpAccessChain %19 %50 %21 %21 %16 %16
+               OpStore %53 %32
+         %56 = OpAccessChain %23 %50 %17 %21 %21 %55
+               OpStore %56 %54
+         %58 = OpAccessChain %26 %50 %57 %21 %17
+               OpStore %58 %45
+               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;
+
+  // Add synonym facts corresponding to the OpCopyObject operations that have
+  // been applied to all constants in the module.
+  fact_manager.AddFact(MakeSynonymFact(16, 100), context.get());
+  fact_manager.AddFact(MakeSynonymFact(21, 101), context.get());
+  fact_manager.AddFact(MakeSynonymFact(17, 102), context.get());
+  fact_manager.AddFact(MakeSynonymFact(57, 103), context.get());
+  fact_manager.AddFact(MakeSynonymFact(18, 104), context.get());
+  fact_manager.AddFact(MakeSynonymFact(40, 105), context.get());
+  fact_manager.AddFact(MakeSynonymFact(32, 106), context.get());
+  fact_manager.AddFact(MakeSynonymFact(43, 107), context.get());
+  fact_manager.AddFact(MakeSynonymFact(55, 108), context.get());
+  fact_manager.AddFact(MakeSynonymFact(8, 109), context.get());
+  fact_manager.AddFact(MakeSynonymFact(47, 110), context.get());
+  fact_manager.AddFact(MakeSynonymFact(28, 111), context.get());
+  fact_manager.AddFact(MakeSynonymFact(45, 112), context.get());
+
+  // Replacements of the form %16 -> %100
+
+  // %20 = OpAccessChain %19 %15 *%16* %17
+  // Corresponds to d.*a*[2]
+  // The index %16 used for a cannot be replaced
+  auto replacement1 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          16, MakeInstructionDescriptor(20, SpvOpAccessChain, 0), 1),
+      100);
+  ASSERT_FALSE(replacement1.IsApplicable(context.get(), fact_manager));
+
+  // %39 = OpAccessChain %23 %37 *%16*
+  // Corresponds to h.*f*
+  // The index %16 used for f cannot be replaced
+  auto replacement2 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          16, MakeInstructionDescriptor(39, SpvOpAccessChain, 0), 1),
+      100);
+  ASSERT_FALSE(replacement2.IsApplicable(context.get(), fact_manager));
+
+  // %41 = OpAccessChain %19 %37 %21 *%16* %21
+  // Corresponds to h.g.*a*[1]
+  // The index %16 used for a cannot be replaced
+  auto replacement3 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          16, MakeInstructionDescriptor(41, SpvOpAccessChain, 0), 2),
+      100);
+  ASSERT_FALSE(replacement3.IsApplicable(context.get(), fact_manager));
+
+  // %52 = OpAccessChain %23 %50 *%16* %16
+  // Corresponds to i[*0*].f
+  // The index %16 used for 0 *can* be replaced
+  auto replacement4 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          16, MakeInstructionDescriptor(52, SpvOpAccessChain, 0), 1),
+      100);
+  ASSERT_TRUE(replacement4.IsApplicable(context.get(), fact_manager));
+  replacement4.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // %52 = OpAccessChain %23 %50 %16 *%16*
+  // Corresponds to i[0].*f*
+  // The index %16 used for f cannot be replaced
+  auto replacement5 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          16, MakeInstructionDescriptor(52, SpvOpAccessChain, 0), 2),
+      100);
+  ASSERT_FALSE(replacement5.IsApplicable(context.get(), fact_manager));
+
+  // %53 = OpAccessChain %19 %50 %21 %21 *%16* %16
+  // Corresponds to i[1].g.*a*[0]
+  // The index %16 used for a cannot be replaced
+  auto replacement6 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          16, MakeInstructionDescriptor(53, SpvOpAccessChain, 0), 3),
+      100);
+  ASSERT_FALSE(replacement6.IsApplicable(context.get(), fact_manager));
+
+  // %53 = OpAccessChain %19 %50 %21 %21 %16 *%16*
+  // Corresponds to i[1].g.a[*0*]
+  // The index %16 used for 0 *can* be replaced
+  auto replacement7 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          16, MakeInstructionDescriptor(53, SpvOpAccessChain, 0), 4),
+      100);
+  ASSERT_TRUE(replacement7.IsApplicable(context.get(), fact_manager));
+  replacement7.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replacements of the form %21 -> %101
+
+  // %24 = OpAccessChain %23 %15 *%21* %8
+  // Corresponds to d.*b*[3]
+  // The index %24 used for b cannot be replaced
+  auto replacement8 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          21, MakeInstructionDescriptor(24, SpvOpAccessChain, 0), 1),
+      101);
+  ASSERT_FALSE(replacement8.IsApplicable(context.get(), fact_manager));
+
+  // %41 = OpAccessChain %19 %37 *%21* %16 %21
+  // Corresponds to h.*g*.a[1]
+  // The index %24 used for g cannot be replaced
+  auto replacement9 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          21, MakeInstructionDescriptor(41, SpvOpAccessChain, 0), 1),
+      101);
+  ASSERT_FALSE(replacement9.IsApplicable(context.get(), fact_manager));
+
+  // %41 = OpAccessChain %19 %37 %21 %16 *%21*
+  // Corresponds to h.g.a[*1*]
+  // The index %24 used for 1 *can* be replaced
+  auto replacement10 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          21, MakeInstructionDescriptor(41, SpvOpAccessChain, 0), 3),
+      101);
+  ASSERT_TRUE(replacement10.IsApplicable(context.get(), fact_manager));
+  replacement10.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // %44 = OpAccessChain %23 %37 *%21* %21 %43
+  // Corresponds to h.*g*.b[0]
+  // The index %24 used for g cannot be replaced
+  auto replacement11 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          21, MakeInstructionDescriptor(44, SpvOpAccessChain, 0), 1),
+      101);
+  ASSERT_FALSE(replacement11.IsApplicable(context.get(), fact_manager));
+
+  // %44 = OpAccessChain %23 %37 %21 *%21* %43
+  // Corresponds to h.g.*b*[0]
+  // The index %24 used for b cannot be replaced
+  auto replacement12 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          21, MakeInstructionDescriptor(44, SpvOpAccessChain, 0), 2),
+      101);
+  ASSERT_FALSE(replacement12.IsApplicable(context.get(), fact_manager));
+
+  // %46 = OpAccessChain %26 %37 *%21* %17
+  // Corresponds to h.*g*.c
+  // The index %24 used for g cannot be replaced
+  auto replacement13 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          21, MakeInstructionDescriptor(46, SpvOpAccessChain, 0), 1),
+      101);
+  ASSERT_FALSE(replacement13.IsApplicable(context.get(), fact_manager));
+
+  // %53 = OpAccessChain %19 %50 *%21* %21 %16 %16
+  // Corresponds to i[*1*].g.a[0]
+  // The index %24 used for 1 *can* be replaced
+  auto replacement14 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          21, MakeInstructionDescriptor(53, SpvOpAccessChain, 0), 1),
+      101);
+  ASSERT_TRUE(replacement14.IsApplicable(context.get(), fact_manager));
+  replacement14.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // %53 = OpAccessChain %19 %50 %21 *%21* %16 %16
+  // Corresponds to i[1].*g*.a[0]
+  // The index %24 used for g cannot be replaced
+  auto replacement15 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          21, MakeInstructionDescriptor(53, SpvOpAccessChain, 0), 2),
+      101);
+  ASSERT_FALSE(replacement15.IsApplicable(context.get(), fact_manager));
+
+  // %56 = OpAccessChain %23 %50 %17 *%21* %21 %55
+  // Corresponds to i[2].*g*.b[1]
+  // The index %24 used for g cannot be replaced
+  auto replacement16 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          21, MakeInstructionDescriptor(56, SpvOpAccessChain, 0), 2),
+      101);
+  ASSERT_FALSE(replacement16.IsApplicable(context.get(), fact_manager));
+
+  // %56 = OpAccessChain %23 %50 %17 %21 *%21* %55
+  // Corresponds to i[2].g.*b*[1]
+  // The index %24 used for b cannot be replaced
+  auto replacement17 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          21, MakeInstructionDescriptor(56, SpvOpAccessChain, 0), 3),
+      101);
+  ASSERT_FALSE(replacement17.IsApplicable(context.get(), fact_manager));
+
+  // %58 = OpAccessChain %26 %50 %57 *%21* %17
+  // Corresponds to i[3].*g*.c
+  // The index %24 used for g cannot be replaced
+  auto replacement18 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          21, MakeInstructionDescriptor(58, SpvOpAccessChain, 0), 2),
+      101);
+  ASSERT_FALSE(replacement18.IsApplicable(context.get(), fact_manager));
+
+  // Replacements of the form %17 -> %102
+
+  // %20 = OpAccessChain %19 %15 %16 %17
+  // Corresponds to d.a[*2*]
+  // The index %17 used for 2 *can* be replaced
+  auto replacement19 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          17, MakeInstructionDescriptor(20, SpvOpAccessChain, 0), 2),
+      102);
+  ASSERT_TRUE(replacement19.IsApplicable(context.get(), fact_manager));
+  replacement19.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // %27 = OpAccessChain %26 %15 %17
+  // Corresponds to d.c
+  // The index %17 used for c cannot be replaced
+  auto replacement20 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          17, MakeInstructionDescriptor(27, SpvOpAccessChain, 0), 1),
+      102);
+  ASSERT_FALSE(replacement20.IsApplicable(context.get(), fact_manager));
+
+  // %46 = OpAccessChain %26 %37 %21 %17
+  // Corresponds to h.g.*c*
+  // The index %17 used for c cannot be replaced
+  auto replacement21 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          17, MakeInstructionDescriptor(46, SpvOpAccessChain, 0), 2),
+      102);
+  ASSERT_FALSE(replacement21.IsApplicable(context.get(), fact_manager));
+
+  // %56 = OpAccessChain %23 %50 %17 %21 %21 %55
+  // Corresponds to i[*2*].g.b[1]
+  // The index %17 used for 2 *can* be replaced
+  auto replacement22 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          17, MakeInstructionDescriptor(56, SpvOpAccessChain, 0), 1),
+      102);
+  ASSERT_TRUE(replacement22.IsApplicable(context.get(), fact_manager));
+  replacement22.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // %58 = OpAccessChain %26 %50 %57 %21 %17
+  // Corresponds to i[3].g.*c*
+  // The index %17 used for c cannot be replaced
+  auto replacement23 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          17, MakeInstructionDescriptor(58, SpvOpAccessChain, 0), 3),
+      102);
+  ASSERT_FALSE(replacement23.IsApplicable(context.get(), fact_manager));
+
+  // Replacements of the form %57 -> %103
+
+  // %58 = OpAccessChain %26 %50 *%57* %21 %17
+  // Corresponds to i[*3*].g.c
+  // The index %57 used for 3 *can* be replaced
+  auto replacement24 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          57, MakeInstructionDescriptor(58, SpvOpAccessChain, 0), 1),
+      103);
+  ASSERT_TRUE(replacement24.IsApplicable(context.get(), fact_manager));
+  replacement24.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replacements of the form %32 -> %106
+
+  // %34 = OpAccessChain %23 %31 *%32*
+  // Corresponds to e[*17*]
+  // The index %32 used for 17 *can* be replaced
+  auto replacement25 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          32, MakeInstructionDescriptor(34, SpvOpAccessChain, 0), 1),
+      106);
+  ASSERT_TRUE(replacement25.IsApplicable(context.get(), fact_manager));
+  replacement25.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replacements of the form %43 -> %107
+
+  // %44 = OpAccessChain %23 %37 %21 %21 *%43*
+  // Corresponds to h.g.b[*0*]
+  // The index %43 used for 0 *can* be replaced
+  auto replacement26 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          43, MakeInstructionDescriptor(44, SpvOpAccessChain, 0), 3),
+      107);
+  ASSERT_TRUE(replacement26.IsApplicable(context.get(), fact_manager));
+  replacement26.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replacements of the form %55 -> %108
+
+  // %56 = OpAccessChain %23 %50 %17 %21 %21 *%55*
+  // Corresponds to i[2].g.b[*1*]
+  // The index %55 used for 1 *can* be replaced
+  auto replacement27 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(
+          55, MakeInstructionDescriptor(56, SpvOpAccessChain, 0), 4),
+      108);
+  ASSERT_TRUE(replacement27.IsApplicable(context.get(), fact_manager));
+  replacement27.Apply(context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  // Replacements of the form %8 -> %109
+
+  // %24 = OpAccessChain %23 %15 %21 *%8*
+  // Corresponds to d.b[*3*]
+  // The index %8 used for 3 *can* be replaced
+  auto replacement28 = TransformationReplaceIdWithSynonym(
+      MakeIdUseDescriptor(8, MakeInstructionDescriptor(24, SpvOpAccessChain, 0),
+                          2),
+      109);
+  ASSERT_TRUE(replacement28.IsApplicable(context.get(), fact_manager));
+  replacement28.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 %13 "S"
+               OpMemberName %13 0 "a"
+               OpMemberName %13 1 "b"
+               OpMemberName %13 2 "c"
+               OpName %15 "d"
+               OpName %31 "e"
+               OpName %35 "T"
+               OpMemberName %35 0 "f"
+               OpMemberName %35 1 "g"
+               OpName %37 "h"
+               OpName %50 "i"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypeInt 32 0
+          %8 = OpConstant %7 3
+          %9 = OpTypeArray %6 %8
+         %10 = OpTypeFloat 32
+         %11 = OpTypeVector %10 4
+         %12 = OpTypeBool
+         %13 = OpTypeStruct %9 %11 %12
+         %14 = OpTypePointer Private %13
+         %15 = OpVariable %14 Private
+         %16 = OpConstant %6 0
+         %17 = OpConstant %6 2
+         %18 = OpConstant %6 10
+         %19 = OpTypePointer Private %6
+         %21 = OpConstant %6 1
+         %22 = OpConstant %10 11
+         %23 = OpTypePointer Private %10
+         %25 = OpConstantFalse %12
+         %26 = OpTypePointer Private %12
+         %28 = OpConstant %7 20
+         %29 = OpTypeArray %10 %28
+         %30 = OpTypePointer Private %29
+         %31 = OpVariable %30 Private
+         %32 = OpConstant %6 17
+         %33 = OpConstant %10 12
+         %35 = OpTypeStruct %10 %13
+         %36 = OpTypePointer Private %35
+         %37 = OpVariable %36 Private
+         %38 = OpConstant %10 13
+         %40 = OpConstant %6 14
+         %42 = OpConstant %10 15
+         %43 = OpConstant %7 0
+         %45 = OpConstantTrue %12
+         %47 = OpConstant %7 4
+         %48 = OpTypeArray %35 %47
+         %49 = OpTypePointer Private %48
+         %50 = OpVariable %49 Private
+         %51 = OpConstant %10 16
+         %54 = OpConstant %10 18
+         %55 = OpConstant %7 1
+         %57 = OpConstant %6 3
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+
+         %100 = OpCopyObject %6 %16 ; 0
+         %101 = OpCopyObject %6 %21 ; 1
+         %102 = OpCopyObject %6 %17 ; 2
+         %103 = OpCopyObject %6 %57 ; 3
+         %104 = OpCopyObject %6 %18 ; 10
+         %105 = OpCopyObject %6 %40 ; 14
+         %106 = OpCopyObject %6 %32 ; 17
+         %107 = OpCopyObject %7 %43 ; 0
+         %108 = OpCopyObject %7 %55 ; 1
+         %109 = OpCopyObject %7  %8 ; 3
+         %110 = OpCopyObject %7 %47 ; 4
+         %111 = OpCopyObject %7 %28 ; 20
+         %112 = OpCopyObject %12 %45 ; true
+
+         %20 = OpAccessChain %19 %15 %16 %102
+               OpStore %20 %18
+         %24 = OpAccessChain %23 %15 %21 %109
+               OpStore %24 %22
+         %27 = OpAccessChain %26 %15 %17
+               OpStore %27 %25
+         %34 = OpAccessChain %23 %31 %106
+               OpStore %34 %33
+         %39 = OpAccessChain %23 %37 %16
+               OpStore %39 %38
+         %41 = OpAccessChain %19 %37 %21 %16 %101
+               OpStore %41 %40
+         %44 = OpAccessChain %23 %37 %21 %21 %107
+               OpStore %44 %42
+         %46 = OpAccessChain %26 %37 %21 %17
+               OpStore %46 %45
+         %52 = OpAccessChain %23 %50 %100 %16
+               OpStore %52 %51
+         %53 = OpAccessChain %19 %50 %101 %21 %16 %100
+               OpStore %53 %32
+         %56 = OpAccessChain %23 %50 %102 %21 %21 %108
+               OpStore %56 %54
+         %58 = OpAccessChain %26 %50 %103 %21 %17
+               OpStore %58 %45
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+}  // namespace
+}  // namespace fuzz
+}  // namespace spvtools