数据流分析概述
数据是如何在CFG上流动的？
特定于应用的数据是如何流经Nodes、Edges、CFG的？
Nodes (BBs/statements)
Edges (control flows)
CFG(a program)
不同的数据流分析应用程序具有<br>不同的数据抽象和<br>不同的流安全近似策略，即<br>不同的传递函数和控制流处理
数据抽象（data abstraction）
+、-、0、unknown、undefined
流安全近似策略（flow safe-approximation）
over-approximation
under-approximation
传递函数（transfer functions）
+ op - = - ; + op + = +
控制流处理（control-flow handlings）
union the signs at merges
may analysis VS must analysis
may analysis
输出的信息可能是对的（over-approximation）
must analysis
输出的信息必须是对的（under-approximation）
Over- and under-approximations都是为了分析的安全性
大多数分析是 may analysis
数据流分析基础
Input and Output States
IR语句的每次执行都会将输入状态（input state）转换为新的输出状态（output state）
输入（输出）状态与语句之前（之后）的程序点（program point）是相关联的
在每个数据流分析应用程序中，我们与每个程序点关联一个数据流值（data-flow value），该值代表对该点（program states）可以观察到的所有可能程序状态集的抽象。
数据流分析应用1：Reaching Definitions Analysis（定义可达分析）
变量v的定义是为v赋值的语句（这里的定义不仅是声明一个变量，也包括为这个变量赋值）
如果存在一条从p到q的路径，则程序点p上的定义d可以到达点q，且d未被沿着该路径“kill”。
也可以这么说：如果存在一条从p到q的路径，则在程序点p处的变量v的定义可以到达点q，而且在该路径上不会出现v的新定义（被赋值）。
定义可达的应用（没理解）
到达定义可用于检测可能的未定义变量。 例如，在CFG的入口处为每个变量v引入虚拟定义，<br>如果v的虚拟定义到达使用v的点p，则可以在定义之前使用v（因为未定义达到v）
定义可达的理解
Data Flow Values/Facts
程序中所有变量的定义可以用位向量表示
例子
D：v = x op y
这条语句“生成”变量v的定义D。它并“kill”程序中定义变量v的所有其他定义，而其余输入的定义不受影响。
Transfer Function（传递函数、作用在一个BB上）
Control Flow（控制流处理、作用在BB之间）
U的含义：只要存在至少一条定义到达的路径，定义就可以到达程序点。
定义可达的算法
算法执行的详细例子（详见PPT）
可以通过while中的条件实现终止吗？
详见PPT
数据流分析应用2：Live Variables Analysis（活变量分析）
实时变量分析表明，是否可以沿CFG的某个路径（从p开始）使用程序点p处的变量v的值。 如果是这样，则v活在p处； 否则，v在p处死亡。
活变量分析的理解
Data Flow Values/Facts
程序中所有变量的定义可以用位向量表示
实例
注意：如果在v在重新被定义前被使用，那么在IN集中也是live的。
活变量分析的算法
算法执行的详细例子（详见PPT）
数据流分析应用3：Available Expressions Analysis（可用表达式分析）
如果（1）从entry到p的所有路径都必须经过x op y的求值，<br>并且（2）在最后一次对x op y求值后，则没有重新定义x op y，<br>则表达式x op y在程序点p处可用。
这个定义意味着在程序p处，我们可以将表达式x op y替换为其最后一次求值的结果
可用表达式的信息可用于检测全局通用子表达式
可用表达式分析的理解
Data Flow Values/Facts
程序中所有变量的定义可以用位向量表示
可用表达式分析的算法
算法执行的详细例子（详见PPT）
