NJU-Static-Analysis-Data-Flow-Analysis-1
Data Flow Analysis
the core in Data Flow Analysis
- 对数据的抽象
- 根据分析的类型，做出合适的估算
- 数据如何transfer
- 控制流如何处理
- CFG
May Analysis 和 Must Analysis
May analysis：输出信息可能正确 => Sound
Must analysis：输出信息一定正确 => complete
- 不同的数据流分析
转移函数 与 控制流信息
different data-flow analysis applications have
different data abstraction and
different flow safe-approximation strategies, i.e.,
different transfer functions and control-flow handlings
Preliminaries of Data Flow Analysis
Input and Output States
IR statement（$s_1$ ，$s_2$，$s_3$）
program point（input state 和 output state）=> 控制流edge上的程序状态
在具体的数据流分析中，我们把
PP关联一个数据流值，代表该点中可观察到的抽象的程序状态
一个说明Program Point的例子：
下图中的红色点就是Program Point
Program Point与一个 data - flow value相挂钩
数据流分析
数据流分析：为所有语句的IN[s]和OUT[s]的一组安全近似导向约束找到一个解决方案
- 基于语句语义的约束，传递函数
- 基于控制流的约束
Transfer Function’s Constrains
- 控制流分析类型
控制流的约束
- BB内控制流
- BB间控制流
Reaching Definitions Analysis（到达定值分析）
Reaching Definitions 基本概念
program point p 处对变量v的定义在q处可达，指p到q有一条路径，且在这条路径中不再存在对v的定义
x的定值d到达 （reaching） p：假定x有定值d（definition），如果存在一个路径p，并且在该路径上没有x的其他定值点
如果该路径上对 x 有其他定义，我们称x这个定值在该路径上 killed 了
到达定值分析可以用来检测源代码中的未定义变量，检测思路：CFG入口处为源代码中的所有变量引入dummy definition，如果最终某个变量v的dummy definition能够达到该变量使用的program point，则变量v为未定义变量
bit vector
使用bit vector的数据结构来表示：对于某个Program Point（记为p），$D_i$在该处置为1 <=> $D_i$处的变量定义经过某个BB后能够到达p
比如下图中的蓝色箭头中的1100 0000，表示$D_1$这条definition中的变量x在经过B2后能够到达
Transfer Function和Control Flow 约束
- Transfer Function（转移函数）约束
Gen指当前BB中存有的definition，而Kill指当前块中存有的definition对应的变量对应的其他definition
例子：B1块中有$d_1$、$d_2$、$d_3$三条definition（记为
gen），其对应变量为i、j、a，这三个变量有关的、且在其他BB的definition有$d_4$、$d_5$、$d_6$、$d_7$（记为kill）
一个BB的gen和kill都可以直接通过扫描所有BB来确定
- control flow handling（控制流处理）约束
处理下一个BB的In[B]，因为输入可能来自很多其他BB的OUT，所以使用Union
到达定值分析的算法
Boundary Condition和其他Basic Block需要分隔开（可以理解为这是一个Iteration算法模板）
例子：参考课程PPT，跟一遍就能体悟到
算法停止的时机
这是整个算法的灵魂，重点在于transfer function的设计
对于一个已经构建好的控制流图，其gen[B]和kill[B]是固定的，所以能在多层迭代中存留的1必定会一直存留，所以正如课中所言，bit vector中每一位的最终结果必然是0->1或1->1，同时definition的个数为有限。
所以必然存在一个bit vector的状态上界，等到某轮迭代结束后到达这个上界，使得算法停止