Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Goコンパイラをゼロから作ってセルフホスト達成するまで / How I wrote a sel...

DQNEO
October 28, 2019

Goコンパイラをゼロから作ってセルフホスト達成するまで / How I wrote a self hosted Go compiler from scratch

Go Conference Tokyo 2019 Autumnでの発表資料です。

DQNEO

October 28, 2019
Tweet

More Decks by DQNEO

Other Decks in Technology

Transcript

  1. minigoの特徴 • フルスクラッチから作った (世界初?) • Lexer, Parser, CodeGenerator 手書き ◦

    (Lex/YACC/LLVMなどを使っていない) • 標準ライブラリも自作 • GNU Assemblyを吐く (x86-64 Linux専用) • 実装は約1万行
  2. • rebuild.fm 第153回 ◦ https://rebuild.fm/153/ • rui さんが 8cc (Cコンパイラ)

    をつくった話 • めちゃくちゃ面白い きっかけ
  3. 8cc の移植 → Cで再実装 コミット履歴を1個ずつ、 1. テスト追加分を見る (次実装するべき機能を知る) 2. 自力で、そのテストをパスする実装をCで書く

    まれに成功して大歓喜 3. 無理だったら写経 ◦ 元コミットを、自分で理解できる最小のコミットに分割 しながら写経 ◦ 「コミット分割できた」 = 「内容を理解できた」 とみなす これで巨大コミットを攻略できる
  4. 8cc の移植 : C から Go へ • 分割したコミットを C

    → Go に移植 • 労力的には ◦ 「 Cで自力で再実装 / 写経 」が 90% ◦ Go への移植は 10% • これを5ヶ月半継続 • 基本文法はほとんどカバー
  5. 8cc の移植 : CとGoを同時に学ぶ • 比較しながら学べる static char *REGS[] =

    {"rdi", "rsi", "rdx", "rcx", "r8", "r9"}; var REGS = []string{"rdi", "rsi", "rdx","rcx", "r8", "r9"} C Go
  6. 8cc の移植 : CとGoを同時に学ぶ for (;;) { int c =

    get(); if (c == EOF) return; if (c == ' ' || c == '\t') continue; for { c, err := get() if err != nil { return } if c == ' ' || c == '\t' { continue } C Go • 比較しながら学べる
  7. 8cc の移植 : CとGoを同時に学ぶ static Ast *ast_uop(int type, Ctype *ctype,

    Ast *operand) { Ast *r = malloc(sizeof(Ast)); r->type = type; r->ctype = ctype; r->operand = operand; return r; } func ast_uop(typ int, ctype *Ctype, operand *Ast) *Ast { r := &Ast{} r.typ = typ r.ctype = ctype r.operand = operand return r } C Go • 比較しながら学べる
  8. 8cc の移植 : 学んだこと • コンパイラの作り方 ◦ 体で覚えた • C言語が動く仕組み

    • アセンブリの読み書き • C と Go は驚くほど共通点が多い → 同じ方法で Goコンパイラも作れるのでは?
  9. • 代入文は式ではない x = 1 • ++, --も式ではない x++ •

    iotaの挙動 • 識別子解決の仕組み、universe block の役割 • defer の関数呼び出しの引数の扱い コンパイラを書くことで仕様を知る
  10. 自作append func append1(x []byte, elm byte) []byte { var z

    []byte xlen := len(x) zlen := xlen + 1 if cap(x) >= zlen { z = x[:zlen] } else { var newcap int if xlen == 0 { newcap = 1 } else { newcap = xlen * 2 } z = makeSlice(zlen, newcap, 1) for i:=0;i<xlen;i++ { z[i] = x[i] } } z[xlen] = elm return z } 書籍『プログラミング言語Go』の appendのコードを拝借したら動いた
  11. 自作malloc • 静的領域を最初にガバっと確保 • malloc()呼ぶ度に切り取って使う var heap [640485760]byte var heapTail

    *int func malloc(size int) *int { if heapTail+ size > len(heap) + heap { panic("malloc failed") } r := heapTail heapTail += size return r }
  12. 自作interface • convert時にオリジナル型を文字列化してメモリに保存 ◦ 例: “*G_NAMED(main.Token)” • type switch /

    type assertion 時に取り出して文字列比較 • メソッド呼び出しは、内部的にメソッドテーブルからmap get
  13. おもしろバグ: panic • なんか第2世代コンパイラが暴走する... ◦ panic() で止まってないっぽい • func panic

    の中身が空だった • func panic を実装した ◦ Segmentation Fault ◦ バグってる... ◦ panic() で落ちる... ◦ ん? それでいいのでは  → 放置
  14. case TMAP: // implemented as pointer w = int64(Widthptr) 「

    map のサイズは pointer のサイズと同じ 」 わかる〜〜 そうだよね〜〜 (自分のと同じ) 本家Go: mapのサイズ
  15. 本家Go: stringの実体 「 ポインタと文字列長の組 」 そうだったのか〜〜 (自分のとちょっと違う) // note this

    is the runtime representation // of the compilers strings. // // typedef struct // { // uchar array[8]; // pointer to data // uchar nel[4]; // number of elements // } String; var sizeof_String int // runtime sizeof(String)
  16. 本家Go: sliceの実体 // note this is the runtime representation //

    of the compilers arrays. // // typedef struct // { // uchar array[8]; // pointer to data // uchar nel[4]; // number of elements // uchar cap[4]; // allocated number of elements // } Array; var array_array int // runtime offsetof(Array,array) - same for String var array_nel int // runtime offsetof(Array,nel) - same for String var array_cap int // runtime offsetof(Array,cap) var sizeof_Array int // runtime sizeof(Array) slice のことを array と呼んでいる? 命名が紛らわしいのでは? (歴史的事情?)
  17. アセンブリの学びかた • ググる • Qiitaの記事 • 8cc/gcc に簡単なCのコードを食わせて、アセンブリ出力 を読む •

    慣れてきたら公式マニュアル (GAS, Intel CPU) • 本は読んでない ◦ 自分に合うもの (X86-64 かつ GAS かつ Linux) が なかった
  18. minigo func sum(a int, b int) int { return a

    + b } main.sum: push %rbp mov %rsp, %rbp push %rdi push %rsi mov -8(%rbp), %rax push %rax mov -16(%rbp), %rax mov %rax, %rcx pop %rax add %rcx, %rax leave ret ソースコード GNU assembler
  19. 8cc int sum(int a, int b) { return a +

    b; } sum: push %rbp mov %rsp, %rbp push %rdi push %rsi mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret C言語 GNU assembler
  20. 本家Go func sum(a int, b int) int { return a

    + b } TEXT sum(SB), $0-24 MOVQ b+16(FP), AX MOVQ a+8(FP), CX ADDQ CX, AX MOVQ AX, 24(FP) RET ソースコード Plan9 assembler