* 「10日くらいでできる！プログラミング言語自作入門」の続編#1-11
-(by [[K]], 2021.05.13)
** (1) HL-21
-今回の最適化は、a = b + c - d; みたいな式に関するものです。HL-20bでは、こうなります。
>codedump 1
(len=0)
>a=b+c-d
48 8b 85 d0 02 00 00 48 03 85 d8 02 00 00 48 89 85 20 01 00 00 48 8b 85 20 01 00 00 48 2b 85 e0 02 00 00 48 89 85 28 01 00 00 48 8b 85 28 01 00 00 48 89 85 c8 02 00 00
(len=56)
-これを見やすくするとこうなっています。
48 8b 85 d0 02 00 00; // RAX = b;
48 03 85 d8 02 00 00; // RAX += c;
48 89 85 20 01 00 00; // _t0 = RAX;
48 8b 85 20 01 00 00; // RAX = _t0;
48 2b 85 e0 02 00 00; // RAX -= d;
48 89 85 28 01 00 00; // _t1 = RAX;
48 8b 85 28 01 00 00; // RAX = _t1;
48 89 85 c8 02 00 00; // a = RAX;
-はい、これはひどいです。_t0や_t1に書いたり読み込んだり、そんなの全然必要ないことです。掛け算や割り算など、異なる優先順位の演算がまざってもいいように問答無用で一時変数に代入するようにしていることが、この無駄の原因になっています。
-これに対して、理想形はこうなります。
48 8b 85 d0 02 00 00; // RAX = b;
48 03 85 d8 02 00 00; // RAX += c;
48 2b 85 e0 02 00 00; // RAX -= d;
48 89 85 c8 02 00 00; // a = RAX;
-っていうか、普通こうなるべきですよね。
----
-もう一つ気になっているのは、このコンパイル結果です。
>if (a+b<c-d) { x=0; }
48 8b 85 c8 02 00 00; // RAX = a;
48 03 85 d0 02 00 00; // RAX += b;
48 89 85 20 01 00 00; // _t0 = RAX;
48 8b 85 d8 02 00 00; // RAX = c;
48 2b 85 e0 02 00 00; // RAX -= d;
48 89 85 28 01 00 00; // _t1 = RAX;
48 8b 85 20 01 00 00; // RAX = _t0;
48 3b 85 28 01 00 00; // if (RAX < _t1) { RAX = 1: } else { RAX = 0; } (SETL)
0f 9c c0;
0f b6 c0;
48 89 85 30 01 00 00; // _t2 = RAX;
48 8b 85 30 01 00 00; // RAX = _t2;
48 85 c0; // if (RAX == 0) goto skip;
0f 84 0e 00 00 00;
48 8b 85 18 00 00 00; // RAX = 0;
48 89 85 e8 02 00 00; // x = RAX;
skip:
-これがだめだなあと思うのは、_t2への無駄な読み書きと、0f_9c_c0;命令で比較結果を計算した後で、またその結果に対して48_85_c0;で比較していることです。理想はこうです。
48 8b 85 c8 02 00 00; // RAX = a;
48 03 85 d0 02 00 00; // RAX += b;
48 89 85 20 01 00 00; // _t0 = RAX;
48 8b 85 d8 02 00 00; // RAX = c;
48 2b 85 e0 02 00 00; // RAX -= d;
48 89 85 28 01 00 00; // _t1 = RAX;
48 8b 85 20 01 00 00; // RAX = _t0;
48 3b 85 28 01 00 00; // if (EAX >= _t1) goto skip;
0f 8d 0e 00 00 00;
48 8b 85 18 00 00 00; // RAX = 0;
48 89 85 e8 02 00 00; // x = RAX;
skip:
----
-ということで、HL-21はこの2つの問題を解決しようと思います。
-[1]regVar()関数の後、putIcX86_sub()関数の前に以下を追加
unsigned char *icq0, *icq1, *icqSet;
void optimizerX64()
{
int i;
if (icq0 != icq) {
if (icq0[0] == 0x0f && 0x90 <= icq0[1] && icq0[1] <= 0x9f) { // SETcc
icqSet = icq0;
}
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;
if (TcTmp0 <= i && i <= TcTmp9) {
icq = icq1; // 89命令も削除.
}
}
icq1 = icq0;
icq0 = icq;
}
if (icqSet + 15 == icq && memcmp(&icqSet[2], "\xc0\x0f\xb6\xc0\x48\x85\xc0\x0f", 8) == 0 && 0x84 <= icqSet[10] && icqSet[10] <= 0x85) {
memcpy(&icqSet[2], &icqSet[11], 4);
icqSet[1] -= 0x10; // SETcc → Jcc.
if (icqSet[10] == 0x84) {
icqSet[1] ^= 1; // 条件反転.
}
icq0 = icq = icqSet + 6;
icq1 = icqSet = 0;
jmps[jp - 1] = icq - 4 - ic;
}
}
-[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] == ':') {
i++;
+ } else if (s[i] == ';') {
+ i++;
+ optimizerX64();
} else if (getHex(s[i]) >= 0 && getHex(s[i + 1]) >= 0) { // 16進数2桁.
（中略）
}
-[3]defLabel()関数に1行追加
void defLabel(int i)
{
if (align > 0) {
int j = (icq - ic) & 15; // 0-15.
if (j > 0 && j <= 7) {
putIcX64("66_0f_1f_84_00_00_00_00_00", 0, 0, 0, 0);
j = (j + 9) & 15;
}
if (j > 0) { // 8-15.
static char *table[8] = {
"0f_1f_84_00_00_00_00_00", "0f_1f_80_00_00_00_00",
"66_0f_1f_44_00_00", "0f_1f_44_00_00", "0f_1f_40_00", "0f_1f_00", "66_90", "90"
};
putIcX64(table[j - 8], 0, 0, 0, 0);
}
align--;
}
var[i] = icq - ic;
+ icq1 = icqSet = 0;
}
-compile()関数を少し改造
int compile(String s)
{
int pc, pc1, i, j;
unsigned char *icq1, *icp;
pc1 = lexer(s, tc);
tc[pc1++] = TcSemi; // 末尾に「;」を付け忘れることが多いので、付けてあげる.
tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = TcDot; // エラー表示用のために末尾にピリオドを登録しておく.
! icq = icq0 = ic;
jp = 0;
+ icq1 = icqSet = 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;
（中略）
}
----
-以上すべての改造を終えると、プログラムは1070行になります。
-さて、うまく動くでしょうか。
>a=b+c-d
48 8b 85 d0 02 00 00 48 03 85 d8 02 00 00 48 2b 85 e0 02 00 00 48 89 85 c8 02 00 00
(len=28)
-うまくいっています。ちゃんと上記の理想通りになっています。
-if文のほうはどうでしょうか。
>if (a+b<c-d) { x=0; }
48 8b 85 c8 02 00 00 48 03 85 d0 02 00 00 48 89
85 20 01 00 00 48 8b 85 d8 02 00 00 48 2b 85 e0
02 00 00 48 89 85 28 01 00 00 48 8b 85 20 01 00
00 48 3b 85 28 01 00 00 0f 8d 0e 00 00 00 48 8b
85 18 00 00 00 48 89 85 e8 02 00 00
(len=76)
-これもうまくいっています！
** (2) プログラムの説明
-今回の改造の中心は、optimizerX64()関数です。
-この関数は、putIcX64()でセミコロンが来たタイミングで呼ばれます。
-まず、3つのグローバル変数があります。
--icq0 : 直前のセミコロンの位置（＝今の命令の開始位置）
--icq1 : さらにその前のセミコロンの位置（＝1つ前の命令の開始位置）
--icqSet : SETcc命令を見つけたら、その先頭を記憶しておく
-icqとicq0とicq1を使えば、連続した2命令をチェックすることができます。これを使って、直前に書いたところをすぐに読み込む場合があったら、その読み込み命令を消します。また、書き込み対象が一時変数なら、書き込み命令も消します。
-またSETcc命令の後に最適化すべきパターンが来ていたら、前述の理想形になるように、命令列を加工しています。また条件分岐命令の位置が変わるので、 jmps[jp - 1] を上書きします。
-最適化対象の機械語フレーズの中にラベルがあると、どこからかそこに分岐して入ってくる可能性があるので、勝手な最適化はできません。ということで、defLabel()では最適化を妨げるためにicq1とicqSetを0クリアしています。
** (3) 成果の比較
-上記みたいなのはすごく特別でレアケースなのか、それともよくあるメジャーケースなのか、たぶん簡単には判断できないと思うので、いくつかのプログラムでcodedumpしてバイト数を比較してみました。
-サイズが小さくなったからいいとか悪いとかではなく、「サイズが小さくなった＝それだけ適用された」ということだと考えてください。
||HL-19a|HL-20|HL-20a|HL-20b|HL-21|
|mandel.c|RIGHT:1200|RIGHT:1088|RIGHT:989|RIGHT:989|RIGHT:856|
|maze.c|RIGHT:2331|RIGHT:2331|RIGHT:2331|RIGHT:2331|RIGHT:2077|
|kcube.c|RIGHT:5207|RIGHT:5207|RIGHT:5207|RIGHT:5207|RIGHT:4286|
|invader.c|RIGHT:3567|RIGHT:3567|RIGHT:3567|RIGHT:3567|RIGHT:3029|
|mandel.c|RIGHT:1200|RIGHT:1088|RIGHT:989|RIGHT:989|RIGHT:814|
|maze.c|RIGHT:2331|RIGHT:2331|RIGHT:2331|RIGHT:2331|RIGHT:1909|
|kcube.c|RIGHT:5207|RIGHT:5207|RIGHT:5207|RIGHT:5207|RIGHT:4188|
|invader.c|RIGHT:3567|RIGHT:3567|RIGHT:3567|RIGHT:3567|RIGHT:3001|
** 次回に続く
-次回: [[a21_txt02_11a]]
*こめんと欄
#comment
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
