Upgrade V8 to version 4.9.385.28
https://chromium.googlesource.com/v8/v8/+/4.9.385.28
FPIIM-449
Change-Id: I4b2e74289d4bf3667f2f3dc8aa2e541f63e26eb4
diff --git a/src/types.cc b/src/types.cc
index c4f1bae..9261060 100644
--- a/src/types.cc
+++ b/src/types.cc
@@ -20,25 +20,32 @@
// -----------------------------------------------------------------------------
// Range-related helper functions.
-// The result may be invalid (max < min).
-template<class Config>
-typename TypeImpl<Config>::Limits TypeImpl<Config>::Intersect(
- Limits lhs, Limits rhs) {
- DisallowHeapAllocation no_allocation;
- Limits result(lhs);
- if (lhs.min->Number() < rhs.min->Number()) result.min = rhs.min;
- if (lhs.max->Number() > rhs.max->Number()) result.max = rhs.max;
- return result;
+template <class Config>
+bool TypeImpl<Config>::Limits::IsEmpty() {
+ return this->min > this->max;
}
template<class Config>
-typename TypeImpl<Config>::Limits TypeImpl<Config>::Union(
+typename TypeImpl<Config>::Limits TypeImpl<Config>::Limits::Intersect(
Limits lhs, Limits rhs) {
DisallowHeapAllocation no_allocation;
Limits result(lhs);
- if (lhs.min->Number() > rhs.min->Number()) result.min = rhs.min;
- if (lhs.max->Number() < rhs.max->Number()) result.max = rhs.max;
+ if (lhs.min < rhs.min) result.min = rhs.min;
+ if (lhs.max > rhs.max) result.max = rhs.max;
+ return result;
+}
+
+
+template <class Config>
+typename TypeImpl<Config>::Limits TypeImpl<Config>::Limits::Union(
+ Limits lhs, Limits rhs) {
+ DisallowHeapAllocation no_allocation;
+ if (lhs.IsEmpty()) return rhs;
+ if (rhs.IsEmpty()) return lhs;
+ Limits result(lhs);
+ if (lhs.min > rhs.min) result.min = rhs.min;
+ if (lhs.max < rhs.max) result.max = rhs.max;
return result;
}
@@ -48,8 +55,7 @@
typename TypeImpl<Config>::RangeType* lhs,
typename TypeImpl<Config>::RangeType* rhs) {
DisallowHeapAllocation no_allocation;
- typename TypeImpl<Config>::Limits lim = Intersect(Limits(lhs), Limits(rhs));
- return lim.min->Number() <= lim.max->Number();
+ return !Limits::Intersect(Limits(lhs), Limits(rhs)).IsEmpty();
}
@@ -58,8 +64,17 @@
typename TypeImpl<Config>::RangeType* lhs,
typename TypeImpl<Config>::RangeType* rhs) {
DisallowHeapAllocation no_allocation;
- return lhs->Min()->Number() <= rhs->Min()->Number()
- && rhs->Max()->Number() <= lhs->Max()->Number();
+ return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
+}
+
+
+template <class Config>
+bool TypeImpl<Config>::Contains(typename TypeImpl<Config>::RangeType* lhs,
+ typename TypeImpl<Config>::ConstantType* rhs) {
+ DisallowHeapAllocation no_allocation;
+ return IsInteger(*rhs->Value()) &&
+ lhs->Min() <= rhs->Value()->Number() &&
+ rhs->Value()->Number() <= lhs->Max();
}
@@ -67,9 +82,8 @@
bool TypeImpl<Config>::Contains(
typename TypeImpl<Config>::RangeType* range, i::Object* val) {
DisallowHeapAllocation no_allocation;
- return IsInteger(val)
- && range->Min()->Number() <= val->Number()
- && val->Number() <= range->Max()->Number();
+ return IsInteger(val) &&
+ range->Min() <= val->Number() && val->Number() <= range->Max();
}
@@ -78,7 +92,7 @@
template<class Config>
double TypeImpl<Config>::Min() {
- DCHECK(this->Is(Number()));
+ DCHECK(this->SemanticIs(Number()));
if (this->IsBitset()) return BitsetType::Min(this->AsBitset());
if (this->IsUnion()) {
double min = +V8_INFINITY;
@@ -87,7 +101,7 @@
}
return min;
}
- if (this->IsRange()) return this->AsRange()->Min()->Number();
+ if (this->IsRange()) return this->AsRange()->Min();
if (this->IsConstant()) return this->AsConstant()->Value()->Number();
UNREACHABLE();
return 0;
@@ -96,7 +110,7 @@
template<class Config>
double TypeImpl<Config>::Max() {
- DCHECK(this->Is(Number()));
+ DCHECK(this->SemanticIs(Number()));
if (this->IsBitset()) return BitsetType::Max(this->AsBitset());
if (this->IsUnion()) {
double max = -V8_INFINITY;
@@ -105,7 +119,7 @@
}
return max;
}
- if (this->IsRange()) return this->AsRange()->Max()->Number();
+ if (this->IsRange()) return this->AsRange()->Max();
if (this->IsConstant()) return this->AsConstant()->Value()->Number();
UNREACHABLE();
return 0;
@@ -121,41 +135,45 @@
typename TypeImpl<Config>::bitset
TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
DisallowHeapAllocation no_allocation;
+ // Fast case.
if (type->IsBitset()) {
return type->AsBitset();
} else if (type->IsUnion()) {
SLOW_DCHECK(type->AsUnion()->Wellformed());
- return type->AsUnion()->Get(0)->BitsetGlb(); // Shortcut.
- // (The remaining BitsetGlb's are None anyway).
+ return type->AsUnion()->Get(0)->BitsetGlb() |
+ SEMANTIC(type->AsUnion()->Get(1)->BitsetGlb()); // Shortcut.
+ } else if (type->IsRange()) {
+ bitset glb = SEMANTIC(
+ BitsetType::Glb(type->AsRange()->Min(), type->AsRange()->Max()));
+ return glb | REPRESENTATION(type->BitsetLub());
} else {
- return kNone;
+ return type->Representation();
}
}
-// The smallest bitset subsuming this type.
+// The smallest bitset subsuming this type, possibly not a proper one.
template<class Config>
typename TypeImpl<Config>::bitset
TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
DisallowHeapAllocation no_allocation;
if (type->IsBitset()) return type->AsBitset();
if (type->IsUnion()) {
- int bitset = kNone;
+ // Take the representation from the first element, which is always
+ // a bitset.
+ int bitset = type->AsUnion()->Get(0)->BitsetLub();
for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
- bitset |= type->AsUnion()->Get(i)->BitsetLub();
+ // Other elements only contribute their semantic part.
+ bitset |= SEMANTIC(type->AsUnion()->Get(i)->BitsetLub());
}
return bitset;
}
- 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();
- }
- if (type->IsConstant()) return type->AsConstant()->Bound()->AsBitset();
- if (type->IsRange()) return type->AsRange()->BitsetLub();
+ if (type->IsClass()) return type->AsClass()->Lub();
+ if (type->IsConstant()) return type->AsConstant()->Lub();
+ if (type->IsRange()) return type->AsRange()->Lub();
if (type->IsContext()) return kInternal & kTaggedPointer;
- if (type->IsArray()) return kArray;
- if (type->IsFunction()) return kOtherObject; // TODO(rossberg): kFunction
+ if (type->IsArray()) return kOtherObject;
+ if (type->IsFunction()) return kFunction;
UNREACHABLE();
return kNone;
}
@@ -204,34 +222,38 @@
}
case HEAP_NUMBER_TYPE:
return kNumber & kTaggedPointer;
+ case SIMD128_VALUE_TYPE:
+ return kSimd;
case JS_VALUE_TYPE:
+ case JS_MESSAGE_OBJECT_TYPE:
case JS_DATE_TYPE:
case JS_OBJECT_TYPE:
case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
case JS_GENERATOR_OBJECT_TYPE:
case JS_MODULE_TYPE:
case JS_GLOBAL_OBJECT_TYPE:
- case JS_BUILTINS_OBJECT_TYPE:
case JS_GLOBAL_PROXY_TYPE:
case JS_ARRAY_BUFFER_TYPE:
+ case JS_ARRAY_TYPE:
case JS_TYPED_ARRAY_TYPE:
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_ITERATOR_RESULT_TYPE:
case JS_WEAK_MAP_TYPE:
case JS_WEAK_SET_TYPE:
+ case JS_PROMISE_TYPE:
+ case JS_BOUND_FUNCTION_TYPE:
if (map->is_undetectable()) return kUndetectable;
return kOtherObject;
- case JS_ARRAY_TYPE:
- return kArray;
case JS_FUNCTION_TYPE:
- return kOtherObject; // TODO(rossberg): there should be a Function type.
+ if (map->is_undetectable()) return kUndetectable;
+ return kFunction;
case JS_REGEXP_TYPE:
return kOtherObject; // TODO(rossberg): there should be a RegExp type.
case JS_PROXY_TYPE:
- case JS_FUNCTION_PROXY_TYPE:
return kProxy;
case MAP_TYPE:
// When compiling stub templates, the meta map is used as a place holder
@@ -243,20 +265,58 @@
// Also, it doesn't apply elsewhere. 8-(
// We ought to find a cleaner solution for compiling stubs parameterised
// over type or class variables, esp ones with bounds...
- return kDetectable;
+ return kDetectable & kTaggedPointer;
+ case ALLOCATION_SITE_TYPE:
case DECLARED_ACCESSOR_INFO_TYPE:
case EXECUTABLE_ACCESSOR_INFO_TYPE:
case SHARED_FUNCTION_INFO_TYPE:
case ACCESSOR_PAIR_TYPE:
case FIXED_ARRAY_TYPE:
+ case FIXED_DOUBLE_ARRAY_TYPE:
case BYTE_ARRAY_TYPE:
+ case BYTECODE_ARRAY_TYPE:
+ case TRANSITION_ARRAY_TYPE:
case FOREIGN_TYPE:
+ case SCRIPT_TYPE:
case CODE_TYPE:
+ case PROPERTY_CELL_TYPE:
return kInternal & kTaggedPointer;
- default:
+
+ // Remaining instance types are unsupported for now. If any of them do
+ // require bit set types, they should get kInternal & kTaggedPointer.
+ case MUTABLE_HEAP_NUMBER_TYPE:
+ case FREE_SPACE_TYPE:
+#define FIXED_TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
+ case FIXED_##TYPE##_ARRAY_TYPE:
+
+ TYPED_ARRAYS(FIXED_TYPED_ARRAY_CASE)
+#undef FIXED_TYPED_ARRAY_CASE
+ case FILLER_TYPE:
+ case DECLARED_ACCESSOR_DESCRIPTOR_TYPE:
+ case ACCESS_CHECK_INFO_TYPE:
+ case INTERCEPTOR_INFO_TYPE:
+ case CALL_HANDLER_INFO_TYPE:
+ case FUNCTION_TEMPLATE_INFO_TYPE:
+ case OBJECT_TEMPLATE_INFO_TYPE:
+ case SIGNATURE_INFO_TYPE:
+ case TYPE_SWITCH_INFO_TYPE:
+ case ALLOCATION_MEMENTO_TYPE:
+ case CODE_CACHE_TYPE:
+ case POLYMORPHIC_CODE_CACHE_TYPE:
+ case TYPE_FEEDBACK_INFO_TYPE:
+ case ALIASED_ARGUMENTS_ENTRY_TYPE:
+ case BOX_TYPE:
+ case DEBUG_INFO_TYPE:
+ case BREAK_POINT_INFO_TYPE:
+ case CELL_TYPE:
+ case WEAK_CELL_TYPE:
+ case PROTOTYPE_INFO_TYPE:
+ case SLOPPY_BLOCK_WITH_EVAL_CONTEXT_EXTENSION_TYPE:
UNREACHABLE();
return kNone;
}
+ UNREACHABLE();
+ return kNone;
}
@@ -279,33 +339,51 @@
if (i::IsMinusZero(value)) return kMinusZero;
if (std::isnan(value)) return kNaN;
if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value);
- return kPlainNumber;
+ return kOtherNumber;
}
-// Minimum values of regular numeric bitsets when SmiValuesAre31Bits.
+// Minimum values of plain numeric bitsets.
template <class Config>
-const typename TypeImpl<Config>::BitsetType::BitsetMin
- TypeImpl<Config>::BitsetType::BitsetMins31[] = {
- {kOtherNumber, -V8_INFINITY},
- {kOtherSigned32, kMinInt},
- {kNegativeSignedSmall, -0x40000000},
- {kUnsignedSmall, 0},
- {kOtherUnsigned31, 0x40000000},
- {kOtherUnsigned32, 0x80000000},
- {kOtherNumber, static_cast<double>(kMaxUInt32) + 1}};
+const typename TypeImpl<Config>::BitsetType::Boundary
+TypeImpl<Config>::BitsetType::BoundariesArray[] = {
+ {kOtherNumber, kPlainNumber, -V8_INFINITY},
+ {kOtherSigned32, kNegative32, kMinInt},
+ {kNegative31, kNegative31, -0x40000000},
+ {kUnsigned30, kUnsigned30, 0},
+ {kOtherUnsigned31, kUnsigned31, 0x40000000},
+ {kOtherUnsigned32, kUnsigned32, 0x80000000},
+ {kOtherNumber, kPlainNumber, static_cast<double>(kMaxUInt32) + 1}};
-// Minimum values of regular numeric bitsets when SmiValuesAre32Bits.
-// OtherSigned32 and OtherUnsigned31 are empty (see the diagrams in types.h).
template <class Config>
-const typename TypeImpl<Config>::BitsetType::BitsetMin
- TypeImpl<Config>::BitsetType::BitsetMins32[] = {
- {kOtherNumber, -V8_INFINITY},
- {kNegativeSignedSmall, kMinInt},
- {kUnsignedSmall, 0},
- {kOtherUnsigned32, 0x80000000},
- {kOtherNumber, static_cast<double>(kMaxUInt32) + 1}};
+const typename TypeImpl<Config>::BitsetType::Boundary*
+TypeImpl<Config>::BitsetType::Boundaries() {
+ return BoundariesArray;
+}
+
+
+template <class Config>
+size_t TypeImpl<Config>::BitsetType::BoundariesSize() {
+ // Windows doesn't like arraysize here.
+ // return arraysize(BoundariesArray);
+ return 7;
+}
+
+
+template <class Config>
+typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::ExpandInternals(
+ typename TypeImpl<Config>::bitset bits) {
+ DisallowHeapAllocation no_allocation;
+ if (!(bits & SEMANTIC(kPlainNumber))) return bits; // Shortcut.
+ const Boundary* boundaries = Boundaries();
+ for (size_t i = 0; i < BoundariesSize(); ++i) {
+ DCHECK(BitsetType::Is(boundaries[i].internal, boundaries[i].external));
+ if (bits & SEMANTIC(boundaries[i].internal))
+ bits |= SEMANTIC(boundaries[i].external);
+ }
+ return bits;
+}
template<class Config>
@@ -313,56 +391,80 @@
TypeImpl<Config>::BitsetType::Lub(double min, double max) {
DisallowHeapAllocation no_allocation;
int lub = kNone;
- const BitsetMin* mins = BitsetMins();
+ const Boundary* mins = Boundaries();
- // Make sure the min-max range touches 0, so we are guaranteed no holes
- // in unions of valid bitsets.
- if (max < -1) max = -1;
- if (min > 0) min = 0;
-
- for (size_t i = 1; i < BitsetMinsSize(); ++i) {
+ for (size_t i = 1; i < BoundariesSize(); ++i) {
if (min < mins[i].min) {
- lub |= mins[i-1].bits;
+ lub |= mins[i-1].internal;
if (max < mins[i].min) return lub;
}
}
- return lub |= mins[BitsetMinsSize()-1].bits;
+ return lub | mins[BoundariesSize() - 1].internal;
}
-template<class Config>
+template <class Config>
+typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::NumberBits(
+ bitset bits) {
+ return SEMANTIC(bits & kPlainNumber);
+}
+
+
+template <class Config>
+typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::Glb(
+ double min, double max) {
+ DisallowHeapAllocation no_allocation;
+ int glb = kNone;
+ const Boundary* mins = Boundaries();
+
+ // If the range does not touch 0, the bound is empty.
+ if (max < -1 || min > 0) return glb;
+
+ for (size_t i = 1; i + 1 < BoundariesSize(); ++i) {
+ if (min <= mins[i].min) {
+ if (max + 1 < mins[i + 1].min) break;
+ glb |= mins[i].external;
+ }
+ }
+ // OtherNumber also contains float numbers, so it can never be
+ // in the greatest lower bound.
+ return glb & ~(SEMANTIC(kOtherNumber));
+}
+
+
+template <class Config>
double TypeImpl<Config>::BitsetType::Min(bitset bits) {
DisallowHeapAllocation no_allocation;
- DCHECK(Is(bits, kNumber));
- const BitsetMin* mins = BitsetMins();
+ DCHECK(Is(SEMANTIC(bits), kNumber));
+ const Boundary* mins = Boundaries();
bool mz = SEMANTIC(bits & kMinusZero);
- for (size_t i = 0; i < BitsetMinsSize(); ++i) {
- if (Is(SEMANTIC(mins[i].bits), bits)) {
+ for (size_t i = 0; i < BoundariesSize(); ++i) {
+ if (Is(SEMANTIC(mins[i].internal), bits)) {
return mz ? std::min(0.0, mins[i].min) : mins[i].min;
}
}
if (mz) return 0;
- return base::OS::nan_value();
+ return std::numeric_limits<double>::quiet_NaN();
}
template<class Config>
double TypeImpl<Config>::BitsetType::Max(bitset bits) {
DisallowHeapAllocation no_allocation;
- DCHECK(Is(bits, kNumber));
- const BitsetMin* mins = BitsetMins();
+ DCHECK(Is(SEMANTIC(bits), kNumber));
+ const Boundary* mins = Boundaries();
bool mz = SEMANTIC(bits & kMinusZero);
- if (BitsetType::Is(mins[BitsetMinsSize()-1].bits, bits)) {
+ if (BitsetType::Is(SEMANTIC(mins[BoundariesSize() - 1].internal), bits)) {
return +V8_INFINITY;
}
- for (size_t i = BitsetMinsSize()-1; i-- > 0; ) {
- if (Is(SEMANTIC(mins[i].bits), bits)) {
+ for (size_t i = BoundariesSize() - 1; i-- > 0;) {
+ if (Is(SEMANTIC(mins[i].internal), bits)) {
return mz ?
std::max(0.0, mins[i+1].min - 1) : mins[i+1].min - 1;
}
}
if (mz) return 0;
- return base::OS::nan_value();
+ return std::numeric_limits<double>::quiet_NaN();
}
@@ -408,22 +510,55 @@
}
+template <class Config>
+typename TypeImpl<Config>::bitset TypeImpl<Config>::Representation() {
+ return REPRESENTATION(this->BitsetLub());
+}
+
+
// Check if [this] <= [that].
template<class Config>
bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
DisallowHeapAllocation no_allocation;
+ // Fast bitset cases
if (that->IsBitset()) {
return BitsetType::Is(this->BitsetLub(), that->AsBitset());
}
+
if (this->IsBitset()) {
return BitsetType::Is(this->AsBitset(), that->BitsetGlb());
}
+ // Check the representations.
+ if (!BitsetType::Is(Representation(), that->Representation())) {
+ return false;
+ }
+
+ // Check the semantic part.
+ return SemanticIs(that);
+}
+
+
+// Check if SEMANTIC([this]) <= SEMANTIC([that]). The result of the method
+// should be independent of the representation axis of the types.
+template <class Config>
+bool TypeImpl<Config>::SemanticIs(TypeImpl* that) {
+ DisallowHeapAllocation no_allocation;
+
+ if (this == that) return true;
+
+ if (that->IsBitset()) {
+ return BitsetType::Is(SEMANTIC(this->BitsetLub()), that->AsBitset());
+ }
+ if (this->IsBitset()) {
+ return BitsetType::Is(SEMANTIC(this->AsBitset()), that->BitsetGlb());
+ }
+
// (T1 \/ ... \/ Tn) <= T if (T1 <= T) /\ ... /\ (Tn <= T)
if (this->IsUnion()) {
for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
- if (!this->AsUnion()->Get(i)->Is(that)) return false;
+ if (!this->AsUnion()->Get(i)->SemanticIs(that)) return false;
}
return true;
}
@@ -431,16 +566,16 @@
// T <= (T1 \/ ... \/ Tn) if (T <= T1) \/ ... \/ (T <= Tn)
if (that->IsUnion()) {
for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
- if (this->Is(that->AsUnion()->Get(i))) return true;
+ if (this->SemanticIs(that->AsUnion()->Get(i)->unhandle())) return true;
if (i > 1 && this->IsRange()) return false; // Shortcut.
}
return false;
}
if (that->IsRange()) {
- return (this->IsRange() && Contains(that->AsRange(), this->AsRange()))
- || (this->IsConstant() &&
- Contains(that->AsRange(), *this->AsConstant()->Value()));
+ return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) ||
+ (this->IsConstant() &&
+ Contains(that->AsRange(), this->AsConstant()));
}
if (this->IsRange()) return false;
@@ -472,10 +607,7 @@
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;
+ return !this->IsClass() || this->AsClass()->Map()->is_stable();
}
@@ -484,10 +616,22 @@
bool TypeImpl<Config>::Maybe(TypeImpl* that) {
DisallowHeapAllocation no_allocation;
+ // Take care of the representation part (and also approximate
+ // the semantic part).
+ if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
+ return false;
+
+ return SemanticMaybe(that);
+}
+
+template <class Config>
+bool TypeImpl<Config>::SemanticMaybe(TypeImpl* that) {
+ DisallowHeapAllocation no_allocation;
+
// (T1 \/ ... \/ Tn) overlaps T if (T1 overlaps T) \/ ... \/ (Tn overlaps T)
if (this->IsUnion()) {
for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
- if (this->AsUnion()->Get(i)->Maybe(that)) return true;
+ if (this->AsUnion()->Get(i)->SemanticMaybe(that)) return true;
}
return false;
}
@@ -495,30 +639,41 @@
// T overlaps (T1 \/ ... \/ Tn) if (T overlaps T1) \/ ... \/ (T overlaps Tn)
if (that->IsUnion()) {
for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
- if (this->Maybe(that->AsUnion()->Get(i))) return true;
+ if (this->SemanticMaybe(that->AsUnion()->Get(i)->unhandle())) return true;
}
return false;
}
- if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
+ if (!BitsetType::SemanticIsInhabited(this->BitsetLub() & that->BitsetLub()))
return false;
- if (this->IsBitset() || that->IsBitset()) return true;
+
+ if (this->IsBitset() && that->IsBitset()) return true;
if (this->IsClass() != that->IsClass()) return true;
if (this->IsRange()) {
if (that->IsConstant()) {
- return Contains(this->AsRange(), *that->AsConstant()->Value());
+ return Contains(this->AsRange(), that->AsConstant());
}
- return that->IsRange() && Overlap(this->AsRange(), that->AsRange());
+ if (that->IsRange()) {
+ return Overlap(this->AsRange(), that->AsRange());
+ }
+ if (that->IsBitset()) {
+ bitset number_bits = BitsetType::NumberBits(that->AsBitset());
+ if (number_bits == BitsetType::kNone) {
+ return false;
+ }
+ double min = std::max(BitsetType::Min(number_bits), this->Min());
+ double max = std::min(BitsetType::Max(number_bits), this->Max());
+ return min <= max;
+ }
}
if (that->IsRange()) {
- if (this->IsConstant()) {
- return Contains(that->AsRange(), *this->AsConstant()->Value());
- }
- return this->IsRange() && Overlap(this->AsRange(), that->AsRange());
+ return that->SemanticMaybe(this); // This case is handled above.
}
+ if (this->IsBitset() || that->IsBitset()) return true;
+
return this->SimplyEquals(that);
}
@@ -554,20 +709,27 @@
DisallowHeapAllocation no_allocation;
// This checks the invariants of the union representation:
// 1. There are at least two elements.
- // 2. At most one element is a bitset, and it must be the first one.
- // 3. At most one element is a range, and it must be the second one
- // (even when the first element is not a bitset).
+ // 2. The first element is a bitset, no other element is a bitset.
+ // 3. At most one element is a range, and it must be the second one.
// 4. No element is itself a union.
- // 5. No element is a subtype of any other.
+ // 5. No element (except the bitset) is a subtype of any other.
+ // 6. If there is a range, then the bitset type does not contain
+ // plain number bits.
DCHECK(this->Length() >= 2); // (1)
+ DCHECK(this->Get(0)->IsBitset()); // (2a)
+
for (int i = 0; i < this->Length(); ++i) {
- if (i != 0) DCHECK(!this->Get(i)->IsBitset()); // (2)
- if (i != 1) DCHECK(!this->Get(i)->IsRange()); // (3)
- DCHECK(!this->Get(i)->IsUnion()); // (4)
+ if (i != 0) DCHECK(!this->Get(i)->IsBitset()); // (2b)
+ if (i != 1) DCHECK(!this->Get(i)->IsRange()); // (3)
+ DCHECK(!this->Get(i)->IsUnion()); // (4)
for (int j = 0; j < this->Length(); ++j) {
- if (i != j) DCHECK(!this->Get(i)->Is(this->Get(j))); // (5)
+ if (i != j && i != 0)
+ DCHECK(!this->Get(i)->SemanticIs(this->Get(j)->unhandle())); // (5)
}
}
+ DCHECK(!this->Get(1)->IsRange() ||
+ (BitsetType::NumberBits(this->Get(0)->AsBitset()) ==
+ BitsetType::kNone)); // (6)
return true;
}
@@ -586,12 +748,10 @@
template<class Config>
typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
TypeHandle type1, TypeHandle type2, Region* region) {
- bitset bits = type1->BitsetGlb() & type2->BitsetGlb();
- if (!BitsetType::IsInhabited(bits)) bits = BitsetType::kNone;
// Fast case: bit sets.
if (type1->IsBitset() && type2->IsBitset()) {
- return BitsetType::New(bits, region);
+ return BitsetType::New(type1->AsBitset() & type2->AsBitset(), region);
}
// Fast case: top or bottom types.
@@ -603,6 +763,26 @@
if (type2->Is(type1)) return type2;
// Slow case: create union.
+
+ // Figure out the representation of the result first.
+ // The rest of the method should not change this representation and
+ // it should not make any decisions based on representations (i.e.,
+ // it should only use the semantic part of types).
+ const bitset representation =
+ type1->Representation() & type2->Representation();
+
+ // Semantic subtyping check - this is needed for consistency with the
+ // semi-fast case above - we should behave the same way regardless of
+ // representations. Intersection with a universal bitset should only update
+ // the representations.
+ if (type1->SemanticIs(type2->unhandle())) {
+ type2 = Any(region);
+ } else if (type2->SemanticIs(type1->unhandle())) {
+ type1 = Any(region);
+ }
+
+ bitset bits =
+ SEMANTIC(type1->BitsetGlb() & type2->BitsetGlb()) | representation;
int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
if (!AddIsSafe(size1, size2)) return Any(region);
@@ -615,38 +795,38 @@
// Deal with bitsets.
result->Set(size++, BitsetType::New(bits, region));
- // Deal with ranges.
- TypeHandle range = None(region);
- RangeType* range1 = type1->GetRange();
- RangeType* range2 = type2->GetRange();
- if (range1 != NULL && range2 != NULL) {
- Limits lim = Intersect(Limits(range1), Limits(range2));
- if (lim.min->Number() <= lim.max->Number()) {
- range = RangeType::New(lim, region);
- }
- }
- result->Set(size++, range);
+ Limits lims = Limits::Empty();
+ size = IntersectAux(type1, type2, result, size, &lims, region);
- size = IntersectAux(type1, type2, result, size, region);
- return NormalizeUnion(result, size);
+ // If the range is not empty, then insert it into the union and
+ // remove the number bits from the bitset.
+ if (!lims.IsEmpty()) {
+ size = UpdateRange(RangeType::New(lims, representation, region), result,
+ size, region);
+
+ // Remove the number bits.
+ bitset number_bits = BitsetType::NumberBits(bits);
+ bits &= ~number_bits;
+ result->Set(0, BitsetType::New(bits, region));
+ }
+ return NormalizeUnion(result, size, region);
}
template<class Config>
int TypeImpl<Config>::UpdateRange(
RangeHandle range, UnionHandle result, int size, Region* region) {
- TypeHandle old_range = result->Get(1);
- DCHECK(old_range->IsRange() || old_range->IsNone());
- if (range->Is(old_range)) return size;
- if (!old_range->Is(range->unhandle())) {
- range = RangeType::New(
- Union(Limits(range->AsRange()), Limits(old_range->AsRange())), region);
+ if (size == 1) {
+ result->Set(size++, range);
+ } else {
+ // Make space for the range.
+ result->Set(size++, result->Get(1));
+ result->Set(1, range);
}
- result->Set(1, range);
// Remove any components that just got subsumed.
for (int i = 2; i < size; ) {
- if (result->Get(i)->Is(range->unhandle())) {
+ if (result->Get(i)->SemanticIs(range->unhandle())) {
result->Set(i, result->Get(--size));
} else {
++i;
@@ -656,50 +836,79 @@
}
-template<class Config>
-int TypeImpl<Config>::IntersectAux(
- TypeHandle lhs, TypeHandle rhs,
- UnionHandle result, int size, Region* region) {
+template <class Config>
+typename TypeImpl<Config>::Limits TypeImpl<Config>::ToLimits(bitset bits,
+ Region* region) {
+ bitset number_bits = BitsetType::NumberBits(bits);
+
+ if (number_bits == BitsetType::kNone) {
+ return Limits::Empty();
+ }
+
+ return Limits(BitsetType::Min(number_bits), BitsetType::Max(number_bits));
+}
+
+
+template <class Config>
+typename TypeImpl<Config>::Limits TypeImpl<Config>::IntersectRangeAndBitset(
+ TypeHandle range, TypeHandle bitset, Region* region) {
+ Limits range_lims(range->AsRange());
+ Limits bitset_lims = ToLimits(bitset->AsBitset(), region);
+ return Limits::Intersect(range_lims, bitset_lims);
+}
+
+
+template <class Config>
+int TypeImpl<Config>::IntersectAux(TypeHandle lhs, TypeHandle rhs,
+ UnionHandle result, int size, Limits* lims,
+ Region* region) {
if (lhs->IsUnion()) {
for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) {
- size = IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, region);
+ size =
+ IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, lims, region);
}
return size;
}
if (rhs->IsUnion()) {
for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) {
- size = IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, region);
+ size =
+ IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, region);
}
return size;
}
- if (!BitsetType::IsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
+ if (!BitsetType::SemanticIsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
return size;
}
if (lhs->IsRange()) {
- if (rhs->IsBitset() || rhs->IsClass()) {
- return UpdateRange(
- Config::template cast<RangeType>(lhs), result, size, region);
+ if (rhs->IsBitset()) {
+ Limits lim = IntersectRangeAndBitset(lhs, rhs, region);
+
+ if (!lim.IsEmpty()) {
+ *lims = Limits::Union(lim, *lims);
+ }
+ return size;
}
- if (rhs->IsConstant() &&
- Contains(lhs->AsRange(), *rhs->AsConstant()->Value())) {
+ if (rhs->IsClass()) {
+ *lims = Limits::Union(Limits(lhs->AsRange()), *lims);
+ }
+ if (rhs->IsConstant() && Contains(lhs->AsRange(), rhs->AsConstant())) {
return AddToUnion(rhs, result, size, region);
}
+ if (rhs->IsRange()) {
+ Limits lim = Limits::Intersect(
+ Limits(lhs->AsRange()), Limits(rhs->AsRange()));
+ if (!lim.IsEmpty()) {
+ *lims = Limits::Union(lim, *lims);
+ }
+ }
return size;
}
if (rhs->IsRange()) {
- if (lhs->IsBitset() || lhs->IsClass()) {
- return UpdateRange(
- Config::template cast<RangeType>(rhs), result, size, region);
- }
- if (lhs->IsConstant() &&
- Contains(rhs->AsRange(), *lhs->AsConstant()->Value())) {
- return AddToUnion(lhs, result, size, region);
- }
- return size;
+ // This case is handled symmetrically above.
+ return IntersectAux(rhs, lhs, result, size, lims, region);
}
-
if (lhs->IsBitset() || rhs->IsBitset()) {
return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, region);
}
@@ -713,10 +922,58 @@
}
+// Make sure that we produce a well-formed range and bitset:
+// If the range is non-empty, the number bits in the bitset should be
+// clear. Moreover, if we have a canonical range (such as Signed32),
+// we want to produce a bitset rather than a range.
+template <class Config>
+typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeRangeAndBitset(
+ RangeHandle range, bitset* bits, Region* region) {
+ // Fast path: If the bitset does not mention numbers, we can just keep the
+ // range.
+ bitset number_bits = BitsetType::NumberBits(*bits);
+ if (number_bits == 0) {
+ return range;
+ }
+
+ // If the range is semantically contained within the bitset, return None and
+ // leave the bitset untouched.
+ bitset range_lub = SEMANTIC(range->BitsetLub());
+ if (BitsetType::Is(range_lub, *bits)) {
+ return None(region);
+ }
+
+ // Slow path: reconcile the bitset range and the range.
+ double bitset_min = BitsetType::Min(number_bits);
+ double bitset_max = BitsetType::Max(number_bits);
+
+ double range_min = range->Min();
+ double range_max = range->Max();
+
+ // Remove the number bits from the bitset, they would just confuse us now.
+ // NOTE: bits contains OtherNumber iff bits contains PlainNumber, in which
+ // case we already returned after the subtype check above.
+ *bits &= ~number_bits;
+
+ if (range_min <= bitset_min && range_max >= bitset_max) {
+ // Bitset is contained within the range, just return the range.
+ return range;
+ }
+
+ if (bitset_min < range_min) {
+ range_min = bitset_min;
+ }
+ if (bitset_max > range_max) {
+ range_max = bitset_max;
+ }
+ return RangeType::New(range_min, range_max,
+ BitsetType::New(BitsetType::kNone, region), region);
+}
+
+
template<class Config>
typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
TypeHandle type1, TypeHandle type2, Region* region) {
-
// Fast case: bit sets.
if (type1->IsBitset() && type2->IsBitset()) {
return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region);
@@ -730,6 +987,13 @@
if (type1->Is(type2)) return type2;
if (type2->Is(type1)) return type1;
+ // Figure out the representation of the result.
+ // The rest of the method should not change this representation and
+ // it should not make any decisions based on representations (i.e.,
+ // it should only use the semantic part of types).
+ const bitset representation =
+ type1->Representation() | type2->Representation();
+
// Slow case: create union.
int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
@@ -740,27 +1004,30 @@
UnionHandle result = UnionType::New(size, region);
size = 0;
- // Deal with bitsets.
- TypeHandle bits = BitsetType::New(
- type1->BitsetGlb() | type2->BitsetGlb(), region);
- result->Set(size++, bits);
+ // Compute the new bitset.
+ bitset new_bitset = SEMANTIC(type1->BitsetGlb() | type2->BitsetGlb());
// Deal with ranges.
TypeHandle range = None(region);
RangeType* range1 = type1->GetRange();
RangeType* range2 = type2->GetRange();
if (range1 != NULL && range2 != NULL) {
- range = RangeType::New(Union(Limits(range1), Limits(range2)), region);
+ Limits lims = Limits::Union(Limits(range1), Limits(range2));
+ RangeHandle union_range = RangeType::New(lims, representation, region);
+ range = NormalizeRangeAndBitset(union_range, &new_bitset, region);
} else if (range1 != NULL) {
- range = handle(range1);
+ range = NormalizeRangeAndBitset(handle(range1), &new_bitset, region);
} else if (range2 != NULL) {
- range = handle(range2);
+ range = NormalizeRangeAndBitset(handle(range2), &new_bitset, region);
}
- result->Set(size++, range);
+ new_bitset = SEMANTIC(new_bitset) | representation;
+ TypeHandle bits = BitsetType::New(new_bitset, region);
+ result->Set(size++, bits);
+ if (!range->IsNone()) result->Set(size++, range);
size = AddToUnion(type1, result, size, region);
size = AddToUnion(type2, result, size, region);
- return NormalizeUnion(result, size);
+ return NormalizeUnion(result, size, region);
}
@@ -777,26 +1044,35 @@
return size;
}
for (int i = 0; i < size; ++i) {
- if (type->Is(result->Get(i))) return size;
+ if (type->SemanticIs(result->Get(i)->unhandle())) return size;
}
result->Set(size++, type);
return size;
}
-template<class Config>
+template <class Config>
typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeUnion(
- UnionHandle unioned, int size) {
- DCHECK(size >= 2);
- // If range is subsumed by bitset, use its place for a different type.
- if (unioned->Get(1)->Is(unioned->Get(0))) {
- unioned->Set(1, unioned->Get(--size));
+ UnionHandle unioned, int size, Region* region) {
+ DCHECK(size >= 1);
+ DCHECK(unioned->Get(0)->IsBitset());
+ // If the union has just one element, return it.
+ if (size == 1) {
+ return unioned->Get(0);
}
- // If bitset is None, use its place for a different type.
- if (size >= 2 && unioned->Get(0)->IsNone()) {
- unioned->Set(0, unioned->Get(--size));
+ bitset bits = unioned->Get(0)->AsBitset();
+ // If the union only consists of a range, we can get rid of the union.
+ if (size == 2 && SEMANTIC(bits) == BitsetType::kNone) {
+ bitset representation = REPRESENTATION(bits);
+ if (representation == unioned->Get(1)->Representation()) {
+ return unioned->Get(1);
+ }
+ if (unioned->Get(1)->IsRange()) {
+ return RangeType::New(unioned->Get(1)->AsRange()->Min(),
+ unioned->Get(1)->AsRange()->Max(), unioned->Get(0),
+ region);
+ }
}
- if (size == 1) return unioned->Get(0);
unioned->Shrink(size);
SLOW_DCHECK(unioned->Wellformed());
return unioned;
@@ -804,6 +1080,25 @@
// -----------------------------------------------------------------------------
+// Component extraction
+
+// static
+template <class Config>
+typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Representation(
+ TypeHandle t, Region* region) {
+ return BitsetType::New(t->Representation(), region);
+}
+
+
+// static
+template <class Config>
+typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Semantic(
+ TypeHandle t, Region* region) {
+ return Intersect(t, BitsetType::New(BitsetType::kSemantic, region), region);
+}
+
+
+// -----------------------------------------------------------------------------
// Iteration.
template<class Config>
@@ -918,7 +1213,8 @@
return ConstantType::New(type->AsConstant()->Value(), region);
} else if (type->IsRange()) {
return RangeType::New(
- type->AsRange()->Min(), type->AsRange()->Max(), region);
+ type->AsRange()->Min(), type->AsRange()->Max(),
+ BitsetType::New(REPRESENTATION(type->BitsetLub()), region), region);
} else if (type->IsContext()) {
TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region);
return ContextType::New(outer, region);
@@ -966,6 +1262,7 @@
#define RETURN_NAMED_SEMANTIC_TYPE(type, value) \
case SEMANTIC(k##type): return #type;
SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
+ INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
#undef RETURN_NAMED_SEMANTIC_TYPE
default:
@@ -984,16 +1281,18 @@
return;
}
+ // clang-format off
static const bitset named_bitsets[] = {
#define BITSET_CONSTANT(type, value) REPRESENTATION(k##type),
- REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
+ REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
#undef BITSET_CONSTANT
#define BITSET_CONSTANT(type, value) SEMANTIC(k##type),
- INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
- SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
+ INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
+ SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
#undef BITSET_CONSTANT
};
+ // clang-format on
bool is_first = true;
os << "(";
@@ -1026,8 +1325,8 @@
} else if (this->IsRange()) {
std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed);
std::streamsize saved_precision = os.precision(0);
- os << "Range(" << this->AsRange()->Min()->Number() << ", "
- << this->AsRange()->Max()->Number() << ")";
+ os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max()
+ << ")";
os.flags(saved_flags);
os.precision(saved_precision);
} else if (this->IsContext()) {
@@ -1103,4 +1402,5 @@
TypeImpl<HeapTypeConfig>::Convert<Type>(
TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*);
-} } // namespace v8::internal
+} // namespace internal
+} // namespace v8