しばしば誤解されるGEP命令¶

はじめに ¶

このドキュメントでは、LLVMのGetElementPtr（GEP）命令を取り巻く謎と混乱を解消することを目指しています。開発者がLLVMでのコーディングを始めるといちばん頻繁に発生する質問はおそらく、この厄介なGEP命令に関する質問です。ここでは、混乱の根源を明らかにし、GEP命令は実際には非常にシンプルであることを示します。

アドレス計算 ¶

GEP命令に初めて遭遇した人は、他のプログラミングパラダイム、特にC言語の配列インデックス付けとフィールド選択から既知の概念に関連付けようとする傾向があります。GEPはC言語の配列インデックス付けとフィールド選択によく似ていますが、少し異なっており、これが以下の質問につながります。

GEP命令の最初のインデックスとは？¶

簡潔な答え：2番目のオペランドをステップするインデックスです。

最初のインデックスに関する混乱は、GetElementPtr命令をC言語のインデックス演算子であるかのように考えてしまうことから生じることがよくあります。両者は同じではありません。「C」で次のように記述する場合

AType *Foo;
...
X = &Foo->F;

は、インデックスはFフィールドの選択のみであり、1つしかないと思うのが自然です。しかし、この例ではFooはポインターです。そのポインターはLLVMでは明示的にインデックス付けする必要があります。一方、C言語では、それを透過的にインデックス付けします。Cコードと同じアドレス位置に到達するには、GEP命令に2つのインデックスオペランドを提供する必要があります。最初のオペランドはポインターをインデックス付けし、2番目のオペランドは、次のように記述した場合と同様に、構造体のFフィールドをインデックス付けします。

X = &Foo[0].F;

この質問は、次のように言い換えられることもあります。

最初のポインターをインデックス付けしても問題ありませんが、後続のポインターは参照解除されないのはなぜですか？

その答えは、計算を実行するためにメモリにアクセスする必要がないからです。GEP命令の2番目のオペランドは、ポインター型の値である必要があります。ポインターの値は、メモリにアクセスする必要なく、オペランドとしてGEP命令に直接提供されます。したがって、インデックス付けする必要があり、インデックスオペランドが必要です。次の例を考えてみましょう。

struct munger_struct {
  int f1;
  int f2;
};
void munge(struct munger_struct *P) {
  P[0].f1 = P[1].f1 + P[2].f2;
}
...
struct munger_struct Array[3];
...
munge(Array);

この「C」の例では、フロントエンドコンパイラ（Clang）は代入文の「P」を通る3つのインデックスに対して3つのGEP命令を生成します。関数引数Pは、これらのGEP命令のそれぞれ2番目のオペランドになります。3番目のオペランドはそのポインターをインデックス付けします。4番目のオペランドは、f1またはf2フィールドのいずれかのstruct munger_struct型へのフィールドオフセットになります。そのため、LLVMアセンブリではmunge関数は次のようになります。

define void @munge(ptr %P) {
entry:
  %tmp = getelementptr %struct.munger_struct, ptr %P, i32 1, i32 0
  %tmp1 = load i32, ptr %tmp
  %tmp2 = getelementptr %struct.munger_struct, ptr %P, i32 2, i32 1
  %tmp3 = load i32, ptr %tmp2
  %tmp4 = add i32 %tmp3, %tmp1
  %tmp5 = getelementptr %struct.munger_struct, ptr %P, i32 0, i32 0
  store i32 %tmp4, ptr %tmp5
  ret void
}

いずれの場合も、2番目のオペランドはGEP命令が開始するポインターです。2番目のオペランドが引数、割り当てられたメモリ、グローバル変数のいずれであるかにかかわらず、同じことが当てはまります。

これを明確にするために、よりわかりにくい例を考えてみましょう。

@MyVar = external global i32
...
%idx1 = getelementptr i32, ptr @MyVar, i64 0
%idx2 = getelementptr i32, ptr @MyVar, i64 1
%idx3 = getelementptr i32, ptr @MyVar, i64 2

これらのGEP命令は、MyVarのベースアドレスからアドレス計算を実行しているだけです。次のようになります（C構文を使用）。

idx1 = (char*) &MyVar + 0
idx2 = (char*) &MyVar + 4
idx3 = (char*) &MyVar + 8

i32型は4バイトの長さであることがわかっているので、インデックス0、1、2はそれぞれ0、4、8のメモリオフセットに変換されます。@MyVarのアドレスはGEP命令に直接渡されるため、これらの計算を行うためにメモリはアクセスされません。

この例でわかりにくい部分は、%idx2と%idx3の場合です。これらは、@MyVarグローバル（i32が1つだけ、3つのi32ではありません）の末尾を超えるメモリを指すアドレスの計算になります。これはLLVMでは合法ですが、これらのGEP命令から得られるポインターを使用したロードまたはストアは未定義動作（UB）をトリガーするため、推奨されません。

なぜ余分な0インデックスが必要なのですか？¶

簡潔な答え：余分なインデックスはありません。

この質問は、GEP命令がグローバル変数（常にポインター型）に適用される場合に最も頻繁に発生します。たとえば、次のことを考えてみましょう。

%MyStruct = external global { ptr, i32 }
...
%idx = getelementptr { ptr, i32 }, ptr %MyStruct, i64 0, i32 1

上記のGEPは、構造体%MyStructのi32型フィールドをインデックス付けすることによってptrを生成します。初めて見た人は、i64 0インデックスが必要な理由を疑問に思うかもしれません。しかし、グローバルとGEPの動作を詳しく調べると、その必要性が明らかになります。次の事実を認識すると、混乱が解消されます。

%MyStructの型は{ ptr, i32 }ではなくptrです。つまり、%MyStructは（構造体への）ポインターであり、構造体自体ではありません。
ポイント1は、GEP命令の2番目のオペランド（%MyStruct）の型がptrであることに注目することで証明されています。
最初のインデックスi64 0は、グローバル変数%MyStructをステップするために必要です。GEP命令の2番目の引数は常にポインター型の値である必要があるため、最初のインデックスはそのポインターをステップします。値0は、そのポインターからのオフセットが0要素であることを意味します。
2番目のインデックスi32 1は、構造体の2番目のフィールド（i32）を選択します。

GEPによって参照解除されるものは？¶

簡潔な答え：何もありません。

GetElementPtr命令は何ものも参照解除しません。つまり、いかなる方法でもメモリにアクセスしません。それがLoad命令とStore命令の役割です。GEPはアドレス計算のみに関与します。たとえば、次のことを考えてみましょう。

@MyVar = external global { i32, ptr }
...
%idx = getelementptr { i32, ptr }, ptr @MyVar, i64 0, i32 1
%arr = load ptr, ptr %idx
%idx = getelementptr [40 x i32], ptr %arr, i64 0, i64 17

この例では、ポインターを含む構造体へのポインターであるグローバル変数@MyVarがあります。この内部ポインターが[40 x i32]型の配列を指していると仮定しましょう。上記のIRは、最初に内部ポインターのアドレスを計算し、次にポインターをロードし、次に18番目の配列要素のアドレスを計算します。

これは、間にメモリ参照解除が必要なため、単一のGEP命令では表現できません。ただし、次の例は問題なく機能します。

@MyVar = external global { i32, [40 x i32 ] }
...
%idx = getelementptr { i32, [40 x i32] }, ptr @MyVar, i64 0, i32 1, i64 17

この場合、構造体にはポインターが含まれておらず、GEP命令はグローバル変数をインデックス付けして、構造体の2番目のフィールドにアクセスし、そこに含まれる18番目のi32にアクセスできます。

GEP x,0,0,1とGEP x,1がエイリアスにならないのはなぜですか？¶

簡潔な答え：異なるアドレス位置を計算します。

これらのGEP命令の最初のインデックスを見ると、それらが異なる（0と1）ことがわかります。したがって、アドレス計算はそのインデックスで異なります。次の例を考えてみましょう。

@MyVar = external global { [10 x i32] }
%idx1 = getelementptr { [10 x i32] }, ptr @MyVar, i64 0, i32 0, i64 1
%idx2 = getelementptr { [10 x i32] }, ptr @MyVar, i64 1

この例では、idx1は@MyVarにある構造体内の配列の2番目の整数のアドレス、つまりMyVar+4を計算します。しかし、idx2は@MyVarの後の*次の*構造体のアドレス、つまりMyVar+40を計算します。これは、MyVar内の10個の4バイト整数をインデックス付けするためです。明らかに、このような状況では、ポインターはエイリアスになりません。

