ただの素人がフロー解析を通過した – 言語実装 Advent Calendar 2017

この記事は「言語実装 Advent Calendar 2017」の11日目のネタです。

今、私は「IL2C」 というプロジェクトをやっているのですが、その実装中に起きた予期せぬフロー解析を、素人なりに実装した話です。IL2Cについては以下を参照してもらえればわかりますが、.NETのIL (Intermediate Language) を、C言語ソースコードに変換します。

GitHub: IL2C step-by-step design project
YouTube: Playlist: Making archive IL2C

「AOT技術 Advent Calendar 2017」でもこれまでの内容を要約して書いてます。この記事はダブルエントリーにしました。

また、「Extensive Xamarin」 でその時点までの技術的なポイントを執筆したので、興味があれば参照して下さい… いや、買って下さい :)

※本記事は抜粋ですが、.NETにあまり明るくない方向けに、細部を省いて焦点に絞って編集してあるため、省略した解説があります。


厨二変換病

私は、IL2Cを実際に作り始めるまでは、こう考えていた —

(ゲームエンジンの)Unityには、”IL2CPP”というツールがあります。IL2CPPとは、.NETのIL(Intermediate Language)を、C++のコードに変換するツールです。ILとは、JavaのバイトコードやLLVM-IRに相当する、.NETの中間言語です。

“IL2CPP”と聞けば、ILのバイトコードを(多少面倒ではあるものの)パースし、一対一でC++のコードに変換していけば完成し、後は、ランタイムをどう実装するのかが大きなトピックだろうと想像できます。

プリミティブタイプは、C++の対応する型に置き換えればよいでしょう。.NET CLRが扱うクラスや構造体の型は、C++のクラスにマッピング出来そうな気がします。

型全体について、System.Object(.NETにおける基底クラス)と同じような基底クラスを軸に、C++でも継承関係を構築すれば、例外クラスもほぼそのまま変換できるように思えます。しかも、C++にはtry-catchが存在するため、例外ハンドリングも楽に実装できるかもしれません。

そして、C++で記述できるコードは、多少冗長になったり面倒になったりしますが、C言語だけでも実装できることを知っています。むしろツール化によって自動生成するのであれば、C言語で出力することは大した問題ではありません。

大きな問題があるとすれば、ガベージコレクションとスレッド周りですが、これらは主にランタイムとの協調が主軸となります —

しかし、IL2Cの設計を進めていくうちに、型の扱いがそれほど簡単でもないことに気が付いた…

立ちはだかる様々な問題のうち、全く想定していなかった「フロー解析」についての知見を残しておきます。同じような事を妄想しちゃった仲間のために :)


.NET CLR評価スタック

.NETのランタイムのことを、「.NET CLR」と呼びます。CLRには仮想計算器が定義されています。この計算器(CPUと読み替えてよい)は、ILのバイトコードを逐次解釈しながら、OpCodeの定義に従った計算を実行します。CLRの仮想計算器は「スタックマシン」と呼ばれている種類のアーキテクチャです。

スタックマシンとは、仮想計算器が使用するスクラッチパッドに、文字通り「スタック」構造のバッファを使います。このスタックのことを「評価スタック」と呼んでいます。例えば、以下のような3つの引数の値を加算するメソッドを見ます:

.method public hidebysig static 
    int64 Add (uint8 a, int32 b, int64 c) cil managed 
{
    ldarg.0     // (1)
    ldarg.1     // (2)
    add         // (3)
    conv.i8     //  |  (expand int32 --> int64)
    ldarg.2     // (4)
    add         // (5)
    ret         // (6)
}

これを、「擬似的」にC++ STLで書いてみます:

int64_t Add(uint8_t a, int32_t b, int64_t c)
{
    // The evaluation stack
    std::stack<object> stack();

    stack.push_back(a);   // (1)
    stack.push_back(b);   // (2)

    // (3)
    stack.push_back((int64_t)(stack.pop_back() + stack.pop_back()));

    stack.push_back(c);   // (4)

    // (5)
    stack.push_back(stack.pop_back() + stack.pop_back());

    // (6)
    return (int64_t)stack.pop_back();
}

評価スタックとは「スタック」と呼ばれるように、LIFO構造のスクラッチパッドです。ポイントは、評価スタックが「スタック」ゆえに、必ずスタックに積まれた順序を守りながら操作するということです。この点は、一般的な物理CPU、たとえばx86・x64・ARMなどのCPUと異なります。これらのCPUは「レジスタ」と呼ばれるスクラッチパッドを使い、評価スタックのようにLIFOであることを想定しません。

