第九章 独立于机器的优化

发表于 更新于

如果简单地把高级语言的每个构造独立地制评由在编译过程中，通过删除目标代码成机器代代码，那么这种用速度较快种方式会中引起较大的话换井完成同中同代营较慢的代码序列等变换来降低所生成代码的运行行开销，.势之为代母事情的代码

通过程序变换（局部变换和全局变换）来改进程序，称为优化

  • 介绍独立于机器的优化，即不考虑任何依赖目标机器性质的优化变换
  • 流图中循环的识别
  • 数据流分析
  • 代码改进变换

    9.1 优化的主要种类

    9.1.1 代码改进变换的标准

  • 代码变换必须保程序的含义
  • 采取安全稳妥的策略
  • 变换减少程序的运行时间平均达到一个可度量的值
  • 变换所作的努力是值得的

    9.1.2 公共子表达式删除

    9.1.3 复写传播

    形成为f := g的赋值叫做复写语句，优化过程中会大量引入复写，复写传播变换的做法是在复写语句f := g后，尽可能用g代表f。复写传播变换本身并不是优化，但它给其它优化带来机会：
    • 常量合并
    • 死代码删除

      9.1.4 死代码删除

  • 死代码是指计算的结果决不被引用的语句
  • 一些优化变换可能会引起死代码

    9.1.5 代码外提

  • 代码外提是循环优化的一种
  • 循环优化的其它重要技术
    • 归纳变量删除
    • 强度削弱

      9.1.6 强度削弱和归纳变量删除

      9.1.7 优化编译器的组织

  • 实现高级结构的操作在中间代码中是显式的
  • 中间代码基本上独立于目标机器

    9.2 流图中的循环

    9.2.1 必经结点

  • 结点d是结点n的必经结点，如果从初始结点起，每条到达n的路径都要经过d，写成d dom n
  • 每个结点是它本身的必经结点
  • 循环的入口是循环中所有结点的必经结点

    9.2.2 自然循环

  • 循环
    • 循环必须有唯一的入口点，叫做首结点，首结点是循环中所有结点的必经结点
    • 至少有一种办法重复循环，也就是至少有一条路径回到首结点
  • 回边
    • 如果有a dom b ，那么边b → a叫做回边
    • 寻找流图中所有循环的一个办法是找出流图的回边
  • 自然循环
  • 内循环
    • 若一个循环的结点集合是另一个循环的结点集合的子集。

      9.2.3 前置结点

      某些变换要求我们移动语句到首结点的前面

      9.2.4 可归纳流图

  • 一个流图G是可归约的，当且仅当
  • 有向边集合=正向边子集回边子集，并有性质:
    • 正向边子集形成有向无环图，在这个图中，每个结点可以从G的初始结点到达
    • 回边子集仅由前面所讲的回边组成
  • 非归约流图

    9.3 全局数据流分析介绍

  • 编译器需要把程序流图作为一个整体来收集信息
  • 并把这些信息分配给流图的各个基本块
  • 数据流信息可以通过建立和解数据流方程来收集

    9.3.1 点和路径

  • 点
    • 基本块中，两个相邻的语句之间为程序的一个点
    • 基本块的开始点和结束点
  • 路径
    • 点序列p1, p2, …, pn，对1和n - 1间的每个i，满足
    • pi是先于一个语句的点，pi＋1是同一块中位于该语句后的点，或者
    • pi是某块的结束点，pi＋1是后继块的开始点

      9.3.2 到达-定值

  • 确切定值：赋值语句或读语句
  • 可能定值：过程调用,别名,通过指针来赋值
  • 确切引用
  • 可能引用
  • 在给出简单的例子加以区别后，我们将不考虑过程调用、别名、通过指针来赋值等引起不确定性的情况。

    9.3.3 可用表达式

    9.3.4 活跃变量分析

    x的值在p点开始的路径上被引用，我们说x在p点活跃，否则称x在p点是死亡的

    9.4 代码改进变换

    依赖于上节收集的数据流信息进行代码改进变换，有些变换可以一起完成，但这里是逐个讨论，代替不了局部变换。

    9.4.1 公共子表达式删除

    对每个s: x := y + z，若y + z 在块的开始点可用,在s前没有y或z的定值，则执行下面的步骤：
    • 从该块开始反向搜索，找出到达该块开始点的y + z的计算
    • 建立新变量u
    • 把上面找到的每个语句w := y + z改成
      u := y + z
      w := u
    • 用x := u代替语句s

      9.4.2 复写传播

      9.4.3 寻找循环不变计算

  • 输入 循环L，对L的每个三地址语句，有ud链可用。
  • 输出 从控制进入L一直到离开L，每次都计算同样值的三地址语句被输出。
  • 方法
    • 把运算对象都是常量（或其所有的到达定值都在L外）的语句，标记为“不变”语句。
    • 重复下一步，直到没有新的语句标记为“不变”为止
    • 给下面的语句标记“不变”：它们先前没有标记，并且所有的运算对象都是下列三种情况之一：
      （a）常量；（b）其所有的到达定值都在L外；
      （c）只有一个到达定值，这个定值是循环中已标记为“不变”的语句。

      9.4.4 代码外提

  • 将循环不变语句提到循环的前置结点中
  • 并不是所有的循环不变语句都可以外提

    9.4.5 归纳变量删除

  • 循环归纳变量:在循环中，其值的每次改变都增加或减少某个固定的常量
  • 基本归纳变量：在循环中只有一个形如i := i  c的i，其中c是常量
  • 其它归纳变量:在循环中仅定值一次，并且其值是某个基本归纳变量的线性函数
  • 寻找归纳变量
    • 找出所有基本归纳变量i := i ± c，描述为(i, 1, 0)的形式
    • 寻找只有一个赋值的k，其形式为：k := jb, k := bj, k := j / b, k := j ± b, k := b ± j
    • 其中b是常数，j是基本的或非基本的归纳变量