1 //===- subzero/src/IceStringPool.h - String pooling -------------*- C++ -*-===// 2 // 3 // The Subzero Code Generator 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 /// 10 /// \file 11 /// \brief Defines unique pooled strings with short unique IDs. This makes 12 /// hashing, equality testing, and ordered comparison faster, and avoids a lot 13 /// of memory allocation compared to directly using std::string. 14 /// 15 //===----------------------------------------------------------------------===// 16 17 #ifndef SUBZERO_SRC_ICESTRINGPOOL_H 18 #define SUBZERO_SRC_ICESTRINGPOOL_H 19 20 #include "IceDefs.h" // Ostream 21 22 #include "llvm/Support/ErrorHandling.h" 23 24 #include <cstdint> // uintptr_t 25 #include <string> 26 27 namespace Ice { 28 29 class StringPool { 30 StringPool(const StringPool &) = delete; 31 StringPool &operator=(const StringPool &) = delete; 32 33 public: 34 using IDType = uintptr_t; 35 36 StringPool() = default; 37 ~StringPool() = default; getNewID()38 IDType getNewID() { 39 // TODO(stichnot): Make it so that the GlobalString ctor doesn't have to 40 // grab the lock, and instead does an atomic increment of NextID. 41 auto NewID = NextID; 42 NextID += IDIncrement; 43 return NewID; 44 } getOrAddString(const std::string & Value)45 IDType getOrAddString(const std::string &Value) { 46 auto Iter = StringToId.find(Value); 47 if (Iter == StringToId.end()) { 48 auto *NewStr = new std::string(Value); 49 auto ID = reinterpret_cast<IDType>(NewStr); 50 StringToId[Value].reset(NewStr); 51 return ID; 52 } 53 return reinterpret_cast<IDType>(Iter->second.get()); 54 } dump(Ostream & Str)55 void dump(Ostream &Str) const { 56 if (StringToId.empty()) 57 return; 58 Str << "String pool (NumStrings=" << StringToId.size() 59 << " NumIDs=" << ((NextID - FirstID) / IDIncrement) << "):"; 60 for (const auto &Tuple : StringToId) { 61 Str << " " << Tuple.first; 62 } 63 Str << "\n"; 64 } 65 66 private: 67 static constexpr IDType FirstID = 1; 68 static constexpr IDType IDIncrement = 2; 69 IDType NextID = FirstID; 70 std::unordered_map<std::string, std::unique_ptr<std::string>> StringToId; 71 }; 72 73 template <typename Traits> class StringID { 74 public: 75 using IDType = StringPool::IDType; 76 77 StringID() = default; // Create a default, invalid StringID. 78 StringID(const StringID &) = default; 79 StringID &operator=(const StringID &) = default; 80 81 /// Create a unique StringID without an actual string, by grabbing the next 82 /// unique integral ID from the Owner. createWithoutString(const typename Traits::OwnerType * Owner)83 static StringID createWithoutString(const typename Traits::OwnerType *Owner) { 84 return StringID(Owner); 85 } 86 /// Create a unique StringID that holds an actual string, by fetching or 87 /// adding the string from the Owner's pool. createWithString(const typename Traits::OwnerType * Owner,const std::string & Value)88 static StringID createWithString(const typename Traits::OwnerType *Owner, 89 const std::string &Value) { 90 return StringID(Owner, Value); 91 } 92 93 /// Tests whether the StringID was initialized with respect to an actual 94 /// std::string value, i.e. via StringID::createWithString(). hasStdString()95 bool hasStdString() const { return isValid() && ((ID & 0x1) == 0); } 96 getID()97 IDType getID() const { 98 assert(isValid()); 99 return ID; 100 } toString()101 const std::string &toString() const { 102 if (!hasStdString()) 103 llvm::report_fatal_error( 104 "toString() called when hasStdString() is false"); 105 return *reinterpret_cast<std::string *>(ID); 106 } toStringOrEmpty()107 std::string toStringOrEmpty() const { 108 if (hasStdString()) 109 return toString(); 110 return ""; 111 } 112 113 bool operator==(const StringID &Other) const { return ID == Other.ID; } 114 bool operator!=(const StringID &Other) const { return !(*this == Other); } 115 bool operator<(const StringID &Other) const { 116 const bool ThisHasString = hasStdString(); 117 const bool OtherHasString = Other.hasStdString(); 118 // Do a normal string comparison if both have strings. 119 if (ThisHasString && OtherHasString) 120 return this->toString() < Other.toString(); 121 // Use the ID as a tiebreaker if neither has a string. 122 if (!ThisHasString && !OtherHasString) 123 return ID < Other.ID; 124 // If exactly one has a string, then that one comes first. 125 assert(ThisHasString != OtherHasString); 126 return ThisHasString; 127 } 128 129 private: 130 static constexpr IDType InvalidID = 0; 131 IDType ID = InvalidID; 132 StringID(const typename Traits::OwnerType * Owner)133 explicit StringID(const typename Traits::OwnerType *Owner) 134 : ID(Traits::getStrings(Owner)->getNewID()) {} StringID(const typename Traits::OwnerType * Owner,const std::string & Value)135 StringID(const typename Traits::OwnerType *Owner, const std::string &Value) 136 : ID(Traits::getStrings(Owner)->getOrAddString(Value)) { 137 assert(hasStdString()); 138 } isValid()139 bool isValid() const { return ID != InvalidID; } 140 }; 141 142 // TODO(stichnot, jpp): Move GlobalStringPoolTraits definition into 143 // IceGlobalContext.h, once the include order issues are solved. 144 struct GlobalStringPoolTraits { 145 using OwnerType = GlobalContext; 146 static LockedPtr<StringPool> getStrings(const OwnerType *Owner); 147 }; 148 149 using GlobalString = StringID<struct GlobalStringPoolTraits>; 150 151 template <typename T> 152 Ostream &operator<<(Ostream &Str, const StringID<T> &Name) { 153 return Str << Name.toString(); 154 } 155 156 template <typename T> 157 std::string operator+(const std::string &A, const StringID<T> &B) { 158 return A + B.toString(); 159 } 160 161 template <typename T> 162 std::string operator+(const StringID<T> &A, const std::string &B) { 163 return A.toString() + B; 164 } 165 166 } // end of namespace Ice 167 168 namespace std { 169 template <typename T> struct hash<Ice::StringID<T>> { 170 size_t operator()(const Ice::StringID<T> &Key) const { 171 if (Key.hasStdString()) 172 return hash<std::string>()(Key.toString()); 173 return hash<Ice::StringPool::IDType>()(Key.getID()); 174 } 175 }; 176 } // end of namespace std 177 178 #endif // SUBZERO_SRC_ICESTRINGPOOL_H 179