cmd/compile: tighten bounds for induction variables in strided loops

for i := 0; i < 9; i += 3

Currently we compute bounds of [0,8]. Really we know that it is [0,6].

CL 415874 computed the better bound as part of overflow detection.
This CL just incorporates that better info to the prove pass.

R=go1.20

Change-Id: Ife82cc415321f6652c2b5d132a40ec23e3385766
Reviewed-on: https://go-review.googlesource.com/c/go/+/415937
Reviewed-by: Heschi Kreinick <heschi@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
Run-TryBot: Keith Randall <khr@golang.org>

1 files changed, 35 insertions, 17 deletions

diff --git a/test/loopbce.go b/test/loopbce.go
index 4ae9a6a630..db830daf5c 100644
--- a/test/loopbce.go
+++ b/test/loopbce.go
@@ -49,7 +49,7 @@ func f2(a []int) int {
 
 func f4(a [10]int) int {
 	x := 0
-	for i := 0; i < len(a); i += 2 { // ERROR "Induction variable: limits \[0,10\), increment 2$"
+	for i := 0; i < len(a); i += 2 { // ERROR "Induction variable: limits \[0,8\], increment 2$"
 		x += a[i] // ERROR "(\([0-9]+\) )?Proved IsInBounds$"
 	}
 	return x
@@ -57,7 +57,7 @@ func f4(a [10]int) int {
 
 func f5(a [10]int) int {
 	x := 0
-	for i := -10; i < len(a); i += 2 { // ERROR "Induction variable: limits \[-10,10\), increment 2$"
+	for i := -10; i < len(a); i += 2 { // ERROR "Induction variable: limits \[-10,8\], increment 2$"
 		x += a[i]
 	}
 	return x
@@ -121,7 +121,7 @@ func g0f(a string) int {
 func g1() int {
 	a := "evenlength"
 	x := 0
-	for i := 0; i < len(a); i += 2 { // ERROR "Induction variable: limits \[0,10\), increment 2$"
+	for i := 0; i < len(a); i += 2 { // ERROR "Induction variable: limits \[0,8\], increment 2$"
 		x += int(a[i]) // ERROR "(\([0-9]+\) )?Proved IsInBounds$"
 	}
 	return x
@@ -130,7 +130,7 @@ func g1() int {
 func g2() int {
 	a := "evenlength"
 	x := 0
-	for i := 0; i < len(a); i += 2 { // ERROR "Induction variable: limits \[0,10\), increment 2$"
+	for i := 0; i < len(a); i += 2 { // ERROR "Induction variable: limits \[0,8\], increment 2$"
 		j := i
 		if a[i] == 'e' { // ERROR "(\([0-9]+\) )?Proved IsInBounds$"
 			j = j + 1
@@ -142,9 +142,11 @@ func g2() int {
 
 func g3a() {
 	a := "this string has length 25"
-	for i := 0; i < len(a); i += 5 { // ERROR "Induction variable: limits \[0,25\), increment 5$"
+	for i := 0; i < len(a); i += 5 { // ERROR "Induction variable: limits \[0,20\], increment 5$"
 		useString(a[i:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$"
-		useString(a[:i+3])
+		useString(a[:i+3]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$"
+		useString(a[:i+5]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$"
+		useString(a[:i+6])
 	}
 }
 
@@ -293,22 +295,22 @@ func d3(a [100]int) [100]int {
 }
 
 func d4() {
-	for i := int64(math.MaxInt64 - 9); i < math.MaxInt64-2; i += 4 { // ERROR "Induction variable: limits \[9223372036854775798,9223372036854775805\), increment 4$"
+	for i := int64(math.MaxInt64 - 9); i < math.MaxInt64-2; i += 4 { // ERROR "Induction variable: limits \[9223372036854775798,9223372036854775802\], increment 4$"
 		useString("foo")
 	}
-	for i := int64(math.MaxInt64 - 8); i < math.MaxInt64-2; i += 4 { // ERROR "Induction variable: limits \[9223372036854775799,9223372036854775805\), increment 4$"
+	for i := int64(math.MaxInt64 - 8); i < math.MaxInt64-2; i += 4 { // ERROR "Induction variable: limits \[9223372036854775799,9223372036854775803\], increment 4$"
 		useString("foo")
 	}
 	for i := int64(math.MaxInt64 - 7); i < math.MaxInt64-2; i += 4 {
 		useString("foo")
 	}
-	for i := int64(math.MaxInt64 - 6); i < math.MaxInt64-2; i += 4 { // ERROR "Induction variable: limits \[9223372036854775801,9223372036854775805\), increment 4$"
+	for i := int64(math.MaxInt64 - 6); i < math.MaxInt64-2; i += 4 { // ERROR "Induction variable: limits \[9223372036854775801,9223372036854775801\], increment 4$"
 		useString("foo")
 	}
-	for i := int64(math.MaxInt64 - 9); i <= math.MaxInt64-2; i += 4 { // ERROR "Induction variable: limits \[9223372036854775798,9223372036854775805\], increment 4$"
+	for i := int64(math.MaxInt64 - 9); i <= math.MaxInt64-2; i += 4 { // ERROR "Induction variable: limits \[9223372036854775798,9223372036854775802\], increment 4$"
 		useString("foo")
 	}
-	for i := int64(math.MaxInt64 - 8); i <= math.MaxInt64-2; i += 4 { // ERROR "Induction variable: limits \[9223372036854775799,9223372036854775805\], increment 4$"
+	for i := int64(math.MaxInt64 - 8); i <= math.MaxInt64-2; i += 4 { // ERROR "Induction variable: limits \[9223372036854775799,9223372036854775803\], increment 4$"
 		useString("foo")
 	}
 	for i := int64(math.MaxInt64 - 7); i <= math.MaxInt64-2; i += 4 {
@@ -320,22 +322,22 @@ func d4() {
 }
 
 func d5() {
-	for i := int64(math.MinInt64 + 9); i > math.MinInt64+2; i -= 4 { // ERROR "Induction variable: limits \(-9223372036854775806,-9223372036854775799\], increment 4"
+	for i := int64(math.MinInt64 + 9); i > math.MinInt64+2; i -= 4 { // ERROR "Induction variable: limits \[-9223372036854775803,-9223372036854775799\], increment 4"
 		useString("foo")
 	}
-	for i := int64(math.MinInt64 + 8); i > math.MinInt64+2; i -= 4 { // ERROR "Induction variable: limits \(-9223372036854775806,-9223372036854775800\], increment 4"
+	for i := int64(math.MinInt64 + 8); i > math.MinInt64+2; i -= 4 { // ERROR "Induction variable: limits \[-9223372036854775804,-9223372036854775800\], increment 4"
 		useString("foo")
 	}
 	for i := int64(math.MinInt64 + 7); i > math.MinInt64+2; i -= 4 {
 		useString("foo")
 	}
-	for i := int64(math.MinInt64 + 6); i > math.MinInt64+2; i -= 4 { // ERROR "Induction variable: limits \(-9223372036854775806,-9223372036854775802\], increment 4"
+	for i := int64(math.MinInt64 + 6); i > math.MinInt64+2; i -= 4 { // ERROR "Induction variable: limits \[-9223372036854775802,-9223372036854775802\], increment 4"
 		useString("foo")
 	}
-	for i := int64(math.MinInt64 + 9); i >= math.MinInt64+2; i -= 4 { // ERROR "Induction variable: limits \[-9223372036854775806,-9223372036854775799\], increment 4"
+	for i := int64(math.MinInt64 + 9); i >= math.MinInt64+2; i -= 4 { // ERROR "Induction variable: limits \[-9223372036854775803,-9223372036854775799\], increment 4"
 		useString("foo")
 	}
-	for i := int64(math.MinInt64 + 8); i >= math.MinInt64+2; i -= 4 { // ERROR "Induction variable: limits \[-9223372036854775806,-9223372036854775800\], increment 4"
+	for i := int64(math.MinInt64 + 8); i >= math.MinInt64+2; i -= 4 { // ERROR "Induction variable: limits \[-9223372036854775804,-9223372036854775800\], increment 4"
 		useString("foo")
 	}
 	for i := int64(math.MinInt64 + 7); i >= math.MinInt64+2; i -= 4 {
@@ -356,7 +358,7 @@ func bce1() {
 		panic("invalid test: modulos should differ")
 	}
 
-	for i := b; i < a; i += z { // ERROR "Induction variable: limits \[-1547,9223372036854774057\), increment 1337"
+	for i := b; i < a; i += z { // ERROR "Induction variable: limits \[-1547,9223372036854772720\], increment 1337"
 		useString("foobar")
 	}
 }
@@ -400,6 +402,22 @@ func issue26116a(a []int) {
 	}
 }
 
+func stride1(x *[7]int) int {
+	s := 0
+	for i := 0; i <= 8; i += 3 { // ERROR "Induction variable: limits \[0,6\], increment 3"
+		s += x[i] // ERROR "Proved IsInBounds"
+	}
+	return s
+}
+
+func stride2(x *[7]int) int {
+	s := 0
+	for i := 0; i < 9; i += 3 { // ERROR "Induction variable: limits \[0,6\], increment 3"
+		s += x[i] // ERROR "Proved IsInBounds"
+	}
+	return s
+}
+
 //go:noinline
 func useString(a string) {
 }