P3-4
2021-04-28 14:54:27 1 举报AI智能生成
南大软件分析P3-4
作者其他创作
大纲/内容
P3-4
数据流分析概述
数据是如何在CFG上流动的？
特定于应用的数据是如何流经Nodes、Edges、CFG的？
Nodes (BBs/statements)
Edges (control flows)
CFG(a program)
不同的数据流分析应用程序具有不同的数据抽象和不同的流安全近似策略，即不同的传递函数和控制流处理
数据抽象（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引入虚拟定义，如果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）
为什么这种迭代算法最终可以停止？
详见PPT
可以通过while中的条件实现终止吗？
数据流分析应用2：Live Variables Analysis（活变量分析）
实时变量分析表明，是否可以沿CFG的某个路径（从p开始）使用程序点p处的变量v的值。 如果是这样，则v活在p处； 否则，v在p处死亡。
活变量分析的理解
实例
注意：如果在v在重新被定义前被使用，那么在IN集中也是live的。
活变量分析的算法
数据流分析应用3：Available Expressions Analysis（可用表达式分析）
如果（1）从entry到p的所有路径都必须经过x op y的求值，并且（2）在最后一次对x op y求值后，则没有重新定义x op y，则表达式x op y在程序点p处可用。
这个定义意味着在程序p处，我们可以将表达式x op y替换为其最后一次求值的结果
可用表达式的信息可用于检测全局通用子表达式
可用表达式分析的理解
可用表达式分析的算法
数据流分析3种应用的比较
0 条评论
回复 删除
下一页
