第6章 Passの概要と実装方法

6.1 Passの概念

ここでLLVMにおけるPassの概念を説明しておきます．LLVM IRはPassによって解析，最適化処理を施されます．要はPassはLLVM IRに何らかの操作をする際に必要になるものと思えば良いと思います．ここで改めてLLVMの構成図を載せておきます．

LLVMの構成

図6.1: LLVMの構成

LLVMではユーザが任意のPassを適用することができます．PassはPassManagerによって管理され，PassManagerは登録されたPassをスケジューリングしてLLVM IRに適用します．

6.2 Passの種類

一言でPassと言っても，Passには様々な種類があります．本節ではLLVMに用意されているPassの主な基底クラスを紹介します．

ユーザは自分がどのレベルでLLVM IRにアクセスして処理を行いたいかによって適切なPassの基底クラスを選択，継承し，オリジナルのPassを実装します．例えば，LLVM IR内のループに対して何かを行いたいというのであればLoopPassを継承すればいいですし，BasicBlock単位で処理を行いたいというのであればBasicBlockPassを継承すべきです．

6.2.1 ImmutablePass

ImmutablePassはLLVM IRに対して変換を一切行わないPassです．このPassは一般的な変換や解析は行いませんが，ターゲットとなるアーキテクチャ情報等の様々な最適化に有用な静的情報を提供します．Writing LLVM Passによると，ImmutablePassはrunされない特殊なPassとなっています．なお，ImmutablePassを継承したクラスの例としては，DataLayoutクラスがあります．

6.2.2 ModulePass

ModulePassはユーザが使用できる最も一般的な基底クラスです．ModulePassの派生クラスはプログラム全体を必要とし，Functionのボディを参照したりFunctionの追加/削除を行います．

ModulePassの派生クラスは，ModulePassを継承した上でrunOnModuleメソッドをオーバーロードする必要があります．runOnModuleメソッドのインタフェースを以下に示します．

llvm::ModulePass::runOnModule

virtual bool runOnModule(Module &M) = 0;

runOnModuleには処理対象となるModuleが渡され，ユーザはこのメソッドで変換や解析などの自身の実装したい処理を行います．runOnModuleは最適化によってModuleが修正された場合にtrueを返し，そうでなければfalseを返すルールになっています．

以降で紹介するPassも同様で，基本的にrunOnXXというメソッドに処理対象が渡されるため，runOnXXメソッドで目的の処理を行います．例えばそれはFunction単位であったりLoop単位であったりしますが，考え方は同じです．

6.2.3 FunctionPass

FunctionPassの処理はプログラム中の全てのFunctionに対して実行されます．FunctionPassは決まった順序で実行されるわけではなく，また外部関数を変更することはありません．FunctionPassでは以下のことをしてはいけません．

  1. 現在処理中のFunction以外のFunctionを操作すること
  2. ModuleにFunctionの追加/削除を行うこと
  3. Moduleにグローバル変数の追加/削除を行うこと
  4. runOnFunctionの実行にまたがって状態を維持すること

FuncitonPassの派生クラスは以下の三つのメソッドをオーバーロードすることができます．これら三つのメソッドは何れもプログラムに変更を行った場合trueを返し，それ以外の場合falseを返却します．

doInitialization

一つ目のメソッドはdoInitializationメソッドです．doInitializationメソッドのインタフェースを以下に示します．

llmv::FunctionPass::doInitialization

virtual bool doInitialization(Module &M);

doInitializationメソッドは，Functionの追加/削除などFunctionPassで許されていない操作のほとんどを実行してよいメソッドです．また，doInitializationメソッドは処理されるFunctionに依存しない要素の初期化を行う場所でもあります．なお，doInitializationメソッドの呼び出しは他のいかなるPassの実行ともオーバーラップしません．

runOnFunction

二つ目のメソッドはrunOnFunctionメソッドです．runOnFunctionメソッドのインタフェースを以下に示します．

llvm::FunctionPass::runOnFunction

virtual bool runOnFunction(Function &F) = 0;

runOnFunctionはFunction毎に呼び出されます．Functionに対する変換や解析を行うためには，全てのFunctionPassの派生クラスはrunOnFunctionを実装する必要があります．通常，Functionが変更された場合にrunOnFuncionメソッドはtrueを返却します．

doFinalization

三つ目のメソッドはdoFinalizationメソッドです．doFinalizationメソッドのインタフェースを以下に示します．

llvm::FunctionPass::doFinalization

virtual bool doFinalization(Module &M)

doFinalizationメソッドはプログラム中の全てのFunctionに対してrunOnFunctionメソッドが呼び出されたあとに呼ばれます．

6.2.4 LoopPass

LoopPassの処理は各Functionの全てのLoopに対して実行されます．なお，LoopPassは多重ループについては内側のループから順に処理します．

LoopPassの派生クラスはLPPassManagerを使用することでLoopのネスト構造を変更することができます．LoopPassの派生クラスは以下の三つの抽象メソッドをオーバーロードすることができます．これら三つのメソッドは何れもプログラムに変更を行った場合trueを返し，それ以外の場合falseを返却します．

doInitialization

一つ目のメソッドはdoInitalizationメソッドです．doInitializationメソッドのインタフェースを以下に示します．

llvm::LoopPass::doInitialization

virtual bool doInitialization(Loop *, LPPassManager &LPM);

doInitializationメソッドは処理されるFunctionに依存しない要素の初期化を行うよう設計されています．また，doInitializationメソッドの呼び出しは他のいかなるPassの実行ともオーバーラップしません．なお，FunctionやModuleレベルの解析情報にアクセスするためにはLPPassManagerインタフェースを使用する必要があります．

runOnLoop

二つ目はrunOnLoopメソッドです．runOnLoopメソッドのインタフェースを以下に示します．

llvm::LoopPass::runOnLoop

virtual bool runOnLoop(Loop *, LPPassManager &LPM) = 0;

他のPass同様，runOnLoopは各Loopに対する任意の処理を実装するために使用されます．LoopPassの派生クラスは変換や解析を行うためにrunOnLoopメソッドを実装する必要があります．通常，Loopが変更された場合にrunOnLoopメソッドはtrueを返却します．なお，Loopのネスト構造を変更するにはLPPassManagerインタフェースを使用する必要があります．

doFinalization

三つ目はdoFinalizationメソッドです．doFinalizationメソッドのインタフェースを以下に示します．

llvm::LoopPass::doFinalization

virtual bool doFinalization();

doFinalizationメソッドは全てのLoopに対してrunOnLoopが呼ばれた後に呼び出されます．

6.2.5 RegionPass

RegionPassはLoopPassに似ていますが，出入り口を一つずつしか持たない領域に対して処理を実行するという点で異なります．RegionPassはネスト構造に対しては，内側の領域から順に処理を適用します．

RegionPassはRGPassManagerインタフェースを使用することでRegionTreeを変更することが出来ます．RegionPassの派生クラスは以下の三つの抽象メソッドをオーバーロードすることができます．これら三つのメソッドは何れもプログラムに変更を行った場合trueを返し，それ以外の場合falseを返却します．

doInitialization

一つ目はdoInitializationメソッドです．doInitializationメソッドのインタフェースを以下に示します．

llvm::RegionPass::doInitialization

virtual bool doInitialization(Region *, RGPassManager &RGM);

doInitializationメソッドでは処理されるFunctionに依存しない要素の初期化を行います．また，doInitializationメソッドの呼び出しは他のいかなるPassの実行ともオーバーラップしません．なお，FunctionやModuleレベルの解析情報にアクセスするためにはRGPassManagerインタフェースを使用する必要があります．

runOnRegion

二つ目はrunOnRegionメソッドです．runOnRegionメソッドのインタフェースを以下に示します．

llvm::RegionPass::runOnRegion

virtual bool runOnRegion(Region *, RGPassManager &RGM) = 0;

RegionPassの派生クラスは変換や解析を行うためにrunOnRegionメソッドを必ず実装する必要があります．通常，Regionが変更された場合にrunOnRegionメソッドはtrueを返却します．なお，RegionTreeを変更するにはRGPassManagerインタフェースを使用する必要があります．

doFinalization

三つ目はdoFinalizationメソッドです．doFinalizationメソッドのインタフェースを以下に示します．

llvm::RegionPass::doFinalization

virtual bool doFinalization();

doFinalizationメソッドは全てのRegionに対してrunOnRegionが呼ばれた後に呼び出されます．

6.2.6 BasicBlockPass

BasicBlockPassは参照や変更の対象が単一のBasicBlockに限られる点以外はFunctionPassに非常によく似ています．BasicBlockPassは以下の処理を行うことが許されません．

  1. 処理中のBasicBlock以外のBasicBlockに対する参照や変更
  2. runOnBasicBlockの呼び出しにまたがった状態の保持
  3. CFGの変更
  4. FunctionPassで禁止されている処理

BasicBlockPassはFunctionPassと同様に，doInitialization(Module)やdoFinalization(Module)をオーバーライドすることができますが，そのほかに以下の3つの抽象メソッドを実装することができます．

doInitialization

一つ目はdoInitializationメソッドです．doInitializationメソッドのインタフェースを以下に示します．

llvm::BasicBlockPass::doInitialization

virtual bool doInitialization(Function &F);

doInitializationメソッドはBasicBlockPassで許されていないが，FunctionPassで許可されている処理はほとんど実行することが出来ます．また，doInitializationメソッドでは処理されるBasicBlockに依存しない要素の初期化を行います．なお，doInitializationメソッドの呼び出しは他のいかなるPassの実行ともオーバーラップしません．

