ハクソク

世界を動かす技術を、日本語で。

C生成に関する考察

105日前原文(wingolog.org)

概要

  • C言語 をターゲットとしたコンパイラ生成についての実践的な知見
  • static inline関数 によるデータ抽象化と最適化
  • 明示的な型変換 と意図を持ったラップ構造体の活用
  • ABIや戻り値処理の工夫 によるCコード生成の安定化
  • Cをターゲットとする利点と課題 の整理

Cをターゲットとしたコンパイラ生成の実践ノート

  • C言語 はアセンブラより高レベルなターゲット言語としてよく利用される選択肢
  • 自動生成されたCコード は手書きCより未定義動作の回避が容易
  • 生成パターン や設計の工夫で堅牢なCコード生成を実現

static inline関数によるデータ抽象化

  • static inline 関数はデータ抽象化のコストをゼロにできる最適化手段
  • かつては マクロ が多用されたが、データアクセスや実装隠蔽にはinline関数が適切
  • 例：WebAssemblyのメモリ範囲をstructで管理し、アクセス関数もstatic inlineで記述
    • BOUNDS_CHECK などのチェックもマクロで柔軟に制御
  • static inline によって、structの値渡し時のABI制約やパフォーマンス懸念も解消

暗黙の整数変換を避ける

  • C言語 のデフォルト整数変換（例：uint8_t→int）や符号付き整数の境界条件は厄介
  • 生成Cコードでは 明示的な型変換関数 （例：u8_to_u32, s16_to_s32等）を用意
    • -Wconversion フラグの活用で変換ミスを検出
  • 型変換関数をstatic inline化し、型保証と最適化の両立

意図を持ったラップ構造体で生ポインタや整数を包む

  • Whippet （C製GC）の例：size_tやuintptr_tのまま扱うと混乱しやすい
  • gc_ref, gc_edge 等の一要素structで概念ごとに型を分離
    • 型ごとに適用可能な操作を限定し、誤用を防止
  • コンパイラ生成時も型安全性をCコードに持ち込める
    • WebAssemblyの型階層をCのstruct継承で再現
    • 例：type_0ref, structref, eqref等のサブタイプ構造体
    • static inline関数でキャストやフィールドアクセスを型安全に実装

memcpyの活用を恐れない

  • WebAssembly のメモリアクセスはアラインされていないことが多い
  • memcpy を使って値をロードし、最適化はCコンパイラに任せる
  • アドレスを型キャストして直接参照するより安全かつ高効率

ABIと多値戻りでの手動レジスタ割り当て

  • attribute((musttail)) でtail callが可能になったが、引数や戻り値が多い場合はCコンパイラのABI管理が不安定
  • 全パラメータをレジスタに割り当てるため、最初のn個はレジスタ、残りはグローバル変数で受け渡し
  • 多値戻りもグローバル変数経由で実現可能
  • 呼び出し側・被呼び出し側で値のロード・ストアを明示的に制御

Cをターゲットとする利点と課題

  • GCCやClang の強力な命令選択・レジスタ割り当てを享受
  • 既存のCランタイム関数との連携や最適化も容易
  • デメリット ：
    • スタック管理の自由度が低い（必要スタック量の把握や拡張が困難）
    • ゼロコスト例外処理の実装が困難（コンパイラ・ツールチェーンの支援必須）
    • ソースレベルデバッグ情報（DWARF等）の埋め込みが難しい
  • Rust をターゲットにする案もあるが、元言語が明示的なlifetimeを持たない場合はメリットが薄い

まとめと所感

  • C生成はローカル最適解 ：最小限の実装コストで高性能な出力を得やすい
  • 型安全性や抽象化 も工夫次第で十分担保可能
  • 完璧な手法は存在しないが、 生成Cの型チェックが通ればほぼ動作 する安心感
  • 現場の知見を活かし、今後も最適な生成手法を探求する姿勢

Hackerたちの意見

