From 1328715977ea6a4f806349ec65f5a03567a129d0 Mon Sep 17 00:00:00 2001 From: neis Date: Thu, 17 Sep 2015 01:51:58 -0700 Subject: [PATCH] Intersection of certain constants with bitsets was wrongly non-empty. R=jarin BUG= Review URL: https://codereview.chromium.org/1343933002 Cr-Commit-Position: refs/heads/master@{#30790} --- src/compiler/typer.cc | 1 + src/types.cc | 83 ++++++++++++++++++++++++--------------------------- src/types.h | 45 ++++++++++++++++++---------- 3 files changed, 70 insertions(+), 59 deletions(-) diff --git a/src/compiler/typer.cc b/src/compiler/typer.cc index 4b576ba..a6a9e67 100644 --- a/src/compiler/typer.cc +++ b/src/compiler/typer.cc @@ -53,6 +53,7 @@ Typer::Typer(Isolate* isolate, Graph* graph, Type::FunctionType* function_type) Type* truncating_to_zero = Type::Union(Type::Union(infinity, minus_infinity, zone), Type::MinusZeroOrNaN(), zone); + DCHECK(!truncating_to_zero->Maybe(Type::Integral32())); singleton_false_ = Type::Constant(factory->false_value(), zone); singleton_true_ = Type::Constant(factory->true_value(), zone); diff --git a/src/types.cc b/src/types.cc index 868b073..af17002 100644 --- a/src/types.cc +++ b/src/types.cc @@ -152,7 +152,7 @@ TypeImpl::BitsetType::Glb(TypeImpl* type) { } -// The smallest bitset subsuming this type. +// The smallest bitset subsuming this type, possibly not a proper one. template typename TypeImpl::bitset TypeImpl::BitsetType::Lub(TypeImpl* type) { @@ -168,13 +168,9 @@ TypeImpl::BitsetType::Lub(TypeImpl* type) { } 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()->Bound(); + 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 kOtherObject; if (type->IsFunction()) return kOtherObject; // TODO(rossberg): kFunction @@ -341,22 +337,21 @@ TypeImpl::BitsetType::Lub(double value) { 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. +// Minimum values of plain numeric bitsets. template const typename TypeImpl::BitsetType::Boundary - TypeImpl::BitsetType::BoundariesArray[] = { - {kPlainNumber, -V8_INFINITY}, - {kNegative32, kMinInt}, - {kNegative31, -0x40000000}, - {kUnsigned30, 0}, - {kUnsigned31, 0x40000000}, - {kUnsigned32, 0x80000000}, - {kPlainNumber, static_cast(kMaxUInt32) + 1} -}; +TypeImpl::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(kMaxUInt32) + 1}}; template @@ -374,6 +369,21 @@ size_t TypeImpl::BitsetType::BoundariesSize() { } +template +typename TypeImpl::bitset TypeImpl::BitsetType::ExpandInternals( + typename TypeImpl::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 typename TypeImpl::bitset TypeImpl::BitsetType::Lub(double min, double max) { @@ -381,18 +391,13 @@ TypeImpl::BitsetType::Lub(double min, double max) { int lub = kNone; 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 < 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[BoundariesSize() - 1].bits; + return lub | mins[BoundariesSize() - 1].internal; } @@ -404,16 +409,6 @@ typename TypeImpl::bitset TypeImpl::BitsetType::NumberBits( template -void TypeImpl::BitsetType::CheckNumberBits(bitset bits) { - // Check that the bitset does not contain any holes in number ranges. - bitset number_bits = NumberBits(bits); - if (number_bits != 0) { - bitset lub = SEMANTIC(Lub(Min(number_bits), Max(number_bits))); - CHECK(lub == number_bits); - } -} - -template typename TypeImpl::bitset TypeImpl::BitsetType::Glb( double min, double max) { DisallowHeapAllocation no_allocation; @@ -426,13 +421,11 @@ typename TypeImpl::bitset TypeImpl::BitsetType::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].bits; + glb |= mins[i].external; } } // OtherNumber also contains float numbers, so it can never be - // in the greatest lower bound. (There is also the small trouble - // of kOtherNumber having a range hole, which we can conveniently - // ignore here.) + // in the greatest lower bound. return glb & ~(SEMANTIC(kOtherNumber)); } @@ -444,7 +437,7 @@ double TypeImpl::BitsetType::Min(bitset bits) { const Boundary* mins = Boundaries(); bool mz = SEMANTIC(bits & kMinusZero); for (size_t i = 0; i < BoundariesSize(); ++i) { - if (Is(SEMANTIC(mins[i].bits), bits)) { + if (Is(SEMANTIC(mins[i].internal), bits)) { return mz ? std::min(0.0, mins[i].min) : mins[i].min; } } @@ -459,11 +452,11 @@ double TypeImpl::BitsetType::Max(bitset bits) { DCHECK(Is(SEMANTIC(bits), kNumber)); const Boundary* mins = Boundaries(); bool mz = SEMANTIC(bits & kMinusZero); - if (BitsetType::Is(SEMANTIC(mins[BoundariesSize() - 1].bits), bits)) { + if (BitsetType::Is(SEMANTIC(mins[BoundariesSize() - 1].internal), bits)) { return +V8_INFINITY; } for (size_t i = BoundariesSize() - 1; i-- > 0;) { - if (Is(SEMANTIC(mins[i].bits), bits)) { + if (Is(SEMANTIC(mins[i].internal), bits)) { return mz ? std::max(0.0, mins[i+1].min - 1) : mins[i+1].min - 1; } @@ -944,7 +937,7 @@ typename TypeImpl::TypeHandle TypeImpl::NormalizeRangeAndBitset( // 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(BitsetType::NumberBits(range_lub), *bits)) { + if (BitsetType::Is(range_lub, *bits)) { return None(region); } @@ -956,6 +949,8 @@ typename TypeImpl::TypeHandle TypeImpl::NormalizeRangeAndBitset( 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) { diff --git a/src/types.h b/src/types.h index f4cc1f9..3acd5cc 100644 --- a/src/types.h +++ b/src/types.h @@ -257,6 +257,11 @@ namespace internal { * -2^31 -2^30 0 2^30 2^31 2^32 * * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1. + * + * Some of the atomic numerical bitsets are internal only (see + * INTERNAL_BITSET_TYPE_LIST). To a types user, they should only occur in + * union with certain other bitsets. For instance, OtherNumber should only + * occur as part of PlainNumber. */ #define PROPER_BITSET_TYPE_LIST(V) \ @@ -436,10 +441,12 @@ class TypeImpl : public Config::Base { static TypeHandle Intersect(TypeHandle type1, TypeHandle type2, Region* reg); static TypeHandle Of(double value, Region* region) { - return Config::from_bitset(BitsetType::Lub(value), region); + return Config::from_bitset(BitsetType::ExpandInternals( + BitsetType::Lub(value)), region); } static TypeHandle Of(i::Object* value, Region* region) { - return Config::from_bitset(BitsetType::Lub(value), region); + return Config::from_bitset(BitsetType::ExpandInternals( + BitsetType::Lub(value)), region); } static TypeHandle Of(i::Handle value, Region* region) { return Of(*value, region); @@ -657,11 +664,9 @@ class TypeImpl::BitsetType : public TypeImpl { bitset Bitset() { return Config::as_bitset(this); } static TypeImpl* New(bitset bits) { - if (FLAG_enable_slow_asserts) CheckNumberBits(bits); return Config::from_bitset(bits); } static TypeHandle New(bitset bits, Region* region) { - if (FLAG_enable_slow_asserts) CheckNumberBits(bits); return Config::from_bitset(bits, region); } @@ -687,6 +692,7 @@ class TypeImpl::BitsetType : public TypeImpl { static bitset Lub(i::Object* value); static bitset Lub(double value); static bitset Lub(double min, double max); + static bitset ExpandInternals(bitset bits); static const char* Name(bitset); static void Print(std::ostream& os, bitset); // NOLINT @@ -698,14 +704,13 @@ class TypeImpl::BitsetType : public TypeImpl { private: struct Boundary { - bitset bits; + bitset internal; + bitset external; double min; }; static const Boundary BoundariesArray[]; static inline const Boundary* Boundaries(); static inline size_t BoundariesSize(); - - static void CheckNumberBits(bitset bits); }; @@ -790,11 +795,6 @@ class TypeImpl::UnionType : public StructuralType { template class TypeImpl::ClassType : public StructuralType { public: - TypeHandle Bound(Region* region) { - return Config::is_class(this) ? - BitsetType::New(BitsetType::Lub(*Config::as_class(this)), region) : - this->Get(0); - } i::Handle Map() { return Config::is_class(this) ? Config::as_class(this) : this->template GetValue(1); @@ -816,6 +816,14 @@ class TypeImpl::ClassType : public StructuralType { DCHECK(type->IsClass()); return static_cast(type); } + + private: + template friend class TypeImpl; + bitset Lub() { + return Config::is_class(this) ? + BitsetType::Lub(*Config::as_class(this)) : + this->Get(0)->AsBitset(); + } }; @@ -825,7 +833,6 @@ class TypeImpl::ClassType : public StructuralType { template class TypeImpl::ConstantType : public StructuralType { public: - TypeHandle Bound() { return this->Get(0); } i::Handle Value() { return this->template GetValue(1); } static ConstantHandle New(i::Handle value, Region* region) { @@ -840,6 +847,10 @@ class TypeImpl::ConstantType : public StructuralType { DCHECK(type->IsConstant()); return static_cast(type); } + + private: + template friend class TypeImpl; + bitset Lub() { return this->Get(0)->AsBitset(); } }; // TODO(neis): Also cache value if numerical. // TODO(neis): Allow restricting the representation. @@ -851,7 +862,6 @@ class TypeImpl::ConstantType : public StructuralType { template class TypeImpl::RangeType : public TypeImpl { public: - bitset Bound() { return Config::range_get_bitset(Config::as_range(this)); } double Min() { return Config::range_get_double(Config::as_range(this), 0); } double Max() { return Config::range_get_double(Config::as_range(this), 1); } @@ -881,8 +891,13 @@ class TypeImpl::RangeType : public TypeImpl { DCHECK(type->IsRange()); return static_cast(type); } + + private: + template friend class TypeImpl; + bitset Lub() { + return Config::range_get_bitset(Config::as_range(this)); + } }; -// TODO(neis): Also cache min and max values. // ----------------------------------------------------------------------------- -- 2.7.4