The nanpanjiang-project from hellollvm

[LLVM] Destruction of SSA

大家好，我是本科大三的学生，目前在做一个编译器的前后端的搭建项目。中间代码使用的是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过程以及其它的其中潜藏的问题，希望得到前辈们的指点！

LLVM系列培训+讨论班计划

暂定的一个LLVM系列培训+讨论班的大纲，如下：

1、LLVM IR与LLVM架构
2、LLVM的Pass体系
3、LLVM的指令选择
4、LLVM的指令调度
5、LLVM的寄存器分配
6、LLVM的tablegen
7、LLVM的优化
8、Clang和Clang tools

计划每节课程会包含2个小节的内容。

有没有什么偏好或者更具体地兴趣点？欢迎列出。

hellollvm / nanpanjiang-project Goto Github PK

nanpanjiang-project's People

Contributors

Stargazers

Watchers

Forkers

nanpanjiang-project's Issues

[LLVM] Destruction of SSA

南盘江第一期许愿池计划

LLVM系列培训+讨论班计划

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent