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

万華鏡のシンボルテーブルは、NamedValuesマップによってコード生成時に使われている。
現状ではこのマップは、名前が付いた倍精度の変数を保持するLLVM Value*を追跡し続ける。
変数の変更をサポートするために、変数のメモリの位置をNamedValuesで保持するよう、少し変更する必要がある。
この変更はリファクタリングであることに注意。
コードの構造は変わるが、コンパイラの振る舞いは変わらない。
これ以降加えていく変更は、全て万華鏡のコード生成器のなかで分離されている。

この時点では、万華鏡は2種類の変数のみをサポートしている。
関数の引数と、forループのための帰納変数である。
一貫性のため、ユーザ定義変数に加えて、それらの変数の変更も可能にしていく。
つまり、それら両方とも、メモリの位置が必要であるということである。

万華鏡の改良を始めるにあたって、NamedValuesマップを、Value*じゃなくてAllocaInst*を指すよう変更する。
こうしておけば、あとはC++のコンパイラがコードの変更すべき箇所を教えてくれる。
訳注: コンパイルエラーの内容を見れば変更すべき箇所が分かる。

static std::map<std::string, AllocaInst*> NamedValues;

そしたら、alloca命令を生成するようにする必要がある。
確実にallocaが関数のentryブロックに生成されるようにするためのヘルパ関数を使う。

/// CreateEntryBlockAlloca - alloca命令を関数のentryブロックに生成する。
/// これは変更可能な変数などのために使われる。
static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
                                          const std::string &VarName) {
  IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
                 TheFunction->getEntryBlock().begin());
  return TmpB.CreateAlloca(Type::getDoubleTy(getGlobalContext()), 0,
                           VarName.c_str());
}

この少々変わったコードは、entryブロックの最初の命令（.begin()）を指すIRBuilderオブジェクトを生成する。
そしたら、指定された名前でallocaを生成し、それを返す。
万華鏡における値は全てdoubleなので、変数の型を渡す必要はない。

これを踏まえ、我々が最初に加えたい機能上の変更点は、変数の参照である。
我々の計画では、変数はスタック上に保持されているので、変数の参照についてのコード生成として、実際にスタックスロットからロードする命令の生成が必要となる。

Value *VariableExprAST::Codegen() {
  // 関数の中でこの変数を探す。
  Value *V = NamedValues[Name];
  if (V == 0) return ErrorV("Unknown variable name");

  // 値をロードする。
  return Builder.CreateLoad(V, Name.c_str());
}

見ての通り、実に簡単なコードである。
そしたら次は、allocaを使うよう、変数を定義する部分を変更する必要がある。
それについてはまず、ForExprAST::Codegenから始める。（”全コード”の節で、省略されてないコードを見るべし。）

Function *TheFunction = Builder.GetInsertBlock()->getParent();

// 変数のためのallocaをentryブロックに生成する。
AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);

// スコープ中の変数無しで、まずStartのコードを生成する。
Value *StartVal = Start->Codegen();
if (StartVal == 0) return 0;

// allocaの中に値を格納する。
Builder.CreateStore(StartVal, Alloca);
...

// 終了条件を計算する。
Value *EndCond = End->Codegen();
if (EndCond == 0) return EndCond;

// allocaを再読み込みし、インクリメントし、セットする。
// これは、ループの本文が変数を変化させる場合を処理する。
Value *CurVar = Builder.CreateLoad(Alloca);
Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");
Builder.CreateStore(NextVar, Alloca);
...

このコードは、変更可能な変数を可能にする以前のコードと同一といってもいいくらい似ている。
大きな違いは、もうphiノードを構築する必要がなく、そして変数へのアクセスに必要に応じてload/storeを使うという点だけである。

引数の変更をサポートするために、それらに関してもallocaを生成する必要がある。
そのためのコードもまた、実にシンプルである。

/// CreateArgumentAllocas - 各引数のためのallocaを生成し、そしてそれをシンボルテーブルに登録する。
/// これによって、引数への参照が可能となる。
void PrototypeAST::CreateArgumentAllocas(Function *F) {
  Function::arg_iterator AI = F->arg_begin();
  for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {
    // この変数のためのallocaを生成する。
    AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);

    // allocaの中に初期値を保存する。
    Builder.CreateStore(AI, Alloca);

    // 引数をシンボルテーブルに追加する。
    NamedValues[Args[Idx]] = Alloca;
  }
}

各引数について、allocaを作成し、関数へ入力された値をallocaの中に保存し、引数のメモリの位置としてallocaを登録する。
FunctionAST::Codegenが関数のentryブロックを準備した直後、このメソッドはFunctionAST::Codegenによって起動される。

あと残ったのは、mem2regパスの追加である。
これによって、効率的なコードの生成機能を今一度得ることが出来る。
訳注: phiノードを使わず、alloca/load/storeで変数を操作するようにすると効率が悪くなる。”今一度得る”というのは、mem2regパスでその効率を取り戻すという意味。

// オプティマイザのパイプラインを準備する。
// ターゲットがデータ構造をどうやって配置するかについての情報をまず登録する。
OurFPM.add(new DataLayout(*TheExecutionEngine->getDataLayout()));
// allocaをレジスタ化する。
OurFPM.add(createPromoteMemoryToRegisterPass());
// 簡単なピープホール最適化（覗き穴最適化）とビット操作最適化を行わせる。
OurFPM.add(createInstructionCombiningPass());
// 式の再結合。
OurFPM.add(createReassociatePass());

mem2reg最適化の実行前と後で、コードがどのようになるかを見るのは面白い。
以下は、再帰的なfib関数のビフォー・アフターの例である。
まず最適化前。

define double @fib(double %x) {
entry:
  %x1 = alloca double
  store double %x, double* %x1
  %x2 = load double* %x1
  %cmptmp = fcmp ult double %x2, 3.000000e+00
  %booltmp = uitofp i1 %cmptmp to double
  %ifcond = fcmp one double %booltmp, 0.000000e+00
  br i1 %ifcond, label %then, label %else

then:       ; preds = %entry
  br label %ifcont

else:       ; preds = %entry
  %x3 = load double* %x1
  %subtmp = fsub double %x3, 1.000000e+00
  %calltmp = call double @fib(double %subtmp)
  %x4 = load double* %x1
  %subtmp5 = fsub double %x4, 2.000000e+00
  %calltmp6 = call double @fib(double %subtmp5)
  %addtmp = fadd double %calltmp, %calltmp6
  br label %ifcont

ifcont:     ; preds = %else, %then
  %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
  ret double %iftmp
}

ここでは変数はひとつだけである（引数x）が、我々が非常に単純なコード生成戦略を使っていることが分かる。
entryブロックで、allocaは生成され、そこに初期値が保存される。
変数への参照では、毎回スタックから再読み込みされている。
if/then/else式を修正してないので、依然としてphiノードが挿入されている点にも注意が必要である。
ここでもallocaを使うようにする事もできるが、phiノードを生成するほうが簡単なのでそのままにしてある。

これがmem2regパスによる最適化後である。

define double @fib(double %x) {
entry:
  %cmptmp = fcmp ult double %x, 3.000000e+00
  %booltmp = uitofp i1 %cmptmp to double
  %ifcond = fcmp one double %booltmp, 0.000000e+00
  br i1 %ifcond, label %then, label %else

then:
  br label %ifcont

else:
  %subtmp = fsub double %x, 1.000000e+00
  %calltmp = call double @fib(double %subtmp)
  %subtmp5 = fsub double %x, 2.000000e+00
  %calltmp6 = call double @fib(double %subtmp5)
  %addtmp = fadd double %calltmp, %calltmp6
  br label %ifcont

ifcont:     ; preds = %else, %then
  %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
  ret double %iftmp
}

これは変数の再定義を含まないので、mem2regにとって取るに足らないなケースである。
非効率な命令の挿入をしても大丈夫だ、という事を示すためにこのコードを示している。

残りの最適化を実行すると以下のようになる。

define double @fib(double %x) {
entry:
  %cmptmp = fcmp ult double %x, 3.000000e+00
  %booltmp = uitofp i1 %cmptmp to double
  %ifcond = fcmp ueq double %booltmp, 0.000000e+00
  br i1 %ifcond, label %else, label %ifcont

else:
  %subtmp = fsub double %x, 1.000000e+00
  %calltmp = call double @fib(double %subtmp)
  %subtmp5 = fsub double %x, 2.000000e+00
  %calltmp6 = call double @fib(double %subtmp5)
  %addtmp = fadd double %calltmp, %calltmp6
  ret double %addtmp

ifcont:
  ret double 1.000000e+00
}

simplifycfgパスによって、ret命令がelseブロックの最後にも追加されている。
これによって、いくらかの枝分かれやphiノードが削減可能となる。

以上で、シンボルテーブルの全ての参照は、スタック変数を使うようになった。
次は、代入演算子（assignment operator）を追加しよう。