数据流分析 学习笔记

学习CSCD70 和 南京大学《软件分析》课程中数据流分析部分的笔记与思考.
ps: 本篇有许多个人观点,如有错误虚心求教.

中间表示 IR

静态单赋值 SSA

静态单赋值（SSA），就是让每次对变量x赋值都重新使用一个新的变量xi，并在后续使用中选择最新的变量.
在控制流汇入同一个块时,导致多个变量备选,则使用合并操作符(phi-function),根据控制流的信息来决定选择哪个变量.

Basic Blocks & Control Flow Graphs

控制流分析（Control Flow Analysis）通常指的是构建控制流图（Control Flow Graph, CFG），并以 CFG 作为基础结构进行静态分析的过程。

可用表达式,活跃变量,到达定值

一个易错的例子.

经典的数据流分析算法,以到达定值为例.

关于数据流算法的理解,我认为为除entry以外的Basic Block赋初值是无意义的,只是为了便于算法的表示和实现,所以赋予的初值应该对结果无影响.

比如ForwardAnalysis中,一个基本块的前驱在分析该基本块时还没有分析过(循环),为了分析该块,应该引入一个对结果无影响的Out,即Top(原因后续解释).

Foudation

Iterative Algorithm, Another View

给定有K个结点的CFG,每次迭代中每个结点产生一个OUT值,一次迭代中所有结点的OUT值的集合定义为k-tuple.每次迭代是对k-tuple执行TransferFunc,如果两次迭代输出的k-tuple相同,算法停止.

Partial Order 偏序

poset 偏序集

pair(一个集合P,一种在P上的偏序关系),称作偏序集.
偏序关系: 自反性,反对称性,传递性

偏序关系与全序关系的区别在于，全序关系可以让任意两个元素比较，而偏序关系不保证所有元素都能进行比较.比如偏序关系为substring, si substring sing, ng substring sing, 但si和ng不能进行比较(注意 比较 和判断比较是否为真的区别).

Upper and Lower Bounds 上下界

上下界是相对于子集S来说的.如果取子集S == P,该上下界为偏序集的上下界.
并不是每个偏序集都有 lub 和 glb，但是如果有，那么该 lub, glb 将是唯一的

Lattice 格

给定一个偏序集，如果任意两个元素 a, b 都有 lub和glb，那么这么偏序集就叫做 格（lattice).只存在其中一个就是半格.
全格: 任意一个集合,都有lub和glb.
在全格中,一定有一个最大元素Top,最小元素Bottom.注意这里的大小不是直观上的,而是偏序关系的一种形象化表述. 南京大学的软件分析课程在Top和Bottom的定义上似乎与CSCD70有冲突,目前我个人倾向于认为Top和Bottom由偏序关系决定,偏序关系由Meet操作体现,南京大学的课程将Union操作认为是Join,而CSCD70认为Union也是Meet的一种,而Meet和Join分别表示最大下界和最小上界,所以这样的差异导致了两种观点中may analysis在lattice上的移动方向不同.但哪一种是正确的还有待进一步了解,如若有师傅愿意指点一下,感恩!

下图来自CSCD70.

有穷的格一定是全格,全格不一定有穷(0,1之间所有实数的小于等于关系).

Data Flow Analysis Framework via Lattice

数据流分析框架(D,L,F)
D:direction for data flow
L: Lattice -> pair(domain of values V ,meet or join).
F: a family of transfer function.
数据流分析: 在 lattice 的值上迭代地应用转移方程和 meet/join 操作符.

Monotonicity and Fixed Point Theorem

基本概念

这张图里单调性的第二种表示看着有点抽象,解释一下,相当于: f(z) ≤ min( f(x),f(y) ),其中z ≤ min(x,y).

不动点存在性证明:
(其实感觉只是用到了半格的性质,如果用全格的性质加单调性可以直接推F(TOP)=TOP ?)

最小不动点证明.

Relate Iterative Algorithm to Fixed Point Theorem

待理解:
每一个结点的OUT的值域是一个Lattice,数据流分析的Lattice是所有上述Lattice的Product.由于一个结点的OUT值域是finite的(Lattice是一个集合,finite指集合的元素有限),所以Product Lattice也是finite的.
至于单调函数,应该从宏观上理解,包含transfer function和join/meet function,输入是上一次迭代的Product Lattice,产生一个新的Product Lattice.(下图的左上方)

Transfer function是单调的,因为其的kill集和gen集仅与指令本身有关而与Input无关,单调方向与Input变化相同.Input变化由join/meet function决定.

When Will The Algorithm The Fixed Point?

最坏情况h*k是假设每次迭代只使得一个结点的OUT下降或上升一个高度,但其实不是很理解这种情况如何产生,如何在一次迭代中仅影响到一个结点的OUT?OUT改变意为IN改变,而IN不就是另一个结点的OUT么?

May/Must Analysis, A Lattice View

MOP

常量传播,稀疏条件常量传播

单个变量可能值域的Lattice设计为这个样子(回想一下,之前使用的Bool的值域其实也是一个Lattice)

Transferfunc像这样.有一点需要注意,之前所说的数据流分析中TranferFunc的单调性依赖于其gen集,kill集与输入无关这一性质,所以OUT与IN成正相关(相对于偏序关系来说).但这里的TransferFunc的gen集明显受到IN的影响,不过分析一下可以发现gen集同样与IN正相关,所以最终的OUT还是正相关的.

Lazy Code Motion

这个就比较复杂了.先放方法和定义,下面再解释.

目标 :
所有不复制代码就可消除的冗余计算都被消除
优化后的代码不会执行源程序中不执行的任何计算
表达式的计算应该尽量靠后, 利于寄存器分配

第一步计算预期执行表达式(绿色部分代表可预期执行),根据可预期执行的定义,在这些点放置表达式不会执行源程序中不执行的任何计算,且计算结果正确. 这是放置的正确性.

第二步计算(将要)可用表达式,是假设在刚刚预期执行表达式分析结果为True的所有点放置对该的表达式计算后,再进行字面意义上的可用表达式分析(金色部分代表可用).

此时预期执行表达式-可用表达式得到的便是最有效的放置点.在被预期执行但不可用的所有点放置该表达式的计算,最小化了放置的数量,且使得刚刚通过假设所有预期执行点放置计算之后的可用表达式的分析结果成立. 这是放置的有效性. 最有效的放置点集合为Earliest.

其实到这里已经完成了从部分冗余表达式到完全冗余表达式的转换,可以完成消除,但还不够完美.因为在Earliest的点放置表达式的计算,意味着表达式的生命周期最长,需要占据寄存器的时间就越长,所以接下来应该尽可能将放置推迟.

最多能推迟到什么地方呢?答案很明显,推迟到表达式的值被使用之前.(黑色部分代表可后延)

最后求Latest集合的公式: 前半部分是可放置的点,后半部分是边界条件,And之后得到最晚的可放置的点.

(也许第一幅图里的Postponable少了个.inB

最终结果:

涉及到的数据流分析: