summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lld/ELF/InputSection.cpp2
-rw-r--r--lld/ELF/OutputSections.cpp4
-rw-r--r--lld/ELF/OutputSections.h2
-rw-r--r--llvm/include/llvm/ADT/CachedHashString.h71
-rw-r--r--llvm/include/llvm/MC/StringTableBuilder.h32
-rw-r--r--llvm/lib/MC/StringTableBuilder.cpp29
-rw-r--r--llvm/unittests/MC/StringTableBuilderTest.cpp1
7 files changed, 88 insertions, 53 deletions
diff --git a/lld/ELF/InputSection.cpp b/lld/ELF/InputSection.cpp
index 24a45468739..be91b27c925 100644
--- a/lld/ELF/InputSection.cpp
+++ b/lld/ELF/InputSection.cpp
@@ -700,7 +700,7 @@ template <class ELFT> void MergeInputSection<ELFT>::finalizePieces() {
auto *OutSec = static_cast<MergeOutputSection<ELFT> *>(this->OutSec);
ArrayRef<uint8_t> D = this->getData(Piece);
StringRef S((const char *)D.data(), D.size());
- CachedHashString V(S, Piece.Hash);
+ CachedHashStringRef V(S, Piece.Hash);
Piece.OutputOff = OutSec->getOffset(V);
}
OffsetMap[Piece.InputOff] = Piece.OutputOff;
diff --git a/lld/ELF/OutputSections.cpp b/lld/ELF/OutputSections.cpp
index 14f206d3b6d..3d3d5a5bb28 100644
--- a/lld/ELF/OutputSections.cpp
+++ b/lld/ELF/OutputSections.cpp
@@ -1244,7 +1244,7 @@ void MergeOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
if (!Piece.Live)
continue;
StringRef Data = toStringRef(Sec->getData(Piece));
- CachedHashString V(Data, Piece.Hash);
+ CachedHashStringRef V(Data, Piece.Hash);
uintX_t OutputOffset = Builder.add(V);
if (!shouldTailMerge())
Piece.OutputOff = OutputOffset;
@@ -1252,7 +1252,7 @@ void MergeOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
}
template <class ELFT>
-unsigned MergeOutputSection<ELFT>::getOffset(CachedHashString Val) {
+unsigned MergeOutputSection<ELFT>::getOffset(CachedHashStringRef Val) {
return Builder.getOffset(Val);
}
diff --git a/lld/ELF/OutputSections.h b/lld/ELF/OutputSections.h
index 85b42267b16..41ec6abcae8 100644
--- a/lld/ELF/OutputSections.h
+++ b/lld/ELF/OutputSections.h
@@ -430,7 +430,7 @@ public:
uintX_t Alignment);
void addSection(InputSectionBase<ELFT> *S) override;
void writeTo(uint8_t *Buf) override;
- unsigned getOffset(llvm::CachedHashString Val);
+ unsigned getOffset(llvm::CachedHashStringRef Val);
void finalize() override;
void finalizePieces() override;
bool shouldTailMerge() const;
diff --git a/llvm/include/llvm/ADT/CachedHashString.h b/llvm/include/llvm/ADT/CachedHashString.h
new file mode 100644
index 00000000000..9d18d93e80e
--- /dev/null
+++ b/llvm/include/llvm/ADT/CachedHashString.h
@@ -0,0 +1,71 @@
+//===- llvm/ADT/CachedHashString.h - Prehashed string/StringRef -*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines CachedHashString and CachedHashStringRef. These are like
+// std::string and StringRef, except they store their hash in addition to their
+// string data.
+//
+// Unlike std::string, CachedHashString can be used in DenseSet/DenseMap
+// (because, unlike std::string, CachedHashString lets us have empty and
+// tombstone values).
+//
+// TODO: Add CachedHashString.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_CACHED_HASH_STRING_H
+#define LLVM_ADT_CACHED_HASH_STRING_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace llvm {
+
+/// A container which contains a StringRef plus a precomputed hash.
+class CachedHashStringRef {
+ const char *P;
+ uint32_t Size;
+ uint32_t Hash;
+
+public:
+ // Explicit because hashing a string isn't free.
+ explicit CachedHashStringRef(StringRef S)
+ : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
+
+ CachedHashStringRef(StringRef S, uint32_t Hash)
+ : P(S.data()), Size(S.size()), Hash(Hash) {
+ assert(S.size() <= std::numeric_limits<uint32_t>::max());
+ }
+
+ StringRef val() const { return StringRef(P, Size); }
+ uint32_t size() const { return Size; }
+ uint32_t hash() const { return Hash; }
+};
+
+template <> struct DenseMapInfo<CachedHashStringRef> {
+ static CachedHashStringRef getEmptyKey() {
+ return CachedHashStringRef(DenseMapInfo<StringRef>::getEmptyKey(), 0);
+ }
+ static CachedHashStringRef getTombstoneKey() {
+ return CachedHashStringRef(DenseMapInfo<StringRef>::getTombstoneKey(), 1);
+ }
+ static unsigned getHashValue(const CachedHashStringRef &S) {
+ assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
+ assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
+ return S.hash();
+ }
+ static bool isEqual(const CachedHashStringRef &LHS,
+ const CachedHashStringRef &RHS) {
+ return DenseMapInfo<StringRef>::isEqual(LHS.val(), RHS.val());
+ }
+};
+
+} // namespace llvm
+
+#endif
diff --git a/llvm/include/llvm/MC/StringTableBuilder.h b/llvm/include/llvm/MC/StringTableBuilder.h
index e63a3530eec..7da444f7bfb 100644
--- a/llvm/include/llvm/MC/StringTableBuilder.h
+++ b/llvm/include/llvm/MC/StringTableBuilder.h
@@ -10,38 +10,20 @@
#ifndef LLVM_MC_STRINGTABLEBUILDER_H
#define LLVM_MC_STRINGTABLEBUILDER_H
-#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/CachedHashString.h"
#include "llvm/ADT/DenseMap.h"
#include <cassert>
namespace llvm {
class raw_ostream;
-class CachedHashString {
- const char *P;
- uint32_t Size;
- uint32_t Hash;
-
-public:
- CachedHashString(StringRef S)
- : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
- CachedHashString(StringRef S, uint32_t Hash)
- : P(S.data()), Size(S.size()), Hash(Hash) {
- assert(S.size() <= std::numeric_limits<uint32_t>::max());
- }
-
- StringRef val() const { return StringRef(P, Size); }
- uint32_t size() const { return Size; }
- uint32_t hash() const { return Hash; }
-};
-
/// \brief Utility for building string tables with deduplicated suffixes.
class StringTableBuilder {
public:
enum Kind { ELF, WinCOFF, MachO, RAW };
private:
- DenseMap<CachedHashString, size_t> StringIndexMap;
+ DenseMap<CachedHashStringRef, size_t> StringIndexMap;
size_t Size = 0;
Kind K;
unsigned Alignment;
@@ -57,8 +39,8 @@ public:
/// \brief Add a string to the builder. Returns the position of S in the
/// table. The position will be changed if finalize is used.
/// Can only be used before the table is finalized.
- size_t add(CachedHashString S);
- size_t add(StringRef S) { return add(CachedHashString(S)); }
+ size_t add(CachedHashStringRef S);
+ size_t add(StringRef S) { return add(CachedHashStringRef(S)); }
/// \brief Analyze the strings and build the final table. No more strings can
/// be added after this point.
@@ -70,8 +52,10 @@ public:
/// \brief Get the offest of a string in the string table. Can only be used
/// after the table is finalized.
- size_t getOffset(CachedHashString S) const;
- size_t getOffset(StringRef S) const { return getOffset(CachedHashString(S)); }
+ size_t getOffset(CachedHashStringRef S) const;
+ size_t getOffset(StringRef S) const {
+ return getOffset(CachedHashStringRef(S));
+ }
size_t getSize() const { return Size; }
void clear();
diff --git a/llvm/lib/MC/StringTableBuilder.cpp b/llvm/lib/MC/StringTableBuilder.cpp
index e5d2a4ae58a..1a501bcafc1 100644
--- a/llvm/lib/MC/StringTableBuilder.cpp
+++ b/llvm/lib/MC/StringTableBuilder.cpp
@@ -9,6 +9,7 @@
#include "llvm/MC/StringTableBuilder.h"
#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallString.h"
#include "llvm/Support/COFF.h"
#include "llvm/Support/Endian.h"
#include "llvm/Support/raw_ostream.h"
@@ -17,28 +18,6 @@
using namespace llvm;
-namespace llvm {
-template <> struct DenseMapInfo<CachedHashString> {
- static CachedHashString getEmptyKey() {
- StringRef S = DenseMapInfo<StringRef>::getEmptyKey();
- return {S, 0};
- }
- static CachedHashString getTombstoneKey() {
- StringRef S = DenseMapInfo<StringRef>::getTombstoneKey();
- return {S, 0};
- }
- static unsigned getHashValue(CachedHashString Val) {
- assert(!isEqual(Val, getEmptyKey()) && "Cannot hash the empty key!");
- assert(!isEqual(Val, getTombstoneKey()) &&
- "Cannot hash the tombstone key!");
- return Val.hash();
- }
- static bool isEqual(CachedHashString A, CachedHashString B) {
- return DenseMapInfo<StringRef>::isEqual(A.val(), B.val());
- }
-};
-}
-
StringTableBuilder::~StringTableBuilder() {}
void StringTableBuilder::initSize() {
@@ -73,7 +52,7 @@ void StringTableBuilder::write(raw_ostream &OS) const {
OS << Data;
}
-typedef std::pair<CachedHashString, size_t> StringPair;
+typedef std::pair<CachedHashStringRef, size_t> StringPair;
void StringTableBuilder::write(uint8_t *Buf) const {
assert(isFinalized());
@@ -183,14 +162,14 @@ void StringTableBuilder::clear() {
StringIndexMap.clear();
}
-size_t StringTableBuilder::getOffset(CachedHashString S) const {
+size_t StringTableBuilder::getOffset(CachedHashStringRef S) const {
assert(isFinalized());
auto I = StringIndexMap.find(S);
assert(I != StringIndexMap.end() && "String is not in table!");
return I->second;
}
-size_t StringTableBuilder::add(CachedHashString S) {
+size_t StringTableBuilder::add(CachedHashStringRef S) {
if (K == WinCOFF)
assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
diff --git a/llvm/unittests/MC/StringTableBuilderTest.cpp b/llvm/unittests/MC/StringTableBuilderTest.cpp
index 517ada5ed96..f68350d90ba 100644
--- a/llvm/unittests/MC/StringTableBuilderTest.cpp
+++ b/llvm/unittests/MC/StringTableBuilderTest.cpp
@@ -7,6 +7,7 @@
//
//===----------------------------------------------------------------------===//
+#include "llvm/ADT/SmallString.h"
#include "llvm/MC/StringTableBuilder.h"
#include "llvm/Support/Endian.h"
#include "gtest/gtest.h"
OpenPOWER on IntegriCloud