MENU

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

June 1, 2020 • Read: 704 • 编程之路,编译原理

编译原理目录
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);
- - - 结束 - - -
  • 文章标题:【编译原理】7、代码优化
  • 文章链接:https://blog.canye365.cn/archives/317.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021