编译-第14章-代码优化

•
Compiler

一、代码优化概述

1.1 基本概念

代码优化指编译程序为了生成高质量的目标程序而做的各种加工和处理，主要目的是提高目标代码的运行效率，包括时间效率（减少运行时间）和空间效率（减少内存容量）。

优化必须严格遵循”不能改变原有程序语义”的原则。

1.2 优化代价与效果关系

优化所花费的代价和优化产生的效果呈非线性关系：简单的处理能带来明显的优化效果，但要进一步提高效果就需要付出更大的代价。

二、优化分类

2.1 按优化层次分类

与机器无关的优化技术 ：在中间代码上进行的优化，如数据流分析、常量传播、公共子表达式删除、死代码删除、循环交换、代码内联等。

与机器相关的优化技术 ：充分利用系统资源，包括面向超标量超流水线架构的指令调度、面向SMP架构的同步负载优化、面向SIMD/MIMD/SPMD架构的数据级并行优化等。

2.2 按优化范围分类

局部优化 ：在基本块内进行的优化，如局部公共子表达式删除。

循环优化 ：对循环语句所生成的中间代码序列上所进行的优化。

全局优化 ：函数/过程内进行的优化，跨越多个基本块，如全局数据流分析。

跨函数优化 ：整个程序范围内的优化，如跨函数别名分析、逃逸分析等。（难，不是重点😭）

三、基本块和流图

3.1 基本块定义

基本块是具有以下特征的连续语句序列：

  • 程序的执行只能从基本块的第一条语句进入
  • 程序的执行只能从基本块的最后一条语句离开

3.2 基本块划分算法

算法14.1 划分基本块的步骤：

  1. 确定入口语句集合：
    • 整个语句序列的第一条语句
    • 能被跳转语句转移到的第一条语句
    • 紧跟在跳转语句之后的第一条语句
  2. 每个入口语句到下一个入口语句（或程序结束）之间的所有语句属于同一基本块

同时，在划分基本块时要注意return语句也是一种跳转语句，意味着程序执行到return语句时会跳出当前函数，因此紧跟在return语句之后的第一条语句也应作为一个新的基本块的入口语句。

1
2
3
4
5
6
7
8
9
10
11
12
13
(1) prod := 0
(2) i := 1
(3) t1 := 4 * i
(4) t2 := a [ t1 ]
(5) t3 := 4 * i
(6) t4 := b [ t3 ]
(7) t5 := t2 * t4
(8) t6 := prod + t5
(9) prod := t6
(10) t7 := i + 1
(11) i := t7
(12) if i <= 20 goto (3)
(13) …

根据规则，我们可以确定1，3，13为入口语句
所以可以划分的基本块为[1-2], [3-12], [13-]

3.3 流图构建

流图是有向图，其中：

流图示意
  • 结点是基本块。
  • 如果 B2 的执行紧跟在 B1 之后，则从 B1 到 B2 有一条有向边。
  • B1 称为 B2 的前驱，B2 称为 B1 的后继。

四、基本块内优化

4.1 代数性质利用

  • 编译时完成常量表达式计算
  • 整数类型与实型转换
  • 下标变量地址计算的部分工作可在编译时完成

4.2 运算强度削弱

用需要较少执行时间的运算代替另一种运算：

1
2
3
4
5
6
x ** 2 → x * x
3 * x → x + x + x
8 * x , 4 * x 等换成左移运算
x / 2 , x / 16 等换成右移运算
x := x + 1 变为INC x指令
x / 5 → x * 0.2 等

4.3 复写传播

对于x:=y这样的赋值语句，在该语句下面出现的x可用y来代替，满足条件时可删除复写语句。

1
x := y ; u := 2 * x ; v := x + 1 ;

4.4 删除冗余代码

删除毫无实际意义的代码，如：

  • x:=x+0
  • x:=x∗1
  • 永真或永假条件分支中的不可达代码

4.5 DAG图与公共子表达式消除

Directed Acyclic Graph图表示：

  • 图的叶结点由变量名或常量所标记，其中值得注意的是对于那些在基本块内先引用再赋值的变量，可以采用下标0 的方法来标注⚠️
  • 图的中间结点由中间代码的操作符所标记
  • 基本块中变量的最终计算结果都对应着图中的一个结点
    通过DAG图进行优化，易得需要两个算法：code in basic block -> DAG -> code after optimization

算法14.2构建DAG图消除公共子表达式：

alt text

  1. 建立结点表记录变量名/常量值与结点序号的对应关系
  2. 按规则建立DAG图，处理形如z=x op y的中间代码
    1. 对于操作数，有节点的记录序号，没有节点的建立叶子节点，序号为(i, j)
    2. 寻找中间节点（其中左i右j），找到了，记录序号k；没有找到，画个图，连接节点，序号为k
    3. 在表里找z，重新修改z的序号为k，或者建立一个表项(z, k)
  3. 通过DAG图识别和消除公共子表达式

