|
|
|
|
  这是我对SSA的理解，以及我实现的算法 - steven_known [ 2005-07-01 00:51 | 4,872 byte(s)]
Re: 这是我对SSA的理解，以及我实现的算法 - steven_known [ 2005-08-10 10:06 | 247 byte(s)]
Re: 这是我对SSA的理解，以及我实现的算法 - steven_known [ 2005-07-01 09:59 | 105 byte(s)]
Re: 这是我对SSA的理解，以及我实现的算法 - yjx_super [ 2005-07-08 08:53 | 51 byte(s)]
Re: 这是我对SSA的理解，以及我实现的算法 - Nemesis2k [ 2005-08-08 15:23 | 164 byte(s)]
|
|
|
|
[Original]
[Print]
[Top]
|
格式有一点乱，请拷贝到 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 |
|------------------|
|
|
|
----
我很大众
|
|
[Original]
[Print]
[Top]
|
|
[Original]
[Print]
[Top]
|
研究一下基于 SSA 的优化框架，把尽可能多的优化放在 ssa 形式中完成
应该比较有意义，这个可以参考 Open64 中的优化器。大家交流一下，我
也好学习一下：）
|
|
|
[Original]
[Print]
[Top]
|
|
[Original]
[Print]
[Top]
|
Open64的ssa是建立在 WHIRL 这种中间语言上，共分为5层，WHIRL在全局优化上使用了SSA这种数据流分析方式，我觉得其中比较重要的是对间接访存运算符的分析，即alias analysis,所以对于每一种中间
语言，ssa构建的复杂程度直接受之影响。
|
|
|
----
我很大众
|
|
[Original]
[Print]
[Top]
|
|
|
声明: 本页内容为中国Linux论坛的内容镜像，文章的版权以及其他所有的相关权利属于中国Linux论坛和相应文章的作者，如果转载，请注明文章来源及相关版权信息。