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ビルドの結果:

Making archive IL2C #6-1 … 3

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

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

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

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


#6-1

IL2Cを始めたいきさつと、どのようにプロジェクトを進めるのかが前半、後半はILSpyを使用して、Hello world的なコードがどのようなILにコンパイルされるのかを解説しています。一応、メタプログラミング初心者とか、IL初心者とかを想定して、割りと細かいところまで解説しています。

#6-2

前回ILSpyで確認したILを、リフレクションを使用してILの情報をプログラマブルに取得するためには、どのような事をすれば良いのかを解説しています。ライブ配信ではありませんが、目の前で一から書いてデバッグして見せることで、感触をつかみやすくしました。この回で、ILのバイトコードデコーダーの雛形を作りました。

#6-3

画像の通り、極初期の、main関数っぽい何か(全然C言語コードではありませんが)を、デコーダーを使って出力する所までを実装しました。これがIL2Cの内部骨格となって、あとはOpCodeをどう変換するかという、要するにスタート地点に立ったことになります。

初歩的なILの組:

ldc.i4.1
stloc.0

int a = 1;

のようなコードに変換されて欲しい、というOpCodeとC言語の対応付けを確認しました。

このまとめを書いたことで思い出したのですが、既に#6-3の時点で評価スタックの型の追跡が必要なのではないかという事に気がついていましたね。

IL2C短信: milestone3

IL2Cの短信です。milestone3となる、ValueTypeのサポートを(限定的ですが)行いました。

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


