08-从 SSA 翻译指令

问题关键：翻译/消除$\phi$函数

• 以下方法均不可行：优化后变量间的依赖十分复杂，前一条语句计算出了新值，后一条语句仍然使用旧值，盲目变动后就会出现依赖问题

将$\phi$函数中的变量替换成同一个

• 不可行：预期的中间值可能会被覆盖

// 原始代码
a = x + y;
b = x + y;
a = 17;
c = x + y;

// ssa 优化后版本，此时再替换同名变量，`c`的赋值就会出现问题
a0 = x0 + y0;
b0 = a0;
a1 = 17;
c0 = a0;

将$\phi$函数替换为赋值语句

Lost-Copy Problem

• Critical Edge：起点有多条出边，终点有多条入边

// 原始代码
i = 1;
while (cond){
  y = i;
  i = i + 1;
}
z = y;

// ssa 优化后版本
i0 = 1;
while (cond){
  i1 = phi(i0, i2);
  i2 = i1 + 1;
}
z0 = i1;

// 改为赋值的版本
i0 = 1;
i1 = i0;
while (cond){
  i2 = i1 + 1;
  i1 = i2;
}
z0 = i1; // 此处 `z0` 赋值错误

解决方案

• 在ai完成计算后，增加块ai'=ai

• 把原始的$\phi$函数替换为a'=phi(a1’, a2’)

• 在$\phi$函数后增加新变量a=a'

• 把所有带'的变量替换成其他名称

• 通过加入赋值语句替换掉$\phi$函数

• 取出其余的冗余语句

// 解决步骤 1-3
i0 = 1;
i0` = i0;
while (cond){
  i1` = phi(i0`, i2`);
  i1 = i1`;
  i2 = i1 + 1;
  i2` = i2;
}
z0 = i1;

// 解决步骤 4-6
y1 = 1;
while (cond){
  i1 = y1;
  y1 = i1 + 1;
}
z0 = i1

Swap Problem

• $\phi$函数在汇合处通过数据流向确定最终值，位于赋值之前，和赋值语句的顺序无关

• 改成赋值语句后带来依赖错乱

// ssa
x0 = 1; y0 = 2;
do {
  x1 = φ(x0, y1);
  y1 = φ(y0, x1);
} while (…);
print(x1, y1);

// 改成赋值的ssa
x0 = 1; y0 = 2;
x1 = x0; y1 = y0;
do {
  x1 = y1;
  y1 = x1; // y1值错误
} while (…);
print(x1, y1);

解决方案

• 在ai完成计算后，增加块ai'=ai，在赋值的等号后面标记编号以显示同时性

• 把原始的$\phi$函数替换为a'=phi(a1’, a2’)

• 在$\phi$函数后增加新变量a=a'

• 把所有带'的变量替换成其他名称

• 通过加入赋值语句替换掉$\phi$函数

• 将并行的赋值序列化，找出存在变量交换的同组语句，使用中间变量替换

• 取出其余的冗余语句

// 解决步骤1-3
x0 = 1; y0 = 2;
x0` =1 x0; y0` =1 y0; // 等号后的数字相同，代表同时赋值 
do {
  x1` = φ(x0`, y1`);
  y1` = φ(y0`, x1`);
  x1 =3 x1`;
  y1 =3 y1`; 
  x1` =2 x1;
  y1` =2 y1; 
} while (…);
print(x1, y1);

// 解决步骤4-5
x0 = 1; y0 = 2;
a0 =1 x0; b0 =1 y0;
a1 =4 a0; b1 =4 b0;
do {
  x1 =3 a1;
  y1 =3 b1; 
  a1 =2 x1;
  b1 =2 y1; 
  a1 =5 b1;
  b1 =5 a1;
} while (…);
print(x1, y1);

// 解决步骤6
x0 = 1; y0 = 2;
a0 =1 x0; b0 =1 y0;
a1 =4 a0; b1 =4 b0;
do {
  x1 =3 a1;
  y1 =3 b1; 
  a1 =2 x1;
  b1 =2 y1;
  t =5 a1;  // 中间变量
  a1 =5 b1;
  b1 =5 t;
} while (…);
print(x1, y1);

// 解决步骤7
a1 = 1; b1 = 2;
do {
  x1 =3 a1;
  y1 =3 b1; 
  t =5 a1;  // 中间变量
  a1 =5 b1;
  b1 =5 t;
} while (…);
print(x1, y1);