• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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