AIコンパイラ原理3

感谢 up 主 ZOMI 酱：https://space.bilibili.com/517221395

LLVM IR と GCC IR の比較#

特性	LLVM IR	GCC IR (GIMPLE)
独立性とライブラリ化アーキテクチャ	高度にモジュール化されており、フロントエンドとバックエンドが分離されていて、新しい言語やターゲットプラットフォームを追加しやすい	従来の GCC アーキテクチャで、フロントエンドとバックエンドが密接に結合されている
表現形式	人間が読めるアセンブリ形式、C++ オブジェクト形式、シリアライズされたビットコード形式	GIMPLE 表現形式、三項アドレスコード、SSA 形式
設計と応用	より独立しており、コンパイラ外のツールで再利用可能で、正式な定義と良好な C++ API があり、ハードウェアの動作に近い	制御フローの複雑さを低減し、最適化が比較的容易
適用シーン	学術界のアプリケーションに適しており、かなりの簡略化が行われているため、結果をより早く得ることができる	工業アプリケーションに適しており、統一された AST を生成してデータフロー分析を行ったり、GIMPLE のような三項アドレスコードを生成して分析を行ったりできる

LLVM IR の利点#

より独立している：LLVM IR はコンパイラ外の任意のツールで再利用できるように設計されており、静的解析ツールやインストゥルメンテーションツールなど、他のタイプのツールを簡単に統合できる。
より正式な定義とより良い C++ API：これにより、処理、変換、分析が容易になる。
よりハードウェアの動作に近い：LLVM IR は RISCV に似たシミュレーション命令セットと強い型システムを提供し、「汎用表現」の目的を達成している。

GIMPLE の利点#

制御フローの複雑さを低減：GIMPLE は制御フローの複雑さを低減し、三項アドレス表現と構文を制限することで、最適化を比較的容易にしている。

LLVM アーキテクチャ設計#

LLVM アーキテクチャ図：

LLVM コアプロセス分析#

コンパイラのフロントエンドの作業フローには、字句解析、構文解析、意味解析が含まれる。中間最適化層では大規模データの Pass 最適化が行われる。コンパイラのバックエンドの作業フローには、機械命令の選択、レジスタの割り当て、命令のスケジューリングが含まれる。

実践：Clang コンパイルプロセス#

.i ファイルを生成
```
clang -E -c .\hello.c -o .\hello.i
```

前処理された.i ファイルを.bc ファイルに変換

clang -emit-llvm .\hello.i -c -o .\hello.bc
clang -emit-llvm .\hello.c -S -o .\hello.ll

llc と lld リンカを使用

llc .\hello.ll -o .\hello.s
llc .\hello.bc -o .\hello2.s

実行可能なバイナリファイルに変換
```
clang .\hello.s -o hello
```
コンパイルプロセスを確認
```
clang -ccc-print-phases .\hello.c
```

まとめ#

LLVM コンポーネント間の相互作用は高レベルの抽象で発生し、異なるコンポーネントは個別のプログラムライブラリとして隔離され、コンパイルパイプライン全体で変換と最適化 Pass を統合しやすくなっている。現在、さまざまな静的および実行時コンパイル言語を実現するための汎用基盤として使用されている。

LLVM IR の詳細#

LLVM IR 設計理念#

LLVM IR は静的単一割り当て形式（Static single assignment、SSA）を採用しており、2 つの重要な特徴を持つ：!

SSA 静的単一割り当て#

LLVM IR では、各変数は使用前に定義されなければならず、各変数は一度だけ割り当てられる。
1 * 2 + 3 の例を挙げる：

LLVM IR 基本構文#

LLVM IR は、簡略化された命令セット（RISC）に似た低レベルの仮想命令セットであり、単純な命令の線形シーケンスをサポートしている。

LLVM IR は、簡略化された命令セット（RISC）に似た低レベルの仮想命令セットである；
実際の簡略化された命令セットと同様に、加算、減算、比較、分岐などの単純な命令の線形シーケンスをサポートしている；
命令はすべて三項アドレス形式であり、一定数の入力を受け取り、異なるレジスタに計算結果を保存する；
大多数の簡略化された命令セットとは異なり、LLVM は強い型の単純な型システムを使用し、機械の差異を排除している；
LLVM IR は固定の命名レジスタを使用せず、% 文字で命名された一時レジスタを使用する；

各三項アドレスコード命令は、四元組（4-tuple）の形式に分解できる：（演算子、オペランド 1、オペランド 2、結果）。各命令は 3 つの変数を含むため、各命令は最大 3 つのオペランドを持つため、三項アドレスコードと呼ばれる。

命令タイプ	命令形式	四元組表現
割り当て命令	`z = x op y (z = x + y)`	`(op, x, y, z)`

LLVM IR メモリモデル#

LLVM IR ファイルの基本単位は module と呼ばれる。
1 つの module には複数のトップレベルエンティティ、例えば function や global variable を持つことができる。
1 つの function define には少なくとも 1 つの basic block が含まれる。
各 basic block にはいくつかの instruction があり、すべて terminator instruction で終了する。

クラス名	詳細
`Module`	Module クラスは、全体の翻訳単位で使用されるすべてのデータを集約します。これは LLVM 用語での「module」の同義語です。Module::iterator typedef を宣言し、このモジュール内の関数を遍歴する簡便な方法を提供します。begin () および end () メソッドを使用してこれらのイテレータを取得できます。
`Function`	Function クラスは、関数の定義と宣言に関するすべてのオブジェクトを含みます。宣言の場合（isDeclaration () を使用してそれが宣言かどうかを確認）、関数プロトタイプのみを含みます。定義または宣言にかかわらず、関数パラメータのリストを含み、getArgumentList () メソッドまたは arg_begin () および arg_end () メソッドを使用してアクセスできます。Function::arg_iterator typedef を使用してそれらを遍歴できます。Function オブジェクトが関数定義を表す場合、次のような文を使用してその内容を遍歴できます：for (Function::iterator i = function.begin (), e = function.end (); i != e; ++i)、基本ブロックを遍歴します。
`BasicBlock`	BasicBlock クラスは LLVM 命令のシーケンスをカプセル化し、begin ()/end () を使用してアクセスできます。getTerminator () メソッドを使用して最後の命令に直接アクセスでき、getSinglePredecessor () を使用して前駆基本ブロックにアクセスするなど、CFG を遍歴するためのいくつかの補助関数を使用できます。基本ブロックが単一の前駆を持つ場合は、前駆リストを自分で遍歴する必要がありますが、基本ブロックを 1 つずつ遍歴し、それらの終端命令のターゲット基本ブロックを確認するだけで簡単です。
`Instruction`	Instruction クラスは LLVM IR の演算原子、単一の命令を表します。いくつかのメソッドを使用して高レベルの主張を取得できます。例えば isAssociative ()、isCommutative ()、isIdempotent ()、isTerminator () などですが、正確な機能は getOpcode () を通じて知ることができ、llvm::Instruction 列挙のメンバーを返し、LLVM IR opcode を表します。op_begin () および op_end () メソッドを使用してそのオペランドにアクセスできます。

LLVM IR メモリモデルの最も重要な概念：Value、Use、User

LLVM IR メモリモデルにおいて、Value、Use、User は 3 つのコア概念であり、これらの関係は LLVM におけるデータフローと制御フローを定義します。

概念	説明
`Value`	LLVM において、Value は非常に基本的な概念であり、定数、変数、関数など、値を持つ任意のエンティティを表します。各 Value には、LLVM 内部で自分を識別するための一意の番号があります。Value は他の指令のオペランドである可能性があるため、ユーザー（User）を持つことができます。
`Use`	Use は Value の使用例です。LLVM において、各 Value は 1 つ以上の Use を持ち、この Value がどの指令で使用されているかを示します。Use は、その Value を使用する User へのポインタと、その User 内でのオペランドインデックスを含みます。
`User`	User は Value を使用する指令または定数を指します。例えば、指令は複数のオペランドを持つことができ、各オペランドは Value であるため、その指令は User となります。User は Use オブジェクトを通じてそのオペランド Value を参照します。

これら 3 つの概念は LLVM IR のメモリモデルを構成し、これらの関係は指令間のデータ依存関係を反映します。LLVM の最適化プロセスにおいて、これらの概念は指令間の依存関係を分析し管理するために非常に重要です。

LLVM フロントエンドと最適化層#

LLVM フロントエンド#

コンパイラのフロントエンドはソースコードをコンパイラの中間表現 LLVM IR に変換します。

字句解析
フロントエンドの最初のステップは、ソースコードのテキスト入力を処理し、言語構造を一連の単語とトークンに分解し、コメント、空白、タブなどを除去します。各単語またはトークンは言語のサブセットに属する必要があり、言語の予約語はコンパイラ内部表現に変換されます。

$ clang -cc1 -dump-tokens hello.c

構文解析
トークンをグループ化して式、文、関数本体などを形成します。一連のトークンが意味を持つかどうかを確認し、コードの物理的なレイアウトを考慮し、未分析のコードの意味を考慮しません。英語の構文解析のように、何を言ったかは関係なく、文が正しいかどうかだけを考慮し、構文木（AST）を出力します。

$ clang -fsyntax-only -Xclang -ast-dump hello.c

意味解析
シンボルテーブルを使用して、コードが言語の型システムに違反していないかを検証します。シンボルテーブルは識別子とそれぞれの型とのマッピングを保存し、その他の内容を含みます。型チェックの直感的な方法は、解析後に AST を遍歴しながらシンボルテーブルから型に関する情報を収集することです。

$ clang -c hello.c

LLVM 最適化層#

最適化は通常、分析 Pass と変換 Pass で構成されます。
最適化は通常、分析 Pass と変換 Pass で構成されます。

分析 Pass：特性や最適化の機会を発掘する責任があります；
変換 Pass：必要なデータ構造を生成し、後続の処理で使用されます；

opt hello.bc -instcount -time-passes -domtree -o hello-tmp.bc -stats

LLVM バックエンドコード生成#

バックエンドアーキテクチャ#

バックエンドは一連の分析と変換 Pass で構成されており、そのタスクはコード生成です。

命令選択#

メモリ内の LLVM IR がターゲット特定の SelectionDAG ノードに変換されます。

命令スケジューリング#

第 1 回命令スケジューリング、または前レジスタ割り当て（RA）スケジューリング；
命令を並べ替え、できるだけ多くの命令の並列性を発見しようとします；
その後、命令は MachineInstr の三項アドレス表現に変換されます。

レジスタ割り当て#

レジスタ割り当ては無限の仮想レジスタ参照を有限のターゲット特定のレジスタセットに変換します。
レジスタが不足している場合は、メモリにスピルされます。

命令スケジューリング#

第 2 回命令スケジューリング、または後レジスタ割り当て（RA）スケジューリング；
この時点で実際のレジスタ情報が得られ、特定のタイプのレジスタには遅延が存在し、それらを使用して命令の順序を改善できます。

コード出力#

コード出力段階では、命令が MachineInstr 表現から MCInst インスタンスに変換されます。