LLVMターゲット非依存コードジェネレータ

警告

これは開発中です。

はじめに

LLVMターゲット非依存コードジェネレータは、LLVM内部表現を指定されたターゲットの機械コード（静的コンパイラに適したアセンブリ形式、またはJITコンパイラで使用できるバイナリ機械コード形式のどちらか）に変換するための、再利用可能なコンポーネントのスイートを提供するフレームワークです。LLVMターゲット非依存コードジェネレータは、6つの主要なコンポーネントで構成されています。

  1. 抽象的なターゲット記述インターフェースは、使用方法とは無関係に、マシンの様々な側面に関する重要なプロパティを捉えます。これらのインターフェースは、include/llvm/Target/で定義されています。

  2. ターゲットに対して生成されるコードを表すために使用されるクラス。これらのクラスは、あらゆるターゲットマシンの機械コードを表すのに十分な抽象性を持つことを意図しています。これらのクラスはinclude/llvm/CodeGen/で定義されています。このレベルでは、「定数プールエントリ」や「ジャンプテーブル」などの概念が明示的に公開されています。

  3. MCレイヤであるオブジェクトファイルレベルでコードを表すために使用されるクラスとアルゴリズム。これらのクラスは、ラベル、セクション、命令などのアセンブリレベルの構成要素を表します。このレベルでは、「定数プールエントリ」や「ジャンプテーブル」などの概念は存在しません。

  4. ターゲット非依存アルゴリズムは、ネイティブコード生成の様々なフェーズ（レジスタ割り当て、スケジューリング、スタックフレーム表現など）を実装するために使用されます。このコードはlib/CodeGen/にあります。

  5. 抽象的なターゲット記述インターフェースの実装は、特定のターゲットを対象としています。これらのマシン記述は、LLVMによって提供されるコンポーネントを利用し、必要に応じてカスタムのターゲット固有のパスを提供して、特定のターゲットのための完全なコードジェネレータを構築します。ターゲット記述はlib/Target/にあります。

  6. ターゲット非依存JITコンポーネント。LLVM JITは完全にターゲット非依存です（ターゲット固有の問題をインターフェースするためにTargetJITInfo構造を使用します。ターゲット非依存JITのコードはlib/ExecutionEngine/JITにあります。

コードジェネレータのどの部分に取り組みたいかによって、これらの異なる部分が役立ちます。いずれの場合も、ターゲット記述と機械コード表現クラスをよく理解しておく必要があります。新しいターゲットのバックエンドを追加する場合は、新しいターゲットのターゲット記述クラスを実装し、LLVMコード表現を理解する必要があります。コード生成アルゴリズムを新しく実装することに関心がある場合は、ターゲット記述と機械コード表現クラスのみに依存する必要があるため、移植性を確保できます。

コードジェネレータに必要なコンポーネント

LLVMコードジェネレータの2つの部分は、コードジェネレータのハイレベルインターフェースと、ターゲット固有のバックエンドを構築するために使用できる再利用可能なコンポーネントのセットです。最も重要な2つのインターフェース（ TargetMachine と DataLayout ）は、バックエンドをLLVMシステムに適合させるために定義する必要がある唯一のものでありますが、再利用可能なコードジェネレータコンポーネントを使用する場合は、他のコンポーネントも定義する必要があります。

この設計には、2つの重要な意味があります。1つ目は、LLVMが完全に非伝統的なコード生成ターゲットをサポートできることです。たとえば、Cバックエンドは、レジスタ割り当て、命令選択、システムによって提供される他の標準コンポーネントを必要としません。そのため、これらの2つのインターフェースのみを実装し、独自の処理を実行します。CバックエンドはLLVM 3.1リリース以降、trunkから削除されていることに注意してください。このようなコードジェネレータの別の例としては、（純粋に仮説的な）LLVMをGCC RTL形式に変換し、GCCを使用してターゲットの機械コードを出力するバックエンドがあります。

この設計はまた、組み込みコンポーネントを使用しない、根本的に異なるコードジェネレータをLLVMシステムで設計および実装できることを意味します。そうすることはまったく推奨されませんが、LLVMマシン記述モデルに適合しない根本的に異なるターゲット（たとえばFPGA）には必要になる可能性があります。

コードジェネレータのハイレベル設計

LLVMターゲット非依存コードジェネレータは、標準的なレジスタベースのマイクロプロセッサに対して効率的で高品質なコード生成をサポートするように設計されています。このモデルでのコード生成は、次の段階に分けられます。

  1. 命令選択 — このフェーズでは、入力LLVMコードをターゲット命令セットで効率的に表現する方法を決定します。この段階では、ターゲット命令セットでプログラムの初期コードを生成し、SSA形式の仮想レジスタと、ターゲットの制約や呼び出し規約による必要なレジスタ割り当てを表す物理レジスタを使用します。このステップにより、LLVMコードはターゲット命令のDAGに変換されます。

  2. スケジューリングと形成 — このフェーズでは、命令選択フェーズで生成されたターゲット命令のDAGを受け取り、命令の順序を決定し、命令を MachineInstrとしてその順序で出力します。これは命令選択セクションで説明していることに注意してください。これはSelectionDAG上で動作するためです。

  3. SSAベースのマシンコード最適化 — このオプションの段階は、命令セレクタによって生成されたSSA形式で動作する一連のマシンコード最適化で構成されます。モジュールスケジューリングやピープホール最適化などの最適化がここで機能します。

  4. レジスタ割り当て — ターゲットコードは、SSA形式の無限の仮想レジスタファイルから、ターゲットで使用される具体的なレジスタファイルに変換されます。このフェーズでは、スピルコードが導入され、プログラムからすべての仮想レジスタ参照が削除されます。

  5. プロローグ/エピローグコード挿入 — 関数のマシンコードが生成され、必要なスタック空間の量が判明したら（LLVM allocaとスピルスロットに使用されます）、関数のプロローグとエピローグコードを挿入し、「抽象的なスタック位置参照」を削除できます。この段階では、フレームポインタの削除やスタックパッキングなどの最適化を実装します。

  6. 後期マシンコード最適化 — 「最終的な」マシンコードで動作する最適化（スピルコードスケジューリングやピープホール最適化など）をここに配置できます。

  7. コード出力 — 最終段階では、ターゲットアセンブラ形式またはマシンコードのいずれかで、現在の関数のコードを実際に出力します。

コードジェネレータは、命令セレクタが高品質なネイティブ命令シーケンスを作成するために最適なパターンマッチングセレクタを使用するという前提に基づいています。パターン展開と積極的な反復ピープホール最適化に基づく代替のコードジェネレータ設計は、はるかに遅くなります。この設計により、コンパイルのさまざまな段階で複雑さのレベルが異なるコンポーネントを使用できるため、効率的なコンパイル（JIT環境にとって重要）と積極的な最適化（オフラインでコードを生成する場合に使用）が可能になります。

これらの段階に加えて、ターゲット実装は、任意のターゲット固有のパスをフローに挿入できます。たとえば、X86ターゲットは、80x87浮動小数点スタックアーキテクチャを処理するための特別なパスを使用します。特殊な要件を持つ他のターゲットは、必要に応じてカスタムパスでサポートできます。

ターゲット記述のためのTableGenの使用

ターゲット記述クラスには、ターゲットアーキテクチャの詳細な記述が必要です。これらのターゲット記述は、多くの共通情報（たとえば、add命令はsub命令とほぼ同一です）を持つことがよくあります。最大限の共通性を考慮に入れるために、LLVMコードジェネレータはTableGenの概要ツールを使用してターゲットマシンの大きな部分を記述します。これにより、ドメイン固有およびターゲット固有の抽象化を使用して繰り返しを減らすことができます。

LLVMの開発と改良が進むにつれて、ターゲット記述のより多くの部分を.td形式に移行する予定です。これにより、いくつかの利点が得られます。最も重要なのは、記述する必要があるC++コードの量と、何かを機能させる前に理解する必要があるコードジェネレータの表面積を減らすことで、LLVMの移植が容易になることです。第二に、変更が容易になります。特に、テーブルやその他のものがすべてtblgenによって出力される場合、すべてのターゲットを新しいインターフェースに更新するには、1か所（tblgen）の変更のみが必要です。

ターゲット記述クラス

LLVMターゲット記述クラス（include/llvm/Targetディレクトリにあります）は、特定のクライアントとは無関係に、ターゲットマシンの抽象的な記述を提供します。これらのクラスは、ターゲットの*抽象的な*プロパティ（命令やレジスタなど）を捉えるように設計されており、特定のコード生成アルゴリズムの一部は組み込まれていません。

すべてのターゲット記述クラス（ DataLayout クラスを除く）は、具体的なターゲット実装によってサブクラス化され、仮想メソッドが実装されるように設計されています。これらの実装にアクセスするために、 TargetMachine クラスは、ターゲットによって実装されるべきアクセサを提供します。

TargetMachineクラス

TargetMachineクラスは、get*Infoメソッド（getInstrInfo、getRegisterInfo、getFrameInfoなど）を介して、さまざまなターゲット記述クラスのターゲット固有の実装にアクセスするために使用される仮想メソッドを提供します。このクラスは、さまざまな仮想メソッドを実装する具体的なターゲット実装（例：X86TargetMachine）によって特殊化されるように設計されています。必要なターゲット記述クラスは DataLayout クラスのみですが、コードジェネレータコンポーネントを使用する場合は、他のインターフェースも実装する必要があります。

DataLayoutクラス

DataLayoutクラスは、唯一必要なターゲット記述クラスであり、拡張不可能な唯一のクラスです（新しいクラスを派生させることはできません）。DataLayoutは、ターゲットが構造体をメモリにレイアウトする方法、さまざまなデータ型の配置要件、ターゲットのポインタのサイズ、ターゲットがリトルエンディアンかビッグエンディアンかについての情報を指定します。

TargetLoweringクラス

TargetLoweringクラスは、主にSelectionDAGベースの命令セレクタによって、LLVMコードをSelectionDAG操作にどのように下げるべきかを記述するために使用されます。とりわけ、このクラスは、

  • さまざまなValueTypeに使用される初期レジスタクラス、

  • ターゲットマシンでネイティブにサポートされている操作、

  • setcc操作の戻り値の型、

  • シフト量に使用される型、および

  • 定数による除算を乗算シーケンスに変換することが有益かどうかなど、さまざまな高レベルの特性を示します。

TargetRegisterInfoクラス

TargetRegisterInfoクラスは、ターゲットのレジスタファイルとレジスタ間の相互作用を記述するために使用されます。

コードジェネレータでは、レジスタは符号なし整数で表されます。物理レジスタ（ターゲット記述に実際に存在するレジスタ）は一意の小さな番号であり、仮想レジスタは一般的に大きいです。レジスタ#0はフラグ値として予約されていることに注意してください。

プロセッサ記述の各レジスタには、関連付けられたTargetRegisterDescエントリがあり、レジスタのテキスト名（アセンブリ出力とデバッグダンプに使用）とエイリアスのセット（1つのレジスタが別のレジスタと重複しているかどうかを示すために使用）を提供します。

レジスタごとの記述に加えて、TargetRegisterInfoクラスは、プロセッサ固有のレジスタクラス（TargetRegisterClassクラスのインスタンス）のセットを公開します。各レジスタクラスには、同じプロパティを持つレジスタのセットが含まれています（たとえば、すべて32ビット整数レジスタです）。命令セレクタによって作成された各SSA仮想レジスタには、関連付けられたレジスタクラスがあります。レジスタアロケータが実行されると、仮想レジスタはセット内の物理レジスタに置き換えられます。

これらのクラスのターゲット固有の実装は、レジスタファイルのTableGenの概要記述から自動生成されます。

TargetInstrInfoクラス

TargetInstrInfoクラスは、ターゲットでサポートされているマシン命令を記述するために使用されます。記述では、オペコードのニーモニック、オペランドの数、暗黙のレジスタの使用と定義のリスト、命令が特定のターゲットに依存しないプロパティ（メモリにアクセスする、交換可能など）を持っているかどうか、およびターゲット固有のフラグを保持するなどの事項を定義します。

TargetFrameLoweringクラス

TargetFrameLowering クラスは、ターゲットのスタックフレームレイアウトに関する情報を提供するために使用されます。スタックの成長方向、各関数のエントリにおける既知のスタックアライメント、ローカル領域へのオフセットを保持します。ローカル領域へのオフセットとは、関数エントリ時のスタックポインタから、関数データ（ローカル変数、スピルロケーション）を格納できる最初の場所までのオフセットです。

TargetSubtarget クラス

TargetSubtarget クラスは、ターゲットとする特定のチップセットに関する情報を提供するために使用されます。サブターゲットは、コード生成に対して、サポートされている命令、命令のレイテンシ、命令実行の旅程（つまり、どの処理ユニットが、どのような順序で、どれだけの時間使用されるか）を知らせます。

TargetJITInfo クラス

