将 AST 编译为汇编

Question

我有一个抽象语法树，需要将其转换为虚拟机程序集。我不知道如何最好地做到这一点，所以我开始使用一系列字符串模板。我的意思的伪代码示例，比如需要编译具有一个条件的简单 if 语句：

std::string compile_if(Node* n) {
    std::string str = "";

    curLabel = nLabels++;

    str += compile_comparison(n->getChild(0));

    str += ".true"+curLabel+":";
    str += compile_block(n->getChild(1));

    str += ".false"+curLabel+":";

    return str;
}

其中每个 compile_* 基于 current/next AST 节点生成一个汇编字符串。然后最后的字符串是运行通过汇编程序。这看起来草率且难以维护，当然这不是大多数编译器所做的。这是一个坏主意，我应该改变它吗？大多数其他编译器如何生成虚拟汇编代码/机器代码？

Answer 1

免责声明： 我只有 X86 机器代码方面的经验。例如，其他指令集可能具有不同的寻址能力，因此我的部分建议可能不适用。抱歉，我现在没有时间研究指令集。

首先，大多数编译器不会将程序集生成为文本，因为将代码序列化为程序集只是让 assembler 直接对其进行解析的效率有点低，正如您可能已经意识到的那样。将编译和汇编阶段分开是合理的，但不是必需的。

在编译阶段，我会考虑的两种策略是：

(a) 将程序集生成为 指令对象 的树/数组，可以象征性地引用一个其他。在组装阶段，这些需要序列化为 bytecode/machinecode。我会推荐这种方法，即使它会使您的编译器体系结构更加复杂。
(b) 使用一些辅助函数将程序集生成为 machinecode/bytecode 到缓冲区中；在这种情况下，您实际上并没有单独的组装阶段。我个人尝试过这种方法，在单个函数的范围内还不错，但是可能会因为不知道函数在assembled.[=20=之前要有多大而造成一些额外的困难]

我猜想 (a) 是 GCC 等优化编译器使用的方法，而 (b) 是使用的方法通过像 TCC 这样的高速编译器。

让我们通过检查现有编译器为简单的 if/else 分支生成的代码来再次考虑 if 示例：

注意反汇编中的重叠跳转 - 一个跳过 'taken' 块，一个跳过 'not-taken' 块。

这些是相对跳转，所以为了 assemble 它们我们需要知道跳转指令和目标之间有多少字节的指令。

下面是使用策略 (a):

编译函数的示例

Instruction[] compile_if(IfNode n) {
    Instruction[] code;

    code ~= compile_condition(n.condition);

    Instruction skip_taken = new JumpInstruction(`jz`);
    code ~= skip_taken;

    code ~= compile_block(n.taken_block);

    Instruction skip_nottaken = new JumpInstruction(`jmp`);
    code ~= skip_nottaken;

    Instruction[] nottaken_code = compile_block(n.nottaken_block);
    skip_taken.destination = nottaken_code[0];
    code ~= nottaken_code;

    Instruction end = new NopInstruction();
    skip_nottaken.destination = end;
    code ~= end;

    return code;
};

这应该是不言自明的。

请注意指令是如何以符号方式相互引用的（skip_taken.destination = nottaken_code[0]），而不是像序列化机器代码中那样通过字节偏移来引用。我们将这些偏移计算留给 assembler.

另请注意，我们如何设置 JumpInstruction 的目的地，仅当它们可用时。

最后的NopInstruction只是为了给skip_nottaken跳转一些参考。

现在，我们如何实际 assemble 这些跳转到真正的 machinecode/bytecode？这是一种可能性（一个非常基本的例子）：

byte[2] assemble_jz(Instruction[] code, int idx) {
    // assemble the jz instruction at code[idx]

    JumpInstruction jump = code[idx];
    ++idx;

    byte jump_offset = 0;
    while (code[idx] != jump.destination) {
        jump_offset += size_of_instruction(code[idx]);
        ++idx;
    };

    byte[2] machinecode = [
        0x74, // jz short
        jump_offset
    ];
    return machinecode;
};

因为assembler可以访问所有指令对象，它可以通过向前扫描直到找到目标指令来计算相对跳转的实际偏移量。

我希望这个简短的介绍可以帮助您开始设计自己的编译器后端。显然，我并不是建议您完全按照我的示例编写编译器，但它应该让您了解如何解决编译和组装非线性指令块的一般问题。

您可能还想查看一些现有的 assembler API，例如 https://github.com/asmjit/asmjit .

祝你好运。

将 AST 编译为汇编

Compiling an AST to Assembly

compiler-construction

assembly

vm-implementation