(注：2017/07/06、いただいたフィードバックを元に翻訳を修正いたしました。)

この記事は、 LLVM コンパイラ基盤を使ってリサーチをする人のための入門書です。これを読めば、コンパイラに全く興味のない大学院生も、楽しみながらLLVMを使って優れた功績をあげられるようになるでしょう。

LLVMとは何か？

LLVMは非常に優れていて、ハックしやすく、C言語やC++のような”ネイティブ”言語向けの、時代の先端を行くコンパイラです。

LLVMの素晴らしさに関しては他にも様々な話を聞くのではないでしょうか（JITコンパイラとしても使えるとか、C言語系列以外の様々な言語を強化できるとか、 App Storeからの新しい配信形態 であるとか、などなど)。もちろん全部本当のことですが、今回の記事の目的としては、上述の定義が重要です。

LLVMが他のコンパイラと差別化される理由には、いくつかの大きな特徴があります。

• LLVMの中間表現（IR）は素晴らしい革新技術です。LLVMは、アセンブリ言語を扱える人であれば、実際に理解することのできるプログラム表現上で機能します。このことがすごいとは思えないかもしれないですが、実はすごいことです。他のコンパイラのIRはインメモリ構造で複雑なため、書き取ることは困難です。ですから、他のコンパイラは理解しづらく、実装するのも厄介なのです。
• LLVMは美しく書かれていて、他のコンパイラに比べ、アーキテクチャがはるかにモジュール化されています。それが実現できたのには、 私たちの仲間 がオリジナルの開発者として携わっているということも1つの理由として挙げられるでしょう。
• 私たちのような、風変わりな研究者ハッカーに 選ばれるツール であるにも関わらず、LLVMは世界最大の企業にサポートされていて、ビジネスにも通用する強力なコンパイラです。つまり、Javaの世界で HotSpot と Jikes のどちらを選ぶか悩むのと違い、素晴らしいコンパイラとハックできるコンパイラとの間で悩まなくても済むのです。

なぜ大学院生にとってLLVMが重要なのか？

LLVMは素晴らしいコンパイラですが、コンパイラの研究をしていない人にとっては興味がないですよね。

コンパイラ基盤とは、プログラムを使って何かをする時に役立つものです。私の経験からすれば、大変大きな役割を果たします。プログラムを分析し、何らかの処理の頻度を調べたり、システムとの整合性を向上させるための変更を行ったりできます。また、新しいアーキテクチャやOSを仮想的に使用するための変更を行えるので、実際に新しいチップを組み入れ、カーネルモジュールを記述する必要もありません。多くの人が支持するツールよりも、大学院生にとってはコンパイラ基盤が適切なツールであると言えます。他に正当な理由がない限り、下記のようなツールをハックするのではなく、最初からLLVMを試してみることをお勧めします。

• アーキテクチャシミュレータ
• Pin などの、Dynamic Binary Instrumentationツール
• ソースレベルでの変換（ sed のようなシンプルなものから、より完全なASTパーサやシリアライゼーションのようなツールまで)
• システムコールをインターセプトするためにカーネルをハックする
• ハイパーバイザや、それに類似したもの

あるコンパイラがあなたのタスクにぴったりだとは思えなくても、例えば、ソースからソースに変換をするよりはるかに簡単に、やりたいことの90%を達成できるでしょう。

それほどコンパイル的ではない研究プロジェクトにLLVMを用いた、効果的な事例を以下にいくつか挙げます。

• UIUC（イリノイ大学アーバナ・シャンペーン校）の Virtual Ghost では、感染したOSカーネルからプロセスを保護するためにコンパイラのpassが利用できるということを示しました。
• UW（ワシントン大学）の CoreDet では、マルチスレッドのプログラムを決定論的に使っています。
• 私たちのアプロキシメート・コンピューティングの研究では、LLVM passを使ってエラーが起こりやすいハードウェアをシミュレートするためのエラーをプログラムに注入しています。

