[Support] Add a UniqueStringSaver: like StringSaver, but deduplicating.

[sammccall]

Summary

Clarify contract of StringSaver (it null-terminates, callers rely on it).

[hokein]

Thanks!

lib/Support/StringSaver.cpp

26 ↗

(On Diff #156476)

While we have nice assertion message here, but in return we pay an extra lookup cost. I think we should avoid it (this function is likely to be used in hot path).

Maybe just

auto It = Unique.insert(S);
if (It.second) {
  *It.first = Strings.save(V);
}
return *It.first.

[sammccall]

Simplify insertion.

lib/Support/StringSaver.cpp

26 ↗

(On Diff #156476)

I was all ready to explain why this doesn't work (keys in a map/set are const) but... it does.
I think this means DenseMap is unsafe (at least less safe than unordered_map) but at least this usage is safe. Left a comment.

[hokein]

LGTM.

lib/Support/StringSaver.cpp

26 ↗

(On Diff #156476)

Yeah, it is tricky.

llvm/trunk/include/llvm/Support/StringSaver.h

 //===- llvm/Support/StringSaver.h -------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_STRINGSAVER_H
 #define LLVM_SUPPORT_STRINGSAVER_H
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/Allocator.h"
 
 namespace llvm {
 
-/// Saves strings in the inheritor's stable storage and returns a
+/// Saves strings in the provided stable storage and returns a
 /// StringRef with a stable character pointer.
 class StringSaver final {
   BumpPtrAllocator &Alloc;
 
 public:
   StringSaver(BumpPtrAllocator &Alloc) : Alloc(Alloc) {}
+
+  // All returned strings are null-terminated: *save(S).end() == 0.
   StringRef save(const char *S) { return save(StringRef(S)); }
   StringRef save(StringRef S);
   StringRef save(const Twine &S) { return save(StringRef(S.str())); }
   StringRef save(const std::string &S) { return save(StringRef(S)); }
 };
+
+/// Saves strings in the provided stable storage and returns a StringRef with a
+/// stable character pointer. Saving the same string yields the same StringRef.
+///
+/// Compared to StringSaver, it does more work but avoids saving the same string
+/// multiple times.
+///
+/// Compared to StringPool, it performs fewer allocations but doesn't support
+/// refcounting/deletion.
+class UniqueStringSaver final {
+  StringSaver Strings;
+  llvm::DenseSet<llvm::StringRef> Unique;
+
+public:
+  UniqueStringSaver(BumpPtrAllocator &Alloc) : Strings(Alloc) {}
+
+  // All returned strings are null-terminated: *save(S).end() == 0.
+  StringRef save(const char *S) { return save(StringRef(S)); }
+  StringRef save(StringRef S);
+  StringRef save(const Twine &S) { return save(StringRef(S.str())); }
+  StringRef save(const std::string &S) { return save(StringRef(S)); }
+};
+
 }
 #endif

llvm/trunk/lib/Support/StringSaver.cpp

 using namespace llvm;
 
 StringRef StringSaver::save(StringRef S) {
   char *P = Alloc.Allocate<char>(S.size() + 1);
   memcpy(P, S.data(), S.size());
   P[S.size()] = '\0';
   return StringRef(P, S.size());
 }
+
+StringRef UniqueStringSaver::save(StringRef S) {
+  auto R = Unique.insert(S);
+  if (R.second)                 // cache miss, need to actually save the string
+    *R.first = Strings.save(S); // safe replacement with equal value
+  return *R.first;
+}