[turbofan] Use range types to type and lower arithmetic ops.

src/compiler/typer.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/bootstrapper.h"
 #include "src/compiler/graph-inl.h"
 #include "src/compiler/js-operator.h"
 #include "src/compiler/node.h"
 #include "src/compiler/node-properties-inl.h"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/simplified-operator.h"
 #include "src/compiler/typer.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 class Typer::Decorator : public GraphDecorator {
  public:
   explicit Decorator(Typer* typer) : typer_(typer) {}
   virtual void Decorate(Node* node);
 
  private:
   Typer* typer_;
 };
 
 
 Typer::Typer(Graph* graph, MaybeHandle<Context> context)
-    : graph_(graph), context_(context), decorator_(NULL) {
+    : graph_(graph),
+      context_(context),
+      decorator_(NULL),
+      weaken_min_limits_(graph->zone()),
+      weaken_max_limits_(graph->zone()) {
   Zone* zone = this->zone();
   Factory* f = zone->isolate()->factory();
 
   Handle<Object> zero = f->NewNumber(0);
   Handle<Object> one = f->NewNumber(1);
-  Handle<Object> positive_infinity = f->NewNumber(+V8_INFINITY);
-  Handle<Object> negative_infinity = f->NewNumber(-V8_INFINITY);
+  Handle<Object> infinity = f->NewNumber(+V8_INFINITY);
+  Handle<Object> minusinfinity = f->NewNumber(-V8_INFINITY);
 
   negative_signed32 = Type::Union(
       Type::SignedSmall(), Type::OtherSigned32(), zone);
   non_negative_signed32 = Type::Union(
       Type::UnsignedSmall(), Type::OtherUnsigned31(), zone);
   undefined_or_null = Type::Union(Type::Undefined(), Type::Null(), zone);
   singleton_false = Type::Constant(f->false_value(), zone);
   singleton_true = Type::Constant(f->true_value(), zone);
   singleton_zero = Type::Range(zero, zero, zone);
   singleton_one = Type::Range(one, one, zone);
   zero_or_one = Type::Union(singleton_zero, singleton_one, zone);
   zeroish = Type::Union(
       singleton_zero, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone);
   falsish = Type::Union(Type::Undetectable(),
       Type::Union(zeroish, undefined_or_null, zone), zone);
-  integer = Type::Range(negative_infinity, positive_infinity, zone);
+  integer = Type::Range(minusinfinity, infinity, zone);
+  weakint = Type::Union(
+      integer, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone);
 
   Type* number = Type::Number();
   Type* signed32 = Type::Signed32();
   Type* unsigned32 = Type::Unsigned32();
   Type* integral32 = Type::Integral32();
   Type* object = Type::Object();
   Type* undefined = Type::Undefined();
-  Type* weakint = Type::Union(
-      integer, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone);
 
   number_fun0_ = Type::Function(number, zone);
   number_fun1_ = Type::Function(number, number, zone);
   number_fun2_ = Type::Function(number, number, number, zone);
   weakint_fun1_ = Type::Function(weakint, number, zone);
   imul_fun_ = Type::Function(signed32, integral32, integral32, zone);
   clz32_fun_ = Type::Function(
       Type::Range(zero, f->NewNumber(32), zone), number, zone);
   random_fun_ = Type::Function(Type::Union(
       Type::UnsignedSmall(), Type::OtherNumber(), zone), zone);
@@ skipping 34 matching lines @@
   array_buffer_fun_ = Type::Function(buffer, unsigned32, zone);
   int8_array_fun_ = Type::Function(int8_array, arg1, arg2, arg3, zone);
   int16_array_fun_ = Type::Function(int16_array, arg1, arg2, arg3, zone);
   int32_array_fun_ = Type::Function(int32_array, arg1, arg2, arg3, zone);
   uint8_array_fun_ = Type::Function(uint8_array, arg1, arg2, arg3, zone);
   uint16_array_fun_ = Type::Function(uint16_array, arg1, arg2, arg3, zone);
   uint32_array_fun_ = Type::Function(uint32_array, arg1, arg2, arg3, zone);
   float32_array_fun_ = Type::Function(float32_array, arg1, arg2, arg3, zone);
   float64_array_fun_ = Type::Function(float64_array, arg1, arg2, arg3, zone);
 
+  const int limits_count = 50;
+  weaken_min_limits_.reserve(limits_count + 1);
+  weaken_max_limits_.reserve(limits_count);
+
+  double limit = 1;

[rossberg, 2014/10/23 11:50:33]

Wouldn't it make sense to go a bit faster at first? There doesn't seem much
reason to single-step through the first 30 bits, you can probably fast forward
to 2^30 directly.

[Jarin, 2014/10/23 13:32:37]

Done.

+  weaken_min_limits_.push_back(f->NewNumber(0));
+  for (int i = 0; i < limits_count; i++) {
+    weaken_min_limits_.push_back(f->NewNumber(-limit));
+    weaken_max_limits_.push_back(f->NewNumber(limit - 1));
+    limit *= 2.0;
+  }
+
   decorator_ = new (zone) Decorator(this);
   graph_->AddDecorator(decorator_);
 }
 
 
 Typer::~Typer() {
   graph_->RemoveDecorator(decorator_);
 }
 
 
@@ skipping 32 matching lines @@
 
   Type* TypeConstant(Handle<Object> value);
 
  protected:
 #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node);
   DECLARE_METHOD(Start)
   VALUE_OP_LIST(DECLARE_METHOD)
 #undef DECLARE_METHOD
 
   Bounds BoundsOrNone(Node* node) {
-    return NodeProperties::IsTyped(node)
-        ? NodeProperties::GetBounds(node) : Bounds(Type::None(zone()));
+    return NodeProperties::IsTyped(node) ? NodeProperties::GetBounds(node)
+                                         : Bounds(Type::None());
   }
 
   Bounds Operand(Node* node, int i) {
     Node* operand_node = NodeProperties::GetValueInput(node, i);
     return BoundsOrNone(operand_node);
   }
 
   Bounds ContextOperand(Node* node) {
     Bounds result = BoundsOrNone(NodeProperties::GetContextInput(node));
     DCHECK(result.upper->Maybe(Type::Internal()));
     // TODO(rossberg): More precisely, instead of the above assertion, we should
     // back-propagate the constraint that it has to be a subtype of Internal.
     return result;
   }
 
+  Type* Weaken(Type::RangeType* previous, Type::RangeType* current);
+
   Zone* zone() { return typer_->zone(); }
   Isolate* isolate() { return typer_->isolate(); }
   Graph* graph() { return typer_->graph(); }
   MaybeHandle<Context> context() { return typer_->context(); }
 
  private:
   Typer* typer_;
   MaybeHandle<Context> context_;
 
   typedef Type* (*UnaryTyperFun)(Type*, Typer* t);
   typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t);
 
   Bounds TypeUnaryOp(Node* node, UnaryTyperFun);
   Bounds TypeBinaryOp(Node* node, BinaryTyperFun);
 
   static Type* Invert(Type*, Typer*);
   static Type* FalsifyUndefined(Type*, Typer*);
