[go] cmd/compile: implement reverse bounds check elimination
3 views
Skip to first unread message
Nhan Nguyen (Gerrit)
2:25 AM (12 hours ago) 2:25 AM
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Nhan Nguyen has uploaded the change for review![]( "Open in Gerrit")
Commit message
cmd/compile: implement reverse bounds check elimination
When an index expression of the form base+k (where k > 0) is proven
to be within bounds, we can also deduce that base is within bounds.
This allows eliminating redundant bounds checks when array accesses
happen in "reverse" order.
For example:
if i >= 0 && i+1 < len(a) {
_ = a[i+1] // bounds check needed
_ = a[i] // bounds check can now be eliminated
}
This optimization benefits common patterns like digit conversion
in strconv.Itoa where digits are written in pairs from high
to low indices.
Fixes #75955
Change-Id: I91a9204430e256cfdd9a5e53d6b16567c6d42f82
Change diff
diff --git a/src/cmd/compile/internal/ssa/prove.go b/src/cmd/compile/internal/ssa/prove.go
index de16dfb..d40b085 100644
--- a/src/cmd/compile/internal/ssa/prove.go
+++ b/src/cmd/compile/internal/ssa/prove.go
@@ -741,6 +741,14 @@
ft.setNonNegative(v.Args[0])
ft.update(v.Block, v.Args[0], v.Args[1], signed, r)
ft.update(v.Block, v.Args[0], v.Args[1], unsigned, r)
+ // If the index is of the form base+k where k > 0,
+ // then base+k < bound implies base < bound.
+ // This allows eliminating bounds checks on base
+ // after we've checked base+k (reverse BCE).
+ if base, delta := isConstDelta(v.Args[0]); base != nil && delta > 0 {
+ ft.update(v.Block, base, v.Args[1], signed, r)
+ ft.update(v.Block, base, v.Args[1], unsigned, r)
+ }
} else {
// On the negative branch, we learn (0 > a0 ||
// a0 >= a1). In the unsigned domain, this is
Change information
Files:
- M src/cmd/compile/internal/ssa/prove.go
Change size: XS
Delta: 1 file changed, 8 insertions(+), 0 deletions(-)
Related details
Attention set is empty
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Keith Randall (Gerrit)
1:09 PM (1 hour ago) 1:09 PM
to Nhan Nguyen, goph...@pubsubhelper.golang.org, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
Attention needed from Martin Möhrmann and Nhan Nguyen
Keith Randall added 1 comment![]( "Open in Gerrit")
Patchset-level comments
File-level comment, Patchset 1 (Latest):
Keith Randall . resolved
This is not correct, for this program:
```
package main
//go:noinline
func f(a string, i int) {
_ = a[i+1]
_ = a[i]
}
func main() {
f("foo", -1)
}
```We still need the idx >= 0 check on the second line. I think this CL removes it because of the unsigned rule. (Because -1 is not less than 3 in the unsigned domain.)
Related details
Attention is currently required from:
- Martin Möhrmann
- Nhan Nguyen
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Nhan Nguyen (Gerrit)
1:46 PM (1 hour ago) 1:46 PM
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Martin Möhrmann and Nhan Nguyen
Nhan Nguyen uploaded new patchset![]( "Open in Gerrit")
Nhan Nguyen uploaded patch set #2 to this change.
Related details
Attention is currently required from:
- Martin Möhrmann
- Nhan Nguyen
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Reply all
Reply to author
Forward
0 new messages