From 746bfd210adaf43ab16590d7226a95686b42e107 Mon Sep 17 00:00:00 2001
From: Alan Baker <alanbaker@google.com>
Date: Tue, 14 Nov 2017 14:11:50 -0500
Subject: [PATCH] Adding new def -> use mapping container

Replaced representation of uses

* Changed uses from unordered_map<uint32_t, UseList> to
set<pairInstruction*, Instruction*>>
* Replaced GetUses with ForEachUser and ForEachUse functions
* updated passes to use new functions
* partially updated tests
* lots of cleanup still todo

Adding an unique id to Instruction generated by IRContext

Each instruction is given an unique id that can be used for ordering
purposes. The ids are generated via the IRContext.

Major changes:
* Instructions now contain a uint32_t for unique id and a cached context
pointer
 * Most constructors have been modified to take a context as input
 * unfortunately I cannot remove the default and copy constructors, but
 developers should avoid these
* Added accessors to parents of basic block and function
* Removed the copy constructors for BasicBlock and Function and replaced
them with Clone functions
* Reworked BuildModule to return an IRContext owning the built module
 * Since all instructions require a context, the context now becomes the
basic unit for IR
* Added a constructor to context to create an owned module internally
* Replaced uses of Instruction's copy constructor with Clone whereever I
found them
* Reworked the linker functionality to perform clones into a different
context instead of moves
* Updated many tests to be consistent with the above changes
 * Still need to add new tests to cover added functionality
* Added comparison operators to Instruction

Adding tests for Instruction, IRContext and IR loading

Fixed some header comments for BuildModule

Fixes to get tests passing again

* Reordered two linker steps to avoid use/def problems
* Fixed def/use manager uses in merge return pass
* Added early return for GetAnnotations
* Changed uses of Instruction::ToNop in passes to IRContext::KillInst

Simplifying the uses for some contexts in passes
---
 source/link/linker.cpp                             |  17 +-
 source/opt/aggressive_dead_code_elim_pass.cpp      |  23 +-
 source/opt/block_merge_pass.cpp                    |  32 +-
 source/opt/common_uniform_elim_pass.cpp            |  31 +-
 source/opt/dead_branch_elim_pass.cpp               |  17 +-
 source/opt/dead_variable_elimination.cpp           |  15 +-
 source/opt/decoration_manager.cpp                  |   3 +-
 source/opt/def_use_manager.cpp                     | 126 +++--
 source/opt/def_use_manager.h                       | 107 +++-
 source/opt/eliminate_dead_constant_pass.cpp        |  39 +-
 source/opt/inline_pass.cpp                         |   6 +-
 source/opt/instruction.h                           |   2 +-
 source/opt/ir_context.cpp                          |  42 +-
 source/opt/ir_context.h                            |   2 +
 source/opt/local_access_chain_convert_pass.cpp     |  32 +-
 source/opt/local_single_block_elim_pass.cpp        |  32 +-
 source/opt/local_single_store_elim_pass.cpp        |  32 +-
 source/opt/mem_pass.cpp                            |  67 +--
 source/opt/merge_return_pass.cpp                   |  26 +-
 .../opt/set_spec_constant_default_value_pass.cpp   |  10 +-
 source/opt/strength_reduction_pass.cpp             |   6 +-
 test/link/entry_points_test.cpp                    |  36 +-
 test/link/global_values_amount_test.cpp            |   4 -
 test/opt/def_use_test.cpp                          | 577 ++++++++++++++-------
 test/opt/ir_context_test.cpp                       |   1 +
 test/opt/set_spec_const_default_value_test.cpp     |  12 +
 26 files changed, 816 insertions(+), 481 deletions(-)

diff --git a/source/link/linker.cpp b/source/link/linker.cpp
index 4ebe6ee..732ff9a 100644
--- a/source/link/linker.cpp
+++ b/source/link/linker.cpp
@@ -260,18 +260,18 @@ spv_result_t Linker::Link(const uint32_t* const* binaries,
   opt::Pass::Status pass_res = manager.Run(&linked_context);
   if (pass_res == opt::Pass::Status::Failure) return SPV_ERROR_INVALID_DATA;
 
-  // Phase 7: Remove linkage specific instructions, such as import/export
+  // Phase 7: Rematch import variables/functions to export variables/functions
+  for (const auto& linking_entry : linkings_to_do)
+    linked_context.ReplaceAllUsesWith(linking_entry.imported_symbol.id,
+                                      linking_entry.exported_symbol.id);
+
+  // Phase 8: Remove linkage specific instructions, such as import/export
   // attributes, linkage capability, etc. if applicable
   res = RemoveLinkageSpecificInstructions(
       consumer, !options.GetCreateLibrary(), linkings_to_do,
       linked_context.get_decoration_mgr(), &linked_context);
   if (res != SPV_SUCCESS) return res;
 
-  // Phase 8: Rematch import variables/functions to export variables/functions
-  for (const auto& linking_entry : linkings_to_do)
-    linked_context.ReplaceAllUsesWith(linking_entry.imported_symbol.id,
-                                      linking_entry.exported_symbol.id);
-
   // Phase 9: Compact the IDs used in the module
   manager.AddPass<opt::CompactIdsPass>();
   pass_res = manager.Run(&linked_context);
@@ -314,6 +314,9 @@ static spv_result_t ShiftIdsInModules(
                                         SPV_ERROR_INVALID_ID)
              << "The limit of IDs, 4194303, was exceeded:"
              << " " << id_bound << " is the current ID bound.";
+
+    // Invalidate the DefUseManager
+    module->context()->InvalidateAnalyses(ir::IRContext::kAnalysisDefUse);
   }
   ++id_bound;
   if (id_bound > 0x3FFFFF)
@@ -704,7 +707,7 @@ static spv_result_t RemoveLinkageSpecificInstructions(
   // Remove declarations of imported variables
   for (const auto& linking_entry : linkings_to_do) {
     for (auto& inst : linked_context->types_values())
-      if (inst.result_id() == linking_entry.imported_symbol.id) inst.ToNop();
+      if (inst.result_id() == linking_entry.imported_symbol.id) linked_context->KillInst(&inst);
   }
 
   // Remove import linkage attributes
diff --git a/source/opt/aggressive_dead_code_elim_pass.cpp b/source/opt/aggressive_dead_code_elim_pass.cpp
index e46e740..b914702 100644
--- a/source/opt/aggressive_dead_code_elim_pass.cpp
+++ b/source/opt/aggressive_dead_code_elim_pass.cpp
@@ -51,25 +51,22 @@ bool AggressiveDCEPass::IsLocalVar(uint32_t varId) {
 }
 
 void AggressiveDCEPass::AddStores(uint32_t ptrId) {
-  const analysis::UseList* uses = get_def_use_mgr()->GetUses(ptrId);
-  if (uses == nullptr) return;
-  for (const auto u : *uses) {
-    const SpvOp op = u.inst->opcode();
-    switch (op) {
+  get_def_use_mgr()->ForEachUser(ptrId, [this](ir::Instruction* user) {
+    switch (user->opcode()) {
       case SpvOpAccessChain:
       case SpvOpInBoundsAccessChain:
-      case SpvOpCopyObject: {
-        AddStores(u.inst->result_id());
-      } break;
+      case SpvOpCopyObject:
+        this->AddStores(user->result_id());
+        break;
       case SpvOpLoad:
         break;
-      // If default, assume it stores eg frexp, modf, function call
+      // If default, assume it stores e.g. frexp, modf, function call
       case SpvOpStore:
-      default: {
-        if (!IsLive(u.inst)) AddToWorklist(u.inst);
-      } break;
+      default:
+        if (!IsLive(user)) AddToWorklist(user);
+        break;
     }
-  }
+  });
 }
 
 bool AggressiveDCEPass::AllExtensionsSupported() const {
diff --git a/source/opt/block_merge_pass.cpp b/source/opt/block_merge_pass.cpp
index c0da5d7..9a72b14 100644
--- a/source/opt/block_merge_pass.cpp
+++ b/source/opt/block_merge_pass.cpp
@@ -23,27 +23,25 @@ namespace spvtools {
 namespace opt {
 
 bool BlockMergePass::HasMultipleRefs(uint32_t labId) {
-  const analysis::UseList* uses = get_def_use_mgr()->GetUses(labId);
   int rcnt = 0;
-  for (const auto u : *uses) {
-    // Don't count OpName
-    if (u.inst->opcode() == SpvOpName) continue;
-    if (rcnt == 1) return true;
-    ++rcnt;
-  }
-  return false;
+  get_def_use_mgr()->ForEachUser(
+      labId, [&rcnt](ir::Instruction* user) {
+        if (user->opcode() != SpvOpName) {
+          ++rcnt;
+        }
+      });
+  return rcnt > 1;
 }
 
 void BlockMergePass::KillInstAndName(ir::Instruction* inst) {
-  const uint32_t id = inst->result_id();
-  if (id != 0) {
-    analysis::UseList* uses = get_def_use_mgr()->GetUses(id);
-    if (uses != nullptr)
-      for (auto u : *uses)
-        if (u.inst->opcode() == SpvOpName) {
-          context()->KillInst(u.inst);
-          break;
-        }
+  std::vector<ir::Instruction*> to_kill;
+  get_def_use_mgr()->ForEachUser(inst, [&to_kill](ir::Instruction* user) {
+    if (user->opcode() == SpvOpName) {
+      to_kill.push_back(user);
+    }
+  });
+  for (auto i: to_kill) {
+    context()->KillInst(i);
   }
   context()->KillInst(inst);
 }
diff --git a/source/opt/common_uniform_elim_pass.cpp b/source/opt/common_uniform_elim_pass.cpp
index 3339c4a..9b8b1ac 100644
--- a/source/opt/common_uniform_elim_pass.cpp
+++ b/source/opt/common_uniform_elim_pass.cpp
@@ -176,23 +176,26 @@ bool CommonUniformElimPass::IsUniformVar(uint32_t varId) {
 }
 
 bool CommonUniformElimPass::HasUnsupportedDecorates(uint32_t id) const {
-  analysis::UseList* uses = get_def_use_mgr()->GetUses(id);
-  if (uses == nullptr) return false;
-  for (auto u : *uses) {
-    const SpvOp op = u.inst->opcode();
-    if (IsNonTypeDecorate(op)) return true;
-  }
-  return false;
+  bool nonTypeDecorate = false;
+  get_def_use_mgr()->ForEachUser(
+      id, [this, &nonTypeDecorate](ir::Instruction* user) {
+        if (this->IsNonTypeDecorate(user->opcode())) {
+          nonTypeDecorate = true;
+        }
+      });
+  return nonTypeDecorate;
 }
 
 bool CommonUniformElimPass::HasOnlyNamesAndDecorates(uint32_t id) const {
-  analysis::UseList* uses = get_def_use_mgr()->GetUses(id);
-  if (uses == nullptr) return true;
-  for (auto u : *uses) {
-    const SpvOp op = u.inst->opcode();
-    if (op != SpvOpName && !IsNonTypeDecorate(op)) return false;
-  }
-  return true;
+  bool onlyNameAndDecorates = true;
+  get_def_use_mgr()->ForEachUser(
+      id, [this, &onlyNameAndDecorates](ir::Instruction* user) {
+        SpvOp op = user->opcode();
+        if (op != SpvOpName && !this->IsNonTypeDecorate(op)) {
+          onlyNameAndDecorates = false;
+        }
+      });
+  return onlyNameAndDecorates;
 }
 
 void CommonUniformElimPass::DeleteIfUseless(ir::Instruction* inst) {
diff --git a/source/opt/dead_branch_elim_pass.cpp b/source/opt/dead_branch_elim_pass.cpp
index f1c9bf1..b9c6562 100644
--- a/source/opt/dead_branch_elim_pass.cpp
+++ b/source/opt/dead_branch_elim_pass.cpp
@@ -124,14 +124,15 @@ bool DeadBranchElimPass::GetSelectionBranch(ir::BasicBlock* bp,
 }
 
 bool DeadBranchElimPass::HasNonPhiNonBackedgeRef(uint32_t labelId) {
-  analysis::UseList* uses = get_def_use_mgr()->GetUses(labelId);
-  if (uses == nullptr) return false;
-  for (auto u : *uses) {
-    if (u.inst->opcode() != SpvOpPhi &&
-        backedges_.find(u.inst) == backedges_.end())
-      return true;
-  }
-  return false;
+  bool nonPhiNonBackedgeRef = false;
+  get_def_use_mgr()->ForEachUser(
+      labelId, [this, &nonPhiNonBackedgeRef](ir::Instruction* user) {
+        if (user->opcode() != SpvOpPhi &&
+            backedges_.find(user) == backedges_.end()) {
+          nonPhiNonBackedgeRef = true;
+        }
+      });
+  return nonPhiNonBackedgeRef;
 }
 
 void DeadBranchElimPass::ComputeBackEdges(
diff --git a/source/opt/dead_variable_elimination.cpp b/source/opt/dead_variable_elimination.cpp
index 723dfa4..01ff04f 100644
--- a/source/opt/dead_variable_elimination.cpp
+++ b/source/opt/dead_variable_elimination.cpp
@@ -56,13 +56,14 @@ Pass::Status DeadVariableElimination::Process(ir::IRContext* c) {
     if (count != kMustKeep) {
       // If we don't have to keep the instruction for other reasons, then look
       // at the uses and count the number of real references.
-      if (analysis::UseList* uses = get_def_use_mgr()->GetUses(result_id)) {
-        count = std::count_if(
-            uses->begin(), uses->end(), [](const analysis::Use& u) {
-              return (!ir::IsAnnotationInst(u.inst->opcode()) &&
-                      u.inst->opcode() != SpvOpName);
-            });
-      }
+      count = 0;
+      get_def_use_mgr()->ForEachUser(
+          result_id, [&count](ir::Instruction* user) {
+            if (!ir::IsAnnotationInst(user->opcode()) &&
+                user->opcode() != SpvOpName) {
+              ++count;
+            }
+          });
     }
     reference_count_[result_id] = count;
     if (count == 0) {
diff --git a/source/opt/decoration_manager.cpp b/source/opt/decoration_manager.cpp
index b25c20f..42c4e77 100644
--- a/source/opt/decoration_manager.cpp
+++ b/source/opt/decoration_manager.cpp
@@ -264,8 +264,9 @@ void DecorationManager::CloneDecorations(
         std::unique_ptr<ir::Instruction> new_inst(inst->Clone(module_->context()));
         new_inst->SetInOperand(0, {to});
         id_to_decoration_insts_[to].push_back(new_inst.get());
-        f(*new_inst, true);
         module_->AddAnnotationInst(std::move(new_inst));
+        auto decoration_iter = --module_->annotation_end();
+        f(*decoration_iter, true);
         break;
       }
       default:
diff --git a/source/opt/def_use_manager.cpp b/source/opt/def_use_manager.cpp
index 3be6980..94935f0 100644
--- a/source/opt/def_use_manager.cpp
+++ b/source/opt/def_use_manager.cpp
@@ -50,7 +50,9 @@ void DefUseManager::AnalyzeInstUse(ir::Instruction* inst) {
       case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
       case SPV_OPERAND_TYPE_SCOPE_ID: {
         uint32_t use_id = inst->GetSingleWordOperand(i);
-        id_to_uses_[use_id].push_back({inst, i});
+        ir::Instruction* def = GetDef(use_id);
+        assert(def && "Definition is not registered.");
+        id_to_users_.insert(UserEntry(def, inst));
         inst_to_used_ids_[inst].push_back(use_id);
       } break;
       default:
@@ -76,33 +78,79 @@ const ir::Instruction* DefUseManager::GetDef(uint32_t id) const {
   return iter->second;
 }
 
-UseList* DefUseManager::GetUses(uint32_t id) {
-  auto iter = id_to_uses_.find(id);
-  if (iter == id_to_uses_.end()) return nullptr;
-  return &iter->second;
+DefUseManager::IdToUsersMap::const_iterator DefUseManager::UsersBegin(
+    const ir::Instruction* def) const {
+  return id_to_users_.lower_bound(
+      UserEntry(const_cast<ir::Instruction*>(def), nullptr));
 }
 
-const UseList* DefUseManager::GetUses(uint32_t id) const {
-  const auto iter = id_to_uses_.find(id);
-  if (iter == id_to_uses_.end()) return nullptr;
-  return &iter->second;
+bool DefUseManager::UsersNotEnd(const IdToUsersMap::const_iterator& iter,
+                                const IdToUsersMap::const_iterator& cached_end,
+                                const ir::Instruction* inst) const {
+  return (iter != cached_end && iter->first == inst);
+}
+
+bool DefUseManager::UsersNotEnd(const IdToUsersMap::const_iterator& iter,
+                                const ir::Instruction* inst) const {
+  return UsersNotEnd(iter, id_to_users_.end(), inst);
+}
+
+void DefUseManager::ForEachUser(const ir::Instruction* def,
+                                const std::function<void(ir::Instruction*)>& f) const {
+  // Ensure that |def| has been registered.
+  assert(def && def == GetDef(def->result_id()) && "Definition is not registered.");
+  auto end = id_to_users_.end();
+  for (auto iter = UsersBegin(def); UsersNotEnd(iter, end, def); ++iter) {
+    f(iter->second);
+  }
+}
+
+void DefUseManager::ForEachUser(uint32_t id,
+                                const std::function<void(ir::Instruction*)>& f) const {
+  ForEachUser(GetDef(id), f);
+}
+
+void DefUseManager::ForEachUse(const ir::Instruction* def,
+                               const std::function<void(ir::Instruction*, uint32_t)>& f) const {
+  // Ensure that |def| has been registered.
+  assert(def && def == GetDef(def->result_id()) && "Definition is not registered.");
+  auto end = id_to_users_.end();
+  for (auto iter = UsersBegin(def); UsersNotEnd(iter, end, def); ++iter) {
+    ir::Instruction* user = iter->second;
+    for (uint32_t idx = 0; idx != user->NumOperands(); ++idx) {
+      const ir::Operand& op = user->GetOperand(idx);
+      if (op.type != SPV_OPERAND_TYPE_RESULT_ID && spvIsIdType(op.type)) {
+        if (def->result_id() == op.words[0])
+          f(user, idx);
+      }
+    }
+  }
+}
+
+void DefUseManager::ForEachUse(uint32_t id,
+                               const std::function<void(ir::Instruction*, uint32_t)>& f) const {
+  ForEachUse(GetDef(id), f);
 }
 
 std::vector<ir::Instruction*> DefUseManager::GetAnnotations(uint32_t id) const {
   std::vector<ir::Instruction*> annos;
-  const auto* uses = GetUses(id);
-  if (!uses) return annos;
-  for (const auto& c : *uses) {
-    if (ir::IsAnnotationInst(c.inst->opcode())) {
-      annos.push_back(c.inst);
+  const ir::Instruction* def = GetDef(id);
+  if (!def) return annos;
+
+  ForEachUser(def, [&annos](ir::Instruction* user) {
+    if (ir::IsAnnotationInst(user->opcode())) {
+      annos.push_back(user);
     }
-  }
+  });
   return annos;
 }
 
 void DefUseManager::AnalyzeDefUse(ir::Module* module) {
   if (!module) return;
-  module->ForEachInst(std::bind(&DefUseManager::AnalyzeInstDefUse, this,
+  // Analyze all the defs before any uses to catch forward references.
+  module->ForEachInst(std::bind(&DefUseManager::AnalyzeInstDef, this,
+                                std::placeholders::_1));
+  module->ForEachInst(std::bind(&DefUseManager::AnalyzeInstUse, this,
                                 std::placeholders::_1));
 }
 
@@ -111,7 +159,12 @@ void DefUseManager::ClearInst(ir::Instruction* inst) {
   if (iter != inst_to_used_ids_.end()) {
     EraseUseRecordsOfOperandIds(inst);
     if (inst->result_id() != 0) {
-      id_to_uses_.erase(inst->result_id());  // Remove all uses of this id.
+      // Remove all uses of this inst.
+      auto users_begin = UsersBegin(inst);
+      auto end = id_to_users_.end();
+      auto new_end = users_begin;
+      for (; UsersNotEnd(new_end, end, inst); ++new_end) {}
+      id_to_users_.erase(users_begin, new_end);
       id_to_def_.erase(inst->result_id());
     }
   }
@@ -120,32 +173,10 @@ void DefUseManager::ClearInst(ir::Instruction* inst) {
 void DefUseManager::EraseUseRecordsOfOperandIds(const ir::Instruction* inst) {
   // Go through all ids used by this instruction, remove this instruction's
   // uses of them.
-  //
-  // We cache end iterators to avoid the cost of repeatedly constructing
-  // and destructing their value.  This cuts runtime on some examples by
-  // a factor of about 3 (e.g. on Windows debug builds, with many thousands
-  // of instructions).
   auto iter = inst_to_used_ids_.find(inst);
   if (iter != inst_to_used_ids_.end()) {
-    // Cache the end iterator on the map.  The end iterator on
-    // an unordered map does not get invalidated when erasing an
-    // element.
-    const auto& id_to_uses_end = id_to_uses_.end();
-    for (const auto use_id : iter->second) {
-      auto uses_iter = id_to_uses_.find(use_id);
-      if (uses_iter == id_to_uses_end) continue;
-      auto& uses = uses_iter->second;
-      // Similarly, cache this end iterator.  It is not invalidated
-      // by erasure of an element from the list.
-      const auto& uses_end = uses.end();
-      for (auto it = uses.begin(); it != uses_end;) {
-        if (it->inst == inst) {
-          it = uses.erase(it);
-        } else {
-          ++it;
-        }
-      }
-      if (uses.empty()) id_to_uses_.erase(use_id);
+    for (auto use_id : iter->second) {
+      id_to_users_.erase(UserEntry(GetDef(use_id), const_cast<ir::Instruction*>(inst)));
     }
     inst_to_used_ids_.erase(inst);
   }
@@ -156,17 +187,8 @@ bool operator==(const DefUseManager& lhs, const DefUseManager& rhs) {
     return false;
   }
 
-  for (auto use : lhs.id_to_uses_) {
-    auto rhs_iter = rhs.id_to_uses_.find(use.first);
-    if (rhs_iter == rhs.id_to_uses_.end()) {
-      return false;
-    }
-    use.second.sort();
-    UseList rhs_uselist = rhs_iter->second;
-    rhs_uselist.sort();
-    if (use.second != rhs_uselist) {
-      return false;
-    }
+  if (lhs.id_to_users_ != rhs.id_to_users_) {
+    return false;
   }
 
   if (lhs.inst_to_used_ids_ != lhs.inst_to_used_ids_) {
diff --git a/source/opt/def_use_manager.h b/source/opt/def_use_manager.h
index 74d4528..1f67305 100644
--- a/source/opt/def_use_manager.h
+++ b/source/opt/def_use_manager.h
@@ -16,6 +16,7 @@
 #define LIBSPIRV_OPT_DEF_USE_MANAGER_H_
 
 #include <list>
+#include <set>
 #include <unordered_map>
 #include <vector>
 
@@ -53,13 +54,60 @@ inline bool operator<(const Use& lhs, const Use& rhs) {
   return lhs.operand_index < rhs.operand_index;
 }
 
-using UseList = std::list<Use>;
+// Definition and user pair.
+//
+// The first element of the pair is the definition.
+// The second element of the pair is the user.
+//
+// Definition should never be null. User can be null, however, such an entry
+// should be used only for searching (e.g. all users of a particular definition)
+// and never stored in a container.
+using UserEntry = std::pair<ir::Instruction*, ir::Instruction*>;
+
+// Orders UserEntry for use in associative containers (i.e. less than ordering).
+//
+// The definition of an UserEntry is treated as the major key and the users as
+// the minor key so that all the users of a particular definition are
+// consecutive in a container.
+//
+// A null user always compares less than a real user. This is done to provide
+// easy values to search for the beginning of the users of a particular
+// definition (i.e. using {def, nullptr}).
+struct UserEntryLess {
+  bool operator()(const UserEntry& lhs, const UserEntry& rhs) const {
+    // If lhs.first and rhs.first are both null, fall through to checking the
+    // second entries.
+    if (!lhs.first && rhs.first)
+      return true;
+    if (lhs.first && !rhs.first)
+      return false;
+
+    // If neither defintion is null, then compare unique ids.
+    if (lhs.first && rhs.first) {
+      if (lhs.first->unique_id() < rhs.first->unique_id())
+        return true;
+      if (rhs.first->unique_id() < lhs.first->unique_id())
+        return false;
+    }
+
+    // Return false on equality.
+    if (!lhs.second && !rhs.second)
+      return false;
+    if (!lhs.second)
+      return true;
+    if (!rhs.second)
+      return false;
+
+    // If neither user is null then compare unique ids.
+    return lhs.second->unique_id() < rhs.second->unique_id();
+  }
+};
 
 // A class for analyzing and managing defs and uses in an ir::Module.
 class DefUseManager {
  public:
   using IdToDefMap = std::unordered_map<uint32_t, ir::Instruction*>;
-  using IdToUsesMap = std::unordered_map<uint32_t, UseList>;
+  using IdToUsersMap = std::set<UserEntry, UserEntryLess>;
 
   // Constructs a def-use manager from the given |module|. All internal messages
   // will be communicated to the outside via the given message |consumer|. This
@@ -76,6 +124,8 @@ class DefUseManager {
   void AnalyzeInstDef(ir::Instruction* inst);
 
   // Analyzes the uses in the given |inst|.
+  //
+  // All operands of |inst| must be analyzed as defs.
   void AnalyzeInstUse(ir::Instruction* inst);
 
   // Analyzes the defs and uses in the given |inst|.
@@ -85,10 +135,33 @@ class DefUseManager {
   // defining |id|, returns nullptr.
   ir::Instruction* GetDef(uint32_t id);
   const ir::Instruction* GetDef(uint32_t id) const;
-  // Returns the use instructions for the given |id|. If there is no uses of
-  // |id|, returns nullptr.
-  UseList* GetUses(uint32_t id);
-  const UseList* GetUses(uint32_t id) const;
+
+  // Runs the given function |f| on each unique user instruction of |def| (or
+  // |id|).
+  //
+  // If one instruction uses |def| in multiple operands, that instruction will
+  // only be visited once.
+  //
+  // |def| (or |id|) must be registered as a definition.
+  void ForEachUser(const ir::Instruction* def,
+                   const std::function<void(ir::Instruction*)>& f) const;
+  void ForEachUser(uint32_t id,
+                   const std::function<void(ir::Instruction*)>& f) const;
+
+  // Runs the given function |f| on each unique use of |def| (or
+  // |id|).
+  //
+  // If one instruction uses |def| in multiple operands, each operand will be
+  // visited separately.
+  //
+  // |def| (or |id|) must be registered as a definition.
+  void ForEachUse(
+      const ir::Instruction* def,
+      const std::function<void(ir::Instruction*, uint32_t operand_index)>& f) const;
+  void ForEachUse(
+      uint32_t id,
+      const std::function<void(ir::Instruction*, uint32_t operand_index)>& f) const;
+
   // Returns the annotation instrunctions which are a direct use of the given
   // |id|. This means when the decorations are applied through decoration
   // group(s), this function will just return the OpGroupDecorate
@@ -98,8 +171,8 @@ class DefUseManager {
 
   // Returns the map from ids to their def instructions.
   const IdToDefMap& id_to_defs() const { return id_to_def_; }
-  // Returns the map from ids to their uses in instructions.
-  const IdToUsesMap& id_to_uses() const { return id_to_uses_; }
+  // Returns the map from instructions to their users.
+  const IdToUsersMap& id_to_users() const { return id_to_users_; }
 
   // Clear the internal def-use record of the given instruction |inst|. This
   // method will update the use information of the operand ids of |inst|. The
@@ -120,12 +193,28 @@ class DefUseManager {
   using InstToUsedIdsMap =
       std::unordered_map<const ir::Instruction*, std::vector<uint32_t>>;
 
+  // Returns the first location that {|def|, nullptr} could be inserted into the
+  // users map without violating ordering.
+  IdToUsersMap::const_iterator UsersBegin(const ir::Instruction* def) const;
+
+  // Returns true if |iter| has not reached the end of |def|'s users.
+  //
+  // In the first version |iter| is compared against the end of the map for
+  // validity before other checks. In the second version, |iter| is compared
+  // against |cached_end| for validity before other checks. This allows caching
+  // the map's end which is a performance improvement on some platforms.
+  bool UsersNotEnd(const IdToUsersMap::const_iterator& iter,
+                   const ir::Instruction* def) const;
+  bool UsersNotEnd(const IdToUsersMap::const_iterator& iter,
+                   const IdToUsersMap::const_iterator& cached_end,
+                   const ir::Instruction* def) const;
+
   // Analyzes the defs and uses in the given |module| and populates data
   // structures in this class. Does nothing if |module| is nullptr.
   void AnalyzeDefUse(ir::Module* module);
 
   IdToDefMap id_to_def_;    // Mapping from ids to their definitions
-  IdToUsesMap id_to_uses_;  // Mapping from ids to their uses
+  IdToUsersMap id_to_users_; // Mapping from ids to their users
   // Mapping from instructions to the ids used in the instruction.
   InstToUsedIdsMap inst_to_used_ids_;
 
diff --git a/source/opt/eliminate_dead_constant_pass.cpp b/source/opt/eliminate_dead_constant_pass.cpp
index 32fc5da..3c4e7f9 100644
--- a/source/opt/eliminate_dead_constant_pass.cpp
+++ b/source/opt/eliminate_dead_constant_pass.cpp
@@ -36,16 +36,15 @@ Pass::Status EliminateDeadConstantPass::Process(ir::IRContext* irContext) {
   for (auto* c : constants) {
     uint32_t const_id = c->result_id();
     size_t count = 0;
-    if (analysis::UseList* uses =
-            irContext->get_def_use_mgr()->GetUses(const_id)) {
-      count =
-          std::count_if(uses->begin(), uses->end(), [](const analysis::Use& u) {
-            return !(ir::IsAnnotationInst(u.inst->opcode()) ||
-                     ir::IsDebug1Inst(u.inst->opcode()) ||
-                     ir::IsDebug2Inst(u.inst->opcode()) ||
-                     ir::IsDebug3Inst(u.inst->opcode()));
-          });
-    }
+    irContext->get_def_use_mgr()->ForEachUse(
+        const_id, [&count](ir::Instruction* user, uint32_t index) {
+          (void)index;
+          SpvOp op = user->opcode();
+          if (!(ir::IsAnnotationInst(op) || ir::IsDebug1Inst(op) ||
+                ir::IsDebug2Inst(op) || ir::IsDebug3Inst(op))) {
+            ++count;
+          }
+        });
     use_counts[c] = count;
     if (!count) {
       working_list.insert(c);
@@ -96,17 +95,15 @@ Pass::Status EliminateDeadConstantPass::Process(ir::IRContext* irContext) {
   // constants.
   std::unordered_set<ir::Instruction*> dead_others;
   for (auto* dc : dead_consts) {
-    if (analysis::UseList* uses =
-            irContext->get_def_use_mgr()->GetUses(dc->result_id())) {
-      for (const auto& u : *uses) {
-        if (ir::IsAnnotationInst(u.inst->opcode()) ||
-            ir::IsDebug1Inst(u.inst->opcode()) ||
-            ir::IsDebug2Inst(u.inst->opcode()) ||
-            ir::IsDebug3Inst(u.inst->opcode())) {
-          dead_others.insert(u.inst);
-        }
+    irContext->get_def_use_mgr()->ForEachUser(dc, [&dead_others](ir::Instruction* user) {
+      SpvOp op = user->opcode();
+      if (ir::IsAnnotationInst(op) ||
+          ir::IsDebug1Inst(op) ||
+          ir::IsDebug2Inst(op) ||
+          ir::IsDebug3Inst(op)) {
+        dead_others.insert(user);
       }
-    }
+    });
   }
 
   // Turn all dead instructions and uses of them to nop
@@ -114,7 +111,7 @@ Pass::Status EliminateDeadConstantPass::Process(ir::IRContext* irContext) {
     irContext->KillDef(dc->result_id());
   }
   for (auto* da : dead_others) {
-    da->ToNop();
+    irContext->KillInst(da);
   }
   return dead_consts.empty() ? Status::SuccessWithoutChange
                              : Status::SuccessWithChange;
diff --git a/source/opt/inline_pass.cpp b/source/opt/inline_pass.cpp
index 5c6e3fb..f813f99 100644
--- a/source/opt/inline_pass.cpp
+++ b/source/opt/inline_pass.cpp
@@ -648,10 +648,8 @@ bool InlinePass::IsInlinableFunction(ir::Function* func) {
 void InlinePass::InitializeInline(ir::IRContext* c) {
   InitializeProcessing(c);
 
-  update_def_use_mgr_ = [this] (ir::Instruction& inst, bool has_changed) {
-    if (has_changed)
-      get_def_use_mgr()->AnalyzeInstDefUse(&inst);
-  };
+  // Don't bother updating the DefUseManger
+  update_def_use_mgr_ = [this] (ir::Instruction&, bool) {};
 
   false_id_ = 0;
 
diff --git a/source/opt/instruction.h b/source/opt/instruction.h
index a046e8d..962b66b 100644
--- a/source/opt/instruction.h
+++ b/source/opt/instruction.h
@@ -126,7 +126,7 @@ class Instruction : public utils::IntrusiveNodeBase<Instruction> {
   // It is the responsibility of the caller to make sure that the storage is
   // removed. It is the caller's responsibility to make sure that there is only
   // one instruction for each result id.
-  Instruction* Clone(IRContext* c) const;
+  Instruction* Clone(IRContext *c) const;
 
   IRContext* context() const { return context_; }
 
diff --git a/source/opt/ir_context.cpp b/source/opt/ir_context.cpp
index 30840a3..8a26814 100644
--- a/source/opt/ir_context.cpp
+++ b/source/opt/ir_context.cpp
@@ -91,25 +91,32 @@ bool IRContext::KillDef(uint32_t id) {
 
 bool IRContext::ReplaceAllUsesWith(uint32_t before, uint32_t after) {
   if (before == after) return false;
-  opt::analysis::UseList* uses = get_def_use_mgr()->GetUses(before);
-  if (uses == nullptr) return false;
 
-  std::vector<opt::analysis::Use> uses_to_update;
-  for (auto it = uses->cbegin(); it != uses->cend(); ++it) {
-    uses_to_update.push_back(*it);
-  }
+  // Ensure that |after| has been registered as def.
+  assert(get_def_use_mgr()->GetDef(after) && "'after' is not a registered def.");
+
+  std::vector<std::pair<ir::Instruction*,uint32_t>> uses_to_update;
+  get_def_use_mgr()->ForEachUse(before, [&uses_to_update](ir::Instruction* user, uint32_t index) {
+    uses_to_update.emplace_back(user, index);
+  });
 
-  for (opt::analysis::Use& use : uses_to_update) {
-    ForgetUses(use.inst);
+  ir::Instruction* prev = nullptr;
+  for (auto p : uses_to_update) {
+    ir::Instruction* user = p.first;
+    uint32_t index = p.second;
+    if (prev == nullptr || prev != user) {
+      ForgetUses(user);
+      prev = user;
+    }
     const uint32_t type_result_id_count =
-        (use.inst->result_id() != 0) + (use.inst->type_id() != 0);
+        (user->result_id() != 0) + (user->type_id() != 0);
 
-    if (use.operand_index < type_result_id_count) {
+    if (index < type_result_id_count) {
       // Update the type_id. Note that result id is immutable so it should
       // never be updated.
-      if (use.inst->type_id() != 0 && use.operand_index == 0) {
-        use.inst->SetResultType(after);
-      } else if (use.inst->type_id() == 0) {
+      if (user->type_id() != 0 && index == 0) {
+        user->SetResultType(after);
+      } else if (user->type_id() == 0) {
         SPIRV_ASSERT(consumer_, false,
                      "Result type id considered as use while the instruction "
                      "doesn't have a result type id.");
@@ -120,12 +127,13 @@ bool IRContext::ReplaceAllUsesWith(uint32_t before, uint32_t after) {
       }
     } else {
       // Update an in-operand.
-      uint32_t in_operand_pos = use.operand_index - type_result_id_count;
+      uint32_t in_operand_pos = index - type_result_id_count;
       // Make the modification in the instruction.
-      use.inst->SetInOperand(in_operand_pos, {after});
+      user->SetInOperand(in_operand_pos, {after});
     }
-    AnalyzeUses(use.inst);
-  }
+    AnalyzeUses(user);
+  };
+
   return true;
 }
 
diff --git a/source/opt/ir_context.h b/source/opt/ir_context.h
index 3ef1a95..468dbc5 100644
--- a/source/opt/ir_context.h
+++ b/source/opt/ir_context.h
@@ -235,6 +235,8 @@ class IRContext {
   // replacement happens. This method does not kill the definition of the
   // |before| id. If |after| is the same as |before|, does nothing and returns
   // false.
+  //
+  // |before| and |after| must be registered definitions in the DefUseManager.
   bool ReplaceAllUsesWith(uint32_t before, uint32_t after);
 
   // Returns true if all of the analyses that are suppose to be valid are
diff --git a/source/opt/local_access_chain_convert_pass.cpp b/source/opt/local_access_chain_convert_pass.cpp
index 14bec99..db7bf95 100644
--- a/source/opt/local_access_chain_convert_pass.cpp
+++ b/source/opt/local_access_chain_convert_pass.cpp
@@ -138,28 +138,22 @@ bool LocalAccessChainConvertPass::IsConstantIndexAccessChain(
 
 bool LocalAccessChainConvertPass::HasOnlySupportedRefs(uint32_t ptrId) {
   if (supported_ref_ptrs_.find(ptrId) != supported_ref_ptrs_.end()) return true;
-  analysis::UseList* uses = get_def_use_mgr()->GetUses(ptrId);
-
-  if (!uses) {
-    // This is a variable (or access chain to a variable) that has no uses.
-    // We won't encounter loads or stores for this <result-id> per se, but
-    // this <result-id> may be derived from some other variable (or access
-    // chain). Return true here can unblock the access chain conversion of
-    // the root variable. This particular <result-id> won't be touched and
-    // can be handled in dead code elimination.
-    return true;
-  }
-
-  for (auto u : *uses) {
-    SpvOp op = u.inst->opcode();
+  bool hasOnlySupportedRefs = true;
+  get_def_use_mgr()->ForEachUser(ptrId, [this,&hasOnlySupportedRefs](ir::Instruction* user) {
+    SpvOp op = user->opcode();
     if (IsNonPtrAccessChain(op) || op == SpvOpCopyObject) {
-      if (!HasOnlySupportedRefs(u.inst->result_id())) return false;
+      if (!HasOnlySupportedRefs(user->result_id())) {
+        hasOnlySupportedRefs = false;
+      }
     } else if (op != SpvOpStore && op != SpvOpLoad && op != SpvOpName &&
-               !IsNonTypeDecorate(op))
-      return false;
+               !IsNonTypeDecorate(op)) {
+      hasOnlySupportedRefs = false;
+    }
+  });
+  if (hasOnlySupportedRefs) {
+    supported_ref_ptrs_.insert(ptrId);
   }
-  supported_ref_ptrs_.insert(ptrId);
-  return true;
+  return hasOnlySupportedRefs;
 }
 
 void LocalAccessChainConvertPass::FindTargetVars(ir::Function* func) {
diff --git a/source/opt/local_single_block_elim_pass.cpp b/source/opt/local_single_block_elim_pass.cpp
index 4f208af..95e9179 100644
--- a/source/opt/local_single_block_elim_pass.cpp
+++ b/source/opt/local_single_block_elim_pass.cpp
@@ -29,28 +29,22 @@ const uint32_t kStoreValIdInIdx = 1;
 
 bool LocalSingleBlockLoadStoreElimPass::HasOnlySupportedRefs(uint32_t ptrId) {
   if (supported_ref_ptrs_.find(ptrId) != supported_ref_ptrs_.end()) return true;
-  analysis::UseList* uses = get_def_use_mgr()->GetUses(ptrId);
-
-  if (!uses) {
-    // This is a variable (or access chain to a variable) that has no uses.
-    // We won't encounter loads or stores for this <result-id> per se, but
-    // this <result-id> may be derived from some other variable (or access
-    // chain). Return true here can unblock the access chain conversion of
-    // the root variable. This particular <result-id> won't be touched and
-    // can be handled in dead code elimination.
-    return true;
-  }
-
-  for (auto u : *uses) {
-    SpvOp op = u.inst->opcode();
+  bool hasOnlySupportedRefs = true;
+  get_def_use_mgr()->ForEachUser(ptrId, [this,&hasOnlySupportedRefs](ir::Instruction* user) {
+    SpvOp op = user->opcode();
     if (IsNonPtrAccessChain(op) || op == SpvOpCopyObject) {
-      if (!HasOnlySupportedRefs(u.inst->result_id())) return false;
+      if (!HasOnlySupportedRefs(user->result_id())) {
+        hasOnlySupportedRefs = false;
+      }
     } else if (op != SpvOpStore && op != SpvOpLoad && op != SpvOpName &&
-               !IsNonTypeDecorate(op))
-      return false;
+               !this->IsNonTypeDecorate(op)) {
+      hasOnlySupportedRefs = false;
+    }
+  });
+  if (hasOnlySupportedRefs) {
+    supported_ref_ptrs_.insert(ptrId);
   }
-  supported_ref_ptrs_.insert(ptrId);
-  return true;
+  return hasOnlySupportedRefs;
 }
 
 bool LocalSingleBlockLoadStoreElimPass::LocalSingleBlockLoadStoreElim(
diff --git a/source/opt/local_single_store_elim_pass.cpp b/source/opt/local_single_store_elim_pass.cpp
index 5eda1d2..b613f8a 100644
--- a/source/opt/local_single_store_elim_pass.cpp
+++ b/source/opt/local_single_store_elim_pass.cpp
@@ -31,28 +31,22 @@ const uint32_t kStoreValIdInIdx = 1;
 
 bool LocalSingleStoreElimPass::HasOnlySupportedRefs(uint32_t ptrId) {
   if (supported_ref_ptrs_.find(ptrId) != supported_ref_ptrs_.end()) return true;
-  analysis::UseList* uses = get_def_use_mgr()->GetUses(ptrId);
-
-  if (!uses) {
-    // This is a variable (or access chain to a variable) that has no uses.
-    // We won't encounter loads or stores for this <result-id> per se, but
-    // this <result-id> may be derived from some other variable (or access
-    // chain). Return true here can unblock the access chain conversion of
-    // the root variable. This particular <result-id> won't be touched and
-    // can be handled in dead code elimination.
-    return true;
-  }
-
-  for (auto u : *uses) {
-    SpvOp op = u.inst->opcode();
+  bool hasOnlySupportedRefs = true;
+  get_def_use_mgr()->ForEachUser(ptrId, [this,&hasOnlySupportedRefs](ir::Instruction* user) {
+    SpvOp op = user->opcode();
     if (IsNonPtrAccessChain(op) || op == SpvOpCopyObject) {
-      if (!HasOnlySupportedRefs(u.inst->result_id())) return false;
+      if (!HasOnlySupportedRefs(user->result_id())) {
+        hasOnlySupportedRefs = false;
+      }
     } else if (op != SpvOpStore && op != SpvOpLoad && op != SpvOpName &&
-               !IsNonTypeDecorate(op))
-      return false;
+               !IsNonTypeDecorate(op)) {
+      hasOnlySupportedRefs = false;
+    }
+  });
+  if (hasOnlySupportedRefs) {
+    supported_ref_ptrs_.insert(ptrId);
   }
-  supported_ref_ptrs_.insert(ptrId);
-  return true;
+  return hasOnlySupportedRefs;
 }
 
 void LocalSingleStoreElimPass::SingleStoreAnalyze(ir::Function* func) {
diff --git a/source/opt/mem_pass.cpp b/source/opt/mem_pass.cpp
index 1292804..848cbb5 100644
--- a/source/opt/mem_pass.cpp
+++ b/source/opt/mem_pass.cpp
@@ -118,13 +118,14 @@ ir::Instruction* MemPass::GetPtr(ir::Instruction* ip, uint32_t* varId) {
 }
 
 bool MemPass::HasOnlyNamesAndDecorates(uint32_t id) const {
-  analysis::UseList* uses = get_def_use_mgr()->GetUses(id);
-  if (uses == nullptr) return true;
-  for (auto u : *uses) {
-    const SpvOp op = u.inst->opcode();
-    if (op != SpvOpName && !IsNonTypeDecorate(op)) return false;
-  }
-  return true;
+  bool hasOnlyNamesAndDecorates = true;
+  get_def_use_mgr()->ForEachUser(id, [this, &hasOnlyNamesAndDecorates](ir::Instruction* user) {
+    SpvOp op = user->opcode();
+    if (op != SpvOpName && !IsNonTypeDecorate(op)) {
+      hasOnlyNamesAndDecorates = false;
+    }
+  });
+  return hasOnlyNamesAndDecorates;
 }
 
 void MemPass::KillAllInsts(ir::BasicBlock* bp) {
@@ -134,18 +135,20 @@ void MemPass::KillAllInsts(ir::BasicBlock* bp) {
 }
 
 bool MemPass::HasLoads(uint32_t varId) const {
-  analysis::UseList* uses = get_def_use_mgr()->GetUses(varId);
-  if (uses == nullptr) return false;
-  for (auto u : *uses) {
-    SpvOp op = u.inst->opcode();
+  bool hasLoads = false;
+  get_def_use_mgr()->ForEachUser(varId, [this, &hasLoads](ir::Instruction* user) {
+    SpvOp op = user->opcode();
     // TODO(): The following is slightly conservative. Could be
     // better handling of non-store/name.
     if (IsNonPtrAccessChain(op) || op == SpvOpCopyObject) {
-      if (HasLoads(u.inst->result_id())) return true;
-    } else if (op != SpvOpStore && op != SpvOpName && !IsNonTypeDecorate(op))
-      return true;
-  }
-  return false;
+      if (HasLoads(user->result_id())) {
+        hasLoads = true;
+      }
+    } else if (op != SpvOpStore && op != SpvOpName && !IsNonTypeDecorate(op)) {
+      hasLoads = true;
+    }
+  });
+  return hasLoads;
 }
 
 bool MemPass::IsLiveVar(uint32_t varId) const {
@@ -170,15 +173,14 @@ bool MemPass::IsLiveStore(ir::Instruction* storeInst) {
 }
 
 void MemPass::AddStores(uint32_t ptr_id, std::queue<ir::Instruction*>* insts) {
-  analysis::UseList* uses = get_def_use_mgr()->GetUses(ptr_id);
-  if (uses != nullptr) {
-    for (auto u : *uses) {
-      if (IsNonPtrAccessChain(u.inst->opcode()))
-        AddStores(u.inst->result_id(), insts);
-      else if (u.inst->opcode() == SpvOpStore)
-        insts->push(u.inst);
+  get_def_use_mgr()->ForEachUser(ptr_id, [this,insts](ir::Instruction* user) {
+    SpvOp op = user->opcode();
+    if (IsNonPtrAccessChain(op)) {
+      AddStores(user->result_id(), insts);
+    } else if (op == SpvOpStore) {
+      insts->push(user);
     }
-  }
+  });
 }
 
 void MemPass::DCEInst(ir::Instruction* inst) {
@@ -221,16 +223,15 @@ MemPass::MemPass() {}
 
 bool MemPass::HasOnlySupportedRefs(uint32_t varId) {
   if (supported_ref_vars_.find(varId) != supported_ref_vars_.end()) return true;
-  analysis::UseList* uses = get_def_use_mgr()->GetUses(varId);
-  if (uses == nullptr) return true;
-  for (auto u : *uses) {
-    const SpvOp op = u.inst->opcode();
+  bool hasOnlySupportedRefs = true;
+  get_def_use_mgr()->ForEachUser(varId, [this,&hasOnlySupportedRefs](ir::Instruction* user) {
+    SpvOp op = user->opcode();
     if (op != SpvOpStore && op != SpvOpLoad && op != SpvOpName &&
-        !IsNonTypeDecorate(op))
-      return false;
-  }
-  supported_ref_vars_.insert(varId);
-  return true;
+        !IsNonTypeDecorate(op)) {
+      hasOnlySupportedRefs = false;
+    }
+  });
+  return hasOnlySupportedRefs;
 }
 
 void MemPass::InitSSARewrite(ir::Function* func) {
diff --git a/source/opt/merge_return_pass.cpp b/source/opt/merge_return_pass.cpp
index e822885..c63bedd 100644
--- a/source/opt/merge_return_pass.cpp
+++ b/source/opt/merge_return_pass.cpp
@@ -58,19 +58,25 @@ bool MergeReturnPass::MergeReturnBlocks(
     return false;
   }
 
+  std::vector<ir::Instruction*> uses_to_update;
+
   // Create a label for the new return block
   std::unique_ptr<ir::Instruction> returnLabel(
       new ir::Instruction(context(), SpvOpLabel, 0u, TakeNextId(), {}));
   uint32_t returnId = returnLabel->result_id();
 
-  // Create the new basic block
+  // Create the new basic block.
   std::unique_ptr<ir::BasicBlock> returnBlock(
       new ir::BasicBlock(std::move(returnLabel)));
   function->AddBasicBlock(std::move(returnBlock));
   ir::Function::iterator retBlockIter = --function->end();
 
-  // Create the PHI for the merged block (if necessary)
-  // Create new return
+  // Register the definition of the return and mark it to update its uses.
+  get_def_use_mgr()->AnalyzeInstDef(retBlockIter->GetLabelInst());
+  uses_to_update.push_back(retBlockIter->GetLabelInst());
+
+  // Create the PHI for the merged block (if necessary).
+  // Create new return.
   std::vector<ir::Operand> phiOps;
   for (auto block : returnBlocks) {
     if (block->tail()->opcode() == SpvOpReturnValue) {
@@ -95,8 +101,10 @@ bool MergeReturnPass::MergeReturnBlocks(
     retBlockIter->AddInstruction(std::move(returnInst));
     ir::BasicBlock::iterator ret = retBlockIter->tail();
 
-    get_def_use_mgr()->AnalyzeInstDefUse(&*phiIter);
-    get_def_use_mgr()->AnalyzeInstDef(&*ret);
+    // Register the phi def and mark instructions for use updates.
+    get_def_use_mgr()->AnalyzeInstDef(&*phiIter);
+    uses_to_update.push_back(&*ret);
+    uses_to_update.push_back(&*phiIter);
   } else {
     std::unique_ptr<ir::Instruction> returnInst(
         new ir::Instruction(context(), SpvOpReturn));
@@ -108,11 +116,13 @@ bool MergeReturnPass::MergeReturnBlocks(
     context()->KillInst(&*block->tail());
     block->tail()->SetOpcode(SpvOpBranch);
     block->tail()->ReplaceOperands({{SPV_OPERAND_TYPE_ID, {returnId}}});
-    get_def_use_mgr()->AnalyzeInstUse(&*block->tail());
-    get_def_use_mgr()->AnalyzeInstUse(block->GetLabelInst());
+    uses_to_update.push_back(&*block->tail());
+    uses_to_update.push_back(block->GetLabelInst());
   }
 
-  get_def_use_mgr()->AnalyzeInstDefUse(retBlockIter->GetLabelInst());
+  for (auto& inst : uses_to_update) {
+    context()->AnalyzeUses(inst);
+  }
 
   return true;
 }
diff --git a/source/opt/set_spec_constant_default_value_pass.cpp b/source/opt/set_spec_constant_default_value_pass.cpp
index 9f2786e..a8f3e03 100644
--- a/source/opt/set_spec_constant_default_value_pass.cpp
+++ b/source/opt/set_spec_constant_default_value_pass.cpp
@@ -137,13 +137,11 @@ ir::Instruction* GetSpecIdTargetFromDecorationGroup(
   // the first OpGroupDecoration instruction that uses the given decoration
   // group.
   ir::Instruction* group_decorate_inst = nullptr;
-  for (const auto& u :
-       *def_use_mgr->GetUses(decoration_group_defining_inst.result_id())) {
-    if (u.inst->opcode() == SpvOp::SpvOpGroupDecorate) {
-      group_decorate_inst = u.inst;
-      break;
+  def_use_mgr->ForEachUser(&decoration_group_defining_inst, [&group_decorate_inst](ir::Instruction* user) {
+    if (user->opcode() == SpvOp::SpvOpGroupDecorate) {
+      group_decorate_inst = user;
     }
-  }
+  });
   if (!group_decorate_inst) return nullptr;
 
   // Scan through the target ids of the OpGroupDecorate instruction. There
diff --git a/source/opt/strength_reduction_pass.cpp b/source/opt/strength_reduction_pass.cpp
index f2aee91..28da788 100644
--- a/source/opt/strength_reduction_pass.cpp
+++ b/source/opt/strength_reduction_pass.cpp
@@ -104,8 +104,8 @@ bool StrengthReductionPass::ReplaceMultiplyByPowerOf2(
                                 newResultId, newOperands));
 
         // Insert the new instruction and update the data structures.
-        get_def_use_mgr()->AnalyzeInstDefUse(&*newInstruction);
         inst = inst.InsertBefore(std::move(newInstruction));
+        get_def_use_mgr()->AnalyzeInstDefUse(&*inst);
         ++inst;
         context()->ReplaceAllUsesWith(inst->result_id(), newResultId);
 
@@ -164,6 +164,10 @@ uint32_t StrengthReductionPass::GetConstantId(uint32_t val) {
         context(), SpvOp::SpvOpConstant, uint32_type_id_, resultId, {constant}));
     get_module()->AddGlobalValue(std::move(newConstant));
 
+    // Notify the DefUseManager about this constant.
+    auto constantIter = --get_module()->types_values_end();
+    get_def_use_mgr()->AnalyzeInstDef(&*constantIter);
+
     // Store the result id for next time.
     constant_ids_[val] = resultId;
   }
diff --git a/test/link/entry_points_test.cpp b/test/link/entry_points_test.cpp
index 54561d5..0193450 100644
--- a/test/link/entry_points_test.cpp
+++ b/test/link/entry_points_test.cpp
@@ -23,10 +23,18 @@ class EntryPoints : public spvtest::LinkerTest {};
 
 TEST_F(EntryPoints, SameModelDifferentName) {
   const std::string body1 = R"(
-OpEntryPoint GLCompute %1 "foo"
+OpEntryPoint GLCompute %3 "foo"
+%1 = OpTypeVoid
+%2 = OpTypeFunction %1
+%3 = OpFunction %1 None %2
+OpFunctionEnd
 )";
   const std::string body2 = R"(
-OpEntryPoint GLCompute %1 "bar"
+OpEntryPoint GLCompute %3 "bar"
+%1 = OpTypeVoid
+%2 = OpTypeFunction %1
+%3 = OpFunction %1 None %2
+OpFunctionEnd
 )";
 
   spvtest::Binary linked_binary;
@@ -36,10 +44,18 @@ OpEntryPoint GLCompute %1 "bar"
 
 TEST_F(EntryPoints, DifferentModelSameName) {
   const std::string body1 = R"(
-OpEntryPoint GLCompute %1 "foo"
+OpEntryPoint GLCompute %3 "foo"
+%1 = OpTypeVoid
+%2 = OpTypeFunction %1
+%3 = OpFunction %1 None %2
+OpFunctionEnd
 )";
   const std::string body2 = R"(
-OpEntryPoint Vertex %1 "foo"
+OpEntryPoint Vertex %3 "foo"
+%1 = OpTypeVoid
+%2 = OpTypeFunction %1
+%3 = OpFunction %1 None %2
+OpFunctionEnd
 )";
 
   spvtest::Binary linked_binary;
@@ -49,10 +65,18 @@ OpEntryPoint Vertex %1 "foo"
 
 TEST_F(EntryPoints, SameModelAndName) {
   const std::string body1 = R"(
-OpEntryPoint GLCompute %1 "foo"
+OpEntryPoint GLCompute %3 "foo"
+%1 = OpTypeVoid
+%2 = OpTypeFunction %1
+%3 = OpFunction %1 None %2
+OpFunctionEnd
 )";
   const std::string body2 = R"(
-OpEntryPoint GLCompute %1 "foo"
+OpEntryPoint GLCompute %3 "foo"
+%1 = OpTypeVoid
+%2 = OpTypeFunction %1
+%3 = OpFunction %1 None %2
+OpFunctionEnd
 )";
 
   spvtest::Binary linked_binary;
diff --git a/test/link/global_values_amount_test.cpp b/test/link/global_values_amount_test.cpp
index 068e6fa..0061ac2 100644
--- a/test/link/global_values_amount_test.cpp
+++ b/test/link/global_values_amount_test.cpp
@@ -105,9 +105,6 @@ class EntryPoints : public spvtest::LinkerTest {
   spvtest::Binaries binaries;
 };
 
-// TODO(dneto): Fix performance issue for debug builds on Windows
-#if !(defined(SPIRV_WINDOWS) && defined(_DEBUG))
-
 TEST_F(EntryPoints, UnderLimit) {
   spvtest::Binary linked_binary;
 
@@ -148,6 +145,5 @@ TEST_F(EntryPoints, OverLimit) {
               HasSubstr("The limit of global values, 65535, was exceeded; "
                         "65536 global values were found."));
 }
-#endif // !(defined(SPIRV_WINDOWS) && defined(_DEBUG))
 
 }  // anonymous namespace
diff --git a/test/opt/def_use_test.cpp b/test/opt/def_use_test.cpp
index bd1ac7e..b51f489 100644
--- a/test/opt/def_use_test.cpp
+++ b/test/opt/def_use_test.cpp
@@ -33,6 +33,27 @@ using ::testing::UnorderedElementsAreArray;
 using namespace spvtools;
 using spvtools::opt::analysis::DefUseManager;
 
+// Returns the number of uses of |id|.
+uint32_t NumUses(const std::unique_ptr<ir::IRContext> &context, uint32_t id) {
+  uint32_t count = 0;
+  context->get_def_use_mgr()->ForEachUse(id, [&count](ir::Instruction*, uint32_t) {
+    ++count;
+  });
+  return count;
+}
+
+// Returns the opcode of each use of |id|.
+//
+// If |id| is used multiple times in a single instruction, that instruction's
+// opcode will appear a corresponding number of times.
+std::vector<SpvOp> GetUseOpcodes(const std::unique_ptr<ir::IRContext> &context, uint32_t id) {
+  std::vector<SpvOp> opcodes;
+  context->get_def_use_mgr()->ForEachUse(id, [&opcodes](ir::Instruction* user, uint32_t) {
+    opcodes.push_back(user->opcode());
+  });
+  return opcodes;
+}
+
 // Disassembles the given |inst| and returns the disassembly.
 std::string DisassembleInst(ir::Instruction* inst) {
   SpirvTools tools(SPV_ENV_UNIVERSAL_1_1);
@@ -71,12 +92,39 @@ void CheckDef(const InstDefUse& expected_defs_uses,
     const auto id = expected_defs_uses.defs[i].first;
     const auto expected_def = expected_defs_uses.defs[i].second;
     ASSERT_EQ(1u, actual_defs.count(id)) << "expected to def id [" << id << "]";
-    EXPECT_EQ(expected_def, DisassembleInst(actual_defs.at(id)));
+    auto def = actual_defs.at(id);
+    if (def->opcode() != SpvOpConstant) {
+      // Constants don't disassemble properly without a full context.
+      EXPECT_EQ(expected_def, DisassembleInst(actual_defs.at(id)));
+    }
+  }
+}
+
+using UserMap = std::unordered_map<uint32_t, std::vector<ir::Instruction*>>;
+
+// Creates a mapping of all definitions to their users (except OpConstant).
+//
+// OpConstants are skipped because they cannot be disassembled in isolation.
+UserMap BuildAllUsers(const DefUseManager* mgr, uint32_t idBound) {
+  UserMap userMap;
+  for (uint32_t id = 0; id != idBound; ++id) {
+    if (mgr->GetDef(id)) {
+      mgr->ForEachUser(id, [id,&userMap](ir::Instruction* user) {
+        if (user->opcode() != SpvOpConstant) {
+          userMap[id].push_back(user);
+        }
+      });
+    }
   }
+  return userMap;
 }
 
+// Constants don't disassemble properly without a full context, so skip them as
+// checks.
 void CheckUse(const InstDefUse& expected_defs_uses,
-              const DefUseManager::IdToUsesMap& actual_uses) {
+              const DefUseManager* mgr,
+              uint32_t idBound) {
+  UserMap actual_uses = BuildAllUsers(mgr, idBound);
   // Check uses.
   ASSERT_EQ(expected_defs_uses.uses.size(), actual_uses.size());
   for (uint32_t i = 0; i < expected_defs_uses.uses.size(); ++i) {
@@ -92,7 +140,7 @@ void CheckUse(const InstDefUse& expected_defs_uses,
 
     std::vector<std::string> actual_uses_disassembled;
     for (const auto actual_use : uses) {
-      actual_uses_disassembled.emplace_back(DisassembleInst(actual_use.inst));
+      actual_uses_disassembled.emplace_back(DisassembleInst(actual_use));
     }
     EXPECT_THAT(actual_uses_disassembled,
                 UnorderedElementsAreArray(expected_uses));
@@ -103,6 +151,14 @@ void CheckUse(const InstDefUse& expected_defs_uses,
 // But, yeah, it's not very readable. However, we only care about the id
 // defs and uses. So, no need to make sure this is valid OpPhi construct.
 const char kOpPhiTestFunction[] =
+    " %1 = OpTypeVoid "
+    " %6 = OpTypeInt 32 0 "
+    "%10 = OpTypeFloat 32 "
+    "%16 = OpTypeBool "
+    " %3 = OpTypeFunction %1 "
+    " %8 = OpConstant %6 0 "
+    "%18 = OpConstant %6 1 "
+    "%12 = OpConstant %10 1.0 "
     " %2 = OpFunction %1 None %3 "
     " %4 = OpLabel "
     "      OpBranch %5 "
@@ -110,8 +166,8 @@ const char kOpPhiTestFunction[] =
     " %5 = OpLabel "
     " %7 = OpPhi %6 %8 %4 %9 %5 "
     "%11 = OpPhi %10 %12 %4 %13 %5 "
-    " %9 = OpIAdd %6 %7 %14 "
-    "%13 = OpFAdd %10 %11 %15 "
+    " %9 = OpIAdd %6 %7 %8 "
+    "%13 = OpFAdd %10 %11 %12 "
     "%17 = OpSLessThan %16 %7 %18 "
     "      OpLoopMerge %19 %5 None "
     "      OpBranchConditional %17 %5 %19 "
@@ -133,14 +189,15 @@ TEST_P(ParseDefUseTest, Case) {
   // Build module.
   const std::vector<const char*> text = {tc.text};
   std::unique_ptr<ir::IRContext> context =
-      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, JoinAllInsts(text));
+      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, JoinAllInsts(text),
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
   ASSERT_NE(nullptr, context);
 
   // Analyze def and use.
   opt::analysis::DefUseManager manager(context->module());
 
   CheckDef(tc.du, manager.id_to_defs());
-  CheckUse(tc.du, manager.id_to_uses());
+  CheckUse(tc.du, &manager, context->module()->IdBound());
 }
 
 // clang-format off
@@ -169,28 +226,6 @@ INSTANTIATE_TEST_CASE_P(
             {} // uses
           }
         },
-        { // single use, no def
-          "OpTypeForwardPointer %1 Input",
-          {
-            {}, // defs
-            {   // uses
-              {1, {"OpTypeForwardPointer %1 Input"}},
-            }
-          }
-        },
-        { // multiple use, no def
-          "OpEntryPoint Fragment %1 \"main\" "
-          "OpTypeForwardPointer %2 Input "
-          "OpTypeForwardPointer %3 Output",
-          {
-            {}, // defs
-            {   // uses
-              {1, {"OpEntryPoint Fragment %1 \"main\""}},
-              {2, {"OpTypeForwardPointer %2 Input"}},
-              {3, {"OpTypeForwardPointer %3 Output"}},
-            }
-          }
-        },
         { // multiple def, multiple use
           "%1 = OpTypeBool "
           "%2 = OpTypeVector %1 3 "
@@ -231,42 +266,55 @@ INSTANTIATE_TEST_CASE_P(
           }
         },
         { // labels
-          "%2 = OpFunction %1 None %3 "
-
-          "%4 = OpLabel "
-          "OpBranchConditional %5 %6 %7 "
+          "%1 = OpTypeVoid "
+          "%2 = OpTypeBool "
+          "%3 = OpTypeFunction %1 "
+          "%4 = OpConstantTrue %2 "
+          "%5 = OpFunction %1 None %3 "
 
           "%6 = OpLabel "
-          "OpBranch %7 "
+          "OpBranchConditional %4 %7 %8 "
 
           "%7 = OpLabel "
+          "OpBranch %7 "
+
+          "%8 = OpLabel "
           "OpReturn "
 
           "OpFunctionEnd",
           {
             { // defs
-              {2, "%2 = OpFunction %1 None %3"},
-              {4, "%4 = OpLabel"},
+              {1, "%1 = OpTypeVoid"},
+              {2, "%2 = OpTypeBool"},
+              {3, "%3 = OpTypeFunction %1"},
+              {4, "%4 = OpConstantTrue %2"},
+              {5, "%5 = OpFunction %1 None %3"},
               {6, "%6 = OpLabel"},
               {7, "%7 = OpLabel"},
+              {8, "%8 = OpLabel"},
             },
             { // uses
-              {1, {"%2 = OpFunction %1 None %3"}},
-              {3, {"%2 = OpFunction %1 None %3"}},
-              {5, {"OpBranchConditional %5 %6 %7"}},
-              {6, {"OpBranchConditional %5 %6 %7"}},
+              {1, {
+                    "%3 = OpTypeFunction %1",
+                    "%5 = OpFunction %1 None %3",
+                  }
+              },
+              {2, {"%4 = OpConstantTrue %2"}},
+              {3, {"%5 = OpFunction %1 None %3"}},
+              {4, {"OpBranchConditional %4 %7 %8"}},
               {7,
                 {
-                  "OpBranchConditional %5 %6 %7",
+                  "OpBranchConditional %4 %7 %8",
                   "OpBranch %7",
                 }
               },
+              {8, {"OpBranchConditional %4 %7 %8"}},
             }
           }
         },
         { // cross function
           "%1 = OpTypeBool "
-
+          "%3 = OpTypeFunction %1 "
           "%2 = OpFunction %1 None %3 "
 
           "%4 = OpLabel "
@@ -279,6 +327,7 @@ INSTANTIATE_TEST_CASE_P(
             { // defs
               {1, "%1 = OpTypeBool"},
               {2, "%2 = OpFunction %1 None %3"},
+              {3, "%3 = OpTypeFunction %1"},
               {4, "%4 = OpLabel"},
               {5, "%5 = OpVariable %1 Function"},
               {6, "%6 = OpFunctionCall %1 %2 %5"},
@@ -287,18 +336,23 @@ INSTANTIATE_TEST_CASE_P(
               {1,
                 {
                   "%2 = OpFunction %1 None %3",
+                  "%3 = OpTypeFunction %1",
                   "%5 = OpVariable %1 Function",
                   "%6 = OpFunctionCall %1 %2 %5",
                 }
               },
               {2, {"%6 = OpFunctionCall %1 %2 %5"}},
-              {5, {"%6 = OpFunctionCall %1 %2 %5"}},
               {3, {"%2 = OpFunction %1 None %3"}},
+              {5, {"%6 = OpFunctionCall %1 %2 %5"}},
               {6, {"OpReturnValue %6"}},
             }
           }
         },
         { // selection merge and loop merge
+          "%1 = OpTypeVoid "
+          "%3 = OpTypeFunction %1 "
+          "%10 = OpTypeBool "
+          "%8 = OpConstantTrue %10 "
           "%2 = OpFunction %1 None %3 "
 
           "%4 = OpLabel "
@@ -321,15 +375,24 @@ INSTANTIATE_TEST_CASE_P(
           "OpFunctionEnd",
           {
             { // defs
+              {1, "%1 = OpTypeVoid"},
               {2, "%2 = OpFunction %1 None %3"},
+              {3, "%3 = OpTypeFunction %1"},
               {4, "%4 = OpLabel"},
               {5, "%5 = OpLabel"},
               {6, "%6 = OpLabel"},
               {7, "%7 = OpLabel"},
+              {8, "%8 = OpConstantTrue %10"},
               {9, "%9 = OpLabel"},
+              {10, "%10 = OpTypeBool"},
             },
             { // uses
-              {1, {"%2 = OpFunction %1 None %3"}},
+              {1,
+                {
+                  "%2 = OpFunction %1 None %3",
+                  "%3 = OpTypeFunction %1",
+                }
+              },
               {3, {"%2 = OpFunction %1 None %3"}},
               {4, {"OpLoopMerge %5 %4 None"}},
               {5, {"OpLoopMerge %5 %4 None"}},
@@ -342,6 +405,7 @@ INSTANTIATE_TEST_CASE_P(
               },
               {8, {"OpBranchConditional %8 %9 %7"}},
               {9, {"OpBranchConditional %8 %9 %7"}},
+              {10, {"%8 = OpConstantTrue %10"}},
             }
           }
         },
@@ -373,18 +437,31 @@ INSTANTIATE_TEST_CASE_P(
           kOpPhiTestFunction,
           {
             { // defs
+              {1, "%1 = OpTypeVoid"},
               {2, "%2 = OpFunction %1 None %3"},
+              {3, "%3 = OpTypeFunction %1"},
               {4, "%4 = OpLabel"},
               {5, "%5 = OpLabel"},
+              {6, "%6 = OpTypeInt 32 0"},
               {7, "%7 = OpPhi %6 %8 %4 %9 %5"},
-              {9, "%9 = OpIAdd %6 %7 %14"},
+              {8, "%8 = OpConstant %6 0"},
+              {9, "%9 = OpIAdd %6 %7 %8"},
+              {10, "%10 = OpTypeFloat 32"},
               {11, "%11 = OpPhi %10 %12 %4 %13 %5"},
-              {13, "%13 = OpFAdd %10 %11 %15"},
+              {12, "%12 = OpConstant %10 1.0"},
+              {13, "%13 = OpFAdd %10 %11 %12"},
+              {16, "%16 = OpTypeBool"},
               {17, "%17 = OpSLessThan %16 %7 %18"},
+              {18, "%18 = OpConstant %6 1"},
               {19, "%19 = OpLabel"},
             },
             { // uses
-              {1, {"%2 = OpFunction %1 None %3"}},
+              {1,
+                {
+                  "%2 = OpFunction %1 None %3",
+                  "%3 = OpTypeFunction %1",
+                }
+              },
               {3, {"%2 = OpFunction %1 None %3"}},
               {4,
                 {
@@ -403,29 +480,41 @@ INSTANTIATE_TEST_CASE_P(
               },
               {6,
                 {
+                  // Can't check constants properly
+                  //"%8 = OpConstant %6 0",
+                  //"%18 = OpConstant %6 1",
                   "%7 = OpPhi %6 %8 %4 %9 %5",
-                  "%9 = OpIAdd %6 %7 %14",
+                  "%9 = OpIAdd %6 %7 %8",
                 }
               },
               {7,
                 {
-                  "%9 = OpIAdd %6 %7 %14",
+                  "%9 = OpIAdd %6 %7 %8",
                   "%17 = OpSLessThan %16 %7 %18",
                 }
               },
-              {8, {"%7 = OpPhi %6 %8 %4 %9 %5"}},
+              {8,
+                {
+                  "%7 = OpPhi %6 %8 %4 %9 %5",
+                  "%9 = OpIAdd %6 %7 %8",
+                }
+              },
               {9, {"%7 = OpPhi %6 %8 %4 %9 %5"}},
               {10,
                 {
+                  //"%12 = OpConstant %10 1.0",
                   "%11 = OpPhi %10 %12 %4 %13 %5",
-                  "%13 = OpFAdd %10 %11 %15",
+                  "%13 = OpFAdd %10 %11 %12",
+                }
+              },
+              {11, {"%13 = OpFAdd %10 %11 %12"}},
+              {12,
+                {
+                  "%11 = OpPhi %10 %12 %4 %13 %5",
+                  "%13 = OpFAdd %10 %11 %12",
                 }
               },
-              {11, {"%13 = OpFAdd %10 %11 %15"}},
-              {12, {"%11 = OpPhi %10 %12 %4 %13 %5"}},
               {13, {"%11 = OpPhi %10 %12 %4 %13 %5"}},
-              {14, {"%9 = OpIAdd %6 %7 %14"}},
-              {15, {"%13 = OpFAdd %10 %11 %15"}},
               {16, {"%17 = OpSLessThan %16 %7 %18"}},
               {17, {"OpBranchConditional %17 %5 %19"}},
               {18, {"%17 = OpSLessThan %16 %7 %18"}},
@@ -440,9 +529,9 @@ INSTANTIATE_TEST_CASE_P(
         },
         { // OpPhi defining and referencing the same id.
           "%1 = OpTypeBool "
+          "%3 = OpTypeFunction %1 "
           "%2 = OpConstantTrue %1 "
-
-          "%4 = OpFunction %3 None %5 "
+          "%4 = OpFunction %1 None %3 "
           "%6 = OpLabel "
           "     OpBranch %7 "
           "%7 = OpLabel "
@@ -453,7 +542,8 @@ INSTANTIATE_TEST_CASE_P(
             { // defs
               {1, "%1 = OpTypeBool"},
               {2, "%2 = OpConstantTrue %1"},
-              {4, "%4 = OpFunction %3 None %5"},
+              {3, "%3 = OpTypeFunction %1"},
+              {4, "%4 = OpFunction %1 None %3"},
               {6, "%6 = OpLabel"},
               {7, "%7 = OpLabel"},
               {8, "%8 = OpPhi %1 %8 %7 %2 %6"},
@@ -462,12 +552,13 @@ INSTANTIATE_TEST_CASE_P(
               {1,
                 {
                   "%2 = OpConstantTrue %1",
+                  "%3 = OpTypeFunction %1",
+                  "%4 = OpFunction %1 None %3",
                   "%8 = OpPhi %1 %8 %7 %2 %6",
                 }
               },
               {2, {"%8 = OpPhi %1 %8 %7 %2 %6"}},
-              {3, {"%4 = OpFunction %3 None %5"}},
-              {5, {"%4 = OpFunction %3 None %5"}},
+              {3, {"%4 = OpFunction %1 None %3"}},
               {6, {"%8 = OpPhi %1 %8 %7 %2 %6"}},
               {7,
                 {
@@ -514,7 +605,8 @@ TEST_P(ReplaceUseTest, Case) {
   // Build module.
   const std::vector<const char*> text = {tc.before};
   std::unique_ptr<ir::IRContext> context =
-      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, JoinAllInsts(text));
+      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, JoinAllInsts(text),
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
   ASSERT_NE(nullptr, context);
 
   // Force a re-build of def-use manager.
@@ -528,7 +620,7 @@ TEST_P(ReplaceUseTest, Case) {
 
   EXPECT_EQ(tc.after, DisassembleModule(context->module()));
   CheckDef(tc.du, context->get_def_use_mgr()->id_to_defs());
-  CheckUse(tc.du, context->get_def_use_mgr()->id_to_uses());
+  CheckUse(tc.du, context->get_def_use_mgr(), context->module()->IdBound());
 }
 
 // clang-format off
@@ -538,22 +630,19 @@ INSTANTIATE_TEST_CASE_P(
       { // no use, no replace request
         "", {}, "", {},
       },
-      { // no use, some replace requests
-        "OpMemoryModel Logical GLSL450",
-        {{1, 2}, {3, 4}, {7, 8}, {7, 9}, {7, 10}, {2, 10}, {3, 10}},
-        "OpMemoryModel Logical GLSL450",
-        {},
-      },
       { // replace one use
         "%1 = OpTypeBool "
-        "%2 = OpTypeVector %1 3",
+        "%2 = OpTypeVector %1 3 "
+        "%3 = OpTypeInt 32 0 ",
         {{1, 3}},
         "%1 = OpTypeBool\n"
-        "%2 = OpTypeVector %3 3",
+        "%2 = OpTypeVector %3 3\n"
+        "%3 = OpTypeInt 32 0",
         {
           { // defs
             {1, "%1 = OpTypeBool"},
             {2, "%2 = OpTypeVector %3 3"},
+            {3, "%3 = OpTypeInt 32 0"},
           },
           { // uses
             {3, {"%2 = OpTypeVector %3 3"}},
@@ -562,14 +651,17 @@ INSTANTIATE_TEST_CASE_P(
       },
       { // replace and then replace back
         "%1 = OpTypeBool "
-        "%2 = OpTypeVector %1 3",
+        "%2 = OpTypeVector %1 3 "
+        "%3 = OpTypeInt 32 0",
         {{1, 3}, {3, 1}},
         "%1 = OpTypeBool\n"
-        "%2 = OpTypeVector %1 3",
+        "%2 = OpTypeVector %1 3\n"
+        "%3 = OpTypeInt 32 0",
         {
           { // defs
             {1, "%1 = OpTypeBool"},
             {2, "%2 = OpTypeVector %1 3"},
+            {3, "%3 = OpTypeInt 32 0"},
           },
           { // uses
             {1, {"%2 = OpTypeVector %1 3"}},
@@ -594,17 +686,23 @@ INSTANTIATE_TEST_CASE_P(
       },
       { // replace in sequence
         "%1 = OpTypeBool "
-        "%2 = OpTypeVector %1 3",
-        {{1, 3}, {3, 4}, {4, 5}, {5, 100}},
+        "%2 = OpTypeVector %1 3 "
+        "%3 = OpTypeInt 32 0 "
+        "%4 = OpTypeInt 32 1 ",
+        {{1, 3}, {3, 4}},
         "%1 = OpTypeBool\n"
-        "%2 = OpTypeVector %100 3",
+        "%2 = OpTypeVector %4 3\n"
+        "%3 = OpTypeInt 32 0\n"
+        "%4 = OpTypeInt 32 1",
         {
           { // defs
             {1, "%1 = OpTypeBool"},
-            {2, "%2 = OpTypeVector %100 3"},
+            {2, "%2 = OpTypeVector %4 3"},
+            {3, "%3 = OpTypeInt 32 0"},
+            {4, "%4 = OpTypeInt 32 1"},
           },
           { // uses
-            {100, {"%2 = OpTypeVector %100 3"}},
+            {4, {"%2 = OpTypeVector %4 3"}},
           },
         },
       },
@@ -615,52 +713,69 @@ INSTANTIATE_TEST_CASE_P(
         "%4 = OpTypeVector %1 4 "
         "%5 = OpTypeMatrix %2 2 "
         "%6 = OpTypeMatrix %3 3 "
-        "%7 = OpTypeMatrix %4 4",
-        {{1, 10}, {2, 20}, {4, 40}},
+        "%7 = OpTypeMatrix %4 4 "
+        "%8 = OpTypeInt 32 0 "
+        "%9 = OpTypeInt 32 1 "
+        "%10 = OpTypeInt 64 0",
+        {{1, 8}, {2, 9}, {4, 10}},
         "%1 = OpTypeBool\n"
-        "%2 = OpTypeVector %10 2\n"
-        "%3 = OpTypeVector %10 3\n"
-        "%4 = OpTypeVector %10 4\n"
-        "%5 = OpTypeMatrix %20 2\n"
+        "%2 = OpTypeVector %8 2\n"
+        "%3 = OpTypeVector %8 3\n"
+        "%4 = OpTypeVector %8 4\n"
+        "%5 = OpTypeMatrix %9 2\n"
         "%6 = OpTypeMatrix %3 3\n"
-        "%7 = OpTypeMatrix %40 4",
+        "%7 = OpTypeMatrix %10 4\n"
+        "%8 = OpTypeInt 32 0\n"
+        "%9 = OpTypeInt 32 1\n"
+        "%10 = OpTypeInt 64 0",
         {
           { // defs
             {1, "%1 = OpTypeBool"},
-            {2, "%2 = OpTypeVector %10 2"},
-            {3, "%3 = OpTypeVector %10 3"},
-            {4, "%4 = OpTypeVector %10 4"},
-            {5, "%5 = OpTypeMatrix %20 2"},
+            {2, "%2 = OpTypeVector %8 2"},
+            {3, "%3 = OpTypeVector %8 3"},
+            {4, "%4 = OpTypeVector %8 4"},
+            {5, "%5 = OpTypeMatrix %9 2"},
             {6, "%6 = OpTypeMatrix %3 3"},
-            {7, "%7 = OpTypeMatrix %40 4"},
+            {7, "%7 = OpTypeMatrix %10 4"},
+            {8, "%8 = OpTypeInt 32 0"},
+            {9, "%9 = OpTypeInt 32 1"},
+            {10, "%10 = OpTypeInt 64 0"},
           },
           { // uses
-            {10,
+            {8,
               {
-                "%2 = OpTypeVector %10 2",
-                "%3 = OpTypeVector %10 3",
-                "%4 = OpTypeVector %10 4",
+                "%2 = OpTypeVector %8 2",
+                "%3 = OpTypeVector %8 3",
+                "%4 = OpTypeVector %8 4",
               }
             },
-            {20, {"%5 = OpTypeMatrix %20 2"}},
+            {9, {"%5 = OpTypeMatrix %9 2"}},
             {3, {"%6 = OpTypeMatrix %3 3"}},
-            {40, {"%7 = OpTypeMatrix %40 4"}},
+            {10, {"%7 = OpTypeMatrix %10 4"}},
           },
         },
       },
       { // OpPhi.
         kOpPhiTestFunction,
         // replace one id used by OpPhi, replace one id generated by OpPhi
-        {{9, 9000}, {11, 9}},
+        {{9, 13}, {11, 9}},
+         "%1 = OpTypeVoid\n"
+         "%6 = OpTypeInt 32 0\n"
+         "%10 = OpTypeFloat 32\n"
+         "%16 = OpTypeBool\n"
+         "%3 = OpTypeFunction %1\n"
+         "%8 = OpConstant %6 0\n"
+         "%18 = OpConstant %6 1\n"
+         "%12 = OpConstant %10 1\n"
          "%2 = OpFunction %1 None %3\n"
          "%4 = OpLabel\n"
                "OpBranch %5\n"
 
          "%5 = OpLabel\n"
-         "%7 = OpPhi %6 %8 %4 %9000 %5\n" // %9 -> %9000
+         "%7 = OpPhi %6 %8 %4 %13 %5\n" // %9 -> %13
         "%11 = OpPhi %10 %12 %4 %13 %5\n"
-         "%9 = OpIAdd %6 %7 %14\n"
-        "%13 = OpFAdd %10 %9 %15\n"       // %11 -> %9
+         "%9 = OpIAdd %6 %7 %8\n"
+        "%13 = OpFAdd %10 %9 %12\n"       // %11 -> %9
         "%17 = OpSLessThan %16 %7 %18\n"
               "OpLoopMerge %19 %5 None\n"
               "OpBranchConditional %17 %5 %19\n"
@@ -670,29 +785,42 @@ INSTANTIATE_TEST_CASE_P(
               "OpFunctionEnd",
         {
           { // defs.
+            {1, "%1 = OpTypeVoid"},
             {2, "%2 = OpFunction %1 None %3"},
+            {3, "%3 = OpTypeFunction %1"},
             {4, "%4 = OpLabel"},
             {5, "%5 = OpLabel"},
-            {7, "%7 = OpPhi %6 %8 %4 %9000 %5"},
-            {9, "%9 = OpIAdd %6 %7 %14"},
+            {6, "%6 = OpTypeInt 32 0"},
+            {7, "%7 = OpPhi %6 %8 %4 %13 %5"},
+            {8, "%8 = OpConstant %6 0"},
+            {9, "%9 = OpIAdd %6 %7 %8"},
+            {10, "%10 = OpTypeFloat 32"},
             {11, "%11 = OpPhi %10 %12 %4 %13 %5"},
-            {13, "%13 = OpFAdd %10 %9 %15"},
+            {12, "%12 = OpConstant %10 1.0"},
+            {13, "%13 = OpFAdd %10 %9 %12"},
+            {16, "%16 = OpTypeBool"},
             {17, "%17 = OpSLessThan %16 %7 %18"},
+            {18, "%18 = OpConstant %6 1"},
             {19, "%19 = OpLabel"},
           },
           { // uses
-            {1, {"%2 = OpFunction %1 None %3"}},
+            {1,
+              {
+                "%2 = OpFunction %1 None %3",
+                "%3 = OpTypeFunction %1",
+              }
+            },
             {3, {"%2 = OpFunction %1 None %3"}},
             {4,
               {
-                "%7 = OpPhi %6 %8 %4 %9000 %5",
+                "%7 = OpPhi %6 %8 %4 %13 %5",
                 "%11 = OpPhi %10 %12 %4 %13 %5",
               }
             },
             {5,
               {
                 "OpBranch %5",
-                "%7 = OpPhi %6 %8 %4 %9000 %5",
+                "%7 = OpPhi %6 %8 %4 %13 %5",
                 "%11 = OpPhi %10 %12 %4 %13 %5",
                 "OpLoopMerge %19 %5 None",
                 "OpBranchConditional %17 %5 %19",
@@ -700,29 +828,45 @@ INSTANTIATE_TEST_CASE_P(
             },
             {6,
               {
-                "%7 = OpPhi %6 %8 %4 %9000 %5",
-                "%9 = OpIAdd %6 %7 %14",
+                // Can't properly check constants
+                //"%8 = OpConstant %6 0",
+                //"%18 = OpConstant %6 1",
+                "%7 = OpPhi %6 %8 %4 %13 %5",
+                "%9 = OpIAdd %6 %7 %8"
               }
             },
             {7,
               {
-                "%9 = OpIAdd %6 %7 %14",
+                "%9 = OpIAdd %6 %7 %8",
                 "%17 = OpSLessThan %16 %7 %18",
               }
             },
-            {8, {"%7 = OpPhi %6 %8 %4 %9000 %5"}},
-            {9, {"%13 = OpFAdd %10 %9 %15"}}, // uses of %9 changed from %7 to %13
+            {8,
+              {
+                "%7 = OpPhi %6 %8 %4 %13 %5",
+                "%9 = OpIAdd %6 %7 %8",
+              }
+            },
+            {9, {"%13 = OpFAdd %10 %9 %12"}}, // uses of %9 changed from %7 to %13
             {10,
               {
                 "%11 = OpPhi %10 %12 %4 %13 %5",
-                "%13 = OpFAdd %10 %9 %15",
+                //"%12 = OpConstant %10 1",
+                "%13 = OpFAdd %10 %9 %12"
               }
             },
             // no more uses of %11
-            {12, {"%11 = OpPhi %10 %12 %4 %13 %5"}},
-            {13, {"%11 = OpPhi %10 %12 %4 %13 %5"}},
-            {14, {"%9 = OpIAdd %6 %7 %14"}},
-            {15, {"%13 = OpFAdd %10 %9 %15"}},
+            {12,
+              {
+                "%11 = OpPhi %10 %12 %4 %13 %5",
+                "%13 = OpFAdd %10 %9 %12"
+              }
+            },
+            {13, {
+                   "%7 = OpPhi %6 %8 %4 %13 %5",
+                   "%11 = OpPhi %10 %12 %4 %13 %5",
+                 }
+            },
             {16, {"%17 = OpSLessThan %16 %7 %18"}},
             {17, {"OpBranchConditional %17 %5 %19"}},
             {18, {"%17 = OpSLessThan %16 %7 %18"}},
@@ -732,16 +876,15 @@ INSTANTIATE_TEST_CASE_P(
                 "OpBranchConditional %17 %5 %19",
               }
             },
-            // new uses of %9000
-            {9000, {"%7 = OpPhi %6 %8 %4 %9000 %5"}},
           },
         },
       },
       { // OpPhi defining and referencing the same id.
         "%1 = OpTypeBool "
+        "%3 = OpTypeFunction %1 "
         "%2 = OpConstantTrue %1 "
 
-        "%4 = OpFunction %3 None %5 "
+        "%4 = OpFunction %3 None %1 "
         "%6 = OpLabel "
         "     OpBranch %7 "
         "%7 = OpLabel "
@@ -750,9 +893,10 @@ INSTANTIATE_TEST_CASE_P(
         "     OpFunctionEnd",
         {{8, 2}},
         "%1 = OpTypeBool\n"
+        "%3 = OpTypeFunction %1\n"
         "%2 = OpConstantTrue %1\n"
 
-        "%4 = OpFunction %3 None %5\n"
+        "%4 = OpFunction %3 None %1\n"
         "%6 = OpLabel\n"
              "OpBranch %7\n"
         "%7 = OpLabel\n"
@@ -763,7 +907,8 @@ INSTANTIATE_TEST_CASE_P(
           { // defs
             {1, "%1 = OpTypeBool"},
             {2, "%2 = OpConstantTrue %1"},
-            {4, "%4 = OpFunction %3 None %5"},
+            {3, "%3 = OpTypeFunction %1"},
+            {4, "%4 = OpFunction %3 None %1"},
             {6, "%6 = OpLabel"},
             {7, "%7 = OpLabel"},
             {8, "%8 = OpPhi %1 %2 %7 %2 %6"},
@@ -772,20 +917,18 @@ INSTANTIATE_TEST_CASE_P(
             {1,
               {
                 "%2 = OpConstantTrue %1",
+                "%3 = OpTypeFunction %1",
+                "%4 = OpFunction %3 None %1",
                 "%8 = OpPhi %1 %2 %7 %2 %6",
               }
             },
             {2,
               {
-                // TODO(antiagainst): address this.
-                // We have duplication here because we didn't check existence
-                // before inserting uses.
-                "%8 = OpPhi %1 %2 %7 %2 %6",
+                // Only checking users
                 "%8 = OpPhi %1 %2 %7 %2 %6",
               }
             },
-            {3, {"%4 = OpFunction %3 None %5"}},
-            {5, {"%4 = OpFunction %3 None %5"}},
+            {3, {"%4 = OpFunction %3 None %1"}},
             {6, {"%8 = OpPhi %1 %2 %7 %2 %6"}},
             {7,
               {
@@ -817,7 +960,8 @@ TEST_P(KillDefTest, Case) {
   // Build module.
   const std::vector<const char*> text = {tc.before};
   std::unique_ptr<ir::IRContext> context =
-      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, JoinAllInsts(text));
+      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, JoinAllInsts(text),
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
   ASSERT_NE(nullptr, context);
 
   // Analyze def and use.
@@ -828,7 +972,7 @@ TEST_P(KillDefTest, Case) {
 
   EXPECT_EQ(tc.after, DisassembleModule(context->module()));
   CheckDef(tc.du, context->get_def_use_mgr()->id_to_defs());
-  CheckUse(tc.du, context->get_def_use_mgr()->id_to_uses());
+  CheckUse(tc.du, context->get_def_use_mgr(), context->module()->IdBound());
 }
 
 // clang-format off
@@ -891,6 +1035,14 @@ INSTANTIATE_TEST_CASE_P(
       { // OpPhi.
         kOpPhiTestFunction,
         {9, 11}, // kill one id used by OpPhi, kill one id generated by OpPhi
+         "%1 = OpTypeVoid\n"
+         "%6 = OpTypeInt 32 0\n"
+         "%10 = OpTypeFloat 32\n"
+         "%16 = OpTypeBool\n"
+         "%3 = OpTypeFunction %1\n"
+         "%8 = OpConstant %6 0\n"
+         "%18 = OpConstant %6 1\n"
+         "%12 = OpConstant %10 1\n"
          "%2 = OpFunction %1 None %3\n"
          "%4 = OpLabel\n"
                "OpBranch %5\n"
@@ -899,7 +1051,7 @@ INSTANTIATE_TEST_CASE_P(
          "%7 = OpPhi %6 %8 %4 %9 %5\n"
               "OpNop\n"
               "OpNop\n"
-        "%13 = OpFAdd %10 %11 %15\n"
+        "%13 = OpFAdd %10 %11 %12\n"
         "%17 = OpSLessThan %16 %7 %18\n"
               "OpLoopMerge %19 %5 None\n"
               "OpBranchConditional %17 %5 %19\n"
@@ -909,57 +1061,77 @@ INSTANTIATE_TEST_CASE_P(
               "OpFunctionEnd",
         {
           { // defs. %9 & %11 are killed.
+            {1, "%1 = OpTypeVoid"},
             {2, "%2 = OpFunction %1 None %3"},
+            {3, "%3 = OpTypeFunction %1"},
             {4, "%4 = OpLabel"},
             {5, "%5 = OpLabel"},
+            {6, "%6 = OpTypeInt 32 0"},
             {7, "%7 = OpPhi %6 %8 %4 %9 %5"},
-            {13, "%13 = OpFAdd %10 %11 %15"},
+            {8, "%8 = OpConstant %6 0"},
+            {10, "%10 = OpTypeFloat 32"},
+            {12, "%12 = OpConstant %10 1.0"},
+            {13, "%13 = OpFAdd %10 %11 %12"},
+            {16, "%16 = OpTypeBool"},
             {17, "%17 = OpSLessThan %16 %7 %18"},
+            {18, "%18 = OpConstant %6 1"},
             {19, "%19 = OpLabel"},
           },
           { // uses
-            {1, {"%2 = OpFunction %1 None %3"}},
+            {1,
+              {
+                "%2 = OpFunction %1 None %3",
+                "%3 = OpTypeFunction %1",
+              }
+            },
             {3, {"%2 = OpFunction %1 None %3"}},
             {4,
               {
                 "%7 = OpPhi %6 %8 %4 %9 %5",
-                // "%11 = OpPhi %10 %12 %4 %13 %5",
+                //"%11 = OpPhi %10 %12 %4 %13 %5",
               }
             },
             {5,
               {
                 "OpBranch %5",
                 "%7 = OpPhi %6 %8 %4 %9 %5",
-                // "%11 = OpPhi %10 %12 %4 %13 %5",
+                //"%11 = OpPhi %10 %12 %4 %13 %5",
                 "OpLoopMerge %19 %5 None",
                 "OpBranchConditional %17 %5 %19",
               }
             },
             {6,
               {
+                // Can't properly check constants
+                //"%8 = OpConstant %6 0",
+                //"%18 = OpConstant %6 1",
                 "%7 = OpPhi %6 %8 %4 %9 %5",
-                // "%9 = OpIAdd %6 %7 %14",
+                //"%9 = OpIAdd %6 %7 %8"
               }
             },
-            {7,
+            {7, {"%17 = OpSLessThan %16 %7 %18"}},
+            {8,
               {
-                // "%9 = OpIAdd %6 %7 %14",
-                "%17 = OpSLessThan %16 %7 %18",
+                "%7 = OpPhi %6 %8 %4 %9 %5",
+                //"%9 = OpIAdd %6 %7 %8",
               }
             },
-            {8, {"%7 = OpPhi %6 %8 %4 %9 %5"}},
-            // {9, {"%7 = OpPhi %6 %8 %4 %9 %5"}},
+            // {9, {"%7 = OpPhi %6 %8 %4 %13 %5"}},
             {10,
               {
-                // "%11 = OpPhi %10 %12 %4 %13 %5",
-                "%13 = OpFAdd %10 %11 %15",
+                //"%11 = OpPhi %10 %12 %4 %13 %5",
+                //"%12 = OpConstant %10 1",
+                "%13 = OpFAdd %10 %11 %12"
               }
             },
-            // {11, {"%13 = OpFAdd %10 %11 %15"}},
-            // {12, {"%11 = OpPhi %10 %12 %4 %13 %5"}},
-            // {13, {"%11 = OpPhi %10 %12 %4 %13 %5"}},
-            // {14, {"%9 = OpIAdd %6 %7 %14"}},
-            {15, {"%13 = OpFAdd %10 %11 %15"}},
+            // {11, {"%13 = OpFAdd %10 %11 %12"}},
+            {12,
+              {
+                //"%11 = OpPhi %10 %12 %4 %13 %5",
+                "%13 = OpFAdd %10 %11 %12"
+              }
+            },
+            //{13, {"%11 = OpPhi %10 %12 %4 %13 %5"}},
             {16, {"%17 = OpSLessThan %16 %7 %18"}},
             {17, {"OpBranchConditional %17 %5 %19"}},
             {18, {"%17 = OpSLessThan %16 %7 %18"}},
@@ -974,9 +1146,9 @@ INSTANTIATE_TEST_CASE_P(
       },
       { // OpPhi defining and referencing the same id.
         "%1 = OpTypeBool "
+        "%3 = OpTypeFunction %1 "
         "%2 = OpConstantTrue %1 "
-
-        "%4 = OpFunction %3 None %5 "
+        "%4 = OpFunction %3 None %1 "
         "%6 = OpLabel "
         "     OpBranch %7 "
         "%7 = OpLabel "
@@ -985,9 +1157,10 @@ INSTANTIATE_TEST_CASE_P(
         "     OpFunctionEnd",
         {8},
         "%1 = OpTypeBool\n"
+        "%3 = OpTypeFunction %1\n"
         "%2 = OpConstantTrue %1\n"
 
-        "%4 = OpFunction %3 None %5\n"
+        "%4 = OpFunction %3 None %1\n"
         "%6 = OpLabel\n"
              "OpBranch %7\n"
         "%7 = OpLabel\n"
@@ -998,7 +1171,8 @@ INSTANTIATE_TEST_CASE_P(
           { // defs
             {1, "%1 = OpTypeBool"},
             {2, "%2 = OpConstantTrue %1"},
-            {4, "%4 = OpFunction %3 None %5"},
+            {3, "%3 = OpTypeFunction %1"},
+            {4, "%4 = OpFunction %3 None %1"},
             {6, "%6 = OpLabel"},
             {7, "%7 = OpLabel"},
             // {8, "%8 = OpPhi %1 %8 %7 %2 %6"},
@@ -1007,12 +1181,13 @@ INSTANTIATE_TEST_CASE_P(
             {1,
               {
                 "%2 = OpConstantTrue %1",
+                "%3 = OpTypeFunction %1",
+                "%4 = OpFunction %3 None %1",
                 // "%8 = OpPhi %1 %8 %7 %2 %6",
               }
             },
             // {2, {"%8 = OpPhi %1 %8 %7 %2 %6"}},
-            {3, {"%4 = OpFunction %3 None %5"}},
-            {5, {"%4 = OpFunction %3 None %5"}},
+            {3, {"%4 = OpFunction %3 None %1"}},
             // {6, {"%8 = OpPhi %1 %8 %7 %2 %6"}},
             {7,
               {
@@ -1028,7 +1203,7 @@ INSTANTIATE_TEST_CASE_P(
     })
 );
 // clang-format on
-//
+
 TEST(DefUseTest, OpSwitch) {
   // Because disassembler has basic type check for OpSwitch's selector, we
   // cannot use the DisassembleInst() in the above. Thus, this special spotcheck
@@ -1045,6 +1220,7 @@ TEST(DefUseTest, OpSwitch) {
       //   return v;
       // }
       " %1 = OpTypeInt 64 1 "
+      " %3 = OpTypePointer Input %1 "
       " %2 = OpFunction %1 None %3 "  // %3 is int64(int64)*
       " %4 = OpFunctionParameter %1 "
       " %5 = OpLabel "
@@ -1067,7 +1243,8 @@ TEST(DefUseTest, OpSwitch) {
       "      OpFunctionEnd";
 
   std::unique_ptr<ir::IRContext> context =
-      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, original_text);
+      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, original_text,
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
   ASSERT_NE(nullptr, context);
 
   // Force a re-build of def-use manager.
@@ -1075,19 +1252,20 @@ TEST(DefUseTest, OpSwitch) {
   (void)context->get_def_use_mgr();
 
   // Do a bunch replacements.
-  context->ReplaceAllUsesWith(9, 900);    // to unused id
-  context->ReplaceAllUsesWith(10, 1000);  // to unused id
   context->ReplaceAllUsesWith(11, 7);     // to existing id
+  context->ReplaceAllUsesWith(10, 11);  // to existing id
+  context->ReplaceAllUsesWith(9, 10);    // to existing id
 
   // clang-format off
   const char modified_text[] =
        "%1 = OpTypeInt 64 1\n"
+       "%3 = OpTypePointer Input %1\n"
        "%2 = OpFunction %1 None %3\n" // %3 is int64(int64)*
        "%4 = OpFunctionParameter %1\n"
        "%5 = OpLabel\n"
        "%6 = OpLoad %1 %4\n" // selector value
             "OpSelectionMerge %7 None\n"
-            "OpSwitch %6 %8 1 %900 -4294967296 %1000 9223372036854775807 %7\n" // changed!
+            "OpSwitch %6 %8 1 %10 -4294967296 %11 9223372036854775807 %7\n" // changed!
        "%8 = OpLabel\n"      // default
             "OpBranch %7\n"
        "%9 = OpLabel\n"
@@ -1107,6 +1285,7 @@ TEST(DefUseTest, OpSwitch) {
   def_uses.defs = {
       {1, "%1 = OpTypeInt 64 1"},
       {2, "%2 = OpFunction %1 None %3"},
+      {3, "%3 = OpTypePointer Input %1"},
       {4, "%4 = OpFunctionParameter %1"},
       {5, "%5 = OpLabel"},
       {6, "%6 = OpLoad %1 %4"},
@@ -1119,32 +1298,22 @@ TEST(DefUseTest, OpSwitch) {
   CheckDef(def_uses, context->get_def_use_mgr()->id_to_defs());
 
   {
-    auto* use_list = context->get_def_use_mgr()->GetUses(6);
-    ASSERT_NE(nullptr, use_list);
-    EXPECT_EQ(2u, use_list->size());
-    std::vector<SpvOp> opcodes = {use_list->front().inst->opcode(),
-                                  use_list->back().inst->opcode()};
+    EXPECT_EQ(2u, NumUses(context, 6));
+    std::vector<SpvOp> opcodes = GetUseOpcodes(context, 6u);
     EXPECT_THAT(opcodes, UnorderedElementsAre(SpvOpSwitch, SpvOpReturnValue));
   }
   {
-    auto* use_list = context->get_def_use_mgr()->GetUses(7);
-    ASSERT_NE(nullptr, use_list);
-    EXPECT_EQ(6u, use_list->size());
-    std::vector<SpvOp> opcodes;
-    for (const auto& use : *use_list) {
-      opcodes.push_back(use.inst->opcode());
-    }
+    EXPECT_EQ(6u, NumUses(context, 7));
+    std::vector<SpvOp> opcodes = GetUseOpcodes(context, 7u);
     // OpSwitch is now a user of %7.
     EXPECT_THAT(opcodes, UnorderedElementsAre(SpvOpSelectionMerge, SpvOpBranch,
                                               SpvOpBranch, SpvOpBranch,
                                               SpvOpBranch, SpvOpSwitch));
   }
   // Check all ids only used by OpSwitch after replacement.
-  for (const auto id : {8, 900, 1000}) {
-    auto* use_list = context->get_def_use_mgr()->GetUses(id);
-    ASSERT_NE(nullptr, use_list);
-    EXPECT_EQ(1u, use_list->size());
-    EXPECT_EQ(SpvOpSwitch, use_list->front().inst->opcode());
+  for (const auto id : {8u, 10u, 11u}) {
+    EXPECT_EQ(1u, NumUses(context, id));
+    EXPECT_EQ(SpvOpSwitch, GetUseOpcodes(context, id).back());
   }
 }
 
@@ -1170,7 +1339,8 @@ TEST_P(AnalyzeInstDefUseTest, Case) {
   opt::analysis::DefUseManager manager(context->module());
 
   CheckDef(tc.expected_define_use, manager.id_to_defs());
-  CheckUse(tc.expected_define_use, manager.id_to_uses());
+  CheckUse(tc.expected_define_use, &manager, context->module()->IdBound());
+  //CheckUse(tc.expected_define_use, manager.id_to_uses());
 }
 
 // clang-format off
@@ -1215,6 +1385,7 @@ TEST(AnalyzeInstDefUse, UseWithNoResultId) {
   ir::Instruction branch(&context, SpvOpBranch, 0, 0,
                          {{SPV_OPERAND_TYPE_ID, {2}}});
   manager.AnalyzeInstDefUse(&branch);
+  context.module()->SetIdBound(3);
 
   InstDefUse expected =
   {
@@ -1227,7 +1398,7 @@ TEST(AnalyzeInstDefUse, UseWithNoResultId) {
   };
 
   CheckDef(expected, manager.id_to_defs());
-  CheckUse(expected, manager.id_to_uses());
+  CheckUse(expected, &manager, context.module()->IdBound());
 }
 
 TEST(AnalyzeInstDefUse, AddNewInstruction) {
@@ -1256,7 +1427,7 @@ TEST(AnalyzeInstDefUse, AddNewInstruction) {
   };
 
   CheckDef(expected, manager.id_to_defs());
-  CheckUse(expected, manager.id_to_uses());
+  CheckUse(expected, &manager, context->module()->IdBound());
 }
 
 struct KillInstTestCase {
@@ -1273,7 +1444,8 @@ TEST_P(KillInstTest, Case) {
 
   // Build module.
   std::unique_ptr<ir::IRContext> context =
-      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, tc.before);
+      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, tc.before,
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
   ASSERT_NE(nullptr, context);
 
   // Force a re-build of the def-use manager.
@@ -1281,17 +1453,15 @@ TEST_P(KillInstTest, Case) {
   (void)context->get_def_use_mgr();
 
   // KillInst
-  uint32_t index = 0;
-  context->module()->ForEachInst([&index, &tc, &context](ir::Instruction* inst) {
-    if (tc.indices_for_inst_to_kill.count(index) != 0) {
+  context->module()->ForEachInst([&tc, &context](ir::Instruction* inst) {
+    if (tc.indices_for_inst_to_kill.count(inst->result_id())) {
       context->KillInst(inst);
     }
-    index++;
   });
 
   EXPECT_EQ(tc.after, DisassembleModule(context->module()));
   CheckDef(tc.expected_define_use, context->get_def_use_mgr()->id_to_defs());
-  CheckUse(tc.expected_define_use, context->get_def_use_mgr()->id_to_uses());
+  CheckUse(tc.expected_define_use, context->get_def_use_mgr(), context->module()->IdBound());
 }
 
 // clang-format off
@@ -1300,6 +1470,8 @@ INSTANTIATE_TEST_CASE_P(
     ::testing::ValuesIn(std::vector<KillInstTestCase>{
       // Kill id defining instructions.
       {
+        "%3 = OpTypeVoid "
+        "%1 = OpTypeFunction %3 "
         "%2 = OpFunction %1 None %3 "
         "%4 = OpLabel "
         "     OpBranch %5 "
@@ -1310,26 +1482,39 @@ INSTANTIATE_TEST_CASE_P(
         "%7 = OpLabel "
         "     OpReturn "
         "     OpFunctionEnd",
-        {0, 3, 5, 7},
+        {3, 5, 7},
         "OpNop\n"
+        "%1 = OpTypeFunction %3\n"
+        "%2 = OpFunction %1 None %3\n"
         "%4 = OpLabel\n"
         "OpBranch %5\n"
         "OpNop\n"
         "OpBranch %6\n"
-        "OpNop\n"
+        "%6 = OpLabel\n"
         "OpBranch %4\n"
         "OpNop\n"
         "OpReturn\n"
         "OpFunctionEnd",
         {
           // defs
-          {{4, "%4 = OpLabel"}},
+          {
+            {1, "%1 = OpTypeFunction %3"},
+            {2, "%2 = OpFunction %1 None %3"},
+            {4, "%4 = OpLabel"},
+            {6, "%6 = OpLabel"},
+          },
           // uses
-          {{4, {"OpBranch %4"}}}
+          {
+            {1, {"%2 = OpFunction %1 None %3"}},
+            {4, {"OpBranch %4"}},
+            {6, {"OpBranch %6"}},
+          }
         }
       },
       // Kill instructions that do not have result ids.
       {
+        "%3 = OpTypeVoid "
+        "%1 = OpTypeFunction %3 "
         "%2 = OpFunction %1 None %3 "
         "%4 = OpLabel "
         "     OpBranch %5 "
@@ -1341,11 +1526,13 @@ INSTANTIATE_TEST_CASE_P(
         "     OpReturn "
         "     OpFunctionEnd",
         {2, 4},
-        "%2 = OpFunction %1 None %3\n"
-        "%4 = OpLabel\n"
+        "%3 = OpTypeVoid\n"
+        "%1 = OpTypeFunction %3\n"
              "OpNop\n"
-        "%5 = OpLabel\n"
              "OpNop\n"
+             "OpBranch %5\n"
+        "%5 = OpLabel\n"
+             "OpBranch %6\n"
         "%6 = OpLabel\n"
              "OpBranch %4\n"
         "%7 = OpLabel\n"
@@ -1354,17 +1541,17 @@ INSTANTIATE_TEST_CASE_P(
         {
           // defs
           {
-            {2, "%2 = OpFunction %1 None %3"},
-            {4, "%4 = OpLabel"},
+            {1, "%1 = OpTypeFunction %3"},
+            {3, "%3 = OpTypeVoid"},
             {5, "%5 = OpLabel"},
             {6, "%6 = OpLabel"},
             {7, "%7 = OpLabel"},
           },
           // uses
           {
-            {1, {"%2 = OpFunction %1 None %3"}},
-            {3, {"%2 = OpFunction %1 None %3"}},
-            {4, {"OpBranch %4"}},
+            {3, {"%1 = OpTypeFunction %3"}},
+            {5, {"OpBranch %5"}},
+            {6, {"OpBranch %6"}},
           }
         }
       },
diff --git a/test/opt/ir_context_test.cpp b/test/opt/ir_context_test.cpp
index 770c306..4b5c642 100644
--- a/test/opt/ir_context_test.cpp
+++ b/test/opt/ir_context_test.cpp
@@ -205,4 +205,5 @@ TEST_F(IRContextTest, TakeNextUniqueIdIncrementing) {
   for (uint32_t i = 1; i < NUM_TESTS; ++i)
     EXPECT_EQ(i, localContext.TakeNextUniqueId());
 }
+
 }  // anonymous namespace
diff --git a/test/opt/set_spec_const_default_value_test.cpp b/test/opt/set_spec_const_default_value_test.cpp
index e4edbc3..276d314 100644
--- a/test/opt/set_spec_const_default_value_test.cpp
+++ b/test/opt/set_spec_const_default_value_test.cpp
@@ -464,11 +464,13 @@ INSTANTIATE_TEST_CASE_P(
         {
             // code
             "OpDecorate %1 SpecId 100\n"
+            "%1 = OpDecorationGroup\n"
             "%int = OpTypeInt 32 1\n",
             // default values
             SpecIdToValueStrMap{{100, "0x7fffffff"}},
             // expected
             "OpDecorate %1 SpecId 100\n"
+            "%1 = OpDecorationGroup\n"
             "%int = OpTypeInt 32 1\n",
         },
         // 2. Do nothing when SpecId decoration is not attached to a
@@ -476,12 +478,14 @@ INSTANTIATE_TEST_CASE_P(
         {
             // code
             "OpDecorate %1 SpecId 100\n"
+            "%1 = OpDecorationGroup\n"
             "%int = OpTypeInt 32 1\n"
             "%int_101 = OpConstant %int 101\n",
             // default values
             SpecIdToValueStrMap{{100, "0x7fffffff"}},
             // expected
             "OpDecorate %1 SpecId 100\n"
+            "%1 = OpDecorationGroup\n"
             "%int = OpTypeInt 32 1\n"
             "%int_101 = OpConstant %int 101\n",
         },
@@ -529,6 +533,7 @@ INSTANTIATE_TEST_CASE_P(
             // code
             "OpDecorate %1 SpecId 100\n"
             "%1 = OpDecorationGroup\n"
+            "%2 = OpDecorationGroup\n"
             "OpGroupDecorate %1 %2\n"
             "%int = OpTypeInt 32 1\n"
             "%int_100 = OpConstant %int 100\n",
@@ -537,6 +542,7 @@ INSTANTIATE_TEST_CASE_P(
             // expected
             "OpDecorate %1 SpecId 100\n"
             "%1 = OpDecorationGroup\n"
+            "%2 = OpDecorationGroup\n"
             "OpGroupDecorate %1 %2\n"
             "%int = OpTypeInt 32 1\n"
             "%int_100 = OpConstant %int 100\n",
@@ -950,11 +956,13 @@ INSTANTIATE_TEST_CASE_P(
         {
             // code
             "OpDecorate %1 SpecId 100\n"
+            "%1 = OpDecorationGroup\n"
             "%int = OpTypeInt 32 1\n",
             // default values
             SpecIdToValueBitPatternMap{{100, {0x7fffffff}}},
             // expected
             "OpDecorate %1 SpecId 100\n"
+            "%1 = OpDecorationGroup\n"
             "%int = OpTypeInt 32 1\n",
         },
         // 2. Do nothing when SpecId decoration is not attached to a
@@ -962,12 +970,14 @@ INSTANTIATE_TEST_CASE_P(
         {
             // code
             "OpDecorate %1 SpecId 100\n"
+            "%1 = OpDecorationGroup\n"
             "%int = OpTypeInt 32 1\n"
             "%int_101 = OpConstant %int 101\n",
             // default values
             SpecIdToValueBitPatternMap{{100, {0x7fffffff}}},
             // expected
             "OpDecorate %1 SpecId 100\n"
+            "%1 = OpDecorationGroup\n"
             "%int = OpTypeInt 32 1\n"
             "%int_101 = OpConstant %int 101\n",
         },
@@ -1015,6 +1025,7 @@ INSTANTIATE_TEST_CASE_P(
             // code
             "OpDecorate %1 SpecId 100\n"
             "%1 = OpDecorationGroup\n"
+            "%2 = OpDecorationGroup\n"
             "OpGroupDecorate %1 %2\n"
             "%int = OpTypeInt 32 1\n"
             "%int_100 = OpConstant %int 100\n",
@@ -1023,6 +1034,7 @@ INSTANTIATE_TEST_CASE_P(
             // expected
             "OpDecorate %1 SpecId 100\n"
             "%1 = OpDecorationGroup\n"
+            "%2 = OpDecorationGroup\n"
             "OpGroupDecorate %1 %2\n"
             "%int = OpTypeInt 32 1\n"
             "%int_100 = OpConstant %int 100\n",
-- 
2.7.4