もう一度強調します。LLVMは、ただ新しいコンパイラの最適化を実装しただけのものではないのですよ。

構成要素

ここに描いたのは、LLVMのアーキテクチャの主要な構成要素です（モダンなコンパイラのアーキテクチャでもあります）。

各要素の説明は以下の通りです。
* フロントエンドがソースコードを中間表現（またはIR）に変換します。この変換によって、これ以降のコンパイラの作業が単純化され、C++の複雑なソースコードと格闘しなくても済むようになります。果敢な大学院生のあなたは恐らく、この部分をハックしなくてもいいでしょう。修正無しで Clang が使えます。
* PassがIRをIRへと変換します。通常の状況では、passはコードを最適化します。つまり、passは入力されたIRと同じことをするIRプログラムを出力するのですが、より速くなるよう最適化するのです。ここがハックのしどころです。あなたの研究ツールはIRがコンパイルのプロセスを通過している間、それを参照し変更しながら作業できるでしょう。
* バックエンドは、実際の機械語を生成します。この箇所についてはほぼノータッチで構いません。

このアーキテクチャは、昨今のほとんどのコンパイラに当てはまりますが、LLVMには注目すべき点が1つあります。それは、全プロセスを通じてプログラムが同じIRを使うということです。他のコンパイラでは、pass毎に独自のコードが生成されることがありますが、LLVMはこれとは逆のアプローチをとっています。私たちハッカーにとっては素晴らしいことで、プロセスがフロントエンドとバックエンドの間である限り、どこでコードが実行されるか心配しなくても済むからです。

オリエンテーション

ではハックしてみましょう。

LLVMを入手する

まずLLVMをインストールします。通常、Linuxのディストリビューションから、LLVMとClangのパッケージがすぐ使える形で入手可能です。注意しなければいけない点は、ハックするために必要なヘッダを含んだバージョンを入手するということです。例えば、 Xcode に付属してくるOS Xのビルドは完全版ではありません。幸い、CMakeを使えば ソースからLLVMをビルドするのは そう難しくありません。通常はLLVMだけをビルドすればいいのです。バージョンさえ合っていれば、システムに付属してきたClangでも十分使えます（ただし、 Clangをビルドするための指示書 もありますから確認してくださいね）。

特にOS Xに関しては、 Brandon Holt による 作業を正しく行うための優れた指示書 を公開していますし、 Homebrew formula も提供されています。

RTFM（ヘルプは読もう）

ドキュメントをよく読み込みましょう。下記に挙げるリンクは繰り返し参照する価値のあるものです。

• 自動生成されるDoxygenのページ はとても重要です。LLVMをハックしている間、少しでも前に進むためには、これらのAPIドキュメントにどっぷり浸かるくらいでなくてはなりません。目的のページを見つけるのが難しいかもしれないので、Google経由で検索することをお勧めします。関数やクラス名に”LLVM”と追加すれば、Googleが 大抵の場合適切なDoxygenページを見つけてくれます （気合があるならGoogleを鍛えて、”LLVM”とタイプしなくてもLLVMの結果が最初に出てくるようにもできますよ）。バカバカしく思えるかもしれませんが、仕事をやり遂げるにはLLVMのAPIドキュメントを常に確認する必要があります。他に良い検索方法があるかもしれませんが、私は知りません。
• 言語マニュアル はLLVMのIRダンプでシンタックスに混乱した時に便利です。
• プログラマ用マニュアル はLLVM独自のデータ構造のtoolchestに関して記述しています。効果的なストリング、マップやベクタのためのSTLの代替手段などが含まれます。また、あちこちで出くわす、fast typeのイントロスペクションツール（ isa 、 cast や、 dyn_cast など)についても解説しています。
• Passに何ができるのか疑問に思ったときはいつでも LLVM passを作成する ためのチュートリアルを読んでください。あなたは研究者であり、日々コンパイラのハックをしているわけではないので、チュートリアルに書いてあることと、この記事の内容とは食い違っていると思うかもしれません（緊急性の高いものとしては、Makefileベースのビルドシステムの解説は無視して、CMakeベースの “out-of -source”instructions の項まで飛んでください）。それでもこれがpass一般に関して標準的な答えの情報源であることには変わりありません。
• GitHub mirror はLLVMソースをオンラインで閲覧する時に便利な場合があります。

