cmd/compile: add tests bruteforcing limit negation and improve limit addition

I had to improve addition to make the tests pass.

Change-Id: I4daba2ee0f24a0dbc3929bf9afadd2116e16efae
Reviewed-on: https://go-review.googlesource.com/c/go/+/724600
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Cherry Mui <cherryyz@google.com>
Auto-Submit: Keith Randall <khr@golang.org>
Auto-Submit: Jorropo <jorropo.pgm@gmail.com>
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Keith Randall <khr@golang.org>

2 files changed, 118 insertions, 3 deletions

diff --git a/src/cmd/compile/internal/ssa/prove.go b/src/cmd/compile/internal/ssa/prove.go
index 536965a0a0..1aab7e3eb7 100644
--- a/src/cmd/compile/internal/ssa/prove.go
+++ b/src/cmd/compile/internal/ssa/prove.go
@@ -250,9 +250,51 @@ func fitsInBitsU(x uint64, b uint) bool {
 	return x>>b == 0
 }
 
+func noLimitForBitsize(bitsize uint) limit {
+	return limit{min: -(1 << (bitsize - 1)), max: 1<<(bitsize-1) - 1, umin: 0, umax: 1<<bitsize - 1}
+}
+
+func convertIntWithBitsize[Target uint64 | int64, Source uint64 | int64](x Source, bitsize uint) Target {
+	switch bitsize {
+	case 64:
+		return Target(x)
+	case 32:
+		return Target(int32(x))
+	case 16:
+		return Target(int16(x))
+	case 8:
+		return Target(int8(x))
+	default:
+		panic("unreachable")
+	}
+}
+
 // add returns the limit obtained by adding a value with limit l
 // to a value with limit l2. The result must fit in b bits.
 func (l limit) add(l2 limit, b uint) limit {
+	var isLConst, isL2Const bool
+	var lConst, l2Const uint64
+	if l.min == l.max {
+		isLConst = true
+		lConst = convertIntWithBitsize[uint64](l.min, b)
+	} else if l.umin == l.umax {
+		isLConst = true
+		lConst = l.umin
+	}
+	if l2.min == l2.max {
+		isL2Const = true
+		l2Const = convertIntWithBitsize[uint64](l2.min, b)
+	} else if l2.umin == l2.umax {
+		isL2Const = true
+		l2Const = l2.umin
+	}
+	if isLConst && isL2Const {
+		r := lConst + l2Const
+		r &= (uint64(1) << b) - 1
+		int64r := convertIntWithBitsize[int64](r, b)
+		return limit{min: int64r, max: int64r, umin: r, umax: r}
+	}
+
 	r := noLimit
 	min, minOk := safeAdd(l.min, l2.min, b)
 	max, maxOk := safeAdd(l.max, l2.max, b)
@@ -357,6 +399,11 @@ func (l limit) com(b uint) limit {
 	}
 }
 
+// Similar to add, but computes the negation of the limit for bitsize b.
+func (l limit) neg(b uint) limit {
+	return l.com(b).add(limit{min: 1, max: 1, umin: 1, umax: 1}, b)
+}
+
 var noLimit = limit{math.MinInt64, math.MaxInt64, 0, math.MaxUint64}
 
 // a limitFact is a limit known for a particular value.
@@ -1753,8 +1800,7 @@ func initLimit(v *Value) limit {
 	}
 
 	// Default limits based on type.
-	bitsize := v.Type.Size() * 8
-	lim := limit{min: -(1 << (bitsize - 1)), max: 1<<(bitsize-1) - 1, umin: 0, umax: 1<<bitsize - 1}
+	lim := noLimitForBitsize(uint(v.Type.Size()) * 8)
 
 	// Tighter limits on some opcodes.
 	switch v.Op {
@@ -1949,7 +1995,7 @@ func (ft *factsTable) flowLimit(v *Value) {
 	case OpNeg64, OpNeg32, OpNeg16, OpNeg8:
 		a := ft.limits[v.Args[0].ID]
 		bitsize := uint(v.Type.Size()) * 8
-		ft.newLimit(v, a.com(bitsize).add(limit{min: 1, max: 1, umin: 1, umax: 1}, bitsize))
+		ft.newLimit(v, a.neg(bitsize))
 	case OpMul64, OpMul32, OpMul16, OpMul8:
 		a := ft.limits[v.Args[0].ID]
 		b := ft.limits[v.Args[1].ID]
diff --git a/src/cmd/compile/internal/ssa/prove_test.go b/src/cmd/compile/internal/ssa/prove_test.go
new file mode 100644
index 0000000000..0044b60a16
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/prove_test.go
@@ -0,0 +1,69 @@
+// Copyright 2025 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"
+	"testing"
+)
+
+func testLimitUnaryOpSigned8(t *testing.T, opName string, op func(l limit, bitsize uint) limit, opImpl func(int8) int8) {
+	sizeLimit := noLimitForBitsize(8)
+	for min := math.MinInt8; min <= math.MaxInt8; min++ {
+		for max := min; max <= math.MaxInt8; max++ {
+			realSmallest, realBiggest := int8(math.MaxInt8), int8(math.MinInt8)
+			for i := min; i <= max; i++ {
+				result := opImpl(int8(i))
+				if result < realSmallest {
+					realSmallest = result
+				}
+				if result > realBiggest {
+					realBiggest = result
+				}
+			}
+
+			l := limit{int64(min), int64(max), 0, math.MaxUint64}
+			l = op(l, 8)
+			l = l.intersect(sizeLimit) // We assume this is gonna be used by newLimit which is seeded by the op size already.
+
+			if l.min != int64(realSmallest) || l.max != int64(realBiggest) {
+				t.Errorf("%s(%d..%d) = %d..%d; want %d..%d", opName, min, max, l.min, l.max, realSmallest, realBiggest)
+			}
+		}
+	}
+}
+
+func testLimitUnaryOpUnsigned8(t *testing.T, opName string, op func(l limit, bitsize uint) limit, opImpl func(uint8) uint8) {
+	sizeLimit := noLimitForBitsize(8)
+	for min := 0; min <= math.MaxUint8; min++ {
+		for max := min; max <= math.MaxUint8; max++ {
+			realSmallest, realBiggest := uint8(math.MaxUint8), uint8(0)
+			for i := min; i <= max; i++ {
+				result := opImpl(uint8(i))
+				if result < realSmallest {
+					realSmallest = result
+				}
+				if result > realBiggest {
+					realBiggest = result
+				}
+			}
+
+			l := limit{math.MinInt64, math.MaxInt64, uint64(min), uint64(max)}
+			l = op(l, 8)
+			l = l.intersect(sizeLimit) // We assume this is gonna be used by newLimit which is seeded by the op size already.
+
+			if l.umin != uint64(realSmallest) || l.umax != uint64(realBiggest) {
+				t.Errorf("%s(%d..%d) = %d..%d; want %d..%d", opName, min, max, l.umin, l.umax, realSmallest, realBiggest)
+			}
+		}
+	}
+}
+
+func TestLimitNegSigned(t *testing.T) {
+	testLimitUnaryOpSigned8(t, "neg", limit.neg, func(x int8) int8 { return -x })
+}
+func TestLimitNegUnsigned(t *testing.T) {
+	testLimitUnaryOpUnsigned8(t, "neg", limit.neg, func(x uint8) uint8 { return -x })
+}