[lld-macho] ICF: Do more work in equalsConstant, less in equalsVariable

[int3]

Summary

In particular, relocations to absolute symbols or literal sections can
be handled in equalsConstant(), since their output addresses will not
change across each iteration of ICF. Offsets and addends can also be
dealt with entirely in equalsConstant(), making the code somewhat easier
to reason about. Only ConcatInputSections need to be handled in
equalsVariable().

LLD-ELF's implementation takes a similar approach.

Although this should make ICF do less work, in practice it seems like
there is no stat sig difference in time taken when linking
chromium_framework.

This refactor is motivated by an upcoming diff which improves ICF's handling of
addends.

[gkm]

Bueno!

lld/MachO/ICF.cpp

 // 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
+// Compare "non-moving" parts of two ConcatInputSections, namely everything
+// except references to other ConcatInputSections.
 static bool equalsConstant(const ConcatInputSection *ia,
                            const ConcatInputSection *ib) {
   // We can only fold within the same OutputSection.
   if (ia->parent != ib->parent)
     return false;
   if (ia->data.size() != ib->data.size())
     return false;
   if (ia->data != ib->data)
     return false;
   if (ia->relocs.size() != ib->relocs.size())
     return false;
-  auto f = [&](const Reloc &ra, const Reloc &rb) {
+  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);
-}
+      return false;
 
-// 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;
+    InputSection *isecA, *isecB;
     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);
+        const auto *da = cast<Defined>(sa);
+        const auto *db = cast<Defined>(sb);
         if (da->isec && db->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);
-            return da->value == db->value && isecA->icfEqClass[icfPass % 2] ==
-                                                 isecB->icfEqClass[icfPass % 2];
-          }
-          // Else we have two literal sections. References to them are
-          // constant-equal if their offsets in the output section are equal.
-          return da->isec->parent == db->isec->parent &&
-                 da->isec->getOffset(da->value) ==
-                     db->isec->getOffset(db->value);
-        }
+          isecA = da->isec;
+          isecB = db->isec;
+        } else {
           assert(da->isAbsolute() && db->isAbsolute());
           return da->value == db->value;
-      } 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");
+        assert(isa<DylibSymbol>(sa));
+        return sa == sb;
       }
     } else {
-      const auto *sa = ra.referent.get<InputSection *>();
-      const auto *sb = rb.referent.get<InputSection *>();
-      if (sa->kind() != sb->kind())
-        return false;
-      if (const auto *isecA = dyn_cast<ConcatInputSection>(sa)) {
-        const auto *isecB = cast<ConcatInputSection>(sb);
-        return isecA->icfEqClass[icfPass % 2] == isecB->icfEqClass[icfPass % 2];
-      } else {
-        assert(isa<CStringInputSection>(sa) ||
-               isa<WordLiteralInputSection>(sa));
-        return sa->getOffset(ra.addend) == sb->getOffset(rb.addend);
-      }
+      isecA = ra.referent.get<InputSection *>();
+      isecB = rb.referent.get<InputSection *>();
+    }
+
+    if (isecA->parent != isecB->parent)
+    // Sections with identical parents should be of the same kind.
+    assert(isecA->kind() == isecB->kind());
+    // We will compare ConcatInputSection contents in equalsVariable.
+    if (isa<ConcatInputSection>(isecA))
+      return true;
+    // Else we have two literal sections. References to them are equal iff their
+    // offsets in the output section are equal.
+    return isecA->getOffset(ra.addend) == isecB->getOffset(rb.addend);
+  };
+  return std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(),
+                    f);
+
+// Compare the "moving" parts of two ConcatInputSections -- i.e. everything not
+// handled by equalsConstant().
+static bool equalsVariable(const ConcatInputSection *ia,
+                           const ConcatInputSection *ib) {
+  assert(ia->relocs.size() == ib->relocs.size());
+  auto f = [](const Reloc &ra, const Reloc &rb) {
+    // We already filtered out mismatching values/addends in equalsConstant.
+    if (ra.referent == rb.referent)
+      return true;
+    const ConcatInputSection *isecA, *isecB;
+    if (ra.referent.is<Symbol *>()) {
+      // Matching DylibSymbols are already filtered out by the
+      // identical-referent check above. Non-matching DylibSymbols were filtered
+      // out in equalsConstant(). So we can safely cast to Defined here.
+      const auto *da = cast<Defined>(ra.referent.get<Symbol *>());
+      const auto *db = cast<Defined>(rb.referent.get<Symbol *>());
+      if (da->isAbsolute())
+        return true;
+      isecA = dyn_cast<ConcatInputSection>(da->isec);
+      if (!isecA)
+        return true; // literal sections were checked in equalsConstant.
+      isecB = cast<ConcatInputSection>(db->isec);
+    } else {
+      const auto *sa = ra.referent.get<InputSection *>();
+      const auto *sb = rb.referent.get<InputSection *>();
+      isecA = dyn_cast<ConcatInputSection>(sa);
+      if (!isecA)
+        return true;
+      isecB = cast<ConcatInputSection>(sb);
     }
+    return isecA->icfEqClass[icfPass % 2] == isecB->icfEqClass[icfPass % 2];
   };
   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];