[LLD][ELF] Remove Duplicate .ARM.exidx sections

[peter.smith]

Summary

The ARM.exidx section contains a table of 8-byte entries with the first word of each entry an offset to the function it describes and the second word instructions for unwinding if an exception is thrown from that function. The SHF_LINK_ORDER processing will order the table in ascending order of the functions described by the exception table entries. As the address range of an exception table entry is terminated by the next table entry, it is possible to merge consecutive table entries that have identical unwind instructions.

For this implementation we define a table entry to be identical if:

• Both entries are the special EXIDX_CANTUNWIND.
• Both entries have the same inline unwind instructions.

We do not attempt to establish if table entries that are references to
.ARM.extab sections are identical.

This implementation works at a granularity of a single .ARM.exidx InputSection. If all entries in the InputSection are identical to the previous table entry we can remove the InputSection. A more sophisticated but more complex implementation would rewrite InputSection contents so that duplicates within a .ARM.exidx InputSection can be merged. The implementation works really well for code compiled with -ffunction-sections and for code such as llvm that is compiled without exceptions (reduces to a single EXIDX_CANTUNWIND). For the real code I've tested it on it seems to be about half as effective as the fine grained approach, reducing the table size to approximately 70% of its original size. The fine grained approach as used by gold and bfd reduces table size to about 55% of its original value. If projects need the find grained approach I can keep working on this.

This is patch 3 of 3 in sequence:

• D40964 Move SHF_LINK_ORDER processing earlier in Writer.cpp [NFC]
• D40966 Refactor to remove loop copying all Sections in OS->finalize() [NFC]
• D40967 Remove Duplicate .ARM.exidx sections

[ruiu]

ELF/Driver.cpp

628

Can you also add -merge-exidx-entries as well and make it the primary option (i.e. add Config->MergeArmExidx instead of NoMergeArmExidx).

ELF/Writer.cpp

1166

Please mention that this is for --merge-exidx-entries and this is ARM only.

1204

nit: remove () after return.

1209

nit: you can remove {}

1248–1258

I wonder if you can use std::unique to remove consecutive duplicate list elements.

[peter.smith]

Thanks very much for the review comments. I've updated the diff to apply them. The one I haven't done yet is std::unique as I don't think I can make the predicate an equivalence relation without missing opportunities. For an example consider two consecutive (made up) unwind entries { 0xabababab, 0x1 } and { 0x1, 0x1, 0x1 }; I can merge the second into the first but not the first into the second. My guess is that the libstdc++ and libc++ implementations of std::unique will let us get away with the predicate not being symmetric but I have memories of the Visual Studio debug implementation actively checking all the preconditions required by the standard.

An alternative would be to write a version of std::unique inline, perhaps in the place of // Remove the Sections we marked as duplicate earlier. That would allow us to remove the middle chunk that sets duplicates to nullptr. Doing the unique check on the unified list does have the advantage of detecting duplicates across an InputSectionDescription boundary but I think that this wouldn't be common or significant in size. Let me know what you think?

[peter.smith]

Comments from Rafael via [llvm-commits]

+ struct ExidxEntry {
+ uint32_t Fn;
+ uint32_t Unwind;
+ };
+
+ // Get the last table Entry from the previous .ARM.exidx section.
+ const ExidxEntry PrevEntry = *reinterpret_cast<const ExidxEntry *>(
+ Prev->Data.data() + Prev->getSize() - sizeof(ExidxEntry));
+ if (IsExtabRef(PrevEntry.Unwind))
+ return false;

This is not safe in a big endian host, no?

I've updated the structure to contain ulittle32_t to match the original introduction in D25127. I'm happy to do it another way if you'd prefer.

Don't we have support for dumpling exidx in llvm-objdump? I was
surprised to not find it in Object/ELFTypes.h.

There is some support in llvm-readobj -u. Having given it a try it seems unreliable (segfaults frequently) when run on executables, and includes executables linked by .bfd and where gnu readelf -u has no problem with them. I've kept with the llvm-objdump -s for now, which also allows us to use fake .ARM.extab data that might also make llvm-readobj more prone to crash.

[peter.smith]

I think you forgot to upload th new patch.

Cheers,
Rafael

Sorry about that, I've uploaded it this time.

[peter.smith]

Thanks very much for the comments, I've applied the suggested changes.

+ RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t
+ RUN: ld.lld %t --no-merge-exidx-entries -o %t2 2>&1

Why the 2>&1 ?

No good reason, I've taken them out.

+// CHECK-NEXT: 100f4 300f0000 01000000

