Data Flow Analysis

前面一节，我们分析了定义式defection在数据流中的判别。这一节，我们分析其他两个variable和expression在数据流中的影响。

Live Variables Analysis

定义：Live variables analysis tells whether the value of variable v at program point p could be used along some path in CFG starting at p. If so, v is live at p; otherwise, v is dead at p.

如果我们要判断变量v在p点存活，当且仅当：

1. 首先，变量v在p点之后有被使用。
2. 其次，从p点开始到被使用前，过程中不能出现变量v的重定义。

存活变量分析可用于处理寄存器分配。例如，在寄存器全部被占用、而我们又需要使用其中一个的时候，可以将其中某个在该时刻存储非存活变量的寄存器优先释放出来使用。

data abstraction：我们将每个变量占1位，在p处当Vi被置为1时，表明Vi在p点存活。

safe-approximation：采用backward分析，从exit向上分析

因为是backward分析，所以control flow handling和transfer function和definition相反，先cfh，再tf

在我理解，当OUT[B]={v}的情况下，IN[B]的值可以看作在P->B之间，变量v是否被use，如5中，v=2被重新定义，所以前面v=3内存被释放，IN[B]={ }；如6中，k=v，v先被use，再被def，任然使用到v=3中的v。

OUT[B]=S a successor of B⋃IN[S]

𝐼𝑁[𝐵]=𝑢𝑠𝑒𝐵∪(𝑂𝑈𝑇[𝐵]−𝑑𝑒𝑓𝐵)IN[B]=useB∪(OUT[B]−defB)

Live variables analysis算法：

注意此时的初始化从IN[exit]={ }开始，判断终止条件为每个BBs的IN是否相同，前面是先kill再gen，这里是先减去def，再加上use；如果再同一个BBs中先use再def同一个变量，则不算。

举个例子：

初始化：从IN[exit]开始，IN[exit]=0000000，其他每个BBs的IN都设置为空0000000

第一轮：根据backward从后向前分析，B5中，z=2p，use p，def z，先置z为0，再置p为1，得到B3,B4的OUT000 1000；B2中，它的OUT[B3]=100 1000,OUT[B4]=010 1000,先对OUT取交集得110 1000，先use k和m，再def m和y，最后得100 1001。最后比较他们的IN，发现每一个都不同，开启第二轮。

第二轮：因为每一个块中的use和def都不变，所以当两轮他们的OUT相同时（蓝色和红色），则这一轮他们对应的IN也不变，这里B4的OUT[B2]改变，在B4中，OUT[B2]=100 1001,OUT[B5]=000 1000,交集100 1001，先use y，再def x和q，得IN[B4]=010 1001；B2中，OUT[B2]=110 1001,use k、m，def m和y，得IN[B2]=100 1001.最后发现只有B4的IN有不同，再来一轮。

第三轮：由于其他的IN都不变，看B4，mergeOUT[B2]OUT[B5]得010 1001，先usey，再defxq,得101 1001，至此，所有的IN都相同，标准改变，程序结束。

Available Expressions Analysis

定义：An expression x op y is available at program point p if (1) all paths from the entry to p must pass through the evaluation of x op y, and (2) after the last evaluation of x op y, there is no redefinition of x or y

根据以上定义，表达式在p点是可用的，当且仅当：

1. 首先，从entry到program point p的路径都要经过x op y的表达式计算。
2. 其次，在最后一处表达式计算之后、p点之前，过程中不能出现变量x或y的重定义。

data abstraction：我们将每个表达式占1位，在p处当E被置为1时，表明E在p点存活。

safe-approximation：采用forward分析，与defination不同的是，可用表达式分析一种must分析，要求“所有”路径都经过x op y的表达式计算才行。也就是说，这里是一种under-approximation的分析，可能会将一个表达式报告为不可用的，即使它在运行时实际上是可用的。

如图所示，采用must分析时，我们要求从entry到program point p的所有路径都要经过x op y的表达式计算，即使他们表达的含义相同（a=e16*x=3与x=3是同一个意思，但不满足相同的xorp表达式也不行）

transfer function和control flow handling如下：

𝑂𝑈𝑇[𝐵]=𝑔𝑒𝑛𝐵∪(𝐼𝑁[𝐵]−𝑘𝑖𝑙𝑙𝐵)OUT[B]=genB∪(IN[B]−killB)

𝐼𝑁[𝐵]=⋂𝑃 𝑎 𝑝𝑟𝑒𝑑𝑒𝑐𝑒𝑠𝑠𝑜𝑟 𝑜𝑓 𝐵𝑂𝑈𝑇[𝑃]IN[B]=P a predecessor of B⋂OUT[P]

算法如下：

这里需要注意几点：

1、我们在处理表达式时，要先kill再gen
2、初始化时，OUT[ENTRY]为空，但其他的OUT[B]都设为全1
3、control flow handing中所有B的前驱OUT取并集（前面两个时取交集），因为这里初始化为全1，只有取并集才会得到不同的值（单调性）

举个例子：

初始化：OUT[entry]设为空，其他OUT[B]设为全1.

第一轮：B2中，OUT[B4]11111和OUT[B1]10000取并集得10000，先kill k和p相关表达式，再genz/5和e7x表达式，得01010；B4中，OUT[B2]01010,先kill x和q，再gen2 y和e7x表达式，得01110。最后比较所有OUT，发现都有改变，第二轮。

第二轮：同上，B2中，OUT[B4]和OUT[B1]取并集得00000，先kill k和p相关，再gen后面两个表达式得01010；所有的输入都没有再发生改变，所以此次循环结束，程序结束。

重中之重！！！

这两节课最重要的就是学会表格内的内容，至此算是入了一点门，纸上得来终觉浅，绝知此事要躬行，继续加油完成实践，能学会多少就是多少！