控制流与数据流分析.doc

第七章 控制流分析
优化需要从程序中获得足够多的信息。控制流分析就是用来获取程序控制结构信息的形式化分析方法，它是数据流分析，依赖分析的基础。

7.1控制流分析方法概述
7.1.1 过程内控制流分析方法主要有下面3种：
1．用dominator图找出循环，把循环标记出来供后面的优化使用。因为循环是程序中最值得改进的地方，所以这种方法广泛被现在的编译器采用。

2．Interval分析：这是一类分析方法的统称，用来分析单个过程的结构，并把它分解成为一系列有层次的结构称为interval。这些结构的层次关系可以用一棵树来表示，就叫控制树。接下来许多分析和优化就可以基于控制树来做。

3．结构分析：结构分析是Interval分析中的特别重要且有代表性的一种，而且它在许多编译器或优化方法中被用到，所以单独作为一种控制流分析方法。

这三种分析方法各有优劣之处，且三种方法并不是互相隔离的，具体实现时可以根据需求做出折衷选择。

7.1.2 控制流图和BB
上面三种分析方法都是基于控制流图(CFG)的基本单元BB来做的。因为控制流图和BB大家都知道，所以这里省略它们的基本概念。只是在识别BB的方法上补充一点：对call语句的处理。

对call语句的处理：一般情况下call语句调用目标过程后会返回call语句顺序的下一条语句。这时call语句和它顺序的下一条语句都不会被作为入口语句。但是，如果一个call语句有好几个返回地址(例如：Fortran中有alternate返回地址)，那么call语句的下一条语句就应该作为入口语句，否则BB中将有一条既不是顺序执行又不在BB末尾的指令。C库函数中的setjump( )和longjump( )也有类似情况。
Fortran
1 call…
2 …
3 …
…
n …
箭头所指都是入口语句

7.13 EBB
EBB与控制流分析的关系不大，只是因为刚介绍了BB，所以把EBB也顺带介绍一下。EBB跟BB相比可以使指令调度这种局部优化在选择指令时范围更宽。介召EBB之前先要知道join node

1. join node的概念：若一个节点不止一个前驱(随便有几个后继)，那么该节点就叫做join node。
2. EBB：除了第一个节点外，其余节点都不是join节点的最大CFG子图。(这里的第一个节点指的是唯一一个前驱不在该EBB之内的节点，其余节点都不是join节点因而只有唯一前驱，而且前驱属于该EBB之内，所以一个EBB就是以join节点为根的一棵树) 图可见《muchnick一书》p177 Fig7.8
完全对称的，我们可以有branch node和reverse EBB的概念，这里略。
3. 找EBB的算法：《muchnick一书》p176 Fig7.6 7.7
Build_EBB(r, succ, pred)：
作用：给定某个join node，求以它为根的EBB树。
思想：它调用Add_Bbs( )从join节点r出发在CFG上做深度优先搜索，若遇到非join节点就把它加入该EBB，然后沿该节点继续深度优先搜索；若遇到join节点就把它放入一个单独的集合EbbRoots里，然后控制返回它的父节点继续搜索。

Build_All_Ebbs(r, succ, pred)：
作用：找到CFG中所有EBB
思想：把CFG的根放入EbbRoots集合里，并把它作为r调用Build_EBB(r, succ, pred)；然后对EbbRoots中的join node队列依次调用Build_EBB(r, succ, pred)，得到所有EBB。

7.2 深度/广度优先搜索，前序/后序遍历
略

7.3 Dominators和PostDominators
7.3.1 dom，idom基本概念
dominate(简写为dom) 是一个二元关系，a dom b表示从CFG的entry节点到b节点的任意一条路径都会经过a节点。这时把a叫做b的dominator。
idom关系由dom关系得来，a idom b表示a dom b，且不存在节点c同时满足a dom c、c dom b。
由CFG的节点集N和idom关系构成的边集组成一棵树，叫idom树，这棵树反映了CFG上所有节点间dom和idom关系。

7.3.2 求dominator和idominator
求dominator的常规算法用的是迭代计算的方法，收敛结果即所求每个节点的domintor集合。该算法大家比较熟悉，略。
求idominator的算法要基于domintor算法的结果，用下图来简单阐述：Domin(n)-{n}
节点n
节点i
节点s

