LLVMについて調べた 2 - 人生は勉強ブログ

先日の記事で、llvmをうまくインストールできないという結論に至ったが、よく見てみたらコマンドがおかしかった。

% llvm which clang
/usr/local/opt/llvm/bin/clang
% llvm clang -v
clang version 6.0.0 (https://llvm.org/git/clang.git 68e041468bfb4a364acdfa32abb0c7e38cfb938e) (https://llvm.org/git/llvm.git 06ded7390f85773afa7424d80d61a4a82ac19689)
Target: x86_64-apple-darwin16.7.0
Thread model: posix
InstalledDir: /usr/local/opt/llvm/bin

llvmというコマンドは存在しなかった。

クロスコンパイル

クロス開発とは、ホストのCPUアーキテクチャと、ターゲットのCPUアーキテクチャが異なる開発環境のことである。

最近では、iosのアプリ開発などで一般的な開発スタイルとなっている。

今までのクロスコンパイルでは、それぞれのターゲットに合わせたクロスコンパイラを個別に用意していたが、Clangでは、多様なターゲットCPUをサポートしているため、それだけで十分である。

では、実際に、llvm/clangを動かしていく。

まず、llvmが対応している、ターゲットCPUアーキテクチャを確認してみる。

% llvm llvm-config --targets-built
AArch64 AMDGPU ARM BPF Hexagon Lanai Mips MSP430 NVPTX PowerPC Sparc SystemZ X86 XCore

いっぱいあった。

これらのうちから、選択して、コンパイルすることができるが、それぞれに対応した、リンカやライブラリが別途必要になる。

LLVM IR

LLVM IR とは、コンパイラの中で閉じて利用される、中間言語のこと。

オンメモリであつかえる

JIT コンパイラが利用できるようにするため。

SSAで処理される

SSAとは、static single assignmentの略であり、日本語にすると、静的単一代入。

言い換えると、「一つの変数に対して、一つの値しか代入されない」

この方式にする理由の一つに、実行コードの最適化がしやすい、という点がまずあげられる。

人間が理解しやすいアセンブリ言語

LLVM IRは、C言語のような高級言語と、x86やARMなどのアセンブリ言語の中間に位置する存在である。

こんな感じ。

pos_x = pos_x + offset;

add r2, r0, r1

$pos_x1 = add i32 %pos_x, %offset

一番下が、LLVM IRである。アセンブリのように、レジスタを直接呼ぶのではなく、%pos_x1のような識別子で呼ぶことができる。

LLVM IRのアセンブリを読む

ではここで、Cで書かれたフィボナッチ数列のソースが、どのように出力されるのかをみていく。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int fib(int n){
    int val;

    if( n < 3 ){
        val = 1;
    }else{
        val = fib(n - 1) + fib(n - 2);
    }
    return val;
}


void usage(){printf("usage: fib <正の整数>\n");}

int main( int argc, char *argv[] ){
    if( argc < 2 ){
        usage();
        return 0;
    }

    int n = atoi(argv[1]);

    printf("%d\n", fib(n));
    return 0;
}

このソースをまずは、コンパイルしてみる。

% clang -o fib_clang fib.c
% src ./fib_clang 9
34


; ターゲット情報
; 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.12.0"


; 初期データ
@.str.1 = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
@str = private unnamed_addr constant [26 x i8] c"usage: fib <\E6\AD\A3\E3\81\AE\E6\95\B4\E6\95\B0>\00"

; fib関数
; Function Attrs: nounwind readnone ssp uwtable
define i32 @fib(i32) local_unnamed_addr #0 {
  %2 = icmp slt i32 %0, 3
  br i1 %2, label %12, label %3

; <label>:3:                                      ; preds = %1
  br label %4

; <label>:4:                                      ; preds = %3, %4
  %5 = phi i32 [ %9, %4 ], [ %0, %3 ]
  %6 = phi i32 [ %10, %4 ], [ 1, %3 ]
  %7 = add nsw i32 %5, -1
  %8 = tail call i32 @fib(i32 %7)
  %9 = add nsw i32 %5, -2
  %10 = add nsw i32 %8, %6
  %11 = icmp slt i32 %5, 5
  br i1 %11, label %12, label %4

; <label>:12:                                     ; preds = %4, %1
  %13 = phi i32 [ 1, %1 ], [ %10, %4 ]
  ret i32 %13
}


; usage関数
; Function Attrs: nounwind ssp uwtable
define void @usage() local_unnamed_addr #1 {
  %1 = tail call i32 @puts(i8* getelementptr inbounds ([26 x i8], [26 x i8]* @str, i64 0, i64 0))
  ret void
}

; printf関数(外部関数の参照)
; Function Attrs: nounwind
declare i32 @printf(i8* nocapture readonly, ...) local_unnamed_addr #2


; main関数
; Function Attrs: nounwind ssp uwtable
define i32 @main(i32, i8** nocapture readonly) local_unnamed_addr #1 {
  %3 = icmp slt i32 %0, 2
  br i1 %3, label %4, label %5

; <label>:4:                                      ; preds = %2
  tail call void @usage()
  br label %11

; <label>:5:                                      ; preds = %2
  %6 = getelementptr inbounds i8*, i8** %1, i64 1
  %7 = load i8*, i8** %6, align 8, !tbaa !3
  %8 = tail call i32 @atoi(i8* %7)
  %9 = tail call i32 @fib(i32 %8)
  %10 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.1, i64 0, i64 0), i32 %9)
  br label %11

; <label>:11:                                     ; preds = %5, %4
  ret i32 0
}


; atoi関数(インライン関数)
; Function Attrs: nounwind readonly
declare i32 @atoi(i8* nocapture) local_unnamed_addr #3