runOnBasicBlock

二つ目はrunOnBasicBlockです．runOnBasicBlockメソッドのインタフェースを以下に示します．

llvm::BasicBlockPass::runBasicBlock

virtual bool runOnBasicBlock(BasicBlock &BB) = 0;

BasicBlockPassの処理を行うためにはこのメソッドを実装する必要があります．runOnBasicBlockメソッドは引数として渡された以外のBasicBlockに対して参照や変更を行ってはいけませんし，CFGの変更も許可されません．runOnBasicBlockはBasicBlockが変更された場合にtrueを返却します．

doFinalization

三つ目はdoFinalizationメソッドです．doFinalizationメソッドのインタフェースを以下に示します．

llvm::BasicBlockPass::doFinalization

virtual bool doFinalization(Function &F);

doFinalizationメソッドはプログラム中のコンパイルされた全てのBasicBlockに対するrunOnBasicBlockの呼び出しが完了した後に呼び出されます．

その他のPassの基底クラス

上記以外のPassの基底クラスにはCallGraphSCCPassやMachineFunctionPassがあります．CallGraphSCCPassとはおそらくコールグラフの強連結成分(Strongly Connected Components)に対して処理を行うPassだと思うのですが，筆者はあまりよくわかっていません．保持する抽象メソッドや実装方法は他のPassと大差ないとは思います．MachineFunctionPassはいわゆるバックエンドで使用するPassで，このクラスについては第7章で説明があります．

6.3 その他のPassに実装すべきもの

前節冒頭で少し触れましたが，ユーザは先ほど説明したPassのうち自分の実装したいものに合わせてPassを選択し，継承します．例えばループに対して何か処理したければ，LoopPassを継承することでLLVM IRのLoop毎にrunOnLoopメソッドが呼ばれます．また，BasicBlockPassならBasicBlock毎，FunctionPassならFunction毎にrunOnXXメソッドが呼ばれます．

基本的にはdoInitalizationで初期化処理を行い，runOnメソッドに目的の処理を記述し，doFinalizationで終了処理という形になると思います．しかし，Passの実装には他にもいくつか実装すべき抽象メソッドやテンプレートが存在します．本節ではそれらのPassの実装に必要な事項を説明します．

6.3.1 Pass::getAnalysisUsageメソッド

まず最初にPassクラスのgetAnalysisUsageメソッドを紹介します．getAnalysisUsageメソッドは以下の様に定義されている抽象メソッドです．

lllvm::Pass::getAnalysisUsage

virtual void getAnalysisUsage(AnalysisUsage &Info) const;

getAnalysisUsageメソッドはPassの実行時に他のPassの実行結果(例えば何らかの解析Passの結果など)を利用したい場合に実装します．

実装するPassがLLVM IRに何らかの変換を行う様なPassであった場合，実行時に他のPassの解析結果に影響を与える可能性があるわけですが，getAnalysisUsageメソッドの実装では“このPassの解析結果には影響を与えない”という情報を引数として与えられるAnalysisUsageに設定することができます．また，getAnalysisUsageメソッド内では，何らかのPassの実行結果を利用したい場合などに，どのPassが必要かという情報をAnalaysisUsageに与えることもできます．本節の以降の説明で，この処理を行うためのメソッドを幾つか紹介します．なお，PassがgetAnalysisUsageメソッドを実装しない場合，そのPassは他のPassによる解析結果を必要とせず，また全ての他のPassの解析結果を無効にすることを意味します．

AnalysisUsage::addRequired<>とAnalysisUsage::addRequiredTransitive<>

一つ目のメソッドはAnalysisUsage::addRequiredメソッドです．addRequiredメソッドのインタフェースを以下に示します．

lllvm::AnalysisUsage::addRequired

template<class PassClass>
AnalysisUsage &llvm::AnalysisUsage::addRequired()

addRequiredメソッドは，実装するPassで事前に実行して欲しいPassを登録するために使用します．getAnalysisUsageメソッド内で，必要な情報を提供するPassクラスを指定してaddRequiredメソッドを呼ぶことで事前に実行しておいて欲しいPassを指定することができます．例えば，Pass内でLoopInfoを利用したい場合，getAnalysisUsageメソッド内にリスト6.1の様に記述します．

リスト6.1: addRequiredの使用例

 1: void MyPass::getAnalysisUsage(AnalysisUsage &AU) const {
 2:   AU.addRequired<LoopInfo>();
 3: }

また，Pass内で別のPassに処理を遷移させたい場合があります．その場合addRequiredメソッドの代わりにaddRequiedTransitiveメソッドを使用します．この二つのメソッドの違いは少々理解し難いのですが，何らかのPassの実行結果にアクセスしたい場合は前者を，何らかのPassにPassとしての処理(計算)をさせたい場合は後者を使用する様です．使用方法はほぼ同一のため省略します．

なお，指定したPassの解析情報を自身のPassで利用するには後述するgetAnalysisメソッドを利用します．

AnalysisUsage::addPreserved<>

PassManagerはPassの実行を管理し，必要の無い再計算を回避します．そのために，Passは影響を与えない他のPassを明示的に指定することが出来ます．これを実現するのがAnalysisUsageクラスのaddPreservedメソッドです．addPreservedメソッドのインタフェースを以下に示します．

llvm::AnalysisUsage::addPreserved

template<class PassClass>
AnalysisUsage &llvm::AnalysisUsage::addPreserved()

なお，類似のメソッドにsetPreservesAllメソッドがあります．setPreservesAllは全てのPassに影響を与えないということを意味します．例えば解析系のPassは，setPreservesAllを使用できるはずです．また，プログラム中の命令を変更するがCFGを変更しないような場合，setPreservesCFGメソッドを使用することが出来ます．

6.3.2 Pass::getAnalysis<>

次に紹介するメソッドはPassクラスのgetAnalysisメソッドです．このメソッドを使用することで，事前にaddRequiredメソッドで指定しておいたPassの実行結果を取得できます．getAnalysisメソッドのインタフェースを以下に示します．

llvm::Pass::getAnalysis

template<typename AnalysisType>
AnalysisType &llvm::Pass::getAnalysis()

AnalysisTypeにPassクラスを指定してgetAnalysisメソッドを使用することで，指定したPassの結果を取得することが出来ます．

例えば，runOnFunctionでLoopInfoの解析結果を使用したい場合は以下の様に記述します．

リスト6.2: getAnalysisの使用例

 1: void MyPass::getAnalysisUsage(AnalysisUsage &AU) const {
 2:   AU.addRequired<LoopInfo>();
 3: }
 4: 
 5: bool MyPass::runOnFunction(Function &F) {
 6:   LoopInfo &LI = getAnalysis<LoopInfo>();
 7:   ・・・
 8: }

6.3.3 PassのIDとRegisterPassテンプレート

本章で紹介したものを含め，Passの基底クラスのコンストラクタはIDというchar型の参照を引数としてとります．IDはパスを識別するために使用するものだそうで，ユーザが作成するPassについてもchar型の変数をメンバとして宣言し基底クラスのコンストラクタに渡す必要があります．以下にその例を示します．

リスト6.3: IDの初期化と基底クラスへの引渡し

 1: class MyPass:public FunctionPass{
 2:   public:
 3:     static char ID;
 4:     MyPass() : FunctionPass(ID){}
 5:     ・・・
 6: }
 7: char MyPass::ID=0;

なお，LLVMはパスを識別するためにIDのアドレスを使うらしいので，初期化値は重要ではないそうです．

また，作成したPassをopt等から参照するためにはPassをシステムに登録しておく必要があります．Passの登録にはRegisterPassという構造体テンプレートを使用します．ユーザはRegisterPass構造体のインスタンスをソースコード(.cppファイル)のグローバルスコープで宣言することでPassを登録することが出来ます．RegisterPassテンプレートのコンストラクタを以下に示します．

llvm::RegisterPassのコンストラクタ

template<typename passName>
llvm::RegisterPass<passName>::RegisterPass(const char *PassArg,
                                           const char *Name,
                                           bool CFGOnly = false,
                                           bool is_analysis = false)

まず，passNameには登録するPassクラスを指定します．次に，第1引数はopt等でこのPassを指定する際に使用する名前であり，第2引数は-helpオプションが指定された時等に表示する情報です．なお，第3，第4引数はPassの挙動を示します．第3引数のboolは登録するPassがCFGを参照するのみで，変更を行わない場合にtrueを指定します．また，第4引数は解析系のPassの場合にtrueを指定します．RegisterPassの使用例を以下に示します．

リスト6.4: RegisterPassの例

 1: RegisterPasss<MyPass> X("mypass", "My Original Pass");

上記の様にPassを登録した場合，optでは-mypassと指定することでMyPassを使用することが出来ます．

6.4 簡単なPassを実装してみる

それでは実際にPassを実装してみましょう．本来のPassは解析や最適化をするものですが，ここではまず“プログラム中の関数名を出力する”というとても簡単なPassを実装し，Passの実装の雰囲気を掴んでいきたいと思います．

6.4.1 どのPassを継承するか

Passを実装するためには，まずどのPassの基底クラスを継承するかを決定する必要があります．Passの基底クラスは6.2節で紹介したように様々ですが，今回はプログラム中の関数名を出力したいので，FunctionPassを継承すれば良さそうです．FunctionPassを継承し，runOnFunctionにFunctionが渡されるたびにFunction名を出力することにします．

6.4.2 Passクラスの宣言

FunctionPassを使用することを決定したので，実際に独自のPassクラスを実装していきます．今回はEasyPassという名前のクラスにしましょう．EasyPassクラスの宣言をリスト6.5に示します．

リスト6.5: 簡単なPassクラスの宣言

 1: #include <cstdio>
 2: #include <llvm/Pass.h>
 3: #include <llvm/Function.h>
 4: class EasyPass : public FunctionPass {
 5: public:
 6:   static char ID;
 7:   EasyPass() : FunctionPass(ID) {}
 8:   ~EasyPass() {}
 9: 
10:   virtual bool runOnFunction(Function &F);
11:   virtual void getAnalysisUsage(llvm::AnalysisUsage &AU) const;
12: };

EasyPassクラスは先ほど説明したとおりFunctionPassを継承します．また，メンバ変数としてIDを持ち，メソッドとしてコンストラクタ，デストラクタ，およびrunOnFuctionを持ちます．メンバ変数のIDは6.2.3節で説明したIDであり，コンストラクタにてFunctionPassのコンストラクタへと渡されます．なお，今回は特に事前処理，後処理がないため，doInitializationとdoFinalizationは実装しないことにします．

6.4.3 Passクラスの定義

次に，宣言したEasyPassクラスのメソッドと登録を実装しましょう．EasyPassクラスの定義をリスト6.6に示します．

リスト6.6: 簡単なPassクラスの定義

 1: bool EasyPass::runOnFunction(Function &F) {
 2:   llvm::errs() << "Function Name : " << F.getName().str() << "\n";
 3:   return false;
 4: }
 5: 
 6: void EasyPass::getAnalysisUsage(llvm::AnalysisUsage &AU) const {
 7:   // 変更を加えないためsetPreservesAll
 8:   AU.setPreservesAll();
 9: }
10: 
11: char EasyPass::ID = 0;
12: static RegisterPass<EasyPass>
13: X("easypass", "easy pass:only print function name", false, false);

1行目～4行目はrunOnFunctionの定義です．runOnFunctionでは，渡されたFunctionのgetNameメソッドでFunctionの名前を取得し，llvm::errsメソッドにて出力します．llvm::errsメソッドは“llvm/Support/raw_ostream.h”に宣言されているメソッドで，標準エラー出力へのraw_ostreamの参照を取得できます．中間表現に変更を加えるわけではないので，runOnFunctionの戻り値はfalseとします．また，同様に中間表現に一切変更を加えないため，6行からのgetAnalysisUsageメソッドでsetPreservesAllメソッドを呼び出しています．11行目はIDの初期化を行っています．今回は0で初期化していますが，6.2.3節で説明したとおり，必要なのはIDのアドレスであるため，初期値は他の値でも問題ありません．最後に，7行目でRegisterPassにてEasyPassクラスをeasypassという名前で登録しています．

6.4.4 Passのコンパイル/実行

それでは，作成したPassをコンパイルしてLLVM IRへ適用する方法を説明します．作成したPassを使用するには，まず下記のコマンドを投入して共有ライブラリを生成します．

# EasyPassクラスのソースコードはeasypass.cppとする
$ g++ -g easypass.cpp `llvm-config --cflags --ldflags -libs` -c -o easypass.o
# -sharedオプションをつけて共有ライブラリを作成　
$ g++ -g easypass.o -shared -o easypass.so

生成した共有ライブラリはoptコマンドを用いることでLLVM IRに適用できます．

# RegisterPassでeasypassという名前で登録している
# -load オプションで生成した共有ライブラリをロード
$ opt -load easypass.so -easypass ./sample/test.ll -S > /dev/null

入力するLLVM IRとしてリスト5.61で示したtest.llを使用した場合，次の様な出力が得られるはずです．

$ opt -load ./bin/easypass.so -easypass ./sample/test.ll -S > /dev/null
Function Name : test
Function Name : main
Function Name : printnum

なお，プログラム中で呼び出す場合は，作成したPassのインスタンスをPassManagerにaddする方法で使用できるはずです．

6.5 無用命令の削除を実装してみる

前節で“関数名を出力する”という非常に簡単なPassを実装しました．これによりPassの実装について大まかなイメージは掴めたかと思いますが，先ほどのPassではLLVM IRに対して特に解析や変換を行いませんし，実際に何かしらの解析/最適化のPassを実装するためにはあまり参考になるとは言えないでしょう．そこで今度は先ほどよりも少し役に立ちそうなPassを実装してみます．とは言え，あまり複雑なものを実装するのは入門書としては適しませんし，無駄にページ数がかさむだけですので簡単な例としてまず，“無用命令の削除”を行うPassを実装することにしましょう．実のところこの機能を持つPassはDCEクラスとしてLLVMで既に用意されているのですが，ここではそれらよりもずっとシンプルな(機能を限定した)Passを実装し，Pass実装の流れを説明したいと思います．

無用命令の削除は，英語でDead Code Eliminationとも呼ばれ，その名の通りプログラム中の死んでいる命令、つまり実行結果に影響を与えない無用な命令を削除する最適化です．本節では最初に最適化処理の前提条件や方針を考え，次に実装方法と結果を解説することにします．

6.5.1 前提条件を考える

まず最初に前提条件を考えてみましょう．無用命令の削除を行うためには，まずどの命令が無用命令となっている(死んでいる命令)かということを判断しなくてはなりません．逆に言うと，プログラム中で無用命令でない，つまり生きている命令を調べることができれば，それ以外のコードが無用命令になるとも言えます．ではLLVM IRにおいて生きている命令がどのような命令かということを考えてみるとどうでしょう？生きている，つまり実行結果に影響を与える命令ですので，次の様な命令が該当すると考えられます．

さらに，生きている命令がオペランドとして参照する命令は必要ですので，生きている命令には次の定義も追加できるでしょう．

というわけで，以上の四つの何れかの条件を満たす命令を生きている命令することにします．

6.5.2 実装方針を考える

ではLLVMでどのようにして生きている命令を探すかを考えてみましょう．まずは命令の削除をどの単位で行うか，という問題があります．処理を単純にするのであればBasicBlock単位で命令を一度確認し，不要な命令があれば削除すれば良い気もします．しかし，ある命令が使用するオペランドはBasicBlock間にまたがっている可能性があります．さらに，ある命令を削除することでその命令がオペランドとして参照していた命令が先ほどの四つ目の条件を満たさなくなり，削除対象になる可能性もあります．イメージ図を図6.2に示してみましょう．

無用命令削除の例

図6.2: 無用命令削除の例

図6.2では左側に今回の例として使用するLLVM IRの初期状態を記載しています．初期状態のLLVM IR内の命令を，先頭から順に削除可能であるか確認した場合，if.endというラベルがついたBasicBlockにあるmul命令が唯一削除可能な命令となります．他の命令，例えばphi命令はmul命令から参照されていますし，add命令やsub命令はそのphi命令から参照されています．また，残りの命令はbr命令とbr命令の条件として参照されるicmp命令です．ここでmul命令を削除するとどうなるでしょう？mul命令削除後のLLVM IRを図6.2の右側に記載しているので確認してみましょう．今度はif.endのphi命令が参照されなくなったことで削除可能な命令となっています．更に次のステップを考えた場合，このphi命令を削除すればadd命令やsub命令が削除できるようになります．つまり，削除する命令のオペランドとして参照している命令は，該当命令を削除することによって削除可能になる可能性がある，ということになります．

ここまでの内容を整理し，今回は下記の手順で命令の削除処理を行うことにします．

  1. Function内の全ての命令を調査対象の命令としてリストに登録する
  2. リスト内の命令を一つずつ調べて生きている命令であるか調べる
  3. 生きている命令でない(つまり無用な命令である)場合はその命令を削除対象とする
  4. 手順3で削除対象とされた場合はその命令のオペランドの値を生成する命令リストに追加する
  5. 手順3で削除対象とした命令を削除する
  6. リストが空になるまで手順2から繰り返す

最後に，本節で実装するPassのゴールを決めておきましょう．本節で実装するPassのゴールは図6.2の初期状態のコードから無用な命令を削除することにします．ここで図6.2のLLVM IRを念のため再掲しておきます．

リスト6.7: 無用な命令を含むLLVM IR

 1: ; ModuleID = './sample/sample.ll'
 2: target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
 3: target triple = "i386-pc-linux-gnu"
 4: 
 5: define i32 @test(i32 %i, i32 %j) nounwind {
 6: entry:
 7:   %cmp = icmp sgt i32 %j, 0
 8:   br i1 %cmp, label %if.then, label %if.else
 9: 
10: if.then:                                          ; preds = %entry
11:   %add = add nsw i32 %i, %j
12:   br label %if.end
13: 
14: if.else:                                          ; preds = %entry
15:   %sub = sub nsw i32 %i, %j
16:   br label %if.end
17: 
18: if.end:                                           ; preds = %if.else, %if.then
19:   %k.0 = phi i32 [ %add, %if.then ], [ %sub, %if.else ]
20:   %mul = mul nsw i32 %k.0, 10
21:   ret i32 0
22: }

なお，このLLVM IRは下記のC言語のソースコードをClangでコンパイルし，mem2regを適用すると得られます．

リスト6.8: C言語での記述

 1: int test(int i, int j) {
 2:   int k;
 3:   if (j > 0) {
 4:     k = i + j;
 5:   } else {
 6:     k = i - j;
 7:   }
 8:   k = k * 10;
 9:   return 0;
10: }

6.5.3 実装

Passクラスの宣言

それでは実装に移ります．まずは継承するPassを決定する必要がありますが，今回はFunction単位で処理を実行するのでFunctionPassを継承しましょう．クラス名をDCEliminatePassとした場合の宣言例を以下に示します．

