[lld/mac] Set branchRange a bit more carefully

[thakis]

Summary

• Don't subtract thunkSize from branchRange. Most places care about the actual maximal branch range. Subtract thunkSize in the one place that wants to leave room for a thunk.
• Set it to 0x800_0000 instead of 0xFF_FFFF
• Subtract 4 for the positive branch direction since it's a two's complement 24bit number sign-extended mutiplied by 4, so its range is -0x800_0000..+0x7FF_FFFC
• Make boundary checks include the boundary values

This doesn't make a huge difference in practice. It's preparation
for a "real" fix for PR51578 -- but it also lets the repro in comment 0
in that bug place one more thunk before hitting the TODO.

[thakis]

lld/MachO/ConcatOutputSection.cpp

167

I don't understand the !tp.first->isInStubs() check here btw – a jump to an import stub might still require a thunk if the stub is towards the end of the stubs table and the stubs table is large, no?

(I mean, the whole thing here is an over-estimate so in practice it should be fine, but is there something I'm missing here?)

259–261

(See also AArch64::inBranchRange in lld/ELF/Arch/AArch64.cpp)

[tschuett]

lld/MachO/ConcatOutputSection.cpp

259–261

Do you have something with more information than a 4. Maybe sizeof() or a named constant?

[thakis]

lld/MachO/ConcatOutputSection.cpp

259–261

It's really just 1 * 4 in simplified. The range of a two's complement number is -2^n..(2^n - 1), and the call offset is multiplied by 4 to get more range (since function start addresses are required to be 4-aligned on arm64).

[int3]

lld/MachO/Arch/ARM64.cpp

137–143

nit: 1 << 28 would be clearer imo

lld/MachO/ConcatOutputSection.cpp

178

I think the size of the stubs table is factored in here

259–261

the literal constant thing doesn't bother me, but I'm bothered that this is arm64 logic leaking out into generic ConcatOutputSection code. I guess the issue is that the max forward branch range is different from the max backward branch range. How about having forwardBranchRange and backwardBranchRange instead?

[thakis]

forwardBranchRange / backwardBranchRange

lld/MachO/ConcatOutputSection.cpp

178

The size of the stubs table yes, but not the size of of thunks needed to reach it as far as I understand. For example:

f:
  b stubFun40
  b stubFun39
  ret
g:
  .fill X MB
  ret
stubTable:
  ...40 entries stubFun1, stubFun2, ...

Where X is chosen so that you can jump until stubFun39 from the start of f without a thunk. That means we'll finalize f and g, and after g is finalized, call this estimateStubsInRange() function, and then process the relocations in f. maxPotentialThunks is 0 since there are only stub calls in this program. So we set stubsInRangeVA at the address of the 2nd b in f. But now we process the first b, realize it needs a thunk (since it's before stubsInRangeVA), which means we insert that thunk after g before the stubs table. But that shifts the stub table 12 bytes further back, which means the b to stubFun39 is now no longer in range, even though according to stubsInRangeVA still thinks it is.

(Right?)

From what I understand, that's what maxPotentialThunks is designed to prevent, but it doesn't count stub calls.

259–261

Oh, you mean because it's a 4 instead of a 1? That's a good point.

But it's also a bit awkward since it suggests we support a setup where forward and backward jumps support meaningfully different ranges, and we need to check min() of both branch ranges etc. But maybe it's good to be explicit about that.

Done.

[int3]

lgtm

lld/MachO/Arch/ARM64.cpp

137–144

would be nice to have a comment explaining the - 4

lld/MachO/ConcatOutputSection.cpp

178

oh gotcha. yeah, I think you're right

[thakis]

Thanks!

[thakis]

lld/MachO/ConcatOutputSection.cpp

178

Made https://reviews.llvm.org/D108924 for this then :)

lld/MachO/Arch/ARM64.cpp

 }
 
 ARM64::ARM64() : ARM64Common(LP64()) {
   cpuType = CPU_TYPE_ARM64;
   cpuSubtype = CPU_SUBTYPE_ARM64_ALL;
 
   stubSize = sizeof(stubCode);
   thunkSize = sizeof(thunkCode);
-  branchRange = maxIntN(28) - thunkSize;
+
+  // Branch immediate is two's complement 26 bits, which is implicitly
+  // multiplied by 4 (since all functions are 4-aligned: The branch range
+  // is -4*(2**(26-1))..4*(2**(26-1) - 1).
+  backwardBranchRange = 128 * 1024 * 1024;
+  forwardBranchRange = backwardBranchRange - 4;
+
   stubHelperHeaderSize = sizeof(stubHelperHeaderCode);
   stubHelperEntrySize = sizeof(stubHelperEntryCode);
 }
 
 TargetInfo *macho::createARM64TargetInfo() {
   static ARM64 t;
   return &t;
 }

lld/MachO/ConcatOutputSection.cpp

 // thunks for programs so large that branch source & destination addresses
 // might differ more than the range of branch instruction(s).
 bool ConcatOutputSection::needsThunks() const {
   if (!target->usesThunks())
     return false;
   uint64_t isecAddr = addr;
   for (InputSection *isec : inputs)
     isecAddr = alignTo(isecAddr, isec->align) + isec->getSize();
-  if (isecAddr - addr + in.stubs->getSize() <= target->branchRange)
+  if (isecAddr - addr + in.stubs->getSize() <=
+      std::min(target->backwardBranchRange, target->forwardBranchRange))
     return false;
   // Yes, this program is large enough to need thunks.
   for (InputSection *isec : inputs) {
     for (Reloc &r : isec->relocs) {
       if (!target->hasAttr(r.type, RelocAttrBits::BRANCH))
         continue;
       auto *sym = r.referent.get<Symbol *>();
       // Pre-populate the thunkMap and memoize call site counts for every
for (InputSection *isec : inputs) {
     }
   }
   return true;
 }
 
 // Since __stubs is placed after __text, we must estimate the address
 // beyond which stubs are within range of a simple forward branch.
 uint64_t ConcatOutputSection::estimateStubsInRangeVA(size_t callIdx) const {
-  uint64_t branchRange = target->branchRange;
   size_t endIdx = inputs.size();
   ConcatInputSection *isec = inputs[callIdx];
   uint64_t isecVA = isec->getVA();
   // Tally the non-stub functions which still have call sites
   // remaining to process, which yields the maximum number
   // of thunks we might yet place.
   size_t maxPotentialThunks = 0;
   for (auto &tp : thunkMap) {
     ThunkInfo &ti = tp.second;
     maxPotentialThunks +=
         !tp.first->isInStubs() && ti.callSitesUsed < ti.callSiteCount;
   }
   // Tally the total size of input sections remaining to process.
   uint64_t isecEnd = isec->getVA();
   for (size_t i = callIdx; i < endIdx; i++) {
     InputSection *isec = inputs[i];
     isecEnd = alignTo(isecEnd, isec->align) + isec->getSize();
   }
   // Estimate the address after which call sites can safely call stubs
   // directly rather than through intermediary thunks.
+  uint64_t forwardBranchRange = target->forwardBranchRange;
   uint64_t stubsInRangeVA = isecEnd + maxPotentialThunks * target->thunkSize +
-                            in.stubs->getSize() - branchRange;
+                            in.stubs->getSize() - forwardBranchRange;
   log("thunks = " + std::to_string(thunkMap.size()) +
       ", potential = " + std::to_string(maxPotentialThunks) +
       ", stubs = " + std::to_string(in.stubs->getSize()) + ", isecVA = " +
       to_hexString(isecVA) + ", threshold = " + to_hexString(stubsInRangeVA) +
       ", isecEnd = " + to_hexString(isecEnd) +
       ", tail = " + to_hexString(isecEnd - isecVA) +
-      ", slop = " + to_hexString(branchRange - (isecEnd - isecVA)));
+      ", slop = " + to_hexString(forwardBranchRange - (isecEnd - isecVA)));
   return stubsInRangeVA;
 }
 
 void ConcatOutputSection::finalize() {
   uint64_t isecAddr = addr;
   uint64_t isecFileOff = fileOff;
   auto finalizeOne = [&](ConcatInputSection *isec) {
     isecAddr = alignTo(isecAddr, isec->align);
     isecFileOff = alignTo(isecFileOff, isec->align);
     isec->outSecOff = isecAddr - addr;
     isec->isFinal = true;
     isecAddr += isec->getSize();
     isecFileOff += isec->getFileSize();
   };
 
   if (!needsThunks()) {
     for (ConcatInputSection *isec : inputs)
       finalizeOne(isec);
     size = isecAddr - addr;
     fileSize = isecFileOff - fileOff;
     return;
   }
 
-  uint64_t branchRange = target->branchRange;
+  uint64_t forwardBranchRange = target->forwardBranchRange;
+  uint64_t backwardBranchRange = target->backwardBranchRange;
   uint64_t stubsInRangeVA = TargetInfo::outOfRangeVA;
   size_t thunkSize = target->thunkSize;
   size_t relocCount = 0;
   size_t callSiteCount = 0;
   size_t thunkCallCount = 0;
   size_t thunkCount = 0;
 
   // inputs[finalIdx] is for finalization (address-assignment)
   size_t finalIdx = 0;
   // Kick-off by ensuring that the first input section has an address
   for (size_t callIdx = 0, endIdx = inputs.size(); callIdx < endIdx;
        ++callIdx) {
     if (finalIdx == callIdx)
       finalizeOne(inputs[finalIdx++]);
     ConcatInputSection *isec = inputs[callIdx];
     assert(isec->isFinal);
     uint64_t isecVA = isec->getVA();
     // Assign addresses up-to the forward branch-range limit
-    while (finalIdx < endIdx &&
-           isecAddr + inputs[finalIdx]->getSize() < isecVA + branchRange)
+    while (finalIdx < endIdx && isecAddr + inputs[finalIdx]->getSize() <
+                                    isecVA + forwardBranchRange - thunkSize)
       finalizeOne(inputs[finalIdx++]);
     if (isec->callSiteCount == 0)
       continue;
     if (finalIdx == endIdx && stubsInRangeVA == TargetInfo::outOfRangeVA) {
       // When we have finalized all input sections, __stubs (destined
       // to follow __text) comes within range of forward branches and
       // we can estimate the threshold address after which we can
       // reach any stub with a forward branch. Note that although it
assert(is_sorted(relocs,
                      [](Reloc &a, Reloc &b) { return a.offset > b.offset; }));
     for (Reloc &r : reverse(relocs)) {
       ++relocCount;
       if (!target->hasAttr(r.type, RelocAttrBits::BRANCH))
         continue;
       ++callSiteCount;
       // Calculate branch reachability boundaries
       uint64_t callVA = isecVA + r.offset;
-      uint64_t lowVA = branchRange < callVA ? callVA - branchRange : 0;
-      uint64_t highVA = callVA + branchRange;
+      uint64_t lowVA =
+          backwardBranchRange < callVA ? callVA - backwardBranchRange : 0;
+      uint64_t highVA = callVA + forwardBranchRange;
       // Calculate our call referent address
       auto *funcSym = r.referent.get<Symbol *>();
       ThunkInfo &thunkInfo = thunkMap[funcSym];
       // The referent is not reachable, so we need to use a thunk ...
       if (funcSym->isInStubs() && callVA >= stubsInRangeVA) {
         // ... Oh, wait! We are close enough to the end that __stubs
         // are now within range of a simple forward branch.
         continue;
       }
       uint64_t funcVA = funcSym->resolveBranchVA();
       ++thunkInfo.callSitesUsed;
-      if (lowVA < funcVA && funcVA < highVA) {
+      if (lowVA <= funcVA && funcVA <= highVA) {
         // The referent is reachable with a simple call instruction.
         continue;
       }
       ++thunkInfo.thunkCallCount;
       ++thunkCallCount;
       // If an existing thunk is reachable, use it ...
       if (thunkInfo.sym) {
         uint64_t thunkVA = thunkInfo.isec->getVA();
-        if (lowVA < thunkVA && thunkVA < highVA) {
+        if (lowVA <= thunkVA && thunkVA <= highVA) {
           r.referent = thunkInfo.sym;
           continue;
         }
       }
       // ... otherwise, create a new thunk
       if (isecAddr > highVA) {
         // When there is small-to-no margin between highVA and
         // isecAddr and the distance between subsequent call sites is

lld/MachO/Target.h

public:
   uint64_t pageZeroSize;
   size_t headerSize;
   size_t stubSize;
   size_t stubHelperHeaderSize;
   size_t stubHelperEntrySize;
   size_t wordSize;
 
   size_t thunkSize = 0;
-  uint64_t branchRange = 0;
+  uint64_t forwardBranchRange = 0;
+  uint64_t backwardBranchRange = 0;
 
   // We contrive this value as sufficiently far from any valid address that it
   // will always be out-of-range for any architecture. UINT64_MAX is not a
   // good choice because it is (a) only 1 away from wrapping to 0, and (b) the
   // tombstone value for DenseMap<> and caused weird assertions for me.
   static constexpr uint64_t outOfRangeVA = 0xfull << 60;
 };