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

  • (by K, 2021.04.21)

(1) HL-14a

  • HL-14は期待通りに速くなってくれて大変うれしいのですが、その生成コードの質はまだ「いまいち」になっています。具体的に見てみましょう。
    >regVar(0 i)
    
    >codedump 1
    
    (len=0)
    
    >run hl3.txt
    8b 05 0c 0a 42 00 89 c3 8b c3 40 89 c3 3b 05 28 0b 42 00 0f 8c ef ff ff ff e8 a9 22 f8 fd
    (len=30)
  • これは、1億回ループのプログラムをcodedump 1の状態でrunした結果です(HL-3参照→a21_txt01_3)。このコードを見やすい形で書き直すとこうなります。
        8b 05 0c 0a 42 00;  // EAX = 0;
        89 c3;              // EBX = EAX;
    label:
        8b c3;              // EAX = EBX;
        40;                 // EAX++;
        89 c3;              // EBX = EAX;
        3b 05 28 0b 42 00;  // if (EAX < 1億) goto label;
        0f 8c ef ff ff ff;
        e8 a9 22 f8 fd;     // call time
  • まあこれは、HL-14のアルゴリズムを考えれば、こうなって当然なのですが、しかし「あちゃー」と言いたくなるような結果でもあるのです。
  • どこが低品質なのかというと、EBXレジスタを使っているにもかかわらず(=メモリじゃないのに)、わざわざEAXに持ち替えてから処理をしているところがだめなのです。
  • 理想を考えると以下のようになります。
        8b 1d 0c 0a 42 00;  // EBX = 0;
    label:
        43;                 // EBX++;
        3b 1d 28 0b 42 00;  // if (EBX < 1億) goto label;
        0f 8c ef ff ff ff;
        e8 a9 22 f8 fd;     // call time
  • 普通ならこのようにEBXをEBXのままで演算すべきなのです。これなら1ループ当たりの命令数は5→3となるので、高速化が期待できます。

  • ここまでは、私もわかっていました。それこそ何年も前から分かっていました。しかしレジスタ変数の場合と、メモリ変数の場合で場合分けして処理を書き始めると、あっという間に言語処理系は大きくなってしまいます。それはちっとも「自作入門」ではありません。だからもともとはこの最適化の話はしない予定でした。
  • でもようやく、これを簡単に書く方法を思いつきました。だから紹介してみます。いやもっといい方法があるかもしれないですが、とりあえず現時点で私が知る中では一番シンプルなやり方です。

  • HL-14の段階では、加算の二項演算子はこうなっています(opBin[]より)。
    8b_%1m0; 03_%2m0; 89_%0m0;
  • これをHL-14aでは以下のようにします。
    %1L0; 03_&8:%2m0; %0S;
  • これの意味を説明します。
  • まず最初の「%1L0;」ですが、これは基本的には「8b_%1m0;」と同じ動作をします。だから基本的には今まで通りです。しかし、もし1番目の変数がレジスタ変数で、しかも0番目の変数と1番目の変数が同じ変数だったら、%1L0;は何も出力しないで、内部変数rにレジスタ変数のレジスタ番号を代入します。なお、この動作をしないときのrのデフォルト値は0です。
  • 次に「&8:」という記述が新しいです。これはプリフィクス(接頭語)で、次の%2m0にかかっています。r=0の時、このプリフィクスは何の効果もありません。だから普段は今まで通りの動作しかしません。しかしrが0以外の時は、このr*8の値を次の命令出力時に加算します。8なのは、&8:と書いてあるからです。もし9だったらr*9の値になりますし、1だったらr*1の値になります。
  • 最後の「%0S;」は、もしr=0だったら、「89_%0m0;」と同じ動作をします。しかしrが0以外なら何も出力しません。
  • では、%0と%1が同じ変数を指していて、しかもレジスタ変数だったら最終的にどんな出力になるでしょうか。ここではEBXレジスタのレジスタ変数だった場合を考えてみます。
  • EBXなので、r=3になります。%1L0と%0Sは何も出力しません。すると、結局1命令だけになり、
    03_%2m3;
  • に相当する機械語だけが出てくることになるのです。おお、これこそまさにEAXを経由せずに、EBXだけで演算が完結しているのです。
  • もし%0と%1のどちらもレジスタ変数だけど、でも同じ変数ではなかったら、つまり
    EBX = ESI + %2;
  • みたいな状態だったら、いつも通りのEAX経由の計算になります。
    EAX = ESI;
    EAX += %2;
    EBX = EAX;
  • これはまだだめじゃないかと思うかもしれません。まあその通りです。せめて「EBX = ESI; EBX += %2;」くらいにできたらいいですよね。そうなんです。しかし、もし%2がEBXだったらどうしましょう。最初の「EBX = ESI;」のせいでEBXの値が上書きされて値が変わってしまうので、うまく計算できなくなります。そういうことを考えるといろいろめんどくさくなってきたので、ひとまずこの件は保留にして、以前通りのEAX経由にしているというわけです。

  • と思ったけど、これを書いて説明しているうちに何とかなりそうな気がしてきました。
    %1L02; 03_&8:%2m0; %0S;
  • こう書かせることにします。それで、%1L02では%1と%0だけをみて挙動を決めるのではなく、必要に応じて%2も見ます。
    • (1)%0と%1がレジスタ変数で、しかも同一変数であれば、%1L02;は%2の内容にかかわらず、rにレジスタ番号をセットして、何も出力しません。
    • (2)上記以外で、%0がレジスタ変数であれば、%2が%0と等しいかどうかを調べます。もし等しくなければ、%0のレジスタ番号をrにセットして、%0=%1;の8b命令を出力します。
    • (3)上記のどちらでもなければ、r=0として、従来通りEAX=%1;の8b命令を出力します。
  • これで余計なEAX経由の計算は最小限にできそうです!

  • [1]opBin[]を以下の記述に差し替え
    String opBin[] = {  // 二項演算子のための機械語.
    !   "%1L11; 3b_&8:%2m0; 0f_94_c0; 0f_b6_c0; 89_%0m0;", // TcEEq   ==
    !   "%1L11; 3b_&8:%2m0; 0f_95_c0; 0f_b6_c0; 89_%0m0;", // TcNEq   !=
    !   "%1L11; 3b_&8:%2m0; 0f_9c_c0; 0f_b6_c0; 89_%0m0;", // TcLt    <
    !   "%1L11; 3b_&8:%2m0; 0f_9d_c0; 0f_b6_c0; 89_%0m0;", // TcGe    >=
    !   "%1L11; 3b_&8:%2m0; 0f_9e_c0; 0f_b6_c0; 89_%0m0;", // TcLe    <=
    !   "%1L11; 3b_&8:%2m0; 0f_9f_c0; 0f_b6_c0; 89_%0m0;", // TcGt    >
    !   "%1L02; 03_&8:%2m0; %0S;",                         // TcPlus  +
    !   "%1L02; 2b_&8:%2m0; %0S;",                         // TcMinus -
    !   "%1L02; 0f_af_&8:%2m0; %0S;",                      // TcAster *
        "8b_%1m0; 99; f7_%2m7; 89_%0m0;",                  // TcSlash /
        "8b_%1m0; 99; f7_%2m7; 89_%0m2;",                  // TcPerce %
    !   "%1L02; 23_&8:%2m0; %0S;",                         // TcAnd   &
    !   "%1L02; 8b_%2m1; d3_&1:f8; %0S;"                   // TcShr   >>
    };
  • [2]putIcX86_sub()関数に書き足し&変更
    void putIcX86_sub(String s, IntP a[])
    {
        int i, j, k;
    +   unsigned char addVal = 0, r = 0;
        for (i = 0; s[i] != 0; ) {
    !       if (s[i] == ' ' || s[i] == '\t' || s[i] == '_' || s[i] == ';' || s[i] == ':') {
                i++;
            } else if (getHex(s[i]) >= 0 && getHex(s[i + 1]) >= 0) { // 16進数2桁.
    !           *icq = getHex(s[i]) * 16 + getHex(s[i + 1]) + addVal;
                i += 2;
                icq++;
    +           addVal = 0;
    +       } else if (s[i] == '&') {
    +           addVal = r * (s[i + 1] - '0');
    +           i += 2;
            } else if (s[i] == '%') {
                j = s[i + 1] - '0';
                if (s[i + 2] == 'm') {	// mod r/m.
                    k = s[i + 3] - '0';
    +               i += 4;
    +subcmd_m:
                    if (regVar(a[j]) < 0) {
    !                   *icq = 0x05 + k * 8 + addVal;
       	             put32(icq + 1, (int) a[j]);
                        icq += 5;
                    } else {
    !                   *icq = 0xc0 + regVarNo[regVar(a[j])] + k * 8 + addVal;
                        icq++;
                    }
    +               addVal = 0;
                    continue;
                }
    +           if (s[i + 2] == 'L') {
    +               int l = s[i + 4] - '0';
    +               k = s[i + 3] - '0';
    +               i += 5;
    +               if (regVar(a[j]) >= 0 && a[j] == a[k]) {
    +                   r = regVarNo[regVar(a[j])];
    +               } else if (regVar(a[k]) >= 0 && a[k] != a[l]) {
    +                   k = r = regVarNo[regVar(a[k])];
    +                   *icq = 0x8b;
    +                   icq++;
    +                   goto subcmd_m;
    +               } else {
    +                   k = r = 0; // EAX.;
    +                   *icq = 0x8b;
    +                   icq++;
    +                   goto subcmd_m;
    +               }
    +               continue;
    +           }
    +           if (s[i + 2] == 'S') {
    +               if (r == 0) {
    +                   k = 0;
    +                   *icq = 0x89;
    +                   icq++;
    +                   i += 3;
    +                   goto subcmd_m;
    +               }
    +           }
                if (s[i + 2] == 'i') {	// int.
                    put32(icq, (int) a[j]);
                    icq += 4;
                }
                (中略)
            } else {
                printf("putIcX86: error: '%s'(%s)\n", s, &s[i]);
                exit(1);
            }
        }
    }
  • [3]ifgoto()関数のうちの2行を差し替え
    void ifgoto(int i, int not, int label)
    {
        int j = wpc[i];
        if (j + 3 == wpc1[i] && TcEEq <= tc[j + 1] && tc[j + 1] <= TcGt) { // 条件式の長さが3トークンで、真ん中が比較演算子だったら.
    !       putIcX86("%2L22; 3b_&8:%3m0; 0f_%0c_%1l;", (IntP) condCode[(tc[j + 1] - TcEEq) ^ not], &var[label], &var[tc[j]], &var[tc[j + 2]]);
        } else {
            i = expr(i);
    !       putIcX86("%2L22; 85_&9:c0; 0f_%0c_%1l;", (IntP) (0x85 - not), &var[label], &var[i], 0);
            tmpFree(i);
        }
    }
  • [3]phrCmpPutIcX86()関数の一部を差し替え
            for (i = 0; i < lenExpr; i++) {
    !           putIcX86("%0L00; 89_&8:44_24_%1c;", &var[e[i]], (IntP) (i * 4), 0, 0);
            }
  • [4]compile()関数の一部を差し替え(1)
            if (phrCmp( 1, "!!*0 = !!*1;", pc)) { // 単純代入.
    +           if (regVar(&var[tc[wpc[0]]]) < 0) {
    !               putIcX86("%1L11; 89_&8:%0m0;", &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0);
    +           } else {
    +               putIcX86("%0L00; 8b_&8:%1m0;", &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0);
    +           }
            } else if (phrCmp(10, "!!*0 = !!*1 + 1; if (!!*2 < !!*3) goto !!*4;", pc) && tc[wpc[0]] == tc[wpc[1]] && tc[wpc[0]] == tc[wpc[2]]) {
    !           putIcX86("%1L11; &1:40; %1S; 3b_&8:%2m0; 0f_8c_%0l;", &var[tc[wpc[4]]], &var[tc[wpc[0]]], &var[tc[wpc[3]]], 0);
            } else if (phrCmp( 9, "!!*0 = !!*1 + 1;", pc) && tc[wpc[0]] == tc[wpc[1]]) {  // 高速化のために+1専用の命令を用意(せこくてすみません).
    !           putIcX86("%0L00; &1:40; %0S;", &var[tc[wpc[0]]], 0, 0, 0);
  • [5]compile()関数の一部を差し替え(2)
            } else if (phrCmp(15, "}", pc) && binf[bd] == BlkFor) {
                defLabel(binf[bd + ForCont]);	// ラベルに対応するicqを記録しておく.
                i = binf[bd + ForWpc01];
                j = binf[bd + ForWpc02];
                if (i + 3 == binf[bd + ForWpc11] && j + 2 == binf[bd + ForWpc12] && tc[i] == tc[j] && tc[i + 1] == TcLt && tc[j + 1] == TcPlPlus) {
                    // !!***1が「i < ?」かつ、!!***2が「i++」だったら(変数名はiじゃなくてもいいけど、共通である必要がある).
    !               putIcX86("%1L11; &1:40; %1S; 3b_&8:%2m0; 0f_8c_%0l;", &var[binf[bd + ForLopBgn]], &var[tc[i]], &var[tc[i + 2]], 0);
                } else {
                    wpc [1] = binf[bd + ForWpc01];
                    wpc1[1] = binf[bd + ForWpc11];
                    wpc [2] = binf[bd + ForWpc02];
                    wpc1[2] = binf[bd + ForWpc12];
                    e2 = expr(2);
                    if (wpc[1] < wpc1[1]) {	// !!***1に何らかの式が書いてあった.
                        ifgoto(1, 0, binf[bd + ForLopBgn]);
                    } else {
                        putIcX86("e9_%0l;", &var[binf[bd + ForLopBgn]], 0, 0, 0);
                    }
                }
                defLabel(binf[bd + ForBrk]);	// ラベルに対応するicqを記録しておく.
                lbd = binf[bd+ ForLbd0]; // 以前の値を復元.
                bd -= BInfSiz;
  • [6]compile()関数に2行を追加
    +       } else if (phrCmp(38, "!!*3 = mul64shr(!!*0, !!*1, !!*2);", pc) && strtol(ts[tc[wpc[2]]], 0, 0) > 0) {
    +           putIcX86("8b_%0m0; f7_%1m5; 0f_ac_d0_%2c; 89_%3m0;", &var[tc[wpc[0]]], &var[tc[wpc[1]]], (IntP) strtol(ts[tc[wpc[2]]], 0, 0), &var[tc[wpc[3]]]);

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

(2) プログラムの説明

  • ここでプログラムの説明を書こうと思ったのですが、もう大体のことは先に説明済みでした。
  • だからもう些末なことしかのこっていないのですが、mul64shr()命令がシンプルに使われていた場合は、シンプルな機械語を出すようにしてみました([6]の追加のところです)。これは二項演算子についてシンプルな場合に特別処理しているのと同じです。
  • この特別処理を書くことによって、演算結果をいったん一時変数に格納して、そこから左辺の変数に代入するということがなくなり、演算結果を直接左辺の変数に代入するようになります。

(3) 効果の確認

  • まずはhl3.txtのコンパイル結果を確認してみます。
    >regVar(0 i)
    
    >codedump 1
    
    (len=0)
    
    >run hl3.txt
    8b 1d 0c 0a 42 00 43 3b 1d 28 0b 42 00 0f 8c f3 ff ff ff e8 cc 23 f6 fd
    (len=24)
  • このコードを見やすい形で書き直すとこうなります。
        8b 1d 0c 0a 42 00; // EBX = 0;
    label:
        43;                // EBX++;
        3b 1d 28 0b 42 00; // if (EBX < 1億) goto label;
        0f 8c f3 ff ff ff:
        e8 cc 23 f8 fd;    // call time;
  • おお、これはまさに上記の「理想形」です。とてもうまくいっているようです。
  • 肝心の実行速度も確認しました。
ページ名名前行数.exeの大きさ説明速度のめやす1速度のめやす2
[ a21_txt01 ]HL-1~HL-9a49行~772行6.0KB~20.0KB「10日くらいでできる!プログラミング言語自作入門」1520倍~5.5倍6.4倍
a21_txt02HL-11692行14.5KBJITコンパイラ版1号計測不能計測不能
a21_txt02_1aHL-11a707行15.0KB簡単な演算もサポート計測不能計測不能
a21_txt02_2HL-12745行16.0KBループ速度の測定ができるところまで5.3倍計測不能
a21_txt02_2aHL-12a766行16.5KBcodedumpコマンドと、codeコマンドの追加5.3倍計測不能
a21_txt02_3HL-13827行21.0KB配列以外は全部JITコンパイラ対応させる(mandel.cで速さを実感!)5.3倍2.0倍
a21_txt02_3aHL-13a819行21.0KB配列もJITコンパイラ対応させる(ついに機能的にはHL-9a相当に!)5.3倍2.0倍
a21_txt02_4HL-14865行21.5KBレジスタ変数の導入(46行しか増えない簡単な改造だけど、結構な効果がある)2.0倍1.2倍
a21_txt02_4aHL-14a906行22.5KBレジスタ変数のための最適化(さらに41行を追加してすごい速さに!)1.0倍0.9倍

次回に続く

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-07-03 (土) 15:59:15 (85d)