Is it easy to check that this is the end of the section?

I've added a CHECK-NEXT for the line afterwords (.ARM.extab section name).

Cheers,
Rafael

ELF/Config.h

struct Configuration {
   bool ExportDynamic;
   bool FixCortexA53Errata843419;
   bool GcSections;
   bool GdbIndex;
   bool GnuHash = false;
   bool HasDynamicList = false;
   bool HasDynSymTab;
   bool ICF;
+  bool MergeArmExidx;
   bool MipsN32Abi = false;
   bool NoGnuUnique;
   bool NoUndefinedVersion;
   bool NoinhibitExec;
   bool Nostdlib;
   bool OFormatBinary;
   bool Omagic;
   bool OptRemarksWithHotness;

ELF/Driver.cpp

void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   Config->ICF = Args.hasFlag(OPT_icf_all, OPT_icf_none, false);
   Config->Init = Args.getLastArgValue(OPT_init, "_init");
   Config->LTOAAPipeline = Args.getLastArgValue(OPT_lto_aa_pipeline);
   Config->LTONewPmPasses = Args.getLastArgValue(OPT_lto_newpm_passes);
   Config->LTOO = args::getInteger(Args, OPT_lto_O, 2);
   Config->LTOPartitions = args::getInteger(Args, OPT_lto_partitions, 1);
   Config->MapFile = Args.getLastArgValue(OPT_Map);
   Config->NoGnuUnique = Args.hasArg(OPT_no_gnu_unique);
+  Config->MergeArmExidx =
+      Args.hasFlag(OPT_merge_exidx_entries, OPT_no_merge_exidx_entries, true);
   Config->NoUndefinedVersion = Args.hasArg(OPT_no_undefined_version);
   Config->NoinhibitExec = Args.hasArg(OPT_noinhibit_exec);
   Config->Nostdlib = Args.hasArg(OPT_nostdlib);
   Config->OFormatBinary = isOutputFormatBinary(Args);
   Config->Omagic = Args.hasFlag(OPT_omagic, OPT_no_omagic, false);
   Config->OptRemarksFilename = Args.getLastArgValue(OPT_opt_remarks_filename);
   Config->OptRemarksWithHotness = Args.hasArg(OPT_opt_remarks_with_hotness);
   Config->Optimize = args::getInteger(Args, OPT_O, 1);

ELF/Options.td

 
 def lto_O: J<"lto-O">, MetaVarName<"<opt-level>">,
   HelpText<"Optimization level for LTO">;
 
 def m: JoinedOrSeparate<["-"], "m">, HelpText<"Set target emulation">;
 
 defm Map: Eq<"Map">, HelpText<"Print a link map to the specified file">;
 
+def merge_exidx_entries: F<"merge-exidx-entries">,
+  HelpText<"Enable merging .ARM.exidx entries">;
+
 def nostdlib: F<"nostdlib">,
   HelpText<"Only search directories specified on the command line">;
 
 def no_as_needed: F<"no-as-needed">,
   HelpText<"Always DT_NEEDED for shared libraries">;
 
 def no_color_diagnostics: F<"no-color-diagnostics">,
   HelpText<"Do not use colors in diagnostics">;
def no_gc_sections: F<"no-gc-sections">,
   HelpText<"Disable garbage collection of unused sections">;
 
 def no_gdb_index: F<"no-gdb-index">,
   HelpText<"Do not generate .gdb_index section">;
 
 def no_gnu_unique: F<"no-gnu-unique">,
   HelpText<"Disable STB_GNU_UNIQUE symbol binding">;
 
+def no_merge_exidx_entries: F<"no-merge-exidx-entries">,
+  HelpText<"Disable merging .ARM.exidx entries">;
+
 def no_threads: F<"no-threads">,
   HelpText<"Do not run the linker multi-threaded">;
 
 def no_whole_archive: F<"no-whole-archive">,
   HelpText<"Restores the default behavior of loading archive members">;
 
