diff --git a/Android.mk b/Android.mk
index f6ac829..4199afc 100644
--- a/Android.mk
+++ b/Android.mk
@@ -119,6 +119,7 @@
 		source/opt/private_to_local_pass.cpp \
 		source/opt/propagator.cpp \
 		source/opt/redundancy_elimination.cpp \
+		source/opt/register_pressure.cpp \
 		source/opt/remove_duplicates_pass.cpp \
 		source/opt/replace_invalid_opc.cpp \
 		source/opt/scalar_analysis.cpp \
diff --git a/source/opt/CMakeLists.txt b/source/opt/CMakeLists.txt
index 114c3a5..408ed31 100644
--- a/source/opt/CMakeLists.txt
+++ b/source/opt/CMakeLists.txt
@@ -76,6 +76,7 @@
   propagator.h
   redundancy_elimination.h
   reflect.h
+  register_pressure.h
   remove_duplicates_pass.h
   replace_invalid_opc.h
   scalar_analysis.h
@@ -154,6 +155,7 @@
   private_to_local_pass.cpp
   propagator.cpp
   redundancy_elimination.cpp
+  register_pressure.cpp
   remove_duplicates_pass.cpp
   replace_invalid_opc.cpp
   scalar_analysis.cpp
diff --git a/source/opt/basic_block.h b/source/opt/basic_block.h
index 0df1f76..d34b047 100644
--- a/source/opt/basic_block.h
+++ b/source/opt/basic_block.h
@@ -19,6 +19,7 @@
 #define LIBSPIRV_OPT_BASIC_BLOCK_H_
 
 #include <functional>
+#include <iterator>
 #include <memory>
 #include <ostream>
 #include <utility>
@@ -39,6 +40,9 @@
  public:
   using iterator = InstructionList::iterator;
   using const_iterator = InstructionList::const_iterator;
+  using reverse_iterator = std::reverse_iterator<InstructionList::iterator>;
+  using const_reverse_iterator =
+      std::reverse_iterator<InstructionList::const_iterator>;
 
   // Creates a basic block with the given starting |label|.
   inline explicit BasicBlock(std::unique_ptr<Instruction> label);
@@ -87,6 +91,21 @@
   const_iterator cbegin() const { return insts_.cbegin(); }
   const_iterator cend() const { return insts_.cend(); }
 
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
+  reverse_iterator rend() { return reverse_iterator(begin()); }
+  const_reverse_iterator rbegin() const {
+    return const_reverse_iterator(cend());
+  }
+  const_reverse_iterator rend() const {
+    return const_reverse_iterator(cbegin());
+  }
+  const_reverse_iterator crbegin() const {
+    return const_reverse_iterator(cend());
+  }
+  const_reverse_iterator crend() const {
+    return const_reverse_iterator(cbegin());
+  }
+
   // Returns an iterator pointing to the last instruction.  This may only
   // be used if this block has an instruction other than the OpLabel
   // that defines it.
diff --git a/source/opt/cfg.cpp b/source/opt/cfg.cpp
index 6767570..d13bdab 100644
--- a/source/opt/cfg.cpp
+++ b/source/opt/cfg.cpp
@@ -90,6 +90,19 @@
       root, get_structured_successors, ignore_block, post_order, ignore_edge);
 }
 
+void CFG::ForEachBlockInPostOrder(BasicBlock* bb,
+                                  const std::function<void(BasicBlock*)>& f) {
+  std::vector<BasicBlock*> po;
+  std::unordered_set<BasicBlock*> seen;
+  ComputePostOrderTraversal(bb, &po, &seen);
+
+  for (BasicBlock* current_bb : po) {
+    if (!IsPseudoExitBlock(current_bb) && !IsPseudoEntryBlock(current_bb)) {
+      f(current_bb);
+    }
+  }
+}
+
 void CFG::ForEachBlockInReversePostOrder(
     BasicBlock* bb, const std::function<void(BasicBlock*)>& f) {
   std::vector<BasicBlock*> po;
diff --git a/source/opt/cfg.h b/source/opt/cfg.h
index ffff7e1..98d06a7 100644
--- a/source/opt/cfg.h
+++ b/source/opt/cfg.h
@@ -71,6 +71,12 @@
   void ComputeStructuredOrder(ir::Function* func, ir::BasicBlock* root,
                               std::list<ir::BasicBlock*>* order);
 
+  // Applies |f| to the basic block in post order starting with |bb|.
+  // Note that basic blocks that cannot be reached from |bb| node will not be
+  // processed.
+  void ForEachBlockInPostOrder(BasicBlock* bb,
+                               const std::function<void(BasicBlock*)>& f);
+
   // Applies |f| to the basic block in reverse post order starting with |bb|.
   // Note that basic blocks that cannot be reached from |bb| node will not be
   // processed.
diff --git a/source/opt/ir_context.cpp b/source/opt/ir_context.cpp
index 856e403..ea1c0b9 100644
--- a/source/opt/ir_context.cpp
+++ b/source/opt/ir_context.cpp
@@ -48,6 +48,9 @@
   if (set & kAnalysisScalarEvolution) {
     BuildScalarEvolutionAnalysis();
   }
+  if (set & kAnalysisRegisterPressure) {
+    BuildRegPressureAnalysis();
+  }
 }
 
 void IRContext::InvalidateAnalysesExceptFor(
diff --git a/source/opt/ir_context.h b/source/opt/ir_context.h
index bb44b49..ec34b97 100644
--- a/source/opt/ir_context.h
+++ b/source/opt/ir_context.h
@@ -24,6 +24,7 @@
 #include "feature_manager.h"
 #include "loop_descriptor.h"
 #include "module.h"
+#include "register_pressure.h"
 #include "scalar_analysis.h"
 #include "type_manager.h"
 
@@ -60,7 +61,8 @@
     kAnalysisLoopAnalysis = 1 << 6,
     kAnalysisNameMap = 1 << 7,
     kAnalysisScalarEvolution = 1 << 8,
-    kAnalysisEnd = 1 << 9
+    kAnalysisRegisterPressure = 1 << 9,
+    kAnalysisEnd = 1 << 10
   };
 
   friend inline Analysis operator|(Analysis lhs, Analysis rhs);
@@ -206,6 +208,15 @@
     return def_use_mgr_.get();
   }
 
+  // Returns a pointer to a liveness analysis.  If the liveness analysis is
+  // invalid, it is rebuilt first.
+  opt::LivenessAnalysis* GetLivenessAnalysis() {
+    if (!AreAnalysesValid(kAnalysisRegisterPressure)) {
+      BuildRegPressureAnalysis();
+    }
+    return reg_pressure_.get();
+  }
+
   // Returns the basic block for instruction |instr|. Re-builds the instruction
   // block map, if needed.
   ir::BasicBlock* get_instr_block(ir::Instruction* instr) {
@@ -394,10 +405,20 @@
   opt::DominatorAnalysis* GetDominatorAnalysis(const ir::Function* f,
                                                const ir::CFG&);
 
+  // Gets the dominator analysis for function |f|.
+  opt::DominatorAnalysis* GetDominatorAnalysis(const ir::Function* f) {
+    return GetDominatorAnalysis(f, *cfg());
+  }
+
   // Gets the postdominator analysis for function |f|.
   opt::PostDominatorAnalysis* GetPostDominatorAnalysis(const ir::Function* f,
                                                        const ir::CFG&);
 
+  // Gets the postdominator analysis for function |f|.
+  opt::PostDominatorAnalysis* GetPostDominatorAnalysis(const ir::Function* f) {
+    return GetPostDominatorAnalysis(f, *cfg());
+  }
+
   // Remove the dominator tree of |f| from the cache.
   inline void RemoveDominatorAnalysis(const ir::Function* f) {
     dominator_trees_.erase(f);
@@ -460,6 +481,12 @@
     valid_analyses_ = valid_analyses_ | kAnalysisScalarEvolution;
   }
 
+  // Builds the liveness analysis from scratch, even if it was already valid.
+  void BuildRegPressureAnalysis() {
+    reg_pressure_.reset(new opt::LivenessAnalysis(this));
+    valid_analyses_ = valid_analyses_ | kAnalysisRegisterPressure;
+  }
+
   // Removes all computed dominator and post-dominator trees. This will force
   // the context to rebuild the trees on demand.
   void ResetDominatorAnalysis() {
@@ -563,6 +590,9 @@
 
   // The cache scalar evolution analysis node.
   std::unique_ptr<opt::ScalarEvolutionAnalysis> scalar_evolution_analysis_;
+
+  // The liveness analysis |module_|.
+  std::unique_ptr<opt::LivenessAnalysis> reg_pressure_;
 };
 
 inline ir::IRContext::Analysis operator|(ir::IRContext::Analysis lhs,
diff --git a/source/opt/iterator.h b/source/opt/iterator.h
index d43dfbe..13ff979 100644
--- a/source/opt/iterator.h
+++ b/source/opt/iterator.h
@@ -166,6 +166,105 @@
           IteratorType(&container, container.cend())};
 }
 
