What is Data Flow Analysis ?
How application-specific Data flows on CFG with safe approximation.
分析算法感兴趣的数据如何流经控制流图。
safe approximation for different purposes 不同的分析目的,对于safe有不同的定义:
相同点:这两种目的往往殊途同归地达到Soundness。
不同的目的对应了不同的手段:1. Data Abstraction 2. Approximation Strategies i.e. transfer functions & control flow handling.
Definition:
$IN[s]\ OUT[s]$ stand for input & output states of program points i.e. before and after executing the IR statements $s$ respectively.
e.g.:
右侧是最简单的程序点的示意图。包括:
语句之间的状态关系1:
右图表示两个顺序的语句之间状态关系。
即,$s_2$的输入是$s_1$的输出
$IN[s_2]=OUT[s_1]$
带有控制流的语句间的状态关系1:
右图表示了一种分支语句的状态关系
带有控制流的语句间的状态关系2:
右图是分支合并语句的状态关系,引入了操作符$\wedge$,表示语句分支的合并