 def noinhibit_exec: F<"noinhibit-exec">,
   HelpText<"Retain the executable output file whenever it is still usable">;

ELF/Writer.cpp

static bool compareByFilePosition(InputSection *A, InputSection *B) {
   InputSection *LB = B->getLinkOrderDep();
   OutputSection *AOut = LA->getParent();
   OutputSection *BOut = LB->getParent();
   if (AOut != BOut)
     return AOut->SectionIndex < BOut->SectionIndex;
   return LA->OutSecOff < LB->OutSecOff;
 }
 
+// This function is used by the --merge-exidx-entries to detect duplicate
+// .ARM.exidx sections. It is Arm only.
+//
+// The .ARM.exidx section is of the form:
+// | PREL31 offset to function | Unwind instructions for function |
+// where the unwind instructions are either a small number of unwind
+// instructions inlined into the table entry, the special CANT_UNWIND value of
+// 0x1 or a PREL31 offset into a .ARM.extab Section that contains unwind
+// instructions.
+//
+// We return true if all the unwind instructions in the .ARM.exidx entries of
+// Cur can be merged into the last entry of Prev.
+static bool isDuplicateArmExidxSec(InputSection *Prev, InputSection *Cur) {
+
+  // References to .ARM.Extab Sections have bit 31 clear and are not the
+  // special EXIDX_CANTUNWIND bit-pattern.
+  auto IsExtabRef = [](uint32_t Unwind) {
+    return (Unwind & 0x80000000) == 0 && Unwind != 0x1;
+  };
+
+  struct ExidxEntry {
+    uint32_t Fn;
+    uint32_t Unwind;
+  };
+
+  // Get the last table Entry from the previous .ARM.exidx section.
+  const ExidxEntry PrevEntry = *reinterpret_cast<const ExidxEntry *>(
+      Prev->Data.data() + Prev->getSize() - sizeof(ExidxEntry));
+  if (IsExtabRef(PrevEntry.Unwind))
+    return false;
+
+  // We consider the unwind instructions of an .ARM.exidx table entry
+  // a duplicate if the previous unwind instructions if:
+  // - Both are the special EXIDX_CANTUNWIND.
+  // - Both are the same inline unwind instructions.
+  // We do not attempt to follow and check links into .ARM.extab tables as
+  // consecutive identical entries are rare and the effort to check that they
+  // are identical is high.
+
+  if (isa<SyntheticSection>(Cur))
+    // Exidx sentinel section has implicit EXIDX_CANTUNWIND;
+    return PrevEntry.Unwind == 0x1;
+
+  ArrayRef<const ExidxEntry> Entries(
+      reinterpret_cast<const ExidxEntry *>(Cur->Data.data()),
+      Cur->getSize() / sizeof(ExidxEntry));
+  for (const ExidxEntry Entry : Entries)
+    if (IsExtabRef(Entry.Unwind) || Entry.Unwind != PrevEntry.Unwind)
+      return false;
+  // All table entries in this .ARM.exidx Section can be merged into the
+  // previous Section.
+  return true;
+}
+
 template <class ELFT> void Writer<ELFT>::resolveShfLinkOrder() {
   for (OutputSection *Sec : OutputSections) {
     if (!(Sec->Flags & SHF_LINK_ORDER))
       continue;
 
     // Link order may be distributed across several InputSectionDescriptions
     // but sort must consider them all at once.
     std::vector<InputSection **> ScriptSections;
     std::vector<InputSection *> Sections;
     for (BaseCommand *Base : Sec->SectionCommands) {
       if (auto *ISD = dyn_cast<InputSectionDescription>(Base)) {
         for (InputSection *&IS : ISD->Sections) {
           ScriptSections.push_back(&IS);
           Sections.push_back(IS);
         }
       }
     }
     std::stable_sort(Sections.begin(), Sections.end(), compareByFilePosition);
+
+    bool RemoveSections = false;
+    if (Config->MergeArmExidx && !Config->Relocatable &&
+        Config->EMachine == EM_ARM && Sec->Type == SHT_ARM_EXIDX) {
+      // The EHABI for the Arm Architecture permits consecutive identical
+      // table entries to be merged. We use a simple implementation that
+      // removes a .ARM.exidx Input Section if it can be merged into the
+      // previous one. This does not require any rewriting of InputSection
+      // contents but misses opportunities for fine grained deduplication where
+      // only a subset of the InputSection contents can be merged.
+      int Cur = 1;
+      int Prev = 0;
+      int N = Sections.size();
+      while (Cur < N) {
+        if (isDuplicateArmExidxSec(Sections[Prev], Sections[Cur])) {
+          Sections[Cur] = nullptr;
+          RemoveSections = true;
+        } else
+          Prev = Cur;
+        ++Cur;
+      }
+    }
+
     for (int I = 0, N = Sections.size(); I < N; ++I)
       *ScriptSections[I] = Sections[I];
+
+    // Remove the Sections we marked as duplicate earlier.
+    if (!RemoveSections)
+      continue;
+    for (BaseCommand *Base : Sec->SectionCommands)
+      if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
+        ISD->Sections.erase(
+            std::remove(ISD->Sections.begin(), ISD->Sections.end(), nullptr),
+            ISD->Sections.end());
   }
 }
 
