Add support for range-extension thunks

[davidlattimore]

Needed to fix #1753 (may not be sufficient if there are other unrelated issues).

Range-extension thunks are mostly needed when producing large binaries for RISC architectures e.g. aarch64.

Where a branch instruction has limited range, e.g. +/- 128MiB, but the target of the branch is beyond that, we need to insert a thunk somewhere within the range that branches to the actual location.

The tricky part is that in order to know whether a thunk is needed, we need to know addresses. In order to figure out addresses, we need to know sizes, but the sizes of the thunks depends on how many we need. So there's basically a cycle in the state dependencies.

One option (call it A) would be to have an iterative algorithm e.g.:

• Determine sizes
• Determine addresses
• Scan relocations, looking of any that are out of range. Allocate thunks as needed.
• Adjust sizes based on allocated thunks
• If any adjustments were made, then go back to determining addresses

Given that determining addresses currently takes about 5% of link time, this could get expensive.

An alternative approach (B) would be to pessimistically allocate a thunk for every branch that might possibly require one. For an initial implementation, that might be sufficient. We could later add a pass where we eliminate unneeded thunks. An elimination approach has the advantage that we can probably stop after one iteration. While eliminating some thunks might reduce sizes enough that other thunks can then be eliminated, I suspect this would be of limited benefit, so probably isn't worth it. Most of the the gains would come from the first pass.

It might be tempting to create a thunk per input symbol ID rather than per relocation. This might work, but there are definitely circumstances in which it wouldn't work. e.g. if a single input symbol is referenced from two different functions that are placed in very different parts of the file - e.g. one function is marked as "cold" and placed with other cold functions.

It would also be tempting to create one thunk per symbol per input section, however the bookkeeping for doing that is likely to be expensive.

Even creating a thunk per eligible relocation requires a bit of bookkeeping. We'd need a count of thunks per input section. Storing any data per input section tends to slow us down. Fortunately there are currently a few free bytes that we can use without increasing the size of SectionSlot.

[davidlattimore]

Another option (C) would be to allocate a fixed-sized chunk of space roughly every 128 MiB in the text section. Then when writing, as we discover the need for a thunk, store the relocation offset and target symbol into a collection. Once writing is finished, sort the list of required thunks by something for determinism and apply them. If we run out of thunk space, we could fail the link, but give the user a flag they can set to in order to increase the thunk space. We could probably tune the algorithm for selecting the chunk size based on total text-section size and total number of relocations. If we aimed to have enough space for a few times more thunks than typically needed, then the flag would almost never be required.

This approach feels somehow less elegant, but I suspect it'd probably end up allocating significantly less thunk-space than the approach of allocating one thunk per eligible relocation.

[davidlattimore]

In both options B and C above, I was trying to avoid an extra scan through the relocations. Currently we do two passes over all the relocations. One during layout and a second during writing. Option A adds an additional scan in between and also repeats address assignment.

But there might be another way to avoid adding a relocation scan (option D). During the section resolution phase, we can add up for each object, the total size of all input sections, grouped by PartId. We can then assign address ranges to each object assuming that none of those input sections will get GCed. Then during the layout phase, as we look at relocations, we can take the address range for the object+part that has the relocation and the address range for the object+part that defines the symbol and compute the size of the range that covers both. This would give us an upper bound for how far apart the relocation and the symbol can be, at least if no space were taken up by thunks. The tricky part is that we need to also allow some space for thunks in this upper bound computation. I guess the easiest (cheap) upper bound would be to take the number of relocations for each text section, multiply by the thunk size and add that to the section size. From some very rough calculations, I'd guess that we'd end up allocating thunks when the range was >80MiB. We'd still only actually use the thunks when range >128MiB, so we'd have some unused thunk space.

Probably the biggest waste with option D isn't the unused thunk slots, it's the fact that thunks are never shared between relocations. We could fix that by emitting a per-object/PartId list of required thunks. Next, for each PartId, we create buckets of objects such that the bucket size plus the required thunk size doesn't exceed 128MiB. We can then deduplicate thunks within each bucket. I suspect we'd have to use a hashmap here, since the symbols requiring thunks are likely to be too sparse to do otherwise. Potentially, we could instead use sorting to deduplicate. Less call this option E.

At this point, we could also eliminate some of those extra thunks with ranges <128MiB. We have new, much more accurate upper bounds on the amount of thunks we need. We also have more accurate .text sizes that exclude GCed sections, so we can recompute the .text address-ranges for each object and PartId, taking into account the thunk block for each bucket and the post-GC sizes. Recomputing per-part, per-object address ranges should be significantly cheaper than computing all symbol addresses (which we haven't yet done at this point). We can then do a pass over the list of previously required thunks keeping only those where the relevant parts of the objects were more than 128MiB apart, from the start of first object part to end of second. Less call this option F.