diff --git a/CMakeLists.txt b/CMakeLists.txt
index ed298aa..fc866c0 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -184,6 +184,7 @@
       ${CMAKE_CURRENT_SOURCE_DIR}/include/spirv-tools/libspirv.h
       ${CMAKE_CURRENT_SOURCE_DIR}/include/spirv-tools/libspirv.hpp
       ${CMAKE_CURRENT_SOURCE_DIR}/include/spirv-tools/optimizer.hpp
+      ${CMAKE_CURRENT_SOURCE_DIR}/include/spirv-tools/linker.hpp
     DESTINATION
       ${CMAKE_INSTALL_INCLUDEDIR}/spirv-tools/)
 endif(ENABLE_SPIRV_TOOLS_INSTALL)
diff --git a/README.md b/README.md
index 85b60c9..cd739dd 100644
--- a/README.md
+++ b/README.md
@@ -109,12 +109,28 @@
   * Eliminate dead branches
   * Merge single successor / single predecessor block pairs
   * Eliminate common uniform loads
+  * Remove duplicates: Capabilities, extended instruction imports, types, and
+    decorations.
 
 For the latest list with detailed documentation, please refer to
 [`include/spirv-tools/optimizer.hpp`](include/spirv-tools/optimizer.hpp).
 
 For suggestions on using the code reduction options, please refer to this [white paper](https://www.lunarg.com/shader-compiler-technologies/white-paper-spirv-opt/).
 
+
+### Linker
+
+*Note:* The linker is still under development.
+
+Current features:
+* Combine multiple SPIR-V binary modules together.
+* Combine into a library (exports are retained) or an executable (no symbols
+  are exported).
+
+See the [CHANGES](CHANGES) file for reports on completed work, and the [General
+sub-project](https://github.com/KhronosGroup/SPIRV-Tools/projects/2) for
+planned and in-progress work.
+
 ### Extras
 
 * [Utility filters](#utility-filters)
@@ -255,10 +271,11 @@
 * `spvValidate` implements the validator functionality. *Incomplete*
 * `spvValidateBinary` implements the validator functionality. *Incomplete*
 
-The C++ interface is comprised of two classes, `SpirvTools` and `Optimizer`,
-both in the `spvtools` namespace.
+The C++ interface is comprised of three classes, `SpirvTools`, `Optimizer` and
+`Linker`, all in the `spvtools` namespace.
 * `SpirvTools` provides `Assemble`, `Disassemble`, and `Validate` methods.
 * `Optimizer` provides methods for registering and running optimization passes.
+* `Linker` provides methods for combining together multiple binaries.
 
 ## Command line tools
 
@@ -295,6 +312,18 @@
 The output includes syntax colouring when printing to the standard output stream,
 on Linux, Windows, and OS X.
 
+### Linker tool
+
+The linker combines multiple SPIR-V binary modules together, resulting in a single
+binary module as output.
+
+This is a work in progress.
+The linker does not support OpenCL program linking options related to math
+flags. (See section 5.6.5.2 in OpenCL 1.2)
+
+* `spirv-link` - the standalone linker
+  * `<spirv-dir>/tools/link`
+
 ### Optimizer tool
 
 The optimizer processes a SPIR-V binary module, applying transformations
@@ -395,6 +424,14 @@
 
 This is a work in progress.
 
+### Linker
+
+* The linker could accept math transformations such as allowing MADs, or other
+  math flags passed at linking-time in OpenCL.
+* Linkage attributes can not be applied through a group.
+* Check decorations of linked functions attributes.
+* Remove dead instructions, such as OpName targeting imported symbols.
+
 ## Licence
 <a name="license"></a>
 Full license terms are in [LICENSE](LICENSE)
diff --git a/include/spirv-tools/linker.hpp b/include/spirv-tools/linker.hpp
new file mode 100644
index 0000000..43c725d
--- /dev/null
+++ b/include/spirv-tools/linker.hpp
@@ -0,0 +1,98 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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 SPIRV_TOOLS_LINKER_HPP_
+#define SPIRV_TOOLS_LINKER_HPP_
+
+#include <cstdint>
+
+#include <memory>
+#include <vector>
+
+#include "libspirv.hpp"
+
+namespace spvtools {
+
+class LinkerOptions {
+ public:
+  LinkerOptions() : createLibrary_(false) {}
+
+  // Returns whether a library or an executable should be produced by the
+  // linking phase.
+  //
+  // All exported symbols are kept when creating a library, whereas they will
+  // be removed when creating an executable.
+  // The returned value will be true if creating a library, and false if
+  // creating an executable.
+  bool GetCreateLibrary() const { return createLibrary_; }
+  // Sets whether a library or an executable should be produced.
+  void SetCreateLibrary(bool create_library) {
+    createLibrary_ = create_library;
+  }
+
+ private:
+  bool createLibrary_;
+};
+
+class Linker {
+ public:
+  // Constructs an instance targeting the given environment |env|.
+  //
+  // The constructed instance will have an empty message consumer, which just
+  // ignores all messages from the library. Use SetMessageConsumer() to supply
+  // one if messages are of concern.
+  explicit Linker(spv_target_env env);
+
+  // Disables copy/move constructor/assignment operations.
+  Linker(const Linker&) = delete;
+  Linker(Linker&&) = delete;
+  Linker& operator=(const Linker&) = delete;
+  Linker& operator=(Linker&&) = delete;
+
+  // Destructs this instance.
+  ~Linker();
+
+  // Sets the message consumer to the given |consumer|. The |consumer| will be
+  // invoked once for each message communicated from the library.
+  void SetMessageConsumer(MessageConsumer consumer);
+
+  // Links one or more SPIR-V modules into a new SPIR-V module. That is,
+  // combine several SPIR-V modules into one, resolving link dependencies
+  // between them.
+  //
+  // At least one binary has to be provided in |binaries|. Those binaries do
+  // not have to be valid, but they should be at least parseable.
+  // The functions can fail due to the following:
+  // * No input modules were given;
+  // * One or more of those modules were not parseable;
+  // * The input modules used different addressing or memory models;
+  // * The ID or global variable number limit were exceeded;
+  // * Some entry points were defined multiple times;
+  // * Some imported symbols did not have an exported counterpart;
+  // * Possibly other reasons.
+  spv_result_t Link(const std::vector<std::vector<uint32_t>>& binaries,
+                    std::vector<uint32_t>& linked_binary,
+                    const LinkerOptions& options = LinkerOptions()) const;
+  spv_result_t Link(const uint32_t* const* binaries, const size_t* binary_sizes,
+                    size_t num_binaries, std::vector<uint32_t>& linked_binary,
+                    const LinkerOptions& options = LinkerOptions()) const;
+
+ private:
+  struct Impl;  // Opaque struct for holding the data fields used by this class.
+  std::unique_ptr<Impl> impl_;  // Unique pointer to implementation data.
+};
+
+}  // namespace spvtools
+
+#endif  // SPIRV_TOOLS_LINKER_HPP_
diff --git a/include/spirv-tools/optimizer.hpp b/include/spirv-tools/optimizer.hpp
index 7e1db25..e513120 100644
--- a/include/spirv-tools/optimizer.hpp
+++ b/include/spirv-tools/optimizer.hpp
@@ -375,6 +375,9 @@
 // The pass remaps result ids to a compact and gapless range starting from %1.
 Optimizer::PassToken CreateCompactIdsPass();
 
+// Creates a remove duplicate capabilities pass.
+Optimizer::PassToken CreateRemoveDuplicatesPass();
+
 }  // namespace spvtools
 
 #endif  // SPIRV_TOOLS_OPTIMIZER_HPP_
diff --git a/source/CMakeLists.txt b/source/CMakeLists.txt
index dd5a5a8..ecd16ea 100644
--- a/source/CMakeLists.txt
+++ b/source/CMakeLists.txt
@@ -190,6 +190,7 @@
 
 add_subdirectory(comp)
 add_subdirectory(opt)
+add_subdirectory(link)
 
 set(SPIRV_SOURCES
   ${spirv-tools_SOURCE_DIR}/include/spirv-tools/libspirv.h
diff --git a/source/link/CMakeLists.txt b/source/link/CMakeLists.txt
new file mode 100644
index 0000000..9db3cab
--- /dev/null
+++ b/source/link/CMakeLists.txt
@@ -0,0 +1,35 @@
+# Copyright (c) 2017 Pierre Moreau
+
+# 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.
+add_library(SPIRV-Tools-link
+  linker.cpp
+)
+
+spvtools_default_compile_options(SPIRV-Tools-link)
+target_include_directories(SPIRV-Tools-link
+  PUBLIC ${spirv-tools_SOURCE_DIR}/include
+  PUBLIC ${SPIRV_HEADER_INCLUDE_DIR}
+  PRIVATE ${spirv-tools_BINARY_DIR}
+)
+# We need the IR functionnalities from the optimizer
+target_link_libraries(SPIRV-Tools-link
+  PUBLIC SPIRV-Tools-opt)
+
+set_property(TARGET SPIRV-Tools-link PROPERTY FOLDER "SPIRV-Tools libraries")
+
+if(ENABLE_SPIRV_TOOLS_INSTALL)
+  install(TARGETS SPIRV-Tools-link
+    RUNTIME DESTINATION ${CMAKE_INSTALL_BINDIR}
+    LIBRARY DESTINATION ${CMAKE_INSTALL_LIBDIR}
+    ARCHIVE DESTINATION ${CMAKE_INSTALL_LIBDIR})
+endif(ENABLE_SPIRV_TOOLS_INSTALL)
diff --git a/source/link/linker.cpp b/source/link/linker.cpp
new file mode 100644
index 0000000..51e720a
--- /dev/null
+++ b/source/link/linker.cpp
@@ -0,0 +1,716 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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 "spirv-tools/linker.hpp"
+
+#include <cstdio>
+#include <cstring>
+
+#include <algorithm>
+#include <iostream>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+#include "assembly_grammar.h"
+#include "diagnostic.h"
+#include "opt/build_module.h"
+#include "opt/compact_ids_pass.h"
+#include "opt/decoration_manager.h"
+#include "opt/ir_loader.h"
+#include "opt/make_unique.h"
+#include "opt/pass_manager.h"
+#include "opt/remove_duplicates_pass.h"
+#include "spirv-tools/libspirv.hpp"
+#include "spirv_target_env.h"
+
+namespace spvtools {
+
+using ir::Instruction;
+using ir::Module;
+using ir::Operand;
+using opt::PassManager;
+using opt::RemoveDuplicatesPass;
+using opt::analysis::DecorationManager;
+using opt::analysis::DefUseManager;
+
+// Stores various information about an imported or exported symbol.
+struct LinkageSymbolInfo {
+  SpvId id;          // ID of the symbol
+  SpvId type_id;     // ID of the type of the symbol
+  std::string name;  // unique name defining the symbol and used for matching
+                     // imports and exports together
+  std::vector<SpvId> parameter_ids;  // ID of the parameters of the symbol, if
+                                     // it is a function
+};
+struct LinkageEntry {
+  LinkageSymbolInfo imported_symbol;
+  LinkageSymbolInfo exported_symbol;
+
+  LinkageEntry(const LinkageSymbolInfo& import_info,
+               const LinkageSymbolInfo& export_info)
+      : imported_symbol(import_info), exported_symbol(export_info) {}
+};
+using LinkageTable = std::vector<LinkageEntry>;
+
+// Shifts the IDs used in each binary of |modules| so that they occupy a
+// disjoint range from the other binaries, and compute the new ID bound which
+// is returned in |max_id_bound|.
+//
+// Both |modules| and |max_id_bound| should not be null, and |modules| should
+// not be empty either.
+static spv_result_t ShiftIdsInModules(
+    const MessageConsumer& consumer,
+    std::vector<std::unique_ptr<ir::Module>>* modules, uint32_t* max_id_bound);
+
+// Generates the header for the linked module and returns it in |header|.
+//
+// |header| should not be null, |modules| should not be empty and
+// |max_id_bound| should be strictly greater than 0.
+//
+// TODO(pierremoreau): What to do when binaries use different versions of
+//                     SPIR-V? For now, use the max of all versions found in
+//                     the input modules.
+static spv_result_t GenerateHeader(
+    const MessageConsumer& consumer,
+    const std::vector<std::unique_ptr<ir::Module>>& modules,
+    uint32_t max_id_bound, ir::ModuleHeader* header);
+
+// Merge all the modules from |inModules| into |linked_module|.
+//
+// |linked_module| should not be null.
+static spv_result_t MergeModules(
+    const MessageConsumer& consumer,
+    const std::vector<std::unique_ptr<Module>>& inModules,
+    const libspirv::AssemblyGrammar& grammar, Module* linked_module);
+
+// Compute all pairs of import and export and return it in |linkings_to_do|.
+//
+// |linkings_to_do should not be null. Built-in symbols will be ignored.
+//
+// TODO(pierremoreau): Linkage attributes applied by a group decoration are
+//                     currently not handled. (You could have a group being
+//                     applied to a single ID.)
+// TODO(pierremoreau): What should be the proper behaviour with built-in
+//                     symbols?
+static spv_result_t GetImportExportPairs(const MessageConsumer& consumer,
+                                         const Module& linked_module,
+                                         const DefUseManager& def_use_manager,
+                                         const DecorationManager& decoration_manager,
+                                         LinkageTable* linkings_to_do);
+
+// Checks that for each pair of import and export, the import and export have
+// the same type as well as the same decorations.
+//
+// TODO(pierremoreau): Decorations on functions parameters are currently not
+// checked.
+static spv_result_t CheckImportExportCompatibility(
+    const MessageConsumer& consumer, const LinkageTable& linkings_to_do,
+    const DefUseManager& def_use_manager,
+    const DecorationManager& decoration_manager);
+
+// Remove linkage specific instructions, such as prototypes of imported
+// functions, declarations of imported variables, import (and export if
+// necessary) linkage attribtes.
+//
+// |linked_module| and |decoration_manager| should not be null, and the
+// 'RemoveDuplicatePass' should be run first.
+//
+// TODO(pierremoreau): Linkage attributes applied by a group decoration are
+//                     currently not handled. (You could have a group being
+//                     applied to a single ID.)
+// TODO(pierremoreau): Run a pass for removing dead instructions, for example
+//                     OpName for prototypes of imported funcions.
+static spv_result_t RemoveLinkageSpecificInstructions(
+    const MessageConsumer& consumer, bool create_executable,
+    const LinkageTable& linkings_to_do, DecorationManager* decoration_manager,
+    Module* linked_module);
+
+// Structs for holding the data members for SpvLinker.
+struct Linker::Impl {
+  explicit Impl(spv_target_env env) : context(spvContextCreate(env)) {
+    // The default consumer in spv_context_t is a null consumer, which provides
+    // equivalent functionality (from the user's perspective) as a real consumer
+    // does nothing.
+  }
+  ~Impl() { spvContextDestroy(context); }
+
+  spv_context context;  // C interface context object.
+};
+
+Linker::Linker(spv_target_env env) : impl_(new Impl(env)) {}
+
+Linker::~Linker() {}
+
+void Linker::SetMessageConsumer(MessageConsumer consumer) {
+  SetContextMessageConsumer(impl_->context, std::move(consumer));
+}
+
+spv_result_t Linker::Link(const std::vector<std::vector<uint32_t>>& binaries,
+                          std::vector<uint32_t>& linked_binary,
+                          const LinkerOptions& options) const {
+  std::vector<const uint32_t*> binary_ptrs;
+  binary_ptrs.reserve(binaries.size());
+  std::vector<size_t> binary_sizes;
+  binary_sizes.reserve(binaries.size());
+
+  for (const auto& binary : binaries) {
+    binary_ptrs.push_back(binary.data());
+    binary_sizes.push_back(binary.size());
+  }
+
+  return Link(binary_ptrs.data(), binary_sizes.data(), binaries.size(),
+              linked_binary, options);
+}
+
+spv_result_t Linker::Link(const uint32_t* const* binaries,
+                          const size_t* binary_sizes, size_t num_binaries,
+                          std::vector<uint32_t>& linked_binary,
+                          const LinkerOptions& options) const {
+  spv_position_t position = {};
+  const MessageConsumer& consumer = impl_->context->consumer;
+
+  linked_binary.clear();
+  if (num_binaries == 0u)
+    return libspirv::DiagnosticStream(position, consumer,
+                                      SPV_ERROR_INVALID_BINARY)
+           << "No modules were given.";
+
+  std::vector<std::unique_ptr<Module>> modules;
+  modules.reserve(num_binaries);
+  for (size_t i = 0u; i < num_binaries; ++i) {
+    const uint32_t schema = binaries[i][4u];
+    if (schema != 0u) {
+      position.index = 4u;
+      return libspirv::DiagnosticStream(position, consumer,
+                                        SPV_ERROR_INVALID_BINARY)
+             << "Schema is non-zero for module " << i << ".";
+    }
+
+    std::unique_ptr<Module> module = BuildModule(
+        impl_->context->target_env, consumer, binaries[i], binary_sizes[i]);
+    if (module == nullptr)
+      return libspirv::DiagnosticStream(position, consumer,
+                                        SPV_ERROR_INVALID_BINARY)
+             << "Failed to build a module out of " << modules.size() << ".";
+    modules.push_back(std::move(module));
+  }
+
+  // Phase 1: Shift the IDs used in each binary so that they occupy a disjoint
+  //          range from the other binaries, and compute the new ID bound.
+  uint32_t max_id_bound = 0u;
+  spv_result_t res = ShiftIdsInModules(consumer, &modules, &max_id_bound);
+  if (res != SPV_SUCCESS) return res;
+
+  // Phase 2: Generate the header
+  ir::ModuleHeader header;
+  res = GenerateHeader(consumer, modules, max_id_bound, &header);
+  if (res != SPV_SUCCESS) return res;
+  auto linked_module = MakeUnique<Module>();
+  linked_module->SetHeader(header);
+
+  // Phase 3: Merge all the binaries into a single one.
+  libspirv::AssemblyGrammar grammar(impl_->context);
+  res = MergeModules(consumer, modules, grammar, linked_module.get());
+  if (res != SPV_SUCCESS) return res;
+
+  DefUseManager def_use_manager(consumer, linked_module.get());
+
+  // Phase 4: Find the import/export pairs
+  LinkageTable linkings_to_do;
+  DecorationManager decoration_manager(linked_module.get());
+  res = GetImportExportPairs(consumer, *linked_module, def_use_manager,
+                             decoration_manager, &linkings_to_do);
+  if (res != SPV_SUCCESS) return res;
+
+  // Phase 5: Ensure the import and export have the same types and decorations.
+  res = CheckImportExportCompatibility(consumer, linkings_to_do,
+                                       def_use_manager, decoration_manager);
+  if (res != SPV_SUCCESS) return res;
+
+  // Phase 6: Remove duplicates
+  PassManager manager;
+  manager.SetMessageConsumer(consumer);
+  manager.AddPass<RemoveDuplicatesPass>();
+  opt::Pass::Status pass_res = manager.Run(linked_module.get());
+  if (pass_res == opt::Pass::Status::Failure) return SPV_ERROR_INVALID_DATA;
+
+  // Phase 7: Remove linkage specific instructions, such as import/export
+  // attributes, linkage capability, etc. if applicable
+  res = RemoveLinkageSpecificInstructions(consumer, !options.GetCreateLibrary(),
+                                          linkings_to_do, &decoration_manager,
+                                          linked_module.get());
+  if (res != SPV_SUCCESS) return res;
+
+  // Phase 8: Rematch import variables/functions to export variables/functions
+  // TODO(pierremoreau): Keep the previous DefUseManager up-to-date
+  DefUseManager def_use_manager2(consumer, linked_module.get());
+  for (const auto& linking_entry : linkings_to_do)
+    def_use_manager2.ReplaceAllUsesWith(linking_entry.imported_symbol.id,
+                                        linking_entry.exported_symbol.id);
+
+  // Phase 9: Compact the IDs used in the module
+  manager.AddPass<opt::CompactIdsPass>();
+  pass_res = manager.Run(linked_module.get());
+  if (pass_res == opt::Pass::Status::Failure) return SPV_ERROR_INVALID_DATA;
+
+  // Phase 10: Output the module
+  linked_module->ToBinary(&linked_binary, true);
+
+  return SPV_SUCCESS;
+}
+
+static spv_result_t ShiftIdsInModules(
+    const MessageConsumer& consumer,
+    std::vector<std::unique_ptr<ir::Module>>* modules, uint32_t* max_id_bound) {
+  spv_position_t position = {};
+
+  if (modules == nullptr)
+    return libspirv::DiagnosticStream(position, consumer,
+                                      SPV_ERROR_INVALID_DATA)
+           << "|modules| of ShiftIdsInModules should not be null.";
+  if (modules->empty())
+    return libspirv::DiagnosticStream(position, consumer,
+                                      SPV_ERROR_INVALID_DATA)
+           << "|modules| of ShiftIdsInModules should not be empty.";
+  if (max_id_bound == nullptr)
+    return libspirv::DiagnosticStream(position, consumer,
+                                      SPV_ERROR_INVALID_DATA)
+           << "|max_id_bound| of ShiftIdsInModules should not be null.";
+
+  uint32_t id_bound = modules->front()->IdBound() - 1u;
+  for (auto module_iter = modules->begin() + 1; module_iter != modules->end();
+       ++module_iter) {
+    Module* module = module_iter->get();
+    module->ForEachInst([&id_bound](Instruction* insn) {
+      insn->ForEachId([&id_bound](uint32_t* id) { *id += id_bound; });
+    });
+    id_bound += module->IdBound() - 1u;
+    if (id_bound > 0x3FFFFF)
+      return libspirv::DiagnosticStream(position, consumer,
+                                        SPV_ERROR_INVALID_ID)
+             << "The limit of IDs, 4194303, was exceeded:"
+             << " " << id_bound << " is the current ID bound.";
+  }
+  ++id_bound;
+  if (id_bound > 0x3FFFFF)
+    return libspirv::DiagnosticStream(position, consumer, SPV_ERROR_INVALID_ID)
+           << "The limit of IDs, 4194303, was exceeded:"
+           << " " << id_bound << " is the current ID bound.";
+
+  *max_id_bound = id_bound;
+
+  return SPV_SUCCESS;
+}
+
+static spv_result_t GenerateHeader(
+    const MessageConsumer& consumer,
+    const std::vector<std::unique_ptr<ir::Module>>& modules,
+    uint32_t max_id_bound, ir::ModuleHeader* header) {
+  spv_position_t position = {};
+
+  if (modules.empty())
+    return libspirv::DiagnosticStream(position, consumer,
+                                      SPV_ERROR_INVALID_DATA)
+           << "|modules| of GenerateHeader should not be empty.";
+  if (max_id_bound == 0u)
+    return libspirv::DiagnosticStream(position, consumer,
+                                      SPV_ERROR_INVALID_DATA)
+           << "|max_id_bound| of GenerateHeader should not be null.";
+
+  uint32_t version = 0u;
+  for (const auto& module : modules)
+    version = std::max(version, module->version());
+
+  header->magic_number = SpvMagicNumber;
+  header->version = version;
+  header->generator = 17u;
+  header->bound = max_id_bound;
+  header->reserved = 0u;
+
+  return SPV_SUCCESS;
+}
+
+static spv_result_t MergeModules(
+    const MessageConsumer& consumer,
+    const std::vector<std::unique_ptr<Module>>& input_modules,
+    const libspirv::AssemblyGrammar& grammar, Module* linked_module) {
+  spv_position_t position = {};
+
+  if (linked_module == nullptr)
+    return libspirv::DiagnosticStream(position, consumer,
+                                      SPV_ERROR_INVALID_DATA)
+           << "|linked_module| of MergeModules should not be null.";
+
+  if (input_modules.empty()) return SPV_SUCCESS;
+
+  for (const auto& module : input_modules)
+    for (const auto& inst : module->capabilities())
+      linked_module->AddCapability(MakeUnique<Instruction>(inst));
+
+  for (const auto& module : input_modules)
+    for (const auto& inst : module->extensions())
+      linked_module->AddExtension(MakeUnique<Instruction>(inst));
+
+  for (const auto& module : input_modules)
+    for (const auto& inst : module->ext_inst_imports())
+      linked_module->AddExtInstImport(MakeUnique<Instruction>(inst));
+
+  do {
+    const Instruction* memory_model_inst = input_modules[0]->GetMemoryModel();
+    if (memory_model_inst == nullptr) break;
+
+    uint32_t addressing_model = memory_model_inst->GetSingleWordOperand(0u);
+    uint32_t memory_model = memory_model_inst->GetSingleWordOperand(1u);
+    for (const auto& module : input_modules) {
+      memory_model_inst = module->GetMemoryModel();
+      if (memory_model_inst == nullptr) continue;
+
+      if (addressing_model != memory_model_inst->GetSingleWordOperand(0u)) {
+        spv_operand_desc initial_desc = nullptr, current_desc = nullptr;
+        grammar.lookupOperand(SPV_OPERAND_TYPE_ADDRESSING_MODEL,
+                              addressing_model, &initial_desc);
+        grammar.lookupOperand(SPV_OPERAND_TYPE_ADDRESSING_MODEL,
+                              memory_model_inst->GetSingleWordOperand(0u),
+                              &current_desc);
+        return libspirv::DiagnosticStream(position, consumer,
+                                          SPV_ERROR_INTERNAL)
+               << "Conflicting addressing models: " << initial_desc->name
+               << " vs " << current_desc->name << ".";
+      }
+      if (memory_model != memory_model_inst->GetSingleWordOperand(1u)) {
+        spv_operand_desc initial_desc = nullptr, current_desc = nullptr;
+        grammar.lookupOperand(SPV_OPERAND_TYPE_MEMORY_MODEL, memory_model,
+                              &initial_desc);
+        grammar.lookupOperand(SPV_OPERAND_TYPE_MEMORY_MODEL,
+                              memory_model_inst->GetSingleWordOperand(1u),
+                              &current_desc);
+        return libspirv::DiagnosticStream(position, consumer,
+                                          SPV_ERROR_INTERNAL)
+               << "Conflicting memory models: " << initial_desc->name << " vs "
+               << current_desc->name << ".";
+      }
+    }
+
+    if (memory_model_inst != nullptr)
+      linked_module->SetMemoryModel(
+          MakeUnique<Instruction>(*memory_model_inst));
+  } while (false);
+
+  std::vector<std::pair<uint32_t, const char*>> entry_points;
+  for (const auto& module : input_modules)
+    for (const auto& inst : module->entry_points()) {
+      const uint32_t model = inst.GetSingleWordInOperand(0);
+      const char* const name =
+          reinterpret_cast<const char*>(inst.GetInOperand(2).words.data());
+      const auto i = std::find_if(
+          entry_points.begin(), entry_points.end(),
+          [model, name](const std::pair<uint32_t, const char*>& v) {
+            return v.first == model && strcmp(name, v.second) == 0;
+          });
+      if (i != entry_points.end()) {
+        spv_operand_desc desc = nullptr;
+        grammar.lookupOperand(SPV_OPERAND_TYPE_EXECUTION_MODEL, model, &desc);
+        return libspirv::DiagnosticStream(position, consumer,
+                                          SPV_ERROR_INTERNAL)
+               << "The entry point \"" << name << "\", with execution model "
+               << desc->name << ", was already defined.";
+      }
+      linked_module->AddEntryPoint(MakeUnique<Instruction>(inst));
+      entry_points.emplace_back(model, name);
+    }
+
+  for (const auto& module : input_modules)
+    for (const auto& inst : module->execution_modes())
+      linked_module->AddExecutionMode(MakeUnique<Instruction>(inst));
+
+  for (const auto& module : input_modules)
+    for (const auto& inst : module->debugs1())
+      linked_module->AddDebug1Inst(MakeUnique<Instruction>(inst));
+
+  for (const auto& module : input_modules)
+    for (const auto& inst : module->debugs2())
+      linked_module->AddDebug2Inst(MakeUnique<Instruction>(inst));
+
+  for (const auto& module : input_modules)
+    for (const auto& inst : module->annotations())
+      linked_module->AddAnnotationInst(MakeUnique<Instruction>(inst));
+
+  // TODO(pierremoreau): Since the modules have not been validate, should we
+  //                     expect SpvStorageClassFunction variables outside
+  //                     functions?
+  uint32_t num_global_values = 0u;
+  for (const auto& module : input_modules) {
+    for (const auto& inst : module->types_values()) {
+      linked_module->AddType(MakeUnique<Instruction>(inst));
+      num_global_values += inst.opcode() == SpvOpVariable;
+    }
+  }
+  if (num_global_values > 0xFFFF)
+    return libspirv::DiagnosticStream(position, consumer, SPV_ERROR_INTERNAL)
+           << "The limit of global values, 65535, was exceeded;"
+           << " " << num_global_values << " global values were found.";
+
+  // Process functions and their basic blocks
+  for (const auto& module : input_modules) {
+    for (const auto& func : *module) {
+      std::unique_ptr<ir::Function> cloned_func =
+          MakeUnique<ir::Function>(func);
+      cloned_func->SetParent(linked_module);
+      linked_module->AddFunction(std::move(cloned_func));
+    }
+  }
+
+  return SPV_SUCCESS;
+}
+
+static spv_result_t GetImportExportPairs(const MessageConsumer& consumer,
+                                         const Module& linked_module,
+                                         const DefUseManager& def_use_manager,
+                                         const DecorationManager& decoration_manager,
+                                         LinkageTable* linkings_to_do) {
+  spv_position_t position = {};
+
+  if (linkings_to_do == nullptr)
+    return libspirv::DiagnosticStream(position, consumer,
+                                      SPV_ERROR_INVALID_DATA)
+           << "|linkings_to_do| of GetImportExportPairs should not be empty.";
+
+  std::vector<LinkageSymbolInfo> imports;
+  std::unordered_map<std::string, std::vector<LinkageSymbolInfo>> exports;
+
+  // Figure out the imports and exports
+  for (const auto& decoration : linked_module.annotations()) {
+    if (decoration.opcode() != SpvOpDecorate ||
+        decoration.GetSingleWordInOperand(1u) != SpvDecorationLinkageAttributes)
+      continue;
+
+    const SpvId id = decoration.GetSingleWordInOperand(0u);
+    // Ignore if the targeted symbol is a built-in
+    bool is_built_in = false;
+    for (const auto& id_decoration : decoration_manager.GetDecorationsFor(id, false)) {
+      if (id_decoration->GetSingleWordInOperand(1u) == SpvDecorationBuiltIn) {
+        is_built_in = true;
+        break;
+      }
+    }
+    if (is_built_in)
+      continue;
+
+    const uint32_t type = decoration.GetSingleWordInOperand(3u);
+
+    LinkageSymbolInfo symbol_info;
+    symbol_info.name =
+        reinterpret_cast<const char*>(decoration.GetInOperand(2u).words.data());
+    symbol_info.id = id;
+    symbol_info.type_id = 0u;
+
+    // Retrieve the type of the current symbol. This information will be used
+    // when checking that the imported and exported symbols have the same
+    // types.
+    const Instruction* def_inst = def_use_manager.GetDef(id);
+    if (def_inst == nullptr)
+      return libspirv::DiagnosticStream(position, consumer,
+                                        SPV_ERROR_INVALID_BINARY)
+             << "ID " << id << " is never defined:\n";
+
+    if (def_inst->opcode() == SpvOpVariable) {
+      symbol_info.type_id = def_inst->type_id();
+    } else if (def_inst->opcode() == SpvOpFunction) {
+      symbol_info.type_id = def_inst->GetSingleWordInOperand(1u);
+
+      // range-based for loop calls begin()/end(), but never cbegin()/cend(),
+      // which will not work here.
+      for (auto func_iter = linked_module.cbegin();
+           func_iter != linked_module.cend(); ++func_iter) {
+        if (func_iter->result_id() != id) continue;
+        func_iter->ForEachParam([&symbol_info](const Instruction* inst) {
+          symbol_info.parameter_ids.push_back(inst->result_id());
+        });
+      }
+    } else {
+      return libspirv::DiagnosticStream(position, consumer,
+                                        SPV_ERROR_INVALID_BINARY)
+             << "Only global variables and functions can be decorated using"
+             << " LinkageAttributes; " << id << " is neither of them.\n";
+    }
+
+    if (type == SpvLinkageTypeImport)
+      imports.push_back(symbol_info);
+    else if (type == SpvLinkageTypeExport)
+      exports[symbol_info.name].push_back(symbol_info);
+  }
+
+  // Find the import/export pairs
+  for (const auto& import : imports) {
+    std::vector<LinkageSymbolInfo> possible_exports;
+    const auto& exp = exports.find(import.name);
+    if (exp != exports.end()) possible_exports = exp->second;
+    if (possible_exports.empty())
+      return libspirv::DiagnosticStream(position, consumer,
+                                        SPV_ERROR_INVALID_BINARY)
+             << "No export linkage was found for \"" << import.name << "\".";
+    else if (possible_exports.size() > 1u)
+      return libspirv::DiagnosticStream(position, consumer,
+                                        SPV_ERROR_INVALID_BINARY)
+             << "Too many export linkages, " << possible_exports.size()
+             << ", were found for \"" << import.name << "\".";
+
+    linkings_to_do->emplace_back(import, possible_exports.front());
+  }
+
+  return SPV_SUCCESS;
+}
+
+static spv_result_t CheckImportExportCompatibility(
+    const MessageConsumer& consumer, const LinkageTable& linkings_to_do,
+    const DefUseManager& def_use_manager,
+    const DecorationManager& decoration_manager) {
+  spv_position_t position = {};
+
+  // Ensure th import and export types are the same.
+  for (const auto& linking_entry : linkings_to_do) {
+    if (!RemoveDuplicatesPass::AreTypesEqual(
+            *def_use_manager.GetDef(linking_entry.imported_symbol.type_id),
+            *def_use_manager.GetDef(linking_entry.exported_symbol.type_id),
+            def_use_manager, decoration_manager))
+      return libspirv::DiagnosticStream(position, consumer,
+                                        SPV_ERROR_INVALID_BINARY)
+             << "Type mismatch between imported variable/function %"
+             << linking_entry.imported_symbol.id
+             << " and exported variable/function %"
+             << linking_entry.exported_symbol.id << ".";
+  }
+
+  // Ensure the import and export decorations are similar
+  for (const auto& linking_entry : linkings_to_do) {
+    if (!decoration_manager.HaveTheSameDecorations(
+            linking_entry.imported_symbol.id, linking_entry.exported_symbol.id))
+      return libspirv::DiagnosticStream(position, consumer,
+                                        SPV_ERROR_INVALID_BINARY)
+             << "Decorations mismatch between imported variable/function %"
+             << linking_entry.imported_symbol.id
+             << " and exported variable/function %"
+             << linking_entry.exported_symbol.id << ".";
+    // TODO(pierremoreau): Decorations on function parameters should probably
+    //                     match, except for FuncParamAttr if I understand the
+    //                     spec correctly, which makes the code more
+    //                     complicated.
+    //    for (uint32_t i = 0u; i <
+    //    linking_entry.imported_symbol.parameter_ids.size(); ++i)
+    //      if
+    //      (!decoration_manager.HaveTheSameDecorations(linking_entry.imported_symbol.parameter_ids[i],
+    //      linking_entry.exported_symbol.parameter_ids[i]))
+    //          return libspirv::DiagnosticStream(position,
+    //          impl_->context->consumer,
+    //                                            SPV_ERROR_INVALID_BINARY)
+    //                 << "Decorations mismatch between imported function %" <<
+    //                 linking_entry.imported_symbol.id << "'s"
+    //                 << " and exported function %" <<
+    //                 linking_entry.exported_symbol.id << "'s " << (i + 1u) <<
+    //                 "th parameter.";
+  }
+
+  return SPV_SUCCESS;
+}
+
+static spv_result_t RemoveLinkageSpecificInstructions(
+    const MessageConsumer& consumer, bool create_executable,
+    const LinkageTable& linkings_to_do, DecorationManager* decoration_manager,
+    Module* linked_module) {
+  spv_position_t position = {};
+
+  if (decoration_manager == nullptr)
+    return libspirv::DiagnosticStream(position, consumer,
+                                      SPV_ERROR_INVALID_DATA)
+           << "|decoration_manager| of RemoveLinkageSpecificInstructions "
+              "should "
+              "not "
+              "be empty.";
+  if (linked_module == nullptr)
+    return libspirv::DiagnosticStream(position, consumer,
+                                      SPV_ERROR_INVALID_DATA)
+           << "|linked_module| of RemoveLinkageSpecificInstructions should not "
+              "be empty.";
+
+  // Remove FuncParamAttr decorations of imported functions' parameters.
+  // From the SPIR-V specification, Sec. 2.13:
+  //   When resolving imported functions, the Function Control and all Function
+  //   Parameter Attributes are taken from the function definition, and not
+  //   from the function declaration.
+  for (const auto& linking_entry : linkings_to_do) {
+    for (const auto parameter_id :
+         linking_entry.imported_symbol.parameter_ids) {
+      for (ir::Instruction* decoration :
+           decoration_manager->GetDecorationsFor(parameter_id, false)) {
+        switch (decoration->opcode()) {
+          case SpvOpDecorate:
+          case SpvOpMemberDecorate:
+            if (decoration->GetSingleWordInOperand(1u) ==
+                SpvDecorationFuncParamAttr)
+              decoration->ToNop();
+            break;
+          default:
+            break;
+        }
+      }
+    }
+  }
+
+  // Remove prototypes of imported functions
+  for (const auto& linking_entry : linkings_to_do) {
+    for (auto func_iter = linked_module->begin();
+         func_iter != linked_module->end();) {
+      if (func_iter->result_id() == linking_entry.imported_symbol.id)
+        func_iter = func_iter.Erase();
+      else
+        ++func_iter;
+    }
+  }
+
+  // Remove declarations of imported variables
+  for (const auto& linking_entry : linkings_to_do) {
+    for (auto& inst : linked_module->types_values())
+      if (inst.result_id() == linking_entry.imported_symbol.id) inst.ToNop();
+  }
+
+  // Remove import linkage attributes
+  for (auto& inst : linked_module->annotations())
+    if (inst.opcode() == SpvOpDecorate &&
+        inst.GetSingleWordOperand(1u) == SpvDecorationLinkageAttributes &&
+        inst.GetSingleWordOperand(3u) == SpvLinkageTypeImport)
+      inst.ToNop();
+
+  // Remove export linkage attributes and Linkage capability if making an
+  // executable
+  if (create_executable) {
+    for (auto& inst : linked_module->annotations())
+      if (inst.opcode() == SpvOpDecorate &&
+          inst.GetSingleWordOperand(1u) == SpvDecorationLinkageAttributes &&
+          inst.GetSingleWordOperand(3u) == SpvLinkageTypeExport)
+        inst.ToNop();
+
+    for (auto& inst : linked_module->capabilities())
+      if (inst.GetSingleWordInOperand(0u) == SpvCapabilityLinkage) {
+        inst.ToNop();
+        // The RemoveDuplicatesPass did remove duplicated capabilities, so we
+        // now there aren’t more SpvCapabilityLinkage further down.
+        break;
+      }
+  }
+
+  return SPV_SUCCESS;
+}
+
+}  // namespace spvtools
diff --git a/source/opt/CMakeLists.txt b/source/opt/CMakeLists.txt
index 67d3b5d..7a2eb85 100644
--- a/source/opt/CMakeLists.txt
+++ b/source/opt/CMakeLists.txt
@@ -20,6 +20,7 @@
   compact_ids_pass.h
   constants.h
   dead_branch_elim_pass.h
+  decoration_manager.h
   def_use_manager.h
   eliminate_dead_constant_pass.h
   flatten_decoration_pass.h
@@ -45,6 +46,7 @@
   passes.h
   pass_manager.h
   eliminate_dead_functions_pass.h
+  remove_duplicates_pass.h
   set_spec_constant_default_value_pass.h
   strength_reduction_pass.h
   strip_debug_info_pass.h
@@ -58,6 +60,7 @@
   build_module.cpp
   common_uniform_elim_pass.cpp
   compact_ids_pass.cpp
+  decoration_manager.cpp
   def_use_manager.cpp
   dead_branch_elim_pass.cpp
   eliminate_dead_constant_pass.cpp
@@ -77,6 +80,7 @@
   local_ssa_elim_pass.cpp
   module.cpp
   eliminate_dead_functions_pass.cpp
+  remove_duplicates_pass.cpp
   set_spec_constant_default_value_pass.cpp
   optimizer.cpp
   mem_pass.cpp
diff --git a/source/opt/aggressive_dead_code_elim_pass.cpp b/source/opt/aggressive_dead_code_elim_pass.cpp
index b3dbff6..4b06a41 100644
--- a/source/opt/aggressive_dead_code_elim_pass.cpp
+++ b/source/opt/aggressive_dead_code_elim_pass.cpp
@@ -198,7 +198,7 @@
   // Remove debug and annotation statements referencing dead instructions.
   // This must be done before killing the instructions, otherwise there are
   // dead objects in the def/use database.
-  for (auto& di : module_->debugs()) {
+  for (auto& di : module_->debugs2()) {
     if (di.opcode() != SpvOpName)
       continue;
     if (KillInstIfTargetDead(&di))
diff --git a/source/opt/basic_block.cpp b/source/opt/basic_block.cpp
index 7420f3b..d163c55 100644
--- a/source/opt/basic_block.cpp
+++ b/source/opt/basic_block.cpp
@@ -14,9 +14,20 @@
 
 #include "basic_block.h"
 
+#include "make_unique.h"
+
 namespace spvtools {
 namespace ir {
 
+BasicBlock::BasicBlock(const BasicBlock& bb)
+    : function_(nullptr),
+      label_(MakeUnique<Instruction>(bb.GetLabelInst())),
+      insts_() {
+  insts_.reserve(bb.insts_.size());
+  for (auto& inst : bb.insts_)
+    AddInstruction(MakeUnique<Instruction>(*inst.get()));
+}
+
 const Instruction* BasicBlock::GetMergeInst() const {
   const Instruction* result = nullptr;
   // If it exists, the merge instruction immediately precedes the
diff --git a/source/opt/basic_block.h b/source/opt/basic_block.h
index 66353e0..0c46400 100644
--- a/source/opt/basic_block.h
+++ b/source/opt/basic_block.h
@@ -40,6 +40,12 @@
   // Creates a basic block with the given starting |label|.
   inline explicit BasicBlock(std::unique_ptr<Instruction> label);
 
+  // Creates a basic block from the given basic block |bb|.
+  //
+  // The parent function will default to null and needs to be explicitly set by
+  // the user.
+  explicit BasicBlock(const BasicBlock& bb);
+
   // Sets the enclosing function for this basic block.
   void SetParent(Function* function) { function_ = function; }
 
@@ -51,6 +57,7 @@
 
   // The label starting this basic block.
   Instruction* GetLabelInst() { return label_.get(); }
+  const Instruction& GetLabelInst() const { return *label_; }
 
   // Returns the merge instruction in this basic block, if it exists.
   // Otherwise return null.  May be used whenever tail() can be used.
diff --git a/source/opt/decoration_manager.cpp b/source/opt/decoration_manager.cpp
new file mode 100644
index 0000000..52a9bca
--- /dev/null
+++ b/source/opt/decoration_manager.cpp
@@ -0,0 +1,234 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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 "decoration_manager.h"
+
+#include <stack>
+
+namespace spvtools {
+namespace opt {
+namespace analysis {
+
+void DecorationManager::RemoveDecorationsFrom(uint32_t id, bool keep_linkage) {
+  auto const ids_iter = id_to_decoration_insts_.find(id);
+  if (ids_iter == id_to_decoration_insts_.end()) return;
+
+  for (ir::Instruction* inst : ids_iter->second) {
+    switch (inst->opcode()) {
+      case SpvOpDecorate:
+      case SpvOpDecorateId:
+      case SpvOpMemberDecorate:
+        if (!(keep_linkage && inst->GetSingleWordInOperand(1u) ==
+                                  SpvDecorationLinkageAttributes))
+          inst->ToNop();
+        break;
+      case SpvOpGroupDecorate:
+        for (uint32_t i = 1u; i < inst->NumInOperands(); ++i) {
+          if (inst->GetSingleWordInOperand(i) == inst->result_id()) {
+            // TODO(pierremoreau): This could be optimised by copying the last
+            //                     operand over this one, or using a compacting
+            //                     filtering algorithm over all other IDs
+            inst->RemoveInOperand(i);
+          }
+        }
+        break;
+      case SpvOpGroupMemberDecorate:
+        for (uint32_t i = 1u; i < inst->NumInOperands(); i += 2u) {
+          if (inst->GetSingleWordInOperand(i) == inst->result_id()) {
+            // TODO(pierremoreau): Same optimisation opportunity as above.
+            inst->RemoveInOperand(i);
+          }
+        }
+        break;
+      default:
+        break;
+    }
+  }
+}
+
+std::vector<ir::Instruction*> DecorationManager::GetDecorationsFor(
+    uint32_t id, bool include_linkage) {
+  return InternalGetDecorationsFor<ir::Instruction*>(id, include_linkage);
+}
+
+std::vector<const ir::Instruction*> DecorationManager::GetDecorationsFor(
+    uint32_t id, bool include_linkage) const {
+  return const_cast<DecorationManager*>(this)->InternalGetDecorationsFor<const ir::Instruction*>(id, include_linkage);
+}
+
+// TODO(pierremoreau): The code will return true for { deco1, deco1 }, { deco1,
+//                     deco2 } when it should return false.
+bool DecorationManager::HaveTheSameDecorations(uint32_t id1,
+                                               uint32_t id2) const {
+  const auto decorationsFor1 = GetDecorationsFor(id1, false);
+  const auto decorationsFor2 = GetDecorationsFor(id2, false);
+  if (decorationsFor1.size() != decorationsFor2.size()) return false;
+
+  for (const ir::Instruction* inst1 : decorationsFor1) {
+    bool didFindAMatch = false;
+    for (const ir::Instruction* inst2 : decorationsFor2) {
+      if (AreDecorationsTheSame(inst1, inst2)) {
+        didFindAMatch = true;
+        break;
+      }
+    }
+    if (!didFindAMatch) return false;
+  }
+  return true;
+}
+
+// TODO(pierremoreau): Handle SpvOpDecorateId by converting them to a regular
+//                     SpvOpDecorate.
+bool DecorationManager::AreDecorationsTheSame(
+    const ir::Instruction* inst1, const ir::Instruction* inst2) const {
+  //  const auto decorateIdToDecorate = [&constants](const Instruction& inst) {
+  //    std::vector<Operand> operands;
+  //    operands.reserve(inst.NumInOperands());
+  //    for (uint32_t i = 2u; i < inst.NumInOperands(); ++i) {
+  //      const auto& j = constants.find(inst.GetSingleWordInOperand(i));
+  //      if (j == constants.end())
+  //        return Instruction();
+  //      const auto operand = j->second->GetOperand(0u);
+  //      operands.emplace_back(operand.type, operand.words);
+  //    }
+  //    return Instruction(SpvOpDecorate, 0u, 0u, operands);
+  //  };
+  //  Instruction tmpA = (deco1.opcode() == SpvOpDecorateId) ?
+  //  decorateIdToDecorate(deco1) : deco1;
+  //  Instruction tmpB = (deco2.opcode() == SpvOpDecorateId) ?
+  //  decorateIdToDecorate(deco2) : deco2;
+  //
+  if (inst1->opcode() == SpvOpDecorateId || inst2->opcode() == SpvOpDecorateId)
+    return false;
+
+  ir::Instruction tmpA = *inst1, tmpB = *inst2;
+  if (tmpA.opcode() != tmpB.opcode() ||
+      tmpA.NumInOperands() != tmpB.NumInOperands() ||
+      tmpA.opcode() == SpvOpNop || tmpB.opcode() == SpvOpNop)
+    return false;
+
+  for (uint32_t i = (tmpA.opcode() == SpvOpDecorate) ? 1u : 2u;
+       i < tmpA.NumInOperands(); ++i)
+    if (tmpA.GetInOperand(i) != tmpB.GetInOperand(i)) return false;
+
+  return true;
+}
+
+void DecorationManager::AnalyzeDecorations(ir::Module* module) {
+  if (!module) return;
+
+  // Collect all group ids.
+  for (const ir::Instruction& inst : module->annotations()) {
+    switch (inst.opcode()) {
+      case SpvOpDecorationGroup:
+        group_to_decoration_insts_.insert({inst.result_id(), {}});
+        break;
+      default:
+        break;
+    }
+  }
+
+  // For each group and instruction, collect all their decoration instructions.
+  for (ir::Instruction& inst : module->annotations()) {
+    switch (inst.opcode()) {
+      case SpvOpDecorate:
+      case SpvOpDecorateId:
+      case SpvOpMemberDecorate: {
+        auto const target_id = inst.GetSingleWordInOperand(0u);
+        auto const group_iter = group_to_decoration_insts_.find(target_id);
+        if (group_iter != group_to_decoration_insts_.end())
+          group_iter->second.push_back(&inst);
+        else
+          id_to_decoration_insts_[target_id].push_back(&inst);
+        break;
+      }
+      case SpvOpGroupDecorate:
+        for (uint32_t i = 1u; i < inst.NumInOperands(); ++i) {
+          auto const target_id = inst.GetSingleWordInOperand(i);
+          auto const group_iter = group_to_decoration_insts_.find(target_id);
+          if (group_iter != group_to_decoration_insts_.end())
+            group_iter->second.push_back(&inst);
+          else
+            id_to_decoration_insts_[target_id].push_back(&inst);
+        }
+        break;
+      case SpvOpGroupMemberDecorate:
+        for (uint32_t i = 1u; i < inst.NumInOperands(); i += 2u) {
+          auto const target_id = inst.GetSingleWordInOperand(i);
+          auto const group_iter = group_to_decoration_insts_.find(target_id);
+          if (group_iter != group_to_decoration_insts_.end())
+            group_iter->second.push_back(&inst);
+          else
+            id_to_decoration_insts_[target_id].push_back(&inst);
+        }
+        break;
+      default:
+        break;
+    }
+  }
+}
+
+template <typename T>
+std::vector<T> DecorationManager::InternalGetDecorationsFor(uint32_t id,
+                                                    bool include_linkage) {
+  std::vector<T> decorations;
+  std::stack<uint32_t> ids_to_process;
+
+  const auto process = [&ids_to_process,
+                        &decorations](T inst) {
+    if (inst->opcode() == SpvOpGroupDecorate ||
+        inst->opcode() == SpvOpGroupMemberDecorate)
+      ids_to_process.push(inst->GetSingleWordInOperand(0u));
+    else
+      decorations.push_back(inst);
+  };
+
+  const auto ids_iter = id_to_decoration_insts_.find(id);
+  // |id| has no decorations
+  if (ids_iter == id_to_decoration_insts_.end()) return decorations;
+
+  // Process |id|'s decorations. Some of them might be groups, in which case
+  // add them to the stack.
+  for (ir::Instruction* inst : ids_iter->second) {
+    const bool is_linkage =
+        inst->opcode() == SpvOpDecorate &&
+        inst->GetSingleWordInOperand(1u) == SpvDecorationLinkageAttributes;
+    if (include_linkage || !is_linkage) process(inst);
+  }
+
+  // If the stack is not empty, then it contains groups ID: retrieve their
+  // decorations and process them. If any of those decorations is applying a
+  // group, push that group ID onto the stack.
+  while (!ids_to_process.empty()) {
+    const uint32_t id_to_process = ids_to_process.top();
+    ids_to_process.pop();
+
+    // Retrieve the decorations of that group
+    const auto group_iter = group_to_decoration_insts_.find(id_to_process);
+    if (group_iter != group_to_decoration_insts_.end()) {
+      // Process all the decorations applied by the group.
+      for (T inst : group_iter->second) process(inst);
+    } else {
+      // Something went wrong.
+      assert(false);
+      return std::vector<T>();
+    }
+  }
+
+  return decorations;
+}
+
+}  // namespace analysis
+}  // namespace opt
+}  // namespace spvtools
diff --git a/source/opt/decoration_manager.h b/source/opt/decoration_manager.h
new file mode 100644
index 0000000..acd8aa8
--- /dev/null
+++ b/source/opt/decoration_manager.h
@@ -0,0 +1,77 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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_DECORATION_MANAGER_H_
+#define LIBSPIRV_OPT_DECORATION_MANAGER_H_
+
+#include <unordered_map>
+#include <vector>
+
+#include "instruction.h"
+#include "module.h"
+
+namespace spvtools {
+namespace opt {
+namespace analysis {
+
+// A class for analyzing and managing decorations in an ir::Module.
+class DecorationManager {
+ public:
+  // Constructs a decoration manager from the given |module|
+  DecorationManager(ir::Module* module) { AnalyzeDecorations(module); }
+  // Removes all decorations from |id|, which should not be a group ID, except
+  // for linkage decorations if |keep_linkage| is set.
+  void RemoveDecorationsFrom(uint32_t id, bool keep_linkage);
+  // Returns a vector of all decorations affecting |id|. If a group is applied
+  // to |id|, the decorations of that group are returned rather than the group
+  // decoration instruction. If |include_linkage| is not set, linkage
+  // decorations won't be returned.
+  std::vector<ir::Instruction*> GetDecorationsFor(uint32_t id,
+                                                  bool include_linkage);
+  std::vector<const ir::Instruction*> GetDecorationsFor(
+      uint32_t id, bool include_linkage) const;
+  // Returns whether two IDs have the same decorations. Two SpvOpGroupDecorate
+  // instructions that apply the same decorations but to different IDs, still
+  // count as being the same.
+  bool HaveTheSameDecorations(uint32_t id1, uint32_t id2) const;
+  // Returns whether two decorations are the same. SpvOpDecorateId is currently
+  // not handled and will return false no matter what.
+  bool AreDecorationsTheSame(const ir::Instruction* inst1,
+                             const ir::Instruction* inst2) const;
+
+ private:
+  using IdToDecorationInstsMap =
+      std::unordered_map<uint32_t, std::vector<ir::Instruction*>>;
+  // Analyzes the defs and uses in the given |module| and populates data
+  // structures in this class. Does nothing if |module| is nullptr.
+  void AnalyzeDecorations(ir::Module* module);
+
+  template <typename T>
+  std::vector<T> InternalGetDecorationsFor(uint32_t id, bool include_linkage);
+
+  // Mapping from ids to the instructions applying a decoration to them. In
+  // other words, for each id you get all decoration instructions referencing
+  // that id, be it directly (SpvOpDecorate, SpvOpMemberDecorate and
+  // SpvOpDecorateId), or indirectly (SpvOpGroupDecorate,
+  // SpvOpMemberGroupDecorate).
+  IdToDecorationInstsMap id_to_decoration_insts_;
+  // Mapping from group ids to all the decoration instructions they apply.
+  IdToDecorationInstsMap group_to_decoration_insts_;
+};
+
+}  // namespace analysis
+}  // namespace opt
+}  // namespace spvtools
+
+#endif  // LIBSPIRV_OPT_DECORATION_MANAGER_H_
diff --git a/source/opt/def_use_manager.cpp b/source/opt/def_use_manager.cpp
index bf0d1e3..da4283a 100644
--- a/source/opt/def_use_manager.cpp
+++ b/source/opt/def_use_manager.cpp
@@ -72,6 +72,12 @@
   return iter->second;
 }
 
+const ir::Instruction* DefUseManager::GetDef(uint32_t id) const {
+  const auto iter = id_to_def_.find(id);
+  if (iter == id_to_def_.end()) return nullptr;
+  return iter->second;
+}
+
 UseList* DefUseManager::GetUses(uint32_t id) {
   auto iter = id_to_uses_.find(id);
   if (iter == id_to_uses_.end()) return nullptr;
diff --git a/source/opt/def_use_manager.h b/source/opt/def_use_manager.h
index a639cab..e4d8a3e 100644
--- a/source/opt/def_use_manager.h
+++ b/source/opt/def_use_manager.h
@@ -71,6 +71,7 @@
   // Returns the def instruction for the given |id|. If there is no instruction
   // defining |id|, returns nullptr.
   ir::Instruction* GetDef(uint32_t id);
+  const ir::Instruction* GetDef(uint32_t id) const;
   // Returns the use instructions for the given |id|. If there is no uses of
   // |id|, returns nullptr.
   UseList* GetUses(uint32_t id);
diff --git a/source/opt/eliminate_dead_constant_pass.cpp b/source/opt/eliminate_dead_constant_pass.cpp
index 9d7a148..f8a99157 100644
--- a/source/opt/eliminate_dead_constant_pass.cpp
+++ b/source/opt/eliminate_dead_constant_pass.cpp
@@ -40,7 +40,8 @@
       count =
           std::count_if(uses->begin(), uses->end(), [](const analysis::Use& u) {
             return !(ir::IsAnnotationInst(u.inst->opcode()) ||
-                     ir::IsDebugInst(u.inst->opcode()));
+                     ir::IsDebug1Inst(u.inst->opcode()) ||
+                     ir::IsDebug2Inst(u.inst->opcode()));
           });
     }
     use_counts[c] = count;
@@ -95,7 +96,8 @@
     if (analysis::UseList* uses = def_use.GetUses(dc->result_id())) {
       for (const auto& u : *uses) {
         if (ir::IsAnnotationInst(u.inst->opcode()) ||
-            ir::IsDebugInst(u.inst->opcode())) {
+            ir::IsDebug1Inst(u.inst->opcode()) ||
+            ir::IsDebug2Inst(u.inst->opcode())) {
           dead_others.insert(u.inst);
         }
       }
diff --git a/source/opt/flatten_decoration_pass.cpp b/source/opt/flatten_decoration_pass.cpp
index 98bb69c..20437e3 100644
--- a/source/opt/flatten_decoration_pass.cpp
+++ b/source/opt/flatten_decoration_pass.cpp
@@ -143,8 +143,8 @@
   // An OpDecorationGroup instruction might not have been used by an
   // OpGroupDecorate or OpGroupMemberDecorate instruction.
   if (!group_ids.empty()) {
-    for (auto debug_inst_iter = module->debug_begin();
-         debug_inst_iter != module->debug_end();) {
+    for (auto debug_inst_iter = module->debug2_begin();
+         debug_inst_iter != module->debug2_end();) {
       if (debug_inst_iter->opcode() == SpvOp::SpvOpName) {
         const uint32_t target = debug_inst_iter->GetSingleWordOperand(0);
         if (group_ids.count(target)) {
diff --git a/source/opt/function.cpp b/source/opt/function.cpp
index 7f7952c..4ad2dce 100644
--- a/source/opt/function.cpp
+++ b/source/opt/function.cpp
@@ -14,9 +14,34 @@
 
 #include "function.h"
 
+#include "make_unique.h"
+
 namespace spvtools {
 namespace ir {
 
+Function::Function(const Function& f)
+    : module_(nullptr),
+      def_inst_(MakeUnique<Instruction>(f.DefInst())),
+      params_(),
+      blocks_(),
+      end_inst_() {
+  params_.reserve(f.params_.size());
+  f.ForEachParam(
+      [this](const Instruction* insn) {
+        AddParameter(MakeUnique<Instruction>(*insn));
+      },
+      true);
+
+  blocks_.reserve(f.blocks_.size());
+  for (const auto& b : f.blocks_) {
+    std::unique_ptr<BasicBlock> bb = MakeUnique<BasicBlock>(*b);
+    bb->SetParent(this);
+    AddBasicBlock(std::move(bb));
+  }
+
+  SetFunctionEnd(MakeUnique<Instruction>(f.function_end()));
+}
+
 void Function::ForEachInst(const std::function<void(Instruction*)>& f,
                            bool run_on_debug_line_insts) {
   if (def_inst_) def_inst_->ForEachInst(f, run_on_debug_line_insts);
@@ -36,8 +61,8 @@
         ->ForEachInst(f, run_on_debug_line_insts);
 
   for (const auto& bb : blocks_)
-    static_cast<const BasicBlock*>(bb.get())
-        ->ForEachInst(f, run_on_debug_line_insts);
+    static_cast<const BasicBlock*>(bb.get())->ForEachInst(
+        f, run_on_debug_line_insts);
 
   if (end_inst_)
     static_cast<const Instruction*>(end_inst_.get())
diff --git a/source/opt/function.h b/source/opt/function.h
index 949f99a..aa15c50 100644
--- a/source/opt/function.h
+++ b/source/opt/function.h
@@ -38,8 +38,14 @@
   // Creates a function instance declared by the given OpFunction instruction
   // |def_inst|.
   inline explicit Function(std::unique_ptr<Instruction> def_inst);
+  // Creates a function instance based on the given function |f|.
+  //
+  // The parent module will default to null and needs to be explicitly set by
+  // the user.
+  explicit Function(const Function& f);
   // The OpFunction instruction that begins the definition of this function.
   Instruction& DefInst() { return *def_inst_; }
+  const Instruction& DefInst() const { return *def_inst_; }
 
   // Sets the enclosing module for this function.
   void SetParent(Module* module) { module_ = module; }
@@ -51,10 +57,17 @@
   // Saves the given function end instruction.
   inline void SetFunctionEnd(std::unique_ptr<Instruction> end_inst);
 
+  // Returns the given function end instruction.
+  inline Instruction* function_end() { return end_inst_.get(); }
+  inline const Instruction& function_end() const { return *end_inst_; }
+
   // Returns function's id
   inline uint32_t result_id() const { return def_inst_->result_id(); }
 
-  // Returns function's type id
+//  // Returns function's type id
+//  inline uint32_t type_id() const { return def_inst_->GetSingleWordInOperand(1u); }
+
+  // Returns function's return type id
   inline uint32_t type_id() const { return def_inst_->type_id(); }
 
   iterator begin() { return iterator(&blocks_, blocks_.begin()); }
diff --git a/source/opt/instruction.h b/source/opt/instruction.h
index 89c9da0..0ded232 100644
--- a/source/opt/instruction.h
+++ b/source/opt/instruction.h
@@ -58,9 +58,17 @@
   spv_operand_type_t type;      // Type of this logical operand.
   std::vector<uint32_t> words;  // Binary segments of this logical operand.
 
+  friend bool operator==(const Operand& o1, const Operand& o2) {
+    return o1.type == o2.type && o1.words == o2.words;
+  }
+
   // TODO(antiagainst): create fields for literal number kind, width, etc.
 };
 
+inline bool operator!=(const Operand& o1, const Operand& o2) {
+  return !(o1 == o2);
+}
+
 // A SPIR-V instruction. It contains the opcode and any additional logical
 // operand, including the result id (if any) and result type id (if any). It
 // may also contain line-related debug instruction (OpLine, OpNoLine) directly
@@ -139,6 +147,10 @@
   inline void SetResultType(uint32_t ty_id);
   // Sets the result id
   inline void SetResultId(uint32_t res_id);
+  // Remove the |index|-th operand
+  void RemoveOperand(uint32_t index) {
+    operands_.erase(operands_.begin() + index);
+  }
 
   // The following methods are similar to the above, but are for in operands.
   uint32_t NumInOperands() const {
@@ -151,6 +163,9 @@
   uint32_t GetSingleWordInOperand(uint32_t index) const {
     return GetSingleWordOperand(index + TypeResultIdCount());
   }
+  void RemoveInOperand(uint32_t index) {
+    operands_.erase(operands_.begin() + index + TypeResultIdCount());
+  }
 
   // Returns true if this instruction is OpNop.
   inline bool IsNop() const;
@@ -166,6 +181,12 @@
   inline void ForEachInst(const std::function<void(const Instruction*)>& f,
                           bool run_on_debug_line_insts = false) const;
 
+  // Runs the given function |f| on all operand ids.
+  //
+  // |f| should not transform an ID into 0, as 0 is an invalid ID.
+  inline void ForEachId(const std::function<void(uint32_t*)>& f);
+  inline void ForEachId(const std::function<void(const uint32_t*)>& f) const;
+
   // Runs the given function |f| on all "in" operand ids
   inline void ForEachInId(const std::function<void(uint32_t*)>& f);
   inline void ForEachInId(const std::function<void(const uint32_t*)>& f) const;
@@ -246,6 +267,20 @@
   f(this);
 }
 
+inline void Instruction::ForEachId(const std::function<void(uint32_t*)>& f) {
+  for (auto& opnd : operands_)
+    if (spvIsIdType(opnd.type)) f(&opnd.words[0]);
+  if (type_id_ != 0u)
+    type_id_ = GetSingleWordOperand(0u);
+  if (result_id_ != 0u) result_id_ = GetSingleWordOperand(type_id_ == 0u ? 0u : 1u);
+}
+
+inline void Instruction::ForEachId(
+    const std::function<void(const uint32_t*)>& f) const {
+  for (const auto& opnd : operands_)
+    if (spvIsIdType(opnd.type)) f(&opnd.words[0]);
+}
+
 inline void Instruction::ForEachInId(const std::function<void(uint32_t*)>& f) {
   for (auto& opnd : operands_) {
     switch (opnd.type) {
diff --git a/source/opt/ir_loader.cpp b/source/opt/ir_loader.cpp
index d358e97..854176e 100644
--- a/source/opt/ir_loader.cpp
+++ b/source/opt/ir_loader.cpp
@@ -99,8 +99,10 @@
         module_->AddEntryPoint(std::move(spv_inst));
       } else if (opcode == SpvOpExecutionMode) {
         module_->AddExecutionMode(std::move(spv_inst));
-      } else if (IsDebugInst(opcode)) {
-        module_->AddDebugInst(std::move(spv_inst));
+      } else if (IsDebug1Inst(opcode)) {
+        module_->AddDebug1Inst(std::move(spv_inst));
+      } else if (IsDebug2Inst(opcode)) {
+        module_->AddDebug2Inst(std::move(spv_inst));
       } else if (IsAnnotationInst(opcode)) {
         module_->AddAnnotationInst(std::move(spv_inst));
       } else if (IsTypeInst(opcode)) {
diff --git a/source/opt/mem_pass.cpp b/source/opt/mem_pass.cpp
index 6768606..8b62f9f 100644
--- a/source/opt/mem_pass.cpp
+++ b/source/opt/mem_pass.cpp
@@ -150,7 +150,7 @@
 
 void MemPass::FindNamedOrDecoratedIds() {
   named_or_decorated_ids_.clear();
-  for (auto& di : module_->debugs())
+  for (auto& di : module_->debugs2())
     if (di.opcode() == SpvOpName)
       named_or_decorated_ids_.insert(di.GetSingleWordInOperand(0));
   for (auto& ai : module_->annotations())
diff --git a/source/opt/module.cpp b/source/opt/module.cpp
index 290e88d..9a7447f 100644
--- a/source/opt/module.cpp
+++ b/source/opt/module.cpp
@@ -83,7 +83,8 @@
   if (memory_model_) DELEGATE(memory_model_);
   for (auto& i : entry_points_) DELEGATE(i);
   for (auto& i : execution_modes_) DELEGATE(i);
-  for (auto& i : debugs_) DELEGATE(i);
+  for (auto& i : debugs1_) DELEGATE(i);
+  for (auto& i : debugs2_) DELEGATE(i);
   for (auto& i : annotations_) DELEGATE(i);
   for (auto& i : types_values_) DELEGATE(i);
   for (auto& i : functions_) DELEGATE(i);
@@ -101,7 +102,8 @@
   if (memory_model_) DELEGATE(memory_model_);
   for (auto& i : entry_points_) DELEGATE(i);
   for (auto& i : execution_modes_) DELEGATE(i);
-  for (auto& i : debugs_) DELEGATE(i);
+  for (auto& i : debugs1_) DELEGATE(i);
+  for (auto& i : debugs2_) DELEGATE(i);
   for (auto& i : annotations_) DELEGATE(i);
   for (auto& i : types_values_) DELEGATE(i);
   for (auto& i : functions_) {
diff --git a/source/opt/module.h b/source/opt/module.h
index e29615f..1a4e4a2 100644
--- a/source/opt/module.h
+++ b/source/opt/module.h
@@ -66,8 +66,14 @@
   inline void AddEntryPoint(std::unique_ptr<Instruction> e);
   // Appends an execution mode instruction to this module.
   inline void AddExecutionMode(std::unique_ptr<Instruction> e);
-  // Appends a debug instruction (excluding OpLine & OpNoLine) to this module.
-  inline void AddDebugInst(std::unique_ptr<Instruction> d);
+  // Appends a debug 1 instruction (excluding OpLine & OpNoLine) to this module.
+  // "debug 1" instructions are the ones in layout section 7.a), see section
+  // 2.4 Logical Layout of a Module from the SPIR-V specification.
+  inline void AddDebug1Inst(std::unique_ptr<Instruction> d);
+  // Appends a debug 2 instruction (excluding OpLine & OpNoLine) to this module.
+  // "debug 2" instructions are the ones in layout section 7.b), see section
+  // 2.4 Logical Layout of a Module from the SPIR-V specification.
+  inline void AddDebug2Inst(std::unique_ptr<Instruction> d);
   // Appends an annotation instruction to this module.
   inline void AddAnnotationInst(std::unique_ptr<Instruction> a);
   // Appends a type-declaration instruction to this module.
@@ -94,25 +100,66 @@
 
   inline uint32_t id_bound() const { return header_.bound; }
 
-  // Iterators for debug instructions (excluding OpLine & OpNoLine) contained in
-  // this module.
-  inline inst_iterator debug_begin();
-  inline inst_iterator debug_end();
-  inline IteratorRange<inst_iterator> debugs();
-  inline IteratorRange<const_inst_iterator> debugs() const;
+  inline uint32_t version() const { return header_.version; }
+
+  // Iterators for capabilities instructions contained in this module.
+  inline inst_iterator capability_begin();
+  inline inst_iterator capability_end();
+  inline IteratorRange<inst_iterator> capabilities();
+  inline IteratorRange<const_inst_iterator> capabilities() const;
+
+  // Iterators for ext_inst_imports instructions contained in this module.
+  inline inst_iterator ext_inst_import_begin();
+  inline inst_iterator ext_inst_import_end();
+  inline IteratorRange<inst_iterator> ext_inst_imports();
+  inline IteratorRange<const_inst_iterator> ext_inst_imports() const;
+
+  // Return the memory model instruction contained inthis module.
+  inline Instruction* GetMemoryModel() { return memory_model_.get(); }
+  inline const Instruction* GetMemoryModel() const { return memory_model_.get(); }
+
+  // Iterators for debug 1 instructions (excluding OpLine & OpNoLine) contained
+  // in this module.
+  inline inst_iterator debug1_begin();
+  inline inst_iterator debug1_end();
+  inline IteratorRange<inst_iterator> debugs1();
+  inline IteratorRange<const_inst_iterator> debugs1() const;
+
+  // Iterators for debug 2 instructions (excluding OpLine & OpNoLine) contained
+  // in this module.
+  inline inst_iterator debug2_begin();
+  inline inst_iterator debug2_end();
+  inline IteratorRange<inst_iterator> debugs2();
+  inline IteratorRange<const_inst_iterator> debugs2() const;
 
   // Iterators for entry point instructions contained in this module
   inline IteratorRange<inst_iterator> entry_points();
   inline IteratorRange<const_inst_iterator> entry_points() const;
 
+  // Iterators for execution_modes instructions contained in this module.
+  inline inst_iterator execution_mode_begin();
+  inline inst_iterator execution_mode_end();
+  inline IteratorRange<inst_iterator> execution_modes();
+  inline IteratorRange<const_inst_iterator> execution_modes() const;
+
   // Clears all debug instructions (excluding OpLine & OpNoLine).
-  void debug_clear() { debugs_.clear(); }
+  void debug_clear() { debug1_clear(); debug2_clear(); }
+
+  // Clears all debug 1 instructions (excluding OpLine & OpNoLine).
+  void debug1_clear() { debugs1_.clear(); }
+
+  // Clears all debug 2 instructions (excluding OpLine & OpNoLine).
+  void debug2_clear() { debugs2_.clear(); }
 
   // Iterators for annotation instructions contained in this module.
+  inline inst_iterator annotation_begin();
+  inline inst_iterator annotation_end();
   IteratorRange<inst_iterator> annotations();
   IteratorRange<const_inst_iterator> annotations() const;
 
   // Iterators for extension instructions contained in this module.
+  inline inst_iterator extension_begin();
+  inline inst_iterator extension_end();
   IteratorRange<inst_iterator> extensions();
   IteratorRange<const_inst_iterator> extensions() const;
 
@@ -161,7 +208,8 @@
   std::unique_ptr<Instruction> memory_model_;
   std::vector<std::unique_ptr<Instruction>> entry_points_;
   std::vector<std::unique_ptr<Instruction>> execution_modes_;
-  std::vector<std::unique_ptr<Instruction>> debugs_;
+  std::vector<std::unique_ptr<Instruction>> debugs1_;
+  std::vector<std::unique_ptr<Instruction>> debugs2_;
   std::vector<std::unique_ptr<Instruction>> annotations_;
   // Type declarations, constants, and global variable declarations.
   std::vector<std::unique_ptr<Instruction>> types_values_;
@@ -192,8 +240,12 @@
   execution_modes_.emplace_back(std::move(e));
 }
 
-inline void Module::AddDebugInst(std::unique_ptr<Instruction> d) {
-  debugs_.emplace_back(std::move(d));
+inline void Module::AddDebug1Inst(std::unique_ptr<Instruction> d) {
+  debugs1_.emplace_back(std::move(d));
+}
+
+inline void Module::AddDebug2Inst(std::unique_ptr<Instruction> d) {
+  debugs2_.emplace_back(std::move(d));
 }
 
 inline void Module::AddAnnotationInst(std::unique_ptr<Instruction> a) {
@@ -212,19 +264,64 @@
   functions_.emplace_back(std::move(f));
 }
 
-inline Module::inst_iterator Module::debug_begin() {
-  return inst_iterator(&debugs_, debugs_.begin());
+inline Module::inst_iterator Module::capability_begin() {
+  return inst_iterator(&capabilities_, capabilities_.begin());
 }
-inline Module::inst_iterator Module::debug_end() {
-  return inst_iterator(&debugs_, debugs_.end());
+inline Module::inst_iterator Module::capability_end() {
+  return inst_iterator(&capabilities_, capabilities_.end());
 }
 
-inline IteratorRange<Module::inst_iterator> Module::debugs() {
-  return make_range(debugs_);
+inline IteratorRange<Module::inst_iterator> Module::capabilities() {
+  return make_range(capabilities_);
 }
 
-inline IteratorRange<Module::const_inst_iterator> Module::debugs() const {
-  return make_const_range(debugs_);
+inline IteratorRange<Module::const_inst_iterator> Module::capabilities() const {
+  return make_const_range(capabilities_);
+}
+
+inline Module::inst_iterator Module::ext_inst_import_begin() {
+  return inst_iterator(&ext_inst_imports_, ext_inst_imports_.begin());
+}
+inline Module::inst_iterator Module::ext_inst_import_end() {
+  return inst_iterator(&ext_inst_imports_, ext_inst_imports_.end());
+}
+
+inline IteratorRange<Module::inst_iterator> Module::ext_inst_imports() {
+  return make_range(ext_inst_imports_);
+}
+
+inline IteratorRange<Module::const_inst_iterator> Module::ext_inst_imports() const {
+  return make_const_range(ext_inst_imports_);
+}
+
+inline Module::inst_iterator Module::debug1_begin() {
+  return inst_iterator(&debugs1_, debugs1_.begin());
+}
+inline Module::inst_iterator Module::debug1_end() {
+  return inst_iterator(&debugs1_, debugs1_.end());
+}
+
+inline IteratorRange<Module::inst_iterator> Module::debugs1() {
+  return make_range(debugs1_);
+}
+
+inline IteratorRange<Module::const_inst_iterator> Module::debugs1() const {
+  return make_const_range(debugs1_);
+}
+
+inline Module::inst_iterator Module::debug2_begin() {
+  return inst_iterator(&debugs2_, debugs2_.begin());
+}
+inline Module::inst_iterator Module::debug2_end() {
+  return inst_iterator(&debugs2_, debugs2_.end());
+}
+
+inline IteratorRange<Module::inst_iterator> Module::debugs2() {
+  return make_range(debugs2_);
+}
+
+inline IteratorRange<Module::const_inst_iterator> Module::debugs2() const {
+  return make_const_range(debugs2_);
 }
 
 inline IteratorRange<Module::inst_iterator> Module::entry_points() {
@@ -235,6 +332,28 @@
   return make_const_range(entry_points_);
 }
 
+inline Module::inst_iterator Module::execution_mode_begin() {
+  return inst_iterator(&execution_modes_, execution_modes_.begin());
+}
+inline Module::inst_iterator Module::execution_mode_end() {
+  return inst_iterator(&execution_modes_, execution_modes_.end());
+}
+
+inline IteratorRange<Module::inst_iterator> Module::execution_modes() {
+  return make_range(execution_modes_);
+}
+
+inline IteratorRange<Module::const_inst_iterator> Module::execution_modes() const {
+  return make_const_range(execution_modes_);
+}
+
+inline Module::inst_iterator Module::annotation_begin() {
+  return inst_iterator(&annotations_, annotations_.begin());
+}
+inline Module::inst_iterator Module::annotation_end() {
+  return inst_iterator(&annotations_, annotations_.end());
+}
+
 inline IteratorRange<Module::inst_iterator> Module::annotations() {
   return make_range(annotations_);
 }
@@ -243,6 +362,13 @@
   return make_const_range(annotations_);
 }
 
+inline Module::inst_iterator Module::extension_begin() {
+  return inst_iterator(&extensions_, extensions_.begin());
+}
+inline Module::inst_iterator Module::extension_end() {
+  return inst_iterator(&extensions_, extensions_.end());
+}
+
 inline IteratorRange<Module::inst_iterator> Module::extensions() {
   return make_range(extensions_);
 }
diff --git a/source/opt/pass_manager.cpp b/source/opt/pass_manager.cpp
index 18267db..2def7bb 100644
--- a/source/opt/pass_manager.cpp
+++ b/source/opt/pass_manager.cpp
@@ -28,6 +28,7 @@
   if (status == Pass::Status::SuccessWithChange) {
     module->SetIdBound(module->ComputeIdBound());
   }
+  passes_.clear();
   return status;
 }
 
diff --git a/source/opt/pass_manager.h b/source/opt/pass_manager.h
index 0bf29f7..2cf9159 100644
--- a/source/opt/pass_manager.h
+++ b/source/opt/pass_manager.h
@@ -63,6 +63,8 @@
   // registered after the error-reporting pass will be skipped. Returns the
   // corresponding Status::Success if processing is succesful to indicate
   // whether changes are made to the module.
+  //
+  // After running all the passes, they are removed from the list.
   Pass::Status Run(ir::Module* module);
 
  private:
diff --git a/source/opt/reflect.h b/source/opt/reflect.h
index 16ea0bd..8c8c136 100644
--- a/source/opt/reflect.h
+++ b/source/opt/reflect.h
@@ -24,8 +24,13 @@
 // following functions tend to be outdated and should be updated when SPIR-V
 // version bumps.
 
-inline bool IsDebugInst(SpvOp opcode) {
-  return (opcode >= SpvOpSourceContinued && opcode <= SpvOpLine) ||
+inline bool IsDebug1Inst(SpvOp opcode) {
+  return (opcode >= SpvOpSourceContinued && opcode <= SpvOpSourceExtension) ||
+         opcode == SpvOpString || opcode == SpvOpLine ||
+         opcode == SpvOpNoLine || opcode == SpvOpModuleProcessed;
+}
+inline bool IsDebug2Inst(SpvOp opcode) {
+  return opcode == SpvOpName || opcode == SpvOpMemberName ||
          opcode == SpvOpNoLine || opcode == SpvOpModuleProcessed;
 }
 inline bool IsDebugLineInst(SpvOp opcode) {
diff --git a/source/opt/remove_duplicates_pass.cpp b/source/opt/remove_duplicates_pass.cpp
new file mode 100644
index 0000000..a44e5dc
--- /dev/null
+++ b/source/opt/remove_duplicates_pass.cpp
@@ -0,0 +1,274 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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 "remove_duplicates_pass.h"
+
+#include <cstring>
+
+#include <algorithm>
+#include <limits>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+#include "decoration_manager.h"
+#include "opcode.h"
+
+namespace spvtools {
+namespace opt {
+
+using ir::Instruction;
+using ir::Module;
+using ir::Operand;
+using opt::analysis::DefUseManager;
+using opt::analysis::DecorationManager;
+
+Pass::Status RemoveDuplicatesPass::Process(Module* module) {
+  DefUseManager defUseManager(consumer(), module);
+  DecorationManager decManager(module);
+
+  bool modified = RemoveDuplicateCapabilities(module);
+  modified |= RemoveDuplicatesExtInstImports(module, defUseManager);
+  modified |= RemoveDuplicateTypes(module, defUseManager, decManager);
+  modified |= RemoveDuplicateDecorations(module);
+
+  return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
+}
+
+bool RemoveDuplicatesPass::RemoveDuplicateCapabilities(Module* module) const {
+  bool modified = false;
+
+  std::unordered_set<uint32_t> capabilities;
+  for (auto i = module->capability_begin(); i != module->capability_end();) {
+    auto res = capabilities.insert(i->GetSingleWordOperand(0u));
+
+    if (res.second) {
+      // Never seen before, keep it.
+      ++i;
+    } else {
+      // It's a duplicate, remove it.
+      i = i.Erase();
+      modified = true;
+    }
+  }
+
+  return modified;
+}
+
+bool RemoveDuplicatesPass::RemoveDuplicatesExtInstImports(
+    Module* module, analysis::DefUseManager& defUseManager) const {
+  bool modified = false;
+
+  std::unordered_map<std::string, SpvId> extInstImports;
+  for (auto i = module->ext_inst_import_begin();
+       i != module->ext_inst_import_end();) {
+    auto res = extInstImports.emplace(
+        reinterpret_cast<const char*>(i->GetInOperand(0u).words.data()),
+        i->result_id());
+    if (res.second) {
+      // Never seen before, keep it.
+      ++i;
+    } else {
+      // It's a duplicate, remove it.
+      defUseManager.ReplaceAllUsesWith(i->result_id(), res.first->second);
+      i = i.Erase();
+      modified = true;
+    }
+  }
+
+  return modified;
+}
+
+bool RemoveDuplicatesPass::RemoveDuplicateTypes(
+    Module* module, DefUseManager& defUseManager,
+    DecorationManager& decManager) const {
+  bool modified = false;
+
+  std::vector<Instruction> visitedTypes;
+  visitedTypes.reserve(module->types_values().size());
+
+  for (auto i = module->types_values_begin();
+       i != module->types_values_end();) {
+    // We only care about types.
+    if (!spvOpcodeGeneratesType((i->opcode())) &&
+        i->opcode() != SpvOpTypeForwardPointer) {
+      ++i;
+      continue;
+    }
+
+    // Is the current type equal to one of the types we have aready visited?
+    SpvId idToKeep = 0u;
+    for (auto j : visitedTypes) {
+      if (AreTypesEqual(*i, j, defUseManager, decManager)) {
+        idToKeep = j.result_id();
+        break;
+      }
+    }
+
+    if (idToKeep == 0u) {
+      // This is a never seen before type, keep it around.
+      visitedTypes.emplace_back(*i);
+      ++i;
+    } else {
+      // The same type has already been seen before, remove this one.
+      defUseManager.ReplaceAllUsesWith(i->result_id(), idToKeep);
+      modified = true;
+      i = i.Erase();
+    }
+  }
+
+  return modified;
+}
+
+bool RemoveDuplicatesPass::RemoveDuplicateDecorations(
+    ir::Module* module) const {
+  bool modified = false;
+
+  std::unordered_map<SpvId, const Instruction*> constants;
+  for (const auto& i : module->types_values())
+    if (i.opcode() == SpvOpConstant) constants[i.result_id()] = &i;
+  for (const auto& i : module->types_values())
+    if (i.opcode() == SpvOpConstant) constants[i.result_id()] = &i;
+
+  std::vector<const Instruction*> visitedDecorations;
+  visitedDecorations.reserve(module->annotations().size());
+
+  opt::analysis::DecorationManager decorationManager(module);
+  for (auto i = module->annotation_begin(); i != module->annotation_end();) {
+    // Is the current decoration equal to one of the decorations we have aready
+    // visited?
+    bool alreadyVisited = false;
+    for (const Instruction* j : visitedDecorations) {
+      if (decorationManager.AreDecorationsTheSame(&*i, j)) {
+        alreadyVisited = true;
+        break;
+      }
+    }
+
+    if (!alreadyVisited) {
+      // This is a never seen before decoration, keep it around.
+      visitedDecorations.emplace_back(&*i);
+      ++i;
+    } else {
+      // The same decoration has already been seen before, remove this one.
+      modified = true;
+      i = i.Erase();
+    }
+  }
+
+  return modified;
+}
+
+bool RemoveDuplicatesPass::AreTypesEqual(const Instruction& inst1,
+                                         const Instruction& inst2,
+                                         const DefUseManager& defUseManager,
+                                         const DecorationManager& decManager) {
+  if (inst1.opcode() != inst2.opcode()) return false;
+  if (!decManager.HaveTheSameDecorations(inst1.result_id(), inst2.result_id()))
+    return false;
+
+  switch (inst1.opcode()) {
+    case SpvOpTypeVoid:
+    case SpvOpTypeBool:
+    case SpvOpTypeSampler:
+    case SpvOpTypeEvent:
+    case SpvOpTypeDeviceEvent:
+    case SpvOpTypeReserveId:
+    case SpvOpTypeQueue:
+    case SpvOpTypePipeStorage:
+    case SpvOpTypeNamedBarrier:
+      return true;
+    case SpvOpTypeInt:
+      return inst1.GetSingleWordInOperand(0u) ==
+                 inst2.GetSingleWordInOperand(0u) &&
+             inst1.GetSingleWordInOperand(1u) ==
+                 inst2.GetSingleWordInOperand(1u);
+    case SpvOpTypeFloat:
+    case SpvOpTypePipe:
+    case SpvOpTypeForwardPointer:
+      return inst1.GetSingleWordInOperand(0u) ==
+             inst2.GetSingleWordInOperand(0u);
+    case SpvOpTypeVector:
+    case SpvOpTypeMatrix:
+      return AreTypesEqual(
+                 *defUseManager.GetDef(inst1.GetSingleWordInOperand(0u)),
+                 *defUseManager.GetDef(inst2.GetSingleWordInOperand(0u)),
+                 defUseManager, decManager) &&
+             inst1.GetSingleWordInOperand(1u) ==
+                 inst2.GetSingleWordInOperand(1u);
+    case SpvOpTypeImage:
+      return AreTypesEqual(
+                 *defUseManager.GetDef(inst1.GetSingleWordInOperand(0u)),
+                 *defUseManager.GetDef(inst2.GetSingleWordInOperand(0u)),
+                 defUseManager, decManager) &&
+             inst1.GetSingleWordInOperand(1u) ==
+                 inst2.GetSingleWordInOperand(1u) &&
+             inst1.GetSingleWordInOperand(2u) ==
+                 inst2.GetSingleWordInOperand(2u) &&
+             inst1.GetSingleWordInOperand(3u) ==
+                 inst2.GetSingleWordInOperand(3u) &&
+             inst1.GetSingleWordInOperand(4u) ==
+                 inst2.GetSingleWordInOperand(4u) &&
+             inst1.GetSingleWordInOperand(5u) ==
+                 inst2.GetSingleWordInOperand(5u) &&
+             inst1.GetSingleWordInOperand(6u) ==
+                 inst2.GetSingleWordInOperand(6u) &&
+             inst1.NumOperands() == inst2.NumOperands() &&
+             (inst1.NumInOperands() == 7u ||
+              inst1.GetSingleWordInOperand(7u) ==
+                  inst2.GetSingleWordInOperand(7u));
+    case SpvOpTypeSampledImage:
+    case SpvOpTypeRuntimeArray:
+      return AreTypesEqual(
+          *defUseManager.GetDef(inst1.GetSingleWordInOperand(0u)),
+          *defUseManager.GetDef(inst2.GetSingleWordInOperand(0u)),
+          defUseManager, decManager);
+    case SpvOpTypeArray:
+      return AreTypesEqual(
+                 *defUseManager.GetDef(inst1.GetSingleWordInOperand(0u)),
+                 *defUseManager.GetDef(inst2.GetSingleWordInOperand(0u)),
+                 defUseManager, decManager) &&
+             AreTypesEqual(
+                 *defUseManager.GetDef(inst1.GetSingleWordInOperand(1u)),
+                 *defUseManager.GetDef(inst2.GetSingleWordInOperand(1u)),
+                 defUseManager, decManager);
+    case SpvOpTypeStruct:
+    case SpvOpTypeFunction: {
+      bool res = inst1.NumInOperands() == inst2.NumInOperands();
+      for (uint32_t i = 0u; i < inst1.NumInOperands() && res; ++i)
+        res &= AreTypesEqual(
+            *defUseManager.GetDef(inst1.GetSingleWordInOperand(i)),
+            *defUseManager.GetDef(inst2.GetSingleWordInOperand(i)),
+            defUseManager, decManager);
+      return res;
+    }
+    case SpvOpTypeOpaque:
+      return std::strcmp(reinterpret_cast<const char*>(
+                             inst1.GetInOperand(0u).words.data()),
+                         reinterpret_cast<const char*>(
+                             inst2.GetInOperand(0u).words.data())) == 0;
+    case SpvOpTypePointer:
+      return inst1.GetSingleWordInOperand(0u) ==
+                 inst2.GetSingleWordInOperand(0u) &&
+             AreTypesEqual(
+                 *defUseManager.GetDef(inst1.GetSingleWordInOperand(1u)),
+                 *defUseManager.GetDef(inst2.GetSingleWordInOperand(1u)),
+                 defUseManager, decManager);
+    default:
+      return false;
+  }
+}
+
+}  // namespace opt
+}  // namespace spvtools
diff --git a/source/opt/remove_duplicates_pass.h b/source/opt/remove_duplicates_pass.h
new file mode 100644
index 0000000..fcf4a05
--- /dev/null
+++ b/source/opt/remove_duplicates_pass.h
@@ -0,0 +1,55 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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_REMOVE_DUPLICATES_PASS_H_
+#define LIBSPIRV_OPT_REMOVE_DUPLICATES_PASS_H_
+
+#include <unordered_map>
+
+#include "decoration_manager.h"
+#include "def_use_manager.h"
+#include "module.h"
+#include "pass.h"
+
+namespace spvtools {
+namespace opt {
+
+using IdDecorationsList =
+    std::unordered_map<uint32_t, std::vector<ir::Instruction*>>;
+
+// See optimizer.hpp for documentation.
+class RemoveDuplicatesPass : public Pass {
+ public:
+  const char* name() const override { return "remove-duplicates"; }
+  Status Process(ir::Module*) override;
+  // Returns whether two types are equal, and have the same decorations.
+  static bool AreTypesEqual(const ir::Instruction& inst1,
+                            const ir::Instruction& inst2,
+                            const analysis::DefUseManager& defUseManager,
+                            const analysis::DecorationManager& decoManager);
+
+ private:
+  bool RemoveDuplicateCapabilities(ir::Module* module) const;
+  bool RemoveDuplicatesExtInstImports(
+      ir::Module* module, analysis::DefUseManager& defUseManager) const;
+  bool RemoveDuplicateTypes(ir::Module* module,
+                            analysis::DefUseManager& defUseManager,
+                            analysis::DecorationManager& decManager) const;
+  bool RemoveDuplicateDecorations(ir::Module* module) const;
+};
+
+}  // namespace opt
+}  // namespace spvtools
+
+#endif  // LIBSPIRV_OPT_REMOVE_DUPLICATES_PASS_H_
diff --git a/source/opt/strip_debug_info_pass.cpp b/source/opt/strip_debug_info_pass.cpp
index 45dd344..3b2b6ca 100644
--- a/source/opt/strip_debug_info_pass.cpp
+++ b/source/opt/strip_debug_info_pass.cpp
@@ -18,7 +18,7 @@
 namespace opt {
 
 Pass::Status StripDebugInfoPass::Process(ir::Module* module) {
-  bool modified = !module->debugs().empty();
+  bool modified = !module->debugs1().empty() || !module->debugs2().empty();
   module->debug_clear();
 
   module->ForEachInst([&modified](ir::Instruction* inst) {
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 8ebcd93..54aa97d 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -180,6 +180,7 @@
   LIBS ${SPIRV_TOOLS})
 
 add_subdirectory(comp)
+add_subdirectory(link)
 add_subdirectory(opt)
 add_subdirectory(stats)
 add_subdirectory(val)
diff --git a/test/link/CMakeLists.txt b/test/link/CMakeLists.txt
new file mode 100644
index 0000000..9768ab3
--- /dev/null
+++ b/test/link/CMakeLists.txt
@@ -0,0 +1,43 @@
+# Copyright (c) 2017 Pierre Moreau
+#
+# 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.
+
+add_spvtools_unittest(TARGET link_binary_version
+  SRCS binary_version_test.cpp
+  LIBS SPIRV-Tools-opt SPIRV-Tools-link
+)
+
+add_spvtools_unittest(TARGET link_memory_model
+  SRCS memory_model_test.cpp
+  LIBS SPIRV-Tools-opt SPIRV-Tools-link
+)
+
+add_spvtools_unittest(TARGET link_entry_points
+  SRCS entry_points_test.cpp
+  LIBS SPIRV-Tools-opt SPIRV-Tools-link
+)
+
+add_spvtools_unittest(TARGET link_global_values_amount
+  SRCS global_values_amount_test.cpp
+  LIBS SPIRV-Tools-opt SPIRV-Tools-link
+)
+
+add_spvtools_unittest(TARGET link_ids_limit
+  SRCS ids_limit_test.cpp
+  LIBS SPIRV-Tools-opt SPIRV-Tools-link
+)
+
+add_spvtools_unittest(TARGET link_matching_imports_to_exports
+  SRCS matching_imports_to_exports_test.cpp
+  LIBS SPIRV-Tools-opt SPIRV-Tools-link
+)
diff --git a/test/link/binary_version_test.cpp b/test/link/binary_version_test.cpp
new file mode 100644
index 0000000..b78440d
--- /dev/null
+++ b/test/link/binary_version_test.cpp
@@ -0,0 +1,54 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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 "gmock/gmock.h"
+#include "linker_fixture.h"
+
+namespace {
+
+using BinaryVersion = spvtest::LinkerTest;
+
+TEST_F(BinaryVersion, LinkerChoosesMaxSpirvVersion) {
+  spvtest::Binaries binaries = {
+      {
+          SpvMagicNumber,
+          0x00000300u,
+          SPV_GENERATOR_CODEPLAY,
+          1u,  // NOTE: Bound
+          0u   // NOTE: Schema; reserved
+      },
+      {
+          SpvMagicNumber,
+          0x00000600u,
+          SPV_GENERATOR_CODEPLAY,
+          1u,  // NOTE: Bound
+          0u   // NOTE: Schema; reserved
+      },
+      {
+          SpvMagicNumber,
+          0x00000100u,
+          SPV_GENERATOR_CODEPLAY,
+          1u,  // NOTE: Bound
+          0u   // NOTE: Schema; reserved
+      }
+  };
+  spvtest::Binary linked_binary;
+
+  ASSERT_EQ(SPV_SUCCESS, Link(binaries, &linked_binary));
+  EXPECT_THAT(GetErrorMessage(), std::string());
+
+  ASSERT_EQ(0x00000600u, linked_binary[1]);
+}
+
+}  // anonymous namespace
diff --git a/test/link/entry_points_test.cpp b/test/link/entry_points_test.cpp
new file mode 100644
index 0000000..54561d5
--- /dev/null
+++ b/test/link/entry_points_test.cpp
@@ -0,0 +1,66 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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 "gmock/gmock.h"
+#include "linker_fixture.h"
+
+namespace {
+
+using ::testing::HasSubstr;
+
+class EntryPoints : public spvtest::LinkerTest {};
+
+TEST_F(EntryPoints, SameModelDifferentName) {
+  const std::string body1 = R"(
+OpEntryPoint GLCompute %1 "foo"
+)";
+  const std::string body2 = R"(
+OpEntryPoint GLCompute %1 "bar"
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_SUCCESS, AssembleAndLink({body1, body2}, &linked_binary));
+  EXPECT_THAT(GetErrorMessage(), std::string());
+}
+
+TEST_F(EntryPoints, DifferentModelSameName) {
+  const std::string body1 = R"(
+OpEntryPoint GLCompute %1 "foo"
+)";
+  const std::string body2 = R"(
+OpEntryPoint Vertex %1 "foo"
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_SUCCESS, AssembleAndLink({body1, body2}, &linked_binary));
+  EXPECT_THAT(GetErrorMessage(), std::string());
+}
+
+TEST_F(EntryPoints, SameModelAndName) {
+  const std::string body1 = R"(
+OpEntryPoint GLCompute %1 "foo"
+)";
+  const std::string body2 = R"(
+OpEntryPoint GLCompute %1 "foo"
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_ERROR_INTERNAL,
+            AssembleAndLink({body1, body2}, &linked_binary));
+  EXPECT_THAT(GetErrorMessage(),
+              HasSubstr("The entry point \"foo\", with execution model "
+                        "GLCompute, was already defined."));
+}
+
+}  // anonymous namespace
diff --git a/test/link/global_values_amount_test.cpp b/test/link/global_values_amount_test.cpp
new file mode 100644
index 0000000..068e6fa
--- /dev/null
+++ b/test/link/global_values_amount_test.cpp
@@ -0,0 +1,153 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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 "gmock/gmock.h"
+#include "linker_fixture.h"
+
+namespace {
+
+using ::testing::HasSubstr;
+
+class EntryPoints : public spvtest::LinkerTest {
+ public:
+  EntryPoints() { binaries.reserve(0xFFFF); }
+
+  virtual void SetUp() override {
+    binaries.push_back({SpvMagicNumber,
+                        SpvVersion,
+                        SPV_GENERATOR_CODEPLAY,
+                        10u,  // NOTE: Bound
+                        0u,   // NOTE: Schema; reserved
+
+                        3u << SpvWordCountShift | SpvOpTypeFloat,
+                        1u,   // NOTE: Result ID
+                        32u,  // NOTE: Width
+
+                        4u << SpvWordCountShift | SpvOpTypePointer,
+                        2u,  // NOTE: Result ID
+                        SpvStorageClassInput,
+                        1u,  // NOTE: Type ID
+
+                        2u << SpvWordCountShift | SpvOpTypeVoid,
+                        3u,  // NOTE: Result ID
+
+                        3u << SpvWordCountShift | SpvOpTypeFunction,
+                        4u,  // NOTE: Result ID
+                        3u,  // NOTE: Return type
+
+                        5u << SpvWordCountShift | SpvOpFunction,
+                        3u,  // NOTE: Result type
+                        5u,  // NOTE: Result ID
+                        SpvFunctionControlMaskNone,
+                        4u,  // NOTE: Function type
+
+                        2u << SpvWordCountShift | SpvOpLabel,
+                        6u,  // NOTE: Result ID
+
+                        4u << SpvWordCountShift | SpvOpVariable,
+                        2u,  // NOTE: Type ID
+                        7u,  // NOTE: Result ID
+                        SpvStorageClassFunction,
+
+                        4u << SpvWordCountShift | SpvOpVariable,
+                        2u,  // NOTE: Type ID
+                        8u,  // NOTE: Result ID
+                        SpvStorageClassFunction,
+
+                        4u << SpvWordCountShift | SpvOpVariable,
+                        2u,  // NOTE: Type ID
+                        9u,  // NOTE: Result ID
+                        SpvStorageClassFunction,
+
+                        1u << SpvWordCountShift | SpvOpReturn,
+
+                        1u << SpvWordCountShift | SpvOpFunctionEnd});
+    for (size_t i = 0u; i < 2u; ++i) {
+      spvtest::Binary binary = {
+          SpvMagicNumber,
+          SpvVersion,
+          SPV_GENERATOR_CODEPLAY,
+          103u,  // NOTE: Bound
+          0u,    // NOTE: Schema; reserved
+
+          3u << SpvWordCountShift | SpvOpTypeFloat,
+          1u,   // NOTE: Result ID
+          32u,  // NOTE: Width
+
+          4u << SpvWordCountShift | SpvOpTypePointer,
+          2u,  // NOTE: Result ID
+          SpvStorageClassInput,
+          1u  // NOTE: Type ID
+      };
+
+      for (uint32_t j = 0u; j < 0xFFFFu / 2u; ++j) {
+        binary.push_back(4u << SpvWordCountShift | SpvOpVariable);
+        binary.push_back(2u);      // NOTE: Type ID
+        binary.push_back(j + 3u);  // NOTE: Result ID
+        binary.push_back(SpvStorageClassInput);
+      }
+      binaries.push_back(binary);
+    }
+  }
+  virtual void TearDown() override { binaries.clear(); }
+
+  spvtest::Binaries binaries;
+};
+
+// TODO(dneto): Fix performance issue for debug builds on Windows
+#if !(defined(SPIRV_WINDOWS) && defined(_DEBUG))
+
+TEST_F(EntryPoints, UnderLimit) {
+  spvtest::Binary linked_binary;
+
+  ASSERT_EQ(SPV_SUCCESS, Link(binaries, &linked_binary));
+  EXPECT_THAT(GetErrorMessage(), std::string());
+}
+
+TEST_F(EntryPoints, OverLimit) {
+  binaries.push_back({SpvMagicNumber,
+                      SpvVersion,
+                      SPV_GENERATOR_CODEPLAY,
+                      5u,  // NOTE: Bound
+                      0u,  // NOTE: Schema; reserved
+
+                      3u << SpvWordCountShift | SpvOpTypeFloat,
+                      1u,   // NOTE: Result ID
+                      32u,  // NOTE: Width
+
+                      4u << SpvWordCountShift | SpvOpTypePointer,
+                      2u,  // NOTE: Result ID
+                      SpvStorageClassInput,
+                      1u,  // NOTE: Type ID
+
+                      4u << SpvWordCountShift | SpvOpVariable,
+                      2u,  // NOTE: Type ID
+                      3u,  // NOTE: Result ID
+                      SpvStorageClassInput,
+
+                      4u << SpvWordCountShift | SpvOpVariable,
+                      2u,  // NOTE: Type ID
+                      4u,  // NOTE: Result ID
+                      SpvStorageClassInput});
+
+  spvtest::Binary linked_binary;
+
+  ASSERT_EQ(SPV_ERROR_INTERNAL, Link(binaries, &linked_binary));
+  EXPECT_THAT(GetErrorMessage(),
+              HasSubstr("The limit of global values, 65535, was exceeded; "
+                        "65536 global values were found."));
+}
+#endif // !(defined(SPIRV_WINDOWS) && defined(_DEBUG))
+
+}  // anonymous namespace
diff --git a/test/link/ids_limit_test.cpp b/test/link/ids_limit_test.cpp
new file mode 100644
index 0000000..0d1bf21
--- /dev/null
+++ b/test/link/ids_limit_test.cpp
@@ -0,0 +1,81 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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 "gmock/gmock.h"
+#include "linker_fixture.h"
+
+namespace {
+
+using ::testing::HasSubstr;
+
+using IdsLimit = spvtest::LinkerTest;
+
+TEST_F(IdsLimit, UnderLimit) {
+  spvtest::Binaries binaries = {
+      {
+          SpvMagicNumber,
+          SpvVersion,
+          SPV_GENERATOR_CODEPLAY,
+          0x2FFFFFu, // NOTE: Bound
+          0u,        // NOTE: Schema; reserved
+      },
+      {
+          SpvMagicNumber,
+          SpvVersion,
+          SPV_GENERATOR_CODEPLAY,
+          0x100000u, // NOTE: Bound
+          0u,        // NOTE: Schema; reserved
+      }
+  };
+  spvtest::Binary linked_binary;
+
+  ASSERT_EQ(SPV_SUCCESS, Link(binaries, &linked_binary));
+  EXPECT_THAT(GetErrorMessage(), std::string());
+  ASSERT_EQ(0x3FFFFEu, linked_binary[3]);
+}
+
+TEST_F(IdsLimit, OverLimit) {
+  spvtest::Binaries binaries = {
+      {
+          SpvMagicNumber,
+          SpvVersion,
+          SPV_GENERATOR_CODEPLAY,
+          0x2FFFFFu, // NOTE: Bound
+          0u,        // NOTE: Schema; reserved
+      },
+      {
+          SpvMagicNumber,
+          SpvVersion,
+          SPV_GENERATOR_CODEPLAY,
+          0x100000u, // NOTE: Bound
+          0u,        // NOTE: Schema; reserved
+      },
+      {
+          SpvMagicNumber,
+          SpvVersion,
+          SPV_GENERATOR_CODEPLAY,
+          3u,  // NOTE: Bound
+          0u,  // NOTE: Schema; reserved
+      }
+  };
+
+  spvtest::Binary linked_binary;
+
+  ASSERT_EQ(SPV_ERROR_INVALID_ID, Link(binaries, &linked_binary));
+  EXPECT_THAT(GetErrorMessage(),
+              HasSubstr("The limit of IDs, 4194303, was exceeded: 4194304 is "
+                        "the current ID bound."));
+}
+
+}  // anonymous namespace
diff --git a/test/link/linker_fixture.h b/test/link/linker_fixture.h
new file mode 100644
index 0000000..33a9660
--- /dev/null
+++ b/test/link/linker_fixture.h
@@ -0,0 +1,124 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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_TEST_LINK_LINK_TEST
+#define LIBSPIRV_TEST_LINK_LINK_TEST
+
+#include <iostream>
+
+#include "source/spirv_constant.h"
+#include "unit_spirv.h"
+
+#include "spirv-tools/linker.hpp"
+
+namespace spvtest {
+
+using Binary = std::vector<uint32_t>;
+using Binaries = std::vector<Binary>;
+
+class LinkerTest : public ::testing::Test {
+ public:
+  LinkerTest()
+      : tools_(SPV_ENV_UNIVERSAL_1_2),
+        linker_(SPV_ENV_UNIVERSAL_1_2),
+        assemble_options_(spvtools::SpirvTools::kDefaultAssembleOption),
+        disassemble_options_(spvtools::SpirvTools::kDefaultDisassembleOption) {
+    const auto consumer = [this](spv_message_level_t level, const char*,
+                                 const spv_position_t& position,
+                                 const char* message) {
+      if (!error_message_.empty()) error_message_ += "\n";
+      switch (level) {
+        case SPV_MSG_FATAL:
+        case SPV_MSG_INTERNAL_ERROR:
+        case SPV_MSG_ERROR:
+          error_message_ += "ERROR";
+          break;
+        case SPV_MSG_WARNING:
+          error_message_ += "WARNING";
+          break;
+        case SPV_MSG_INFO:
+          error_message_ += "INFO";
+          break;
+        case SPV_MSG_DEBUG:
+          error_message_ += "DEBUG";
+          break;
+      }
+      error_message_ += ": " + std::to_string(position.index) + ": " + message;
+    };
+    tools_.SetMessageConsumer(consumer);
+    linker_.SetMessageConsumer(consumer);
+  }
+
+  virtual void TearDown() override { error_message_.clear(); }
+
+  // Assembles each of the given strings into SPIR-V binaries before linking
+  // them together. SPV_ERROR_INVALID_TEXT is returned if the assembling failed
+  // for any of the input strings, and SPV_ERROR_INVALID_POINTER if
+  // |linked_binary| is a null pointer.
+  spv_result_t AssembleAndLink(
+      const std::vector<std::string>& bodies, spvtest::Binary* linked_binary,
+      spvtools::LinkerOptions options = spvtools::LinkerOptions()) {
+    if (!linked_binary) return SPV_ERROR_INVALID_POINTER;
+
+    spvtest::Binaries binaries(bodies.size());
+    for (size_t i = 0u; i < bodies.size(); ++i)
+      if (!tools_.Assemble(bodies[i], binaries.data() + i, assemble_options_))
+        return SPV_ERROR_INVALID_TEXT;
+
+    return linker_.Link(binaries, *linked_binary, options);
+  }
+
+  // Links the given SPIR-V binaries together; SPV_ERROR_INVALID_POINTER is
+  // returned if |linked_binary| is a null pointer.
+  spv_result_t Link(
+      const spvtest::Binaries& binaries, spvtest::Binary* linked_binary,
+      spvtools::LinkerOptions options = spvtools::LinkerOptions()) {
+    if (!linked_binary) return SPV_ERROR_INVALID_POINTER;
+    return linker_.Link(binaries, *linked_binary, options);
+  }
+
+  // Disassembles |binary| and outputs the result in |text|. If |text| is a
+  // null pointer, SPV_ERROR_INVALID_POINTER is returned.
+  spv_result_t Disassemble(const spvtest::Binary& binary, std::string* text) {
+    if (!text) return SPV_ERROR_INVALID_POINTER;
+    return tools_.Disassemble(binary, text, disassemble_options_)
+               ? SPV_SUCCESS
+               : SPV_ERROR_INVALID_BINARY;
+  }
+
+  // Sets the options for the assembler.
+  void SetAssembleOptions(uint32_t assemble_options) {
+    assemble_options_ = assemble_options;
+  }
+
+  // Sets the options used by the disassembler.
+  void SetDisassembleOptions(uint32_t disassemble_options) {
+    disassemble_options_ = disassemble_options;
+  }
+
+  // Returns the accumulated error messages for the test.
+  std::string GetErrorMessage() const { return error_message_; }
+
+ private:
+  spvtools::SpirvTools
+      tools_;  // An instance for calling SPIRV-Tools functionalities.
+  spvtools::Linker linker_;
+  uint32_t assemble_options_;
+  uint32_t disassemble_options_;
+  std::string error_message_;
+};
+
+}  // namespace spvtest
+
+#endif  // LIBSPIRV_TEST_LINK_LINK_TEST
diff --git a/test/link/matching_imports_to_exports_test.cpp b/test/link/matching_imports_to_exports_test.cpp
new file mode 100644
index 0000000..894cfea
--- /dev/null
+++ b/test/link/matching_imports_to_exports_test.cpp
@@ -0,0 +1,326 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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 "gmock/gmock.h"
+#include "linker_fixture.h"
+
+namespace {
+
+using ::testing::HasSubstr;
+using MatchingImportsToExports = spvtest::LinkerTest;
+
+TEST_F(MatchingImportsToExports, Default) {
+  const std::string body1 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Import
+%2 = OpTypeFloat 32
+%1 = OpVariable %2 Uniform
+%3 = OpVariable %2 Input
+)";
+  const std::string body2 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+%2 = OpTypeFloat 32
+%3 = OpConstant %2 42
+%1 = OpVariable %2 Uniform %3
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_SUCCESS, AssembleAndLink({body1, body2}, &linked_binary))
+      << GetErrorMessage();
+
+  const std::string expected_res = R"(%1 = OpTypeFloat 32
+%2 = OpVariable %1 Input
+%3 = OpConstant %1 42
+%4 = OpVariable %1 Uniform %3
+)";
+  std::string res_body;
+  SetDisassembleOptions(SPV_BINARY_TO_TEXT_OPTION_NO_HEADER);
+  ASSERT_EQ(SPV_SUCCESS, Disassemble(linked_binary, &res_body))
+      << GetErrorMessage();
+  ASSERT_EQ(expected_res, res_body);
+}
+
+TEST_F(MatchingImportsToExports, NotALibraryExtraExports) {
+  const std::string body = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+%2 = OpTypeFloat 32
+%1 = OpVariable %2 Uniform
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_SUCCESS, AssembleAndLink({body}, &linked_binary))
+      << GetErrorMessage();
+
+  const std::string expected_res = R"(%1 = OpTypeFloat 32
+%2 = OpVariable %1 Uniform
+)";
+  std::string res_body;
+  SetDisassembleOptions(SPV_BINARY_TO_TEXT_OPTION_NO_HEADER);
+  ASSERT_EQ(SPV_SUCCESS, Disassemble(linked_binary, &res_body))
+      << GetErrorMessage();
+  ASSERT_EQ(expected_res, res_body);
+}
+
+TEST_F(MatchingImportsToExports, LibraryExtraExports) {
+  const std::string body = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+%2 = OpTypeFloat 32
+%1 = OpVariable %2 Uniform
+)";
+
+  spvtest::Binary linked_binary;
+  spvtools::LinkerOptions options;
+  options.SetCreateLibrary(true);
+  ASSERT_EQ(SPV_SUCCESS, AssembleAndLink({body}, &linked_binary, options))
+      << GetErrorMessage();
+
+  const std::string expected_res = R"(OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+%2 = OpTypeFloat 32
+%1 = OpVariable %2 Uniform
+)";
+  std::string res_body;
+  SetDisassembleOptions(SPV_BINARY_TO_TEXT_OPTION_NO_HEADER);
+  ASSERT_EQ(SPV_SUCCESS, Disassemble(linked_binary, &res_body))
+      << GetErrorMessage();
+  ASSERT_EQ(expected_res, res_body);
+}
+
+TEST_F(MatchingImportsToExports, UnresolvedImports) {
+  const std::string body1 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Import
+%2 = OpTypeFloat 32
+%1 = OpVariable %2 Uniform
+)";
+  const std::string body2 = R"()";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_ERROR_INVALID_BINARY,
+            AssembleAndLink({body1, body2}, &linked_binary));
+  EXPECT_THAT(GetErrorMessage(),
+              HasSubstr("No export linkage was found for \"foo\"."));
+}
+
+TEST_F(MatchingImportsToExports, TypeMismatch) {
+  const std::string body1 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Import
+%2 = OpTypeFloat 32
+%1 = OpVariable %2 Uniform
+%3 = OpVariable %2 Input
+)";
+  const std::string body2 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+%2 = OpTypeInt 32 0
+%3 = OpConstant %2 42
+%1 = OpVariable %2 Uniform %3
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_ERROR_INVALID_BINARY,
+            AssembleAndLink({body1, body2}, &linked_binary))
+      << GetErrorMessage();
+  EXPECT_THAT(GetErrorMessage(),
+              HasSubstr("Type mismatch between imported variable/function %1 "
+                        "and exported variable/function %4"));
+}
+
+TEST_F(MatchingImportsToExports, MultipleDefinitions) {
+  const std::string body1 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Import
+%2 = OpTypeFloat 32
+%1 = OpVariable %2 Uniform
+%3 = OpVariable %2 Input
+)";
+  const std::string body2 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+%2 = OpTypeFloat 32
+%3 = OpConstant %2 42
+%1 = OpVariable %2 Uniform %3
+)";
+  const std::string body3 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+%2 = OpTypeFloat 32
+%3 = OpConstant %2 -1
+%1 = OpVariable %2 Uniform %3
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_ERROR_INVALID_BINARY,
+            AssembleAndLink({body1, body2, body3}, &linked_binary))
+      << GetErrorMessage();
+  EXPECT_THAT(
+      GetErrorMessage(),
+      HasSubstr("Too many export linkages, 2, were found for \"foo\"."));
+}
+
+TEST_F(MatchingImportsToExports, SameNameDifferentTypes) {
+  const std::string body1 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Import
+%2 = OpTypeFloat 32
+%1 = OpVariable %2 Uniform
+%3 = OpVariable %2 Input
+)";
+  const std::string body2 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+%2 = OpTypeInt 32 0
+%3 = OpConstant %2 42
+%1 = OpVariable %2 Uniform %3
+)";
+  const std::string body3 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+%2 = OpTypeFloat 32
+%3 = OpConstant %2 12
+%1 = OpVariable %2 Uniform %3
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_ERROR_INVALID_BINARY,
+            AssembleAndLink({body1, body2, body3}, &linked_binary))
+      << GetErrorMessage();
+  EXPECT_THAT(
+      GetErrorMessage(),
+      HasSubstr("Too many export linkages, 2, were found for \"foo\"."));
+}
+
+TEST_F(MatchingImportsToExports, DecorationMismatch) {
+  const std::string body1 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Import
+OpDecorate %2 Constant
+%2 = OpTypeFloat 32
+%1 = OpVariable %2 Uniform
+%3 = OpVariable %2 Input
+)";
+  const std::string body2 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+%2 = OpTypeFloat 32
+%3 = OpConstant %2 42
+%1 = OpVariable %2 Uniform %3
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_ERROR_INVALID_BINARY,
+            AssembleAndLink({body1, body2}, &linked_binary))
+      << GetErrorMessage();
+  EXPECT_THAT(GetErrorMessage(),
+              HasSubstr("Type mismatch between imported variable/function %1 "
+                        "and exported variable/function %4."));
+}
+
+TEST_F(MatchingImportsToExports, FuncParamAttr) {
+  const std::string body1 = R"(
+OpCapability Kernel
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Import
+OpDecorate %2 FuncParamAttr Zext
+%3 = OpTypeVoid
+%4 = OpTypeInt 32 0
+%5 = OpTypeFunction %3 %4
+%1 = OpFunction %3 None %5
+%2 = OpFunctionParameter %4
+OpFunctionEnd
+)";
+  const std::string body2 = R"(
+OpCapability Kernel
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+OpDecorate %2 FuncParamAttr Sext
+%3 = OpTypeVoid
+%4 = OpTypeInt 32 0
+%5 = OpTypeFunction %3 %4
+%1 = OpFunction %3 None %5
+%2 = OpFunctionParameter %4
+%6 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_SUCCESS, AssembleAndLink({body1, body2}, &linked_binary))
+      << GetErrorMessage();
+
+  const std::string expected_res = R"(OpCapability Kernel
+OpDecorate %1 FuncParamAttr Sext
+%2 = OpTypeVoid
+%3 = OpTypeInt 32 0
+%4 = OpTypeFunction %2 %3
+%5 = OpFunction %2 None %4
+%1 = OpFunctionParameter %3
+%6 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+  std::string res_body;
+  SetDisassembleOptions(SPV_BINARY_TO_TEXT_OPTION_NO_HEADER);
+  ASSERT_EQ(SPV_SUCCESS, Disassemble(linked_binary, &res_body))
+      << GetErrorMessage();
+  ASSERT_EQ(expected_res, res_body);
+}
+
+TEST_F(MatchingImportsToExports, FunctionCtrl) {
+  const std::string body1 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Import
+%2 = OpTypeVoid
+%3 = OpTypeFunction %2
+%4 = OpTypeFloat 32
+%5 = OpVariable %4 Uniform
+%1 = OpFunction %2 None %3
+OpFunctionEnd
+)";
+  const std::string body2 = R"(
+OpCapability Linkage
+OpDecorate %1 LinkageAttributes "foo" Export
+%2 = OpTypeVoid
+%3 = OpTypeFunction %2
+%1 = OpFunction %2 Inline %3
+%4 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_SUCCESS, AssembleAndLink({body1, body2}, &linked_binary))
+      << GetErrorMessage();
+
+  const std::string expected_res = R"(%1 = OpTypeVoid
+%2 = OpTypeFunction %1
+%3 = OpTypeFloat 32
+%4 = OpVariable %3 Uniform
+%5 = OpFunction %1 Inline %2
+%6 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+  std::string res_body;
+  SetDisassembleOptions(SPV_BINARY_TO_TEXT_OPTION_NO_HEADER);
+  ASSERT_EQ(SPV_SUCCESS, Disassemble(linked_binary, &res_body))
+      << GetErrorMessage();
+  ASSERT_EQ(expected_res, res_body);
+}
+
+}  // anonymous namespace
diff --git a/test/link/memory_model_test.cpp b/test/link/memory_model_test.cpp
new file mode 100644
index 0000000..76eae9a
--- /dev/null
+++ b/test/link/memory_model_test.cpp
@@ -0,0 +1,71 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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 "gmock/gmock.h"
+#include "linker_fixture.h"
+
+namespace {
+
+using ::testing::HasSubstr;
+
+using MemoryModel = spvtest::LinkerTest;
+
+TEST_F(MemoryModel, Default) {
+  const std::string body1 = R"(
+OpMemoryModel Logical Simple
+)";
+  const std::string body2 = R"(
+OpMemoryModel Logical Simple
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_SUCCESS, AssembleAndLink({body1, body2}, &linked_binary));
+  EXPECT_THAT(GetErrorMessage(), std::string());
+
+  ASSERT_EQ(SpvAddressingModelLogical, linked_binary[6]);
+  ASSERT_EQ(SpvMemoryModelSimple, linked_binary[7]);
+}
+
+TEST_F(MemoryModel, AddressingMismatch) {
+  const std::string body1 = R"(
+OpMemoryModel Logical Simple
+)";
+  const std::string body2 = R"(
+OpMemoryModel Physical32 Simple
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_ERROR_INTERNAL,
+            AssembleAndLink({body1, body2}, &linked_binary));
+  EXPECT_THAT(
+      GetErrorMessage(),
+      HasSubstr("Conflicting addressing models: Logical vs Physical32."));
+}
+
+TEST_F(MemoryModel, MemoryMismatch) {
+  const std::string body1 = R"(
+OpMemoryModel Logical Simple
+)";
+  const std::string body2 = R"(
+OpMemoryModel Logical GLSL450
+)";
+
+  spvtest::Binary linked_binary;
+  ASSERT_EQ(SPV_ERROR_INTERNAL,
+            AssembleAndLink({body1, body2}, &linked_binary));
+  EXPECT_THAT(GetErrorMessage(),
+              HasSubstr("Conflicting memory models: Simple vs GLSL450."));
+}
+
+}  // anonymous namespace
diff --git a/test/opt/pass_manager_test.cpp b/test/opt/pass_manager_test.cpp
index 704aa53..d06ad3d 100644
--- a/test/opt/pass_manager_test.cpp
+++ b/test/opt/pass_manager_test.cpp
@@ -70,17 +70,17 @@
   EXPECT_STREQ("null-with-args", manager.GetPass(6)->name());
 }
 
-// A pass that appends an OpNop instruction to the debug section.
+// A pass that appends an OpNop instruction to the debug1 section.
 class AppendOpNopPass : public opt::Pass {
  public:
   const char* name() const override { return "AppendOpNop"; }
   Status Process(ir::Module* module) override {
-    module->AddDebugInst(MakeUnique<ir::Instruction>());
+    module->AddDebug1Inst(MakeUnique<ir::Instruction>());
     return Status::SuccessWithChange;
   }
 };
 
-// A pass that appends specified number of OpNop instructions to the debug
+// A pass that appends specified number of OpNop instructions to the debug1
 // section.
 class AppendMultipleOpNopPass : public opt::Pass {
  public:
@@ -89,7 +89,7 @@
   const char* name() const override { return "AppendOpNop"; }
   Status Process(ir::Module* module) override {
     for (uint32_t i = 0; i < num_nop_; i++) {
-      module->AddDebugInst(MakeUnique<ir::Instruction>());
+      module->AddDebug1Inst(MakeUnique<ir::Instruction>());
     }
     return Status::SuccessWithChange;
   }
@@ -98,13 +98,13 @@
   uint32_t num_nop_;
 };
 
-// A pass that duplicates the last instruction in the debug section.
+// A pass that duplicates the last instruction in the debug1 section.
 class DuplicateInstPass : public opt::Pass {
  public:
   const char* name() const override { return "DuplicateInst"; }
   Status Process(ir::Module* module) override {
-    auto inst = MakeUnique<ir::Instruction>(*(--module->debug_end()));
-    module->AddDebugInst(std::move(inst));
+    auto inst = MakeUnique<ir::Instruction>(*(--module->debug1_end()));
+    module->AddDebug1Inst(std::move(inst));
     return Status::SuccessWithChange;
   }
 };
