FPGA開発日記

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

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

LLVM

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

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

いくつかのPassについて。CallGraphSCCPassクラス、FunctionPassクラス、LoopPassクラス。

llvm.org

LLVMのPassを書く

CallGraphSCCPassクラス

CallGraphSCCPassはpassがプログラムの呼び出しグラフを下から上にする必要があるときに使用する(呼び出し先から呼び出し元へ)。 CallGraphSCCPassはCallGraphを作成するメカニズムを提供するが、システムがCallGraphSCCPassの最適化実行も許す。 あなたのpassが以下のアウトラインに示す要件に合致し、FunctionPassの要件に合致しないならば、CallGraphSCCPassから派生させるべきです。

TODO: SCCとは何か、Tarjanのアルゴリズム、B-U meanについて説明する。

CallGraphSCCPassサブクラスについてその役割を明確にすると:

  1. 現在のSCCおよびSCCの直接呼び出し元と直接呼び出し先以外の関数を検査したり変更したりすることはできません。
  2. 現在のCallGraphオブジェクトを保存し、プログラムに加えられた変更を反映して更新することが求められる。
  3. SCC の内容を変更することはできても、現在のモジュールに SCC を追加したり削除したりすることはできない。
  4. 現在のモジュールにグローバル変数を追加・削除することができる。
  5. runOnSCC の起動に関わらず、状態を維持することができる(グローバルデータを含む)。

Note: SCCって何? --> "Strongly Connected Component"

SCCを1つ以上のノードで管理しなければならないため、CallGraphSCCPassを実装するのは、いくつかの場合において非常にトリッキーです。 以下で説明するすべてのバーチャルメソッドでは、プログラムを変更した場合にはtrueを、そうでない場合はfalseを返す必要があります。

doInitialization(CallGraph &)メソッド

virtual bool doInitialization(CallGraph &CG);

doInitiazilationメソッドはCallGraphSCCPassが許可していないことのほとんどを許可するメソッドである。関数の追加や削除、関数のポインタの取得などが行えます。doInitializatoinメソッドは処理されるSCCに依存しない単純な初期化などに使用されます。doInitilizationメソッドは他のpassの実行とオーバラップしないようにスケジュールされます(従ってこのメソッドは非常に高速であるべきです)。

runOnSCCメソッド

virtual bool runOnSCC(CallGraphSCC &SCC) = 0;

runOnSCCメソッドはpassの最も興味のある動作を行う場所です。モジュールが変換により変換された場合はtrueを返し、そうでない場合はfalseを返すべきです。

doFinalization(CallGraph &)メソッド

virtual bool doFinalization(CallGraph &CG);

doFinalizationメソッドは、passのフレームワークがコンパイルされるプログラムのすべてのSCCに対してrunOnSCCを呼び終わった後に呼び出されます。

FunctionPassクラス

ModulePassサブクラスと対比して、FunctionPassサブクラスは予測可能な、システムによって予測可能な動作を持っている。すべてのFunctionPassはプログラム中の関数を独立に実行する。FunctionPassは特定の順序で動作する必要はなく、FunctionPassは外部の関数を変更しない。

明確化するために、FunctionPassサブクラスは以下を許可しない：

  • 現在処理されているFunction以外の関数を検査や変更すること
  • 現在のModuleから関数を追加もしくは削除すること
  • 現在のModuleからグローバル変数を追加または削除すること
  • runOnFunctionの起動の状態を操作すること(グローバルデータを含む)

FunctionPassの実装は通常は単純です("Hello World"passの例を参照のこと)。FunctionPassは3つのバーチャルメソッドをオーバロードする。すべてのメソッドは、プログラムを変更した場合にはtrueを返す必要があり、そうでない場合はfalseを返す。

doInitialization(Module &) メソッド

virtual bool doInitialization(Module &M);

このdoInitializationメソッドはFunctionPassが許可しない殆どの操作を行うことができます。関数の追加削除や、関数のポインタの取得などが行えます。このdoInitializationメソッドは処理する関数に依存しないタイプの様々なことを簡単に初期化するために設計されています。 doInitializationメソッドは他のpassとオーバラップして呼び出されるようにはスケジュールされていません(従って非常に高速であるべきです)。

このメソッドの使い方の良い例としてLowerAllocationpassがあります。 このpassはmallocとfree命令をプラットフォームに依存するmalloc()とfree()関数呼び出しに置き換えます。 doInitializationメソッドではmallocとfree関数への参照を取得し、必要ならばモジュールにプロトタイプを追加します。

runOnFunctionメソッド

virtual bool runOnFunction(Function &F) = 0;

runOnFunctionメソッドはpassによる変換や解析処理を行うために実装する必要があります。 通常は、関数が変更されたらtrueを返します。

