阅读 chibicc 笔记

从 chibicc 中学习编译原理和指令集。

1写在前面
2Week 1
3Week 2
4Week 3
5未完待续......

DAY1 - 第一个提交

对应提交 0522e2d。

编译器可以帮助我们将一种语言转换为另外一种。对于 C 编译器而言，我们可以将 C 语言代码转换为对应 CPU 指令集上的汇编代码，之后又进一步转换为机器代码。

生成最小汇编

作为第一个提交，我们不输入 C 语言代码，相反，我们简单生成一个最小的汇编代码，如下：

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "%s: invalid number of arguments\n", argv[0]);
    return 1;
  }
  
  printf("  .globl main\n");
  printf("main:\n");
  printf("  mov $%d, %%rax\n", atoi(argv[1]));
  printf("  ret\n");
  return 0;
}

这里我们的 C 程序接受一个命令行参数（即 argv[1]），并将汇编代码输出到标准输出中。

如果我们将这段代码编译为 chibicc 可执行文件。那么对于如下的脚本而言：

./chibicc 0 > tmp.s || exit
gcc -static -o tmp tmp.s
./tmp

我们会首先在 tmp.s 中生成如下的汇编代码：

  .globl main
main:
  mov $0, %rax
  ret

这个汇编的语法是 AT&T 格式的。它通过 .globl 来将符号 main 作为全局符号暴露出去，这样链接器就能知道 main 函数在哪里。GCC 将汇编转换为对象文件，并通过链接来得到可执行文件 tmp。

这里的汇编中使用了两个指令，分别是 MOV 和 RET 指令，它们分别是：

MOV

移动。我们可以使用这个指令来将值从寄存器或者内存位置移动到寄存器或者内存位置（不能同时为内存位置）。其中源操作数可以是立即数。

这里 mov $0, %rax 的 $0 就是立即数，它会被编码到指令中。含义是将 0 移动到 RAX 寄存器中。这使得 RAX 寄存器的值为 0。

RET

我们使用这个从 CALL 指令导致的过程调用中返回。CALL 会将返回地址压入栈中，而 RET 可以从栈中取出返回地址，并将控制权转移到这个地址对应的指令。

这里的意思是返回到 main 函数的调用者。这一般由 libc 库提供，比如 glibc 等。例如在 glibc 中，我们提供了一个函数 __libc_start_call_main，它会真正调用 main 函数，而这里的 RET 指令就会直接将控制器返回给它。

这个代码中，我们定义了一个 main 函数，根据 System V ABI [2]，寄存器 RAX 被用于表示返回值，所以这个 main 函数简单地返回了 0。我们编译这段汇编并运行，而因为 main 函数的返回值就是运行这段程序的返回值，并且我们可以通过 shell 提供的 $? 变量来获取它，之后检查即可发现 $? 正好是 0。

一个简单的 Makefile

为了能够编译 chibicc，我们给出 Makefile 如下：

CFLAGS=-std=c11 -g -fno-common

chibicc: main.o
	$(CC) -o chibicc main.o $(LDFLAGS)
	
test: chibicc
	./test.sh
	
clean:
	rm -f chibicc *.o *~ tmp*
	
.PHONY: test clean

这里的 CFLAGS 表明：

  • 我们使用 C11 规范。
  • 带上一些调试信息。
  • 不使用 COMMON 块，来将未初始化的全局变量视为强符号，这能避免掉一些问题。值得一提的是，对于高版本 GCC 而言，这个选项是默认的。

GNU make 的内建规则中，我们使用 $(CC) $(CPPFLAGS) $(CFLAGS) -c 来编译对象文件，所以我们可以简单设置 CFLAGS 变量来影响编译过程。

一个简单的测试脚本

这里我们的测试脚本如下：

#!/bin/bash
assert() {
  expected="$1"
  input="$2"
  
  ./chibicc "$input" > tmp.s || exit
  gcc -static -o tmp tmp.s
  ./tmp
  actual="$?"
  
  if [ "$actual" = "$expected" ]; then
    echo "$input => $actual"
  else
    echo "$input => $expected expected, but got $actual"
    exit 1
  fi
}

