ZT 这是我对SSA的理解，以及我实现的算法

prolj

原文http://www.linuxforum.net/forum/ ... sb=&o=&vc=1

格式有一点乱，请拷贝到 vi 或记事本中观看，设置tab键为8

Strictly Dominate:
node x dominates node w and x!=w

Dominance Frontier:
node x dominate node w 的某一个前驱， 但 x 不满足 strictly dominates w 的条件
则 w 属于 x 的 Dominance Frontier集合。

Dominance Frontier Criterion:
如果在 node x 中对变量 a进行了定义 , 则要在 node x 的DF集合中的所有 node 中插入 a 的 phi-function

//BB 表示 Basic Block , BB_SET 表示由BB组成的集合
//该函数为CFG中的每一个BB生成DF
//假设参数 dom_x 表示 x 的 Dominate BB Set ,之前已经计算好
//假设 CFG 的 Dominate Tree 已经构建
BB_SET Get_DF(BB x , BB_SET dom_x)
{
BB_SET df_x; // df_x 表示 x Dominance Frontier Set
BB d,m;
FOR_ALL_BB_IN_DOM(x,d) //所有被 x 支配(dominate)的 BB
{
FOR_ALL_SUCC(d,m)// d 的所有后继节点 m
{
if( BB_SET_Member(dom_x,m) && // m 不被 x dominate.
x!=m )
{
continue; // m 不属于 x 的 Dominance Frontier
}
else
{
BB_SET_Union(df_x,m); // m 属于 x 的 Dominance Frontier
}
}

}
return df_x;
}

Example:

Original CFG:

|-------|0
| ENTER |
|-------|
|
V
|--------|1
| k <- 0 |
| i <- 1 |
| j <- 2 |
|--------|
|
-----------------| |
| V V
| |--------|2
| | i <= N?|
| |--------|
| / \
| / \
| / \
| V V
| |---------|3 |-----------|4
| | k <- 1 | | k > 0 ? |
| | i <- i+1| |-----------|
| |---------| / \
| | / \
| | V V
|------| |---------|5 |-----------|6
| i <- 0 | | i<- i+1 |
|---------| |-----------|
\ /
\ /
V V
|-----------|7
| EXIT |
|-----------|


Dominator tree:


0
|
1
|
2
/ \
3 4
/|\
/ | \
5 6 7


Dominance Frontier:

n DF(n)
0 {}
1 {}
2 {2}
3 {2}
4 {}
5 {7}
6 {7}
7 {}


SSA Form:
|-------|0
| ENTER |
|-------|
|
V
|---------|1
| k1 <- 0 |
| i1 <- 1 |
| j1 <- 2 |
|---------|
|
-----------------| |
| V V
| |------------------|2
| | k2 <- phi(k3,k1) |
| | i2 <- phi(i3,i1) |
| | i2 <= N? |
| |------------------|
| / \
| / \
| / \
| V V
| |-----------|3 |-----------|4
| | k3 <- 1 | | k2 > 0 ? |
| | i3 <- i2+1| |-----------|
| |-----------| / \
| | / \
| | V V
|------| |----------|5 |-------------|6
| i4 <- 0 | | i5<- i2+1 |
|----------| |-------------|
\ /
\ /
V V
|------------------|7
| i6 <- phi(i4,i5) |
| EXIT |
|------------------|

[ 本帖最后由 prolj 于 2007-9-27 22:45 编辑 ]