[lld-macho] Move ICF earlier to avoid emitting redundant binds

[int3]

Summary

This is a pretty big refactoring diff, so here are the motivations:

Previously, ICF ran after scanRelocations(), where we emitting
bind/rebase opcodes etc. So we had a bunch of redundant leftovers after
ICF. Having ICF run before Writer seems like a better design, and is
what LLD-ELF does, so this diff refactors it accordingly.

However, ICF had two dependencies on things occurring in Writer: 1) it
needs literals to be deduplicated beforehand and 2) it needs to know
which functions have unwind info, which was being handled by
UnwindInfoSection::prepareRelocations().

In order to do literal deduplication earlier, we need to add literal
input sections to their corresponding output sections. So instead of
putting all input sections into the big inputSections vector, and then
filtering them by type later on, I've changed things so that literal
sections get added directly to their output sections during the 'gather'
phase. Likewise for compact unwind sections -- they get added directly
to the UnwindInfoSection now. This latter change is not strictly
necessary, but makes it easier for ICF to determine which functions have
unwind info.

Adding literal sections directly to their output sections means that we
can no longer determine inputOrder from iterating over
inputSections. Instead, we store that order explicitly on
InputSection. Bloating the size of InputSection for this purpose would
be unfortunate -- but LLD-ELF has already solved this problem: it reuses
outSecOff to store this order value.

One downside of this refactor is that we now make an additional pass
over the unwind info relocations to figure out which functions have
unwind info, since want to know that before processRelocations(). I've
made sure to run that extra loop only if ICF is enabled, so there should
be no overhead in non-optimizing runs of the linker.

The upside of all this is that the inputSections vector now contains
only ConcatInputSections that are destined for ConcatOutputSections, so
we can clean up a bunch of code that just existed to filter out other
elements from that vector.

I will test for the lack of redundant binds/rebases in the upcoming
cfstring deduplication diff. While binds/rebases can also happen in the
regular .text section, they're more common in .data sections, so it
seems more natural to test it that way.

This change is perf-neutral when linking chromium_framework.

[int3]

lld/MachO/SyntheticSections.cpp

778

another benefit of moving ICF earlier: the lack of canonicalization is now obvious, since the parent point of coalesced InputSections is null.

[int3]

change how we implement inputOrder

[oontvoo]

lld/MachO/Driver.cpp

994

(clang-tidy suggestion)

1002

why not leave it as 0-based rather than 1?

not saying it's wrong ... just curious :)

lld/MachO/UnwindInfoSection.cpp

133

why "4"? is this not platform dependent?

lld/MachO/Writer.cpp

615

894

nit: just for consistency

[int3]

lld/MachO/Driver.cpp

1002

well some reviewers seem to dislike post-increments :)

either a zero- or 1-based index works here, but yeah, maybe keeping it zero-based will be less surprising. I'll change it back

lld/MachO/UnwindInfoSection.cpp

133

this is existing code, I think @gkm wrote this

[int3]

address comments

[oontvoo]

LGTM - thanks! (but still curious about the hard-coded alignment)

[int3]

A quick check of ld64's output shows that __unwind_info is aligned to 4 across x86_64/x86/arm64/armv7, so I think we're good here :)

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

void ConcatOutputSection::finalizeFlags(InputSection *input) {
   case S_THREAD_LOCAL_INIT_FUNCTION_POINTERS:
   case S_THREAD_LOCAL_VARIABLE_POINTERS:
   case S_NON_LAZY_SYMBOL_POINTERS:
   case S_SYMBOL_STUBS:
     flags |= input->flags;
     break;
   }
 }
-
-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/Driver.cpp

 //===- Driver.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 "Driver.h"
 #include "Config.h"
+#include "ICF.h"
 #include "InputFiles.h"
 #include "LTO.h"
 #include "MarkLive.h"
 #include "ObjC.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
+#include "UnwindInfoSection.h"
 #include "Writer.h"
 
 #include "lld/Common/Args.h"
 #include "lld/Common/Driver.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/LLVM.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Reproduce.h"
case OPT_weak_framework:
                    opt.getID() == OPT_reexport_framework, /*isExplicit=*/true);
       break;
     default:
       break;
     }
   }
 }
 