+  static Type* Rangify(Type*, Typer*);
 
   static Type* ToPrimitive(Type*, Typer*);
   static Type* ToBoolean(Type*, Typer*);
   static Type* ToNumber(Type*, Typer*);
   static Type* ToString(Type*, Typer*);
   static Type* NumberToInt32(Type*, Typer*);
   static Type* NumberToUint32(Type*, Typer*);
 
   static Type* JSAddRanger(Type::RangeType*, Type::RangeType*, Typer*);
   static Type* JSSubtractRanger(Type::RangeType*, Type::RangeType*, Typer*);
@@ skipping 33 matching lines @@
 };
 
 
 class Typer::NarrowVisitor : public Typer::Visitor {
  public:
   explicit NarrowVisitor(Typer* typer) : Visitor(typer) {}
 
   GenericGraphVisit::Control Pre(Node* node) {
     if (OperatorProperties::HasValueOutput(node->op())) {
       Bounds previous = NodeProperties::GetBounds(node);
-      Bounds bounds = TypeNode(node);
-      NodeProperties::SetBounds(node, Bounds::Both(bounds, previous, zone()));
-      DCHECK(bounds.Narrows(previous));
+      Bounds current = TypeNode(node);
+      NodeProperties::SetBounds(node, Bounds::Both(current, previous, zone()));
+      DCHECK(current.Narrows(previous));
       // Stop when nothing changed (but allow re-entry in case it does later).
-      return previous.Narrows(bounds)
-          ? GenericGraphVisit::DEFER : GenericGraphVisit::REENTER;
+      return previous.Narrows(current) ? GenericGraphVisit::DEFER
+                                       : GenericGraphVisit::REENTER;
     } else {
       return GenericGraphVisit::SKIP;
     }
   }
 
   GenericGraphVisit::Control Post(Node* node) {
     return GenericGraphVisit::REENTER;
   }
+
+ private:
+  // Returns the least integers-only supertype that's not a range.  If there is
+  // no such supertype, it returns Range(-inf, +inf) instead.
+  Type* MaybeWeaken(Type* current, Type* previous) {

[rossberg, 2014/10/23 11:50:33]

Move this to Typer::Visitor as protected, to avoid duplicating it.

[neis, 2014/10/23 12:43:06]

Also the comment no longer matches the code.

[Jarin, 2014/10/23 13:32:37]

Done.

+    if (current->IsRange() && previous->IsRange()) {
+      return Weaken(previous->AsRange(), current->AsRange());
+    }
+    return current;
+  }
 };
 
 
 class Typer::WidenVisitor : public Typer::Visitor {
  public:
   explicit WidenVisitor(Typer* typer) : Visitor(typer) {}
 
   GenericGraphVisit::Control Pre(Node* node) {
     if (OperatorProperties::HasValueOutput(node->op())) {
       Bounds previous = BoundsOrNone(node);
-      Bounds bounds = TypeNode(node);
-      DCHECK(previous.lower->Is(bounds.lower));
-      DCHECK(previous.upper->Is(bounds.upper));
-      NodeProperties::SetBounds(node, bounds);
+      Bounds current = TypeNode(node);
+
+      // Speed up termination in the presence of range types:
+      current.upper = MaybeWeaken(current.upper, previous.upper);
+      current.lower = MaybeWeaken(current.lower, previous.lower);
+
+      DCHECK(previous.lower->Is(current.lower));
+      DCHECK(previous.upper->Is(current.upper));
+
+      NodeProperties::SetBounds(node, current);
       // Stop when nothing changed (but allow re-entry in case it does later).
-      return bounds.Narrows(previous)
-          ? GenericGraphVisit::DEFER : GenericGraphVisit::REENTER;
+      return previous.Narrows(current) && current.Narrows(previous)
+                 ? GenericGraphVisit::DEFER
+                 : GenericGraphVisit::REENTER;
     } else {
       return GenericGraphVisit::SKIP;
     }
   }
 
   GenericGraphVisit::Control Post(Node* node) {
     return GenericGraphVisit::REENTER;
   }
+
+ private:
+  Type* MaybeWeaken(Type* current, Type* previous) {
+    if (current->IsRange() && previous->IsRange()) {
+      return Weaken(previous->AsRange(), current->AsRange());
+    }
+    return current;
+  }
 };
 
 
 void Typer::Run() {
   RunVisitor typing(this);
   graph_->VisitNodeInputsFromEnd(&typing);
   // Find least fixpoint.
   WidenVisitor widen(this);
   for (NodeSetIter it = typing.redo.begin(); it != typing.redo.end(); ++it) {
     graph_->VisitNodeUsesFrom(*it, &widen);
@@ skipping 70 matching lines @@
   return type;
 }
 
 
 Type* Typer::Visitor::FalsifyUndefined(Type* type, Typer* t) {
   if (type->Is(Type::Undefined())) return t->singleton_false;
   return type;
 }
 
 
+Type* Typer::Visitor::Rangify(Type* type, Typer* t) {
+  if (!type->Is(t->integer)) return type;  // Give up.
+  if (type->IsRange()) return type;        // Shortcut.

[rossberg, 2014/10/23 11:50:33]

Nit: put this first.

[Jarin, 2014/10/23 13:32:37]

Done.

+  Factory* f = t->isolate()->factory();
+  return Type::Range(f->NewNumber(type->Min()), f->NewNumber(type->Max()),
+                     t->zone());
+}
+
+
 // Type conversion.
 
 
 Type* Typer::Visitor::ToPrimitive(Type* type, Typer* t) {
   if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) {
     return type;
   }
   return Type::Primitive();
 }
 
@@ skipping 54 matching lines @@
 
 // Common operators.
 
 
 Bounds Typer::Visitor::TypeParameter(Node* node) {
   return Bounds::Unbounded(zone());
 }
 
 
 Bounds Typer::Visitor::TypeInt32Constant(Node* node) {
-  Factory* f = zone()->isolate()->factory();
+  Factory* f = isolate()->factory();
   Handle<Object> number = f->NewNumber(OpParameter<int32_t>(node));
   return Bounds(Type::Intersect(
       Type::Range(number, number, zone()), Type::UntaggedInt32(), zone()));
 }
 
 
 Bounds Typer::Visitor::TypeInt64Constant(Node* node) {
   return Bounds(Type::Internal());  // TODO(rossberg): Add int64 bitset type?
 }
 
 
 Bounds Typer::Visitor::TypeFloat32Constant(Node* node) {
   return Bounds(Type::Intersect(
       Type::Of(OpParameter<float>(node), zone()),
       Type::UntaggedFloat32(), zone()));
 }
 
 
 Bounds Typer::Visitor::TypeFloat64Constant(Node* node) {
   return Bounds(Type::Intersect(
       Type::Of(OpParameter<double>(node), zone()),
       Type::UntaggedFloat64(), zone()));
 }
 
 
 Bounds Typer::Visitor::TypeNumberConstant(Node* node) {
-  Factory* f = zone()->isolate()->factory();
+  Factory* f = isolate()->factory();
   return Bounds(Type::Constant(
       f->NewNumber(OpParameter<double>(node)), zone()));
 }
 
 
 Bounds Typer::Visitor::TypeHeapConstant(Node* node) {
   return Bounds(TypeConstant(OpParameter<Unique<Object> >(node).handle()));
 }
 
 
