【静态分析】数据流分析-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),则认为vlive,否则就是dead

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

image-20210327143037134

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

Live Variables Analysis有什么作用呢?

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

Live Variables AnalysisReaching 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 plive的。

后面依然针对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 AnalysisControl Flow也是取$\bigcup$ ,只不过由于是backwardOUTp[B]变成求所有后继节点IN[S]的并集:

上面对Transfer FunctionControl Flow的解释多用文字,因此配上一张老师提供的例图来加深理解:

image-20210327154929253

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

Live Variables Analysis 算法设计

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

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

综上,结合Transfer FunctionControl 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

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

image-20210327162508258

总结

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

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

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

参考

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