课程主页:

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

课程视频:

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

备注:

图片均来自于课件。

这次回顾局部优化。

中间代码

简介

中间代码是

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

  • 提供中间级别的抽象

    • 比源语言更多的细节

    • 比目标代码更少的细节

  • 中间语言 = 高级汇编

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

例子

  • 每条指令的格式均为

    • $\mathrm y$和$\mathrm z$是寄存器或常量
    • 这是中间代码的常见形式
  • 表达式$\mathrm{x + y \star z}$被翻译为

    • 每个子表达式都有一个“名称”

代码生成

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

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

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

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

  • 不难看出

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

小结

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

优化概述

简介

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

分析

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

例子

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

其中

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

基本块

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

    • 没有标签(第一条指令除外)
    • 无跳跃(上一条指令除外)
  • 思想:

    • 无法跳入基本块(开头除外)
    • 无法跳出基本块(末尾除外)
    • 基本块是单入口单出口直线代码段
  • 考虑基本块

    • (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)
  • 在实际中,通常会刻意不实现最先进的优化方法
  • 为什么?
    • 某些优化难以实现
    • 某些优化会花费大量的编译时间
    • 一些优化的回报很低
    • 很多花哨的优化同时满足这三点
  • 我们的目标:以最低成本获得最大收益

局部优化

简介

局部优化是

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

常数优化

  • 某些语句可以删除

  • 某些语句可以化简

    (在某些机器上,$\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 {
      
      }

赋值优化

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

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

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

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

  • 如果

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

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

    • 例子:

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

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

    • 假设一次赋值

    • 该方法称为复制传播

    • 例子:

  • 仅对启用其他优化有用

    • 常数折叠(constant folding)
    • 死亡代码消除(dead code elimination)
  • 例子

死亡代码

  • 如果

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

    • 称$\mathrm{w := rhs}$语句dead,可以消除
    • dead =对程序结果无贡献
  • 例子:($\mathrm a$在其他任何地方均未使用)

小结

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

例子

初始代码:

代数优化:

复制传播:

常数折叠:

公共子表达式消除:

复制传播:

死亡代码消除:

最终版本:

习题

选择第三第四项。

窥孔优化(Peephole Optimization)

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

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

    • “窥孔”是简短的(通常是连续的)指令序列
    • 优化器将序列替换为另一个等效序列(但速度更快)
  • 编写窥孔优化作为替换规则

    其中rhs是lhs的改进版本

  • 例子:

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

  • 另一个例子

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

    • 示例:$\text {addiu $a $b 0 }\to \mathrm {move\ $a\ $ b}$
    • 示例:$\mathrm {move\ $a\ $ a} \to$
    • 这两个一起消除了$\text {addiu $a $a 0}$
  • 对于局部优化,必须重复应用窥孔优化以最大程度地发挥作用

小结

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