《muchnick一书》p184 Fig7.15
思想：任取节点i属于Domin(n)-{n}，固定i，依次检查Domin(n)-{n}-{i}中节点s，若s属于Domin(i)，则从Domin(n)中删除节点s，因为它不可能成为节点n的idominator了。检查完集合Domin(n)-{n}-{i}中剩余节点s之后，再改变节点i，继续上面做的检查。直到domin(n)-{n}集合中只剩一个节点，该节点就是节点n的idominator。
求Postdominator的算法与求dominator的算法对称，只要把算法Fig7.14中的pred函数改为succ函数就行了。

7.3.3 计算dominator的快速算法
该算法的详细介绍见Lengauer and Tarjan A Fast Algorithm for Finding Dominators in a Flowgraph
常规算法时间复杂度为O(n2 . e)，快速算法的时间复杂度为O(n . α(e,n)),α(e,n)是ackermann函数的倒数，增长非常缓慢。

先给一个定义sdom(w)：
sdom(w) = min{ u| 存在路径v0=u,v1,…,vk=w且vj>w (1<= j<= k-1) }
先对CFG作深度优先搜索，搜索树为T，里面的u，w，v1,…,vk都是T中先序遍历的访问顺序，后面经常就用这个顺序号来指代节点。

Sdom(w)表示: 节点u有路径到达w，且路径上除u之外的其它节点的序号都大于w。取CFG中满足这个条件且序号最小的u作为sdom(w)。
引入sdom函数的目的是由sdom可以计算idom(w)

因为算法比较复杂，不能几句话说清楚，所以先给个梗概。即我们首先会给出一些引理和定理，由它们得到sdom(w)的递推计算方法和基于sdom函数的idom(w)的递推计算方法，然后按照特定的顺序使用递推计算方法计算得到sdom和idom。引理和定理的意义不直观，可能需要了解证明过程才能清楚，可以查看上面的论文，这里只在附录中给出最重要的定理的证明。(引理1 2 3可以先跳过不看)

引理1：如果v,w都是G中的点，且v<=w,那么v到w的任何路径都要经过v和w在深度优先树T上的公共祖先。

引理2：sdom(w) --＋ w；idom(w) -- * sdom(w)
sdom(w) --＋ w表示在T上sdom(w)是w的祖先，且sdom(w)!=w
idom(w) --* sdom(w)表示在T上idom(w)是sdom(w)的祖先，且有可能idom(w)=sdom(w)。

引理3：如果v,w满足v --* w ,那么或者有v --* idom(w)或者有
idom(w) --* idom(v)。

定理1：假如w!=r
sdom(w) = min({ v| (v,w)属于E and v < w }∪{ sdom(u)| u>w and 存在边(v,w)并且满足u --* v })
定理1就是sdom(w)的递推计算式。

定理一的证明：
设X等于上面等式的右边部分
一：证明
如果且，那么，由sdom的定义和。
如果，u满足且且，则有路径l：从
到u，从u到v，从v到w。且到u上的节点的序号uw，从u到v的路径上的节点序号也是uw，所以
二：证明
，
设k＝1，即，且，由min式前半部分有x＝min。
若k1，则取j是满足的那个最小的j，假如有，则由引理一，存在是和的公共祖先，即，这与j的取法矛盾。所以
所以存在路径，一直到且路径上的点除了两端点外都大于等于，这说明，又
，所以

综合一二，可知。

定理2：如果每一个满足sdom(w) --+ u --* w的u都同时满足sdom(u) >= sdom(w)，那么idom(w) = sdom(w)

定理3：假设u是满足sdom(w) --+ u --* w并且使sdom值最小的那个u，那么u满足sdom(u) <= sdom(w)，且idom(w) = idom(u)

由定理2和定理3得到推论：
推论1：假设w!=r，u是满足sdom(w) + u * w并且使sdom值最小的那个u，那么有
idom(w) = sdom(w) if sdom(w) = sdom(u)
idom(w) = idom(u) if sdom(w) > sdom(u)
这就得到了基于sdom函数的idom(w)的递推计算式。

上面这些定理比较烦杂，有用的是定理1、2、3和推论，其它都是为了证明这些而给出的。

算法的步骤：
(1) 算法首先对CFG做深度优先搜索，按先序遍历次序给各个节点编号。
(2) 按照递减次序，用定理1计算各个节点sdom函数值
(3) 按照递减次序, 用推论1计算各个节点的idom函数值，这里要说明的是推论1计算idom函数值分两种情况，第一种情况下计算idom(w)时sdom(w)已经得到，对应于下面图1的step3；而第二种情况下计算idom(w)时idom(u)还没得到，这时idom(w)中记录序号u，等递减遍历完成后，再进行一次序号递增遍历，这时idom(u)的值一定会在idom(w)之前被计算出来，用idom(w)=idom(idom(w))就能得到idom(w)的值，对应于图1中的step4。
第(2)步比较复杂，把它拿出来讨论。
我们打算用semi函数来表示sdom函数，但semi函数在算法各个阶段表示的含义不完全相同。Semi(w)值在(1)之前都为0，在(1)之后等于w，在(2)之后等于sdom(w)。第二步每计算完一个节点的semi函数值，就在该节点和其T上的父节点之间连一条边，这样我们得到一个森林<F>。还要引入一个eval函数，有了eval函数我们可以简化sdom函数的计算。

eval(v)：如果v是森林<F>中某棵树的根，eval(v)=v；否则取v所在树的根结点r，在r到v的树干(不包括r)上找semi值最小的节点u，eval(v)=u。
有了eval函数之后，我们把定理1的sdom函数计算式简化为
semi(w)=min{ semi(eval(v))|(v,w)∈ E} E为CFG的边集。这样我们只要得到w的所有前驱的eval值a，并算出所有semi(a)并从中取最小值，就得到了semi(w)。

对应于下图算法的step2
图1：
图2：

数字表示深度优先搜索序号，括号内的左边字母表示该节点的sdom节点，右边表示idom节点。

计算的例子：
以图2为例，说明semi(E)和idom(w)的求解，其中semi(w)=E节点的父节点
当step2 i＝3时，处理节点E，pred(E)有B和L，eval(B)=B,eval(L)=A,semi(B)=2,semi(E)=3,semi(A)=1；
所以semi(E)=min(semi(B),semi(A),semi(E))=semi(A)=1，即节点R。
这时E在T中的父节点B被加入森林中，假如semi(w)=B,那么计算idom(w)的条件就已经具备。由图2看出semi(D)=B,由step3，eval(D)等于A，semi(A)<semi(D)所以idom(D)=A。等到step2,3的for循环完成，此时计算出了idom(A)=R,转到step4，idom(D)=idom(idom(D))=idom(A)=R，这样就计算出了idom(D)。

7.4 循环和强连通部分
自然循环的定义和通过回边找自然循环的算法大家都很熟悉，略
7.4.1 强连通部分的概念
强连通部分：CFG中的一个子图，其中任两节点之间都互相有路径可以到达对方。
最大强连通部分：强连通部分A，A不是任何一个强连通部分(除A本身之外)的子图。

7.4.2 计算最大强连通部分的算法
先给一个定义：
式一：
lowlink(x)= min({ w|(x,w)属于E，w属于x所在的SCC且 x>w}
并{lowlink(w)|(x,w)属于E且 x<w}并{x})

lowlink(x)＝y的含义：节点y是从节点x出发，经由最多包含一条回边或一条cross边的路径，能到达的序号最小的，x所在SCC中的点。

由式一可知：在深度优先搜索树上作一次后序遍历，只要依次对节点x的前驱的序号(x>w时)或前驱的lowlink值(x<w)做比较，我们就能计算出所有节点的lowlink。

Tarjan给出了一个定理：如果x＝lowlink(x)，那么x一定是它所在的最大强连通部分当中序号最小的点，也是深度优先搜索树上该最大强连通部分形成的子树的根。

这里简单证明一下：设x＝lowlink(x)，假如有节点y!=x，x与y同属一个最大强连通部分且有y<x，那么一定有从x到y的路径，取z为从x到y的路径上第一个序号小于x的节点(至少有y这个节点，所以一定可以找到),因此lowlink(x)<=z<x，这与假设矛盾。所以x一定是它所在的最大强连通部分当中序号最小的点。反过来，因为lowlink(x)是x由最多一条回边或一条cross边能到达的序号最小的x所在SCC中节点，而x本身就是x所在SCC中序号最小的点，所以x=lowlink(x)。

算法见《muchnick一书》p195 Fig7.26
算法思想：
Strong_Components(x, Succ)的作用：如果节点x是最大强连通部分中序号最小的节点，就可以得到x所在最大强连通部分，并把该最大强连通部分加入All_SCC。

