ELFObjectWriter: optimize suffices in strtab

[hans]

Summary

We already do this for shstrtab, so might as well do it for strtab. This extracts the code for this into a separate class. It might be overkill to have this in a separate file, but I figured maybe this is useful for other object formats and lld. If not, we can just move it into ELFObjectWriter.cpp.

I mostly wanted to do this for the general principle, but it does save a little bit on object file size. I tried this on a clang bootstrap and saved 0.54% on the sum of object file sizes (1.14 MB out of 212 MB for a release build).

[• rafael]

I am in favour of moving this to its own file, by why ADT? All the listed potential users would be using lib/Object, so it can stay there, no?

LGTM with the class being somewhere in lib/Object.

lib/Support/StringTableBuilder.cpp

35

Starting the table with a null character makes this ELF specific? That is fine for now, but please comment.

test/MC/ELF/symref.s

116

Just remove the number. The printed name is all that the test needs. These are leftover from the old and horrible elf-dump script.

[silvas]

Please cross-reference this from the TODO above StringTableBuilder in tools/yaml2obj/yaml2elf.h

include/llvm/ADT/StringTableBuilder.h

18–19

Please add a class comment indicating that this is primarily a convenience for doing suffix deduplication.

[silvas]

include/llvm/ADT/StringTableBuilder.h

18–19

also, you probably want to call out the very finicky nature of finalize(), since the behavior of the class changes completely before and after it is called (it would be cleaner and safer to have two separate classes, but I think that might complicate things enough to be a net loss)

[hans]

I am in favour of moving this to its own file, by why ADT? All the listed potential users would be using lib/Object, so it can stay there, no?

Yes, lib/Object is of course the right place. Moved it there now.

LGTM with the class being somewhere in lib/Object.

Thanks! Landing..

Please cross-reference this from the TODO above StringTableBuilder in tools/yaml2obj/yaml2elf.h

Done. I'll see if I can hook this up in a follow-up patch.

include/llvm/ADT/StringTableBuilder.h

18–19

Done.

18–19

I figured the asserts make it pretty clear what's going on, but I've also expanded the comments a bit.

lib/Support/StringTableBuilder.cpp

35

Done.

test/MC/ELF/symref.s

116

Done.

[hans]

This was committed in r207670.

include/llvm/ADT/StringTableBuilder.h

+//===-- StringTableBuilder.h - String table building utility ------*- C++ -*-=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_STRINGTABLE_BUILDER_H
+#define LLVM_ADT_STRINGTABLE_BUILDER_H
+
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringMap.h"
+#include <cassert>
+
+namespace llvm {
+
+class StringTableBuilder {
+  SmallString<256> StringTable;
+  StringMap<size_t> StringIndexMap;
+
+public:
+  /// \brief Add a string to the builder. Returns a StringRef to the internal
+  /// copy of s.
+  StringRef add(StringRef s) {
+    assert(!isFinalized());
+    return StringIndexMap.GetOrCreateValue(s, 0).getKey();
+  }
+
+  /// \brief Analyze the strings and build the final table. No more strings can
+  /// be added after this point.
+  void finalize();
+
+  /// \brief Retrieve the string table data.
+  StringRef data() {
+    assert(isFinalized());
+    return StringTable;
+  }
+
+  /// \brief Get the offest of a string in the string table.
+  size_t getOffset(StringRef s) {
+    assert(isFinalized());
+    assert(StringIndexMap.count(s) && "String is not in table!");
+    return StringIndexMap[s];
+  }
+
+private:
+  bool isFinalized() {
+    return !StringTable.empty();
+  }
+};
+
+} // end llvm namespace
+
+#endif

lib/MC/ELFObjectWriter.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringTableBuilder.h"
 #include "llvm/MC/MCAsmBackend.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCAsmLayout.h"

       MCSymbolData *SymbolData;
       uint64_t StringIndex;
       uint32_t SectionIndex;
+      StringRef Name;
 
       // Support lexicographic sorting.
       bool operator<(const ELFSymbolData &RHS) const {
-        return SymbolData->getSymbol().getName() <
-               RHS.SymbolData->getSymbol().getName();
+        return Name < RHS.Name;
       }
     };
 

 
     llvm::DenseMap<const MCSectionData *, std::vector<ELFRelocationEntry>>
     Relocations;
-    DenseMap<const MCSection*, uint64_t> SectionStringTableIndex;
+    StringTableBuilder ShStrTabBuilder;
 
     /// @}
     /// @name Symbol Table Data
     /// @{
 
-    SmallString<256> StringTable;
+    StringTableBuilder StrTabBuilder;
     std::vector<uint64_t> FileSymbolData;
     std::vector<ELFSymbolData> LocalSymbolData;
     std::vector<ELFSymbolData> ExternalSymbolData;

                                        SectionIndexMapTy &SectionIndexMap) {
   // The string table must be emitted first because we need the index
   // into the string table for all the symbol names.
-  assert(StringTable.size() && "Missing string table");
 
   // FIXME: Make sure the start of the symbol table is aligned.
 

     MCELF::SetBinding(Data, ELF::STB_GLOBAL);
   }
 
-  // Index 0 is always the empty string.
-  StringMap<uint64_t> StringIndexMap;
-  StringTable += '\x00';
-
-  // FIXME: We could optimize suffixes in strtab in the same way we
-  // optimize them in shstrtab.
-
-  for (MCAssembler::const_file_name_iterator it = Asm.file_names_begin(),
-                                            ie = Asm.file_names_end();
-                                            it != ie;
-                                            ++it) {
-    StringRef Name = *it;
-    uint64_t &Entry = StringIndexMap[Name];
-    if (!Entry) {
-      Entry = StringTable.size();
-      StringTable += Name;
-      StringTable += '\x00';
-    }
-    FileSymbolData.push_back(Entry);
-  }
-
   // Add the data for the symbols.
   for (MCSymbolData &SD : Asm.symbols()) {
     const MCSymbol &Symbol = SD.getSymbol();

     // @@ in defined ones.
     StringRef Name = Symbol.getName();
     SmallString<32> Buf;
-
     size_t Pos = Name.find("@@@");
     if (Pos != StringRef::npos) {
       Buf += Name.substr(0, Pos);

       Buf += Name.substr(Pos + Skip);
       Name = Buf;
     }
+    MSD.Name = StrTabBuilder.add(Name);
 
-    uint64_t &Entry = StringIndexMap[Name];
-    if (!Entry) {
-      Entry = StringTable.size();
-      StringTable += Name;
-      StringTable += '\x00';
-    }
-    MSD.StringIndex = Entry;
     if (MSD.SectionIndex == ELF::SHN_UNDEF)
       UndefinedSymbolData.push_back(MSD);
     else if (Local)

       ExternalSymbolData.push_back(MSD);
   }
 
+  for (auto i = Asm.file_names_begin(), e = Asm.file_names_end(); i != e; ++i)
+    StrTabBuilder.add(*i);
+
+  StrTabBuilder.finalize();
+
+  for (auto i = Asm.file_names_begin(), e = Asm.file_names_end(); i != e; ++i)
+    FileSymbolData.push_back(StrTabBuilder.getOffset(*i));
+
+  for (ELFSymbolData& MSD : LocalSymbolData)
+    MSD.StringIndex = StrTabBuilder.getOffset(MSD.Name);
+  for (ELFSymbolData& MSD : ExternalSymbolData)
+    MSD.StringIndex = StrTabBuilder.getOffset(MSD.Name);
+  for (ELFSymbolData& MSD : UndefinedSymbolData)
+    MSD.StringIndex = StrTabBuilder.getOffset(MSD.Name);
+
   // Symbols are required to be in lexicographic order.
   array_pod_sort(LocalSymbolData.begin(), LocalSymbolData.end());
   array_pod_sort(ExternalSymbolData.begin(), ExternalSymbolData.end());

   }
 }
 
-static int compareBySuffix(const MCSectionELF *const *a,
-                           const MCSectionELF *const *b) {
-  const StringRef &NameA = (*a)->getSectionName();
-  const StringRef &NameB = (*b)->getSectionName();
-  const unsigned sizeA = NameA.size();
-  const unsigned sizeB = NameB.size();
-  const unsigned len = std::min(sizeA, sizeB);
-  for (unsigned int i = 0; i < len; ++i) {
-    char ca = NameA[sizeA - i - 1];
-    char cb = NameB[sizeB - i - 1];
-    if (ca != cb)
-      return cb - ca;
-  }
-
-  return sizeB - sizeA;
-}
-
 void ELFObjectWriter::CreateMetadataSections(MCAssembler &Asm,
                                              MCAsmLayout &Layout,
                                              SectionIndexMapTy &SectionIndexMap,

   WriteSymbolTable(F, Asm, Layout, SectionIndexMap);
 
   F = new MCDataFragment(&StrtabSD);
-  F->getContents().append(StringTable.begin(), StringTable.end());
+  F->getContents().append(StrTabBuilder.data().begin(),
+                          StrTabBuilder.data().end());
 
   F = new MCDataFragment(&ShstrtabSD);
 
-  std::vector<const MCSectionELF*> Sections;
-  for (MCAssembler::const_iterator it = Asm.begin(),
-         ie = Asm.end(); it != ie; ++it) {
+  // Section header string table.
+  for (auto it = Asm.begin(), ie = Asm.end(); it != ie; ++it) {
     const MCSectionELF &Section =
       static_cast<const MCSectionELF&>(it->getSection());
-    Sections.push_back(&Section);
-  }
-  array_pod_sort(Sections.begin(), Sections.end(), compareBySuffix);
-
-  // Section header string table.
-  //
-  // The first entry of a string table holds a null character so skip
-  // section 0.
-  uint64_t Index = 1;
-  F->getContents().push_back('\x00');
-
-  for (unsigned int I = 0, E = Sections.size(); I != E; ++I) {
-    const MCSectionELF &Section = *Sections[I];
-
-    StringRef Name = Section.getSectionName();
-    if (I != 0) {
-      StringRef PreviousName = Sections[I - 1]->getSectionName();
-      if (PreviousName.endswith(Name)) {
-        SectionStringTableIndex[&Section] = Index - Name.size() - 1;
-        continue;
-      }
-    }
-    // Remember the index into the string table so we can write it
-    // into the sh_name field of the section header table.
-    SectionStringTableIndex[&Section] = Index;
-
-    Index += Name.size() + 1;
-    F->getContents().append(Name.begin(), Name.end());
-    F->getContents().push_back('\x00');
+    ShStrTabBuilder.add(Section.getSectionName());
   }
+  ShStrTabBuilder.finalize();
+  F->getContents().append(ShStrTabBuilder.data().begin(),
+                          ShStrTabBuilder.data().end());
 }
 
 void ELFObjectWriter::CreateIndexedSections(MCAssembler &Asm,

 
   switch(Section.getType()) {
   case ELF::SHT_DYNAMIC:
-    sh_link = SectionStringTableIndex[&Section];
+    sh_link = ShStrTabBuilder.getOffset(Section.getSectionName());
     sh_info = 0;
     break;
 

     }
   }
 
-  WriteSecHdrEntry(SectionStringTableIndex[&Section], Section.getType(),
+  WriteSecHdrEntry(ShStrTabBuilder.getOffset(Section.getSectionName()),
+                   Section.getType(),
                    Section.getFlags(), 0, Offset, Size, sh_link, sh_info,
                    Alignment, Section.getEntrySize());
 }

lib/Support/CMakeLists.txt

   StringPool.cpp
   StringRef.cpp
   StringRefMemoryObject.cpp
+  StringTableBuilder.cpp
   SystemUtils.cpp
   Timer.cpp
   ToolOutputFile.cpp

lib/Support/StringTableBuilder.cpp

+//===-- StringTableBuilder.cpp - String table building utility ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/StringTableBuilder.h"
+#include "llvm/ADT/SmallVector.h"
+
+using namespace llvm;
+
+static bool compareBySuffix(StringRef a, StringRef b) {
+  size_t sizeA = a.size();
+  size_t sizeB = b.size();
+  size_t len = std::min(sizeA, sizeB);
+  for (size_t i = 0; i < len; ++i) {
+    char ca = a[sizeA - i - 1];
+    char cb = b[sizeB - i - 1];
+    if (ca != cb)
+      return ca > cb;
+  }
+  return sizeA > sizeB;
+}
+
+void StringTableBuilder::finalize() {
+  SmallVector<StringRef, 8> Strings;
+  for (auto i = StringIndexMap.begin(), e = StringIndexMap.end(); i != e; ++i)
+    Strings.push_back(i->getKey());
+
+  std::sort(Strings.begin(), Strings.end(), compareBySuffix);
+
+  StringTable += '\x00';
+  StringRef Previous;
+  for (StringRef s : Strings) {
+    if (Previous.endswith(s)) {
+      StringIndexMap[s] = StringTable.size() - 1 - s.size();
+      continue;
+    }
+
+    StringIndexMap[s] = StringTable.size();
+    StringTable += s;
+    StringTable += '\x00';
+    Previous = s;
+  }
+}

test/MC/AArch64/tls-relocs.s

 
 // CHECK-ELF:      Symbols [
 // CHECK-ELF:        Symbol {
-// CHECK-ELF:          Name: var (6)
+// CHECK-ELF:          Name: var (1)
 // CHECK-ELF-NEXT:     Value:
 // CHECK-ELF-NEXT:     Size:
 // CHECK-ELF-NEXT:     Binding: Global

test/MC/ARM64/tls-relocs.s

 
 // CHECK-ELF:      Symbols [
 // CHECK-ELF:        Symbol {
-// CHECK-ELF:          Name: var (6)
+// CHECK-ELF:          Name: var (1)
 // CHECK-ELF-NEXT:     Value:
 // CHECK-ELF-NEXT:     Size:
 // CHECK-ELF-NEXT:     Binding: Global

test/MC/ELF/comdat.s

 // Test that g1 and g2 are local, but g3 is an undefined global.
 
 // CHECK:        Symbol {
-// CHECK:          Name: g1 (1)
+// CHECK:          Name: g1 (7)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:   }
 
 // CHECK:        Symbol {
-// CHECK:          Name: g3 (7)
+// CHECK:          Name: g3 (1)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

test/MC/ELF/common.s

   .comm common1,1,1
 
 // CHECK:        Symbol {
-// CHECK:          Name: common1 (1)
+// CHECK:          Name: common1 (45)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 1
 // CHECK-NEXT:     Binding: Local

   .comm common2,1,1
 
 // CHECK:        Symbol {
-// CHECK:          Name: common2 (9)
+// CHECK:          Name: common2 (37)
 // CHECK-NEXT:     Value: 0x1
 // CHECK-NEXT:     Size: 1
 // CHECK-NEXT:     Binding: Local

         .comm common6,8,16
 
 // CHECK:        Symbol {
-// CHECK:          Name: common6 (17)
+// CHECK:          Name: common6 (5)
 // CHECK-NEXT:     Value: 0x10
 // CHECK-NEXT:     Size: 8
 // CHECK-NEXT:     Binding: Local

   .comm common3,4,4
 
 // CHECK:        Symbol {
-// CHECK:          Name: common3 (25)
+// CHECK:          Name: common3 (29)
 // CHECK-NEXT:     Value: 0x4
 // CHECK-NEXT:     Size: 4
 // CHECK-NEXT:     Binding: Global

   .comm common4,40,16
 
 // CHECK:        Symbol {
-// CHECK:          Name: common4 (37)
+// CHECK:          Name: common4 (21)
 // CHECK-NEXT:     Value: 0x10
 // CHECK-NEXT:     Size: 40
 // CHECK-NEXT:     Binding: Global

         .comm common5,4,4
 
 // CHECK:        Symbol {
-// CHECK:          Name: common5 (45)
+// CHECK:          Name: common5 (13)
 // CHECK-NEXT:     Value: 0x4
 // CHECK-NEXT:     Size: 4
 // CHECK-NEXT:     Binding: Global

test/MC/ELF/file-double.s

 bar.c:
 
 // CHECK:        Symbol {
-// CHECK:          Name: foo.c (1)
+// CHECK:          Name: foo.c (7)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Other: 0
 // CHECK-NEXT:     Section: Absolute (0xFFF1)
 // CHECK-NEXT:   }
-// CHECK:          Name: bar.c (7)
+// CHECK:          Name: bar.c (1)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Section: Absolute (0xFFF1)
 // CHECK-NEXT:   }
 // CHECK:        Symbol {
-// CHECK:        Name: bar.c (7)
+// CHECK:        Name: bar.c (1)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK:        Symbol {
-// CHECK:        Name: foo.c (1)
+// CHECK:        Name: foo.c (7)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

test/MC/ELF/lcomm.s

 .lcomm B, 32 << 20
 
 // CHECK:        Symbol {
-// CHECK:          Name: A (1)
+// CHECK:          Name: A (3)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 5
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Section: .bss (0x3)
 // CHECK-NEXT:   }
 // CHECK:        Symbol {
-// CHECK:          Name: B (3)
+// CHECK:          Name: B (1)
 // CHECK-NEXT:     Value: 0x5
 // CHECK-NEXT:     Size: 33554432
 // CHECK-NEXT:     Binding: Local

test/MC/ELF/many-sections-2.s

 
 
 // Test that both a and b show up in the correct section.
-// SYMBOLS:         Name: a (1)
+// SYMBOLS:         Name: a (3)
 // SYMBOLS-NEXT:    Value: 0x0
 // SYMBOLS-NEXT:    Size: 0
 // SYMBOLS-NEXT:    Binding: Local (0x0)

 // SYMBOLS-NEXT:    Section: last (0xFF00)
 // SYMBOLS-NEXT:  }
 // SYMBOLS-NEXT:  Symbol {
-// SYMBOLS-NEXT:    Name: b (3)
+// SYMBOLS-NEXT:    Name: b (1)
 // SYMBOLS-NEXT:    Value: 0x1
 // SYMBOLS-NEXT:    Size: 0
 // SYMBOLS-NEXT:    Binding: Local (0x0)

test/MC/ELF/pic-diff.s

 // CHECK-NEXT: ]
 
 // CHECK:        Symbol {
-// CHECK:          Name: baz (5)
+// CHECK:          Name: baz (1)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

test/MC/ELF/pr9292.s

 
 
 // CHECK:        Symbol {
-// CHECK:          Name: bar (5)
+// CHECK:          Name: bar (1)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo (1)
+// CHECK-NEXT:     Name: foo (5)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

test/MC/ELF/set.s

 .set kernbase,0xffffffff80000000
 
 // CHECK:        Symbol {
-// CHECK:          Name: kernbase (1)
+// CHECK:          Name: kernbase (5)
 // CHECK-NEXT:     Value: 0xFFFFFFFF80000000
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 
 // Test that there is an undefined reference to bar
 // CHECK:        Symbol {
-// CHECK:          Name: bar (10)
+// CHECK:          Name: bar (1)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

test/MC/ELF/strtab-suffix-opt.s

+// RUN: llvm-mc -filetype=obj -triple i686-pc-linux-gnu %s -o - | llvm-readobj -symbols | FileCheck %s
+
+  .text
+  .globl  foobar
+  .align  16, 0x90
+  .type foobar,@function
+foobar:
+  pushl %ebp
+  movl  %esp, %ebp
+  subl  $8, %esp
+  calll foo
+  calll bar
+  addl  $8, %esp
+  popl  %ebp
+  retl
+.Ltmp3:
+  .size foobar, .Ltmp3-foobar
+
+// CHECK:     Name: foobar (1)
+// CHECK:     Name: bar (4)
+// CHECK:     Name: foo (8)

test/MC/ELF/symref.s

 // CHECK-NEXT: ]
 
 // CHECK:        Symbol {
-// CHECK:          Name: bar1@zed (19)
+// CHECK:          Name: bar1@zed (47)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar3@@zed (37)
+// CHECK-NEXT:     Name: bar3@@zed (11)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar5@@zed (47)
+// CHECK-NEXT:     Name: bar5@@zed (1)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: defined1 (1)
+// CHECK-NEXT:     Name: defined1 (73)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: defined2 (10)
+// CHECK-NEXT:     Name: defined2 (56)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Section: .bss (0x4)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: g1@@zed (74)
+// CHECK-NEXT:     Name: g1@@zed (21)
 // CHECK-NEXT:     Value: 0x14
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: global1 (66)
+// CHECK-NEXT:     Name: global1 (65)
 // CHECK-NEXT:     Value: 0x14
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar2@zed (28)
+// CHECK-NEXT:     Name: bar2@zed (38)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar6@zed (57)
+// CHECK-NEXT:     Name: bar6@zed (29)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

test/MC/ELF/tls-i386.s

         .long   fooE@INDNTPOFF
 
 // CHECK:        Symbol {
-// CHECK:          Name: foo1 (1)
+// CHECK:          Name: foo1 (88)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo2 (6)
+// CHECK-NEXT:     Name: foo2 (83)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo3 (11)
+// CHECK-NEXT:     Name: foo3 (78)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo4 (16)
+// CHECK-NEXT:     Name: foo4 (73)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo5 (21)
+// CHECK-NEXT:     Name: foo5 (68)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo6 (26)
+// CHECK-NEXT:     Name: foo6 (63)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo7 (31)
+// CHECK-NEXT:     Name: foo7 (58)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo8 (36)
+// CHECK-NEXT:     Name: foo8 (53)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo9 (41)
+// CHECK-NEXT:     Name: foo9 (48)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: fooA (46)
+// CHECK-NEXT:     Name: fooA (43)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: fooB (51)
+// CHECK-NEXT:     Name: fooB (38)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: fooC (56)
+// CHECK-NEXT:     Name: fooC (33)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: fooD (61)
+// CHECK-NEXT:     Name: fooD (28)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: fooE (66)
+// CHECK-NEXT:     Name: fooE (23)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

test/MC/ELF/tls.s

   .long 43
 
 // CHECK:        Symbol {
-// CHECK:          Name: foobar (31)
+// CHECK:          Name: foobar (1)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:   }
 
 // CHECK:        Symbol {
-// CHECK:          Name: foo1 (1)
+// CHECK:          Name: foo1 (55)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo2 (6)
+// CHECK-NEXT:     Name: foo2 (50)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo3 (11)
+// CHECK-NEXT:     Name: foo3 (45)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo4 (16)
+// CHECK-NEXT:     Name: foo4 (40)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo5 (21)
+// CHECK-NEXT:     Name: foo5 (35)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: foo6 (26)
+// CHECK-NEXT:     Name: foo6 (30)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

test/MC/ELF/type.s

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym1 (54)
+// CHECK-NEXT:    Name: sym1 (166)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

 // CHECK-NEXT:    Section: .text (0x1)
 // CHECK-NEXT:  }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym10 (162)
+// CHECK-NEXT:    Name: sym10 (193)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

 // CHECK-NEXT:    Section: .text (0x1)
 // CHECK-NEXT:  }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym11 (176)
+// CHECK-NEXT:    Name: sym11 (179)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

 // CHECK-NEXT:    Section: .text (0x1)
 // CHECK-NEXT:  }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym12 (190)
+// CHECK-NEXT:    Name: sym12 (153)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

 // CHECK-NEXT:    Section: .text (0x1)
 // CHECK-NEXT:  }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym2 (66)
+// CHECK-NEXT:    Name: sym2 (140)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

 // CHECK-NEXT:    Section: .text (0x1)
 // CHECK-NEXT:  }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym3 (78)
+// CHECK-NEXT:    Name: sym3 (128)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

 // CHECK-NEXT:    Section: .text (0x1)
 // CHECK-NEXT:  }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym4 (90)
+// CHECK-NEXT:    Name: sym4 (116)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

 // CHECK-NEXT:    Section: .text (0x1)
 // CHECK-NEXT:  }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym5 (102)
+// CHECK-NEXT:    Name: sym5 (104)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

 // CHECK-NEXT:    Section: .text (0x1)
 // CHECK-NEXT:  }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym6 (114)
+// CHECK-NEXT:    Name: sym6 (92)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

 // CHECK-NEXT:    Section: .text (0x1)
 // CHECK-NEXT:  }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym7 (126)
+// CHECK-NEXT:    Name: sym7 (80)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

 // CHECK-NEXT:    Section: .text (0x1)
 // CHECK-NEXT:  }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym8 (138)
+// CHECK-NEXT:    Name: sym8 (68)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

 // CHECK-NEXT:    Section: .text (0x1)
 // CHECK-NEXT:  }
 // CHECK-NEXT:  Symbol {
-// CHECK-NEXT:    Name: sym9 (150)
+// CHECK-NEXT:    Name: sym9 (56)
 // CHECK-NEXT:    Value: 0x0
 // CHECK-NEXT:    Size: 0
 // CHECK-NEXT:    Binding: Global (0x1)

test/MC/ELF/weakref.s

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar6 (21)
+// CHECK-NEXT:     Name: bar6 (16)
 // CHECK-NEXT:     Value: 0x18
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar7 (26)
+// CHECK-NEXT:     Name: bar7 (11)
 // CHECK-NEXT:     Value: 0x18
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar8 (31)
+// CHECK-NEXT:     Name: bar8 (6)
 // CHECK-NEXT:     Value: 0x1C
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar9 (36)
+// CHECK-NEXT:     Name: bar9 (1)
 // CHECK-NEXT:     Value: 0x20
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local

 // CHECK-NEXT:     Section: .bss (0x4)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar10 (41)
+// CHECK-NEXT:     Name: bar10 (71)
 // CHECK-NEXT:     Value: 0x28
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar11 (47)
+// CHECK-NEXT:     Name: bar11 (65)
 // CHECK-NEXT:     Value: 0x30
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar12 (53)
+// CHECK-NEXT:     Name: bar12 (59)
 // CHECK-NEXT:     Value: 0x30
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar13 (59)
+// CHECK-NEXT:     Name: bar13 (48)
 // CHECK-NEXT:     Value: 0x34
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar14 (65)
+// CHECK-NEXT:     Name: bar14 (37)
 // CHECK-NEXT:     Value: 0x38
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar15 (71)
+// CHECK-NEXT:     Name: bar15 (26)
 // CHECK-NEXT:     Value: 0x40
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: .text (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar2 (1)
+// CHECK-NEXT:     Name: bar2 (54)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar3 (6)
+// CHECK-NEXT:     Name: bar3 (43)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Weak

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar4 (11)
+// CHECK-NEXT:     Name: bar4 (32)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
-// CHECK-NEXT:     Name: bar5 (16)
+// CHECK-NEXT:     Name: bar5 (21)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global

unittests/ADT/CMakeLists.txt

   SparseSetTest.cpp
   StringMapTest.cpp
   StringRefTest.cpp
+  StringTableBuilderTest.cpp
   TinyPtrVectorTest.cpp
   TripleTest.cpp
   TwineTest.cpp

unittests/ADT/StringTableBuilderTest.cpp

+//===----------- StringTableBuilderTest.cpp -------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/ADT/StringTableBuilder.h"
+#include <string>
+
+using namespace llvm;
+
+namespace {
+
+TEST(StringTableBuilderTest, Basic) {
+  StringTableBuilder B;
+
+  B.add("foo");
+  B.add("bar");
+  B.add("foobar");
+
+  B.finalize();
+
+  std::string Expected;
+  Expected += '\x00';
+  Expected += "foobar";
+  Expected += '\x00';
+  Expected += "foo";
+  Expected += '\x00';
+
+  EXPECT_EQ(Expected, B.data());
+  EXPECT_EQ(1U, B.getOffset("foobar"));
+  EXPECT_EQ(4U, B.getOffset("bar"));
+  EXPECT_EQ(8U, B.getOffset("foo"));
+}
+
+}