Support Int32 representation for selected binary operations.

runtime/vm/flow_graph_range_analysis.h

 // Copyright (c) 2014, 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_FLOW_GRAPH_RANGE_ANALYSIS_H_
 #define VM_FLOW_GRAPH_RANGE_ANALYSIS_H_
 
 #include "vm/flow_graph.h"
 #include "vm/intermediate_language.h"
 
 namespace dart {
 
 class RangeBoundary : public ValueObject {
  public:
   enum Kind {
     kUnknown,
     kNegativeInfinity,
     kPositiveInfinity,
     kSymbol,
     kConstant,
   };
 
   enum RangeSize {
     kRangeBoundarySmi,
+    kRangeBoundaryInt32,
     kRangeBoundaryInt64,
   };
 
   RangeBoundary() : kind_(kUnknown), value_(0), offset_(0) { }
 
   RangeBoundary(const RangeBoundary& other)
       : ValueObject(),
         kind_(other.kind_),
         value_(other.value_),
         offset_(other.offset_) { }
@@ skipping 32 matching lines @@
   // 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);
   }
 
-    // Construct a RangeBoundary for the constant kMin value.
+  // Construct a RangeBoundary for the constant kMin value.
   static RangeBoundary MinConstant() {
     return FromConstant(kMin);
   }
 
   // Construct a RangeBoundary for the constant kMax value.
   static RangeBoundary MaxConstant() {
     return FromConstant(kMax);
   }
 
+  // Construct a RangeBoundary for the constant kMin value.
+  static RangeBoundary MinConstant(RangeSize size) {
+    switch (size) {
+      case kRangeBoundarySmi:
+        return FromConstant(Smi::kMinValue);
+      case kRangeBoundaryInt32:
+        return FromConstant(kMinInt32);
+      case kRangeBoundaryInt64:
+        return FromConstant(kMinInt64);
+    }
+    UNREACHABLE();
+    return FromConstant(kMinInt64);
+  }
+
+  static RangeBoundary MaxConstant(RangeSize size) {
+    switch (size) {
+      case kRangeBoundarySmi:
+        return FromConstant(Smi::kMaxValue);
+      case kRangeBoundaryInt32:
+        return FromConstant(kMaxInt32);
+      case kRangeBoundaryInt64:
+        return FromConstant(kMaxInt64);
+    }
+    UNREACHABLE();
+    return FromConstant(kMaxInt64);
+  }
+
+
   // Given two boundaries a and b, select one of them as c so that
   //
   //   inf {[a, ...) ^ [b, ...)} >= inf {c}
   //
   static RangeBoundary IntersectionMin(RangeBoundary a, RangeBoundary b);
 
   // Given two boundaries a and b, select one of them as c so that
   //
   //   sup {(..., a] ^ (..., b]} <= sup {c}
   //
   static RangeBoundary IntersectionMax(RangeBoundary a, RangeBoundary b);
 
   // Given two boundaries a and b compute boundary c such that
   //
   //   inf {[a, ...) U  [b, ...)} >= inf {c}
   //
   // Try to select c such that it is as close to inf {[a, ...) U [b, ...)}
   // as possible.
-  static RangeBoundary JoinMin(RangeBoundary a, RangeBoundary b);
+  static RangeBoundary JoinMin(RangeBoundary a,
+                               RangeBoundary b,
+                               RangeBoundary::RangeSize size);
 
   // Given two boundaries a and b compute boundary c such that
   //
   //   sup {(..., a] U (..., b]} <= sup {c}
   //
   // Try to select c such that it is as close to sup {(..., a] U (..., b]}
   // as possible.
-  static RangeBoundary JoinMax(RangeBoundary a, RangeBoundary b);
+  static RangeBoundary JoinMax(RangeBoundary a,
+                               RangeBoundary b,
+                               RangeBoundary::RangeSize size);
 
   // Returns true when this is a constant that is outside of Smi range.
   bool OverflowedSmi() const {
     return (IsConstant() && !Smi::IsValid(ConstantValue())) || IsInfinity();
   }
 
+  bool Overflowed(RangeBoundary::RangeSize size) const {
+    ASSERT(IsConstantOrInfinity());
+    return !Equals(Clamp(size));
+  }
+
   // Returns true if this outside mint range.
   bool OverflowedMint() const {
     return IsInfinity();
   }
 
   // -/+ infinity are clamped to MinConstant/MaxConstant of the given type.
   RangeBoundary Clamp(RangeSize size) const {
     if (IsNegativeInfinity()) {
-      return (size == kRangeBoundaryInt64) ? MinConstant() : MinSmi();
+      return RangeBoundary::MinConstant(size);
     }
+
     if (IsPositiveInfinity()) {
-      return (size == kRangeBoundaryInt64) ? MaxConstant() : MaxSmi();
+      return RangeBoundary::MaxConstant(size);
     }
-    if ((size == kRangeBoundarySmi) && IsConstant()) {
-      if (ConstantValue() <= Smi::kMinValue) {
-        return MinSmi();
+
+    if (IsConstant()) {
+      const RangeBoundary range_min = RangeBoundary::MinConstant(size);
+      const RangeBoundary range_max = RangeBoundary::MaxConstant(size);
+
+      if (ConstantValue() <= range_min.ConstantValue()) {
+        return range_min;
       }
-      if (ConstantValue() >= Smi::kMaxValue) {
-        return MaxSmi();
+      if (ConstantValue() >= range_max.ConstantValue()) {
+        return range_max;
       }
     }
+
     // If this range is a symbolic range, we do not clamp it.
     // This could lead to some imprecision later on.
     return *this;
   }
 
-  bool IsSmiMinimumOrBelow() const {
+  bool IsMinimumOrBelow(RangeSize size) const {
     return IsNegativeInfinity() ||
-           (IsConstant() && (ConstantValue() <= Smi::kMinValue));
+        (IsConstant() &&
+         (ConstantValue() <= RangeBoundary::MinConstant(size).ConstantValue()));
   }
 
-  bool IsSmiMaximumOrAbove() const {
+  bool IsMaximumOrAbove(RangeSize size) const {
     return IsPositiveInfinity() ||
-           (IsConstant() && (ConstantValue() >= Smi::kMaxValue));
-  }
-
-  bool IsMinimumOrBelow() const {
-    return IsNegativeInfinity() || (IsConstant() && (ConstantValue() == kMin));
-  }
-
-  bool IsMaximumOrAbove() const {
-    return IsPositiveInfinity() || (IsConstant() && (ConstantValue() == kMax));
+        (IsConstant() &&
+         (ConstantValue() >= RangeBoundary::MaxConstant(size).ConstantValue()));
   }
 
   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; }
@@ skipping 66 matching lines @@
 
   // 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;
 
+  int64_t UpperBound(RangeSize size) const {
+    return UpperBound().Clamp(size).ConstantValue();
+  }
+
+  int64_t LowerBound(RangeSize size) const {
+    return LowerBound().Clamp(size).ConstantValue();
+  }
+
   int64_t SmiUpperBound() const {
-    return UpperBound().Clamp(kRangeBoundarySmi).ConstantValue();
+    return UpperBound(kRangeBoundarySmi);
   }
 
   int64_t SmiLowerBound() const {
-    return LowerBound().Clamp(kRangeBoundarySmi).ConstantValue();
+    return LowerBound(kRangeBoundarySmi);
   }
 
  private:
   RangeBoundary(Kind kind, int64_t value, int64_t offset)
       : kind_(kind), value_(value), offset_(offset) { }
 
   Kind kind_;
   int64_t value_;
   int64_t offset_;
 };
@@ skipping 19 matching lines @@
   }
 
   static bool IsUnknown(const Range* other) {
     if (other == NULL) {
       return true;
     }
     return other->min().IsUnknown();
   }
 
   static Range Full(RangeBoundary::RangeSize size) {
-    if (size == RangeBoundary::kRangeBoundarySmi) {
-      return Range(RangeBoundary::MinSmi(), RangeBoundary::MaxSmi());
-    } else {
-      ASSERT(size == RangeBoundary::kRangeBoundaryInt64);
-      return Range(RangeBoundary::MinConstant(), RangeBoundary::MaxConstant());
-    }
+    return Range(RangeBoundary::MinConstant(size),
+                 RangeBoundary::MaxConstant(size));
   }
 
   void PrintTo(BufferFormatter* f) const;
   static const char* ToCString(const Range* range);
 
   bool Equals(const Range* other) {
     ASSERT(min_.IsUnknown() == max_.IsUnknown());
     if (other == NULL) {
       return min_.IsUnknown();
     }
     return min_.Equals(other->min_) &&
         max_.Equals(other->max_);
   }
 
   const RangeBoundary& min() const { return min_; }
   const RangeBoundary& max() const { return max_; }
   void set_min(const RangeBoundary& value) {
     min_ = value;
   }
   void set_max(const RangeBoundary& value) {
     max_ = value;
   }
 
   static RangeBoundary ConstantMinSmi(const Range* range) {
-    if (range == NULL) {
-      return RangeBoundary::MinSmi();
-    }
-    return range->min().LowerBound().Clamp(RangeBoundary::kRangeBoundarySmi);
+    return ConstantMin(range, RangeBoundary::kRangeBoundarySmi);
   }
 
   static RangeBoundary ConstantMaxSmi(const Range* range) {
-    if (range == NULL) {
-      return RangeBoundary::MaxSmi();
-    }
-    return range->max().UpperBound().Clamp(RangeBoundary::kRangeBoundarySmi);
+    return ConstantMax(range, RangeBoundary::kRangeBoundarySmi);
   }
 
   static RangeBoundary ConstantMin(const Range* range) {
-    if (range == NULL) {
-      return RangeBoundary::MinConstant();
-    }
-    return range->min().LowerBound().Clamp(RangeBoundary::kRangeBoundaryInt64);
+    return ConstantMin(range, RangeBoundary::kRangeBoundaryInt64);
   }
 
   static RangeBoundary ConstantMax(const Range* range) {
+    return ConstantMax(range, RangeBoundary::kRangeBoundaryInt64);
+  }
+
+  static RangeBoundary ConstantMin(const Range* range,
+                                   RangeBoundary::RangeSize size) {
     if (range == NULL) {
-      return RangeBoundary::MaxConstant();
+      return RangeBoundary::MinConstant(size);
     }
-    return range->max().UpperBound().Clamp(RangeBoundary::kRangeBoundaryInt64);
+    return range->min().LowerBound().Clamp(size);
   }
 
+  static RangeBoundary ConstantMax(const Range* range,
+                                   RangeBoundary::RangeSize size) {
+    if (range == NULL) {
+      return RangeBoundary::MaxConstant(size);
+    }
+    return range->max().UpperBound().Clamp(size);
+  }
+
+
   // [0, +inf]
   bool IsPositive() const;
 
   // [-inf, val].
   bool OnlyLessThanOrEqualTo(int64_t val) const;
 
   // [val, +inf].
   bool OnlyGreaterThanOrEqualTo(int64_t val) const;
 
   // Inclusive.
   bool IsWithin(int64_t min_int, int64_t max_int) const;
 
   // Inclusive.
   bool Overlaps(int64_t min_int, int64_t max_int) const;
 
   bool IsUnsatisfiable() const;
 
   bool IsFinite() const {
     return !min_.IsInfinity() && !max_.IsInfinity();
   }
 
   Range Intersect(const Range* other) const {
     return Range(RangeBoundary::IntersectionMin(min(), other->min()),
                  RangeBoundary::IntersectionMax(max(), other->max()));
   }
 
+  bool Fits(RangeBoundary::RangeSize size) const {
+    return !min().LowerBound().Overflowed(size) &&
+           !max().UpperBound().Overflowed(size);
+  }
+
+  static bool Fits(Range* range, RangeBoundary::RangeSize size) {
+    return !IsUnknown(range) && range->Fits(size);
+  }

[srdjan, 2014/08/27 16:17:13]

I think it is confusing to have a non-static and static method with same name.

[Vyacheslav Egorov (Google), 2014/08/28 20:48:37]

Agreed. Moved into a separate AllStatic helper class.

+
   // Clamp this to be within size.
   void Clamp(RangeBoundary::RangeSize size);
 
   static void Add(const Range* left_range,
                   const Range* right_range,
                   RangeBoundary* min,
                   RangeBoundary* max,
                   Definition* left_defn);
 
   static void Sub(const Range* left_range,
@@ skipping 110 matching lines @@
   void Iterate(JoinOperator op, intptr_t max_iterations);
   bool InferRange(JoinOperator op, Definition* defn, intptr_t iteration);
 
   // Based on computed ranges find and eliminate redundant CheckArrayBound
   // instructions.
   void EliminateRedundantBoundsChecks();
 
   // Find unsatisfiable constraints and mark corresponding blocks unreachable.
   void MarkUnreachableBlocks();
 
+  // Convert mint operations that stay within int32 range into Int32 operations.
+  void NarrowMintToInt32();
+
   // Remove artificial Constraint instructions and replace them with actual
   // unconstrained definitions.
   void RemoveConstraints();
 
   Range* ConstraintSmiRange(Token::Kind op, Definition* boundary);
 
   Isolate* isolate() const { return flow_graph_->isolate(); }
 
   FlowGraph* flow_graph_;
 
   // Range object representing full Smi range.
   Range smi_range_;
 
   // Value that are known to be smi or mint.
   GrowableArray<Definition*> values_;
 
+  GrowableArray<BinaryMintOpInstr*> binary_mint_ops_;
+
+  GrowableArray<ShiftMintOpInstr*> shift_mint_ops_;
+
   // All CheckArrayBound instructions.
   GrowableArray<CheckArrayBoundInstr*> bounds_checks_;
 
   // All Constraints inserted during InsertConstraints phase. They are treated
   // as smi values.
   GrowableArray<ConstraintInstr*> constraints_;
 
   // List of integer (smi or mint) definitions including constraints sorted
   // in the reverse postorder.
   GrowableArray<Definition*> definitions_;
@@ skipping 27 matching lines @@
   BitVector* selected_uint32_defs_;
 
   FlowGraph* flow_graph_;
   Isolate* isolate_;
 };
 
 
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_RANGE_ANALYSIS_H_