RustのLLVM IRでプログラム分析ことはじめ

この記事は、Rustその2 Advent Calendar 2019の22日目の記事です。

はじめに

Rustのコンパイラは内部でLLVMを利用しています。

LLVMとはいわゆるコンパイラ基盤というもので、Rustのコンパイル側でLLVMの中間コード(IR)まで生成できたら、あとはLLVM側が最適化や実行ファイルの作成までを行ってくれます。

Rust Blogの記事「Introducing MIR」の中にある画像が大変わかりやすいので、そちらを引用させていただきます。

f:id:toyamaguchi:20191221104040p:plain
ビルドの流れ

このコンパイラ基盤の視点から言うと、Rustコンパイラはフロントエンド、LLVM側はバックエンドという位置づけです。 LLVMが様々な環境で動くプログラムを生成できるからこそ、Rustも多くの環境で動くプログラムを比較的容易に生成できるわけです。 プログラムの最適化技術についても、LLVM側でそのノウハウを洗練させていけば、LLVMを利用しているプログラミング言語すべてで洗練されていきます。

LLVMコンパイルをする過程では、「Pass」という名前のモジュールにIRを何度か通すことになります。 Passは入力としてIRを受け付け、それを最適化して、IRを出力するフィルタのようなものです。 それぞれ異なる最適化手法が実装されたPassをいくつか通し、IRを洗練させていくようです。

これについては、Adrian Sampson氏のブログ記事「LLVM for Grad Students」(日本語記事)が初心者向けで大変詳しくてありがたいです。(むしろ、この記事をRustに適用したのが本記事と言っても過言はないです。) このブログ記事から、LLVMコンパイルの流れの図を引用したいと思います。

f:id:toyamaguchi:20191221110800p:plain
LLVMコンパイルの流れ

また、LLVMはただのコンパイラ基盤として使われるだけでなく、ソフトウェアの分析ツールとして使われることもあります。 ソースコードコンパイルする際に得られるメタデータを使って、ソフトウェアの構造を明らかにしたり、データの危険な使用がないかを調査するのです。 その調査をする際にも、さきほどのPassを使ってメタデータを取得していくようです。

前置きが長くなりましたが、このブログ記事ではRustのソースコードからLLVM IRを生成し、それをPassに読み込ませてプログラム分析をする「一歩目」を踏み出そうと思います。

LLVMのダウンロード

どうもRustはLLVM 9.0を使っているようなので、それをダウンロードします。

私のLinux環境はDebian Linuxなのですが、DebianUbuntuのユーザーにはaptでインストールできるnightly packageというものがあるようなので、今回はそれを使ってみます。

このサイトに従って、次のコマンドを実行しました。

bash -c "$(wget -O - https://apt.llvm.org/llvm.sh)"

2019年12月21日現在では、LLVM 9.0.1がダウンロードできたようです。

Passの作成

LLVM 9.0の仕様に沿ったPassを用意します。

今回はPassの作り方も詳しくわからないため、次のレポジトリを利用します。 これはLLVMのPassのいくつかの実装例を公開してくれているレポジトリです。

このレポジトリの中には、PassのHelloWorldがありますので、それを使っていきます。 CMakeLists.txtとHelloWorld.cppをダウンロードしてましょう。

ただし、どうもこのままできあがったPassを使うと、使用した最後にSegmentation Faultが起こってしまうようです。 調べてみたところ、GitHubのIssueStackoverflowに似た問題があがっていたので、この解決方法を導入します。 Passのコンパイル時に、リンカオプションの-Wl,-znodeleteを追加することで、共有オブジェクトのアンロードを防ぎ、Segmentation Faultを防ぐことができるそうです。

CMakeLists.txtの中に、次に記すような行を追加しておきましょう。

if(NOT LLVM_ENABLE_RTTI)                                
  set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fno-rtti")   
endif()                                                 
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wl,-znodelete")    # add this line!

ちなみに、コンパイル方法は次のようになります。(一般的なcmakeの方法です。) 2つのファイルが置いてあるフォルダ内で実行しましょう。

mkdir build
cd build
cmake ..
make

これでlibHelloWorld.soというPassファイルが完成します。

RustのソースコードLLVM IRに変換

今回はRustのソースコードとして、「cargo new」してできるデフォルトのソースコードを利用します。 プロジェクトフォルダを作って、中に入りましょう。

cargo new hello_world
cd hello_world

rustcコマンドでLLVM IRを作成するコマンドは、次のようになります。 このコマンドで、人間が読めるLLVM IRのソースコードである、main.llが生成されます。

rustc src/main.rs --emit=llvm-ir

ただ、実際のところPassが読み込むのはLLVM IRのビットコードです。 rustcコマンドでLLVM IRのビットコード生成しましょう。 main.bcが生成されます。

rustc src/main.rs --emit=llvm-bc

Passによる分析

今回のPassはソースコード上の関数を読み込む際に実行される「FunctionPass」です。 しかも、関数の名前と引数の数を表示するだけの簡単なものなので、実は「分析」というほど難しいものではありません。

さっそくPassを使ってmain.bcを読み込んでみましょう。「opt」コマンドというものを使って実行します。

opt-9 -load pass-f/build/libHelloWorld.so --legacy-hello-world -o output.bc main.bc

これを実行すると、標準出力に次のような内容が出力されました。

Visiting: _ZN3std2rt10lang_start17hf1171c84b02c6532E (takes 3 args)
Visiting: _ZN3std2rt10lang_start28_$u7b$$u7b$closure$u7d$$u7d$17h7ce99b67d7e681a9E (takes 1 args)
Visiting: _ZN3std3sys4unix7process14process_common8ExitCode6as_i3217h8b78488b8649031eE (takes 1 args)
Visiting: _ZN4core3fmt9Arguments6new_v117hcb57928db4a7c5fcE (takes 5 args)
Visiting: _ZN4core3ops8function6FnOnce40call_once$u7b$$u7b$vtable.shim$u7d$$u7d$17hfa439257376c02c0E (takes 1 args)
Visiting: _ZN4core3ops8function6FnOnce9call_once17h04664e48e200f143E (takes 1 args)
Visiting: _ZN4core3ptr18real_drop_in_place17h11442e413e5b1531E (takes 1 args)
Visiting: _ZN54_$LT$$LP$$RP$$u20$as$u20$std..process..Termination$GT$6report17hfd48e48bde5a14dcE (takes 0 args)
Visiting: _ZN68_$LT$std..process..ExitCode$u20$as$u20$std..process..Termination$GT$6report17h7035bf1bc5cd901aE (takes 1 args)
Visiting: _ZN4main4main17h9e0ea2b04575dfdbE (takes 0 args)
Visiting: main (takes 2 args)

HelloWorld.cpp内でいうところの次のコードが、関数の情報を表示しているところです。

void visitor(Function &F) {
    errs() << "Visiting: ";
    errs() << F.getName() << " (takes ";
    errs() << F.arg_size() << " args)\n";
}

IRのビットコードには、main関数以外にもプログラムの実行に関わる目に見えていなかった関数があったことがわかりますね。

まとめ

Rustの内部では、コンパイラ基盤のLLVMを使っています。

このLLVMを使うとプログラム分析を行うことができます。

今回はFunctionPassという種類のPassを作成しました。

Passの種類は他にもModulePass、CallGraphSCCPass、BasicBlockPassなど、興味深い名前のものもあります。

いろいろな種類のPassを作ってみて、Rustのソースコードを分析できるようにしたら楽しそうですね。

参考文献

f:id:toyamaguchi:20191221150338p:plain