diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index ea0cacc..9018fee 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -455,6 +455,9 @@
 #define DECLARE_INSTRUCTION(type)                          \
   virtual const char* DebugName() const { return #type; }  \
   virtual H##type* As##type() { return this; }             \
+  virtual bool InstructionTypeEquals(HInstruction* other) const {     \
+    return other->Is##type();                              \
+  }                                                        \
   virtual void Accept(HGraphVisitor* visitor)              \
 
 template <typename T>
@@ -477,9 +480,42 @@
   DISALLOW_COPY_AND_ASSIGN(HUseListNode);
 };
 
+// Represents the side effects an instruction may have.
+class SideEffects : public ValueObject {
+ public:
+  static SideEffects None() {
+    return SideEffects(0);
+  }
+
+  static SideEffects All() {
+    return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_);
+  }
+
+  static SideEffects ChangesSomething() {
+    return SideEffects((1 << kFlagChangesCount) - 1);
+  }
+
+  static SideEffects DependsOnSomething() {
+    int count = kFlagDependsOnCount - kFlagChangesCount;
+    return SideEffects(((1 << count) - 1) << kFlagChangesCount);
+  }
+
+ private:
+  static constexpr int kFlagChangesSomething = 0;
+  static constexpr int kFlagChangesCount = kFlagChangesSomething + 1;
+
+  static constexpr int kFlagDependsOnSomething = kFlagChangesCount;
+  static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1;
+
+ private:
+  explicit SideEffects(size_t flags) : flags_(flags) {}
+
+  const size_t flags_;
+};
+
 class HInstruction : public ArenaObject {
  public:
-  HInstruction()
+  explicit HInstruction(SideEffects side_effects)
       : previous_(nullptr),
         next_(nullptr),
         block_(nullptr),
@@ -490,7 +526,8 @@
         environment_(nullptr),
         locations_(nullptr),
         live_interval_(nullptr),
-        lifetime_position_(kNoLifetime) {}
+        lifetime_position_(kNoLifetime),
+        side_effects_(side_effects) {}
 
   virtual ~HInstruction() {}
 
@@ -574,6 +611,22 @@
   FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
 #undef INSTRUCTION_TYPE_CHECK
 
+  // Returns whether the instruction can be moved within the graph.
+  virtual bool CanBeMoved() const { return false; }
+
+  // Returns whether the two instructions are of the same kind.
+  virtual bool InstructionTypeEquals(HInstruction* other) const { return false; }
+
+  // Returns whether any data encoded in the two instructions is equal.
+  // This method does not look at the inputs. Both instructions must be
+  // of the same type, otherwise the method has undefined behavior.
+  virtual bool InstructionDataEquals(HInstruction* other) const { return false; }
+
+  // Returns whether two instructions are equal, that is:
+  // 1) They have the same type and contain the same data,
+  // 2) Their inputs are identical.
+  bool Equals(HInstruction* other) const;
+
   size_t GetLifetimePosition() const { return lifetime_position_; }
   void SetLifetimePosition(size_t position) { lifetime_position_ = position; }
   LiveInterval* GetLiveInterval() const { return live_interval_; }
@@ -613,6 +666,8 @@
   // order of blocks where this instruction's live interval start.
   size_t lifetime_position_;
 
+  const SideEffects side_effects_;
+
   friend class HBasicBlock;
   friend class HInstructionList;
 
@@ -789,7 +844,8 @@
 template<intptr_t N>
 class HTemplateInstruction: public HInstruction {
  public:
-  HTemplateInstruction<N>() : inputs_() {}
+  HTemplateInstruction<N>(SideEffects side_effects)
+      : HInstruction(side_effects), inputs_() {}
   virtual ~HTemplateInstruction() {}
 
   virtual size_t InputCount() const { return N; }
@@ -807,9 +863,10 @@
 };
 
 template<intptr_t N>
-class HExpression: public HTemplateInstruction<N> {
+class HExpression : public HTemplateInstruction<N> {
  public:
-  explicit HExpression<N>(Primitive::Type type) : type_(type) {}
+  HExpression<N>(Primitive::Type type, SideEffects side_effects)
+      : HTemplateInstruction<N>(side_effects), type_(type) {}
   virtual ~HExpression() {}
 
   virtual Primitive::Type GetType() const { return type_; }
@@ -822,7 +879,7 @@
 // instruction that branches to the exit block.
 class HReturnVoid : public HTemplateInstruction<0> {
  public:
-  HReturnVoid() {}
+  HReturnVoid() : HTemplateInstruction(SideEffects::None()) {}
 
   virtual bool IsControlFlow() const { return true; }
 
@@ -836,7 +893,7 @@
 // instruction that branches to the exit block.
 class HReturn : public HTemplateInstruction<1> {
  public:
-  explicit HReturn(HInstruction* value) {
+  explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) {
     SetRawInputAt(0, value);
   }
 
@@ -853,7 +910,7 @@
 // exit block.
 class HExit : public HTemplateInstruction<0> {
  public:
-  HExit() {}
+  HExit() : HTemplateInstruction(SideEffects::None()) {}
 
   virtual bool IsControlFlow() const { return true; }
 
@@ -866,14 +923,14 @@
 // Jumps from one block to another.
 class HGoto : public HTemplateInstruction<0> {
  public:
-  HGoto() {}
+  HGoto() : HTemplateInstruction(SideEffects::None()) {}
+
+  virtual bool IsControlFlow() const { return true; }
 
   HBasicBlock* GetSuccessor() const {
     return GetBlock()->GetSuccessors().Get(0);
   }
 
-  virtual bool IsControlFlow() const { return true; }
-
   DECLARE_INSTRUCTION(Goto);
 
  private:
@@ -885,10 +942,12 @@
 // two successors.
 class HIf : public HTemplateInstruction<1> {
  public:
-  explicit HIf(HInstruction* input) {
+  explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) {
     SetRawInputAt(0, input);
   }
 
+  virtual bool IsControlFlow() const { return true; }
+
   HBasicBlock* IfTrueSuccessor() const {
     return GetBlock()->GetSuccessors().Get(0);
   }
@@ -897,8 +956,6 @@
     return GetBlock()->GetSuccessors().Get(1);
   }
 
-  virtual bool IsControlFlow() const { return true; }
-
   DECLARE_INSTRUCTION(If);
 
   virtual bool IsIfInstruction() const { return true; }
@@ -911,7 +968,7 @@
  public:
   HBinaryOperation(Primitive::Type result_type,
                    HInstruction* left,
-                   HInstruction* right) : HExpression(result_type) {
+                   HInstruction* right) : HExpression(result_type, SideEffects::None()) {
     SetRawInputAt(0, left);
     SetRawInputAt(1, right);
   }
@@ -922,6 +979,9 @@
 
   virtual bool IsCommutative() { return false; }
 
+  virtual bool CanBeMoved() const { return true; }
+  virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
  private:
   DISALLOW_COPY_AND_ASSIGN(HBinaryOperation);
 };
@@ -1053,7 +1113,8 @@
 // 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)
+      : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {}
 
   DECLARE_INSTRUCTION(Local);
 
@@ -1069,7 +1130,8 @@
 // Load a given local. The local is an input of this instruction.
 class HLoadLocal : public HExpression<1> {
  public:
-  explicit HLoadLocal(HLocal* local, Primitive::Type type) : HExpression(type) {
+  explicit HLoadLocal(HLocal* local, Primitive::Type type)
+      : HExpression(type, SideEffects::None()) {
     SetRawInputAt(0, local);
   }
 
@@ -1085,7 +1147,7 @@
 // and the local.
 class HStoreLocal : public HTemplateInstruction<2> {
  public:
-  HStoreLocal(HLocal* local, HInstruction* value) {
+  HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) {
     SetRawInputAt(0, local);
     SetRawInputAt(1, value);
   }
@@ -1100,7 +1162,9 @@
 
 class HConstant : public HExpression<0> {
  public:
-  explicit HConstant(Primitive::Type type) : HExpression(type) {}
+  explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {}
+
+  virtual bool CanBeMoved() const { return true; }
 
   DECLARE_INSTRUCTION(Constant);
 
@@ -1116,6 +1180,10 @@
 
   int32_t GetValue() const { return value_; }
 
+  virtual bool InstructionDataEquals(HInstruction* other) const {
+    return other->AsIntConstant()->value_ == value_;
+  }
+
   DECLARE_INSTRUCTION(IntConstant);
 
  private:
@@ -1130,6 +1198,10 @@
 
   int64_t GetValue() const { return value_; }
 
+  virtual bool InstructionDataEquals(HInstruction* other) const {
+    return other->AsLongConstant()->value_ == value_;
+  }
+
   DECLARE_INSTRUCTION(LongConstant);
 
  private:
@@ -1144,7 +1216,8 @@
           uint32_t number_of_arguments,
           Primitive::Type return_type,
           uint32_t dex_pc)
-    : inputs_(arena, number_of_arguments),
+    : HInstruction(SideEffects::All()),
+      inputs_(arena, number_of_arguments),
       return_type_(return_type),
       dex_pc_(dex_pc) {
     inputs_.SetSize(number_of_arguments);
@@ -1200,8 +1273,10 @@
 
 class HNewInstance : public HExpression<0> {
  public:
-  HNewInstance(uint32_t dex_pc, uint16_t type_index) : HExpression(Primitive::kPrimNot),
-    dex_pc_(dex_pc), type_index_(type_index) {}
+  HNewInstance(uint32_t dex_pc, uint16_t type_index)
+      : HExpression(Primitive::kPrimNot, SideEffects::None()),
+        dex_pc_(dex_pc),
+        type_index_(type_index) {}
 
   uint32_t GetDexPc() const { return dex_pc_; }
   uint16_t GetTypeIndex() const { return type_index_; }
@@ -1249,7 +1324,7 @@
 class HParameterValue : public HExpression<0> {
  public:
   HParameterValue(uint8_t index, Primitive::Type parameter_type)
-      : HExpression(parameter_type), index_(index) {}
+      : HExpression(parameter_type, SideEffects::None()), index_(index) {}
 
   uint8_t GetIndex() const { return index_; }
 
@@ -1265,10 +1340,13 @@
 
 class HNot : public HExpression<1> {
  public:
-  explicit HNot(HInstruction* input) : HExpression(Primitive::kPrimBoolean) {
+  explicit HNot(HInstruction* input) : HExpression(Primitive::kPrimBoolean, SideEffects::None()) {
     SetRawInputAt(0, input);
   }
 
+  virtual bool CanBeMoved() const { return true; }
+  virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
   DECLARE_INSTRUCTION(Not);
 
  private:
@@ -1278,7 +1356,8 @@
 class HPhi : public HInstruction {
  public:
   HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type)
-      : inputs_(arena, number_of_inputs),
+      : HInstruction(SideEffects::None()),
+        inputs_(arena, number_of_inputs),
         reg_number_(reg_number),
         type_(type),
         is_live_(false) {
@@ -1318,10 +1397,13 @@
 class HNullCheck : public HExpression<1> {
  public:
   HNullCheck(HInstruction* value, uint32_t dex_pc)
-      : HExpression(value->GetType()), dex_pc_(dex_pc) {
+      : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
     SetRawInputAt(0, value);
   }
 
+  virtual bool CanBeMoved() const { return true; }
+  virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
   virtual bool NeedsEnvironment() const { return true; }
 
   uint32_t GetDexPc() const { return dex_pc_; }
@@ -1352,10 +1434,17 @@
   HInstanceFieldGet(HInstruction* value,
                     Primitive::Type field_type,
                     MemberOffset field_offset)
-      : HExpression(field_type), field_info_(field_offset, field_type) {
+      : HExpression(field_type, SideEffects::DependsOnSomething()),
+        field_info_(field_offset, field_type) {
     SetRawInputAt(0, value);
   }
 
+  virtual bool CanBeMoved() const { return true; }
+  virtual bool InstructionDataEquals(HInstruction* other) const {
+    size_t other_offset = other->AsInstanceFieldGet()->GetFieldOffset().SizeValue();
+    return other_offset == GetFieldOffset().SizeValue();
+  }
+
   MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
   Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
 
@@ -1373,7 +1462,8 @@
                     HInstruction* value,
                     Primitive::Type field_type,
                     MemberOffset field_offset)
-      : field_info_(field_offset, field_type) {
+      : HTemplateInstruction(SideEffects::ChangesSomething()),
+        field_info_(field_offset, field_type) {
     SetRawInputAt(0, object);
     SetRawInputAt(1, value);
   }
@@ -1392,11 +1482,14 @@
 class HArrayGet : public HExpression<2> {
  public:
   HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type)
-      : HExpression(type) {
+      : HExpression(type, SideEffects::DependsOnSomething()) {
     SetRawInputAt(0, array);
     SetRawInputAt(1, index);
   }
 
+  virtual bool CanBeMoved() const { return true; }
+  virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
   DECLARE_INSTRUCTION(ArrayGet);
 
  private:
@@ -1409,7 +1502,10 @@
             HInstruction* index,
             HInstruction* value,
             Primitive::Type component_type,
-            uint32_t dex_pc) : dex_pc_(dex_pc), component_type_(component_type) {
+            uint32_t dex_pc)
+      : HTemplateInstruction(SideEffects::ChangesSomething()),
+        dex_pc_(dex_pc),
+        component_type_(component_type) {
     SetRawInputAt(0, array);
     SetRawInputAt(1, index);
     SetRawInputAt(2, value);
@@ -1436,10 +1532,16 @@
 
 class HArrayLength : public HExpression<1> {
  public:
-  explicit HArrayLength(HInstruction* array) : HExpression(Primitive::kPrimInt) {
+  explicit HArrayLength(HInstruction* array)
+      : HExpression(Primitive::kPrimInt, SideEffects::None()) {
+    // Note that arrays do not change length, so the instruction does not
+    // depend on any write.
     SetRawInputAt(0, array);
   }
 
+  virtual bool CanBeMoved() const { return true; }
+  virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
   DECLARE_INSTRUCTION(ArrayLength);
 
  private:
@@ -1449,12 +1551,15 @@
 class HBoundsCheck : public HExpression<2> {
  public:
   HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc)
-      : HExpression(index->GetType()), dex_pc_(dex_pc) {
+      : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
     DCHECK(index->GetType() == Primitive::kPrimInt);
     SetRawInputAt(0, index);
     SetRawInputAt(1, length);
   }
 
+  virtual bool CanBeMoved() const { return true; }
+  virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
   virtual bool NeedsEnvironment() const { return true; }
 
   uint32_t GetDexPc() const { return dex_pc_; }
@@ -1476,7 +1581,7 @@
  */
 class HTemporary : public HTemplateInstruction<0> {
  public:
-  explicit HTemporary(size_t index) : index_(index) {}
+  explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {}
 
   size_t GetIndex() const { return index_; }
 
@@ -1550,7 +1655,8 @@
 
 class HParallelMove : public HTemplateInstruction<0> {
  public:
-  explicit HParallelMove(ArenaAllocator* arena) : moves_(arena, kDefaultNumberOfMoves) {}
+  explicit HParallelMove(ArenaAllocator* arena)
+      : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {}
 
   void AddMove(MoveOperands* move) {
     moves_.Add(move);