Simple array bounds check elimination on top of range analysis framework.

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 1565 matching lines @@
 class RangeBoundary : public ValueObject {
  public:
   enum Kind { kUnknown, kSymbol, kConstant };
 
   RangeBoundary() : kind_(kUnknown), value_(0), offset_(0) { }
 
   static RangeBoundary FromConstant(intptr_t val) {
     return RangeBoundary(kConstant, val, 0);
   }
 
-  static RangeBoundary FromDefinition(Definition* defn, intptr_t offs = 0) {
-    return RangeBoundary(kSymbol, reinterpret_cast<intptr_t>(defn), offs);
-  }
+  static RangeBoundary FromDefinition(Definition* defn, intptr_t offs = 0);
 
   static RangeBoundary MinSmi() {
     return FromConstant(Smi::kMinValue);
   }
 
   static RangeBoundary MaxSmi() {
     return FromConstant(Smi::kMaxValue);
   }
 
   static const intptr_t kMinusInfinity = Smi::kMinValue - 1;
   static const intptr_t kPlusInfinity = Smi::kMaxValue + 1;
 
   static RangeBoundary OverflowedMinSmi() {
     return FromConstant(Smi::kMinValue - 1);
   }
 
   static RangeBoundary OverflowedMaxSmi() {
     return FromConstant(Smi::kMaxValue + 1);
   }
 
-  static RangeBoundary Min(RangeBoundary a, RangeBoundary b) {
-    const intptr_t min_a = a.LowerBound().value();
-    const intptr_t min_b = b.LowerBound().value();
+  static RangeBoundary Min(RangeBoundary a, RangeBoundary b);
 
-    return RangeBoundary::FromConstant(Utils::Minimum(min_a, min_b));
-  }
-
-  static RangeBoundary Max(RangeBoundary a, RangeBoundary b) {
-    const intptr_t max_a = a.UpperBound().value();
-    const intptr_t max_b = b.UpperBound().value();
-
-    return RangeBoundary::FromConstant(Utils::Maximum(max_a, max_b));
-  }
+  static RangeBoundary Max(RangeBoundary a, RangeBoundary b);
 
   bool Overflowed() const {
     return !Smi::IsValid(value());
   }
 
   RangeBoundary Clamp() const {
     if (IsConstant()) {
       if (value() < Smi::kMinValue) return MinSmi();
       if (value() > Smi::kMaxValue) return MaxSmi();
     }
     return *this;
   }
 
   bool Equals(const RangeBoundary& other) const {
     return (kind_ == other.kind_) && (value_ == other.value_);
   }
 
   bool IsUnknown() const { return kind_ == kUnknown; }
   bool IsConstant() const { return kind_ == kConstant; }
   bool IsSymbol() const { return kind_ == kSymbol; }

[srdjan, 2012/10/25 20:51:36]

IsSymbol  is a pretty widely used operation on class String. I would use a
different name to make it more readable ( reading the call sites, I thought we
were dealing with Strings). Ditto for IsConstant.

[Vyacheslav Egorov (Google), 2012/10/26 14:23:29]

I am not sure how to rename it. I agree that it is unfortunate that symbol and
constant have a lot of different meanings. However it is used in a very limited
scope (range analysis) where it has a well defined meaning, just like "symbolic
computations" have a well defined meaning that has nothing to do with strings.

I am open to suggestions and will rename if we manage to come up with something
that is recognizable.

 
   intptr_t value() const {
     ASSERT(IsConstant());
     return value_;
   }
 
   Definition* symbol() const {
     ASSERT(IsSymbol());
     return reinterpret_cast<Definition*>(value_);
   }
 
+  intptr_t offset() const {
+    return offset_;
+  }
+
   RangeBoundary LowerBound() const;
   RangeBoundary UpperBound() const;
 
   void PrintTo(BufferFormatter* f) const;
+  const char* ToCString() const;
 
   static RangeBoundary Add(const RangeBoundary& a,
                            const RangeBoundary& b,
                            const RangeBoundary& overflow) {
     ASSERT(a.IsConstant() && b.IsConstant());
 
     intptr_t result = a.value() + b.value();
     if (!Smi::IsValid(result)) {
       return overflow;
     }
@@ skipping 1274 matching lines @@
 
 class LoadFieldInstr : public TemplateDefinition<1> {
  public:
   LoadFieldInstr(Value* value,
                  intptr_t offset_in_bytes,
                  const AbstractType& type,
                  bool immutable = false)
       : offset_in_bytes_(offset_in_bytes),
         type_(type),
         result_cid_(kDynamicCid),
-        immutable_(immutable) {
+        immutable_(immutable),
+        recognized_kind_(MethodRecognizer::kUnknown) {
     ASSERT(value != NULL);
     ASSERT(type.IsZoneHandle());  // May be null if field is not an instance.
     inputs_[0] = value;
   }
 
   DECLARE_INSTRUCTION(LoadField)
   virtual RawAbstractType* CompileType() const;
 
   Value* value() const { return inputs_[0]; }
   intptr_t offset_in_bytes() const { return offset_in_bytes_; }
   const AbstractType& type() const { return type_; }
   void set_result_cid(intptr_t value) { result_cid_ = value; }
 
   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(Instruction* other) const;
 
   virtual bool AffectedBySideEffect() const { return !immutable_; }
 
+  virtual void InferRange();
+
+  void set_recognized_kind(MethodRecognizer::Kind kind) {
+    recognized_kind_ = kind;
+  }
+
+  MethodRecognizer::Kind recognized_kind() const {
+    return recognized_kind_;
+  }
+
  private:
   const intptr_t offset_in_bytes_;
   const AbstractType& type_;
   intptr_t result_cid_;
   const bool immutable_;
 
+  MethodRecognizer::Kind recognized_kind_;
+
   DISALLOW_COPY_AND_ASSIGN(LoadFieldInstr);
 };
 
 
 class StoreVMFieldInstr : public TemplateDefinition<2> {
  public:
   StoreVMFieldInstr(Value* dest,
                     intptr_t offset_in_bytes,
                     Value* value,
                     const AbstractType& type)
@@ skipping 986 matching lines @@
 
   virtual bool AttributesEqual(Instruction* other) const;
 
   virtual bool AffectedBySideEffect() const { return false; }
 
   Value* array() const { return inputs_[0]; }
   Value* index() const { return inputs_[1]; }
 
   intptr_t array_type() const { return array_type_; }
 
+  bool IsRedundant();
+
  private:
   intptr_t array_type_;
 
   DISALLOW_COPY_AND_ASSIGN(CheckArrayBoundInstr);
 };
 
 
 #undef DECLARE_INSTRUCTION
 
 class Environment : public ZoneAllocated {
@@ skipping 201 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_