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 type = Type::Intersect(type, Type::MinusZeroOrNaN(), zone());
370 type = Type::Union(type, cache_.kInteger, zone());
371 return type;
372 }
373
NumberFround(Type * type)374 Type* OperationTyper::NumberFround(Type* type) {
375 DCHECK(type->Is(Type::Number()));
376 return Type::Number();
377 }
378
NumberLog(Type * type)379 Type* OperationTyper::NumberLog(Type* type) {
380 DCHECK(type->Is(Type::Number()));
381 return Type::Number();
382 }
383
NumberLog1p(Type * type)384 Type* OperationTyper::NumberLog1p(Type* type) {
385 DCHECK(type->Is(Type::Number()));
386 return Type::Number();
387 }
388
NumberLog2(Type * type)389 Type* OperationTyper::NumberLog2(Type* type) {
390 DCHECK(type->Is(Type::Number()));
391 return Type::Number();
392 }
393
NumberLog10(Type * type)394 Type* OperationTyper::NumberLog10(Type* type) {
395 DCHECK(type->Is(Type::Number()));
396 return Type::Number();
397 }
398
NumberRound(Type * type)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
NumberSign(Type * type)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
NumberSin(Type * type)428 Type* OperationTyper::NumberSin(Type* type) {
429 DCHECK(type->Is(Type::Number()));
430 return Type::Number();
431 }
432
NumberSinh(Type * type)433 Type* OperationTyper::NumberSinh(Type* type) {
434 DCHECK(type->Is(Type::Number()));
435 return Type::Number();
436 }
437
NumberSqrt(Type * type)438 Type* OperationTyper::NumberSqrt(Type* type) {
439 DCHECK(type->Is(Type::Number()));
440 return Type::Number();
441 }
442
NumberTan(Type * type)443 Type* OperationTyper::NumberTan(Type* type) {
444 DCHECK(type->Is(Type::Number()));
445 return Type::Number();
446 }
447
NumberTanh(Type * type)448 Type* OperationTyper::NumberTanh(Type* type) {
449 DCHECK(type->Is(Type::Number()));
450 return Type::Number();
451 }
452
NumberTrunc(Type * type)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
NumberToBoolean(Type * type)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
NumberToInt32(Type * type)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
NumberToUint32(Type * type)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
NumberToUint8Clamped(Type * type)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
NumberSilenceNaN(Type * type)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
NumberAdd(Type * lhs,Type * rhs)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
NumberSubtract(Type * lhs,Type * rhs)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
NumberMultiply(Type * lhs,Type * rhs)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
NumberDivide(Type * lhs,Type * rhs)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
NumberModulus(Type * lhs,Type * rhs)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
NumberBitwiseOr(Type * lhs,Type * rhs)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
NumberBitwiseAnd(Type * lhs,Type * rhs)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
NumberBitwiseXor(Type * lhs,Type * rhs)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
NumberShiftLeft(Type * lhs,Type * rhs)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
NumberShiftRight(Type * lhs,Type * rhs)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
NumberShiftRightLogical(Type * lhs,Type * rhs)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
NumberAtan2(Type * lhs,Type * rhs)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
NumberImul(Type * lhs,Type * rhs)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
NumberMax(Type * lhs,Type * rhs)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
NumberMin(Type * lhs,Type * rhs)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
NumberPow(Type * lhs,Type * rhs)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)
SPECULATIVE_NUMBER_BINOP(NumberSubtract)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
Invert(Type * type)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
Invert(ComparisonOutcome outcome)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
FalsifyUndefined(ComparisonOutcome outcome)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
TypeTypeGuard(const Operator * sigma_op,Type * input)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