[LLD][ELF] Implement --keep-unique option

[peter.smith]

Summary

The --keep-unique <symbol> option is taken from gold. The intention is that <symbol> will be prevented from being folded by ICF. Although not specifically mentioned in the documentation <symbol> only matches global symbols. In gold the option "unfolds" sections that have been folded due to ICF. For LLD I've decided to make sections defining a global symbol specified by --keep-unique inelligible for ICF.

This option is used within the Android ART runtime for jit_debug_register_code and dex_debug_register_code. Supporting it will allow ART to be linked with LLD. I think it could also be used as a basis for --icf=safe (find unsafe symbols and exclude the sections that define them).

[ruiu]

I agree that we should support this option.

ELF/ICF.cpp

422–423

I think that looking up a hash function for each input section is slow, so I'd avoid doing this. Instead, I believe you can add a KeepUnique bit to the InputSection and set that bit in the driver.

[grimar]

ELF/ICF.cpp

422–423

I think adding KeepUnique will not change the size of SectionBase, so that is probably ok.

But at the same time, I just wonder why do you think it should be slow? I do not expect to see more than ... well, 50? sections in a set. That probably should not be slow here. We could avoid adding the flag then.

test/ELF/icf-keep-unique.s

9

This contains absolute path and will fail in a different environment I think.

29

can these 3 lines be a nop?

[grimar]

ELF/ICF.cpp

427

We usually start warnings and errors from the lower case character.

[peter.smith]

Thanks very much for the comments. I've made the following changes:

• Used a bitfield for KeepUnique
• moved findKeepUniqueSections to the driver
• Simplified test case with nops, and removed absolute paths.

[ruiu]

LGTM with these changes.

ELF/Driver.cpp

1168–1169

I'd think you don't need Config->KeepUnique if you pass Args to this function. If you do that, you can directly consume --keep-unique arguments like this

for (auto *Arg : Args.filtered(OPT_keep_unique)) {
  StringRef Name = Arg->getValue();
  ...

1170–1171

nit: you could do this

if (auto *Sym = dyn_cast_or_null<Defined>(Symtab->Find(Name))

[peter.smith]

Thank you. I've made the suggested changes and committed under r332332

ELF/Driver.cpp

if (shouldDemote<ELFT>(*Sym)) {
       bool Used = Sym->Used;
       replaceSymbol<Undefined>(Sym, nullptr, Sym->getName(), Sym->Binding,
                                Sym->StOther, Sym->Type);
       Sym->Used = Used;
     }
   }
 }
 
+// Record sections that define symbols mentioned in --keep-unique <symbol>
+// these sections are inelligible for ICF.
+static void findKeepUniqueSections(opt::InputArgList &Args) {
+  for (auto *Arg : Args.filtered(OPT_keep_unique)) {
+    StringRef Name = Arg->getValue();
+    if (auto *Sym = dyn_cast_or_null<Defined>(Symtab->find(Name)))
+      Sym->Section->KeepUnique = true;
+    else
+      warn("could not find symbol " + Name + " to keep unique");
+  }
+}
+
 // Do actual linking. Note that when this function is called,
 // all linker scripts have already been parsed.
 template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   Target = getTarget();
 
   Config->MaxPageSize = getMaxPageSize(Args);
   Config->ImageBase = getImageBase(Args);
 
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
 
   // Do size optimizations: garbage collection, merging of SHF_MERGE sections
   // and identical code folding.
   decompressSections();
   splitSections<ELFT>();
   markLive<ELFT>();
   demoteSymbols<ELFT>();
   mergeSections();
-  if (Config->ICF)
+  if (Config->ICF) {
+    findKeepUniqueSections(Args);
     doIcf<ELFT>();
+  }
 
   // Read the callgraph now that we know what was gced or icfed
   if (auto *Arg = Args.getLastArg(OPT_call_graph_ordering_file))
     if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
       readCallGraph(*Buffer);
 
   // Write the result to the file.
   writeResult<ELFT>();
 }