TargetJITInfo クラスは、Just-In-Time コードジェネレータがスタブの生成など、ターゲット固有のアクティビティを実行するために使用する抽象インターフェースを公開します。TargetMachine が JIT コード生成をサポートする場合は、getJITInfo メソッドを通じてこれらのオブジェクトの1つを提供する必要があります。

マシンコード記述クラス

高レベルでは、LLVMコードは、 MachineFunction , MachineBasicBlock 、および MachineInstr インスタンス（include/llvm/CodeGen で定義）で構成されるマシン固有の表現に変換されます。この表現は完全にターゲットに依存せず、命令を最も抽象的な形式（オペコードと一連のオペランド）で表現します。この表現は、マシンコードの SSA 表現と、レジスタ割り当て済みで非 SSA 形式の両方をサポートするように設計されています。

MachineInstr クラス

ターゲットのマシン命令は、MachineInstr クラスのインスタンスとして表現されます。このクラスは、マシン命令を表す非常に抽象的な方法です。特に、オペコード番号と一連のオペランドのみを追跡します。

オペコード番号は、特定のバックエンドに対してのみ意味を持つ単純な符号なし整数です。ターゲットのすべての命令は、ターゲットの*InstrInfo.tdファイルで定義する必要があります。オペコードの列挙値はこの記述から自動生成されます。MachineInstr クラスには、命令の解釈方法（つまり、命令の意味）に関する情報は含まれていません。それについては、 TargetInstrInfo クラスを参照する必要があります。

マシン命令のオペランドには、レジスタ参照、定数整数、基本ブロック参照など、いくつかの異なる型があります。さらに、マシンオペランドは、値の定義または使用としてマークする必要があります（ただし、レジスタのみが定義として許可されます）。

慣例により、LLVMコードジェネレータは、通常とは異なる順序で出力されるアーキテクチャでも、すべてのレジスタ定義がレジスタ使用の前にくるように命令オペランドを並べ替えます。たとえば、SPARCのadd命令「add %i1, %i2, %i3」は「%i1」と「%i2」レジスタを加算し、結果を「%i3」レジスタに格納します。LLVMコードジェネレータでは、オペランドは「%i3, %i1, %i2」のように、宛先を最初に格納する必要があります。

宛先（定義）オペランドをオペランドリストの先頭に配置することには、いくつかの利点があります。特に、デバッグプリンタは命令をこのように出力します。

%r3 = add %i1, %i2

また、最初のオペランドが定義である場合、最初のオペランドのみが定義である命令の作成が容易になります。

MachineInstrBuilder.h 関数の使用

マシン命令は、include/llvm/CodeGen/MachineInstrBuilder.hファイルにあるBuildMI関数を使用して作成されます。BuildMI関数は、任意のマシン命令を簡単に構築できます。BuildMI関数の使用方法は次のとおりです。

// Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
// instruction and insert it at the end of the given MachineBasicBlock.
const TargetInstrInfo &TII = ...
MachineBasicBlock &MBB = ...
DebugLoc DL;
MachineInstr *MI = BuildMI(MBB, DL, TII.get(X86::MOV32ri), DestReg).addImm(42);

// Create the same instr, but insert it before a specified iterator point.
MachineBasicBlock::iterator MBBI = ...
BuildMI(MBB, MBBI, DL, TII.get(X86::MOV32ri), DestReg).addImm(42);

// Create a 'cmp Reg, 0' instruction, no destination reg.
MI = BuildMI(MBB, DL, TII.get(X86::CMP32ri8)).addReg(Reg).addImm(42);

// Create an 'sahf' instruction which takes no operands and stores nothing.
MI = BuildMI(MBB, DL, TII.get(X86::SAHF));

// Create a self looping branch instruction.
BuildMI(MBB, DL, TII.get(X86::JNE)).addMBB(&MBB);

定義オペランド（オプションの宛先レジスタ以外）を追加する必要がある場合は、明示的にそのようにマークする必要があります。

MI.addReg(Reg, RegState::Define);

固定（事前割り当て）レジスタ

コードジェネレータが認識する必要がある重要な問題の1つは、固定レジスタの存在です。特に、命令ストリームには、レジスタアロケータが特定の値を特定のレジスタに配置する必要がある場所が頻繁にあります。これは、命令セットの制限（たとえば、X86はEAX/EDXレジスタを使用して32ビット除算のみを実行できます）、または呼び出し規約などの外部要因によって発生する可能性があります。いずれの場合でも、命令セレクタは必要に応じて仮想レジスタを物理レジスタに出入りさせるコードを出力する必要があります。

たとえば、この単純なLLVM例を考えてみましょう。

define i32 @test(i32 %X, i32 %Y) {
  %Z = sdiv i32 %X, %Y
  ret i32 %Z
}

X86命令セレクタは、divとretに対してこのマシンコードを生成する可能性があります。

;; Start of div
%EAX = mov %reg1024           ;; Copy X (in reg1024) into EAX
%reg1027 = sar %reg1024, 31
%EDX = mov %reg1027           ;; Sign extend X into EDX
idiv %reg1025                 ;; Divide by Y (in reg1025)
%reg1026 = mov %EAX           ;; Read the result (Z) out of EAX

;; Start of ret
%EAX = mov %reg1026           ;; 32-bit return value goes in EAX
ret

コード生成の最後に、レジスタアロケータはレジスタを統合し、結果として生じる同一性移動を削除して、次のコードを生成します。

;; X is in EAX, Y is in ECX
mov %EAX, %EDX
sar %EDX, 31
idiv %ECX
ret

このアプローチは非常に一般的であり（X86アーキテクチャを処理できる場合は、何でも処理できます！）、命令ストリームに関するターゲット固有の知識をすべて命令セレクタに分離できます。良好なコード生成のためには、物理レジスタの寿命は短くする必要があり、すべての物理レジスタは、基本ブロックのエントリと終了時（レジスタ割り当て前）にはデッドとみなされます。したがって、値を基本ブロックの境界を越えて有効にする必要がある場合、それは必ず仮想レジスタに存在する必要があります。

呼び出しで変更されるレジスタ

呼び出しなどのマシン命令の中には、多数の物理レジスタを変更するものがあります。それらすべてに<def,dead>オペランドを追加する代わりに、MO_RegisterMaskオペランドを使用できます。レジスタマスクオペランドは保存されたレジスタのビットマスクを保持し、それ以外はすべて命令によって変更されたと見なされます。

SSA形式のマシンコード

MachineInstrは、最初はSSA形式で選択され、レジスタ割り当てが行われるまでSSA形式で維持されます。LLVMはすでにSSA形式であるため、ほとんどの場合、これは非常に簡単です。LLVMのPHIノードはマシンコードのPHIノードになり、仮想レジスタは単一の定義のみを持つことができます。

レジスタ割り当て後、コードには仮想レジスタが残っていないため、マシンコードはSSA形式ではなくなります。

MachineBasicBlock クラス

MachineBasicBlockクラスには、マシン命令のリスト（ MachineInstr インスタンス）が含まれています。これは、命令セレクタへのLLVMコード入力にほぼ対応していますが、1対多のマッピング（つまり、1つのLLVM基本ブロックが複数マシン基本ブロックにマップされる可能性があります）が存在する可能性があります。MachineBasicBlockクラスには、「getBasicBlock」メソッドがあり、そこから取得したLLVM基本ブロックを返します。

MachineFunction クラス

MachineFunctionクラスには、マシン基本ブロックのリスト（ MachineBasicBlock インスタンス）が含まれています。これは、命令セレクタへのLLVM関数入力と1対1に対応します。基本ブロックのリストに加えて、MachineFunctionには、MachineConstantPool、MachineFrameInfo、MachineFunctionInfo、MachineRegisterInfoが含まれています。詳細については、include/llvm/CodeGen/MachineFunction.hを参照してください。

MachineInstr バンドル

LLVMコードジェネレータは、命令のシーケンスをMachineInstrバンドルとしてモデル化できます。MIバンドルは、任意の数の並列命令を含むVLIWグループ/パックをモデル化できます。また、合法的に分離できない命令の連続リスト（データ依存関係がある可能性があります）（例：ARM Thumb2 ITブロック）をモデル化するためにも使用できます。

概念的には、MIバンドルは、いくつかの他のMIがネストされたMIです。

--------------
|   Bundle   | ---------
--------------          \
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |           ----------------
       |           |      MI      |
       |           ----------------
       |
--------------
|   Bundle   | --------
--------------         \
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |                  ...
       |
--------------
|   Bundle   | --------
--------------         \
       |
      ...

MIバンドルサポートは、MachineBasicBlockとMachineInstrの物理的な表現を変更しません。すべてのMI（最上位レベルのものとネストされたものも含む）は、MIのシーケンシャルリストとして格納されます。「バンドルされた」MIは、「InsideBundle」フラグでマークされます。特別なBUNDLEオペコードを持つ最上位レベルのMIは、バンドルの開始を表すために使用されます。バンドル内にもバンドルを表すものでもない個々のMIとBUNDLE MIを混在させることは合法です。

MachineInstrパスは、MIバンドルを単一ユニットとして操作する必要があります。メンバメソッドは、バンドルとバンドル内のMIを正しく処理するように設計されています。MachineBasicBlockイテレータは、バンドルされたMIをスキップして、バンドルを単一ユニットとする概念を強制するように変更されました。代替イテレータinstr_iteratorがMachineBasicBlockに追加され、パスがバンドル内にネストされているものも含めて、MachineBasicBlock内のすべてのMIを反復処理できるようにしました。最上位レベルのBUNDLE命令は、バンドルされたMIの累積入力と出力を表すレジスタMachineOperandの正しいセットを持っている必要があります。

VLIWアーキテクチャのMachineInstrのパッキング/バンドリングは、一般的にレジスタ割り当てスーパーパスの一部として行う必要があります。より具体的には、どのMIを一緒にバンドルするかを決定するパスは、コードジェネレータがSSA形式を終了した後（つまり、2アドレスパス、PHI除去、コピー結合の後）に行う必要があります。このようなバンドルは、仮想レジスタが物理レジスタに書き換えられた後に最終化されます（つまり、BUNDLE MIと入力および出力レジスタMachineOperandを追加します）。これにより、仮想レジスタオペランドをBUNDLE命令に追加する必要がなくなり、仮想レジスタの定義と使用リストが事実上倍増することを防ぎます。バンドルは仮想レジスタを使用し、SSA形式で形成できますが、すべてのユースケースに適しているとは限りません。

「MC」レイヤ

MCレイヤは、生の機械コードレベルでコードを表し処理するために使用され、「定数プール」、「ジャンプテーブル」、「グローバル変数」などのような「高レベル」の情報はありません。このレベルでは、LLVMはオブジェクトファイル内のラベル名、機械命令、セクションなどを処理します。このレイヤのコードは、いくつかの重要な目的で使用されます。コードジェネレータの最後尾では、.sファイルまたは.oファイルを作成するために使用され、llvm-mcツールでもスタンドアロンの機械コードアセンブラと逆アセンブラを実装するために使用されます。

このセクションでは、いくつかの重要なクラスについて説明します。このレイヤで相互作用する多くの重要なサブシステムもあり、これらについてはこのマニュアルの後半で説明します。

MCStreamer API

MCStreamerは、アセンブラAPIとして考えるのが最適です。これは抽象的なAPIであり、異なる方法で実装されます（例：.sファイルを出力する、ELF .oファイルを出力するなど）。しかし、そのAPIは.sファイルで見られるものと直接対応しています。MCStreamerには、EmitLabel、EmitSymbolAttribute、switchSection、emitValue（.byte、.word用）など、アセンブリレベルのディレクティブに直接対応するディレクティブごとに1つのメソッドがあります。また、MCInstをストリーマーに出力するために使用されるEmitInstructionメソッドもあります。

このAPIは、2つのクライアントにとって最も重要です。llvm-mcスタンドアロンアセンブラは、事実上、行を解析するパーサーであり、次にMCStreamerのメソッドを呼び出します。コードジェネレータでは、コードエミッションフェーズは、より高レベルのLLVM IRとMachine*コンストラクトをMCレイヤに落とし込み、MCStreamerを介してディレクティブを出力します。

MCStreamerの実装側には、.sファイルを出力するためのもの（MCAsmStreamer）と.oファイルを出力するためのもの（MCObjectStreamer）の2つの主要な実装があります。MCAsmStreamerは、各メソッドに対してディレクティブを出力する簡単な実装です（例：EmitValue -> .byte）。しかし、MCObjectStreamerは完全なアセンブラを実装しています。

ターゲット固有のディレクティブについては、MCStreamerはMCTargetStreamerインスタンスを持っています。それを必要とする各ターゲットは、それから継承するクラスを定義し、MCStreamer自体と非常によく似ています。ディレクティブごとに1つのメソッドと、それから継承する2つのクラス（ターゲットオブジェクトストリーマーとターゲットasmストリーマー）があります。ターゲットasmストリーマーはそれを印刷するだけです（emitFnStart -> .fnstart）。オブジェクトストリーマーは、それに対するアセンブラロジックを実装します。

