cmd/compile: deadstores and nilchecks solvable after memory to ssa renames are not handled

mariecurried commented 2 weeks ago

Go version

go version devel go1.24-7fcd4a7 Mon Aug 19 23:36:23 2024 +0000 linux/amd64

What did you do?

I was reading https://www.dolthub.com/blog/2024-08-23-the-4-chan-go-programmer and there was a piece of code that caught my attention (keep in mind that it is a contrived example, but could reveal a bigger problem). So I decided to check the generated assembly (https://go.godbolt.org/z/oxqbPnPxn).

package test

func f() {
    i := 1
    setInt1(&i)
}

func setInt1(i *int) {
    setInt2(&i)
}

func setInt2(i **int) {
    setInt3(&i)
}

func setInt3(i ***int) {
    setInt4(&i)
}

func setInt4(i ****int) {
    ****i = 100
}

What did you see happen?

In some of the functions there were redundant instructions (marked with ; REDUNDANT).

setInt4 is compiled to:

MOVQ    (AX), AX
MOVQ    (AX), AX
MOVQ    (AX), AX
MOVQ    $100, (AX)
RET

setInt3 is compiled to:

MOVQ    AX, command-line-arguments.i+8(SP) ; REDUNDANT
MOVQ    (AX), AX
MOVQ    (AX), AX
XCHGL   AX, AX
MOVQ    $100, (AX)
RET

setInt2 is compiled to:

MOVQ    AX, command-line-arguments.i+8(SP)  ; REDUNDANT
LEAQ    command-line-arguments.i+8(SP), AX  ; REDUNDANT
MOVQ    (AX), AX                            ; REDUNDANT
MOVQ    (AX), AX
XCHGL   AX, AX
XCHGL   AX, AX
MOVQ    $100, (AX)
RET

setInt1 is compiled to:

(...stack handling...)
MOVQ    AX, command-line-arguments.i+24(SP)  ; REDUNDANT
LEAQ    command-line-arguments.i+24(SP), AX  ; REDUNDANT
MOVQ    AX, command-line-arguments.i(SP)     ; REDUNDANT
LEAQ    command-line-arguments.i(SP), AX     ; REDUNDANT
MOVQ    (AX), AX                             ; REDUNDANT
MOVQ    (AX), AX                             ; REDUNDANT
NOP
XCHGL   AX, AX
XCHGL   AX, AX
MOVQ    $100, (AX)
(...stack handling...)
RET

What did you expect to see?

I expected to see no redundant instructions.

gabyhelp commented 2 weeks ago

Related Issues and Documentation

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

prattmic commented 2 weeks ago

cc @golang/compiler @randall77

Jorropo commented 2 weeks ago

This happens without inlining: https://go.godbolt.org/z/v58b47zf3

I know why it fails, there is a systemic tradeoff in most of the compiler only operating on SSA values, when you store things in memory (&i) a lot of optimization information is lost, here in this case nilcheckelim abandon. So only the outer most *& pair is being optimized because the ****p is never stored in memory.

Solving this for all possible cases is impossible, and getting right often is extremely costy both in term of compilation time and compiler code complexity which is a tradeoff the go compiler usually do not accept. The CPU perform store → load forward at runtime, I doubt this has huge cost impact at runtime.

I have an idea on how to cheaply improve this extremely naive example but this wont solve much more cases.

Jorropo commented 2 weeks ago

Well I was only able to improve the situation slightly:

    # /tmp/a.go
    00000 (3) TEXT command-line-arguments.f(SB), ABIInternal
    00001 (3) FUNCDATA $0, gclocals·g2BeySu+wFnoycgXfElmcg==(SB)
    00002 (3) FUNCDATA $1, gclocals·EaPwxsZ75yY1hHMVZLmk6g==(SB)
    00003 (3) FUNCDATA $2, command-line-arguments.f.stkobj(SB)
v6  00004 (+4) MOVQ $1, command-line-arguments.i-24(SP)
v27 00005 (+5) LEAQ command-line-arguments.i-24(SP), AX
v10 00006 (5) MOVQ AX, command-line-arguments.p1-8(SP)
v16 00007 (+6) LEAQ command-line-arguments.p1-8(SP), AX
v14 00008 (6) MOVQ AX, command-line-arguments.p2-16(SP)
v24 00009 (+9) MOVQ command-line-arguments.p2-16(SP), AX
v26 00010 (9) MOVQ (AX), AX
v28 00011 (9) MOVQ $100, (AX)
b1  00012 (10) RET
    00013 (?) END

I removed the in the way nilchecks, which removes one more load, however then the dead stores become in the way and I don't know of a cheap way to run theses during late opt. I think this fall in the « passes ordering is hard » kind of camp, given it would solve itself if we reran the core generic passes in a loop until things stabilize but that expensive.

gopherbot commented 2 weeks ago

Change https://go.dev/cl/609995 mentions this issue: cmd/compile: remove some uneeded nilchecks during opt

golang / go