cmd/compile: optimize int % powerOfTwo != 0

[rillig]

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]

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]

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]

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