Bounds Check Elimination

alias bce="go tool compile -d=ssa/check_bce/debug=1 ${1}"
bce example.go

{
    "version": "2.0.0",
    "tasks": [
        {
            "label": "Go: Bounds Check",
            "type": "shell",
            "command": "go tool compile -d=ssa/check_bce/debug=1 ${file} && for _ in '${fileDirname}/*.o'; do unlink $_ ; done",
            "presentation": {
                "echo": true,
                "reveal": "always",
                "focus": true,
                "panel": "shared",
                "showReuseMessage":false,
                "clear": true,
            },
            "problemMatcher": [
                "$go"
            ]
        }
    ]
}

//  - valyala.go - 
package main

import (
	"unsafe"
	"fmt"
)

// example from the Aliaksand Valialkin presentation about unsafe.
// pointless, but ok. not really bce, but it is in some order.

func example(){
	a := []int{1,2,3}
	x := unsafeGet(a, 5)

	fmt.Printf("x:%+v\n", x)
}

func unsafeGet(a []int, idx int) int {
	// calculating offset from zero element for index idx with size of zero element.
	return *(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(&a[0])) + uintptr(idx)*unsafe.Sizeof(a[0])))
}

//  - examples_1.go - 
// Example from the go101 article.
package main


// Moving last bound check to be fun as first.

func f1_before(s []int) {
	_ = s[0] // line 8: bounds check
	_ = s[1] // line 9: bounds check
	_ = s[2] // line 10: bounds check
}

func f1_after(s []int) {
	_ = s[2] // line 14: bounds check
	_ = s[1] // line 15: bounds check eliminated!
	_ = s[0] // line 16: bounds check eliminated!
}



// Double checks are ignored.

func f2(s []int, index int) {
	_ = s[index] // line 24: bounds check
	_ = s[index] // line 25: bounds check eliminated!
}

// passing fixed size array, no ned for check.
func f3(a [5]int) {
	_ = a[4] // line 30: bounds check eliminated!
}

//  - examples_2.go - 
// Example from the go101 article.
package main


// Iteration over the key, so its always in the array.
func f5(s []int) {
	for i := range s {
		_ = s[i]
		_ = s[i:len(s)]      // Range is always in the bounds.
		_ = s[:i+1]          // i+1 wound't be used as it "not include bound" and i is in the slice
	}
}


// Side of slice is determined by len(s)
func f6(s []int) {
	for i := 0; i < len(s); i++ {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

// Same by reverse.
func f7(s []int) {
	for i := len(s) - 1; i >= 0; i-- {
		_ = s[i]
		_ = s[i:len(s)]
	}
}

// no need to bounds check s we doing it.
func f8(s []int, index int) {
	if index >= 0 && index < len(s) {
		_ = s[index]
		_ = s[index:len(s)]
	}
}

// predefined len of s
func f9(s []int) {
	if len(s) > 2 {
	    _, _, _ = s[0], s[1], s[2]
	}
}

//  - examples_3.go - 
// Example from the go101 article.
package main

import "math/rand"


// slice defined in visible scope, so its defined that len(s) == cap(s)
func fa() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	index := rand.Intn(7)
	_ = s[:index] // line 9: bounds check
	_ = s[index:] // line 10: bounds check eliminated!
}

func fb(s []int, i int) {
	_ = s[:i] // line 14: bounds check
	_ = s[i:] // line 15: bounds check, not smart enough?
}

func fc() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	s = s[:4]
	i := rand.Intn(7)
	_ = s[:i] // line 22: bounds check
	_ = s[i:] // line 23: bounds check, not smart enough?
}

//  - examples_4.go - 
// Example from the go101 article.
package main


func fd(is []int, bs []byte) {
	if len(is) >= 256 {
		for _, n := range bs {
			_ = is[n] // line 7: bounds check
		}
	}
}

func fd2(is []int, bs []byte) {
	if len(is) >= 256 {
		is = is[:256] // line 14: a hint
		for _, n := range bs {
			_ = is[n] // line 16: BCEed!
		}
	}
}

func fe_before(isa []int, isb []int) {
	if len(isa) > 0xFFF {
		for _, n := range isb {
			_ = isa[n & 0xFFF] // line 24: bounds check
		}
	}
}

func fe_after(isa []int, isb []int) {
	if len(isa) > 0xFFF {
		isa = isa[:0xFFF+1] // line 31: a hint
		for _, n := range isb {
			_ = isa[n & 0xFFF] // line 33: BCEed!
		}
	}
}

//  - pattern_1.go - 
package main

func p1(b []byte, v uint32) {
	b[0] = byte(v >> 24)
	b[1] = byte(v >> 16)
	b[2] = byte(v >> 8)
	b[3] = byte(v)
}

func p1_after(b []byte, v uint32) {
	_ = b[3]

	b[0] = byte(v >> 24)
	b[1] = byte(v >> 16)
	b[2] = byte(v >> 8)
	b[3] = byte(v)
}

//  - pattern_2.go - 
package main

func p2(b []byte, n int) {
	for i:=0; i < n; i++{
		b[i] = 9
	}
}

func p2_after(b []byte, n int) {
	_ = b[n-1]
	for i:=0; i < n; i++{
		b[i] = 9
	}
}

//  - pattern_3.go - 
package main

func p3(b []byte, n int) {

	_ = b[n+5]

	b[n] = byte(1 >> 40)
	b[n+1] = byte(1 >> 32)
	b[n+2] = byte(1 >> 24)
	b[n+3] = byte(1 >> 16)
	b[n+4] = byte(1 >> 8)
	b[n+5] = byte(1)

}

// using re slicing.

func p3_after(b []byte, n int) {

	b = b[n: n+5]

	b[0] = byte(1 >> 40)
	b[1] = byte(1 >> 32)
	b[2] = byte(1 >> 24)
	b[3] = byte(1 >> 16)
	b[4] = byte(1 >> 8)
	b[5] = byte(1)

}

//  - pattern_4.go - 
package main

func p4(a,b,c []byte) {
	for i := range a {
		a[i] = b[i] + c[i]
	}
}

func p4_after(a,b,c []byte) {
	_ = b[len(a)-1]
	_ = c[len(a)-1]
	for i := range a {
		a[i] = b[i] + c[i]
	}
}

//  - pattern_5.go - 
package main

func p5(b []byte, h []int32) {
	for _, t := range b {
		h[t]++
	}
}

// bytes as they limited, so this is utilize it.
func p5_after(b []byte, h []int32) {

	h = h[:256]

	for _, t := range b {
		h[t]++
	}
}