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

cmd/compile: missed optimization: binary alignment is unnecessarily complex #54496

Closed
piotr-sneller opened this issue Aug 17, 2022 · 3 comments
Closed
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone

Comments

@piotr-sneller
Copy link

piotr-sneller commented Aug 17, 2022

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

1.19

Does this issue reproduce with the latest release?

yes

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

amd64/windows

If binary alignment like in the function below is encountered, the compiler correctly strength reduces the division/multiplication to shifts, but then fails to combine them into a single `and`. In general `(x >> N) << N` should be further folded to `x & -(1 << N)` for constant N during strength reduction

What did you do?

package testcase

func foo(x uint) uint {
    return x / 64 * 64
}

Compile:
go tool compile -S t1.go

Output:

<unlinkable>.foo STEXT nosplit size=9 args=0x8 locals=0x0 funcid=0x0 align=0x0                  
        0x0000 00000 (t1.go:4)  TEXT    <unlinkable>.foo(SB), NOSPLIT|ABIInternal, $0-8         
        0x0000 00000 (t1.go:4)  FUNCDATA        $0, gclocals·g2BeySu+wFnoycgXfElmcg==(SB)       
        0x0000 00000 (t1.go:4)  FUNCDATA        $1, gclocals·g2BeySu+wFnoycgXfElmcg==(SB)       
        0x0000 00000 (t1.go:4)  FUNCDATA        $5, <unlinkable>.foo.arginfo1(SB)               
        0x0000 00000 (t1.go:4)  FUNCDATA        $6, <unlinkable>.foo.argliveinfo(SB)            
        0x0000 00000 (t1.go:4)  PCDATA  $3, $1                                                  
        0x0000 00000 (t1.go:5)  SHRQ    $6, AX <= here                                              
        0x0004 00004 (t1.go:5)  SHLQ    $6, AX <= here                                                   
        0x0008 00008 (t1.go:5)  RET   

What did you expect to see?

ANDQ $FFFFFFFFFFFFFFC0, AX

What did you see instead?

SHRQ    $6, AX
SHLQ    $6, AX
@seankhliao seankhliao changed the title missed optimization: binary alignment is unnecessarily complex cmd/compile: missed optimization: binary alignment is unnecessarily complex Aug 17, 2022
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Aug 17, 2022
@seankhliao seankhliao added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Aug 17, 2022
@randall77
Copy link
Contributor

randall77 commented Aug 17, 2022

We used to do the optimization in the other direction (and => 2 shifts) because it uses one less register in the case where the constant needs to be materialized (e.g. >>48<<48).
That was removed in https://go-review.googlesource.com/c/go/+/196810/ , but we didn't add the (2 shifts => and) rule. We probably should.

We do handle >>1<<1 with BTR.

@martisch

@randall77 randall77 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 Aug 17, 2022
@randall77 randall77 added this to the Unplanned milestone Aug 17, 2022
@martisch
Copy link
Contributor

martisch commented Aug 17, 2022

For the same reasons that https://go-review.googlesource.com/c/go/+/196810/ prefers and over 2 shifts I think we should actively rewrite shifts to ANDs where it is possible. One pitfall I can see is that we need to make sure this does not interfere with other better shift merging rules if there are any. Would be an optimization in the category todo as late as possible in an extra pass.

If noone wants to tackle this before e.g. as an entry to go ssa rules optmization, I can likely have a try at this sometime in the next 2 weeks.

@gopherbot
Copy link

gopherbot commented Aug 18, 2022

Change https://go.dev/cl/424856 mentions this issue: cmd/compile: rewrite >>c<<c to &^(1<<c-1)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Development

No branches or pull requests

5 participants