[LLVM] Destruction of SSA

[NK-MXD]

大家好，我是本科大三的学生，目前在做一个编译器的前后端的搭建项目。中间代码使用的是LLVM语言，后端对应的是armv7平台。在中间代码优化方面我遇到一个问题：

目前我已经实现了mem2reg算法，将phi指令插入到了合适的位置，但是在消除phi指令的过程中遇到了一些困难，例如如下程序片段：

int fun(int m,int n){
	int rem;			
	while(n > 0){
		rem = m % n;
		m = n;
		n = rem;
	}
        return m;
}

使用mem2reg算法插入phi指令之后，得到的程序片段如下（进行了简单的循环优化，但还未进行其它优化）：

define i32 @fun(i32 %t0, i32 %t2) {
B28:
  br label %B32
B32:                               	; preds = %B28
  %t6 = icmp sgt i32 %t2, 0
  br i1 %t6, label %B33, label %B37
B33:                               	; preds = %B32, %B33
  %t60 = phi i32[ 0 , %B32 ], [ %t10 , %B33 ]
  %t48 = phi i32[ %t0 , %B32 ], [ %t54 , %B33 ]
  %t54 = phi i32[ %t2 , %B32 ], [ %t10 , %B33 ]
  %t10 = srem i32 %t48, %t54
  %t39 = icmp sgt i32 %t10, 0
  br i1 %t39, label %B33, label %B42
B37:                               	; preds = %B32
  br label %B34
B42:                               	; preds = %B33
  br label %B34
B34:                               	; preds = %B37, %B42
  %t61 = phi i32[ 0 , %B37 ], [ %t10 , %B42 ]
  %t55 = phi i32[ %t2 , %B37 ], [ %t10 , %B42 ]
  %t49 = phi i32[ %t0 , %B37 ], [ %t54 , %B42 ]
  ret i32 %t49
}

为了消除phi指令，我采用了一种非常朴素的办法：

1. 将有依赖关系的phi指令（例如%t48与%t54）中先计算的提到前面（将%t48提到前面）
2. 将phi指令转变为add指令依次插入前驱块当中

得到的结果如下所示：

define i32 @fun(i32 %t0, i32 %t2) {
B28:
  br label %B32
B32:                               	; preds = %B28
  %t60 = add i32 0, 0
  %t48 = add i32 %t0, 0
  %t54 = add i32 %t2, 0
  %t6 = icmp sgt i32 %t2, 0
  br i1 %t6, label %B33, label %B37
B33:                               	; preds = %B32, %B33
  %t10 = srem i32 %t48, %t54
  %t60 = add i32 %t10, 0
  %t48 = add i32 %t54, 0
  %t54 = add i32 %t10, 0
  %t39 = icmp sgt i32 %t10, 0
  br i1 %t39, label %B33, label %B42
B37:                               	; preds = %B32
  %t61 = add i32 0, 0
  %t55 = add i32 %t2, 0
  %t49 = add i32 %t0, 0
  br label %B34
B42:                               	; preds = %B33
  %t61 = add i32 %t10, 0
  %t55 = add i32 %t10, 0
  %t49 = add i32 %t54, 0
  br label %B34
B34:                               	; preds = %B37, %B42
  ret i32 %t49
}

但是这样做有一个问题，就是在B33块中每次在结尾得到的%t54，%t48等都是下一次循环的起始值，使得之后使用到%t54，%t48进行计算的结果都发生了错误（例如%t49），我很困惑如何在现有的循环结构的基础上解决这个问题。

另外，自己也调研过llvm当中的phi指令的消除，包括关键边，赋值丢失等问题，但是还是没有很清楚SSA的Destruction过程以及其它的其中潜藏的问题，希望得到前辈们的指点！

[NK-MXD]

上面提到的代码部分问题已经解决了，🤐很抱歉我对于phi指令的消除还没有足够的认识，上面的情况已经属于了关键边的处理，对应的处理方式有两种：1. 插入一个新块（我已经实现了）2. 加入临时变量（保证赋值不丢失，还未实现）

define i32 @fun(i32 %t0, i32 %t2) {
B28:
  br label %B32
B32:                               	; preds = %B28
  %t60 = add i32 0, 0
  %t48 = add i32 %t0, 0
  %t54 = add i32 %t2, 0
  %t6 = icmp sgt i32 %t2, 0
  br i1 %t6, label %B33, label %B37
B33:                               	; preds = %B32, %B70
  %t10 = srem i32 %t48, %t54
  %t39 = icmp sgt i32 %t10, 0
  br i1 %t39, label %B70, label %B42
B37:                               	; preds = %B32
  %t61 = add i32 0, 0
  %t55 = add i32 %t2, 0
  %t49 = add i32 %t0, 0
  br label %B34
B42:                               	; preds = %B33
  %t61 = add i32 %t10, 0
  %t55 = add i32 %t10, 0
  %t49 = add i32 %t54, 0
  br label %B34
B34:                               	; preds = %B37, %B42
  ret i32 %t49
B70:
  %t60 = add i32 %t10, 0
  %t48 = add i32 %t54, 0
  %t54 = add i32 %t10, 0
  br label %B33
}

而且我还发现我这种处理思路对于循环赋值来说是不适用的，还需要加入临时变量。

另外我注意到TSSA和CSSA等概念，感觉这样的处理方式更加系统优美，想请教一下使用TSSA转化为CSSA的思路进行phi指令的消除。