[parser] Make parser string table empty-valued Add support for empty values (i.e. set behaviour) and heterogeneous lookup (lookup with a different key than the one you'll insert) to TemplateHashMap, and use it for the string table in AstValueFactory. Change-Id: I0c1487c9598127aac97059d4b9220e5c3c6283ce Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2494705 Auto-Submit: Leszek Swirski <leszeks@chromium.org> Commit-Queue: Igor Sheludko <ishell@chromium.org> Reviewed-by: Igor Sheludko <ishell@chromium.org> Cr-Commit-Position: refs/heads/master@{#70765}
diff --git a/src/ast/ast-value-factory.cc b/src/ast/ast-value-factory.cc index 598096b..5e2dbd5 100644 --- a/src/ast/ast-value-factory.cc +++ b/src/ast/ast-value-factory.cc
@@ -27,6 +27,7 @@ #include "src/ast/ast-value-factory.h" +#include "src/base/hashmap-entry.h" #include "src/base/logging.h" #include "src/common/globals.h" #include "src/heap/factory-inl.h" @@ -113,9 +114,7 @@ return *c; } -bool AstRawString::Compare(void* a, void* b) { - const AstRawString* lhs = static_cast<AstRawString*>(a); - const AstRawString* rhs = static_cast<AstRawString*>(b); +bool AstRawString::Compare(const AstRawString* lhs, const AstRawString* rhs) { DCHECK_EQ(lhs->Hash(), rhs->Hash()); if (lhs->length() != rhs->length()) return false; @@ -248,7 +247,7 @@ AstStringConstants::AstStringConstants(Isolate* isolate, uint64_t hash_seed) : zone_(isolate->allocator(), ZONE_NAME), - string_table_(AstRawString::Compare), + string_table_(), hash_seed_(hash_seed) { DCHECK_EQ(ThreadId::Current(), isolate->thread_id()); #define F(name, str) \ @@ -262,16 +261,13 @@ /* The Handle returned by the factory is located on the roots */ \ /* array, not on the temporary HandleScope, so this is safe. */ \ name##_string_->set_string(isolate->factory()->name##_string()); \ - base::HashMap::Entry* entry = \ - string_table_.InsertNew(name##_string_, name##_string_->Hash()); \ - DCHECK_NULL(entry->value); \ - entry->value = reinterpret_cast<void*>(1); \ + string_table_.InsertNew(name##_string_, name##_string_->Hash()); \ } AST_STRING_CONSTANTS(F) #undef F } -AstRawString* AstValueFactory::GetOneByteStringInternal( +const AstRawString* AstValueFactory::GetOneByteStringInternal( Vector<const uint8_t> literal) { if (literal.length() == 1 && literal[0] < kMaxOneCharStringValue) { int key = literal[0]; @@ -287,7 +283,7 @@ return GetString(hash_field, true, literal); } -AstRawString* AstValueFactory::GetTwoByteStringInternal( +const AstRawString* AstValueFactory::GetTwoByteStringInternal( Vector<const uint16_t> literal) { uint32_t hash_field = StringHasher::HashSequentialString<uint16_t>( literal.begin(), literal.length(), hash_seed_); @@ -295,7 +291,7 @@ } const AstRawString* AstValueFactory::GetString(Handle<String> literal) { - AstRawString* result = nullptr; + const AstRawString* result = nullptr; DisallowHeapAllocation no_gc; String::FlatContent content = literal->GetFlatContent(no_gc); if (content.IsOneByte()) { @@ -348,27 +344,29 @@ template EXPORT_TEMPLATE_DEFINE( V8_EXPORT_PRIVATE) void AstValueFactory::Internalize(LocalIsolate* isolate); -AstRawString* AstValueFactory::GetString(uint32_t hash_field, bool is_one_byte, - Vector<const byte> literal_bytes) { +const AstRawString* AstValueFactory::GetString( + uint32_t hash_field, bool is_one_byte, Vector<const byte> literal_bytes) { // literal_bytes here points to whatever the user passed, and this is OK // because we use vector_compare (which checks the contents) to compare // against the AstRawStrings which are in the string_table_. We should not // return this AstRawString. AstRawString key(is_one_byte, literal_bytes, hash_field); - base::HashMap::Entry* entry = string_table_.LookupOrInsert(&key, key.Hash()); - if (entry->value == nullptr) { - // Copy literal contents for later comparison. - int length = literal_bytes.length(); - byte* new_literal_bytes = zone()->NewArray<byte>(length); - memcpy(new_literal_bytes, literal_bytes.begin(), length); - AstRawString* new_string = zone()->New<AstRawString>( - is_one_byte, Vector<const byte>(new_literal_bytes, length), hash_field); - CHECK_NOT_NULL(new_string); - AddString(new_string); - entry->key = new_string; - entry->value = reinterpret_cast<void*>(1); - } - return reinterpret_cast<AstRawString*>(entry->key); + AstRawStringMap::Entry* entry = string_table_.LookupOrInsert( + &key, key.Hash(), + [&]() { + // Copy literal contents for later comparison. + int length = literal_bytes.length(); + byte* new_literal_bytes = zone()->NewArray<byte>(length); + memcpy(new_literal_bytes, literal_bytes.begin(), length); + AstRawString* new_string = zone()->New<AstRawString>( + is_one_byte, Vector<const byte>(new_literal_bytes, length), + hash_field); + CHECK_NOT_NULL(new_string); + AddString(new_string); + return new_string; + }, + [&]() { return base::NoHashMapValue(); }); + return entry->key; } } // namespace internal
diff --git a/src/ast/ast-value-factory.h b/src/ast/ast-value-factory.h index 0ae6776..776b45a 100644 --- a/src/ast/ast-value-factory.h +++ b/src/ast/ast-value-factory.h
@@ -48,6 +48,8 @@ class AstRawString final : public ZoneObject { public: + static bool Compare(const AstRawString* a, const AstRawString* b); + bool IsEmpty() const { return literal_bytes_.length() == 0; } int length() const { return is_one_byte() ? literal_bytes_.length() @@ -85,7 +87,6 @@ friend Zone; // Members accessed only by the AstValueFactory & related classes: - static bool Compare(void* a, void* b); AstRawString(bool is_one_byte, const Vector<const byte>& literal_bytes, uint32_t hash_field) : next_(nullptr), @@ -205,6 +206,19 @@ const char* bigint_; }; +struct AstRawStringMapMatcher { + bool operator()(uint32_t hash1, uint32_t hash2, + const AstRawString* lookup_key, + const AstRawString* entry_key) const { + return hash1 == hash2 && AstRawString::Compare(lookup_key, entry_key); + } +}; + +using AstRawStringMap = + base::TemplateHashMapImpl<const AstRawString*, base::NoHashMapValue, + AstRawStringMapMatcher, + base::DefaultAllocationPolicy>; + // For generating constants. #define AST_STRING_CONSTANTS(F) \ F(anonymous, "anonymous") \ @@ -270,13 +284,11 @@ #undef F uint64_t hash_seed() const { return hash_seed_; } - const base::CustomMatcherHashMap* string_table() const { - return &string_table_; - } + const AstRawStringMap* string_table() const { return &string_table_; } private: Zone zone_; - base::CustomMatcherHashMap string_table_; + AstRawStringMap string_table_; uint64_t hash_seed_; #define F(name, str) AstRawString* name##_string_; @@ -354,14 +366,14 @@ strings_ = nullptr; strings_end_ = &strings_; } - V8_EXPORT_PRIVATE AstRawString* GetOneByteStringInternal( + V8_EXPORT_PRIVATE const AstRawString* GetOneByteStringInternal( Vector<const uint8_t> literal); - AstRawString* GetTwoByteStringInternal(Vector<const uint16_t> literal); - AstRawString* GetString(uint32_t hash, bool is_one_byte, - Vector<const byte> literal_bytes); + const AstRawString* GetTwoByteStringInternal(Vector<const uint16_t> literal); + const AstRawString* GetString(uint32_t hash, bool is_one_byte, + Vector<const byte> literal_bytes); - // All strings are copied here, one after another (no zeroes inbetween). - base::CustomMatcherHashMap string_table_; + // All strings are copied here. + AstRawStringMap string_table_; AstRawString* strings_; AstRawString** strings_end_; @@ -373,7 +385,7 @@ // Caches one character lowercase strings (for minified code). static const int kMaxOneCharStringValue = 128; - AstRawString* one_character_strings_[kMaxOneCharStringValue]; + const AstRawString* one_character_strings_[kMaxOneCharStringValue]; Zone* zone_;
diff --git a/src/base/hashmap-entry.h b/src/base/hashmap-entry.h index 629e734..2f984f3 100644 --- a/src/base/hashmap-entry.h +++ b/src/base/hashmap-entry.h
@@ -6,15 +6,25 @@ #define V8_BASE_HASHMAP_ENTRY_H_ #include <cstdint> +#include <type_traits> + +#include "src/base/memory.h" namespace v8 { namespace base { +// Marker type for hashmaps without a value (i.e. hashsets). These won't +// allocate space for the value in the entry. +struct NoHashMapValue {}; + // HashMap entries are (key, value, hash) triplets, with a boolean indicating if // they are an empty entry. Some clients may not need to use the value slot -// (e.g. implementers of sets, where the key is the value). +// (e.g. implementers of sets, where the key is the value), in which case they +// should use NoHashMapValue. template <typename Key, typename Value> struct TemplateHashMapEntry { + STATIC_ASSERT((!std::is_same<Value, NoHashMapValue>::value)); + Key key; Value value; uint32_t hash; // The full hash value for key @@ -33,6 +43,8 @@ // Specialization for pointer-valued keys template <typename Key, typename Value> struct TemplateHashMapEntry<Key*, Value> { + STATIC_ASSERT((!std::is_same<Value, NoHashMapValue>::value)); + Key* key; Value value; uint32_t hash; // The full hash value for key @@ -45,8 +57,42 @@ void clear() { key = nullptr; } }; -// TODO(leszeks): There could be a specialisation for void values (e.g. for -// sets), which omits the value field +// Specialization for no value. +template <typename Key> +struct TemplateHashMapEntry<Key, NoHashMapValue> { + union { + Key key; + NoHashMapValue value; // Value in union with key to not take up space. + }; + uint32_t hash; // The full hash value for key + + TemplateHashMapEntry(Key key, NoHashMapValue value, uint32_t hash) + : key(key), hash(hash), exists_(true) {} + + bool exists() const { return exists_; } + + void clear() { exists_ = false; } + + private: + bool exists_; +}; + +// Specialization for pointer-valued keys and no value. +template <typename Key> +struct TemplateHashMapEntry<Key*, NoHashMapValue> { + union { + Key* key; + NoHashMapValue value; // Value in union with key to not take up space. + }; + uint32_t hash; // The full hash value for key + + TemplateHashMapEntry(Key* key, NoHashMapValue value, uint32_t hash) + : key(key), hash(hash) {} + + bool exists() const { return key != nullptr; } + + void clear() { key = nullptr; } +}; } // namespace base } // namespace v8
diff --git a/src/base/hashmap.h b/src/base/hashmap.h index 2b40b32..3b3ef74 100644 --- a/src/base/hashmap.h +++ b/src/base/hashmap.h
@@ -72,6 +72,20 @@ template <typename Func> Entry* LookupOrInsert(const Key& key, uint32_t hash, const Func& value_func); + // Heterogeneous version of LookupOrInsert, which allows a + // different lookup key type than the hashmap's key type. + // The requirement is that MatchFun has an overload: + // + // operator()(const LookupKey& lookup_key, const Key& entry_key) + // + // If an entry with matching key is found, returns that entry. + // If no matching entry is found, a new entry is inserted with + // a key created by key_func, key hash, and value created by + // value_func. + template <typename LookupKey, typename KeyFunc, typename ValueFunc> + Entry* LookupOrInsert(const LookupKey& lookup_key, uint32_t hash, + const KeyFunc& key_func, const ValueFunc& value_func); + Entry* InsertNew(const Key& key, uint32_t hash); // Removes the entry with matching key. @@ -115,7 +129,8 @@ private: Entry* map_end() const { return impl_.map_ + impl_.capacity_; } - Entry* Probe(const Key& key, uint32_t hash) const; + template <typename LookupKey> + Entry* Probe(const LookupKey& key, uint32_t hash) const; Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value, uint32_t hash); void Resize(); @@ -214,13 +229,24 @@ typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert( const Key& key, uint32_t hash, const Func& value_func) { + return LookupOrInsert( + key, hash, [&key]() { return key; }, value_func); +} + +template <typename Key, typename Value, typename MatchFun, + class AllocationPolicy> +template <typename LookupKey, typename KeyFunc, typename ValueFunc> +typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* +TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert( + const LookupKey& lookup_key, uint32_t hash, const KeyFunc& key_func, + const ValueFunc& value_func) { // Find a matching entry. - Entry* entry = Probe(key, hash); + Entry* entry = Probe(lookup_key, hash); if (entry->exists()) { return entry; } - return FillEmptyEntry(entry, key, value_func(), hash); + return FillEmptyEntry(entry, key_func(), value_func(), hash); } template <typename Key, typename Value, typename MatchFun, @@ -328,9 +354,10 @@ template <typename Key, typename Value, typename MatchFun, class AllocationPolicy> +template <typename LookupKey> typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe( - const Key& key, uint32_t hash) const { + const LookupKey& key, uint32_t hash) const { DCHECK(base::bits::IsPowerOfTwo(capacity())); size_t i = hash & (capacity() - 1); DCHECK(i < capacity());