摘要
本文中介绍了 Go 编译器的整体编译流程脉络和一个编译优化谬误导致数据越界拜访的 bug，并剖析了对这个 bug 的排查和修复过程，心愿可能借此让大家对 Go 编译器有更多的理解，在遇到相似问题时有排查思路。
缘起
某日，一位友人在群里招呼我，“看到有人给 Go 提了个编译器的 bug，挺有意思，感觉还挺重大的，要不要来看看？”于是我关上了 issue 40367[1]。彼时，最新一条评论是 这条[2]：
提到将循环体中的一个常数从 1 改成 2 就无奈复现问题，这登时勾起了我的趣味，于是我筹备钻研一番。
bug 代码跟景象如下图，失常来看，代码应该在输入 “5 6” 后进行，然而实际上却有限执行了上来，只能强行终止或期待程序触碰到无权限内存地址之后解体。
首先，咱们要定位到这个问题具体的间接起因。简略来说，这个 bug 是 for-range loop 越界，本来循环应该在循环次数达到数组长度后终止，然而这个复现程序中的循环有限执行了上来。乍一看，问题像是有 bound check 被优化掉了，那么咱们来实锤一下。有一个不便的网站，能够在线察看给定程序编译产出的汇编后果，我用 这个网站[3] 别离生成了原复现程序和将第六行的 +1 改为 +2 后不复现程序的汇编，供大家比照。抛开无关细节不提，能够很容易地看到前者的汇编相较于后者确实少了一次判断，导致循环无奈终止，具体的地位是第二段代码的 105 行：
既然间接起因曾经定位到了，那接下来咱们就要想方法追进编译器来查看为什么汇编后果有问题了。对很多同学来说，追进编译器查问题的过程可能比拟生疏，听起来就令人望而生畏，那么咱们如何来排查这个问题呢？
背景常识
在追踪这个具体问题之前，咱们须要先理解一些相干常识背景。
Go 编译器的大体运行流程
想要追究 Go 编译器的问题，首先就须要理解 Go 编译器的大抵运行流程。其实 Go 的编译器的实现中规中矩，相比于 GCC/Clang 等老牌编译器甚至有些简陋，许多优化并未实现。一个 Go 程序在生成汇编前的工作大略分为这几步：
- 语法解析。因为 Go 语言语法相当简略，所以 Go 编译器应用的是一个手写的 LALR (1) 解析器，这部分跟明天的 bug 无关，细节略过不提。
- 类型查看。Go 是强类型动态类型语言，在编译期会对赋值、函数调用等过程做类型查看，判断程序是否非法。另外，这个步骤会将一些 Go 自带的泛型函数变换成具体类型的函数调用，比方说 make 函数，在类型查看阶段会依据类型查看的后果变换成具体的 makeslice/makemap 等。这部分也跟明天的 bug 无关。
- 中间代码（IR）生成。为不便做跨平台代码生成，也为不便做编译优化，古代编译器通常会将语法树变成一个中间代码示意模式，这个示意模式的形象水平通常是介于语法树和平台汇编之间。Go 抉择的是一种动态单赋值（SSA）模式的中间代码。这部分较为重要，接下来一个大节会开展详述一下。
- 编译优化。在生成了 SSA IR 之后，编译器会基于这个 IR 跑很多趟（pass）代码剖析和改写，每个 pass 会实现一个优化策略。另外值得一提的是，Go 中很多强度削减类的策略是应用一种 DSL 形容，而后代码生成出理论的 pass 代码来的，不过这块跟明天内容没什么关系，感兴趣的同学能够下来看看。在文章的后续内容中，咱们就会定位到导致本文中这个 bug 的具体的 pass，并看到那个 pass 中有问题的逻辑。
这几步之后，编译器就曾经筹备好生成最终的平台汇编代码了。
动态单赋值模式
动态单赋值的含意是，在这种类型的 IR 中，每一个变量只会被赋值一次。这种模式的益处咱们不再赘述，仅以一段简略的 Go 代码作为实例帮忙大家了解 SSA IR 的含意。
这里是一个简略的例子，右侧是 Go 代码所对应的 SSA IR。能够看到，整个代码被切分成了多块，每个代码块（block）的代码以 bXX 作为结尾，另外在缩进所对应的结尾可能看到这个 block 会跳转到哪个 block。在 block 外部，能够看到包含常量在内的每个值都会有一个独自的名字，比方变量 a 在 Go 代码的 4、5 行的两次赋值，在 SSA IR 中对应了 v7 和 v11 两个值。
然而，如果是代码中蕴含了 if 等语句，在编译时不能确定须要应用哪个值，在 SSA IR 中如何示意呢？例子中正好有这样的代码，能够看到 Go 代码中第六行的 if。实际上，SSA IR 中有一个专门的 phi 操作符，就是为了这种状况设计，phi 操作符的含意是，返回值可能是参数的多个值中的任意一个，然而具体到底是哪个值，须要取决于这个 block 此次运行是从哪个 block 跳转而来。在上图中，能够看到 b2 就有一个 phi 运算符，v22 可能等于 v11 或 v21，具体等于哪个值须要看 b2 的上一个块到底是 b1 还是 b3，实际上就对应了 if 条件的成立或不成立。当然，这个例子中 if 显然成立，只不过咱们这里看到的 SSA IR 是未通过优化的 IR，在理论的编译过程中，这里会被优化掉。
Go 编译器提供了十分不便的性能，能够查看各个优化 pass 前后的 SSA IR，只须要在编译时，减少一个 GOSSAFUNC=xxx 环境变量即可，xxx 即为想要剖析的函数的名字，因为 Go 编译器外部的优化都是函数级别的。比方上图的例子，只须要运行 GOSSAFUNC=main go build ssaexample.go，编译器就会将 SSA IR 后果输入到当前目录的 ssa.html 中，用浏览器关上即可。
排查过程
追究出问题的优化策略
理解了这么多前置常识，咱们终于能够来追究这个具体的 bug 成因了。第一步，咱们要首先通过 Go 编译器 dump 进去的 SSA IR，查看到底是哪一个 pass 出了问题。用上一节中讲到的形式，咱们能够察看 issue 中的复现程序的所有 SSA IR。因为 Go 编译器的优化 pass 不少，所以在 ssa.html 中记录了大量的 SSA IR，咱们如何找到有问题的 pass 呢。对于我集体来说，因为我之前有所理解，可能大抵猜到这种问题是 prove pass 的 bug。然而即便大家没有相干背景，因为咱们曾经晓得这个 bug 的间接起因是少了一条比拟判断，所以也能够通过二分法查看哪个 pass 少了一条比拟指令来进行定位。须要留神的是，大家可能会定位到 generic deadcode pass，因为这个 pass 中少了一条 Less64 指令，如图（我这里应用的是 Go 1.15rc1，具体输入与编译器版本相干，可能有所不同），右侧是 generic deadcode pass：
能够看到相比于左侧，右侧中 b4 里的 Less64 隐没了，再察看这条 Less64 的参数，v11 就是常量 6，也即代码中数组的长度，能够确定这条指令就是那个隐没的边界判断。那么咱们是否能够确定 bug 出在 generic deadcode pass 呢？并不能。因为这个 pass 只是把后面 pass 中曾经变成死代码的局部删除掉，实际上这行 Less64 在后面曾经变成死代码了，从左侧这条指令的浅灰色能够看进去，也就是说 generic deadcode pass 其实是背锅的。不过从这里开始，往前查具体是哪个 pass 变成的死代码，就容易很多了，只须要在浏览器中点击这行指令，就能将这条指令的变迁高亮进去，往前追几个 pass 很容易看到是 prove pass 出了问题：
右侧是 prove pass，能够看到这行在 prove pass 变成了灰色。
prove pass 简介
定位了出问题的策略是 prove pass，那么接下来咱们就须要看看 prove pass 到底是干什么用的。实际上，prove pass 的性能是对全局中 SSA 值的取值范畴做一个推断，这样就能够打消掉许多不必要的分支判断，是不是听起来就跟明天的 bug 脱不了干系？实际上，这是在 Go 编译器中十分重要的一个 pass，很多优化都依赖于这个 pass 之后失去的后果。比方，因为 Go 是内存平安的语言，所以所有的 slice 取元素操作都须要做一个查看，来判断取元素用的下标是否超出了 slice 的范畴，这个操作叫做 bound check。然而实际上，很多代码中在编译期就能确定这个下标是否越界，那么咱们就能够将本来须要在运行期做 bound check 的查看给打消掉，这步优化叫做 bound check elimination，具体代码示例比方上面这段，是从 Go 规范库[4] 拿来的代码:
func (bigEndian) PutUint64(b []byte, v uint64) {_ = b[7] // early bounds check to guarantee safety of writes below
b[0] = byte(v >> 56)
b[1] = byte(v >> 48)
b[2] = byte(v >> 40)
b[3] = byte(v >> 32)
b[4] = byte(v >> 24)
b[5] = byte(v >> 16)
b[6] = byte(v >> 8)
b[7] = byte(v)
}
能够看到，这个函数中首先进行了 b[7] 的操作，这样一来，编译器在 prove pass 就能够理解到，当程序运行到第三行及之后时，slice b 的长度是必然大于等于 7 的，因而后续操作的 bound check 都能够被 eliminate 掉。然而，prove pass 不止会做 bound check elimination 这一个特定 pattern 的优化，还有许多其余 pattern 也会在 prove pass 被优化掉。那么明天的这个 bug 到底是 prove pass 中什么中央出了问题呢？prove pass 问题排查
说起代码问题的定位办法，可能大体上可能分成三个流派。第一是打日志，通过在日志中加信息来定位问题；第二是通过 gdb 等 debugger 下断点、单步运行来排查问题；第三是动静追踪，通过 perf/systemtap/ebpf 之类的伎俩来动静观测程序运行时的行为。具体到 Go 编译器这里，其实开发 Go 编译器的 Go team 大牛们也须要日常排查问题，也不外乎这几种伎俩，然而在编译优化的问题上他们更青眼第一种打日志的形式，所以他们曾经在各个 pass 中预埋了许多 debug 日志，只是这些日志平时不会开启，须要非凡的编译开关。既然 prove pass 相当简单，咱们无妨通过查日志的形式来进一步放大问题排查范畴。prove pass 的 debug 日志开关是 -d=ssa/prove/debug=1，其中 debug 前面跟的数字越大日志越具体，咱们只须要在编译时执行 go tool compile -d=ssa/prove/debug=1 bug.go 就能看到对应的日志。具体到这个 bug，用 debug=1 的级别可能看到比照。如下图，左侧为复现程序的日志，右侧为批改常量后不复现的程序的日志：
能够很分明地看到，bug 程序显著多证出了一个关系。进一步地，通过 grep 编译器代码中这段日志关键词，就能找到只有 findIndVar 和 addLocalInductiveFacts 这两个函数中会打这条日志，联合上下文和相干正文不难看出实际上问题是出在 addLocalInductiveFacts 这个函数上。addLocalInductiveFacts 具体是什么性能呢？从正文中不难看出，这里的性能是匹配到一种非凡的代码 pattern，即相似 repeat until 的逻辑，在循环开端判断某个条件是否成立。具体这个函数中的 bug 出在何处，咱们还须要进一步用更高级别的 debug=3 来看其运行细节：
我这里只截到了相干日志局部。能看到，在出问题的 induction 之前，首先证得了 v10 >= v16 不成立。联合 addLocalInductiveFacts 能够发现，实际上编译器是将 v10 和 v16 别离当作了循环变量的上下界，也就是代码中的 min 和 max 变量。然而，联合 SSA IR 不难看出，其实 v16 基本不是循环变量的上界，那么问题到底出在哪呢？
读 addLocalInductiveFacts 的 抽取 max 的相干代码[5]（如上图片段）能够看出，这里的用意其实就是从条件判断完结后循环头部的 phi 操作所在 block 登程，一路向前追溯，找到条件判断的 block（if block），而后如代码中 1104 行，判断 phi 操作到底是 if 的条件成立分支逻辑，还是 else 逻辑，依据分支来判断是否该当对条件进行取反，因为如果是 else 分支逻辑，那么意味着条件判断后果是 false，咱们须要对条件取反能力失去真正成立的逻辑条件。看到这里的代码，置信大家曾经晓得了这个 bug 的根因所在。1104-1113 行代码写的很分明，如果是条件成立分支，那么 br 为 positive，如果是 else 分支，那么 br 为 negative。然而，这里并没有判断 phi 操作跟 if block 的间接关联，如果 phi 操作跟 if block 没有间接分割，那么即便咱们追溯到了 if block，也没法晓得 br 变量到底是 positive 还是 negative，取值就是 unknown。然而在后续逻辑中，并没有判断 unknown，而是间接默认依照 positive 的流程走；恰好在这个 bug 复现程序中，phi 操作所在 block 跟 if block 的 else 分支有间接关联，走 positive 流程天然就出了问题。
上图为问题复现代码的 ssa cfg 图，可能分明地看出，b6 没有与对应的 b5 有间接关联，而是间接关联，命中了代码的谬误门路。
结尾
定位到了问题，那么如何修复呢？一个很简略的形式，就是间接在 br 求值的逻辑前面，减少一个 unknown 判断逻辑，当 br == unknown 就间接退出判断。这样一来，prove pass 显然会变得激进，然而能够保障正确性。加了这个查看之后 bug 复现程序就运行失常了，然而作为更加 general 的修复，咱们在函数的入口处减少对入口 block 的判断，确保入口 block 确实是一个循环结尾块，而不是什么别的恰好也能匹配上以后 pattern 的货色。我将这个修复提交给了上游。这个 bug 因为十分重大，而且这个修复对性能实测根本没有太大影响，所以很快合入了 master，即 commit 7f8608047644ca34bad1728d5e2dbef041a1b3f2[6]，并且将要 cherry pick 到依然承诺保护的前两个大版本 1.13 和 1.14 中。后面提到，这个 patch 会让优化器更加激进，所以后续会通过其余批改让优化器复原到之前的程度，我也曾经提交了对应的 patch，不过因为 1.15 开发周期曾经解冻，所以预计会在 1.16 cycle 合入 master。
置信大家通过本文曾经对 Go 编译器的运行过程、定位 bug 的一些形式有了根本的理解。可能大家曾经留神到，结尾我提到这个 bug 的复现程序在批改一个常数为 2 之后就不再复现，那到底是什么起因导致批改常数之后就不复现了呢？置信仔细的你通过钻研之后晓得了答案。Happy hacking ;-)
退出咱们
咱们是字节跳动基础架构的图平台团队，专一于构建世界一流的分布式图数据库和大规模图计算平台，反对抖音、今日头条等社交、举荐、风控等要害业务，致力于解决海量并发下 social graph 架构、举荐架构、用户画像、常识图谱等场景下的关键技术问题，把乏味的分布式系统技术落地，服务 10 亿级别用户，在继续招聘中。内推分割邮箱：tech@bytedance.com；邮件题目：姓名 – 工作年限 – 基础架构 – 图平台。
参考资料
[1] issue 40367:
https://github.com/golang/go/…
[2] 这条:
https://github.com/golang/go/…
[3] 这个网站:
https://godbolt.org/z/s9sWc4
[4] Go 规范库:
https://golang.org/src/encodi…
[5] 抽取 max 的相干代码:
https://golang.org/src/cmd/co…
[6] commit 7f8608047644ca34bad1728d5e2dbef041a1b3f2:
https://github.com/golang/go/…
更多分享
字节跳动破局联邦学习：开源 Fedlearner 框架，广告投放增效 209%
抖音品质建设 – iOS 启动优化《原理篇》
iOS 性能优化实际：头条抖音如何实现 OOM 解体率降落 50%+
字节跳动全链路压测 (Rhino) 的实际
欢送关注「字节跳动技术团队」
简历投递分割邮箱「tech@bytedance.com」
点击浏览原文，快来退出咱们吧！