From 89c8ffd54221cfe2d0b5e391974143d08f047ae0 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sun, 12 Apr 2020 10:44:03 -0700 Subject: [PATCH] NFC: Clean up the implementation of StringPool a bit, and remove dependence on some "implicitly MallocAllocator" based methods on StringMapEntry. This allows reducing the #includes in StringMapEntry.h. Summary: StringPool has many caveats and isn't used in the monorepo. I will propose removing it as a patch separate from this refactoring patch. Reviewers: rriddle Subscribers: hiraditya, dexonsmith, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D77976 --- llvm/include/llvm/ADT/StringMap.h | 1 + llvm/include/llvm/ADT/StringMapEntry.h | 18 --- llvm/include/llvm/Support/StringPool.h | 197 +++++++++++++++++---------------- llvm/lib/IR/Value.cpp | 9 +- llvm/lib/IR/ValueSymbolTable.cpp | 13 ++- llvm/lib/Support/StringPool.cpp | 24 ++-- llvm/unittests/ADT/StringMapTest.cpp | 12 +- llvm/unittests/ADT/StringSetTest.cpp | 7 +- 8 files changed, 136 insertions(+), 145 deletions(-) diff --git a/llvm/include/llvm/ADT/StringMap.h b/llvm/include/llvm/ADT/StringMap.h index d6cad5f..fd8643f 100644 --- a/llvm/include/llvm/ADT/StringMap.h +++ b/llvm/include/llvm/ADT/StringMap.h @@ -14,6 +14,7 @@ #define LLVM_ADT_STRINGMAP_H #include "llvm/ADT/StringMapEntry.h" +#include "llvm/Support/AllocatorBase.h" #include "llvm/Support/PointerLikeTypeTraits.h" #include #include diff --git a/llvm/include/llvm/ADT/StringMapEntry.h b/llvm/include/llvm/ADT/StringMapEntry.h index 76a8e1f..19638f3 100644 --- a/llvm/include/llvm/ADT/StringMapEntry.h +++ b/llvm/include/llvm/ADT/StringMapEntry.h @@ -16,7 +16,6 @@ #define LLVM_ADT_STRINGMAPENTRY_H #include "llvm/ADT/StringRef.h" -#include "llvm/Support/AllocatorBase.h" namespace llvm { @@ -113,17 +112,6 @@ public: return newItem; } - /// Create - Create a StringMapEntry with normal malloc/free. - template - static StringMapEntry *Create(StringRef key, InitType &&... initVal) { - MallocAllocator allocator; - return Create(key, allocator, std::forward(initVal)...); - } - - static StringMapEntry *Create(StringRef key) { - return Create(key, ValueTy()); - } - /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded /// into a StringMapEntry, return the StringMapEntry itself. static StringMapEntry &GetStringMapEntryFromKeyData(const char *keyData) { @@ -139,12 +127,6 @@ public: this->~StringMapEntry(); allocator.Deallocate(static_cast(this), AllocSize); } - - /// Destroy this object, releasing memory back to the malloc allocator. - void Destroy() { - MallocAllocator allocator; - Destroy(allocator); - } }; } // end namespace llvm diff --git a/llvm/include/llvm/Support/StringPool.h b/llvm/include/llvm/Support/StringPool.h index a4f4591..aecfbee 100644 --- a/llvm/include/llvm/Support/StringPool.h +++ b/llvm/include/llvm/Support/StringPool.h @@ -1,4 +1,4 @@ -//===- StringPool.h - Interned string pool ----------------------*- C++ -*-===// +//===- StringPool.h - Intern'd string pool ----------------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -6,8 +6,9 @@ // //===----------------------------------------------------------------------===// // -// This file declares an interned string pool, which helps reduce the cost of -// strings by using the same storage for identical strings. +// This file declares an interned string pool with separately malloc and +// reference counted entries. This can reduce the cost of strings by using the +// same storage for identical strings. // // To intern a string: // @@ -29,110 +30,112 @@ #define LLVM_SUPPORT_STRINGPOOL_H #include "llvm/ADT/StringMap.h" -#include "llvm/ADT/StringRef.h" -#include namespace llvm { - class PooledStringPtr; +class PooledStringPtr; - /// StringPool - An interned string pool. Use the intern method to add a - /// string. Strings are removed automatically as PooledStringPtrs are - /// destroyed. - class StringPool { - /// PooledString - This is the value of an entry in the pool's interning - /// table. - struct PooledString { - StringPool *Pool = nullptr; ///< So the string can remove itself. - unsigned Refcount = 0; ///< Number of referencing PooledStringPtrs. - - public: - PooledString() = default; - }; - - friend class PooledStringPtr; - - using table_t = StringMap; - using entry_t = StringMapEntry; - table_t InternTable; +/// StringPool - An interned string pool. Use the intern method to add a +/// string. Strings are removed automatically as PooledStringPtrs are +/// destroyed. +class StringPool { + /// PooledString - This is the value of an entry in the pool's interning + /// table. + struct PooledString { + StringPool *pool = nullptr; ///< So the string can remove itself. + unsigned refcount = 0; ///< Number of referencing PooledStringPtrs. public: - StringPool(); - ~StringPool(); - - /// intern - Adds a string to the pool and returns a reference-counted - /// pointer to it. No additional memory is allocated if the string already - /// exists in the pool. - PooledStringPtr intern(StringRef Str); - - /// empty - Checks whether the pool is empty. Returns true if so. - /// - inline bool empty() const { return InternTable.empty(); } + PooledString() = default; }; - /// PooledStringPtr - A pointer to an interned string. Use operator bool to - /// test whether the pointer is valid, and operator * to get the string if so. - /// This is a lightweight value class with storage requirements equivalent to - /// a single pointer, but it does have reference-counting overhead when - /// copied. - class PooledStringPtr { - using entry_t = StringPool::entry_t; - - entry_t *S = nullptr; - - public: - PooledStringPtr() = default; - - explicit PooledStringPtr(entry_t *E) : S(E) { - if (S) ++S->getValue().Refcount; - } - - PooledStringPtr(const PooledStringPtr &That) : S(That.S) { - if (S) ++S->getValue().Refcount; - } - - PooledStringPtr &operator=(const PooledStringPtr &That) { - if (S != That.S) { - clear(); - S = That.S; - if (S) ++S->getValue().Refcount; - } - return *this; - } - - void clear() { - if (!S) - return; - if (--S->getValue().Refcount == 0) { - S->getValue().Pool->InternTable.remove(S); - S->Destroy(); - } - S = nullptr; - } - - ~PooledStringPtr() { clear(); } - - inline const char *begin() const { - assert(*this && "Attempt to dereference empty PooledStringPtr!"); - return S->getKeyData(); + friend class PooledStringPtr; + using Entry = StringMapEntry; + StringMap internTable; + +public: + StringPool(); + ~StringPool(); + + /// intern - Adds a string to the pool and returns a reference-counted + /// pointer to it. No additional memory is allocated if the string already + /// exists in the pool. + PooledStringPtr intern(StringRef string); + + /// empty - Checks whether the pool is empty. Returns true if so. + bool empty() const { return internTable.empty(); } +}; + +/// PooledStringPtr - A pointer to an interned string. Use operator bool to +/// test whether the pointer is valid, and operator * to get the string if so. +/// This is a lightweight value class with storage requirements equivalent to +/// a single pointer, but it does have reference-counting overhead when +/// copied. +class PooledStringPtr { + using Entry = StringPool::Entry; + Entry *entry = nullptr; + +public: + PooledStringPtr() = default; + + explicit PooledStringPtr(Entry *e) : entry(e) { + if (entry) + ++entry->getValue().refcount; + } + + PooledStringPtr(const PooledStringPtr &that) : entry(that.entry) { + if (entry) + ++entry->getValue().refcount; + } + + PooledStringPtr &operator=(const PooledStringPtr &that) { + if (entry != that.entry) { + clear(); + entry = that.entry; + if (entry) + ++entry->getValue().refcount; } - - inline const char *end() const { - assert(*this && "Attempt to dereference empty PooledStringPtr!"); - return S->getKeyData() + S->getKeyLength(); - } - - inline unsigned size() const { - assert(*this && "Attempt to dereference empty PooledStringPtr!"); - return S->getKeyLength(); + return *this; + } + + void clear() { + if (!entry) + return; + if (--entry->getValue().refcount == 0) { + entry->getValue().pool->internTable.remove(entry); + MallocAllocator allocator; + entry->Destroy(allocator); } - - inline const char *operator*() const { return begin(); } - inline explicit operator bool() const { return S != nullptr; } - - inline bool operator==(const PooledStringPtr &That) const { return S == That.S; } - inline bool operator!=(const PooledStringPtr &That) const { return S != That.S; } - }; + entry = nullptr; + } + + ~PooledStringPtr() { clear(); } + + const char *begin() const { + assert(*this && "Attempt to dereference empty PooledStringPtr!"); + return entry->getKeyData(); + } + + const char *end() const { + assert(*this && "Attempt to dereference empty PooledStringPtr!"); + return entry->getKeyData() + entry->getKeyLength(); + } + + unsigned size() const { + assert(*this && "Attempt to dereference empty PooledStringPtr!"); + return entry->getKeyLength(); + } + + const char *operator*() const { return begin(); } + explicit operator bool() const { return entry != nullptr; } + + bool operator==(const PooledStringPtr &that) const { + return entry == that.entry; + } + bool operator!=(const PooledStringPtr &that) const { + return entry != that.entry; + } +}; } // end namespace llvm diff --git a/llvm/lib/IR/Value.cpp b/llvm/lib/IR/Value.cpp index afb509f..015bf20 100644 --- a/llvm/lib/IR/Value.cpp +++ b/llvm/lib/IR/Value.cpp @@ -128,8 +128,10 @@ void Value::deleteValue() { void Value::destroyValueName() { ValueName *Name = getValueName(); - if (Name) - Name->Destroy(); + if (Name) { + MallocAllocator Allocator; + Name->Destroy(Allocator); + } setValueName(nullptr); } @@ -312,7 +314,8 @@ void Value::setNameImpl(const Twine &NewName) { destroyValueName(); // Create the new name. - setValueName(ValueName::Create(NameRef)); + MallocAllocator Allocator; + setValueName(ValueName::Create(NameRef, Allocator)); getValueName()->setValue(this); return; } diff --git a/llvm/lib/IR/ValueSymbolTable.cpp b/llvm/lib/IR/ValueSymbolTable.cpp index 417ec04..b498423 100644 --- a/llvm/lib/IR/ValueSymbolTable.cpp +++ b/llvm/lib/IR/ValueSymbolTable.cpp @@ -31,7 +31,7 @@ using namespace llvm; // Class destructor ValueSymbolTable::~ValueSymbolTable() { -#ifndef NDEBUG // Only do this in -g mode... +#ifndef NDEBUG // Only do this in -g mode... for (const auto &VI : vmap) dbgs() << "Value still in symbol table! Type = '" << *VI.getValue()->getType() << "' Name = '" << VI.getKeyData() @@ -69,7 +69,7 @@ ValueName *ValueSymbolTable::makeUniqueName(Value *V, // Insert a value into the symbol table with the specified name... // -void ValueSymbolTable::reinsertValue(Value* V) { +void ValueSymbolTable::reinsertValue(Value *V) { assert(V->hasName() && "Can't insert nameless Value into symbol table"); // Try inserting the name, assuming it won't conflict. @@ -83,7 +83,8 @@ void ValueSymbolTable::reinsertValue(Value* V) { SmallString<256> UniqueName(V->getName().begin(), V->getName().end()); // The name is too already used, just free it so we can allocate a new name. - V->getValueName()->Destroy(); + MallocAllocator Allocator; + V->getValueName()->Destroy(Allocator); ValueName *VN = makeUniqueName(V, UniqueName); V->setValueName(VN); @@ -116,11 +117,11 @@ ValueName *ValueSymbolTable::createValueName(StringRef Name, Value *V) { // dump - print out the symbol table // LLVM_DUMP_METHOD void ValueSymbolTable::dump() const { - //dbgs() << "ValueSymbolTable:\n"; + // dbgs() << "ValueSymbolTable:\n"; for (const auto &I : *this) { - //dbgs() << " '" << I->getKeyData() << "' = "; + // dbgs() << " '" << I->getKeyData() << "' = "; I.getValue()->dump(); - //dbgs() << "\n"; + // dbgs() << "\n"; } } #endif diff --git a/llvm/lib/Support/StringPool.cpp b/llvm/lib/Support/StringPool.cpp index 2746444..7d345df 100644 --- a/llvm/lib/Support/StringPool.cpp +++ b/llvm/lib/Support/StringPool.cpp @@ -1,4 +1,4 @@ -//===-- StringPool.cpp - Interned string pool -----------------------------===// +//===-- StringPool.cpp - Intern'd string pool -----------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -11,25 +11,23 @@ //===----------------------------------------------------------------------===// #include "llvm/Support/StringPool.h" -#include "llvm/ADT/StringRef.h" -#include - using namespace llvm; StringPool::StringPool() {} StringPool::~StringPool() { - assert(InternTable.empty() && "PooledStringPtr leaked!"); + assert(internTable.empty() && "PooledStringPtr leaked!"); } -PooledStringPtr StringPool::intern(StringRef Key) { - table_t::iterator I = InternTable.find(Key); - if (I != InternTable.end()) - return PooledStringPtr(&*I); +PooledStringPtr StringPool::intern(StringRef key) { + auto it = internTable.find(key); + if (it != internTable.end()) + return PooledStringPtr(&*it); - entry_t *S = entry_t::Create(Key); - S->getValue().Pool = this; - InternTable.insert(S); + MallocAllocator allocator; + auto *entry = Entry::Create(key, allocator); + entry->getValue().pool = this; + internTable.insert(entry); - return PooledStringPtr(S); + return PooledStringPtr(entry); } diff --git a/llvm/unittests/ADT/StringMapTest.cpp b/llvm/unittests/ADT/StringMapTest.cpp index 5f0c83d..fc82c27 100644 --- a/llvm/unittests/ADT/StringMapTest.cpp +++ b/llvm/unittests/ADT/StringMapTest.cpp @@ -224,9 +224,10 @@ TEST_F(StringMapTest, IterationTest) { // Test StringMapEntry::Create() method. TEST_F(StringMapTest, StringMapEntryTest) { + MallocAllocator Allocator; StringMap::value_type* entry = StringMap::value_type::Create( - StringRef(testKeyFirst, testKeyLength), 1u); + StringRef(testKeyFirst, testKeyLength), Allocator, 1u); EXPECT_STREQ(testKey, entry->first().data()); EXPECT_EQ(1u, entry->second); free(entry); @@ -353,14 +354,15 @@ TEST_F(StringMapTest, MoveOnly) { StringMap t; t.insert(std::make_pair("Test", MoveOnly(42))); StringRef Key = "Test"; - StringMapEntry::Create(Key, MoveOnly(42)) - ->Destroy(); + StringMapEntry::Create(Key, t.getAllocator(), MoveOnly(42)) + ->Destroy(t.getAllocator()); } TEST_F(StringMapTest, CtorArg) { StringRef Key = "Test"; - StringMapEntry::Create(Key, Immovable()) - ->Destroy(); + MallocAllocator Allocator; + StringMapEntry::Create(Key, Allocator, Immovable()) + ->Destroy(Allocator); } TEST_F(StringMapTest, MoveConstruct) { diff --git a/llvm/unittests/ADT/StringSetTest.cpp b/llvm/unittests/ADT/StringSetTest.cpp index f3ec217..e27306d 100644 --- a/llvm/unittests/ADT/StringSetTest.cpp +++ b/llvm/unittests/ADT/StringSetTest.cpp @@ -1,4 +1,4 @@ -//===- llvm/unittest/ADT/StringSetTest.cpp - StringSet unit tests ----------===// +//===- llvm/unittest/ADT/StringSetTest.cpp - StringSet unit tests ---------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -33,12 +33,13 @@ TEST_F(StringSetTest, InsertAndCountStringMapEntry) { // Test insert(StringMapEntry) and count(StringMapEntry) // which are required for set_difference(StringSet, StringSet). StringSet<> Set; - StringMapEntry *Element = StringMapEntry::Create("A"); + StringMapEntry *Element = + StringMapEntry::Create("A", Set.getAllocator()); Set.insert(*Element); size_t Count = Set.count(*Element); size_t Expected = 1; EXPECT_EQ(Expected, Count); - Element->Destroy(); + Element->Destroy(Set.getAllocator()); } TEST_F(StringSetTest, EmptyString) { -- 2.7.4