Go语言编译器简介

1 .Go语言编译器简介 史斌 

2 .关于我 

3 .编译器的重要性 • 只有1%的程序员懂汇编语言 • 汇编语言无法构建大型系统 • 操作系统内核也需要编译器才能运行起来 • 编译理论是图灵奖大户，仅次于计算复杂度理论 • 操作系统有后门，编译器的后门更致命 

4 .编译器的难题：任务爆炸 N种语言 * M种机器 = N*M 个任务 

5 .两个方案 N种语言 + M种机器 = N+M 个任务 其它语言 -> C -> 各个机器 各个语言 -> x86 -> 其它机器 matlab Just In Time Ahead Of Time go-1.3 

6 .通用（非专用）编译器的方案 AST = Abstract Syntax Tree 抽象语法树 SSA = Single Static Assignment 单静态赋值 IR = Intermediate Representation 中间表示 优点： 1. 减少任务； 2. 代码复用； 3. 相关理论成熟高效； 

7 .LLVM的三阶段结构 前端 中端 后端 

8 .Go编译器工作流程初窥 从源码到汇编，需要48道工序！ 

9 .Go编译器工作流程 48 个 工 序 ， 被 分 为 九 个 阶 段 ， 前 中 后 三 端 。 

10 .前端语法分析：Source -> AST func ssa(a int) (int, int) { return a / 2, a * 2 } 

11 .前端语义分析：常量折叠 a=2*3-c → a=6-c → 

12 .前端语义分析：内联 func A(a b int) int { return a * b } func B(a, b, c int) int { return A(a, b) + c } ↓ func B(a, b, c int) int { return a*b + c } 

13 .前端语义分析 • 类型检查 • 确定变量的作用域 • 内联 • 常量折叠/常量传播 • 闭包分析 • 逃逸分析 • 导入（import/include） • 其它 

14 .SSA IR func ssa(n uint) uint { ssa: s := uint(0) n := param[0] for i := 0; i < n; i++ { s := 0 } s=s+i*i → _loop: i := 0 return s c := (i >= n) } if (c) goto _end tmp0 := i * i s = s + tmp0 SSA IR: 没有人类可读的结构， i=i+1 它更像汇编语言： goto _loop 1. 赋值 _end: 2. 一元/二元运算 ret[0] = s 3. goto 4. if-goto 5. 传递参数/返回值 

15 .SSA IR func ssa(n, m int) int { ssa: if n > m { n := param[0] return n - m m := param[1] } else { return m - n → c := (n <= m) var tmp0 } if (c) goto _b2 } tmp0 = n - m goto _end _b2: SSA IR: 没有人类可读的结构， tmp0 = m - n 它更像汇编语言： _end: 1. 赋值 ret[0] = tmp0 2. 一元/二元运算 3. goto 4. if-goto 5. 传递参数/返回值 

16 .中端体系无关优化：公共子表达式消除 → tmp0 = a * b tmp0 = a * b tmp1 = tmp0 + c tmp1 = tmp0 + c tmp2 = a * b tmp3 = tmp0 - c ← tmp3 = tmp2 - c ← ret[0] = tmp1 ret[0] = tmp1 ret[1] = tmp3 ret[1] = tmp3 

17 .中端体系无关优化：运算强度消减 ssa: ssa: → a = param[0] tmp0 = a * 4 → a = param[0] tmp0 = a << 2 ret[0] = tmp0 ret[0] = tmp0 ssa: ssa: → → a = param[0] a = param[0] tmp0 = a % 256 tmp0 = a & 255 ret[0] = tmp0 ret[0] = tmp0 

18 .中端体系无关优化：常量折叠 ssa: ssa: a = param[0] a = param[0] → b=a*3 → tmp0 = a * 9 tmp0 = b * 3 ret[0] = tmp0 ret[0] = tmp0 

19 .中端体系无关优化：循环优化 Go编译器尚未实现！ 循环不变量放到循环体外面 循环归纳变量：变乘为加 

