セキュリティ・キャンプ2018で作ってきていた自作Cコンパイラが、9月4日にセルフホストを達成したので参加記を書いていく。
セルフホスト、達成です!(プリプロセッサはまだない) #hsjoihs_c_compilerhttps://t.co/HlCUT5Hqlg
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) September 3, 2018
(執筆はプリプロセッサを実装してからにしようとも思っていたが、アンケートの結果「先に記事を書くべし」とのことだったので)
先にやるべきは #hsjoihs_c_compiler
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) September 8, 2018
応募とか
sksat_tty氏とかが言及していたことをきっかけに興味を持ち始め、↓に直接後押しされる感じで「じゃあ応募してみるかなぁ」と思い始めた。なお、この段階では「思った」だけであった。
セキュキャンなりなんらかの審査があるイベント、「自分なんかだとダメだろうなあ」とか勝手に思って申込みすらしないのが一番もったいなくて、とりあえず申し込んでみるのとても大事です、これホント https://t.co/eCE2HDnNs6
— ロケットはえっち (@sksat_tty) 2018年3月21日
なんかCコンパイラゼミとかいうのが行われるらしい。Cなら趣味で仕様とか読んでるし(書いたことはあんまりないけど)楽しめそう。
というわけで僕ですら3日だけなら無謀だと思っている企画なんですが、事前にしっかりサポートしていけば大丈夫であろうという目論見のもとセキュキャンの講師をすることにしました。というわけでみっちりやりますよ。 https://t.co/WlxWZw4HF8
— Rui Ueyama (@rui314) 2018年4月24日
月日は流れ5月後半。締切も近づきTLがセキュキャンで盛り上がり始める。なお私は書き始めてすらいない。
セキュキャン、楽しそうだがまだ課題を始めていないのである(やれ)
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年5月19日
とりあえず応募用紙を7296文字書いて出した。*1メールの履歴を見る限り、応募を提出したのは5月27日だそうだ。
そして締切がやってくる。
世界はつらく厳しいものですが、セキュキャン応募チャレンジを達成された皆様は本当にお疲れさまでした。回答を書き上げる過程だけでも、学んだことは多かったと思います。
— hikalium (@hikalium) 2018年5月28日
これから我々は真剣に選考しますので、皆様まずはゆっくりと休んでください...。#seccamp
受かった
6月14日に合否発表があった。受かっていた。感謝の気持ちにあふれるなどした。
私は(当時バタバタしていたこともあり)合格したことをツイートしそこねており(他人の合否ツイはRTしていたというのに)、数日後に「あれ、セキュキャン来るんですよね?」というDMが講師のhikalium先生から来てしまったので慌ててツイートをした。
セキュリティキャンプ全国大会2018の「Cコンパイラを自作してみよう!」ゼミに参加します。よろしくお願いします。#seccamp#seccamp2018
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年6月18日
不安感を与えてしまって申し訳ないなどと思った。
これでセキュキャン2018 Cコンパイラコースの受講者が全員Twitter上で参加表明をしてくれたので、とても安心した。
— hikalium (@hikalium) 2018年6月18日
やっていき
6月下旬には事前学習slackが立ち上がり、
#seccamp2018 の事前学習slackに入った
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年6月22日
7月8日から開発が始まった。なお、開発日記は↓に書いている。
セキュキャン前日
なんか天気が荒れており、雷が鳴っていたので念の為パソコンをコンセントから外しておいたりしていたところ、slackの方で「前泊だけどずぶ濡れになった」という情報が流れてきた。大変そう。
とか思ってのんきにコードを書いていたところ*2、
はりぼて自作Cコンパイラaqccでセルフコンパイルできました。楽しい。https://t.co/bOlDDuAv50 #seccamp
— 艮 鮟鱇 (@ushitora_anqou) 2018年8月13日
とかいう話がtwitterとslackに流れてきていた。つよい。ちなみに当時の私はポインタ・配列・char・文字列リテラルとかが実装されている程度の進捗であった。
あと、
セキュキャン期間中、C言語でお困りの方がいらっしゃいましたら、YトラックCコンパイラゼミにおいでください。きっと6人の賢者たちが仕様書をもちだして答えてくれます...(講師はのんびりそれを眺めるお仕事です)。
— hikalium (@hikalium) 2018年8月12日
とかいうのが流れてきたので「これ、手元の本を色々持ってっといた方がよいのでは」という気持ちになるなどした。
セキュキャン当日 (Day 1)
荷物の準備とかを慌てて始め、無事到着。
初日は集中開発コースの人々も全員共通の講義を受けるので、Cコンパイラには一切手を付けなかった。(同じテーブルにいる人に対してコンパイラのdemoとかをしたりはした。)共通講義では様々な有益情報が得られ、ありがたかった*3。
Day 2
集中開発である。とりあえずはコードを書いていく。
具体的な開発内容は前述の日記に書くとして、大まかな変更点は以下の3つ。
- 過去に発見していたものの見なかったことにしていた「関数呼び出し式の中で関数呼び出しが行われるとバグることがある」を修正した。このバグの原因究明で私が悩んでいる間、隣のほうでは「レジスタに整数演算するとセグフォする」とかいうすごい現象が起きていて、「つらそう(つらそう)」などと思った。
- 構文解析と意味解析を分離した。時間は掛かったが、わりとただの作業だったのでそこまで大変ではなかった。
- で、旧い「構文+意味解析機」と新しい「意味解析機」で生成される構文木にわずかに差がある(ので、新しい構文木でテストを走らせるととあるテストケースで無限ループになる)問題が検出された。要するに新しいほうがバグってる。経験上、デバッグは睡眠時間を削って行うと効率が下がるので、そこそこ原因が絞り込めた段階で寝ることにした。
Day 3
朝起きてデバッグ。後置++と後置--に関して意味解析器でノード付け忘れていただけだった。なるほど、それでforの第三式が吹っ飛ぶので無限ループになっていたと。
とりあえず構造体が欲しい。オフセットの計算が少々厄介という話を聞いた*4ので、これを機にそのあたりについてちゃんと勉強しようと考えた。とりあえず軽くググって出てきた「データ型のアラインメントとは何か,なぜ必要なのか?」に言及したところ、「そのサイト分かりやすかったからオススメ」と言われたので読んだ。
理解したので組んでいく。「このパターンは使わんから組まなくていいか」みたいなアドホックをやりまくっていたら泥沼にはまり、作り直すはめになった。型のスコープをちゃんと実装するのが面倒ということも鑑み、最終的に取った戦略は次の通り。
- ちゃんとtype-specifierとして
struct A {int a; int b;}
とstruct A
の両方を許す - 変数宣言/定義およびそれに準ずるものが登場した時、その宣言の中に構造体の言及があるかどうか確認。
{int a; int b;}
つきで構造体型が言及されていればメンバを登録。ただしローカルの場合は現状では未対応。{int a; int b;}
なしでの言及はローカルでも問題なく素通り。
この「登録」でstructのsizeを追加していくことで、structの配列とかをローカルやグローバルに作れるようになった。
Day 4
構造体だけあってもメンバアクセスができなければほぼ意味がない。ということで実装した。
実質今日が最終日なので、とりあえずあと一つぐらい機能を足して「ここまでできました」をやりたい。何を足そう。
そういえばvoidが一切無いな。で、voidを足せばvector.cがセルフホストできそうだ*5。足すか。
ということで「空の引数リストとしてのvoid」「void*としてのvoid」「何も返さない関数としてのvoid」を実装。スライド(↓*6)も作って発表した。
そのあとは、本を頂いたりした。私はそこそこ前に買おうかと思って結局買わないでいた 「https://www.amazon.co.jp/独自CPU開発で学ぶコンピュータのしくみ-伊藤-剛浩/dp/4798045365」などを頂いた。
Day 5
最終日。とりあえず、増えた荷物*7を処理するのが大変だった。
$ zip 荷物.zip 荷物
— callsnote (@callsnote) 2018年8月17日
をしている(7zしたい)(そもそもの容量が大きい)
様々な発表が行われた。uint256_t氏の「自作JSエンジンの、自作ブラウザ上での発表」のインパクトがとても強かった。
uint256_t氏やばすぎる(自作ブラウザで自作JavaScriptのプレゼンをするという粋な演出)。
— hikalium (@hikalium) 2018年8月18日
0日目セルフホストの人がプレゼンも2分スピーチも完璧にやっていて「すごいなぁ」となった。
一方私は発表の合間を縫ってswitch-caseを実装することを試みた。結果、caseもdefaultもないswitch *8が実装できた。
「さてセキュキャン終わったし帰るか」とか思っていたら、講師のRuiさんの「Cコンパイラ班で焼肉食べませんか、よかったらuint256_tくんもどうぞ」という提案により焼肉となった。
Rui さんたちと焼肉食べます
— uint256_t (@uint256_t) 2018年8月18日
Ruiさんごちそうさまでした。ありがとうございました。(DMに書き忘れたのでここに書いておく)
その後
なんやかんや機能を足していってセルフホストできた。やったね。
…というので締めるのも微妙なので、セキュキャン以降セルフホストまでの話をかいつまんで書いて締めとする。
フランケンコンパイル
順当に機能を足していき、8月26日には音ゲー勢とのオフ会で(人々が音ゲーをしている中、私はゲーセンの椅子に座ってコードを書いていたので)フランケンコンパイル*9に成功した。
はすじょいさんと椅子で待機してる
— 南夏 (@t_blazerona) 2018年8月26日
コンパイラのフランケンコンパイル(自身を部分的にコンパイル)が成功した。 #hsjoihs_c_compilerhttps://t.co/Tz6PIDHj4j
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年8月26日
ソースコードに手動で手を加えることで自身のソースコードと同じ機能のアセンブリを吐くのはセキュキャン期間中にできていたけど、手を加えずにできるようになったのは比較的うれしいものがある
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年8月26日
なお、余談だが、フランケンコンパイルに浮かれていたらあえなくバッテリー切れを起こした。
隣でブチッを見て驚いた
— 南夏 (@t_blazerona) 2018年8月26日
フランケンコンパイルのテストケース増やしてテスト回してる最中に落ちた(最近は残り30%で落ちるのでつらい) https://t.co/UbLSGpTkfu
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年8月26日
一回復活しかけたけどゲージ真ん中で再度ブチッ
— 南夏 (@t_blazerona) 2018年8月26日
悲しいなぁ
最近パソコンのバッテリーが不安定でつらい思いをしている。
diff
先人の轍を踏まぬよう、今の段階から2世代目(clangでコンパイルした初代自作コンパイラで、自作コンパイラの一部をコンパイルしてできたバイナリ)と3世代目(2代目の自作コンパイラで、自作コンパイラの一部をコンパイルしてできたバイナリ)のdiffを取るようにしておいた。これが実はあとでかなり役立った。
先人が通ってきた「2代目と3代目が違う」というヤバを早期から検出すべく、もうテストに2代目と3代目のdiffを入れるようにした
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年8月27日
構造体を値で返す
セキュキャンCコンパイラ班の他の人のコンパイラと私のコンパイラの大きな違いとして、私の実装では構造体を値で扱っているコードがかなり多いというのがある。ということで8月28日の段階で構造体の一括代入を実装した。
さて、「構造体を値で扱っているコードがかなり多い」ということは、構造体を値で返す関数も実装する必要がある。ところで、(私がソースコード中で使っている構造体については)x86-64 System V ABIでは2種*10に分類され、挙動が異なる。
System V ABI だと、この2ファイルをコンパイル&リンクすると正常に動いてくれるのか… pic.twitter.com/zNk8o9EV4t
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年8月28日
ちなみに、struct F {int a; int b;}; とかのときは System V ABI ではこの互換性がありません(普通に8バイトの値を返す) https://t.co/GOf2DFD0ke
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年8月28日
とりあえず、INTEGERという分類に属する構造体を返せるようにして、
小さめの構造体を値で返せるようにした。 #hsjoihs_c_compilerhttps://t.co/imMCjoZJfd
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年8月29日
関数に構造体を渡すことに関しては実装しないことにして*11、
「INTEGERに属する構造体を返す関数」を呼ぶ処理を書いたら興味深いタイプのバグが出てきて、
さて「二世代目の実行中に非自明に落ちる」が出てきて、盛り上がってまいりました #hsjoihs_c_compiler
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年9月2日
原因判明。構造体を返す関数を呼ぶ時、引数をレジスタに入れていない!!! #hsjoihs_c_compiler
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年9月3日
MEMORYに属する構造体を返す関数の呼び出しを実装し、
MEMORYなクラスの構造体を返す関数を呼び出せるようになった。 #hsjoihs_c_compilerhttps://t.co/EkxO4GPvYy
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年9月3日
MEMORYに属する構造体を返す関数の定義を実装し、
MEMORY_CLASSの構造体を返す関数を定義するのにも成功。さああとはセルフコンパイル(してバグが出たらデバッグ)するだけだ #hsjoihs_c_compilerhttps://t.co/lAE0SvJfez
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) 2018年9月3日
冒頭のとおりになるという話である。
セルフホスト、達成です!(プリプロセッサはまだない) #hsjoihs_c_compilerhttps://t.co/HlCUT5Hqlg
— hsjoihs@数情物化語(@hsjoihs@mstdn.jp) (@hsjoihs) September 3, 2018
*1:応募用紙はまた別の機会に全文公開する
*2:荷物の準備、とかではないことに注目
*3:講義の内容にどこまで言及していいのかが分からないので、何も言及しないでおく
*4:「int, char, char, intって12バイトなんですよ。『intが4バイトだから全部4バイトに合わせて、intが4バイト、charが4バイト、charが4バイト、intが4バイト』みたいに勘違いすると間違える」みたいな話がされていた
*5:constとか無いからそれは手で取り除かないと動かないけど
*6:ただしセキュキャン時とのdiffあり
*7:様々なものを頂けたのはありがたいことであって、どちらかというと私の用意したスーツケースが妙に小さかったことが主問題であった
*8:「それはswitchではない」と言われた。それはそう
*9:コンパイラの一部を自分のコンパイラで、残りをclangでコンパイルすること
*10:詳しいことは https://www.uclibc.org/docs/psABI-x86_64.pdfに書いてある
*11:まず、MEMORYに属する構造体はスタックを使わなければならない。現状引数をスタックで渡す処理は実装していないので後回しにしたい。また、INTEGERに属する構造体はレジスタを使って渡すのだが、ソースコード上の引数と消費するレジスタ数が異なってくるとか面倒なので、こっちも後回しにしたい。