deps/v8/src/compiler/typer.cc

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/base/flags.h"
   6 #include "src/bootstrapper.h"
   7 #include "src/compiler/graph-reducer.h"
   8 #include "src/compiler/js-operator.h"
   9 #include "src/compiler/node.h"
  10 #include "src/compiler/node-properties.h"
  11 #include "src/compiler/simplified-operator.h"
  12 #include "src/compiler/typer.h"
  13
  14 namespace v8 {
  15 namespace internal {
  16 namespace compiler {
  17
  18 #define NATIVE_TYPES(V) \
  19   V(Int8)               \
  20   V(Uint8)              \
  21   V(Int16)              \
  22   V(Uint16)             \
  23   V(Int32)              \
  24   V(Uint32)             \
  25   V(Float32)            \
  26   V(Float64)
  27
  28 enum LazyCachedType {
  29   kNumberFunc0,
  30   kNumberFunc1,
  31   kNumberFunc2,
  32   kImulFunc,
  33   kClz32Func,
  34   kArrayBufferFunc,
  35 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
  36   k##Type, k##Type##Array, k##Type##ArrayFunc,
  37   TYPED_ARRAYS(TYPED_ARRAY_CASE)
  38 #undef TYPED_ARRAY_CASE
  39       kNumLazyCachedTypes
  40 };
  41
  42
  43 // Constructs and caches types lazily.
  44 // TODO(turbofan): these types could be globally cached or cached per isolate.
  45 class LazyTypeCache FINAL : public ZoneObject {
  46  public:
  47   explicit LazyTypeCache(Isolate* isolate, Zone* zone)
  48       : isolate_(isolate), zone_(zone) {
  49     memset(cache_, 0, sizeof(cache_));
  50   }
  51
  52   inline Type* Get(LazyCachedType type) {
  53     int index = static_cast<int>(type);
  54     DCHECK(index < kNumLazyCachedTypes);
  55     if (cache_[index] == NULL) cache_[index] = Create(type);
  56     return cache_[index];
  57   }
  58
  59  private:
  60   Type* Create(LazyCachedType type) {
  61     switch (type) {
  62       case kInt8:
  63         return CreateNative(CreateRange<int8_t>(), Type::UntaggedSigned8());
  64       case kUint8:
  65         return CreateNative(CreateRange<uint8_t>(), Type::UntaggedUnsigned8());
  66       case kInt16:
  67         return CreateNative(CreateRange<int16_t>(), Type::UntaggedSigned16());
  68       case kUint16:
  69         return CreateNative(CreateRange<uint16_t>(),
  70                             Type::UntaggedUnsigned16());
  71       case kInt32:
  72         return CreateNative(Type::Signed32(), Type::UntaggedSigned32());
  73       case kUint32:
  74         return CreateNative(Type::Unsigned32(), Type::UntaggedUnsigned32());
  75       case kFloat32:
  76         return CreateNative(Type::Number(), Type::UntaggedFloat32());
  77       case kFloat64:
  78         return CreateNative(Type::Number(), Type::UntaggedFloat64());
  79       case kUint8Clamped:
  80         return Get(kUint8);
  81       case kNumberFunc0:
  82         return Type::Function(Type::Number(), zone());
  83       case kNumberFunc1:
  84         return Type::Function(Type::Number(), Type::Number(), zone());
  85       case kNumberFunc2:
  86         return Type::Function(Type::Number(), Type::Number(), Type::Number(),
  87                               zone());
  88       case kImulFunc:
  89         return Type::Function(Type::Signed32(), Type::Integral32(),
  90                               Type::Integral32(), zone());
  91       case kClz32Func:
  92         return Type::Function(CreateRange(0, 32), Type::Number(), zone());
  93       case kArrayBufferFunc:
  94         return Type::Function(Type::Object(zone()), Type::Unsigned32(), zone());
  95 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
  96   case k##Type##Array:                                  \
  97     return CreateArray(Get(k##Type));                   \
  98   case k##Type##ArrayFunc:                              \
  99     return CreateArrayFunction(Get(k##Type##Array));
 100         TYPED_ARRAYS(TYPED_ARRAY_CASE)
 101 #undef TYPED_ARRAY_CASE
 102       case kNumLazyCachedTypes:
 103         break;
 104     }
 105     UNREACHABLE();
 106     return NULL;
 107   }
 108
 109   Type* CreateArray(Type* element) const {
 110     return Type::Array(element, zone());
 111   }
 112
 113   Type* CreateArrayFunction(Type* array) const {
 114     Type* arg1 = Type::Union(Type::Unsigned32(), Type::Object(), zone());
 115     Type* arg2 = Type::Union(Type::Unsigned32(), Type::Undefined(), zone());
 116     Type* arg3 = arg2;
 117     return Type::Function(array, arg1, arg2, arg3, zone());
 118   }
 119
 120   Type* CreateNative(Type* semantic, Type* representation) const {
 121     return Type::Intersect(semantic, representation, zone());
 122   }
 123
 124   template <typename T>
 125   Type* CreateRange() const {
 126     return CreateRange(std::numeric_limits<T>::min(),
 127                        std::numeric_limits<T>::max());
 128   }
 129
 130   Type* CreateRange(double min, double max) const {
 131     return Type::Range(min, max, zone());
 132   }
 133
 134   Factory* factory() const { return isolate()->factory(); }
 135   Isolate* isolate() const { return isolate_; }
 136   Zone* zone() const { return zone_; }
 137
 138   Type* cache_[kNumLazyCachedTypes];
 139   Isolate* isolate_;
 140   Zone* zone_;
 141 };
 142
 143
 144 class Typer::Decorator FINAL : public GraphDecorator {
 145  public:
 146   explicit Decorator(Typer* typer) : typer_(typer) {}
 147   void Decorate(Node* node, bool incomplete) FINAL;
 148
 149  private:
 150   Typer* typer_;
 151 };
 152
 153
 154 Typer::Typer(Isolate* isolate, Graph* graph, MaybeHandle<Context> context)
 155     : isolate_(isolate),
 156       graph_(graph),
 157       context_(context),
 158       decorator_(NULL),
 159       cache_(new (graph->zone()) LazyTypeCache(isolate, graph->zone())) {
 160   Zone* zone = this->zone();
 161   Factory* f = isolate->factory();
 162
 163   Handle<Object> infinity = f->NewNumber(+V8_INFINITY);
 164   Handle<Object> minusinfinity = f->NewNumber(-V8_INFINITY);
 165
 166   Type* number = Type::Number();
 167   Type* signed32 = Type::Signed32();
 168   Type* unsigned32 = Type::Unsigned32();
 169   Type* nan_or_minuszero = Type::Union(Type::NaN(), Type::MinusZero(), zone);
 170   Type* truncating_to_zero =
 171       Type::Union(Type::Union(Type::Constant(infinity, zone),
 172                               Type::Constant(minusinfinity, zone), zone),
 173                   nan_or_minuszero, zone);
 174
 175   boolean_or_number = Type::Union(Type::Boolean(), Type::Number(), zone);
 176   undefined_or_null = Type::Union(Type::Undefined(), Type::Null(), zone);
 177   undefined_or_number = Type::Union(Type::Undefined(), Type::Number(), zone);
 178   singleton_false = Type::Constant(f->false_value(), zone);
 179   singleton_true = Type::Constant(f->true_value(), zone);
 180   singleton_zero = Type::Range(0.0, 0.0, zone);
 181   singleton_one = Type::Range(1.0, 1.0, zone);
 182   zero_or_one = Type::Union(singleton_zero, singleton_one, zone);
 183   zeroish = Type::Union(singleton_zero, nan_or_minuszero, zone);
 184   signed32ish = Type::Union(signed32, truncating_to_zero, zone);
 185   unsigned32ish = Type::Union(unsigned32, truncating_to_zero, zone);
 186   falsish = Type::Union(Type::Undetectable(),
 187                         Type::Union(Type::Union(singleton_false, zeroish, zone),
 188                                     undefined_or_null, zone),
 189                         zone);
 190   truish = Type::Union(
 191       singleton_true,
 192       Type::Union(Type::DetectableReceiver(), Type::Symbol(), zone), zone);
 193   integer = Type::Range(-V8_INFINITY, V8_INFINITY, zone);
 194   weakint = Type::Union(integer, nan_or_minuszero, zone);
 195
 196   number_fun0_ = Type::Function(number, zone);
 197   number_fun1_ = Type::Function(number, number, zone);
 198   number_fun2_ = Type::Function(number, number, number, zone);
 199
 200   weakint_fun1_ = Type::Function(weakint, number, zone);
 201   random_fun_ = Type::Function(Type::OrderedNumber(), zone);
 202
 203   decorator_ = new (zone) Decorator(this);
 204   graph_->AddDecorator(decorator_);
 205 }
 206
 207
 208 Typer::~Typer() {
 209   graph_->RemoveDecorator(decorator_);
 210 }
 211
 212
 213 class Typer::Visitor : public Reducer {
 214  public:
 215   explicit Visitor(Typer* typer)
 216       : typer_(typer), weakened_nodes_(typer->zone()) {}
 217
 218   Reduction Reduce(Node* node) OVERRIDE {
 219     if (node->op()->ValueOutputCount() == 0) return NoChange();
 220     switch (node->opcode()) {
 221 #define DECLARE_CASE(x) \
 222   case IrOpcode::k##x:  \
 223     return UpdateBounds(node, TypeBinaryOp(node, x##Typer));
 224       JS_SIMPLE_BINOP_LIST(DECLARE_CASE)
 225 #undef DECLARE_CASE
 226
 227 #define DECLARE_CASE(x) \
 228   case IrOpcode::k##x:  \
 229     return UpdateBounds(node, Type##x(node));
 230       DECLARE_CASE(Start)
 231       // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST:
 232       COMMON_OP_LIST(DECLARE_CASE)
 233       SIMPLIFIED_OP_LIST(DECLARE_CASE)
 234       MACHINE_OP_LIST(DECLARE_CASE)
 235       JS_SIMPLE_UNOP_LIST(DECLARE_CASE)
 236       JS_OBJECT_OP_LIST(DECLARE_CASE)
 237       JS_CONTEXT_OP_LIST(DECLARE_CASE)
 238       JS_OTHER_OP_LIST(DECLARE_CASE)
 239 #undef DECLARE_CASE
 240
 241 #define DECLARE_CASE(x) case IrOpcode::k##x:
 242       DECLARE_CASE(End)
 243       INNER_CONTROL_OP_LIST(DECLARE_CASE)
 244 #undef DECLARE_CASE
 245       break;
 246     }
 247     return NoChange();
 248   }
 249
 250   Bounds TypeNode(Node* node) {
 251     switch (node->opcode()) {
 252 #define DECLARE_CASE(x) \
 253       case IrOpcode::k##x: return TypeBinaryOp(node, x##Typer);
 254       JS_SIMPLE_BINOP_LIST(DECLARE_CASE)
 255 #undef DECLARE_CASE
 256
 257 #define DECLARE_CASE(x) case IrOpcode::k##x: return Type##x(node);
 258       DECLARE_CASE(Start)
 259       // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST:
 260       COMMON_OP_LIST(DECLARE_CASE)
 261       SIMPLIFIED_OP_LIST(DECLARE_CASE)
 262       MACHINE_OP_LIST(DECLARE_CASE)
 263       JS_SIMPLE_UNOP_LIST(DECLARE_CASE)
 264       JS_OBJECT_OP_LIST(DECLARE_CASE)
 265       JS_CONTEXT_OP_LIST(DECLARE_CASE)
 266       JS_OTHER_OP_LIST(DECLARE_CASE)
 267 #undef DECLARE_CASE
 268
 269 #define DECLARE_CASE(x) case IrOpcode::k##x:
 270       DECLARE_CASE(End)
 271       INNER_CONTROL_OP_LIST(DECLARE_CASE)
 272 #undef DECLARE_CASE
 273       break;
 274     }
 275     UNREACHABLE();
 276     return Bounds();
 277   }
 278
 279   Type* TypeConstant(Handle<Object> value);
 280
 281  private:
 282   Typer* typer_;
 283   MaybeHandle<Context> context_;
 284   ZoneSet<NodeId> weakened_nodes_;
 285
 286 #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node);
 287   DECLARE_METHOD(Start)
 288   VALUE_OP_LIST(DECLARE_METHOD)
 289 #undef DECLARE_METHOD
 290
 291   Bounds BoundsOrNone(Node* node) {
 292     return NodeProperties::IsTyped(node) ? NodeProperties::GetBounds(node)
 293                                          : Bounds(Type::None());
 294   }
 295
 296   Bounds Operand(Node* node, int i) {
 297     Node* operand_node = NodeProperties::GetValueInput(node, i);
 298     return BoundsOrNone(operand_node);
 299   }
 300
 301   Bounds WrapContextBoundsForInput(Node* node);
 302   Type* Weaken(Node* node, Type* current_type, Type* previous_type);
 303
 304   Zone* zone() { return typer_->zone(); }
 305   Isolate* isolate() { return typer_->isolate(); }
 306   Graph* graph() { return typer_->graph(); }
 307   MaybeHandle<Context> context() { return typer_->context(); }
 308
 309   void SetWeakened(NodeId node_id) { weakened_nodes_.insert(node_id); }
 310   bool IsWeakened(NodeId node_id) {
 311     return weakened_nodes_.find(node_id) != weakened_nodes_.end();
 312   }
 313
 314   typedef Type* (*UnaryTyperFun)(Type*, Typer* t);
 315   typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t);
 316
 317   Bounds TypeUnaryOp(Node* node, UnaryTyperFun);
 318   Bounds TypeBinaryOp(Node* node, BinaryTyperFun);
 319
 320   enum ComparisonOutcomeFlags {
 321     kComparisonTrue = 1,
 322     kComparisonFalse = 2,
 323     kComparisonUndefined = 4
 324   };
 325   typedef base::Flags<ComparisonOutcomeFlags> ComparisonOutcome;
 326
 327   static ComparisonOutcome Invert(ComparisonOutcome, Typer*);
 328   static Type* Invert(Type*, Typer*);
 329   static Type* FalsifyUndefined(ComparisonOutcome, Typer*);
 330   static Type* Rangify(Type*, Typer*);
 331
 332   static Type* ToPrimitive(Type*, Typer*);
 333   static Type* ToBoolean(Type*, Typer*);
 334   static Type* ToNumber(Type*, Typer*);
 335   static Type* ToString(Type*, Typer*);
 336   static Type* NumberToInt32(Type*, Typer*);
 337   static Type* NumberToUint32(Type*, Typer*);
 338
 339   static Type* JSAddRanger(Type::RangeType*, Type::RangeType*, Typer*);
 340   static Type* JSSubtractRanger(Type::RangeType*, Type::RangeType*, Typer*);
 341   static Type* JSMultiplyRanger(Type::RangeType*, Type::RangeType*, Typer*);
 342   static Type* JSDivideRanger(Type::RangeType*, Type::RangeType*, Typer*);
 343   static Type* JSModulusRanger(Type::RangeType*, Type::RangeType*, Typer*);
 344
 345   static ComparisonOutcome JSCompareTyper(Type*, Type*, Typer*);
 346
 347 #define DECLARE_METHOD(x) static Type* x##Typer(Type*, Type*, Typer*);
 348   JS_SIMPLE_BINOP_LIST(DECLARE_METHOD)
 349 #undef DECLARE_METHOD
 350
 351   static Type* JSUnaryNotTyper(Type*, Typer*);
 352   static Type* JSLoadPropertyTyper(Type*, Type*, Typer*);
 353   static Type* JSCallFunctionTyper(Type*, Typer*);
 354
 355   Reduction UpdateBounds(Node* node, Bounds current) {
 356     if (NodeProperties::IsTyped(node)) {
 357       // Widen the bounds of a previously typed node.
 358       Bounds previous = NodeProperties::GetBounds(node);
 359       if (node->opcode() == IrOpcode::kPhi) {
 360         // Speed up termination in the presence of range types:
 361         current.upper = Weaken(node, current.upper, previous.upper);
 362         current.lower = Weaken(node, current.lower, previous.lower);
 363       }
 364
 365       // Types should not get less precise.
 366       DCHECK(previous.lower->Is(current.lower));
 367       DCHECK(previous.upper->Is(current.upper));
 368
 369       NodeProperties::SetBounds(node, current);
 370       if (!(previous.Narrows(current) && current.Narrows(previous))) {
 371         // If something changed, revisit all uses.
 372         return Changed(node);
 373       }
 374       return NoChange();
 375     } else {
 376       // No previous type, simply update the bounds.
 377       NodeProperties::SetBounds(node, current);
 378       return Changed(node);
 379     }
 380   }
 381 };
 382
 383
 384 void Typer::Run() {
 385   {
 386     // TODO(titzer): this is a hack. Reset types for interior nodes first.
 387     NodeDeque deque(zone());
 388     NodeMarker<bool> marked(graph(), 2);
 389     deque.push_front(graph()->end());
 390     marked.Set(graph()->end(), true);
 391     while (!deque.empty()) {
 392       Node* node = deque.front();
 393       deque.pop_front();
 394       // TODO(titzer): there shouldn't be a need to retype constants.
 395       if (node->op()->ValueOutputCount() > 0)
 396         NodeProperties::RemoveBounds(node);
 397       for (Node* input : node->inputs()) {
 398         if (!marked.Get(input)) {
 399           marked.Set(input, true);
 400           deque.push_back(input);
 401         }
 402       }
 403     }
 404   }
 405
 406   Visitor visitor(this);
 407   GraphReducer graph_reducer(graph(), zone());
 408   graph_reducer.AddReducer(&visitor);
 409   graph_reducer.ReduceGraph();
 410 }
 411
 412
 413 void Typer::Decorator::Decorate(Node* node, bool incomplete) {
 414   if (incomplete) return;
 415   if (node->op()->ValueOutputCount() > 0) {
 416     // Only eagerly type-decorate nodes with known input types.
 417     // Other cases will generally require a proper fixpoint iteration with Run.
 418     bool is_typed = NodeProperties::IsTyped(node);
 419     if (is_typed || NodeProperties::AllValueInputsAreTyped(node)) {
 420       Visitor typing(typer_);
 421       Bounds bounds = typing.TypeNode(node);
 422       if (is_typed) {
 423         bounds =
 424           Bounds::Both(bounds, NodeProperties::GetBounds(node), typer_->zone());
 425       }
 426       NodeProperties::SetBounds(node, bounds);
 427     }
 428   }
 429 }
 430
 431
 432 // -----------------------------------------------------------------------------
 433
 434 // Helper functions that lift a function f on types to a function on bounds,
 435 // and uses that to type the given node.  Note that f is never called with None
 436 // as an argument.
 437
 438
 439 Bounds Typer::Visitor::TypeUnaryOp(Node* node, UnaryTyperFun f) {
 440   Bounds input = Operand(node, 0);
 441   Type* upper =
 442       input.upper->IsInhabited() ? f(input.upper, typer_) : Type::None();
 443   Type* lower = input.lower->IsInhabited()
 444                     ? ((input.lower == input.upper || upper->IsConstant())
 445                            ? upper  // TODO(neis): Extend this to Range(x,x),
 446                                     // NaN, MinusZero, ...?
 447                            : f(input.lower, typer_))
 448                     : Type::None();
 449   // TODO(neis): Figure out what to do with lower bound.
 450   return Bounds(lower, upper);
 451 }
 452
 453
 454 Bounds Typer::Visitor::TypeBinaryOp(Node* node, BinaryTyperFun f) {
 455   Bounds left = Operand(node, 0);
 456   Bounds right = Operand(node, 1);
 457   Type* upper = left.upper->IsInhabited() && right.upper->IsInhabited()
 458                     ? f(left.upper, right.upper, typer_)
 459                     : Type::None();
 460   Type* lower =
 461       left.lower->IsInhabited() && right.lower->IsInhabited()
 462           ? (((left.lower == left.upper && right.lower == right.upper) ||
 463               upper->IsConstant())
 464                  ? upper
 465                  : f(left.lower, right.lower, typer_))
 466           : Type::None();
 467   // TODO(neis): Figure out what to do with lower bound.
 468   return Bounds(lower, upper);
 469 }
 470
 471
 472 Type* Typer::Visitor::Invert(Type* type, Typer* t) {
 473   DCHECK(type->Is(Type::Boolean()));
 474   DCHECK(type->IsInhabited());
 475   if (type->Is(t->singleton_false)) return t->singleton_true;
 476   if (type->Is(t->singleton_true)) return t->singleton_false;
 477   return type;
 478 }
 479
 480
 481 Typer::Visitor::ComparisonOutcome Typer::Visitor::Invert(
 482     ComparisonOutcome outcome, Typer* t) {
 483   ComparisonOutcome result(0);
 484   if ((outcome & kComparisonUndefined) != 0) result |= kComparisonUndefined;
 485   if ((outcome & kComparisonTrue) != 0) result |= kComparisonFalse;
 486   if ((outcome & kComparisonFalse) != 0) result |= kComparisonTrue;
 487   return result;
 488 }
 489
 490
 491 Type* Typer::Visitor::FalsifyUndefined(ComparisonOutcome outcome, Typer* t) {
 492   if ((outcome & kComparisonFalse) != 0 ||
 493       (outcome & kComparisonUndefined) != 0) {
 494     return (outcome & kComparisonTrue) != 0 ? Type::Boolean()
 495                                             : t->singleton_false;
 496   }
 497   // Type should be non empty, so we know it should be true.
 498   DCHECK((outcome & kComparisonTrue) != 0);
 499   return t->singleton_true;
 500 }
 501
 502
 503 Type* Typer::Visitor::Rangify(Type* type, Typer* t) {
 504   if (type->IsRange()) return type;        // Shortcut.
 505   if (!type->Is(t->integer) && !type->Is(Type::Integral32())) {
 506     return type;  // Give up on non-integer types.
 507   }
 508   double min = type->Min();
 509   double max = type->Max();
 510   // Handle the degenerate case of empty bitset types (such as
 511   // OtherUnsigned31 and OtherSigned32 on 64-bit architectures).
 512   if (std::isnan(min)) {
 513     DCHECK(std::isnan(max));
 514     return type;
 515   }
 516   return Type::Range(min, max, t->zone());
 517 }
 518
 519
 520 // Type conversion.
 521
 522
 523 Type* Typer::Visitor::ToPrimitive(Type* type, Typer* t) {
 524   if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) {
 525     return type;
 526   }
 527   return Type::Primitive();
 528 }
 529
 530
 531 Type* Typer::Visitor::ToBoolean(Type* type, Typer* t) {
 532   if (type->Is(Type::Boolean())) return type;
 533   if (type->Is(t->falsish)) return t->singleton_false;
 534   if (type->Is(t->truish)) return t->singleton_true;
 535   if (type->Is(Type::PlainNumber()) && (type->Max() < 0 || 0 < type->Min())) {
 536     return t->singleton_true;  // Ruled out nan, -0 and +0.
 537   }
 538   return Type::Boolean();
 539 }
 540
 541
 542 Type* Typer::Visitor::ToNumber(Type* type, Typer* t) {
 543   if (type->Is(Type::Number())) return type;
 544   if (type->Is(Type::Null())) return t->singleton_zero;
 545   if (type->Is(Type::Undefined())) return Type::NaN();
 546   if (type->Is(t->undefined_or_null)) {
 547     return Type::Union(Type::NaN(), t->singleton_zero, t->zone());
 548   }
 549   if (type->Is(t->undefined_or_number)) {
 550     return Type::Union(Type::Intersect(type, Type::Number(), t->zone()),
 551                        Type::NaN(), t->zone());
 552   }
 553   if (type->Is(t->singleton_false)) return t->singleton_zero;
 554   if (type->Is(t->singleton_true)) return t->singleton_one;
 555   if (type->Is(Type::Boolean())) return t->zero_or_one;
 556   if (type->Is(t->boolean_or_number)) {
 557     return Type::Union(Type::Intersect(type, Type::Number(), t->zone()),
 558                        t->zero_or_one, t->zone());
 559   }
 560   return Type::Number();
 561 }
 562
 563
 564 Type* Typer::Visitor::ToString(Type* type, Typer* t) {
 565   if (type->Is(Type::String())) return type;
 566   return Type::String();
 567 }
 568
 569
 570 Type* Typer::Visitor::NumberToInt32(Type* type, Typer* t) {
 571   // TODO(neis): DCHECK(type->Is(Type::Number()));
 572   if (type->Is(Type::Signed32())) return type;
 573   if (type->Is(t->zeroish)) return t->singleton_zero;
 574   if (type->Is(t->signed32ish)) {
 575     return Type::Intersect(Type::Union(type, t->singleton_zero, t->zone()),
 576                            Type::Signed32(), t->zone());
 577   }
 578   return Type::Signed32();
 579 }
 580
 581
 582 Type* Typer::Visitor::NumberToUint32(Type* type, Typer* t) {
 583   // TODO(neis): DCHECK(type->Is(Type::Number()));
 584   if (type->Is(Type::Unsigned32())) return type;
 585   if (type->Is(t->zeroish)) return t->singleton_zero;
 586   if (type->Is(t->unsigned32ish)) {
 587     return Type::Intersect(Type::Union(type, t->singleton_zero, t->zone()),
 588                            Type::Unsigned32(), t->zone());
 589   }
 590   return Type::Unsigned32();
 591 }
 592
 593
 594 // -----------------------------------------------------------------------------
 595
 596
 597 // Control operators.
 598
 599
 600 Bounds Typer::Visitor::TypeStart(Node* node) {
 601   return Bounds(Type::None(zone()), Type::Internal(zone()));
 602 }
 603
 604
 605 // Common operators.
 606
 607
 608 Bounds Typer::Visitor::TypeAlways(Node* node) {
 609   return Bounds(Type::None(zone()), Type::Boolean(zone()));
 610 }
 611
 612
 613 Bounds Typer::Visitor::TypeParameter(Node* node) {
 614   return Bounds::Unbounded(zone());
 615 }
 616
 617
 618 Bounds Typer::Visitor::TypeOsrValue(Node* node) {
 619   if (node->InputAt(0)->opcode() == IrOpcode::kOsrLoopEntry) {
 620     // Before deconstruction, OSR values have type {None} to avoid polluting
 621     // the types of phis and other nodes in the graph.
 622     return Bounds(Type::None(), Type::None());
 623   }
 624   if (NodeProperties::IsTyped(node)) {
 625     // After deconstruction, OSR values may have had a type explicitly set.
 626     return NodeProperties::GetBounds(node);
 627   }
 628   // Otherwise, be conservative.
 629   return Bounds::Unbounded(zone());
 630 }
 631
 632
 633 Bounds Typer::Visitor::TypeInt32Constant(Node* node) {
 634   double number = OpParameter<int32_t>(node);
 635   return Bounds(Type::Intersect(
 636       Type::Range(number, number, zone()), Type::UntaggedSigned32(), zone()));
 637 }
 638
 639
 640 Bounds Typer::Visitor::TypeInt64Constant(Node* node) {
 641   // TODO(rossberg): This actually seems to be a PointerConstant so far...
 642   return Bounds(Type::Internal());  // TODO(rossberg): Add int64 bitset type?
 643 }
 644
 645
 646 Bounds Typer::Visitor::TypeFloat32Constant(Node* node) {
 647   return Bounds(Type::Intersect(
 648       Type::Of(OpParameter<float>(node), zone()),
 649       Type::UntaggedFloat32(), zone()));
 650 }
 651
 652
 653 Bounds Typer::Visitor::TypeFloat64Constant(Node* node) {
 654   return Bounds(Type::Intersect(
 655       Type::Of(OpParameter<double>(node), zone()),
 656       Type::UntaggedFloat64(), zone()));
 657 }
 658
 659
 660 Bounds Typer::Visitor::TypeNumberConstant(Node* node) {
 661   Factory* f = isolate()->factory();
 662   return Bounds(Type::Constant(
 663       f->NewNumber(OpParameter<double>(node)), zone()));
 664 }
 665
 666
 667 Bounds Typer::Visitor::TypeHeapConstant(Node* node) {
 668   return Bounds(TypeConstant(OpParameter<Unique<HeapObject> >(node).handle()));
 669 }
 670
 671
 672 Bounds Typer::Visitor::TypeExternalConstant(Node* node) {
 673   return Bounds(Type::None(zone()), Type::Internal(zone()));
 674 }
 675
 676
 677 Bounds Typer::Visitor::TypeSelect(Node* node) {
 678   return Bounds::Either(Operand(node, 1), Operand(node, 2), zone());
 679 }
 680
 681
 682 Bounds Typer::Visitor::TypePhi(Node* node) {
 683   int arity = node->op()->ValueInputCount();
 684   Bounds bounds = Operand(node, 0);
 685   for (int i = 1; i < arity; ++i) {
 686     bounds = Bounds::Either(bounds, Operand(node, i), zone());
 687   }
 688   return bounds;
 689 }
 690
 691
 692 Bounds Typer::Visitor::TypeEffectPhi(Node* node) {
 693   UNREACHABLE();
 694   return Bounds();
 695 }
 696
 697
 698 Bounds Typer::Visitor::TypeEffectSet(Node* node) {
 699   UNREACHABLE();
 700   return Bounds();
 701 }
 702
 703
 704 Bounds Typer::Visitor::TypeValueEffect(Node* node) {
 705   UNREACHABLE();
 706   return Bounds();
 707 }
 708
 709
 710 Bounds Typer::Visitor::TypeFinish(Node* node) {
 711   return Operand(node, 0);
 712 }
 713
 714
 715 Bounds Typer::Visitor::TypeFrameState(Node* node) {
 716   // TODO(rossberg): Ideally FrameState wouldn't have a value output.
 717   return Bounds(Type::None(zone()), Type::Internal(zone()));
 718 }
 719
 720
 721 Bounds Typer::Visitor::TypeStateValues(Node* node) {
 722   return Bounds(Type::None(zone()), Type::Internal(zone()));
 723 }
 724
 725
 726 Bounds Typer::Visitor::TypeTypedStateValues(Node* node) {
 727   return Bounds(Type::None(zone()), Type::Internal(zone()));
 728 }
 729
 730
 731 Bounds Typer::Visitor::TypeCall(Node* node) {
 732   return Bounds::Unbounded(zone());
 733 }
 734
 735
 736 Bounds Typer::Visitor::TypeProjection(Node* node) {
 737   // TODO(titzer): use the output type of the input to determine the bounds.
 738   return Bounds::Unbounded(zone());
 739 }
 740
 741
 742 // JS comparison operators.
 743
 744
 745 Type* Typer::Visitor::JSEqualTyper(Type* lhs, Type* rhs, Typer* t) {
 746   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return t->singleton_false;
 747   if (lhs->Is(t->undefined_or_null) && rhs->Is(t->undefined_or_null)) {
 748     return t->singleton_true;
 749   }
 750   if (lhs->Is(Type::Number()) && rhs->Is(Type::Number()) &&
 751       (lhs->Max() < rhs->Min() || lhs->Min() > rhs->Max())) {
 752       return t->singleton_false;
 753   }
 754   if (lhs->IsConstant() && rhs->Is(lhs)) {
 755     // Types are equal and are inhabited only by a single semantic value,
 756     // which is not nan due to the earlier check.
 757     // TODO(neis): Extend this to Range(x,x), MinusZero, ...?
 758     return t->singleton_true;
 759   }
 760   return Type::Boolean();
 761 }
 762
 763
 764 Type* Typer::Visitor::JSNotEqualTyper(Type* lhs, Type* rhs, Typer* t) {
 765   return Invert(JSEqualTyper(lhs, rhs, t), t);
 766 }
 767
 768
 769 static Type* JSType(Type* type) {
 770   if (type->Is(Type::Boolean())) return Type::Boolean();
 771   if (type->Is(Type::String())) return Type::String();
 772   if (type->Is(Type::Number())) return Type::Number();
 773   if (type->Is(Type::Undefined())) return Type::Undefined();
 774   if (type->Is(Type::Null())) return Type::Null();
 775   if (type->Is(Type::Symbol())) return Type::Symbol();
 776   if (type->Is(Type::Receiver())) return Type::Receiver();  // JS "Object"
 777   return Type::Any();
 778 }
 779
 780
 781 Type* Typer::Visitor::JSStrictEqualTyper(Type* lhs, Type* rhs, Typer* t) {
 782   if (!JSType(lhs)->Maybe(JSType(rhs))) return t->singleton_false;
 783   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return t->singleton_false;
 784   if (lhs->Is(Type::Number()) && rhs->Is(Type::Number()) &&
 785       (lhs->Max() < rhs->Min() || lhs->Min() > rhs->Max())) {
 786       return t->singleton_false;
 787   }
 788   if (lhs->IsConstant() && rhs->Is(lhs)) {
 789     // Types are equal and are inhabited only by a single semantic value,
 790     // which is not nan due to the earlier check.
 791     return t->singleton_true;
 792   }
 793   return Type::Boolean();
 794 }
 795
 796
 797 Type* Typer::Visitor::JSStrictNotEqualTyper(Type* lhs, Type* rhs, Typer* t) {
 798   return Invert(JSStrictEqualTyper(lhs, rhs, t), t);
 799 }
 800
 801
 802 // The EcmaScript specification defines the four relational comparison operators
 803 // (<, <=, >=, >) with the help of a single abstract one.  It behaves like <
 804 // but returns undefined when the inputs cannot be compared.
 805 // We implement the typing analogously.
 806 Typer::Visitor::ComparisonOutcome Typer::Visitor::JSCompareTyper(Type* lhs,
 807                                                                  Type* rhs,
 808                                                                  Typer* t) {
 809   lhs = ToPrimitive(lhs, t);
 810   rhs = ToPrimitive(rhs, t);
 811   if (lhs->Maybe(Type::String()) && rhs->Maybe(Type::String())) {
 812     return ComparisonOutcome(kComparisonTrue) |
 813            ComparisonOutcome(kComparisonFalse);
 814   }
 815   lhs = ToNumber(lhs, t);
 816   rhs = ToNumber(rhs, t);
 817
 818   // Shortcut for NaNs.
 819   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return kComparisonUndefined;
 820
 821   ComparisonOutcome result;
 822   if (lhs->IsConstant() && rhs->Is(lhs)) {
 823     // Types are equal and are inhabited only by a single semantic value.
 824     result = kComparisonFalse;
 825   } else if (lhs->Min() >= rhs->Max()) {
 826     result = kComparisonFalse;
 827   } else if (lhs->Max() < rhs->Min()) {
 828     result = kComparisonTrue;
 829   } else {
 830     // We cannot figure out the result, return both true and false. (We do not
 831     // have to return undefined because that cannot affect the result of
 832     // FalsifyUndefined.)
 833     return ComparisonOutcome(kComparisonTrue) |
 834            ComparisonOutcome(kComparisonFalse);
 835   }
 836   // Add the undefined if we could see NaN.
 837   if (lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN())) {
 838     result |= kComparisonUndefined;
 839   }
 840   return result;
 841 }
 842
 843
 844 Type* Typer::Visitor::JSLessThanTyper(Type* lhs, Type* rhs, Typer* t) {
 845   return FalsifyUndefined(JSCompareTyper(lhs, rhs, t), t);
 846 }
 847
 848
 849 Type* Typer::Visitor::JSGreaterThanTyper(Type* lhs, Type* rhs, Typer* t) {
 850   return FalsifyUndefined(JSCompareTyper(rhs, lhs, t), t);
 851 }
 852
 853
 854 Type* Typer::Visitor::JSLessThanOrEqualTyper(Type* lhs, Type* rhs, Typer* t) {
 855   return FalsifyUndefined(Invert(JSCompareTyper(rhs, lhs, t), t), t);
 856 }
 857
 858
 859 Type* Typer::Visitor::JSGreaterThanOrEqualTyper(
 860     Type* lhs, Type* rhs, Typer* t) {
 861   return FalsifyUndefined(Invert(JSCompareTyper(lhs, rhs, t), t), t);
 862 }
 863
 864
 865 // JS bitwise operators.
 866
 867
 868 Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs, Type* rhs, Typer* t) {
 869   lhs = NumberToInt32(ToNumber(lhs, t), t);
 870   rhs = NumberToInt32(ToNumber(rhs, t), t);
 871   double lmin = lhs->Min();
 872   double rmin = rhs->Min();
 873   double lmax = lhs->Max();
 874   double rmax = rhs->Max();
 875   // Or-ing any two values results in a value no smaller than their minimum.
 876   // Even no smaller than their maximum if both values are non-negative.
 877   double min =
 878       lmin >= 0 && rmin >= 0 ? std::max(lmin, rmin) : std::min(lmin, rmin);
 879   double max = Type::Signed32()->Max();
 880
 881   // Or-ing with 0 is essentially a conversion to int32.
 882   if (rmin == 0 && rmax == 0) {
 883     min = lmin;
 884     max = lmax;
 885   }
 886   if (lmin == 0 && lmax == 0) {
 887     min = rmin;
 888     max = rmax;
 889   }
 890
 891   if (lmax < 0 || rmax < 0) {
 892     // Or-ing two values of which at least one is negative results in a negative
 893     // value.
 894     max = std::min(max, -1.0);
 895   }
 896   return Type::Range(min, max, t->zone());
 897   // TODO(neis): Be precise for singleton inputs, here and elsewhere.
 898 }
 899
 900
 901 Type* Typer::Visitor::JSBitwiseAndTyper(Type* lhs, Type* rhs, Typer* t) {
 902   lhs = NumberToInt32(ToNumber(lhs, t), t);
 903   rhs = NumberToInt32(ToNumber(rhs, t), t);
 904   double lmin = lhs->Min();
 905   double rmin = rhs->Min();
 906   double lmax = lhs->Max();
 907   double rmax = rhs->Max();
 908   double min = Type::Signed32()->Min();
 909   // And-ing any two values results in a value no larger than their maximum.
 910   // Even no larger than their minimum if both values are non-negative.
 911   double max =
 912       lmin >= 0 && rmin >= 0 ? std::min(lmax, rmax) : std::max(lmax, rmax);
 913   // And-ing with a non-negative value x causes the result to be between
 914   // zero and x.
 915   if (lmin >= 0) {
 916     min = 0;
 917     max = std::min(max, lmax);
 918   }
 919   if (rmin >= 0) {
 920     min = 0;
 921     max = std::min(max, rmax);
 922   }
 923   return Type::Range(min, max, t->zone());
 924 }
 925
 926
 927 Type* Typer::Visitor::JSBitwiseXorTyper(Type* lhs, Type* rhs, Typer* t) {
 928   lhs = NumberToInt32(ToNumber(lhs, t), t);
 929   rhs = NumberToInt32(ToNumber(rhs, t), t);
 930   double lmin = lhs->Min();
 931   double rmin = rhs->Min();
 932   double lmax = lhs->Max();
 933   double rmax = rhs->Max();
 934   if ((lmin >= 0 && rmin >= 0) || (lmax < 0 && rmax < 0)) {
 935     // Xor-ing negative or non-negative values results in a non-negative value.
 936     return Type::Unsigned31();
 937   }
 938   if ((lmax < 0 && rmin >= 0) || (lmin >= 0 && rmax < 0)) {
 939     // Xor-ing a negative and a non-negative value results in a negative value.
 940     // TODO(jarin) Use a range here.
 941     return Type::Negative32();
 942   }
 943   return Type::Signed32();
 944 }
 945
 946
 947 Type* Typer::Visitor::JSShiftLeftTyper(Type* lhs, Type* rhs, Typer* t) {
 948   return Type::Signed32();
 949 }
 950
 951
 952 Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) {
 953   lhs = NumberToInt32(ToNumber(lhs, t), t);
 954   rhs = NumberToUint32(ToNumber(rhs, t), t);
 955   double min = kMinInt;
 956   double max = kMaxInt;
 957   if (lhs->Min() >= 0) {
 958     // Right-shifting a non-negative value cannot make it negative, nor larger.
 959     min = std::max(min, 0.0);
 960     max = std::min(max, lhs->Max());
 961     if (rhs->Min() > 0 && rhs->Max() <= 31) {
 962       max = static_cast<int>(max) >> static_cast<int>(rhs->Min());
 963     }
 964   }
 965   if (lhs->Max() < 0) {
 966     // Right-shifting a negative value cannot make it non-negative, nor smaller.
 967     min = std::max(min, lhs->Min());
 968     max = std::min(max, -1.0);
 969     if (rhs->Min() > 0 && rhs->Max() <= 31) {
 970       min = static_cast<int>(min) >> static_cast<int>(rhs->Min());
 971     }
 972   }
 973   if (rhs->Min() > 0 && rhs->Max() <= 31) {
 974     // Right-shifting by a positive value yields a small integer value.
 975     double shift_min = kMinInt >> static_cast<int>(rhs->Min());
 976     double shift_max = kMaxInt >> static_cast<int>(rhs->Min());
 977     min = std::max(min, shift_min);
 978     max = std::min(max, shift_max);
 979   }
 980   // TODO(jarin) Ideally, the following micro-optimization should be performed
 981   // by the type constructor.
 982   if (max != Type::Signed32()->Max() || min != Type::Signed32()->Min()) {
 983     return Type::Range(min, max, t->zone());
 984   }
 985   return Type::Signed32();
 986 }
 987
 988
 989 Type* Typer::Visitor::JSShiftRightLogicalTyper(Type* lhs, Type* rhs, Typer* t) {
 990   lhs = NumberToUint32(ToNumber(lhs, t), t);
 991   // Logical right-shifting any value cannot make it larger.
 992   return Type::Range(0.0, lhs->Max(), t->zone());
 993 }
 994
 995
 996 // JS arithmetic operators.
 997
 998
 999 // Returns the array's least element, ignoring NaN.
1000 // There must be at least one non-NaN element.
1001 // Any -0 is converted to 0.
1002 static double array_min(double a[], size_t n) {
1003   DCHECK(n != 0);
1004   double x = +V8_INFINITY;
1005   for (size_t i = 0; i < n; ++i) {
1006     if (!std::isnan(a[i])) {
1007       x = std::min(a[i], x);
1008     }
1009   }
1010   DCHECK(!std::isnan(x));
1011   return x == 0 ? 0 : x;  // -0 -> 0
1012 }
1013
1014
1015 // Returns the array's greatest element, ignoring NaN.
1016 // There must be at least one non-NaN element.
1017 // Any -0 is converted to 0.
1018 static double array_max(double a[], size_t n) {
1019   DCHECK(n != 0);
1020   double x = -V8_INFINITY;
1021   for (size_t i = 0; i < n; ++i) {
1022     if (!std::isnan(a[i])) {
1023       x = std::max(a[i], x);
1024     }
1025   }
1026   DCHECK(!std::isnan(x));
1027   return x == 0 ? 0 : x;  // -0 -> 0
1028 }
1029
1030
1031 Type* Typer::Visitor::JSAddRanger(Type::RangeType* lhs, Type::RangeType* rhs,
1032                                   Typer* t) {
1033   double results[4];
1034   results[0] = lhs->Min() + rhs->Min();
1035   results[1] = lhs->Min() + rhs->Max();
1036   results[2] = lhs->Max() + rhs->Min();
1037   results[3] = lhs->Max() + rhs->Max();
1038   // Since none of the inputs can be -0, the result cannot be -0 either.
1039   // However, it can be nan (the sum of two infinities of opposite sign).
1040   // On the other hand, if none of the "results" above is nan, then the actual
1041   // result cannot be nan either.
1042   int nans = 0;
1043   for (int i = 0; i < 4; ++i) {
1044     if (std::isnan(results[i])) ++nans;
1045   }
1046   if (nans == 4) return Type::NaN();  // [-inf..-inf] + [inf..inf] or vice versa
1047   Type* range =
1048       Type::Range(array_min(results, 4), array_max(results, 4), t->zone());
1049   return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone());
1050   // Examples:
1051   //   [-inf, -inf] + [+inf, +inf] = NaN
1052   //   [-inf, -inf] + [n, +inf] = [-inf, -inf] \/ NaN
1053   //   [-inf, +inf] + [n, +inf] = [-inf, +inf] \/ NaN
1054   //   [-inf, m] + [n, +inf] = [-inf, +inf] \/ NaN
1055 }
1056
1057
1058 Type* Typer::Visitor::JSAddTyper(Type* lhs, Type* rhs, Typer* t) {
1059   lhs = ToPrimitive(lhs, t);
1060   rhs = ToPrimitive(rhs, t);
1061   if (lhs->Maybe(Type::String()) || rhs->Maybe(Type::String())) {
1062     if (lhs->Is(Type::String()) || rhs->Is(Type::String())) {
1063       return Type::String();
1064     } else {
1065       return Type::NumberOrString();
1066     }
1067   }
1068   lhs = Rangify(ToNumber(lhs, t), t);
1069   rhs = Rangify(ToNumber(rhs, t), t);
1070   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
1071   if (lhs->IsRange() && rhs->IsRange()) {
1072     return JSAddRanger(lhs->AsRange(), rhs->AsRange(), t);
1073   }
1074   // TODO(neis): Deal with numeric bitsets here and elsewhere.
1075   return Type::Number();
1076 }
1077
1078
1079 Type* Typer::Visitor::JSSubtractRanger(Type::RangeType* lhs,
1080                                        Type::RangeType* rhs, Typer* t) {
1081   double results[4];
1082   results[0] = lhs->Min() - rhs->Min();
1083   results[1] = lhs->Min() - rhs->Max();
1084   results[2] = lhs->Max() - rhs->Min();
1085   results[3] = lhs->Max() - rhs->Max();
1086   // Since none of the inputs can be -0, the result cannot be -0.
1087   // However, it can be nan (the subtraction of two infinities of same sign).
1088   // On the other hand, if none of the "results" above is nan, then the actual
1089   // result cannot be nan either.
1090   int nans = 0;
1091   for (int i = 0; i < 4; ++i) {
1092     if (std::isnan(results[i])) ++nans;
1093   }
1094   if (nans == 4) return Type::NaN();  // [inf..inf] - [inf..inf] (all same sign)
1095   Type* range =
1096       Type::Range(array_min(results, 4), array_max(results, 4), t->zone());
1097   return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone());
1098   // Examples:
1099   //   [-inf, +inf] - [-inf, +inf] = [-inf, +inf] \/ NaN
1100   //   [-inf, -inf] - [-inf, -inf] = NaN
1101   //   [-inf, -inf] - [n, +inf] = [-inf, -inf] \/ NaN
1102   //   [m, +inf] - [-inf, n] = [-inf, +inf] \/ NaN
1103 }
1104
1105
1106 Type* Typer::Visitor::JSSubtractTyper(Type* lhs, Type* rhs, Typer* t) {
1107   lhs = Rangify(ToNumber(lhs, t), t);
1108   rhs = Rangify(ToNumber(rhs, t), t);
1109   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
1110   if (lhs->IsRange() && rhs->IsRange()) {
1111     return JSSubtractRanger(lhs->AsRange(), rhs->AsRange(), t);
1112   }
1113   return Type::Number();
1114 }
1115
1116
1117 Type* Typer::Visitor::JSMultiplyRanger(Type::RangeType* lhs,
1118                                        Type::RangeType* rhs, Typer* t) {
1119   double results[4];
1120   double lmin = lhs->Min();
1121   double lmax = lhs->Max();
1122   double rmin = rhs->Min();
1123   double rmax = rhs->Max();
1124   results[0] = lmin * rmin;
1125   results[1] = lmin * rmax;
1126   results[2] = lmax * rmin;
1127   results[3] = lmax * rmax;
1128   // If the result may be nan, we give up on calculating a precise type, because
1129   // the discontinuity makes it too complicated.  Note that even if none of the
1130   // "results" above is nan, the actual result may still be, so we have to do a
1131   // different check:
1132   bool maybe_nan = (lhs->Maybe(t->singleton_zero) &&
1133                     (rmin == -V8_INFINITY || rmax == +V8_INFINITY)) ||
1134                    (rhs->Maybe(t->singleton_zero) &&
1135                     (lmin == -V8_INFINITY || lmax == +V8_INFINITY));
1136   if (maybe_nan) return t->weakint;  // Giving up.
1137   bool maybe_minuszero = (lhs->Maybe(t->singleton_zero) && rmin < 0) ||
1138                          (rhs->Maybe(t->singleton_zero) && lmin < 0);
1139   Type* range =
1140       Type::Range(array_min(results, 4), array_max(results, 4), t->zone());
1141   return maybe_minuszero ? Type::Union(range, Type::MinusZero(), t->zone())
1142                          : range;
1143 }
1144
1145
1146 Type* Typer::Visitor::JSMultiplyTyper(Type* lhs, Type* rhs, Typer* t) {
1147   lhs = Rangify(ToNumber(lhs, t), t);
1148   rhs = Rangify(ToNumber(rhs, t), t);
1149   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
1150   if (lhs->IsRange() && rhs->IsRange()) {
1151     return JSMultiplyRanger(lhs->AsRange(), rhs->AsRange(), t);
1152   }
1153   return Type::Number();
1154 }
1155
1156
1157 Type* Typer::Visitor::JSDivideTyper(Type* lhs, Type* rhs, Typer* t) {
1158   lhs = ToNumber(lhs, t);
1159   rhs = ToNumber(rhs, t);
1160   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
1161   // Division is tricky, so all we do is try ruling out nan.
1162   // TODO(neis): try ruling out -0 as well?
1163   bool maybe_nan =
1164       lhs->Maybe(Type::NaN()) || rhs->Maybe(t->zeroish) ||
1165       ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) &&
1166        (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
1167   return maybe_nan ? Type::Number() : Type::OrderedNumber();
1168 }
1169
1170
1171 Type* Typer::Visitor::JSModulusRanger(Type::RangeType* lhs,
1172                                       Type::RangeType* rhs, Typer* t) {
1173   double lmin = lhs->Min();
1174   double lmax = lhs->Max();
1175   double rmin = rhs->Min();
1176   double rmax = rhs->Max();
1177
1178   double labs = std::max(std::abs(lmin), std::abs(lmax));
1179   double rabs = std::max(std::abs(rmin), std::abs(rmax)) - 1;
1180   double abs = std::min(labs, rabs);
1181   bool maybe_minus_zero = false;
1182   double omin = 0;
1183   double omax = 0;
1184   if (lmin >= 0) {  // {lhs} positive.
1185     omin = 0;
1186     omax = abs;
1187   } else if (lmax <= 0) {  // {lhs} negative.
1188     omin = 0 - abs;
1189     omax = 0;
1190     maybe_minus_zero = true;
1191   } else {
1192     omin = 0 - abs;
1193     omax = abs;
1194     maybe_minus_zero = true;
1195   }
1196
1197   Type* result = Type::Range(omin, omax, t->zone());
1198   if (maybe_minus_zero)
1199     result = Type::Union(result, Type::MinusZero(), t->zone());
1200   return result;
1201 }
1202
1203
1204 Type* Typer::Visitor::JSModulusTyper(Type* lhs, Type* rhs, Typer* t) {
1205   lhs = ToNumber(lhs, t);
1206   rhs = ToNumber(rhs, t);
1207   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
1208
1209   if (lhs->Maybe(Type::NaN()) || rhs->Maybe(t->zeroish) ||
1210       lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) {
1211     // Result maybe NaN.
1212     return Type::Number();
1213   }
1214
1215   lhs = Rangify(lhs, t);
1216   rhs = Rangify(rhs, t);
1217   if (lhs->IsRange() && rhs->IsRange()) {
1218     return JSModulusRanger(lhs->AsRange(), rhs->AsRange(), t);
1219   }
1220   return Type::OrderedNumber();
1221 }
1222
1223
1224 // JS unary operators.
1225
1226
1227 Type* Typer::Visitor::JSUnaryNotTyper(Type* type, Typer* t) {
1228   return Invert(ToBoolean(type, t), t);
1229 }
1230
1231
1232 Bounds Typer::Visitor::TypeJSUnaryNot(Node* node) {
1233   return TypeUnaryOp(node, JSUnaryNotTyper);
1234 }
1235
1236
1237 Bounds Typer::Visitor::TypeJSTypeOf(Node* node) {
1238   return Bounds(Type::None(zone()), Type::InternalizedString(zone()));
1239 }
1240
1241
1242 // JS conversion operators.
1243
1244
1245 Bounds Typer::Visitor::TypeJSToBoolean(Node* node) {
1246   return TypeUnaryOp(node, ToBoolean);
1247 }
1248
1249
1250 Bounds Typer::Visitor::TypeJSToNumber(Node* node) {
1251   return TypeUnaryOp(node, ToNumber);
1252 }
1253
1254
1255 Bounds Typer::Visitor::TypeJSToString(Node* node) {
1256   return TypeUnaryOp(node, ToString);
1257 }
1258
1259
1260 Bounds Typer::Visitor::TypeJSToName(Node* node) {
1261   return Bounds(Type::None(), Type::Name());
1262 }
1263
1264
1265 Bounds Typer::Visitor::TypeJSToObject(Node* node) {
1266   return Bounds(Type::None(), Type::Receiver());
1267 }
1268
1269
1270 // JS object operators.
1271
1272
1273 Bounds Typer::Visitor::TypeJSCreate(Node* node) {
1274   return Bounds(Type::None(), Type::Object());
1275 }
1276
1277
1278 Type* Typer::Visitor::JSLoadPropertyTyper(Type* object, Type* name, Typer* t) {
1279   // TODO(rossberg): Use range types and sized array types to filter undefined.
1280   if (object->IsArray() && name->Is(Type::Integral32())) {
1281     return Type::Union(
1282         object->AsArray()->Element(), Type::Undefined(), t->zone());
1283   }
1284   return Type::Any();
1285 }
1286
1287
1288 Bounds Typer::Visitor::TypeJSLoadProperty(Node* node) {
1289   return TypeBinaryOp(node, JSLoadPropertyTyper);
1290 }
1291
1292
1293 Bounds Typer::Visitor::TypeJSLoadNamed(Node* node) {
1294   return Bounds::Unbounded(zone());
1295 }
1296
1297
1298 // Returns a somewhat larger range if we previously assigned
1299 // a (smaller) range to this node. This is used  to speed up
1300 // the fixpoint calculation in case there appears to be a loop
1301 // in the graph. In the current implementation, we are
1302 // increasing the limits to the closest power of two.
1303 Type* Typer::Visitor::Weaken(Node* node, Type* current_type,
1304                              Type* previous_type) {
1305   static const double kWeakenMinLimits[] = {
1306       0.0, -1073741824.0, -2147483648.0, -4294967296.0, -8589934592.0,
1307       -17179869184.0, -34359738368.0, -68719476736.0, -137438953472.0,
1308       -274877906944.0, -549755813888.0, -1099511627776.0, -2199023255552.0,
1309       -4398046511104.0, -8796093022208.0, -17592186044416.0, -35184372088832.0,
1310       -70368744177664.0, -140737488355328.0, -281474976710656.0,
1311       -562949953421312.0};
1312   static const double kWeakenMaxLimits[] = {
1313       0.0, 1073741823.0, 2147483647.0, 4294967295.0, 8589934591.0,
1314       17179869183.0, 34359738367.0, 68719476735.0, 137438953471.0,
1315       274877906943.0, 549755813887.0, 1099511627775.0, 2199023255551.0,
1316       4398046511103.0, 8796093022207.0, 17592186044415.0, 35184372088831.0,
1317       70368744177663.0, 140737488355327.0, 281474976710655.0,
1318       562949953421311.0};
1319   STATIC_ASSERT(arraysize(kWeakenMinLimits) == arraysize(kWeakenMaxLimits));
1320
1321   // If the types have nothing to do with integers, return the types.
1322   if (!previous_type->Maybe(typer_->integer)) {
1323     return current_type;
1324   }
1325   DCHECK(current_type->Maybe(typer_->integer));
1326
1327   Type* current_integer =
1328       Type::Intersect(current_type, typer_->integer, zone());
1329   Type* previous_integer =
1330       Type::Intersect(previous_type, typer_->integer, zone());
1331
1332   // Once we start weakening a node, we should always weaken.
1333   if (!IsWeakened(node->id())) {
1334     // Only weaken if there is range involved; we should converge quickly
1335     // for all other types (the exception is a union of many constants,
1336     // but we currently do not increase the number of constants in unions).
1337     Type::RangeType* previous = previous_integer->GetRange();
1338     Type::RangeType* current = current_integer->GetRange();
1339     if (current == nullptr || previous == nullptr) {
1340       return current_type;
1341     }
1342     // Range is involved => we are weakening.
1343     SetWeakened(node->id());
1344   }
1345
1346   double current_min = current_integer->Min();
1347   double new_min = current_min;
1348   // Find the closest lower entry in the list of allowed
1349   // minima (or negative infinity if there is no such entry).
1350   if (current_min != previous_integer->Min()) {
1351     new_min = typer_->integer->AsRange()->Min();
1352     for (double const min : kWeakenMinLimits) {
1353       if (min <= current_min) {
1354         new_min = min;
1355         break;
1356       }
1357     }
1358   }
1359
1360   double current_max = current_integer->Max();
1361   double new_max = current_max;
1362   // Find the closest greater entry in the list of allowed
1363   // maxima (or infinity if there is no such entry).
1364   if (current_max != previous_integer->Max()) {
1365     new_max = typer_->integer->AsRange()->Max();
1366     for (double const max : kWeakenMaxLimits) {
1367       if (max >= current_max) {
1368         new_max = max;
1369         break;
1370       }
1371     }
1372   }
1373
1374   return Type::Union(current_type,
1375                      Type::Range(new_min, new_max, typer_->zone()),
1376                      typer_->zone());
1377 }
1378
1379
1380 Bounds Typer::Visitor::TypeJSStoreProperty(Node* node) {
1381   UNREACHABLE();
1382   return Bounds();
1383 }
1384
1385
1386 Bounds Typer::Visitor::TypeJSStoreNamed(Node* node) {
1387   UNREACHABLE();
1388   return Bounds();
1389 }
1390
1391
1392 Bounds Typer::Visitor::TypeJSDeleteProperty(Node* node) {
1393   return Bounds(Type::None(zone()), Type::Boolean(zone()));
1394 }
1395
1396
1397 Bounds Typer::Visitor::TypeJSHasProperty(Node* node) {
1398   return Bounds(Type::None(zone()), Type::Boolean(zone()));
1399 }
1400
1401
1402 Bounds Typer::Visitor::TypeJSInstanceOf(Node* node) {
1403   return Bounds(Type::None(zone()), Type::Boolean(zone()));
1404 }
1405
1406
1407 // JS context operators.
1408
1409
1410 Bounds Typer::Visitor::TypeJSLoadContext(Node* node) {
1411   Bounds outer = Operand(node, 0);
1412   Type* context_type = outer.upper;
1413   if (context_type->Is(Type::None())) {
1414     // Upper bound of context is not yet known.
1415     return Bounds(Type::None(), Type::Any());
1416   }
1417
1418   DCHECK(context_type->Maybe(Type::Internal()));
1419   // TODO(rossberg): More precisely, instead of the above assertion, we should
1420   // back-propagate the constraint that it has to be a subtype of Internal.
1421
1422   ContextAccess access = OpParameter<ContextAccess>(node);
1423   MaybeHandle<Context> context;
1424   if (context_type->IsConstant()) {
1425     context = Handle<Context>::cast(context_type->AsConstant()->Value());
1426   }
1427   // Walk context chain (as far as known), mirroring dynamic lookup.
1428   // Since contexts are mutable, the information is only useful as a lower
1429   // bound.
1430   // TODO(rossberg): Could use scope info to fix upper bounds for constant
1431   // bindings if we know that this code is never shared.
1432   for (size_t i = access.depth(); i > 0; --i) {
1433     if (context_type->IsContext()) {
1434       context_type = context_type->AsContext()->Outer();
1435       if (context_type->IsConstant()) {
1436         context = Handle<Context>::cast(context_type->AsConstant()->Value());
1437       }
1438     } else if (!context.is_null()) {
1439       context = handle(context.ToHandleChecked()->previous(), isolate());
1440     }
1441   }
1442   if (context.is_null()) {
1443     return Bounds::Unbounded(zone());
1444   } else {
1445     Handle<Object> value =
1446         handle(context.ToHandleChecked()->get(static_cast<int>(access.index())),
1447                isolate());
1448     Type* lower = TypeConstant(value);
1449     return Bounds(lower, Type::Any());
1450   }
1451 }
1452
1453
1454 Bounds Typer::Visitor::TypeJSStoreContext(Node* node) {
1455   UNREACHABLE();
1456   return Bounds();
1457 }
1458
1459
1460 Bounds Typer::Visitor::WrapContextBoundsForInput(Node* node) {
1461   Bounds outer = BoundsOrNone(NodeProperties::GetContextInput(node));
1462   if (outer.upper->Is(Type::None())) {
1463     return Bounds(Type::None());
1464   } else {
1465     DCHECK(outer.upper->Maybe(Type::Internal()));
1466     return Bounds(Type::Context(outer.upper, zone()));
1467   }
1468 }
1469
1470
1471 Bounds Typer::Visitor::TypeJSCreateFunctionContext(Node* node) {
1472   return WrapContextBoundsForInput(node);
1473 }
1474
1475
1476 Bounds Typer::Visitor::TypeJSCreateCatchContext(Node* node) {
1477   return WrapContextBoundsForInput(node);
1478 }
1479
1480
1481 Bounds Typer::Visitor::TypeJSCreateWithContext(Node* node) {
1482   return WrapContextBoundsForInput(node);
1483 }
1484
1485
1486 Bounds Typer::Visitor::TypeJSCreateBlockContext(Node* node) {
1487   return WrapContextBoundsForInput(node);
1488 }
1489
1490
1491 Bounds Typer::Visitor::TypeJSCreateModuleContext(Node* node) {
1492   // TODO(rossberg): this is probably incorrect
1493   return WrapContextBoundsForInput(node);
1494 }
1495
1496
1497 Bounds Typer::Visitor::TypeJSCreateScriptContext(Node* node) {
1498   return WrapContextBoundsForInput(node);
1499 }
1500
1501
1502 // JS other operators.
1503
1504
1505 Bounds Typer::Visitor::TypeJSYield(Node* node) {
1506   return Bounds::Unbounded(zone());
1507 }
1508
1509
1510 Bounds Typer::Visitor::TypeJSCallConstruct(Node* node) {
1511   return Bounds(Type::None(), Type::Receiver());
1512 }
1513
1514
1515 Type* Typer::Visitor::JSCallFunctionTyper(Type* fun, Typer* t) {
1516   return fun->IsFunction() ? fun->AsFunction()->Result() : Type::Any();
1517 }
1518
1519
1520 Bounds Typer::Visitor::TypeJSCallFunction(Node* node) {
1521   return TypeUnaryOp(node, JSCallFunctionTyper);  // We ignore argument types.
1522 }
1523
1524
1525 Bounds Typer::Visitor::TypeJSCallRuntime(Node* node) {
1526   switch (CallRuntimeParametersOf(node->op()).id()) {
1527     case Runtime::kInlineIsSmi:
1528     case Runtime::kInlineIsNonNegativeSmi:
1529     case Runtime::kInlineIsArray:
1530     case Runtime::kInlineIsFunction:
1531     case Runtime::kInlineIsRegExp:
1532       return Bounds(Type::None(zone()), Type::Boolean(zone()));
1533     case Runtime::kInlineDoubleLo:
1534     case Runtime::kInlineDoubleHi:
1535       return Bounds(Type::None(zone()), Type::Signed32());
1536     case Runtime::kInlineConstructDouble:
1537     case Runtime::kInlineMathFloor:
1538     case Runtime::kInlineMathSqrt:
1539     case Runtime::kInlineMathAcos:
1540     case Runtime::kInlineMathAsin:
1541     case Runtime::kInlineMathAtan:
1542     case Runtime::kInlineMathAtan2:
1543       return Bounds(Type::None(zone()), Type::Number());
1544     case Runtime::kInlineMathClz32:
1545       return Bounds(Type::None(), Type::Range(0, 32, zone()));
1546     case Runtime::kInlineStringGetLength:
1547       // The string::length property is always an unsigned smi.
1548       return Bounds(Type::None(), Type::Intersect(Type::UnsignedSmall(),
1549                                                   Type::TaggedSigned()));
1550     default:
1551       break;
1552   }
1553   return Bounds::Unbounded(zone());
1554 }
1555
1556
1557 Bounds Typer::Visitor::TypeJSStackCheck(Node* node) {
1558   return Bounds::Unbounded(zone());
1559 }
1560
1561
1562 // Simplified operators.
1563
1564
1565 Bounds Typer::Visitor::TypeBooleanNot(Node* node) {
1566   return Bounds(Type::None(zone()), Type::Boolean(zone()));
1567 }
1568
1569
1570 Bounds Typer::Visitor::TypeBooleanToNumber(Node* node) {
1571   return TypeUnaryOp(node, ToNumber);
1572 }
1573
1574
1575 Bounds Typer::Visitor::TypeNumberEqual(Node* node) {
1576   return Bounds(Type::None(zone()), Type::Boolean(zone()));
1577 }
1578
1579
1580 Bounds Typer::Visitor::TypeNumberLessThan(Node* node) {
1581   return Bounds(Type::None(zone()), Type::Boolean(zone()));
1582 }
1583
1584
1585 Bounds Typer::Visitor::TypeNumberLessThanOrEqual(Node* node) {
1586   return Bounds(Type::None(zone()), Type::Boolean(zone()));
1587 }
1588
1589
1590 Bounds Typer::Visitor::TypeNumberAdd(Node* node) {
1591   return Bounds(Type::None(zone()), Type::Number(zone()));
1592 }
1593
1594
1595 Bounds Typer::Visitor::TypeNumberSubtract(Node* node) {
1596   return Bounds(Type::None(zone()), Type::Number(zone()));
1597 }
1598
1599
1600 Bounds Typer::Visitor::TypeNumberMultiply(Node* node) {
1601   return Bounds(Type::None(zone()), Type::Number(zone()));
1602 }
1603
1604
1605 Bounds Typer::Visitor::TypeNumberDivide(Node* node) {
1606   return Bounds(Type::None(zone()), Type::Number(zone()));
1607 }
1608
1609
1610 Bounds Typer::Visitor::TypeNumberModulus(Node* node) {
1611   return Bounds(Type::None(zone()), Type::Number(zone()));
1612 }
1613
1614
1615 Bounds Typer::Visitor::TypeNumberToInt32(Node* node) {
1616   return TypeUnaryOp(node, NumberToInt32);
1617 }
1618
1619
1620 Bounds Typer::Visitor::TypeNumberToUint32(Node* node) {
1621   return TypeUnaryOp(node, NumberToUint32);
1622 }
1623
1624
1625 Bounds Typer::Visitor::TypePlainPrimitiveToNumber(Node* node) {
1626   return TypeUnaryOp(node, ToNumber);
1627 }
1628
1629
1630 Bounds Typer::Visitor::TypeReferenceEqual(Node* node) {
1631   return Bounds(Type::None(zone()), Type::Boolean(zone()));
1632 }
1633
1634
1635 Bounds Typer::Visitor::TypeStringEqual(Node* node) {
1636   return Bounds(Type::None(zone()), Type::Boolean(zone()));
1637 }
1638
1639
1640 Bounds Typer::Visitor::TypeStringLessThan(Node* node) {
1641   return Bounds(Type::None(zone()), Type::Boolean(zone()));
1642 }
1643
1644
1645 Bounds Typer::Visitor::TypeStringLessThanOrEqual(Node* node) {
1646   return Bounds(Type::None(zone()), Type::Boolean(zone()));
1647 }
1648
1649
1650 Bounds Typer::Visitor::TypeStringAdd(Node* node) {
1651   return Bounds(Type::None(zone()), Type::String(zone()));
1652 }
1653
1654
1655 namespace {
1656
1657 Type* ChangeRepresentation(Type* type, Type* rep, Zone* zone) {
1658   return Type::Union(Type::Semantic(type, zone),
1659                      Type::Representation(rep, zone), zone);
1660 }
1661
1662 }  // namespace
1663
1664
1665 Bounds Typer::Visitor::TypeChangeTaggedToInt32(Node* node) {
1666   Bounds arg = Operand(node, 0);
1667   // TODO(neis): DCHECK(arg.upper->Is(Type::Signed32()));
1668   return Bounds(
1669       ChangeRepresentation(arg.lower, Type::UntaggedSigned32(), zone()),
1670       ChangeRepresentation(arg.upper, Type::UntaggedSigned32(), zone()));
1671 }
1672
1673
1674 Bounds Typer::Visitor::TypeChangeTaggedToUint32(Node* node) {
1675   Bounds arg = Operand(node, 0);
1676   // TODO(neis): DCHECK(arg.upper->Is(Type::Unsigned32()));
1677   return Bounds(
1678       ChangeRepresentation(arg.lower, Type::UntaggedUnsigned32(), zone()),
1679       ChangeRepresentation(arg.upper, Type::UntaggedUnsigned32(), zone()));
1680 }
1681
1682
1683 Bounds Typer::Visitor::TypeChangeTaggedToFloat64(Node* node) {
1684   Bounds arg = Operand(node, 0);
1685   // TODO(neis): DCHECK(arg.upper->Is(Type::Number()));
1686   return Bounds(
1687       ChangeRepresentation(arg.lower, Type::UntaggedFloat64(), zone()),
1688       ChangeRepresentation(arg.upper, Type::UntaggedFloat64(), zone()));
1689 }
1690
1691
1692 Bounds Typer::Visitor::TypeChangeInt32ToTagged(Node* node) {
1693   Bounds arg = Operand(node, 0);
1694   // TODO(neis): DCHECK(arg.upper->Is(Type::Signed32()));
1695   Type* lower_rep = arg.lower->Is(Type::SignedSmall()) ? Type::TaggedSigned()
1696                                                        : Type::Tagged();
1697   Type* upper_rep = arg.upper->Is(Type::SignedSmall()) ? Type::TaggedSigned()
1698                                                        : Type::Tagged();
1699   return Bounds(ChangeRepresentation(arg.lower, lower_rep, zone()),
1700                 ChangeRepresentation(arg.upper, upper_rep, zone()));
1701 }
1702
1703
1704 Bounds Typer::Visitor::TypeChangeUint32ToTagged(Node* node) {
1705   Bounds arg = Operand(node, 0);
1706   // TODO(neis): DCHECK(arg.upper->Is(Type::Unsigned32()));
1707   return Bounds(
1708       ChangeRepresentation(arg.lower, Type::Tagged(), zone()),
1709       ChangeRepresentation(arg.upper, Type::Tagged(), zone()));
1710 }
1711
1712
1713 Bounds Typer::Visitor::TypeChangeFloat64ToTagged(Node* node) {
1714   Bounds arg = Operand(node, 0);
1715   // TODO(neis): CHECK(arg.upper->Is(Type::Number()));
1716   return Bounds(
1717       ChangeRepresentation(arg.lower, Type::Tagged(), zone()),
1718       ChangeRepresentation(arg.upper, Type::Tagged(), zone()));
1719 }
1720
1721
1722 Bounds Typer::Visitor::TypeChangeBoolToBit(Node* node) {
1723   Bounds arg = Operand(node, 0);
1724   // TODO(neis): DCHECK(arg.upper->Is(Type::Boolean()));
1725   return Bounds(
1726       ChangeRepresentation(arg.lower, Type::UntaggedBit(), zone()),
1727       ChangeRepresentation(arg.upper, Type::UntaggedBit(), zone()));
1728 }
1729
1730
1731 Bounds Typer::Visitor::TypeChangeBitToBool(Node* node) {
1732   Bounds arg = Operand(node, 0);
1733   // TODO(neis): DCHECK(arg.upper->Is(Type::Boolean()));
1734   return Bounds(ChangeRepresentation(arg.lower, Type::TaggedPointer(), zone()),
1735                 ChangeRepresentation(arg.upper, Type::TaggedPointer(), zone()));
1736 }
1737
1738
1739 Bounds Typer::Visitor::TypeLoadField(Node* node) {
1740   return Bounds(FieldAccessOf(node->op()).type);
1741 }
1742
1743
1744 Bounds Typer::Visitor::TypeLoadBuffer(Node* node) {
1745   // TODO(bmeurer): This typing is not yet correct. Since we can still access
1746   // out of bounds, the type in the general case has to include Undefined.
1747   switch (BufferAccessOf(node->op()).external_array_type()) {
1748 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
1749   case kExternal##Type##Array:                          \
1750     return Bounds(typer_->cache_->Get(k##Type));
1751     TYPED_ARRAYS(TYPED_ARRAY_CASE)
1752 #undef TYPED_ARRAY_CASE
1753   }
1754   UNREACHABLE();
1755   return Bounds();
1756 }
1757
1758
1759 Bounds Typer::Visitor::TypeLoadElement(Node* node) {
1760   return Bounds(ElementAccessOf(node->op()).type);
1761 }
1762
1763
1764 Bounds Typer::Visitor::TypeStoreField(Node* node) {
1765   UNREACHABLE();
1766   return Bounds();
1767 }
1768
1769
1770 Bounds Typer::Visitor::TypeStoreBuffer(Node* node) {
1771   UNREACHABLE();
1772   return Bounds();
1773 }
1774
1775
1776 Bounds Typer::Visitor::TypeStoreElement(Node* node) {
1777   UNREACHABLE();
1778   return Bounds();
1779 }
1780
1781
1782 Bounds Typer::Visitor::TypeObjectIsSmi(Node* node) {
1783   return Bounds(Type::Boolean());
1784 }
1785
1786
1787 Bounds Typer::Visitor::TypeObjectIsNonNegativeSmi(Node* node) {
1788   return Bounds(Type::Boolean());
1789 }
1790
1791
1792 // Machine operators.
1793
1794 Bounds Typer::Visitor::TypeLoad(Node* node) {
1795   return Bounds::Unbounded(zone());
1796 }
1797
1798
1799 Bounds Typer::Visitor::TypeStore(Node* node) {
1800   UNREACHABLE();
1801   return Bounds();
1802 }
1803
1804
1805 Bounds Typer::Visitor::TypeWord32And(Node* node) {
1806   return Bounds(Type::Integral32());
1807 }
1808
1809
1810 Bounds Typer::Visitor::TypeWord32Or(Node* node) {
1811   return Bounds(Type::Integral32());
1812 }
1813
1814
1815 Bounds Typer::Visitor::TypeWord32Xor(Node* node) {
1816   return Bounds(Type::Integral32());
1817 }
1818
1819
1820 Bounds Typer::Visitor::TypeWord32Shl(Node* node) {
1821   return Bounds(Type::Integral32());
1822 }
1823
1824
1825 Bounds Typer::Visitor::TypeWord32Shr(Node* node) {
1826   return Bounds(Type::Integral32());
1827 }
1828
1829
1830 Bounds Typer::Visitor::TypeWord32Sar(Node* node) {
1831   return Bounds(Type::Integral32());
1832 }
1833
1834
1835 Bounds Typer::Visitor::TypeWord32Ror(Node* node) {
1836   return Bounds(Type::Integral32());
1837 }
1838
1839
1840 Bounds Typer::Visitor::TypeWord32Equal(Node* node) {
1841   return Bounds(Type::Boolean());
1842 }
1843
1844
1845 Bounds Typer::Visitor::TypeWord32Clz(Node* node) {
1846   return Bounds(Type::Integral32());
1847 }
1848
1849
1850 Bounds Typer::Visitor::TypeWord64And(Node* node) {
1851   return Bounds(Type::Internal());
1852 }
1853
1854
1855 Bounds Typer::Visitor::TypeWord64Or(Node* node) {
1856   return Bounds(Type::Internal());
1857 }
1858
1859
1860 Bounds Typer::Visitor::TypeWord64Xor(Node* node) {
1861   return Bounds(Type::Internal());
1862 }
1863
1864
1865 Bounds Typer::Visitor::TypeWord64Shl(Node* node) {
1866   return Bounds(Type::Internal());
1867 }
1868
1869
1870 Bounds Typer::Visitor::TypeWord64Shr(Node* node) {
1871   return Bounds(Type::Internal());
1872 }
1873
1874
1875 Bounds Typer::Visitor::TypeWord64Sar(Node* node) {
1876   return Bounds(Type::Internal());
1877 }
1878
1879
1880 Bounds Typer::Visitor::TypeWord64Ror(Node* node) {
1881   return Bounds(Type::Internal());
1882 }
1883
1884
1885 Bounds Typer::Visitor::TypeWord64Equal(Node* node) {
1886   return Bounds(Type::Boolean());
1887 }
1888
1889
1890 Bounds Typer::Visitor::TypeInt32Add(Node* node) {
1891   return Bounds(Type::Integral32());
1892 }
1893
1894
1895 Bounds Typer::Visitor::TypeInt32AddWithOverflow(Node* node) {
1896   return Bounds(Type::Internal());
1897 }
1898
1899
1900 Bounds Typer::Visitor::TypeInt32Sub(Node* node) {
1901   return Bounds(Type::Integral32());
1902 }
1903
1904
1905 Bounds Typer::Visitor::TypeInt32SubWithOverflow(Node* node) {
1906   return Bounds(Type::Internal());
1907 }
1908
1909
1910 Bounds Typer::Visitor::TypeInt32Mul(Node* node) {
1911   return Bounds(Type::Integral32());
1912 }
1913
1914
1915 Bounds Typer::Visitor::TypeInt32MulHigh(Node* node) {
1916   return Bounds(Type::Signed32());
1917 }
1918
1919
1920 Bounds Typer::Visitor::TypeInt32Div(Node* node) {
1921   return Bounds(Type::Integral32());
1922 }
1923
1924
1925 Bounds Typer::Visitor::TypeInt32Mod(Node* node) {
1926   return Bounds(Type::Integral32());
1927 }
1928
1929
1930 Bounds Typer::Visitor::TypeInt32LessThan(Node* node) {
1931   return Bounds(Type::Boolean());
1932 }
1933
1934
1935 Bounds Typer::Visitor::TypeInt32LessThanOrEqual(Node* node) {
1936   return Bounds(Type::Boolean());
1937 }
1938
1939
1940 Bounds Typer::Visitor::TypeUint32Div(Node* node) {
1941   return Bounds(Type::Unsigned32());
1942 }
1943
1944
1945 Bounds Typer::Visitor::TypeUint32LessThan(Node* node) {
1946   return Bounds(Type::Boolean());
1947 }
1948
1949
1950 Bounds Typer::Visitor::TypeUint32LessThanOrEqual(Node* node) {
1951   return Bounds(Type::Boolean());
1952 }
1953
1954
1955 Bounds Typer::Visitor::TypeUint32Mod(Node* node) {
1956   return Bounds(Type::Unsigned32());
1957 }
1958
1959
1960 Bounds Typer::Visitor::TypeUint32MulHigh(Node* node) {
1961   return Bounds(Type::Unsigned32());
1962 }
1963
1964
1965 Bounds Typer::Visitor::TypeInt64Add(Node* node) {
1966   return Bounds(Type::Internal());
1967 }
1968
1969
1970 Bounds Typer::Visitor::TypeInt64Sub(Node* node) {
1971   return Bounds(Type::Internal());
1972 }
1973
1974
1975 Bounds Typer::Visitor::TypeInt64Mul(Node* node) {
1976   return Bounds(Type::Internal());
1977 }
1978
1979
1980 Bounds Typer::Visitor::TypeInt64Div(Node* node) {
1981   return Bounds(Type::Internal());
1982 }
1983
1984
1985 Bounds Typer::Visitor::TypeInt64Mod(Node* node) {
1986   return Bounds(Type::Internal());
1987 }
1988
1989
1990 Bounds Typer::Visitor::TypeInt64LessThan(Node* node) {
1991   return Bounds(Type::Boolean());
1992 }
1993
1994
1995 Bounds Typer::Visitor::TypeInt64LessThanOrEqual(Node* node) {
1996   return Bounds(Type::Boolean());
1997 }
1998
1999
2000 Bounds Typer::Visitor::TypeUint64Div(Node* node) {
2001   return Bounds(Type::Internal());
2002 }
2003
2004
2005 Bounds Typer::Visitor::TypeUint64LessThan(Node* node) {
2006   return Bounds(Type::Boolean());
2007 }
2008
2009
2010 Bounds Typer::Visitor::TypeUint64Mod(Node* node) {
2011   return Bounds(Type::Internal());
2012 }
2013
2014
2015 Bounds Typer::Visitor::TypeChangeFloat32ToFloat64(Node* node) {
2016   return Bounds(Type::Intersect(
2017       Type::Number(), Type::UntaggedFloat64(), zone()));
2018 }
2019
2020
2021 Bounds Typer::Visitor::TypeChangeFloat64ToInt32(Node* node) {
2022   return Bounds(Type::Intersect(
2023       Type::Signed32(), Type::UntaggedSigned32(), zone()));
2024 }
2025
2026
2027 Bounds Typer::Visitor::TypeChangeFloat64ToUint32(Node* node) {
2028   return Bounds(Type::Intersect(
2029       Type::Unsigned32(), Type::UntaggedUnsigned32(), zone()));
2030 }
2031
2032
2033 Bounds Typer::Visitor::TypeChangeInt32ToFloat64(Node* node) {
2034   return Bounds(Type::Intersect(
2035       Type::Signed32(), Type::UntaggedFloat64(), zone()));
2036 }
2037
2038
2039 Bounds Typer::Visitor::TypeChangeInt32ToInt64(Node* node) {
2040   return Bounds(Type::Internal());
2041 }
2042
2043
2044 Bounds Typer::Visitor::TypeChangeUint32ToFloat64(Node* node) {
2045   return Bounds(Type::Intersect(
2046       Type::Unsigned32(), Type::UntaggedFloat64(), zone()));
2047 }
2048
2049
2050 Bounds Typer::Visitor::TypeChangeUint32ToUint64(Node* node) {
2051   return Bounds(Type::Internal());
2052 }
2053
2054
2055 Bounds Typer::Visitor::TypeTruncateFloat64ToFloat32(Node* node) {
2056   return Bounds(Type::Intersect(
2057       Type::Number(), Type::UntaggedFloat32(), zone()));
2058 }
2059
2060
2061 Bounds Typer::Visitor::TypeTruncateFloat64ToInt32(Node* node) {
2062   return Bounds(Type::Intersect(
2063       Type::Signed32(), Type::UntaggedSigned32(), zone()));
2064 }
2065
2066
2067 Bounds Typer::Visitor::TypeTruncateInt64ToInt32(Node* node) {
2068   return Bounds(Type::Intersect(
2069       Type::Signed32(), Type::UntaggedSigned32(), zone()));
2070 }
2071
2072
2073 Bounds Typer::Visitor::TypeFloat64Add(Node* node) {
2074   return Bounds(Type::Number());
2075 }
2076
2077
2078 Bounds Typer::Visitor::TypeFloat64Sub(Node* node) {
2079   return Bounds(Type::Number());
2080 }
2081
2082
2083 Bounds Typer::Visitor::TypeFloat64Mul(Node* node) {
2084   return Bounds(Type::Number());
2085 }
2086
2087
2088 Bounds Typer::Visitor::TypeFloat64Div(Node* node) {
2089   return Bounds(Type::Number());
2090 }
2091
2092
2093 Bounds Typer::Visitor::TypeFloat64Mod(Node* node) {
2094   return Bounds(Type::Number());
2095 }
2096
2097
2098 Bounds Typer::Visitor::TypeFloat64Max(Node* node) {
2099   return Bounds(Type::Number());
2100 }
2101
2102
2103 Bounds Typer::Visitor::TypeFloat64Min(Node* node) {
2104   return Bounds(Type::Number());
2105 }
2106
2107
2108 Bounds Typer::Visitor::TypeFloat64Sqrt(Node* node) {
2109   return Bounds(Type::Number());
2110 }
2111
2112
2113 Bounds Typer::Visitor::TypeFloat64Equal(Node* node) {
2114   return Bounds(Type::Boolean());
2115 }
2116
2117
2118 Bounds Typer::Visitor::TypeFloat64LessThan(Node* node) {
2119   return Bounds(Type::Boolean());
2120 }
2121
2122
2123 Bounds Typer::Visitor::TypeFloat64LessThanOrEqual(Node* node) {
2124   return Bounds(Type::Boolean());
2125 }
2126
2127
2128 Bounds Typer::Visitor::TypeFloat64RoundDown(Node* node) {
2129   // TODO(sigurds): We could have a tighter bound here.
2130   return Bounds(Type::Number());
2131 }
2132
2133
2134 Bounds Typer::Visitor::TypeFloat64RoundTruncate(Node* node) {
2135   // TODO(sigurds): We could have a tighter bound here.
2136   return Bounds(Type::Number());
2137 }
2138
2139
2140 Bounds Typer::Visitor::TypeFloat64RoundTiesAway(Node* node) {
2141   // TODO(sigurds): We could have a tighter bound here.
2142   return Bounds(Type::Number());
2143 }
2144
2145
2146 Bounds Typer::Visitor::TypeFloat64ExtractLowWord32(Node* node) {
2147   return Bounds(Type::Signed32());
2148 }
2149
2150
2151 Bounds Typer::Visitor::TypeFloat64ExtractHighWord32(Node* node) {
2152   return Bounds(Type::Signed32());
2153 }
2154
2155
2156 Bounds Typer::Visitor::TypeFloat64InsertLowWord32(Node* node) {
2157   return Bounds(Type::Number());
2158 }
2159
2160
2161 Bounds Typer::Visitor::TypeFloat64InsertHighWord32(Node* node) {
2162   return Bounds(Type::Number());
2163 }
2164
2165
2166 Bounds Typer::Visitor::TypeLoadStackPointer(Node* node) {
2167   return Bounds(Type::Internal());
2168 }
2169
2170
2171 Bounds Typer::Visitor::TypeCheckedLoad(Node* node) {
2172   return Bounds::Unbounded(zone());
2173 }
2174
2175
2176 Bounds Typer::Visitor::TypeCheckedStore(Node* node) {
2177   UNREACHABLE();
2178   return Bounds();
2179 }
2180
2181
2182 // Heap constants.
2183
2184
2185 Type* Typer::Visitor::TypeConstant(Handle<Object> value) {
2186   if (value->IsJSFunction()) {
2187     if (JSFunction::cast(*value)->shared()->HasBuiltinFunctionId()) {
2188       switch (JSFunction::cast(*value)->shared()->builtin_function_id()) {
2189         case kMathRandom:
2190           return typer_->random_fun_;
2191         case kMathFloor:
2192           return typer_->weakint_fun1_;
2193         case kMathRound:
2194           return typer_->weakint_fun1_;
2195         case kMathCeil:
2196           return typer_->weakint_fun1_;
2197         // Unary math functions.
2198         case kMathAbs:  // TODO(rossberg): can't express overloading
2199         case kMathLog:
2200         case kMathExp:
2201         case kMathSqrt:
2202         case kMathCos:
2203         case kMathSin:
2204         case kMathTan:
2205         case kMathAcos:
2206         case kMathAsin:
2207         case kMathAtan:
2208         case kMathFround:
2209           return typer_->cache_->Get(kNumberFunc1);
2210         // Binary math functions.
2211         case kMathAtan2:
2212         case kMathPow:
2213         case kMathMax:
2214         case kMathMin:
2215           return typer_->cache_->Get(kNumberFunc2);
2216         case kMathImul:
2217           return typer_->cache_->Get(kImulFunc);
2218         case kMathClz32:
2219           return typer_->cache_->Get(kClz32Func);
2220         default:
2221           break;
2222       }
2223     } else if (JSFunction::cast(*value)->IsBuiltin() && !context().is_null()) {
2224       Handle<Context> native =
2225           handle(context().ToHandleChecked()->native_context(), isolate());
2226       if (*value == native->array_buffer_fun()) {
2227         return typer_->cache_->Get(kArrayBufferFunc);
2228       } else if (*value == native->int8_array_fun()) {
2229         return typer_->cache_->Get(kInt8ArrayFunc);
2230       } else if (*value == native->int16_array_fun()) {
2231         return typer_->cache_->Get(kInt16ArrayFunc);
2232       } else if (*value == native->int32_array_fun()) {
2233         return typer_->cache_->Get(kInt32ArrayFunc);
2234       } else if (*value == native->uint8_array_fun()) {
2235         return typer_->cache_->Get(kUint8ArrayFunc);
2236       } else if (*value == native->uint16_array_fun()) {
2237         return typer_->cache_->Get(kUint16ArrayFunc);
2238       } else if (*value == native->uint32_array_fun()) {
2239         return typer_->cache_->Get(kUint32ArrayFunc);
2240       } else if (*value == native->float32_array_fun()) {
2241         return typer_->cache_->Get(kFloat32ArrayFunc);
2242       } else if (*value == native->float64_array_fun()) {
2243         return typer_->cache_->Get(kFloat64ArrayFunc);
2244       }
2245     }
2246   } else if (value->IsJSTypedArray()) {
2247     switch (JSTypedArray::cast(*value)->type()) {
2248 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
2249   case kExternal##Type##Array:                          \
2250     return typer_->cache_->Get(k##Type##Array);
2251       TYPED_ARRAYS(TYPED_ARRAY_CASE)
2252 #undef TYPED_ARRAY_CASE
2253     }
2254   }
2255   return Type::Constant(value, zone());
2256 }
2257
2258 }  // namespace compiler
2259 }  // namespace internal
2260 }  // namespace v8