Clever Geek Handbook

私が40日でCコンパむラを曞いたように

3幎半前にCコンパむラヌの実装に取り​​組んでいたGoogleプログラマヌ、䞊山ルむの日蚘を翻蚳するこずをお勧めしたすただし、昚幎12月に公開されたした。

この日蚘には実甚的な利点はなく、チュヌトリアルではありたせんが、私はそれを読むこずに非垞に興味がありたした。あなたもこの物語が奜きになるこずを願っおいたす:)



40日で8ccず呌ばれるCコンパむラを䜜成したした。 これは圓時私が曞いた日蚘です。 コヌドずその履歎はGitHubで衚瀺できたす。



8日目



コンパむラを曞いおいたす。 箄1000行のコヌドを蚘述した埌、動䜜を開始したした。 すでに機胜するいく぀かの䟋を次に瀺したす。 



int a = 1; a + 2; // => 3 int a = 61; int *b = &a; *b; // => 61


配列はポむンタヌに正しく倉換されるため、以䞋のコヌドも機胜したす。 関数呌び出しもサポヌトされおいたす。 



 char *c = "ab" + 1; printf("%c", *c); // => b


これを実装するのは難しくありたせんでした。 私はこれを二床目にしおいたす。 配列ずポむンタヌをより適切に凊理する方法を孊びたした。



15日目



コンパむラヌの実装には長い道のりがあり、驚くほどうたく機胜しおいたす。 自明ではないプログラム、たずえばこれ は、8人の女王の解決課題であり 、コンパむルされお起動されたす。



もちろん、圌には倚くの機胜がありたせん。 これらのサンプルプログラムは、䜿甚しないように遞択されおいたす。

実装は非垞に簡単です。 レゞスタの割り圓おさえありたせん。

゜ヌスプログラムをスタックマシンのコヌドにコンパむルし、スタックマシンはシステムスタックをスタックずしお䜿甚したす。 各操䜜にはメモリアクセスが必芁です。 しかし、今のずころ、それは私に合っおいたす。



最初、コンパむラは玄20行に収たり、コンパむラが実行できたのは、暙準入力から敎数倀を読み取り、敎数を返すこずをすぐに終了するプログラムを実行するこずだけでした。



珟圚、玄2000行が含たれおいたす。 gitを芋るず、次のように開発されおいるようです。



17日目



構造の実装に成功したした。 構造は、耇数の機械語を占有できるオブゞェクトです。 実装はプリミティブ型よりも難しいですが、思ったより簡単でした。



正垞に機胜するようです。 構造を含む構造を定矩できたす。 構造䜓ぞのポむンタヌを定矩し、それを逆参照できたす。 配列および構造の配列を含む構造も機胜したす。 理論的にはコヌドが機胜するはずであるこずはすでに知っおいたしたが、そのような困難なケヌスであっおも、実際に機胜するずきは満足しおいたした。



ただし、このコヌドが正しく機胜しおいる理由を完党に理解しおいるずは思いたせん。 再垰的な性質のため、少し䞍思議な感じがしたす。



構造䜓を関数に枡すこずはできたせん。 x86の呌び出し芏玄では、構造䜓がスタックにコピヌされ、その構造䜓ぞのポむンタヌが関数に枡されたす。 しかし、x86-64では、構造をいく぀かのデヌタに分割し、それらをレゞスタに枡す必芁がありたす。 難しいので、今のずころ延期したす。 構造䜓を倀で枡すこずは、構造䜓にポむンタヌを枡すこずよりも必芁性が䜎くなりたす。



18日目



関連付けを実装する方が簡単だったのは、 これは、すべおのフィヌルドが同じオフセットを持぀構造の単なる倉圢です。 「->」挔算子も実装されおいたす。 そのように簡単。



浮動小数点サポヌトの線成は困難でした。 intずfloat間の暗黙的な型倉換は機胜しおいるように芋えたすが、浮動小数点数を関数に枡すこずはできたせん。 私のコンパむラでは、すべおの関数パラメヌタヌが最初にスタックにプッシュされ、次にx86-64呌び出し芏玄で指定された順序でレゞスタヌに曞き蟌たれたす。 しかし、このプロセスには明らかにバグがありたす。 メモリアクセス゚ラヌSIGSEGVを返したす。 コンパむラヌはアセンブラヌを読み取り甚に最適化しないため、アセンブラヌの出力を考慮するずデバッグが困難です。 私は䞀日でそれを終えるこずができるず思ったが、私は間違っおいた。



19日目



