diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 143d5c9..503f31d 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -38,6 +38,15 @@
 static const int kDefaultNumberOfPredecessors = 2;
 static const int kDefaultNumberOfBackEdges = 1;
 
+enum IfCondition {
+  kCondEQ,
+  kCondNE,
+  kCondLT,
+  kCondLE,
+  kCondGT,
+  kCondGE,
+};
+
 class HInstructionList {
  public:
   HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {}
@@ -66,7 +75,7 @@
         maximum_number_of_out_vregs_(0),
         number_of_vregs_(0),
         number_of_in_vregs_(0),
-        current_instruction_id_(0) { }
+        current_instruction_id_(0) {}
 
   ArenaAllocator* GetArena() const { return arena_; }
   const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; }
@@ -381,7 +390,13 @@
 
 #define FOR_EACH_INSTRUCTION(M)                            \
   M(Add)                                                   \
+  M(Condition)                                             \
   M(Equal)                                                 \
+  M(NotEqual)                                              \
+  M(LessThan)                                              \
+  M(LessThanOrEqual)                                       \
+  M(GreaterThan)                                           \
+  M(GreaterThanOrEqual)                                    \
   M(Exit)                                                  \
   M(Goto)                                                  \
   M(If)                                                    \
@@ -400,6 +415,7 @@
   M(StoreLocal)                                            \
   M(Sub)                                                   \
 
+
 #define FORWARD_DECLARATION(type) class H##type;
 FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
 #undef FORWARD_DECLARATION
