[lld-macho] Implement ICF

[gkm]

Summary

ICF = Identical C(ode|OMDAT) Folding

This is the LLD ELF/COFF algorithm, adapted for MachO. So far, only -icf all is supported. In order to support -icf safe, we will need to port address-significance tables (.addrsig directives) to MachO, which will come in later diffs.

check-{llvm,clang,lld} have 0 regressions for lld -icf all vs. baseline ld64.

We only run ICF on __TEXT,__text for reasons explained in the block comment in ConcatOutputSection.cpp.

Here is the perf impact for linking chromium_framekwork on a Mac Pro (16-core Xeon W) for the non-ICF case vs. pre-ICF:

    N           Min           Max        Median           Avg        Stddev
x  20          4.27          4.44          4.34         4.349   0.043029977
+  20          4.37          4.46         4.405        4.4115   0.025188761
Difference at 95.0% confidence
        0.0625 +/- 0.0225658
        1.43711% +/- 0.518873%
        (Student's t, pooled s = 0.0352566)

[MaskRay]

test/ELF/icf*.s have great coverage. It'd be good to ensure the cases are all covered. There is certainly a lot of labor but the return will be good.

[gkm]

• fix build break
• fix clang-tidy complaint
• remove obsolete #if 0

[gkm]

• new test cases

[gkm]

• add FIXME comments
• add log() monitoring of fold rejections
• segregate equivalence classes on a dedicated vector
• break-out Writer::foldIdenticalSections() from Writer::createOutputSections()

[gkm]

• resolved some FIXMEs, updated others
• integrated with new -dead_strip changes

[gkm]

• Resolve more FIXMEs
• Update & expand comments

[int3]

Haven't dug into the details yet, but a few high-level thoughts:

• The logging code is fairly extensive. Is it really necessary to commit it? If we are leaving it in, could we perhaps cut out InputSection::defined and symbolicate addresses by doing a linear/binary search for the matching symbol?
• Relatedly: can we have a perf benchmark between LLD-before-this-diff and LLD-with-this-diff-and-ICF-none? I'm wondering if the increased size of the InputSection will cost us.
• "Folding cannot occur across output-section boundaries, therefore ConcatOutputSection is the natural place to run ICF." -- is this not the case for ELF and COFF? Personally I would prefer keeping "core data types" like ConcatOutputSection as simple as possible, as well as to mirror the ELF/COFF ports more closely.

lld/MachO/ConcatOutputSection.cpp

379

I was hoping that __cfstring would be handled seamlessly by ICF once it's integrated with literal merging. (And I think the current implementation should be able to handle it.)

lld/MachO/InputFiles.cpp

647–655

why is this change necessary?

lld/MachO/InputSection.h

119

I roughly get why we have two entries here, but a comment explaining it would be nice

[gkm]

In D103292#2804387, @int3 wrote:

• The logging code is fairly extensive. Is it really necessary to commit it? If we are leaving it in, could we perhaps cut out InputSection::defined and symbolicate addresses by doing a linear/binary search for the matching symbol?

I can remove the logging and retain it as a patch if/when needed.

• Relatedly: can we have a perf benchmark between LLD-before-this-diff and LLD-with-this-diff-and-ICF-none? I'm wondering if the increased size of the InputSection will cost us.

Yes.

• "Folding cannot occur across output-section boundaries, therefore ConcatOutputSection is the natural place to run ICF." -- is this not the case for ELF and COFF? Personally I would prefer keeping "core data types" like ConcatOutputSection as simple as possible, as well as to mirror the ELF/COFF ports more closely.

ELF & COFF also fold only within output sections, but the segregation algorithm runs on all input sections in one batch, so output-section boundaries are enforced explicitly during segregation. Output-section boundaries need not be checked for MachO, because we have already sorted all input sections into ConcatOutputSections. Perhaps I should just remove the comment because it is a minor point and might serve only to mislead.

lld/MachO/ConcatOutputSection.cpp

379

We can experiment with ICF on only __TEXT,__text and __DATA_CONST,__cfstring.

lld/MachO/InputFiles.cpp

647–655

Not strictly necessary. I saw SEGVs when checking isec->data.data() == nullptr because parseSymbols would advance the initial nullptr for a zero-fill section at every split. The alternative is to designate data.data() as undefined for zero-fill sections.

lld/MachO/InputSection.h

119

It is likely best to refer the reader to the block comment in lld/ELF/ICF.cpp where the segregation algorithm is documented.

[int3]

Output-section boundaries need not be checked for MachO, because we have already sorted all input sections into ConcatOutputSections

Got it. Still... can we have the ICF code in a separate class / file to mirror the other ports?

[gkm]

In D103292#2804387, @int3 wrote:

Haven't dug into the details yet, but a few high-level thoughts:

• The logging code is fairly extensive. Is it really necessary to commit it? If we are leaving it in, could we perhaps cut out InputSection::defined and symbolicate addresses by doing a linear/binary search for the matching symbol?

FYI, defined is used extensively from equalsVariable() during the segregation algorithm. It is integral to the operation of ICF, regardless of logging. Removing defined in favor of reverse symbol-table lookups will severely degrade ICF performance.

[int3]

Could you point out the line where it's used in equalsVariable? I'm not sure I see it...

(I do see it being used in a non-logging sense in foldIdentical, though.)

[gkm]

In D103292#2807020, @int3 wrote:

Could you point out the line where it's used in equalsVariable? I'm not sure I see it...

Brain fart. You are correct, there is no non-logging use.

(I do see it being used in a non-logging sense in foldIdentical, though.)

Yes, that's the place it's really used. Does that use justify the .75% overhead? The alternative is making an isec-to-defined map when isec->icfEquivalenceClass & (1ull << 63) .

[gkm]

• Relocate things from ConcatOutputSection into new class ICF

[int3]

Yes, that's the place it's really used. Does that use justify the .75% overhead? The alternative is making an isec-to-defined map when isec->icfEquivalenceClass & (1ull << 63) .

Do the other LLD backends deal with a similar problem, or is this unique to us/Mach-O's format?

[int3]

lld/MachO/InputSection.cpp

114

There can be more than one symbol pointing to a given section, due to N_ALT_ENTRY. Perhaps another point in favor of having a separate isec-to-defined map...

[int3]

nit: Can we put the ICF class in its own file too?

[gkm]

This comment was removed by gkm.

[gkm]

In D103292#2808544, @int3 wrote:

Yes, that's the place it's really used. Does that use justify the .75% overhead? The alternative is making an isec-to-defined map when isec->icfEquivalenceClass & (1ull << 63) .

Do the other LLD backends deal with a similar problem, or is this unique to us/Mach-O's format?

ELF and COFF add the member InputSection *repl to their input sections. Among a collection of duplicate sections, the dead ones point to the live one. There is no getting around that. The only thing unique about MachO is that dead sections indirect through a defined symbol to reference the live section. I did this for the sake of debugging. I can remove that indirection though and make dead input sections point directly to the live input section. However, there is no away around adding that one pointer to InputSection so that the dead sections can reference the live section.

[int3]

Ah I see. Fair enough, there seems no getting around that. Having a pointer to the canonical InputSection instead of a symbol would solve the problem with N_ALT_ENTRY mentioned earlier, though

[gkm]

• move ICF code into new files ICF.h and ICF.cpp
• In InputSection, drop Defined *defined in favor of InputSection *replacement
• remove expensive ICF debug logging

[int3]

Nice work :)

lld/MachO/ConcatOutputSection.cpp

21

needs to be moved to ICF.cpp

lld/MachO/Driver.cpp

701

should we have -no_deduplicate as a synonym for -icf=none?

lld/MachO/ICF.cpp

68

nit: would it be possible to structure the code so that clang-format doesn't insert all this left-padding?

99–103

I think this doesn't work with N_ALT_ENTRY either; I think we'll need to compare Defined::value too?

108

do we need to compare gotIndex too?

181

ditto regarding N_ALT_ENTRY

231–232

can Mid ever clash with icfInvalidId?

lld/MachO/InputFiles.cpp

647–655

oh that makes sense. Could you leave a comment to that effect?

lld/MachO/InputSection.cpp

56–57

Passing textOutputSection here just for this check seems pretty awkward to me... how about adding a hasPersonality bit on InputSection that gets set directly by UnwindInfoSection? we could make InputSection::live a 1-bit value avoid taking up extra space

96

104–105

I think this should be right since all the symbol references will now be transferred away from the copy

would be good to include a test with N_ALT_ENTRY to check we get this right

lld/MachO/InputSection.h

66

looks like LLD-ELF uses 32 bits for these hashes, we might want to consider doing the same if there's a perf win (no need to sort it out in this diff though)

lld/MachO/Symbols.cpp

45

how about adding a method like InputSection::canonical() that returns the replacement as necessary?

lld/MachO/UnwindInfoSection.cpp

156

should get<InputSection *>() ever return null? If rFunc was a symbol relocation, we would have to track the corresponding InputSection it belonged to, right?

lld/MachO/UnwindInfoSection.h

33

nit: this doesn't need to be virtual, only the templated methods need to be

lld/MachO/Writer.cpp

977–978

nit: s/std::to_string/Twine/

lld/test/MachO/icf-scale.s

11

13

14

22

not the most descriptive comment :p

lld/test/MachO/icf.s

20

how about using COM:? https://llvm.org/docs/CommandGuide/FileCheck.html#the-com-directive

[int3]

lld/MachO/ICF.cpp

108

actually... since ICF doesn't fold DylibSymbols, can we not just check for pointer equality of the DylibSymbols here?

[gkm]

• revise according to review feedback
• add some TODOs to lld/test/MachO/icf.s

[gkm]

lld/MachO/Driver.cpp

701

Are you proposing that -no_deduplicate be a strict synonym for -icf=none, or that it disable all forms of deduplication, including --deduplicate_literals ?

lld/MachO/ICF.cpp

108

We already checked (ra.referent == rb.referent) above, so the isa<DylibSymbol>() block is dead code. Good catch!

231–232

[ FYI, I also did this: s/icfInvalidId/icfUniqueID/ ]

The unique IDs and hashes are all replaced with equivalence-class IDs by the first run of segregate. Although the unique ID space does overlap the equivalence-class ID space, they never coexist. Even so, for sake of debugging years ago, it might have been nice to begin the icfUniqueID space at inputSections.size(). I'll do it anyway, even though it ought have no effect.

lld/MachO/InputSection.cpp

56–57

There were already 3 bools. I rearranged slightly so that now 3+1 bools are adjacent.

I still need to reject S_REGULAR sections that are not in __TEXT,__text. I think I made it a bit less awkward by passing the isText bool rather than textOutputSection.

lld/MachO/InputSection.h

66

I wonder if truncating hashes to 32 bits was a legacy choice from the time when people still ran LLVM on 32-bit hosts. There's also space-savings of 8 bytes per InputSection to consider. I will benchmark to see if there is any benefit for modern 64-bit hosts.

lld/MachO/UnwindInfoSection.cpp

156

These are always section relocs.

[int3]

Neat! I think we still need a test for N_ALT_ENTRY, but I'm fine with having that in a follow-up (maybe just leave a TODO in icf.s).

lld/MachO/Driver.cpp

701

Good question. ld64 does literal dedup regardless of that flag, but it also runs ICF by default unless -no_deduplicate is passed. If we want to be a drop-in replacement we should match that behavior. But having only *some* optimizations run by default seems bizarre. It would probably be better to disable all optimizations by default and print out a message when -no_deduplicate is passed saying that it's now redundant. I guess we can sort that out in a future diff...

lld/MachO/InputFiles.cpp

647–655

I think you missed this one :)

lld/test/MachO/icf.s

24–26

nit: can we align the RHS of these lines?

[gkm]

• revise according to review feedback
• add -no_deduplicate option as synonym for -icf none
• handle isa<DylibSymbol> in equalsVariable()
• add test for no fold when dylib symbol references differ

[gkm]

• fix clang-tidy complaint

[thakis]

lld/MachO/Options.td

278

Is this an ld64 flag? If not: We put non-ld64-compat flags at the top and give them -- prefixes.

[int3]

lld/MachO/ICF.cpp

109

I guess we do need those extra tests :)

[gkm]

lld/MachO/ICF.cpp

109

Yow! I am having trouble writing assembler to define absolute & relocatable symbols with the same value.

lld/MachO/CMakeLists.txt