いくつかの実験やおもちゃを通じて、ほとんどの投稿に同意するよ。must_tail属性が主要な3つのコンパイラで信頼できるものになればいいんだけど、今のところそれは期待できないね（幸いにも、最近のClangはWindowsでかなり信頼できるみたい）。追加で2つのポイントがあるんだけど、1つ目は、記事がDWARFについて触れているけど、これがなくても#lineディレクティブを使って生成されたコードに行番号を付けられるよ（デバッグの際にすごく役立つ）。もう1つは、ローカル変数とその内容について。変数については、C++のサブセットを使うことでかなりの距離を稼げるよ（コンパイル時間に影響しないサブセット、つまりstd::名前空間のインクルードは避ける）。例えば、"root/gc/smart"ポインタなど（言語のセマンティクスによるけど）、#lineディレクティブがあればデバッガーに変数が表示されるから、「まともな」名前のマングリングが必要だね。2つ目は、Cをバックエンドにしたときの本当の痛点はGCだよ。最良のGCは通常のスタックフレームと絡み合っているから、普通のスタックウォーキングルーチンも正確なGCに必要な情報を提供するんだ（移動GC設計には必須、もっと単純な世代コレクタはそれなしでも可能だけど）。もし正確でそこそこ速いポータブルなスタックスキャンが必要なら、現在の最も理にかなった方法はシャドウスタックを維持することだね。呼び出しの際に前のフレームポインタを渡して、前のフレームポインタはフラットな配列の末尾を指すポインタで、マジックポインタと前の前のフレームポインタを前に追加して（いくつかの書き込みコストと、クリーンアップコストなしの追加引数でリンクリストを形成する）。残念ながら、パフォーマンスの良いリンクドシャドウスタックはデバッグのためにすべてのポインタを隠してしまうから、複数の名前付き変数ではなく1つの配列にまとめる必要があるし、スタック上の複雑なオブジェクトを制限されるんだ。新しいC++のリフレクションサポートを使ってシャドウスタックを利用できればいいけど、コンパイル時間が壊れないことを願ってるよ。でも、それはまた別の話だね。

└

シャドウスタックに関連して、Cの最適化ツールを納得させるのが大変だった。誰もがヒープに割り当てたヘルパースタックをエイリアスしていないと。制限アノテーションを使ってそれを伝える方法があるはずだけど、かなり面倒で、関数のパラメータにしか効かないし、いろんな理由で無視されることもある。生成されたコードで制限ポインタをうまく使ったコンパイラを知っている人いる？何か使えるものを教えてほしいな。

└

... [ポインタ]は一つの配列にまとめる必要がある... 各スタックフレームを構造体に入れて、最初のフィールドにそのフレーム内のポインタを列挙するconst static stack-mapデータ構造や関数へのポインタを持たせることができるよ。ちなみに、この構造体へのポインタは、ネストされた関数やクロージャがあるときに呼び出し関数の変数にアクセスするためにも使える。

└

これを何度か実験やおもちゃでやってみたけど、投稿のほとんどに完全に同意するよ。must_tail属性の追加が大手3つのコンパイラで信頼できるものになればいいけど、信頼できるものじゃないからね（幸い、最近のClangはWindowsでかなり信頼できるみたい）。これはバカな質問かもしれないけど、もし関数がmust tailなら、それはただのジャンプじゃないの？gotoを使えばいいじゃん？

そして最後に、ソースレベルのデバッグは厄介だよ。コードに対応するDWARF情報を埋め込めるといいんだけど、Cを生成する際にそれをどうやってやるのか分からない。生成されたコードの前に、各行に対して#line 12 "source.wasm"のようなものを出力するのが、GDBがうまく認識するための手段だと思う。

└

yaccやbisonのようなものを使ったことがあるなら、gdbでのデバッグは比較的まともだよ。y.tab.cを読めば、デバッグ可能にするためのすべてのトリックが見つかるし、変なコンパイラのためのコーナーケースも含まれている。yaccの歴史が必要ないなら、Re2cはもう少し現代的だよ。

└

NimはCにコンパイルできるし、そうするためのコンパイラオプションもあるよ。

コンパイラのターゲットとして使うための厳密なCのサブセットを定義した人はいる？理想的には、もっと規則的でシンプルな言語がいいけど、Cコンパイラを書くのは落とし穴だらけだからね。

└

正確には違うけど、C--（検索が難しい！）はコンパイラが生成するためのCに似た（またはCのサブセットの？）中間言語だった。もう少し詳しい情報が載っているRedditのスレッドを見つけたよ：https://www.reddit.com/r/haskell/comments/1pbbon/c_as_a_proj... それとプロジェクトのリンクも：https://www.cs.tufts.edu/~nr/c--/

└

例えば、https://en.wikipedia.org/wiki/C-- ってどう？

└

移植性のために、C89も希望かな？

└

LLVMが作られた理由みたいだね？（MLIRやNaCLのような派生物も）そのIRはCっぽくなるように設計されてるけど、すべてが明確で、Cよりもずっと表現力があるんだ。

└

Cの形式的意味論に互換性のあるサブセットを使うこともできると思う。KフレームワークのCの意味論や、CompCert C、VerisoftのC0とかね。あるいは、オープンソースの検証ツールでサポートされているものでもいい。そうすれば、正確な意味論と堅牢な出力を生成するためのツールが両方揃うことになる。

└

誰か、コンパイラのターゲットとして使うためのCの厳密なサブセットを定義した人はいる？理想的には、もっと規則的でシンプルな言語がいいな。Cコンパイラを書くのは落とし穴だらけだからね。Cをターゲットにする主な理由は、ポータビリティと無料のコンパイラ最適化のためだよ。新しい中間言語やCの方言を発明し始めたら、そもそもトランスパイルするメリットは何なの？自分のコンパイラバックエンドを書いて、Cではなく自分の言語の意味論に基づいて最適化した機械コードを直接出力すればいいじゃん。個人的には、Cのポータビリティと無料のコンパイラ最適化を望むなら、C89がコンパイラがターゲットにすべき厳密なサブセットだと思う。理解しやすくて、過度に複雑でもなく、過去50年間のどのアーキテクチャでも速くて理にかなった機械コードにコンパイルできるから。

インターン時代に似たようなことをやったことがあるよ。私たちは生成するCのサブセットをサポートするHaskellベースのC ASTライブラリを持っていて、デフォルトで良いフォーマットのCコードを生成するためのプリティプリントライブラリもあった。高レベルの抽象力と良い最適化を得るためには、かなり合理的なアプローチだったよ。

ヴァージルについて、結局元に戻るかもしれないな。2005年頃、ヴァージルをCにコンパイルして、次にavr-gccでAVRにしたんだ。だって、誰がAVRバックエンドなんて書きたいと思う？2009年頃には、ヴァージルIIIのために新しいコンパイラを作ったし、それ以来JVM、x86、x86-64、wasm、wasm-gc、（未完成の）arm64もサポートしてる。コンパイラのバックエンドは好きだけど、正直言って、もう飽きてきた。LLVM IRを生成することも考えたけど、ちょっと癖が強くて不安定なんだよね。ヴァージルのwasmバックエンドにはシャドウスタックがあるから、今は最初からやり直してCコードを生成しつつ、正確なGCのためにスタック上のルートを管理することができるかもしれない。うーん…。

└

参考までに言うと、LLVMのビットコード形式はテキストIRよりも互換性の保証が強いと思う。でも、どちらにしても面倒なのは同意するよ。それに、ライブラリへのリンクをやめてユーザーがインストールしている「llc」に頼ると、バグを見つけるのは楽しくない時間になるね…。

スタティックインライン関数は、時々コンパイラにとって最適化の障壁になることがある。ほんとにイライラするよ。Cをターゲットにしたコンパイルの際に、常にインライン関数に置き換えるとコード生成が悪化するケースにたくさん遭遇した。コンパイラにはバグがあるからね。あと、次の2つの式はCでは同じ意味を持たない問題もある。float v = a * b + c; と static_inline float get_thing(float a, float b) { return a*b; } float v = get_thing(a, b) + c; これはC特有の問題（浮動小数点の収束）で、常にインライン関数に抽出することがパフォーマンスに悪影響を及ぼすことがある。Cの仕様がそうなってるから、残念だよ！uintptr_tもポインタと同じ意味を持たないし。例えば、こう書くと：void my_func(strong_type1* a, strong_type2* b); では、aとbは異なるし、基底型を引き出せる。でも、こう書くと：void my_func(some_type_that_has_a_uintptr_t1 ap, some_type_that_has_a_uintptr_t2 bp) { float* a = get(ap); float* b = get(bp); } では、aがbと等しい可能性がある。セマンティクス的にはuintptr_tバージョンはエイリアスのセマンティクスを提供しない。これは、高レベル言語のセマンティクスによっては望むものかもしれないし、そうでないかもしれないけど、コンパイラがうまく最適化できないから、その違いを意識しておく価値はあるよ。

└

コンパイラのバグや仕様の欠陥は最悪だけど、もっと最悪なのは何か知ってる？コンパイラのバグやエッジケースに対する回避策が、長年にわたって広まった悲観的な知恵になってしまうこと。昔のプロジェクトの古参たちを納得させるのに、インライン関数をマクロの代わりに使えるってことを理解させるのにそれくらいかかったんだ。再び懐疑的にならないようにしたいな。

└

インライン関数はオペランドを引数として受け取るから、何であれ浮動小数点数に変換されるんだ。だから、インラインコードは実質的にこうなる：float v = (float) ((float) a) * ((float) b) + c; もし v が浮動小数点数なら、戻り値の変換を表すキャストは省略できる：float v = ((float) a) * ((float) b) + c; で、もし a と b がすでに浮動小数点数なら、これは同じことになる。でも、そうじゃない場合、もしそれらがダブルや整数なら、元のオープンコードではダブルや整数の掛け算になるよ。

└

uintptr_t と intptr_t はポインタを保持するのに十分な大きさの整数型だよ。ポインタ型ではないし（標準ではオプションでもある）。最初の my_func では、a と b が構造体のレイアウトが同じなら等しい可能性がある（あるいは、一方がもう一方のフィールドの適切なサブセットを同じ順序で持っている場合）。コンパイラに重複しないことを伝えるためには、(strong_type1 *restrict a, strong_type2 *restrict b) を使う。ポインタが同じアドレスを指しているけど等しくない可能性もあるよ。例えば、LAM/UAI/TBIが有効になっている場合、単純なポインタの等価比較では不十分だ。なぜなら、高ビットが等しくないかもしれないから。あるいは、メモリアクセスが常にアラインされているプラットフォームでは、低ビットが等しくないこともある。これらのビットは、ポインタに追加情報をタグ付けするために使われることがあるんだ。

ジェネレーターはポータブルなコードを出力する必要はないよ。出力に必要なコンパイラを文書化して、それはジェネレーターのリリースごとに変更できるものだから。生成されたコードは、そのコンパイラで動くものを使う。もし他のコンパイラでその出力を使ったら、それはジェネレーターの文書に対して未定義の動作になるから、自分で何とかしないと。「動くものなら何でも」ってのは、実際には動くけど文書化されていないことかもしれない。

ZigがILRになったらどうなるんだろう。簡単にクロスコンパイルできるし、ランタイムチェックを使ってコンパイラの出力をデバッグするのに役立つかも。サイドプロジェクトとして面白そうだね。

自分はCプログラマーじゃないんだ。過去20年間は高級言語だけでコーディングしてきたから。でも最近WASMをたくさんやってて、async/await機能のためにasincify型の変換を実装しなくて済むように、スタック切り替えの提案を楽しみにしてる。Cプログラムがスタックを制御できないって本当なら、Wastrelでのスタック切り替えをサポートするのはどういうことになるのかな？サスペンドされた非同期関数からスタックを再具現化して別のものに置き換えることはできないの？WASMスタック切り替えをサポートするなら、すべてのスタックにユーザーランドスタックが必要になるのかな？