Skip to content

cmd/compile: unneccesary 0 check in division #45928

Closed
@JAicewizard

Description

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

Activity

changed the title [-]unneccesary 0 check in division[/-] [+]cmd/compile: unneccesary 0 check in division[/+] on May 3, 2021
added this to the Unplanned milestone on May 3, 2021
added
NeedsInvestigationSomeone must examine and confirm this is a valid issue and not a duplicate of an existing one.
on May 4, 2021
josharian

josharian commented on May 7, 2021

@josharian
Contributor

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

gopherbot

gopherbot commented on Jun 5, 2022

@gopherbot
Contributor

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

added
NeedsFixThe path to resolution is known, but the work has not been done.
and removed
NeedsInvestigationSomeone must examine and confirm this is a valid issue and not a duplicate of an existing one.
on Jan 23, 2023
modified the milestones: Unplanned, Go1.20 on Jan 23, 2023
mvdan

mvdan commented on Jan 30, 2023

@mvdan
Member

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.

2 remaining items

modified the milestones: Go1.20, Go1.21 on Feb 1, 2023
cuonglm

cuonglm commented on Apr 10, 2023

@cuonglm
Member

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

randall77

randall77 commented on Apr 10, 2023

@randall77
Contributor

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

cuonglm

cuonglm commented on Apr 10, 2023

@cuonglm
Member

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

gopherbot commented on Apr 10, 2023

@gopherbot
Contributor

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

added a commit that references this issue on Feb 20, 2024
3680b5e
locked and limited conversation to collaborators on Apr 9, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @josharian@cagedmantis@mknyszek@dmitshur@mvdan

        Issue actions

          cmd/compile: unneccesary 0 check in division · Issue #45928 · golang/go