a21_txt02_12a のバックアップ(No.4)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
a21_txt02_12a へ行く。
- 1 (2021-05-18 (火) 11:46:40)
- 2 (2021-05-18 (火) 11:46:40)
- 3 (2021-05-20 (木) 23:34:02)
- 4 (2021-05-22 (土) 00:56:27)

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

(by K, 2021.05.18)

(1) HL-22a

HL-22までで、「簡単にできる」かつ「そこそこ効果がある」なことは全部やってしまったと思っていたのですが、急に一つ思いつきました。
機械語の中で%mを使ってメモリアクセスしている回数を変数別に集計したら面白いのではないか、と。・・・さっそくやってみます。
これがわかれば、出現頻度が高いものからregVarに指定すれば、コードは最も小さくできるはずです（ただ、それはサイズ優先であって、使用頻度を優先したものではないので、性能が高いかどうかは不確かです。使用頻度を重視するならやはりコードを読んで重そうなところを探す必要があります）。

[1]optimizerX64()関数の宣言の直前に、以下の一行を追加
```
int vc[MAX_TC + 1];
```

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

        if (icq0[0] == 0x48 && icq0[1] == 0x8b && isConstM(&icq0[2])) { // 48_8b.
            AInt reg = (icq0[2] >> 3) & 7, i = getConstM(&icq0[2]);
+           vc[get32(&icq0[3]) / 8]--;
            icq = icq0;
            if (i == 0)            { putIcX64("31_%0c", (IntP) (reg * 9 + 0xc0), 0, 0, 0); }
            else if (i >> 32 == 0) { putIcX64("%0c_%1i", (IntP) (reg + 0xb8), (IntP) i, 0, 0); }
            else if (is32bit(i))   { putIcX64("48_c7_%0c_%1i", (IntP) (reg + 0xc0), (IntP) i, 0, 0); }
            else                   { putIcX64("48_%0c_%1q", (IntP) (reg + 0xb8), (IntP) i, 0, 0); }
        }
        if (icq0[0] == 0x4c && icq0[1] == 0x8b && isConstM(&icq0[2])) { // 4c_8b.
            AInt reg = (icq0[2] >> 3) & 7, i = getConstM(&icq0[2]);
+           vc[get32(&icq0[3]) / 8]--;
            icq = icq0;
            if (i == 0)            { putIcX64("4d_31_%0c", (IntP) (reg * 9 + 0xc0), 0, 0, 0); }
            else if (i >> 32 == 0) { putIcX64("41_%0c_%1i", (IntP) (reg + 0xb8), (IntP) i, 0, 0); }
            else if (is32bit(i))   { putIcX64("49_c7_%0c_%1i", (IntP) (reg + 0xc0), (IntP) i, 0, 0); }
            else                   { putIcX64("49_%0c_%1q", (IntP) (reg + 0xb8), (IntP) i, 0, 0); }
        }
        if (icq0[0] == 0x48 && icq0[1] <= 0x3f && (icq0[1] & 7) == 3 && isConstM(&icq0[2]) && is32bit(getConstM(&icq0[2]))) { // 03, 0b, 13, 1b, 23, 2b, 33, 3b.
            AInt reg = (icq0[2] >> 3) & 7, i = getConstM(&icq0[2]);
+           vc[get32(&icq0[3]) / 8]--;
            icq = icq0;
            if (-0x80 <= i && i <= 0x7f) { putIcX64("48_83_%0c_%1c", (IntP) ((icq0[1] & 0x38) + reg + 0xc0), (IntP) i, 0, 0); }
            else                         { putIcX64("48_81_%0c_%1i", (IntP) ((icq0[1] & 0x38) + reg + 0xc0), (IntP) i, 0, 0); }
        }
        if (icq0[0] == 0x4c && icq0[1] <= 0x3f && (icq0[1] & 7) == 3 && isConstM(&icq0[2]) && is32bit(getConstM(&icq0[2]))) { // 03, 0b, 13, 1b, 23, 2b, 33, 3b.
            AInt reg = (icq0[2] >> 3) & 7, i = getConstM(&icq0[2]);
+           vc[get32(&icq0[3]) / 8]--;
            icq = icq0;
            if (-0x80 <= i && i <= 0x7f) { putIcX64("49_83_%0c_%1c", (IntP) ((icq0[1] & 0x38) + reg + 0xc0), (IntP) i, 0, 0); }
            else                         { putIcX64("49_81_%0c_%1i", (IntP) ((icq0[1] & 0x38) + reg + 0xc0), (IntP) i, 0, 0); }
        }
        if (icq0[0] == 0x48 && icq0[1] == 0x0f && icq0[2] == 0xaf && isConstM(&icq0[3]) && is32bit(getConstM(&icq0[3]))) { // 0f_af.
            AInt reg = (icq0[3] >> 3) & 7, i = getConstM(&icq0[3]);
+           vc[get32(&icq0[4]) / 8]--;
            icq = icq0;
            if (-0x80 <= i && i <= 0x7f) { putIcX64("48_6b_%0c_%1c", (IntP) (reg * 9 + 0xc0), (IntP) i, 0, 0); }
            else                         { putIcX64("48_69_%0c_%1i", (IntP) (reg * 9 + 0xc0), (IntP) i, 0, 0); }
        }
        if (icq0[0] == 0x4c && icq0[1] == 0x0f && icq0[2] == 0xaf && isConstM(&icq0[3]) && is32bit(getConstM(&icq0[3]))) { // 0f_af.
            AInt reg = (icq0[3] >> 3) & 7, i = getConstM(&icq0[3]);
+           vc[get32(&icq0[4]) / 8]--;
            icq = icq0;
            if (-0x80 <= i && i <= 0x7f) { putIcX64("4d_6b_%0c_%1c", (IntP) (reg * 9 + 0xc0), (IntP) i, 0, 0); }
            else                         { putIcX64("4d_69_%0c_%1i", (IntP) (reg * 9 + 0xc0), (IntP) i, 0, 0); }
        }

