OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include <iomanip> | 5 #include <iomanip> |
6 | 6 |
7 #include "src/types.h" | 7 #include "src/types.h" |
8 | 8 |
| 9 #include "src/handles-inl.h" |
9 #include "src/ostreams.h" | 10 #include "src/ostreams.h" |
10 #include "src/types-inl.h" | |
11 | 11 |
12 namespace v8 { | 12 namespace v8 { |
13 namespace internal { | 13 namespace internal { |
14 | 14 |
15 | 15 |
16 // NOTE: If code is marked as being a "shortcut", this means that removing | 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. | 17 // the code won't affect the semantics of the surrounding function definition. |
18 | 18 |
| 19 // static |
| 20 bool Type::IsInteger(i::Object* x) { |
| 21 return x->IsNumber() && Type::IsInteger(x->Number()); |
| 22 } |
19 | 23 |
20 // ----------------------------------------------------------------------------- | 24 // ----------------------------------------------------------------------------- |
21 // Range-related helper functions. | 25 // Range-related helper functions. |
22 | 26 |
23 template <class Config> | 27 bool RangeType::Limits::IsEmpty() { return this->min > this->max; } |
24 bool TypeImpl<Config>::Limits::IsEmpty() { | |
25 return this->min > this->max; | |
26 } | |
27 | 28 |
28 | 29 RangeType::Limits RangeType::Limits::Intersect(Limits lhs, Limits rhs) { |
29 template<class Config> | |
30 typename TypeImpl<Config>::Limits TypeImpl<Config>::Limits::Intersect( | |
31 Limits lhs, Limits rhs) { | |
32 DisallowHeapAllocation no_allocation; | 30 DisallowHeapAllocation no_allocation; |
33 Limits result(lhs); | 31 Limits result(lhs); |
34 if (lhs.min < rhs.min) result.min = rhs.min; | 32 if (lhs.min < rhs.min) result.min = rhs.min; |
35 if (lhs.max > rhs.max) result.max = rhs.max; | 33 if (lhs.max > rhs.max) result.max = rhs.max; |
36 return result; | 34 return result; |
37 } | 35 } |
38 | 36 |
39 | 37 RangeType::Limits RangeType::Limits::Union(Limits lhs, Limits rhs) { |
40 template <class Config> | |
41 typename TypeImpl<Config>::Limits TypeImpl<Config>::Limits::Union( | |
42 Limits lhs, Limits rhs) { | |
43 DisallowHeapAllocation no_allocation; | 38 DisallowHeapAllocation no_allocation; |
44 if (lhs.IsEmpty()) return rhs; | 39 if (lhs.IsEmpty()) return rhs; |
45 if (rhs.IsEmpty()) return lhs; | 40 if (rhs.IsEmpty()) return lhs; |
46 Limits result(lhs); | 41 Limits result(lhs); |
47 if (lhs.min > rhs.min) result.min = rhs.min; | 42 if (lhs.min > rhs.min) result.min = rhs.min; |
48 if (lhs.max < rhs.max) result.max = rhs.max; | 43 if (lhs.max < rhs.max) result.max = rhs.max; |
49 return result; | 44 return result; |
50 } | 45 } |
51 | 46 |
52 | 47 bool Type::Overlap(RangeType* lhs, RangeType* rhs) { |
53 template<class Config> | |
54 bool TypeImpl<Config>::Overlap( | |
55 typename TypeImpl<Config>::RangeType* lhs, | |
56 typename TypeImpl<Config>::RangeType* rhs) { | |
57 DisallowHeapAllocation no_allocation; | 48 DisallowHeapAllocation no_allocation; |
58 return !Limits::Intersect(Limits(lhs), Limits(rhs)).IsEmpty(); | 49 return !RangeType::Limits::Intersect(RangeType::Limits(lhs), |
| 50 RangeType::Limits(rhs)) |
| 51 .IsEmpty(); |
59 } | 52 } |
60 | 53 |
61 | 54 bool Type::Contains(RangeType* lhs, RangeType* rhs) { |
62 template<class Config> | |
63 bool TypeImpl<Config>::Contains( | |
64 typename TypeImpl<Config>::RangeType* lhs, | |
65 typename TypeImpl<Config>::RangeType* rhs) { | |
66 DisallowHeapAllocation no_allocation; | 55 DisallowHeapAllocation no_allocation; |
67 return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max(); | 56 return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max(); |
68 } | 57 } |
69 | 58 |
70 | 59 bool Type::Contains(RangeType* lhs, ConstantType* rhs) { |
71 template <class Config> | |
72 bool TypeImpl<Config>::Contains(typename TypeImpl<Config>::RangeType* lhs, | |
73 typename TypeImpl<Config>::ConstantType* rhs) { | |
74 DisallowHeapAllocation no_allocation; | 60 DisallowHeapAllocation no_allocation; |
75 return IsInteger(*rhs->Value()) && | 61 return IsInteger(*rhs->Value()) && |
76 lhs->Min() <= rhs->Value()->Number() && | 62 lhs->Min() <= rhs->Value()->Number() && |
77 rhs->Value()->Number() <= lhs->Max(); | 63 rhs->Value()->Number() <= lhs->Max(); |
78 } | 64 } |
79 | 65 |
80 | 66 bool Type::Contains(RangeType* range, i::Object* val) { |
81 template<class Config> | |
82 bool TypeImpl<Config>::Contains( | |
83 typename TypeImpl<Config>::RangeType* range, i::Object* val) { | |
84 DisallowHeapAllocation no_allocation; | 67 DisallowHeapAllocation no_allocation; |
85 return IsInteger(val) && | 68 return IsInteger(val) && |
86 range->Min() <= val->Number() && val->Number() <= range->Max(); | 69 range->Min() <= val->Number() && val->Number() <= range->Max(); |
87 } | 70 } |
88 | 71 |
89 | 72 |
90 // ----------------------------------------------------------------------------- | 73 // ----------------------------------------------------------------------------- |
91 // Min and Max computation. | 74 // Min and Max computation. |
92 | 75 |
93 template<class Config> | 76 double Type::Min() { |
94 double TypeImpl<Config>::Min() { | |
95 DCHECK(this->SemanticIs(Number())); | 77 DCHECK(this->SemanticIs(Number())); |
96 if (this->IsBitset()) return BitsetType::Min(this->AsBitset()); | 78 if (this->IsBitset()) return BitsetType::Min(this->AsBitset()); |
97 if (this->IsUnion()) { | 79 if (this->IsUnion()) { |
98 double min = +V8_INFINITY; | 80 double min = +V8_INFINITY; |
99 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { | 81 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { |
100 min = std::min(min, this->AsUnion()->Get(i)->Min()); | 82 min = std::min(min, this->AsUnion()->Get(i)->Min()); |
101 } | 83 } |
102 return min; | 84 return min; |
103 } | 85 } |
104 if (this->IsRange()) return this->AsRange()->Min(); | 86 if (this->IsRange()) return this->AsRange()->Min(); |
105 if (this->IsConstant()) return this->AsConstant()->Value()->Number(); | 87 if (this->IsConstant()) return this->AsConstant()->Value()->Number(); |
106 UNREACHABLE(); | 88 UNREACHABLE(); |
107 return 0; | 89 return 0; |
108 } | 90 } |
109 | 91 |
110 | 92 double Type::Max() { |
111 template<class Config> | |
112 double TypeImpl<Config>::Max() { | |
113 DCHECK(this->SemanticIs(Number())); | 93 DCHECK(this->SemanticIs(Number())); |
114 if (this->IsBitset()) return BitsetType::Max(this->AsBitset()); | 94 if (this->IsBitset()) return BitsetType::Max(this->AsBitset()); |
115 if (this->IsUnion()) { | 95 if (this->IsUnion()) { |
116 double max = -V8_INFINITY; | 96 double max = -V8_INFINITY; |
117 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { | 97 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { |
118 max = std::max(max, this->AsUnion()->Get(i)->Max()); | 98 max = std::max(max, this->AsUnion()->Get(i)->Max()); |
119 } | 99 } |
120 return max; | 100 return max; |
121 } | 101 } |
122 if (this->IsRange()) return this->AsRange()->Max(); | 102 if (this->IsRange()) return this->AsRange()->Max(); |
123 if (this->IsConstant()) return this->AsConstant()->Value()->Number(); | 103 if (this->IsConstant()) return this->AsConstant()->Value()->Number(); |
124 UNREACHABLE(); | 104 UNREACHABLE(); |
125 return 0; | 105 return 0; |
126 } | 106 } |
127 | 107 |
128 | 108 |
129 // ----------------------------------------------------------------------------- | 109 // ----------------------------------------------------------------------------- |
130 // Glb and lub computation. | 110 // Glb and lub computation. |
131 | 111 |
132 | 112 |
133 // The largest bitset subsumed by this type. | 113 // The largest bitset subsumed by this type. |
134 template<class Config> | 114 Type::bitset BitsetType::Glb(Type* type) { |
135 typename TypeImpl<Config>::bitset | |
136 TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) { | |
137 DisallowHeapAllocation no_allocation; | 115 DisallowHeapAllocation no_allocation; |
138 // Fast case. | 116 // Fast case. |
139 if (type->IsBitset()) { | 117 if (IsBitset(type)) { |
140 return type->AsBitset(); | 118 return type->AsBitset(); |
141 } else if (type->IsUnion()) { | 119 } else if (type->IsUnion()) { |
142 SLOW_DCHECK(type->AsUnion()->Wellformed()); | 120 SLOW_DCHECK(type->AsUnion()->Wellformed()); |
143 return type->AsUnion()->Get(0)->BitsetGlb() | | 121 return type->AsUnion()->Get(0)->BitsetGlb() | |
144 SEMANTIC(type->AsUnion()->Get(1)->BitsetGlb()); // Shortcut. | 122 SEMANTIC(type->AsUnion()->Get(1)->BitsetGlb()); // Shortcut. |
145 } else if (type->IsRange()) { | 123 } else if (type->IsRange()) { |
146 bitset glb = SEMANTIC( | 124 bitset glb = SEMANTIC( |
147 BitsetType::Glb(type->AsRange()->Min(), type->AsRange()->Max())); | 125 BitsetType::Glb(type->AsRange()->Min(), type->AsRange()->Max())); |
148 return glb | REPRESENTATION(type->BitsetLub()); | 126 return glb | REPRESENTATION(type->BitsetLub()); |
149 } else { | 127 } else { |
150 return type->Representation(); | 128 return type->Representation(); |
151 } | 129 } |
152 } | 130 } |
153 | 131 |
154 | 132 |
155 // The smallest bitset subsuming this type, possibly not a proper one. | 133 // The smallest bitset subsuming this type, possibly not a proper one. |
156 template<class Config> | 134 Type::bitset BitsetType::Lub(Type* type) { |
157 typename TypeImpl<Config>::bitset | |
158 TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) { | |
159 DisallowHeapAllocation no_allocation; | 135 DisallowHeapAllocation no_allocation; |
160 if (type->IsBitset()) return type->AsBitset(); | 136 if (IsBitset(type)) return type->AsBitset(); |
161 if (type->IsUnion()) { | 137 if (type->IsUnion()) { |
162 // Take the representation from the first element, which is always | 138 // Take the representation from the first element, which is always |
163 // a bitset. | 139 // a bitset. |
164 int bitset = type->AsUnion()->Get(0)->BitsetLub(); | 140 int bitset = type->AsUnion()->Get(0)->BitsetLub(); |
165 for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) { | 141 for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) { |
166 // Other elements only contribute their semantic part. | 142 // Other elements only contribute their semantic part. |
167 bitset |= SEMANTIC(type->AsUnion()->Get(i)->BitsetLub()); | 143 bitset |= SEMANTIC(type->AsUnion()->Get(i)->BitsetLub()); |
168 } | 144 } |
169 return bitset; | 145 return bitset; |
170 } | 146 } |
171 if (type->IsClass()) return type->AsClass()->Lub(); | 147 if (type->IsClass()) return type->AsClass()->Lub(); |
172 if (type->IsConstant()) return type->AsConstant()->Lub(); | 148 if (type->IsConstant()) return type->AsConstant()->Lub(); |
173 if (type->IsRange()) return type->AsRange()->Lub(); | 149 if (type->IsRange()) return type->AsRange()->Lub(); |
174 if (type->IsContext()) return kInternal & kTaggedPointer; | 150 if (type->IsContext()) return kInternal & kTaggedPointer; |
175 if (type->IsArray()) return kOtherObject; | 151 if (type->IsArray()) return kOtherObject; |
176 if (type->IsFunction()) return kFunction; | 152 if (type->IsFunction()) return kFunction; |
177 if (type->IsTuple()) return kInternal; | 153 if (type->IsTuple()) return kInternal; |
178 UNREACHABLE(); | 154 UNREACHABLE(); |
179 return kNone; | 155 return kNone; |
180 } | 156 } |
181 | 157 |
182 | 158 Type::bitset BitsetType::Lub(i::Map* map) { |
183 template<class Config> | |
184 typename TypeImpl<Config>::bitset | |
185 TypeImpl<Config>::BitsetType::Lub(i::Map* map) { | |
186 DisallowHeapAllocation no_allocation; | 159 DisallowHeapAllocation no_allocation; |
187 switch (map->instance_type()) { | 160 switch (map->instance_type()) { |
188 case STRING_TYPE: | 161 case STRING_TYPE: |
189 case ONE_BYTE_STRING_TYPE: | 162 case ONE_BYTE_STRING_TYPE: |
190 case CONS_STRING_TYPE: | 163 case CONS_STRING_TYPE: |
191 case CONS_ONE_BYTE_STRING_TYPE: | 164 case CONS_ONE_BYTE_STRING_TYPE: |
192 case SLICED_STRING_TYPE: | 165 case SLICED_STRING_TYPE: |
193 case SLICED_ONE_BYTE_STRING_TYPE: | 166 case SLICED_ONE_BYTE_STRING_TYPE: |
194 case EXTERNAL_STRING_TYPE: | 167 case EXTERNAL_STRING_TYPE: |
195 case EXTERNAL_ONE_BYTE_STRING_TYPE: | 168 case EXTERNAL_ONE_BYTE_STRING_TYPE: |
(...skipping 115 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
311 case WEAK_CELL_TYPE: | 284 case WEAK_CELL_TYPE: |
312 case PROTOTYPE_INFO_TYPE: | 285 case PROTOTYPE_INFO_TYPE: |
313 case SLOPPY_BLOCK_WITH_EVAL_CONTEXT_EXTENSION_TYPE: | 286 case SLOPPY_BLOCK_WITH_EVAL_CONTEXT_EXTENSION_TYPE: |
314 UNREACHABLE(); | 287 UNREACHABLE(); |
315 return kNone; | 288 return kNone; |
316 } | 289 } |
317 UNREACHABLE(); | 290 UNREACHABLE(); |
318 return kNone; | 291 return kNone; |
319 } | 292 } |
320 | 293 |
321 | 294 Type::bitset BitsetType::Lub(i::Object* value) { |
322 template<class Config> | |
323 typename TypeImpl<Config>::bitset | |
324 TypeImpl<Config>::BitsetType::Lub(i::Object* value) { | |
325 DisallowHeapAllocation no_allocation; | 295 DisallowHeapAllocation no_allocation; |
326 if (value->IsNumber()) { | 296 if (value->IsNumber()) { |
327 return Lub(value->Number()) & | 297 return Lub(value->Number()) & |
328 (value->IsSmi() ? kTaggedSigned : kTaggedPointer); | 298 (value->IsSmi() ? kTaggedSigned : kTaggedPointer); |
329 } | 299 } |
330 return Lub(i::HeapObject::cast(value)->map()); | 300 return Lub(i::HeapObject::cast(value)->map()); |
331 } | 301 } |
332 | 302 |
333 | 303 Type::bitset BitsetType::Lub(double value) { |
334 template<class Config> | |
335 typename TypeImpl<Config>::bitset | |
336 TypeImpl<Config>::BitsetType::Lub(double value) { | |
337 DisallowHeapAllocation no_allocation; | 304 DisallowHeapAllocation no_allocation; |
338 if (i::IsMinusZero(value)) return kMinusZero; | 305 if (i::IsMinusZero(value)) return kMinusZero; |
339 if (std::isnan(value)) return kNaN; | 306 if (std::isnan(value)) return kNaN; |
340 if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value); | 307 if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value); |
341 return kOtherNumber; | 308 return kOtherNumber; |
342 } | 309 } |
343 | 310 |
344 | 311 |
345 // Minimum values of plain numeric bitsets. | 312 // Minimum values of plain numeric bitsets. |
346 template <class Config> | 313 const BitsetType::Boundary BitsetType::BoundariesArray[] = { |
347 const typename TypeImpl<Config>::BitsetType::Boundary | 314 {kOtherNumber, kPlainNumber, -V8_INFINITY}, |
348 TypeImpl<Config>::BitsetType::BoundariesArray[] = { | 315 {kOtherSigned32, kNegative32, kMinInt}, |
349 {kOtherNumber, kPlainNumber, -V8_INFINITY}, | 316 {kNegative31, kNegative31, -0x40000000}, |
350 {kOtherSigned32, kNegative32, kMinInt}, | 317 {kUnsigned30, kUnsigned30, 0}, |
351 {kNegative31, kNegative31, -0x40000000}, | 318 {kOtherUnsigned31, kUnsigned31, 0x40000000}, |
352 {kUnsigned30, kUnsigned30, 0}, | 319 {kOtherUnsigned32, kUnsigned32, 0x80000000}, |
353 {kOtherUnsigned31, kUnsigned31, 0x40000000}, | 320 {kOtherNumber, kPlainNumber, static_cast<double>(kMaxUInt32) + 1}}; |
354 {kOtherUnsigned32, kUnsigned32, 0x80000000}, | |
355 {kOtherNumber, kPlainNumber, static_cast<double>(kMaxUInt32) + 1}}; | |
356 | 321 |
| 322 const BitsetType::Boundary* BitsetType::Boundaries() { return BoundariesArray; } |
357 | 323 |
358 template <class Config> | 324 size_t BitsetType::BoundariesSize() { |
359 const typename TypeImpl<Config>::BitsetType::Boundary* | |
360 TypeImpl<Config>::BitsetType::Boundaries() { | |
361 return BoundariesArray; | |
362 } | |
363 | |
364 | |
365 template <class Config> | |
366 size_t TypeImpl<Config>::BitsetType::BoundariesSize() { | |
367 // Windows doesn't like arraysize here. | 325 // Windows doesn't like arraysize here. |
368 // return arraysize(BoundariesArray); | 326 // return arraysize(BoundariesArray); |
369 return 7; | 327 return 7; |
370 } | 328 } |
371 | 329 |
372 | 330 Type::bitset BitsetType::ExpandInternals(Type::bitset bits) { |
373 template <class Config> | |
374 typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::ExpandInternals( | |
375 typename TypeImpl<Config>::bitset bits) { | |
376 DisallowHeapAllocation no_allocation; | 331 DisallowHeapAllocation no_allocation; |
377 if (!(bits & SEMANTIC(kPlainNumber))) return bits; // Shortcut. | 332 if (!(bits & SEMANTIC(kPlainNumber))) return bits; // Shortcut. |
378 const Boundary* boundaries = Boundaries(); | 333 const Boundary* boundaries = Boundaries(); |
379 for (size_t i = 0; i < BoundariesSize(); ++i) { | 334 for (size_t i = 0; i < BoundariesSize(); ++i) { |
380 DCHECK(BitsetType::Is(boundaries[i].internal, boundaries[i].external)); | 335 DCHECK(BitsetType::Is(boundaries[i].internal, boundaries[i].external)); |
381 if (bits & SEMANTIC(boundaries[i].internal)) | 336 if (bits & SEMANTIC(boundaries[i].internal)) |
382 bits |= SEMANTIC(boundaries[i].external); | 337 bits |= SEMANTIC(boundaries[i].external); |
383 } | 338 } |
384 return bits; | 339 return bits; |
385 } | 340 } |
386 | 341 |
387 | 342 Type::bitset BitsetType::Lub(double min, double max) { |
388 template<class Config> | |
389 typename TypeImpl<Config>::bitset | |
390 TypeImpl<Config>::BitsetType::Lub(double min, double max) { | |
391 DisallowHeapAllocation no_allocation; | 343 DisallowHeapAllocation no_allocation; |
392 int lub = kNone; | 344 int lub = kNone; |
393 const Boundary* mins = Boundaries(); | 345 const Boundary* mins = Boundaries(); |
394 | 346 |
395 for (size_t i = 1; i < BoundariesSize(); ++i) { | 347 for (size_t i = 1; i < BoundariesSize(); ++i) { |
396 if (min < mins[i].min) { | 348 if (min < mins[i].min) { |
397 lub |= mins[i-1].internal; | 349 lub |= mins[i-1].internal; |
398 if (max < mins[i].min) return lub; | 350 if (max < mins[i].min) return lub; |
399 } | 351 } |
400 } | 352 } |
401 return lub | mins[BoundariesSize() - 1].internal; | 353 return lub | mins[BoundariesSize() - 1].internal; |
402 } | 354 } |
403 | 355 |
404 | 356 Type::bitset BitsetType::NumberBits(bitset bits) { |
405 template <class Config> | |
406 typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::NumberBits( | |
407 bitset bits) { | |
408 return SEMANTIC(bits & kPlainNumber); | 357 return SEMANTIC(bits & kPlainNumber); |
409 } | 358 } |
410 | 359 |
411 | 360 Type::bitset BitsetType::Glb(double min, double max) { |
412 template <class Config> | |
413 typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::Glb( | |
414 double min, double max) { | |
415 DisallowHeapAllocation no_allocation; | 361 DisallowHeapAllocation no_allocation; |
416 int glb = kNone; | 362 int glb = kNone; |
417 const Boundary* mins = Boundaries(); | 363 const Boundary* mins = Boundaries(); |
418 | 364 |
419 // If the range does not touch 0, the bound is empty. | 365 // If the range does not touch 0, the bound is empty. |
420 if (max < -1 || min > 0) return glb; | 366 if (max < -1 || min > 0) return glb; |
421 | 367 |
422 for (size_t i = 1; i + 1 < BoundariesSize(); ++i) { | 368 for (size_t i = 1; i + 1 < BoundariesSize(); ++i) { |
423 if (min <= mins[i].min) { | 369 if (min <= mins[i].min) { |
424 if (max + 1 < mins[i + 1].min) break; | 370 if (max + 1 < mins[i + 1].min) break; |
425 glb |= mins[i].external; | 371 glb |= mins[i].external; |
426 } | 372 } |
427 } | 373 } |
428 // OtherNumber also contains float numbers, so it can never be | 374 // OtherNumber also contains float numbers, so it can never be |
429 // in the greatest lower bound. | 375 // in the greatest lower bound. |
430 return glb & ~(SEMANTIC(kOtherNumber)); | 376 return glb & ~(SEMANTIC(kOtherNumber)); |
431 } | 377 } |
432 | 378 |
433 | 379 double BitsetType::Min(bitset bits) { |
434 template <class Config> | |
435 double TypeImpl<Config>::BitsetType::Min(bitset bits) { | |
436 DisallowHeapAllocation no_allocation; | 380 DisallowHeapAllocation no_allocation; |
437 DCHECK(Is(SEMANTIC(bits), kNumber)); | 381 DCHECK(Is(SEMANTIC(bits), kNumber)); |
438 const Boundary* mins = Boundaries(); | 382 const Boundary* mins = Boundaries(); |
439 bool mz = SEMANTIC(bits & kMinusZero); | 383 bool mz = SEMANTIC(bits & kMinusZero); |
440 for (size_t i = 0; i < BoundariesSize(); ++i) { | 384 for (size_t i = 0; i < BoundariesSize(); ++i) { |
441 if (Is(SEMANTIC(mins[i].internal), bits)) { | 385 if (Is(SEMANTIC(mins[i].internal), bits)) { |
442 return mz ? std::min(0.0, mins[i].min) : mins[i].min; | 386 return mz ? std::min(0.0, mins[i].min) : mins[i].min; |
443 } | 387 } |
444 } | 388 } |
445 if (mz) return 0; | 389 if (mz) return 0; |
446 return std::numeric_limits<double>::quiet_NaN(); | 390 return std::numeric_limits<double>::quiet_NaN(); |
447 } | 391 } |
448 | 392 |
449 | 393 double BitsetType::Max(bitset bits) { |
450 template<class Config> | |
451 double TypeImpl<Config>::BitsetType::Max(bitset bits) { | |
452 DisallowHeapAllocation no_allocation; | 394 DisallowHeapAllocation no_allocation; |
453 DCHECK(Is(SEMANTIC(bits), kNumber)); | 395 DCHECK(Is(SEMANTIC(bits), kNumber)); |
454 const Boundary* mins = Boundaries(); | 396 const Boundary* mins = Boundaries(); |
455 bool mz = SEMANTIC(bits & kMinusZero); | 397 bool mz = SEMANTIC(bits & kMinusZero); |
456 if (BitsetType::Is(SEMANTIC(mins[BoundariesSize() - 1].internal), bits)) { | 398 if (BitsetType::Is(SEMANTIC(mins[BoundariesSize() - 1].internal), bits)) { |
457 return +V8_INFINITY; | 399 return +V8_INFINITY; |
458 } | 400 } |
459 for (size_t i = BoundariesSize() - 1; i-- > 0;) { | 401 for (size_t i = BoundariesSize() - 1; i-- > 0;) { |
460 if (Is(SEMANTIC(mins[i].internal), bits)) { | 402 if (Is(SEMANTIC(mins[i].internal), bits)) { |
461 return mz ? | 403 return mz ? |
462 std::max(0.0, mins[i+1].min - 1) : mins[i+1].min - 1; | 404 std::max(0.0, mins[i+1].min - 1) : mins[i+1].min - 1; |
463 } | 405 } |
464 } | 406 } |
465 if (mz) return 0; | 407 if (mz) return 0; |
466 return std::numeric_limits<double>::quiet_NaN(); | 408 return std::numeric_limits<double>::quiet_NaN(); |
467 } | 409 } |
468 | 410 |
469 | 411 |
470 // ----------------------------------------------------------------------------- | 412 // ----------------------------------------------------------------------------- |
471 // Predicates. | 413 // Predicates. |
472 | 414 |
473 | 415 bool Type::SimplyEquals(Type* that) { |
474 template<class Config> | |
475 bool TypeImpl<Config>::SimplyEquals(TypeImpl* that) { | |
476 DisallowHeapAllocation no_allocation; | 416 DisallowHeapAllocation no_allocation; |
477 if (this->IsClass()) { | 417 if (this->IsClass()) { |
478 return that->IsClass() | 418 return that->IsClass() |
479 && *this->AsClass()->Map() == *that->AsClass()->Map(); | 419 && *this->AsClass()->Map() == *that->AsClass()->Map(); |
480 } | 420 } |
481 if (this->IsConstant()) { | 421 if (this->IsConstant()) { |
482 return that->IsConstant() | 422 return that->IsConstant() |
483 && *this->AsConstant()->Value() == *that->AsConstant()->Value(); | 423 && *this->AsConstant()->Value() == *that->AsConstant()->Value(); |
484 } | 424 } |
485 if (this->IsContext()) { | 425 if (this->IsContext()) { |
(...skipping 27 matching lines...) Expand all Loading... |
513 } | 453 } |
514 for (int i = 0, n = this_tuple->Arity(); i < n; ++i) { | 454 for (int i = 0, n = this_tuple->Arity(); i < n; ++i) { |
515 if (!this_tuple->Element(i)->Equals(that_tuple->Element(i))) return false; | 455 if (!this_tuple->Element(i)->Equals(that_tuple->Element(i))) return false; |
516 } | 456 } |
517 return true; | 457 return true; |
518 } | 458 } |
519 UNREACHABLE(); | 459 UNREACHABLE(); |
520 return false; | 460 return false; |
521 } | 461 } |
522 | 462 |
523 | 463 Type::bitset Type::Representation() { |
524 template <class Config> | |
525 typename TypeImpl<Config>::bitset TypeImpl<Config>::Representation() { | |
526 return REPRESENTATION(this->BitsetLub()); | 464 return REPRESENTATION(this->BitsetLub()); |
527 } | 465 } |
528 | 466 |
529 | 467 |
530 // Check if [this] <= [that]. | 468 // Check if [this] <= [that]. |
531 template<class Config> | 469 bool Type::SlowIs(Type* that) { |
532 bool TypeImpl<Config>::SlowIs(TypeImpl* that) { | |
533 DisallowHeapAllocation no_allocation; | 470 DisallowHeapAllocation no_allocation; |
534 | 471 |
535 // Fast bitset cases | 472 // Fast bitset cases |
536 if (that->IsBitset()) { | 473 if (that->IsBitset()) { |
537 return BitsetType::Is(this->BitsetLub(), that->AsBitset()); | 474 return BitsetType::Is(this->BitsetLub(), that->AsBitset()); |
538 } | 475 } |
539 | 476 |
540 if (this->IsBitset()) { | 477 if (this->IsBitset()) { |
541 return BitsetType::Is(this->AsBitset(), that->BitsetGlb()); | 478 return BitsetType::Is(this->AsBitset(), that->BitsetGlb()); |
542 } | 479 } |
543 | 480 |
544 // Check the representations. | 481 // Check the representations. |
545 if (!BitsetType::Is(Representation(), that->Representation())) { | 482 if (!BitsetType::Is(Representation(), that->Representation())) { |
546 return false; | 483 return false; |
547 } | 484 } |
548 | 485 |
549 // Check the semantic part. | 486 // Check the semantic part. |
550 return SemanticIs(that); | 487 return SemanticIs(that); |
551 } | 488 } |
552 | 489 |
553 | 490 |
554 // Check if SEMANTIC([this]) <= SEMANTIC([that]). The result of the method | 491 // Check if SEMANTIC([this]) <= SEMANTIC([that]). The result of the method |
555 // should be independent of the representation axis of the types. | 492 // should be independent of the representation axis of the types. |
556 template <class Config> | 493 bool Type::SemanticIs(Type* that) { |
557 bool TypeImpl<Config>::SemanticIs(TypeImpl* that) { | |
558 DisallowHeapAllocation no_allocation; | 494 DisallowHeapAllocation no_allocation; |
559 | 495 |
560 if (this == that) return true; | 496 if (this == that) return true; |
561 | 497 |
562 if (that->IsBitset()) { | 498 if (that->IsBitset()) { |
563 return BitsetType::Is(SEMANTIC(this->BitsetLub()), that->AsBitset()); | 499 return BitsetType::Is(SEMANTIC(this->BitsetLub()), that->AsBitset()); |
564 } | 500 } |
565 if (this->IsBitset()) { | 501 if (this->IsBitset()) { |
566 return BitsetType::Is(SEMANTIC(this->AsBitset()), that->BitsetGlb()); | 502 return BitsetType::Is(SEMANTIC(this->AsBitset()), that->BitsetGlb()); |
567 } | 503 } |
568 | 504 |
569 // (T1 \/ ... \/ Tn) <= T if (T1 <= T) /\ ... /\ (Tn <= T) | 505 // (T1 \/ ... \/ Tn) <= T if (T1 <= T) /\ ... /\ (Tn <= T) |
570 if (this->IsUnion()) { | 506 if (this->IsUnion()) { |
571 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { | 507 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { |
572 if (!this->AsUnion()->Get(i)->SemanticIs(that)) return false; | 508 if (!this->AsUnion()->Get(i)->SemanticIs(that)) return false; |
573 } | 509 } |
574 return true; | 510 return true; |
575 } | 511 } |
576 | 512 |
577 // T <= (T1 \/ ... \/ Tn) if (T <= T1) \/ ... \/ (T <= Tn) | 513 // T <= (T1 \/ ... \/ Tn) if (T <= T1) \/ ... \/ (T <= Tn) |
578 if (that->IsUnion()) { | 514 if (that->IsUnion()) { |
579 for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) { | 515 for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) { |
580 if (this->SemanticIs(that->AsUnion()->Get(i)->unhandle())) return true; | 516 if (this->SemanticIs(that->AsUnion()->Get(i))) return true; |
581 if (i > 1 && this->IsRange()) return false; // Shortcut. | 517 if (i > 1 && this->IsRange()) return false; // Shortcut. |
582 } | 518 } |
583 return false; | 519 return false; |
584 } | 520 } |
585 | 521 |
586 if (that->IsRange()) { | 522 if (that->IsRange()) { |
587 return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) || | 523 return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) || |
588 (this->IsConstant() && | 524 (this->IsConstant() && |
589 Contains(that->AsRange(), this->AsConstant())); | 525 Contains(that->AsRange(), this->AsConstant())); |
590 } | 526 } |
591 if (this->IsRange()) return false; | 527 if (this->IsRange()) return false; |
592 | 528 |
593 return this->SimplyEquals(that); | 529 return this->SimplyEquals(that); |
594 } | 530 } |
595 | 531 |
| 532 // Most precise _current_ type of a value (usually its class). |
| 533 Type* Type::NowOf(i::Object* value, Zone* zone) { |
| 534 if (value->IsSmi() || |
| 535 i::HeapObject::cast(value)->map()->instance_type() == HEAP_NUMBER_TYPE) { |
| 536 return Of(value, zone); |
| 537 } |
| 538 return Class(i::handle(i::HeapObject::cast(value)->map()), zone); |
| 539 } |
596 | 540 |
597 template<class Config> | 541 bool Type::NowContains(i::Object* value) { |
598 bool TypeImpl<Config>::NowIs(TypeImpl* that) { | 542 DisallowHeapAllocation no_allocation; |
| 543 if (this->IsAny()) return true; |
| 544 if (value->IsHeapObject()) { |
| 545 i::Map* map = i::HeapObject::cast(value)->map(); |
| 546 for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) { |
| 547 if (*it.Current() == map) return true; |
| 548 } |
| 549 } |
| 550 return this->Contains(value); |
| 551 } |
| 552 |
| 553 bool Type::NowIs(Type* that) { |
599 DisallowHeapAllocation no_allocation; | 554 DisallowHeapAllocation no_allocation; |
600 | 555 |
601 // TODO(rossberg): this is incorrect for | 556 // TODO(rossberg): this is incorrect for |
602 // Union(Constant(V), T)->NowIs(Class(M)) | 557 // Union(Constant(V), T)->NowIs(Class(M)) |
603 // but fuzzing does not cover that! | 558 // but fuzzing does not cover that! |
604 if (this->IsConstant()) { | 559 if (this->IsConstant()) { |
605 i::Object* object = *this->AsConstant()->Value(); | 560 i::Object* object = *this->AsConstant()->Value(); |
606 if (object->IsHeapObject()) { | 561 if (object->IsHeapObject()) { |
607 i::Map* map = i::HeapObject::cast(object)->map(); | 562 i::Map* map = i::HeapObject::cast(object)->map(); |
608 for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) { | 563 for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) { |
609 if (*it.Current() == map) return true; | 564 if (*it.Current() == map) return true; |
610 } | 565 } |
611 } | 566 } |
612 } | 567 } |
613 return this->Is(that); | 568 return this->Is(that); |
614 } | 569 } |
615 | 570 |
616 | 571 |
617 // Check if [this] contains only (currently) stable classes. | 572 // Check if [this] contains only (currently) stable classes. |
618 template<class Config> | 573 bool Type::NowStable() { |
619 bool TypeImpl<Config>::NowStable() { | |
620 DisallowHeapAllocation no_allocation; | 574 DisallowHeapAllocation no_allocation; |
621 return !this->IsClass() || this->AsClass()->Map()->is_stable(); | 575 return !this->IsClass() || this->AsClass()->Map()->is_stable(); |
622 } | 576 } |
623 | 577 |
624 | 578 |
625 // Check if [this] and [that] overlap. | 579 // Check if [this] and [that] overlap. |
626 template<class Config> | 580 bool Type::Maybe(Type* that) { |
627 bool TypeImpl<Config>::Maybe(TypeImpl* that) { | |
628 DisallowHeapAllocation no_allocation; | 581 DisallowHeapAllocation no_allocation; |
629 | 582 |
630 // Take care of the representation part (and also approximate | 583 // Take care of the representation part (and also approximate |
631 // the semantic part). | 584 // the semantic part). |
632 if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub())) | 585 if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub())) |
633 return false; | 586 return false; |
634 | 587 |
635 return SemanticMaybe(that); | 588 return SemanticMaybe(that); |
636 } | 589 } |
637 | 590 |
638 template <class Config> | 591 bool Type::SemanticMaybe(Type* that) { |
639 bool TypeImpl<Config>::SemanticMaybe(TypeImpl* that) { | |
640 DisallowHeapAllocation no_allocation; | 592 DisallowHeapAllocation no_allocation; |
641 | 593 |
642 // (T1 \/ ... \/ Tn) overlaps T if (T1 overlaps T) \/ ... \/ (Tn overlaps T) | 594 // (T1 \/ ... \/ Tn) overlaps T if (T1 overlaps T) \/ ... \/ (Tn overlaps T) |
643 if (this->IsUnion()) { | 595 if (this->IsUnion()) { |
644 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { | 596 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { |
645 if (this->AsUnion()->Get(i)->SemanticMaybe(that)) return true; | 597 if (this->AsUnion()->Get(i)->SemanticMaybe(that)) return true; |
646 } | 598 } |
647 return false; | 599 return false; |
648 } | 600 } |
649 | 601 |
650 // T overlaps (T1 \/ ... \/ Tn) if (T overlaps T1) \/ ... \/ (T overlaps Tn) | 602 // T overlaps (T1 \/ ... \/ Tn) if (T overlaps T1) \/ ... \/ (T overlaps Tn) |
651 if (that->IsUnion()) { | 603 if (that->IsUnion()) { |
652 for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) { | 604 for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) { |
653 if (this->SemanticMaybe(that->AsUnion()->Get(i)->unhandle())) return true; | 605 if (this->SemanticMaybe(that->AsUnion()->Get(i))) return true; |
654 } | 606 } |
655 return false; | 607 return false; |
656 } | 608 } |
657 | 609 |
658 if (!BitsetType::SemanticIsInhabited(this->BitsetLub() & that->BitsetLub())) | 610 if (!BitsetType::SemanticIsInhabited(this->BitsetLub() & that->BitsetLub())) |
659 return false; | 611 return false; |
660 | 612 |
661 if (this->IsBitset() && that->IsBitset()) return true; | 613 if (this->IsBitset() && that->IsBitset()) return true; |
662 | 614 |
663 if (this->IsClass() != that->IsClass()) return true; | 615 if (this->IsClass() != that->IsClass()) return true; |
(...skipping 19 matching lines...) Expand all Loading... |
683 return that->SemanticMaybe(this); // This case is handled above. | 635 return that->SemanticMaybe(this); // This case is handled above. |
684 } | 636 } |
685 | 637 |
686 if (this->IsBitset() || that->IsBitset()) return true; | 638 if (this->IsBitset() || that->IsBitset()) return true; |
687 | 639 |
688 return this->SimplyEquals(that); | 640 return this->SimplyEquals(that); |
689 } | 641 } |
690 | 642 |
691 | 643 |
692 // Return the range in [this], or [NULL]. | 644 // Return the range in [this], or [NULL]. |
693 template<class Config> | 645 Type* Type::GetRange() { |
694 typename TypeImpl<Config>::RangeType* TypeImpl<Config>::GetRange() { | |
695 DisallowHeapAllocation no_allocation; | 646 DisallowHeapAllocation no_allocation; |
696 if (this->IsRange()) return this->AsRange(); | 647 if (this->IsRange()) return this; |
697 if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) { | 648 if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) { |
698 return this->AsUnion()->Get(1)->AsRange(); | 649 return this->AsUnion()->Get(1); |
699 } | 650 } |
700 return NULL; | 651 return NULL; |
701 } | 652 } |
702 | 653 |
703 | 654 bool Type::Contains(i::Object* value) { |
704 template<class Config> | |
705 bool TypeImpl<Config>::Contains(i::Object* value) { | |
706 DisallowHeapAllocation no_allocation; | 655 DisallowHeapAllocation no_allocation; |
707 for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) { | 656 for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) { |
708 if (*it.Current() == value) return true; | 657 if (*it.Current() == value) return true; |
709 } | 658 } |
710 if (IsInteger(value)) { | 659 if (IsInteger(value)) { |
711 RangeType* range = this->GetRange(); | 660 Type* range = this->GetRange(); |
712 if (range != NULL && Contains(range, value)) return true; | 661 if (range != NULL && Contains(range->AsRange(), value)) return true; |
713 } | 662 } |
714 return BitsetType::New(BitsetType::Lub(value))->Is(this); | 663 return BitsetType::New(BitsetType::Lub(value))->Is(this); |
715 } | 664 } |
716 | 665 |
717 | 666 bool UnionType::Wellformed() { |
718 template<class Config> | |
719 bool TypeImpl<Config>::UnionType::Wellformed() { | |
720 DisallowHeapAllocation no_allocation; | 667 DisallowHeapAllocation no_allocation; |
721 // This checks the invariants of the union representation: | 668 // This checks the invariants of the union representation: |
722 // 1. There are at least two elements. | 669 // 1. There are at least two elements. |
723 // 2. The first element is a bitset, no other element is a bitset. | 670 // 2. The first element is a bitset, no other element is a bitset. |
724 // 3. At most one element is a range, and it must be the second one. | 671 // 3. At most one element is a range, and it must be the second one. |
725 // 4. No element is itself a union. | 672 // 4. No element is itself a union. |
726 // 5. No element (except the bitset) is a subtype of any other. | 673 // 5. No element (except the bitset) is a subtype of any other. |
727 // 6. If there is a range, then the bitset type does not contain | 674 // 6. If there is a range, then the bitset type does not contain |
728 // plain number bits. | 675 // plain number bits. |
729 DCHECK(this->Length() >= 2); // (1) | 676 DCHECK(this->Length() >= 2); // (1) |
730 DCHECK(this->Get(0)->IsBitset()); // (2a) | 677 DCHECK(this->Get(0)->IsBitset()); // (2a) |
731 | 678 |
732 for (int i = 0; i < this->Length(); ++i) { | 679 for (int i = 0; i < this->Length(); ++i) { |
733 if (i != 0) DCHECK(!this->Get(i)->IsBitset()); // (2b) | 680 if (i != 0) DCHECK(!this->Get(i)->IsBitset()); // (2b) |
734 if (i != 1) DCHECK(!this->Get(i)->IsRange()); // (3) | 681 if (i != 1) DCHECK(!this->Get(i)->IsRange()); // (3) |
735 DCHECK(!this->Get(i)->IsUnion()); // (4) | 682 DCHECK(!this->Get(i)->IsUnion()); // (4) |
736 for (int j = 0; j < this->Length(); ++j) { | 683 for (int j = 0; j < this->Length(); ++j) { |
737 if (i != j && i != 0) | 684 if (i != j && i != 0) |
738 DCHECK(!this->Get(i)->SemanticIs(this->Get(j)->unhandle())); // (5) | 685 DCHECK(!this->Get(i)->SemanticIs(this->Get(j))); // (5) |
739 } | 686 } |
740 } | 687 } |
741 DCHECK(!this->Get(1)->IsRange() || | 688 DCHECK(!this->Get(1)->IsRange() || |
742 (BitsetType::NumberBits(this->Get(0)->AsBitset()) == | 689 (BitsetType::NumberBits(this->Get(0)->AsBitset()) == |
743 BitsetType::kNone)); // (6) | 690 BitsetType::kNone)); // (6) |
744 return true; | 691 return true; |
745 } | 692 } |
746 | 693 |
747 | 694 |
748 // ----------------------------------------------------------------------------- | 695 // ----------------------------------------------------------------------------- |
749 // Union and intersection | 696 // Union and intersection |
750 | 697 |
751 | 698 |
752 static bool AddIsSafe(int x, int y) { | 699 static bool AddIsSafe(int x, int y) { |
753 return x >= 0 ? | 700 return x >= 0 ? |
754 y <= std::numeric_limits<int>::max() - x : | 701 y <= std::numeric_limits<int>::max() - x : |
755 y >= std::numeric_limits<int>::min() - x; | 702 y >= std::numeric_limits<int>::min() - x; |
756 } | 703 } |
757 | 704 |
758 | 705 Type* Type::Intersect(Type* type1, Type* type2, Zone* zone) { |
759 template<class Config> | |
760 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect( | |
761 TypeHandle type1, TypeHandle type2, Region* region) { | |
762 | |
763 // Fast case: bit sets. | 706 // Fast case: bit sets. |
764 if (type1->IsBitset() && type2->IsBitset()) { | 707 if (type1->IsBitset() && type2->IsBitset()) { |
765 return BitsetType::New(type1->AsBitset() & type2->AsBitset(), region); | 708 return BitsetType::New(type1->AsBitset() & type2->AsBitset()); |
766 } | 709 } |
767 | 710 |
768 // Fast case: top or bottom types. | 711 // Fast case: top or bottom types. |
769 if (type1->IsNone() || type2->IsAny()) return type1; // Shortcut. | 712 if (type1->IsNone() || type2->IsAny()) return type1; // Shortcut. |
770 if (type2->IsNone() || type1->IsAny()) return type2; // Shortcut. | 713 if (type2->IsNone() || type1->IsAny()) return type2; // Shortcut. |
771 | 714 |
772 // Semi-fast case. | 715 // Semi-fast case. |
773 if (type1->Is(type2)) return type1; | 716 if (type1->Is(type2)) return type1; |
774 if (type2->Is(type1)) return type2; | 717 if (type2->Is(type1)) return type2; |
775 | 718 |
776 // Slow case: create union. | 719 // Slow case: create union. |
777 | 720 |
778 // Figure out the representation of the result first. | 721 // Figure out the representation of the result first. |
779 // The rest of the method should not change this representation and | 722 // The rest of the method should not change this representation and |
780 // it should not make any decisions based on representations (i.e., | 723 // it should not make any decisions based on representations (i.e., |
781 // it should only use the semantic part of types). | 724 // it should only use the semantic part of types). |
782 const bitset representation = | 725 const bitset representation = |
783 type1->Representation() & type2->Representation(); | 726 type1->Representation() & type2->Representation(); |
784 | 727 |
785 // Semantic subtyping check - this is needed for consistency with the | 728 // Semantic subtyping check - this is needed for consistency with the |
786 // semi-fast case above - we should behave the same way regardless of | 729 // semi-fast case above - we should behave the same way regardless of |
787 // representations. Intersection with a universal bitset should only update | 730 // representations. Intersection with a universal bitset should only update |
788 // the representations. | 731 // the representations. |
789 if (type1->SemanticIs(type2->unhandle())) { | 732 if (type1->SemanticIs(type2)) { |
790 type2 = Any(region); | 733 type2 = Any(); |
791 } else if (type2->SemanticIs(type1->unhandle())) { | 734 } else if (type2->SemanticIs(type1)) { |
792 type1 = Any(region); | 735 type1 = Any(); |
793 } | 736 } |
794 | 737 |
795 bitset bits = | 738 bitset bits = |
796 SEMANTIC(type1->BitsetGlb() & type2->BitsetGlb()) | representation; | 739 SEMANTIC(type1->BitsetGlb() & type2->BitsetGlb()) | representation; |
797 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1; | 740 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1; |
798 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1; | 741 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1; |
799 if (!AddIsSafe(size1, size2)) return Any(region); | 742 if (!AddIsSafe(size1, size2)) return Any(); |
800 int size = size1 + size2; | 743 int size = size1 + size2; |
801 if (!AddIsSafe(size, 2)) return Any(region); | 744 if (!AddIsSafe(size, 2)) return Any(); |
802 size += 2; | 745 size += 2; |
803 UnionHandle result = UnionType::New(size, region); | 746 Type* result_type = UnionType::New(size, zone); |
| 747 UnionType* result = result_type->AsUnion(); |
804 size = 0; | 748 size = 0; |
805 | 749 |
806 // Deal with bitsets. | 750 // Deal with bitsets. |
807 result->Set(size++, BitsetType::New(bits, region)); | 751 result->Set(size++, BitsetType::New(bits)); |
808 | 752 |
809 Limits lims = Limits::Empty(); | 753 RangeType::Limits lims = RangeType::Limits::Empty(); |
810 size = IntersectAux(type1, type2, result, size, &lims, region); | 754 size = IntersectAux(type1, type2, result, size, &lims, zone); |
811 | 755 |
812 // If the range is not empty, then insert it into the union and | 756 // If the range is not empty, then insert it into the union and |
813 // remove the number bits from the bitset. | 757 // remove the number bits from the bitset. |
814 if (!lims.IsEmpty()) { | 758 if (!lims.IsEmpty()) { |
815 size = UpdateRange(RangeType::New(lims, representation, region), result, | 759 size = UpdateRange(RangeType::New(lims, representation, zone), result, size, |
816 size, region); | 760 zone); |
817 | 761 |
818 // Remove the number bits. | 762 // Remove the number bits. |
819 bitset number_bits = BitsetType::NumberBits(bits); | 763 bitset number_bits = BitsetType::NumberBits(bits); |
820 bits &= ~number_bits; | 764 bits &= ~number_bits; |
821 result->Set(0, BitsetType::New(bits, region)); | 765 result->Set(0, BitsetType::New(bits)); |
822 } | 766 } |
823 return NormalizeUnion(result, size, region); | 767 return NormalizeUnion(result_type, size, zone); |
824 } | 768 } |
825 | 769 |
826 | 770 int Type::UpdateRange(Type* range, UnionType* result, int size, Zone* zone) { |
827 template<class Config> | |
828 int TypeImpl<Config>::UpdateRange( | |
829 RangeHandle range, UnionHandle result, int size, Region* region) { | |
830 if (size == 1) { | 771 if (size == 1) { |
831 result->Set(size++, range); | 772 result->Set(size++, range); |
832 } else { | 773 } else { |
833 // Make space for the range. | 774 // Make space for the range. |
834 result->Set(size++, result->Get(1)); | 775 result->Set(size++, result->Get(1)); |
835 result->Set(1, range); | 776 result->Set(1, range); |
836 } | 777 } |
837 | 778 |
838 // Remove any components that just got subsumed. | 779 // Remove any components that just got subsumed. |
839 for (int i = 2; i < size; ) { | 780 for (int i = 2; i < size; ) { |
840 if (result->Get(i)->SemanticIs(range->unhandle())) { | 781 if (result->Get(i)->SemanticIs(range)) { |
841 result->Set(i, result->Get(--size)); | 782 result->Set(i, result->Get(--size)); |
842 } else { | 783 } else { |
843 ++i; | 784 ++i; |
844 } | 785 } |
845 } | 786 } |
846 return size; | 787 return size; |
847 } | 788 } |
848 | 789 |
849 | 790 RangeType::Limits Type::ToLimits(bitset bits, Zone* zone) { |
850 template <class Config> | |
851 typename TypeImpl<Config>::Limits TypeImpl<Config>::ToLimits(bitset bits, | |
852 Region* region) { | |
853 bitset number_bits = BitsetType::NumberBits(bits); | 791 bitset number_bits = BitsetType::NumberBits(bits); |
854 | 792 |
855 if (number_bits == BitsetType::kNone) { | 793 if (number_bits == BitsetType::kNone) { |
856 return Limits::Empty(); | 794 return RangeType::Limits::Empty(); |
857 } | 795 } |
858 | 796 |
859 return Limits(BitsetType::Min(number_bits), BitsetType::Max(number_bits)); | 797 return RangeType::Limits(BitsetType::Min(number_bits), |
| 798 BitsetType::Max(number_bits)); |
860 } | 799 } |
861 | 800 |
862 | 801 RangeType::Limits Type::IntersectRangeAndBitset(Type* range, Type* bitset, |
863 template <class Config> | 802 Zone* zone) { |
864 typename TypeImpl<Config>::Limits TypeImpl<Config>::IntersectRangeAndBitset( | 803 RangeType::Limits range_lims(range->AsRange()); |
865 TypeHandle range, TypeHandle bitset, Region* region) { | 804 RangeType::Limits bitset_lims = ToLimits(bitset->AsBitset(), zone); |
866 Limits range_lims(range->AsRange()); | 805 return RangeType::Limits::Intersect(range_lims, bitset_lims); |
867 Limits bitset_lims = ToLimits(bitset->AsBitset(), region); | |
868 return Limits::Intersect(range_lims, bitset_lims); | |
869 } | 806 } |
870 | 807 |
871 | 808 int Type::IntersectAux(Type* lhs, Type* rhs, UnionType* result, int size, |
872 template <class Config> | 809 RangeType::Limits* lims, Zone* zone) { |
873 int TypeImpl<Config>::IntersectAux(TypeHandle lhs, TypeHandle rhs, | |
874 UnionHandle result, int size, Limits* lims, | |
875 Region* region) { | |
876 if (lhs->IsUnion()) { | 810 if (lhs->IsUnion()) { |
877 for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) { | 811 for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) { |
878 size = | 812 size = |
879 IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, lims, region); | 813 IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, lims, zone); |
880 } | 814 } |
881 return size; | 815 return size; |
882 } | 816 } |
883 if (rhs->IsUnion()) { | 817 if (rhs->IsUnion()) { |
884 for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) { | 818 for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) { |
885 size = | 819 size = |
886 IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, region); | 820 IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, zone); |
887 } | 821 } |
888 return size; | 822 return size; |
889 } | 823 } |
890 | 824 |
891 if (!BitsetType::SemanticIsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) { | 825 if (!BitsetType::SemanticIsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) { |
892 return size; | 826 return size; |
893 } | 827 } |
894 | 828 |
895 if (lhs->IsRange()) { | 829 if (lhs->IsRange()) { |
896 if (rhs->IsBitset()) { | 830 if (rhs->IsBitset()) { |
897 Limits lim = IntersectRangeAndBitset(lhs, rhs, region); | 831 RangeType::Limits lim = IntersectRangeAndBitset(lhs, rhs, zone); |
898 | 832 |
899 if (!lim.IsEmpty()) { | 833 if (!lim.IsEmpty()) { |
900 *lims = Limits::Union(lim, *lims); | 834 *lims = RangeType::Limits::Union(lim, *lims); |
901 } | 835 } |
902 return size; | 836 return size; |
903 } | 837 } |
904 if (rhs->IsClass()) { | 838 if (rhs->IsClass()) { |
905 *lims = Limits::Union(Limits(lhs->AsRange()), *lims); | 839 *lims = |
| 840 RangeType::Limits::Union(RangeType::Limits(lhs->AsRange()), *lims); |
906 } | 841 } |
907 if (rhs->IsConstant() && Contains(lhs->AsRange(), rhs->AsConstant())) { | 842 if (rhs->IsConstant() && Contains(lhs->AsRange(), rhs->AsConstant())) { |
908 return AddToUnion(rhs, result, size, region); | 843 return AddToUnion(rhs, result, size, zone); |
909 } | 844 } |
910 if (rhs->IsRange()) { | 845 if (rhs->IsRange()) { |
911 Limits lim = Limits::Intersect( | 846 RangeType::Limits lim = RangeType::Limits::Intersect( |
912 Limits(lhs->AsRange()), Limits(rhs->AsRange())); | 847 RangeType::Limits(lhs->AsRange()), RangeType::Limits(rhs->AsRange())); |
913 if (!lim.IsEmpty()) { | 848 if (!lim.IsEmpty()) { |
914 *lims = Limits::Union(lim, *lims); | 849 *lims = RangeType::Limits::Union(lim, *lims); |
915 } | 850 } |
916 } | 851 } |
917 return size; | 852 return size; |
918 } | 853 } |
919 if (rhs->IsRange()) { | 854 if (rhs->IsRange()) { |
920 // This case is handled symmetrically above. | 855 // This case is handled symmetrically above. |
921 return IntersectAux(rhs, lhs, result, size, lims, region); | 856 return IntersectAux(rhs, lhs, result, size, lims, zone); |
922 } | 857 } |
923 if (lhs->IsBitset() || rhs->IsBitset()) { | 858 if (lhs->IsBitset() || rhs->IsBitset()) { |
924 return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, region); | 859 return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, zone); |
925 } | 860 } |
926 if (lhs->IsClass() != rhs->IsClass()) { | 861 if (lhs->IsClass() != rhs->IsClass()) { |
927 return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, region); | 862 return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, zone); |
928 } | 863 } |
929 if (lhs->SimplyEquals(rhs->unhandle())) { | 864 if (lhs->SimplyEquals(rhs)) { |
930 return AddToUnion(lhs, result, size, region); | 865 return AddToUnion(lhs, result, size, zone); |
931 } | 866 } |
932 return size; | 867 return size; |
933 } | 868 } |
934 | 869 |
935 | 870 |
936 // Make sure that we produce a well-formed range and bitset: | 871 // Make sure that we produce a well-formed range and bitset: |
937 // If the range is non-empty, the number bits in the bitset should be | 872 // If the range is non-empty, the number bits in the bitset should be |
938 // clear. Moreover, if we have a canonical range (such as Signed32), | 873 // clear. Moreover, if we have a canonical range (such as Signed32), |
939 // we want to produce a bitset rather than a range. | 874 // we want to produce a bitset rather than a range. |
940 template <class Config> | 875 Type* Type::NormalizeRangeAndBitset(Type* range, bitset* bits, Zone* zone) { |
941 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeRangeAndBitset( | |
942 RangeHandle range, bitset* bits, Region* region) { | |
943 // Fast path: If the bitset does not mention numbers, we can just keep the | 876 // Fast path: If the bitset does not mention numbers, we can just keep the |
944 // range. | 877 // range. |
945 bitset number_bits = BitsetType::NumberBits(*bits); | 878 bitset number_bits = BitsetType::NumberBits(*bits); |
946 if (number_bits == 0) { | 879 if (number_bits == 0) { |
947 return range; | 880 return range; |
948 } | 881 } |
949 | 882 |
950 // If the range is semantically contained within the bitset, return None and | 883 // If the range is semantically contained within the bitset, return None and |
951 // leave the bitset untouched. | 884 // leave the bitset untouched. |
952 bitset range_lub = SEMANTIC(range->BitsetLub()); | 885 bitset range_lub = SEMANTIC(range->BitsetLub()); |
953 if (BitsetType::Is(range_lub, *bits)) { | 886 if (BitsetType::Is(range_lub, *bits)) { |
954 return None(region); | 887 return None(); |
955 } | 888 } |
956 | 889 |
957 // Slow path: reconcile the bitset range and the range. | 890 // Slow path: reconcile the bitset range and the range. |
958 double bitset_min = BitsetType::Min(number_bits); | 891 double bitset_min = BitsetType::Min(number_bits); |
959 double bitset_max = BitsetType::Max(number_bits); | 892 double bitset_max = BitsetType::Max(number_bits); |
960 | 893 |
961 double range_min = range->Min(); | 894 double range_min = range->Min(); |
962 double range_max = range->Max(); | 895 double range_max = range->Max(); |
963 | 896 |
964 // Remove the number bits from the bitset, they would just confuse us now. | 897 // Remove the number bits from the bitset, they would just confuse us now. |
965 // NOTE: bits contains OtherNumber iff bits contains PlainNumber, in which | 898 // NOTE: bits contains OtherNumber iff bits contains PlainNumber, in which |
966 // case we already returned after the subtype check above. | 899 // case we already returned after the subtype check above. |
967 *bits &= ~number_bits; | 900 *bits &= ~number_bits; |
968 | 901 |
969 if (range_min <= bitset_min && range_max >= bitset_max) { | 902 if (range_min <= bitset_min && range_max >= bitset_max) { |
970 // Bitset is contained within the range, just return the range. | 903 // Bitset is contained within the range, just return the range. |
971 return range; | 904 return range; |
972 } | 905 } |
973 | 906 |
974 if (bitset_min < range_min) { | 907 if (bitset_min < range_min) { |
975 range_min = bitset_min; | 908 range_min = bitset_min; |
976 } | 909 } |
977 if (bitset_max > range_max) { | 910 if (bitset_max > range_max) { |
978 range_max = bitset_max; | 911 range_max = bitset_max; |
979 } | 912 } |
980 return RangeType::New(range_min, range_max, | 913 return RangeType::New(range_min, range_max, BitsetType::kNone, zone); |
981 BitsetType::New(BitsetType::kNone, region), region); | |
982 } | 914 } |
983 | 915 |
984 | 916 Type* Type::Union(Type* type1, Type* type2, Zone* zone) { |
985 template<class Config> | |
986 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union( | |
987 TypeHandle type1, TypeHandle type2, Region* region) { | |
988 // Fast case: bit sets. | 917 // Fast case: bit sets. |
989 if (type1->IsBitset() && type2->IsBitset()) { | 918 if (type1->IsBitset() && type2->IsBitset()) { |
990 return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region); | 919 return BitsetType::New(type1->AsBitset() | type2->AsBitset()); |
991 } | 920 } |
992 | 921 |
993 // Fast case: top or bottom types. | 922 // Fast case: top or bottom types. |
994 if (type1->IsAny() || type2->IsNone()) return type1; | 923 if (type1->IsAny() || type2->IsNone()) return type1; |
995 if (type2->IsAny() || type1->IsNone()) return type2; | 924 if (type2->IsAny() || type1->IsNone()) return type2; |
996 | 925 |
997 // Semi-fast case. | 926 // Semi-fast case. |
998 if (type1->Is(type2)) return type2; | 927 if (type1->Is(type2)) return type2; |
999 if (type2->Is(type1)) return type1; | 928 if (type2->Is(type1)) return type1; |
1000 | 929 |
1001 // Figure out the representation of the result. | 930 // Figure out the representation of the result. |
1002 // The rest of the method should not change this representation and | 931 // The rest of the method should not change this representation and |
1003 // it should not make any decisions based on representations (i.e., | 932 // it should not make any decisions based on representations (i.e., |
1004 // it should only use the semantic part of types). | 933 // it should only use the semantic part of types). |
1005 const bitset representation = | 934 const bitset representation = |
1006 type1->Representation() | type2->Representation(); | 935 type1->Representation() | type2->Representation(); |
1007 | 936 |
1008 // Slow case: create union. | 937 // Slow case: create union. |
1009 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1; | 938 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1; |
1010 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1; | 939 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1; |
1011 if (!AddIsSafe(size1, size2)) return Any(region); | 940 if (!AddIsSafe(size1, size2)) return Any(); |
1012 int size = size1 + size2; | 941 int size = size1 + size2; |
1013 if (!AddIsSafe(size, 2)) return Any(region); | 942 if (!AddIsSafe(size, 2)) return Any(); |
1014 size += 2; | 943 size += 2; |
1015 UnionHandle result = UnionType::New(size, region); | 944 Type* result_type = UnionType::New(size, zone); |
| 945 UnionType* result = result_type->AsUnion(); |
1016 size = 0; | 946 size = 0; |
1017 | 947 |
1018 // Compute the new bitset. | 948 // Compute the new bitset. |
1019 bitset new_bitset = SEMANTIC(type1->BitsetGlb() | type2->BitsetGlb()); | 949 bitset new_bitset = SEMANTIC(type1->BitsetGlb() | type2->BitsetGlb()); |
1020 | 950 |
1021 // Deal with ranges. | 951 // Deal with ranges. |
1022 TypeHandle range = None(region); | 952 Type* range = None(); |
1023 RangeType* range1 = type1->GetRange(); | 953 Type* range1 = type1->GetRange(); |
1024 RangeType* range2 = type2->GetRange(); | 954 Type* range2 = type2->GetRange(); |
1025 if (range1 != NULL && range2 != NULL) { | 955 if (range1 != NULL && range2 != NULL) { |
1026 Limits lims = Limits::Union(Limits(range1), Limits(range2)); | 956 RangeType::Limits lims = |
1027 RangeHandle union_range = RangeType::New(lims, representation, region); | 957 RangeType::Limits::Union(RangeType::Limits(range1->AsRange()), |
1028 range = NormalizeRangeAndBitset(union_range, &new_bitset, region); | 958 RangeType::Limits(range2->AsRange())); |
| 959 Type* union_range = RangeType::New(lims, representation, zone); |
| 960 range = NormalizeRangeAndBitset(union_range, &new_bitset, zone); |
1029 } else if (range1 != NULL) { | 961 } else if (range1 != NULL) { |
1030 range = NormalizeRangeAndBitset(handle(range1), &new_bitset, region); | 962 range = NormalizeRangeAndBitset(range1, &new_bitset, zone); |
1031 } else if (range2 != NULL) { | 963 } else if (range2 != NULL) { |
1032 range = NormalizeRangeAndBitset(handle(range2), &new_bitset, region); | 964 range = NormalizeRangeAndBitset(range2, &new_bitset, zone); |
1033 } | 965 } |
1034 new_bitset = SEMANTIC(new_bitset) | representation; | 966 new_bitset = SEMANTIC(new_bitset) | representation; |
1035 TypeHandle bits = BitsetType::New(new_bitset, region); | 967 Type* bits = BitsetType::New(new_bitset); |
1036 result->Set(size++, bits); | 968 result->Set(size++, bits); |
1037 if (!range->IsNone()) result->Set(size++, range); | 969 if (!range->IsNone()) result->Set(size++, range); |
1038 | 970 |
1039 size = AddToUnion(type1, result, size, region); | 971 size = AddToUnion(type1, result, size, zone); |
1040 size = AddToUnion(type2, result, size, region); | 972 size = AddToUnion(type2, result, size, zone); |
1041 return NormalizeUnion(result, size, region); | 973 return NormalizeUnion(result_type, size, zone); |
1042 } | 974 } |
1043 | 975 |
1044 | 976 |
1045 // Add [type] to [result] unless [type] is bitset, range, or already subsumed. | 977 // Add [type] to [result] unless [type] is bitset, range, or already subsumed. |
1046 // Return new size of [result]. | 978 // Return new size of [result]. |
1047 template<class Config> | 979 int Type::AddToUnion(Type* type, UnionType* result, int size, Zone* zone) { |
1048 int TypeImpl<Config>::AddToUnion( | |
1049 TypeHandle type, UnionHandle result, int size, Region* region) { | |
1050 if (type->IsBitset() || type->IsRange()) return size; | 980 if (type->IsBitset() || type->IsRange()) return size; |
1051 if (type->IsUnion()) { | 981 if (type->IsUnion()) { |
1052 for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) { | 982 for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) { |
1053 size = AddToUnion(type->AsUnion()->Get(i), result, size, region); | 983 size = AddToUnion(type->AsUnion()->Get(i), result, size, zone); |
1054 } | 984 } |
1055 return size; | 985 return size; |
1056 } | 986 } |
1057 for (int i = 0; i < size; ++i) { | 987 for (int i = 0; i < size; ++i) { |
1058 if (type->SemanticIs(result->Get(i)->unhandle())) return size; | 988 if (type->SemanticIs(result->Get(i))) return size; |
1059 } | 989 } |
1060 result->Set(size++, type); | 990 result->Set(size++, type); |
1061 return size; | 991 return size; |
1062 } | 992 } |
1063 | 993 |
1064 | 994 Type* Type::NormalizeUnion(Type* union_type, int size, Zone* zone) { |
1065 template <class Config> | 995 UnionType* unioned = union_type->AsUnion(); |
1066 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeUnion( | |
1067 UnionHandle unioned, int size, Region* region) { | |
1068 DCHECK(size >= 1); | 996 DCHECK(size >= 1); |
1069 DCHECK(unioned->Get(0)->IsBitset()); | 997 DCHECK(unioned->Get(0)->IsBitset()); |
1070 // If the union has just one element, return it. | 998 // If the union has just one element, return it. |
1071 if (size == 1) { | 999 if (size == 1) { |
1072 return unioned->Get(0); | 1000 return unioned->Get(0); |
1073 } | 1001 } |
1074 bitset bits = unioned->Get(0)->AsBitset(); | 1002 bitset bits = unioned->Get(0)->AsBitset(); |
1075 // If the union only consists of a range, we can get rid of the union. | 1003 // If the union only consists of a range, we can get rid of the union. |
1076 if (size == 2 && SEMANTIC(bits) == BitsetType::kNone) { | 1004 if (size == 2 && SEMANTIC(bits) == BitsetType::kNone) { |
1077 bitset representation = REPRESENTATION(bits); | 1005 bitset representation = REPRESENTATION(bits); |
1078 if (representation == unioned->Get(1)->Representation()) { | 1006 if (representation == unioned->Get(1)->Representation()) { |
1079 return unioned->Get(1); | 1007 return unioned->Get(1); |
1080 } | 1008 } |
1081 if (unioned->Get(1)->IsRange()) { | 1009 if (unioned->Get(1)->IsRange()) { |
1082 return RangeType::New(unioned->Get(1)->AsRange()->Min(), | 1010 return RangeType::New(unioned->Get(1)->AsRange()->Min(), |
1083 unioned->Get(1)->AsRange()->Max(), unioned->Get(0), | 1011 unioned->Get(1)->AsRange()->Max(), |
1084 region); | 1012 unioned->Get(0)->AsBitset(), zone); |
1085 } | 1013 } |
1086 } | 1014 } |
1087 unioned->Shrink(size); | 1015 unioned->Shrink(size); |
1088 SLOW_DCHECK(unioned->Wellformed()); | 1016 SLOW_DCHECK(unioned->Wellformed()); |
1089 return unioned; | 1017 return union_type; |
1090 } | 1018 } |
1091 | 1019 |
1092 | 1020 |
1093 // ----------------------------------------------------------------------------- | 1021 // ----------------------------------------------------------------------------- |
1094 // Component extraction | 1022 // Component extraction |
1095 | 1023 |
1096 // static | 1024 // static |
1097 template <class Config> | 1025 Type* Type::Representation(Type* t, Zone* zone) { |
1098 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Representation( | 1026 return BitsetType::New(t->Representation()); |
1099 TypeHandle t, Region* region) { | |
1100 return BitsetType::New(t->Representation(), region); | |
1101 } | 1027 } |
1102 | 1028 |
1103 | 1029 |
1104 // static | 1030 // static |
1105 template <class Config> | 1031 Type* Type::Semantic(Type* t, Zone* zone) { |
1106 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Semantic( | 1032 return Intersect(t, BitsetType::New(BitsetType::kSemantic), zone); |
1107 TypeHandle t, Region* region) { | |
1108 return Intersect(t, BitsetType::New(BitsetType::kSemantic, region), region); | |
1109 } | 1033 } |
1110 | 1034 |
1111 | 1035 |
1112 // ----------------------------------------------------------------------------- | 1036 // ----------------------------------------------------------------------------- |
1113 // Iteration. | 1037 // Iteration. |
1114 | 1038 |
1115 template<class Config> | 1039 int Type::NumClasses() { |
1116 int TypeImpl<Config>::NumClasses() { | |
1117 DisallowHeapAllocation no_allocation; | 1040 DisallowHeapAllocation no_allocation; |
1118 if (this->IsClass()) { | 1041 if (this->IsClass()) { |
1119 return 1; | 1042 return 1; |
1120 } else if (this->IsUnion()) { | 1043 } else if (this->IsUnion()) { |
1121 int result = 0; | 1044 int result = 0; |
1122 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { | 1045 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { |
1123 if (this->AsUnion()->Get(i)->IsClass()) ++result; | 1046 if (this->AsUnion()->Get(i)->IsClass()) ++result; |
1124 } | 1047 } |
1125 return result; | 1048 return result; |
1126 } else { | 1049 } else { |
1127 return 0; | 1050 return 0; |
1128 } | 1051 } |
1129 } | 1052 } |
1130 | 1053 |
1131 | 1054 int Type::NumConstants() { |
1132 template<class Config> | |
1133 int TypeImpl<Config>::NumConstants() { | |
1134 DisallowHeapAllocation no_allocation; | 1055 DisallowHeapAllocation no_allocation; |
1135 if (this->IsConstant()) { | 1056 if (this->IsConstant()) { |
1136 return 1; | 1057 return 1; |
1137 } else if (this->IsUnion()) { | 1058 } else if (this->IsUnion()) { |
1138 int result = 0; | 1059 int result = 0; |
1139 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { | 1060 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { |
1140 if (this->AsUnion()->Get(i)->IsConstant()) ++result; | 1061 if (this->AsUnion()->Get(i)->IsConstant()) ++result; |
1141 } | 1062 } |
1142 return result; | 1063 return result; |
1143 } else { | 1064 } else { |
1144 return 0; | 1065 return 0; |
1145 } | 1066 } |
1146 } | 1067 } |
1147 | 1068 |
1148 | 1069 template <class T> |
1149 template<class Config> template<class T> | 1070 Type* Type::Iterator<T>::get_type() { |
1150 typename TypeImpl<Config>::TypeHandle | |
1151 TypeImpl<Config>::Iterator<T>::get_type() { | |
1152 DCHECK(!Done()); | 1071 DCHECK(!Done()); |
1153 return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_; | 1072 return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_; |
1154 } | 1073 } |
1155 | 1074 |
1156 | 1075 |
1157 // C++ cannot specialise nested templates, so we have to go through this | 1076 // C++ cannot specialise nested templates, so we have to go through this |
1158 // contortion with an auxiliary template to simulate it. | 1077 // contortion with an auxiliary template to simulate it. |
1159 template<class Config, class T> | 1078 template <class T> |
1160 struct TypeImplIteratorAux { | 1079 struct TypeImplIteratorAux { |
1161 static bool matches(typename TypeImpl<Config>::TypeHandle type); | 1080 static bool matches(Type* type); |
1162 static i::Handle<T> current(typename TypeImpl<Config>::TypeHandle type); | 1081 static i::Handle<T> current(Type* type); |
1163 }; | 1082 }; |
1164 | 1083 |
1165 template<class Config> | 1084 template <> |
1166 struct TypeImplIteratorAux<Config, i::Map> { | 1085 struct TypeImplIteratorAux<i::Map> { |
1167 static bool matches(typename TypeImpl<Config>::TypeHandle type) { | 1086 static bool matches(Type* type) { return type->IsClass(); } |
1168 return type->IsClass(); | 1087 static i::Handle<i::Map> current(Type* type) { |
1169 } | |
1170 static i::Handle<i::Map> current(typename TypeImpl<Config>::TypeHandle type) { | |
1171 return type->AsClass()->Map(); | 1088 return type->AsClass()->Map(); |
1172 } | 1089 } |
1173 }; | 1090 }; |
1174 | 1091 |
1175 template<class Config> | 1092 template <> |
1176 struct TypeImplIteratorAux<Config, i::Object> { | 1093 struct TypeImplIteratorAux<i::Object> { |
1177 static bool matches(typename TypeImpl<Config>::TypeHandle type) { | 1094 static bool matches(Type* type) { return type->IsConstant(); } |
1178 return type->IsConstant(); | 1095 static i::Handle<i::Object> current(Type* type) { |
1179 } | |
1180 static i::Handle<i::Object> current( | |
1181 typename TypeImpl<Config>::TypeHandle type) { | |
1182 return type->AsConstant()->Value(); | 1096 return type->AsConstant()->Value(); |
1183 } | 1097 } |
1184 }; | 1098 }; |
1185 | 1099 |
1186 template<class Config> template<class T> | 1100 template <class T> |
1187 bool TypeImpl<Config>::Iterator<T>::matches(TypeHandle type) { | 1101 bool Type::Iterator<T>::matches(Type* type) { |
1188 return TypeImplIteratorAux<Config, T>::matches(type); | 1102 return TypeImplIteratorAux<T>::matches(type); |
1189 } | 1103 } |
1190 | 1104 |
1191 template<class Config> template<class T> | 1105 template <class T> |
1192 i::Handle<T> TypeImpl<Config>::Iterator<T>::Current() { | 1106 i::Handle<T> Type::Iterator<T>::Current() { |
1193 return TypeImplIteratorAux<Config, T>::current(get_type()); | 1107 return TypeImplIteratorAux<T>::current(get_type()); |
1194 } | 1108 } |
1195 | 1109 |
1196 | 1110 template <class T> |
1197 template<class Config> template<class T> | 1111 void Type::Iterator<T>::Advance() { |
1198 void TypeImpl<Config>::Iterator<T>::Advance() { | |
1199 DisallowHeapAllocation no_allocation; | 1112 DisallowHeapAllocation no_allocation; |
1200 ++index_; | 1113 ++index_; |
1201 if (type_->IsUnion()) { | 1114 if (type_->IsUnion()) { |
1202 for (int n = type_->AsUnion()->Length(); index_ < n; ++index_) { | 1115 for (int n = type_->AsUnion()->Length(); index_ < n; ++index_) { |
1203 if (matches(type_->AsUnion()->Get(index_))) return; | 1116 if (matches(type_->AsUnion()->Get(index_))) return; |
1204 } | 1117 } |
1205 } else if (index_ == 0 && matches(type_)) { | 1118 } else if (index_ == 0 && matches(type_)) { |
1206 return; | 1119 return; |
1207 } | 1120 } |
1208 index_ = -1; | 1121 index_ = -1; |
1209 } | 1122 } |
1210 | 1123 |
1211 | 1124 |
1212 // ----------------------------------------------------------------------------- | 1125 // ----------------------------------------------------------------------------- |
1213 // Printing. | 1126 // Printing. |
1214 | 1127 |
1215 template<class Config> | 1128 const char* BitsetType::Name(bitset bits) { |
1216 const char* TypeImpl<Config>::BitsetType::Name(bitset bits) { | |
1217 switch (bits) { | 1129 switch (bits) { |
1218 case REPRESENTATION(kAny): return "Any"; | 1130 case REPRESENTATION(kAny): return "Any"; |
1219 #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \ | 1131 #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \ |
1220 case REPRESENTATION(k##type): return #type; | 1132 case REPRESENTATION(k##type): return #type; |
1221 REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE) | 1133 REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE) |
1222 #undef RETURN_NAMED_REPRESENTATION_TYPE | 1134 #undef RETURN_NAMED_REPRESENTATION_TYPE |
1223 | 1135 |
1224 #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \ | 1136 #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \ |
1225 case SEMANTIC(k##type): return #type; | 1137 case SEMANTIC(k##type): return #type; |
1226 SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE) | 1138 SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE) |
1227 INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE) | 1139 INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE) |
1228 #undef RETURN_NAMED_SEMANTIC_TYPE | 1140 #undef RETURN_NAMED_SEMANTIC_TYPE |
1229 | 1141 |
1230 default: | 1142 default: |
1231 return NULL; | 1143 return NULL; |
1232 } | 1144 } |
1233 } | 1145 } |
1234 | 1146 |
1235 | 1147 void BitsetType::Print(std::ostream& os, // NOLINT |
1236 template <class Config> | 1148 bitset bits) { |
1237 void TypeImpl<Config>::BitsetType::Print(std::ostream& os, // NOLINT | |
1238 bitset bits) { | |
1239 DisallowHeapAllocation no_allocation; | 1149 DisallowHeapAllocation no_allocation; |
1240 const char* name = Name(bits); | 1150 const char* name = Name(bits); |
1241 if (name != NULL) { | 1151 if (name != NULL) { |
1242 os << name; | 1152 os << name; |
1243 return; | 1153 return; |
1244 } | 1154 } |
1245 | 1155 |
1246 // clang-format off | 1156 // clang-format off |
1247 static const bitset named_bitsets[] = { | 1157 static const bitset named_bitsets[] = { |
1248 #define BITSET_CONSTANT(type, value) REPRESENTATION(k##type), | 1158 #define BITSET_CONSTANT(type, value) REPRESENTATION(k##type), |
(...skipping 15 matching lines...) Expand all Loading... |
1264 if (!is_first) os << " | "; | 1174 if (!is_first) os << " | "; |
1265 is_first = false; | 1175 is_first = false; |
1266 os << Name(subset); | 1176 os << Name(subset); |
1267 bits -= subset; | 1177 bits -= subset; |
1268 } | 1178 } |
1269 } | 1179 } |
1270 DCHECK(bits == 0); | 1180 DCHECK(bits == 0); |
1271 os << ")"; | 1181 os << ")"; |
1272 } | 1182 } |
1273 | 1183 |
1274 | 1184 void Type::PrintTo(std::ostream& os, PrintDimension dim) { |
1275 template <class Config> | |
1276 void TypeImpl<Config>::PrintTo(std::ostream& os, PrintDimension dim) { | |
1277 DisallowHeapAllocation no_allocation; | 1185 DisallowHeapAllocation no_allocation; |
1278 if (dim != REPRESENTATION_DIM) { | 1186 if (dim != REPRESENTATION_DIM) { |
1279 if (this->IsBitset()) { | 1187 if (this->IsBitset()) { |
1280 BitsetType::Print(os, SEMANTIC(this->AsBitset())); | 1188 BitsetType::Print(os, SEMANTIC(this->AsBitset())); |
1281 } else if (this->IsClass()) { | 1189 } else if (this->IsClass()) { |
1282 os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < "; | 1190 os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < "; |
1283 BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim); | 1191 BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim); |
1284 os << ")"; | 1192 os << ")"; |
1285 } else if (this->IsConstant()) { | 1193 } else if (this->IsConstant()) { |
1286 os << "Constant(" << Brief(*this->AsConstant()->Value()) << ")"; | 1194 os << "Constant(" << Brief(*this->AsConstant()->Value()) << ")"; |
1287 } else if (this->IsRange()) { | 1195 } else if (this->IsRange()) { |
1288 std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed); | 1196 std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed); |
1289 std::streamsize saved_precision = os.precision(0); | 1197 std::streamsize saved_precision = os.precision(0); |
1290 os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max() | 1198 os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max() |
1291 << ")"; | 1199 << ")"; |
1292 os.flags(saved_flags); | 1200 os.flags(saved_flags); |
1293 os.precision(saved_precision); | 1201 os.precision(saved_precision); |
1294 } else if (this->IsContext()) { | 1202 } else if (this->IsContext()) { |
1295 os << "Context("; | 1203 os << "Context("; |
1296 this->AsContext()->Outer()->PrintTo(os, dim); | 1204 this->AsContext()->Outer()->PrintTo(os, dim); |
1297 os << ")"; | 1205 os << ")"; |
1298 } else if (this->IsUnion()) { | 1206 } else if (this->IsUnion()) { |
1299 os << "("; | 1207 os << "("; |
1300 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { | 1208 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { |
1301 TypeHandle type_i = this->AsUnion()->Get(i); | 1209 Type* type_i = this->AsUnion()->Get(i); |
1302 if (i > 0) os << " | "; | 1210 if (i > 0) os << " | "; |
1303 type_i->PrintTo(os, dim); | 1211 type_i->PrintTo(os, dim); |
1304 } | 1212 } |
1305 os << ")"; | 1213 os << ")"; |
1306 } else if (this->IsArray()) { | 1214 } else if (this->IsArray()) { |
1307 os << "Array("; | 1215 os << "Array("; |
1308 AsArray()->Element()->PrintTo(os, dim); | 1216 AsArray()->Element()->PrintTo(os, dim); |
1309 os << ")"; | 1217 os << ")"; |
1310 } else if (this->IsFunction()) { | 1218 } else if (this->IsFunction()) { |
1311 if (!this->AsFunction()->Receiver()->IsAny()) { | 1219 if (!this->AsFunction()->Receiver()->IsAny()) { |
1312 this->AsFunction()->Receiver()->PrintTo(os, dim); | 1220 this->AsFunction()->Receiver()->PrintTo(os, dim); |
1313 os << "."; | 1221 os << "."; |
1314 } | 1222 } |
1315 os << "("; | 1223 os << "("; |
1316 for (int i = 0; i < this->AsFunction()->Arity(); ++i) { | 1224 for (int i = 0; i < this->AsFunction()->Arity(); ++i) { |
1317 if (i > 0) os << ", "; | 1225 if (i > 0) os << ", "; |
1318 this->AsFunction()->Parameter(i)->PrintTo(os, dim); | 1226 this->AsFunction()->Parameter(i)->PrintTo(os, dim); |
1319 } | 1227 } |
1320 os << ")->"; | 1228 os << ")->"; |
1321 this->AsFunction()->Result()->PrintTo(os, dim); | 1229 this->AsFunction()->Result()->PrintTo(os, dim); |
1322 } else if (this->IsTuple()) { | 1230 } else if (this->IsTuple()) { |
1323 os << "<"; | 1231 os << "<"; |
1324 for (int i = 0, n = this->AsTuple()->Arity(); i < n; ++i) { | 1232 for (int i = 0, n = this->AsTuple()->Arity(); i < n; ++i) { |
1325 TypeHandle type_i = this->AsTuple()->Element(i); | 1233 Type* type_i = this->AsTuple()->Element(i); |
1326 if (i > 0) os << ", "; | 1234 if (i > 0) os << ", "; |
1327 type_i->PrintTo(os, dim); | 1235 type_i->PrintTo(os, dim); |
1328 } | 1236 } |
1329 os << ">"; | 1237 os << ">"; |
1330 } else { | 1238 } else { |
1331 UNREACHABLE(); | 1239 UNREACHABLE(); |
1332 } | 1240 } |
1333 } | 1241 } |
1334 if (dim == BOTH_DIMS) os << "/"; | 1242 if (dim == BOTH_DIMS) os << "/"; |
1335 if (dim != SEMANTIC_DIM) { | 1243 if (dim != SEMANTIC_DIM) { |
1336 BitsetType::Print(os, REPRESENTATION(this->BitsetLub())); | 1244 BitsetType::Print(os, REPRESENTATION(this->BitsetLub())); |
1337 } | 1245 } |
1338 } | 1246 } |
1339 | 1247 |
1340 | 1248 |
1341 #ifdef DEBUG | 1249 #ifdef DEBUG |
1342 template <class Config> | 1250 void Type::Print() { |
1343 void TypeImpl<Config>::Print() { | |
1344 OFStream os(stdout); | 1251 OFStream os(stdout); |
1345 PrintTo(os); | 1252 PrintTo(os); |
1346 os << std::endl; | 1253 os << std::endl; |
1347 } | 1254 } |
1348 template <class Config> | 1255 void BitsetType::Print(bitset bits) { |
1349 void TypeImpl<Config>::BitsetType::Print(bitset bits) { | |
1350 OFStream os(stdout); | 1256 OFStream os(stdout); |
1351 Print(os, bits); | 1257 Print(os, bits); |
1352 os << std::endl; | 1258 os << std::endl; |
1353 } | 1259 } |
1354 #endif | 1260 #endif |
1355 | 1261 |
1356 // static | 1262 // static |
1357 FieldType* FieldType::None() { | 1263 FieldType* FieldType::None() { |
1358 return reinterpret_cast<FieldType*>(Smi::FromInt(0)); | 1264 return reinterpret_cast<FieldType*>(Smi::FromInt(0)); |
1359 } | 1265 } |
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1433 if (IsAny()) { | 1339 if (IsAny()) { |
1434 os << "Any"; | 1340 os << "Any"; |
1435 } else if (IsNone()) { | 1341 } else if (IsNone()) { |
1436 os << "None"; | 1342 os << "None"; |
1437 } else { | 1343 } else { |
1438 DCHECK(IsClass()); | 1344 DCHECK(IsClass()); |
1439 os << "Class(" << static_cast<void*>(*AsClass()) << ")"; | 1345 os << "Class(" << static_cast<void*>(*AsClass()) << ")"; |
1440 } | 1346 } |
1441 } | 1347 } |
1442 | 1348 |
| 1349 BitsetType::bitset BitsetType::SignedSmall() { |
| 1350 return i::SmiValuesAre31Bits() ? kSigned31 : kSigned32; |
| 1351 } |
| 1352 |
| 1353 BitsetType::bitset BitsetType::UnsignedSmall() { |
| 1354 return i::SmiValuesAre31Bits() ? kUnsigned30 : kUnsigned31; |
| 1355 } |
| 1356 |
| 1357 #define CONSTRUCT_SIMD_TYPE(NAME, Name, name, lane_count, lane_type) \ |
| 1358 Type* Type::Name(Isolate* isolate, Zone* zone) { \ |
| 1359 return Class(i::handle(isolate->heap()->name##_map()), zone); \ |
| 1360 } |
| 1361 SIMD128_TYPES(CONSTRUCT_SIMD_TYPE) |
| 1362 #undef CONSTRUCT_SIMD_TYPE |
| 1363 |
1443 // ----------------------------------------------------------------------------- | 1364 // ----------------------------------------------------------------------------- |
1444 // Instantiations. | 1365 // Instantiations. |
1445 | 1366 |
1446 template class TypeImpl<ZoneTypeConfig>; | 1367 template class Type::Iterator<i::Map>; |
1447 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Map>; | 1368 template class Type::Iterator<i::Object>; |
1448 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Object>; | |
1449 | 1369 |
1450 } // namespace internal | 1370 } // namespace internal |
1451 } // namespace v8 | 1371 } // namespace v8 |
OLD | NEW |