アルパカ三銃士

〜アルパカに酔いしれる獣たちへ捧げる〜

フィボナッチ数列の LLVM IR を読む

LLVM IR を読んでみた。
以下のような記事を見つけたため、今後のためにメモを残すことにした。

takoeight0821.hatenablog.jp

今回読むのは次のフィボナッチのコードである。

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 #0attribute 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, %9icmp 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 がちょっと分かりづらかったかなー