リスト6.9: DCEliminatePassクラスの宣言

 1: class DCEliminatePass : public llvm::FunctionPass {
 2: public:
 3:   static char ID;
 4:   DCEliminatePass() : llvm::FunctionPass(ID) {}
 5:   ~DCEliminatePass() {}
 6: 
 7:   virtual bool runOnFunction(llvm::Function &F);
 8:   virtual void getAnalysisUsage(llvm::AnalysisUsage &AU) const;
 9: };

DCEliminatePassクラスはFunctionPassを継承し，runOnFunctionとgetAnalysisUsageを実装します．

Function内のInstructionの取得

ではここからrunOnFunctionの実装について見ていきましょう．まずは，一つ目の手順として，LLVM IR内のInstructionを全て取得する必要があります.これはllvm/Support/InstIterator.hのinst_begin関数，inst_end関数およびinst_iteratorを利用することで可能です．InstIterator.hのinst_begin関数，inst_end関数の定義は以下の通りです．

llvm::inst_beginとllvm::inst_endメソッド

inst_iterator inst_begin(Function *F)
inst_iterator inst_end(Function *F)

llvm::inst_begin関数ではイテレータの先頭が，llvm::inst_end関数では末尾要素の次を指すイテレータが返却されます．これらの関数を利用してInstructionを取得する際の例は下記の様になります．

リスト6.10: Function内のInstructionの取得

 1: bool DCEliminatePass::runOnFunction(llvm::Function &F) {
 2:   // 対象の命令を格納するlist
 3:   std::list<llvm::Instruction *> works;
 4: 
 5:   // 命令を削除したらtrueに変更
 6:   bool change = false;
 7: 
 8:   // 最初に全ての命令を調べる
 9:   llvm::inst_iterator inst_it = llvm::inst_begin(F);
10:   llvm::inst_iterator inst_it_end = llvm::inst_end(F);
11:   for (; inst_it != inst_it_end; inst_it++)
12:     works.push_back(&*inst_it);
13: 
14:   ・・・命令確認と削除処理・・・
15: 
16:   // 命令を削除したらtrueにしておく
17:   return change;
18: }

9行目，10行目でinst_begin関数とinst_end関数に対象のFunctionへの参照を渡し，イテレータを取得しています．inst_beginで取得したイテレータはC++のSTLと同様に++演算子を使用することで次の要素へ移れるため，11，12行目のループ文でinst_endで取得したイテレータと一致するまで処理を繰り返し，Function内の全てのInstructionを取得します．

ちなみに，LLVMでは他にも各種データ構造の要素を辿るために，XXXbegin，XXXendといったメソッドや関数が数多く用意されています．使用方法はC++のSTLと同様で，XXXbeginは先頭を，XXXendは末尾要素の次を指すイテレータを返却するメソッドです．例えば，Function内のInstructionを走査するという目的であれば，以下の様にFunctionクラスやBasicBlockクラスのbeginメソッド，endメソッドで返却されるイテレータを利用することでも可能です．

リスト6.11: Function内のInstructionを取得する際の別例

 1:   /*
 2:    * この方法でもInstructionを辿れる
 3:   */
 4:   llvm::Function::iterator bb_it = F.begin();
 5:   llvm::Function::iterator bb_it_end = F.end();
 6:   for(;bb_it != bb_it_end; bb_it++){
 7:     llvm::BasicBlock::iterator inst_it = bb_it->begin();
 8:     llvm::BasicBlock::iterator inst_it_end = bb_it->end();
 9:     for(;inst_it != inst_it_end; inst_it++)
10:       works.push_back(&*inst_it);
11:   }

生きている命令であるかの確認

命令の取得ができたら，次は取得した各命令が生きているかどうかの判定を行います．ここで，前節に記載した生きている命令の定義を再掲しておきます．

この定義の一つ目～三つ目は各Instrucitonの種類を調べるだけで良さそうです．これは第5章でも使用したisa<>テンプレートで簡単に実装できます．残りは4つ目の“生きている命令から参照されているか”という点ですが，命令を削除する場合はオペランドを再度確認するわけですので，“命令を調べる時点で残っている他の命令は全て生きている”と考えれば判定時に他の命令から参照されているかを調べるだけで良いと言えます．ある値が他の命令で使用されているかはInstructionクラスの基底クラスであるllvm::Valueクラスのuse_emptyメソッドによって簡単に調べられます．use_emptyメソッドの定義を以下に示します．

llvm::Value::use_emptyメソッド

bool llvm::Value::use_empty() const

llvm::Value::use_emptyメソッドはこのValueを参照する他のValueが存在する場合にfalseを，存在しない場合はtrueを返却するため，今回はこのメソッドがfalseが返したときは生きている命令であるとすることができます．以上から対象の命令が生きている命令であるかの確認は下記の様になります．

リスト6.12: 生きている命令であるかの確認

 1: bool DCEliminatePass::runOnFunction(llvm::Function &F) {
 2:   // 対象の命令を格納するlist
 3:   std::list<llvm::Instruction *> works;
 4: 
 5:   bool change = false;
 6: 
 7:   ・・・省略・・・
 8: 
 9:   // worksに追加した命令からdead codeがないか調べる
10:   // worksが空になるまで繰り返す
11:   llvm::Instruction *inst = NULL;
12:   while (!works.empty()) {
13:     // 命令をpop
14:     inst = works.front();
15:     works.pop_front();
16: 
17:     // この命令の値を使用している命令がある場合は生きているとする
18:     // load/store命令、call命令、終端命令(returnやbr)は生きている命令にする
19:     if (!inst->use_empty() || llvm::isa<llvm::TerminatorInst>(inst) ||
20:         llvm::isa<llvm::CallInst>(inst) || llvm::isa<llvm::LoadInst>(inst) ||
21:         llvm::isa<llvm::StoreInst>(inst))
22:       continue;
23: 
24:     ・・・ここで命令の削除を実行・・・
25:   }
26: 
27:   return change;
28: }

12行目からのループ内でリストに登録されたInstructionを順番に取り出し，生きている命令であるかを確認しています．実際にその確認を行っているのは19行目～21行目の条件文で，先ほど紹介したuse_emptyメソッドによる参照するValueの有無や，isaテンプレートによる命令の種類の確認を行っています．load命令に関してはvolatile属性がついていなければ削除対象としても良さそうですが，今回は実装を簡単にするためload命令の場合は常に生きている命令としています．なお，br命令を表すllvm::BranchInstクラスや，ret命令を表すReturnInstクラスなど，終端命令に分類される命令のクラスはTerminatorInstクラスのサブクラスですので，終端命令であるかどうかはisaテンプレートを用いてTerminatorInstクラスであるかを調べるだけで問題ありません．何れかの条件に一致すれば生きている命令のためcontinue文で次の命令の確認に移ります．また，全ての条件に一致しなかった場合は無用な命令ですので削除対称となります．

命令のオペランドの取得と命令の削除

次は命令の削除ですが，命令の削除を行う前にその命令のオペランドをリストに再登録する必要があります．そのためには対象のInstructionのオペランドを全て取得する必要があるのですが，これもイテレータを使用することで簡単に行えます．llvm::User::op_beginメソッドでイテレータの先頭が，llvm::User::op_endメソッドで末尾要素の次を指すイテレータが返却されます．ちなみに，UserクラスはInstructionクラスのスーパークラスです．使用方法は先程と同様のため説明は省略します．ここで取得した各オペランドをdyn_castテンプレートでInstructionにキャストすることで，命令が依存する値(オペランド)を生成する命令のInstructionを取得できます．オペランドがInstructionではなく，例えばConstantIntだった場合などにはdyn_castの結果としてNULLが返却されます．Instructionでなければ確認の必要は無いため，NULLが返却された場合はリストへの登録は不要です．

命令の削除についてはllvm::Instruction::eraseFromParentメソッドで実行可能です．このメソッドはBasicBlockからInstructionを除外するとともにそのInstructionをdeleteします．llvm::Instruction::eraseFromParentメソッドの定義は下記の通りです．

llvm::Instruction::eraseFromParentメソッド

void Instruction::eraseFromParent()

オペランドの取得と命令削除を追加したコードは以下の様になります．

リスト6.13: オペランドの取得と命令削除

 1: bool DCEliminatePass::runOnFunction(llvm::Function &F) {
 2:   // 対象の命令を格納するlist
 3:   std::list<llvm::Instruction *> works;
 4: 
 5:   // 変更したかどうかを表すフラグ
 6:   bool change = false;
 7: 
 8:   ・・・省略・・・
 9: 
10:   // worksに追加した命令からdead codeがないか調べる
11:   // worksが空になるまで繰り返す
12:   llvm::Instruction *inst = NULL;
13:   while (!works.empty()) {
14:     // 命令をpop
15:     inst = works.front();
16:     works.pop_front();
17: 
18:     ・・・生きている命令か判定・・・
19: 
20:     // 削除する命令のオペランドがdead codeになる可能性があるので
21:     // オペランドをworksに追加する
22:     llvm::User::op_iterator op_it = inst->op_begin();
23:     llvm::User::op_iterator op_it_end = inst->op_end();
24:     for (; op_it != op_it_end; op_it++) {
25:       // 既にworksに登録済みなら何もしない
26:       llvm::Instruction *op_inst = llvm::dyn_cast<llvm::Instruction>(*op_it);
27:       if (op_inst)
28:         if (std::find(works.begin(), works.end(), &*op_inst) == works.end())
29:           works.push_back(op_inst);
30:     }
31: 
32:     // 削除する
33:     change = true;
34:     inst->eraseFromParent();
35:   }
36: 
37:   return change;
38: }

