chibiccを読む～Cコンパイラコードリーディング～ ステップ16
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ16に該当
github.com
追加・修正されたコンパイラのソースコード
tokenize関数
https://github.com/rui314/chibicc/commit/80ed7c425842319de78031c20fa0b04bb33fc840#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R167
https://github.com/rui314/chibicc/blob/80ed7c425842319de78031c20fa0b04bb33fc840/tokenize.c#L167
Token *tokenize() {
char *p = user_input;
Token head;
head.next = NULL;
Token *cur = &head;
while (*p) {
// Skip whitespace characters.
if (isspace(*p)) {
p++;
continue;
}
// Keyword or multi-letter punctuator
char *kw = starts_with_reserved(p);
if (kw) {
int len = strlen(kw);
cur = new_token(TK_RESERVED, cur, p, len);
p += len;
continue;
}
// Single-letter punctuator
if (strchr("+-*/()<>;={},&", *p)) {
cur = new_token(TK_RESERVED, cur, p++, 1);
continue;
}
// Identifier
if (is_alpha(*p)) {
char *q = p++;
while (is_alnum(*p))
p++;
cur = new_token(TK_IDENT, cur, q, p - q);
continue;
}
// Integer literal
if (isdigit(*p)) {
cur = new_token(TK_NUM, cur, p, 0);
char *q = p;
cur->val = strtol(p, &p, 10);
cur->len = p - q;
continue;
}
error_at(p, "invalid token");
}
new_token(TK_EOF, cur, p, 0);
return head.next;
}
文字列の先頭アドレスを取得する(変更なし)
char *p = user_input;
トークンからなる連結リストのヘッダーを作成する(変更なし)
Token head; head.next = NULL; Token *cur = &head;
空白文字の場合(変更なし)
while (*p) {
// Skip whitespace characters.
if (isspace(*p)) {
p++;
continue;
}
キーワードの場合(変更なし)
// Keyword or multi-letter punctuator
char *kw = starts_with_reserved(p);
if (kw) {
int len = strlen(kw);
cur = new_token(TK_RESERVED, cur, p, len);
p += len;
continue;
}
1文字の記号の場合
// Single-letter punctuator
if (strchr("+-*/()<>;={},&", *p)) {
cur = new_token(TK_RESERVED, cur, p++, 1);
continue;
}第一引数の文字列に"&"を追加し、"&"をトークンとして扱えるようにします。
識別子の場合(変更なし)
// Identifier
if (is_alpha(*p)) {
char *q = p++;
while (is_alnum(*p))
p++;
cur = new_token(TK_IDENT, cur, q, p - q);
continue;
}
数字の場合(変更なし)
// Integer literal
if (isdigit(*p)) {
cur = new_token(TK_NUM, cur, p, 0);
char *q = p;
cur->val = strtol(p, &p, 10);
cur->len = p - q;
continue;
}
その他の場合(変更なし)
error_at(p, "invalid token");
連結リストの先頭トークンを戻り値としてリターンする(変更なし)
return head.next;
NodeKind
https://github.com/rui314/chibicc/commit/80ed7c425842319de78031c20fa0b04bb33fc840#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R74
https://github.com/rui314/chibicc/blob/80ed7c425842319de78031c20fa0b04bb33fc840/chibicc.h#L74
// AST node
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
} NodeKind;"&"を表現したノード型 ND_ADDRと”*”を表現したノード型ND_DEREFを追加します。
unary関数
https://github.com/rui314/chibicc/commit/80ed7c425842319de78031c20fa0b04bb33fc840#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR288
https://github.com/rui314/chibicc/blob/80ed7c425842319de78031c20fa0b04bb33fc840/parse.c#L288
// unary = ("+" | "-" | "*" | "&")? unary
// | primary
Node *unary() {
Token *tok;
if (consume("+"))
return unary();
if (tok = consume("-"))
return new_binary(ND_SUB, new_num(0, tok), unary(), tok);
if (tok = consume("&"))
return new_unary(ND_ADDR, unary(), tok);
if (tok = consume("*"))
return new_unary(ND_DEREF, unary(), tok);
return primary();
}unary関数は、生成規則 unary = ("+" | "-" | "*" | "&")? unary に基づいて、抽象構文木のノードを生成します。
「"+"または"-"または"&"または"*"を0回か1回」とunaray
Token *tok;
if (consume("+"))
return unary();
if (tok = consume("-"))
return new_binary(ND_SUB, new_num(0, tok), unary(), tok);
if (tok = consume("&"))
return new_unary(ND_ADDR, unary(), tok);
if (tok = consume("*"))
return new_unary(ND_DEREF, unary(), tok);現在着目しているトークンが"&"や"*"の場合の処理を追加します。
consume("&")の戻り値がtrueとなる場合→着目しているトークンが "&" の場合は、new_unary関数を呼び出して、"&"を表現するノードを生成します。この"&"を表現するノードは、第二引数のunaryで生成されたノードを子ノードとして持ちます。
consume("*")の戻り値がtrueとなる場合→着目しているトークンが "*" の場合は、new_unary関数を呼び出して、"*"を表現するノードを生成します。この"*"を表現するノードは、第二引数のunaryで生成されたノードを子ノードとして持ちます。
primary(変更なし)
return primary();
gen関数
https://github.com/rui314/chibicc/commit/80ed7c425842319de78031c20fa0b04bb33fc840#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR57
https://github.com/rui314/chibicc/blob/80ed7c425842319de78031c20fa0b04bb33fc840/codegen.c#L57
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:
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");
};
二項演算以外を行うアセンブリコードを生成する
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;
}ノード型がND_ADDRの場合の処理(ノードの種類が"&"の場合の処理)とノード型がND_DEREFの場合の処理(ノードの種類が"*"の場合の処理)を追加します。
ノード型がND_ADDRの場合は、その子ノードnode->lhsを用いてgen_addr関数を呼び出します。子ノードnode->lhsはローカル変数を表現するノードであることを前提としているので、gen_addr関数によって、子ノードnode->lhsに対応するローカル変数のアドレスを取得するためのアセンブリコードが生成されます。
ノード型がND_DEREFの場合は、その子ノードnode->lhsを用いてgen関数を呼び出します。
gen関数によってアドレス(ノードnode->lhsの結果)を取得するためのアセンブリコードが生成されます。
そのアドレス(左辺値)を使って、アドレス(左辺値)が指定するメモリ領域から値(右辺値)を取得するアセンブリコードを生成するために、load関数を呼び出します。
二項演算の対象となる値を得るためのアセンブリコードを生成する(変更なし)
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");
gen_addr関数
https://github.com/rui314/chibicc/commit/80ed7c425842319de78031c20fa0b04bb33fc840#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR12
https://github.com/rui314/chibicc/blob/80ed7c425842319de78031c20fa0b04bb33fc840/codegen.c#L12
// Pushes the given node's address to the stack.
void gen_addr(Node *node) {
switch (node->kind) {
case ND_VAR:
printf(" lea rax, [rbp-%d]\n", node->var->offset);
printf(" push rax\n");
return;
case ND_DEREF:
gen(node->lhs);
return;
}
error_tok(node->tok, "not an lvalue");
}
左辺値を取得するためのアセンブリコードを生成する
switch (node->kind) {
case ND_VAR:
printf(" lea rax, [rbp-%d]\n", node->var->offset);
printf(" push rax\n");
return;
case ND_DEREF:
gen(node->lhs);
return;
}引数で与えられたノードのノード型がND_DEREFの場合の処理(ノードの種類が"*"の場合の処理)を追加します。
引数で与えられたノードのノード型がND_DEREFの場合、その子ノードnode->lhsを用いてgen関数を呼び出し、アドレス値(子ノードnode->lhsの結果)を取得するためのアセンブリコードを生成します(生成されたアセンブリコードの実行時は、アドレス値(子ノードnode->lhsの結果)はスタックに退避されている状態です)。
エラーメッセージを表示する(変更なし)
error_tok(node->tok, "not an lvalue");
テストコード
https://github.com/rui314/chibicc/commit/80ed7c425842319de78031c20fa0b04bb33fc840#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R94
https://github.com/rui314/chibicc/blob/80ed7c425842319de78031c20fa0b04bb33fc840/test.sh#L94
#!/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 'main() { return 0; }'
assert 42 'main() { return 42; }'
assert 21 'main() { return 5+20-4; }'
assert 41 'main() { return 12 + 34 - 5 ; }'
assert 47 'main() { return 5+6*7; }'
assert 15 'main() { return 5*(9-6); }'
assert 4 'main() { return (3+5)/2; }'
assert 10 'main() { return -10+20; }'
assert 10 'main() { return - -10; }'
assert 10 'main() { return - - +10; }'
assert 0 'main() { return 0==1; }'
assert 1 'main() { return 42==42; }'
assert 1 'main() { return 0!=1; }'
assert 0 'main() { return 42!=42; }'
assert 1 'main() { return 0<1; }'
assert 0 'main() { return 1<1; }'
assert 0 'main() { return 2<1; }'
assert 1 'main() { return 0<=1; }'
assert 1 'main() { return 1<=1; }'
assert 0 'main() { return 2<=1; }'
assert 1 'main() { return 1>0; }'
assert 0 'main() { return 1>1; }'
assert 0 'main() { return 1>2; }'
assert 1 'main() { return 1>=0; }'
assert 1 'main() { return 1>=1; }'
assert 0 'main() { return 1>=2; }'
assert 3 'main() { a=3; return a; }'
assert 8 'main() { a=3; z=5; return a+z; }'
assert 1 'main() { return 1; 2; 3; }'
assert 2 'main() { 1; return 2; 3; }'
assert 3 'main() { 1; 2; return 3; }'
assert 3 'main() { foo=3; return foo; }'
assert 8 'main() { foo123=3; bar=5; return foo123+bar; }'
assert 3 'main() { if (0) return 2; return 3; }'
assert 3 'main() { if (1-1) return 2; return 3; }'
assert 2 'main() { if (1) return 2; return 3; }'
assert 2 'main() { if (2-1) return 2; return 3; }'
assert 3 'main() { {1; {2;} return 3;} }'
assert 10 'main() { i=0; while(i<10) i=i+1; return i; }'
assert 55 'main() { i=0; j=0; while(i<=10) {j=i+j; i=i+1;} return j; }'
assert 55 'main() { i=0; j=0; for (i=0; i<=10; i=i+1) j=i+j; return j; }'
assert 3 'main() { for (;;) return 3; return 5; }'
assert 3 'main() { return ret3(); }'
assert 5 'main() { return ret5(); }'
assert 8 'main() { return add(3, 5); }'
assert 2 'main() { return sub(5, 3); }'
assert 21 'main() { return add6(1,2,3,4,5,6); }'
assert 32 'main() { return ret32(); } ret32() { return 32; }'
assert 7 'main() { return add2(3,4); } add2(x,y) { return x+y; }'
assert 1 'main() { return sub2(4,3); } sub2(x,y) { return x-y; }'
assert 55 'main() { return fib(9); } fib(x) { if (x<=1) return 1; return fib(x-1) + fib(x-2); }'
assert 3 'main() { x=3; return *&x; }'
assert 3 'main() { x=3; y=&x; z=&y; return **z; }'
assert 5 'main() { x=3; y=5; return *(&x+8); }'
assert 3 'main() { x=3; y=5; return *(&y-8); }'
assert 5 'main() { x=3; y=&x; *y=5; return x; }'
assert 7 'main() { x=3; y=5; *(&x+8)=7; return y; }'
assert 7 'main() { x=3; y=5; *(&y-8)=7; return x; }'
echo OK
Makefile
https://github.com/rui314/chibicc/blob/80ed7c425842319de78031c20fa0b04bb33fc840/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
