LLVMを使ってみる

LLVM-1.x系の文書です。コマンドラインツールの使い方は同じですが.llの構文が2.2では通らないです。

インストール

ubuntuでLLVMのパッケージを入れます。

apt-get install llvm llvm-cfe llvm-libs

LLVMについて

LLVMは仮想マシンですが、そのバイトコード仕様に忠実なアセンブリ言語もLLVM言語と呼んでいるようです。

• http://llvm.org/docs/LangRef.html

この言語で直接コードを書いて、llvm-asコマンドでバイトコードに落とすこともできます。が、llvm-cfeパッケージにgccフロントエンドがあるので、C言語で書いてバイトコードに落とすこともできます。

例

hello.c

extern int puts(char*);

int main() {
  puts("Hello World");
  return 0;
}

このコードをバイトコード化してみます:

$ /usr/lib/llvm/llvm-gcc4/bin/llvm-gcc hello.c -o hello
$ ls -a
.  ..  hello  hello.bc  hello.c
$ cat hello
#!/bin/sh
lli=${LLVMINTERP-lli}
exec $lli \
    $0.bc ${1+"$@"}
$ file hello.bc
hello.bc: LLVM byte-codes, null compression
$

hello.bcがLLVMバイトコードです。helloはVM起動のlliコマンドを使って、lli hello.bcを起動するシェルスクリプトです。

hello.bcをディスアセンブルします。

$ llvm-dis hello.bc
$ ls -a
.  ..  hello  hello.bc  hello.c  hello.ll

生成されたhello.llがLLVM言語で記述されています。

