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: detect divisions that always result in 0 #25733

Open
davecheney opened this issue Jun 5, 2018 · 7 comments
Open

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

davecheney opened this issue Jun 5, 2018 · 7 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. Performance
Milestone
Unreleased

Comments

@davecheney
Copy link
Contributor

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

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

@FiloSottile FiloSottile changed the title cmd/compile: missed optimisation cmd/compile: detect divisions that always result in 0 Jun 5, 2018
@davecheney
Copy link
Contributor Author

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

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

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

@ChrisALiles
Copy link
Contributor

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

@odeke-em
Copy link
Member

odeke-em commented Feb 3, 2019

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.

@odeke-em odeke-em modified the milestones: Go1.12, Unreleased Feb 3, 2019
@ALTree ALTree added the NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. label Oct 12, 2020
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. Performance
Projects
Go Compiler / Runtime
Status: Triage Backlog
Milestone
Unreleased
Development

No branches or pull requests
9 participants
@davecheney @josharian @magical @valyala @ALTree @odeke-em @randall77 @gopherbot @ChrisALiles