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