参考wiki: blog: http://blog.llvm.org/2009/12/advanced-topics-in-redundant-load.html
静态单次赋值:
相对于编译器中对一个变量进行多次赋值, 有一个<等价>的形式就是一切变量都只被赋值一次. 这种等价性使得事情变的简单了.
a = 1;
b=a;
a = 2;
c = a;
在ssa中转化为这样:
a1=1;
b1 =a1;
a2=2;
c1 =a2;
这样做首先不会让事情变糟糕, 因为每一次赋值都等于销毁了前一次的赋值,
所以对于a来说, 经过了a=2这个"涅槃"之后, 前面的值就没有意义了, 甚至可以等价于<没有>
因此, 对于每一次赋值, 等价于创造了新的事物, 而隐含的意义就是之前的某些事物可能没有了,
但是不管有没有, 都没关系, ssa的意义就在于消除了'update'这种语义.只有产生和消亡,没有改变.
这些理论在基本块内是完美的.
但是对于控制流(这里是基本块外面的世界了)if (...) {
*A = 5;
P = A;
} else {
*B = 9;
P = B;
}
use(*P);
在最后活着的P到底是谁?
在基本块之间是不讲SSA的, 进入了基本块之后才SSA.
对于优化来说, 数据依赖是分析的一个途径, 基本块之间的数据依赖有一种方法叫"PHI翻译".
LLVM的"虚拟指令集"中有一条指令叫phi.
它就像是热水器下面把冷水和热水管道合并成一路的那个东西, 也可以看成是马氏管, 或者垃圾道 (或者mux?)
特点就是从这玩意出来的东西可能有不同的内容.
if语句的两个基本块(Basic Block)分别叫做BB1和BB2,
%P = phi i32* [%A, %BB1], [%B, %BB2]
表示P有可能是从BB1来的A,或者BB2来的B
支配(dominate)如果说A支配B, 那么表示如果要得到B, 必须先有A, 比如说父亲和母亲支配儿子.这样, 我们如果得到了B, 我们知道A已经有了. 代码执行到B,说明已经执行过A了.
A => B
dominance frontier 可以理解为'支配域'吧. B处于A的支配域, 表示到达B即可以经过A, 又可以不经过A.
B哥给出形象的解释:
热水管的支配域包括了莲蓬头, 冷水管的支配域也包括了莲蓬头, 不过莲蓬头到底出什么水, 绝对不是光热水管说了算, 也不是光冷水管说了算. 对于代码来说可以限制同时只能开一种水, 要不就烫死猪, 要不就冰冰浴.
如果BB1的支配域包括了P, 那么P的PHI函数中就包括了一项对应BB1, 很多人的支配域都包括了P,那么自然P的PHI函数中就包括了一堆项.
PHI就解决了基本块之间依赖性的描述问题, 各种基于PHI变换的优化应运而生...
在百花齐放, 百家争鸣的改革开放大潮下, 伊利诺伊大学开发了LLVM这个伟大的项目, 北欧的共产主义革命家也开发了GHC编译器, 就连修正主义的沙俄也有地下党发布了nginx, 这标志这共产主义事业一定会让我奋斗终生.
----
GCC的GIMPLE也是一种比较通用的中间语言, 比LLVM的IR要大, 也有SSA和PHI的各种概念.
阅读(1484) | 评论(0) | 转发(0) |
