Extend Range analysis to 64-bit range and mint operations

runtime/vm/intermediate_language.h

 // Copyright (c) 2013, 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 2493 matching lines @@
         value_(other.value_),
         offset_(other.offset_) { }
 
   RangeBoundary& operator=(const RangeBoundary& other) {
     kind_ = other.kind_;
     value_ = other.value_;
     offset_ = other.offset_;
     return *this;
   }
 
+  static const intptr_t kMin = kIntptrMin;
+  static const intptr_t kMax = kIntptrMax;
+
+  // Construct a RangeBoundary for a constant value.
   static RangeBoundary FromConstant(intptr_t val) {
     return RangeBoundary(kConstant, val, 0);
   }
 
+  // Construct a RangeBoundary for -inf.
   static RangeBoundary NegativeInfinity() {
     return RangeBoundary(kNegativeInfinity, 0, 0);
   }
 
+  // Construct a RangeBoundary for +inf.
   static RangeBoundary PositiveInfinity() {
     return RangeBoundary(kPositiveInfinity, 0, 0);
   }
 
+  // Construct a RangeBoundary from a definition and offset.
   static RangeBoundary FromDefinition(Definition* defn, intptr_t offs = 0);
 
+  // Construct a RangeBoundary for the constant MinSmi value.
   static RangeBoundary MinSmi() {
     return FromConstant(Smi::kMinValue);
   }
 
+  // Construct a RangeBoundary for the constant MaxSmi value.
   static RangeBoundary MaxSmi() {
     return FromConstant(Smi::kMaxValue);
   }
 
   static RangeBoundary Min(RangeBoundary a, RangeBoundary b);
 
   static RangeBoundary Max(RangeBoundary a, RangeBoundary b);
 
+  // Returns true when this is a constant that is outside of range or is +/-inf.
   bool Overflowed() const {
-    // If the value is a constant outside of Smi range or infinity.
-    return (IsConstant() && !Smi::IsValid(value())) || IsInfinity();
+    // TODO(johnmccutchan): Support overflow testing to non-smi ranges.
+    return (IsConstant() && !Smi::IsValid(ConstantValue())) || IsInfinity();
   }
 
+  // Clamps this into a representable constant or symbol RangeBoundary.
+  // +/- infinity are clamped to MinSmi/MaxSmi.
   RangeBoundary Clamp() const {
+    // TODO(johnmccutchan): Support clamping to non-smi ranges.
     if (IsNegativeInfinity()) {
       return MinSmi();
-    } else if (IsPositiveInfinity()) {
+    }
+    if (IsPositiveInfinity()) {
       return MaxSmi();
-    } else if (IsConstant()) {
-      if (value() < Smi::kMinValue) return MinSmi();
-      if (value() > Smi::kMaxValue) return MaxSmi();
+    }
+    if (IsConstant()) {
+      if (ConstantValue() < Smi::kMinValue) return MinSmi();
+      if (ConstantValue() > Smi::kMaxValue) return MaxSmi();
     }
     return *this;
   }
 
+  intptr_t kind() const {
+    return kind_;
+  }
+
+  // Kind tests.
   bool IsUnknown() const { return kind_ == kUnknown; }
   bool IsConstant() const { return kind_ == kConstant; }
   bool IsSymbol() const { return kind_ == kSymbol; }
   bool IsNegativeInfinity() const { return kind_ == kNegativeInfinity; }
   bool IsPositiveInfinity() const { return kind_ == kPositiveInfinity; }
   bool IsInfinity() const {
     return IsNegativeInfinity() || IsPositiveInfinity();
   }
