From 715bccae4a4a70340333ea0645553d497736d7f7 Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Fri, 23 Oct 2015 21:48:05 +0000 Subject: [PATCH] Add a RAW mode to StringTableBuilder. In this mode it just tries to tail merge the strings without imposing any other format constrains. It will not, for example, add a null byte between them. Also add support for keeping a tentative size and offset if we decide to not optimize after all. This will be used shortly in lld for merging SHF_STRINGS sections. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251153 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/MC/MCMachObjectWriter.h | 2 +- include/llvm/MC/StringTableBuilder.h | 23 ++++++++++++++--------- lib/MC/ELFObjectWriter.cpp | 4 ++-- lib/MC/MachObjectWriter.cpp | 2 +- lib/MC/StringTableBuilder.cpp | 21 ++++++++++++++++----- lib/MC/WinCOFFObjectWriter.cpp | 4 ++-- tools/yaml2obj/yaml2elf.cpp | 8 ++++---- unittests/MC/StringTableBuilderTest.cpp | 8 ++++---- 8 files changed, 44 insertions(+), 28 deletions(-) diff --git a/include/llvm/MC/MCMachObjectWriter.h b/include/llvm/MC/MCMachObjectWriter.h index fe1227fe3dd..730b0e4d83a 100644 --- a/include/llvm/MC/MCMachObjectWriter.h +++ b/include/llvm/MC/MCMachObjectWriter.h @@ -104,7 +104,7 @@ class MachObjectWriter : public MCObjectWriter { /// \name Symbol Table Data /// @{ - StringTableBuilder StringTable; + StringTableBuilder StringTable{StringTableBuilder::MachO}; std::vector LocalSymbolData; std::vector ExternalSymbolData; std::vector UndefinedSymbolData; diff --git a/include/llvm/MC/StringTableBuilder.h b/include/llvm/MC/StringTableBuilder.h index 68ad76e7fae..adde86b4558 100644 --- a/include/llvm/MC/StringTableBuilder.h +++ b/include/llvm/MC/StringTableBuilder.h @@ -18,23 +18,26 @@ namespace llvm { /// \brief Utility for building string tables with deduplicated suffixes. class StringTableBuilder { +public: + enum Kind { ELF, WinCOFF, MachO, RAW }; + +private: SmallString<256> StringTable; DenseMap StringIndexMap; + size_t Size = 0; + Kind K; public: - /// \brief Add a string to the builder. Returns a StringRef to the internal - /// copy of s. Can only be used before the table is finalized. - void add(StringRef S); + StringTableBuilder(Kind K); - enum Kind { - ELF, - WinCOFF, - MachO - }; + /// \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(StringRef S); /// \brief Analyze the strings and build the final table. No more strings can /// be added after this point. - void finalize(Kind K); + void finalize(); /// \brief Retrieve the string table data. Can only be used after the table /// is finalized. @@ -47,6 +50,8 @@ public: /// after the table is finalized. size_t getOffset(StringRef S) const; + const DenseMap &getMap() const { return StringIndexMap; } + size_t getSize() const { return Size; } void clear(); private: diff --git a/lib/MC/ELFObjectWriter.cpp b/lib/MC/ELFObjectWriter.cpp index 5fdfcf9ef2d..230d3d775b1 100644 --- a/lib/MC/ELFObjectWriter.cpp +++ b/lib/MC/ELFObjectWriter.cpp @@ -109,7 +109,7 @@ class ELFObjectWriter : public MCObjectWriter { BumpPtrAllocator Alloc; StringSaver VersionSymSaver{Alloc}; - StringTableBuilder StrTabBuilder; + StringTableBuilder StrTabBuilder{StringTableBuilder::ELF}; /// @} @@ -880,7 +880,7 @@ void ELFObjectWriter::computeSymbolTable( for (const std::string &Name : FileNames) StrTabBuilder.add(Name); - StrTabBuilder.finalize(StringTableBuilder::ELF); + StrTabBuilder.finalize(); for (const std::string &Name : FileNames) Writer.writeSymbol(StrTabBuilder.getOffset(Name), diff --git a/lib/MC/MachObjectWriter.cpp b/lib/MC/MachObjectWriter.cpp index d5184f1d9a4..17023d82d62 100644 --- a/lib/MC/MachObjectWriter.cpp +++ b/lib/MC/MachObjectWriter.cpp @@ -520,7 +520,7 @@ void MachObjectWriter::computeSymbolTable( StringTable.add(Symbol.getName()); } - StringTable.finalize(StringTableBuilder::MachO); + StringTable.finalize(); // Build the symbol arrays but only for non-local symbols. // diff --git a/lib/MC/StringTableBuilder.cpp b/lib/MC/StringTableBuilder.cpp index fc6c3bc0902..6210238e72a 100644 --- a/lib/MC/StringTableBuilder.cpp +++ b/lib/MC/StringTableBuilder.cpp @@ -16,6 +16,8 @@ using namespace llvm; +StringTableBuilder::StringTableBuilder(Kind K) : K(K) {} + static int compareBySuffix(std::pair *const *AP, std::pair *const *BP) { StringRef A = (*AP)->first; @@ -32,7 +34,7 @@ static int compareBySuffix(std::pair *const *AP, return SizeB - SizeA; } -void StringTableBuilder::finalize(Kind K) { +void StringTableBuilder::finalize() { std::vector *> Strings; Strings.reserve(StringIndexMap.size()); for (std::pair &P : StringIndexMap) @@ -41,6 +43,8 @@ void StringTableBuilder::finalize(Kind K) { array_pod_sort(Strings.begin(), Strings.end(), compareBySuffix); switch (K) { + case RAW: + break; case ELF: case MachO: // Start the table with a NUL byte. @@ -59,17 +63,19 @@ void StringTableBuilder::finalize(Kind K) { assert(S.size() > COFF::NameSize && "Short string in COFF string table!"); if (Previous.endswith(S)) { - P->second = StringTable.size() - 1 - S.size(); + P->second = StringTable.size() - S.size() - (K != RAW); continue; } P->second = StringTable.size(); StringTable += S; - StringTable += '\x00'; + if (K != RAW) + StringTable += '\x00'; Previous = S; } switch (K) { + case RAW: case ELF: break; case MachO: @@ -85,6 +91,8 @@ void StringTableBuilder::finalize(Kind K) { StringTable.data(), Size); break; } + + Size = StringTable.size(); } void StringTableBuilder::clear() { @@ -99,7 +107,10 @@ size_t StringTableBuilder::getOffset(StringRef S) const { return I->second; } -void StringTableBuilder::add(StringRef S) { +size_t StringTableBuilder::add(StringRef S) { assert(!isFinalized()); - StringIndexMap.insert(std::make_pair(S, 0)); + auto P = StringIndexMap.insert(std::make_pair(S, Size)); + if (P.second) + Size += S.size() + (K != RAW); + return P.first->second; } diff --git a/lib/MC/WinCOFFObjectWriter.cpp b/lib/MC/WinCOFFObjectWriter.cpp index f251942161d..8d4d3df21ab 100644 --- a/lib/MC/WinCOFFObjectWriter.cpp +++ b/lib/MC/WinCOFFObjectWriter.cpp @@ -127,7 +127,7 @@ public: COFF::header Header; sections Sections; symbols Symbols; - StringTableBuilder Strings; + StringTableBuilder Strings{StringTableBuilder::WinCOFF}; // Maps used during object file creation. section_map SectionMap; @@ -908,7 +908,7 @@ void WinCOFFObjectWriter::writeObject(MCAssembler &Asm, for (const auto &S : Symbols) if (S->should_keep() && S->Name.size() > COFF::NameSize) Strings.add(S->Name); - Strings.finalize(StringTableBuilder::WinCOFF); + Strings.finalize(); // Set names. for (const auto &S : Sections) diff --git a/tools/yaml2obj/yaml2elf.cpp b/tools/yaml2obj/yaml2elf.cpp index 849f202b126..d03986e9c88 100644 --- a/tools/yaml2obj/yaml2elf.cpp +++ b/tools/yaml2obj/yaml2elf.cpp @@ -105,10 +105,10 @@ class ELFState { typedef typename object::ELFFile::Elf_Rela Elf_Rela; /// \brief The future ".strtab" section. - StringTableBuilder DotStrtab; + StringTableBuilder DotStrtab{StringTableBuilder::ELF}; /// \brief The future ".shstrtab" section. - StringTableBuilder DotShStrtab; + StringTableBuilder DotShStrtab{StringTableBuilder::ELF}; NameToIdxMap SN2I; NameToIdxMap SymN2I; @@ -193,7 +193,7 @@ bool ELFState::initSectionHeaders(std::vector &SHeaders, for (const auto &Sec : Doc.Sections) DotShStrtab.add(Sec->Name); - DotShStrtab.finalize(StringTableBuilder::ELF); + DotShStrtab.finalize(); for (const auto &Sec : Doc.Sections) { zero(SHeader); @@ -286,7 +286,7 @@ void ELFState::initSymtabSectionHeader(Elf_Shdr &SHeader, DotStrtab.add(Sym.Name); for (const auto &Sym : Doc.Symbols.Weak) DotStrtab.add(Sym.Name); - DotStrtab.finalize(StringTableBuilder::ELF); + DotStrtab.finalize(); addSymbols(Doc.Symbols.Local, Syms, ELF::STB_LOCAL); addSymbols(Doc.Symbols.Global, Syms, ELF::STB_GLOBAL); diff --git a/unittests/MC/StringTableBuilderTest.cpp b/unittests/MC/StringTableBuilderTest.cpp index 716b9c7ae87..4cc0bda0a03 100644 --- a/unittests/MC/StringTableBuilderTest.cpp +++ b/unittests/MC/StringTableBuilderTest.cpp @@ -17,13 +17,13 @@ using namespace llvm; namespace { TEST(StringTableBuilderTest, BasicELF) { - StringTableBuilder B; + StringTableBuilder B(StringTableBuilder::ELF); B.add("foo"); B.add("bar"); B.add("foobar"); - B.finalize(StringTableBuilder::ELF); + B.finalize(); std::string Expected; Expected += '\x00'; @@ -39,14 +39,14 @@ TEST(StringTableBuilderTest, BasicELF) { } TEST(StringTableBuilderTest, BasicWinCOFF) { - StringTableBuilder B; + StringTableBuilder B(StringTableBuilder::WinCOFF); // Strings must be 9 chars or longer to go in the table. B.add("hippopotamus"); B.add("pygmy hippopotamus"); B.add("river horse"); - B.finalize(StringTableBuilder::WinCOFF); + B.finalize(); // size_field + "pygmy hippopotamus\0" + "river horse\0" uint32_t ExpectedSize = 4 + 19 + 12; -- 2.34.1