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