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/factory.h"
      8 #include "src/isolate.h"
      9 #include "src/type-cache.h"
     10 #include "src/types.h"
     11 
     12 #include "src/objects-inl.h"
     13 
     14 namespace v8 {
     15 namespace internal {
     16 namespace compiler {
     17 
     18 OperationTyper::OperationTyper(Isolate* isolate, Zone* zone)
     19     : zone_(zone), cache_(TypeCache::Get()) {
     20   Factory* factory = isolate->factory();
     21   singleton_false_ = Type::Constant(factory->false_value(), zone);
     22   singleton_true_ = Type::Constant(factory->true_value(), zone);
     23   singleton_the_hole_ = Type::Constant(factory->the_hole_value(), zone);
     24 }
     25 
     26 Type* OperationTyper::Merge(Type* left, Type* right) {
     27   return Type::Union(left, right, zone());
     28 }
     29 
     30 Type* OperationTyper::WeakenRange(Type* previous_range, Type* current_range) {
     31   static const double kWeakenMinLimits[] = {0.0,
     32                                             -1073741824.0,
     33                                             -2147483648.0,
     34                                             -4294967296.0,
     35                                             -8589934592.0,
     36                                             -17179869184.0,
     37                                             -34359738368.0,
     38                                             -68719476736.0,
     39                                             -137438953472.0,
     40                                             -274877906944.0,
     41                                             -549755813888.0,
     42                                             -1099511627776.0,
     43                                             -2199023255552.0,
     44                                             -4398046511104.0,
     45                                             -8796093022208.0,
     46                                             -17592186044416.0,
     47                                             -35184372088832.0,
     48                                             -70368744177664.0,
     49                                             -140737488355328.0,
     50                                             -281474976710656.0,
     51                                             -562949953421312.0};
     52   static const double kWeakenMaxLimits[] = {0.0,
     53                                             1073741823.0,
     54                                             2147483647.0,
     55                                             4294967295.0,
     56                                             8589934591.0,
     57                                             17179869183.0,
     58                                             34359738367.0,
     59                                             68719476735.0,
     60                                             137438953471.0,
     61                                             274877906943.0,
     62                                             549755813887.0,
     63                                             1099511627775.0,
     64                                             2199023255551.0,
     65                                             4398046511103.0,
     66                                             8796093022207.0,
     67                                             17592186044415.0,
     68                                             35184372088831.0,
     69                                             70368744177663.0,
     70                                             140737488355327.0,
     71                                             281474976710655.0,
     72                                             562949953421311.0};
     73   STATIC_ASSERT(arraysize(kWeakenMinLimits) == arraysize(kWeakenMaxLimits));
     74 
     75   double current_min = current_range->Min();
     76   double new_min = current_min;
     77   // Find the closest lower entry in the list of allowed
     78   // minima (or negative infinity if there is no such entry).
     79   if (current_min != previous_range->Min()) {
     80     new_min = -V8_INFINITY;
     81     for (double const min : kWeakenMinLimits) {
     82       if (min <= current_min) {
     83         new_min = min;
     84         break;
     85       }
     86     }
     87   }
     88 
     89   double current_max = current_range->Max();
     90   double new_max = current_max;
     91   // Find the closest greater entry in the list of allowed
     92   // maxima (or infinity if there is no such entry).
     93   if (current_max != previous_range->Max()) {
     94     new_max = V8_INFINITY;
     95     for (double const max : kWeakenMaxLimits) {
     96       if (max >= current_max) {
     97         new_max = max;
     98         break;
     99       }
    100     }
    101   }
    102 
    103   return Type::Range(new_min, new_max, zone());
    104 }
    105 
    106 Type* OperationTyper::Rangify(Type* type) {
    107   if (type->IsRange()) return type;  // Shortcut.
    108   if (!type->Is(cache_.kInteger)) {
    109     return type;  // Give up on non-integer types.
    110   }
    111   double min = type->Min();
    112   double max = type->Max();
    113   // Handle the degenerate case of empty bitset types (such as
    114   // OtherUnsigned31 and OtherSigned32 on 64-bit architectures).
    115   if (std::isnan(min)) {
    116     DCHECK(std::isnan(max));
    117     return type;
    118   }
    119   return Type::Range(min, max, zone());
    120 }
    121 
    122 namespace {
    123 
    124 // Returns the array's least element, ignoring NaN.
    125 // There must be at least one non-NaN element.
    126 // Any -0 is converted to 0.
    127 double array_min(double a[], size_t n) {
    128   DCHECK(n != 0);
    129   double x = +V8_INFINITY;
    130   for (size_t i = 0; i < n; ++i) {
    131     if (!std::isnan(a[i])) {
    132       x = std::min(a[i], x);
    133     }
    134   }
    135   DCHECK(!std::isnan(x));
    136   return x == 0 ? 0 : x;  // -0 -> 0
    137 }
    138 
    139 // Returns the array's greatest element, ignoring NaN.
    140 // There must be at least one non-NaN element.
    141 // Any -0 is converted to 0.
    142 double array_max(double a[], size_t n) {
    143   DCHECK(n != 0);
    144   double x = -V8_INFINITY;
    145   for (size_t i = 0; i < n; ++i) {
    146     if (!std::isnan(a[i])) {
    147       x = std::max(a[i], x);
    148     }
    149   }
    150   DCHECK(!std::isnan(x));
    151   return x == 0 ? 0 : x;  // -0 -> 0
    152 }
    153 
    154 }  // namespace
    155 
    156 Type* OperationTyper::AddRanger(double lhs_min, double lhs_max, double rhs_min,
    157                                 double rhs_max) {
    158   double results[4];
    159   results[0] = lhs_min + rhs_min;
    160   results[1] = lhs_min + rhs_max;
    161   results[2] = lhs_max + rhs_min;
    162   results[3] = lhs_max + rhs_max;
    163   // Since none of the inputs can be -0, the result cannot be -0 either.
    164   // However, it can be nan (the sum of two infinities of opposite sign).
    165   // On the other hand, if none of the "results" above is nan, then the actual
    166   // result cannot be nan either.
    167   int nans = 0;
    168   for (int i = 0; i < 4; ++i) {
    169     if (std::isnan(results[i])) ++nans;
    170   }
    171   if (nans == 4) return Type::NaN();  // [-inf..-inf] + [inf..inf] or vice versa
    172   Type* range =
    173       Type::Range(array_min(results, 4), array_max(results, 4), zone());
    174   return nans == 0 ? range : Type::Union(range, Type::NaN(), zone());
    175   // Examples:
    176   //   [-inf, -inf] + [+inf, +inf] = NaN
    177   //   [-inf, -inf] + [n, +inf] = [-inf, -inf] \/ NaN
    178   //   [-inf, +inf] + [n, +inf] = [-inf, +inf] \/ NaN
    179   //   [-inf, m] + [n, +inf] = [-inf, +inf] \/ NaN
    180 }
    181 
    182 Type* OperationTyper::SubtractRanger(RangeType* lhs, RangeType* rhs) {
    183   double results[4];
    184   results[0] = lhs->Min() - rhs->Min();
    185   results[1] = lhs->Min() - rhs->Max();
    186   results[2] = lhs->Max() - rhs->Min();
    187   results[3] = lhs->Max() - rhs->Max();
    188   // Since none of the inputs can be -0, the result cannot be -0.
    189   // However, it can be nan (the subtraction of two infinities of same sign).
    190   // On the other hand, if none of the "results" above is nan, then the actual
    191   // result cannot be nan either.
    192   int nans = 0;
    193   for (int i = 0; i < 4; ++i) {
    194     if (std::isnan(results[i])) ++nans;
    195   }
    196   if (nans == 4) return Type::NaN();  // [inf..inf] - [inf..inf] (all same sign)
    197   Type* range =
    198       Type::Range(array_min(results, 4), array_max(results, 4), zone());
    199   return nans == 0 ? range : Type::Union(range, Type::NaN(), zone());
    200   // Examples:
    201   //   [-inf, +inf] - [-inf, +inf] = [-inf, +inf] \/ NaN
    202   //   [-inf, -inf] - [-inf, -inf] = NaN
    203   //   [-inf, -inf] - [n, +inf] = [-inf, -inf] \/ NaN
    204   //   [m, +inf] - [-inf, n] = [-inf, +inf] \/ NaN
    205 }
    206 
    207 Type* OperationTyper::ModulusRanger(RangeType* lhs, RangeType* rhs) {
    208   double lmin = lhs->Min();
    209   double lmax = lhs->Max();
    210   double rmin = rhs->Min();
    211   double rmax = rhs->Max();
    212 
    213   double labs = std::max(std::abs(lmin), std::abs(lmax));
    214   double rabs = std::max(std::abs(rmin), std::abs(rmax)) - 1;
    215   double abs = std::min(labs, rabs);
    216   bool maybe_minus_zero = false;
    217   double omin = 0;
    218   double omax = 0;
    219   if (lmin >= 0) {  // {lhs} positive.
    220     omin = 0;
    221     omax = abs;
    222   } else if (lmax <= 0) {  // {lhs} negative.
    223     omin = 0 - abs;
    224     omax = 0;
    225     maybe_minus_zero = true;
    226   } else {
    227     omin = 0 - abs;
    228     omax = abs;
    229     maybe_minus_zero = true;
    230   }
    231 
    232   Type* result = Type::Range(omin, omax, zone());
    233   if (maybe_minus_zero) result = Type::Union(result, Type::MinusZero(), zone());
    234   return result;
    235 }
    236 
    237 Type* OperationTyper::MultiplyRanger(Type* lhs, Type* rhs) {
    238   double results[4];
    239   double lmin = lhs->AsRange()->Min();
    240   double lmax = lhs->AsRange()->Max();
    241   double rmin = rhs->AsRange()->Min();
    242   double rmax = rhs->AsRange()->Max();
    243   results[0] = lmin * rmin;
    244   results[1] = lmin * rmax;
    245   results[2] = lmax * rmin;
    246   results[3] = lmax * rmax;
    247   // If the result may be nan, we give up on calculating a precise type,
    248   // because
    249   // the discontinuity makes it too complicated.  Note that even if none of
    250   // the
    251   // "results" above is nan, the actual result may still be, so we have to do
    252   // a
    253   // different check:
    254   bool maybe_nan = (lhs->Maybe(cache_.kSingletonZero) &&
    255                     (rmin == -V8_INFINITY || rmax == +V8_INFINITY)) ||
    256                    (rhs->Maybe(cache_.kSingletonZero) &&
    257                     (lmin == -V8_INFINITY || lmax == +V8_INFINITY));
    258   if (maybe_nan) return cache_.kIntegerOrMinusZeroOrNaN;  // Giving up.
    259   bool maybe_minuszero = (lhs->Maybe(cache_.kSingletonZero) && rmin < 0) ||
    260                          (rhs->Maybe(cache_.kSingletonZero) && lmin < 0);
    261   Type* range =
    262       Type::Range(array_min(results, 4), array_max(results, 4), zone());
    263   return maybe_minuszero ? Type::Union(range, Type::MinusZero(), zone())
    264                          : range;
    265 }
    266 
    267 Type* OperationTyper::ToNumber(Type* type) {
    268   if (type->Is(Type::Number())) return type;
    269   if (type->Is(Type::NullOrUndefined())) {
    270     if (type->Is(Type::Null())) return cache_.kSingletonZero;
    271     if (type->Is(Type::Undefined())) return Type::NaN();
    272     return Type::Union(Type::NaN(), cache_.kSingletonZero, zone());
    273   }
    274   if (type->Is(Type::NumberOrUndefined())) {
    275     return Type::Union(Type::Intersect(type, Type::Number(), zone()),
    276                        Type::NaN(), zone());
    277   }
    278   if (type->Is(singleton_false_)) return cache_.kSingletonZero;
    279   if (type->Is(singleton_true_)) return cache_.kSingletonOne;
    280   if (type->Is(Type::Boolean())) return cache_.kZeroOrOne;
    281   if (type->Is(Type::BooleanOrNumber())) {
    282     return Type::Union(Type::Intersect(type, Type::Number(), zone()),
    283                        cache_.kZeroOrOne, zone());
    284   }
    285   return Type::Number();
    286 }
    287 
    288 Type* OperationTyper::NumericAdd(Type* lhs, Type* rhs) {
    289   DCHECK(lhs->Is(Type::Number()));
    290   DCHECK(rhs->Is(Type::Number()));
    291 
    292   // We can give more precise types for integers.
    293   if (!lhs->Is(cache_.kIntegerOrMinusZeroOrNaN) ||
    294       !rhs->Is(cache_.kIntegerOrMinusZeroOrNaN)) {
    295     return Type::Number();
    296   }
    297   Type* int_lhs = Type::Intersect(lhs, cache_.kInteger, zone());
    298   Type* int_rhs = Type::Intersect(rhs, cache_.kInteger, zone());
    299   Type* result =
    300       AddRanger(int_lhs->Min(), int_lhs->Max(), int_rhs->Min(), int_rhs->Max());
    301   if (lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN())) {
    302     result = Type::Union(result, Type::NaN(), zone());
    303   }
    304   if (lhs->Maybe(Type::MinusZero()) && rhs->Maybe(Type::MinusZero())) {
    305     result = Type::Union(result, Type::MinusZero(), zone());
    306   }
    307   return result;
    308 }
    309 
    310 Type* OperationTyper::NumericSubtract(Type* lhs, Type* rhs) {
    311   DCHECK(lhs->Is(Type::Number()));
    312   DCHECK(rhs->Is(Type::Number()));
    313 
    314   lhs = Rangify(lhs);
    315   rhs = Rangify(rhs);
    316   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
    317   if (lhs->IsRange() && rhs->IsRange()) {
    318     return SubtractRanger(lhs->AsRange(), rhs->AsRange());
    319   }
    320   // TODO(neis): Deal with numeric bitsets here and elsewhere.
    321   return Type::Number();
    322 }
    323 
    324 Type* OperationTyper::NumericMultiply(Type* lhs, Type* rhs) {
    325   DCHECK(lhs->Is(Type::Number()));
    326   DCHECK(rhs->Is(Type::Number()));
    327   lhs = Rangify(lhs);
    328   rhs = Rangify(rhs);
    329   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
    330   if (lhs->IsRange() && rhs->IsRange()) {
    331     return MultiplyRanger(lhs, rhs);
    332   }
    333   return Type::Number();
    334 }
    335 
    336 Type* OperationTyper::NumericDivide(Type* lhs, Type* rhs) {
    337   DCHECK(lhs->Is(Type::Number()));
    338   DCHECK(rhs->Is(Type::Number()));
    339 
    340   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
    341   // Division is tricky, so all we do is try ruling out nan.
    342   bool maybe_nan =
    343       lhs->Maybe(Type::NaN()) || rhs->Maybe(cache_.kZeroish) ||
    344       ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) &&
    345        (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
    346   return maybe_nan ? Type::Number() : Type::OrderedNumber();
    347 }
    348 
    349 Type* OperationTyper::NumericModulus(Type* lhs, Type* rhs) {
    350   DCHECK(lhs->Is(Type::Number()));
    351   DCHECK(rhs->Is(Type::Number()));
    352   if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
    353 
    354   if (lhs->Maybe(Type::NaN()) || rhs->Maybe(cache_.kZeroish) ||
    355       lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) {
    356     // Result maybe NaN.
    357     return Type::Number();
    358   }
    359 
    360   lhs = Rangify(lhs);
    361   rhs = Rangify(rhs);
    362   if (lhs->IsRange() && rhs->IsRange()) {
    363     return ModulusRanger(lhs->AsRange(), rhs->AsRange());
    364   }
    365   return Type::OrderedNumber();
    366 }
    367 
    368 Type* OperationTyper::ToPrimitive(Type* type) {
    369   if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) {
    370     return type;
    371   }
    372   return Type::Primitive();
    373 }
    374 
    375 Type* OperationTyper::Invert(Type* type) {
    376   DCHECK(type->Is(Type::Boolean()));
    377   DCHECK(type->IsInhabited());
    378   if (type->Is(singleton_false())) return singleton_true();
    379   if (type->Is(singleton_true())) return singleton_false();
    380   return type;
    381 }
    382 
    383 OperationTyper::ComparisonOutcome OperationTyper::Invert(
    384     ComparisonOutcome outcome) {
    385   ComparisonOutcome result(0);
    386   if ((outcome & kComparisonUndefined) != 0) result |= kComparisonUndefined;
    387   if ((outcome & kComparisonTrue) != 0) result |= kComparisonFalse;
    388   if ((outcome & kComparisonFalse) != 0) result |= kComparisonTrue;
    389   return result;
    390 }
    391 
    392 Type* OperationTyper::FalsifyUndefined(ComparisonOutcome outcome) {
    393   if ((outcome & kComparisonFalse) != 0 ||
    394       (outcome & kComparisonUndefined) != 0) {
    395     return (outcome & kComparisonTrue) != 0 ? Type::Boolean()
    396                                             : singleton_false();
    397   }
    398   // Type should be non empty, so we know it should be true.
    399   DCHECK((outcome & kComparisonTrue) != 0);
    400   return singleton_true();
    401 }
    402 
    403 Type* OperationTyper::TypeJSAdd(Type* lhs, Type* rhs) {
    404   lhs = ToPrimitive(lhs);
    405   rhs = ToPrimitive(rhs);
    406   if (lhs->Maybe(Type::String()) || rhs->Maybe(Type::String())) {
    407     if (lhs->Is(Type::String()) || rhs->Is(Type::String())) {
    408       return Type::String();
    409     } else {
    410       return Type::NumberOrString();
    411     }
    412   }
    413   lhs = ToNumber(lhs);
    414   rhs = ToNumber(rhs);
    415   return NumericAdd(lhs, rhs);
    416 }
    417 
    418 Type* OperationTyper::TypeJSSubtract(Type* lhs, Type* rhs) {
    419   return NumericSubtract(ToNumber(lhs), ToNumber(rhs));
    420 }
    421 
    422 }  // namespace compiler
    423 }  // namespace internal
    424 }  // namespace v8
    425