Data Flow Analysis

SRC->IR(3AC)->CFG->Data Flow Analysis这是课上到这里学习的静态分析流程，本节课学习了DFA中十分重要的判断数据流的算法，here we go!

什么是数据流分析？

数据流分析就是将源码划分成不同的BBS，在根据CFG在图这个数据结构上进行处理。

may analysis:就是类似于前面的sound，输出信息有真有假

must analysis:类似于complete，输出信息一定为真

以上是三种不同情况的input和output，

• 左侧控制流，IN[s2] = OUT[s1]
• 中间控制流，IN[s2] = IN[s3] = OUT[s1]
• 右侧控制流，IN[s2] = OUT[s1] ^ OUT[s3]

第一种单分支后一个的输入等于前一个的输出；

第二种前一个的输出对应后两个的输入；

第三种后一个的输入等于前两个输出的合集运算

在数据流分析应用（application）中，我们通常将每个program point与一个数据流值（data-flow values）关联，此data-flow value代表了在该点上可以观察到的所有可能的程序状态的抽象集合。对于一个application来说，所有可能的data-flow values构成的集合称为该application的域（domain）。在以上这些内容的基础上，我们可以说，数据流分析的目的就是要为一个“以safe-approximation为导向”的约束（constraints）集合，为所有语句（statements）s，在IN[s]和OUT[s]上，找到一个解（solution）。

前向和后向分析

顾名思义，一个正向分析，一个反向

我们需要将每个BBs单独计算,另外，从前向分析的角度看，BB间控制流有以下特性：

• 𝑂𝑈𝑇[𝐵]=𝑓𝐵(𝐼𝑁[𝐵]),𝑓𝐵=𝑓𝑠𝑛∘ … ∘𝑓𝑠2∘𝑓𝑠1OUT[B]=fB(IN[B]),fB=fsn∘ … ∘fs2∘fs1
• 𝐼𝑁[𝐵]=⋀𝑃 𝑎 𝑝𝑟𝑒𝑑𝑒𝑐𝑒𝑠𝑠𝑜𝑟 𝑜𝑓 𝐵𝑂𝑈𝑇[𝑃]IN[B]=⋀P a predecessor of BOUT[P]

⋀ ⋀ 符号用于表示B的所有前驱对B的贡献的综合结果。

从后向分析的角度看，BB间控制流有以下特性：

• 𝐼𝑁[𝐵]=𝑓𝐵(𝑂𝑈𝑇[𝐵]),𝑓𝐵=𝑓𝑠1∘ … ∘𝑓𝑠𝑛−1∘𝑓𝑠𝑛IN[B]=fB(OUT[B]),fB=fs1∘ … ∘fsn−1∘fsn
• 𝑂𝑈𝑇[𝐵]=⋀𝑆 𝑎 𝑠𝑢𝑐𝑐𝑒𝑠𝑠𝑜𝑟 𝑜𝑓 𝐵𝐼𝑁[𝑆]OUT[B]=⋀S a successor of BIN[S]

Reaching Definitions Analysis(重点！！！)

定义：

A definition d at program point p reaches a point q if there is a path from p to q such that d is not “killed” along that path

对变量v的定义，指的是一个对v赋值的语句。因此，我们可以借助变量v来进一步阐释上述定义：program point p处对变量v的定义在q可达，指的是从p到q有一条路径，而且这条路径上没有其他对v的定义语句。

这个可以结合后面的例子理解，在我看来，其目的类似于污点分析，去寻找相关联影响的函数变量。

对于定义可达性分析的来说，数据流中的值是一个程序中的所有变量的定义，它们可以用bit vector来表示。例如，上述程序我们定义d1-d7（0000000）来表示赋值变量，在program point p处，di被置为1，当且仅当di处的变量定义能够到达p。如B4的输入（0010000）表示d3处（a=u1）会对B4造成影响。

求解transfer functions和control-flow

对于每一个BBs中的transfer functions和control-flow，我们遵循以下定义：

用上述例子，genb可以理解为本BBs的di，如B1中包含d1,d2,d3,将此三位置为1（1110000）killB可以理解为删除与此块中受影响的d，如B1中，有i，j，a三个变量，要找到下面的函数中包含此三个变量的d（d4,d5,d6,d7），将该位di置为0（1110000），OUT[B]为二者的U集；

IN[B]可以理解为前面的BBS的输出的集合

经典算法实现

上述算法中有两个值得讨论的点：

1. 为什么 𝑂𝑈𝑇[𝑒𝑛𝑡𝑟𝑦]=∅OUT[entry]=∅ 被单独拎出来了，没有和下面的for循环合并？
2. 为什么我们能确定while循环一定会终止？（终止条件为while里不再发生改变）

第一个问题比较简单，因为这么写在修改时更方便。在一些其他的分析中，可能entry之外的其他BB的初始化值并非空集，此时只需要修改for循环内部的赋值语句即可。

第二个问题稍微复杂一些，借助后面的例子能够更好地理解。这里我们先回答一下：一个程序中的definitions（di）是有限的，即bit vector的长度是有限的（00000...），每个BB的𝑂𝑈𝑇[𝐵]OUT[B]实际上只与𝐼𝑁[𝐵]IN[B]有关（因为𝑔𝑒𝑛𝐵genB和𝑘𝑖𝑙𝑙𝐵killB总是保持不变），且按照算法来看，𝑂𝑈𝑇[𝐵]OUT[B]置1数一定不会比𝐼𝑁[𝐵]IN[B]小(只有0->1,1->1两种情况)。该算法是单调递增的，并且有一个上界（bit vector全部置1），因此最终一定会停止。

举个例子：

第一轮：初始化所有的输入为空（0000 0000）

第二轮：根据for循环中IN[B]和OUT[B]两个公式，得到每个BBs中的IN和OUT。如B2的IN为1100 0000和0000 0000，U集为 1100 0000，KILL为D2，gen为D3,D4，所以最后变为1011 0000，同理可得下面完整式子，先kill再gen。最后执行完毕发现B1B2B3B4B5的OUT都和第一轮不一样，所以还要再来一轮while

第三轮：同理，以B2为例子，输入为B1和B4的OUT（1100 0000和0011 1100），合并为1111 1100，killD2为1011 1100，genD3D4为1011 1100，最终输出为（1011 1100），经过这一轮发现，B2,B3的OUT仍有不同，还需要再来一轮，同时也发现，对于相同的输入，kill和gen的值固定，输出值不变。

第四轮：经过四轮，所有的OUT值与前一轮的OUT都相同，至此，程序结束。我们也可以理解每一位的具体含义，如B5的OUT(0011 1011),意思是对于B5的块，置于1的位对其均有影响，D3D4D5D7D8的函数。

后面还需要再判断一次吗？

答案是否定的，根据数学原理和前面的分析，kill和gen固定，如果out不变则in不变，IN不变OUT更不会变，至此程序结束。

To be continued