Implement array bounds checks explicitly in the optimized IL.

runtime/vm/intermediate_language.h

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef VM_INTERMEDIATE_LANGUAGE_H_
 #define VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
@@ skipping 90 matching lines @@
   M(NumberNegate, NumberNegateComp)                                            \
   M(CheckStackOverflow, CheckStackOverflowComp)                                \
   M(DoubleToDouble, DoubleToDoubleComp)                                        \
   M(SmiToDouble, SmiToDoubleComp)                                              \
   M(CheckClass, CheckClassComp)                                                \
   M(CheckSmi, CheckSmiComp)                                                    \
   M(Materialize, MaterializeComp)                                              \
   M(CheckEitherNonSmi, CheckEitherNonSmiComp)                                  \
   M(UnboxedDoubleBinaryOp, UnboxedDoubleBinaryOpComp)                          \
   M(UnboxDouble, UnboxDoubleComp)                                              \
-  M(BoxDouble, BoxDoubleComp)
+  M(BoxDouble, BoxDoubleComp)                                                  \
+  M(CheckArrayBound, CheckArrayBoundComp)
 
 
 #define FORWARD_DECLARATION(ShortName, ClassName) class ClassName;
 FOR_EACH_COMPUTATION(FORWARD_DECLARATION)
 FOR_EACH_VALUE(FORWARD_DECLARATION)
 #undef FORWARD_DECLARATION
 
 // Forward declarations.
 class BindInstr;
 class BranchInstr;
@@ skipping 49 matching lines @@
   // Compares two computations. Returns true, if:
   // 1. They are of the same kind.
   // 2. All input operands match.
   // 3. All other attributes match.
   bool Equals(Computation* other) const;
 
   // Returns a hash code for use with hash maps.
   virtual intptr_t Hashcode() const;
 
   // Compare attributes of an computation (except input operands and kind).
-  // TODO(fschneider): Make this abstract and implement for all computations.
-  virtual bool AttributesEqual(Computation* other) const { return true; }
+  // All computations that participate in CSE have to override this function.
+  virtual bool AttributesEqual(Computation* other) const {
+    UNREACHABLE();
+    return false;
+  }
 
   // Returns true if the instruction may have side effects.
   // TODO(fschneider): Make this abstract and implement for all computations
   // instead of returning the safe default (true).
   virtual bool HasSideEffect() const { return true; }
 
   // Compile time type of the computation, which typically depends on the
   // compile time types (and possibly propagated types) of its inputs.
   virtual RawAbstractType* CompileType() const = 0;
   virtual intptr_t ResultCid() const = 0;
@@ skipping 943 matching lines @@
   const Field& field_;
 
   DISALLOW_COPY_AND_ASSIGN(StoreStaticFieldComp);
 };
 
 
 class LoadIndexedComp : public TemplateComputation<2> {
  public:
   LoadIndexedComp(Value* array,
                   Value* index,
-                  intptr_t receiver_type,
-                  InstanceCallComp* original)
-      : receiver_type_(receiver_type),
-        original_(original) {
+                  intptr_t receiver_type)
+      : receiver_type_(receiver_type) {
     ASSERT(array != NULL);
     ASSERT(index != NULL);
     inputs_[0] = array;
     inputs_[1] = index;
   }
 
   DECLARE_COMPUTATION(LoadIndexed)
 
   Value* array() const { return inputs_[0]; }
   Value* index() const { return inputs_[1]; }
 
   intptr_t receiver_type() const { return receiver_type_; }
 
-  InstanceCallComp* original() const { return original_; }
-
-  virtual bool CanDeoptimize() const { return true; }
+  virtual bool CanDeoptimize() const { return false; }
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
   intptr_t receiver_type_;
-  InstanceCallComp* original_;
 
   DISALLOW_COPY_AND_ASSIGN(LoadIndexedComp);
 };
 
 
 class StoreIndexedComp : public TemplateComputation<3> {
  public:
   StoreIndexedComp(Value* array,
                    Value* index,
                    Value* value,
-                   intptr_t receiver_type,
-                   InstanceCallComp* original)
-        : receiver_type_(receiver_type),
-          original_(original) {
+                   intptr_t receiver_type)
+        : receiver_type_(receiver_type) {
     ASSERT(array != NULL);
     ASSERT(index != NULL);
     ASSERT(value != NULL);
     inputs_[0] = array;
     inputs_[1] = index;
     inputs_[2] = value;
   }
 
   DECLARE_COMPUTATION(StoreIndexed)
 
   Value* array() const { return inputs_[0]; }
   Value* index() const { return inputs_[1]; }
   Value* value() const { return inputs_[2]; }
 
-  InstanceCallComp* original() const { return original_; }
-
   intptr_t receiver_type() const { return receiver_type_; }
 
-  virtual bool CanDeoptimize() const { return true; }
+  virtual bool CanDeoptimize() const { return false; }
   virtual intptr_t ResultCid() const { return kDynamicCid; }
 
  private:
   intptr_t receiver_type_;
-  InstanceCallComp* original_;
 
   DISALLOW_COPY_AND_ASSIGN(StoreIndexedComp);
 };
 
 
 // Note overrideable, built-in: value? false : true.
 class BooleanNegateComp : public TemplateComputation<1> {
  public:
   explicit BooleanNegateComp(Value* value) {
     ASSERT(value != NULL);
@@ skipping 497 matching lines @@
     ASSERT(right != NULL);
     inputs_[0] = left;
     inputs_[1] = right;
   }
 
   DECLARE_COMPUTATION(CheckEitherNonSmi)
 
   virtual bool CanDeoptimize() const { return true; }
   virtual intptr_t ResultCid() const { return kIllegalCid; }
 
+  virtual bool AttributesEqual(Computation* other) const { return true; }
+
   virtual bool HasSideEffect() const { return false; }
 
   Value* left() const { return inputs_[0]; }
 
   Value* right() const { return inputs_[1]; }
 
   virtual Definition* TryReplace(BindInstr* instr) const;
 
  private:
   InstanceCallComp* instance_call_;
@@ skipping 372 matching lines @@
   intptr_t deopt_id() const { return original_->deopt_id(); }
   intptr_t try_index() const { return original_->try_index(); }
 
  private:
   InstanceCallComp* original_;
 
   DISALLOW_COPY_AND_ASSIGN(CheckSmiComp);
 };
 
 
+class CheckArrayBoundComp : public TemplateComputation<2> {
+ public:
+  CheckArrayBoundComp(Value* array,
+                      Value* index,
+                      intptr_t array_type,
+                      InstanceCallComp* original)
+      : array_type_(array_type), original_(original) {
+    ASSERT(array != NULL);
+    ASSERT(index != NULL);
+    inputs_[0] = array;
+    inputs_[1] = index;
+  }
+
+  DECLARE_COMPUTATION(CheckArrayBound)
+
+  virtual bool CanDeoptimize() const { return true; }
+  virtual intptr_t ResultCid() const { return kIllegalCid; }
+
+  virtual bool AttributesEqual(Computation* other) const;
+
+  virtual bool HasSideEffect() const { return false; }
+
+  Value* array() const { return inputs_[0]; }
+  Value* index() const { return inputs_[1]; }
+
+  intptr_t array_type() const { return array_type_; }
+
+  intptr_t deopt_id() const { return original_->deopt_id(); }
+  intptr_t try_index() const { return original_->try_index(); }
+
+ private:
+  intptr_t array_type_;
+  InstanceCallComp* original_;
+
+  DISALLOW_COPY_AND_ASSIGN(CheckArrayBoundComp);
+};
+
+
 #undef DECLARE_COMPUTATION
 
 
 // Implementation of type testers and cast functins.
 #define DEFINE_COMPUTATION_PREDICATE(ShortName, ClassName)                     \
 bool Computation::Is##ShortName() const {                                      \
   return computation_kind() == k##ShortName;                                   \
 }                                                                              \
 const ClassName* Computation::As##ShortName() const {                          \
   if (!Is##ShortName()) return NULL;                                           \
@@ skipping 1262 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_