MENU

编译器笔记--代码生成

July 15, 2023 • 阅读: 880 • 笔记&折腾

在扫描和解析源代码、构造 AST、执行类型检查并生成中间表示之后，是生成代码。

首先，我们将采用一种简单的方法来生成代码，其中我们单独考虑程序的每个元素。每个表达式和语句都将作为独立单元生成，而不参考其邻居。这简单明了，但是比较保守，并且会导致大量的非优化代码。但它会起作用，并为您提供思考更复杂技术的起点。
以下示例将重点关注 X86-64 汇编代码，但根据需要它们并不难适应 ARM 和其他汇编语言。与前面的阶段一样，我们将为程序的每个元素定义一个方法。 decl_codegen 将为声明生成代码，为语句调用 stmt_codegen，为表达式调用 expr_codegen，等等。

一旦您学习了这种基本的代码生成方法，就可以在其中考虑更复杂的方法来生成更高度优化的代码。

支持函数

在生成一些代码之前，我们需要设置一些支持函数来跟踪一些细节。要生成表达式，您将需要一些临时寄存器来保存运算符之间的中间值。编写三个函数，接口如下：

int scratch_alloc();
void scratch_free( int r );
const char * scratch_name( int r );

我们预留每个寄存器都有一个目的：一些用于函数参数，一些用于堆栈帧，有些可用于临时值。取出这些暂存寄存器并将它们放入如下表中：

r023456
name%rbx%r10%r11%r12%r13%r15
正在使用X X

然后，写一个 scratch_alloc 函数在表中找到一个未使用的寄存器，将其标记为正在使用，并返回寄存器号r。scratch_free 将指定的寄存器标记为可用。 scratch_name 函数给定其编号 r 返回寄存器的名称。用完暂存寄存器是可能的，如果 scratch_alloc 无法找到空闲寄存器，只需发出错误消息并停止。
接下来，我们需要生成大量唯一的匿名标签来指示跳转和条件分支的目标。编写两个函数来生成和显示标签：

int label_create();
const char * label_name( int label );

label_create 只是增加全局计数器并返回当前值。 label_name 以字符串形式返回该标签，因此标签 15 表示为“.L15”。

最后，我们需要一种从程序中的符号映射到代表这些符号的汇编语言代码的方法。为此，编写一个函数来生成符号的地址：

const char * symbol_codegen( struct symbol *s );

该函数返回一个字符串，它是指令的片段，表示给定符号所需的地址计算。编写 symbol_codegen 首先检查符号的范围。全局变量很简单：汇编语言中的名称与源语言中的名称相同。如果您有一个表示全局变量 count:integer 的符号结构，则 symbol_codegen 应该简单地返回 count 。
表示局部变量和函数参数的符号应该返回一个地址计算，该地址计算产生该局部变量或参数在堆栈上的位置。其基础是在类型检查阶段，您为每个符号分配一个唯一的编号，从参数开始，然后是每个局部变量。例如，假设您有以下函数定义：

f: function void ( x: integer, y: integer ) =
{
    z: integer = 10;
    return x + y + z;
}

在本例中，x 被指定为位置 0，y 为位置 1，z 为位置 2。根据 X86-64 处理器上的堆栈布局。位置 0 位于地址 -8(%rbp) ，位置 1 位于 -16(%rbp) ，位置 2 位于 -24(%rbp) 。
鉴于此，您现在可以扩展 symbol_codegen 以返回描述局部变量和参数的精确堆栈地址的字符串，只要知道其在堆栈帧中的位置。

生成表达式

为表达式生成汇编代码的基本方法是执行 AST 或 DAG 的后序遍历，并为每个节点发出一条或多条指令。主要思想是跟踪存储每个中间值的寄存器。为此，请向 AST 或 DAG 节点结构添加一个 reg 字段，该字段将保存 scratch_alloc 返回的寄存器的编号。当您访问每个节点时，发出一条指令并将包含该值的寄存器编号放入 reg 字段中。当不再需要该节点时，调用 scratch free 将其释放reg字段中的寄存器。

假设我们要为以下 DAG 生成 X86 代码，其中a、b 和 c 是全局整数：

后序遍历将按以下顺序访问节点：

  1. 访问a节点。调用 scratch_alloc 分配一个新的寄存器（0）并将其保存在 node->reg 中。然后发出指令 MOVQ a, R0 将值加载到寄存器 0 中。
  2. 访问3节点。调用 scratch_alloc 分配一个新寄存器(1) 并发出指令MOVQ $3, R1 。
  3. 访问IADD节点。通过检查该节点的两个子节点，我们可以看到它们的值存储在寄存器 R0 和 R1 中，因此我们发出一条指令将它们相加：ADDQ R0, R1 。这是一条破坏性的双地址指令，将结果保留在 R1 中。
  4. 访问b节点。调用 scratch_alloc 分配一个新寄存器(0) 并发出 MOVQ b, R0 。
  5. 访问ISUB节点。发出 SUBQ R0、R1，将结果保留在 R1 中，并释放寄存器 R0。
  6. 访问 c 节点，但不发出任何内容，因为它是赋值的目标。
  7. 访问 ASSIGN 节点并发出 MOVQ R1，c 。

