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   type = Type::Intersect(type, Type::MinusZeroOrNaN(), zone());
    370   type = Type::Union(type, cache_.kInteger, zone());
    371   return type;
    372 }
    373 
    374 Type* OperationTyper::NumberFround(Type* type) {
    375   DCHECK(type->Is(Type::Number()));
    376   return Type::Number();
    377 }
    378 
    379 Type* OperationTyper::NumberLog(Type* type) {
    380   DCHECK(type->Is(Type::Number()));
    381   return Type::Number();
    382 }
    383 
    384 Type* OperationTyper::NumberLog1p(Type* type) {
    385   DCHECK(type->Is(Type::Number()));
    386   return Type::Number();
    387 }
    388 
    389 Type* OperationTyper::NumberLog2(Type* type) {
    390   DCHECK(type->Is(Type::Number()));
    391   return Type::Number();
    392 }
    393 
    394 Type* OperationTyper::NumberLog10(Type* type) {
    395   DCHECK(type->Is(Type::Number()));
    396   return Type::Number();
    397 }
    398 
    399 Type* OperationTyper::NumberRound(Type* type) {
    400   DCHECK(type->Is(Type::Number()));
    401   if (type->Is(cache_.kIntegerOrMinusZeroOrNaN)) return type;
    402   // TODO(bmeurer): We could infer a more precise type here.
    403   return cache_.kIntegerOrMinusZeroOrNaN;
    404 }
    405 
    406 Type* OperationTyper::NumberSign(Type* type) {
    407   DCHECK(type->Is(Type::Number()));
    408   if (type->Is(cache_.kZeroish)) return type;
    409   bool maybe_minuszero = type->Maybe(Type::MinusZero());
    410   bool maybe_nan = type->Maybe(Type::NaN());
    411   type = Type::Intersect(type, Type::PlainNumber(), zone());
    412   if (type->Max() < 0.0) {
    413     type = cache_.kSingletonMinusOne;
    414   } else if (type->Max() <= 0.0) {
    415     type = cache_.kMinusOneOrZero;
    416   } else if (type->Min() > 0.0) {
    417     type = cache_.kSingletonOne;
    418   } else if (type->Min() >= 0.0) {
    419     type = cache_.kZeroOrOne;
    420   } else {
    421     type = Type::Range(-1.0, 1.0, zone());
    422   }
    423   if (maybe_minuszero) type = Type::Union(type, Type::MinusZero(), zone());
    424   if (maybe_nan) type = Type::Union(type, Type::NaN(), zone());
    425   return type;
    426 }
    427 
    428 Type* OperationTyper::NumberSin(Type* type) {
    429   DCHECK(type->Is(Type::Number()));
    430   return Type::Number();
    431 }
    432 
    433 Type* OperationTyper::NumberSinh(Type* type) {
    434   DCHECK(type->Is(Type::Number()));
    435   return Type::Number();
    436 }
    437 
    438 Type* OperationTyper::NumberSqrt(Type* type) {
    439   DCHECK(type->Is(Type::Number()));
    440   return Type::Number();
    441 }
    442 
    443 Type* OperationTyper::NumberTan(Type* type) {
    444   DCHECK(type->Is(Type::Number()));
    445   return Type::Number();
    446 }
    447 
    448 Type* OperationTyper::NumberTanh(Type* type) {
    449   DCHECK(type->Is(Type::Number()));
    450   return Type::Number();
    451 }
    452 
    453 Type* OperationTyper::NumberTrunc(Type* type) {
    454   DCHECK(type->Is(Type::Number()));
    455   if (type->Is(cache_.kIntegerOrMinusZeroOrNaN)) return type;
    456   // TODO(bmeurer): We could infer a more precise type here.
    457   return cache_.kIntegerOrMinusZeroOrNaN;
    458 }
    459 
    460 Type* OperationTyper::NumberToBoolean(Type* type) {
    461   DCHECK(type->Is(Type::Number()));
    462   if (!type->IsInhabited()) return Type::None();
    463   if (type->Is(cache_.kZeroish)) return singleton_false_;
    464   if (type->Is(Type::PlainNumber()) && (type->Max() < 0 || 0 < type->Min())) {
    465     return singleton_true_;  // Ruled out nan, -0 and +0.
    466   }
    467   return Type::Boolean();
    468 }
    469 
    470 Type* OperationTyper::NumberToInt32(Type* type) {
    471   DCHECK(type->Is(Type::Number()));
    472 
    473   if (type->Is(Type::Signed32())) return type;
    474   if (type->Is(cache_.kZeroish)) return cache_.kSingletonZero;
    475   if (type->Is(signed32ish_)) {
    476     return Type::Intersect(Type::Union(type, cache_.kSingletonZero, zone()),
    477                            Type::Signed32(), zone());
    478   }
    479   return Type::Signed32();
    480 }
    481 
    482 Type* OperationTyper::NumberToUint32(Type* type) {
    483   DCHECK(type->Is(Type::Number()));
    484 
    485   if (type->Is(Type::Unsigned32())) return type;
    486   if (type->Is(cache_.kZeroish)) return cache_.kSingletonZero;
    487   if (type->Is(unsigned32ish_)) {
    488     return Type::Intersect(Type::Union(type, cache_.kSingletonZero, zone()),
    489                            Type::Unsigned32(), zone());
    490   }
    491   return Type::Unsigned32();
    492 }
    493 
    494 Type* OperationTyper::NumberToUint8Clamped(Type* type) {
    495   DCHECK(type->Is(Type::Number()));
    496 
    497   if (type->Is(cache_.kUint8)) return type;
    498   return cache_.kUint8;
    499 }
    500 
    501 Type* OperationTyper::NumberSilenceNaN(Type* type) {
    502   DCHECK(type->Is(Type::Number()));
    503   // TODO(jarin): This is a terrible hack; we definitely need a dedicated type
    504   // for the hole (tagged and/or double). Otherwise if the input is the hole
    505   // NaN constant, we'd just eliminate this node in JSTypedLowering.
    506   if (type->Maybe(Type::NaN())) return Type::Number();
    507   return type;
    508 }
    509 
    510 Type* OperationTyper::NumberAdd(Type* lhs, Type* rhs) {
    511   DCHECK(lhs->Is(Type::Number()));
    512   DCHECK(rhs->Is(Type::Number()));
    513 
    514   if (!lhs->IsInhabited() || !rhs->IsInhabited()) {
    515     return Type::None();
    516   }
    517 
    518   // Addition can return NaN if either input can be NaN or we try to compute
    519   // the sum of two infinities of opposite sign.
    520   bool maybe_nan = lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN());
    521 
    522   // Addition can yield minus zero only if both inputs can be minus zero.
    523   bool maybe_minuszero = true;
    524   if (lhs->Maybe(Type::MinusZero())) {
    525     lhs = Type::Union(lhs, cache_.kSingletonZero, zone());
    526   } else {
    527     maybe_minuszero = false;
    528   }
    529   if (rhs->Maybe(Type::MinusZero())) {
    530     rhs = Type::Union(rhs, cache_.kSingletonZero, zone());
    531   } else {
    532     maybe_minuszero = false;
    533   }
    534 
    535   // We can give more precise types for integers.
    536   Type* type = Type::None();
    537   lhs = Type::Intersect(lhs, Type::PlainNumber(), zone());
    538   rhs = Type::Intersect(rhs, Type::PlainNumber(), zone());
    539   if (lhs->IsInhabited() && rhs->IsInhabited()) {
    540     if (lhs->Is(cache_.kInteger) && rhs->Is(cache_.kInteger)) {
    541       type = AddRanger(lhs->Min(), lhs->Max(), rhs->Min(), rhs->Max());
    542     } else {
    543       if ((lhs->Maybe(minus_infinity_) && rhs->Maybe(infinity_)) ||
    544           (rhs->Maybe(minus_infinity_) && lhs->Maybe(infinity_))) {
    545         maybe_nan = true;
    546       }
    547       type = Type::PlainNumber();
    548     }
    549   }
    550 
    551   // Take into account the -0 and NaN information computed earlier.
    552   if (maybe_minuszero) type = Type::Union(type, Type::MinusZero(), zone());
    553   if (maybe_nan) type = Type::Union(type, Type::NaN(), zone());
    554   return type;
    555 }
    556 
    557 Type* OperationTyper::NumberSubtract(Type* lhs, Type* rhs) {
    558   DCHECK(lhs->Is(Type::Number()));
    559   DCHECK(rhs->Is(Type::Number()));
    560 
    561   if (!lhs->IsInhabited() || !rhs->IsInhabited()) {
    562     return Type::None();
    563   }
    564 
    565   // Subtraction can return NaN if either input can be NaN or we try to
    566   // compute the sum of two infinities of opposite sign.
    567   bool maybe_nan = lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN());
    568 
    569   // Subtraction can yield minus zero if {lhs} can be minus zero and {rhs}
    570   // can be zero.
    571   bool maybe_minuszero = false;
    572   if (lhs->Maybe(Type::MinusZero())) {
    573     lhs = Type::Union(lhs, cache_.kSingletonZero, zone());
    574     maybe_minuszero = rhs->Maybe(cache_.kSingletonZero);
    575   }
    576   if (rhs->Maybe(Type::MinusZero())) {
    577     rhs = Type::Union(rhs, cache_.kSingletonZero, zone());
    578   }
    579 
    580   // We can give more precise types for integers.
    581   Type* type = Type::None();
    582   lhs = Type::Intersect(lhs, Type::PlainNumber(), zone());
    583   rhs = Type::Intersect(rhs, Type::PlainNumber(), zone());
    584   if (lhs->IsInhabited() && rhs->IsInhabited()) {
    585     if (lhs->Is(cache_.kInteger) && rhs->Is(cache_.kInteger)) {
    586       type = SubtractRanger(lhs->Min(), lhs->Max(), rhs->Min(), rhs->Max());
    587     } else {
    588       if ((lhs->Maybe(infinity_) && rhs->Maybe(infinity_)) ||
    589           (rhs->Maybe(minus_infinity_) && lhs->Maybe(minus_infinity_))) {
    590         maybe_nan = true;
    591       }
    592       type = Type::PlainNumber();
    593     }
    594   }
    595 
    596   // Take into account the -0 and NaN information computed earlier.
    597   if (maybe_minuszero) type = Type::Union(type, Type::MinusZero(), zone());
    598   if (maybe_nan) type = Type::Union(type, Type::NaN(), zone());
    599   return type;
    600 }
    601 
    602 Type* OperationTyper::NumberMultiply(Type* lhs, Type* rhs) {
    603   DCHECK(lhs->Is(Type::Number()));
    604   DCHECK(rhs->Is(Type::Number()));
    605 
    606   if (!lhs->IsInhabited() || !rhs->IsInhabited()) {
    607     return Type::None();
    608   }
    609 
    610   lhs = Rangify(lhs);
    611   rhs = Rangify(rhs);
    612   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
    613   if (lhs->IsRange() && rhs->IsRange()) {
    614     return MultiplyRanger(lhs, rhs);
    615   }
    616   return Type::Number();
    617 }
    618 
    619 Type* OperationTyper::NumberDivide(Type* lhs, Type* rhs) {
    620   DCHECK(lhs->Is(Type::Number()));
    621   DCHECK(rhs->Is(Type::Number()));
    622 
    623   if (!lhs->IsInhabited() || !rhs->IsInhabited()) {
    624     return Type::None();
    625   }
    626 
    627   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
    628   // Division is tricky, so all we do is try ruling out -0 and NaN.
    629   bool maybe_minuszero = !lhs->Is(cache_.kPositiveIntegerOrNaN) ||
    630                          !rhs->Is(cache_.kPositiveIntegerOrNaN);
    631   bool maybe_nan =
    632       lhs->Maybe(Type::NaN()) || rhs->Maybe(cache_.kZeroish) ||
    633       ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) &&
    634        (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
    635 
    636   // Take into account the -0 and NaN information computed earlier.
    637   Type* type = Type::PlainNumber();
    638   if (maybe_minuszero) type = Type::Union(type, Type::MinusZero(), zone());
    639   if (maybe_nan) type = Type::Union(type, Type::NaN(), zone());
    640   return type;
    641 }
    642 
    643 Type* OperationTyper::NumberModulus(Type* lhs, Type* rhs) {
    644   DCHECK(lhs->Is(Type::Number()));
    645   DCHECK(rhs->Is(Type::Number()));
    646 
    647   // Modulus can yield NaN if either {lhs} or {rhs} are NaN, or
    648   // {lhs} is not finite, or the {rhs} is a zero value.
    649   bool maybe_nan = lhs->Maybe(Type::NaN()) || rhs->Maybe(cache_.kZeroish) ||
    650                    lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY;
    651 
    652   // Deal with -0 inputs, only the signbit of {lhs} matters for the result.
    653   bool maybe_minuszero = false;
    654   if (lhs->Maybe(Type::MinusZero())) {
    655     maybe_minuszero = true;
    656     lhs = Type::Union(lhs, cache_.kSingletonZero, zone());
    657   }
    658   if (rhs->Maybe(Type::MinusZero())) {
    659     rhs = Type::Union(rhs, cache_.kSingletonZero, zone());
    660   }
    661 
    662   // Rule out NaN and -0, and check what we can do with the remaining type info.
    663   Type* type = Type::None();
    664   lhs = Type::Intersect(lhs, Type::PlainNumber(), zone());
    665   rhs = Type::Intersect(rhs, Type::PlainNumber(), zone());
    666 
    667   // We can only derive a meaningful type if both {lhs} and {rhs} are inhabited,
    668   // and the {rhs} is not 0, otherwise the result is NaN independent of {lhs}.
    669   if (lhs->IsInhabited() && !rhs->Is(cache_.kSingletonZero)) {
    670     // Determine the bounds of {lhs} and {rhs}.
    671     double const lmin = lhs->Min();
    672     double const lmax = lhs->Max();
    673     double const rmin = rhs->Min();
    674     double const rmax = rhs->Max();
    675 
    676     // The sign of the result is the sign of the {lhs}.
    677     if (lmin < 0.0) maybe_minuszero = true;
    678 
    679     // For integer inputs {lhs} and {rhs} we can infer a precise type.
    680     if (lhs->Is(cache_.kInteger) && rhs->Is(cache_.kInteger)) {
    681       double labs = std::max(std::abs(lmin), std::abs(lmax));
    682       double rabs = std::max(std::abs(rmin), std::abs(rmax)) - 1;
    683       double abs = std::min(labs, rabs);
    684       double min = 0.0, max = 0.0;
    685       if (lmin >= 0.0) {
    686         // {lhs} positive.
    687         min = 0.0;
    688         max = abs;
    689       } else if (lmax <= 0.0) {
    690         // {lhs} negative.
    691         min = 0.0 - abs;
    692         max = 0.0;
    693       } else {
    694         // {lhs} positive or negative.
    695         min = 0.0 - abs;
    696         max = abs;
    697       }
    698       type = Type::Range(min, max, zone());
    699     } else {
    700       type = Type::PlainNumber();
    701     }
    702   }
    703 
    704   // Take into account the -0 and NaN information computed earlier.
    705   if (maybe_minuszero) type = Type::Union(type, Type::MinusZero(), zone());
    706   if (maybe_nan) type = Type::Union(type, Type::NaN(), zone());
    707   return type;
    708 }
    709 
    710 Type* OperationTyper::NumberBitwiseOr(Type* lhs, Type* rhs) {
    711   DCHECK(lhs->Is(Type::Number()));
    712   DCHECK(rhs->Is(Type::Number()));
    713 
    714   if (!lhs->IsInhabited() || !rhs->IsInhabited()) return Type::None();
    715 
    716   lhs = NumberToInt32(lhs);
    717   rhs = NumberToInt32(rhs);
    718 
    719   double lmin = lhs->Min();
    720   double rmin = rhs->Min();
    721   double lmax = lhs->Max();
    722   double rmax = rhs->Max();
    723   // Or-ing any two values results in a value no smaller than their minimum.
    724   // Even no smaller than their maximum if both values are non-negative.
    725   double min =
    726       lmin >= 0 && rmin >= 0 ? std::max(lmin, rmin) : std::min(lmin, rmin);
    727   double max = kMaxInt;
    728 
    729   // Or-ing with 0 is essentially a conversion to int32.
    730   if (rmin == 0 && rmax == 0) {
    731     min = lmin;
    732     max = lmax;
    733   }
    734   if (lmin == 0 && lmax == 0) {
    735     min = rmin;
    736     max = rmax;
    737   }
    738 
    739   if (lmax < 0 || rmax < 0) {
    740     // Or-ing two values of which at least one is negative results in a negative
    741     // value.
    742     max = std::min(max, -1.0);
    743   }
    744   return Type::Range(min, max, zone());
    745 }
    746 
    747 Type* OperationTyper::NumberBitwiseAnd(Type* lhs, Type* rhs) {
    748   DCHECK(lhs->Is(Type::Number()));
    749   DCHECK(rhs->Is(Type::Number()));
    750 
    751   if (!lhs->IsInhabited() || !rhs->IsInhabited()) return Type::None();
    752 
    753   lhs = NumberToInt32(lhs);
    754   rhs = NumberToInt32(rhs);
    755 
    756   double lmin = lhs->Min();
    757   double rmin = rhs->Min();
    758   double lmax = lhs->Max();
    759   double rmax = rhs->Max();
    760   double min = kMinInt;
    761   // And-ing any two values results in a value no larger than their maximum.
    762   // Even no larger than their minimum if both values are non-negative.
    763   double max =
    764       lmin >= 0 && rmin >= 0 ? std::min(lmax, rmax) : std::max(lmax, rmax);
    765   // And-ing with a non-negative value x causes the result to be between
    766   // zero and x.
    767   if (lmin >= 0) {
    768     min = 0;
    769     max = std::min(max, lmax);
    770   }
    771   if (rmin >= 0) {
    772     min = 0;
    773     max = std::min(max, rmax);
    774   }
    775   return Type::Range(min, max, zone());
    776 }
    777 
    778 Type* OperationTyper::NumberBitwiseXor(Type* lhs, Type* rhs) {
    779   DCHECK(lhs->Is(Type::Number()));
    780   DCHECK(rhs->Is(Type::Number()));
    781 
    782   if (!lhs->IsInhabited() || !rhs->IsInhabited()) return Type::None();
    783 
    784   lhs = NumberToInt32(lhs);
    785   rhs = NumberToInt32(rhs);
    786 
    787   double lmin = lhs->Min();
    788   double rmin = rhs->Min();
    789   double lmax = lhs->Max();
    790   double rmax = rhs->Max();
    791   if ((lmin >= 0 && rmin >= 0) || (lmax < 0 && rmax < 0)) {
    792     // Xor-ing negative or non-negative values results in a non-negative value.
    793     return Type::Unsigned31();
    794   }
    795   if ((lmax < 0 && rmin >= 0) || (lmin >= 0 && rmax < 0)) {
    796     // Xor-ing a negative and a non-negative value results in a negative value.
    797     // TODO(jarin) Use a range here.
    798     return Type::Negative32();
    799   }
    800   return Type::Signed32();
    801 }
    802 
    803 Type* OperationTyper::NumberShiftLeft(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   int32_t min_lhs = lhs->Min();
    813   int32_t max_lhs = lhs->Max();
    814   uint32_t min_rhs = rhs->Min();
    815   uint32_t max_rhs = rhs->Max();
    816   if (max_rhs > 31) {
    817     // rhs can be larger than the bitmask
    818     max_rhs = 31;
    819     min_rhs = 0;
    820   }
    821 
    822   if (max_lhs > (kMaxInt >> max_rhs) || min_lhs < (kMinInt >> max_rhs)) {
    823     // overflow possible
    824     return Type::Signed32();
    825   }
    826 
    827   double min =
    828       std::min(static_cast<int32_t>(static_cast<uint32_t>(min_lhs) << min_rhs),
    829                static_cast<int32_t>(static_cast<uint32_t>(min_lhs) << max_rhs));
    830   double max =
    831       std::max(static_cast<int32_t>(static_cast<uint32_t>(max_lhs) << min_rhs),
    832                static_cast<int32_t>(static_cast<uint32_t>(max_lhs) << max_rhs));
    833 
    834   if (max == kMaxInt && min == kMinInt) return Type::Signed32();
    835   return Type::Range(min, max, zone());
    836 }
    837 
    838 Type* OperationTyper::NumberShiftRight(Type* lhs, Type* rhs) {
    839   DCHECK(lhs->Is(Type::Number()));
    840   DCHECK(rhs->Is(Type::Number()));
    841 
    842   if (!lhs->IsInhabited() || !rhs->IsInhabited()) return Type::None();
    843 
    844   lhs = NumberToInt32(lhs);
    845   rhs = NumberToUint32(rhs);
    846 
    847   int32_t min_lhs = lhs->Min();
    848   int32_t max_lhs = lhs->Max();
    849   uint32_t min_rhs = rhs->Min();
    850   uint32_t max_rhs = rhs->Max();
    851   if (max_rhs > 31) {
    852     // rhs can be larger than the bitmask
    853     max_rhs = 31;
    854     min_rhs = 0;
    855   }
    856   double min = std::min(min_lhs >> min_rhs, min_lhs >> max_rhs);
    857   double max = std::max(max_lhs >> min_rhs, max_lhs >> max_rhs);
    858 
    859   if (max == kMaxInt && min == kMinInt) return Type::Signed32();
    860   return Type::Range(min, max, zone());
    861 }
    862 
    863 Type* OperationTyper::NumberShiftRightLogical(Type* lhs, Type* rhs) {
    864   DCHECK(lhs->Is(Type::Number()));
    865   DCHECK(rhs->Is(Type::Number()));
    866 
    867   if (!lhs->IsInhabited() || !rhs->IsInhabited()) return Type::None();
    868 
    869   lhs = NumberToUint32(lhs);
    870   rhs = NumberToUint32(rhs);
    871 
    872   uint32_t min_lhs = lhs->Min();
    873   uint32_t max_lhs = lhs->Max();
    874   uint32_t min_rhs = rhs->Min();
    875   uint32_t max_rhs = rhs->Max();
    876   if (max_rhs > 31) {
    877     // rhs can be larger than the bitmask
    878     max_rhs = 31;
    879     min_rhs = 0;
    880   }
    881 
    882   double min = min_lhs >> max_rhs;
    883   double max = max_lhs >> min_rhs;
    884   DCHECK_LE(0, min);
    885   DCHECK_LE(max, kMaxUInt32);
    886 
    887   if (min == 0 && max == kMaxInt) return Type::Unsigned31();
    888   if (min == 0 && max == kMaxUInt32) return Type::Unsigned32();
    889   return Type::Range(min, max, zone());
    890 }
    891 
    892 Type* OperationTyper::NumberAtan2(Type* lhs, Type* rhs) {
    893   DCHECK(lhs->Is(Type::Number()));
    894   DCHECK(rhs->Is(Type::Number()));
    895   return Type::Number();
    896 }
    897 
    898 Type* OperationTyper::NumberImul(Type* lhs, Type* rhs) {
    899   DCHECK(lhs->Is(Type::Number()));
    900   DCHECK(rhs->Is(Type::Number()));
    901   // TODO(turbofan): We should be able to do better here.
    902   return Type::Signed32();
    903 }
    904 
    905 Type* OperationTyper::NumberMax(Type* lhs, Type* rhs) {
    906   DCHECK(lhs->Is(Type::Number()));
    907   DCHECK(rhs->Is(Type::Number()));
    908   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) {
    909     return Type::NaN();
    910   }
    911   Type* type = Type::None();
    912   // TODO(turbofan): Improve minus zero handling here.
    913   if (lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN())) {
    914     type = Type::Union(type, Type::NaN(), zone());
    915   }
    916   lhs = Type::Intersect(lhs, Type::OrderedNumber(), zone());
    917   rhs = Type::Intersect(rhs, Type::OrderedNumber(), zone());
    918   if (lhs->Is(cache_.kInteger) && rhs->Is(cache_.kInteger)) {
    919     double max = std::max(lhs->Max(), rhs->Max());
    920     double min = std::max(lhs->Min(), rhs->Min());
    921     type = Type::Union(type, Type::Range(min, max, zone()), zone());
    922   } else {
    923     type = Type::Union(type, Type::Union(lhs, rhs, zone()), zone());
    924   }
    925   return type;
    926 }
    927 
    928 Type* OperationTyper::NumberMin(Type* lhs, Type* rhs) {
    929   DCHECK(lhs->Is(Type::Number()));
    930   DCHECK(rhs->Is(Type::Number()));
    931   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) {
    932     return Type::NaN();
    933   }
    934   Type* type = Type::None();
    935   // TODO(turbofan): Improve minus zero handling here.
    936   if (lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN())) {
    937     type = Type::Union(type, Type::NaN(), zone());
    938   }
    939   lhs = Type::Intersect(lhs, Type::OrderedNumber(), zone());
    940   rhs = Type::Intersect(rhs, Type::OrderedNumber(), zone());
    941   if (lhs->Is(cache_.kInteger) && rhs->Is(cache_.kInteger)) {
    942     double max = std::min(lhs->Max(), rhs->Max());
    943     double min = std::min(lhs->Min(), rhs->Min());
    944     type = Type::Union(type, Type::Range(min, max, zone()), zone());
    945   } else {
    946     type = Type::Union(type, Type::Union(lhs, rhs, zone()), zone());
    947   }
    948   return type;
    949 }
    950 
    951 Type* OperationTyper::NumberPow(Type* lhs, Type* rhs) {
    952   DCHECK(lhs->Is(Type::Number()));
    953   DCHECK(rhs->Is(Type::Number()));
    954   // TODO(turbofan): We should be able to do better here.
    955   return Type::Number();
    956 }
    957 
    958 #define SPECULATIVE_NUMBER_BINOP(Name)                                     \
    959   Type* OperationTyper::Speculative##Name(Type* lhs, Type* rhs) {          \
    960     lhs = ToNumber(Type::Intersect(lhs, Type::NumberOrOddball(), zone())); \
    961     rhs = ToNumber(Type::Intersect(rhs, Type::NumberOrOddball(), zone())); \
    962     return Name(lhs, rhs);                                                 \
    963   }
    964 SPECULATIVE_NUMBER_BINOP(NumberAdd)
    965 SPECULATIVE_NUMBER_BINOP(NumberSubtract)
    966 SPECULATIVE_NUMBER_BINOP(NumberMultiply)
    967 SPECULATIVE_NUMBER_BINOP(NumberDivide)
    968 SPECULATIVE_NUMBER_BINOP(NumberModulus)
    969 SPECULATIVE_NUMBER_BINOP(NumberBitwiseOr)
    970 SPECULATIVE_NUMBER_BINOP(NumberBitwiseAnd)
    971 SPECULATIVE_NUMBER_BINOP(NumberBitwiseXor)
    972 SPECULATIVE_NUMBER_BINOP(NumberShiftLeft)
    973 SPECULATIVE_NUMBER_BINOP(NumberShiftRight)
    974 SPECULATIVE_NUMBER_BINOP(NumberShiftRightLogical)
    975 #undef SPECULATIVE_NUMBER_BINOP
    976 
    977 Type* OperationTyper::ToPrimitive(Type* type) {
    978   if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) {
    979     return type;
    980   }
    981   return Type::Primitive();
    982 }
    983 
    984 Type* OperationTyper::Invert(Type* type) {
    985   DCHECK(type->Is(Type::Boolean()));
    986   DCHECK(type->IsInhabited());
    987   if (type->Is(singleton_false())) return singleton_true();
    988   if (type->Is(singleton_true())) return singleton_false();
    989   return type;
    990 }
    991 
    992 OperationTyper::ComparisonOutcome OperationTyper::Invert(
    993     ComparisonOutcome outcome) {
    994   ComparisonOutcome result(0);
    995   if ((outcome & kComparisonUndefined) != 0) result |= kComparisonUndefined;
    996   if ((outcome & kComparisonTrue) != 0) result |= kComparisonFalse;
    997   if ((outcome & kComparisonFalse) != 0) result |= kComparisonTrue;
    998   return result;
    999 }
   1000 
   1001 Type* OperationTyper::FalsifyUndefined(ComparisonOutcome outcome) {
   1002   if ((outcome & kComparisonFalse) != 0 ||
   1003       (outcome & kComparisonUndefined) != 0) {
   1004     return (outcome & kComparisonTrue) != 0 ? Type::Boolean()
   1005                                             : singleton_false();
   1006   }
   1007   // Type should be non empty, so we know it should be true.
   1008   DCHECK((outcome & kComparisonTrue) != 0);
   1009   return singleton_true();
   1010 }
   1011 
   1012 Type* OperationTyper::TypeTypeGuard(const Operator* sigma_op, Type* input) {
   1013   return Type::Intersect(input, TypeGuardTypeOf(sigma_op), zone());
   1014 }
   1015 
   1016 }  // namespace compiler
   1017 }  // namespace internal
   1018 }  // namespace v8
   1019