Add support for merging strings with alignment larger than one char.

This reduces the .rodata of scyladb from 4501932 to 4334639 bytes (1.038
times smaller).

I don't think it is critical to support tail merging, just exact
duplicates, but given the code organization it was actually a bit easier
to support both.

llvm-svn: 261327

6 files changed, 84 insertions, 24 deletions

diff --git a/lld/ELF/InputFiles.cpp b/lld/ELF/InputFiles.cpp
index b8e36290c80..d64d6b41f32 100644
--- a/lld/ELF/InputFiles.cpp
+++ b/lld/ELF/InputFiles.cpp
@@ -162,15 +162,15 @@ static bool shouldMerge(const typename ELFFile<ELFT>::Elf_Shdr &Sec) {
   if (!EntSize || Sec.sh_size % EntSize)
     fatal("SHF_MERGE section size must be a multiple of sh_entsize");
 
-  // Don't try to merge if the aligment is larger than the sh_entsize.
+  // Don't try to merge if the aligment is larger than the sh_entsize and this
+  // is not SHF_STRINGS.
   //
-  // If this is not a SHF_STRINGS, we would need to pad after every entity. It
-  // would be equivalent for the producer of the .o to just set a larger
+  // Since this is not a SHF_STRINGS, we would need to pad after every entity.
+  // It would be equivalent for the producer of the .o to just set a larger
   // sh_entsize.
-  //
-  // If this is a SHF_STRINGS, the larger alignment makes sense. Unfortunately
-  // it would complicate tail merging. This doesn't seem that common to
-  // justify the effort.
+  if (Flags & SHF_STRINGS)
+    return true;
+
   if (Sec.sh_addralign > EntSize)
     return false;
 
diff --git a/lld/ELF/OutputSections.cpp b/lld/ELF/OutputSections.cpp
index 19337fb86a8..c7fd9919091 100644
--- a/lld/ELF/OutputSections.cpp
+++ b/lld/ELF/OutputSections.cpp
@@ -1223,8 +1223,9 @@ template <class ELFT> void EHOutputSection<ELFT>::writeTo(uint8_t *Buf) {
 
 template <class ELFT>
 MergeOutputSection<ELFT>::MergeOutputSection(StringRef Name, uint32_t Type,
-                                             uintX_t Flags)
-    : OutputSectionBase<ELFT>(Name, Type, Flags) {}
+                                             uintX_t Flags, uintX_t Alignment)
+    : OutputSectionBase<ELFT>(Name, Type, Flags),
+      Builder(llvm::StringTableBuilder::RAW, Alignment) {}
 
 template <class ELFT> void MergeOutputSection<ELFT>::writeTo(uint8_t *Buf) {
   if (shouldTailMerge()) {
diff --git a/lld/ELF/OutputSections.h b/lld/ELF/OutputSections.h
index a5af47a2c2e..a3a80db42ea 100644
--- a/lld/ELF/OutputSections.h
+++ b/lld/ELF/OutputSections.h
@@ -300,14 +300,15 @@ class MergeOutputSection final : public OutputSectionBase<ELFT> {
   bool shouldTailMerge() const;
 
 public:
-  MergeOutputSection(StringRef Name, uint32_t Type, uintX_t Flags);
+  MergeOutputSection(StringRef Name, uint32_t Type, uintX_t Flags,
+                     uintX_t Alignment);
   void addSection(InputSectionBase<ELFT> *S) override;
   void writeTo(uint8_t *Buf) override;
   unsigned getOffset(StringRef Val);
   void finalize() override;
 
 private:
-  llvm::StringTableBuilder Builder{llvm::StringTableBuilder::RAW};
+  llvm::StringTableBuilder Builder;
 };
 
 // FDE or CIE
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index 3a8fa08bd74..e8fbc2ce621 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -211,7 +211,7 @@ template <bool Is64Bits> struct SectionKey {
   StringRef Name;
   uint32_t Type;
   uintX_t Flags;
-  uintX_t EntSize;
+  uintX_t Alignment;
 };
 }
 namespace llvm {
@@ -225,13 +225,13 @@ template <bool Is64Bits> struct DenseMapInfo<SectionKey<Is64Bits>> {
                                 0, 0};
   }
   static unsigned getHashValue(const SectionKey<Is64Bits> &Val) {
-    return hash_combine(Val.Name, Val.Type, Val.Flags, Val.EntSize);
+    return hash_combine(Val.Name, Val.Type, Val.Flags, Val.Alignment);
   }
   static bool isEqual(const SectionKey<Is64Bits> &LHS,
                       const SectionKey<Is64Bits> &RHS) {
     return DenseMapInfo<StringRef>::isEqual(LHS.Name, RHS.Name) &&
            LHS.Type == RHS.Type && LHS.Flags == RHS.Flags &&
-           LHS.EntSize == RHS.EntSize;
+           LHS.Alignment == RHS.Alignment;
   }
 };
 }
