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

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

今回作成するコンパイラ

文字型を実装する(文字型を扱えるコンパイラを作成する)

追加・修正されたコンパイラのソースコード

main関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR25
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/main.c#L25

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();
  Program *prog = program();
  add_type(prog);

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

  // 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();

パースを行う

  Program *prog = program();

型付けを行う(変更なし)

  add_type(prog);

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

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

align_to(offset, 8)を呼び出して、スタックサイズoffsetを8バイト境界に切り上げた値をFuntion構造体に記録します。

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

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

align_to関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR3
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/main.c#L3

int align_to(int n, int align) {
  return (n + align - 1) & ~(align - 1);
}

align_to関数は、引数nの値 を 引数align(2の冪乗)バイト境界の値 へ切り上げます。
2進数n に align-1 を足すことで、2進数nの下位\log_2align桁がどのような値であっても、(\log_2_align)+1 桁目が必ず繰り上がるようにします。
繰り上げた値n+align-1 を ~(align-1) でマスク処理することにより、下位\log_2_align桁が全て0となり切り上げが完了します。

starts_with_reserved関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R131
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/tokenize.c#L131

char *starts_with_reserved(char *p) {
  // Keyword
  static char *kw[] = {"return", "if", "else", "while", "for", "int",
                       "char", "sizeof"};

  for (int i = 0; i < sizeof(kw) / sizeof(*kw); i++) {
    int len = strlen(kw[i]);
    if (startswith(p, kw[i]) && !is_alnum(p[len]))
      return kw[i];
  }

  // Multi-letter punctuator
  static char *ops[] = {"==", "!=", "<=", ">="};

  for (int i = 0; i < sizeof(ops) / sizeof(*ops); i++)
    if (startswith(p, ops[i]))
      return ops[i];

  return NULL;
}

キーワードを取得する

  // Keyword
  static char *kw[] = {"return", "if", "else", "while", "for", "int",
                       "char", "sizeof"};

  for (int i = 0; i < sizeof(kw) / sizeof(*kw); i++) {
    int len = strlen(kw[i]);
    if (startswith(p, kw[i]) && !is_alnum(p[len]))
      return kw[i];
  }

配列kwに"char"を追加し、"char"をキーワードとして扱えるようにします。

複数文字の記号を取得する(変更なし)

  // Multi-letter punctuator
  static char *ops[] = {"==", "!=", "<=", ">="};

  for (int i = 0; i < sizeof(ops) / sizeof(*ops); i++)
    if (startswith(p, ops[i]))
      return ops[i];

  return NULL;

TypeKind

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R148
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/chibicc.h#L148

typedef enum {
  TY_CHAR,
  TY_INT,
  TY_PTR,
  TY_ARRAY,
} TypeKind;

char型を表現する定数TY_CHARを追加します。

stmt関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR301
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/parse.c#L301

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

  if (is_typename())
    return declaration();

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

"return"、expr、";"(変更なし)

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


}

"if"、"("、expr、")"、stmt 、「"else" と stmt」を0回か1回(変更なし)

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

"while"、"("、expr、")"、stmt(変更なし)

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

"for"、"("、exprを0回か1回、 ";"、exprを0回か1回、";"、exprを0回か1回、")"、stmt(変更なし)

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

"{"、stmtを0回以上、"}"(変更なし)

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

declaration

  if (is_typename())
    return declaration();

tok = peek("int") を is_typename() に置き換え、現在着目しているトークンが型を表すキーワード(char、または、int)であるかを判定するようにします。

expr、";"(変更なし)

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

is_typename関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR228
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/parse.c#L228

bool is_typename() {
  return peek("char") || peek("int");
}

is_typename関数は、現在着目しているトークンが、型を表すキーワード(char、または、int)であるかを判定します。

basetype関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR119
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/parse.c#L119

// basetype = ("char" | "int") "*"*
Type *basetype() {
  Type *ty;
  if (consume("char")) {
    ty = char_type();
  } else {
    expect("int");
    ty = int_type();
  }

  while (consume("*"))
    ty = pointer_to(ty);
  return ty;
}

char型、または、int型のキーワードを表現したType構造体を生成する

  Type *ty;
  if (consume("char")) {
    ty = char_type();
  } else {
    expect("int");
    ty = int_type();
  }

