runtime: add explicit lower bounds check to decoderune

decoderune is only called by generated code, so we can guarantee that
it's non-negative. This allows eliminating the automatic bounds check in
it.

To make this work, we need to expand the existing optimization to uints.
This generally enables BCE for cases like this:
```go
func test(list []int, idx uint64) int {
        if idx >= uint64(len(list)) {
                return 0
        }

        list1 := list[idx:]
        return list1[0]
}
```

Change-Id: I86a51b26ca0e63522dec99f7d6efe6bdcd2d6487
GitHub-Last-Rev: 82d44e0a080b53ee02c31ee1f92a8a0acd8d2621
GitHub-Pull-Request: golang/go#76610
Reviewed-on: https://go-review.googlesource.com/c/go/+/725101
Reviewed-by: Keith Randall <khr@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
Auto-Submit: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

3 files changed, 50 insertions, 21 deletions

diff --git a/src/cmd/compile/internal/ssa/prove.go b/src/cmd/compile/internal/ssa/prove.go
index 1083874100..0bc97db73c 100644
--- a/src/cmd/compile/internal/ssa/prove.go
+++ b/src/cmd/compile/internal/ssa/prove.go
@@ -2180,29 +2180,56 @@ func (ft *factsTable) detectSubRelations(v *Value) {
 
 	// Check if we might wrap around. If so, give up.
 	width := uint(v.Type.Size()) * 8
-	if _, ok := safeSub(xLim.min, yLim.max, width); !ok {
-		return // x-y might underflow
-	}
-	if _, ok := safeSub(xLim.max, yLim.min, width); !ok {
-		return // x-y might overflow
+
+	// v >= 1 in the signed domain?
+	var vSignedMinOne bool
+
+	// Signed optimizations
+	if _, ok := safeSub(xLim.min, yLim.max, width); ok {
+		// Large abs negative y can also overflow
+		if _, ok := safeSub(xLim.max, yLim.min, width); ok {
+			// x-y won't overflow
+
+			// Subtracting a positive non-zero number only makes
+			// things smaller. If it's positive or zero, it might
+			// also do nothing (x-0 == v).
+			if yLim.min > 0 {
+				ft.update(v.Block, v, x, signed, lt)
+			} else if yLim.min == 0 {
+				ft.update(v.Block, v, x, signed, lt|eq)
+			}
+
+			// Subtracting a number from a bigger one
+			// can't go below 1. If the numbers might be
+			// equal, then it can't go below 0.
+			//
+			// This requires the overflow checks because
+			// large negative y can cause an overflow.
+			if ft.orderS.Ordered(y, x) {
+				ft.signedMin(v, 1)
+				vSignedMinOne = true
+			} else if ft.orderS.OrderedOrEqual(y, x) {
+				ft.setNonNegative(v)
+			}
+		}
 	}
 
-	// Subtracting a positive non-zero number only makes
-	// things smaller. If it's positive or zero, it might
-	// also do nothing (x-0 == v).
-	if yLim.min > 0 {
-		ft.update(v.Block, v, x, signed, lt)
-	} else if yLim.min == 0 {
-		ft.update(v.Block, v, x, signed, lt|eq)
+	// Unsigned optimizations
+	if _, ok := safeSubU(xLim.umin, yLim.umax, width); ok {
+		if yLim.umin > 0 {
+			ft.update(v.Block, v, x, unsigned, lt)
+		} else {
+			ft.update(v.Block, v, x, unsigned, lt|eq)
+		}
 	}
 
-	// Subtracting a number from a bigger one
-	// can't go below 1. If the numbers might be
-	// equal, then it can't go below 0.
-	if ft.orderS.Ordered(y, x) {
-		ft.signedMin(v, 1)
-	} else if ft.orderS.OrderedOrEqual(y, x) {
-		ft.setNonNegative(v)
+	// Proving v >= 1 in the signed domain automatically
+	// proves it in the unsigned domain, so we can skip it.
+	//
+	// We don't need overflow checks here, since if y < x,
+	// then x-y can never overflow for uint.
+	if !vSignedMinOne && ft.orderU.Ordered(y, x) {
+		ft.unsignedMin(v, 1)
 	}
 }
 
diff --git a/src/cmd/compile/internal/walk/range.go b/src/cmd/compile/internal/walk/range.go
index e6a9a4bcfb..4f239694ce 100644
--- a/src/cmd/compile/internal/walk/range.go
+++ b/src/cmd/compile/internal/walk/range.go
@@ -348,6 +348,8 @@ func walkRange(nrange *ir.RangeStmt) ir.Node {
 		// } else {
 		// hv2, hv1 = decoderune(ha, hv1)
 		fn := typecheck.LookupRuntime("decoderune")
+		// decoderune expects a uint, but hv1 is an int.
+		// This is safe because hv1 is always >= 0.
 		call := mkcall1(fn, fn.Type().ResultsTuple(), &nif.Else, ha, hv1)
 		a := ir.NewAssignListStmt(base.Pos, ir.OAS2, []ir.Node{hv2, hv1}, []ir.Node{call})
 		nif.Else.Append(a)
diff --git a/src/runtime/utf8.go b/src/runtime/utf8.go
index 52b757662d..e94b89ef3e 100644
--- a/src/runtime/utf8.go
+++ b/src/runtime/utf8.go
@@ -57,10 +57,10 @@ func countrunes(s string) int {
 // If the string appears to be incomplete or decoding problems
 // are encountered (runeerror, k + 1) is returned to ensure
 // progress when decoderune is used to iterate over a string.
-func decoderune(s string, k int) (r rune, pos int) {
+func decoderune(s string, k uint) (r rune, pos uint) {
 	pos = k
 
-	if k >= len(s) {
+	if k >= uint(len(s)) {
 		return runeError, k + 1
 	}