共有回帖数 0 个
-
偶尔会看到吧里有人在看编译原理时吐槽难以看懂或者枯燥无味，作为一个搞编译器的人，深感应该稍微普及下我大编译器神教。好吧，其实我就是在刷存在感而已，渣文，请随时吐槽。
总之这个帖子的初始目的是介绍下目前存在于各大编译器中的主流优化们，不过LZ我思维很发散，说不定写着写着就顺带手写写编译器架构和分析技术之类了。我个人觉得如果你不做编译器，你不太可能会直接面对这些问题，但是这些优化理论中的很多思想还是有益的。
好吧，其实LZ很拿不准有几个人对这种内容会有兴趣…………
LZ的大概计划是先介绍些中间端优化，然后是体系相关优化，如果有余力的话能介绍下代码生成阶段最好，前端什么的如果有人有兴趣的话，放最后说吧。讲优化的时候会中间穿插些控制流，数据流分析，依赖关系，别名分析的内容。当然如果真有那么一两个人感兴趣，并且对这个计划顺序有意见或者希望插入别的内容，LZ会尽量配合……
介绍中的绝大多数优化，分析等，LZ都亲手实现过，虽然可能分布在不同编译器和不同平台上……但是请不要找LZ要代码。LZ签了保密协议的，LZ不是做开源的，LZ要是传了代码可能就得卖房子了……
另外如无必要LZ不会涉及具体的实现算法，最多只会提及思想和思路，需知实现算法是和具体实现相关的，不同编译器不同体系不同IR不同优化遍都会导致不同，LZ我很懒，真心没力气去讨论那个
最后，其实LZ是半路出家的渣水平，LZ不是很懂专业名词，所以除了一些必须的专门词，LZ多半会使用口语来介绍，当然一些专门词我会以英文名为主，尽可能附上比较正式的中文译名或者我听说过的其他译名（参考龙鲸虎书，如果三书中有冲突以鲸书为准，别问LZ为什么）
最后的最后，渣水平渣中文，欢迎吐槽
No.1 常量传播 (Constant Propagation) & 复制传播 (Copy Propagation)
这是两个非常相似的优化，以致在一些书中被合并在一起，所以LZ就一起介绍了
【中心思想】
当有形如 u = v的赋值时，将之后使用u的地方都尽可能的用v来代替。
当v是常量的时候，一般称为Constant Propagation，当v是变量时，被称为Copy Propagation。
Note:
1. v不能是表达式，原因可以自己思考，或者等到讲另一个优化的时候再细说
2. 这个优化本身并不会带来改进，但是当所有使用u的地方都被v代替时，我们可以删除u = v的赋值，从而带来改进。
【详细】
首先我们来看最简单的形式，基本块内的传播
x = a;
y = x + c;
z = x + y;
对于上面这种简单形式，对于复制语句(x = a)，我们可以很简单的将之后所有使用x的地方都替换成a，于是优化后变成
x = a;
y = a + c;
z = a + y;
此时, x = a的赋值就没有了意义变成冗余语句可以删除。
然后是复杂形式，跨基本块的传播
if (z) {
x = a;
} else {
x = b;
}
y = x + 1;
在复杂形式中，由于复制语句和使用语句分处于不同的基本块中，这使得使用处的变量可能引用了不同的定义，例如上面的形式中，虽然x = a, x = b都是复制语句，且y = x +1中使用了x，但是很显然x的值可能来自于两这种任意一个，此时我们不能将y = x + 1中的x替换成a或b。所以这种情况下这个优化就不能做了。
因此对于跨基本块的传播，不仅需要找到复制语句u = v和之后使用u的语句，而且需要判断其定义来源是否形式一致(都是u = v)。在上面的例子中，如果else部分也是x = a，则这个优化是可以做的。
最后是小题目，下面的例子应该如何优化：
x = a;
y = b;
for (i = 0; i 10; i++) {
m = x;
y = y – 1;
}
先放一节吧，观望下
No.2 公共子表达式删除 (Common Sub-expression
Elimination)
在不涉及循环优化之前，这是一个相对较复杂的优化，但是这个优化本身与上面所讲的复制传播优化是相辅相成的，它们经常被先后的执行以提高优化的效果。
【中心思想】
CSE的目的是消除程序中重复的表达式计算。如果一个表达式E在某处出现之前已经被计算过，并且E中所有的变量值从那次计算到出现的某处之间都没有被改变。那么我们将表达式E称为一个公共子表达式。我们可以做一个显而易见的优化，即将那次计算时E的结果赋给一个变量x，然后在E出现的某处改为对x的引用。这样的优化就是CSE。
【详细】
老规矩，还是首先考虑最简单的形式，即基本块内的优化：
x = a + b +c; (1)
y = a + b +d; (2)
z = a + b +c; (3)
c = 1; (4)
m = a + b +c; (5)
上述的例子中：
对于语句(1)，实际有两个表达式被计算a + b和a + b + c;
对于语句(2)，也有两个表达式被计算a + b和a + b +d。显然，由于(2)处, ab的值都未改变，a+b计算是不必要的，此时表达式a+b是一个公共子表达式，我们可以优化使得(2)处的a+b不被计算而直接引用(1)中计算的值。
对于语句(3)，a + b + c也是一个公共子表达式。当然此处a+b也是公共子表达式，但是由于a+b也是a+b+c的子表达式，优化a+b+c显然比优化a+b更有利。
对于语句(4)，c的值被改变，a+b+c不再是公共子表达式，而a+b仍然是
对于语句(5)，a+b是公共子表达式
因此结果将优化成：
t1 = a + b;
t2 = t1 + c
x = t2; (1)
y = t1 + d; (2)
z = t2; (3)
c = 1; (4)
m = t1 + c;(5)
Note: 联系复制传播优化，CSE优化产生了很多的复制语句，这将进一步创造复制传播优化的机会
然后是跨块的情况，例如：
x = a + b +c;
if (z) {
y = a + b + c;
} else {
n = a + b + c;
a = 1;
z = a + b + c;
}
m = a + b +c;
跨基本块的情况通常比较复杂，它需要对程序构建典型的控制流和数据流分析，这里概要介绍下对于CSE优化的分析方法。将上面的程序分块如下：
这种把程序分块并计算其前驱后继块的分析方法就是基本的控制流分析。
然后我们定义另一种分析，对于每一个基本块B，它具有下列4种“函数”，数学公式我就不写了，直接口语吧：
GEN(B): 表示基本块B中被计算且直到基本块出口其值都不会改变的表达式的**
KILL(B): 表示基本块B中变量值被改变的表达式**
IN(B): 表示在基本块B入口处其结果仍然有效（即其变量没有改变）的表达式**。于是IN(B) = 所有B的前驱块的OUT的交集
OUT(B): 表示在基本块B出口处其结果仍然有效（即其变量没有改变）的表达式**。OUT（B）= IN(B) – KILL(B) + GEN(B)
根据这样的定义，我们可以分析每个基本块：
GEN(B1) = {a + b, a + b + c}
KILL(B1) = {}
IN(B1) = {}
OUT(B1) = {a + b, a + b + c}
GEN(B2) = {a + b, a + b + c}
KILL(B2) = {}
IN(B2) = {a + b, a + b + c }
OUT(B2) = {a + b, a + b + c}
GEN(B3) = {a + b, a + b + c}
KILL(B3) = {a + b, a + b + c}
IN(B3) = {a + b, a + b + c }
OUT(B3) = {a + b, a + b + c}
GEN(B4) = {a + b, a + b + c}
KILL(B4) = {}
IN(B4) = {a + b, a + b + c }
OUT(B4) = {a + b, a + b + c}
上面的分析则是一种数据流分析。根据这种数据流分析，我们可以得知在每个基本块出口入口处公共子表达式的信息，对于每个基本块我们可以逐句顺序的分析，按照前面所述的简单情况进行分析并得到块内的公共子表达式信息。
例如对于B3，由于IN(B3) = {a + b, a + b +c}，因此n = a + b +c可以直接使用之前计算的结果，此时a + b +c是可以优化的公共子表达式。
然后a = 1, a + b+ c和a+b的值都被改变，因此z = a + b + c中就不再是公共子表达式，而应作为一次计算。
按照这样的分析方法最后可以优化如下：
t1 = a + b +c;
x = t1;
if (z) {
y =t1;
} else {
n = t1;
a = 1;
t1 = a + b + c;
z = t1;
}
m = t1;
小题目，下面的形式会优化成怎样
x = a + b + c;
while (z) {
y = a + b + c;
a = 1;
}
m = a + b +c;
楼主 2015-11-19 13:38 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
