マジでちいさいセルフホストコンパイラがほしい

リポジトリ：https://github.com/sozysozbot/2kmcc

hsjoihs「C コンパイラ自作においてセルフホスト達成はかなり分かりやすいマイルストーン」

hsjoihs「セルフホスト、たとえば構造体がほしくなるので構造体を実装するモチベができる」

hsjoihs「しかしながら、このゴールポストは、C で C コンパイラを書かない限り達成できない」

hsjoihs「そうだ、マジで小さい『セルフホストコンパイラ』を C で書いて、『それをコンパイルできたらすごい』にしよう！！！！」

hiromi_mi さんの hanando-fukui v1.1.1 が単一 .c で 2200 行、.h に 169 行

hsjoihs「@hiromi_mi hanando-fukui ってどんな機能があります？」

hiromi_mi「可変長引数の関数を定義できない。NULLの扱いが規格違反なはず」

hsjoihs「まあそれぐらいはよくあるのでは」

hiromi_mi「あとソースファイルが単一。行数削減の効果は実際あったと思うし、それを狙ってあえて単一ソースファイルにした記憶がある」

hiromi_mi「三項演算子がない」

メトリック

• 行数が一番わかりやすい
• 行数は hack しやすい指標なので競技に向きづらいが、まあそこは紳士協定で、可読性を下げる効果しかないタイプの構文上の小手先のテクで行数を減らすのはナシということで（「フォーマッタ強制して測る」はまあ解決策の一つだけど、とはいえ）

デザイン

• 「実装に使う機能」を削りたい
• typedef はなくても困らない
• 型チェックはしなくてもよい
• 単一ファイルにすれば #include "main.h" も要らない。プリプロセッサ無しを狙う
• enum を削りつつ可読性を発生させるには、トークン名として文字リテラルそのものを用いるという手がある。 case '+': みたいに。
• これで困るのは二文字トークン

• 二文字トークンを使わない、は避けたい。全てに i = i + 1 とか if (!(a - b)) とか書いてまわるのは嫌だ
• 嫌だけど……できちゃいそうだなぁ
• 二文字トークンは '+' * 256 + '=' ってエンコードする手がある
• でも、case '+' * 256 + '=':って書くと定数畳み込みを実装する必要がある
• そもそも switch-case を排し、if (tok.id == '+' * 256 + '=') で全て書けば解決

• 逆に「これ削ったらもはや C コンパイラじゃないだろ」は？

• ポインタ
• 配列、配列の配列
• struct
• 文字列リテラル

2023/01/28

hiromi_mi「@ushitora_anqu に尋ねたところ、https://github.com/jserv/amacc が出てきた。セルフホストと主張はしている. Armでありすぐには試せないけれど......」

hiromi_mi「みました. ここのコミットで (単純行数) 1719行でArm ELF ファイルを出力するセルフホストCコンパイラになっていると主張している。いまパッと qemu-user-arm 用意できないので確認するのは今度.」

hiromi_mi「
実装状況：

• syntax error などのエラー処理はほとんどされていない
• struct, enumは実装されていそう. 複合代入演算子, typedef, NULLがない.

削減ポイント：

• tokenとclass (node?) として同じenumを使い回している
• gen() においてoperandを直接書いている *je++ = 0xe59000000;

• ELFを自前で出力してる. 比較できないが、行数という意味では増えてると思う

• 構文解析部分がad-hoc (まだ読めていない.) stmt() と next() 関数の2関数のみで、ほとんどをswitchで処理している

• これが大きい

// tokens and classes (operators last and in precedence order)

enum {

    Num = 128, Fun, Sys, Glo, Loc, Id,

    Break, Case, Char, Default, Else, Enum, If, Int, Return, Sizeof,

    Struct, Switch, For, While,

    Assign, Cond,

    Lor, Lan, Or, Xor, And,

    Eq, Ne, Lt, Gt, Le, Ge,

    Shl, Shr, Add, Sub, Mul, Inc, Dec, Dot, Arrow, Brak

};

// opcodes

enum {

    LEA ,IMM ,JMP ,JSR ,BZ  ,BNZ ,ENT ,ADJ ,LEV ,LI  ,LC  ,SI  ,SC  ,PSH ,

    OR  ,XOR ,AND ,EQ  ,NE  ,LT  ,GT  ,LE  ,GE  ,SHL ,SHR ,ADD ,SUB ,MUL ,

    OPEN,READ,WRIT,CLOS,PRTF,MALC,MSET,MCMP,MCPY,MMAP,DSYM,BSCH,CLCA,EXIT

};

構文解析部分、相当ad-hocなことしてるように見えるが、すぐには読み解けない」

hsjoihs「こっちのレギュレーションに legible 入れておいてよかったな」

hiromi_mi「本当にその通り」

2023/01/28

2kmcc という名前を付けた

2023/01/31

2kmcc は 2k-line mundane C compiler ということにした

hsjoihs「2k-line mundane C compiler: a self-hosting toy C compiler that's so mundane, your puny C compiler can compile me

にしようと思います（押し出すポイントはそこなので）」

hsjoihs「なので、コンパイラ数珠つなぎでコンパイラを列挙しまくったのが効いてきて、『このコンパイラも私をコンパイルできる！』ってのをズラッと列挙する形になる」

2023/01/31

「ステップ22: 配列の添字を実装する」まで実装したタイミングで、行数はこんな感じ

最初の怒涛のリファクタリングで減らしたおかげでかなりなんとかなっている

これは sub 2k いけるかもしれん

実装量としては、switch - case も enum も要らないのが特にうれしい

2023/02/01

れもん「はすじょいさんの最近やってるCコンパイラのログ見てて、amaccの構文解析部分を覗いたのですがexprがlevelを引数として取ってて1関数であるところを見るにprattパーサーですね。それでいて演算子の順序付けが必要なんですがそれをどうもenumの順序でやってるっぽくかしこい」

hsjoihs「

はいステップ 27 終わり（ステップ 28 の「テスト C 化」は意図的にやらない。）

ステップ 26 は「複数行入力に対するまともなエラーメッセージ」だけ実装するつもり。2kmcc、コードゴルフの産物ではなくて「普通に使い物になる toy c compiler」を目指したいので、行数が許す限りまともなエラーメッセージ出したいのよね

」

2023/02/02

