This is an area of optimization that was figured out in the Pascal era, then forgotten during the C era. It's good to see it coming back. Work on Pascal was able to optimize out about 95% of bounds checks. Here's an overview that has a literature survey.[1]
A big win is hoisting bounds checks out of loops. I think the Go compiler already optimized out the check for loops where the loop iteration variable is bounded by the range of the array. But that's a special case. The general case has a problem. Consider
func copy(src []int, dst []int) {
for i := range(src) {
dst[i] = src[i]
}
}
This has a subscript out of range error if dst is shorter than src. It's the classic C buffer overflow. For optimization purposes, we can look at this as func copy(src []int, dst []int) {
for i := range(src) {
assert(i < len(src)) // subscript check
assert(i < len(dst)) // subscript check
dst[i] = src[i]
}
}
The FOR statement insures that i < len(src), so a prover would see this as (i < len(src) implies (i < len(src)), which reduces to True, and we can discard that assert. We still have the assert for "dst". For that, it's possible to hoist it out of the loop. We generate the check func copy(src []int, dst []int) {
assert(len(src) <= len(dst)) // generated
for i := range(src) {
assert(i < len(src)) // optimized out
assert(i < len(dst)) // subscript check
dst[i] = src[i]
}
}
which gives us len(src) <= len(dst) and i < len(src) implies (i < len(dst))
which simplifies to True. So assert(i < len(dst) can be optimized out.
We have one run-time check remaining, and it's outside the loop, done once. This is hoisting a bounds check out of a loop, and it's a huge win for inner loops. Good test for a compiler: write a matrix multiply and make sure it can do this.