数据流分析

数据流主要研究数据怎么在CFG(程序流程图 BB+边)中流动

基本术语

input and output states

汇聚的时候那个符号没有限制，可能是交集也可能是并集

states会被关联一个value

Reaching Definitions

注意：对于Entry的IN和OUT不作更新

根据算法得出在每个边里对每个destination是否能reach的抽象表达值

当前块中的D，->1
当前块中的D的左值，在其它块的D中也是左值时，kill掉 ->0

算法的结束条件是每个out和上一轮一致

每个out的变化规律：只会不变或增长有0->1 或 1->1,不会有1->0

因此算法一定会结束，会到达一个不动点

Live Variables

注意：对于Exit的IN和OUT不作更新

live

当一个变量在一条path里没有被redefine，则称为live的

抽象表示

与reaching destination类似，用一些列二进制数表示一些列变量

backward or forward

为了设计算法简便，使用backward

forward会使得判断live比较麻烦

对于S1 和 S2 使用may analysis，把in 取并集，OUT[B]=IN[S2] U IN[S1]

这些in和out都是变量的集合，

in->out的算法

IN[B]=$use_B$ U (OUT[B]-$def_B$)

如果use在redefine之前，也认为live

出现在左值说明被redefine

出现在右值说明被use

当IN不变时结束

先kill define再加use

image-20231008161552115

一般情况下，may analysis初始化是空，must analysis初始化是all

Available Expression

注意：对于Entry的IN和OUT不作更新

判断表达式是否available（是否还能用，与前一个块相比，表示的值是否变化）

数据抽象

1bit表示一个expression

forward

算法

如果有变量被define，要kill掉含有该变量的表达式
加上出现的表达式
初始化时除了entry的out，其它都是全集

must analysis

常量传播

meetvalue规则

NAC：not a const
UNDEF：未定义
c：常量

UNDEF⊓v=v 解释：可能v是const，但这样一meet就成了const，似乎漏报了一个undef，但这关注的是常量传播，并不是live variables，

在做常量传播时，会假设程序是正确的，因此如果这里真的meet到了UNDEF，其实是不会走这条path的

transfer函数

删除x变量（redefine了）

软件分析-数据流分析