2016年4月7日

Go言語で利用するLLVM入門

はじめに

LLVMは、コンパイラを作成するための基盤です。2000年にChris Lattnerによって作成され、2003年にリリースされました。それ以来、LLVMリンカlldやLLVMデバッガlldbなど幅広いツール群を持つ包括的なプロジェクトに発展してきました。

LLVMの秀でた特徴は、一般にLLVM IRと呼ばれる、その中間表現です。LLVMの考え方は、まずこのIRにコンパイルし、次にそのIRを、JITコンパイルする、インタープリタで実行する、または実行しているマシンのネイティブアセンブリにコンパイルするといういうものです。このIRの主なターゲットは、コンパイラです。実際LLVMを使用するコンパイラは、世の中に数多くあります。C言語とC++用はそれぞれclangとclang++、D言語用のldc2、Rust、Swiftなどです。Emscriptenのようなプロジェクトさえあります。これは、LLVM BC (LLVM bitcode)をブラウザで実行されるJavaScriptにコンパイルします。

一般的にコンパイラの設計では、レジスタ割り当て、いろいろなアーキテクチャのためのコード生成、また十分に最適化された効率の良いコード生成に気を配る必要があります。LLVMの良さは、今述べたことを全て処理してくれるところです。LLVMは、非常に多くの最適化コレクションを備えており、さまざまなアーキテクチャをターゲットにすることができます。GNUコンパイラのコレクションが長年のデファクトスタンダードでしたが、LLVMの実装が大幅にそれを上回る結果が示されており¹、多くの場合、より優れたエラーメッセージを出力します。

LLVM IR

では、LLVM IRを素早く見てみましょう。標準的なCのプログラムを-emit-llvmと-Sフラグを付けてclangでコンパイルすると、.llファイルが生成されます。このファイルの拡張子は、LLVM IRだということを表しています。

LLVM IRに変換するCのコードは次のとおりです。

int main() {
  int a = 32;
  int b = 16;
  return a + b;
}

何も最適化しないように指定してclangを実行しました。clang test.c -S -emit-llvm -O0。結果は次のとおりです。

define i32 @main() #0 {
  %1 = alloca i32, align 4
  %a = alloca i32, align 4
  %b = alloca i32, align 4
  store i32 0, i32* %1
  store i32 32, i32* %a, align 4
  store i32 16, i32* %b, align 4
  %2 = load i32, i32* %a, align 4
  %3 = load i32, i32* %b, align 4
  %4 = add nsw i32 %2, %3
  ret i32 %4
}

単純化のために余分なコードの多くを省略しました。IRを見てみると、冗長性が増して読みやすいアセンブリ言語のように見えます。気付いたかもしれませんが、IRは型が厳密に定義されています。型の注釈が命令、値、関数など全てに付いています。

それでは、このIRの中で何が行われているのか、1行ずつ理解していきましょう。まず最初に、中括弧、型、名前、及び引数用の括弧を持つC言語風の関数によく似た構文の関数があります。

関数内に、値と命令が並んでいます。このIRの中には、5つの命令が含まれています。alloca、store、load、add、そしてretです。

では、これがどのように動作するのかを理解するためにIRを部分ごとに詳しく見てみましょう。ここでは、アライメントとnswフラグの説明は省きます。これらの詳細については、LLVMのドキュメントをご覧ください。ここでは、基本的な意味だけを説明します。

ローカル識別子

命令に取り掛かる前に、ローカル識別子とは何かを知る必要があります。ローカル識別子は変数のようなもので、記号%で表します。名前のとおり、定義されている関数内に限られていることを示しています。従って、宣言された関数の外からは参照も変更もできません。

`alloca`命令

この命令は、スタックフレームにメモリを割り当てます。関数が戻る時に、このメモリは解放されます。この命令は値を返すので、例えば%aなどにそれを代入します。戻り値は割り当てられたメモリへのポインタです。例えば次のとおりです。

%a = alloca i32, align 4

この命令は、32ビット符号付き整数のための領域をスタックに割り当てます。ポインタはローカル識別子aに格納されます。

`store`命令

store命令は、指定されたポインタが指し示す場所の値を与えられた値に書き換えます。簡単に説明できる例を以下に示します。

store i32 32, i32* %a, align 4

この例では、LLVMにi32型の値32をi32*型（i32型へのポインタ）のローカル識別子aに格納するよう指示しています。この命令は、void型を返します。つまり、何も返さないので、ローカル識別子に代入できません。

`load`命令

最後は、load命令です。この命令は、指定されたメモリアドレスの値を返します。

%2 = load i32, i32* %a, align 4

上記の例では、メモリアドレスa（i32型へのポインタ）からi32型の値をロードします。この値は、ローカル識別子2に格納されます。参照先の値を取得することはできないので、値をロードする必要があります。

命令が何を意味しているか分かったので、うまくいけば、上記のIRの半分以上は読んで理解することができるはずです。残りの命令については、比較的分かりやすいはずです。add命令は与えられた値の加算を行い、結果を返します。ret命令は、関数の戻り値を指定します。

LLVM API

LLVMは、このIRを構築するためのAPIを提供しています。元のAPIは、C++で書かれていますが、Lua、OCaml、C、Goなど様々な言語バインディングがあります。

この記事では、Goバインディングを使用していきます。IRのビルドを始める前に、詳細を理解しておかなければならない事が幾つかあります。

モジュール

モジュールは、定義と宣言の集まりです。これは、コンテナであり、必ず作成する必要があります。通常モジュールはファイルごと作成されますので、最初の例では、C言語のファイルがモジュールです。

モジュールは次のように作成します。モジュール名として文字列を渡します。これがメインモジュールとなるので、”main”と名付けましょう。

module := llvm.NewModule("main")

型

LLVMは、バイト、整数、浮動小数点などのプリミティブ型から、構造体、配列、関数型のような複雑な型まで多様な型を提供しています。

組み込み型は、TypeWidthType()の形式になっています。例えば、Int16Typeは16ビット幅の整数です。

foo := llvm.Int16Type()
bar := llvm.Int32Type()

任意のビット幅を指定することもできます。

fupa := llvm.IntType(32)

配列は次のように指定できます。

ages := llvm.ArrayType(llvm.Int32Type(), 16)

これは、要素数が16の32ビット整数型配列です。

値

LLVMの値は命令から戻されますが、それは定数、関数、グローバル変数等々である可能性もあります。

以下に値666を持つi32型定数整数を作りました。末尾のブーリアンパラメータは符号拡張するかどうかを示します。

foo := llvm.ConstInt(llvm.Int32Type(), 666, false)

浮動小数点定数も作れます。

bar := llvm.ConstFloat(llvm.FloatType(), 32.5)

そしてこれらの値を変数に割り当てたり、関数に渡したりすることができます。ここで2つの定数値を足す加算命令を作りましょう。

a := llvm.ConstInt(llvm.Int32Type(), 12)
b := llvm.ConstInt(llvm.Int32Type(), 24)
c := llvm.ConstAdd(a, b)

基本ブロック

これはおそらく予想するものと少々異なります。アセンブリでは、関数にラベルを使ってフローを制御します。関数に明示的な構文を備えているものの、LLVMは非常にそれに似ています。しかし、どのようにプログラムのフローの制御をすればよいのでしょうか。基本ブロックを使うのです。IRは次のようになります。

define i32 @main() {
entry:
    ...
0:
    ...
1:
    ...
}

main関数があり、その関数内に3つの基本ブロックがあります。entryブロック、それから0と1のブロックです。必要な数だけ基本ブロックを持つことができます。用途は、例えば、ループ、if文などです
。

LLVMのためのGoバインディングで、基本ブロックを次のように定義しましょう。

llvm.AddBasicBlock(context, "entry")

contextにブロックを追加したい関数を指定します。これは関数型ではありません。その点については後で述べます。

IRビルダ

IRビルダはIRを作成するツールです。値、命令などを全てまとめて与える必要があります。ビルダで重要なのは、ビルドする場所を再配置するのに利用できるということと、別の場所に命令を追加できるということです。

モジュールに命令を追加する際にこのビルダを使ってみましょう。ビルダをセットアップし、関数とentryブロックを作って定数を格納するための単純な命令を追加したのが下記です。

builder := llvm.CreateBuilder()
// create a function "main"
// create a block "entry"

foo := builder.CreateAlloca(llvm.Int32Type(), "foo")
builder.CreateStore(foo, llvm.ConstInt(llvm.Int32Type(), 12, false))

これは次のようにIRを生成します。


define i32 @main() {
entry:
    %foo = alloca i32
    store i32 12, i32* %foo
}

関数

関数はLLVMにおける1つの型です。関数型を定義するには幾つかの指定が必要です。戻り値の型、パラメータの型、そして関数が可変長引数かどうか、つまり引数の個数が可変かどうかを指定します。

ここまで見てきたmain関数は次のとおりです。

main := llvm.FunctionType(llvm.Int32Type(), []llvm.Type{}, false)
llvm.AddFunction(mod, "main", main)

最初のパラメータは戻り値の型で、32 ビットの整数です。ここでの関数はパラメータを取りませんので、ただ空の配列を渡します。関数が可変長引数ではないので、falseを最後の引数に渡します。簡単ですね。

AddFunctionは指定されたモジュールに、指定された名前で関数を追加します。この関数については次のようにして後で参照できます（キーと値のマップで管理されています）。

mainFunc := mod.NamedFunction("main")

これはモジュール内の関数を検索します。

ここまでで学んできたことをまとめてみましょう。

// setup our builder and module
builder := llvm.CreateBuilder()
mod := llvm.NewModule("my_module")

// create our function prologue
main := llvm.FunctionType(llvm.Int32Type(), []llvm.Type{}, false)
llvm.AddFunction(mod, "main", main)
block := llvm.AddBasicBlock(mod.NamedFunction("main"), "entry")

// note that we've set a function and need to tell
// the builder where to insert things to
builder.SetInsertPoint(block, block.FirstInstruction())

// int a = 32
a := builder.CreateAlloca(llvm.Int32Type(), "a")
builder.CreateStore(llvm.ConstInt(llvm.Int32Type(), 32, false), a)

// int b = 16
b := builder.CreateAlloca(llvm.Int32Type(), "b")
builder.CreateStore(llvm.ConstInt(llvm.Int32Type(), 16, false), b)

うまく行っていますが、allocaがポインタを返すため、まとめて追加することができません。ポインタを「参照しデータを取得する」ためには、幾つかのloadを生成しなければなりません。

aVal := builder.CreateLoad(a, "a_val")
bVal := builder.CreateLoad(b, "b_val")

次は計算です。a + bを行うには、単純にadd命令を作ります。

result := builder.CreateAdd(aVal, bVal, "ab_value")

関数がi32を返しますので、次の内容を返す必要があります。

builder.CreateRet(result)

これで完成です。しかし、どうすれば実行できるのでしょうか。幾つか方法があります。

LLVMのJIT/実行エンジンを使う。
IR -> BitCode -> アセンブリ -> オブジェクト – > 実行ファイルへと変換する。

1つ目のオプションは実行ファイルに落とし込む方法としてより簡潔なので、こちらを選びます。2つ目は読者の演習用として残しておきましょう。実行ファイルを作成し、実行後にステータスコードを確認したら、結果は48になるはずです。Bashでこれを行うには、$?環境変数を表示させてください。

$ ./a.out
$ echo $?
$ 48

標準出力に表示したい場合は、printf関数やputchまたは同等のものを定義しなければなりません。このチュートリアルを読めばその作業も十分に可能でしょう。行き詰まった場合は、（手前味噌ですが）私が作っているLLVMベースにGoで記述した言語、Arkをチェックしてください。Arkコードジェネレータはこちら。

そしてLLVMのバインディングに関するドキュメントはこちらです。知っておくべき事項はほぼ掲載されています。

LLVM仕様書も、同様に全てを詳細に至るまで網羅しており、命令、組み込み関数、属性なども含まれています。

コードを走らせよう

寄り道はこのくらいにして、早速実行してみます。この章の概要は次のとおりです。

モジュールのverify
実行エンジンの初期化
関数呼び出しをセットアップし実行

まず、モジュールが正しいことを確認します。

if ok := llvm.VerifyModule(mod, llvm.ReturnStatusAction); ok != nil {
    fmt.Println(ok.Error())
    // ideally you would dump and exit, but hey ho
}
mod.Dump()

このコードはモジュールが無効の場合、エラーを表示します。モジュールが無効になる原因は様々ですが、IRの欠陥による可能性が大きいです。mod.Dump()呼び出しはモジュールIRを標準出力にダンプします。

では、実行エンジンを初期化しましょう。

engine, err := llvm.NewExecutionEngine(mod)
if err != nil {
    fmt.Println(err.Error())
    // exit...
}

最後に、関数を実行し、結果を標準出力に表示します。関数は引数を取らないので、空のGenericValues配列を渡します。

funcResult := engine.RunFunction(mod.NamedFunction("main"), []llvm.GenericValue{})
fmt.Printf("%d\n", funcResult.Int(false))

ビルド

LLVMがインストール済みであることが前提です。幸運にもこの作業は非常にシンプルです。

$ pacman -S llvm

Windowsを使っているなら、これは少々難しいもしれません。その他のLinuxでは、パッケージマネジャでllvmを検索してください。Macなら、Homebrewが使えます。

それからGoバインディングもインストールします。releaseの変数は362ですが、例えばllvm 3.7.0を使っているならこれは370になります。LLVMリポジトリをGOPATHにクローンし、バインディングをビルド、インストールする方法は下記のとおりです。

$ release=RELEASE_362
$ svn co https://llvm.org/svn/llvm-project/llvm/tags/$release/final $GOPATH/src/llvm.org/llvm
$ cd $GOPATH/src/llvm.org/llvm/bindings/go
$ ./build.sh
$ go install llvm.org/llvm/bindings/go/llvm

次に、Goファイルに”llvm.org/llvm/bindings/go/llvm”を必ずインポートしてください。完了すると、Goファイルを実行し、結果を表示させることができます。

できました。新しい発見はあったでしょうか。これがプログラミング言語の記述にどのように使えるかが分かっていただけたなら幸いです。次のステップとしてKaleidoscopeチュートリアルをチェックするか、自身のプログラムをいろいろとテスト、実装してみることをおすすめします。

最後まで読んでいただきありがとうございます :)

フルコード

package main

import (
    "fmt"
    "llvm.org/llvm/bindings/go/llvm"
)

func main() {
    // setup our builder and module
    builder := llvm.NewBuilder()
    mod := llvm.NewModule("my_module")

    // create our function prologue
    main := llvm.FunctionType(llvm.Int32Type(), []llvm.Type{}, false)
    llvm.AddFunction(mod, "main", main)
    block := llvm.AddBasicBlock(mod.NamedFunction("main"), "entry")
    builder.SetInsertPoint(block, block.FirstInstruction())

    // int a = 32
    a := builder.CreateAlloca(llvm.Int32Type(), "a")
    builder.CreateStore(llvm.ConstInt(llvm.Int32Type(), 32, false), a)

    // int b = 16
    b := builder.CreateAlloca(llvm.Int32Type(), "b")
    builder.CreateStore(llvm.ConstInt(llvm.Int32Type(), 16, false), b)

    // return a + b
    bVal := builder.CreateLoad(b, "b_val")
    aVal := builder.CreateLoad(a, "a_val")
    result := builder.CreateAdd(aVal, bVal, "ab_val")
    builder.CreateRet(result)

    // verify it's all good
    if ok := llvm.VerifyModule(mod, llvm.ReturnStatusAction); ok != nil {
        fmt.Println(ok.Error())
    }
    mod.Dump()

    // create our exe engine
    engine, err := llvm.NewExecutionEngine(mod)
    if err != nil {
        fmt.Println(err.Error())
    }

    // run the function!
    funcResult := engine.RunFunction(mod.NamedFunction("main"), []llvm.GenericValue{})
    fmt.Printf("%d\n", funcResult.Int(false))
}

http://www.phoronix.com/scan.php?page=article&item=clang-37-gcc52&num=2 ↩

画像処理入門講座 : OpenCVとPythonで始める画像処理

Go言語で利用するLLVM入門

はじめに

LLVM IR

ローカル識別子

alloca命令

store命令

load命令

LLVM API

モジュール

型

値

基本ブロック

IRビルダ

関数

コードを走らせよう

ビルド

フルコード

Go言語の並行性を映像化する

イベントループなしでのハイパフォーマンス – C10K問題へのGoの回答

Goで毎分100万リクエストを処理する

Goで使える10のテクニック

Goはオブジェクト指向言語だろうか？

Previous Post

`alloca`命令

`store`命令

`load`命令