摘要本文介绍了Go编译器的整体编译过程和一个编译优化错误导致数据越界访问的bug，并分析了排查修复针对这个bug的处理，希望能让大家对Go编译器有更多的了解，遇到类似问题时有排查思路。一天，群里有个朋友跟我打招呼，“看到有人说了一个Go的编译器bug，很有意思，感觉挺严重的，你要不要看一下？”所以我打开了issue40367[1]。当时最新的评论是这样的[2]：有人提到将循环体中的一个常量从1改成2无法重现问题，一下子引起了我的兴趣，于是打算研究一下。bug代码及现象如下图所示。正常情况下，代码应该在输出“56”后停止，但实际上它会无限期地继续执行。只能在触及未经授权的内存地址后强行终止或等待程序崩溃。首先，我们需要定位导致这个问题的具体直接原因。这个bug简单来说就是for-range循环越界。原始循环应该在循环次数达到数组长度后终止，但这个复制程序中的循环会继续无限执行。乍一看，问题好像出在boundcheck优化上了，我们来看一下。有一个方便的网站，您可以在线观察给定程序的编译输出。我用这个网站[3]生成了原来的复现程序和第6行把+1改成+2后没有复现的程序。编译供您比较。撇开无关紧要的细节不谈，不难看出前者的编译确实比后者少了一个判断，导致循环无法终止。具体位置是第二段代码的105行：既然已经找到了直接原因，那我们就得想办法跟编译器追上，看看为什么汇编结果有问题。对于很多同学来说，追着编译器检查问题的过程可能比较陌生，听上去很头疼，那么我们该如何排查这个问题呢？背景知识在跟踪这个具体问题之前，我们需要了解一些相关的知识背景。Go编译器的大致运行流程如果要追查Go编译器的问题，首先需要了解Go编译器的大致运行流程。事实上，Go编译器的实现是中规中矩的。与GCC/Clang等老牌编译器相比，甚至有些简陋，很多优化都没有实现。一个Go程序在生成汇编之前的工作大致分为这几个步骤：语法分析。由于Go语言的语法非常简单，Go编译器使用手写的LALR(1)解析器。这部分与今天的bug无关，不再赘述。类型检查。Go是一种强类型的静态类型语言。在编译过程中，会对赋值、函数调用等过程进行类型检查，以确定程序是否合法。另外，这一步会将Go自带的一些泛型函数转化为特定类型的函数调用，比如make函数，在类型检查阶段会根据类型检查的结果转化为具体的makeslice/makemap。这部分也和今天的bug无关。中间代码(IR)生成。为了便于跨平台代码生成和编译优化，现代编译器通常将语法树转化为一种中间代码表示，而这种表示的抽象通常介于语法树和平台汇编之间。Go选择一种形式的静态单一赋值（SSA）中间代码。这部分比较重要，将在下一小节中详细说明。编译优化。生成SSAIR后，编译器会根据这个IR运行很多pass（pass）代码分析和重写，每pass都会完成一个优化策略。另外值得一提的是，Go中的很多强度降低策略都是通过DSL来描述的，然后代码生成实际的通行码。不过，这篇文章与今天的内容无关。感兴趣的同学可以下来看看。在文章的后续内容中，我们会定位到造成本文bug的具体pass，看看那个pass中有问题的逻辑。在这几个步骤之后，编译器就可以为平台生成最终的汇编代码了。静态单次??赋值形式静态单次赋值是指在这种IR中，每个变量只会被赋值一次。这种形式的好处我们不再赘述，仅以一段简单的Go代码为例，帮助大家理解SSAIR的含义。这是一个简单的示例，右侧的Go代码具有相应的SSAIR。可以看到整个代码被分成了多个block，每个block（块）的代码以bXX开头，在缩进对应的末尾可以看到这个block会跳转到哪个block。在块内，您可以看到包括常量在内的每个值都有一个单独的名称。比如Go代码第4行和第5行对变量a的双重赋值，对应SSAIR中v7和v11的两个值。但是，如果代码中包含if之类的语句，编译时无法确定使用哪个值，那么在SSAIR中如何表达呢？例子中有这样一段代码，可以看到Go代码第六行的if。其实SSAIR中有一个专门的phi算子，就是专门针对这种情况设计的。phi运算符的意思是，返回值可能是参数的多个值中的任意一个，但是具体取值要看这个block这次是从哪个block跳出来的。上图中可以看到b2有一个phi算子，v22可能等于v11或者v21。具体取值取决于b2的前一个块是b1还是b3。其实对应的是if条件成立orinvalid。当然，这个例子中的if显然是成立的，但是我们这里看到的SSAIR是一个未优化的IR，在实际编译过程中会进行优化。Go编译器提供了一个非常方便的功能。您可以在每次优化通过之前和之后查看SSAIR。编译的时候只需要添加一个GOSSAFUNC=xxx的环境变量，其中xxx就是你要分析的函数名，因为Go编译器内部的优化是在函数层面的。比如上面的例子，你只需要运行GOSSAFUNC=maingobuildssaexample.go，编译器就会将SSAIR结果输出到当前目录下的ssa.html中，用浏览器打开。排错过程中追查问题的优化策略了解了这么多前置知识，我们终于可以追查到bug的具体原因了。第一步是通过从Go编译器转储SSAIR来检查哪个通道有问题。使用上一节中提到的方法，我们可以观察到问题中复制器的所有SSAIR。由于Go编译器有很多优化pass，ssa.html中记录了大量的SSAIR，我们如何找到有问题的pass？就我个人而言，由于之前的理解，我可以大致猜到这种问题是provepass的bug。但是即使你没有相关背景，既然我们已经知道这个bug的直接原因是没有进行比较判断，那么我们也可以通过二分法来检查是哪个pass缺少比较指令来定位。需要注意的是，你可能会定位到genericdeadcodepass，因为这个pass中少了一条Less64指令，如图（我这里使用的是Go1.15rc1，具体输出与编译器版本有关，可能是different),右边是genericdeadcodepass：可以看到相比左边，右边b4中的Less64消失了，再观察这个Less64的参数，v11就是常量6，也就是代码中数组的长度，可以确定这第一条指令是消失的边界判断。那么我们可以确定该错误存在于通用死代码通道中吗？并不真地。因为这pass只是把上pass已经变成死代码的部分删掉了。其实这行Less64在前面已经变成死代码了。从左侧指令的浅灰色可以看出，也就是说genericdeadcodepass其实是故障。但是从这里开始，要找出哪个pass变成了死代码就容易多了。你只需要在浏览器中点击这一行命令，就可以高亮显示这条命令的变化。很容易看出provepass有问题：右边是provepass，可以看到provepass中这条线变成了灰色。provepass的介绍把有问题的策略定位为provepass，那么接下来我们要看看provepass是干什么用的。其实provepass的作用就是对全局的SSA值的取值范围进行推断，这样可以省去很多不必要的分支判断。听起来是不是跟今天的bug密不可分？事实上，这是Go编译器中非常重要的一个pass，很多优化都依赖于这个pass之后得到的结果。例如，由于Go是内存安全的语言，所有的切片取元素操作都需要检查，判断取元素的下标是否超出了切片的范围。此操作称为绑定检查。但实际上，在很多代码中，在编译时就可以判断下标是否越界，这样我们就可以省去原本需要在运行时进行的绑定检查。这个优化步骤称为边界检查消除。具体代码示例如下一段是从Go标准库[4]中摘取的代码：func(bigEndian)PutUint64(b[]byte,vuint64){_=b[7]//earlyboundschecktoguaranteesafetyofwritesbelowb[0]=字节(v>>56)b[1]=字节(v>>48)b[2]=字节(v>>40)b[3]=字节(v>>32)b[4]=字节(v>>24)b[5]=byte(v>>16)b[6]=byte(v>>8)b[7]=byte(v)}可以看出b[7的操作]在这个函数中先执行，这样编译器在provepass中就可以知道当程序运行到第三行及以后的时候，sliceb的长度必须大于等于7，所以bound检查可以消除后续操作。然而，provepass不仅会优化boundcheckelimination的特定pattern，许多其他pattern也会在provepass中进行优化。那么今天provepass中的bug有什么问题呢？Provepasstroubleshooting说到定位代码问题，大概可以分为三种流派。第一种是打日志，通过在日志中添加信息来定位问题；二是通过gdb等调试器设置断点单步运行来排查问题；三是动态跟踪，通过perf/systemtap/ebpf等手段来动态观察程序在运行时的行为。具体到Go编译器，其实开发Go编译器的Go团队高手，日常也需要排查问题，也无外乎这些方法，但在编译时更喜欢第一种logging的方法优化，所以他们在每一关都预埋了很多调试日志，但是这些日志通常是不会打开的，需要专门的编译开关。由于provepass比较复杂，我们不妨通过查看日志来缩小排查范围。provepass的debuglog开关是-d=ssa/prove/debug=1，debug后面的数字越大，log越详细，我们只需要执行gotoolcompile-d=ssa/prove/编译时debug=1可以在bug.go中看到对应的log。具体这个bug，可以看debug=1级别的对比。如下图，左边是复现程序的log，右边是修改常量后没有复现的程序log：可以明显看出bug程序明显多了一个证明关系。此外，通过在编译器代码中grep这个日志关键字，可以发现只有函数findIndVar和addLocalInductiveFacts会打出这个日志。结合上下文和相关评论不难看出，问题其实出在函数addLocalInductiveFacts上级。addLocalInductiveFacts具体作用是什么？从注释不难看出，这里的作用是匹配一个特殊的codepattern，也就是类似repeatuntil的逻??辑，在循环结束时判断某个条件是否为真。具体这个函数的bug在哪里，我们需要使用更高级别的debug=3才能看到它的运行细节：我这里只截取了相关的log部分。可以看出，在有问题的归纳之前，先证明v10>=v16不成立。结合addLocalInductiveFacts可以发现，编译器实际上是将v10和v16作为循环变量的上下界，即代码中的min和max变量。但是结合SSAIR，不难看出v16根本就不是循环变量的上界，那么问题出在哪里呢？阅读addLocalInductiveFacts[5]中提取max的相关代码（上图）可以看出，这里的用意其实是从条件判断完成后循环头的phi操作所在的block开始，trace一路向前找到条件判断的block（ifblock），然后如代码中1104行，判断phi操作是if条件的分支逻辑，还是else逻辑，判断条件是否应该根据分支取反，因为如果是else分支逻辑，就说明条件判断结果为false，我们需要对条件取反，才能得到真正的逻辑条件。看到这里的代码，相信大家已经知道这个bug的根源了。代码1104-1113行写的很清楚。如果是条件分支，则br为正。如果是else分支，则br为负。但是，phi操作和if块之间没有间接关系。如果phi运算与if块没有直接关系，那么即使追溯到if块，也无法知道br变量是正还是负，取值也是未知的。但是在后续逻辑中，不判断unknown，而是默认跟随正过程；只是在这个bug复现程序中，phi操作所在的块与if块的else分支有间接关系，自然会出现正向过程。问题。上图是问题复现代码的ssacfg图片。可以明显看出b6与对应的b5并没有直接关联，而是间接关联，这就打错了代码路径。问题位于最后，那么如何解决呢？一个很简单的方法就是在br的求值逻辑后面直接加一个unknown判断逻辑，当br==unknown时直接退出判断。这样provepass显然会变得保守，但是可以保证正确性。添加这个检查后，bug重现程序运行正常，但是作为更通用的修复，我们在函数入口处添加了对入口块的判断，以确保入口块确实是循环开始块，而不是其他东西。它还可以匹配当前模式。我在上游提交了这个修复。因为这个bug很严重，而且这个修复对性能测量影响不大，所以很快就合并到master了，即commit7f8608047644ca34bad1728d5e2dbef041a1b3f2[6]，并且会cherrypick到前两个大版本1.13和1.14仍然致力于维护中间。如前所述，此补丁将使优化器更加保守，因此将进行其他修改以将优化器恢复到以前的水平。我也提交了相应的patch，但是由于1.15开发周期已经冻结，预计1.16发布周期合并到master。相信通过本文，你对Go编译器的运行过程和一些bug定位方法有了基本的了解。大家可能已经注意到，我开头提到的这个bug的复现程序，修改一个常量为2后就不再复现了，那么修改常量后不复现的原因是什么呢？相信细心的你一定会通过研究知道答案的。快乐黑客;-)
