ただの素人がフロー解析を通過した – 言語実装 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言語向けに、型ごとのコード生成を行っています。

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

投稿者:

kekyo

A strawberry red slime mold. Likes metaprogramming. MA. Bicycle rider. http://amzn.to/1SeuUwD