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