水星程序的静态区域分析与优化

### 水星程序的静态区域分析与优化 在程序开发中，有效的内存管理至关重要。本文将介绍一种针对水星（Mercury）程序的静态区域分析方法，该方法能够帮助我们更好地管理内存，提高程序的性能。 #### 区域指向分析 区域指向分析是一种流不敏感的分析方法，它由过程内分析和过程间分析两部分组成。 ##### 过程内分析 假设我们正在分析一个过程 `p`，其区域指向图 `G = (N, E)` 的计算步骤如下： 1. 为 `p` 中的每个变量分配一个单独的节点。对于变量 `X`，`nX` 成为 `N` 中的一个节点，且 `vars(nX) = {X}`。 2. 逐个处理 `p` 中的专门合一操作： - 赋值操作 `X := Y`：应用 `unify(nX, nY)` 以确保第一个不变式。 - 测试操作 `X == Y`：不做任何处理。 - 解构操作 `X => f(Y1, ..., Yn)` 或构造操作 `X <= f(Y1, ..., Yn)`：通过添加边 `edge(nX, (f, 1), nY1), ..., edge(nX, (f, n), nYn)` 创建从 `nX` 到每个 `nY1, ..., nYn` 的引用。 3. 只要适用，就触发图 4 中的规则。规则 `P1` 和 `P2` 用于确保第二个不变式，规则 `P3` 用于强制执行第三个不变式。 ```plaintext k = unify(n, n′) (k, sel, m) ∈E (k, sel, m′) ∈E m ̸= m′ unify(m, m′) (P1) edge(n, sel, m) (n, sel, m′) ∈E m ̸= m′ unify(m, m′) (P2) edge(n, sel, m) (k1, m) ∈E+ (m, k2) ∈E+ k1 ̸= k2 type(k1) = type(k2) unify(k1, k2) (P3) ``` 其中，`E+` 是 `E` 的自反传递闭包，`type(n)` 返回节点 `n` 的类型。 ##### 过程间分析 过程间分析通过在每个调用点将被调用过程的区域指向图的相关部分集成到过程 `p` 的区域指向图 `Gp` 中来更新 `Gp`。对于调用 `q(Y1, ..., Yn)`，定义过程的头部为 `q(X1, ..., Xn)`。分析步骤如下： 1. 处理 `p` 中的每个过程调用 `q(Y1, ..., Yn)`：通过构建从 `Nq` 到 `Np` 的部分 `α` 映射，将 `q` 的图 `Gq = (Nq, Eq)` 集成到 `p` 的图 `Gp = (Np, Ep)` 中： - 初始化 `α` 映射，`α(nX1) = nY1, ..., α(nXn) = nYn`。对于在 `Gq` 中已经合一的节点，`Gp` 中对应的节点也应合一。通过应用图 5 中的规则 `P4` 来确保 `α` 是一个函数。 - 在图 `Gq` 中，从每个 `nXi` 开始，沿着每条边遍历一次，并在适用时应用图 5 中的规则 `P5 - P8`。这些规则完成 `α` 映射，并将与 `nXi` 相关的 `Gq` 部分复制到 `Gp` 中。当 `Gp` 中的两个节点合一（规则 `P4` 和 `P5`）或向 `Gp` 中添加一条边（规则 `P7` 和 `P8`）时，我们需要分别应用规则 `P1` 或 `P3` 到 `Gp` 以维护第二个和第三个不变式。（规则 `P2` 永远不适用，因为其条件无法满足。） 2. 重复步骤 1，直到 `Gp` 不再发生变化。 ```plaintext α(nXi ) = nYi α(nXj ) = nYj nXi = nXj nYi ̸= nYj unify(nYi , nYj ) (P4) (nq, sel, mq) ∈Eq α(nq) = np (np, sel, m′ p) ∈Ep α(mq) = mp ̸= m′ p unify(mp, m′ p) (P5) (nq, sel, mq) ∈Eq α(nq) = np (np, sel, mp) ∈Ep α(mq) undefined α(mq) = mp (P6) (nq, sel, mq) ∈Eq α(nq) = np ̸ ∃k : (np, sel, k) ∈Ep α(mq) = mp edge(np, sel, mp) (P7) (nq, sel, mq) ∈Eq α(nq) = np ̸ ∃k : (np, sel, k) ∈Ep α(mq) undefined mp : a new node in Gp α(mq) = mp edge(np, sel, mp) (P8) ``` 当算法终止时，即没有规则可以应用且达到一个不动点时，程序过程的区域指向图将都是兼容的。 #### 活跃区域分析 活跃区域分析的目标是检测每个程序点哪些区域变量是活跃的，并决定每个过程创建和移除哪些区域。 ##### 程序点的活跃区域变量 - **活跃变量**：在过程 `p` 中，一个变量在程序点之后是活跃的，如果满足以下条件之一： - 存在一条包含该程序点的执行路径，在该程序点之前或在该程序点实例化该变量，并在该程序点之后使用它。 - 它是 `p` 的输出变量，且在该程序点之前或在该程序点实例化。 - 活跃变量集的计算公式如下： - `LV after(i) = {V | ∃P : V ∈(pre inst(i, P) ∪out(i)) ∩(out(p) ∪post use(i, P))}` - `LV before(i) = (LV after(i) \ out(i)) ∪in(i)` - 过程 `p` 执行路径的第一个程序点的 `LV before` 定义为 `in(p)`，即过程的输入变量集。最后一个程序点的 `LV after` 定义为 `out(p)`。 - **活跃区域变量**：如果一个区域变量的节点在程序点可以从活跃变量到达，则该区域变量在该程序点是活跃的。 - 可达节点集的定义如下： - `Reach(X) = {nX} ∪{m | ∃(nX, m) ∈E∗(X)}` - `E∗(X) = {(nX, ni) | ∃(nX, sel0, n1), ..., (ni−1, seli−1, ni) ∈E}` - 程序点 `i` 之前和之后的活跃区域变量集定义如下： - `LRbefor