[lld-macho][nfc] Reduce size of icfEqClass hash

[int3]

Summary

... from a uint64_t to a uint32_t. (LLD-ELF uses a uint32_t too.)

About a 1.7% reduction in peak RSS when linking chromium_framework on my
3.2 GHz 16-Core Intel Xeon W Mac Pro, and no stat sig change in wall
time.

         </Users/jezng/test2.sh ["before"]>  </Users/jezng/test2.sh ["after"]>  difference (95% CI)
RSS      1003036672.000 ± 9891065.259        985539505.231 ± 10272748.749       [  -2.3% ..   -1.2%]
samples  27                                  26

           base           diff           difference (95% CI)
sys_time   1.277 ± 0.023  1.277 ± 0.024  [  -0.9% ..   +0.9%]
user_time  6.682 ± 0.046  6.598 ± 0.043  [  -1.6% ..   -0.9%]
wall_time  5.904 ± 0.062  5.895 ± 0.063  [  -0.7% ..   +0.4%]
samples    46             28

No appreciable change (~0.01%) in number of equals comparisons either:

Before:

ld64.lld: ICF needed 8 iterations
ld64.lld: equalsConstant() called 701643 times
ld64.lld: equalsVariable() called 3438526 times

After:

ld64.lld: ICF needed 8 iterations
ld64.lld: equalsConstant() called 701729 times
ld64.lld: equalsVariable() called 3438526 times

[thakis]

lld/MachO/ICF.cpp

280–281

what happened to the dylibSym branch?

283–285

if you want to rename this variable (why?), do that in a separate commit (doesn't need a review)

[MaskRay]

LGTM barring the comment. You may want to change std::vector<Reloc> to SmallVector<Reloc, 0> to make it smaller.

[int3]

both the changes you commented on were accidentally included in this diff... will split them out

lld/MachO/ICF.cpp

280–281

oops, I didn't intend to fold that change into this commit. I'll commit this separately

but as for the rationale... the existing hashing of stubsHelperIndex is actually a no-op because ICF runs before dylib symbols get their stubs index assigned. I guess we could consider hashing the name + filename of the DylibSymbol instead, but I'm not sure the overhead's worth it... also LLD/ELF only hashes their Defined symbols as well.

[int3]

lld/MachO/ICF.cpp

283–285

why?

It's shadowing the isec defined on line 275, which I found a bit confusing to read

[int3]

split out unrelated changes

[thakis]

thanks!

[int3]

You may want to change std::vector<Reloc> to SmallVector<Reloc, 0> to make it smaller.

Good idea! I'll benchmark it in a separate diff.

[thakis]

lld/MachO/ICF.cpp

375

Should this be a uint32_t now? (doesn't matter in practice; I just found it confusing when I was reading the code just now)

[int3]

lld/MachO/ICF.cpp

375

yep, forgot to change this

lld/MachO/ICF.cpp

void ICF::forEachClass(llvm::function_ref<void(size_t, size_t)> func) {
   });
   ++icfPass;
 }
 
 void ICF::run() {
   // Into each origin-section hash, combine all reloc referent section hashes.
   for (icfPass = 0; icfPass < 2; ++icfPass) {
     parallelForEach(icfInputs, [&](ConcatInputSection *isec) {
-      uint64_t hash = isec->icfEqClass[icfPass % 2];
+      uint32_t hash = isec->icfEqClass[icfPass % 2];
       for (const Reloc &r : isec->relocs) {
         if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
           if (auto *defined = dyn_cast<Defined>(sym)) {
             if (defined->isec) {
               if (auto referentIsec =
                       dyn_cast<ConcatInputSection>(defined->isec))
                 hash += defined->value + referentIsec->icfEqClass[icfPass % 2];
               else
                 hash += defined->isec->kind() +
                         defined->isec->getOffset(defined->value);
             } else {
               hash += defined->value;
             }
           } else if (!isa<Undefined>(sym)) { // ICF runs before Undefined diags
             llvm_unreachable("foldIdenticalSections symbol kind");
           }
         }
       }
       // Set MSB to 1 to avoid collisions with non-hashed classes.
-      isec->icfEqClass[(icfPass + 1) % 2] = hash | (1ull << 63);
+      isec->icfEqClass[(icfPass + 1) % 2] = hash | (1ull << 31);
     });
   }
 
   llvm::stable_sort(
       icfInputs, [](const ConcatInputSection *a, const ConcatInputSection *b) {
         return a->icfEqClass[0] < b->icfEqClass[0];
       });
   forEachClass([&](size_t begin, size_t end) {
void macho::foldIdenticalSections() {
   // 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()
   std::vector<ConcatInputSection *> hashable;
   uint64_t icfUniqueID = inputSections.size();
   for (ConcatInputSection *isec : inputSections) {
     // FIXME: consider non-code __text sections as hashable?
     bool isHashable = (isCodeSection(isec) || isCfStringSection(isec)) &&
                       !isec->shouldOmitFromOutput() &&
                       sectionType(isec->getFlags()) == MachO::S_REGULAR;
     if (isHashable) {
       hashable.push_back(isec);
       for (Defined *d : isec->symbols)
         if (d->unwindEntry)
           hashable.push_back(d->unwindEntry);
     } else {
       isec->icfEqClass[0] = ++icfUniqueID;
     }
   }
   parallelForEach(hashable, [](ConcatInputSection *isec) {
     assert(isec->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
-    isec->icfEqClass[0] = xxHash64(isec->data) | (1ull << 63);
+    isec->icfEqClass[0] = xxHash64(isec->data) | (1ull << 31);
   });
   // Now that every input section is either hashed or marked as unique, run the
   // segregation algorithm to detect foldable subsections.
   ICF(hashable).run();
 }

lld/MachO/InputSection.h

public:
 
   static bool classof(const InputSection *isec) {
     return isec->kind() == ConcatKind;
   }
 
   // Points to the surviving section after this one is folded by ICF
   ConcatInputSection *replacement = nullptr;
   // Equivalence-class ID for ICF
-  uint64_t icfEqClass[2] = {0, 0};
+  uint32_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

 using namespace llvm::support;
 using namespace lld;
 using namespace lld::macho;
 
 // Verify ConcatInputSection's size on 64-bit builds. The size of std::vector
 // can differ based on STL debug levels (e.g. iterator debugging on MSVC's STL),
 // so account for that.
 static_assert(sizeof(void *) != 8 ||
-                  sizeof(ConcatInputSection) == sizeof(std::vector<Reloc>) + 96,
+                  sizeof(ConcatInputSection) == sizeof(std::vector<Reloc>) + 88,
               "Try to minimize ConcatInputSection's size, we create many "
               "instances of it");
 
 std::vector<ConcatInputSection *> macho::inputSections;
 
 uint64_t InputSection::getFileSize() const {
   return isZeroFill(getFlags()) ? 0 : getSize();
 }