また、評価スタックにはどのような値も入れることが出来ます。プリミティブ型・値型・オブジェクト参照・マネージ参照などです。

以下に評価スタックの処理を示します:

  1. aの値を評価スタックにプッシュ
  2. bの値を評価スタックにプッシュ
  3. 2つの値を取り出し(ポップ)ながら加算処理を行い、結果をプッシュ
  4. cの値を評価スタックにプッシュ
  5. 2つの値を取り出し(ポップ)ながら加算処理を行い、結果をプッシュ
  6. 値を取り出し(ポップ)、呼び出し元に返す

評価スタックの正体

このC++コードには、明らかに問題のありそうな実装が含まれています。もう一度、ILと対応するC++コードを示します:

.method public hidebysig static 
    int64 Add (uint8 a, int32 b, int64 c) cil managed 
{
    ldarg.0     // uint8 a
    ldarg.1     // int32 b
    add
    conv.i8     // int32 --> int64
    ldarg.2     // int64 c
    add
    ret         // int64
}
int64_t Add(uint8_t a, int32_t b, int64_t c)
{
    // First problem: cannot declaration object type using C++
    std::stack<object> stack();

    stack.push_back(a);
    stack.push_back(b);

    // Second problem: cannot find operator +() overload
    stack.push_back(stack.pop_back() + stack.pop_back());

    stack.push_back(c);

    // Third problem: cannot find operator +() overload
    stack.push_back(stack.pop_back() + stack.pop_back());

    return (int64_t)stack.pop_back();
}

まず、std::stackのテンプレート型引数”object”が解決できません。つまり、C++にはSystem.Object(.NETにおける基底クラス)に対応するクラスが存在しないため、このコードは成り立ちません。(関連して、operator +()が解決できないという問題も存在します)

仮に、全ての型の基底となるクラスを導入すれば解決できそうな気もします(同程度の新たな問題も発生しますが、ここでは述べません)。しかし、私達の目標はC++ではなくCです。C言語で上記のコードを模倣する場合、次の方法が考えられます:

  1. std::stackと等価な、テンプレートクラスベースではないスタック操作関数を用意する
    この方法は、スタックポインタの操作(現在のスタック位置を把握する)を実装する必要があり、Cコンパイラが最適化によってこれらを不要と検出できるかどうかが鍵となります(実際のところ、スタックポインタの計算処理が含まれるため、難しいかもしれません)。しかし、結局、System.Object型をC言語でどのように扱うのかが解決されません。
  2. スタックに値が2個しか出し入れされていない前提で、それぞれをローカル変数に置き換える
    「人間の目」で確認すれば、評価スタックのインデックス(スタックに積まれた位置)毎に、何型の値を格納しているのかがわかります。

次のILの例では:

ldarg.0     // [0] int32
ldarg.1     // [1] int32    (A)
add         // [0] int32    (B)
conv.i8     // [0] int64    (C)
ldarg.2     // [1] int64    (D)
add         // [0] int64    (E)

OpCode実行後のスタックの位置とその型が定められているため、この情報を使って、次のようなCコードに変換できます:

// Evaluation stack simulated by C
int32_t stack0_0;
int32_t stack1_0;
int64_t stack0_1;
int64_t stack1_1;

// ldarg.0
stack0_0 = a;
// ldarg.1  (A)
stack1_0 = b;

// add      (B)
stack0_0 = stack0_0 + stack1_0;

// conv.i8  (C)
stack0_1 = stack0_0;

// ldarg.2  (D)
stack1_1 = c;

// add      (E)
stack0_1 = stack0_1 + stack1_1;

// ret
return stack0_1;

評価スタックの使われ方を図示すると、次のようになります:

これで、評価スタックをCコードで問題なくシミュレートできたことになります。出力されるコードの問題自体は解決しましたが、IL2Cの変換処理は非常に複雑になります。当初の想定では、リフレクションAPIで取得できるメタデータ情報とILのバイトコードを、逐一Cコードに置き換えるだけでした。

たとえば、メソッドの引数群・戻り値・ローカル変数群の型は、Typeクラスのインスタンスによって直接かつ容易に特定できます。しかし、評価スタックの操作だけは、型が明示的に指定されない(PushやPop時に型指定されない)ため、PushやPop操作を追跡し、どこでどのスタック位置をどのように使っているか、を解析しなければならないのです。


評価スタック解析の方法

