summaryrefslogtreecommitdiffstats
path: root/src/cmd/compile/internal/ssa/magic_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/cmd/compile/internal/ssa/magic_test.go')
-rw-r--r--src/cmd/compile/internal/ssa/magic_test.go410
1 files changed, 410 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/magic_test.go b/src/cmd/compile/internal/ssa/magic_test.go
new file mode 100644
index 0000000..7c6009d
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/magic_test.go
@@ -0,0 +1,410 @@
+// Copyright 2017 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package ssa
+
+import (
+ "math/big"
+ "testing"
+)
+
+func TestMagicExhaustive8(t *testing.T) {
+ testMagicExhaustive(t, 8)
+}
+func TestMagicExhaustive8U(t *testing.T) {
+ testMagicExhaustiveU(t, 8)
+}
+func TestMagicExhaustive16(t *testing.T) {
+ if testing.Short() {
+ t.Skip("slow test; skipping")
+ }
+ testMagicExhaustive(t, 16)
+}
+func TestMagicExhaustive16U(t *testing.T) {
+ if testing.Short() {
+ t.Skip("slow test; skipping")
+ }
+ testMagicExhaustiveU(t, 16)
+}
+
+// exhaustive test of magic for n bits
+func testMagicExhaustive(t *testing.T, n uint) {
+ min := -int64(1) << (n - 1)
+ max := int64(1) << (n - 1)
+ for c := int64(1); c < max; c++ {
+ if !smagicOK(n, int64(c)) {
+ continue
+ }
+ m := int64(smagic(n, c).m)
+ s := smagic(n, c).s
+ for i := min; i < max; i++ {
+ want := i / c
+ got := (i * m) >> (n + uint(s))
+ if i < 0 {
+ got++
+ }
+ if want != got {
+ t.Errorf("signed magic wrong for %d / %d: got %d, want %d (m=%d,s=%d)\n", i, c, got, want, m, s)
+ }
+ }
+ }
+}
+func testMagicExhaustiveU(t *testing.T, n uint) {
+ max := uint64(1) << n
+ for c := uint64(1); c < max; c++ {
+ if !umagicOK(n, int64(c)) {
+ continue
+ }
+ m := umagic(n, int64(c)).m
+ s := umagic(n, int64(c)).s
+ for i := uint64(0); i < max; i++ {
+ want := i / c
+ got := (i * (max + m)) >> (n + uint(s))
+ if want != got {
+ t.Errorf("unsigned magic wrong for %d / %d: got %d, want %d (m=%d,s=%d)\n", i, c, got, want, m, s)
+ }
+ }
+ }
+}
+
+func TestMagicUnsigned(t *testing.T) {
+ One := new(big.Int).SetUint64(1)
+ for _, n := range [...]uint{8, 16, 32, 64} {
+ TwoN := new(big.Int).Lsh(One, n)
+ Max := new(big.Int).Sub(TwoN, One)
+ for _, c := range [...]uint64{
+ 3,
+ 5,
+ 6,
+ 7,
+ 9,
+ 10,
+ 11,
+ 12,
+ 13,
+ 14,
+ 15,
+ 17,
+ 1<<8 - 1,
+ 1<<8 + 1,
+ 1<<16 - 1,
+ 1<<16 + 1,
+ 1<<32 - 1,
+ 1<<32 + 1,
+ 1<<64 - 1,
+ } {
+ if c>>n != 0 {
+ continue // not appropriate for the given n.
+ }
+ if !umagicOK(n, int64(c)) {
+ t.Errorf("expected n=%d c=%d to pass\n", n, c)
+ }
+ m := umagic(n, int64(c)).m
+ s := umagic(n, int64(c)).s
+
+ C := new(big.Int).SetUint64(c)
+ M := new(big.Int).SetUint64(m)
+ M.Add(M, TwoN)
+
+ // Find largest multiple of c.
+ Mul := new(big.Int).Div(Max, C)
+ Mul.Mul(Mul, C)
+ mul := Mul.Uint64()
+
+ // Try some input values, mostly around multiples of c.
+ for _, x := range [...]uint64{0, 1,
+ c - 1, c, c + 1,
+ 2*c - 1, 2 * c, 2*c + 1,
+ mul - 1, mul, mul + 1,
+ uint64(1)<<n - 1,
+ } {
+ X := new(big.Int).SetUint64(x)
+ if X.Cmp(Max) > 0 {
+ continue
+ }
+ Want := new(big.Int).Quo(X, C)
+ Got := new(big.Int).Mul(X, M)
+ Got.Rsh(Got, n+uint(s))
+ if Want.Cmp(Got) != 0 {
+ t.Errorf("umagic for %d/%d n=%d doesn't work, got=%s, want %s\n", x, c, n, Got, Want)
+ }
+ }
+ }
+ }
+}
+
+func TestMagicSigned(t *testing.T) {
+ One := new(big.Int).SetInt64(1)
+ for _, n := range [...]uint{8, 16, 32, 64} {
+ TwoNMinusOne := new(big.Int).Lsh(One, n-1)
+ Max := new(big.Int).Sub(TwoNMinusOne, One)
+ Min := new(big.Int).Neg(TwoNMinusOne)
+ for _, c := range [...]int64{
+ 3,
+ 5,
+ 6,
+ 7,
+ 9,
+ 10,
+ 11,
+ 12,
+ 13,
+ 14,
+ 15,
+ 17,
+ 1<<7 - 1,
+ 1<<7 + 1,
+ 1<<15 - 1,
+ 1<<15 + 1,
+ 1<<31 - 1,
+ 1<<31 + 1,
+ 1<<63 - 1,
+ } {
+ if c>>(n-1) != 0 {
+ continue // not appropriate for the given n.
+ }
+ if !smagicOK(n, int64(c)) {
+ t.Errorf("expected n=%d c=%d to pass\n", n, c)
+ }
+ m := smagic(n, int64(c)).m
+ s := smagic(n, int64(c)).s
+
+ C := new(big.Int).SetInt64(c)
+ M := new(big.Int).SetUint64(m)
+
+ // Find largest multiple of c.
+ Mul := new(big.Int).Div(Max, C)
+ Mul.Mul(Mul, C)
+ mul := Mul.Int64()
+
+ // Try some input values, mostly around multiples of c.
+ for _, x := range [...]int64{
+ -1, 1,
+ -c - 1, -c, -c + 1, c - 1, c, c + 1,
+ -2*c - 1, -2 * c, -2*c + 1, 2*c - 1, 2 * c, 2*c + 1,
+ -mul - 1, -mul, -mul + 1, mul - 1, mul, mul + 1,
+ int64(1)<<(n-1) - 1, -int64(1) << (n - 1),
+ } {
+ X := new(big.Int).SetInt64(x)
+ if X.Cmp(Min) < 0 || X.Cmp(Max) > 0 {
+ continue
+ }
+ Want := new(big.Int).Quo(X, C)
+ Got := new(big.Int).Mul(X, M)
+ Got.Rsh(Got, n+uint(s))
+ if x < 0 {
+ Got.Add(Got, One)
+ }
+ if Want.Cmp(Got) != 0 {
+ t.Errorf("smagic for %d/%d n=%d doesn't work, got=%s, want %s\n", x, c, n, Got, Want)
+ }
+ }
+ }
+ }
+}
+
+func testDivisibleExhaustiveU(t *testing.T, n uint) {
+ maxU := uint64(1) << n
+ for c := uint64(1); c < maxU; c++ {
+ if !udivisibleOK(n, int64(c)) {
+ continue
+ }
+ k := udivisible(n, int64(c)).k
+ m := udivisible(n, int64(c)).m
+ max := udivisible(n, int64(c)).max
+ mask := ^uint64(0) >> (64 - n)
+ for i := uint64(0); i < maxU; i++ {
+ want := i%c == 0
+ mul := (i * m) & mask
+ rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
+ got := rot <= max
+ if want != got {
+ t.Errorf("unsigned divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,max=%d)\n", i, c, got, want, k, m, max)
+ }
+ }
+ }
+}
+
+func TestDivisibleExhaustive8U(t *testing.T) {
+ testDivisibleExhaustiveU(t, 8)
+}
+
+func TestDivisibleExhaustive16U(t *testing.T) {
+ if testing.Short() {
+ t.Skip("slow test; skipping")
+ }
+ testDivisibleExhaustiveU(t, 16)
+}
+
+func TestDivisibleUnsigned(t *testing.T) {
+ One := new(big.Int).SetUint64(1)
+ for _, n := range [...]uint{8, 16, 32, 64} {
+ TwoN := new(big.Int).Lsh(One, n)
+ Max := new(big.Int).Sub(TwoN, One)
+ for _, c := range [...]uint64{
+ 3,
+ 5,
+ 6,
+ 7,
+ 9,
+ 10,
+ 11,
+ 12,
+ 13,
+ 14,
+ 15,
+ 17,
+ 1<<8 - 1,
+ 1<<8 + 1,
+ 1<<16 - 1,
+ 1<<16 + 1,
+ 1<<32 - 1,
+ 1<<32 + 1,
+ 1<<64 - 1,
+ } {
+ if c>>n != 0 {
+ continue // c too large for the given n.
+ }
+ if !udivisibleOK(n, int64(c)) {
+ t.Errorf("expected n=%d c=%d to pass\n", n, c)
+ }
+ k := udivisible(n, int64(c)).k
+ m := udivisible(n, int64(c)).m
+ max := udivisible(n, int64(c)).max
+ mask := ^uint64(0) >> (64 - n)
+
+ C := new(big.Int).SetUint64(c)
+
+ // Find largest multiple of c.
+ Mul := new(big.Int).Div(Max, C)
+ Mul.Mul(Mul, C)
+ mul := Mul.Uint64()
+
+ // Try some input values, mostly around multiples of c.
+ for _, x := range [...]uint64{0, 1,
+ c - 1, c, c + 1,
+ 2*c - 1, 2 * c, 2*c + 1,
+ mul - 1, mul, mul + 1,
+ uint64(1)<<n - 1,
+ } {
+ X := new(big.Int).SetUint64(x)
+ if X.Cmp(Max) > 0 {
+ continue
+ }
+ want := x%c == 0
+ mul := (x * m) & mask
+ rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
+ got := rot <= max
+ if want != got {
+ t.Errorf("unsigned divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,max=%d)\n", x, c, got, want, k, m, max)
+ }
+ }
+ }
+ }
+}
+
+func testDivisibleExhaustive(t *testing.T, n uint) {
+ minI := -int64(1) << (n - 1)
+ maxI := int64(1) << (n - 1)
+ for c := int64(1); c < maxI; c++ {
+ if !sdivisibleOK(n, int64(c)) {
+ continue
+ }
+ k := sdivisible(n, int64(c)).k
+ m := sdivisible(n, int64(c)).m
+ a := sdivisible(n, int64(c)).a
+ max := sdivisible(n, int64(c)).max
+ mask := ^uint64(0) >> (64 - n)
+ for i := minI; i < maxI; i++ {
+ want := i%c == 0
+ mul := (uint64(i)*m + a) & mask
+ rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
+ got := rot <= max
+ if want != got {
+ t.Errorf("signed divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,a=%d,max=%d)\n", i, c, got, want, k, m, a, max)
+ }
+ }
+ }
+}
+
+func TestDivisibleExhaustive8(t *testing.T) {
+ testDivisibleExhaustive(t, 8)
+}
+
+func TestDivisibleExhaustive16(t *testing.T) {
+ if testing.Short() {
+ t.Skip("slow test; skipping")
+ }
+ testDivisibleExhaustive(t, 16)
+}
+
+func TestDivisibleSigned(t *testing.T) {
+ One := new(big.Int).SetInt64(1)
+ for _, n := range [...]uint{8, 16, 32, 64} {
+ TwoNMinusOne := new(big.Int).Lsh(One, n-1)
+ Max := new(big.Int).Sub(TwoNMinusOne, One)
+ Min := new(big.Int).Neg(TwoNMinusOne)
+ for _, c := range [...]int64{
+ 3,
+ 5,
+ 6,
+ 7,
+ 9,
+ 10,
+ 11,
+ 12,
+ 13,
+ 14,
+ 15,
+ 17,
+ 1<<7 - 1,
+ 1<<7 + 1,
+ 1<<15 - 1,
+ 1<<15 + 1,
+ 1<<31 - 1,
+ 1<<31 + 1,
+ 1<<63 - 1,
+ } {
+ if c>>(n-1) != 0 {
+ continue // not appropriate for the given n.
+ }
+ if !sdivisibleOK(n, int64(c)) {
+ t.Errorf("expected n=%d c=%d to pass\n", n, c)
+ }
+ k := sdivisible(n, int64(c)).k
+ m := sdivisible(n, int64(c)).m
+ a := sdivisible(n, int64(c)).a
+ max := sdivisible(n, int64(c)).max
+ mask := ^uint64(0) >> (64 - n)
+
+ C := new(big.Int).SetInt64(c)
+
+ // Find largest multiple of c.
+ Mul := new(big.Int).Div(Max, C)
+ Mul.Mul(Mul, C)
+ mul := Mul.Int64()
+
+ // Try some input values, mostly around multiples of c.
+ for _, x := range [...]int64{
+ -1, 1,
+ -c - 1, -c, -c + 1, c - 1, c, c + 1,
+ -2*c - 1, -2 * c, -2*c + 1, 2*c - 1, 2 * c, 2*c + 1,
+ -mul - 1, -mul, -mul + 1, mul - 1, mul, mul + 1,
+ int64(1)<<(n-1) - 1, -int64(1) << (n - 1),
+ } {
+ X := new(big.Int).SetInt64(x)
+ if X.Cmp(Min) < 0 || X.Cmp(Max) > 0 {
+ continue
+ }
+ want := x%c == 0
+ mul := (uint64(x)*m + a) & mask
+ rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
+ got := rot <= max
+ if want != got {
+ t.Errorf("signed divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,a=%d,max=%d)\n", x, c, got, want, k, m, a, max)
+ }
+ }
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-27 04:19:16 +0000