[lld/mac] Tweak estimateStubsInRangeVA a bit

[thakis]

Summary

• Move a few variables closer to their uses, remove some completely (no behavior change)
• Add some comments
• Make maxPotentialThunks include calls to stubs. It's possible that an earlier call to a stub late in the stub table will need a thunk, and that inserted thunk could push a stub earlier in the stub table out of range. This is unlikely to happen, but usually there are way fewer stub calls than non-stub calls, so if we're doing a conservative approximation here we might as well do it correctly. (For chromium's unit_tests target, 134421/242639 stub calls are direct calls without this change, compared to 134408/242639 with this change)

No real, meaningful behavior difference.

[oontvoo]

lld/MachO/ConcatOutputSection.cpp

173–176

I must be missing something here but why does this need to be a loop and not simply

if (callIdx < inputs.size()) {
  InputSection *isec = inputs.last();
   secEnd = alignTo(isecEnd, isec->align) + isec->getSize();
}

IOWs, isecEnd seems to get overridden in each iteration, yes?

[thakis]

lld/MachO/ConcatOutputSection.cpp

173–176

Yes, this computes the end address of all sections. After the loop, isecEndpoints right after where the last section would end up, assuming we don't insert thunk sections anywhere along the way.

[int3]

thanks!

lld/MachO/ConcatOutputSection.cpp

173–176

It's a loop since it's summing the aligned sizes

[oontvoo]

lld/MachO/ConcatOutputSection.cpp

173–176

Thanks :)
i shouldn't have done reviews on monday before☕

lld/MachO/ConcatOutputSection.cpp

 //
 // (2) Thunks: Instruction(s) to load the destination address into a scratch
 //     register, followed by a register-indirect branch. Thunks are
 //     constructed to reach any arbitrary address, so need not be
 //     chained. Although thunks need not be chained, a program might need
 //     multiple thunks to the same destination distributed throughout a large
 //     program so that all call sites can have one within range.
 //
-// The optimal approach is to mix islands for distinations within two hops,
+// The optimal approach is to mix islands for destinations within two hops,
 // and use thunks for destinations at greater distance. For now, we only
 // implement thunks. TODO: Adding support for branch islands!
 //
 // Internally -- as expressed in LLD's data structures -- a
 // branch-range-extension thunk comprises ...
 //
 // (1) new Defined privateExtern symbol for the thunk named
 //     <FUNCTION>.thunk.<SEQUENCE>, which references ...
for (Reloc &r : isec->relocs) {
         continue;
       auto *sym = r.referent.get<Symbol *>();
       // Pre-populate the thunkMap and memoize call site counts for every
       // InputSection and ThunkInfo. We do this for the benefit of
       // ConcatOutputSection::estimateStubsInRangeVA()
       ThunkInfo &thunkInfo = thunkMap[sym];
       // Knowing ThunkInfo call site count will help us know whether or not we
       // might need to create more for this referent at the time we are
-      // estimating distance to __stubs in .
+      // estimating distance to __stubs in estimateStubsInRangeVA().
       ++thunkInfo.callSiteCount;
       // Knowing InputSection call site count will help us avoid work on those
       // that have no BRANCH relocs.
       ++isec->callSiteCount;
     }
   }
   return true;
 }
 
 // Since __stubs is placed after __text, we must estimate the address
 // beyond which stubs are within range of a simple forward branch.
+// This is called exactly once, when the last input section has been finalized.
 uint64_t ConcatOutputSection::estimateStubsInRangeVA(size_t callIdx) const {
-  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.
+  // Tally the 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;
+    // This overcounts: Only sections that are in forward jump range from the
+    // currently-active section get finalized, and all input sections are
+    // finalized when estimateStubsInRangeVA() is called. So only backward
+    // jumps will need thunks, but we count all jumps.
+    if (ti.callSitesUsed < ti.callSiteCount)
+      maxPotentialThunks += 1;
   }
   // Tally the total size of input sections remaining to process.
-  uint64_t isecEnd = isec->getVA();
-  for (size_t i = callIdx; i < endIdx; i++) {
+  uint64_t isecVA = inputs[callIdx]->getVA();
+  uint64_t isecEnd = isecVA;
+  for (size_t i = callIdx; i < inputs.size(); 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;
+  assert(isecEnd > forwardBranchRange &&
+         "should not run thunk insertion if all code fits in jump range");
+  assert(isecEnd - isecVA <= forwardBranchRange &&
+         "should only finalize sections in jump range");
   uint64_t stubsInRangeVA = isecEnd + maxPotentialThunks * target->thunkSize +
                             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) +
for (Reloc &r : reverse(relocs)) {
       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) {
+        assert(callVA != TargetInfo::outOfRangeVA);
         // ... 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) {
         // 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) {
           r.referent = thunkInfo.sym;
           continue;
         }
       }
-      // ... otherwise, create a new thunk
+      // ... 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
         // smaller than thunkSize, then a new thunk can go out of
         // range.  Fix by unfinalizing inputs[finalIdx] to reduce the
         // distance between callVA and highVA, then shift some thunks
         // to occupy address-space formerly occupied by the
         // unfinalized inputs[finalIdx].