Stanford Compiler Week 7 Local Optimization

课程主页：

https://www.edx.org/course/compilers

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

备注：

图片均来自于课件。

这次回顾局部优化。

中间代码

简介

中间代码是

• 源代码和目标代码之间的语言

• 提供中间级别的抽象

  • 比源语言更多的细节

  • 比目标代码更少的细节

  • 

• 中间语言 = 高级汇编

  • 使用寄存器名称，但数量不受限制
  • 使用汇编语言之类的控制结构
  • 使用操作码，但有些是更高级别的
    • 例如，push转换为多个汇编指令
    • 大多数操作码直接对应于汇编操作码

例子

• 每条指令的格式均为

  $$\begin{array}{l} \text{x:=y op z} \\ \text{x:=op y} \end{array}$$
  • $\mathrm y$和$\mathrm z$是寄存器或常量
  • 这是中间代码的常见形式

• 表达式$\mathrm{x + y \star z}$被翻译为

  $$\begin{array}{l} \mathrm{t_{1}:=y\star z} \\ \mathrm{t_{2}:=x+t_{1} } \end{array}$$
  • 每个子表达式都有一个“名称”

代码生成

• 中间语言的代码生成类似于汇编代码生成

• 但是可以使用任意数量的IL寄存器来保存中间结果

• 记号：$\operatorname{igen}(\mathrm{e}, \mathrm{t})$

  • 计算寄存器$\mathrm t$中$\mathrm e$的值的代码

• 例子：

  $$\begin{aligned} \mathrm{igen\left(e_{1}+e_{2}, t\right)}= &\ \mathrm{igen\left(e_{1}, t_{1}\right)} \\ &\ \mathrm{igen\left(e_{2}, t_{2}\right)} \\ &\ \mathrm{t:=t_1+t_2} \end{aligned}$$

• 不难看出

  • 无限数量的寄存器=>简单的代码生成

小结

• 您应该要有能力使用中间代码
  • 只要达到在讲座中讨论的水平
• 您不需要知道如何生成中间代码
  • 因为我们不会进一步讨论
  • 但实际上只是代码生成的一种变体

优化概述

简介

• 编译器的整体流程
  • LA
  • Parsing
  • Sematic A
  • OPT
  • Code Gen
• 最优化是最后一个编译阶段
• 现代编译器中最复杂的是优化器
  • 也是迄今为止最大的阶段

分析

• 我们什么时候应该执行优化？
  • AST
    • 优点：与机器无关
    • 缺点：层级太高（too high level）
  • 汇编语言
    • 优点：展示优化机会
    • 缺点：与机器有关
    • 缺点：重新定位时必须重新实现优化
  • 中间语言
    • 优点：与机器无关
    • 优点：展示优化机会

例子

考虑如下语法指定的中间语言

$$\begin{aligned} \mathrm{P} \rightarrow\ & \mathrm{SP} \mid \mathrm{S} \\ \mathrm{S} \rightarrow\ &\text {id := id op id } \\ |& \text{ id := op id} \\ |& \text { id := id } \\ |& \text { push id } \\ |&\text { id := pop } \\ |&\text { i if id relop id goto L} \\ |&\text { L: } \\ |&\text { jump L } \end{aligned}$$

其中

• id是寄存器名称
• 常数可以替换id
• 典型运算符：$+,-,\star$

基本块

• 基本块是具有以下内容的最大指令序列：

  • 没有标签（第一条指令除外）
  • 无跳跃（上一条指令除外）

• 思想：

  • 无法跳入基本块（开头除外）
  • 无法跳出基本块（末尾除外）
  • 基本块是单入口单出口直线代码段

