静态单赋值(SSA)(只讲形式不讲实现)
定义
除了三地址代码
之外,静态单赋值(SSA)
是另一种表现形式。
区别在于:
- 所有的赋值都是针对不同名字的变量
用途
便于目标代码的优化。(先记住这个结果,至于怎么优化,可以参见《编译原理(第二版)》
举例
假设三地址代码
p = a + b
q = p - c
p = q * d
p = e - p
q = p + q
则静态单赋值形式如下
p1 = a + b
q1 = p1 - c
p2 = q1 * d
p3 = e - p2
q2 = p3 + q1
phi函数
假设C语言代码如下
if(flag){
x = -1;
}
else{
x = 1;
}
x
在不同分支中被定义。如果转换成三地址代码
,则x
会变成x1
和x2
if(flag){
x1 = -1;
}
else{
x2 = 1;
}
问题来了,请问最后究竟是用x1
还是x2
?
这完全是由程序运行时决定的,但是总会用到一个值,不是x1
就是x2
,那么根据三地址代码
的形式。
x3 = x1或者x2中的某一个值
这种方式在静态单赋值中用函数phi表示
x 3 = ϕ ( x 1 , x 2 ) x3 = \phi(x1,x2) x3=ϕ(x1,x2)
注意:Phi函数在编译器优化中很重要,先记住这个结论。