From 2cb10d42b762f5f47dd239a2c114d1840dc5cfbf Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Thu, 7 May 2020 13:44:51 -0700 Subject: cmd/compile: in prove, zero right shifts of positive int by #bits - 1 Taking over Zach's CL 212277. Just cleaned up and added a test. For a positive, signed integer, an arithmetic right shift of count (bit-width - 1) equals zero. e.g. int64(22) >> 63 -> 0. This CL makes prove replace these right shifts with a zero-valued constant. These shifts may arise in source code explicitly, but can also be created by the generic rewrite of signed division by a power of 2. // Signed divide by power of 2. // n / c = n >> log(c) if n >= 0 // = (n+c-1) >> log(c) if n < 0 // We conditionally add c-1 by adding n>>63>>(64-log(c)) (first shift signed, second shift unsigned). (Div64 n (Const64 [c])) && isPowerOfTwo(c) -> (Rsh64x64 (Add64 n (Rsh64Ux64 (Rsh64x64 n (Const64 [63])) (Const64 [64-log2(c)]))) (Const64 [log2(c)])) If n is known to be positive, this rewrite includes an extra Add and 2 extra Rsh. This CL will allow prove to replace one of the extra Rsh with a 0. That replacement then allows lateopt to remove all the unneccesary fixups from the generic rewrite. There is a rewrite rule to handle this case directly: (Div64 n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo(c) -> (Rsh64Ux64 n (Const64 [log2(c)])) But this implementation of isNonNegative really only handles constants and a few special operations like len/cap. The division could be handled if the factsTable version of isNonNegative were available. Unfortunately, the first opt pass happens before prove even has a chance to deduce the numerator is non-negative, so the generic rewrite has already fired and created the extra Ops discussed above. Fixes #36159 By Printf count, this zeroes 137 right shifts when building std and cmd. Change-Id: Iab486910ac9d7cfb86ace2835456002732b384a2 Reviewed-on: https://go-review.googlesource.com/c/go/+/232857 Run-TryBot: Keith Randall TryBot-Result: Gobot Gobot Reviewed-by: Cherry Zhang --- test/codegen/arithmetic.go | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'test/codegen/arithmetic.go') diff --git a/test/codegen/arithmetic.go b/test/codegen/arithmetic.go index a076664e8e..8f25974376 100644 --- a/test/codegen/arithmetic.go +++ b/test/codegen/arithmetic.go @@ -451,3 +451,14 @@ func addSpecial(a, b, c uint32) (uint32, uint32, uint32) { c += 128 return a, b, c } + + +// Divide -> shift rules usually require fixup for negative inputs. +// If the input is non-negative, make sure the fixup is eliminated. +func divInt(v int64) int64 { + if v < 0 { + return 0 + } + // amd64:-`.*SARQ.*63,`, -".*SHRQ", ".*SARQ.*[$]9," + return v / 512 +} -- cgit v1.3