[lld] Estimate think slope size instead of using a magic constant

[serge-sans-paille]

Summary

Historically, the slope size has been manually increased over time as
more code base bump into the "FIXME: thunk range overrun" fatal error.

This provides an adaptive approach where we first (over) estimate the
slope and then use it.

This should result in smaller slopes for the generic case, and large
enough slope in the limit case.

[int3]

I'm actually working on a fix for this issue right now. The current code fails to account for alignment, hence the overruns we see. Once that's fixed I think we can stay with the hardcoded slop size.

[int3]

D144029: [lld-macho] Account for alignment in thunk insertion algorithm

[serge-sans-paille]

Superseded by https://reviews.llvm.org/D144029

lld/MachO/ConcatOutputSection.h

public:
   explicit TextOutputSection(StringRef name) : ConcatOutputSection(name) {}
   void finalizeContents() override {}
   void finalize() override;
   bool needsThunks() const;
   void writeTo(uint8_t *buf) const override;
 
 private:
   uint64_t estimateStubsInRangeVA(size_t callIdx) const;
+  unsigned computeSlopUpperBound(const size_t finalIdx, const size_t endIdx,
+                                 const ConcatInputSection *isec,
+                                 const unsigned initialFactor = 64) const;
 
   std::vector<ConcatInputSection *> thunks;
 };
 
 // We maintain one ThunkInfo per real function.
 //
 // The "active thunk" is represented by the sym/isec pair that
 // turns-over during finalize(): as the call-site address advances,

lld/MachO/ConcatOutputSection.cpp

for (size_t callIdx = 0, endIdx = inputs.size(); callIdx < endIdx;
 
     // Assign addresses up-to the forward branch-range limit.
     // Every call instruction needs a small number of bytes (on Arm64: 4),
     // and each inserted thunk needs a slightly larger number of bytes
     // (on Arm64: 12). If a section starts with a branch instruction and
     // contains several branch instructions in succession, then the distance
     // from the current position to the position where the thunks are inserted
     // grows. So leave room for a bunch of thunks.
-    unsigned slop = 1024 * thunkSize;
+    unsigned slop = computeSlopUpperBound(finalIdx, endIdx, isec);
+
     while (finalIdx < endIdx && addr + size + inputs[finalIdx]->getSize() <
                                     isecVA + forwardBranchRange - slop)
       finalizeOne(inputs[finalIdx++]);
 
     if (!isec->hasCallSites)
       continue;
 
     if (finalIdx == endIdx && stubsInRangeVA == TargetInfo::outOfRangeVA) {
for (Reloc &r : reverse(relocs)) {
       if (thunkInfo.sym) {
         uint64_t thunkVA = thunkInfo.isec->getVA();
         if (lowVA <= thunkVA && thunkVA <= highVA) {
           r.referent = thunkInfo.sym;
           continue;
         }
       }
       // ... otherwise, create a new thunk.
-      if (addr + size > highVA) {
-        // There were too many consecutive branch instructions for `slop`
-        // above. If you hit this: For the current algorithm, just bumping up
-        // slop above and trying again is probably simplest. (See also PR51578
-        // comment 5).
-        fatal(Twine(__FUNCTION__) + ": FIXME: thunk range overrun");
-      }
+      assert(addr + size <= highVA &&
+             "computeSlopUpperBound should have found a large enough slop.");
+
       thunkInfo.isec =
           makeSyntheticInputSection(isec->getSegName(), isec->getName());
       thunkInfo.isec->parent = this;
 
       // This code runs after dead code removal. Need to set the `live` bit
       // on the thunk isec so that asserts that check that only live sections
       // get written are happy.
       thunkInfo.isec->live = true;
while (i < ie || t < te) {
     }
     while (t < te && (i == ie || thunks[t]->outSecOff < inputs[i]->outSecOff)) {
       thunks[t]->writeTo(buf + thunks[t]->outSecOff);
       ++t;
     }
   }
 }
 
+unsigned TextOutputSection::computeSlopUpperBound(
+    const size_t initialFinalIdx, const size_t endIdx,
+    const ConcatInputSection *isec, const unsigned initialFactor) const {
+  const size_t thunkSize = target->thunkSize;
+  const uint64_t forwardBranchRange = target->forwardBranchRange;
+  const uint64_t isecVA = isec->getVA();
+  const unsigned slop = initialFactor * thunkSize;
+
+  size_t finalIdx = initialFinalIdx;
+  size_t computed_size = size;
+
+  if (!slop)
+    return 0;
+
+  if (!isec->hasCallSites)
+    return slop;
+
+  while (finalIdx < endIdx &&
+         addr + computed_size + inputs[finalIdx]->getSize() <
+             isecVA + forwardBranchRange - slop) {
+    ConcatInputSection *isec = inputs[finalIdx++];
+    computed_size = alignTo(computed_size, isec->align) + isec->getSize();
+  }
+
+  // This is a very rough mocking of the relocation process. This should use
+  // more thunk space than we actually need, so that we actually compute an
+  // upper bound of the size actually used.
+  for (const Reloc &r : reverse(isec->relocs)) {
+    if (!target->hasAttr(r.type, RelocAttrBits::BRANCH))
+      continue;
+    uint64_t callVA = isecVA + r.offset;
+    uint64_t highVA = callVA + forwardBranchRange;
+    if (addr + computed_size > highVA) {
+      return computeSlopUpperBound(initialFinalIdx, endIdx, isec,
+                                   2 * initialFactor);
+    }
+    computed_size = alignTo(computed_size, isec->align) + isec->getSize();
+  }
+  return slop;
+}
+
 void ConcatOutputSection::finalizeFlags(InputSection *input) {
   switch (sectionType(input->getFlags())) {
   default /*type-unspec'ed*/:
     // FIXME: Add additional logic here when supporting emitting obj files.
     break;
   case S_4BYTE_LITERALS:
   case S_8BYTE_LITERALS:
   case S_16BYTE_LITERALS: