フィボナッチ数列の LLVM IR を読む
LLVM IR を読んでみた。
以下のような記事を見つけたため、今後のためにメモを残すことにした。
今回読むのは次のフィボナッチのコードである。
int fib(int n) { int i, t, a = 0, b = 1; for (i = 0; i < n; i++) { t = a + b; a = b; b = t; } return b; }
clang のバージョンは
❯❯❯ clang -v clang version 5.0.1 (tags/RELEASE_501/final) Target: x86_64-apple-darwin15.6.0 Thread model: posix InstalledDir: /usr/local/opt/llvm/bin
LLVM IR を読む
LLVM IR の出力は次のように行った。
clang -emit-llvm -O0 fib.c -S
これで fib.ll
が作成されているはず。
結果として次のようなコードが生成された。
; ModuleID = 'fib.c' source_filename = "fib.c" target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-apple-macosx10.11.0" ; Function Attrs: noinline nounwind optnone ssp uwtable define i32 @fib(i32) #0 { %2 = alloca i32, align 4 %3 = alloca i32, align 4 %4 = alloca i32, align 4 %5 = alloca i32, align 4 %6 = alloca i32, align 4 store i32 %0, i32* %2, align 4 store i32 0, i32* %5, align 4 store i32 1, i32* %6, align 4 store i32 0, i32* %3, align 4 br label %7 ; <label>:7: ; preds = %17, %1 %8 = load i32, i32* %3, align 4 %9 = load i32, i32* %2, align 4 %10 = icmp slt i32 %8, %9 br i1 %10, label %11, label %20 ; <label>:11: ; preds = %7 %12 = load i32, i32* %5, align 4 %13 = load i32, i32* %6, align 4 %14 = add nsw i32 %12, %13 store i32 %14, i32* %4, align 4 %15 = load i32, i32* %6, align 4 store i32 %15, i32* %5, align 4 %16 = load i32, i32* %4, align 4 store i32 %16, i32* %6, align 4 br label %17 ; <label>:17: ; preds = %11 %18 = load i32, i32* %3, align 4 %19 = add nsw i32 %18, 1 store i32 %19, i32* %3, align 4 br label %7 ; <label>:20: ; preds = %7 %21 = load i32, i32* %6, align 4 ret i32 %21 } attributes #0 = { noinline nounwind optnone ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="core2" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } !llvm.module.flags = !{!0, !1} !llvm.ident = !{!2} !0 = !{i32 1, !"wchar_size", i32 4} !1 = !{i32 7, !"PIC Level", i32 2} !2 = !{!"clang version 5.0.1 (tags/RELEASE_501/final)"}
attributes #0
は attribute groups と呼ばれ function attributes を書きまとめることができる- attribute group の
target-features
がコンパイルするアーキテクチャのターゲットらしい define i32 @fib(i32) #0
は 32 bit の整数を返し、同様の引数を受け取ることを宣言している。#0
は attribute group を参照している%2 = alloca i32, align 4
ではalloca
でレジスタを確保しaligin 4
でアドレスが 4 の倍数であることを保証するstore i32 %0, i32* %2, align 4
ではレジスタに値をセットする。%0
は関数 fib の引数であると考える。これを%2
へセットしているbr label %7
は; <label>:7:
へジャンプするbr i1 %10, label %11, label %20
だと%10
が真偽値に相当する。真だと; <label>:11:
へ、偽だと; <label>:20:
へジャンプするicmp slt i32 %8, %9
は icmp instruction を読んだ方が圧倒的に理解できる; preds = %7
はどのラベルからジャンプしてくるかの意味だと思うadd nsw i32 %12, %13
に関しても add instruction を読むべき- nuw and nsw stand for “No Unsigned Wrap” and “No Signed Wrap”, respectively.
ret i32 %21
はご存知 return
眺めていて、なんとなくこういう感じなんだろうなというのもあるため理解がしやすい。
次は最適化を行った IR を読む。
; ModuleID = 'fib.c' source_filename = "fib.c" target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-apple-macosx10.11.0" ; Function Attrs: minsize norecurse nounwind optsize readnone ssp uwtable define i32 @fib(i32) local_unnamed_addr #0 { br label %2 ; <label>:2: ; preds = %7, %1 %3 = phi i32 [ 0, %1 ], [ %9, %7 ] %4 = phi i32 [ 0, %1 ], [ %5, %7 ] %5 = phi i32 [ 1, %1 ], [ %8, %7 ] %6 = icmp slt i32 %3, %0 br i1 %6, label %7, label %10 ; <label>:7: ; preds = %2 %8 = add nsw i32 %5, %4 %9 = add nuw nsw i32 %3, 1 br label %2 ; <label>:10: ; preds = %2 ret i32 %5 } attributes #0 = { minsize norecurse nounwind optsize readnone ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="core2" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } !llvm.module.flags = !{!0, !1} !llvm.ident = !{!2} !0 = !{i32 1, !"wchar_size", i32 4} !1 = !{i32 7, !"PIC Level", i32 2} !2 = !{!"clang version 5.0.1 (tags/RELEASE_501/final)"}
おお!!いと短し
phi i32 [ 0, %1 ], [ %9, %7 ]
は phi instruction を読むと詳しく理解ができるが、読んでも分からなかったため llvm : 'phi' Instruction を読んだ- 遷移先によって値が変わるらしい
んー phi がちょっと分かりづらかったかなー