ILのバイトコードを上から順に解析するのではなく、評価スタックの操作を追跡して解析しなければならないとすると、実際に仮想計算器が解析を行う挙動を模倣する必要があります。具体的には、バイトコードのエントリポイント(先頭)から順に解析を行いつつ、

  1. OpCodeのPushやPopの操作を追跡する(その際に、Pushされた型を記憶する)
  2. ブランチ命令を発見した場合は、ブランチ先を新たなフローとしてキューに保存する
  3. ret命令や、解析済みのバイトコードに到達した時点で、そのフロー解析を終了する

という動作を、キューを全て消費するまで繰り返します。ここで重要なのは、評価スタックの使用方法のチェックです。

ブランチ命令によって遷移する先のバイトコードは、すでにフローとして解析済みの可能性があります。その場合、そこから先で使用(Pop)する予定のスタックの型が、ブランチ直前のスタックの型と一致していれば、Cコード上でもまったく同じコードが使用可能であるとみなせます。しかし、スタックにPushされている値の型が異なる場合、ブランチ元で想定される型で新たにCコードを出力しなければなりません。次のコードは、手動で技巧的なILを構成した例です:

// Handmade IL code
.method public hidebysig static 
    native int Multiple10 (native int a) cil managed 
{
    .locals (
        [0] int32 count
    )

    ldc.i4.s 10
    stloc.0
    ldc.i4.0            // [0] int32   (A)

L_0000:
    ldarg.0             // [1] native int
    add                 // [0] native int  (B)
    ldloc.0
    ldc.i4.1
    sub
    stloc.0
    ldloc.0
    brtrue.s L_0000     // (C)

    ret
}

OpCodeの”add”命令は、次のような評価スタックの入力を受け付けます(他にもバリエーションがありますが省略します):

  1. int32 + int32 → int32
  2. int64 + int64 → int64
  3. int32 + native int → native int
  4. native int + native int → native int

native intとは、”System.IntPtr”のことです。これは32ビット環境では32ビット値、64ビット環境では64ビット値を保持します。(但し、現在のIL2Cは、まだnative intをサポートしていません)

ここで問題なのは、(B)で計算されるadd命令が、初回は(A)により3)であり、次回以降が4)として処理されることです。こういったコードはC#では書くことができませんが、ILとしては有効です。上記の判定は、ILのバイトコードをデコードした、静的な情報だけではわからないため、フローを解析し、

  1. 最初のフローで(A)によって、スタック[0]位置がint32として扱われていること
  2. (C)のブランチによってL_0000へ遷移する新たなフローが発生し、かつ、その際のスタックの使用状況がint32→native intと変わっていること
  3. (C)のブランチが条件を満たさない場合の、後続のフローが存在すること

を判断し、特に2)によって、「似たような、しかし異なるCコードを生成する必要」を判断します。

結果として、次のようなCのコードを出力します:

intptr_t Multiple10 (intptr_t a)
{
    int32_t count;

    int32_t stack0_0;
    intptr_t stack0_1;
    int32_t stack1_0;
    intptr_t stack1_1;
    int32_t stack2_0;

    stack0_0 = 10;
    count = stack0_0;

    stack0_0 = 0;

    stack1_1 = a;
    stack0_1 = stack0_0 + stack1_1;     // (D)

    stack1_0 = count;                   // ---+
    stack2_0 = 1;                       //    |
    stack1_0 = stack1_0 - stack2_0;     //    |
    count = stack1_0;                   //    | (F)
                                        //    |
    stack1_0 = count;                   //    |
    if (stack1_0 != 0) goto L_0000      //    |
                                        //    |
    return stack0_1;                    // ---+

L_0000:
    stack1_1 = a;
    stack0_1 = stack0_1 + stack1_1;     // (E)

    stack1_0 = count;                   // ---+
    stack2_0 = 1;                       //    |
    stack1_0 = stack1_0 - stack2_0;     //    |
    count = stack1_0;                   //    | (F)
                                        //    |
    stack1_0 = count;                   //    |
    if (stack1_0 != 0) goto L_0000      //    |
                                        //    |
    return stack0_1;                    // ---+
}

(D)と(E)によって、スタック[0]に想定される型が異なるのがわかりますか? C言語では、ローカル変数に型を指定しなければなりません。同じスタック位置でも異なる型を必要とする場合は、
その変数を使用する全ての箇所で、ソースコードを再生成する必要があります。

但し、(F)の部分は完全に同一なので、ラベルとgotoを駆使することで共通化できる可能性があります。(現在のIL2Cはその検知を行っていません。判定は複雑ではなさそうですが、難易度は高いと思います。また、ただgotoで遷移させただけだと、可読性が極端に低下する可能性があります)

まとめ

