数据流分析之def-use链分析

引言

编译过程中，知道函数中每个指令引用的变量(或虚拟寄存器)来自于前面的哪一次赋值是很有必要的。例如llvm中对store/load转phi优化，就需要准确知道该信息。def-use链分析(也叫定值分析)能帮助我们准确地建立这些信息。

1 相关概念

• 入口定值列表
  指每条指令执行前的相关变量的可能值。指令n的入口定值集合表示为in[n]，n为指令序号、元素为寄存器+赋值指令序号的二元组；

• 出口定值列表
  指每条指令执行后的相关变量的可能值。指令n的出口定值集合表示为out[n]，n为指令序号、元素为寄存器+赋值指令序号的二元组；

• 生成定值
  指令操作中，对寄存器的修改又称为生成定值。指令n的生成定值集合表示为gen[n]，n为指令序号、元素为寄存器+赋值指令序号的二元组(一般有0个或1个元素)；

• 杀死定值
  若一条指令对寄存器R生成了定值，其他指令对R的生成定值称为对该条指令关于R的杀死定值。指令n的杀死定值集合表示为kill[n]，n为指令序号、元素为寄存器+赋值指令序号的二元组；

注：定值分析就是分析每条指令执行前后的入口定值列表和出口定值列表。另外对于对于llvm IR这种SSA类型指令，上述集合元素可以直接是指令序号或指令指针(因为指令序号/指针与定值寄存器是等价的)。

2 算法

2.1 算法规则

整个算法其核心思想是如下三条规则：

1. 若变量属于gen[n]，必属于out[n]。即用每个指令结点的gen初始化其out；
2. 若变量属于out[n]，必属于n的后继结点e的out[e]。即沿着有向图正向求并集传播；
3. 若变量属于in[n]且不属于kill[n]，必属于out[n]。即kill会阻止正向传播；

2.2 算法流程

1. 首先，将函数的指令按执行顺序(包括跳转顺序)串成一个有向图，每个结点对应一条指令；
2. 将每个指令结点n的 gen[n] 添加到 out[n] 中（添加前 out[n] 为空集合）；
3. 反复执行如下操作，直到所有结点的 in 和 out 没有变化：
   将每个结点n的 out[n] 添加到其后继结点e的 in[e] 中；
   将每个结点n的 in[n] 中、且不在 kill[n] 中的变量添加到out[n]中；

2.3 算法优化

3 举例