前言
上节课，李樾老师教授了数据流分析基础知识和定义可达性分析。这是数据流分析应用的第二节课，包括存活变量（live variables）分析和可用表达式（available expressions）分析。这节课的最后，老师带领我们对两节课中涉及的三种数据流分析应用进行了总结。
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点是存活的，当且仅当：
- 首先，变量v在p点之后有被使用。
- 其次，从p点开始到被使用前，过程中不能出现变量v的重定义。
存活变量分析可用于处理寄存器分配。例如，在寄存器全部被占用、而我们又需要使用其中一个的时候，可以将其中某个在该时刻存储非存活变量的寄存器优先释放出来使用。
和上一节的定义可达性分析类似，接下来分别考虑data abstraction和safe-approximation。
对于data abstraction来说，这里数据流的值是一个程序中的所有变量，可以用bit vectors表示。例如，如果$V_{1}$到$V_{100}$表示程序中所有的100个变量，那么我们可以用一个长度为100的bit vector来表示它。在program point p处，$V_{i}$被置1，当且仅当$V_{i}$在p点存活。
对于safe-approximation来说，存活变量分析应该采用一种backward analysis的思路，也就是从exit往上分析，直到p点——因为定义中提到的判定条件是从p点开始，而非到p点结束。换而言之，我们最终求的是$IN[B]$，而非$OUT[B]$。
基于此，可以得到如control flow handling和transfer function（注意，顺序反过来了，因为是backward analysis）：
$$ OUT[B] = \bigcup_{S\ a\ successor\ of\ B}IN[S] $$
$$ IN[B] = use_{B} \cup (OUT[B] - def_{B}) $$
存活变量分析算法如下：
接下来是一个示例。除了初始化过程外，这个分析进行了三轮。第三轮中，bit vector没有发生变化，循环终止。最终得到的不同program point处的bit vector（IN）就是存活变量分析结果：
如何使用或解读这个结果呢？例如，在$B_{3}$入口处，变量x是存活的，因此在这个地方去使用存储x的寄存器就不是一个好策略，应该去使用存储非存活变量的寄存器，如变量y的。
关于这个算法在该例子上执行的具体过程，推荐去看李樾老师的授课视频或课件，非常详细清楚。存活变量分析就到此为止了，接下来是可用表达式分析的部分。
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点是可用的，当且仅当：
- 首先，从entry到program point p的路径都要经过
x op y的表达式计算。 - 其次，在最后一处表达式计算之后、p点之前，过程中不能出现变量x或y的重定义。
从定义来看，判定条件是到p点结束，因此应该采用forward analysis的思路。另外，与定义可达性分析和存活变量分析不同的是，可用表达式分析一种must分析，要求“所有”路径都经过x op y的表达式计算才行。也就是说，这里是一种under-approximation的分析，可能会将一个表达式报告为不可用的，即使它在运行时实际上是可用的。
轻车熟路，接下来分别考虑data abstraction和safe-approximation。
对于data abstraction来说，这里数据流的值是一个程序中的所有表达式，可以用bit vectors表示。例如，如果$E_{1}$到$E_{100}$表示程序中所有的100个表达式，那么我们可以用一个长度为100的bit vector来表示它。在program point p处，$E_{i}$被置1，当且仅当$E_{i}$在p点可用。
对于safe-approximation来说，transfer function和control flow handling如下：
$$ OUT[B] = gen_{B} \cup (IN[B] - kill_{B}) $$
$$ IN[B] = \bigcap_{P\ a\ predecessor\ of\ B} OUT[P] $$
注意，这里是must analysis，所以与定义可达性分析不同，control flow handling是对前驱数据结果流取交集，而非并集。
可用表达式分析算法如下：
接下来是一个示例。除了初始化过程外，这个分析进行了两轮。第二轮中，bit vector没有发生变化，循环终止。最终得到的不同program point处的bit vector（OUT）就是可用表达式分析结果：
关于这个算法在该例子上执行的具体过程，推荐去看李樾老师的授课视频或课件，非常详细清楚。
总结与思考
至此，我们已经了解了三种数据流分析应用。下表是对这三种应用的总结：
| Reach Definitions | Live Variables | Available Expressions | |
|---|---|---|---|
| Domain | set of definitions | set of variables | set of experssions |
| Direction | forwards | backwards | forwards |
| May/Must | may | may | must |
| Boundary | $OUT[entry] = \empty$ | $IN[exit] = \empty$ | $OUT[entry] = \empty$ |
| Initialization | $OUT[B] = \empty$ | $IN[B] = \empty$ | $OUT[B] = \cup$ |
| Transfer Function | $OUT = gen \cup (IN - kill)$ | $IN = gen \cup (OUT - kill)$ | $OUT = gen \cup (IN - kill)$ |
| Meet | $\bigcup$ | $\bigcup$ | $\bigcap$ |
在本课的最后，李樾老师提到，开课以来，有的人离开，有的人始终坚持，还有一些在国内企业工作的人也加入进来学习。其实从B站课程视频列表中的播放量数据也可以看出来，随着课程的推进，整体的播放量趋势是下降的（如下图中红色箭头所示）。当然了，这也与课程视频在B站的推出时间有关，而且也有两处上升的情况（如下图中绿色箭头所示）。
无论如何，对于自己感兴趣和热爱的事物，一定要坚持下去。毕竟，无论是学习还是工作，找到一个让自己愿意投身的领域，从而不觉得时光虚度，并不容易。