数组、指针及函数调用的DAG图
数组：x = a[i]; a[j] = y; z = a[i]，能否认为 x = z？
不一定。若 j == i，中间那句把同一个元素改了，z 就不等于 x。在没有“j 与 i 一定不同”的证明时，要保守处理

将数组变量a作为一个单独的变量进行考虑，将形如x = a[i]的中间代码都表示为x = a [] i，其中[]为数组取值操作符；形如a[j] = y的中间代码都表示为a = j “[]=” y，其中“[]=”为数组成员赋值操作符。

alt text

4.7 窥孔优化

关注目标指令的短序列，通过删除冗余代码或用更高效代码替代来提升质量，不局限于同一基本块。

1
2
mov a b
mov b a
1
2
jump B
B: ...

五、全局优化

全局优化一定要知道某个数据（变量）什么时候定义的，在某个点是否存活，某个点被定义的值具体用在了什么地方

以上属于数据流分析，是全局优化的基础

5.1 数据流分析基础

数据流分析用于获取数据在程序执行路径中如何流动的信息，是全局优化的基础。程序执行过程是程序状态的变换过程。

5.2 到达定义分析（数据流最常用的分析）

如果从d出发，到p点之间再无其他定义，则称d到达p

如果路径上存在对该变量的其他赋值语句，那么路径上的前一个定义点就被路径上的后一个定义点“杀死”

数据流方程：out[S]=gen[S]∪(in[S]−kill[S])

其中：

  • out[S]：S末尾的数据流信息
  • gen[S]：S本身产生的数据流信息
  • in[S]：进入S时的数据流信息
  • kill[S]：S注销的数据流信息

对于基本块中的某一条中间代码：d1: u = v op w

  • gen[d1] = {d1}
  • kill[d1] = 在程序中对所有对u的其他定义
    对于基本块B的到达定义数据流方程:
    out[B]=gen[B]∪(in[B]−kill[B])
  • in[B]=∪B的前驱基本块P out[P]
  • kill[B]=kill[d1]∪kill[d2]∪…
  • gen[B] = gen[dn]∪
    (gen[d(n-1)] – kill[dn])∪
    (gen[d(n-2)] – kill[d(n-1)] – kill[dn])…∪
    (gen[d1] – kill[d2] – kill[d3]… – kill[dn])，倒序合并并剔除被后面杀死的

算法14.5基本块到达定义分析：

  1. 初始化所有基本块的out集合为空
  2. 根据方程循环计算in[B]和out[B]，直到不再变化

5.3 活跃变量分析（反方向沿着图路径的）

活跃变量分析可以用来分配寄存器

  • 如果变量x拥有寄存器，在之后不再活跃，则可以将该寄存器分配给其他变量使用
  • 如果两个变量的活跃区间不重叠，则可以分配同一个寄存器

了解变量在某个执行点是否活跃（值会被使用）。数据流方程：

  • in[B]=use[B]∪(out[B]−def[B])
  • out[B]=∪B的后继基本块P in[P]

其中：

  • def[B]：在B中被定义先于任何使用的变量集合
  • use[B]：在B中被使用先于任何定义的变量集合

算法14.4基本块活跃变量分析：

  1. 初始化所有基本块的in集合为空
  2. 根据方程循环计算out[B]和in[B]，直到不再变化

判断活跃变量的方法

  • 入口活跃性：变量x在基本块B的入口处活跃，当且仅当x ∈ in[B]

  • 出口活跃性：变量x在基本块B的出口处活跃，当且仅当x ∈ out[B]

  • 基本块内部活跃性：对于基本块内部的某个点，结合def和use信息判断。如果在某点之后有对变量的使用且之前没有重新定义，则该变量活跃；一旦变量被重新定义，其旧值就不再活跃

5.4 冲突图构建

冲突图中结点是待分配全局寄存器的变量，当两个变量中一个在另一个定义处活跃时，它们之间有边连接。用于寄存器分配优化。

5.5 定义-使用链和网

定义-使用链例图

定义-使用链：变量的定义点及所有可能使用该值的使用点组成的链

注意⚠️：不能按照数据流把所有有关b的变量使用都连上，因为b在基本块内被重新定义了，所以只能把基本块内从定义点出发到下一个定义点前的使用点连上

网的构造

网：同一变量的多个定义-使用链如果拥有共同使用点，则合并为同一个网。

  • 如果一个变量有两个网，则这个变量可当作两个不同的变量来处理，从而增加寄存器分配的灵活性。
  • 如果两个变量的网之间有交点，则交点是它们共同活跃的点。

