边界检查消除

// example1.go
package main

func f1(s []int) {
    _ = s[0] // 第5行： 需要边界检查
    _ = s[1] // 第6行： 需要边界检查
    _ = s[2] // 第7行： 需要边界检查
}
func f2(s []int) {
    _ = s[2] // 第11行： 需要边界检查
    _ = s[1] // 第12行： 边界检查消除了！
    _ = s[0] // 第13行： 边界检查消除了！
}
func f3(s []int, index int) {
    _ = s[index] // 第17行： 需要边界检查
    _ = s[index] // 第18行： 边界检查消除了！
}
func f4(a [5]int) {
    _ = a[4] // 第22行： 边界检查消除了！
}
func main() {}

$ go build -gcflags="-d=ssa/check_bce/debug=1" example1.go
./example1.go:5: Found IsInBounds
./example1.go:6: Found IsInBounds
./example1.go:7: Found IsInBounds
./example1.go:11: Found IsInBounds
./example1.go:17: Found IsInBounds

我们可以看到函数f2中的第12行和第13行不再需要边界检查了，因为第11行的检查确保了第12行和第13行中使用的下标肯定不会越界。

但是，函数f1中的三行仍然都需要边界检查，因为第5行中的边界检查不能保证第6行和第7行中的下标没有越界，第6行中的边界检查也不能保证第第7行中的下标没有越界。

在函数f3中，编译器知道如果第一个s[index]是安全的，则第二个s[index]是无需边界检查的。

编译器也正确地认为函数f4中的唯一一行（第22行）是无需边界检查的。

// 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]
        _ = 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

酷！官方标准编译器消除了上例程序中的所有边界检查。

注意：在Go官方工具链1.11之前，官方标准编译器没有足够聪明到认为第22行是不需要边界检查的。

// example3.go
package main

import “math/rand”
func fa() {
    s := []int{0, 1, 2, 3, 4, 5, 6}
    index := rand.Intn(7)
    _ = s[:index] // 第9行： 需要边界检查
    _ = s[index:] // 第10行： 边界检查消除了！
}
func fb(s []int, index int) {
    _ = s[:index] // 第14行： 需要边界检查
    _ = s[index:] // 第15行： 需要边界检查（不够智能？）
}
func fc() {
    s := []int{0, 1, 2, 3, 4, 5, 6}
    s = s[:4]
    index := rand.Intn(7)
    _ = s[:index] // 第22行： 需要边界检查
    _ = s[index:] // 第23行： 需要边界检查（不够智能？）
}
func main() {}

$ go build -gcflags="-d=ssa/check_bce/debug=1" example3.go
./example3.go:9: Found IsSliceInBounds
./example3.go:14: Found IsSliceInBounds
./example3.go:15: Found IsSliceInBounds
./example3.go:22: Found IsSliceInBounds
./example3.go:23: Found IsSliceInBounds

噢，仍然有这么多的边界检查！

但是等等，为什么官方标准编译器认为第10行不需要边界检查，却认为第15和第23行仍旧需要边界检查呢？ 是标准编译器不够智能吗？

事实上，这里标准编译器做得对！为什么呢？ 原因是一个子切片表达式中的起始下标可能会大于基础切片的长度。 让我们先看一个简单的使用了子切片的例子：

package main

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

    index := 8

    // 在Go中，对于一个子切片表达式s[a:b]，a和b须满足
    // 0 <= a <= b <= cap(s);否则，将产生一个恐慌。

    _ = s0[:index]
    // 上一行是安全的不能保证下一行是无需边界检查的。
    // 事实上，下一行将产生一个恐慌，因为起始下标
    // index大于终止下标（即切片s0的长度）。
    _ = s0[index:] // panic
}

所以如果s[:index]是安全的则s[index:]是无需边界检查的这条论述只有在len(s)和cap(s)相等的情况下才正确。这就是函数fb和fc中的代码仍旧需要边界检查的原因。

标准编译器成功地检测到在函数fa中len(s)和cap(s)是相等的。干得漂亮！Go语言开发团队！

// example4.go
package main

import “math/rand”
func fb2(s []int, index int) {
    _ = s[index:] // 第7行： 需要边界检查
    _ = s[:index] // 第8行： 边界检查消除了！
}
func fc2() {
    s := []int{0, 1, 2, 3, 4, 5, 6}
    s = s[:4]
    index := rand.Intn(7)
    _ = s[index:] // 第15行： 需要边界检查
    _ = s[:index] // 第16行： 边界检查消除了！
}
func main() {}

$ go build -gcflags="-d=ssa/check_bce/debug=1" example4.go
./example4.go:7:7: Found IsSliceInBounds
./example4.go:15:7: Found IsSliceInBounds

在此例子中，标准编译器成功推断出：

• 在函数fb2中，如果第7行是安全的，则第8行是无需边界检查的；
• 在函数fc2中，如果第15行是安全的，则第16行是无需边界检查的。

注意：Go官方工具链1.9之前中的标准编译器没有出推断出第8行不需要边界检查。

// example5.go
package main

func fd(is []int, bs []byte) {
    if len(is) >= 256 {
        for _, n := range bs {
            _ = is[n] // 第7行： 需要边界检查
        }
    }
}

func fd2(is []int, bs []byte) {
    if len(is) >= 256 {
        is = is[:256] // 第14行： 一个暗示
        for _, n := range bs {
            _ = is[n] // 第16行： 边界检查消除了！
        }
    }
}

func fe(isa []int, isb []int) {
    if len(isa) > 0xFFF {
        for _, n := range isb {
            _ = isa[n & 0xFFF] // 第24行： 需要边界检查
        }
    }
}

func fe2(isa []int, isb []int) {
    if len(isa) > 0xFFF {
        isa = isa[:0xFFF+1] // 第31行： 一个暗示
        for _, n := range isb {
            _ = isa[n & 0xFFF] // 第33行： 边界检查消除了！
        }
    }
}

func main() {}

$ go build -gcflags="-d=ssa/check_bce/debug=1" example5.go
./example5.go:7: Found IsInBounds
./example5.go:24: Found IsInBounds

1. Bounds Check Elimination
2. Utilizing the Go 1.7 SSA Compiler（第二部分）