てけもぐ Tech 忘備録

LLVM-IR の getelementptr で勘違いしてた話

対象

LLVM 初学者

内容

https://github.com/mzuhi5/tiny_c_compiler の続きで、LLVMBuildGEP2() の話を書こうと思ったのだけど、その前の GEP の話だけになりましたとさ。合っているかは知らないけれど、一応それっぽく理解出来た気がするのでメモ。

LLVM の GEP(Get Element Pointer) が理解しずらいのは自分だけじゃないみたいで、公式にそれ用のページ - The Often Misunderstood GEP Instruction - がある。

基本的には、これは単に変数に対するアドレス計算命令。

それなのに、こいつに会うといつも混乱する。

本来はマニュアルに書いてある説明の通り。この中でインデックスの引数の指定の仕方にポイントがある。

ポイントは以下の３点。

  1. deref(メモリ先からのロード) するの？
  2. インデックスの引数がひとつ多い時ない？
  3. 構造体の時のインデックスの型がいつも i32 で、構造体の要素型にあってないけどなんで？

まず１つ目のは、「しない」。getelementptr() は、アドレスの計算をするだけでメモリの中身は読みに行かない。これは以下の様にここに記述あり。

It performs address calculation only and does not access memory.

２つ目の、インデックスの引数がひとつ多い時ない？は、The Often Misunderstood GEP Instruction のここと、その一つ後の項に書いてある。手っ取り早く言うと、ベースになる変数はいつもポインタ(レジスタ)変数なので、対象のアドレスをこのポインタ変数から取り出す必要があるからだよ！という話かと。

３つ目の、struct に対するインデックスの型がいつも i32 なのは、リファレンスマニュアルのここにも一応載ってる。

The type of each index argument depends on the type it is indexing into. When indexing into a (optionally packed) structure, only i32 integer constants are allowed (when using a vector of indices they must all be the same i32 integer constant). When indexing into an array, pointer or vector, integers of any width are allowed, and they are not required to be constant. These integers are treated as signed values where relevant.

もう少し詳しい説明が、The Often Misunderstood GEP Instruction の下の方にあり、

The specific type i32 is probably just a historical artifact, however it’s wide enough for all practical purposes, so there’s been no need to change it. It doesn’t necessarily imply i32 address arithmetic; it’s just an identifier which identifies a field in a struct. Requiring that all struct indices be the same reduces the range of possibilities for cases where two GEPs are effectively the same but have distinct operand types.

とある。

ここで自分の勘違いにハタと気づく...。

インデックスに指定している、i32 1 などの型というのは、実際のメモリ配置のアドレス先の型の事ではなくて、i32 1 の 1 を指し示してる型なんだって。ガーン。オフセットを計算する型として掛け算に使っているのかと思っていたら、違いました。オフセット計算は型の定義の方から引っ張るんでしょうね。これですわ、分からなかった理由。うへぇ。「The type of each index argument depends on the type it is indexing into. 」を見て、メモリ上で指し示す型なのかと思ってしまってました。

上の引用したドキュメントに書いてある通り、構造体の場合は i32 の大きさの固定数、配列やポインタの場合は自由な符号付き整数型で、しかも固定数じゃなくてもいいと。

リファレンスマニュアルに載っている例で見てみる。

struct RT {
  char A;
  int B[10][20];
  char C;
};
struct ST {
  int X;
  double Y;
  struct RT Z;
};

int *foo(struct ST *s) {
  return &s[1].Z.B[5][13];
}

これの IR も引用すると、

%struct.RT = type { i8, [10 x [20 x i32]], i8 }
%struct.ST = type { i32, double, %struct.RT }

define ptr @foo(ptr %s) {
entry:
  %arrayidx = getelementptr inbounds %struct.ST, ptr %s, i64 1, i32 2, i32 1, i64 5, i64 13
  ret ptr %arrayidx
}

i64 1, i32 2, i32 1, i64 5, i64 13がそれぞれ、&s[1].Z.B[5][13]に対応でしょうか。

clang -S -O0 -emit-llvm sample.c として最適化を外すと、以下の様にそれぞれ分かれて出力される。

%struct.ST = type { i32, double, %struct.RT }
%struct.RT = type { i8, [10 x [20 x i32]], i8 }

define dso_local ptr @foo(ptr noundef %0) #0 {
  %2 = alloca ptr, align 8
  store ptr %0, ptr %2, align 8
  %3 = load ptr, ptr %2, align 8
  %4 = getelementptr inbounds %struct.ST, ptr %3, i8 1
  %5 = getelementptr inbounds %struct.ST, ptr %4, i8 0, i32 2
  %6 = getelementptr inbounds %struct.RT, ptr %5, i8 0, i32 1
  %7 = getelementptr inbounds [10 x [20 x i32]], ptr %6, i8 0, i64 5
  %8 = getelementptr inbounds [20 x i32], ptr %7, i64 0, i8 13
  ret ptr %8
}

この内、構造体内のアドレス計算をするもの以外は、先程の箇所で述べられている通り i32 型じゃなくてもいい。i8 になってるところも i64 や i32 としてもコンパイルは通る。

%5 = getelementptr inbounds %struct.ST, ptr %4, i8 0, i32 2 の行は、その前の行でせっかくポインタをアドレスに変えたのに、また i8 0 ともう一度ポインタからアドレスを取り出すのか？と一瞬思いましたが、%4という(ポインタ)変数から取り出すので必要ということ。

ちなみに、ポインタや配列を対象にしている場合は、 i8/i32/i64 なども使える、符号付きなのでマイナスでも行けるし、変数でもオーケーで、以下のようなサンプルだと、

int foo(){
  return 2;
}
int main() {
  char array[3];
  int i = foo();
  array[i-1] = 'A';
}

吐き出されれる IR には、 %7 = getelementptr inbounds [3 x i8], ptr %1, i64 0, i64 %6 の様に、インデックスに変数を指定出来る行が出て来る。考えてみればそれが出来なきゃアドレス計算できないわな。そして構造体の場合はこのパターンは許可しない。構造体の要素はコンパイル時に決まっているのでインデックスは固定数、しかも i32 の大きさより大い構造体の要素数なんてないだろうから i32 の大きさまで。つまり、構造体の中をただのメモリ列として考えてオフセット計算をやるなら、別の方法を取る必要があるんでしょうね。なるほど。

一応 IR ファイルを弄ってコンパイルを確認してみたりしたけども、この理解でいいのだろうかなぁ。

LLVM-C API の方の話はまた今度。

Tags

#LLVM