compiler-construction - 我可以将 AST 转换为 SSA，还是需要先转换为 CFG，然后再转换为 SSA？

Question

我可以将抽象语法树直接转换为 SSA 形式，还是需要创建一个控制流图，然后从所述 CFG 创建静态单一分配形式？

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

如果我从 CFG 生成 SSA，我是否需要担心有一个代表语句控制流的 CFG？我想我只需要表示基本的块控制流。

Answer 1

是的，您可以在不先构建 CFG 的情况下创建 SSA 表单，但是您不能使用 Cytron 等人的经典 SSA 构建算法来执行此操作。论文Simple and Efficient Construction of Static Single Assignment Form中描述了另一种算法。 (免责声明:我是作者之一)。该算法用于libFirm ，在 OpenJDK 和 Go 编译器中。

大多数编译器 (afaik) 使用一个 CFG-per-function 模型。每个基本块都是一个节点。语句(又名操作/指令/等)属于一个基本块。一些将指令存储为每个基本块中的列表。一些将指令存储为类似于 CFG 的部分有序图。