• 根据中间表示(IR)生成代码
• 代码生成器之前可能有一个优化组件
• 代码生成器的三个任务
  • 指令选择: 选择适当的指令实现IR语句
  • 寄存器分配和指派: 把哪个值放在哪个寄存器中
  • 指令排序: 按照什么顺序安排指令执行

ch8-8.2

目标机模型

常见指令：

指令翻译

栈式分配

例题：

假设使用栈式分配而寄存器SP指向栈的顶端，为下列的三地址语句生成代码。假设起始地址为100，过程p、q、r的入口地址分别为200、400、600

1
2
3
4
5
6

call p
call q
return
call r
return
return

答案：

块内优化

许多局部优化技术需要先将基本块内的指令转化为有向无环图(Directed Acyclic Graph, DAG)

构建DAG

规则：

示例：

局部公共子表达式优化

• 建立某个结点M之前，检查是否存在一个结点N，它和M具有相同的运算符和子结点（顺序也相同）

• 如果存在，则不需要生成新的结点，用N代表M

例如：（注意：两个b+c语句不是，其中的b是不同的）

代数恒等式优化

• 恒等式

  • , , ,

• 强度消减

  • , ,

• 常量合并/折叠

  • 2*3.14可以用6.28替换

• 通用代数转换规则

  • 交换律和结合律等，如

实现这些优化，只需在DAG图上寻找特定的模式

窥孔优化

窥孔优化(peephole optimization): 使用一个滑动窗口(窥孔)来检查目标指令，在窥孔内实现优化

• 冗余指令消除

• 控制流优化

• 代数化简

• 机器特有指令的使用

示例一	示例二

冗余指令消除

• 多余的LD/ST指令

  • LD R0, a
  • ST a, R0 //可删除

• 级联跳转代码

  • if debug == 1 goto L1; goto L2; L1: …; L2: …;
  • 如果已知debug一定是0, 那么替换成为goto L2

控制流优化

代数化简和机器特有指令

• 应用代数恒等式

  • 消除x = x + 0, x = x * 1, …

• 使用机器特有指令

  • INC, DEC, …

ch8-3 寄存器分配

寄存器分配目的：

• 减少寄存器使用

• 少溢出

• 寄存器速度快

局部寄存器分配

全局寄存器分配—图着色

chaitin算法

另外例子：

线性扫描寄存器

寄存器分配的优化（为什么优化）

• 溢出优化：尽量减少寄存器溢出，以降低内存访问的影响。

• 重用寄存器：在可能的情况下，尽量重用已经分配的寄存器，减少指令数量和内存访问。

无法被分配在相同的寄存器的变量必须被保留在随机存取存储器，在需要读取或写入时才会被加载，这个过程称之为溢出（spilling）。

ch9 基于DFA优化

语义不变的优化方法

全局公共子表达式

• 公共子表达式

  • 在某次出现之前必然已被计算过
  • E的运算分量在该次计算之后没有被改变

• 如果上次公共子表达式E值赋给了x，且x值没有被修改过，那么我们可使用x，而无需计算E

复制传播

死代码消除

代码移动

• 循环中的代码会被执行很多次

  • 循环不变表达式: 循环的同一次运行的不同迭代中，表达式的值不变

• 把循环不变表达式移动到循环入口之前计算可以提高效率

  • 循环入口: 进入循环的跳转都以这个入口为目标

例如while (i <= limit – 2){...}，如果limit在循环体内不会改变, 则可在循环外计算limit - 2。可以优化为t = limit - 2; while(i <= t){...}

归纳变量和强度消减

数据流分析

回顾一些基本概念：

• 基本块（Basic Block）：一个基本块是一段没有分支和跳转的连续代码。换句话说，它是一个入口和一个出口之间的代码段，只有在入口处进入，并且在出口处离开。

• 控制流图（Control Flow Graph, CFG）：控制流图是由基本块作为节点，控制流作为边构成的有向图。它展示了程序执行的所有可能路径。

通过数据流方程，计算每个基本块的入口和出口状态。常见的数据流方程包括：

• 到达定义（Reaching Definitions）：哪些变量定义可以到达这个基本块。

• 活跃变量（Live Variables）：哪些变量在基本块之后仍然需要使用。

• 可用表达式（Available Expressions）：哪些表达式在基本块入口处已经计算过且没有被修改。

数据流分析基础

• 每条IR语句 s 将一个 input state 转换成一个新的 output state

• The input（output）数据流信息分别与语句 s 的前（后）点相关联

• 设基本块B由语句 S1，S2，.，Sn 顺序组成，则必有：

  • , for all i = 1, 2, …, n-1
  • 

• 语句s的转移函数
  

• 正向分析和反向分析
  

• 到达-定值分析
  

• 到达定值的转移函数（传递方程）：

  • Reaching Definitions定义：A definition d may reach a program point, if there is a path from d to the program point such that d is not killed along the path
    

• 基本块的转移函数：
  

例题：
手动计算：（根据到达-定值分析）例如in[B2]中d4因为d7被杀死所以为X）

• 计算到达定值的迭代算法
  

  • 和不变，随着更多信息流入in[B]，使得out[B]从不收缩（0->1,1->1）
  • 定值点是有穷的

例题：基于算法计算

• UD链-引用的定值链
  

活跃变量分析

• 活跃变量

  • 对于程序中的变量v和某点p：流图中存在一条从p开始的通路引用v在点p的值，则称v在点p是活跃的（live），否则是不活跃的（dead）。

• 活跃变量的转移函数
  

• 活跃变量数据流方程
  

• 活跃变量的迭代算法
  

可用表达式分析

• 可用表达式

  • 如果从流图的入口节点到达程序点 p的每条路径都对表达式x op y进行计算，并且从最后一个这样的计算到点p之间没有再次对x或y定值，那么表达式x op y在点p是可用的（available）

• 表达式可用的直观意义

  • 在点 p，x op y已经在之前被计算过，不需要重新计算

• 计算可用表达式的迭代算法
  

• ← Previous Post
• Next Post →