operation-typer.cc revision 62ed631aa0ff23db68a47fd423efa9c019ff2c9e 
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
15namespace v8 {
16namespace internal {
17namespace compiler {
18
19OperationTyper::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
34Type* OperationTyper::Merge(Type* left, Type* right) {
35  return Type::Union(left, right, zone());
36}
37
38Type* 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
114Type* 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
130namespace {
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.
135double 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.
150double 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
164Type* 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
191Type* 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
217Type* 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
244Type* 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
271Type* 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
299Type* OperationTyper::NumberAcos(Type* type) {
300  DCHECK(type->Is(Type::Number()));
301  return Type::Number();
302}
303
304Type* OperationTyper::NumberAcosh(Type* type) {
305  DCHECK(type->Is(Type::Number()));
306  return Type::Number();
307}
308
309Type* OperationTyper::NumberAsin(Type* type) {
310  DCHECK(type->Is(Type::Number()));
311  return Type::Number();
312}
313
314Type* OperationTyper::NumberAsinh(Type* type) {
315  DCHECK(type->Is(Type::Number()));
316  return Type::Number();
317}
318
319Type* OperationTyper::NumberAtan(Type* type) {
320  DCHECK(type->Is(Type::Number()));
321  return Type::Number();
322}
323
324Type* OperationTyper::NumberAtanh(Type* type) {
325  DCHECK(type->Is(Type::Number()));
326  return Type::Number();
327}
328
329Type* OperationTyper::NumberCbrt(Type* type) {
330  DCHECK(type->Is(Type::Number()));
331  return Type::Number();
332}
333
334Type* 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
341Type* OperationTyper::NumberClz32(Type* type) {
342  DCHECK(type->Is(Type::Number()));
343  return cache_.kZeroToThirtyTwo;
344}
345
346Type* OperationTyper::NumberCos(Type* type) {
347  DCHECK(type->Is(Type::Number()));
348  return Type::Number();
349}
350
351Type* OperationTyper::NumberCosh(Type* type) {
352  DCHECK(type->Is(Type::Number()));
353  return Type::Number();
354}
355
356Type* OperationTyper::NumberExp(Type* type) {
357  DCHECK(type->Is(Type::Number()));
358  return Type::Union(Type::PlainNumber(), Type::NaN(), zone());
359}
360
361Type* OperationTyper::NumberExpm1(Type* type) {
362  DCHECK(type->Is(Type::Number()));
363  return Type::Union(Type::PlainNumber(), Type::NaN(), zone());
364}
365
366Type* 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
374Type* OperationTyper::NumberFround(Type* type) {
375  DCHECK(type->Is(Type::Number()));
376  return Type::Number();
377}
378
379Type* OperationTyper::NumberLog(Type* type) {
380  DCHECK(type->Is(Type::Number()));
381  return Type::Number();
382}
383
384Type* OperationTyper::NumberLog1p(Type* type) {
385  DCHECK(type->Is(Type::Number()));
386  return Type::Number();
387}
388
389Type* OperationTyper::NumberLog2(Type* type) {
390  DCHECK(type->Is(Type::Number()));
391  return Type::Number();
392}
393
394Type* OperationTyper::NumberLog10(Type* type) {
395  DCHECK(type->Is(Type::Number()));
396  return Type::Number();
397}
398
399Type* 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
406Type* 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
428Type* OperationTyper::NumberSin(Type* type) {
429  DCHECK(type->Is(Type::Number()));
430  return Type::Number();
431}
432
433Type* OperationTyper::NumberSinh(Type* type) {
434  DCHECK(type->Is(Type::Number()));
435  return Type::Number();
436}
437
438Type* OperationTyper::NumberSqrt(Type* type) {
439  DCHECK(type->Is(Type::Number()));
440  return Type::Number();
441}
442
443Type* OperationTyper::NumberTan(Type* type) {
444  DCHECK(type->Is(Type::Number()));
445  return Type::Number();
446}
447
448Type* OperationTyper::NumberTanh(Type* type) {
449  DCHECK(type->Is(Type::Number()));
450  return Type::Number();
451}
452
453Type* 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
460Type* 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
470Type* 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
482Type* 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
494Type* 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
501Type* 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
510Type* 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
557Type* 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
602Type* 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
619Type* 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
643Type* 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
710Type* 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
747Type* 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
778Type* 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
803Type* 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
838Type* 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
863Type* 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
892Type* OperationTyper::NumberAtan2(Type* lhs, Type* rhs) {
893  DCHECK(lhs->Is(Type::Number()));
894  DCHECK(rhs->Is(Type::Number()));
895  return Type::Number();
896}
897
898Type* 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
905Type* 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
928Type* 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
951Type* 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  }
964SPECULATIVE_NUMBER_BINOP(NumberAdd)
965SPECULATIVE_NUMBER_BINOP(NumberSubtract)
966SPECULATIVE_NUMBER_BINOP(NumberMultiply)
967SPECULATIVE_NUMBER_BINOP(NumberDivide)
968SPECULATIVE_NUMBER_BINOP(NumberModulus)
969SPECULATIVE_NUMBER_BINOP(NumberBitwiseOr)
970SPECULATIVE_NUMBER_BINOP(NumberBitwiseAnd)
971SPECULATIVE_NUMBER_BINOP(NumberBitwiseXor)
972SPECULATIVE_NUMBER_BINOP(NumberShiftLeft)
973SPECULATIVE_NUMBER_BINOP(NumberShiftRight)
974SPECULATIVE_NUMBER_BINOP(NumberShiftRightLogical)
975#undef SPECULATIVE_NUMBER_BINOP
976
977Type* OperationTyper::ToPrimitive(Type* type) {
978  if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) {
979    return type;
980  }
981  return Type::Primitive();
982}
983
984Type* 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
992OperationTyper::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
1001Type* 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
1012Type* 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