assert 0 0
assert 42 42

echo OK

这里，我们通过 assert 函数来完成测试。我们生成汇编，编译为二进制文件，并检测生成程序的退出码是否符合预期。

DAY2 - 支持简单加法和减法

对应提交 bf7081f。

在前一天，我们编写了一个程序。当给定参数 11，它返回一个汇编程序。运行生成的汇编程序，它的返回码为 11。

今天我们希望能够给定一个简单的算式作为参数，比如 5+20-4，能够得到运行后返回码为 21 的汇编程序。我们希望能够将这个算式变为对应的一系列指令，由汇编程序完成计算。这里我们希望生成的汇编程序如下：

    .globl main
main:
    mov $5, %rax
    add $20, %rax
    sub $4, %rax
    ret

这里我们完全在 RAX 寄存器上操作，我们先赋值为表达式中的第一个数字，并且根据操作符来选择不同的指令（到底是 ADD 还是 SUB），不断地执行运算。以上面的汇编程序例子来说，它：

  • 使用 MOV 指令，让 RAX 寄存器为 5。
  • 使用 ADD 指令，让 RAX 寄存器加上 20。
  • 使用 SUB 指令，让 RAX 寄存器减去 4。
  • 最后返回。

我们在 DAY1 时已经讨论过 MOV 和 RET 指令了，这里有两个新的指令，我们使用它来进行运算，分别是：

ADD

执行加法。例如 add $20, %rax 表示计算 RAX 寄存器的值加上 20，并写入到 RAX 寄存器中。

SUB

执行减法。和 ADD 指令类似。

为此，我们变更了 chibicc.c 文件，在 main 函数中，使得其如下：

int main(int argc, char **argv) {
  // ...
  
  char *p = argv[1];

  printf("    .globl main\n");
  printf("main:\n");
  printf("    mov $%ld, %%rax\n", strtol(p, &p, 10));
  
  while (*p) {
    if (*p == '+') {
      p++;
      printf("    add $%ld, %%rax\n", strtol(p, &p, 10));
      continue;
    }
    
    if (*p == '-') {
      p++;
      printf("    sub $%ld, %%rax\n", strtol(p, &p, 10));
      continue;
    }
    
    fprintf(stderr, "unexpected character: '%c'\n", *p);
    return 1;
  }

  printf("  ret\n");

  // ...
}

新的逻辑很简单。

我们通过指针 p 来对传入的参数 argv[1] 进行迭代。迭代过程中，我们通过标准库的 strtol 函数来完成对字符串中数字的消费。除了第一个数字，其他的数字前都有 + 或者 -，这使得我们根据这个选择 ADD 指令或者 SUB 指令。

这里 strtol 函数签名如下：

long int strtol(const char *str, char **endpoint, int base)

这里 str 参数为我们想要消费的字符串，endpoint 参数被用于将消费掉的数字之后那个地址写入给定指针指向的位置，base 参数为进制数。这里我们使用 10 进制。通过令 str 为 p，令 endpoint 为 &p，我们使得每次消费完 p 指向的数字后，又让 p 指向数字之后的下一个字符。

这样，我们支持了生成简单的加法和减法。

DAY3 - 支持 tokenizer

对应提交 a1ab0ff。

今天我们尝试支持 tokenizer。即，我们会将输入先转换为多个 token，其中空格被忽略，而字符串被拆分并解释为更有意义的 token。

拆分 token 是非常符合直觉的。例如对于 5 + 20 - 4 而言，我们会认为它由以下 token 构成：

  • 数字字面量 5。
  • 加号 +。
  • 数字字面量 20。
  • 减号 -。
  • 数字字面量 4。

即我们有：

Tokenize

我们使用如下的结构来表示一个 token。

typedef enum {
  TK_PUNCT, // Punctuators
  TK_NUM,   // Numeric literals
  TK_EOF,   // End-of-file markers
} TokenKind;

// Token type
typedef struct Token Token;
struct Token {
  TokenKind kind; // Token kind
  Token *next;    // Next token
  int val;        // If kind is TK_NUM, its value
  char *loc;      // Token location
  int len;        // Token length
};

可以看到， token 被表示为在内存中的一个结构体 Token。每个 token 有几个属性：

  • 类别。一个枚举值。我们使用它判断 token 是否为数字，或者一个标点符号，或者被用来表示符号流的结尾。
  • 值。只有数字字面量 token 才有有效的值。
  • 位置。字段 loc 和 len 能够让我们知道这个 token 对应到字符流中的位置。
  • 下一个 token。字段 next 被用于指向下一个 token，这使得我们可以方便地使用链表的形式来表示这个流。

这样我们就能够表示一个 token 流了。Token 给了我们一个更加结构化的工具，是一种有益的抽象，这使得我们不需要直接处理字符串，而是处理更具有语义的 token。

我们使用 tokenize 函数来完成字符流到 token 流的转换，如下：

// Tokenize `p` and returns new tokens.
static Token *tokenize(char *p) {
  Token head = {};
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Numeric literal
    if (isdigit(*p)) {
      cur = cur->next = new_token(TK_NUM, p, p);
      char *q = p;
      cur->val = strtoul(p, &p, 10);
      cur->len = p - q;
      continue;
    }

    // Punctuator
    if (*p == '+' || *p == '-') {
      cur = cur->next = new_token(TK_PUNCT, p, p + 1);
      p++;
      continue;
    }

    error("invalid token");
  }

  cur = cur->next = new_token(TK_EOF, p, p);
  return head.next;
}

可以看到，我们在一个 while (*p) { ... } 循环中完成对字符串 p 的消费（它同时也是被用于迭代的指针）。我们是这么消费这个字符流的：

  • 我们判断第一个字符，如果它是空格的话，我们会直接忽略，并进入下一个循环。
  • 反之，如果它是一个数字字符的话，我们认为它可以和之后的多个字符构成了一个数字字面量 token。我们使用标准库函数 strtoul 来消费数字字面量，并进入下一个循环；
  • 最后，如果它是 + 或者 - 符号，那么我们认为它构成了一个标点符号 token，并进入下一个循环。
  • 如果什么都不是，则报错。

在消费中，会维护用于迭代的指针 p 和 token 流。 可以看到，我们会移动 p 指针，也同时往链表末尾加入新生成的 token。最后我们放置一个 TK_EOF token，并且返回这个 token 流。

可以看到，这个过程中，我们使用 new_token 来构建一个 token，它定义如下：

// Create a new token.
static Token *new_token(TokenKind kind, char *start, char *end) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->loc = start;
  tok->len = end - start;
  return tok;
}

它使用的是 calloc 来分配内存（使用 calloc 相比 malloc 而言，分配到的内存为全 0 的）。还有一点需要提及的是，我们只定义了分配 Token 的内存，而没有释放它们，事实上 chibicc 作者把这个工作交给了操作系统。当程序执行完成后由操作系统来完成内存的回收。我们不会调用 free 函数。

可以看到，我们也使用 error 函数来报错。它使用变长参数来报错并退出：

// Reports an error and exit.
static void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

这使得我们可以以类似 printf 的形式调用 error，并以 1 的返回码退出进程。其中 ... 被用于表示 C 语言的变长参数。

接下来是 main 函数，我们简单地从消费字符串变换为消费 token 流了：

int main(int argc, char **argv) {
  if (argc != 2)
    error("%s: invalid number of arguments", argv[0]);

  Token *tok = tokenize(argv[1]);

  printf("  .globl main\n");
  printf("main:\n");

  // The first token must be a number
  printf("  mov $%d, %%rax\n", get_number(tok));
  tok = tok->next;

  // ... followed by either `+ <number>` or `- <number>`.
  while (tok->kind != TK_EOF) {
    if (equal(tok, "+")) {
      printf("  add $%d, %%rax\n", get_number(tok->next));
      tok = tok->next->next;
      continue;
    }

    tok = skip(tok, "-");
    printf("  sub $%d, %%rax\n", get_number(tok));
    tok = tok->next;
  }

  printf("  ret\n");
  return 0;
}