 static void applySynthetic(const std::vector<SyntheticSection *> &Sections,
                            std::function<void(SyntheticSection *)> Fn) {
   for (SyntheticSection *SS : Sections)
     if (SS && SS->getParent() && !SS->empty())
       Fn(SS);

test/ELF/arm-exidx-dedup.s

+// RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t
+// RUN: ld.lld %t --no-merge-exidx-entries -o %t2 2>&1
+// RUN: llvm-objdump -s %t2 | FileCheck --check-prefix CHECK-DUPS %s
+// RUN: ld.lld %t -o %t3 2>&1
+// RUN: llvm-objdump -s %t3 | FileCheck %s
+// REQUIRES: arm
+// Test that lld can at least remove duplicate .ARM.exidx sections. A more
+// fine grained implementation will be able to remove duplicate entries within
+// a .ARM.exidx section.
+
+// With duplicate entries
+// CHECK-DUPS: Contents of section .ARM.exidx:
+// CHECK-DUPS-NEXT:  100d4 2c0f0000 01000000 280f0000 01000000
+// CHECK-DUPS-NEXT:  100e4 240f0000 01000000 200f0000 01000000
+// CHECK-DUPS-NEXT:  100f4 1c0f0000 08849780 180f0000 08849780
+// CHECK-DUPS-NEXT:  10104 140f0000 08849780 100f0000 14000000
+// CHECK-DUPS-NEXT:  10114 0c0f0000 18000000 080f0000 01000000
+
+// After duplicate entry removal
+// CHECK: Contents of section .ARM.exidx:
+// CHECK-NEXT:  100d4 2c0f0000 01000000 340f0000 08849780
+// CHECK-NEXT:  100e4 380f0000 14000000 340f0000 18000000
+// CHECK-NEXT:  100f4 300f0000 01000000
+        .syntax unified
+
+        // Expect 1 EXIDX_CANTUNWIND entry.
+        .section .text.00, "ax", %progbits
+        .globl _start
+_start:
+        .fnstart
+        bx lr
+        .cantunwind
+        .fnend
+
+        // Expect .ARM.exidx.text.01 to be identical to .ARM.exidx.text.00
+        .section .text.01, "ax", %progbits
+        .globl f1
+f1:
+        .fnstart
+        bx lr
+        .cantunwind
+        .fnend
+
+        // Expect 2 EXIDX_CANTUNWIND entries, these can be duplicated into
+        // .ARM.exid.text.00
+        .section .text.02, "ax", %progbits
+        .globl f2
+f2:
+        .fnstart
+        bx lr
+        .cantunwind
+        .fnend
+
+        .globl f3
+f3:
+        .fnstart
+        bx lr
+        .cantunwind
+        .fnend
+
+        // Expect inline unwind instructions, not a duplicate of previous entry.
+        .section .text.03, "ax", %progbits
+        .global f4
+f4:
+        .fnstart
+        bx lr
+        .save {r7, lr}
+        .setfp r7, sp, #0
+        .fnend
+
+        // Expect 2 inline unwind entries that are a duplicate of
+        // .ARM.exidx.text.03
+        .section .text.04, "ax", %progbits
+        .global f5
+f5:
+        .fnstart
+        bx lr
+        .save {r7, lr}
+        .setfp r7, sp, #0
+        .fnend
+
+        .global f6
+f6:
+        .fnstart
+        bx lr
+        .save {r7, lr}
+        .setfp r7, sp, #0
+        .fnend
+
+        // Expect a section with a reference to an .ARM.extab. Not a duplicate
+        // of previous inline table entry.
+        .section .text.05, "ax",%progbits
+        .global f7
+f7:
+        .fnstart
+        bx lr
+        .personality __gxx_personality_v0
+        .handlerdata
+        .long 0
+        .fnend
+
+        // Expect a reference to an identical .ARM.extab. We do not try to
+        // deduplicate references to .ARM.extab sections.
+        .section .text.06, "ax",%progbits
+        .global f8
+f8:
+        .fnstart
+        bx lr
+        .personality __gxx_personality_v0
+        .handlerdata
+        .long 0
+        .fnend
+
+ // Dummy implementation of personality routines to satisfy reference from
+ // exception tables
+        .section .text.__gcc_personality_v0, "ax", %progbits
+        .global __gxx_personality_v0
+__gxx_personality_v0:
+        bx lr
+
+        .section .text.__aeabi_unwind_cpp_pr0, "ax", %progbits
+        .global __aeabi_unwind_cpp_pr0
+__aeabi_unwind_cpp_pr0:
+        bx lr

test/ELF/arm-exidx-gc.s

 // RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t
-// RUN: ld.lld %t -o %t2 --gc-sections 2>&1
+// RUN: ld.lld %t --no-merge-exidx-entries -o %t2 --gc-sections 2>&1
 // RUN: llvm-objdump -d -triple=armv7a-none-linux-gnueabi %t2 | FileCheck %s
 // RUN: llvm-objdump -s -triple=armv7a-none-linux-gnueabi %t2 | FileCheck -check-prefix=CHECK-EXIDX %s
 // REQUIRES: arm
 
 // Test the behavior of .ARM.exidx sections under garbage collection
 // A .ARM.exidx section is live if it has a relocation to a live executable
 // section.
 // A .ARM.exidx section may have a relocation to a .ARM.extab section, if the

test/ELF/arm-exidx-order.s

 // RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t
 // RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %S/Inputs/arm-exidx-cantunwind.s -o %tcantunwind
-// RUN: ld.lld %t %tcantunwind -o %t2 2>&1
+// RUN: ld.lld --no-merge-exidx-entries %t %tcantunwind -o %t2 2>&1
 // RUN: llvm-objdump -d -triple=armv7a-none-linux-gnueabi %t2 | FileCheck %s
 // RUN: llvm-objdump -s -triple=armv7a-none-linux-gnueabi %t2 | FileCheck -check-prefix=CHECK-EXIDX %s
 // RUN: llvm-readobj --program-headers --sections %t2 | FileCheck -check-prefix=CHECK-PT %s
 // Use Linker script to place .ARM.exidx in between .text and orphan sections
 // RUN: echo "SECTIONS { \
 // RUN:          .text 0x11000 : { *(.text*) } \
 // RUN:          .ARM.exidx : { *(.ARM.exidx) } } " > %t.script
-// RUN: ld.lld --script %t.script %tcantunwind %t -o %t3 2>&1
+// RUN: ld.lld --no-merge-exidx-entries --script %t.script %tcantunwind %t -o %t3 2>&1
 // RUN: llvm-objdump -d -triple=armv7a-none-linux-gnueabi %t3 | FileCheck -check-prefix=CHECK-SCRIPT %s
 // RUN: llvm-objdump -s -triple=armv7a-none-linux-gnueabi %t3 | FileCheck -check-prefix=CHECK-SCRIPT-EXIDX %s
 // REQUIRES: arm
 
 // Each assembler created .ARM.exidx section has the SHF_LINK_ORDER flag set
 // with the sh_link containing the section index of the executable section
 // containing the function it describes. The linker must combine the .ARM.exidx
 // InputSections in the same order that it has combined the executable section,

test/ELF/arm-exidx-sentinel-orphan.s

 // RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t
 // Use Linker script without .ARM.exidx Output Section so it is treated as
 // an orphan. We must still add the sentinel table entry
 // RUN: echo "SECTIONS { \
 // RUN:          .text 0x11000 : { *(.text*) } \
 // RUN:          } " > %t.script
-// RUN: ld.lld --script %t.script %t -o %t2
+// RUN: ld.lld --no-merge-exidx-entries --script %t.script %t -o %t2
 // RUN: llvm-objdump -s -triple=armv7a-none-linux-gnueabi %t2 | FileCheck %s
 // REQUIRES: arm
 
  .syntax unified
  .text
  .global _start
 _start:
  .fnstart
  .cantunwind
  bx lr
  .fnend
 
 // CHECK: Contents of section .ARM.exidx:
 // 11004 - 4 = 0x11000 = _start
 // 1100c - 8 = 0x11004 = _start + sizeof(_start)
 // CHECK-NEXT: 11004 fcffff7f 01000000 f8ffff7f 01000000

test/ELF/arm-static-defines.s

 // RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t
-// RUN: ld.lld %t --static -o %t2 2>&1
+// RUN: ld.lld --no-merge-exidx-entries %t --static -o %t2 2>&1
 // RUN: llvm-readobj --symbols %t2 | FileCheck %s
 // REQUIRES: arm
 
 // Check that on ARM we don't get a multiply defined symbol for __tls_get_addr
 // and undefined symbols for references to __exidx_start and __exidx_end
  .syntax unified
 .section .text
  .global __tls_get_addr