20 .中端体系无关优化 • 常量传播/常量折叠 • 复制传播 • 强度消减 • 循环不变量/归纳变量 • 冗余消除 • 活跃分析 • 向量优化 • 其它 

21 .后端：指令选择 正则表达式模式匹配 

22 .后端：X86相关优化 x=0 // 优化成x=x^x，因为"XOR AX,AX"的指令码比"MOV $0,AX"更短 x=y*2+z // 使用LEA指令，避免先移位后相加两步运算 x=x&0xffff7fff // 使用BCLR指令将bit-15清零（其它位不变），取消位与运算 x++ // 使用"INC AX"取代"ADD $1,AX" x-- // 使用"DEC AX"取代"SUB $1,AX" if ((x&0x8)==0) // 使用TEST指令，避免AND+CMP两步运算 if (a == 0) // 使用"TEST AX,AX"，避免"CMP $0,AX" a > 0 ? b : c // 使用CMOV，避免分支跳转 if // 使用JZ/JC/JNZ等条件跳转指令 

23 .后端：ARM相关优化 x=y+z*8 // 加/与/或运算指令，其中一个操作数可以带移位，单周期完成 x=y-z*8 // SUB指令，减数可以带移位，单周期完成 x=z*8-y // RSB指令，被减数可以带移位，单周期完成 d=x*y+z // 使用单条MLA指令，避免先乘后加两步操作 d=z-x*y // 使用单条MLS指令，避免先乘后减两步操作 x=y+0xffff // 分解成两步，x=y+0xff，x=x+0xff00，优化常量池 x=y+0xaeff80 // 分解成两步，x=y+0xaf0000，x=x-0x80，优化常量池 if ((x&0x8)==0) // 使用TST指令，避免AND+CMP两步运算 if ((x^0x8)==0) // 使用TEQ指令，避免XOR+CMP两步运算 if ((x+y)>0) // 使用CMN指令，避免ADD+CMP两步运算 

24 .后端机器相关优化 • 高效指令选择 • 指令调度 • 流水线优化 • 缓存优化 • 并行优化 • 窥孔优化 • 其它 

25 .我对Go编译器的优化 t0 = b * c : MUL Rb, Rc, Rt0 t1 = a + t0 : ADD Ra, Rt0, Rt1 t1 = a + b * c : MADD Rb, Rc, Ra, Rt1 普通的机器指令只有两个操作数并 生成一个结果，因此a+b*c需要拆分 成MUL/ADD两条指令；而ARM64 上有MADD指令，带三个操作数， 一次生成a+b*c的结果。此类优化 并不适用X86。 https://github.com/golang/go/commits?author=benshi001 

26 .我对Go编译器的优化 var array float32[] address = base + index : ADD Rb, Ri, Ra temp = *addr : FMOVS (Ra), Fx var array float32[] temp += *(base + index) : FMOVS (Rb)(Ri), Fx 从数组中取一个浮点数，需要先计算 地址（数组基地址加索引），然后读取 内存，共两条指令；而ARM64读取内存 指令可以同时包括基地址和索引偏移量。 https://github.com/golang/go/commits?author=benshi001 

27 .我对Go运行时库的优化 使用硬件除法器替代软件除法算法， 除法性能提升40%； 保持兼容性，ARMv5和ARMv6上使用 软件除法，ARMv7上使用硬件除法； 程序启动时，动态探测当前硬件版本 并选择除法实现； https://github.com/golang/go/commits?author=benshi001 

28 .我发现及修复的bug TST Ra, Rb；64位位测试指令 TSTW Ra, Rb；32位位测试指令 https://github.com/golang/go/issues/created_by/benshi001 

29 .学习编译器的益处 • 理解Go程序运行机制，提升代码质量 • 提升内功：词法分析涉及到正则表达式 • 提升内功：语法语义分析涉及到树变换和树搜索 • 提升内功：中端有大量的关于图变换和图搜索的高效算法 • 提升内功：掌握不同处理器/平台的特点 • 定制自己的DSL（Domain Specific Language）