LLVM IR 実践

LLVM IR は、最適化器とバックエンドが共同で処理する型付き中間言語です。SSA 値、明示的な制御フロー、明示的なメモリ操作を含みますが、すべての値が最終的に物理レジスタに配置されることを意味するものではなく、あるソース言語の全セマンティクスと同等でもありません。

以下の例では、最新の ptr 不透明ポインタ構文を使用しており、この構文をサポートする同じバージョンの LLVM ツールで検証できます。言語リファレンスは各命令の正確なセマンティクスを規定しており、名称だけで推測してはいけません。LLVM 言語リファレンス

3つの表現とツールの役割分担

テキスト形式の .ll は可読性に優れ、bitcode の .bc はシリアライズ用に使用され、メモリ上の IR はコンパイラ API によって操作されます。llvm-as はテキストを bitcode に変換し、llvm-dis はその逆を行います。opt は IR の解析と変換を行い、llc はターゲットコードを生成します。すべてのツールが任意の3つの表現間で相互変換できるわけではありません。

まず clang -S -emit-llvm を用いて C コードの IR を観察し、その後、小さな手書きモジュールで具体的な命令を理解することをお勧めします。最適化レベルによって出力構造は顕著に異なります。

名前、型、および基本ブロック

@name は通常、グローバル変数または関数を参照し、%name はローカル値、引数、およびその他のローカル識別子を参照できます。整数型 i32 は 32 ビットを表しますが、符号付き属性は自带していません。icmp slt、icmp ult、および異なる除算命令は、それぞれ符号付きまたは符号なしの解釈を選択します。

基本ブロックは終端命令（br、ret、または switch）で終了します。通常命令は終端命令の後に配置して実行を継続することはできません。φ 命令はブロックの先頭に位置し、先行ブロックから入力を受け取ります。間接関数呼び出しは、call 命令の関数ポインタターゲットを使用します。indirectbr を通常の仮想関数呼び出し命令として扱ってはなりません。

実行可能なモジュール

以下を example.ll として保存してください：

%Pair = type { i32, double }

define i32 @choose_add(i1 %take_a, i32 %a, i32 %b) {
entry:
  br i1 %take_a, label %left, label %right
left:
  %a1 = add i32 %a, 1
  br label %merge
right:
  %b1 = add i32 %b, 1
  br label %merge
merge:
  %result = phi i32 [ %a1, %left ], [ %b1, %right ]
  ret i32 %result
}

define double @read_weight(ptr %p) {
entry:
  %field = getelementptr %Pair, ptr %p, i64 0, i32 1
  %value = load double, ptr %field
  ret double %value
}

define i32 @main() {
entry:
  %pair = alloca %Pair
  %weight = getelementptr %Pair, ptr %pair, i64 0, i32 1
  store double 2.500000e+00, ptr %weight
  %got = call double @read_weight(ptr %pair)
  %a = call i32 @choose_add(i1 true, i32 40, i32 9)
  %b = call i32 @choose_add(i1 false, i32 40, i32 9)
  %ok_a = icmp eq i32 %a, 41
  %ok_b = icmp eq i32 %b, 10
  %ok_w = fcmp oeq double %got, 2.500000e+00
  %ok_ab = and i1 %ok_a, %ok_b
  %ok = and i1 %ok_ab, %ok_w
  %status = select i1 %ok, i32 0, i32 1
  ret i32 %status
}

llvm-as example.ll -o example.bc
opt -passes=verify -disable-output example.bc
lli example.bc
opt -passes='default<O2>' -S example.bc -o optimized.ll

main 関数は、2つの分岐の実際の結果と構造体フィールドの読み取り結果を用いて終了状態を構築し、成功の場合は 0 を返します。バリデーターは IR の構造と一部のセマンティクス条件をチェックしますが、ランタイム時にすべてのポインタが有効であることを証明するものではありません。

Opaque pointer：ポインタ型は pointee type を保持しない

最新の ptr は、i32 を指すのか double を指すのかをエンコードしません。読み書きの幅は load/store 命令によって与えられ、アドレス計算のレイアウトは GEP のソース要素型によって与えられます。アドレス空間は依然としてポインタ型の重要な部分であり、すべての ptr を同じ物理表現として扱ってはなりません。Opaque Pointers

したがって、load i32, ptr %p は、p が実際に i32 を指していることをランタイムにチェックするものではなく、フロントエンドが今回の読み取りに i32 のセマンティクスを使用することを宣言するものです。有効なオブジェクト、アラインメント、ライフタイム、およびエイリアシングなどの要件は依然として満たす必要があります。

