Consolidate all range analysis related code in a separate file.

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 14 matching lines @@
 class Definition;
 class Environment;
 class FlowGraph;
 class FlowGraphBuilder;
 class FlowGraphCompiler;
 class FlowGraphVisitor;
 class Instruction;
 class LocalVariable;
 class ParsedFunction;
 class Range;
+class RangeBoundary;
 
 
 // TODO(srdjan): Unify with INTRINSIC_LIST.
 // (class-name, function-name, recognized enum, fingerprint).
 // See intrinsifier for fingerprint computation.
 #define RECOGNIZED_LIST(V)                                                     \
   V(::, identical, ObjectIdentical, 496869842)                                 \
   V(ClassID, getID, ClassIDgetID, 1322490980)                                  \
   V(Object, ==, ObjectEquals, 1068471689)                                      \
   V(Object, Object., ObjectConstructor, 1066669787)                            \
@@ skipping 2511 matching lines @@
   virtual EffectSet Dependencies() const { return EffectSet::None(); }
   virtual EffectSet Effects() const { return EffectSet::None(); }
 
   virtual bool MayThrow() const { return false; }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(RedefinitionInstr);
 };
 
 
-class RangeBoundary : public ValueObject {
- public:
-  enum Kind {
-    kUnknown,
-    kNegativeInfinity,
-    kPositiveInfinity,
-    kSymbol,
-    kConstant,
-  };
-
-  enum RangeSize {
-    kRangeBoundarySmi,
-    kRangeBoundaryInt64,
-  };
-
-  RangeBoundary() : kind_(kUnknown), value_(0), offset_(0) { }
-
-  RangeBoundary(const RangeBoundary& other)
-      : ValueObject(),
-        kind_(other.kind_),
-        value_(other.value_),
-        offset_(other.offset_) { }
-
-  explicit RangeBoundary(int64_t val)
-      : kind_(kConstant), value_(val), offset_(0) { }
-
-  RangeBoundary& operator=(const RangeBoundary& other) {
-    kind_ = other.kind_;
-    value_ = other.value_;
-    offset_ = other.offset_;
-    return *this;
-  }
-
-  static const int64_t kMin = kMinInt64;
-  static const int64_t kMax = kMaxInt64;
-
-  // Construct a RangeBoundary for a constant value.
-  static RangeBoundary FromConstant(int64_t val) {
-    return RangeBoundary(val);
-  }
-
-  // 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, int64_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);
-  }
-
-    // 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);
-  }
-
-  // Calculate the minimum of a and b within the given range.
-  static RangeBoundary Min(RangeBoundary a, RangeBoundary b, RangeSize size);
-  static RangeBoundary Max(RangeBoundary a, RangeBoundary b, RangeSize size);
-
-  // Returns true when this is a constant that is outside of Smi range.
-  bool OverflowedSmi() const {
-    return (IsConstant() && !Smi::IsValid(ConstantValue())) || IsInfinity();
-  }
-
-  // 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();
-    }
-    if (IsPositiveInfinity()) {
-      return (size == kRangeBoundaryInt64) ? MaxConstant() : MaxSmi();
-    }
-    if ((size == kRangeBoundarySmi) && IsConstant()) {
-      if (ConstantValue() <= Smi::kMinValue) {
-        return MinSmi();
-      }
-      if (ConstantValue() >= Smi::kMaxValue) {
-        return MaxSmi();
-      }
-    }
-    // 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 {
-    return IsNegativeInfinity() ||
-           (IsConstant() && (ConstantValue() <= Smi::kMinValue));
-  }
-
-  bool IsSmiMaximumOrAbove() const {
-    return IsPositiveInfinity() ||
-           (IsConstant() && (ConstantValue() >= Smi::kMaxValue));
-  }
-
-  bool IsMinimumOrBelow() const {
-    return IsNegativeInfinity() || (IsConstant() && (ConstantValue() == kMin));
-  }
-
-  bool IsMaximumOrAbove() const {
-    return IsPositiveInfinity() || (IsConstant() && (ConstantValue() == kMax));
-  }
-
-  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();
-  }
-  bool IsConstantOrInfinity() const {
-    return IsConstant() || IsInfinity();
-  }
-
-  // Returns the value of a kConstant RangeBoundary.
-  int64_t ConstantValue() const;
-
-  // Returns the Definition associated with a kSymbol RangeBoundary.
-  Definition* symbol() const {
-    ASSERT(IsSymbol());
-    return reinterpret_cast<Definition*>(value_);
-  }
-
-  // Offset from symbol.
-  int64_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);
-
-  static RangeBoundary Sub(const RangeBoundary& a,
-                           const RangeBoundary& b,
-                           const RangeBoundary& overflow);
-
-  static RangeBoundary Shl(const RangeBoundary& value_boundary,
-                           int64_t shift_count,
-                           const RangeBoundary& overflow);
-
-  static RangeBoundary Shr(const RangeBoundary& value_boundary,
-                           int64_t shift_count) {
-    ASSERT(value_boundary.IsConstant());
-    ASSERT(shift_count >= 0);
-    int64_t value = static_cast<int64_t>(value_boundary.ConstantValue());
-    int64_t result = value >> shift_count;
-    return RangeBoundary(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, int64_t value, int64_t offset)
-      : kind_(kind), value_(value), offset_(offset) { }
-
-  Kind kind_;
-  int64_t value_;
-  int64_t offset_;
-};
-
-
-class Range : public ZoneAllocated {
- public:
-  Range(RangeBoundary min, RangeBoundary max) : min_(min), max_(max) { }
-
-  static Range* Unknown() {
-    return new Range(RangeBoundary::MinConstant(),
-                     RangeBoundary::MaxConstant());
-  }
-
-  static Range* UnknownSmi() {
-    return new Range(RangeBoundary::MinSmi(),
-                     RangeBoundary::MaxSmi());
-  }
-
-  void PrintTo(BufferFormatter* f) const;
-  static const char* ToCString(const Range* range);
-
-  const RangeBoundary& min() const { return min_; }
-  const RangeBoundary& max() const { return max_; }
-
-  static RangeBoundary ConstantMinSmi(const Range* range) {
-    if (range == NULL) {
-      return RangeBoundary::MinSmi();
-    }
-    return range->min().LowerBound().Clamp(RangeBoundary::kRangeBoundarySmi);
-  }
-
-  static RangeBoundary ConstantMaxSmi(const Range* range) {
-    if (range == NULL) {
-      return RangeBoundary::MaxSmi();
-    }
-    return range->max().UpperBound().Clamp(RangeBoundary::kRangeBoundarySmi);
-  }
-
-  static RangeBoundary ConstantMin(const Range* range) {
-    if (range == NULL) {
-      return RangeBoundary::MinConstant();
-    }
-    return range->min().LowerBound().Clamp(RangeBoundary::kRangeBoundaryInt64);
-  }
-
-  static RangeBoundary ConstantMax(const Range* range) {
-    if (range == NULL) {
-      return RangeBoundary::MaxConstant();
-    }
-    return range->max().UpperBound().Clamp(RangeBoundary::kRangeBoundaryInt64);
-  }
-
-  // [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();
-  }
-
-  // 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,
-                  const Range* right_range,
-                  RangeBoundary* min,
-                  RangeBoundary* max,
-                  Definition* left_defn);
-
-  static bool Mul(const Range* left_range,
-                  const Range* right_range,
-                  RangeBoundary* min,
-                  RangeBoundary* max);
-  static void Shr(const Range* left_range,
-                  const Range* right_range,
-                  RangeBoundary* min,
-                  RangeBoundary* max);
-
-  static void Shl(const Range* left_range,
-                  const Range* right_range,
-                  RangeBoundary* min,
-                  RangeBoundary* max);
-
-  static bool And(const Range* left_range,
-                  const Range* right_range,
-                  RangeBoundary* min,
-                  RangeBoundary* max);
-
-
-  // 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 Range* left_range,
-                         const Range* right_range,
-                         Definition* left_defn);
-
- private:
-  RangeBoundary min_;
-  RangeBoundary max_;
-};
-
-
 class ConstraintInstr : public TemplateDefinition<2> {
  public:
   ConstraintInstr(Value* value, Range* constraint)
       : constraint_(constraint),
         target_(NULL) {
     SetInputAt(0, value);
   }
 
   DECLARE_INSTRUCTION(Constraint)
 
@@ skipping 5157 matching lines @@
 
   Value* length() const { return inputs_[kLengthPos]; }
   Value* index() const { return inputs_[kIndexPos]; }
 
   DECLARE_INSTRUCTION(CheckArrayBound)
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   virtual bool CanDeoptimize() const { return true; }
 
-  bool IsRedundant(RangeBoundary length);
+  bool IsRedundant(const RangeBoundary& length);
 
   virtual Instruction* Canonicalize(FlowGraph* flow_graph);
 
   // Returns the length offset for array and string types.
   static intptr_t LengthOffsetFor(intptr_t class_id);
 
   static bool IsFixedLengthArrayType(intptr_t class_id);
 
   virtual bool AllowsCSE() const { return true; }
   virtual EffectSet Effects() const { return EffectSet::None(); }
@@ skipping 529 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_