1 // Copyright 2014 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 <iomanip>
6
7 #include "src/compiler/types.h"
8
9 #include "src/handles-inl.h"
10 #include "src/objects-inl.h"
11 #include "src/ostreams.h"
12
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16
17 // NOTE: If code is marked as being a "shortcut", this means that removing
18 // the code won't affect the semantics of the surrounding function definition.
19
20 // static
IsInteger(i::Object * x)21 bool Type::IsInteger(i::Object* x) {
22 return x->IsNumber() && Type::IsInteger(x->Number());
23 }
24
25 // -----------------------------------------------------------------------------
26 // Range-related helper functions.
27
IsEmpty()28 bool RangeType::Limits::IsEmpty() { return this->min > this->max; }
29
Intersect(Limits lhs,Limits rhs)30 RangeType::Limits RangeType::Limits::Intersect(Limits lhs, Limits rhs) {
31 DisallowHeapAllocation no_allocation;
32 Limits result(lhs);
33 if (lhs.min < rhs.min) result.min = rhs.min;
34 if (lhs.max > rhs.max) result.max = rhs.max;
35 return result;
36 }
37
Union(Limits lhs,Limits rhs)38 RangeType::Limits RangeType::Limits::Union(Limits lhs, Limits rhs) {
39 DisallowHeapAllocation no_allocation;
40 if (lhs.IsEmpty()) return rhs;
41 if (rhs.IsEmpty()) return lhs;
42 Limits result(lhs);
43 if (lhs.min > rhs.min) result.min = rhs.min;
44 if (lhs.max < rhs.max) result.max = rhs.max;
45 return result;
46 }
47
Overlap(RangeType * lhs,RangeType * rhs)48 bool Type::Overlap(RangeType* lhs, RangeType* rhs) {
49 DisallowHeapAllocation no_allocation;
50 return !RangeType::Limits::Intersect(RangeType::Limits(lhs),
51 RangeType::Limits(rhs))
52 .IsEmpty();
53 }
54
Contains(RangeType * lhs,RangeType * rhs)55 bool Type::Contains(RangeType* lhs, RangeType* rhs) {
56 DisallowHeapAllocation no_allocation;
57 return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
58 }
59
Contains(RangeType * range,i::Object * val)60 bool Type::Contains(RangeType* range, i::Object* val) {
61 DisallowHeapAllocation no_allocation;
62 return IsInteger(val) && range->Min() <= val->Number() &&
63 val->Number() <= range->Max();
64 }
65
66 // -----------------------------------------------------------------------------
67 // Min and Max computation.
68
Min()69 double Type::Min() {
70 DCHECK(this->Is(Number()));
71 if (this->IsBitset()) return BitsetType::Min(this->AsBitset());
72 if (this->IsUnion()) {
73 double min = +V8_INFINITY;
74 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
75 min = std::min(min, this->AsUnion()->Get(i)->Min());
76 }
77 return min;
78 }
79 if (this->IsRange()) return this->AsRange()->Min();
80 if (this->IsOtherNumberConstant())
81 return this->AsOtherNumberConstant()->Value();
82 UNREACHABLE();
83 return 0;
84 }
85
Max()86 double Type::Max() {
87 DCHECK(this->Is(Number()));
88 if (this->IsBitset()) return BitsetType::Max(this->AsBitset());
89 if (this->IsUnion()) {
90 double max = -V8_INFINITY;
91 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
92 max = std::max(max, this->AsUnion()->Get(i)->Max());
93 }
94 return max;
95 }
96 if (this->IsRange()) return this->AsRange()->Max();
97 if (this->IsOtherNumberConstant())
98 return this->AsOtherNumberConstant()->Value();
99 UNREACHABLE();
100 return 0;
101 }
102
103 // -----------------------------------------------------------------------------
104 // Glb and lub computation.
105
106 // The largest bitset subsumed by this type.
Glb(Type * type)107 Type::bitset BitsetType::Glb(Type* type) {
108 DisallowHeapAllocation no_allocation;
109 // Fast case.
110 if (IsBitset(type)) {
111 return type->AsBitset();
112 } else if (type->IsUnion()) {
113 SLOW_DCHECK(type->AsUnion()->Wellformed());
114 return type->AsUnion()->Get(0)->BitsetGlb() |
115 type->AsUnion()->Get(1)->BitsetGlb(); // Shortcut.
116 } else if (type->IsRange()) {
117 bitset glb =
118 BitsetType::Glb(type->AsRange()->Min(), type->AsRange()->Max());
119 return glb;
120 } else {
121 return kNone;
122 }
123 }
124
125 // The smallest bitset subsuming this type, possibly not a proper one.
Lub(Type * type)126 Type::bitset BitsetType::Lub(Type* type) {
127 DisallowHeapAllocation no_allocation;
128 if (IsBitset(type)) return type->AsBitset();
129 if (type->IsUnion()) {
130 // Take the representation from the first element, which is always
131 // a bitset.
132 int bitset = type->AsUnion()->Get(0)->BitsetLub();
133 for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
134 // Other elements only contribute their semantic part.
135 bitset |= type->AsUnion()->Get(i)->BitsetLub();
136 }
137 return bitset;
138 }
139 if (type->IsHeapConstant()) return type->AsHeapConstant()->Lub();
140 if (type->IsOtherNumberConstant())
141 return type->AsOtherNumberConstant()->Lub();
142 if (type->IsRange()) return type->AsRange()->Lub();
143 if (type->IsTuple()) return kOtherInternal;
144 UNREACHABLE();
145 return kNone;
146 }
147
Lub(i::Map * map)148 Type::bitset BitsetType::Lub(i::Map* map) {
149 DisallowHeapAllocation no_allocation;
150 switch (map->instance_type()) {
151 case STRING_TYPE:
152 case ONE_BYTE_STRING_TYPE:
153 case CONS_STRING_TYPE:
154 case CONS_ONE_BYTE_STRING_TYPE:
155 case THIN_STRING_TYPE:
156 case THIN_ONE_BYTE_STRING_TYPE:
157 case SLICED_STRING_TYPE:
158 case SLICED_ONE_BYTE_STRING_TYPE:
159 case EXTERNAL_STRING_TYPE:
160 case EXTERNAL_ONE_BYTE_STRING_TYPE:
161 case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
162 case SHORT_EXTERNAL_STRING_TYPE:
163 case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE:
164 case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
165 return kOtherString;
166 case INTERNALIZED_STRING_TYPE:
167 case ONE_BYTE_INTERNALIZED_STRING_TYPE:
168 case EXTERNAL_INTERNALIZED_STRING_TYPE:
169 case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
170 case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
171 case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE:
172 case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
173 case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
174 return kInternalizedString;
175 case SYMBOL_TYPE:
176 return kSymbol;
177 case ODDBALL_TYPE: {
178 Heap* heap = map->GetHeap();
179 if (map == heap->undefined_map()) return kUndefined;
180 if (map == heap->null_map()) return kNull;
181 if (map == heap->boolean_map()) return kBoolean;
182 if (map == heap->the_hole_map()) return kHole;
183 DCHECK(map == heap->uninitialized_map() ||
184 map == heap->no_interceptor_result_sentinel_map() ||
185 map == heap->termination_exception_map() ||
186 map == heap->arguments_marker_map() ||
187 map == heap->optimized_out_map() ||
188 map == heap->stale_register_map());
189 return kOtherInternal;
190 }
191 case HEAP_NUMBER_TYPE:
192 return kNumber;
193 case JS_OBJECT_TYPE:
194 case JS_ARGUMENTS_TYPE:
195 case JS_ERROR_TYPE:
196 case JS_GLOBAL_OBJECT_TYPE:
197 case JS_GLOBAL_PROXY_TYPE:
198 case JS_API_OBJECT_TYPE:
199 case JS_SPECIAL_API_OBJECT_TYPE:
200 if (map->is_undetectable()) {
201 // Currently we assume that every undetectable receiver is also
202 // callable, which is what we need to support document.all. We
203 // could add another Type bit to support other use cases in the
204 // future if necessary.
205 DCHECK(map->is_callable());
206 return kOtherUndetectable;
207 }
208 if (map->is_callable()) {
209 return kOtherCallable;
210 }
211 return kOtherObject;
212 case JS_VALUE_TYPE:
213 case JS_MESSAGE_OBJECT_TYPE:
214 case JS_DATE_TYPE:
215 case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
216 case JS_GENERATOR_OBJECT_TYPE:
217 case JS_MODULE_NAMESPACE_TYPE:
218 case JS_ARRAY_BUFFER_TYPE:
219 case JS_ARRAY_TYPE:
220 case JS_REGEXP_TYPE: // TODO(rossberg): there should be a RegExp type.
221 case JS_TYPED_ARRAY_TYPE:
222 case JS_DATA_VIEW_TYPE:
223 case JS_SET_TYPE:
224 case JS_MAP_TYPE:
225 case JS_SET_ITERATOR_TYPE:
226 case JS_MAP_ITERATOR_TYPE:
227 case JS_STRING_ITERATOR_TYPE:
228 case JS_ASYNC_FROM_SYNC_ITERATOR_TYPE:
229
230 case JS_TYPED_ARRAY_KEY_ITERATOR_TYPE:
231 case JS_FAST_ARRAY_KEY_ITERATOR_TYPE:
232 case JS_GENERIC_ARRAY_KEY_ITERATOR_TYPE:
233 case JS_UINT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
234 case JS_INT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
235 case JS_UINT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
236 case JS_INT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
237 case JS_UINT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
238 case JS_INT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
239 case JS_FLOAT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
240 case JS_FLOAT64_ARRAY_KEY_VALUE_ITERATOR_TYPE:
241 case JS_UINT8_CLAMPED_ARRAY_KEY_VALUE_ITERATOR_TYPE:
242 case JS_FAST_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
243 case JS_FAST_HOLEY_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
244 case JS_FAST_ARRAY_KEY_VALUE_ITERATOR_TYPE:
245 case JS_FAST_HOLEY_ARRAY_KEY_VALUE_ITERATOR_TYPE:
246 case JS_FAST_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
247 case JS_FAST_HOLEY_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
248 case JS_GENERIC_ARRAY_KEY_VALUE_ITERATOR_TYPE:
249 case JS_UINT8_ARRAY_VALUE_ITERATOR_TYPE:
250 case JS_INT8_ARRAY_VALUE_ITERATOR_TYPE:
251 case JS_UINT16_ARRAY_VALUE_ITERATOR_TYPE:
252 case JS_INT16_ARRAY_VALUE_ITERATOR_TYPE:
253 case JS_UINT32_ARRAY_VALUE_ITERATOR_TYPE:
254 case JS_INT32_ARRAY_VALUE_ITERATOR_TYPE:
255 case JS_FLOAT32_ARRAY_VALUE_ITERATOR_TYPE:
256 case JS_FLOAT64_ARRAY_VALUE_ITERATOR_TYPE:
257 case JS_UINT8_CLAMPED_ARRAY_VALUE_ITERATOR_TYPE:
258 case JS_FAST_SMI_ARRAY_VALUE_ITERATOR_TYPE:
259 case JS_FAST_HOLEY_SMI_ARRAY_VALUE_ITERATOR_TYPE:
260 case JS_FAST_ARRAY_VALUE_ITERATOR_TYPE:
261 case JS_FAST_HOLEY_ARRAY_VALUE_ITERATOR_TYPE:
262 case JS_FAST_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
263 case JS_FAST_HOLEY_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
264 case JS_GENERIC_ARRAY_VALUE_ITERATOR_TYPE:
265
266 case JS_WEAK_MAP_TYPE:
267 case JS_WEAK_SET_TYPE:
268 case JS_PROMISE_CAPABILITY_TYPE:
269 case JS_PROMISE_TYPE:
270 DCHECK(!map->is_callable());
271 DCHECK(!map->is_undetectable());
272 return kOtherObject;
273 case JS_BOUND_FUNCTION_TYPE:
274 DCHECK(!map->is_undetectable());
275 return kBoundFunction;
276 case JS_FUNCTION_TYPE:
277 DCHECK(!map->is_undetectable());
278 return kFunction;
279 case JS_PROXY_TYPE:
280 DCHECK(!map->is_undetectable());
281 if (map->is_callable()) return kCallableProxy;
282 return kOtherProxy;
283 case MAP_TYPE:
284 case ALLOCATION_SITE_TYPE:
285 case ACCESSOR_INFO_TYPE:
286 case SHARED_FUNCTION_INFO_TYPE:
287 case FUNCTION_TEMPLATE_INFO_TYPE:
288 case ACCESSOR_PAIR_TYPE:
289 case FIXED_ARRAY_TYPE:
290 case FIXED_DOUBLE_ARRAY_TYPE:
291 case BYTE_ARRAY_TYPE:
292 case BYTECODE_ARRAY_TYPE:
293 case TRANSITION_ARRAY_TYPE:
294 case FOREIGN_TYPE:
295 case SCRIPT_TYPE:
296 case CODE_TYPE:
297 case PROPERTY_CELL_TYPE:
298 case MODULE_TYPE:
299 case MODULE_INFO_ENTRY_TYPE:
300 return kOtherInternal;
301
302 // Remaining instance types are unsupported for now. If any of them do
303 // require bit set types, they should get kOtherInternal.
304 case MUTABLE_HEAP_NUMBER_TYPE:
305 case FREE_SPACE_TYPE:
306 #define FIXED_TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
307 case FIXED_##TYPE##_ARRAY_TYPE:
308
309 TYPED_ARRAYS(FIXED_TYPED_ARRAY_CASE)
310 #undef FIXED_TYPED_ARRAY_CASE
311 case FILLER_TYPE:
312 case ACCESS_CHECK_INFO_TYPE:
313 case INTERCEPTOR_INFO_TYPE:
314 case CALL_HANDLER_INFO_TYPE:
315 case OBJECT_TEMPLATE_INFO_TYPE:
316 case ALLOCATION_MEMENTO_TYPE:
317 case TYPE_FEEDBACK_INFO_TYPE:
318 case ALIASED_ARGUMENTS_ENTRY_TYPE:
319 case PROMISE_RESOLVE_THENABLE_JOB_INFO_TYPE:
320 case PROMISE_REACTION_JOB_INFO_TYPE:
321 case DEBUG_INFO_TYPE:
322 case BREAK_POINT_INFO_TYPE:
323 case CELL_TYPE:
324 case WEAK_CELL_TYPE:
325 case PROTOTYPE_INFO_TYPE:
326 case TUPLE2_TYPE:
327 case TUPLE3_TYPE:
328 case CONTEXT_EXTENSION_TYPE:
329 case CONSTANT_ELEMENTS_PAIR_TYPE:
330 UNREACHABLE();
331 return kNone;
332 }
333 UNREACHABLE();
334 return kNone;
335 }
336
Lub(i::Object * value)337 Type::bitset BitsetType::Lub(i::Object* value) {
338 DisallowHeapAllocation no_allocation;
339 if (value->IsNumber()) {
340 return Lub(value->Number());
341 }
342 return Lub(i::HeapObject::cast(value)->map());
343 }
344
Lub(double value)345 Type::bitset BitsetType::Lub(double value) {
346 DisallowHeapAllocation no_allocation;
347 if (i::IsMinusZero(value)) return kMinusZero;
348 if (std::isnan(value)) return kNaN;
349 if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value);
350 return kOtherNumber;
351 }
352
353 // Minimum values of plain numeric bitsets.
354 const BitsetType::Boundary BitsetType::BoundariesArray[] = {
355 {kOtherNumber, kPlainNumber, -V8_INFINITY},
356 {kOtherSigned32, kNegative32, kMinInt},
357 {kNegative31, kNegative31, -0x40000000},
358 {kUnsigned30, kUnsigned30, 0},
359 {kOtherUnsigned31, kUnsigned31, 0x40000000},
360 {kOtherUnsigned32, kUnsigned32, 0x80000000},
361 {kOtherNumber, kPlainNumber, static_cast<double>(kMaxUInt32) + 1}};
362
Boundaries()363 const BitsetType::Boundary* BitsetType::Boundaries() { return BoundariesArray; }
364
BoundariesSize()365 size_t BitsetType::BoundariesSize() {
366 // Windows doesn't like arraysize here.
367 // return arraysize(BoundariesArray);
368 return 7;
369 }
370
ExpandInternals(Type::bitset bits)371 Type::bitset BitsetType::ExpandInternals(Type::bitset bits) {
372 DisallowHeapAllocation no_allocation;
373 if (!(bits & kPlainNumber)) return bits; // Shortcut.
374 const Boundary* boundaries = Boundaries();
375 for (size_t i = 0; i < BoundariesSize(); ++i) {
376 DCHECK(BitsetType::Is(boundaries[i].internal, boundaries[i].external));
377 if (bits & boundaries[i].internal) bits |= boundaries[i].external;
378 }
379 return bits;
380 }
381
Lub(double min,double max)382 Type::bitset BitsetType::Lub(double min, double max) {
383 DisallowHeapAllocation no_allocation;
384 int lub = kNone;
385 const Boundary* mins = Boundaries();
386
387 for (size_t i = 1; i < BoundariesSize(); ++i) {
388 if (min < mins[i].min) {
389 lub |= mins[i - 1].internal;
390 if (max < mins[i].min) return lub;
391 }
392 }
393 return lub | mins[BoundariesSize() - 1].internal;
394 }
395
NumberBits(bitset bits)396 Type::bitset BitsetType::NumberBits(bitset bits) { return bits & kPlainNumber; }
397
Glb(double min,double max)398 Type::bitset BitsetType::Glb(double min, double max) {
399 DisallowHeapAllocation no_allocation;
400 int glb = kNone;
401 const Boundary* mins = Boundaries();
402
403 // If the range does not touch 0, the bound is empty.
404 if (max < -1 || min > 0) return glb;
405
406 for (size_t i = 1; i + 1 < BoundariesSize(); ++i) {
407 if (min <= mins[i].min) {
408 if (max + 1 < mins[i + 1].min) break;
409 glb |= mins[i].external;
410 }
411 }
412 // OtherNumber also contains float numbers, so it can never be
413 // in the greatest lower bound.
414 return glb & ~(kOtherNumber);
415 }
416
Min(bitset bits)417 double BitsetType::Min(bitset bits) {
418 DisallowHeapAllocation no_allocation;
419 DCHECK(Is(bits, kNumber));
420 const Boundary* mins = Boundaries();
421 bool mz = bits & kMinusZero;
422 for (size_t i = 0; i < BoundariesSize(); ++i) {
423 if (Is(mins[i].internal, bits)) {
424 return mz ? std::min(0.0, mins[i].min) : mins[i].min;
425 }
426 }
427 if (mz) return 0;
428 return std::numeric_limits<double>::quiet_NaN();
429 }
430
Max(bitset bits)431 double BitsetType::Max(bitset bits) {
432 DisallowHeapAllocation no_allocation;
433 DCHECK(Is(bits, kNumber));
434 const Boundary* mins = Boundaries();
435 bool mz = bits & kMinusZero;
436 if (BitsetType::Is(mins[BoundariesSize() - 1].internal, bits)) {
437 return +V8_INFINITY;
438 }
439 for (size_t i = BoundariesSize() - 1; i-- > 0;) {
440 if (Is(mins[i].internal, bits)) {
441 return mz ? std::max(0.0, mins[i + 1].min - 1) : mins[i + 1].min - 1;
442 }
443 }
444 if (mz) return 0;
445 return std::numeric_limits<double>::quiet_NaN();
446 }
447
448 // static
IsOtherNumberConstant(double value)449 bool OtherNumberConstantType::IsOtherNumberConstant(double value) {
450 // Not an integer, not NaN, and not -0.
451 return !std::isnan(value) && !Type::IsInteger(value) &&
452 !i::IsMinusZero(value);
453 }
454
455 // static
IsOtherNumberConstant(Object * value)456 bool OtherNumberConstantType::IsOtherNumberConstant(Object* value) {
457 return value->IsHeapNumber() &&
458 IsOtherNumberConstant(HeapNumber::cast(value)->value());
459 }
460
HeapConstantType(BitsetType::bitset bitset,i::Handle<i::HeapObject> object)461 HeapConstantType::HeapConstantType(BitsetType::bitset bitset,
462 i::Handle<i::HeapObject> object)
463 : TypeBase(kHeapConstant), bitset_(bitset), object_(object) {
464 DCHECK(!object->IsHeapNumber());
465 DCHECK_IMPLIES(object->IsString(), object->IsInternalizedString());
466 }
467
468 // -----------------------------------------------------------------------------
469 // Predicates.
470
SimplyEquals(Type * that)471 bool Type::SimplyEquals(Type* that) {
472 DisallowHeapAllocation no_allocation;
473 if (this->IsHeapConstant()) {
474 return that->IsHeapConstant() &&
475 this->AsHeapConstant()->Value().address() ==
476 that->AsHeapConstant()->Value().address();
477 }
478 if (this->IsOtherNumberConstant()) {
479 return that->IsOtherNumberConstant() &&
480 this->AsOtherNumberConstant()->Value() ==
481 that->AsOtherNumberConstant()->Value();
482 }
483 if (this->IsRange()) {
484 if (that->IsHeapConstant() || that->IsOtherNumberConstant()) return false;
485 }
486 if (this->IsTuple()) {
487 if (!that->IsTuple()) return false;
488 TupleType* this_tuple = this->AsTuple();
489 TupleType* that_tuple = that->AsTuple();
490 if (this_tuple->Arity() != that_tuple->Arity()) {
491 return false;
492 }
493 for (int i = 0, n = this_tuple->Arity(); i < n; ++i) {
494 if (!this_tuple->Element(i)->Equals(that_tuple->Element(i))) return false;
495 }
496 return true;
497 }
498 UNREACHABLE();
499 return false;
500 }
501
502 // Check if [this] <= [that].
SlowIs(Type * that)503 bool Type::SlowIs(Type* that) {
504 DisallowHeapAllocation no_allocation;
505
506 // Fast bitset cases
507 if (that->IsBitset()) {
508 return BitsetType::Is(this->BitsetLub(), that->AsBitset());
509 }
510
511 if (this->IsBitset()) {
512 return BitsetType::Is(this->AsBitset(), that->BitsetGlb());
513 }
514
515 // (T1 \/ ... \/ Tn) <= T if (T1 <= T) /\ ... /\ (Tn <= T)
516 if (this->IsUnion()) {
517 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
518 if (!this->AsUnion()->Get(i)->Is(that)) return false;
519 }
520 return true;
521 }
522
523 // T <= (T1 \/ ... \/ Tn) if (T <= T1) \/ ... \/ (T <= Tn)
524 if (that->IsUnion()) {
525 for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
526 if (this->Is(that->AsUnion()->Get(i))) return true;
527 if (i > 1 && this->IsRange()) return false; // Shortcut.
528 }
529 return false;
530 }
531
532 if (that->IsRange()) {
533 return (this->IsRange() && Contains(that->AsRange(), this->AsRange()));
534 }
535 if (this->IsRange()) return false;
536
537 return this->SimplyEquals(that);
538 }
539
540 // Check if [this] and [that] overlap.
Maybe(Type * that)541 bool Type::Maybe(Type* that) {
542 DisallowHeapAllocation no_allocation;
543
544 if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
545 return false;
546
547 // (T1 \/ ... \/ Tn) overlaps T if (T1 overlaps T) \/ ... \/ (Tn overlaps T)
548 if (this->IsUnion()) {
549 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
550 if (this->AsUnion()->Get(i)->Maybe(that)) return true;
551 }
552 return false;
553 }
554
555 // T overlaps (T1 \/ ... \/ Tn) if (T overlaps T1) \/ ... \/ (T overlaps Tn)
556 if (that->IsUnion()) {
557 for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
558 if (this->Maybe(that->AsUnion()->Get(i))) return true;
559 }
560 return false;
561 }
562
563 if (this->IsBitset() && that->IsBitset()) return true;
564
565 if (this->IsRange()) {
566 if (that->IsRange()) {
567 return Overlap(this->AsRange(), that->AsRange());
568 }
569 if (that->IsBitset()) {
570 bitset number_bits = BitsetType::NumberBits(that->AsBitset());
571 if (number_bits == BitsetType::kNone) {
572 return false;
573 }
574 double min = std::max(BitsetType::Min(number_bits), this->Min());
575 double max = std::min(BitsetType::Max(number_bits), this->Max());
576 return min <= max;
577 }
578 }
579 if (that->IsRange()) {
580 return that->Maybe(this); // This case is handled above.
581 }
582
583 if (this->IsBitset() || that->IsBitset()) return true;
584
585 return this->SimplyEquals(that);
586 }
587
588 // Return the range in [this], or [NULL].
GetRange()589 Type* Type::GetRange() {
590 DisallowHeapAllocation no_allocation;
591 if (this->IsRange()) return this;
592 if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) {
593 return this->AsUnion()->Get(1);
594 }
595 return NULL;
596 }
597
Wellformed()598 bool UnionType::Wellformed() {
599 DisallowHeapAllocation no_allocation;
600 // This checks the invariants of the union representation:
601 // 1. There are at least two elements.
602 // 2. The first element is a bitset, no other element is a bitset.
603 // 3. At most one element is a range, and it must be the second one.
604 // 4. No element is itself a union.
605 // 5. No element (except the bitset) is a subtype of any other.
606 // 6. If there is a range, then the bitset type does not contain
607 // plain number bits.
608 DCHECK(this->Length() >= 2); // (1)
609 DCHECK(this->Get(0)->IsBitset()); // (2a)
610
611 for (int i = 0; i < this->Length(); ++i) {
612 if (i != 0) DCHECK(!this->Get(i)->IsBitset()); // (2b)
613 if (i != 1) DCHECK(!this->Get(i)->IsRange()); // (3)
614 DCHECK(!this->Get(i)->IsUnion()); // (4)
615 for (int j = 0; j < this->Length(); ++j) {
616 if (i != j && i != 0) DCHECK(!this->Get(i)->Is(this->Get(j))); // (5)
617 }
618 }
619 DCHECK(!this->Get(1)->IsRange() ||
620 (BitsetType::NumberBits(this->Get(0)->AsBitset()) ==
621 BitsetType::kNone)); // (6)
622 return true;
623 }
624
625 // -----------------------------------------------------------------------------
626 // Union and intersection
627
AddIsSafe(int x,int y)628 static bool AddIsSafe(int x, int y) {
629 return x >= 0 ? y <= std::numeric_limits<int>::max() - x
630 : y >= std::numeric_limits<int>::min() - x;
631 }
632
Intersect(Type * type1,Type * type2,Zone * zone)633 Type* Type::Intersect(Type* type1, Type* type2, Zone* zone) {
634 // Fast case: bit sets.
635 if (type1->IsBitset() && type2->IsBitset()) {
636 return BitsetType::New(type1->AsBitset() & type2->AsBitset());
637 }
638
639 // Fast case: top or bottom types.
640 if (type1->IsNone() || type2->IsAny()) return type1; // Shortcut.
641 if (type2->IsNone() || type1->IsAny()) return type2; // Shortcut.
642
643 // Semi-fast case.
644 if (type1->Is(type2)) return type1;
645 if (type2->Is(type1)) return type2;
646
647 // Slow case: create union.
648
649 // Semantic subtyping check - this is needed for consistency with the
650 // semi-fast case above.
651 if (type1->Is(type2)) {
652 type2 = Any();
653 } else if (type2->Is(type1)) {
654 type1 = Any();
655 }
656
657 bitset bits = type1->BitsetGlb() & type2->BitsetGlb();
658 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
659 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
660 if (!AddIsSafe(size1, size2)) return Any();
661 int size = size1 + size2;
662 if (!AddIsSafe(size, 2)) return Any();
663 size += 2;
664 Type* result_type = UnionType::New(size, zone);
665 UnionType* result = result_type->AsUnion();
666 size = 0;
667
668 // Deal with bitsets.
669 result->Set(size++, BitsetType::New(bits));
670
671 RangeType::Limits lims = RangeType::Limits::Empty();
672 size = IntersectAux(type1, type2, result, size, &lims, zone);
673
674 // If the range is not empty, then insert it into the union and
675 // remove the number bits from the bitset.
676 if (!lims.IsEmpty()) {
677 size = UpdateRange(RangeType::New(lims, zone), result, size, zone);
678
679 // Remove the number bits.
680 bitset number_bits = BitsetType::NumberBits(bits);
681 bits &= ~number_bits;
682 result->Set(0, BitsetType::New(bits));
683 }
684 return NormalizeUnion(result_type, size, zone);
685 }
686
UpdateRange(Type * range,UnionType * result,int size,Zone * zone)687 int Type::UpdateRange(Type* range, UnionType* result, int size, Zone* zone) {
688 if (size == 1) {
689 result->Set(size++, range);
690 } else {
691 // Make space for the range.
692 result->Set(size++, result->Get(1));
693 result->Set(1, range);
694 }
695
696 // Remove any components that just got subsumed.
697 for (int i = 2; i < size;) {
698 if (result->Get(i)->Is(range)) {
699 result->Set(i, result->Get(--size));
700 } else {
701 ++i;
702 }
703 }
704 return size;
705 }
706
ToLimits(bitset bits,Zone * zone)707 RangeType::Limits Type::ToLimits(bitset bits, Zone* zone) {
708 bitset number_bits = BitsetType::NumberBits(bits);
709
710 if (number_bits == BitsetType::kNone) {
711 return RangeType::Limits::Empty();
712 }
713
714 return RangeType::Limits(BitsetType::Min(number_bits),
715 BitsetType::Max(number_bits));
716 }
717
IntersectRangeAndBitset(Type * range,Type * bitset,Zone * zone)718 RangeType::Limits Type::IntersectRangeAndBitset(Type* range, Type* bitset,
719 Zone* zone) {
720 RangeType::Limits range_lims(range->AsRange());
721 RangeType::Limits bitset_lims = ToLimits(bitset->AsBitset(), zone);
722 return RangeType::Limits::Intersect(range_lims, bitset_lims);
723 }
724
IntersectAux(Type * lhs,Type * rhs,UnionType * result,int size,RangeType::Limits * lims,Zone * zone)725 int Type::IntersectAux(Type* lhs, Type* rhs, UnionType* result, int size,
726 RangeType::Limits* lims, Zone* zone) {
727 if (lhs->IsUnion()) {
728 for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) {
729 size =
730 IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, lims, zone);
731 }
732 return size;
733 }
734 if (rhs->IsUnion()) {
735 for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) {
736 size =
737 IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, zone);
738 }
739 return size;
740 }
741
742 if (!BitsetType::IsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
743 return size;
744 }
745
746 if (lhs->IsRange()) {
747 if (rhs->IsBitset()) {
748 RangeType::Limits lim = IntersectRangeAndBitset(lhs, rhs, zone);
749
750 if (!lim.IsEmpty()) {
751 *lims = RangeType::Limits::Union(lim, *lims);
752 }
753 return size;
754 }
755 if (rhs->IsRange()) {
756 RangeType::Limits lim = RangeType::Limits::Intersect(
757 RangeType::Limits(lhs->AsRange()), RangeType::Limits(rhs->AsRange()));
758 if (!lim.IsEmpty()) {
759 *lims = RangeType::Limits::Union(lim, *lims);
760 }
761 }
762 return size;
763 }
764 if (rhs->IsRange()) {
765 // This case is handled symmetrically above.
766 return IntersectAux(rhs, lhs, result, size, lims, zone);
767 }
768 if (lhs->IsBitset() || rhs->IsBitset()) {
769 return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, zone);
770 }
771 if (lhs->SimplyEquals(rhs)) {
772 return AddToUnion(lhs, result, size, zone);
773 }
774 return size;
775 }
776
777 // Make sure that we produce a well-formed range and bitset:
778 // If the range is non-empty, the number bits in the bitset should be
779 // clear. Moreover, if we have a canonical range (such as Signed32),
780 // we want to produce a bitset rather than a range.
NormalizeRangeAndBitset(Type * range,bitset * bits,Zone * zone)781 Type* Type::NormalizeRangeAndBitset(Type* range, bitset* bits, Zone* zone) {
782 // Fast path: If the bitset does not mention numbers, we can just keep the
783 // range.
784 bitset number_bits = BitsetType::NumberBits(*bits);
785 if (number_bits == 0) {
786 return range;
787 }
788
789 // If the range is semantically contained within the bitset, return None and
790 // leave the bitset untouched.
791 bitset range_lub = range->BitsetLub();
792 if (BitsetType::Is(range_lub, *bits)) {
793 return None();
794 }
795
796 // Slow path: reconcile the bitset range and the range.
797 double bitset_min = BitsetType::Min(number_bits);
798 double bitset_max = BitsetType::Max(number_bits);
799
800 double range_min = range->Min();
801 double range_max = range->Max();
802
803 // Remove the number bits from the bitset, they would just confuse us now.
804 // NOTE: bits contains OtherNumber iff bits contains PlainNumber, in which
805 // case we already returned after the subtype check above.
806 *bits &= ~number_bits;
807
808 if (range_min <= bitset_min && range_max >= bitset_max) {
809 // Bitset is contained within the range, just return the range.
810 return range;
811 }
812
813 if (bitset_min < range_min) {
814 range_min = bitset_min;
815 }
816 if (bitset_max > range_max) {
817 range_max = bitset_max;
818 }
819 return RangeType::New(range_min, range_max, zone);
820 }
821
NewConstant(double value,Zone * zone)822 Type* Type::NewConstant(double value, Zone* zone) {
823 if (IsInteger(value)) {
824 return Range(value, value, zone);
825 } else if (i::IsMinusZero(value)) {
826 return Type::MinusZero();
827 } else if (std::isnan(value)) {
828 return Type::NaN();
829 }
830
831 DCHECK(OtherNumberConstantType::IsOtherNumberConstant(value));
832 return OtherNumberConstant(value, zone);
833 }
834
NewConstant(i::Handle<i::Object> value,Zone * zone)835 Type* Type::NewConstant(i::Handle<i::Object> value, Zone* zone) {
836 if (IsInteger(*value)) {
837 double v = value->Number();
838 return Range(v, v, zone);
839 } else if (value->IsHeapNumber()) {
840 return NewConstant(value->Number(), zone);
841 } else if (value->IsString() && !value->IsInternalizedString()) {
842 return Type::OtherString();
843 }
844 return HeapConstant(i::Handle<i::HeapObject>::cast(value), zone);
845 }
846
Union(Type * type1,Type * type2,Zone * zone)847 Type* Type::Union(Type* type1, Type* type2, Zone* zone) {
848 // Fast case: bit sets.
849 if (type1->IsBitset() && type2->IsBitset()) {
850 return BitsetType::New(type1->AsBitset() | type2->AsBitset());
851 }
852
853 // Fast case: top or bottom types.
854 if (type1->IsAny() || type2->IsNone()) return type1;
855 if (type2->IsAny() || type1->IsNone()) return type2;
856
857 // Semi-fast case.
858 if (type1->Is(type2)) return type2;
859 if (type2->Is(type1)) return type1;
860
861 // Slow case: create union.
862 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
863 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
864 if (!AddIsSafe(size1, size2)) return Any();
865 int size = size1 + size2;
866 if (!AddIsSafe(size, 2)) return Any();
867 size += 2;
868 Type* result_type = UnionType::New(size, zone);
869 UnionType* result = result_type->AsUnion();
870 size = 0;
871
872 // Compute the new bitset.
873 bitset new_bitset = type1->BitsetGlb() | type2->BitsetGlb();
874
875 // Deal with ranges.
876 Type* range = None();
877 Type* range1 = type1->GetRange();
878 Type* range2 = type2->GetRange();
879 if (range1 != NULL && range2 != NULL) {
880 RangeType::Limits lims =
881 RangeType::Limits::Union(RangeType::Limits(range1->AsRange()),
882 RangeType::Limits(range2->AsRange()));
883 Type* union_range = RangeType::New(lims, zone);
884 range = NormalizeRangeAndBitset(union_range, &new_bitset, zone);
885 } else if (range1 != NULL) {
886 range = NormalizeRangeAndBitset(range1, &new_bitset, zone);
887 } else if (range2 != NULL) {
888 range = NormalizeRangeAndBitset(range2, &new_bitset, zone);
889 }
890 Type* bits = BitsetType::New(new_bitset);
891 result->Set(size++, bits);
892 if (!range->IsNone()) result->Set(size++, range);
893
894 size = AddToUnion(type1, result, size, zone);
895 size = AddToUnion(type2, result, size, zone);
896 return NormalizeUnion(result_type, size, zone);
897 }
898
899 // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
900 // Return new size of [result].
AddToUnion(Type * type,UnionType * result,int size,Zone * zone)901 int Type::AddToUnion(Type* type, UnionType* result, int size, Zone* zone) {
902 if (type->IsBitset() || type->IsRange()) return size;
903 if (type->IsUnion()) {
904 for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
905 size = AddToUnion(type->AsUnion()->Get(i), result, size, zone);
906 }
907 return size;
908 }
909 for (int i = 0; i < size; ++i) {
910 if (type->Is(result->Get(i))) return size;
911 }
912 result->Set(size++, type);
913 return size;
914 }
915
NormalizeUnion(Type * union_type,int size,Zone * zone)916 Type* Type::NormalizeUnion(Type* union_type, int size, Zone* zone) {
917 UnionType* unioned = union_type->AsUnion();
918 DCHECK(size >= 1);
919 DCHECK(unioned->Get(0)->IsBitset());
920 // If the union has just one element, return it.
921 if (size == 1) {
922 return unioned->Get(0);
923 }
924 bitset bits = unioned->Get(0)->AsBitset();
925 // If the union only consists of a range, we can get rid of the union.
926 if (size == 2 && bits == BitsetType::kNone) {
927 if (unioned->Get(1)->IsRange()) {
928 return RangeType::New(unioned->Get(1)->AsRange()->Min(),
929 unioned->Get(1)->AsRange()->Max(), zone);
930 }
931 }
932 unioned->Shrink(size);
933 SLOW_DCHECK(unioned->Wellformed());
934 return union_type;
935 }
936
NumConstants()937 int Type::NumConstants() {
938 DisallowHeapAllocation no_allocation;
939 if (this->IsHeapConstant() || this->IsOtherNumberConstant()) {
940 return 1;
941 } else if (this->IsUnion()) {
942 int result = 0;
943 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
944 if (this->AsUnion()->Get(i)->IsHeapConstant()) ++result;
945 }
946 return result;
947 } else {
948 return 0;
949 }
950 }
951
952 // -----------------------------------------------------------------------------
953 // Printing.
954
Name(bitset bits)955 const char* BitsetType::Name(bitset bits) {
956 switch (bits) {
957 #define RETURN_NAMED_TYPE(type, value) \
958 case k##type: \
959 return #type;
960 PROPER_BITSET_TYPE_LIST(RETURN_NAMED_TYPE)
961 INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_TYPE)
962 #undef RETURN_NAMED_TYPE
963
964 default:
965 return NULL;
966 }
967 }
968
Print(std::ostream & os,bitset bits)969 void BitsetType::Print(std::ostream& os, // NOLINT
970 bitset bits) {
971 DisallowHeapAllocation no_allocation;
972 const char* name = Name(bits);
973 if (name != NULL) {
974 os << name;
975 return;
976 }
977
978 // clang-format off
979 static const bitset named_bitsets[] = {
980 #define BITSET_CONSTANT(type, value) k##type,
981 INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
982 PROPER_BITSET_TYPE_LIST(BITSET_CONSTANT)
983 #undef BITSET_CONSTANT
984 };
985 // clang-format on
986
987 bool is_first = true;
988 os << "(";
989 for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
990 bitset subset = named_bitsets[i];
991 if ((bits & subset) == subset) {
992 if (!is_first) os << " | ";
993 is_first = false;
994 os << Name(subset);
995 bits -= subset;
996 }
997 }
998 DCHECK(bits == 0);
999 os << ")";
1000 }
1001
PrintTo(std::ostream & os)1002 void Type::PrintTo(std::ostream& os) {
1003 DisallowHeapAllocation no_allocation;
1004 if (this->IsBitset()) {
1005 BitsetType::Print(os, this->AsBitset());
1006 } else if (this->IsHeapConstant()) {
1007 os << "HeapConstant(" << Brief(*this->AsHeapConstant()->Value()) << ")";
1008 } else if (this->IsOtherNumberConstant()) {
1009 os << "OtherNumberConstant(" << this->AsOtherNumberConstant()->Value()
1010 << ")";
1011 } else if (this->IsRange()) {
1012 std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed);
1013 std::streamsize saved_precision = os.precision(0);
1014 os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max()
1015 << ")";
1016 os.flags(saved_flags);
1017 os.precision(saved_precision);
1018 } else if (this->IsUnion()) {
1019 os << "(";
1020 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1021 Type* type_i = this->AsUnion()->Get(i);
1022 if (i > 0) os << " | ";
1023 type_i->PrintTo(os);
1024 }
1025 os << ")";
1026 } else if (this->IsTuple()) {
1027 os << "<";
1028 for (int i = 0, n = this->AsTuple()->Arity(); i < n; ++i) {
1029 Type* type_i = this->AsTuple()->Element(i);
1030 if (i > 0) os << ", ";
1031 type_i->PrintTo(os);
1032 }
1033 os << ">";
1034 } else {
1035 UNREACHABLE();
1036 }
1037 }
1038
1039 #ifdef DEBUG
Print()1040 void Type::Print() {
1041 OFStream os(stdout);
1042 PrintTo(os);
1043 os << std::endl;
1044 }
Print(bitset bits)1045 void BitsetType::Print(bitset bits) {
1046 OFStream os(stdout);
1047 Print(os, bits);
1048 os << std::endl;
1049 }
1050 #endif
1051
SignedSmall()1052 BitsetType::bitset BitsetType::SignedSmall() {
1053 return i::SmiValuesAre31Bits() ? kSigned31 : kSigned32;
1054 }
1055
UnsignedSmall()1056 BitsetType::bitset BitsetType::UnsignedSmall() {
1057 return i::SmiValuesAre31Bits() ? kUnsigned30 : kUnsigned31;
1058 }
1059
1060 } // namespace compiler
1061 } // namespace internal
1062 } // namespace v8
1063