+// Wrapping iterator class that only consider elements that satisfy the given
+// predicate |Predicate|. When moving to the next element of the iterator, the
+// FilterIterator will iterate over the range until it finds an element that
+// satisfies |Predicate| or reaches the end of the iterator.
+//
+// Currently this iterator is always an input iterator.
+template <typename SubIterator, typename Predicate>
+class FilterIterator
+    : public std::iterator<
+          std::input_iterator_tag, typename SubIterator::value_type,
+          typename SubIterator::difference_type, typename SubIterator::pointer,
+          typename SubIterator::reference> {
+ public:
+  // Iterator interface.
+  using iterator_category = typename SubIterator::iterator_category;
+  using value_type = typename SubIterator::value_type;
+  using pointer = typename SubIterator::pointer;
+  using reference = typename SubIterator::reference;
+  using difference_type = typename SubIterator::difference_type;
+
+  using Range = IteratorRange<FilterIterator>;
+
+  FilterIterator(const IteratorRange<SubIterator>& iteration_range,
+                 Predicate predicate)
+      : cur_(iteration_range.begin()),
+        end_(iteration_range.end()),
+        predicate_(predicate) {
+    if (!IsPredicateSatisfied()) {
+      MoveToNextPosition();
+    }
+  }
+
+  FilterIterator(const SubIterator& end, Predicate predicate)
+      : FilterIterator({end, end}, predicate) {}
+
+  inline FilterIterator& operator++() {
+    MoveToNextPosition();
+    return *this;
+  }
+  inline FilterIterator operator++(int) {
+    FilterIterator old = *this;
+    MoveToNextPosition();
+    return old;
+  }
+
+  reference operator*() const { return *cur_; }
+  pointer operator->() { return &*cur_; }
+
+  inline bool operator==(const FilterIterator& rhs) const {
+    return cur_ == rhs.cur_ && end_ == rhs.end_;
+  }
+  inline bool operator!=(const FilterIterator& rhs) const {
+    return !(*this == rhs);
+  }
+
+  // Returns the underlying iterator.
+  SubIterator Get() const { return cur_; }
+
+  // Returns the sentinel iterator.
+  FilterIterator GetEnd() const { return FilterIterator(end_, predicate_); }
+
+ private:
+  // Returns true if the predicate is satisfied or the current iterator reached
+  // the end.
+  bool IsPredicateSatisfied() { return cur_ == end_ || predicate_(*cur_); }
+
+  void MoveToNextPosition() {
+    if (cur_ == end_) return;
+
+    do {
+      ++cur_;
+    } while (!IsPredicateSatisfied());
+  }
+
+  SubIterator cur_;
+  SubIterator end_;
+  Predicate predicate_;
+};
+
+template <typename SubIterator, typename Predicate>
+FilterIterator<SubIterator, Predicate> MakeFilterIterator(
+    const IteratorRange<SubIterator>& sub_iterator_range, Predicate predicate) {
+  return FilterIterator<SubIterator, Predicate>(sub_iterator_range, predicate);
+}
+
+template <typename SubIterator, typename Predicate>
+FilterIterator<SubIterator, Predicate> MakeFilterIterator(
+    const SubIterator& begin, const SubIterator& end, Predicate predicate) {
+  return MakeFilterIterator(make_range(begin, end), predicate);
+}
+
+template <typename SubIterator, typename Predicate>
+typename FilterIterator<SubIterator, Predicate>::Range MakeFilterIteratorRange(
+    const SubIterator& begin, const SubIterator& end, Predicate predicate) {
+  return typename FilterIterator<SubIterator, Predicate>::Range(
+      MakeFilterIterator(begin, end, predicate),
+      MakeFilterIterator(end, end, predicate));
+}
+
 template <typename VT, bool IC>
 inline UptrVectorIterator<VT, IC>& UptrVectorIterator<VT, IC>::operator++() {
   ++iterator_;
diff --git a/source/opt/loop_descriptor.h b/source/opt/loop_descriptor.h
index 7ccab1b..210ec89 100644
--- a/source/opt/loop_descriptor.h
+++ b/source/opt/loop_descriptor.h
@@ -59,8 +59,6 @@
   Loop(IRContext* context, opt::DominatorAnalysis* analysis, BasicBlock* header,
        BasicBlock* continue_target, BasicBlock* merge_target);
 
-  ~Loop() {}
-
   // Iterators over the immediate sub-loops.
   inline iterator begin() { return nested_loops_.begin(); }
   inline iterator end() { return nested_loops_.end(); }
@@ -405,6 +403,9 @@
   using iterator = opt::PostOrderTreeDFIterator<Loop>;
   using const_iterator = opt::PostOrderTreeDFIterator<const Loop>;
 
+  using pre_iterator = opt::TreeDFIterator<Loop>;
+  using const_pre_iterator = opt::TreeDFIterator<const Loop>;
+
   // Creates a loop object for all loops found in |f|.
   explicit LoopDescriptor(const Function* f);
 
@@ -458,6 +459,17 @@
     return const_iterator::end(&dummy_top_loop_);
   }
 
