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: optimize int % powerOfTwo != 0 #34166

Closed
rillig opened this issue Sep 7, 2019 · 3 comments
Closed

cmd/compile: optimize int % powerOfTwo != 0 #34166

rillig opened this issue Sep 7, 2019 · 3 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone

Comments

@rillig
Copy link
Contributor

rillig commented Sep 7, 2019

What version of Go are you using?

go version go1.12.7 windows/amd64

What did you do?

func bitTestArith(i int) int {
	if i%2 != 0 {
		return 1
	}
	return 0
}

func bitTestBinary(i int) int {
	if i&1 != 0 {
		return 1
	}
	return 0
}

What did you expect to see?

The two conditions in the if statements compile to the same code.

What did you see instead?

The first condition is compiled to:

movq     0x8(sp), ax
movq     ax, cx
shrq     $0x3f, ax
addq     cx, ax
sarq     $0x1, ax
shlq     $0x1, ax
cmpq     ax, cx
je       0x1b9dbb (line 13, varalignblock.go:713)

The second condition is compiled to:

movq     0x8(sp), ax
btl      $0x0, ax
jae      0x1b9df1 (line 24, varalignblock.go:720)
@niaow
Copy link

niaow commented Sep 8, 2019

Context on why this currently happens:

For unsigned types, we do the optimization x % c -> x & k, since these operations will both produce the same results. However, this does not work on signed types where x can be negative. For instance -1%2 == -1 and -1&1 == 1.

However, since you are comparing with 0, we can safely say that we do not care about the sign. Therefore, we have the property that x % c != 0 is equivalent to uint(x) % uint(c) != 0 where c is a power of 2. If c is negative, we can safely flip the sign of it here.

@bmkessler
Copy link
Contributor

Note 44343c7 added rules for signed divisibility checks for powers of two, i.e. x%(1<<k) == 0 So that

func bitTestArith(i int) int {
	if i%2 == 0 {
		return 0
	}
	return 1
}

func bitTestBinary(i int) int {
	if i&1 == 0 {
		return 0
	}
	return 1
}

func bitTestNegArith(i int) int {
	if !(i%2 == 0) {
		return 1
	}
	return 0
}

all compile identically using go 1.13 https://godbolt.org/z/bhDShH. Adding the not divisible rules is just identical copies of the existing rules but matching the not equal condition.

@gopherbot
Copy link

Change https://golang.org/cl/194219 mentions this issue: cmd/compile: add signed indivisibility by power of 2 rules

@FiloSottile FiloSottile added this to the Go1.14 milestone Sep 10, 2019
@FiloSottile FiloSottile added the NeedsFix The path to resolution is known, but the work has not been done. label Sep 10, 2019
@rsc rsc modified the milestones: Go1.14, Backlog Oct 9, 2019
@golang golang locked and limited conversation to collaborators Nov 6, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Development

No branches or pull requests

7 participants