LLVMでこれらのクラスを使用するには、ターゲット初期化で、対応するターゲットストリーマーを割り当てるコールバックを渡してTargetRegistry::RegisterAsmStreamerとTargetRegistry::RegisterMCObjectStreamerを呼び出し、createAsmStreamerまたは適切なオブジェクトストリーマーコンストラクタに渡す必要があります。

MCContextクラス

MCContextクラスは、シンボル、セクションなど、MCレイヤのさまざまな一意のデータ構造の所有者です。そのため、これはシンボルとセクションを作成するためにやり取りするクラスです。このクラスはサブクラス化できません。

MCSymbolクラス

MCSymbolクラスは、アセンブリファイルのシンボル（別名ラベル）を表します。興味深い2種類のシンボルがあります。アセンブラ一時シンボルと通常のシンボルです。アセンブラ一時シンボルは、アセンブラによって使用および処理されますが、オブジェクトファイルが生成されるときに破棄されます。この違いは、通常、ラベルにプレフィックスを追加することで表されます。たとえば、「L」ラベルはMachOのアセンブラ一時ラベルです。

MCSymbolはMCContextによって作成され、そこで一意になります。つまり、MCSymbolをポインタの等価性で比較して、同じシンボルかどうかを調べることができます。ただし、ポインタの不等式は、ラベルが異なるアドレスに終わることを保証するものではありません。.sファイルに次のようなものを出力することは完全に合法です。

foo:
bar:
  .byte 4

この場合、fooシンボルとbarシンボルの両方が同じアドレスを持つことになります。

MCSectionクラス

MCSectionクラスは、オブジェクトファイル固有のセクションを表します。オブジェクトファイル固有の実装（例：MCSectionMachO、MCSectionCOFF、MCSectionELF）によってサブクラス化され、これらはMCContextによって作成され、一意になります。MCStreamerは現在のセクションの概念を持っており、SwitchToSectionメソッド（.sファイルの「.section」ディレクティブに対応）を使用して変更できます。

MCInstクラス

MCInstクラスは、命令のターゲットに依存しない表現です。MachineInstrよりもはるかに単純なクラスであり、ターゲット固有のオペコードとMCOperandのベクトルを保持します。MCOperandは、3つのケースの単純な弁別的共用体です。1）単純な即値、2）ターゲットレジスタID、3）シンボリックな式（例：「Lfoo-Lbar+42」）をMCExprとして。

MCInstは、MCレイヤで機械命令を表すために使用される共通の通貨です。これは、命令エンコーダ、命令プリンタで使用される型であり、アセンブラパーサーと逆アセンブラによって生成される型です。

オブジェクトファイル形式

MCレイヤのオブジェクトライターは、さまざまなオブジェクト形式をサポートしています。オブジェクト形式のターゲット固有の側面のため、各ターゲットはMCレイヤによってサポートされる形式のサブセットのみをサポートしています。ほとんどのターゲットはELFオブジェクトの出力に対応しています。他のベンダー固有のオブジェクトは、一般的に、そのベンダーによってサポートされているターゲットでのみサポートされています（つまり、MachOはDarwinによってサポートされているターゲットでのみサポートされ、XCOFFはAIXをサポートしているターゲットでのみサポートされます）。さらに、一部のターゲットには独自のオブジェクト形式があります（つまり、DirectX、SPIR-V、WebAssembly）。

以下の表は、LLVMでのオブジェクトファイルサポートのスナップショットを示しています。

表 101 オブジェクトファイル形式

形式

サポート対象

COFF

AArch64、ARM、X86

DXContainer

DirectX

ELF

AArch64、AMDGPU、ARM、AVR、BPF、CSKY、Hexagon、Lanai、LoongArch、M86k、MSP430、MIPS、PowerPC、RISCV、SPARC、SystemZ、VE、X86

GOFF

SystemZ

MachO

AArch64、ARM、X86

SPIR-V

SPIRV

WASM

WebAssembly

XCOFF

PowerPC

ターゲットに依存しないコード生成アルゴリズム

このセクションでは、コードジェネレータの高レベル設計で説明されているフェーズについて説明します。それらがどのように機能するか、およびそれらの設計の背後にある理由の一部について説明します。

命令選択

命令選択は、コードジェネレータに提示されたLLVMコードをターゲット固有の機械命令に変換するプロセスです。文献には、これを行うためのいくつかのよく知られた方法があります。LLVMは、SelectionDAGベースの命令セレクタを使用します。

DAG命令セレクタの一部は、ターゲット記述（*.td）ファイルから生成されます。私たちの目標は、命令セレクタ全体をこれらの.tdファイルから生成することですが、現在でもカスタムC++コードが必要な部分があります。

GlobalISelは、別の命令選択フレームワークです。

SelectionDAGの紹介

SelectionDAGは、自動的な手法（例：動的計画法に基づく最適なパターンマッチングセレクタ）を使用して命令選択に適した方法でコード表現の抽象化を提供します。これは、コード生成の他のフェーズ、特に命令スケジューリングにも適しています（SelectionDAGは、選択後のスケジューリングDAGに非常に近いです）。さらに、SelectionDAGは、非常に低レベル（ただしターゲットに依存しない）最適化を幅広く実行できるホスト表現を提供します。これは、ターゲットによって効率的にサポートされる命令に関する広範な情報が必要です。

SelectionDAGは、ノードがSDNodeクラスのインスタンスである有向非巡回グラフです。SDNodeの主なペイロードは、ノードが実行する操作と操作のオペランドを示すオペコード（Opcode）です。さまざまな操作ノードの種類は、include/llvm/CodeGen/ISDOpcodes.hファイルの先頭で説明されています。

ほとんどの演算は単一の値を定義しますが、グラフ内の各ノードは複数の値を定義する場合があります。たとえば、組み合わせたdiv/rem演算は、商と剰余の両方を定義します。多くの他の状況でも複数の値が必要になります。各ノードは、使用される値を定義するノードへのエッジである、いくつかのオペランドも持っています。ノードは複数の値を定義できるため、エッジはSDValueクラスのインスタンスで表されます。これは<SDNode, unsigned>のペアであり、それぞれ使用されるノードと結果の値を示します。SDNodeによって生成される各値には、値の型を示す関連付けられたMVT（マシン値型）があります。

SelectionDAGには、データフローを表す値と、制御フローの依存関係を表す値の2種類の値が含まれています。データ値は、整数型または浮動小数点型の単純なエッジです。制御エッジは、MVT::Other型の「チェーン」エッジとして表されます。これらのエッジは、副作用を持つノード（ロード、ストア、コール、リターンなど）間の順序付けを提供します。副作用を持つすべてのノードは、トークンチェーンを入力として受け取り、新しいトークンチェーンを出力として生成する必要があります。慣例により、トークンチェーン入力は常にオペランド＃0であり、チェーン結果は常に演算によって生成される最後の値です。ただし、命令選択後、マシンノードは命令のオペランドの後にチェーンを持ち、グルーノードが続く場合があります。

SelectionDAGには、指定された「エントリ」ノードと「ルート」ノードがあります。エントリノードは常に、ISD::EntryTokenのオペコードを持つマーカーノードです。ルートノードは、トークンチェーンにおける最後の副作用のあるノードです。たとえば、単一の基本ブロック関数では、リターンノードになります。

SelectionDAGにとって重要な概念の1つは、「合法的な」DAGと「非合法的な」DAGの概念です。ターゲットに対する合法的なDAGとは、サポートされている演算とサポートされている型のみを使用するDAGです。たとえば、32ビットPowerPCでは、i1、i8、i16、またはi64型の値を持つDAG、またはSREMまたはUREM演算を使用するDAGは非合法です。型を合法化するフェーズと演算を合法化するフェーズは、非合法的なDAGを合法的なDAGに変換する役割を担っています。

SelectionDAG命令選択プロセス

SelectionDAGベースの命令選択は、次の手順で構成されます。

  1. 初期DAGの構築 — この段階では、入力LLVMコードから非合法なSelectionDAGへの単純な変換を実行します。

  2. SelectionDAGの最適化 — この段階では、SelectionDAGに対して単純な最適化を実行して簡素化し、これらのメタ演算をサポートするターゲットに対してメタ命令（回転やdiv/remペアなど）を認識します。これにより、結果のコードがより効率的になり、DAGからの命令の選択フェーズ（下記）が簡素化されます。

  3. SelectionDAG型の合法化 — この段階では、ターゲットでサポートされていない型を排除するためにSelectionDAGノードを変換します。

  4. SelectionDAGの最適化 — 型の合法化によって公開された冗長性を解消するために、SelectionDAG最適化器が実行されます。

  5. SelectionDAG演算の合法化 — この段階では、ターゲットでサポートされていない演算を排除するためにSelectionDAGノードを変換します。

  6. SelectionDAGの最適化 — 演算の合法化によって導入された非効率性を排除するために、SelectionDAG最適化器が実行されます。

  7. DAGからの命令の選択 — 最後に、ターゲット命令セレクタは、DAG演算をターゲット命令にマッピングします。このプロセスは、ターゲットに依存しない入力DAGを、ターゲット命令の別のDAGに変換します。

  8. SelectionDAGのスケジューリングと形成 — 最後のフェーズでは、ターゲット命令DAG内の命令に線形順序を割り当て、コンパイルされているMachineFunctionに出力します。このステップでは、従来のプリパススケジューリング手法を使用します。

これらの手順がすべて完了すると、SelectionDAGは破棄され、残りのコード生成パスが実行されます。

これらのステップをデバッグする最も一般的な方法の1つは、-debug-only=iselを使用することです。これにより、これらの各ステップの後、デバッグ情報などの他の情報とともにDAGが出力されます。あるいは、-debug-only=isel-dumpはDAGダンプのみを表示しますが、結果は-filter-print-funcs=<function names>を使用して関数名でフィルタリングできます。

ここで何が起こっているかを視覚化する優れた方法の1つは、いくつかのLLCコマンドラインオプションを利用することです。次のオプションは、特定のタイミングでSelectionDAGを表示するウィンドウを表示します（これを使用中にコンソールにエラーのみが表示される場合、おそらくシステムを構成してサポートを追加する必要があります）。

  • -view-dag-combine1-dagsは、最初の最適化パスを実行する前の、構築後のDAGを表示します。

  • -view-legalize-dagsは、合法化前のDAGを表示します。

  • -view-dag-combine2-dagsは、2回目の最適化パス前のDAGを表示します。

  • -view-isel-dagsは、選択フェーズ前のDAGを表示します。

  • -view-sched-dagsは、スケジューリング前のDAGを表示します。

-view-sunit-dagsは、スケジューラの依存関係グラフを表示します。このグラフは最終的なSelectionDAGに基づいており、一緒にスケジュールする必要があるノードは単一のスケジューリングユニットノードにバンドルされ、スケジューリングに関係のない即時オペランドや他のノードは省略されています。

-filter-view-dagsオプションを使用すると、視覚化したい基本ブロックの名前を選択し、前のview-*-dagsオプションをすべてフィルタリングできます。

初期SelectionDAGの構築

初期SelectionDAGは、SelectionDAGBuilderクラスによって、LLVM入力から単純にピープホール展開されます。このパスの目的は、可能な限り低レベルのターゲット固有の詳細をSelectionDAGに公開することです。このパスはほとんどハードコードされています（例：LLVM addはSDNode addになり、getelementptrは明らかな算術演算に展開されます）。このパスには、コール、リターン、可変長引数などを削減するためのターゲット固有のフックが必要です。これらの機能については、 TargetLowering インターフェースが使用されます。

SelectionDAG LegalizeTypesフェーズ

合法化フェーズは、DAGをターゲットでネイティブにサポートされている型のみを使用するように変換する役割を担っています。

サポートされていないスカラー型の値をサポートされている型の値に変換するには、主に2つの方法があります。小さい型を大きい型に変換する（「昇格」）ことと、大きな整数型を小さな型に分割する（「展開」）ことです。たとえば、ターゲットでは、すべてのf32値をf64に昇格させ、すべてのi1/i8/i16値をi32に昇格させる必要がある場合があります。同じターゲットでは、すべてのi64値をi32値のペアに展開する必要がある場合があります。これらの変更により、必要に応じて符号拡張とゼロ拡張を挿入して、最終的なコードが入力と同じ動作をするようにすることができます。

サポートされていないベクトル型の値をサポートされている型の値に変換するには、主に2つの方法があります。ベクトル型を必要に応じて複数回分割して合法的な型が見つかるまで分割することと、要素を最後に追加して合法的な型に丸めることによってベクトル型を拡張する（「拡大」）ことです。ベクトルがサポートされているベクトル型が見つからない単一要素の部分まで完全に分割された場合、要素はスカラーに変換されます（「スカラー化」）。

ターゲット実装は、TargetLoweringコンストラクタでaddRegisterClassメソッドを呼び出すことによって、サポートされている型（およびそれらに使用するレジスタクラス）を合法化ツールに伝えます。

SelectionDAG合法化フェーズ

合法化フェーズは、DAGをターゲットでネイティブにサポートされている演算のみを使用するように変換する役割を担っています。

ターゲットには、サポートされているデータ型ごとにすべての演算をサポートしていないなど、奇妙な制約があることがよくあります（例：X86はバイト条件付き移動をサポートしておらず、PowerPCは16ビットメモリ位置からの符号拡張ロードをサポートしていません）。合法化は、演算をエミュレートする別の演算シーケンスをオープンコーディングする（「展開」）、演算をサポートするより大きな型に型を昇格させる（「昇格」）、または合法化を実装するためにターゲット固有のフックを使用する（「カスタム」）ことによって、この問題に対処します。

ターゲット実装は、TargetLoweringコンストラクタでsetOperationActionメソッドを呼び出すことによって、サポートされていない演算（および上記の3つのアクションのどれを実行するか）を合法化ツールに伝えます。

ターゲットに合法的なベクトル型がある場合、それらの型を使用してshufflevector IR命令の一般的な形式に対して効率的なマシンコードを生成することが期待されます。これには、shufflevector IRから作成されたSelectionDAGベクトル演算のカスタム合法化が必要になる場合があります。処理する必要があるshufflevector形式には、次のようなものがあります。

  • ベクトル選択 — ベクトルの各要素は、2つの入力ベクトルの対応する要素のいずれかから選択されます。この演算は、ターゲットアセンブリでは「ブレンド」または「ビット単位選択」としても知られています。このタイプのシャッフルは、shuffle_vector SelectionDAGノードに直接マップされます。

  • サブベクトルの挿入 — ベクタは、インデックス0から始まるより長いベクタ型に配置されます。このタイプのシャッフルは、indexオペランドが0に設定されたinsert_subvector SelectionDAGノードに直接マップされます。

  • サブベクトルの抽出 — ベクタは、インデックス0から始まるより長いベクタ型から取得されます。このタイプのシャッフルは、indexオペランドが0に設定されたextract_subvector SelectionDAGノードに直接マップされます。

  • Splat — ベクタのすべての要素が同一のスカラー要素を持つ。この操作は、ターゲットアセンブリでは「ブロードキャスト」または「複製」としても知られている。shufflevector IR命令はベクタ長を変更する可能性があるため、この操作はshuffle_vector、concat_vectors、insert_subvector、extract_subvectorを含む複数のSelectionDAGノードにマッピングされる可能性がある。

Legalizeパスが存在する前、すべてのターゲットセレクタが、ネイティブにサポートされていない場合でも、すべての演算子と型をサポートし処理することが要求されていた。Legalizeフェーズの導入により、すべての正規化パターンをターゲット間で共有することが可能になり、DAGの形式のままなので、正規化されたコードを最適化することが非常に容易になる。

SelectionDAG最適化フェーズ：DAGコンバイナ

SelectionDAG最適化フェーズは、コード生成のために複数回実行され、DAGが構築された直後と、各合法化の後に1回実行される。パスの初回実行により、初期コードをクリーンアップすることができる（例：演算子が制限された型の入力を有することを知っていることに依存する最適化を実行する）。パスの後続の実行は、Legalizeパスによって生成された混乱したコードをクリーンアップし、Legalizeを非常にシンプルにする（良い合法的なコードを生成することに集中するのではなく、コードを合法的にすることに集中できる）。

実行される最適化の重要なクラスの1つは、挿入された符号拡張命令とゼロ拡張命令の最適化である。現在、アドホックな手法を使用しているが、将来的にはより厳密な手法に移行できる。このトピックに関する優れた論文をいくつか紹介する。

“整数算術の拡張”
Kevin Redwine and Norman Ramsey
コンパイラ構成に関する国際会議（CC）2004

“効果的な符号拡張の削除”
Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani
プログラミング言語設計と実装に関するACM SIGPLAN 2002会議論文集。

SelectionDAG選択フェーズ

選択フェーズは、命令選択のためのターゲット固有コードの大部分である。このフェーズは、合法的なSelectionDAGを入力として受け取り、ターゲットによってサポートされる命令をこのDAGにパターンマッチングし、ターゲットコードの新しいDAGを生成する。例えば、次のLLVMフラグメントを考えてみよう。

%t1 = fadd float %W, %X
%t2 = fmul float %t1, %Y
%t3 = fadd float %t2, %Z

このLLVMコードは、基本的に次のようなSelectionDAGに対応する。

(fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)

ターゲットが浮動小数点乗算加算（FMA）演算をサポートしている場合、加算の1つは乗算とマージできる。例えばPowerPCでは、命令セレクタの出力が次のDAGのように見える可能性がある。

(FMADDS (FADDS W, X), Y, Z)

FMADDS命令は、最初の2つのオペランドを乗算し、3番目のオペランドを加算する三項演算（単精度浮動小数点数として）である。FADDS命令は、単純な二項単精度加算命令である。このパターンマッチングを実行するために、PowerPCバックエンドには次の命令定義が含まれている。

def FMADDS : AForm_1<59, 29,
                    (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRC, F4RC:$FRB),
                    "fmadds $FRT, $FRA, $FRC, $FRB",
                    [(set F4RC:$FRT, (fadd (fmul F4RC:$FRA, F4RC:$FRC),
                                           F4RC:$FRB))]>;
def FADDS : AForm_2<59, 21,
                    (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRB),
                    "fadds $FRT, $FRA, $FRB",
                    [(set F4RC:$FRT, (fadd F4RC:$FRA, F4RC:$FRB))]>;

命令定義の強調表示された部分は、命令のマッチングに使用されるパターンを示している。DAG演算子（fmul/faddなど）は、include/llvm/Target/TargetSelectionDAG.tdファイルで定義されている。“F4RC”は、入力値と結果値のレジスタクラスである。

TableGen DAG命令セレクタジェネレータは、.tdファイルの命令パターンを読み取り、ターゲットのパターンマッチングコードの一部を自動的に構築する。次のような利点がある。

  • コンパイラのコンパイル時に、命令パターンを分析し、パターンが意味を持つかどうかを知らせてくれる。

  • パターンマッチングに対するオペランドの任意の制約を処理できる。特に、「13ビット符号拡張値である任意の即値に一致する」といったことを簡単に指定できる。例として、PowerPCバックエンドのimmSExt16および関連するtblgenクラスを参照。

  • 定義されたパターンに対していくつかの重要な同一性を認識している。例えば、加算は可換であることを認識しているので、上記のFMADDSパターンは「(fadd X, (fmul Y, Z))」と「(fadd (fmul X, Y), Z)」の両方に一致する。ターゲット作成者がこのケースを特別に処理する必要はない。

  • 完全な機能を備えた型推論システムを備えている。特に、パターンのどの部分がどのような型であるかを明示的にシステムに伝える必要はほとんどない。上記のFMADDSの例では、パターン内のすべてのノードが型「f32」であることをtblgenに伝える必要はなかった。F4RCが型「f32」であるという事実から、この知識を推論して伝播することができた。

  • ターゲットは、独自の（そして組み込みの）「パターンフラグメント」を定義できる。パターンフラグメントは、コンパイラのコンパイル時にパターンにインライン化される、再利用可能なパターンのチャンクである。例えば、整数「(not x)」演算は、実際には「(xor x, -1)」として展開されるパターンフラグメントとして定義されている。SelectionDAGにはネイティブの「not」演算がないためである。ターゲットは必要に応じて独自の省略記号フラグメントを定義できる。「not」と「ineg」の定義を参照。

  • 命令に加えて、ターゲットは「Pat」クラスを使用して、1つ以上の命令にマッピングされる任意のパターンを指定できる。例えば、PowerPCには、任意の整数即値を1つの命令でレジスタにロードする方法がない。tblgenにこれを行う方法を伝えるために、次のように定義している。

    // Arbitrary immediate support.  Implement in terms of LIS/ORI.
def : Pat<(i32 imm:$imm),
          (ORI (LIS (HI16 imm:$imm)), (LO16 imm:$imm))>;

    レジスタへの即値のロードに関する単一命令のパターンのいずれにも一致しない場合、これが使用される。このルールは、「任意のi32即値に一致し、ORI（「16ビット即値をORする」）とLIS（「16ビット即値をロードする。即値は左に16ビットシフトされる」）命令に変換する」ことを意味する。これを機能させるために、LO16/HI16ノード変換を使用して入力即値を操作する（この場合は、即値の高位または低位16ビットを取得する）。

  • 「Pat」クラスを使用して、1つ以上の複雑なオペランドを持つ命令にパターンをマッピングする場合（例：X86アドレスモード）、パターンはComplexPatternを使用してオペランド全体を指定するか、または複雑なオペランドのコンポーネントを個別に指定するかのいずれかである。後者は、PowerPCバックエンドによってプリインクリメント命令に対して実行される。

    def STWU  : DForm_1<37, (outs ptr_rc:$ea_res), (ins GPRC:$rS, memri:$dst),
                "stwu $rS, $dst", LdStStoreUpd, []>,
                RegConstraint<"$dst.reg = $ea_res">, NoEncode<"$ea_res">;

def : Pat<(pre_store GPRC:$rS, ptr_rc:$ptrreg, iaddroff:$ptroff),
          (STWU GPRC:$rS, iaddroff:$ptroff, ptr_rc:$ptrreg)>;

    ここで、ptroffとptrregオペランドのペアは、STWU命令のクラスmemriの複雑なオペランドdstにマッチングされる。

  • システムは多くのことを自動化しているが、表現が難しいものがあれば、特殊なケースに一致するカスタムC++コードを記述することもできる。

多くの利点がある一方で、システムには現在いくつかの制限がある。主に、進行中の作業であり、まだ完成していないためである。

  • 全体的に、複数の値を定義するSelectionDAGノード（例：SMUL_LOHI、LOAD、CALLなど）を定義またはマッチングする方法はない。これは、現在も命令セレクタのためにカスタムC++コードを記述する必要がある最大の理由である。

  • 複雑なアドレスモードのマッチングをサポートする優れた方法はまだない。将来的には、パターンフラグメントを拡張して複数の値を定義できるようにする（例：現在カスタムC++コードでマッチングされているX86アドレスモードの4つのオペランド）。さらに、フラグメントを拡張して、フラグメントが複数の異なるパターンにマッチングできるようにする。

  • isStore/isLoadなどのフラグは自動的に推論されない。

  • Legalizerに対してサポートされているレジスタと演算のセットは自動的に生成されない。

  • カスタム合法化ノードを組み込む方法はまだない。

これらの制限にもかかわらず、命令セレクタジェネレータは、典型的な命令セットのバイナリ演算と論理演算のほとんどに対して非常に役立つ。問題が発生したり、何かを行う方法が分からなくなったりした場合は、Chrisに連絡してください！

SelectionDAGスケジューリングと形成フェーズ

スケジューリングフェーズは、選択フェーズからのターゲット命令のDAGを受け取り、順序を割り当てる。スケジューラは、マシンのさまざまな制約（つまり、レジスタ圧力が最小限になるように順序付けする、または命令のレイテンシをカバーするように試みる）に応じて順序を選択できる。順序が確定したら、DAGはのリストに変換される。 MachineInstrとしてそして、SelectionDAGは破棄される。

このフェーズは論理的には命令選択フェーズとは別々だが、SelectionDAGを操作するため、コード内では密接に関連していることに注意。

SelectionDAGの今後の方向性

  1. 関数ごとの選択のオプション化。

  2. .tdファイルからセレクタ全体を自動生成する。

SSAベースのマシンコード最適化

未記述

ライブインターバル

ライブインターバルとは、変数が*ライブ*である範囲（インターバル）です。これらは、レジスタアロケータパスの一部で使用され、同じ物理レジスタを必要とする2つ以上の仮想レジスタがプログラムの同じ時点でライブであるかどうか（つまり、競合するかどうか）を判断します。このような状況が発生した場合、1つの仮想レジスタを*スピル*する必要があります。

ライブ変数解析

変数のライブインターバルを決定する最初のステップは、命令の直後にデッドになるレジスタの集合（つまり、命令が値を計算するが、決して使用されない）と、命令で使用されるが、命令の後では決して使用されないレジスタの集合（つまり、キルされる）を計算することです。ライブ変数の情報は、関数の各*仮想*レジスタと*レジスタ割り当て可能*な物理レジスタに対して計算されます。これは、SSAを使用して仮想レジスタ（SSA形式）のライフタイム情報をスパースに計算し、ブロック内の物理レジスタのみを追跡する必要があるため、非常に効率的な方法で行われます。レジスタ割り当ての前に、LLVMは物理レジスタが単一の基本ブロック内でのみライブであると仮定できます。これにより、各基本ブロック内で物理レジスタのライフタイムを解決するために、単一のローカル解析を実行できます。物理レジスタがレジスタ割り当て可能でない場合（スタックポインタや条件コードなど）、追跡されません。

物理レジスタは、関数内に出入りする際にライブになる可能性があります。ライブイン値は通常、レジスタ内の引数です。ライブアウト値は通常、レジスタ内の戻り値です。ライブイン値はそのようにマークされ、ライブインターバル解析中にダミーの「定義」命令が与えられます。関数の最後の基本ブロックがreturnである場合、関数のすべてのライブアウト値を使用しているとマークされます。

PHIノードは、関数のCFGの深さ優先トラバーサルからのライブ変数情報の計算では、PHIノードで使用される仮想レジスタが使用される前に定義されているとは保証されないため、特別に処理する必要があります。PHIノードが検出された場合、使用は他の基本ブロックで処理されるため、定義のみが処理されます。

現在の基本ブロックの各PHIノードについて、現在の基本ブロックの最後に代入をシミュレートし、後続の基本ブロックをトラバースします。後続の基本ブロックにPHIノードがあり、PHIノードのオペランドの1つが現在の基本ブロックから来ている場合、変数は現在の基本ブロックとそのすべての先行基本ブロック内で*ライブ*としてマークされ、定義命令を持つ基本ブロックが遭遇するまで続きます。

ライブインターバル解析

これで、ライブインターバル解析を実行し、ライブインターバル自体を構築するために必要な情報が揃いました。まず、基本ブロックとマシン命令に番号を付けます。次に、「ライブイン」値を処理します。これらは物理レジスタにあるため、物理レジスタは基本ブロックの終わりまでにキルされると仮定されます。仮想レジスタのライブインターバルは、マシン命令[1, N]の順序に従って計算されます。ライブインターバルはインターバル[i, j)であり、ここで1 >= i >= j > Nであり、変数がライブです。

注記

続報あり…

レジスタ割り当て

レジスタ割り当て問題とは、無制限の数の仮想レジスタを使用できるプログラム Pvを、有限の（場合によっては少ない）数の物理レジスタを含むプログラム Ppにマッピングすることです。各ターゲットアーキテクチャには、異なる数の物理レジスタがあります。物理レジスタの数がすべての仮想レジスタを収容するのに十分でない場合、それらのいくつかはメモリにマッピングする必要があります。これらの仮想レジスタは、スピルされた仮想レジスタと呼ばれます。

LLVMでのレジスタの表現方法

LLVMでは、物理レジスタは通常1から1023の範囲の整数で表されます。特定のアーキテクチャでこの番号付けがどのように定義されているかを確認するには、そのアーキテクチャのGenRegisterNames.incファイルを参照してください。たとえば、lib/Target/X86/X86GenRegisterInfo.incを調べると、32ビットレジスタEAXは43で表され、MMXレジスタMM0は65にマッピングされていることがわかります。

一部のアーキテクチャには、同じ物理ロケーションを共有するレジスタが含まれています。注目すべき例はX86プラットフォームです。たとえば、X86アーキテクチャでは、レジスタEAX、AX、ALは最初の8ビットを共有します。これらの物理レジスタは、LLVMではエイリアス化されているとマークされています。特定のアーキテクチャについて、どのレジスタがエイリアス化されているかを確認するには、そのRegisterInfo.tdファイルを確認してください。さらに、クラスMCRegAliasIteratorは、レジスタにエイリアス化されたすべての物理レジスタを列挙します。

LLVMでは、物理レジスタはレジスタクラスにグループ化されています。同じレジスタクラスの要素は機能的に同等であり、交換可能に使用できます。各仮想レジスタは、特定のクラスの物理レジスタのみにマッピングできます。たとえば、X86アーキテクチャでは、一部の仮想レジスタは8ビットレジスタのみに割り当てることができます。レジスタクラスはTargetRegisterClassオブジェクトによって記述されます。仮想レジスタが特定の物理レジスタと互換性があるかどうかを確認するには、このコードを使用できます。

bool RegMapping_Fer::compatible_class(MachineFunction &mf,
                                      unsigned v_reg,
                                      unsigned p_reg) {
  assert(TargetRegisterInfo::isPhysicalRegister(p_reg) &&
         "Target register must be physical");
  const TargetRegisterClass *trc = mf.getRegInfo().getRegClass(v_reg);
  return trc->contains(p_reg);
}

デバッグ目的で主に、ターゲットアーキテクチャで使用可能な物理レジスタの数を変更することが役立つ場合があります。これは、TargetRegisterInfo.tdファイル内で静的に行う必要があります。RegisterClassをgrepすると、最後のパラメータはレジスタのリストになります。いくつかをコメントアウトするだけで、それらが使用されないようにするのは簡単な方法の1つです。より丁寧な方法は、割り当て順序から一部のレジスタを明示的に除外することです。この例については、lib/Target/X86/X86RegisterInfo.tdのGR8レジスタクラスの定義を参照してください。

仮想レジスタも整数で表されます。物理レジスタとは異なり、異なる仮想レジスタが同じ番号を共有することはありません。物理レジスタはTargetRegisterInfo.tdファイルで静的に定義されており、アプリケーション開発者が作成することはできませんが、仮想レジスタはそうではありません。新しい仮想レジスタを作成するには、メソッドMachineRegisterInfo::createVirtualRegister()を使用します。このメソッドは新しい仮想レジスタを返します。IndexedMap<Foo, VirtReg2IndexFunctor>を使用して、仮想レジスタごとに情報を保持します。すべての仮想レジスタを列挙する必要がある場合は、関数TargetRegisterInfo::index2VirtReg()を使用して仮想レジスタ番号を見つけます。

for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
  unsigned VirtReg = TargetRegisterInfo::index2VirtReg(i);
  stuff(VirtReg);
}

レジスタ割り当ての前に、命令のオペランドはほとんどが仮想レジスタですが、物理レジスタも使用される場合があります。特定のマシンオペランドがレジスタかどうかを確認するには、ブール関数MachineOperand::isRegister()を使用します。レジスタの整数コードを取得するには、MachineOperand::getReg()を使用します。命令はレジスタを定義したり使用したりする場合があります。たとえば、ADD reg:1026 := reg:1025 reg:1024はレジスタ1024を定義し、レジスタ1025と1026を使用します。レジスタオペランドが与えられると、メソッドMachineOperand::isUse()は、そのレジスタが命令で使用されているかどうかを知らせます。メソッドMachineOperand::isDef()は、そのレジスタが定義されているかどうかを知らせます。

レジスタ割り当ての前にLLVMビットコードに存在する物理レジスタを、プリカラーレジスタと呼びます。プリカラーレジスタは、関数の呼び出しのパラメータを渡したり、特定の命令の結果を格納したりするなど、多くの状況で使用されます。プリカラーレジスタには、暗黙的に定義されたものと、明示的に定義されたものの2種類があります。明示的に定義されたレジスタは通常のオペランドであり、MachineInstr::getOperand(int)::getReg()を使用してアクセスできます。命令によって暗黙的に定義されるレジスタを確認するには、TargetInstrInfo::get(opcode)::ImplicitDefsを使用します。ここでopcodeはターゲット命令のオペコードです。明示的な物理レジスタと暗黙的な物理レジスタの重要な違いの1つは、後者は各命令に対して静的に定義されるのに対し、前者はコンパイルされているプログラムによって異なる場合があります。たとえば、関数呼び出しを表す命令は、常に同じ物理レジスタの集合を暗黙的に定義または使用します。命令によって暗黙的に使用されるレジスタを読み取るには、TargetInstrInfo::get(opcode)::ImplicitUsesを使用します。プリカラーレジスタは、レジスタ割り当てアルゴリズムに制約を課します。レジスタアロケータは、ライブ中に仮想レジスタの値によってそれらが上書きされないようにする必要があります。

仮想レジスタの物理レジスタへのマッピング

仮想レジスタを物理レジスタ（またはメモリスロット）にマッピングする方法は2つあります。1つ目の方法を *直接マッピング* と呼びますが、これは TargetRegisterInfo クラスと MachineOperand クラスのメソッドを使用することに基づいています。2つ目の方法を *間接マッピング* と呼びますが、メモリとの間で値の送受信を行うロードおよびストア命令を挿入するために VirtRegMap クラスに依存します。

直接マッピングは、レジスタアロケータの開発者に高い柔軟性を提供しますが、エラーが発生しやすく、実装作業も多くなります。基本的に、プログラマは、メモリから値を取得および格納するために、コンパイル対象のターゲット関数にロードおよびストア命令をどこに挿入すべきかを指定する必要があります。特定のオペランドに存在する仮想レジスタに物理レジスタを割り当てるには、MachineOperand::setReg(p_reg) を使用します。ストア命令を挿入するには TargetInstrInfo::storeRegToStackSlot(...) を、ロード命令を挿入するには TargetInstrInfo::loadRegFromStackSlot を使用します。

間接マッピングは、ロードおよびストア命令の挿入の複雑さからアプリケーション開発者を保護します。仮想レジスタを物理レジスタにマッピングするには、VirtRegMap::assignVirt2Phys(vreg, preg) を使用します。特定の仮想レジスタをメモリにマッピングするには、VirtRegMap::assignVirt2StackSlot(vreg) を使用します。このメソッドは、vreg の値が配置されるスタックスロットを返します。別の仮想レジスタを同じスタックスロットにマッピングする必要がある場合は、VirtRegMap::assignVirt2StackSlot(vreg, stack_location) を使用します。間接マッピングを使用する場合に考慮すべき重要な点として、仮想レジスタがメモリにマッピングされている場合でも、物理レジスタにマッピングする必要があるという点が挙げられます。この物理レジスタは、仮想レジスタが格納される前、または再ロードされた後に存在する場所です。

間接戦略を使用する場合、すべての仮想レジスタが物理レジスタまたはスタックスロットにマッピングされた後、スプラオブジェクトを使用してコードにロードおよびストア命令を配置する必要があります。スタックスロットにマッピングされた仮想レジスタは、定義された後にメモリに格納され、使用される前にロードされます。スプラの実装では、ロード/ストア命令の再利用を試み、不要な命令を回避します。スプラの呼び出し方法の例については、lib/CodeGen/RegAllocLinearScan.cpp の RegAllocLinearScan::runOnMachineFunction を参照してください。

2アドレス命令の処理

非常にまれな例外（例：関数呼び出し）を除き、LLVMマシンコード命令は3アドレス命令です。つまり、各命令は最大で1つのレジスタを定義し、最大で2つのレジスタを使用することが期待されています。ただし、一部のアーキテクチャでは2アドレス命令を使用します。この場合、定義されたレジスタは使用されたレジスタの1つでもあります。たとえば、X86の ADD %EAX, %EBX などの命令は、実際には %EAX = %EAX + %EBX と同等です。

正しいコードを生成するために、LLVMは2アドレス命令を表す3アドレス命令を真の2アドレス命令に変換する必要があります。LLVMはこの特定の目的のために TwoAddressInstructionPass パスを提供します。これはレジスタ割り当てが行われる前に実行する必要があります。実行後、結果のコードはSSA形式ではなくなる可能性があります。これは、たとえば、%a = ADD %b %c のような命令が次の2つの命令に変換される場合に発生します。

%a = MOVE %b
%a = ADD %a %c

内部的には、2番目の命令は ADD %a[def/use] %c として表されます。つまり、レジスタオペランド %a は、命令によって使用および定義されます。

SSA分解フェーズ

レジスタ割り当て中に発生する重要な変換に、*SSA分解フェーズ* があります。SSA形式は、プログラムの制御フローグラフに対して実行される多くの解析を簡素化します。しかし、従来の命令セットはPHI命令を実装していません。したがって、実行可能コードを生成するために、コンパイラはPHI命令をそれらのセマンティクスを維持する他の命令に置き換える必要があります。

ターゲットコードからPHI命令を安全に削除する方法はたくさんあります。最も伝統的なPHI分解アルゴリズムは、PHI命令をコピー命令で置き換えます。これはLLVMによって採用されている戦略です。SSA分解アルゴリズムは lib/CodeGen/PHIElimination.cpp に実装されています。このパスを呼び出すには、レジスタアロケータのコードで PHIEliminationID識別子を必須としてマークする必要があります。

命令の折りたたみ

*命令の折りたたみ* は、レジスタ割り当て中に実行される最適化であり、不要なコピー命令を削除します。たとえば、次のような命令シーケンスは、

%EBX = LOAD %mem_address
%EAX = COPY %EBX

次のような単一の命令で安全に置き換えることができます。

%EAX = LOAD %mem_address

命令は TargetRegisterInfo::foldMemoryOperand(...) メソッドを使用して折りたたむことができます。命令を折りたたむ際には注意が必要です。折り畳まれた命令は、元の命令とはかなり異なる可能性があります。使用方法の例については、lib/CodeGen/LiveIntervalAnalysis.cpp の LiveIntervals::addIntervalsForSpills を参照してください。

組み込みレジスタアロケータ

