[lld-macho][nfc] Track # of ICF calls to `equals*` methods

[int3]

Summary

This is debug code that is disabled by default. It'll provide a easy way
to figure out the impact (if any) of tweaking ICF's hashing algorithm
(since a poor quality hash will result in many more equals* calls).

[oontvoo]

LG

lld/MachO/ICF.cpp

26

nit:

lld/MachO/ICF.cpp

 #include "llvm/Support/xxhash.h"
 
 #include <atomic>
 
 using namespace llvm;
 using namespace lld;
 using namespace lld::macho;
 
+static constexpr bool verboseDiagnostics = false;
+
 class ICF {
 public:
   ICF(std::vector<ConcatInputSection *> &inputs);
   void run();
 
   using EqualsFn = bool (ICF::*)(const ConcatInputSection *,
                                  const ConcatInputSection *);
   void segregate(size_t begin, size_t end, EqualsFn);
   size_t findBoundary(size_t begin, size_t end);
   void forEachClassRange(size_t begin, size_t end,
                          llvm::function_ref<void(size_t, size_t)> func);
   void forEachClass(llvm::function_ref<void(size_t, size_t)> func);
 
   bool equalsConstant(const ConcatInputSection *ia,
                       const ConcatInputSection *ib);
   bool equalsVariable(const ConcatInputSection *ia,
                       const ConcatInputSection *ib);
 
   // ICF needs a copy of the inputs vector because its equivalence-class
   // segregation algorithm destroys the proper sequence.
   std::vector<ConcatInputSection *> icfInputs;
 
   unsigned icfPass = 0;
   std::atomic<bool> icfRepeat{false};
+  std::atomic<uint64_t> equalsConstantCount{0};
+  std::atomic<uint64_t> equalsVariableCount{0};
 };
 
 ICF::ICF(std::vector<ConcatInputSection *> &inputs) {
   icfInputs.assign(inputs.begin(), inputs.end());
 }
 
 // ICF = Identical Code Folding
 //

 //
 // FIXME(gkm): implement keep-unique attributes
 // FIXME(gkm): implement address-significance tables for MachO object files
 
 // Compare "non-moving" parts of two ConcatInputSections, namely everything
 // except references to other ConcatInputSections.
 bool ICF::equalsConstant(const ConcatInputSection *ia,
                          const ConcatInputSection *ib) {
+  if (verboseDiagnostics)
+    ++equalsConstantCount;
   // 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())
bool ICF::equalsConstant(const ConcatInputSection *ia,
   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().
 bool ICF::equalsVariable(const ConcatInputSection *ia,
                          const ConcatInputSection *ib) {
+  if (verboseDiagnostics)
+    ++equalsVariableCount;
   assert(ia->relocs.size() == ib->relocs.size());
   auto f = [this](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
void ICF::run() {
   // Split equivalence groups by comparing relocations until convergence
   do {
     icfRepeat = false;
     forEachClass([&](size_t begin, size_t end) {
       segregate(begin, end, &ICF::equalsVariable);
     });
   } while (icfRepeat);
   log("ICF needed " + Twine(icfPass) + " iterations");
+  if (verboseDiagnostics) {
+    log("equalsConstant() called " + Twine(equalsConstantCount) + " times");
+    log("equalsVariable() called " + Twine(equalsVariableCount) + " times");
+  }
 
   // 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]);