5

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

4

3 回答 3

8

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

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

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

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

于 2009-12-02T06:20:17.740 回答
7

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

RETURN
    CALL f
        ARGS x, y, ...

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

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

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

于 2009-12-09T09:55:53.523 回答
2

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

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

于 2014-12-17T03:43:12.210 回答