24行からのループ文で，削除対象になった命令のオペランドをリストに再登録しています．先程と同様に，イテレータでオペランドを辿り，worksに登録されていないInstructionのみを登録するようにしています．また，33行目でフラグをtrueに変更し，34行目ではeraseFromParentメソッドで対象のInstructionを削除しています．これでrunOnFunctionの実装は完了です．

getAnalysisUsageとRegisterPassの追加

最後に，getAnalysisUsageの定義とRegisterPassも必要ですので追加しましょう．最終的なコードは以下の様になります．

リスト6.14: DCEliminatePassクラスの定義

 1: bool DCEliminatePass::runOnFunction(llvm::Function &F) {
 2:   // 対象の命令を格納するlist
 3:   std::list<llvm::Instruction *> works;
 4: 
 5:   // 最初に全ての命令を調べる
 6:   bool change = false;
 7: 
 8:   llvm::inst_iterator inst_it = llvm::inst_begin(F);
 9:   llvm::inst_iterator inst_it_end = llvm::inst_end(F);
10:   for (; inst_it != inst_it_end; inst_it++)
11:     works.push_back(&*inst_it);
12: 
13:   // worksに追加した命令からdead codeになった物がないか調べる
14:   // worksが空になるまで繰り返す
15:   llvm::Instruction *inst = NULL;
16:   while (!works.empty()) {
17:     // 命令をpop
18:     inst = works.front();
19:     works.pop_front();
20: 
21:     // この命令の値を使用している命令がある場合は生きているとする
22:     // load/store命令、call命令、終端命令(returnやbr)は生きている命令にする
23:     if (!inst->use_empty() || llvm::isa<llvm::TerminatorInst>(inst) ||
24:         llvm::isa<llvm::CallInst>(inst) || llvm::isa<llvm::LoadInst>(inst) ||
25:         llvm::isa<llvm::StoreInst>(inst))
26:       continue;
27: 
28:     // 削除する命令のオペランドがdead codeになる可能性があるので
29:     // オペランドをworksに追加する
30:     llvm::User::op_iterator op_it = inst->op_begin();
31:     llvm::User::op_iterator op_it_end = inst->op_end();
32:     for (; op_it != op_it_end; op_it++) {
33:       // 既にworksに登録済みなら何もしない
34:       llvm::Instruction *op_inst = llvm::dyn_cast<llvm::Instruction>(*op_it);
35:       if (op_inst)
36:         if (std::find(works.begin(), works.end(), &*op_inst) == works.end())
37:           works.push_back(op_inst);
38:     }
39: 
40:     // 削除する
41:     change = true;
42:     inst->eraseFromParent();
43:   }
44: 
45:   return change;
46: }
47: 
48: void DCEliminatePass::getAnalysisUsage(llvm::AnalysisUsage &AU) const {
49:   // CFGに変更を加えない
50:   AU.setPreservesCFG();
51: }
52: 
53: char DCEliminatePass::ID = 0;
54: static llvm::RegisterPass<DCEliminatePass>
55: X("dceliminate", "eliminate dead code", false, false);

今回のPassは命令の削除は実行しますが，CFGへの変更は加えないため，getAnalysisUsageメソッド内でsetPreservesCFGを呼び出しておきます．また，今回のPassはRegisterPassテンプレートにてdceliminateという名前で登録することにします．

以上で実装は完了です．今回の実装はかなり簡単に済ませてしまっている部分もありますが，今回はこれで良しとしましょう．

6.5.4 コンパイルと実行

最後にコンパイルと実行結果の確認を行いましょう．まずはコンパイルから確認します．下記コマンドにてコンパイルを行います．なお，ソースコードはdcelminate.cpp，dceliminate.hppという名前で，それぞれsrcディレクトリとincディレクトリ配下に保存されていることとします．

# dceliminate.cpp，dceliminate.hpp という名前で保存されているとする
$ g++ -g ./src/dceliminate.cpp -I./inc `llvm-config \
  --cxxflags --ldflags --libs` -ldl -pthread -c -o dceliminate.o
# -shared オプションをつけて共有ライブラリを作成
$ g++ -g -shared -o ./bin/dceliminate.so dceliminate.o

コンパイルが出来たら次は下記コマンドでPassをLLVM IRに適用します．入力するLLVM IRはリスト6.7で示した物とします．

$ opt -load ./bin/dceliminate.so -dceliminate ./sample/sample.ll -S

リスト6.15: 実行結果

 1: ; ModuleID = './sample/sample.ll'
 2: target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
 3: target triple = "i386-pc-linux-gnu"
 4: 
 5: define i32 @test(i32 %i, i32 %j) nounwind {
 6: entry:
 7:   %cmp = icmp sgt i32 %j, 0
 8:   br i1 %cmp, label %if.then, label %if.else
 9: 
10: if.then:                                          ; preds = %entry
11:   br label %if.end
12: 
13: if.else:                                          ; preds = %entry
14:   br label %if.end
15: 
16: if.end:                                           ; preds = %if.else, %if.then
17:   ret i32 0
18: }

不要だった命令が全て削除され，ret命令やbr命令とそこから参照されるcmp命令だけという非常に寂しいLLVM IRが出力されています．

6.5.5 DCEクラスを使用する

最初に無用命令の削除はLLVMでDCEクラスとして用意されているとお話しましたが，ここでその使用方法を紹介しておきます．DCEはoptコマンドに下記のオプションを与えて実行します．

$ opt -dce ./sample/sample.ll -S

実行結果として下記のLLVM IRが出力されると思います．

リスト6.16: 実行結果

 1: ; ModuleID = './sample/sample.ll'
 2: target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
 3: target triple = "i386-pc-linux-gnu"
 4: 
 5: define i32 @test(i32 %i, i32 %j) nounwind {
 6: entry:
 7:   %cmp = icmp sgt i32 %j, 0
 8:   br i1 %cmp, label %if.then, label %if.else
 9: 
10: if.then:                                          ; preds = %entry
11:   br label %if.end
12: 
13: if.else:                                          ; preds = %entry
14:   br label %if.end
15: 
16: if.end:                                           ; preds = %if.else, %if.then
17:   ret i32 0
18: }

先程と同じように不要な命令が全て削除されています．

6.6 ループの繰り返し回数のカウント

次の例として，今度はループの繰り返し回数をカウントするPassを実装してみましょう．ループの繰り返し回数は，ループアンローリング等の最適化をかけるための情報として利用できる有用な情報です．しかし一言にループと言ってもその形式(構成)は様々で，全てのループに対応するというのは難しいため，今回は入力されるLLVM IRにある程度条件を設けることで処理を簡単にしたPassを実装したいと思います．この機能もLLVMのScalarEvolutionクラスで既に用意されていますが，今回実装するPassはScalarEvolutionクラスにおける実装よりももっと限定的，かつシンプルなものにします．

6.6.1 前提条件を考える

それではまず前提条件を考えましょう．先ほども軽くふれましたが，今回は入力として想定するLLVM IRをできるだけシンプルにすることで，処理を簡単にしたPassを実装したいと思います．言語レベルで考えた場合，シンプルなループ文の例として“for(int i=定数; i<定数; i=i+定数)”という形式の，つまり下記の条件を満たすようなループがあげられると思います．

今回はこの形式のループ文を解析対象としたいと思います．しかしこれだけでは条件が不十分だと思うので，もう少し条件を追加していきましょう．

繰り返し条件以外にループを抜ける分岐が含まれると解析が面倒になります．今回は簡単にしたいのでループはヘッダからのみ抜けることとします．さらに最後にもう一つ条件を追加しておきます．

これは今までの条件と異なり，言語レベルの条件ではなくLLVM IRとしての条件です．この条件を設けることでdef-useの関係が追いやすく，実装する処理を簡単にすることができます．

解析対象のLLVM IRに対する条件は以上です．この形式のループ文は，例えば下記の様なLLVM IRになります．

リスト6.17: 単純なループ文の例

 1: ; ModuleID = './sample/loop.ll'
 2: target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
 3: target triple = "i386-pc-linux-gnu"
 4: 
 5: @.str = private unnamed_addr constant [7 x i8] c"i:%d \0A\00", align 1
 6: 
 7: define i32 @main() nounwind {
 8: entry:
 9:   br label %for.cond
10: 
11: for.cond:                                         ; preds = %for.inc, %entry
12:   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
13:   %cmp = icmp slt i32 %i.0, 10
14:   br i1 %cmp, label %for.body, label %for.end
15: 
16: for.body:                                         ; preds = %for.cond
17:   %call = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([7 x i8]* @.str, i32 0, i32 0), i32 %i.0)
18:   br label %for.inc
19: 
20: for.inc:                                          ; preds = %for.body
21:   %inc = add nsw i32 %i.0, 1
22:   br label %for.cond
23: 
24: for.end:                                          ; preds = %for.cond
25:   ret i32 0
26: }
27: 
28: declare i32 @printf(i8*, ...)

リスト6.17は制御変数を0で初期化し，ループの繰り返し毎に制御変数を1ずつ増加させながら制御変数が10未満の間printfの呼び出し処理を繰り返す，という非常に単純なループ文のLLVM IRです．今回のゴールはこのLLVM IRから繰り返し回数を抽出することにしましょう．ちなみにリスト6.17のLLVM IRは下記のソースコードをclangでコンパイルし，mem2regを適用することで生成できます．