@@ skipping 156 matching lines @@
 Type* Typer::Visitor::JSGreaterThanOrEqualTyper(
     Type* lhs, Type* rhs, Typer* t) {
   return FalsifyUndefined(Invert(JSCompareTyper(lhs, rhs, t), t), t);
 }
 
 
 // JS bitwise operators.
 
 
 Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs, Type* rhs, Typer* t) {
-  Factory* f = t->zone()->isolate()->factory();
+  Factory* f = t->isolate()->factory();
   lhs = NumberToInt32(ToNumber(lhs, t), t);
   rhs = NumberToInt32(ToNumber(rhs, t), t);
   double lmin = lhs->Min();
   double rmin = rhs->Min();
   double lmax = lhs->Max();
   double rmax = rhs->Max();
   // Or-ing any two values results in a value no smaller than their minimum.
   // Even no smaller than their maximum if both values are non-negative.
   Handle<Object> min = f->NewNumber(
       lmin >= 0 && rmin >= 0 ? std::max(lmin, rmin) : std::min(lmin, rmin));
   if (lmax < 0 || rmax < 0) {
     // Or-ing two values of which at least one is negative results in a negative
     // value.
     Handle<Object> max = f->NewNumber(-1);
     return Type::Range(min, max, t->zone());
   }
   Handle<Object> max = f->NewNumber(Type::Signed32()->Max());
   return Type::Range(min, max, t->zone());
   // TODO(neis): Be precise for singleton inputs, here and elsewhere.
 }
 
 
 Type* Typer::Visitor::JSBitwiseAndTyper(Type* lhs, Type* rhs, Typer* t) {
-  Factory* f = t->zone()->isolate()->factory();
+  Factory* f = t->isolate()->factory();
   lhs = NumberToInt32(ToNumber(lhs, t), t);
   rhs = NumberToInt32(ToNumber(rhs, t), t);
   double lmin = lhs->Min();
   double rmin = rhs->Min();
   double lmax = lhs->Max();
   double rmax = rhs->Max();
   // And-ing any two values results in a value no larger than their maximum.
   // Even no larger than their minimum if both values are non-negative.
   Handle<Object> max = f->NewNumber(
       lmin >= 0 && rmin >= 0 ? std::min(lmax, rmax) : std::max(lmax, rmax));
@@ skipping 27 matching lines @@
 }
 
 
 Type* Typer::Visitor::JSShiftLeftTyper(Type* lhs, Type* rhs, Typer* t) {
   return Type::Signed32();
 }
 
 
 Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) {
   lhs = NumberToInt32(ToNumber(lhs, t), t);
-  Factory* f = t->zone()->isolate()->factory();
+  Factory* f = t->isolate()->factory();
   if (lhs->Min() >= 0) {
     // Right-shifting a non-negative value cannot make it negative, nor larger.
     Handle<Object> min = f->NewNumber(0);
     Handle<Object> max = f->NewNumber(lhs->Max());
     return Type::Range(min, max, t->zone());
   }
   if (lhs->Max() < 0) {
     // Right-shifting a negative value cannot make it non-negative, nor smaller.
     Handle<Object> min = f->NewNumber(lhs->Min());
     Handle<Object> max = f->NewNumber(-1);
     return Type::Range(min, max, t->zone());
   }
   return Type::Signed32();
 }
 
 
 Type* Typer::Visitor::JSShiftRightLogicalTyper(Type* lhs, Type* rhs, Typer* t) {
   lhs = NumberToUint32(ToNumber(lhs, t), t);
-  Factory* f = t->zone()->isolate()->factory();
+  Factory* f = t->isolate()->factory();
   // Logical right-shifting any value cannot make it larger.
   Handle<Object> min = f->NewNumber(0);
   Handle<Object> max = f->NewNumber(lhs->Max());
   return Type::Range(min, max, t->zone());
 }
 
 
 // JS arithmetic operators.
 
 
