ARM64 Indirect call produces redundant address load for R2R

[kunalspathak]

While generating indirect call for R2R, I have noticed we generate redundant indirect address loads in x11 as well as x4 and end up using the one present in x4. In dotnet/coreclr#5020 we fixed x11 as being a register to store indirect cell address, but in dotnet/coreclr#16171 we moved to morph phase. However with that, we end up creating 2nd redundant addrp/add pair inside lower that uses x4 register.

        9000000B          adrp    x11, [RELOC #0x20a0e212c50]
        9100016B          add     x11, x11, #0
        90000004          adrp    x4, [RELOC #0x20a0e212c50]
        91000084          add     x4, x4, #0
        F9400084          ldr     x4, [x4]
        D63F0080          blr     x4

We need to investigate to see why x4 is needed and if yes, then simplify it to mov x4, x11.

category:cq
theme:ready-to-run
skill-level:intermediate
cost:large

[Dotnet-GitSync-Bot]

I couldn't figure out the best area label to add to this issue. Please help me learn by adding exactly one area label.

[kunalspathak]

@sandreenko @BruceForstall @AntonLapounov

[BruceForstall]

Well, we certainly need x4 in this example because it is an available register that is used to compute the branch target address. It appears that the non-standard argument register x11 is used by R2R to identify the indirection cell address to the call stub.

Given that x11 and x4 here are loaded with the same address, we should be able to generate:

adrp    x11, [RELOC #0x20a0e212c50]
add     x11, x11, #0
ldr     x4, [x11] // re-use x11 here as stub address
blr     x4

[BruceForstall]

@jkotas @fadimounir When looking at R2R codegen on arm64, we see the inefficient pattern above for calls through an indirection cell. On x64, the code would be simply:

call [RELOC #0x20a0e212c50]

I'm not sure what is actually going on here, but I presume this indirection cell initially points to some kind of stub, and after the actual target is determined, the indirection cell is fixed up to the actual target address. In the x64 case, then, the steady state overhead is just an indirect call instead of a direct call. On arm64, however, the steady state also includes setting up the x11 argument, which will not be used. (In my optimized example, it would still be used to load the indirection cell value, and we would always need something like this.)

Is this the optimal way to generate this code?

We could instead generate the LDR (literal) instruction, e.g.:

ldr     x4, RELOC #0x20a0e212c50
blr     x4

but that only has a +/-1MB PC-relative range, and wouldn't allow setting x11.

Possibly we could change the stub to include the stub address? (Or perhaps the stub is shared?)

[jkotas]

The methods have to be called via indirection cells in R2R images. (We may be able to direct calls in some cases as an optimization. We do not have that optimization today for R2R, on any platform - that would be a separate discussion.)

The indirection cell points to a delay load stub initially. The delay load stub worker method needs the address of the indirection cell to figure out the target method and to update the indirection cell with the address of the target method.

On x64, we get the address of the indirection cell by disassembling the callsite. It works fine because of the x64 encoding details (note that there are details to consider like how break points injected by debugger are encoded, etc.).

On arm/arm64, we require the address of the indirection cell to be passed in a fixed register. You are right that we could move the loading of the address from the code stream into the non-shared portion of the stub. I am not sure whether it would actually save anything interesting. It would likely just move the code from one place in the R2R image to a different place in the R2R image and/or regress the steady state performance (depends on the details).

Your suggestion in #35108 (comment) sounds good as the first step.

[kunalspathak]

I collected no. of such adrp/add groups in framework libraries and found approx. 615732 such groups in 126823 methods.

[BruceForstall]

The current code sequence, using adrp/add pair has 32-bit PC-relative range, which presumably means that all the indirection cells can be packed together in the PE file. Is that important?

If we instead chose to use the LDR (literal) instruction, with only +/-1MB range, presumably we would have to move them into various sections "close to" their calling functions, or even per-calling-function (which means they wouldn't be shared; presumably that's a loss?). However, then presumably the VM could use the same idea as x64: disassembly the LDR instruction using the return address in the lr register.

We would presumably need an escape hatch if the call was within a function that itself was >1MB, so it couldn't even reach outside of its own code section (such as hiding it somewhere in the code, or bailing the compilation and retrying but disallowing the "short" form of the instruction pattern).

[BruceForstall]

While we should start by removing the duplication of setting up the indirection cell address, this pattern is so common it seems like we should consider how to optimize it even further.

[BruceForstall]

For example, you could imagine a case where there are a lot of calls to different functions with similar indirection cell addresses, where the indirection cells are packed together. In that case, a single adrp/add could establish a "base pointer", and a single "add" to this base pointer could compute the indirection cell address (instead of a new adrp/add pair). This would require "relocs" for these adds, a decision about whether maintaining a "base pointer" was profitable, and an "escape hatch" if all the targets couldn't be reached from the one (or more) base pointer(s). So yes, it could be complex.

[jkotas]

this pattern is so common it seems like we should consider how to optimize it even further.

Definitely agree.

all the indirection cells can be packed together in the PE file. Is that important?

This packing is important for some types of cells (e.g. string literals - to avoid duplicates). It is not as important for other types of cells. Also, this packing makes the PE file algorithm simple.

move them into various sections

I expect that the number of sections in the PE image is capped to something relatively small. We may start hitting against this limit if we start generating 2 sections per 1MB of binary. This is really only a problem on Windows where we use the OS loader. It is not a problem on Linux where we have our own loader today.

a single adrp/add could establish a "base pointer", and a single "add" to this base pointer could compute the indirection cell address (instead of a new adrp/add pair)

This idea sounds most scalable idea to me. It does not have the corner cases where it breaks down.

I would look into these ideas on top of crossgen2 only. I do not think we would want to spend time to teach crossgen about this.

cc @dotnet/crossgen-contrib