kazuk は null に触れてしまった

C# / .NET 系技術ネタ縛りでお送りしております

.NET 基礎勉強会で IL の話をしてきました


資料現物とかは以下

PowerPoint のファイル http://sdrv.ms/12Gh11k

ソースとかはこちら https://github.com/kazuk/SimpleILer/

 

比較的簡単(当社比)なコードで、 MSIL を逆アセンブル、制御フロー解析、データフロー解析をやっています。

コアロジックは Msil クラス に実装されていて、上から順に ILInstructions で命令の切り出し、GetRuns で基本ブロックに分解、PopulateControlFlowPath で制御フローパスの列挙、 SimulateEvalStack で評価スタックのシミュレーションをやり、結果として各 IL 命令のデータ依存グラフが得られます。

基本ブロック

簡単に言えば、制御構造単位での命令列です。基本ブロックでは末尾を除いて制御フロー命令が無いようになっています。また、基本ブロックの途中には飛び込まない(制御フローが飛び込む場所は基本ブロックの先頭になる)ように切り出しされます。

[制御フロー命令ではない一連の命令] optional [制御フロー命令]

制御フロー命令が無い基本ブロックの末尾には、次のブロックへの無条件分岐が暗黙に存在すると考えても一緒です。

基本ブロックを導入する事で、制御フローの列挙が非常に簡単になります。各基本ブロック内には制御フロー命令は存在しませんから基本ブロック内の命令を完全取り去って nop にしてしまっても、トポロジー的な意味でのメソッド内での制御構造は変化しません。逆にMSIL を吐き出したく、その中である程度複雑な制御トポロジーを扱いたい(=コンパイラを書きたい)なら複数の基本ブロックを作り上げてその基本ブロックを出力ILバイト列にどういう順序で出力するか、基本ブロックを接続する制御フロー命令は何を使えば良いかという順序で考える事になります。

動作フローのパス列挙

基本ブロックに分解された結果の基本ブロックの末尾命令が示すブロック間の接続を Queue を使った幅優先探索をやっています。

例外とかで飛び出す、飛び込む物を認識したい場合にはもうちょっと細工が要りますが要点は一緒です。

単純に無条件分岐なら分岐先基本ブロックが次の探索対象、条件分岐であれば条件成立時と非成立時の両方を探索するようにキューすることになります。当然に多分岐なら多分岐のすべての分岐先を探索します。

評価スタックのシミュレーションとデータフロー解析

今回の実装では評価スタックの要素型は意識していません。何個のデータを Push するかによって命令オフセットをスタックに積み、何個のデータを Pop するかにしたがって、スタックに積まれた命令オフセットを取り込んで、どの命令が積んだデータをどの命令が受け取るかという事だけを求めています。命令オフセットだけあれば再度 IL バイト列を見てあげれば実際の操作もわかるし、そのスタック要素の型も求まりますのでそこのコストが低ければ解析結果に入れる必要とか無いんじゃないのって事です。

デコンパイルやクロスプラットフォーム変換

この関係性を元に “データを受け取る IL 命令 ( データを出したIL命令 , … )” の形式で出力された構造がデモの最後に表示された変な式構造です。 IL 命令が add だったら + を二項演算子の中置記法でだすとかの判定と変換をしつこくやっていけば普通の言語での式になるでしょう。表示せずに式の木構造を何かに出せばもっとなんかできるかもしれません。(.NETの式木のノードを出力すれば式木になるでしょう) LLVM Instruction で出せばLLVMバックエンドでコンパイルできるはずでしょう。

この辺はやりたきゃどうぞの世界です。

まとめ

こんな基礎の上に .NET が乗っかってるんだって話で MSIL 読もうぜ、コードで!って話でした。

自分的には制約ソルバーとか証明って方に進んでいきたいんだけど、それをするには僕の人生ではまだ時間が足りていない感じで妄想段階を出ていませんです。

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。