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

cmd/compile: detect divisions that always result in 0 #25733

Open
davecheney opened this Issue Jun 5, 2018 · 6 comments

Comments

Projects
None yet
7 participants
@davecheney
Contributor

davecheney commented Jun 5, 2018

Please answer these questions before submitting your issue. Thanks!

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

go version devel +b7f3c178a3 Mon May 14 04:42:45 2018 +0000 darwin/amd64

Does this issue reproduce with the latest release?

yes

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

darwin/amd64

What did you do?

func f(p, q uint) uint {
        return p + (q%6)/9
}

go run -gcflags=-S moddiv.go

What did you expect to see?

Something akin to

"".f STEXT nosplit size=69 args=0x18 locals=0x0
        0x0000 00000 (/Users/dfc/src/moddiv.go:5)       TEXT    "".f(SB), NOSPLIT, $0-24
        0x0000 00000 (/Users/dfc/src/moddiv.go:5)       FUNCDATA        $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0000 00000 (/Users/dfc/src/moddiv.go:5)       FUNCDATA        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0000 00000 (/Users/dfc/src/moddiv.go:6)       MOVQ    $-6148914691236517205, AX
        0x000a 00010 (/Users/dfc/src/moddiv.go:6)       MOVQ    "".q+16(SP), CX
        0x003f 00063 (/Users/dfc/src/moddiv.go:6)       MOVQ    CX, "".~r2+24(SP)
        0x0044 00068 (/Users/dfc/src/moddiv.go:6)       RET

What did you see instead?

"".f STEXT nosplit size=69 args=0x18 locals=0x0
        0x0000 00000 (/Users/dfc/src/moddiv.go:5)       TEXT    "".f(SB), NOSPLIT, $0-24
        0x0000 00000 (/Users/dfc/src/moddiv.go:5)       FUNCDATA        $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0000 00000 (/Users/dfc/src/moddiv.go:5)       FUNCDATA        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0000 00000 (/Users/dfc/src/moddiv.go:6)       MOVQ    $-6148914691236517205, AX
        0x000a 00010 (/Users/dfc/src/moddiv.go:6)       MOVQ    "".q+16(SP), CX
        0x000f 00015 (/Users/dfc/src/moddiv.go:6)       MULQ    CX
        0x0012 00018 (/Users/dfc/src/moddiv.go:6)       SHRQ    $2, DX
        0x0016 00022 (/Users/dfc/src/moddiv.go:6)       LEAQ    (DX)(DX*2), DX
        0x001a 00026 (/Users/dfc/src/moddiv.go:6)       SHLQ    $1, DX
        0x001d 00029 (/Users/dfc/src/moddiv.go:6)       SUBQ    DX, CX
        0x0020 00032 (/Users/dfc/src/moddiv.go:6)       MOVQ    $-4099276460824344803, AX
        0x002a 00042 (/Users/dfc/src/moddiv.go:6)       MULQ    CX
        0x002d 00045 (/Users/dfc/src/moddiv.go:6)       ADDQ    DX, CX
        0x0030 00048 (/Users/dfc/src/moddiv.go:6)       RCRQ    $1, CX
        0x0033 00051 (/Users/dfc/src/moddiv.go:6)       SHRQ    $3, CX
        0x0037 00055 (/Users/dfc/src/moddiv.go:6)       MOVQ    "".p+8(SP), DX
        0x003c 00060 (/Users/dfc/src/moddiv.go:6)       ADDQ    DX, CX
        0x003f 00063 (/Users/dfc/src/moddiv.go:6)       MOVQ    CX, "".~r2+24(SP)
        0x0044 00068 (/Users/dfc/src/moddiv.go:6)       RET

The value of q is in the range [0-6) because of the modulo, which divided by 9 is always 0. So the result of f(x, y) is always x

@randall77 randall77 added this to the Go1.12 milestone Jun 5, 2018

@josharian

This comment has been minimized.

Contributor

josharian commented Jun 5, 2018

@davecheney safe to assume this came from real code? Autogenerated?

@FiloSottile FiloSottile changed the title from cmd/compile: missed optimisation to cmd/compile: detect divisions that always result in 0 Jun 5, 2018

@davecheney

This comment has been minimized.

Contributor

davecheney commented Jun 5, 2018

I'm afraid it's worse, this code came from a LLVM presentation, https://youtu.be/V6ug3e3jC54?t=3m22s

@valyala

This comment has been minimized.

Contributor

valyala commented Jun 6, 2018

This sounds like a job for prove pass. cc'ing @aclements and @rasky , since they recently were working on it.

@gopherbot

This comment has been minimized.

gopherbot commented Aug 20, 2018

Change https://golang.org/cl/129759 mentions this issue: cmd/compile: optimize divisions like (x%a)/b

@ChrisALiles

This comment has been minimized.

Contributor

ChrisALiles commented Aug 20, 2018

I don’t know if or when prove will do this kind of optimisation. In the meantime this is a simple fix for the specific issue.

@magical

This comment has been minimized.

Contributor

magical commented Aug 31, 2018

@davecheney I'm wondering about the expected utility of this optimization - what situations is it expected to arise in? How common are they? Is this explained in the presentation?

Thanks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment