FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

LLVMのPassの作り方について学ぶ(ドキュメントを読む1)

LLVM

LLVMについて、バックエンドの部分はある程度勉強したけど、そういえばPassの作り方をまじめに勉強したことが無かった。

LLVMと言えばPassだろう！ということでPassの作り方について勉強することにした。これはそのうちLLVMの拡張や最適化をしたいときに役に立つはずだ。

参考にしたのはWriting LLVM Passというドキュメント。読み進めていくとこのPass Managerは古いそうなのだが、まあまずは古い方のドキュメントを読んで、新しい方の差分を確認していけばよかろう。

llvm.org

LLVMのPassを書く

Passとは何か？

LLVMのPassフレームワークはLLVMシステムで重要な部分です。 LLVM Passはコンパイラ内に存在する面白い部分殆どに存在しています。 Passは、コンパイラを構成する変換や最適化を行い、これらの変換で使用される解析結果を構築し、そして何よりもコンパイラコードの構造化技術です。

LLVMのすべてのPassはPassクラスのサブクラスで、仮想メソッドをPassクラスから継承してオーバライドすることによって機能を実装します。 Passがどのように動作するかに依存して、ModulePass, CallGraphSCCPass, FunctionPass, LoopPass, RegionPassクラスのどれから継承するかを選択する必要があります。 それぞれのクラスがpassがどのように動作するかの情報のシステムを提供し、どのように他のpassと組み合わせられるのかについての情報を提供します。 LLVM Passフレームワークの大きな特徴の一つに、あなたのpassの要件(どのクラスから継承されたか、を示す)をもとに効率的なpassの実行方法のスケジューリングがあります。

まずはどのようにpassを構築するのか、コードをセットアップしてコンパイルし、ロードして実行することですべてを見ていきましょう。 基本を押さえた後で、より高度な機能について議論します。

注意: このドキュメントでは、レガシーなpassマネージャを扱っています。 LLVMは最適化パイプラインのために、新しいpassマネージャをデフォルトで使用しています(codegenパイプラインはまだレガシーパスマネージャを使用しています)。 詳細については、Writing an LLVM Pass と Using the New Pass Managerを参照のこと。 optでレガシーpassマネージャを使用するには、すべてのoptの呼び出しに-enable-new-pm=0フラグを渡してください。

クイックスタート: hello worldを書く

ここでは、"hello world" passを書く手順について説明します。 "Hello" passは単純にコンパイルされたプログラムのうち、外部関数ではないものの名前をプリントアウトするだけのものです。 これはプログラムを全く変更せずに、単純に調査するだけです。 このpassのソースコードとファイルはLLVMのソースツリー内のlib/Transform/Helloディレクトリに置かれています。

ビルド環境を構築する

まず、LLVMを校正してビルドします。次にLLVMのソースベースに対して新しいディレクトうぃろ作成する必要があります。 この例では、lib/Transforms/Helloに新しいディレクトリを作成したものとします。 最後に、新しいpassのためのソースコードをコンパイルするためのビルドスクリプトを用意する必要があります。 このために、以下のコードをコピーしてCMakeLists.txtとして保存してください。

add_llvm_library( LLVMHello MODULE
  Hello.cpp

  PLUGIN_TOOL
  opt
  )

そして以下のコードをlib/Transforms/CMakeLists.txtに挿入します。

add_subdirectory(Hello)

(すでにHelloディレクトリが作成されており、"Hello"サンプルpassが実装されている場合、すぐにそれを試すことができます。 この場合はCMakeLists.txtファイルを変更する必要はありません。 すべてを一からから作りたい場合、別の名前を使用して試すことができます)

ビルドスクリプトは当該ディレクトリのHello.cppを指定しており、これがコンパイルされて共有オブジェクト$(LEVEL)/lib/LLVMHello.soとしてリンクされます。 このオブジェクトはoptの-loadオプションによって動的んいロードされます。 使用しているオペレーティングシステムが.so以外の接尾子を使っている場合(WindowsやMacOSなど)、適切な拡張子が使用されます。

ビルドスクリプトの構築が完了したら、次にpassを書いていきます。

必須の基本コード

ここまでで新しいpassをコンパイルするための準備が整いました。次にコードを書いていきます。まず以下から始めましょう。

#include "llvm/Pass.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/raw_ostream.h"

Pass.hは私たちは今Passを書いているので必要なもの、 何かをプリントするのでFunctionが必要です。

次に以下を追加します。

using namespace llvm;

これは、インクルードファイルに機能はllvm名前空間に存在しているからです。

次に、

namespace {

これは無名の名前空間から始まるという意味です。無名の名前空間はC++ではstaticキーワードでC言語から(グローバルスコープで)使用できます。 無名の名前空間で定義したものは、このファイルでのみ参照できます。 もしこの機能にあまり詳しくなければ、まともなC++の本を読んで参考にしてください。

次に、私たちのpassを宣言します:

static Hello : public FunctionPass {

これはFunctionPassのサブクラスとして"Hello"クラスを提起します。 ビルトインpassのサブクラスの違いは以降で説明しますが、 今はFunctionPassは関数を一度に処理するということだけ知っておいてください。

static char ID;
Hello() : FunctionPass(ID) {}

これはLLVM内でpassを識別するための識別子を定義します。 これによりLLVMがC++の高価なランタイム情報を使用することが回避できます。

  bool runOnFunction(Function &F) override {
    errs() << "Hello: ";
    errs().write_escaped(F.getName()) << '\n';
    return false;
  }
}; // end of struct Hello
}  // end of anonymous namespace

runOnFunction()メソッドを定義します。 これは私たちのやりたいことを実現する関数で、各関数の名前をメッセージとして出力します。

ここでpassのIDを初期化します。LLVMはpassを識別するためにIDアドレスを使用しますので、この初期化はあまり重要ではありません。

static RegisterPass<Hello> X("hello", "Hello World Pass",
                             false /* Only looks at CFG */,
                             false /* Analysis Pass */);

最後に、Helloクラスを登録しますし、 コマンドライン引数として"hello"を使えるようにし、名前を"Hello World Pass"とします。 最後の2つの引数はこのクラスの動作を示しています: もしpassがCFG中を探索し、それを変更しない場合、3つ目の引数をtrueに設定します; もしそのpassが解析pass、例えばdominator tree passの場合、4番目の引数をtrueに設定します。

もしpassを既存のパイプラインの1ステップとして登録したい場合は、いくつかの拡張ポイントが提供されます。 例えば、PassManagerBuilder::EP_EarlyAsPossble は私たちのpassを最適化の前に適用し、 PassManagerBuilder::EP_FullLinkTimeOptimizationLastではリンク時最適化の後に挿入します。

static llvm::RegisterStandardPasses Y(
    llvm::PassManagerBuilder::EP_EarlyAsPossible,
    [](const llvm::PassManagerBuilder &Builder,
       llvm::legacy::PassManagerBase &PM) { PM.add(new Hello()); });

全体として、.cppファイルは以下のようになります。

#include "llvm/Pass.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/raw_ostream.h"

#include "llvm/IR/LegacyPassManager.h"
#include "llvm/Transforms/IPO/PassManagerBuilder.h"

using namespace llvm;

namespace {
struct Hello : public FunctionPass {
  static char ID;
  Hello() : FunctionPass(ID) {}

  bool runOnFunction(Function &F) override {
    errs() << "Hello: ";
    errs().write_escaped(F.getName()) << '\n';
    return false;
  }
}; // end of struct Hello
}  // end of anonymous namespace

char Hello::ID = 0;
static RegisterPass<Hello> X("hello", "Hello World Pass",
                             false /* Only looks at CFG */,
                             false /* Analysis Pass */);