doFinalization(Module &)メソッド

virtual bool doFinalization(Module &M);

doFinalizationメソッドはあまり使われませんが、passのフレームワークが、コンパイルされるプログラムに対してすべてのrunOnFunctionの呼び終えた後に呼び出されます。

LoopPassクラス

LoopPassクラスは関数内の独立したループに対して適用されます。LoopPassはネストされた順番に実行され、つまり最も上位のループが最後に実行されます。

LoopPassサブクラスはLPPassManagerインタフェースを通じてループネストをアップデートすることが許可されています。loop passを実装することは通常は単純です。LoopPassは3つバーチャルメソッドをオーバロードする必要があります。すべてのこれらのメソッドは、プログラムを変更した場合はtrueを返し、そうでない場合はfalseを返すべきです。

LoopPassサブクラスは、同じ関数の解析を実行するメインのループパスパイプラインの一部として実行するように意図されています。これを簡単にするために、LoopUtils.hにはgeTLoopAnalysisUsage関数が提供されています。これはサブクラスのgeTAnalysisUsageのオーバライドの中で呼び出すことが出来、一貫性と正しい動作を行うために必要です。同様に、INITIALIZE_PASS_DEPENDENCY(LoopPass)はいくつかの関数の解析を初期化します。

doInitialization(Loop *, LPPassManager &)メソッド

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

doInitializationメソッドは処理する関数に依存しない簡単な初期化を実行します。doInitializationメソッドは他のpassと実行がオーバラップしないようにスケジュールされます(従って、この関数は素早く処理を終える必要があります)。LPPassManagerインタフェースはFuncitonとModuleレベルの解析情報にアクセスするために使用します。

runOnLoopメソッド

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

runOnLoopメソッドは、サブクラス内、変換及び解析を行うために実装しなければならないメソッドです。通常、関数が変更された場合にはtrueを返す必要があります。LPPassManagerインタフェースはループネストをアップデートするために必要です。

doFinalizationメソッド

virtual bool doFinalization();

doFinalizationメソッドはあまり使われることのないメソッドですが、passフレームワークが、コンパイルされるプログラム内のすべてのループに対してrunOnLoopの呼び出しを終了すると呼び出されます。

RegionPassクラス

RegionPassはLoopPassと似ていますが、関数内のエントリから終了までを実行します。RegionPassはその領域をネスト順に実行し、もっとも外側の領域が最後に処理されます。

RegionPassサブクラスはRGPassManagerインタフェースを使って領域ツリーを更新することが許されています。RegionPass内の3つのバーチャルメソッドをオーバロードして独自のリージョンpassを実装することができます。これらのメソッドは、プログラムを変更した場合にはtrueを返す必要があります。

doInitialization(Region *, RGPassManager &)メソッド

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

doInitializationメソッドは処理される関数に依存しない簡単な初期化などを行うためのものです。doInitializationメソッドは他のpassの実行とオーバラップしないようにスケジュールされます(したがって高速に動作する必要があります)。RPPassManagerインタフェースはFunctionもしくはModuleレベルの解析情報にアクセスするために必要となります。

runOnRegionメソッド

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

runOnRegionメソッドは、変換や解析などの実行するために必要な関数です。通常、その領域を変更した場合にはtrueを返します。RGPassManagerは領域ツリーをアップデートするために必要です。

doFinalization()メソッド

virtual bool doFinalization();

doFinalizationメソッドはあまり使われることのないメソッドで、コンパイルされるプログラムのすべての領域に対してrunOnRegionが実行された後に呼び出されます。

MachineFunctionPassクラス

MachineFunctionPassはLLVMコードジェネレータの一部で、プログラム中のマシンに依存する表現に対して実行されるものです。

コードジェネレータpassはTargetMachine::addPassToEmitFileにより特別に登録され初期化されます。従ってこれらは一般的にoptやbugpointコマンドによって実行することはできません。

MachineFunctionPassはFunctionPassでもあります。したがってFunctionPassのすべての制約はMachineFunctionPassにも当てはまります。MachineFunctionPassは以下のことが許可されていません:

  1. LLVM IRのInstruction, BasciBlock, Argument, Function, GlobalVariables, GlobalAlias, Moduleの作成または変更
  2. 現在処理しているMachineFunction以外のMachineFunctionの変更
  3. runOnMachineFunctionの起動を促すステートの調整 (グローバルデータも含む)

runOnMachineFunction(MachineFunction &MF) メソッド

virtual bool runOnMachineFunction(MachineFunction &MF) = 0;

runOnMachineFunctionはMachineFunctionPassのメインのエントリポイントと考えることができます; つまり、このメソッドをオーバライドしてMachineFunctionPassを実装することができます。