您最喜欢的抽象语法树优化

对ast(而不是cfg)最容易进行的优化是尾调用优化:如果您看到表单的子树:

RETURN
    CALL f
        ARGS x, y, ...

您可以用跳转来替换它 f . 如果 f(a, b) 是尾调用出现的函数,替换简单如下:

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

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

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

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

如果你 做 有了所有其他的表示,您可以考虑在AST级别进行优化。大多数构建编译器的人并不费事;他们转换为数据流表示并简单地优化它。但是,如果您想用更改来重现源代码,则需要AST。您还需要一个预打印器来重新生成源代码。如果你走到这一步,你会得到一个源到源的结果。 程序转换系统。

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

在AST中应用优化的一个优点是可以减少一些后端优化过程的执行时间。但是,我认为这些优化需要以节俭的方式完成,因为您可能会妨碍代码中进一步的优化。

也就是说,在AST级别或在IR生成期间应用的一个简单但有趣的优化是简化形式(1 2)或(2<3 a)等的布尔表达式到它们的最终结果。我相信一些简单的窥视孔优化可能也是值得的。