斯坦福cs231(编译原理)の 9 Optimization

本文是斯坦福cs143编译原理的笔记，内容大部分来自于课件和自己的理解，笔者能力和精力有限，如果有错误欢迎指出

中间代码

什么是中间代码？一般常指介于高级语言(源语言)和低级语言(汇编语言)的一种语言

Provides an intermediate level of abstraction
- More details than the source
- Fewer details then the target

source lang =>intermediate lang => target lang

intermediate lang = high-level assembly

uses register names, but has unlimited number
Uses control structures like assemblly language
uses opcodes but some are higher level
- Eg: push translates to serveral assembly instructions
- most opcodes correspond directly to assembly opcodes

每个指令都是以下两种形式之一(三地址码)：

x := y op z
x := op y

🌰：表达式 x + y * z 可以转换成如下中间代码形式(每一个子表达式都有一个(寄存器)名称)：

t1 := y * z
t2 := x + t1

总结

中间代码的好处：与机器无关，可以在中间代码实现优化，提高了程序在不同系统架构之间迁移的可能性

优化

Optimization is complex and largest phase

Parsing => Semantic => Opt => Gen

什么时候做优化？

On AST ?
- Pro: Machine independent
- Cons: Too high level
On assembly lang ?
- Pro: Exposes optimization oppotunities
- Cons: Machine dependent
- Cons: Must reimplement optimizations when retargetting
On intermediate lang ?
- Pro: machine independent
- Pro: Exposes optimization oppotunities

Basic Block: is a maximal sequence of instructions with:

no labels (except at the first instructions), and
no jumps (except at the last instructions)

其实就是指一段除了起始入口和末尾跳转(退出)指令没有其他跳转(退出)指令的一段指令集

A basic block is a single-entry, single-exit, straight-line code segment

单一入口，单一出口，一行一行执行的程序段

control-flow graph：is a directed graph with:

Basic blocks as nodes
An edge from block A to block B if the execution can pass from the last instruction in A to the first instruction in B

eg:

the last instruction in A is jump LabelB
execution can fall through from block A to block B (在block A执行失败了后跳转到了block B)

优化的好处：

提高执行时间
减小代码体积
减少网络传输量
减小内存的使用
减小硬盘的使用（存储汇编代码文件）
减少硬件使用的电量 (这也可以，...)

优化的三个粒度：

local optimizations (局部优化)
- Apply to a basic block isolation
global optimizations (全局优化)
- Apply to a control-flow in isolation
Inter-procedural optimizations
- Apply across method boundaries

实际情况下：很难实现一个非常理想化的优化算法

为什么？
- 某些优化难以实现
- 某些优化会花费大量的编译时间
- 一些优化的回报很低
- 很多花哨的优化同时满足这三点

局部优化

优化基本block，不涉及整个代码，比较简单

algebra optimization (代数优化)

有些运算可以被另一些更快的运算代替：

x := x * 8 => x := x << 3

Constant fold（常数折叠）

Operations on constants can be computed at compile time:

if there is a statement x := y op z
and y and z constants
then y op z can be computed at compile time

Eg: x := 2 + 2 => x := 4; if 2 < 0 jump L can be deleted

常数折叠也并不安全，因为会存在交叉编译的情况：

在X架构上编译到架构Y上运行，编译后的产物在X上运行和在Y上运行可能会产生不同的结果

X: a : = 1.2 + 6.9 经过常数折叠后=> a := 8.1

Y: a: = 8

单一赋值形式：每一个寄存器名称仅仅出现在一次在赋值语句的左侧

x := z + b := z + y

a := x => a := b

x := 2 * x x := 2 * b

这里有一个很重要的概念，和变量活跃度有关：Single assigment form

基于这个假设：如果基本块是以单一赋值形式出现的，即 x:= 是在该块内仅有的一次为x赋值

那么当块内出现了相同的右侧表达式，这个表达式就是重复的（Common subexpression elimination）

🌰: 这个例子里x，y和z的值在省略号里是不会改变的

x := y + z x := y + z

... => ...

w := y + z w := x

Copy propagatation（拷贝传播）

假设基本块是以单一赋值形式存在的：

if w := x appears in a block, replace subsequent uses of w with uses of x

🌰:

b := z + y b := z + y

a := b => a := b

x := 2 * a x := 2 * b

Dead code elimination

上面的a := b对代码结果没什么恭喜，可以删除

Unresearchable code delete

删除不可达代码，减小代码体积

Eg: 不可能走的条件分支语句；导入了一个包里所有的工具，但是有没有用(有点类似tree shaking)

代数优化后：

拷贝传播后：

常数折叠：

公共子表达式删除：

最终：

Peephole Optimization

全局优化

为了在基本块之间用常数k代替变量x，编译器必须知道每条使用变量x路径的最后一个关于x的赋值语句x := k～～

对于全局优化，全局常量传播应该在～～处执行

所以全局优化的目标就是找到所有的～～

定义如下形式化符号：

