ギークもどきの日記帳

雑多な知識が垂れ流される場所。ほとんど無害。

セキュリティ・キャンプ全国大会2019でCコンパイラ書きました

はじめに

2019年8月13日から5日間開催されたセキュリティ・キャンプ全国大会2019のCコンパイラ自作ゼミに参加しました。 この記事は、応募から修了までのレポートです。 ほとんど下書き状態ですが、ここから文章が改善される気がしないのでこのまま公開します。

セキュキャンでの進捗

3ヶ月ぐらいゴリゴリコードを書いて、セルフホストCコンパイラを実装した。switch-case文や#ifdef、可変長引数とかも実装している。 リポジトリは↓

github.com

これまでの星にゃーん

一昨年は言語自作ゼミ、去年はCコンパイラゼミに応募するも通らなかった。3度目の応募で合格。参加者の中では応募回数トップタイらしい。

今年の経緯

しばらく前から精神がオワってしまいひきこもり生活を送っている。ひきこもりながらもGHCのコードリーディングや自作コンパイラ開発をやっていたがスランプに陥る。 リハビリのために何かをやろうと考え、周りを見渡すと全人類Cコンパイラ書いとる。あ、書けるんだ、と思ったので書き始めた。 低レイヤを知りたい人のためのCコンパイラ作成入門https://github.com/rui314/9ccを読んで勘が掴めたので手を動かすことに。

hikaliumさんに1分でリツイートされ後がなくなる星にゃーん.jpg

うかつな発言によりCコンパイラセルフホストRTAが始まってしまった。それっぽいものは簡単に書け、1週間でif文とかが動いた。3日でセルフホストはさすがに無理。再走者求む。

せっかくなので今年もCコンパイラ自作ゼミに応募してみることにした。体力面の不安が大きかったが、どうせ家に居ても死んでるので変わらないと判断。 通った。びっくり。通ったので元気が出た。単純ですね。

事前学習ではCコンパイラを書いた。週1でruiさんとhikaliumさんとのオンラインミーティングが設定された。参考になる資料や歴史の話が盛りだくさんで面白い話を毎回できた。コーディング自体はそんなに詰まることなくスムーズに進んだ。『低レベルプログラミング』と『BINARY HACKS』の知識がかなり役立った。コンパイラの開発自体はやったことがあるのも功を奏した。それでもバグりまくって常にウンウン唸ってましたが…

実装の話

3日でセルフホストと言ったので出来るだけ早くセルフホストしたい。しかし24時間ぶっ続けで書き続ける元気はないので、出来るだけ実装をサボることにした。よくあるコードを正しく解釈できればよいとして、コーナーケースへの対応は必要ない限り行わなかった。unsignedな値すらサポートしていない。意外とunsignedとsignedの区別を付けるのが面倒。

コード量が大きくなることは目に見えていたので、あえてあまり抽象化せず愚直に書くことにした。Cで短く簡潔なコードを書くのは不可能ではないが難しい。 愚直に書くといっても冗長に書くことは避けた。何事もバランスが大事。それなりに綺麗なコードが書けたんじゃないかと思う。

スタックのアライメントがバグりにバグりまくった。バグを直したと思っても数日後にまたバグが見つかる、みたいなのを繰り返した。アラインするコードがバグってるのでxmmレジスタが絡むとセグフォするが、浮動小数点数コンパイラではほとんど使わないのでなかなかバグが発覚しない。根本の原因は剰余演算を算数レベルで勘違いしていたことだった。わり算むずかしすぎる。 スタックのサイズをコード生成時にグローバル変数で管理するようにしていたがこれもバグの温床だったので、最終的に下記のアルゴリズムで実行時にアラインすることで解決した。

int roundup(int x, int round_to) {
  return (x + round_to - 1) & ~(round_to - 1);
}

トークンに位置情報を持たせてエラー出力をいい感じにした。該当コードはこのあたり。 エラー出力は下記のような見た目になる。モダンっぽい雰囲気がする良いエラー出力。

$ ./hoc examples/parse_error.c
error at (1, 11)

int main( {
          ^

) expected

これはruiさんに教えてもらった中でも特に印象的なコード。しかしincludeを実装したあたりでエラー出力がセグフォするように。includeしたファイルでソースコード文字列を指すポインタが書き換わってるのが原因だった。 #includeを使うとprint_lineが正しく動作しなくなるバグを修正 · takoeight0821/hoc_nyan@c1390ae · GitHub

バグ、特にセグフォ周りのバグはセグフォとは関係ない(スタックトレース上に現れない)コードが直接の原因であることが多かった。GDBで落ちてる箇所の検討をつけた後、関連するコードでprintfデバッグをしまくった。watchpointとかをうまく使えばもっと楽になると思う。 GDBgdb-pedaが役立った。Day2に他の人が使ってるのを見て存在を思い出しインストールした。自作コンパイラのバグはスタックの異常として現れることが多かったので、スタックを自動でダンプしてくれるのが便利。もっとはやく存在を思い出したかった…

アセンブリにコメントで情報(コード生成時のノードとか)を埋め込んでおくとエスパーの助けになる。stderrへのデバッグ出力がコメントになるようにしておいて、stdoutにアセンブリを吐いて合わせて眺めると埋め込むより楽そう。早い段階で .loc を出力しておくようにするのも良いかもしれない。

セルフホストを達成した時のコミットは for(;;) への対応( 継続条件が空のforが実行されないことがあるバグを修正 · takoeight0821/hoc_nyan@83f1db0 · GitHub)。 条件が空の時に不正な値を読んでた。

GASのintel syntaxだと、 ltand のような名前をラベル名に使えないらしい。 invalid use of operatror lt のようなエラーメッセージが出る。 とりあえずソースコード内の ltand とかを別の名前にリネームして問題を回避した。時間ができたらこのあたりを再度調べてまとめておきたい。

異常系テストは大事だと再認識した。「このファイルはパースに失敗する」みたいなのがちゃんと失敗することを確かめておくと、いろんなバグを早期発見できる。上に書いた #include のバグもパースエラー出力のテストで発覚した。

まとめ

同じような興味と高いスキルを持つ人たちに囲まれて、一つのタスクにひたすら取り組み続ける機会は学生のうちはなかなか得難い。 なかなかタフな5日間だったが、気分はかなり爽快で良いリフレッシュになったと感じている。 実装力に自信がついたし、普段の日常会話で相当なストレスを溜めていることを自覚することもできた。 人生が変わったとまでは言えないが、間違いなく良い影響を受けたと思う。

セキュキャン期間中は6時起床24時就寝、3食毎日食べる規則正しい生活を送っていた。 しかし家に帰った翌日は16時まで寝ていた。無事生活習慣が元に戻りました。この話はこれでオワリです。

Homebrewで他のformulaから依存されていないformulaを列挙する

brew listでインストール済みのすべてのformulaを列挙する。 xargs -P ...でそれぞれのformulaについて、そのformulaに依存しているインストール済みのformulaの数を数える。 grep " 0"で依存されていないformulaのみを取得する。

$ brew list | xargs -P 10 -IPACKAGE sh -c "brew uses --installed PACKAGE | wc -l | xargs echo PACKAGE" | grep " 0"

参考リンク:

Coq 8.7.1でSoftware Foundationsを読もうとしてハマったメモ

Software FoundationsのProgramming Language FoundationsのEquiv.vをProof Generalで読み込んだら以下のようなエラーが出た。

Error:
The file /Users/yuya/dev/src/local/softwarefoundations/plf/Maps.vo contains library
Top.Maps and not library Maps

以下のような内容の_CoqProjectというファイルを作成すると上手く読み込めた。

-R "." Top

Coqの物理パスと論理パスの扱いに絡む問題っぽい。

プログラミング言語をつくっている

去年の夏頃からプログラミング言語を作っています。

こんな感じのソースコードから

let
  extern print_int : Int -> Unit = "print_int"
  extern newline : Unit -> Unit = "newline"
  fun fib(n : Int) : Int =
    if n <= 1
    then 1
    else fib(n - 1) + fib(n - 2)
  fun fib_loop(n : Int) : Unit =
    let val unused:Int = fib(30)
    in if n <= 0
       then print_int(fib(0));
            newline()
       else print_int(fib(n));
            newline();
            fib_loop(n - 1)
    end
in
  fib_loop(30)
end

こんな感じのllvm irが吐かれて、

; ModuleID = 'examples/fib.mlg'


declare external ccc i8* @GC_malloc(i64)

declare external ccc {} @newline({}, i8*)

declare external ccc {} @print_int(i32, i8*)

define external ccc {} @"fib_loop.4:(Int -> {})"(i32 %n.5, i8* %captures){
; <label>:0:
  %"unused.6:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 30, i8* undef)
  %"$k.16:Bool" = icmp sle i32 %n.5, 0
  %resultptr = alloca {}
  br i1 %"$k.16:Bool", label %then, label %else
then:
  %"$k.19:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 0, i8* undef)
  %"$_.18:{}" = call ccc {} @print_int(i32 %"$k.19:Int", i8* undef)
  %valdec = call ccc {} @newline({} undef, i8* undef)
  store {} %valdec, {}* %resultptr
  br label %end
else:
  %"$k.23:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %n.5, i8* undef)
  %"$_.22:{}" = call ccc {} @print_int(i32 %"$k.23:Int", i8* undef)
  %"$_.24:{}" = call ccc {} @newline({} undef, i8* undef)
  %"$k.26:Int" = sub i32 %n.5, 1
  %valdec1 = call ccc {} @"fib_loop.4:(Int -> {})"(i32 %"$k.26:Int", i8* undef)
  store {} %valdec1, {}* %resultptr
  br label %end
end:
  %valdec2 = load {}, {}* %resultptr
  ret {} %valdec2
}

define external ccc i32 @"fib.2:(Int -> Int)"(i32 %n.3, i8* %captures){
; <label>:0:
  %"$k.7:Bool" = icmp sle i32 %n.3, 1
  %resultptr = alloca i32
  br i1 %"$k.7:Bool", label %then, label %else
then:
  store i32 1, i32* %resultptr
  br label %end
else:
  %"$k.10:Int" = sub i32 %n.3, 1
  %"$k.9:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %"$k.10:Int", i8* undef)
  %"$k.13:Int" = sub i32 %n.3, 2
  %"$k.12:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %"$k.13:Int", i8* undef)
  %valdec = add i32 %"$k.9:Int", %"$k.12:Int"
  store i32 %valdec, i32* %resultptr
  br label %end
end:
  %valdec1 = load i32, i32* %resultptr
  ret i32 %valdec1
}

define external ccc i32 @main(){
  %main = call ccc {} @"fib_loop.4:(Int -> {})"(i32 30, i8* undef)
  ret i32 0
}

llvmの最適化をかけたりなんだりゴニョゴニョすると実行可能ファイルができます。

詳しくはREADMEを読んで下さい。Githubで公開しています。

github.com

Malgoの話

Malgoはコンパイラの動作について学習するために作っている俺言語です。 文法はSMLベース(というか虎本のTigerベース)で、タプルや無名関数リテラルがあります。 言語的にはいわゆる単純型付きラムダ計算のシンプルな実装で、多相型もコレクションもまだ無いので自明でないことをするにはちょっとコツが要ります。

Haskellの話

実装にはHaskellを使いました。 選考理由は

  1. ASTとか扱うのに代数的データ型があると嬉しい
  2. 良い感じのllvmバインディングがある(https://github.com/llvm-hs/llvm-hs
  3. stackとかでてきて環境構築が楽になった
  4. 慣れてる

ぐらいです。OCamlとどっち使うか長いこと悩みましたが、これは個人的には自転車置き場の議論だったのでエイヤッで決めました。

Preludeがつらい問題

Haskellのよく知られた問題としてPreludeが辛いというか惜しいというのがあります。 例えば

  • mapの型がFunctor f => (a -> b) -> f a -> f bではなく(a -> b) -> [a] -> [b]
  • lookupのようなよくある関数がアドホック多相になっていなくてMap.lookupなどと書かないといけない
  • デフォルトの文字列型が[Char]

実用上はゴニョれば良いのであんまり問題ないですが、この問題を解決しようと色々なオレオレPrelude*1が作成されていたりします。

malgoの実装では、試しにprotolude*2を使ってみました。 これはオレオレPreludeを作るためのライブラリとして作られているようです。 malgoの実装では、protoludeをベースに、プロジェクトに依存しないユーティリティをまとめてLanguage.Malgo.Preludeモジュールを作っています。

例えば、Showのインスタンスをプリティプリンタ代わりのは微妙という話があるのでPrettyPrint型クラスを作ったり、辞書として使える型を表すDict型クラスを作ったりしています。

実装の話

処理の流れとしては

  1. パースする(Lexer.hs, Parser.y
  2. shadowingなどのアレコレを名前解決して、全識別子に連番を振る(Rename.hs
  3. 型検査を行い、識別子に型情報を付加する(TypeCheck.hs
  4. K正規化と脱糖衣を行う(KNormal.hs
  5. もろもろの最適化(まだほとんど未実装)
  6. クロージャ変換(Closure.hs
  7. LLVM IRの生成(CodeGen.hs

とかなりシンプルです。

中間表現は

  • パースでASTとして生成されるSyntax NameSyntax.hs
  • 名前解決で生成されるSyntax ID
  • 型検査で生成されるSyntax TypedID
  • K正規化&脱糖衣で生成されるHIR TypedIDHIR.hs
  • クロージャ変換で生成されるMIR TypedIDMIR.hs

みたいな感じになっています。

今後の話

  • 多相型を実装
  • リスト、配列などのコレクションを実装
  • モジュールシステムを実装

などをやっていき〜みたいな感じです。

Hakyllでブログ作った

こうののブログ - Home

stackにはHakyll用のテンプレートもあるので、ブログ制作そのものは簡単にできる。 Github Pagesの仕様にあわせるため若干のハックが必要だった。 具体的には、記事作成そのものはblogブランチで行い、_site/以下をmasterブランチにコピーしpushするということをしている。 stack exec blog deployでその辺の作業を自動化した。

CのVariable-length array

C99では, 実行時に配列の長さを指定できる機能が追加された.

#include <stdio.h>
int foo(int n) {
  int array[n];
  int array[0] = 1;
  int array[1] = 1;
  for (int i = 2; i < n; i++) {
     array[i] = array[i-1] + array[i-2];
  }
  return array[n-1];
}

sizeofは実行時に計算される.

ただし, C11ではオプション機能に格下げされている. VLAが実装されていない処理系では, __STDC_NO_VLA__というマクロが定義されている.

問題点として, メモリがアロケートされるのがスタックかヒープかが実装依存である点がある. GCCではスタックらしい. また, 巨大なVLAを定義しようとするとプログラムはクラッシュする. ある状況では非常に便利だが, 慎重に扱う必要がある.

ちょっと身内で話題になったので簡単にまとめてみた.

参考URL

詳しくはWebで!

stack ghciでllvm-hs読み込めないときにすること

$ stack ghci
Configuring GHCi with the following ...

lookupSymbol failed in relocateSection (relocate external)
/usr/local/Cellar/llvm-4.0/4.0.0/lib/llvm-4.0/lib/libLLVMLTO.a: unknown symbol `__ZN4llvm3lto11thinBackendERNS0_6ConfigEjNSt3__18functionIFNS3_10unique_ptrINS0_18NativeObjectStreamENS3_14default_deleteIS6_EEEEjEEERNS_6ModuleERNS_18ModuleSummaryIndexERKNS_9StringMapINS3_3mapIyjNS3_4lessIyEENS3_9allocatorINS3_4pairIKyjEEEEEENS_15MallocAllocatorEEERKNSH_IyPNS_18GlobalValueSummaryESJ_NSK_INSL_ISM_SV_EEEEEERNS_9MapVectorINS_9StringRefENS_13BitcodeModuleENS_8DenseMapIS12_jNS_12DenseMapInfoIS12_EENS_6detail12DenseMapPairIS12_jEEEENS3_6vectorINSL_IS12_S13_EENSK_IS1C_EEEEEE'
ghc: Could not on-demand load symbol '__ZN4llvm11raw_ostream13SetUnbufferedEv'

GHC runtime linker: fatal error: I found a duplicate definition for symbol
   __ZN4llvm11raw_ostream13SetUnbufferedEv
whilst processing object file
   /usr/local/Cellar/llvm-4.0/4.0.0/lib/llvm-4.0/lib/libLLVMLTO.a
The symbol was previously defined in
   /usr/local/Cellar/llvm-4.0/4.0.0/lib/llvm-4.0/lib/libLLVMLTO.a(LTO.cpp.o)
This could be caused by:
   * Loading two different object files which export the same symbol
   * Specifying the same object file twice on the GHCi command line
   * An incorrect `package.conf' entry, causing some object to be
     loaded twice.
ghc: Could not on-demand load symbol '__ZN4llvm9StringMapIcNS_15MallocAllocatorEE11try_emplaceIJcEEENSt3__14pairINS_17StringMapIteratorIcEEbEENS_9StringRefEDpOT_'

GHC runtime linker: fatal error: I found a duplicate definition for symbol
   __ZN4llvm9StringMapIcNS_15MallocAllocatorEE11try_emplaceIJcEEENSt3__14pairINS_17StringMapIteratorIcEEbEENS_9StringRefEDpOT_
whilst processing object file
   /usr/local/Cellar/llvm-4.0/4.0.0/lib/llvm-4.0/lib/libLLVMLTO.a
The symbol was previously defined in
   /usr/local/Cellar/llvm-4.0/4.0.0/lib/llvm-4.0/lib/libLLVMLTO.a(LTOBackend.cpp.o)
This could be caused by:

などと吐いてstack ghciが死ぬ。 intero-modeはstack ghciに依存しているのでつらい。 REPLでゴニョゴニョできないのもつらい。

解決策

stack.yamlflags: {}を次のように書き換える

flags:
  llvm-hs:
    shared-llvm: true