LLVM IR の alloca 命令のつかいかた - はやくプログラムになりたい

LLVM IR の alloca 命令の使い方について，リファレンスマニュアルに載ってない注意点があったのでメモがてら書きます．

`alloca` 命令とは

スタック上にメモリを確保し，確保した領域の先頭へのポインタを返します．スタック上にメモリを割り付けることでアドレスが必要なメモリ領域を得ることができ，自動変数などの実装に使うことができます．

http://llvm.org/docs/LangRef.html#alloca-instruction

%ptr = alloca i32                             ; yields i32*:ptr
%ptr = alloca i32, i32 4                      ; yields i32*:ptr
%ptr = alloca i32, i32 4, align 1024          ; yields i32*:ptr
%ptr = alloca i32, align 1024                 ; yields i32*:ptr

変数などは基本的にこの alloca 命令を使って領域を確保するお馴染みの命令です．スタック上に割り当てるので，関数を抜けると同時にその領域は解放されます．

と，ここまでならリファレンスマニュアルを読めばそれで解決なのですが，いくつか注意点があります．

`alloca` によるメモリ割り当てのタイミング

例えば下記のようなループを実装したいケース

int i = 0;
while (i < 10) {
    int j = i * 2;
    printf("%d\n", j);
    ++i;
}

そのまま書き下すと

  %i = alloca i32
  store i32 0 i32* %i
  br label %loop.init
loop.init:
  %i1 = load i32 i32* %i
  %0 = icmp sle i32 %i1 10
  br i1 %0 label %loop.end, label %loop.body
loop.body:
  %1 = mul i32 %i1, 2
  %j = alloca i32
  store i32 %1 i32* %j
  %2 = load i32 i32* %j
  call void @printf(i8* @str, i32 %2)
  %3 = add i32 %i1, 1
  store i32 %3 i32* %i
  br label %loop.init
loop.end:

のような IR をつくりたくなりますが，これだと10行目の %j = alloca i32 がループごとに確保されてしまうので，ループするだけで再帰でもないのにどんどんスタックを食っていってしまいます．

なので，下記のようにスタックのアロケーションは原則関数の頭でやります．

  %i = alloca i32
  %j = alloca i32
  store i32 0 i32* %i
  br label %loop.init
loop.init:
  %i1 = load i32 i32* %i
  %0 = icmp sle i32 %i1 10
  br i1 %0 label %loop.end, label %loop.body
loop.body:
  %1 = mul i32 %i1, 2
  store i32 %1 i32* %j
  %2 = load i32 i32* %j
  call void @printf(i8* @str, i32 %2)
  %3 = add i32 %i1, 1
  store i32 %3 i32* %i
  br label %loop.init
loop.end:

これは割と常識らしく，Clang は明示的にブロックをつくりこそしませんが，関数の頭で alloca を呼んでいます．Rust や Crystal は関数の最初にその関数内で必要なスタック領域をすべて alloca する基本ブロックを置く実装になっています．どちらでも良いですが，LLVM の C++ API でなく C bindings な llvm-c を使う場合は後者の方が実装がかなり楽だと思います．

C89 までブロックの先頭でしか変数を定義できなかったのはこういった理由があるのかもしれません（未確認）

関数の頭でメモリを割り当てられない例外：動的サイズ配列

ここまでは一般的なケースですが，残念ながらこれではうまくいかないケースがあります．C99 の動的サイズ配列です． alloca 命令はN要素分の領域確保もできるためスタック上に動的サイズでメモリを確保すること自体は問題なくできます．

int i = 0;
while (i < 10) {
    int arr[i + 1];
    arr[i] = 42;
    printf("%d\n", arr[i]);
    ++i;
}

例えば上記のようなコードの場合，arr の確保する領域は i の値に応じて動的に変わります．なので，関数の先頭で alloca しておく前述の方法は使えません．しかし，ループの中で単に alloca してしまうとループが回るごとにスタックが積み上がっていってしまい，無限ループでもしようものならスタックを使い切ってプログラムがクラッシュしてしまうでしょう．

そこで，LLVM には llvm.stacksave と llvm.stackrestore という intrinsic 関数があります．前者は現在のスタック位置をレジスタに保存し，後者はレジスタの値にスタック位置を復帰します．

  %0 = call i8* @llvm.stacksave()      ; 現在のスタック位置を %0 に保存
  %1 = alloca i32, i64 %x              ; i32 の値を %x 個分確保する
  ; %1 を使った処理
  call void @llvm.stackrestore(i8* %0) ; スタック位置を復帰．%1 の領域は解放される