步骤：首先在深度优先搜索树上做后序遍历，求出节点x子树中所有节点的lowlink，算法中的stack存放以x为根的子树中的一些节点(x所在最大强连通部分中的节点一定在栈中)。如果lowlink(x)=Dfn(x) (即lowlink(x)=x，我采用这种简单表示法，虽然有点不严密)，则把栈中x以上一直到栈顶的元素(包括x)全部弹出，放到SCC集合中。SCC集合中的节点就是x所在最大强连通部分的所有节点(*)。

把(*)再说明一下：假设栈中x以上的部分有不属于x所在最大强连通部分的节点v0，一定有lowlink(v0)=v1，lowlink(v1)=v2……lowlink(vk)=vk。如果vk是x为根的子树中的节点的话，按照算法(if Lowlink(x)=Dfn(x)…)，它应该和v0一起已经被从栈中删掉，这与假设矛盾；如果vk不属于x为根的子树，那x有路径
从xàv0àvk，设vj是路径上第一个不属于以x为根的子树的，这样lowlink(x)<vj，而vj<x，这与lowlink(x)=x矛盾。所以栈中x以上的元素都属于x所在最大强连通部分。反过来很容易看出x所在最大强连通部分中的节点一定在栈中x以上的位置。两方面综合起来，得到(*)。
如果上页提到那个问题确实存在的话，最大强连通部分的最小序号节点3的lowlink(3)＝2，这时不退栈。到遍历到节点2时，有lowlink(2)=2，这时退栈，把2、3、4、5算作一个最大强连通分量，这就不对了。

7.5 可规约性
概念：流图G是可规约的当且仅当不存在两个或两个以上入口的强连通子图。

绝大多数的程序设计语言由语言本身语义保证了不出现不可规约的流图。在Fortran77中90％的程序都是可规约的，即使是叫一个不懂结构化编程思想的人用goto语句编程，得到的程序大部分也都是可规约的。在不可规约区域上，像代码外提、规纳变量删除等许多优化就不能做了。

虽然不可规约程序出现很少，但仍然要考虑。解决办法有：
1． 做迭代数据流分析。这是最通用的方法。
2． 节点分裂。节点分裂可以使不可规约流图变成可规约流图，但同时流图中的节点数会指数级上升。
3． 在格上做迭代。这个会在后面数据流分析部分讲到。

7.6 interval分析和控制树
interval分析是一类分析方法的统称。它们的主要思想都是通过在流图上分析某些节点和它们之间的前驱后继关系，识别出控制流图中某些结构，把这些结构塌缩成一个点(同时维持好该节点与流图中其它节点的边),然后再去识别其它结构，一直这样做下去做到不能做为止，最后得到流图一系列有层次的结构，每一个这样的结构就叫做一个interval。

Interval的层次结构可以用一棵树来表示，这棵树就叫控制树。
1．控制树的根是代表整个流图的一个抽象图(塌缩做到不能做的时候的流图叫抽象图)
2.控制树的叶子是基本块(最初流图中的所有节点)
3.非根非叶节点是抽象点(由某个结构塌缩后得到的那个节点叫抽象点)
4.把抽象点和它所代表的结构(或者叫域)中所有节点都连上一条边

几种interval分析方法：
1. T1－T2分析：这是最早也是最简单的interval分析方法，它仅仅识别两种结构

识别出流图中横向箭头左边的结构，把它塌缩成右边的节点，然后继续在改变了的流图中找这样的结构。

举一个T1－T2分析的简单例子：

例如节点B1a和B3b构成一个T1型的结构，把它塌缩成B1b节点，控制树上分别连上B1b到B1a、B3b的边。

2. maximal interval分析
maximal interval分析只识别一种结构：极大单入口子图，且该子图必须满足子图中所有闭合路径都经过唯一的入口。注意：maximal interval分析不能处理不可规约的区域。例如：
B1
B2
B3

如果满足单入口条件，B1必须纳入B2、B3所在区域内。但纳入之后，该区域又不满足所有闭合路径都经过唯一入口的要求。因为B2、B3组成的回路不经过节点B1。

3. minimal interval分析
把流图中以下三种结构识别为minimal interval。Minimal interval分析可以一直做到整个流图只剩一个节点。
1. 自然循环 2. 极大非循环子图 3. 最小不可规约区域(包含所有入口的最小强连通子图)
例子见《muchnick一书》p201 Fig7.33、Fig7.34