+static void gatherInputSections() {
+  TimeTraceScope timeScope("Gathering input sections");
+  int inputOrder = 0;
+  for (const InputFile *file : inputFiles) {
+    for (const SubsectionMap &map : file->subsections) {
+      for (const SubsectionEntry &entry : map) {
+        if (auto *isec = dyn_cast<ConcatInputSection>(entry.isec)) {
+          if (isec->isCoalescedWeak())
+            continue;
+          if (isec->segname == segment_names::ld) {
+            assert(isec->name == section_names::compactUnwind);
+            in.unwindInfo->addInput(isec);
+            continue;
+          }
+          isec->outSecOff = inputOrder++;
+          inputSections.push_back(isec);
+        } else if (auto *isec = dyn_cast<CStringInputSection>(entry.isec)) {
+          if (in.cStringSection->inputOrder == UnspecifiedInputOrder)
+            in.cStringSection->inputOrder = inputOrder++;
+          in.cStringSection->addInput(isec);
+        } else if (auto *isec = dyn_cast<WordLiteralInputSection>(entry.isec)) {
+          if (in.wordLiteralSection->inputOrder == UnspecifiedInputOrder)
+            in.wordLiteralSection->inputOrder = inputOrder++;
+          in.wordLiteralSection->addInput(isec);
+        } else {
+          llvm_unreachable("unexpected input section kind");
+        }
+      }
+    }
+  }
+  assert(inputOrder <= UnspecifiedInputOrder);
+}
+
+static void foldIdenticalLiterals() {
+  // We always create a cStringSection, regardless of whether dedupLiterals is
+  // true. If it isn't, we simply create a non-deduplicating CStringSection.
+  // Either way, we must unconditionally finalize it here.
+  in.cStringSection->finalizeContents();
+  if (in.wordLiteralSection)
+    in.wordLiteralSection->finalizeContents();
+}
+
 bool macho::link(ArrayRef<const char *> argsArr, bool canExitEarly,
                  raw_ostream &stdoutOS, raw_ostream &stderrOS) {
   lld::stdoutOS = &stdoutOS;
   lld::stderrOS = &stderrOS;
 
   errorHandler().cleanupCallback = []() { freeArena(); };
 
   errorHandler().logName = args::getFilenameWithoutExe(argsArr[0]);
for (const Arg *arg : args.filtered(OPT_sectcreate)) {
       StringRef segName = arg->getValue(0);
       StringRef sectName = arg->getValue(1);
       StringRef fileName = arg->getValue(2);
       Optional<MemoryBufferRef> buffer = readFile(fileName);
       if (buffer)
         inputFiles.insert(make<OpaqueFile>(*buffer, segName, sectName));
     }
 
-    {
-      TimeTraceScope timeScope("Gathering input sections");
-      // Gather all InputSections into one vector.
-      for (const InputFile *file : inputFiles) {
-        for (const SubsectionMap &map : file->subsections) {
-          for (const SubsectionEntry &entry : map) {
-            if (auto concatIsec = dyn_cast<ConcatInputSection>(entry.isec))
-              if (concatIsec->isCoalescedWeak())
-                continue;
-            inputSections.push_back(entry.isec);
-          }
-        }
-      }
-      assert(inputSections.size() < UnspecifiedInputOrder);
-    }
+    gatherInputSections();
 
     if (config->deadStrip)
       markLive();
 
+    // ICF assumes that all literals have been folded already, so we must run
+    // foldIdenticalLiterals before foldIdenticalSections.
+    foldIdenticalLiterals();
+    if (config->icfLevel != ICFLevel::none)
+      foldIdenticalSections();
+
     // Write to an output file.
     if (target->wordSize == 8)
       writeResult<LP64>();
     else
       writeResult<ILP32>();
 
     depTracker->write(getLLDVersion(), inputFiles, config->outputFile);
   }

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;
-};
+void foldIdenticalSections();
 
 } // 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 "UnwindInfoSection.h"
+
 #include "llvm/Support/Parallel.h"
+#include "llvm/Support/TimeProfiler.h"
 
 #include <atomic>
 
 using namespace llvm;
 using namespace lld;
 using namespace lld::macho;
 
