cmd/compile: teach prove about len's & cap's max based on the element size

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

2 files changed, 22 insertions, 1 deletions

diff --git a/src/cmd/compile/internal/ssa/prove.go b/src/cmd/compile/internal/ssa/prove.go
index b9b5d3386d..309229b4d7 100644
--- a/src/cmd/compile/internal/ssa/prove.go
+++ b/src/cmd/compile/internal/ssa/prove.go
@@ -1619,7 +1619,16 @@ func initLimit(v *Value) limit {
 		lim = lim.unsignedMax(1)
 
 	// length operations
-	case OpStringLen, OpSliceLen, OpSliceCap:
+	case OpSliceLen, OpSliceCap:
+		f := v.Block.Func
+		elemSize := uint64(v.Args[0].Type.Elem().Size())
+		if elemSize > 0 {
+			heapSize := uint64(1)<<(uint64(f.Config.PtrSize)*8) - 1
+			maximumElementsFittingInHeap := heapSize / elemSize
+			lim = lim.unsignedMax(maximumElementsFittingInHeap)
+		}
+		fallthrough
+	case OpStringLen:
 		lim = lim.signedMin(0)
 	}
 
diff --git a/test/prove.go b/test/prove.go
index ef7690bbde..70a27865cf 100644
--- a/test/prove.go
+++ b/test/prove.go
@@ -2330,6 +2330,18 @@ func issue74473(s []uint) {
 	}
 }
 
+func setCapMaxBasedOnElementSize(x []uint64) int {
+	c := uintptr(cap(x))
+	max := ^uintptr(0) >> 3
+	if c > max { // ERROR "Disproved Less"
+		return 42
+	}
+	if c <= max { // ERROR "Proved Leq"
+		return 1337
+	}
+	return 0
+}
+
 //go:noinline
 func useInt(a int) {
 }