代码优化应该处在编译的什么位置？
可以在语义分析之前吗？
假如我们有这样的代码：
if (1) {
...
} else {
printf(2);
}
我们经过语义分析后，得到一棵抽象语法树，然后进入中间表示阶段：
等价于停机问题(判断一个程序是否能在有限时间内结束运行的问题)：
给定程序p，把 Opt§ 和下面的程序比较：
L:
jmp L
如果能将 一个程序 优化成上述程序，那么该程序就是无终止的
而我们总能加入优化让编译程序更好，所以不存在“完全优化”
这称为”编译器从业者永不失业定理“
下面将介绍：
注：常量折叠也可以在中间端和后端来做，但是在前端来做有其优势。
算法
// 语法制导的常量折叠算法
// 在语法树上
const_fold(Exp_t e)
while (e is still shrinking) // 找不动点
switch (e -> kind)
case EXP_ADD:
Exp_t l = e->left;
Exp_t r = e->right;
if (l->kind == EXP_NUM && r->kind == EXP_NUM) // 都是常量
e = Exp_Num_new (l->value + r->value); // 表达式优化成常量
break;
default:
break;
常量折叠优化小结
// 代数化简的算法
alg_simp(Exp_t e)
while (e is still shrinking)
switch (e->kind)
case EXP_ADD:
EXP_t l = e->left;
Exp_t r = e->right;
if (l->kind == EXP_NUM && l->value==0)
e=r;
break;
case ...: ...; // 类似
基本思想：
静态移除程序中不可执行的代码
示例：
if (false)
s1;
else s2; ==> s2;
在控制流图上也可以进行这些优化，但在早期做这些优化可以简化中后端
// 不可达代码删除算法
deadcode (Stm_t s)
while (s is still shrinking)
switch (s->kind)
case STM_IF:
Exp_t e = s->condition;
if (e->kind == EXP_FALSE)
s = s->else;
break;
case ...: ...; // 类似
算法如下：
// 常量传播算法
const_prop(Prog_t P)
// 第一步：程序分析
reaching_definition (p);
// 第二步：程序改写
foreach (stm s in p: y = x1, ..., xn)
foreach (use of xi in s)
if (the reaching def of xi is unique: xi = n)
y = x1, ..., xi-1, n, xi+1, ..., xn
示例：
1: x = 1;
2: y = 2; {1}
3: z = x + y; {1, 2}
4: a = z + 5; {1, 2, 3}
5: print(a); {1, 2, 3, 4}
我们发现在3可以做常量传播优化：
1: x = 1;
2: y = 2; {1}
3: z = 1 + 2; {1, 2}
4: a = z + 5; {1, 2, 3}
5: print(a); {1, 2, 3, 4}
我们发现在3接着可以做常量折叠优化：
1: x = 1;
2: y = 2; {1}
3: z = 3; {1, 2}
4: a = z + 5; {1, 2, 3}
5: print(a); {1, 2, 3, 4}
我们发现在4可以做常量传播优化：
1: x = 1;
2: y = 2; {1}
3: z = 3; {1, 2}
4: a = 3 + 5; {1, 2, 3}
5: print(a); {1, 2, 3, 4}
我们发现在4接着可以做常量折叠优化：
1: x = 1;
2: y = 2; {1}
3: z = 3; {1, 2}
4: a = 8; {1, 2, 3}
5: print(a); {1, 2, 3, 4}
最后在5做常量传播优化：
1: x = 1;
2: y = 2; {1}
3: z = 3; {1, 2}
4: a = 8; {1, 2, 3}
5: print(8); {1, 2, 3, 4}
算法如下：
// 拷贝传播算法
copy_prop(Prog_t p)
// 第一步：程序分析
reaching_definition(p);
// 第二步：程序改写
foreach(stms s in p: y = x1, ..., xn)
foreach(use of xi in s)
if (the reaching def of xi is unique: xi = z)
y = x1, ..., xi-1, z, xi+1, ..., xn
算法如下：
// 死代码删除算法
dead_code(Prog_t p)
// 第一步：程序分析
liveness_analysis(p);
// 第二步：程序改写
foreach(stm s in p: y = ...)
if (y is NOT in live_out[s])
remove(s);
我们先给出一些定义：
四元式等价
设（w1，A1，B1，t1）和（w2，A2，B2，t2）是非赋值型运算类四元式。
若 w1 = w2，并且 A1 和 Ａ2，B1 和 Ｂ2 的值彼此相等，则称这两个四元式等价。
公共子表达式优化
如果在基本块中出现多个等价的四元式，则除了第一个外其它的等价的四元式，称为第一个四元式的公共子表达式
然而，公共子表达式的关健在是判断两个分量的值是否相等。
我们这里只介绍值编码的方式来帮助我们解决该问题。
基本思想：对于中间代码中出现的每个分量，确定一个值编码，使得具有相同值编码的分量等价。
示例：
优化前：
t = b * c
c = b * c + b * c
d = b * c + d
优化后：
t = b * c
c = t + t
d = b * c + d
我们用V（x）来代表变量x的值编码，对于值编码的分配，是全局递增，首次产生1，其次2……
会用到三张表：
值编码表：ValuNum，存放变量（或常数）及其值编码
可用表达式代码表UsableExpr，存放基本块中的可用于匹配的表达式编码四元式（四元式中的变量用其编码替换）
临时变量等价表PAIR，存放等价的临时变量偶对。如（ti，tj）是等价的，需要用ti 替换 tj
示例
a = b * c + b * c;
d = b;
e = d * c + b * c;
过程如下：
循环不变式：如果一个表达式E在一个循环中不改变其值，则称它为该循环的不变表达式。
循环不变式外提优化
for (int i = 1; i <= 1000; ++ i) {
a *= x * y;
}
我们做如下优化：
int t = x * y;
for (int i = 1; i <= 1000; ++ i) {
a *= t;
}
这样减少了1000次运算
循环不变式的关键
安全性：不可外提类
除法表达式不可外提（除0溢出）
while E do
if y == 0
then x = y;
else
x = a / y
假如 a / y 是循环不变式，我们外提，又恰好 y = 0，这个时候就会出问题了
赋值表达式不能外提（即使赋值表达式的左部和右部都是循环不变式）
外提策略：
循环不变式外提算法
示例1
我们显然可以及那个 2 * k + 2 * k * 2 外提，对应到中间代码中的三条语句外提
示例2
后端优化的特点
后端优化的几种典型方法
寄存器分配是现代编译器中最普遍，最重要的优化
寄存器分配的示例
有三个变量 a，b，c；假设目标机器上只有2个物理寄存器：r1，r2
1: a = 1;
2: b = a + 2;
3: c = b + 3;
4: c = a + 3;
5: return c + a;
和上一章类似，我们做活性分析
寄存器分配后的代码：
1: r1 = 1;
2: r2 = r1 + 2;
3: r2 = r2 + 3;
4: r2 = r1 + 3;
5: return r2 + r1;
但是，很可惜的是，最优寄存器分配是一个NPC问题，在几乎任何假设下，都没有多项式时间，所以下面将介绍的是启发式算法
还记得上一章的一般性后向数据流方程吗：
自底向上轻松的算出out 和 in
我们根据上面活性分析的结果，画出下面的RIG
示例
这样源程序可以改写为：
问题是：如何计算图着色？
这个问题有点难
图着色的启发式算法
观察
算法步骤
示例
思考：启发式算法如果失败了怎么办？
答案：直接将变量分配到内存
如果所有节点都有大于等于k个邻居，怎么办?
例如 k = 3时，我们删除掉 a 之后就卡住了
仍以上图为例，我们假设选择 f 溢出
然后，剩下的这个图是 3-可着色的
然后我们栈弹出元素着色的时候，如果遇到前面溢出的f
两种做法：
这样我们寄存器分配后，得到的代码：
我们重新进行下活性分析：
尝试画出 RIG
溢出缩减了f的活跃区间！！！，从而减少了RIG中的邻居数量(f仅在load后或store前活跃)
但其实又带来了新的问题：溢出哪些变量最好？
因篇幅问题不能全部显示，请点此查看更多更全内容