第 6 章 Pass の概要と実装方法 4. runOnFunction の実行にまたがって状態を維持すること 3. ModuIe にグローバル変数の追加 / 削除を行うこと 2. M0dule に Function の追加 / 削除を行うこと 1. 現在処理中の Function 以外の Function を操作すること ドはいずれもプログラムに変更を行った場合は true を返し、それ以外の場合は false を返します。 FuncitonPass の派生クラスは次の 3 つのメソッドをオーバーロードすることができます。これらのメソッ virtual b001 doInitiaIization(Module lImv::FunctionPass::doInitiaIization ます。 dolnitialization 1 つ目のメソッドは dolnitialization メソッドです。 dolnitialization メソッドのインターフェイスを次に示し 初期化を行う場所でもあります。なお、 dolnitialization メソッドの呼び出しは、ほかのいかなる Pass の実 どを実行できるメソッドです。また、 dolnitialization メソッドは処理される Function に依存しない要素の dolnitialization メソッドは、 Function の追加 / 削除など FunctionPass で許されていない操作のほとん 行ともオーバーラップしません。 runOnFunction 2 つ目のメソッドは runOnFunction メソッドです。 します。 IIvm::FunctionPass::runOnFunction runOnFunction メソッドのインターフェイスを次に示 virtual b001 runOnFunction(Function &F) すべての FunctionPass の派生クラスは runOnFunction を実装する必要があります。通常、 Function が runOnFunction は Function ごとに呼び出されます。 Function に対する変換や解析を行うためには、 172 3 つ目のメソッドは doFinalization メソッドです。 doFinalization メソッドのインターフェイスを次に示します。 doFinalization 変更された場合に runOnFuncion メソッドは true を返します。

3.4 ツールの種類と確認 Clang の使用例 # Clang で実行ファイルを生成する場合 $ clang ー 0 hoge. 0 hoge ・ c # C1ang で VM ビットコードを出力する場合 $ clang -emit-llvm ー 0 hoge. bc hoge ・ c # C1ang でⅧアセンブリを出力する場合 $ clang -emit-llvm -S ー 0 hoge ・ 11 hoge. c 3.4.2 Ⅲ Ⅲは、 LLVM のインタブリタ兼 JIT コンパイラです。Ⅲはデフォルトでは JIT コンパイラ (Lazy) で動作 します。オプションとして -disable-lazy を指定すると、 Eager で起動できます。また、 -force-interpreter を 指定するとインタブリタとして実行します。 Ⅲの使用例 # Ⅷビットコードを作成してインタブリタで実行する場合 $ cla れ 9 -emit-llvm ー 0 hoge. bc hoge ・ c $ 11 土—force-interpreter hoge ・ bc 3.4.3 llvm-as llvm-as は、 LLVM IR のアセンプラです。 llvm-as は LLVM アセンプリを入力として受け取り、 LLVM ビットコードへ変換します。入力ファイル名が省略された場合や「 - 」が指定された場合は、標準入力の情報 を読み取ります。 llvm-as の使用例 # ソースコードを一度 VM アセンブリに変換し、Ⅷで実行 $ clang -emit-llvm -S -0 hoge. s hoge. c $ llvm-as ー 0 hoge. bc hoge ・ s $ 11i hoge ・ bc 3.4.4 Ⅱ c は、 LLVMIR を入力として受け取り、指定されたアーキテクチャのアセンプリまたオプジェクトを出力 します。アーキテクチャは - march オプションで指定できますが、指定しない場合は入力ファイルから自動 的に選択されます。オプジェクトを出力する場合は -filetype=obj を指定します。 21

第 6 章 Pass の概要と実装方法 IIIvm::AnaIysisUsage::addRequired template<class PassC1ass> AnalysisUsage & 1 ⅳ爪 : :Ana1ysisUsage: :addRequired( ) addRequired メソッドは、実装する Pass で事前に実行してほしい pass を登録するために使用します。 getAnalysisUsage メソッド内で、必要な情報を提供する pass クラスを PassClass に指定して addRequired メソッドを呼ぶことで、事前に実行しておいてほしい pass を指定できます。たとえば pass 内で Lo 叩 lnfo を利用したい場合、 getAnaIysisUsage メソッド内にリスト 6.1 のように記述します。 ・リスト 6.1 addRequired の使用例 1 void MyPass : :getAna1ysisUsage(Ana1ysisUsage &AU) const { 2 AU. addRequired く Loop 工 nfo> ( 房 また、 Pass 内で別の Pass に処理を遷移させたい場合があります。その場合は addRequired メソッドの 代わりに addRequiedTransitive メソッドを使用します。この 2 つのメソッドの違いは少々理解しづらいの ですが、何らかの Pass の実行結果にアクセスしたい場合は前者を、何らかの pass に pass としての処理 ( 計算 ) をさせたい場合は後者を使用するようです ( 使用方法はほば同一なので、詳細は省略します ) 。 なお、指定した Pass の解析情報を自身の pass で利用するには、後述する getAnalysis メソッドを利用 します。 AnalysisUsage::addPreserved く > PassManager は Pass の実行を管理し、必要のない再計算を回避します。そのために、 pass は影 響を与えないほかの Pass を明示的に指定できます。これを実現するのが、 AnalysisUsage クラスの addPreserved メソッドです。 addPreserved メソッドのインターフェイスを次に示します。 IIvm::AnaIysisUsage::addPreserved template く class PassCIass> Ana1ysisUsage & 11vm::Ana1ysisUsage::addPreserved() なお、類似のメソッドに setPreservesAll メソッドがあります。 setPreservesAll は、すべての Pass に 影響を与えないということを意味します。たとえば解析系の pass は、 setPreservesAll を使用できるはず ですまた、プログラム中の命令を変更するけれども CFG は変更しないような場合、 setPreservesCFG メ ソッドを使用できます。 178

3.3 インストール --enable-optimized を付けないと Debug でビルドされる . / llvm ー 3.2. src/configure --prefix=/usr/local/llvm --enable-optimized # 司オプションは後ろに指定した数値分並列で動作する。 # 環境に合わせて任意の値を指定 $ make —j2 # 一応テストをしてみる $ make check # インストール $ sudo make install ビルドにはそれなりの時間がかかるので、コーヒーでも飲みながら気長に待ちましよう。なお、こでは ReIease 版でビルドしていますが、 Debug 版でビルドしたい場合は configure 時のオプションを次のように 指定します。 Debug ビルドにすると、 Debugn シンボルが含められた形でコンパイルされます。 第 3 章 # デフォルトで Debug だが --disable-optimized を付けて明示的に Debug ビルドを指定 . / 11V Ⅲ -3.2. src/configure --prefix=/usr/local/llvm —-disable-optimized \ -enable-assertions --enable-debug-runtime --enable-debug-symbols Debug ビルドに失敗する場合 LLVM の Debug ビルドはかなりのメモリを消費します。そのため、メモリが不足していると OOMKiller によって make プロセスが異常終了してしまうことがあります。詳細にメモリ使用量を計測したわけではあ りませんが、最大でおおよそ 2GB 程度のメモリを使用するようなので、メモリとスワップを合わせて 3GB 程度は確保しておいたほうがよいでしよう。シグナル 9 もしくはシグナル 2 でビルドが終了してしまうこと がある場合は、 sysl 。 g ログファイルを確認することをお勧めします。メモリ不足が原因であれば、「 Out of memory 」というログメッセージを確認できるはすです。 過去の LLVM をインストールする場合の注意 通常はバージョン 3.2 をインストールすればよいのですが、何らかの理由で過去のバージョンをインストー ルする場合は注意点が 1 つあります。過去の LLVM ( 筆者は 3.0 で確認しています ) では OCaml がインス トールされていると、 make install の投入時に、 META.llvm で No rule to make target というエラーが 発生します。この場合は、次のコマンドで META. 1 ⅳ m を手動コピーする必要があります。コピー後再度 make install を投入すれば、インストールは正常に完了するはずです。 $ cp -p bindings/ocam1/11vm/META. llvm bindings/ocam1/11vm/ReIease/META. llvm 19

4.2 LLVM 旧の特徴 単純なサンプルコード ■リスト 4.1 何も考えずに中間表現に直すとそのまま代入文を繰り返せばよいわけで すが、それでは同じ変数に代入が行われ、 SSA にはなりません。 SSA 形 式で表すとリスト 4.2 のようになります。 ■リスト 4.2 単純な SSA 表現 1 xl = 嶹 2 yl = 3 x2=y1; SSA ではこのように変数にバージョン情報を付加し、同名の変数には一度しか代入が行われないように 表現します。 さて、こで問題となるのは、分岐などが存在し、変数のとる値が静的に決定できない場合です。また 実例を出して見てみましよう。今度はリスト 4.3 のようなソースコードがあったとします。 ■リスト 4.3 分岐を含むサンプルコード 2 if ( x く 10 ) { 5 else{ x = 10 ー 6 このコードでは if 文の then 節と else 節でそれぞれ x の値が定義されており、最終的に y への代入文 で x のとる値としては、 0 と 10 の 2 つのパターンが考えられます。どちらが到達するかは現段階ではわか らないので、最終的に y にどちらの値が代入されるのか決定できません。 これを解決するのが「の関数 ( phi function) 」と呼ばれるものです。リスト 4.3 のコードをの関数を利用 した SSA で表した場合のイメージを図 4.1 に示します。ゆ関数は、参照する定義が複数存在する場合に、 どの制御フローを通過したかによって適切な値を選択する関数です。つまり、先の例では、ゆ関数は x が 10 より小さい場合は then 節の x の値を選択し、 x が 10 以上の場合は else 節の x の値を選択します ( な んだかしつくりこないかもしれませんが、そういうものです ) 。 0 第 4 章

6.6 ループの繰り返し回数のカウント 6.6.5 ScaIarEvoIution クラスを使用する場合 前述したように、 Lo 叩の繰り返し回数の計算は LLVM の ScaIarEvoIution クラスにすでに用意されてい ます。 ScaIarEvoIution はループの帰納変数の情報などを解析するパスで、 ScaIarEvoIution に用意された メソッドの 1 つを利用するとループの繰り返し回数を取得できます。 Pass の宣言 さっそく ScalarEvolution クラスを利用する場合の例を確認していきましよう。まずは実装する Pass クラ スの宣言ですが、これは先ほどと同様に Lo 叩 pass を継承することにします。クラス名を SCEVSampIe と した場合、たとえばリスト 6.25 のように宣言します。 ■リスト 6.25 SCaIaraEvolution クラスを使用する場合の定義例 1 class SCEVSampIe : public 11V 爪 : :LoopPass{ 2 3 4 5 6 7 8 public: static char 工 D; SCEVSamp1e( ) : llvm: :LoopPass ( (D) { } -SCEVSamp1e( ) { } virtual b001 run0nLoop ( 11V Ⅲ : : LOOP *L' llvm: : LPPassManager & も P virtual void getAna1ysisUsage(llvm: :Ana1ysisUsage &AU) const; runOnLoop の実装 次に runOnLo 叩の実装を見ていきましよう。今回は ScalarEvolution クラスを利用するので、最初に getAnalysisUsage メソッド内で addRequired メソッドを利用してその旨を記述しておく必要があります。 また、 LLVM IR には変更を加えないため、今回も setPreservesAll メソッドを呼んでおくべきです。 ーーで RegisterPass テンプレートによる pass の登録も行っておくことにしましよう。今回は ついでに 「 scevsample 」という名前で登録することにします。 こまでの内容については特に問題ないでしよう。ますはここまでの実装を確認します ( リスト 6.26 ) 。 1 b001 SCEVSampIe : : runOnLoop ( 11V 爪 : : LOOP ′ 11V 爪 : : LPPassManager &LPM) { ■リスト 6.26 SCalaraEvoIution クラスを使用する場合の例 2 3 4 5 7 ・・・後ほど説明・・・ return false; 8 void SCEVSamp1e: :getAna1ysisUsage(llvm: :AnalysisUsage &AU) const{ / / 変更を加えない 9 207

7.12 AsmPrinter の実装 オプジェクトの出力を行います。その過程でどのようなクラスを利用しているかを知っておくとわかりやすい でしよう。 AsmPrinter パス ( クラス ) に関連するクラスを図 7.4 に示します。 AsmPrinter クラスは Machine FunctionPass を継承したパスとなります。 SampIeAsmPrinter クラスは AsmPrinter クラスを継承し、必 要に応じてメソッドをオーバーライドして実装することにより、ターゲット固有の処理を実現しています。 MachineFunctionPass <—AsmP 「 inte 「← SampleAsmP 「 inte 「 ↑ MCStreame 「 SampIeMCInstLowe 「 MCAsmStreame 「 オプジ土クト生畆 アセンプリ生成 MCObjectSt 「 eame 「 4 MCELFSt 「 eame 「 MCAssemble 「 --> MClnstP 「 inte 「 SamplelnstPrinter --> MCObjectWrite 「 WinCOFFObjectWrite 「 MachObjectW 「 iter ELFObjectWriter -+MCELFObjectTargetW 「 ite 「 SampIeELFOb)ectW 「 ite 「 卞 MCCodeEmitte 「 SampleMCCodeEmitte 「 ま MCAsmBackend sampleAsmBackend ・図 7.4 AsmPrinter のクラス図 AsmPrinter クラスの内部では MCStreamer クラスを持っており、アセンプリ出力やオプジェクト出力 は MCStreamer クラスが担当します。 MCStreamer が扱うのは MC Layer となるので、 AsmPrinter 側 で MachineCode から MC Layer への Lowering をする必要があります。 Lowering の処理は Sample MCInstLower クラスで行います。 MCStreamer の種類 ( 子クラス ) としては 2 種類あり、アセンプリ生成の場合は MCAsmStreamer ク ラス、オプジェクト生成の場合は MCObjectStreamer クラスを使います。オプジェクト生成においても、 ELF ファイル生成の場合は MCObjectStreamer の子クラスである MCELFStreamer クラスを使います。 MCAsmStreamer クラスは MCInstPrinter クラスを操作してアセンプリ生成を行います。また、 MCCodeEmitter クラスと MCAsmBackend クラスが実装されている場合は、これらのクラスを利用して アセンプリ生成時に機械語も出力します。 第 7 章 263

5.13 CommandLine ライブラリ clEnumVal マクロは第 1 引数に enum を指定し、第 2 引数にそのオプションの説明を表す文字列を渡し ます。 clEnumVal では第 1 引数で指定した enum の名前がオプション名として使用されます。 cIEnumVaIN オプションも cIEnumVaI とよく似たマクロですが、こちらは enum の名前とオプション名が 異なる場合に使用します。 clEnumValN は第 1 引数に enum をとり、第 2 引数にオプション名を指定しま す。第 3 引数は該当オプションの説明となります。 なお、 llvm::cl::values の引数の最後には必ず cIEnumVaIEnd を指定しなければならないことに注意して ください。 それでは、実行結果の確認をしておきましよう。 # cltes し cpp という名前のソースコードの場合のコンバイル $ 9 + 十一 9 cltest ・ cpp 、 llvm-config --cxxflags -ldflags ー 0 cltest # 最適化オプションの確認 $ . /cltest ー 00 disable Optimization # help の表示 $ . /cltest -help OVERV 工 EW: CommandLine Samp1e -pthre ad \ ー 1d1 ー 1 土 bs 、 ÜSAGE : cltest [ options ] OPT 工 ONS : 最適化レベルの選択 ー最適化しません -00 ー基本的な最適化 -01 ー積極的な最適化 ー 02 ーさらに積極的な最適化 -03 Disp1ay available options ( -help-hidden f0 て more ) -help Disp1ay the version Of this program —versxon 第 5 章 llvm::cl::values を使用した場合、 llvm::cl:: 叩 t に渡した llvm::cl::desc の内容がトップレベルに表示され、 その下に llvm: ℃ l::values に渡した各オプション名とその説明が出力されます。今回の例では各最適化オプ ションのオプション名と説明が示されていることがわかります。 5.13.3 1 つのオプションで複数の値を受ける DummyC においては入力ファイルは 1 つのみとしていますが、場合によっては複数のファイルを受け取 りたいこともあるでしよう。こでは 1 つのオプションに複数の値を受け取りたい場合の CommandLine ラ イプラリの使用方法を紹介します。 165

第 5 章 20 22 23 24 26 27 28 29 30 32 33 フロントエンドの作成 / / 工ラーメッセージを出して NULL を返す fprintf( stderr, "Function : %s is redefined" SAFE—DELETE ( proto return NULL ー ′ prot0->getName ( ) . c—str ( ) / / ( 関数名ー引数 ) のペアをプロトタイプ宣言テーブル (Map) に追加 PrototypeTab1e [ proto->getName ( ) ] =proto->getParamNum( 房 Tokens—>getNextToken ( return proto ー }else{ SAFE—DELETE ( pro セ 0 Tokens->app1yTokenIndex ( bkup return NULL ー 34 } まず visitFunctionDeclaration では、 16 行目で PrototypeTable を参照し、新しく解析した関数がすで に宣言されているかを確認しています。 17 、 18 行目では同様に FunctionTabIe を参照しており、関数が定 義済みであるか、定義済みの場合は引数の数が合っているかを確認しています。この処理によって再定義 と判断された場合はエラーメッセージを出力して NULL を返します。新規に宣言された関数の場合は、 26 行目で PrototypeTable に関数名、引数の数のペアを追加します。 続いて visitFunctionDefinition を修正します。 visitFunctionDefinition に追加したい処理は次のとおり る処理 です。 ・関数がプロトタイプ宣言されていた場合、プロトタイプ宣言と関数定義の引数の数が同一であることを確認す ・リスト 5.26 意味解析を実装した visitFunctionDefinition に示します。 これらの処理を追加したテープルを用いて実装します。修正後の visitFunctionDefinition をリスト 5.26 ・同名の関数が複数定義されていないことを確認する処理 2 3 4 5 6 7 8 9 100 * FunctionDefinition 用構文解析メソッド * @return 解析成功 : FunctionAST 解析失敗 : NULL FunctionAST *Parser: :visitFunctionDefinition( ) { int bkup=T0kens->getCurIndex ( PrototypeAST *proto=visitprototype ( ); if( !proto){ return NULL ー

6.3 Pass に実装すべきその他のもの ー 6.3 pass に実装すべきその他のもの 前節の冒頭で少し触れましたが、ユーザは先ほど説明した Pass のうち、自分の実装したいものに合わ せて Pass を選択し、継承します。たとえばループに対して何か処理したければ、 Lo 叩 Pass を継承するこ とで LLVM IR の Loop ごとに runOnLoop メソッドが呼ばれます。 BasicBIockPass なら BasicBlock ごと、 FunctionPass なら Function ごとに runOnXX メソッドが呼ばれます。 基本的には dolnitalization で初期化処理を行い、 runOn メソッドに目的の処理を記述し、 doF ⅲ alization で終了処理という形になるでしよう。しかし、 pass の実装にはほかにもいくつか実装すべき 抽象メソッドやテンプレートが存在します。本節ではそれらの pass の実装に必要な事項を説明します。 6.3.1 Pass::getAnaIysisUsage メソッド 最初に pass クラスの getAnalysisUsage メソッドを紹介します。 getAnalysisUsage メソッドは、次のよ うに定義されている抽象メソッドです。 llIvm::Pass::getAnalysisUsage virtual VOid getAnalysisUsage(AnalysisUsage & 工 nfO) 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 く > 1 つ目のメソッドは AnaIysisUsage::addRequired メソッドです。 addRequired メソッドのインターフェイ スを次に示します。 第 6 章 177