Index: lld/trunk/ELF/InputSection.cpp =================================================================== --- lld/trunk/ELF/InputSection.cpp +++ lld/trunk/ELF/InputSection.cpp @@ -700,7 +700,7 @@ auto *OutSec = static_cast *>(this->OutSec); ArrayRef 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; Index: lld/trunk/ELF/OutputSections.h =================================================================== --- lld/trunk/ELF/OutputSections.h +++ lld/trunk/ELF/OutputSections.h @@ -430,7 +430,7 @@ uintX_t Alignment); void addSection(InputSectionBase *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; Index: lld/trunk/ELF/OutputSections.cpp =================================================================== --- lld/trunk/ELF/OutputSections.cpp +++ lld/trunk/ELF/OutputSections.cpp @@ -1244,7 +1244,7 @@ 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 @@ } template -unsigned MergeOutputSection::getOffset(CachedHashString Val) { +unsigned MergeOutputSection::getOffset(CachedHashStringRef Val) { return Builder.getOffset(Val); } Index: llvm/trunk/include/llvm/ADT/CachedHashString.h =================================================================== --- llvm/trunk/include/llvm/ADT/CachedHashString.h +++ llvm/trunk/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::getHashValue(S)) {} + + CachedHashStringRef(StringRef S, uint32_t Hash) + : P(S.data()), Size(S.size()), Hash(Hash) { + assert(S.size() <= std::numeric_limits::max()); + } + + StringRef val() const { return StringRef(P, Size); } + uint32_t size() const { return Size; } + uint32_t hash() const { return Hash; } +}; + +template <> struct DenseMapInfo { + static CachedHashStringRef getEmptyKey() { + return CachedHashStringRef(DenseMapInfo::getEmptyKey(), 0); + } + static CachedHashStringRef getTombstoneKey() { + return CachedHashStringRef(DenseMapInfo::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::isEqual(LHS.val(), RHS.val()); + } +}; + +} // namespace llvm + +#endif Index: llvm/trunk/include/llvm/MC/StringTableBuilder.h =================================================================== --- llvm/trunk/include/llvm/MC/StringTableBuilder.h +++ llvm/trunk/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 namespace llvm { class raw_ostream; -class CachedHashString { - const char *P; - uint32_t Size; - uint32_t Hash; - -public: - CachedHashString(StringRef S) - : CachedHashString(S, DenseMapInfo::getHashValue(S)) {} - CachedHashString(StringRef S, uint32_t Hash) - : P(S.data()), Size(S.size()), Hash(Hash) { - assert(S.size() <= std::numeric_limits::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 StringIndexMap; + DenseMap StringIndexMap; size_t Size = 0; Kind K; unsigned Alignment; @@ -57,8 +39,8 @@ /// \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 @@ /// \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(); Index: llvm/trunk/lib/MC/StringTableBuilder.cpp =================================================================== --- llvm/trunk/lib/MC/StringTableBuilder.cpp +++ llvm/trunk/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 { - static CachedHashString getEmptyKey() { - StringRef S = DenseMapInfo::getEmptyKey(); - return {S, 0}; - } - static CachedHashString getTombstoneKey() { - StringRef S = DenseMapInfo::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::isEqual(A.val(), B.val()); - } -}; -} - StringTableBuilder::~StringTableBuilder() {} void StringTableBuilder::initSize() { @@ -73,7 +52,7 @@ OS << Data; } -typedef std::pair StringPair; +typedef std::pair StringPair; void StringTableBuilder::write(uint8_t *Buf) const { assert(isFinalized()); @@ -183,14 +162,14 @@ 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!"); Index: llvm/trunk/unittests/MC/StringTableBuilderTest.cpp =================================================================== --- llvm/trunk/unittests/MC/StringTableBuilderTest.cpp +++ llvm/trunk/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"