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

Question

如果你正在构建一个编译器,那么AST级别的优化是最好的吗？

Answer 1

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

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

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

在DMS软件再造工具包是变换的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可能需要一个特殊的节点，该节点可以指示以后的遍历使用参数覆盖当前堆栈帧并相应地跳转。