「10日くらいでできる！プログラミング言語自作入門」の続編#1-6a
(1) HL-16a
- HL-16までで、「簡単にできる」かつ「そこそこ効果がある」なことは全部やってしまったと思っていたのですが、急に一つ思いつきました。
- 機械語の中で%mを使ってメモリアクセスしている回数を変数別に集計したら面白いのではないか、と。・・・さっそくやってみます。
- これがわかれば、出現頻度が高いものからregVarに指定すれば、コードは最も小さくできるはずです（ただ、それはサイズ優先であって、使用頻度を優先したものではないので、性能が高いかどうかは不確かです。使用頻度を重視するならやはりコードを読んで重そうなところを探す必要があります）。
- [1]optimizerX86()関数の宣言の直前に、以下の一行を追加
int vc[MAX_TC + 1];
- [2]optimizerX86()関数に3行追加
if (icq0[0] == 0x8b && isConstM(&icq0[1])) {
int reg = (icq0[1] >> 3) & 7, i = getConstM(&icq0[1]);
+ vc[((AInt *) get32(&icq0[2])) - var]--;
icq = icq0;
if (i == 0) { putIcX86("31_%0c", (IntP) (reg * 9 + 0xc0), 0, 0, 0); }
else { putIcX86("%0c_%1i", (IntP) (reg + 0xb8), (IntP) i, 0, 0); }
}
if (icq0[0] <= 0x3f && (icq0[0] & 7) == 3 && isConstM(&icq0[1])) {
int reg = (icq0[1] >> 3) & 7, i = getConstM(&icq0[1]);
+ vc[((AInt *) get32(&icq0[2])) - var]--;
icq = icq0;
if (-0x80 <= i && i <= 0x7f) { putIcX86("83_%0c_%1c", (IntP) ((icq0[0] & 0x38) + reg + 0xc0), (IntP) i, 0, 0); }
else { putIcX86("81_%0c_%1i", (IntP) ((icq0[0] & 0x38) + reg + 0xc0), (IntP) i, 0, 0); }
}
if (icq0[0] == 0x0f && icq0[1] == 0xaf && isConstM(&icq0[2])) {
int reg = (icq0[2] >> 3) & 7, i = getConstM(&icq0[2]);
+ vc[((AInt *) get32(&icq0[3])) - var]--;
icq = icq0;
if (-0x80 <= i && i <= 0x7f) { putIcX86("6b_%0c_%1c", (IntP) (reg * 9 + 0xc0), (IntP) i, 0, 0); }
else { putIcX86("69_%0c_%1i", (IntP) (reg * 9 + 0xc0), (IntP) i, 0, 0); }
}
- [3]optimizerX86()関数に2行追加
if (icq0[0] == 0x8b && icq1 != 0 && icq1[0] == 0x89 && icq0[1] == 0x05 && icq1[1] == 0x05 && get32(icq0 + 2) == get32(icq1 + 2)) {
icq = icq0; // 8b命令は削除.
i = (IntP) get32(icq1 + 2) - var;
+ vc[i]--;
if (TcTmp0 <= i && i <= TcTmp9) {
+ vc[i]--;
icq = icq1; // 89命令も削除.
}
}
- [4]putIcX86_sub()関数に1行追加
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]);
+ vc[a[j] - var]++;
icq += 5;
} else {
*icq = 0xc0 + regVarNo[regVar(a[j])] + 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(%08x): %06d: %s\n", i, (int) &var[i], vc[i], ts[i]);
+ }
+ }
}
return 0;
}
- 以上すべての改造を終えると、プログラムは1081行になります。
- それでは早速動かしてみます。
>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-13a | HL-14 | HL-14a | HL-15 | HL-15a | HL-16 | HL-16a | 備考 | | mandel.c | 1087 | 1007 | 942 | 768 | 726 | 657 | 657 | regVar(0,zx,zy,xx,yy)[HL-14以降] | | maze.c | 2192 | 2192 | 2192 | 1770 | 1536 | 1533 | 1265 | regVar(0,xx,yy,dd,x)[HL-16a以降] | | kcube.c | 4623 | 4623 | 4623 | 3695 | 3495 | 3494 | 3116 | regVar(0,i,l,x,y)[HL-16a以降] | | invader.c | 3260 | 3260 | 3260 | 2750 | 2399 | 2357 | 1949 | regVar(0,i,j,ly,ix)[HL-16a以降] |
- x86(32bit)のJITコンパイラの話はこれでいったんおしまいです。
- 次からはx64(64bit)のJITコンパイラの話を書きます。
次回に続く
こめんと欄
|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
