boundscheck.go

package main

import (
	"fmt"
	"math/rand"
)

// This will show various cases where bounds checks can be eliminated by keeping track of
// minimum and maximum potential values of slices and variables as SSA.
func main() {
	var a []byte

	// === CASE A -  All constant sizes ====
	a = make([]byte, 256)

	for i := 0; i < 50; i++ {
		_ = a[i]
	}

	// === CASE B - Assert length by slicing. ====
	a = somefunc()
	a = a[0:100]

	// If we are here, length is at least 100
	for i := 0; i < 50; i++ {
		_ = a[i]
	}

	// === CASE C - Assert length by slicing an array ====
	var b [200]byte
	a = b[:]

	for i := 0; i < 50; i++ {
		_ = a[i]
	}

	// === CASE D - Derive maximum from type ====
	a = make([]byte, 256)

	// byte can never be > 255
	for i := 0; i < 50000; i++ {
		_ = a[byte(i)]
	}

	// === CASE E - Derive maximum from type, and size from array ====
	var c [256]int

	// byte can never be > 255
	for i := 0; i < 50000; i++ {
		_ = c[byte(i)]
	}

	// === CASE F - Derive maximum size from AND ====

	// int & 0xff can never be "< 0" or "> 0xff".
	for i := -10000; i < 10000; i++ {
		_ = c[i&0xff]
	}

	// === CASE G - Check by if ====
	a = somefunc()

	func() {
		if len(a) < 100 {
			return
		}

		for i := 0; i < 50; i++ {
			_ = a[i]
		}
	}()

	// === CASE H - Check by if ====
	a = make([]byte, 256)

	for i := -500; i < 500; i++ {
		if i >= 0 && i < 256 {
			_ = a[i]
		}
	}

	// === CASE I - Range Checked earlier ====
	a = make([]byte, 256)
	for n := 0; n < 1000; n++ {
		if n >= len(a) {
			break
		}
		_ = a[n]
	}

	// === CASE J - Checked early by explicit size ====
	a = somefunc()
	_ = a[23]

	// 'a' is at least 23 entries, so no need to re-check.
	for i := 0; i < 10; i++ {
		_ = a[i]
	}

	fmt.Println("all ok")
}

// Assume the compiler cannor determine the size of the
// returned slice. It is at least 100 bytes to display re-slicing.
func somefunc() []byte {
	return make([]byte, 100+rand.Intn(1000))
}

Case A: Not currently working because len(a) doesn't transcend make. It's a known bug.
Case B: Missed optimization. Maximum not known. I can do this easily.
Case C: Same as B
Case D: Works
Case E: Works
Case F: Works
Case G: Same as B
Case H: Same as A.
Case I: Difficult. Bounds are detected in two different passes.
Case J: Same as I.