[lld] Implement safe icf for MachO

[alx32]

Summary

This change implements --icf=safe for MachO based on addrsig section that is implemented in D123751.

[thakis]

Very cool!

This needs a test case.

[int3]

Re testing: you can look at https://github.com/llvm/llvm-project/blob/main/lld/test/MachO/icf.s for inspiration. I would probably create a new test file that has some address-significant functions, and check that we don't dedup them with --icf=safe while continuing to do so with --icf=all.

[int3]

lld/test/MachO/icf-safe.s

9–13 ↗

(On Diff #423491)

if you add --macho to the objdump command (i.e. llvm-objdump --macho -d) these will be rendered as bl _func0<N> instead, then it's easy to check that those values are the same / different

[int3]

lld/MachO/Driver.cpp

1510–1512

nit: can omit if braces

lld/MachO/ICF.cpp

361–365

can omit braces

370–371

hmm if I understand correctly, the failure case we are trying to avoid here is that a DSO may export two symbols a and b, and whatever loads that DSO may end up comparing the addresses of a and b for equality? If that's the case I think any exported symbol in a DSO should be marked as address-significant. But... that seems like we would end up marking a lot of symbols :/

referencedDynamically is only used to mark symbols that shouldn't be stripped (and currently only applies to __mh_execute_header, as per its block comment); but stripped symbols can still have their addresses taken if they are in the export trie.

What does LLD-ELF do here?

373

I think the _or_null isn't necessary, this should always be nonnull

380

389–390

codebase convention is to avoid auto for simple types

427

lld/MachO/ICF.h

24

symtab and config are globals in LLD; no need to pass them explicitly

lld/MachO/InputSection.h

74

would be nice to have a comment here

lld/test/MachO/icf-options.s

12 ↗

(On Diff #423660)

can just reuse DIAG-EMPTY here, no need for DIAG-SAFE

lld/test/MachO/icf-safe.s

16–18 ↗

(On Diff #423660)

nit: align

34–39 ↗

(On Diff #423660)

we usually try to create test cases that are as minimal as possible. can this just be a ret void?

104–106 ↗

(On Diff #423660)

ditto, I suppose we need noinline but can we omit the others?

[int3]

lld/MachO/ICF.cpp

370–371

we should cover this with a test too

[int3]

lgtm!

lld/MachO/ICF.h

12

could forward-declare InputFile and move this include to the .cpp

21

oops, I belatedly realized that inputFiles is a global as well, doesn't need to be passed either :D

(we could do away with the SetVector.h include in that case)

lld/test/MachO/icf-safe.s

9–11 ↗

(On Diff #423966)

FileCheck operates via substring matching by default, so there's no need for the regex

nit: also align the lines with the _callAllFunctions line above

23 ↗

(On Diff #423966)

should remove the other attributes we deleted below (or just remove the entire comment altogether)

[smeenai]

lld/MachO/InputSection.h

74

Nit: "symbol" is a bit confusing, since the flag is on a section. Perhaps something like this instead?

[smeenai]

lld/test/MachO/icf-safe.s

24 ↗

(On Diff #423966)

Nit: you can inline the attributes instead of declaring them out of line (same for everything below)

lld/MachO/Driver.cpp

     warn(Twine("unknown --icf=OPTION `") + icfLevelStr +
          "', defaulting to `none'");
     icfLevel = ICFLevel::none;
-  } else if (icfLevel == ICFLevel::safe) {
-    warn(Twine("`--icf=safe' is not yet implemented, reverting to `none'"));
-    icfLevel = ICFLevel::none;
   }
   return icfLevel;
 }

     // ICF assumes that all literals have been folded already, so we must run
     // foldIdenticalLiterals before foldIdenticalSections.
     foldIdenticalLiterals();
-    if (config->icfLevel != ICFLevel::none)
+    if (config->icfLevel != ICFLevel::none) {
+      if (config->icfLevel == ICFLevel::safe) {
+        markAddrSigSymbols(inputFiles, &*symtab, &*config);
+      }
       foldIdenticalSections();
+    }
 
     // Write to an output file.
     if (target->wordSize == 8)

lld/MachO/ICF.h

 #ifndef LLD_MACHO_ICF_H
 #define LLD_MACHO_ICF_H
 
+#include "InputFiles.h"
 #include "lld/Common/LLVM.h"
+#include "llvm/ADT/SetVector.h"
 #include <vector>
 
 namespace lld {
 namespace macho {
+struct Configuration;
+class SymbolTable;
+class Symbol;
 
+void markAddrSigSymbols(llvm::SetVector<InputFile *> &inputFiles,
+                        SymbolTable *symtab, Configuration *config);
+void markSymAsAddrSig(Symbol *s);
 void foldIdenticalSections();
 
 } // namespace macho

lld/MachO/ICF.cpp

 
 #include "ICF.h"
 #include "ConcatOutputSection.h"
+#include "Config.h"
 #include "InputSection.h"
+#include "SymbolTable.h"
 #include "Symbols.h"
 #include "UnwindInfoSection.h"
 
 #include "lld/Common/CommonLinkerContext.h"
+#include "llvm/Support/LEB128.h"
 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/xxhash.h"

   }
 }
 
+void macho::markSymAsAddrSig(Symbol *s) {
+  if (auto *d = dyn_cast_or_null<Defined>(s)) {
+    if (d->isec) {
+      d->isec->keepUnique = true;
+    }
+  }
+}
+
+void macho::markAddrSigSymbols(SetVector<InputFile *> &inputFiles,
+                               SymbolTable *symtab, Configuration *config) {
+  // Symbols in the dynsym could be address-significant in other executables
+  // or DSOs, so we conservatively mark them as address-significant.
+  for (Symbol *sym : symtab->getSymbols()) {
+    Defined *def = dyn_cast_or_null<Defined>(sym);
+    if (def && def->referencedDynamically) {
+      markSymAsAddrSig(sym);
+    }
+  }
+
+  for (InputFile *file : inputFiles) {
+    auto *obj = dyn_cast_or_null<ObjFile>(file);
+    if (!obj)
+      continue;
+
+    auto *addrSigSection = obj->addrSigSection;
+    if (!addrSigSection)
+      continue;
+    assert(addrSigSection->subsections.size() == 1);
+
+    auto *subSection = &addrSigSection->subsections[0];
+    auto &contents = subSection->isec->data;
+
+    const uint8_t *pData = contents.begin();
+    while (pData != contents.end()) {
+      unsigned size;
+      const char *err;
+      uint32_t symIndex = decodeULEB128(pData, &size, contents.end(), &err);
+      if (err)
+        fatal(toString(file) + ": could not decode addrsig section: " + err);
+      markSymAsAddrSig(obj->symbols[symIndex]);
+      pData += size;
+    }
+  }
+}
+
 void macho::foldIdenticalSections() {
   TimeTraceScope timeScope("Fold Identical Code Sections");
   // The ICF equivalence-class segregation algorithm relies on pre-computed

     // FIXME: consider non-code __text sections as hashable?
     bool isHashable = (isCodeSection(isec) || isCfStringSection(isec) ||
                        isClassRefsSection(isec)) &&
+                      (isec->keepUnique == false) &&
                       !isec->shouldOmitFromOutput() &&
                       sectionType(isec->getFlags()) == MachO::S_REGULAR;
     if (isHashable) {

lld/MachO/InputFiles.h

   const uint32_t modTime;
   std::vector<ConcatInputSection *> debugSections;
   std::vector<CallGraphEntry> callGraph;
+  Section *addrSigSection = nullptr;
 
 private:
   Section *compactUnwindSection = nullptr;

lld/MachO/InputFiles.cpp

       // spurious duplicate symbol errors, we do not parse these sections.
       // TODO: Evaluate whether the bitcode metadata is needed.
     } else {
+      if (name == section_names::addrSig)
+        addrSigSection = sections.back();
+
       auto *isec = make<ConcatInputSection>(section, data, align);
       if (isDebugSection(isec->getFlags()) &&
           isec->getSegName() == segment_names::dwarf) {

lld/MachO/InputSection.h

 public:
   // is address assigned?
   bool isFinal = false;
+  bool keepUnique = false;
   uint32_t align = 1;
 
   OutputSection *parent = nullptr;

 constexpr const char unwindInfo[] = "__unwind_info";
 constexpr const char weakBinding[] = "__weak_binding";
 constexpr const char zeroFill[] = "__zerofill";
+constexpr const char addrSig[] = "__llvm_addrsig";
 
 } // namespace section_names