; ModuleID = 'hello.bc'
target endian = little
target pointersize = 32
target triple = "i686-pc-linux-gnu"
deplibs = [ "c", "crtend" ]
%.str_1 = internal constant [12 x sbyte] c"Hello World\00"              ; <[12 x sbyte]*> [#uses=2]

implementation   ; Functions:

int %main() {
entry:
        br label %no_exit.i

no_exit.i:              ; preds = %no_exit.i, %entry
        %indvar.i = phi uint [ 0, %entry ], [ %indvar.next.i, %no_exit.i ]              ; <uint> [#uses=3]
        %Str.0.0.rec.i = cast uint %indvar.i to int             ; <int> [#uses=1]
        %Str.0.0.i = getelementptr [12 x sbyte]* %.str_1, int 0, uint %indvar.i         ; <sbyte*> [#uses=1]
        %inc.rec.i = add int %Str.0.0.rec.i, 1          ; <int> [#uses=1]
        %inc.i = getelementptr [12 x sbyte]* %.str_1, int 0, int %inc.rec.i             ; <sbyte*> [#uses=1]
        %tmp.7.i = load sbyte* %Str.0.0.i               ; <sbyte> [#uses=1]
        %tmp.8.i = cast sbyte %tmp.7.i to int           ; <int> [#uses=1]
        %tmp.5.i = tail call int %putchar( int %tmp.8.i )               ; <int> [#uses=0]
        %tmp.2.i = load sbyte* %inc.i           ; <sbyte> [#uses=1]
        %tmp.3.i = seteq sbyte %tmp.2.i, 0              ; <bool> [#uses=1]
        %indvar.next.i = add uint %indvar.i, 1          ; <uint> [#uses=1]
        br bool %tmp.3.i, label %puts.exit, label %no_exit.i

puts.exit:              ; preds = %no_exit.i
        %tmp.9.i = tail call int %putchar( int 10 )             ; <int> [#uses=0]
        ret int 0
}

declare int %putchar(int)

putsが展開されputcharを呼ぶループになっています。

LLVM言語

LLVM言語の特徴は、以下とおりです:

• (任意個の)レジスタベース
• 型付
• Static Single Assignment(SSA)形式

LLVM命令は単純で、基本的には処理を実行した結果を別の変数に入れるものになっています。スタックマシンではないので、バイトコード上でも命令のオペランドは名前で指定します。

上記の生成コードの中で特徴的なのはphi命令です。
どこからジャンプされてきた命令かによって、割り当てる値を変える命令です。

以下の部分で、ループをジャンプ命令brで実現しています。

entry:
        br label %no_exit.i

no_exit.i:
        %indvar.i = phi uint [ 0, %entry ], [ %indvar.next.i, %no_exit.i ]
        ...
        %indvar.next.i = add uint %indvar.i, 1
        br bool %tmp.3.i, label %puts.exit, label %no_exit.i

上から実行すると、entryセクションに入り、br label %no_exit.iで無条件でno_exit.iセクションに入ります。このときentryから着たので、%indvar.iは0が割り当てられます。

一方ループの最後で、%tmp3.iがfalseのとき、%no_exit.iへ飛ぶようになっています。このときは、phi命令によって%indvar.iは、ジャンプ元がno_exit.iであるため%indvar.next.iの値が割り当てられることになります。

つまり、phi命令は、分岐の合流でどの変数値を使うかを、どこから来たかによって振り分ける命令になります。

上記コードは、コメントを消しリネームしてクリーンナップすると以下のようになります。

deplibs = [ "c", "crtend" ]
%hello = internal constant [12 x sbyte] c"Hello World\00"


declare int %putchar(int)


implementation

int %main() {
init:
        br label %loop

loop:
        %i = phi uint [ 0, %init ], [ %ipp, %loop ]
        %cur = cast uint %i to int
        %curp = getelementptr [12 x sbyte]* %hello, int 0, uint %i
        %next = add int %cur, 1
        %nextp = getelementptr [12 x sbyte]* %hello, int 0, int %next
        %curch = load sbyte* %curp
        %curchi = cast sbyte %curch to int
        %ret = tail call int %putchar( int %curchi )
        %nextch = load sbyte* %nextp
        %isnull = seteq sbyte %nextch, 0
        %ipp = add uint %i, 1
        br bool %isnull, label %last, label %loop

last:
        %ret2 = tail call int %putchar( int 10 )
        ret int 0
}

LLVMでは、新規割り当て以外での代入はできないので注意です。上で%ret2を、%retにするとコンパイルエラーが出ます。またたとえば、%n = add int %n, 1のようなコードもコンパイルではじかれます。

これでもllvm-asがとおり、バイトコードが生成され、実行できます。これをさらにllvm-disでディスアセンブルすると、以下のようになりました。

; ModuleID = 'hello.bc'
deplibs = [ "c", "crtend" ]
%hello = internal constant [12 x sbyte] c"Hello World\00"               ; <[12 x sbyte]*> [#uses=2]

implementation   ; Functions:

declare int %putchar(int)

int %main() {
init:
        br label %loop

loop:           ; preds = %loop, %init
        %i = phi uint [ 0, %init ], [ %ipp, %loop ]             ; <uint> [#uses=3]
        %cur = cast uint %i to int              ; <int> [#uses=1]
        %curp = getelementptr [12 x sbyte]* %hello, int 0, uint %i              ; <sbyte*> [#uses=1]
        %next = add int %cur, 1         ; <int> [#uses=1]
        %nextp = getelementptr [12 x sbyte]* %hello, int 0, int %next           ; <sbyte*> [#uses=1]
        %curch = load sbyte* %curp              ; <sbyte> [#uses=1]
        %curchi = cast sbyte %curch to int              ; <int> [#uses=1]
        %ret = tail call int %putchar( int %curchi )            ; <int> [#uses=0]
        %nextch = load sbyte* %nextp            ; <sbyte> [#uses=1]
        %isnull = seteq sbyte %nextch, 0                ; <bool> [#uses=1]
        %ipp = add uint %i, 1           ; <uint> [#uses=1]
        br bool %isnull, label %last, label %loop

last:           ; preds = %loop
        %ret2 = tail call int %putchar( int 10 )                ; <int> [#uses=0]
        ret int 0
}

変数(レジスタ)名は保存され、変数の型と使用数、ジャンプの元などがコメントで埋め込まれます。

バイトコードからネイティブコードへ

lliはバイトコードの仮想マシンですが、llcコマンドによって、バイトコードから、プラットフォームのアセンブリに変換できます。

$ llc hello.bc
$ cat hello.s


.text
        .align  16
        .globl  main
main:
        subl $20, %esp
        movl %esi, 12(%esp)
        fnstcw 18(%esp)
        movb $2, 19(%esp)
        fldcw 18(%esp)
        movl $hello, %esi
.LBB1_1:        #loop
        movsbl (%esi), %eax
        movl %eax, (%esp)
        call putchar
        incl %esi
        movb (%esi), %al
        cmpb $0, %al
        jne .LBB1_1     #loop
.LBB1_2:        #last
        movl $10, (%esp)
        call putchar
        xorl %eax, %eax
        movl 12(%esp), %esi
        addl $20, %esp
        ret
        .size main, .-main
.data
hello:                          # hello
        .size hello, 12
        .asciz  "Hello World"

これをgasでコンパイルすることで、ネイティブのバイナリを作れます。

$ gcc hello.s
$ ./a.out
Hello World
$

おまけ

ちなみに、

extern int putchar(int);
static char str[] = "Hello World";

int main() {
  int i;
  for (i = 0; str[i] != 0; i += 1) {
    putchar(str[i]);
  }
  putchar('\n');
  return 0;
}

というコードを変換すると、

; ModuleID = 'hello2.bc'
target endian = little
target pointersize = 32
target triple = "i686-pc-linux-gnu"
deplibs = [ "c", "crtend" ]

implementation   ; Functions:

declare int %putchar(int)

int %main() {
loopexit:
        %tmp.5 = tail call int %putchar( int 72 )               ; <int> [#uses=0]
        %tmp.5.1 = tail call int %putchar( int 101 )            ; <int> [#uses=0]
        %tmp.5.2 = tail call int %putchar( int 108 )            ; <int> [#uses=0]
        %tmp.5.3 = tail call int %putchar( int 108 )            ; <int> [#uses=0]
        %tmp.5.4 = tail call int %putchar( int 111 )            ; <int> [#uses=0]
        %tmp.5.5 = tail call int %putchar( int 32 )             ; <int> [#uses=0]
        %tmp.5.6 = tail call int %putchar( int 87 )             ; <int> [#uses=0]
        %tmp.5.7 = tail call int %putchar( int 111 )            ; <int> [#uses=0]
        %tmp.5.8 = tail call int %putchar( int 114 )            ; <int> [#uses=0]
        %tmp.5.9 = tail call int %putchar( int 108 )            ; <int> [#uses=0]
        %tmp.5.10 = tail call int %putchar( int 100 )           ; <int> [#uses=0]
        %tmp.12 = tail call int %putchar( int 10 )              ; <int> [#uses=0]
        ret int 0
}

というコードに展開されました(-O0つけても)。

文字列宣言からstaticをはずすと、ループに展開されました。

; ModuleID = 'hello3.bc'
target endian = little
target pointersize = 32
target triple = "i686-pc-linux-gnu"
deplibs = [ "c", "crtend" ]
%str = internal constant [12 x sbyte] c"Hello World\00"         ; <[12 x sbyte]*> [#uses=2]

implementation   ; Functions:

declare int %putchar(int)

int %main() {
entry:
        br label %no_exit

no_exit:                ; preds = %no_exit, %entry
        %indvar = phi uint [ %indvar.next, %no_exit ], [ 0, %entry ]            ; <uint> [#uses=3]
        %i.0.0 = cast uint %indvar to int               ; <int> [#uses=1]
        %tmp.7 = getelementptr [12 x sbyte]* %str, int 0, uint %indvar          ; <sbyte*> [#uses=1]
        %tmp.8 = load sbyte* %tmp.7             ; <sbyte> [#uses=1]
        %tmp.9 = cast sbyte %tmp.8 to int               ; <int> [#uses=1]
        %tmp.5 = tail call int %putchar( int %tmp.9 )           ; <int> [#uses=0]
        %tmp.11 = add int %i.0.0, 1             ; <int> [#uses=1]
        %tmp.1 = getelementptr [12 x sbyte]* %str, int 0, int %tmp.11           ; <sbyte*> [#uses=1]
        %tmp.2 = load sbyte* %tmp.1             ; <sbyte> [#uses=1]
        %tmp.3 = seteq sbyte %tmp.2, 0          ; <bool> [#uses=1]
        %indvar.next = add uint %indvar, 1              ; <uint> [#uses=1]
        br bool %tmp.3, label %loopexit, label %no_exit

loopexit:               ; preds = %no_exit
        %tmp.12 = tail call int %putchar( int 10 )              ; <int> [#uses=0]
        ret int 0
}