.NET ILのメタデータには、.NETの型情報が全て含まれています。リフレクション(やメタデータを解析するサードパーティのライブラリ)を使用すれば、型の情報は容易に引き出すことが出来ます。これによって、フィールドの型・メソッドの戻り値の型・メソッド引数群の型・ローカル変数群の型など、あらゆる型を直接特定できます。しかし、評価スタックの各スロットに格納される値の型については、どのような型が格納されるのかを静的に定めることが出来ません。

IL2Cでは、IL内での評価スタックの使われ方を解析して、評価スタックのスロットにどんな型を想定しうるかを調べています。そして、その情報を元に、完全に静的に定める必要のあるC言語向けに、型ごとのコード生成を行っています。

当初はこのような事を考えていなかったので、必要性を知ったときには「これは大変そうだ」と思いましたが、何とか乗り切ったので良かったです。

Making archive IL2C #6-28 … 30

この記事は「AOT技術 Advent Calendar 2017」の10日目です。
というか、今のところこのカテゴリに私しかエントリーしてないので、漏れた日を埋めていこうかな、ぐらいの感じです。

YouTube: Playlist: Making archive IL2C
GitHub: IL2C step-by-step design project

ネタをひねり出すのもアレなので、今まで蓄積したMaking archive IL2Cのダイジェストをやっていこうかと思います。

(イメージをクリックするとYouTubeが開きます)


#6-28 (.NET Conf 2017 Tokyo)

今までに至る解説を「.NET Conf 2017 Tokyo」で登壇 して喋ってきました。

unpluged枠だったので、スライドは殆ど無く、喋りだけです。この時にも幾つか過去のビデオを見直していたのですが、やっぱりフロー解析の辺りが一番大変でしたね。

#6-29

#6-27に引き続き、Value typeのインスタンスフィールド・メソッドの対応を行います。

インスタンスフィールドにアクセスするにはldfldやstfldを使えばよいのですが、インスタンスメンバにアクセスするには、インスタンスへのアドレス(マネージ参照)が必要です。MSDNではマネージ参照のことを「アドレス」と呼んでおり、かなり違和感があります(アンマネージポインタのようだ…)。

とにかく、Value typeのメンバにアクセスする場合は、マネージ参照を評価スタックにpushすれば良いため、ldlocaを使ってローカル変数へのマネージ参照をスタックにpushしておきます。

実はメンバを参照するだけ(例えばフィールドから値をldfldで取得する)であれば、マネージ参照ではなく値そのものでも問題ありません。しかし、値をストアする(stfld)場合は、必ずマネージ参照をpushする必要があります。これはちょっと考えると当たり前で、スタックに格納されている値型のフィールドを変更しても、それはスタックに保持されているので、すぐに破棄されてしまいます。

#6-30

引き続き、Value typeのフィールドアクセスに必要なILに対処しました。ldloca.s・initobj・stfld命令のILConverterを実装します。

口に出していませんが、この辺から、評価スタックに付けているマングリングされたシンボル名がやたら長くなるのが気になってきました。

それにしても、InlinePhi、何なんでしょうね…

Making archive IL2C #6-25 … 27

この記事は「AOT技術 Advent Calendar 2017」の9日目です。
というか、今のところこのカテゴリに私しかエントリーしてないので、漏れた日を埋めていこうかな、ぐらいの感じです。

YouTube: Playlist: Making archive IL2C
GitHub: IL2C step-by-step design project

ネタをひねり出すのもアレなので、今まで蓄積したMaking archive IL2Cのダイジェストをやっていこうかと思います。

(イメージをクリックするとYouTubeが開きます)


#6-25

アセンブリ・モジュール・型・メソッド・メソッドボディの関係を説明しました。

で、実装して確認してみると、method tokenからMethodInfo取ってみたら違うメソッドが取れるww 対象のモジュールを間違えていました。method tokenはそれが定義されているモジュールで一意なので、正しいモジュールからResolveする必要があります。

結果として、以下のような出力が得られました:

#include <stdbool.h>
#include <stdint.h>

int32_t IL2C_ConverterTest_CallTestMethod(void)
{
  int32_t local0;

  int32_t __stack0_int32_t;
  int32_t __stack1_int32_t;

  __stack0_int32_t = 1;
  __stack1_int32_t = 2;
  __stack0_int32_t = IL2C_ConverterTest_CallStaticMethodTestType_Test(
    __stack0_int32_t, (int16_t)__stack1_int32_t);
  local0 = __stack0_int32_t;
  goto L_0000;
L_0000:
  __stack0_int32_t = local0;
  return __stack0_int32_t;
}

第二引数はint16であり、評価スタックが常にint32以上となるので、明示的にキャストを挿入しています。

#6-26

次に、Value type内のスタティックフィールドの変換です。

.NETでのスタティックフィールドとは、一意なインスタンスの格納先となるのですが、C言語に対応するものは「グローバル変数」です。思い出しましたか? えぇ、「グローバル変数」ですよ。そうだっけ?みたいな感じでした :)

C言語でグローバル変数を実現する場合にも、staticキーワードを付けることが出来ます。このキーワードは、シンボルをファイルスコープに制約するもので、(C#構文と似ているのに).NETとは似ても似つかない感じですね。.NETで対応する概念は、アクセス修飾子 ですかね。

この回ではValue typeに対応する定義までを行いました。

#6-27

引き続き、Value typeのスタティックフィールドに対処しました。

スタティックフィールドの初期値を埋めるために、FieldInfo.GetValue()を使いましたが、ここでType initializerの問題に気が付きました。

ここで示した方法は、リフレクションでスタティックフィールドの初期値を取り出していますが、この方法には重大な問題があります。値の取得時に暗黙にType initializerが実行されてしまうということです。これは結構厄介な問題で、現在(#50)の時点ではissueに積んで保留しています。

Making archive IL2C #6-22 … 24

この記事は「AOT技術 Advent Calendar 2017」の8日目です。
というか、今のところこのカテゴリに私しかエントリーしてないので、漏れた日を埋めていこうかな、ぐらいの感じです。

YouTube: Playlist: Making archive IL2C
GitHub: IL2C step-by-step design project

ネタをひねり出すのもアレなので、今まで蓄積したMaking archive IL2Cのダイジェストをやっていこうかと思います。

(イメージをクリックするとYouTubeが開きます)


#6-22

16ビットプリミティブの対応を行いました。8ビットとほとんど同じ対応で行けました。

ldc.i2が存在しないので、果たしてリテラル16ビット値がどのように扱われるのか、ちょっと興味がありました。

  • 小さい数値はldc.i4.2とかの単形式ILを使う
  • 大きい数値はldc.i4で、16ビットの範囲内でpushする – どうせ32ビットに拡張され、切り捨てられるので問題ない

のような最適化(というほどのものでもありませんが)がRoslynで行われていました。

#6-23

micro:bitでデモを行う ための準備を行いました。il2c.exeを放置していたので、これを最低限のツールとしての体裁を整えます。

ツールとして、コマンドラインのオプションを受け取れるようにするのも課題ですが、コマンドラインからメソッドの実体を注入することは出来ないため:

  • コマンドラインに対象のアセンブリファイルを指定する
  • アセンブリに含まれる全てのメソッドを変換の対象とする
  • メソッド名は、名前空間と型名を含めた、マングリングされた関数名に変換する
  • 結果を単一のCソースファイルとして出力する

というように決めました。ここで初めて、マングリングされたシンボル名が具体的にどんな具合なのかを見ました。シンボル名解決のためにC++を使いたいなーという感想。

#6-24

とうとうValue typeに着手しました。メンバー(フィールド・メソッド)とスタティック・インスタンスの組み合わせによる定義を変換可能にします。

OR(Object reference)型をやろうとすると、あまりに多くのフィーチャーを一度に考えなければならないので、Value typeが先です。OR型はガベージコレクタ・参照追跡の手法・オブジェクト階層・インターフェイス実装・仮想メソッドなどなど、盛り沢山過ぎます :)
Value typeであれば、メンバーの構成方法・型の定義方法ぐらいです、それでもかなり大掛かりですが…

まずは、スタティックメソッドの呼び出しを処理させます。call命令のoperandから取得できる、method tokenからMethodInfoを取得して、対応する関数呼び出し式に変換します。スタティックなので、callvirtではなくcall命令を使います。また、method tokenを取得する際に参照するモジュールと、何故.NETには「モジュール(.netmodule)」という考え方があるのか? と言う話をしています。Moduleが特定できれば、method token値からMethodInfoを入手できます。ここから、関数呼び出しのソースコードを構成します。

メソッド呼び出しのパラメータ群は、評価スタックに積まれているので、これを逆順で取り出します。DecodeContextには評価スタックに相当する式をシンボル名(”__stack0″のような)で取得できるので、これをカンマで結合すれば、関数の引数群を構成できます。

最後に、少しだけALM(ビルドシステムとしてどこからどこまでどのように実現するか)の事に触れています。

Making archive IL2C #6-19 … 21

この記事は「AOT技術 Advent Calendar 2017」の7日目です。
というか、今のところこのカテゴリに私しかエントリーしてないので、漏れた日を埋めていこうかな、ぐらいの感じです。

YouTube: Playlist: Making archive IL2C
GitHub: IL2C step-by-step design project

ネタをひねり出すのもアレなので、今まで蓄積したMaking archive IL2Cのダイジェストをやっていこうかと思います。

(イメージをクリックするとYouTubeが開きます)


#6-19

前回から引き続き、ブランチ命令と、ラベルの対応付けを行う実装を行いました。これでifによる現実的なコードの変換が行われることが確認できました。

近所のインドカレー屋の不思議な運営の雑談もあります(?)

#6-20

if文の対応から横道にそれましたが、やっと、8ビット・16ビットプリミティブ型の対応を行いました。8ビットと言えばByteとShortですが、C言語で8ビットリテラル値がどのように扱われるのか… 今更C言語のリテラル表現を調べることになるとは思いもよらず。

そして、ここでようやく評価スタックに8ビットの値を入れる場合は32ビットのint32として自動的に符号拡張される、という事実を知ることに。また、ローカル変数に格納する場合も、int32から自動的に上位24ビットが切り捨てられる。前回その辺りをまとめましたが、実際にはこの回ぐらいで理解することになりました。

#6-21

引き続き、8ビットのSByte対応を行いました。8ビットの符号ビットの計算は、特別な処理が必要かどうかを検証しています。なぜなら、8ビットの値を評価スタックにpushする際には32ビット(int32)としてpushするので、ここで符号拡張(又はpopするときに縮退又は切り捨て)の区別をつける必要があるかどうかが重要だからです。結局、切り捨てるだけで良かったので、符号拡張ではなくビット幅を広げ、popした時に24ビットを切り捨てれば辻褄が合います。

ここで検討していたときには気が付きませんでしたが、今考えると、評価スタックのスロットを異なる型で再利用しなければ問題は発生しない、という条件が付きます。端的に言えば、問題のあるILが来るとマズイですが、InvalidProgramExceptionな案件のような気がします(IL2Cはこの例外を送出しませんが)。

Making archive IL2C #6-16 … 18

この記事は「AOT技術 Advent Calendar 2017」の6日目です。
というか、今のところこのカテゴリに私しかエントリーしてないので、漏れた日を埋めていこうかな、ぐらいの感じです。

YouTube: Playlist: Making archive IL2C
GitHub: IL2C step-by-step design project

ネタをひねり出すのもアレなので、今まで蓄積したMaking archive IL2Cのダイジェストをやっていこうかと思います。

(イメージをクリックするとYouTubeが開きます)


#6-16 (milestone2)

前回の方針で、引き続きコードを変更し、テストも修正します。 milestone2到達です。

ようやく、フロー解析にまつわる大変更が終わってホッとしました。ぶっ壊れてヤル気が折れなくて良かった… この回の終盤に、今後の方針を再確認しています。

#6-17

プリミティブ型でまだやっていない、ByteとかShortを扱えるようにしようとしたのですが、その前にあまりにわかりにくいDecodeContextにまつわるメンバー名を、リファクタリングで修正しました。また、ラベル番号がILのインデックスという状況をどうにかしたくて、後から連番でfixupするように変更しました。

*** ニャーン ***

#6-18

そう言えば、実際にifで分岐したコードでブランチ命令のテストをしていない、ということで、先にそのテストをしました。すると…

if文の判定条件に従って、評価スタックにtrue又はfalseの値がpushされるのですが、その後ブランチ命令で結果によって分岐する際に驚愕の事実が。

  • 評価スタックにはあらゆる型の値を保持できる
  • しかし、以下の値は、int32の値として保持される:
    Byte, SByte, Int16, UInt16, UInt32, Boolean
  • 数値の扱いは対称性がない:
    Int64はそのまま、UInt64はInt64、SingleはDoubleとして保持
  • その他の値型はそのままの値で保持
  • その他のOR型・マネージド参照・ポインタはそのままの値で保持

一見わかりにくそうなのですが、実はこれ、CやC#の符号拡張に似てる感じがします。そして、これまでの実装では型を真面目に扱っていたため、例えば、boolの値を評価スタックにBoolean型で保持するというように、型の追跡を行っていたので、条件ブランチ命令のPop(brfalse)でハマりました。

Making archive IL2C #6-13 … 15

この記事は「AOT技術 Advent Calendar 2017」の5日目です。
というか、今のところこのカテゴリに私しかエントリーしてないので、漏れた日を埋めていこうかな、ぐらいの感じです。

YouTube: Playlist: Making archive IL2C
GitHub: IL2C step-by-step design project

ネタをひねり出すのもアレなので、今まで蓄積したMaking archive IL2Cのダイジェストをやっていこうかと思います。

(イメージをクリックするとYouTubeが開きます)


#6-13

これは、いわゆる型推論のような何かとか、CPUのレジスタリネーミングのような何かでは?みたいな事を考えながら、理論的なことはわからないので実コードとして実装可能なように問題を整理していました。

ここで、スタックスロットをシンボルとして抽象化した時に、単にリネーミングするとC言語に落としたときに型が合わなくてコードが成立しないので、その場合はそれぞれの型に合わせたコードを出力する必要があります。ようやく、問題の核心にたどり着きました。

#6-14

ILConverterの構造に手を入れて、全体的に修正したコードの解説を行いました。前回わかった問題を、どうやって対処するのか、ですが…

ブランチ命令によって分割される「実行パス」を認識して、それぞれのパスをキューに入れ、実行パス分岐後の流入箇所で想定される評価スタックのスロット(ここではインデックスと読んでいる)の型が一致しているかどうかを確認し、一致していればC言語上でもコードが一致するので単にgotoで飛ばし、そうでないなら、新たな型を使うが同じようなコードとして出力し直す、ということをします。

この部分、スタックスロットのコンシューマーが、ブランチ直前と遷移先で、どこまでと規定されるのかを機械的に判断するのが難しく、現在(#50)での実装も少し手抜きになっています(複雑というだけで不可能ではない)。

この大幅に変更したコードで、実際にフロー解析が機能して変換されるのかどうか? 緊張しましたが、正しく期待通りに変換されました。そして、Cコンパイラはこの複雑に見えるコードをちゃんと見抜いています。

#6-15

痛恨の収録ミス… 音声入ってなーい!!! orz ということで、後から映像だけ見ながらオーディオコメンタリーやって結合しました :)

  • 変換中の情報をDecodeContextクラスで保持する
  • スタックとスタックの各スロットに格納されることを想定している型の情報を保持する
  • それぞれのスタックスロットに対して、個別のシンボル名を割り当てる(型の異なるローカル変数を区別可能にする)

という登場人物を図示して、実際のコードに落としていきます。

あと、goto文を成立させるためにラベルをどうやって付けるか、という問題を考えています。今考えると、関数で遅延評価すれば良いよなと思うんですが、C#で書くと(ちょっとしたことではあるんですが)モヤモヤして、結局小さい入れ物を作って対処しました。

Making archive IL2C #6-10 … 12

この記事は「AOT技術 Advent Calendar 2017」の4日目です。
というか、今のところこのカテゴリに私しかエントリーしてないので、漏れた日を埋めていこうかな、ぐらいの感じです。

YouTube: Playlist: Making archive IL2C
GitHub: IL2C step-by-step design project

ネタをひねり出すのもアレなので、今まで蓄積したMaking archive IL2Cのダイジェストをやっていこうかと思います。

(イメージをクリックするとYouTubeが開きます)


#6-10

前回から引き続き、フロー解析(実行パス解析)の検討です。

ここら辺で、評価スタックの同じインデックスに異なる型が使用される可能性について気がついた感じです。ただ、まだadd opcodeについてのバリエーションで同じことが起きる、ぐらいの狭い範囲での気づきです(と言うか、こっちの前にIL全体で発生しうるという事に気が付きたかった :)

#6-11

フローについて本格的に解析が必要になり、今まではILConverterで変換した結果を一方的に変換処理に垂れ流ししていたのですが、実行パス(解析開始位置からブランチ先までの一連のopcodeシーケンス)毎に「フローの束」として順次解析を行う事が出来るように、地味ですが重要なリファクタリングを行っていきます。

#6-12

引き続き、フロー解析のコア部分を検討しながら実装しています。評価スタックの同一インデックスが異なる型で使われる場合のCソースコード上の表現方法について、ホワイトボードにあるように異なるローカル変数として宣言して使い分ける、という方針で実装することになりました。

Making archive IL2C #6-7 … 9

この記事は「AOT技術 Advent Calendar 2017」の3日目です。
というか、今のところこのカテゴリに私しかエントリーしてないので、漏れた日を埋めていこうかな、ぐらいの感じです。

YouTube: Playlist: Making archive IL2C
GitHub: IL2C step-by-step design project

ネタをひねり出すのもアレなので、今まで蓄積したMaking archive IL2Cのダイジェストをやっていこうかと思います。

(イメージをクリックするとYouTubeが開きます)


#6-7

Hello world的な最初のトライがInt32の計算だったので、まずはInt64を扱うことで、どのような差異が生まれるのかを確認しました。

計算自体はInt32とほぼ同じ(C言語に変換しても結果的に “+” オペレータになる)なのですが、リテラルの数値に”LL”を付けたり、関数引数の型に応じてローカル変数の型を変える必要があり、変換用コンテキストとして保持している情報にパラメータ群も保持するように改造しました。

このあたりではまだ評価スタックは、直前にPushされた値に対応する式を直接文字列で格納していたりして、ある意味のどかな感じです。

#6-8

迷走の始まりです :)