这里还使用到了一些辅助函数（我们没有放出它的定义，感兴趣的读者可以阅览源文件），为：

  • get_number。 从 TK_NUM token 中获取数字的值。
  • equal。比较 token 对应的字符串是否和给定字符串一致。
  • skip。比较 token 对应的字符串是否和给定字符串一致，并且如果一致的话，就通过 tok = tok->next 来对其进行消费。

DAY4 - 更好的错误消息

对应提交 cc5a6d9。

今天我们尝试支持更好的错误消息，这使得有：

$ ./chibicc 1+foo
1+foo
  ^ expected a number

为了支持这个，我们使用了 verror_at 和相关包装函数代替了之前的 error 函数来抛出错误：

// Input string
static char *current_input;

// Reports an error location and exit.
static void verror_at(char *loc, char *fmt, va_list ap) {
  int pos = loc - current_input;
  fprintf(stderr, "%s\n", current_input);
  fprintf(stderr, "%*s", pos, ""); // print pos spaces.
  fprintf(stderr, "^ ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

其中 current_input 为输入（在 main 函数中，我们会让其赋值为 argv[1]）。然后 verror_at 接收一个额外的参数 loc，它被用于指出出错的地方。verror_at 会在标准错误中输出传入的表达式、一个箭头（用于指出出错的地方）、以及错误消息。

有意思的是，我们使用 %*s 来打印空格，它接收两个参数，分别是宽度和想要输出的字符串（因为没有什么需要输出的，所以设置为空字符串）。

包装函数 error_at 和 error_tok 定义如下：

static void error_at(char *loc, char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  verror_at(loc, fmt, ap);
}

static void error_tok(Token *tok, char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  verror_at(tok->loc, fmt, ap);
}

这使得我们可以很容易使用新的函数来代替 error 函数来抛出错误消息。比如原来的 get_number 函数是这样的：

// Ensure that the current token is TK_NUM.
static int get_number(Token *tok) {
  if (tok->kind != TK_NUM)
    error("expected a number");
  return tok->val;
}

原先我们使用 error 函数来抛出错误。更改后，它就简单使用 error_tok 来报错：

// Ensure that the current token is TK_NUM.
static int get_number(Token *tok) {
  if (tok->kind != TK_NUM)
    error_tok(tok, "expected a number");
  return tok->val;
}

就这么简单。

DAY5 - 支持简单的乘法、除法和括号

对应提交 84cfcaf。

今天我们开始试着支持 5 + 6 * 7 和 5 * (9 - 6) 这种更加复杂的表达式。我们很容易将这种表达式看作一棵树；同时，如果我们真的能将其转换为一棵树，那么也更容易处理它。比如，5 + 6 * 7 可以视为：

AST

我们将这种树称为 AST，即抽象语法树。因为引入了 AST，我们的整个编译流程现在则多了一步。现在，我们整个编译流程变为了：

  1. 首先将字符流先转换为更加结构化的 token 流。
  2. 接着，token 流会被转化为 AST，这时，我们使用树来表示程序。
  3. 最后，我们将 AST 转换为汇编代码。

AST 的定义

我们需要在 C 语言中表示 AST。

我们首先需要定义 AST 相关 C 语言类型。可以看到 AST 由多个节点和多个边构成，其中节点被定义为：

typedef struct Node Node;
struct Node {
  NodeKind kind; // Node kind
  Node *lhs;     // Left-hand side
  Node *rhs;     // Right-hand side
  int val;       // Used if kind == ND_NUM
};

可以看到 kind 被用于表示节点类型，这使得我们支持多种节点类型，包括加法节点、减法节点，等等。它为一个枚举，目前定义如下：

typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_NUM, // Integer
} NodeKind;

目前我们只有 5 种 AST 节点。

我们使用指针来表示 AST 的边。目前节点要不然有两个出边，要不然没有出边。比如，对于加法节点，我们使用 lhs 和 rhs 来分别指向左右子树。同时，我们也使用 val 字段来表示节点内部的值。只有 ND_NUM 节点的 val 字段是有意义的。

为了简化 AST 的构造，我们有一系列 AST 节点 Node 的构造函数：new_node，new_binary 和 new_num。它们的含义为：

  • new_node。用于初始化一个没有左右子树的 Node 对象，并返回指针。
  • new_binary。用于初始化一个有左右子树的 Node 对象，并返回指针。
  • new_num。用于初始化一个 ND_NUM 的 Node 对象，并返回指针。

这些构造函数都很简单。比如 new_node 实现如下：

static Node *new_node(NodeKind kind) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = kind;
  return node;
}

