月: 2017年12月

厨二変換病

私は、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操作を追跡し、どこでどのスタック位置をどのように使っているか、を解析しなければならないのです。

// 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
}

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;                    // ---+
}

#6-29

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

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

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

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

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

#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-23

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

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

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

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

#6-20

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

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

#6-17

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

*** ニャーン ***

#6-14

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

#6-11

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

#6-8

迷走の始まりです :)

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

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

#6-5

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

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

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