リスト6.18: C言語でのループ例

 1: #include <stdio.h>
 2: int main() {
 3:   for (int i = 0; i < 10; i++)
 4:     printf("i:%d \n", i);
 5: 
 6:   return 0;
 7: }

6.6.2 実装方針を考える

次に実装方針を考えてみましょう．まずは，先程のループをCFGに変換し，その構成を確認しながら考えていきましょう．

リスト6.17のCFG

図6.3: リスト6.17のCFG

基本的な構成は第4章で紹介したLLVM IRと同様です．この中で大切なのはfor.condというラベルのついたBasicBlockに含まれる命令とfor.incのadd命令です．CFGからも分かる通り，このLoopにおいて繰り返し条件を含む，つまりLoopの外に抜ける命令を含むBasicBlockはfor.condです．そのBasicBlockの終端命令であるbr命令を確認すると，第一オペランドがicmp命令をさしています．このicmp命令は，“i < 10”に相当する命令ですので，オペランドには制御変数と定数があります．ここで繰り返し条件の右辺の値がわかります．次にicmp命令の第一オペランドを辿るとphi命令にたどり着きます．このphi命令では制御変数%i.0の選択を行っていますが，第一オペランドはpreheaderである%entryブロックから到達する値ですので，ここで制御変数の初期値が取得できます．また，第二オペランドはループの後処理を行う%for.incブロックのadd命令をさしています．add命令は“i++”に相当しますので，add命令の第二オペランドの定数が増分値となります．また，add命令の第一オペランドは先程のphi命令になっていることも確認できます．ループ内で制御変数に対する代入が行われていなければこのようにadd命令の第一オペランドがphi命令になっていると想定できます．

以上の内容から，今回は下記の手順でループの繰り返し回数を取得したいと思います．

  1. Loopの終了条件を含むBasicBlockを取得する
  2. 1のBasicBlockの終端命令(br命令)を取得する
  3. 2で取得した命令のオペランドからicmp命令を取得する
  4. 3のicmp命令のオペランドからphi命令と制御変数の最大値を取得する
  5. 3のicmp命令の演算子が“<”であることを確認する
  6. 4で取得した命令のオペランドからadd命令を取得する
  7. 5で取得したadd命令のオペランドがphi命令になっていることを確認する
  8. 7で取得したadd命令のオペランドから制御変数の増分値を取得する
  9. 8までで取得した値から繰り返し回数を計算する

なお，各手順において期待する命令や定数が取得できなかった場合は解析不能として終了することにします．

6.6.3 実装

本節ではループの繰り返し回数を解析するPassの実装を説明します．今回も処理毎に順を追って必要なメソッドや使用方法を説明していきます．

Passクラスの宣言

まず最初に継承するPassクラスを決定します．FunctionPassクラスを継承して内包するLoopに対して処理を行う方式でも良いかもしれませんが，今回はLoop毎に繰り返し回数を取得するだけですのでLoopPassを継承することにします．クラス名をLPCountPassとした場合の宣言例は以下の様になります．

リスト6.19: LPCountPassクラスの宣言

 1: class LPCountPass : public llvm::LoopPass {
 2: public:
 3:   static char ID;
 4:   LPCountPass() : llvm::LoopPass(ID) {}
 5:   ~LPCountPass() {}
 6: 
 7:   virtual bool runOnLoop(llvm::Loop *L, llvm::LPPassManager &LPM);
 8:   virtual void getAnalysisUsage(llvm::AnalysisUsage &AU) const;
 9: };

LoopのExitingBlockと終端命令の取得

ここからrunOnLoopメソッドの実装に移ります．runOnLoopでは最初にループの繰り返し条件を含む，つまりループから抜けるBasicBlockを取得します．これは，LoopクラスのスーパークラスであるLoopBaseクラスに定義されたExitingBlockメソッドで取得できます．llvm::LoopBase::ExitingBlockの定義は下記の通りです．

llvm::LoopBase::ExitingBlock

template<class BlockT , class LoopT>
BlockT *llvm::LoopBase<BlockT, LoopT>::getExitingBlock() const

llvm::LoopBase::getExitingBlockは対象のBasicBlockが複数あった場合はNULLを返却します．NULLが返却された場合は繰り返し条件以外にもループを抜ける処理があるということですので，今回は解析不可とします．

次に先程取得したBasicBlcok内の終端命令を取得します．BasicBlockの終端命令はgetTerminatorメソッドで取得できます．

llvm::BasicBlock::getTerminator

TerminatorInst *BasicBlock::getTerminator()

今回設けた条件により，取得した終端命令はbr命令であるはずですので，返却された命令をdyn_castテンプレートでBranchInstにキャストできるはずです．また4章で示した様にbr命令にはいくつかのフォーマットがありますが，今回のbr命令は条件文の形式になっているはずです．これはBranchInstクラスのisConditionalメソッドで確認できます．

llvm::BranchInst::isConditional

bool llvm::BranchInst::isConditional() const

isConditionalメソッドはそのBranchInstのオペランドが三つであれば，つまり条件文の場合はtrueを，そうでなければfalseを返します．ここまでの処理を実装したrunOnLoopの例は下記の様になります．

リスト6.20: LoopのExitingBlockと終端命令の取得

 1: bool LPCountPass::runOnLoop(llvm::Loop *L, llvm::LPPassManager &LPM) {
 2:   // 終了ブロックを取得
 3:   llvm::BasicBlock *exiting_block = L->getExitingBlock();
 4:   if (exiting_block == NULL)
 5:     return false;
 6: 
 7:   // 終了ブロックのTerminatorInstを取得
 8:   llvm::BranchInst *branch_inst =
 9:       llvm::dyn_cast<llvm::BranchInst>(exiting_block->getTerminator());
10:   if (branch_inst == NULL)
11:     return false;
12: 
13:   // conditionalか確認
14:   // operand数が3であるか確認してるだけ
15:   if (!branch_inst->isConditional())
16:     return false;
17: 
18:   ・・・その他の情報取得と繰り返し回数の計算処理を実装・・・
19: 
20:   return false;
21: }

繰り返し条件の取得

次に，br命令のオペランドからLoopの繰り返し条件となるicmp命令を取得したいと思います．命令のオペランドはllvm::Userクラスに用意されているgetOperandメソッドで取得できます．UserクラスはInstructionクラスのスーパークラスです．

llvm::User::getOperand

Value *llvm::User::getOperand(unsigned i) const

getOperandメソッドは引数として与えたインデックスのオペランドが取得できます．getOperandメソッドは返り値としてValueクラスのポインタを返却するので，これをdyn_castテンプレートでICmpInstにキャストします．

前節で設定した条件より，icmp命令の述語は“<”であり，第二オペランドの片方は最大値を表す定数であるはずですので，この確認をしておく必要があります．まずicmp命令の述語の種類はgetPredicateメソッドで取得できます．

llvm::CmpInst::getPredicate

Predicate llvm::CmpInst::getPredicate() const

getPredicateメソッドは該当のCmpInstの述語の種類を返却します．返り値となっているPredicateはllvm::CmpInstで定義されているenumで，第4章の表4.11，表4.12にて示したものが要素として記述されています．fcmp命令のPredicateは“FCMP_FALSE”のように接頭語として“FCMP_”を，icmp命令のPredicateは“ICMP_EQ”のように接頭語として“ICMP_”をつけて，全て大文字で定義されています．今回は“<”を期待しているので，返却されたPredicateがllvm::CmpInst::ICMP_SLTになっている必要があります．

ちなみに，icmp命令の第一オペランドはPHINodeとなっているはずですので，icmp命令取得と同時にこちらも合わせて取得することにします．ここまでの実装を組み込んだrunOnLoopは下記の様になります．

リスト6.21: runOnLoopの定義

 1: bool LPCountPass::runOnLoop(llvm::Loop *L, llvm::LPPassManager &LPM) {
 2: 
 3:   ・・・ExitingBlockとbr命令の取得・・・
 4: 
 5:   // cmp命令取得
 6:   llvm::ICmpInst *icmp =
 7:       llvm::dyn_cast<llvm::ICmpInst>(branch_inst->getOperand(0));
 8:   if (icmp == NULL)
 9:     return false;
10: 
11:   // 第二オペランドは終了値を表す定数のはず
12:   // もう片方はPHINodeを想定
13:   llvm::Value *lhs = icmp->getOperand(0);
14:   llvm::Value *rhs = icmp->getOperand(1);
15:   llvm::PHINode *phin = llvm::dyn_cast<llvm::PHINode>(lhs);
16:   llvm::ConstantInt *exit_val = llvm::dyn_cast<llvm::ConstantInt>(rhs);
17:   if (!(phin && exit_val)) {
18:     return false;
19:   }
20: 
21:   // PredicateはSLTであるはず
22:   llvm::CmpInst::Predicate pred = icmp->getPredicate();
23:   if (pred != llvm::ICmpInst::ICMP_SLT)
24:     return false;
25: 
26:   ・・・その他の情報取得と繰り返し回数の計算処理を実装・・・
27: 
28:   return false;
29: }

制御変数の初期値とLoopの後処理の取得

次に制御変数の初期値を取得したいと思います．ここで，今回の入力とするLLVM IRの制限からicmp命令から取得したphi命令で選択するValueの片方は，Loopの前処理を行うBasicBlockから到達する制御変数の初期値のはずです．phi命令が選択するValueは，getIncomingValueで取得できます．

llvm::PHINode::getIncomingValue

Value *llvm::PHINode::getIncomingValue(unsigned i) const

getIncomingValueはPHINodeで選択するValueのうち，引数に渡したインデックスのValueのポインタを返却します．初期値は定数であると仮定しているため，今回は返却された値をdyn_castテンプレートでConstantIntにキャストすれば良いでしょう．なお，今回解析対象とするLLVM IRでは，phi命令で選択するもう片方のValueはLoopの後処理に相当するadd命令となっているはずですので，こちらも合わせてgetIncomingValueメソッドにて取得することにしましょう．add命令であることの確認は，dyn_castテンプレートによるBinaryOperatorへのキャストと，llvm::BinOerator::getOpcodeメソッドによって返却される値によって確認します．

llvm::BinaryOperator::getOpcode

BinaryOps llvm::BinaryOperator::getOpcode() const

戻り値のBinaryOpsは“llvm/Instruction.h”に定義されているenumで，add命令であればllvm::Instruction::Addが返却されているはずです．その他の命令についても“llvm/Instruction.h”内にenumとして定義されているので，詳細を確認したい方は“llvm/Instruction.h”，およびここからインクルードされている“llvm/Instruction.def”(LLVM3.3では“llvm/IR/Instruction.h”になる模様)を確認すると良いでしょう．

ここで紹介したメソッドによる処理を追加したrunOnLoopは以下の様になります．

リスト6.22: runOnLoopの定義

 1: bool LPCountPass::runOnLoop(llvm::Loop *L, llvm::LPPassManager &LPM) {
 2: 
 3:   ・・・ExitingBlock，br命令，icmp命令，PHINodeの取得処理・・・
 4: 
 5:   // PHINodeのどちらかが定数であってほしい
 6:   lhs = phin->getIncomingValue(0);
 7:   rhs = phin->getIncomingValue(1);
 8: 
 9:   // phinodeのオペランドの片方が初期値
10:   // もう片方がadd命令になるはず
11:   llvm::ConstantInt *init_val = llvm::dyn_cast<llvm::ConstantInt>(lhs);
12:   llvm::BinaryOperator *bin_op = llvm::dyn_cast<llvm::BinaryOperator>(rhs);
13:   if (!(init_val && bin_op)) {
14:     init_val = llvm::dyn_cast<llvm::ConstantInt>(rhs);
15:     bin_op = llvm::dyn_cast<llvm::BinaryOperator>(lhs);
16:   }
17: 
18:   // いずれにも一致しなければ終了
19:   if ((!init_val || !exit_val)) {
20:     return false;
21:   }
22: 
23:   // add命令であることを確認
24:   if (bin_op == NULL || bin_op->getOpcode() != llvm::Instruction::Add)
25:     return false;
26: 
27:   ・・・その他の情報取得と繰り返し回数の計算処理を実装・・・
28: 
29:   return false;
30: }

制御変数の増分値の取得と繰り返し回数の計算

次の処理として先程取得したLoopの後処理に相当するadd命令から制御変数の増分値を取得しましょう．今回設けた制限より，add命令のどちらかが定数であり，その定数が増分値となっているはずです．これはgetOperandメソッドでadd命令のオペランドを取得し，dyn_castテンプレートでConstantIntにキャストすればよいでしょう．add命令の形式として，“%val = add %i, const”と“%val = add const, %i”という二つのパターンが考えられますが，今回はadd命令の第二オペランドが定数になっていると仮定して処理を進めてみましょう．この場合，getOperandメソッドを引数として1を指定して呼び出せば定数が取得できるはずです．また，Loop内の処理で制御変数への代入が行われていなければadd命令のgetOperandメソッドに引数0を指定して取得できるValueは，先程のPHINodeを指しているはずですのでこちらも合わせて確認しておくことにします．

増分値が取得できればこれまでに取得した情報と組合わせることで繰り返し回数が計算できます．ConstantIntクラスのgetZExtValueメソッドでConstantIntの値を64bitの符号無整数として取得できますので，この値を使用して計算し，llvm::errs関数で結果を出力することにしましょう．

llvm::ConstantInt::getZExtValue

uint64_t llvm::ConstantInt::getZExtValue() const

ちなみに，ConstantIntクラスのgetValueメソッドを利用すればConstantIntの値を表すAPIntを取得できますので，こちらを利用して計算しても良いでしょう．以上の処理を実装すると以下の様になります．

リスト6.23: runOnLoopの定義

 1: bool LPCountPass::runOnLoop(llvm::Loop *L, llvm::LPPassManager &LPM) {
 2: 
 3:   ・・・ExitingBlockやbr命令の取得・・・
 4: 
 5:   // %val = add %i，const の形であると仮定する
 6:   // 制御変数への代入がなければadd命令の第一オペランドは先程取得したPHINodeのはず
 7:   if (bin_op->getOperand(0) != phin)
 8:     return false;
 9: 
10:   // 第二オペランドの定数が繰り返しごとの増分値になる
11:   llvm::ConstantInt *step =
12:       llvm::dyn_cast<llvm::ConstantInt>(bin_op->getOperand(1));
13:   if (step == NULL)
14:     return false;
15: 
16:   // 初期値と終了値と増分値が得られたので繰り返し回数が得られるはず
17:   if (step->getZExtValue() == 0)
18:     return false;
19: 
20:   uint64_t result = (exit_val->getZExtValue() - init_val->getZExtValue()) /
21:                     (step->getZExtValue());
22:   if (((exit_val->getZExtValue() - init_val->getZExtValue()) %
23:        (step->getZExtValue())))
24:     result++;
25: 
26:   llvm::errs() << "loop count = " << result << "\n";
27: 
28:   return false;
29: }

getAnalysisUsageとRegisterPassの追加

最後にgetAnalysisUsageとRegisterPassを追加します．今回は入力されるLLVM IRに何も変更を加えないため，getAnalysisUsageメソッド内でsetPreservesAllメソッドを呼び出しておくべきでしょう．また，RegisterPassテンプレートでLPCountPassを“lpcount”と言う名前で登録することにします．以上を追加した最終的なソースコードは以下の様になります．

リスト6.24: runOnLoopの定義

 1: bool LPCountPass::runOnLoop(llvm::Loop *L, llvm::LPPassManager &LPM) {
 2:   // 終了ブロックを取得
 3:   llvm::BasicBlock *exiting_block = L->getExitingBlock();
 4:   if (exiting_block == NULL)
 5:     return false;
 6: 
 7:   // 終了ブロックのTerminatorInstを取得
 8:   llvm::BranchInst *branch_inst =
 9:       llvm::dyn_cast<llvm::BranchInst>(exiting_block->getTerminator());
10:   if (branch_inst == NULL)
11:     return false;
12: 
13:   // conditionalか確認
14:   // operand数が3であるか確認してるだけ
15:   if (!branch_inst->isConditional())
16:     return false;
17: 
18:   // cmp命令取得
19:   llvm::ICmpInst *icmp =
20:       llvm::dyn_cast<llvm::ICmpInst>(branch_inst->getOperand(0));
21:   if (icmp == NULL)
22:     return false;
23: 
24:   // 第二オペランドは終了値を表す定数のはず
25:   // もう片方はPHINodeであると仮定
26:   llvm::Value *lhs = icmp->getOperand(0);
27:   llvm::Value *rhs = icmp->getOperand(1);
28:   llvm::PHINode *phin = llvm::dyn_cast<llvm::PHINode>(lhs);
29:   llvm::ConstantInt *exit_val = llvm::dyn_cast<llvm::ConstantInt>(rhs);
30:   if (!(phin && exit_val)) {
31:     return false;
32:   }
33: 
34:   // PredicateはSLTであるはず
35:   llvm::CmpInst::Predicate pred = icmp->getPredicate();
36:   if (pred != llvm::ICmpInst::ICMP_SLT)
37:     return false;
38: 
39:   // PHINodeのどちらかが定数であってほしい
40:   lhs = phin->getIncomingValue(0);
41:   rhs = phin->getIncomingValue(1);
42: 
43:   // phinodeのオペランドの片方が初期値
44:   // もう片方がadd命令になるはず
45:   llvm::ConstantInt *init_val = llvm::dyn_cast<llvm::ConstantInt>(lhs);
46:   llvm::BinaryOperator *bin_op = llvm::dyn_cast<llvm::BinaryOperator>(rhs);
47:   if (!(init_val && bin_op)) {
48:     init_val = llvm::dyn_cast<llvm::ConstantInt>(rhs);
49:     bin_op = llvm::dyn_cast<llvm::BinaryOperator>(lhs);
50:   }
51: 
52:   // いずれにも一致しなければ終了
53:   if ((!init_val || !exit_val)) {
54:     return false;
55:   }
56: 
57:   // add命令であることを確認
58:   if (bin_op == NULL || bin_op->getOpcode() != llvm::Instruction::Add)
59:     return false;
60: 
61:   // %val = add %i，const の形であると仮定する
62:   // 制御変数への代入がなければadd命令の第一オペランドは先程取得したPHINodeのはず
63:   if (bin_op->getOperand(0) != phin)
64:     return false;
65: 
66:   // 第二オペランドの定数が繰り返しごとの増分値になる
67:   llvm::ConstantInt *step =
68:       llvm::dyn_cast<llvm::ConstantInt>(bin_op->getOperand(1));
69:   if (!step)
70:     return false;
71: 
72:   // 初期値と終了値と増分値が得られたので繰り返し回数が得られるはず
73:   if (step->getZExtValue() == 0)
74:     return false;
75: 
76:   uint64_t result = (exit_val->getZExtValue() - init_val->getZExtValue()) /
77:                     (step->getZExtValue());
78:   if (((exit_val->getZExtValue() - init_val->getZExtValue()) %
79:        (step->getZExtValue())))
80:     result++;
81: 
82:   llvm::errs() << "loop count = " << result << "\n";
83: 
84:   return false;
85: }
86: 
87: void LPCountPass::getAnalysisUsage(llvm::AnalysisUsage &AU) const {
88:   // 変更を加えない
89:   AU.setPreservesAll();
90: }
91: 
92: char LPCountPass::ID = 0;
93: static llvm::RegisterPass<LPCountPass>
94: X("lpcount", "lpcount pass : count loop iterate time", false, false);

以上で実装は完了です．

6.6.4 コンパイルと実行

それでは実装したPassのコンパイルと実行結果の確認を行いましょう．まず，ここまで実装したソースコードはそれぞれlpcount.cppとlpcount.hppという名前で，srcディレクトリとincディレクトリ配下に配置されていることとします．その場合，下記コマンドでコンパイルするとlibディレクトリ配下に.soファイルが出きるはずです．

# lpcount.cpp，lpcount.hppという名前で保存されているとする
$ g++ -g ./src/lpcount.cpp -I./inc `llvm-config --cxxflags \
  --ldflags --libs` -ldl -pthread -c -o lpcount.o
# -sharedオプションをつけて共有ライブラリを作成　
$ g++ -g -shared -o ./bin/lpcount.so lpcount.o

生成したPassのオブジェクトはoptコマンドでLLVM IRに適用できます．冒頭で示したLLVM IRがloop.llという名前であれば，下記のコマンドで実行できます．

# 対象のLLVM IRはloop.llという名前で保存されているとする
$ opt -load ./bin/lpcount.so -lpcount ./sample/loop.ll -S > /dev/null
loop count = 10

6.6.5 ScalarEvolutionクラスを使用する場合

最初に説明した通り，Loopの繰り返し回数の計算はLLVM のScalarEvolutionクラスに既に用意されています．ScalarEvolutionはループの帰納変数の情報などを解析するパスで，ScalarEvolutionに用意されたメソッドの一つを利用するとループの繰り返し回数を取得できます．

Passの宣言

早速ScalarEvolutionクラスを利用する場合の例を確認していきましょう．まずは実装するPassクラスの宣言ですが，これは先程と同様にLoopPassを継承することにしましょう．クラス名をSCEVSampleとした場合，例えば下記の様に宣言すれば良いでしょう．

リスト6.25: SCalaraEvolutionクラスを使用する場合の定義例

 1: class SCEVSample : public llvm::LoopPass {
 2: public:
 3:   static char ID;
 4:   SCEVSample() : llvm::LoopPass(ID) {}
 5:   ~SCEVSample() {}
 6: 
 7:   virtual bool runOnLoop(llvm::Loop *L, llvm::LPPassManager &LPM);
 8:   virtual void getAnalysisUsage(llvm::AnalysisUsage &AU) const;
 9: };

runOnLoopの実装

次にrunOnLoopの実装を見ていきましょう．今回はScalarEvolutionクラスを利用するため，まず最初にgetAnalysisUsageメソッド内でaddRequiredメソッドを利用してその旨を記述しておく必要があります．また，LLVM IRには変更を加えないため今回もsetPreservesAllメソッドを呼んでおくべきです．ついでですので，ここでRegisterPassテンプレートによるPassの登録も行っておくことにします．今回は“scevsample”という名前で登録しましょう．ここまでの内容については，特に問題ないと思いますので，まずはここまでの実装を確認しましょう．

リスト6.26: SCalaraEvolutionクラスを使用する場合の例

 1: bool SCEVSample::runOnLoop(llvm::Loop *L, llvm::LPPassManager &LPM) {
 2: 
 3:   ・・・後ほど説明・・・
 4: 
 5:   return false;
 6: }
 7: 
 8: void SCEVSample::getAnalysisUsage(llvm::AnalysisUsage &AU) const {
 9:   // 変更を加えない
10:   AU.setPreservesAll();
11: 
12:   // ScalarEvolutionを利用するのでaddRequired
13:   AU.addRequired<llvm::ScalarEvolution>();
14: }
15: 
16: char SCEVSample::ID = 0;
17: static llvm::RegisterPass<SCEVSample>
18: X("scevsample", "analyze loop trip count using scalar evolution", false, false);

次はrunOnLoopの実装です．まずはgetAnalysisUsageメソッド内で登録しておいたScalarEvolutionを取得する必要があります．これは6.3.2節で紹介したgetAnalysisメソッドを使用します．使用方法がわからない方は6.3.2節を再度確認してみてください．

次に，繰り返し回数を取得する為のScalarEvolutionクラスのメソッドを紹介します．Loopの繰り返し回数はgetSmallConstantTripCountメソッドを使用することで取得できます．

llvm::ScalarEvolution::getSmallConstantTripCount

unsigned ScalarEvolution::getSmallConstantTripCount(Loop *L,
                                                    BasicBlock *ExitingBlock)

llvm::ScalarEvolution::getSmallConstantTripCountは第一引数に対象のLoopを，第二引数にLoopから抜けるBasicBlockを指定して呼び出すと，対象のLoopの最大繰り返し回数を符号無し整数で返却します．繰り返し回数が解析できない，もしくは定数でない場合には0が返却されます．ここで，返却される繰り返し回数は第二引数で指定したBasicBlockを通って終了するという前提で計算されます．

今回の例では，第一引数にはrunOnLoopの引数で渡されるLoopを，第二引数にはそのLoopのgetExitingBlockメソッドで取得したBasicBlockを渡せば良いでしょう．今回紹介したメソッドを使用すると，runOnLoopは下記の様になります．

リスト6.27: SCalaraEvolutionクラスを使用する場合の例

 1: bool SCEVSample::runOnLoop(llvm::Loop *L, llvm::LPPassManager &LPM) {
 2:   // getAnalysisでScalarEvolutionを取得
 3:   llvm::ScalarEvolution *SE = &(getAnalysis<llvm::ScalarEvolution>());
 4: 
 5:   // ExitingBlockを取得
 6:   llvm::BasicBlock *exiting_bb = L->getExitingBlock();
 7:   if (exiting_bb == NULL)
 8:     return false;
 9:   unsigned int trip_count = SE->getSmallConstantTripCount(L, exiting_bb);
10: 
11:   llvm::errs() << "loop trip count = " << result << "\n";
12: 
13:   return false;
14: }
15: 
16: void SCEVSample::getAnalysisUsage(llvm::AnalysisUsage &AU) const {
17:   // 変更を加えない
18:   AU.setPreservesAll();
19:   // ScalarEvolutionを利用するのでaddRequired
20:   AU.addRequired<llvm::ScalarEvolution>();
21: }
22: 
23: char SCEVSample::ID = 0;
24: static llvm::RegisterPass<SCEVSample>
25: X("scevsample", "analyze loop trip count using scalar evolution", false, false);

自分で実装した場合に比べてかなりスッキリと楽に実装できてしまいましたね．

コンパイルと実行

念のため，ScalarEvolutionを利用した場合のPassについても動作確認を行っておきましょう．まず，下記コマンドでコンパイルします．これまで同様ソースコードはscevsample.cpp，scevsample.hppという名前でそれぞれsrcディレクトリとincディレクトリに配置されていることとします．

# scevsample.cpp，scevsample.hppという名前で保存されているとする
$ g++ -g ./src/scevsample.cpp -I./inc `llvm-config --cxxflags \
  --ldflags --libs` -ldl -pthread -c -o scevsample.o
# -sharedオプションをつけて共有ライブラリを作成　
$ g++ -g -shared -o ./bin/scevsample.so scevsample.o

生成したオブジェクトは，これまで同様optコマンドでLLVM IRに適用できます．

# 対象のLLVM IRはloop.llという名前で保存されているとする
$ opt -load ./bin/scevsample.so -scevsample ./sample/loop.ll -S > /dev/null
loop trip count = 10

先程と同じく繰り返し回数が出力されていることが確認できましたね．

6.7 適用されるPassを確認する

optで何らかのPassを使用する場合，実際にどのようなPassがどういった順番で実行されているか気になることもあるかと思いますが，そんなときに便利なオプションを紹介します．

optコマンドではオプションとして“-debug-pass=Structure”を指定するとパスの情報を表示できます．

# -debug-pass=Structureを指定してoptを実行
$ opt -load ./bin/easypass.so -easypass -debug-pass=Structure ./sample/test.ll -S > /dev/null
Pass Arguments:  -targetlibinfo -targetdata -easypass -preverify -domtree \
-verify -print-module
Target Library Information
Target Data Layout
  ModulePass Manager
    FunctionPass Manager
      easy pass:only print function name
      Preliminary module verification
      Dominator Tree Construction
      Module Verifier
    Print module to stderr
Function Name : test
Function Name : main
Function Name : printnum

ちなみにdebug-passにはStructure以外にも指定可能なパラメータ(デバッグレベル)が存在します．表6.1に指定可能なデバッグレベルと表示内容を示します．

表6.1: debug-passに指定可能なデバッグレベル

指定可能なデバッグレベル出力内容
Noneデバッグ表示を無効化(デフォルト値)
Argumentsoptに渡される引数，つまり実行されるパスを表示
Structureパス情報をrun()の前に表示
Executionsパスの実行と開放表示
Details実行中に詳細を表示

なお，上記表のデバッグレベルは下に行くほどより詳細であり，指定したデバッグレベル以下のレベルの情報はすべて有効になります*1．例えば，Executionsを指定した場合はArgumentsとStructureが有効になります．

[*1] もちろんNoneはのぞく