+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;
+};
+
 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
while (begin < end) {
 
     // If we created a group, we need to iterate the main loop again.
     if (mid != end)
       icfRepeat = true;
 
     begin = mid;
   }
 }
+
+template <class Ptr>
+DenseSet<const InputSection *> findFunctionsWithUnwindInfo() {
+  DenseSet<const InputSection *> result;
+  for (ConcatInputSection *isec : in.unwindInfo->getInputs()) {
+    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>, functionAddress))
+        continue;
+      result.insert(r.referent.get<InputSection *>());
+    }
+  }
+  return result;
+}
+
+void macho::foldIdenticalSections() {
+  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 simple vectors.
+  std::vector<ConcatInputSection *> codeSections;
+
+  // ICF can't fold functions with unwind info
+  DenseSet<const InputSection *> functionsWithUnwindInfo =
+      target->wordSize == 8 ? findFunctionsWithUnwindInfo<uint64_t>()
+                            : findFunctionsWithUnwindInfo<uint32_t>();
+
+  // 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 (ConcatInputSection *isec : inputSections) {
+    bool isHashable = isCodeSection(isec) && !isec->shouldOmitFromOutput() &&
+                      !functionsWithUnwindInfo.contains(isec) &&
+                      isec->isHashableForICF();
+    if (isHashable) {
+      codeSections.push_back(isec);
+    } else {
+      isec->icfEqClass[0] = ++icfUniqueID;
+    }
+  }
+  parallelForEach(codeSections,
+                  [](ConcatInputSection *isec) { isec->hashForICF(); });
+  // Now that every input section is either hashed or marked as unique, run the
+  // segregation algorithm to detect foldable subsections.
+  ICF(codeSections).run();
+}

lld/MachO/InputSection.h

public:
 
   uint64_t getOffset(uint64_t off) const override { return outSecOff + off; }
   uint64_t getVA() const { return InputSection::getVA(0); }
   // ConcatInputSections are entirely live or dead, so the offset is irrelevant.
   bool isLive(uint64_t off) const override { return live; }
   void markLive(uint64_t off) override { live = true; }
   bool isCoalescedWeak() const { return wasCoalesced && numRefs == 0; }
   bool shouldOmitFromOutput() const { return !live || isCoalescedWeak(); }
-  bool isHashableForICF(bool isText) const;
+  bool isHashableForICF() const;
   void hashForICF();
   void writeTo(uint8_t *buf);
 
   void foldIdentical(ConcatInputSection *redundant);
   InputSection *canonical() override {
     return replacement ? replacement : this;
   }
 
   static bool classof(const InputSection *isec) {
     return isec->kind() == ConcatKind;
   }
 
-  // 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};
 
   // 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;