diff --git a/tools/CMakeLists.txt b/tools/CMakeLists.txt
index 052fb77..fa4ade7 100644
--- a/tools/CMakeLists.txt
+++ b/tools/CMakeLists.txt
@@ -42,6 +42,7 @@
   add_spvtools_tool(TARGET spirv-dis SRCS dis/dis.cpp LIBS ${SPIRV_TOOLS})
   add_spvtools_tool(TARGET spirv-val SRCS val/val.cpp LIBS ${SPIRV_TOOLS})
   add_spvtools_tool(TARGET spirv-opt SRCS opt/opt.cpp LIBS SPIRV-Tools-opt ${SPIRV_TOOLS})
+  add_spvtools_tool(TARGET spirv-link SRCS link/linker.cpp LIBS SPIRV-Tools-link ${SPIRV_TOOLS})
   add_spvtools_tool(TARGET spirv-stats
 	            SRCS stats/stats.cpp
 		         stats/stats_analyzer.cpp
@@ -56,7 +57,8 @@
   target_include_directories(spirv-stats PRIVATE ${spirv-tools_SOURCE_DIR}
                                                  ${SPIRV_HEADER_INCLUDE_DIR})
 
-  set(SPIRV_INSTALL_TARGETS spirv-as spirv-dis spirv-val spirv-opt spirv-stats spirv-cfg)
+  set(SPIRV_INSTALL_TARGETS spirv-as spirv-dis spirv-val spirv-opt spirv-stats
+                            spirv-cfg spirv-link)
 
   if(SPIRV_BUILD_COMPRESSION)
     add_spvtools_tool(TARGET spirv-markv SRCS comp/markv.cpp
diff --git a/tools/link/linker.cpp b/tools/link/linker.cpp
new file mode 100644
index 0000000..6549be5
--- /dev/null
+++ b/tools/link/linker.cpp
@@ -0,0 +1,150 @@
+// Copyright (c) 2017 Pierre Moreau
+//
+// 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 <cstring>
+#include <iostream>
+#include <vector>
+
+#include "source/spirv_target_env.h"
+#include "spirv-tools/libspirv.hpp"
+#include "spirv-tools/linker.hpp"
+#include "tools/io.h"
+
+void print_usage(char* argv0) {
+  printf(
+      R"(%s - Link SPIR-V binary files together.
+
+USAGE: %s [options] <filename> [<filename> ...]
+
+The SPIR-V binaries are read from the different <filename>.
+
+NOTE: The linker is a work in progress.
+
+Options:
+  -h, --help       Print this help.
+  -o               Name of the resulting linked SPIR-V binary.
+  --create-library Link the binaries into a library, keeping all exported symbols.
+  --version        Display linker version information
+  --target-env     {vulkan1.0|spv1.0|spv1.1|spv1.2|opencl2.1|opencl2.2}
+                   Use Vulkan1.0/SPIR-V1.0/SPIR-V1.1/SPIR-V1.2/OpenCL-2.1/OpenCL2.2 validation rules.
+)",
+      argv0, argv0);
+}
+
+int main(int argc, char** argv) {
+  std::vector<const char*> inFiles;
+  const char* outFile = nullptr;
+  spv_target_env target_env = SPV_ENV_UNIVERSAL_1_0;
+  spvtools::LinkerOptions options;
+  bool continue_processing = true;
+  int return_code = 0;
+
+  for (int argi = 1; continue_processing && argi < argc; ++argi) {
+    const char* cur_arg = argv[argi];
+    if ('-' == cur_arg[0]) {
+      if (0 == strcmp(cur_arg, "-o")) {
+        if (argi + 1 < argc) {
+          if (!outFile) {
+            outFile = argv[++argi];
+          } else {
+            fprintf(stderr, "error: More than one output file specified\n");
+            continue_processing = false;
+            return_code = 1;
+          }
+        } else {
+          fprintf(stderr, "error: Missing argument to %s\n", cur_arg);
+          continue_processing = false;
+          return_code = 1;
+        }
+      } else if (0 == strcmp(cur_arg, "--create-library")) {
+        options.SetCreateLibrary(true);
+      } else if (0 == strcmp(cur_arg, "--version")) {
+        printf("%s\n", spvSoftwareVersionDetailsString());
+        // TODO(dneto): Add OpenCL 2.2 at least.
+        printf("Targets:\n  %s\n  %s\n  %s\n",
+               spvTargetEnvDescription(SPV_ENV_UNIVERSAL_1_1),
+               spvTargetEnvDescription(SPV_ENV_VULKAN_1_0),
+               spvTargetEnvDescription(SPV_ENV_UNIVERSAL_1_2));
+        continue_processing = false;
+        return_code = 0;
+      } else if (0 == strcmp(cur_arg, "--help") || 0 == strcmp(cur_arg, "-h")) {
+        print_usage(argv[0]);
+        continue_processing = false;
+        return_code = 0;
+      } else if (0 == strcmp(cur_arg, "--target-env")) {
+        if (argi + 1 < argc) {
+          const auto env_str = argv[++argi];
+          if (!spvParseTargetEnv(env_str, &target_env)) {
+            fprintf(stderr, "error: Unrecognized target env: %s\n", env_str);
+            continue_processing = false;
+            return_code = 1;
+          }
+        } else {
+          fprintf(stderr, "error: Missing argument to --target-env\n");
+          continue_processing = false;
+          return_code = 1;
+        }
+      }
+    } else {
+      inFiles.push_back(cur_arg);
+    }
+  }
+
+  // Exit if command line parsing was not successful.
+  if (!continue_processing) {
+    return return_code;
+  }
+
+  if (inFiles.empty()) {
+    fprintf(stderr, "error: No input file specified\n");
+    return 1;
+  }
+
+  std::vector<std::vector<uint32_t>> contents(inFiles.size());
+  for (size_t i = 0u; i < inFiles.size(); ++i) {
+    if (!ReadFile<uint32_t>(inFiles[i], "rb", &contents[i])) return 1;
+  }
+
+  spvtools::Linker linker(target_env);
+  linker.SetMessageConsumer([](spv_message_level_t level, const char*,
+                               const spv_position_t& position,
+                               const char* message) {
+    switch (level) {
+      case SPV_MSG_FATAL:
+      case SPV_MSG_INTERNAL_ERROR:
+      case SPV_MSG_ERROR:
+        std::cerr << "error: " << position.index << ": " << message
+                  << std::endl;
+        break;
+      case SPV_MSG_WARNING:
+        std::cout << "warning: " << position.index << ": " << message
+                  << std::endl;
+        break;
+      case SPV_MSG_INFO:
+        std::cout << "info: " << position.index << ": " << message << std::endl;
+        break;
+      default:
+        break;
+    }
+  });
+
+  std::vector<uint32_t> linkingResult;
+  bool succeed = linker.Link(contents, linkingResult, options);
+
+  if (!WriteFile<uint32_t>(outFile, "wb", linkingResult.data(),
+                           linkingResult.size()))
+    return 1;
+
+  return !succeed;
+}
diff --git a/utils/check_copyright.py b/utils/check_copyright.py
index 08fb082..cc24863 100755
--- a/utils/check_copyright.py
+++ b/utils/check_copyright.py
@@ -29,7 +29,8 @@
 # List of designated copyright owners.
 AUTHORS = ['The Khronos Group Inc.',
            'LunarG Inc.',
-           'Google Inc.']
+           'Google Inc.',
+           'Pierre Moreau']
 CURRENT_YEAR='2017'
 
 YEARS = '(2014-2016|2015-2016|2016|2016-2017|2017)'