「10日くらいでできる!プログラミング言語自作入門」の続編#1-10a
(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となるので、高速化が期待できます。
- ここまでは、私もわかっていました。それこそ何年も前から分かっていました。しかしレジスタ変数の場合と、メモリ変数の場合で場合分けして処理を書き始めると、あっという間に言語処理系は大きくなってしまいます。それはちっとも「自作入門」ではありません。だからもともとはこの最適化の話はしない予定でした。
- でもようやく、これを簡単に書く方法を思いつきました。だから紹介してみます。いやもっといい方法があるかもしれないですが、とりあえず現時点で私が知る中では一番シンプルなやり方です。
- では、%0と%1が同じ変数を指していて、しかもレジスタ変数だったら最終的にどんな出力になるでしょうか。ここではRBXレジスタのレジスタ変数だった場合を考えてみます。
- RBXなので、r=3になります。%1L0と%0Sは何も出力しません。すると、結局1命令だけになり、
%R_03_%2m3;
- に相当する機械語だけが出てくることになるのです。おお、これこそまさにRAXを経由せずに、RBXだけで演算が完結しているのです。
- これはまだだめじゃないかと思うかもしれません。まあその通りです。せめて「RBX = RSI; RBX += %2;」くらいにできたらいいですよね。そうなんです。しかし、もし%2がRBXだったらどうしましょう。最初の「RBX = RSI;」のせいでRBXの値が上書きされて値が変わってしまうので、うまく計算できなくなります。そういうことを考えるといろいろめんどくさくなってきたので、ひとまずこの件は保留にして、以前通りのRAX経由にしているというわけです。
- [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;
- おお、これはまさに上記の「理想形」です。とてもうまくいっているようです。
ページ名 | 名前 | 行数 | .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 | HL-20a | 1014行 | 37.0KB | レジスタ変数のための最適化(さらに50行を追加してすごい速さに!・・・なってない) | 2.1倍 | 0.7倍 |
- あれ?10億回ループは速くなっていませんね・・・。
- ということでHL-20bでそれを解決します。
次回に続く
こめんと欄
|