技術

7.2. なぜ難しいのか?

LLVMによるプログラミング言語の実装チュートリアル日本語訳
第7章 万華鏡: 言語の拡張: 変更可能な変数(Mutable Variables)
第2節 なぜ難しいのか?

変更可能な変数がなぜ、SSAの構築を複雑にしてしまうのか、それについて理解するために、次の非常に簡単なCの例について考えてみる。

int G, H;
int test(_Bool Condition) {
  int X;
  if (Condition)
    X = G;
  else
    X = H;
  return X;
}

この場合では、変数Xの値はプログラムの実行パスに依存する。
return命令の前に、Xは2つの異なった値をとりうるので、その2つの値をマージするためにphiノードが挿入される。
この場合について我々が望むLLVM IRは以下のような感じとなる。

@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:
  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.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
  ret i32 %X.2
}

この例では、グローバル変数GとHからのロードは、LLVM IR上で明確となっていて、そしてそれらはif文のthenとelseの枝分かれ(cond_trueとcond_false)の中に存在している。
入ってくる値をマージするために、cond_nextの中のX.2のphiノードは、制御フローがどこから来たのかに基づいて、正しい値を選択する。
制御フローが、cond_falseブロックから来たならば、X.2はX.1の値を得る。
逆に、制御フローが、cond_trueブロックから来たならば、X.2はX.0の値を得る。
この章の目的は、SSA形式の詳細について説明することではない。
詳細のためには、ネットの情報を参照。
訳注: 「SSA形式」や「静的単一代入」でググるべし。

この節の疑問点は、”変更可能な変数に割り当てた後の部分に、誰がphiノードを配置するのか?”ということである。
ここでは、LLVMはSSA形式でIRを要求するということに着目している。(SSAを用いない方法は無い。)
しかしながら、SSAの構築は、ちょっとしたアルゴリズムとデータ構造では行えないので、すべてのフロントエンドがこのロジックをそれぞれで実装しなければならないのは不便で不経済である。
訳注: ここの例では、前々節でやったような、if式(上の例ではCなので式じゃなくて文だが)の結果のためのphiノードではなく、if式におけるXという変数に対する副作用のためのphiノードについてである。
前者の場合なら、前々節でやった通り、if式のコード生成時にphiノードを生成することができるが、後者の場合、phiノードの生成をどのASTノードが担当すべきかが明確に出来ない。
なので”(適切な場所に)誰がphiノードを配置するのか?”という疑問が出てくる。
その答えは次節ですぐ分かるが、簡単にネタばらしをすると、LLVMに自動的にphiノードを配置させることが出来る。
あと、もしphiノードの生成を独自にやるとしたら、例えば変数を読み取ってる部分で、それ以前に分岐が無いかさかのぼって調べ、分岐してたら適切な箇所にphiノードを追加したりする必要がある。
これ以外の方法も当然あると思うが、どうやっても面倒な処理になりそうである。
ここが多分本文の”ちょっとしたアルゴリズムとデータ構造では行えない”の部分に対応する。

コメントを残す

メールアドレスが公開されることはありません。



※画像をクリックして別の画像を表示