chibiccを読む～Cコンパイラコードリーディング～ ステップ15

トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ15に該当
github.com
ステップ15に該当
github.com
該当ステップなし
github.com

今回作成するコンパイラ

関数の定義に対応する(引数なしの関数の定義に対応したコンパイラ、最大引数6つの関数定義に対応したコンパイラ、エラーメッセージ改良のためにノードが生成された時のトークン位置を参照できるようにしたコンパイラを作成する)

追加・修正されたコンパイラのソースコード(引数なしの関数の定義に対応したコンパイラを作成する)

main関数

https://github.com/rui314/chibicc/commit/004b0fd8d230352fda871fe5badd80ff92c4068c#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR10
https://github.com/rui314/chibicc/blob/004b0fd8d230352fda871fe5badd80ff92c4068c/main.c#L10

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

  // Tokenize and parse.
  user_input = argv[1];
  token = tokenize();
  Function *prog = program();

  // Assign offsets to local variables.
  for (Function *fn = prog; fn; fn = fn->next) {
    int offset = 0;
    for (Var *var = prog->locals; var; var = var->next) {
      offset += 8;
      var->offset = offset;
    }
    fn->stack_size = offset;
  }

  // Traverse the AST to emit assembly.
  codegen(prog);

  return 0;
}

コマンドライン引数の個数をチェックする(変更なし)

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

トークナイズを行う(変更なし)

  // Tokenize and parse.
  user_input = argv[1];
  token = tokenize();

パースを行う

  Function *prog = program();

戻り値の型をFunction構造体に変更します。

ローカル変数のアドレスとスタックを用意する

  // Assign offsets to local variables.
  for (Function *fn = prog; fn; fn = fn->next) {
    int offset = 0;
    for (Var *var = prog->locals; var; var = var->next) {
      offset += 8;
      var->offset = offset;
    }
    fn->stack_size = offset;
  }

全てのコードをなんらかの関数内に記述する形式にしているので、関数ごとにローカル変数のアドレスとスタックを用意するようにします。

アセンブリコードを生成する(変更なし)

 // Traverse the AST to emit assembly.
  codegen(prog);
  return 0;

expect_ident関数

https://github.com/rui314/chibicc/commit/004b0fd8d230352fda871fe5badd80ff92c4068c#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R71
https://github.com/rui314/chibicc/blob/004b0fd8d230352fda871fe5badd80ff92c4068c/tokenize.c#L71

// Ensure that the current token is TK_IDENT.
char *expect_ident() {
  if (token->kind != TK_IDENT)
    error_at(token->str, "expected an identifier");
  char *s = strndup(token->str, token->len);
  token = token->next;
  return s;
}

expect_ident関数は、現在着目しているトークンの種類が識別子である場合に、そのトークンの文字列を戻り値として取得し、トークン列を1つ読み進めます。

現在着目しているトークンの種類が識別子であることを確認する

  if (token->kind != TK_IDENT)
    error_at(token->str, "expected an identifier");

現在着目しているトークンの型がTK_IDENTではない場合(トークンの種類が識別子ではない場合)、NULLを戻り値として処理を終了します。

着目しているトークンを次のトークンに変更する

  char *s = strndup(token->str, token->len);
  token = token->next;
  return s;

着目しているトークンを次のトークンに変更します。
最後に、strdup関数を呼び出して取得した識別子名を戻り値としてリターンします。

Function構造体

https://github.com/rui314/chibicc/commit/004b0fd8d230352fda871fe5badd80ff92c4068c#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R106
https://github.com/rui314/chibicc/blob/004b0fd8d230352fda871fe5badd80ff92c4068c/chibicc.h#L106

typedef struct Function Function;
struct Function {
  Function *next;
  char *name;
  Node *node;
  Var *locals;
  int stack_size;
};

Program構造体をFunction構造体に変更し、全てのコードをなんらかの関数内に記述する形式にします。

program関数

https://github.com/rui314/chibicc/commit/004b0fd8d230352fda871fe5badd80ff92c4068c#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR63
https://github.com/rui314/chibicc/blob/004b0fd8d230352fda871fe5badd80ff92c4068c/parse.c#L63

Function *program() {
  Function head;
  head.next = NULL;
  Function *cur = &head;

  while (!at_eof()) {
    cur->next = function();
    cur = cur->next;
  }
  return head.next;
}

program関数は、Function構造体(関数定義に対応する抽象構文木を含む)の連結リストを作成します。

Function構造体からなる連結リストのヘッダーを作成する

  Function head;
  head.next = NULL;
  Function *cur = &head;

Fuction構造体headを定義し、これから作成する連結リスト(Function構造体からなる連結リスト)のヘッダーとします。
nextメンバの初期値はNULL、連結リストの終端をcurで表現します。

