LLVMでFizzBuzz

9438 ワード
FizzBuzz LLVM FizzBuzz テキストリンク

LLVMって？

LLVMでFizzBuzzってなんだろうと思った方、いらっしゃるかと思います。LLVMは見聞きされたことはあるでしょうか？ これはコンパイラ基盤というもので、C、C++、Objective-C等のコンパイラを実装する際の土台になるものです。一般にはClangとして知られているC言語系コンパイラがLLVMを利用しています。最近では、IDE（統合開発環境）で静的解析やリファクタリング支援機能を提供するためにもLLVMが利用されるケースが増えてきているようです。

とりあえず試してみましょう。筆者はUbuntu 17.04で行いました。

初めてのLLVM

LLVMとClangをインストールします。

$ sudo apt-get install llvm-3.9-dev clang-3.9

サンプルプログラムです。

test.c
#include <stdio.h>

int main()
{
    printf("Hello, world\n");
    return 0;
}

お馴染みのやつですね。これをclangコンパイラにかけてみます。

$ clang-3.9 -c -S -emit-llvm test.c -o test.ll

次のようなファイルが生成されます。

test.ll
; ModuleID = 'test.c'
source_filename = "test.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

@.str = private unnamed_addr constant [14 x i8] c"Hello, world\0A\00", align 1

; Function Attrs: nounwind uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @.str, i32 0, i32 0))
  ret i32 0
}

declare i32 @printf(i8*, ...) #1

attributes #0 = { nounwind uwtable "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" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { "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" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.ident = !{!0}

!0 = !{!"clang version 3.9.1-5ubuntu1.1 (tags/RELEASE_391/rc2)"}

なんとなくアセンブリ言語に似ています。でもx86のアセンブリではありません。これが LLVM IR というもので、最終的に機械語になる前の中間コードです。-Oオプションがあれば、最適化が行われて、より洗練された LLVM IR が生成されます。

これを実行可能なプログラムにしてみましょう。

$ clang-3.9 test.ll

a.outが作成されるはずです。では実行してみましょう。

$ ./a.out
Hello, world

LLVMでFizzBuzzやるよ

LLVMのAPIを呼び出して、FizzBuzzを実行する LLVM IR を生成してみましょう。実装はC++です。ソースはちょっと大きいのでGitHubに置きました。

$ git clone https://github.com/soramimi/llfizzbuzz.git
$ cd llfizzbuzz
$ make

メイクが完了するとllfizzbuzzというプログラムができあがります。これをそのまま実行すると LLVM IR が表示されます。実行可能プログラムにするには次のようにします。

$ ./llfizzbuzz >a.ll
$ clang-3.9 a.ll

そして、お待ちかねのFizzBuzzです。

$ ./a.out

解説

main.cpp見ても何が何だかわからないと思います。これを作った私でも一週間もすると忘れてしまうレベルです。ともかく、「なんとか::Create()」みたいなのを大量に呼び出して、LLVM IRの細々した命令を一個一個生成しています。

大雑把に説明すると、

  • コンテキスト（LLVMContext）を作る
  • モジュール（Module）を作る
  • モジュールの中に関数（Function）を作る
  • 関数の中にブロック（BasicBlock）を作る
  • ブロックの中に命令を追加する

ブロックは、分岐先のラベルの数だけ、大量に作る必要があります。命令は、それこそアセンブリ言語みたいに、四則演算やビット演算をはじめ、単純な命令の組み合わせです。本物のコンパイラ（のフロントエンド）は、ソースファイルを読み込んで字句解析してから、上記のような細かい命令を大量に生成します。

もしご興味があれば、私が以前書いた「Orelang(俺言語) の LLVM IR コンパイラを作ってみた」という記事もご覧ください。

コンパイラの専門家ではない私がこれ以上書くとボロが出ますのでこれくらいにしておきます。