Iterative Algorithm

对于一个含 $k$ 个节点的CFG，每个迭代算法对于每个node $n$ 更新$\mathrm{OUT}[n]$。
假设迭代算法的研究对象（domain）是$V$，定义一个k元组
$V^k=\left(\mathrm{OUT}\left[\mathrm{n}_{1}\right], \mathrm{OUT}\left[\mathrm{n}_{2}\right], \ldots, \mathrm{OUT}\left[\mathrm{n}_{\mathrm{k}}\right]\right)$，$V^k\in(V_1 \times V_2 \times \dots \times V_k)$ ，
$ V^k $ 即一次迭代产生的输出，每次迭代会更新$V^k$，可以将每次迭代经过transfer functions和control-flow handing的过程抽象为$F: V^k\rightarrow {V^{k}}’$
当$V^k\rightarrow {V^{k}}’$时，即$X=F(X)$ ，称$F(x)$在$X$处到达了不动点，$X$为$F(x)$的不动点，

Poset & partial order（偏序集和偏序）

We define poset as a pair (P, ⊑) where ⊑ is a binary relation that defines a partial ordering over P, and ⊑ has the following properties:

(1) $\forall x \in P, x \sqsubseteq x$ (Reflexivity, 自反性)
(2) $\forall x, y \in P, x \sqsubseteq y \wedge y \sqsubseteq x \Rightarrow x=y \quad$ (Antisymmetry，反对称性)
(3) $\forall x,y,z \in P, x \sqsubseteq y \wedge y \sqsubseteq z \Rightarrow x \sqsubseteq z $ (Transitivity，传递性)

偏序集为一个二元组$(P, \sqsubseteq)$，$P$为一集合，$\sqsubseteq$为在集合上的一种比较关系，这个二元组为偏序集当且仅当集合元素在关系上满足自反性、反对称性和传递性。

偏序的含义：一个集合中的任意两个元素不一定存在顺序关系（任意两元素不一定能比较大小）

Uppper and Lower Bounds（上界和下界）

Given a poset (P, ⊑) and its subset $S$ that $S\subseteq P$, we say that $u\in P$ is an upper bound of $S$, if $\forall x \in P, x\sqsubseteq u$. Similarly, $l∈P$ is an lower bound of $S$, if $\forall x \in P, l\sqsubseteq u$.

如图，$\{a,b,c\}$是$S$的上界（灰色），$\{\}$是$S$的下界：

最小上界、最大下界

We define the least upper bound (lub or join) of $S$, written $⊔S$, if for every upper bound of $S$, say $u, ⊔S⊑u$. Similarly, We define the greatest lower bound (glb or meet) of $S$, written $⊓S$, if for every lower bound of $S$, say $l, l⊑⊓S$.

特别的，对于仅有两个元素的集合$S=\{a,b\}$，$\sqcup S$ 可以写为$a \sqcup b$，同理 $\sqcap S$可以写为 $a\sqcap b$。

注意：（最小）上界和（最大）下界是针对集合中的特定子集的，而上下界本身不一定在子集中，并且：

不是所有偏序集均存在lub或者glb（如先前灰色的集合就不含lub）
如果一个偏序集存在lub和glb，那么它是唯一的
- 证明：设$g_1$ 和$g_2$ 同为 P 的glb，那么根据定义 $g_1\sqsubseteq (g_2 = \sqcap P)$ 并且$g_2\sqsubseteq (g_1 = \sqcap P)$，又因为反对称性，所以$g_1=g_2$

Lattice, Semilattice, Complete and Product Lattice

Lattice（格）

Given a poset $(P, ⊑), ∀a,b∈P$, if $a⊔b$ and $a⊓b$ exist, then $(P,⊑)$ is called a lattice.

如果一个偏序集的任意两个元素都有最小上界和最大下界，那么这一偏序集是一个格

Semilattice

最小上界和最大下界只存在一个的偏序集称半格，只存在最小上界称为“join semilattice”，只存在最大下界称为“meet semilattice”。

