Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

cmd/compile: unneccesary 0 check in division #45928

Closed
JAicewizard opened this issue May 3, 2021 · 8 comments
Closed

cmd/compile: unneccesary 0 check in division #45928

JAicewizard opened this issue May 3, 2021 · 8 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FrozenDueToAge help wanted NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone
Go1.21

Comments

@JAicewizard
Copy link

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.
@seankhliao seankhliao changed the title unneccesary 0 check in division cmd/compile: unneccesary 0 check in division May 3, 2021
@randall77 randall77 added this to the Unplanned milestone May 3, 2021
@cagedmantis cagedmantis added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label May 4, 2021
@josharian
Copy link
Contributor

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

@gopherbot
Copy link

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

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
@dmitshur dmitshur added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Jan 23, 2023
@dmitshur dmitshur modified the milestones: Unplanned, Go1.20 Jan 23, 2023
@mvdan
Copy link
Member

mvdan commented Jan 30, 2023

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.

@mvdan mvdan reopened this Jan 30, 2023
@cuonglm
Copy link
Member

cuonglm commented Jan 31, 2023

@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.

@gopherbot gopherbot modified the milestones: Go1.20, Go1.21 Feb 1, 2023
@cuonglm
Copy link
Member

cuonglm commented Apr 10, 2023

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

@randall77
Copy link
Contributor

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

@cuonglm
Copy link
Member

cuonglm commented Apr 10, 2023 •
edited

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
Copy link

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

@golang golang locked and limited conversation to collaborators Apr 9, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FrozenDueToAge help wanted NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Milestone
Go1.21
Development

No branches or pull requests
9 participants
@josharian @cagedmantis @mknyszek @dmitshur @mvdan @cuonglm @randall77 @gopherbot @JAicewizard