Function構造体からなる連結リストを作成する

  while (!at_eof()) {
    cur->next = function();
    cur = cur->next;
  }

at_eof()関数の戻り値がtrueになるまで→着目しているトークンがトークン列の終端を表すトークンになるまで、while文のループを継続します。
function関数を呼び出してを Function構造体生成し、 Function構造体のアドレスを戻り値として取得します。
戻り値として取得した Function構造体のアドレスを連結リストの終端要素のnextメンバに格納し、連結リストの終端要素を表すcurを更新します。

Function構造体をリターンする

  return head.next;

連結リストの先頭ノード(連結リストのヘッダーの次にあるノード)のアドレスを戻り値としてリターンします。

function関数

https://github.com/rui314/chibicc/commit/004b0fd8d230352fda871fe5badd80ff92c4068c#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR76
https://github.com/rui314/chibicc/blob/004b0fd8d230352fda871fe5badd80ff92c4068c/parse.c#L76

// function = ident "(" ")" "{" stmt* "}"
Function *function() {
  locals = NULL;

  char *name = expect_ident();
  expect("(");
  expect(")");
  expect("{");

  Node head;
  head.next = NULL;
  Node *cur = &head;

  while (!consume("}")) {
    cur->next = stmt();
    cur = cur->next;
  }

  Function *fn = calloc(1, sizeof( Function));
  fn->name = name;
  fn->node = head.next;
  fn->locals = locals;
  return fn;
}

function関数は、生成規則 function = ident "(" ")" "{" stmt* "}" に基づいて抽象構文木のノードを生成し、Function構造体(関数定義に対応する抽象構文木を含む)を生成します。

ident、"("、")"

  char *name = expect_ident();
  expect("(");
  expect(")");

最初のトークンは識別子(関数名)であることが期待されているので(全てのコードをなんらかの関数内に記述する形式にしているので)、expect_ident関数を呼び出して関数名を取得しトークン列を1つ読み進めます。
識別子(関数名)の次は ”(” と ”)” が続いていることが期待されているので(この時点では引数なしの関数定義にのみ対応しているので)、 expect("(")とexpect(")")を呼び出してトークン列を読み進めます。

"{"、stmtを0回以上、 "}"

  expect("{");

  Node head;
  head.next = NULL;
  Node *cur = &head;

  while (!consume("}")) {
    cur->next = stmt();
    cur = cur->next;
  }

関数の実装に対応する抽象構文木を生成していきます(1つの文に対して1つの抽象構文木を生成します)。

ブロックの最初のトークンは "{" であることが期待されているので、expect("{")を呼び出してトークン列を1つ読み進めます。

ノード構造体headを定義し、これから作成する連結リスト(ノード構造体からなる連結リスト)のヘッダーとします。
nextメンバの初期値はNULL、連結リストの終端をcurで表現します。

consume("}")の戻り値がtrueになるまで→着目しているトークンが”}”を表すトークンになるまで、while文のループを継続します。
stmt関数を呼び出して抽象構文木を生成し、生成された抽象構文木のルートノードのアドレスを戻り値として取得します。
戻り値として取得した抽象構文木のルートノードのアドレスを連結リストの終端要素のnextメンバに格納し、連結リストの終端要素を表すcurを更新します。

Function構造体を生成する

  Function *fn = calloc(1, sizeof( Function));
  fn->name = name;
  fn->node = head.next;
  fn->locals = locals;
  return fn;

calloc関数を呼び出してFunction構造体を生成し、関数名、実装に対応する抽象構文木の(ルートノードからなる)連結リスト、Var構造体の連結リストを記録します。

codegen関数

https://github.com/rui314/chibicc/commit/004b0fd8d230352fda871fe5badd80ff92c4068c#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR188
https://github.com/rui314/chibicc/blob/004b0fd8d230352fda871fe5badd80ff92c4068c/codegen.c#L188

void codegen(Function *prog) {
  printf(".intel_syntax noprefix\n");

  for (Function *fn = prog; fn; fn = fn->next) {
    printf(".global %s\n", fn->name);
    printf("%s:\n", fn->name);
    funcname = fn->name;

    // Prologue
    printf("  push rbp\n");
    printf("  mov rbp, rsp\n");
    printf("  sub rsp, %d\n", fn->stack_size);

    // Emit code
    for (Node *node = fn->node; node; node = node->next)
      gen(node);

    // Epilogue
    printf(".Lreturn.%s:\n", funcname);
    printf("  mov rsp, rbp\n");
    printf("  pop rbp\n");
    printf("  ret\n");
  }
}

部分的にアセンブリコードを生成する①

  printf(".intel_syntax noprefix\n");

