Home | History | Annotate | Download | only in compiler 
      1 // Copyright 2016 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/compiler/operation-typer.h"
      6 
      7 #include "src/compiler/common-operator.h"
      8 #include "src/compiler/type-cache.h"
      9 #include "src/compiler/types.h"
     10 #include "src/factory.h"
     11 #include "src/isolate.h"
     12 
     13 #include "src/objects-inl.h"
     14 
     15 namespace v8 {
     16 namespace internal {
     17 namespace compiler {
     18 
     19 OperationTyper::OperationTyper(Isolate* isolate, Zone* zone)
     20     : zone_(zone), cache_(TypeCache::Get()) {
     21   Factory* factory = isolate->factory();
     22   infinity_ = Type::NewConstant(factory->infinity_value(), zone);
     23   minus_infinity_ = Type::NewConstant(factory->minus_infinity_value(), zone);
     24   Type* truncating_to_zero = Type::MinusZeroOrNaN();
     25   DCHECK(!truncating_to_zero->Maybe(Type::Integral32()));
     26 
     27   singleton_false_ = Type::HeapConstant(factory->false_value(), zone);
     28   singleton_true_ = Type::HeapConstant(factory->true_value(), zone);
     29   singleton_the_hole_ = Type::HeapConstant(factory->the_hole_value(), zone);
     30   signed32ish_ = Type::Union(Type::Signed32(), truncating_to_zero, zone);
     31   unsigned32ish_ = Type::Union(Type::Unsigned32(), truncating_to_zero, zone);
     32 }
     33 
     34 Type* OperationTyper::Merge(Type* left, Type* right) {
     35   return Type::Union(left, right, zone());
     36 }
     37 
     38 Type* OperationTyper::WeakenRange(Type* previous_range, Type* current_range) {
     39   static const double kWeakenMinLimits[] = {0.0,
     40                                             -1073741824.0,
     41                                             -2147483648.0,
     42                                             -4294967296.0,
     43                                             -8589934592.0,
     44                                             -17179869184.0,
     45                                             -34359738368.0,
     46                                             -68719476736.0,
     47                                             -137438953472.0,
     48                                             -274877906944.0,
     49                                             -549755813888.0,
     50                                             -1099511627776.0,
     51                                             -2199023255552.0,
     52                                             -4398046511104.0,
     53                                             -8796093022208.0,
     54                                             -17592186044416.0,
     55                                             -35184372088832.0,
     56                                             -70368744177664.0,
     57                                             -140737488355328.0,
     58                                             -281474976710656.0,
     59                                             -562949953421312.0};
     60   static const double kWeakenMaxLimits[] = {0.0,
     61                                             1073741823.0,
     62                                             2147483647.0,
     63                                             4294967295.0,
     64                                             8589934591.0,
     65                                             17179869183.0,
     66                                             34359738367.0,
     67                                             68719476735.0,
     68                                             137438953471.0,
     69                                             274877906943.0,
     70                                             549755813887.0,
     71                                             1099511627775.0,
     72                                             2199023255551.0,
     73                                             4398046511103.0,
     74                                             8796093022207.0,
     75                                             17592186044415.0,
     76                                             35184372088831.0,
     77                                             70368744177663.0,
     78                                             140737488355327.0,
     79                                             281474976710655.0,
     80                                             562949953421311.0};
     81   STATIC_ASSERT(arraysize(kWeakenMinLimits) == arraysize(kWeakenMaxLimits));
     82 
     83   double current_min = current_range->Min();
     84   double new_min = current_min;
     85   // Find the closest lower entry in the list of allowed
     86   // minima (or negative infinity if there is no such entry).
     87   if (current_min != previous_range->Min()) {
     88     new_min = -V8_INFINITY;
     89     for (double const min : kWeakenMinLimits) {
     90       if (min <= current_min) {
     91         new_min = min;
     92         break;
     93       }
     94     }
     95   }
     96 
     97   double current_max = current_range->Max();
     98   double new_max = current_max;
     99   // Find the closest greater entry in the list of allowed
    100   // maxima (or infinity if there is no such entry).
    101   if (current_max != previous_range->Max()) {
    102     new_max = V8_INFINITY;
    103     for (double const max : kWeakenMaxLimits) {
    104       if (max >= current_max) {
    105         new_max = max;
    106         break;
    107       }
    108     }
    109   }
    110 
    111   return Type::Range(new_min, new_max, zone());
    112 }
    113 
    114 Type* OperationTyper::Rangify(Type* type) {
    115   if (type->IsRange()) return type;  // Shortcut.
    116   if (!type->Is(cache_.kInteger)) {
    117     return type;  // Give up on non-integer types.
    118   }
    119   double min = type->Min();
    120   double max = type->Max();
    121   // Handle the degenerate case of empty bitset types (such as
    122   // OtherUnsigned31 and OtherSigned32 on 64-bit architectures).
    123   if (std::isnan(min)) {
    124     DCHECK(std::isnan(max));
    125     return type;
    126   }
    127   return Type::Range(min, max, zone());
    128 }
    129 
    130 namespace {
    131 
    132 // Returns the array's least element, ignoring NaN.
    133 // There must be at least one non-NaN element.
    134 // Any -0 is converted to 0.
    135 double array_min(double a[], size_t n) {
    136   DCHECK(n != 0);
    137   double x = +V8_INFINITY;
    138   for (size_t i = 0; i < n; ++i) {
    139     if (!std::isnan(a[i])) {
    140       x = std::min(a[i], x);
    141     }
    142   }
    143   DCHECK(!std::isnan(x));
    144   return x == 0 ? 0 : x;  // -0 -> 0
    145 }
    146 
    147 // Returns the array's greatest element, ignoring NaN.
    148 // There must be at least one non-NaN element.
    149 // Any -0 is converted to 0.
    150 double array_max(double a[], size_t n) {
    151   DCHECK(n != 0);
    152   double x = -V8_INFINITY;
    153   for (size_t i = 0; i < n; ++i) {
    154     if (!std::isnan(a[i])) {
    155       x = std::max(a[i], x);
    156     }
    157   }
    158   DCHECK(!std::isnan(x));
    159   return x == 0 ? 0 : x;  // -0 -> 0
    160 }
    161 
    162 }  // namespace
    163 
    164 Type* OperationTyper::AddRanger(double lhs_min, double lhs_max, double rhs_min,
    165                                 double rhs_max) {
    166   double results[4];
    167   results[0] = lhs_min + rhs_min;
    168   results[1] = lhs_min + rhs_max;
    169   results[2] = lhs_max + rhs_min;
    170   results[3] = lhs_max + rhs_max;
    171   // Since none of the inputs can be -0, the result cannot be -0 either.
    172   // However, it can be nan (the sum of two infinities of opposite sign).
    173   // On the other hand, if none of the "results" above is nan, then the
    174   // actual result cannot be nan either.
    175   int nans = 0;
    176   for (int i = 0; i < 4; ++i) {
    177     if (std::isnan(results[i])) ++nans;
    178   }
    179   if (nans == 4) return Type::NaN();
    180   Type* type =
    181       Type::Range(array_min(results, 4), array_max(results, 4), zone());
    182   if (nans > 0) type = Type::Union(type, Type::NaN(), zone());
    183   // Examples:
    184   //   [-inf, -inf] + [+inf, +inf] = NaN
    185   //   [-inf, -inf] + [n, +inf] = [-inf, -inf] \/ NaN
    186   //   [-inf, +inf] + [n, +inf] = [-inf, +inf] \/ NaN
    187   //   [-inf, m] + [n, +inf] = [-inf, +inf] \/ NaN
    188   return type;
    189 }
    190 
    191 Type* OperationTyper::SubtractRanger(double lhs_min, double lhs_max,
    192                                      double rhs_min, double rhs_max) {
    193   double results[4];
    194   results[0] = lhs_min - rhs_min;
    195   results[1] = lhs_min - rhs_max;
    196   results[2] = lhs_max - rhs_min;
    197   results[3] = lhs_max - rhs_max;
    198   // Since none of the inputs can be -0, the result cannot be -0.
    199   // However, it can be nan (the subtraction of two infinities of same sign).
    200   // On the other hand, if none of the "results" above is nan, then the actual
    201   // result cannot be nan either.
    202   int nans = 0;
    203   for (int i = 0; i < 4; ++i) {
    204     if (std::isnan(results[i])) ++nans;
    205   }
    206   if (nans == 4) return Type::NaN();  // [inf..inf] - [inf..inf] (all same sign)
    207   Type* type =
    208       Type::Range(array_min(results, 4), array_max(results, 4), zone());
    209   return nans == 0 ? type : Type::Union(type, Type::NaN(), zone());
    210   // Examples:
    211   //   [-inf, +inf] - [-inf, +inf] = [-inf, +inf] \/ NaN
    212   //   [-inf, -inf] - [-inf, -inf] = NaN
    213   //   [-inf, -inf] - [n, +inf] = [-inf, -inf] \/ NaN
    214   //   [m, +inf] - [-inf, n] = [-inf, +inf] \/ NaN
    215 }
    216 
    217 Type* OperationTyper::MultiplyRanger(Type* lhs, Type* rhs) {
    218   double results[4];
    219   double lmin = lhs->AsRange()->Min();
    220   double lmax = lhs->AsRange()->Max();
    221   double rmin = rhs->AsRange()->Min();
    222   double rmax = rhs->AsRange()->Max();
    223   results[0] = lmin * rmin;
    224   results[1] = lmin * rmax;
    225   results[2] = lmax * rmin;
    226   results[3] = lmax * rmax;
    227   // If the result may be nan, we give up on calculating a precise type, because
    228   // the discontinuity makes it too complicated.  Note that even if none of the
    229   // "results" above is nan, the actual result may still be, so we have to do a
    230   // different check:
    231   bool maybe_nan = (lhs->Maybe(cache_.kSingletonZero) &&
    232                     (rmin == -V8_INFINITY || rmax == +V8_INFINITY)) ||
    233                    (rhs->Maybe(cache_.kSingletonZero) &&
    234                     (lmin == -V8_INFINITY || lmax == +V8_INFINITY));
    235   if (maybe_nan) return cache_.kIntegerOrMinusZeroOrNaN;  // Giving up.
    236   bool maybe_minuszero = (lhs->Maybe(cache_.kSingletonZero) && rmin < 0) ||
    237                          (rhs->Maybe(cache_.kSingletonZero) && lmin < 0);
    238   Type* range =
    239       Type::Range(array_min(results, 4), array_max(results, 4), zone());
    240   return maybe_minuszero ? Type::Union(range, Type::MinusZero(), zone())
    241                          : range;
    242 }
    243 
    244 Type* OperationTyper::ToNumber(Type* type) {
    245   if (type->Is(Type::Number())) return type;
    246   if (type->Is(Type::NullOrUndefined())) {
    247     if (type->Is(Type::Null())) return cache_.kSingletonZero;
    248     if (type->Is(Type::Undefined())) return Type::NaN();
    249     return Type::Union(Type::NaN(), cache_.kSingletonZero, zone());
    250   }
    251   if (type->Is(Type::Boolean())) {
    252     if (type->Is(singleton_false_)) return cache_.kSingletonZero;
    253     if (type->Is(singleton_true_)) return cache_.kSingletonOne;
    254     return cache_.kZeroOrOne;
    255   }
    256   if (type->Is(Type::NumberOrOddball())) {
    257     if (type->Is(Type::NumberOrUndefined())) {
    258       type = Type::Union(type, Type::NaN(), zone());
    259     } else if (type->Is(Type::NullOrNumber())) {
    260       type = Type::Union(type, cache_.kSingletonZero, zone());
    261     } else if (type->Is(Type::BooleanOrNullOrNumber())) {
    262       type = Type::Union(type, cache_.kZeroOrOne, zone());
    263     } else {
    264       type = Type::Union(type, cache_.kZeroOrOneOrNaN, zone());
    265     }
    266     return Type::Intersect(type, Type::Number(), zone());
    267   }
    268   return Type::Number();
    269 }
    270 
    271 Type* OperationTyper::NumberAbs(Type* type) {
    272   DCHECK(type->Is(Type::Number()));
    273 
    274   if (!type->IsInhabited()) {
    275     return Type::None();
    276   }
    277 
    278   bool const maybe_nan = type->Maybe(Type::NaN());
    279   bool const maybe_minuszero = type->Maybe(Type::MinusZero());
    280   type = Type::Intersect(type, Type::PlainNumber(), zone());
    281   double const max = type->Max();
    282   double const min = type->Min();
    283   if (min < 0) {
    284     if (type->Is(cache_.kInteger)) {
    285       type = Type::Range(0.0, std::max(std::fabs(min), std::fabs(max)), zone());
    286     } else {
    287       type = Type::PlainNumber();
    288     }
    289   }
    290   if (maybe_minuszero) {
    291     type = Type::Union(type, cache_.kSingletonZero, zone());
    292   }
    293   if (maybe_nan) {
    294     type = Type::Union(type, Type::NaN(), zone());
    295   }
    296   return type;
    297 }
    298 
    299 Type* OperationTyper::NumberAcos(Type* type) {
    300   DCHECK(type->Is(Type::Number()));
    301   return Type::Number();
    302 }
    303 
    304 Type* OperationTyper::NumberAcosh(Type* type) {
    305   DCHECK(type->Is(Type::Number()));
    306   return Type::Number();
    307 }
    308 
    309 Type* OperationTyper::NumberAsin(Type* type) {
    310   DCHECK(type->Is(Type::Number()));
    311   return Type::Number();
    312 }
    313 
    314 Type* OperationTyper::NumberAsinh(Type* type) {
    315   DCHECK(type->Is(Type::Number()));
    316   return Type::Number();
    317 }
    318 
    319 Type* OperationTyper::NumberAtan(Type* type) {
    320   DCHECK(type->Is(Type::Number()));
    321   return Type::Number();
    322 }
    323 
    324 Type* OperationTyper::NumberAtanh(Type* type) {
    325   DCHECK(type->Is(Type::Number()));
    326   return Type::Number();
    327 }
    328 
    329 Type* OperationTyper::NumberCbrt(Type* type) {
    330   DCHECK(type->Is(Type::Number()));
    331   return Type::Number();
    332 }
    333 
    334 Type* OperationTyper::NumberCeil(Type* type) {
    335   DCHECK(type->Is(Type::Number()));
    336   if (type->Is(cache_.kIntegerOrMinusZeroOrNaN)) return type;
    337   // TODO(bmeurer): We could infer a more precise type here.
    338   return cache_.kIntegerOrMinusZeroOrNaN;
    339 }
    340 
    341 Type* OperationTyper::NumberClz32(Type* type) {
    342   DCHECK(type->Is(Type::Number()));
    343   return cache_.kZeroToThirtyTwo;
    344 }
    345 
    346 Type* OperationTyper::NumberCos(Type* type) {
    347   DCHECK(type->Is(Type::Number()));
    348   return Type::Number();
    349 }
    350 
    351 Type* OperationTyper::NumberCosh(Type* type) {
    352   DCHECK(type->Is(Type::Number()));
    353   return Type::Number();
    354 }
    355 
    356 Type* OperationTyper::NumberExp(Type* type) {
    357   DCHECK(type->Is(Type::Number()));
    358   return Type::Union(Type::PlainNumber(), Type::NaN(), zone());
    359 }
    360 
    361 Type* OperationTyper::NumberExpm1(Type* type) {
    362   DCHECK(type->Is(Type::Number()));
    363   return Type::Union(Type::PlainNumber(), Type::NaN(), zone());
    364 }
    365 
    366 Type* OperationTyper::NumberFloor(Type* type) {
    367   DCHECK(type->Is(Type::Number()));
    368   if (type->Is(cache_.kIntegerOrMinusZeroOrNaN)) return type;
    369   // TODO(bmeurer): We could infer a more precise type here.
    370   return cache_.kIntegerOrMinusZeroOrNaN;
    371 }
    372 
    373 Type* OperationTyper::NumberFround(Type* type) {
    374   DCHECK(type->Is(Type::Number()));
    375   return Type::Number();
    376 }
    377 
    378 Type* OperationTyper::NumberLog(Type* type) {
    379   DCHECK(type->Is(Type::Number()));
    380   return Type::Number();
    381 }
    382 
    383 Type* OperationTyper::NumberLog1p(Type* type) {
    384   DCHECK(type->Is(Type::Number()));
    385   return Type::Number();
    386 }
    387 
    388 Type* OperationTyper::NumberLog2(Type* type) {
    389   DCHECK(type->Is(Type::Number()));
    390   return Type::Number();
    391 }
    392 
    393 Type* OperationTyper::NumberLog10(Type* type) {
    394   DCHECK(type->Is(Type::Number()));
    395   return Type::Number();
    396 }
    397 
    398 Type* OperationTyper::NumberRound(Type* type) {
    399   DCHECK(type->Is(Type::Number()));
    400   if (type->Is(cache_.kIntegerOrMinusZeroOrNaN)) return type;
    401   // TODO(bmeurer): We could infer a more precise type here.
    402   return cache_.kIntegerOrMinusZeroOrNaN;
    403 }
    404 
    405 Type* OperationTyper::NumberSign(Type* type) {
    406   DCHECK(type->Is(Type::Number()));
    407   if (type->Is(cache_.kZeroish)) return type;
    408   bool maybe_minuszero = type->Maybe(Type::MinusZero());
    409   bool maybe_nan = type->Maybe(Type::NaN());
    410   type = Type::Intersect(type, Type::PlainNumber(), zone());
    411   if (type->Max() < 0.0) {
    412     type = cache_.kSingletonMinusOne;
    413   } else if (type->Max() <= 0.0) {
    414     type = cache_.kMinusOneOrZero;
    415   } else if (type->Min() > 0.0) {
    416     type = cache_.kSingletonOne;
    417   } else if (type->Min() >= 0.0) {
    418     type = cache_.kZeroOrOne;
    419   } else {
    420     type = Type::Range(-1.0, 1.0, zone());
    421   }
    422   if (maybe_minuszero) type = Type::Union(type, Type::MinusZero(), zone());
    423   if (maybe_nan) type = Type::Union(type, Type::NaN(), zone());
    424   return type;
    425 }
    426 
    427 Type* OperationTyper::NumberSin(Type* type) {
    428   DCHECK(type->Is(Type::Number()));
    429   return Type::Number();
    430 }
    431 
    432 Type* OperationTyper::NumberSinh(Type* type) {
    433   DCHECK(type->Is(Type::Number()));
    434   return Type::Number();
    435 }
    436 
    437 Type* OperationTyper::NumberSqrt(Type* type) {
    438   DCHECK(type->Is(Type::Number()));
    439   return Type::Number();
    440 }
    441 
    442 Type* OperationTyper::NumberTan(Type* type) {
    443   DCHECK(type->Is(Type::Number()));
    444   return Type::Number();
    445 }
    446 
    447 Type* OperationTyper::NumberTanh(Type* type) {
    448   DCHECK(type->Is(Type::Number()));
    449   return Type::Number();
    450 }
    451 
    452 Type* OperationTyper::NumberTrunc(Type* type) {
    453   DCHECK(type->Is(Type::Number()));
    454   if (type->Is(cache_.kIntegerOrMinusZeroOrNaN)) return type;
    455   // TODO(bmeurer): We could infer a more precise type here.
    456   return cache_.kIntegerOrMinusZeroOrNaN;
    457 }
    458 
    459 Type* OperationTyper::NumberToBoolean(Type* type) {
    460   DCHECK(type->Is(Type::Number()));
    461   if (!type->IsInhabited()) return Type::None();
    462   if (type->Is(cache_.kZeroish)) return singleton_false_;
    463   if (type->Is(Type::PlainNumber()) && (type->Max() < 0 || 0 < type->Min())) {
    464     return singleton_true_;  // Ruled out nan, -0 and +0.
    465   }
    466   return Type::Boolean();
    467 }
    468 
    469 Type* OperationTyper::NumberToInt32(Type* type) {
    470   DCHECK(type->Is(Type::Number()));
    471 
    472   if (type->Is(Type::Signed32())) return type;
    473   if (type->Is(cache_.kZeroish)) return cache_.kSingletonZero;
    474   if (type->Is(signed32ish_)) {
    475     return Type::Intersect(Type::Union(type, cache_.kSingletonZero, zone()),
    476                            Type::Signed32(), zone());
    477   }
    478   return Type::Signed32();
    479 }
    480 
    481 Type* OperationTyper::NumberToUint32(Type* type) {
    482   DCHECK(type->Is(Type::Number()));
    483 
    484   if (type->Is(Type::Unsigned32())) return type;
    485   if (type->Is(cache_.kZeroish)) return cache_.kSingletonZero;
    486   if (type->Is(unsigned32ish_)) {
    487     return Type::Intersect(Type::Union(type, cache_.kSingletonZero, zone()),
    488                            Type::Unsigned32(), zone());
    489   }
    490   return Type::Unsigned32();
    491 }
    492 
    493 Type* OperationTyper::NumberToUint8Clamped(Type* type) {
    494   DCHECK(type->Is(Type::Number()));
    495 
    496   if (type->Is(cache_.kUint8)) return type;
    497   return cache_.kUint8;
    498 }
    499 
    500 Type* OperationTyper::NumberSilenceNaN(Type* type) {
    501   DCHECK(type->Is(Type::Number()));
    502   // TODO(jarin): This is a terrible hack; we definitely need a dedicated type
    503   // for the hole (tagged and/or double). Otherwise if the input is the hole
    504   // NaN constant, we'd just eliminate this node in JSTypedLowering.
    505   if (type->Maybe(Type::NaN())) return Type::Number();
    506   return type;
    507 }
    508 
    509 Type* OperationTyper::NumberAdd(Type* lhs, Type* rhs) {
    510   DCHECK(lhs->Is(Type::Number()));
    511   DCHECK(rhs->Is(Type::Number()));
    512 
    513   if (!lhs->IsInhabited() || !rhs->IsInhabited()) {
    514     return Type::None();
    515   }
    516 
    517   // Addition can return NaN if either input can be NaN or we try to compute
    518   // the sum of two infinities of opposite sign.
    519   bool maybe_nan = lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN());
    520 
    521   // Addition can yield minus zero only if both inputs can be minus zero.
    522   bool maybe_minuszero = true;
    523   if (lhs->Maybe(Type::MinusZero())) {
    524     lhs = Type::Union(lhs, cache_.kSingletonZero, zone());
    525   } else {
    526     maybe_minuszero = false;
    527   }
    528   if (rhs->Maybe(Type::MinusZero())) {
    529     rhs = Type::Union(rhs, cache_.kSingletonZero, zone());
    530   } else {
    531     maybe_minuszero = false;
    532   }
    533 
    534   // We can give more precise types for integers.
    535   Type* type = Type::None();
    536   lhs = Type::Intersect(lhs, Type::PlainNumber(), zone());
    537   rhs = Type::Intersect(rhs, Type::PlainNumber(), zone());
    538   if (lhs->IsInhabited() && rhs->IsInhabited()) {
    539     if (lhs->Is(cache_.kInteger) && rhs->Is(cache_.kInteger)) {
    540       type = AddRanger(lhs->Min(), lhs->Max(), rhs->Min(), rhs->Max());
    541     } else {
    542       if ((lhs->Maybe(minus_infinity_) && rhs->Maybe(infinity_)) ||
    543           (rhs->Maybe(minus_infinity_) && lhs->Maybe(infinity_))) {
    544         maybe_nan = true;
    545       }
    546       type = Type::PlainNumber();
    547     }
    548   }
    549 
    550   // Take into account the -0 and NaN information computed earlier.
    551   if (maybe_minuszero) type = Type::Union(type, Type::MinusZero(), zone());
    552   if (maybe_nan) type = Type::Union(type, Type::NaN(), zone());
    553   return type;
    554 }
    555 
    556 Type* OperationTyper::NumberSubtract(Type* lhs, Type* rhs) {
    557   DCHECK(lhs->Is(Type::Number()));
    558   DCHECK(rhs->Is(Type::Number()));
    559 
    560   if (!lhs->IsInhabited() || !rhs->IsInhabited()) {
    561     return Type::None();
    562   }
    563 
    564   // Subtraction can return NaN if either input can be NaN or we try to
    565   // compute the sum of two infinities of opposite sign.
    566   bool maybe_nan = lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN());
    567 
    568   // Subtraction can yield minus zero if {lhs} can be minus zero and {rhs}
    569   // can be zero.
    570   bool maybe_minuszero = false;
    571   if (lhs->Maybe(Type::MinusZero())) {
    572     lhs = Type::Union(lhs, cache_.kSingletonZero, zone());
    573     maybe_minuszero = rhs->Maybe(cache_.kSingletonZero);
    574   }
    575   if (rhs->Maybe(Type::MinusZero())) {
    576     rhs = Type::Union(rhs, cache_.kSingletonZero, zone());
    577   }
    578 
    579   // We can give more precise types for integers.
    580   Type* type = Type::None();
    581   lhs = Type::Intersect(lhs, Type::PlainNumber(), zone());
    582   rhs = Type::Intersect(rhs, Type::PlainNumber(), zone());
    583   if (lhs->IsInhabited() && rhs->IsInhabited()) {
    584     if (lhs->Is(cache_.kInteger) && rhs->Is(cache_.kInteger)) {
    585       type = SubtractRanger(lhs->Min(), lhs->Max(), rhs->Min(), rhs->Max());
    586     } else {
    587       if ((lhs->Maybe(infinity_) && rhs->Maybe(infinity_)) ||
    588           (rhs->Maybe(minus_infinity_) && lhs->Maybe(minus_infinity_))) {
    589         maybe_nan = true;
    590       }
    591       type = Type::PlainNumber();
    592     }
    593   }
    594 
    595   // Take into account the -0 and NaN information computed earlier.
    596   if (maybe_minuszero) type = Type::Union(type, Type::MinusZero(), zone());
    597   if (maybe_nan) type = Type::Union(type, Type::NaN(), zone());
    598   return type;
    599 }
    600 
    601 Type* OperationTyper::NumberMultiply(Type* lhs, Type* rhs) {
    602   DCHECK(lhs->Is(Type::Number()));
    603   DCHECK(rhs->Is(Type::Number()));
    604 
    605   if (!lhs->IsInhabited() || !rhs->IsInhabited()) {
    606     return Type::None();
    607   }
    608 
    609   lhs = Rangify(lhs);
    610   rhs = Rangify(rhs);
    611   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
    612   if (lhs->IsRange() && rhs->IsRange()) {
    613     return MultiplyRanger(lhs, rhs);
    614   }
    615   return Type::Number();
    616 }
    617 
    618 Type* OperationTyper::NumberDivide(Type* lhs, Type* rhs) {
    619   DCHECK(lhs->Is(Type::Number()));
    620   DCHECK(rhs->Is(Type::Number()));
    621 
    622   if (!lhs->IsInhabited() || !rhs->IsInhabited()) {
    623     return Type::None();
    624   }
    625 
    626   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
    627   // Division is tricky, so all we do is try ruling out nan.
    628   bool maybe_nan =
    629       lhs->Maybe(Type::NaN()) || rhs->Maybe(cache_.kZeroish) ||
    630       ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) &&
    631        (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
    632   return maybe_nan ? Type::Number() : Type::OrderedNumber();
    633 }
    634 
    635 Type* OperationTyper::NumberModulus(Type* lhs, Type* rhs) {
    636   DCHECK(lhs->Is(Type::Number()));
    637   DCHECK(rhs->Is(Type::Number()));
    638 
    639   // Modulus can yield NaN if either {lhs} or {rhs} are NaN, or
    640   // {lhs} is not finite, or the {rhs} is a zero value.
    641   bool maybe_nan = lhs->Maybe(Type::NaN()) || rhs->Maybe(cache_.kZeroish) ||
    642                    lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY;
    643 
    644   // Deal with -0 inputs, only the signbit of {lhs} matters for the result.
    645   bool maybe_minuszero = false;
    646   if (lhs->Maybe(Type::MinusZero())) {
    647     maybe_minuszero = true;
    648     lhs = Type::Union(lhs, cache_.kSingletonZero, zone());
    649   }
    650   if (rhs->Maybe(Type::MinusZero())) {
    651     rhs = Type::Union(rhs, cache_.kSingletonZero, zone());
    652   }
    653 
    654   // Rule out NaN and -0, and check what we can do with the remaining type info.
    655   Type* type = Type::None();
    656   lhs = Type::Intersect(lhs, Type::PlainNumber(), zone());
    657   rhs = Type::Intersect(rhs, Type::PlainNumber(), zone());
    658 
    659   // We can only derive a meaningful type if both {lhs} and {rhs} are inhabited,
    660   // and the {rhs} is not 0, otherwise the result is NaN independent of {lhs}.
    661   if (lhs->IsInhabited() && !rhs->Is(cache_.kSingletonZero)) {
    662     // Determine the bounds of {lhs} and {rhs}.
    663     double const lmin = lhs->Min();
    664     double const lmax = lhs->Max();
    665     double const rmin = rhs->Min();
    666     double const rmax = rhs->Max();
    667 
    668     // The sign of the result is the sign of the {lhs}.
    669     if (lmin < 0.0) maybe_minuszero = true;
    670 
    671     // For integer inputs {lhs} and {rhs} we can infer a precise type.
    672     if (lhs->Is(cache_.kInteger) && rhs->Is(cache_.kInteger)) {
    673       double labs = std::max(std::abs(lmin), std::abs(lmax));
    674       double rabs = std::max(std::abs(rmin), std::abs(rmax)) - 1;
    675       double abs = std::min(labs, rabs);
    676       double min = 0.0, max = 0.0;
    677       if (lmin >= 0.0) {
    678         // {lhs} positive.
    679         min = 0.0;
    680         max = abs;
    681       } else if (lmax <= 0.0) {
    682         // {lhs} negative.
    683         min = 0.0 - abs;
    684         max = 0.0;
    685       } else {
    686         // {lhs} positive or negative.
    687         min = 0.0 - abs;
    688         max = abs;
    689       }
    690       type = Type::Range(min, max, zone());
    691     } else {
    692       type = Type::PlainNumber();
    693     }
    694   }
    695 
    696   // Take into account the -0 and NaN information computed earlier.
    697   if (maybe_minuszero) type = Type::Union(type, Type::MinusZero(), zone());
    698   if (maybe_nan) type = Type::Union(type, Type::NaN(), zone());
    699   return type;
    700 }
    701 
    702 Type* OperationTyper::NumberBitwiseOr(Type* lhs, Type* rhs) {
    703   DCHECK(lhs->Is(Type::Number()));
    704   DCHECK(rhs->Is(Type::Number()));
    705 
    706   if (!lhs->IsInhabited() || !rhs->IsInhabited()) return Type::None();
    707 
    708   lhs = NumberToInt32(lhs);
    709   rhs = NumberToInt32(rhs);
    710 
    711   double lmin = lhs->Min();
    712   double rmin = rhs->Min();
    713   double lmax = lhs->Max();
    714   double rmax = rhs->Max();
    715   // Or-ing any two values results in a value no smaller than their minimum.
    716   // Even no smaller than their maximum if both values are non-negative.
    717   double min =
    718       lmin >= 0 && rmin >= 0 ? std::max(lmin, rmin) : std::min(lmin, rmin);
    719   double max = kMaxInt;
    720 
    721   // Or-ing with 0 is essentially a conversion to int32.
    722   if (rmin == 0 && rmax == 0) {
    723     min = lmin;
    724     max = lmax;
    725   }
    726   if (lmin == 0 && lmax == 0) {
    727     min = rmin;
    728     max = rmax;
    729   }
    730 
    731   if (lmax < 0 || rmax < 0) {
    732     // Or-ing two values of which at least one is negative results in a negative
    733     // value.
    734     max = std::min(max, -1.0);
    735   }
    736   return Type::Range(min, max, zone());
    737 }
    738 
    739 Type* OperationTyper::NumberBitwiseAnd(Type* lhs, Type* rhs) {
    740   DCHECK(lhs->Is(Type::Number()));
    741   DCHECK(rhs->Is(Type::Number()));
    742 
    743   if (!lhs->IsInhabited() || !rhs->IsInhabited()) return Type::None();
    744 
    745   lhs = NumberToInt32(lhs);
    746   rhs = NumberToInt32(rhs);
    747 
    748   double lmin = lhs->Min();
    749   double rmin = rhs->Min();
    750   double lmax = lhs->Max();
    751   double rmax = rhs->Max();
    752   double min = kMinInt;
    753   // And-ing any two values results in a value no larger than their maximum.
    754   // Even no larger than their minimum if both values are non-negative.
    755   double max =
    756       lmin >= 0 && rmin >= 0 ? std::min(lmax, rmax) : std::max(lmax, rmax);
    757   // And-ing with a non-negative value x causes the result to be between
    758   // zero and x.
    759   if (lmin >= 0) {
    760     min = 0;
    761     max = std::min(max, lmax);
    762   }
    763   if (rmin >= 0) {
    764     min = 0;
    765     max = std::min(max, rmax);
    766   }
    767   return Type::Range(min, max, zone());
    768 }
    769 
    770 Type* OperationTyper::NumberBitwiseXor(Type* lhs, Type* rhs) {
    771   DCHECK(lhs->Is(Type::Number()));
    772   DCHECK(rhs->Is(Type::Number()));
    773 
    774   if (!lhs->IsInhabited() || !rhs->IsInhabited()) return Type::None();
    775 
    776   lhs = NumberToInt32(lhs);
    777   rhs = NumberToInt32(rhs);
    778 
    779   double lmin = lhs->Min();
    780   double rmin = rhs->Min();
    781   double lmax = lhs->Max();
    782   double rmax = rhs->Max();
    783   if ((lmin >= 0 && rmin >= 0) || (lmax < 0 && rmax < 0)) {
    784     // Xor-ing negative or non-negative values results in a non-negative value.
    785     return Type::Unsigned31();
    786   }
    787   if ((lmax < 0 && rmin >= 0) || (lmin >= 0 && rmax < 0)) {
    788     // Xor-ing a negative and a non-negative value results in a negative value.
    789     // TODO(jarin) Use a range here.
    790     return Type::Negative32();
    791   }
    792   return Type::Signed32();
    793 }
    794 
    795 Type* OperationTyper::NumberShiftLeft(Type* lhs, Type* rhs) {
    796   DCHECK(lhs->Is(Type::Number()));
    797   DCHECK(rhs->Is(Type::Number()));
    798 
    799   // TODO(turbofan): Infer a better type here.
    800   return Type::Signed32();
    801 }
    802 
    803 Type* OperationTyper::NumberShiftRight(Type* lhs, Type* rhs) {
    804   DCHECK(lhs->Is(Type::Number()));
    805   DCHECK(rhs->Is(Type::Number()));
    806 
    807   if (!lhs->IsInhabited() || !rhs->IsInhabited()) return Type::None();
    808 
    809   lhs = NumberToInt32(lhs);
    810   rhs = NumberToUint32(rhs);
    811 
    812   double min = kMinInt;
    813   double max = kMaxInt;
    814   if (lhs->Min() >= 0) {
    815     // Right-shifting a non-negative value cannot make it negative, nor larger.
    816     min = std::max(min, 0.0);
    817     max = std::min(max, lhs->Max());
    818     if (rhs->Min() > 0 && rhs->Max() <= 31) {
    819       max = static_cast<int>(max) >> static_cast<int>(rhs->Min());
    820     }
    821   }
    822   if (lhs->Max() < 0) {
    823     // Right-shifting a negative value cannot make it non-negative, nor smaller.
    824     min = std::max(min, lhs->Min());
    825     max = std::min(max, -1.0);
    826     if (rhs->Min() > 0 && rhs->Max() <= 31) {
    827       min = static_cast<int>(min) >> static_cast<int>(rhs->Min());
    828     }
    829   }
    830   if (rhs->Min() > 0 && rhs->Max() <= 31) {
    831     // Right-shifting by a positive value yields a small integer value.
    832     double shift_min = kMinInt >> static_cast<int>(rhs->Min());
    833     double shift_max = kMaxInt >> static_cast<int>(rhs->Min());
    834     min = std::max(min, shift_min);
    835     max = std::min(max, shift_max);
    836   }
    837   // TODO(jarin) Ideally, the following micro-optimization should be performed
    838   // by the type constructor.
    839   if (max == kMaxInt && min == kMinInt) return Type::Signed32();
    840   return Type::Range(min, max, zone());
    841 }
    842 
    843 Type* OperationTyper::NumberShiftRightLogical(Type* lhs, Type* rhs) {
    844   DCHECK(lhs->Is(Type::Number()));
    845   DCHECK(rhs->Is(Type::Number()));
    846 
    847   if (!lhs->IsInhabited()) return Type::None();
    848 
    849   lhs = NumberToUint32(lhs);
    850 
    851   // Logical right-shifting any value cannot make it larger.
    852   return Type::Range(0.0, lhs->Max(), zone());
    853 }
    854 
    855 Type* OperationTyper::NumberAtan2(Type* lhs, Type* rhs) {
    856   DCHECK(lhs->Is(Type::Number()));
    857   DCHECK(rhs->Is(Type::Number()));
    858   return Type::Number();
    859 }
    860 
    861 Type* OperationTyper::NumberImul(Type* lhs, Type* rhs) {
    862   DCHECK(lhs->Is(Type::Number()));
    863   DCHECK(rhs->Is(Type::Number()));
    864   // TODO(turbofan): We should be able to do better here.
    865   return Type::Signed32();
    866 }
    867 
    868 Type* OperationTyper::NumberMax(Type* lhs, Type* rhs) {
    869   DCHECK(lhs->Is(Type::Number()));
    870   DCHECK(rhs->Is(Type::Number()));
    871   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) {
    872     return Type::NaN();
    873   }
    874   Type* type = Type::None();
    875   // TODO(turbofan): Improve minus zero handling here.
    876   if (lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN())) {
    877     type = Type::Union(type, Type::NaN(), zone());
    878   }
    879   lhs = Type::Intersect(lhs, Type::OrderedNumber(), zone());
    880   rhs = Type::Intersect(rhs, Type::OrderedNumber(), zone());
    881   if (lhs->Is(cache_.kInteger) && rhs->Is(cache_.kInteger)) {
    882     double max = std::max(lhs->Max(), rhs->Max());
    883     double min = std::max(lhs->Min(), rhs->Min());
    884     type = Type::Union(type, Type::Range(min, max, zone()), zone());
    885   } else {
    886     type = Type::Union(type, Type::Union(lhs, rhs, zone()), zone());
    887   }
    888   return type;
    889 }
    890 
    891 Type* OperationTyper::NumberMin(Type* lhs, Type* rhs) {
    892   DCHECK(lhs->Is(Type::Number()));
    893   DCHECK(rhs->Is(Type::Number()));
    894   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) {
    895     return Type::NaN();
    896   }
    897   Type* type = Type::None();
    898   // TODO(turbofan): Improve minus zero handling here.
    899   if (lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN())) {
    900     type = Type::Union(type, Type::NaN(), zone());
    901   }
    902   lhs = Type::Intersect(lhs, Type::OrderedNumber(), zone());
    903   rhs = Type::Intersect(rhs, Type::OrderedNumber(), zone());
    904   if (lhs->Is(cache_.kInteger) && rhs->Is(cache_.kInteger)) {
    905     double max = std::min(lhs->Max(), rhs->Max());
    906     double min = std::min(lhs->Min(), rhs->Min());
    907     type = Type::Union(type, Type::Range(min, max, zone()), zone());
    908   } else {
    909     type = Type::Union(type, Type::Union(lhs, rhs, zone()), zone());
    910   }
    911   return type;
    912 }
    913 
    914 Type* OperationTyper::NumberPow(Type* lhs, Type* rhs) {
    915   DCHECK(lhs->Is(Type::Number()));
    916   DCHECK(rhs->Is(Type::Number()));
    917   // TODO(turbofan): We should be able to do better here.
    918   return Type::Number();
    919 }
    920 
    921 #define SPECULATIVE_NUMBER_BINOP(Name)                                     \
    922   Type* OperationTyper::Speculative##Name(Type* lhs, Type* rhs) {          \
    923     lhs = ToNumber(Type::Intersect(lhs, Type::NumberOrOddball(), zone())); \
    924     rhs = ToNumber(Type::Intersect(rhs, Type::NumberOrOddball(), zone())); \
    925     return Name(lhs, rhs);                                                 \
    926   }
    927 SPECULATIVE_NUMBER_BINOP(NumberAdd)
    928 SPECULATIVE_NUMBER_BINOP(NumberSubtract)
    929 SPECULATIVE_NUMBER_BINOP(NumberMultiply)
    930 SPECULATIVE_NUMBER_BINOP(NumberDivide)
    931 SPECULATIVE_NUMBER_BINOP(NumberModulus)
    932 SPECULATIVE_NUMBER_BINOP(NumberBitwiseOr)
    933 SPECULATIVE_NUMBER_BINOP(NumberBitwiseAnd)
    934 SPECULATIVE_NUMBER_BINOP(NumberBitwiseXor)
    935 SPECULATIVE_NUMBER_BINOP(NumberShiftLeft)
    936 SPECULATIVE_NUMBER_BINOP(NumberShiftRight)
    937 SPECULATIVE_NUMBER_BINOP(NumberShiftRightLogical)
    938 #undef SPECULATIVE_NUMBER_BINOP
    939 
    940 Type* OperationTyper::ToPrimitive(Type* type) {
    941   if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) {
    942     return type;
    943   }
    944   return Type::Primitive();
    945 }
    946 
    947 Type* OperationTyper::Invert(Type* type) {
    948   DCHECK(type->Is(Type::Boolean()));
    949   DCHECK(type->IsInhabited());
    950   if (type->Is(singleton_false())) return singleton_true();
    951   if (type->Is(singleton_true())) return singleton_false();
    952   return type;
    953 }
    954 
    955 OperationTyper::ComparisonOutcome OperationTyper::Invert(
    956     ComparisonOutcome outcome) {
    957   ComparisonOutcome result(0);
    958   if ((outcome & kComparisonUndefined) != 0) result |= kComparisonUndefined;
    959   if ((outcome & kComparisonTrue) != 0) result |= kComparisonFalse;
    960   if ((outcome & kComparisonFalse) != 0) result |= kComparisonTrue;
    961   return result;
    962 }
    963 
    964 Type* OperationTyper::FalsifyUndefined(ComparisonOutcome outcome) {
    965   if ((outcome & kComparisonFalse) != 0 ||
    966       (outcome & kComparisonUndefined) != 0) {
    967     return (outcome & kComparisonTrue) != 0 ? Type::Boolean()
    968                                             : singleton_false();
    969   }
    970   // Type should be non empty, so we know it should be true.
    971   DCHECK((outcome & kComparisonTrue) != 0);
    972   return singleton_true();
    973 }
    974 
    975 Type* OperationTyper::TypeTypeGuard(const Operator* sigma_op, Type* input) {
    976   return Type::Intersect(input, TypeGuardTypeOf(sigma_op), zone());
    977 }
    978 
    979 }  // namespace compiler
    980 }  // namespace internal
    981 }  // namespace v8
    982