From 73df946d56c74384511a194dd01dbe099584fd1a Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 15:14:23 +0200 Subject: Adding upstream version 1.16.10. Signed-off-by: Daniel Baumann --- src/cmd/compile/internal/ssa/magic_test.go | 410 +++++++++++++++++++++++++++++ 1 file changed, 410 insertions(+) create mode 100644 src/cmd/compile/internal/ssa/magic_test.go (limited to 'src/cmd/compile/internal/ssa/magic_test.go') 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)< 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)< 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) + } + } + } + } +} -- cgit v1.2.3