Go: 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?

~~~go
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:

~none
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:

~none
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 https://github.com/golang/go/commit/44343c777ca8c02262d1d381a2cc24866b3c5414 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