value
$ $	This statement never executes（还没执行，一般用于初始化）
$ C $	X = C (C is constant)
$$	X is not a constant（已执行，但是不确定具体值）

常数拷贝：常数拷贝是很有用的因为它可以使得一些变量直接转换成常量，从而减少寄存器的使用，但是在控制图里，判断一个变量是否可以被替换成常量是困难的

一种思路是一个变量的信息和它的上下文有关（前后语句） \[ C(s, x, in) = value \quad of \quad x \quad before \quad s \quad 在语句s之前变量x的信息 \]

\[ C(s, x, out) = value \quad of \quad x \quad after \quad s \quad 在语句s之后变量x的信息 \]

由于课本上的规则过于复杂，本人总结了以下规则rules：

针对某个节点的入度，有以下几种情况：
1. 如果其入度节点其中有一个是T，则该节点信息为T
2. 如果其入度节点存在常量，但是均不相等，则该节点信息为T
3. 如果其入度节点存在节点固定为某个常量，且其入度节点不为T，则该节点也为该常量
4. 如果其入度节点均为unknown，则该节点为unknown
针对某个节点的出度，
1. 入度为unknown，则出度也为unknown
2. 在s语句赋值为某个常量，则出度为该常量
3. 在s语句赋值为某个非常量表达式，则出度为T
4. s语句如果没有对入度节点做任何更改，则出度=入度

伪代码描述常量传播：

For every entry s to the program,，set C(s, x, in) = $\top$ set C(s, x, in) = C(s, x, out) = \[\perp\] everywhere else repeat util all points satisfy 1-8： Pick s not satisfying 1-8 and update using the appropriate rule

为什么要引入$ $？

由于循环，循环的每个点都需要值存在

直觉上，分配一些初始值去打破循环

$ $表示直到目前为止，控制流程还没有到达当前点；

$\top$事一种抽象值，因为不知道运行的时候具体的值，

C之间是不可比较的

$\top$是最大的，$ $是最小的

符号形式化：

对是$ ,, C$进行排序： \[ \perp < C < \top \] 可以形象化如下：

定义 lub 运算：在这个层级规则下的最小上界

lub(x, y, z, ..)：大于等于x,y,z,...的最小值

部分可以写作：

1 2	`C(s, x, in) = lub { C(p, x, out) \| p is a predecessor of s }`

🌰：

Lub(到, 1) = 1

Lub(T, 1) = 1

Lub(1, 2) = T

之前简单的说一直重复直到没什么东西发生变化才停止是不准确，不规范的；

正式描述应该使用lub，lub为什么是正确的？

values start as 到 and only increase
$ $ can change to a constant, and a constant to $\top$
Thus, C(s, x, _) can change at most twice

常量拷贝算法是的时间复杂度和程序大小成正比

Number of steps =

Number of C(...) values computed * 2 = ✖️2是因为每个语句的最多算两次

Number of program statements * 4 ✖️2是因为每个语句的in and out

变量生存分析：

从程序退出节点开始分析，向上回溯节点，

如果当前节点包含出度的活跃变量的赋值语句，则当前节点的入度，就不会在有这个活跃变量(因为重新赋值了，之前的相当于是dead code，可以被视为dead variable)；
如果当前节点的rfs（右表达式）包含某个变量，则这些变量是活跃变量；

有两个exit节点，initNode = { a, b }, lives = { b }，开始自底向上分析

b = f + c 使用了f和c，产生了b，根据规则2，入度里f和c是活跃变量，根据规则1入度里b不是活跃变量 {f, c}

f = 2 * e 使用了e，根据规则2，入度里e是活跃变量，f是新的赋值，根据规则1入度里f不是活跃变量，格局规则3，c的活跃不发生变化 {c, e}

b = d + e，使用了d和e，根据规则2，d和e是活跃变量，而b被赋值了，c和f未出现1在左侧，所以{c,d,e,f}

e = e + 1, 使用了e，根据规则1，e是活跃变量，而c和f以及b都是其后续节点需要的，所以{b, c, e, f }

对于分支处，取并集得：{b, c, f}

对于f = 2 * e的入度，f被重新赋值，而e是被用的，所以{ c, e }

同理对于 b = d + e和e = e + 1的入度，其活跃变量已经计算过：{c, d, e, f}

取并集的e = d + f的出度 {c, d, e, f}

e = d + f的入度 => {c, d, f}

d = -a 的入度 => {c, a, f}

a = b + c的入度 => {f, c, b}

总结：

变量分析是自底向上，从程序的退出节点回溯的，因为程序退出的时候，可能希望某些变量依旧保存

编译原理

#编译原理，计算机基础，cool

斯坦福cs231(编译原理)の 9 Optimization

https://mingmingjiang1.github.io/emocoder/2023/05/14/编译原理/编译原理九/

作者

迷途知返

发布于

2023年5月14日

许可协议

斯坦福cs231(编译原理)の 11 Automatic Memory Management 上一篇

斯坦福cs231(编译原理)の 6 Cool Operational semantics 下一篇