「10日くらいでできる!プログラミング言語自作入門」の続編#1-12

  • (by K, 2021.05.14)

(1) HL-22

  • HL-21aで「print 1+2*3」をJITコンパイルするとこうなります。
    >print 1+2*3
    b8 02 00 00 00 48 6b c0 03 48 89 85 20 01 00 00 b8 01 00 00 00 48 03 85 20 01 00 00 48 89 85 28 01 00 00 48 8b 8d 28 01 00 00 48 ff 95 70 01 00 00
    (len=49)
  • この機械語を整理するとこうなります。
    b8_02_00_00_00_00;    // RAX=2;
    48_6b_c0_03;          // RAX=RAX*3;
    48_89_85_20_01_00_00; // _t0=RAX;
    b8_01_00_00_00_00;    // RAX=1;
    48_03_85_20_01_00_00; // RAX=RAX+_t0;
    48_89_85_28_01_00_00; // _t1=RAX;
    48_8b_8d_28_01_00_00; // RCX=_t1;
    48_ff_95_70_01_00_00; // CALL sub_print;
  • つまり、一生懸命に式を計算しているのです。当たり前ですけどね。
  • でも、こんな定数式は別に実行時に計算しなくたっていいはずです。結果は変わらないのですから。だから、
    b9_07_00_00_00; // RCX=7;
    48_ff_95_70_01_00_00; // CALL sub_print;
    みたいにJITコンパイルできたらかっこいいと思いませんか?私は思います。
  • ということで、それを実現するのがHL-22の目標です。

  • [1]isConst()関数に2行追加
    int isConst(int i)
    {
        if ('0' <= ts[i][0] && ts[i][0] <= '9') return 1;
    +   if (ts[i][0] == '-' && '0' <= ts[i][1] && ts[i][1] <= '9') return 1;
    +   if (ts[i][0] == 34) return 1;
        return 0;
    }
  • [2]getConstM()関数の後に以下の記述を追加
    int calcConst1(int op, int a)
    {
        AInt v = 0, va = var[a];
        char s[100];
        if (isConst(a) == 0) return 0;
        switch (op) {
        case TcMinus: v = - va; break;
        }
        sprintf(s, "%d", (int) v);
        return getTc(s, strlen(s));
    }
    
    int calcConst2(int op, int a, int b)
    {
        AInt v = 0, va = var[a], vb = var[b];
        char s[100];
        if (isConst(a) == 0 || isConst(b) == 0) return 0;
        switch (op) {
        case TcEEq:   v = va == vb; break;
        case TcNEq:   v = va != vb; break;
        case TcLt:    v = va <  vb; break;
        case TcGe:    v = va >= vb; break;
        case TcLe:    v = va <= vb; break;
        case TcGt:    v = va >  vb; break;
        case TcPlus:  v = va +  vb; break;
        case TcMinus: v = va -  vb; break;
        case TcAster: v = va *  vb; break;
        case TcSlash: v = va /  vb; break;
        case TcPerce: v = va %  vb; break;
        case TcAnd:   v = va &  vb; break;
        case TcShr:   v = va >> vb; break;
        }
        sprintf(s, "%d", (int) v);
        return getTc(s, strlen(s));
    }
    
  • [3]exprSub1()関数に3行追加
    int exprSub1(int i, int priority, int op)	// 二項演算子の処理の標準形.
    {
        int j, k;
        epc++;
        j = exprSub(priority);
    +   k = calcConst2(op, i, j);
    +   if (k == 0) {
            k = tmpAlloc();
            putIcX64(opBin[op - TcEEq], &var[k], &var[i], &var[j], 0);
    +   }
        tmpFree(i);
        tmpFree(j);
        if (i < 0 || j < 0) return -1;
        return k;
    }
  • [4]exprSub()関数に3行追加
        } else if (tc[epc] == TcMinus) {	// 単項マイナス.
            epc++;
            e0 = exprSub(2);
    +       i = calcConst1(TcMinus, e0);
    +       if (i == 0) {
                i = tmpAlloc();
                putIcX64("%R_8b_%1m0; %R_f7_d8; %R_89_%0m0;", &var[i], &var[e0], 0, 0);
    +       }
  • [5]compile()関数に9行追加
            } else if (phrCmp( 2, "!!*0 = !!*1 !!*2 !!*3;", pc) && TcEEq <= tc[wpc[2]] && tc[wpc[2]] <= TcShr) {  // 加算, 減算など.
    +           i = calcConst2(tc[wpc[2]], tc[wpc[1]], tc[wpc[3]]);
    +           if (i == 0) {
                    putIcX64(opBin[tc[wpc[2]] - TcEEq], &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[3]]], 0);
    +           } else {
    +               if (regVar(&var[tc[wpc[0]]]) < 0) {
    +                   putIcX64("%1L11; %R_89_&48:%0m0;", &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0);
    +               } else {
    +                   putIcX64("%0L00; %R_8b_&48:%1m0;", &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0);
    +               }
    +           }

  • 以上すべての改造を終えると、プログラムは1204行になります。
  • それでは効果を確認してみます。
    >print 1+2*3
    b9 07 00 00 00 48 ff 95 70 01 00 00
    (len=12)
  • こんなふうにちゃんと定数式が計算されて7がいきなり渡されていることが確認できます。
  • 以下の例のように、部分的に定数式がある場合も、その部分だけコンパイル時に計算されます。ばっちりです!
    >a=b+(9-1)
    48 8b 85 10 03 00 00 48 83 c0 08 48 89 85 08 03 00 00
    (len=18)
    
    48_8b_85_10_03_00_00; // RAX=b;
    48_83_c0_08;          // RAX=RAX+8;
    48_89_85_08_03_00_00; // a=RAX;

(2) プログラムの説明

  • isConst()関数に2行追加
    • これは負の数や文字列リテラルを定数だと認識するように拡張しています。
  • calcConst1()
    • これは単項演算子の定数計算をするものです。
    • もし渡されたトークンが定数なら計算結果のトークンを返します。
    • 定数でなければ0を返します。
  • calcConst2()
    • これは二項演算子の定数計算をするものです。
    • もし渡されたトークンが2つとも定数なら計算結果のトークンを返します。
    • そうでなければ定数計算はできないので0を返します。
  • これらがそろった後は、演算時にこれを呼び出して、もし0以外が返ってくれば計算のための機械語の生成をスキップします。
  • a=b+c;みたいなシンプルな計算の場合に、b+cの部分が定数計算できるときは、a=const;型の定数代入命令になります。

(3) 成果の比較

  • 上記みたいなのはすごく特別でレアケースなのか、それともよくあるメジャーケースなのか、たぶん簡単には判断できないと思うので、いくつかのプログラムでcodedumpしてバイト数を比較してみました。
  • サイズが小さくなったからいいとか悪いとかではなく、「サイズが小さくなった=それだけ適用された」ということだと考えてください。
HL-19aHL-20HL-20aHL-20bHL-21HL-21aHL-22
mandel.c12001088989989814719670
maze.c2331233123312331190916541638
kcube.c5207520752075207418839493948
invader.c3567356735673567300125932532

次回に続く

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-05-18 (火) 11:38:21 (131d)