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