ch6.2

静态单赋值

静态单赋值（SSA）是一种中间代码表示形式，在该形式下，每个变量在程序的每个控制流路径上都仅被赋值一次。SSA 形式通过在适当的地方插入 φ 函数 来处理控制流合流点，使得代码既具有数据流分析的简洁性，又能够有效优化。

如果某个变量需要被重新赋值，会创建一个新的变量名称，例如 x1, x2, x3。

由于控制流可能发生分支和合流，因此在合流点需要一个 φ 函数来选择正确的变量版本。形式：，表示如果控制流来自不同的路径，x 取对应路径的变量值。

对某一代码写出SSA步骤：先翻译为三地址码，再根据三地址码写出SSA。

Gated SSA

• 特性 1：每个变量只有单一定义

• 特性 2：使用递归 ℽ 函数合并来自多路径的定义

• 特性 3：对循环变量使用 𝛍 和 𝛈 函数

转换为SSA

基本块

如何将三地址码划分为基本块：

• 基本块是一段连续的指令序列

• 每个基本块的首条指令是引导指令（leader）：

  • 函数的第一条指令是引导指令
  • 任何作为跳转目标的指令是引导指令
  • 任何紧跟跳转指令的指令是引导指令

支配和后支配（重要）

• A 支配 B（A dom B），如果从入口（Entry）到 B 的所有路径都必须经过 A（起始点到B的路径一定经过A）。

• A 后支配 B（A post-dom B），如果从 B 到出口（Exit）的所有路径都必须经过 A（B到出口一定经过A）。

• 严格（后）支配：A（后）支配 B，但 A ≠ B。

• 直接支配（Immediate Dominance）：A 严格支配 B，但不存在 C，使得 A 严格支配 C 且 C 严格支配 B。

证明直接支配关系为什么会生成树而不是图？

要证明直接支配关系生成的是树而不是图，我们需要证明以下两点：

1. 每个节点（除入口节点外）有唯一的直接支配节点（保证没有多父节点，排除图的可能性）。

2. 直接支配关系形成一个无环的层次结构（保证树形结构）。

步骤 1：每个节点有唯一直接支配节点

假设一个节点 B 有两个不同的直接支配节点 A1 和 A2，即：

• A1 严格支配 B，且不存在 C 使得 A1 严格支配 C 且 C 严格支配 B。

• A2 严格支配 B，且不存在 C 使得 A2 严格支配 C 且 C 严格支配 B。

我们需要证明 A1 = A2（即直接支配节点是唯一的）。

证明（反证法）：

• 假设 A1 ≠ A2。

• 因为 A1 严格支配 B，从入口到 B 的每条路径都必须经过 A1。同样，因为 A2 严格支配 B，从入口到 B 的每条路径都必须经过 A2。

• 现在考虑从入口到 B 的一条路径 P：

  • P 必须经过 A1 和 A2（因为 A1 和 A2 都支配 B）。
  • 在路径 P 上，A1 和 A2 出现的顺序有三种可能：
    • A1 在 A2 之前：那么从入口到 A2 的路径经过 A1，说明 A1 支配 A2（A1 dom A2）。因为 A1 ≠ A2，这意味着 A1 严格支配 A2。但 A2 是 B 的直接支配节点，意味着不存在 C 使得 A2 严格支配 C 且 C 严格支配 B。然而，A1 严格支配 A2 且 A2 严格支配 B，这与 A2 是 B 的直接支配节点矛盾。
    • A2 在 A1 之前：类似地，A2 严格支配 A1，A1 严格支配 B，这与 A1 是 B 的直接支配节点矛盾。
    • A1 和 A2 相同：这与假设 A1 ≠ A2 矛盾。
  • 因此，假设 A1 ≠ A2 导致矛盾，说明 B 不可能有两个不同的直接支配节点。
  • 结论：每个节点 B（除入口节点外）有唯一的直接支配节点。

步骤 2：直接支配关系无环

• 直接支配关系定义了父子关系：如果 A 是 B 的直接支配节点，则 A 是 B 的父节点。

• 假设存在一个环，例如 A1 → A2 → A3 → … → A1（A1 是 A2 的直接支配节点，A2 是 A3 的直接支配节点，等等）。

• 根据直接支配的定义：

  • A1 严格支配 A2，A2 严格支配 A3，…，A1 严格支配 A2。这意味着 A1 支配 A1（通过环），但严格支配要求 A1 ≠ A1，这是不可能的。

• 因此，直接支配关系不可能形成环，关系是有向无环的。

步骤 3：形成树的结构

• 从步骤 1，我们知道每个节点（除入口节点外）有唯一的直接支配节点，这意味着每个节点有唯一的父节点。

• 从步骤 2，我们知道直接支配关系是无环的。

• CFG 的入口节点没有支配它的节点（它是根节点）。

• 结合以上两点，直接支配关系形成一个以入口节点为根的树形结构：

  • 每个节点有唯一的父节点（直接支配节点）。
  • 没有环，层次结构清晰。

• 所有节点都可以通过支配关系追溯到入口节点。

步骤 4：为什么不是图？

• 如果直接支配关系形成图，意味着某些节点可能有多个父节点（多重直接支配节点）或存在环。

• 从步骤 1，已证明每个节点有唯一的直接支配节点，排除多父节点的可能性。

• 从步骤 2，已证明关系无环。

• 因此，直接支配关系不可能形成图，只能是树。

支配树

树的节点：基本块（Block）树的边：直接支配关系（Immediate Dominance Relation）

由控制流图创建支配树：

控制依赖（重要）

B控制依赖于A：

• A的结果决定B是否执行。

• A有很多后继结点，不是每条路径都能到达B。

• B 后支配 A 的某个后继节点，B 不后支配 A 的所有后继节点。

控制依赖生成的是图

支配边界

Dominance Frontier：

• DF(B) = { … }

• B 所支配的块的直接后继节点集合，这些后继节点不被 B 严格支配

迭代支配边界（IDF）

Bset 的迭代支配边界

• DF1 = DF(Bset); Bset = Bset ∪ DF1

• DF2 = DF(Bset); Bset = Bset ∪ DF2

• ……

• 直到达到固定点（即 DFn = DFn-1）

IDF vs. SSA

变量的定义可以传递到以下块：

• 被该定义所支配的块，或位于迭代支配边界（IDF）中的块，例如，IDF({A, B, C}) = { E, F }

• 这些块是插入 φ 函数的位置

---

• ← Previous Post
• Next Post →

---