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: arithmetic optimization for shifts #69635

Closed
StefanEnspired opened this issue Sep 26, 2024 · 5 comments
Closed

cmd/compile: arithmetic optimization for shifts #69635

StefanEnspired opened this issue Sep 26, 2024 · 5 comments
Labels
FixPending Issues that have a fix which has not yet been reviewed or submitted. NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone

Comments

@StefanEnspired
Copy link

Proposal Details

I have a simple expression optimization suggestion that I noticed in some of my code. The minimal snippet that produces the offending code is this:

func calc(a uint64) uint64 {
	v := a >> 20 & 0x7f
	return v << 3
}

In my actual code, the calculation on the first line is actually happening in another (inlined) function; this terser version leads to the same result:

SHRQ $20, AX
ANDL $127, AX
SHLQ $3, AX

Obviously, shift left and shift rights do not cancel each other out in the same way as additions and subtractions do, but they are almost close enough. Addition and subtraction will in fact be combined, also in the inlined-function case:

func calc(a uint64) uint64 {
	v := a - 6
	return v + 2
}

ADDQ $-4, AX

For combining shifts in the same way, an additional masking AND would be required, but if it is already there, it can be recycled to efficiently combine the shifts. Actually the operations do not even have to oppose each other. Combining two adds or two shifts in the same direction would work just as well.

For x << i & m >> j with constants i, j and m, the combined shifting distance d would be i-j (or i+j for << <<, or -i-j for >> >>, .. you get the idea). We would then end up with the optimized version:

x DIR-SHIFT d & (m SH j)

where DIR-SHIFT is the idealized shift operation in either direction depending on the polarity of d,
and SH is whatever the original second shift direction was.

The final result for the original function would thus be:

SHRQ $17, AX
ANDL $1016, AX
@gopherbot gopherbot added this to the Proposal milestone Sep 26, 2024
@ianlancetaylor
Copy link
Member

There are no API changes here, so taking this out of the proposal process.

@ianlancetaylor ianlancetaylor changed the title proposal: cmd/compile: Arithmetic optimization for shifts cmd/compile: arithmetic optimization for shifts Sep 26, 2024
@ianlancetaylor ianlancetaylor added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. and removed Proposal labels Sep 26, 2024
@ianlancetaylor ianlancetaylor modified the milestones: Proposal, Backlog Sep 26, 2024
@randall77
Copy link
Contributor

Sounds reasonable.

Note that this depends on architecture. On arm64 it is already just 2 instructions.

UBFX	$20, R0, $7, R1
LSL	$3, R1, R0

@StefanEnspired
Copy link
Author

Note that this depends on architecture. On arm64 it is already just 2 instructions.

Only for "nice" mask constants, though.

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/621357 mentions this issue: cmd/compile: arithmetic optimization for shifts

@dmitshur dmitshur added NeedsFix The path to resolution is known, but the work has not been done. FixPending Issues that have a fix which has not yet been reviewed or submitted. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Oct 21, 2024
@dmitshur dmitshur modified the milestones: Backlog, Go1.24 Oct 21, 2024
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/621755 mentions this issue: cmd/compile: add shift optimization test

gopherbot pushed a commit that referenced this issue Oct 25, 2024
For #69635

Change-Id: Id5696dc9724c3b3afcd7b60a6994f98c5309eb0e
Reviewed-on: https://go-review.googlesource.com/c/go/+/621755
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Michael Pratt <mpratt@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Michael Pratt <mpratt@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
FixPending Issues that have a fix which has not yet been reviewed or submitted. 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