+  // Iterators for pre-order depth first traversal of the loops.
+  // Inner most loops will be visited first.
+  inline pre_iterator pre_begin() { return ++pre_iterator(&dummy_top_loop_); }
+  inline pre_iterator pre_end() { return pre_iterator(); }
+  inline const_pre_iterator pre_begin() const { return pre_cbegin(); }
+  inline const_pre_iterator pre_end() const { return pre_cend(); }
+  inline const_pre_iterator pre_cbegin() const {
+    return ++const_pre_iterator(&dummy_top_loop_);
+  }
+  inline const_pre_iterator pre_cend() const { return const_pre_iterator(); }
+
   // Returns the inner most loop that contains the basic block |bb|.
   inline void SetBasicBlockToLoop(uint32_t bb_id, Loop* loop) {
     basic_block_to_loop_[bb_id] = loop;
diff --git a/source/opt/register_pressure.cpp b/source/opt/register_pressure.cpp
new file mode 100644
index 0000000..d414e70
--- /dev/null
+++ b/source/opt/register_pressure.cpp
@@ -0,0 +1,578 @@
+// Copyright (c) 2018 Google LLC.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "register_pressure.h"
+
+#include <iterator>
+
+#include "cfg.h"
+#include "def_use_manager.h"
+#include "dominator_tree.h"
+#include "function.h"
+#include "ir_context.h"
+#include "iterator.h"
+
+namespace spvtools {
+namespace opt {
+
+namespace {
+// Predicate for the FilterIterator to only consider instructions that are not
+// phi instructions defined in the basic block |bb|.
+class ExcludePhiDefinedInBlock {
+ public:
+  ExcludePhiDefinedInBlock(ir::IRContext* context, const ir::BasicBlock* bb)
+      : context_(context), bb_(bb) {}
+
+  bool operator()(ir::Instruction* insn) const {
+    return !(insn->opcode() == SpvOpPhi &&
+             context_->get_instr_block(insn) == bb_);
+  }
+
+ private:
+  ir::IRContext* context_;
+  const ir::BasicBlock* bb_;
+};
+
+// Returns true if |insn| generates a SSA register that is likely to require a
+// physical register.
+bool CreatesRegisterUsage(ir::Instruction* insn) {
+  if (!insn->HasResultId()) return false;
+  if (insn->opcode() == SpvOpUndef) return false;
+  if (ir::IsConstantInst(insn->opcode())) return false;
+  if (insn->opcode() == SpvOpLabel) return false;
+  return true;
+}
+
+// Compute the register liveness for each basic block of a function. This also
+// fill-up some information about the pick register usage and a break down of
+// register usage. This implements: "A non-iterative data-flow algorithm for
+// computing liveness sets in strict ssa programs" from Boissinot et al.
+class ComputeRegisterLiveness {
+ public:
+  ComputeRegisterLiveness(RegisterLiveness* reg_pressure, ir::Function* f)
+      : reg_pressure_(reg_pressure),
+        context_(reg_pressure->GetContext()),
+        function_(f),
+        cfg_(*reg_pressure->GetContext()->cfg()),
+        def_use_manager_(*reg_pressure->GetContext()->get_def_use_mgr()),
+        dom_tree_(
+            reg_pressure->GetContext()->GetDominatorAnalysis(f)->GetDomTree()),
+        loop_desc_(*reg_pressure->GetContext()->GetLoopDescriptor(f)) {}
+
+  // Computes the register liveness for |function_| and then estimate the
+  // register usage. The liveness algorithm works in 2 steps:
+  //   - First, compute the liveness for each basic blocks, but will ignore any
+  //   back-edge;
+  //   - Second, walk loop forest to propagate registers crossing back-edges
+  //   (add iterative values into the liveness set).
+  void Compute() {
+    cfg_.ForEachBlockInPostOrder(
+        &*function_->begin(),
+        [this](ir::BasicBlock* bb) { ComputePartialLiveness(bb); });
+    DoLoopLivenessUnification();
+    EvaluateRegisterRequirements();
+  }
+
+ private:
+  // Registers all SSA register used by successors of |bb| in their phi
+  // instructions.
+  void ComputePhiUses(const ir::BasicBlock& bb,
+                      RegisterLiveness::RegionRegisterLiveness::LiveSet* live) {
+    uint32_t bb_id = bb.id();
+    bb.ForEachSuccessorLabel([live, bb_id, this](uint32_t sid) {
+      ir::BasicBlock* succ_bb = cfg_.block(sid);
+      succ_bb->ForEachPhiInst([live, bb_id, this](const ir::Instruction* phi) {
+        for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) {
+          if (phi->GetSingleWordInOperand(i + 1) == bb_id) {
+            ir::Instruction* insn_op =
+                def_use_manager_.GetDef(phi->GetSingleWordInOperand(i));
+            if (CreatesRegisterUsage(insn_op)) {
+              live->insert(insn_op);
+              break;
+            }
+          }
+        }
+      });
+    });
+  }
+
+  // Computes register liveness for each basic blocks but ignores all
+  // back-edges.
+  void ComputePartialLiveness(ir::BasicBlock* bb) {
+    assert(reg_pressure_->Get(bb) == nullptr &&
+           "Basic block already processed");
+
+    RegisterLiveness::RegionRegisterLiveness* live_inout =
+        reg_pressure_->GetOrInsert(bb->id());
+    ComputePhiUses(*bb, &live_inout->live_out_);
+
+    const ir::BasicBlock* cbb = bb;
+    cbb->ForEachSuccessorLabel([&live_inout, bb, this](uint32_t sid) {
+      // Skip back edges.
+      if (dom_tree_.Dominates(sid, bb->id())) {
+        return;
+      }
+
+      ir::BasicBlock* succ_bb = cfg_.block(sid);
+      RegisterLiveness::RegionRegisterLiveness* succ_live_inout =
+          reg_pressure_->Get(succ_bb);
+      assert(succ_live_inout &&
+             "Successor liveness analysis was not performed");
+
+      ExcludePhiDefinedInBlock predicate(context_, succ_bb);
+      auto filter = ir::MakeFilterIteratorRange(
+          succ_live_inout->live_in_.begin(), succ_live_inout->live_in_.end(),
+          predicate);
+      live_inout->live_out_.insert(filter.begin(), filter.end());
+    });
+
+    live_inout->live_in_ = live_inout->live_out_;
+    for (ir::Instruction& insn : ir::make_range(bb->rbegin(), bb->rend())) {
+      if (insn.opcode() == SpvOpPhi) {
+        live_inout->live_in_.insert(&insn);
+        break;
+      }
+      live_inout->live_in_.erase(&insn);
+      insn.ForEachInId([live_inout, this](uint32_t* id) {
+        ir::Instruction* insn_op = def_use_manager_.GetDef(*id);
+        if (CreatesRegisterUsage(insn_op)) {
+          live_inout->live_in_.insert(insn_op);
+        }
+      });
+    }
+  }
+
+  // Propagates the register liveness information of each loop iterators.
+  void DoLoopLivenessUnification() {
+    for (const ir::Loop* loop : *loop_desc_.GetDummyRootLoop()) {
+      DoLoopLivenessUnification(*loop);
+    }
+  }
+
+  // Propagates the register liveness information of loop iterators trough-out
+  // the loop body.
+  void DoLoopLivenessUnification(const ir::Loop& loop) {
+    auto blocks_in_loop = ir::MakeFilterIteratorRange(
+        loop.GetBlocks().begin(), loop.GetBlocks().end(),
+        [&loop, this](uint32_t bb_id) {
+          return bb_id != loop.GetHeaderBlock()->id() &&
+                 loop_desc_[bb_id] == &loop;
+        });
+
+    RegisterLiveness::RegionRegisterLiveness* header_live_inout =
+        reg_pressure_->Get(loop.GetHeaderBlock());
+    assert(header_live_inout &&
+           "Liveness analysis was not performed for the current block");
+
+    ExcludePhiDefinedInBlock predicate(context_, loop.GetHeaderBlock());
+    auto live_loop = ir::MakeFilterIteratorRange(
+        header_live_inout->live_in_.begin(), header_live_inout->live_in_.end(),
+        predicate);
+
+    for (uint32_t bb_id : blocks_in_loop) {
+      ir::BasicBlock* bb = cfg_.block(bb_id);
+
+      RegisterLiveness::RegionRegisterLiveness* live_inout =
+          reg_pressure_->Get(bb);
+      live_inout->live_in_.insert(live_loop.begin(), live_loop.end());
+      live_inout->live_out_.insert(live_loop.begin(), live_loop.end());
+    }
+
+    for (const ir::Loop* inner_loop : loop) {
+      RegisterLiveness::RegionRegisterLiveness* live_inout =
+          reg_pressure_->Get(inner_loop->GetHeaderBlock());
+      live_inout->live_in_.insert(live_loop.begin(), live_loop.end());
+      live_inout->live_out_.insert(live_loop.begin(), live_loop.end());
+
+      DoLoopLivenessUnification(*inner_loop);
+    }
+  }
+
+  // Get the number of required registers for this each basic block.
+  void EvaluateRegisterRequirements() {
+    for (ir::BasicBlock& bb : *function_) {
+      RegisterLiveness::RegionRegisterLiveness* live_inout =
+          reg_pressure_->Get(bb.id());
+      assert(live_inout != nullptr && "Basic block not processed");
+
+      size_t reg_count = live_inout->live_out_.size();
+      for (ir::Instruction* insn : live_inout->live_out_) {
+        live_inout->AddRegisterClass(insn);
+      }
+      live_inout->used_registers_ = reg_count;
+
+      std::unordered_set<uint32_t> die_in_block;
+      for (ir::Instruction& insn : ir::make_range(bb.rbegin(), bb.rend())) {
+        // If it is a phi instruction, the register pressure will not change
+        // anymore.
+        if (insn.opcode() == SpvOpPhi) {
+          break;
+        }
+
+        insn.ForEachInId(
+            [live_inout, &die_in_block, &reg_count, this](uint32_t* id) {
+              ir::Instruction* op_insn = def_use_manager_.GetDef(*id);
+              if (!CreatesRegisterUsage(op_insn) ||
+                  live_inout->live_out_.count(op_insn)) {
+                // already taken into account.
+                return;
+              }
+              if (!die_in_block.count(*id)) {
+                live_inout->AddRegisterClass(def_use_manager_.GetDef(*id));
+                reg_count++;
+                die_in_block.insert(*id);
+              }
+            });
+        live_inout->used_registers_ =
+            std::max(live_inout->used_registers_, reg_count);
+        if (CreatesRegisterUsage(&insn)) {
+          reg_count--;
+        }
+      }
+    }
+  }
+
+  RegisterLiveness* reg_pressure_;
+  ir::IRContext* context_;
+  ir::Function* function_;
+  ir::CFG& cfg_;
+  analysis::DefUseManager& def_use_manager_;
+  DominatorTree& dom_tree_;
+  ir::LoopDescriptor& loop_desc_;
+};
+}  // namespace
+
+// Get the number of required registers for each basic block.
+void RegisterLiveness::RegionRegisterLiveness::AddRegisterClass(
+    ir::Instruction* insn) {
+  assert(CreatesRegisterUsage(insn) && "Instruction does not use a register");
+  analysis::Type* type =
+      insn->context()->get_type_mgr()->GetType(insn->type_id());
+
+  RegisterLiveness::RegisterClass reg_class{type, false};
+
+  insn->context()->get_decoration_mgr()->WhileEachDecoration(
+      insn->result_id(), SpvDecorationUniform,
+      [&reg_class](const ir::Instruction&) {
+        reg_class.is_uniform_ = true;
+        return false;
+      });
+
+  AddRegisterClass(reg_class);
+}
+
+void RegisterLiveness::Analyze(ir::Function* f) {
+  block_pressure_.clear();
+  ComputeRegisterLiveness(this, f).Compute();
+}
+
+void RegisterLiveness::ComputeLoopRegisterPressure(
+    const ir::Loop& loop, RegionRegisterLiveness* loop_reg_pressure) const {
+  loop_reg_pressure->Clear();
+
+  const RegionRegisterLiveness* header_live_inout = Get(loop.GetHeaderBlock());
+  loop_reg_pressure->live_in_ = header_live_inout->live_in_;
+
+  std::unordered_set<uint32_t> exit_blocks;
+  loop.GetExitBlocks(&exit_blocks);
+
+  for (uint32_t bb_id : exit_blocks) {
+    const RegionRegisterLiveness* live_inout = Get(bb_id);
+    loop_reg_pressure->live_out_.insert(live_inout->live_in_.begin(),
+                                        live_inout->live_in_.end());
+  }
+
+  std::unordered_set<uint32_t> seen_insn;
+  for (ir::Instruction* insn : loop_reg_pressure->live_out_) {
+    loop_reg_pressure->AddRegisterClass(insn);
+    seen_insn.insert(insn->result_id());
+  }
+  for (ir::Instruction* insn : loop_reg_pressure->live_in_) {
+    if (!seen_insn.count(insn->result_id())) {
+      continue;
+    }
+    loop_reg_pressure->AddRegisterClass(insn);
+    seen_insn.insert(insn->result_id());
+  }
+
+  loop_reg_pressure->used_registers_ = 0;
+
+  for (uint32_t bb_id : loop.GetBlocks()) {
+    ir::BasicBlock* bb = context_->cfg()->block(bb_id);
+
+    const RegionRegisterLiveness* live_inout = Get(bb_id);
+    assert(live_inout != nullptr && "Basic block not processed");
+    loop_reg_pressure->used_registers_ = std::max(
+        loop_reg_pressure->used_registers_, live_inout->used_registers_);
+
+    for (ir::Instruction& insn : *bb) {
+      if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) ||
+          seen_insn.count(insn.result_id())) {
+        continue;
+      }
+      loop_reg_pressure->AddRegisterClass(&insn);
+    }
+  }
+}
+
+void RegisterLiveness::SimulateFusion(
+    const ir::Loop& l1, const ir::Loop& l2,
+    RegionRegisterLiveness* sim_result) const {
+  sim_result->Clear();
+
+  // Compute the live-in state:
+  //   sim_result.live_in = l1.live_in U l2.live_in
+  // This assumes that |l1| does not generated register that is live-out for
+  // |l1|.
+  const RegionRegisterLiveness* l1_header_live_inout = Get(l1.GetHeaderBlock());
+  sim_result->live_in_ = l1_header_live_inout->live_in_;
+
+  const RegionRegisterLiveness* l2_header_live_inout = Get(l2.GetHeaderBlock());
+  sim_result->live_in_.insert(l2_header_live_inout->live_in_.begin(),
+                              l2_header_live_inout->live_in_.end());
+
+  // The live-out set of the fused loop is the l2 live-out set.
+  std::unordered_set<uint32_t> exit_blocks;
+  l2.GetExitBlocks(&exit_blocks);
+
+  for (uint32_t bb_id : exit_blocks) {
+    const RegionRegisterLiveness* live_inout = Get(bb_id);
+    sim_result->live_out_.insert(live_inout->live_in_.begin(),
+                                 live_inout->live_in_.end());
+  }
+
+  // Compute the register usage information.
+  std::unordered_set<uint32_t> seen_insn;
+  for (ir::Instruction* insn : sim_result->live_out_) {
+    sim_result->AddRegisterClass(insn);
+    seen_insn.insert(insn->result_id());
+  }
+  for (ir::Instruction* insn : sim_result->live_in_) {
+    if (!seen_insn.count(insn->result_id())) {
+      continue;
+    }
+    sim_result->AddRegisterClass(insn);
+    seen_insn.insert(insn->result_id());
+  }
+
+  sim_result->used_registers_ = 0;
+
+  // The loop fusion is injecting the l1 before the l2, the latch of l1 will be
+  // connected to the header of l2.
+  // To compute the register usage, we inject the loop live-in (union of l1 and
+  // l2 live-in header blocks) into the the live in/out of each basic block of
+  // l1 to get the peak register usage. We then repeat the operation to for l2
+  // basic blocks but in this case we inject the live-out of the latch of l1.
+  auto live_loop = ir::MakeFilterIteratorRange(
+      sim_result->live_in_.begin(), sim_result->live_in_.end(),
+      [&l1, &l2](ir::Instruction* insn) {
+        ir::BasicBlock* bb = insn->context()->get_instr_block(insn);
+        return insn->HasResultId() &&
+               !(insn->opcode() == SpvOpPhi &&
+                 (bb == l1.GetHeaderBlock() || bb == l2.GetHeaderBlock()));
+      });
+
+  for (uint32_t bb_id : l1.GetBlocks()) {
+    ir::BasicBlock* bb = context_->cfg()->block(bb_id);
+
+    const RegionRegisterLiveness* live_inout_info = Get(bb_id);
+    assert(live_inout_info != nullptr && "Basic block not processed");
+    RegionRegisterLiveness::LiveSet live_out = live_inout_info->live_out_;
+    live_out.insert(live_loop.begin(), live_loop.end());
+    sim_result->used_registers_ =
+        std::max(sim_result->used_registers_,
+                 live_inout_info->used_registers_ + live_out.size() -
+                     live_inout_info->live_out_.size());
+
+    for (ir::Instruction& insn : *bb) {
+      if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) ||
+          seen_insn.count(insn.result_id())) {
+        continue;
+      }
+      sim_result->AddRegisterClass(&insn);
+    }
+  }
+
+  const RegionRegisterLiveness* l1_latch_live_inout_info =
+      Get(l1.GetLatchBlock()->id());
+  assert(l1_latch_live_inout_info != nullptr && "Basic block not processed");
+  RegionRegisterLiveness::LiveSet l1_latch_live_out =
+      l1_latch_live_inout_info->live_out_;
+  l1_latch_live_out.insert(live_loop.begin(), live_loop.end());
+
+  auto live_loop_l2 =
+      ir::make_range(l1_latch_live_out.begin(), l1_latch_live_out.end());
+
+  for (uint32_t bb_id : l2.GetBlocks()) {
+    ir::BasicBlock* bb = context_->cfg()->block(bb_id);
+
+    const RegionRegisterLiveness* live_inout_info = Get(bb_id);
+    assert(live_inout_info != nullptr && "Basic block not processed");
+    RegionRegisterLiveness::LiveSet live_out = live_inout_info->live_out_;
+    live_out.insert(live_loop_l2.begin(), live_loop_l2.end());
+    sim_result->used_registers_ =
+        std::max(sim_result->used_registers_,
+                 live_inout_info->used_registers_ + live_out.size() -
+                     live_inout_info->live_out_.size());
+
+    for (ir::Instruction& insn : *bb) {
+      if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) ||
+          seen_insn.count(insn.result_id())) {
+        continue;
+      }
+      sim_result->AddRegisterClass(&insn);
+    }
+  }
+}
+
+void RegisterLiveness::SimulateFission(
+    const ir::Loop& loop,
+    const std::unordered_set<ir::Instruction*>& moved_inst,
+    const std::unordered_set<ir::Instruction*>& copied_inst,
+    RegionRegisterLiveness* l1_sim_result,
+    RegionRegisterLiveness* l2_sim_result) const {
+  l1_sim_result->Clear();
+  l2_sim_result->Clear();
+
+  // Filter predicates: consider instructions that only belong to the first and
+  // second loop.
+  auto belong_to_loop1 = [&moved_inst, &copied_inst,
+                          &loop](ir::Instruction* insn) {
+    return moved_inst.count(insn) || copied_inst.count(insn) ||
+           !loop.IsInsideLoop(insn);
+  };
+  auto belong_to_loop2 = [&moved_inst](ir::Instruction* insn) {
+    return !moved_inst.count(insn);
+  };
+
+  const RegionRegisterLiveness* header_live_inout = Get(loop.GetHeaderBlock());
+  // l1 live-in
+  {
+    auto live_loop = ir::MakeFilterIteratorRange(
+        header_live_inout->live_in_.begin(), header_live_inout->live_in_.end(),
+        belong_to_loop1);
+    l1_sim_result->live_in_.insert(live_loop.begin(), live_loop.end());
+  }
+  // l2 live-in
+  {
+    auto live_loop = ir::MakeFilterIteratorRange(
+        header_live_inout->live_in_.begin(), header_live_inout->live_in_.end(),
+        belong_to_loop2);
+    l2_sim_result->live_in_.insert(live_loop.begin(), live_loop.end());
+  }
+
+  std::unordered_set<uint32_t> exit_blocks;
+  loop.GetExitBlocks(&exit_blocks);
+
+  // l2 live-out.
+  for (uint32_t bb_id : exit_blocks) {
+    const RegionRegisterLiveness* live_inout = Get(bb_id);
+    l2_sim_result->live_out_.insert(live_inout->live_in_.begin(),
+                                    live_inout->live_in_.end());
+  }
+  // l1 live-out.
+  {
+    auto live_out = ir::MakeFilterIteratorRange(
+        l2_sim_result->live_out_.begin(), l2_sim_result->live_out_.end(),
+        belong_to_loop1);
+    l1_sim_result->live_out_.insert(live_out.begin(), live_out.end());
+  }
+  {
+    auto live_out = ir::MakeFilterIteratorRange(l2_sim_result->live_in_.begin(),
+                                                l2_sim_result->live_in_.end(),
+                                                belong_to_loop1);
+    l1_sim_result->live_out_.insert(live_out.begin(), live_out.end());
+  }
+  // Lives out of l1 are live out of l2 so are live in of l2 as well.
+  l2_sim_result->live_in_.insert(l1_sim_result->live_out_.begin(),
+                                 l1_sim_result->live_out_.end());
+
+  for (ir::Instruction* insn : l1_sim_result->live_in_) {
+    l1_sim_result->AddRegisterClass(insn);
+  }
+  for (ir::Instruction* insn : l2_sim_result->live_in_) {
+    l2_sim_result->AddRegisterClass(insn);
+  }
+
+  l1_sim_result->used_registers_ = 0;
+  l2_sim_result->used_registers_ = 0;
+
+  for (uint32_t bb_id : loop.GetBlocks()) {
+    ir::BasicBlock* bb = context_->cfg()->block(bb_id);
+
+    const RegisterLiveness::RegionRegisterLiveness* live_inout = Get(bb_id);
+    assert(live_inout != nullptr && "Basic block not processed");
+    auto l1_block_live_out = ir::MakeFilterIteratorRange(
+        live_inout->live_out_.begin(), live_inout->live_out_.end(),
+        belong_to_loop1);
+    auto l2_block_live_out = ir::MakeFilterIteratorRange(
+        live_inout->live_out_.begin(), live_inout->live_out_.end(),
+        belong_to_loop2);
+
+    size_t l1_reg_count =
+        std::distance(l1_block_live_out.begin(), l1_block_live_out.end());
+    size_t l2_reg_count =
+        std::distance(l2_block_live_out.begin(), l2_block_live_out.end());
+
+    std::unordered_set<uint32_t> die_in_block;
+    for (ir::Instruction& insn : ir::make_range(bb->rbegin(), bb->rend())) {
+      if (insn.opcode() == SpvOpPhi) {
+        break;
+      }
+
+      bool does_belong_to_loop1 = belong_to_loop1(&insn);
+      bool does_belong_to_loop2 = belong_to_loop2(&insn);
+      insn.ForEachInId([live_inout, &die_in_block, &l1_reg_count, &l2_reg_count,
+                        does_belong_to_loop1, does_belong_to_loop2,
+                        this](uint32_t* id) {
+        ir::Instruction* op_insn = context_->get_def_use_mgr()->GetDef(*id);
+        if (!CreatesRegisterUsage(op_insn) ||
+            live_inout->live_out_.count(op_insn)) {
+          // already taken into account.
+          return;
+        }
+        if (!die_in_block.count(*id)) {
+          if (does_belong_to_loop1) {
+            l1_reg_count++;
+          }
+          if (does_belong_to_loop2) {
+            l2_reg_count++;
+          }
+          die_in_block.insert(*id);
+        }
+      });
+      l1_sim_result->used_registers_ =
+          std::max(l1_sim_result->used_registers_, l1_reg_count);
+      l2_sim_result->used_registers_ =
+          std::max(l2_sim_result->used_registers_, l2_reg_count);
+      if (CreatesRegisterUsage(&insn)) {
+        if (does_belong_to_loop1) {
+          if (!l1_sim_result->live_in_.count(&insn)) {
+            l1_sim_result->AddRegisterClass(&insn);
+          }
+          l1_reg_count--;
+        }
+        if (does_belong_to_loop2) {
+          if (!l2_sim_result->live_in_.count(&insn)) {
+            l2_sim_result->AddRegisterClass(&insn);
+          }
+          l2_reg_count--;
+        }
+      }
+    }
+  }
+}
+
+}  // namespace opt
+}  // namespace spvtools
diff --git a/source/opt/register_pressure.h b/source/opt/register_pressure.h
new file mode 100644
index 0000000..d827a20
--- /dev/null
+++ b/source/opt/register_pressure.h
@@ -0,0 +1,201 @@
+// Copyright (c) 2018 Google LLC.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef LIBSPIRV_OPT_REGISTER_PRESSURE_H_
+#define LIBSPIRV_OPT_REGISTER_PRESSURE_H_
+
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+#include "function.h"
+#include "types.h"
+
+namespace spvtools {
+namespace ir {
+class IRContext;
+class Loop;
+class LoopDescriptor;
+}  // namespace ir
+
+namespace opt {
+
+// Handles the register pressure of a function for different regions (function,
+// loop, basic block). It also contains some utilities to foresee the register
+// pressure following code transformations.
+class RegisterLiveness {
+ public:
+  // Classification of SSA registers.
+  struct RegisterClass {
+    analysis::Type* type_;
+    bool is_uniform_;
+
+    bool operator==(const RegisterClass& rhs) const {
+      return std::tie(type_, is_uniform_) ==
+             std::tie(rhs.type_, rhs.is_uniform_);
+    }
+  };
+
+  struct RegionRegisterLiveness {
+    using LiveSet = std::unordered_set<ir::Instruction*>;
+    using RegClassSetTy = std::vector<std::pair<RegisterClass, size_t>>;
+
+    // SSA register live when entering the basic block.
+    LiveSet live_in_;
+    // SSA register live when exiting the basic block.
+    LiveSet live_out_;
+
+    // Maximum number of required registers.
+    size_t used_registers_;
+    // Break down of the number of required registers per class of register.
+    RegClassSetTy registers_classes_;
+
+    void Clear() {
+      live_out_.clear();
+      live_in_.clear();
+      used_registers_ = 0;
+      registers_classes_.clear();
+    }
+
+    void AddRegisterClass(const RegisterClass& reg_class) {
+      auto it = std::find_if(
+          registers_classes_.begin(), registers_classes_.end(),
+          [&reg_class](const std::pair<RegisterClass, size_t>& class_count) {
+            return class_count.first == reg_class;
+          });
+      if (it != registers_classes_.end()) {
+        it->second++;
+      } else {
+        registers_classes_.emplace_back(std::move(reg_class),
+                                        static_cast<size_t>(1));
+      }
+    }
+
+    void AddRegisterClass(ir::Instruction* insn);
+  };
+
+  RegisterLiveness(ir::IRContext* context, ir::Function* f)
+      : context_(context) {
+    Analyze(f);
+  }
+
+  // Returns liveness and register information for the basic block |bb|. If no
+  // entry exist for the basic block, the function returns null.
+  const RegionRegisterLiveness* Get(const ir::BasicBlock* bb) const {
+    return Get(bb->id());
+  }
+
+  // Returns liveness and register information for the basic block id |bb_id|.
+  // If no entry exist for the basic block, the function returns null.
+  const RegionRegisterLiveness* Get(uint32_t bb_id) const {
+    RegionRegisterLivenessMap::const_iterator it = block_pressure_.find(bb_id);
+    if (it != block_pressure_.end()) {
+      return &it->second;
+    }
+    return nullptr;
+  }
+
+  ir::IRContext* GetContext() const { return context_; }
+
+  // Returns liveness and register information for the basic block |bb|. If no
+  // entry exist for the basic block, the function returns null.
+  RegionRegisterLiveness* Get(const ir::BasicBlock* bb) {
+    return Get(bb->id());
+  }
+
+  // Returns liveness and register information for the basic block id |bb_id|.
+  // If no entry exist for the basic block, the function returns null.
+  RegionRegisterLiveness* Get(uint32_t bb_id) {
+    RegionRegisterLivenessMap::iterator it = block_pressure_.find(bb_id);
+    if (it != block_pressure_.end()) {
+      return &it->second;
+    }
+    return nullptr;
+  }
+
+  // Returns liveness and register information for the basic block id |bb_id| or
+  // create a new empty entry if no entry already existed.
+  RegionRegisterLiveness* GetOrInsert(uint32_t bb_id) {
+    return &block_pressure_[bb_id];
+  }
+
+  // Compute the register pressure for the |loop| and store the result into
+  // |reg_pressure|. The live-in set corresponds to the live-in set of the
+  // header block, the live-out set of the loop corresponds to the union of the
+  // live-in sets of each exit basic block.
+  void ComputeLoopRegisterPressure(const ir::Loop& loop,
+                                   RegionRegisterLiveness* reg_pressure) const;
+
+  // Estimate the register pressure for the |l1| and |l2| as if they were making
+  // one unique loop. The result is stored into |simulation_result|.
+  void SimulateFusion(const ir::Loop& l1, const ir::Loop& l2,
+                      RegionRegisterLiveness* simulation_result) const;
+
+  // Estimate the register pressure of |loop| after it has been fissioned
+  // according to |moved_instructions| and |copied_instructions|. The function
+  // assumes that the fission creates a new loop before |loop|, moves any
+  // instructions present inside |moved_instructions| and copies any
+  // instructions present inside |copied_instructions| into this new loop.
+  // The set |loop1_sim_result| store the simulation result of the loop with the
+  // moved instructions. The set |loop2_sim_result| store the simulation result
+  // of the loop with the removed instructions.
+  void SimulateFission(
+      const ir::Loop& loop,
+      const std::unordered_set<ir::Instruction*>& moved_instructions,
+      const std::unordered_set<ir::Instruction*>& copied_instructions,
+      RegionRegisterLiveness* loop1_sim_result,
+      RegionRegisterLiveness* loop2_sim_result) const;
+
+ private:
+  using RegionRegisterLivenessMap =
+      std::unordered_map<uint32_t, RegionRegisterLiveness>;
+
+  ir::IRContext* context_;
+  RegionRegisterLivenessMap block_pressure_;
+
+  void Analyze(ir::Function* f);
+};
+
+// Handles the register pressure of a function for different regions (function,
+// loop, basic block). It also contains some utilities to foresee the register
+// pressure following code transformations.
+class LivenessAnalysis {
+  using LivenessAnalysisMap =
+      std::unordered_map<const ir::Function*, RegisterLiveness>;
+
+ public:
+  LivenessAnalysis(ir::IRContext* context) : context_(context) {}
+
+  // Computes the liveness analysis for the function |f| and cache the result.
+  // If the analysis was performed for this function, then the cached analysis
+  // is returned.
+  const RegisterLiveness* Get(ir::Function* f) {
+    LivenessAnalysisMap::iterator it = analysis_cache_.find(f);
+    if (it != analysis_cache_.end()) {
+      return &it->second;
+    }
+    return &analysis_cache_.emplace(f, RegisterLiveness{context_, f})
+                .first->second;
+  }
+
+ private:
+  ir::IRContext* context_;
+  LivenessAnalysisMap analysis_cache_;
+};
+
+}  // namespace opt
+}  // namespace spvtools
+
+#endif  // ! LIBSPIRV_OPT_REGISTER_PRESSURE_H_
diff --git a/test/opt/CMakeLists.txt b/test/opt/CMakeLists.txt
index 07b2d1e..e3d83d6 100644
--- a/test/opt/CMakeLists.txt
+++ b/test/opt/CMakeLists.txt
@@ -297,6 +297,11 @@
   LIBS SPIRV-Tools-opt
 )
 
+add_spvtools_unittest(TARGET register_liveness
+  SRCS register_liveness.cpp
+  LIBS SPIRV-Tools-opt
+)
+
 add_spvtools_unittest(TARGET simplification
   SRCS simplification_test.cpp pass_utils.cpp
   LIBS SPIRV-Tools-opt
diff --git a/test/opt/iterator_test.cpp b/test/opt/iterator_test.cpp
index 5afe88c..5918430 100644
--- a/test/opt/iterator_test.cpp
+++ b/test/opt/iterator_test.cpp
@@ -214,4 +214,53 @@
   EXPECT_EQ(count, range.size());
 }
 
+TEST(Iterator, FilterIterator) {
+  struct Placeholder {
+    int val;
+  };
+  std::vector<Placeholder> data = {{1}, {2}, {3}, {4}, {5},
+                                   {6}, {7}, {8}, {9}, {10}};
+
+  // Predicate to only consider odd values.
+  struct Predicate {
+    bool operator()(const Placeholder& data) { return data.val % 2; }
+  };
+  Predicate pred;
+
+  auto filter_range =
+      ir::MakeFilterIteratorRange(data.begin(), data.end(), pred);
+
+  EXPECT_EQ(filter_range.begin().Get(), data.begin());
+  EXPECT_EQ(filter_range.end(), filter_range.begin().GetEnd());
+
+  for (Placeholder& data : filter_range) {
+    EXPECT_EQ(data.val % 2, 1);
+  }
+
+  for (auto it = filter_range.begin(); it != filter_range.end(); it++) {
+    EXPECT_EQ(it->val % 2, 1);
+    EXPECT_EQ((*it).val % 2, 1);
+  }
+
+  for (auto it = filter_range.begin(); it != filter_range.end(); ++it) {
+    EXPECT_EQ(it->val % 2, 1);
+    EXPECT_EQ((*it).val % 2, 1);
+  }
+
+  EXPECT_EQ(ir::MakeFilterIterator(data.begin(), data.end(), pred).Get(),
+            data.begin());
+  EXPECT_EQ(ir::MakeFilterIterator(data.end(), data.end(), pred).Get(),
+            data.end());
+  EXPECT_EQ(ir::MakeFilterIterator(data.begin(), data.end(), pred).GetEnd(),
+            ir::MakeFilterIterator(data.end(), data.end(), pred));
+  EXPECT_NE(ir::MakeFilterIterator(data.begin(), data.end(), pred),
+            ir::MakeFilterIterator(data.end(), data.end(), pred));
+
+  // Empty range: no values satisfies the predicate.
+  auto empty_range = ir::MakeFilterIteratorRange(
+      data.begin(), data.end(),
+      [](const Placeholder& data) { return data.val > 10; });
+  EXPECT_EQ(empty_range.begin(), empty_range.end());
+}
+
 }  // anonymous namespace
diff --git a/test/opt/register_liveness.cpp b/test/opt/register_liveness.cpp
new file mode 100644
index 0000000..1425cf9
--- /dev/null
+++ b/test/opt/register_liveness.cpp
@@ -0,0 +1,1279 @@
+// Copyright (c) 2018 Google LLC.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <gmock/gmock.h>
+
+#include <memory>
+#include <string>
+#include <vector>
+
+#include "assembly_builder.h"
+#include "function_utils.h"
+#include "opt/register_pressure.h"
+#include "pass_fixture.h"
+#include "pass_utils.h"
+
+namespace {
+
+using namespace spvtools;
+using ::testing::UnorderedElementsAre;
+
+using PassClassTest = PassTest<::testing::Test>;
+
+static void CompareSets(const std::unordered_set<ir::Instruction*>& computed,
+                        const std::unordered_set<uint32_t>& expected) {
+  for (ir::Instruction* insn : computed) {
+    EXPECT_TRUE(expected.count(insn->result_id()))
+        << "Unexpected instruction in live set: " << *insn;
+  }
+  EXPECT_EQ(computed.size(), expected.size());
+}
+
+/*
+Generated from the following GLSL
+
+#version 330
+in vec4 BaseColor;
+flat in int Count;
+void main()
+{
+  vec4 color = BaseColor;
+  vec4 acc;
+  if (Count == 0) {
+    acc = color;
+  }
+  else {
+    acc = color + vec4(0,1,2,0);
+  }
+  gl_FragColor = acc + color;
+}
+*/
+TEST_F(PassClassTest, LivenessWithIf) {
+  const std::string text = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main" %11 %15 %32
+               OpExecutionMode %4 OriginLowerLeft
+               OpSource GLSL 330
+               OpName %4 "main"
+               OpName %11 "BaseColor"
+               OpName %15 "Count"
+               OpName %32 "gl_FragColor"
+               OpDecorate %11 Location 0
+               OpDecorate %15 Flat
+               OpDecorate %15 Location 0
+               OpDecorate %32 Location 0
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeFloat 32
+          %7 = OpTypeVector %6 4
+         %10 = OpTypePointer Input %7
+         %11 = OpVariable %10 Input
+         %13 = OpTypeInt 32 1
+         %14 = OpTypePointer Input %13
+         %15 = OpVariable %14 Input
+         %17 = OpConstant %13 0
+         %18 = OpTypeBool
+         %26 = OpConstant %6 0
+         %27 = OpConstant %6 1
+         %28 = OpConstant %6 2
+         %29 = OpConstantComposite %7 %26 %27 %28 %26
+         %31 = OpTypePointer Output %7
+         %32 = OpVariable %31 Output
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %12 = OpLoad %7 %11
+         %16 = OpLoad %13 %15
+         %19 = OpIEqual %18 %16 %17
+               OpSelectionMerge %21 None
+               OpBranchConditional %19 %20 %24
+         %20 = OpLabel
+               OpBranch %21
+         %24 = OpLabel
+         %30 = OpFAdd %7 %12 %29
+               OpBranch %21
+         %21 = OpLabel
+         %36 = OpPhi %7 %12 %20 %30 %24
+         %35 = OpFAdd %7 %36 %12
+               OpStore %32 %35
+               OpReturn
+               OpFunctionEnd
+  )";
+  std::unique_ptr<ir::IRContext> context =
+      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+  ir::Module* module = context->module();
+  EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
+                             << text << std::endl;
+  ir::Function* f = &*module->begin();
+  opt::LivenessAnalysis* liveness_analysis = context->GetLivenessAnalysis();
+  const opt::RegisterLiveness* register_liveness = liveness_analysis->Get(f);
+  {
+    SCOPED_TRACE("Block 5");
+    auto live_sets = register_liveness->Get(5);
+    std::unordered_set<uint32_t> live_in{
+        11,  // %11 = OpVariable %10 Input
+        15,  // %15 = OpVariable %14 Input
+        32,  // %32 = OpVariable %31 Output
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        12,  // %12 = OpLoad %7 %11
+        32,  // %32 = OpVariable %31 Output
+    };
+    CompareSets(live_sets->live_out_, live_out);
+  }
+  {
+    SCOPED_TRACE("Block 20");
+    auto live_sets = register_liveness->Get(20);
+    std::unordered_set<uint32_t> live_inout{
+        12,  // %12 = OpLoad %7 %11
+        32,  // %32 = OpVariable %31 Output
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+  }
+  {
+    SCOPED_TRACE("Block 24");
+    auto live_sets = register_liveness->Get(24);
+    std::unordered_set<uint32_t> live_in{
+        12,  // %12 = OpLoad %7 %11
+        32,  // %32 = OpVariable %31 Output
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        12,  // %12 = OpLoad %7 %11
+        30,  // %30 = OpFAdd %7 %12 %29
+        32,  // %32 = OpVariable %31 Output
+    };
+    CompareSets(live_sets->live_out_, live_out);
+  }
+  {
+    SCOPED_TRACE("Block 21");
+    auto live_sets = register_liveness->Get(21);
+    std::unordered_set<uint32_t> live_in{
+        12,  // %12 = OpLoad %7 %11
+        32,  // %32 = OpVariable %31 Output
+        36,  // %36 = OpPhi %7 %12 %20 %30 %24
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{};
+    CompareSets(live_sets->live_out_, live_out);
+  }
+}
+
+/*
+Generated from the following GLSL
+#version 330
+in vec4 bigColor;
+in vec4 BaseColor;
+in float f;
+flat in int Count;
+flat in uvec4 v4;
+void main()
+{
+    vec4 color = BaseColor;
+    for (int i = 0; i < Count; ++i)
+        color += bigColor;
+    float sum = 0.0;
+    for (int i = 0; i < 4; ++i) {
+      float acc = 0.0;
+      if (sum == 0.0) {
+        acc = v4[i];
+      }
+      else {
+        acc = BaseColor[i];
+      }
+      sum += acc + v4[i];
+    }
+    vec4 tv4;
+    for (int i = 0; i < 4; ++i)
+        tv4[i] = v4[i] * 4u;
+    color += vec4(sum) + tv4;
+    vec4 r;
+    r.xyz = BaseColor.xyz;
+    for (int i = 0; i < Count; ++i)
+        r.w = f;
+    color.xyz += r.xyz;
+    for (int i = 0; i < 16; i += 4)
+      for (int j = 0; j < 4; j++)
+        color *= f;
+    gl_FragColor = color + tv4;
+}
+*/
+TEST_F(PassClassTest, RegisterLiveness) {
+  const std::string text = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main" %11 %24 %28 %55 %124 %176
+               OpExecutionMode %4 OriginLowerLeft
+               OpSource GLSL 330
+               OpName %4 "main"
+               OpName %11 "BaseColor"
+               OpName %24 "Count"
+               OpName %28 "bigColor"
+               OpName %55 "v4"
+               OpName %84 "tv4"
+               OpName %124 "f"
+               OpName %176 "gl_FragColor"
+               OpDecorate %11 Location 0
+               OpDecorate %24 Flat
+               OpDecorate %24 Location 0
+               OpDecorate %28 Location 0
+               OpDecorate %55 Flat
+               OpDecorate %55 Location 0
+               OpDecorate %124 Location 0
+               OpDecorate %176 Location 0
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeFloat 32
+          %7 = OpTypeVector %6 4
+          %8 = OpTypePointer Function %7
+         %10 = OpTypePointer Input %7
+         %11 = OpVariable %10 Input
+         %13 = OpTypeInt 32 1
+         %16 = OpConstant %13 0
+         %23 = OpTypePointer Input %13
+         %24 = OpVariable %23 Input
+         %26 = OpTypeBool
+         %28 = OpVariable %10 Input
+         %33 = OpConstant %13 1
+         %35 = OpTypePointer Function %6
+         %37 = OpConstant %6 0
+         %45 = OpConstant %13 4
+         %52 = OpTypeInt 32 0
+         %53 = OpTypeVector %52 4
+         %54 = OpTypePointer Input %53
+         %55 = OpVariable %54 Input
+         %57 = OpTypePointer Input %52
+         %63 = OpTypePointer Input %6
+         %89 = OpConstant %52 4
+        %102 = OpTypeVector %6 3
+        %124 = OpVariable %63 Input
+        %158 = OpConstant %13 16
+        %175 = OpTypePointer Output %7
+        %176 = OpVariable %175 Output
+        %195 = OpUndef %7
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %84 = OpVariable %8 Function
+         %12 = OpLoad %7 %11
+               OpBranch %17
+         %17 = OpLabel
+        %191 = OpPhi %7 %12 %5 %31 %18
+        %184 = OpPhi %13 %16 %5 %34 %18
+         %25 = OpLoad %13 %24
+         %27 = OpSLessThan %26 %184 %25
+               OpLoopMerge %19 %18 None
+               OpBranchConditional %27 %18 %19
+         %18 = OpLabel
+         %29 = OpLoad %7 %28
+         %31 = OpFAdd %7 %191 %29
+         %34 = OpIAdd %13 %184 %33
+               OpBranch %17
+         %19 = OpLabel
+               OpBranch %39
+         %39 = OpLabel
+        %188 = OpPhi %6 %37 %19 %73 %51
+        %185 = OpPhi %13 %16 %19 %75 %51
+         %46 = OpSLessThan %26 %185 %45
+               OpLoopMerge %41 %51 None
+               OpBranchConditional %46 %40 %41
+         %40 = OpLabel
+         %49 = OpFOrdEqual %26 %188 %37
+               OpSelectionMerge %51 None
+               OpBranchConditional %49 %50 %61
+         %50 = OpLabel
+         %58 = OpAccessChain %57 %55 %185
+         %59 = OpLoad %52 %58
+         %60 = OpConvertUToF %6 %59
+               OpBranch %51
+         %61 = OpLabel
+         %64 = OpAccessChain %63 %11 %185
+         %65 = OpLoad %6 %64
+               OpBranch %51
+         %51 = OpLabel
+        %210 = OpPhi %6 %60 %50 %65 %61
+         %68 = OpAccessChain %57 %55 %185
+         %69 = OpLoad %52 %68
+         %70 = OpConvertUToF %6 %69
+         %71 = OpFAdd %6 %210 %70
+         %73 = OpFAdd %6 %188 %71
+         %75 = OpIAdd %13 %185 %33
+               OpBranch %39
+         %41 = OpLabel
+               OpBranch %77
+         %77 = OpLabel
+        %186 = OpPhi %13 %16 %41 %94 %78
+         %83 = OpSLessThan %26 %186 %45
+               OpLoopMerge %79 %78 None
+               OpBranchConditional %83 %78 %79
+         %78 = OpLabel
+         %87 = OpAccessChain %57 %55 %186
+         %88 = OpLoad %52 %87
+         %90 = OpIMul %52 %88 %89
+         %91 = OpConvertUToF %6 %90
+         %92 = OpAccessChain %35 %84 %186
+               OpStore %92 %91
+         %94 = OpIAdd %13 %186 %33
+               OpBranch %77
+         %79 = OpLabel
+         %96 = OpCompositeConstruct %7 %188 %188 %188 %188
+         %97 = OpLoad %7 %84
+         %98 = OpFAdd %7 %96 %97
+        %100 = OpFAdd %7 %191 %98
+        %104 = OpVectorShuffle %102 %12 %12 0 1 2
+        %106 = OpVectorShuffle %7 %195 %104 4 5 6 3
+               OpBranch %108
+        %108 = OpLabel
+        %197 = OpPhi %7 %106 %79 %208 %133
+        %196 = OpPhi %13 %16 %79 %143 %133
+        %115 = OpSLessThan %26 %196 %25
+               OpLoopMerge %110 %133 None
+               OpBranchConditional %115 %109 %110
+        %109 = OpLabel
+               OpBranch %117
+        %117 = OpLabel
+        %209 = OpPhi %7 %197 %109 %181 %118
+        %204 = OpPhi %13 %16 %109 %129 %118
+        %123 = OpSLessThan %26 %204 %45
+               OpLoopMerge %119 %118 None
+               OpBranchConditional %123 %118 %119
+        %118 = OpLabel
+        %125 = OpLoad %6 %124
+        %181 = OpCompositeInsert %7 %125 %209 3
+        %129 = OpIAdd %13 %204 %33
+               OpBranch %117
+        %119 = OpLabel
+               OpBranch %131
+        %131 = OpLabel
+        %208 = OpPhi %7 %209 %119 %183 %132
+        %205 = OpPhi %13 %16 %119 %141 %132
+        %137 = OpSLessThan %26 %205 %45
+               OpLoopMerge %133 %132 None
+               OpBranchConditional %137 %132 %133
+        %132 = OpLabel
+        %138 = OpLoad %6 %124
+        %183 = OpCompositeInsert %7 %138 %208 3
+        %141 = OpIAdd %13 %205 %33
+               OpBranch %131
+        %133 = OpLabel
+        %143 = OpIAdd %13 %196 %33
+               OpBranch %108
+        %110 = OpLabel
+        %145 = OpVectorShuffle %102 %197 %197 0 1 2
+        %147 = OpVectorShuffle %102 %100 %100 0 1 2
+        %148 = OpFAdd %102 %147 %145
+        %150 = OpVectorShuffle %7 %100 %148 4 5 6 3
+               OpBranch %152
+        %152 = OpLabel
+        %200 = OpPhi %7 %150 %110 %203 %163
+        %199 = OpPhi %13 %16 %110 %174 %163
+        %159 = OpSLessThan %26 %199 %158
+               OpLoopMerge %154 %163 None
+               OpBranchConditional %159 %153 %154
+        %153 = OpLabel
+               OpBranch %161
+        %161 = OpLabel
+        %203 = OpPhi %7 %200 %153 %170 %162
+        %201 = OpPhi %13 %16 %153 %172 %162
+        %167 = OpSLessThan %26 %201 %45
+               OpLoopMerge %163 %162 None
+               OpBranchConditional %167 %162 %163
+        %162 = OpLabel
+        %168 = OpLoad %6 %124
+        %170 = OpVectorTimesScalar %7 %203 %168
+        %172 = OpIAdd %13 %201 %33
+               OpBranch %161
+        %163 = OpLabel
+        %174 = OpIAdd %13 %199 %45
+               OpBranch %152
+        %154 = OpLabel
+        %178 = OpLoad %7 %84
+        %179 = OpFAdd %7 %200 %178
+               OpStore %176 %179
+               OpReturn
+               OpFunctionEnd
+  )";
+  std::unique_ptr<ir::IRContext> context =
+      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+  ir::Module* module = context->module();
+  EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
+                             << text << std::endl;
+  ir::Function* f = &*module->begin();
+  opt::LivenessAnalysis* liveness_analysis = context->GetLivenessAnalysis();
+  const opt::RegisterLiveness* register_liveness = liveness_analysis->Get(f);
+  ir::LoopDescriptor& ld = *context->GetLoopDescriptor(f);
+
+  {
+    SCOPED_TRACE("Block 5");
+    auto live_sets = register_liveness->Get(5);
+    std::unordered_set<uint32_t> live_in{
+        11,   // %11 = OpVariable %10 Input
+        24,   // %24 = OpVariable %23 Input
+        28,   // %28 = OpVariable %10 Input
+        55,   // %55 = OpVariable %54 Input
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        24,   // %24 = OpVariable %23 Input
+        28,   // %28 = OpVariable %10 Input
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 8u);
+  }
+  {
+    SCOPED_TRACE("Block 17");
+    auto live_sets = register_liveness->Get(17);
+    std::unordered_set<uint32_t> live_in{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        24,   // %24 = OpVariable %23 Input
+        28,   // %28 = OpVariable %10 Input
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        184,  // %184 = OpPhi %13 %16 %5 %34 %18
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        28,   // %28 = OpVariable %10 Input
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        184,  // %184 = OpPhi %13 %16 %5 %34 %18
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 11u);
+  }
+  {
+    SCOPED_TRACE("Block 18");
+    auto live_sets = register_liveness->Get(18);
+    std::unordered_set<uint32_t> live_in{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        24,   // %24 = OpVariable %23 Input
+        28,   // %28 = OpVariable %10 Input
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        184,  // %184 = OpPhi %13 %16 %5 %34 %18
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        24,   // %24 = OpVariable %23 Input
+        28,   // %28 = OpVariable %10 Input
+        31,   // %31 = OpFAdd %7 %191 %29
+        34,   // %34 = OpIAdd %13 %184 %33
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 12u);
+  }
+  {
+    SCOPED_TRACE("Block 19");
+    auto live_sets = register_liveness->Get(19);
+    std::unordered_set<uint32_t> live_inout{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 8u);
+  }
+  {
+    SCOPED_TRACE("Block 39");
+    auto live_sets = register_liveness->Get(39);
+    std::unordered_set<uint32_t> live_inout{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        185,  // %185 = OpPhi %13 %16 %19 %75 %51
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 11u);
+  }
+  {
+    SCOPED_TRACE("Block 40");
+    auto live_sets = register_liveness->Get(40);
+    std::unordered_set<uint32_t> live_inout{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        185,  // %185 = OpPhi %13 %16 %19 %75 %51
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 11u);
+  }
+  {
+    SCOPED_TRACE("Block 50");
+    auto live_sets = register_liveness->Get(50);
+    std::unordered_set<uint32_t> live_in{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        185,  // %185 = OpPhi %13 %16 %19 %75 %51
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        60,   // %60 = OpConvertUToF %6 %59
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        185,  // %185 = OpPhi %13 %16 %19 %75 %51
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 12u);
+  }
+  {
+    SCOPED_TRACE("Block 61");
+    auto live_sets = register_liveness->Get(61);
+    std::unordered_set<uint32_t> live_in{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        185,  // %185 = OpPhi %13 %16 %19 %75 %51
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        65,   // %65 = OpLoad %6 %64
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        185,  // %185 = OpPhi %13 %16 %19 %75 %51
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 12u);
+  }
+  {
+    SCOPED_TRACE("Block 51");
+    auto live_sets = register_liveness->Get(51);
+    std::unordered_set<uint32_t> live_in{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        185,  // %185 = OpPhi %13 %16 %19 %75 %51
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+        210,  // %210 = OpPhi %6 %60 %50 %65 %61
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        73,   // %73 = OpFAdd %6 %188 %71
+        75,   // %75 = OpIAdd %13 %185 %33
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 13u);
+  }
+  {
+    SCOPED_TRACE("Block 41");
+    auto live_sets = register_liveness->Get(41);
+    std::unordered_set<uint32_t> live_inout{
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 8u);
+  }
+  {
+    SCOPED_TRACE("Block 77");
+    auto live_sets = register_liveness->Get(77);
+    std::unordered_set<uint32_t> live_inout{
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        186,  // %186 = OpPhi %13 %16 %41 %94 %78
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 10u);
+  }
+  {
+    SCOPED_TRACE("Block 78");
+    auto live_sets = register_liveness->Get(78);
+    std::unordered_set<uint32_t> live_in{
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        186,  // %186 = OpPhi %13 %16 %41 %94 %78
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        94,   // %94 = OpIAdd %13 %186 %33
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 11u);
+  }
+  {
+    SCOPED_TRACE("Block 79");
+    auto live_sets = register_liveness->Get(79);
+    std::unordered_set<uint32_t> live_in{
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        106,  // %106 = OpVectorShuffle %7 %195 %104 4 5 6 3
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 9u);
+  }
+  {
+    SCOPED_TRACE("Block 108");
+    auto live_sets = register_liveness->Get(108);
+    std::unordered_set<uint32_t> live_in{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        196,  // %196 = OpPhi %13 %16 %79 %143 %133
+        197,  // %197 = OpPhi %7 %106 %79 %208 %133
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        196,  // %196 = OpPhi %13 %16 %79 %143 %133
+        197,  // %197 = OpPhi %7 %106 %79 %208 %133
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 8u);
+  }
+  {
+    SCOPED_TRACE("Block 109");
+    auto live_sets = register_liveness->Get(109);
+    std::unordered_set<uint32_t> live_inout{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        196,  // %196 = OpPhi %13 %16 %79 %143 %133
+        197,  // %197 = OpPhi %7 %106 %79 %208 %133
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 7u);
+  }
+  {
+    SCOPED_TRACE("Block 117");
+    auto live_sets = register_liveness->Get(117);
+    std::unordered_set<uint32_t> live_inout{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        196,  // %196 = OpPhi %13 %16 %79 %143 %133
+        204,  // %204 = OpPhi %13 %16 %109 %129 %118
+        209,  // %209 = OpPhi %7 %197 %109 %181 %118
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 9u);
+  }
+  {
+    SCOPED_TRACE("Block 118");
+    auto live_sets = register_liveness->Get(118);
+    std::unordered_set<uint32_t> live_in{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        196,  // %196 = OpPhi %13 %16 %79 %143 %133
+        204,  // %204 = OpPhi %13 %16 %109 %129 %118
+        209,  // %209 = OpPhi %7 %197 %109 %181 %118
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        129,  // %129 = OpIAdd %13 %204 %33
+        176,  // %176 = OpVariable %175 Output
+        181,  // %181 = OpCompositeInsert %7 %125 %209 3
+        196,  // %196 = OpPhi %13 %16 %79 %143 %133
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 10u);
+  }
+  {
+    SCOPED_TRACE("Block 119");
+    auto live_sets = register_liveness->Get(119);
+    std::unordered_set<uint32_t> live_inout{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        196,  // %196 = OpPhi %13 %16 %79 %143 %133
+        209,  // %209 = OpPhi %7 %197 %109 %181 %118
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 7u);
+  }
+  {
+    SCOPED_TRACE("Block 131");
+    auto live_sets = register_liveness->Get(131);
+    std::unordered_set<uint32_t> live_inout{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        196,  // %196 = OpPhi %13 %16 %79 %143 %133
+        205,  // %205 = OpPhi %13 %16 %119 %141 %132
+        208,  // %208 = OpPhi %7 %209 %119 %183 %132
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 9u);
+  }
+  {
+    SCOPED_TRACE("Block 132");
+    auto live_sets = register_liveness->Get(132);
+    std::unordered_set<uint32_t> live_in{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        196,  // %196 = OpPhi %13 %16 %79 %143 %133
+        205,  // %205 = OpPhi %13 %16 %119 %141 %132
+        208,  // %208 = OpPhi %7 %209 %119 %183 %132
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        141,  // %141 = OpIAdd %13 %205 %33
+        176,  // %176 = OpVariable %175 Output
+        183,  // %183 = OpCompositeInsert %7 %138 %208 3
+        196,  // %196 = OpPhi %13 %16 %79 %143 %133
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 10u);
+  }
+  {
+    SCOPED_TRACE("Block 133");
+    auto live_sets = register_liveness->Get(133);
+    std::unordered_set<uint32_t> live_in{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        196,  // %196 = OpPhi %13 %16 %79 %143 %133
+        208,  // %208 = OpPhi %7 %209 %119 %183 %132
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        25,   // %25 = OpLoad %13 %24
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        143,  // %143 = OpIAdd %13 %196 %33
+        176,  // %176 = OpVariable %175 Output
+        208,  // %208 = OpPhi %7 %209 %119 %183 %132
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 8u);
+  }
+  {
+    SCOPED_TRACE("Block 110");
+    auto live_sets = register_liveness->Get(110);
+    std::unordered_set<uint32_t> live_in{
+        84,   // %84 = OpVariable %8 Function
+        100,  // %100 = OpFAdd %7 %191 %98
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        197,  // %197 = OpPhi %7 %106 %79 %208 %133
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        150,  // %150 = OpVectorShuffle %7 %100 %148 4 5 6 3
+        176,  // %176 = OpVariable %175 Output
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 7u);
+  }
+  {
+    SCOPED_TRACE("Block 152");
+    auto live_sets = register_liveness->Get(152);
+    std::unordered_set<uint32_t> live_inout{
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        199,  // %199 = OpPhi %13 %16 %110 %174 %163
+        200,  // %200 = OpPhi %7 %150 %110 %203 %163
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 6u);
+  }
+  {
+    SCOPED_TRACE("Block 153");
+    auto live_sets = register_liveness->Get(153);
+    std::unordered_set<uint32_t> live_inout{
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        199,  // %199 = OpPhi %13 %16 %110 %174 %163
+        200,  // %200 = OpPhi %7 %150 %110 %203 %163
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 5u);
+  }
+  {
+    SCOPED_TRACE("Block 161");
+    auto live_sets = register_liveness->Get(161);
+    std::unordered_set<uint32_t> live_inout{
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        199,  // %199 = OpPhi %13 %16 %110 %174 %163
+        201,  // %201 = OpPhi %13 %16 %153 %172 %162
+        203,  // %203 = OpPhi %7 %200 %153 %170 %162
+    };
+    CompareSets(live_sets->live_in_, live_inout);
+    CompareSets(live_sets->live_out_, live_inout);
+
+    EXPECT_EQ(live_sets->used_registers_, 7u);
+  }
+  {
+    SCOPED_TRACE("Block 162");
+    auto live_sets = register_liveness->Get(162);
+    std::unordered_set<uint32_t> live_in{
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        199,  // %199 = OpPhi %13 %16 %110 %174 %163
+        201,  // %201 = OpPhi %13 %16 %153 %172 %162
+        203,  // %203 = OpPhi %7 %200 %153 %170 %162
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        170,  // %170 = OpVectorTimesScalar %7 %203 %168
+        172,  // %172 = OpIAdd %13 %201 %33
+        176,  // %176 = OpVariable %175 Output
+        199,  // %199 = OpPhi %13 %16 %110 %174 %163
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 8u);
+  }
+  {
+    SCOPED_TRACE("Block 163");
+    auto live_sets = register_liveness->Get(163);
+    std::unordered_set<uint32_t> live_in{
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        199,  // %199 = OpPhi %13 %16 %110 %174 %163
+        203,  // %203 = OpPhi %7 %200 %153 %170 %162
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        174,  // %174 = OpIAdd %13 %199 %45
+        176,  // %176 = OpVariable %175 Output
+        203,  // %203 = OpPhi %7 %200 %153 %170 %162
+    };
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 6u);
+  }
+  {
+    SCOPED_TRACE("Block 154");
+    auto live_sets = register_liveness->Get(154);
+    std::unordered_set<uint32_t> live_in{
+        84,   // %84 = OpVariable %8 Function
+        176,  // %176 = OpVariable %175 Output
+        200,  // %200 = OpPhi %7 %150 %110 %203 %163
+    };
+    CompareSets(live_sets->live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{};
+    CompareSets(live_sets->live_out_, live_out);
+
+    EXPECT_EQ(live_sets->used_registers_, 4u);
+  }
+
+  {
+    SCOPED_TRACE("Compute loop pressure");
+    opt::RegisterLiveness::RegionRegisterLiveness loop_reg_pressure;
+    register_liveness->ComputeLoopRegisterPressure(*ld[39], &loop_reg_pressure);
+    // Generate(*context->cfg()->block(39), &loop_reg_pressure);
+    std::unordered_set<uint32_t> live_in{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        185,  // %185 = OpPhi %13 %16 %19 %75 %51
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(loop_reg_pressure.live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(loop_reg_pressure.live_out_, live_out);
+
+    EXPECT_EQ(loop_reg_pressure.used_registers_, 13u);
+  }
+
+  {
+    SCOPED_TRACE("Loop Fusion simulation");
+    opt::RegisterLiveness::RegionRegisterLiveness simulation_resut;
+    register_liveness->SimulateFusion(*ld[17], *ld[39], &simulation_resut);
+
+    std::unordered_set<uint32_t> live_in{
+        11,   // %11 = OpVariable %10 Input
+        12,   // %12 = OpLoad %7 %11
+        24,   // %24 = OpVariable %23 Input
+        25,   // %25 = OpLoad %13 %24
+        28,   // %28 = OpVariable %10 Input
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        184,  // %184 = OpPhi %13 %16 %5 %34 %18
+        185,  // %185 = OpPhi %13 %16 %19 %75 %51
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(simulation_resut.live_in_, live_in);
+
+    std::unordered_set<uint32_t> live_out{
+        12,   // %12 = OpLoad %7 %11
+        25,   // %25 = OpLoad %13 %24
+        55,   // %55 = OpVariable %54 Input
+        84,   // %84 = OpVariable %8 Function
+        124,  // %124 = OpVariable %63 Input
+        176,  // %176 = OpVariable %175 Output
+        188,  // %188 = OpPhi %6 %37 %19 %73 %51
+        191,  // %191 = OpPhi %7 %12 %5 %31 %18
+    };
+    CompareSets(simulation_resut.live_out_, live_out);
+
+    EXPECT_EQ(simulation_resut.used_registers_, 17u);
+  }
+}
+
+TEST_F(PassClassTest, FissionSimulation) {
+  const std::string source = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %2 "main"
+               OpExecutionMode %2 OriginUpperLeft
+               OpSource GLSL 430
+               OpName %2 "main"
+               OpName %3 "i"
+               OpName %4 "A"
+               OpName %5 "B"
+          %6 = OpTypeVoid
+          %7 = OpTypeFunction %6
+          %8 = OpTypeInt 32 1
+          %9 = OpTypePointer Function %8
+         %10 = OpConstant %8 0
+         %11 = OpConstant %8 10
+         %12 = OpTypeBool
+         %13 = OpTypeFloat 32
+         %14 = OpTypeInt 32 0
+         %15 = OpConstant %14 10
+         %16 = OpTypeArray %13 %15
+         %17 = OpTypePointer Function %16
+         %18 = OpTypePointer Function %13
+         %19 = OpConstant %8 1
+          %2 = OpFunction %6 None %7
+         %20 = OpLabel
+          %3 = OpVariable %9 Function
+          %4 = OpVariable %17 Function
+          %5 = OpVariable %17 Function
+               OpBranch %21
+         %21 = OpLabel
+         %22 = OpPhi %8 %10 %20 %23 %24
+               OpLoopMerge %25 %24 None
+               OpBranch %26
+         %26 = OpLabel
+         %27 = OpSLessThan %12 %22 %11
+               OpBranchConditional %27 %28 %25
+         %28 = OpLabel
+         %29 = OpAccessChain %18 %5 %22
+         %30 = OpLoad %13 %29
+         %31 = OpAccessChain %18 %4 %22
+               OpStore %31 %30
+         %32 = OpAccessChain %18 %4 %22
+         %33 = OpLoad %13 %32
+         %34 = OpAccessChain %18 %5 %22
+               OpStore %34 %33
+               OpBranch %24
+         %24 = OpLabel
+         %23 = OpIAdd %8 %22 %19
+               OpBranch %21
+         %25 = OpLabel
+               OpStore %3 %22
+               OpReturn
+               OpFunctionEnd
+    )";
+  std::unique_ptr<ir::IRContext> context =
+      BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, source,
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+  ir::Module* module = context->module();
+  EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
+                             << source << std::endl;
+  ir::Function* f = &*module->begin();
+  opt::LivenessAnalysis* liveness_analysis = context->GetLivenessAnalysis();
+  const opt::RegisterLiveness* register_liveness = liveness_analysis->Get(f);
+  ir::LoopDescriptor& ld = *context->GetLoopDescriptor(f);
+  opt::analysis::DefUseManager& def_use_mgr = *context->get_def_use_mgr();
+
+  {
+    opt::RegisterLiveness::RegionRegisterLiveness l1_sim_resut;
+    opt::RegisterLiveness::RegionRegisterLiveness l2_sim_resut;
+    std::unordered_set<ir::Instruction*> moved_instructions{
+        def_use_mgr.GetDef(29), def_use_mgr.GetDef(30), def_use_mgr.GetDef(31),
+        def_use_mgr.GetDef(31)->NextNode()};
+    std::unordered_set<ir::Instruction*> copied_instructions{
+        def_use_mgr.GetDef(22), def_use_mgr.GetDef(27),
+        def_use_mgr.GetDef(27)->NextNode(), def_use_mgr.GetDef(23)};
+
+    register_liveness->SimulateFission(*ld[21], moved_instructions,
+                                       copied_instructions, &l1_sim_resut,
+                                       &l2_sim_resut);
+    {
+      SCOPED_TRACE("L1 simulation");
+      std::unordered_set<uint32_t> live_in{
+          3,   // %3 = OpVariable %9 Function
+          4,   // %4 = OpVariable %17 Function
+          5,   // %5 = OpVariable %17 Function
+          22,  // %22 = OpPhi %8 %10 %20 %23 %24
+      };
+      CompareSets(l1_sim_resut.live_in_, live_in);
+
+      std::unordered_set<uint32_t> live_out{
+          3,   // %3 = OpVariable %9 Function
+          4,   // %4 = OpVariable %17 Function
+          5,   // %5 = OpVariable %17 Function
+          22,  // %22 = OpPhi %8 %10 %20 %23 %24
+      };
+      CompareSets(l1_sim_resut.live_out_, live_out);
+
+      EXPECT_EQ(l1_sim_resut.used_registers_, 6u);
+    }
+    {
+      SCOPED_TRACE("L2 simulation");
+      std::unordered_set<uint32_t> live_in{
+          3,   // %3 = OpVariable %9 Function
+          4,   // %4 = OpVariable %17 Function
+          5,   // %5 = OpVariable %17 Function
+          22,  // %22 = OpPhi %8 %10 %20 %23 %24
+      };
+      CompareSets(l2_sim_resut.live_in_, live_in);
+
+      std::unordered_set<uint32_t> live_out{
+          3,   // %3 = OpVariable %9 Function
+          22,  // %22 = OpPhi %8 %10 %20 %23 %24
+      };
+      CompareSets(l2_sim_resut.live_out_, live_out);
+
+      EXPECT_EQ(l2_sim_resut.used_registers_, 6u);
+    }
+  }
+}
+}  // namespace