static RegisterStandardPasses Y(
    PassManagerBuilder::EP_EarlyAsPossible,
    [](const PassManagerBuilder &Builder,
       legacy::PassManagerBase &PM) { PM.add(new Hello()); });

すべてを組み合わせて、ビルドディレクトリのトップで単にgmakeコマンドを入力すればlib/LLVMHello.soファイルが生成されているはずです。 このファイルに含まれているものすべてが無名名前空間に含まれています - これはpass自体が自身を内蔵しているユニットであり、 外部のインタフェースを必要としない(しかし必要とあれば持つこともできます)ということを意味します。

optを使ったpassの実行

私たちは新しく作った、輝かしい共有オブジェクトを手に入れました。optコマンドを使ってLLVM実行中にpassを渡すことができます。 RegisterPassを使ってpassを登録したので、optツールによってそれにアクセスすることができます。

テストのために、Getting Started with the LLVM System の最後に使った例を使って "Hello World"をLLVMでコンパイルしてみましょう。 ビットコードファイル(hello.bc)のプログラム全体を以下のようにして変換します(もちろん、どのようなビットコードでも問題ありません)。

$ opt -load lib/LLVMHello.so -hello < hello.bc > /dev/null
Hello: __main
Hello: puts
Hello: main

-loadオプションによってoptがどのような共有オブジェクトをpassとしてロードすべきなのかを指定しており、 これにより-hello引数が有効となります。(これが[passの登録]の必要な理由です)。 Hello passはどのような興味深い方法でもプログラムを全く変更しないので、私たちはoptの結果を単純に捨てています(結果を/dev/nullに渡しています)。

他にどのような文字列を登録したのか、optを-helpオプションで見てみましょう:

$ opt -load lib/LLVMHello.so -help
OVERVIEW: llvm .bc -> .bc modular optimizer and analysis printer

USAGE: opt [subcommand] [options] <input bitcode file>

OPTIONS:
  Optimizations available:
...
    -guard-widening           - Widen guards
    -gvn                      - Global Value Numbering
    -gvn-hoist                - Early GVN Hoisting of Expressions
    -hello                    - Hello World Pass
    -indvars                  - Induction Variable Simplification
    -inferattrs               - Infer set function attributes
...

passの名前に、あなたのpassの情報文字列が追加され、optのいくつかのドキュメントに追加されています。 これで動作するpassを手に入れることができましたので、次によりクールな変換用のpassの実装に移ることができます。 一度動作を確認しテストすると、このpassがどれくらいの速度なのかをチェックできると便利です。 PassManagerは便利なコマンドラインオプション(-time-passes)を提供しており、他のpassと一緒にあなたのpassが どれくらいの実行時間だったのかを知ることができます。例えば:

$ opt -load lib/LLVMHello.so -hello -time-passes < hello.bc > /dev/null
Hello: __main
Hello: puts
Hello: main
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 0.0007 seconds (0.0005 wall clock)

   ---User Time---   --User+System--   ---Wall Time---  --- Name ---
   0.0004 ( 55.3%)   0.0004 ( 55.3%)   0.0004 ( 75.7%)  Bitcode Writer
   0.0003 ( 44.7%)   0.0003 ( 44.7%)   0.0001 ( 13.6%)  Hello World Pass
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0001 ( 10.7%)  Module Verifier
   0.0007 (100.0%)   0.0007 (100.0%)   0.0005 (100.0%)  Total

見てわかる通り私たちの実装はかなり高速です。他のpassはoptによって自動的に挿入されたもので、 あなたのpassによってLLVMから出力されたものが有効でLLVMにより正しく構成されているもの確認し、 何も壊されていないことを確認するためのものです。

ここまでで、passの基本とpassの裏側にあるメカニズムについてみてきました。 これらがどのように動作するのかと、どのように使用すればよいのかについてより詳細に見ていきましょう。