chibiccを読む～Cコンパイラコードリーディング～ ステップ17, 18, 19
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ18, 19に該当
github.com
ステップ17に該当
github.com
- 今回作成するコンパイラ
- 追加・修正されたコンパイラのソースコード(ステップ18・19、ポインタを扱えるコンパイラを作成する)
- 追加・修正されたコンパイラのソースコード(ステップ17、int型を扱えるコンパイラを作成する)
- テストコード
- Makefile
今回作成するコンパイラ
ポインタ型を導入する・ポインタの加算と減算を実装する(ステップ18・19、ポインタを扱えるコンパイラを作成する)
↓
暗黙の変数定義を廃止して、intというキーワードを導入する(ステップ17、int型を扱えるコンパイラを作成する)
追加・修正されたコンパイラのソースコード(ステップ18・19、ポインタを扱えるコンパイラを作成する)
main関数
https://github.com/rui314/chibicc/commit/1813fe470e4774c8d52b867649545d93f677323c#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR11
https://github.com/rui314/chibicc/blob/1813fe470e4774c8d52b867649545d93f677323c/main.c#L11
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();
add_type(prog);
// 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]);
トークナイズを行う(変更なし)
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;
TypeKind
https://github.com/rui314/chibicc/commit/1813fe470e4774c8d52b867649545d93f677323c#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R135
https://github.com/rui314/chibicc/blob/1813fe470e4774c8d52b867649545d93f677323c/chibicc.h#L135
typedef enum { TY_INT, TY_PTR } TypeKind;型の種類を表現する名前付き整数定数を定め、TypeKind型を定義します。
TY_INTは int型 を、TY_PTRは ～へのポインタ型 を表現しています。
Type構造体
https://github.com/rui314/chibicc/commit/1813fe470e4774c8d52b867649545d93f677323c#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R137
https://github.com/rui314/chibicc/blob/1813fe470e4774c8d52b867649545d93f677323c/chibicc.h#L137
https://github.com/rui314/chibicc/commit/1813fe470e4774c8d52b867649545d93f677323c#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R8
https://github.com/rui314/chibicc/blob/1813fe470e4774c8d52b867649545d93f677323c/chibicc.h#L8
struct Type {
TypeKind kind;
Type *base;
};
typedef struct Type Type;型を表現するデータ構造であるType構造体を定義し、さらに、Type型として定義します。
Node構造体
https://github.com/rui314/chibicc/commit/1813fe470e4774c8d52b867649545d93f677323c#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R94
https://github.com/rui314/chibicc/blob/1813fe470e4774c8d52b867649545d93f677323c/chibicc.h#L94
// AST node type
typedef struct Node Node;
struct Node {
NodeKind kind; // Node kind
Node *next; // Next node
Type *ty; // Type, e.g. int or pointer to int型付けを行うために、Node構造体にtyメンバを追加します。
add_type関数
https://github.com/rui314/chibicc/commit/1813fe470e4774c8d52b867649545d93f677323c#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R75
https://github.com/rui314/chibicc/blob/1813fe470e4774c8d52b867649545d93f677323c/type.c#L75
void add_type(Function *prog) {
for (Function *fn = prog; fn; fn = fn->next)
for (Node *node = fn->node; node; node = node->next)
visit(node);
}add_type関数は、プログラム内にある全ての抽象構文木に対して型付け処理を行います。
visit関数
https://github.com/rui314/chibicc/commit/1813fe470e4774c8d52b867649545d93f677323c#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R16
https://github.com/rui314/chibicc/blob/1813fe470e4774c8d52b867649545d93f677323c/type.c#L16
void visit(Node *node) {
if (!node)
return;
visit(node->lhs);
visit(node->rhs);
visit(node->cond);
visit(node->then);
visit(node->els);
visit(node->init);
visit(node->inc);
for (Node *n = node->body; n; n = n->next)
visit(n);
for (Node *n = node->args; n; n = n->next)
visit(n);
switch (node->kind) {
case ND_MUL:
case ND_DIV:
case ND_EQ:
case ND_NE:
case ND_LT:
case ND_LE:
case ND_VAR:
case ND_FUNCALL:
case ND_NUM:
node->ty = int_type();
return;
case ND_ADD:
if (node->rhs->ty->kind == TY_PTR) {
Node *tmp = node->lhs;
node->lhs = node->rhs;
node->rhs = tmp;
}
if (node->rhs->ty->kind == TY_PTR)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;
case ND_SUB:
if (node->rhs->ty->kind == TY_PTR)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;
case ND_ASSIGN:
node->ty = node->lhs->ty;
return;
case ND_ADDR:
node->ty = pointer_to(node->lhs->ty);
return;
case ND_DEREF:
if (node->lhs->ty->kind == TY_PTR)
node->ty = node->lhs->ty->base;
else
node->ty = int_type();
return;
}
}visit関数は、抽象構文木が持つ全てのノードに対して型付け処理を行います。
ノードがセットされていない場合
if (!node)
return;引数nodeにアドレスがセットされていない場合は、何もせずリターンします。
全ての子のノードに対してvisit関数を再帰的に呼び出す
visit(node->lhs);
visit(node->rhs);
visit(node->cond);
visit(node->then);
visit(node->els);
visit(node->init);
visit(node->inc);
for (Node *n = node->body; n; n = n->next)
visit(n);
for (Node *n = node->args; n; n = n->next)
visit(n);全ての子ノードに対してvisit関数を再帰的に呼び出します。
子ノードnode->bodyと子ノードnode->argsは抽象構文木のルートノードからなる連結リストなので、連結リストの全ての要素に対してもvisit関数を呼び出します。
ノード型に応じて型付け処理を行う(int型を付ける)
switch (node->kind) {
case ND_MUL:
case ND_DIV:
case ND_EQ:
case ND_NE:
case ND_LT:
case ND_LE:
case ND_VAR:
case ND_FUNCALL:
case ND_NUM:
node->ty = int_type();
return;ノードの型が、ND_MUL( * )、ND_DIV( / )、ND_EQ(=)、ND_NE(!=)、ND_LT(<)、ND_LE(<=)、ND_VAR(ローカル変数)、ND_FUNCALL(関数呼び出し)、ND_NUM(数値)の場合は、int_type関数を呼び出してint型を表現したType構造体を生成し、そのアドレスをtyメンバにセットします。
ノード型に応じて型付け処理を行う(ND_ADD)
case ND_ADD:
if (node->rhs->ty->kind == TY_PTR) {
Node *tmp = node->lhs;
node->lhs = node->rhs;
node->rhs = tmp;
}
if (node->rhs->ty->kind == TY_PTR)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;ノード型がND_ADD(+)の場合は、左右両方のオペランドが「～へのポインタ」型の場合、左右どちらか一方のオペランドが「～へのポインタ」型の場合、左右両方のオペランドが「～へのポインタ」型ではない場合、を考慮した処理を行います。
node->rhs->ty->kind == TY_PTR が真となる場合 → 右オペランドが「～へのポインタ」型の場合は、子ノードを入れ替えて左オペランドが「～へのポインタ」型になるようにします。
(右オペランドに「～へのポインタ」型を持つノードが対応する場合は、子ノードを入れ替えて、左オペランドに「～へのポインタ」型を持つノードが対応するようにします。)
node->rhs->ty->kind == TY_PTR が真となる場合 → 右オペランドが「～へのポインタ」型の場合 → 左右両方のオペランドが「～へのポインタ」型だった場合は、error_tok関数を呼び出してエラーメッセージを出力します。
node->rhs->ty->kind == TY_PTR が偽となる場合 → 右オペランドが「～へのポインタ」型ではない場合 → 左右どちらか一方のオペランドが「～へのポインタ」型だった、または、左右両方のオペランドが「～へのポインタ」型ではなかった場合は、ノードnodeの型の種類を左オペランドの型と同じ種類にします。
ノード型に応じて型付け処理を行う(ND_SUB)
case ND_SUB:
if (node->rhs->ty->kind == TY_PTR)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;ノード型がND_SUB( - )の場合は、右オペランドの型に注意して型付け処理を行います。
node->rhs->ty->kind == TY_PTR が真となる場合 → 右オペランドが「～へのポインタ」型の場合は、error_tok関数を呼び出してエラーメッセージを出力します。
node->rhs->ty->kind == TY_PTR が偽となる場合 → 右オペランドが「～へのポインタ」型ではない場合は、ノードnodeの型の種類を左オペランドの型と同じ種類にします。
ノード型に応じて型付け処理を行う(ND_ASSIGN)
case ND_ASSIGN:
node->ty = node->lhs->ty;
return;ノード型がND_ASSIGN(=)の場合は、ノードnodeの型の種類を左オペランドの型と同じ種類にします。
(ノード型がND_ASSIGN(=)の場合は、親ノードnodeが持つ型を左オペランドに対応するノードが持つ型と同じ種類にします。)
ノード型に応じて型付け処理を行う(ND_ADDR)
case ND_ADDR:
node->ty = pointer_to(node->lhs->ty);
return;ノード型が ND_ADDR(&)の場合は、pointer_to関数を呼び出して、「"子ノードnode->lhsが持つ型"へのポインタ」型を表現するType構造体を生成し、nodeのtyメンバにセットします(nodeの持つ型を「"子ノードnode->lhsが持つ型"へのポインタ」型にします)。
ノード型に応じて型付け処理を行う(ND_DEREF)
case ND_DEREF:
if (node->lhs->ty->kind == TY_PTR)
node->ty = node->lhs->ty->base;
else
node->ty = int_type();
return;
}ノード型が ND_DEREF( * )の場合は、オペランドの型が「～へのポインタ」型である場合と「～へのポインタ」型ではない場合を考慮して型付け処理を行います。
node->lhs->ty->kind == TY_PTR が真となる場合 → オペランドの型が「～へのポインタ」型の場合は、親ノードnodeが持つ型を、子ノードnode->lhs(オペランド)が持つ型が参照している型と、同じ種類の型にします。
node->lhs->ty->kind == TY_PTR が偽となる場合 → オペランドの型が「～へのポインタ」型ではない場合は、int_type関数を呼び出して親ノードnodeの型をint型にします(int_type関数を呼び出してint型を表現したType構造体を生成し、そのアドレスをtyメンバにセットします)。
int_type関数
https://github.com/rui314/chibicc/commit/1813fe470e4774c8d52b867649545d93f677323c#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R3
https://github.com/rui314/chibicc/blob/1813fe470e4774c8d52b867649545d93f677323c/type.c#L3
Type *int_type() {
Type *ty = calloc(1, sizeof(Type));
ty->kind = TY_INT;
return ty;
}int_type関数は、int型を表現するType構造体を生成します。
pointer_to関数
https://github.com/rui314/chibicc/commit/1813fe470e4774c8d52b867649545d93f677323c#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R9
https://github.com/rui314/chibicc/blob/1813fe470e4774c8d52b867649545d93f677323c/type.c#L9
Type *pointer_to(Type *base) {
Type *ty = calloc(1, sizeof(Type));
ty->kind = TY_PTR;
ty->base = base;
return ty;
}pointer_to関数は、base型へのポインタを表現するType構造体を生成します。
gen関数
https://github.com/rui314/chibicc/commit/1813fe470e4774c8d52b867649545d93f677323c#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR164
https://github.com/rui314/chibicc/blob/1813fe470e4774c8d52b867649545d93f677323c/codegen.c#L164
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_ADDR:
gen_addr(node->lhs);
return;
case ND_DEREF:
gen(node->lhs);
load();
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:
if (node->ty->kind == TY_PTR)
printf(" imul rdi, 8\n");
printf(" add rax, rdi\n");
break;
case ND_SUB:
if (node->ty->kind == TY_PTR)
printf(" imul rdi, 8\n");
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_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_ADDR:
gen_addr(node->lhs);
return;
case ND_DEREF:
gen(node->lhs);
load();
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:
if (node->ty->kind == TY_PTR)
printf(" imul rdi, 8\n");
printf(" add rax, rdi\n");
break;
case ND_SUB:
if (node->ty->kind == TY_PTR)
printf(" imul rdi, 8\n");
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_ADDの場合(加算を行う場合)とノード型がND_SUBの場合(減算を行う場合)の処理を改修します。
node->ty->kind == TY_PTR が真となる場合 → ノードの型が「～へのポインタ」型である場合は、visit関数で見たように左オペランドが「～へのポインタ」型、右オペランドが整数値となるので、右オペランドの値を8(ポインタのサイズ)倍するために、アセンブリコード" imul rdi, 8"を生成しておきます。
(chibccでは、ポインタのサイズは8バイトとなっています)
追加・修正されたコンパイラのソースコード(ステップ17、int型を扱えるコンパイラを作成する)
starts_with_reserved
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R131
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/tokenize.c#L131
char *starts_with_reserved(char *p) {
// Keyword
static char *kw[] = {"return", "if", "else", "while", "for", "int"};
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"};
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の要素としてintを追加し、intをキーワードとして扱えるようにします。
複数文字の記号を取得する(変更なし)
// 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;
peek関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R52
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/tokenize.c#L52
// Returns true if the current token matches a given string.
Token *peek(char *s) {
if (token->kind != TK_RESERVED || strlen(s) != token->len ||
memcmp(token->str, s, token->len))
return NULL;
return token;
}peek関数は、現在着目しているトークンが引数sが指定する文字列と一致する場合に、そのトークンを戻り値として取得します。
consume関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R61
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/tokenize.c#L61
// Consumes the current token if it matches a given string.
Token *consume(char *s) {
if (!peek(s))
return NULL;
Token *t = token;
token = token->next;
return t;
}
トークンを戻り値としてリターンする(変更なし)
return t;
expect関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R78
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/tokenize.c#L78
// Ensure that the current token is a given string
void expect(char *s) {
if (!peek(s))
error_tok(token, "expected \"%s\"", s);
token = token->next;
}
NodeKind
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R89
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/chibicc.h#L89
typedef enum {
ND_ADD, // +
ND_SUB, // -
ND_MUL, // *
ND_DIV, // /
ND_EQ, // ==
ND_NE, // !=
ND_LT, // <
ND_LE, // <=
ND_ASSIGN, // =
ND_ADDR, // unary &
ND_DEREF, // unary *
ND_RETURN, // "return"
ND_IF, // "if"
ND_WHILE, // "while"
ND_FOR, // "for"
ND_BLOCK, // { ... }
ND_FUNCALL, // Function call
ND_EXPR_STMT, // Expression statement
ND_VAR, // Variable
ND_NUM, // Integer
ND_NULL, // Empty statement
} NodeKind;アセンブリコードの生成で使用されないノードであることを示すノード型ND_NULLを追加します。
Var構造体
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R57
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/chibicc.h#L57
// Local variable
typedef struct Var Var;
struct Var {
char *name; // Variable name
Type *ty; // Type
int offset; // Offset from RBP
};ローカル変数の型付けを行うために、Var構造体にtyメンバを追加します。
function関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR117
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/parse.c#L117
Function *function() {
locals = NULL;
Function *fn = calloc(1, sizeof(Function));
basetype();
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構造体を生成します。
basetype、ident、 "("、 paramsを0回か1回、 ")"
basetype();
fn->name = expect_ident();
expect("(");
fn->params = read_func_params();basetype関数を呼び出して、戻り値の型を表したトークンを読み取ってType構造体を生成します。
expect_ident関数を呼び出して、戻り値の型を表したトークンの次にあるトークンが関数名(識別子)であることを確認し、その関数名をFuction構造体のnameメンバに記録します。
expect関数を呼び出して、関数名(識別子)を表したトークンの次にあるトークンが "(" であることを確認します。
read_func_params関数を呼び出して、引数を管理しているValist構造体の連結リストを作成し、その連結リストの先頭アドレスをFuction構造体のparamsメンバに記録します。
(read_func_param関数内で呼び出されるpush_var関数によって、引数を管理しているValist構造体の連結リストはローカル変数を管理しているVarList構造体の連結リストLocalsにも追加されています。)
"{"、stmtを0回以上、 "}"(変更なし)
expect("{");
Node head;
head.next = NULL;
Node *cur = &head;
while (!consume("}")) {
cur->next = stmt();
cur = cur->next;
}
Function構造体に値を設定する
fn->node = head.next; fn->locals = locals; return fn;
実装に対応する抽象構文木の(ルートノードからなる)連結リストのアドレス、ローカル変数を管理しているVarList構造体の連結リストのアドレスを記録します。
read_func_params関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR105
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/parse.c#L105
VarList *read_func_params() {
if (consume(")"))
return NULL;
VarList *head = read_func_param();
VarList *cur = head;
while (!consume(")")) {
expect(",");
cur->next = read_func_param();
cur = cur->next;
}
return head;
}
引数の有無を確認する(変更なし)
if (consume(")"))
return NULL;
VarList構造体からなる連結リストの先頭要素を生成する
VarList *head = read_func_param(); VarList *cur = head;
Valist構造体の生成・push_var関数によるVar構造体の生成をread_func_param関数で置き換えます。
VarList構造体からなる連結リストを作成する
while (!consume(")")) {
expect(",");
cur->next = read_func_param();
cur = cur->next;
}Valist構造体の生成・push_var関数によるVar構造体の生成をread_func_param関数で置き換えます。
VarList構造体をリターンする(変更なし)
return head;
read_func_param関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR94
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/parse.c#L94
VarList *read_func_param() {
VarList *vl = calloc(1, sizeof(VarList));
Type *ty = basetype();
vl->var = push_var(expect_ident(), ty);
return vl;
}read_func_param関数は、1つの引数を管理しているVarList構造体と1つの引数を表現しているVar構造体を生成します。
VarList構造体を生成する
VarList *vl = calloc(1, sizeof(VarList));
calloc関数を呼び出して、引数を管理するVarList構造体を生成します。
Var構造体を生成する
vl->var = push_var(expect_ident(), ty);
push_var関数を呼び出して、引数を表現しているVar構造体を生成し、VarList構造体のvarメンバにセットします。
VarList構造体を戻り値としてリターンする
return vl;
stmt関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR234
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/parse.c#L234
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 (tok = peek("int"))
return declaration();
Node *node = read_expr_stmt();
expect(";");
return node;
}
"return"、expr、";"(変更なし)
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 (tok = peek("int"))
return declaration();tok = peek("int")が真となる場合 → 現在着目しているトークンがintの場合は、declarationを呼び出して抽象構文木のノードを生成します。
expr、";"(変更なし)
Node *node = read_expr_stmt();
expect(";");
return node;
}
primary関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR369
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/parse.c#L369
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)
error_tok(tok, "undefined variable");
return new_var(var, tok);
}
tok = token;
if (tok->kind != TK_NUM)
error_tok(tok, "expected expression");
return new_num(expect_number(), tok);
}
"("、expr、")"(変更なし)
if (consume("(")) {
Node *node = expr();
expect(")");
return node;
}
ident、func-argsを0回か1回
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)
error_tok(tok, "undefined variable");
return new_var(var, tok);
}find_var関数を呼び出してVar構造体を取得できなかった場合 → 現在着目しているトークンが持つ変数名が宣言がされていないものだった場合は、error_tok関数を呼び出してエラーメッセージを出力します。
num(変更なし)
tok = token;
if (tok->kind != TK_NUM)
error_tok(tok, "expected expression");
return new_num(expect_number(), tok);
}
declaration関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR143
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/parse.c#L143
Node *declaration() {
Token *tok = token;
Type *ty = basetype();
Var *var = push_var(expect_ident(), ty);
if (consume(";"))
return new_node(ND_NULL, tok);
expect("=");
Node *lhs = new_var(var, tok);
Node *rhs = expr();
expect(";");
Node *node = new_binary(ND_ASSIGN, lhs, rhs, tok);
return new_unary(ND_EXPR_STMT, node, tok);
}declaration関数は、生成規則 declaration = basetype ident ("=" expr)? ";" に基づいて、抽象構文木のノードを生成します。
ident
Var *var = push_var(expect_ident(), ty);
if (consume(";"))
return new_node(ND_NULL, tok);expect_ident関数を呼び出して取得した変数名(識別子)を用いて、push_var関数を呼び出しVar構造体を生成します。
また、consume(";")が真となる場合 → 現在着目しているトークンが" ; "だった場合 → 変数の宣言時に初期化を行っていない場合は、new_node関数を呼び出してND_NULL型のノードを生成します。
basetype関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR85
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/parse.c#L85
// basetype = "int" "*"*
Type *basetype() {
expect("int");
Type *ty = int_type();
while (consume("*"))
ty = pointer_to(ty);
return ty;
}basetype関数は、型を表すトークンを読み取り、その型を表現したType構造体を生成します。
int型のキーワードを表現したType構造体を生成する
expect("int");
Type *ty = int_type();expect関数を呼び出して、現在着目しているトークンがintであることを確認してから、int_type関数を呼び出しint型を表現したType構造体を生成します。
ポインタを表現したType構造体を生成する
while (consume("*"))
ty = pointer_to(ty);
return ty;consume("*")を呼び出してトークンを取得できた場合は、そのたびにpointer_to関数を呼び出して、「～へのポインタ」型を表現したType構造体を生成します。
push_var関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR47
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/parse.c#L47
Var *push_var(char *name, Type *ty) {
Var *var = calloc(1, sizeof(Var));
var->name = name;
var->ty = ty;
VarList *vl = calloc(1, sizeof(VarList));
vl->var = var;
vl->next = locals;
locals = vl;
return var;
}
Var構造体を生成する
Var *var = calloc(1, sizeof(Var)); var->name = name; var->ty = ty;
push_var関数内でVar構造体のtyメンバを設定できるようにします。
(push_var関数内でローカル変数の型付けを行えるようにします)
変数を管理しているValist構造体を生成する(変更なし)
VarList *vl = calloc(1, sizeof(VarList)); vl->var = var; vl->next = locals; locals = vl;
生成したVar構造体をリターンする(変更なし)
return var;
visit関数
void visit(Node *node) {
if (!node)
return;
visit(node->lhs);
visit(node->rhs);
visit(node->cond);
visit(node->then);
visit(node->els);
visit(node->init);
visit(node->inc);
for (Node *n = node->body; n; n = n->next)
visit(n);
for (Node *n = node->args; n; n = n->next)
visit(n);
switch (node->kind) {
case ND_MUL:
case ND_DIV:
case ND_EQ:
case ND_NE:
case ND_LT:
case ND_LE:
case ND_FUNCALL:
case ND_NUM:
node->ty = int_type();
return;
case ND_VAR:
node->ty = node->var->ty;
return;
case ND_ADD:
if (node->rhs->ty->kind == TY_PTR) {
Node *tmp = node->lhs;
node->lhs = node->rhs;
node->rhs = tmp;
}
if (node->rhs->ty->kind == TY_PTR)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;
case ND_SUB:
if (node->rhs->ty->kind == TY_PTR)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;
case ND_ASSIGN:
node->ty = node->lhs->ty;
return;
case ND_ADDR:
node->ty = pointer_to(node->lhs->ty);
return;
case ND_DEREF:
if (node->lhs->ty->kind != TY_PTR)
error_tok(node->tok, "invalid pointer dereference");
node->ty = node->lhs->ty->base;
return;
}
}
ノードがセットされていない場合(変更なし)
if (!node)
return;
全ての子のノードに対してvisit関数を再帰的に呼び出す(変更なし)
visit(node->lhs);
visit(node->rhs);
visit(node->cond);
visit(node->then);
visit(node->els);
visit(node->init);
visit(node->inc);
for (Node *n = node->body; n; n = n->next)
visit(n);
for (Node *n = node->args; n; n = n->next)
visit(n);
ノード型に応じて型付け処理を行う(int型を付ける、変更なし)
switch (node->kind) {
case ND_MUL:
case ND_DIV:
case ND_EQ:
case ND_NE:
case ND_LT:
case ND_LE:
case ND_FUNCALL:
case ND_NUM:
node->ty = int_type();
return;
}
ノード型に応じて型付け処理を行う(ND_VAR)
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R44
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/type.c#L44
case ND_VAR:
node->ty = node->var->ty;
return;ノード型がND_VARの場合は、そのノードが持っているVar構造体のtyメンバを用いて、そのノードの型付けを行います。
ノード型に応じて型付け処理を行う(ND_ADD、変更なし)
case ND_ADD:
if (node->rhs->ty->kind == TY_PTR) {
Node *tmp = node->lhs;
node->lhs = node->rhs;
node->rhs = tmp;
}
if (node->rhs->ty->kind == TY_PTR)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;
ノード型に応じて型付け処理を行う(ND_SUB、変更なし)
case ND_SUB:
if (node->rhs->ty->kind == TY_PTR)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;
ノード型に応じて型付け処理を行う(ND_ASSIGN、変更なし)
case ND_ASSIGN:
node->ty = node->lhs->ty;
return;
ノード型に応じて型付け処理を行う(ND_ADDR、変更なし)
case ND_ADDR:
node->ty = pointer_to(node->lhs->ty);
return;
ノード型に応じて型付け処理を行う(ND_DEREF)
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R69
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/type.c#L69
case ND_DEREF:
if (node->lhs->ty->kind != TY_PTR)
error_tok(node->tok, "invalid pointer dereference");
node->ty = node->lhs->ty->base;
return;
}宣言されていない変数に型付けを行わないようにします。
node->lhs->ty->kind != TY_PTRが真となる場合 → 親ノードがND_DEREFにもかかわらず、子ノードの持つ型が「～へのポインタ」型ではない場合は、error_tok関数を呼び出してエラーメッセージを出力します。
gen関数
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR41
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/codegen.c#L41
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);
load();
return;
case ND_ASSIGN:
gen_addr(node->lhs);
gen(node->rhs);
store();
return;
case ND_ADDR:
gen_addr(node->lhs);
return;
case ND_DEREF:
gen(node->lhs);
load();
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:
if (node->ty->kind == TY_PTR)
printf(" imul rdi, 8\n");
printf(" add rax, rdi\n");
break;
case ND_SUB:
if (node->ty->kind == TY_PTR)
printf(" imul rdi, 8\n");
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_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);
load();
return;
case ND_ASSIGN:
gen_addr(node->lhs);
gen(node->rhs);
store();
return;
case ND_ADDR:
gen_addr(node->lhs);
return;
case ND_DEREF:
gen(node->lhs);
load();
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_NULLの場合は、何もせずリターンするようにします。
二項演算の対象となる値を得るためのアセンブリコードを生成する(変更なし)
gen(node->lhs);
gen(node->rhs);
printf(" pop rdi\n");
printf(" pop rax\n");
二項演算を行うアセンブリコードを生成する(変更なし)
switch (node->kind) {
case ND_ADD:
if (node->ty->kind == TY_PTR)
printf(" imul rdi, 8\n");
printf(" add rax, rdi\n");
break;
case ND_SUB:
if (node->ty->kind == TY_PTR)
printf(" imul rdi, 8\n");
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");
}
テストコード
https://github.com/rui314/chibicc/commit/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R30
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/test.sh#L30
#!/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; }'
echo OK
Makefile
https://github.com/rui314/chibicc/blob/0d0358fc85f2a74f6e37f5ca21afd57af3eaee6a/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
