‘壹’ 【课程笔记】南大软件分析课程4——数据流分析基础（课时5/6）
关于这一节 zcc 的笔记已经够完美了，我就直接在他基础上记录了。
上节课是介绍了3种数据流分析迭代算法，本节课将从数学理论的角度来讨论数据流分析，加深对数据流分析算法的理解。
本质 ：常见的数据流迭代算法，目的是通过迭代计算，最终得到一个稳定的不变的解。
定义1 ：给定有k个节点（基本块）的CFG，迭代算法就是在每次迭代时，更新每个节点n的OUT[n]。
定义2 ：设数据流分析的值域是V，可定义一个 k-元组 ： (OUT[n 1 ], OUT[n 2 ], ... , OUT[n k ])。是集合 (V 1 V 2 ... V k ) （幂集，记为V k ）的一个元素，表示每次迭代后k个节点整体的值。
定义3 ：每一次迭代可看作是V k 映射到新的V k ，通过转换规则和控制流来映射，记作函数F：V k V k 。
迭代算法本质 ：通过不断迭代，直到相邻两次迭代的 k-元组 值一样，算法结束。
不动点 ：当X i = F(X i )时，就是不动点。
问题 ：
定义 ：给定偏序集(P, )， 是集合P上的二元关系，若满足以下性质则为偏序集：
例子 ：
定义 ：给定偏序集(P, )，且有P的子集S⊆P：
最小上界 ：least upper bound（lub 或者称为join），用⊔S表示。上确界？
定义：对于子集S的任何一个上界u，均有⊔S⊑u。
最大下界 ：greatest lower bound（glb 或者称为meet），用⊓S表示。下确界？
定义：对于子集S的任何一个下界l，均有l⊑⊓S。
若S只包含两个元素，a、b（S = {a, b}）那么上界可以表示为a⊔b，下界可以表示为a⊓b。
都是基于上下确界来定义的。
定义 ：给定一个偏序集(P,⊑)，∀a,b∈P，如果存在a⊔b和a⊓b，那么就称该偏序集为格。偏序集中的 任意两个元素 构成的集合均 存在最小上界和最大下界 ，那么该偏序集就是格。
例子 ：
定义 ：给定一个偏序集(P,⊑)，∀a,b∈P：
当且仅当a⊔b存在（上确界），该偏序集叫做 join semilatice；
当且仅当a⊓b存在（下确界），该偏序集叫做 meet semilatice
定义 ：对于格点 (S, ) （前提是格点）的任意子集S，⊔ S 上确界和⊓S下确界都存在，则为全格complete lattice。
例子 ：
符号 ： = P ，叫做top； = P，叫做bottom。
性质 ：有穷的格点必然是complete lattice。全格一定有穷吗？ 不一定，如实数界[0, 1]。
定义 ：给定一组格，L 1 =(P 1 , 1 )，L 2 =(P 2 , 2 )，... ，L n =(P n , n )，都有上确界 i 和下确界 i ，则定义格点积 L n = (P, )：
性质 ：格点积也是格点；格点都是全格，则格点积也是全格。
数据流分析框架(D, L, F) ：
数据流分析可以看做是 迭代算法 对 格点 利用 转换规则 和 meet/join操作 。
目标问题：迭代算法一定会停止（到达不动点）吗？
（1）单调性
定义 ：函数f: L L，满足∀x,y∈L，x⊑y⇒f(x)⊑f(y)，则为单调的。
（2）不动点理论
定义 ：给定一个 完全lattice(L,⊑) ，如果f:L→L是 单调 的，并且 L有限
那么我们能得到最小不动点，通过迭代：f(⊥),f(f(⊥)),...,f k (⊥)直到找到最小的一个不动点。
同理 我们能得到最大不动点，通过迭代：f(⊤),f(f(⊤)),...,fk(⊤)直到找到最大的一个不动点。
（3）证明
不动点的存在性；
最小不动点证明。
问题 ：我们如何在理论上证明 迭代算法有解 、 有最优解 、 何时到达不动点 ？那就是将迭代算法转化为 不动点理论 。因为不动点理论已经证明了，单调、有限的完全lattice，存在不动点，且从⊤开始能找到最大不动点，从⊥开始能找到最小不动点。
目标 ：证明迭代算法是一个 完全lattice(L, ) ，是 有限 的， 单调 的。
根据第5小节，迭代算法每个 节点（基本块）的值域 相当于一个 lattice ，每次迭代的 k个基本块的值域 就是一个 k-元组 。k-元组可看作 lattice积 ，根据格点积性质：若L k 中每一个lattice都是完全的，则L k 也是 完全 的。
迭代算法中，值域是0/1，是有限的，则lattice有限，则L k 也有限。
函数F：BB中转换函数f i ：L → L + BB分支之间的控制流影响（汇聚是join / meet 操作，分叉是拷贝操作）。
总结 ：迭代算法是完全lattice，且是有限、单调的，所以一定有解、有最优解。
定义 ： lattice高度 —从lattice的top到bottom之间最长的路径。
最坏情况迭代次数 ：设有n个块，每次迭代只有1个BB的OUT/IN值的其中1位发生变化（则从top→bottom这1位都变化），则最多迭 ( n × h ) 次。
说明 ：may 和 must 分析算法都是从不安全到安全（是否安全取决于safe-aprroximate过程），从准确到不准确。
以 Reaching Definitions分析为例：
以available expressions分析为例：
迭代算法转化到lattice上，may/must分析分别初始化为最小值 和最大值 ，最后求最小上界/最大下界。
目的 ：MOP（meet-over-all-paths）衡量迭代算法的精度。
定义 ：最终将所有的路径一起来进行join/meet操作。
路径P = 在cfg图上从entry到基本块s i 的一条路径（P = Entry → s 1 → s 2 → ... → s~i ）。
路径P上的转移函数F p ：该路径上所有语句的转移函数的组合f s1 ，f s2 ，... ，f si-1 ，从而构成F P 。
MOP ：从entry到s i 所有路径的F P 的meet操作。本质—求这些值的最小上界/最大下界。
MOP准确性 ：有些路径不会被执行，所以不准确；若路径包含循环，或者路径爆炸，所以实操性不高，只能作为理论的一种衡量方式。
对于以上的CFG，抽象出itter和MOP公式。
证明 ：
结论 ：所以，MOP更准确。若F满足分配律，则迭代算法和MOP精确度一样 F ( x ⊔ y )= F ( x )⊔ F ( y )。一般，对于控制流的join/meet，是进行集合的交或并操作，则满足分配律。
问题描述 ：在程序点p处的变量x，判断x是否一定指向常量值。
类别 ： must分析 ，因为要考虑经过p点所有路径上，x的值必须都一样，才算作一定指向常量。
表示 ：CFG每个节点的OUT是pair（x, v）的集合，表示变量x是否指向常数v。
（1）D：forward更直观
（2）L：lattice
变量值域 ：所有实数。must分析，所以 是UNDEF未定义（unsafe）， 是NAC非常量（safe）。
meet操作 ：must分析， 。在每个路径汇聚点PC，对流入的所有变量进行meet操作，但并非常见的交和并，所以 不满足分配律 。
（3） F转换函数
OUT[s] = gen U (IN[s] - {(x, _})
输出 = BB中新被赋值的 U 输入 - BB中相关变量值已经不是f常量的部分。
对所有的赋值语句进行分析（不是赋值语句则不管，用val(x)表示x指向的值）：
（4） 性质 ：不满足分配律
可以发现，MOP更准确。F(X Y) F(X) F(Y)，但是是单调的。
本质 ：对迭代算法进行优化，采用队列来存储需要处理的基本块，减少大量的冗余的计算。
软件分析——数据流分析2
‘贰’ 数据流是什么怎么弄
您好，数据流计算机
【解释】： 由数据来驱动操作的电子计算机。机内所存储的程序指令不需顺序执行，当所需的操作数据完备时就立即执行。当多个操作同时满足条件时，它们可并行执行而不受程序指令顺序的限制，从而大大提高了计算机的运行速度。
1、确定系统的输入输出
由于系统究竟包括哪些功能可能一时难于弄清楚，可使范围尽量大一些，把可能有的内容全部都包括进去。此时，应该向用户了解“系统从外界接受什么数据”、“系统向外界送出什么数据”等信息，然后，根据用户的答复画出数据流图的外围。
2、由外向里画系统的顶层数据流图
首先，将系统的输人数据和输出数据用一连串的加工连接起来。在数据流的值发生变化的地方就是一个加工。接着，给各个加工命名。然后，给加工之间的数据命名。最后，给文件命名。
3、自顶向下逐层分解，绘出分层数据流图
对于大型的系统，为了控制复杂性，便于理解，需要采用自顶向下逐层分解的方法进行，即用分层的方法将一个数据流图分解成几个数据流图来分别表示。