chibiccを読む～Cコンパイラコードリーディング～ ステップ28
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ28に該当
github.com
今回行うこと
ステップ28 テストをCで書き直す
テストコード
https://github.com/rui314/chibicc/blob/91fbea423d277b83f14bb0a819bb790b9afc450b/tests
// -*- c -*-
// This is a line comment.
/*
* This is a block comment.
*/
int g1;
int g2[4];
int assert(int expected, int actual, char *code) {
if (expected == actual) {
printf("%s => %d\n", code, actual);
} else {
printf("%s => %d expected but got %d\n", code, expected, actual);
exit(1);
}
}
int ret3() {
return 3;
return 5;
}
int add2(int x, int y) {
return x + y;
}
int sub2(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;
}
int addx(int *x, int y) {
return *x + y;
}
int sub_char(char a, char b, char c) {
return a - b - c;
}
int fib(int x) {
if (x<=1)
return 1;
return fib(x-1) + fib(x-2);
}
int main() {
assert(8, ({ int a=3; int z=5; a+z; }), "int a=3; int z=5; a+z;");
assert(0, 0, "0");
assert(42, 42, "42");
assert(5, 5, "0");
assert(41, 12 + 34 - 5 , " 12 + 34 - 5 ");
assert(5, 5, "0");
assert(15, 5*(9-6), "5*(9-6)");
assert(4, (3+5)/2, "(3+5)/2");
assert(-10, -10, "0");
assert(10, - -10, "- -10");
assert(10, - - +10, "- - +10");
assert(0, 0==1, "0==1");
assert(1, 42==42, "42==42");
assert(1, 0!=1, "0!=1");
assert(0, 42!=42, "42!=42");
assert(1, 0<1, "0<1");
assert(0, 1<1, "1<1");
assert(0, 2<1, "2<1");
assert(1, 0<=1, "0<=1");
assert(1, 1<=1, "1<=1");
assert(0, 2<=1, "2<=1");
assert(1, 1>0, "1>0");
assert(0, 1>1, "1>1");
assert(0, 1>2, "1>2");
assert(1, 1>=0, "1>=0");
assert(1, 1>=1, "1>=1");
assert(0, 1>=2, "1>=2");
assert(3, ({ int a; a=3; a; }), "int a; a=3; a;");
assert(8, ({ int a; int z; a=3; z=5; a+z; }), "int a; int z; a=3; z=5; a+z;");
assert(3, ({ int a=3; a; }), "int a=3; a;");
assert(8, ({ int a=3; int z=5; a+z; }), "int a=3; int z=5; a+z;");
assert(3, ({ int foo=3; foo; }), "int foo=3; foo;");
assert(8, ({ int foo123=3; int bar=5; foo123+bar; }), "int foo123=3; int bar=5; foo123+bar;");
assert(3, ret3(), "ret3();");
assert(3, ({ int x=0; if (0) x=2; else x=3; x; }), "int x=0; if (0) x=2; else x=3; x;");
assert(3, ({ int x=0; if (1-1) x=2; else x=3; x; }), "int x=0; if (1-1) x=2; else x=3; x;");
assert(2, ({ int x=0; if (1) x=2; else x=3; x; }), "int x=0; if (1) x=2; else x=3; x;");
assert(2, ({ int x=0; if (2-1) x=2; else x=3; x; }), "int x=0; if (2-1) x=2; else x=3; x;");
assert(3, ({ 1; {2;} 3; }), "1; {2;} 3;");
assert(10, ({ int i=0; i=0; while(i<10) i=i+1; i; }), "int i=0; i=0; while(i<10) i=i+1; i;");
assert(55, ({ int i=0; int j=0; while(i<=10) {j=i+j; i=i+1;} j; }), "int i=0; int j=0; while(i<=10) {j=i+j; i=i+1;} j;");
assert(55, ({ int i=0; int j=0; for (i=0; i<=10; i=i+1) j=i+j; j; }), "int i=0; int j=0; for (i=0; i<=10; i=i+1) j=i+j; j;");
assert(8, add2(3, 5), "add(3, 5)");
assert(2, sub2(5, 3), "sub(5, 3)");
assert(21, add6(1,2,3,4,5,6), "add6(1,2,3,4,5,6)");
assert(55, fib(9), "fib(9)");
assert(3, ({ int x=3; *&x; }), "int x=3; *&x;");
assert(3, ({ int x=3; int *y=&x; int **z=&y; **z; }), "int x=3; int *y=&x; int **z=&y; **z;");
assert(5, ({ int x=3; int y=5; *(&x+1); }), "int x=3; int y=5; *(&x+1);");
assert(5, ({ int x=3; int y=5; *(1+&x); }), "int x=3; int y=5; *(1+&x);");
assert(3, ({ int x=3; int y=5; *(&y-1); }), "int x=3; int y=5; *(&y-1);");
assert(5, ({ int x=3; int y=5; int *z=&x; *(z+1); }), "int x=3; int y=5; int *z=&x; *(z+1);");
assert(3, ({ int x=3; int y=5; int *z=&y; *(z-1); }), "int x=3; int y=5; int *z=&y; *(z-1);");
assert(5, ({ int x=3; int *y=&x; *y=5; x; }), "int x=3; int *y=&x; *y=5; x;");
assert(7, ({ int x=3; int y=5; *(&x+1)=7; y; }), "int x=3; int y=5; *(&x+1)=7; y;");
assert(7, ({ int x=3; int y=5; *(&y-1)=7; x; }), "int x=3; int y=5; *(&y-1)=7; x;");
assert(8, ({ int x=3; int y=5; addx(&x, y); }), "int x=3; int y=5; addx(&x, y);");
assert(3, ({ int x[2]; int *y=&x; *y=3; *x; }), "int x[2]; int *y=&x; *y=3; *x;");
assert(3, ({ int x[3]; *x=3; *(x+1)=4; *(x+2)=5; *x; }), "int x[3]; *x=3; *(x+1)=4; *(x+2)=5; *x;");
assert(4, ({ int x[3]; *x=3; *(x+1)=4; *(x+2)=5; *(x+1); }), "int x[3]; *x=3; *(x+1)=4; *(x+2)=5; *(x+1);");
assert(5, ({ int x[3]; *x=3; *(x+1)=4; *(x+2)=5; *(x+2); }), "int x[3]; *x=3; *(x+1)=4; *(x+2)=5; *(x+2);");
assert(0, ({ int x[2][3]; int *y=x; *y=0; **x; }), "int x[2][3]; int *y=x; *y=0; **x;");
assert(1, ({ int x[2][3]; int *y=x; *(y+1)=1; *(*x+1); }), "int x[2][3]; int *y=x; *(y+1)=1; *(*x+1);");
assert(2, ({ int x[2][3]; int *y=x; *(y+2)=2; *(*x+2); }), "int x[2][3]; int *y=x; *(y+2)=2; *(*x+2);");
assert(3, ({ int x[2][3]; int *y=x; *(y+3)=3; **(x+1); }), "int x[2][3]; int *y=x; *(y+3)=3; **(x+1);");
assert(4, ({ int x[2][3]; int *y=x; *(y+4)=4; *(*(x+1)+1); }), "int x[2][3]; int *y=x; *(y+4)=4; *(*(x+1)+1);");
assert(5, ({ int x[2][3]; int *y=x; *(y+5)=5; *(*(x+1)+2); }), "int x[2][3]; int *y=x; *(y+5)=5; *(*(x+1)+2);");
assert(6, ({ int x[2][3]; int *y=x; *(y+6)=6; **(x+2); }), "int x[2][3]; int *y=x; *(y+6)=6; **(x+2);");
assert(3, ({ int x[3]; *x=3; x[1]=4; x[2]=5; *x; }), "int x[3]; *x=3; x[1]=4; x[2]=5; *x;");
assert(4, ({ int x[3]; *x=3; x[1]=4; x[2]=5; *(x+1); }), "int x[3]; *x=3; x[1]=4; x[2]=5; *(x+1);");
assert(5, ({ int x[3]; *x=3; x[1]=4; x[2]=5; *(x+2); }), "int x[3]; *x=3; x[1]=4; x[2]=5; *(x+2);");
assert(5, ({ int x[3]; *x=3; x[1]=4; x[2]=5; *(x+2); }), "int x[3]; *x=3; x[1]=4; x[2]=5; *(x+2);");
assert(5, ({ int x[3]; *x=3; x[1]=4; 2[x]=5; *(x+2); }), "int x[3]; *x=3; x[1]=4; 2[x]=5; *(x+2);");
assert(0, ({ int x[2][3]; int *y=x; y[0]=0; x[0][0]; }), "int x[2][3]; int *y=x; y[0]=0; x[0][0];");
assert(1, ({ int x[2][3]; int *y=x; y[1]=1; x[0][1]; }), "int x[2][3]; int *y=x; y[1]=1; x[0][1];");
assert(2, ({ int x[2][3]; int *y=x; y[2]=2; x[0][2]; }), "int x[2][3]; int *y=x; y[2]=2; x[0][2];");
assert(3, ({ int x[2][3]; int *y=x; y[3]=3; x[1][0]; }), "int x[2][3]; int *y=x; y[3]=3; x[1][0];");
assert(4, ({ int x[2][3]; int *y=x; y[4]=4; x[1][1]; }), "int x[2][3]; int *y=x; y[4]=4; x[1][1];");
assert(5, ({ int x[2][3]; int *y=x; y[5]=5; x[1][2]; }), "int x[2][3]; int *y=x; y[5]=5; x[1][2];");
assert(6, ({ int x[2][3]; int *y=x; y[6]=6; x[2][0]; }), "int x[2][3]; int *y=x; y[6]=6; x[2][0];");
assert(8, ({ int x; sizeof(x); }), "int x; sizeof(x);");
assert(8, ({ int x; sizeof x; }), "int x; sizeof x;");
assert(8, ({ int *x; sizeof(x); }), "int *x; sizeof(x);");
assert(32, ({ int x[4]; sizeof(x); }), "int x[4]; sizeof(x);");
assert(96, ({ int x[3][4]; sizeof(x); }), "int x[3][4]; sizeof(x);");
assert(32, ({ int x[3][4]; sizeof(*x); }), "int x[3][4]; sizeof(*x);");
assert(8, ({ int x[3][4]; sizeof(**x); }), "int x[3][4]; sizeof(**x);");
assert(9, ({ int x[3][4]; sizeof(**x) + 1; }), "int x[3][4]; sizeof(**x) + 1;");
assert(9, ({ int x[3][4]; sizeof **x + 1; }), "int x[3][4]; sizeof **x + 1;");
assert(8, ({ int x[3][4]; sizeof(**x + 1); }), "int x[3][4]; sizeof(**x + 1);");
assert(0, g1, "g1");
g1=3;
assert(3, g1, "g1");
g2[0]=0; g2[1]=1; g2[2]=2; g2[3]=3;
assert(0, g2[0], "g2[0]");
assert(1, g2[1], "g2[1]");
assert(2, g2[2], "g2[2]");
assert(3, g2[3], "g2[3]");
assert(8, sizeof(g1), "sizeof(g1)");
assert(32, sizeof(g2), "sizeof(g2)");
assert(1, ({ char x=1; x; }), "char x=1; x;");
assert(1, ({ char x=1; char y=2; x; }), "char x=1; char y=2; x;");
assert(2, ({ char x=1; char y=2; y; }), "char x=1; char y=2; y;");
assert(1, ({ char x; sizeof(x); }), "char x; sizeof(x);");
assert(10, ({ char x[10]; sizeof(x); }), "char x[10]; sizeof(x);");
assert(1, sub_char(7, 3, 3), "sub_char(7, 3, 3)");
assert(97, "abc"[0], "\"abc\"[0]");
assert(98, "abc"[1], "\"abc\"[1]");
assert(99, "abc"[2], "\"abc\"[2]");
assert(0, "abc"[3], "\"abc\"[3]");
assert(4, sizeof("abc"), "sizeof(\"abc\")");
assert(7, "\a"[0], "\"\\a\"[0]");
assert(8, "\b"[0], "\"\\b\"[0]");
assert(9, "\t"[0], "\"\\t\"[0]");
assert(10, "\n"[0], "\"\\n\"[0]");
assert(11, "\v"[0], "\"\\v\"[0]");
assert(12, "\f"[0], "\"\\f\"[0]");
assert(13, "\r"[0], "\"\\r\"[0]");
assert(27, "\e"[0], "\"\\e\"[0]");
assert(0, "\0"[0], "\"\\0\"[0]");
assert(106, "\j"[0], "\"\\j\"[0]");
assert(107, "\k"[0], "\"\\k\"[0]");
assert(108, "\l"[0], "\"\\l\"[0]");
assert(2, ({ int x=2; { int x=3; } x; }), "int x=2; { int x=3; } x;");
assert(2, ({ int x=2; { int x=3; } int y=4; x; }), "int x=2; { int x=3; } int y=4; x;");
assert(3, ({ int x=2; { x=3; } x; }), "int x=2; { x=3; } x;");
printf("OK\n");
return 0;
}
Makefile
https://github.com/rui314/chibicc/commit/91fbea423d277b83f14bb0a819bb790b9afc450b#diff-76ed074a9305c04054cdebb9e9aad2d818052b07091de1f20cad0bbac34ffb52R11
https://github.com/rui314/chibicc/blob/91fbea423d277b83f14bb0a819bb790b9afc450b/Makefile#L11
CFLAGS=-std=c11 -g -static SRCS=$(wildcard *.c) OBJS=$(SRCS:.c=.o) chibicc: $(OBJS) $(CC) -o $@ $(OBJS) $(LDFLAGS) $(OBJS): chibicc.h test: chibicc ./chibicc tests > tmp.s gcc -static -o tmp tmp.s ./tmp clean: rm -f chibicc *.o *~ tmp* .PHONY: test clean
chibiccを読む～Cコンパイラコードリーディング～ ステップ27
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ27に該当
github.com
該当ステップなし
github.com
- 今回作成するコンパイラ
- 追加・修正されたコンパイラのソースコード(ステップ27、行コメントとブロックコメント)
- 追加・修正されたコンパイラのソースコード(該当ステップなし、ブロックのスコープに対応したコンパイラを作成する)
- テストコード
- Makefile
今回作成するコンパイラ
ステップ27 行コメントとブロックコメント(行コメントとブロックコメントを扱えるコンパイラを作成する)
↓
該当ステップなし(ブロックのスコープに対応したコンパイラを作成する)
追加・修正されたコンパイラのソースコード(ステップ27、行コメントとブロックコメント)
tokenize関数
Token *tokenize() {
char *p = user_input;
Token head;
head.next = NULL;
Token *cur = &head;
while (*p) {
// Skip whitespace characters.
if (isspace(*p)) {
p++;
continue;
}
// Skip line comments.
if (startswith(p, "//")) {
p += 2;
while (*p != '\n')
p++;
continue;
}
// Skip block comments.
if (startswith(p, "/*")) {
char *q = strstr(p + 2, "*/");
if (!q)
error_at(p, "unclosed block comment");
p = q + 2;
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;
}
// String literal
if (*p == '"') {
cur = read_string_literal(cur, p);
p += cur->len;
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;
}
コメント行の場合
https://github.com/rui314/chibicc/commit/81403b2d9969dafaaed05b8a4a85ee92bb80c89d#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R231
https://github.com/rui314/chibicc/blob/81403b2d9969dafaaed05b8a4a85ee92bb80c89d/tokenize.c#L231
// Skip line comments.
if (startswith(p, "//")) {
p += 2;
while (*p != '\n')
p++;
continue;
}startswith(p, "//") が真となる場合 → 文字&#m042;pが"//"の一部だった場合は、コメント行とみなします。
"//"の2文字分だけpをインクリメントし、さらに、文字&#m042;pが改行文字'\n'になるまでインクリメントします。
コメントアウトの場合
https://github.com/rui314/chibicc/commit/81403b2d9969dafaaed05b8a4a85ee92bb80c89d#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R239
https://github.com/rui314/chibicc/blob/81403b2d9969dafaaed05b8a4a85ee92bb80c89d/tokenize.c#L239
// Skip block comments.
if (startswith(p, "/*")) {
char *q = strstr(p + 2, "*/");
if (!q)
error_at(p, "unclosed block comment");
p = q + 2;
continue;
}startswith(p, "/*") が真となる場合 → 文字&#m042;pが"/*"の一部だった場合は、コメントアウトとみなします。
strstr関数を呼び出して、コメントアウトの開始記号"/*"以降にある文字列(第一引数)から、コメントアウトの終了記号の文字列"*/"(第二引数)を探索し、
"*/"のアドレスを戻り値として取得します。pはコメントアウトの開始記号"/*"のうち"/"を指定するアドレスなので、p+2はコメントアウトの開始記号"/*"以降にある文字列の先頭アドレスとなります。
!qが偽となる場合 → "*/"のアドレスを戻り値として取得できなかった場合は、error_at関数を呼び出してエラーメッセージを出力します。
最後に、pをq + 2で更新して、コメントアウトの終了記号の文字列"*/"の次の文字をpが指定するようにします。
キーワードの場合(変更なし)
// 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;
}
文字列リテラルの場合
// String literal
if (*p == '"') {
char *q = p++;
while (*p && *p != '"')
p++;
if (!*p)
error_at(q, "unclosed string literal");
p++;
cur = new_token(TK_STR, cur, q, p - q);
cur->contents = strndup(q + 1, p - q - 2);
cur->cont_len = p - q - 1;
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;
追加・修正されたコンパイラのソースコード(該当ステップなし、ブロックのスコープに対応したコンパイラを作成する)
push_var関数
https://github.com/rui314/chibicc/commit/5346339ae97195bed027f44b55434be803f718fa#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR65
https://github.com/rui314/chibicc/blob/5346339ae97195bed027f44b55434be803f718fa/parse.c#L65
Var *push_var(char *name, Type *ty, bool is_local) {
Var *var = calloc(1, sizeof(Var));
var->name = name;
var->ty = ty;
var->is_local = is_local;
VarList *vl = calloc(1, sizeof(VarList));
vl->var = var;
if (is_local) {
vl->next = locals;
locals = vl;
} else {
vl->next = globals;
globals = vl;
}
VarList *sc = calloc(1, sizeof(VarList));
sc->var = var;
sc->next = scope;
scope = sc;
return var;
}
Var構造体を生成する
Var *var = calloc(1, sizeof(Var)); var->name = name; var->ty = ty; var->is_local = is_local;
calloc関数を呼び出して、変数を表現したVar構造体を生成します。
変数名(name)をnameメンバに、変数の型(を表現したType構造体変数ty)をtyメンバに、ローカル変数かグローバル変数かを示すis_localをis_localメンバに、設定します。
変数を管理しているValist構造体を生成する
VarList *vl = calloc(1, sizeof(VarList));
vl->var = var;
if (is_local) {
vl->next = locals;
locals = vl;
} else {
vl->next = globals;
globals = vl;
}calloc関数を呼び出して、VarList構造体を生成します。このVarList構造体は変数を表現したVar構造体を管理するために用いられます。
is_localがtrueの場合 → Var構造体がローカル変数を表現している場合は、localsが指定する連結リストにVarList構造体を追加します。
is_localがfalseの場合 → Var構造体がグローバル変数を表現している場合は、globalsが指定する連結リストにVarList構造体を追加します。
スコープを管理しているVarList構造体を生成する
VarList *sc = calloc(1, sizeof(VarList)); sc->var = var; sc->next = scope; scope = sc;
calloc関数を呼び出して、VarList構造体を生成します。このVarList構造体は変数のスコープを管理するために用いられます。
find_var関数
https://github.com/rui314/chibicc/commit/5346339ae97195bed027f44b55434be803f718fa#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR9
https://github.com/rui314/chibicc/blob/5346339ae97195bed027f44b55434be803f718fa/parse.c#L9
// Find a variable by name.
Var *find_var(Token *tok) {
for (VarList *vl = scope; 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;
}scopeが指定する連結リストから、トークンが表現する変数名を探すようにします。
stmt_expr関数！
https://github.com/rui314/chibicc/commit/5346339ae97195bed027f44b55434be803f718fa#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR428
https://github.com/rui314/chibicc/blob/5346339ae97195bed027f44b55434be803f718fa/parse.c#L428
// stmt-expr = "(" "{" stmt stmt* "}" ")"
//
// Statement expression is a GNU C extension.
Node *stmt_expr(Token *tok) {
VarList *sc = scope;
Node *node = new_node(ND_STMT_EXPR, tok);
node->body = stmt();
Node *cur = node->body;
while (!consume("}")) {
cur->next = stmt();
cur = cur->next;
}
expect(")");
scope = sc;
if (cur->kind != ND_EXPR_STMT)
error_tok(cur->tok, "stmt expr returning void is not supported");
*cur = *cur->lhs;
return node;
}
stmt関数！
https://github.com/rui314/chibicc/commit/5346339ae97195bed027f44b55434be803f718fa#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR297
https://github.com/rui314/chibicc/blob/5346339ae97195bed027f44b55434be803f718fa/parse.c#L297
if (tok = consume("{")) {
Node head;
head.next = NULL;
Node *cur = &head;
VarList *sc = scope;
while (!consume("}")) {
cur->next = stmt();
cur = cur->next;
}
scope = sc;
Node *node = new_node(ND_BLOCK, tok);
node->body = head.next;
return node;
}
テストコード
https://github.com/rui314/chibicc/commit/5346339ae97195bed027f44b55434be803f718fa#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R194
https://github.com/rui314/chibicc/blob/5346339ae97195bed027f44b55434be803f718fa/test.sh#L194
#!/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 <(echo "$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; }'
assert 97 'int main() { return "abc"[0]; }'
assert 98 'int main() { return "abc"[1]; }'
assert 99 'int main() { return "abc"[2]; }'
assert 0 'int main() { return "abc"[3]; }'
assert 4 'int main() { return sizeof("abc"); }'
assert 7 'int main() { return "\a"[0]; }'
assert 8 'int main() { return "\b"[0]; }'
assert 9 'int main() { return "\t"[0]; }'
assert 10 'int main() { return "\n"[0]; }'
assert 11 'int main() { return "\v"[0]; }'
assert 12 'int main() { return "\f"[0]; }'
assert 13 'int main() { return "\r"[0]; }'
assert 27 'int main() { return "\e"[0]; }'
assert 0 'int main() { return "\0"[0]; }'
assert 106 'int main() { return "\j"[0]; }'
assert 107 'int main() { return "\k"[0]; }'
assert 108 'int main() { return "\l"[0]; }'
assert 0 'int main() { return ({ 0; }); }'
assert 2 'int main() { return ({ 0; 1; 2; }); }'
assert 1 'int main() { ({ 0; return 1; 2; }); return 3; }'
assert 3 'int main() { return ({ int x=3; x; }); }'
assert 2 'int main() { /* return 1; */ return 2; }'
assert 2 'int main() { // return 1;
return 2; }'
assert 2 'int main() { int x=2; { int x=3; } return x; }'
assert 2 'int main() { int x=2; { int x=3; } { int y=4; return x; }}'
assert 3 'int main() { int x=2; { x=3; } return x; }'
echo OK
Makefile
https://github.com/rui314/chibicc/blob/5346339ae97195bed027f44b55434be803f718fa/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
chibiccを読む～Cコンパイラコードリーディング～ ステップ26
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
該当ステップなし
github.com
ステップ26に該当
github.com
- 今回作成するコンパイラ
- 追加・修正されたコンパイラのソースコード(該当ステップなし、gccの拡張構文を扱えるコンパイラを作成する)
- 追加・修正されたコンパイラのソースコード(ステップ26、入力をファイルから読む)
- テストコード
- Makefile
追加・修正されたコンパイラのソースコード(該当ステップなし、gccの拡張構文を扱えるコンパイラを作成する)
NodeKind
https://github.com/rui314/chibicc/commit/9a810d65939deb65bd4cc45a65f34e774a8a9ca1#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R100
https://github.com/rui314/chibicc/blob/9a810d65939deb65bd4cc45a65f34e774a8a9ca1/chibicc.h#L100
// 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_SIZEOF, // "sizeof"
ND_BLOCK, // { ... }
ND_FUNCALL, // Function call
ND_EXPR_STMT, // Expression statement
ND_STMT_EXPR, // Statement expression
ND_VAR, // Variable
ND_NUM, // Integer
ND_NULL, // Empty statement
} NodeKind;GNUの拡張構文を表現するノード型ND_STMT_EXPRを追加します。
primary関数
https://github.com/rui314/chibicc/commit/9a810d65939deb65bd4cc45a65f34e774a8a9ca1#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR467
https://github.com/rui314/chibicc/blob/9a810d65939deb65bd4cc45a65f34e774a8a9ca1/parse.c#L467
Node *primary() {
Token *tok;
if (tok = consume("(")) {
if (consume("{"))
return stmt_expr(tok);
Node *node = expr();
expect(")");
return node;
}
if (tok = consume("sizeof"))
return new_unary(ND_SIZEOF, unary(), 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_STR) {
token = token->next;
Type *ty = array_of(char_type(), tok->cont_len);
Var *var = push_var(new_label(), ty, false);
var->contents = tok->contents;
var->cont_len = tok->cont_len;
return new_var(var, tok);
}
if (tok->kind != TK_NUM)
error_tok(tok, "expected expression");
return new_num(expect_number(), tok);
}primary関数は、生成規則 primary = "(" "{" stmt-expr-tail | "(" expr ")" | "sizeof" unary | ident func-args? | str | num に基づいて、抽象構文木のノードを生成します。
"("、"{"、stmt-expr-tail
Token *tok;
if (tok = consume("(")) {
if (consume("{"))
return stmt_expr(tok);consume("(")がトークンを取得できた、かつ、consume("{")がトークンを取得できた場合 → 現在着目しているトークンが"("、かつ、次のトークンが"("の場合は、stmt_expr関数を呼び出して、抽象構文木のノードを生成します。
"("、expr、")"
Node *node = expr();
expect(")");
return node;
}consume("(")がトークンを取得できた、かつ、consume("{")がトークンを取得できなかった場合 → 現在着目しているトークンが"("、かつ、次のトークンが"("ではなかった場合は、式に対応する抽象構文木のノードを生成するようにします。
sizeof、unary(変更なし)
if (tok = consume("sizeof"))
return new_unary(ND_SIZEOF, unary(), tok);
ident、func-argsを0回か1回(変更なし)
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);
}
str(変更なし)
tok = token;
if (tok->kind == TK_STR) {
token = token->next;
Type *ty = array_of(char_type(), tok->cont_len);
Var *var = push_var(new_label(), ty, false);
var->contents = tok->contents;
var->cont_len = tok->cont_len;
return new_var(var, tok);
}
num(変更なし)
if (tok->kind != TK_NUM)
error_tok(tok, "expected expression");
return new_num(expect_number(), tok);
stmt_expr関数
https://github.com/rui314/chibicc/commit/9a810d65939deb65bd4cc45a65f34e774a8a9ca1#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR423
https://github.com/rui314/chibicc/blob/9a810d65939deb65bd4cc45a65f34e774a8a9ca1/parse.c#L423
// stmt-expr = "(" "{" stmt stmt* "}" ")"
//
// Statement expression is a GNU C extension.
Node *stmt_expr(Token *tok) {
Node *node = new_node(ND_STMT_EXPR, tok);
node->body = stmt();
Node *cur = node->body;
while (!consume("}")) {
cur->next = stmt();
cur = cur->next;
}
expect(")");
if (cur->kind != ND_EXPR_STMT)
error_tok(cur->tok, "stmt expr returning void is not supported");
*cur = *cur->lhs;
return node;
}stmt_expr関数は、生成規則 stmt-expr = "(" "{" stmt stmt* "}" ")" に基づいて、抽象構文木を生成します。
"("、"{"
Node *node = new_node(ND_STMT_EXPR, tok);
new_node関数を呼び出して、GNUの拡張構文を表現するノードを生成します。
stmt_expr関数の呼び出し元で、既に "(" と "{" のトークンの読み取りは行われています。
stmtを0回以上、 "}"、")"
Node *cur = node->body;
while (!consume("}")) {
cur->next = stmt();
cur = cur->next;
}
expect(")");consume("}")がトークンを取得するまで → トークン列から"}"を読み取るまで、stmt関数を呼び出して文に対応している抽象構文木を生成し、生成された抽象構文木のルートノードからなる連結リストを作成します。Node型へのポインタcurは、その連結リストの終端要素を指定するようにします。
連結リストの作成が終わったら、"}"のトークンの次は")"のトークンであることが期待されているので、expect(")")を呼び出して読み取ったトークンが")"であることを確認します。
GNUの拡張構文の評価値の確認
if (cur->kind != ND_EXPR_STMT)
error_tok(cur->tok, "stmt expr returning void is not supported");
*cur = *cur->lhs;
return node;{ }内にある最後の式文の評価値がGNU拡張構文の評価値となるので、作成した連結リストの最後の要素から式文の評価値を取得できるようにします。
cur->kind != ND_EXPR_STMT が真となる場合 → 連結リストの最後の要素が式文ではない場合は、error_tok関数を呼び出してエラーメッセージを出力します。
cur->kind != ND_EXPR_STMT が偽となる場合 → 連結リストの最後の要素が式文である場合は、子ノードlhsの結果が式文の評価値となるので、連結リストの最後の要素に子ノードlhsの内容をコピーします。
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->base) {
Node *tmp = node->lhs;
node->lhs = node->rhs;
node->rhs = tmp;
}
if (node->rhs->ty->base)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;
case ND_SUB:
if (node->rhs->ty->base)
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:
if (node->lhs->ty->kind == TY_ARRAY)
node->ty = pointer_to(node->lhs->ty->base);
else
node->ty = pointer_to(node->lhs->ty);
return;
case ND_DEREF:
if (!node->lhs->ty->base)
error_tok(node->tok, "invalid pointer dereference");
node->ty = node->lhs->ty->base;
return;
case ND_SIZEOF:
node->kind = ND_NUM;
node->ty = int_type();
node->val = size_of(node->lhs->ty);
node->lhs = NULL;
return;
case ND_STMT_EXPR: {
Node *last = node->body;
while (last->next)
last = last->next;
node->ty = last->ty;
return;
}
}
}
ノード型に応じて型付け処理を行う(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、変更なし)
case ND_VAR:
node->ty = node->var->ty;
return;
ノード型に応じて型付け処理を行う(ND_ADD、変更なし)
case ND_ADD:
if (node->rhs->ty->base) {
Node *tmp = node->lhs;
node->lhs = node->rhs;
node->rhs = tmp;
}
if (node->rhs->ty->base)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;
ノード型に応じて型付け処理を行う(ND_SUB、変更なし)
case ND_SUB:
if (node->rhs->ty->base)
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:
if (node->lhs->ty->kind == TY_ARRAY)
node->ty = pointer_to(node->lhs->ty->base);
else
node->ty = pointer_to(node->lhs->ty);
return;
ノード型に応じて型付け処理を行う(ND_DEREF、変更なし)
case ND_DEREF:
if (!node->lhs->ty->base)
error_tok(node->tok, "invalid pointer dereference");
node->ty = node->lhs->ty->base;
return;
ノード型に応じて型付け処理を行う(ND_SIZEOF、変更なし)
case ND_SIZEOF:
node->kind = ND_NUM;
node->ty = int_type();
node->val = size_of(node->lhs->ty);
node->lhs = NULL;
return;
ノード型に応じて型付け処理を行う(ND_STMT_EXPR)
https://github.com/rui314/chibicc/commit/9a810d65939deb65bd4cc45a65f34e774a8a9ca1#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R109
https://github.com/rui314/chibicc/blob/9a810d65939deb65bd4cc45a65f34e774a8a9ca1/type.c#L109
case ND_STMT_EXPR: {
Node *last = node->body;
while (last->next)
last = last->next;
node->ty = last->ty;
return;
}親ノードのノード型がND_STMT_EXPR(ノードの種類がGNU拡張構文)の場合は、子ノードの連結リストから終端要素となるノードを取得し、その終端要素のノードが持つ型を親ノードnodeが持つ型とします。
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:
case ND_STMT_EXPR:
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:
case ND_STMT_EXPR:
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_STMT_EXPRの場合の処理を追加します。
https://github.com/rui314/chibicc/commit/9a810d65939deb65bd4cc45a65f34e774a8a9ca1#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR142
https://github.com/rui314/chibicc/blob/9a810d65939deb65bd4cc45a65f34e774a8a9ca1/codegen.c#L142
case ND_STMT_EXPR:
for (Node *n = node->body; n; n = n->next)
gen(n);
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");
追加・修正されたコンパイラのソースコード(ステップ26、入力をファイルから読む)
main関数
https://github.com/rui314/chibicc/commit/6a62177536c03225695db3edb26ee08e26a85c90#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR32
https://github.com/rui314/chibicc/blob/6a62177536c03225695db3edb26ee08e26a85c90/main.c#L32
int main(int argc, char **argv) {
if (argc != 2)
error("%s: invalid number of arguments", argv[0]);
// Tokenize and parse.
filename = argv[1];
user_input = read_file(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]);
トークナイズを行う
filename = argv[1]; user_input = read_file(argv[1]); token = tokenize();
コマンドライン引数argv[1]からファイル名を取得し、read_file関数を呼び出してファイルの読み込みを行います。
パースを行う(変更なし)
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);
read_file関数！
https://github.com/rui314/chibicc/commit/6a62177536c03225695db3edb26ee08e26a85c90#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR3
https://github.com/rui314/chibicc/blob/6a62177536c03225695db3edb26ee08e26a85c90/main.c#L3
// Returns the contents of a given file.
char *read_file(char *path) {
// Open and read the file.
FILE *fp = fopen(path, "r");
if (!fp)
error("cannot open %s: %s", path, strerror(errno));
int filemax = 10 * 1024 * 1024;
char *buf = malloc(filemax);
int size = fread(buf, 1, filemax - 2, fp);
if (!feof(fp))
error("%s: file too large");
// Make sure that the string ends with "\n\0".
if (size == 0 || buf[size - 1] != '\n')
buf[size++] = '\n';
buf[size] = '\0';
return buf;
}
verror_at関数！
https://github.com/rui314/chibicc/commit/6a62177536c03225695db3edb26ee08e26a85c90#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R21
https://github.com/rui314/chibicc/blob/6a62177536c03225695db3edb26ee08e26a85c90/tokenize.c#L21
// Reports an error message in the following format and exit.
//
// foo.c:10: x = y + 1;
// ^ <error message here>
void verror_at(char *loc, char *fmt, va_list ap) {
// Find a line containing `loc`.
char *line = loc;
while (user_input < line && line[-1] != '\n')
line--;
char *end = loc;
while (*end != '\n')
end++;
// Get a line number.
int line_num = 1;
for (char *p = user_input; p < line; p++)
if (*p == '\n')
line_num++;
// Print out the line.
int indent = fprintf(stderr, "%s:%d: ", filename, line_num);
fprintf(stderr, "%.*s\n", (int)(end - line), line);
// Show the error message.
int pos = loc - line + indent;
fprintf(stderr, "%*s", pos, ""); // print pos spaces.
fprintf(stderr, "^ ");
vfprintf(stderr, fmt, ap);
fprintf(stderr, "\n");
exit(1);
}
テストコード
https://github.com/rui314/chibicc/commit/6a62177536c03225695db3edb26ee08e26a85c90#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R17
https://github.com/rui314/chibicc/blob/6a62177536c03225695db3edb26ee08e26a85c90/test.sh#L17
#!/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 <(echo "$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; }'
assert 97 'int main() { return "abc"[0]; }'
assert 98 'int main() { return "abc"[1]; }'
assert 99 'int main() { return "abc"[2]; }'
assert 0 'int main() { return "abc"[3]; }'
assert 4 'int main() { return sizeof("abc"); }'
assert 7 'int main() { return "\a"[0]; }'
assert 8 'int main() { return "\b"[0]; }'
assert 9 'int main() { return "\t"[0]; }'
assert 10 'int main() { return "\n"[0]; }'
assert 11 'int main() { return "\v"[0]; }'
assert 12 'int main() { return "\f"[0]; }'
assert 13 'int main() { return "\r"[0]; }'
assert 27 'int main() { return "\e"[0]; }'
assert 0 'int main() { return "\0"[0]; }'
assert 106 'int main() { return "\j"[0]; }'
assert 107 'int main() { return "\k"[0]; }'
assert 108 'int main() { return "\l"[0]; }'
assert 0 'int main() { return ({ 0; }); }'
assert 2 'int main() { return ({ 0; 1; 2; }); }'
assert 1 'int main() { ({ 0; return 1; 2; }); return 3; }'
assert 3 'int main() { return ({ int x=3; x; }); }'
echo OK
Makefile
https://github.com/rui314/chibicc/blob/6a62177536c03225695db3edb26ee08e26a85c90/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
chibiccを読む～Cコンパイラコードリーディング～ ステップ25
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ25に該当
github.com
該当ステップなし
github.com
- 今回作成するコンパイラ
- 追加・修正されたコンパイラのソースコード(ステップ25、文字列リテラルを実装する)
- 追加・修正されたコンパイラのソースコード(該当ステップなし、特殊文字列を扱えるコンパイラを作成する)
- テストコード
- Makefile
追加・修正されたコンパイラのソースコード(ステップ25、文字列リテラルを実装する)
TokenKind
https://github.com/rui314/chibicc/commit/a1e2f21e94f00450075773489cd048dc86af6b4f#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R19
https://github.com/rui314/chibicc/blob/a1e2f21e94f00450075773489cd048dc86af6b4f/chibicc.h#L19
// Token
typedef enum {
TK_RESERVED, // Keywords or punctuators
TK_IDENT, // Identifiers
TK_STR, // String literals
TK_NUM, // Integer literals
TK_EOF, // End-of-file markers
} TokenKind;
Token構造体
https://github.com/rui314/chibicc/commit/a1e2f21e94f00450075773489cd048dc86af6b4f#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R33
https://github.com/rui314/chibicc/blob/a1e2f21e94f00450075773489cd048dc86af6b4f/chibicc.h#L33
// Token type
typedef struct Token Token;
struct Token {
TokenKind kind; // Token kind
Token *next; // Next token
int val; // If kind is TK_NUM, its value
char *str; // Token string
int len; // Token length
char *contents; // String literal contents including terminating '\0'
char cont_len; // string literal length
};ヌル終端文字列を保存するためのメンバcontentsとそのヌル終端文字列の長さを保存するためのメンバlenを追加します。
tokenize関数
https://github.com/rui314/chibicc/commit/a1e2f21e94f00450075773489cd048dc86af6b4f#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R188
https://github.com/rui314/chibicc/blob/a1e2f21e94f00450075773489cd048dc86af6b4f/tokenize.c#L188
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;
}
// String literal
if (*p == '"') {
char *q = p++;
while (*p && *p != '"')
p++;
if (!*p)
error_at(q, "unclosed string literal");
p++;
cur = new_token(TK_STR, cur, q, p - q);
cur->contents = strndup(q + 1, p - q - 2);
cur->cont_len = p - q - 1;
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;
}
文字列リテラルの場合
// String literal
if (*p == '"') {
char *q = p++;
while (*p && *p != '"')
p++;
if (!*p)
error_at(q, "unclosed string literal");
p++;
cur = new_token(TK_STR, cur, q, p - q);
cur->contents = strndup(q + 1, p - q - 2);
cur->cont_len = p - q - 1;
continue;
}*pp == '"' が真となる場合 → 文字*pが " の場合は、文字列リテラルのトークンを生成する処理を行います。
char *q = p++;
文字 " のアドレスをchar型へのポインタqに保存し(文字列の長さを算出する時に使用する)、文字 " の次の文字を得るために後置インクリメントします。
while (*p && *p != '"') p++;
文字*pが、ヌル文字、または、" になるまで、ポインタpをインクリメントします。
if (!*p) error_at(q, "unclosed string literal");
文字*pがヌル文字だった場合は、error_at関数を呼び出して、エラーメッセージを出力します。
p++;
計算の都合上、pをインクリメントします。
cur = new_token(TK_STR, cur, q, p - q);
new_token関数を呼び出して、( " と " を含む)文字列リテラルを表現したトークンを生成します。
(pをインクリメントしなかった場合は、 " と " を含む文字列の長さは、p - q + 1 = (p+1) - q となります)
cur->contents = strndup(q + 1, p - q - 2);
strndup関数を呼び出して、" と " の間にある文字列からなるヌル終端文字列を作成し、文字列リテラルを表現したトークンに保存します。
(pをインクリメントしなかった場合は、 " と " の間にある文字列からなるヌル終端文字列の長さは、p - q +1 - 2 = (p+1) - q - 2 となります)
cur->cont_len = p - q - 1;
contentsに保存した文字列からヌル終端文字の除いた文字列の長さをcont_lenに保存します。
(pをインクリメントしなかった場合は、 contentsに保存した文字列からヌル終端文字の除いた文字列の長さは、p - q +1 - 1 = (p+1) - q - 1 となります)
数字の場合(変更なし)
// 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;
Var構造体
https://github.com/rui314/chibicc/commit/a1e2f21e94f00450075773489cd048dc86af6b4f#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R69
https://github.com/rui314/chibicc/commit/a1e2f21e94f00450075773489cd048dc86af6b4f#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R69
// Variable
typedef struct Var Var;
struct Var {
char *name; // Variable name
Type *ty; // Type
bool is_local; // local or global
// Local variable
int offset; // Offset from RBP
// Global variable
char *contents;
int cont_len;
};ヌル終端文字列を保存するメンバcontentsとヌル終端文字列の長さ(ヌル文字を除く)を保存するメンバcont_lenを追加します。
primary関数
https://github.com/rui314/chibicc/commit/a1e2f21e94f00450075773489cd048dc86af6b4f#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR468
https://github.com/rui314/chibicc/blob/a1e2f21e94f00450075773489cd048dc86af6b4f/parse.c#L468
// primary = "(" expr ")" | "sizeof" unary | ident func-args? | str | num
// args = "(" ident ("," ident)* ")"
Node *primary() {
Token *tok;
if (consume("(")) {
Node *node = expr();
expect(")");
return node;
}
if (tok = consume("sizeof"))
return new_unary(ND_SIZEOF, unary(), 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_STR) {
token = token->next;
Type *ty = array_of(char_type(), tok->cont_len);
Var *var = push_var(new_label(), ty, false);
var->contents = tok->contents;
var->cont_len = tok->cont_len;
return new_var(var, tok);
}
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;
}
sizeof、unary(変更なし)
if (tok = consume("sizeof"))
return new_unary(ND_SIZEOF, unary(), tok);
ident、func-argsを0回か1回(変更なし)
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);
}
str
tok = token;
if (tok->kind == TK_STR) {
token = token->next;
Type *ty = array_of(char_type(), tok->cont_len);
Var *var = push_var(new_label(), ty, false);
var->contents = tok->contents;
var->cont_len = tok->cont_len;
return new_var(var, tok);
}トークン型がTK_STR(トークンの種類が文字列リテラル)の場合の処理を追加します。
Type *ty = array_of(char_type(), tok->cont_len);
array_of関数を呼び出して、char型の配列を表現したType構造体を生成します。
Var *var = push_var(new_label(), ty, false);
new_label関数を呼び出して、data領域に保存するために用いるラベル名を生成します。
そのラベル名と先ほど生成したタイプ構造体を用いてpush_var関数を呼び出し、配列名を表現したVar構造体を生成します。
文字列リテラルはdata領域に保存するので、第三引数をfalseにします(グローバル変数と同様の扱いとします)。
var->contents = tok->contents;
var->cont_len = tok->cont_len;
トークンが保有している文字列リテラルと文字列リテラルの長さをVar構造体にコピーします。
return new_var(var, tok);
最後に、 new_var関数を呼び出して、変数(配列名)を表現するノードを生成します。
num(変更なし)
if (tok->kind != TK_NUM)
error_tok(tok, "expected expression");
return new_num(expect_number(), tok);
new_label関数
https://github.com/rui314/chibicc/commit/a1e2f21e94f00450075773489cd048dc86af6b4f#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR74
https://github.com/rui314/chibicc/blob/a1e2f21e94f00450075773489cd048dc86af6b4f/parse.c#L74
char *new_label() {
static int cnt = 0;
char buf[20];
sprintf(buf, ".L.data.%d", cnt++);
return strndup(buf, 20);
}new_label関数は、data領域に保存するために用いるラベル名を生成します。
static int cnt = 0;
new_label関数によって生成されるラベルを識別する番号を定義します。
static修飾子を付けているので、関数の実行が終了した後も、変数cntに値が保存されます。
char buf[20];
sprintf(buf, ".L.data.%d", cnt++);
sprintf関数を呼び出して、第二引数で指定されたラベル名(フォーマットの文字列)を、第一引数で指定されたbufに保存します。
return strndup(buf, 20);
strndup関数を呼び出して、割り当てられたメモリ領域にラベル名(フォーマットの文字列)を保存し、そのメモリ領域のアドレスを戻り値としてリターンします。
emit_data関数
https://github.com/rui314/chibicc/commit/a1e2f21e94f00450075773489cd048dc86af6b4f#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR233
https://github.com/rui314/chibicc/blob/a1e2f21e94f00450075773489cd048dc86af6b4f/codegen.c#L233
void emit_data(Program *prog) {
printf(".data\n");
for (VarList *vl = prog->globals; vl; vl = vl->next) {
Var *var = vl->var;
printf("%s:\n", var->name);
if (!var->contents) {
printf(" .zero %d\n", size_of(var->ty));
continue;
}
for (int i = 0; i < var->cont_len; i++)
printf(" .byte %d\n", var->contents[i]);
}
}
データセクションを指定するディレクティブを生成する(変更なし)
printf(".data\n");
グローバル変数のラベルを生成する(変更なし)
for (VarList *vl = prog->globals; vl; vl = vl->next) {
Var *var = vl->var;
printf("%s:\n", var->name);
グローバル変数の値を初期化する
if (!var->contents) {
printf(" .zero %d\n", size_of(var->ty));
continue;
}
for (int i = 0; i < var->cont_len; i++)
printf(" .byte %d\n", var->contents[i]);
}!var->contentsが真となる場合 → var->contentsに文字列リテラルが保存されていない場合は、型のサイズに応じてnバイトのメモリ領域を0で初期化する.zero n ディレクティブを生成します。
!var->contentsが偽となる場合 → var->contentsに文字列リテラルが保存されている場合は、.byteディレクティブと1つの文字データを用いて、1バイトずつ文字列リテラルを定義するアセンブリコードを生成します。
追加・修正されたコンパイラのソースコード(該当ステップなし、特殊文字列を扱えるコンパイラを作成する)
tokenize関数
https://github.com/rui314/chibicc/commit/ff171ad6dbfdeddcdaca47364cced2c636c43dca#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R232
https://github.com/rui314/chibicc/blob/ff171ad6dbfdeddcdaca47364cced2c636c43dca/tokenize.c#L232
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;
}
// String literal
if (*p == '"') {
cur = read_string_literal(cur, p);
p += cur->len;
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;
}
文字列リテラルの場合
// String literal
if (*p == '"') {
cur = read_string_literal(cur, p);
p += cur->len;
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;
read_string_literal関数
https://github.com/rui314/chibicc/commit/ff171ad6dbfdeddcdaca47364cced2c636c43dca#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R165
https://github.com/rui314/chibicc/blob/ff171ad6dbfdeddcdaca47364cced2c636c43dca/tokenize.c#L165
Token *read_string_literal(Token *cur, char *start) {
char *p = start + 1;
char buf[1024];
int len = 0;
for (;;) {
if (len == sizeof(buf))
error_at(start, "string literal too large");
if (*p == '\0')
error_at(start, "unclosed string literal");
if (*p == '"')
break;
if (*p == '\\') {
p++;
buf[len++] = get_escape_char(*p++);
} else {
buf[len++] = *p++;
}
}
Token *tok = new_token(TK_STR, cur, start, p - start + 1);
tok->contents = malloc(len + 1);
memcpy(tok->contents, buf, len);
tok->contents[len] = '\0';
tok->cont_len = len + 1;
return tok;
}read_string_literal関数は、文字列リテラルを表現するトークンを生成します。
char *p = start + 1;
startは文字列リテラルの先頭にある " を指定するアドレスなので、start+1は " の次にある文字を指定するアドレスとなります。
for文内の処理について
文字列リテラルから読み取った文字*pを配列bufに保存していきます。lenは配列bufのインデックスです。
文字列リテラルから文字を読み取ることができても配列bufにこれ以上文字を保存できない場合(len == sizeof(buf)) が真となる場合)や、文字列リテラルの途中でヌル文字が出現した場合(*p == '\0' が真となる場合)は、error_at関数を呼び出しエラーメッセージを出力します。
文字列リテラルから " を読み取った場合(*p == '"' が真となる場合)は、文字列リテラルの末端に達したとみなし、for文から脱出します。
文字列リテラルから \ を読み取った場合(*p == '\\' が真となる場合)は、 get_escape_char関数を呼び出して、特殊文字を配列bufに保存し、pとlenをインクリメントします(後置インクリメントしています)。
それ以外の場合は、pとlenをインクリメントします。
Token *tok = new_token(TK_STR, cur, start, p - start + 1);以降の処理
new_token関数を呼び出して、( " と " を含む)文字列リテラルを表現したトークンを生成し、文字列リテラルをヌル終端文字列にしてから生成したトークンに保存します。また、生成したトークンに保存した文字列からヌル終端文字の除いた文字列の長さをcont_lenに保存します。
get_escape_char関数
https://github.com/rui314/chibicc/commit/ff171ad6dbfdeddcdaca47364cced2c636c43dca#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R150
https://github.com/rui314/chibicc/blob/ff171ad6dbfdeddcdaca47364cced2c636c43dca/tokenize.c#L150
char get_escape_char(char c) {
switch (c) {
case 'a': return '\a';
case 'b': return '\b';
case 't': return '\t';
case 'n': return '\n';
case 'v': return '\v';
case 'f': return '\f';
case 'r': return '\r';
case 'e': return 27;
case '0': return 0;
default: return c;
}
}get_escape_char関数は、引数cで指定された文字データに応じて、特殊文字を取得します。
テストコード
https://github.com/rui314/chibicc/commit/ff171ad6dbfdeddcdaca47364cced2c636c43dca#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R171
https://github.com/rui314/chibicc/blob/ff171ad6dbfdeddcdaca47364cced2c636c43dca/test.sh#L171
#!/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; }'
assert 97 'int main() { return "abc"[0]; }'
assert 98 'int main() { return "abc"[1]; }'
assert 99 'int main() { return "abc"[2]; }'
assert 0 'int main() { return "abc"[3]; }'
assert 4 'int main() { return sizeof("abc"); }'
assert 7 'int main() { return "\a"[0]; }'
assert 8 'int main() { return "\b"[0]; }'
assert 9 'int main() { return "\t"[0]; }'
assert 10 'int main() { return "\n"[0]; }'
assert 11 'int main() { return "\v"[0]; }'
assert 12 'int main() { return "\f"[0]; }'
assert 13 'int main() { return "\r"[0]; }'
assert 27 'int main() { return "\e"[0]; }'
assert 0 'int main() { return "\0"[0]; }'
assert 106 'int main() { return "\j"[0]; }'
assert 107 'int main() { return "\k"[0]; }'
assert 108 'int main() { return "\l"[0]; }'
echo OK
Makefile
https://github.com/rui314/chibicc/blob/ff171ad6dbfdeddcdaca47364cced2c636c43dca/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
chibiccを読む～Cコンパイラコードリーディング～ ステップ24
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ24に該当
github.com
- 今回作成するコンパイラ
- 追加・修正されたコンパイラのソースコード
- テストコード
- Makefile
追加・修正されたコンパイラのソースコード
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
chibiccを読む～Cコンパイラコードリーディング～ ステップ23
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ23に該当
github.com
- 今回作成するコンパイラ
- 追加・修正されたコンパイラのソースコード
- テストコード
- Makefile
追加・修正されたコンパイラのソースコード
main関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR10
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/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();
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 = 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();
パースを行う
Program *prog = program();
Function構造体から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 = offset;
}Program構造体progからFunction構造体fnを取得するようにします。
アセンブリコードを生成する(変更なし)
// Traverse the AST to emit assembly. codegen(prog); return 0;
Program構造体
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R137
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/chibicc.h#L137
typedef struct {
VarList *globals;
Function *fns;
} Program;構造体の型をFunction型からProgram型へ変更します。
program関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR97
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/parse.c#L97
// program = (global-var | function)*
Program *program() {
Function head;
head.next = NULL;
Function *cur = &head;
globals = NULL;
while (!at_eof()) {
if (is_function()) {
cur->next = function();
cur = cur->next;
} else {
global_var();
}
}
Program *prog = calloc(1, sizeof(Program));
prog->globals = globals;
prog->fns = head.next;
return prog;
}
Program構造体からなる連結リストのヘッダーを作成する
Function head; head.next = NULL; Function *cur = &head; globals = NULL;
Program構造体からなる連結リストを作成する
while (!at_eof()) {
if (is_function()) {
cur->next = function();
cur = cur->next;
} else {
global_var();
}
}is_function関数の戻り値がtrueとなる場合は関数定義のパースを行うようにし、is_function関数の戻り値がfalseとなる場合はグローバル変数のパースを行うようにします。
is_function関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR89
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/parse.c#L89
bool is_function() {
Token *tok = token;
basetype();
bool isfunc = consume_ident() && consume("(");
token = tok;
return isfunc;
}is_function関数は、トークン列を先読みして、そのトークン列が関数定義の構文の一部かグローバル変数の構文の一部かを判定します。
Token *tok = token;
現在着目しているトークンを指定するアドレスをtokに保存しておきます。
basetype();
basetype関数を呼び出して、型となるキーワードを表現しているトークンを読み取ります。
bool isfunc = consume_ident() && consume("(");
consume_ident()の戻り値とconsume("(")の戻り値の論理積の結果を取得します。
consume_ident()を呼び出して識別子を表現したトークンを取得できた、かつ、consume("(")を呼び出して"("を表現したトークンを取得できた場合に、isfuncはtrueとなります(そのトークン列が関数定義の構文の一部であると判断します)。
token = tok;
現在着目しているトークンをis_function関数内でトークン列を読み進める前の状態に戻しておきます。
return isfunc
判定結果を戻り値としてリターンします。
read_func_param関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR143
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/parse.c#L143
VarList *read_func_param() {
Type *ty = basetype();
char *name = expect_ident();
ty = read_type_suffix(ty);
VarList *vl = calloc(1, sizeof(VarList));
vl->var = push_var(name, ty, true);
return vl;
}
Type構造体を生成する(変更なし)
Type *ty = basetype();
変数名か配列名になる識別子を取得する(変更なし)
char *name = expect_ident();
Type構造体を更新する(変更なし)
ty = read_type_suffix(ty);
VarList構造体を生成する
VarList *vl = calloc(1, sizeof(VarList)); vl->var = push_var(name, ty, true);
push_var関数の第三引数にtrueを指定して、ローカル変数を表現したVar構造体を生成するようにします。
Var構造体を生成する(変更なし)
return vl;
declaration関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR204
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/parse.c#L204
// declaration = basetype ident ("[" num "]")* ("=" expr)? ";"
Node *declaration() {
Token *tok = token;
Type *ty = basetype();
char *name = expect_ident();
ty = read_type_suffix(ty);
Var *var = push_var(name, ty, true);
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);
}
basetype(変更なし)
Type *ty = basetype();
ident(変更なし)
char *name = expect_ident();
「"["とnumと"]"」を0回以上
ty = read_type_suffix(ty); Var *var = push_var(name, ty, true);
push_var関数の第三引数にtrueを指定して、ローカル変数を表現したVar構造体を生成するようにします。
「"="とexpr」を0回か1回(変更なし)
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);
global_var関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR189
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/parse.c#L189
// global-var = basetype ident ("[" num "]")* ";"
void global_var() {
Type *ty = basetype();
char *name = expect_ident();
ty = read_type_suffix(ty);
expect(";");
push_var(name, ty, false);
}global_var関数は、生成規則 global-var = basetype ident ("[" num "]")* ";" に基づいて、抽象構文木のノードを生成します。
ident
char *name = expect_ident();
この時点では、トークンから読み取った識別子が配列名か変数名かわからないので、expect_ident関数を呼び出しその識別子を保存しておきます。
「"["、num、"]"」を0回以上
ty = read_type_suffix(ty);
read_type_suffix関数を呼び出して、トークンを読み取りながら、グローバル変数の型が、配列型か、それ以外の型か、を決定します。
";"
expect(";");
push_var(name, ty, false); expect(";")を呼び出して、現在着目しているトークンが";"であることを確認します。
最後に、配列名か変数名をグルーバル変数を表現するVar構造体を生成します。
globals変数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR4
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/parse.c#L4
VarList *globals;
グローバル変数を管理しているVarList構造体の先頭要素を指定するポインタglobalsを定義します。
Var構造体
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R57
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/chibicc.h#L57
// Variable
typedef struct Var Var;
struct Var {
char *name; // Variable name
Type *ty; // Type
bool is_local; // local or global
// Local variable
int offset; // Offset from RBP
};Var構造体がローカル変数を表現しているのかグローバル変数を表現しているのかを区別するために、is_localメンバを追加します。
push_var関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR62
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/parse.c#L63
Var *push_var(char *name, Type *ty, bool is_local) {
Var *var = calloc(1, sizeof(Var));
var->name = name;
var->ty = ty;
var->is_local = is_local;
VarList *vl = calloc(1, sizeof(VarList));
vl->var = var;
if (is_local) {
vl->next = locals;
locals = vl;
} else {
vl->next = globals;
globals = vl;
}
return var;
}
Var構造体を生成する
Var *var = calloc(1, sizeof(Var)); var->name = name; var->ty = ty; var->is_local = is_local;
生成したVar構造体に、ローカル変数かグローバル変数かを示すis_localフラグをセットします。
変数を管理しているValist構造体を生成する
VarList *vl = calloc(1, sizeof(VarList));
vl->var = var;
if (is_local) {
vl->next = locals;
locals = vl;
} else {
vl->next = globals;
globals = vl;
}is_localがtrueの場合 → Var構造体がローカル変数を表現している場合は、localsが指定する連結リストにVarList構造体を追加します。
is_localがfalseの場合 → Var構造体がグローバル変数を表現している場合は、globalsが指定する連結リストにVarList構造体を追加します。
生成したVar構造体をリターンする(変更なし)
return var;
find_var関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR14
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/parse.c#L14
// 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;
}
for (VarList *vl = globals; 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;
}globalsが指定する連結リストからもVar構造体を探索するようにします。
add_type関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R100
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/type.c#L100
void add_type(Program *prog) {
for (Function *fn = prog->fns; fn; fn = fn->next)
for (Node *node = fn->node; node; node = node->next)
visit(node);
}構造体変数progの型をFunctionからProgramへ変更します。
codegen関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR263
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/codegen.c#L263
void codegen(Program *prog) {
printf(".intel_syntax noprefix\n");
emit_data(prog);
emit_text(prog);
}
ディレクティブを生成する
printf(".intel_syntax noprefix\n");
emit_data関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR221
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/codegen.c#L221
void emit_data(Program *prog) {
printf(".data\n");
for (VarList *vl = prog->globals; vl; vl = vl->next) {
Var *var = vl->var;
printf("%s:\n", var->name);
printf(" .zero %d\n", size_of(var->ty));
}
}emit_data関数は、data領域に配置させるアセンブリコードを生成します。
データセクションを指定するディレクティブを生成する
printf(".data\n");data領域の開始を示す.dataディレクティブを生成します。
emit_text関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR231
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/codegen.c#L231
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) {
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");
}
}emit_text関数は、text領域に配置させるアセンブリコードを生成します。
テキストセクションを指定するディレクティブを生成する
printf(".text\n");text領域の開始を示す.textディレクティブを生成します。
関数名のラベルを生成する
for (Function *fn = prog->fns; 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);
引数の値をスタックに退避させるアセンブリコードを生成する
// 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");
gen_addr関数
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR13
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/codegen.c#L13
// Pushes the given node's address to the stack.
void gen_addr(Node *node) {
switch (node->kind) {
case ND_VAR: {
Var *var = node->var;
if (var->is_local) {
printf(" lea rax, [rbp-%d]\n", var->offset);
printf(" push rax\n");
} else {
printf(" push offset %s\n", var->name);
}
return;
}
case ND_DEREF:
gen(node->lhs);
return;
}
error_tok(node->tok, "not an lvalue");
}
左辺値を取得するためのアセンブリコードを生成する
switch (node->kind) {
case ND_VAR: {
Var *var = node->var;
if (var->is_local) {
printf(" lea rax, [rbp-%d]\n", var->offset);
printf(" push rax\n");
} else {
printf(" push offset %s\n", var->name);
}
return;
}
case ND_DEREF:
gen(node->lhs);
return;
}ノード型がND_VARの場合(ノードがローカル変数を表現している場合)における処理の改修です。
var->is_localがfalseになる場合 → Var構造体がグローバル変数を表現している場合は、グローバル変数が配置されているアドレスをスタックに退避させるアセンブリコード "push offset グローバル変数名"を生成します。アセンブリコードにあるoffset演算子は変数名からアドレスを取得します。
エラーメッセージを表示する(変更なし)
error_tok(node->tok, "not an lvalue");
テストコード
https://github.com/rui314/chibicc/commit/97935ca2fadd1fe61e81b98cc0e528781a7ec868#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R147
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/test.sh#L147
#!/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); }'
echo OK
Makefile
https://github.com/rui314/chibicc/blob/97935ca2fadd1fe61e81b98cc0e528781a7ec868/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
chibiccを読む～Cコンパイラコードリーディング～ ステップ20, 21, 22
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ21に該当
github.com
ステップ22に該当
github.com
ステップ20に該当
github.com
- 今回作成するコンパイラ
- 追加・修正されたコンパイラのソースコード(ステップ21、配列を扱えるコンパイラを実装する)
- 追加・修正されたコンパイラのソースコード(ステップ22、配列の添字を扱えるコンパイラを作成する)
- 追加・修正されたコンパイラのソースコード(ステップ20、sizeof演算子を扱えるコンパイラを作成する)
- starts_with_reserved関数
- NodeKind
- primary関数
- visit関数
- ノードがセットされていない場合(変更なし)
- 全ての子のノードに対してvisit関数を再帰的に呼び出す(変更なし)
- ノード型に応じて型付け処理を行う(int型を付ける、変更なし)
- ノード型に応じて型付け処理を行う(ND_VAR、変更なし)
- ノード型に応じて型付け処理を行う(ND_ADD、変更なし)
- ノード型に応じて型付け処理を行う(ND_SUB、変更なし)
- ノード型に応じて型付け処理を行う(ND_ASSIGN、変更なし)
- ノード型に応じて型付け処理を行う(ND_ADDR、変更なし)
- ノード型に応じて型付け処理を行う(ND_DEREF、変更なし)
- ノード型に応じて型付け処理を行う(ND_SIZEOF)
- テストコード
- Makefile
今回作成するコンパイラ
配列を実装する(ステップ21、配列を扱えるコンパイラを作成する)
↓
配列の添字を実装する(ステップ22、配列の添字を扱えるコンパイラを作成する)
↓
sizeof演算子(ステップ20、sizeof演算子を扱えるコンパイラを作成する)
追加・修正されたコンパイラのソースコード(ステップ21、配列を扱えるコンパイラを実装する)
main関数
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR17
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/main.c#L17
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) {
Var *var = vl->var;
offset += size_of(var->ty);
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();
型付けを行う(変更なし)
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) {
Var *var = vl->var;
offset += size_of(var->ty);
var->offset = offset;
}
fn->stack_size = offset;
}引数やローカル変数に割り当てるアドレス(スタックのベースアドレスからのオフセットアドレス)を8バイトからsize_of(var->ty)バイト(型のバイトサイズ)へ変更します。
アセンブリコードを生成する(変更なし)
// Traverse the AST to emit assembly. codegen(prog); return 0;
tokenize関数
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R173
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/tokenize.c#L173
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;
declaration関数
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR155
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/parse.c#L155
// declaration = basetype ident ("[" num "]")* ("=" expr) ";"
Node *declaration() {
Token *tok = token;
Type *ty = basetype();
char *name = expect_ident();
ty = read_type_suffix(ty);
Var *var = push_var(name, 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 ("[" num "]")* ("=" expr)? ";" に基づいて、抽象構文木のノードを生成します。
basetype(変更なし)
Type *ty = basetype();
ident
char *name = expect_ident();
この時点では、トークンから読み取った識別子が変数名か配列名かわからないので、expect_ident関数を呼び出し名前を保存しておきます。
「"["とnumと"]"」を0回以上
ty = read_type_suffix(ty); Var *var = push_var(name, ty);
read_type_suffix関数を呼び出して、トークンを読み取りながら、データ型が配列型がそれ以外の型かを決定します。
その後、配列名かローカル変数名を表現するVar構造体を生成します。
「"="とexpr」を0回か1回(変更なし)
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);
read_func_param関数
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR105
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/parse.c#L105
VarList *read_func_param() {
Type *ty = basetype();
char *name = expect_ident();
ty = read_type_suffix(ty);
VarList *vl = calloc(1, sizeof(VarList));
vl->var = push_var(name, ty);
return vl;
}
Type構造体を生成する(変更なし)
Type *ty = basetype();
変数名か配列名になる識別子を取得する
char *name = expect_ident();
この時点では、トークンから読み取った識別子が変数名か配列名かわからないので、expect_ident関数を呼び出し名前を保存しておきます。
Type構造体を更新する
ty = read_type_suffix(ty);
read_type_suffix関数を呼び出して、トークンを読み取りながら、データ型が配列型がそれ以外の型かを決定します。
VarList構造体を生成する(変更なし)
VarList *vl = calloc(1, sizeof(VarList));
Var構造体を生成する(変更なし)
vl->var = push_var(name, ty);
read_type_suffix関数
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR94
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/parse.c#L94
Type *read_type_suffix(Type *base) {
if (!consume("["))
return base;
int sz = expect_number();
expect("]");
base = read_type_suffix(base);
return array_of(base, sz);
}read_type_suffix関数は、トークンを読み取って、データ型が配列型か配列型以外かを決定します。
!consume("[") が真となる場合 → 現在着目しているトークンが"["ではなかった場合は、Type構造体baseを戻り値としてリターンします。
"["の次のトークンは、配列のサイズを指定する整数値であることが期待されているので、expect_number関数を呼び出して、その整数値を取得します。
多次元配列に対応するために、read_type_suffix関数を再帰的に呼び出し、baseを更新します。
最後に、array_of関数を呼び出して、配列型を表現するType構造体を生成します。
TypeKind
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R139
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/chibicc.h#L139
typedef enum { TY_INT, TY_PTR, TY_ARRAY } TypeKind;配列型を表現するTY_ARRAYを追加します。
Type構造体
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R144
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/chibicc.h#L144
struct Type {
TypeKind kind;
Type *base;
int array_size;
};配列のサイズを記録するためにarray_sizeメンバを追加します。
array_of関数
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R16
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/type.c#L16
Type *array_of(Type *base, int size) {
Type *ty = calloc(1, sizeof(Type));
ty->kind = TY_ARRAY;
ty->base = base;
ty->array_size = size;
return ty;
}array_of関数は、配列型を表現するType構造体を生成します。
size_of関数
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R24
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/type.c#L24
int size_of(Type *ty) {
if (ty->kind == TY_INT || ty->kind == TY_PTR)
return 8;
assert(ty->kind == TY_ARRAY);
return size_of(ty->base) * ty->array_size;
}sizet_of関数は、引数で指定されType構造体が表現する型に応じて、その型のサイズを取得します。
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->base) {
Node *tmp = node->lhs;
node->lhs = node->rhs;
node->rhs = tmp;
}
if (node->rhs->ty->base)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;
case ND_SUB:
if (node->rhs->ty->base)
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:
if (node->lhs->ty->kind == TY_ARRAY)
node->ty = pointer_to(node->lhs->ty->base);
else
node->ty = pointer_to(node->lhs->ty);
return;
case ND_DEREF:
if (!node->lhs->ty->base)
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、変更なし)
case ND_VAR:
node->ty = node->var->ty;
return;
ノード型に応じて型付け処理を行う(ND_ADD)
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R63
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/type.c#L63
case ND_ADD:
if (node->rhs->ty->base) {
Node *tmp = node->lhs;
node->lhs = node->rhs;
node->rhs = tmp;
}
if (node->rhs->ty->base)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;子ノードrhsの型が「~へのポインタ」型であるかどうかを、子ノードが持つType構造体がさらにType構造体を参照しているかどうかで、判断するようにします。
ノード型に応じて型付け処理を行う(ND_SUB)
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R73
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/type.c#L73
case ND_SUB:
if (node->rhs->ty->base)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;子ノードrhsの型が「~へのポインタ」型であるかどうかを、子ノードが持つType構造体がさらにType構造体を参照しているかどうかで、判断するようにします。
ノード型に応じて型付け処理を行う(ND_ASSIGN、変更なし)
case ND_ASSIGN:
node->ty = node->lhs->ty;
return;
ノード型に応じて型付け処理を行う(ND_ADDR)
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R81
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/type.c#L81
case ND_ADDR:
if (node->lhs->ty->kind == TY_ARRAY)
node->ty = pointer_to(node->lhs->ty->base);
else
node->ty = pointer_to(node->lhs->ty);
return;
}子ノードlhsの持つType構造体が配列型を表現している場合は(子ノードlhsの持つ型が配列型の場合は)、その配列型を表現しているType構造体が参照しているType構造体を用いてpointer_to関数を呼び出し、親ノードが持つ型(Type構造体)を「base型へのポインタ」型にします。
ノード型に応じて型付け処理を行う(ND_DEREF)
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R87
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/type.c#L87
case ND_DEREF:
if (!node->lhs->ty->base)
error_tok(node->tok, "invalid pointer dereference");
node->ty = node->lhs->ty->base;
return;子ノードlhsの型が「~へのポインタ」型であるかどうかを、子ノードが持つType構造体がさらにType構造体を参照しているかどうかで、判断するようにします。
また、!node->lhs->ty->baseが真となる場合 → 子ノードが持つType構造体がさらにType構造体を参照していなかった場合 → 子ノードlhsの型が「~へのポインタ」型でなかった場合は、 error_tok関数を呼び出してエラーメッセージを出力します。
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();
return;
case ND_ASSIGN:
gen_lval(node->lhs);
gen(node->rhs);
store();
return;
case ND_ADDR:
gen_addr(node->lhs);
return;
case ND_DEREF:
gen(node->lhs);
if (node->ty->kind != TY_ARRAY)
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->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();
return;
case ND_ASSIGN:
gen_lval(node->lhs);
gen(node->rhs);
store();
return;
case ND_ADDR:
gen_addr(node->lhs);
return;
case ND_DEREF:
gen(node->lhs);
if (node->ty->kind != TY_ARRAY)
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_VARの場合は(ノードがローカル変数に対応している場合は)、ノードの持つType構造体が配列型を表現していないことを確認してから、load関数を呼び出します。
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR58
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/codegen.c#L58
case ND_VAR:
gen_addr(node);
if (node->ty->kind != TY_ARRAY)
load();
return;ノード型がND_ASSIGNの場合(ノードが等号記号に対応している場合)の処理において、gen_addr(node->lhs)からgen_lval(node->lhsへ変更します。
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR62
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/codegen.c#L62
case ND_ASSIGN:
gen_lval(node->lhs);
gen(node->rhs);
store();
return;ノード型がND_DEREFの場合は(ノードが 間接参照演算子"*" に対応している場合は)、ノードの持つType構造体が配列型を表現していないことを確認してから、load関数を呼び出します。
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR71
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/codegen.c#L71
case ND_DEREF:
gen(node->lhs);
if (node->ty->kind != TY_ARRAY)
load();
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_ADDの場合(加算を行う場合)における処理の改修です。
ノードの型が「~へのポインタ」型であるかどうかを、ノードが持つType構造体がさらにType構造体を参照しているかどうかで、判断するようにします。
ノードの型が「~へのポインタ」型である場合は、右オペランドの値をsize_of(node->ty->base)倍する必要があるので、加算を行うアセンブリコード"add rax, rdi"を生成する前に、アセンブリコード" imul rdi, (「~へのポインタ」型のサイズ)"を生成するようにします。
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR174
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/codegen.c#L174
case ND_ADD:
if (node->ty->base)
printf(" imul rdi, %d\n", size_of(node->ty->base));
printf(" add rax, rdi\n");
break;ノード型がND_SUBの場合(減算を行う場合)における処理の改修です。
ノードの型が「~へのポインタ」型であるかどうかを、ノードが持つType構造体がさらにType構造体を参照しているかどうかで、判断するようにします。
ノードの型が「~へのポインタ」型である場合は、右オペランドの値をsize_of(node->ty->base)倍する必要があるので、減算を行うアセンブリコード"sub rax, rdi"を生成する前に、アセンブリコード" imul rdi, (「~へのポインタ」型のサイズ)"を生成するようにします。
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR179
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/codegen.c#L179
case ND_SUB:
if (node->ty->base)
printf(" imul rdi, %d\n", size_of(node->ty->base));
printf(" sub rax, rdi\n");
break;
gen_lval関数
https://github.com/rui314/chibicc/commit/f5536961e8182951376e320fafe4340c3a8e12b3#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR25
https://github.com/rui314/chibicc/blob/f5536961e8182951376e320fafe4340c3a8e12b3/codegen.c#L25
void gen_lval(Node *node) {
if (node->ty->kind == TY_ARRAY)
error_tok(node->tok, "not an lvalue");
gen_addr(node);
}gen_lval関数は、ノードが持つType構造体が配列型を表現していない場合にのみ、gen_addr関数を呼び出し左辺値を取得するためのアセンブリコードを生成するようにします。
追加・修正されたコンパイラのソースコード(ステップ22、配列の添字を扱えるコンパイラを作成する)
unary関数
https://github.com/rui314/chibicc/commit/c97aa80173b949104eb0a3e376bbf6309ce90d55#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR348
https://github.com/rui314/chibicc/blob/c97aa80173b949104eb0a3e376bbf6309ce90d55/parse.c#L348
// unary = ("+" | "-" | "*" | "&")? unary
// | postfix
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 postfix();
}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);
postfix関数
https://github.com/rui314/chibicc/commit/c97aa80173b949104eb0a3e376bbf6309ce90d55#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR351
https://github.com/rui314/chibicc/blob/c97aa80173b949104eb0a3e376bbf6309ce90d55/parse.c#L351
// postfix = primary ("[" expr "]")*
Node *postfix() {
Node *node = primary();
Token *tok;
while (tok = consume("[")) {
// x[y] is short for *(x+y)
Node *exp = new_binary(ND_ADD, node, expr(), tok);
expect("]");
node = new_unary(ND_DEREF, exp, tok);
}
return node;
}postfix関数は、生成規則 postfix = primary ("[" expr "]")* に基づいて、抽象構文木のノードを生成します。
「"["、expr、"]"」を0回以上
Token *tok;
while (tok = consume("[")) {
// x[y] is short for *(x+y)
Node *exp = new_binary(ND_ADD, node, expr(), tok);
expect("]");
node = new_unary(ND_DEREF, exp, tok);
}
return node;tok = consume("[")が真となる場合 → 現在読み取っているトークンが"["の場合は、以降のトークンの並びが、"配列のインデックスとなるexpr"、"]"となる想定でパースを進めていきます。その際、x[y]を*(x+y)と読み替えて、抽象構文木のノードを生成します。
追加・修正されたコンパイラのソースコード(ステップ20、sizeof演算子を扱えるコンパイラを作成する)
starts_with_reserved関数
https://github.com/rui314/chibicc/commit/30d530831fa2312ed6f2e73520c1525202745d88#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R131
https://github.com/rui314/chibicc/blob/30d530831fa2312ed6f2e73520c1525202745d88/tokenize.c#L131
char *starts_with_reserved(char *p) {
// Keyword
static char *kw[] = {"return", "if", "else", "while", "for", "int", "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", "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に"sizeof"を追加し、"sizeof"をキーワードとして扱えるようにします。
複数文字の記号を取得する(変更なし)
// 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;
NodeKind
https://github.com/rui314/chibicc/commit/30d530831fa2312ed6f2e73520c1525202745d88#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R85
https://github.com/rui314/chibicc/blob/30d530831fa2312ed6f2e73520c1525202745d88/chibicc.h#L85
// 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_SIZEOF, // "sizeof"
ND_BLOCK, // { ... }
ND_FUNCALL, // Function call
ND_EXPR_STMT, // Expression statement
ND_VAR, // Variable
ND_NUM, // Integer
ND_NULL, // Empty statement
} NodeKind;キーワード"sizeof"を表現するノード型ND_SIZEOFを追加します。
primary関数
https://github.com/rui314/chibicc/commit/30d530831fa2312ed6f2e73520c1525202745d88#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR390
https://github.com/rui314/chibicc/blob/30d530831fa2312ed6f2e73520c1525202745d88/parse.c#L390
// primary = "(" expr ")" | "sizeof" unary | ident func-args? | num
Node *primary() {
Token *tok;
if (consume("(")) {
Node *node = expr();
expect(")");
return node;
}
if (tok = consume("sizeof"))
return new_unary(ND_SIZEOF, unary(), 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);
}primary関数は、生成規則 primary = "(" expr ")" | "sizeof" unary | ident func-args? | num に基づいて、抽象構文木のノードを生成します。
"("、expr、")"(変更なし)
if (consume("(")) {
Node *node = expr();
expect(")");
return node;
}
sizeof、unary
if (tok = consume("sizeof"))
return new_unary(ND_SIZEOF, unary(), tok);tok = consume("sizeof")が真となる場合 → 現在着目トークンが"sizeof"の場合は、new_unary関数を呼び出し"sizeof"に対応するノードを生成します。
また、new_unary関数の第二引数にunary関数の戻り値を指定し、unary関数によって生成された抽象構文木のルートノードがsizeof演算子のオペランドに対応する子ノードとなるようにします。
ident、func-argsを0回か1回(変更なし)
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);
}
num(変更なし)
tok = token;
if (tok->kind != TK_NUM)
error_tok(tok, "expected expression");
return new_num(expect_number(), tok);
visit関数
https://github.com/rui314/chibicc/commit/30d530831fa2312ed6f2e73520c1525202745d88#diff-76824d44018db869c0d65b9ae798b19e16fca3176fd792fbc855fe74da032e32R91
https://github.com/rui314/chibicc/blob/30d530831fa2312ed6f2e73520c1525202745d88/type.c#L91
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->base) {
Node *tmp = node->lhs;
node->lhs = node->rhs;
node->rhs = tmp;
}
if (node->rhs->ty->base)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;
case ND_SUB:
if (node->rhs->ty->base)
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:
if (node->lhs->ty->kind == TY_ARRAY)
node->ty = pointer_to(node->lhs->ty->base);
else
node->ty = pointer_to(node->lhs->ty);
return;
case ND_DEREF:
if (!node->lhs->ty->base)
error_tok(node->tok, "invalid pointer dereference");
node->ty = node->lhs->ty->base;
return;
case ND_SIZEOF:
node->kind = ND_NUM;
node->ty = int_type();
node->val = size_of(node->lhs->ty);
node->lhs = NULL;
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、変更なし)
case ND_VAR:
node->ty = node->var->ty;
return;
ノード型に応じて型付け処理を行う(ND_ADD、変更なし)
case ND_ADD:
if (node->rhs->ty->base) {
Node *tmp = node->lhs;
node->lhs = node->rhs;
node->rhs = tmp;
}
if (node->rhs->ty->base)
error_tok(node->tok, "invalid pointer arithmetic operands");
node->ty = node->lhs->ty;
return;
ノード型に応じて型付け処理を行う(ND_SUB、変更なし)
case ND_SUB:
if (node->rhs->ty->base)
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:
if (node->lhs->ty->kind == TY_ARRAY)
node->ty = pointer_to(node->lhs->ty->base);
else
node->ty = pointer_to(node->lhs->ty);
return;
ノード型に応じて型付け処理を行う(ND_DEREF、変更なし)
case ND_DEREF:
if (!node->lhs->ty->base)
error_tok(node->tok, "invalid pointer dereference");
node->ty = node->lhs->ty->base;
return;
ノード型に応じて型付け処理を行う(ND_SIZEOF)
case ND_SIZEOF:
node->kind = ND_NUM;
node->ty = int_type();
node->val = size_of(node->lhs->ty);
node->lhs = NULL;
return;nodeのノード型がND_SIZEOFの場合は、nodeをsizeof演算子の評価値に対応するノードへ変更します。
nodeのノード型をND_NUMに変更し、nodeの持つ型をint型にするためにint_type関数を呼び出します。
nodeの持つ値は、子ノードnode->lhsの持つ型のサイズとなります。
最後に、子ノードへの参照をなくしておきます。
テストコード
https://github.com/rui314/chibicc/commit/30d530831fa2312ed6f2e73520c1525202745d88#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R136
https://github.com/rui314/chibicc/blob/30d530831fa2312ed6f2e73520c1525202745d88/test.sh#L136
#!/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); }'
echo OK
Makefile
https://github.com/rui314/chibicc/blob/30d530831fa2312ed6f2e73520c1525202745d88/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
