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