[lld-macho] Move ICF members from InputSection to ConcatInputSection

[int3]

Summary

icfEqClass only makes sense on ConcatInputSections since (in contrast
to literal sections) they are deduplicated as an atomic unit.

Similarly, hasPersonality and replacement don't make sense on
literal sections.

This mirrors LLD-ELF, which stores icfEqClass only on non-mergeable
sections.

[gkm]

Bueno!

lld/MachO/ICF.cpp

138

212

lld/MachO/InputSection.cpp

65

lld/MachO/UnwindInfoSection.cpp

156

lld/MachO/Writer.cpp

970

[int3]

address comments

lld/MachO/ICF.cpp

if (ra.referent.is<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())
+        if (da->isAbsolute() != db->isAbsolute())
           return false;
-        if (da->isec)
-          if (da->isec->icfEqClass[icfPass % 2] !=
-              db->isec->icfEqClass[icfPass % 2])
+        if (da->isec) {
+          if (da->isec->kind() != db->isec->kind())
             return false;
+          if (const auto *isecA = dyn_cast<ConcatInputSection>(da->isec)) {
+            const auto *isecB = cast<ConcatInputSection>(db->isec);
+            if (isecA->icfEqClass[icfPass % 2] !=
+                isecB->icfEqClass[icfPass % 2])
+              return false;
+          } else {
+            // FIXME: implement ICF for other InputSection kinds
+            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])
+      if (sa->kind() != sb->kind())
+        return false;
+      if (const auto *isecA = dyn_cast<ConcatInputSection>(sa)) {
+        const auto *isecB = cast<ConcatInputSection>(sb);
+        if (isecB->icfEqClass[icfPass % 2] != isecB->icfEqClass[icfPass % 2])
           return false;
+      } else {
+        // FIXME: implement ICF for other InputSection kinds
+        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
parallelForEachN(1, shards + 1, [&](size_t i) {
     }
   });
   ++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) {
+    parallelForEach(icfInputs, [&](ConcatInputSection *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
+          else if (auto *defined = dyn_cast<Defined>(sym)) {
+            hash += defined->value;
+            if (defined->isec)
+              if (auto isec = cast<ConcatInputSection>(defined->isec))
+                hash += isec->icfEqClass[icfPass % 2];
+            // FIXME: implement ICF for other InputSection kinds
+          } 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];
-                    });
+  llvm::stable_sort(
+      icfInputs, [](const ConcatInputSection *a, const ConcatInputSection *b) {
   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);

lld/MachO/InputSection.h

public:
   // Translates \p off -- an offset relative to this InputSection -- into an
   // offset from the beginning of its parent OutputSection.
   virtual uint64_t getOffset(uint64_t off) const = 0;
   // The offset from the beginning of the file.
   uint64_t getVA(uint64_t off) const;
   // Whether the data at \p off in this InputSection is live.
   virtual bool isLive(uint64_t off) const = 0;
   virtual void markLive(uint64_t off) = 0;
+  virtual InputSection *canonical() { return this; }
 
   InputFile *file = nullptr;
   StringRef name;
   StringRef segname;
 
   OutputSection *parent = nullptr;
 
   uint32_t align = 1;
   uint32_t flags = 0;
   uint32_t callSiteCount = 0;
 
   // 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) {}
 
   InputSection(Kind kind, StringRef segname, StringRef name, InputFile *file,
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;
+  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;
   }
 
-  void foldIdentical(ConcatInputSection *redundant);
+  // 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;

lld/MachO/InputSection.cpp

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;
+bool ConcatInputSection::isHashableForICF(bool isText) const {
+  if (shouldOmitFromOutput())
   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;
+    // FIXME(jezng): We should have any ConcatInputSections of these types when
+    // running ICF.
+    return false;
   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() {
+void ConcatInputSection::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) {

lld/MachO/UnwindInfoSection.cpp

for (size_t i = 0; i < isec->relocs.size(); ++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;
+    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;
       }

lld/MachO/Writer.cpp

void Writer::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 a simple vector.
-  std::vector<InputSection *> hashable;
+  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 (isec->isHashableForICF(isec->parent == textOutputSection))
-      hashable.push_back(isec);
+    if (auto concatIsec = dyn_cast<ConcatInputSection>(isec)) {
+      if (concatIsec->isHashableForICF(isec->parent == textOutputSection))
+        hashable.push_back(concatIsec);
       else
-      isec->icfEqClass[0] = ++icfUniqueID;
+        concatIsec->icfEqClass[0] = ++icfUniqueID;
     }
-  parallelForEach(hashable, [](InputSection *isec) { isec->hashForICF(); });
+    // FIXME: hash literal sections here?
+  }
+  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));