[MachO] Shrink reloc from 32 bytes to 24 bytes

[smeenai]

Summary

The r_address field of relocation_info is only 4 bytes, so our
offset field (which is the r_address field adjusted for subsection
splitting) also only needs to be 4 bytes. This reduces the structure
size from 32 bytes to 24 bytes.

Combined with https://reviews.llvm.org/D113813, this is a minor perf
improvement for linking an internal app, tested on two machines:

           smol-relocs     baseline        difference (95% CI)
sys_time   7.367 ± 0.138   7.543 ± 0.157   [  +0.9% ..   +3.8%]
user_time  21.843 ± 0.351  21.861 ± 0.450  [  -1.3% ..   +1.4%]
wall_time  20.301 ± 0.307  20.556 ± 0.324  [  +0.1% ..   +2.4%]
samples    16              16

           smol-relocs     baseline        difference (95% CI)
sys_time   2.923 ± 0.050   2.992 ± 0.018   [  +1.4% ..   +3.4%]
user_time  10.345 ± 0.039  10.448 ± 0.023  [  +0.8% ..   +1.2%]
wall_time  12.068 ± 0.071  12.229 ± 0.021  [  +1.0% ..   +1.7%]
samples    15              12

More importantly though, this change by itself reduces our maximum
resident set size by 220 MB (2.75%, from 7.85 GB to 7.64 GB) on the
first machine. On the second machine, it reduces it by 125 MB (1.94%,
from 6.31 GB to 6.19 GB).

[smeenai]

Turning findContainingSubsection into a template is a little ugly, but there's legitimate cases where the offset can be 64 bits (e.g. embedded addends for relocations), so we need to support both uint32_t * and uint64_t * arguments.

If reviewers prefer, I could instead make findContainingSubsection take the InputSection * as the output argument and return the adjusted offset, so that the return value can just be downcast instead of needing a template.

[int3]

from 7.85 MB to 7.64 MB

I think you meant GB :)

lld/MachO/InputFiles.cpp

355

hm, can't we leave it as uint64_t and have the uint32_t be automatically promoted?

[smeenai]

In D113818#3128844, @int3 wrote:

from 7.85 MB to 7.64 MB

I think you meant GB :)

Hah, fixed.

lld/MachO/InputFiles.cpp

355

Promotion doesn't happen for pointer arguments (you wouldn't wanna write 8 bytes into a 4 byte storage slot).

[int3]

Thanks!

lld/MachO/InputFiles.cpp

355

OH right. I knew that, I just couldn't read :P

If reviewers prefer, I could instead make findContainingSubsection take the InputSection * as the output argument and return the adjusted offset, so that the return value can just be downcast instead of needing a template.

Nah this seems ugly in a different way, findFoo functions should generally return Foos...

Maybe add a comment here that we expect T to be either uint32_t or uint64_t?

[smeenai]

lld/MachO/InputFiles.cpp

355

I was gonna add a type assert but screwed up my push; whoops. @oontvoo fixed that in D114044; thank you!

lld/MachO/InputFiles.cpp

 
 // Find the subsection corresponding to the greatest section offset that is <=
 // that of the given offset.
 //
 // offset: an offset relative to the start of the original InputSection (before
 // any subsection splitting has occurred). It will be updated to represent the
 // same location as an offset relative to the start of the containing
 // subsection.
-static InputSection *findContainingSubsection(SubsectionMap &map,
-                                              uint64_t *offset) {
+template <class T>
+static InputSection *findContainingSubsection(SubsectionMap &map, T *offset) {
   auto it = std::prev(llvm::upper_bound(
       map, *offset, [](uint64_t value, SubsectionEntry subsecEntry) {
         return value < subsecEntry.offset;
       }));
   *offset -= it->offset;
   return it->isec;
 }
 

lld/MachO/Relocations.h

 };
 
 struct Reloc {
   uint8_t type = llvm::MachO::GENERIC_RELOC_INVALID;
   bool pcrel = false;
   uint8_t length = 0;
   // The offset from the start of the subsection that this relocation belongs
   // to.
-  uint64_t offset = 0;
+  uint32_t offset = 0;
   // Adding this offset to the address of the referent symbol or subsection
   // gives the destination that this relocation refers to.
   int64_t addend = 0;
   llvm::PointerUnion<Symbol *, InputSection *> referent = nullptr;
 };
 
+static_assert(sizeof(void *) != 8 || sizeof(Reloc) == 24,
+              "Try to minimize Reloc's size; we create many instances");
+
 bool validateSymbolRelocation(const Symbol *, const InputSection *,
                               const Reloc &);
 
 /*
  * v: The value the relocation is attempting to encode
  * bits: The number of bits actually available to encode this relocation
  */
 void reportRangeError(const Reloc &, const llvm::Twine &v, uint8_t bits,