consume("char")がトークンを取得できた場合 → 現在着目しているトークンが"char"の場合は、char_type関数を呼び出しchar型を表現したType構造体を生成します。
consume("char")がトークンを取得できなかった場合 → 現在着目しているトークンが"char"ではない場合は、expect関数を呼び出して、現在着目しているトークンがintであることを確認します。その後、int_type関数を呼び出しint型を表現したType構造体を生成します。

ポインタを表現したType構造体を生成する(変更なし)

  while (consume("*"))
    ty = pointer_to(ty);
  return ty;

new_type関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R3
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/type.c#L3

Type *new_type(TypeKind kind) {
  Type *ty = calloc(1, sizeof(Type));
  ty->kind = kind;
  return ty;
}

new_type関数は、引数kindが指定する型の種類を表現したType構造体を生成します。

char_type関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R9
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/type.c#L9

Type *char_type() {
  return new_type(TY_CHAR);
}

char_type関数は、char型を表現したType構造体を生成します。

int_type関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R13
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/type.c#L13

Type *int_type() {
  return new_type(TY_INT);
}

int_type関数は、int型を表現したType構造体を生成します。

pointer_to関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R18
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/type.c#L18

Type *pointer_to(Type *base) {
  Type *ty = new_type(TY_PTR);
  ty->base = base;
  return ty;
}

new_type関数を用いて、「~へのポインタ」型を表現するType構造体を生成するようにします。

array_of関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R24
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/type.c#L24

Type *array_of(Type *base, int size) {
  Type *ty = new_type(TY_ARRAY);
  ty->base = base;
  ty->array_size = size;
  return ty;
}

new_type関数を用いて、~型の配列を表現するType構造体を生成するようにします。

size_of関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R31
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/type.c#L31

int size_of(Type *ty) {
  switch (ty->kind) {
  case TY_CHAR:
    return 1;
  case TY_INT:
  case TY_PTR:
    return 8;
  default:
    assert(ty->kind == TY_ARRAY);
    return size_of(ty->base) * ty->array_size;
  }
}

Type構造体の種類がTY_CHARの場合は、1が戻り値になるようにします(char型のサイズは1バイトサイズにします)。
Type構造体の種類がTY_INTやTY_PTRの場合は、8が戻り値になるようにします(int型や「~へのポインタ」型のサイズは8バイトサイズにします)。
Type構造体の種類が上記以外の場合は、配列全体のサイズが戻り値になるようにします。

emit_text関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR265
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/codegen.c#L265

