From bd7b8a52c847afcfc15b21741ec8972275a79c34 Mon Sep 17 00:00:00 2001 From: Jonah Uellenberg Date: Fri, 6 Feb 2026 02:48:07 +0000 Subject: [PATCH] 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 LUCI-TryBot-Result: Go LUCI Reviewed-by: Michael Knyszek Auto-Submit: Keith Randall Reviewed-by: Keith Randall --- src/cmd/compile/internal/ssa/prove.go | 65 ++++++++++++++++++-------- src/cmd/compile/internal/walk/range.go | 2 + src/runtime/utf8.go | 4 +- 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 } -- 2.52.0