其他函数就不一一列举了。

举例来说，对于 5 + 6 * 7 这种表达式，我们可以通过下面的语句来构造对应的 AST：

new_binary(ND_ADD, new_num(5), new_binary(ND_MUL, new_num(6), new_num(7)))

从 token 中构建 AST

我们定义了 AST，接下来就是给出如何从 token 流中构建 AST。

这里我们给出一个函数 expr，它负责从 token 流中构造表达式对应的 AST。它接受一个 Token** 类型的参数 rest，用于返回解析后剩余的 token；还接受一个 Token* 类型的参数 tok，用于表示当前开始解析的位置。注意，如果消费了 token，那么我们需要使用 *rest = /* ... */; 语句来更新剩余 token 的位置。

// expr = mul ("+" mul | "-" mul)*
static Node *expr(Token **rest, Token *tok) {
  Node *node = mul(&tok, tok);

  for (;;) {
    if (equal(tok, "+")) {
      node = new_binary(ND_ADD, node, mul(&tok, tok->next));
      continue;
    }

    if (equal(tok, "-")) {
      node = new_binary(ND_SUB, node, mul(&tok, tok->next));
      continue;
    }

    *rest = tok;
    return node;
  }
}

这里的含义很明显：

  • 先使用 mul 消费一个乘法或者除法表达式（注意，这不表示它包含乘法或者除法操作符，比如 mul 也可以简单消费 5），并将得到的 AST 存储在 node 中。
  • 然后不断循环。如果遇到了 mul 无法消费的 + 或者 - 符号，那么跳过这个符号，将剩下的 token 流传入来得到对应 mul 对应的 AST，然后将先前得到的 AST，和新的 AST，作为子树组合为新的 ND_ADD 或者 ND_SUB 的 AST，并赋值给 node。
  • 这样，我们一直循环，直到遇到了非预期的符号。比如 TK_EOF 符号。

这里注释即 expr 函数对应的 BNF 语法，即所有表达式都可以表达为多个乘法（或除法）的项的和（或者差）。

这里给出 mul 函数对应的 BNF 语法：

mul = primary ("*" primary | "/" primary)*

然后是 primary 函数对应的 BNF 语法。

primary = "(" expr ")" | num

其中 mul 和 expr 在代码构成上基本一致，这里就不再展示。而 primary 函数的实现为：

// primary = "(" expr ")" | num
static Node *primary(Token **rest, Token *tok) {
  if (equal(tok, "(")) {
    Node *node = expr(&tok, tok->next);
    *rest = skip(tok, ")");
    return node;
  }

  if (tok->kind == TK_NUM) {
    Node *node = new_num(tok->val);
    *rest = tok->next;
    return node;
  }

  error_tok(tok, "expected an expression");
}

即，如果是 “(“ 符号对应的 token，那么我们会尝试消费表达式，因为表达式遇到非预期的 “)“ token 会停止，那么我们再跳过 “)“ 符号，这样我们就完成了 BNF 语法的第一个分支的实现。否则我们会尝试消费一个数字。

使用 AST 生成汇编

我们现在拿到了 AST，那么下一步就是基于 AST 来生成汇编。

在 DAY2 中我们知道，5 + 20 - 4 可以简单生成如下汇编：

    .globl main
main:
    mov $5, %rax
    add $20, %rax
    sub $4, %rax
    ret

可以看到，我们只用了一个寄存器 RAX。但是如果我们需要支持相对复杂的表达式，只有一个寄存器 RAX 是远远不够的。比如 5 * 4 + 12 / 4，那么我们在算加法前，需要先求出 5 * 4 和 12 / 4 表达式的值，最后再加起来。这的确可以使用两个寄存器来解决，那如果我们将 5 个乘法表达式加起来呢？为了避免过于复杂，我们可以使用 PUSH 指令和 POP 指令。我们使用 PUSH 指令可以将寄存器的值放在栈上，然后使用 POP 指令来从栈上弹出一个值，并放在指定寄存器中。可能不太好理解，这里我们给出一个更为具体的例子，即对于 5 * 4 + 12 / 4，我们可以将其表示为：

    .globl main
main:
    ; (1)
    mov $4, %rax       ; Registers = { %rax: 4 }; Stack = [].
    push %rax          ; Registers = { %rax: 4 }; Stack = [4].
    mov $12, %rax      ; Registers = { %rax: 12 }; Stack = [4].
    pop %rdi           ; Registers = { %rax: 12, %rdi: 4 }; Stack = [].
    cqo                ;
    idiv %rdi          ; Registers = { %rax: 3 }; Stack = [].

    ; (2)
    push %rax          ; Registers = { %rax: 3 }; Stack = [3].

    ; (3)
    mov $4, %rax       ; Registers = { %rax: 4 }; Stack = [3].
    push %rax          ; Registers = { %rax: 4 }; Stack = [3, 4].
    mov $5, %rax       ; Registers = { %rax: 5 }; Stack = [3, 4].
    pop %rdi           ; Registers = { %rax: 5, %rdi: 4 }; Stack = [3].
    imul %rdi, %rax    ; Registers = { %rax: 20 }; Stack = [3].

    ; (4)
    pop %rdi           ; Registers = { %rax: 20, %rdi: 3 }; Stack = [].
    add %rdi, %rax     ; Registers = { %rax: 23 }; Stack = [].

    ret

在汇编中，我们给出了对应注释，用于表示指令执行完毕后我们关心的寄存器的值，和栈上的值。这些指令被我划分为 4 个部分，分别是：

  1. 计算出 12 / 4 表达式的值，并将结果放置在 RAX 寄存器中。
  2. 将表达式存放在栈上供后续使用。
  3. 计算出 5 * 4 表达式的值，并将结果放置在 RAX 寄存器中。
  4. 将栈上对应的 12 / 4 对应的值放置到 RDI 寄存器中，并执行加法，并将结果放置在 RAX 寄存器中。

可以看到，我们只需要两个寄存器和一个栈，就能计算这种简单的算术表达式。

对于一个简单的整数，例如 5，我们只需要生成 mov $5, %rax 即可将结果放置在 RAX 寄存器中。

而对于一个有左右子树的 AST 节点而言，结果相对复杂，但其对应汇编逻辑也依然很简洁：

  1. 先计算右子树的值，并将其放置在 RAX 寄存器中。
  2. 将右子树的值 PUSH 到栈顶。
  3. 再计算左子树的值，并将其放置在 RAX 寄存器中。
  4. 然后将右子树的值从栈顶 POP 出来，将其放置在 RDI 寄存器中。
  5. 最后根据 RAX、RDI 寄存器的值，根据节点类型生成对应汇编，并使得最后结果放置在 RAX 寄存器中。

我们使用 gen_expr 函数来表示根据 AST 来生成汇编程序的逻辑：

static void gen_expr(Node *node) {
  if (node->kind == ND_NUM) {
    printf("  mov $%d, %%rax\n", node->val);
    return;
  }

  gen_expr(node->rhs);
  push();
  gen_expr(node->lhs);
  pop("%rdi");

  switch (node->kind) {
  case ND_ADD:
    printf("  add %%rdi, %%rax\n");
    return;
  case ND_SUB:
    printf("  sub %%rdi, %%rax\n");
    return;
  case ND_MUL:
    printf("  imul %%rdi, %%rax\n");
    return;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv %%rdi\n");
    return;
  }

  error("invalid expression");
}

