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

Answer 1

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

<小时/>

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

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

• (a) 将程序集生成为指令对象的树/数组，它们可以象征性地相互引用。在汇编阶段，这些需要被序列化为字节码/机器码。我推荐这种方法，即使它会使编译器的体系结构变得更加复杂。

• (b) 将程序集作为机器码/字节码生成到缓冲区中，并带有一些辅助函数；在这种情况下，您实际上没有单独的组装阶段。我亲自尝试过这种方法，在单个函数的范围内它还不错，但由于不知道函数在组装之前会有多大，可能会造成一些额外的困难。

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

<小时/>

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

请注意反汇编中的重叠跳转 - 一个跳过“taken” block ，另一个跳过“not-taken” block 。

这些是相对跳转，因此为了组装它们，我们需要知道跳转指令和目标之间有多少字节指令。

以下是使用策略(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;
};

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

<小时/>

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

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

祝你好运。