这是 scratch_name 提供的实际寄存器名称相同的代码:

MOVQ a, %rbx
MOVQ $3, %r10
ADDQ %r10, %rbx
MOVQ b, %rbx
SUBQ %rbx, %r10
MOVQ %r10, c

下面是如何用代码实现它。编写一个名为 expr_codegen 的函数，该函数首先为其左右子节点递归调用 expr_codegen 。这将导致每个子进程生成代码，以便将结果保留在 register 字段中注明的寄存器编号中。然后，当前节点使用这些寄存器生成代码，并释放不再需要的寄存器。以下给出了这种方法的框架。

void expr_codegen( struct expr *e )
{
    if(!e) return;
    switch(e->kind) {
        // Leaf node: allocate register and load value.
        case EXPR_NAME:
            e->reg = scratch_alloc();
            printf("MOVQ %s, %s\n",
                symbol_codegen(e->symbol),
                scratch_name(e->reg));
            break;
        // Interior node: generate children, then add them.
        case EXPR_ADD:
            expr_codegen(e->left);
            expr_codegen(e->right);
            printf("ADDQ %s, %s\n",
                scratch_name(e->left->reg),
                scratch_name(e->right->reg));
            e->reg = e->right->reg;
            scratch_free(e->left->reg);
            break;
        case EXPR_ASSIGN:
            expr_codegen(e->left);
            printf("MOVQ %s, %s\n",
                scratch_name(e->left->reg),
                symbol_codegen(e->right->symbol));
            e->reg = e->left->reg;
            break;
        . . .
    }
}

基本流程还需要一些额外的改进。首先，并非所有符号都是简单的全局变量。当符号构成指令的一部分时，使用 symbol_codegen 返回给出该符号特定地址的字符串。例如，如果 a 是函数的第一个参数，则序列中的第一条指令将如下所示：

MOVQ -8(%rbp), %rbx

其次，DAG中的一些节点可能需要多个指令，以便处理指令集的特殊性。X86 IMUL 仅采用一个参数，因为第一个参数始终是 %rax ，并且结果始终放置在 %rax 中，溢出位于 %rdx 中。要执行乘法，我们必须将一个子寄存器移至 %rax，与另一个子寄存器相乘，然后将结果从 %rax 移至目标暂存寄存器。例如，表达式 (x*10) 将翻译为：

MOV $10, %rbx
MOV x, %r10
MOV %rbx, %rax
IMUL %r10
MOV %rax, %r11

当然，这也意味着在进行乘法时 %rax 和 %rdx 不能用于其他目的。由于我们有大量的暂存寄存器可供使用，因此我们不会在基本代码生成器中将 %rdx 用于任何其他目的。

第三，我们如何调用函数？回想一下，函数由单个 CALL 节点表示，每个参数都位于不平衡的 ARG 节点树中。下图给出了表示表达式 a=f(10,b+c) 的 DAG 示例。

代码生成器必须评估每个 ARG 节点，计算每个左子节点的值。如果机器有堆栈调用约定，则每个 ARG 节点对应于堆栈上的 PUSH。如果机器有寄存器调用约定，则生成所有参数，然后在生成所有参数后将每个参数复制到适当的参数寄存器中。然后，在保存所有调用者保存的寄存器后，对函数名称发出 CALL。当函数调用返回时，将值从返回寄存器 (%rax) 移动到新分配的暂存寄存器中，并恢复调用者保存的寄存器。

生成语句

现在我们已经将表达式生成封装到单个函数 expr_codegen 中，我们可以开始构建依赖于表达式的更大的代码结构。 stmt_codegen 将为所有控制流语句创建代码。首先为 stmt_codegen 编写一个框架，如下所示：

void stmt_codegen( struct stmt *s )
{
    if(!s) return;
    switch(s->kind) {
        case STMT_EXPR:
            ...
            break;
        case STMT_DECL:
            ...
            break;
        ...
    }
    stmt_codegen(s->next);
}

现在依次考虑每种语句，从简单的情况开始。如果该语句描述了局部变量的声明 STMT_DECL，则只需通过调用 decl_codegen 来委托该声明：

case STMT_DECL:
    decl_codegen(s->decl);
    break;

由表达式 (STMT_EXPR) 组成的语句只需要我们对该表达式调用 expr_codegen，然后释放包含该表达式顶级值的暂存寄存器。 （事实上​​，每次调用 expr_codegen 时，都应该释放暂存寄存器。）

case STMT_EXPR:
    expr_codegen(s->expr);
    scratch_free(s->expr->reg);
    break;

return 语句必须计算一个表达式，将其移动到返回值 %rax 的指定寄存器中，然后跳转到函数尾声，这将展开堆栈并返回到调用点。

case STMT_RETURN:
    expr_codegen(s->expr);
    printf("MOV %s, %%rax\n",scratch_name(s->expr->reg));
    printf("JMP .%s_epilogue\n",function_name);
    scratch_free(s->expr->reg);
    break;

