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/ast/ast-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 :
16 : // NOTE: If code is marked as being a "shortcut", this means that removing
17 : // the code won't affect the semantics of the surrounding function definition.
18 :
19 : // static
20 3958 : bool AstType::IsInteger(i::Object* x) {
21 5183 : return x->IsNumber() && AstType::IsInteger(x->Number());
22 : }
23 :
24 : // -----------------------------------------------------------------------------
25 : // Range-related helper functions.
26 :
27 563459 : bool AstRangeType::Limits::IsEmpty() { return this->min > this->max; }
28 :
29 0 : AstRangeType::Limits AstRangeType::Limits::Intersect(Limits lhs, Limits rhs) {
30 : DisallowHeapAllocation no_allocation;
31 : Limits result(lhs);
32 0 : if (lhs.min < rhs.min) result.min = rhs.min;
33 0 : if (lhs.max > rhs.max) result.max = rhs.max;
34 0 : return result;
35 : }
36 :
37 0 : AstRangeType::Limits AstRangeType::Limits::Union(Limits lhs, Limits rhs) {
38 : DisallowHeapAllocation no_allocation;
39 27 : if (lhs.IsEmpty()) return rhs;
40 27 : if (rhs.IsEmpty()) return lhs;
41 : Limits result(lhs);
42 27 : if (lhs.min > rhs.min) result.min = rhs.min;
43 27 : if (lhs.max < rhs.max) result.max = rhs.max;
44 0 : return result;
45 : }
46 :
47 0 : bool AstType::Overlap(AstRangeType* lhs, AstRangeType* rhs) {
48 : DisallowHeapAllocation no_allocation;
49 : return !AstRangeType::Limits::Intersect(AstRangeType::Limits(lhs),
50 : AstRangeType::Limits(rhs))
51 0 : .IsEmpty();
52 : }
53 :
54 295185 : bool AstType::Contains(AstRangeType* lhs, AstRangeType* rhs) {
55 : DisallowHeapAllocation no_allocation;
56 295185 : return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
57 : }
58 :
59 2732 : bool AstType::Contains(AstRangeType* lhs, AstConstantType* rhs) {
60 : DisallowHeapAllocation no_allocation;
61 2732 : return IsInteger(*rhs->Value()) && lhs->Min() <= rhs->Value()->Number() &&
62 1823 : rhs->Value()->Number() <= lhs->Max();
63 : }
64 :
65 0 : bool AstType::Contains(AstRangeType* range, i::Object* val) {
66 : DisallowHeapAllocation no_allocation;
67 0 : return IsInteger(val) && range->Min() <= val->Number() &&
68 0 : val->Number() <= range->Max();
69 : }
70 :
71 : // -----------------------------------------------------------------------------
72 : // Min and Max computation.
73 :
74 1034 : double AstType::Min() {
75 : DCHECK(this->SemanticIs(Number()));
76 1255 : if (this->IsBitset()) return AstBitsetType::Min(this->AsBitset());
77 813 : if (this->IsUnion()) {
78 0 : double min = +V8_INFINITY;
79 0 : for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
80 0 : min = std::min(min, this->AsUnion()->Get(i)->Min());
81 : }
82 0 : return min;
83 : }
84 813 : if (this->IsRange()) return this->AsRange()->Min();
85 3 : if (this->IsConstant()) return this->AsConstant()->Value()->Number();
86 0 : UNREACHABLE();
87 : return 0;
88 : }
89 :
90 1034 : double AstType::Max() {
91 : DCHECK(this->SemanticIs(Number()));
92 1255 : if (this->IsBitset()) return AstBitsetType::Max(this->AsBitset());
93 813 : if (this->IsUnion()) {
94 0 : double max = -V8_INFINITY;
95 0 : for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
96 0 : max = std::max(max, this->AsUnion()->Get(i)->Max());
97 : }
98 0 : return max;
99 : }
100 813 : if (this->IsRange()) return this->AsRange()->Max();
101 3 : if (this->IsConstant()) return this->AsConstant()->Value()->Number();
102 0 : UNREACHABLE();
103 : return 0;
104 : }
105 :
106 : // -----------------------------------------------------------------------------
107 : // Glb and lub computation.
108 :
109 : // The largest bitset subsumed by this type.
110 5324540 : AstType::bitset AstBitsetType::Glb(AstType* type) {
111 : DisallowHeapAllocation no_allocation;
112 : // Fast case.
113 5324540 : if (IsBitset(type)) {
114 1121576 : return type->AsBitset();
115 4202964 : } else if (type->IsUnion()) {
116 : SLOW_DCHECK(type->AsUnion()->Wellformed());
117 821710 : return type->AsUnion()->Get(0)->BitsetGlb() |
118 821710 : AST_SEMANTIC(type->AsUnion()->Get(1)->BitsetGlb()); // Shortcut.
119 3792109 : } else if (type->IsRange()) {
120 2716 : bitset glb = AST_SEMANTIC(
121 : AstBitsetType::Glb(type->AsRange()->Min(), type->AsRange()->Max()));
122 2716 : return glb | AST_REPRESENTATION(type->BitsetLub());
123 : } else {
124 3789393 : return type->Representation();
125 : }
126 : }
127 :
128 : // The smallest bitset subsuming this type, possibly not a proper one.
129 40376754 : AstType::bitset AstBitsetType::Lub(AstType* type) {
130 : DisallowHeapAllocation no_allocation;
131 65956646 : if (IsBitset(type)) return type->AsBitset();
132 14796862 : if (type->IsUnion()) {
133 : // Take the representation from the first element, which is always
134 : // a bitset.
135 1128782 : int bitset = type->AsUnion()->Get(0)->BitsetLub();
136 3136706 : for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
137 : // Other elements only contribute their semantic part.
138 5144630 : bitset |= AST_SEMANTIC(type->AsUnion()->Get(i)->BitsetLub());
139 : }
140 564391 : return bitset;
141 : }
142 14232471 : if (type->IsClass()) return type->AsClass()->Lub();
143 11945693 : if (type->IsConstant()) return type->AsConstant()->Lub();
144 3680185 : if (type->IsRange()) return type->AsRange()->Lub();
145 3276105 : if (type->IsContext()) return kOtherInternal & kTaggedPointer;
146 1914807 : if (type->IsArray()) return kOtherObject;
147 1357911 : if (type->IsFunction()) return kFunction;
148 0 : if (type->IsTuple()) return kOtherInternal;
149 0 : UNREACHABLE();
150 : return kNone;
151 : }
152 :
153 1270526 : AstType::bitset AstBitsetType::Lub(i::Map* map) {
154 : DisallowHeapAllocation no_allocation;
155 1270526 : switch (map->instance_type()) {
156 : case STRING_TYPE:
157 : case ONE_BYTE_STRING_TYPE:
158 : case CONS_STRING_TYPE:
159 : case CONS_ONE_BYTE_STRING_TYPE:
160 : case THIN_STRING_TYPE:
161 : case THIN_ONE_BYTE_STRING_TYPE:
162 : case SLICED_STRING_TYPE:
163 : case SLICED_ONE_BYTE_STRING_TYPE:
164 : case EXTERNAL_STRING_TYPE:
165 : case EXTERNAL_ONE_BYTE_STRING_TYPE:
166 : case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
167 : case SHORT_EXTERNAL_STRING_TYPE:
168 : case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE:
169 : case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
170 : return kOtherString;
171 : case INTERNALIZED_STRING_TYPE:
172 : case ONE_BYTE_INTERNALIZED_STRING_TYPE:
173 : case EXTERNAL_INTERNALIZED_STRING_TYPE:
174 : case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
175 : case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
176 : case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE:
177 : case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
178 : case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
179 958060 : return kInternalizedString;
180 : case SYMBOL_TYPE:
181 10 : return kSymbol;
182 : case ODDBALL_TYPE: {
183 757417 : Heap* heap = map->GetHeap();
184 269319 : if (map == heap->undefined_map()) return kUndefined;
185 244903 : if (map == heap->null_map()) return kNull;
186 231360 : if (map == heap->boolean_map()) return kBoolean;
187 11835 : if (map == heap->the_hole_map()) return kHole;
188 : DCHECK(map == heap->uninitialized_map() ||
189 : map == heap->termination_exception_map() ||
190 : map == heap->arguments_marker_map() ||
191 : map == heap->optimized_out_map() ||
192 : map == heap->stale_register_map());
193 11376 : return kOtherInternal & kTaggedPointer;
194 : }
195 : case HEAP_NUMBER_TYPE:
196 27 : return kNumber & kTaggedPointer;
197 : case JS_OBJECT_TYPE:
198 : case JS_ARGUMENTS_TYPE:
199 : case JS_ERROR_TYPE:
200 : case JS_GLOBAL_OBJECT_TYPE:
201 : case JS_GLOBAL_PROXY_TYPE:
202 : case JS_API_OBJECT_TYPE:
203 : case JS_SPECIAL_API_OBJECT_TYPE:
204 22959 : if (map->is_undetectable()) return kOtherUndetectable;
205 22959 : return kOtherObject;
206 : case JS_VALUE_TYPE:
207 : case JS_MESSAGE_OBJECT_TYPE:
208 : case JS_DATE_TYPE:
209 : case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
210 : case JS_GENERATOR_OBJECT_TYPE:
211 : case JS_ASYNC_GENERATOR_OBJECT_TYPE:
212 : case JS_MODULE_NAMESPACE_TYPE:
213 : case JS_ARRAY_BUFFER_TYPE:
214 : case JS_ARRAY_TYPE:
215 : case JS_REGEXP_TYPE: // TODO(rossberg): there should be a RegExp type.
216 : case JS_TYPED_ARRAY_TYPE:
217 : case JS_DATA_VIEW_TYPE:
218 : case JS_SET_TYPE:
219 : case JS_MAP_TYPE:
220 : case JS_SET_ITERATOR_TYPE:
221 : case JS_MAP_ITERATOR_TYPE:
222 : case JS_STRING_ITERATOR_TYPE:
223 : case JS_ASYNC_FROM_SYNC_ITERATOR_TYPE:
224 :
225 : case JS_TYPED_ARRAY_KEY_ITERATOR_TYPE:
226 : case JS_FAST_ARRAY_KEY_ITERATOR_TYPE:
227 : case JS_GENERIC_ARRAY_KEY_ITERATOR_TYPE:
228 : case JS_UINT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
229 : case JS_INT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
230 : case JS_UINT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
231 : case JS_INT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
232 : case JS_UINT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
233 : case JS_INT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
234 : case JS_FLOAT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
235 : case JS_FLOAT64_ARRAY_KEY_VALUE_ITERATOR_TYPE:
236 : case JS_UINT8_CLAMPED_ARRAY_KEY_VALUE_ITERATOR_TYPE:
237 : case JS_FAST_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
238 : case JS_FAST_HOLEY_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
239 : case JS_FAST_ARRAY_KEY_VALUE_ITERATOR_TYPE:
240 : case JS_FAST_HOLEY_ARRAY_KEY_VALUE_ITERATOR_TYPE:
241 : case JS_FAST_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
242 : case JS_FAST_HOLEY_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
243 : case JS_GENERIC_ARRAY_KEY_VALUE_ITERATOR_TYPE:
244 : case JS_UINT8_ARRAY_VALUE_ITERATOR_TYPE:
245 : case JS_INT8_ARRAY_VALUE_ITERATOR_TYPE:
246 : case JS_UINT16_ARRAY_VALUE_ITERATOR_TYPE:
247 : case JS_INT16_ARRAY_VALUE_ITERATOR_TYPE:
248 : case JS_UINT32_ARRAY_VALUE_ITERATOR_TYPE:
249 : case JS_INT32_ARRAY_VALUE_ITERATOR_TYPE:
250 : case JS_FLOAT32_ARRAY_VALUE_ITERATOR_TYPE:
251 : case JS_FLOAT64_ARRAY_VALUE_ITERATOR_TYPE:
252 : case JS_UINT8_CLAMPED_ARRAY_VALUE_ITERATOR_TYPE:
253 : case JS_FAST_SMI_ARRAY_VALUE_ITERATOR_TYPE:
254 : case JS_FAST_HOLEY_SMI_ARRAY_VALUE_ITERATOR_TYPE:
255 : case JS_FAST_ARRAY_VALUE_ITERATOR_TYPE:
256 : case JS_FAST_HOLEY_ARRAY_VALUE_ITERATOR_TYPE:
257 : case JS_FAST_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
258 : case JS_FAST_HOLEY_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
259 : case JS_GENERIC_ARRAY_VALUE_ITERATOR_TYPE:
260 :
261 : case JS_WEAK_MAP_TYPE:
262 : case JS_WEAK_SET_TYPE:
263 : case JS_PROMISE_CAPABILITY_TYPE:
264 : case JS_PROMISE_TYPE:
265 : case JS_BOUND_FUNCTION_TYPE:
266 : DCHECK(!map->is_undetectable());
267 17199 : return kOtherObject;
268 : case JS_FUNCTION_TYPE:
269 : DCHECK(!map->is_undetectable());
270 2747 : return kFunction;
271 : case JS_PROXY_TYPE:
272 : DCHECK(!map->is_undetectable());
273 0 : return kProxy;
274 : case MAP_TYPE:
275 : case ALLOCATION_SITE_TYPE:
276 : case ACCESSOR_INFO_TYPE:
277 : case SHARED_FUNCTION_INFO_TYPE:
278 : case ACCESSOR_PAIR_TYPE:
279 : case FIXED_ARRAY_TYPE:
280 : case FIXED_DOUBLE_ARRAY_TYPE:
281 : case BYTE_ARRAY_TYPE:
282 : case BYTECODE_ARRAY_TYPE:
283 : case TRANSITION_ARRAY_TYPE:
284 : case FOREIGN_TYPE:
285 : case SCRIPT_TYPE:
286 : case CODE_TYPE:
287 : case PROPERTY_CELL_TYPE:
288 : case MODULE_TYPE:
289 : case MODULE_INFO_ENTRY_TYPE:
290 : case ASYNC_GENERATOR_REQUEST_TYPE:
291 0 : return kOtherInternal & kTaggedPointer;
292 :
293 : // Remaining instance types are unsupported for now. If any of them do
294 : // require bit set types, they should get kOtherInternal & kTaggedPointer.
295 : case MUTABLE_HEAP_NUMBER_TYPE:
296 : case FREE_SPACE_TYPE:
297 : #define FIXED_TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
298 : case FIXED_##TYPE##_ARRAY_TYPE:
299 :
300 : TYPED_ARRAYS(FIXED_TYPED_ARRAY_CASE)
301 : #undef FIXED_TYPED_ARRAY_CASE
302 : case FILLER_TYPE:
303 : case ACCESS_CHECK_INFO_TYPE:
304 : case INTERCEPTOR_INFO_TYPE:
305 : case PROMISE_RESOLVE_THENABLE_JOB_INFO_TYPE:
306 : case PROMISE_REACTION_JOB_INFO_TYPE:
307 : case FUNCTION_TEMPLATE_INFO_TYPE:
308 : case OBJECT_TEMPLATE_INFO_TYPE:
309 : case ALLOCATION_MEMENTO_TYPE:
310 : case ALIASED_ARGUMENTS_ENTRY_TYPE:
311 : case DEBUG_INFO_TYPE:
312 : case STACK_FRAME_INFO_TYPE:
313 : case CELL_TYPE:
314 : case WEAK_CELL_TYPE:
315 : case PROTOTYPE_INFO_TYPE:
316 : case TUPLE2_TYPE:
317 : case TUPLE3_TYPE:
318 : case CONTEXT_EXTENSION_TYPE:
319 : case PADDING_TYPE_1:
320 : case PADDING_TYPE_2:
321 : case PADDING_TYPE_3:
322 : case PADDING_TYPE_4:
323 0 : UNREACHABLE();
324 : return kNone;
325 : }
326 0 : UNREACHABLE();
327 : return kNone;
328 : }
329 :
330 2812200 : AstType::bitset AstBitsetType::Lub(i::Object* value) {
331 : DisallowHeapAllocation no_allocation;
332 2812200 : if (value->IsNumber()) {
333 1580028 : return Lub(value->Number()) &
334 1580028 : (value->IsSmi() ? kTaggedSigned : kTaggedPointer);
335 : }
336 1232172 : return Lub(i::HeapObject::cast(value)->map());
337 : }
338 :
339 1580028 : AstType::bitset AstBitsetType::Lub(double value) {
340 : DisallowHeapAllocation no_allocation;
341 1580028 : if (i::IsMinusZero(value)) return kMinusZero;
342 1572070 : if (std::isnan(value)) return kNaN;
343 3177021 : if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value);
344 : return kOtherNumber;
345 : }
346 :
347 : // Minimum values of plain numeric bitsets.
348 : const AstBitsetType::Boundary AstBitsetType::BoundariesArray[] = {
349 : {kOtherNumber, kPlainNumber, -V8_INFINITY},
350 : {kOtherSigned32, kNegative32, kMinInt},
351 : {kNegative31, kNegative31, -0x40000000},
352 : {kUnsigned30, kUnsigned30, 0},
353 : {kOtherUnsigned31, kUnsigned31, 0x40000000},
354 : {kOtherUnsigned32, kUnsigned32, 0x80000000},
355 : {kOtherNumber, kPlainNumber, static_cast<double>(kMaxUInt32) + 1}};
356 :
357 : const AstBitsetType::Boundary* AstBitsetType::Boundaries() {
358 : return BoundariesArray;
359 : }
360 :
361 : size_t AstBitsetType::BoundariesSize() {
362 : // Windows doesn't like arraysize here.
363 : // return arraysize(BoundariesArray);
364 : return 7;
365 : }
366 :
367 7356 : AstType::bitset AstBitsetType::ExpandInternals(AstType::bitset bits) {
368 : DisallowHeapAllocation no_allocation;
369 7356 : if (!(bits & AST_SEMANTIC(kPlainNumber))) return bits; // Shortcut.
370 : const Boundary* boundaries = Boundaries();
371 42140 : for (size_t i = 0; i < BoundariesSize(); ++i) {
372 : DCHECK(AstBitsetType::Is(boundaries[i].internal, boundaries[i].external));
373 42140 : if (bits & AST_SEMANTIC(boundaries[i].internal))
374 6403 : bits |= AST_SEMANTIC(boundaries[i].external);
375 : }
376 : return bits;
377 : }
378 :
379 362165 : AstType::bitset AstBitsetType::Lub(double min, double max) {
380 : DisallowHeapAllocation no_allocation;
381 : int lub = kNone;
382 : const Boundary* mins = Boundaries();
383 :
384 4960782 : for (size_t i = 1; i < BoundariesSize(); ++i) {
385 5987852 : if (min < mins[i].min) {
386 2214630 : lub |= mins[i - 1].internal;
387 2214630 : if (max < mins[i].min) return lub;
388 : }
389 : }
390 108568 : return lub | mins[BoundariesSize() - 1].internal;
391 : }
392 :
393 0 : AstType::bitset AstBitsetType::NumberBits(bitset bits) {
394 1323 : return AST_SEMANTIC(bits & kPlainNumber);
395 : }
396 :
397 2716 : AstType::bitset AstBitsetType::Glb(double min, double max) {
398 : DisallowHeapAllocation no_allocation;
399 : int glb = kNone;
400 : const Boundary* mins = Boundaries();
401 :
402 : // If the range does not touch 0, the bound is empty.
403 2716 : if (max < -1 || min > 0) return glb;
404 :
405 8454 : for (size_t i = 1; i + 1 < BoundariesSize(); ++i) {
406 7661 : if (min <= mins[i].min) {
407 7491 : if (max + 1 < mins[i + 1].min) break;
408 6459 : glb |= mins[i].external;
409 : }
410 : }
411 : // OtherNumber also contains float numbers, so it can never be
412 : // in the greatest lower bound.
413 1825 : return glb & ~(AST_SEMANTIC(kOtherNumber));
414 : }
415 :
416 1031 : double AstBitsetType::Min(bitset bits) {
417 : DisallowHeapAllocation no_allocation;
418 : DCHECK(Is(AST_SEMANTIC(bits), kNumber));
419 : const Boundary* mins = Boundaries();
420 1031 : bool mz = AST_SEMANTIC(bits & kMinusZero);
421 2268 : for (size_t i = 0; i < BoundariesSize(); ++i) {
422 4502 : if (Is(AST_SEMANTIC(mins[i].internal), bits)) {
423 1095 : return mz ? std::min(0.0, mins[i].min) : mins[i].min;
424 : }
425 : }
426 17 : if (mz) return 0;
427 0 : return std::numeric_limits<double>::quiet_NaN();
428 : }
429 :
430 1031 : double AstBitsetType::Max(bitset bits) {
431 : DisallowHeapAllocation no_allocation;
432 : DCHECK(Is(AST_SEMANTIC(bits), kNumber));
433 : const Boundary* mins = Boundaries();
434 1031 : bool mz = AST_SEMANTIC(bits & kMinusZero);
435 1031 : if (AstBitsetType::Is(AST_SEMANTIC(mins[BoundariesSize() - 1].internal),
436 : bits)) {
437 : return +V8_INFINITY;
438 : }
439 2111 : for (size_t i = BoundariesSize() - 1; i-- > 0;) {
440 4188 : if (Is(AST_SEMANTIC(mins[i].internal), bits)) {
441 1012 : return mz ? std::max(0.0, mins[i + 1].min - 1) : mins[i + 1].min - 1;
442 : }
443 : }
444 17 : if (mz) return 0;
445 0 : return std::numeric_limits<double>::quiet_NaN();
446 : }
447 :
448 : // -----------------------------------------------------------------------------
449 : // Predicates.
450 :
451 942189 : bool AstType::SimplyEquals(AstType* that) {
452 : DisallowHeapAllocation no_allocation;
453 942189 : if (this->IsClass()) {
454 285227 : return that->IsClass() &&
455 214697 : *this->AsClass()->Map() == *that->AsClass()->Map();
456 : }
457 727492 : if (this->IsConstant()) {
458 423402 : return that->IsConstant() &&
459 314090 : *this->AsConstant()->Value() == *that->AsConstant()->Value();
460 : }
461 413402 : if (this->IsContext()) {
462 182459 : return that->IsContext() &&
463 182459 : this->AsContext()->Outer()->Equals(that->AsContext()->Outer());
464 : }
465 264780 : if (this->IsArray()) {
466 111625 : return that->IsArray() &&
467 111625 : this->AsArray()->Element()->Equals(that->AsArray()->Element());
468 : }
469 179896 : if (this->IsFunction()) {
470 179896 : if (!that->IsFunction()) return false;
471 : AstFunctionType* this_fun = this->AsFunction();
472 : AstFunctionType* that_fun = that->AsFunction();
473 125603 : if (this_fun->Arity() != that_fun->Arity() ||
474 158595 : !this_fun->Result()->Equals(that_fun->Result()) ||
475 32992 : !this_fun->Receiver()->Equals(that_fun->Receiver())) {
476 : return false;
477 : }
478 34132 : for (int i = 0, n = this_fun->Arity(); i < n; ++i) {
479 32810 : if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false;
480 : }
481 : return true;
482 : }
483 0 : if (this->IsTuple()) {
484 0 : if (!that->IsTuple()) return false;
485 : AstTupleType* this_tuple = this->AsTuple();
486 : AstTupleType* that_tuple = that->AsTuple();
487 0 : if (this_tuple->Arity() != that_tuple->Arity()) {
488 : return false;
489 : }
490 0 : for (int i = 0, n = this_tuple->Arity(); i < n; ++i) {
491 0 : if (!this_tuple->Element(i)->Equals(that_tuple->Element(i))) return false;
492 : }
493 : return true;
494 : }
495 0 : UNREACHABLE();
496 : return false;
497 : }
498 :
499 0 : AstType::bitset AstType::Representation() {
500 6878904 : return AST_REPRESENTATION(this->BitsetLub());
501 : }
502 :
503 : // Check if [this] <= [that].
504 27255997 : bool AstType::SlowIs(AstType* that) {
505 : DisallowHeapAllocation no_allocation;
506 :
507 : // Fast bitset cases
508 27255997 : if (that->IsBitset()) {
509 24130811 : return AstBitsetType::Is(this->BitsetLub(), that->AsBitset());
510 : }
511 :
512 3125186 : if (this->IsBitset()) {
513 2413535 : return AstBitsetType::Is(this->AsBitset(), that->BitsetGlb());
514 : }
515 :
516 : // Check the representations.
517 711651 : if (!AstBitsetType::Is(Representation(), that->Representation())) {
518 : return false;
519 : }
520 :
521 : // Check the semantic part.
522 605693 : return SemanticIs(that);
523 : }
524 :
525 : // Check if AST_SEMANTIC([this]) <= AST_SEMANTIC([that]). The result of the
526 : // method
527 : // should be independent of the representation axis of the types.
528 2942708 : bool AstType::SemanticIs(AstType* that) {
529 : DisallowHeapAllocation no_allocation;
530 :
531 2942708 : if (this == that) return true;
532 :
533 2918605 : if (that->IsBitset()) {
534 2201218 : return AstBitsetType::Is(AST_SEMANTIC(this->BitsetLub()), that->AsBitset());
535 : }
536 1817996 : if (this->IsBitset()) {
537 1055386 : return AstBitsetType::Is(AST_SEMANTIC(this->AsBitset()), that->BitsetGlb());
538 : }
539 :
540 : // (T1 \/ ... \/ Tn) <= T if (T1 <= T) /\ ... /\ (Tn <= T)
541 1290303 : if (this->IsUnion()) {
542 113147 : for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
543 200992 : if (!this->AsUnion()->Get(i)->SemanticIs(that)) return false;
544 : }
545 : return true;
546 : }
547 :
548 : // T <= (T1 \/ ... \/ Tn) if (T <= T1) \/ ... \/ (T <= Tn)
549 1241278 : if (that->IsUnion()) {
550 396650 : for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
551 705672 : if (this->SemanticIs(that->AsUnion()->Get(i))) return true;
552 427900 : if (i > 1 && this->IsRange()) return false; // Shortcut.
553 : }
554 : return false;
555 : }
556 :
557 1134169 : if (that->IsRange()) {
558 567830 : return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) ||
559 1823 : (this->IsConstant() &&
560 204636 : Contains(that->AsRange(), this->AsConstant()));
561 : }
562 931356 : if (this->IsRange()) return false;
563 :
564 931113 : return this->SimplyEquals(that);
565 : }
566 :
567 : // Most precise _current_ type of a value (usually its class).
568 12835 : AstType* AstType::NowOf(i::Object* value, Zone* zone) {
569 20692 : if (value->IsSmi() ||
570 : i::HeapObject::cast(value)->map()->instance_type() == HEAP_NUMBER_TYPE) {
571 5418 : return Of(value, zone);
572 : }
573 7417 : return Class(i::handle(i::HeapObject::cast(value)->map()), zone);
574 : }
575 :
576 973 : bool AstType::NowContains(i::Object* value) {
577 : DisallowHeapAllocation no_allocation;
578 973 : if (this->IsAny()) return true;
579 901 : if (value->IsHeapObject()) {
580 : i::Map* map = i::HeapObject::cast(value)->map();
581 1552 : for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) {
582 120 : if (*it.Current() == map) return true;
583 : }
584 : }
585 889 : return this->Contains(value);
586 : }
587 :
588 1588203 : bool AstType::NowIs(AstType* that) {
589 : DisallowHeapAllocation no_allocation;
590 :
591 : // TODO(rossberg): this is incorrect for
592 : // Union(Constant(V), T)->NowIs(Class(M))
593 : // but fuzzing does not cover that!
594 1588203 : if (this->IsConstant()) {
595 : i::Object* object = *this->AsConstant()->Value();
596 105204 : if (object->IsHeapObject()) {
597 : i::Map* map = i::HeapObject::cast(object)->map();
598 164924 : for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) {
599 11260 : if (*it.Current() == map) return true;
600 : }
601 : }
602 : }
603 1586729 : return this->Is(that);
604 : }
605 :
606 : // Check if [this] contains only (currently) stable classes.
607 0 : bool AstType::NowStable() {
608 : DisallowHeapAllocation no_allocation;
609 0 : return !this->IsClass() || this->AsClass()->Map()->is_stable();
610 : }
611 :
612 : // Check if [this] and [that] overlap.
613 721190 : bool AstType::Maybe(AstType* that) {
614 : DisallowHeapAllocation no_allocation;
615 :
616 : // Take care of the representation part (and also approximate
617 : // the semantic part).
618 1442380 : if (!AstBitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
619 : return false;
620 :
621 68318 : return SemanticMaybe(that);
622 : }
623 :
624 71205 : bool AstType::SemanticMaybe(AstType* that) {
625 : DisallowHeapAllocation no_allocation;
626 :
627 : // (T1 \/ ... \/ Tn) overlaps T if (T1 overlaps T) \/ ... \/ (Tn overlaps T)
628 71205 : if (this->IsUnion()) {
629 1427 : for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
630 2830 : if (this->AsUnion()->Get(i)->SemanticMaybe(that)) return true;
631 : }
632 : return false;
633 : }
634 :
635 : // T overlaps (T1 \/ ... \/ Tn) if (T overlaps T1) \/ ... \/ (T overlaps Tn)
636 70239 : if (that->IsUnion()) {
637 1502 : for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
638 2944 : if (this->SemanticMaybe(that->AsUnion()->Get(i))) return true;
639 : }
640 : return false;
641 : }
642 :
643 69246 : if (!AstBitsetType::SemanticIsInhabited(this->BitsetLub() &
644 69246 : that->BitsetLub()))
645 : return false;
646 :
647 68353 : if (this->IsBitset() && that->IsBitset()) return true;
648 :
649 15930 : if (this->IsClass() != that->IsClass()) return true;
650 :
651 14995 : if (this->IsRange()) {
652 0 : if (that->IsConstant()) {
653 0 : return Contains(this->AsRange(), that->AsConstant());
654 : }
655 0 : if (that->IsRange()) {
656 0 : return Overlap(this->AsRange(), that->AsRange());
657 : }
658 0 : if (that->IsBitset()) {
659 : bitset number_bits = AstBitsetType::NumberBits(that->AsBitset());
660 0 : if (number_bits == AstBitsetType::kNone) {
661 : return false;
662 : }
663 0 : double min = std::max(AstBitsetType::Min(number_bits), this->Min());
664 0 : double max = std::min(AstBitsetType::Max(number_bits), this->Max());
665 0 : return min <= max;
666 : }
667 : }
668 14995 : if (that->IsRange()) {
669 : return that->SemanticMaybe(this); // This case is handled above.
670 : }
671 :
672 14995 : if (this->IsBitset() || that->IsBitset()) return true;
673 :
674 457 : return this->SimplyEquals(that);
675 : }
676 :
677 : // Return the range in [this], or [NULL].
678 400987 : AstType* AstType::GetRange() {
679 : DisallowHeapAllocation no_allocation;
680 400987 : if (this->IsRange()) return this;
681 449855 : if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) {
682 1674 : return this->AsUnion()->Get(1);
683 : }
684 : return NULL;
685 : }
686 :
687 2173 : bool AstType::Contains(i::Object* value) {
688 : DisallowHeapAllocation no_allocation;
689 4700 : for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
690 430 : if (*it.Current() == value) return true;
691 : }
692 2135 : if (IsInteger(value)) {
693 757 : AstType* range = this->GetRange();
694 757 : if (range != NULL && Contains(range->AsRange(), value)) return true;
695 : }
696 4270 : return AstBitsetType::New(AstBitsetType::Lub(value))->Is(this);
697 : }
698 :
699 0 : bool AstUnionType::Wellformed() {
700 : DisallowHeapAllocation no_allocation;
701 : // This checks the invariants of the union representation:
702 : // 1. There are at least two elements.
703 : // 2. The first element is a bitset, no other element is a bitset.
704 : // 3. At most one element is a range, and it must be the second one.
705 : // 4. No element is itself a union.
706 : // 5. No element (except the bitset) is a subtype of any other.
707 : // 6. If there is a range, then the bitset type does not contain
708 : // plain number bits.
709 : DCHECK(this->Length() >= 2); // (1)
710 : DCHECK(this->Get(0)->IsBitset()); // (2a)
711 :
712 : for (int i = 0; i < this->Length(); ++i) {
713 : if (i != 0) DCHECK(!this->Get(i)->IsBitset()); // (2b)
714 : if (i != 1) DCHECK(!this->Get(i)->IsRange()); // (3)
715 : DCHECK(!this->Get(i)->IsUnion()); // (4)
716 : for (int j = 0; j < this->Length(); ++j) {
717 : if (i != j && i != 0)
718 : DCHECK(!this->Get(i)->SemanticIs(this->Get(j))); // (5)
719 : }
720 : }
721 : DCHECK(!this->Get(1)->IsRange() ||
722 : (AstBitsetType::NumberBits(this->Get(0)->AsBitset()) ==
723 : AstBitsetType::kNone)); // (6)
724 0 : return true;
725 : }
726 :
727 : // -----------------------------------------------------------------------------
728 : // Union and intersection
729 :
730 : static bool AddIsSafe(int x, int y) {
731 1527148 : return x >= 0 ? y <= std::numeric_limits<int>::max() - x
732 3054296 : : y >= std::numeric_limits<int>::min() - x;
733 : }
734 :
735 10529848 : AstType* AstType::Intersect(AstType* type1, AstType* type2, Zone* zone) {
736 : // Fast case: bit sets.
737 20291935 : if (type1->IsBitset() && type2->IsBitset()) {
738 13084992 : return AstBitsetType::New(type1->AsBitset() & type2->AsBitset());
739 : }
740 :
741 : // Fast case: top or bottom types.
742 3987352 : if (type1->IsNone() || type2->IsAny()) return type1; // Shortcut.
743 3955902 : if (type2->IsNone() || type1->IsAny()) return type2; // Shortcut.
744 :
745 : // Semi-fast case.
746 917869 : if (type1->Is(type2)) return type1;
747 616235 : if (type2->Is(type1)) return type2;
748 :
749 : // Slow case: create union.
750 :
751 : // Figure out the representation of the result first.
752 : // The rest of the method should not change this representation and
753 : // it should not make any decisions based on representations (i.e.,
754 : // it should only use the semantic part of types).
755 : const bitset representation =
756 563459 : type1->Representation() & type2->Representation();
757 :
758 : // Semantic subtyping check - this is needed for consistency with the
759 : // semi-fast case above - we should behave the same way regardless of
760 : // representations. Intersection with a universal bitset should only update
761 : // the representations.
762 563459 : if (type1->SemanticIs(type2)) {
763 : type2 = Any();
764 518881 : } else if (type2->SemanticIs(type1)) {
765 : type1 = Any();
766 : }
767 :
768 : bitset bits =
769 563459 : AST_SEMANTIC(type1->BitsetGlb() & type2->BitsetGlb()) | representation;
770 563459 : int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
771 563459 : int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
772 563459 : if (!AddIsSafe(size1, size2)) return Any();
773 563459 : int size = size1 + size2;
774 563459 : if (!AddIsSafe(size, 2)) return Any();
775 563459 : size += 2;
776 563459 : AstType* result_type = AstUnionType::New(size, zone);
777 : AstUnionType* result = result_type->AsUnion();
778 : size = 0;
779 :
780 : // Deal with bitsets.
781 563459 : result->Set(size++, AstBitsetType::New(bits));
782 :
783 563459 : AstRangeType::Limits lims = AstRangeType::Limits::Empty();
784 563459 : size = IntersectAux(type1, type2, result, size, &lims, zone);
785 :
786 : // If the range is not empty, then insert it into the union and
787 : // remove the number bits from the bitset.
788 563459 : if (!lims.IsEmpty()) {
789 : size = UpdateRange(AstRangeType::New(lims, representation, zone), result,
790 0 : size, zone);
791 :
792 : // Remove the number bits.
793 : bitset number_bits = AstBitsetType::NumberBits(bits);
794 0 : bits &= ~number_bits;
795 : result->Set(0, AstBitsetType::New(bits));
796 : }
797 563459 : return NormalizeUnion(result_type, size, zone);
798 : }
799 :
800 0 : int AstType::UpdateRange(AstType* range, AstUnionType* result, int size,
801 : Zone* zone) {
802 0 : if (size == 1) {
803 0 : result->Set(size++, range);
804 : } else {
805 : // Make space for the range.
806 0 : result->Set(size++, result->Get(1));
807 : result->Set(1, range);
808 : }
809 :
810 : // Remove any components that just got subsumed.
811 0 : for (int i = 2; i < size;) {
812 0 : if (result->Get(i)->SemanticIs(range)) {
813 0 : result->Set(i, result->Get(--size));
814 : } else {
815 0 : ++i;
816 : }
817 : }
818 0 : return size;
819 : }
820 :
821 0 : AstRangeType::Limits AstType::ToLimits(bitset bits, Zone* zone) {
822 : bitset number_bits = AstBitsetType::NumberBits(bits);
823 :
824 0 : if (number_bits == AstBitsetType::kNone) {
825 : return AstRangeType::Limits::Empty();
826 : }
827 :
828 : return AstRangeType::Limits(AstBitsetType::Min(number_bits),
829 0 : AstBitsetType::Max(number_bits));
830 : }
831 :
832 0 : AstRangeType::Limits AstType::IntersectRangeAndBitset(AstType* range,
833 : AstType* bitset,
834 : Zone* zone) {
835 : AstRangeType::Limits range_lims(range->AsRange());
836 0 : AstRangeType::Limits bitset_lims = ToLimits(bitset->AsBitset(), zone);
837 0 : return AstRangeType::Limits::Intersect(range_lims, bitset_lims);
838 : }
839 :
840 780222 : int AstType::IntersectAux(AstType* lhs, AstType* rhs, AstUnionType* result,
841 : int size, AstRangeType::Limits* lims, Zone* zone) {
842 780222 : if (lhs->IsUnion()) {
843 128400 : for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) {
844 : size =
845 212682 : IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, lims, zone);
846 : }
847 : return size;
848 : }
849 758163 : if (rhs->IsUnion()) {
850 133489 : for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) {
851 : size =
852 220844 : IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, zone);
853 : }
854 : return size;
855 : }
856 :
857 735096 : if (!AstBitsetType::SemanticIsInhabited(lhs->BitsetLub() &
858 735096 : rhs->BitsetLub())) {
859 : return size;
860 : }
861 :
862 152390 : if (lhs->IsRange()) {
863 0 : if (rhs->IsBitset()) {
864 0 : AstRangeType::Limits lim = IntersectRangeAndBitset(lhs, rhs, zone);
865 :
866 0 : if (!lim.IsEmpty()) {
867 0 : *lims = AstRangeType::Limits::Union(lim, *lims);
868 : }
869 : return size;
870 : }
871 0 : if (rhs->IsClass()) {
872 : *lims = AstRangeType::Limits::Union(AstRangeType::Limits(lhs->AsRange()),
873 0 : *lims);
874 : }
875 0 : if (rhs->IsConstant() && Contains(lhs->AsRange(), rhs->AsConstant())) {
876 0 : return AddToUnion(rhs, result, size, zone);
877 : }
878 0 : if (rhs->IsRange()) {
879 : AstRangeType::Limits lim =
880 : AstRangeType::Limits::Intersect(AstRangeType::Limits(lhs->AsRange()),
881 : AstRangeType::Limits(rhs->AsRange()));
882 0 : if (!lim.IsEmpty()) {
883 0 : *lims = AstRangeType::Limits::Union(lim, *lims);
884 : }
885 : }
886 0 : return size;
887 : }
888 152390 : if (rhs->IsRange()) {
889 : // This case is handled symmetrically above.
890 : return IntersectAux(rhs, lhs, result, size, lims, zone);
891 : }
892 152390 : if (lhs->IsBitset() || rhs->IsBitset()) {
893 133556 : return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, zone);
894 : }
895 18834 : if (lhs->IsClass() != rhs->IsClass()) {
896 8215 : return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, zone);
897 : }
898 10619 : if (lhs->SimplyEquals(rhs)) {
899 461 : return AddToUnion(lhs, result, size, zone);
900 : }
901 : return size;
902 : }
903 :
904 : // Make sure that we produce a well-formed range and bitset:
905 : // If the range is non-empty, the number bits in the bitset should be
906 : // clear. Moreover, if we have a canonical range (such as Signed32),
907 : // we want to produce a bitset rather than a range.
908 1323 : AstType* AstType::NormalizeRangeAndBitset(AstType* range, bitset* bits,
909 : Zone* zone) {
910 : // Fast path: If the bitset does not mention numbers, we can just keep the
911 : // range.
912 1323 : bitset number_bits = AstBitsetType::NumberBits(*bits);
913 1323 : if (number_bits == 0) {
914 : return range;
915 : }
916 :
917 : // If the range is semantically contained within the bitset, return None and
918 : // leave the bitset untouched.
919 1053 : bitset range_lub = AST_SEMANTIC(range->BitsetLub());
920 2106 : if (AstBitsetType::Is(range_lub, *bits)) {
921 : return None();
922 : }
923 :
924 : // Slow path: reconcile the bitset range and the range.
925 810 : double bitset_min = AstBitsetType::Min(number_bits);
926 810 : double bitset_max = AstBitsetType::Max(number_bits);
927 :
928 810 : double range_min = range->Min();
929 810 : double range_max = range->Max();
930 :
931 : // Remove the number bits from the bitset, they would just confuse us now.
932 : // NOTE: bits contains OtherNumber iff bits contains PlainNumber, in which
933 : // case we already returned after the subtype check above.
934 810 : *bits &= ~number_bits;
935 :
936 810 : if (range_min <= bitset_min && range_max >= bitset_max) {
937 : // Bitset is contained within the range, just return the range.
938 : return range;
939 : }
940 :
941 108 : if (bitset_min < range_min) {
942 : range_min = bitset_min;
943 : }
944 108 : if (bitset_max > range_max) {
945 : range_max = bitset_max;
946 : }
947 108 : return AstRangeType::New(range_min, range_max, AstBitsetType::kNone, zone);
948 : }
949 :
950 14289466 : AstType* AstType::Union(AstType* type1, AstType* type2, Zone* zone) {
951 : // Fast case: bit sets.
952 28424699 : if (type1->IsBitset() && type2->IsBitset()) {
953 21764648 : return AstBitsetType::New(type1->AsBitset() | type2->AsBitset());
954 : }
955 :
956 : // Fast case: top or bottom types.
957 3407142 : if (type1->IsAny() || type2->IsNone()) return type1;
958 3374561 : if (type2->IsAny() || type1->IsNone()) return type2;
959 :
960 : // Semi-fast case.
961 628114 : if (type1->Is(type2)) return type2;
962 558578 : if (type2->Is(type1)) return type1;
963 :
964 : // Figure out the representation of the result.
965 : // The rest of the method should not change this representation and
966 : // it should not make any decisions based on representations (i.e.,
967 : // it should only use the semantic part of types).
968 : const bitset representation =
969 200115 : type1->Representation() | type2->Representation();
970 :
971 : // Slow case: create union.
972 200115 : int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
973 200115 : int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
974 200115 : if (!AddIsSafe(size1, size2)) return Any();
975 200115 : int size = size1 + size2;
976 200115 : if (!AddIsSafe(size, 2)) return Any();
977 200115 : size += 2;
978 200115 : AstType* result_type = AstUnionType::New(size, zone);
979 : AstUnionType* result = result_type->AsUnion();
980 : size = 0;
981 :
982 : // Compute the new bitset.
983 200115 : bitset new_bitset = AST_SEMANTIC(type1->BitsetGlb() | type2->BitsetGlb());
984 :
985 : // Deal with ranges.
986 : AstType* range = None();
987 200115 : AstType* range1 = type1->GetRange();
988 200115 : AstType* range2 = type2->GetRange();
989 200115 : if (range1 != NULL && range2 != NULL) {
990 : AstRangeType::Limits lims =
991 : AstRangeType::Limits::Union(AstRangeType::Limits(range1->AsRange()),
992 27 : AstRangeType::Limits(range2->AsRange()));
993 27 : AstType* union_range = AstRangeType::New(lims, representation, zone);
994 27 : range = NormalizeRangeAndBitset(union_range, &new_bitset, zone);
995 200088 : } else if (range1 != NULL) {
996 891 : range = NormalizeRangeAndBitset(range1, &new_bitset, zone);
997 199197 : } else if (range2 != NULL) {
998 405 : range = NormalizeRangeAndBitset(range2, &new_bitset, zone);
999 : }
1000 200115 : new_bitset = AST_SEMANTIC(new_bitset) | representation;
1001 : AstType* bits = AstBitsetType::New(new_bitset);
1002 201195 : result->Set(size++, bits);
1003 200115 : if (!range->IsNone()) result->Set(size++, range);
1004 :
1005 200115 : size = AddToUnion(type1, result, size, zone);
1006 200115 : size = AddToUnion(type2, result, size, zone);
1007 200115 : return NormalizeUnion(result_type, size, zone);
1008 : }
1009 :
1010 : // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
1011 : // Return new size of [result].
1012 744654 : int AstType::AddToUnion(AstType* type, AstUnionType* result, int size,
1013 : Zone* zone) {
1014 1269907 : if (type->IsBitset() || type->IsRange()) return size;
1015 523903 : if (type->IsUnion()) {
1016 251547 : for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
1017 404384 : size = AddToUnion(type->AsUnion()->Get(i), result, size, zone);
1018 : }
1019 : return size;
1020 : }
1021 733402 : for (int i = 0; i < size; ++i) {
1022 2009293 : if (type->SemanticIs(result->Get(i))) return size;
1023 : }
1024 406607 : result->Set(size++, type);
1025 406607 : return size;
1026 : }
1027 :
1028 763574 : AstType* AstType::NormalizeUnion(AstType* union_type, int size, Zone* zone) {
1029 : AstUnionType* unioned = union_type->AsUnion();
1030 : DCHECK(size >= 1);
1031 : DCHECK(unioned->Get(0)->IsBitset());
1032 : // If the union has just one element, return it.
1033 763574 : if (size == 1) {
1034 1100170 : return unioned->Get(0);
1035 : }
1036 : bitset bits = unioned->Get(0)->AsBitset();
1037 : // If the union only consists of a range, we can get rid of the union.
1038 248619 : if (size == 2 && AST_SEMANTIC(bits) == AstBitsetType::kNone) {
1039 70260 : bitset representation = AST_REPRESENTATION(bits);
1040 70260 : if (representation == unioned->Get(1)->Representation()) {
1041 6888 : return unioned->Get(1);
1042 : }
1043 63372 : if (unioned->Get(1)->IsRange()) {
1044 : return AstRangeType::New(unioned->Get(1)->AsRange()->Min(),
1045 : unioned->Get(1)->AsRange()->Max(),
1046 0 : unioned->Get(0)->AsBitset(), zone);
1047 : }
1048 : }
1049 : unioned->Shrink(size);
1050 : SLOW_DCHECK(unioned->Wellformed());
1051 241731 : return union_type;
1052 : }
1053 :
1054 : // -----------------------------------------------------------------------------
1055 : // Component extraction
1056 :
1057 : // static
1058 68801 : AstType* AstType::Representation(AstType* t, Zone* zone) {
1059 68801 : return AstBitsetType::New(t->Representation());
1060 : }
1061 :
1062 : // static
1063 68805 : AstType* AstType::Semantic(AstType* t, Zone* zone) {
1064 68805 : return Intersect(t, AstBitsetType::New(AstBitsetType::kSemantic), zone);
1065 : }
1066 :
1067 : // -----------------------------------------------------------------------------
1068 : // Iteration.
1069 :
1070 206338 : int AstType::NumClasses() {
1071 : DisallowHeapAllocation no_allocation;
1072 206338 : if (this->IsClass()) {
1073 : return 1;
1074 202046 : } else if (this->IsUnion()) {
1075 : int result = 0;
1076 47344 : for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1077 74428 : if (this->AsUnion()->Get(i)->IsClass()) ++result;
1078 : }
1079 : return result;
1080 : } else {
1081 : return 0;
1082 : }
1083 : }
1084 :
1085 206338 : int AstType::NumConstants() {
1086 : DisallowHeapAllocation no_allocation;
1087 206338 : if (this->IsConstant()) {
1088 : return 1;
1089 194572 : } else if (this->IsUnion()) {
1090 : int result = 0;
1091 47344 : for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1092 74428 : if (this->AsUnion()->Get(i)->IsConstant()) ++result;
1093 : }
1094 : return result;
1095 : } else {
1096 : return 0;
1097 : }
1098 : }
1099 :
1100 : template <class T>
1101 0 : AstType* AstType::Iterator<T>::get_type() {
1102 : DCHECK(!Done());
1103 11810 : return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_;
1104 : }
1105 :
1106 : // C++ cannot specialise nested templates, so we have to go through this
1107 : // contortion with an auxiliary template to simulate it.
1108 : template <class T>
1109 : struct TypeImplIteratorAux {
1110 : static bool matches(AstType* type);
1111 : static i::Handle<T> current(AstType* type);
1112 : };
1113 :
1114 : template <>
1115 : struct TypeImplIteratorAux<i::Map> {
1116 : static bool matches(AstType* type) { return type->IsClass(); }
1117 : static i::Handle<i::Map> current(AstType* type) {
1118 : return type->AsClass()->Map();
1119 : }
1120 : };
1121 :
1122 : template <>
1123 : struct TypeImplIteratorAux<i::Object> {
1124 : static bool matches(AstType* type) { return type->IsConstant(); }
1125 : static i::Handle<i::Object> current(AstType* type) {
1126 : return type->AsConstant()->Value();
1127 : }
1128 : };
1129 :
1130 : template <class T>
1131 0 : bool AstType::Iterator<T>::matches(AstType* type) {
1132 0 : return TypeImplIteratorAux<T>::matches(type);
1133 : }
1134 :
1135 : template <class T>
1136 5905 : i::Handle<T> AstType::Iterator<T>::Current() {
1137 5905 : return TypeImplIteratorAux<T>::current(get_type());
1138 : }
1139 :
1140 : template <class T>
1141 19957 : void AstType::Iterator<T>::Advance() {
1142 : DisallowHeapAllocation no_allocation;
1143 19957 : ++index_;
1144 39914 : if (type_->IsUnion()) {
1145 11359 : for (int n = type_->AsUnion()->Length(); index_ < n; ++index_) {
1146 20090 : if (matches(type_->AsUnion()->Get(index_))) return;
1147 : }
1148 28326 : } else if (index_ == 0 && matches(type_)) {
1149 : return;
1150 : }
1151 14052 : index_ = -1;
1152 : }
1153 :
1154 : // -----------------------------------------------------------------------------
1155 : // Printing.
1156 :
1157 0 : const char* AstBitsetType::Name(bitset bits) {
1158 0 : switch (bits) {
1159 : case AST_REPRESENTATION(kAny):
1160 : return "Any";
1161 : #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \
1162 : case AST_REPRESENTATION(k##type): \
1163 : return #type;
1164 0 : AST_REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE)
1165 : #undef RETURN_NAMED_REPRESENTATION_TYPE
1166 :
1167 : #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \
1168 : case AST_SEMANTIC(k##type): \
1169 : return #type;
1170 0 : AST_SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
1171 0 : AST_INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
1172 : #undef RETURN_NAMED_SEMANTIC_TYPE
1173 :
1174 : default:
1175 0 : return NULL;
1176 : }
1177 : }
1178 :
1179 0 : void AstBitsetType::Print(std::ostream& os, // NOLINT
1180 : bitset bits) {
1181 : DisallowHeapAllocation no_allocation;
1182 0 : const char* name = Name(bits);
1183 0 : if (name != NULL) {
1184 0 : os << name;
1185 0 : return;
1186 : }
1187 :
1188 : // clang-format off
1189 : static const bitset named_bitsets[] = {
1190 : #define BITSET_CONSTANT(type, value) AST_REPRESENTATION(k##type),
1191 : AST_REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
1192 : #undef BITSET_CONSTANT
1193 :
1194 : #define BITSET_CONSTANT(type, value) AST_SEMANTIC(k##type),
1195 : AST_INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
1196 : AST_SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
1197 : #undef BITSET_CONSTANT
1198 : };
1199 : // clang-format on
1200 :
1201 : bool is_first = true;
1202 0 : os << "(";
1203 0 : for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
1204 0 : bitset subset = named_bitsets[i];
1205 0 : if ((bits & subset) == subset) {
1206 0 : if (!is_first) os << " | ";
1207 : is_first = false;
1208 0 : os << Name(subset);
1209 0 : bits -= subset;
1210 : }
1211 : }
1212 : DCHECK(bits == 0);
1213 0 : os << ")";
1214 : }
1215 :
1216 0 : void AstType::PrintTo(std::ostream& os, PrintDimension dim) {
1217 : DisallowHeapAllocation no_allocation;
1218 0 : if (dim != REPRESENTATION_DIM) {
1219 0 : if (this->IsBitset()) {
1220 0 : AstBitsetType::Print(os, AST_SEMANTIC(this->AsBitset()));
1221 0 : } else if (this->IsClass()) {
1222 0 : os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < ";
1223 0 : AstBitsetType::New(AstBitsetType::Lub(this))->PrintTo(os, dim);
1224 0 : os << ")";
1225 0 : } else if (this->IsConstant()) {
1226 0 : os << "Constant(" << Brief(*this->AsConstant()->Value()) << ")";
1227 0 : } else if (this->IsRange()) {
1228 0 : std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed);
1229 : std::streamsize saved_precision = os.precision(0);
1230 0 : os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max()
1231 0 : << ")";
1232 0 : os.flags(saved_flags);
1233 : os.precision(saved_precision);
1234 0 : } else if (this->IsContext()) {
1235 0 : os << "Context(";
1236 0 : this->AsContext()->Outer()->PrintTo(os, dim);
1237 0 : os << ")";
1238 0 : } else if (this->IsUnion()) {
1239 0 : os << "(";
1240 0 : for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1241 0 : AstType* type_i = this->AsUnion()->Get(i);
1242 0 : if (i > 0) os << " | ";
1243 0 : type_i->PrintTo(os, dim);
1244 : }
1245 0 : os << ")";
1246 0 : } else if (this->IsArray()) {
1247 0 : os << "Array(";
1248 0 : AsArray()->Element()->PrintTo(os, dim);
1249 0 : os << ")";
1250 0 : } else if (this->IsFunction()) {
1251 0 : if (!this->AsFunction()->Receiver()->IsAny()) {
1252 0 : this->AsFunction()->Receiver()->PrintTo(os, dim);
1253 0 : os << ".";
1254 : }
1255 0 : os << "(";
1256 0 : for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
1257 0 : if (i > 0) os << ", ";
1258 0 : this->AsFunction()->Parameter(i)->PrintTo(os, dim);
1259 : }
1260 0 : os << ")->";
1261 0 : this->AsFunction()->Result()->PrintTo(os, dim);
1262 0 : } else if (this->IsTuple()) {
1263 0 : os << "<";
1264 0 : for (int i = 0, n = this->AsTuple()->Arity(); i < n; ++i) {
1265 : AstType* type_i = this->AsTuple()->Element(i);
1266 0 : if (i > 0) os << ", ";
1267 0 : type_i->PrintTo(os, dim);
1268 : }
1269 0 : os << ">";
1270 : } else {
1271 0 : UNREACHABLE();
1272 : }
1273 : }
1274 0 : if (dim == BOTH_DIMS) os << "/";
1275 0 : if (dim != SEMANTIC_DIM) {
1276 0 : AstBitsetType::Print(os, AST_REPRESENTATION(this->BitsetLub()));
1277 : }
1278 0 : }
1279 :
1280 : #ifdef DEBUG
1281 : void AstType::Print() {
1282 : OFStream os(stdout);
1283 : PrintTo(os);
1284 : os << std::endl;
1285 : }
1286 : void AstBitsetType::Print(bitset bits) {
1287 : OFStream os(stdout);
1288 : Print(os, bits);
1289 : os << std::endl;
1290 : }
1291 : #endif
1292 :
1293 4261550 : AstBitsetType::bitset AstBitsetType::SignedSmall() {
1294 4261550 : return i::SmiValuesAre31Bits() ? kSigned31 : kSigned32;
1295 : }
1296 :
1297 27 : AstBitsetType::bitset AstBitsetType::UnsignedSmall() {
1298 27 : return i::SmiValuesAre31Bits() ? kUnsigned30 : kUnsigned31;
1299 : }
1300 :
1301 : // -----------------------------------------------------------------------------
1302 : // Instantiations.
1303 :
1304 : template class AstType::Iterator<i::Map>;
1305 : template class AstType::Iterator<i::Object>;
1306 :
1307 : } // namespace internal
1308 : } // namespace v8
|
