我能否将抽象语法树翻译成静态单赋值形式，还是需要先将其转换成控制流图再转换成静态单赋值形式？

Question

我能直接将抽象语法树转换成静态单赋值形式(SSA)，还是需要创建控制流图(CFG)，然后从该CFG创建静态单赋值形式？

在控制流图的上下文中：如何为类似于C的程序表示这个问题？我考虑存储每个函数中所有基本块的CFG图，但是当我调用函数时，这可能会使事情复杂化。另一种我能想到的方式是整个程序的CFG，即所有源文件，但是如何存储有关函数的信息？我可以在基本块(即父节点)中存储指向函数的指针吗？

如果我从CFG生成SSA，我需要担心表示语句的控制流程的CFG吗？我认为我只需要表示基本块的控制流程。

- Jon Flow

Answer 1

是的，您可以在不先构建CFG的情况下创建SSA表单，但是您不能使用Cytron等人的经典SSA构造算法来实现。文章Simple and Efficient Construction of Static Single Assignment Form（声明：我是作者之一）中描述了另一种算法。该算法用于libFirm、OpenJDK和Go编译器中。

大多数编译器（据我所知）使用每个函数一个CFG的模型。每个基本块都是一个节点。语句（也称操作/指令等）属于一个基本块。有些编译器将指令存储为每个基本块内部的列表。有些则将指令存储为类似于CFG的部分有序图形式。

- qznc

---

我刚刚读完这篇文章，非常棒！我只是想知道它是构建了最小的还是修剪过的SSA，因为有时它说“修剪”，有时说“最小”，大多数时候则是“最小和修剪”。 - xilpex

算法真的没有CFG吗？在我看来，文章中介绍的那个算法是基于CFG操作的。 - Björn Lindqvist

我认为这根本不是无 CFG，尽管摘要中说它可以直接从字节码转换到 SSA。从论文中可以看出：“本文介绍的算法是第一个在可约 CFG 上构建最小和修剪 SSA 的算法”，“首先，我们考虑单个基本块。然后，我们将算法扩展到整个 CFG。最后，我们展示如何处理不完整的 CFG，这通常在将 AST 转换为 IR 时出现。”这些陈述都与从字节码或线性指令转换为 SSA 无关。 - larkwiot