The symptom is superficially similar to #32969. Any idea whether the root cause is the same?

(CC @randall77 @dr2chase)

I can't reproduce. I get this when compiling Zig with tip (5235501c0509385c28294b3a314891e1e7165163):

	0x0000 00000 (/usr/local/google/home/khr/gowork/issue33349.go:8)	MOVQ	"".x+8(SP), AX
	0x0005 00005 (/usr/local/google/home/khr/gowork/issue33349.go:8)	ADDQ	AX, AX
	0x0008 00008 (/usr/local/google/home/khr/gowork/issue33349.go:8)	SBBQ	CX, CX
	0x000b 00011 (/usr/local/google/home/khr/gowork/issue33349.go:9)	XORQ	CX, AX
	0x000e 00014 (/usr/local/google/home/khr/gowork/issue33349.go:9)	MOVQ	AX, "".~r1+16(SP)

Yes, that's Zig()'s code. But when it is inlined into AppendZig() causes the problem. Apologies didn't make it clear.

Ok, that makes more sense.

Looks like we need a tweak to the schedule pass. Schedule produces:

v40 (+8) = ADDQcarry <uint64,flags> v10 v10
v65 (8) = Select0 <uint64> v40 (y[uint64])
v42 (8) = Select1 <flags> v40
v48 (25) = ADDQ <*byte> v115 v71
v50 (25) = MOVQstore <mem> v2 v48 v49
v53 (25) = MOVQstore <mem> [8] v2 v102 v50
v57 (25) = MOVQstore <mem> [16] v2 v86 v53
v58 (25) = CALLstatic <mem> {runtime.memmove} [24] v57
v45 (8) = SBBQcarrymask <uint64> v42

There's just a single ADDQ, and we use Select0/Select1 to get the 64-bit result and the carry, respectively. But then the carry isn't used until after the memmove. That means we need to spill the carry and restore it around the memmove call. And because there's no instruction to spill/restore flags (no cheap one, anyway), we reissue the flag-generating instruction after the memmove. After flagalloc, we have:

v40 (+8) = ADDQcarry <uint64,flags> v10 v10
v65 (8) = Select0 <uint64> v40 (y[uint64])
v42 (8) = Select1 <flags> v40
v48 (25) = ADDQ <*byte> v115 v71
v50 (25) = MOVQstore <mem> v2 v48 v49
v53 (25) = MOVQstore <mem> [8] v2 v102 v50
v57 (25) = MOVQstore <mem> [16] v2 v86 v53
v58 (25) = CALLstatic <mem> {runtime.memmove} [24] v57
v6 (8) = ADDQcarry <uint64,flags> v10 v10
v15 (8) = Select1 <flags> v6
v45 (8) = SBBQcarrymask <uint64> v15

v42 is now dead, we've recomputed it as v6+v15.

We already try to schedule flag users earlier, to make flag lifetimes short. Just pushing ReadFlags ahead of Memory (which is what memmove is) seems to fix this issue. I'll have to think a bit about whether that would break anything else.

Just prioritizing the flags op is not enough, as it leads to another bad ordering. With that change we do just a single add, but end up spilling both the add result and the result of the SBBQ to the stack before the memmove. Those values are then loaded and xored immediately after the memmove. It would be better to do the xor before spilling so there is only one thing to spill+restore.

This will probably require a more general upgrade to the scheduling pass. We need to incorporate information to enable prioritization of instructions which kill more arguments than they generate results (or perhaps even enable subsequent instructions to do so). Right now it is done just by instruction class, which isn't precise enough.

I did manage to find a similar issue with bits.Len(), as it also relies on flags.

package oddsched

import (
	"math/bits"
)

func AppendVarint(p []byte, x uint64) []byte {
	t := [10]byte{
		uint8(x) | 0x80,
		uint8(x>>7) | 0x80,
		uint8(x>>14) | 0x80,
		uint8(x>>21) | 0x80,
		uint8(x>>28) | 0x80,
		uint8(x>>35) | 0x80,
		uint8(x>>42) | 0x80,
		uint8(x>>49) | 0x80,
		uint8(x>>56) | 0x80,
		1,
	}
	n := (bits.Len64(x|1) + 6) / 7
	t[n-1] &= 0x7F
	return append(p, t[:n]...)
}

The assembly starts with performing x|1 and a BSR, then goes initialises t, so has to perform another BSRQ to finally compute n.

	MOVQ	"".x+152(SP), DX
	MOVQ	DX, BX
	ORQ	$1, DX
	BSRQ	DX, SI
        ... init t...
   	BSRQ	DX, DX
	MOVQ	$-1, DX
	CMOVQEQ	DX, SI
	LEAQ	7(SI), DX
	MOVQ	$5270498306774157605, AX
	MOVQ	DX, CX
	IMULQ	DX
	SARQ	$1, DX
	SARQ	$63, CX
	SUBQ	CX, DX