cmd/compile: unneccesary 0 check in division

[JAicewizard]

What version of Go are you using (go version)?

$ go version
go version go1.16.3 linux/amd64

Does this issue reproduce with the latest release?

AFAIK I run the latest, havnt tried on tip.

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/jaap/.cache/go-build"
GOENV="/home/jaap/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/jaap/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/jaap/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/lib/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/lib/go/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="go1.16.3"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/dev/null"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build3803926857=/tmp/go-build -gno-record-gcc-switches"

What did you do?

$ cat main.go
package A

func DivPositSameES(x uint32) {
	combinedFrac := (x) / (x | (1 << 31))
	println(combinedFrac)
}
$ go tool compile -S main.go
"".DivPositSameES STEXT size=110 args=0x8 locals=0x18 funcid=0x0
        0x0000 00000 (main.go:3)        TEXT    "".DivPositSameES(SB), ABIInternal, $24-8
        0x0000 00000 (main.go:3)        MOVQ    (TLS), CX
        0x0009 00009 (main.go:3)        CMPQ    SP, 16(CX)
        0x000d 00013 (main.go:3)        PCDATA  $0, $-2
        0x000d 00013 (main.go:3)        JLS     103
        0x000f 00015 (main.go:3)        PCDATA  $0, $-1
        0x000f 00015 (main.go:3)        SUBQ    $24, SP
        0x0013 00019 (main.go:3)        MOVQ    BP, 16(SP)
        0x0018 00024 (main.go:3)        LEAQ    16(SP), BP
        0x001d 00029 (main.go:3)        FUNCDATA        $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x001d 00029 (main.go:3)        FUNCDATA        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x001d 00029 (main.go:4)        MOVL    "".x+32(SP), AX
        0x0021 00033 (main.go:4)        MOVL    AX, CX
        0x0023 00035 (main.go:4)        BTSL    $31, AX
        0x0027 00039 (main.go:4)        TESTL   AX, AX
        0x0029 00041 (main.go:4)        JEQ     97
        0x002b 00043 (main.go:4)        MOVL    AX, DX
        0x002d 00045 (main.go:4)        MOVL    CX, AX
        0x002f 00047 (main.go:4)        MOVL    DX, BX
        0x0031 00049 (main.go:4)        XORL    DX, DX
        0x0033 00051 (main.go:4)        DIVL    BX
        0x0035 00053 (main.go:4)        MOVL    AX, "".combinedFrac+12(SP)
        0x0039 00057 (main.go:5)        PCDATA  $1, $0
        0x0039 00057 (main.go:5)        CALL    runtime.printlock(SB)
        0x003e 00062 (main.go:5)        MOVL    "".combinedFrac+12(SP), CX
        0x0042 00066 (main.go:5)        MOVL    CX, CX
        0x0044 00068 (main.go:5)        MOVQ    CX, (SP)
        0x0048 00072 (main.go:5)        CALL    runtime.printuint(SB)
        0x004d 00077 (main.go:5)        CALL    runtime.printnl(SB)
        0x0052 00082 (main.go:5)        CALL    runtime.printunlock(SB)
        0x0057 00087 (main.go:6)        MOVQ    16(SP), BP
        0x005c 00092 (main.go:6)        ADDQ    $24, SP
        0x0060 00096 (main.go:6)        RET
        0x0061 00097 (main.go:4)        CALL    runtime.panicdivide(SB)
        0x0066 00102 (main.go:4)        XCHGL   AX, AX
        0x0067 00103 (main.go:4)        NOP
        0x0067 00103 (main.go:3)        PCDATA  $1, $-1
        0x0067 00103 (main.go:3)        PCDATA  $0, $-2
        0x0067 00103 (main.go:3)        CALL    runtime.morestack_noctxt(SB)
        0x006c 00108 (main.go:3)        PCDATA  $0, $-1
        0x006c 00108 (main.go:3)        JMP     0
        0x0000 64 48 8b 0c 25 00 00 00 00 48 3b 61 10 76 58 48  dH..%....H;a.vXH
        0x0010 83 ec 18 48 89 6c 24 10 48 8d 6c 24 10 8b 44 24  ...H.l$.H.l$..D$
        0x0020 20 89 c1 0f ba e8 1f 85 c0 74 36 89 c2 89 c8 89   ........t6.....
        0x0030 d3 31 d2 f7 f3 89 44 24 0c e8 00 00 00 00 8b 4c  .1....D$.......L
        0x0040 24 0c 89 c9 48 89 0c 24 e8 00 00 00 00 e8 00 00  $...H..$........
        0x0050 00 00 e8 00 00 00 00 48 8b 6c 24 10 48 83 c4 18  .......H.l$.H...
        0x0060 c3 e8 00 00 00 00 90 e8 00 00 00 00 eb 92        ..............
        rel 5+4 t=17 TLS+0
        rel 58+4 t=8 runtime.printlock+0
        rel 73+4 t=8 runtime.printuint+0
        rel 78+4 t=8 runtime.printnl+0
        rel 83+4 t=8 runtime.printunlock+0
        rel 98+4 t=8 runtime.panicdivide+0
        rel 104+4 t=8 runtime.morestack_noctxt+0
go.cuinfo.packagename. SDWARFCUINFO dupok size=0
        0x0000 41                                               A
gclocals·33cdeccccebe80329f1fdbee7f5874cb SRODATA dupok size=8
        0x0000 01 00 00 00 00 00 00 00                          ........

What did you expect to see?

I expected the compiler to be smart enough to know that x | (1 << 31) would never be 0, as it should be quite obvious.

What did you see instead?

Most notibly:

        0x0027 00039 (main.go:4)        TESTL   AX, AX
        0x0029 00041 (main.go:4)        JEQ     97

This is a 0 check that I did not expect to see.

It sounds quite plausible to me that the compiler only checks for non-0 constants to remove this check. I think that when it is so explicitly not 0, the compiler should be able to figure this one out.

[josharian]

cc @zdjones as this seems likely to be prove-related

[gopherbot]

Change https://go.dev/cl/410336 mentions this issue: cmd/compile: teach prove about or operation

[mvdan]

The merged CL was reverted recently in https://go-review.googlesource.com/c/go/+/463295 due to #57959. Reopening the issue, as presumably we still want to try improving the prove pass.

[cuonglm]

@randall77 from your comment at #57959 (comment)

If anything, maybe we could figure out when we don't need to prove anything about a value during the prove pass itself. Maybe if the result of an OR is only used in subsequent ORs and shifts, then don't record anything about it. Or something like that.

I tried something like this, and it bring the slowness from 100x to 10x, still seems not worth to do that.

[cuonglm]

@randall77 maybe we can update fact table if either arguments of OpOr is a constant? (aka v.isGenericIntConst())?

[randall77]

Sure, that would be a simple rule. How many facts does it add to the table? How much slowdown?

[cuonglm]

Sure, that would be a simple rule. How many facts does it add to the table? How much slowdown?

For the repo in #57959, there's 2s slowdown:

$ time go build glyphs.go
=====
JOB go build glyphs.go
174%    cpu
7.23s real
11.44s user
1.16s sys
$ time go1.20.3 build glyphs.go
=====
JOB go1.20.3 build glyphs.go
134%    cpu
5.76s real
6.65s user
1.08s sys

Nearly 200 facts added:

$ go build glyphs.go |& grep -c ADDED
192

[gopherbot]

Change https://go.dev/cl/483359 mentions this issue: cmd/compile: teach prove about bitwise OR operation