From 44343c777ca8c02262d1d381a2cc24866b3c5414 Mon Sep 17 00:00:00 2001
From: Brian Kessler <brian.m.kessler@gmail.com>
Date: Tue, 23 Apr 2019 22:04:38 -0600
Subject: cmd/compile: add signed divisibility by power of 2 rules
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

For powers of two (c=1<<k), the divisibility check x%c == 0 can be made
just by checking the trailing zeroes via a mask x&(c-1) == 0 even for signed
integers. This avoids division fix-ups when just divisibility check is needed.

To apply this rule, we match on the fixed-up version of the division. This is
neccessary because the mod and division rewrite rules are already applied
during the initial opt pass.

The speed up on amd64 due to elimination of unneccessary fix-up code is ~55%:

name                     old time/op  new time/op  delta
DivconstI64-4            2.08ns ± 0%  2.09ns ± 1%     ~     (p=0.730 n=5+5)
DivisiblePow2constI64-4  1.78ns ± 1%  0.81ns ± 1%  -54.66%  (p=0.008 n=5+5)
DivconstU64-4            2.08ns ± 0%  2.08ns ± 0%     ~     (p=0.683 n=5+5)
DivconstI32-4            1.53ns ± 0%  1.53ns ± 1%     ~     (p=0.968 n=4+5)
DivisiblePow2constI32-4  1.79ns ± 1%  0.81ns ± 1%  -54.97%  (p=0.008 n=5+5)
DivconstU32-4            1.78ns ± 1%  1.80ns ± 2%     ~     (p=0.206 n=5+5)
DivconstI16-4            1.54ns ± 2%  1.54ns ± 0%     ~     (p=0.238 n=5+4)
DivisiblePow2constI16-4  1.78ns ± 0%  0.81ns ± 1%  -54.72%  (p=0.000 n=4+5)
DivconstU16-4            1.00ns ± 5%  1.01ns ± 1%     ~     (p=0.119 n=5+5)
DivconstI8-4             1.54ns ± 0%  1.54ns ± 2%     ~     (p=0.571 n=4+5)
DivisiblePow2constI8-4   1.78ns ± 0%  0.82ns ± 8%  -53.71%  (p=0.008 n=5+5)
DivconstU8-4             0.93ns ± 1%  0.93ns ± 1%     ~     (p=0.643 n=5+5)

A follow-up CL will address the general case of x%c == 0 for signed integers.

Updates #15806

Change-Id: Iabadbbe369b6e0998c8ce85d038ebc236142e42a
Reviewed-on: https://go-review.googlesource.com/c/go/+/173557
Run-TryBot: Brian Kessler <brian.m.kessler@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
---
 test/codegen/arithmetic.go | 21 +++++++++++++++++----
 1 file changed, 17 insertions(+), 4 deletions(-)

(limited to 'test/codegen/arithmetic.go')

diff --git a/test/codegen/arithmetic.go b/test/codegen/arithmetic.go
index b5976be9d2..a937be7fe5 100644
--- a/test/codegen/arithmetic.go
+++ b/test/codegen/arithmetic.go
@@ -176,15 +176,28 @@ func Pow2Mods(n1 uint, n2 int) (uint, int) {
 	// ppc64le:"ANDCC\t[$]31"
 	a := n1 % 32 // unsigned
 
-	// 386:-"IDIVL"
-	// amd64:-"IDIVQ"
-	// arm:-".*udiv"
-	// arm64:-"REM"
+	// 386:"SHRL",-"IDIVL"
+	// amd64:"SHRQ",-"IDIVQ"
+	// arm:"SRA",-".*udiv"
+	// arm64:"ASR",-"REM"
+	// ppc64:"SRAD"
+	// ppc64le:"SRAD"
 	b := n2 % 64 // signed
 
 	return a, b
 }
 
+// Check that signed divisibility checks get converted to AND on low bits
+func Pow2DivisibleSigned(n int) bool {
+	// 386:"TESTL\t[$]63",-"DIVL",-"SHRL"
+	// amd64:"TESTQ\t[$]63",-"DIVQ",-"SHRQ"
+	// arm:"AND\t[$]63",-".*udiv",-"SRA"
+	// arm64:"AND\t[$]63",-"UDIV",-"ASR"
+	// ppc64:"ANDCC\t[$]63",-"SRAD"
+	// ppc64le:"ANDCC\t[$]63",-"SRAD"
+	return n%64 == 0 // signed
+}
+
 // Check that constant modulo divs get turned into MULs
 func ConstMods(n1 uint, n2 int) (uint, int) {
 	// amd64:"MOVQ\t[$]-1085102592571150095","MULQ",-"DIVQ"
-- 
cgit v1.2.1