LLVMをちょっと調べてみた

最近LLVMについて調べてみたのでまとめてみる。自分はコンパイラの専門家でも何でもないので間違った内容があるかもしれない。

GCCとコンパイラの仕組み

LLVMの前にまずはコンパイラ一般の話。コンパイラはまずソースコードを解析して内部表現にする。これはたいていツリー構造となる。このツリー構造のデータに対して文法チェックを行ったり最適化処理を行ったりした後に、オブジェクトファイルを生成する。

コンパイラの内部表現だが、実際には複数の種類の内部表現を使っていることが多いらしく、GCCもそのようになっている（[1]の図3）。これによるとまずはその言語固有のツリーにするようだ（C trees, C++ treesなど）。これをGENERICという形式にする。GENERICは名前のとおり言語に依存しない一般的な形式で、どの言語の場合も一度GENERICにする。

GENERICはその後さらにGIMPLEという形式に変換される。GIMPLEはGENERICより記述が制限され、最適化処理に適した形式になっている。GIMPLEにはさらにHigh GIMPLEとLow GIMPLEがあるようだ（[2]の3ページ）。

GIMPLEもまだ最終形態ではなく、さらにRTL (Register Transfer Language) という形式に変換される。RTLはおおよそ「無限のレジスタを持つ抽象機械に対するアセンブラ」ということらしい。そして、RTLからようやくオブジェクトファイルが生成される（[2]の13ページ）。

とこんな感じになっているGCCだが、その内部構造はかなり複雑になっているらしく、ちょっと手を加えようと思っても部外者がそう簡単にいじれるものではなくなってしまっているらしい。そこでもっと良い設計のものを作ろうと考えたのがLLVMの発端（[3]）。

用語について

と、ここでコンパイラ関連用語について説明する（詳細は[4]）。

AST: 抽象構文木（Abstract Syntax Tree）。ソースコードの内容をツリー構造に表したもの。コンパイラはたいていまずASTを作る。GCCのC treesなどが多分これにあたる。
フロントエンド、ミドルエンド、バックエンド: コンパイラのうち、ソースコードを解析して内部表現にする部分をフロントエンドと呼ぶ。また、最適化処理やオブジェクトコード生成用の解析を行う部分をミドルエンド、オブジェクトコードを生成する部分をバックエンドと呼ぶ。GCCで言えば、C treesを作ってGENERICを経由し、GIMPLEを作るあたりまでがフロントエンド。GIMPLEを使って最適化を行い、RTLを作るあたりがミドルエンド。RTLからオブジェクトコードを生成するあたりがバックエンドとなる。

LLVMの概要

ここからようやくLLVMの話。LLVMの概要については[5]を読むのだ良いだろう。概要の一部を引用させてもらう。

LLVM は、JavaとJVMの関係のように、まず仮想機械をターゲットとした中間言語を生成し、その仮想機械向けコードを特定のマシンの機械語に変換する。この時言語やプラットフォームとは独立した最適化を行う。この方法によってLLVM は言語からもアーキテクチャからも独立しており、それぞれに特化した、プログラミング言語固有のモジュールと、マシン向けコード生成部を用意することにより様々な言語アーキテクチャーに対応する。

自分の理解では、LLVMはコンパイラの仕事のうち、ミドルエンドとバックエンドに相当する部分を実装したものだ。LLVM-IRという内部表現とそれを操作・最適化などの各種API、それにオブジェクトコードを出力する機能がある。

一方フロントエンドの機能はないため、LLVMだけではプログラミング言語処理系にはならない（アセンブラっぽいものを手書きすることはできるが）。公式ページのチュートリアルではKaleidoscopeという簡易な独自言語を定義してそのフロントエンド（つまりソースコードを解析してASTを作るもの）を作り、それを基にLLVM-IRを生成するようになっている。LLVMによる最適化機能も使っており、これを読んで試してみればなんとなく概要を掴めると思う。

LLVM-IR

LLVM-IR（IRはInternal Representationのこと）には3つの表現形式がある。

in-memory compiler IR（以下メモリ内IRと呼ぶことにする）
ディスク上のバイナリ表現
人間が読めるアセンブラの形式

いずれも等価の内容であり、相互に変換可能である。また、メモリ内IRを作るためのAPIも用意されている。

最適化機能

プログラミング言語処理系を作る人間にとってLLVMを使うことの利点は、多くの最適化の処理を任せることができる点だ。LLVMのチュートリアルから最適化の機能を見てみる。

定数畳み込み

まずはKaleidoscopeで以下のようなコードを書いたとする。

def test(x) 1+2+x;

defは関数の定義であり、testという関数を定義している。その中身は1+2+xだ。Cっぽく書けば以下のようになる。なお、Kaleidoscopeの数値はすべてdoulbeになっている。

double test(double x) {
  return 1.0 + 2.0 + x;
}

Kaleidoscope処理系（コンパイラあるいはインタプリタ）は次のアセンブラ表現に相当するメモリ内IRを作ることになる。

%addtmp = fadd double 2.000000e+00, 1.000000e+00
%addtmp1 = fadd double %addtmp, %x
ret double %addtmp1

LLVM-IRの詳細を知らなくてもだいたい内容は理解できるだろう。2.0と1.0を足した結果をaddtmpに入れ、さらにaddtmpとxを足した結果をaddtmp1に入れ、最後にaddtmp1をreturnしている。

しかし、実際に生成されるIRは以下のようになる。

%addtmp = fadd double 3.000000e+00, %x
ret double %addtmp

つまり、1.0 + 2.0が自動的に計算され、実行時の演算回数を減らしている。このような最適化を定数畳み込み（Constant folding）という。LLVMはこれを自動で行ってくれる。

共通部分式除去

今度は以下のコードはどうだろう。

def test(x) (1+2+x)*(x+(1+2));

どう最適化するかは見ただけで想像がつくと思うが、掛け算の左辺と右辺が同じ内容になっているため、"1+2+x"の計算を1回にすることができる。
実際、LLVMではこのコードを以下のようにすることが可能だ。

%addtmp = fadd double %x, 3.000000e+00
%multmp = fmul double %addtmp, %addtmp
ret double %multmp

このような処理はCSE（Common Subexpression Elimination: 共通部分式除去）と呼ぶ。これもLLVMが持つ機能であり、言語処理系開発者は単に「CSEをやれ」と命令するだけでCSEを実現できる。

他にもさまざまな機能が実装されており、自由に組み合わせることができる（定数畳み込みは自動で行われるようだ）。これにより、言語処理系開発者は言語設計に専念することができる。

オブジェクトコード出力機能

LLVMは多くのプラットフォーム用のコードを出力することができる（X86, X86-64, PowerPC, PowerPC-64, ARM, Thumb, SPARC, Alpha, CellSPU, MIPS, MSP430, SystemZ, and XCore）。また、X86, X86-64, PowerPC and PowerPC-64ではJITコード生成ができる。

また、DWARF形式のデバッグ情報を入れることもできるので、生成されたコードに対してgdbなどでデバッグすることも可能だ。さらに、gprofのようなプロファイリング機能もあるらしい。

LLVMの利用例

llvm-gcc

さてそんな素晴らしいLLVMだが、先に書いたとおりあくまでコンパイラ基盤であり、フロントエンドの部分がない。そこで、gccのフロントエンドを流用したのがllvm-gccだ。これにより、C言語のコンパイルができるようになる。ただし、llvm-gccは後述のclangができるまでの繋ぎであり、現在の最新版であるLLVM 2.9が、llvm-gccをサポートする最後のバージョンになるようだ。

clang

clang（発音は片仮名なら「クラン」あるいは「クラング」）はLLVMのサブプロジェクトの一つで、独自のC/C++/Obj-Cフロントエンドである。clangの特徴は以下がある。

コンパイル時だけでなく、リンク時の最適化（-O4）も可能
コンパイル時間も早い
エラーメッセージも分かりやすい

ベンチマークなどについては[6]の20ページ以降を見るのが良いだろう。コンパイル時間は-O4でもgccの-O2より速く、実行時間も-O4ならgccの-O2より20%ほど速い。

C++はまだ実用レベルではないようだが、CとObj-Cはかなりのところまで来ており、本格的な採用を検討しているプロジェクトもある。コンパイラとしての性能もさることながら、ライセンスも魅力の1つ。LLVMはBSDライクなライセンスであり比較的緩い。一方GCCはライセンスがGPLv3になり、特許やDRMに関する記述がある。このあたりが一部の企業やプロジェクトにとっては採用したくない原因になるようだ。

実際、FreeBSDはGCCがGPLv3になったものは使っておらず、GCC-4.2.1のままになっている。FreeBSD 10あたりでClangの全面採用することを検討している模様。

また、AppleもGCCを使ってきたが、Xcode 4からはllvm-gccやclangも使えるようになったようで、Mac OS X本体も徐々にClangに置き換わることが噂されている。実際AppleはLLVM, Clangの開発に非常に活発で、多数の開発者を送り込んでいる。

今のところclangはコンパイル機能はあるがリンクの機能はなく、外部のリンカを使っている。今度リリースされるLLVM 3.0では独自のリンカも入り、これでCコンパイラとしての機能が揃うことになる。

PNaCl

PNaClの説明をする前にまずNativeClientを説明しなければならない。Googleが開発したもので、NativeClientはブラウザ上でネイティブコードを実行するものだ。

ブラウザ上でプログラムを動かす場合は普通JavaScriptを使う。しかし、JavaScriptはネイティブコードに比べ実行速度の面で不利だ（最近はかなり速くなってはいるが）。そこで、JavaScriptの代わりにネイティブのオブジェクトコードをダウンロードして実行するのがNativeClientである。要はActiveXと似たようなものなわけだが、セキュリティに関する考え方が異なる。そのあたりの話はこのページが詳しい。

NativeClientはネイティブコードを使うため、CPUが異なると実行できない。例えばx86用に作られたコードを、ARM上のブラウザで実行することはできない。そこで、ネイティブコードの代わりにLLVM-IRをダウンロードし、それをネイティブコードに変換して実行するのがPNaClだ。PNaClを使うことでネイティブコードに近い処理効率をポータブルに実現できる。

Emscripten

EmscriptenはLLVM-IRからJavaScriptコードを生成するものだ。例えばclangやllvm-gccでコンパイルできるC言語プログラムなら途中でLLVM-IRになるので、これをEmscriptenに渡せばJavaScriptコードになる。つまり、LLVMを使って書かれた言語なら何でもJavaScriptにすることができる。

その昔人気を博したDOOMというゲームがあるが（Cで書かれているらしい）、これをEmscriptenでJavaScript化し、ブラウザで実行するデモがYoutubeにある（http://www.youtube.com/watch?v=WDUPZRQf7oc）。

LLVM + OpenGL

AppleのOS（Mac OSやiOS）での3Dグラフィックスでの使われ方。3DグラフィックスのAPIであるOpenGLにはGLSLというシェーディング言語があり、これによってより質の高いグラフィックスを作ることができる。GLSLで書かれたコードはすべてGPUで行わるのが理想的だが、実際にはGPUによってはサポートされていない機能があったりするため、一部はCPUでやることになる。

最初はGLSL用の独自JIT コンパイラを作っていたそうだ。ただし、最適化などはあまり優れていなかったようだ。また、このJIT コンパイラもOpenGLのすべての機能をサポートしていたわけではなく、一部はインタプリタで処理されていた。これが非常に遅く、JITに比べて100倍以上遅かったらしい。

そこで、今度はGLSLからLLVM-IRを作るようにし、以降の最適化とJITをLLVMに任せるようにしたらとてもうまくいったそうだ。iPhoneのような小さな機器でも高品位なグラフィックスを出せる裏にはこういう工夫があったのだ。

GLSLからLLVMへの変換作業がどのようになっているかについては[6]の6ページ以降を参照。