a21_txt02_10a の編集

* 「10日くらいでできる！プログラミング言語自作入門」の続編#1-10a
-(by [[K]], 2021.05.12)

** (1) HL-20a
-HL-20は期待通りに速くなってくれて大変うれしいのですが、その生成コードの質はまだ「いまいち」になっています。具体的に見てみましょう。
 >regVar(0, i)
 
 >codedump 1
 
 (len=0)
 
 >run hl3.txt
 48 8b 85 18 00 00 00 48 89 c3 48 8b c3 48 ff c0 48 89 c3 48 3b 85 e0 02 00 00 0f 8c ea ff ff ff 48 ff 95 78 01 00 00
 (len=39)
-これは、1億回ループのプログラムをcodedump 1の状態でrunした結果です（HL-3参照→[[a21_txt01_3]]）。このコードを見やすい形で書き直すとこうなります。
     48 8b 85 18 00 00 00;  // RAX = 0;
     48 89 c3;              // RBX = RAX;
 label:
     48 8b c3;              // RAX = RBX;
     48 ff c0;              // RAX++;
     48 89 c3;              // RBX = RAX;
     48 3b 85 e0 02 00 00;  // if (RAX < 1億) goto label;
     0f 8c ea ff ff ff;
     48 ff 95 78 01 00 00;  // call sub_time
-まあこれは、HL-20のアルゴリズムを考えれば、こうなって当然なのですが、しかし「あちゃー」と言いたくなるような結果でもあるのです。
-どこが低品質なのかというと、RBXレジスタを使っているにもかかわらず（＝メモリじゃないのに）、わざわざRAXに持ち替えてから処理をしているところがだめなのです。
-理想を考えると以下のようになります。
     48 8b 9d 18 00 00 00;  // RBX = 0;
 label:
     48 ff c3;              // RBX++;
     48 3b 9d e0 02 00 00;  // if (RBX < 1億) goto label;
     0f 8c f0 ff ff ff;
     48 ff 95 78 01 00 00;  // call sub_time

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

----
-HL-14の段階では、加算の二項演算子はこうなっています（opBin[]より）。
 %R_8b_%1m0; %R_03_%2m0; %R_89_%0m0;
-これをHL-14aでは以下のようにします。
 %1L0; %R_03_&8:%2m0; %0S;
-これの意味を説明します。
-まず最初の「%1L0;」ですが、これは基本的には「%R_8b_%1m0;」と同じ動作をします。だから基本的には今まで通りです。しかし、もし1番目の変数がレジスタ変数で、しかも0番目の変数と1番目の変数が同じ変数だったら、%1L0;は何も出力しないで、内部変数rにレジスタ変数のレジスタ番号を代入します。なお、この動作をしないときのrのデフォルト値は0です。
-次に「&48:」という記述が新しいです。これはプリフィクス（接頭語）で、次の%2m0にかかっています。r=0の時、このプリフィクスは何の効果もありません。だから普段は今まで通りの動作しかしません。しかしrが0以外の時は、以下の動作をします。
--最初の数字4は、もしrが8以上だったら、REXのところに4を加算せよ、という指示です。
--次の数字8は、r*8を次の命令出力時に加算せよ、という指示です。
-最後の「%0S;」は、もしr=0だったら、「%R_89_%0m0;」と同じ動作をします。しかしrが0以外なら何も出力しません。

-では、%0と%1が同じ変数を指していて、しかもレジスタ変数だったら最終的にどんな出力になるでしょうか。ここではRBXレジスタのレジスタ変数だった場合を考えてみます。
-RBXなので、r=3になります。%1L0と%0Sは何も出力しません。すると、結局1命令だけになり、
 %R_03_%2m3;
-に相当する機械語だけが出てくることになるのです。おお、これこそまさにRAXを経由せずに、RBXだけで演算が完結しているのです。

-もし%0と%1のどちらもレジスタ変数だけど、でも同じ変数ではなかったら、つまり
 RBX = RSI + %2;
-みたいな状態だったら、いつも通りのRAX経由の計算になります。
 RAX = RSI;
 RAX += %2;
 RBX = RAX;

-これはまだだめじゃないかと思うかもしれません。まあその通りです。せめて「RBX = RSI; RBX += %2;」くらいにできたらいいですよね。そうなんです。しかし、もし%2がRBXだったらどうしましょう。最初の「RBX = RSI;」のせいでRBXの値が上書きされて値が変わってしまうので、うまく計算できなくなります。そういうことを考えるといろいろめんどくさくなってきたので、ひとまずこの件は保留にして、以前通りのRAX経由にしているというわけです。
----
-と思ったけど、これを書いて説明しているうちに何とかなりそうな気がしてきました。
 %1L02; %R_03_&48:%2m0; %0S;