; Function Attrs: nounwind
declare i32 @puts(i8* nocapture readonly) local_unnamed_addr #4


; 属性
attributes #0 = { nounwind 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"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { nounwind 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"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #2 = { nounwind "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-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #3 = { nounwind readonly "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-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #4 = { nounwind }



; メタデータ
!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 6.0.0 (https://llvm.org/git/clang.git 68e041468bfb4a364acdfa32abb0c7e38cfb938e) (https://llvm.org/git/llvm.git 06ded7390f85773afa7424d80d61a4a82ac19689)"}
!3 = !{!4, !4, i64 0}
!4 = !{!"any pointer", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}

ターゲット情報

; 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.12.0"

target datalayoutでは、コード内で用いられている値の種類、サイズ、ポインタなどを定義している。

どのような値のサイズを用いて演算を行うかを、実行環境に基づいて決めている。

ここでは、ハイフン区切りで、一つの数値の型を定義している。

e-m:o-i64:64-f80:128-n8:16:32:64-S128

となっているため、分けていくと、

e
m:o
i64:64
f80:128
n8:16:32:64
S128

このようになる。

eはリトルエンディアン

m:oは、わからなかった。

i:64:64は、整数型で、

f80:128は浮動小数点、

n8:16:32:64は、ハードウェア実装されているビット幅

S128は、スタックのアライメントを128ビットにする。

target tripleでは、実行対象の定義を指定している。

target triple = "x86_64-apple-macosx10.12.0"となっているため、なんとなくわかる。

ABI

これはapplication binary interfaceの略で、オブジェクトファイルやライブラリファイルが相互に問題なくリンクできるように

それらの生成に必要な規約を定めたものである。

一般的に定められている規約としては、

C言語の変数の型のバイト数
CPUのレジスタごとに役割
構造体、共用体のデータ構造
関数への値を渡す方法

初期データ

名前通り、初期として利用されるデータ

上のソースでいうと、usage関数の中で使用されている文字列である。

; 初期データ
@.str.1 = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
@str = private unnamed_addr constant [26 x i8] c"usage: fib <\E6\AD\A3\E3\81\AE\E6\95\B4\E6\95\B0>\00"

これらのうち、@で始まるものは、関数名やグローバル変数のように、いろいろなところから参照される変数につけられ、

%から始まるものは、レジスタ名、ローカル変数など、局所的に参照される値につけられる。

printf("%d\n", fib(n));// の%d\n
"usage: fib <正の整数>\n"

ソースでいうと、この二つか。

初期データの定義は、以下のフォーマットで書かれる。

<label> = <linkage> <attribute> constant [<size> x <type>] c"<strings>"

外部関数の定義

; Function Attrs: nounwind
declare i32 @printf(i8* nocapture readonly, ...) local_unnamed_addr #2

左から順に、返り値、識別子、引数の順に定義されている。

fib関数の定義

; Function Attrs: nounwind readnone ssp uwtable
define i32 @fib(i32) local_unnamed_addr #0 {
  %2 = icmp slt i32 %0, 3
  br i1 %2, label %12, label %3

; <label>:3:                                      ; preds = %1
  br label %4

; <label>:4:                                      ; preds = %3, %4
  %5 = phi i32 [ %9, %4 ], [ %0, %3 ]
  %6 = phi i32 [ %10, %4 ], [ 1, %3 ]
  %7 = add nsw i32 %5, -1
  %8 = tail call i32 @fib(i32 %7)
  %9 = add nsw i32 %5, -2
  %10 = add nsw i32 %8, %6
  %11 = icmp slt i32 %5, 5
  br i1 %11, label %12, label %4

; <label>:12:                                     ; preds = %4, %1
  %13 = phi i32 [ 1, %1 ], [ %10, %4 ]
  ret i32 %13
}

int fib(int n){
    int val;

    if( n < 3 ){
        val = 1;
    }else{
        val = fib(n - 1) + fib(n - 2);
    }
    // printf("%d\n", val);
    return val;
}

brは、改行ではなく、分岐(branch)のbr

これの.bcバージョンから図式化する。

% src clang -emit-llvm -O1 -o fib.bc -c fib.c
% src opt -dot-cfg fib.bc
# WARNING: You're attempting to print out a bitcode file.
# This is inadvisable as it may cause display problems. If
# you REALLY want to taste LLVM bitcode first-hand, you
# can force output with the `-f' option.

# Writing 'cfg.fib.dot'...
# Writing 'cfg.usage.dot'...
# Writing 'cfg.main.dot'...
% src dot -Tpng cfg.fib.dot -o cfg.fib.dot.png

f:id:dooooooooinggggg:20171101151218p:plain

属性

attributes #0 = { nounwind 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"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { nounwind 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"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #2 = { nounwind "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-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #3 = { nounwind readonly "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-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #4 = { nounwind }

関数に設定できる属性のこと。

ネイティブコードを生成する際の情報を付加するためにある。

バックエンドでは、上で書かれた命令を元に、この属性を加味しながら、ネイティブコードを生成する。

試しに、一個見てみる

attributes #0 = {
    nounwind 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"="penryn"
    "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+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 6.0.0 (https://llvm.org/git/clang.git 68e041468bfb4a364acdfa32abb0c7e38cfb938e) (https://llvm.org/git/llvm.git 06ded7390f85773afa7424d80d61a4a82ac19689)"}
!3 = !{!4, !4, i64 0}
!4 = !{!"any pointer", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}

これは、LLVM IRでは表記しきれない情報を伝達するために使われる。

今後

今後は、もっと手を動かしたい。