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 "src/types.h" | 5 #include "src/types.h" |
6 | 6 |
7 #include "src/ostreams.h" | 7 #include "src/ostreams.h" |
8 #include "src/types-inl.h" | 8 #include "src/types-inl.h" |
9 | 9 |
10 namespace v8 { | 10 namespace v8 { |
11 namespace internal { | 11 namespace internal { |
12 | 12 |
13 | 13 |
14 // NOTE: If code is marked as being a "shortcut", this means that removing | |
15 // the code won't affect the semantics of the surrounding function definition. | |
16 | |
17 | |
14 // ----------------------------------------------------------------------------- | 18 // ----------------------------------------------------------------------------- |
15 // Range-related custom order on doubles. | 19 // Range-related helper functions. |
16 // We want -0 to be less than +0. | |
17 | 20 |
18 static bool dle(double x, double y) { | 21 // The result may be invalid (max < min). |
19 return x <= y && (x != 0 || IsMinusZero(x) || !IsMinusZero(y)); | 22 template<class Config> |
23 typename TypeImpl<Config>::Limits TypeImpl<Config>::Intersect( | |
24 Limits lhs, Limits rhs) { | |
25 DisallowHeapAllocation no_allocation; | |
26 Limits result(lhs); | |
27 if (lhs.min->Number() < rhs.min->Number()) result.min = rhs.min; | |
28 if (lhs.max->Number() > rhs.max->Number()) result.max = rhs.max; | |
29 return result; | |
20 } | 30 } |
21 | 31 |
22 | 32 |
23 static bool deq(double x, double y) { | 33 template<class Config> |
24 return dle(x, y) && dle(y, x); | 34 typename TypeImpl<Config>::Limits TypeImpl<Config>::Union( |
35 Limits lhs, Limits rhs) { | |
36 DisallowHeapAllocation no_allocation; | |
37 Limits result(lhs); | |
38 if (lhs.min->Number() > rhs.min->Number()) result.min = rhs.min; | |
39 if (lhs.max->Number() < rhs.max->Number()) result.max = rhs.max; | |
40 return result; | |
41 } | |
42 | |
43 | |
44 template<class Config> | |
45 bool TypeImpl<Config>::Overlap( | |
46 typename TypeImpl<Config>::RangeType* lhs, | |
47 typename TypeImpl<Config>::RangeType* rhs) { | |
48 DisallowHeapAllocation no_allocation; | |
49 typename TypeImpl<Config>::Limits lim = Intersect(Limits(lhs), Limits(rhs)); | |
50 return lim.min->Number() <= lim.max->Number(); | |
51 } | |
52 | |
53 | |
54 template<class Config> | |
55 bool TypeImpl<Config>::Contains( | |
56 typename TypeImpl<Config>::RangeType* lhs, | |
57 typename TypeImpl<Config>::RangeType* rhs) { | |
58 DisallowHeapAllocation no_allocation; | |
59 return lhs->Min()->Number() <= rhs->Min()->Number() | |
60 && rhs->Max()->Number() <= lhs->Max()->Number(); | |
61 } | |
62 | |
63 | |
64 template<class Config> | |
65 bool TypeImpl<Config>::Contains( | |
66 typename TypeImpl<Config>::RangeType* range, i::Object* val) { | |
67 DisallowHeapAllocation no_allocation; | |
68 return IsInteger(val) | |
69 && range->Min()->Number() <= val->Number() | |
70 && val->Number() <= range->Max()->Number(); | |
71 } | |
72 | |
73 | |
74 // ----------------------------------------------------------------------------- | |
75 // Min and Max computation. | |
76 | |
77 template<class Config> | |
78 double TypeImpl<Config>::Min() { | |
79 DCHECK(this->Is(Number())); | |
80 if (this->IsBitset()) return BitsetType::Min(this->AsBitset()); | |
81 if (this->IsUnion()) { | |
82 double min = +V8_INFINITY; | |
83 for (int i = 0; i < this->AsUnion()->Length(); ++i) { | |
84 min = std::min(min, this->AsUnion()->Get(i)->Min()); | |
85 } | |
86 return min; | |
87 } | |
88 if (this->IsRange()) return this->AsRange()->Min()->Number(); | |
89 if (this->IsConstant()) return this->AsConstant()->Value()->Number(); | |
90 UNREACHABLE(); | |
91 return 0; | |
92 } | |
93 | |
94 | |
95 template<class Config> | |
96 double TypeImpl<Config>::Max() { | |
97 DCHECK(this->Is(Number())); | |
98 if (this->IsBitset()) return BitsetType::Max(this->AsBitset()); | |
99 if (this->IsUnion()) { | |
100 double max = -V8_INFINITY; | |
101 for (int i = 0; i < this->AsUnion()->Length(); ++i) { | |
102 max = std::max(max, this->AsUnion()->Get(i)->Max()); | |
103 } | |
104 return max; | |
105 } | |
106 if (this->IsRange()) return this->AsRange()->Max()->Number(); | |
107 if (this->IsConstant()) return this->AsConstant()->Value()->Number(); | |
108 UNREACHABLE(); | |
109 return 0; | |
25 } | 110 } |
26 | 111 |
27 | 112 |
28 // ----------------------------------------------------------------------------- | 113 // ----------------------------------------------------------------------------- |
29 // Glb and lub computation. | 114 // Glb and lub computation. |
30 | 115 |
116 | |
31 // The largest bitset subsumed by this type. | 117 // The largest bitset subsumed by this type. |
32 template<class Config> | 118 template<class Config> |
33 int TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) { | 119 int TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) { |
34 DisallowHeapAllocation no_allocation; | 120 DisallowHeapAllocation no_allocation; |
35 if (type->IsBitset()) { | 121 if (type->IsBitset()) { |
36 return type->AsBitset(); | 122 return type->AsBitset(); |
37 } else if (type->IsUnion()) { | 123 } else if (type->IsUnion()) { |
38 UnionHandle unioned = handle(type->AsUnion()); | 124 SLOW_DCHECK(type->AsUnion()->Wellformed()); |
39 DCHECK(unioned->Wellformed()); | 125 return type->AsUnion()->Get(0)->BitsetGlb(); // Shortcut. |
40 return unioned->Get(0)->BitsetGlb(); // Other BitsetGlb's are kNone anyway. | 126 // (The remaining BitsetGlb's are None anyway). |
41 } else { | 127 } else { |
42 return kNone; | 128 return kNone; |
43 } | 129 } |
44 } | 130 } |
45 | 131 |
46 | 132 |
47 // The smallest bitset subsuming this type. | 133 // The smallest bitset subsuming this type. |
48 template<class Config> | 134 template<class Config> |
49 int TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) { | 135 int TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) { |
50 DisallowHeapAllocation no_allocation; | 136 DisallowHeapAllocation no_allocation; |
51 if (type->IsBitset()) { | 137 if (type->IsBitset()) return type->AsBitset(); |
52 return type->AsBitset(); | 138 if (type->IsUnion()) { |
53 } else if (type->IsUnion()) { | |
54 UnionHandle unioned = handle(type->AsUnion()); | |
55 int bitset = kNone; | 139 int bitset = kNone; |
56 for (int i = 0; i < unioned->Length(); ++i) { | 140 for (int i = 0; i < type->AsUnion()->Length(); ++i) { |
57 bitset |= unioned->Get(i)->BitsetLub(); | 141 bitset |= type->AsUnion()->Get(i)->BitsetLub(); |
58 } | 142 } |
59 return bitset; | 143 return bitset; |
60 } else if (type->IsClass()) { | |
61 // Little hack to avoid the need for a region for handlification here... | |
62 return Config::is_class(type) ? Lub(*Config::as_class(type)) : | |
63 type->AsClass()->Bound(NULL)->AsBitset(); | |
64 } else if (type->IsConstant()) { | |
65 return type->AsConstant()->Bound()->AsBitset(); | |
66 } else if (type->IsRange()) { | |
67 return type->AsRange()->Bound()->AsBitset(); | |
68 } else if (type->IsContext()) { | |
69 return type->AsContext()->Bound()->AsBitset(); | |
70 } else if (type->IsArray()) { | |
71 return type->AsArray()->Bound()->AsBitset(); | |
72 } else if (type->IsFunction()) { | |
73 return type->AsFunction()->Bound()->AsBitset(); | |
74 } else { | |
75 UNREACHABLE(); | |
76 return kNone; | |
77 } | 144 } |
145 if (type->IsClass()) return type->AsClass()->BitsetLub(); | |
146 if (type->IsConstant()) return type->AsConstant()->BitsetLub(); | |
147 if (type->IsRange()) return type->AsRange()->BitsetLub(); | |
148 if (type->IsContext()) return kInternal & kTaggedPtr; | |
149 if (type->IsArray()) return kArray; | |
150 if (type->IsFunction()) return kFunction; | |
151 UNREACHABLE(); | |
152 return kNone; | |
78 } | 153 } |
79 | 154 |
80 | 155 |
81 // The smallest bitset subsuming this type, ignoring explicit bounds. | |
82 template<class Config> | |
83 int TypeImpl<Config>::BitsetType::InherentLub(TypeImpl* type) { | |
84 DisallowHeapAllocation no_allocation; | |
85 if (type->IsBitset()) { | |
86 return type->AsBitset(); | |
87 } else if (type->IsUnion()) { | |
88 UnionHandle unioned = handle(type->AsUnion()); | |
89 int bitset = kNone; | |
90 for (int i = 0; i < unioned->Length(); ++i) { | |
91 bitset |= unioned->Get(i)->InherentBitsetLub(); | |
92 } | |
93 return bitset; | |
94 } else if (type->IsClass()) { | |
95 return Lub(*type->AsClass()->Map()); | |
96 } else if (type->IsConstant()) { | |
97 return Lub(*type->AsConstant()->Value()); | |
98 } else if (type->IsRange()) { | |
99 return Lub(type->AsRange()->Min(), type->AsRange()->Max()); | |
100 } else if (type->IsContext()) { | |
101 return kInternal & kTaggedPtr; | |
102 } else if (type->IsArray()) { | |
103 return kArray; | |
104 } else if (type->IsFunction()) { | |
105 return kFunction; | |
106 } else { | |
107 UNREACHABLE(); | |
108 return kNone; | |
109 } | |
110 } | |
111 | |
112 | |
113 template<class Config> | |
114 int TypeImpl<Config>::BitsetType::Lub(i::Object* value) { | |
115 DisallowHeapAllocation no_allocation; | |
116 if (value->IsNumber()) { | |
117 return Lub(value->Number()) & (value->IsSmi() ? kTaggedInt : kTaggedPtr); | |
118 } | |
119 return Lub(i::HeapObject::cast(value)->map()); | |
120 } | |
121 | |
122 | |
123 template<class Config> | |
124 int TypeImpl<Config>::BitsetType::Lub(double value) { | |
125 DisallowHeapAllocation no_allocation; | |
126 if (i::IsMinusZero(value)) return kMinusZero; | |
127 if (std::isnan(value)) return kNaN; | |
128 if (IsUint32Double(value)) return Lub(FastD2UI(value)); | |
129 if (IsInt32Double(value)) return Lub(FastD2I(value)); | |
130 return kOtherNumber; | |
131 } | |
132 | |
133 | |
134 template<class Config> | |
135 int TypeImpl<Config>::BitsetType::Lub(double min, double max) { | |
136 DisallowHeapAllocation no_allocation; | |
137 DCHECK(dle(min, max)); | |
138 if (deq(min, max)) return BitsetType::Lub(min); // Singleton range. | |
139 int bitset = BitsetType::kNumber ^ SEMANTIC(BitsetType::kNaN); | |
140 if (dle(0, min) || max < 0) bitset ^= SEMANTIC(BitsetType::kMinusZero); | |
141 return bitset; | |
142 // TODO(neis): Could refine this further by doing more checks on min/max. | |
143 } | |
144 | |
145 | |
146 template<class Config> | |
147 int TypeImpl<Config>::BitsetType::Lub(int32_t value) { | |
148 if (value >= 0x40000000) { | |
149 return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall; | |
150 } | |
151 if (value >= 0) return kUnsignedSmall; | |
152 if (value >= -0x40000000) return kOtherSignedSmall; | |
153 return i::SmiValuesAre31Bits() ? kOtherSigned32 : kOtherSignedSmall; | |
154 } | |
155 | |
156 | |
157 template<class Config> | |
158 int TypeImpl<Config>::BitsetType::Lub(uint32_t value) { | |
159 DisallowHeapAllocation no_allocation; | |
160 if (value >= 0x80000000u) return kOtherUnsigned32; | |
161 if (value >= 0x40000000u) { | |
162 return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall; | |
163 } | |
164 return kUnsignedSmall; | |
165 } | |
166 | |
167 | |
168 template<class Config> | 156 template<class Config> |
169 int TypeImpl<Config>::BitsetType::Lub(i::Map* map) { | 157 int TypeImpl<Config>::BitsetType::Lub(i::Map* map) { |
170 DisallowHeapAllocation no_allocation; | 158 DisallowHeapAllocation no_allocation; |
171 switch (map->instance_type()) { | 159 switch (map->instance_type()) { |
172 case STRING_TYPE: | 160 case STRING_TYPE: |
173 case ONE_BYTE_STRING_TYPE: | 161 case ONE_BYTE_STRING_TYPE: |
174 case CONS_STRING_TYPE: | 162 case CONS_STRING_TYPE: |
175 case CONS_ONE_BYTE_STRING_TYPE: | 163 case CONS_ONE_BYTE_STRING_TYPE: |
176 case SLICED_STRING_TYPE: | 164 case SLICED_STRING_TYPE: |
177 case SLICED_ONE_BYTE_STRING_TYPE: | 165 case SLICED_ONE_BYTE_STRING_TYPE: |
178 case EXTERNAL_STRING_TYPE: | 166 case EXTERNAL_STRING_TYPE: |
179 case EXTERNAL_ONE_BYTE_STRING_TYPE: | 167 case EXTERNAL_ONE_BYTE_STRING_TYPE: |
180 case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: | 168 case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: |
181 case SHORT_EXTERNAL_STRING_TYPE: | 169 case SHORT_EXTERNAL_STRING_TYPE: |
182 case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE: | 170 case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE: |
183 case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: | 171 case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: |
172 return kOtherString; | |
184 case INTERNALIZED_STRING_TYPE: | 173 case INTERNALIZED_STRING_TYPE: |
185 case ONE_BYTE_INTERNALIZED_STRING_TYPE: | 174 case ONE_BYTE_INTERNALIZED_STRING_TYPE: |
186 case EXTERNAL_INTERNALIZED_STRING_TYPE: | 175 case EXTERNAL_INTERNALIZED_STRING_TYPE: |
187 case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE: | 176 case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE: |
188 case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE: | 177 case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE: |
189 case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE: | 178 case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE: |
190 case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE: | 179 case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE: |
191 case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE: | 180 case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE: |
192 return kString; | 181 return kInternalizedString; |
193 case SYMBOL_TYPE: | 182 case SYMBOL_TYPE: |
194 return kSymbol; | 183 return kSymbol; |
195 case ODDBALL_TYPE: { | 184 case ODDBALL_TYPE: { |
196 Heap* heap = map->GetHeap(); | 185 Heap* heap = map->GetHeap(); |
197 if (map == heap->undefined_map()) return kUndefined; | 186 if (map == heap->undefined_map()) return kUndefined; |
198 if (map == heap->null_map()) return kNull; | 187 if (map == heap->null_map()) return kNull; |
199 if (map == heap->boolean_map()) return kBoolean; | 188 if (map == heap->boolean_map()) return kBoolean; |
200 DCHECK(map == heap->the_hole_map() || | 189 DCHECK(map == heap->the_hole_map() || |
201 map == heap->uninitialized_map() || | 190 map == heap->uninitialized_map() || |
202 map == heap->no_interceptor_result_sentinel_map() || | 191 map == heap->no_interceptor_result_sentinel_map() || |
(...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
254 case FOREIGN_TYPE: | 243 case FOREIGN_TYPE: |
255 case CODE_TYPE: | 244 case CODE_TYPE: |
256 return kInternal & kTaggedPtr; | 245 return kInternal & kTaggedPtr; |
257 default: | 246 default: |
258 UNREACHABLE(); | 247 UNREACHABLE(); |
259 return kNone; | 248 return kNone; |
260 } | 249 } |
261 } | 250 } |
262 | 251 |
263 | 252 |
253 template<class Config> | |
254 int TypeImpl<Config>::BitsetType::Lub(i::Object* value) { | |
255 DisallowHeapAllocation no_allocation; | |
256 if (value->IsNumber()) { | |
257 return Lub(value->Number()) & (value->IsSmi() ? kTaggedInt : kTaggedPtr); | |
258 } | |
259 return Lub(i::HeapObject::cast(value)->map()); | |
260 } | |
261 | |
262 | |
263 template<class Config> | |
264 int TypeImpl<Config>::BitsetType::Lub(double value) { | |
265 DisallowHeapAllocation no_allocation; | |
266 if (i::IsMinusZero(value)) return kMinusZero; | |
267 if (std::isnan(value)) return kNaN; | |
268 if (IsUint32Double(value)) return Lub(FastD2UI(value)); | |
269 if (IsInt32Double(value)) return Lub(FastD2I(value)); | |
270 return kOtherNumber; | |
271 } | |
272 | |
273 | |
274 template<class Config> | |
275 int TypeImpl<Config>::BitsetType::Lub(int32_t value) { | |
276 DisallowHeapAllocation no_allocation; | |
277 if (value >= 0x40000000) { | |
278 return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall; | |
279 } | |
280 if (value >= 0) return kUnsignedSmall; | |
281 if (value >= -0x40000000) return kOtherSignedSmall; | |
282 return i::SmiValuesAre31Bits() ? kOtherSigned32 : kOtherSignedSmall; | |
283 } | |
284 | |
285 | |
286 template<class Config> | |
287 int TypeImpl<Config>::BitsetType::Lub(uint32_t value) { | |
288 DisallowHeapAllocation no_allocation; | |
289 if (value >= 0x80000000u) return kOtherUnsigned32; | |
290 if (value >= 0x40000000u) { | |
291 return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall; | |
292 } | |
293 return kUnsignedSmall; | |
294 } | |
295 | |
296 | |
297 // Minimum values of regular numeric bitsets when SmiValuesAre31Bits. | |
298 template<class Config> | |
299 const typename TypeImpl<Config>::BitsetType::BitsetMin | |
300 TypeImpl<Config>::BitsetType::BitsetMins31[] = { | |
301 {kOtherNumber, -V8_INFINITY}, | |
302 {kOtherSigned32, kMinInt}, | |
303 {kOtherSignedSmall, -0x40000000}, | |
304 {kUnsignedSmall, 0}, | |
305 {kOtherUnsigned31, 0x40000000}, | |
306 {kOtherUnsigned32, 0x80000000}, | |
307 {kOtherNumber, static_cast<double>(kMaxUInt32) + 1} | |
308 }; | |
309 | |
310 | |
311 // Minimum values of regular numeric bitsets when SmiValuesAre32Bits. | |
312 // OtherSigned32 and OtherUnsigned31 are empty (see the diagrams in types.h). | |
313 template<class Config> | |
314 const typename TypeImpl<Config>::BitsetType::BitsetMin | |
315 TypeImpl<Config>::BitsetType::BitsetMins32[] = { | |
316 {kOtherNumber, -V8_INFINITY}, | |
317 {kOtherSignedSmall, kMinInt}, | |
318 {kUnsignedSmall, 0}, | |
319 {kOtherUnsigned32, 0x80000000}, | |
320 {kOtherNumber, static_cast<double>(kMaxUInt32) + 1} | |
321 }; | |
322 | |
323 | |
324 template<class Config> | |
325 int TypeImpl<Config>::BitsetType::Lub(Limits lim) { | |
326 DisallowHeapAllocation no_allocation; | |
327 double min = lim.min->Number(); | |
328 double max = lim.max->Number(); | |
329 int lub = kNone; | |
330 | |
331 for (size_t i = 1; i < BitsetMinsSize(); ++i) { | |
332 if (min < BitsetMins()[i].min) { | |
rossberg
2014/09/23 15:20:37
Nit: make a local for BitsetMins(). Similarly belo
neis1
2014/09/24 07:21:38
Done.
| |
333 lub |= BitsetMins()[i-1].bitset; | |
334 if (max < BitsetMins()[i].min) return lub; | |
335 } | |
336 } | |
337 return lub |= BitsetMins()[BitsetMinsSize()-1].bitset; | |
338 } | |
339 | |
340 | |
341 template<class Config> | |
342 double TypeImpl<Config>::BitsetType::Min(int bitset) { | |
343 DisallowHeapAllocation no_allocation; | |
344 DCHECK(Is(bitset, kNumber)); | |
345 bool mz = SEMANTIC(bitset & kMinusZero); | |
346 for (size_t i = 0; i < BitsetMinsSize(); ++i) { | |
347 if (Is(SEMANTIC(BitsetMins()[i].bitset), bitset)) { | |
348 return mz ? std::min(0.0, BitsetMins()[i].min) : BitsetMins()[i].min; | |
349 } | |
350 } | |
351 if (mz) return 0; | |
352 return base::OS::nan_value(); | |
353 } | |
354 | |
355 | |
356 template<class Config> | |
357 double TypeImpl<Config>::BitsetType::Max(int bitset) { | |
358 DisallowHeapAllocation no_allocation; | |
359 DCHECK(Is(bitset, kNumber)); | |
360 bool mz = bitset & kMinusZero; | |
361 if (BitsetType::Is(BitsetMins()[BitsetMinsSize()-1].bitset, bitset)) { | |
362 return +V8_INFINITY; | |
363 } | |
364 for (size_t i = BitsetMinsSize()-1; i-- > 0; ) { | |
365 if (Is(SEMANTIC(BitsetMins()[i].bitset), bitset)) { | |
366 return mz ? | |
367 std::max(0.0, BitsetMins()[i+1].min - 1) : BitsetMins()[i+1].min - 1; | |
368 } | |
369 } | |
370 if (mz) return 0; | |
371 return base::OS::nan_value(); | |
372 } | |
373 | |
374 | |
264 // ----------------------------------------------------------------------------- | 375 // ----------------------------------------------------------------------------- |
265 // Predicates. | 376 // Predicates. |
266 | 377 |
267 // Check this <= that. | 378 |
379 template<class Config> | |
380 bool TypeImpl<Config>::SimplyEquals(TypeImpl* that) { | |
381 DisallowHeapAllocation no_allocation; | |
382 if (this->IsClass()) { | |
383 return that->IsClass() | |
384 && *this->AsClass()->Map() == *that->AsClass()->Map(); | |
385 } | |
386 if (this->IsConstant()) { | |
387 return that->IsConstant() | |
388 && *this->AsConstant()->Value() == *that->AsConstant()->Value(); | |
389 } | |
390 if (this->IsContext()) { | |
391 return that->IsContext() | |
392 && this->AsContext()->Outer()->Equals(that->AsContext()->Outer()); | |
393 } | |
394 if (this->IsArray()) { | |
395 return that->IsArray() | |
396 && this->AsArray()->Element()->Equals(that->AsArray()->Element()); | |
397 } | |
398 if (this->IsFunction()) { | |
399 if (!that->IsFunction()) return false; | |
400 FunctionType* this_fun = this->AsFunction(); | |
401 FunctionType* that_fun = that->AsFunction(); | |
402 if (this_fun->Arity() != that_fun->Arity() || | |
403 !this_fun->Result()->Equals(that_fun->Result()) || | |
404 !this_fun->Receiver()->Equals(that_fun->Receiver())) { | |
405 return false; | |
406 } | |
407 for (int i = 0; i < this_fun->Arity(); ++i) { | |
408 if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false; | |
409 } | |
410 return true; | |
411 } | |
412 UNREACHABLE(); | |
413 return false; | |
414 } | |
415 | |
416 | |
417 // Check if [this] <= [that]. | |
268 template<class Config> | 418 template<class Config> |
269 bool TypeImpl<Config>::SlowIs(TypeImpl* that) { | 419 bool TypeImpl<Config>::SlowIs(TypeImpl* that) { |
270 DisallowHeapAllocation no_allocation; | 420 DisallowHeapAllocation no_allocation; |
271 | 421 |
272 // Fast path for bitsets. | |
273 if (this->IsNone()) return true; | |
274 if (that->IsBitset()) { | 422 if (that->IsBitset()) { |
275 return BitsetType::Is(BitsetType::Lub(this), that->AsBitset()); | 423 return BitsetType::Is(this->BitsetLub(), that->AsBitset()); |
424 } | |
425 if (this->IsBitset()) { | |
426 return BitsetType::Is(this->AsBitset(), that->BitsetGlb()); | |
276 } | 427 } |
277 | 428 |
278 if (that->IsClass()) { | 429 // (T1 \/ ... \/ Tn) <= T if (T1 <= T) /\ ... /\ (Tn <= T) |
279 return this->IsClass() | |
280 && *this->AsClass()->Map() == *that->AsClass()->Map() | |
281 && ((Config::is_class(that) && Config::is_class(this)) || | |
282 BitsetType::New(this->BitsetLub())->Is( | |
283 BitsetType::New(that->BitsetLub()))); | |
284 } | |
285 if (that->IsConstant()) { | |
286 return this->IsConstant() | |
287 && *this->AsConstant()->Value() == *that->AsConstant()->Value() | |
288 && this->AsConstant()->Bound()->Is(that->AsConstant()->Bound()); | |
289 } | |
290 if (that->IsRange()) { | |
291 return this->IsRange() | |
292 && this->AsRange()->Bound()->Is(that->AsRange()->Bound()) | |
293 && dle(that->AsRange()->Min(), this->AsRange()->Min()) | |
294 && dle(this->AsRange()->Max(), that->AsRange()->Max()); | |
295 } | |
296 if (that->IsContext()) { | |
297 return this->IsContext() | |
298 && this->AsContext()->Outer()->Equals(that->AsContext()->Outer()); | |
299 } | |
300 if (that->IsArray()) { | |
301 return this->IsArray() | |
302 && this->AsArray()->Element()->Equals(that->AsArray()->Element()); | |
303 } | |
304 if (that->IsFunction()) { | |
305 // We currently do not allow for any variance here, in order to keep | |
306 // Union and Intersect operations simple. | |
307 if (!this->IsFunction()) return false; | |
308 FunctionType* this_fun = this->AsFunction(); | |
309 FunctionType* that_fun = that->AsFunction(); | |
310 if (this_fun->Arity() != that_fun->Arity() || | |
311 !this_fun->Result()->Equals(that_fun->Result()) || | |
312 !that_fun->Receiver()->Equals(this_fun->Receiver())) { | |
313 return false; | |
314 } | |
315 for (int i = 0; i < this_fun->Arity(); ++i) { | |
316 if (!that_fun->Parameter(i)->Equals(this_fun->Parameter(i))) return false; | |
317 } | |
318 return true; | |
319 } | |
320 | |
321 // (T1 \/ ... \/ Tn) <= T <=> (T1 <= T) /\ ... /\ (Tn <= T) | |
322 if (this->IsUnion()) { | 430 if (this->IsUnion()) { |
323 UnionHandle unioned = handle(this->AsUnion()); | 431 UnionHandle unioned = handle(this->AsUnion()); |
324 for (int i = 0; i < unioned->Length(); ++i) { | 432 for (int i = 0; i < unioned->Length(); ++i) { |
325 if (!unioned->Get(i)->Is(that)) return false; | 433 if (!unioned->Get(i)->Is(that)) return false; |
326 } | 434 } |
327 return true; | 435 return true; |
328 } | 436 } |
329 | 437 |
330 // T <= (T1 \/ ... \/ Tn) <=> (T <= T1) \/ ... \/ (T <= Tn) | 438 // T <= (T1 \/ ... \/ Tn) if (T <= T1) \/ ... \/ (T <= Tn) |
331 // (iff T is not a union) | 439 if (that->IsUnion()) { |
332 DCHECK(!this->IsUnion() && that->IsUnion()); | 440 for (int i = 0; i < that->AsUnion()->Length(); ++i) { |
333 UnionHandle unioned = handle(that->AsUnion()); | 441 if (this->Is(that->AsUnion()->Get(i))) return true; |
334 for (int i = 0; i < unioned->Length(); ++i) { | 442 if (i > 1 && this->IsRange()) return false; // Shortcut. |
335 if (this->Is(unioned->Get(i))) return true; | 443 } |
336 if (this->IsBitset()) break; // Fast fail, only first field is a bitset. | 444 return false; |
337 } | 445 } |
338 return false; | 446 |
447 if (that->IsRange()) { | |
448 return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) | |
449 || (this->IsConstant() && | |
450 Contains(that->AsRange(), *this->AsConstant()->Value())); | |
451 } | |
452 if (this->IsRange()) return false; | |
453 return this->SimplyEquals(that); | |
339 } | 454 } |
340 | 455 |
341 | 456 |
342 template<class Config> | 457 template<class Config> |
343 bool TypeImpl<Config>::NowIs(TypeImpl* that) { | 458 bool TypeImpl<Config>::NowIs(TypeImpl* that) { |
344 DisallowHeapAllocation no_allocation; | 459 DisallowHeapAllocation no_allocation; |
345 | 460 |
346 // TODO(rossberg): this is incorrect for | 461 // TODO(rossberg): this is incorrect for |
347 // Union(Constant(V), T)->NowIs(Class(M)) | 462 // Union(Constant(V), T)->NowIs(Class(M)) |
348 // but fuzzing does not cover that! | 463 // but fuzzing does not cover that! |
349 if (this->IsConstant()) { | 464 if (this->IsConstant()) { |
350 i::Object* object = *this->AsConstant()->Value(); | 465 i::Object* object = *this->AsConstant()->Value(); |
351 if (object->IsHeapObject()) { | 466 if (object->IsHeapObject()) { |
352 i::Map* map = i::HeapObject::cast(object)->map(); | 467 i::Map* map = i::HeapObject::cast(object)->map(); |
353 for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) { | 468 for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) { |
354 if (*it.Current() == map) return true; | 469 if (*it.Current() == map) return true; |
355 } | 470 } |
356 } | 471 } |
357 } | 472 } |
358 return this->Is(that); | 473 return this->Is(that); |
359 } | 474 } |
360 | 475 |
361 | 476 |
362 // Check if this contains only (currently) stable classes. | 477 // Check if [this] contains only (currently) stable classes. |
363 template<class Config> | 478 template<class Config> |
364 bool TypeImpl<Config>::NowStable() { | 479 bool TypeImpl<Config>::NowStable() { |
365 DisallowHeapAllocation no_allocation; | 480 DisallowHeapAllocation no_allocation; |
366 for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) { | 481 for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) { |
367 if (!it.Current()->is_stable()) return false; | 482 if (!it.Current()->is_stable()) return false; |
368 } | 483 } |
369 return true; | 484 return true; |
370 } | 485 } |
371 | 486 |
372 | 487 |
373 // Check this overlaps that. | 488 // Check if [this] and [that] overlap. |
374 template<class Config> | 489 template<class Config> |
375 bool TypeImpl<Config>::Maybe(TypeImpl* that) { | 490 bool TypeImpl<Config>::Maybe(TypeImpl* that) { |
376 DisallowHeapAllocation no_allocation; | 491 DisallowHeapAllocation no_allocation; |
377 | 492 |
378 // (T1 \/ ... \/ Tn) overlaps T <=> (T1 overlaps T) \/ ... \/ (Tn overlaps T) | 493 // (T1 \/ ... \/ Tn) overlaps T if (T1 overlaps T) \/ ... \/ (Tn overlaps T) |
379 if (this->IsUnion()) { | 494 if (this->IsUnion()) { |
380 UnionHandle unioned = handle(this->AsUnion()); | 495 UnionHandle unioned = handle(this->AsUnion()); |
381 for (int i = 0; i < unioned->Length(); ++i) { | 496 for (int i = 0; i < unioned->Length(); ++i) { |
382 if (unioned->Get(i)->Maybe(that)) return true; | 497 if (unioned->Get(i)->Maybe(that)) return true; |
383 } | 498 } |
384 return false; | 499 return false; |
385 } | 500 } |
386 | 501 |
387 // T overlaps (T1 \/ ... \/ Tn) <=> (T overlaps T1) \/ ... \/ (T overlaps Tn) | 502 // T overlaps (T1 \/ ... \/ Tn) if (T overlaps T1) \/ ... \/ (T overlaps Tn) |
388 if (that->IsUnion()) { | 503 if (that->IsUnion()) { |
389 UnionHandle unioned = handle(that->AsUnion()); | 504 for (int i = 0; i < that->AsUnion()->Length(); ++i) { |
390 for (int i = 0; i < unioned->Length(); ++i) { | 505 if (this->Maybe(that->AsUnion()->Get(i))) return true; |
391 if (this->Maybe(unioned->Get(i))) return true; | |
392 } | 506 } |
393 return false; | 507 return false; |
394 } | 508 } |
395 | 509 |
396 DCHECK(!this->IsUnion() && !that->IsUnion()); | 510 if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub())) |
397 if (this->IsBitset() || that->IsBitset()) { | 511 return false; |
398 return BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()); | 512 if (this->IsBitset() || that->IsBitset()) return true; |
513 | |
514 if (this->IsClass() != that->IsClass()) return true; | |
515 | |
516 if (this->IsRange()) { | |
517 if (that->IsConstant()) { | |
518 return Contains(this->AsRange(), *that->AsConstant()->Value()); | |
519 } | |
520 return that->IsRange() && Overlap(this->AsRange(), that->AsRange()); | |
399 } | 521 } |
400 if (this->IsClass()) { | 522 if (that->IsRange()) { |
401 return that->IsClass() | 523 if (this->IsConstant()) { |
402 && *this->AsClass()->Map() == *that->AsClass()->Map(); | 524 return Contains(that->AsRange(), *this->AsConstant()->Value()); |
403 } | 525 } |
404 if (this->IsConstant()) { | 526 return this->IsRange() && Overlap(this->AsRange(), that->AsRange()); |
405 return that->IsConstant() | |
406 && *this->AsConstant()->Value() == *that->AsConstant()->Value(); | |
407 } | |
408 if (this->IsContext()) { | |
409 return this->Equals(that); | |
410 } | |
411 if (this->IsArray()) { | |
412 // There is no variance! | |
413 return this->Equals(that); | |
414 } | |
415 if (this->IsFunction()) { | |
416 // There is no variance! | |
417 return this->Equals(that); | |
418 } | 527 } |
419 | 528 |
420 return false; | 529 return this->SimplyEquals(that); |
421 } | 530 } |
422 | 531 |
423 | 532 |
424 // Check if value is contained in (inhabits) type. | 533 // Return the range in [this], or [NULL]. |
534 template<class Config> | |
535 typename TypeImpl<Config>::RangeType* TypeImpl<Config>::GetRange() { | |
536 DisallowHeapAllocation no_allocation; | |
537 if (this->IsRange()) return this->AsRange(); | |
538 if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) { | |
539 return this->AsUnion()->Get(1)->AsRange(); | |
540 } | |
541 return NULL; | |
542 } | |
543 | |
544 | |
425 template<class Config> | 545 template<class Config> |
426 bool TypeImpl<Config>::Contains(i::Object* value) { | 546 bool TypeImpl<Config>::Contains(i::Object* value) { |
427 DisallowHeapAllocation no_allocation; | 547 DisallowHeapAllocation no_allocation; |
428 if (this->IsRange()) { | |
429 return value->IsNumber() && | |
430 dle(this->AsRange()->Min(), value->Number()) && | |
431 dle(value->Number(), this->AsRange()->Max()) && | |
432 BitsetType::Is(BitsetType::Lub(value), this->BitsetLub()); | |
433 } | |
434 for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) { | 548 for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) { |
435 if (*it.Current() == value) return true; | 549 if (*it.Current() == value) return true; |
436 } | 550 } |
551 if (IsInteger(value)) { | |
552 RangeType* range = this->GetRange(); | |
553 if (range != NULL && Contains(range, value)) return true; | |
554 } | |
437 return BitsetType::New(BitsetType::Lub(value))->Is(this); | 555 return BitsetType::New(BitsetType::Lub(value))->Is(this); |
438 } | 556 } |
439 | 557 |
440 | 558 |
441 template<class Config> | 559 template<class Config> |
442 bool TypeImpl<Config>::UnionType::Wellformed() { | 560 bool TypeImpl<Config>::UnionType::Wellformed() { |
443 DCHECK(this->Length() >= 2); | 561 DisallowHeapAllocation no_allocation; |
562 // This checks the invariants of the union representation: | |
563 // 1. There are at least two elements. | |
564 // 2. At most one element is a bitset, and it must be the first one. | |
565 // 3. At most one element is a range, and it must be the second one | |
566 // (even when the first element is not a bitset). | |
567 // 4. No element is itself a union. | |
568 // 5. No element is a subtype of any other. | |
569 DCHECK(this->Length() >= 2); // (1) | |
444 for (int i = 0; i < this->Length(); ++i) { | 570 for (int i = 0; i < this->Length(); ++i) { |
445 DCHECK(!this->Get(i)->IsUnion()); | 571 if (i != 0) DCHECK(!this->Get(i)->IsBitset()); // (2) |
446 if (i > 0) DCHECK(!this->Get(i)->IsBitset()); | 572 if (i != 1) DCHECK(!this->Get(i)->IsRange()); // (3) |
573 DCHECK(!this->Get(i)->IsUnion()); // (4) | |
447 for (int j = 0; j < this->Length(); ++j) { | 574 for (int j = 0; j < this->Length(); ++j) { |
448 if (i != j) DCHECK(!this->Get(i)->Is(this->Get(j))); | 575 if (i != j) DCHECK(!this->Get(i)->Is(this->Get(j))); // (5) |
449 } | 576 } |
450 } | 577 } |
451 return true; | 578 return true; |
452 } | 579 } |
453 | 580 |
454 | 581 |
455 // ----------------------------------------------------------------------------- | 582 // ----------------------------------------------------------------------------- |
456 // Union and intersection | 583 // Union and intersection |
457 | 584 |
458 template<class Config> | 585 |
459 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Rebound( | 586 static bool AddIsSafe(int x, int y) { |
460 int bitset, Region* region) { | 587 return x >= 0 ? |
461 TypeHandle bound = BitsetType::New(bitset, region); | 588 y <= std::numeric_limits<int>::max() - x : |
462 if (this->IsClass()) { | 589 y >= std::numeric_limits<int>::min() - x; |
463 return ClassType::New(this->AsClass()->Map(), bound, region); | 590 } |
464 } else if (this->IsConstant()) { | 591 |
465 return ConstantType::New(this->AsConstant()->Value(), bound, region); | 592 |
466 } else if (this->IsRange()) { | 593 template<class Config> |
467 return RangeType::New( | 594 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect( |
468 this->AsRange()->Min(), this->AsRange()->Max(), bound, region); | 595 TypeHandle type1, TypeHandle type2, Region* region) { |
469 } else if (this->IsContext()) { | 596 int bitset = type1->BitsetGlb() & type2->BitsetGlb(); |
470 return ContextType::New(this->AsContext()->Outer(), bound, region); | 597 if (!BitsetType::IsInhabited(bitset)) bitset = BitsetType::kNone; |
471 } else if (this->IsArray()) { | 598 |
472 return ArrayType::New(this->AsArray()->Element(), bound, region); | 599 // Fast case: bit sets. |
473 } else if (this->IsFunction()) { | 600 if (type1->IsBitset() && type2->IsBitset()) { |
474 FunctionHandle function = Config::handle(this->AsFunction()); | 601 return BitsetType::New(bitset, region); |
475 int arity = function->Arity(); | 602 } |
476 FunctionHandle type = FunctionType::New( | 603 |
477 function->Result(), function->Receiver(), bound, arity, region); | 604 // Fast case: top or bottom types. |
478 for (int i = 0; i < arity; ++i) { | 605 if (type1->IsNone() || type2->IsAny()) return type1; // Shortcut. |
479 type->InitParameter(i, function->Parameter(i)); | 606 if (type2->IsNone() || type1->IsAny()) return type2; // Shortcut. |
480 } | 607 |
481 return type; | 608 // Semi-fast case. |
482 } | 609 if (type1->Is(type2)) return type1; |
483 UNREACHABLE(); | 610 if (type2->Is(type1)) return type2; |
484 return TypeHandle(); | 611 |
485 } | 612 // Slow case: create union. |
486 | 613 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1; |
487 | 614 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1; |
488 template<class Config> | 615 if (!AddIsSafe(size1, size2)) return Any(region); |
489 int TypeImpl<Config>::BoundBy(TypeImpl* that) { | 616 int size = size1 + size2; |
490 DCHECK(!this->IsUnion()); | 617 if (!AddIsSafe(size, 2)) return Any(region); |
491 if (that->IsUnion()) { | 618 size += 2; |
492 UnionType* unioned = that->AsUnion(); | 619 UnionHandle result = UnionType::New(size, region); |
493 int length = unioned->Length(); | 620 size = 0; |
494 int bitset = BitsetType::kNone; | 621 |
495 for (int i = 0; i < length; ++i) { | 622 // Deal with bitsets. |
496 bitset |= BoundBy(unioned->Get(i)->unhandle()); | 623 result->Set(size++, BitsetType::New(bitset, region)); |
497 } | 624 |
498 return bitset; | 625 // Deal with ranges. |
499 } else if (that->IsClass() && this->IsClass() && | 626 TypeHandle range = None(region); |
500 *this->AsClass()->Map() == *that->AsClass()->Map()) { | 627 RangeType* range1 = type1->GetRange(); |
501 return that->BitsetLub(); | 628 RangeType* range2 = type2->GetRange(); |
502 } else if (that->IsConstant() && this->IsConstant() && | 629 if (range1 != NULL && range2 != NULL) { |
503 *this->AsConstant()->Value() == *that->AsConstant()->Value()) { | 630 Limits lim = Intersect(Limits(range1), Limits(range2)); |
504 return that->AsConstant()->Bound()->AsBitset(); | 631 if (lim.min->Number() <= lim.max->Number()) { |
505 } else if (that->IsContext() && this->IsContext() && this->Is(that)) { | 632 range = RangeType::New(lim, region); |
506 return that->AsContext()->Bound()->AsBitset(); | 633 } |
507 } else if (that->IsArray() && this->IsArray() && this->Is(that)) { | 634 } |
508 return that->AsArray()->Bound()->AsBitset(); | 635 result->Set(size++, range); |
509 } else if (that->IsFunction() && this->IsFunction() && this->Is(that)) { | 636 |
510 return that->AsFunction()->Bound()->AsBitset(); | 637 size = IntersectAux(type1, type2, result, size, region); |
511 } | 638 return NormalizeUnion(result, size); |
512 return that->BitsetGlb(); | 639 } |
513 } | 640 |
514 | 641 |
515 | 642 template<class Config> |
516 template<class Config> | 643 int TypeImpl<Config>::UpdateRange( |
517 int TypeImpl<Config>::IndexInUnion( | 644 RangeHandle range, UnionHandle result, int size, Region* region) { |
518 int bound, UnionHandle unioned, int current_size) { | 645 TypeHandle old_range = result->Get(1); |
519 DCHECK(!this->IsUnion()); | 646 DCHECK(old_range->IsRange() || old_range->IsNone()); |
520 for (int i = 0; i < current_size; ++i) { | 647 if (range->Is(old_range)) return size; |
521 TypeHandle that = unioned->Get(i); | 648 if (!old_range->Is(range->unhandle())) { |
522 if (that->IsBitset()) { | 649 range = RangeType::New( |
523 if (BitsetType::Is(bound, that->AsBitset())) return i; | 650 Union(Limits(range->AsRange()), Limits(old_range->AsRange())), region); |
524 } else if (that->IsClass() && this->IsClass()) { | 651 } |
525 if (*this->AsClass()->Map() == *that->AsClass()->Map()) return i; | 652 result->Set(1, range); |
526 } else if (that->IsConstant() && this->IsConstant()) { | 653 |
527 if (*this->AsConstant()->Value() == *that->AsConstant()->Value()) | 654 // Remove any components that just got subsumed. |
528 return i; | 655 for (int i = 2; i < size; ) { |
529 } else if (that->IsContext() && this->IsContext()) { | 656 if (result->Get(i)->Is(range->unhandle())) { |
530 if (this->Is(that)) return i; | 657 result->Set(i, result->Get(--size)); |
531 } else if (that->IsArray() && this->IsArray()) { | 658 } else { |
532 if (this->Is(that)) return i; | 659 ++i; |
533 } else if (that->IsFunction() && this->IsFunction()) { | |
534 if (this->Is(that)) return i; | |
535 } | |
536 } | |
537 return -1; | |
538 } | |
539 | |
540 | |
541 // Get non-bitsets from type, bounded by upper. | |
542 // Store at result starting at index. Returns updated index. | |
543 template<class Config> | |
544 int TypeImpl<Config>::ExtendUnion( | |
545 UnionHandle result, int size, TypeHandle type, | |
546 TypeHandle other, bool is_intersect, Region* region) { | |
547 if (type->IsUnion()) { | |
548 UnionHandle unioned = handle(type->AsUnion()); | |
549 for (int i = 0; i < unioned->Length(); ++i) { | |
550 TypeHandle type_i = unioned->Get(i); | |
551 DCHECK(i == 0 || !(type_i->IsBitset() || type_i->Is(unioned->Get(0)))); | |
552 if (!type_i->IsBitset()) { | |
553 size = ExtendUnion(result, size, type_i, other, is_intersect, region); | |
554 } | |
555 } | |
556 } else if (!type->IsBitset()) { | |
557 DCHECK(type->IsClass() || type->IsConstant() || type->IsRange() || | |
558 type->IsContext() || type->IsArray() || type->IsFunction()); | |
559 int inherent_bound = type->InherentBitsetLub(); | |
560 int old_bound = type->BitsetLub(); | |
561 int other_bound = type->BoundBy(other->unhandle()) & inherent_bound; | |
562 int new_bound = | |
563 is_intersect ? (old_bound & other_bound) : (old_bound | other_bound); | |
564 if (new_bound != BitsetType::kNone) { | |
565 int i = type->IndexInUnion(new_bound, result, size); | |
566 if (i == -1) { | |
567 i = size++; | |
568 } else if (result->Get(i)->IsBitset()) { | |
569 return size; // Already fully subsumed. | |
570 } else { | |
571 int type_i_bound = result->Get(i)->BitsetLub(); | |
572 new_bound |= type_i_bound; | |
573 if (new_bound == type_i_bound) return size; | |
574 } | |
575 if (new_bound != old_bound) type = type->Rebound(new_bound, region); | |
576 result->Set(i, type); | |
577 } | 660 } |
578 } | 661 } |
579 return size; | 662 return size; |
580 } | 663 } |
581 | 664 |
582 | 665 |
583 // Union is O(1) on simple bitsets, but O(n*m) on structured unions. | 666 template<class Config> |
667 int TypeImpl<Config>::IntersectAux( | |
668 TypeHandle lhs, TypeHandle rhs, | |
669 UnionHandle result, int size, Region* region) { | |
670 if (lhs->IsUnion()) { | |
671 for (int i = 0; i < lhs->AsUnion()->Length(); ++i) { | |
672 size = IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, region); | |
673 } | |
674 return size; | |
675 } | |
676 if (rhs->IsUnion()) { | |
677 for (int i = 0; i < rhs->AsUnion()->Length(); ++i) { | |
678 size = IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, region); | |
679 } | |
680 return size; | |
681 } | |
682 | |
683 if (!BitsetType::IsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) { | |
684 return size; | |
685 } | |
686 | |
687 if (lhs->IsRange()) { | |
688 if (rhs->IsBitset() || rhs->IsClass()) { | |
689 return UpdateRange( | |
690 Config::template cast<RangeType>(lhs), result, size, region); | |
691 } | |
692 if (rhs->IsConstant() && | |
693 Contains(lhs->AsRange(), *rhs->AsConstant()->Value())) { | |
694 return AddToUnion(rhs, result, size, region); | |
695 } | |
696 return size; | |
697 } | |
698 if (rhs->IsRange()) { | |
699 if (lhs->IsBitset() || lhs->IsClass()) { | |
700 return UpdateRange( | |
701 Config::template cast<RangeType>(rhs), result, size, region); | |
702 } | |
703 if (lhs->IsConstant() && | |
704 Contains(rhs->AsRange(), *lhs->AsConstant()->Value())) { | |
705 return AddToUnion(lhs, result, size, region); | |
706 } | |
707 return size; | |
708 } | |
709 | |
710 if (lhs->IsBitset() || rhs->IsBitset()) { | |
711 return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, region); | |
712 } | |
713 if (lhs->IsClass() != rhs->IsClass()) { | |
714 return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, region); | |
715 } | |
716 if (lhs->SimplyEquals(rhs->unhandle())) { | |
717 return AddToUnion(lhs, result, size, region); | |
718 } | |
719 return size; | |
720 } | |
721 | |
722 | |
584 template<class Config> | 723 template<class Config> |
585 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union( | 724 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union( |
586 TypeHandle type1, TypeHandle type2, Region* region) { | 725 TypeHandle type1, TypeHandle type2, Region* region) { |
726 | |
587 // Fast case: bit sets. | 727 // Fast case: bit sets. |
588 if (type1->IsBitset() && type2->IsBitset()) { | 728 if (type1->IsBitset() && type2->IsBitset()) { |
589 return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region); | 729 return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region); |
590 } | 730 } |
591 | 731 |
592 // Fast case: top or bottom types. | 732 // Fast case: top or bottom types. |
593 if (type1->IsAny() || type2->IsNone()) return type1; | 733 if (type1->IsAny() || type2->IsNone()) return type1; |
594 if (type2->IsAny() || type1->IsNone()) return type2; | 734 if (type2->IsAny() || type1->IsNone()) return type2; |
595 | 735 |
596 // Semi-fast case: Unioned objects are neither involved nor produced. | 736 // Semi-fast case. |
597 if (!(type1->IsUnion() || type2->IsUnion())) { | 737 if (type1->Is(type2)) return type2; |
598 if (type1->Is(type2)) return type2; | 738 if (type2->Is(type1)) return type1; |
599 if (type2->Is(type1)) return type1; | 739 |
600 } | 740 // Slow case: create union. |
601 | 741 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1; |
602 // Slow case: may need to produce a Unioned object. | 742 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1; |
603 int size = 0; | 743 if (!AddIsSafe(size1, size2)) return Any(region); |
604 if (!type1->IsBitset()) { | 744 int size = size1 + size2; |
605 size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1); | 745 if (!AddIsSafe(size, 2)) return Any(region); |
606 } | 746 size += 2; |
607 if (!type2->IsBitset()) { | 747 UnionHandle result = UnionType::New(size, region); |
608 size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1); | |
609 } | |
610 int bitset = type1->BitsetGlb() | type2->BitsetGlb(); | |
611 if (bitset != BitsetType::kNone) ++size; | |
612 DCHECK(size >= 1); | |
613 | |
614 UnionHandle unioned = UnionType::New(size, region); | |
615 size = 0; | 748 size = 0; |
616 if (bitset != BitsetType::kNone) { | 749 |
617 unioned->Set(size++, BitsetType::New(bitset, region)); | 750 // Deal with bitsets. |
618 } | 751 TypeHandle bitset = BitsetType::New( |
619 size = ExtendUnion(unioned, size, type1, type2, false, region); | 752 type1->BitsetGlb() | type2->BitsetGlb(), region); |
620 size = ExtendUnion(unioned, size, type2, type1, false, region); | 753 result->Set(size++, bitset); |
621 | 754 |
622 if (size == 1) { | 755 // Deal with ranges. |
623 return unioned->Get(0); | 756 TypeHandle range = None(region); |
624 } else { | 757 RangeType* range1 = type1->GetRange(); |
625 unioned->Shrink(size); | 758 RangeType* range2 = type2->GetRange(); |
626 DCHECK(unioned->Wellformed()); | 759 if (range1 != NULL && range2 != NULL) { |
627 return unioned; | 760 range = RangeType::New(Union(Limits(range1), Limits(range2)), region); |
628 } | 761 } else if (range1 != NULL) { |
629 } | 762 range = handle(range1); |
630 | 763 } else if (range2 != NULL) { |
631 | 764 range = handle(range2); |
632 // Intersection is O(1) on simple bitsets, but O(n*m) on structured unions. | 765 } |
633 template<class Config> | 766 result->Set(size++, range); |
634 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect( | 767 |
635 TypeHandle type1, TypeHandle type2, Region* region) { | 768 size = AddToUnion(type1, result, size, region); |
636 // Fast case: bit sets. | 769 size = AddToUnion(type2, result, size, region); |
637 if (type1->IsBitset() && type2->IsBitset()) { | 770 return NormalizeUnion(result, size); |
638 return BitsetType::New(type1->AsBitset() & type2->AsBitset(), region); | 771 } |
639 } | 772 |
640 | 773 |
641 // Fast case: top or bottom types. | 774 // Add [type] to [result] unless [type] is bitset, range, or already subsumed. |
642 if (type1->IsNone() || type2->IsAny()) return type1; | 775 // Return new size of [result]. |
643 if (type2->IsNone() || type1->IsAny()) return type2; | 776 template<class Config> |
644 | 777 int TypeImpl<Config>::AddToUnion( |
645 // Semi-fast case: Unioned objects are neither involved nor produced. | 778 TypeHandle type, UnionHandle result, int size, Region* region) { |
646 if (!(type1->IsUnion() || type2->IsUnion())) { | 779 if (type->IsBitset() || type->IsRange()) return size; |
647 if (type1->Is(type2)) return type1; | 780 if (type->IsUnion()) { |
648 if (type2->Is(type1)) return type2; | 781 for (int i = 0; i < type->AsUnion()->Length(); ++i) { |
649 } | 782 size = AddToUnion(type->AsUnion()->Get(i), result, size, region); |
650 | 783 } |
651 // Slow case: may need to produce a Unioned object. | 784 return size; |
652 int size = 0; | 785 } |
653 if (!type1->IsBitset()) { | 786 for (int i = 0; i < size; ++i) { |
654 size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1); | 787 if (type->Is(result->Get(i))) return size; |
655 } | 788 } |
656 if (!type2->IsBitset()) { | 789 result->Set(size++, type); |
657 size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1); | 790 return size; |
658 } | 791 } |
659 int bitset = type1->BitsetGlb() & type2->BitsetGlb(); | 792 |
660 if (bitset != BitsetType::kNone) ++size; | 793 |
661 DCHECK(size >= 1); | 794 template<class Config> |
662 | 795 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeUnion( |
663 UnionHandle unioned = UnionType::New(size, region); | 796 UnionHandle unioned, int size) { |
664 size = 0; | 797 DCHECK(size >= 2); |
665 if (bitset != BitsetType::kNone) { | 798 // If range is subsumed by bitset, use its place for a different type. |
666 unioned->Set(size++, BitsetType::New(bitset, region)); | 799 if (unioned->Get(1)->Is(unioned->Get(0))) { |
667 } | 800 unioned->Set(1, unioned->Get(--size)); |
668 size = ExtendUnion(unioned, size, type1, type2, true, region); | 801 } |
669 size = ExtendUnion(unioned, size, type2, type1, true, region); | 802 // If bitset is None, use its place for a different type. |
670 | 803 if (size >= 2 && unioned->Get(0)->IsNone()) { |
671 if (size == 0) { | 804 unioned->Set(0, unioned->Get(--size)); |
672 return None(region); | 805 } |
673 } else if (size == 1) { | 806 if (size == 1) return unioned->Get(0); |
674 return unioned->Get(0); | 807 unioned->Shrink(size); |
675 } else { | 808 SLOW_DCHECK(unioned->Wellformed()); |
676 unioned->Shrink(size); | 809 return unioned; |
677 DCHECK(unioned->Wellformed()); | 810 } |
678 return unioned; | 811 |
679 } | 812 |
680 } | |
681 | |
682 | |
683 // ----------------------------------------------------------------------------- | 813 // ----------------------------------------------------------------------------- |
684 // Iteration. | 814 // Iteration. |
685 | 815 |
686 template<class Config> | 816 template<class Config> |
687 int TypeImpl<Config>::NumClasses() { | 817 int TypeImpl<Config>::NumClasses() { |
688 DisallowHeapAllocation no_allocation; | 818 DisallowHeapAllocation no_allocation; |
689 if (this->IsClass()) { | 819 if (this->IsClass()) { |
690 return 1; | 820 return 1; |
691 } else if (this->IsUnion()) { | 821 } else if (this->IsUnion()) { |
692 UnionHandle unioned = handle(this->AsUnion()); | 822 UnionHandle unioned = handle(this->AsUnion()); |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
786 // ----------------------------------------------------------------------------- | 916 // ----------------------------------------------------------------------------- |
787 // Conversion between low-level representations. | 917 // Conversion between low-level representations. |
788 | 918 |
789 template<class Config> | 919 template<class Config> |
790 template<class OtherType> | 920 template<class OtherType> |
791 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert( | 921 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert( |
792 typename OtherType::TypeHandle type, Region* region) { | 922 typename OtherType::TypeHandle type, Region* region) { |
793 if (type->IsBitset()) { | 923 if (type->IsBitset()) { |
794 return BitsetType::New(type->AsBitset(), region); | 924 return BitsetType::New(type->AsBitset(), region); |
795 } else if (type->IsClass()) { | 925 } else if (type->IsClass()) { |
796 TypeHandle bound = BitsetType::New(type->BitsetLub(), region); | 926 return ClassType::New(type->AsClass()->Map(), region); |
797 return ClassType::New(type->AsClass()->Map(), bound, region); | |
798 } else if (type->IsConstant()) { | 927 } else if (type->IsConstant()) { |
799 TypeHandle bound = Convert<OtherType>(type->AsConstant()->Bound(), region); | 928 return ConstantType::New(type->AsConstant()->Value(), region); |
800 return ConstantType::New(type->AsConstant()->Value(), bound, region); | |
801 } else if (type->IsRange()) { | 929 } else if (type->IsRange()) { |
802 TypeHandle bound = Convert<OtherType>(type->AsRange()->Bound(), region); | |
803 return RangeType::New( | 930 return RangeType::New( |
804 type->AsRange()->Min(), type->AsRange()->Max(), bound, region); | 931 type->AsRange()->Min(), type->AsRange()->Max(), region); |
805 } else if (type->IsContext()) { | 932 } else if (type->IsContext()) { |
806 TypeHandle bound = Convert<OtherType>(type->AsContext()->Bound(), region); | |
807 TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region); | 933 TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region); |
808 return ContextType::New(outer, bound, region); | 934 return ContextType::New(outer, region); |
809 } else if (type->IsUnion()) { | 935 } else if (type->IsUnion()) { |
810 int length = type->AsUnion()->Length(); | 936 int length = type->AsUnion()->Length(); |
811 UnionHandle unioned = UnionType::New(length, region); | 937 UnionHandle unioned = UnionType::New(length, region); |
812 for (int i = 0; i < length; ++i) { | 938 for (int i = 0; i < length; ++i) { |
813 TypeHandle t = Convert<OtherType>(type->AsUnion()->Get(i), region); | 939 TypeHandle t = Convert<OtherType>(type->AsUnion()->Get(i), region); |
814 unioned->Set(i, t); | 940 unioned->Set(i, t); |
815 } | 941 } |
816 return unioned; | 942 return unioned; |
817 } else if (type->IsArray()) { | 943 } else if (type->IsArray()) { |
818 TypeHandle element = Convert<OtherType>(type->AsArray()->Element(), region); | 944 TypeHandle element = Convert<OtherType>(type->AsArray()->Element(), region); |
819 TypeHandle bound = Convert<OtherType>(type->AsArray()->Bound(), region); | 945 return ArrayType::New(element, region); |
820 return ArrayType::New(element, bound, region); | |
821 } else if (type->IsFunction()) { | 946 } else if (type->IsFunction()) { |
822 TypeHandle res = Convert<OtherType>(type->AsFunction()->Result(), region); | 947 TypeHandle res = Convert<OtherType>(type->AsFunction()->Result(), region); |
823 TypeHandle rcv = Convert<OtherType>(type->AsFunction()->Receiver(), region); | 948 TypeHandle rcv = Convert<OtherType>(type->AsFunction()->Receiver(), region); |
824 TypeHandle bound = Convert<OtherType>(type->AsFunction()->Bound(), region); | |
825 FunctionHandle function = FunctionType::New( | 949 FunctionHandle function = FunctionType::New( |
826 res, rcv, bound, type->AsFunction()->Arity(), region); | 950 res, rcv, type->AsFunction()->Arity(), region); |
827 for (int i = 0; i < function->Arity(); ++i) { | 951 for (int i = 0; i < function->Arity(); ++i) { |
828 TypeHandle param = Convert<OtherType>( | 952 TypeHandle param = Convert<OtherType>( |
829 type->AsFunction()->Parameter(i), region); | 953 type->AsFunction()->Parameter(i), region); |
830 function->InitParameter(i, param); | 954 function->InitParameter(i, param); |
831 } | 955 } |
832 return function; | 956 return function; |
833 } else { | 957 } else { |
834 UNREACHABLE(); | 958 UNREACHABLE(); |
835 return None(region); | 959 return None(region); |
836 } | 960 } |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
901 DisallowHeapAllocation no_allocation; | 1025 DisallowHeapAllocation no_allocation; |
902 if (dim != REPRESENTATION_DIM) { | 1026 if (dim != REPRESENTATION_DIM) { |
903 if (this->IsBitset()) { | 1027 if (this->IsBitset()) { |
904 BitsetType::Print(os, SEMANTIC(this->AsBitset())); | 1028 BitsetType::Print(os, SEMANTIC(this->AsBitset())); |
905 } else if (this->IsClass()) { | 1029 } else if (this->IsClass()) { |
906 os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < "; | 1030 os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < "; |
907 BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim); | 1031 BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim); |
908 os << ")"; | 1032 os << ")"; |
909 } else if (this->IsConstant()) { | 1033 } else if (this->IsConstant()) { |
910 os << "Constant(" << static_cast<void*>(*this->AsConstant()->Value()) | 1034 os << "Constant(" << static_cast<void*>(*this->AsConstant()->Value()) |
911 << " : "; | 1035 << ")"; |
912 BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim); | |
913 os << ")"; | |
914 } else if (this->IsRange()) { | 1036 } else if (this->IsRange()) { |
915 os << "Range(" << this->AsRange()->Min() | 1037 os << "Range(" << this->AsRange()->Min()->Number() |
916 << ".." << this->AsRange()->Max() << " : "; | 1038 << ", " << this->AsRange()->Max()->Number() << ")"; |
917 BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim); | |
918 os << ")"; | |
919 } else if (this->IsContext()) { | 1039 } else if (this->IsContext()) { |
920 os << "Context("; | 1040 os << "Context("; |
921 this->AsContext()->Outer()->PrintTo(os, dim); | 1041 this->AsContext()->Outer()->PrintTo(os, dim); |
922 os << ")"; | 1042 os << ")"; |
923 } else if (this->IsUnion()) { | 1043 } else if (this->IsUnion()) { |
924 os << "("; | 1044 os << "("; |
925 UnionHandle unioned = handle(this->AsUnion()); | 1045 UnionHandle unioned = handle(this->AsUnion()); |
926 for (int i = 0; i < unioned->Length(); ++i) { | 1046 for (int i = 0; i < unioned->Length(); ++i) { |
927 TypeHandle type_i = unioned->Get(i); | 1047 TypeHandle type_i = unioned->Get(i); |
928 if (i > 0) os << " | "; | 1048 if (i > 0) os << " | "; |
(...skipping 27 matching lines...) Expand all Loading... | |
956 } | 1076 } |
957 | 1077 |
958 | 1078 |
959 #ifdef DEBUG | 1079 #ifdef DEBUG |
960 template <class Config> | 1080 template <class Config> |
961 void TypeImpl<Config>::Print() { | 1081 void TypeImpl<Config>::Print() { |
962 OFStream os(stdout); | 1082 OFStream os(stdout); |
963 PrintTo(os); | 1083 PrintTo(os); |
964 os << endl; | 1084 os << endl; |
965 } | 1085 } |
1086 template <class Config> | |
1087 void TypeImpl<Config>::BitsetType::Print(int bitset) { | |
1088 OFStream os(stdout); | |
1089 Print(os, bitset); | |
1090 os << endl; | |
1091 } | |
966 #endif | 1092 #endif |
967 | 1093 |
968 | 1094 |
969 // ----------------------------------------------------------------------------- | 1095 // ----------------------------------------------------------------------------- |
970 // Instantiations. | 1096 // Instantiations. |
971 | 1097 |
972 template class TypeImpl<ZoneTypeConfig>; | 1098 template class TypeImpl<ZoneTypeConfig>; |
973 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Map>; | 1099 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Map>; |
974 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Object>; | 1100 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Object>; |
975 | 1101 |
976 template class TypeImpl<HeapTypeConfig>; | 1102 template class TypeImpl<HeapTypeConfig>; |
977 template class TypeImpl<HeapTypeConfig>::Iterator<i::Map>; | 1103 template class TypeImpl<HeapTypeConfig>::Iterator<i::Map>; |
978 template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>; | 1104 template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>; |
979 | 1105 |
980 template TypeImpl<ZoneTypeConfig>::TypeHandle | 1106 template TypeImpl<ZoneTypeConfig>::TypeHandle |
981 TypeImpl<ZoneTypeConfig>::Convert<HeapType>( | 1107 TypeImpl<ZoneTypeConfig>::Convert<HeapType>( |
982 TypeImpl<HeapTypeConfig>::TypeHandle, TypeImpl<ZoneTypeConfig>::Region*); | 1108 TypeImpl<HeapTypeConfig>::TypeHandle, TypeImpl<ZoneTypeConfig>::Region*); |
983 template TypeImpl<HeapTypeConfig>::TypeHandle | 1109 template TypeImpl<HeapTypeConfig>::TypeHandle |
984 TypeImpl<HeapTypeConfig>::Convert<Type>( | 1110 TypeImpl<HeapTypeConfig>::Convert<Type>( |
985 TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*); | 1111 TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*); |
986 | 1112 |
987 } } // namespace v8::internal | 1113 } } // namespace v8::internal |
OLD | NEW |