将抽象语法树编译成汇编代码

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_*都基于当前/下一个AST节点生成汇编字符串。然后将最终字符串通过汇编器运行。这看起来很松散，难以维护，肯定不是大多数编译器所做的。这是一个坏主意吗？我应该改变它吗？其他大多数编译器如何生成虚拟汇编代码/机器代码？

- Accumulator

---

然后最终的字符串会通过汇编器运行。这可能是“大多数编译器”所做的，但这是一个完全有效的方法。我不明白这与C++有什么关系，因此我将删除该标签。 - user2100815

你在询问关于你正在做的哪个方面？ - harold

模板字符串 - Accumulator

你说“汇编语言”，我期望它与机器架构有关，例如“x86”，但是你又说“虚拟机”，我期望它与指令集有关，例如“Java字节码”。请解释一下？ - Guy Coder

一种虚拟汇编语言，使编写编译器更容易，并且在编译后如果需要修改也更容易。 - Accumulator

stringstream 可能更好。 - harold

Answer 1

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

---

首先，大多数编译器不会生成文本形式的汇编代码，因为将代码串行化成汇编代码再由汇编器解析会很低效，你可能已经意识到了。在编译和汇编两个阶段中，可以选择拆分这两个阶段，但这并非必要。

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

• (a) 生成汇编代码作为一个树/指令对象数组，它们可以象征性地相互引用。在汇编阶段，需要将它们序列化为字节码/机器码。我推荐使用该方法，即使它使得编译器的架构稍微复杂一些。

• (b) 以缓冲区的方式生成汇编代码/机器码，并带有一些辅助函数；在这种情况下，你实际上没有单独的汇编阶段。我个人尝试过这种方法，在一个函数的范围内还不错，但在汇编之前无法确定一个函数的大小，可能会导致一些额外的困难。

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

---

让我们再考虑下if的例子，并通过检查现有编译器为简单的if/else分支生成的代码来进行分析：

请注意汇编代码中重叠的跳转 - 一个跳过了“taken”块，另一个跳过了“not-taken”块。

这些是相对跳转，因此要将它们汇编起来，我们需要知道跳转指令和目标之间有多少字节的指令。

以下示例使用策略(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]）而不是像串行化机器码那样使用字节偏移。我们将这些偏移计算留给汇编器处理。

还要注意，我们只在JumpInstruction可用时才设置它们的目标。

结尾处的NopInstruction只是为了给skip_nottaken跳转提供一个参照物。

那么，如何将这些跳转组装成真正的机器码/字节码呢？以下是一种可能性（非常基本的例子）：

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;
};

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

---

我希望这个简短的介绍能帮助你开始设计自己的编译器后端。显然，我并不建议您完全像我的示例那样编写编译器，但它应该会给您一些如何处理编译和组装非线性指令块的通用问题的思路。

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

祝你好运。

- Cauterite