a21_txt02_12 のバックアップ(No.1)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
a21_txt02_12 へ行く。
- 1 (2021-05-14 (金) 23:42:06)
- 2 (2021-05-15 (土) 00:00:03)
- 3 (2021-05-18 (火) 11:38:21)
- 4 (2021-05-18 (火) 11:38:21)

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

(by K, 2021.05.14)

(1) HL-22

HL-21aで「print 1+2*3」をJITコンパイルするとこうなります。

（以下編集中）

>print 1+2*3
b8 02 00 00 00 6b c0 03 89 05 a0 0a 42 00 b8 01 00 00 00 03 05 a0 0a 42 00 89 44 24 00 e8 8f 27 c6 ff
(len=34)

この機械語を整理するとこうなります。

b8_02_00_00_00_00; // EAX=2;
6b_c0_03;          // EAX=EAX*3;
89_05_a0_0a_42_00; // _t0=EAX;
b8_01_00_00_00_00; // EAX=1;
03_05_a0_0a_42_00; // EAX=EAX+_t0;
89_44_24_00;       // [ESP+0]=EAX;
e8_8f_27_c6_ff;    // CALL sub_print;

つまり、一生懸命に式を計算しているのです。当たり前ですけどね。

でも、こんな定数式は別に実行時に計算しなくたっていいはずです。結果は変わらないのですから。だから、
```
b8_07_00_00_00; // EAX=7;
89_44_24_00;    // [ESP+0]=EAX;
e8_8f_27_c6_ff; // CALL sub_print;
```
みたいにJITコンパイルできたらかっこいいと思いませんか？私は思います。
ということで、それを実現するのがHL-16の目標です。

[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)
{
    int v = 0, va = var[a];
    char s[100];
    if (isConst(a) == 0) return 0;
    switch (op) {
    case TcMinus: v = - va; break;
    }
    sprintf(s, "%d", v);
    return getTc(s, strlen(s));
}

int calcConst2(int op, int a, int b)
{
    int 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", 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();
        putIcX86(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();
            putIcX86("8b_%1m0; f7_d8; 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) {
                putIcX86(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) {
+                   putIcX86("%1L11; 89_&8:%0m0;", &var[tc[wpc[0]]], &var[i], 0, 0);
+               } else {
+                   putIcX86("%0L00; 8b_&8:%1m0;", &var[tc[wpc[0]]], &var[i], 0, 0);
+               }
+           }

以上すべての改造を終えると、プログラムは1065行になります。

それでは効果を確認してみます。

>print 1+2*3
b8 07 00 00 00 89 44 24 00 e8 f4 28 2f fe
(len=14)

こんなふうにちゃんと定数式が計算されて7がいきなり渡されていることが確認できます。

以下の例のように、部分的に定数式がある場合も、その部分だけコンパイル時に計算されます。ばっちりです！

>a=b+(9-1)
8b 05 50 0b 42 00 83 c0 08 89 05 4c 0b 42 00
(len=15)

8b_05_50_0b_42_00; // EAX=b;
83_c0_08;          // EAX=EAX+8;
89_05_4c_0b_42_00; // a=EAX;

↑

(2) プログラムの説明

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

↑

(3) 成果の比較

上記みたいなのはすごく特別でレアケースなのか、それともよくあるメジャーケースなのか、たぶん簡単には判断できないと思うので、いくつかのプログラムでcodedumpしてバイト数を比較してみました。
サイズが小さくなったからいいとか悪いとかではなく、「サイズが小さくなった＝それだけ適用された」ということだと考えてください。

	HL-13a	HL-14	HL-14a	HL-15	HL-15a	HL-16
mandel.c	1087	1007	942	768	726	657
maze.c	2192	2192	2192	1770	1536	1533
kcube.c	4623	4623	4623	3695	3495	3494
invader.c	3260	3260	3260	2750	2399	2357

↑

次回に続く

次回: a21_txt02_6a

↑

こめんと欄

コメント	お名前	NameLink