六、循环优化

6.1 重要性

程序运行时间的80%由仅占源程序20%的循环部分执行，特别是多重循环的最内层。

6.2 循环不变式代码外提

将不随循环控制变量改变的表达式[不变表达式]，移到循环外部，减少计算次数（频度削弱）。

1
2
3
4
for (i=1; i<=n; i++) {
    t = a + b; // 不变表达式
    x[i] = t * i;
}

6.3 循环展开

循环展开

将循环体代码重复产生多次，以空间换时间。必须提前知道代码循环的次数。

判断准则：

  • 主存资源丰富，处理机时间昂贵
  • 循环体语句越少越有利

部分展开：折衷方法，如将步长改为3，每次循环执行3次循环体操作。

6.4 归纳变量

归纳变量：在每一次执行循环迭代的过程中，若某变量的值固定增加（或减少）一个常量值
即若当前执行循环的第 j 次迭代，归纳变量的值应为c * j + c’, 这里 c和 c’ 都是循环不变式

6.5 其他循环优化方法

  • 多重嵌套循环变成单层循环
  • n个相同形式循环合成一个循环
  • 过程，函数调用改为in_line展开

附件
可以用的活跃分析和到达定义分析代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
# 各基本块的 gen/kill/use/def 集（示例即你的那张图）
blocks = ["B1", "B2", "B3", "B4", "B5", "B6", "Bexit"]

gen = {
    "B1": {"d1", "d2"},
    "B2": set(),
    "B3": {"d3", "d4"},
    "B4": {"d5", "d6"},
    "B5": set(),
    "B6": {"d7", "d8"},
    "Bexit": set(),
}

kill = {
    "B1": {"d3", "d4", "d6", "d8"},
    "B2": set(),
    "B3": {"d1", "d2", "d6", "d8"},
    "B4": {"d2", "d4", "d7", "d8"},
    "B5": set(),
    "B6": {"d2","d4","d5", "d6"},
    "Bexit": set(),
}

# 控制流关系
succ = {
    "B1": ["B2"],
    "B2": ["B3", "B4"],
    "B3": ["B2"],
    "B4": ["B5"],
    "B5": ["B6", "Bexit"],
    "B6": ["B5"],
    "Bexit": []
}


def reaching_definitions(blocks, gen, kill, succ):
    # 逆向得到前驱关系
    pred = {b: [] for b in blocks}
    for b in blocks:
        for s in succ[b]:
            pred[s].append(b)

    in_sets = {b: set() for b in blocks}
    out_sets = {b: set() for b in blocks}

    changed = True
    iteration = 1
    while changed:
        print(f"\n===== 第 {iteration} 轮迭代 =====")
        changed = False
        for b in blocks:
            # in[B] = ⋃ 前驱的 out
            in_b = set().union(*(out_sets[p] for p in pred[b]))
            # out[B] = gen[B] ∪ (in[B] - kill[B])
            out_b = gen[b] | (in_b - kill[b])
            print(f"{b}: in={in_b}, out={out_b}")
            if in_b != in_sets[b] or out_b != out_sets[b]:
                changed = True
                in_sets[b], out_sets[b] = in_b, out_b
        iteration += 1
    return in_sets, out_sets


def live_variable_analysis(blocks, succ, use, define):
    # 反向：需要后继表
    in_sets = {b: set() for b in blocks}
    out_sets = {b: set() for b in blocks}

    changed = True
    iteration = 1
    while changed:
        print(f"\n===== 第 {iteration} 轮迭代 =====")
        changed = False
        for b in reversed(blocks):  # 从后往前
            # out[B] = ⋃ 后继的 in
            out_b = set().union(*(in_sets[s] for s in succ[b]))
            # in[B] = use[B] ∪ (out[B] - def[B])
            in_b = use[b] | (out_b - define[b])
            print(f"{b}: in={in_b}, out={out_b}")
            if in_b != in_sets[b] or out_b != out_sets[b]:
                changed = True
                in_sets[b], out_sets[b] = in_b, out_b
        iteration += 1
    return in_sets, out_sets


use = {
    "B1": set(),
    "B2": {"i"},
    "B3": {"a", "i"},
    "B4": {"a"},
    "B5": {"i"},
    "B6": {"b", "i"},
    "Bexit": set(),
}

define = {
    "B1": {"a", "i"},
    "B2": set(),
    "B3": set(),
    "B4": {"b", "i"},
    "B5": set(),
    "B6": set(),
    "Bexit": set(),
}


if __name__ == "__main__":
    print("=== 到达定义分析 ===")
    in_def, out_def = reaching_definitions(blocks, gen, kill, succ)

    print("\n=== 活跃变量分析 ===")
    in_live, out_live = live_variable_analysis(blocks, succ, use, define)