Kefir: C17/C23 独立コンパイラ

概要

Kefir は、Jevgenij Protopopov によって開発された、C17/C23 プログラミング言語のための独立したコンパイラです。Kefir の実装正当性は、GNU coreutils や binutils、Curl、Nginx、OpenSSL、Perl、Postgresql、Tcl など、100 ソフトウェアプロジェクトに及ぶテストスイートで検証されています。このコンパイラは x86_64 アーキテクチャと System-V AMD64 ABI を対象とし、Linux、FreeBSD、NetBSD、OpenBSD、DragonflyBSD のプラットフォームをサポートしています。本プロジェクトは、SSA ベースの最適化パイプライン、デバッグ情報の生成、位置独立型コード（PIC）サポート、ビット同値なブートストラップ機能などを備えた、รอบอบถ้วน で互換性があり規範準拠したコンパイラを提供することを意図しています。Kefir はアッセンブラー、リンカー、共有ライブラリなど、システムツールチェーンの他の構成要素と統合されます。

特徴

Kefir の主な特徴は以下の通りです：

• C17 標準準拠: C17 標準をサポートします。複素数や虚数、アトミック演算子、変長配列などの機能を含まれます（実装の詳細については「実装上の peculiarities」を参照）。
• C23 標準準拠: C23 標準をサポートします。ビット単位表現の整数（Bit-precise integers）および

  _Decimal

  フローティングポイント数のサポートを含みます（実装の詳細については「実装上の peculiarities」を参照）。
• GNU エクステンション: 一般的な GNU C のインリンブートイン関数、特定のエクステンション、インラインアッセンブラーコード、128 ビット整数などの一部をサポートします。
• 実装言語: C11 で書かれています。ランタイム依存は標準ライブラリ、POSIX の一部、シェルまでを限定しています。
• アーキテクチャ: 主に x86_64 アーキテクチャと System-V ABI を対象としています。主に Linux（glibc および musl libc）をサポートし、其次に FreeBSD、NetBSD、OpenBSD、DragonflyBSD に対応します（サポート環境を参照）。
• 検証: リアルワールドのオープンソースソフトウェアのテストスイートにおいて徹底的に検証されています。複数のよく知られたプロジェクトが含まれます（テストと検証を参照）。
• 最適化: SSA ベースの最適化パイプラインを実装しており、2 つの SSA フェーズを持っています。主にローカルスカラーを扱いますが、以下のような機能を提供します：ローカル変数のレジスタへのプーミング、デッドコード排除、定数畳み込み、グローバルバリューナンバリング、ループ不変式コード移動、関数インライン化、テールコール最適化など。また、保守的なグローバルメモリアクセス最適化やターゲット固有の最適化も提供します（最適化とコード生成を参照）。
• デバッグ情報: DWARF5 デバッグ情報をサポートし、位置独立型コード、GNU As の AT&T および Intel シンタックスに対応しています。Yasm には部分的な対応があります。
• ブートストラップ: ビット同値なブートストラップを実装しています。一定の環境下では、Kefir は自身のコピーを生成します。
• スタンドアロンコード（Freestanding Code）: スレッドローカルストレージ（ABI による外部コールが必要な場合あり）、

  _Decimal

  フローティングポイント数、プラットフォーム固有サイズではないアトミック演算子（libatomic-compliant ライブラリが必要）を除く、フリースタンディングアッセンブラーコードの生成が可能です。
• インターフェース: cc 互換のコマンドラインインターフェースを提供します。
• 中間出力: マシン可読な JSON 形式で内部表現（トークン、抽象構文木 AST、中間表現）を出力できます。
• 監査機能: プレビューリリースのテストのために、検証可能なログとすべてのビルドアートを提供します。
• ライセンス: コンパイラ本体は GNU GPLv3 のみ（ランタイム含めは BSD-3 クロース）、それぞれのライブラリについては LICENSE ファイルを参照してください。
• 作者性: 単一の開発者によって書かれています。
• 命名: 発酵ミルク飲料にちなんで名付けられています。他の比喩的な意図はありません。

重要な注意事項

1. このプロジェクトは単一の個人により、資金も不足しており余暇時間に開発・維持されているため、著者は生産環境での Kefir 使用が望ましくないかもしれないという警告を発しています（著者が提供できるサポートの不足分によるものです）。
2. 著者の知る限り、上記のすべての主張是真的です（多くの項目はテストスイートによって再現可能に証明されています）。しかし、いかなる慎重さをもってしても、バグ、意図せずした欠落、不一致、または誤解が混入する可能性があります。著者はプロジェクトの能力を誠実に表現することに努め、この点での誇張に対して特に敏感です。上記内容に疑義、異議や不同意がある場合は、著者に連絡することを躊躇しないでください（作者と連絡先を参照）。欠陥が特定された後には、即座に訂正が発行されます。

---

インストールと使用方法

サポートされているプラットフォーム上で、Kefir は以下の手順でビルドおよびテストされます：

make test all                  # Linux glibc 用
make test all USE_SHARED=no CC=musl-gcc KEFIR_TEST_USE_MUSL=yes   # Linux musl 用
gmake test all CC=clang        # FreeBSD 用
gmake test all CC=clang AS=gas # OpenBSD 用
gmake test all CC=gcc AS=gas   # NetBSD 用
gmake test all LD=/usr/local/bin/ld AS=/usr/local/bin/as # DragonflyBSD 用

インストールは、

(g)make install

コマンドを実行し、

prefix=....

オプションを指定することで完了します。デフォルトのプレフィックスは

/opt/kefir

です。

ビルド依存関係

Kefir のビルディング時の依存関係：

• C11 コンパイラ（gcc と clang でテスト済み）
• Bash
• GNU Make
• GNU Coreutils
• Groff
• m4
• mandoc

Kefir のランタイム依存関係：

• C 標準ライブラリと POSIX
• シェル

さらに、エンドツーエンドの正しいコンパイルを遂行するために、Kefir は以下を必要とします：

• 外部アッセンブラー（GNU As への完全サポート、Yasm への部分的サポート）
• 外部リンカー（GNU ld）
• 外部 libc（Linux では glibc または musl libc、*BSD システムではシステム標準の libc）。注：これは Kefir 自身がリンクする libc と異なる場合があります。
• 外部スタートファイル（

  crti.o

  、

  Scrt.o

  など）
• libatomic-compliant ライブラリ（gcc の libatomic、または clang の compiler_rt など）
• libgcc（小数点以下を含む浮動小数点数サポートが必要な場合）

必要となる環境は、

dist/Dockerfile*

ファイル（Ubuntu (base target)、Fedora、Alpine 向け）、および Arch Linux 向けの

dist/PKGBUILD

ファイルを参照してください。*BSD システムについては、該当する

.builds/*.yml

ファイルを参照してください。

注： ビルド時に Kefir はホストシステムのツールチェーン（アッセンブラー、リンカー、ヘッダーおよびライブラリパス）を検出し、それに応じて構成します。ツールチェーンを更新した後の場合は、

kefir-detect-host-env --environment

コマンドを実行し、その出力を

$(prefix)/etc/kefir.local

ファイルに配置してください。

注 #2： 上記の依存関係には、オプションの開発および完全なテストスイートの依存関係は含まれません。これらについては

dist/Dockerfile.dev

および

full

ターゲットを参照してください。

現時点では、Kefir は Ubuntu 24.04、FreeBSD 14.x、OpenBSD 7.7、NetBSD 10.x の環境で自動的にテストされています。Arch Linux が主要な開発環境として使用されています。DragonflyBSD のサポートはリリース前に手動でテストされます。

小数点浮動小数点数サポート

Kefir は、libgcc の算術ルーチンに依存した

_Decimal

浮動小数点数数のサポートを提供します。このサポートを有効にするには、ホストコンパイラとして gcc を使用して Kefir を直接または間接（すなわちブートストラップ）ビルドする必要があります。Kefir によって生成された小数点算術コードは libgcc とのリンカ結合を必要とし、ビット単位表現の整数と小数点浮動小数点数数之间的変換を希望する場合は、バージョン 14 またはそれ以降の libgcc が求められます。

両方の BID および DPD エンコーディングがサポートされており、BID がデフォルトです。DPD を有効にするには、Kefir をビルドする際の次の Make オプションを渡してください：

EXTRA_CFLAGS="-DKEFIR_PLATFORM_DECIMAL_DPD"

Kefir は libgcc バージョン 4.7.4 を自動的にブートストラップできます：

make bootstrap_libgcc474 -j$(nproc)

Libatomic

Kefir は、compiler_rt プロジェクトから必要な libatomic ルーチンをビルドできます：

make build_libatomic -j$(nproc)

使用方法

Kefir は cc 互換のコマンドラインインターフェースを実装しているため、標準的なコンパイルパイプラインにおける

cc

の近似的なドロップイン置き換え（実装上の peculiarities を参照）として使用できます：

which kefir # インストール後には、kefir の正しいパスが出力されるはずです

使用例

kefir -O1 -g -fPIC -o hello_world ./hello_world.c
./hello_world

さらに、Kefir はコマンドラインオプションと環境に関する考慮事項を文書化したマニュアルページを提供します：

man kefir # インストールディレクトリが man の検索範囲に含まれていることを確認してください
kefir --help # マニュアルページのコンテンツと同等です

ポータブルな Kefir

Kefir は、Linux 用のポータブルでスタンドアロンの Kefir ディストリビューションパッケージをビルドするためのスクリプトを提供します。このパッケージには、静的にリンクされた Kefir C コンパイラ、musl libc、および GNU Binutils から選択されたツールが含まれます。このパッケージは、ホストシステムのツールチェーンに依存しない最小限の C 開発ツールチェーンの提供を意図しています。

make portable_bootstrap -j$(nproc)
# ビルドアータは bin/portable/kefir-portable-*.tar.gz に配置されます

サポートされている環境

Kefir は x86_64 命令セットアーキテクチャと System-V AMD64 ABI を対象としています。サポートされているプラットフォームには、Linux（glibc および musl libc）、FreeBSD、OpenBSD、NetBSD、DragonflyBSD の最新バージョンが含まれます。

プラットフォームが「サポートされている」とみなされる条件は以下の通りです：

• Kefir をシステムコンパイラでビルドでき、かつ自分のテストスイートを実行できること。
• Kefir を自分自身でビルドでき、かつ自分のテストスイートを実行できること。
• Kefir が c-testsuite および gcc-torture テストをパスすること（詳細は Testing and validation 節を参照）。
• Kefir で Lua をコンパイルでき、かつその基本テストスイートを成功させることができること。
• 固定された環境内で自分自身を再現可能に（すなわちビット同値なブートストラップ）構築できること。

プラットフォームが「サポートされている」と主張するためには、他の要件は課されません。Testing and validation セクションで記述されている他のテストと検証は、主に Linux で行われるものであり、全体的なコンパイルプロセスの正当性を確保することを目的としています。一般的に、Linux と BSD システム間のコード生成には非常に大きな違いはありませんため、完全なテストおよび検証シーケンスは単一のプラットフォームだけで十分です。libc ヘッダーの peculiarities が互換性の主な要因であることに注意してください。そのため、追加のマクロ定義や個別のヘッダーオーバーライドが必要になる場合があります。musl libc は最も滑らかな体験を提供しますが、Kefir は GNU C エクステンションへの十分なサポートを有しており、glibc および BSD libc の実装も合理的に使用可能です（詳細は Implementation quirks および Testing and validation の外部テストスイート部分、および所望のプラットフォーム用の respective

.build/*.yml

ファイルを参照）。

Installation セクションで述べた通り、Kefir はビルド時にシステムツールチェーンの設定を検出し、後にそれを使用します。コンパイラは、組み込み設定よりも優先される環境変数のセットもサポートしています。支持されている環境変数の詳細については、マニュアルページの関連セクションを参照してください。

標準ライブラリの考慮事項

• Linux 上: Kefir は glibc および musl libc の両方で動作します。musl ヘッダーはより標準準拠であり、一般的に滑らかな互換性を提供します。一方、glibc はメインストリームのコンパイラ以外のものに互不相容な問題を導入する可能性があります（Implementation quirks を参照）。
• FreeBSD, OpenBSD, NetBSD 上: システム標準ライブラリを使用できますが、ビルドの成功のために追加のマクロ定義（例：

  __GNUC__

  、

  __GNUC_MINOR__

  ）が必要になる場合があります。

実装上の peculiarities (Implementation Quirks)

以下の詳細には注意を払う必要があります：

1. C23 浮動小数点数: Kefir の C23 標準実装は、libgcc ルーチンに依存した

   _Decimal

   浮動小数点数数のサポートを提供します（Installation and Usage を参照）。
2. 文字型: C23 標準では、

   char8_t

   、

   char16_t

   、および

   char32_t

   タイプとリテラルに対して Unicode の使用を義務付けています。Kefir は標準ライブラリのワイド文字エンコーディング機能に依存するため、この要件はシステムローカールがUnicode ベースであることを条件として実装されます。著者はこれが合理的な仮定であると信じています。
3. C17 と C23 への信頼度: 一般的に、著者は C17 および以前のバージョンの機能との互換性に対してはるかに高い信頼を持っています。現在の外部テストスイート（Testing and validation を参照）における絶対的な大多数のサードパーティプロジェクトが C23 の機能を依存していないため、C23 サポートの外部検証は大幅に制限されています。このため、著者は C23 標準に含まれる変更を誠実に読み込み、良心と尽された能力の範囲内でそれらを実装したことを断言します。
4. glibc peculiarities: Linux 上の glibc では、ライブラリがメインストリームのコンパイラにおける特定の機能を壊すコーナーケースが存在します。例えば、glibc は

   __attribute__

   スペシフィケーションを空のマクロで上書きし、packed エイトリビュートなどを省略することで、Kefir がサポートしているにもかかわらず互不相容な状態を引き起こします。Kefir インストールには

   <sys/cdefs.h>

   ヘッダー向けの shims ヴァッパーが含まれており、最も顕著な問題を修正しますが、完全な互換性は保証できません。著者は、外部テストスイートのプロジェクトビルド構成について理解することを推奨します（Testing and validation を参照）。
5. アトミック演算子: アトミック演算子は主に、指定されたメモリ順序にかかわらずシーケンシャルリソースセマンティクスを実装しており、ネイティブスカラーアトミックストアを除いてはリリースおよび seq_cst セマンティクスを区別しません。この動作は安全であり、ソフトウェアを壊さないはずです。ネイティブサイズではないアトミック演算子は、外部ソフトウェアアトミックライブラリ（gcc の libatomic または clang の compiler_rt）に依存します。Kefir は musl libc を除くすべての構成で、結果の実行ファイルを自動的にこのライブラリとリンカ結合します。さらに、Clang の

   <stdatomic.h>

   システムヘッダーを使用する場合は、

   -D__GNUC__=4 -D__GNUC_MINOR__=20

   コマンドライン引数を必要とします。
6. Long Double Atomic:

   long double

   変数（スカラーおよび複素数の両方）に対するアトミック演算子を使用する場合は、各

   long double

   ストレージユニットの最後の 48 ビットが未初期化である可能性があるため注意が必要です。Kefir は、この問題の可能性を軽減するために未初期化のパディングへのゼロ化を実装しています。
7. ブートイン完備性: ホスト C 標準ライブラリへの依存は、Kefir が標準ライブラリヘッダーに出現するあらゆるブートインまたはコンパイラエクステンションを実装することを意味します。著者は多数のブートインをコンパイラに導入しましたが、その完全性は保証できません。サポートされているプラットフォーム上で標準 C ライブラリ関数が欠けているブートインやエクステンションのために使用できない場合、これはバグとして扱われます。
8. 標準ドラフト: すべての関連する C 言語標準のバージョンは、実質的なコストしか公式に入手できません。コンパイラを開発する際、著者は公開されている標準のドラフト（Useful resources and links を参照）に基づいていました。これらのドラフトが最終標準と矛盾する部分があれば、著者は具体的な詳細を知りたいと考えています。

実践的な観点 (In Practice)

Kefir ユーザーが必要な考慮事項：

1. パフォーマンス: Kefir は、GCC や Clang のような確立された主要コンパイラとは生い立ちのパフォーマンス、ポータビリティ、または広範さにおいて直接競争することはできません。Kefir プロジェクトの目的は、単一の開発者が実装可能で、C17/C23 コンパイラとしての明確なアーキテクチャと定義された範囲を持つ独立したコンパイラを生成することです。
2. 最適化の機会: 特に生きたパフォーマンスに関する点では、Kefir はよりパフォーマンス志向プロジェクトに劣る場合があります。著者はいまだにレジスタ割り当て、最適化パス、命令選択、スケジューリングなどで多くの低懸垂の果実を見ていると考えます。
3. GNU C 互換性: GNU C 互換性の観点からは、Kefir は実用的に有用であるために十分な数のエクステンションとブートインを実装しています。ブートインの詳細なリストは

   source/tests/end2end/supported_builtins1/lib.asmgen.expected

   で利用可能です。
4. 置換能力: 特定の peculiarities（Implementation quirks を参照）を考慮した上で、Kefir はホスト C コンパイラの近似的なドロップイン置き換えとして使用でき、多くの有名な C プロジェクトをコンパイルして成功裏に実行できることが Testing and validation で示されています。
5. 標準準拠: C17/C23 互換性の観点からは、著者の意図は言語標準への近いまたはほぼ完全な準拠です。Implementation quirks で文書化されていない振る舞いの変化はコンパイラのバグとして見なされます。

テストと検証

オブンステストスイート

Kefir コンパイラ独自のテストスイートは、プロジェクトのコードベースの一部として著者によって維持されています。一般的なルールとして、コンパイラーで行われたあらゆる変更をカバーするように、独自のテストスイートを拡張します。既存のテストが既にその変更をカバーする場合や、変更を合理的にテストできない場合（特定のバグを再現するには禁止的ほど長いケースが必要な場合など）には例外があります。

独自のテストスイートは以下のカテゴリのテストを含みます：

• 部分的なテスト: 個別のコンポーネント、サブシステム、またはサブシステム組合せを演じます。手作業による初期化に依存します：
  • ユニットテスト: Kefir はカスタムのユニットテストライブラリを実装しています。
  • 統合テスト: 個別のサブシステムをテストするためにスナップショットテスト技術（すなわち、期待される出力との比較）を使用します。
  • システムテスト: Kefir サブモジュールを初期化してアッセンブラーコードを生成し、ホスト C コンパイラによって構築された対応するモジュールで組み立ておよびリンカ結合します。対応するモジュールは Kefir 出力をテストするためのハスネスを提供します。
• エンドツーエンドテスト: 完全なコンパイラーパイプラインをカバーしており、

  *.kefir.c

  および

  *.host.c

  モジュールのセットで構成されています。これらはそれぞれ Kefir とホスト C コンパイラによって構築され、互いにリンカ結合されて実行されます。通常、ホストモジュールはシステムテストと同様に Kefir をテストするためのハスネスを提供します。オプションで、エンドツーエンドテストはスナップショット（asmgen）テストを含むことも可能です。

CSmith によって生成された選択的なテストケースも、エンドツーエンドテストスイートに含まれています。

歴史的には、コンパイラーパイプラインが完了する前は主に部分的なテストに依存していましたが、現在は新しい作業の大半は主にエンドツーエンドテストで検証されています。

Linux glibc および FreeBSD プラットフォーム上の継続的インテグレーション環境では、独自のテストスイートは Valgrind および未定義振る舞いサンタイザーと共に実行されます。さらに、すべてのサポートされたプラットフォームで、Kefir がホストコンパイラとして動作する特別な「自己テスト」ランを実行します。プラットフォーム固有の独自テストスイート実行の詳細なセットアップについては、

.builds

ディレクトリの

ubuntu.yml

、

ubuntu-musl.yml

、

ubuntu-self.yml

、

freebsd.yml

、

freebsd-self.yml

、

openbsd.yml

、

netbsd.yml

を参照してください。

ブートストラップテスト

すべてのサポートされたプラットフォームで、Kefir は再現可能なブートストラップテストも実行します：

1. ステージ0: Kefir はホスト C コンパイラによって通常通りビルドされます。
2. ステージ1: ステージ0 の kefir が自身をビルドしてステージ1を生成します。すべての中間アッセンブラーリストは保持されます。
3. ステージ2: ステージ1 の kefir が自身をビルドしてステージ2を生成します。すべての中間アッセンブラーリストは保持されます。

ステージ1とステージ2からのアッセンブラーリストは同一であるべきです。さらに、ブートストラップテストが成功するためには、ステージ1とステージ2からの kefir 実行ファイルおよび libkefir.so ライブラリの sha256 チェックサムも同一である必要があります。

ブートストラップテストは固定された環境内（すなわち、標準ライブラリ、アッセンブラー、リンカーのバージョンはテスト中に変更されません）で実施され、Kefir が自身を同様のコピーを生成できることを示しています。Ubuntu 上では、GNU As および Yasm をターゲットアッセンブラとして使用してブートストラップが行われます。プラットフォーム固有のブートストラップテスト実行の詳細なセットアップについては、

.builds

ディレクトリの

ubuntu-other.yml

、

ubuntu-musl.yml

、

freebsd.yml

、

openbsd.yml

、

netbsd.yml

を参照してください。

実践的な観点から、Kefir は自身を CC コンパイラとして指定することでブートストラップできます：

make CC=$(which kefir) -j$(nproc)

この形式的なブートストラップは再現性を検証せず、単にコンパイラを自分自身を使用して再構築します。

ポータブルブートストラップ

Installation セクションで記述されたポータブル Kefir ブートストラップ手順は、追加のテストとしての役割も果たします。このポータブルブートストラップはビット単位表現の再現性チェックを省略しますが、各ステージで完全なツールチェーン（musl libc、GNU As、GNU ld）の反復的な再ビルドを実行します。したがって、Kefir が自己完結型開発環境を生産する能力を保証します。

c-testsuite および gcc-torture スイート

すべてのサポートされたプラットフォームで、Kefir は以下の外部テストスイートを実行します：

• c-testsuite: より小さいテストスイートで、テストケースをコンパイルして実行し、その出力を期待されるスナップショットと比較するものに依存しています。220 のテストのうち、3 つのテストファイルは非標準エクステンションに依存しておりスキップされ、残りはパスするはずです。
• GCC Torture スイート: gcc 15.2.0 からインポートされたテストスイートで、自己テストのアサーション形式で実行される個別のテストケースのセットを構成しています。このテストスイートは gcc の特定の機能に大きく依存しているため、より多くの失敗が予想されます。現在のバージョンでは、3663 のテストのうち Kefir は 429 を失敗させ、29 をスキップします。ターゲットプラットフォームとハードウェアパフォーマンス（強制された 10 秒のタイムアウトのため）によっては、失敗するテストの正確な数がわずかに異なることに注意してください。報告された数は Ubuntu glibc におけるベストケースの結果です。さらに、テストが成功するためには、実行時またはコンパイル時において致命傷、中止、セグメンテーションエラー、またはキャッチされたシグナルによって引き起こされる失敗は一つもない必要があります。
• GCC テストスイート _BitInt bits: C23 標準からのビット単位表現の整数の正しい実装を確保するための、gcc 15.2.0 からインポートされた 71 のテストの別々のセットです。このスイートのすべてのテストは成功裏に実行されるはずです。

Lua 基本テストスイート

すべてのサポートされたプラットフォームで、Kefir は Lua 5.4.8/5.5.0 をビルドし、その基本テストスイートを実行し、完全にパスさせるように設計されています。このテストの目的は、Kefir がターゲットプラットフォーム上で非自明なソフトウェアを成功裏に構築できることを示すことです。技術的には、これは外部テストスイートの一部（以下を参照）であり、歴史的な理由から一般的なテストランへの含め込みがなされました。

フッズティング

リリース 0.5.0 以降、Kefir のテスト規律は、ナイトリーテストスイートランの毎回の夜に 20,000 つのランダムに生成された csmith ケースを含むように拡張されています。これまでのところ、Kefir は少なくとも 2,500,000 件のランダムテストを成功裏にパスしました。テストは gcc に対する差分（differential）です --- kefir および gcc の両方で与えられたタイムアウト以内にコンパイルおよび実行できるすべてのテストケースについて、出力が同一である必要があります。すべての失敗するケースは修正され、独自のテストスイートに追加されます。

外部テストスイート

これは、Kefir を使用してビルドされ、その後の検証が行われる 100 のサードパーティオープンソースプロジェクトのスイートです。大半のプロジェクトでは、そのテストスイートが実行されます；これが不可能な場合はカスタムスモークテストが実施されます；少数については、成功裏なビルドの事実が十分と考えられています。

外部テストスイートの目的は：

1. Kefir コンパイラの実装正当性とリアルワールドでの適用可能性を確立すること。
2. GNU binutils、coreutils、Ruby、Python、Perl、OpenSSH、OpenSSL、zsh など、多くの有名なソフトウェアプロジェクトをコンパイルし、Kefir の能力を示すこと。
3. 開発サイクル中の退化（regression）を追跡すること。外部テストスイートは十分に多様であり、潜在的な退歩に対して敏感であり、新しく導入された欠陥を素早く浮き彫りにします。これにより、著者は問題を迅速に解決し、自信を持つことができます。
4. Linux glibc でリアルワールドソフトウェアを Kefir で構築する際に生じる課題の解決を文書化すること。そのような課題には、glibc 関連の問題の緩和、ビルドシステム仮定の修正などがあります。

Lua を除いて、外部テストスイートは

dist/Dockerfile

で定義されたように Linux glibc 環境で排他的に実行されます。その主な理由はリソース制約です。外部テストスイートの実行は完全に自動化されています：

make .EXTERNAL_TESTS_SUITE -j$(nproc)
make .EXTERNAL_EXTRA_TESTS_SUITE -j$(nproc) # zig-bootstrap 用のみ、下記を参照

外部テストスイート（zig-bootstrap を除く）は、現在の Kefir 開発バージョンおよびリリース前の段階で毎日に実行されます。バージョン 0.5.0 からは、外部テストスイートに含まれるすべてのサードパーティソフトウェアのソースアーカイブが、プロジェクトのウェブサイトのリリース検証セクション下に公開され、再現性と完全性の目的のためにミラーリングされます。デフォルトでは、すべての外部テストは依然として元のアップストリームリンクを使用してサードパーティソフトウェアソースを使用していますが、これらはオプションでアーカイブバージョンに置き換えることができます。Kefir は、アップストリームリンクをアーカイブへ透明なリダイレクトに必要なスクリプトを提供します。

制限

一般的に、ソースコードの大半は「ありのまま」ビルドおよび実行されますが、多かれ少なかれ（glibc peculiarities を回避する、ハードコーディされたコンパイラ仮定を修正する、異端的な非標準イディオムを置き換える、意図的に抑制されたテストケースを無視するなど）パッチが適用される可能性があります。

著者は以下の原則を確立しました：あらゆるそのようなパッチは自明で極めて小さく、非自明な変化は決して考慮されません。

あるプロジェクトの個別のテストケースが抑制される可能性があります。その理由は通常、コンパイラまたは環境について過剰な仮定があるか、著者が不安定性の正確な理由に確信がない場合があります。しかし著者の見積もりによれば、>99% の個別のテストは変更なしで成功裏にパスします。

このサイズのテストスイートには自然に若干の不安定性（flakiness）が現れる可能性があります。一部の日常ビルドでは、コンパイラの変更とは無関係であるが、ネットワーク失敗、カレンダー日付の変化、CPU スロットリングおよび関連する遅延（特定のテストはタイミングに依存する）などの理由による失敗を観察しました。そのような失敗は通常ワンショットで、繰り返し観察されることはありません。異なるハードウェア上でスイートを実行することで、著者が観測しなかったいくつかの失敗が浮き彫りになる可能性があります。

著者は、上述の制限が外部テストスイートの目的と有用性を損なわないと考えています。

外部テストスイートの構造

外部テストスイートに含められるソフトウェアは、以下の通り広範にグループ化できます。提供されたソフトウェアリストは網羅的ではありませんので、完全な詳細と具体的なバージョンについては

source/tests/external

を確認してください。一般的なルールとして、著者は Kefir のリリース前にはほとんどのパッケージのアップグレードを行います。

• 広く使用されているソフトウェアパッケージ: GNU Bash, Binutils, Bison, Coreutils, Curl, GNU Awk, Git, Guile, Gzip, ImageMagick、expat/gmp/jpeg/png/uv/xml2 などのライブラリ、Lua, GNU Make, Memcached, Musl, Nano, Nasm, Nginx, OCaml, OpenSSH, OpenSSL, PCRe2, Perl, PHP, PostgreSQL, Python, Redis, Ruby, SQLite, tar, Tcl, Vim, Wget, xz, zlib, zsh, zstd、およびその他のもの。これは最大のグループで、上記のすべての目的（正当性、退化追跡、リアルワールドビルド能力と課題の文書化）に役立ちます。GCC 4.0.4 のブートストラップ手順もこのグループに属します。
  • zig-bootstrap は技術的にはこのグループにも属しますが、不合理な CPU タイムとメモリ要件のため、頻繁には実行されません。
• 問題固有のソフトウェア: c23doku, jtckdint および C23 の初期採用者のいくつか。このグループの主な役割は Kefir の特定の側面をテストすることです（例：jtckdint 用のチェックされた算術ブートイン、他者用の C23 機能サポート）。
• "相互"プロジェクト: hummingbird, libsir, oksh, slimcc, tin。これらは Kefir の存在を何らかの方法で認めたプロジェクトで、しばしば早期にです。奉仕の証として、これらは外部テストスイートに含まれています。

ナイトリーおよびリリース前テストラン

ナイトリーおよびリリース前テストランは主に Linux プラットフォームで一致しており、

scripts/pre_release_test.sh

スクリプトによって符号化されており、上記のすべてのステージを含んでいます。このスクリプトは

dist/Dockerfile

で定義された環境で実行されます。さらに、ナイトリーランには

.builds

ディレクトリからランダムにサンプリングされた少なくとも 4 つの CI マニフェストが含まれます。リリース前ランは追加の要件を課します：

• .builds

  ディレクトリからのすべての CI マニフェストを実行しパスする必要があります。

• .builds/dragonflybsd.sh

  スクリプトで指定された DragonflyBSD テストがパスする必要があります。

• dist/Dockerfile

  で指定された環境での zig-bootstrap テストがパスする必要があります。

scripts/pre_release_test.sh

規律には、glibc および musl gcc/kefir ホスト、clang ホストのすべての構成を含む独自のテストスイート、glibc および musl libc を持つ GNU As と Yasm ターゲットのすべての構成を含む再現可能なブートストラップテスト、ポータブルブートストラップラン、外部テストスイートの実行（zig-bootstrap を除く）が含まれます。

• ナイトリーテスト: コードベースへのあらゆる変更時に実行され、毎日バッチ化されます。共有プロセッサ VPS で以下の仕様を使用：AMD EPYC Rome CPU（4 コア）、8 GB の RAM および 8 GB のスワップ。
• リリース前テスト: マスターブランチへのすべてのマージ時、すなわちリリースタグ付けと一致する時間に実行されます。

リリース前テスト

バージョン 0.5.0 から、Kefir の各リリースは以下のアーティファクトが付属します：

• scripts/pre_release_test.sh

  の全ランの完全なログが保存され、公開されます。さらに、外部テストソースのアーカイブと、テスト実行環境およびすべてのビルドアータと中間ファイルを有するコンテナイメージが含まれます。
• zig-bootstrap 外部テストは、別のマシンと同じ環境で実施されます。完全なセットのログとコンテナイメージも公開されます。

• .builds

  ディレクトリからのすべての継続的インテグレーションマニフェストのための SourceHut ビルドサービスによって生成されたログのセット。これらのビルドには、Supported environments セクションで概説した要件に準拠して Linux、FreeBSD、OpenBSD、NetBSD のテストランが含まれます。

すべてのアーティファクトは、Kefir ウェブサイトでリリースソースコードと共に監査可能な形式で公開され、著者の PGP キーで署名されます。

最適化とコード生成

中間表現

Kefir は AST からコード出力までの間に複数の中間表現を持つコンパイルパイプラインを構成しています。

パイプラインは抽象化レベルによって分割され、3 つの部分に構成されています。ターゲット独立部分には、同じ実行セマンティクス（コアセットのオペコード）を共有するが制御およびデータフロー表現が異なる高級な表現が含まれます：線形スタックベースIR と構造化された最適化 SSA（メモリ SSA は補完的であり、いくつかの最適化パスの一部として最適化 SSA から派生します）。ターゲット固有部分はさらにリソース管理戦略に基づいて分割されます：バーチャル表現はタイプと割り当て制約で特徴付けられた仮想 CPU レジスタを使用し、一方で物理的 3AC は実際のレジスタ名をエンコードします。ターゲット固有部分にも、同じ実行セマンティクスを共有する異なる制御およびデータフロー形状の表現が含まれます。

哲学的には、Kefir の最適化パイプラインは 2 つの次元（抽象化レベルと関心事）に沿って構成されています。抽象化レベルは、特定の時点で利用可能なソース言語とマシーン固有情報の度を定義し、利用可能な演算とデータ型のセットを指定します。関心事は、特定の中間表現の存在意義（executable か analytical か）を定義し、したがって制御およびデータフローの形状、それが述べた目的のために役立つことを指定します。核となるアイデアは、実行可能 IR（スタックベースと 3 アドレスコード）は適切なアーキテクチャの（仮想）マシーンによって直接実行できる合理的な運用セマンティクスを持つべきであり、一方で解析表現は分析およびトランスフォームに適していることです。さらに、Kefir は同じ抽象化レベルを共有する IR ファミリー間の硬い境界を強制し、各ファミリーが自己完結しており、プログラムのセマンティクスを表すのに必要なすべての情報を保持することを確保します。各ローリング境界は下位のファミリーの実行可能形式を対象とするため、適切な制御およびデータフロー構造を構築する必要から解放された単純な手続き的ローリングが可能になります。したがって、Kefir の最適化パイプラインは 2 次元空間での縦横ジグザグ形状として想像できます。

このような設計哲学は、流行の近代的アプローチ（例：MLIR）と矛盾するかもしれません。著者はこの構造を、以下の要件を満たすのにより適しているとして動機付けます：

• 拡張性: 実行可能形式と解析形式間の意図的な分離は、早期コード出力を可能にします。これにより、コンパイラ構築の初期段階でのフィードバックループが早められます。Kefir プロジェクトの進化はこのパターンに従います：コンパイラの早期バージョンはスタックベース IR を実際の運用モデルとして使用してスタックベーススレッドコードを生成し、後続に追加された最適化 SSA および 3AC が元のバックエンドを置き換え、ターゲットIR は 3AC のdevirtualization から発展して最終的な開発となりました。
• デバッグ性: 各抽象化共有 IR ファミリーは、プログラムセマンティクスを表すための完全なプライムプリズムを提供し、トランスフォーム/ローリング問題の素早い分離と各段階についての推論を可能にします。著者は、同じパイプライン内で複雑な法律化ルールを持つ異なる抽象化レベル（dialects）を混合するアプローチは、特定の時点で利用可能な操作とプログラムセマンティクスについての理解を悪化させ、dialects 間で同等の操作の重複を引き起こすことを発見しました。Kefir パイプラインでは、法律化は主に IR ファミリー間のローリングと一致します。
• 拡張可能性: 各個別の中間表現は、拡張およびプラグインを追加するための独立した安定ターゲットとして機能できます。各拡張は、必要な抽象化レベルにおけるプログラムの一貫した完全なビューを提供し、拡張ポイント以前または以降の利用可能な操作とトランスフォームパスを心配する必要がありません。現在の Kefir はフロントエンド外での拡張メカニズムを提供していませんが、原則として現在の設計内でそのような統合が可能 です。
• 柔軟性: 一見矛盾するようですが、著者はこのコンパイルスキームがより柔軟であるとみなします。これは、各抽象化レベルのセマンティクスを定義するだけでなく、正確なトランスフォームパイプライン構造への前もったコミットメントを必要としません。各抽象化ファミリーのトランスフォームは自由に再配置および再構成でき、各抽象化が豊かで利用可能な操作のセットを持つプログラムの一貫したビューを提供するためです。これらの操作はレベル内のあらゆるトランスフォームの基盤として機能します。

スタックベース IR

スタックベース IR は実行可能モジュールの完全な表現です。実行コードに加えて、シンボル情報、タイプおよび関数シグネチャ、グローバルデータ定義、文字列リテラル、インラインアッセンブラーフラグメントを含みます。実行観点から、スタックベース IR の各関数は以下の特徴を持ちます：

• 仮想無限スタック。スタックには固定された要素タイプまたは幅がなく、スカラーおよび複素値は一様に処理されます。集合は参照によって管理されます。
• スタック上で動作する非構造的線形フロー命令で、条件なしジャンプと分岐によって支配されます。各命令はオプションの即座、タイプID、またはコード参照パラメータを持つことができます。
• ユニークID とオプションのスコープを持つ型指定されたアドレス可能ローカル変数スロットのセット。スロットはインストラクションフロー内で定義され、初回参照時にインスタンス化されます。

スタックベース IR はフロントエンドと Kefir のミドルおよびバックエンドの間を分離レベルを提供し、すべてのターゲット固有の詳細をカプセル化して上位層に統合された抽象化を提供します。コードのコンテナを超えて、スタックベース IR はフロントエンドがターゲット固有情報を（タイプレイアウト、サイズ、アライメントなど）取得するための API セットを提供します。スタックベース IR オペコードのリストは

headers/kefir/optimizer/opcode_defs.h

および

headers/kefir/ir/opcode_defs.h

（前者にはいくつかの SSA 固有オペコードも含む）で利用可能です。スタックベース IR は関心事次元に沿った実行可能形式を表します。早期バージョンの kefir はこれをスタックベーススレッドコードを生成するための運用モデルとして使用しました。

オプティマイザIR

オプティマイザ IR はスタックベース IR の解析的対照物です。部分順序を持つサイドエフェクトフリー操作を持つ SSA フレーバーを使用します。オプティマイザ IR の特徴は以下の通りです：

• 基本ブロックの明示的な制御フローグラフで、個別の命令を所有しています。
• 命令と値との緊密な対応関係。各命令自体が値を表し、変数とコピー操作の概念は存在しません。オプティマイザ SSA は常に非伝統的フォームです。
• 各基本ブロック内のサイドエフェクトフル命令の線形「制御フロー」チェーン。サイドエフェクトフル命令には関数コール、メモリ操作、インラインアッセンブラー、ブロック終止子が含まれます。原則として、命令オペコードが制御フローチェーンに属するかどうかを決定しない（ブロック終止子を除く）：部分順序されたコールまたはメモリアクセスは制御フローチェーンの外に存在できる可能性があるが、それらはプログラム状態の非連続セグメント上で動作する限り。むしろ、このチェーンはソースレベルサイドエフェクト順序を反映します。
• 各基本ブロック内のサイドエフェクトフリー命令（すなわち純粋計算）の有向非循環グラフ。各個別の命令の位置は、追加の順序付け制約なしにその入ってくるデータフローエッジによってのみ決定されます。
• どの種類の命令でも、現在または他の基本ブロックからのサイドエフェクトフルおよびサイドエフェクトフリー両方の命令に依存できます。したがって、支配関係は緩和され、データフロー依存性と制御フロー内の位置に基づいて指令の相対的なシーケンシングを反映します。この構造は、正確なスケジュールを指定せずにスケジューリングのための制約のセットを提供します。コンパイラは任意の合法的線形化を仮定する自由があります。
• データフローは通常の Phi 命令によって組織化されます。Phi は常にサイドエフェクトフリーです。

コード表現の外で、オプティマイザIR はスタックベース IR と共有されるプログラムの他のセマンティクス側面（シンボル、タイプおよび関数シグネチャなど）を持っています。オプティマイザ IR オペコードのリストは

headers/kefir/optimizer/opcode_defs.h

で利用可能です。

著者は、概説した設計が C コンパイルにとって最も適しているとみなし、LLVM IR と Sea-of-Nodes スタイルの極端とのスペクトル内で全体的に有利な位置にあると考えています。特に：

• 設計は多くのプログラミング言語で存在する純粋計算とサイドエフェクトフル操作の違いを自然に反映します。C においては、これは標準が明示的にシーケンシャルポイントと「as-if」規則の用語で抽象マシーンセマンティクスを定義することに起因して特に顕著です。サイドエフェクトフル操作は、基本ブロック内の線形操作チェーンを通じて親しみやすい方法で組織化されます。Sea-of-Nodes アプローチに対する批判の一部は、データおよび制御フロー依存関係のための統一表現の複雑さに焦点化しており、これはデバッグ性と理解を損ないます。Kefir は伝統的なアプローチを維持することでこれを回避しようとします。
• サイドエフェクトフリー操作は、命令内のよく定義された位置を持つブロックローカル有向非循環グラフを使用します。理論的表現力については、LLVM のブロックローカル線形アプローチと同じであり、データフローを尊重する再スケジュールが可能ですが、著者はそのような構造の修正とトランスフォームが単純なタスクであるとみなし、正確な挿入ポイントを指定する必要がないためです。大部分の命令はサイドエフェクトフリーであり、したがって多くのトランスフォームパスは新しい指令 DAG フラグメントをその対応する基本ブロックに「投げ出す」ことができ、正確な位置はスケジューリング段階で後に行われます。原則として、LLVM 様のブロックローカル線形化は制御フローチェーンの過剰指定によって達成できますが、Kefir はそのような過剰指定を考慮するための再スケジュールファシリティを持っていません。
• この構造は、制御フローチェーンおよび到達可能基本ブロックの推移データ依存関係の巡回によりデッドコード排除を自然に誘発します。Kefir は正規化のためにのみ別々の DCE トランスフォームパスを提供します。

メモリ SSA

メモリ SSA はオプティマイザ IR の下部に属し、いくつかの最適化パスのためにそれから構成されます。メモリ SSA は、オプティマイザ IR CFG 内の生きている命令をスキャンしてメモリエフェクト（メモリアクセス、関数コール、インラインアッセンブラー）を検出し、以下のノードを持つグラフに結果として構成されます：ルート（関数エントリポイント）、終止（関数戻り）、プロデュース（読み取り専用メモリオperation）、コンシューム（読み取り専用メモリオperation）、プロデュース-コンシューム（読み書き）、および Phi。プロデュース/コンシュームノードは、それらを誘発するオプティマイザ IR 命令に戻ります。ルート、プロデュース、およびプロデュース-コンシュームノードは、コンシューム、プロデュース-コンシューム、および終止ノードによって消費されることができる新しいメモリのバージョンを定義します。プロデュースとプロデュース-コンシュームノード間の区別は、操作がメモリを変更する場所に関連して動作を反映するために役立ちます。

オプティマイザ IR と比較して、メモリ SSA は基本ブロック構造を省略し、オプティマイザ IR の部分順序を制御およびデータフローによって許可される任意の全順序に線形化します。後者の変換は有効であることが保証されており、任意の 2 つの部分メモリアクセスは必ずしもメモリの非連続セグメント上で動作することをオプティマイザ IR が確保するからです。基本ブロックの省略は可能であり、メモリ SSA は制御フローまたは他の計算を明示的に表さないためです。

最適化パイプライン

Kefir は -O1 レベルで以下の上位レベル最適化パスを含みます：

• 関数インライン化: オプティマイザはパイプラインの早期にのみインライン化を行い、ソースコードレベルで提供された注釈だけで導かれます。Kefir は関数のインライン化のためのどのヒューリスティックも実装していませんが、過剰なインライン化深度のためにいくつかのインライン化が無効になる可能性があります。著者はこれを単なる最適化ではなく、プログラマーの注釈への誠実な実装と見なします。
• ローカル変数のレジスタへのプーミング (mem2reg): オプティマイザはアドレスが関数から決して逃げず、そしてニクス（alias）しないスカラーおよび複素ローカル変数を特定し、これらローカル変数を SSA 値にプーミングします。これは主にさらに多くの分析を有効にするための主要な最適化です。
• Phi 除去: オプティマイザは冗長な SSA phi ノードとウェブを特定して排除します。
• 定数畳み込み: オプティマイザは SSA のすべての定数木を特定して畳み込みます。
• 単純化: これらの最適化パスは、正規化、最適化、そして多様な命令形状の単純化を組み合わせています。単純化はオプティマイザ IR へのアドホックパターンマッチングとして実装され、固定点に達するまで実行されます。
• ローカル割り当て沈み込み: mem2reg パスによって排除されていないローカル変数の割り当てが、実際の使用に近づけられてスタックフレームレイアウトをより密集させます。
• メモリ SSA: オプティマイザはオプティマイザIR からメモリ SSA 表現を構築し、ロード-ロード、ストア-ストア、ストア-ロードおよびゼロ化ストアの最適化を実行します。現在、これらの最適化パスの効率は主に保守的な非感度型アライズおよびエスケープ解析によって制限されています。
• 集合のスカラー置換: オプティマイザは mem2reg およびアライズ解析インフラストラクチャを借りて、ニクスしない方法でアクセスされ、決して逃げるローカル変数のセグメントを特定します。その結果、これらのフラグメントは SSA 値に昇格されます。この最適化パスは mem2reg の一般化と見なすことができます。
• グローバルバリューナンバリング (gvn): オプティマイザは関数コード全体で同一である指令木を特定し、それらを重複排除します。必要に応じて、重複排除された木は上に持ち上げられます。gvn パスは積分スカラー指令木のみ動作し、サイドエフェクトを含んでいないため、非常に保守的です。これに mem2reg、メモリ SSA、および sroa パスを先行させることで、いくつかのメモリアクセスが SSA 値に昇格され、GVN トランスフォームがより有能になります。
• ループ不変式コード移動 (licm): オプティマイザはループを特定し、それらをネストにグループ化します。ループ内のループ値に依存しない指令木は、ループネストの外レベルまたはその外側に持ち上げられます。GVN と異なり、LICM はメモリアクセスのサイドエフェクトフリーメモリロードとループ不変式ストアをラフトするためのメモリ SSA を統合します。
• ループ除去: C 言語標準によって提供されるサイドエフェクトフリーループ終止の仮定の下で、特定のループが除去されます。
• デッドコードおよび割り当て排除: オプティマイザはデッド指令とローカル変数の割り当てを特定して排除します。これは現在のオプティマイザ IR フレームワーク内のコード生成には必要ではありませんが、これにより依存関係を検討する必要があるいくつかの後続のパスを単純化します。
• ブロックマージ: オプティマイザは安全にマージできる基本ブロックを特定し、マージを実行して制御フローエッジを排除します。
• テールコール最適化: 最適化パイプラインの最終部分として、オプティマイザは潜在的なテールコールを特定します。それは保守的なエスケープ分析を実行して、ローカル変数のアドレスが関数から逃げないことを確認します。最適化パスはターゲット固有の側面を考慮せず、したがってテールコールを行う最終的な決定はコード生成段階で行われます。

上記に記述されたすべての最適化パスは、コード正当性の観点からは厳密にオプションです。これらのパスに加えて、Kefir はパイプラインの一部としてローリングパスを実装しています。ローリングパスは、C23 標準の実装（_BitInt）と特定のソフトウェア浮動小数点操作を実行するための任意精度算術指令を、オプティマイザネイティブ算術指令またはサポートルーチンコール（Runtime library を参照）に変換するために必要です。ローリングは IR にターゲット固有の詳細を導入しません。

最適化レベル: 現時点で、Kefir は -O0 および -O1 の 2 つの最適化レベルをサポートしています（他はすべて -O1 と同等と考えられています）。両方のレベルには関数インライン化、ローカル割り当て沈み込み、デッドコードおよびデッド割り当て排除、およびローリングパスが含まれます。さらに、-O1 は上記のすべてのパスを含みますが、いくつかの重複があります。詳細な最適化パイプラインについては

source/driver/driver.c

を参照し、コマンドラインオプションで明示的に最適化パイプラインパスを定義するためのマニュアルページを参照してください。

バーチャル 3 アドレスコード（Virtual 3AC）

バーチャル 3AC は抽象化次元軸に沿ったターゲット固有ファミリへの仮想化リソース管理へのシフトを表します。原則として、バーチャル 3AC を x86_64 アッセンブラーと仮想レジスタおよびスビエリアセグメントを持つものとして見ることができますが、技術的には Kefir は 3AC のコンテナ（指令構造、値、ラベル付着、仮想レジスタタイプと制約）を x86_64 固有インスタンス化から分離しています。Kefir はオプティマイザIR を x86_64 3AC へローリングするために、極小数の指令バリエーションと最小限の融合を持つ単純な手続き的指令選択を実装します。多くの最適性関心、包括的に指令バリエーション、より大きなパターン、融合、アドレッシングモードはターゲット IR ステージにシフトされます。さらに、バーチャル 3AC は特定の指令形状の合法性を心配せず、あらゆるオペランドの組み合わせを受諾し、法律化はターゲットIR の破壊時に物理的 3AC へ起こります。

正確なレジスタ要件を符号化する主なアプローチは、レジスタアロケータのためのプレカラーリングを指定する仮想レジスタ制約です。仮想レジスタ制約は ABI（例：コール規約）および ISA（例：暗黙レジスタオペランド）固有の要件を符号化するために使用されるため、指令選択後の段階がこれらの要件について機械的な制約満足の外に推論することから解放されます。通常、制約された仮想レジスタの場合、指令シーレクターはまた最小必要なライフタイムを確保する特別な指令（以下参照）を発行します。3AC は物理レジスタを直接指定する方法を提供しますが、関数のプロローグおよびエピログの非常に特異なコードフラグメント、特殊な非割り当て可能なレジスタ（例：rsp, rbp, セグメントレジスタ）、または周囲仮想レジスタの制約によって保護された配置（消えつつある少数の場合）でのみ、バーチャル段階での出現が制限されます。すべての場合において、残りのパイプラインは指定された物理レジスタがレジスタ割り当てまたは他の決断と干渉することはないという仮定の下で動作することを許可されています。

サポートされている x86-64 オペコードの一般セットは

headers/kefir/target/asm/amd64/db.h

で利用可能で、特殊なオペコードは

headers/kefir/codegen/amd64/asmcmp.h

です。特殊なオペコードの間、リンクは仮想レジスタの任意のタイプ間の多態的な mov 操作として使用され、touch および weak_touch は仮想レジスタライフタイム拡張操作を表し、後者は ABI 誘発制約（ターゲット IR 構築後に消去）に予約されています。produce は未指定値を持つ新しい仮想レジスタの定義を表します --- これは必要です。なぜなら x86-64 で use-define チェーンはしばしば曖昧であり、いくつかの指令（例：xor %eax, %eax）は純粋な定義を提供し、技術的には RMW with no-op uses と見なされるためです。

バーチャル 3AC は関心事次元に沿った実行可能形式を表します。それは無数のレジスタを持つ仮想 x86-64 CPU によって実行可能であるべきですが、歴史的に Kefir は物理的 3AC と併せて使用し、単純なレジスタ割り当てと devirtualization スキームを実装して指令形状の法律化を行いました。現在のバージョンでは、バーチャル 3AC はより強力な最適化のためのターゲットIR へ変換されます。

ターゲット IR

ターゲットIR はターゲット固有バーチャル 3AC の解析的対照物です。x86-64 マシンの状態を SSA フォームで仮想化リソース管理で表します。ターゲット IR の特徴は以下の通りです：

• 基本ブロックの明示的な制御フローで、基本ブロック内の命令の全体的線形順序。
• 指示と値間の 1 対多数の関係。各指令はゼロまたは複数の出力値を持つことができ、各値は一意に識別されます。指令 ID とアスペクト ID のペアによって。
• 値アスペクトは値のクラスを特定します：直接（汎用および浮動小数点レジスタなどの仮想化リソースを表す）、リソース（個別フラグ、x87 スタックなどのマシーン状態内の唯一の名付けられたエンティティを表す）間接的（メモリエフェクトを表す）。1 つの指令は同じアスペクトクラスを持つ複数の値を生成でき、順序番号によって区別されます。
• 各値はタイプに関連付けられており、種類、バリエーション、および制約で特徴付けられます。直接値の種類には汎用、浮動小数点、スビスペース、外部メモリアドレスが含まれます。リソースの種類の種類と間接的値は固定されています。バリエーションは指令によって計算される出力ストレージの割合（例：8/16/32/64 ビット）を指定します。出力ストレージ（レジスタ、スビスペーススロットなど）は、バリエーションに関係なく完全に修飾されると仮定され、これは直接計算結果と入力オペランドから伝搬された結合部分を区別するためのものです。
• 制約はレジスタアロケータに communicated されます。
• 各指令はゼロまたは複数のオペランドを持ち、その構造はバーチャル 3AC オペランドを反映し、仮想レジスタを値参照で、ラベルをブロック参照で置き換えます。値参照にはバリエーションと結合フラグがあり、バリエーションは計算に直接使用される値の部分を指示し、結合フラグはその入力パラメータから他のビットをその出力値に移転する可能性があるかどうかを示します。
• バーチャル 3AC と比較して、各指令はより多くの入力オペランドと出力を持つことができ、ターゲットIR の構築時にすべての暗黙的パラメータとエフェクトが明示化されるためです。
• リード-_modify-write 指令パラメータは、バーチャル 3AC から構築された際に入出力パラメータに分解されます。結合パラメータの逆転は破壊時または特定のパス（正確な指令形状を区別する必要がある）で一時的に行われます。
• 直接およびリソースクラスの値は構築およびトランスフォームにおいて同様に振る舞います。違いはレジスタ割り当てと破壊時に現れ、直接値は適切なバックストレージに自動的に割り当てられるのに対し、リソースは良好な動作を前提としています。したがって、リソースに対して SSA フォームは任意の変換によって保持されるべき明確なデータフロー帳簿としての役割を果たします。違いは、ターゲットアーキテクチャが効率的に個別のリソース（例：個別の CPU フラグ）を操作する機構を持たないため、バックストレージの自動管理が問題になる可能性があることに正当化されます。
• ターゲットIR は物理レジスタの存在を原則的に許可しますが、それらは物理的レジスタ割り当てまたはターゲットIR が下す他の決断と干渉することはないという仮定の下でのみ現れます（バーチャル 3AC セクションで説明した同じ感覚）。

ターゲット IR の構造を示すために、x86-64 で通常複数の暗黙レジスタおよび RMW 操作を含み CPU フラグを修飾する

cdq -> idiv

操作を表すコードフラグメントを検討してください（注：kefir は IR を JSON フォーマットで出力します。以下は構文的には簡略化されていますが、意味論的に同等です）。

(%42:direct[0] gp variant default requires rdx) = cdq (%41:direct[0] variant 32bit !tied)
(%43:direct[0] gp variant default requires rax), (%43:direct[1] gp variant default requires rdx),
    (%43:flag_sf), (%43:flag_of), (%43:flag_pf), (%43:flag_cf), (%43:flag_zf) =
    idiv (%40:direct[0] variant 32bit !tied) (%41:direct[0] variant 32bit tied) (%42:direct[0] variant 32bit tied)

これは LLVM の MachineIR と比較できます。

著者はターゲット IR デザインが以下の有益な特性を持つと考えています：

• 統一表現: x86-64 マシンリソースの主要なものの統一表現。ターゲット IR は SSA フレームワークの外にアドホックプロパティや特殊形式を指定する必要性を回避します。
• 明示的表現: 入力および出力の明示的かつ完全な表現、RMW 操作を含む。ターゲットIR はこれらを SSA フォームに持ち上げ、使用されている大部分のリソースで自動バックストレージ管理を保証します。特別な処理が必要な指令数は最小化されます。
• SSA ネイティブ追跡: すべての値のための SSA ネイティブライブレンジおよび使用追跡。ターゲット IR は物理レジスタの直接エンコーディングを抑制し、代わりに値に割り当て制約を付与します。したがって、特別な属性を追跡する必要性なしに標準データフロー分析が利用可能です。

これにより、ターゲット IR は以下のトランスフォームを実装します：

• グローバル「ピープホール」最適化: 多くの伝統的なピープホール最適化は、機能全体のデータフローでパターンを一致するように緩和されます。これには異なる指令形状の選択、さまざまな単純化、デッドコード排除、定数伝搬、複雑なアドレッシングモードへの指令シーケンスの畳み込みが含まれます。
• 多段階レジスタ割り当て: ターゲットIR はレジスタ割り当ての前に SSA 外の変換を受けます。現在ターゲット IR はライブレンジ分割なしで単純なevicting レジスタアロケータを実装しています。予備的なレジスタ割り当てを取得した後、ターゲット IR コードはスパilling 情報によって生成されたガイドによるさらなる最適化のための SSA フォームに戻って簡単に復元されます。このスキームは単純なレジスタアロケータのいくつかの弱点を緩和しつつ、パイプラインを扱いやすく保ちます。
• ローカルホットコピー挿入と再物質化: 予備的なレジスタ割り当て結果によって導かれます。

物理的 3AC

物理的 3AC はその実行可能形式での最低レベルの抽象化ファミリを表します。これは、すでに割り当てられた物理リソースを持つコードのターゲットマシーン固有表現を符号化しています。物理的 3AC の特徴は以下の通りです：

• バーチャル 3AC と共有コンテナ。両方の IR は同じ指令構造を使用し、主な違いはレジスタオペランドのタイプです。
• 物理的 3AC は仮想レジスタの存在を禁止します。
• すべての指令はターゲットIR の破壊の結果として法律化された形で出現するはずです。物理的 3AC からコード放出は自明なシングルパス操作です。
• 物理的 3AC はスビスペースアドレスリングの特殊な形式（スビスロット、ローカル変数）を許可します。コードエミッタにはフレームベース相対アドレスに解決するために使用されるスタックフレームレイアウトが提供されます。
• 物理的 3AC は通常 x86-64 指令シーケンスとして符号化され、オペランド順序は Intel シンタックスに対応しています。物理的 3AC のコードエミッタは複数の可能なシンタックスターゲット（GNU As AT&T、前付き付き/なしの Intel、Yasm）を実装します。

デバッグ情報

Kefir は GNU As ターゲットアッセンブラー向けのデバッグ情報の生成をサポートしています。生成されたデバッグ情報は DWARF-5 フォーマットで、アッセンブラー指令とソースコード場所間のマッピング、変数場所、タイプ情報、関数シグネチャを含みます。著者はオプティマイザパイプライン全体で変数場所を維持するための最善の努力を試みました However, いくつかの -O1 レベルでの最適化はデバッグ体験を大幅に妨げる可能性があります。

ランタイムライブラリ

非ネイティブアトミック演算子（libatomic を必要とする）、小数点浮動小数点数（libgcc）およびスレッドローカルストレージを除いて、Kefir は自己完結なアッセンブラーリストを生成し、独自のランタイムライブラリを必要としません。コードジェネレーターは通常、大部分の操作の実装をターゲット関数に直接インライン化します。この唯一の例外は、C23 標準の

_BitInt

機能をサポートするために必要な任意精度算術操作と、複素数のためにいくつかのソフトウェア浮動小数点操作です。これらの操作中、Kefir は関数コールを発行し、内部リンカを持つ必要な関数を生成されたアッセンブラーリストの最後に追加します。

ゴールと優先順位

プロジェクトとして、Kefir は以下の目標を持っています（優先順）：

1. 独立性: その範囲内では、C17/C23 ソースコードからアッセンブラーへの翻訳において、Kefir は独立しており、パース、コンパイラ、またはコード生成フレームワーク/ライブラリに依存しません。範囲外では、Kefir はシステムツールチェーン構成要素と統合する必要があります。
2. 正当性、互換性、準拠: Kefir は以下に準拠する必要があります：
   • C17 および C23 言語標準。標準からの逸脱は、明示的に peculiarity として文書化されない限り、Kefir のバグと見なされます。
   • System-V AMD64 ABI。Kefir は他のコンパイラによって生成された同じプラットフォーム上のオブジェクトファイルまたはライブラリと自由にリンクできるコードを生成する必要があります。
   • 他の関連する文書（DWARF-5 標準、スレッドローカルストレージモデル）。Kefir は可能な限り他のプラットフォームバイナリインターフェースや環境を定義する文書に準拠し、完全な互換性を促進します。
   • 人気のある C 言語エクステンション（GNU C エクステンション、gcc ブートイン）。完全な言語エクステンションセットの実装は Kefir の目標ではありませんが、リアルワールドソフトウェアをコンパイルするために十分な数のエクステンションがサポートされるべきです（外部テストスイートに含められているなど）。各特定エクステンションのサポート度合いと互換性は異なる場合があります。
   • コマンドラインインターフェース。Kefir は cc 互換コマンドラインインターフェースを実装し、gcc または clang コンパイラによってサポートされたいくつかのオプションで拡張されています。目標は、Implementation quirks で文書化されている制限が観察される場合に

     cc

     のドロップイン置き換えを役立てることです。
3. 限定された範囲: Kefir はソースからアッセンブラーへの翻訳および他のシステムツールの統合に焦点を当てています。ツールチェーンの他の部分（libc、アッセンブラー、リンカー）または他の言語/ダイアLECTの実装は現在、プロジェクトの目標ではありません。
4. 「roundness」: Kefir は全段階が信用できる C コンパイラから期待されるアーキテクチャを持つべきです。いくつかの段階のパフォーマンス（実行時間およびコンパイル時間）は不足しているかもしれませんが、すべての段階が存在し、アーキテクチャ的に健全である必要があります。プロジェクトアーキテクチャは特定の段階の微調整とコンパイラの改善のための反復アプローチを許可する必要があります。
5. パフォーマンス: 他のすべての目標が合理的に観察された後、プロジェクトは広範な意味でのパフォーマンス向上を含むかもしれません。この文脈でのパフォーマンスという概念には、コンパイラのパフォーマンスと生成されたコードの効率的の両方が含まれます。Optimization and codegen セクションで説明されている最適化パスおよびコード生成は主に正当性と roundness 条件を満たすために定義され、パフォーマンス向上は後に続きます。
6. ポータビリティ: Kefir は Unix 様 x86_64 システム間でポータブルであるべきです。非 x86_64 または非 Unix プラットフォームへのサポートは現在非目標と考えられますが、将来変更する可能性があります。

歴史と将来計画

プロジェクトは 2020 年 11 月以来アクティブな開発が続いています。その期間中、著者はいくつかの中間バージョンをリリースし、完全な記述は CHANGELOG で利用可能です。バージョン化スキームは一貫性ではなく、「vibe-versioning」（すなわち厳格なバージョン化スキームの欠如と、リリースについての著者の個人的な感覚に依存）として特徴付けられます。

• 0.1.0 -- 2022 年 9 月にリリース。プロジェクトの最初の 2 年を表し、Linux および BSD システム向けにいくつかの欠落を有する基本的な C17 コンパイラを提供し、いくつかのリアルプロジェクトのブートストラップおよびビルドが可能です。コンパイラはスレッドコード実行モデルに基づいており、いかなる最適化も行いません。
• 0.2.0 -- 2023 年 7 月にリリース。プロジェクトは新しいオプティマイザ IR とコードジェネレータを導入しましたが、すべての最適化は後続のリリースに延期されました。
• 0.3.0 -- 2023 年 8 月にリリース。いくつかの最適化とユーザビリティ向上が追加されました。
• 0.3.1 -- 2023 年 11 月にリリース。プロジェクトは新しいコードジェネレータを獲得しました。この時点で、プロジェクトアーキテクチャは現在の形式へ変換されました。
• 0.4.0 -- 2024 年 9 月にリリース。欠落している C17 機能の実装、デバッグ情報ジェネレータの導入、外部テストスイートの導入。
• 0.4.1 -- 2025 年 2 月にリリース。生成されたコードの正当性と互換性における大幅な改善、外部テストスイートの大幅な拡張。
• 0.5.0 -- 2025 年 9 月にリリース。オプティマイザIR 構造の大幅なリファクタリングと改善、新しい最適化パス、C23 サポート、リアルワールド互換性の別の大幅な拡張。
• 0.5.1 -- 2026 年 4 月にリリース。C23 サポートの完了（小数点浮動小数点数、虚数浮動小数点数、STDC プラグマ）、コード生成層の大幅な書き換え（Optimization & codegen の「Target IR」セクション参照）、保守的なメモリ分析の統合を含むオプティマイザ改善、128 ビット整数サポート、リアルワールド互換性の拡張。

著者は将来の開発に関するいかなる約束やコミットメントも行いません。プロジェクトへのコミットは予告なしで最後のものになる可能性があります。Nevertheless, 開発が終了するか indefinitely 停止される場合、著者はこれを明確に伝達しようとします。さらに、アクティブな開発の終了後既に公開されたコードにおけるバグが発見された場合、著者は問題に対処する限られた修正を发行するかもしれません。

配布

Kefir はソースコードとして排他的に配布され、以下のソースから入手できます：

• Kefir プロジェクト (Sourcehut) -- 主要な開発リポジトリ。
• 著者の個人 git リポジトリ -- ミラー。
• Kefir リポジトリ (Codeberg) -- 二次ミラー。

著者はプロジェクトのウェブサイトでリリース tarballs を公開します。ソースコードは、マスターブランチから取得することを推奨し、より最新のコードを含んでいる可能性があるため、そのブランチへのマージはリリースと同様に徹底的にテストされます。

さらに、著者は ArchLinux User Repository で 2 つの PKGBUILD ビルドスクリプトを維持しています：

kefir

および

kefir-git

。

著者はサードパーティによって生産された kefir パッケージを知っています。著者はこれらのパッケージメンテナと結びついていませんので、使用は自己責任で行ってください。パッケージは陳腐化しているか他の問題を持つ可能性があります：

• GNU Guix
• FreeBSD
• Ubuntu PPA
• Alpine パッケージ
• Fedora パッケージ
• Nelson H. F. Beebe のビルド

ライセンス

コンパイラコード本体は GNU GPLv3 (のみ) 条件の下でライセンスされ、LICENSE を参照してください。念のため、唯一の部分に注意：Kefir はいかなる「後続バージョン」条項も含んでおらず、新しい GNU GPL バージョンの公開はプロジェクトに影響しません。

任意精度整数処理ルーチン (

headers/kefir_bigint

) およびランタイムヘッダー (

headers/kefir/runtime

) は BSD 3 クロース条項ライセンスの条件の下でライセンスされています。これらのファイルからのコードはコンパイラによって生産されるアータに含まれることを意図しているため、ライセンス要件が緩和されています。さらに、これらのファイルが Kefir との通常のコンパイルパイプラインの一部として使用される場合、そのライセンスは GCC ランタイムライブラリ例外の精神に従うとみなすことができます。そのようなケースでは、著者は BSD ライセンスの再配布条項 (#1 および #2) をいかなる方法でも強制する意図はありません。

明瞭のために、リポジトリ内の大部分のソースファイルにはライセンスおよび著作権ヘッダーが含まれています。

コントリビュート

著者はプロジェクトを極端な大聖堂モデルに従って作業しています。潜在的な外部コードコントリビュートは、著者によって事前に議論されるべきであり、例外は自明でシリーズの短かいコミットとして書かれており、著者が「一瞬で」レビューできる場合です。事前の議論を経ない非自明な無誘惑マージ要求は、追加の議論または考慮なしに拒絶される可能性があります。

ただし、著者はコード以外のコントリビュート（バグ報告、バグ再現サンプル、関連資料への参照、出版物など）を歓迎します。

有用なリソースとリンク

基礎情報

• C11 標準最終ワーキングドラフト
• C17 標準最終ワーキングドラフト
• C11 - DRs が C17 言語標準に組み込まれた Clarification Request Summary。
• The first C2Y draft shall be content-wise equivalent to the published C23 standard.

プラットフォーム固有

• System-V AMD64 ABI
• AMD64 命令セットリファレンス

有用なツール

• Compiler Explorer
• Record and Replay フレームワーク
• CSmith

補足情報

• C リファレンス
• x86 命令セットリファレンス
• x86 および amd64 命令リファレンス

Kefir 固有リンク

• 著者の個人ウェブサイト
• Kefir ウェブサイト
• Kefir プロジェクト (Sourcehut) -- 主要な開発リポジトリ。
• Kefir ミラー (著者の個人 git リポジトリ) -- ミラー。
• Kefir リポジトリ (Codeberg) -- 二次ミラー。
• 著者の PGP キー -- すべての git タグ、リリースおよび関連アータは、さらなる通知までこのキーで署名されます。
• Kefir にある Coffee Compiler Club の話

トリビア

• Fermented milk drink
• The Cathedral and the Bazaar

謝辞

著者は、Kefir で作業する意図、動機および能力に影響を与えた多くの人々（特定の順序なし）に敬意を表します：

• C プログラミング言語および UNIX の元の作者およびデザイナー：Dennis Ritchie および Ken Thompson。疑いなく、Kefir のどの作業も著者は巨人の肩の上に立っている因为只有彼らがなければ不可能です。
• 主要 C コンパイラの元の作者 -- GNU Compiler Collection の Richard Matthew Stallman および Clang の Chris Lattner -- および Tiny C Compiler の作者である Fabrice Bellard。これらの人々の作品は Kefir の創造を鼓舞しました。
• Kefir のビルドまたは開発プロセスで何らかの方法で依存しているソフトウェアプロジェクトの作者およびコントリビュータ：Linux カーネル、FreeBSD、OpenBSD、NetBSD、DragonflyBSD、GNU プロジェクト、Clang、Musl libc、CSmith、および他の小さなプロジェクト。
  • 特に著者は Record and Replay フレームワークプロジェクトを強調したいです。それはより知られていませんが、Kefir およびそれによってコンパイルされたソフトウェアの失敗を調査するのに重要であり、このプロジェクトは Kefir の現在の状態に非自明の影響を与えました。
• once again、GNU General Public License の作者である Richard Matthew Stallman。著者は GNU GPL がフリーソフトウェア運動を確立する礎であると信じています。
• 外部テストスイートで使用されるすべてのプロジェクトの作者およびコントリビュータ。これらはここにリストするには多すぎますので、

  source/tests/external

  を参照してください。
• slimcc の開発者である Hsiang-Ying Fu がコンパイラ検証のために素晴らしい C プロジェクトコレクションをコンパイルしました。
• 著者がコンパイラの作業を再開する動機を与えたブロガーである Dr. Brian Robert Callahan。
• Kefir 開発の早期段階で観察し認められた他の誰でも。
• 著者の友人および親族で、年々 C コンパiling トピックについての独り言にリスナーだった人々。

プロジェクトは Jevgenij Protopopov (合法な綴り：Jevgēnijs Protopopovs) が一人でアーキテクチャ、エンジニアリング、実装しました、サードパーティから得た 2 つのパッチを除きます：

• Brian Robert Callahan - 初期 OpenBSD ポート
• remph - 無長環境変数を未設定として扱う

著者はメールで直接またはマailing リストを通じて連絡できます。

プロジェクトの開発は外部資金源または制度的サポートなしに独立して行われました。