GEP x,1,0,0とGEP x,1がエイリアスになるのはなぜですか？¶

簡潔な答え：同じアドレス位置を計算します。

これらの2つのGEP命令は、0番目の要素をインデックス付けしてもアドレスが変わらないため、同じアドレスを計算します。次の例を考えてみましょう。

@MyVar = global { [10 x i32] }
%idx1 = getelementptr { [10 x i32] }, ptr @MyVar, i64 1, i32 0, i64 0
%idx2 = getelementptr { [10 x i32] }, ptr @MyVar, i64 1

この例では、%idx1の値はMyVar+40であり、%idx2の値もMyVar+40です。

GEPはベクトル要素にインデックス付けできますか？¶

これは常に強制的に禁止されていたわけではありませんが、推奨されません。最適化器において厄介な特殊なケースを引き起こし、IRに根本的な矛盾を生じさせます。将来は、完全に禁止される可能性が高いです。

アドレス空間はGEPにどのような影響を与えますか？¶

結果型のアアドレス空間修飾子が、第2オペランドポインタ型のアアドレス空間修飾子と常に一致すること以外は、ありません。

GEPは`ptrtoint`、算術演算、および`inttoptr`とどう違いますか？¶

非常に似ていますが、微妙な違いがあります。

ptrtointでは、整数型を選択する必要があります。i64を選択するアプローチがあります。これはLLVMがサポートするすべてのものにおいて安全であり（LLVMは内部的に多くの場所でポインタが64ビットより幅広くなることはないと仮定しています）、最適化器は実際には、ほとんどの場合64ビット算術演算をサポートしないターゲットでi64算術演算を実際のポインタサイズに狭めます。ただし、そうならない場合もあります。GEPを使用すると、この問題を回避できます。

また、GEPは追加のポインタエイリアシング規則を備えています。あるオブジェクトからGEPを取得し、別の別々に割り当てられたオブジェクトにアドレスを指定して参照外しを行うことは無効です。IR生成元（フロントエンド）は、この規則に従う必要があり、消費元（最適化器、特にエイリアス解析）は、それに依存できるという利点があります。詳細については、規則セクションを参照してください。

そして、GEPは一般的なケースではより簡潔です。

ただし、暗黙の基礎となる整数計算については、違いはありません。

GEPのカスタムローワーリングが必要なターゲットのバックエンドを作成しています。どのようにすればよいですか？¶

あなたはそうしません。GEPによって暗示される整数計算はターゲットに依存しません。通常、行う必要があるのは、GEPがローワーされるADD、MULなどの式ツリーをバックエンドでパターンマッチングすることです。これには、コードがより多くのケースで正しく動作するという利点があります。

GEPは、データ型のサイズとレイアウトにターゲット依存のパラメータを使用しており、ターゲットでカスタマイズできます。

8ビット以外のアドレス単位をサポートする必要がある場合、バックエンドの多くのコードを修正する必要があります。GEPのローワーリングは全体像のごく一部にすぎません。

VLAアドレス指定はGEPでどのように機能しますか？¶

GEPはネイティブにVLAをサポートしていません。LLVMの型システムは完全に静的であり、GEPアドレス計算はLLVM型によって導かれます。

VLAインデックスは線形化されたインデックスとして実装できます。X[a][b][c]のような式は、X[a*m+b*n+c]のような形式に効果的にローワーされる必要があるため、GEPに1次元配列参照として表示されます。

つまり、配列インデックスを理解する分析を作成し、VLAをサポートしたい場合は、コードは線形化を逆エンジニアリングする準備ができていなければなりません。この問題を解決する1つの方法は、ScalarEvolutionライブラリを使用することです。これは常にVLAと非VLAのインデックスを同じ方法で提示します。

規則 ¶

配列インデックスが範囲外になった場合、どうなりますか？¶

配列インデックスが範囲外になるには、2つの意味があります。

まず、GEPの最初のオペランドの（静的）型から得られる配列型があります。対応する静的配列型にある要素数よりも大きいインデックスは有効です。この意味では、範囲外のインデックスに問題はありません。配列へのインデックス付けは、配列要素のサイズにのみ依存し、要素の数には依存しません。

これがどのように使用されるかの一般的な例は、サイズが不明な配列です。これらの表現には、長さ0の配列型を使用するのが一般的です。静的型が要素が0個であると述べているという事実は無関係です。計算は配列要素のサイズにのみ依存し、要素の数には依存しないため、任意の要素インデックスを計算することは完全に有効です。長さ0の配列はここでは特別なケースではありません。

この意味はinboundsキーワードとは無関係です。inboundsキーワードは、高レベルの配列インデックス付け規則ではなく、低レベルのポインタ算術オーバーフロー条件を記述するために設計されています。

配列インデックスを理解したい分析パスは、静的配列型境界が尊重されると仮定すべきではありません。

2番目の範囲外の意味は、実際の基礎となる割り当てられたオブジェクトを超えるアドレスを計算することです。

inboundsキーワードを使用すると、アドレスが実際の基礎となる割り当てられたオブジェクトの外側にあり、end-of-the-arrayではない場合、GEPの結果値はpoisonになります。

inboundsキーワードがない場合、範囲外のアドレスを計算することには制限がありません。明らかに、ロードまたはストアを実行するには、割り当てられ、十分に整列されたメモリのアドレスが必要です。しかし、GEP自体はアドレスの計算のみに関係します。

配列インデックスは負にすることができますか？¶

はい。これは基本的に、配列インデックスが範囲外になる特別なケースです。

GEPで計算された2つの値を比較できますか？¶

はい。両方のアドレスが同じ割り当てられたオブジェクト内にある場合、またはend-of-the-arrayの場合、予想される比較結果が得られます。どちらかがそれの外側にある場合、整数演算のラップアラウンドが発生する可能性があるため、比較が無意味になる可能性があります。

基礎となるオブジェクトの型とは異なるポインタ型でGEPを実行できますか？¶

はい。ポインタ値を任意のポインタ型にビットキャストすることには制限がありません。GEPの型は、基礎となる整数計算のパラメータを定義するためだけに役立ちます。基礎となるオブジェクトの実際の型と対応する必要はありません。

さらに、ロードとストアは、基礎となるオブジェクトの型と同じ型を使用する必要はありません。このコンテキストでの型は、メモリサイズとアライメントを指定するためだけに役立ちます。それ以外は、最適化器へのヒントであり、値がどのように使用される可能性が高いかを示しています。

オブジェクトのアドレスを整数にキャストしてnullに追加できますか？¶

その方法でアドレスを計算できますが、GEPを使用して加算を行う場合、オブジェクトがLLVMの外で管理されていない限り、そのポインタを使用してオブジェクトに実際にアクセスすることはできません。

基礎となる整数計算は十分に定義されています。nullには定義された値（ゼロ）があり、任意の値を追加できます。

ただし、そのようなポインタを使用してLLVM認識オブジェクト（GlobalVariables、Allocas、およびnoaliasポインタによって指されるオブジェクトを含む）にアクセスする（ロードまたはストア）することは無効です。

この機能が実際に必要な場合は、明示的な整数命令で算術演算を行い、inttoptrを使用して結果をアドレスに変換できます。GEPの特殊なエイリアシング規則のほとんどは、ptrtoint、算術演算、inttoptrシーケンスから計算されたポインタには適用されません。

2つのオブジェクト間の距離を計算し、その値を1つのアドレスに追加して別のアドレスを計算できますか？¶

nullの算術演算と同様に、GEPを使用してその方法でアドレスを計算できますが、オブジェクトがLLVMの外で管理されていない限り、そのポインタを使用してオブジェクトに実際にアクセスすることはできません。

上記と同様に、ptrtointとinttoptrは、この制限がない代替の方法を提供します。

LLVM IRで型ベースのエイリアス解析を実行できますか？¶

LLVMの組み込み型システムを使用して型ベースのエイリアス解析を実行することはできません。なぜなら、LLVMはアドレス指定、ロード、またはストアで型を混在させることについて制限がないからです。

LLVMの型ベースのエイリアス解析パスは、メタデータを使用して異なる型システム（C型システムなど）を記述し、その上で型ベースのエイリアシングを実行します。詳細は、言語リファレンスを参照してください。

GEP計算がオーバーフローした場合、どうなりますか？¶

GEPにinboundsキーワードがない場合、値は暗黙の2の補数整数計算を評価した結果になります。ただし、オブジェクトがアドレス空間のどこに割り当てられるかの保証がないため、このような値の意味は限られています。

GEPにinboundsキーワードがある場合、GEPがオーバーフローする場合（つまり、アドレス空間の終わりをラップアラウンドする場合）、結果値はpoisonになります。

そのため、インバウンドGEPにはいくつかの影響があります。配列/ベクトル/ポインタインデックスによって暗示されるスケールは、符号付き値であり要素サイズでスケールされるため、常に「nsw」（no signed wrap）であることがわかっています。これらの値は負の値も許容されます（例：「gep i32, ptr %P, i32 -1」）。しかし、ポインタ自体は論理的に符号なし値として扱われます。これは、GEPにおいて、ポインタベース（符号なしとして扱われる）とそれに適用されるオフセット（符号付きとして扱われる）との間に非対称の関係が存在することを意味します。オフセット計算内の加算の結果は、符号付きオーバーフローが発生することはありませんが、ベースポインタに適用されると、符号付きオーバーフローが発生する可能性があります。

フロントエンドがルールに従っているかどうかを確認するにはどうすればよいですか？¶

現在、getelementptrルールのチェッカーはありません。現在、これを行う唯一の方法は、フロントエンドでGetElementPtr演算子が作成される場所をそれぞれ手動で確認することです。

すべてのルールの違反を静的に検出できるチェッカーを作成することは不可能です。動的チェックでコードをインストルメント化することで動作するチェッカーを作成することは可能でしょう。あるいは、考えられる問題のサブセットを検出する静的チェッカーを作成することも可能です。しかし、そのようなチェッカーは現在存在しません。

根拠 ¶

なぜGEPはこのように設計されているのですか？¶

GEPの設計には、優先順位はおおよその非公式な順序ですが、以下の目標があります。

C、Cに似た言語、および概念的にCに低減できる言語（多くの言語をカバー）をサポートします。
Cコンパイラで一般的なものなどの最適化をサポートします。特に、GEPはLLVMのポインタエイリアシングモデルの基盤です。
アドレス計算をIRのロードおよびストア命令の一部にする必要がないように、アドレスを計算するための整合性のある方法を提供します。
他の目標と干渉しない範囲で、Cに似た言語以外の言語をサポートします。
IR内のターゲット固有の情報を最小限に抑えます。

なぜ構造体メンバインデックスは常に`i32`を使用するのですか？¶

特定の型i32はおそらく単なる歴史的産物ですが、実際的な目的には十分な幅があり、変更する必要はありませんでした。必ずしもi32アドレス演算を意味するわけではありません。構造体内のフィールドを識別する識別子にすぎません。すべての構造体インデックスが同じであることを要求すると、2つのGEPが事実上同じだがオペランド型が異なる場合の可能性の範囲が狭まります。

uglygepとは何ですか？¶

一部のLLVM最適化器は、GEPを内部的によりプリミティブな整数式に低減することで動作し、それらを他の整数式と組み合わせたり、複数の個別の整数式に分割したりすることができます。非自明な変更が行われた場合、LLVM IRへの変換には、元の最初のオペランドの静的型に適合させるために、アドレス指定の構造をリバースエンジニアリングする必要があります。この構造を完全に再構築することは常に可能とは限りません。場合によっては、基礎となるアドレス指定が静的型とまったく一致しない場合があります。そのような場合、最適化器は代わりに、ベースポインタを単純なアドレス単位ポインタにキャストしたGEPを「uglygep」という名前で出力します。これは見栄えは良くありませんが、同様に有効であり、GEPが提供するポインタエイリアシングの保証を維持するのに十分です。

要約 ¶

要約すると、GetElementPtr命令について常に覚えておくべきことがいくつかあります。

GEP命令はメモリにアクセスすることはなく、ポインタ計算のみを提供します。
GEP命令の2番目のオペランドは常にポインタであり、インデックス付けする必要があります。
GEP命令には余分なインデックスはありません。
末尾のゼロインデックスは、ポインタエイリアシングには冗長ですが、ポインタの型には冗長ではありません。
先頭のゼロインデックスは、ポインタエイリアシングとポインタの型に対して冗長ではありません。

ドキュメント

参加方法

追加リンク

このページ