前回までで評価スタックに式を文字列で格納するのは問題がありそうだ、ということは分かったのですが、具体的に何が問題になりそうなのかはまだグレーだったので、簡単なILから順に考えて問題の焦点を考察しました。

デコーダー(とILConverterの前後)で、ブランチ命令の分析が必要ではないかという事が臭ってきます。何故なら、評価スタックにPushする値(の型)は自由であり型の制約がないため、フロー解析(実行パス解析)を行わないと、どの型に対応するのかが分からないからです。

#6-9

前回から引き続き、フロー解析のアルゴリズムの検討です。

この頃はまだ、文字列で表現された式でどうやってうまくやるかという事に執着していたような気がします。ひたすら細かいパターンを詳細に検討します。

Making archive IL2C #6-4 … 6

この記事は「AOT技術 Advent Calendar 2017」の二日目です。
というか、今のところこのカテゴリに私しかエントリーしてないので、漏れた日を埋めていこうかな、ぐらいの感じです。

YouTube: Playlist: Making archive IL2C
GitHub: IL2C step-by-step design project

ネタをひねり出すのもアレなので、今まで蓄積したMaking archive IL2Cのダイジェストをやっていこうかと思います。

(イメージをクリックするとYouTubeが開きます)


#6-4

ILConverterという抽象クラスを導入して、OpCodeに対応する変換の実装をクラスで表現できるようにしました。また、ILConverterを動的に収集して、ILConverterを実装した具象クラスを定義するだけで、OpCodeのデコーダーへの紐付けを動的に処理できるようにしました。