LLVMインフラストラクチャは、アプリケーション開発者に3つの異なるレジスタアロケータを提供します。

  • 高速 - このレジスタアロケータは、デバッグビルドのデフォルトです。基本ブロックレベルでレジスタを割り当て、値をレジスタに保持し、必要に応じてレジスタを再利用しようとします。

  • 基本 - これは、レジスタ割り当てに対する漸進的なアプローチです。ライブレンジは、ヒューリスティックによって駆動される順序で、一度に1つずつレジスタに割り当てられます。割り当て中にコードをオンザフライで書き換えることができるため、このフレームワークでは、興味深いアロケータを拡張機能として開発できます。それ自体はプロダクションレジスタアロケータではありませんが、バグの選別やパフォーマンスのベースラインとして、スタンドアロンモードとして潜在的に役立ちます。

  • 貪欲 - *デフォルトのアロケータ*。これは、グローバルライブレンジ分割を組み込んだ *基本* アロケータの高性能実装です。このアロケータは、スピルコードのコストを最小限に抑えるために努力します。

  • PBQP - 分割ブール2次計画法（PBQP）に基づくレジスタアロケータ。このアロケータは、検討中のレジスタ割り当て問題を表すPBQP問題を構築し、PBQPソルバーを使用してこれを解決し、解をレジスタ割り当てにマッピングすることによって機能します。

llcで使用されるレジスタアロケータの種類は、コマンドラインオプション -regalloc=... で選択できます。

$ llc -regalloc=linearscan file.bc -o ln.s
$ llc -regalloc=fast file.bc -o fa.s
$ llc -regalloc=pbqp file.bc -o pbqp.s

プロローグ/エピローグコードの挿入

注記

未記述

コンパクトアンワインド

例外をスローするには、関数から *アンワインド* する必要があります。特定の関数をアンワインドする方法に関する情報は、従来、DWARFアンワインド（別名フレーム）情報で表されていました。しかし、その形式はもともとデバッガがバックトレースするために開発されたものであり、各フレーム記述エントリ（FDE）には関数あたり約20〜30バイトが必要です。また、実行時に関数内のアドレスから対応するFDEへのマッピングのコストもあります。代替のアンワインドエンコーディングは *コンパクトアンワインド* と呼ばれ、関数あたりわずか4バイトしか必要ありません。

コンパクトアンワインドエンコーディングは32ビット値であり、アーキテクチャ固有の方法でエンコードされます。これにより、どのレジスタをどこから復元するか、および関数のアンワインド方法が指定されます。リンカが最終的なリンクされたイメージを作成すると、__TEXT,__unwind_info セクションが作成されます。このセクションは、ランタイムが任意の関数のアンワインド情報にアクセスするための小さく高速な方法です。関数のコンパクトアンワインド情報を生成する場合、そのコンパクトアンワインド情報は __TEXT,__unwind_info セクションにエンコードされます。DWARFアンワインド情報を生成する場合、__TEXT,__unwind_info セクションには、最終的なリンクされたイメージの __TEXT,__eh_frame セクション内のFDEのオフセットが含まれます。

X86の場合、コンパクトアンワインドエンコーディングには3つのモードがあります。

フレームポインタ（``EBP``または``RBP``）を持つ関数

EBP/RBPベースのフレームでは、EBP/RBPは戻りアドレスの直後にスタックにプッシュされ、その後ESP/RSPはEBP/RBPに移動されます。したがって、アンワインドするには、ESP/RSPは現在のEBP/RBPの値で復元され、その後EBP/RBPはスタックをポップすることで復元され、さらにスタックを一度ポップしてPCに返すことで処理が完了します。復元する必要があるすべての非揮発性レジスタは、EBP-4からEBP-1020（RBP-8からRBP-1020）で始まるスタック上の小さな範囲に保存されている必要があります。オフセット（32ビットモードでは4で、64ビットモードでは8で除算）は、ビット16〜23にエンコードされます（マスク：0x00FF0000）。保存されたレジスタは、ビット0〜14（マスク：0x00007FFF）に、以下の表からの5つの3ビットのエントリとしてエンコードされます。

コンパクト番号

i386レジスタ

x86-64レジスタ

1

EBX

RBX

2

ECX

R12

3

EDX

R13

4

EDI

R14

5

ESI

R15

6

EBP

RBP
小さな定数スタックサイズを持つフレームレス（``EBP``または``RBP``はフレームポインタとして使用されません）

戻るには、（コンパクトアンワインドエンコーディングにエンコードされた）定数がESP/RSPに追加されます。その後、スタックをPCにポップすることで戻ります。復元する必要があるすべての非揮発性レジスタは、戻りアドレスの直後にスタックに保存されている必要があります。スタックサイズ（32ビットモードでは4で、64ビットモードでは8で除算）は、ビット16〜23にエンコードされます（マスク：0x00FF0000）。32ビットモードでは最大スタックサイズは1024バイト、64ビットモードでは2048バイトです。保存されたレジスタの数は、ビット9〜12（マスク：0x00001C00）にエンコードされます。ビット0〜9（マスク：0x000003FF）には、保存されたレジスタとその順序が含まれています。（エンコーディングアルゴリズムについては、lib/Target/X86FrameLowering.cppのencodeCompactUnwindRegistersWithoutFrame()関数を参照してください。）

大きな定数スタックサイズを持つフレームレス（``EBP``または``RBP``はフレームポインタとして使用されません）

このケースは、「小さな定数スタックサイズを持つフレームレス」のケースに似ていますが、スタックサイズが大きすぎてコンパクトアンワインドエンコーディングにエンコードできません。代わりに、関数のプロローグに「subl $nnnnnn, %esp」が含まれている必要があります。コンパクトエンコーディングには、関数内の$nnnnnn値へのオフセットがビット9〜12（マスク：0x00001C00）に含まれています。

後期機械コード最適化

注記

未記述

コードエミッション

コード生成のコードエミッションステップは、コードジェネレータの抽象化（MachineFunction、MachineInstrなど）を、MCレイヤで使用される抽象化（MCInst、MCStreamerなど）に落とし込む役割を担っています。これは、いくつかの異なるクラスの組み合わせによって行われます。（誤った名前の）ターゲット非依存のAsmPrinterクラス、AsmPrinterのターゲット固有のサブクラス（SparcAsmPrinterなど）、およびTargetLoweringObjectFileクラスです。

MCレイヤはオブジェクトファイルの抽象化レベルで動作するため、関数、グローバル変数などの概念を持っていません。代わりに、ラベル、ディレクティブ、命令について考えています。この時点で使用される重要なクラスはMCStreamerクラスです。これは、異なる方法で実装される抽象API（例：.sファイルを出力する、ELF .oファイルを出力するなど）であり、効果的に「アセンブラAPI」です。MCStreamerには、EmitLabel、EmitSymbolAttribute、switchSectionなど、アセンブリレベルのディレクティブに直接対応するディレクティブごとに1つのメソッドがあります。

ターゲットのコードジェネレータを実装することに関心がある場合、ターゲットに対して実装する必要がある3つの重要なものがあります。

  1. まず、ターゲットのAsmPrinterのサブクラスが必要です。このクラスは、MachineFunctionをMCラベル構造に変換する一般的なローワーリングプロセスを実装します。AsmPrinterベースクラスは、多くの便利なメソッドとルーチンを提供し、いくつかの重要な方法でローワーリングプロセスをオーバーライドすることもできます。ELF、COFF、またはMachOターゲットを実装する場合、TargetLoweringObjectFileクラスが共通のロジックの大部分を既に実装しているため、ローワーリングの大部分を無料で利用できます。

  2. 次に、ターゲットの命令プリンタを実装する必要があります。命令プリンタはMCInstを受け取り、テキストとしてraw_ostreamにレンダリングします。この大部分は.tdファイルから自動的に生成されます（命令に「add $dst, $src1, $src2」のように指定した場合）、オペランドを出力するルーチンを実装する必要があります。

  3. 第三に、「<target>MCInstLower.cpp」で通常実装されるMachineInstrをMCInstに落とすコードを実装する必要があります。このローワーリングプロセスは多くの場合ターゲット固有であり、ジャンプテーブルのエントリ、定数プールのインデックス、グローバル変数のアドレスなどを適切にMCLabelに変換する役割を担います。この変換レイヤは、コードジェネレータで使用される擬似オペコードを、対応する実際の機械命令に展開する役割も担っています。これによって生成されたMCInstは、命令プリンタまたはエンコーダに供給されます。

最後に、必要に応じて、MCInstを機械コードバイトとリロケーションに落とすMCCodeEmitterのサブクラスを実装することもできます。これは、直接.oファイルのエミッションをサポートする場合、またはターゲットのアセンブラを実装する場合に重要です。

関数スタックサイズ情報のエミッション

TargetLoweringObjectFile::StackSizesSectionがNULLではなく、TargetOptions::EmitStackSizeSectionが設定されている場合（-stack-size-section）、関数スタックサイズに関するメタデータを含むセクションが出力されます。このセクションには、関数シンボル値（ポインタサイズ）とスタックサイズ（符号なしLEB128）のペアの配列が含まれます。スタックサイズの値には、関数プロローグで割り当てられた領域のみが含まれます。動的スタック割り当てを行う関数は含まれません。

VLIWパケタイザ

Very Long Instruction Word（VLIW）アーキテクチャでは、コンパイラはアーキテクチャで使用可能な機能ユニットに命令をマッピングする役割を担います。そのため、コンパイラは*パケット*または*バンドル*と呼ばれる命令のグループを作成します。LLVMのVLIWパケタイザは、機械命令のパケタイゼーションを可能にするターゲット非依存のメカニズムです。

命令から機能ユニットへのマッピング

VLIWターゲットの命令は、通常、複数の機能ユニットにマッピングできます。パケタイゼーションのプロセス中に、コンパイラは命令をパケットに追加できるかどうかを推論できる必要があります。コンパイラは命令の機能ユニットへのすべての可能なマッピングを調べなければならないため、この決定は複雑になる可能性があります。そのため、コンパイル時の複雑さを軽減するために、VLIWパケタイザはターゲットの命令クラスを解析し、コンパイラのビルド時にテーブルを生成します。これらのテーブルは、提供された機械非依存APIによってクエリされ、命令をパケットに収容できるかどうかを判断できます。

パケタイゼーションテーブルの生成と使用方法

パケタイザは、ターゲットのイテラリから命令クラスを読み取り、パケットの状態を表す決定性有限オートマトン（DFA）を作成します。DFAは、入力、状態、遷移の3つの主要な要素で構成されます。生成されたDFAの入力のセットは、パケットに追加される命令を表します。状態は、パケット内の命令による機能ユニットの可能な消費を表します。DFAでは、既存のパケットに命令を追加すると、ある状態から別の状態への遷移が発生します。機能ユニットから命令への合法的なマッピングが存在する場合、DFAには対応する遷移が含まれます。遷移がないことは、合法的なマッピングが存在せず、命令をパケットに追加できないことを示しています。

VLIWターゲットのテーブルを生成するには、ターゲットディレクトリのMakefileにTargetGenDFAPacketizer.incをターゲットとして追加します。エクスポートされたAPIは、DFAPacketizer::clearResources()、DFAPacketizer::reserveResources(MachineInstr *MI)、およびDFAPacketizer::canReserveResources(MachineInstr *MI)の3つの関数を提供します。これらの関数は、ターゲットパケタイザが既存のパケットに命令を追加し、命令をパケットに追加できるかどうかを確認できるようにします。詳細については、llvm/CodeGen/DFAPacketizer.hを参照してください。

ネイティブアセンブラの実装

おそらくコンパイラバックエンドの記述や保守のためにこれを読んでいるのでしょうが、LLVMはネイティブアセンブラの構築も完全にサポートしています。.tdファイル（特に命令の構文とエンコーディング）からアセンブラの生成を自動化するために努力しており、手動で繰り返し行うデータ入力の大部分を削減し、コンパイラと共有することができます。

命令の解析

注記

未記述

命令エイリアスの処理

命令が解析されると、MatchInstructionImpl関数に入ります。MatchInstructionImpl関数はエイリアスの処理を実行してから、実際のマッチングを行います。

エイリアスの処理とは、同じ命令の異なる字句形式を1つの表現に正規化する段階です。実装可能なエイリアスの種類はいくつかあり、以下に処理順序（最も単純/弱いものから最も複雑/強力なものまで）でリストされています。一般的に、命令のニーズを満たす最初のエイリアスメカニズムを使用することをお勧めします。なぜなら、より簡潔な記述が可能になるからです。

ニーモニックエイリアス

エイリアス処理の最初の段階は、2つの異なるニーモニックが許可されている命令クラスに対する単純な命令ニーモニックのリマッピングです。この段階は、1つの入力ニーモニックから1つの出力ニーモニックへの単純で無条件のリマッピングです。この形式のエイリアスではオペランドをまったく調べることができないため、リマッピングは特定のニーモニックのすべての形式に適用する必要があります。ニーモニックエイリアスは、たとえばX86には以下のように単純に定義されます。

def : MnemonicAlias<"cbw",     "cbtw">;
def : MnemonicAlias<"smovq",   "movsq">;
def : MnemonicAlias<"fldcww",  "fldcw">;
def : MnemonicAlias<"fucompi", "fucomip">;
def : MnemonicAlias<"ud2a",    "ud2">;

…そして他にもたくさんあります。MnemonicAliasの定義を使用すると、ニーモニックは単純かつ直接的にリマップされます。MnemonicAliasは命令のあらゆる側面（オペランドなど）を調べることができませんが、Requires句を通じてグローバルモード（マッチャによってサポートされるものと同じ）に依存できます。

def : MnemonicAlias<"pushf", "pushfq">, Requires<[In64BitMode]>;
def : MnemonicAlias<"pushf", "pushfl">, Requires<[In32BitMode]>;

この例では、ニーモニックは現在の命令セットに応じて異なるニーモニックにマップされます。

命令エイリアス

エイリアス処理の最も一般的なフェーズは、マッチング中に発生します。これは、マッチャーがマッチングを行う新しい形式と、生成する特定の命令を提供します。命令エイリアスは、マッチングする文字列と生成する命令の2つの部分で構成されます。例えば

def : InstAlias<"movsx $src, $dst", (MOVSX16rr8W GR16:$dst, GR8  :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX16rm8W GR16:$dst, i8mem:$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX32rr8  GR32:$dst, GR8  :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX32rr16 GR32:$dst, GR16 :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX64rr8  GR64:$dst, GR8  :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX64rr16 GR64:$dst, GR16 :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX64rr32 GR64:$dst, GR32 :$src)>;

これは命令エイリアスの強力な例を示しており、アセンブリに存在するオペランドに応じて、同じニーモニックを複数の異なる方法でマッチングします。命令エイリアスの結果は、宛先命令とは異なる順序でオペランドを含めることができ、入力値を複数回使用することもできます。例えば

def : InstAlias<"clrb $reg", (XOR8rr  GR8 :$reg, GR8 :$reg)>;
def : InstAlias<"clrw $reg", (XOR16rr GR16:$reg, GR16:$reg)>;
def : InstAlias<"clrl $reg", (XOR32rr GR32:$reg, GR32:$reg)>;
def : InstAlias<"clrq $reg", (XOR64rr GR64:$reg, GR64:$reg)>;

この例はまた、結び付けられたオペランドは一度しかリストされないことを示しています。X86バックエンドでは、XOR8rrは2つの入力GR8と1つの出力GR8を持っています（入力は出力に結び付けられています）。InstAliasesは、結び付けられたオペランドについて重複のないフラット化されたオペランドリストを取ります。命令エイリアスの結果は、イミディエイトと固定された物理レジスタを使用することもでき、これらは結果に単純なイミディエイトオペランドとして追加されます。例えば

// Fixed Immediate operand.
def : InstAlias<"aad", (AAD8i8 10)>;

// Fixed register operand.
def : InstAlias<"fcomi", (COM_FIr ST1)>;

// Simple alias.
def : InstAlias<"fcomi $reg", (COM_FIr RST:$reg)>;

命令エイリアスには、サブターゲット固有にするためのRequires句を含めることもできます。

バックエンドがサポートしている場合、命令プリンターは、エイリアスされているものよりもエイリアスを自動的に出力できます。通常、より良く、より読みやすいコードにつながります。エイリアスされているものを出力する方が良い場合は、InstAlias定義の第3パラメーターとして「0」を渡します。

命令マッチング

注記

未記述

ターゲット固有の実装に関する注記

このセクションでは、特定のターゲットのコードジェネレーターに固有の機能または設計上の決定について説明します。

テールコール最適化

呼び出し元のスタックを呼び出し先が再利用するテールコール最適化は、現在、x86/x86-64、PowerPC、AArch64、およびWebAssemblyでサポートされています。x86/x86-64、PowerPC、およびAArch64では、以下の場合に実行されます。

  • 呼び出し元と呼び出し先の呼び出し規約がfastcc、cc 10（GHC呼び出し規約）、cc 11（HiPE呼び出し規約）、tailcc、またはswifttailccである。

  • 呼び出しがテールコールである - テールポジションにある（retが呼び出しの直後に続き、retが呼び出しの値を使用するか、voidである）。

  • オプション-tailcalloptが有効になっているか、呼び出し規約がtailccである。

  • プラットフォーム固有の制約が満たされている。

x86/x86-64の制約

  • 可変個の引数リストは使用されない。

  • GOT/PICコードを生成する場合、x86-64ではモジュールローカル呼び出し（visibility = hiddenまたはprotected）のみがサポートされます。

PowerPCの制約

  • 可変個の引数リストは使用されない。

  • byvalパラメーターは使用されない。

  • ppc32/64 GOT/PICでは、モジュールローカル呼び出し（visibility = hiddenまたはprotected）のみがサポートされます。

WebAssemblyの制約

  • 可変個の引数リストは使用されない

  • 「tail-call」ターゲット属性が有効になっている。

  • 呼び出し元と呼び出し先の戻り値の型は一致する必要があります。呼び出し元がvoidでない限り、呼び出し先もvoidである必要があります。

AArch64の制約

  • 可変個の引数リストは使用されない。

例

llc -tailcallopt test.llとして呼び出す。

declare fastcc i32 @tailcallee(i32 inreg %a1, i32 inreg %a2, i32 %a3, i32 %a4)

define fastcc i32 @tailcaller(i32 %in1, i32 %in2) {
  %l1 = add i32 %in1, %in2
  %tmp = tail call fastcc i32 @tailcallee(i32 inreg %in1, i32 inreg %in2, i32 %in1, i32 %l1)
  ret i32 %tmp
}

-tailcalloptの影響

呼び出し先が呼び出し元よりも多くの引数を持つ状況でテールコール最適化をサポートするために、「呼び出し先が引数をポップする」規約が使用されます。これは現在、上記の制約の1つ以上が満たされていないためテールコール最適化されていない各fastcc呼び出しに、スタックの再調整が続くことを引き起こします。そのため、そのような場合のパフォーマンスは低下する可能性があります。

兄弟呼び出し最適化

兄弟呼び出し最適化は、テールコール最適化の制限された形式です。前のセクションで説明したテールコール最適化とは異なり、-tailcalloptオプションが指定されていない場合、任意のテールコールで自動的に実行できます。

兄弟呼び出し最適化は、現在、以下の制約が満たされている場合にx86/x86-64で実行されます。

  • 呼び出し元と呼び出し先の呼び出し規約が同じである。 cまたはfastccのいずれかです。

  • 呼び出しがテールコールである - テールポジションにある（retが呼び出しの直後に続き、retが呼び出しの値を使用するか、voidである）。

  • 呼び出し元と呼び出し先の戻り値の型が一致するか、呼び出し先の結果は使用されない。

  • 呼び出し先の引数のいずれかがスタックで渡されている場合、呼び出し元の独自の着信引数スタックで使用可能である必要があり、フレームオフセットは同じである必要があります。

例

declare i32 @bar(i32, i32)

define i32 @foo(i32 %a, i32 %b, i32 %c) {
entry:
  %0 = tail call i32 @bar(i32 %a, i32 %b)
  ret i32 %0
}

X86バックエンド

X86コードジェネレーターはlib/Target/X86ディレクトリにあります。このコードジェネレーターは、さまざまなx86-32およびx86-64プロセッサーをターゲットにすることができ、MMXやSSEなどのISA拡張機能のサポートが含まれています。

サポートされているX86ターゲットトリプル

以下は、X86バックエンドでサポートされている既知のターゲットトリプルです。これは網羅的なリストではなく、人々がテストしたものを追加することが役立つでしょう。

  • i686-pc-linux-gnu — Linux

  • i386-unknown-freebsd5.3 — FreeBSD 5.3

  • i686-pc-cygwin — Win32上のCygwin

  • i686-pc-mingw32 — Win32上のMingW

  • i386-pc-mingw32msvc — Linux上のMingWクロスコンパイラー

  • i686-apple-darwin* — X86上のApple Darwin

  • x86_64-unknown-linux-gnu — Linux

サポートされているX86呼び出し規約

バックエンドで既知のターゲット固有の呼び出し規約を以下に示します。

  • x86_StdCall — Microsoft Windowsプラットフォームで見られるstdcall呼び出し規約（CC ID = 64）。

  • x86_FastCall — Microsoft Windowsプラットフォームで見られるfastcall呼び出し規約（CC ID = 65）。

  • x86_ThisCall — X86_StdCallに似ています。最初の引数をECXで渡し、他の引数をスタックで渡します。呼び出し元がスタックのクリーンアップを担当します。この規約は、MSVCによって、そのABIでのメソッドにデフォルトで使用されます（CC ID = 70）。

MachineInstrsでのX86アドレッシングモードの表現

x86は、メモリへのアクセス方法が非常に柔軟です。整数命令（ModR/Mアドレッシングを使用）で、次の式のメモリアドレスを直接形成できます。

SegmentReg: Base + [1,2,4,8] * IndexReg + Disp32

これを表現するために、LLVMは、この形式の各メモリオペランドに対して少なくとも5つのオペランドを追跡します。つまり、「mov」の「ロード」形式には、この順序で次のMachineOperandがあります。

Index:        0     |    1        2       3           4          5
Meaning:   DestReg, | BaseReg,  Scale, IndexReg, Displacement Segment
OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg,   SignExtImm  PhysReg

ストアと他のすべての命令は、4つのメモリオペランドを同じ方法で、同じ順序で処理します。セグメントレジスタが未指定の場合（regno = 0）、セグメントオーバーライドは生成されません。「Lea」操作にはセグメントレジスタが指定されていないため、メモリ参照には4つのオペランドしかありません。

サポートされているX86アドレス空間

x86には、x86セグメントレジスタを介して異なるアドレス空間にロードとストアを実行する機能があります。命令へのセグメントオーバーライドプレフィックスバイトにより、命令のメモリアクセスが指定されたセグメントに移動します。LLVMアドレス空間0はデフォルトのアドレス空間であり、スタックとプログラム内の修飾されていないメモリアクセスが含まれます。アドレス空間1〜255は現在、ユーザー定義コード用に予約されています。GSセグメントはアドレス空間256で、FSセグメントはアドレス空間257で、SSセグメントはアドレス空間258で表されます。他のx86セグメントには、まだアドレス空間番号が割り当てられていません。

これらのアドレス空間は、thread_localキーワードによるTLSと似ており、多くの場合同じ基盤となるハードウェアを使用しますが、根本的な違いがあります。

thread_localキーワードはグローバル変数に適用され、スレッドローカルメモリに割り当てられることを指定します。型修飾子は関与せず、これらの変数は通常のポインターで指すことができ、通常のロードとストアでアクセスできます。thread_localキーワードはLLVM IRレベルではターゲットに依存しません（ただし、LLVMはまだ一部の構成でこれを実装していません）。

一方、特別なアドレス空間は静的型に適用されます。すべてのロードとストアには、アドレスオペランド型に特定のアドレス空間があり、これがアクセスされるアドレス空間を決定します。LLVMはグローバル変数に対するこれらの特別なアドレス空間修飾子を無視し、それらに直接ストレージを割り当てる方法を提供しません。LLVM IRレベルでは、これらの特別なアドレス空間の動作は、基盤となるOSまたはランタイム環境に部分的に依存し、x86に固有です（そしてLLVMはまだいくつかのケースで正しく処理していません）。

一部のオペレーティングシステムとランタイム環境は、FS/GSセグメントレジスタをさまざまな低レベルの目的で使用している（または将来使用する可能性があります）ため、それらを使用する際には注意が必要です。

命令の命名

命令名は、基本名、デフォルトのオペランドサイズ、オペランドごとの文字、オプションの特別なサイズで構成されます。例えば

ADD8rr      -> add, 8-bit register, 8-bit register
IMUL16rmi   -> imul, 16-bit register, 16-bit memory, 16-bit immediate
IMUL16rmi8  -> imul, 16-bit register, 16-bit memory, 8-bit immediate
MOVSX32rm16 -> movsx, 32-bit register, 16-bit memory

PowerPCバックエンド

PowerPCコードジェネレーターは、lib/Target/PowerPCディレクトリにあります。コード生成は、PowerPC ISAのいくつかのバリエーションまたは*サブターゲット*に再ターゲット可能で、ppc32、ppc64、およびaltivecが含まれます。

LLVM PowerPC ABI

LLVMはAIX PowerPC ABIに準拠していますが、2つの例外があります。LLVMはグローバル値へのアクセスにPC相対(PIC)アドレス指定または静的アドレス指定を使用するため、TOC(r2)を使用しません。2点目は、スタックフレームの動的拡張を可能にするために、r31をフレームポインタとして使用することです。LLVMはTOCを使用しないことを利用して、呼び出し元フレームのPowerPCリンケージ領域にフレームポインタを保存するための領域を提供します。PowerPC ABIのその他の詳細は、PowerPC ABIを参照してください。注記：このリンクは32ビットABIについて説明しています。64ビットABIは類似していますが、GPRのサイズは8バイト(4バイトではない)であり、r13はシステム用に予約されています。

