Make use of the instruction folder.

Implementation of the simplification pass.

- Create pass that calls the instruction folder on each instruction and
  propagate instructions that fold to a copy.  This will do copy
  propagation as well.

- Did not use the propagator engine because I want to modify the instruction
  as we go along.

- Change folding to not allocate new instructions, but make changes in
  place.  This change had a big impact on compile time.

- Add simplification pass to the legalization passes in place of
  insert-extract elimination.

- Added test cases for new folding rules.

- Added tests for the simplification pass

- Added a method to the CFG to apply a function to the basic blocks in
  reverse post order.

Contributes to #1164.

10 files changed, 414 insertions, 50 deletions

diff --git a/source/opt/CMakeLists.txt b/source/opt/CMakeLists.txt
index c02086cc..f43ac777 100644
--- a/source/opt/CMakeLists.txt
+++ b/source/opt/CMakeLists.txt
@@ -70,6 +70,7 @@ add_library(SPIRV-Tools-opt
   replace_invalid_opc.h
   scalar_replacement_pass.h
   set_spec_constant_default_value_pass.h
+  simplification_pass.h
   strength_reduction_pass.h
   strip_debug_info_pass.h
   tree_iterator.h
@@ -135,6 +136,7 @@ add_library(SPIRV-Tools-opt
   replace_invalid_opc.cpp
   scalar_replacement_pass.cpp
   set_spec_constant_default_value_pass.cpp
+  simplification_pass.cpp
   strength_reduction_pass.cpp
   strip_debug_info_pass.cpp
   type_manager.cpp
diff --git a/source/opt/cfg.cpp b/source/opt/cfg.cpp
index c2dd235b..404d1924 100644
--- a/source/opt/cfg.cpp
+++ b/source/opt/cfg.cpp
@@ -87,6 +87,19 @@ void CFG::ComputeStructuredOrder(ir::Function* func, ir::BasicBlock* root,
       root, get_structured_successors, ignore_block, post_order, ignore_edge);
 }
 
+void CFG::ForEachBlockInReversePostOrder(
+    BasicBlock* bb, const std::function<void(BasicBlock*)>& f) {
+  std::vector<BasicBlock*> po;
+  std::unordered_set<BasicBlock*> seen;
+  ComputePostOrderTraversal(bb, &po, &seen);
+
+  for (auto current_bb = po.rbegin(); current_bb != po.rend(); ++current_bb) {
+    if (!IsPseudoExitBlock(*current_bb) && !IsPseudoEntryBlock(*current_bb)) {
+      f(*current_bb);
+    }
+  }
+}
+
 void CFG::ComputeStructuredSuccessors(ir::Function* func) {
   block2structured_succs_.clear();
   for (auto& blk : *func) {
@@ -111,5 +124,18 @@ void CFG::ComputeStructuredSuccessors(ir::Function* func) {
   }
 }
 
+void CFG::ComputePostOrderTraversal(BasicBlock* bb, vector<BasicBlock*>* order,
+                                    unordered_set<BasicBlock*>* seen) {
+  seen->insert(bb);
+  static_cast<const BasicBlock*>(bb)->ForEachSuccessorLabel(
+      [&order, &seen, this](const uint32_t sbid) {
+        BasicBlock* succ_bb = id2block_[sbid];
+        if (!seen->count(succ_bb)) {
+          ComputePostOrderTraversal(succ_bb, order, seen);
+        }
+      });
+  order->push_back(bb);
+}
+
 }  // namespace ir
 }  // namespace spvtools
diff --git a/source/opt/cfg.h b/source/opt/cfg.h
index 138aa0a6..53dddd23 100644
--- a/source/opt/cfg.h
+++ b/source/opt/cfg.h
@@ -19,6 +19,7 @@
 
 #include <list>
 #include <unordered_map>
+#include <unordered_set>
 
 namespace spvtools {
 namespace ir {
@@ -68,6 +69,12 @@ class CFG {
   void ComputeStructuredOrder(ir::Function* func, ir::BasicBlock* root,
                               std::list<ir::BasicBlock*>* order);
 
+  // Applies |f| to the basic block in reverse post order starting with |bb|.
+  // Note that basic blocks that cannot be reached from |bb| node will not be
+  // processed.
+  void ForEachBlockInReversePostOrder(
+      BasicBlock* bb, const std::function<void(BasicBlock*)>& f);
+
   // Registers |blk| as a basic block in the cfg, this also updates the
   // predecessor lists of each successor of |blk|.
   void RegisterBlock(ir::BasicBlock* blk) {
@@ -101,6 +108,13 @@ class CFG {
   // ignored by DFS.
   void ComputeStructuredSuccessors(ir::Function* func);
 
+  // Computes the post-order traversal of the cfg starting at |bb| skipping
+  // nodes in |seen|.  The order of the traversal is appended to |order|, and
+  // all nodes in the traversal are added to |seen|.
+  void ComputePostOrderTraversal(BasicBlock* bb,
+                                 std::vector<BasicBlock*>* order,
+                                 std::unordered_set<BasicBlock*>* seen);
+
   // Module for this CFG.
   ir::Module* module_;
 
diff --git a/source/opt/dead_insert_elim_pass.h b/source/opt/dead_insert_elim_pass.h
index df13c0cc..5ce2aefa 100644
--- a/source/opt/dead_insert_elim_pass.h
+++ b/source/opt/dead_insert_elim_pass.h
@@ -36,7 +36,7 @@ namespace opt {
 class DeadInsertElimPass : public MemPass {
  public:
   DeadInsertElimPass();
-  const char* name() const override { return "eliminate-dead-insert"; }
+  const char* name() const override { return "eliminate-dead-inserts"; }
   Status Process(ir::IRContext*) override;
 
  private:
diff --git a/source/opt/fold.cpp b/source/opt/fold.cpp
index a6c93f89..04c04469 100644
--- a/source/opt/fold.cpp
+++ b/source/opt/fold.cpp
@@ -182,10 +182,10 @@ uint32_t OperateWords(SpvOp opcode,
   }
 }
 
-bool FoldInstructionInternal(ir::Instruction* inst,
-                             std::function<uint32_t(uint32_t)> id_map) {
+bool FoldInstructionInternal(ir::Instruction* inst) {
   ir::IRContext* context = inst->context();
-  ir::Instruction* folded_inst = FoldInstructionToConstant(inst, id_map);
+  auto identity_map = [](uint32_t id) { return id; };
+  ir::Instruction* folded_inst = FoldInstructionToConstant(inst, identity_map);
   if (folded_inst != nullptr) {
     inst->SetOpcode(SpvOpCopyObject);
     inst->SetInOperands({{SPV_OPERAND_TYPE_ID, {folded_inst->result_id()}}});
@@ -201,8 +201,7 @@ bool FoldInstructionInternal(ir::Instruction* inst,
     if (operand->type != SPV_OPERAND_TYPE_ID) {
       constants.push_back(nullptr);
     } else {
-      uint32_t id = id_map(operand->words[0]);
-      inst->SetInOperand(i, {id});
+      uint32_t id = operand->words[0];
       const analysis::Constant* constant =
           const_manger->FindDeclaredConstant(id);
       constants.push_back(constant);
@@ -660,29 +659,13 @@ bool IsFoldableType(ir::Instruction* type_inst) {
   return false;
 }
 
-ir::Instruction* FoldInstruction(ir::Instruction* inst,
-                                 std::function<uint32_t(uint32_t)> id_map) {
-  ir::IRContext* context = inst->context();
+bool FoldInstruction(ir::Instruction* inst) {
   bool modified = false;
-  std::unique_ptr<ir::Instruction> folded_inst(inst->Clone(context));
-  while (FoldInstructionInternal(&*folded_inst, id_map)) {
+  ir::Instruction* folded_inst(inst);
+  while (FoldInstructionInternal(&*folded_inst)) {
     modified = true;
   }
-
-  if (modified) {
-    if (folded_inst->opcode() == SpvOpCopyObject) {
-      analysis::DefUseManager* def_use_mgr = context->get_def_use_mgr();
-      return def_use_mgr->GetDef(folded_inst->GetSingleWordInOperand(0));
-    } else {
-      InstructionBuilder ir_builder(
-          context, inst,
-          ir::IRContext::kAnalysisDefUse |
-              ir::IRContext::kAnalysisInstrToBlockMapping);
-      folded_inst->SetResultId(context->TakeNextId());
-      return ir_builder.AddInstruction(std::move(folded_inst));
-    }
-  }
-  return nullptr;
+  return modified;
 }
 
 }  // namespace opt
diff --git a/source/opt/fold.h b/source/opt/fold.h
index 0438ccfe..439ed2b6 100644
--- a/source/opt/fold.h
+++ b/source/opt/fold.h
@@ -15,12 +15,12 @@
 #ifndef LIBSPIRV_UTIL_FOLD_H_
 #define LIBSPIRV_UTIL_FOLD_H_
 
-#include "constants.h"
-#include "def_use_manager.h"
-
 #include <cstdint>
 #include <vector>
 
+#include "constants.h"
+#include "def_use_manager.h"
+
 namespace spvtools {
 namespace opt {
 
@@ -75,26 +75,18 @@ bool IsFoldableType(ir::Instruction* type_inst);
 ir::Instruction* FoldInstructionToConstant(
     ir::Instruction* inst, std::function<uint32_t(uint32_t)> id_map);
 
-// Tries to fold |inst| to a simpler instruction that computes the same value,
-// when the input ids to |inst| have been substituted using |id_map|.  Returns a
-// pointer to the simplified instruction if successful.  If necessary, a new
-// instruction is created and placed in the global values section, for
-// constants, or after |inst| for other instructions.
+// Returns true if |inst| can be folded into a simpler instruction.
+// If |inst| can be simplified, |inst| is overwritten with the simplified
+// instruction reusing the same result id.
 //
-// |inst| must be an instruction that exists in the body of a function.
+// If |inst| is simplified, it is possible that the resulting code in invalid
+// because the instruction is in a bad location.  Callers of this function have
+// to handle the following cases:
 //
-// |id_map| is a function that takes one result id and returns another.  It can
-// be used for things like CCP where it is known that some ids contain a
-// constant, but the instruction itself has not been updated yet.  This can map
-// those ids to the appropriate constants.
-ir::Instruction* FoldInstruction(ir::Instruction* inst,
-                                 std::function<uint32_t(uint32_t)> id_map);
-
-// The same as above when |id_map| is the identity function.
-inline ir::Instruction* FoldInstruction(ir::Instruction* inst) {
-  auto identity_map = [](uint32_t id) { return id; };
-  return FoldInstruction(inst, identity_map);
-}
+// 1) An OpPhi becomes and OpCopyObject - If there are OpPhi instruction after
+//    |inst| in a basic block then this is invalid.  The caller must fix this
+//    up.
+bool FoldInstruction(ir::Instruction* inst);
 
 }  // namespace opt
 }  // namespace spvtools
diff --git a/source/opt/folding_rules.cpp b/source/opt/folding_rules.cpp
index 728ad0cd..ed33dfd6 100644
--- a/source/opt/folding_rules.cpp
+++ b/source/opt/folding_rules.cpp
@@ -31,7 +31,7 @@ FoldingRule IntMultipleBy1() {
         continue;
       }
       const analysis::IntConstant* int_constant = constants[i]->AsIntConstant();
-      if (int_constant->GetU32BitValue() == 1) {
+      if (int_constant && int_constant->GetU32BitValue() == 1) {
         inst->SetOpcode(SpvOpCopyObject);
         inst->SetInOperands(
             {{SPV_OPERAND_TYPE_ID, {inst->GetSingleWordInOperand(1 - i)}}});
@@ -42,6 +42,142 @@ FoldingRule IntMultipleBy1() {
   };
 }
 
+FoldingRule CompositeConstructFeedingExtract() {
+  return [](ir::Instruction* inst,
+            const std::vector<const analysis::Constant*>&) {
+    // If the input to an OpCompositeExtract is an OpCompositeConstruct,
+    // then we can simply use the appropriate element in the construction.
+    assert(inst->opcode() == SpvOpCompositeExtract &&
+           "Wrong opcode.  Should be OpCompositeExtract.");
+    analysis::DefUseManager* def_use_mgr = inst->context()->get_def_use_mgr();
+    analysis::TypeManager* type_mgr = inst->context()->get_type_mgr();
+    uint32_t cid = inst->GetSingleWordInOperand(kExtractCompositeIdInIdx);
+    ir::Instruction* cinst = def_use_mgr->GetDef(cid);
+
+    if (cinst->opcode() != SpvOpCompositeConstruct) {
+      return false;
+    }
+
+    std::vector<ir::Operand> operands;
+    analysis::Type* composite_type = type_mgr->GetType(cinst->type_id());
+    if (composite_type->AsVector() == nullptr) {
+      // Get the element being extracted from the OpCompositeConstruct
+      // Since it is not a vector, it is simple to extract the single element.
+      uint32_t element_index = inst->GetSingleWordInOperand(1);
+      uint32_t element_id = cinst->GetSingleWordInOperand(element_index);
+      operands.push_back({SPV_OPERAND_TYPE_ID, {element_id}});
+
+      // Add the remaining indices for extraction.
+      for (uint32_t i = 2; i < inst->NumInOperands(); ++i) {
+        operands.push_back(
+            {SPV_OPERAND_TYPE_ID, {inst->GetSingleWordInOperand(i)}});
+      }
+
+    } else {
+      // With vectors we have to handle the case where it is concatenating
+      // vectors.
+      assert(inst->NumInOperands() == 2 &&
+             "Expecting a vector of scalar values.");
+
+      uint32_t element_index = inst->GetSingleWordInOperand(1);
+      for (uint32_t construct_index = 0;
+           construct_index < cinst->NumInOperands(); ++construct_index) {
+        uint32_t element_id = cinst->GetSingleWordInOperand(construct_index);
+        ir::Instruction* element_def = def_use_mgr->GetDef(element_id);
+        analysis::Vector* element_type =
+            type_mgr->GetType(element_def->type_id())->AsVector();
+        if (element_type) {
+          uint32_t vector_size = element_type->element_count();
+          if (vector_size < element_index) {
+            // The element we want comes after this vector.
+            element_index -= vector_size;
+          } else {
+            // We want an element of this vector.
+            operands.push_back({SPV_OPERAND_TYPE_ID, {element_id}});
+            operands.push_back(
+                {SPV_OPERAND_TYPE_LITERAL_INTEGER, {element_index}});
+            break;
+          }
+        } else {
+          if (element_index == 0) {
+            // This is a scalar, and we this is the element we are extracting.
+            operands.push_back({SPV_OPERAND_TYPE_ID, {element_id}});
+            break;
+          } else {
+            // Skip over this scalar value.
+            --element_index;
+          }
+        }
+      }
+    }
+
+    // If there were no extra indices, then we have the final object.  No need
+    // to extract even more.
+    if (operands.size() == 1) {
+      inst->SetOpcode(SpvOpCopyObject);
+    }
+
+    inst->SetInOperands(std::move(operands));
+    return true;
+  };
+}
+
+FoldingRule CompositeExtractFeedingConstruct() {
+  // If the OpCompositeConstruct is simply putting back together elements that
+  // where extracted from the same souce, we can simlpy reuse the source.
+  //
+  // This is a common code pattern because of the way that scalar replacement
+  // works.
+  return [](ir::Instruction* inst,
+            const std::vector<const analysis::Constant*>&) {
+    assert(inst->opcode() == SpvOpCompositeConstruct &&
+           "Wrong opcode.  Should be OpCompositeConstruct.");
+    analysis::DefUseManager* def_use_mgr = inst->context()->get_def_use_mgr();
+    uint32_t original_id = 0;
+
+    // Check each element to make sure they are:
+    // - extractions
+    // - extracting the same position they are inserting
+    // - all extract from the same id.
+    for (uint32_t i = 0; i < inst->NumInOperands(); ++i) {
+      uint32_t element_id = inst->GetSingleWordInOperand(i);
+      ir::Instruction* element_inst = def_use_mgr->GetDef(element_id);
+
+      if (element_inst->opcode() != SpvOpCompositeExtract) {
+        return false;
+      }
+
+      if (element_inst->NumInOperands() != 2) {
+        return false;
+      }
+
+      if (element_inst->GetSingleWordInOperand(1) != i) {
+        return false;
+      }
+
+      if (i == 0) {
+        original_id =
+            element_inst->GetSingleWordInOperand(kExtractCompositeIdInIdx);
+      } else if (original_id != element_inst->GetSingleWordInOperand(
+                                    kExtractCompositeIdInIdx)) {
+        return false;
+      }
+    }
+
+    // The last check it to see that the object being extracted from is the
+    // correct type.
+    ir::Instruction* original_inst = def_use_mgr->GetDef(original_id);
+    if (original_inst->type_id() != inst->type_id()) {
+      return false;
+    }
+
+    // Simplify by using the original object.
+    inst->SetOpcode(SpvOpCopyObject);
+    inst->SetInOperands({{SPV_OPERAND_TYPE_ID, {original_id}}});
+    return true;
+  };
+}
+
 FoldingRule InsertFeedingExtract() {
   return [](ir::Instruction* inst,
             const std::vector<const analysis::Constant*>&) {
@@ -113,6 +249,51 @@ FoldingRule InsertFeedingExtract() {
     return true;
   };
 }
+
+FoldingRule RedundantPhi() {
+  // An OpPhi instruction where all values are the same or the result of the phi
+  // itself, can be replaced by the value itself.
+  return
+      [](ir::Instruction* inst, const std::vector<const analysis::Constant*>&) {
+        assert(inst->opcode() == SpvOpPhi && "Wrong opcode.  Should be OpPhi.");
+
+        ir::IRContext* context = inst->context();
+        analysis::DefUseManager* def_use_mgr = context->get_def_use_mgr();
+
+        uint32_t incoming_value = 0;
+
+        for (uint32_t i = 0; i < inst->NumInOperands(); i += 2) {
+          uint32_t op_id = inst->GetSingleWordInOperand(i);
+          if (op_id == inst->result_id()) {
+            continue;
+          }
+
+          ir::Instruction* op_inst = def_use_mgr->GetDef(op_id);
+          if (op_inst->opcode() == SpvOpUndef) {
+            // TODO: We should be able to still use op_id if we know that
+            // the definition of op_id dominates |inst|.
+            return false;
+          }
+
+          if (incoming_value == 0) {
+            incoming_value = op_id;
+          } else if (op_id != incoming_value) {
+            // Found two possible value.  Can't simplify.
+            return false;
+          }
+        }
+
+        if (incoming_value == 0) {
+          // Code looks invalid.  Don't do anything.
+          return false;
+        }
+
+        // We have a single incoming value.  Simplify using that value.
+        inst->SetOpcode(SpvOpCopyObject);
+        inst->SetInOperands({{SPV_OPERAND_TYPE_ID, {incoming_value}}});
+        return true;
+      };
+}
 }  // namespace
 
 spvtools::opt::FoldingRules::FoldingRules() {
@@ -121,9 +302,14 @@ spvtools::opt::FoldingRules::FoldingRules() {
   // applies to the instruction, the rest of the rules will not be attempted.
   // Take that into consideration.
 
-  rules[SpvOpIMul].push_back(IntMultipleBy1());
+  rules[SpvOpCompositeConstruct].push_back(CompositeExtractFeedingConstruct());
 
   rules[SpvOpCompositeExtract].push_back(InsertFeedingExtract());
+  rules[SpvOpCompositeExtract].push_back(CompositeConstructFeedingExtract());
+
+  rules[SpvOpIMul].push_back(IntMultipleBy1());
+
+  rules[SpvOpPhi].push_back(RedundantPhi());
 }
 }  // namespace opt
 }  // namespace spvtools
diff --git a/source/opt/optimizer.cpp b/source/opt/optimizer.cpp
index 31f42ae0..bdcc6840 100644
--- a/source/opt/optimizer.cpp
+++ b/source/opt/optimizer.cpp
@@ -18,6 +18,7 @@
 #include "make_unique.h"
 #include "pass_manager.h"
 #include "passes.h"
+#include "simplification_pass.h"
 
 namespace spvtools {
 
@@ -103,7 +104,7 @@ Optimizer& Optimizer::RegisterLegalizationPasses() {
           .RegisterPass(CreateLocalMultiStoreElimPass())
           // Copy propagate members.  Cleans up code sequences generated by
           // scalar replacement.
-          .RegisterPass(CreateInsertExtractElimPass())
+          .RegisterPass(CreateSimplificationPass())
           // May need loop unrolling here see
           // https://github.com/Microsoft/DirectXShaderCompiler/pull/930
           .RegisterPass(CreateDeadBranchElimPass())
@@ -379,4 +380,9 @@ Optimizer::PassToken CreateReplaceInvalidOpcodePass() {
   return MakeUnique<Optimizer::PassToken::Impl>(
       MakeUnique<opt::ReplaceInvalidOpcodePass>());
 }
+
+Optimizer::PassToken CreateSimplificationPass() {
+  return MakeUnique<Optimizer::PassToken::Impl>(
+      MakeUnique<opt::SimplificationPass>());
+}
 }  // namespace spvtools
diff --git a/source/opt/simplification_pass.cpp b/source/opt/simplification_pass.cpp
new file mode 100644
index 00000000..47706e8f
--- /dev/null
+++ b/source/opt/simplification_pass.cpp
@@ -0,0 +1,114 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "simplification_pass.h"
+
+#include <set>
+#include <unordered_set>
+#include <vector>
+
+#include "fold.h"
+
+namespace spvtools {
+namespace opt {
+
+Pass::Status SimplificationPass::Process(ir::IRContext* c) {
+  InitializeProcessing(c);
+  bool modified = false;
+
+  for (ir::Function& function : *get_module()) {
+    modified |= SimplifyFunction(&function);
+  }
+  return (modified ? Status::SuccessWithChange : Status::SuccessWithoutChange);
+}
+
+bool SimplificationPass::SimplifyFunction(ir::Function* function) {
+  bool modified = false;
+  // Phase 1: Traverse all instructions in dominance order.
+  // The second phase will only be on the instructions whose inputs have changed
+  // after being processed during phase 1.  Since OpPhi instructions are the
+  // only instructions whose inputs do not necessarily dominate the use, we keep
+  // track of the OpPhi instructions already seen, and add them to the work list
+  // for phase 2 when needed.
+  std::vector<ir::Instruction*> work_list;
+  std::unordered_set<ir::Instruction*> process_phis;
+  std::unordered_set<ir::Instruction*> inst_to_kill;
+  std::unordered_set<ir::Instruction*> in_work_list;
+
+  cfg()->ForEachBlockInReversePostOrder(
+      function->entry().get(),
+      [&modified, &process_phis, &work_list, &in_work_list, &inst_to_kill,
+       this](ir::BasicBlock* bb) {
+        for (ir::Instruction* inst = &*bb->begin(); inst;
+             inst = inst->NextNode()) {
+          if (inst->opcode() == SpvOpPhi) {
+            process_phis.insert(inst);
+          }
+
+          if (inst->opcode() == SpvOpCopyObject || FoldInstruction(inst)) {
+            modified = true;
+            context()->AnalyzeUses(inst);
+            get_def_use_mgr()->ForEachUser(inst, [&work_list, &process_phis,
+                                                  &in_work_list](
+                                                     ir::Instruction* use) {
+              if (process_phis.count(use) && in_work_list.insert(use).second) {
+                work_list.push_back(use);
+              }
+            });
+            if (inst->opcode() == SpvOpCopyObject) {
+              context()->ReplaceAllUsesWith(inst->result_id(),
+                                            inst->GetSingleWordInOperand(0));
+              inst_to_kill.insert(inst);
+              in_work_list.insert(inst);
+            }
+          }
+        }
+      });
+
+  // Phase 2: process the instructions in the work list until all of the work is
+  //          done.  This time we add all users to the work list because phase 1
+  //          has already finished.
+  for (size_t i = 0; i < work_list.size(); ++i) {
+    ir::Instruction* inst = work_list[i];
+    in_work_list.erase(inst);
+    if (FoldInstruction(inst)) {
+      modified = true;
+      context()->AnalyzeUses(inst);
+      get_def_use_mgr()->ForEachUser(
+          inst, [&work_list, &in_work_list](ir::Instruction* use) {
+            if (!use->IsDecoration() && use->opcode() != SpvOpName &&
+                in_work_list.insert(use).second) {
+              work_list.push_back(use);
+            }
+          });
+
+      if (inst->opcode() == SpvOpCopyObject) {
+        context()->ReplaceAllUsesWith(inst->result_id(),
+                                      inst->GetSingleWordInOperand(0));
+        inst_to_kill.insert(inst);
+        in_work_list.insert(inst);
+      }
+    }
+  }
+
+  // Phase 3: Kill instructions we know are no longer needed.
+  for (ir::Instruction* inst : inst_to_kill) {
+    context()->KillInst(inst);
+  }
+
+  return modified;
+}
+
+}  // namespace opt
+}  // namespace spvtools
diff --git a/source/opt/simplification_pass.h b/source/opt/simplification_pass.h
new file mode 100644
index 00000000..ff0e3be1
--- /dev/null
+++ b/source/opt/simplification_pass.h
@@ -0,0 +1,41 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef LIBSPIRV_OPT_SIMPLIFICATION_PASS_H_
+#define LIBSPIRV_OPT_SIMPLIFICATION_PASS_H_
+
+#include "function.h"
+#include "ir_context.h"
+#include "pass.h"
+
+namespace spvtools {
+namespace opt {
+
+// See optimizer.hpp for documentation.
+class SimplificationPass : public Pass {
+ public:
+  const char* name() const override { return "simplify-instructions"; }
+  Status Process(ir::IRContext*) override;
+
+ private:
+  // Returns true if the module was changed.  The simplifier is called on every
+  // instruction in |function| until nothing else in the function can be
+  // simplified.
+  bool SimplifyFunction(ir::Function* function);
+};
+
+}  // namespace opt
+}  // namespace spvtools
+
+#endif  // LIBSPIRV_OPT_SIMPLIFICATION_PASS_H_