控制流语句更有趣。首先考虑我们希望输出的汇编语言是什么样子，然后逆向工作以获得生成它的代码是很有用的。
这是条件语句的模板：

if ( expr ) {
    true-statements
} else {
    false-statements
}

为了在汇编中表达这一点，我们必须计算控制表达式，以便其值驻留在已知的寄存器中。然后使用 CMP 表达式来测试该值是否等于零 (false)。如果表达式为假，那么我们必须用JE（jump-if-equal）语句跳转到该语句的假分支。否则，我们将继续执行语句的 true 分支。在 true 语句的末尾，我们必须 JMP 越过 else 主体到语句的末尾。

    expr
    CMP $0, register
    JE false-label
    true-statements
    JMP done-label
false-label :
    false-statements
done-label :

一旦有了所需代码的框架，编写代码生成器就很容易了。首先，生成两个新标签，然后为每个表达式调用 expr_codegen，为每个语句调用 stmt_codegen，并根据需要替换一些附加指令以形成整体结构。

case STMT_IF:
    int else_label = label_create();
    int done_label = label_create();
    expr_codegen(s->expr);
    printf("CMP $0, %s\n",scratch_name(s->expr->reg));
    scratch_free(s->expr->reg);
    printf("JE %s\n",label_name(else_label));
    stmt_codegen(s->body);
    printf("JMP %s\n",label_name(done_label));
    printf("%s:\n",label_name(else_label));
    stmt_codegen(s->else_body);
    printf("%s:\n",label_name(done_label));
    break;

可以使用类似的方法来生成循环。这是 for 循环的模板：

for ( init-expr ; expr ; next-expr ) {
    body-statements
}

这是相应的汇编模板。首先，评估初始化表达式。然后，在循环的每次迭代中，计算控制表达式。如果为 false，则跳转到循环末尾。如果不是，则执行循环体，然后计算下一个表达式。

    init-expr
top-label:
    expr
    CMP $0, register
    JE done-label
    body-statements
    next-expression
    JMP top-label
done-label :

以下是它的简单代码生成器：

case STMT_FOR:
    int top_label = label_create();
    int done_label = label_create();
    expr_codegen(s->init_expr);
    printf("%s:\n",label_name(top_label));
    expr_codegen(s->expr);
    printf("CMP $0, %s\n",scratch_name(s->expr->reg));
    scratch_free(s->expr->reg);
    printf("JE %s\n",label_name(done_label));
    stmt_codegen(s->body);
    stmt_codegen(s->next_expr);
    printf("JMP %s\n",label_name(top_label));
    printf("%s:\n",label_name(done_label));
    break;

条件表达式

条件表达式（小于、大于、等于等）比较两个值并返回布尔值。它们最常出现在控制流表达式中，但也可以用作简单值，案例（ b: boolean = x < y; ）。
问题在于没有一条指令可以简单地执行比较并将布尔结果放入寄存器中。相反，您必须绕很远的路并创建一个控制流构造来比较两个表达式，然后构造所需的结果。
例如，如果您有这样的条件表达式：left-expr < right-expr
然后根据这个模板生成代码：

    left-expr
    right-expr
    CMP left-register, right-register
    JLT true-label
    MOV false, result-register
    JMP done-label
true-label:
    MOV true, result-register
done-label:

当然，对于不同的条件运算符，在适当的地方使用不同的跳转指令。只需稍加变化，您就可以使用相同的方法来实现许多语言中的三元条件运算符 (x?a:b )。

生成声明

声明可以分为三种情况：全局变量声明、局部变量声明和全局函数声明。

全局数据声明只是发出一个标签以及保留必要空间的合适指令和初始化程序（如果需要）的问题。例如，全局范围内的这些声明：

i: integer = 10;
s: string = "hello";
b: array [4] boolean = {true, false, true, false};

应该产生这些输出指令：

.data
i: .quad 10
s: .string "hello"
b: .quad 1, 0, 1, 0

请注意，全局变量声明只能由常量值（而不是通用表达式）初始化，因为程序的数据部分只能包含常量（而不是代码）。如果程序员不小心将代码放入初始化程序中，那么类型检查器应该发现这一点并在代码生成开始之前引发错误。

发出局部变量声明要容易得多。 （只有当 stmt_codegen 在函数声明内调用 decl_codegen 时，才会发生这种情况。）在这里，您可以假设函数序言已经为局部变量建立了空间，因此不需要堆栈操作。但是，如果变量声明具有初始化表达式 (x:integer=y*10; )，则必须为该表达式生成代码，将其存储在局部变量中，并释放寄存器。

函数声明是最后一部分。要生成函数，必须发出带有函数名称的标签，后跟函数序言。序言必须考虑到参数和局部变量的数量，在堆栈上留出适当的空间。接下来是函数主体，然后是函数尾声。尾声应该有一个独特的标签，以便返回语句可以轻松跳转到那里。

编译器编译Compiler
Leave a Comment