compiler-construction - 从抽象语法树生成基于寄存器的字节码？

Question

有哪些众所周知的生成策略register based来自给定 anstract 语法树 (AST) 的字节码？

考虑这个表达式 1 + 2 - 3 * 4 / 5及其 AST 形式:

bin_exp(-)
    bin_exp(+)
        num_exp(1)
        num_exp(2)
    bin_exp(/)
        bin_exp(*)
            num_exp(3)
            num_exp(4)
        num_exp(5)

我正在努力在程序上将 AST 转换为其相应的字节码。
目前我只找到了一个 article ，其中仅简要介绍了它。我对它想表达的意思的解释...

int ridx; // register index

function visit_exp(exp)
{
    switch (exp)
    {
        case bin_exp:
            visit_exp(exp.left);
            visit_exp(exp.right);

            printf("add %i, %i -> %i\n", ridx - 2, ridx - 1, ridx);

            // save ridx, as it contains the result
                    break;
        case num_exp:
            printf("mov %i -> %i\n", ridx, exp.value);
            break;
    }
}

请帮我一把，谢谢。

Answer 1

请执行下列操作:

给每个表达式节点一个唯一的编号 en。您可以在飞越树时执行此操作。

对于编号为 el 的叶节点，生成“MOV el,operand”

对于每个编号为 er 的内部节点“OP”，带有二进制子节点 es 和 et，生成“OP er, es, et”。使用明显的概括来处理具有任意数量子项的运算符。

这将产生“原始”代码，因为虚拟寄存器数量可以任意大(例如，由程序的大小决定)。

更复杂的版本会保留一个节点编号池，当您从左到右遇到每个节点时，将池中最低的可用编号分配给每个节点，并将 OP 指令输入操作数的编号放回池中(因为它们现在是“免费的”)，因为每个 OP 指令都会生成。这将在实践中产生一组小得多的虚拟寄存器组编号。

想变聪明，做完以上，申请 register coloring到生成的代码，启用使用固定数量的寄存器。