cmd/compile: extend prove pass to handle constant comparisons

Find comparisons to constants and propagate that information
down the dominator tree.  Use it to resolve other constant
comparisons on the same variable.

So if we know x >= 7, then a x > 4 condition must return true.

This change allows us to use "_ = b[7]" hints to eliminate bounds checks.

Fixes #14900

Change-Id: Idbf230bd5b7da43de3ecb48706e21cf01bf812f7
Reviewed-on: https://go-review.googlesource.com/21008
Reviewed-by: Alexandru Moșoi <alexandru@mosoi.ro>

1 files changed, 173 insertions, 3 deletions

diff --git a/test/prove.go b/test/prove.go
index e5e5b544cf..fc2908eb03 100644
--- a/test/prove.go
+++ b/test/prove.go
@@ -3,12 +3,14 @@
 
 package main
 
+import "math"
+
 func f0(a []int) int {
 	a[0] = 1
 	a[0] = 1 // ERROR "Proved boolean IsInBounds$"
 	a[6] = 1
 	a[6] = 1 // ERROR "Proved boolean IsInBounds$"
-	a[5] = 1
+	a[5] = 1 // ERROR "Proved IsInBounds$"
 	a[5] = 1 // ERROR "Proved boolean IsInBounds$"
 	return 13
 }
@@ -17,15 +19,25 @@ func f1(a []int) int {
 	if len(a) <= 5 {
 		return 18
 	}
-	a[0] = 1
+	a[0] = 1 // ERROR "Proved non-negative bounds IsInBounds$"
 	a[0] = 1 // ERROR "Proved boolean IsInBounds$"
 	a[6] = 1
 	a[6] = 1 // ERROR "Proved boolean IsInBounds$"
-	a[5] = 1 // ERROR "Proved non-negative bounds IsInBounds$"
+	a[5] = 1 // ERROR "Proved IsInBounds$"
 	a[5] = 1 // ERROR "Proved boolean IsInBounds$"
 	return 26
 }
 
+func f1b(a []int, i int, j uint) int {
+	if i >= 0 && i < len(a) { // TODO: handle this case
+		return a[i]
+	}
+	if j < uint(len(a)) {
+		return a[j] // ERROR "Proved IsInBounds"
+	}
+	return 0
+}
+
 func f2(a []int) int {
 	for i := range a {
 		a[i] = i
@@ -245,6 +257,164 @@ func f12(a []int, b int) {
 	useSlice(a[:b])
 }
 
+func f13a(a, b, c int, x bool) int {
+	if a > 12 {
+		if x {
+			if a < 12 { // ERROR "Disproved Less64$"
+				return 1
+			}
+		}
+		if x {
+			if a <= 12 { // ERROR "Disproved Leq64$"
+				return 2
+			}
+		}
+		if x {
+			if a == 12 { // ERROR "Disproved Eq64$"
+				return 3
+			}
+		}
+		if x {
+			if a >= 12 { // ERROR "Proved Geq64$"
+				return 4
+			}
+		}
+		if x {
+			if a > 12 { // ERROR "Proved boolean Greater64$"
+				return 5
+			}
+		}
+		return 6
+	}
+	return 0
+}
+
+func f13b(a int, x bool) int {
+	if a == -9 {
+		if x {
+			if a < -9 { // ERROR "Disproved Less64$"
+				return 7
+			}
+		}
+		if x {
+			if a <= -9 { // ERROR "Proved Leq64$"
+				return 8
+			}
+		}
+		if x {
+			if a == -9 { // ERROR "Proved boolean Eq64$"
+				return 9
+			}
+		}
+		if x {
+			if a >= -9 { // ERROR "Proved Geq64$"
+				return 10
+			}
+		}
+		if x {
+			if a > -9 { // ERROR "Disproved Greater64$"
+				return 11
+			}
+		}
+		return 12
+	}
+	return 0
+}
+
+func f13c(a int, x bool) int {
+	if a < 90 {
+		if x {
+			if a < 90 { // ERROR "Proved boolean Less64$"
+				return 13
+			}
+		}
+		if x {
+			if a <= 90 { // ERROR "Proved Leq64$"
+				return 14
+			}
+		}
+		if x {
+			if a == 90 { // ERROR "Disproved Eq64$"
+				return 15
+			}
+		}
+		if x {
+			if a >= 90 { // ERROR "Disproved Geq64$"
+				return 16
+			}
+		}
+		if x {
+			if a > 90 { // ERROR "Disproved Greater64$"
+				return 17
+			}
+		}
+		return 18
+	}
+	return 0
+}
+
+func f13d(a int) int {
+	if a < 5 {
+		if a < 9 { // ERROR "Proved Less64$"
+			return 1
+		}
+	}
+	return 0
+}
+
+func f13e(a int) int {
+	if a > 9 {
+		if a > 5 { // ERROR "Proved Greater64$"
+			return 1
+		}
+	}
+	return 0
+}
+
+func f13f(a int64) int64 {
+	if a > math.MaxInt64 {
+		// Unreachable, but prove doesn't know that.
+		if a == 0 {
+			return 1
+		}
+	}
+	return 0
+}
+
+func f13g(a int) int {
+	if a < 3 {
+		return 5
+	}
+	if a > 3 {
+		return 6
+	}
+	if a == 3 { // ERROR "Proved Eq64$"
+		return 7
+	}
+	return 8
+}
+
+func f13h(a int) int {
+	if a < 3 {
+		if a > 1 {
+			if a == 2 { // ERROR "Proved Eq64$"
+				return 5
+			}
+		}
+	}
+	return 0
+}
+
+func f13i(a uint) int {
+	if a == 0 {
+		return 1
+	}
+	if a > 0 { // ERROR "Proved Greater64U$"
+		return 2
+	}
+	return 3
+}
+
 //go:noinline
 func useInt(a int) {
 }