4

我正在为我正在编写的编译器实现SSA 构造。SSA 算法中有一些我不理解的东西（使用Cytron 论文和《Java 中的现代编译器实现》一书，AW Appel 的第二版）。如果一个变量y第一次在一个直接的控制流路径中定义（并使用）但从未在另一个并行路径中定义，该怎么办？我是否必须在连接点（块定义的优势边界y）插入 PHI 函数？

x = 1;            // A
if (P)            // A
    y = x + 1;    // B
    y = y + 1;    // B
x = x + 1;        // C
return;           // C

例如，在块 B 中有 的第一个定义y。我是否必须在块 C 的开头插入一条 PHI 指令，带有两个操作数（一个用于每个传入的控制流路径）？然后在 SSA 重命名：我将如何命名来自从未定义的路径A -> C（而不是通过 B）的操作数？y

Entry --- A --------- C --- Exit
           \         /
            \-- B --/
4

1 回答 1

3

再次阅读材料后，我在AW Appel 的Modern Compiler Implementation in Java, second edition一书中发现了一个关于变量的隐式定义的小提示c0。进一步搜索发现，算法期望所有变量在第一个基本块之前都有一个隐式定义。这个隐含的定义表示变量是全局的、参数或未初始化的变量。

添加这个隐式定义解决了我的问题，示例将变为：

x1 = 1;           // A
if (P)            // A
    y1 = x1 + 1;  // B
    y2 = y1 + 1;  // B
y3 = φ(y0, y2)    // C
x2 = x1 + 1;      // C
return;           // C
于 2012-05-21T22:27:02.687 回答