这节课讲的是Data Flow Analysis更具体的说,研究的额是是：How data flows on CFG?
也就是在程序控制流图的基础上,如何对各种数据的流转进行分析
- Overview of Data Flow Analysis
- Preliminaries of Data Flow Analysis
- Reaching Definitions Analysis
- Live Variables Analysis
- Available Expressions Analysis
1. Overview of Data Flow Analysis
数据流分析是在Nodes(节点) Edges(边) CFG(控制流图)上的分析,围绕着这几个“数据类型”有两种分析思想 may analysis 和 must analysis,但是这节课只是提出和解释了概念,具体为什么要使用这两个思想以及他们怎么帮助我们找到最终的不动点的理论知识在下一课(涉及到离散数学中最小上界最大下界以及格,不动点等基础知识)
第一节课曾提到,做静态分析其实就是在做abstraction(抽象)和over-approximation(过近似),而over-approximation也可称为may analysis,大部分时候我们都是做的may,因为为了实现soundness嘛,我们首先追求的是尽可能多的“可能信息”,考虑尽可能多的情况;但是相对应的,有一些场景我们用到的是under-approximation(下近似),也称must analysis,这两种分析有不同的使用场景,也许后续我们会把它们结合起来,实现更多更高级的分析目标
- may analysis
- 需要尽可能全面的可能为真的信息(上近似)
- must analysis
- 输出必然为真 的信息（下近似）
2. Preliminaries of Data Flow Analysis
这里要介绍几个数据流分析中的概念,主要是program points 和transfer funtion
Program Points
program point 就是in[s]和out[s]这种points
数据流分析是为了找到一组对对于所有语句的IN[s]和OUT[s]的基于安全近似约束的解决方案
Transfer Function’s
- 基于语句语义（转移函数）的约束 - 基于控制流约束
数据流分析的两种方向,正向和逆向,把statement里的信息抽象为函数fs
正向由当前节点的in求out;逆向反之
Reaching Definitions Analysis
这里是没有cover到的两个部分
课程里不涉及这两个部分因为学完不会花很多时间就能学会这两个
这里举了一个例子,假如要检测变量是否都有定义,那么在入口处有一个dummy definition,相当于为每个未赋值变量赋值为未定义,如果某个地方引用到了一个未赋值的变量,那么说明有一条路径是从未定义的变量到这一点的,所以Reaching Definitions是检测可达性的不放过任何一条路径的may analysis
然后这里第一次展示了用二进制的01来表示每个definitions是否生效,非常简洁,后面两个算法也会用到这种形式,不过表示的含义不同,不再作介绍
如图,每个BB内会kill掉当前block种定义了的变量在其他地方的定义
boundary condition在这里的entry里应该按语义去设计算法,通常都为空
但是每个block的OUT[B]在不同算法里不同,所以这里没有对边界条件进行合并
然后对每一个有对out进行修改的地方进行一个对其每个block的transform funtion的约束
不断遍历直到没有任何变化
再回头看这两段话
gens和kills保持不变
当更多事实流入IN[S]时，”更多事实”要么 - 被杀死，或者
- 流向OUT[S]（幸存者）
当一个事实被添加到OUT[S]中，无论是通过gens还是通过幸存者，它将永远保留在那里
因此OUT[S]永远不会缩小（例如，0→1，或1→1）
由于事实的集合是有限的（例如，程序中的所有定义），必然存在一个迭代的轮次，在此轮次中没有任何事实被添加到任何OUT中，然后算法终止
这段的意思就是说out不变的时候in也不会变,in不变的话,kill和gen是固定的,那么out又不会变
所以算法最终会停止
Live Variables Analysis
live variables analysis有助于程序运行时,替换那些已经是dead的variable的寄存器
Live Variables Analysis 和Reaching Analysis的顺序是反过来的,是backwards的,又这两个公式推导每个node的IN[B]应该是什么
如果一个变量在block里有定义,就把IN里这个参数kill掉,如果用到了,就在IN里gen
总结
Available Expressions Analysis
可用表达式分析
如果所有从入口到程序点p的路径都必须经过x op y的计算，并且在x op y的最后一次计算之后，x或y没有被重新定义，则表达式x op y在程序点p是可用的。
这个定义意味着在程序点p，我们可以用x op y的最后一次计算结果来代替该表达式
可用表达式的信息可以用于检测全局公共子表达式。
要严格按照定义来判断某个是否Available
这个分析是must analysis,可以有漏报,不能有误报
可以少优化,不能优化错
