admin管理员组文章数量:1666615
本文只是个随笔,记录一下看源码的思维过程,免得忘了。可能有很多废话,hhhh
相信对于熟悉LLVM的SSA以及了解支配概念的读者来说,应该都不陌生了,这个pass无非就是将LLVM最“原汁原味”的IR转化为SSA形式的IR。首先从形式上,就简明了不少,另外,SSA形式还有特殊的用处。
如果你还不太了解SSA的话,不妨上网搜搜,先大概了解下SSA的好处。
这篇文章不打算谈SSA的好处,也不会从头开始谈SSA在LLVM是如何建立的。网上有很多关于LLVM中mem2reg是如何建立SSA的。包括知乎的R大,还有“电影旅行大哥”,都有非常好的解答。本文主要从LLVM源码的角度,更详细的介绍LLVM是如何通过mem2reg来建立SSA的。
这里先给几个大神的解答,请大家看完之后,再继续阅读本文。
1、对于LLVM之类的编译器是如何实现在构造 SSA 形式的 IR 的时候,计算出 def-use 链?
2、调试LLVM如何生成SSA
3、mem2reg
其实上面第二篇文章已经有了部分源码的解释了。所以下面在讲解相对应部分的时候,就不会花太多笔墨去解释了。
mem2reg整体流程
我们直接来看下R大转发的对mem2reg整体流程的介绍,这里我对其翻译一下,这里就不放英文介绍了:
- LLVM假设程序中所有的局部变量都在栈上,并且通过Alloca指令在函数的Entry BB进行声明,并且只出现在Entry BB里。但不同的前端可能会有特殊情况,但是就我的机器而言,基本都是这样的。所以我们暂时接受这个假设。
- 对步骤1中声明的每个ALLOC指令,LLVM都会检查它是否promotable(这个词还没想好怎么翻译,翻译成“提升”?感觉怪怪的,所以暂时不翻译吧,大概意思就是是否可以转化成SSA形式,从而删掉这个Alloca)。如果满足下面的2个条件,就是可promotable:
- 这个ALLOC出来的临时变量不在任何volatile指定中使用
- 这个变量是直接通过LOAD或者STORE进行访问的,比如,不会被取址。
- 对于步骤2中选出来的可promotable的那些局部变量,扫描一次当前函数,看下哪些基本块在使用这些ALLOC,哪些基本块定义了这个ALLOC(这里的使用是指LOAD,定义是通过STORE语句)
- 在这个过程中,可以执行一些基本的优化,比如:
- 未使用的ALLOC变量,比如声明或定义的但没使用变量
- 如果只有一个定义基本块(只有一个STORE语句,且只存在一个基本块中),那么被这个定义基本块所支配的所有LOAD都要被替换为STORE语句中的那个右值。
- 如果某个ALLOC出来的局部变量的读或者写都只存在一个基本块中,那么我们就没必要去遍历所有的CFG的,因为这个store语句支配了这些LOAD,所以可以用STORE的右值直接替换使用LOAD指令的那些值。说起来很拗口,后面会用代码说明,别急。
- 构建支配者树。
- 利用支配信息,来插入PHI节点,具体做法是:
- 对于每一个经过上述步骤筛选后的ALLOC临时变量,找到一组基本块,这些基本块只使用了这个临时变量,而没有定义它,这组基本块也可能不存在。
- 通过一种线性时间复杂度的算法来求得PHI节点的插入点。给自己埋个坑,后续会出一篇文章详细讲讲这个算法。
- 将PHI节点插入到上一步找到的那些插入点,且插在这些BB的开头。
- 一旦所有的PHI节点都插入到位后,就开始重命名PASS。(这一步的相关步骤还需要看源码再进行翻译)
先看一个小例子
我们先来看下LLVM前端生成的原始IR和mem2reg后的IR是咋样的,然后我们看看汇编是咋样的。
// 这是一段简单的demo C源码
int fun(){
int x = 5, y =10;
int b;
if(x > y + 1) {
b = 10;
}else
b = 5;
int c = b;
c++;
return c;
}
通过下面指令后:
clang -S -c -Xclang -disable-O0-optnone -fno-discard-value-names -emit-llvm xxx.c -o xxx.ll
生成了最简单、最原始IR:
; Function Attrs: noinline nounwind uwtable
define dso_local i32 @fun() #0 {
entry:
%x = alloca i32, align 4
%y = alloca i32, align 4
%b = alloca i32, align 4
%c = alloca i32, align 4
store i32 5, i32* %x, align 4
store i32 10, i32* %y, align 4
%0 = load i32, i32* %x, align 4
%1 = load i32, i32* %y, align 4
%add = add nsw i32 %1, 1
%cmp = icmp sgt i32 %0, %add
br i1 %cmp, label %if.then, label %if.else
if.then: ; preds = %entry
store i32 10, i32* %b, align 4
br label %if.end
if.else: ; preds = %entry
store i32 5, i32* %b, align 4
br label %if.end
if.end: ; preds = %if.else, %if.then
%2 = load i32, i32* %b, align 4
store i32 %2, i32* %c, align 4
%3 = load i32, i32* %c, align 4
%inc = add nsw i32 %3, 1
store i32 %inc, i32* %c, align 4
%4 = load i32, i32* %c, align 4
ret i32 %4
}
这里就可以看到LLVM的那个假设,即声明了很多栈上的ALLOCA临时变量。
然后我们通过opt指令生成mem2reg:
opt -mem2reg xxx.ll -o xxx_opt.ll
# 下面这个llvm-dis是把opt生成的非人类可读的文件转化为人类可读的文
llvm-dis xxx_opt.ll -o xxx_opt_dis.ll
# xxx_opt_dis.ll
; Function Attrs: noinline nounwind uwtable
define dso_local i32 @fun() #0 {
entry:
%add = add nsw i32 10, 1
%cmp = icmp sgt i32 5, %add
br i1 %cmp, label %if.then, label %if.else
if.then: ; preds = %entry
br label %if.end
if.else: ; preds = %entry
br label %if.end
if.end: ; preds = %if.else, %if.then
%b.0 = phi i32 [ 10, %if.then ], [ 5, %if.else ]
%inc = add nsw i32 %b.0, 1
ret i32 %inc
}
这一下就清凉了好多。可以看到,在最后一个BB的开头,有一个PHI节点。接下来我们看看汇编长啥样:
00000000004004b0 <fun>:
4004b0: 55 push %rbp
4004b1: 48 89 e5 mov %rsp,%rbp
4004b4: b8 01 00 00 00 mov $0x1,%eax
4004b9: 83 c0 0a add $0xa,%eax
4004bc: b9 05 00 00 00 mov $0x5,%ecx
4004c1: 39 c1 cmp %eax,%ecx
4004c3: 0f 8e 0d 00 00 00 jle 4004d6 <fun+0x26>
4004c9: b8 0a 00 00 00 mov $0xa,%eax
4004ce: 89 45 fc mov %eax,-0x4(%rbp)
4004d1: e9 0d 00 00 00 jmpq 4004e3 <fun+0x33> <---
4004d6: b8 05 00 00 00 mov $0x5,%eax
4004db: 89 45 fc mov %eax,-0x4(%rbp)
4004de: e9 00 00 00 00 jmpq 4004e3 <fun+0x33> <---
4004e3: 8b 45 fc mov -0x4(%rbp),%eax <---
4004e6: 83 c0 01 add $0x1,%eax
4004e9: 5d pop %rbp
4004ea: c3 retq
4004eb: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
注意一下3个箭头指向的那三个语句,我们后面会再来详细解释一下PHI节点是如何转化成我们真正能运行的代码的,因为指令集里面是没有针对PHI节点的指令的。
LLVM mem2reg源码之旅
从这里开始,我们开始介绍LLVM的关于mem2reg的源码。并且,我们会将源码进行拆分,使其与我们之前提到的整体流程中的步骤对应起来。LLVM的版本是最新的12.0。LLVM中mem2reg的注释非常多,也非常精准,所以如果有原生注释,我们就不解释了。并且我的注释会直接在代码上,方便对应起来。
mem2reg的路径在:/llvm/lib/Transforms/Utils/mem2reg.cpp
struct PromoteLegacyPass : public FunctionPass {
// Pass identification, replacement for typeid
static char ID;
PromoteLegacyPass() : FunctionPass(ID) {
initializePromoteLegacyPassPass(*PassRegistry::getPassRegistry());
}
// runOnFunction - To run this pass, first we calculate the alloca
// instructions that are safe for promotion, then we promote each one.
bool runOnFunction(Function &F) override {
if (skipFunction(F))
return false;
DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
AssumptionCache &AC =
getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
return promoteMemoryToRegister(F, DT, AC);
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<AssumptionCacheTracker>();
AU.addRequired<DominatorTreeWrapperPass>();
AU.setPreservesCFG();
}
};
我们可以看到,mem2reg其实是一个函数的PASS,即它的处理单元是函数级的,并且使用到了支配树的PASS。
在runOnFunction函数中,首先有一个判断,如果该函数开了不优化的选项,那么就会直接跳过。即mem2reg只优化那些没有打开“不优化”选项的函数。
promoteMemoryToRegister函数是mem2reg的入口函数。
static bool promoteMemoryToRegister(Fun
版权声明:本文标题:源码解读---mem2reg源码(1) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1730075344a1221703.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论