Go1.7里面的BCE(跳跃检测排除)(译文)

astaxie · · 1514 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。


最近发布的 Go 1.7 里面使用了一个新的基于 SSA 的编译后端(目前只有 amd64 可用)。SSA 使得编译出来的代码更加高效 SSA,主要是里面有包含了 BCE公共子表达式消除

这篇文章将会通过一些例子给大家展示 Go 1.7 里面BCE是如何工作的。

在 Go 1.7 里面我们可以通过这个命令 go build -gcflags="-d=ssa/check_bce/debug=1" 来展示我们的代码哪一行需要进行越界检查。

例子1

// example1.gopackage mainfunc 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

我们可以看到这个f2函数里面的12行和13行不需要进行越界检查,因为在11行里面的越界检查可以保证12,13行的代码是不会越界的。

但是在f1里面必须每一行都逐一检查越界,因为第5行没办法保证第6、第7行是安全的,第6行没办法保证第7行是安全的。

函数f3里面,Go 1.7 编译器知道如果第一行是安全的情况下,那么第二行的s[index]是完全安全的

Go 1.7 的编辑器也正确的分析出来了f4函数里面的唯一的一行(22行)也是安全的。

例子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

我们可以看到在例子2里面只有一行需要进行越界检查

Go 1.7 编译器是如此的聪明,它精确的做出决定说:在f5和f6里面所有的代码都是安全的

但是好像还是没有我们人类聪明,看上去22行也是安全的

例子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 smart 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

啊!那么多地方需要进行越界检查

但是等等,为什么 Go 1.7 的编译器会认为第10行是安全的,但是15行和23行不安全?是因为编译器不够聪明还是这是一个bug?

实际上,编译器在这里是对的!为什么?原因是子slice可能大于原始的slice,看下面这个例子:

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
}

所以如果s[:index]是安全的话,也就当len(s) == cap(s)的时候,s[index:]才是安全的
。这就是为什么在例子3里面fb和fc里面的代码还需要进行越界检查。

Go 1.7 编译器在函数fa里面成功的检测到了 len(s) == cap(s)。太棒了!Golang Team!

然而,如果s[index:]是安全的话,那么s[:index]就一直是安全的。

例子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 smart 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

在这个例子中, Go 1.7 编译器成功的计算出来在fc2函数里面如果22行安全的情况下那么23行也是安全的,但是在fb2里面没办法计算出来如果14行安全的情况下15行也是安全的情况。

例子5

尽管当前的编译器(Go1.7.1 amd64) 还是不够智能的排除一些不需要检测的地方,但是我们可以做一些暗示来帮助编译器排除这些不必要的越界检查。

// example5.go
package main

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

func fd2(is []int, bs []byte) {
    if len(is) >= 256 {
        is = is[:256] // line 14: bounds check. A hint for the compiler.
        for _, n := range bs {
            _ = is[n] // line 16: bounds check eliminatd! 
        }
    }
}

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

func fe2(isa []int, isb []int) {
    if len(isa) > 0xFFF {
        isa = isa[:0xFFF+1] // line 31: bounds check. A hint for the compiler.
        for _, n := range isb {
            _ = isa[n & 0xFFF] // line 33: bounds check eliminatd! 
        }
    }
}

func ff(s []int) []int {
    s2 := make([]int, len(s))
    for i := range s {
        s2[i] = -s[i] // line 41: bounds check, not smart enough.
    }
    return s2
}

func ff2(s []int) []int {
    s2 := make([]int, len(s))
    s2 = s2[:len(s)] // line 48: bounds check. A hint for the compiler.
    for i := range s {
        s2[i] = -s[i] // line 50: bounds check eliminatd! 
    }
    return s2
}

func main() {}
$ go build -gcflags="-d=ssa/check_bce/debug=1" example5.go
# command-line-arguments
./11.go:7: Found IsInBounds
./11.go:14: Found IsSliceInBounds
./11.go:24: Found IsInBounds
./11.go:31: Found IsSliceInBounds
./11.go:41: Found IsInBounds
./11.go:48: Found IsSliceInBounds

总结

尽管当前1.7版本里面的 BCE 特性还不够完美,但是在大多数情况下还是表现的非常好。毫无疑问Go的编译器将会在后续版本里面做的更好,感谢 Go 团队增加了如此帮的特性

参考文献

  1. gBounds Checking Elimination

  2. Utilizing the Go 1.7 SSA Compiler

原文:http://www.tapirgames.com/blog/golang-1.7-bce


Go社区:https://gocn.io



有疑问加站长微信联系(非本文作者)

本文来自:微信公众平台

感谢作者:astaxie

查看原文:Go1.7里面的BCE(跳跃检测排除)(译文)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1514 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传