IL2Cをmicro:bitで動かす (#6-24・#6-25)

  • #6-24・#6-25の時点のIL2Cを使用して、micro:bitArduino UNOのCコンパイラを使って実際に極小環境で動かしました。

Making Archive IL2C at .NET Conf 2017 Tokyo (#6-28)

namespace il2c_test_target
{
    public class Hoge1
    {
        public static int Add1(int a, bool isTwo)
        {
            return a + (isTwo ? 2 : 1);
        }
    }
}
int32_t il2c_test_target_Hoge1_Add1(int32_t a, bool isTwo)
{
    int32_t local0;

    int32_t __stack0_int32_t;
    int32_t __stack1_int32_t;

    __stack0_int32_t = a;
    __stack1_int32_t = isTwo ? 1 : 0;
    if (__stack1_int32_t != 0) goto L_0000;
    __stack1_int32_t = 1;
    goto L_0001;
L_0000:
    __stack1_int32_t = 2;
L_0001:
    __stack0_int32_t = __stack0_int32_t + __stack1_int32_t;
    local0 = __stack0_int32_t;
    goto L_0002;
L_0002:
    __stack0_int32_t = local0;
    return __stack0_int32_t;
}

milestone3 (#6-37)

  • byte, sbyte, short, ushort, boolのサポート。
  • ValueType(構造体)のフィールドとメソッドをサポート。スタティックとインスタンスメンバの両方共に変換出来ます。
    スタティックメンバはCソースコード上、グローバル変数とグローバル関数として変換し、インスタンスフィールドは構造体、インスタンスメソッドはグローバル関数として変換。
  • 名前空間と型名についてのマングリングの導入。
  • 値を返さないメソッド(void)のret OpCodeのサポート
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace il2c_test_target
{
    public struct Hoge3
    {
        public static int Value1 = 123;
        public int Value2;

        public int GetValue2(int a, int b)
        {
            return this.Value2 + a + b;
        }
    }

    public class Hoge4
    {
        public static int Test4()
        {
            var hoge3 = new Hoge3();
            hoge3.Value2 = 456;

            return hoge3.Value2;
        }

        public static int Test5()
        {
            var hoge3 = new Hoge3();
            hoge3.Value2 = 789;

            var result = hoge3.GetValue2(123, 456);
            return result;
        }
    }
}
#ifndef __MODULE_il2c_test_target__
#define __MODULE_il2c_test_target__

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

typedef struct il2c_test_target_Hoge3
{
    int32_t Value2;
} il2c_test_target_Hoge3;

extern int32_t il2c_test_target_Hoge3_Value1;

extern int32_t il2c_test_target_Hoge3_GetValue2(il2c_test_target_Hoge3* __this, int32_t a, int32_t b);
extern int32_t il2c_test_target_Hoge4_Test4(void);
extern int32_t il2c_test_target_Hoge4_Test5(void);

#endif
#include "il2c_test_target.h"

int32_t il2c_test_target_Hoge3_Value1 = 123;

int32_t il2c_test_target_Hoge3_GetValue2(il2c_test_target_Hoge3* __this, int32_t a, int32_t b)
{
    int32_t local0;

    il2c_test_target_Hoge3* __stack0_il2c_test_target_Hoge3_reference;
    int32_t __stack0_int32_t;
    int32_t __stack1_int32_t;

    __stack0_il2c_test_target_Hoge3_reference = __this;
    __stack0_int32_t = __stack0_il2c_test_target_Hoge3_reference->Value2;
    __stack1_int32_t = a;
    __stack0_int32_t = __stack0_int32_t + __stack1_int32_t;
    __stack1_int32_t = b;
    __stack0_int32_t = __stack0_int32_t + __stack1_int32_t;
    local0 = __stack0_int32_t;
    goto L_0000;
L_0000:
    __stack0_int32_t = local0;
    return __stack0_int32_t;
}

int32_t il2c_test_target_Hoge4_Test4(void)
{
    il2c_test_target_Hoge3 local0;
    int32_t local1;

    il2c_test_target_Hoge3* __stack0_il2c_test_target_Hoge3_reference;
    il2c_test_target_Hoge3 __stack0_il2c_test_target_Hoge3;
    int32_t __stack0_int32_t;
    int32_t __stack1_int32_t;

    __stack0_il2c_test_target_Hoge3_reference = &local0;
    memset(__stack0_il2c_test_target_Hoge3_reference, 0x00, sizeof(il2c_test_target_Hoge3));
    __stack0_il2c_test_target_Hoge3_reference = &local0;
    __stack1_int32_t = 456;
    __stack0_il2c_test_target_Hoge3_reference->Value2 = __stack1_int32_t;
    __stack0_il2c_test_target_Hoge3 = local0;
    __stack0_int32_t = __stack0_il2c_test_target_Hoge3.Value2;
    local1 = __stack0_int32_t;
    goto L_0000;
L_0000:
    __stack0_int32_t = local1;
    return __stack0_int32_t;
}

int32_t il2c_test_target_Hoge4_Test5(void)
{
    il2c_test_target_Hoge3 local0;
    int32_t local1;
    int32_t local2;

    il2c_test_target_Hoge3* __stack0_il2c_test_target_Hoge3_reference;
    int32_t __stack0_int32_t;
    int32_t __stack1_int32_t;
    int32_t __stack2_int32_t;

    __stack0_il2c_test_target_Hoge3_reference = &local0;
    memset(__stack0_il2c_test_target_Hoge3_reference, 0x00, sizeof(il2c_test_target_Hoge3));
    __stack0_il2c_test_target_Hoge3_reference = &local0;
    __stack1_int32_t = 789;
    __stack0_il2c_test_target_Hoge3_reference->Value2 = __stack1_int32_t;
    __stack0_il2c_test_target_Hoge3_reference = &local0;
    __stack1_int32_t = 123;
    __stack2_int32_t = 456;
    __stack0_int32_t = il2c_test_target_Hoge3_GetValue2(__stack0_il2c_test_target_Hoge3_reference, __stack1_int32_t, __stack2_int32_t);
    local1 = __stack0_int32_t;
    __stack0_int32_t = local1;
    local2 = __stack0_int32_t;
    goto L_0000;
L_0000:
    __stack0_int32_t = local2;
    return __stack0_int32_t;
}

IL2Cプロジェクト – Extensive Xamarin

技術書典3で配布予定の”Extensive Xamarin”に、IL2Cを寄稿させて頂きました。
是非、皆さん入手して読んでください :)

範囲はおおよそ.NET Confの発表分です。ビデオシリーズではすべて網羅していますが、その中でも印象深かったトピックについて、書籍化で解説しやすい部分を抜粋してあります。
締切がギリギリでしたが掲載を快諾していただいたXamaritansのメンバーの方々に感謝します。

何故Xamarin本に寄稿したのかですが、#6-38で喋っています:

IL2C短信: milestone2

IL2Cの短信です。milestoneを決めてやっているわけではないのですが、一区切りついたのでmilestone2ということにしておこう。

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


milestone1 (#6-4)

Hello world的なシンプルコードの変換が出来る:

public static int main()
{
  var a = 1;
  var b = 2;
  var c = a + b;
  return c;
}
int main(void)
{
  int local0;
  int local1;
  int local2;
  int local3;

  local0 = 1;
  local1 = 2;
  local2 = local1 + local0;
  local3 = local2;
  return local3;
}

milestone2 (#6-16)

  • プリミティブ型のプラットフォーム依存性を回避したいので、stdint.hを使うようにする。
  • 64ビット整数の足し算のサポート(今後の方向性検証のため)。
  • スタックの高度な再利用を含むコードの変換が出来る。
    これが一番大変だった… ILの実行パス解析に型推論が必要(知識ないのでもっと直接的な手法で実装した)とか。今の方法にも積み残しがあるけど。
  • 無条件・条件ジャンプに対応。
    上が出来たので、必然的にこれも出来るようになった。
public static long main()
{
  var a = 1L;
  var b = 2L;
  var c = a + b;
  return c;
}
#include <stdint.h>

int64_t main(void)
{
  int64_t local0;
  int64_t local1;
  int64_t local2;
  int64_t local3;

  int32_t __stack0_int32_t;
  int64_t __stack0_int64_t;
  int64_t __stack1_int64_t;

  __stack0_int32_t = 1;
  __stack0_int64_t = (int64_t)__stack0_int32_t;
  local0 = __stack0_int64_t;
  __stack0_int32_t = 2;
  __stack0_int64_t = (int64_t)__stack0_int32_t;
  local1 = __stack0_int64_t;
  __stack0_int64_t = local0;
  __stack1_int64_t = local1;
  __stack0_int64_t = __stack0_int64_t + __stack1_int64_t;
  local2 = __stack0_int64_t;
  __stack0_int64_t = local2;
  local3 = __stack0_int64_t;
  goto L_000b;
L_000b:
  __stack0_int64_t = local3;
  return __stack0_int64_t;
}

この冗長なコードは、VC++のReleaseビルドで2命令に短縮されます:

ビデオネタ: IL2C

IL2Cと言うのは、Unityで言うところのIL2CPPのC言語版です。これをフルスクラッチで作ってみるというビデオシリーズです。
つまり、C#(というか、それをコンパイルしたILを含むDLLやEXE)を入力に、C言語のソースコードを生成するツール、というわけです。

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

現在第6回までやったところですが、以下のようなC#のコード:

public static int main()
{
  var a = 1;
  var b = 2;
  var c = a + b;
  return c;
}

が、

#include <stdint.h>
int32_t main(void)
{
  int32_t local0;
  int32_t local1;
  int32_t local2;
  int32_t local3;

  local0 = 1;
  local1 = 2;
  local2 = local1 + local0;
  local3 = local2;
  return local3;
}

というC言語のソースコードに変換できる所まで出来ました。また、これの64ビット(long, int64_t)も出来たところです。

開発の方法の検討・設計・実装・テストまで含めて、全体を一からフルスクラッチでやってるところを、ほぼカット無しで収録しています。メタプログラミングに興味のある方は視聴してみてください。

この調子で続けると、40回~50回ぐらいで完成かな… 先は長そうだ :)

あと、途中でHuman Resource Machineというゲームをちょっとだけ紹介しています。IL(というかアセンブリ言語)をゲーム感覚で学べるアプリでお薦めです。