Simple redundant load elimination.

runtime/vm/intermediate_language.h

Index: runtime/vm/intermediate_language.h
===================================================================
--- runtime/vm/intermediate_language.h	(revision 12420)
+++ runtime/vm/intermediate_language.h	(working copy)
@@ -278,7 +278,8 @@
         lifetime_position_(-1),
         previous_(NULL),
         next_(NULL),
-        env_(NULL) { }
+        env_(NULL),
+        expr_id_(-1) { }
 
   virtual Tag tag() const = 0;
 
@@ -311,6 +312,9 @@
   // Returns true, if this instruction can deoptimize.
   virtual bool CanDeoptimize() const = 0;
 
+  // Returns true if the instruction may have side effects.
+  virtual bool HasSideEffect() const  = 0;
+
   // Visiting support.
   virtual void Accept(FlowGraphVisitor* visitor) = 0;
 
@@ -434,6 +438,10 @@
     return Isolate::kNoDeoptId;
   }
 
+  // Id for instructions used in CSE.
+  intptr_t expr_id() const { return expr_id_; }
+  void set_expr_id(intptr_t expr_id) { expr_id_ = expr_id; }
+
  protected:
   // Fetch deopt id without checking if this computation can deoptimize.
   intptr_t GetDeoptId() const {
@@ -458,6 +466,8 @@
   Instruction* previous_;
   Instruction* next_;
   Environment* env_;
+  intptr_t expr_id_;
+
   DISALLOW_COPY_AND_ASSIGN(Instruction);
 };
 
@@ -557,6 +567,8 @@
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual bool HasSideEffect() const { return false; }
+
   MoveOperands* AddMove(Location dest, Location src) {
     MoveOperands* move = new MoveOperands(dest, src);
     moves_.Add(move);
@@ -659,6 +671,8 @@
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual bool HasSideEffect() const { return false; }
+
   intptr_t try_index() const { return try_index_; }
 
   BitVector* loop_info() const { return loop_info_; }
@@ -1086,6 +1100,8 @@
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual bool HasSideEffect() const { return false; }
+
   // TODO(regis): This helper will be removed once we support type sets.
   RawAbstractType* LeastSpecificInputType() const;
 
@@ -1159,6 +1175,8 @@
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t Hashcode() const {
     UNREACHABLE();
     return 0;
@@ -1224,6 +1242,8 @@
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual bool HasSideEffect() const { return false; }
+
   virtual void PrintOperandsTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
@@ -1252,6 +1272,8 @@
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual bool HasSideEffect() const { return false; }
+
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
@@ -1274,6 +1296,8 @@
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual bool HasSideEffect() const { return true; }
+
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
@@ -1296,6 +1320,8 @@
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual bool HasSideEffect() const { return true; }
+
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
@@ -1323,6 +1349,8 @@
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual bool HasSideEffect() const { return false; }
+
   ParallelMoveInstr* parallel_move() const {
     return parallel_move_;
   }
@@ -1401,6 +1429,8 @@
   void SetInputAt(intptr_t i, Value* value);
   virtual bool CanDeoptimize() const;
 
+  virtual bool HasSideEffect() const;
+
   ComparisonInstr* comparison() const { return comparison_; }
   void set_comparison(ComparisonInstr* value) { comparison_ = value; }
 
@@ -1468,6 +1498,8 @@
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const;
 
   virtual bool AttributesEqual(Definition* other) const;
@@ -1523,6 +1555,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -1561,6 +1596,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kBoolCid; }
 
  private:
@@ -1595,6 +1633,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kBoolCid; }
 
  private:
@@ -1614,6 +1655,9 @@
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -1634,6 +1678,9 @@
   Value* value() const { return inputs_[0]; }
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kIllegalCid; }
 
  private:
@@ -1662,6 +1709,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -1719,6 +1769,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -1761,6 +1814,9 @@
   const ICData& ic_data() const { return ic_data_; }
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
@@ -1824,6 +1880,11 @@
 }
 
 
+inline bool BranchInstr::HasSideEffect() const {
+  return comparison()->HasSideEffect();
+}
+
+
 inline LocationSummary* BranchInstr::locs() {
   if (comparison()->locs_ == NULL) {
     LocationSummary* summary = comparison()->MakeLocationSummary();
@@ -1860,6 +1921,11 @@
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual bool HasSideEffect() const { return false; }
+
+  virtual bool AttributesEqual(Definition* other) const;
+  virtual bool AffectedBySideEffect() const { return false; }
+
   virtual Definition* Canonicalize();
 
   virtual intptr_t ResultCid() const { return kBoolCid; }
@@ -1905,6 +1971,10 @@
     return (receiver_class_id() != kDoubleCid)
         && (receiver_class_id() != kSmiCid);
   }
+  virtual bool HasSideEffect() const {
+    return (receiver_class_id() != kDoubleCid)
+        && (receiver_class_id() != kSmiCid);
+  }
 
   virtual intptr_t ResultCid() const;
 
@@ -1966,6 +2036,10 @@
     return (operands_class_id() != kDoubleCid)
         && (operands_class_id() != kSmiCid);
   }