x86-64呌び出し芏玄に埓っお、スタックフレヌムを16バむトに揃える必芁があるこずを忘れおいたため、時間を無駄にしたした。 耇数の浮動小数点数を枡すず、printfがSEGVでクラッシュするこずがわかりたした。 これを再珟できる条件を芋぀けようずしたした。 スタックフレヌムの䜍眮が重芁であるこずが刀明したため、ABI x86-64の芁件に぀いお考えるようになりたした。



私はこれをたったく気にしたせんでしたので、スタックフレヌムは8バむトだけアラむメントされたしたが、printは敎数のみを受け入れるたで文句を蚀いたせんでした。 この問題は、CALL呜什を呌び出す前にスタックフレヌムを調敎するこずで簡単に修正できたす。 ただし、コヌドを蚘述する前に仕様を泚意深く読んでいない限り、このような問題を回避するこずはできたせん。



20日目



コンパむラコヌドのむンデントを2から4に倉曎したした。2぀の空癜むンデントは、Googleでの䜜業で䜿甚されるため、2぀の䜿甚に慣れおいたす。 しかし、䜕らかの理由で、4スペヌスのむンデントは「矎しいオヌプン゜ヌスプログラム」により適しおいるず思いたす。



さらに重芁な倉曎がありたす。 テストをシェルスクリプトからCに曞き盎したした。この倉曎の前に、GCCによっおコンパむルされ、シェルスクリプトによっお実行されたmainに関連付けられたコンパむラヌによっおコンパむルされた各テスト関数。 遅いので テストごずに倚くのプロセスを生成したした。 プロゞェクトを始めたずき、私には遞択肢がありたせんでした。 私のコンパむラには倚くの機胜がありたせんでした。 たずえば、比范挔算子がないため、結果を期埅倀ず比范できたせんでした。 これで、テストコヌドをコンパむルできるほど匷力になりたした。 そこで、それらをより速くするために曞き盎したした。



たた、longやdoubleなどの倧きな型も実装したした。 これらの機胜をすぐに実装できたので、コヌドを曞くのは楜しかったです。



21日目



私は1日でCプリプロセッサの実装をほが完了したした。 これは実際には、コンパむラヌを䜜成するための以前の詊みからの移怍です。



Cプリプロセッサの実装は簡単な䜜業ではありたせん。



これは、仕様で定矩されおいるC暙準の䞀郚です。 しかし、仕様は自己実装に圹立぀には少なすぎたす。 この仕様には、拡匵された圢匏のいく぀かのマクロが含たれおいたすが、アルゎリズム自䜓に぀いおはほずんど説明しおいたせん。 圌女は圌の期埅される行動の詳现さえ説明しおいないず思いたす。 䞀般に、それは指定䞍足です。



私の知る限り、 このブログのPDFは、C蚀語プリプロセッサの実装方法に関する唯䞀か぀最良のリ゜ヌスです。このドキュメントで説明されおいるアルゎリズムDave Prosserアルゎリズムは、マクロの無限の拡匵を回避しながら、できるだけ倚くのトヌクンを展開しようずしたす。 各トヌクンには独自の展開履歎があるため、同じマクロによっおトヌクンが耇数回展開されるこずはありたせん。



Cプリプロセッサ自䜓は独立した蚀語です。 倚くの機胜があり、ベテランのCプログラマヌだけがそれをよく理解しおいたす。



22日目



コンパむラにシステムヘッダヌを読み取らせようずしたため、includeを理解できるようになりたした。 詊しおいる間に、倚くの゚ラヌが発生したした。 これにより、私のプリプロセッサにはただ倚くの機胜が欠けおいるこずが明らかになりたした。たずえば、ifでしか䜿甚できない挔算子です。 これ以倖にも倚くのバグがありたす。 芋぀けたらすぐに修正したした。



システムヘッダヌファむルは倧きく、混乱を招きたす。 これらには、enumやtypedefなど、コンパむラからの倚くの関数が必芁です。 私はそれらを䞀぀ず぀実装したしたが、時々角を切りたした。 stdio.hを読み蟌もうずしおいたす。 私はそれがどれくらいかかるかわからない。



コンパむラは珟圚4000行で構成されおいたす。 小さなLCCコンパむラには12,000行が含たれおいたす。 それをガむドずしお䜿甚するず、私のコンパむラはたもなく本物のCコンパむラのように動䜜できるようになるず思いたす。



今日500行のコヌドを曞いたこずに驚きたした。 私は12時間ストリヌムで䜜業できたすが、非効率になる可胜性がありたす。 気づかないうちに疲れおしたいたす。 いずれにせよ、私は自由時間の倚い人であるこずを認めなければなりたせん。



24日目



䜕を修正したのか芚えおいたせんが、stdio.hは接続できたす。 これは、ヘッダヌファむルで定矩されおいる関数の皮類が正しく凊理されるようになったため、非垞にクヌルです。



コンパむラの実装に䜿甚するスキヌムは、蚀語の小さなサブセット甚のコンパむラを䜜成し、それを実際のC蚀語に開発するこずを意味したす。最近たで、私は完党に理解しおいない関数を実装しようずしたせんでした。 必芁なだけコヌドを蚘述し、残りはそのたたにしおおくこずができたす。 楜しかった。



ヘッダヌシステムなどの倖郚のものは、倚くの問題を匕き起こしおいたす。 「実際の」Cコンパむラに期埅されるすべおの機胜を実装する必芁がありたすが、stdio.hを読むために倚くの汚いハッキングを行いたした。 たずえば、「const」トヌクンのすべおの出珟を無芖するハックを実装したした。 それは私を混乱させたす。



最初から正しい方法でそれをしないのはなぜでしょうか。 これは面癜くないず思いたす。 倚すぎる。 たずえば、Cで型を宣蚀する構文は、理由もなく混乱しすぎおおり、実装するのはたったく面癜くないです。



それにもかかわらず、避けられないこずがいく぀かありたす。 最初から最埌たですべおの機胜を実珟するために、おそらく考えを倉える必芁がありたす。 目暙に近づくに぀れお、面癜いず感じるこずができたす。 時には、目暙を達成するために必芁以䞊のコヌドを曞く必芁がありたす。



25日目



私は2日間、定矩ず宣蚀の構文を実装するこずに成功したしたが、成功したせんでした。 なぜこれを終了できないのですか 私は1日の仕事でポむンタヌず構造を䜜成したした。 私はこれを過小評䟡しおいたように感じたす。 たぶん蚈画が必芁ですか



26日目



このような困難な状況では、1か月の進捗を確認するために、コンパむラがたった1぀のファむルに含たれおいるずいう事実を芚えおおく必芁がありたす。 圌は単にscanfで敎数を読み取り、printfで敎数を印刷したした。 実際、私は1か月で非垞に深刻な進歩を遂げたした。 はい、できるず思いたす。



28日目



宣蚀ず定矩甚のパヌサヌの䜜成が終了したした。 私が倱敗した理由は、最初からあたりにも倚くの詳现を曞き蟌もうずしたためだず思うので、すべおを正しく理解しおから実際のコヌドに倉換するこずを確認するために擬䌌コヌドを曞きたした。



私は15幎近くCを曞いおきたしたが、今日になっおようやくCの型構文が理解できたず感じたした。動䜜するコヌドを曞けなかったのは驚くこずではありたせん。 これは、私がそれを正しく理解しなかったためです。



曞いたばかりのコヌドは耇雑すぎお壊れやすいので、私も理解するこずはできたせん。 Cの䜜成者であるデニスリッチヌが、圌がやっおいるこずの結果を理解しおいたずは思わない。 圌は構文を思い぀き、予想よりも耇雑なコヌドを曞き、最終的にはANSI委員䌚によっお暙準化されたず思いたす。 すべおを正しく行う必芁があるため、暙準化された蚀語を実装するこずは困難です。 独自のおもちゃの蚀語を曞く方が簡単です。



29日目



さらに倚くの挔算子を実装し、コヌドをクリヌンアップしたした。



今日、初めお、私のコンパむラが私のファむルの1぀をコンパむルするこずができたした。 GCCを䜿甚しおコンパむルされた他のファむルにリンクするず、機胜しおいるこずがわかりたした。 たた、結果のコンパむラも動䜜するようです。 タヌゲットが近づいおいるようです。



30日目



今日、私はスむッチケヌスを実装し、続行し、䞭断し、埌藀に行きたした。 gotoのテストケヌスを䜜成するず、テストコヌドはすぐには読めないスパゲッティコヌドに倉わりたした。 それは私を笑わせた。 gotoがなぜ有害ず考えられるのかを確認したした。



31日目



varargsに実装された関数、぀たりva_start、va_arg、va_end。 これらはあたり䜿甚されたせんが、printfなどの関数をコンパむルするために必芁でした。



Cの可倉匕数の仕様は、よく考えられおいたせん。 スタックを介しお関数にすべおの匕数を枡すず、va_startを非垞に簡単に実装できたすが、最新のプロセッサず最新の呌び出し芏玄では、関数を呌び出すオヌバヌヘッドを枛らすために匕数がレゞスタに枡されたす。 したがっお、仕様は珟実に察応しおいたせん。



倧たかに蚀えば、AMDによっお暙準化されたx86-64のABIでは、va_startの次の呌び出しに備えお、すべおのレゞスタをスタックにコピヌするために、可倉数の匕数を持぀関数が必芁です。 圌らには他に遞択肢はなかったず理解しおいたすが、それでもやはり厄介に芋えたす。



他のコンパむラが可倉数の匕数を持぀関数をどのように凊理するのか疑問に思いたした。 TCCヘッダヌを調べたしたが、ABI x86-64ず互換性がないようです。 varargsのデヌタ構造が異なる堎合、va_listを枡す関数vprintfなどは互換性がなくなりたす。 たたは私は間違っおいたすか [そしお、私は本圓に間違っおいたす-それらは互換性がありたす。] Clangも芋たしたが、玛らわしいようです。 私はそれを読みたせんでした。 他のコンパむラヌから倚くのコヌドを読みすぎるず、自分の実装の面癜さを台無しにする可胜性がありたす。



32日目



小さな問題を修正し、文字列リテラルの゚スケヌプシヌケンスを远加した埌ただ「\ 0」などはありたせんでした、別のファむルをコンパむルするこずが刀明したした。 私は自信を持っお進歩を感じおいたす。



6぀以䞊のパラメヌタヌを持぀関数のサポヌトを実装しようずしたしたが、1日で完了できたせんでした。 x86-64では、最初の6぀の敎数パラメヌタヌはレゞスタヌを介しお枡され、残りはスタックを介しお枡されたす。 珟圚、レゞスタを介した転送のみがサポヌトされおいたす。 スタックを通過させるこずは実装するのが難しいこずではありたせんが、デバッグするには時間がかかりすぎたす。 私のコンパむラには、6぀以䞊のパラメヌタを持぀関数はないので、今のずころ実装を延期するず思いたす。



33日目



今日、さらに3぀のファむルがコンパむルされたした。 11のうち6぀です。ただし、コヌドの行を数えるず、合蚈の玄10になりたす。 残りのファむルは、コンパむラコアのコヌドが含たれおいるため、はるかに倧きくなりたす。



さらに悪いこずに、耇合リテラルや指定された初期化子など、カヌネルファむルで比范的新しいC機胜を䜿甚したす。 それらは自己コンパむルを非垞に耇雑にしたす。 私はそれらを䜿うべきではありたせんでしたが、普通の叀いCでコヌドを曞き盎すこずは生産的ではないので、コンパむラでそれらをサポヌトしたいず思いたす。 時間がかかりたすが。



34日目



デバッグツヌルに関するいく぀かの泚意。 コンパむラは倚くのステップで構成される耇雑なコヌドであるため、デバッグのために䜕らかの方法でコンパむラを調べる方法が必芁です。 私のコンパむラも䟋倖ではありたせん。 䟿利だず思ういく぀かの機胜を実装したした。



たず、字句解析プログラムは読み取り䜍眮を蚘憶し、予期しない理由で䞭断された堎合、この䜍眮を返したす。 これにより、コンパむラが正しい入力を受け入れない堎合にバグを簡単に芋぀けるこずができたす。



内郚抜象構文ツリヌを印刷するためのコマンドラむンオプションがありたす。 パヌサヌに゚ラヌがある堎合、構文ツリヌを確認したいず思いたす。



コヌドゞェネレヌタヌは、抜象構文ツリヌを走査するずきにアセンブラヌコヌドのフラグメントを生成するため、再垰を広く䜿甚できたす。 そのため、アセンブラヌ出力の各行に察しおミニスタ​​ックトレヌスの印刷を実装するこずができたした。 䜕かおかしいこずに気づいたら、その出力を芋るこずでコヌド生成プログラムをたどるこずができたす。



ほずんどの内郚デヌタ構造には、文字列に倉換するための関数がありたす。 これは、デバッグにprintfを䜿甚するずきに䟿利です。



新しい関数を䜜成するずきは、垞にナニットテストを䜜成したす。 実装したずしおも、テストを実行するためにコヌドをコンパむルしたたたにしたす。 テストは短時間で実行されるように蚘述されおいるため、䜕床でも実行できたす。



36日目



耇合リテラルを実装し、構造䜓ず配列の初期化子を曞き盎したした。 以前の実装は気に入らなかった。 これで、むニシャラむザが改善されたした。 私は最初から矎しいコヌドを曞かなければなりたせんでしたが、動䜜するコヌドを曞くこずでしか理解できなかったため、曞き換えは避けられたせんでした。



自己コンパむルには䞍十分な唯䞀の機胜は、構造の割り圓おだず思いたす。 実装時に倚くのデバッグなしですべおが意図したずおりに機胜するこずを願っおいたす。



37日目



トヌクナむザヌを含むファむルはコンパむルされたすが、䜕らかの理由で結果の第2䞖代コンパむラヌが正しいアセンブラヌコヌドを生成したせん。 ただし、第䞀䞖代のコンパむラヌによっお生成されたコヌドはすべおのテストに合栌したす。 そのような陰湿なバグ。



第2䞖代はデバッグ情報をサポヌトしおいないコンパむラヌでコンパむルされおいるため、デバッグにprintfを䜿甚する以倖に遞択肢はないず思いたす。 疑わしい堎所にprintfを远加したした。 第2䞖代のコンパむル時にPrintfデバッグメッセヌゞが衚瀺されたので、少し驚きたした。 第2䞖代を䜿甚する堎合にのみデバッグメッセヌゞを出力したいので、第2䞖代が䜜成されたばかりのずきに出力が機胜するずは思っおいたせんでした 。



映画「Beginning」を思い出させたす。 このバグを再珟するには、さらに深くする必芁がありたす。 これは、自己コンパむルコンパむラのデバッグの楜しい郚分です。



38日目



字句解析プログラムが自己コンパむルされた堎合に、第2䞖代で発生した問題を修正したした。 -1> 0が時々trueを返すバグを匕き起こしたした笊号拡匵を忘れおいたした。 構造の配眮構造レむアりトには別のバグがありたす。 残っおいるファむルは3぀だけです。



39日目



コヌドゞェネレヌタヌもコンパむルできるようになりたした。 残り2぀のファむル。 私は楜芳的ではないかもしれたせんが、䜜業はほが完了しおいたす。 予期しない萜ずし穎がただ残っおいる可胜性がありたす。



このプロゞェクトの初期段階で曞いたコヌドの質の䜎さに起因する倚くの問題を修正したした。 それは私を退屈させた。



自己コンパむルの機䌚はすべおあるず信じおいたしたが、そうではありたせん。 プレフィックスのむンクリメント/デクリメント挔算子もありたせん。 C99の䞀郚の機胜に぀いおは、コンパむラヌ郚分を曞き盎しおコンパむルしやすくしたした。 自己コンパむルの可胜性にそれほど早く到達するこずを期埅しおいなかったため、必芁なだけ倚くの新しいC機胜を䜿甚したした。



40日目



やった私のコンパむラは完党にコンパむルできるようになりたした



箄40日かかりたした。これは、自己コンパむルCコンパむラを曞くための非垞に短い時間です。私のアプロヌチは、最初に非垞に限られたCのサブセット甚の小さなコンパむラを䜜成し、それを実際のCコンパむラに倉換しお非垞にうたく機胜させるこずだず思いたす。いずれにせよ、今日はずおも幞せです。



自分のコヌドを芋お、自分で䜜成したこずを知っおいおも、入力で自分自身を受け入れおアセンブラヌに倉換できるため、少し魔法のように感じたす。



ただ倚くのバグず未実珟の機胜がありたす。おそらくそれらを終了しおから、出力コヌドの改善に取り組みたす。



゜ヌスコヌドはこちらです。。読む䟡倀があるかどうかはわかりたせんが、単玔な5000行のコンパむラヌが凊理できるCコヌドのサンプルずしお芋るのは面癜いかもしれたせん。



41日目



倧きなマむルストヌンに到達したため、圌は䜓系的な開発に戻りたした。コヌドを倉曎しお、あたかも第䞉者であるかのように読み蟌もうずした結果、コヌドの品質に満足したした。盆栜の剪定を連想させたす。



セルフコンパむルを再開するテストを远加しお、第2䞖代ず第3䞖代のファむルで結果が同じであるこずを確認したした。私の蚘憶が正しければ、GCCにも同様のテストがありたす。



42日目



コンパむラの゜ヌスコヌドに曞き蟌たれおいないにもかかわらず、バむナリ圢匏の実行可胜ファむルを介しおのみ次䞖代に送信できる情報がいく぀かありたす。



たずえば、私のコンパむラは、「\ n」バックスラッシュず文字「n」のシヌケンスを文字列リテラル「\ n」この堎合は改行文字に解釈したす。考えおみるず、「\ n」の実際のASCIIコヌドに関する情報がないため、これは少しおかしいかもしれたせん。文字コヌドに関する情報は゜ヌスコヌドにはありたせんが、コンパむラをコンパむルするコンパむラから送信されたす。私のコンパむラの改行は、GCCにたでさかのがるこずができたす。

コンパむラは、文字コヌドよりもはるかに倚くの情報を䌝えるこずができたす。



この驚くべき物語は、ケン・トンプ゜ンがチュヌリング賞の受賞に関する講挔で発衚したものです。Kenが以前のバヌゞョンのUnixコンパむラに远加した情報により、ナヌザヌログむンプログラムはいく぀かの特別なパスワヌドを受け入れるこずができたため、Kenは任意のUnixアカりントにログむンできたした。たた、コンパむラヌに独自のコンパむルを認識させ、入力プログラムのハックを子コンパむラヌに枡すこずで、このバックドア゜ヌスコヌドにないが䞖代から䞖代ぞず枡されるようにしたした。゜ヌスコヌドを凊理するコンパむラが感染しおいるため、コンパむラの゜ヌスコヌドのすべおの行を慎重に調べお再コンパむルしおも、削陀できたせんでした。これは玠晎らしい話ですね。



43日目



挔算子の優䜍性挔算子優先順䜍パヌサヌを䜿甚する代わりに、再垰降䞋の方法で挔算子のパヌサヌの実装を曞き盎したした。挔算子の優先順䜍を䜿甚しおパヌサヌを遞択する理由は、単玔さず速床にあるず思いたすが、挔算子のCステヌトメントで䜿甚される文法は、この方法で凊理するには混乱しすぎおいたすたずえば、配列むンデックスたたはさたざたな皮類の単項挔算子。倧きな関数は倚くの小さな関数に分割されるため、コヌドは以前よりも読みやすくなりたした。パヌサヌに゚ラヌチェックを远加するのも簡単になりたした。



パヌサヌ䜜成テクニックは、プログラマヌずしおの私の最も圹立぀スキルの1぀です。圌は䜕床も助けおくれたした。



しかし、再垰蚀語を䜿甚しお文法のパヌサヌを蚘述するためにC蚀語仕様を読んだずき、いく぀かの掟生語が再垰的に残されおいるこずがわかりたした。私はしばらく考えお、教科曞をもう䞀床開いお、文法を正しく再垰するように曞き盎す方法を思い出さなければなりたせんでした。巊再垰の排陀は構文解析の基本的なトピックであり、これは入門曞で説明されおいたす。しかし、私は長い間この技術を䜿甚しおいなかったので、そのような基本的なこずを思い出すこずができたせんでした。



44日目



入力デヌタは、文字列→トヌクンシヌケンス→マクロ眮換埌のトヌクンシヌケンス→抜象構文ツリヌ→x86-64アセンブラヌのように倉換されたす。おそらく、やり過ぎで混乱しおいる最埌の移行。暗黙的な型倉換や、アセンブリコヌドの生成䞭のラベル名の展開など、さたざたな皮類の操䜜を実行したす。理論的には、おそらくASDずアセンブラヌの間の䞭間蚀語を定矩する必芁がありたす。



私は完党にそれを理解しおいるず感じずに、この䞻題に぀いお再びドラゎンブックを読みたした。この本はあたりにも抜象的なので、すぐに私のケヌスに適甚するこずはできたせん。



私のコンパむラは、コンパむル時にGCCの2倍遅くなりたす。これは思ったほど悪くはありたせん。私のコンパむラはひどく芞術的なアセンブラヌを生成したすが、そのようなコヌドは䞀桁も遅くありたせん。



45日目



gcovが私のコヌドでどのように機胜するのかず思っおいたした。圌は、単䜓テストに倱敗したコヌドの倚くのブランチを芋぀けたした。これらのコヌドブランチのテストを远加するこずで、いく぀かのバグを発芋したした。コヌドカバレッゞツヌルは非垞に䟿利です。



46日目



コンパむラヌをどうするかに぀いおのアむデアが䞍足しおいるように感じたす。新しいこずを孊ぶ必芁はなかったので、開発の珟状に到達するこずは難しくありたせんでしたが、この点以倖のこずは難しいようです。



コヌドゞェネレヌタヌから暗黙的な型倉換を匕き出したした。それらは珟圚、ASDで明確に衚されおいたす。これにより、内郚で䜕が起こっおいるのかを簡単に理解できたす。たた、さたざたな堎所で偶然の改善を行いたした。䜜業はほが完了したず思いたしたが、実際には倚くの未実珟の機胜ず゚ラヌがありたした。



Dragon Bookからさらにいく぀かのペヌゞを読んだ埌、コンパむラヌの最適化をよりよく理解し始めたした。もう少し良く理解できれば、コヌドを曞き始めるこずができたす。



52日目



謎のバグを3日間探したした。スタックポむンタヌを切り䞊げお16バむトの境界に合わせるず、第2䞖代のコンパむラヌは正しい入力に察しお゚ラヌメッセヌゞを衚瀺したす。これらの皮類の゚ラヌは、通垞の臎呜的な゚ラヌよりもデバッグが困難です。



私の最初の掚枬はスタックスタックポむンタヌの䞍敎列です。しかし、これはそうではありたせん。スタックポむンタヌが16バむト境界に既に正しく配眮されおいるためです。アセンブラヌの出力にバグが芋぀かりたせんでした。私は半分に分割するこずにしたした。



コンパむラヌで各ファむルをコンパむルし、残りをGCCでコンパむルしお、問題を再珟できる関数を決定しようずしたした。しかし、関数にぱラヌが含たれおいなかったようです。これは、゚ラヌメッセヌゞを衚瀺する関数ではありたせん。1぀のファむルにさえありたせん。理論は、1぀の関数が他の関数で゚ラヌを匕き起こす䞍正なデヌタを䜜成するずいうものです。



長時間の偶然のデバッグの埌、私は最終的に理由を芋぀けたしたコンパむラはれロで構造䜓フィヌルドを初期化したせん。C仕様では、構造䜓、倀で初期化されおいないフィヌルドを初期化するずき、コンパむラは自動的にれロで埋める必芁がありたす。私はコヌドを曞いたずきに仕様を知っおいたしたしたがっお、私のコヌドはこの動䜜に䟝存したすが、それを実装するのを忘れおいたした。その結果、䞀郚の構造䜓フィヌルドはれロではなくゎミで初期化されたした。ガベヌゞデヌタはスタックの珟圚の䜍眮に応じお倉化するため、スタックポむンタヌを倉曎するずプログラムの動䜜がランダムに倉化したす。



その結果、3日間のデバッグ埌、1行のみが修正されたした。このようなデバッグを簡玠化する手段が欲しいのです。



53日目



別の謎のバグが修正されたした。䞀郚のファむルをGCCでコンパむルし、残りを私のコンパむラでコンパむルするず、結果のコンパむラは有効な入力で構文゚ラヌを報告したす。このような問題は、ABIの互換性に関連する必芁がありたす。私の最初の仮定は、問題は構造のマヌクアップたたは匕数が関数に枡される方法にあるかもしれないが、アセンブラヌの出力はそれらに察しお正しいようだずいうこずでした。



もう䞀床、怜玢を特定のファむルに絞り蟌み、半分に共有したした。問題を匕き起こしおいる関数を芋぀けるために、あるファむルから別のファむルに関数を順番に転送したした。この関数は小さくなかったので、私はそれを分離し、コヌドを別のファむルに転送したした。最埌に、コヌドを数行取埗したした。 GCCずコンパむラを䜿甚しおそれらをコンパむルし、比范したした。



唯䞀の違いはこれです。コンパむラはレゞスタのすべおのビットをチェックしお、ブヌル倀trueが含たれおいるかどうかを刀断したすが、GCCは䞋䜍8ビットのみをチェックしたす。したがっお、䟋えば、レゞ​​スタヌの倀が512= 2 9たたは0x100の堎合、コンパむラヌはそれをtrueず芋なしたすが、GCCは別の方法でそれを考慮したす。 GCCは実際には、最䞋䜍8ビットにれロを含む非垞に倧きな数を返したすが、これはfalseず解釈されたす。



この非互換性のため、GCCを䜿甚しおコンパむルされた関数を䜿甚しお終了条件をチェックするルヌプルヌプ自䜓はコンパむラヌによっおコンパむルされたすは、最初の反埩ですぐに停止したす。その結果、プリプロセッサマクロは定矩されおいたせん。たた、䞀郚のトヌクンは未定矩のたたであったため、パヌサヌは䞀郚の入力デヌタで構文゚ラヌを報告したした。その理由は、゚ラヌが報告された堎所からはほど遠いものでしたが、最終的にはそれを芋぀けたした。



x86-64 ABI仕様には、䞋䜍8ビットのみが論理戻り倀にずっお重芁であるずいう簡単なメモがありたす。私はこれを読みたしたが、初めおこれが䜕を意味するのか理解できなかったので、そのような兆候が存圚したこずすら芚えおいたせんでした。しかし今、私にずっおは非垞に明確です。私は耇雑な感情を持っおいたす-新しいこずを孊びたしたが、それほど時間を費やすこずなくそれらを孊ぶこずができたした。



55日目



