From 49621cc311a41b71f60f03202f3872c0633cac59 Mon Sep 17 00:00:00 2001
From: Jorropo <jorropo.pgm@gmail.com>
Date: Fri, 9 Aug 2024 15:45:39 +0200
Subject: [PATCH] cmd/compile: compute XOR's limits from argument's limits

This help to optimize code like this:

  func f(buckets *[512]bucket, v value) {
    a, b := v.computeSomething()
    // assume a and b are proved < 512
    b := &buckets[a ^ b] // pick a random bucket
    b.store(v)
  }

Change-Id: I1acf702f5a8137f9ded49081b4703922879b0288
Reviewed-on: https://go-review.googlesource.com/c/go/+/604455
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: David Chase <drchase@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
---
 src/cmd/compile/internal/ssa/prove.go | 10 ++++++++--
 test/prove.go                         | 18 ++++++++++++++++++
 2 files changed, 26 insertions(+), 2 deletions(-)

diff --git a/src/cmd/compile/internal/ssa/prove.go b/src/cmd/compile/internal/ssa/prove.go
index 1daf8d85c4..5195a48608 100644
--- a/src/cmd/compile/internal/ssa/prove.go
+++ b/src/cmd/compile/internal/ssa/prove.go
@@ -1688,6 +1688,10 @@ func (ft *factsTable) flowLimit(v *Value) bool {
 			uint64(bits.Len8(uint8(a.umax))))
 
 	// Masks.
+
+	// TODO: if y.umax and y.umin share a leading bit pattern, y also has that leading bit pattern.
+	// we could compare the patterns of always set bits in a and b and learn more about minimum and maximum.
+	// But I doubt this help any real world code.
 	case OpAnd64, OpAnd32, OpAnd16, OpAnd8:
 		// AND can only make the value smaller.
 		a := ft.limits[v.Args[0].ID]
@@ -1699,8 +1703,10 @@ func (ft *factsTable) flowLimit(v *Value) bool {
 		b := ft.limits[v.Args[1].ID]
 		return ft.unsignedMin(v, maxU(a.umin, b.umin))
 	case OpXor64, OpXor32, OpXor16, OpXor8:
-		// TODO: use leading/trailing zeroes?
-		// Not sure if it is worth it.
+		// XOR can't flip bits that are proved to be zero in both inputs.
+		a := ft.limits[v.Args[0].ID]
+		b := ft.limits[v.Args[1].ID]
+		return ft.unsignedMax(v, 1<<bits.Len64(a.umax|b.umax)-1)
 
 	// Arithmetic.
 	case OpAdd64:
diff --git a/test/prove.go b/test/prove.go
index 1bb2ef0db7..2d5d181aa9 100644
--- a/test/prove.go
+++ b/test/prove.go
@@ -1390,6 +1390,24 @@ func bitLen8(x uint8, ensureBothBranchesCouldHappen bool) int {
 	return y
 }
 
+func xor64(a, b uint64, ensureBothBranchesCouldHappen bool) int {
+	a &= 0xff
+	b &= 0xfff
+
+	z := a ^ b
+
+	if ensureBothBranchesCouldHappen {
+		if z > 0xfff { // ERROR "Disproved Less64U$"
+			return 42
+		}
+	} else {
+		if z <= 0xfff { // ERROR "Proved Leq64U$"
+			return 1337
+		}
+	}
+	return int(z)
+}
+
 //go:noinline
 func useInt(a int) {
 }
-- 
2.48.1