a21_txt02_10 のバックアップ(No.2)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
a21_txt02_10 へ行く。
- 1 (2021-05-12 (水) 15:21:36)
- 2 (2021-05-12 (水) 16:13:34)

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

(by K, 2021.05.12)

(1) HL-20

さて、とにかくJITコンパイラにはなったものの、生成している機械語の質が低いので、gcc-O3と比べるとまだまだ速度で負けています。

ページ名	名前	行数	.exeの大きさ	説明	速度のめやす1	速度のめやす2
[ a21_txt01 ]	HL-1～HL-9a	49行～772行	6.0KB～20.0KB	「10日くらいでできる！プログラミング言語自作入門」	1520倍～5.5倍	6.4倍
a21_txt02_7	HL-17	741行	25.0KB	x64に対応したJITコンパイラ第1号	計測不能	計測不能
a21_txt02_7a	HL-17a	756行	26.0KB	簡単な演算もサポート	計測不能	計測不能
a21_txt02_8	HL-18	795行	27.0KB	ループ速度の測定ができるところまで	4.2倍	計測不能
a21_txt02_8a	HL-18a	816行	27.5KB	codedumpコマンドと、codeコマンドの追加	4.2倍	計測不能
a21_txt02_9	HL-19	893行	35.5KB	配列以外は全部JITコンパイラ対応させる（mandel.cで速さを実感！）	4.2倍	1.8倍
a21_txt02_9a	HL-19a	899行	36.0KB	配列もJITコンパイラ対応させる（ついに機能的にはHL-9a相当に！）	4.2倍	1.8倍

さすがに追いついたり追い越したりはできないと思いますが、でももうちょっと近づきたいとは思うので、ここからしばらくは最適化をやってスピードアップをしたいと思います。

最適化をどこからやるかですが、おそらく効果が一番あるのは「レジスタ変数」のサポートです。HL-19aでは、変数はすべてメモリ上にありました。これをRAXレジスタに読み込ませて、演算をして、RAXに結果が生成されて、それをメモリ書き戻しています。多くの場合この一連の処理の中で一番のボトルネックはメモリへの読み書きで、これをなくしてレジスタ内の演算だけにすればきっと速くなると思われます。
x64の場合、演算に使えそうなレジスタは、RAXのほかにRCX、RDX、RBX、RBP、RSI、RDI、R08～R15があって合計15個です。でもこのうちのRAX、RCX、RDXの3つは、割り算やシフト命令や配列アクセスなどで使用するために、そこそこの頻度で値が壊される危険があります。またHL-19aではRBPも var[ ] へのアクセスのために多用しているので使えません。
その上、関数呼び出しで破壊されるレジスタがたくさんあります。結局、自由に使えるのは以下のものだけになります。
- [ABI_MSW64のとき] RBX、RSI、RDI、R12～R15 （合計7つ）
- [ABI_SYSV64のとき] RBX、R12～R15 （合計5つ）

一方で、プログラムで使われる変数は5個よりも多いことが普通で、だからすべての変数をレジスタ変数に割り当てることはできません。一般には使用頻度の高い変数をレジスタ変数に割り当てることになります。・・・それで、どの変数をレジスタ変数に割り当てるべきか、gccなどのコンパイラはプログラムを解析してすごい努力をして決定しています。おそらコンパイルに時間がかかっている主たる理由はこれなのではないかと私は思っています。
ではHL-20ではどうしましょうか。人間が見れば、この変数をレジスタ変数にしたらよさそうだなっていうのは結構簡単にわかります。ループの最も内側で使っている変数とかを速くすればいいだけなのです。しかしそれを自動判定するプログラムは、きっとすごく大変なので、私はここで扱いたくありません。ということで、人間が自由に指定することにします。機械が得意なことは機械がやって、人間が得意なことは人間がやればいいのです。
ということで regVar()コマンドを作ります。
```
regVar(0, x); regVar(1, y); regVar(2, z);
```
とすると、xを優先度0でレジスタ変数化してほしくて（＝最優先）、yを優先度1でレジスタ変数化してほしくて、zを優先度2でレジスタ変数化してほしい、ということにしました。というのは、HLシリーズはx64以外のCPUにも対応していくかもしれません。そしたら使えるレジスタ変数の数もきっと変わるでしょう。その場合は優先度を見て、順番に割り当てさせることにします。もしレジスタが足りなくなったら、優先度の低いものについてはメモリ割り付けのままにします。
上記のように三回もregVarと入力するのは面倒なので、
```
regVar(0, x, y, z);
```
という省略形も使えるようにします。
関数の形にしているのは、プログラム内で使った時にC言語との互換性を維持できるようにするためです。C言語で使うときは、
```
#define regVar(...)
```
などと書いて、regVar()命令を無視させるようにします。

[1]putIcX64_sub()関数の前に以下を追加

#if (ABI_MSW64 != 0)
    #define RegVarLen 7
    int regVarNo[7] = { 3, 6, 7, 12, 13, 14, 15 }; // レジスタ変数番号から、レジスタ番号に変換.
#elif (ABI_SYSV64 != 0)
    #define RegVarLen 5
    int regVarNo[5] = { 3, 12, 13, 14, 15 }; // レジスタ変数番号から、レジスタ番号に変換.
#endif
IntP regVarTbl[RegVarLen]; // レジスタ変数の割り当て状況を記憶.

int regVar(IntP v) // もし変数vがレジスタに割り当てられていれば、0～7を返す. そうでなければ-1を返す.
{
    int i;
    for (i = 0; i < RegVarLen; i++) {
        if (regVarTbl[i] == v)
            return i;
        }
        return -1;
}

[2]putIcX64_sub()関数の一部を改造

            if (s[i + 2] == 'm') {	// mod r/m.
                k = s[i + 3] - '0';
                if (s[i + 3] >= 'a') { // もしかしたらこの記述は最後まで出番がないかも.
                    k = s[i + 3] - 'a' + 10;
                }
+               if (k >= 8) {
+                   *putIcX64_rex += 4;
+                   k -= 8;
+               }
+               int rv = regVar(a[j]);
+               if (rv < 0) {
                    *icq = 0x85 + k * 8;
                    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;
+                   icq++;
+               }
                i += 4;
                continue;
            }

[3]putIcX64()関数の宣言の後に以下を追加

enum { RvSave = 0x89, RvLoad = 0x8b };

void regVarSaveLoad(int op) // レジスタ変数を準備するor書き戻す.
{
    int i, rv, rex;
    for (i = 0; i < RegVarLen; i++) {
        if (regVarTbl[i] != 0) {
            rv = regVarNo[i];
            rex = 0x48;
            if (rv >= 8) {
                rex = 0x48 + 4;
                rv -= 8;
            }
            putIcX64("%0c_%1c_%2c_%3i;", (IntP) (AInt) rex, (IntP) (AInt) op, (IntP) (AInt) (0x85 + rv * 8), (IntP) (AInt) ((regVarTbl[i] - var) * 8));
        }
    }
}

[4]compile()関数に1行追加(1)

    icq = ic;
    jp = 0;
    putIcX64("41_57; 41_56; 41_55; 41_54; 41_53; 41_52;", 0, 0, 0, 0);
    putIcX64("41_51; 41_50; 57; 56; 55; 54; 53; 52; 51; 50;", 0, 0, 0, 0);
    putIcX64("%R_81_ec_f8_01_00_00; %R_bd_%0q;", var, 0, 0, 0);
+   regVarSaveLoad(RvLoad);
    dump0 = icq;

[5]compile()関数に14行追加