7.7 structural分析
Rosen发明了语法制导的高层数据流分析方法，能够识别高级语言的语法树上的特定结构，并给出该结构上数据流分析的公式，从而避免迭代计算。现在structural分析相当于把这种分析方法搬到中间代码，试图在中间表示级识别某些结构，以加速数据流分析。Structure分析是interval分析方法中的一种。

structural分析与上一小节提到的几种interval分析方法有两个明显差别：
1．Structure分析识别的结构类型比前面提到过的interval分析方法都要细致
得多。
2．Structure分析中识别的每一个结构(或者叫域)都只有一个入口，因为不可
规约区域不止一个入口，那就必须把这多个入口的lowest common dominator
加入该域。使这个dominator成为该域的唯一入口。
Structure分析识别的结构类型见《muchnick一书》p203 Fig7.35 Fig7.36
Structure分析作用在中间代码上，这时已经通过了编译器前端的语法分析，
去掉了不符合程序规范的控制结构，剩下来的都是符合程序规范的规则的结
构。任何一种结构都可以在Fig7.35 、Fig7.36中找到所属的类别。

算法思想：
Acyclic_Region_Type(N,E,node,nset)：给定流图上节点node，看node是否是
某一个非循环结构中的节点。如果node确实属于某个非循环结构，那由nset
返回该结构中所有节点。

具体判断方法是：该节点若只有一个前驱，而该前驱只有一个后继，那它们
同属于一个block shema(见Fig7.35)，然后继续看那个前驱是否也只有一个
前驱，该前驱是否也只有一个后继….直到找到该block shema中所有节点为
止。如果node节点不属于block shema，那再看它是否刚好有两个后继，如
果是，再用类似办法(检查相应节点的前驱后继情况) 看它是否属于if then
else或者Case或者proper。

Cyclic_Region_Type(N,E,node,nset)：与Acyclic_Region_Type(N,E,node,nset)
的作用和判断方法非常类似，它查看node是否属于某个循环结构。
在循环结构是自然循环的情况下，Structural_Analysis过程中的ReachUnder集
合收集了自然循环中所有的节点；如果是不可规约循环，节点n如果是不可规
约循环的一个入口，那么就将把整个强连通分量都放到ReachUnder集合里，而
且把不在强连通分量中，而是通过其它入口能够到达节点n的那些点也放入
ReachUnder集合。那么在Cyclic_Region_Type过程中，如果发现node节点不是
循环结构唯一入口（判断依据：不可规约循环情况下，n节点与其它入口节点引
入的节点之间没有边可到达），那么可以断定该循环是不可规约循环，这时调用
Minimize_Improper过程。

Reduce(N,E,rtype,NodeSet)：把某一个结构塌缩成一个节点p，调用replace( )
函数使原来结构中的点和其他点之间的边改成p与其它点之间的边。同时在
StructureType，Structures，StructNodes，StructOf中记录下该结构的信息。

Minimize_Improper( )： 首先用MEC_Entries过程找出nset集合中不可规约循环
的所有入口，再用NC_Domin过程找出这些入口的最近公共dominator，最后把可
以不经过这个dominator节点到达强连通分量的节点也加入这个improper region。

Structure_Analysis(N,E,entry)：给定流图<N,E>和流图入口entry，对该流图
进行结构分析。

步骤：首先调用DFS_Postorder( …)记录下后序遍历的顺序。
按后序遍历顺序依次查看各个节点，调用Acyclic_Region_Type函数看该节点是否属于某个非循环结构。若是，继续查看其它节点；若否，调用Cyclic_Region_Type函数看该节点是否属于某个非循环结构。

具体例子见：《muchnick一书》 page211 Fig 7.46

第八章 数据流分析
数据流分析的目的是提供过程怎样操纵数据的信息。数据流分析包含范围很广，从简单分析到复杂的过程的抽象执行都属于数据流分析的范畴。
数据流分析的两个原则：1 数据流方程的解必须是实际正确信息的一个保守的近似。2 在保证正确性的条件下，尽可能的激进，使提供更多信息，以求从优化中获得更多好处。
有一些概念大家都很熟悉，例如什么是Gen、In、Out…，所以略掉。
说明一下：通常的迭代数据流分析方法大家都很熟悉，这里侧重一些迭代分析的理论根据，但是书上在讲这方面内容时许多关键部分只是说了结果，没有解释原因，我也只好大概跟着书上的思路走，有些地方我找到了原来论文给出了解答，有些地方按我自己的想法给了解释。但许多地方究其原因还是不甚了了，所以说明一下，请大家看的时候注意，有想法请和我一起讨论。