部分的にアセンブリコードを生成する②

  for (Function *fn = prog; fn; fn = fn->next) {
    printf(".global %s\n", fn->name);
    printf("%s:\n", fn->name);
    funcname = fn->name;

.globalディレクティブと関数名のラベルを生成します。

部分的にアセンブリコードを生成する③

    // Prologue
    printf("  push rbp\n");
    printf("  mov rbp, rsp\n");
    printf("  sub rsp, %d\n", fn->stack_size);

関数のプロローグとなるアセンブリコードを生成します。

部分的にアセンブリコードを生成する④

    // Emit code
    for (Node *node = fn->node; node; node = node->next)
      gen(node);

関数の実装に対応するアセンブリコードを生成します。

部分的にアセンブリコードを生成する⑤

    // Epilogue
    printf(".Lreturn.%s:\n", funcname);
    printf("  mov rsp, rbp\n");
    printf("  pop rbp\n");
    printf("  ret\n");

関数のエピローグとなるアセンブリコードを生成します。

gen関数

https://github.com/rui314/chibicc/commit/004b0fd8d230352fda871fe5badd80ff92c4068c#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR139
https://github.com/rui314/chibicc/blob/004b0fd8d230352fda871fe5badd80ff92c4068c/codegen.c#L139

void gen(Node *node) {
  switch (node->kind) {
  case ND_NUM:
    printf("  push %d\n", node->val);
    return;
  case ND_EXPR_STMT:
    gen(node->lhs);
    printf("  add rsp, 8\n");
    return;
  case ND_VAR:
    gen_addr(node);
    load();
    return;
  case ND_ASSIGN:
    gen_addr(node->lhs);
    gen(node->rhs);
    store();
    return;
  case ND_IF: {
    int seq = labelseq++;
    if (node->els) {
      gen(node->cond);
      printf("  pop rax\n");
      printf("  cmp rax, 0\n");
      printf("  je  .Lelse%d\n", seq);
      gen(node->then);
      printf("  jmp .Lend%d\n", seq);
      printf(".Lelse%d:\n", seq);
      gen(node->els);
      printf(".Lend%d:\n", seq);
    } else {
      gen(node->cond);
      printf("  pop rax\n");
      printf("  cmp rax, 0\n");
      printf("  je  .Lend%d\n", seq);
      gen(node->then);
      printf(".Lend%d:\n", seq);
    }
    return;
  }
  case ND_WHILE: {
    int seq = labelseq++;
    printf(".Lbegin%d:\n", seq);
    gen(node->cond);
    printf("  pop rax\n");
    printf("  cmp rax, 0\n");
    printf("  je  .Lend%d\n", seq);
    gen(node->then);
    printf("  jmp .Lbegin%d\n", seq);
    printf(".Lend%d:\n", seq);
    return;
  }
  case ND_FOR: {
    int seq = labelseq++;
    if (node->init)
      gen(node->init);
    printf(".Lbegin%d:\n", seq);
    if (node->cond) {
      gen(node->cond);
      printf("  pop rax\n");
      printf("  cmp rax, 0\n");
      printf("  je  .Lend%d\n", seq);
    }
    gen(node->then);
    if (node->inc)
      gen(node->inc);
    printf("  jmp .Lbegin%d\n", seq);
    printf(".Lend%d:\n", seq);
    return;
  }
  case ND_BLOCK:
    for (Node *n = node->body; n; n = n->next)
      gen(n);
    return;
  case ND_FUNCALL: {
    int nargs = 0;
    for (Node *arg = node->args; arg; arg = arg->next) {
      gen(arg);
      nargs++;
    }

    for (int i = nargs - 1; i >= 0; i--)
      printf("  pop %s\n", argreg[i]);

    // We need to align RSP to a 16 byte boundary before
    // calling a function because it is an ABI requirement.
    // RAX is set to 0 for variadic function.
    int seq = labelseq++;
    printf("  mov rax, rsp\n");
    printf("  and rax, 15\n");
    printf("  jnz .Lcall%d\n", seq);
    printf("  mov rax, 0\n");
    printf("  call %s\n", node->funcname);
    printf("  jmp .Lend%d\n", seq);
    printf(".Lcall%d:\n", seq);
    printf("  sub rsp, 8\n");
    printf("  mov rax, 0\n");
    printf("  call %s\n", node->funcname);
    printf("  add rsp, 8\n");
    printf(".Lend%d:\n", seq);
    printf("  push rax\n");
    return;
  }
  case ND_RETURN:
    gen(node->lhs);
    printf("  pop rax\n");
    printf("  jmp .Lreturn.%s\n", funcname);
    return;
  }

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  case ND_EQ:
    printf("  cmp rax, rdi\n");
    printf("  sete al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_NE:
    printf("  cmp rax, rdi\n");
    printf("  setne al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LT:
    printf("  cmp rax, rdi\n");
    printf("  setl al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LE:
    printf("  cmp rax, rdi\n");
    printf("  setle al\n");
    printf("  movzb rax, al\n");
    break;
  }

  printf("  push rax\n");
}

二項演算以外を行うアセンブリコードを生成する

void gen(Node *node) {
  switch (node->kind) {
  case ND_NUM:
    printf("  push %d\n", node->val);
    return;
  case ND_EXPR_STMT:
    gen(node->lhs);
    printf("  add rsp, 8\n");
    return;
  case ND_VAR:
    gen_addr(node);
    load();
    return;
  case ND_ASSIGN:
    gen_addr(node->lhs);
    gen(node->rhs);
    store();
    return;
  case ND_IF: {
    int seq = labelseq++;
    if (node->els) {
      gen(node->cond);
      printf("  pop rax\n");
      printf("  cmp rax, 0\n");
      printf("  je  .Lelse%d\n", seq);
      gen(node->then);
      printf("  jmp .Lend%d\n", seq);
      printf(".Lelse%d:\n", seq);
      gen(node->els);
      printf(".Lend%d:\n", seq);
    } else {
      gen(node->cond);
      printf("  pop rax\n");
      printf("  cmp rax, 0\n");
      printf("  je  .Lend%d\n", seq);
      gen(node->then);
      printf(".Lend%d:\n", seq);
    }
    return;
  }
  case ND_WHILE: {
    int seq = labelseq++;
    printf(".Lbegin%d:\n", seq);
    gen(node->cond);
    printf("  pop rax\n");
    printf("  cmp rax, 0\n");
    printf("  je  .Lend%d\n", seq);
    gen(node->then);
    printf("  jmp .Lbegin%d\n", seq);
    printf(".Lend%d:\n", seq);
    return;
  }
  case ND_FOR: {
    int seq = labelseq++;
    if (node->init)
      gen(node->init);
    printf(".Lbegin%d:\n", seq);
    if (node->cond) {
      gen(node->cond);
      printf("  pop rax\n");
      printf("  cmp rax, 0\n");
      printf("  je  .Lend%d\n", seq);
    }
    gen(node->then);
    if (node->inc)
      gen(node->inc);
    printf("  jmp .Lbegin%d\n", seq);
    printf(".Lend%d:\n", seq);
    return;
  }
  case ND_BLOCK:
    for (Node *n = node->body; n; n = n->next)
      gen(n);
    return;
  case ND_FUNCALL: {
    int nargs = 0;
    for (Node *arg = node->args; arg; arg = arg->next) {
      gen(arg);
      nargs++;
    }

    for (int i = nargs - 1; i >= 0; i--)
      printf("  pop %s\n", argreg[i]);

    // We need to align RSP to a 16 byte boundary before
    // calling a function because it is an ABI requirement.
    // RAX is set to 0 for variadic function.
    int seq = labelseq++;
    printf("  mov rax, rsp\n");
    printf("  and rax, 15\n");
    printf("  jnz .Lcall%d\n", seq);
    printf("  mov rax, 0\n");
    printf("  call %s\n", node->funcname);
    printf("  jmp .Lend%d\n", seq);
    printf(".Lcall%d:\n", seq);
    printf("  sub rsp, 8\n");
    printf("  mov rax, 0\n");
    printf("  call %s\n", node->funcname);
    printf("  add rsp, 8\n");
    printf(".Lend%d:\n", seq);
    printf("  push rax\n");
    return;
  }
  case ND_RETURN:
    gen(node->lhs);
    printf("  pop rax\n");
    printf("  jmp .Lreturn.%s\n", funcname);
    return;
  }

ノードの型がND_RETURNの場合の処理を修正します。
全てのコードをなんらかの関数内に記述する形式にしているので、関数ごとにreturnを使用できるようにします。

二項演算の対象となる値を得るためのアセンブリコードを生成する(変更なし)

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

二項演算を行うアセンブリコードを生成する(変更なし)

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  case ND_EQ:
    printf("  cmp rax, rdi\n");
    printf("  sete al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_NE:
    printf("  cmp rax, rdi\n");
    printf("  setne al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LT:
    printf("  cmp rax, rdi\n");
    printf("  setl al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LE:
    printf("  cmp rax, rdi\n");
    printf("  setle al\n");
    printf("  movzb rax, al\n");
    break;
  }

  printf("  push rax\n");
}

追加・修正されたコンパイラのソースコード(最大引数6つの関数の定義に対応したコンパイラを作成する)

main関数

https://github.com/rui314/chibicc/commit/3973698139945efa05228416a133ec27fd296639#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR15
https://github.com/rui314/chibicc/blob/3973698139945efa05228416a133ec27fd296639/main.c#L15

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

  // Tokenize and parse.
  user_input = argv[1];
  token = tokenize();
  Function *prog = program();

  // Assign offsets to local variables.
  for (Function *fn = prog; fn; fn = fn->next) {
    int offset = 0;
    for (VarList *vl = fn->locals; vl; vl = vl->next) {
      offset += 8;
      vl->var->offset = offset;
    }
    fn->stack_size = offset;
  }

  // Traverse the AST to emit assembly.
  codegen(prog);

  return 0;
}

コマンドライン引数の個数をチェックする(変更なし)

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

トークナイズを行う(変更なし)

  // Tokenize and parse.
  user_input = argv[1];
  token = tokenize();

パースを行う(変更なし)

  Function *prog = program();

引数・ローカル変数のアドレスとスタックサイズを定める

  // Assign offsets to local variables.
  for (Function *fn = prog; fn; fn = fn->next) {
    int offset = 0;
    for (VarList *vl = fn->locals; vl; vl = vl->next) {
      offset += 8;
      vl->var->offset = offset;
    }
    fn->stack_size = offset;
  }

VarList構造体からVar構造体を取得するようにします。

アセンブリコードを生成する(変更なし)

  // Traverse the AST to emit assembly.
  codegen(prog);

  return 0;

Var構造体

https://github.com/rui314/chibicc/commit/3973698139945efa05228416a133ec27fd296639#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334L52
https://github.com/rui314/chibicc/blob/3973698139945efa05228416a133ec27fd296639/chibicc.h#L50

typedef struct Var Var;
struct Var {
  char *name; // Variable name
  int offset; // Offset from RBP
};

nextメンバを削除します。

VarList構造体

https://github.com/rui314/chibicc/commit/3973698139945efa05228416a133ec27fd296639#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R56
https://github.com/rui314/chibicc/blob/3973698139945efa05228416a133ec27fd296639/chibicc.h#L56

typedef struct VarList VarList;
struct VarList {
  VarList *next;
  Var *var;
};

関数の引数やローカル変数(どちらもVar構造体で表現される)を管理するためにVarList構造体を定義します。

locals変数

https://github.com/rui314/chibicc/commit/3973698139945efa05228416a133ec27fd296639#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR3
https://github.com/rui314/chibicc/blob/3973698139945efa05228416a133ec27fd296639/parse.c#L3

VarList *locals;

グローバル変数localsの型をVarList型に変更し、Valist構造体の連結リスト(引数とローカル変数を管理するリスト)の先頭要素を指定するようにします。

Function構造体

https://github.com/rui314/chibicc/commit/3973698139945efa05228416a133ec27fd296639#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R115
https://github.com/rui314/chibicc/blob/3973698139945efa05228416a133ec27fd296639/chibicc.h#L115

typedef struct Function Function;
struct Function {
  Function *next;
  char *name;
  VarList *params;

  Node *node;
  VarList *locals;
  int stack_size;
};

paramsメンバを追加します。

function関数

https://github.com/rui314/chibicc/commit/3973698139945efa05228416a133ec27fd296639#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR104
https://github.com/rui314/chibicc/blob/3973698139945efa05228416a133ec27fd296639/parse.c#L104

// function = ident "(" params? ")" "{" stmt* "}"
// params   = ident ("," ident)*
Function *function() {
  locals = NULL;

  Function *fn = calloc(1, sizeof(Function));
  fn->name = expect_ident();
  expect("(");
  fn->params = read_func_params();
  expect("{");

  Node head;
  head.next = NULL;
  Node *cur = &head;
  while (!consume("}")) {
    cur->next = stmt();
    cur = cur->next;
  }

  fn->node = head.next;
  fn->locals = locals;
  return fn;
}

Function構造体を生成する

  Function *fn = calloc(1, sizeof(Function));

calloc関数を呼び出してFunction構造体を生成します。

関数名、(、引数、)、をパースする

  fn->name = expect_ident();
  expect("(");
  fn->params = read_func_params();

最初のトークンは識別子(関数名)であることが期待されているので(全てのコードをなんらかの関数内に記述する形式にしているので)、expect_ident関数を呼び出して関数名を取得しトークン列を1つ読み進めます。
識別子(関数名)の次のトークンは ”(” であることが期待されているので、expect("(")を呼び出してトークン列を1つ読み進めます。
read_func_params関数を呼び出して、引数に対応するVar構造体を含んだVarList構造体の連結リストを作成し、その連結リストの先頭ｱﾄﾞﾚｽをparamsメンバにセットします(引数の次のトークンである ")" は、read_func_params関数内で読み取られます)。

関数の実装に対応する抽象構文木を生成する

  expect("{");

  Node head;
  head.next = NULL;
  Node *cur = &head;
  while (!consume("}")) {
    cur->next = stmt();
    cur = cur->next;
  }

関数の実装に対応する抽象構文木を生成していきます(1つの文に対して1つの抽象構文木を生成します)。。

ブロックの最初のトークンは "{" であることが期待されているので、expect("{")を呼び出してトークン列を1つ読み進めます。

ノード構造体headを定義し、これから作成する連結リスト(ノード構造体からなる連結リスト)のヘッダーとします。
nextメンバの初期値はNULL、連結リストの終端をcurで表現します。

consume("}")の戻り値がtrueになるまで→着目しているトークンが”}”を表すトークンになるまで、while文のループを継続します。
stmt関数を呼び出して抽象構文木を生成し、生成された抽象構文木のルートノードのアドレスを戻り値として取得します。
戻り値として取得した抽象構文木のルートノードのアドレスを連結リストの終端要素のnextメンバに格納し、連結リストの終端要素を表すcurを更新します。

Function構造体に値を設定する

  fn->node = head.next;
  fn->locals = locals;
  return fn;

関数の実装に対応する抽象構文木の(ルートノードからなる)連結リストの先頭アドレス、VarList構造体の連結リストの先頭アドレス(read_func_params関数内で生成されたVarList構造体・Var構造体も、この連結リストに追加されています)を記録します。

read_func_params関数

https://github.com/rui314/chibicc/commit/3973698139945efa05228416a133ec27fd296639#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR81
https://github.com/rui314/chibicc/blob/3973698139945efa05228416a133ec27fd296639/parse.c#L81

VarList *read_func_params() {
  if (consume(")"))
    return NULL;

  VarList *head = calloc(1, sizeof(VarList));
  head->var = push_var(expect_ident());
  VarList *cur = head;

  while (!consume(")")) {
    expect(",");
    cur->next = calloc(1, sizeof(VarList));
    cur->next->var = push_var(expect_ident());
    cur = cur->next;
  }

  return head;
}

read_func_params関数は、引数を管理するVarList構造体の連結リストを作成します。

引数の有無を確認する

  if (consume(")"))
    return NULL;

consume(")")の戻り値がtrueとなる場合 → "関数名("の次のトークンが”)”の場合は、引数なしの関数になるので、戻り値をNULLにしてリターンします。

VarList構造体からなる連結リストの先頭要素を生成する

  VarList *head = calloc(1, sizeof(VarList));
  head->var = push_var(expect_ident());
  VarList *cur = head;

calloc関数を呼び出して、VarList構造体へのポインタheadにメモリを割り当てます。
トークン列では次のトークンは引数名(識別子)であることが期待されているので、expect_ident関数を呼び出して引数名(識別子)を取得し、取得した引数名(識別子)を用いてpush_var関数を呼び出し、引数に対応するVar構造体を生成します。
また、連結リストの終端をcurで表現します。

VarList構造体からなる連結リストを作成する

  while (!consume(")")) {
    expect(",");
    cur->next = calloc(1, sizeof(VarList));
    cur->next->var = push_var(expect_ident());
    cur = cur->next;
  }

consume("}")の戻り値がtrueになるまで→着目しているトークンが”}”を表すトークンになるまで、while文のループを継続します。

トークン列では次のトークンは” , ”であることが期待されているので、expect(",")を呼びだしてトークン列を1つ読み進めます。

calloc関数を呼び出してVaList構造体を生成し、生成されたVaList構造体を連結リストの終端要素として追加します。

トークン列では次のトークンは引数名(識別子)であることが期待されているので、expect_ident関数を呼び出して引数名(識別子)を取得し、取得した引数名(識別子)を用いてpush_var関数を呼び出し、引数に対応するVar構造体を生成し、生成したVar構造体を連結リストの終端要素のnextメンバに格納します。

最後に連結リストの終端要素を表すcurを更新します。

VarList構造体をリターンする

  return head;

連結リストの先頭要素のアドレスを戻り値としてリターンします。

push_var関数

https://github.com/rui314/chibicc/commit/3973698139945efa05228416a133ec27fd296639#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR50
https://github.com/rui314/chibicc/blob/3973698139945efa05228416a133ec27fd296639/parse.c#L50

Var *push_var(char *name) {
  Var *var = calloc(1, sizeof(Var));
  var->name = name;

  VarList *vl = calloc(1, sizeof(VarList));
  vl->var = var;
  vl->next = locals;
  locals = vl;
  return var;
}

push_var関数は、変数を表現しているVar構造体、Var構想体を管理しているVarlist構造体、を生成し、生成したVarlist構造体を連結リストに追加します。

Var構造体を生成する

  Var *var = calloc(1, sizeof(Var));
  var->name = name;

calloc関数を呼び出して、Var構造体を生成します。
生成したVar構造体に変数名nameをセットします。

変数を管理しているValist構造体を生成する

  VarList *vl = calloc(1, sizeof(VarList));
  vl->var = var;
  vl->next = locals;
  locals = vl;

calloc関数を呼び出して、Varlist構造体を生成します。
生成したVarlist構造体にVar構造体をセットします。
生成したVarlist構造体を新しい先頭要素として、localsが指定する連結リストに追加します。

生成したVar構造体をリターンする

  return var;

find_var関数

https://github.com/rui314/chibicc/commit/3973698139945efa05228416a133ec27fd296639#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR7
https://github.com/rui314/chibicc/blob/3973698139945efa05228416a133ec27fd296639/parse.c#L7

// Find a local variable by name.
Var *find_var(Token *tok) {
  for (VarList *vl = locals; vl; vl = vl->next) {
    Var *var = vl->var;
    if (strlen(var->name) == tok->len && !memcmp(tok->str, var->name, tok->len))
      return var;
  }
  return NULL;
}

Varlist構造体の連結リストから、トークンの文字列と同じ名前を持つvar構造体を探索するようにします(今まで定義されたローカル変数からトークンの文字列と同じ名前を持つローカル変数を探索します)。

codegen関数

https://github.com/rui314/chibicc/commit/3973698139945efa05228416a133ec27fd296639#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR201
https://github.com/rui314/chibicc/blob/3973698139945efa05228416a133ec27fd296639/codegen.c#L201

void codegen(Function *prog) {
  printf(".intel_syntax noprefix\n");

  for (Function *fn = prog; fn; fn = fn->next) {
    printf(".global %s\n", fn->name);
    printf("%s:\n", fn->name);
    funcname = fn->name;

    // Prologue
    printf("  push rbp\n");
    printf("  mov rbp, rsp\n");
    printf("  sub rsp, %d\n", fn->stack_size);

    // Push arguments to the stack
    int i = 0;
    for (VarList *vl = fn->params; vl; vl = vl->next) {
      Var *var = vl->var;
      printf("  mov [rbp-%d], %s\n", var->offset, argreg[i++]);
    }

    // Emit code
    for (Node *node = fn->node; node; node = node->next)
      gen(node);

    // Epilogue
    printf(".Lreturn.%s:\n", funcname);
    printf("  mov rsp, rbp\n");
    printf("  pop rbp\n");
    printf("  ret\n");
  }
}

部分的にアセンブリコードを生成する①(変更なし)

  printf(".intel_syntax noprefix\n");

部分的にアセンブリコードを生成する②(変更なし)

  for (Function *fn = prog; fn; fn = fn->next) {
    printf(".global %s\n", fn->name);
    printf("%s:\n", fn->name);
    funcname = fn->name;

部分的にアセンブリコードを生成する③

    // Prologue
    printf("  push rbp\n");
    printf("  mov rbp, rsp\n");
    printf("  sub rsp, %d\n", fn->stack_size);

部分的にアセンブリコードを生成する④

    // Push arguments to the stack
    int i = 0;
    for (VarList *vl = fn->params; vl; vl = vl->next) {
      Var *var = vl->var;
      printf("  mov [rbp-%d], %s\n", var->offset, argreg[i++]);
    }

    // Emit code
    for (Node *node = fn->node; node; node = node->next)
      gen(node);

Function構造体ごとに(関数ごとに)用意されたVarList構造体へのポインタparamsから引数に対応するVar構造体を取り出し、引数の値(レジスタにセットされた値)をスタック領域のアドレス(RBPの値にvar->offsetを減算した値)に退避させるアセンブリコードを生成するようにします。

部分的にアセンブリコードを生成する⑤(変更なし)

    // Epilogue
    printf(".Lreturn.%s:\n", funcname);
    printf("  mov rsp, rbp\n");
    printf("  pop rbp\n");
    printf("  ret\n");

追加・修正されたコンパイラのソースコード！(エラーメッセージ改良のために、ノードが生成された時のトークン位置を参照できるようにしたコンパイラを作成する)

consume関数

Token *consume(char *op) {
  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    return NULL;
  Token *t = token;
  token = token->next;
  return t;
}

expect関数

void expect(char *op) {
  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    error_tok(token, "expected \"%s\"", op);
  token = token->next;
}

expect_number関数

int expect_number() {
  if (token->kind != TK_NUM)
    error_tok(token, "expected a number");
  int val = token->val;
  token = token->next;
  return val;
}

expect_ident関数

char *expect_ident() {
  if (token->kind != TK_IDENT)
    error_tok(token, "expected an identifier");
  char *s = strndup(token->str, token->len);
  token = token->next;
  return s;
}

error_tok関数

void error_tok(Token *tok, char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  if (tok)
    verror_at(tok->str, fmt, ap);

  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

error_at関数

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

verror_at関数

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

new_node関数

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

new_binary関数

Node *new_binary(NodeKind kind, Node *lhs, Node *rhs, Token *tok) {
  Node *node = new_node(kind, tok);
  node->lhs = lhs;
  node->rhs = rhs;
  return node;
}

new_unary関数

Node *new_unary(NodeKind kind, Node *expr, Token *tok) {
  Node *node = new_node(kind, tok);
  node->lhs = expr;
  return node;
}

new_num関数

Node *new_num(int val, Token *tok) {
  Node *node = new_node(ND_NUM, tok);
  node->val = val;
  return node;
}

new_var関数

Node *new_var(Var *var, Token *tok) {
  Node *node = new_node(ND_VAR, tok);
  node->var = var;
  return node;
}

stmt関数

Node *stmt() {
  Token *tok;
  if (tok = consume("return")) {
    Node *node = new_unary(ND_RETURN, expr(), tok);
    expect(";");
    return node;
  }

  if (tok = consume("if")) {
    Node *node = new_node(ND_IF, tok);
    expect("(");
    node->cond = expr();
    expect(")");
    node->then = stmt();
    if (consume("else"))
      node->els = stmt();
    return node;
  }

  if (tok = consume("while")) {
    Node *node = new_node(ND_WHILE, tok);
    expect("(");
    node->cond = expr();
    expect(")");
    node->then = stmt();
    return node;
  }

  if (tok = consume("for")) {
    Node *node = new_node(ND_FOR, tok);
    expect("(");
    if (!consume(";")) {
      node->init = read_expr_stmt();
      expect(";");
    }
    if (!consume(";")) {
      node->cond = expr();
      expect(";");
    }
    if (!consume(")")) {
      node->inc = read_expr_stmt();
      expect(")");
    }
    node->then = stmt();
    return node;
  }

  if (tok = consume("{")) {
    Node head;
    head.next = NULL;
    Node *cur = &head;

    while (!consume("}")) {
      cur->next = stmt();
      cur = cur->next;
    }

    Node *node = new_node(ND_BLOCK, tok);
    node->body = head.next;
    return node;
  }

  Node *node = read_expr_stmt();
  expect(";");
  return node;
}

read_expr_stmt関数

Node *read_expr_stmt() {
  Token *tok = token;
  return new_unary(ND_EXPR_STMT, expr(), tok);
}

assign関数

Node *assign() {
  Node *node = equality();
  Token *tok;
  if (tok = consume("="))
    node = new_binary(ND_ASSIGN, node, assign(), tok);
  return node;
}

equality関数

Node *equality() {
  Node *node = relational();
  Token *tok;

  for (;;) {
    if (tok = consume("=="))
      node = new_binary(ND_EQ, node, relational(), tok);
    else if (tok = consume("!="))
      node = new_binary(ND_NE, node, relational(), tok);
    else
      return node;
  }
}

relational関数

Node *relational() {
  Node *node = add();
  Token *tok;

  for (;;) {
    if (tok = consume("<"))
      node = new_binary(ND_LT, node, add(), tok);
    else if (tok = consume("<="))
      node = new_binary(ND_LE, node, add(), tok);
    else if (tok = consume(">"))
      node = new_binary(ND_LT, add(), node, tok);
    else if (tok = consume(">="))
      node = new_binary(ND_LE, add(), node, tok);
    else
      return node;
  }
}

add関数

Node *add() {
  Node *node = mul();
  Token *tok;

  for (;;) {
    if (tok = consume("+"))
      node = new_binary(ND_ADD, node, mul(), tok);
    else if (tok = consume("-"))
      node = new_binary(ND_SUB, node, mul(), tok);
    else
      return node;
  }
}

mul関数

Node *mul() {
  Node *node = unary();
  Token *tok;

  for (;;) {
    if (tok = consume("*"))
      node = new_binary(ND_MUL, node, unary(), tok);
    else if (tok = consume("/"))
      node = new_binary(ND_DIV, node, unary(), tok);
    else
      return node;
  }
}

unary関数

Node *unary() {
  Token *tok;
  if (consume("+"))
    return unary();
  if (tok = consume("-"))
    return new_binary(ND_SUB, new_num(0, tok), unary(), tok);
  return primary();
}

primary関数

Node *primary() {
  if (consume("(")) {
    Node *node = expr();
    expect(")");
    return node;
  }

  Token *tok;
  if (tok = consume_ident()) {
    if (consume("(")) {
      Node *node = new_node(ND_FUNCALL, tok);
      node->funcname = strndup(tok->str, tok->len);
      node->args = func_args();
      return node;
    }

    Var *var = find_var(tok);
    if (!var)
      var = push_var(strndup(tok->str, tok->len));
    return new_var(var, tok);
  }

  tok = token;
  if (tok->kind != TK_NUM)
    error_tok(tok, "expected expression");
  return new_num(expect_number(), tok);
}

gen_addr関数

void gen_addr(Node *node) {
  if (node->kind == ND_VAR) {
    printf("  lea rax, [rbp-%d]\n", node->var->offset);
    printf("  push rax\n");
    return;
  }

  error_tok(node->tok, "not an lvalue");
}

テストコード

Makefile