フレームレイアウト

PowerPCフレームのサイズは、通常、関数の呼び出し中は固定されています。フレームのサイズは固定されているため、フレーム内のすべての参照は、スタックポインタからの固定オフセットを使用してアクセスできます。例外は、動的なallocaや可変サイズの配列が存在する場合です。その場合は、ベースポインタ(r31)がスタックポインタの代理として使用され、スタックポインタは自由に増減できます。llvm-gccに-fomit-frame-pointerフラグが渡されない場合も、ベースポインタが使用されます。スタックポインタは常に16バイトにアラインメントされるため、AltiVecベクトル用に割り当てられた領域は適切にアラインメントされます。

呼び出しフレームは、次のようにレイアウトされます（低メモリが上）。

リンケージ
パラメータ領域
動的領域
ローカル変数領域
レジスタ保存領域

以前のフレーム

リンケージ領域は、呼び出し先が独自のフレームを割り当てる前に特殊レジスタを保存するために使用されます。LLVMに関連するエントリは3つだけです。最初のエントリは以前のスタックポインタ(sp)つまりリンクです。これにより、gdbや例外ハンドラなどの調査ツールは、スタック内のフレームを迅速にスキャンできます。関数エピローグは、リンクを使用してスタックからフレームをポップすることもできます。リンケージ領域の3番目のエントリは、lrレジスタからの戻りアドレスを保存するために使用されます。最後に、前述のように、最後のエントリは以前のフレームポインタ(r31)を保存するために使用されます。リンケージ領域のエントリはGPRのサイズであるため、リンケージ領域は32ビットモードでは24バイト、64ビットモードでは48バイトの長さになります。

32ビットリンケージ領域

0 保存されたSP (r1)
4 保存されたCR
8 保存されたLR
12 予約済み
16 予約済み
20 保存されたFP (r31)

64ビットリンケージ領域

0 保存されたSP (r1)
8 保存されたCR
16 保存されたLR
24 予約済み
32 予約済み
40 保存されたFP (r31)

パラメータ領域は、呼び出し先関数に渡される引数を格納するために使用されます。PowerPC ABIに従って、最初のいくつかの引数は実際にはレジスタで渡され、パラメータ領域のスペースは使用されません。ただし、レジスタが不足している場合、または呼び出し先がthunk関数または可変引数関数である場合、これらのレジスタ引数はパラメータ領域にスピルされる可能性があります。したがって、パラメータ領域は、呼び出し元によって行われた最大の呼び出しシーケンスのすべてのパラメータを格納できる大きさでなければなりません。また、レジスタr3〜r10をスピルするのに十分な大きさである必要があります。これにより、thunk関数や可変引数関数など、呼び出しシグネチャを認識しない呼び出し先でも、引数レジスタをキャッシュするための十分なスペースが確保されます。したがって、パラメータ領域は最小で32バイト（64ビットモードでは64バイト）です。また、パラメータ領域はフレームの上部からの固定オフセットであるため、呼び出し先はスタックポインタ（またはベースポインタ）からの固定オフセットを使用して分割された引数にアクセスできることに注意してください。

リンケージ、パラメータ領域、およびアラインメントに関する情報を組み合わせると、スタックフレームは32ビットモードでは最小64バイト、64ビットモードでは最小128バイトになります。

動的領域は、最初はサイズゼロです。関数が動的なallocaを使用する場合、スタックにスペースが追加され、リンケージとパラメータ領域はスタックの先頭にシフトされ、新しいスペースはリンケージとパラメータ領域の直下にすぐに使用可能になります。リンケージとパラメータ領域をシフトするコストは、リンク値をコピーする必要があるだけなのでわずかです。リンク値は、元のフレームサイズをベースポインタに追加することで簡単に取得できます。動的領域内の割り当ては、16バイトのアラインメントを遵守する必要があることに注意してください。

ローカル変数領域は、LLVMコンパイラがローカル変数のスペースを予約する場所です。

レジスタ保存領域は、LLVMコンパイラが呼び出し先保存レジスタを呼び出し先へのエントリでスピルする場所です。

プロローグ/エピローグ

LLVMのプロローグとエピローグは、PowerPC ABIで説明されているものと同じですが、次の例外があります。呼び出し先保存レジスタは、フレームが作成された後にスピルされます。これにより、LLVMエピローグ/プロローグのサポートを他のターゲットと共通にすることができます。ベースポインタの呼び出し先保存レジスタr31は、リンケージ領域のTOCスロットに保存されます。これにより、ベースポインタのスペースの割り当てが簡素化され、プログラムによる位置特定とデバッグが容易になります。

動的割り当て

注記

TODO - 続報あり。

NVPTXバックエンド

lib/Target/NVPTXにあるNVPTXコードジェネレータは、NVIDIA NVPTXコードジェネレータのオープンソースバージョンです。NVIDIAによって提供され、CUDAコンパイラ(nvcc)で使用されているコードジェネレータの移植版です。PTX 3.0/3.1 ISAをターゲットとし、2.0以上のコンピューティング能力(Fermi)をターゲットにすることができます。

このターゲットは製品品質であり、公式のNVIDIAツールチェーンと完全に互換性があるはずです。

コードジェネレータオプション

オプション 説明
sm_20 シェーダーモデル/コンピューティング能力を2.0に設定
sm_21 シェーダーモデル/コンピューティング能力を2.1に設定
sm_30 シェーダーモデル/コンピューティング能力を3.0に設定
sm_35 シェーダーモデル/コンピューティング能力を3.5に設定
ptx30 PTX 3.0をターゲット
ptx31 PTX 3.1をターゲット

拡張Berkeley Packet Filter (eBPF)バックエンド

拡張BPF（またはeBPF）は、ネットワークパケットのフィルタリングに使用される元の（従来の）BPF（cBPF）に似ています。bpf()システムコールは、eBPFに関連するさまざまな操作を実行します。cBPFとeBPFプログラムの両方について、Linuxカーネルはプログラムをロードする前に静的に分析して、実行中のシステムに損害を与えることができないようにします。eBPFは、64ビットCPUへの1対1のマッピングを目的とした64ビットRISC命令セットです。オペコードは8ビットでエンコードされ、87個の命令が定義されています。10個のレジスタがあり、下記のように関数ごとにグループ化されています。

R0        return value from in-kernel functions; exit value for eBPF program
R1 - R5   function call arguments to in-kernel functions
R6 - R9   callee-saved registers preserved by in-kernel functions
R10       stack frame pointer (read only)

命令エンコーディング（算術演算とジャンプ）

eBPFは、従来のBPFからeBPFへの変換を簡素化するために、従来のオペコードエンコーディングの大部分を再利用しています。算術演算命令とジャンプ命令では、8ビットの「code」フィールドは3つの部分に分割されます。

+----------------+--------+--------------------+
|   4 bits       |  1 bit |   3 bits           |
| operation code | source | instruction class  |
+----------------+--------+--------------------+
(MSB)                                      (LSB)

3つのLSBビットは、次のいずれかの命令クラスを格納します。

BPF_LD     0x0
BPF_LDX    0x1
BPF_ST     0x2
BPF_STX    0x3
BPF_ALU    0x4
BPF_JMP    0x5
(unused)   0x6
BPF_ALU64  0x7

BPF_CLASS(code) == BPF_ALUまたはBPF_ALU64またはBPF_JMPの場合、4番目のビットはソースオペランドをエンコードします。

BPF_X     0x1  use src_reg register as source operand
BPF_K     0x0  use 32 bit immediate as source operand

そして、4つのMSBビットはオペコードを格納します。

BPF_ADD   0x0  add
BPF_SUB   0x1  subtract
BPF_MUL   0x2  multiply
BPF_DIV   0x3  divide
BPF_OR    0x4  bitwise logical OR
BPF_AND   0x5  bitwise logical AND
BPF_LSH   0x6  left shift
BPF_RSH   0x7  right shift (zero extended)
BPF_NEG   0x8  arithmetic negation
BPF_MOD   0x9  modulo
BPF_XOR   0xa  bitwise logical XOR
BPF_MOV   0xb  move register to register
BPF_ARSH  0xc  right shift (sign extended)
BPF_END   0xd  endianness conversion

BPF_CLASS(code) == BPF_JMPの場合、BPF_OP(code)は次のいずれかです。

BPF_JA    0x0  unconditional jump
BPF_JEQ   0x1  jump ==
BPF_JGT   0x2  jump >
BPF_JGE   0x3  jump >=
BPF_JSET  0x4  jump if (DST & SRC)
BPF_JNE   0x5  jump !=
BPF_JSGT  0x6  jump signed >
BPF_JSGE  0x7  jump signed >=
BPF_CALL  0x8  function call
BPF_EXIT  0x9  function return

命令エンコーディング（ロード、ストア）

ロード命令とストア命令では、8ビットの「code」フィールドは次のように分割されます。

+--------+--------+-------------------+
| 3 bits | 2 bits |   3 bits          |
|  mode  |  size  | instruction class |
+--------+--------+-------------------+
(MSB)                             (LSB)

サイズ修飾子は次のいずれかです。

BPF_W       0x0  word
BPF_H       0x1  half word
BPF_B       0x2  byte
BPF_DW      0x3  double word

モード修飾子は次のいずれかです。

BPF_IMM     0x0  immediate
BPF_ABS     0x1  used to access packet data
BPF_IND     0x2  used to access packet data
BPF_MEM     0x3  memory
(reserved)  0x4
(reserved)  0x5
BPF_XADD    0x6  exclusive add

パケットデータアクセス（BPF_ABS、BPF_IND）

2つの汎用ではない命令：（BPF_ABS | <size> | BPF_LD）と（BPF_IND | <size> | BPF_LD）は、パケットデータへのアクセスに使用されます。レジスタR6は、sk_buffへのポインタを含んでいる必要がある暗黙の入力です。レジスタR0は、パケットからフェッチされたデータを含む暗黙の出力です。レジスタR1〜R5はスクラッチレジスタであり、BPF_ABS | BPF_LDまたはBPF_IND | BPF_LD命令間でデータを格納するために使用してはなりません。これらの命令には、プログラムの終了条件も暗黙的に含まれています。eBPFプログラムがパケット境界を超えたデータにアクセスしようとした場合、インタプリタはプログラムの実行を中止します。

BPF_IND | BPF_W | BPF_LDは次のと同等です。

R0 = ntohl(*(u32 *) (((struct sk_buff *) R6)->data + src_reg + imm32))

eBPFマップ

eBPFマップは、カーネルとユーザースペース間でデータを共有するために提供されます。現在実装されているタイプはハッシュと配列であり、ブルームフィルタ、ラジックスツリーなどをサポートするように拡張される可能性があります。マップは、そのタイプ、最大要素数、キーサイズ、および値サイズ（バイト単位）によって定義されます。eBPFシステムコールは、マップの作成、更新、検索、および削除関数をサポートします。

関数呼び出し

関数呼び出しの引数は、最大5つのレジスタ（R1〜R5）を使用して渡されます。戻り値は専用のレジスタ（R0）で渡されます。さらに4つのレジスタ（R6〜R9）は呼び出し先保存レジスタであり、これらのレジスタの値はカーネル関数内で保持されます。R0〜R5はカーネル関数内のスクラッチレジスタであり、したがってeBPFプログラムは、関数呼び出し間で必要に応じてこれらのレジスタの値を保存/復元する必要があります。スタックは、読み取り専用のフレームポインタR10を使用してアクセスできます。eBPFレジスタは、x86_64およびその他の64ビットアーキテクチャのハードウェアレジスタと1対1でマップされます。たとえば、x86_64のカーネル内JITは次のようにマップします。

R0 - rax
R1 - rdi
R2 - rsi
R3 - rdx
R4 - rcx
R5 - r8
R6 - rbx
R7 - r13
R8 - r14
R9 - r15
R10 - rbp

x86_64 ABIでは、rdi、rsi、rdx、rcx、r8、r9を引数の渡しに使用し、rbx、r12〜r15は呼び出し先保存レジスタであるため。

プログラム開始

eBPFプログラムは1つの引数を受け取り、1つのeBPFメインルーチンを含みます。プログラムはeBPF関数を含みません。関数呼び出しは、事前に定義されたカーネル関数のセットに限定されます。プログラムのサイズは4K命令に制限されています。これは、迅速な終了とカーネル関数呼び出しの数の制限を保証します。eBPFプログラムを実行する前に、検証プログラムが静的分析を実行して、コード内のループを防ぎ、有効なレジスタの使用とオペランドのタイプを保証します。

AMDGPUバックエンド

AMDGPUコードジェネレータは、lib/Target/AMDGPUディレクトリにあります。このコードジェネレータは、さまざまなAMD GPUプロセッサをターゲットにすることができます。AMDGPUバックエンドのユーザーガイドで詳細を確認してください。