+// Returns the array's least element, ignoring NaN.
+// There must be at least one non-NaN element.
+// Any -0 is converted to 0.
+static double array_min(double a[], size_t n) {
+  DCHECK(n != 0);
+  double x = a[0];

[rossberg, 2014/10/23 11:50:33]

What if this is already a NaN? As discussed offline, as a fix you could
initialise with -inf and start the loop from 0.

[neis, 2014/10/23 12:43:06]

If x is nan initially, the result of the first min() will be whatever the first
argument is, i.e. not nan.

So I think the code is correct, although I also admit it's not the clearest.

[Jarin, 2014/10/23 13:32:37]

Done.

+  for (size_t i = 1; i < n; ++i) {
+    x = std::min(std::isnan(a[i]) ? +V8_INFINITY : a[i], x);

[rossberg, 2014/10/23 11:50:33]

Simplify to

  if (!std::isnan(a[i])) x = std::min(x, a[i]);

[Jarin, 2014/10/23 13:32:37]

Done.

+  }
+  DCHECK(!std::isnan(x));
+  return x == 0 ? 0 : x;  // -0 -> 0
+}
+
+
+// Returns the array's greatest element, ignoring NaN.
+// There must be at least one non-NaN element.
+// Any -0 is converted to 0.
+static double array_max(double a[], size_t n) {

[rossberg, 2014/10/23 11:50:33]

Same here.

[Jarin, 2014/10/23 13:32:37]

Done.

+  DCHECK(n != 0);
+  double x = a[0];
+  for (size_t i = 1; i < n; ++i) {
+    x = std::max(std::isnan(a[i]) ? -V8_INFINITY : a[i], x);
+  }
+  DCHECK(!std::isnan(x));
+  return x == 0 ? 0 : x;  // -0 -> 0
+}
+
+
+Type* Typer::Visitor::JSAddRanger(Type::RangeType* lhs, Type::RangeType* rhs,
+                                  Typer* t) {
+  double results[4];
+  results[0] = lhs->Min()->Number() + rhs->Min()->Number();
+  results[1] = lhs->Min()->Number() + rhs->Max()->Number();
+  results[2] = lhs->Max()->Number() + rhs->Min()->Number();
+  results[3] = lhs->Max()->Number() + rhs->Max()->Number();
+  // Since none of the inputs can be -0, the result cannot be -0 either.
+  // However, it can be nan (the sum of two infinities of opposite sign).
+  // On the other hand, if none of the "results" above is nan, then the actual
+  // result cannot be nan either.
+  int nans = 0;
+  for (int i = 0; i < 4; ++i) {
+    if (std::isnan(results[i])) ++nans;
+  }
+  if (nans == 4) return Type::NaN();  // [-inf..-inf] + [inf..inf] or vice versa
+  Factory* f = t->isolate()->factory();
+  Type* range = Type::Range(f->NewNumber(array_min(results, 4)),
+                            f->NewNumber(array_max(results, 4)), t->zone());
+  return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone());
+  // Examples:
+  //   [-inf, -inf] + [+inf, +inf] = NaN
+  //   [-inf, -inf] + [n, +inf] = [-inf, -inf] \/ NaN
+  //   [-inf, +inf] + [n, +inf] = [-inf, +inf] \/ NaN
+  //   [-inf, m] + [n, +inf] = [-inf, +inf] \/ NaN
+}
+
+
 Type* Typer::Visitor::JSAddTyper(Type* lhs, Type* rhs, Typer* t) {
   lhs = ToPrimitive(lhs, t);
   rhs = ToPrimitive(rhs, t);
   if (lhs->Maybe(Type::String()) || rhs->Maybe(Type::String())) {
     if (lhs->Is(Type::String()) || rhs->Is(Type::String())) {
       return Type::String();
     } else {
       return Type::NumberOrString();
     }
   }
-  lhs = ToNumber(lhs, t);
-  rhs = ToNumber(rhs, t);
+  lhs = Rangify(ToNumber(lhs, t), t);
+  rhs = Rangify(ToNumber(rhs, t), t);
   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
-  // TODO(neis): Do some analysis.
+  if (lhs->IsRange() && rhs->IsRange()) {
+    return JSAddRanger(lhs->AsRange(), rhs->AsRange(), t);
+  }
   // TODO(neis): Deal with numeric bitsets here and elsewhere.

[rossberg, 2014/10/23 11:50:33]

This seems to be subsumed by Rangify.

[neis, 2014/10/23 12:43:06]

Rangify converts a union of integer constants and possibly a range to a range. 
Its result is always a supertype of its argument.  It does not deal with
bitsets, although it might be possible to do that here as well.

   return Type::Number();
 }
 
 
+Type* Typer::Visitor::JSSubtractRanger(Type::RangeType* lhs,
+                                       Type::RangeType* rhs, Typer* t) {
+  double results[4];
+  results[0] = lhs->Min()->Number() - rhs->Min()->Number();
+  results[1] = lhs->Min()->Number() - rhs->Max()->Number();
+  results[2] = lhs->Max()->Number() - rhs->Min()->Number();
+  results[3] = lhs->Max()->Number() - rhs->Max()->Number();
+  // Since none of the inputs can be -0, the result cannot be -0.
+  // However, it can be nan (the subtraction of two infinities of same sign).
+  // On the other hand, if none of the "results" above is nan, then the actual
+  // result cannot be nan either.
+  int nans = 0;
+  for (int i = 0; i < 4; ++i) {
+    if (std::isnan(results[i])) ++nans;
+  }
+  if (nans == 4) return Type::NaN();  // [inf..inf] - [inf..inf] (all same sign)
+  Factory* f = t->isolate()->factory();
+  Type* range = Type::Range(f->NewNumber(array_min(results, 4)),
+                            f->NewNumber(array_max(results, 4)), t->zone());
+  return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone());
+  // Examples:
+  //   [-inf, +inf] - [-inf, +inf] = [-inf, +inf] \/ NaN
+  //   [-inf, -inf] - [-inf, -inf] = NaN
+  //   [-inf, -inf] - [n, +inf] = [-inf, -inf] \/ NaN
+  //   [m, +inf] - [-inf, n] = [-inf, +inf] \/ NaN
+}
+
+
 Type* Typer::Visitor::JSSubtractTyper(Type* lhs, Type* rhs, Typer* t) {
-  lhs = ToNumber(lhs, t);
-  rhs = ToNumber(rhs, t);
+  lhs = Rangify(ToNumber(lhs, t), t);
+  rhs = Rangify(ToNumber(rhs, t), t);
   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
-  // TODO(neis): Do some analysis.
+  if (lhs->IsRange() && rhs->IsRange()) {
+    return JSSubtractRanger(lhs->AsRange(), rhs->AsRange(), t);
+  }
   return Type::Number();
 }
 
 
