call arguments can produce lots of shuffling

[bagggage]

Problem

I have a certain code generator based on bunny-jit where I often have to make calls to external functions by address. I frequently find myself in the following situation:

...
movabs rcx, 0x55556533aef0
movabs r9, 0x555558c79c20
mov rsi, rdi
mov rdi, rcx
mov rbx, rdx
xor edx, edx
mov rcx, rsp
mov rax, r9
call rax
...

This is part of the result of compiling some code that involves a function call with 4 arguments. The first thing that stands out is the pointless loading of the function address into r9 instead of just loading it directly into rax. This happens consistently, and it’s likely related to the fact that the frontend’s Proc::i/d/tcallp takes it as the first argument, and I use Proc::lcu before calling Proc::i/d/tcallp. Afterward, the frontend itself generates opcodes for loading the arguments. Thus, first comes the address, then the arguments, and then the call, which again requires the address.

A similar problem occurs with the arguments themselves: values are constantly being shuffled between registers instead of computations being performed directly in the desired registers to avoid unnecessary mov instructions.

Question

Where can I find the implementation code related to this, the optimization passes, etc.? I’d like to improve this and possibly implement some optimizations if it turns out to be feasible.

[signaldust]

Just to sanity check, this is happening with optimization level set to at least 1?

The lcu+callp is a reasonable thing to do.

Most likely what is going is an artifact of how the current register allocator (opt-ra, which I'm afraid is probably the weakest part of the whole thing really) works: it's not really able to look ahead when it comes fixed register constraints, rather it allocates registers basically in the order of instructions and then tries to do some simple hacks to try and fix some things, but reverts to shuffling if necessary in order to at least produce correct code. For most straight-line code this isn't an issue, because very few instructions (div mostly) have fixed register constraints, but obviously the function calls are the worst case. Unfortunately I have to admit that somewhat sub-optimal code is expected.

That said, the case of loading two constants into random registers and then moving them to the required registers after shuffling other things is obviously very silly and probably the easier issue to fix too. There is some logic to avoid spilling constants (rather they are rematerialized), so I think this could perhaps be avoided simply by forbidding the RA from moving constants from one register to another, instead forcing it to rematerialize in the desired register, which should then let DCE cleanup the original (now useless) load. I can try to look into that at least.

Avoiding the rest of the shuffles though ... that's likely a case where we'd really need a better register allocation algorithm, though without the surrounding code it's hard to say for sure.

[signaldust]

bacc03e forbids RA from moving constants to satisfy input constraints, forcing a rematerialization instead, which seems sufficient for bin/test_callp to directly load function address into x9 on ARM (the same issue putting the target address into a forbidden register first, although bin/test_callp doesn't have this issue on x86)

that should fix the biggest problem with the silly loads into wrong register..

[bagggage]

Just to sanity check, this is happening with optimization level set to at least 1?

Yes, this happens when using optimization levels 1 and 2.

---

I also found another bug, sometimes there is a push/pop of one or two registers that are never used.

push rbp
push rbx
push r12 ; unused
push r13 ; unused
sub rsp, 0x38
...
xor eax, eax
add rsp, 0x38
pop r13 ; <-
pop r12 ; <-
pop rbx
pop rbp
ret 

I think this is also related to the fact that they were allocated but, after optimization passes, are no longer needed, although the code that saves them on the stack during the call frame setup still remains.

[signaldust]

I could use a repro test-case for the second issue with the excess pushes/pops...

Since the only optimization that runs after RA is the DCE (dead-code elimination) this must be a case where the RA initially decides to compute something into a register and then later chooses to rematerialize the value without actually ever using the original value... but the damage is done, 'cos it's RA that tracks which registers are used. In fact my fix "don't rename constants" fix could trigger this too.

I think that should probably be fixed by writing a separate pass that runs after the very final DCE, just before assembly that simply iterates through all the live blocks and ops and collects output registers and regsLost() and use that instead.

[signaldust]

To be honest, the way RA collects the regs is probably a bit error-prone in general, so refactoring that into a separate pass is not necessarily a bad idea in general.

[signaldust]

8e389ec collects used registers in separate pass, should fix the excess pushes/pops

[bagggage]

It seems to be working, with the previous fix the resulting code has significantly decreased in size.

I could use a repro test-case for the second issue with the excess pushes/pops...

Yeah... I’d like to provide a test case, but my code generator is a bit convoluted, and I can’t track exactly which Proc::* calls it’s making to reproduce this. I’ll try to do so next time I come across something, but I can’t promise anything.

[signaldust]

Well, to be honest, I'm not even sure how to make a good unit test out that.. so we'll assume findUsedRegs() is fine and revisit the issue later if there's a problem.

I'll take the "bug" label off for now, but leave this open, since the argument shuffling with the calls is not something that is easily fixable, but I might see if something can be done about it some time in the future..

[signaldust]

2bf2a33 should hopefully improve handling of single-use constants in general + tries to fix some silly spills where we need to reload/remat into a register that already has a value we will need later