void emit_text(Program *prog) {
  printf(".text\n");

  for (Function *fn = prog->fns; 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)
      load_arg(vl->var, 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(".text\n");

関数名のラベルを生成する(変更なし)

  for (Function *fn = prog->fns; 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)
      load_arg(vl->var, i++);

引数の値(レジスタにセットされた値)をスタック領域のアドレスに退避させるアセンブリコードを生成する処理をload_arg関数で置き換えます。

関数の実装に対応するアセンブリコードを生成する(変更なし)

    // 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");
  }

argreg8配列

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR4
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/codegen.c#L4

char *argreg8[] = {"rdi", "rsi", "rdx", "rcx", "r8", "r9"};

既存のargreg配列をargreg8配列として定義します。

argreg1配列

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR3
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/codegen.c#L3

char *argreg1[] = {"dil", "sil", "dl", "cl", "r8b", "r9b"};

dilレジスタ(RDIレジスタの下位1バイト)、silレジスタ(RSIレジスタの下位1バイト)、dlレジスタ(RDXレジスタの下位1バイト)、clレジスタ(RCXレジスタの下位1バイト), r8bレジスタ(r8レジスタの下位1バイト), r9bレジスタ(r9レジスタの下位1バイト)、の1バイトの値を扱うためのレジスタ名を用意します。

load_arg関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR240
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/codegen.c#L240

void load_arg(Var *var, int idx) {
  int sz = size_of(var->ty);
  if (sz == 1) {
    printf("  mov [rbp-%d], %s\n", var->offset, argreg1[idx]);
  } else {
    assert(sz == 8);
    printf("  mov [rbp-%d], %s\n", var->offset, argreg8[idx]);
  }
}

load_arg関数は、変数が持つ型のサイズに応じて(Var構造体が持つType構造体の種類に応じて)、引数の値(レジスタにセットされた値)をスタック領域のアドレス(RBPの値にvar->offsetを減算した値)に退避させるアセンブリコードを生成します。

gen関数

void gen(Node *node) {
  switch (node->kind) {
  case ND_NULL:
    return;
  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);
    if (node->ty->kind != TY_ARRAY)
      load(node->ty);
    return;
  case ND_ASSIGN:
    gen_lval(node->lhs);
    gen(node->rhs);
    store(node->ty);
    return;
  case ND_ADDR:
    gen_addr(node->lhs);
    return;
  case ND_DEREF:
    gen(node->lhs);
    if (node->ty->kind != TY_ARRAY)
      load(node->ty);
    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", argreg8[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:
    if (node->ty->base)
      printf("  imul rdi, %d\n", size_of(node->ty->base));
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    if (node->ty->base)
      printf("  imul rdi, %d\n", size_of(node->ty->base));
    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");
}

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

  switch (node->kind) {
  case ND_NULL:
    return;
  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);
    if (node->ty->kind != TY_ARRAY)
      load(node->ty);
    return;
  case ND_ASSIGN:
    gen_lval(node->lhs);
    gen(node->rhs);
    store(node->ty);
    return;
  case ND_ADDR:
    gen_addr(node->lhs);
    return;
  case ND_DEREF:
    gen(node->lhs);
    if (node->ty->kind != TY_ARRAY)
      load(node->ty);
    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", argreg8[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_VARの場合の処理において、load()からload(node->ty)へ変更します。
https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR74
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/codegen.c#L74

  case ND_VAR:
    gen_addr(node);
    if (node->ty->kind != TY_ARRAY)
      load(node->ty);
    return;

ノード型がND_ASSIGNの場合の処理において、store()からstore(node->ty)へ変更します。
https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR79
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/codegen.c#L79

  case ND_ASSIGN:
    gen_lval(node->lhs);
    gen(node->rhs);
    store(node->ty);
    return;

ノード型がND_DEREFの場合の処理において、load()からload(node->ty)へ変更します。
https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR87
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/codegen.c#L87

  case ND_DEREF:
    gen(node->lhs);
    if (node->ty->kind != TY_ARRAY)
      load(node->ty);
    return;

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

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

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

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

  switch (node->kind) {
  case ND_ADD:
    if (node->ty->base)
      printf("  imul rdi, %d\n", size_of(node->ty->base));
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    if (node->ty->base)
      printf("  imul rdi, %d\n", size_of(node->ty->base));
    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");

ノード型がND_FUNCALLの場合の処理において、argregからargreg8へ変更します。
https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR153
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/codegen.c#L153

  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", argreg8[i]);

load関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR38
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/codegen.c#L38

void load(Type *ty) {
  printf("  pop rax\n");
  if (size_of(ty) == 1)
    printf("  movsx rax, byte ptr [rax]\n");
  else
    printf("  mov rax, [rax]\n");
  printf("  push rax\n");
}

型のサイズに応じて(Type構造体が表現している型の種類に応じて)、左辺値が指定するメモリ領域から右辺値を取得するアセンブリコードを生成するようにします。

store関数

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR47
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/codegen.c#L47

void store(Type *ty) {
  printf("  pop rdi\n");
  printf("  pop rax\n");

  if (size_of(ty) == 1)
    printf("  mov [rax], dil\n");
  else
    printf("  mov [rax], rdi\n");

  printf("  push rdi\n");
}

型のサイズに応じて(Type構造体が表現している型の種類に応じて)、左辺値が指定するメモリ領域に右辺値を保存するアセンブリコードを生成します。

テストコード

https://github.com/rui314/chibicc/commit/87a9d298e164d2ec5c3346b940e7d589aeb17ea2#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R157
https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/test.sh#L157

#!/bin/bash
cat <<EOF | gcc -xc -c -o tmp2.o -
int ret3() { return 3; }
int ret5() { return 5; }
int add(int x, int y) { return x+y; }
int sub(int x, int y) { return x-y; }
int add6(int a, int b, int c, int d, int e, int f) {
  return a+b+c+d+e+f;
}
EOF

assert() {
  expected="$1"
  input="$2"

  ./chibicc "$input" > tmp.s
  gcc -static -o tmp tmp.s tmp2.o
  ./tmp
  actual="$?"

  if [ "$actual" = "$expected" ]; then
    echo "$input => $actual"
  else
    echo "$input => $expected expected, but got $actual"
    exit 1
  fi
}

assert 0 'int main() { return 0; }'
assert 42 'int main() { return 42; }'
assert 21 'int main() { return 5+20-4; }'
assert 41 'int main() { return  12 + 34 - 5 ; }'
assert 47 'int main() { return 5+6*7; }'
assert 15 'int main() { return 5*(9-6); }'
assert 4 'int main() { return (3+5)/2; }'
assert 10 'int main() { return -10+20; }'
assert 10 'int main() { return - -10; }'
assert 10 'int main() { return - - +10; }'

assert 0 'int main() { return 0==1; }'
assert 1 'int main() { return 42==42; }'
assert 1 'int main() { return 0!=1; }'
assert 0 'int main() { return 42!=42; }'

assert 1 'int main() { return 0<1; }'
assert 0 'int main() { return 1<1; }'
assert 0 'int main() { return 2<1; }'
assert 1 'int main() { return 0<=1; }'
assert 1 'int main() { return 1<=1; }'
assert 0 'int main() { return 2<=1; }'

assert 1 'int main() { return 1>0; }'
assert 0 'int main() { return 1>1; }'
assert 0 'int main() { return 1>2; }'
assert 1 'int main() { return 1>=0; }'
assert 1 'int main() { return 1>=1; }'
assert 0 'int main() { return 1>=2; }'

assert 3 'int main() { int a; a=3; return a; }'
assert 8 'int main() { int a; int z; a=3; z=5; return a+z; }'
assert 3 'int main() { int a=3; return a; }'
assert 8 'int main() { int a=3; int z=5; return a+z; }'

assert 1 'int main() { return 1; 2; 3; }'
assert 2 'int main() { 1; return 2; 3; }'
assert 3 'int main() { 1; 2; return 3; }'

assert 3 'int main() { int foo=3; return foo; }'
assert 8 'int main() { int foo123=3; int bar=5; return foo123+bar; }'

assert 3 'int main() { if (0) return 2; return 3; }'
assert 3 'int main() { if (1-1) return 2; return 3; }'
assert 2 'int main() { if (1) return 2; return 3; }'
assert 2 'int main() { if (2-1) return 2; return 3; }'

assert 3 'int main() { {1; {2;} return 3;} }'

assert 10 'int main() { int i=0; i=0; while(i<10) i=i+1; return i; }'
assert 55 'int main() { int i=0; int j=0; while(i<=10) {j=i+j; i=i+1;} return j; }'

assert 55 'int main() { int i=0; int j=0; for (i=0; i<=10; i=i+1) j=i+j; return j; }'
assert 3 'int main() { for (;;) return 3; return 5; }'

assert 3 'int main() { return ret3(); }'
assert 5 'int main() { return ret5(); }'
assert 8 'int main() { return add(3, 5); }'
assert 2 'int main() { return sub(5, 3); }'
assert 21 'int main() { return add6(1,2,3,4,5,6); }'

assert 32 'int main() { return ret32(); } int ret32() { return 32; }'
assert 7 'int main() { return add2(3,4); } int add2(int x, int y) { return x+y; }'
assert 1 'int main() { return sub2(4,3); } int sub2(int x, int y) { return x-y; }'
assert 55 'int main() { return fib(9); } int fib(int x) { if (x<=1) return 1; return fib(x-1) + fib(x-2); }'

assert 3 'int main() { int x=3; return *&x; }'
assert 3 'int main() { int x=3; int *y=&x; int **z=&y; return **z; }'
assert 5 'int main() { int x=3; int y=5; return *(&x+1); }'
assert 5 'int main() { int x=3; int y=5; return *(1+&x); }'
assert 3 'int main() { int x=3; int y=5; return *(&y-1); }'
assert 5 'int main() { int x=3; int y=5; int *z=&x; return *(z+1); }'
assert 3 'int main() { int x=3; int y=5; int *z=&y; return *(z-1); }'
assert 5 'int main() { int x=3; int *y=&x; *y=5; return x; }'
assert 7 'int main() { int x=3; int y=5; *(&x+1)=7; return y; }'
assert 7 'int main() { int x=3; int y=5; *(&y-1)=7; return x; }'
assert 8 'int main() { int x=3; int y=5; return foo(&x, y); } int foo(int *x, int y) { return *x + y; }'

assert 3 'int main() { int x[2]; int *y=&x; *y=3; return *x; }'

assert 3 'int main() { int x[3]; *x=3; *(x+1)=4; *(x+2)=5; return *x; }'
assert 4 'int main() { int x[3]; *x=3; *(x+1)=4; *(x+2)=5; return *(x+1); }'
assert 5 'int main() { int x[3]; *x=3; *(x+1)=4; *(x+2)=5; return *(x+2); }'

assert 0 'int main() { int x[2][3]; int *y=x; *y=0; return **x; }'
assert 1 'int main() { int x[2][3]; int *y=x; *(y+1)=1; return *(*x+1); }'
assert 2 'int main() { int x[2][3]; int *y=x; *(y+2)=2; return *(*x+2); }'
assert 3 'int main() { int x[2][3]; int *y=x; *(y+3)=3; return **(x+1); }'
assert 4 'int main() { int x[2][3]; int *y=x; *(y+4)=4; return *(*(x+1)+1); }'
assert 5 'int main() { int x[2][3]; int *y=x; *(y+5)=5; return *(*(x+1)+2); }'
assert 6 'int main() { int x[2][3]; int *y=x; *(y+6)=6; return **(x+2); }'

assert 3 'int main() { int x[3]; *x=3; x[1]=4; x[2]=5; return *x; }'
assert 4 'int main() { int x[3]; *x=3; x[1]=4; x[2]=5; return *(x+1); }'
assert 5 'int main() { int x[3]; *x=3; x[1]=4; x[2]=5; return *(x+2); }'
assert 5 'int main() { int x[3]; *x=3; x[1]=4; x[2]=5; return *(x+2); }'
assert 5 'int main() { int x[3]; *x=3; x[1]=4; 2[x]=5; return *(x+2); }'

assert 0 'int main() { int x[2][3]; int *y=x; y[0]=0; return x[0][0]; }'
assert 1 'int main() { int x[2][3]; int *y=x; y[1]=1; return x[0][1]; }'
assert 2 'int main() { int x[2][3]; int *y=x; y[2]=2; return x[0][2]; }'
assert 3 'int main() { int x[2][3]; int *y=x; y[3]=3; return x[1][0]; }'
assert 4 'int main() { int x[2][3]; int *y=x; y[4]=4; return x[1][1]; }'
assert 5 'int main() { int x[2][3]; int *y=x; y[5]=5; return x[1][2]; }'
assert 6 'int main() { int x[2][3]; int *y=x; y[6]=6; return x[2][0]; }'

assert 8 'int main() { int x; return sizeof(x); }'
assert 8 'int main() { int x; return sizeof x; }'
assert 8 'int main() { int *x; return sizeof(x); }'
assert 32 'int main() { int x[4]; return sizeof(x); }'
assert 96 'int main() { int x[3][4]; return sizeof(x); }'
assert 32 'int main() { int x[3][4]; return sizeof(*x); }'
assert 8 'int main() { int x[3][4]; return sizeof(**x); }'
assert 9 'int main() { int x[3][4]; return sizeof(**x) + 1; }'
assert 9 'int main() { int x[3][4]; return sizeof **x + 1; }'
assert 8 'int main() { int x[3][4]; return sizeof(**x + 1); }'

assert 0 'int x; int main() { return x; }'
assert 3 'int x; int main() { x=3; return x; }'
assert 0 'int x[4]; int main() { x[0]=0; x[1]=1; x[2]=2; x[3]=3; return x[0]; }'
assert 1 'int x[4]; int main() { x[0]=0; x[1]=1; x[2]=2; x[3]=3; return x[1]; }'
assert 2 'int x[4]; int main() { x[0]=0; x[1]=1; x[2]=2; x[3]=3; return x[2]; }'
assert 3 'int x[4]; int main() { x[0]=0; x[1]=1; x[2]=2; x[3]=3; return x[3]; }'

assert 8 'int x; int main() { return sizeof(x); }'
assert 32 'int x[4]; int main() { return sizeof(x); }'

assert 1 'int main() { char x=1; return x; }'
assert 1 'int main() { char x=1; char y=2; return x; }'
assert 2 'int main() { char x=1; char y=2; return y; }'

assert 1 'int main() { char x; return sizeof(x); }'
assert 10 'int main() { char x[10]; return sizeof(x); }'
assert 1 'int main() { return sub_char(7, 3, 3); } int sub_char(char a, char b, char c) { return a-b-c; }'

echo OK

Makefile

https://github.com/rui314/chibicc/blob/87a9d298e164d2ec5c3346b940e7d589aeb17ea2/Makefile

CFLAGS=-std=c11 -g -static
SRCS=$(wildcard *.c)
OBJS=$(SRCS:.c=.o)

chibicc: $(OBJS)
	$(CC) -o $@ $(OBJS) $(LDFLAGS)

$(OBJS): chibicc.h

test: chibicc
	./test.sh

clean:
	rm -f chibicc *.o *~ tmp*

.PHONY: test clean