• 考虑基本块

  $$\begin{aligned} &1. \mathrm{L:}&& \\ &2. \quad\ \mathrm{t:=2\star x}\\ &3. \quad\ \mathrm{w:=t+x} \\ &4. \quad\ \mathrm{if\ w>0\ goto\ L'} \end{aligned}$$
  • (3)仅在(2)之后执行
    • 我们可以将(3)更改为$\mathrm{w:= 3 \star x}$
    • 我们是否也可以消除(2)？

控制流图

• 控制流图是有向图，特点是
  • 基本块作为节点
  • 如果执行可以从A中的最后一条指令传递到B中的第一条指令，则存在从块A到块B的边
  • 例如，A中的最后一条指令是$\mathrm{jump\ L_{B} }$，那么块A可能会进入块B
• 方法（或过程）的主体可以表示为控制流图
• 有一个初始节点
• 所有“返回”节点均为终止节点

例子：

小结

• 优化旨在提高程序的资源利用率
  • 执行时间（最常见），对应memory
  • 代码大小 ，对应disk
  • 发送的网络消息等，对应power

• 优化不应改变程序的计算结果

  • 结果必须仍然相同

• 对于C和Cool这样的语言，存在三种优化粒度

  • 1. 局部优化
    • 分别应用于基本块
  • 1. 全局优化
    • 单独应用于控制流图（方法主体）

  • 3 . 过程间优化

    • 跨方法边界应用
• 大多数编译器会执行（1），很多会执行（2），很少会执行（3）
• 在实际中，通常会刻意不实现最先进的优化方法
• 为什么？
  • 某些优化难以实现
  • 某些优化会花费大量的编译时间
  • 一些优化的回报很低
  • 很多花哨的优化同时满足这三点
• 我们的目标：以最低成本获得最大收益

局部优化

简介

局部优化是

• 最简单的优化形式
• 优化一个基本块
  • 无需分析整个程序主体

常数优化

• 某些语句可以删除

  $$\begin{aligned} \mathrm{x}&:=\mathrm{x+0} \\ \mathrm{x}&:=\mathrm{x * 1} \end{aligned}$$

• 某些语句可以化简

  $$\begin{aligned} \mathrm{x:=x * 0} & \Rightarrow \mathrm{x:=0} \\ \mathrm{y:=y * * 2} & \Rightarrow \mathrm{y:=y * y} \\ \mathrm{x:=x* 8} & \Rightarrow \mathrm{x:=x\ll3} \\ \mathrm{x:=x* 15} & \Rightarrow \mathrm{t:=x\ll4 ; x:=t-x} \end{aligned}$$

  （在某些机器上，$\ll$比$\star$快，但不是在所有机器上都是这样）

• 常量运算可以在编译时计算

  • 如果有语句$\text{x:=y op z}$
  • 并且$\mathrm{y}$和$\mathrm z$是常数
  • 那么可以在编译时计算$\text{y op z}$
  • 示例：
    • $\mathrm{x:=2+2 \Rightarrow x:=4}$
    • $\text { if 2<0 jump L}$可以被删除
  • 该方法称为常数折叠（constant folding）

• 常数折叠可能是危险的

  • 考虑交叉编译

      Compiler    -------->	  Gen Code
      ---------                ---------
    |		|			   |	    |
      |	X	|			   |	Y   |
      ---------			    ---------

  • X和Y架构不同，那么在X机器上，可能

    a := 1.5 + 3.7
    a := 5.2

    但是在Y机器上，可能

    a := 5.19

删除

另一种优化方式是删除：

• 消除无法访问的基本块：

  • 从初始块无法访问的代码
    • 例如，不是条件跳跃或“跌落”目标的基本块

• 删除无法访问的代码使程序更小

  • 有时也更快
    • 这是由于内存缓存的影响
    • 增加空间局部性

• 为什么会出现无法到达的基本块？

  • 考虑调试的例子：

    #define DEBUG 0
    if (DEBUG) then {
    
    }

赋值优化

• 如果每个寄存器在赋值的左侧仅出现一次，则简化了某些优化

• 因为可以以单一分配形式重写中间代码

  $$\begin{aligned} \begin{aligned} &\mathrm{x:=z+y} \\ &\mathrm{a:=x} \\ &\mathrm{x:=2 * x } \end{aligned} \Rightarrow \begin{aligned} &\mathrm{b:=z+y} \\ &\mathrm{a:=b} \\ &\mathrm{x:=2 * b} \end{aligned} \end{aligned}$$

  • $\mathrm b$是新的寄存器。

  • 由于循环，一般情况下这种替换更复杂。

• 如果

  • 基本块采用一次赋值形式
  • 定义$\mathrm{x :=}$是$\mathrm{x}$在块中的首次使用

• 那么

  • 当两个赋值具有相同的rhs时，它们将计算相同的值

  • 例子：

    $$\begin{aligned} \begin{aligned} &\mathrm{x:=y+z} \\ &\ldots \\ &\mathrm{w:=y +z } \end{aligned} \Rightarrow \begin{aligned} &\mathrm{x:=y +z} \\ &\ldots \\ &\mathrm{w:=x} \end{aligned} \end{aligned}$$

    假设（$\mathrm {x,y }$和$\mathrm {z}$的值在…代码中不变）

• 如果$\mathrm{w:= x}$出现在块中，则将$\mathrm{w}$的后续使用替换为$\mathrm{x}$的使用

  • 假设一次赋值

  • 该方法称为复制传播

  • 例子：

    $$\begin{aligned} \begin{aligned} &\mathrm{b:=z+y} \\ &\mathrm{a:=b} \\ &\mathrm{x:=2 * a } \end{aligned} \Rightarrow \begin{aligned} &\mathrm{b:=z+y} \\ &\mathrm{a:=b} \\ &\mathrm{x:=2 * b} \end{aligned} \Rightarrow \begin{aligned} &\mathrm{b:=z+y} \\ &\mathrm{x:=2 * b} \end{aligned} \end{aligned}$$

• 仅对启用其他优化有用

  • 常数折叠（constant folding）
  • 死亡代码消除（dead code elimination）

• 例子

  $$\begin{aligned} \begin{aligned} &\mathrm{a:=5} \\ &\mathrm{x:=2*a} \\ &\mathrm{y:=x + 6}\\ &\mathrm{t:=x*y} \end{aligned} \Rightarrow \begin{aligned} &\mathrm{a:=5} \\ &\mathrm{x:=10} \\ &\mathrm{y:=16}\\ &\mathrm{t:=x\ll 4}\\ \end{aligned} \end{aligned}$$

死亡代码

• 如果

  • $\mathrm{w := rhs}$出现在基本块中
  • ${\mathrm w}$在程序中其他任何地方都没有出现

• 那么

  • 称$\mathrm{w := rhs}$语句dead，可以消除
  • dead =对程序结果无贡献

• 例子：（$\mathrm a$在其他任何地方均未使用）

  $$\begin{aligned} \begin{aligned} &\mathrm{x:=z+y} \\ &\mathrm{a:=x} \\ &\mathrm{x:=2 * a } \end{aligned} \Rightarrow \begin{aligned} &\mathrm{b:=z+y} \\ &\mathrm{a:=b} \\ &\mathrm{x:=2 * b} \end{aligned} \Rightarrow \begin{aligned} &\mathrm{b:=z+y} \\ &\mathrm{x:=2 * b} \end{aligned} \end{aligned}$$

小结

• 每个局部优化本身起很小的作用
• 通常，优化会相互影响
  • 执行一项优化可实现另一项优化
• 优化编译器重复优化，直到无法进行改进为止
  • 优化器也可以随时停止以限制编译时间

例子

初始代码：

代数优化：

复制传播：

常数折叠：

公共子表达式消除：

复制传播：

死亡代码消除：

最终版本：

习题

选择第三第四项。

窥孔优化（Peephole Optimization）

• 优化可以直接应用于汇编代码

• 窥孔优化可有效改善汇编代码

  • “窥孔”是简短的（通常是连续的）指令序列
  • 优化器将序列替换为另一个等效序列（但速度更快）

• 编写窥孔优化作为替换规则

  $$\mathrm{i}_{1}, \ldots, \mathrm{i}_{\mathrm{n} } \rightarrow \mathrm{j}_{1}, \ldots, \mathrm{j}_{\mathrm{m} }$$

  其中rhs是lhs的改进版本

• 例子：

  $$\mathrm {move\ \$a\ \$ b,\ move\ \$b\ \$a \rightarrow move\ \$a\ \$ b}$$

  如果$\mathrm{ move\ $b\ $a}$不是jump的目标

• 另一个例子

  $$\text { addiu \$a \$a i, addiu \$a \$a } \mathrm{j} \rightarrow \text {addiu \$a \$a i+j }$$

• 许多（但不是全部）基本块优化可以转换为窥孔优化

  • 示例：$\text {addiu $a $b 0 }\to \mathrm {move\ $a\ $ b}$
  • 示例：$\mathrm {move\ $a\ $ a} \to$
  • 这两个一起消除了$\text {addiu $a $a 0}$

• 对于局部优化，必须重复应用窥孔优化以最大程度地发挥作用

小结

• 许多简单的优化仍然可以应用于汇编语言
• “程序优化”的名称严重错误
  • 在任何合理的意义上，“优化器”产生的代码都不是最佳的
  • “Program improvement”是一个更合适的术语