申请试用
HOT
登录
注册
 
Go语言编译器简介
0 点赞
0 收藏
0下载
无厘头
/
发布于
/
217
人观看

编译器的重要性

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

前端语义分析

  • 类型检查
  • 确定变量的作用域
  • 内联
  • 常量折叠/常量传播
  • 闭包分析
  • 逃逸分析
  • 导入(import/include)
  • 其它

中端体系无关优化

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

后端机器相关优化

  • 高效指令选择
  • 指令调度
  • 流水线优化
  • 缓存优化
  • 并行优化
  • 窥孔优化
  • 其它
展开查看详情

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)

0 点赞
0 收藏
0下载