[3]optimizerX64()関数に2行追加

        if (icq1 != 0 && memcmp(icq0, "\x48\x8b\x85", 3) == 0 && memcmp(icq1, "\x48\x89\x85", 3) == 0 && get32(icq0 + 3) == get32(icq1 + 3)) {
            icq = icq0;	// 	8b命令は削除.
            i = get32(icq1 + 3) / 8;
+           vc[i]--;
            if (TcTmp0 <= i && i <= TcTmp9) {
                icq = icq1;	// 89命令も削除.
+               vc[i]--;
            }
        }

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

            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: ;
                int rv = regVar(a[j]);
                if (k >= 8) {
                    *putIcX64_rex += 4;
                    k -= 8;
                }
                if (rv < 0) {
                    *icq = 0x85 + k * 8 + addVal;
                    put32(icq + 1, (a[j] - var) * 8);
+                   vc[a[j] - var]++;
                    icq += 5;
                } else {
                    rv = regVarNo[rv];
                    if (rv >= 8) {
                        *putIcX64_rex += 1;
                        rv -= 8;
                    }
                    *icq = 0xc0 + rv + k * 8 + addVal;
                    icq++;
                }
                addVal = 0;
                continue;
            }

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

int compile(String s)
{
    （中略）
    for (i = 0; i < 10; i++) {
        tmp_flag[i] = 0;
    }
    tmpLabelNo = 0;
+   for (i = 0; i < MAX_TC + 1; i++) {
+       vc[i] = 0;
+   }
    bd = lbd = 0;
    toExit = tmpLabelAlloc();
    for (pc = 0; pc < pc1; ) { // コンパイル開始.
    （中略）
}

[6]run()関数に5行追加

int run(String s)
{
    if (compile(s) < 0)
        return 1;
    if (codedump == 0) {
        void (*func)() = (void (*)()) ic;
        t0 = clock();
        func();
        if (win != 0) {
            aFlushAll(win);
        }
   } else {
       int i, i1 = dump1 - dump0;
       for (i = 0; i < i1; i++) {
           printf("%02x ", dump0[i]);
       }
       printf("\n(len=%d)\n", i1);
+      for (i = 0; i < MAX_TC + 1; i++) {
+          if (vc[i] != 0) {
+              printf("#%04d: %06d: %s\n", i, vc[i], ts[i])
+          }
+       }
    }
    return 0;
}

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

（以下編集中）

それでは早速動かしてみます。

>codedump 1

(len=0)

>run maze.c
b8 f0 02 00 ... 
(len=1533)
#0036(00421aa0): 000024: _t0
#0037(00421aa4): 000010: _t1
#0038(00421aa8): 000008: _t2
#0071(00421b2c): 000001: w
#0072(00421b30): 000003: i
#0073(00421b34): 000009: x
#0074(00421b38): 000009: y
#0075(00421b3c): 000014: xx
#0076(00421b40): 000014: yy
#0077(00421b44): 000004: d0
#0078(00421b48): 000004: d1
#0079(00421b4c): 000004: d2
#0080(00421b50): 000004: d3
#0081(00421b54): 000002: d
#0082(00421b58): 000013: dd
#0093(00421b84): 000001: 23
#0094(00421b88): 000001: 15

これを見ると、変数xx, yy, ddの出現頻度が高そうです。あとはxとyが同列で並んでいます。今のHL-16aはregVarに4つしか指定できないので（それ以上指定しても無視されるので）、 regVar(0, xx, yy, dd, x); としてみます。

>regVar(0 xx yy dd x)
8b 1d 3c 1b ...
(len=96)

>run maze.c
b8 f0 02 00 ...
(len=1265)
#0036(00421aa0): 000024: _t0
#0037(00421aa4): 000010: _t1
#0038(00421aa8): 000008: _t2
#0071(00421b2c): 000001: w
#0072(00421b30): 000003: i
#0074(00421b38): 000009: y
#0077(00421b44): 000004: d0
#0078(00421b48): 000004: d1
#0079(00421b4c): 000004: d2
#0080(00421b50): 000004: d3
#0081(00421b54): 000002: d
#0093(00421b84): 000001: 23
#0094(00421b88): 000001: 15

ということで、このregVarの設定ではプログラムの大きさが1533→1265バイトになったことがわかります。またregVar対象の変数は、%mでメモリアクセスにはならないので、変数アクセス回数にも表示されなくなっています（0回のものは表示しない仕様です）。

↑

(2) プログラムの説明

まず変数vc[]を追加します。
そしてputIcX86_sub()関数で、%mで参照されるたびにvc[]を加算していきます。
あとはoptimizerX86()関数で最適化の結果、メモリ変数へのアクセスがなくなったら、vc[]を減じます。
最後にcodedumpで機械語を出力するついでにvc[]の値を表示します。

↑

(3) 成果の比較

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

	HL-19a	HL-20	HL-20a	HL-20b	HL-21	HL-21a	HL-22	HL-22a	備考
mandel.c	1200	1088	989	989	814	719	670	670	regVar(0,zx,zy,xx,yy,t,cx,cy)[HL-14以降]
maze.c	2331	2331	2331	2331	1909	1654	1638	1289	regVar(0,xx,yy,x,y,dd,d0,d1)[HL-16a以降]
kcube.c	5207	5207	5207	5207	4188	3949	3948	3401	regVar(0,i,l,squar,x,y,p1x,p1y)[HL-16a以降]
invader.c	3567	3567	3567	3567	3001	2593	2532	1977	regVar(0,i,j,ly,ix,pnt,iy,score)[HL-16a以降]

↑

次回に続く

次回: a21_txt02_13

↑

こめんと欄

コメント	お名前	NameLink