diff options
author | Keith Randall <khr@golang.org> | 2020-05-07 13:44:51 -0700 |
---|---|---|
committer | Keith Randall <khr@golang.org> | 2020-05-11 16:23:52 +0000 |
commit | 2cb10d42b762f5f47dd239a2c114d1840dc5cfbf (patch) | |
tree | 6ffd6de46031e61d0aba4aa874e76ad000cb5775 /test/codegen/arithmetic.go | |
parent | daf39d06ee04414fa962aa61fd0e7bc4ee166bfd (diff) | |
download | go-git-2cb10d42b762f5f47dd239a2c114d1840dc5cfbf.tar.gz |
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 <t> n (Const64 [c])) && isPowerOfTwo(c) ->
(Rsh64x64
(Add64 <t> n (Rsh64Ux64 <t>
(Rsh64x64 <t> n (Const64 <typ.UInt64> [63]))
(Const64 <typ.UInt64> [64-log2(c)])))
(Const64 <typ.UInt64> [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 <typ.UInt64> [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 <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
Diffstat (limited to 'test/codegen/arithmetic.go')
-rw-r--r-- | test/codegen/arithmetic.go | 11 |
1 files changed, 11 insertions, 0 deletions
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 +} |