Passを作成してみよう

LLVMを使って生産的な研究をするには、カスタムのpassを作成したほうがいいでしょう。この項では、臨機応変にプログラムを変換することのできるシンプルなpassをビルドし、実行するまでを解説します。

スケルトン

実用的ではないLLVM passを格納した テンプレート用のリポジトリ を作ったので、このテンプレートから着手してみてください。一から作ると、ビルドコンフィギュレーションの設定に手間がかかるかもしれません。

GitHubから llvm-pass-skeleton リポジトリ をクローンします。

$ git clone https://github.com/sampsyo/llvm-pass-skeleton.git

実際の作業は skeleton/Skeleton.cpp 上で行われるので、ファイルを開きましょう。ここで作業が行われます。

virtual bool runOnFunction(Function &F) {
  errs() << "I saw a function called " << F.getName() << "!\n";
  return false;
}

LLVMのpassが何種類かありますが、私たちが使うのは function pass と呼ばれるものです（最初に手を着けるのに適しています）。予想通り、LLVMは、コンパイルをかけているプログラムの中に見つけた全ての関数に対して上記のメソッドを呼び出します。今のところは、名称の出力しかしていません。

詳細は以下の通りです。

• この errs() というのは、LLVMが提供するC++の出力ストリームで、コンソールを出力するのに使えます。
• 関数は、 F を変更しなかった印に false を返します。後で、実際にプログラムを変換した時は、 true を返す必要があります。

ビルドしてみよう

CMake でpassをビルドします。

$ cd llvm-pass-skeleton
$ mkdir build
$ cd build
$ cmake ..  # Generate the Makefile.
$ make  # Actually build the pass.

LLVMがグローバルにインストールされていない場合は、CMakeに対して場所を指示する必要があります。 LLVM_DIR 環境変数の中にLLVMがある share/llvm/cmake/ ディレクトリならどこのパスを指定しても大丈夫です。Homebrewのパスの例は下記のようになります。

$ LLVM_DIR=/usr/local/opt/llvm/share/llvm/cmake cmake ..

Passをビルドすると共有ライブラリが生成されます。 build/skeleton/libSkeletonPass.so または、プラットフォームに応じて似たような名称で見つけられます。次は、このライブラリを読み込んで、実際のコード上でこのpassを実行してみます。

実行しよう

新しいpassを実行するには、Cのプログラムで clang を呼び出し、今コンパイルした共有ライブラリを指す変なフラグを使います。

$ clang -Xclang -load -Xclang build/skeleton/libSkeletonPass.* something.c
I saw a function called main!

この -Xclang -load -Xclang path/to/lib.so を使えば、 Clang上であなたのpassを読み込み、アクティベートできます 。より大きなプロジェクトを処理する必要があるなら、Makefileの CFLAGS か、あなたのビルドシステム上の同等なものに対して、これらの引数を付加すればいいのです。

（ clang から呼び出すのとは別に、passを一度に実行することもできます。これは、LLVMの opt コマンドを用いるやり方で、 公式のドキュメントで記述されている方法です が、この記事では触れません）。

おめでとうございます。コンパイラのハックができました。次は、この演習passを拡張して、プログラムに対して何か面白いことをしてみましょう。

LLVM IRを理解する

モジュール は、 関数 で構成され、関数は 基本ブロック で、基本ブロックは 命令 で構成されています。モジュール以外の全ては、 値 から枝分かれします。

LLVMでプログラムを扱うには、多少なりともIRの構造を知っておく必要があります。

構成

以下はLLVMプログラムで最も重要な構成要素の概要です。

• モジュール は、（大まかに言うと）ソースファイル、（専門的に言うと）トランスレーションユニットのことを意味し、これら以外の全てもモジュールに含まれています。
• 中でも注目すべきは、モジュールにその名前が意味する通りの、大量の実行可能な 関数 が含まれているということです（C++では、関数、メソッドのどちらもLLVM関数のことを指します）。
• 関数名や引数の宣言のことはさておき、関数は主に、 基本ブロック で構成されています。 基本ブロック は、コンパイラの概念として知られていますが、ここでは連続した命令の塊でしかありません。
• その 命令 ですが、これは単一コードの演算子です。抽象化の度合いは、ほぼ RISC と同じで、例えば、整数加算や浮動小数点除算、またはメモリに格納するといった命令など、機械語によく似ています。

関数や基本ブロック、命令を含むLLVMのほとんどが、 値 と呼ばれる多岐にわたる基底クラスから継承しているC++のクラスです。値は、数字やコードのアドレスなど、計算に使える値であれば何でも構いません。グローバル変数や定数（リテラル、即値とも呼ばれる。例えば数字の5など）もまた値になります。

命令

以下は、人間が理解することができる形式で記述されたLLVM IRの命令の一例です。

%5 = add i32 %4, 2

この命令は、2つの32ビット整数（ i32 型と表示）を加算することを意味しています。つまり、レジスタ4（ %4 ）の整数とリテラル2（ 2 ）を加算し、その結果をレジスタ5に表示させるということです。先程、私がLLVM IRは理想のRISCの機械語に似ていると言ったのは、これが理由です。レジスタといった同様の専門用語を使っていますが、たくさんのレジスタが無限に存在します。

同様の命令は、C++クラスの 命令 のインスタンスとしてコンパイラの内部で表現されています。オブジェクトには命令コードがあり、加算であること、型であること、そして他の値のオブジェクトのポインタであるオペランドのリストであることを示しています。この例の場合、 定数 のオブジェクトは数字の2であり、他の 命令 はレジスタ4となります。（LLVM IRは 静的単一代入 であることから、レジスタと命令は1つずつで、それらは同じものになります。レジスタの数値は、文字表現の中間生成物です。）

もし、あなたのプログラムでLLVM IRを出力してみたいのであれば、Clangを使ってみてください。

$ clang -emit-llvm -S -o - something.c

Pass内でのIRの調査

では、LLVM passの話に戻りましょう。全ての重要なIRオブジェクトを調査するには、 dump() という、誰もが知っている便利なメソッドを使います。これはIR内にある、人間が理解することができるオブジェクトの表現を出力してくれます。Passは関数に渡されているので、これを各関数の基本ブロック、そして各基本ブロックの命令セットに繰り返し適用するために使いましょう。

以下がそのコードです。このコードは、 “ containers （構成）”ブランチ 内にある llvm-pass-skeleton というgitリポジトリから入手が可能です。

errs() << "Function body:\n";
F.dump();

for (auto& B : F) {
  errs() << "Basic block:\n";
  B.dump();

  for (auto& I : B) {
    errs() << "Instruction: ";
    I.dump();
  }
}

C++11 の auto 型やforeachシンタックスを使えば、LLVM IRの階層間の移動が容易になります。

再度passを構築し、それを通してプログラムを起動させると、パーツ間を行き来するたびに、IRの様々なパーツが分散されていくのが分かると思います。

Passにもう少し面白いことをさせる

プログラムのパターンを探し、それが見つかったら、そのコードを変えてみてください。驚くことが起こります。簡単な例を挙げましょう。例えば、全ての関数の最初の二項演算子( + , - など)を乗算に変換したいとします。なんだか役立ちそうですよね？

コードはこんな感じになります。このバージョンは、実際に試せるプログラムの例と併せて、 “ mutate （変換）”ブランチ 内にある llvm-pass-skeleton というgitリポジトリから入手が可能です。

for (auto& B : F) {
  for (auto& I : B) {
    if (auto* op = dyn_cast<BinaryOperator>(&I)) {
      // Insert at the point where the instruction `op` appears.
      IRBuilder<> builder(op);

      // Make a multiply with the same operands as `op`.
      Value* lhs = op->getOperand(0);
      Value* rhs = op->getOperand(1);
      Value* mul = builder.CreateMul(lhs, rhs);

      // Everywhere the old instruction was used as an operand, use our
      // new multiply instruction instead.
      for (auto& U : op->uses()) {
        User* user = U.getUser();  // A User is anything with operands.
        user->setOperand(U.getOperandNo(), mul);
      }

      // We modified the code.
      return true;
    }
  }
}

詳細は以下の通りです。

• dyn_cast<T>(p) の構成は、 LLVM限定のイントロスペクションユーティリティ です。これは、動的な型テストを効率良く行うために、LLVMコードベースにあるいくつかの慣例を使用します。と言うのも、コンパイラではこれらのコンベンションを常に使用しなくてはならないからです。 I が aBinaryOperator でない場合、特定の構成はnullポインタを返します。ですから、このような特別なケースには有効です。
• IRBuilder は、コードを構成するために使用します。ここには、あなたが使いたいと思う様々なタイプの命令を作成する、大量のメソッドがリストされています。
• 新しい命令をコードに組み込むためには、命令が使われている場所を全て探し出し、新しい命令を引数として置き換えなくてはなりません。命令は値であることを思い出してください。乗算命令は、他の命令でオペランドとして使われているので、積は引数として送られることになります。
• 恐らく古い命令も取り除かなくてはいけないでしょう。しかし、簡潔にするために、ここまでにしておきます。

では、下記のプログラムをコンパイルすると、どうなるでしょう（コードはリポジトリにある example.c です）。

#include <stdio.h>
int main(int argc, const char** argv) {
    int num;
    scanf("%i", &num);
    printf("%i\n", num + 2);
    return 0;
}

通常のコンパイラでコンパイルをするとコードに記述された通りの結果となりますが、私たちのプラグインでは、2を追加するのではなく、値を倍にする結果となります。

$ cc example.c
$ ./a.out
10
12
$ clang -Xclang -load -Xclang build/skeleton/libSkeletonPass.so example.c
$ ./a.out
10
20

素晴らしい！

ランタイムライブラリとのリンク

重要な作業をするために、コードをインストルメントしなくてはならない時、 IRBuilder を使ってLLVMの命令を生成するのは手間がかかるので、C言語にランタイムの振る舞いを記述し、コンパイルしているプログラムにリンクさせたいと思うかもしれません。ここでは、二項演算子の結果をログするランタイムライブラリの記述方法を紹介します。

以下は、LLVMのpassコードです。このコードは、 “ rtlib “ブランチ 内の llvm-pass-skeleton リポジトリから入手できます。

// Get the function to call from our runtime library.
LLVMContext& Ctx = F.getContext();
Constant* logFunc = F.getParent()->getOrInsertFunction(
  "logop", Type::getVoidTy(Ctx), Type::getInt32Ty(Ctx), NULL
);

for (auto& B : F) {
  for (auto& I : B) {
    if (auto* op = dyn_cast<BinaryOperator>(&I)) {
      // Insert *after* `op`.
      IRBuilder<> builder(op);
      builder.SetInsertPoint(&B, ++builder.GetInsertPoint());

      // Insert a call to our function.
      Value* args[] = {op};
      builder.CreateCall(logFunc, args);

      return true;
    }
  }
}

必要なツールは、 Module::getOrInsertFunctio と IRBuilder::CreateCall です。前者は、ランタイム関数 logop に対する宣言を定義します。これは、関数本体を持たないC言語のソースのプログラムにある void logop(int i); の宣言と類似しています。インストルメント化されたコードは、 logop 関数を定義するランタイムライブラリ（リポジトリにある rtlib.c ）と組み合わされます。

#include <stdio.h>
void logop(int i) {
  printf("computed: %i\n", i);
}

インストルメント化されたプログラムを起動するには、ランタイムライブラリとリンクさせます。

$ cc -c rtlib.c
$ clang -Xclang -load -Xclang build/skeleton/libSkeletonPass.so -c example.c
$ cc example.o rtlib.o
$ ./a.out
12
computed: 14
14

また、機械語にコンパイルする前に、プログラムとランタイムライブラリをまとめることも可能です。 llvm-link ユーティリティ（ ld と同等レベルの大まかなIRと思われるかもしれませんが）が活用できます。

アノテーション

ほとんどのプロジェクトは、最終的にプログラマと連携しなくてはなりません。そして、プログラムからLLVM passに追加情報を渡す方法である、アノテーションの必要性を感じるでしょう。ここで、アノテーションシステムを構築するいくつかの方法をご紹介します。

• 実用的な攻略法は、マジック関数を使用することです。ヘッダファイルにユニークな名前が付けられたものなどと併せて、いくつかの空関数を宣言します。このファイルをソースに加え、何もしないこれらの関数を呼び出します。そして、passから関数を呼び出す CallInsｔ 命令 を探し、マジックをトリガーするためにこの命令を使います。例えば、特定の領域に対して、プログラムがコードの変更を制限させるように __enable_instrumentation() と __disable_instrumentation() を呼び出します。
• プログラマに関数や変数の宣言に対してマーカーを加えてもらう必要があるなら、Clangの __attribute__((annotate("foo"))) シンタックスによって、pass内でプロセスすることができる任意の文字列と共に メタデータ を発行できます。Brandon Holtには、 このテクニックに関するいくつかの裏話があります 。もし、宣言する代わりに式をマークする必要があるなら、ドキュメント化されておらず、制限されてしまっている intrinsic文、 __builtin_annotation(e, "foo") が使えるかもしれません。
• 新しいシンタックスを解釈するためにClangそのものを修正しようと思うかもしれませんが、お勧めしません。
• 知らず知らずのうちにやっていることかもしれませんが、型をアノテーションする必要がある人のために、私は、 Quala と言うシステムを開発しています。カスタムの型修飾子とJava向け JSR-308 のような、取り外し可能な型システムをサポートするためにClangにパッチを当てています。このプロジェクトに協力していただける方は、是非 ご連絡ください ！

これらのテクニックに関して更なる記事を投稿していきたいと思います。

更に

LLVMは膨大な範囲に及びます。今回、触れることができなかったトピックについて、いくつか挙げておきます。

• LLVMの不要なものを格納しておく場所にある、利用可能で莫大な数の古典的なコンパイラ解析の配列を使用する。
• アーキテクトがよくやりたいように、バックエンドをハックすることにより、特別な機械命令を生成する。
• デバッグ情報 を利用することで、IRの時点で一致しているソース行と列を連結することが可能。
• Clangのためのフロントエンドのプラグイン を記述する。

あなたが素晴らしい何かを作り出すのに、少しでも助けになることを願っています。研究して、作成して、これが役に立ったか 教えてください ！

ワシントン大学の アーキテクチャ グループと システム グループに感謝します。この記事で取り扱ったトピックに対し活発に議論し、刺激になるいい質問をしてくれました。

親切な読者による補遺。

• Emery Berger の指摘によると、 Pin のようなDynamic Binary Instrumentationツールは、アーキテクチャの特性、すなわちレジスタ、メモリ階層、命令エンコードなどの監視が必要な場合に、いまだ有効と言えるようです。
• Brandon Holt はGraphVizで制御フローグラフを描写する方法を含め、 LLVMにおけるデバッグのコツ を投稿しています。
• John Regehr はAPIの不安定さなど、LLVMのスター型とソフトウェアワゴンをつなぐ弱点について 述べています 。リリースごとにLLVM内には多数の変更が施されているので、プロジェクトを維持することは、プロジェクトを研究し続けることにもなります。 Alex Bradbury の LLVMの週刊ニュースレター はLLVMエコシステムを理解するうえで、非常に使えるリソースです。

コメントや質問があれば、 メール していただくか @samps 宛てにツイートしてください。