LLVMによるプログラミング言語の実装チュートリアル日本語訳
第7章 万華鏡: 言語の拡張: 変更可能な変数（Mutable Variables）
第3節 LLVMにおけるメモリ

LLVMは全てのレジスタをSSA形式にすることを要求するが、メモリオブジェクトに関してはSSA形式であることを要求しない（もしくは許可ししない）という点がミソである。
前節の例においては、GやHからの読み込みは、GやHに対する直接的なアクセスである。（GやHは、リネームされたりバージョン付けされていない。）
これは、メモリオブジェクトをバージョン付けしようとする他のコンパイラシステムとは違っている。
LLVMでは、メモリのデータフロー解析をLLVM IRにエンコードせずに、必要に応じて計算される解析パス（Analysis Passes）によって処理する。

これを踏まえて、関数の中における変更可能なオブジェクトのためのスタック変数（スタック上にあるので、つまりメモリ上にある）を作成したい、というのがより高いレベルのアイデアである。
この方法の利点を活かすために、LLVMはどうやってスタック変数を表現するのかということについて考える必要がある。

LLVMでは、全てのメモリアクセスはload/store命令によって明確に行われ、アドレスを得る命令（”address-of” operator）を持たない（または必要としない）よう注意深くデザインされている。
グローバル変数@G/@Hは、”i32″として定義されているが、実際は”i32*”である事に注意。
つまり、＠Gはグローバルのデータ領域にi32用の領域を定義するが、その名前は実際にはその領域のアドレスを参照するという事である。
スタック変数も、グローバル変数定義として宣言されるのではなく、LLVMのalloca命令で宣言される点を除いて（@G/@Hと）同じように動作する。

define i32 @example() {
entry:
  %X = alloca i32           ; %X は i32* 型。
  ...
  %tmp = load i32* %X       ; スタックからスタック値 %X を読み込む。
  %tmp2 = add i32 %tmp, 1   ; インクリメント。
  store i32 %tmp2, i32* %X  ; %tmp2 から %X へ書き戻す。
  ...

このコードは、LLVMにおけるスタック変数の宣言と操作の方法を例示している。
alloca命令によってスタックメモリを割り当てるのは、LLVMにおいては極めて普通の事である。（スタックスロットのアドレスを関数に渡したり、それを他の変数に格納したりなども可能である。）
前節の例だと、phiノードの使用を避けるためにallocaを使用するよう書き換えることができる。

@G = weak global i32 0   ; type of @G is i32*
@H = weak global i32 0   ; type of @H is i32*

define i32 @test(i1 %Condition) {
entry:
  %X = alloca i32           ; type of %X is i32*.
  br i1 %Condition, label %cond_true, label %cond_false

cond_true:
  %X.0 = load i32* @G
  store i32 %X.0, i32* %X   ; Update X
  br label %cond_next

cond_false:
  %X.1 = load i32* @H
  store i32 %X.1, i32* %X   ; Update X
  br label %cond_next

cond_next:
  %X.2 = load i32* %X       ; Read X
  ret i32 %X.2
}

これによって、我々は任意の変更可能な変数を、phiノードの生成をまったく必要とせずに、処理する方法を発見した事になる。

1. 変更可能な変数は、スタックへの割り当て（allocation）となる。
2. 変数からの読み込みは、スタックからのロード（load）となる。
3. 変数の書き換えは、スタックへのストア（store）となる。
4. 変数のアドレスを得るには、スタックのアドレスを直接用いる。

このやり方は、我々の目下の問題を解決する一方、あらたな問題を起こす。
かなりシンプルで基本的な処理を行うにも、スタックへのアクセス量の増大を招きそうだという、性能上重大な問題である。
幸い、LLVMのオプティマイザは高度にチューンされた最適化パスを持つ。
その名も”mem2reg”で、それはこの場合のようなallocaをSSAレジスタに変換し、適切にphiノードを挿入する。
以上の例を、このパスに通すと、以下のような結果が得られる。

$ llvm-as < example.ll | opt -mem2reg | llvm-disこれ
@G = weak global i32 0
@H = weak global i32 0

define i32 @test(i1 %Condition) {
entry:
  br i1 %Condition, label %cond_true, label %cond_false

cond_true:
  %X.0 = load i32* @G
  br label %cond_next

cond_false:
  %X.1 = load i32* @H
  br label %cond_next

cond_next:
  %X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
  ret i32 %X.01
}

mem2regパスには、SSA形式の構築と、標準的な”繰り返し支配辺境（iterated dominance frontier）”アルゴリズムが実装されて、また（よくある）悪いケースをスピードアップするための多くの最適化処理も持つ。
mem2reg最適化パスは、変更可能な変数を扱うための答えであり、それを使う事を我々は強く推奨する。
mem2regは、ある種の状況においてのみ動作する点に注意。

1. mem2regは、alloca駆動である。
   allocaを探し、それが処理可能なら処理する。
   グローバル変数や、ヒープの割り当て（heap allocation）に対しては動作しない。
2. mem2regは、関数のentryブロックの中でのみalloca命令を探す。
   entryブロックではallocaが一度だけ実行されることが保証されるので、解析処理をシンプルに出来る。
3. mem2regは、直接ロードもしくはストアされるallocaのみを処理する。
   もし関数に、スタックオブジェクトのアドレスが渡された場合、もしくは、何か特殊なポインタ演算に関係する場合、そのallocaを処理しない。
4. mem2regは、（ポインタやスカラやベクタのような）第一級オブジェクト（first class value）で、配列の割り当てサイズが1（もしくは.llファイル上でサイズが省略されている場合）のallocaのみを対象とする。
   mem2regには、構造体や配列をレジスタに変換する能力はない。
   ちなみに、”scalarrepl”パスはより強力で、構造体や共用体や配列を多くの場合で処理可能である。

多くの命令型言語において、以上の項目を全て満たすのは簡単である。
これについて、この後万華鏡を使って解説する。
あなたがするであろう最後の質問は、次のようなものだろう。
“フロントエンドの実装において、このよく解らないやり方について心配すべきでしょうか。mem2reg最適化パスを使用せずに、単にSSAを直接構築すればいいんじゃないでしょうか？”
一口に言えば、非常に十分な理由が無い限り、SSA形式の構築のためにこの技法を使用するよう強く推奨する。
訳注: この技法 = とりあえず変数をallocaで宣言するようにし、phiノードを生成しないでおいて、後はmem2regに任せる方法

この技法を使う事は、

• よく使われ、よくテストされている。
  llvm-gccとclangの両方は、この技法をローカル変数に使っている。
  つまり、LLVMの一番のクライアントが、多数の変数を処理するためにこの技法を使っている。
  なので、バグはすぐに発見され、すぐに修正されることが見込める。
• 極めて速い。
  mem2regは、完全に一般的な場合と同様に、よくある場合において高速化するための、多くの特殊な最適化法を持つ。
  例えばmem2regは、ひとつのブロックでのみ使用されている変数や、1回のみ代入される変数などに対する近道（fast paths）や、不必要なphiノードを削減するための良い経験則を持っている。
• デバッグ情報の生成に必要。
  LLVMでは、デバッグ情報を付け加えるために、変数のアドレスを露出させる必要がある。
  この技法は、このような形式のデバッグ情報にとても自然に適合する。

なにはともあれ、この技法によって、フロントエンドの立ち上げと実行がより簡単になり、実装がとてもシンプルになる。
それでは、変更可能な変数によって万華鏡を拡張してみよう！