読者です 読者をやめる 読者になる 読者になる

llvm : 'phi' Instruction

llvm

LLVM Language Reference Manual — LLVM 3.4 documentation』を引き続き読む。
phi命令の動作が読んだだけでは分からなかったので、実際に動かして試してみた。


コード:

;;; ファイル名: phi.ll
;;; コンパイル: llvm-as phi.ll -o phi.bc
;;; コマンドの引数に与える数字に応じて、異なるメッセージを出力する

; 出力用メッセージ
@MSG0 = internal constant [5 x i8] c"zero\00"
@MSG1 = internal constant [4 x i8] c"one\00"
@MSG2 = internal constant [4 x i8] c"two\00"
@MSGX = internal constant [8 x i8] c"default\00"

; atoi 及び puts
declare i32  @atoi(i8*)
declare void @puts(i8*)

;; phiテスト用の関数
define void @phi_test(i32 %n) {
entry:
 ; メッセージのポインタを取得
 %msg0 = getelementptr [5 x i8]* @MSG0, i64 0, i64 0
 %msg1 = getelementptr [4 x i8]* @MSG1, i64 0, i64 0
 %msg2 = getelementptr [4 x i8]* @MSG2, i64 0, i64 0
 %msgx = getelementptr [8 x i8]* @MSGX, i64 0, i64 0

 ; 引数の数値で分岐  ※デフォルトではprintラベルに遷移
 switch i32 %n, label %print [ i32 0, label %label0
                               i32 1, label %label1
                               i32 2, label %label2 ] 

 ; label0~2は、すべてprintへ遷移する
label0:
 br label %print
label1:
 br label %print
label2:
 br label %print

print:
 ; 表示するメッセージを取得する
 ; 遷移元の(=br/switch命令がある)ブロック(ラベル)によって、使用する文字列ポインタを振り分ける
 ;
 ; [間違っているかもしれないメモ]
 ; phi命令の形式は、
 ;   phi <値の型> [<値>, <遷移元ブロック>] ...
 ; ※ 遷移元にはないブロックが指定された場合はエラー
 ; ※ ここに遷移するブロックの内で、指定もれがある場合もエラー
 ; ※ 遷移元ブロックは、phi命令の前方(上方)にある必要はない
 ; ※ phi命令は、ブロックの先頭以外では使えない
 %msg = phi i8* [%msgx,%entry], [%msg0,%label0], [%msg1,%label1], [%msg2,%label2]

 ; 表示
 call void @puts(i8* %msg)
 ret void
}

;; メイン関数
define i32 @main(i32 %argc, i8** %argv) {
 ; atoi 
 %argv1 = getelementptr i8** %argv, i32 1
 %tmp   = load i8** %argv1
 %n     = call i32 @atoi(i8* %tmp)

 ; 
 call void @phi_test(i32 %n)
 ret i32 0
}

実行:

$ lli phi.bc 0
zero 
$ lli phi.bc 2
two
$ lli phi.bc 30
default 

つまり、遷移元のブロックに応じて使用する値を振り分けられるのが、phi命令。


これを応用して*1、前に作成したハノイの塔を末尾再帰っぽく修正してみる。

@.MSG = internal constant [10 x i8] c"%c -> %c\0A\00"

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

;; ハノイの塔 : 末尾再帰(?)版
define void @hanoi(i8 %start, i8 %tmp, i8 %dist, i32 %level) {
entry:
  %cond = icmp eq i32 %level, 0
  br i1 %cond, label %end, label %recur
recur:
  %level1 = phi i32 [%level, %entry], [%level2, %recur]
  %start1 = phi i8  [%start, %entry], [%tmp1, %recur]
  %tmp1   = phi i8  [%tmp,   %entry], [%start1, %recur]

  %level2 = sub i32 %level1, 1
  %msg = getelementptr [10 x i8]* @.MSG, i64 0, i64 0

  call void @hanoi(i8 %start1, i8 %dist, i8 %tmp1, i32 %level2)
  call i32 @printf(i8* %msg, i8 %start1, i8 %dist)
  
  ; 再帰的にhanoi関数を呼び出さないで、直接%recurラベルに遷移してしまう(終了ケース以外の場合)
  %cond2 = icmp eq i32 %level2, 0
  br i1 %cond2, label %end, label %recur
  ret void
end:
  ret void
}

;; メイン関数 : コマンドの引数で塔の高さを指定可能なように変更
define i32 @main(i32 %argc, i8** %argv) {
  %argv1 = getelementptr i8** %argv, i32 1
  %num   = load i8** %argv1
  %level = call i32 @atoi(i8* %num)
  call void @hanoi(i8 65, i8 66, i8 67, i32 %level)
  ret i32 0
}

tailとかfastccとかの宣言(?)を使えば、llvmが末尾再帰関数呼出をやってくれるようなのだが、いろいろ条件があるようでややこしいので、それはまた今度試す。

*1:llvmSSA(Static Single Assignment)というモデルを採用しているらしく、(同一ブロック内にいる間?)変数の値を変更(再代入)することができない。そのため、「変数の値を更新した後に、先頭部分に遷移する」というような方法でループを実現することができない(ように思う。できるかもしれない)。※この注釈の信頼性はかなり低い