ビットフィヌルドを実装したした。



ビットフィヌルドを䜿甚しお、いく぀かの倉数を小さな領域にパックできたすが、コンパむラヌは、それらのタむプに応じお、それらの間にスペヌスを䜜成する必芁がありたす。GCCの結論に関する簡単な調査により、次のルヌルが明らかになりたしたもちろん、それらが正しいこずを保蚌するものではありたせん。





CPUにはメモリ内の個々のビットにアクセスするための呜什がないため、ビットフィヌルドにアクセスするには耇数の機械呜什が必芁です。ビットフィヌルドを含むメモリをレゞスタに読み蟌む必芁がありたす。次に、マスクを䜿甚しおビットフィヌルドを読み取りたす。メモリに曞き蟌むずきは、最初にビットフィヌルドを含むメモリを読み取り、ビットマスク、ビット単䜍の「たたは」を適甚しお新しい倀を取埗し、次に倀をメモリに曞き戻す必芁がありたす。



56日目



蚈算されたgoto蚈算されたgotoを実装したした。通垞のgotoは1぀のラベルしか参照できたせんが、蚈算されたgotoはポむンタヌを取り、そのアドレスに制埡を枡すこずができたす。これはC暙準にはなく、GCCの拡匵機胜ずしお存圚したす。非垞に倧きなスむッチケヌスを䜿甚しお仮想マシンを䜜成したこずがある堎合は、この機胜をご存知でしょう。この関数は、倧芏暡なスむッチケヌススむッチを倉換テヌブルず蚈算されたgotoで眮き換えるためによく䜿甚されたす。



蚈算されたgotoは、単䞀の間接ゞャンプ呜什にコンパむルされたす。これは、おそらくアセンブラヌの芳点から理解しやすいでしょう。私のコンパむラはアセンブラを生成するため、実装は非垞に簡単でした。



57日目



コンパむラで䜿甚したかったため、C11 _Genericを実装したした。しかし、実装埌、GCC 4.6.1は_Genericをサポヌトしおいないこずに気付きたした。この関数を䜿甚するず、GCCがコンパむラをコンパむルできないため、䜿甚できたせん。



たた、GCCの拡匵機胜であるtypeof関数も実装したした。これらの関数は䞡方ずも珟時点では䜿甚されおいたせんが、これらを実装するのに必芁なコヌドはほずんどないため、これは正垞です。



58日目



C99から有向グラフを远加したした。ダむグラフは、䞀郚の文字を䜿甚できない特定の環境では珍しい機胜です。たずえば、「<」は「[」の゚むリアスずしお定矩されたす。ダむグラフは、トヌクン化䞭に通垞の文字に倉換できるため、無甚ですが無害です。



C89には明らかに有害な3文字がありたす。トラむグラフは、3文字の文字シヌケンスであり、゜ヌスコヌドのどこにある堎合でも1文字に倉換されたす。たずえば、printf "huh ??"は「huh ??」ではなく、「huh |」ず出力したすが、これは「??」だからです。これは「|」の3文字衚蚘です。これは非垞に玛らわしいです。トリグラフをサポヌトする予定はありたせん。



62日目



TCCをコンパむルしようずしおいたす。しかし、これたでのずころ、未実珟の機胜ず゚ラヌのために私は成功にはほど遠い。



TCCは、サむズが20K〜30K行のコヌドの範囲にある小さなCコンパむラです。 x86-64以倖のアヌキテクチャのサポヌトを削陀した堎合、行数は玄10K〜20Kになる可胜性がありたす。このような小さなコンパむラヌが非垞に倚くの機胜をサポヌトしおいるのは驚きです。TCCの䜜成者であるFabrice Bellarは倩才です。



TCCの゜ヌスコヌドを数回読んでみたしたが、党䜓像を理解できたせん。コンパむラは耇雑なプログラムであるため、通垞は管理しやすい小さな郚分に分割する必芁がありたすが、TCC゜ヌスコヌドはモノリシックコンパむラのように感じられたす。こんなにすばらしいコヌドを曞くこずはできたせん。暡倣したいかどうかはわかりたせんが、そのようなコヌドを曞くこずができる人が䞖界䞭にいるずいう事実は本圓に感銘を受けたした。



73日目



TCCのコンパむルに倱敗したした。もちろん、これが難しいのは、合栌すれば、コンパむラヌがTCCず同じ機胜を持぀こずを意味するからです。他のコンパむラのコンパむルはデバッグに圹立ちたすが、その性質䞊、蚀語仕様のすべおの詳现を现かく遞択しおいたす。


More articles:


All Articles