8.1 数据流分析模型：
Geni，Killi，Ini，Outi都叫数据流属性，它们的值叫数据流信息。

8.1.1 数据流分析的限制(以可用表达式分析为例)：

由上面数据流分析的限制可以得到数据流方程。
只要把的号改成等号，并且把中的改成等
号。注意：对于nondistributive的数据流分析来说，把的号改成等号可能会造成数据流信息丢失。

对照《Handbook》p7 Fig1.2
先给一个可用表达式数据流属性列表，这个表现在不用看，下面用到时再查。
（前面加的Av表示可用表达式）
表一
Nodei AvGeni AvKilli fi(x)
1 {e1} {e2,e5,e6,e7,e8} {e1}(x-{e2,e5,e6,e7,e8})
2 {e2,e3} {e3,e4} {e2,e3}(x-{e3,e4})
3 {e4} {e5,e6} {e4}(x-{e5,e6})
4 {e4} {e5,e6} {e4}(x-{e5,e6})
5 {e8} {e2,e7,e8} {e8}(x-{e2,e7,e8})
6 x
8.1.2 几组数据流方程的解：
以下是由上面的可用表达式数据流属性得到的几组数据流方程的解，来看看
它们有什么不同。
1. ，这组解表示没有任何表达式在程序任何点可用，虽然这组解看起来不对，但是它完全符合上面说到的数据流分析的限制。如果我们用这组解来指导公共子表达式删除，它不会错误地更改程序本来的语义。这是一组安全的赋值。
2. （U代表表达式的全集）显然这组解是错误的，而且如果用这组解来指导公共子表达式删除，它会错误地更改程序本来的语义。这是一组不安全的赋值。
3. node AVIn AVOut
1 {e1}
2 {e2,e3}
3 {e2,e3} {e2,e3,e4}
4 {e2,e3} {e2,e3,e4}
5 {e2,e3,e4} {e3,e4,e8}
6
这组解也符合上面的限制，但是我们注意到表一中e1在节点1中计算后在任何节点都没有被kill掉，所以这组解不是最大的一组解。
4. 3. node AVIn AVOut
1 {e1}
2 {e1} {e1,e2,e3}
3 {e1,e2,e3} {e1,e2,e3,e4}
4 {e2,e3} {e1,e2,e3,e4}
5 {e2,e3,e4} {e1,e3,e4,e8}
6 {e1} {e1}
这组解是最大安全赋值，给这组解加任何表达式都会违反数据流分析的限制。
一组安全赋值代表了数据流分析的一组有效解，我们最想要的是这些有效解中的最大一组，叫做MSA(maximum safe assignment)。MSA又叫MOP(meet over paths)。
仍对照《Handbook》p7 Fig1.2，按照数据流分析的限制，我们有
过程一：
，而又可以有

所以，稍微推广一点来看，有
（），
如果把改成＝，那就属于MSA，因为考虑了控制流所有可能经过的路径，是符合所有数据流分析限制的解中的最大值。

如果所有流函数都单调(单调概念在格理论中介绍)，而且数据流属性的可能值又有限的话，只要取中有限路径就可以得到MSA的解。

大家都很熟悉我们通常使用的迭代数据流分析方法，迭代数据流分析方法得到的是最大固定点赋值（MFA），但最大MFA可能与MSA不同，产生的原因来自于合流算符，它可能会使一些有用信息丢失。《Handbook》p18 1.3.6.2.1就举了一个常量传播的例子：原本知道z＝x＋y的结果是常量10，在合流之后反而认为z的结果不是常量了，这是因为常量传播是nondistributive，z是不是常量要取决于其它的变量。

8.2 格、流函数和固定点的理论
8.2.1 格的基本概念
我们首先将建立格的框架，在这个框架中的元素代表了程序中变量、表达式、
或程序结构的抽象属性。并且这些属性必须与程序的执行情况相独立，不会
因为程序中某个条件执行而改变。即数据流分析是不考虑程序具体执行时某
个条件的真假的，即使该条件一直是真或一直是假。

流函数则是格上的元素到元素的映射，这种映射代表的是程序中具体结构在程序中所起的作用。

我们仅讨论半格。
什么是半格：半格就是一个二元组，， 表示一个集合，计算中
两个元素的最大下界。由 我们可以定义部分序关系，。
如果存在两个特殊元素最大元素和最小元素，则半格叫做完全半格。

8.2.2 迭代数据流分析怎样会收敛
单调的概念：给定流函数h，如果满足：任意元素x、y属于，若xy且
h(x) h(y)，那么函数h单调。如果x与h(x)可比较的话，函数单调加上格
中元素有限这两个条件就可以保证格上的迭代数据流分析一定收敛。因为
x，h(x), h(h(x))…可以组成一个chain，它是单调增或者单调减的。

我认为这里的流函数(在格上讨论的流函数)应该把它认为是与程序的一次迭代相联系的函数，它的自变量和因变量都应该指的是程序中同一个点的流信息状态，而不是那种通常的与某个基本块或某个结构对应的流函数f： 自变量是in(B)，因变量是out(B)。

一般情况下，流函数h的自变量与因变量是可比较的，因为迭代数据流分析的初始值大都设为最小值或者最大值(例如到达定制初始设为空，可用表达式初始值设为全部表达式U)，而和跟半格上任何元素都可比，所以h()与可比，再由单调性就有h()与h (h())也可比，…这样形成一个chain。

但对于常量传播来说，流函数h的自变量与因变量就是不可比较的，因为常量传播的格元素不是通常用的bitvector (如果用bitvector，那bitvector将是无限长)，它的格叫ICP。中间一排点分别代表变量的值，从负无穷到正无穷。

假如有z＝z＋1的循环计算，那每次计算完z的值都加1，因变量仍然属于中间一排的元素，只不过加了1，因此自变量与因变量不可比较。下图就是ICP。

8.2.3 Distributive函数
如果h满足，则函数h是distributive函数。因为按照迭代数据流分析，我们不断地要做类似的合流操作，在8.2.1中已经举过一个常量传播的例子，合流操作可能会导致有用信息丢失。如果流函数有distributive性质的话，就能够保证在做合流操作时，有用信息不会丢失。

我们想要的数据流分析的解是MSA(或者叫MOP),
MOP = 对于path(B)＝entry,B1,…,Bn=B ，p是从程序入口到节点B的任意路径，Fp就是这个路径的流函数(注意与格上讨论的流函数相区别)，所有这些流函数作用在初始数据流信息得到值，MOP即对这些值做合流得到的结果。

但是，我们通常做数据流迭代只能得到MFA(最大固定点赋值，8.1最后提到过)，计算MFA就要按每迭代一次就要作一次合流。合流可能造成有用信息丢失，所以MFA可能不等于MSA，但是如果有了distributive性质，MFA就能保证等于MSA了。
在Kild73 A Unified Approach to global program analysis有详细证明，有
兴趣的可以参考那篇论文，这里说个大概做法，：
从两个方向证明MFA(B)<=MOP(B)，MOP(B)<=MFA(B)
证明第一个方向只要证明任意一条从entry到B的路径p，MFA(B)<=。用对路径p的长度做归纳。证明第二个方向只要对合流次数作归纳。

8.2.4 Bit Vector函数
先给bounded函数空间的定义：循环结构作数据流分析时，该结构对应
的流函数f可能会发生任意次作用f*。而在一个k-bounded函数空间里，f*=
如果数据流信息能用位矢量的形式来表示的话，该数据流分析的流函数就有很好的性质：例如单调、distributive且各个变量数据流信息独立。除此之外，位矢量的函数空间是2－bounded，即f*=，这一点在后面把structural分析用于数据流分析时，非常有用。f*=式的原因在于位矢量的每一维都只有0和1两种取值，且f把矢量哪一维变成0、哪一维变成1是固定的。举个例子：In(B)经过f作用一次以后得到f(In(B))，相当于（0011…）变成了（1001…），f(In(B))与In(B)合流之后得到(0001…)，再经过f作用仍然会把第一位的0变成1，把第三位的1变成0，得到(1001…)，这与f(In(B))相同。

8.3 基于控制树的流分析
如标题所示，这种分析方法主要基于控制树。一般对控制树做两次遍历，