+  // This variable has two usages. Initially, it represents the input order.
+  // After assignAddresses is called, it represents the offset from the
+  // beginning of the output section this section was assigned to.
   uint64_t outSecOff = 0;
 };
 
 // Helper functions to make it easy to sprinkle asserts.
 
 inline bool shouldOmitFromOutput(InputSection *isec) {
   return isa<ConcatInputSection>(isec) &&
          cast<ConcatInputSection>(isec)->shouldOmitFromOutput();

 inline bool isWordLiteralSection(uint32_t flags) {
   return sectionType(flags) == llvm::MachO::S_4BYTE_LITERALS ||
          sectionType(flags) == llvm::MachO::S_8BYTE_LITERALS ||
          sectionType(flags) == llvm::MachO::S_16BYTE_LITERALS;
 }
 
 bool isCodeSection(const InputSection *);
 
-extern std::vector<InputSection *> inputSections;
+extern std::vector<ConcatInputSection *> inputSections;
 
 namespace section_names {
 
 constexpr const char authGot[] = "__auth_got";
 constexpr const char authPtr[] = "__auth_ptr";
 constexpr const char binding[] = "__binding";
 constexpr const char bitcodeBundle[] = "__bundle";
 constexpr const char cString[] = "__cstring";

lld/MachO/InputSection.cpp

 #include "llvm/Support/xxhash.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::support;
 using namespace lld;
 using namespace lld::macho;
 
-std::vector<InputSection *> macho::inputSections;
+std::vector<ConcatInputSection *> macho::inputSections;
 
 uint64_t InputSection::getFileSize() const {
   return isZeroFill(flags) ? 0 : getSize();
 }
 
 uint64_t InputSection::getVA(uint64_t off) const {
   return parent->addr + getOffset(off);
 }
 
 static uint64_t resolveSymbolVA(const Symbol *sym, uint8_t type) {
   const RelocAttrs &relocAttrs = target->getRelocAttrs(type);
   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 ConcatInputSection::isHashableForICF(bool isText) const {
-  if (shouldOmitFromOutput())
-    return false;
+bool ConcatInputSection::isHashableForICF() const {
   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;
+    return true;
   case S_CSTRING_LITERALS:
   case S_4BYTE_LITERALS:
   case S_8BYTE_LITERALS:
   case S_16BYTE_LITERALS:
   case S_LITERAL_POINTERS:
     llvm_unreachable("found unexpected literal type in ConcatInputSection");
   case S_ZEROFILL:
   case S_GB_ZEROFILL:

lld/MachO/MarkLive.cpp

for (const InputFile *file : inputFiles)
     if (auto *objFile = dyn_cast<ObjFile>(file))
       for (Symbol *sym : objFile->symbols)
         if (auto *defined = dyn_cast_or_null<Defined>(sym))
           if (!defined->isExternal() && defined->noDeadStrip)
             addSym(defined);
   if (auto *stubBinder =
           dyn_cast_or_null<DylibSymbol>(symtab->find("dyld_stub_binder")))
     addSym(stubBinder);
-  for (InputSection *isec : inputSections) {
+  for (ConcatInputSection *isec : inputSections) {
     // Sections marked no_dead_strip
     if (isec->flags & S_ATTR_NO_DEAD_STRIP) {
-      assert(isa<ConcatInputSection>(isec));
       enqueue(isec, 0);
       continue;
     }
 
     // mod_init_funcs, mod_term_funcs sections
     if (sectionType(isec->flags) == S_MOD_INIT_FUNC_POINTERS ||
         sectionType(isec->flags) == S_MOD_TERM_FUNC_POINTERS) {
-      assert(isa<ConcatInputSection>(isec));
       enqueue(isec, 0);
       continue;
     }
+  }
 
-    // Dead strip runs before UnwindInfoSection handling so we need to keep
-    // __LD,__compact_unwind alive here.
-    // But that section contains absolute references to __TEXT,__text and
-    // keeps most code alive due to that. So we can't just enqueue() the
-    // section: We must skip the relocations for the functionAddress
-    // in each CompactUnwindEntry.
-    // See also scanEhFrameSection() in lld/ELF/MarkLive.cpp.
-    if (isec->segname == segment_names::ld &&
-        isec->name == section_names::compactUnwind) {
-      auto concatIsec = cast<ConcatInputSection>(isec);
-      concatIsec->live = true;
-      const int compactUnwindEntrySize =
-          target->wordSize == 8 ? sizeof(CompactUnwindEntry<uint64_t>)
-                                : sizeof(CompactUnwindEntry<uint32_t>);
-      for (const Reloc &r : isec->relocs) {
-        // This is the relocation for the address of the function itself.
-        // Ignore it, else these would keep everything alive.
-        if (r.offset % compactUnwindEntrySize == 0)
-          continue;
+  for (ConcatInputSection *isec : in.unwindInfo->getInputs()) {
+    isec->live = true;
 
-        if (auto *s = r.referent.dyn_cast<Symbol *>())
-          addSym(s);
-        else
-          enqueue(r.referent.get<InputSection *>(), r.addend);
-      }
-      continue;
-    }
   }
 
   do {
     // Mark things reachable from GC roots as live.
     while (!worklist.empty()) {
       ConcatInputSection *s = worklist.pop_back_val();
       assert(s->live && "We mark as live when pushing onto the worklist!");
 
       // Mark all symbols listed in the relocation table for this section.
       for (const Reloc &r : s->relocs) {
         if (auto *s = r.referent.dyn_cast<Symbol *>())
           addSym(s);
         else
           enqueue(r.referent.get<InputSection *>(), r.addend);
       }
     }
 
     // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live section.
     // Process them in a second pass.
-    for (InputSection *isec : inputSections) {
-      if (!isa<ConcatInputSection>(isec))
-        continue;
-      auto concatIsec = cast<ConcatInputSection>(isec);
+    for (ConcatInputSection *isec : inputSections) {
       // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a
       // separate vector and only walking that here is faster.
-      if (!(concatIsec->flags & S_ATTR_LIVE_SUPPORT) || concatIsec->live)
+      if (!(isec->flags & S_ATTR_LIVE_SUPPORT) || isec->live)
         continue;
 
       for (const Reloc &r : isec->relocs) {
         bool referentLive;
         if (auto *s = r.referent.dyn_cast<Symbol *>())
           referentLive = s->isLive();
         else
           referentLive = r.referent.get<InputSection *>()->isLive(r.addend);

lld/MachO/SyntheticSections.h

 public:
   using UInt128 = std::pair<uint64_t, uint64_t>;
   // I don't think the standard guarantees the size of a pair, so let's make
   // sure it's exact -- that way we can construct it via `mmap`.
   static_assert(sizeof(UInt128) == 16, "");
 
   WordLiteralSection();
   void addInput(WordLiteralInputSection *);
+  void finalizeContents();
   void writeTo(uint8_t *buf) const override;
 
   uint64_t getSize() const override {
     return literal16Map.size() * 16 + literal8Map.size() * 8 +
            literal4Map.size() * 4;
   }
 
   bool isNeeded() const override {
public:
   }
 
   uint64_t getLiteral4Offset(const uint8_t *buf) const {
     return literal16Map.size() * 16 + literal8Map.size() * 8 +
            literal4Map.at(*reinterpret_cast<const uint32_t *>(buf)) * 4;
   }
 
 private:
+  std::vector<WordLiteralInputSection *> inputs;
+
   template <class T> struct Hasher {
     llvm::hash_code operator()(T v) const { return llvm::hash_value(v); }
   };
   // We're using unordered_map instead of DenseMap here because we need to
   // support all possible integer values -- there are no suitable tombstone
   // values for DenseMap.
   std::unordered_map<UInt128, uint64_t, Hasher<UInt128>> literal16Map;
   std::unordered_map<uint64_t, uint64_t> literal8Map;

lld/MachO/SyntheticSections.cpp

if (lastFile == nullptr || lastFile != file) {
         emitEndSourceStab();
       lastFile = file;
 
       emitBeginSourceStab(file->compileUnit);
       emitObjectFileStab(file);
     }
 
     StabsEntry symStab;
-    symStab.sect = defined->isec->parent->index;
+    symStab.sect = defined->isec->canonical()->parent->index;
     symStab.strx = stringTableSection.addString(defined->getName());
     symStab.value = defined->getVA();
 
     if (isCodeSection(isec)) {
       symStab.type = N_FUN;
       stabs.emplace_back(std::move(symStab));
       emitEndFunStab(defined);
     } else {
if (auto *defined = dyn_cast<Defined>(entry.sym)) {
       }
 
       if (defined->isAbsolute()) {
         nList->n_type = scope | N_ABS;
         nList->n_sect = NO_SECT;
         nList->n_value = defined->value;
       } else {
         nList->n_type = scope | N_SECT;
-        nList->n_sect = defined->isec->parent->index;
+        nList->n_sect = defined->isec->canonical()->parent->index;
         // For the N_SECT symbol type, n_value is the address of the symbol
         nList->n_value = defined->getVA();
       }
       nList->n_desc |= defined->thumb ? N_ARM_THUMB_DEF : 0;
       nList->n_desc |= defined->isExternalWeakDef() ? N_WEAK_DEF : 0;
       nList->n_desc |=
           defined->referencedDynamically ? REFERENCED_DYNAMICALLY : 0;
     } else if (auto *dysym = dyn_cast<DylibSymbol>(entry.sym)) {

 // our merged-literals section a different name.
 WordLiteralSection::WordLiteralSection()
     : SyntheticSection(segment_names::text, section_names::literals) {
   align = 16;
 }
 
 void WordLiteralSection::addInput(WordLiteralInputSection *isec) {
   isec->parent = this;
+  inputs.push_back(isec);
+}
+
+void WordLiteralSection::finalizeContents() {
+  for (WordLiteralInputSection *isec : inputs) {
     // We do all processing of the InputSection here, so it will be effectively
     // finalized.
     isec->isFinal = true;
     const uint8_t *buf = isec->data.data();
     switch (sectionType(isec->flags)) {
     case S_4BYTE_LITERALS: {
       for (size_t off = 0, e = isec->data.size(); off < e; off += 4) {
         if (!isec->isLive(off))
           continue;
         uint32_t value = *reinterpret_cast<const uint32_t *>(buf + off);
         literal4Map.emplace(value, literal4Map.size());
       }
       break;
     }
     case S_8BYTE_LITERALS: {
       for (size_t off = 0, e = isec->data.size(); off < e; off += 8) {
         if (!isec->isLive(off))
           continue;
         uint64_t value = *reinterpret_cast<const uint64_t *>(buf + off);
         literal8Map.emplace(value, literal8Map.size());
       }
       break;
     }
     case S_16BYTE_LITERALS: {
       for (size_t off = 0, e = isec->data.size(); off < e; off += 16) {
         if (!isec->isLive(off))
           continue;
         UInt128 value = *reinterpret_cast<const UInt128 *>(buf + off);
         literal16Map.emplace(value, literal16Map.size());
       }
       break;
     }
     default:
       llvm_unreachable("invalid literal section type");
     }
   }
+}
 
 void WordLiteralSection::writeTo(uint8_t *buf) const {
   // Note that we don't attempt to do any endianness conversion in addInput(),
   // so we don't do it here either -- just write out the original value,
   // byte-for-byte.
   for (const auto &p : literal16Map)
     memcpy(buf + p.second * 16, &p.first, 16);
   buf += literal16Map.size() * 16;

lld/MachO/UnwindInfoSection.h

template <class Ptr> struct CompactUnwindEntry {
   uint32_t functionLength;
   compact_unwind_encoding_t encoding;
   Ptr personality;
   Ptr lsda;
 };
 
 class UnwindInfoSection : public SyntheticSection {
 public:
-  bool isNeeded() const override { return compactUnwindSection != nullptr; }
+  bool isNeeded() const override {
+    return !compactUnwindSection->inputs.empty();
+  }
   uint64_t getSize() const override { return unwindInfoSize; }
-  virtual void prepareRelocations(ConcatInputSection *) = 0;
-
-  void setCompactUnwindSection(ConcatOutputSection *cuSection) {
-    compactUnwindSection = cuSection;
+  virtual void addInput(ConcatInputSection *) = 0;
+  std::vector<ConcatInputSection *> getInputs() {
+    return compactUnwindSection->inputs;
   }
+  void prepareRelocations();
 
 protected:
-  UnwindInfoSection()
-      : SyntheticSection(segment_names::text, section_names::unwindInfo) {
-    align = 4;
-  }
+  UnwindInfoSection();
+  virtual void prepareRelocations(ConcatInputSection *) = 0;
 
-  ConcatOutputSection *compactUnwindSection = nullptr;
+  ConcatOutputSection *compactUnwindSection;
   uint64_t unwindInfoSize = 0;
 };
 
 UnwindInfoSection *makeUnwindInfoSection();
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/UnwindInfoSection.cpp

struct SecondLevelPage {
   uint32_t kind;
   size_t entryIndex;
   size_t entryCount;
   size_t byteCount;
   std::vector<compact_unwind_encoding_t> localEncodings;
   EncodingMap localEncodingIndexes;
 };
 
-template <class Ptr> class UnwindInfoSectionImpl : public UnwindInfoSection {
+template <class Ptr>
+class UnwindInfoSectionImpl final : public UnwindInfoSection {
 public:
   void prepareRelocations(ConcatInputSection *) override;
+  void addInput(ConcatInputSection *) override;
   void finalize() override;
   void writeTo(uint8_t *buf) const override;
 
 private:
   std::vector<std::pair<compact_unwind_encoding_t, size_t>> commonEncodings;
   EncodingMap commonEncodingIndexes;
   // Indices of personality functions within the GOT.
   std::vector<uint32_t> personalities;
   SmallDenseMap<std::pair<InputSection *, uint64_t /* addend */>, Symbol *>
       personalityTable;
   std::vector<unwind_info_section_header_lsda_index_entry> lsdaEntries;
   // Map of function offset (from the image base) to an index within the LSDA
   // array.
   llvm::DenseMap<uint32_t, uint32_t> functionToLsdaIndex;
   std::vector<CompactUnwindEntry<Ptr>> cuVector;
   std::vector<CompactUnwindEntry<Ptr> *> cuPtrVector;
   std::vector<SecondLevelPage> secondLevelPages;
   uint64_t level2PagesOffset = 0;
 };
 
+UnwindInfoSection::UnwindInfoSection()
+    : SyntheticSection(segment_names::text, section_names::unwindInfo) {
+  align = 4;
+  compactUnwindSection =
+      make<ConcatOutputSection>(section_names::compactUnwind);
+}
+
+void UnwindInfoSection::prepareRelocations() {
+  for (ConcatInputSection *isec : compactUnwindSection->inputs)
+    prepareRelocations(isec);
+}
+
+template <class Ptr>
+void UnwindInfoSectionImpl<Ptr>::addInput(ConcatInputSection *isec) {
+  assert(isec->segname == segment_names::ld &&
+         isec->name == section_names::compactUnwind);
+  compactUnwindSection->addInput(isec);
+}
+
 // Compact unwind relocations have different semantics, so we handle them in a
 // separate code path from regular relocations. First, we do not wish to add
 // rebase opcodes for __LD,__compact_unwind, because that section doesn't
 // actually end up in the final binary. Second, personality pointers always
 // reside in the GOT and must be treated specially.
 template <class Ptr>
 void UnwindInfoSectionImpl<Ptr>::prepareRelocations(ConcatInputSection *isec) {
-  assert(isec->segname == segment_names::ld &&
-         isec->name == section_names::compactUnwind);
   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 (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));
-    auto *referentIsec =
-        cast<ConcatInputSection>(rFunc.referent.get<InputSection *>());
-    referentIsec->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 foldIdenticalLiterals();
-  void foldIdenticalSections();
   void finalizeAddresses();
   void finalizeLinkEditSegment();
   void assignAddresses(OutputSegment *);
 
   void openFile();
   void writeSections();
   void writeUuid();
   void writeCodeSignature();
if (relocAttrs.hasAttr(RelocAttrBits::BRANCH)) {
     // need of rebase opcodes.
     if (!(isThreadLocalVariables(isec->flags) && isa<Defined>(sym)))
       addNonLazyBindingEntries(sym, isec, r.offset, r.addend);
   }
 }
 
 void Writer::scanRelocations() {
   TimeTraceScope timeScope("Scan relocations");
-  for (InputSection *isec : inputSections) {
-    if (!isa<ConcatInputSection>(isec))
+  for (ConcatInputSection *isec : inputSections) {
+    if (isec->shouldOmitFromOutput())
       continue;
-    auto concatIsec = cast<ConcatInputSection>(isec);
-
-    if (concatIsec->shouldOmitFromOutput())
-      continue;
-
-    if (concatIsec->segname == segment_names::ld) {
-      in.unwindInfo->prepareRelocations(concatIsec);
-      continue;
-    }
 
     for (auto it = isec->relocs.begin(); it != isec->relocs.end(); ++it) {
       Reloc &r = *it;
       if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
         // Skip over the following UNSIGNED relocation -- it's just there as the
         // minuend, and doesn't have the usual UNSIGNED semantics. We don't want
         // to emit rebase opcodes for it.
         it++;
         continue;
       }
       if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
         if (auto *undefined = dyn_cast<Undefined>(sym))
           treatUndefinedSymbol(*undefined);
         // treatUndefinedSymbol() can replace sym with a DylibSymbol; re-check.
         if (!isa<Undefined>(sym) && validateSymbolRelocation(sym, isec, r))
           prepareSymbolRelocation(sym, isec, r);
       } else {
-        assert(r.referent.is<InputSection *>());
+        // Canonicalize the referent so that later accesses in Writer won't
+        // have to worry about it. Perhaps we should do this for Defined::isec
+        // too...
+        auto *referentIsec = r.referent.get<InputSection *>();
+        r.referent = referentIsec->canonical();
         if (!r.pcrel)
           in.rebase->addEntry(isec, r.offset);
       }
     }
   }
+
+  in.unwindInfo->prepareRelocations();
 }
 
 void Writer::scanSymbols() {
   TimeTraceScope timeScope("Scan symbols");
   for (const Symbol *sym : symtab->getSymbols()) {
     if (const auto *defined = dyn_cast<Defined>(sym)) {
       if (defined->overridesWeakDef && defined->isLive())
         in.weakBinding->addNonWeakDefinition(defined);
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.
-  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 (concatOsec == nullptr)
-        concatOsec = make<ConcatOutputSection>(names.second);
-      concatOsec->addInput(concatIsec);
-      osec = concatOsec;
-    } else if (auto *cStringIsec = dyn_cast<CStringInputSection>(isec)) {
-      in.cStringSection->addInput(cStringIsec);
-      osec = in.cStringSection;
-    } else if (auto *litIsec = dyn_cast<WordLiteralInputSection>(isec)) {
-      in.wordLiteralSection->addInput(litIsec);
-      osec = in.wordLiteralSection;
-    } else {
-      llvm_unreachable("unhandled InputSection type");
-    }
-    osec->inputOrder = std::min(osec->inputOrder, static_cast<int>(p.index()));
+  for (ConcatInputSection *isec : inputSections) {
+    if (isec->shouldOmitFromOutput())
+    ConcatOutputSection *&osec = concatOutputSections[names];
+    if (!osec)
+      osec = make<ConcatOutputSection>(names.second);
+    osec->addInput(isec);
+    osec->inputOrder =
+        std::min(osec->inputOrder, static_cast<int>(isec->outSecOff));
   }
 
   // Once all the inputs are added, we can finalize the output section
   // properties and create the corresponding output segments.
   for (const auto &it : concatOutputSections) {
     StringRef segname = it.first.first;
     ConcatOutputSection *osec = it.second;
-    if (segname == segment_names::ld) {
-      assert(osec->name == section_names::compactUnwind);
-      in.unwindInfo->setCompactUnwindSection(osec);
-    } else {
-      getOrCreateOutputSegment(segname)->addOutputSection(osec);
-    }
-  }
+    assert(segname != segment_names::ld);
 
   for (SyntheticSection *ssec : syntheticSections) {
     auto it = concatOutputSections.find({ssec->segname, ssec->name});
     if (ssec->isNeeded()) {
       if (it == concatOutputSections.end()) {
         getOrCreateOutputSegment(ssec->segname)->addOutputSection(ssec);
       } else {
         fatal("section from " + toString(it->second->firstSection()->file) +
               " conflicts with synthetic section " + ssec->segname + "," +
               ssec->name);
       }
     }
   }
 
   // dyld requires __LINKEDIT segment to always exist (even if empty).
   linkEditSegment = getOrCreateOutputSegment(segment_names::linkEdit);
 }
 
-void Writer::foldIdenticalLiterals() {
-  if (in.cStringSection)
-    in.cStringSection->finalizeContents();
-  // TODO: WordLiteralSection & CFStringSection should be finalized here too
-}
-
-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<ConcatInputSection *> 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 (auto *concatIsec = dyn_cast<ConcatInputSection>(isec)) {
-      if (concatIsec->isHashableForICF(isec->parent == textOutputSection))
-        hashable.push_back(concatIsec);
-      else
-        concatIsec->icfEqClass[0] = ++icfUniqueID;
-    }
-  }
-  // FIXME: hash literal sections here too?
-  parallelForEach(hashable,
-                  [](ConcatInputSection *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>();
-  // ICF assumes that all literals have been folded already, so we must run
-  // foldIdenticalLiterals before foldIdenticalSections.
-  foldIdenticalLiterals();
-  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();