-こう書かせることにします。それで、%1L02では%1と%0だけをみて挙動を決めるのではなく、必要に応じて%2も見ます。
--(1)%0と%1がレジスタ変数で、しかも同一変数であれば、%1L02;は%2の内容にかかわらず、rにレジスタ番号をセットして、何も出力しません。
--(2)上記以外で、%0がレジスタ変数であれば、%2が%0と等しいかどうかを調べます。もし等しくなければ、%0のレジスタ番号をrにセットして、%0=%1;の8b命令を出力します。
--(3)上記のどちらでもなければ、r=0として、従来通りRAX=%1;の8b命令を出力します。
-これで余計なRAX経由の計算は最小限にできそうです！
//  zx = xx + cx; に効いたらしい。
----
-[1]opBin[]を以下の記述に差し替え
 String opBin[] = {  // 二項演算子のための機械語.
 !   "%1L11; %R_3b_&48:%2m0; 0f_94_c0; 0f_b6_c0; %R_89_%0m0;", // TcEEq   ==
 !   "%1L11; %R_3b_&48:%2m0; 0f_95_c0; 0f_b6_c0; %R_89_%0m0;", // TcNEq   !=
 !   "%1L11; %R_3b_&48:%2m0; 0f_9c_c0; 0f_b6_c0; %R_89_%0m0;", // TcLt    <
 !   "%1L11; %R_3b_&48:%2m0; 0f_9d_c0; 0f_b6_c0; %R_89_%0m0;", // TcGe    >=
 !   "%1L11; %R_3b_&48:%2m0; 0f_9e_c0; 0f_b6_c0; %R_89_%0m0;", // TcLe    <=
 !   "%1L11; %R_3b_&48:%2m0; 0f_9f_c0; 0f_b6_c0; %R_89_%0m0;", // TcGt    >
 !   "%1L02; %R_03_&48:%2m0; %0S;",                            // TcPlus  +
 !   "%1L02; %R_2b_&48:%2m0; %0S;",                            // TcMinus -
 !   "%1L02; %R_0f_af_&48:%2m0; %0S;",                         // TcAster *
     "%R_8b_%1m0; %R_99; %R_f7_%2m7; %R_89_%0m0;",             // TcSlash /
     "%R_8b_%1m0; %R_99; %R_f7_%2m7; %R_89_%0m2;",             // TcPerce %
 !   "%1L02; %R_23_&48:%2m0; %0S;",                            // TcAnd   &
 !   "%1L02; %R_8b_%2m1; %R_d3_&11:f8; %0S;"                   // TcShr   >>
 };
-[2]putIcX64_sub()関数に書き足し＆変更
 void putIcX64_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] == '&') {
 +           if (r >= 8) {
 +               *putIcX64_rex += s[i + 1] - '0';
 +           }
 +           addVal = (r & 7) * (s[i + 2] - '0');
 +           i += 3;
         } else if (s[i] == '%') {
             if (s[i + 1] == 'R') {
                 putIcX64_rex = icq;
                 *icq = 0x48;
                 icq++;
                 i += 2;
                 continue;
             }
             j = s[i + 1] - '0';
             if (s[i + 2] == 'm') {	// mod r/m.
                 k = s[i + 3] - '0';
                 if (s[i + 3] >= 'a') { // もしかしたらこの記述は最後まで出番がないかも.
                     k = s[i + 3] - 'a' + 10;
                 }
 +               i += 4;
 +subcmd_m:
                 if (k >= 8) {
                     *putIcX64_rex += 4;
                     k -= 8;
                 }
                 int rv = regVar(a[j]);
                 if (rv < 0) {
 !                   *icq = 0x85 + k * 8 + addVal;
                     put32(icq + 1, (a[j] - var) * 8);
                     icq += 5;
                 } else {
                     rv = regVarNo[rv];
                     if (rv >= 8) {
                         *putIcX64_rex += 1;
                         rv -= 8;
                     }
 !                   *icq = 0xc0 + rv + 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[0] = 0x48;
 +                   icq[1] = 0x8b;
 +                   putIcX64_rex = icq;
 +                   icq += 2;
 +                   goto subcmd_m;
 +               } else {
 +                   k = r = 0; // RAX.;
 +                   icq[0] = 0x48;
 +                   icq[1] = 0x8b;
 +                   putIcX64_rex = icq;
 +                   icq += 2;
 +                   goto subcmd_m;
 +               }
 +               continue;
 +           }
 +           if (s[i + 2] == 'S') {
 +               if (r == 0) {
 +                   k = 0;
 +                   icq[0] = 0x48;
 +                   icq[1] = 0x89;
 +                   putIcX64_rex = icq;
 +                   icq += 2;
 +                   i += 3;
 +                   goto subcmd_m;
 +               }
 +           }
             if (s[i + 2] == 'i') {	// int.
                 put32(icq, (int) a[j]);
                 icq += 4;
             }
             （中略）
         } else {
             printf("putIcX64: 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トークンで、真ん中が比較演算子だったら.
 !       putIcX64("%2L22; %R_3b_&48:%3m0; 0f_%0c_%1l;", (IntP) (AInt) condCode[(tc[j + 1] - TcEEq) ^ not], &var[label], &var[tc[j]], &var[tc[j + 2]]);
     } else {
         i = expr(i);
 !       putIcX64("%2L22; %R_85_&59:c0; 0f_%0c_%1l;", (IntP) (AInt) (0x85 - not), &var[label], &var[i], 0);
         tmpFree(i);
     }
 }
-[3]phrCmpPutIcX86()関数の一部を差し替え(1)
             for (i = 4; i < lenExpr; i++) {
 !               putIcX64("%0L00; %R_89_&48:44_24_%1c;", &var[e[i]], (IntP) ((AInt) i * 8), 0, 0);
             }
-[4]phrCmpPutIcX86()関数の一部を差し替え(2)
             for (i = 6; i < lenExpr; i++) {
 !               putIcX64("%0L00; %R_89_&48:44_24_%1c;", &var[e[i]], (IntP) ((AInt) (i - 6) * 8), 0, 0);
             }

-[5]compile()関数の一部を差し替え(1)
         if (phrCmp( 1, "!!*0 = !!*1;", pc)) { // 単純代入.
 +           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);
 +           }
         } 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]]) {
 !           putIcX64("%1L11; %R_ff_&11:c0; %1S; %R_3b_&48:%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専用の命令を用意(せこくてすみません).
 !           putIcX64("%0L00; %R_ff_&11:c0; %0S;", &var[tc[wpc[0]]], 0, 0, 0);
-[6]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じゃなくてもいいけど、共通である必要がある）.
 !               putIcX64("%1L11; %R_ff_&11:c0; %1S; %R_3b_&48:%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 {
                     putIcX64("e9_%0l;", &var[binf[bd + ForLopBgn]], 0, 0, 0);
                 }
             }
             defLabel(binf[bd + ForBrk]);	// ラベルに対応するicqを記録しておく.
             lbd = binf[bd+ ForLbd0]; // 以前の値を復元.
             bd -= BInfSiz;
-[7]compile()関数に2行を追加
 +       } else if (phrCmp(38, "!!*3 = mul64shr(!!*0, !!*1, !!*2);", pc) && strtol(ts[tc[wpc[2]]], 0, 0) > 0) {
 +           putIcX64("%0L31; %R_0f_af_&48:%1m0; %R_c1_&11:f8_%2c; %3S;", &var[tc[wpc[0]]], &var[tc[wpc[1]]], (IntP) (AInt) strtol(ts[tc[wpc[2]]], 0, 0), &var[tc[wpc[3]]]);

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

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

** (3) 効果の確認
-まずはhl3.txtのコンパイル結果を確認してみます。
 >regVar(0, i)
 
 >codedump 1
 
 (len=0)
 
 >run hl3.txt
 48 8b 9d 18 00 00 00 48 ff c3 48 3b 9d e0 02 00 00 0f 8c f0 ff ff ff 48 ff 95 78 01 00 00
 (len=30)
-このコードを見やすい形で書き直すとこうなります。
     48 8b 9d 18 00 00 00; // RBX = 0;
 label:
     48 ff c3;             // RBX++;
     48 3b 9d e0 02 00 00; // if (RBX < 1億) goto label;
     0f 8c f0 ff ff ff;
     48 ff 95 78 01 00 00; // call time;
-おお、これはまさに上記の「理想形」です。とてもうまくいっているようです。

-肝心の実行速度も確認しました。

-あれ？10億回ループは速くなっていませんね・・・。
-ということでHL-20bでそれを解決します。

** 次回に続く
-次回: [[a21_txt02_10b]]

*こめんと欄
#comment