+Type* Typer::Visitor::JSMultiplyRanger(Type::RangeType* lhs,
+                                       Type::RangeType* rhs, Typer* t) {
+  double results[4];
+  double lmin = lhs->Min()->Number();
+  double lmax = lhs->Max()->Number();
+  double rmin = rhs->Min()->Number();
+  double rmax = rhs->Max()->Number();
+  results[0] = lmin * rmin;
+  results[1] = lmin * rmax;
+  results[2] = lmax * rmin;
+  results[3] = lmax * rmax;
+  // If the result may be nan, we give up on calculating a precise type, because
+  // the discontinuity makes it too complicated.  Note that even if none of the
+  // "results" above is nan, the actual result may still be, so we have to do a
+  // different check:
+  bool maybe_nan = (lhs->Maybe(t->singleton_zero) &&
+                    (rmin == -V8_INFINITY || rmax == +V8_INFINITY)) ||
+                   (rhs->Maybe(t->singleton_zero) &&
+                    (lmin == -V8_INFINITY || lmax == +V8_INFINITY));
+  if (maybe_nan) return t->weakint;  // Giving up.
+  bool maybe_minuszero = (lhs->Maybe(t->singleton_zero) && rmin < 0) ||
+                         (rhs->Maybe(t->singleton_zero) && lmin < 0);
+  Factory* f = t->isolate()->factory();
+  Type* range = Type::Range(f->NewNumber(array_min(results, 4)),
+                            f->NewNumber(array_max(results, 4)), t->zone());
+  return maybe_minuszero ? Type::Union(range, Type::MinusZero(), t->zone())
+                         : range;
+}
+
+
 Type* Typer::Visitor::JSMultiplyTyper(Type* lhs, Type* rhs, Typer* t) {
-  lhs = ToNumber(lhs, t);
-  rhs = ToNumber(rhs, t);
+  lhs = Rangify(ToNumber(lhs, t), t);
+  rhs = Rangify(ToNumber(rhs, t), t);
   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
-  // TODO(neis): Do some analysis.
+  if (lhs->IsRange() && rhs->IsRange()) {
+    return JSMultiplyRanger(lhs->AsRange(), rhs->AsRange(), t);
+  }
   return Type::Number();
 }
 
 
 Type* Typer::Visitor::JSDivideTyper(Type* lhs, Type* rhs, Typer* t) {
   lhs = ToNumber(lhs, t);
   rhs = ToNumber(rhs, t);
   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
-  // TODO(neis): Do some analysis.
-  return Type::Number();
+  // Division is tricky, so all we do is try ruling out nan.
+  // TODO(neis): try ruling out -0 as well?
+  bool maybe_nan =
+      lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN()) ||
+      rhs->Maybe(t->singleton_zero) ||