行数を過激に削った。

        } else if (strchr(";(){},[]", c)) {

            tokens_start[token_index].kind = c;

            token_index += 1;

            i += 1;

        } else if (strchr("+-*/&><=!", c)) {

            i += 1;

            if (str[i] == '=') {

                i += 1;

                tokens_start[token_index].kind = enum2(c, '=');

                token_index += 1;

            } else if (str[i] == c && !strchr("*!", c)) {

                panic("++, --, &&, >>, <<, >>=, <<= not supported");

            } else {

                tokens_start[token_index].kind = c;

                token_index += 1;

            }

とかいうだいぶ過激な実装。あと、ソースコードから ++, --, || を削ったが、このうち ++ は実装した方が行数が減る（tokens_start[token_index++].kind = c; みたいな書き方ができるようになるため）気がする。

現在 1159 行。なんと！まだ 841 行も書いていいというのか

2kmcc 行数

その後、複合代入演算子・後置デクリメント・トークナイザの全演算子への対応などをやった結果、現在 1136 行。これはわりと行けそうだな。

現状足らん：

• エスケープシーケンス
• トークン列を読み込む配列の長さチェックとか
• struct
• void
• for(int i = 0; ...)
• 変数を定義して即代入（ローカルのみ）
• ポインタの 0 との比較
• 否定演算子
• &&
• sizeof(型)
• const

あれ、こんなもんか？こんなもんか。複合初期化子は意図的に避けてきたし、typedef はすぐ消せるし。これ以上制御構文とか要らないのが地味にうれしいな。

実は void * も一ヶ所でしか使ってないんだよな。これ void も削れるな。削るか。

えーと void を返している関数は 16 個。

/home/hsjoihs/c-compilers/2kmcc/main.c

  73,1: void panic(const char *msg) {

  264,1: void consume_otherwise_panic(int kind) {

  271,1: void expect_otherwise_panic(int kind) {

  278,1: void panic_if_eof() {

  379,1: void display_type(Type *t) {

  390,1: void assert_same_type(Type *t1, Type *t2) {

  403,1: void assert_compatible_type(Type *t1, Type *t2) {

  760,1: void store_func_decl(NameAndType *rettype_and_funcname) {

  767,1: void parseToplevel() {

  875,1: void EvaluateExprIntoRax(Expr *expr);

  877,1: void EvaluateLValueAddressIntoRax(Expr *expr) {

  896,1: void CodegenStmt(Stmt *stmt) {

  955,1: void CodegenFunc(FuncDef *funcdef) {

  977,1: void deref_rax(int sz) {

  991,1: void write_rax_to_where_rdi_points(int sz) {

  1018,1: void EvaluateExprIntoRax(Expr *expr) {

んー、早すぎる最適化は諸悪の根源。今日はここらへんで切り上げよう

2023/02/04

まあとりあえず sizeof(int **) でも実装するか。

そうしたら…まあ int i = 0; かなぁ。

じゃあその後は for(int i = 0; ...) {} ですわな。これは { int i=0; for(; ...) {} } へとコンパイルすれば正しいはず。ところで、セルフホストまでにスコープチェーンを真面目に実装するか怪しいな。

現状足らん：

• エスケープシーケンス
• トークン列を読み込む配列の長さチェックとか
• struct
• void
• ポインタの 0
• ポインタの 0 との比較
• 否定演算子
• &&
• const
• スコープチェーン
• 関数宣言
• 文字リテラル

とはいえ、スコープチェーンがない環境でコードはあんまり書きたくないので、実装したほうがいいんだろうな。

関数宣言は簡単だしサクッと足しちゃおう。あ、宣言自体は store_func_decl で既に蓄えてるから、セミコロンを見たらすり替えるとすればいいのか。

            if (maybe_consume(';'))

                return;

を足すだけでよい。

さ～て、次はヌルポインタ定数・否定演算子・&& かなぁ。まあ要は boolean context で式を評価する話が必要なわけですね。

とりあえずヌルポインタ定数を実装し、比較演算子や代入演算子、初期化子に 0 が来たときの型チェックを緩めた。

そうすれば、今度は The expression !E is equivalent to (0==E) とあるのでそれを定義するだけ。えっなんでコケるの。

理解。ヌルポインタを代入するところが mov [rdi], eax になってしまっている。

理解。== じゃなくて != を書いてる。

（ということでここで一旦 push）

現状足らん：

• エスケープシーケンス
• トークン列を読み込む配列の長さチェックとか
• struct
• void
• &&
• const
• スコープチェーン
• 文字リテラル

文字リテラルをサッサと足してしまおう。エスケープシーケンス付きで足した。

文字列の方もエスケープシーケンスに対応しようかな。実はこっちはアセンブラに任せることにより手間が減るのよね。

現状足らん：

• トークン列を読み込む配列の長さチェックとか
• struct
• void
• &&
• const
• スコープチェーン

&& ぐらい作れるだろ。作るか。

現状足らん：

• トークン列を読み込む配列の長さチェックとか
• struct
• void
• const
• スコープチェーン
• break

さて、あとは struct なんだけど、先に pratt パーサーにして行数が減るかの実験をした方がよさそうだな。

さーて struct やるかぁ。int main() { return sizeof(struct A*); } と int main() { struct A *p; return 0; } は一瞬で実装できる。そしたら次は struct A { int a; }; だな。先に Map<構造体名, Map<変数名, (オフセット, 型)>> を作る必要がある。

あ、待てよ、

typedef struct StructMember {

    char *struct_name;

    char *member_name;

    int member_offset;

    Type *member_type;

} StructMember;

をフラットに格納すれば一応機能は果たせるな。えーと parseToplevel に足せばいいのか

パースはできた。ということでオフセットを計算するためにアラインメントが必要。

2023/02/05

struct A { char a[5]; int b; }; int main() { return sizeof(struct A); }

ができた。さてメンバアクセスが必要ですね。

&p->a が p + offsetof(typeof(*p), a) なんだよな。これを p@a と略記すれば、

はい、両方実装。

現状足らん：

• トークン列を読み込む配列の長さチェックとか
• void
• const
• スコープチェーン
• break

ん－。とりあえず typedef の滅ぼしでもやるか。滅ぼした。

break って 3 回しか使ってないのか。滅ぼしたい。滅ぼした。

const は読み飛ばすかぁ。今のところ char の直前にしか来てない。

現状足らん：

• トークン列を読み込む配列の長さチェックとか
• `void`, `void *`, `return;`
• スコープチェーン

スコープチェーンってどうなってたっけ。実は関数スコープさえあれば一応耐えるという気持ちはある。関数スコープは普通にある。しかし関数内で for 文の添え字をいちいち変える必要に迫られるのは嫌である。

あー、ネストしてなければ一応現状でも動くのか。スコープが重なってさえいなければ動く。でもなぁ。んー。

とりあえず、どこまで準拠しているかをわかりやすくすべく、現状のテストを分割していくか。

• correctly_accepts
• correctly_rejects
• miscompiles
• incorrectly_accepts
• incorrectly_rejects

の 5 つだな。

2023/02/07

n.takana (@_Alignof) さんを誘った。

takana — 今日 18:25

ログとコードを読んだのですが，頑張りにより本当にコードが小さくなっておりすごい

takana — 今日 18:27

そしてコード読みに夢中になっていて忘れていたがこっちは面白そうなのでやってみたい感があります

hsjoihs — 今日 18:29

やったぁ。2kmcc、「数珠繋ぎの対象にしやすい」ってのを目標にしているので、人海戦術で「このコンパイラでも 2kmcc を正しくコンパイルできる！」を調べ、その一覧をズラーッと README に並べる、みたいなことやりたいんですよね

あと、未達の目標として「compilerbook 流の、行番号と位置が出るエラーメッセージ」があって、これでちょっとは行数かさみそうだなと思ってます

2023/02/09

とりあえず `void`, `void *`, `return;` をやるかぁ。

decode_kind を試そうとしたらミスコンパイルする

int enum3(int a, int b, int c) {

    return enum2(a, enum2(b, c));

}

が破滅していそう。

.globl enum3

enum3:

  push rbp

  mov rbp, rsp

  sub rsp, 48

  mov [rbp - 8], rdi

  mov [rbp - 16], rsi

  mov [rbp - 56], rdx

は？なぜ rbp - 56 を読んでいる？

はい～関数定義ごとに変数スコープを切り分けていないっぽい。LVar のテーブルをクリアし忘れている。データ構造変えるか？いや、これは別ステップにすべきだろう。先に void と return; を組みます

組んだので、ミスコンパイルを直していこう。

まず、locals が唯一の連結リスト（name と offset_from_rbp を持つ）としてあって、こいつはヌル初期化されていて、findLVar でそれが走査される。insertLVar で挿入をしている。

あ、そもそもこの連結リストってコードジェネレートのときにしか触ってないのか。じゃあ CodegenFunc の冒頭で locals をクリアするだけで直る？直ったわ。

まあとはいえ、変数のブロックスコープを発生させることに成功していないので、そこはなんとかしてもいいかもな。でもめんどいし、後回しかなぁ。

テストケース、compilerbook をもとにするというのを考えた。あーでも int main(int argc, char **argv) を扱うためにはコマンドライン引数の処理が必要だな。ん？違う、今回はスタートアップは gcc 側が提供してくれているんだった。

さて step 2 で落ちる！ mov rax, 1398145024 とか吐いてるし、バグってそう。

んー、以下のコードが mov rax, 128042 を返してくるな。

int printf();

int isDigit(char c);

void *calloc();

int parseInt(char *str) {

    int result = 0;

    while (isDigit(*str)) {

        int digit = *str - '0';

        result = result * 10 + digit;

        str++;

    }

    return result;

}

int intLength(char *str) {

    int length = 0;

    while (isDigit(*str)) {

        length++;

        str++;

    }

    return length;

}

int isDigit(char c) {

    return '0' <= c && c <= '9';

}

int main() {

    char *p = calloc(3, 1);

    p[0] = '0';

    p[1] = 0;

    printf(".intel_syntax noprefix\\n");

    printf(".globl main\\n");

    printf("main:\\n");

    int parsednum_ = parseInt(p);

    int parsedlength_ = intLength(p);

    p += parsedlength_;

    printf("  mov rax, %d\\n", parsednum_);

    while (*p) {

        if (*p == '+') {

            p++;

            int parsednum = parseInt(p);

            int parsedlength = intLength(p);

            p += parsedlength;

            printf("  add rax, %d\\n", parsednum);

        } else if (*p == '-') {

            p++;

            int parsednum2 = parseInt(p);

            int parsedlength2 = intLength(p);

            p += parsedlength2;

            printf("  sub rax, %d\\n", parsednum2);

        } else {

            return 2;

        }

    }

    printf("  ret\\n");

    return 0;

}

いろいろ試し、解決。char の上位 56 ビットクリア忘れか～

次。ステップ 3。あー構造体の配列をグローバルに宣言する構文に対応していない。

ステップ 6 まで動いた。

2023/02/10

文字列の中で \0 を使っているので、それに対処。

さーて、parse error: expected TokenKind `IDNT`; got TokenKind `)` と言われたが、流石にどこか分からんし、エラー位置を表示する仕組みがないとやってらんないな。

ということで compilerbook の error_at を足す。トークンに位置フィールド足さなきゃいかん。

あー、プロトタイプ宣言の struct Expr *parseMultiplicative(void); で落ちてる。まあこれはサポートしてやってもいいんだよな。

引数型チェックぐらいはあってもいいんだよなぁ～

そういや前置インクリメントないんだった。これぐらいはあってもいいんだよな。あと || を作ってないやつ。

それはそれとして、step 18 を走らせてみると…… int three() { return 3; } int main() { return three(); } がコンパイルできない（無が出力される）。

gdb --args tmp_2kmcc_stepn "int three(){return 3;} int main(){return three();}" 

をやると、

.intel_syntax noprefix

.globl three

three:

  push rbp

  mov rbp, rsp

  sub rsp, 208

  mov rax, 1

  mov rax, 3

  mov rsp, rbp

  pop rbp

  ret

.globl main

main:

  push rbp

  mov rbp, rsp

  sub rsp, 208

  mov rax, 1

Program received signal SIGSEGV, Segmentation fault.

と言われる。

(gdb) bt

#0  0x000000000044c1c7 in __strlen_avx2 ()

#1  0x000000000041bd05 in __vfprintf_internal ()

#2  0x00000000004168fc in printf ()

#3  0x00000000004071af in EvaluateExprIntoRax ()

#4  0x0000000000406611 in CodegenStmt ()

#5  0x000000000040658a in CodegenStmt ()

#6  0x0000000000406f22 in CodegenFunc ()

#7  0x0000000000407ba0 in main ()

よし、分からんので、step18 が吐くアセンブリに手を加えてデバッグしよう。

            printf("#3\\n");

            printf("    pop %s\\n", nth_arg_reg(i));

あ～なんか察した。まあそもそもこういうトリッキーなことをしない方がいいよね。

const char *nth_arg_reg(int n) {

        if (n == 0) {

            return "rdi";

        } else if (n == 1) {

            return "rsi";

        } else if (n == 2) {

            return "rdx";

        } else if (n == 3) {

            return "rcx";

        } else if (n == 4) {

            return "r8";

        } else if (n == 5) {

            return "r9";

        } else {

            exit(1);

        }

}

にしてみよう。

FAIL:check (stepN returned with non-zero):

と言われた。ふむ～？エラーメッセージを吐かせてみよう。
!!!!!!!!!error: incorrect n: -1

おやおや。

あ～ 符号をまたぐ比較とか 64 bit vs. 32 bit とかでバグってるパターンか？そんな気がしてきた。それにより

        for (int i = expr->func_arg_len - 1; i >= 0; i--) {

            printf("#3\\n");

            printf("    pop %s\\n", nth_arg_reg(i));

        }

に悪影響が出ているのだろう。たぶん。

ということでテスト。

int printf();

int main() {

    for (int i = 0 - 1; i >= 0; i--) {

        printf("%d", i);

    }

    return 0;

}

はい～無限ループする。出力されているアセンブリは？

.intel_syntax noprefix

  .text

  .section .rodata

.LC0:

  .string "%d"

  .text

.text

.globl main

main:

  push rbp

  mov rbp, rsp

  sub rsp, 8

# inserting a variable named `i` at offset 8

  mov rax, 1

  lea rax, [rbp - 8] # rax = &i

  push rax

  mov rax, 0

  push rax

  mov rax, 1

  mov rdi, rax

  pop rax

  sub rax,rdi

  pop rdi

  mov [rdi], eax

  mov rax, 42

.Lbegin0:

  lea rax, [rbp - 8] # rax = &i

  mov eax,[rax]

  push rax

  mov rax, 0

  mov rdi, rax

  pop rax

  cmp rax, rdi

  setge al

  movzb rax, al

  cmp rax, 0

  je  .Lend0

  mov rax, 42

  mov eax, OFFSET FLAT:.LC0

  push rax

  lea rax, [rbp - 8] # rax = &i

  mov eax,[rax]

  push rax

  pop rsi

  pop rdi

  mov rax, 0

  call printf

  mov rax, 1

  push rax

  lea rax, [rbp - 8] # rax = &i

  mov rsi, rax

  mov rax, [rax]

  pop rdi

  sub rax,rdi

  mov rdi, rsi

  mov [rdi], eax

  push rax

  mov rax, 1

  mov rdi, rax

  pop rax

  add rax,rdi

  jmp  .Lbegin0

.Lend0:

  mov rax, 0

  mov rsp, rbp

  pop rbp

  ret

  mov rax, 42

  mov rsp, rbp

  pop rbp

  ret

とりあえず比較を 4 byte でするように直した。さてこれでどうだろう。動いた。

もういきなり step 44 とか動かせるんじゃないかという気がしてきたが、さすがに楽観的すぎか。まあでもやってみるか。あーでも、テストケースが増えてからのはめんどいから、テストケースを増やす直前、typedef と break をソースコードから排して const を無視するようにした a1866e2cd5c4580188558a39ed267ff06e6342a1 を試してみるか。

えーと空文はない。

あーあと || がない。 || を避ける理由はマジでないのでサクッと組んでしまおう。組んだ。

2023/02/13

さて、最後に残ったものとして stderr があるんだよな。こいつも滅ぼす設計にしようかなと思っている。つまり、コンパイルエラーも出力ファイルに出すという方針。

とりあえずエラーメッセージの列挙でもするか？

fprintf(stderr, "cannot find a function named `%s`. Implicitly assumes that it return an int\n", name);

は exit してないやつなんだよな。まあこれはコメントアウトかなぁ。

panic_two_types って使ってたっけ。後回し

2023/02/18

さ～てやっていくか。えーと前回は panic_two_types まで見たのか。そして予想通りこれ 1 回しか使ってないね。panic_invalid_binary_operand_types(e1, e2, op_kind); で代用できるね。削ろう

エラーメッセージを全部確認し、必要に応じて文言を直した。コード生成の際のエラーメッセージは（残りの実装にバグがない限り）発生させることができないはずなので、Internal compiler error と書くことにした。

さて、stderr を滅ぼしたのはいいんだが、問題はテストスクリプトを変えねばならないこと。

テストスクリプトも変えた。

はい～～セルフホスト成功。

hsjoihs-c-compiler の大量のテストケースも導入。これで「なにに対応できていないのか」がかなり分かりやすくなった。