过程间和过程内的数据流分析算法在类似LLVM的IR或HotSpot C1的HIR中,是如何实现的?

我自己为了学习的目的,实现了一个类C语言的编译器,想把数据流分析算法应用进去,迄今未知,一直非常的困惑是经典的数据流分析算法如何在类似LLVM的IR和HotSpot的HIR中实现(因为我自己实现的编译器参考了它们两者的特点)。 -------------------------------------------------------------------------------------------------------------- 我看LLVM的源代码没找到对应实现,如果能说出哪个文件就非常好了,谢谢! HotSpot…
关注者
94
被浏览
1792
咦题主把之前的问题删掉了么…我还打算回答之前那个呢。
呃原来之前那个不是题主问的。我把这篇答案联动到之前的问题了:新版的龙书和鲸书上讲了很多数据流分析的理论,LLVM中有对应的实现吗? - RednaxelaFX 的回答

Z大 @zephyr z 的回答对LLVM的讲解到位。正是因为SSA形式贯穿于LLVM IR,所以针对SSA value的数据流分析,在LLVM里都是用sparse的方式做的,而不像传统的IR那样要用bit vector / int vector / set迭代遍历每条指令去传播信息直到到达fixpoint。
  • dense分析:要用个容器携带所有变量的信息去遍历所有指令,即便某条指令不关心的变量信息也要携带过去。
  • sparse分析:变量的信息直接在def与use之间传播,中间不需要遍历其它不相关的指令。
不过Z大的答案略微不准确的是,即便是sparse分析,放在一个dataflow framework里还是可以使用lattice的,而且分析过程可能还是迭代的(只是不需要每次都迭代所有指令而已)。

过程内分析(intraprocedural analysis)

LLVM

LLVM IR虽然被许多人叫做“low-level IR”,但由于它还持有GEP之类的颇为高级的之类,我觉得把它看作“middle-level IR”比较好。
LLVM的大部分优化都在LLVM IR上做,包括所有平台无关优化以及少量平台相关优化(主要是平台相关性影响一些本来通用的优化的策略)。
LLVM IR是SSA形式的,并且维护双向的def-use信息:use-def信息是很自然的通过指针实现,而def-use则是通过一种比较节省内存的跳表/链表来实现的。维持双向def-use信息便于在IR上做各种操作,例如前向数据流分析(forward dataflow analysis)、后向数据流分析(backward dataflow analysis),以及方便的变换IR(例如RAUW——replaceAllUsesWith)。

作为LLVM IR上的数据流分析例子,可以看看这个超简单的optimistic (aggressive) dead code elimination:
llvm/ADCE.cpp at master · llvm-mirror/llvm · GitHub
这个pass自身已经被更强的别的版本的DCE替代了。但是这个用来作为例子讲解还是很不错的。
这个ADCE的本质就是,这是liveness analysis的应用,是一个backward dataflow problem(所以信息顺着use-def方向传播):
  1. 使用一个只有2个元素的lattice,top是unreachable(U),bottom是reachable(R)
  2. 乐观(optimistic)的分析策略,也就是最初假定所有指令都是U,除非能证明是R
  3. 算法的起点是所有terminating指令(例如return)、potentially side effecting指令(例如store、call),这些认为肯定是R
  4. 然后,利用SSA形式的use-def信息,从上述root出发迭代出去,把所有能通过use-def链到达的指令都标记为R(注意这个标记过程,从lattice的角度看是单调(monotonic)的——只能从U变成R)
  5. 最后,没有被标记为R的指令就是U,遍历一次所有指令,把没有被标记为R的指令删除,DCE就完成了。
这里最最重要的地方就是上面的(3)和(4),不是以函数的入口为起点,也不需要线性迭代所有指令(dense);而是以别的特殊指令为起点,并且通过use-def链直接把信息传播到相关的指令上(而不需要携带这些信息逐条指令去看谁需要这些信息,所以叫做sparse)。

上面的描述其实挖了个坑,那就是“针对SSA value的数据流分析”。LLVM IR里,“memory”不是一个SSA value(直到LLVM的memory SSA项目完成为止),所以如果要对memory分析的话,就无法sparse了。留意上面的(3)中的“起点”有potentially side effecting指令,这就是对内存的保守分析。


HotSpot Client Compiler (C1)

HotSpot C1的话,嗯它真的是个超级简单的编译器,没做那么多正式的重量级的分析和优化。

先举个C1 LIR的例子。C1有两层IR,SSA形式的平台无关HIR,和传统形式(非SSA形式)的平台相关LIR。大部分优化都是在HIR上做的,LIR基本上只用来做寄存器分配和最终的代码生成。
在这传统形式的LIR层面上,有个颇为传统liveness analysis:LinearScan::compute_local_live_sets() 与 LinearScan::compute_global_live_sets()
jdk8u/jdk8u/hotspot: ddce0b7cee93 src/share/vm/c1/c1_LinearScan.cpp

先在每个基本块内遍历所有LIR指令算出基本块的live_in和live_out,然后在CFG上从后向前遍历基本块来传播liveness信息。这是典型的dense analysis的思路。



HotSpot C1 HIR的SSA形式…(待续)