ELF: Implement --icf=safe using address-significance tables.

[pcc]

Summary

Depends on D47744

[ruiu]

Overall looking pretty good.

lld/ELF/Driver.cpp

1213

nit: can't this return type inferred?

This function doesn't depend on anything in the outer function. I'd define this as a file-scope function.

1224

Can you add a comment?

1236

toString(F) is better because it automatically include an archive file name if F is created from an archive file.

lld/ELF/ICF.cpp

175–176

Update this comment?

lld/ELF/InputFiles.cpp

434

Maybe this needs some explanation as to why objcopy could break your object files.

[pcc]

• Address review comments and fix a few problems with the test case

[peter.smith]

Thanks for the patches. Out of curiosity did you have any thoughts about how the proposal to ELF was going? https://groups.google.com/forum/#!topic/generic-abi/MPr8TVtnVn4 . In particular compressed SHT_SYMATTR seemed promising.

lld/ELF/ICF.cpp

180

If I've read this right, we merge read-only sections when ICFLevel::Safe but not when ICFLevel::All?

This seems a bit non-intuitive based on the expectation that All will be more aggressive than Safe. On the assumption that the address significance tables permit this to be done safely then would it make sense to do:

• ICFLevel = All + IgnoreDataAddressEquality = Don't use address significance tables and merge RO-data.
• ICFLevel = All = Use address significance tables for RO-data but not executable sections.
• ICFLevel = Safe = Use address significance tables for RO-data and executable sections.

lld/ELF/InputFiles.cpp

436

In the discussions on llvm-dev http://lists.llvm.org/pipermail/llvm-dev/2018-May/123514.html there was some concern that just checking for non preservation of the sh_link field wouldn't catch cases from other ELF processing tools that might preserve sh_link but not the symbol table ordering. I don't think it is necessary to get this in at first, but it may be worth making sure we can add one later without breaking existing object files. Do you have any plans for a stronger check?

lld/test/ELF/icf-safe.s

3

Some ideas for some more tests. I don't think that they are necessary for the patch but are areas that are at higher risk of getting broken by future changes:

• Include some symbols with STB_LOCAL binding.
• Include some symbols with STV_HIDDEN visibility.
• Include some symbols that would be exported into the dynamic symbol table for an executable.

[pcc]

In D48146#1132138, @peter.smith wrote:

Thanks for the patches. Out of curiosity did you have any thoughts about how the proposal to ELF was going? https://groups.google.com/forum/#!topic/generic-abi/MPr8TVtnVn4 . In particular compressed SHT_SYMATTR seemed promising.

It does seem promising indeed, and as I mentioned on the thread I think I'd be in favour of that for standardisation, but I think that we should stick with a simple representation to start with since a full implementation of SHT_SYMATTR is beneficial only if it ends up being standardised (and then used for something else), and there's still no concensus as far as I can tell on what (if anything) we're going to do in the gABI.

lld/ELF/ICF.cpp

180

If I've read this right, we merge read-only sections when ICFLevel::Safe but not when ICFLevel::All?

Correct.

This seems a bit non-intuitive based on the expectation that All will be more aggressive than Safe. On the assumption that the address significance tables permit this to be done safely then would it make sense to do: [...]

I think that's exactly what the end state should be. I was going to do that in a followup since it would involve some rethinking of how KeepUnique and the --keep-unique flag interact.

lld/ELF/InputFiles.cpp

436

It should be possible to add one later. I think your proposal was to compute a hash of the .symtab and .strtab sections, and we can avoid changing the format by storing it in sh_info.

lld/test/ELF/icf-safe.s

3

Will do.

[pcc]

• Add some more tests

[peter.smith]

Thanks very much for the update. I don't have any more comments at this stage.

[echristo]

You'll want to wait on Rui for an actual LGTM, but this looks good to me and will match the llvm support so we can try this out in more detail and see where we should move the proposals.

[ruiu]

LGTM

Please also update the man page before submitting. Thanks!

lld/ELF/Config.h

 };
 
 // For --build-id.
 enum class BuildIdKind { None, Fast, Md5, Sha1, Hexstring, Uuid };
 
 // For --discard-{all,locals,none}.
 enum class DiscardPolicy { Default, All, Locals, None };
 
+// For --icf={none,safe,all}.
+enum class ICFLevel { None, Safe, All };
+
 // For --strip-{all,debug}.
 enum class StripPolicy { None, All, Debug };
 
 // For --unresolved-symbols.
 enum class UnresolvedPolicy { ReportError, Warn, Ignore, IgnoreAll };
 
 // For --orphan-handling.
 enum class OrphanHandlingPolicy { Place, Warn, Error };
struct Configuration {
   bool ExportDynamic;
   bool FixCortexA53Errata843419;
   bool GcSections;
   bool GdbIndex;
   bool GnuHash = false;
   bool GnuUnique;
   bool HasDynamicList = false;
   bool HasDynSymTab;
-  bool ICF;
   bool IgnoreDataAddressEquality;
   bool IgnoreFunctionAddressEquality;
   bool LTODebugPassManager;
   bool LTONewPassManager;
   bool MergeArmExidx;
   bool MipsN32Abi = false;
   bool NoinhibitExec;
   bool Nostdlib;
struct Configuration {
   bool ZNow;
   bool ZOrigin;
   bool ZRelro;
   bool ZRodynamic;
   bool ZText;
   bool ZRetpolineplt;
   bool ZWxneeded;
   DiscardPolicy Discard;
+  ICFLevel ICF;
   OrphanHandlingPolicy OrphanHandling;
   SortSectionPolicy SortSection;
   StripPolicy Strip;
   UnresolvedPolicy UnresolvedSymbols;
   Target2Policy Target2;
   BuildIdKind BuildId = BuildIdKind::None;
   ELFKind EKind = ELFNoneKind;
   uint16_t DefaultSymbolVersion = llvm::ELF::VER_NDX_GLOBAL;

lld/ELF/Driver.cpp

 #include "lld/Common/TargetOptionsCommandFlags.h"
 #include "lld/Common/Threads.h"
 #include "lld/Common/Version.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compression.h"
+#include "llvm/Support/LEB128.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/TarWriter.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstdlib>
 #include <utility>
 
 using namespace llvm;
static void checkOptions(opt::InputArgList &Args) {
   if (!Config->Relocatable && !Config->DefineCommon)
     error("-no-define-common not supported in non relocatable output");
 
   if (Config->Relocatable) {
     if (Config->Shared)
       error("-r and -shared may not be used together");
     if (Config->GcSections)
       error("-r and --gc-sections may not be used together");
-    if (Config->ICF)
+    if (Config->ICF != ICFLevel::None)
       error("-r and --icf may not be used together");
     if (Config->Pie)
       error("-r and -pie may not be used together");
   }
 }
 
