Add support for merging strings with alignment larger than one char

[• rafael]

Summary

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.

[ruiu]

LGTM

[Eugene.Zelenko]

Committed in r261327.

ELF/InputFiles.cpp

   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;
 

ELF/OutputSections.h

   bool shouldTailMerge() const;
 
 public:
-  MergeOutputSection(StringRef Name, uint32_t sh_type, uintX_t sh_flags);
+  MergeOutputSection(StringRef Name, uint32_t sh_type, uintX_t sh_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

ELF/OutputSections.cpp

 
 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()) {

ELF/Writer.cpp

   StringRef Name;
   uint32_t Type;
   uintX_t Flags;
-  uintX_t EntSize;
+  uintX_t Alignment;
 };
 }
 namespace llvm {

                                 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;
   }
 };
 }

     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>();

   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

       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

test/ELF/merge-string-align.s

 // 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 [

 // 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

 // 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: )

test/ELF/tail-merge-string-align.s

+// 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: )