数据流分析（data flow analysis）

数据流分析是一类分析，其分析对象是控制流图（CFG），产生特定于应用程序的数据结果（application-specific Data）。

不同的数据流分析应用有着：

• 不同的数据抽象
• 不同的流安全近似（flow safe-approximation）策略
• 不同的传输函数和控制流处理（transfer functions & control-flow handings）

flow through

• nodes (BBs/statements)
• edges (control flows of)
• cfg (a program)

输入和输出状态

在每个语句中，前一语句的输出作为当前语句的输入，生成当前的输出。

在每个数据流分析应用中，我们将每个程序点（program point）与数据流值（data-flow value）关联起来，这个数据流值表示该点可以观察到的所有可能的程序状态的抽象。
数据流分析旨在找到一个解，其中包含一组在In[s]和OUT[s]中的以安全近似为导向的约束，对于所有语句s：

• 基于语句语义的约束（传输函数，transfer function）
• 基于控制流的约束

传输函数约束的符号表示

两种类型：

1. 正向分析（forward analysis）
   OUT[s] = f_s(IN[s])

2. 反向分析：（backward analysis）
   IN[s] = f_s(OUT[s])

基本块内的控制流（control flow within a BB）：

IN[s_i+1] = OUT[s_i], for all i=1,2,...,n-1
基本块之间的控制流（control flow among BBs）：

参见图表

数据流分析应用（Data flow analysis Applications）

非常基础的3种数据流模式：

1. 到达定义分析（Reaching Definitions Analysis）
2. 活跃变量分析（Live Variables Analysis）
3. 可用表达式分析（Available Expressions Analysis）

到达定义分析（Reaching Definitions Analysis）

A definition d at program point p reaches a point q if there is a path from p to q such that d is not killed along that path
在程序点p的定义d能够达到程序点q，是否有一个路径从p到q且d在路径上没有被killed

给定程序点q，能够检查某变量的值是何时定义的。

可以用于检查可能的未定义变量，在入口为每个变量v引入dummy定义，如果v的dummy定义能够到达使用v的某个程序点p没有被killed
也可以用于常量传播，复制传播上。

分类：

• forward/backward analysis? forward analysis
• must/may analysis? may analysis(over apprioximation)

data flow values/ facts: all definiton in a program，可以用bit vectors表示

algorithm

• 为什么OUT[entry]=空集？
  • 回想out定义（在这一program point有什么定义可以流到这里）
• 为什么对各个基本块初始化entry被排除而单独对entry初始化？
  • 因为这个算法是一个data algorithm模板，其他的data analysis(特别是must analysis) 中entry和各基本块的初始化会不一样
• 为什么需要判断OUT是否有变化然后多次迭代？
  • CFG可能包含环，第一次遍历CFG时，某些边可能未初始化。多次迭代是为了获得最终结果。
• 为什么迭代一定会停止？
  对于某个基本块B，kill和gen是常量，所以输入不变输出不变。
  当一个fact（某个位）加到OUT[s]，要么是通过gen添加的，要么是前一个块的fact经过当前块的survivor。
  当添加更多fact（某个位）时，它们要么被killed，要么流入到OUT[s]中。
  因此，OUT[s]从来不会变小（其中的位只会从0变成1，或者保持1不变）

也就是说，如果某位想变0，不可能是kill或gen引起的（因为这俩是常量），只可能是前一个BB的OUT中该位从1变为了0，但这也是不可能的，理由同前，这个过程是递归的，直到入口都不会有人的OUT从1变为了0

因为fact集合是有限的，所以一定有一趟迭代没有任何东西添加到OUT，所以算法终止

活跃变量分析（Live Variables Analysis）

分析在程序点（program point）p的变量v的值是否在CFG中从p开始的路径中被使用（v在这条路径中使用前不能被重新定义）。

给定程序点p，某变量的值未来是否会使用到

一个重要用途：可用于为基本块进行寄存器分配。如果我们能分析出某寄存器中的值在以后不会被使用（dead value），我们更倾向于使用这个寄存器。

data flow values/ facts: all variable in a program

分类：

• forward/backward analysis? backward analysis
• must/may analysis? may analysis

注意方程中：
defb是指这样的变量：基本块中对其定值先于任何对其使用
useb是指这样的变量：基本块中对其使用先于任何对其定值

algorithm

可用表达式分析（Available Expressions Analysis）

A definition d at program point p reaches a point q if there is a path from p to q such that d is not killed along that path
在程序点p的表达式x op y是可用的，如果

1. 所有从入口到p一定经过x op y的求值；
2. 在最后一个x op y的求值以后，没有对x或y的重新定义。

这个定义意味着在程序点p，我们可以用最后依次x op y的求值结果替换表达式x op y

主要用途：寻找全局公共子表达式

分类：

• forward/backward analysis? / analysis
• must/may analysis? must analysis(under apprioximation) why? may report an expression as unavailable even if it is truly available

data flow values/ facts: all expression in a program

algorithm

注意基本块初始化为全1（因为后面对于汇聚都是取交集，初始化为0会导致错误）
注意汇聚都是取交集（因为must analysis，不能有误报，不能引起错误优化）

小结