【静态分析】数据流分析-Part II

前言

上一篇【静态分析】数据流分析-Part I - 求索对数据流分析中的Reaching Definition Analysis中进行了详解，用于发现undefined variables，本文继续第二部分内容——Live Variables Analysis。主要内容包括：

  • Live Variables Analysis的定义和理解
  • Live Variables Analysis算法设计与详解
  • 举个栗子
  • 总结

读完本文会对数据流分析Live Variables Analysis内容有一个初步的了解，解答包括是什么，怎么做，效果怎么样三方面的问题。

本文中涉及的一些专业术语或定义可在上一篇Part I中找到，强烈建议先阅读上一篇文章，本文不再重复赘述

Live Variables Analysis

从名字翻译过来是对存储变量的分析，自然而然要引出定义什么是Live，什么是Dead。

对于明确给定的的一个program point p，如果存在一条执行路径，在该路径上Variable v被使用过（如a = v），则认为v是live，否则就是dead

换成人话就是如果没被使用过的变量就是dead(没用的变量)，就好比初始化了一个变量v，然而后面的程序就没v什么事了，那这个v等于dead

image-20210327143037134

注意在该路径上v不应该被重新定义

那Live Variables Analysis有什么作用呢？

一个常见的场景是当程序需要对某些变量进行计算，同时寄存器已经满了的时候，就可以将dead的变量从寄存器中替换掉。

Live Variables Analysis与Reaching Definition Analysis的分析不同的一点是采用了backward的分析方式，也就是自底向上（倒着分析），这一点需要解释一下：

  • 为什么采用backward的分析方式：假设forward分析，对于pogram point p要确认v是否live的前提是找到一个v被使用的语句，并且一直要算到exit,这也就意味着，在执行到exit之前，都要保留p这个位置关于v的信息，这意味着对一个变量v需要一个一维数组保留其到exit前所有的状态，对于多个v，那就需要二维数组来存储。

    但如果是backward，只要发现v被使用的情况，只需要找前面最近的一条对于v的definition匹配上即可，因此这个过程中可以用一维的数组存储所有的变量，当匹配到相应definition就认定该变量对该program point p是live的。

后面依然针对Abstraction,Transfer Function,Control Flow三个部分依次实现。

Abstraction

针对Live Variables Analysis，我们的关注点在于变量v的变化，它有两个状态live or dead，因此我们依然可以用bit vector的方式去对程序中出现的多个变量进行定义，假设程序有V1,V2,...,Vn，用1表示live，0表示dead，容易得到一组向量表示00...00(初始化的时候所有v都是dead)

Transfer Function

前面我们已经确定了backward，也就是说在经过一个BB的时候，需要从OUT[B]结合BB中对v的使用情况，计算得到IN[B]，如此，我们需要考虑几种不同BB的情况（下面的v并非一个具体的变量，而是所有在BB中可能被使用的变量）：

  1. BB中没用对v的使用，也没有对v重新定义（如k=n）：很显然IN[B] = OUT[B]
  2. BB中存在对v的使用，但没有对v重新定义（如k=v）: 显然在IN[B]中要加上使用的部分，用$use_B$表示，即$IN[B] = OUT[B] \bigcup use_B$
  3. BB中不存在对v的使用，但有对v的重新定义（如v=3）：这意味着要从OUT[B]中去除被定义的部分，即$IN[B]=OUT[B]-def_B$
  4. BB中同时存在对v的定义和使用，这时候就要分开考虑定义在前还是在后：
    • 定义在前（v=2 k=v）：实际上这时候被使用的v已经是新定义的v了，因此和3一样处理
    • 定义在后（k=v,v=2）：这时候被使用的v依然是原来的v，只不过用完之后被重新定义了（根据Live Variables Analysis的定义，v should not be redefined before usage），这意味着这种情况也是live的，同2处理

综上所述，我们可以得到Transfer Function:

其中$use_B$是指那些use在redefine之前的的使用

Control Flow

下面考虑如何处理数据流汇聚的情况，根据前面的Live Variables Analysis定义，只要存在一条执行路径，该变量被使用过即可，因此与Reaching Definition Analysis相同，Live Variables Analysis的Control Flow也是取$\bigcup$ ，只不过由于是backward，OUTp[B]变成求所有后继节点IN[S]的并集：

上面对Transfer Function和Control Flow的解释多用文字，因此配上一张老师提供的例图来加深理解：

image-20210327154929253

其中，假设OUT[B] = {v}（即在OUT[B]中v是live的），根据图中不同数字标注的情况，计算IN[B]中v的live,dead情况

Live Variables Analysis 算法设计

有了之前Reaching Definition Analysis的算法设计思路，其实我们对Live Variables Analysis算法的设计应该变得很容易，主要关注变化的点：

  1. 分析方向由forward转向backward，这意味着我们初始化的对象要从entry转向exit，OUT转向IN
  2. 关注的变化对象要修改了，之前是关注OUT，因为最终计算结果在OUT[B]中体现，但现在要看IN[B]了

综上，结合Transfer Function和Control Flow，可以得到算法如下：

image-20210327160043126

这里对算法不过多解释，详细可以参考上一篇对Reaching Definition Analysis的算法分析过程

举个栗子

同样地，理解了概念之后，需要经过一个实际的栗子来加深映像，与上文一样，这里受限于文章内容，只给出起始和结束的状态：

  • 起始：假设某CFG如下

image-20210327160354443

左上角是程序中出现的变量，0表示都还未被使用

  • 结束

image-20210327160455308

B5 B4 B3 B2 B1
def z x, q x m, y x, y
use(before def) p y x k p, q, z

整个的计算思路和上一篇文章类似，只要沿着算法过程不断迭代就可以得到最终结果。对于def 和use(before def)的计算我特地按照B5->B1的顺序，是为了突出backward的思想。根据上面的表格结合算法，很容易计算得到每个BB的IN[B],OUT[B]。对于最终结果取如下栗子解释，100 1001表示x,p,k在此program point是live，其他都是dead，你不妨手动根据定义验证一下这个结论是否正确

image-20210327162508258

总结

本文着重讲解了数据流分析中的Live Variables Analysis，包括其定义与理解，分析过程（算法），实际例子，实际上这部分内容和Reaching Definition Analysis基本上是异曲同工，只不过将分析的对象从定义转换到了变量，因此，在文中很多对方，我会拿两者进行对比，并进行一些跳跃，如果有看不懂的地方，建议去B站仔细看看老师的授课视频，相信会有更深的体会。

这堂课带给我比较打的一个思考就是backward和forward的选择，这一点有点像背包问题中的正向循环（01背包）和逆向循环（完全背包）。当某一条路前进计算困难时，不妨逆向思考，倒着走或许会有惊奇的发现（当然思考不是随缘，是基于对定义的深度理解和剖析得到的）

至此，已完成数据流分析中两部分的分析内容，下一部分是Available Expresiions Analysis，当写完三部分内容后，会对三者进行一个对比总结。

参考

1 : 南京大学《软件分析》课程04（Data Flow Analysis II）_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili