compiler-construction - 你最喜欢的抽象语法树优化

Question

如果您正在构建一个编译器，那么 AST 级别的哪种优化是最好的？

Answer 1

大多数情况下，您无法在 AST 级别进行有趣的优化，因为您需要了解数据如何从程序的一部分流向另一部分的信息。虽然数据流隐含在 AST 的含义中，但仅通过检查 AST 并不容易确定，这就是为什么人们构建编译器和优化器构建其他程序表示（包括符号表、控制流图、到达定义、数据流和 SSA 表格等）。

拥有一种语言的解析器是分析/操作该语言的简单部分。你需要所有其他的东西才能做好工作。

如果您确实拥有所有其他表示，则可以考虑在 AST 级别进行优化。大多数构建编译器的人都不会打扰。它们转换为数据流表示并简单地对其进行优化。但是，如果您想重现带有更改的源代码，则需要 AST。您还需要一个漂亮的打印机来重新生成源代码。如果你走到这一步，你最终会得到一个源到源的程序转换系统。

DMS Software Reengineering Toolkit是一个转换 AST的系统，使用所有这些其他表示来实现转换所需的分析。

Answer 2

在 AST（而不是 CFG）上最容易进行的优化是尾调用优化：如果您看到以下形式的子树：

RETURN
    CALL f
        ARGS x, y, ...

您可以将其替换为跳转到f. 如果f(a, b)是尾调用出现的函数，替换很简单：

a = x; b = y
JUMP to root of tree

我发现将跳转表示为特殊的“重新启动”语句最容易，AST->CFG 转换将其视为返回第一个节点的边缘。跳转到其他函数有点棘手，因为您不能只设置局部变量，您需要提前考虑如何将参数传递给它们并准备在较低级别进行转换。例如，AST 可能需要一个特殊的节点，它可以指示稍后的传递用参数覆盖当前堆栈帧并相应地跳转。

Answer 3

在 AST 中应用优化的一个优点是它可以减少一些后端优化通道的执行时间。但是，我认为这些优化需要通过简约来完成，因为您可能会阻碍代码中的进一步优化。

话虽如此，在 AST 级别或在 IR 生成期间应用的 IMO 一项简单而有趣的优化是对 (1 || 2) 或 (2 < 3 || A) 等形式的布尔表达式的简化。净结果。我相信一些简单的窥视孔优化也可能是值得的。