LLVM Liveness Analysis
基于 llvm 实现活跃变量分析
活跃变量分析
活跃变量分析是最典型的数据流分析的算法之一,它的作用是确定变量在程序中的活跃性。
变量在某个程序点有两种状态,live
或 dead
。对于变量 x 和程序点 p,判断 x 在点 p 上的值是否会在 CFG 中的某条从点 p 出发的路径中使用。如果是,就说 x 在 p 上 live
;否则就说x在p上是 dead
。
活跃变量分析主要作用
- 寄存器分配
- 死代码删除
活跃变量计算算法
实现思路
整体思路
- 单独计算每个基本块的 $use_B$ 与 $def_B$ 集合 (是否可以先把基本块转为DAG形式?)
- 后序遍历分析函数的基本块,对每个基本块应用 TransferFunction
- 一直迭代,直到 IN 集合不再改变
细节思路
- 集合运算采用 llvm::BitVector 加速分析
- $OUT[B] - def_B$ 位运算等价于 $OUT[B] \And Not(def_B)$
测试样例程序
1 |
|
只分析 sum 函数
1 |
|
映射 BitVec 与定值的关系
1 |
|
输出样本如下
1 |
|
测试样例一共有 19 个定值,每一个定值对应 BitVector 中的一个二进制位。
use 与 def 的计算
有一种特殊情况,需要考虑,例如某个基本块如下
1 |
|
use = {c}, def = {a, b, d}
因为 a
的定值在当前基本块内且在引用之前,所以 use 集合中没有 a
在 llvm 分析中,分析基本块 def 的时候应该去掉有“定值”作用的指令,例如 BranchInst
, StoreInst
, ReturnInst
等….
分析 use 的时候,应该去掉对 BranchInst
,Contant
等…
1 |
|
测试样例某基本块输出如下:
1 |
|
该基本块生成有 3个定值,引用外部两个定值 %test2
和 %5
均不在该基本块,因此属于 use 集合。
Entry 基本块的 use 集合只有参数,因为对于 Entry 来说,参数是外部的。
1 |
|
迭代计算活跃性
迭代计算,直到所有基本块的IN集合不再改变。
1 |
|
数据样例
第一次迭代16基本块:
1 |
|
第二次迭代16基本块
1 |
|
第三次迭代16基本块
1 |
|
集合不再发生变化.
最终所有全局活跃变量的并集
1 |
|
这给死代码删除提供了一个思路,如果某一个变量全局不活跃,并且在基本块内无引用,则为死代码可以删掉。
完整代码
1 |
|
调用代码
1 |
|
参考
[1] https://www.bilibili.com/video/BV19741197zA?t=2059 “南京大学《软件分析》课程04(Data Flow Analysis II)”
[2] https://panda0s.top/2021/02/20/Register-Allocation/ “Register Allocation”
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!