@@ -413,7 +429,7 @@
 class HUseListNode : public ArenaObject {
  public:
   HUseListNode(T* user, size_t index, HUseListNode* tail)
-      : user_(user), index_(index), tail_(tail) { }
+      : user_(user), index_(index), tail_(tail) {}
 
   HUseListNode* GetTail() const { return tail_; }
   T* GetUser() const { return user_; }
@@ -444,7 +460,7 @@
         live_interval_(nullptr),
         lifetime_position_(kNoLifetime) {}
 
-  virtual ~HInstruction() { }
+  virtual ~HInstruction() {}
 
   HInstruction* GetNext() const { return next_; }
   HInstruction* GetPrevious() const { return previous_; }
@@ -507,6 +523,10 @@
 
   void ReplaceWith(HInstruction* instruction);
 
+  bool HasOnlyOneUse() const {
+    return uses_ != nullptr && uses_->GetTail() == nullptr;
+  }
+
 #define INSTRUCTION_TYPE_CHECK(type)                                           \
   bool Is##type() { return (As##type() != nullptr); }                          \
   virtual H##type* As##type() { return nullptr; }
@@ -616,7 +636,7 @@
 
 class HInputIterator : public ValueObject {
  public:
-  explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) { }
+  explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {}
 
   bool Done() const { return index_ == instruction_->InputCount(); }
   HInstruction* Current() const { return instruction_->InputAt(index_); }
@@ -676,7 +696,7 @@
 template<typename T, intptr_t N>
 class EmbeddedArray {
  public:
-  EmbeddedArray() : elements_() { }
+  EmbeddedArray() : elements_() {}
 
   intptr_t GetLength() const { return N; }
 
@@ -721,8 +741,8 @@
 template<intptr_t N>
 class HTemplateInstruction: public HInstruction {
  public:
-  HTemplateInstruction<N>() : inputs_() { }
-  virtual ~HTemplateInstruction() { }
+  HTemplateInstruction<N>() : inputs_() {}
+  virtual ~HTemplateInstruction() {}
 
   virtual size_t InputCount() const { return N; }
   virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; }
@@ -738,6 +758,18 @@
   friend class SsaBuilder;
 };
 
+template<intptr_t N>
+class HExpression: public HTemplateInstruction<N> {
+ public:
+  explicit HExpression<N>(Primitive::Type type) : type_(type) {}
+  virtual ~HExpression() {}
+
+  virtual Primitive::Type GetType() const { return type_; }
+
+ private:
+  const Primitive::Type type_;
+};
+
 // Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow
 // instruction that branches to the exit block.
 class HReturnVoid : public HTemplateInstruction<0> {
@@ -800,6 +832,7 @@
   DISALLOW_COPY_AND_ASSIGN(HGoto);
 };
 
+
 // Conditional branch. A block ending with an HIf instruction must have
 // two successors.
 class HIf : public HTemplateInstruction<1> {
@@ -820,53 +853,143 @@
 
   DECLARE_INSTRUCTION(If);
 
+  virtual bool IsIfInstruction() const { return true; }
+
  private:
   DISALLOW_COPY_AND_ASSIGN(HIf);
 };
 
-class HBinaryOperation : public HTemplateInstruction<2> {
+class HBinaryOperation : public HExpression<2> {
  public:
   HBinaryOperation(Primitive::Type result_type,
                    HInstruction* left,
-                   HInstruction* right) : result_type_(result_type) {
+                   HInstruction* right) : HExpression(result_type) {
     SetRawInputAt(0, left);
     SetRawInputAt(1, right);
   }
 
   HInstruction* GetLeft() const { return InputAt(0); }
   HInstruction* GetRight() const { return InputAt(1); }
-  Primitive::Type GetResultType() const { return result_type_; }
+  Primitive::Type GetResultType() const { return GetType(); }
 
   virtual bool IsCommutative() { return false; }
-  virtual Primitive::Type GetType() const { return GetResultType(); }
 
  private:
-  const Primitive::Type result_type_;
-
   DISALLOW_COPY_AND_ASSIGN(HBinaryOperation);
 };
 
-
-// Instruction to check if two inputs are equal to each other.
-class HEqual : public HBinaryOperation {
+class HCondition : public HBinaryOperation {
  public:
-  HEqual(HInstruction* first, HInstruction* second)
+  HCondition(HInstruction* first, HInstruction* second)
       : HBinaryOperation(Primitive::kPrimBoolean, first, second) {}
 
   virtual bool IsCommutative() { return true; }
+  bool NeedsMaterialization() const;
 
-  virtual Primitive::Type GetType() const { return Primitive::kPrimBoolean; }
+  DECLARE_INSTRUCTION(Condition);
+
+  virtual IfCondition GetCondition() const = 0;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HCondition);
+};
+
+// Instruction to check if two inputs are equal to each other.
+class HEqual : public HCondition {
+ public:
+  HEqual(HInstruction* first, HInstruction* second)
+      : HCondition(first, second) {}
 
   DECLARE_INSTRUCTION(Equal);
 
+  virtual IfCondition GetCondition() const {
+    return kCondEQ;
+  }
+
  private:
   DISALLOW_COPY_AND_ASSIGN(HEqual);
 };
 
+class HNotEqual : public HCondition {
+ public:
+  HNotEqual(HInstruction* first, HInstruction* second)
+      : HCondition(first, second) {}
+
+  DECLARE_INSTRUCTION(NotEqual);
+
+  virtual IfCondition GetCondition() const {
+    return kCondNE;
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HNotEqual);
+};
+
+class HLessThan : public HCondition {
+ public:
+  HLessThan(HInstruction* first, HInstruction* second)
+      : HCondition(first, second) {}
+
+  DECLARE_INSTRUCTION(LessThan);
+
+  virtual IfCondition GetCondition() const {
+    return kCondLT;
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HLessThan);
+};
+
+class HLessThanOrEqual : public HCondition {
+ public:
+  HLessThanOrEqual(HInstruction* first, HInstruction* second)
+      : HCondition(first, second) {}
+
+  DECLARE_INSTRUCTION(LessThanOrEqual);
+
+  virtual IfCondition GetCondition() const {
+    return kCondLE;
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual);
+};
+
+class HGreaterThan : public HCondition {
+ public:
+  HGreaterThan(HInstruction* first, HInstruction* second)
+      : HCondition(first, second) {}
+
+  DECLARE_INSTRUCTION(GreaterThan);
+
+  virtual IfCondition GetCondition() const {
+    return kCondGT;
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HGreaterThan);
+};
+
+class HGreaterThanOrEqual : public HCondition {
+ public:
+  HGreaterThanOrEqual(HInstruction* first, HInstruction* second)
+      : HCondition(first, second) {}
+
+  DECLARE_INSTRUCTION(GreaterThanOrEqual);
+
+  virtual IfCondition GetCondition() const {
+    return kCondGE;
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual);
+};
+
+
 // A local in the graph. Corresponds to a Dex register.
 class HLocal : public HTemplateInstruction<0> {
  public:
-  explicit HLocal(uint16_t reg_number) : reg_number_(reg_number) { }
+  explicit HLocal(uint16_t reg_number) : reg_number_(reg_number) {}
 
   DECLARE_INSTRUCTION(Local);
 
@@ -880,21 +1003,17 @@
 };
 
 // Load a given local. The local is an input of this instruction.
-class HLoadLocal : public HTemplateInstruction<1> {
+class HLoadLocal : public HExpression<1> {
  public:
-  explicit HLoadLocal(HLocal* local, Primitive::Type type) : type_(type) {
+  explicit HLoadLocal(HLocal* local, Primitive::Type type) : HExpression(type) {
     SetRawInputAt(0, local);
   }
 
-  virtual Primitive::Type GetType() const { return type_; }
-
   HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
 
   DECLARE_INSTRUCTION(LoadLocal);
 
  private:
-  const Primitive::Type type_;
-
   DISALLOW_COPY_AND_ASSIGN(HLoadLocal);
 };
 
@@ -917,12 +1036,11 @@
 
 // Constants of the type int. Those can be from Dex instructions, or
 // synthesized (for example with the if-eqz instruction).
-class HIntConstant : public HTemplateInstruction<0> {
+class HIntConstant : public HExpression<0> {
  public:
-  explicit HIntConstant(int32_t value) : value_(value) { }
+  explicit HIntConstant(int32_t value) : HExpression(Primitive::kPrimInt), value_(value) {}
 
   int32_t GetValue() const { return value_; }
-  virtual Primitive::Type GetType() const { return Primitive::kPrimInt; }
 
   DECLARE_INSTRUCTION(IntConstant);
 
@@ -932,9 +1050,9 @@
   DISALLOW_COPY_AND_ASSIGN(HIntConstant);
 };
 
-class HLongConstant : public HTemplateInstruction<0> {
+class HLongConstant : public HExpression<0> {
  public:
-  explicit HLongConstant(int64_t value) : value_(value) { }
+  explicit HLongConstant(int64_t value) : HExpression(Primitive::kPrimLong), value_(value) {}
 
   int64_t GetValue() const { return value_; }
 
@@ -1008,15 +1126,14 @@
   DISALLOW_COPY_AND_ASSIGN(HInvokeStatic);
 };
 
-class HNewInstance : public HTemplateInstruction<0> {
+class HNewInstance : public HExpression<0> {
  public:
-  HNewInstance(uint32_t dex_pc, uint16_t type_index) : dex_pc_(dex_pc), type_index_(type_index) {}
+  HNewInstance(uint32_t dex_pc, uint16_t type_index) : HExpression(Primitive::kPrimNot),
+    dex_pc_(dex_pc), type_index_(type_index) {}
 
   uint32_t GetDexPc() const { return dex_pc_; }
   uint16_t GetTypeIndex() const { return type_index_; }
 
-  virtual Primitive::Type GetType() const { return Primitive::kPrimNot; }
-
   // Calls runtime so needs an environment.
   virtual bool NeedsEnvironment() const { return true; }
 
@@ -1057,15 +1174,13 @@
 
 // The value of a parameter in this method. Its location depends on
 // the calling convention.
-class HParameterValue : public HTemplateInstruction<0> {
+class HParameterValue : public HExpression<0> {
  public:
   HParameterValue(uint8_t index, Primitive::Type parameter_type)
-      : index_(index), parameter_type_(parameter_type) {}
+      : HExpression(parameter_type), index_(index) {}
 
   uint8_t GetIndex() const { return index_; }
 
-  virtual Primitive::Type GetType() const { return parameter_type_; }
-
   DECLARE_INSTRUCTION(ParameterValue);
 
  private:
@@ -1073,19 +1188,15 @@
   // than HGraph::number_of_in_vregs_;
   const uint8_t index_;
 
-  const Primitive::Type parameter_type_;
-
   DISALLOW_COPY_AND_ASSIGN(HParameterValue);
 };
 
-class HNot : public HTemplateInstruction<1> {
+class HNot : public HExpression<1> {
  public:
-  explicit HNot(HInstruction* input) {
+  explicit HNot(HInstruction* input) : HExpression(Primitive::kPrimBoolean) {
     SetRawInputAt(0, input);
   }
 
-  virtual Primitive::Type GetType() const { return Primitive::kPrimBoolean; }
-
   DECLARE_INSTRUCTION(Not);
 
  private:
@@ -1210,10 +1321,10 @@
 
 class HGraphVisitor : public ValueObject {
  public:
-  explicit HGraphVisitor(HGraph* graph) : graph_(graph) { }
-  virtual ~HGraphVisitor() { }
+  explicit HGraphVisitor(HGraph* graph) : graph_(graph) {}
+  virtual ~HGraphVisitor() {}
 
-  virtual void VisitInstruction(HInstruction* instruction) { }
+  virtual void VisitInstruction(HInstruction* instruction) {}
   virtual void VisitBasicBlock(HBasicBlock* block);
 
   void VisitInsertionOrder();