ELF/ICF.cpp

 // Returns a hash value for S. Note that the information about
 // relocation targets is not included in the hash value.
 template <class ELFT> static uint32_t getHash(InputSection *S) {
   return hash_combine(S->Flags, S->getSize(), S->NumRelocations, S->Data);
 }
 
 // Returns true if section S is subject of ICF.
 static bool isEligible(InputSection *S) {
-  if (!S->Live || !(S->Flags & SHF_ALLOC) || (S->Flags & SHF_WRITE))
+  if (!S->Live || S->KeepUnique || !(S->Flags & SHF_ALLOC) ||
+      (S->Flags & SHF_WRITE))
     return false;
 
   // Don't merge read only data sections unless
   // --ignore-data-address-equality was passed.
   if (!(S->Flags & SHF_EXECINSTR) && !Config->IgnoreDataAddressEquality)
     return false;
 
   // Don't merge synthetic sections as their Data member is not valid and empty.
if (Config->PrintIcfSections)
     message(S);
 }
 
 // The main function of ICF.
 template <class ELFT> void ICF<ELFT>::run() {
   // Collect sections to merge.
   for (InputSectionBase *Sec : InputSections)
     if (auto *S = dyn_cast<InputSection>(Sec))
       if (isEligible(S))
         Sections.push_back(S);
 
   // Initially, we use hash values to partition sections.
   parallelForEach(Sections, [&](InputSection *S) {
     // Set MSB to 1 to avoid collisions with non-hash IDs.
     S->Class[0] = getHash<ELFT>(S) | (1 << 31);
   });
 
   // From now on, sections in Sections vector are ordered so that sections
   // in the same equivalence class are consecutive in the vector.
   std::stable_sort(Sections.begin(), Sections.end(),
                    [](InputSection *A, InputSection *B) {
                      return A->Class[0] < B->Class[0];

ELF/InputSection.h

public:
   // put them here so the struct packs better.
 
   // The garbage collector sets sections' Live bits.
   // If GC is disabled, all sections are considered live by default.
   unsigned Live : 1;
 
   unsigned Bss : 1;
 
+  // Set for sections that should not be folded by ICF.
+  unsigned KeepUnique : 1;
+
   // These corresponds to the fields in Elf_Shdr.
   uint32_t Alignment;
   uint64_t Flags;
   uint64_t Entsize;
   uint32_t Type;
   uint32_t Link;
   uint32_t Info;
 
   OutputSection *getOutputSection();
   const OutputSection *getOutputSection() const {
     return const_cast<SectionBase *>(this)->getOutputSection();
   }
 
   // Translate an offset in the input section to an offset in the output
   // section.
   uint64_t getOffset(uint64_t Offset) const;
 
   uint64_t getVA(uint64_t Offset = 0) const;
 
 protected:
   SectionBase(Kind SectionKind, StringRef Name, uint64_t Flags,
               uint64_t Entsize, uint64_t Alignment, uint32_t Type,
               uint32_t Info, uint32_t Link)
       : Name(Name), Repl(this), SectionKind(SectionKind), Live(false),
-        Bss(false), Alignment(Alignment), Flags(Flags), Entsize(Entsize),
-        Type(Type), Link(Link), Info(Info) {}
+        Bss(false), KeepUnique(false), Alignment(Alignment), Flags(Flags),
+        Entsize(Entsize), Type(Type), Link(Link), Info(Info) {}
 };
 
 // This corresponds to a section of an input file.
 class InputSectionBase : public SectionBase {
 public:
   template <class ELFT>
   InputSectionBase(ObjFile<ELFT> &File, const typename ELFT::Shdr &Header,
                    StringRef Name, Kind SectionKind);

ELF/Options.td

 
 defm image_base : Eq<"image-base">, HelpText<"Set the base address">;
 
 defm init: Eq<"init">, HelpText<"Specify an initializer function">,
   MetaVarName<"<symbol>">;
 
 defm just_symbols: Eq<"just-symbols">, HelpText<"Just link symbols">;
 
+defm keep_unique: Eq<"keep-unique">, HelpText<"Do not fold this symbol during ICF">;
+
 defm library: Eq<"library">, HelpText<"Root name of library to use">,
   MetaVarName<"<libName>">;
 
 def lto_O: J<"lto-O">, MetaVarName<"<opt-level>">,
   HelpText<"Optimization level for LTO">;
 
 def m: JoinedOrSeparate<["-"], "m">, HelpText<"Set target emulation">;
 

test/ELF/icf-keep-unique.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t2 --icf=all --print-icf-sections | FileCheck %s
+# RUN: ld.lld %t -o %t2 --keep-unique f2 --keep-unique f4 --keep-unique f5 --icf=all --print-icf-sections 2>&1 | FileCheck %s -check-prefix=CHECK-KEEP
+
+// Base case, expect only .text.f1 to be kept
+// CHECK: selected section {{.*}}:(.text.f1)
+// CHECK-NEXT:   removing identical section {{.*}}:(.text.f2)
+// CHECK-NEXT:   removing identical section {{.*}}:(.text.f3)
+// CHECK-NEXT:   removing identical section {{.*}}:(.text.f4)
+// CHECK-NEXT:   removing identical section {{.*}}:(.text.f5)
+
+// With --keep-unique f2, f4 and f5 we expect only f3 and f5 to be removed.
+// f5 is not matched by --keep-unique as it is a local symbol.
+// CHECK-KEEP: warning: could not find symbol f5 to keep unique
+// CHECK-KEEP: selected section {{.*}}:(.text.f1)
+// CHECK-KEEP-NEXT:   removing identical section {{.*}}:(.text.f3)
+// CHECK-KEEP-NEXT:   removing identical section {{.*}}:(.text.f5)
+ .globl _start, f1, f2, f3, f4
+_start:
+ ret
+
+ .section .text.f1, "ax"
+f1:
+ nop
+
+ .section .text.f2, "ax"
+f2:
+ nop
+
+.section .text.f3, "ax"
+f3:
+ nop
+
+.section .text.f4, "ax"
+f4:
+ nop
+
+# f5 is local, not found by --keep-unique f5
+.section .text.f5, "ax"
+f5:
+ nop