前言

上一篇【静态分析】数据流分析-Part II - 求索 对数据流分析中的Live Variables Analysis进行了详解，用于查找used/unused variables，本文继续第三部分内容（也是数据流分析的最后一部分内容）——Available Expression Analysis。主要内容包括：

• Available Expression Analysis的定义和理解
• Available Expression Analysis算法设计与详解
• 举个栗子
• 数据流分析中的三种分析方式对比
• 总结

读完本文回对数据流分析Available Expression Analysis

内容有一个初步的了解，解答是什么，怎么做，效果怎么样三方面的问题，同时作为最后一篇数据流分析的文章，会将前面两个部分与本文内容做一个整体的总结，以表格形式对比三者，加深对数据流分析三种分析方式的理解。

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

Available Expression Analysis

即可用表达式分析，首先明确分析对象是表达式，类似x op y这种，下面看一下定义：

对于给定的一个program point p，表达式可用的前提是：

1. 所有从entry到p的路径都必须经过对该表达式x op y的执行（也即该路径上必须至少出现一次该表达式）
2. 在表达式x op y 最后一次执行之后，没有对x，y的重定义

用人话解释一下就是，在程序的某一阶段program point p，我们打算直接用某个变量去替代一个表达式了（避免多次计算），这就需要保证该表达式中涉及的变量没有发生变化（前提2），同时所有路径的表达式都要出现过且应该要一致（前提1），这样就能保证该变量与表达式计算的值是一致的。

看一下下面的例子：

程序块输入IN={a+b}，经过执行a=x op y后，添加新的表达式x op y到输出中，同时因为a被重定义了，所以表达式a+b从集合中去除，最终结果输出OUT={x op y}

同样，针对Available Expression Analysis，也要明确Abstraction,Transfer Function,Control Flow。

Abstraction

对象是表达式，没得说了，假设有表达式E1,E2,...En，则定义1表示available，0表示unavailable，易得bit vector表示：000..000

Transfer Function

在前面的例子中已经体现出了transfer function的核心要点：

1. 将新的表达式$gen_B$加入输出中
2. 从输出中去除含重定义变量的表达式$def_B$

因此，显然有：

$$OUT[B] = gen_B \bigcup (IN[B]-def_B)$$

关于先gen还是kill，就看语句的执行书顺序，例如：

# e.g. 1
x = x + y  # 先gen x+y，又因为x被redefined，kill x+y

# e.g. 2
a = x + y  # kill a的表达式
c = a + b  # 新生成a+b

Control Flow

这一块和之前两种分析方式都不一样了，因为根据定义，所有的path都应该要有该表达式的执行（假设存在一条路径没有，那么一旦执行到这条路径，某变量和表达式的值就不一定相等了），因此从多输出聚合到输入的过程中，应该采用交集：

$$IN[B] = \bigcap_{P\ a\ predecessor\ of\ B}OUT[P]$$

Available Expression Analysis 算法设计

有过前面两次的设计经验，这部分应该驾轻就熟了，输入输出都是差不多的，需要特别明确的一点是初始化的部分：

1. 一开始所有的expression都应该是unavilable，所以对$OUT[entry]=\phi$
2. 对所有OUT[B]就不一样了，因为前面说到我们要对所有前驱输出做交集得到下一BB的输入，如果初始化的时候前驱BB都是0，那意味着结果一定都为0，这样就没有起到对IN[BB]的更新效果，因此，除entry外的BB初始化$OUT[B] = \cup(1)$

其他的实际上和Reaching definition analysis没什么差别，循环迭代直到OUT不再产生变化，具体算法描述如下：

举个栗子

下面通过一个具体的样例来加深对算法过程的理解，与之前一样，受限于文章内容，只给出初始和结束状态：

• 起始：假设某CFG如下：

左上角是程序中出现的表达式

• 结束

整个过程实际上基本上和Reaching Definition Analysis十分相近，只不过在初始化和Transfer Function,Control Flow的表达式上不同

三种分析方式对比

下图展示了Reaching Definition Analysis, Live Variables Analysis, Available Expression Analysis三种分析方式的对比：

	Reaching Definitions	Live Variables	Available Expressions
Domain(分析对象)	definitions	variables	expressions
Direction(分析方向)	forward	backward	forward
May/Must(存在/全部)	may	may	must
Boundary(边界)	$OUT[entry]=\phi$	$IN[exit]=\phi$	$OUT[entry]=\phi$
Initialization(初始化)	$OUT[B]=\phi$	$IN[B]=\phi$	$OUT[B]=\cup$
Transfer Function	$OUT[B]=gen_B\bigcup(IN[B]-kill_B)$	$IN[B]=use_B\bigcup(IN[B]-def_B)$	$OUT[B]=gen_B\bigcup(IN[B]-def_B)$
Meet($\cup/\cap$)	$\cup$	$\cup$	$\cap$

总结

本文着重讲解了数据流分析中的Available Expression Analysis，包括其定义与理解，分析过程（算法），实际例子，该分析使得在编译优化的过程中可以避免对大量表达式进行重复计算，大大提升程序效率，文末还对现有的三种分析方式进行了对比。

至此，数据流分析的三种分析已经全部结束，当然这些尚处于理论层次的理解，还需要通过实际的动手分析锻炼后才能将这些内容融会贯通，后续会添加我的手动实践笔记到博客中。

参考

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