静态单一赋值：并非所有可能的路径都定义变量 - 如何插入 PHI？

Question

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

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 --/

Answer 1

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

\n\n

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

\n\n

x1 = 1;           // A\nif (P)            // A\n    y1 = x1 + 1;  // B\n    y2 = y1 + 1;  // B\ny3 = \xcf\x86(y0, y2)    // C\nx2 = x1 + 1;      // C\nreturn;           // C\n

\n