diff options
Diffstat (limited to 'chromium/v8/src/types.cc')
| -rw-r--r-- | chromium/v8/src/types.cc | 1143 |
1 files changed, 774 insertions, 369 deletions
diff --git a/chromium/v8/src/types.cc b/chromium/v8/src/types.cc index 485ba885187..22694c06e84 100644 --- a/chromium/v8/src/types.cc +++ b/chromium/v8/src/types.cc @@ -1,155 +1,159 @@ -// Copyright 2013 the V8 project authors. All rights reserved. -// Redistribution and use in source and binary forms, with or without -// modification, are permitted provided that the following conditions are -// met: -// -// * Redistributions of source code must retain the above copyright -// notice, this list of conditions and the following disclaimer. -// * Redistributions in binary form must reproduce the above -// copyright notice, this list of conditions and the following -// disclaimer in the documentation and/or other materials provided -// with the distribution. -// * Neither the name of Google Inc. nor the names of its -// contributors may be used to endorse or promote products derived -// from this software without specific prior written permission. -// -// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS -// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT -// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR -// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT -// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, -// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT -// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, -// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY -// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT -// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - -#include "types.h" -#include "string-stream.h" +// Copyright 2014 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "src/types.h" + +#include "src/string-stream.h" +#include "src/types-inl.h" namespace v8 { namespace internal { -int Type::NumClasses() { - if (is_class()) { - return 1; - } else if (is_union()) { - Handle<Unioned> unioned = as_union(); - int result = 0; - for (int i = 0; i < unioned->length(); ++i) { - if (union_get(unioned, i)->is_class()) ++result; +// ----------------------------------------------------------------------------- +// Glb and lub computation. + +// The largest bitset subsumed by this type. +template<class Config> +int TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) { + DisallowHeapAllocation no_allocation; + if (type->IsBitset()) { + return type->AsBitset(); + } else if (type->IsUnion()) { + UnionHandle unioned = handle(type->AsUnion()); + int bitset = kNone; + for (int i = 0; i < unioned->Length(); ++i) { + bitset |= unioned->Get(i)->BitsetGlb(); } - return result; + return bitset; + } else if (type->IsClass()) { + // Little hack to avoid the need for a region for handlification here... + return REPRESENTATION(Config::is_class(type) + ? Lub(*Config::as_class(type)) + : type->AsClass()->Bound(NULL)->AsBitset()); + } else if (type->IsConstant()) { + return REPRESENTATION(type->AsConstant()->Bound()->AsBitset()); + } else if (type->IsContext()) { + return REPRESENTATION(type->AsContext()->Bound()->AsBitset()); + } else if (type->IsArray()) { + return REPRESENTATION(type->AsArray()->Bound()->AsBitset()); + } else if (type->IsFunction()) { + return REPRESENTATION(type->AsFunction()->Bound()->AsBitset()); } else { - return 0; + UNREACHABLE(); + return kNone; } } -int Type::NumConstants() { - if (is_constant()) { - return 1; - } else if (is_union()) { - Handle<Unioned> unioned = as_union(); - int result = 0; - for (int i = 0; i < unioned->length(); ++i) { - if (union_get(unioned, i)->is_constant()) ++result; +// The smallest bitset subsuming this type. +template<class Config> +int TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) { + DisallowHeapAllocation no_allocation; + if (type->IsBitset()) { + return type->AsBitset(); + } else if (type->IsUnion()) { + UnionHandle unioned = handle(type->AsUnion()); + int bitset = kNone; + for (int i = 0; i < unioned->Length(); ++i) { + bitset |= unioned->Get(i)->BitsetLub(); } - return result; + return bitset; + } else if (type->IsClass()) { + // Little hack to avoid the need for a region for handlification here... + return Config::is_class(type) ? Lub(*Config::as_class(type)) : + type->AsClass()->Bound(NULL)->AsBitset(); + } else if (type->IsConstant()) { + return type->AsConstant()->Bound()->AsBitset(); + } else if (type->IsContext()) { + return type->AsContext()->Bound()->AsBitset(); + } else if (type->IsArray()) { + return type->AsArray()->Bound()->AsBitset(); + } else if (type->IsFunction()) { + return type->AsFunction()->Bound()->AsBitset(); } else { - return 0; + UNREACHABLE(); + return kNone; } } -template<class T> -Handle<Type> Type::Iterator<T>::get_type() { - ASSERT(!Done()); - return type_->is_union() ? union_get(type_->as_union(), index_) : type_; -} - -template<> -Handle<i::Map> Type::Iterator<i::Map>::Current() { - return get_type()->as_class(); -} - -template<> -Handle<i::Object> Type::Iterator<i::Object>::Current() { - return get_type()->as_constant(); +// The smallest bitset subsuming this type, ignoring explicit bounds. +template<class Config> +int TypeImpl<Config>::BitsetType::InherentLub(TypeImpl* type) { + DisallowHeapAllocation no_allocation; + if (type->IsBitset()) { + return type->AsBitset(); + } else if (type->IsUnion()) { + UnionHandle unioned = handle(type->AsUnion()); + int bitset = kNone; + for (int i = 0; i < unioned->Length(); ++i) { + bitset |= unioned->Get(i)->InherentBitsetLub(); + } + return bitset; + } else if (type->IsClass()) { + return Lub(*type->AsClass()->Map()); + } else if (type->IsConstant()) { + return Lub(*type->AsConstant()->Value()); + } else if (type->IsContext()) { + return kInternal & kTaggedPtr; + } else if (type->IsArray()) { + return kArray; + } else if (type->IsFunction()) { + return kFunction; + } else { + UNREACHABLE(); + return kNone; + } } -template<> -bool Type::Iterator<i::Map>::matches(Handle<Type> type) { - return type->is_class(); -} - -template<> -bool Type::Iterator<i::Object>::matches(Handle<Type> type) { - return type->is_constant(); +template<class Config> +int TypeImpl<Config>::BitsetType::Lub(i::Object* value) { + DisallowHeapAllocation no_allocation; + if (value->IsNumber()) { + return Lub(value->Number()) & (value->IsSmi() ? kTaggedInt : kTaggedPtr); + } + return Lub(i::HeapObject::cast(value)->map()); } -template<class T> -void Type::Iterator<T>::Advance() { - ++index_; - if (type_->is_union()) { - Handle<Unioned> unioned = type_->as_union(); - for (; index_ < unioned->length(); ++index_) { - if (matches(union_get(unioned, index_))) return; - } - } else if (index_ == 0 && matches(type_)) { - return; - } - index_ = -1; +template<class Config> +int TypeImpl<Config>::BitsetType::Lub(double value) { + DisallowHeapAllocation no_allocation; + if (i::IsMinusZero(value)) return kMinusZero; + if (std::isnan(value)) return kNaN; + if (IsUint32Double(value)) return Lub(FastD2UI(value)); + if (IsInt32Double(value)) return Lub(FastD2I(value)); + return kOtherNumber; } -template class Type::Iterator<i::Map>; -template class Type::Iterator<i::Object>; - -// Get the smallest bitset subsuming this type. -int Type::LubBitset() { - if (this->is_bitset()) { - return this->as_bitset(); - } else if (this->is_union()) { - Handle<Unioned> unioned = this->as_union(); - int bitset = kNone; - for (int i = 0; i < unioned->length(); ++i) { - bitset |= union_get(unioned, i)->LubBitset(); - } - return bitset; - } else if (this->is_class()) { - return LubBitset(*this->as_class()); - } else { - return LubBitset(*this->as_constant()); +template<class Config> +int TypeImpl<Config>::BitsetType::Lub(int32_t value) { + if (value >= 0x40000000) { + return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall; } + if (value >= 0) return kUnsignedSmall; + if (value >= -0x40000000) return kOtherSignedSmall; + return i::SmiValuesAre31Bits() ? kOtherSigned32 : kOtherSignedSmall; } -int Type::LubBitset(i::Object* value) { - if (value->IsSmi()) return kSmi; - i::Map* map = i::HeapObject::cast(value)->map(); - if (map->instance_type() == HEAP_NUMBER_TYPE) { - int32_t i; - uint32_t u; - if (value->ToInt32(&i)) return Smi::IsValid(i) ? kSmi : kOtherSigned32; - if (value->ToUint32(&u)) return kUnsigned32; - return kDouble; +template<class Config> +int TypeImpl<Config>::BitsetType::Lub(uint32_t value) { + DisallowHeapAllocation no_allocation; + if (value >= 0x80000000u) return kOtherUnsigned32; + if (value >= 0x40000000u) { + return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall; } - if (map->instance_type() == ODDBALL_TYPE) { - if (value->IsUndefined()) return kUndefined; - if (value->IsNull()) return kNull; - if (value->IsBoolean()) return kBoolean; - if (value->IsTheHole()) return kAny; // TODO(rossberg): kNone? - UNREACHABLE(); - } - return Type::LubBitset(map); + return kUnsignedSmall; } -int Type::LubBitset(i::Map* map) { +template<class Config> +int TypeImpl<Config>::BitsetType::Lub(i::Map* map) { + DisallowHeapAllocation no_allocation; switch (map->instance_type()) { case STRING_TYPE: case ASCII_STRING_TYPE: @@ -165,8 +169,6 @@ int Type::LubBitset(i::Map* map) { case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: case INTERNALIZED_STRING_TYPE: case ASCII_INTERNALIZED_STRING_TYPE: - case CONS_INTERNALIZED_STRING_TYPE: - case CONS_ASCII_INTERNALIZED_STRING_TYPE: case EXTERNAL_INTERNALIZED_STRING_TYPE: case EXTERNAL_ASCII_INTERNALIZED_STRING_TYPE: case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE: @@ -176,10 +178,20 @@ int Type::LubBitset(i::Map* map) { return kString; case SYMBOL_TYPE: return kSymbol; - case ODDBALL_TYPE: - return kOddball; + case ODDBALL_TYPE: { + Heap* heap = map->GetHeap(); + if (map == heap->undefined_map()) return kUndefined; + if (map == heap->the_hole_map()) return kAny; // TODO(rossberg): kNone? + if (map == heap->null_map()) return kNull; + if (map == heap->boolean_map()) return kBoolean; + ASSERT(map == heap->uninitialized_map() || + map == heap->no_interceptor_result_sentinel_map() || + map == heap->termination_exception_map() || + map == heap->arguments_marker_map()); + return kInternal & kTaggedPtr; + } case HEAP_NUMBER_TYPE: - return kDouble; + return kNumber & kTaggedPtr; case JS_VALUE_TYPE: case JS_DATE_TYPE: case JS_OBJECT_TYPE: @@ -194,6 +206,8 @@ int Type::LubBitset(i::Map* map) { case JS_DATA_VIEW_TYPE: case JS_SET_TYPE: case JS_MAP_TYPE: + case JS_SET_ITERATOR_TYPE: + case JS_MAP_ITERATOR_TYPE: case JS_WEAK_MAP_TYPE: case JS_WEAK_SET_TYPE: if (map->is_undetectable()) return kUndetectable; @@ -220,9 +234,11 @@ int Type::LubBitset(i::Map* map) { return kDetectable; case DECLARED_ACCESSOR_INFO_TYPE: case EXECUTABLE_ACCESSOR_INFO_TYPE: + case SHARED_FUNCTION_INFO_TYPE: case ACCESSOR_PAIR_TYPE: case FIXED_ARRAY_TYPE: - return kInternal; + case FOREIGN_TYPE: + return kInternal & kTaggedPtr; default: UNREACHABLE(); return kNone; @@ -230,65 +246,79 @@ int Type::LubBitset(i::Map* map) { } -// Get the largest bitset subsumed by this type. -int Type::GlbBitset() { - if (this->is_bitset()) { - return this->as_bitset(); - } else if (this->is_union()) { - // All but the first are non-bitsets and thus would yield kNone anyway. - return union_get(this->as_union(), 0)->GlbBitset(); - } else { - return kNone; - } -} - - -// Most precise _current_ type of a value (usually its class). -Type* Type::OfCurrently(Handle<i::Object> value) { - if (value->IsSmi()) return Smi(); - i::Map* map = i::HeapObject::cast(*value)->map(); - if (map->instance_type() == HEAP_NUMBER_TYPE || - map->instance_type() == ODDBALL_TYPE) { - return Type::Of(value); - } - return Class(i::handle(map)); -} - +// ----------------------------------------------------------------------------- +// Predicates. // Check this <= that. -bool Type::SlowIs(Type* that) { - // Fast path for bitsets. - if (this->is_none()) return true; - if (that->is_bitset()) { - return (this->LubBitset() | that->as_bitset()) == that->as_bitset(); - } +template<class Config> +bool TypeImpl<Config>::SlowIs(TypeImpl* that) { + DisallowHeapAllocation no_allocation; - if (that->is_class()) { - return this->is_class() && *this->as_class() == *that->as_class(); - } - if (that->is_constant()) { - return this->is_constant() && *this->as_constant() == *that->as_constant(); + // Fast path for bitsets. + if (this->IsNone()) return true; + if (that->IsBitset()) { + return (BitsetType::Lub(this) | that->AsBitset()) == that->AsBitset(); + } + if (this->IsBitset() && SEMANTIC(this->AsBitset()) == BitsetType::kNone) { + // Bitsets only have non-bitset supertypes along the representation axis. + int that_bitset = that->BitsetGlb(); + return (this->AsBitset() | that_bitset) == that_bitset; + } + + if (that->IsClass()) { + return this->IsClass() + && *this->AsClass()->Map() == *that->AsClass()->Map() + && ((Config::is_class(that) && Config::is_class(this)) || + BitsetType::New(this->BitsetLub())->Is( + BitsetType::New(that->BitsetLub()))); + } + if (that->IsConstant()) { + return this->IsConstant() + && *this->AsConstant()->Value() == *that->AsConstant()->Value() + && this->AsConstant()->Bound()->Is(that->AsConstant()->Bound()); + } + if (that->IsContext()) { + return this->IsContext() + && this->AsContext()->Outer()->Equals(that->AsContext()->Outer()); + } + if (that->IsArray()) { + return this->IsArray() + && this->AsArray()->Element()->Equals(that->AsArray()->Element()); + } + if (that->IsFunction()) { + // We currently do not allow for any variance here, in order to keep + // Union and Intersect operations simple. + if (!this->IsFunction()) return false; + FunctionType* this_fun = this->AsFunction(); + FunctionType* that_fun = that->AsFunction(); + if (this_fun->Arity() != that_fun->Arity() || + !this_fun->Result()->Equals(that_fun->Result()) || + !that_fun->Receiver()->Equals(this_fun->Receiver())) { + return false; + } + for (int i = 0; i < this_fun->Arity(); ++i) { + if (!that_fun->Parameter(i)->Equals(this_fun->Parameter(i))) return false; + } + return true; } // (T1 \/ ... \/ Tn) <= T <=> (T1 <= T) /\ ... /\ (Tn <= T) - if (this->is_union()) { - Handle<Unioned> unioned = this->as_union(); - for (int i = 0; i < unioned->length(); ++i) { - Handle<Type> this_i = union_get(unioned, i); - if (!this_i->Is(that)) return false; + if (this->IsUnion()) { + UnionHandle unioned = handle(this->AsUnion()); + for (int i = 0; i < unioned->Length(); ++i) { + if (!unioned->Get(i)->Is(that)) return false; } return true; } // T <= (T1 \/ ... \/ Tn) <=> (T <= T1) \/ ... \/ (T <= Tn) // (iff T is not a union) - ASSERT(!this->is_union()); - if (that->is_union()) { - Handle<Unioned> unioned = that->as_union(); - for (int i = 0; i < unioned->length(); ++i) { - Handle<Type> that_i = union_get(unioned, i); - if (this->Is(that_i)) return true; - if (this->is_bitset()) break; // Fast fail, no other field is a bitset. + ASSERT(!this->IsUnion()); + if (that->IsUnion()) { + UnionHandle unioned = handle(that->AsUnion()); + for (int i = 0; i < unioned->Length(); ++i) { + if (this->Is(unioned->Get(i))) return true; + if (this->IsBitset()) break; // Fast fail, only first field is a bitset. } return false; } @@ -297,291 +327,666 @@ bool Type::SlowIs(Type* that) { } -bool Type::IsCurrently(Type* that) { - return this->Is(that) || - (this->is_constant() && that->is_class() && - this->as_constant()->IsHeapObject() && - i::HeapObject::cast(*this->as_constant())->map() == *that->as_class()); +template<class Config> +bool TypeImpl<Config>::NowIs(TypeImpl* that) { + DisallowHeapAllocation no_allocation; + + // TODO(rossberg): this is incorrect for + // Union(Constant(V), T)->NowIs(Class(M)) + // but fuzzing does not cover that! + if (this->IsConstant()) { + i::Object* object = *this->AsConstant()->Value(); + if (object->IsHeapObject()) { + i::Map* map = i::HeapObject::cast(object)->map(); + for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) { + if (*it.Current() == map) return true; + } + } + } + return this->Is(that); } -// Check this overlaps that. -bool Type::Maybe(Type* that) { - // Fast path for bitsets. - if (this->is_bitset()) { - return (this->as_bitset() & that->LubBitset()) != 0; - } - if (that->is_bitset()) { - return (this->LubBitset() & that->as_bitset()) != 0; +// Check if this contains only (currently) stable classes. +template<class Config> +bool TypeImpl<Config>::NowStable() { + DisallowHeapAllocation no_allocation; + for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) { + if (!it.Current()->is_stable()) return false; } + return true; +} + + +// Check this overlaps that. +template<class Config> +bool TypeImpl<Config>::Maybe(TypeImpl* that) { + DisallowHeapAllocation no_allocation; // (T1 \/ ... \/ Tn) overlaps T <=> (T1 overlaps T) \/ ... \/ (Tn overlaps T) - if (this->is_union()) { - Handle<Unioned> unioned = this->as_union(); - for (int i = 0; i < unioned->length(); ++i) { - Handle<Type> this_i = union_get(unioned, i); - if (this_i->Maybe(that)) return true; + if (this->IsUnion()) { + UnionHandle unioned = handle(this->AsUnion()); + for (int i = 0; i < unioned->Length(); ++i) { + if (unioned->Get(i)->Maybe(that)) return true; } return false; } // T overlaps (T1 \/ ... \/ Tn) <=> (T overlaps T1) \/ ... \/ (T overlaps Tn) - if (that->is_union()) { - Handle<Unioned> unioned = that->as_union(); - for (int i = 0; i < unioned->length(); ++i) { - Handle<Type> that_i = union_get(unioned, i); - if (this->Maybe(that_i)) return true; + if (that->IsUnion()) { + UnionHandle unioned = handle(that->AsUnion()); + for (int i = 0; i < unioned->Length(); ++i) { + if (this->Maybe(unioned->Get(i))) return true; } return false; } - ASSERT(!that->is_union()); - if (this->is_class()) { - return that->is_class() && *this->as_class() == *that->as_class(); + ASSERT(!this->IsUnion() && !that->IsUnion()); + if (this->IsBitset()) { + return BitsetType::IsInhabited(this->AsBitset() & that->BitsetLub()); + } + if (that->IsBitset()) { + return BitsetType::IsInhabited(this->BitsetLub() & that->AsBitset()); } - if (this->is_constant()) { - return that->is_constant() && *this->as_constant() == *that->as_constant(); + if (this->IsClass()) { + return that->IsClass() + && *this->AsClass()->Map() == *that->AsClass()->Map(); + } + if (this->IsConstant()) { + return that->IsConstant() + && *this->AsConstant()->Value() == *that->AsConstant()->Value(); + } + if (this->IsContext()) { + return this->Equals(that); + } + if (this->IsArray()) { + // There is no variance! + return this->Equals(that); + } + if (this->IsFunction()) { + // There is no variance! + return this->Equals(that); } return false; } -bool Type::InUnion(Handle<Unioned> unioned, int current_size) { - ASSERT(!this->is_union()); +// Check if value is contained in (inhabits) type. +template<class Config> +bool TypeImpl<Config>::Contains(i::Object* value) { + DisallowHeapAllocation no_allocation; + for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) { + if (*it.Current() == value) return true; + } + return BitsetType::New(BitsetType::Lub(value))->Is(this); +} + + +template<class Config> +bool TypeImpl<Config>::UnionType::Wellformed() { + ASSERT(this->Length() >= 2); + for (int i = 0; i < this->Length(); ++i) { + ASSERT(!this->Get(i)->IsUnion()); + if (i > 0) ASSERT(!this->Get(i)->IsBitset()); + for (int j = 0; j < this->Length(); ++j) { + if (i != j) ASSERT(!this->Get(i)->Is(this->Get(j))); + } + } + return true; +} + + +// ----------------------------------------------------------------------------- +// Union and intersection + +template<class Config> +typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Narrow( + int bitset, Region* region) { + TypeHandle bound = BitsetType::New(bitset, region); + if (this->IsClass()) { + return ClassType::New(this->AsClass()->Map(), bound, region); + } else if (this->IsConstant()) { + return ConstantType::New(this->AsConstant()->Value(), bound, region); + } else if (this->IsContext()) { + return ContextType::New(this->AsContext()->Outer(), bound, region); + } else if (this->IsArray()) { + return ArrayType::New(this->AsArray()->Element(), bound, region); + } else if (this->IsFunction()) { + FunctionType* function = this->AsFunction(); + int arity = function->Arity(); + FunctionHandle type = FunctionType::New( + function->Result(), function->Receiver(), bound, arity, region); + for (int i = 0; i < arity; ++i) { + type->InitParameter(i, function->Parameter(i)); + } + return type; + } + UNREACHABLE(); + return TypeHandle(); +} + + +template<class Config> +int TypeImpl<Config>::BoundBy(TypeImpl* that) { + ASSERT(!this->IsUnion()); + if (that->IsUnion()) { + UnionType* unioned = that->AsUnion(); + int length = unioned->Length(); + int bitset = BitsetType::kNone; + for (int i = 0; i < length; ++i) { + bitset |= BoundBy(unioned->Get(i)->unhandle()); + } + return bitset; + } else if (that->IsClass() && this->IsClass() && + *this->AsClass()->Map() == *that->AsClass()->Map()) { + return that->BitsetLub(); + } else if (that->IsConstant() && this->IsConstant() && + *this->AsConstant()->Value() == *that->AsConstant()->Value()) { + return that->AsConstant()->Bound()->AsBitset(); + } else if (that->IsContext() && this->IsContext() && this->Is(that)) { + return that->AsContext()->Bound()->AsBitset(); + } else if (that->IsArray() && this->IsArray() && this->Is(that)) { + return that->AsArray()->Bound()->AsBitset(); + } else if (that->IsFunction() && this->IsFunction() && this->Is(that)) { + return that->AsFunction()->Bound()->AsBitset(); + } + return that->BitsetGlb(); +} + + +template<class Config> +int TypeImpl<Config>::IndexInUnion( + int bound, UnionHandle unioned, int current_size) { + ASSERT(!this->IsUnion()); for (int i = 0; i < current_size; ++i) { - Handle<Type> type = union_get(unioned, i); - if (this->Is(type)) return true; + TypeHandle that = unioned->Get(i); + if (that->IsBitset()) { + if ((bound | that->AsBitset()) == that->AsBitset()) return i; + } else if (that->IsClass() && this->IsClass()) { + if (*this->AsClass()->Map() == *that->AsClass()->Map()) return i; + } else if (that->IsConstant() && this->IsConstant()) { + if (*this->AsConstant()->Value() == *that->AsConstant()->Value()) + return i; + } else if (that->IsContext() && this->IsContext()) { + if (this->Is(that)) return i; + } else if (that->IsArray() && this->IsArray()) { + if (this->Is(that)) return i; + } else if (that->IsFunction() && this->IsFunction()) { + if (this->Is(that)) return i; + } } - return false; + return -1; } -// Get non-bitsets from this which are not subsumed by union, store at unioned, -// starting at index. Returns updated index. -int Type::ExtendUnion(Handle<Unioned> result, int current_size) { - int old_size = current_size; - if (this->is_class() || this->is_constant()) { - if (!this->InUnion(result, old_size)) result->set(current_size++, this); - } else if (this->is_union()) { - Handle<Unioned> unioned = this->as_union(); - for (int i = 0; i < unioned->length(); ++i) { - Handle<Type> type = union_get(unioned, i); - ASSERT(i == 0 || !(type->is_bitset() || type->Is(union_get(unioned, 0)))); - if (type->is_bitset()) continue; - if (!type->InUnion(result, old_size)) result->set(current_size++, *type); +// Get non-bitsets from type, bounded by upper. +// Store at result starting at index. Returns updated index. +template<class Config> +int TypeImpl<Config>::ExtendUnion( + UnionHandle result, int size, TypeHandle type, + TypeHandle other, bool is_intersect, Region* region) { + int old_size = size; + if (type->IsUnion()) { + UnionHandle unioned = handle(type->AsUnion()); + for (int i = 0; i < unioned->Length(); ++i) { + TypeHandle type_i = unioned->Get(i); + ASSERT(i == 0 || !(type_i->IsBitset() || type_i->Is(unioned->Get(0)))); + if (!type_i->IsBitset()) { + size = ExtendUnion(result, size, type_i, other, is_intersect, region); + } + } + } else if (!type->IsBitset()) { + ASSERT(type->IsClass() || type->IsConstant() || + type->IsArray() || type->IsFunction() || type->IsContext()); + int inherent_bound = type->InherentBitsetLub(); + int old_bound = type->BitsetLub(); + int other_bound = type->BoundBy(other->unhandle()) & inherent_bound; + int new_bound = + is_intersect ? (old_bound & other_bound) : (old_bound | other_bound); + if (new_bound != BitsetType::kNone) { + int i = type->IndexInUnion(new_bound, result, old_size); + if (i == -1) { + i = size++; + } else if (result->Get(i)->IsBitset()) { + return size; // Already fully subsumed. + } else { + int type_i_bound = result->Get(i)->BitsetLub(); + new_bound |= type_i_bound; + if (new_bound == type_i_bound) return size; + } + if (new_bound != old_bound) type = type->Narrow(new_bound, region); + result->Set(i, type); } } - return current_size; + return size; } -// Union is O(1) on simple bit unions, but O(n*m) on structured unions. -// TODO(rossberg): Should we use object sets somehow? Is it worth it? -Type* Type::Union(Handle<Type> type1, Handle<Type> type2) { +// If bitset is subsumed by another entry in the result, remove it. +// (Only bitsets with empty semantic axis can be subtypes of non-bitsets.) +template<class Config> +int TypeImpl<Config>::NormalizeUnion(UnionHandle result, int size, int bitset) { + if (bitset != BitsetType::kNone && SEMANTIC(bitset) == BitsetType::kNone) { + for (int i = 1; i < size; ++i) { + int glb = result->Get(i)->BitsetGlb(); + if ((bitset | glb) == glb) { + for (int j = 1; j < size; ++j) { + result->Set(j - 1, result->Get(j)); + } + --size; + break; + } + } + } + return size; +} + + +// Union is O(1) on simple bitsets, but O(n*m) on structured unions. +template<class Config> +typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union( + TypeHandle type1, TypeHandle type2, Region* region) { // Fast case: bit sets. - if (type1->is_bitset() && type2->is_bitset()) { - return from_bitset(type1->as_bitset() | type2->as_bitset()); + if (type1->IsBitset() && type2->IsBitset()) { + return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region); } // Fast case: top or bottom types. - if (type1->SameValue(Type::Any())) return *type1; - if (type2->SameValue(Type::Any())) return *type2; - if (type1->SameValue(Type::None())) return *type2; - if (type2->SameValue(Type::None())) return *type1; + if (type1->IsAny() || type2->IsNone()) return type1; + if (type2->IsAny() || type1->IsNone()) return type2; // Semi-fast case: Unioned objects are neither involved nor produced. - if (!(type1->is_union() || type2->is_union())) { - if (type1->Is(type2)) return *type2; - if (type2->Is(type1)) return *type1; + if (!(type1->IsUnion() || type2->IsUnion())) { + if (type1->Is(type2)) return type2; + if (type2->Is(type1)) return type1; } // Slow case: may need to produce a Unioned object. - Isolate* isolate = NULL; - int size = type1->is_bitset() || type2->is_bitset() ? 1 : 0; - if (!type1->is_bitset()) { - isolate = i::HeapObject::cast(*type1)->GetIsolate(); - size += (type1->is_union() ? type1->as_union()->length() : 1); - } - if (!type2->is_bitset()) { - isolate = i::HeapObject::cast(*type2)->GetIsolate(); - size += (type2->is_union() ? type2->as_union()->length() : 1); - } - ASSERT(isolate != NULL); - ASSERT(size >= 2); - Handle<Unioned> unioned = isolate->factory()->NewFixedArray(size); - size = 0; + int size = 0; + if (!type1->IsBitset()) { + size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1); + } + if (!type2->IsBitset()) { + size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1); + } + int bitset = type1->BitsetGlb() | type2->BitsetGlb(); + if (bitset != BitsetType::kNone) ++size; + ASSERT(size >= 1); - int bitset = type1->GlbBitset() | type2->GlbBitset(); - if (bitset != kNone) unioned->set(size++, from_bitset(bitset)); - size = type1->ExtendUnion(unioned, size); - size = type2->ExtendUnion(unioned, size); + UnionHandle unioned = UnionType::New(size, region); + size = 0; + if (bitset != BitsetType::kNone) { + unioned->Set(size++, BitsetType::New(bitset, region)); + } + size = ExtendUnion(unioned, size, type1, type2, false, region); + size = ExtendUnion(unioned, size, type2, type1, false, region); + size = NormalizeUnion(unioned, size, bitset); if (size == 1) { - return *union_get(unioned, 0); - } else if (size == unioned->length()) { - return from_handle(unioned); - } - - // There was an overlap. Copy to smaller union. - Handle<Unioned> result = isolate->factory()->NewFixedArray(size); - for (int i = 0; i < size; ++i) result->set(i, unioned->get(i)); - return from_handle(result); -} - - -// Get non-bitsets from this which are also in that, store at unioned, -// starting at index. Returns updated index. -int Type::ExtendIntersection( - Handle<Unioned> result, Handle<Type> that, int current_size) { - int old_size = current_size; - if (this->is_class() || this->is_constant()) { - if (this->Is(that) && !this->InUnion(result, old_size)) - result->set(current_size++, this); - } else if (this->is_union()) { - Handle<Unioned> unioned = this->as_union(); - for (int i = 0; i < unioned->length(); ++i) { - Handle<Type> type = union_get(unioned, i); - ASSERT(i == 0 || !(type->is_bitset() || type->Is(union_get(unioned, 0)))); - if (type->is_bitset()) continue; - if (type->Is(that) && !type->InUnion(result, old_size)) - result->set(current_size++, *type); - } + return unioned->Get(0); + } else { + unioned->Shrink(size); + ASSERT(unioned->Wellformed()); + return unioned; } - return current_size; } -// Intersection is O(1) on simple bit unions, but O(n*m) on structured unions. -// TODO(rossberg): Should we use object sets somehow? Is it worth it? -Type* Type::Intersect(Handle<Type> type1, Handle<Type> type2) { +// Intersection is O(1) on simple bitsets, but O(n*m) on structured unions. +template<class Config> +typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect( + TypeHandle type1, TypeHandle type2, Region* region) { // Fast case: bit sets. - if (type1->is_bitset() && type2->is_bitset()) { - return from_bitset(type1->as_bitset() & type2->as_bitset()); + if (type1->IsBitset() && type2->IsBitset()) { + return BitsetType::New(type1->AsBitset() & type2->AsBitset(), region); } // Fast case: top or bottom types. - if (type1->SameValue(Type::None())) return *type1; - if (type2->SameValue(Type::None())) return *type2; - if (type1->SameValue(Type::Any())) return *type2; - if (type2->SameValue(Type::Any())) return *type1; + if (type1->IsNone() || type2->IsAny()) return type1; + if (type2->IsNone() || type1->IsAny()) return type2; // Semi-fast case: Unioned objects are neither involved nor produced. - if (!(type1->is_union() || type2->is_union())) { - if (type1->Is(type2)) return *type1; - if (type2->Is(type1)) return *type2; + if (!(type1->IsUnion() || type2->IsUnion())) { + if (type1->Is(type2)) return type1; + if (type2->Is(type1)) return type2; } // Slow case: may need to produce a Unioned object. - Isolate* isolate = NULL; int size = 0; - if (!type1->is_bitset()) { - isolate = i::HeapObject::cast(*type1)->GetIsolate(); - size = (type1->is_union() ? type1->as_union()->length() : 2); - } - if (!type2->is_bitset()) { - isolate = i::HeapObject::cast(*type2)->GetIsolate(); - int size2 = (type2->is_union() ? type2->as_union()->length() : 2); - size = (size == 0 ? size2 : Min(size, size2)); - } - ASSERT(isolate != NULL); - ASSERT(size >= 2); - Handle<Unioned> unioned = isolate->factory()->NewFixedArray(size); - size = 0; + if (!type1->IsBitset()) { + size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1); + } + if (!type2->IsBitset()) { + size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1); + } + int bitset = type1->BitsetGlb() & type2->BitsetGlb(); + if (bitset != BitsetType::kNone) ++size; + ASSERT(size >= 1); - int bitset = type1->GlbBitset() & type2->GlbBitset(); - if (bitset != kNone) unioned->set(size++, from_bitset(bitset)); - size = type1->ExtendIntersection(unioned, type2, size); - size = type2->ExtendIntersection(unioned, type1, size); + UnionHandle unioned = UnionType::New(size, region); + size = 0; + if (bitset != BitsetType::kNone) { + unioned->Set(size++, BitsetType::New(bitset, region)); + } + size = ExtendUnion(unioned, size, type1, type2, true, region); + size = ExtendUnion(unioned, size, type2, type1, true, region); + size = NormalizeUnion(unioned, size, bitset); if (size == 0) { - return None(); + return None(region); } else if (size == 1) { - return *union_get(unioned, 0); - } else if (size == unioned->length()) { - return from_handle(unioned); + return unioned->Get(0); + } else { + unioned->Shrink(size); + ASSERT(unioned->Wellformed()); + return unioned; } +} - // There were dropped cases. Copy to smaller union. - Handle<Unioned> result = isolate->factory()->NewFixedArray(size); - for (int i = 0; i < size; ++i) result->set(i, unioned->get(i)); - return from_handle(result); + +// ----------------------------------------------------------------------------- +// Iteration. + +template<class Config> +int TypeImpl<Config>::NumClasses() { + DisallowHeapAllocation no_allocation; + if (this->IsClass()) { + return 1; + } else if (this->IsUnion()) { + UnionHandle unioned = handle(this->AsUnion()); + int result = 0; + for (int i = 0; i < unioned->Length(); ++i) { + if (unioned->Get(i)->IsClass()) ++result; + } + return result; + } else { + return 0; + } } -Type* Type::Optional(Handle<Type> type) { - return type->is_bitset() - ? from_bitset(type->as_bitset() | kUndefined) - : Union(type, Undefined()->handle_via_isolate_of(*type)); +template<class Config> +int TypeImpl<Config>::NumConstants() { + DisallowHeapAllocation no_allocation; + if (this->IsConstant()) { + return 1; + } else if (this->IsUnion()) { + UnionHandle unioned = handle(this->AsUnion()); + int result = 0; + for (int i = 0; i < unioned->Length(); ++i) { + if (unioned->Get(i)->IsConstant()) ++result; + } + return result; + } else { + return 0; + } } -Representation Representation::FromType(Handle<Type> type) { - if (type->Is(Type::None())) return Representation::None(); - if (type->Is(Type::Smi())) return Representation::Smi(); - if (type->Is(Type::Signed32())) return Representation::Integer32(); - if (type->Is(Type::Number())) return Representation::Double(); - return Representation::Tagged(); +template<class Config> template<class T> +typename TypeImpl<Config>::TypeHandle +TypeImpl<Config>::Iterator<T>::get_type() { + ASSERT(!Done()); + return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_; } -#ifdef OBJECT_PRINT -void Type::TypePrint() { - TypePrint(stdout); - PrintF(stdout, "\n"); - Flush(stdout); +// C++ cannot specialise nested templates, so we have to go through this +// contortion with an auxiliary template to simulate it. +template<class Config, class T> +struct TypeImplIteratorAux { + static bool matches(typename TypeImpl<Config>::TypeHandle type); + static i::Handle<T> current(typename TypeImpl<Config>::TypeHandle type); +}; + +template<class Config> +struct TypeImplIteratorAux<Config, i::Map> { + static bool matches(typename TypeImpl<Config>::TypeHandle type) { + return type->IsClass(); + } + static i::Handle<i::Map> current(typename TypeImpl<Config>::TypeHandle type) { + return type->AsClass()->Map(); + } +}; + +template<class Config> +struct TypeImplIteratorAux<Config, i::Object> { + static bool matches(typename TypeImpl<Config>::TypeHandle type) { + return type->IsConstant(); + } + static i::Handle<i::Object> current( + typename TypeImpl<Config>::TypeHandle type) { + return type->AsConstant()->Value(); + } +}; + +template<class Config> template<class T> +bool TypeImpl<Config>::Iterator<T>::matches(TypeHandle type) { + return TypeImplIteratorAux<Config, T>::matches(type); +} + +template<class Config> template<class T> +i::Handle<T> TypeImpl<Config>::Iterator<T>::Current() { + return TypeImplIteratorAux<Config, T>::current(get_type()); } -const char* Type::bitset_name(int bitset) { +template<class Config> template<class T> +void TypeImpl<Config>::Iterator<T>::Advance() { + DisallowHeapAllocation no_allocation; + ++index_; + if (type_->IsUnion()) { + UnionHandle unioned = handle(type_->AsUnion()); + for (; index_ < unioned->Length(); ++index_) { + if (matches(unioned->Get(index_))) return; + } + } else if (index_ == 0 && matches(type_)) { + return; + } + index_ = -1; +} + + +// ----------------------------------------------------------------------------- +// Conversion between low-level representations. + +template<class Config> +template<class OtherType> +typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert( + typename OtherType::TypeHandle type, Region* region) { + if (type->IsBitset()) { + return BitsetType::New(type->AsBitset(), region); + } else if (type->IsClass()) { + return ClassType::New( + type->AsClass()->Map(), + BitsetType::New(type->BitsetLub(), region), region); + } else if (type->IsConstant()) { + return ConstantType::New( + type->AsConstant()->Value(), + Convert<OtherType>(type->AsConstant()->Bound(), region), region); + } else if (type->IsContext()) { + TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region); + return ContextType::New(outer, region); + } else if (type->IsUnion()) { + int length = type->AsUnion()->Length(); + UnionHandle unioned = UnionType::New(length, region); + for (int i = 0; i < length; ++i) { + unioned->Set(i, Convert<OtherType>(type->AsUnion()->Get(i), region)); + } + return unioned; + } else if (type->IsArray()) { + return ArrayType::New( + Convert<OtherType>(type->AsArray()->Element(), region), + Convert<OtherType>(type->AsArray()->Bound(), region), region); + } else if (type->IsFunction()) { + FunctionHandle function = FunctionType::New( + Convert<OtherType>(type->AsFunction()->Result(), region), + Convert<OtherType>(type->AsFunction()->Receiver(), region), + Convert<OtherType>(type->AsFunction()->Bound(), region), + type->AsFunction()->Arity(), region); + for (int i = 0; i < function->Arity(); ++i) { + function->InitParameter(i, + Convert<OtherType>(type->AsFunction()->Parameter(i), region)); + } + return function; + } else { + UNREACHABLE(); + return None(region); + } +} + + +// ----------------------------------------------------------------------------- +// Printing. + +template<class Config> +const char* TypeImpl<Config>::BitsetType::Name(int bitset) { switch (bitset) { - #define PRINT_COMPOSED_TYPE(type, value) case k##type: return #type; - BITSET_TYPE_LIST(PRINT_COMPOSED_TYPE) - #undef PRINT_COMPOSED_TYPE + case REPRESENTATION(kAny): return "Any"; + #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \ + case REPRESENTATION(k##type): return #type; + REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE) + #undef RETURN_NAMED_REPRESENTATION_TYPE + + #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \ + case SEMANTIC(k##type): return #type; + SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE) + #undef RETURN_NAMED_SEMANTIC_TYPE + default: return NULL; } } -void Type::TypePrint(FILE* out) { - if (is_bitset()) { - int bitset = as_bitset(); - const char* name = bitset_name(bitset); - if (name != NULL) { - PrintF(out, "%s", name); - } else { - bool is_first = true; - PrintF(out, "("); - for (int mask = 1; mask != 0; mask = mask << 1) { - if ((bitset & mask) != 0) { - if (!is_first) PrintF(out, " | "); - is_first = false; - PrintF(out, "%s", bitset_name(mask)); - } +template<class Config> +void TypeImpl<Config>::BitsetType::PrintTo(StringStream* stream, int bitset) { + DisallowHeapAllocation no_allocation; + const char* name = Name(bitset); + if (name != NULL) { + stream->Add("%s", name); + } else { + static const int named_bitsets[] = { + #define BITSET_CONSTANT(type, value) REPRESENTATION(k##type), + REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT) + #undef BITSET_CONSTANT + + #define BITSET_CONSTANT(type, value) SEMANTIC(k##type), + SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT) + #undef BITSET_CONSTANT + }; + + bool is_first = true; + stream->Add("("); + for (int i(ARRAY_SIZE(named_bitsets) - 1); bitset != 0 && i >= 0; --i) { + int subset = named_bitsets[i]; + if ((bitset & subset) == subset) { + if (!is_first) stream->Add(" | "); + is_first = false; + stream->Add("%s", Name(subset)); + bitset -= subset; } - PrintF(out, ")"); } - } else if (is_constant()) { - PrintF(out, "Constant(%p : ", static_cast<void*>(*as_constant())); - from_bitset(LubBitset())->TypePrint(out); - PrintF(")"); - } else if (is_class()) { - PrintF(out, "Class(%p < ", static_cast<void*>(*as_class())); - from_bitset(LubBitset())->TypePrint(out); - PrintF(")"); - } else if (is_union()) { - PrintF(out, "("); - Handle<Unioned> unioned = as_union(); - for (int i = 0; i < unioned->length(); ++i) { - Handle<Type> type_i = union_get(unioned, i); - if (i > 0) PrintF(out, " | "); - type_i->TypePrint(out); + ASSERT(bitset == 0); + stream->Add(")"); + } +} + + +template<class Config> +void TypeImpl<Config>::PrintTo(StringStream* stream, PrintDimension dim) { + DisallowHeapAllocation no_allocation; + if (dim != REPRESENTATION_DIM) { + if (this->IsBitset()) { + BitsetType::PrintTo(stream, SEMANTIC(this->AsBitset())); + } else if (this->IsClass()) { + stream->Add("Class(%p < ", static_cast<void*>(*this->AsClass()->Map())); + BitsetType::New(BitsetType::Lub(this))->PrintTo(stream, dim); + stream->Add(")"); + return; + } else if (this->IsConstant()) { + stream->Add("Constant(%p : ", + static_cast<void*>(*this->AsConstant()->Value())); + BitsetType::New(BitsetType::Lub(this))->PrintTo(stream, dim); + stream->Add(")"); + return; + } else if (this->IsContext()) { + stream->Add("Context("); + this->AsContext()->Outer()->PrintTo(stream, dim); + stream->Add(")"); + } else if (this->IsUnion()) { + stream->Add("("); + UnionHandle unioned = handle(this->AsUnion()); + for (int i = 0; i < unioned->Length(); ++i) { + TypeHandle type_i = unioned->Get(i); + if (i > 0) stream->Add(" | "); + type_i->PrintTo(stream, dim); + } + stream->Add(")"); + return; + } else if (this->IsArray()) { + stream->Add("Array("); + AsArray()->Element()->PrintTo(stream, dim); + stream->Add(")"); + } else if (this->IsFunction()) { + if (!this->AsFunction()->Receiver()->IsAny()) { + this->AsFunction()->Receiver()->PrintTo(stream, dim); + stream->Add("."); + } + stream->Add("("); + for (int i = 0; i < this->AsFunction()->Arity(); ++i) { + if (i > 0) stream->Add(", "); + this->AsFunction()->Parameter(i)->PrintTo(stream, dim); + } + stream->Add(")->"); + this->AsFunction()->Result()->PrintTo(stream, dim); + } else { + UNREACHABLE(); } - PrintF(out, ")"); + } + if (dim == BOTH_DIMS) { + stream->Add("/"); + } + if (dim != SEMANTIC_DIM) { + BitsetType::PrintTo(stream, REPRESENTATION(this->BitsetLub())); } } -#endif +template<class Config> +void TypeImpl<Config>::TypePrint(FILE* out, PrintDimension dim) { + HeapStringAllocator allocator; + StringStream stream(&allocator); + PrintTo(&stream, dim); + stream.OutputToFile(out); +} + + +template<class Config> +void TypeImpl<Config>::TypePrint(PrintDimension dim) { + TypePrint(stdout, dim); + PrintF(stdout, "\n"); + Flush(stdout); +} + + +// ----------------------------------------------------------------------------- +// Instantiations. + +template class TypeImpl<ZoneTypeConfig>; +template class TypeImpl<ZoneTypeConfig>::Iterator<i::Map>; +template class TypeImpl<ZoneTypeConfig>::Iterator<i::Object>; + +template class TypeImpl<HeapTypeConfig>; +template class TypeImpl<HeapTypeConfig>::Iterator<i::Map>; +template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>; + +template TypeImpl<ZoneTypeConfig>::TypeHandle + TypeImpl<ZoneTypeConfig>::Convert<HeapType>( + TypeImpl<HeapTypeConfig>::TypeHandle, TypeImpl<ZoneTypeConfig>::Region*); +template TypeImpl<HeapTypeConfig>::TypeHandle + TypeImpl<HeapTypeConfig>::Convert<Type>( + TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*); + } } // namespace v8::internal |