Consolidate all range analysis related code in a separate file.

runtime/vm/intermediate_language.cc

 // 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.
 
 #include "vm/intermediate_language.h"
 
 #include "vm/bigint_operations.h"
 #include "vm/bit_vector.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_allocator.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
 #include "vm/flow_graph_optimizer.h"
+#include "vm/flow_graph_range_analysis.h"
 #include "vm/locations.h"
 #include "vm/object.h"
 #include "vm/object_store.h"
 #include "vm/os.h"
 #include "vm/resolver.h"
 #include "vm/scopes.h"
 #include "vm/stub_code.h"
 #include "vm/symbols.h"
 
 #include "vm/il_printer.h"
@@ skipping 2550 matching lines @@
   intptr_t use_index = instr->env()->Length();  // Start index after inner.
   for (Environment::DeepIterator it(copy); !it.Done(); it.Advance()) {
     Value* value = it.CurrentValue();
     value->set_instruction(instr);
     value->set_use_index(use_index++);
     value->definition()->AddEnvUse(value);
   }
 }
 
 
-RangeBoundary RangeBoundary::FromDefinition(Definition* defn, int64_t offs) {
-  if (defn->IsConstant() && defn->AsConstant()->value().IsSmi()) {
-    return FromConstant(Smi::Cast(defn->AsConstant()->value()).Value() + offs);
-  }
-  return RangeBoundary(kSymbol, reinterpret_cast<intptr_t>(defn), offs);
-}
-
-
-RangeBoundary RangeBoundary::LowerBound() const {
-  if (IsInfinity()) {
-    return NegativeInfinity();
-  }
-  if (IsConstant()) return *this;
-  return Add(Range::ConstantMin(symbol()->range()),
-             RangeBoundary::FromConstant(offset_),
-             NegativeInfinity());
-}
-
-
-RangeBoundary RangeBoundary::UpperBound() const {
-  if (IsInfinity()) {
-    return PositiveInfinity();
-  }
-  if (IsConstant()) return *this;
-  return Add(Range::ConstantMax(symbol()->range()),
-             RangeBoundary::FromConstant(offset_),
-             PositiveInfinity());
-}
-
-
-RangeBoundary RangeBoundary::Add(const RangeBoundary& a,
-                                 const RangeBoundary& b,
-                                 const RangeBoundary& overflow) {
-  if (a.IsInfinity() || b.IsInfinity()) return overflow;
-
-  ASSERT(a.IsConstant() && b.IsConstant());
-  if (Utils::WillAddOverflow(a.ConstantValue(), b.ConstantValue())) {
-    return overflow;
-  }
-
-  int64_t result = a.ConstantValue() + b.ConstantValue();
-
-  return RangeBoundary::FromConstant(result);
-}
-
-
-RangeBoundary RangeBoundary::Sub(const RangeBoundary& a,
-                                 const RangeBoundary& b,
-                                 const RangeBoundary& overflow) {
-  if (a.IsInfinity() || b.IsInfinity()) return overflow;
-  ASSERT(a.IsConstant() && b.IsConstant());
-  if (Utils::WillSubOverflow(a.ConstantValue(), b.ConstantValue())) {
-    return overflow;
-  }
-
-  int64_t result = a.ConstantValue() - b.ConstantValue();
-
-  return RangeBoundary::FromConstant(result);
-}
-
-
-bool RangeBoundary::SymbolicAdd(const RangeBoundary& a,
-                                const RangeBoundary& b,
-                                RangeBoundary* result) {
-  if (a.IsSymbol() && b.IsConstant()) {
-    if (Utils::WillAddOverflow(a.offset(), b.ConstantValue())) {
-      return false;
-    }
-
-    const int64_t offset = a.offset() + b.ConstantValue();
-
-    *result = RangeBoundary::FromDefinition(a.symbol(), offset);
-    return true;
-  } else if (b.IsSymbol() && a.IsConstant()) {
-    return SymbolicAdd(b, a, result);
-  }
-  return false;
-}
-
-
-bool RangeBoundary::SymbolicSub(const RangeBoundary& a,
-                                const RangeBoundary& b,
-                                RangeBoundary* result) {
-  if (a.IsSymbol() && b.IsConstant()) {
-    if (Utils::WillSubOverflow(a.offset(), b.ConstantValue())) {
-      return false;
-    }
-
-    const int64_t offset = a.offset() - b.ConstantValue();
-
-    *result = RangeBoundary::FromDefinition(a.symbol(), offset);
-    return true;
-  }
-  return false;
-}
-
-
-static Definition* UnwrapConstraint(Definition* defn) {
-  while (defn->IsConstraint()) {
-    defn = defn->AsConstraint()->value()->definition();
-  }
-  return defn;
-}
-
-
-static bool AreEqualDefinitions(Definition* a, Definition* b) {
-  a = UnwrapConstraint(a);
-  b = UnwrapConstraint(b);
-  return (a == b) ||
-      (a->AllowsCSE() &&
-       a->Dependencies().IsNone() &&
-       b->AllowsCSE() &&
-       b->Dependencies().IsNone() &&
-       a->Equals(b));
-}
-
-
-// Returns true if two range boundaries refer to the same symbol.
-static bool DependOnSameSymbol(const RangeBoundary& a, const RangeBoundary& b) {
-  return a.IsSymbol() && b.IsSymbol() &&
-      AreEqualDefinitions(a.symbol(), b.symbol());
-}
-
-
-bool RangeBoundary::Equals(const RangeBoundary& other) const {
-  if (IsConstant() && other.IsConstant()) {
-    return ConstantValue() == other.ConstantValue();
-  } else if (IsInfinity() && other.IsInfinity()) {
-    return kind() == other.kind();
-  } else if (IsSymbol() && other.IsSymbol()) {
-    return (offset() == other.offset()) && DependOnSameSymbol(*this, other);
-  } else if (IsUnknown() && other.IsUnknown()) {
-    return true;
-  }
-  return false;
-}
-
-
-RangeBoundary RangeBoundary::Shl(const RangeBoundary& value_boundary,
-                                 int64_t shift_count,
-                                 const RangeBoundary& overflow) {
-  ASSERT(value_boundary.IsConstant());
-  ASSERT(shift_count >= 0);
-  int64_t limit = 64 - shift_count;
-  int64_t value = value_boundary.ConstantValue();
-
-  if ((value == 0) ||
-      (shift_count == 0) ||
-      ((limit > 0) && Utils::IsInt(static_cast<int>(limit), value))) {
-    // Result stays in 64 bit range.
-    int64_t result = value << shift_count;
-    return RangeBoundary(result);
-  }
-
-  return overflow;
-}
-
-
-static RangeBoundary CanonicalizeBoundary(const RangeBoundary& a,
-                                          const RangeBoundary& overflow) {
-  if (a.IsConstant() || a.IsInfinity()) {
-    return a;
-  }
-
-  int64_t offset = a.offset();
-  Definition* symbol = a.symbol();
-
-  bool changed;
-  do {
-    changed = false;
-    if (symbol->IsConstraint()) {
-      symbol = symbol->AsConstraint()->value()->definition();
-      changed = true;
-    } else if (symbol->IsBinarySmiOp()) {
-      BinarySmiOpInstr* op = symbol->AsBinarySmiOp();
-      Definition* left = op->left()->definition();
-      Definition* right = op->right()->definition();
-      switch (op->op_kind()) {
-        case Token::kADD:
-          if (right->IsConstant()) {
-            int64_t rhs = Smi::Cast(right->AsConstant()->value()).Value();
-            if (Utils::WillAddOverflow(offset, rhs)) {
-              return overflow;
-            }
-            offset += rhs;
-            symbol = left;
-            changed = true;
-          } else if (left->IsConstant()) {
-            int64_t rhs = Smi::Cast(left->AsConstant()->value()).Value();
-            if (Utils::WillAddOverflow(offset, rhs)) {
-              return overflow;
-            }
-            offset += rhs;
-            symbol = right;
-            changed = true;
-          }
-          break;
-
-        case Token::kSUB:
-          if (right->IsConstant()) {
-            int64_t rhs = Smi::Cast(right->AsConstant()->value()).Value();
-            if (Utils::WillSubOverflow(offset, rhs)) {
-              return overflow;
-            }
-            offset -= rhs;
-            symbol = left;
-            changed = true;
-          }
-          break;
-
-        default:
-          break;
-      }
-    }
-  } while (changed);
-
-  return RangeBoundary::FromDefinition(symbol, offset);
-}
-
-
-static bool CanonicalizeMaxBoundary(RangeBoundary* a) {
-  if (!a->IsSymbol()) return false;
-
-  Range* range = a->symbol()->range();
-  if ((range == NULL) || !range->max().IsSymbol()) return false;
-
-
-  if (Utils::WillAddOverflow(range->max().offset(), a->offset())) {
-    *a = RangeBoundary::PositiveInfinity();
-    return true;
-  }
-
-  const int64_t offset = range->max().offset() + a->offset();
-
-
-  *a = CanonicalizeBoundary(
-      RangeBoundary::FromDefinition(range->max().symbol(), offset),
-      RangeBoundary::PositiveInfinity());
-
-  return true;
-}
-
-
-static bool CanonicalizeMinBoundary(RangeBoundary* a) {
-  if (!a->IsSymbol()) return false;
-
-  Range* range = a->symbol()->range();
-  if ((range == NULL) || !range->min().IsSymbol()) return false;
-
-  if (Utils::WillAddOverflow(range->min().offset(), a->offset())) {
-    *a = RangeBoundary::NegativeInfinity();
-    return true;
-  }
-
-  const int64_t offset = range->min().offset() + a->offset();
-
-  *a = CanonicalizeBoundary(
-      RangeBoundary::FromDefinition(range->min().symbol(), offset),
-      RangeBoundary::NegativeInfinity());
-
-  return true;
-}
-
-
-RangeBoundary RangeBoundary::Min(RangeBoundary a, RangeBoundary b,
-                                 RangeSize size) {
-  ASSERT(!(a.IsNegativeInfinity() || b.IsNegativeInfinity()));
-  ASSERT(!a.IsUnknown() || !b.IsUnknown());
-  if (a.IsUnknown() && !b.IsUnknown()) {
-    return b;
-  }
-  if (!a.IsUnknown() && b.IsUnknown()) {
-    return a;
-  }
-  if (size == kRangeBoundarySmi) {
-    if (a.IsSmiMaximumOrAbove() && !b.IsSmiMaximumOrAbove()) {
-      return b;
-    }
-    if (!a.IsSmiMaximumOrAbove() && b.IsSmiMaximumOrAbove()) {
-      return a;
-    }
-  } else {
-    ASSERT(size == kRangeBoundaryInt64);
-    if (a.IsMaximumOrAbove() && !b.IsMaximumOrAbove()) {
-      return b;
-    }
-    if (!a.IsMaximumOrAbove() && b.IsMaximumOrAbove()) {
-      return a;
-    }
-  }
-
-  if (a.Equals(b)) {
-    return b;
-  }
-
-  {
-    RangeBoundary canonical_a =
-        CanonicalizeBoundary(a, RangeBoundary::PositiveInfinity());
-    RangeBoundary canonical_b =
-        CanonicalizeBoundary(b, RangeBoundary::PositiveInfinity());
-    do {
-      if (DependOnSameSymbol(canonical_a, canonical_b)) {
-        a = canonical_a;
-        b = canonical_b;
-        break;
-      }
-    } while (CanonicalizeMaxBoundary(&canonical_a) ||
-             CanonicalizeMaxBoundary(&canonical_b));
-  }
-
-  if (DependOnSameSymbol(a, b)) {
-    return (a.offset() <= b.offset()) ? a : b;
-  }
-
-  const int64_t min_a = a.UpperBound().Clamp(size).ConstantValue();
-  const int64_t min_b = b.UpperBound().Clamp(size).ConstantValue();
-
-  return RangeBoundary::FromConstant(Utils::Minimum(min_a, min_b));
-}
-
-
-RangeBoundary RangeBoundary::Max(RangeBoundary a, RangeBoundary b,
-                                 RangeSize size) {
-  ASSERT(!(a.IsPositiveInfinity() || b.IsPositiveInfinity()));
-  ASSERT(!a.IsUnknown() || !b.IsUnknown());
-  if (a.IsUnknown() && !b.IsUnknown()) {
-    return b;
-  }
-  if (!a.IsUnknown() && b.IsUnknown()) {
-    return a;
-  }
-  if (size == kRangeBoundarySmi) {
-    if (a.IsSmiMinimumOrBelow() && !b.IsSmiMinimumOrBelow()) {
-      return b;
-    }
-    if (!a.IsSmiMinimumOrBelow() && b.IsSmiMinimumOrBelow()) {
-      return a;
-    }
-  } else {
-     ASSERT(size == kRangeBoundaryInt64);
-    if (a.IsMinimumOrBelow() && !b.IsMinimumOrBelow()) {
-      return b;
-    }
-    if (!a.IsMinimumOrBelow() && b.IsMinimumOrBelow()) {
-      return a;
-    }
-  }
-  if (a.Equals(b)) {
-    return b;
-  }
-
-  {
-    RangeBoundary canonical_a =
-        CanonicalizeBoundary(a, RangeBoundary::NegativeInfinity());
-    RangeBoundary canonical_b =
-        CanonicalizeBoundary(b, RangeBoundary::NegativeInfinity());
-
-    do {
-      if (DependOnSameSymbol(canonical_a, canonical_b)) {
-        a = canonical_a;
-        b = canonical_b;
-        break;
-      }
-    } while (CanonicalizeMinBoundary(&canonical_a) ||
-             CanonicalizeMinBoundary(&canonical_b));
-  }
-
-  if (DependOnSameSymbol(a, b)) {
-    return (a.offset() <= b.offset()) ? b : a;
-  }
-
-  const int64_t max_a = a.LowerBound().Clamp(size).ConstantValue();
-  const int64_t max_b = b.LowerBound().Clamp(size).ConstantValue();
-
-  return RangeBoundary::FromConstant(Utils::Maximum(max_a, max_b));
-}
-
-
-int64_t RangeBoundary::ConstantValue() const {
-  ASSERT(IsConstant());
-  return value_;
-}
-
-
-void Definition::InferRange() {
-  if (Type()->ToCid() == kSmiCid) {
-    if (range_ == NULL) {
-      range_ = Range::UnknownSmi();
-    }
-  } else if (IsMintDefinition()) {
-    if (range_ == NULL) {
-      range_ = Range::Unknown();
-    }
-  } else {
-    // Only Smi and Mint supported.
-    UNREACHABLE();
-  }
-}
-
-
-void ConstantInstr::InferRange() {
-  if (value_.IsSmi()) {
-    if (range_ == NULL) {
-      int64_t value = Smi::Cast(value_).Value();
-      range_ = new Range(RangeBoundary::FromConstant(value),
-                         RangeBoundary::FromConstant(value));
-    }
-  } else if (value_.IsMint()) {
-    if (range_ == NULL) {
-      int64_t value = Mint::Cast(value_).value();
-      range_ = new Range(RangeBoundary::FromConstant(value),
-                         RangeBoundary::FromConstant(value));
-    }
-  } else {
-    // Only Smi and Mint supported.
-    UNREACHABLE();
-  }
-}
-
-
-void UnboxIntegerInstr::InferRange() {
-  if (range_ == NULL) {
-    Definition* unboxed = value()->definition();
-    ASSERT(unboxed != NULL);
-    Range* range = unboxed->range();
-    if (range == NULL) {
-      range_ = Range::Unknown();
-      return;
-    }
-    range_ = new Range(range->min(), range->max());
-  }
-}
-
-
-void ConstraintInstr::InferRange() {
-  Range* value_range = value()->definition()->range();
-
-  // Only constraining smi values.
-  ASSERT(value()->IsSmiValue());
-
-  RangeBoundary min;
-  RangeBoundary max;
-
-  {
-    RangeBoundary value_min = (value_range == NULL) ?
-        RangeBoundary() : value_range->min();
-    RangeBoundary constraint_min = constraint()->min();
-    min = RangeBoundary::Max(value_min, constraint_min,
-                             RangeBoundary::kRangeBoundarySmi);
-  }
-
-  ASSERT(!min.IsUnknown());
-
-  {
-    RangeBoundary value_max = (value_range == NULL) ?
-        RangeBoundary() : value_range->max();
-    RangeBoundary constraint_max = constraint()->max();
-    max = RangeBoundary::Min(value_max, constraint_max,
-                             RangeBoundary::kRangeBoundarySmi);
-  }
-
-  ASSERT(!max.IsUnknown());
-
-  range_ = new Range(min, max);
-
-  // Mark branches that generate unsatisfiable constraints as constant.
-  if (target() != NULL && range_->IsUnsatisfiable()) {
-    BranchInstr* branch =
-        target()->PredecessorAt(0)->last_instruction()->AsBranch();
-    if (target() == branch->true_successor()) {
-      // True unreachable.
-      if (FLAG_trace_constant_propagation) {
-        OS::Print("Range analysis: True unreachable (B%" Pd ")\n",
-                  branch->true_successor()->block_id());
-      }
-      branch->set_constant_target(branch->false_successor());
-    } else {
-      ASSERT(target() == branch->false_successor());
-      // False unreachable.
-      if (FLAG_trace_constant_propagation) {
-        OS::Print("Range analysis: False unreachable (B%" Pd ")\n",
-                  branch->false_successor()->block_id());
-      }
-      branch->set_constant_target(branch->true_successor());
-    }
-  }
-}
-
-
-void LoadFieldInstr::InferRange() {
-  if ((range_ == NULL) &&
-      ((recognized_kind() == MethodRecognizer::kObjectArrayLength) ||
-       (recognized_kind() == MethodRecognizer::kImmutableArrayLength))) {
-    range_ = new Range(RangeBoundary::FromConstant(0),
-                       RangeBoundary::FromConstant(Array::kMaxElements));
-    return;
-  }
-  if ((range_ == NULL) &&
-      (recognized_kind() == MethodRecognizer::kTypedDataLength)) {
-    range_ = new Range(RangeBoundary::FromConstant(0), RangeBoundary::MaxSmi());
-    return;
-  }
-  if ((range_ == NULL) &&
-      (recognized_kind() == MethodRecognizer::kStringBaseLength)) {
-    range_ = new Range(RangeBoundary::FromConstant(0),
-                       RangeBoundary::FromConstant(String::kMaxElements));
-    return;
-  }
-  Definition::InferRange();
-}
-
-
-
-void LoadIndexedInstr::InferRange() {
-  switch (class_id()) {
-    case kTypedDataInt8ArrayCid:
-      range_ = new Range(RangeBoundary::FromConstant(-128),
-                         RangeBoundary::FromConstant(127));
-      break;
-    case kTypedDataUint8ArrayCid:
-    case kTypedDataUint8ClampedArrayCid:
-    case kExternalTypedDataUint8ArrayCid:
-    case kExternalTypedDataUint8ClampedArrayCid:
-      range_ = new Range(RangeBoundary::FromConstant(0),
-                         RangeBoundary::FromConstant(255));
-      break;
-    case kTypedDataInt16ArrayCid:
-      range_ = new Range(RangeBoundary::FromConstant(-32768),
-                         RangeBoundary::FromConstant(32767));
-      break;
-    case kTypedDataUint16ArrayCid:
-      range_ = new Range(RangeBoundary::FromConstant(0),
-                         RangeBoundary::FromConstant(65535));
-      break;
-    case kTypedDataInt32ArrayCid:
-      if (Typed32BitIsSmi()) {
-        range_ = Range::UnknownSmi();
-      } else {
-        range_ = new Range(RangeBoundary::FromConstant(kMinInt32),
-                           RangeBoundary::FromConstant(kMaxInt32));
-      }
-      break;
-    case kTypedDataUint32ArrayCid:
-      if (Typed32BitIsSmi()) {
-        range_ = Range::UnknownSmi();
-      } else {
-        range_ = new Range(RangeBoundary::FromConstant(0),
-                           RangeBoundary::FromConstant(kMaxUint32));
-      }
-      break;
-    case kOneByteStringCid:
-      range_ = new Range(RangeBoundary::FromConstant(0),
-                         RangeBoundary::FromConstant(0xFF));
-      break;
-    case kTwoByteStringCid:
-      range_ = new Range(RangeBoundary::FromConstant(0),
-                         RangeBoundary::FromConstant(0xFFFF));
-      break;
-    default:
-      Definition::InferRange();
-      break;
-  }
-}
-
-
-void IfThenElseInstr::InferRange() {
-  const intptr_t min = Utils::Minimum(if_true_, if_false_);
-  const intptr_t max = Utils::Maximum(if_true_, if_false_);
-  range_ = new Range(RangeBoundary::FromConstant(min),
-                     RangeBoundary::FromConstant(max));
-}
-
-
 static bool BindsToSmiConstant(Value* value) {
   return value->BindsToConstant() && value->BoundConstant().IsSmi();
 }
 
 
 ComparisonInstr* EqualityCompareInstr::CopyWithNewOperands(Value* new_left,
                                                            Value* new_right) {
   return new EqualityCompareInstr(token_pos(),
                                   kind(),
                                   new_left,
@@ skipping 71 matching lines @@
         && !comparison->AsStrictCompare()->needs_number_check();
   }
   if (comparison->operation_cid() != kSmiCid) {
     // Non-smi comparisons are not supported by if-conversion.
     return false;
   }
   return is_smi_result;
 }
 
 
-void PhiInstr::InferRange() {
-  RangeBoundary new_min;
-  RangeBoundary new_max;
-
-  ASSERT(Type()->ToCid() == kSmiCid);
-
-  for (intptr_t i = 0; i < InputCount(); i++) {
-    Range* input_range = InputAt(i)->definition()->range();
-    if (input_range == NULL) {
-      range_ = Range::UnknownSmi();
-      return;
-    }
-
-    if (new_min.IsUnknown()) {
-      new_min = Range::ConstantMin(input_range);
-    } else {
-      new_min = RangeBoundary::Min(new_min,
-                                   Range::ConstantMinSmi(input_range),
-                                   RangeBoundary::kRangeBoundarySmi);
-    }
-
-    if (new_max.IsUnknown()) {
-      new_max = Range::ConstantMax(input_range);
-    } else {
-      new_max = RangeBoundary::Max(new_max,
-                                   Range::ConstantMaxSmi(input_range),
-                                   RangeBoundary::kRangeBoundarySmi);
-    }
-  }
-
-  ASSERT(new_min.IsUnknown() == new_max.IsUnknown());
-  if (new_min.IsUnknown()) {
-    range_ = Range::UnknownSmi();
-    return;
-  }
-
-  range_ = new Range(new_min, new_max);
-}
-
-
 bool PhiInstr::IsRedundant() const {
   ASSERT(InputCount() > 1);
   Definition* first = InputAt(0)->definition();
   for (intptr_t i = 1; i < InputCount(); ++i) {
     Definition* def = InputAt(i)->definition();
     if (def != first) return false;
   }
   return true;
 }
 
 
-static bool IsArrayLength(Definition* defn) {
-  if (defn == NULL) {
-    return false;
-  }
-  LoadFieldInstr* load = defn->AsLoadField();
-  return (load != NULL) && load->IsImmutableLengthLoad();
-}
-
-
-void BinarySmiOpInstr::InferRange() {
-  // TODO(vegorov): canonicalize BinarySmiOp to always have constant on the
-  // right and a non-constant on the left.
-  Definition* left_defn = left()->definition();
-
-  Range* left_range = left_defn->range();
-  Range* right_range = right()->definition()->range();
-
-  if ((left_range == NULL) || (right_range == NULL)) {
-    range_ = Range::UnknownSmi();
-    return;
-  }
-
-  Range* possible_range = Range::BinaryOp(op_kind(),
-                                          left_range,
-                                          right_range,
-                                          left_defn);
-
-  if ((range_ == NULL) && (possible_range == NULL)) {
-    // Initialize.
-    range_ = Range::UnknownSmi();
-    return;
-  }
-
-  if (possible_range == NULL) {
-    // Nothing new.
-    return;
-  }
-
-  range_ = possible_range;
-
-  ASSERT(!range_->min().IsUnknown() && !range_->max().IsUnknown());
-  // Calculate overflowed status before clamping.
-  const bool overflowed = range_->min().LowerBound().OverflowedSmi() ||
-                          range_->max().UpperBound().OverflowedSmi();
-  set_overflow(overflowed);
-
-  // Clamp value to be within smi range.
-  range_->Clamp(RangeBoundary::kRangeBoundarySmi);
-}
-
-
-void BinaryMintOpInstr::InferRange() {
-  // TODO(vegorov): canonicalize BinaryMintOpInstr to always have constant on
-  // the right and a non-constant on the left.
-  Definition* left_defn = left()->definition();
-
-  Range* left_range = left_defn->range();
-  Range* right_range = right()->definition()->range();
-
-  if ((left_range == NULL) || (right_range == NULL)) {
-    range_ = Range::Unknown();
-    return;
-  }
-
-  Range* possible_range = Range::BinaryOp(op_kind(),
-                                          left_range,
-                                          right_range,
-                                          left_defn);
-
-  if ((range_ == NULL) && (possible_range == NULL)) {
-    // Initialize.
-    range_ = Range::Unknown();
-    return;
-  }
-
-  if (possible_range == NULL) {
-    // Nothing new.
-    return;
-  }
-
-  range_ = possible_range;
-
-  ASSERT(!range_->min().IsUnknown() && !range_->max().IsUnknown());
-
-  // Calculate overflowed status before clamping.
-  const bool overflowed = range_->min().LowerBound().OverflowedMint() ||
-                          range_->max().UpperBound().OverflowedMint();
-  set_can_overflow(overflowed);
-
-  // Clamp value to be within mint range.
-  range_->Clamp(RangeBoundary::kRangeBoundaryInt64);
-}
-
-
-void ShiftMintOpInstr::InferRange() {
-  Definition* left_defn = left()->definition();
-
-  Range* left_range = left_defn->range();
-  Range* right_range = right()->definition()->range();
-
-  if ((left_range == NULL) || (right_range == NULL)) {
-    range_ = Range::Unknown();
-    return;
-  }
-
-  Range* possible_range = Range::BinaryOp(op_kind(),
-                                          left_range,
-                                          right_range,
-                                          left_defn);
-
-  if ((range_ == NULL) && (possible_range == NULL)) {
-    // Initialize.
-    range_ = Range::Unknown();
-    return;
-  }
-
-  if (possible_range == NULL) {
-    // Nothing new.
-    return;
-  }
-
-  range_ = possible_range;
-
-  ASSERT(!range_->min().IsUnknown() && !range_->max().IsUnknown());
-
-  // Calculate overflowed status before clamping.
-  const bool overflowed = range_->min().LowerBound().OverflowedMint() ||
-                          range_->max().UpperBound().OverflowedMint();
-  set_can_overflow(overflowed);
-
-  // Clamp value to be within mint range.
-  range_->Clamp(RangeBoundary::kRangeBoundaryInt64);
-}
-
-
-void BoxIntegerInstr::InferRange() {
-  Range* input_range = value()->definition()->range();
-  if (input_range != NULL) {
-    bool is_smi = !input_range->min().LowerBound().OverflowedSmi() &&
-                  !input_range->max().UpperBound().OverflowedSmi();
-    set_is_smi(is_smi);
-    // The output range is the same as the input range.
-    range_ = input_range;
-  }
-}
-
-
-bool Range::IsPositive() const {
-  if (min().IsNegativeInfinity()) {
-    return false;
-  }
-  if (min().LowerBound().ConstantValue() < 0) {
-    return false;
-  }
-  if (max().IsPositiveInfinity()) {
-    return true;
-  }
-  return max().UpperBound().ConstantValue() >= 0;
-}
-
-
-bool Range::OnlyLessThanOrEqualTo(int64_t val) const {
-  if (max().IsPositiveInfinity()) {
-    // Cannot be true.
-    return false;
-  }
-  if (max().UpperBound().ConstantValue() > val) {
-    // Not true.
-    return false;
-  }
-  return true;
-}
-
-
-bool Range::OnlyGreaterThanOrEqualTo(int64_t val) const {
-  if (min().IsNegativeInfinity()) {
-    return false;
-  }
-  if (min().LowerBound().ConstantValue() < val) {
-    return false;
-  }
-  return true;
-}
-
-
-// Inclusive.
-bool Range::IsWithin(int64_t min_int, int64_t max_int) const {
-  RangeBoundary lower_min = min().LowerBound();
-  if (lower_min.IsNegativeInfinity() || (lower_min.ConstantValue() < min_int)) {
-    return false;
-  }
-  RangeBoundary upper_max = max().UpperBound();
-  if (upper_max.IsPositiveInfinity() || (upper_max.ConstantValue() > max_int)) {
-    return false;
-  }
-  return true;
-}
-
-
-bool Range::Overlaps(int64_t min_int, int64_t max_int) const {
-  RangeBoundary lower = min().LowerBound();
-  RangeBoundary upper = max().UpperBound();
-  const int64_t this_min = lower.IsNegativeInfinity() ?
-      RangeBoundary::kMin : lower.ConstantValue();
-  const int64_t this_max = upper.IsPositiveInfinity() ?
-      RangeBoundary::kMax : upper.ConstantValue();
-  if ((this_min <= min_int) && (min_int <= this_max)) return true;
-  if ((this_min <= max_int) && (max_int <= this_max)) return true;
-  if ((min_int < this_min) && (max_int > this_max)) return true;
-  return false;
-}
-
-
-bool Range::IsUnsatisfiable() const {
-  // Infinity case: [+inf, ...] || [..., -inf]
-  if (min().IsPositiveInfinity() || max().IsNegativeInfinity()) {
-    return true;
-  }
-  // Constant case: For example [0, -1].
-  if (Range::ConstantMin(this).ConstantValue() >
-      Range::ConstantMax(this).ConstantValue()) {
-    return true;
-  }
-  // Symbol case: For example [v+1, v].
-  if (DependOnSameSymbol(min(), max()) && min().offset() > max().offset()) {
-    return true;
-  }
-  return false;
-}
-
-
-void Range::Clamp(RangeBoundary::RangeSize size) {
-  min_ = min_.Clamp(size);
-  max_ = max_.Clamp(size);
-}
-
-
-void Range::Shl(const Range* left,
-                const Range* right,
-                RangeBoundary* result_min,
-                RangeBoundary* result_max) {
-  ASSERT(left != NULL);
-  ASSERT(right != NULL);
-  ASSERT(result_min != NULL);
-  ASSERT(result_max != NULL);
-  RangeBoundary left_max = Range::ConstantMax(left);
-  RangeBoundary left_min = Range::ConstantMin(left);
-  // A negative shift count always deoptimizes (and throws), so the minimum
-  // shift count is zero.
-  int64_t right_max = Utils::Maximum(Range::ConstantMax(right).ConstantValue(),
-                                     static_cast<int64_t>(0));
-  int64_t right_min = Utils::Maximum(Range::ConstantMin(right).ConstantValue(),
-                                     static_cast<int64_t>(0));
-
-  *result_min = RangeBoundary::Shl(
-      left_min,
-      left_min.ConstantValue() > 0 ? right_min : right_max,
-      left_min.ConstantValue() > 0
-          ? RangeBoundary::PositiveInfinity()
-          : RangeBoundary::NegativeInfinity());
-
-  *result_max = RangeBoundary::Shl(
-      left_max,
-      left_max.ConstantValue() > 0 ? right_max : right_min,
-      left_max.ConstantValue() > 0
-          ? RangeBoundary::PositiveInfinity()
-          : RangeBoundary::NegativeInfinity());
-}
-
-
-void Range::Shr(const Range* left,
-                const Range* right,
-                RangeBoundary* result_min,
-                RangeBoundary* result_max) {
-  RangeBoundary left_max = Range::ConstantMax(left);
-  RangeBoundary left_min = Range::ConstantMin(left);
-  // A negative shift count always deoptimizes (and throws), so the minimum
-  // shift count is zero.
-  int64_t right_max = Utils::Maximum(Range::ConstantMax(right).ConstantValue(),
-                                     static_cast<int64_t>(0));
-  int64_t right_min = Utils::Maximum(Range::ConstantMin(right).ConstantValue(),
-                                     static_cast<int64_t>(0));
-
-  *result_min = RangeBoundary::Shr(
-      left_min,
-      left_min.ConstantValue() > 0 ? right_max : right_min);
-
-  *result_max = RangeBoundary::Shr(
-      left_max,
-      left_max.ConstantValue() > 0 ? right_min : right_max);
-}
-
-
-bool Range::And(const Range* left_range,
-                const Range* right_range,
-                RangeBoundary* result_min,
-                RangeBoundary* result_max) {
-  ASSERT(left_range != NULL);
-  ASSERT(right_range != NULL);
-  ASSERT(result_min != NULL);
-  ASSERT(result_max != NULL);
-
-  if (Range::ConstantMin(right_range).ConstantValue() >= 0) {
-    *result_min = RangeBoundary::FromConstant(0);
-    *result_max = Range::ConstantMax(right_range);
-    return true;
-  }
-
-  if (Range::ConstantMin(left_range).ConstantValue() >= 0) {
-    *result_min = RangeBoundary::FromConstant(0);
-    *result_max = Range::ConstantMax(left_range);
-    return true;
-  }
-
-  return false;
-}
-
-
-void Range::Add(const Range* left_range,
-                const Range* right_range,
-                RangeBoundary* result_min,
-                RangeBoundary* result_max,
-                Definition* left_defn) {
-  ASSERT(left_range != NULL);
-  ASSERT(right_range != NULL);
-  ASSERT(result_min != NULL);
-  ASSERT(result_max != NULL);
-
-  RangeBoundary left_min =
-    IsArrayLength(left_defn) ?
-        RangeBoundary::FromDefinition(left_defn) : left_range->min();
-
-  RangeBoundary left_max =
-    IsArrayLength(left_defn) ?
-        RangeBoundary::FromDefinition(left_defn) : left_range->max();
-
-  if (!RangeBoundary::SymbolicAdd(left_min, right_range->min(), result_min)) {
-    *result_min = RangeBoundary::Add(left_range->min().LowerBound(),
-                                     right_range->min().LowerBound(),
-                                     RangeBoundary::NegativeInfinity());
-  }
-  if (!RangeBoundary::SymbolicAdd(left_max, right_range->max(), result_max)) {
-    *result_max = RangeBoundary::Add(right_range->max().UpperBound(),
-                                     left_range->max().UpperBound(),
-                                     RangeBoundary::PositiveInfinity());
-  }
-}
-
-
-void Range::Sub(const Range* left_range,
-                const Range* right_range,
-                RangeBoundary* result_min,
-                RangeBoundary* result_max,
-                Definition* left_defn) {
-  ASSERT(left_range != NULL);
-  ASSERT(right_range != NULL);
-  ASSERT(result_min != NULL);
-  ASSERT(result_max != NULL);
-
-  RangeBoundary left_min =
-    IsArrayLength(left_defn) ?
-        RangeBoundary::FromDefinition(left_defn) : left_range->min();
-
-  RangeBoundary left_max =
-    IsArrayLength(left_defn) ?
-        RangeBoundary::FromDefinition(left_defn) : left_range->max();
-
-  if (!RangeBoundary::SymbolicSub(left_min, right_range->max(), result_min)) {
-    *result_min = RangeBoundary::Sub(left_range->min().LowerBound(),
-                              right_range->max().UpperBound(),
-                              RangeBoundary::NegativeInfinity());
-  }
-  if (!RangeBoundary::SymbolicSub(left_max, right_range->min(), result_max)) {
-    *result_max = RangeBoundary::Sub(left_range->max().UpperBound(),
-                                     right_range->min().LowerBound(),
-                                     RangeBoundary::PositiveInfinity());
-  }
-}
-
-
-bool Range::Mul(const Range* left_range,
-                const Range* right_range,
-                RangeBoundary* result_min,
-                RangeBoundary* result_max) {
-  ASSERT(left_range != NULL);
-  ASSERT(right_range != NULL);
-  ASSERT(result_min != NULL);
-  ASSERT(result_max != NULL);
-
-  const int64_t left_max = ConstantAbsMax(left_range);
-  const int64_t right_max = ConstantAbsMax(right_range);
-  if ((left_max <= -kSmiMin) && (right_max <= -kSmiMin) &&
-      ((left_max == 0) || (right_max <= kMaxInt64 / left_max))) {
-    // Product of left and right max values stays in 64 bit range.
-    const int64_t mul_max = left_max * right_max;
-    if (Smi::IsValid(mul_max) && Smi::IsValid(-mul_max)) {
-      const int64_t r_min =
-          OnlyPositiveOrZero(*left_range, *right_range) ? 0 : -mul_max;
-      *result_min = RangeBoundary::FromConstant(r_min);
-      const int64_t r_max =
-          OnlyNegativeOrZero(*left_range, *right_range) ? 0 : mul_max;
-      *result_max = RangeBoundary::FromConstant(r_max);
-      return true;
-    }
-  }
-  return false;
-}
-
-
-// Both the a and b ranges are >= 0.
-bool Range::OnlyPositiveOrZero(const Range& a, const Range& b) {
-  return a.OnlyGreaterThanOrEqualTo(0) && b.OnlyGreaterThanOrEqualTo(0);
-}
-
-
-// Both the a and b ranges are <= 0.
-bool Range::OnlyNegativeOrZero(const Range& a, const Range& b) {
-  return a.OnlyLessThanOrEqualTo(0) && b.OnlyLessThanOrEqualTo(0);
-}
-
-
-// Return the maximum absolute value included in range.
-int64_t Range::ConstantAbsMax(const Range* range) {
-  if (range == NULL) {
-    return RangeBoundary::kMax;
-  }
-  const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).ConstantValue());
-  const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).ConstantValue());
-  return Utils::Maximum(abs_min, abs_max);
-}
-
-
-Range* Range::BinaryOp(const Token::Kind op,
-                       const Range* left_range,
-                       const Range* right_range,
-                       Definition* left_defn) {
-  ASSERT(left_range != NULL);
-  ASSERT(right_range != NULL);
-
-  // Both left and right ranges are finite.
-  ASSERT(left_range->IsFinite());
-  ASSERT(right_range->IsFinite());
-
-  RangeBoundary min;
-  RangeBoundary max;
-  ASSERT(min.IsUnknown() && max.IsUnknown());
-
-  switch (op) {
-    case Token::kADD:
-      Range::Add(left_range, right_range, &min, &max, left_defn);
-      break;
-    case Token::kSUB:
-      Range::Sub(left_range, right_range, &min, &max, left_defn);
-      break;
-    case Token::kMUL: {
-      if (!Range::Mul(left_range, right_range, &min, &max)) {
-        return NULL;
-      }
-      break;
-    }
-    case Token::kSHL: {
-      Range::Shl(left_range, right_range, &min, &max);
-      break;
-    }
-    case Token::kSHR: {
-      Range::Shr(left_range, right_range, &min, &max);
-      break;
-    }
-    case Token::kBIT_AND:
-      if (!Range::And(left_range, right_range, &min, &max)) {
-        return NULL;
-      }
-      break;
-    default:
-      return NULL;
-      break;
-  }
-
-  ASSERT(!min.IsUnknown() && !max.IsUnknown());
-
-  return new Range(min, max);
-}
-
-
 bool CheckArrayBoundInstr::IsFixedLengthArrayType(intptr_t cid) {
   return LoadFieldInstr::IsFixedLengthArrayCid(cid);
 }
 
 
