[ELF] Implement --icf=safe

[MaskRay]

Summary

gold --icf=safe is used in some Android and Chrome builds.

In C++, ctors and dtors are not allowed to be taken addresses. This
property is exploited by gold --icf=safe to fold only ctors and dtors,
and functions whose addresses are not taken (by checking target-specific relocations).

Checking relocation is too hacky and we should avoid that.
This revision implements a weak version of --icf=safe by checking only ctors and dtors. It might be less effective than gold --icf=safe, but would allow Android/Chrome/... builds to pass.

[MaskRay]

CHECK-NEXT:

[MaskRay]

test

[smeenai]

See also @pcc's proposal: http://lists.llvm.org/pipermail/llvm-dev/2018-May/123514.html

[ruiu]

As you know, I also experimented the same idea to merge ctors/dtors (which I shared with you as https://reviews.llvm.org/D47034), and what I noticed was that the size reduction by this version of safe ICF is negligible. When I link Firefox with my patch, I observed only 0.16% size reduction.

I have another concern about the gold-style safe ICF. Gold's safe ICF is inherently hacky as it depends on heuristics which are not really guaranteed by any compiler or standard, and that's inherently slow because it needs to collect evidences form many places to determine whether a section seems to safe to merge or not. Since Peter now has a proposal of doing it in a better, controlled manner, I personally don't want to add the gold-style safe ICF to lld. Once we add some feature, we can't delete a feature in practice. We'll have to live with it in the foreseeable future. So eventually we'd have two safe ICFs if we add gold's ICF now. I'd like to err on the conservative side to not add a lesser one if some better one is coming.

[MaskRay]

I hadn't noticed the better proposal when I sent this one out. I'll abandon this revision

ELF/CMakeLists.txt

add_lld_library(lldELF
   Writer.cpp
 
   LINK_COMPONENTS
   ${LLVM_TARGETS_TO_BUILD}
   BinaryFormat
   BitWriter
   Core
   DebugInfoDWARF
+  Demangle
   LTO
   MC
   Object
   Option
   Support
 
   LINK_LIBS
   lldCommon
   ${LLVM_PTHREAD_LIB}
 
   DEPENDS
   ELFOptionsTableGen
   ${tablegen_deps}
   )

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 ICFPolicy { 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;
+  ICFPolicy 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;

ELF/Driver.cpp

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)
-      error("-r and --icf may not be used together");
+    if (Config->ICF != ICFPolicy::None)
+      error("-r and --icf={safe,all} 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))
     return Arg->getValue();
if (!Arg)
     return DiscardPolicy::Default;
   if (Arg->getOption().getID() == OPT_discard_all)
     return DiscardPolicy::All;
   if (Arg->getOption().getID() == OPT_discard_locals)
     return DiscardPolicy::Locals;
   return DiscardPolicy::None;
 }
 
+static ICFPolicy getICF(opt::InputArgList &Args) {
+  auto *Arg = Args.getLastArg(OPT_icf_none, OPT_icf_safe, OPT_icf_all);
+  if (!Arg)
+    return ICFPolicy::None;
+  if (Arg->getOption().getID() == OPT_icf_safe)
+    return ICFPolicy::Safe;
+  if (Arg->getOption().getID() == OPT_icf_all)
+    return ICFPolicy::All;
+  return ICFPolicy::None;
+}
+
 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 StripPolicy getStrip(opt::InputArgList &Args) {
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);
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 != ICFPolicy::None) {
     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

 #include "Config.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Writer.h"
 #include "lld/Common/Threads.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/BinaryFormat/ELF.h"
+#include "llvm/Demangle/Demangle.h"
 #include "llvm/Object/ELF.h"
 #include <algorithm>
 #include <atomic>
 
 using namespace lld;
 using namespace lld::elf;
 using namespace llvm;
 using namespace llvm::ELF;

 
 // 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) {
+static bool isEligible(llvm::ItaniumPartialDemangler *D, InputSection *S) {
   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;
if (S->Name == ".init" || S->Name == ".fini")
     return false;
 
   // A user program may enumerate sections named with a C identifier using
   // __start_* and __stop_* symbols. We cannot ICF any such sections because
   // that could change program semantics.
   if (isValidCIdentifier(S->Name))
     return false;
 
+  if (Config->ICF == ICFPolicy::Safe) {
+    size_t Pos = S->Name.rfind('.');
+    if (Pos == StringRef::npos)
+      return false;
+    StringRef Mangled = S->Name.substr(Pos+1);
+    // _ZN <nested-name>
+    // _ZZ <local-name>
+    // The prefixes are used as a prefilter.
+    if ((Mangled.startswith("_ZN") || Mangled.startswith("_ZZ")) &&
+        !D->partialDemangle(std::string(Mangled).c_str()) && D->isCtorOrDtor())
+      return true;
+
+    // Sections not associated with a ctor/dtor are non-eligible.
+    return false;
+  }
+
   return true;
 }
 
 // Split an equivalence class into smaller classes.
 template <class ELFT>
 void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
   // This loop rearranges sections in [Begin, End) so that all sections
   // that are equal in terms of equals{Constant,Variable} are contiguous

 static void print(const Twine &S) {
   if (Config->PrintIcfSections)
     message(S);
 }
 
 // The main function of ICF.
 template <class ELFT> void ICF<ELFT>::run() {
   // Collect sections to merge.
+  llvm::ItaniumPartialDemangler D;
   for (InputSectionBase *Sec : InputSections)
     if (auto *S = dyn_cast<InputSection>(Sec))
-      if (isEligible(S))
+      if (isEligible(&D, 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);
   });
 

ELF/Options.td

 
 defm hash_style: Eq<"hash-style">,
   HelpText<"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 identical code folding for ctors and dtors">;
+
 def icf_none: F<"icf=none">, HelpText<"Disable identical code folding">;
 
 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">;
 

test/ELF/driver.test

 # ERR2: -r and -shared may not be used together
 
 ## Attempt to use -r and --gc-sections together
 # RUN: not ld.lld -r --gc-sections %t -o %tfail 2>&1 | FileCheck -check-prefix=ERR3 %s
 # ERR3: -r and --gc-sections may not be used together
 
 ## Attempt to use -r and --icf together
 # RUN: not ld.lld -r --icf=all %t -o %tfail 2>&1 | FileCheck -check-prefix=ERR4 %s
-# ERR4: -r and --icf may not be used together
+# ERR4: -r and --icf={safe,all} may not be used together
 
 ## Attempt to use -r and -pie together
 # RUN: not ld.lld -r -pie %t -o %tfail 2>&1 | FileCheck -check-prefix=ERR5 %s
 # ERR5: -r and -pie may not be used together
 
 ## Attempt to use -shared and -pie together
 # RUN: not ld.lld -shared -pie %t -o %tfail 2>&1 | FileCheck -check-prefix=ERR6 %s
 # ERR6: -shared and -pie may not be used together

test/ELF/icf-safe.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t.exe --icf=safe --print-icf-sections | FileCheck %s
+# CHECK: selected section {{.*}}:(.text._ZN1AC2Ev)
+# CHECK-NEXT:   removing identical section {{.*}}:(.text._ZN1AD2Ev)
+# CHECK-NOT: removing identical section
+
+# A::A()
+.section .text._ZN1AC2Ev,"ax",@progbits
+.byte 42
+
+# A::~A()
+.section .text._ZN1AD2Ev,"ax",@progbits
+.byte 42
+
+# A::f()
+.section .text._ZN1A1fEv,"ax",@progbits
+.byte 42
+
+# f
+.section .text.f,"ax",@progbits
+.byte 42