能够看到，我们选择将 AST 树转换为一段汇编指令，这些汇编指令会计算 AST 树，并将结果存储在 RAX 寄存器中。如果 AST 节点有左右子树，那么我们先转换这些子树，并使用 PUSH 和 POP 指令，使得子树最后的值分别存储在 RAX 和 RDI 中，并进一步计算。

其中 push 和 pop 的定义如下：

static int depth;

static void push(void) {
  printf("  push %%rax\n");
  depth++;
}

static void pop(char *arg) {
  printf("  pop %s\n", arg);
  depth--;
}

这里我们使用到了一些新的指令，如下：

IMUL

执行有符号乘法。例如 imul %rdi, %rax 表示将 RDI 和 RAX 两个寄存器的值相乘，并写入到 RAX 寄存器中。

CQO

将 RAX 寄存器符号扩展到 RDX:RAX 中。这使得我们可以使用两个寄存器，即 RDX 和 RAX，一共 128 位来表示一个数。这是 IDIV 指令的要求。

IDIV

执行有符号除法。它只带一个操作数，即除数，而被除数从 RDX:RAX 中获取。对于 idiv r/m64，RDX:RAX 共同构成 128 位被除数，商会放在 RAX 中，而余数会放在 RDX 中。

PUSH

将值推入到栈顶。更进一步地说，将值写入到 SS:rSP 指向的内存位置，并更新 SS:rSP 来指向新的位置。

POP

这是 PUSH 的逆操作。即从栈顶弹出值并写入到给出的寄存器中。

DAY6 - 支持 unary plus 和 minus

对应提交 bf9ab52。

今天我们会支持一元操作符，现在我们就能处理 -10 + 20 这种表达式了。

我们会用到新的指令 NEG，有：

NEG

执行二进制补码求负。等价于使用 0 减去指令数。

为此我们：

  • 让 AST 支持 ND_NEG 节点。这种类型的节点只需要一个子树，我们使用 lhs 来指向子树。
  • 我们提供了 new_unary 构造函数，和 DAY5 的 new_binary 类似，只不过只生成有一个子树的 AST 节点。

回顾一下，之前的 BNF 如下：

expr    = mul ("+" mul | "-" mul)*
mul     = primary ("*" primary | "/" primary)*
primary = "(" expr ")" | num

为了支持一元表达式，我们将其更新为：

expr    = mul ("+" mul | "-" mul)*
mul     = unary ("*" unary | "/" unary)*
unary   = ("+" | "-") unary
        | primary
primary = "(" expr ")" | num

其中 unary 对应的生成 AST 的函数如下：

static Node *unary(Token **rest, Token *tok) {
  if (equal(tok, "+"))
    return unary(rest, tok->next);

  if (equal(tok, "-"))
    return new_unary(ND_NEG, unary(rest, tok->next));

  return primary(rest, tok);
}

而 mul 函数的变更是显然的，这里不再赘述。

我们也更新 gen_expr 函数，使得其能够处理 ND_NEG 节点：

static void gen_expr(Node *node) {
  switch (node->kind) {
  case ND_NUM:
    printf("  mov $%d, %%rax\n", node->val);
    return;
  case ND_NEG:
    gen_expr(node->lhs);
    printf("  neg %%rax\n");
    return;
  }

  // ...
}

可以看到，对于 ND_NEG 节点，我们：

  • 先生成子树的汇编代码。我们知道，子树的汇编代码会把计算结果保存在寄存器 %rax 中；
  • 生成一行汇编代码 neg %rax。

DAY7 - 支持比较

对应提交 25b4b85。

今天我们尝试支持 ==、!=、<=、>=、>、< 共 6 种比较操作符。在 C 语言中我们使用 0 来表示 false，使用 1 来表示 true（准确地说，任何非零的都表示 true，但是这里如果比较表达式为真的话，我们返回的是 1），所以这些比较操作符能够正确地被编译并且输出正确的 0 或者 1。

Token 流阶段

这里我们需要为这些操作符依然生成 TK_PUNCT token，不过之前我们的操作符，比如 +、- 都是一个字节长的，所以我们现在给出 read_punct 来专门读取 token，它返回我们需要读取的字节数：

static bool startswith(char *p, char *q) {
  return strncmp(p, q, strlen(q)) == 0;
}

// Read a punctuator token from p and returns its length.
static int read_punct(char *p) {
  if (startswith(p, "==") || startswith(p, "!=") ||
      startswith(p, "<=") || startswith(p, ">="))
    return 2;

  return ispunct(*p) ? 1 : 0;
}

我们这样来读取操作符：

static Token *tokenize(void) {
  // ...
  
  while (*p) {
    // ...
    
    // Punctuators
    int punct_len = read_punct(p);
    if (punct_len) {
      cur = cur->next = new_token(TK_PUNCT, p, p + punct_len);
      p += cur->len;
      continue;
    }
    
    // ...
  }
  
  // ...
}

可以看到 read_punct 在不成功的时候返回 0，否则返回操作符号的长度。这样我们可以在非 0 的时候通过 new_token(TK_PUNCT, p, p + punct_len) 表达式来构造比较符 token 了。

AST 阶段

我们也需要修改 AST 的算法，从而支持这 6 种操作。这里我们新加了 ND_EQ、ND_NE、ND_LT 和 ND_LE 这四种新 node。同时，我们的 BNF 表达式也进行了变更：

expr       = equality
equality   = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add        = mul ("+" mul | "-" mul)*
mul        = unary ("*" unary | "/" unary)*
unary      = ("+" | "-") unary
           | primary
primary    = "(" expr ")" | num

参考 DAY5 了解如何编写 equality、relational 和 add 函数。

值得注意到的是，我们可以使用 ND_LT 来表示 6 > 3 这种表达式，即 6 > 3 和 3 < 6 是等价的。这使得我们可以使用较少的节点类型来表示它们。

汇编生成阶段

我们更新 gen_expr 函数，使得：

static void gen_expr(Node *node) {
  switch (node->kind) {
  // ...
 
  case ND_EQ:
  case ND_NE:
  case ND_LT:
  case ND_LE:
    printf("  cmp %%rdi, %%rax\n");

    if (node->kind == ND_EQ)
      printf("  sete %%al\n");
    else if (node->kind == ND_NE)
      printf("  setne %%al\n");
    else if (node->kind == ND_LT)
      printf("  setl %%al\n");
    else if (node->kind == ND_LE)
      printf("  setle %%al\n");

    printf("  movzb %%al, %%rax\n");
    return; 
  }
  
  // ...
}

这里我们有一些新的指令：

CMP

比较。它和 SUB 指令类似，它也会使用目标操作数减去源操作数。不过它并不会将结果值存储在目标操作数中，它的效果是设置或清除相关算术标志位（OF、SF、ZF、AF、CF、PF）。

SETcc

我们会根据条件，来设置字节操作数为 1 或者 0。

比如 SETO 会测试 OF flag，其会在溢出的时候设置为 1。

在本例子中，有：

  • SETE。当相等时设置字节。
  • SETNE。当不相等时设置字节。
  • SETL。当小于时设置字节。
  • SETLE。当小于等于时设置字节。

在这里，我们使用 %al 作为操作数，它本质上是 RAX 寄存器的最低一个字节。

MOVZX

移动，使用带零扩展（Zero-Extend）。

在这里，我们使用 movzb %al, %rax，本质上是让 RAX 除了最低字节之外的其他位都清零。

例如，对于表达式 0 == 1，我们会生成如下的汇编代码：

    .globl main
main:
    ; Let %rax be 0, and %rdi be 1.
    mov $1, %rax
    push %rax
    mov $0, %rax
    pop %rdi
    
    ; Compare and store the result in %rax.
    cmp %rdi, %rax
    sete %al
    movzb %al, %rax

链接和引用

  1. AMD Docs / AMD64 Architecture Programmer’s Manual Volume 1: Application Programming: https://docs.amd.com/v/u/en-US/24592_3.24
  2. LinuxBase / System V ABI: https://refspecs.linuxbase.org/elf/x86_64-abi-0.99.pdf
上一篇写在前面下一篇Week 2