add_lld_library(lldMachO2
   Arch/ARM64Common.cpp
   Arch/ARM64_32.cpp
   Arch/X86_64.cpp
   ConcatOutputSection.cpp
   Driver.cpp
   DriverUtils.cpp
   Dwarf.cpp
   ExportTrie.cpp
+  ICF.cpp
   InputFiles.cpp
   InputSection.cpp
   LTO.cpp
   MapFile.cpp
   MarkLive.cpp
   ObjC.cpp
   OutputSection.cpp
   OutputSegment.cpp

lld/MachO/ConcatOutputSection.h

public:
   // These accessors will only be valid after finalizing the section
   uint64_t getSize() const override { return size; }
   uint64_t getFileSize() const override { return fileSize; }
 
   void addInput(ConcatInputSection *input);
   void finalize() override;
   bool needsThunks() const;
   uint64_t estimateStubsInRangeVA(size_t callIdx) const;
+  void eraseOmittedInputSections();
 
   void writeTo(uint8_t *buf) const override;
 
   std::vector<ConcatInputSection *> inputs;
   std::vector<ConcatInputSection *> thunks;
 
   static bool classof(const OutputSection *sec) {
     return sec->kind() == ConcatKind;

lld/MachO/ConcatOutputSection.cpp

 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Support/ScopedPrinter.h"
-
-#include <algorithm>
+#include "llvm/Support/TimeProfiler.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace lld;
 using namespace lld::macho;
 
 void ConcatOutputSection::addInput(ConcatInputSection *input) {
   if (inputs.empty()) {
     align = input->align;
void ConcatOutputSection::mergeFlags(InputSection *input) {
 
   // Negate pure instruction presence if any section isn't pure.
   uint32_t pureMask = ~S_ATTR_PURE_INSTRUCTIONS | (input->flags & flags);
 
   // Merge the rest
   flags |= input->flags;
   flags &= pureMask;
 }
+
+void ConcatOutputSection::eraseOmittedInputSections() {
+  // Remove the duplicates from inputs
+  inputs.erase(std::remove_if(inputs.begin(), inputs.end(),
+                              [](const ConcatInputSection *isec) -> bool {
+                                return isec->shouldOmitFromOutput();
+                              }),
+               inputs.end());
+}

lld/MachO/Config.h

 enum class UndefinedSymbolTreatment {
   unknown,
   error,
   warning,
   suppress,
   dynamic_lookup,
 };
 
+enum class ICFLevel {
+  unknown,
+  none,
+  safe,
+  all,
+};
+
 struct SectionAlign {
   llvm::StringRef segName;
   llvm::StringRef sectName;
   uint32_t align;
 };
 
 struct SegmentProtection {
   llvm::StringRef name;
struct Configuration {
   llvm::StringRef thinLTOJobs;
   bool deadStripDylibs = false;
   bool demangle = false;
   bool deadStrip = false;
   PlatformInfo platformInfo;
   NamespaceKind namespaceKind = NamespaceKind::twolevel;
   UndefinedSymbolTreatment undefinedSymbolTreatment =
       UndefinedSymbolTreatment::error;
+  ICFLevel icfLevel = ICFLevel::none;
   llvm::MachO::HeaderFileType outputType;
   std::vector<llvm::StringRef> systemLibraryRoots;
   std::vector<llvm::StringRef> librarySearchPaths;
   std::vector<llvm::StringRef> frameworkSearchPaths;
   std::vector<llvm::StringRef> runtimePaths;
   std::vector<std::string> astPaths;
   std::vector<Symbol *> explicitUndefineds;
   // There are typically few custom sectionAlignments or segmentProtections,

lld/MachO/Driver.cpp

if (treatment == UndefinedSymbolTreatment::warning)
       error("'-undefined warning' only valid with '-flat_namespace'");
     else
       error("'-undefined suppress' only valid with '-flat_namespace'");
     treatment = UndefinedSymbolTreatment::error;
   }
   return treatment;
 }
 
+static ICFLevel getICFLevel(const ArgList &args) {
+  bool noDeduplicate = args.hasArg(OPT_no_deduplicate);
+  StringRef icfLevelStr = args.getLastArgValue(OPT_icf);
+  auto icfLevel = StringSwitch<ICFLevel>(icfLevelStr)
+                      .Cases("none", "", ICFLevel::none)
+                      .Case("safe", ICFLevel::safe)
+                      .Case("all", ICFLevel::all)
+                      .Default(ICFLevel::unknown);
+  if (icfLevel == ICFLevel::unknown) {
+    warn(Twine("unknown -icf OPTION `") + icfLevelStr +
+         "', defaulting to `none'");
+    icfLevel = ICFLevel::none;
+  } else if (icfLevel != ICFLevel::none && noDeduplicate) {
+    warn(Twine("`-icf " + icfLevelStr +
+               "' conflicts with -no_deduplicate, setting 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;
+}
+
 static void warnIfDeprecatedOption(const Option &opt) {
   if (!opt.getGroup().isValid())
     return;
   if (opt.getGroup().getID() == OPT_grp_deprecated) {
     warn("Option `" + opt.getPrefixedName() + "' is deprecated in ld64:");
     warn(opt.getHelpText());
   }
 }
#endif
   if (const Arg *arg =
           args.getLastArg(OPT_flat_namespace, OPT_twolevel_namespace))
     config->namespaceKind = arg->getOption().getID() == OPT_twolevel_namespace
                                 ? NamespaceKind::twolevel
                                 : NamespaceKind::flat;
 
   config->undefinedSymbolTreatment = getUndefinedSymbolTreatment(args);
 
+  config->icfLevel = getICFLevel(args);
+
   if (config->outputType == MH_EXECUTE)
     config->entry = symtab->addUndefined(args.getLastArgValue(OPT_e, "_main"),
                                          /*file=*/nullptr,
                                          /*isWeakRef=*/false);
 
   config->librarySearchPaths =
       getLibrarySearchPaths(args, config->systemLibraryRoots);
   config->frameworkSearchPaths =

lld/MachO/ICF.h

+//===- ICF.h ----------------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_MACHO_ICF_H
+#define LLD_MACHO_ICF_H
+
+#include "lld/Common/LLVM.h"
+#include <vector>
+
+namespace lld {
+namespace macho {
+
+class ConcatInputSection;
+
+class ICF {
+public:
+  ICF(std::vector<ConcatInputSection *> &inputs);
+
+  void run();
+  void segregate(size_t begin, size_t end,
+                 std::function<bool(const ConcatInputSection *,
+                                    const ConcatInputSection *)>
+                     equals);
+  size_t findBoundary(size_t begin, size_t end);
+  void forEachClassRange(size_t begin, size_t end,
+                         std::function<void(size_t, size_t)> func);
+  void forEachClass(std::function<void(size_t, size_t)> func);
+
+  // ICF needs a copy of the inputs vector because its equivalence-class
+  // segregation algorithm destroys the proper sequence.
+  std::vector<ConcatInputSection *> icfInputs;
+};
+
+} // namespace macho
+} // namespace lld
+
+#endif

lld/MachO/ICF.cpp

+//===- ICF.cpp ------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "ICF.h"
+#include "ConcatOutputSection.h"
+#include "InputSection.h"
+#include "Symbols.h"
+#include "llvm/Support/Parallel.h"
+
+#include <atomic>
+
+using namespace llvm;
+using namespace lld;
+using namespace lld::macho;
+
+ICF::ICF(std::vector<ConcatInputSection *> &inputs) {
+  icfInputs.assign(inputs.begin(), inputs.end());
+}
+
+// ICF = Identical Code Folding
+//
+// We only fold __TEXT,__text, so this is really "code" folding, and not
+// "COMDAT" folding. String and scalar constant literals are deduplicated
+// elsewhere.
+//
+// Summary of segments & sections:
+//
+// Since folding never occurs across output-section boundaries,
+// ConcatOutputSection is the natural input for ICF.
+//
+// The __TEXT segment is readonly at the MMU. Some sections are already
+// deduplicated elsewhere (__TEXT,__cstring & __TEXT,__literal*) and some are
+// synthetic and inherently free of duplicates (__TEXT,__stubs &
+// __TEXT,__unwind_info). We only run ICF on __TEXT,__text. One might hope ICF
+// could work on __TEXT,__concat, but doing so induces many test failures.
+//
+// The __LINKEDIT segment is readonly at the MMU, yet entirely synthetic, and
+// thus ineligible for ICF.
+//
+// The __DATA_CONST segment is read/write at the MMU, but is logically const to
+// the application after dyld applies fixups to pointer data. Some sections are
+// deduplicated elsewhere (__DATA_CONST,__cfstring), and some are synthetic
+// (__DATA_CONST,__got). There are no ICF opportunities here.
+//
+// The __DATA segment is read/write at the MMU, and as application-writeable
+// data, none of its sections are eligible for ICF.
+//
+// Please see the large block comment in lld/ELF/ICF.cpp for an explanation
+// of the segregation algorithm.
+//
+// FIXME(gkm): implement keep-unique attributes
+// FIXME(gkm): implement address-significance tables for MachO object files
+
+static unsigned icfPass = 0;
+static std::atomic<bool> icfRepeat{false};
+
+// Compare everything except the relocation referents
+static bool equalsConstant(const ConcatInputSection *ia,
+                           const ConcatInputSection *ib) {
+  if (ia->data.size() != ib->data.size())
+    return false;
+  if (ia->data != ib->data)
+    return false;
+  if (ia->flags != ib->flags)
+    return false;
+  if (ia->relocs.size() != ib->relocs.size())
+    return false;
+  auto f = [&](const Reloc &ra, const Reloc &rb) {
+    if (ra.type != rb.type)
+      return false;
+    if (ra.pcrel != rb.pcrel)
+      return false;
+    if (ra.length != rb.length)
+      return false;
+    if (ra.offset != rb.offset)
+      return false;
+    if (ra.addend != rb.addend)
+      return false;
+    if (ra.referent.is<Symbol *>() != rb.referent.is<Symbol *>())
+      return false; // a nice place to breakpoint
+    return true;
+  };
+  return std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(),
+                    f);
+}
+
+// Compare only the relocation referents
+static bool equalsVariable(const ConcatInputSection *ia,
+                           const ConcatInputSection *ib) {
+  assert(ia->relocs.size() == ib->relocs.size());
+  auto f = [&](const Reloc &ra, const Reloc &rb) {
+    if (ra.referent == rb.referent)
+      return true;
+    if (ra.referent.is<Symbol *>()) {
+      const auto *sa = ra.referent.get<Symbol *>();
+      const auto *sb = rb.referent.get<Symbol *>();
+      if (sa->kind() != sb->kind())
+        return false;
+      if (isa<Defined>(sa)) {
+        const auto *da = dyn_cast<Defined>(sa);
+        const auto *db = dyn_cast<Defined>(sb);
+        if (da->value != db->value)
+          return false;
+        if (da->isAbsolute() != da->isAbsolute())
+          return false;
+        if (da->isec)
+          if (da->isec->icfEqClass[icfPass % 2] !=
+              db->isec->icfEqClass[icfPass % 2])
+            return false;
+      } else if (isa<DylibSymbol>(sa)) {
+        // There is one DylibSymbol per gotIndex and we already checked for
+        // symbol equality, thus we know that these must be different.
+        return false;
+      } else {
+        llvm_unreachable("equalsVariable symbol kind");
+      }
+    } else {
+      const auto *sa = ra.referent.get<InputSection *>();
+      const auto *sb = rb.referent.get<InputSection *>();
+      if (sa->icfEqClass[icfPass % 2] != sb->icfEqClass[icfPass % 2])
+        return false;
+    }
+    return true;
+  };
+  return std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(),
+                    f);
+}
+
+// Find the first InputSection after BEGIN whose equivalence class differs
+size_t ICF::findBoundary(size_t begin, size_t end) {
+  uint64_t beginHash = icfInputs[begin]->icfEqClass[icfPass % 2];
+  for (size_t i = begin + 1; i < end; ++i)
+    if (beginHash != icfInputs[i]->icfEqClass[icfPass % 2])
+      return i;
+  return end;
+}
+
+// Invoke FUNC on subranges with matching equivalence class
+void ICF::forEachClassRange(size_t begin, size_t end,
+                            std::function<void(size_t, size_t)> func) {
+  while (begin < end) {
+    size_t mid = findBoundary(begin, end);
+    func(begin, mid);
+    begin = mid;
+  }
+}
+
+// Split icfInputs into shards, then parallelize invocation of FUNC on subranges
+// with matching equivalence class
+void ICF::forEachClass(std::function<void(size_t, size_t)> func) {
+  // Only use threads when the benefits outweigh the overhead.
+  const size_t threadingThreshold = 1024;
+  if (icfInputs.size() < threadingThreshold) {
+    forEachClassRange(0, icfInputs.size(), func);
+    ++icfPass;
+    return;
+  }
+
+  // Shard into non-overlapping intervals, and call FUNC in parallel.  The
+  // sharding must be completed before any calls to FUNC are made so that FUNC
+  // can modify the InputSection in its shard without causing data races.
+  const size_t shards = 256;
+  size_t step = icfInputs.size() / shards;
+  size_t boundaries[shards + 1];
+  boundaries[0] = 0;
+  boundaries[shards] = icfInputs.size();
+  parallelForEachN(1, shards, [&](size_t i) {
+    boundaries[i] = findBoundary((i - 1) * step, icfInputs.size());
+  });
+  parallelForEachN(1, shards + 1, [&](size_t i) {
+    if (boundaries[i - 1] < boundaries[i]) {
+      forEachClassRange(boundaries[i - 1], boundaries[i], func);
+    }
+  });
+  ++icfPass;
+}
+
+void ICF::run() {
+  // Into each origin-section hash, combine all reloc referent section hashes.
+  for (icfPass = 0; icfPass < 2; ++icfPass) {
+    parallelForEach(icfInputs, [&](InputSection *isec) {
+      uint64_t hash = isec->icfEqClass[icfPass % 2];
+      for (const Reloc &r : isec->relocs) {
+        if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
+          if (auto *dylibSym = dyn_cast<DylibSymbol>(sym))
+            hash += dylibSym->stubsHelperIndex;
+          else if (auto *defined = dyn_cast<Defined>(sym))
+            hash +=
+                defined->value +
+                (defined->isec ? defined->isec->icfEqClass[icfPass % 2] : 0);
+          else
+            llvm_unreachable("foldIdenticalSections symbol kind");
+        }
+      }
+      // Set MSB to 1 to avoid collisions with non-hashed classes.
+      isec->icfEqClass[(icfPass + 1) % 2] = hash | (1ull << 63);
+    });
+  }
+
+  llvm::stable_sort(icfInputs,
+                    [](const InputSection *a, const InputSection *b) {
+                      return a->icfEqClass[0] < b->icfEqClass[0];
+                    });
+  forEachClass(
+      [&](size_t begin, size_t end) { segregate(begin, end, equalsConstant); });
+
+  // Split equivalence groups by comparing relocations until convergence
+  do {
+    icfRepeat = false;
+    forEachClass([&](size_t begin, size_t end) {
+      segregate(begin, end, equalsVariable);
+    });
+  } while (icfRepeat);
+  log("ICF needed " + Twine(icfPass) + " iterations");
+
+  // Fold sections within equivalence classes
+  forEachClass([&](size_t begin, size_t end) {
+    if (end - begin < 2)
+      return;
+    ConcatInputSection *beginIsec = icfInputs[begin];
+    for (size_t i = begin + 1; i < end; ++i)
+      beginIsec->foldIdentical(icfInputs[i]);
+  });
+}
+
+// Split an equivalence class into smaller classes.
+void ICF::segregate(
+    size_t begin, size_t end,
+    std::function<bool(const ConcatInputSection *, const ConcatInputSection *)>
+        equals) {
+  while (begin < end) {
+    // Divide [begin, end) into two. Let mid be the start index of the
+    // second group.
+    auto bound = std::stable_partition(icfInputs.begin() + begin + 1,
+                                       icfInputs.begin() + end,
+                                       [&](ConcatInputSection *isec) {
+                                         return equals(icfInputs[begin], isec);
+                                       });
+    size_t mid = bound - icfInputs.begin();
+
+    // Split [begin, end) into [begin, mid) and [mid, end). We use mid as an
+    // equivalence class ID because every group ends with a unique index.
+    for (size_t i = begin; i < mid; ++i)
+      icfInputs[i]->icfEqClass[(icfPass + 1) % 2] = mid;
+
+    // If we created a group, we need to iterate the main loop again.
+    if (mid != end)
+      icfRepeat = true;
+
+    begin = mid;
+  }
+}

lld/MachO/InputFiles.cpp

for (size_t j = 0; j < symbolIndices.size(); ++j) {
           sym.n_desc & N_ALT_ENTRY || !isa<ConcatInputSection>(isec)) {
         symbols[symIndex] =
             createDefined(sym, name, isec, symbolOffset, symbolSize);
         continue;
       }
       auto *concatIsec = cast<ConcatInputSection>(isec);
 
       auto *nextIsec = make<ConcatInputSection>(*concatIsec);
-      nextIsec->data = isec->data.slice(symbolOffset);
       nextIsec->numRefs = 0;
       nextIsec->wasCoalesced = false;
+      if (isZeroFill(isec->flags)) {
+        // Zero-fill sections have NULL data.data() non-zero data.size()
+        nextIsec->data = {nullptr, isec->data.size() - symbolOffset};
+        isec->data = {nullptr, symbolOffset};
+      } else {
+        nextIsec->data = isec->data.slice(symbolOffset);
         isec->data = isec->data.slice(0, symbolOffset);
+      }
 
       // By construction, the symbol will be at offset zero in the new
       // subsection.
       symbols[symIndex] =
           createDefined(sym, name, nextIsec, /*value=*/0, symbolSize);
       // TODO: ld64 appears to preserve the original alignment as well as each
       // subsection's offset from the last aligned address. We should consider
       // emulating that behavior.
       nextIsec->align = MinAlign(sectionAlign, sym.n_value);

lld/MachO/InputSection.h

 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/BinaryFormat/MachO.h"
 
 namespace lld {
 namespace macho {
 
 class InputFile;
 class OutputSection;
+class Defined;
 
 class InputSection {
 public:
   enum Kind {
     ConcatKind,
     CStringLiteralKind,
     WordLiteralKind,
   };
public:
   StringRef name;
   StringRef segname;
 
   OutputSection *parent = nullptr;
 
   uint32_t align = 1;
   uint32_t flags = 0;
   uint32_t callSiteCount = 0;
-  bool isFinal = false; // is address assigned?
 
+  // is address assigned?
+  bool isFinal = false;
+
+  bool isHashableForICF(bool isText) const;
+  void hashForICF();
+  InputSection *canonical() { return replacement ? replacement : this; }
+
+  // ICF can't fold functions with LSDA+personality
+  bool hasPersonality = false;
+  // Points to the surviving section after this one is folded by ICF
+  InputSection *replacement = nullptr;
+  // Equivalence-class ID for ICF
+  uint64_t icfEqClass[2] = {0, 0};
 
   ArrayRef<uint8_t> data;
   std::vector<Reloc> relocs;
 
 protected:
   InputSection(Kind kind, StringRef segname, StringRef name)
       : name(name), segname(segname), sectionKind(kind) {}
 
public:
   bool isCoalescedWeak() const { return wasCoalesced && numRefs == 0; }
   bool shouldOmitFromOutput() const { return !live || isCoalescedWeak(); }
   void writeTo(uint8_t *buf);
 
   static bool classof(const InputSection *isec) {
     return isec->kind() == ConcatKind;
   }
 
+  void foldIdentical(ConcatInputSection *redundant);
+
   // With subsections_via_symbols, most symbols have their own InputSection,
   // and for weak symbols (e.g. from inline functions), only the
   // InputSection from one translation unit will make it to the output,
   // while all copies in other translation units are coalesced into the
   // first and not copied to the output.
   bool wasCoalesced = false;
   bool live = !config->deadStrip;
   // How many symbols refer to this InputSection.
   uint32_t numRefs = 0;
   uint64_t outSecOff = 0;
 };
 

lld/MachO/InputSection.cpp

 //===- InputSection.cpp ---------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputSection.h"
 #include "InputFiles.h"
 #include "OutputSegment.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
+#include "UnwindInfoSection.h"
 #include "Writer.h"
 #include "lld/Common/Memory.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/xxhash.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::support;
if (relocAttrs.hasAttr(RelocAttrBits::BRANCH))
     return sym->resolveBranchVA();
   else if (relocAttrs.hasAttr(RelocAttrBits::GOT))
     return sym->resolveGotVA();
   else if (relocAttrs.hasAttr(RelocAttrBits::TLV))
     return sym->resolveTlvVA();
   return sym->getVA();
 }
 
+// ICF needs to hash any section that might potentially be duplicated so
+// that it can match on content rather than identity.
+bool InputSection::isHashableForICF(bool isText) const {
+  if (auto const *concatIsec = dyn_cast<ConcatInputSection>(this))
+    if (concatIsec->shouldOmitFromOutput())
+      return false;
+  switch (sectionType(flags)) {
+  case S_REGULAR:
+    if (isText)
+      return !hasPersonality;
+    // One might hope that we could hash __TEXT,__const subsections to fold
+    // references to duplicated values, but alas, many tests fail.
+    return false;
+  case S_CSTRING_LITERALS:
+  case S_4BYTE_LITERALS:
+  case S_8BYTE_LITERALS:
+  case S_16BYTE_LITERALS:
+  case S_LITERAL_POINTERS:
+    // FIXME(gkm): once literal sections are deduplicated, their content and
+    // identity correlate, so we can assign unique IDs to them rather than hash
+    // them.
+    return true;
+  case S_ZEROFILL:
+  case S_GB_ZEROFILL:
+  case S_NON_LAZY_SYMBOL_POINTERS:
+  case S_LAZY_SYMBOL_POINTERS:
+  case S_SYMBOL_STUBS:
+  case S_MOD_INIT_FUNC_POINTERS:
+  case S_MOD_TERM_FUNC_POINTERS:
+  case S_COALESCED:
+  case S_INTERPOSING:
+  case S_DTRACE_DOF:
+  case S_LAZY_DYLIB_SYMBOL_POINTERS:
+  case S_THREAD_LOCAL_REGULAR:
+  case S_THREAD_LOCAL_ZEROFILL:
+  case S_THREAD_LOCAL_VARIABLES:
+  case S_THREAD_LOCAL_VARIABLE_POINTERS:
+  case S_THREAD_LOCAL_INIT_FUNCTION_POINTERS:
+    return false;
+  default:
+    llvm_unreachable("Section type");
+  }
+}
+
+void InputSection::hashForICF() {
+  assert(data.data()); // zeroFill section data has nullptr with non-zero size
+  assert(icfEqClass[0] == 0); // don't overwrite a unique ID!
+  // Turn-on the top bit to guarantee that valid hashes have no collisions
+  // with the small-integer unique IDs for ICF-ineligible sections
+  icfEqClass[0] = xxHash64(data) | (1ull << 63);
+}
+
+void ConcatInputSection::foldIdentical(ConcatInputSection *copy) {
+  align = std::max(align, copy->align);
+  copy->live = false;
+  copy->wasCoalesced = true;
+  numRefs += copy->numRefs;
+  copy->numRefs = 0;
+  copy->replacement = this;
+}
+
 void ConcatInputSection::writeTo(uint8_t *buf) {
   assert(!shouldOmitFromOutput());
 
   if (getFileSize() == 0)
     return;
 
   memcpy(buf, data.data(), data.size());
 
   for (size_t i = 0; i < relocs.size(); i++) {
     const Reloc &r = relocs[i];
     uint8_t *loc = buf + r.offset;
     uint64_t referentVA = 0;
     if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
       const Symbol *fromSym = r.referent.get<Symbol *>();

lld/MachO/Options.td

 def merge_zero_fill_sections : Flag<["-"], "merge_zero_fill_sections">,
     HelpText<"Merge all zeroed data into the __zerofill section">,
     Flags<[HelpHidden]>,
     Group<grp_opts>;
 def no_branch_islands : Flag<["-"], "no_branch_islands">,
     HelpText<"Disable infra for branches beyond the maximum branch distance.">,
     Flags<[HelpHidden]>,
     Group<grp_opts>;
+def icf: Separate<["-"], "icf">,
+    HelpText<"Set level for identical code folding (default: none)">,
+    MetaVarName<"[none,safe,all]">,
+    Group<grp_opts>;
+def no_deduplicate : Flag<["-"], "no_deduplicate">,
+    HelpText<"Disable code deduplicaiton (synonym for `-icf none')">,
+    Group<grp_opts>;
 
 def grp_version : OptionGroup<"version">, HelpText<"VERSION TARGETING">;
 
 def platform_version : MultiArg<["-"], "platform_version", 3>,
     MetaVarName<"<platform> <min_version> <sdk_version>">,
     HelpText<"Platform (e.g., macos, ios, tvos, watchos, bridgeos, mac-catalyst, ios-sim, tvos-sim, watchos-sim, driverkit) and version numbers">,
     Group<grp_version>;
 def sdk_version : Separate<["-"], "sdk_version">,

 def version_details : Flag<["-"], "version_details">,
     HelpText<"Print the linker version in JSON form">,
     Flags<[HelpHidden]>,
     Group<grp_rare>;
 def no_weak_imports : Flag<["-"], "no_weak_imports">,
     HelpText<"Fail if any symbols are weak imports, allowed to be NULL at runtime">,
     Flags<[HelpHidden]>,
     Group<grp_rare>;
-def no_deduplicate : Flag<["-"], "no_deduplicate">,
-    HelpText<"Omit the deduplication pass">,
-    Flags<[HelpHidden]>,
-    Group<grp_rare>;
 def verbose_deduplicate : Flag<["-"], "verbose_deduplicate">,
     HelpText<"Print function names eliminated by deduplication and the total size of code savings">,
     Flags<[HelpHidden]>,
     Group<grp_rare>;
 def no_inits : Flag<["-"], "no_inits">,
     HelpText<"Fail if the output contains static initializers">,
     Flags<[HelpHidden]>,
     Group<grp_rare>;

lld/MachO/Symbols.cpp

bool Symbol::isLive() const {
   if (isa<DylibSymbol>(this) || isa<Undefined>(this))
     return used;
 
   if (auto *d = dyn_cast<Defined>(this)) {
     // Non-absolute symbols might be alive because their section is
     // no_dead_strip or live_support. In that case, the section will know
     // that it's live but `used` might be false. Non-absolute symbols always
     // have to use the section's `live` bit as source of truth.
-    return d->isAbsolute() ? used : d->isec->isLive(d->value);
+    if (d->isAbsolute())
+      return used;
+    return d->isec->canonical()->isLive(d->value);
   }
 
   assert(!isa<CommonSymbol>(this) &&
          "replaceCommonSymbols() runs before dead code stripping, and isLive() "
          "should only be called after dead code stripping");
 
   // Assume any other kind of symbol is live.
   return true;
 }
 
 uint64_t Defined::getVA() const {
   assert(isLive() && "this should only be called for live symbols");
 
   if (isAbsolute())
     return value;
 
-  if (!isec->isFinal) {
+  if (!isec->canonical()->isFinal) {
     // A target arch that does not use thunks ought never ask for
     // the address of a function that has not yet been finalized.
     assert(target->usesThunks());
 
     // ConcatOutputSection::finalize() can seek the address of a
     // function before its address is assigned. The thunking algorithm
     // knows that unfinalized functions will be out of range, so it is
     // expedient to return a contrived out-of-range address.
     return TargetInfo::outOfRangeVA;
   }
-  return isec->getVA(value);
+  return isec->canonical()->getVA(value);
 }
 
 uint64_t DylibSymbol::getVA() const {
   return isInStubs() ? getStubVA() : Symbol::getVA();
 }
 
 void LazySymbol::fetchArchiveMember() { getFile()->fetch(sym); }

lld/MachO/SyntheticSections.cpp

 
 void FunctionStartsSection::finalizeContents() {
   raw_svector_ostream os{contents};
   std::vector<uint64_t> addrs;
   for (const Symbol *sym : symtab->getSymbols()) {
     if (const auto *defined = dyn_cast<Defined>(sym)) {
       if (!defined->isec || !isCodeSection(defined->isec) || !defined->isLive())
         continue;
+      if (const auto *concatIsec = dyn_cast<ConcatInputSection>(defined->isec))
+        if (concatIsec->shouldOmitFromOutput())
+          continue;
       // TODO: Add support for thumbs, in that case
       // the lowest bit of nextAddr needs to be set to 1.
       addrs.push_back(defined->getVA());
     }
   }
   llvm::sort(addrs);
   uint64_t addr = in.header->addr;
   for (uint64_t nextAddr : addrs) {

lld/MachO/UnwindInfoSection.h

 //===- UnwindInfoSection.h ------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_UNWIND_INFO_H
 #define LLD_MACHO_UNWIND_INFO_H
 
 #include "ConcatOutputSection.h"
 #include "SyntheticSections.h"
 
 #include "mach-o/compact_unwind_encoding.h"
-#include "llvm/ADT/DenseMap.h"
-
-#include <vector>
 
 namespace lld {
 namespace macho {
 
 template <class Ptr> struct CompactUnwindEntry {
   Ptr functionAddress;
   uint32_t functionLength;
   compact_unwind_encoding_t encoding;
   Ptr personality;
   Ptr lsda;
 };
 
 class UnwindInfoSection : public SyntheticSection {
 public:
   bool isNeeded() const override { return compactUnwindSection != nullptr; }
   uint64_t getSize() const override { return unwindInfoSize; }
   virtual void prepareRelocations(ConcatInputSection *) = 0;
 
   void setCompactUnwindSection(ConcatOutputSection *cuSection) {
     compactUnwindSection = cuSection;
   }
 
 protected:
   UnwindInfoSection()
       : SyntheticSection(segment_names::text, section_names::unwindInfo) {
     align = 4;

lld/MachO/UnwindInfoSection.cpp

void UnwindInfoSectionImpl<Ptr>::prepareRelocations(ConcatInputSection *isec) {
   assert(!isec->shouldOmitFromOutput() &&
          "__compact_unwind section should not be omitted");
 
   // FIXME: Make this skip relocations for CompactUnwindEntries that
   // point to dead-stripped functions. That might save some amount of
   // work. But since there are usually just few personality functions
   // that are referenced from many places, at least some of them likely
   // live, it wouldn't reduce number of got entries.
-  for (Reloc &r : isec->relocs) {
+  for (size_t i = 0; i < isec->relocs.size(); ++i) {
+    Reloc &r = isec->relocs[i];
     assert(target->hasAttr(r.type, RelocAttrBits::UNSIGNED));
     if (r.offset % sizeof(CompactUnwindEntry<Ptr>) !=
         offsetof(CompactUnwindEntry<Ptr>, personality))
       continue;
 
+    Reloc &rFunc = isec->relocs[++i];
+    assert(r.offset ==
+           rFunc.offset + offsetof(CompactUnwindEntry<Ptr>, personality));
+    rFunc.referent.get<InputSection *>()->hasPersonality = true;
+
     if (auto *s = r.referent.dyn_cast<Symbol *>()) {
       if (auto *undefined = dyn_cast<Undefined>(s)) {
         treatUndefinedSymbol(*undefined);
         // treatUndefinedSymbol() can replace s with a DylibSymbol; re-check.
         if (isa<Undefined>(s))
           continue;
       }
       if (auto *defined = dyn_cast<Defined>(s)) {

lld/MachO/Writer.cpp

 //===- Writer.cpp ---------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "Writer.h"
 #include "ConcatOutputSection.h"
 #include "Config.h"
+#include "ICF.h"
 #include "InputFiles.h"
 #include "InputSection.h"
 #include "MapFile.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"

 class Writer {
 public:
   Writer() : buffer(errorHandler().outputBuffer) {}
 
   void scanRelocations();
   void scanSymbols();
   template <class LP> void createOutputSections();
   template <class LP> void createLoadCommands();
+  void foldIdenticalSections();
   void finalizeAddresses();
   void finalizeLinkEditSegment();
   void assignAddresses(OutputSegment *);
 
   void openFile();
   void writeSections();
   void writeUuid();
   void writeCodeSignature();
public:
   SymtabSection *symtabSection = nullptr;
   IndirectSymtabSection *indirectSymtabSection = nullptr;
   CodeSignatureSection *codeSignatureSection = nullptr;
   DataInCodeSection *dataInCodeSection = nullptr;
   FunctionStartsSection *functionStartsSection = nullptr;
 
   LCUuid *uuidCommand = nullptr;
   OutputSegment *linkEditSegment = nullptr;
+  DenseMap<NamePair, ConcatOutputSection *> concatOutputSections;
 };
 
 // LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
 class LCDyldInfo final : public LoadCommand {
 public:
   LCDyldInfo(RebaseSection *rebaseSection, BindingSection *bindingSection,
              WeakBindingSection *weakBindingSection,
              LazyBindingSection *lazyBindingSection,
template <class LP> void Writer::createOutputSections() {
   case MH_DYLIB:
   case MH_BUNDLE:
     break;
   default:
     llvm_unreachable("unhandled output file type");
   }
 
   // Then add input sections to output sections.
-  DenseMap<NamePair, ConcatOutputSection *> concatOutputSections;
   for (const auto &p : enumerate(inputSections)) {
     InputSection *isec = p.value();
     OutputSection *osec;
     if (auto *concatIsec = dyn_cast<ConcatInputSection>(isec)) {
       if (concatIsec->shouldOmitFromOutput())
         continue;
       NamePair names = maybeRenameSection({isec->segname, isec->name});
       ConcatOutputSection *&concatOsec = concatOutputSections[names];
if (ssec->isNeeded()) {
       }
     }
   }
 
   // dyld requires __LINKEDIT segment to always exist (even if empty).
   linkEditSegment = getOrCreateOutputSegment(segment_names::linkEdit);
 }
 
+void Writer::foldIdenticalSections() {
+  if (config->icfLevel == ICFLevel::none)
+    return;
+  ConcatOutputSection *textOutputSection = concatOutputSections.lookup(
+      maybeRenameSection({segment_names::text, section_names::text}));
+  if (textOutputSection == nullptr)
+    return;
+
+  TimeTraceScope timeScope("Fold Identical Code Sections");
+  // The ICF equivalence-class segregation algorithm relies on pre-computed
+  // hashes of InputSection::data for the ConcatOutputSection::inputs and all
+  // sections referenced by their relocs. We could recursively traverse the
+  // relocs to find every referenced InputSection, but that precludes easy
+  // parallelization. Therefore, we hash every InputSection here where we have
+  // them all accessible as a simple vector.
+  std::vector<InputSection *> hashable;
+  // If an InputSection is ineligible for ICF, we give it a unique ID to force
+  // it into an unfoldable singleton equivalence class.  Begin the unique-ID
+  // space at inputSections.size(), so that it will never intersect with
+  // equivalence-class IDs which begin at 0. Since hashes & unique IDs never
+  // coexist with equivalence-class IDs, this is not necessary, but might help
+  // someone keep the numbers straight in case we ever need to debug the
+  // ICF::segregate()
+  uint64_t icfUniqueID = inputSections.size();
+  for (InputSection *isec : inputSections) {
+    if (isec->isHashableForICF(isec->parent == textOutputSection))
+      hashable.push_back(isec);
+    else
+      isec->icfEqClass[0] = ++icfUniqueID;
+  }
+  parallelForEach(hashable, [](InputSection *isec) { isec->hashForICF(); });
+  // Now that every input section is either hashed or marked as unique,
+  // run the segregation algorithm to detect foldable subsections
+  ICF(textOutputSection->inputs).run();
+  size_t oldSize = textOutputSection->inputs.size();
+  textOutputSection->eraseOmittedInputSections();
+  size_t newSize = textOutputSection->inputs.size();
+  log("ICF kept " + Twine(newSize) + " removed " + Twine(oldSize - newSize) +
+      " of " + Twine(oldSize));
+}
+
 void Writer::finalizeAddresses() {
   TimeTraceScope timeScope("Finalize addresses");
   uint64_t pageSize = target->getPageSize();
   // Ensure that segments (and the sections they contain) are allocated
   // addresses in ascending order, which dyld requires.
   //
   // Note that at this point, __LINKEDIT sections are empty, but we need to
   // determine addresses of other segments/sections before generating its

 template <class LP> void Writer::run() {
   if (config->entry && !isa<Undefined>(config->entry))
     prepareBranchTarget(config->entry);
   scanRelocations();
   if (in.stubHelper->isNeeded())
     in.stubHelper->setup();
   scanSymbols();
   createOutputSections<LP>();
+  foldIdenticalSections();
   // After this point, we create no new segments; HOWEVER, we might
   // yet create branch-range extension thunks for architectures whose
   // hardware call instructions have limited range, e.g., ARM(64).
   // The thunks are created as InputSections interspersed among
   // the ordinary __TEXT,_text InputSections.
   sortSegmentsAndSections();
   createLoadCommands<LP>();
   finalizeAddresses();

lld/test/MachO/Inputs/MacOSX.sdk/usr/lib/libSystem.tbd

- target:       arm64-macos
     value:        00000000-0000-0000-0000-000000000005
 install-name:     '/usr/lib/system/libsystem_m.dylib'
 current-version:  0001.001.1
 parent-umbrella:
   - targets:      [ x86_64-macos, x86_64-maccatalyst, arm64-macos ]
     umbrella:     System
 exports:
   - targets:      [ x86_64-macos, x86_64-maccatalyst, arm64-macos ]
-    symbols:      [ ___nan ]
+    symbols:      [ ___nan, ___isnan, ___inf, ___isinf ]
 ...

lld/test/MachO/icf-options.s

+# REQUIRES: x86
+# RUN: rm -rf %t; mkdir %t
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/main.o
+# RUN: %lld -lSystem -icf all -o %t/all %t/main.o 2>&1 \
+# RUN:     | FileCheck %s --check-prefix=DIAG-EMPTY --allow-empty
+# RUN: %lld -lSystem -icf none -o %t/none %t/main.o 2>&1 \
+# RUN:     | FileCheck %s --check-prefix=DIAG-EMPTY --allow-empty
+# RUN: %lld -lSystem -no_deduplicate -o %t/no_dedup %t/main.o 2>&1 \
+# RUN:     | FileCheck %s --check-prefix=DIAG-EMPTY --allow-empty
+# RUN: not %lld -lSystem -icf safe -o %t/safe %t/main.o 2>&1 \
+# RUN:     | FileCheck %s --check-prefix=DIAG-SAFE
+# RUN: not %lld -lSystem -icf junk -o %t/junk %t/main.o 2>&1 \
+# RUN:     | FileCheck %s --check-prefix=DIAG-JUNK
+# RUN: not %lld -lSystem -icf all -no_deduplicate -o %t/clash %t/main.o 2>&1 \
+# RUN:     | FileCheck %s --check-prefix=DIAG-CLASH
+
+# DIAG-EMPTY-NOT: {{.}}
+# DIAG-SAFE: `-icf safe' is not yet implemented, reverting to `none'
+# DIAG-JUNK: unknown -icf OPTION `junk', defaulting to `none'
+# DIAG-CLASH: `-icf all' conflicts with -no_deduplicate, setting to `none'
+
+# RUN: llvm-objdump -d --syms %t/all | FileCheck %s --check-prefix=FOLD
+# RUN: llvm-objdump -d --syms %t/none | FileCheck %s --check-prefix=NOOP
+# RUN: llvm-objdump -d --syms %t/no_dedup | FileCheck %s --check-prefix=NOOP
+
+# FOLD-LABEL: SYMBOL TABLE:
+# FOLD:       [[#%x,MAIN:]] g   F __TEXT,__text _main
+# FOLD:       [[#%x,F:]]    g   F __TEXT,__text _f1
+# FOLD:       [[#%x,F]]     g   F __TEXT,__text _f2
+
+# FOLD-LABEL: Disassembly of section __TEXT,__text:
+# FOLD:       [[#%x,MAIN]] <_main>:
+# FOLD-NEXT:  callq 0x[[#%x,F]]  <_f2>
+# FOLD-NEXT:  callq 0x[[#%x,F]]  <_f2>
+
+# NOOP-LABEL: SYMBOL TABLE:
+# NOOP:       [[#%x,MAIN:]] g   F __TEXT,__text _main
+# NOOP:       [[#%x,F1:]]   g   F __TEXT,__text _f1
+# NOOP:       [[#%x,F2:]]   g   F __TEXT,__text _f2
+
+# NOOP-LABEL: Disassembly of section __TEXT,__text:
+# NOOP:       [[#%x,MAIN]] <_main>:
+# NOOP-NEXT:  callq 0x[[#%x,F1]]  <_f1>
+# NOOP-NEXT:  callq 0x[[#%x,F2]]  <_f2>
+
+.subsections_via_symbols
+.text
+.p2align 2
+
+.globl _f1
+_f1:
+  movl $0, %eax
+  ret
+
+.globl _f2
+_f2:
+  movl $0, %eax
+  ret
+
+.globl _main
+_main:
+  callq _f1
+  callq _f2
+  ret

lld/test/MachO/icf-scale.s

+# REQUIRES: x86
+# RUN: rm -rf %t*
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
+# RUN: %lld -lSystem -icf all -o %t %t.o
+# RUN: llvm-objdump -d --syms %t | FileCheck %s
+
+## When ICF has fewer than 1 Ki functions to segregate into equivalence classes,
+## it uses a sequential algorithm to avoid the overhead of threading.
+## At 1 Ki functions or more, when threading begins to pay-off, ICF employs its
+## parallel segregation algorithm. Here we generate 4 Ki functions to exercise
+## the parallel algorithm. There are 4 unique function bodies, each replicated
+## 1 Ki times. The resulting folded program should retain one instance for each
+## of the four unique functions.
+
+# CHECK-LABEL: SYMBOL TABLE:
+# CHECK: [[#%x,G0:]] g   F __TEXT,__text _g000000
+# CHECK: [[#%x,G1:]] g   F __TEXT,__text _g100000
+# CHECK: [[#%x,G2:]] g   F __TEXT,__text _g200000
+# CHECK: [[#%x,G3:]] g   F __TEXT,__text _g300000
+## . . . many intervening _gXXXXXX symbols
+# CHECK: [[#%x,G0]]  g   F __TEXT,__text _g033333
+# CHECK: [[#%x,G1]]  g   F __TEXT,__text _g133333
+# CHECK: [[#%x,G2]]  g   F __TEXT,__text _g233333
+# CHECK: [[#%x,G3]]  g   F __TEXT,__text _g333333
+
+# CHECK-LABEL: Disassembly of section __TEXT,__text:
+# CHECK-DAG: [[#%x,G0]]  <_g033333>:
+# CHECK-DAG: [[#%x,G1]]  <_g133333>:
+# CHECK-DAG: [[#%x,G2]]  <_g233333>:
+# CHECK-DAG: [[#%x,G3]]  <_g333333>:
+# CHECK-NOT: [[#]]       <_g{{.*}}>:
+
+.subsections_via_symbols
+.text
+.p2align 2
+
+.macro gen_4 c
+  .globl _g0\c, _g1\c, _g2\c, _g3\c
+  _g0\c:; movl $0, %eax; ret
+  _g1\c:; movl $1, %eax; ret
+  _g2\c:; movl $2, %eax; ret
+  _g3\c:; movl $3, %eax; ret
+.endm
+
+.macro gen_16 c
+  gen_4 0\c
+  gen_4 1\c
+  gen_4 2\c
+  gen_4 3\c
+.endm
+
+.macro gen_64 c
+  gen_16 0\c
+  gen_16 1\c
+  gen_16 2\c
+  gen_16 3\c
+.endm
+
+.macro gen_256 c
+  gen_64 0\c
+  gen_64 1\c
+  gen_64 2\c
+  gen_64 3\c
+.endm
+
+.macro gen_1024 c
+  gen_256 0\c
+  gen_256 1\c
+  gen_256 2\c
+  gen_256 3\c
+.endm
+
+gen_1024 0
+gen_1024 1
+gen_1024 2
+gen_1024 3
+
+.globl _main
+_main:
+  ret

lld/test/MachO/icf.s

+# REQUIRES: x86
+# RUN: rm -rf %t; mkdir %t
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/main.o
+# RUN: %lld -lSystem -icf all -o %t/main %t/main.o
+# RUN: llvm-objdump -d --syms %t/main | FileCheck %s
+
+# CHECK-LABEL: SYMBOL TABLE:
+# CHECK:       [[#%x,MAIN:]] g   F __TEXT,__text _main
+# CHECK:       [[#%x,A:]]    g   F __TEXT,__text _a1
+# CHECK:       [[#%x,A]]     g   F __TEXT,__text _a2
+# CHECK:       [[#%x,C:]]    g   F __TEXT,__text _c
+# CHECK:       [[#%x,D:]]    g   F __TEXT,__text _d
+# CHECK:       [[#%x,E:]]    g   F __TEXT,__text _e
+# CHECK:       [[#%x,F:]]    g   F __TEXT,__text _f
+# CHECK:       [[#%x,G:]]    g   F __TEXT,__text _g
+# CHECK:       [[#%x,SR:]]   g   F __TEXT,__text _sr1
+# CHECK:       [[#%x,SR]]    g   F __TEXT,__text _sr2
+# CHECK:       [[#%x,MR:]]   g   F __TEXT,__text _mr1
+# CHECK:       [[#%x,MR]]    g   F __TEXT,__text _mr2
+### FIXME: Mutually-recursive functions with identical bodies (see below)
+# COM:         [[#%x,XR:]]   g   F __TEXT,__text _xr1
+# COM:         [[#%x,XR]]    g   F __TEXT,__text _xr2
+
+# CHECK-LABEL: Disassembly of section __TEXT,__text:
+# CHECK:       [[#%x,MAIN]] <_main>:
+# CHECK-NEXT:  callq 0x[[#%x,A]]  <_a2>
+# CHECK-NEXT:  callq 0x[[#%x,A]]  <_a2>
+# CHECK-NEXT:  callq 0x[[#%x,C]]  <_c>
+# CHECK-NEXT:  callq 0x[[#%x,D]]  <_d>
+# CHECK-NEXT:  callq 0x[[#%x,E]]  <_e>
+# CHECK-NEXT:  callq 0x[[#%x,F]]  <_f>
+# CHECK-NEXT:  callq 0x[[#%x,G]]  <_g>
+# CHECK-NEXT:  callq 0x[[#%x,SR]] <_sr2>
+# CHECK-NEXT:  callq 0x[[#%x,SR]] <_sr2>
+# CHECK-NEXT:  callq 0x[[#%x,MR]] <_mr2>
+# CHECK-NEXT:  callq 0x[[#%x,MR]] <_mr2>
+### FIXME: Mutually-recursive functions with identical bodies (see below)
+# COM-NEXT:    callq 0x[[#%x,XR]] <_xr2>
+# COM-NEXT:    callq 0x[[#%x,XR]] <_xr2>
+
+### TODO:
+### * Fold: funcs only differ in alignment
+### * No fold: func has personality/LSDA
+### * No fold: reloc references to absolute symbols with different values
+### * No fold: func is weak? preemptable?
+### * No fold: relocs to N_ALT_ENTRY symbols
+
+.subsections_via_symbols
+.text
+
+### Fold: _a1 & _a2 have identical bodies, flags, relocs
+
+.globl _a1
+.p2align 4, 0x90
+_a1:
+  callq _d
+  mov ___nan@GOTPCREL(%rip), %rax
+  callq ___isnan
+  movl $0, %eax
+  ret
+
+.globl _a2
+.p2align 4, 0x90
+_a2:
+  callq _d
+  mov ___nan@GOTPCREL(%rip), %rax
+  callq ___isnan
+  movl $0, %eax
+  ret
+
+### No fold: _c has slightly different body from _a1 & _a2
+
+.globl _c
+.p2align 4, 0x90
+_c:
+  callq _d
+  mov ___nan@GOTPCREL(%rip), %rax
+  callq ___isnan
+  movl $1, %eax
+  ret
+
+### No fold: _d has the same body as _a1 & _a2, but _d is recursive!
+
+.globl _d
+.p2align 4, 0x90
+_d:
+  callq _d
+  mov ___nan@GOTPCREL(%rip), %rax
+  callq ___isnan
+  movl $0, %eax
+  ret
+
+### No fold: the body of _e is longer
+
+.globl _e
+.p2align 4, 0x90
+_e:
+  callq _d
+  mov ___nan@GOTPCREL(%rip), %rax
+  callq ___isnan
+  movl $0, %eax
+  ret
+  nop
+
+### No fold: the dylib symbols differ
+
+.globl _f
+.p2align 4, 0x90
+_f:
+  callq _d
+  mov ___inf@GOTPCREL(%rip), %rax
+  callq ___isnan
+  movl $0, %eax
+  ret
+
+.globl _g
+.p2align 4, 0x90
+_g:
+  callq _d
+  mov ___inf@GOTPCREL(%rip), %rax
+  callq ___isinf
+  movl $0, %eax
+  ret
+
+### Fold: Simple recursion
+
+.globl _sr1
+.p2align 4, 0x90
+_sr1:
+  callq _sr1
+  movl $2, %eax
+  ret
+
+.globl _sr2
+.p2align 4, 0x90
+_sr2:
+  callq _sr2
+  movl $2, %eax
+  ret
+
+### Fold: Mutually-recursive functions with symmetric bodies
+
+.globl _mr1
+.p2align 4, 0x90
+_mr1:
+  callq _mr1 # call myself
+  callq _mr2 # call my twin
+  movl $1, %eax
+  ret
+
+.globl _mr2
+.p2align 4, 0x90
+_mr2:
+  callq _mr2 # call myself
+  callq _mr1 # call my twin
+  movl $1, %eax
+  ret
+
+### Fold: Mutually-recursive functions with identical bodies
+###
+### FIXME: This test is currently broken. Recursive call sites have no relocs
+### and the non-zero displacement field is already written to the section
+### data, while non-recursive call sites use symbol relocs and section data
+### contains zeros in the displacement field. Thus, ICF's equalsConstant()
+### finds that the section data doesn't match.
+###
+### ELF folds this case properly because it emits symbol relocs for all calls,
+### even recursive ones.
+
+.globl _xr1
+.p2align 4, 0x90
+_xr1:
+  callq _xr1 # call myself
+  callq _xr2 # call my twin
+  movl $3, %eax
+  ret
+
+.globl _xr2
+.p2align 4, 0x90
+_xr2:
+  callq _xr1 # call my twin
+  callq _xr2 # call myself
+  movl $3, %eax
+  ret
+
+###
+
+.globl _main
+.p2align 4, 0x90
+_main:
+  callq _a1
+  callq _a2
+  callq _c
+  callq _d
+  callq _e
+  callq _f
+  callq _g
+  callq _sr1
+  callq _sr2
+  callq _mr1
+  callq _mr2
+  callq _xr1
+  callq _xr2
+  ret