+       } else if (phrCmp(37, "regVar(!!*0", pc)) {
+           i = tc[wpc[0]] - Tc0;
+           regVarSaveLoad(RvSave);
+           for (pc = ppc1; tc[pc] != TcBrCls; pc++) {
+               if (tc[pc] == TcComma) continue;
+               if (0 <= i && i < RegVarLen) {
+                   regVarTbl[i] = &var[tc[pc]];
+                   if (tc[pc] == Tc0)
+                       regVarTbl[i] = 0;
+               }
+               i++;
+           }
+           regVarSaveLoad(RvLoad);
+           ppc1 = pc + 2;

[6]compile()関数に1行追加(2)

    defLabel(toExit);
    dump1 = icq;
+   regVarSaveLoad(RvSave);
    putIcX64("%R_81_c4_f8_01_00_00;", 0, 0, 0, 0);
    putIcX64("58; 59; 5a; 5b; 5c; 5d; 5e; 5f; 41_58; 41_59;", 0, 0, 0, 0);
    putIcX64("41_5a; 41_5b; 41_5c; 41_5d; 41_5e; 41_5f; c3;", 0, 0, 0, 0);
    icq1 = icq;

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

↑

(2) プログラムの説明

今回の改造で最も重要なのは、putIcX86_sub()関数の改造のところです。

            if (s[i + 2] == 'm') {	// mod r/m.
                k = s[i + 3] - '0';
                if (s[i + 3] >= 'a') { // もしかしたらこの記述は最後まで出番がないかも.
                    k = s[i + 3] - 'a' + 10;
                }
+               if (k >= 8) {
+                   *putIcX64_rex += 4;
+                   k -= 8;
+               }
+               int rv = regVar(a[j]);
+               if (rv < 0) {
                    *icq = 0x85 + k * 8;
                    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;
+                   icq++;
+               }
                i += 4;
                continue;
            }

これはつまり、%mで変数を指定されたときにレジスタ変数でなければ従来通りの機械語を生成しますが、レジスタ変数であればmod r/mのmodをメモリ指定モードではなくレジスタ指定モードに切り替えて、r/mのところでレジスタ番号を指定するようにしているのです。
またレジスタ番号が8以上になってあふれた時は、REX命令のところに+1して、レジスタ番号が8以上であることをCPUに伝えています。

あとはcompile()の最初のところで、レジスタ変数の場合はメモリ上にある変数の値をレジスタに読み込ませます。そしてcompile()の最後のところで、レジスタの内容をメモリに書き戻します。そうすれば次回実行時にもレジスタ変数の値は引き継がれます。

またregVar()命令でレジスタ変数の設定状況を変更するときは、まずregVarSaveLoad()でレジスタ変数の値をメモリ書き戻させて、その次に設定を変更し、最後に変更された設定に従ってレジスタ変数を読み込ませています。

なおregVar()命令で、変数名の代わりに0を指定すると、その優先度のレジスタ変数の設定は解除されます。つまり regVar(0, 0, 0, 0, 0, 0, 0, 0); とすればレジスタ変数を一切指定していない初期状態に戻るというわけです。

（以下編集中）

↑

(3) さて、これでどのくらい高速化されるか？

10億回ループを実行する前に、 regVar(0, i); を実行しておきます。
また、 run mandel.c する前には、 regVar(0, zx, zy, xx, yy, t, cx, cy); を実行しておきます。

ページ名	名前	行数	.exeの大きさ	説明	速度のめやす1	速度のめやす2
[ a21_txt01 ]	HL-1～HL-9a	49行～772行	6.0KB～20.0KB	「10日くらいでできる！プログラミング言語自作入門」	1520倍～5.5倍	6.4倍
a21_txt02_7	HL-17	741行	25.0KB	x64に対応したJITコンパイラ第1号	計測不能	計測不能
a21_txt02_7a	HL-17a	756行	26.0KB	簡単な演算もサポート	計測不能	計測不能
a21_txt02_8	HL-18	795行	27.0KB	ループ速度の測定ができるところまで	4.2倍	計測不能
a21_txt02_8a	HL-18a	816行	27.5KB	codedumpコマンドと、codeコマンドの追加	4.2倍	計測不能
a21_txt02_9	HL-19	893行	35.5KB	配列以外は全部JITコンパイラ対応させる（mandel.cで速さを実感！）	4.2倍	1.8倍
a21_txt02_9a	HL-19a	899行	36.0KB	配列もJITコンパイラ対応させる（ついに機能的にはHL-9a相当に！）	4.2倍	1.8倍
a21_txt02_10	HL-20	964行	36.0KB	レジスタ変数の導入（65行しか増えない簡単な改造だけど、結構な効果がある）	2.1倍	1.0倍

はっきりと効果が出ています！！

↑

次回に続く

次回: a21_txt02_10a

↑

こめんと欄

コメント	お名前	NameLink