GEP：最初のインデックスは「間接参照」ではない

%Pair に対して、getelementptr %Pair, ptr %p, i64 0, i32 1 は、まず 0 番目の Pair を選択し、次にフィールド 1 を選択します。フィールドのオフセットには、ターゲットの DataLayout に基づくアラインメントとパディングが含まれており、単に前のフィールドのサイズを足し合わせたものではありません。

最初のインデックスは 0 でなくてもよい：%p を連続する Pair シーケンスのベースアドレスと見なす場合、インデックス 2 は Pair の割り当てサイズに従って 2 要素分進むことを意味します。通常の配列要素へのアクセスでも非ゼロのインデックスがよく使用され、opaque pointer はこれを no-op に変えるものではありません。

GEP 自体はメモリアクセスを行いません。計算されたアドレスがすべて読み取り可能であるという意味ではありません。inbounds は、より強いオブジェクトおよび計算制約を追加し、違反すると poison が発生する可能性があります。「最適化を良くするために」という理由で根拠なく追加してはいけません。

Pair 配列：要素のストライドとフィールドオフセットは一緒に計算する

一般的な x86-64 System V レイアウトでは、{ i32, double } のフィールド 0 はバイト [0,4) を占め、その後に 4 バイトのパディングがあり、フィールド 1 は [8,16) を占め、オブジェクト全体のサイズは 16 です。Pair 配列の 2 番目の要素の weight にアクセスする場合、オフセットは 2*16+8=40 であり、2*(4+8)+4=28 ではありません。

同じターゲットの C レイアウトでクロスチェックできます。ここでは静的アサーションで期待値を明確に固定しており、これらの数値が任意の DataLayout に適用可能であると主張するものではありません：

#include <stddef.h>
struct Pair { int tag; double weight; };
_Static_assert(sizeof(int) == 4, "requires 32-bit int");
_Static_assert(sizeof(struct Pair) == 16, "different target layout");
_Static_assert(offsetof(struct Pair, weight) == 8, "different field layout");
int main(void) {
    struct Pair pairs[3] = {{0, 0.0}, {0, 0.0}, {7, 2.5}};
    return pairs[2].weight != 2.5;
}

「ポインタは 64 ビットである」という理由だけで、集約全体のレイアウトを単独で導出しないでください。DataLayout は異なる型サイズとアラインメントも規定しており、packed 構造体はフィールド間のパディングを変更します。アドレスを計算できたとしても、load のアラインメントの約束は実際のオブジェクトと一致している必要があります。GEP レイアウト説明

どのオブジェクト、どのフィールド、それぞれがどの程度のオフセットを寄与するか？

アドレスに対する乗算と加算は、それぞれ2層の選択に対応しています：i 個の完全なオブジェクトを跨ぎ、その後、現在のオブジェクトのフィールドに入る。以下では各行のバイト目盛りを保持し、通常のレイアウトのパディングと packed の短いストライドを明示的に描画します。変化するのは例示された DataLayout であり、load は実行されません。あるフィールドのアドレスが自然アラインメントでない場合、後続のアクセスに対して根拠なくより強いアラインメントの約束を追加することはできません。

$$\mathrm{addr}=\mathrm{base}+i\cdot \mathrm{allocSize}(T)+\mathrm{fieldOffset}(T,j)$$

算術フラグとソース言語セマンティクス

通常の整数 add はビット幅で処理されます。nsw、nuw はそれぞれオーバーフローしないという約束を表し、自動的にオーバーフローチェックを行ってソース言語の例外を投げるものではありません。ソース言語で加算のチェックが必要な場合、フロントエンドは検出、分岐、または適切な intrinsic を生成する必要があります。

同様に、無条件評価の select ですべての短絡 && を単純に置き換えることはできません。右辺で関数呼び出し、メモリアクセス、または例外発生が発生する可能性がある場合、ソース言語の条件付き実行を保持する必要があります。事前に計算された2つの値の選択と、評価制御を行うことは異なります。

オーバーフローチェック付き加算：オーバーフローフラグを制御フローに変換する

インターフェースの規約を以下のように設定します：2つの符号付き i32 を加算し、成功した場合、出力スロットに書き込み 1 を返し、オーバーフローした場合、出力スロットを変更せずに 0 を返します。通常の add にはこのチェック動作はなく、add nsw も自動的に失敗分岐にジャンプしません。checked.ll として保存してください：

declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32)

define i32 @checked_add(i32 %a, i32 %b, ptr %out) {
entry:
  %pair = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %a, i32 %b)
  %sum = extractvalue { i32, i1 } %pair, 0
  %overflow = extractvalue { i32, i1 } %pair, 1
  br i1 %overflow, label %failure, label %success
success:
  store i32 %sum, ptr %out, align 4
  ret i32 1
failure:
  ret i32 0
}

この intrinsic は、切り捨てられたビットパターンと符号付きオーバーフローフラグの両方を生成します。失敗分岐で %sum を使用しない場合でも、フラグの計算は消滅しません。成功分岐のみが結果を呼び出し元に公開します。ここでインターフェースは、out が有効で少なくとも 4 バイトアラインされた i32 出力オブジェクトを指すことを要求しており、C ドライバは通常の int オブジェクトを使用してこのターゲット要件を満たします。オーバーフロー検出付き加算

/* checked-main.c：clang checked.ll checked-main.c -o checked-demo */
#include <limits.h>
_Static_assert(INT_MAX == 2147483647, "requires 32-bit int");
extern int checked_add(int, int, int *);
int main(void) {
    int out = 99;
    if (checked_add(20, 22, &out) != 1 || out != 42) return 1;
    if (checked_add(INT_MAX, 0, &out) != 1 || out != INT_MAX) return 2;
    out = 99;
    if (checked_add(INT_MAX, 1, &out) != 0 || out != 99) return 3;
    if (checked_add(INT_MIN, -1, &out) != 0 || out != 99) return 4;
    if (checked_add(INT_MIN, 0, &out) != 1 || out != INT_MIN) return 5;
    return 0;
}

入力に INT_MAX と 1 を指定した場合、数学的な和は符号付き範囲を超え、0 を返し、元の out=99 を保持します。INT_MAX と 0 の場合、境界値自体は合法であり、1 を返します。2つの分岐の違いは明示的な IR によって定義されており、最適化器は機械語の実装を変更できますが、このインターフェース動作を保持する必要があります。

同じビットパターンが、なぜ同じ約束を表せないのか？

ビットパターンとインターフェースの約束を並べて配置することで、「オーバーフローした」という言葉ですべての動作を概括することを防ぎます。以下では i8 に縮小して符号ビットを見やすくしていますが、3つのセマンティクスは依然として分離されています。モジュラ加算は切り捨てられたビットパターンを生成し、nsw は約束を超える結果に対して poison を与え、チェックインターフェースは明示的な分岐を通じて out への書き込み可否を決定します。poison ラベルは結果のカテゴリを示すだけで、後続の任意の使用の動作をシミュレートするものではありません。

可変ローカル変数とアドレスの同一性

フロントエンドの初学者は、可変ローカル変数に対して適切な alloca を作成し、load/store を使用してから、mem2reg または SROA によって最適化可能な部分を昇格させることができます。「alloca へのアドレス取得」自体が昇格を阻止するわけではありません。alloca は本来アドレスを返すものです。重要なのは、アドレスの具体的な使用が昇格の条件に合致しているかどうかです。

ソースプログラムにおいて、オブジェクトのアドレスがエスケープする可能性がある、またはアイデンティティが観測可能な場合、フロントエンドは最初から正しくモデル化する必要があります。最適化後にソースコードの &x を見て、適当に新しい alloca を作成し、元のオブジェクトのアイデンティティを回復したと主張してはいけません。

モジュールと ABI の境界

ターゲット triple と DataLayout はレイアウトと生成されるターゲットに影響します。外部関数を呼び出すには、正しい署名、呼び出し規約、引数属性、および ABI の lowering が必要です。IR における集約引数の書き方が、すべてのプラットフォームの C ABI に自然に適合するとは限りません。

musttail、例外呼び出し、アトミック操作、volatile、および各種属性には独立した制約があります。まず最小限の信頼できるセマンティクスを用いて合法な IR を生成し、証明に基づいて最適化情報を追加してください。誤った属性は、最適化器が元の意図に反するプログラムを合法に生成する原因となります。

参考

• LLVM 言語リファレンス。
• Opaque Pointers。
• Kaleidoscope：可変変数と昇格。

Keywords: LLVM IR, bitcode, ptr, opaque pointer, phi, GEP, load, store, DataLayout, poison, mem2reg, verifier