laccアウェイlaccソースCEADダウンロード

lacc

C# ソースコード

1.0.0

ダウンロード

LACC：シンプルで自己ホスティングCコンパイラ

これは私のおもちゃのプロジェクトであり、Cでコンパイラを作成することを目標としています。これはCで書かれています。

特徴

後の基準からのいくつかの機能に加えて、C89の完全なサポート。
ターゲットX86_64アセンブリGNU構文（-S）、バイナリELFオブジェクトファイル（-C）、または純粋な前処理（-E）。
豊富な中間表現、各関数定義の3つのアドレスコードの基本ブロックを備えたコントロールフローグラフ（CFG）を構築します。これは、基本的なデータフロー分析と最適化の目標です。

インストール

ソースからクローンとビルドを使用すると、バイナリはbin/laccに配置されます。

 git clone https://github.com/larmel/lacc.git
cd lacc
./configure
make
make install

デフォルトの構成には、コンパイルしているマシンとLIBCを検出するための環境の基本的な調査が含まれます。現在、認識されているプラットフォームには、GLIBCまたはMUSLを備えたLinux、およびOpenBSDが含まれています。

stddef.hやstdarg.hなどの特定の標準ライブラリヘッダーには、本質的にコンパイラ固有の定義が含まれており、lib/の下のLACC専用に提供されています。ヘッダーをインストールせずにbin/laccを直接使用する場合は、このフォルダーを直接指すように設定して場所を--libdirできます。

installターゲットは、バイナリとヘッダーを通常の場所にコピーするか、 --prefixまたは--bindirで構成されています。 DESTDIRを設定するオプションもあります。実行してmake uninstallコピーされたすべてのファイルを削除します。

./configure --helpビルドとインストールのパラメーターをカスタマイズするためのオプションについては。

使用法

コマンドラインインターフェイスは、同じフラグとオプションのサブセットを使用して、GCCや他のコンパイラと同様に保持されます。

 -E         Output preprocessed.
-S         Output GNU style textual x86_64 assembly.
-c         Output x86_64 ELF object file.
-dot       Output intermediate representation in dot format.
-o         Specify output file name. If not speficied, default to input file
           name with suffix changed to '.s', '.o' or '.dot' when compiling
           with -S, -c or -dot, respectively. Otherwise use stdout.
-std=      Specify C standard, valid options are c89, c99, and c11.
-I         Add directory to search for included files.
-w         Disable warnings.
-g         Generate debug information (DWARF).
-O{0..3}   Set optimization level.
-D X[=]    Define macro, optionally with a value. For example -DNDEBUG, or
           -D 'FOO(a)=a*2+1'.
-f[no-]PIC Generate position-independent code.
-v         Print verbose diagnostic information. This will dump a lot of
           internal state during compilation, and can be useful for debugging.
--help     Print help text.

オプションと一致しない引数は、入力ファイルになると見なされます。コンパイルモードが指定されていない場合、LACCはシステムリンカー/bin/ldのラッパーとして機能します。いくつかの一般的なリンカーフラグがサポートされています。

 -Wl,       Specify linker options, separated by commas.
-L         Add linker include directory.
-l         Add linker library.
-shared    Passed to linker as is.
-rdynamic  Pass -export-dynamic to linker.

例として、ここではTest/c89/fact.cをオブジェクトコードにコンパイルし、システムリンカーを使用して最終的な実行可能ファイルを生成します。

 bin/lacc -c test/c89/fact.c -o fact.o
bin/lacc fact.o -o fact

このプログラムはテストスイートの一部であり、5を計算します！再帰を使用し、答えを終了します。 running ./factに続いてecho $? 120印刷する必要があります。

実装

コンパイラはC89で記述されており、合計で約19k行のコードをカウントします。 C標準libaryを除いて、外部依存関係はありません。また、リンカーを呼び出すのに必要なシステム呼び出しもあります。

実装は4つの主要な部分に編成されています。プリプロセッサ、パーサー、オプティマイザー、バックエンド、それぞれがSRC/の下の独自のディレクトリにあります。一般に、各モジュール（通常、パブリックインターフェイスを定義する.hファイルとペアになった.cファイル）は、主に独自のサブツリーのヘッダーに依存します。グローバルレベルで共有されている宣言は、include/lacc/に存在します。ここでは、コアデータ構造と、前処理、解析、およびコード生成の間のインターフェイスがあります。

プリプロセッサ

プリプロセシングには、読み取りファイル、トークン化、マクロ拡張、およびディレクティブ処理が含まれます。プリプロセッサstruct tokenのインターフェイスは、 peek(0) 、 peekn(1) 、 consume(1) 、 try_consume(1) 、およびnext(0)です。これらはinclude/lacc/token.hで定義されています。

入力処理は、より多くの入力を消費するようにこれらの関数を呼び出すパーサーによって駆動されることによって完全にゆっくりと行われます。前処理されたトークンのバッファーは、見た目のために保持され、先に覗くときにオンデマンドで満たされます。

中間表現

コードは、基本ブロックの制御フローグラフとしてモデル化されており、それぞれが3つのアドレスコードステートメントのシーケンスを保持しています。各外部変数または関数定義は、単一のstruct symbolとコードを保持しているCFGを定義するstruct definitionオブジェクトによって表されます。中間表現を裏付けるデータ構造は、include/lacc/ir.hにあります。

中間表現を視覚化することは、個別の出力ターゲットです。 -DOTオプションが指定されている場合、ドットフォーマットされたテキストファイルが出力として生成されます。

 bin/lacc -dot -I include src/backend/compile.c -o compile.dot
dot -Tps compile.dot -o compile.ps

以下は、完全なグラフのスライスを示すSRC/BackEnd/Compile.cにある関数の例です。完全な出力は、表示されているコマンドを実行することにより、PostScriptファイルとして生成できます。

中間表現の例

グラフ内の各基本ブロックには、式（ struct expression ） IR_ASSIGN変数（ struct var ）に割り当てる声明のリストがあります。式には、高レベルでメモリの位置、アドレス、および参照されるポインターをエンコードできる可変オペランドも含まれています。

DIRECTオペランドは、 *(&symbol + offset)のメモリを参照します。ここで、シンボルはメモリ内の特定の場所（スタックなど）で可変または一時的です。
ADDRESSオペランドは、 DIRECTオペランドのアドレス、つまり(&symbol + offset)を正確に表します。
DEREFオペランドは、シンボル（ポインタータイプのものでなければならない）で指摘されたメモリを指します。式は*(symbol + offset)であり、アセンブリにマッピングするには2つの負荷操作が必要です。 DEREFとDIRECT変数のみが、割り当てまたはl値のターゲットになります。
IMMEDIATEオペランドには、一定の数、または文字列があります。即時のオペランドの評価は、自動的に一定の折りたたみを行います。

パーサー

パーサーはハンドコード化された再帰降下で、メインパーツはSRC/パーサー/宣言に分割され、src/parser/initializer.c、src/parser/expression.c、およびsrc/parser/statement.cに分割されます。現在の関数制御フローグラフ、およびそのグラフの現在のアクティブな基本ブロックは、各生産の引数として渡されます。グラフは、新しい3つのアドレスコード命令が現在のブロックに追加されると、徐々に構築されます。

次の例は、ビットワイズまたは式の解析ルールを示しています。これにより、現在のブロックに新しいIR_OP_OR操作が追加されます。 eval_exprのロジックは、エラーの場合に終了するオペランドvalueとblock->exprが有効であることを確認します。

 static struct block *inclusive_or_expression(
    struct definition *def,
    struct block *block)
{
    struct var value;

    block = exclusive_or_expression(def, block);
    while (try_consume('|')) {
        value = eval(def, block, block->expr);
        block = exclusive_or_expression(def, block);
        block->expr = eval_or(def, block, value, eval(def, block, block->expr));
    }

    return block;
}

最新の評価結果は、常にblock->exprに保存されます。分岐は、新しい基本ブロックをインスタンス化し、ポインターを維持することによって行われます。各基本ブロックには、他のブロックへの真および偽の分岐ポインターがあります。これが、枝とGOTOのモデル化方法です。構文ツリー構造が構築されていないことに注意してください。それは再帰に暗黙的にのみ存在します。

オプティマイザ

制御フローグラフを構築する主な動機は、データフロー分析と最適化を行うことができることです。ここの現在の機能はまだ制限されていますが、追加のより高度な分析と最適化パスで簡単に拡張できます。

livension解析は、すべてのステートメントで、後で読み取られる可能性のあるすべてのステートメントで把握するために使用されます。データフローアルゴリズムは、シンボルを表すためにビットマスクを使用して実装され、1-63に番号が付けられます。結果として、最適化は64未満の変数を持つ関数でのみ機能します。また、ポインターエイリアス分析がないため、アルゴリズムも非常に保守的でなければなりません。

Livension情報を使用して、Dead Store Eliminationを実行する変換パスは、 IR_ASSIGNノードを削除します。

バックエンド

3つのバックエンドターゲットがあります。テキストアセンブリコード、ELFオブジェクトファイル、および中間表現のドットです。パーサーから生成された各struct definitionオブジェクトは、SRC/バックエンド/compile.cモジュールに渡されます。ここでは、中間制御フローグラフの表現から低レベルのIRまでのマッピングを行い、コードをx86_64命令を直接表すものに減らします。これの定義は、SRC/BackEnd/x86_64/encoding.hにあります。

プログラムの開始に設定された関数ポインターに応じて、指示はELFバックエンドまたはテキストアセンブリのいずれかに送信されます。したがって、テキストアセンブリを出力するコードは非常にシンプルで、多かれ少なかれ低レベルのIR命令とGNU構文アセンブリコードの間のマッピングです。 src/backend/x86_64/assemble.cを参照してください。

DOT出力は、生成するために低レベルIRを必要としない個別のパイプラインです。コンパイルモジュールは、CFGをSRC/BackEnd/GraphViz/dot.cに単純に転送します。

正しさ

テストは、LACCとシステムコンパイラ（CC）でコンパイルされたプログラムのランタイム出力を比較することによって行われます。検証に使用される小さなスタンドアロンプログラムのコレクションは、テスト/ディレクトリの下にあります。テストは、Preprocessing、Assembly、およびELFの出力を検証するCheck.shを使用して実行されます。

 $ test/check.sh bin/lacc test/c89/fact.c
[-E: Ok!] [-S: Ok!] [-c: Ok!] [-c -O1: Ok!] :: test/c89/fact.c

コンパイラの完全なテストは、LACCの自己ホストバージョンですべてのテストケースを実行することにより行われます。

 make -C test

これにより、最初にすでに構築されたbin/laccを使用して、 bin/bootstrap/laccを生成します。これはbin/selfhost/laccの構築に使用されます。ブートストラップ段階と自己採用段階の間で、中間オブジェクトファイルは平等と比較されます。すべてが正しく機能する場合、これらの段階は同じバイナリを生成するはずです。コンパイラは、すべてのテストがセルフホストバイナリを渡すときに「良い」ものです。これは、すべてのコミットで常に緑である必要があります。

クスミス

考えられるすべてのケースをカバーする優れたテストスイートを考案するのは困難です。バグを取り除くために、Csmithを使用して、検証に適したランダムプログラムを生成できます。

 ./csmith.sh

csmith.shスクリプトは、csmithを実行して、テストハーネスに何かが失敗するまで無限のランダムプログラムを生成します。通常、失敗することなく何千ものテストを実行します。

4314テストを実行した後もまだ成功しています

Csmithによって生成されたプログラムには、一連のグローバル変数が含まれており、これらに変異を行う機能が含まれています。最後に、すべての変数の完全な状態のチェックサムが出力されます。このチェックサムは、異なるコンパイラと比較して、矛盾またはバグを見つけることができます。 Csmithによって生成されたプログラムの例については、doc/random.cを参照してください。

crecuce

バグが見つかった場合、Creduceを使用して最小限の再ロックを作成できます。これは、通常のテストスイートの新しいテストケースになります。

パフォーマンス

コンパイラ自体を高速にするために多少の努力が払われています（ただし、生成されたコードはまだ非常に最適化されていません）。パフォーマンスベンチマークと正確性テストの両方として機能し、SQLiteデータベースエンジンを使用します。ソースコードは、200 k以上のライン（コメントや空白を含む）にまたがる単一の〜7 MB（7184634バイト）の大きなCファイルとして配布されます。これは、コンパイラのストレステストに最適です。

次の実験は、I5-7300U CPUを備えたラップトップで実行され、SQLite3のバージョン3.20.1をコンパイルしました。測定は、コンパイルからオブジェクトコード（-C）に行われます。

コンピレーション速度

LACCを使用してファイルをコンパイルするには200ミリ秒未満ですが、時間ではなく、CPUサイクルのより正確なサンプリングと実行された命令を調べます。ハードウェアパフォーマンスカウンターデータは、 perf statとvalgrind --trace-children=yesによるメモリの割り当てで収集されます。 Valgrindでは、GCCを実行している間、コンパイラ自体（ cc1実行可能ファイル）からの貢献のみを数えています。

LACCの数字はmake CC='clang -O3 -DNDEBUG' bin/laccによって生成される最適化されたビルドからのものです。各コンパイラには、引数-c sqlite/sqlite3.c -o foo.oで呼び出されます。

コンパイラ	サイクル	説明書	割り当て	割り当てられたバイト	結果サイズ
LACC	412,334,334	619,466,003	49,020	24,244,107	1,590,482
TCC（0.9.27）	245,142,166	397,514,762	2,909	23,020,917	1,409,716
GCC（9.3.0）	9,958,514,599	14,524,274,665	1,546,790	1,111,331,606	1,098,408
クラン（10.0.0）	4,351,456,211	5,466,808,426	1,434,072	476,529,342	1,116,992

おそらく利用可能な最速のCコンパイラの1つであるTCCに近づくために、まだやるべきことがあります。それでも、私たちはTCCのパフォーマンスから妥当な距離内にあり、GCCやClangよりも数桁優れています。

コードゲン品質

上記の表から、LACCによって生成されたSQLiteオブジェクトファイルのサイズが他のコンパイラによって生成されたファイルよりも大きいことがわかります。

LACCとGCCから生成されたコードの相対的な品質を比較するために、GCCによって構築されたバイナリとバイナリによって実行される自己採用バイナリによって実行される動的命令の数を調べることができます。上記と同じテストを実行し、SQLiteをオブジェクトコードにコンパイルします。テストのターゲットは、GCCが生成するデフォルトのコンパイラビルド（ bin/lacc ）と、LACCが生成する自己採用バイナリ（ bin/selfhost/lacc ）です。これらのターゲットは両方とも、最適化を有効にせず、 NDEBUGを定義することなく生成されます。