@@ -840,7 +840,8 @@ OutputSectionFactory<ELFT>::create(InputSectionBase<ELFT> *C,
     Sec = new EHOutputSection<ELFT>(Key.Name, Key.Type, Key.Flags);
     break;
   case InputSectionBase<ELFT>::Merge:
-    Sec = new MergeOutputSection<ELFT>(Key.Name, Key.Type, Key.Flags);
+    Sec = new MergeOutputSection<ELFT>(Key.Name, Key.Type, Key.Flags,
+                                       Key.Alignment);
     break;
   case InputSectionBase<ELFT>::MipsReginfo:
     Sec = new MipsReginfoOutputSection<ELFT>();
@@ -863,10 +864,15 @@ OutputSectionFactory<ELFT>::createKey(InputSectionBase<ELFT> *C,
   const Elf_Shdr *H = C->getSectionHdr();
   uintX_t Flags = H->sh_flags & ~SHF_GROUP;
 
-  // For SHF_MERGE we create different output sections for each sh_entsize.
-  // This makes each output section simple and keeps a single level
-  // mapping from input to output.
-  uintX_t EntSize = isa<MergeInputSection<ELFT>>(C) ? H->sh_entsize : 0;
+  // For SHF_MERGE we create different output sections for each alignment.
+  // This makes each output section simple and keeps a single level mapping from
+  // input to output.
+  uintX_t Alignment = 0;
+  if (isa<MergeInputSection<ELFT>>(C)) {
+    Alignment = H->sh_addralign;
+    if (H->sh_entsize > Alignment)
+      Alignment = H->sh_entsize;
+  }
 
   // GNU as can give .eh_frame secion type SHT_PROGBITS or SHT_X86_64_UNWIND
   // depending on the construct. We want to canonicalize it so that
@@ -876,7 +882,7 @@ OutputSectionFactory<ELFT>::createKey(InputSectionBase<ELFT> *C,
       isa<EHInputSection<ELFT>>(C))
     Type = SHT_X86_64_UNWIND;
 
-  return SectionKey<ELFT::Is64Bits>{OutsecName, Type, Flags, EntSize};
+  return SectionKey<ELFT::Is64Bits>{OutsecName, Type, Flags, Alignment};
 }
 
 // The linker is expected to define some symbols depending on
diff --git a/lld/test/ELF/merge-string-align.s b/lld/test/ELF/merge-string-align.s
index b06920ac0af..0cb1afc8ba7 100644
--- a/lld/test/ELF/merge-string-align.s
+++ b/lld/test/ELF/merge-string-align.s
@@ -1,15 +1,20 @@
 // REQUIRES: x86
 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
 // RUN: ld.lld %t.o -o %t.so -shared
-// RUN: llvm-readobj -s %t.so | FileCheck %s
+// RUN: llvm-readobj -s -section-data %t.so | FileCheck %s
 
-        .section        .rodata.str1.16,"aMS",@progbits,1
+        .section        .rodata.foo,"aMS",@progbits,1
         .align  16
         .asciz "foo"
 
-        .section        .rodata.str1.1,"aMS",@progbits,1
+        .section        .rodata.foo2,"aMS",@progbits,1
+        .align  16
         .asciz "foo"
 
+        .section        .rodata.bar,"aMS",@progbits,1
+        .align  16
+        .asciz "bar"
+
 // CHECK:      Name: .rodata
 // CHECK-NEXT: Type: SHT_PROGBITS
 // CHECK-NEXT: Flags [
@@ -19,10 +24,18 @@
 // CHECK-NEXT: ]
 // CHECK-NEXT: Address:
 // CHECK-NEXT: Offset:
-// CHECK-NEXT: Size: 4
+// CHECK-NEXT: Size: 20
 // CHECK-NEXT: Link: 0
 // CHECK-NEXT: Info: 0
 // CHECK-NEXT: AddressAlignment: 16
+// CHECK-NEXT: EntrySize:
+// CHECK-NEXT: SectionData (
+// CHECK-NEXT:   0000:  666F6F00 00000000 00000000 00000000  |foo.............|
+// CHECK-NEXT:   0010:  62617200                             |bar.|
+// CHECK-NEXT: )
+
+        .section        .rodata.str1.1,"aMS",@progbits,1
+        .asciz "foo"
 
 // CHECK:      Name: .rodata
 // CHECK-NEXT: Type: SHT_PROGBITS
@@ -37,3 +50,7 @@
 // CHECK-NEXT: Link: 0
 // CHECK-NEXT: Info: 0
 // CHECK-NEXT: AddressAlignment: 1
+// CHECK-NEXT: EntrySize:
+// CHECK-NEXT: SectionData (
+// CHECK-NEXT:   0000:  666F6F00 |foo.|
+// CHECK-NEXT: )
diff --git a/lld/test/ELF/tail-merge-string-align.s b/lld/test/ELF/tail-merge-string-align.s
new file mode 100644
index 00000000000..a5d4603b6f8
--- /dev/null
+++ b/lld/test/ELF/tail-merge-string-align.s
@@ -0,0 +1,35 @@
+// REQUIRES: x86
+// RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
+// RUN: ld.lld %t.o -o %t.so -shared -O3
+// RUN: llvm-readobj -s -section-data %t.so | FileCheck %s
+
+        .section        .rodata.4a,"aMS",@progbits,1
+        .align 4
+        .asciz "abcdef"
+
+        .section        .rodata.4b,"aMS",@progbits,1
+        .align 4
+        .asciz "ef"
+
+        .section        .rodata.4c,"aMS",@progbits,1
+        .align 4
+        .asciz "f"
+
+
+// CHECK:      Name: .rodata
+// CHECK-NEXT: Type: SHT_PROGBITS
+// CHECK-NEXT: Flags [
+// CHECK-NEXT:   SHF_ALLOC
+// CHECK-NEXT:   SHF_MERGE
+// CHECK-NEXT:   SHF_STRINGS
+// CHECK-NEXT: ]
+// CHECK-NEXT: Address:
+// CHECK-NEXT: Offset:
+// CHECK-NEXT: Size: 1
+// CHECK-NEXT: Link: 0
+// CHECK-NEXT: Info: 0
+// CHECK-NEXT: AddressAlignment: 4
+// CHECK-NEXT: EntrySize:
+// CHECK-NEXT: SectionData (
+// CHECK-NEXT:   0000:    61626364 65660000 6600               |abcdef..f.|
+// CHECK-NEXT: )