-bool CheckArrayBoundInstr::IsRedundant(RangeBoundary length) {
-  Range* index_range = index()->definition()->range();
-
-  // Range of the index is unknown can't decide if the check is redundant.
-  if (index_range == NULL) {
-    return false;
-  }
-
-  // Range of the index is not positive. Check can't be redundant.
-  if (Range::ConstantMinSmi(index_range).ConstantValue() < 0) {
-    return false;
-  }
-
-  RangeBoundary max = CanonicalizeBoundary(index_range->max(),
-                                           RangeBoundary::PositiveInfinity());
-
-  if (max.OverflowedSmi()) {
-    return false;
-  }
-
-
-  RangeBoundary max_upper = max.UpperBound();
-  RangeBoundary length_lower = length.LowerBound();
-
-  if (max_upper.OverflowedSmi() || length_lower.OverflowedSmi()) {
-    return false;
-  }
-
-  // Try to compare constant boundaries.
-  if (max_upper.ConstantValue() < length_lower.ConstantValue()) {
-    return true;
-  }
-
-  length = CanonicalizeBoundary(length, RangeBoundary::PositiveInfinity());
-  if (length.OverflowedSmi()) {
-    return false;
-  }
-
-  // Try symbolic comparison.
-  do {
-    if (DependOnSameSymbol(max, length)) return max.offset() < length.offset();
-  } while (CanonicalizeMaxBoundary(&max) || CanonicalizeMinBoundary(&length));
-
-  // Failed to prove that maximum is bounded with array length.
-  return false;
-}
-
-
 Instruction* CheckArrayBoundInstr::Canonicalize(FlowGraph* flow_graph) {
   return IsRedundant(RangeBoundary::FromDefinition(length()->definition())) ?
       NULL : this;
 }
 
 
 intptr_t CheckArrayBoundInstr::LengthOffsetFor(intptr_t class_id) {
   if (RawObject::IsExternalTypedDataClassId(class_id)) {
     return ExternalTypedData::length_offset();
   }
@@ skipping 259 matching lines @@
     case Token::kTRUNCDIV: return 0;
     case Token::kMOD: return 1;
     default: UNIMPLEMENTED(); return -1;
   }
 }
 
 
 #undef __
 
 }  // namespace dart