LLVMのphiとは

はじめに

LLVMのphiについて、ざっくりと説明します。
個人的な理解を書いているだけなのでご了承ください。

予備知識：ブロックとは

phiを理解する前に、ブロック(Basic Block)について知っておく必要があります。

ざっくり言うと、ブロックとは「ラベルから、次のラベルの手前まで」のことです。
アセンブリで説明すると、

label1:
  ; 何か処理
  ; ここまでが、'label1'という名前のブロック
label2:

の場合、label1: から label2: の直前までが一つのブロックになります。
label2: 以降はまた別のブロックになります。

phiとは

phiとは、「どのブロックから飛んできたかで値を選択する」命令です。
例を挙げると、

phi.ll

define i32 @some_function(i32) {
entry:
  %1 = icmp eq i32 %0, 0
  br i1 %1, label %phi_label, label %label1

label1:
  %2 = icmp eq i32 %0, 1
  br i1 %2, label %phi_label, label %label2

label2:
  br label %phi_label

phi_label:
  %3 = phi i32 [5, %entry], [8, %label1], [3, %label2] ; entryから来たら5、label1からなら8,それ以外なら３を返す。
  ret i32 %3
}

上記の関数some_functionは、
・引数が０なら５
・引数が１なら８
・それ以外なら３
を返す関数です。

%3 = phi i32 [5, %entry], [8, %label1], [3, %label2] の行の
. [5, %entry] が"entryブロックから来たら５"
. [8, %label1] が"label1ブロックから来たら8"
. [3, %label2] が"label2ブロックから来たら３"
をphiの値とする、ことを表しています。

飛んでくるブロックが増えたなら、[5, %entry], [8, %label1], [3, %label2] の部分はブロックの数だけ増やせます。
[5, %entry], [8, %label1], [3, %label2], [1, %some_label], [2, %another_label] などのようにいくらでも（？）増やせます。

なぜphiが必要なのか？

静的単一代入（Static Single Assignment form）において、

C言語っぽい例

int x;
if(何か条件){
  x = 1;
}else{
  x = 2;
}

のように条件によって変数の値を変えたい場合に必要だとか何とか。詳しくは知らない。

おまけ：全コード

一応、some_functionを試すmain関数つきのコードを載せておきます。

phi.ll

define i32 @some_function(i32) {
entry:
  %1 = icmp eq i32 %0, 0
  br i1 %1, label %phi_label, label %label1

label1:
  %2 = icmp eq i32 %0, 1
  br i1 %2, label %phi_label, label %label2

label2:
  br label %phi_label

phi_label:
  %3 = phi i32 [5, %entry], [8, %label1], [3, %label2]
  ret i32 %3
}

@0 = private unnamed_addr constant [4 x i8] c"%d\0A\00"

declare i32 @printf(i8*, ...)

define void @main() {
entry:
  %0 = call i32 @some_function(i32 0)
  %1 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @0, i32 0, i32 0), i32 %0)

  %2 = call i32 @some_function(i32 1)
  %3 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @0, i32 0, i32 0), i32 %2)

  %4 = call i32 @some_function(i32 2)
  %5 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @0, i32 0, i32 0), i32 %4)
  ret void
}

実行方法は、

bash

$ llvm-as phi.ll
$ lli phi.bc