【编译原理】7、代码优化

编译原理目录
1、词法分析
2、语法分析（重点）
3、语法制导翻译与抽象语法树
4、语义分析
5、代码生成
6、中间代码与程序分析
7、代码优化

七、代码优化

优化的位置

1. 基本概念

什么是代码优化？

• 代码优化是对被优化的程序进行的一种语义保持的变换（或改写）
• 语义保持：程序的可观察行为不能改变
• 变换的目的是让程序能够比变换前：更小、更快、cache行为更好、更节能等等。

不存在“完全优化”

• 等价于停机问题：给定程序p，把Opt(p) 和下面的程序比较:L:jmp L
• 这称为“编译器从业者永不失业定理”。

代码优化很困难

• 不能保证优化总能产生“好”的结果
• 优化的顺序和组合很关键
• 很多优化问题是非确定的
• 优化的正确性论证很微妙

正确的观点

• “把该做对的做对”
• 不是任何程序都会同概率出现
• 所以能处理大部分常见情况的优化就可以接受
• “不期待完美编译器”
• 如果一个编译器有足够多的优化，则就是一个好的编译器

---

• 前端优化

  • 局部的、流不敏感的
  • 常量折叠、代数优化、死代码删除等

• 中期优化

  • 全局的、流敏感的
  • 常量传播、拷贝传播、死代码删除、公共字表达式删除等

• 后端优化

  • 在后端（汇编代码级）进行
  • 寄存器分配、指令调度、窥孔优化等

2. 前端优化

对 抽象语法树 进行优化

2.1 实例1 —— 常量折叠

基本思想： 在编译期计算表达式的值

• 例如： a = 3 + 5 ==> a = 8
• 例如： if (true && false) ==> if (false)

算法：

// 语法制导的常量折叠算法
const_fold(Exp_t e)
  while (e is still shrinking)
    switch (e->kind)
      case EXP_ADD:
        Exp_t l = e->left;
        Exp_t r = e->right;
        if (l->kind==EXP_NUM && r->kind==EXP_NUM)
          e = Exp_Num_new (l->value + r->value);
        break;
      case...
      default:
        break;

优缺点

• 容易实现、可以在语法树或者中间表示上进行
• 通常被实现成公共子函数被其它优化调用

• 必须要很小心遵守语言的语义：例如考虑溢出或异常的。

  • 例子： 0xffffffff+1 ==> 0 (???)

2.2 实例2 —— 代数化简

基本思想：

• 利用代数系统的性质对程序进行化简，示例：

  • a = 0+b ==> a = b
  • a = 1*b ==> a = b
  • 2*a ==> a + a （强度消弱）
  • 2*a ==> a<<1 （强度消弱）

• 同样必须非常仔细的处理语义

  • 示例： (i-j) + (i-j) ==> i+ i -j -j (×)

算法

// 代数化简的算法
alg_simp(Exp_t e)
  while (e is still shrinking)
    switch (e->kind)
      case EXP_ADD:
        Exp_t l = e->left;
        Exp_t r = e->right;
        if (l->kind==EXP_NUM && l->value==0)
        e = r;
      case ...
      break;
        case ...: ...; // 类似

2.3 实例3 —— 死代码（不可达代码）删除

基本思想：

• 静态移除程序中不可执行的代码，示例：

  • if (false) s1; else s2;
  • ==> s2;
• 在控制流图上也可以进行这些优化，但在早期做这些优化可以简化中后端。

算法：

// 不可达代码删除算法
deadcode(Stm_t s)
  while(s is still shrinking)
    switch (s->kind)
      case STM_IF:
        Exp_t e = s->condition;
        if (e->kind==EXP_FALSE)
        s = s->elsee;
      case ...
      break;
        case ...: ...; // 类似

3. 中间表示层优化

3.1 中间表示上的代码优化

• 依赖于具体所使用的中间表示：控制流图(CFG)、控制依赖图(CDG)、静态单赋值形式(SSA)、后续传递风格(CPS)等

• 共同的特点是需要进行程序分析

  • 优化是全局进行的，而不是局部
  • 通用的模式是： 程序分析 → 程序重写

• 在这部分中，我们将基于控制流图进行讨论

  • 但类似的技术可以用于其它类型的中间表示

优化的一般模式

• 程序分析

  • 控制流分析，数据流分析，依赖分析， …
  • 得到被优化程序的静态保守信息 (是对动态运行行为的近似)

• 程序重写

  • 以上一步得到的信息制导对程序的重写

3.2 实例1 —— 常量传播

算法

// 常量传播算法
const_prop(Prog_t p)
  // 第一步：程序分析,到达定义分析
  reaching_definition(p);
  // 第二步：程序改写
  foreach (stm s in p: y = x1, ..., xn)
    foreach (use of xi in s)
      if(the reaching def of xi is unique: xi = n)
        y = x1, ..., xi-1, n, xi+1, ..., xn

示例：

3.3 实例2 —— 拷贝传播

算法：

// 拷贝传播算法
copy_prop(Prog_t p)
  // 第一步：程序分析,到达定义分析
  reaching_definition(p);
  // 第二步：程序改写
  foreach (stm s in p: y = x1, ..., xn)
    foreach (use of xi in s)
      if(the reaching def of xi is unique: xi = z)
        y = x1, ..., xi-1, z, xi+1, ..., xn

3.4 实例3 —— 死代码删除

live_out：最后用的到的变量值

算法：

// 死代码删除算法
dead_code(Prog_t p)
  // 第一步：程序分析
  liveness_analysis(p); // 得到每一个语句的out[]集合
  // 第二步：程序改写
  foreach (stm s in p: y = ...)
    if (y is NOT in live_out[s])
      remove (s);