数据流分析

数据流分析概念

• 点（point）：程序中某条指令的前/后位置
• 定值点（definition point）：对某变量赋值的指令位置
• 引用点（use point）：使用某变量值的指令位置

到达定值（Reaching Definition）

定义：定值点 $d$ 到达点 $p$，当且仅当存在一条路径从 $d$ 到 $p$，且此路径上 $d$ 未被注销。

UD 链 / DU 链

• UD 链（Use-Definition Chain）：对某个引用点，所有可能到达该点的定值点集合
• DU 链（Definition-Use Chain）：对某个定值点，所有可能使用该定值的引用点集合

活跃变量（Live Variable）

变量 $v$ 在点 $p$ 处活跃，当且仅当存在一条路径从 $p$ 出发，在 $v$ 被重定值前被引用。

gen 和 kill

• gen：本基本块内产生的定值
• kill：本基本块内被注销的定值（即同一变量被重新赋值）

数据流方向

方向	示例
前 $\to$ 后	到达定值、可用表达式
后 $\to$ 前	活跃变量

迭代算法（到达定值）

初始化：

• $in[B_0]=\varnothing$（入口基本块）
• $out[B_0]=gen[B_0]$
• $in[B]=\varnothing$，$out[B]=gen[B]$（对 $B\ne B_0$）

迭代至不动点：

1. 对每个基本块 $B\ne B_0$：$in[B]={\bigcup }_{p\in pred(B)}out[p]$
2. $out[B]=(in[B]-kill[B])\cup gen[B]$
3. 若本轮 $in/out$ 有变化，重复 1-2

实现中用 $change$ 标记记录变化，仅在有变化的基本块间传播。

到达定值数据流方程

重点 数据流方程 $out=(in-kill)\cup gen$。

$$\begin{array}{rl}out[B]& =(in[B]-kill[B])\cup gen[B]\\ in[B]& =\bigcup _{p\in pred(B)}out[p]\end{array}$$

• 会合运算：并集（任何一个前驱的定值都可能到达）
• 方向：前驱 $\to$ 后继（前 $\to$ 后）

可用表达式数据流方程

满足交集（表达式必须所有路径都可用才算可用）：

$$\begin{array}{rl}out[B]& =(in[B]-kill[B])\cup gen[B]\\ in[B]& =\bigcap _{p\in pred(B)}out[p]\end{array}$$

• 会合运算：交集（所有前驱路径都必须经过）

活跃变量数据流方程

后 $\to$ 前方向（从后继出发反推到前驱）：

$$\begin{array}{rl}in[B]& =(out[B]-def[B])\cup use[B]\\ out[B]& =\bigcup _{s\in succ(B)}in[s]\end{array}$$

• $def[B]$：在 B 中定值但定值前未被引用的变量
• $use[B]$：在 B 中引用但引用前未被定值的变量

重点 活跃变量数据流方程方向与控制流相反（后 $\to$ 前）。

数据流分析的结果为 循环优化算法 中的代码外提、强度削弱和归纳变量删除提供关键信息（如定值可达性、变量活跃性）。