Complete Lattice，top & bottom（全格，$\top$ 和 $\perp$）*

Given a lattice $(P,⊑)$, for arbitrary subset $S$ of $P$, if $⊔S$ and $⊓S$ exist, then $(P,⊑)$ is called a complete lattice.

一个偏序集的任意子集均存在最小上界和最大下界，那么这个偏序集成为全格。

每个全格都存在一个最大元素 top（$\top=\sqcup P$）和最小元素bottom（$\perp=\sqcap P$）

所有元素有限的格（finite lattice）均是全格。（反之不成立）

Product Lattice

Given lattices $L_1=(P_1,⊑_1),L_2=(P_2,⊑_2),…,L_n=(P_n,⊑)n)$, if for all $i$, $(P_i,⊑_i)$ has $⊔i$(least upper bound) and $⊓_i$(greatest lower bound), then we can have a product lattice $L^n=(P,⊑)$ that is defined by:

$P=P_{1} \times \ldots \times P_{n}$

$\left(x_{1}, \ldots, x_{n}\right) \sqsubseteq\left(y_{1}, \ldots, y_{n}\right) \Leftrightarrow\left(x_{1} \sqsubseteq y_{1}\right) \wedge \ldots \wedge\left(x_{n} \sqsubseteq y_{n}\right)$

$\left(x_{1}, \ldots, x_{n}\right) \sqcup\left(y_{1}, \ldots, y_{n}\right)=\left(x_{1} \sqcup_{1} y_{1}, \ldots, x_{n} \cup_{n} y_{n}\right)$

$\left(x_{1}, \ldots, x_{n}\right) \sqcap\left(y_{1}, \ldots, y_{n}\right)=\left(x_{1} \sqcap_{1} y_{1}, \ldots, x_{n} \sqcap_{n} y_{n}\right)$

Product Lattice仍是Lattice，若每个子格为全格，那么乘积也是全格。

Data Flow Analysis Framework via Lattice

一个数据流分析框架可以表示为一个三元组$(D,L,F)$ ，其中：

D：指数据流分析的方向，i.e., forward or backward；
L：指lattice，该格表示所有domain值域，以及meet（$\sqcap$）或join（$\sqcup$）操作；
F：一组transfer function。

Monotonicity and Fixed Point Theorem

Monotonicity（单调性）

A function $f: L→L$ ($L$ is a lattice) is monotonic if $∀x,y∈L$, $x⊑y⟹f(x)⊑f(y)$

普通函数的单调性的推广

Fixed-Point Theorem

Given a complete lattice ($L,⊑$), if (1) $f:L→L$ is monotonic and (2) $L$ is finite, then the least fixed point of $f$ can be found by iterating $f(⊥), f(f(⊥)), \dots, f^k(⊥)$ until a fixed point is reached the greatest fixed point of $f$ can be found by iterating $f(\top),f(f(\top)),\dots, f^k(\top)$ until a fixed point is reached.

如果f单调且L有界，那么f存在不动点，从$⊥$开始迭代执行$f$可得最小不动点，从$\top$开始迭代可得最大不动点。

证明：
(1) Existence
由$\perp$定义以及$f:L\rightarrow L$可得

$\perp \sqsubseteq f(\perp)$

又因$f$是单调的，因此

$f(\perp) \sqsubseteq f(f(\perp))=f^2(\perp)$

由于L是有限(finite)的，因此总会存在一个k，有

$f^{Fix}=f^k(\perp)=f^{k+1}(\perp)$

（2）Least Fixed Point（数归法，证明最小）

假设我们有另一个不动点x，i.e., $x=f(x)$

由$\perp$的定义，我们有$\perp \sqsubseteq x$;

下面用数归法证明：

由于 $f$ 是单调的，因此

$f(\perp) \sqsubseteq f(x)$

对于$f^i(\perp)\sqsubseteq f^i(x)$，由于 $f$ 是单调的，因此有

$f^{i+1}(\perp)\sqsubseteq f^{i+1}(x)$

因此对于任意i，有

$f^i(\perp)\sqsubseteq f^i(x)$

又因为$x=f(x)$，所以存在一个i，有$f^i(\perp)\sqsubseteq f^i(x)=x$，因此有

$f^{Fix} = f^k(\perp) \sqsubseteq x$

因此$f^i(\perp)$ 是最小不动点。

Relate lterative Algorithm to Fixed Point Theorem

如何将迭代算法和不动点定理联系起来？

程序中每一个状态为一个product lattice
Transfer function和join/meet fucntion可以视为F

下面只需要证明Transfer function和 join/meet function均为单调的即可

Transfer function是单调的，因为通过之前分析，所有Gen/Kill的函数都是单调的；
Join/meet function是单调的，证明如下

要证Join/meet function，就是要证$\forall x, y, z \in L, x \sqsubseteq y \Rightarrow x\sqcup z \sqsubseteq y \sqcup z$

由 $\sqcup$ 定义可得，$y \sqsubseteq y \sqcup z$，

由于$\sqsubseteq$传递性，$x \sqsubseteq y$，因此$x \sqsubseteq y \sqcup z$，因此 $y \sqcup z$ 是 $x$ 的上界，

注意到 $y \sqcup z$ 也是 $z$ 的上界，而$x\sqcup z$ 是 $x$ 和 $z$ 的最小上界，

因此 $ x \sqsubseteq y \Rightarrow x\sqcup z \sqsubseteq y \sqcup z$

讨论算法复杂度

定义格的高度即从top至bottom的最长路径长，

The height of a lattice $h$ is the length of the longest path from Top to Bottom in the lattice.

最坏情况即一次迭代，只变化一个单位高度，因此复杂度为$O(h \times k)$.

May/Must Analysis, A Lattice View*

任何分析初始状态都从unsafe至safe。

个人对safe和unsafe的理解：针对于分析结果而言，处理所有分析结果后，程序行为正常为safe，反之为unsafe，极端的safe是无用的（如安全扫描中的模式匹配）

Must和May分析的示意图如上图所示，对于Must分析，每个代码块都是从 $\top$ 开始的，因为在程序一开始，算法认为所有的待分析对象都是“合格”的（例如存活表达式分析中，算法认为每个表达式都是成活的）——这是一个不安全的状态，经过不断迭代，算法逐渐下降到最大不动点，虽然已经过了truth点（漏报），但是这已经是最好情况了（越往下走越safe但是结果也没意义了），对这些结果做优化能确保程序不出错（safe）。

对于May分析，每个代码块从 $\perp$ 开始，即在一开始，算法认为所有分析对象都是不合格的（例如定义可达性分析中，算法认为每一条定义都没有新的定义）——这是May类型的不安全状态，经过不断迭代，算法逐渐上升到最小不动点，同样也过了truth（误报），这也是分析的最好情况，算法依旧停留在safe区域。

Distributivity（分配性） and MOP

MOP（Meet-Over-All-Paths Solution）

设 $s_x$ 为每一个statments，设 $F_p$ 是一个路径 $P$ 上的 transfer function，那么$MOP[S_i]=\sqcup/\sqcap_{\text{A path }P\text{ from Entry to }S_{i}} F_p(OUT[Entry])$.

就是说，之前数据流分析的结果是流敏感的，而 MOP 的结果是路径敏感的，

例如下图所示的数据流，数据流分析的结果是 $\mathrm{IN}\left[\mathrm{s}_{4}\right]=f_{s_{3}}\left(f_{s_{1}}(\mathrm{OUT}[ entry ]) \sqcup f_{S_{2}}( OUT [ Entry ])\right)$，而MOP是 $ \mathrm{MOP}\left[\mathrm{s}_{4}\right]=f_{S_{3}}\left(f_{s_{1}}(\mathrm{OUT}[ entry ])\right) \sqcup f_{S_{3}}\left(f_{S_{2}}(\mathrm{OUT}[ Entry ])\right)$（注意$f_{s_3}$的位置）

