Go: cmd/compile: detect divisions that always result in 0

[davecheney]

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

[josharian]

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

[davecheney]

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

[valyala]

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

[gopherbot]

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

[ChrisALiles]

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]

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

[odeke-em]

CL https://go-review.googlesource.com/c/go/+/129759/ hasn't had much movement since August 30th 2018 and due to the questions still pending, I shall punt this to "Unreleased" as Go1.12 will soon be out the door. Please feel free to revert my triaging if so.