[rossberg, 2014/10/23 11:50:33]

I think this needs to check for -0 as well.

Also, instead of doing all the rhs->Maybe's separately, do one on a (predefined)
union type.

[neis, 2014/10/23 12:43:06]

Acknowledged.

[Jarin, 2014/10/23 13:32:37]

Done.

+      ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) &&
+       (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
+  return maybe_nan ? Type::Number() : Type::OrderedNumber();
 }
 
 
 Type* Typer::Visitor::JSModulusTyper(Type* lhs, Type* rhs, Typer* t) {
   lhs = ToNumber(lhs, t);
   rhs = ToNumber(rhs, t);
   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
-  // TODO(neis): Do some analysis.
-  return Type::Number();
+  // Division is tricky, so all we do is try ruling out nan.
+  // TODO(neis): try ruling out -0 as well?
+  bool maybe_nan =
+      lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN()) ||
+      rhs->Maybe(t->singleton_zero) ||

[rossberg, 2014/10/23 11:50:33]

Same here.

[Jarin, 2014/10/23 13:32:37]

Done.

+      ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) &&
+       (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
+  return maybe_nan ? Type::Number() : Type::OrderedNumber();
 }
 
 
 // JS unary operators.
 
 
 Type* Typer::Visitor::JSUnaryNotTyper(Type* type, Typer* t) {
   return Invert(ToBoolean(type, t), t);
 }
 
@@ skipping 57 matching lines @@
 Bounds Typer::Visitor::TypeJSLoadProperty(Node* node) {
   return TypeBinaryOp(node, JSLoadPropertyTyper);
 }
 
 
 Bounds Typer::Visitor::TypeJSLoadNamed(Node* node) {
   return Bounds::Unbounded(zone());
 }
 
 
+Type* Typer::Visitor::Weaken(Type::RangeType* previous,
+                             Type::RangeType* current) {
+  double current_min = current->Min()->Number();
+  double current_max = current->Max()->Number();
+
+  Handle<Object> new_min = current->Min();
+  Handle<Object> new_max = current->Max();
+
+  // Find the closest lower entry in the list of allowed
+  // minima (or negative infinity if there is no such entry).
+  if (current_min != previous->Min()->Number()) {
+    new_min = typer_->integer->AsRange()->Min();
+    for (auto i = typer_->weaken_min_limits_.begin();

[Benedikt Meurer, 2014/10/23 10:33:26]

range based for loops: for (const auto val : weaken_min_limits_) {...}

[Jarin, 2014/10/23 11:14:52]

Done.

+         i != typer_->weaken_min_limits_.end(); i++) {
+      if ((*i)->Number() <= current_min) {
+        new_min = *i;
+        break;
+      }
+    }
+  }
+
+  // Find the closest greater entry in the list of allowed
+  // maxima (or infinity if there is no such entry).
+  if (current_max != previous->Max()->Number()) {
+    new_max = typer_->integer->AsRange()->Max();
+    for (auto i = typer_->weaken_max_limits_.begin();

[Benedikt Meurer, 2014/10/23 10:33:26]

range based for loops: for (const auto val : weaken_max_limits_) {...}

[Jarin, 2014/10/23 11:14:52]

Done.

+         i != typer_->weaken_max_limits_.end(); i++) {
+      if ((*i)->Number() >= current_max) {
+        new_max = *i;
+        break;
+      }
+    }
+  }
+
+  return Type::Range(new_min, new_max, typer_->zone());
+}
+
+
 Bounds Typer::Visitor::TypeJSStoreProperty(Node* node) {
   UNREACHABLE();
   return Bounds();
 }
 
 
 Bounds Typer::Visitor::TypeJSStoreNamed(Node* node) {
   UNREACHABLE();
   return Bounds();
 }
@@ skipping 732 matching lines @@
         return typer_->float64_array_fun_;
       }
     }
   }
   return Type::Constant(value, zone());
 }
 
 }
 }
 }  // namespace v8::internal::compiler