数据流分析框架包含方向(D)、值(V)、转换函数(F)、初始值(I)和交运算(Λ)5 个元素,只要分析清楚这 5 个元素,就可以按照固定的套路来编写分析程序。

全局优化时两个分支相遇,要做一个运算,计算他们相交的值,这个运算我们可以用大写的希腊字母(lambda)表示。那么 Λ 怎么计算呢?研究者们用了一个数学工具,叫做“半格”(Semilattice)。

首先,半格是一种偏序集。偏序集就是集合中只有部分成员能互相比较大小。举例来说比较直观。在做全局活跃性分析的时候,{a, b, c} 和 {a, c} 相遇,产生的新值是 {a, b, c}。我们形式化地写成 {a, b, c} Λ {a, c} = {a, b, c}。这时候我们说 {a, b, c} 是可以与 {a, c} 比较大小的。那么哪个大哪个小呢?

$$ X Λ Y = X, X<= Y $$

所以,{a, b, c} 是比较小的,{a, c} 是比较大的。

当然,{a, b, c} 也可以跟 {a, b} 比较大小,但它没有办法跟 {c, d} 比较大小。所以把包含了 {{a, b, c}、{a, c}、{a, b}、{c, d} …} 这样的一个集合,叫做偏序集,它们中只有部分成员之间可以比较大小。哪些成员可以比较呢?就是下面的半格图中,可以通过有方向的线连起来的。半格可以画成图形,理解起来更直观,假设我们的程序只有 a, b, c 三个变量,那么这个半格画成图形是这样的:

d9811d73fef1347e92fc3151fdd48485.webp

沿着上面图中的线,两个值是可以比较大小的,按箭头的方向依次减少:{} > {a} > {a, b} > {a, b, c}。如果两个值之间没有一条路径,那么它们之间就是不能比较大小的,就像 {a} 和 {b} 就不能比较大小。对于这个半格,我们把 {} (空集)叫做 Top,Top 大于所有其它的值。而 {a, b, c} 叫做 Bottom,它是最小的值。

半格是偏序集中,一种特殊的类型,它要求偏序集中,每个非空有限的子集,要么有最小上界(并半格,join-semilattice),要么有最大下界(交半格,meet-semilattice)。

在做活跃性分析的时候,我们的 Λ 运算是计算两个值的最大下界(Greatest Lower Bound)。怎么讲呢?就是比两个原始值都小的值中,取最大的那个。{a} 和 {b} 的最大下界是 {a, b},{a, b, c} 和 {a, c} 的最大下界 {a, b, c}。