現在の実装(#6-48)でもそうですが、どうにかして「OpCodeと対応する変換処理」と「オペランドの扱い」を分離したいと言うバックグラウンドが垣間見えます。理由は、分離したほうがテストがしやすいのではないかとか、そういう事を考えていたと思います。今は…?

そう言えば、まだ録画機材とかで色々トラブルとか試行錯誤とかしていた頃で、(YouTubeに上げて正常公開されたにもかかわらず)ちょっと変な気がします。H264のストリームが壊れてるのかもしれません。今見ても、Full HD視聴はYouTubeから跳ねられることがあります… 生ファイルは持っているので再エンコードして入れ替えたいのですが、今のYouTubeの仕様では後から動画の差し替えが出来ないんですよね。

#6-5

前半では、「Human resource machine」という、Androidのゲームを紹介しています。このゲームは、ILやバイトコードのような低レベル言語がどのように動作するのかを、パズルのような遊び感覚で知ることが出来るものです。開発をやらない人によっては、このゲームの由来がそういう所から来ている事すら気が付かない人もいると思います。面白いのでおすすめです。

後半は、ILConverterの実装が増えてくることを考えて、ILConverterの変換結果をテストできるように、ユニットテストを実装する方法と実際の実装をやってみました。テストにはNUnitを使っています。

ユニットテストはしばらくこのインフラを使っていきますが、現在の実装においては機能していません。途中での大幅に構造に手を入れた事があり、今後もまだ構造に変更が加わらないかどうかがまだ見えていないため、この修正は保留しています。

#6-6

Hello world的な変換が出来て、テストコードも書けたので、今後の大まかな方針をまとめました。その上で、Int32を扱ったので、Int64にしたらどうなるのかを検証しなから対応しました。題材として丁度良かったので、徐々にTDDでやるようにしていきました。

C言語の整数リテラルの変則的な扱いについて驚いたりしてましたね :)

そして、いよいよVC++のプロジェクトを作り、そこに変換されたCソースコードを突っ込んで、正しく動作する事を確認しました。ここで、生成された機械語コードが「想定通り」全部静的解決されて、計算が直値に置き換わり、しかも関数呼び出しもインライン化されて、たった1命令に短縮されたことを確認しました。

Debugビルドの結果:

Releaseビルドの結果: