~mpu/qbe

1

problem in rega.c

Details
Message ID
<D6DX0RE7126V.27SVHGRPXQC9A@turminal.net>
DKIM signature
pass
Download raw message
Hi,

I hit a problem in QBE while working on Harec. When trying to compile this:
https://paste.sr.ht/~turminal/83a9e151bdb8f9f8e374ff7380f3cd2c6585e2c0
With a modified version of Harec (available at
https://git.sr.ht/~turminal/harec, branch qbe, the last commit is what
makes it fail, making a bunch of copies that were previously just reuse
of a temporary), QBE fails on the produced IR with "cannot have more
moves than registers" in rega.c:pmadd.

I reduced the Hare code to this:
https://paste.sr.ht/~turminal/d5a6309a7bc183836a1d4d424e778f7dfd3c6762
The "as" thingies are type assertions, they kill the program if the
expression on the left is not of the correct variant of the tagged
union. The deferred expressions above are supposed to be run before the
program is killed, and due to a somewhat suboptimal state of harec
codeged, the deferred expressions are generated once for each exit path
from the function, so there's a lot of
duplication.

The resulting IR is here:
https://paste.sr.ht/~turminal/249291aeea3802473fce0ff3432c586ae20f9841
I managed to reduce it further, but the result is still over 250 lines:
https://paste.sr.ht/~turminal/88d767b6ad3f8a3c57a6523467ca209e3cbb83c0
Afaict simplifying anything more than that makes it compile.

It's highly repetitive, it starts with some prelude and then the rest of
it is just repetitions of
@passed.A
	jnz 0, @passed.NEXTA, @failed.B
@failed.B
	jnz 0, @body.C, @.D
@body.C
	%.load.E =l copy %binding
	%.F =l add %.load.E, 16
	%.G =l loadl %.load.E
	%.H =l loadl %.F
	jmp @failed.B
@.D
	%.load.I =l copy %binding
	%.J =l add %.load.I, 16
	%.K =l loadl %.load.I
	%.L =l loadl %.J
@passed.NEXTA
...

with the letters replaced with a different set of numbers each time.
Notice that the binding from which things are loaded is the same, and
that its address is copied everytime. Removing this copy (basically
doing s/%load/%binding/ and then removing the lines copying the binding
makes the issue go away. So I guess this has something to do with these
copies? This is also indicated by the commit in harec that makes this
break. Another thing that I find odd is the significance of the
@failed.B block. If I remove it (by moving the jnz to the end of
@body.C), the error doesn't happen.

To me, this IR looks perfectly fine, except for the inefficiency with
copy and the slightly stupid indirection with @failed.B, and I can't
think of a reason it would be very register allocation heavy. I'm also
out of ideas on how to debug this furter. So I'm wondering if this is a
bug in QBE? Or am I just emitting trash IR and should do better?

Or both? :)
Details
Message ID
<b8853f6c-a7ed-47f7-9c4a-30ca3316e000@app.fastmail.com>
In-Reply-To
<D6DX0RE7126V.27SVHGRPXQC9A@turminal.net> (view parent)
DKIM signature
pass
Download raw message
On Tue, Dec 17, 2024, at 11:48, Bor Grošelj Simić wrote:
> of a temporary), QBE fails on the produced IR with "cannot have more
> moves than registers" in rega.c:pmadd.

I remember hitting this one already when, I think it was when
Michael tried to bootstrap zig with qbe. We trigger it when
there is a lot of shuffle to make at block boundaries. I will
look at your code to understand why it stresses qbe.

To quickly unblock yourself you can bump the size of the static
array pm[] in rega.c and update accordingly the condition under
which the die() call you hit triggers.

> I reduced the Hare code to this:
> https://paste.sr.ht/~turminal/d5a6309a7bc183836a1d4d424e778f7dfd3c6762

Thanks, that's helpful.

> The "as" thingies are type assertions, they kill the program if the
> expression on the left is not of the correct variant of the tagged
> union. The deferred expressions above are supposed to be run before the
> program is killed, and due to a somewhat suboptimal state of harec
> codeged, the deferred expressions are generated once for each exit path
> from the function, so there's a lot of
> duplication.

I know! I started working on this at one point, but have not
converged yet. It was in the context of unparse that is quite
slow to compile for this reason.

> with the letters replaced with a different set of numbers each time.
> Notice that the binding from which things are loaded is the same, and
> that its address is copied everytime. Removing this copy (basically
> doing s/%load/%binding/ and then removing the lines copying the binding
> makes the issue go away. So I guess this has something to do with these
> copies? This is also indicated by the commit in harec that makes this
> break. Another thing that I find odd is the significance of the
> @failed.B block. If I remove it (by moving the jnz to the end of
> @body.C), the error doesn't happen.
>
> To me, this IR looks perfectly fine, except for the inefficiency with
> copy and the slightly stupid indirection with @failed.B, and I can't
> think of a reason it would be very register allocation heavy. I'm also
> out of ideas on how to debug this further. So I'm wondering if this is a
> bug in QBE? Or am I just emitting trash IR and should do better?

You went pretty far already and I think there is a defect in qbe.
Now, it'd be great to solve the repetition incurred by defer blocks.
Reply to thread Export thread (mbox)