-
-  intptr_t value() const {
-    ASSERT(IsConstant());
-    return value_;
+  bool IsConstantOrInfinity() const {
+    return IsConstant() || IsInfinity();
   }
 
+  // Returns the value of a kConstant RangeBoundary.
+  intptr_t ConstantValue() const;
+
+  // Returns the Definition associated with a kSymbol RangeBoundary.
   Definition* symbol() const {
     ASSERT(IsSymbol());
     return reinterpret_cast<Definition*>(value_);
   }
 
+  // Offset from symbol.
   intptr_t offset() const {
     return offset_;
   }
 
+  // Computes the LowerBound of this. Three cases:
+  // IsInfinity() -> NegativeInfinity().
+  // IsConstant() -> value().
+  // IsSymbol() -> lower bound computed from definition + offset.
   RangeBoundary LowerBound() const;
+
+  // Computes the UpperBound of this. Three cases:
+  // IsInfinity() -> PositiveInfinity().
+  // IsConstant() -> value().
+  // IsSymbol() -> upper bound computed from definition + offset.
   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;
-    }
-    return RangeBoundary::FromConstant(result);
-  }
+                           const RangeBoundary& overflow);
 
   static RangeBoundary Sub(const RangeBoundary& a,
                            const RangeBoundary& b,
-                           const RangeBoundary& overflow) {
-    ASSERT(a.IsConstant() && b.IsConstant());
+                           const RangeBoundary& overflow);
 
-    intptr_t result = a.value() - b.value();
-    if (!Smi::IsValid(result)) {
-      return overflow;
-    }
-    return RangeBoundary::FromConstant(result);
-  }
+  // Attempts to calculate a + b when:
+  // a is a symbol and b is a constant OR
+  // a is a constant and b is a symbol
+  // returns true if it succeeds, output is in result.
+  static bool SymbolicAdd(const RangeBoundary& a,
+                          const RangeBoundary& b,
+                          RangeBoundary* result);
+
+  // Attempts to calculate a - b when:
+  // a is a symbol and b is a constant
+  // returns true if it succeeds, output is in result.
+  static bool SymbolicSub(const RangeBoundary& a,
+                          const RangeBoundary& b,
+                          RangeBoundary* result);
+
+  bool Equals(const RangeBoundary& other) const;
+
+
 
  private:
   RangeBoundary(Kind kind, intptr_t value, intptr_t offset)
       : kind_(kind), value_(value), offset_(offset) { }
 
   Kind kind_;
   intptr_t value_;
   intptr_t offset_;
 };
 
@@ skipping 28 matching lines @@
 
   // [0, +inf]
   bool IsPositive() const;
 
   // [-inf, 0)
   bool IsNegative() const;
 
   // [-inf, val].
   bool OnlyLessThanOrEqualTo(intptr_t val) const;
 
+  // [val, +inf].
+  bool OnlyGreaterThanOrEqualTo(intptr_t val) const;
+
   // Inclusive.
   bool IsWithin(intptr_t min_int, intptr_t max_int) const;
 
   // Inclusive.
   bool Overlaps(intptr_t min_int, intptr_t max_int) const;
 
   bool IsUnsatisfiable() const;
 
+  // Returns true if range is NULL or includes -inf.
+  static bool IncludesNegativeInfinity(const Range* range);
+
+  // Returns true if range is NULL or includes +inf.
+  static bool IncludesPositiveInfinity(const Range* range);
+
+  // Both the a and b ranges are >= 0.
+  static bool OnlyPositiveOrZero(const Range& a, const Range& b);
+
+  // Both the a and b ranges are <= 0.
+  static bool OnlyNegativeOrZero(const Range& a, const Range& b);
+
+  // Return the maximum absolute value included in range.
+  static int64_t ConstantAbsMax(const Range* range);
+
+  static Range* BinaryOp(const Token::Kind op,
+                         const RangeBoundary& left_min,
+                         const RangeBoundary& left_max,
+                         const Range* left_range,
+                         const Range* right_range,
+                         const Range* original_range);
+
  private:
   RangeBoundary min_;
   RangeBoundary max_;
 };
 
 
 class ConstraintInstr : public TemplateDefinition<2> {
  public:
   ConstraintInstr(Value* value, Range* constraint)
       : constraint_(constraint),
@@ skipping 5331 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_