数据流分析与格（一）

2022-10-13 | 阅读：次

迭代算法

以May & Forward Analysis为例

OUT[entry] = EMPTY
for(each entry block B\entry)
	OUT[B] = EMPTY;  //may analysis一般为EMPTY, must analysis一般为FULL
while(changes to any OUT occur)
	for(each basic block B\entry){
		IN[B] = union(OUT[B.predecessors]);
		OUT[B] = union(gen(B), IN[B]-kill(B));
	}

迭代算法的表现为：给定k个节点的CFG，每一次迭代更新每个节点的OUT。

假设数据流分析的值域为V，那么我们可以定义一个k元组

\[(OUT[n_1],OUT[n_2],...,OUT[n_k])\]

来作为集合$(V_1,V_2,…,V_k)$（又记为$V^k$)的元素。

每一次迭代便可以视为执行一个函数$F:V^k \rightarrow V^k$。迭代会产生一个k元组的序列，直到最后连续两次产生的元组相同。

重新审视迭代算法：

\[init \rightarrow (\perp,\perp,...,\perp)=X_0\\ iter\ 1 \rightarrow (v_1^1,v_2^1,...,v_k^1)=X_1=F(X_0)\\ iter\ 2 \rightarrow (v_1^2,v_2^2,...,v_k^2)=X_2=F(X_1)\\ ...\\ iter\ i \rightarrow (v_1^i,v_2^i,...,v_k^i)=X_i=F(X_{i-1})\\ iter\ i+1 \rightarrow (v_1^i,v_2^i,...,v_k^i)=X_{i+1}=F(X_i)=X_i\\\]

在迭代的最后得到$X=F(X)$，即不动点。

偏序与格

偏序关系

我们定义一个偏序集为一个二元组$(P,\sqsubseteq)$，其中$\sqsubseteq$为一个二元操作，其定义了$P$上的偏序关系。

$\sqsubseteq$满足以下性质：

自反性：

\[\forall x \in P,x\sqsubseteq x\]

反对称性：

\[\forall x,y \in P, x\sqsubseteq y \wedge y \sqsubseteq x \rightarrow x=y\]

传递性：

\[\forall x,y,z \in P,x\sqsubseteq y \wedge y \sqsubseteq z \rightarrow x\sqsubseteq z\]

在偏序集中，可能存在两个元素不可比较。

上下界

给定$(P,\sqsubseteq)$和子集$S \subseteq P$，如果$\forall x \in S,x\sqsubseteq$ u，则$u\in P$是$S$的一个上界。

同理，如果$\forall x \in S,l\sqsubseteq$ x，则$l\in P$是$S$的一个下界。

我们定义最小上界（lub或join）。$S$的最小上界（记作$\sqcup S$）是对于$S$的每一个上界$u$，都有$\sqcup S \sqsubseteq u$。

最大下界（glb或meet）。$S$的最大下界（记作$\sqcap S$）是对于$S$的每一个下界$l$，都有$l \sqsubseteq \sqcap S$。

一般而言，如果$S$只有两个元素a和b，那么$\sqcup S$可以记作$a\sqcup b$， $\sqcap S$可以记作$a\sqcap b$

偏序集不一定有glb或lub，但如果一个偏序集有glb或lub，那么它们一定是唯一的。

格

给定$(P,\sqsubseteq)$，$\forall a,b \in P$，如果$a\sqcup b, a\sqcap b$都存在，那么$(P,\sqsubseteq)$就是一个格。

半格

对偏序集的任意两个元素，如果它们只有lub存在，那么该集合为join半格。meet半格同理。

全格

给定$(P,\sqsubseteq)$，$\forall S \subseteq P$，如果$\sqcap S, \sqcup S$都存在，那么$(P,\sqsubseteq)$便是一个全格。

对于一个完全格，其一定有一个最大元素$\top=\sqcup P$和最小元素$\bot =\sqcap P$

乘积格

给定格$L_1,L_2,…,L_n$，我们定义$L^n=(P,\sqsubseteq)$，其中

$P=P_1 \times … \times P_n$
$(x_1,…,x_n)\sqsubseteq(y_1,…,y_n)\Leftrightarrow (x_1 \sqsubseteq y_1)\wedge … \wedge (x_n \sqsubseteq y_n)$
$(x_1,…,x_n)\sqcap(y_1,…,y_n) = (x_1 \sqcap_1 y_1,…,x_n \sqcap_n y_n)$
$(x_1,…,x_n)\sqcup(y_1,…,y_n) = (x_1 \sqcup_1 y_1,…,x_n \sqcup_n y_n)$

乘积格是格。如果由完全格乘得，那么其也是完全格。