cmd/compile: add signed divisibility rules

"Division by invariant integers using multiplication" paper
by Granlund and Montgomery contains a method for directly computing
divisibility (x%c == 0 for c constant) by means of the modular inverse.
The method is further elaborated in "Hacker's Delight" by Warren Section 10-17

This general rule can compute divisibilty by one multiplication, and add
and a compare for odd divisors and an additional rotate for even divisors.

To apply the divisibility rule, we must take into account
the rules to rewrite x%c = x-((x/c)*c) and (x/c) for c constant on the first
optimization pass "opt".  This complicates the matching as we want to match
only in the cases where the result of (x/c) is not also needed.
So, we must match on the expanded form of (x/c) in the expression x == c*(x/c)
in the "late opt" pass after common subexpresion elimination.

Note, that if there is an intermediate opt pass introduced in the future we
could simplify these rules by delaying the magic division rewrite to "late opt"
and matching directly on (x/c) in the intermediate opt pass.

On amd64, the divisibility check is 30-45% faster.

name                     old time/op  new time/op  delta`
DivisiblePow2constI64-4  0.83ns ± 1%  0.82ns ± 0%     ~     (p=0.079 n=5+4)
DivisibleconstI64-4      2.68ns ± 1%  1.87ns ± 0%  -30.33%  (p=0.000 n=5+4)
DivisibleWDivconstI64-4  2.69ns ± 1%  2.71ns ± 3%     ~     (p=1.000 n=5+5)
DivisiblePow2constI32-4  1.15ns ± 1%  1.15ns ± 0%     ~     (p=0.238 n=5+4)
DivisibleconstI32-4      2.24ns ± 1%  1.20ns ± 0%  -46.48%  (p=0.016 n=5+4)
DivisibleWDivconstI32-4  2.27ns ± 1%  2.27ns ± 1%     ~     (p=0.683 n=5+5)
DivisiblePow2constI16-4  0.81ns ± 1%  0.82ns ± 1%     ~     (p=0.135 n=5+5)
DivisibleconstI16-4      2.11ns ± 2%  1.20ns ± 1%  -42.99%  (p=0.008 n=5+5)
DivisibleWDivconstI16-4  2.23ns ± 0%  2.27ns ± 2%   +1.79%  (p=0.029 n=4+4)
DivisiblePow2constI8-4   0.81ns ± 1%  0.81ns ± 1%     ~     (p=0.286 n=5+5)
DivisibleconstI8-4       2.13ns ± 3%  1.19ns ± 1%  -43.84%  (p=0.008 n=5+5)
DivisibleWDivconstI8-4   2.23ns ± 1%  2.25ns ± 1%     ~     (p=0.183 n=5+5)

Fixes #30282
Fixes #15806

Change-Id: Id20d78263a4fdfe0509229ae4dfa2fede83fc1d0
Reviewed-on: https://go-review.googlesource.com/c/go/+/173998
Run-TryBot: Brian Kessler <brian.m.kessler@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

1 files changed, 133 insertions, 21 deletions

diff --git a/src/cmd/compile/internal/gc/testdata/arith_test.go b/src/cmd/compile/internal/gc/testdata/arith_test.go
index 9821095f97..158fedc28e 100644
--- a/src/cmd/compile/internal/gc/testdata/arith_test.go
+++ b/src/cmd/compile/internal/gc/testdata/arith_test.go
@@ -1283,24 +1283,65 @@ func div19_uint64(n uint64) bool {
 	return n%19 == 0
 }
 
+//go:noinline
+func div6_int8(n int8) bool {
+	return n%6 == 0
+}
+
+//go:noinline
+func div6_int16(n int16) bool {
+	return n%6 == 0
+}
+
+//go:noinline
+func div6_int32(n int32) bool {
+	return n%6 == 0
+}
+
+//go:noinline
+func div6_int64(n int64) bool {
+	return n%6 == 0
+}
+
+//go:noinline
+func div19_int8(n int8) bool {
+	return n%19 == 0
+}
+
+//go:noinline
+func div19_int16(n int16) bool {
+	return n%19 == 0
+}
+
+//go:noinline
+func div19_int32(n int32) bool {
+	return n%19 == 0
+}
+
+//go:noinline
+func div19_int64(n int64) bool {
+	return n%19 == 0
+}
+
 // testDivisibility confirms that rewrite rules x%c ==0 for c constant are correct.
 func testDivisibility(t *testing.T) {
+	// unsigned tests
 	// test an even and an odd divisor
-	var six, nineteen uint64 = 6, 19
+	var sixU, nineteenU uint64 = 6, 19
 	// test all inputs for uint8, uint16
 	for i := uint64(0); i <= math.MaxUint16; i++ {
 		if i <= math.MaxUint8 {
-			if want, got := uint8(i)%uint8(six) == 0, div6_uint8(uint8(i)); got != want {
+			if want, got := uint8(i)%uint8(sixU) == 0, div6_uint8(uint8(i)); got != want {
 				t.Errorf("div6_uint8(%d) = %v want %v", i, got, want)
 			}
-			if want, got := uint8(i)%uint8(nineteen) == 0, div19_uint8(uint8(i)); got != want {
+			if want, got := uint8(i)%uint8(nineteenU) == 0, div19_uint8(uint8(i)); got != want {
 				t.Errorf("div6_uint19(%d) = %v want %v", i, got, want)
 			}
 		}
-		if want, got := uint16(i)%uint16(six) == 0, div6_uint16(uint16(i)); got != want {
+		if want, got := uint16(i)%uint16(sixU) == 0, div6_uint16(uint16(i)); got != want {
 			t.Errorf("div6_uint16(%d) = %v want %v", i, got, want)
 		}
-		if want, got := uint16(i)%uint16(nineteen) == 0, div19_uint16(uint16(i)); got != want {
+		if want, got := uint16(i)%uint16(nineteenU) == 0, div19_uint16(uint16(i)); got != want {
 			t.Errorf("div19_uint16(%d) = %v want %v", i, got, want)
 		}
 	}
@@ -1308,35 +1349,106 @@ func testDivisibility(t *testing.T) {
 	// spot check inputs for uint32 and uint64
 	xu := []uint64{
 		0, 1, 2, 3, 4, 5,
-		six, 2 * six, 3 * six, 5 * six, 12345 * six,
-		six + 1, 2*six - 5, 3*six + 3, 5*six + 4, 12345*six - 2,
-		nineteen, 2 * nineteen, 3 * nineteen, 5 * nineteen, 12345 * nineteen,
-		nineteen + 1, 2*nineteen - 5, 3*nineteen + 3, 5*nineteen + 4, 12345*nineteen - 2,
+		sixU, 2 * sixU, 3 * sixU, 5 * sixU, 12345 * sixU,
+		sixU + 1, 2*sixU - 5, 3*sixU + 3, 5*sixU + 4, 12345*sixU - 2,
+		nineteenU, 2 * nineteenU, 3 * nineteenU, 5 * nineteenU, 12345 * nineteenU,
+		nineteenU + 1, 2*nineteenU - 5, 3*nineteenU + 3, 5*nineteenU + 4, 12345*nineteenU - 2,
 		maxU32, maxU32 - 1, maxU32 - 2, maxU32 - 3, maxU32 - 4,
-		maxU32, maxU32 - 5, maxU32 - 6, maxU32 - 7, maxU32 - 8,
-		maxU32, maxU32 - 9, maxU32 - 10, maxU32 - 11, maxU32 - 12,
-		maxU32, maxU32 - 13, maxU32 - 14, maxU32 - 15, maxU32 - 16,
-		maxU32, maxU32 - 17, maxU32 - 18, maxU32 - 19, maxU32 - 20,
+		maxU32 - 5, maxU32 - 6, maxU32 - 7, maxU32 - 8,
+		maxU32 - 9, maxU32 - 10, maxU32 - 11, maxU32 - 12,
+		maxU32 - 13, maxU32 - 14, maxU32 - 15, maxU32 - 16,
+		maxU32 - 17, maxU32 - 18, maxU32 - 19, maxU32 - 20,
 		maxU64, maxU64 - 1, maxU64 - 2, maxU64 - 3, maxU64 - 4,
-		maxU64, maxU64 - 5, maxU64 - 6, maxU64 - 7, maxU64 - 8,
-		maxU64, maxU64 - 9, maxU64 - 10, maxU64 - 11, maxU64 - 12,
-		maxU64, maxU64 - 13, maxU64 - 14, maxU64 - 15, maxU64 - 16,
-		maxU64, maxU64 - 17, maxU64 - 18, maxU64 - 19, maxU64 - 20,
+		maxU64 - 5, maxU64 - 6, maxU64 - 7, maxU64 - 8,
+		maxU64 - 9, maxU64 - 10, maxU64 - 11, maxU64 - 12,
+		maxU64 - 13, maxU64 - 14, maxU64 - 15, maxU64 - 16,
+		maxU64 - 17, maxU64 - 18, maxU64 - 19, maxU64 - 20,
 	}
 	for _, x := range xu {
 		if x <= maxU32 {
-			if want, got := uint32(x)%uint32(six) == 0, div6_uint32(uint32(x)); got != want {
+			if want, got := uint32(x)%uint32(sixU) == 0, div6_uint32(uint32(x)); got != want {
 				t.Errorf("div6_uint32(%d) = %v want %v", x, got, want)
 			}
-			if want, got := uint32(x)%uint32(nineteen) == 0, div19_uint32(uint32(x)); got != want {
+			if want, got := uint32(x)%uint32(nineteenU) == 0, div19_uint32(uint32(x)); got != want {
 				t.Errorf("div19_uint32(%d) = %v want %v", x, got, want)
 			}
 		}
-		if want, got := x%six == 0, div6_uint64(x); got != want {
+		if want, got := x%sixU == 0, div6_uint64(x); got != want {
 			t.Errorf("div6_uint64(%d) = %v want %v", x, got, want)
 		}
-		if want, got := x%nineteen == 0, div19_uint64(x); got != want {
+		if want, got := x%nineteenU == 0, div19_uint64(x); got != want {
 			t.Errorf("div19_uint64(%d) = %v want %v", x, got, want)
 		}
 	}
+
+	// signed tests
+	// test an even and an odd divisor
+	var sixS, nineteenS int64 = 6, 19
+	// test all inputs for int8, int16
+	for i := int64(math.MinInt16); i <= math.MaxInt16; i++ {
+		if math.MinInt8 <= i && i <= math.MaxInt8 {
+			if want, got := int8(i)%int8(sixS) == 0, div6_int8(int8(i)); got != want {
+				t.Errorf("div6_int8(%d) = %v want %v", i, got, want)
+			}
+			if want, got := int8(i)%int8(nineteenS) == 0, div19_int8(int8(i)); got != want {
+				t.Errorf("div6_int19(%d) = %v want %v", i, got, want)
+			}
+		}
+		if want, got := int16(i)%int16(sixS) == 0, div6_int16(int16(i)); got != want {
+			t.Errorf("div6_int16(%d) = %v want %v", i, got, want)
+		}
+		if want, got := int16(i)%int16(nineteenS) == 0, div19_int16(int16(i)); got != want {
+			t.Errorf("div19_int16(%d) = %v want %v", i, got, want)
+		}
+	}
+	var minI32, maxI32, minI64, maxI64 int64 = math.MinInt32, math.MaxInt32, math.MinInt64, math.MaxInt64
+	// spot check inputs for int32 and int64
+	xs := []int64{
+		0, 1, 2, 3, 4, 5,
+		-1, -2, -3, -4, -5,
+		sixS, 2 * sixS, 3 * sixS, 5 * sixS, 12345 * sixS,
+		sixS + 1, 2*sixS - 5, 3*sixS + 3, 5*sixS + 4, 12345*sixS - 2,
+		-sixS, -2 * sixS, -3 * sixS, -5 * sixS, -12345 * sixS,
+		-sixS + 1, -2*sixS - 5, -3*sixS + 3, -5*sixS + 4, -12345*sixS - 2,
+		nineteenS, 2 * nineteenS, 3 * nineteenS, 5 * nineteenS, 12345 * nineteenS,
+		nineteenS + 1, 2*nineteenS - 5, 3*nineteenS + 3, 5*nineteenS + 4, 12345*nineteenS - 2,
+		-nineteenS, -2 * nineteenS, -3 * nineteenS, -5 * nineteenS, -12345 * nineteenS,
+		-nineteenS + 1, -2*nineteenS - 5, -3*nineteenS + 3, -5*nineteenS + 4, -12345*nineteenS - 2,
+		minI32, minI32 + 1, minI32 + 2, minI32 + 3, minI32 + 4,
+		minI32 + 5, minI32 + 6, minI32 + 7, minI32 + 8,
+		minI32 + 9, minI32 + 10, minI32 + 11, minI32 + 12,
+		minI32 + 13, minI32 + 14, minI32 + 15, minI32 + 16,
+		minI32 + 17, minI32 + 18, minI32 + 19, minI32 + 20,
+		maxI32, maxI32 - 1, maxI32 - 2, maxI32 - 3, maxI32 - 4,
+		maxI32 - 5, maxI32 - 6, maxI32 - 7, maxI32 - 8,
+		maxI32 - 9, maxI32 - 10, maxI32 - 11, maxI32 - 12,
+		maxI32 - 13, maxI32 - 14, maxI32 - 15, maxI32 - 16,
+		maxI32 - 17, maxI32 - 18, maxI32 - 19, maxI32 - 20,
+		minI64, minI64 + 1, minI64 + 2, minI64 + 3, minI64 + 4,
+		minI64 + 5, minI64 + 6, minI64 + 7, minI64 + 8,
+		minI64 + 9, minI64 + 10, minI64 + 11, minI64 + 12,
+		minI64 + 13, minI64 + 14, minI64 + 15, minI64 + 16,
+		minI64 + 17, minI64 + 18, minI64 + 19, minI64 + 20,
+		maxI64, maxI64 - 1, maxI64 - 2, maxI64 - 3, maxI64 - 4,
+		maxI64 - 5, maxI64 - 6, maxI64 - 7, maxI64 - 8,
+		maxI64 - 9, maxI64 - 10, maxI64 - 11, maxI64 - 12,
+		maxI64 - 13, maxI64 - 14, maxI64 - 15, maxI64 - 16,
+		maxI64 - 17, maxI64 - 18, maxI64 - 19, maxI64 - 20,
+	}
+	for _, x := range xs {
+		if minI32 <= x && x <= maxI32 {
+			if want, got := int32(x)%int32(sixS) == 0, div6_int32(int32(x)); got != want {
+				t.Errorf("div6_int32(%d) = %v want %v", x, got, want)
+			}
+			if want, got := int32(x)%int32(nineteenS) == 0, div19_int32(int32(x)); got != want {
+				t.Errorf("div19_int32(%d) = %v want %v", x, got, want)
+			}
+		}
+		if want, got := x%sixS == 0, div6_int64(x); got != want {
+			t.Errorf("div6_int64(%d) = %v want %v", x, got, want)
+		}
+		if want, got := x%nineteenS == 0, div19_int64(x); got != want {
+			t.Errorf("div19_int64(%d) = %v want %v", x, got, want)
+		}
+	}
 }