Add passes to eliminate dead output stores (#4970)

This adds two passes to accomplish this: one pass to analyze a shader
to determine the input slots that are live. The second pass is run on
the preceding shader to eliminate any stores to output slots that are
not consumed by the following shader.

These passes support vert, tesc, tese, geom, and frag shaders.

These passes are currently only available through the API.

These passes together with dead code elimination, and elimination of
dead input and output components and variables (WIP), will allow users
to do dead code elimination across shader boundaries.

18 files changed, 2817 insertions, 2 deletions

diff --git a/Android.mk b/Android.mk
index 80c61b080..3a28b6630 100644
--- a/Android.mk
+++ b/Android.mk
@@ -78,6 +78,7 @@ SPVTOOLS_SRC_FILES := \
 SPVTOOLS_OPT_SRC_FILES := \
 		source/opt/aggressive_dead_code_elim_pass.cpp \
 		source/opt/amd_ext_to_khr.cpp \
+		source/opt/analyze_live_input_pass.cpp \
 		source/opt/basic_block.cpp \
 		source/opt/block_merge_pass.cpp \
 		source/opt/block_merge_util.cpp \
@@ -111,6 +112,7 @@ SPVTOOLS_OPT_SRC_FILES := \
 		source/opt/eliminate_dead_functions_util.cpp \
 		source/opt/eliminate_dead_input_components_pass.cpp \
 		source/opt/eliminate_dead_members_pass.cpp \
+		source/opt/eliminate_dead_output_stores_pass.cpp \
 		source/opt/feature_manager.cpp \
 		source/opt/fix_func_call_arguments.cpp \
 		source/opt/fix_storage_class.cpp \
@@ -136,6 +138,7 @@ SPVTOOLS_OPT_SRC_FILES := \
 		source/opt/ir_context.cpp \
 		source/opt/ir_loader.cpp \
 		source/opt/licm_pass.cpp \
+		source/opt/liveness.cpp \
 		source/opt/local_access_chain_convert_pass.cpp \
 		source/opt/local_redundancy_elimination.cpp \
 		source/opt/local_single_block_elim_pass.cpp \
diff --git a/BUILD.gn b/BUILD.gn
index b7e20b343..e4c14f2a7 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -562,6 +562,8 @@ static_library("spvtools_opt") {
     "source/opt/aggressive_dead_code_elim_pass.h",
     "source/opt/amd_ext_to_khr.cpp",
     "source/opt/amd_ext_to_khr.h",
+    "source/opt/analyze_live_input_pass.cpp",
+    "source/opt/analyze_live_input_pass.h",
     "source/opt/basic_block.cpp",
     "source/opt/basic_block.h",
     "source/opt/block_merge_pass.cpp",
@@ -628,6 +630,8 @@ static_library("spvtools_opt") {
     "source/opt/eliminate_dead_input_components_pass.h",
     "source/opt/eliminate_dead_members_pass.cpp",
     "source/opt/eliminate_dead_members_pass.h",
+    "source/opt/eliminate_dead_output_stores_pass.cpp",
+    "source/opt/eliminate_dead_output_stores_pass.h",
     "source/opt/empty_pass.h",
     "source/opt/feature_manager.cpp",
     "source/opt/feature_manager.h",
@@ -681,6 +685,8 @@ static_library("spvtools_opt") {
     "source/opt/iterator.h",
     "source/opt/licm_pass.cpp",
     "source/opt/licm_pass.h",
+    "source/opt/liveness.cpp",
+    "source/opt/liveness.h",
     "source/opt/local_access_chain_convert_pass.cpp",
     "source/opt/local_access_chain_convert_pass.h",
     "source/opt/local_redundancy_elimination.cpp",
diff --git a/include/spirv-tools/optimizer.hpp b/include/spirv-tools/optimizer.hpp
index 949735608..bca12520f 100644
--- a/include/spirv-tools/optimizer.hpp
+++ b/include/spirv-tools/optimizer.hpp
@@ -19,6 +19,7 @@
 #include <ostream>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <utility>
 #include <vector>
 
@@ -893,6 +894,26 @@ Optimizer::PassToken CreateInterpolateFixupPass();
 // types.
 Optimizer::PassToken CreateEliminateDeadInputComponentsPass();
 
+// Analyzes shader and populates |live_locs| and |live_builtins|. Best results
+// will be obtained if shader has all dead code eliminated first. |live_locs|
+// and |live_builtins| are subsequently used when calling
+// CreateEliminateDeadOutputStoresPass on the preceding shader. Currently only
+// supports tesc, tese, geom, and frag shaders.
+Optimizer::PassToken CreateAnalyzeLiveInputPass(
+    std::unordered_set<uint32_t>* live_locs,
+    std::unordered_set<uint32_t>* live_builtins);
+
+// Removes stores to output locations not listed in |live_locs| or
+// |live_builtins|. Best results are obtained if constant propagation is
+// performed first. A subsequent call to ADCE will eliminate any dead code
+// created by the removal of the stores. A subsequent call to
+// CreateEliminateDeadOutputComponentsPass will eliminate any dead output
+// components created by the elimination of the stores. Currently only supports
+// vert, tesc, tese, and geom shaders.
+Optimizer::PassToken CreateEliminateDeadOutputStoresPass(
+    std::unordered_set<uint32_t>* live_locs,
+    std::unordered_set<uint32_t>* live_builtins);
+
 // Creates a convert-to-sampled-image pass to convert images and/or
 // samplers with given pairs of descriptor set and binding to sampled image.
 // If a pair of an image and a sampler have the same pair of descriptor set and
diff --git a/source/opt/CMakeLists.txt b/source/opt/CMakeLists.txt
index 75fe4c0fd..085c4302a 100644
--- a/source/opt/CMakeLists.txt
+++ b/source/opt/CMakeLists.txt
@@ -15,6 +15,7 @@ set(SPIRV_TOOLS_OPT_SOURCES
   fix_func_call_arguments.h
   aggressive_dead_code_elim_pass.h
   amd_ext_to_khr.h
+  analyze_live_input_pass.h
   basic_block.h
   block_merge_pass.h
   block_merge_util.h
@@ -48,6 +49,7 @@ set(SPIRV_TOOLS_OPT_SOURCES
   eliminate_dead_functions_util.h
   eliminate_dead_input_components_pass.h
   eliminate_dead_members_pass.h
+  eliminate_dead_output_stores_pass.h
   empty_pass.h
   feature_manager.h
   fix_storage_class.h
@@ -74,6 +76,7 @@ set(SPIRV_TOOLS_OPT_SOURCES
   ir_context.h
   ir_loader.h
   licm_pass.h
+  liveness.h
   local_access_chain_convert_pass.h
   local_redundancy_elimination.h
   local_single_block_elim_pass.h
@@ -131,6 +134,7 @@ set(SPIRV_TOOLS_OPT_SOURCES
   fix_func_call_arguments.cpp
   aggressive_dead_code_elim_pass.cpp
   amd_ext_to_khr.cpp
+  analyze_live_input_pass.cpp
   basic_block.cpp
   block_merge_pass.cpp
   block_merge_util.cpp
@@ -164,6 +168,7 @@ set(SPIRV_TOOLS_OPT_SOURCES
   eliminate_dead_functions_util.cpp
   eliminate_dead_input_components_pass.cpp
   eliminate_dead_members_pass.cpp
+  eliminate_dead_output_stores_pass.cpp
   feature_manager.cpp
   fix_storage_class.cpp
   flatten_decoration_pass.cpp
@@ -188,6 +193,7 @@ set(SPIRV_TOOLS_OPT_SOURCES
   ir_context.cpp
   ir_loader.cpp
   licm_pass.cpp
+  liveness.cpp
   local_access_chain_convert_pass.cpp
   local_redundancy_elimination.cpp
   local_single_block_elim_pass.cpp
diff --git a/source/opt/analyze_live_input_pass.cpp b/source/opt/analyze_live_input_pass.cpp
new file mode 100644
index 000000000..f54206f08
--- /dev/null
+++ b/source/opt/analyze_live_input_pass.cpp
@@ -0,0 +1,45 @@
+// Copyright (c) 2022 The Khronos Group Inc.
+// Copyright (c) 2022 LunarG Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/opt/analyze_live_input_pass.h"
+
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace opt {
+
+Pass::Status AnalyzeLiveInputPass::Process() {
+  // Current functionality assumes shader capability
+  if (!context()->get_feature_mgr()->HasCapability(SpvCapabilityShader))
+    return Status::SuccessWithoutChange;
+  Pass::Status status = DoLiveInputAnalysis();
+  return status;
+}
+
+Pass::Status AnalyzeLiveInputPass::DoLiveInputAnalysis() {
+  // Current functionality only supports frag, tesc, tese or geom shaders.
+  // Report failure for any other stage.
+  auto stage = context()->GetStage();
+  if (stage != SpvExecutionModelFragment &&
+      stage != SpvExecutionModelTessellationControl &&
+      stage != SpvExecutionModelTessellationEvaluation &&
+      stage != SpvExecutionModelGeometry)
+    return Status::Failure;
+  context()->get_liveness_mgr()->GetLiveness(live_locs_, live_builtins_);
+  return Status::SuccessWithoutChange;
+}
+
+}  // namespace opt
+}  // namespace spvtools
diff --git a/source/opt/analyze_live_input_pass.h b/source/opt/analyze_live_input_pass.h
new file mode 100644
index 000000000..ab292effe
--- /dev/null
+++ b/source/opt/analyze_live_input_pass.h
@@ -0,0 +1,57 @@
+// Copyright (c) 2022 The Khronos Group Inc.
+// Copyright (c) 2022 LunarG Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SOURCE_OPT_ANALYZE_LIVE_INPUT_H_
+#define SOURCE_OPT_ANALYZE_LIVE_INPUT_H_
+
+#include <unordered_set>
+
+#include "source/opt/pass.h"
+
+namespace spvtools {
+namespace opt {
+
+// See optimizer.hpp for documentation.
+class AnalyzeLiveInputPass : public Pass {
+ public:
+  explicit AnalyzeLiveInputPass(std::unordered_set<uint32_t>* live_locs,
+                                std::unordered_set<uint32_t>* live_builtins)
+      : live_locs_(live_locs), live_builtins_(live_builtins) {}
+
+  const char* name() const override { return "analyze-live-input"; }
+  Status Process() override;
+
+  // Return the mask of preserved Analyses.
+  IRContext::Analysis GetPreservedAnalyses() override {
+    return IRContext::kAnalysisDefUse |
+           IRContext::kAnalysisInstrToBlockMapping |
+           IRContext::kAnalysisCombinators | IRContext::kAnalysisCFG |
+           IRContext::kAnalysisDominatorAnalysis |
+           IRContext::kAnalysisLoopAnalysis | IRContext::kAnalysisNameMap |
+           IRContext::kAnalysisConstants | IRContext::kAnalysisTypes;
+  }
+
+ private:
+  // Do live input analysis
+  Status DoLiveInputAnalysis();
+
+  std::unordered_set<uint32_t>* live_locs_;
+  std::unordered_set<uint32_t>* live_builtins_;
+};
+
+}  // namespace opt
+}  // namespace spvtools
+
+#endif  // SOURCE_OPT_ANALYZE_LIVE_INPUT_H_
diff --git a/source/opt/eliminate_dead_output_stores_pass.cpp b/source/opt/eliminate_dead_output_stores_pass.cpp
new file mode 100644
index 000000000..9378898fd
--- /dev/null
+++ b/source/opt/eliminate_dead_output_stores_pass.cpp
@@ -0,0 +1,231 @@
+// Copyright (c) 2022 The Khronos Group Inc.
+// Copyright (c) 2022 LunarG Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/opt/eliminate_dead_output_stores_pass.h"
+
+#include "source/opt/instruction.h"
+#include "source/opt/ir_context.h"
+
+namespace {
+
+const uint32_t kDecorationLocationInIdx = 2;
+const uint32_t kOpDecorateMemberMemberInIdx = 1;
+const uint32_t kOpDecorateBuiltInLiteralInIdx = 2;
+const uint32_t kOpDecorateMemberBuiltInLiteralInIdx = 3;
+const uint32_t kOpAccessChainIdx0InIdx = 1;
+const uint32_t kOpConstantValueInIdx = 0;
+
+}  // namespace
+
+namespace spvtools {
+namespace opt {
+
+Pass::Status EliminateDeadOutputStoresPass::Process() {
+  // Current functionality assumes shader capability
+  if (!context()->get_feature_mgr()->HasCapability(SpvCapabilityShader))
+    return Status::SuccessWithoutChange;
+  Pass::Status status = DoDeadOutputStoreElimination();
+  return status;
+}
+
+void EliminateDeadOutputStoresPass::InitializeElimination() {
+  kill_list_.clear();
+}
+
+bool EliminateDeadOutputStoresPass::IsLiveBuiltin(uint32_t bi) {
+  return live_builtins_->find(bi) != live_builtins_->end();
+}
+
+bool EliminateDeadOutputStoresPass::AnyLocsAreLive(uint32_t start,
+                                                   uint32_t count) {
+  auto finish = start + count;
+  for (uint32_t u = start; u < finish; ++u) {
+    if (live_locs_->find(u) != live_locs_->end()) return true;
+  }
+  return false;
+}
+
+void EliminateDeadOutputStoresPass::KillAllStoresOfRef(Instruction* ref) {
+  analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
+  if (ref->opcode() == SpvOpStore) {
+    kill_list_.push_back(ref);
+    return;
+  }
+  assert((ref->opcode() == SpvOpAccessChain ||
+          ref->opcode() == SpvOpInBoundsAccessChain) &&
+         "unexpected use of output variable");
+  def_use_mgr->ForEachUser(ref, [this](Instruction* user) {
+    if (user->opcode() == SpvOpStore) kill_list_.push_back(user);
+  });
+}
+
+void EliminateDeadOutputStoresPass::KillAllDeadStoresOfLocRef(
+    Instruction* ref, Instruction* var) {
+  analysis::TypeManager* type_mgr = context()->get_type_mgr();
+  analysis::DecorationManager* deco_mgr = context()->get_decoration_mgr();
+  analysis::LivenessManager* live_mgr = context()->get_liveness_mgr();
+  // Find variable location if present.
+  uint32_t start_loc = 0;
+  auto var_id = var->result_id();
+  bool no_loc = deco_mgr->WhileEachDecoration(
+      var_id, SpvDecorationLocation, [&start_loc](const Instruction& deco) {
+        assert(deco.opcode() == SpvOpDecorate && "unexpected decoration");
+        start_loc = deco.GetSingleWordInOperand(kDecorationLocationInIdx);
+        return false;
+      });
+  // Find patch decoration if present
+  bool is_patch = !deco_mgr->WhileEachDecoration(
+      var_id, SpvDecorationPatch, [](const Instruction& deco) {
+        if (deco.opcode() != SpvOpDecorate)
+          assert(false && "unexpected decoration");
+        return false;
+      });
+  // Compute offset and final type of reference. If no location found
+  // or any stored locations are live, return without removing stores.
+  auto ptr_type = type_mgr->GetType(var->type_id())->AsPointer();
+  assert(ptr_type && "unexpected var type");
+  auto var_type = ptr_type->pointee_type();
+  uint32_t ref_loc = start_loc;
+  auto curr_type = var_type;
+  if (ref->opcode() == SpvOpAccessChain ||
+      ref->opcode() == SpvOpInBoundsAccessChain)
+    live_mgr->AnalyzeAccessChainLoc(ref, &curr_type, &ref_loc, &no_loc,
+                                    is_patch, /* input */ false);
+  if (no_loc || AnyLocsAreLive(ref_loc, live_mgr->GetLocSize(curr_type)))
+    return;
+  // Kill all stores based on this reference
+  KillAllStoresOfRef(ref);
+}
+
+void EliminateDeadOutputStoresPass::KillAllDeadStoresOfBuiltinRef(
+    Instruction* ref, Instruction* var) {
+  auto deco_mgr = context()->get_decoration_mgr();
+  auto def_use_mgr = context()->get_def_use_mgr();
+  auto type_mgr = context()->get_type_mgr();
+  auto live_mgr = context()->get_liveness_mgr();
+  // Search for builtin decoration of base variable
+  uint32_t builtin = SpvBuiltInMax;
+  auto var_id = var->result_id();
+  (void)deco_mgr->WhileEachDecoration(
+      var_id, SpvDecorationBuiltIn, [&builtin](const Instruction& deco) {
+        assert(deco.opcode() == SpvOpDecorate && "unexpected decoration");
+        builtin = deco.GetSingleWordInOperand(kOpDecorateBuiltInLiteralInIdx);
+        return false;
+      });
+  // If analyzed builtin and not live, kill stores.
+  if (builtin != SpvBuiltInMax) {
+    if (live_mgr->IsAnalyzedBuiltin(builtin) && !IsLiveBuiltin(builtin))
+      KillAllStoresOfRef(ref);
+    return;
+  }
+  // Search for builtin decoration on indexed member
+  auto ref_op = ref->opcode();
+  if (ref_op != SpvOpAccessChain && ref_op != SpvOpInBoundsAccessChain) return;
+  uint32_t in_idx = kOpAccessChainIdx0InIdx;
+  analysis::Type* var_type = type_mgr->GetType(var->type_id());
+  analysis::Pointer* ptr_type = var_type->AsPointer();
+  auto curr_type = ptr_type->pointee_type();
+  auto arr_type = curr_type->AsArray();
+  if (arr_type) {
+    curr_type = arr_type->element_type();
+    ++in_idx;
+  }
+  auto str_type = curr_type->AsStruct();
+  auto str_type_id = type_mgr->GetId(str_type);
+  auto member_idx_id = ref->GetSingleWordInOperand(in_idx);
+  auto member_idx_inst = def_use_mgr->GetDef(member_idx_id);
+  assert(member_idx_inst->opcode() == SpvOpConstant &&
+         "unexpected non-constant index");
+  auto ac_idx = member_idx_inst->GetSingleWordInOperand(kOpConstantValueInIdx);
+  (void)deco_mgr->WhileEachDecoration(
+      str_type_id, SpvDecorationBuiltIn,
+      [ac_idx, &builtin](const Instruction& deco) {
+        assert(deco.opcode() == SpvOpMemberDecorate && "unexpected decoration");
+        auto deco_idx =
+            deco.GetSingleWordInOperand(kOpDecorateMemberMemberInIdx);
+        if (deco_idx == ac_idx) {
+          builtin =
+              deco.GetSingleWordInOperand(kOpDecorateMemberBuiltInLiteralInIdx);
+          return false;
+        }
+        return true;
+      });
+  assert(builtin != SpvBuiltInMax && "builtin not found");
+  // If analyzed builtin and not live, kill stores.
+  if (live_mgr->IsAnalyzedBuiltin(builtin) && !IsLiveBuiltin(builtin))
+    KillAllStoresOfRef(ref);
+}
+
+Pass::Status EliminateDeadOutputStoresPass::DoDeadOutputStoreElimination() {
+  // Current implementation only supports vert, tesc, tese, geom shaders
+  auto stage = context()->GetStage();
+  if (stage != SpvExecutionModelVertex &&
+      stage != SpvExecutionModelTessellationControl &&
+      stage != SpvExecutionModelTessellationEvaluation &&
+      stage != SpvExecutionModelGeometry)
+    return Status::Failure;
+  InitializeElimination();
+  analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
+  analysis::TypeManager* type_mgr = context()->get_type_mgr();
+  analysis::DecorationManager* deco_mgr = context()->get_decoration_mgr();
+  // Process all output variables
+  for (auto& var : context()->types_values()) {
+    if (var.opcode() != SpvOpVariable) {
+      continue;
+    }
+    analysis::Type* var_type = type_mgr->GetType(var.type_id());
+    analysis::Pointer* ptr_type = var_type->AsPointer();
+    if (ptr_type->storage_class() != SpvStorageClassOutput) {
+      continue;
+    }
+    // If builtin decoration on variable, process as builtin.
+    auto var_id = var.result_id();
+    bool is_builtin = false;
+    if (deco_mgr->HasDecoration(var_id, SpvDecorationBuiltIn)) {
+      is_builtin = true;
+    } else {
+      // If interface block with builtin members, process as builtin.
+      // Strip off outer array type if present.
+      auto curr_type = ptr_type->pointee_type();
+      auto arr_type = curr_type->AsArray();
+      if (arr_type) curr_type = arr_type->element_type();
+      auto str_type = curr_type->AsStruct();
+      if (str_type) {
+        auto str_type_id = type_mgr->GetId(str_type);
+        if (deco_mgr->HasDecoration(str_type_id, SpvDecorationBuiltIn))
+          is_builtin = true;
+      }
+    }
+    // For each store or access chain using var, if dead builtin or all its
+    // locations are dead, kill store or all access chain's stores
+    def_use_mgr->ForEachUser(
+        var_id, [this, &var, is_builtin](Instruction* user) {
+          auto op = user->opcode();
+          if (op == SpvOpEntryPoint || op == SpvOpName || op == SpvOpDecorate)
+            return;
+          if (is_builtin)
+            KillAllDeadStoresOfBuiltinRef(user, &var);
+          else
+            KillAllDeadStoresOfLocRef(user, &var);
+        });
+  }
+  for (auto& kinst : kill_list_) context()->KillInst(kinst);
+
+  return kill_list_.empty() ? Status::SuccessWithoutChange
+                            : Status::SuccessWithChange;
+}
+
+}  // namespace opt
+}  // namespace spvtools
diff --git a/source/opt/eliminate_dead_output_stores_pass.h b/source/opt/eliminate_dead_output_stores_pass.h
new file mode 100644
index 000000000..13785f349
--- /dev/null
+++ b/source/opt/eliminate_dead_output_stores_pass.h
@@ -0,0 +1,87 @@
+// Copyright (c) 2022 The Khronos Group Inc.
+// Copyright (c) 2022 LunarG Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SOURCE_OPT_ELIMINATE_DEAD_OUTPUT_STORES_H_
+#define SOURCE_OPT_ELIMINATE_DEAD_OUTPUT_STORES_H_
+
+#include <unordered_set>
+
+#include "source/opt/ir_context.h"
+#include "source/opt/module.h"
+#include "source/opt/pass.h"
+
+namespace spvtools {
+namespace opt {
+
+// See optimizer.hpp for documentation.
+class EliminateDeadOutputStoresPass : public Pass {
+ public:
+  explicit EliminateDeadOutputStoresPass(
+      std::unordered_set<uint32_t>* live_locs,
+      std::unordered_set<uint32_t>* live_builtins)
+      : live_locs_(live_locs), live_builtins_(live_builtins) {}
+
+  const char* name() const override { return "eliminate-dead-output-stores"; }
+  Status Process() override;
+
+  // Return the mask of preserved Analyses.
+  IRContext::Analysis GetPreservedAnalyses() override {
+    return IRContext::kAnalysisDefUse |
+           IRContext::kAnalysisInstrToBlockMapping |
+           IRContext::kAnalysisCombinators | IRContext::kAnalysisCFG |
+           IRContext::kAnalysisDominatorAnalysis |
+           IRContext::kAnalysisLoopAnalysis | IRContext::kAnalysisNameMap |
+           IRContext::kAnalysisConstants | IRContext::kAnalysisTypes;
+  }
+
+ private:
+  // Initialize elimination
+  void InitializeElimination();
+
+  // Do dead output store analysis
+  Status DoDeadOutputStoreAnalysis();
+
+  // Do dead output store analysis
+  Status DoDeadOutputStoreElimination();
+
+  // Mark all locations live
+  void MarkAllLocsLive();
+
+  // Kill all stores resulting from |ref|.
+  void KillAllStoresOfRef(Instruction* ref);
+
+  // Kill all dead stores resulting from |user| of loc-based |var|.
+  void KillAllDeadStoresOfLocRef(Instruction* user, Instruction* var);
+
+  // Kill all dead stores resulting from |user| of builtin |var|.
+  void KillAllDeadStoresOfBuiltinRef(Instruction* user, Instruction* var);
+
+  // Return true if any of |count| locations starting at location |start| are
+  // live.
+  bool AnyLocsAreLive(uint32_t start, uint32_t count);
+
+  // Return true if builtin |bi| is live.
+  bool IsLiveBuiltin(uint32_t bi);
+
+  std::unordered_set<uint32_t>* live_locs_;
+  std::unordered_set<uint32_t>* live_builtins_;
+
+  std::vector<Instruction*> kill_list_;
+};
+
+}  // namespace opt
+}  // namespace spvtools
+
+#endif  // SOURCE_OPT_ELIMINATE_DEAD_OUTPUT_STORES_H_
diff --git a/source/opt/ir_context.cpp b/source/opt/ir_context.cpp
index c9c3f1b5d..9116d4b26 100644
--- a/source/opt/ir_context.cpp
+++ b/source/opt/ir_context.cpp
@@ -29,6 +29,7 @@ static const int kSpvDecorateDecorationInIdx = 1;
 static const int kSpvDecorateBuiltinInIdx = 2;
 static const int kEntryPointInterfaceInIdx = 3;
 static const int kEntryPointFunctionIdInIdx = 1;
+static const int kEntryPointExecutionModelInIdx = 0;
 
 // Constants for OpenCL.DebugInfo.100 / NonSemantic.Shader.DebugInfo.100
 // extension instructions.
@@ -152,6 +153,9 @@ void IRContext::InvalidateAnalyses(IRContext::Analysis analyses_to_invalidate) {
   if (analyses_to_invalidate & kAnalysisConstants) {
     constant_mgr_.reset(nullptr);
   }
+  if (analyses_to_invalidate & kAnalysisLiveness) {
+    liveness_mgr_.reset(nullptr);
+  }
   if (analyses_to_invalidate & kAnalysisTypes) {
     type_mgr_.reset(nullptr);
   }
@@ -1058,5 +1062,26 @@ bool IRContext::IsReachable(const opt::BasicBlock& bb) {
   return GetDominatorAnalysis(enclosing_function)
       ->Dominates(enclosing_function->entry().get(), &bb);
 }
+
+SpvExecutionModel IRContext::GetStage() {
+  const auto& entry_points = module()->entry_points();
+  if (entry_points.empty()) {
+    return SpvExecutionModelMax;
+  }
+
+  uint32_t stage = entry_points.begin()->GetSingleWordInOperand(
+      kEntryPointExecutionModelInIdx);
+  auto it = std::find_if(
+      entry_points.begin(), entry_points.end(), [stage](const Instruction& x) {
+        return x.GetSingleWordInOperand(kEntryPointExecutionModelInIdx) !=
+               stage;
+      });
+  if (it != entry_points.end()) {
+    EmitErrorMessage("Mixed stage shader module not supported", &(*it));
+  }
+
+  return static_cast<SpvExecutionModel>(stage);
+}
+
 }  // namespace opt
 }  // namespace spvtools
diff --git a/source/opt/ir_context.h b/source/opt/ir_context.h
index 2f27942b4..9dee84e9b 100644
--- a/source/opt/ir_context.h
+++ b/source/opt/ir_context.h
@@ -35,6 +35,7 @@
 #include "source/opt/dominator_analysis.h"
 #include "source/opt/feature_manager.h"
 #include "source/opt/fold.h"
+#include "source/opt/liveness.h"
 #include "source/opt/loop_descriptor.h"
 #include "source/opt/module.h"
 #include "source/opt/register_pressure.h"
@@ -81,6 +82,7 @@ class IRContext {
     kAnalysisConstants = 1 << 14,
     kAnalysisTypes = 1 << 15,
     kAnalysisDebugInfo = 1 << 16,
+    kAnalysisLiveness = 1 << 17,
     kAnalysisEnd = 1 << 17
   };
 
@@ -248,6 +250,15 @@ class IRContext {
     return def_use_mgr_.get();
   }
 
+  // Returns a pointer to a liveness manager.  If the liveness manager is
+  // invalid, it is rebuilt first.
+  analysis::LivenessManager* get_liveness_mgr() {
+    if (!AreAnalysesValid(kAnalysisLiveness)) {
+      BuildLivenessManager();
+    }
+    return liveness_mgr_.get();
+  }
+
   // Returns a pointer to a value number table.  If the liveness analysis is
   // invalid, it is rebuilt first.
   ValueNumberTable* GetValueNumberTable() {
@@ -625,6 +636,10 @@ class IRContext {
   // the function that contains |bb|.
   bool IsReachable(const opt::BasicBlock& bb);
 
+  // Return the stage of the module. Will generate error if entry points don't
+  // all have the same stage.
+  SpvExecutionModel GetStage();
+
  private:
   // Builds the def-use manager from scratch, even if it was already valid.
   void BuildDefUseManager() {
@@ -632,6 +647,12 @@ class IRContext {
     valid_analyses_ = valid_analyses_ | kAnalysisDefUse;
   }
 
+  // Builds the liveness manager from scratch, even if it was already valid.
+  void BuildLivenessManager() {
+    liveness_mgr_ = MakeUnique<analysis::LivenessManager>(this);
+    valid_analyses_ = valid_analyses_ | kAnalysisLiveness;
+  }
+
   // Builds the instruction-block map for the whole module.
   void BuildInstrToBlockMapping() {
     instr_to_block_.clear();
@@ -852,6 +873,9 @@ class IRContext {
 
   std::unique_ptr<StructuredCFGAnalysis> struct_cfg_analysis_;
 
+  // The liveness manager for |module_|.
+  std::unique_ptr<analysis::LivenessManager> liveness_mgr_;
+
   // The maximum legal value for the id bound.
   uint32_t max_id_bound_;
 
diff --git a/source/opt/liveness.cpp b/source/opt/liveness.cpp
new file mode 100644
index 000000000..08b1c6ebc
--- /dev/null
+++ b/source/opt/liveness.cpp
@@ -0,0 +1,330 @@
+// Copyright (c) 2022 The Khronos Group Inc.
+// Copyright (c) 2022 LunarG Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/opt/liveness.h"
+
+#include "source/opt/ir_context.h"
+
+namespace {
+
+const uint32_t kDecorationLocationInIdx = 2;
+const uint32_t kOpDecorateMemberMemberInIdx = 1;
+const uint32_t kOpDecorateMemberLocationInIdx = 3;
+const uint32_t kOpDecorateBuiltInLiteralInIdx = 2;
+const uint32_t kOpDecorateMemberBuiltInLiteralInIdx = 3;
+
+}  // namespace
+
+namespace spvtools {
+namespace opt {
+namespace analysis {
+
+LivenessManager::LivenessManager(IRContext* ctx) : ctx_(ctx), computed_(false) {
+  // Liveness sets computed when queried
+}
+
+void LivenessManager::InitializeAnalysis() {
+  live_locs_.clear();
+  live_builtins_.clear();
+  // Mark all builtins live for frag shader.
+  if (context()->GetStage() == SpvExecutionModelFragment) {
+    live_builtins_.insert(SpvBuiltInPointSize);
+    live_builtins_.insert(SpvBuiltInClipDistance);
+    live_builtins_.insert(SpvBuiltInCullDistance);
+  }
+}
+
+bool LivenessManager::IsAnalyzedBuiltin(uint32_t bi) {
+  // There are only three builtins that can be analyzed and removed between
+  // two stages: PointSize, ClipDistance and CullDistance. All others are
+  // always consumed implicitly by the downstream stage.
+  return bi == SpvBuiltInPointSize || bi == SpvBuiltInClipDistance ||
+         bi == SpvBuiltInCullDistance;
+}
+
+bool LivenessManager::AnalyzeBuiltIn(uint32_t id) {
+  auto deco_mgr = context()->get_decoration_mgr();
+  bool saw_builtin = false;
+  // Analyze all builtin decorations of |id|.
+  (void)deco_mgr->ForEachDecoration(
+      id, SpvDecorationBuiltIn,
+      [this, &saw_builtin](const Instruction& deco_inst) {
+        saw_builtin = true;
+        // No need to process builtins in frag shader. All assumed used.
+        if (context()->GetStage() == SpvExecutionModelFragment) return;
+        uint32_t builtin = SpvBuiltInMax;
+        if (deco_inst.opcode() == SpvOpDecorate)
+          builtin =
+              deco_inst.GetSingleWordInOperand(kOpDecorateBuiltInLiteralInIdx);
+        else if (deco_inst.opcode() == SpvOpMemberDecorate)
+          builtin = deco_inst.GetSingleWordInOperand(
+              kOpDecorateMemberBuiltInLiteralInIdx);
+        else
+          assert(false && "unexpected decoration");
+        if (IsAnalyzedBuiltin(builtin)) live_builtins_.insert(builtin);
+      });
+  return saw_builtin;
+}
+
+void LivenessManager::MarkLocsLive(uint32_t start, uint32_t count) {
+  auto finish = start + count;
+  for (uint32_t u = start; u < finish; ++u) {
+    live_locs_.insert(u);
+  }
+}
+
+uint32_t LivenessManager::GetLocSize(const analysis::Type* type) const {
+  auto arr_type = type->AsArray();
+  if (arr_type) {
+    auto comp_type = arr_type->element_type();
+    auto len_info = arr_type->length_info();
+    assert(len_info.words[0] == analysis::Array::LengthInfo::kConstant &&
+           "unexpected array length");
+    auto comp_len = len_info.words[1];
+    return comp_len * GetLocSize(comp_type);
+  }
+  auto struct_type = type->AsStruct();
+  if (struct_type) {
+    uint32_t size = 0u;
+    for (auto& el_type : struct_type->element_types())
+      size += GetLocSize(el_type);
+    return size;
+  }
+  auto mat_type = type->AsMatrix();
+  if (mat_type) {
+    auto cnt = mat_type->element_count();
+    auto comp_type = mat_type->element_type();
+    return cnt * GetLocSize(comp_type);
+  }
+  auto vec_type = type->AsVector();
+  if (vec_type) {
+    auto comp_type = vec_type->element_type();
+    if (comp_type->AsInteger()) return 1;
+    auto float_type = comp_type->AsFloat();
+    assert(float_type && "unexpected vector component type");
+    auto width = float_type->width();
+    if (width == 32 || width == 16) return 1;
+    assert(width == 64 && "unexpected float type width");
+    auto comp_cnt = vec_type->element_count();
+    return (comp_cnt > 2) ? 2 : 1;
+  }
+  assert((type->AsInteger() || type->AsFloat()) && "unexpected input type");
+  return 1;
+}
+
+const analysis::Type* LivenessManager::GetComponentType(
+    uint32_t index, const analysis::Type* agg_type) const {
+  auto arr_type = agg_type->AsArray();
+  if (arr_type) return arr_type->element_type();
+  auto struct_type = agg_type->AsStruct();
+  if (struct_type) return struct_type->element_types()[index];
+  auto mat_type = agg_type->AsMatrix();
+  if (mat_type) return mat_type->element_type();
+  auto vec_type = agg_type->AsVector();
+  assert(vec_type && "unexpected non-aggregate type");
+  return vec_type->element_type();
+}
+
+uint32_t LivenessManager::GetLocOffset(uint32_t index,
+                                       const analysis::Type* agg_type) const {
+  auto arr_type = agg_type->AsArray();
+  if (arr_type) return index * GetLocSize(arr_type->element_type());
+  auto struct_type = agg_type->AsStruct();
+  if (struct_type) {
+    uint32_t offset = 0u;
+    uint32_t cnt = 0u;
+    for (auto& el_type : struct_type->element_types()) {
+      if (cnt == index) break;
+      offset += GetLocSize(el_type);
+      ++cnt;
+    }
+    return offset;
+  }
+  auto mat_type = agg_type->AsMatrix();
+  if (mat_type) return index * GetLocSize(mat_type->element_type());
+  auto vec_type = agg_type->AsVector();
+  assert(vec_type && "unexpected non-aggregate type");
+  auto comp_type = vec_type->element_type();
+  auto flt_type = comp_type->AsFloat();
+  if (flt_type && flt_type->width() == 64u && index >= 2u) return 1;
+  return 0;
+}
+
+void LivenessManager::AnalyzeAccessChainLoc(const Instruction* ac,
+                                            const analysis::Type** curr_type,
+                                            uint32_t* offset, bool* no_loc,
+                                            bool is_patch, bool input) {
+  analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
+  analysis::TypeManager* type_mgr = context()->get_type_mgr();
+  analysis::DecorationManager* deco_mgr = context()->get_decoration_mgr();
+  // For tesc, tese and geom input variables, and tesc output variables,
+  // first array index does not contribute to offset.
+  auto stage = context()->GetStage();
+  bool skip_first_index = false;
+  if ((input && (stage == SpvExecutionModelTessellationControl ||
+                 stage == SpvExecutionModelTessellationEvaluation ||
+                 stage == SpvExecutionModelGeometry)) ||
+      (!input && stage == SpvExecutionModelTessellationControl))
+    skip_first_index = !is_patch;
+  uint32_t ocnt = 0;
+  ac->WhileEachInOperand([this, &ocnt, def_use_mgr, type_mgr, deco_mgr,
+                          curr_type, offset, no_loc,
+                          skip_first_index](const uint32_t* opnd) {
+    if (ocnt >= 1) {
+      // Skip first index's contribution to offset if indicated
+      if (ocnt == 1 && skip_first_index) {
+        auto arr_type = (*curr_type)->AsArray();
+        assert(arr_type && "unexpected wrapper type");
+        *curr_type = arr_type->element_type();
+        ocnt++;
+        return true;
+      }
+      // If any non-constant index, mark the entire current object and return.
+      auto idx_inst = def_use_mgr->GetDef(*opnd);
+      if (idx_inst->opcode() != SpvOpConstant) return false;
+      // If current type is struct, look for location decoration on member and
+      // reset offset if found.
+      auto index = idx_inst->GetSingleWordInOperand(0);
+      auto str_type = (*curr_type)->AsStruct();
+      if (str_type) {
+        uint32_t loc = 0;
+        auto str_type_id = type_mgr->GetId(str_type);
+        bool no_mem_loc = deco_mgr->WhileEachDecoration(
+            str_type_id, SpvDecorationLocation,
+            [&loc, index, no_loc](const Instruction& deco) {
+              assert(deco.opcode() == SpvOpMemberDecorate &&
+                     "unexpected decoration");
+              if (deco.GetSingleWordInOperand(kOpDecorateMemberMemberInIdx) ==
+                  index) {
+                loc =
+                    deco.GetSingleWordInOperand(kOpDecorateMemberLocationInIdx);
+                *no_loc = false;
+                return false;
+              }
+              return true;
+            });
+        if (!no_mem_loc) {
+          *offset = loc;
+          *curr_type = GetComponentType(index, *curr_type);
+          ocnt++;
+          return true;
+        }
+      }
+
+      // Update offset and current type based on constant index.
+      *offset += GetLocOffset(index, *curr_type);
+      *curr_type = GetComponentType(index, *curr_type);
+    }
+    ocnt++;
+    return true;
+  });
+}
+
+void LivenessManager::MarkRefLive(const Instruction* ref, Instruction* var) {
+  analysis::TypeManager* type_mgr = context()->get_type_mgr();
+  analysis::DecorationManager* deco_mgr = context()->get_decoration_mgr();
+  // Find variable location if present.
+  uint32_t loc = 0;
+  auto var_id = var->result_id();
+  bool no_loc = deco_mgr->WhileEachDecoration(
+      var_id, SpvDecorationLocation, [&loc](const Instruction& deco) {
+        assert(deco.opcode() == SpvOpDecorate && "unexpected decoration");
+        loc = deco.GetSingleWordInOperand(kDecorationLocationInIdx);
+        return false;
+      });
+  // Find patch decoration if present
+  bool is_patch = !deco_mgr->WhileEachDecoration(
+      var_id, SpvDecorationPatch, [](const Instruction& deco) {
+        if (deco.opcode() != SpvOpDecorate)
+          assert(false && "unexpected decoration");
+        return false;
+      });
+  // If use is a load, mark all locations of var
+  auto ptr_type = type_mgr->GetType(var->type_id())->AsPointer();
+  assert(ptr_type && "unexpected var type");
+  auto var_type = ptr_type->pointee_type();
+  if (ref->opcode() == SpvOpLoad) {
+    assert(!no_loc && "missing input variable location");
+    MarkLocsLive(loc, GetLocSize(var_type));
+    return;
+  }
+  // Mark just those locations indicated by access chain
+  assert((ref->opcode() == SpvOpAccessChain ||
+          ref->opcode() == SpvOpInBoundsAccessChain) &&
+         "unexpected use of input variable");
+  // Traverse access chain, compute location offset and type of reference
+  // through constant indices and mark those locs live. Assert if no location
+  // found.
+  uint32_t offset = loc;
+  auto curr_type = var_type;
+  AnalyzeAccessChainLoc(ref, &curr_type, &offset, &no_loc, is_patch);
+  assert(!no_loc && "missing input variable location");
+  MarkLocsLive(offset, GetLocSize(curr_type));
+}
+
+void LivenessManager::ComputeLiveness() {
+  InitializeAnalysis();
+  analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
+  analysis::TypeManager* type_mgr = context()->get_type_mgr();
+  // Process all input variables
+  for (auto& var : context()->types_values()) {
+    if (var.opcode() != SpvOpVariable) {
+      continue;
+    }
+    analysis::Type* var_type = type_mgr->GetType(var.type_id());
+    analysis::Pointer* ptr_type = var_type->AsPointer();
+    if (ptr_type->storage_class() != SpvStorageClassInput) {
+      continue;
+    }
+    // If var is builtin, mark live if analyzed and continue to next variable
+    auto var_id = var.result_id();
+    if (AnalyzeBuiltIn(var_id)) continue;
+    // If interface block with builtin members, mark live if analyzed and
+    // continue to next variable. Input interface blocks will only appear
+    // in tesc, tese and geom shaders. Will need to strip off one level of
+    // arrayness to get to block type.
+    auto pte_type = ptr_type->pointee_type();
+    auto arr_type = pte_type->AsArray();
+    if (arr_type) {
+      auto elt_type = arr_type->element_type();
+      auto str_type = elt_type->AsStruct();
+      if (str_type) {
+        auto str_type_id = type_mgr->GetId(str_type);
+        if (AnalyzeBuiltIn(str_type_id)) continue;
+      }
+    }
+    // Mark all used locations of var live
+    def_use_mgr->ForEachUser(var_id, [this, &var](Instruction* user) {
+      auto op = user->opcode();
+      if (op == SpvOpEntryPoint || op == SpvOpName || op == SpvOpDecorate)
+        return;
+      MarkRefLive(user, &var);
+    });
+  }
+}
+
+void LivenessManager::GetLiveness(std::unordered_set<uint32_t>* live_locs,
+                                  std::unordered_set<uint32_t>* live_builtins) {
+  if (!computed_) {
+    ComputeLiveness();
+    computed_ = true;
+  }
+  *live_locs = live_locs_;
+  *live_builtins = live_builtins_;
+}
+
+}  // namespace analysis
+}  // namespace opt
+}  // namespace spvtools
diff --git a/source/opt/liveness.h b/source/opt/liveness.h
new file mode 100644
index 000000000..7d8a9fb40
--- /dev/null
+++ b/source/opt/liveness.h
@@ -0,0 +1,99 @@
+// Copyright (c) 2022 The Khronos Group Inc.
+// Copyright (c) 2022 LunarG Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SOURCE_OPT_LIVENESS_H_
+#define SOURCE_OPT_LIVENESS_H_
+
+#include <cstdint>
+#include <unordered_set>
+
+namespace spvtools {
+namespace opt {
+
+class IRContext;
+class Instruction;
+
+namespace analysis {
+
+class Type;
+
+// This class represents the liveness of the input variables of a module
+class LivenessManager {
+ public:
+  LivenessManager(IRContext* ctx);
+
+  // Copy liveness info into |live_locs| and |builtin_locs|.
+  void GetLiveness(std::unordered_set<uint32_t>* live_locs,
+                   std::unordered_set<uint32_t>* live_builtins);
+
+  // Return true if builtin |bi| is being analyzed.
+  bool IsAnalyzedBuiltin(uint32_t bi);
+
+  // Determine starting loc |offset| and the type |cur_type| of
+  // access chain |ac|. Set |no_loc| to true if no loc found.
+  // |is_patch| indicates if patch variable. |input| is true
+  // if input variable, otherwise output variable.
+  void AnalyzeAccessChainLoc(const Instruction* ac,
+                             const analysis::Type** curr_type, uint32_t* offset,
+                             bool* no_loc, bool is_patch, bool input = true);
+
+  // Return size of |type_id| in units of locations
+  uint32_t GetLocSize(const analysis::Type* type) const;
+
+ private:
+  IRContext* context() const { return ctx_; }
+
+  // Initialize analysis
+  void InitializeAnalysis();
+
+  // Analyze |id| for builtin var and struct members. Return true if builtins
+  // found.
+  bool AnalyzeBuiltIn(uint32_t id);
+
+  // Mark all live locations resulting from |user| of |var| at |loc|.
+  void MarkRefLive(const Instruction* user, Instruction* var);
+
+  // Mark |count| locations starting at location |start|.
+  void MarkLocsLive(uint32_t start, uint32_t count);
+
+  // Return type of component of aggregate type |agg_type| at |index|
+  const analysis::Type* GetComponentType(uint32_t index,
+                                         const analysis::Type* agg_type) const;
+
+  // Return offset of |index| into aggregate type |agg_type| in units of
+  // input locations
+  uint32_t GetLocOffset(uint32_t index, const analysis::Type* agg_type) const;
+
+  // Populate live_locs_ and live_builtins_
+  void ComputeLiveness();
+
+  // IR context that owns this liveness manager.
+  IRContext* ctx_;
+
+  // True if live_locs_ and live_builtins_ are computed
+  bool computed_;
+
+  // Live locations
+  std::unordered_set<uint32_t> live_locs_;
+
+  // Live builtins
+  std::unordered_set<uint32_t> live_builtins_;
+};
+
+}  // namespace analysis
+}  // namespace opt
+}  // namespace spvtools
+
+#endif  // SOURCE_OPT_LIVENESS_H_
diff --git a/source/opt/module.cpp b/source/opt/module.cpp
index c98af8f51..2f788ffda 100644
--- a/source/opt/module.cpp
+++ b/source/opt/module.cpp
@@ -159,7 +159,6 @@ void Module::ToBinary(std::vector<uint32_t>* binary, bool skip_nop) const {
     if (between_merge_and_branch && i->IsLineInst()) {
       return;
     }
-    between_merge_and_branch = false;
     if (last_line_inst != nullptr) {
       // If the current instruction is OpLine or DebugLine and it is the same
       // as the last line instruction that is still effective (can be applied
@@ -202,7 +201,7 @@ void Module::ToBinary(std::vector<uint32_t>* binary, bool skip_nop) const {
 
     if (!(skip_nop && i->IsNop())) {
       const auto& scope = i->GetDebugScope();
-      if (scope != last_scope) {
+      if (scope != last_scope && !between_merge_and_branch) {
         // Can only emit nonsemantic instructions after all phi instructions
         // in a block so don't emit scope instructions before phi instructions
         // for NonSemantic.Shader.DebugInfo.100.
@@ -221,6 +220,7 @@ void Module::ToBinary(std::vector<uint32_t>* binary, bool skip_nop) const {
       i->ToBinaryWithoutAttachedDebugInsts(binary);
     }
     // Update the last line instruction.
+    between_merge_and_branch = false;
     if (spvOpcodeIsBlockTerminator(opcode) || i->IsNoLine()) {
       last_line_inst = nullptr;
     } else if (opcode == SpvOpLoopMerge || opcode == SpvOpSelectionMerge) {
diff --git a/source/opt/optimizer.cpp b/source/opt/optimizer.cpp
index 381589b53..75a47784c 100644
--- a/source/opt/optimizer.cpp
+++ b/source/opt/optimizer.cpp
@@ -60,6 +60,7 @@ struct Optimizer::Impl {
 
   spv_target_env target_env;      // Target environment.
   opt::PassManager pass_manager;  // Internal implementation pass manager.
+  std::unordered_set<uint32_t> live_locs;  // Arg to debug dead output passes
 };
 
 Optimizer::Optimizer(spv_target_env env) : impl_(new Impl(env)) {
@@ -1019,6 +1020,20 @@ Optimizer::PassToken CreateEliminateDeadInputComponentsPass() {
       MakeUnique<opt::EliminateDeadInputComponentsPass>());
 }
 
+Optimizer::PassToken CreateAnalyzeLiveInputPass(
+    std::unordered_set<uint32_t>* live_locs,
+    std::unordered_set<uint32_t>* live_builtins) {
+  return MakeUnique<Optimizer::PassToken::Impl>(
+      MakeUnique<opt::AnalyzeLiveInputPass>(live_locs, live_builtins));
+}
+
+Optimizer::PassToken CreateEliminateDeadOutputStoresPass(
+    std::unordered_set<uint32_t>* live_locs,
+    std::unordered_set<uint32_t>* live_builtins) {
+  return MakeUnique<Optimizer::PassToken::Impl>(
+      MakeUnique<opt::EliminateDeadOutputStoresPass>(live_locs, live_builtins));
+}
+
 Optimizer::PassToken CreateConvertToSampledImagePass(
     const std::vector<opt::DescriptorSetAndBinding>&
         descriptor_set_binding_pairs) {
diff --git a/source/opt/passes.h b/source/opt/passes.h
index 21354c77b..5344dcf95 100644
--- a/source/opt/passes.h
+++ b/source/opt/passes.h
@@ -19,6 +19,7 @@
 
 #include "source/opt/aggressive_dead_code_elim_pass.h"
 #include "source/opt/amd_ext_to_khr.h"
+#include "source/opt/analyze_live_input_pass.h"
 #include "source/opt/block_merge_pass.h"
 #include "source/opt/ccp_pass.h"
 #include "source/opt/cfg_cleanup_pass.h"
@@ -36,6 +37,7 @@
 #include "source/opt/eliminate_dead_functions_pass.h"
 #include "source/opt/eliminate_dead_input_components_pass.h"
 #include "source/opt/eliminate_dead_members_pass.h"
+#include "source/opt/eliminate_dead_output_stores_pass.h"
 #include "source/opt/empty_pass.h"
 #include "source/opt/fix_func_call_arguments.h"
 #include "source/opt/fix_storage_class.h"
diff --git a/test/opt/CMakeLists.txt b/test/opt/CMakeLists.txt
index 15966c184..36bf04c32 100644
--- a/test/opt/CMakeLists.txt
+++ b/test/opt/CMakeLists.txt
@@ -18,6 +18,7 @@ add_subdirectory(loop_optimizations)
 add_spvtools_unittest(TARGET opt
   SRCS aggressive_dead_code_elim_test.cpp
        amd_ext_to_khr.cpp
+       analyze_live_input_test.cpp
        assembly_builder_test.cpp
        block_merge_test.cpp
        ccp_test.cpp
@@ -44,6 +45,7 @@ add_spvtools_unittest(TARGET opt
        eliminate_dead_functions_test.cpp
        eliminate_dead_input_components_test.cpp
        eliminate_dead_member_test.cpp
+       eliminate_dead_output_stores_test.cpp
        feature_manager_test.cpp
        fix_func_call_arguments_test.cpp
        fix_storage_class_test.cpp
diff --git a/test/opt/analyze_live_input_test.cpp b/test/opt/analyze_live_input_test.cpp
new file mode 100644
index 000000000..d61dbdb85
--- /dev/null
+++ b/test/opt/analyze_live_input_test.cpp
@@ -0,0 +1,910 @@
+// Copyright (c) 2022 The Khronos Group Inc.
+// Copyright (c) 2022 LunarG Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <unordered_set>
+
+#include "gmock/gmock.h"
+#include "test/opt/pass_fixture.h"
+#include "test/opt/pass_utils.h"
+
+namespace spvtools {
+namespace opt {
+namespace {
+
+using AnalyzeLiveInputTest = PassTest<::testing::Test>;
+
+TEST_F(AnalyzeLiveInputTest, FragMultipleLocations) {
+  // Should report locations {2, 5}
+  //
+  // #version 450
+  //
+  // layout(location = 2) in Vertex
+  // {
+  //         vec4 color0;
+  //         vec4 color1;
+  //         vec4 color2[3];
+  // } iVert;
+  //
+  // layout(location = 0) out vec4 oFragColor;
+  //
+  // void main()
+  // {
+  //     oFragColor = iVert.color0 + iVert.color2[1];
+  // }
+  const std::string text = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %main "main" %oFragColor %iVert
+               OpExecutionMode %main OriginUpperLeft
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %oFragColor "oFragColor"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "color0"
+               OpMemberName %Vertex 1 "color1"
+               OpMemberName %Vertex 2 "color2"
+               OpName %iVert "iVert"
+               OpDecorate %oFragColor Location 0
+               OpDecorate %Vertex Block
+               OpDecorate %iVert Location 2
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+ %oFragColor = OpVariable %_ptr_Output_v4float Output
+       %uint = OpTypeInt 32 0
+     %uint_3 = OpConstant %uint 3
+%_arr_v4float_uint_3 = OpTypeArray %v4float %uint_3
+     %Vertex = OpTypeStruct %v4float %v4float %_arr_v4float_uint_3
+%_ptr_Input_Vertex = OpTypePointer Input %Vertex
+      %iVert = OpVariable %_ptr_Input_Vertex Input
+        %int = OpTypeInt 32 1
+      %int_0 = OpConstant %int 0
+%_ptr_Input_v4float = OpTypePointer Input %v4float
+      %int_2 = OpConstant %int 2
+      %int_1 = OpConstant %int 1
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %19 = OpAccessChain %_ptr_Input_v4float %iVert %int_0
+         %20 = OpLoad %v4float %19
+         %23 = OpAccessChain %_ptr_Input_v4float %iVert %int_2 %int_1
+         %24 = OpLoad %v4float %23
+         %25 = OpFAdd %v4float %20 %24
+               OpStore %oFragColor %25
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  auto result = SinglePassRunToBinary<AnalyzeLiveInputPass>(
+      text, true, &live_inputs, &live_builtins);
+
+  auto itr0 = live_inputs.find(0);
+  auto itr1 = live_inputs.find(1);
+  auto itr2 = live_inputs.find(2);
+  auto itr3 = live_inputs.find(3);
+  auto itr4 = live_inputs.find(4);
+  auto itr5 = live_inputs.find(5);
+  auto itr6 = live_inputs.find(6);
+
+  // Expect live_inputs == {2, 5}
+  EXPECT_TRUE(itr0 == live_inputs.end());
+  EXPECT_TRUE(itr1 == live_inputs.end());
+  EXPECT_TRUE(itr2 != live_inputs.end());
+  EXPECT_TRUE(itr3 == live_inputs.end());
+  EXPECT_TRUE(itr4 == live_inputs.end());
+  EXPECT_TRUE(itr5 != live_inputs.end());
+  EXPECT_TRUE(itr6 == live_inputs.end());
+}
+
+TEST_F(AnalyzeLiveInputTest, FragMatrix) {
+  // Should report locations {2, 8, 9, 10, 11}
+  //
+  // #version 450
+  //
+  // uniform ui_name {
+  //     int i;
+  // } ui_inst;
+  //
+  // layout(location = 2) in Vertex
+  // {
+  //         vec4 color0;
+  //         vec4 color1;
+  //         mat4 color2;
+  //         mat4 color3;
+  //         mat4 color4;
+  // } iVert;
+  //
+  // // Output variable for the color
+  // layout(location = 0) out vec4 oFragColor;
+  //
+  // void main()
+  // {
+  //     oFragColor = iVert.color0 + iVert.color3[ui_inst.i];
+  // }
+  const std::string text = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %main "main" %oFragColor %iVert %ui_inst
+               OpExecutionMode %main OriginUpperLeft
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %oFragColor "oFragColor"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "color0"
+               OpMemberName %Vertex 1 "color1"
+               OpMemberName %Vertex 2 "color2"
+               OpMemberName %Vertex 3 "color3"
+               OpMemberName %Vertex 4 "color4"
+               OpName %iVert "iVert"
+               OpName %ui_name "ui_name"
+               OpMemberName %ui_name 0 "i"
+               OpName %ui_inst "ui_inst"
+               OpDecorate %oFragColor Location 0
+               OpDecorate %Vertex Block
+               OpDecorate %iVert Location 2
+               OpMemberDecorate %ui_name 0 Offset 0
+               OpDecorate %ui_name Block
+               OpDecorate %ui_inst DescriptorSet 0
+               OpDecorate %ui_inst Binding 0
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+ %oFragColor = OpVariable %_ptr_Output_v4float Output
+%mat4v4float = OpTypeMatrix %v4float 4
+     %Vertex = OpTypeStruct %v4float %v4float %mat4v4float %mat4v4float %mat4v4float
+%_ptr_Input_Vertex = OpTypePointer Input %Vertex
+      %iVert = OpVariable %_ptr_Input_Vertex Input
+        %int = OpTypeInt 32 1
+      %int_0 = OpConstant %int 0
+%_ptr_Input_v4float = OpTypePointer Input %v4float
+      %int_3 = OpConstant %int 3
+    %ui_name = OpTypeStruct %int
+%_ptr_Uniform_ui_name = OpTypePointer Uniform %ui_name
+    %ui_inst = OpVariable %_ptr_Uniform_ui_name Uniform
+%_ptr_Uniform_int = OpTypePointer Uniform %int
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %17 = OpAccessChain %_ptr_Input_v4float %iVert %int_0
+         %18 = OpLoad %v4float %17
+         %24 = OpAccessChain %_ptr_Uniform_int %ui_inst %int_0
+         %25 = OpLoad %int %24
+         %26 = OpAccessChain %_ptr_Input_v4float %iVert %int_3 %25
+         %27 = OpLoad %v4float %26
+         %28 = OpFAdd %v4float %18 %27
+               OpStore %oFragColor %28
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  auto result = SinglePassRunToBinary<AnalyzeLiveInputPass>(
+      text, true, &live_inputs, &live_builtins);
+
+  auto itr0 = live_inputs.find(0);
+  auto itr1 = live_inputs.find(1);
+  auto itr2 = live_inputs.find(2);
+  auto itr3 = live_inputs.find(3);
+  auto itr4 = live_inputs.find(4);
+  auto itr5 = live_inputs.find(5);
+  auto itr6 = live_inputs.find(6);
+  auto itr7 = live_inputs.find(7);
+  auto itr8 = live_inputs.find(8);
+  auto itr9 = live_inputs.find(9);
+  auto itr10 = live_inputs.find(10);
+  auto itr11 = live_inputs.find(11);
+  auto itr12 = live_inputs.find(12);
+  auto itr13 = live_inputs.find(13);
+  auto itr14 = live_inputs.find(14);
+  auto itr15 = live_inputs.find(15);
+
+  // Expect live_inputs == {2, 8, 9, 10, 11}
+  EXPECT_TRUE(itr0 == live_inputs.end());
+  EXPECT_TRUE(itr1 == live_inputs.end());
+  EXPECT_TRUE(itr2 != live_inputs.end());
+  EXPECT_TRUE(itr3 == live_inputs.end());
+  EXPECT_TRUE(itr4 == live_inputs.end());
+  EXPECT_TRUE(itr5 == live_inputs.end());
+  EXPECT_TRUE(itr6 == live_inputs.end());
+  EXPECT_TRUE(itr7 == live_inputs.end());
+  EXPECT_TRUE(itr8 != live_inputs.end());
+  EXPECT_TRUE(itr9 != live_inputs.end());
+  EXPECT_TRUE(itr10 != live_inputs.end());
+  EXPECT_TRUE(itr11 != live_inputs.end());
+  EXPECT_TRUE(itr12 == live_inputs.end());
+  EXPECT_TRUE(itr13 == live_inputs.end());
+  EXPECT_TRUE(itr14 == live_inputs.end());
+  EXPECT_TRUE(itr15 == live_inputs.end());
+}
+
+TEST_F(AnalyzeLiveInputTest, FragMemberLocs) {
+  // Should report location {1}
+  //
+  // #version 450
+  //
+  // in Vertex
+  // {
+  //     layout (location = 1) vec4 Cd;
+  //     layout (location = 0) vec2 uv;
+  // } iVert;
+  //
+  // layout (location = 0) out vec4 fragColor;
+  //
+  // void main()
+  // {
+  //     vec4 color = vec4(iVert.Cd);
+  //     fragColor = color;
+  // }
+  const std::string text = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %main "main" %iVert %fragColor
+               OpExecutionMode %main OriginUpperLeft
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %color "color"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "Cd"
+               OpMemberName %Vertex 1 "uv"
+               OpName %iVert "iVert"
+               OpName %fragColor "fragColor"
+               OpMemberDecorate %Vertex 0 Location 1
+               OpMemberDecorate %Vertex 1 Location 0
+               OpDecorate %Vertex Block
+               OpDecorate %fragColor Location 0
+               OpDecorate %_struct_27 Block
+               OpMemberDecorate %_struct_27 0 Location 1
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+%_ptr_Function_v4float = OpTypePointer Function %v4float
+    %v2float = OpTypeVector %float 2
+     %Vertex = OpTypeStruct %v4float %v2float
+%_ptr_Input_Vertex = OpTypePointer Input %Vertex
+        %int = OpTypeInt 32 1
+      %int_0 = OpConstant %int 0
+%_ptr_Input_v4float = OpTypePointer Input %v4float
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+  %fragColor = OpVariable %_ptr_Output_v4float Output
+ %_struct_27 = OpTypeStruct %v4float
+%_ptr_Input__struct_27 = OpTypePointer Input %_struct_27
+      %iVert = OpVariable %_ptr_Input__struct_27 Input
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+      %color = OpVariable %_ptr_Function_v4float Function
+         %17 = OpAccessChain %_ptr_Input_v4float %iVert %int_0
+         %18 = OpLoad %v4float %17
+         %19 = OpCompositeExtract %float %18 0
+         %20 = OpCompositeExtract %float %18 1
+         %21 = OpCompositeExtract %float %18 2
+         %22 = OpCompositeExtract %float %18 3
+         %23 = OpCompositeConstruct %v4float %19 %20 %21 %22
+               OpStore %color %23
+         %26 = OpLoad %v4float %color
+               OpStore %fragColor %26
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  auto result = SinglePassRunToBinary<AnalyzeLiveInputPass>(
+      text, true, &live_inputs, &live_builtins);
+
+  auto itr0 = live_inputs.find(0);
+  auto itr1 = live_inputs.find(1);
+
+  // Expect live_inputs == {2, 5}
+  EXPECT_TRUE(itr0 == live_inputs.end());
+  EXPECT_TRUE(itr1 != live_inputs.end());
+}
+
+TEST_F(AnalyzeLiveInputTest, ArrayedInput) {
+  // Tests handling of arrayed input seen in Tesc, Tese and Geom shaders.
+  //
+  // Should report location {1, 10}.
+  //
+  // #version 450
+  //
+  // layout (vertices = 4) out;
+  //
+  // layout (location = 1) in Vertex
+  // {
+  //                 vec4 p;
+  //                 vec3 n;
+  //                 vec4 f[100];
+  // } iVert[];
+  //
+  // layout (location = 0) out vec4 position[4];
+  //
+  // void main()
+  // {
+  //                 vec4 pos = iVert[gl_InvocationID].p *
+  //                            iVert[gl_InvocationID].f[7];
+  //                 position[gl_InvocationID] = pos;
+  // }
+  const std::string text = R"(
+               OpCapability Tessellation
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint TessellationControl %main "main" %iVert %gl_InvocationID %position
+               OpExecutionMode %main OutputVertices 4
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "p"
+               OpMemberName %Vertex 1 "n"
+               OpMemberName %Vertex 2 "f"
+               OpName %iVert "iVert"
+               OpName %gl_InvocationID "gl_InvocationID"
+               OpName %position "position"
+               OpDecorate %Vertex Block
+               OpDecorate %iVert Location 1
+               OpDecorate %gl_InvocationID BuiltIn InvocationId
+               OpDecorate %position Location 0
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+    %v3float = OpTypeVector %float 3
+       %uint = OpTypeInt 32 0
+   %uint_100 = OpConstant %uint 100
+%_arr_v4float_uint_100 = OpTypeArray %v4float %uint_100
+     %Vertex = OpTypeStruct %v4float %v3float %_arr_v4float_uint_100
+    %uint_32 = OpConstant %uint 32
+%_arr_Vertex_uint_32 = OpTypeArray %Vertex %uint_32
+%_ptr_Input__arr_Vertex_uint_32 = OpTypePointer Input %_arr_Vertex_uint_32
+      %iVert = OpVariable %_ptr_Input__arr_Vertex_uint_32 Input
+        %int = OpTypeInt 32 1
+%_ptr_Input_int = OpTypePointer Input %int
+%gl_InvocationID = OpVariable %_ptr_Input_int Input
+      %int_0 = OpConstant %int 0
+%_ptr_Input_v4float = OpTypePointer Input %v4float
+      %int_2 = OpConstant %int 2
+      %int_7 = OpConstant %int 7
+     %uint_4 = OpConstant %uint 4
+%_arr_v4float_uint_4 = OpTypeArray %v4float %uint_4
+%_ptr_Output__arr_v4float_uint_4 = OpTypePointer Output %_arr_v4float_uint_4
+   %position = OpVariable %_ptr_Output__arr_v4float_uint_4 Output
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %22 = OpLoad %int %gl_InvocationID
+         %25 = OpAccessChain %_ptr_Input_v4float %iVert %22 %int_0
+         %26 = OpLoad %v4float %25
+         %30 = OpAccessChain %_ptr_Input_v4float %iVert %22 %int_2 %int_7
+         %31 = OpLoad %v4float %30
+         %32 = OpFMul %v4float %26 %31
+         %40 = OpAccessChain %_ptr_Output_v4float %position %22
+               OpStore %40 %32
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  auto result = SinglePassRunToBinary<AnalyzeLiveInputPass>(
+      text, true, &live_inputs, &live_builtins);
+
+  auto itr0 = live_inputs.find(0);
+  auto itr1 = live_inputs.find(1);
+  auto itr2 = live_inputs.find(2);
+  auto itr3 = live_inputs.find(3);
+  auto itr4 = live_inputs.find(4);
+  auto itr5 = live_inputs.find(5);
+  auto itr6 = live_inputs.find(6);
+  auto itr7 = live_inputs.find(7);
+  auto itr8 = live_inputs.find(8);
+  auto itr9 = live_inputs.find(9);
+  auto itr10 = live_inputs.find(10);
+  auto itr11 = live_inputs.find(11);
+
+  // Expect live_inputs == {1, 10}
+  EXPECT_TRUE(itr0 == live_inputs.end());
+  EXPECT_TRUE(itr1 != live_inputs.end());
+  EXPECT_TRUE(itr2 == live_inputs.end());
+  EXPECT_TRUE(itr3 == live_inputs.end());
+  EXPECT_TRUE(itr4 == live_inputs.end());
+  EXPECT_TRUE(itr5 == live_inputs.end());
+  EXPECT_TRUE(itr6 == live_inputs.end());
+  EXPECT_TRUE(itr7 == live_inputs.end());
+  EXPECT_TRUE(itr8 == live_inputs.end());
+  EXPECT_TRUE(itr9 == live_inputs.end());
+  EXPECT_TRUE(itr10 != live_inputs.end());
+  EXPECT_TRUE(itr11 == live_inputs.end());
+}
+
+TEST_F(AnalyzeLiveInputTest, ArrayedInputMemberLocs) {
+  // Tests handling of member locs with arrayed input seen in Tesc, Tese
+  // and Geom shaders.
+  //
+  // Should report location {1, 12}.
+  //
+  // #version 450
+  //
+  // layout (vertices = 4) out;
+  //
+  // in Vertex
+  // {
+  //     layout (location = 1) vec4 p;
+  //     layout (location = 3) vec3 n;
+  //     layout (location = 5) vec4 f[100];
+  // } iVert[];
+  //
+  // layout (location = 0) out vec4 position[4];
+  //
+  // void main()
+  // {
+  //                 vec4 pos = iVert[gl_InvocationID].p *
+  //                            iVert[gl_InvocationID].f[7];
+  //                 position[gl_InvocationID] = pos;
+  // }
+  const std::string text = R"(
+               OpCapability Tessellation
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint TessellationControl %main "main" %iVert %gl_InvocationID %position
+               OpExecutionMode %main OutputVertices 4
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "p"
+               OpMemberName %Vertex 1 "n"
+               OpMemberName %Vertex 2 "f"
+               OpName %iVert "iVert"
+               OpName %gl_InvocationID "gl_InvocationID"
+               OpName %position "position"
+               OpMemberDecorate %Vertex 0 Location 1
+               OpMemberDecorate %Vertex 1 Location 3
+               OpMemberDecorate %Vertex 2 Location 5
+               OpDecorate %Vertex Block
+               OpDecorate %gl_InvocationID BuiltIn InvocationId
+               OpDecorate %position Location 0
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+    %v3float = OpTypeVector %float 3
+       %uint = OpTypeInt 32 0
+   %uint_100 = OpConstant %uint 100
+%_arr_v4float_uint_100 = OpTypeArray %v4float %uint_100
+     %Vertex = OpTypeStruct %v4float %v3float %_arr_v4float_uint_100
+    %uint_32 = OpConstant %uint 32
+%_arr_Vertex_uint_32 = OpTypeArray %Vertex %uint_32
+%_ptr_Input__arr_Vertex_uint_32 = OpTypePointer Input %_arr_Vertex_uint_32
+      %iVert = OpVariable %_ptr_Input__arr_Vertex_uint_32 Input
+        %int = OpTypeInt 32 1
+%_ptr_Input_int = OpTypePointer Input %int
+%gl_InvocationID = OpVariable %_ptr_Input_int Input
+      %int_0 = OpConstant %int 0
+%_ptr_Input_v4float = OpTypePointer Input %v4float
+      %int_2 = OpConstant %int 2
+      %int_7 = OpConstant %int 7
+     %uint_4 = OpConstant %uint 4
+%_arr_v4float_uint_4 = OpTypeArray %v4float %uint_4
+%_ptr_Output__arr_v4float_uint_4 = OpTypePointer Output %_arr_v4float_uint_4
+   %position = OpVariable %_ptr_Output__arr_v4float_uint_4 Output
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %22 = OpLoad %int %gl_InvocationID
+         %25 = OpAccessChain %_ptr_Input_v4float %iVert %22 %int_0
+         %26 = OpLoad %v4float %25
+         %30 = OpAccessChain %_ptr_Input_v4float %iVert %22 %int_2 %int_7
+         %31 = OpLoad %v4float %30
+         %32 = OpFMul %v4float %26 %31
+         %40 = OpAccessChain %_ptr_Output_v4float %position %22
+               OpStore %40 %32
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  auto result = SinglePassRunToBinary<AnalyzeLiveInputPass>(
+      text, true, &live_inputs, &live_builtins);
+
+  auto itr0 = live_inputs.find(0);
+  auto itr1 = live_inputs.find(1);
+  auto itr2 = live_inputs.find(2);
+  auto itr3 = live_inputs.find(3);
+  auto itr4 = live_inputs.find(4);
+  auto itr5 = live_inputs.find(5);
+  auto itr6 = live_inputs.find(6);
+  auto itr7 = live_inputs.find(7);
+  auto itr8 = live_inputs.find(8);
+  auto itr9 = live_inputs.find(9);
+  auto itr10 = live_inputs.find(10);
+  auto itr11 = live_inputs.find(11);
+  auto itr12 = live_inputs.find(12);
+  auto itr13 = live_inputs.find(13);
+
+  // Expect live_inputs == {1, 12}
+  EXPECT_TRUE(itr0 == live_inputs.end());
+  EXPECT_TRUE(itr1 != live_inputs.end());
+  EXPECT_TRUE(itr2 == live_inputs.end());
+  EXPECT_TRUE(itr3 == live_inputs.end());
+  EXPECT_TRUE(itr4 == live_inputs.end());
+  EXPECT_TRUE(itr5 == live_inputs.end());
+  EXPECT_TRUE(itr6 == live_inputs.end());
+  EXPECT_TRUE(itr7 == live_inputs.end());
+  EXPECT_TRUE(itr8 == live_inputs.end());
+  EXPECT_TRUE(itr9 == live_inputs.end());
+  EXPECT_TRUE(itr10 == live_inputs.end());
+  EXPECT_TRUE(itr11 == live_inputs.end());
+  EXPECT_TRUE(itr12 != live_inputs.end());
+  EXPECT_TRUE(itr13 == live_inputs.end());
+}
+
+TEST_F(AnalyzeLiveInputTest, Builtins) {
+  // Tests handling of builtin input seen in Tesc, Tese and Geom shaders.
+  //
+  // Should report builtin gl_PointSize only.
+  //
+  // #version 460
+  //
+  // layout(triangle_strip, max_vertices = 3) out;
+  // layout(triangles) in;
+  //
+  // void main()
+  // {
+  //         for (int i = 0; i < 3; i++)
+  //         {
+  //                 gl_Position = gl_in[i].gl_Position;
+  //                 gl_PointSize = gl_in[i].gl_PointSize;
+  //
+  //                 EmitVertex();
+  //         }
+  //
+  //         EndPrimitive();
+  // }
+  const std::string text = R"(
+               OpCapability Geometry
+               OpCapability GeometryPointSize
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Geometry %main "main" %_ %gl_in
+               OpExecutionMode %main Triangles
+               OpExecutionMode %main Invocations 1
+               OpExecutionMode %main OutputTriangleStrip
+               OpExecutionMode %main OutputVertices 3
+               OpSource GLSL 460
+               OpName %main "main"
+               OpName %i "i"
+               OpName %gl_PerVertex "gl_PerVertex"
+               OpMemberName %gl_PerVertex 0 "gl_Position"
+               OpMemberName %gl_PerVertex 1 "gl_PointSize"
+               OpMemberName %gl_PerVertex 2 "gl_ClipDistance"
+               OpMemberName %gl_PerVertex 3 "gl_CullDistance"
+               OpName %_ ""
+               OpName %gl_PerVertex_0 "gl_PerVertex"
+               OpMemberName %gl_PerVertex_0 0 "gl_Position"
+               OpMemberName %gl_PerVertex_0 1 "gl_PointSize"
+               OpMemberName %gl_PerVertex_0 2 "gl_ClipDistance"
+               OpMemberName %gl_PerVertex_0 3 "gl_CullDistance"
+               OpName %gl_in "gl_in"
+               OpMemberDecorate %gl_PerVertex 0 BuiltIn Position
+               OpMemberDecorate %gl_PerVertex 1 BuiltIn PointSize
+               OpMemberDecorate %gl_PerVertex 2 BuiltIn ClipDistance
+               OpMemberDecorate %gl_PerVertex 3 BuiltIn CullDistance
+               OpDecorate %gl_PerVertex Block
+               OpMemberDecorate %gl_PerVertex_0 0 BuiltIn Position
+               OpMemberDecorate %gl_PerVertex_0 1 BuiltIn PointSize
+               OpDecorate %gl_PerVertex_0 Block
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+        %int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+      %int_0 = OpConstant %int 0
+      %int_3 = OpConstant %int 3
+       %bool = OpTypeBool
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+       %uint = OpTypeInt 32 0
+     %uint_1 = OpConstant %uint 1
+%_arr_float_uint_1 = OpTypeArray %float %uint_1
+%gl_PerVertex = OpTypeStruct %v4float %float %_arr_float_uint_1 %_arr_float_uint_1
+%_ptr_Output_gl_PerVertex = OpTypePointer Output %gl_PerVertex
+          %_ = OpVariable %_ptr_Output_gl_PerVertex Output
+%gl_PerVertex_0 = OpTypeStruct %v4float %float
+     %uint_3 = OpConstant %uint 3
+%_arr_gl_PerVertex_0_uint_3 = OpTypeArray %gl_PerVertex_0 %uint_3
+%_ptr_Input__arr_gl_PerVertex_0_uint_3 = OpTypePointer Input %_arr_gl_PerVertex_0_uint_3
+      %gl_in = OpVariable %_ptr_Input__arr_gl_PerVertex_0_uint_3 Input
+%_ptr_Input_v4float = OpTypePointer Input %v4float
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+      %int_1 = OpConstant %int 1
+%_ptr_Input_float = OpTypePointer Input %float
+%_ptr_Output_float = OpTypePointer Output %float
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+          %i = OpVariable %_ptr_Function_int Function
+               OpStore %i %int_0
+               OpBranch %10
+         %10 = OpLabel
+               OpLoopMerge %12 %13 None
+               OpBranch %14
+         %14 = OpLabel
+         %15 = OpLoad %int %i
+         %18 = OpSLessThan %bool %15 %int_3
+               OpBranchConditional %18 %11 %12
+         %11 = OpLabel
+         %32 = OpLoad %int %i
+         %34 = OpAccessChain %_ptr_Input_v4float %gl_in %32 %int_0
+         %35 = OpLoad %v4float %34
+         %37 = OpAccessChain %_ptr_Output_v4float %_ %int_0
+               OpStore %37 %35
+         %39 = OpLoad %int %i
+         %41 = OpAccessChain %_ptr_Input_float %gl_in %39 %int_1
+         %42 = OpLoad %float %41
+         %44 = OpAccessChain %_ptr_Output_float %_ %int_1
+               OpStore %44 %42
+               OpEmitVertex
+               OpBranch %13
+         %13 = OpLabel
+         %45 = OpLoad %int %i
+         %46 = OpIAdd %int %45 %int_1
+               OpStore %i %46
+               OpBranch %10
+         %12 = OpLabel
+               OpEndPrimitive
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  auto result = SinglePassRunToBinary<AnalyzeLiveInputPass>(
+      text, true, &live_inputs, &live_builtins);
+
+  auto itr0 = live_builtins.find(SpvBuiltInPointSize);
+  auto itr1 = live_builtins.find(SpvBuiltInClipDistance);
+  auto itr2 = live_builtins.find(SpvBuiltInCullDistance);
+
+  // Expect live_builtins == { SpvBuiltInPointSize }
+  EXPECT_TRUE(itr0 != live_builtins.end());
+  EXPECT_TRUE(itr1 == live_builtins.end());
+  EXPECT_TRUE(itr2 == live_builtins.end());
+}
+
+TEST_F(AnalyzeLiveInputTest, ArrayedInputPatchLocs) {
+  // Tests handling of locs with arrayed input patch seen in Tese
+  //
+  // Should report location {3}.
+  //
+  // #version 450 core
+  //
+  // layout(triangles, ccw) in;
+  //
+  // layout(fractional_odd_spacing) in;
+  //
+  // layout(point_mode) in;
+  //
+  // layout(location=2) patch in float patchIn1[2];
+  //
+  // void main()
+  // {
+  //     vec4 p = gl_in[1].gl_Position;
+  //     gl_Position = p * patchIn1[1];
+  // }
+  const std::string text = R"(
+               OpCapability Tessellation
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint TessellationEvaluation %main "main" %gl_in %_ %patchIn1
+               OpExecutionMode %main Triangles
+               OpExecutionMode %main SpacingFractionalOdd
+               OpExecutionMode %main VertexOrderCcw
+               OpExecutionMode %main PointMode
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %p "p"
+               OpName %gl_PerVertex "gl_PerVertex"
+               OpMemberName %gl_PerVertex 0 "gl_Position"
+               OpName %gl_in "gl_in"
+               OpName %gl_PerVertex_0 "gl_PerVertex"
+               OpMemberName %gl_PerVertex_0 0 "gl_Position"
+               OpName %_ ""
+               OpName %patchIn1 "patchIn1"
+               OpMemberDecorate %gl_PerVertex 0 BuiltIn Position
+               OpDecorate %gl_PerVertex Block
+               OpMemberDecorate %gl_PerVertex_0 0 BuiltIn Position
+               OpDecorate %gl_PerVertex_0 Block
+               OpDecorate %patchIn1 Patch
+               OpDecorate %patchIn1 Location 2
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+%_ptr_Function_v4float = OpTypePointer Function %v4float
+       %uint = OpTypeInt 32 0
+     %uint_1 = OpConstant %uint 1
+%_arr_float_uint_1 = OpTypeArray %float %uint_1
+%gl_PerVertex = OpTypeStruct %v4float
+    %uint_32 = OpConstant %uint 32
+%_arr_gl_PerVertex_uint_32 = OpTypeArray %gl_PerVertex %uint_32
+%_ptr_Input__arr_gl_PerVertex_uint_32 = OpTypePointer Input %_arr_gl_PerVertex_uint_32
+      %gl_in = OpVariable %_ptr_Input__arr_gl_PerVertex_uint_32 Input
+        %int = OpTypeInt 32 1
+      %int_1 = OpConstant %int 1
+      %int_0 = OpConstant %int 0
+%_ptr_Input_v4float = OpTypePointer Input %v4float
+%gl_PerVertex_0 = OpTypeStruct %v4float
+%_ptr_Output_gl_PerVertex_0 = OpTypePointer Output %gl_PerVertex_0
+          %_ = OpVariable %_ptr_Output_gl_PerVertex_0 Output
+     %uint_2 = OpConstant %uint 2
+%_arr_float_uint_2 = OpTypeArray %float %uint_2
+%_ptr_Input__arr_float_uint_2 = OpTypePointer Input %_arr_float_uint_2
+   %patchIn1 = OpVariable %_ptr_Input__arr_float_uint_2 Input
+%_ptr_Input_float = OpTypePointer Input %float
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+          %p = OpVariable %_ptr_Function_v4float Function
+         %22 = OpAccessChain %_ptr_Input_v4float %gl_in %int_1 %int_0
+         %23 = OpLoad %v4float %22
+               OpStore %p %23
+         %27 = OpLoad %v4float %p
+         %33 = OpAccessChain %_ptr_Input_float %patchIn1 %int_1
+         %34 = OpLoad %float %33
+         %35 = OpVectorTimesScalar %v4float %27 %34
+         %37 = OpAccessChain %_ptr_Output_v4float %_ %int_0
+               OpStore %37 %35
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  auto result = SinglePassRunToBinary<AnalyzeLiveInputPass>(
+      text, true, &live_inputs, &live_builtins);
+
+  auto itr0 = live_inputs.find(0);
+  auto itr1 = live_inputs.find(1);
+  auto itr2 = live_inputs.find(2);
+  auto itr3 = live_inputs.find(3);
+
+  // Expect live_inputs == {3}
+  EXPECT_TRUE(itr0 == live_inputs.end());
+  EXPECT_TRUE(itr1 == live_inputs.end());
+  EXPECT_TRUE(itr2 == live_inputs.end());
+  EXPECT_TRUE(itr3 != live_inputs.end());
+}
+
+TEST_F(AnalyzeLiveInputTest, FragMultipleLocationsF16) {
+  // Should report locations {2, 5}
+  //
+  // #version 450
+  //
+  // layout(location = 2) in Vertex
+  // {
+  //         f16vec4 color0;
+  //         f16vec4 color1;
+  //         f16vec4 color2[3];
+  // } iVert;
+  //
+  // layout(location = 0) out f16vec4 oFragColor;
+  //
+  // void main()
+  // {
+  //     oFragColor = iVert.color0 + iVert.color2[1];
+  // }
+  const std::string text = R"(
+               OpCapability Shader
+               OpCapability Float16
+               OpCapability StorageInputOutput16
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %main "main" %oFragColor %iVert
+               OpExecutionMode %main OriginUpperLeft
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %oFragColor "oFragColor"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "color0"
+               OpMemberName %Vertex 1 "color1"
+               OpMemberName %Vertex 2 "color2"
+               OpName %iVert "iVert"
+               OpDecorate %oFragColor Location 0
+               OpDecorate %Vertex Block
+               OpDecorate %iVert Location 2
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+       %half = OpTypeFloat 16
+     %v4half = OpTypeVector %half 4
+%_ptr_Output_v4half = OpTypePointer Output %v4half
+ %oFragColor = OpVariable %_ptr_Output_v4half Output
+       %uint = OpTypeInt 32 0
+     %uint_3 = OpConstant %uint 3
+%_arr_v4half_uint_3 = OpTypeArray %v4half %uint_3
+     %Vertex = OpTypeStruct %v4half %v4half %_arr_v4half_uint_3
+%_ptr_Input_Vertex = OpTypePointer Input %Vertex
+      %iVert = OpVariable %_ptr_Input_Vertex Input
+        %int = OpTypeInt 32 1
+      %int_0 = OpConstant %int 0
+%_ptr_Input_v4half = OpTypePointer Input %v4half
+      %int_2 = OpConstant %int 2
+      %int_1 = OpConstant %int 1
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %19 = OpAccessChain %_ptr_Input_v4half %iVert %int_0
+         %20 = OpLoad %v4half %19
+         %23 = OpAccessChain %_ptr_Input_v4half %iVert %int_2 %int_1
+         %24 = OpLoad %v4half %23
+         %25 = OpFAdd %v4half %20 %24
+               OpStore %oFragColor %25
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  auto result = SinglePassRunToBinary<AnalyzeLiveInputPass>(
+      text, true, &live_inputs, &live_builtins);
+
+  auto itr0 = live_inputs.find(0);
+  auto itr1 = live_inputs.find(1);
+  auto itr2 = live_inputs.find(2);
+  auto itr3 = live_inputs.find(3);
+  auto itr4 = live_inputs.find(4);
+  auto itr5 = live_inputs.find(5);
+  auto itr6 = live_inputs.find(6);
+
+  // Expect live_inputs == {2, 5}
+  EXPECT_TRUE(itr0 == live_inputs.end());
+  EXPECT_TRUE(itr1 == live_inputs.end());
+  EXPECT_TRUE(itr2 != live_inputs.end());
+  EXPECT_TRUE(itr3 == live_inputs.end());
+  EXPECT_TRUE(itr4 == live_inputs.end());
+  EXPECT_TRUE(itr5 != live_inputs.end());
+  EXPECT_TRUE(itr6 == live_inputs.end());
+}
+
+}  // namespace
+}  // namespace opt
+}  // namespace spvtools
diff --git a/test/opt/eliminate_dead_output_stores_test.cpp b/test/opt/eliminate_dead_output_stores_test.cpp
new file mode 100644
index 000000000..6e382c243
--- /dev/null
+++ b/test/opt/eliminate_dead_output_stores_test.cpp
@@ -0,0 +1,952 @@
+// Copyright (c) 2022 The Khronos Group Inc.
+// Copyright (c) 2022 LunarG Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <unordered_set>
+
+#include "gmock/gmock.h"
+#include "test/opt/pass_fixture.h"
+#include "test/opt/pass_utils.h"
+
+namespace spvtools {
+namespace opt {
+namespace {
+
+using ElimDeadOutputStoresTest = PassTest<::testing::Test>;
+
+TEST_F(ElimDeadOutputStoresTest, VertMultipleLocations) {
+  // #version 450
+  //
+  // layout(location = 2) out Vertex
+  // {
+  //         vec4 color0;
+  //         vec4 color1;
+  //         vec4 color2[3];
+  // } oVert;
+  //
+  // void main()
+  // {
+  //     oVert.color0 = vec4(0.0,0.0,0.0,0.0);
+  //     oVert.color1 = vec4(0.1,0.0,0.0,0.0);
+  //     oVert.color2[0] = vec4(0.2,0.0,0.0,0.0);
+  //     oVert.color2[1] = vec4(0.3,0.0,0.0,0.0);
+  //     oVert.color2[2] = vec4(0.4,0.0,0.0,0.0);
+  // }
+  const std::string text = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Vertex %main "main" %oVert
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "color0"
+               OpMemberName %Vertex 1 "color1"
+               OpMemberName %Vertex 2 "color2"
+               OpName %oVert "oVert"
+               OpDecorate %Vertex Block
+               OpDecorate %oVert Location 2
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+       %uint = OpTypeInt 32 0
+     %uint_3 = OpConstant %uint 3
+%_arr_v4float_uint_3 = OpTypeArray %v4float %uint_3
+     %Vertex = OpTypeStruct %v4float %v4float %_arr_v4float_uint_3
+%_ptr_Output_Vertex = OpTypePointer Output %Vertex
+      %oVert = OpVariable %_ptr_Output_Vertex Output
+        %int = OpTypeInt 32 1
+      %int_0 = OpConstant %int 0
+    %float_0 = OpConstant %float 0
+         %17 = OpConstantComposite %v4float %float_0 %float_0 %float_0 %float_0
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+      %int_1 = OpConstant %int 1
+%float_0_100000001 = OpConstant %float 0.100000001
+         %22 = OpConstantComposite %v4float %float_0_100000001 %float_0 %float_0 %float_0
+      %int_2 = OpConstant %int 2
+%float_0_200000003 = OpConstant %float 0.200000003
+         %26 = OpConstantComposite %v4float %float_0_200000003 %float_0 %float_0 %float_0
+%float_0_300000012 = OpConstant %float 0.300000012
+         %29 = OpConstantComposite %v4float %float_0_300000012 %float_0 %float_0 %float_0
+%float_0_400000006 = OpConstant %float 0.400000006
+         %32 = OpConstantComposite %v4float %float_0_400000006 %float_0 %float_0 %float_0
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %19 = OpAccessChain %_ptr_Output_v4float %oVert %int_0
+               OpStore %19 %17
+;CHECK:            OpStore %19 %17
+         %23 = OpAccessChain %_ptr_Output_v4float %oVert %int_1
+               OpStore %23 %22
+;CHECK-NOT:        OpStore %23 %22
+         %27 = OpAccessChain %_ptr_Output_v4float %oVert %int_2 %int_0
+               OpStore %27 %26
+;CHECK-NOT:        OpStore %27 %26
+         %30 = OpAccessChain %_ptr_Output_v4float %oVert %int_2 %int_1
+               OpStore %30 %29
+;CHECK:            OpStore %30 %29
+         %33 = OpAccessChain %_ptr_Output_v4float %oVert %int_2 %int_2
+               OpStore %33 %32
+;CHECK-NOT:        OpStore %33 %32
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  live_inputs.insert(2);
+  live_inputs.insert(5);
+  SinglePassRunAndMatch<EliminateDeadOutputStoresPass>(text, true, &live_inputs,
+                                                       &live_builtins);
+}
+
+TEST_F(ElimDeadOutputStoresTest, VertMatrix) {
+  // #version 450
+  //
+  // layout(location = 2) out Vertex
+  // {
+  //         vec4 color0;
+  //         vec4 color1;
+  //         mat4 color2;
+  //         mat4 color3;
+  //         mat4 color4;
+  // } oVert;
+  //
+  // void main()
+  // {
+  //     oVert.color0 = vec4(0.0,0.0,0.0,0.0);
+  //     oVert.color1 = vec4(0.1,0.0,0.0,0.0);
+  //     oVert.color2[2] = vec4(0.2,0.0,0.0,0.0);
+  //     oVert.color3[1] = vec4(0.3,0.0,0.0,0.0);
+  //     oVert.color4[0] = vec4(0.4,0.0,0.0,0.0);
+  // }
+  const std::string text = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Vertex %main "main" %oVert
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "color0"
+               OpMemberName %Vertex 1 "color1"
+               OpMemberName %Vertex 2 "color2"
+               OpMemberName %Vertex 3 "color3"
+               OpMemberName %Vertex 4 "color4"
+               OpName %oVert "oVert"
+               OpDecorate %Vertex Block
+               OpDecorate %oVert Location 2
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+%mat4v4float = OpTypeMatrix %v4float 4
+     %Vertex = OpTypeStruct %v4float %v4float %mat4v4float %mat4v4float %mat4v4float
+%_ptr_Output_Vertex = OpTypePointer Output %Vertex
+      %oVert = OpVariable %_ptr_Output_Vertex Output
+        %int = OpTypeInt 32 1
+      %int_0 = OpConstant %int 0
+    %float_0 = OpConstant %float 0
+         %15 = OpConstantComposite %v4float %float_0 %float_0 %float_0 %float_0
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+      %int_1 = OpConstant %int 1
+%float_0_100000001 = OpConstant %float 0.100000001
+         %20 = OpConstantComposite %v4float %float_0_100000001 %float_0 %float_0 %float_0
+      %int_2 = OpConstant %int 2
+%float_0_200000003 = OpConstant %float 0.200000003
+         %24 = OpConstantComposite %v4float %float_0_200000003 %float_0 %float_0 %float_0
+      %int_3 = OpConstant %int 3
+%float_0_300000012 = OpConstant %float 0.300000012
+         %28 = OpConstantComposite %v4float %float_0_300000012 %float_0 %float_0 %float_0
+      %int_4 = OpConstant %int 4
+%float_0_400000006 = OpConstant %float 0.400000006
+         %32 = OpConstantComposite %v4float %float_0_400000006 %float_0 %float_0 %float_0
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %17 = OpAccessChain %_ptr_Output_v4float %oVert %int_0
+               OpStore %17 %15
+; CHECK:           OpStore %17 %15
+         %21 = OpAccessChain %_ptr_Output_v4float %oVert %int_1
+               OpStore %21 %20
+; CHECK-NOT:       OpStore %21 %20
+         %25 = OpAccessChain %_ptr_Output_v4float %oVert %int_2 %int_2
+               OpStore %25 %24
+; CHECK-NOT:       OpStore %25 %24
+         %29 = OpAccessChain %_ptr_Output_v4float %oVert %int_3 %int_1
+               OpStore %29 %28
+; CHECK:           OpStore %29 %28
+         %33 = OpAccessChain %_ptr_Output_v4float %oVert %int_4 %int_0
+               OpStore %33 %32
+; CHECK-NOT:       OpStore %33 %32
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  live_inputs.insert(2);
+  live_inputs.insert(8);
+  live_inputs.insert(9);
+  live_inputs.insert(10);
+  live_inputs.insert(11);
+  SinglePassRunAndMatch<EliminateDeadOutputStoresPass>(text, true, &live_inputs,
+                                                       &live_builtins);
+}
+
+TEST_F(ElimDeadOutputStoresTest, VertMemberLocs) {
+  // #version 450
+  //
+  // out Vertex
+  // {
+  //     layout (location = 1) vec4 Cd;
+  //     layout (location = 0) vec2 uv;
+  // } oVert;
+  //
+  // layout (location  = 0) in vec3 P;
+  //
+  // void main()
+  // {
+  //     oVert.uv = vec2(0.1, 0.7);
+  //     oVert.Cd = vec4(1, 0.5, 0, 1);
+  //     gl_Position = vec4(P, 1);
+  // }
+  const std::string text = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Vertex %main "main" %oVert %_ %P
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "Cd"
+               OpMemberName %Vertex 1 "uv"
+               OpName %oVert "oVert"
+               OpName %gl_PerVertex "gl_PerVertex"
+               OpMemberName %gl_PerVertex 0 "gl_Position"
+               OpMemberName %gl_PerVertex 1 "gl_PointSize"
+               OpMemberName %gl_PerVertex 2 "gl_ClipDistance"
+               OpMemberName %gl_PerVertex 3 "gl_CullDistance"
+               OpName %_ ""
+               OpName %P "P"
+               OpMemberDecorate %Vertex 0 Location 1
+               OpMemberDecorate %Vertex 1 Location 0
+               OpDecorate %Vertex Block
+               OpMemberDecorate %gl_PerVertex 0 BuiltIn Position
+               OpMemberDecorate %gl_PerVertex 1 BuiltIn PointSize
+               OpMemberDecorate %gl_PerVertex 2 BuiltIn ClipDistance
+               OpMemberDecorate %gl_PerVertex 3 BuiltIn CullDistance
+               OpDecorate %gl_PerVertex Block
+               OpDecorate %P Location 0
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+    %v2float = OpTypeVector %float 2
+     %Vertex = OpTypeStruct %v4float %v2float
+%_ptr_Output_Vertex = OpTypePointer Output %Vertex
+      %oVert = OpVariable %_ptr_Output_Vertex Output
+        %int = OpTypeInt 32 1
+      %int_1 = OpConstant %int 1
+%float_0_100000001 = OpConstant %float 0.100000001
+%float_0_699999988 = OpConstant %float 0.699999988
+         %16 = OpConstantComposite %v2float %float_0_100000001 %float_0_699999988
+%_ptr_Output_v2float = OpTypePointer Output %v2float
+      %int_0 = OpConstant %int 0
+    %float_1 = OpConstant %float 1
+  %float_0_5 = OpConstant %float 0.5
+    %float_0 = OpConstant %float 0
+         %23 = OpConstantComposite %v4float %float_1 %float_0_5 %float_0 %float_1
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+       %uint = OpTypeInt 32 0
+     %uint_1 = OpConstant %uint 1
+%_arr_float_uint_1 = OpTypeArray %float %uint_1
+%gl_PerVertex = OpTypeStruct %v4float %float %_arr_float_uint_1 %_arr_float_uint_1
+%_ptr_Output_gl_PerVertex = OpTypePointer Output %gl_PerVertex
+          %_ = OpVariable %_ptr_Output_gl_PerVertex Output
+    %v3float = OpTypeVector %float 3
+%_ptr_Input_v3float = OpTypePointer Input %v3float
+          %P = OpVariable %_ptr_Input_v3float Input
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %18 = OpAccessChain %_ptr_Output_v2float %oVert %int_1
+               OpStore %18 %16
+; CHECK-NOT:       OpStore %18 %16
+         %25 = OpAccessChain %_ptr_Output_v4float %oVert %int_0
+               OpStore %25 %23
+; CHECK:           OpStore %25 %23
+         %35 = OpLoad %v3float %P
+         %36 = OpCompositeExtract %float %35 0
+         %37 = OpCompositeExtract %float %35 1
+         %38 = OpCompositeExtract %float %35 2
+         %39 = OpCompositeConstruct %v4float %36 %37 %38 %float_1
+         %40 = OpAccessChain %_ptr_Output_v4float %_ %int_0
+               OpStore %40 %39
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  live_inputs.insert(1);
+  SinglePassRunAndMatch<EliminateDeadOutputStoresPass>(text, true, &live_inputs,
+                                                       &live_builtins);
+}
+
+TEST_F(ElimDeadOutputStoresTest, ArrayedOutput) {
+  // Tests elimination of arrayed output as seen in Tesc shaders.
+  //
+  // #version 450
+  //
+  // layout (vertices = 4) out;
+  //
+  // layout (location = 0) in vec3 N[];
+  // layout (location = 1) in vec3 P[];
+  //
+  // layout (location = 5) out Vertex
+  // {
+  //                 vec4 c;
+  //                 vec3 n;
+  //                 vec3 f[10];
+  // } oVert[];
+  //
+  // void main()
+  // {
+  //                 oVert[gl_InvocationID].c = vec4(1, 0, 0, 1);
+  //                 oVert[gl_InvocationID].n = N[gl_InvocationID];
+  //                 oVert[gl_InvocationID].f[3] = vec3(0, 1, 0);
+  //                 vec4 worldSpacePos = vec4(P[gl_InvocationID], 1);
+  //                 gl_out[gl_InvocationID].gl_Position = worldSpacePos;
+  // }
+  const std::string text = R"(
+               OpCapability Tessellation
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint TessellationControl %main "main" %oVert %gl_InvocationID %N %P %gl_out
+               OpExecutionMode %main OutputVertices 4
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "c"
+               OpMemberName %Vertex 1 "n"
+               OpMemberName %Vertex 2 "f"
+               OpName %oVert "oVert"
+               OpName %gl_InvocationID "gl_InvocationID"
+               OpName %N "N"
+               OpName %P "P"
+               OpName %gl_PerVertex "gl_PerVertex"
+               OpMemberName %gl_PerVertex 0 "gl_Position"
+               OpMemberName %gl_PerVertex 1 "gl_PointSize"
+               OpMemberName %gl_PerVertex 2 "gl_ClipDistance"
+               OpMemberName %gl_PerVertex 3 "gl_CullDistance"
+               OpName %gl_out "gl_out"
+               OpDecorate %Vertex Block
+               OpDecorate %oVert Location 5
+               OpDecorate %gl_InvocationID BuiltIn InvocationId
+               OpDecorate %N Location 0
+               OpDecorate %P Location 1
+               OpMemberDecorate %gl_PerVertex 0 BuiltIn Position
+               OpMemberDecorate %gl_PerVertex 1 BuiltIn PointSize
+               OpMemberDecorate %gl_PerVertex 2 BuiltIn ClipDistance
+               OpMemberDecorate %gl_PerVertex 3 BuiltIn CullDistance
+               OpDecorate %gl_PerVertex Block
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+    %v3float = OpTypeVector %float 3
+       %uint = OpTypeInt 32 0
+    %uint_10 = OpConstant %uint 10
+%_arr_v3float_uint_10 = OpTypeArray %v3float %uint_10
+     %Vertex = OpTypeStruct %v4float %v3float %_arr_v3float_uint_10
+     %uint_4 = OpConstant %uint 4
+%_arr_Vertex_uint_4 = OpTypeArray %Vertex %uint_4
+%_ptr_Output__arr_Vertex_uint_4 = OpTypePointer Output %_arr_Vertex_uint_4
+      %oVert = OpVariable %_ptr_Output__arr_Vertex_uint_4 Output
+        %int = OpTypeInt 32 1
+%_ptr_Input_int = OpTypePointer Input %int
+%gl_InvocationID = OpVariable %_ptr_Input_int Input
+      %int_0 = OpConstant %int 0
+    %float_1 = OpConstant %float 1
+    %float_0 = OpConstant %float 0
+         %24 = OpConstantComposite %v4float %float_1 %float_0 %float_0 %float_1
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+      %int_1 = OpConstant %int 1
+    %uint_32 = OpConstant %uint 32
+%_arr_v3float_uint_32 = OpTypeArray %v3float %uint_32
+%_ptr_Input__arr_v3float_uint_32 = OpTypePointer Input %_arr_v3float_uint_32
+          %N = OpVariable %_ptr_Input__arr_v3float_uint_32 Input
+%_ptr_Input_v3float = OpTypePointer Input %v3float
+%_ptr_Output_v3float = OpTypePointer Output %v3float
+      %int_2 = OpConstant %int 2
+      %int_3 = OpConstant %int 3
+         %42 = OpConstantComposite %v3float %float_0 %float_1 %float_0
+          %P = OpVariable %_ptr_Input__arr_v3float_uint_32 Input
+     %uint_1 = OpConstant %uint 1
+%_arr_float_uint_1 = OpTypeArray %float %uint_1
+%gl_PerVertex = OpTypeStruct %v4float %float %_arr_float_uint_1 %_arr_float_uint_1
+%_arr_gl_PerVertex_uint_4 = OpTypeArray %gl_PerVertex %uint_4
+%_ptr_Output__arr_gl_PerVertex_uint_4 = OpTypePointer Output %_arr_gl_PerVertex_uint_4
+     %gl_out = OpVariable %_ptr_Output__arr_gl_PerVertex_uint_4 Output
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %20 = OpLoad %int %gl_InvocationID
+         %26 = OpAccessChain %_ptr_Output_v4float %oVert %20 %int_0
+               OpStore %26 %24
+; CHECK:           OpStore %26 %24
+         %35 = OpAccessChain %_ptr_Input_v3float %N %20
+         %36 = OpLoad %v3float %35
+         %38 = OpAccessChain %_ptr_Output_v3float %oVert %20 %int_1
+               OpStore %38 %36
+; CHECK-NOT:       OpStore %38 %36
+         %43 = OpAccessChain %_ptr_Output_v3float %oVert %20 %int_2 %int_3
+               OpStore %43 %42
+; CHECK:           OpStore %43 %42
+         %48 = OpAccessChain %_ptr_Input_v3float %P %20
+         %49 = OpLoad %v3float %48
+         %50 = OpCompositeExtract %float %49 0
+         %51 = OpCompositeExtract %float %49 1
+         %52 = OpCompositeExtract %float %49 2
+         %53 = OpCompositeConstruct %v4float %50 %51 %52 %float_1
+         %62 = OpAccessChain %_ptr_Output_v4float %gl_out %20 %int_0
+               OpStore %62 %53
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  live_inputs.insert(5);
+  live_inputs.insert(10);
+  SinglePassRunAndMatch<EliminateDeadOutputStoresPass>(text, true, &live_inputs,
+                                                       &live_builtins);
+}
+
+TEST_F(ElimDeadOutputStoresTest, ArrayedOutputMemberLocs) {
+  // Tests elimination of member location with arrayed output as seen in
+  // Tesc shaders.
+  //
+  // #version 450
+  //
+  // layout (vertices = 4) out;
+  //
+  // layout (location = 0) in vec3 N[];
+  // layout (location = 1) in vec3 P[];
+  //
+  // out Vertex
+  // {
+  //                 layout (location = 1) vec4 c;
+  //                 layout (location = 3) vec3 n;
+  //                 layout (location = 5) vec3 f[10];
+  // } oVert[];
+  //
+  // void main()
+  // {
+  //                 oVert[gl_InvocationID].c = vec4(1, 0, 0, 1);
+  //                 oVert[gl_InvocationID].n = N[gl_InvocationID];
+  //                 oVert[gl_InvocationID].f[3] = vec3(0, 1, 0);
+  //                 vec4 worldSpacePos = vec4(P[gl_InvocationID], 1);
+  //                 gl_out[gl_InvocationID].gl_Position = worldSpacePos;
+  // }
+  const std::string text = R"(
+               OpCapability Tessellation
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint TessellationControl %main "main" %oVert %gl_InvocationID %N %P %gl_out
+               OpExecutionMode %main OutputVertices 4
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "c"
+               OpMemberName %Vertex 1 "n"
+               OpMemberName %Vertex 2 "f"
+               OpName %oVert "oVert"
+               OpName %gl_InvocationID "gl_InvocationID"
+               OpName %N "N"
+               OpName %P "P"
+               OpName %gl_PerVertex "gl_PerVertex"
+               OpMemberName %gl_PerVertex 0 "gl_Position"
+               OpMemberName %gl_PerVertex 1 "gl_PointSize"
+               OpMemberName %gl_PerVertex 2 "gl_ClipDistance"
+               OpMemberName %gl_PerVertex 3 "gl_CullDistance"
+               OpName %gl_out "gl_out"
+               OpMemberDecorate %Vertex 0 Location 1
+               OpMemberDecorate %Vertex 1 Location 3
+               OpMemberDecorate %Vertex 2 Location 5
+               OpDecorate %Vertex Block
+               OpDecorate %gl_InvocationID BuiltIn InvocationId
+               OpDecorate %N Location 0
+               OpDecorate %P Location 1
+               OpMemberDecorate %gl_PerVertex 0 BuiltIn Position
+               OpMemberDecorate %gl_PerVertex 1 BuiltIn PointSize
+               OpMemberDecorate %gl_PerVertex 2 BuiltIn ClipDistance
+               OpMemberDecorate %gl_PerVertex 3 BuiltIn CullDistance
+               OpDecorate %gl_PerVertex Block
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+    %v3float = OpTypeVector %float 3
+       %uint = OpTypeInt 32 0
+    %uint_10 = OpConstant %uint 10
+%_arr_v3float_uint_10 = OpTypeArray %v3float %uint_10
+     %Vertex = OpTypeStruct %v4float %v3float %_arr_v3float_uint_10
+     %uint_4 = OpConstant %uint 4
+%_arr_Vertex_uint_4 = OpTypeArray %Vertex %uint_4
+%_ptr_Output__arr_Vertex_uint_4 = OpTypePointer Output %_arr_Vertex_uint_4
+      %oVert = OpVariable %_ptr_Output__arr_Vertex_uint_4 Output
+        %int = OpTypeInt 32 1
+%_ptr_Input_int = OpTypePointer Input %int
+%gl_InvocationID = OpVariable %_ptr_Input_int Input
+      %int_0 = OpConstant %int 0
+    %float_1 = OpConstant %float 1
+    %float_0 = OpConstant %float 0
+         %24 = OpConstantComposite %v4float %float_1 %float_0 %float_0 %float_1
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+      %int_1 = OpConstant %int 1
+    %uint_32 = OpConstant %uint 32
+%_arr_v3float_uint_32 = OpTypeArray %v3float %uint_32
+%_ptr_Input__arr_v3float_uint_32 = OpTypePointer Input %_arr_v3float_uint_32
+          %N = OpVariable %_ptr_Input__arr_v3float_uint_32 Input
+%_ptr_Input_v3float = OpTypePointer Input %v3float
+%_ptr_Output_v3float = OpTypePointer Output %v3float
+      %int_2 = OpConstant %int 2
+      %int_3 = OpConstant %int 3
+         %42 = OpConstantComposite %v3float %float_0 %float_1 %float_0
+          %P = OpVariable %_ptr_Input__arr_v3float_uint_32 Input
+     %uint_1 = OpConstant %uint 1
+%_arr_float_uint_1 = OpTypeArray %float %uint_1
+%gl_PerVertex = OpTypeStruct %v4float %float %_arr_float_uint_1 %_arr_float_uint_1
+%_arr_gl_PerVertex_uint_4 = OpTypeArray %gl_PerVertex %uint_4
+%_ptr_Output__arr_gl_PerVertex_uint_4 = OpTypePointer Output %_arr_gl_PerVertex_uint_4
+     %gl_out = OpVariable %_ptr_Output__arr_gl_PerVertex_uint_4 Output
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %20 = OpLoad %int %gl_InvocationID
+         %26 = OpAccessChain %_ptr_Output_v4float %oVert %20 %int_0
+               OpStore %26 %24
+;CHECK:            OpStore %26 %24
+         %35 = OpAccessChain %_ptr_Input_v3float %N %20
+         %36 = OpLoad %v3float %35
+         %38 = OpAccessChain %_ptr_Output_v3float %oVert %20 %int_1
+               OpStore %38 %36
+;CHECK-NOT:        OpStore %38 %36
+         %43 = OpAccessChain %_ptr_Output_v3float %oVert %20 %int_2 %int_3
+               OpStore %43 %42
+;CHECK:            OpStore %43 %42
+         %48 = OpAccessChain %_ptr_Input_v3float %P %20
+         %49 = OpLoad %v3float %48
+         %50 = OpCompositeExtract %float %49 0
+         %51 = OpCompositeExtract %float %49 1
+         %52 = OpCompositeExtract %float %49 2
+         %53 = OpCompositeConstruct %v4float %50 %51 %52 %float_1
+         %62 = OpAccessChain %_ptr_Output_v4float %gl_out %20 %int_0
+               OpStore %62 %53
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  live_inputs.insert(1);
+  live_inputs.insert(8);
+  SinglePassRunAndMatch<EliminateDeadOutputStoresPass>(text, true, &live_inputs,
+                                                       &live_builtins);
+}
+
+TEST_F(ElimDeadOutputStoresTest, ScalarBuiltins) {
+  // Tests elimination of scalar builtins as seen in vert shaders.
+  //
+  // #version 460
+  //
+  // layout (location = 0) in vec3 P;
+  //
+  // void main()
+  // {
+  //         gl_Position = vec4(P, 1.0);
+  //         gl_PointSize = 1.0;
+  // }
+  const std::string text = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Vertex %main "main" %_ %P
+               OpSource GLSL 460
+               OpName %main "main"
+               OpName %gl_PerVertex "gl_PerVertex"
+               OpMemberName %gl_PerVertex 0 "gl_Position"
+               OpMemberName %gl_PerVertex 1 "gl_PointSize"
+               OpMemberName %gl_PerVertex 2 "gl_ClipDistance"
+               OpMemberName %gl_PerVertex 3 "gl_CullDistance"
+               OpName %_ ""
+               OpName %P "P"
+               OpMemberDecorate %gl_PerVertex 0 BuiltIn Position
+               OpMemberDecorate %gl_PerVertex 1 BuiltIn PointSize
+               OpMemberDecorate %gl_PerVertex 2 BuiltIn ClipDistance
+               OpMemberDecorate %gl_PerVertex 3 BuiltIn CullDistance
+               OpDecorate %gl_PerVertex Block
+               OpDecorate %P Location 0
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+       %uint = OpTypeInt 32 0
+     %uint_1 = OpConstant %uint 1
+%_arr_float_uint_1 = OpTypeArray %float %uint_1
+%gl_PerVertex = OpTypeStruct %v4float %float %_arr_float_uint_1 %_arr_float_uint_1
+%_ptr_Output_gl_PerVertex = OpTypePointer Output %gl_PerVertex
+          %_ = OpVariable %_ptr_Output_gl_PerVertex Output
+        %int = OpTypeInt 32 1
+      %int_0 = OpConstant %int 0
+    %v3float = OpTypeVector %float 3
+%_ptr_Input_v3float = OpTypePointer Input %v3float
+          %P = OpVariable %_ptr_Input_v3float Input
+    %float_1 = OpConstant %float 1
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+      %int_1 = OpConstant %int 1
+%_ptr_Output_float = OpTypePointer Output %float
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %19 = OpLoad %v3float %P
+         %21 = OpCompositeExtract %float %19 0
+         %22 = OpCompositeExtract %float %19 1
+         %23 = OpCompositeExtract %float %19 2
+         %24 = OpCompositeConstruct %v4float %21 %22 %23 %float_1
+         %26 = OpAccessChain %_ptr_Output_v4float %_ %int_0
+               OpStore %26 %24
+;CHECK:                   OpStore %26 %24
+         %29 = OpAccessChain %_ptr_Output_float %_ %int_1
+               OpStore %29 %float_1
+;CHECK-NOT:               OpStore %29 %float_1
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  // Omit SpvBuiltInPointSize
+  live_builtins.insert(SpvBuiltInClipDistance);
+  live_builtins.insert(SpvBuiltInCullDistance);
+  SinglePassRunAndMatch<EliminateDeadOutputStoresPass>(text, true, &live_inputs,
+                                                       &live_builtins);
+}
+
+TEST_F(ElimDeadOutputStoresTest, ArrayedBuiltins) {
+  // Tests elimination of arrayed builtins as seen in geom, tesc, and tese
+  // shaders.
+  //
+  // #version 460
+  //
+  // layout(triangle_strip, max_vertices = 3) out;
+  // layout(triangles) in;
+  //
+  // void main()
+  // {
+  //         for (int i = 0; i < 3; i++)
+  //         {
+  //                 gl_Position = gl_in[i].gl_Position;
+  //                 gl_PointSize = gl_in[i].gl_PointSize;
+  //
+  //                 EmitVertex();
+  //         }
+  //
+  //         EndPrimitive();
+  // }
+  const std::string text = R"(
+               OpCapability Geometry
+               OpCapability GeometryPointSize
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Geometry %main "main" %_ %gl_in
+               OpExecutionMode %main Triangles
+               OpExecutionMode %main Invocations 1
+               OpExecutionMode %main OutputTriangleStrip
+               OpExecutionMode %main OutputVertices 3
+               OpSource GLSL 460
+               OpName %main "main"
+               OpName %i "i"
+               OpName %gl_PerVertex "gl_PerVertex"
+               OpMemberName %gl_PerVertex 0 "gl_Position"
+               OpMemberName %gl_PerVertex 1 "gl_PointSize"
+               OpMemberName %gl_PerVertex 2 "gl_ClipDistance"
+               OpMemberName %gl_PerVertex 3 "gl_CullDistance"
+               OpName %_ ""
+               OpName %gl_PerVertex_0 "gl_PerVertex"
+               OpMemberName %gl_PerVertex_0 0 "gl_Position"
+               OpMemberName %gl_PerVertex_0 1 "gl_PointSize"
+               OpMemberName %gl_PerVertex_0 2 "gl_ClipDistance"
+               OpMemberName %gl_PerVertex_0 3 "gl_CullDistance"
+               OpName %gl_in "gl_in"
+               OpMemberDecorate %gl_PerVertex 0 BuiltIn Position
+               OpMemberDecorate %gl_PerVertex 1 BuiltIn PointSize
+               OpMemberDecorate %gl_PerVertex 2 BuiltIn ClipDistance
+               OpMemberDecorate %gl_PerVertex 3 BuiltIn CullDistance
+               OpDecorate %gl_PerVertex Block
+               OpMemberDecorate %gl_PerVertex_0 0 BuiltIn Position
+               OpMemberDecorate %gl_PerVertex_0 1 BuiltIn PointSize
+               OpMemberDecorate %gl_PerVertex_0 2 BuiltIn ClipDistance
+               OpMemberDecorate %gl_PerVertex_0 3 BuiltIn CullDistance
+               OpDecorate %gl_PerVertex_0 Block
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+        %int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+      %int_0 = OpConstant %int 0
+      %int_3 = OpConstant %int 3
+       %bool = OpTypeBool
+      %float = OpTypeFloat 32
+    %v4float = OpTypeVector %float 4
+       %uint = OpTypeInt 32 0
+     %uint_1 = OpConstant %uint 1
+%_arr_float_uint_1 = OpTypeArray %float %uint_1
+%gl_PerVertex = OpTypeStruct %v4float %float %_arr_float_uint_1 %_arr_float_uint_1
+%_ptr_Output_gl_PerVertex = OpTypePointer Output %gl_PerVertex
+          %_ = OpVariable %_ptr_Output_gl_PerVertex Output
+%gl_PerVertex_0 = OpTypeStruct %v4float %float %_arr_float_uint_1 %_arr_float_uint_1
+     %uint_3 = OpConstant %uint 3
+%_arr_gl_PerVertex_0_uint_3 = OpTypeArray %gl_PerVertex_0 %uint_3
+%_ptr_Input__arr_gl_PerVertex_0_uint_3 = OpTypePointer Input %_arr_gl_PerVertex_0_uint_3
+      %gl_in = OpVariable %_ptr_Input__arr_gl_PerVertex_0_uint_3 Input
+%_ptr_Input_v4float = OpTypePointer Input %v4float
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+      %int_1 = OpConstant %int 1
+%_ptr_Input_float = OpTypePointer Input %float
+%_ptr_Output_float = OpTypePointer Output %float
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+          %i = OpVariable %_ptr_Function_int Function
+               OpStore %i %int_0
+               OpBranch %10
+         %10 = OpLabel
+               OpLoopMerge %12 %13 None
+               OpBranch %14
+         %14 = OpLabel
+         %15 = OpLoad %int %i
+         %18 = OpSLessThan %bool %15 %int_3
+               OpBranchConditional %18 %11 %12
+         %11 = OpLabel
+         %32 = OpLoad %int %i
+         %34 = OpAccessChain %_ptr_Input_v4float %gl_in %32 %int_0
+         %35 = OpLoad %v4float %34
+         %37 = OpAccessChain %_ptr_Output_v4float %_ %int_0
+               OpStore %37 %35
+;CHECK:                   OpStore %37 %35
+         %39 = OpLoad %int %i
+         %41 = OpAccessChain %_ptr_Input_float %gl_in %39 %int_1
+         %42 = OpLoad %float %41
+         %44 = OpAccessChain %_ptr_Output_float %_ %int_1
+               OpStore %44 %42
+;CHECK-NOT:               OpStore %44 %42
+               OpEmitVertex
+               OpBranch %13
+         %13 = OpLabel
+         %45 = OpLoad %int %i
+         %46 = OpIAdd %int %45 %int_1
+               OpStore %i %46
+               OpBranch %10
+         %12 = OpLabel
+               OpEndPrimitive
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  // Omit SpvBuiltInPointSize
+  live_builtins.insert(SpvBuiltInClipDistance);
+  live_builtins.insert(SpvBuiltInCullDistance);
+  SinglePassRunAndMatch<EliminateDeadOutputStoresPass>(text, true, &live_inputs,
+                                                       &live_builtins);
+}
+
+TEST_F(ElimDeadOutputStoresTest, ArrayedOutputPatchLocs) {
+  // Tests elimination of location with arrayed patch output as seen in
+  // Tesc shaders.
+  //
+  // #version 450 core
+  //
+  // layout(vertices = 4) out;
+  //
+  // layout(location=0) patch out float patchOut0[2];
+  // layout(location=2) patch out float patchOut1[2];
+  //
+  // void main()
+  // {
+  //     patchOut0[1] = 0.0;  // Dead loc 1
+  //     patchOut1[1] = 1.0;  // Live loc 3
+  // }
+  const std::string text = R"(
+               OpCapability Tessellation
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint TessellationControl %main "main" %patchOut0 %patchOut1
+               OpExecutionMode %main OutputVertices 4
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %patchOut0 "patchOut0"
+               OpName %patchOut1 "patchOut1"
+               OpDecorate %patchOut0 Patch
+               OpDecorate %patchOut0 Location 0
+               OpDecorate %patchOut1 Patch
+               OpDecorate %patchOut1 Location 2
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %float = OpTypeFloat 32
+       %uint = OpTypeInt 32 0
+     %uint_2 = OpConstant %uint 2
+%_arr_float_uint_2 = OpTypeArray %float %uint_2
+%_ptr_Output__arr_float_uint_2 = OpTypePointer Output %_arr_float_uint_2
+  %patchOut0 = OpVariable %_ptr_Output__arr_float_uint_2 Output
+        %int = OpTypeInt 32 1
+      %int_1 = OpConstant %int 1
+    %float_0 = OpConstant %float 0
+%_ptr_Output_float = OpTypePointer Output %float
+  %patchOut1 = OpVariable %_ptr_Output__arr_float_uint_2 Output
+    %float_1 = OpConstant %float 1
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %16 = OpAccessChain %_ptr_Output_float %patchOut0 %int_1
+               OpStore %16 %float_0
+;CHECK-NOT:               OpStore %16 %float_0
+         %19 = OpAccessChain %_ptr_Output_float %patchOut1 %int_1
+               OpStore %19 %float_1
+;CHECK:                   OpStore %19 %float_1
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  live_inputs.insert(3);
+  SinglePassRunAndMatch<EliminateDeadOutputStoresPass>(text, true, &live_inputs,
+                                                       &live_builtins);
+}
+
+TEST_F(ElimDeadOutputStoresTest, VertMultipleLocationsF16) {
+  // #version 450
+  //
+  // layout(location = 2) out Vertex
+  // {
+  //         f16vec4 color0;
+  //         f16vec4 color1;
+  //         f16vec4 color2[3];
+  // } oVert;
+  //
+  // void main()
+  // {
+  //     oVert.color0 = f16vec4(0.0,0.0,0.0,0.0);
+  //     oVert.color1 = f16vec4(0.1,0.0,0.0,0.0);
+  //     oVert.color2[0] = f16vec4(0.2,0.0,0.0,0.0);
+  //     oVert.color2[1] = f16vec4(0.3,0.0,0.0,0.0);
+  //     oVert.color2[2] = f16vec4(0.4,0.0,0.0,0.0);
+  // }
+  const std::string text = R"(
+               OpCapability Shader
+               OpCapability Float16
+               OpCapability StorageInputOutput16
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Vertex %main "main" %oVert
+               OpSource GLSL 450
+               OpName %main "main"
+               OpName %Vertex "Vertex"
+               OpMemberName %Vertex 0 "color0"
+               OpMemberName %Vertex 1 "color1"
+               OpMemberName %Vertex 2 "color2"
+               OpName %oVert "oVert"
+               OpDecorate %Vertex Block
+               OpDecorate %oVert Location 2
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+      %half = OpTypeFloat 32
+    %v4half = OpTypeVector %half 4
+       %uint = OpTypeInt 32 0
+     %uint_3 = OpConstant %uint 3
+%_arr_v4half_uint_3 = OpTypeArray %v4half %uint_3
+     %Vertex = OpTypeStruct %v4half %v4half %_arr_v4half_uint_3
+%_ptr_Output_Vertex = OpTypePointer Output %Vertex
+      %oVert = OpVariable %_ptr_Output_Vertex Output
+        %int = OpTypeInt 32 1
+      %int_0 = OpConstant %int 0
+    %half_0 = OpConstant %half 0
+         %17 = OpConstantComposite %v4half %half_0 %half_0 %half_0 %half_0
+%_ptr_Output_v4half = OpTypePointer Output %v4half
+      %int_1 = OpConstant %int 1
+%half_0_100000001 = OpConstant %half 0.100000001
+         %22 = OpConstantComposite %v4half %half_0_100000001 %half_0 %half_0 %half_0
+      %int_2 = OpConstant %int 2
+%half_0_200000003 = OpConstant %half 0.200000003
+         %26 = OpConstantComposite %v4half %half_0_200000003 %half_0 %half_0 %half_0
+%half_0_300000012 = OpConstant %half 0.300000012
+         %29 = OpConstantComposite %v4half %half_0_300000012 %half_0 %half_0 %half_0
+%half_0_400000006 = OpConstant %half 0.400000006
+         %32 = OpConstantComposite %v4half %half_0_400000006 %half_0 %half_0 %half_0
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+         %19 = OpAccessChain %_ptr_Output_v4half %oVert %int_0
+               OpStore %19 %17
+;CHECK:            OpStore %19 %17
+         %23 = OpAccessChain %_ptr_Output_v4half %oVert %int_1
+               OpStore %23 %22
+;CHECK-NOT:        OpStore %23 %22
+         %27 = OpAccessChain %_ptr_Output_v4half %oVert %int_2 %int_0
+               OpStore %27 %26
+;CHECK-NOT:        OpStore %27 %26
+         %30 = OpAccessChain %_ptr_Output_v4half %oVert %int_2 %int_1
+               OpStore %30 %29
+;CHECK:            OpStore %30 %29
+         %33 = OpAccessChain %_ptr_Output_v4half %oVert %int_2 %int_2
+               OpStore %33 %32
+;CHECK-NOT:        OpStore %33 %32
+               OpReturn
+               OpFunctionEnd
+)";
+
+  SetTargetEnv(SPV_ENV_VULKAN_1_3);
+  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+
+  std::unordered_set<uint32_t> live_inputs;
+  std::unordered_set<uint32_t> live_builtins;
+  live_inputs.insert(2);
+  live_inputs.insert(5);
+  SinglePassRunAndMatch<EliminateDeadOutputStoresPass>(text, true, &live_inputs,
+                                                       &live_builtins);
+}
+
+}  // namespace
+}  // namespace opt
+}  // namespace spvtools