Iterative Algorithm v.s. MOP

MOP比Iterative分析更精确，也就是说路径敏感比敏感更精确，下面为证明（这里只需证明两条路径的情况，其它数归即可）：

由 $\sqcup$ 的定义得 $\mathrm{x} \sqsubseteq \mathrm{x} \sqcup \mathrm{y}$ 且 $\mathrm{y} \sqsubseteq \mathrm{x} \sqcup \mathrm{y}$；

因为 $F$ 是单调的，因此有 $F(x) \sqsubseteq F(x \sqcup y)$ 且 $F(y) \sqsubseteq F(x \sqcup y)$；

因此$F(x\sqcup y)$ 是 $F(x)$ 和 $F(y)$ 的上界；

又因为$F(x)\sqcup F(y)$是 $F(x)$ 和 $F(y)$ 的最小上界；

因此 $ F(x) \sqcup F(y) \sqsubseteq F(x\sqcup y)$，即$MOP \sqsubseteq Ours$。

然而，当F是distributive（F满足分配率）时，Interative和MOP一样准确。

BitVector或是Gen/Kill问题（set union/intersection for join/meet）都是满足分配率的

Constant Propagation

Given a variable $x$ at program point p, determine whether $x$ is guaranteed to hold a constant value at $p$

对于在程序点 $p$ 的一个变量 $x$，判断 $x$ 是否为在 $p$ 点为一个常量

分析结果：对于每一个CFG节点，对应一个 $(x,v)$ 集合，$x$ 是变量，$v$ 是 $x$ 的值

Lattice

Domain： UNDEF → {…, -2, -1, 0, 1, 2, …} → NAC ，→ 表示 $\sqsubseteq$ 关系

Meet Operator $\sqcap$：

$\mathrm{NAC} \sqcap v= \mathrm{NAC}$
$\mathrm{UNDEF} \sqcap v= v$
$c \sqcap v= \mathrm{NAC}$ （c 为一常量）
$c \sqcap c= c$
$c_1 \sqcap c_2 = \mathrm{NAC}$

Transfer Function

讨论transfer function，对于一个赋值语句 s: x= ... 来说，定义其 F 为

$F: \mathrm{OUT}[s]=gen \cup(\mathrm{IN}[s]-\{(x, \_)\})$

s: x=c; $gen=\{(x,c)\}$
s: x=y; $gen=\{(x, val(y))\}$
s: x=y op z; $gen=\{(x, f(x,z))\}$

而 $f(x,z)$ 有三种情况：

$f(y,z)=\left\{ \begin{array}{ll} val(y) \text { op } val(z) & \text {// if val(y) and val(z) are constants } \\ \text { NAC } & \text {//if val(y) or val(z) is NAC } \\ \text { UNDEF } & \text {// otherwise } \\ \end{array}\right.$

function不满足分配性

如下图所示，$F(X\sqcap Y)$ 中C的值为NAC，而$F(X) \sqcap F(Y)$中 C 的值为10，因此F不满足分配性。

Worklist Algorithm

Iterative Algorithm的优化，Iterative 存在冗余的计算，而Worklist只计算有变化的node：

OUT[entry] =∅;
for(each basic block B\entry) 
	OUT[B] =∅;
    Worklist←all basic blocks
	while (Worklist is notempty) 
    	Pick a basic block B from Worklist
		old_OUT= OUT[B]
        IN[B] =⊔OUT[P]; # join/meet P为B的前置代码块
        OUT[B] = genB U (IN[B] - killB); # transfer function 
        if(old_OUT≠OUT[B])
        	Add all successors of B to Worklis

分析特性

流敏感：程序语句随意调换位置，分析结果不变为流非敏感，否则为流敏感；
路径敏感：考虑程序中路径的可行性；

总结

本节课主要介绍格，接着用格抽象描述数据流分析，解释为什么迭代算法能够到达最大/最小不动点，接着比较了流敏感和路径敏感的准确性，最后介绍worklist算法，以提升迭代算法的效率。