Bounds Check Elimination (BCE) in Golang 1.7

Datetime:2016-08-23 05:13:54          Topic: Golang           Share



The recent released Go 1.7 uses a new compiler back end, which based on static single-assignment form (SSA) (now only availabe for amd64). SSA makes go compiler generate more efficient code with optimizations like bounds check elimination (BCE) and common subexpression elimination .

This article will show some examples how BCE works in Go 1.7.

In Go 1.7, one can run go build -gcflags="-d=ssa/check_bce/debug=1" program.go to show which code lines still need checking bounds.

Exampe 1

// example1.go
package main

func f1(s []int) {
	_ = s[0] // line 5: bounds check 
	_ = s[1] // line 6: bounds check 
	_ = s[2] // line 7: bounds check 
}

func f2(s []int) {
	_ = s[2] // line 11: bounds check 
	_ = s[1] // line 12: bounds check eliminatd!
	_ = s[0] // line 13: bounds check eliminatd!
}

func f3(s []int, index int) {
	_ = s[index] // line 17: bounds check 
	_ = s[index] // line 18: bounds check eliminatd!
}

func f4(a [5]int) {
	_ = a[4] // line 22: bounds check eliminatd!
}

func main() {}
go build -gcflags="-d=ssa/check_bce/debug=1" example1.go
# command-line-arguments
./11.go:5: Found IsInBounds
./11.go:6: Found IsInBounds
./11.go:7: Found IsInBounds
./11.go:11: Found IsInBounds
./11.go:17: Found IsInBounds

We can see that there is no needs to do bounds check for line 12 and line 13 in function f2, for the bounds check at line 11 assures that the indexes in line 12 and line 13 will not be out of range.

But in function f1, bounds check must be performed for all three lines. The bounds check at line 5 can't assure line 6 and line 7 are safe, and the bounds check at line 6 can't assure line 7 is safe.

For function f3, Go 1.7 compiler knows the second s[index] is absolutely safe if the first s[index] is safe.

Go 1.7 compiler also correctly think the only line (line 22) in function f4 is safe.

Exampe 2

// example2.go
package main

func f5(s []int) {
	for i := range s {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f6(s []int) {
	for i := 0; i < len(s); i ++ {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f7(s []int) {
	for i := len(s) - 1; i >= 0; i -- {
		_ = s[i] // line 22: bounds check 
		_ = s[i:len(s)]
	}
}

func f8(s []int, index int) {
	if index >= 0 && index < len(s) {
		_ = s[index]
		_ = s[index:len(s)]
	}
}

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

func main() {}
go build -gcflags="-d=ssa/check_bce/debug=1" example2.go
# command-line-arguments
./11.go:22: Found IsInBounds

We can see that there is only one line need bounds check in example2.go.

Go 1.7 compiler is so clever to make the conclusion that all lines in function f3 and f4 are safe.

Aha, maybe it is still not clever enough as human being, it looks line 22 is also safe.

Exampe 3

// example3.go
package main

import "math/rand"

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 eliminatd!
}

func fb(s []int, index int) {
	_ = s[:index] // line 14: bounds check 
	_ = s[index:] // line 15: bounds check // not clever enough or a bug?
}

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

func main() {}
go build -gcflags="-d=ssa/check_bce/debug=1" example3.go
# command-line-arguments
./11.go:9: Found IsSliceInBounds
./11.go:14: Found IsSliceInBounds
./11.go:15: Found IsSliceInBounds
./11.go:22: Found IsSliceInBounds
./11.go:23: Found IsSliceInBounds

Oh, so many places still need to do bounds check!

But wait, why does the Go 1.7 compiler think line 10 is safe but line 15 and line 23 are not? Is the compiler still not clever enough or is it a bug?

In fact, the compiler is right here! Why? The reason is the length of a sub slice may be larger than original slice. For example:

package main

func main() {
	s0 := make([]int, 5, 10) // len(s0) == 5, cap(s0) == 10

	index := 8

	// In golang, for the subslice syntax s[a:b],
	// the valid rage for a is [0, len(s)],
	// the valid rage for b is [a, cap(s)].
	
	// So, this line is no problem.
	_ = s0[:index]
	// But, above line is safe can't assure the following line is also safe.
	// In fact, it will panic.
	_ = s0[index:] // panic: runtime error: slice bounds out of range
}

So the statement if s[:index] is safe then s[index:] is also safe is only true when len(s) == cap(s) . This is why the code lines in function fb and fc of example 3 still need to do bounds check.

Go 1.7 compiler successfully detects len(s) == cap(s) in function fa. Great work! Golang team!

However, it looks the statement if s[index:] is safe then s[:index] is also safe is always true.

Exampe 4

// example4.go
package main

import "math/rand"

func fa2() {
	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 eliminatd!
}

func fb2(s []int, index int) {
	_ = s[index:] // line 14: bounds check
	_ = s[:index] // line 15: bounds check // not clever enough?
}

func fc2() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	s = s[:4]
	index := rand.Intn(7)
	_ = s[index:] // line 22: bounds check 
	_ = s[:index] // line 23: bounds check eliminatd!
}

func main() {}
go build -gcflags="-d=ssa/check_bce/debug=1" example4.go
# command-line-arguments
./11.go:9: Found IsSliceInBounds
./11.go:14: Found IsSliceInBounds
./11.go:15: Found IsSliceInBounds
./11.go:22: Found IsSliceInBounds

In this example, Go 1.7 compiler successfully concludes line 23 is also safe if line 22 is safe in function fc2, but fails to conclude line 15 is also safe if line 14 is safe in function fb2.

Anyway, the bounds check elimination (BCE) feature in the offical Go SDK 1.7 is a big advance!





About List