 static const char *getReproduceOption(opt::InputArgList &Args) {
   if (auto *Arg = Args.getLastArg(OPT_reproduce))

 
 static StringRef getDynamicLinker(opt::InputArgList &Args) {
   auto *Arg = Args.getLastArg(OPT_dynamic_linker, OPT_no_dynamic_linker);
   if (!Arg || Arg->getOption().getID() == OPT_no_dynamic_linker)
     return "";
   return Arg->getValue();
 }
 
+static ICFLevel getICF(opt::InputArgList &Args) {
+  auto *Arg = Args.getLastArg(OPT_icf_none, OPT_icf_safe, OPT_icf_all);
+  if (!Arg || Arg->getOption().getID() == OPT_icf_none)
+    return ICFLevel::None;
+  if (Arg->getOption().getID() == OPT_icf_safe)
+    return ICFLevel::Safe;
+  return ICFLevel::All;
+}
+
 static StripPolicy getStrip(opt::InputArgList &Args) {
   if (Args.hasArg(OPT_relocatable))
     return StripPolicy::None;
 
   auto *Arg = Args.getLastArg(OPT_strip_all, OPT_strip_debug);
   if (!Arg)
     return StripPolicy::None;
   if (Arg->getOption().getID() == OPT_strip_all)
void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   Config->ExportDynamic =
       Args.hasFlag(OPT_export_dynamic, OPT_no_export_dynamic, false);
   Config->FilterList = args::getStrings(Args, OPT_filter);
   Config->Fini = Args.getLastArgValue(OPT_fini, "_fini");
   Config->FixCortexA53Errata843419 = Args.hasArg(OPT_fix_cortex_a53_843419);
   Config->GcSections = Args.hasFlag(OPT_gc_sections, OPT_no_gc_sections, false);
   Config->GnuUnique = Args.hasFlag(OPT_gnu_unique, OPT_no_gnu_unique, true);
   Config->GdbIndex = Args.hasFlag(OPT_gdb_index, OPT_no_gdb_index, false);
-  Config->ICF = Args.hasFlag(OPT_icf_all, OPT_icf_none, false);
+  Config->ICF = getICF(Args);
   Config->IgnoreDataAddressEquality =
       Args.hasArg(OPT_ignore_data_address_equality);
   Config->IgnoreFunctionAddressEquality =
       Args.hasArg(OPT_ignore_function_address_equality);
   Config->Init = Args.getLastArgValue(OPT_init, "_init");
   Config->LTOAAPipeline = Args.getLastArgValue(OPT_lto_aa_pipeline);
   Config->LTODebugPassManager = Args.hasArg(OPT_lto_debug_pass_manager);
   Config->LTONewPassManager = Args.hasArg(OPT_lto_new_pass_manager);
if (shouldDemote<ELFT>(*Sym)) {
       bool Used = Sym->Used;
       replaceSymbol<Undefined>(Sym, nullptr, Sym->getName(), Sym->Binding,
                                Sym->StOther, Sym->Type);
       Sym->Used = Used;
     }
   }
 }
 
+static bool keepUnique(Symbol *S) {
+  if (auto *D = dyn_cast_or_null<Defined>(S)) {
+    if (D->Section) {
+      D->Section->KeepUnique = true;
+      return true;
+    }
+  }
+  return false;
+}
+
 // Record sections that define symbols mentioned in --keep-unique <symbol>
-// these sections are inelligible for ICF.
+// and symbols referred to by address-significance tables. These sections are
+// ineligible for ICF.
+template <class ELFT>
 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
+    if (!keepUnique(Symtab->find(Name)))
       warn("could not find symbol " + Name + " to keep unique");
   }
+
+  if (Config->ICF == ICFLevel::Safe) {
+    // Symbols in the dynsym could be address-significant in other executables
+    // or DSOs, so we conservatively mark them as address-significant.
+    for (Symbol *S : Symtab->getSymbols())
+      if (S->includeInDynsym())
+        keepUnique(S);
+
+    // Visit the address-significance table in each object file and mark each
+    // referenced symbol as address-significant.
+    for (InputFile *F : ObjectFiles) {
+      auto *Obj = cast<ObjFile<ELFT>>(F);
+      ArrayRef<Symbol *> Syms = Obj->getSymbols();
+      if (Obj->AddrsigSec) {
+        ArrayRef<uint8_t> Contents =
+            check(Obj->getObj().getSectionContents(Obj->AddrsigSec));
+        const uint8_t *Cur = Contents.begin();
+        while (Cur != Contents.end()) {
+          unsigned Size;
+          const char *Err;
+          uint64_t SymIndex = decodeULEB128(Cur, &Size, Contents.end(), &Err);
+          if (Err)
+            fatal(toString(F) + ": could not decode addrsig section: " + Err);
+          keepUnique(Syms[SymIndex]);
+          Cur += Size;
+        }
+      } else {
+        // If an object file does not have an address-significance table,
+        // conservatively mark all of its symbols as address-significant.
+        for (Symbol *S : Syms)
+          keepUnique(S);
+      }
+    }
+  }
 }
 
 // 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);
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) {
-    findKeepUniqueSections(Args);
+  if (Config->ICF != ICFLevel::None) {
+    findKeepUniqueSections<ELFT>(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>();
 }

lld/ELF/ICF.cpp

if (!S->Live || S->KeepUnique || !(S->Flags & SHF_ALLOC))
     return false;
 
   // Don't merge writable sections. .data.rel.ro sections are marked as writable
   // but are semantically read-only.
   if ((S->Flags & SHF_WRITE) && S->Name != ".data.rel.ro" &&
       !S->Name.startswith(".data.rel.ro."))
     return false;
 
   // Don't merge read only data sections unless
-  // --ignore-data-address-equality was passed.
-  if (!(S->Flags & SHF_EXECINSTR) && !Config->IgnoreDataAddressEquality)
+  // --ignore-data-address-equality or --icf=safe was passed.
+  if (!(S->Flags & SHF_EXECINSTR) &&
+      !(Config->IgnoreDataAddressEquality || Config->ICF == ICFLevel::Safe))
     return false;
 
   // Don't merge synthetic sections as their Data member is not valid and empty.
   // The Data member needs to be valid for ICF as it is used by ICF to determine
   // the equality of section contents.
   if (isa<SyntheticSection>(S))
     return false;
 
   // .init and .fini contains instructions that must be executed to initialize
   // and finalize the process. They cannot and should not be merged.

lld/ELF/InputFiles.h

public:
   // R_MIPS_GPREL16 / R_MIPS_GPREL32 relocations.
   uint32_t MipsGp0 = 0;
 
   // Name of source file obtained from STT_FILE symbol value,
   // or empty string if there is no such symbol in object file
   // symbol table.
   StringRef SourceFile;
 
+  // Pointer to this input file's .llvm_addrsig section, if it has one.
+  const Elf_Shdr *AddrsigSec = nullptr;
+
 private:
   void
   initializeSections(llvm::DenseSet<llvm::CachedHashStringRef> &ComdatGroups);
   void initializeSymbols();
   void initializeJustSymbols();
   void initializeDwarf();
   InputSectionBase *getRelocTarget(const Elf_Shdr &Sec);
   InputSectionBase *createInputSection(const Elf_Shdr &Sec);

lld/ELF/InputFiles.cpp

for (size_t I = 0, E = ObjSections.size(); I < E; I++) {
     if (this->Sections[I] == &InputSection::Discarded)
       continue;
     const Elf_Shdr &Sec = ObjSections[I];
 
     // SHF_EXCLUDE'ed sections are discarded by the linker. However,
     // if -r is given, we'll let the final link discard such sections.
     // This is compatible with GNU.
     if ((Sec.sh_flags & SHF_EXCLUDE) && !Config->Relocatable) {
+      if (Sec.sh_type == SHT_LLVM_ADDRSIG) {
+        // We ignore the address-significance table if we know that the object
+        // file was created by objcopy or ld -r. This is because these tools
+        // will reorder the symbols in the symbol table, invalidating the data
+        // in the address-significance table, which refers to symbols by index.
+        if (Sec.sh_link != 0)
+          this->AddrsigSec = &Sec;
+        else if (Config->ICF == ICFLevel::Safe)
+          warn(toString(this) + ": --icf=safe is incompatible with object "
+                                "files created using objcopy or ld -r");
+      }
       this->Sections[I] = &InputSection::Discarded;
       continue;
     }
 
     switch (Sec.sh_type) {
     case SHT_GROUP: {
       // De-duplicate section groups by their signatures.
       StringRef Signature = getShtGroupSignature(ObjSections, Sec);

lld/ELF/Options.td

defm gnu_unique: B<"gnu-unique",
   "Disable STB_GNU_UNIQUE symbol binding">;
 
 defm hash_style: Eq<"hash-style", "Specify hash style (sysv, gnu or both)">;
 
 def help: F<"help">, HelpText<"Print option help">;
 
 def icf_all: F<"icf=all">, HelpText<"Enable identical code folding">;
 
+def icf_safe: F<"icf=safe">, HelpText<"Enable safe identical code folding">;
+
 def icf_none: F<"icf=none">, HelpText<"Disable identical code folding (default)">;
 
 def ignore_function_address_equality: F<"ignore-function-address-equality">,
   HelpText<"lld can break the address equality of functions">;
 
 def ignore_data_address_equality: F<"ignore-data-address-equality">,
   HelpText<"lld can break the address equality of data">;
 

lld/test/ELF/Inputs/icf-safe.s

+.section .text.non_addrsig1,"ax",@progbits
+.globl non_addrsig1
+non_addrsig1:
+ret
+
+.section .text.non_addrsig2,"ax",@progbits
+.globl non_addrsig2
+non_addrsig2:
+ret

lld/test/ELF/icf-safe.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
+# RUN: llvm-objcopy %t1.o %t1copy.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %S/Inputs/icf-safe.s -o %t2.o
+# RUN: ld.lld %t1.o %t2.o -o %t2 --icf=safe --print-icf-sections | FileCheck %s
+# RUN: ld.lld %t1.o %t2.o -o %t3 --icf=safe --print-icf-sections -shared | FileCheck --check-prefix=EXPORT %s
+# RUN: ld.lld %t1.o %t2.o -o %t3 --icf=safe --print-icf-sections --export-dynamic | FileCheck --check-prefix=EXPORT %s
+# RUN: ld.lld %t1copy.o -o %t4 --icf=safe 2>&1 | FileCheck --check-prefix=OBJCOPY %s
+
+# CHECK-NOT: selected section {{.*}}:(.rodata.l1)
+# CHECK: selected section {{.*}}:(.rodata.l3)
+# CHECK:   removing identical section {{.*}}:(.rodata.l4)
+
+# CHECK-NOT: selected section {{.*}}:(.text.f1)
+# CHECK: selected section {{.*}}:(.text.f3)
+# CHECK:   removing identical section {{.*}}:(.text.f4)
+
+# CHECK-NOT: selected section {{.*}}:(.rodata.h1)
+# CHECK: selected section {{.*}}:(.rodata.h3)
+# CHECK:   removing identical section {{.*}}:(.rodata.h4)
+
+# CHECK-NOT: selected section {{.*}}:(.rodata.g1)
+# CHECK: selected section {{.*}}:(.rodata.g3)
+# CHECK:   removing identical section {{.*}}:(.rodata.g4)
+
+# CHECK-NOT: selected section {{.*}}:(.text.non_addrsig{{.}})
+
+# llvm-mc normally emits an empty .text section into every object file. Since
+# nothing actually refers to it via a relocation, it doesn't have any associated
+# symbols (thus nor can anything refer to it via a relocation, making it safe to
+# merge with the empty section in the other input file). Here we check that the
+# only two sections merged are the two empty sections and the sections with only
+# STB_LOCAL or STV_HIDDEN symbols. The dynsym entries should have prevented
+# anything else from being merged.
+# EXPORT-NOT: selected section
+# EXPORT: selected section {{.*}}:(.rodata.l3)
+# EXPORT:   removing identical section {{.*}}:(.rodata.l4)
+# EXPORT-NOT: selected section
+# EXPORT: selected section {{.*}}:(.rodata.h3)
+# EXPORT:   removing identical section {{.*}}:(.rodata.h4)
+# EXPORT-NOT: selected section
+# EXPORT: selected section {{.*}}:(.text)
+# EXPORT:   removing identical section {{.*}}:(.text)
+# EXPORT-NOT: selected section
+
+# OBJCOPY: --icf=safe is incompatible with object files created using objcopy or ld -r
+
+.section .text.f1,"ax",@progbits
+.globl f1
+f1:
+ret
+
+.section .text.f2,"ax",@progbits
+.globl f2
+f2:
+ret
+
+.section .text.f3,"ax",@progbits
+.globl f3
+f3:
+ud2
+
+.section .text.f4,"ax",@progbits
+.globl f4
+f4:
+ud2
+
+.section .rodata.g1,"a",@progbits
+.globl g1
+g1:
+.byte 1
+
+.section .rodata.g2,"a",@progbits
+.globl g2
+g2:
+.byte 1
+
+.section .rodata.g3,"a",@progbits
+.globl g3
+g3:
+.byte 2
+
+.section .rodata.g4,"a",@progbits
+.globl g4
+g4:
+.byte 2
+
+.section .rodata.l1,"a",@progbits
+l1:
+.byte 3
+
+.section .rodata.l2,"a",@progbits
+l2:
+.byte 3
+
+.section .rodata.l3,"a",@progbits
+l3:
+.byte 4
+
+.section .rodata.l4,"a",@progbits
+l4:
+.byte 4
+
+.section .rodata.h1,"a",@progbits
+.globl h1
+.hidden h1
+h1:
+.byte 5
+
+.section .rodata.h2,"a",@progbits
+.globl h2
+.hidden h2
+h2:
+.byte 5
+
+.section .rodata.h3,"a",@progbits
+.globl h3
+.hidden h3
+h3:
+.byte 6
+
+.section .rodata.h4,"a",@progbits
+.globl h4
+.hidden h4
+h4:
+.byte 6
+
+.addrsig
+.addrsig_sym f1
+.addrsig_sym f2
+.addrsig_sym g1
+.addrsig_sym g2
+.addrsig_sym l1
+.addrsig_sym l2
+.addrsig_sym h1
+.addrsig_sym h2