+  virtual bool HasSideEffect() const {
+    return (operands_class_id() != kDoubleCid)
+        && (operands_class_id() != kSmiCid);
+  }
 
   virtual intptr_t ResultCid() const;
 
@@ -2022,6 +2096,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return result_cid_; }
   void set_result_cid(intptr_t value) { result_cid_ = value; }
 
@@ -2051,6 +2128,12 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const {
+    UNREACHABLE();
+    return false;
+  }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2085,6 +2168,12 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const {
+    UNREACHABLE();
+    return false;
+  }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2126,6 +2215,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2162,6 +2254,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2184,6 +2279,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
   virtual bool AffectedBySideEffect() const { return !field().is_final(); }
@@ -2214,6 +2312,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2239,6 +2340,9 @@
   Value* index() const { return inputs_[1]; }
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2273,6 +2377,9 @@
   }
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2296,6 +2403,9 @@
   Value* value() const { return inputs_[0]; }
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kBoolCid; }
 
  private:
@@ -2337,6 +2447,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kBoolCid; }
 
  private:
@@ -2374,6 +2487,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2405,6 +2521,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2448,6 +2567,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2480,6 +2602,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2516,6 +2641,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return result_cid_; }
 
   virtual bool AttributesEqual(Definition* other) const;
@@ -2557,6 +2685,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2591,6 +2722,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2625,6 +2759,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2655,6 +2792,9 @@
   intptr_t token_pos() const { return ast_node_.token_pos(); }
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2680,6 +2820,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
@@ -2703,6 +2846,9 @@
   Value* context_value() const { return inputs_[0]; }
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kIllegalCid; }
 
  private:
@@ -2725,6 +2871,9 @@
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kIllegalCid; }
 
  private:
@@ -2749,6 +2898,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return true; }
+
   virtual intptr_t ResultCid() const { return kIllegalCid; }
 
  private:
@@ -2775,6 +2927,9 @@
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kIllegalCid; }
 
   virtual bool AttributesEqual(Definition* other) const { return true; }
@@ -2805,6 +2960,9 @@
   intptr_t token_pos() const { return token_pos_; }
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual bool AffectedBySideEffect() const { return false; }
   virtual bool AttributesEqual(Definition* other) const { return true; }
 
@@ -2839,6 +2997,8 @@
     return value()->ResultCid() != kDoubleCid;
   }
 
+  virtual bool HasSideEffect() const { return false; }
+
   // The output is not an instance but when it is boxed it becomes double.
   virtual intptr_t ResultCid() const { return kDoubleCid; }
 
@@ -2868,6 +3028,7 @@
   Value* value() const { return inputs_[0]; }
 
   virtual bool CanDeoptimize() const { return false; }
+
   virtual bool HasSideEffect() const { return false; }
 
   virtual bool AttributesEqual(Definition* other) const {
@@ -2922,6 +3083,9 @@
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual bool AffectedBySideEffect() const { return false; }
 
   virtual bool AttributesEqual(Definition* other) const {
@@ -2986,6 +3150,11 @@
 
   virtual bool CanDeoptimize() const;
 
+  virtual bool HasSideEffect() const { return false; }
+
+  virtual bool AffectedByEffect() const { return false; }
+  virtual bool AttributesEqual(Definition* other) const;
+
   virtual intptr_t ResultCid() const;
 
  private:
@@ -3025,6 +3194,9 @@
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const;
 
  private:
@@ -3058,6 +3230,9 @@
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const { return op_kind() == Token::kNEGATE; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kSmiCid; }
 
  private:
@@ -3087,6 +3262,9 @@
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kDoubleCid; }
 
  private:
@@ -3107,6 +3285,9 @@
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kIllegalCid; }
 
  private:
@@ -3132,6 +3313,9 @@
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kDoubleCid; }
 
  private:
@@ -3154,6 +3338,9 @@
   virtual intptr_t ArgumentCount() const { return 1; }
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kDoubleCid; }
 
  private:
@@ -3178,6 +3365,9 @@
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kIllegalCid; }
 
   virtual bool AttributesEqual(Definition* other) const;
@@ -3212,6 +3402,9 @@
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kIllegalCid; }
 
   virtual bool AttributesEqual(Definition* other) const { return true; }
@@ -3245,6 +3438,9 @@
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const { return true; }
+
+  virtual bool HasSideEffect() const { return false; }
+
   virtual intptr_t ResultCid() const { return kIllegalCid; }
 
   virtual bool AttributesEqual(Definition* other) const;