a21_txt02_11a のバックアップソース(No.5)

[ トップ ]   [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• バックアップ を表示
• a21_txt02_11a へ行く。
  • 1 (2021-05-13 (木) 23:07:08)
  • 2 (2021-05-14 (金) 00:57:17)
  • 3 (2021-05-16 (日) 23:21:26)
  • 4 (2021-05-17 (月) 20:07:06)
  • 5 (2021-05-17 (月) 22:23:40)

* 「10日くらいでできる！プログラミング言語自作入門」の続編#1-11a
-(by [[K]], 2021.05.13)

** (1) HL-21a
-HL-21まででは、整数の定数があってもそれはすべて変数扱いになっていました。しかしx64は整数の定数を高速かつコンパクトに扱う命令をたくさん持っています。HL-21aではそれに対応させたいと思います。

-[1]optimizerX64()関数を以下のものと差し替え
 unsigned char *icq0, *icq1, *icqSet;
 
 int isConst(int i)
 {
     if ('0' <= ts[i][0] && ts[i][0] <= '9') return 1;
     return 0;
 }
 
 int isConstM(unsigned char *p)
 {
     if ((*p & 0xc7) != 0x85) return 0;
     return isConst(get32(p + 1) / 8);
 }
 
 AInt getConstM(unsigned char *p)
 {
     return var[get32(p + 1) / 8];
 }
 
 int is32bit(AInt i)
 {
     if (-0x80000000LL <= i && i <= 0x7fffffffLL) return 1;
     return 0;
 }
 
 void putIcX64(String s, IntP p0, IntP p1, IntP p2, IntP p3); // プロトタイプ宣言.
 
 void optimizerX64()
 {
     if (icq0 != icq) {
         if (icq0[0] == 0x0f && 0x90 <= icq0[1] && icq0[1] <= 0x9f) {	// SETcc
             icqSet = icq0;
         }
 +       if (icq0[0] == 0x48 && icq0[1] == 0x8b && isConstM(&icq0[2])) { // 48_8b.
 +           AInt reg = (icq0[2] >> 3) & 7, i = getConstM(&icq0[2]);
 +           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]);
 +           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]);
 +           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]);
 +           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]);
 +           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]);
 +           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); }
 +       }
 +       if ((icq0[0] == 0x48 || icq0[0] == 0x49) && icq0[1] == 0x83 && (icq0[2] & 0xf8) == 0xc0 && icq0[3] == 1) { // ADD 1 → INC.
 +           icq = icq0;
 +           putIcX64("%0c_ff_%1c", (IntP) (AInt) icq0[0], (IntP) (AInt) ((icq0[2] & 7) + 0xc0), 0, 0);
 +       }
 +       if ((icq0[0] == 0x48 || icq0[0] == 0x49) && icq0[1] == 0x83 && (icq0[2] & 0xf8) == 0xe8 && icq0[3] == 1) { // SUB 1 → DEC.
 +           icq = icq0;
 +           putIcX64("%0c_ff_%1c", (IntP) (AInt) icq0[0], (IntP) (AInt) ((icq0[2] & 7) + 0xc8), 0, 0);
 +       }
 +       if (icq0[0] == 0x48 && icq0[1] == 0x83 && (icq0[2] & 0xf8) == 0xf8 && icq0[3] == 0) { // CMP 0 → TEST.
 +           icq = icq0;
 +           putIcX64("48_85_%0c", (IntP) (AInt) ((icq0[2] & 7) * 9 + 0xc0), 0, 0, 0);
 +       }
 +       if (icq0[0] == 0x49 && icq0[1] == 0x83 && (icq0[2] & 0xf8) == 0xf8 && icq0[3] == 0) { // CMP 0 → TEST.
 +           icq = icq0;
 +           putIcX64("4d_85_%0c", (IntP) (AInt) ((icq0[2] & 7) * 9 + 0xc0), 0, 0, 0);
 +       }
         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;
     }
 }
----
-以上すべての改造を終えると、プログラムは1151行になります。


** (2) プログラムの説明#1
-isConst()関数
 int isConst(int i)
 {
     if ('0' <= ts[i][0] && ts[i][0] <= '9') return 1;
     return 0;
 }
--これは、トークンコード（トークン番号）を渡すと、それが定数か変数なのか判別します。 文字列リテラルの場合も定数なので、そこも判定すればもっといいのですが、今は手抜きでそこまではやっていません。
-isConstM()関数
 int isConstM(unsigned char *p)
 {
     if ((*p & 0xc7) != 0x85) return 0;
     return isConst(get32(p + 1) / 8);
 }
--これは%mの部分のポインタを渡すと、その引数が定数を指しているのか、それ以外なのかをチェックします。
-getConstM()関数
 int getConstM(unsigned char *p)
 {
     return var[get32(p + 1) / 8];
 }
--定数だった場合に、その定数値を受け取ります。
-is32bit()関数
 int is32bit(AInt i)
 {
     if (-0x80000000LL <= i && i <= 0x7fffffffLL) return 1;
     return 0;
 }
--与えられた値が、32bitで表現可能な場合に1を返します。
----
-optimizerX64()関数の中（8b用）
 +       if (icq0[0] == 0x48 && icq0[1] == 0x8b && isConstM(&icq0[2])) { // 48_8b.
 +           AInt reg = (icq0[2] >> 3) & 7, i = getConstM(&icq0[2]);
 +           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]);
 +           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); }
 +       }
--これは例えば「a = 0;」をHL-21でコンパイルすると「48_8b_85_18_00_00_00; 48_89_85_18_03_00_00;」になるのですが、このうちの最初の8b命令に関する最適化です。
--[最適化対象例] 48_8b_85_18_00_00_00
--[最適化結果例#1] 31_c0 （定数=0の場合）
--[最適化結果例#2] b8_??_??_??_?? （それ以外の場合）

-optimizerX86()関数の中（03～3b用）
 +       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]);
 +           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]);
 +           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); }
 +       }
--これは例えば「a = b + 2;」をHL-21でコンパイルすると「48_8b_85_20_03_00_00; 48_03_85_28_00_00_00; 48_89_85_18_03_00_00;」になるのですが、このうちの真ん中の03命令に関する最適化です。
--[最適化対象例] 48_03_85_28_00_00_00
--[最適化結果例#1] 48_83_c0_?? （定数=-128～+127の場合）
--[最適化結果例#2] 48_81_c0_??_??_??_?? （それ以外の場合）

-optimizerX86()関数の中（0f_af用）
 +       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]);
 +           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]);
 +           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); }
 +       }
--これは例えば「a = b * 12;」をHL-21でコンパイルすると「48_8b_85_20_03_00_00; 48_0f_af_85_28_03_00_00; 48_89_85_18_03_00_00;」になるのですが、このうちの真ん中の0f_af命令に関する最適化です。
--[最適化対象例] 48_0f_af_85_28_03_00_00
--[最適化結果例#1] 48_6b_c0_?? （定数=-128～+127の場合）
--[最適化結果例#2] 48_69_c0_??_??_??_?? （それ以外の場合）

-optimizerX86()関数の中（さらに最適化）
 +       if ((icq0[0] == 0x48 || icq0[0] == 0x49) && icq0[1] == 0x83 && (icq0[2] & 0xf8) == 0xc0 && icq0[3] == 1) { // ADD 1 → INC.
 +           icq = icq0;
 +           putIcX64("%0c_ff_%1c", (IntP) (AInt) icq0[0], (IntP) (AInt) ((icq0[2] & 7) + 0xc0), 0, 0);
 +       }
 +       if ((icq0[0] == 0x48 || icq0[0] == 0x49) && icq0[1] == 0x83 && (icq0[2] & 0xf8) == 0xe8 && icq0[3] == 1) { // SUB 1 → DEC.
 +           icq = icq0;
 +           putIcX64("%0c_ff_%1c", (IntP) (AInt) icq0[0], (IntP) (AInt) ((icq0[2] & 7) + 0xc8), 0, 0);
 +       }
 +       if (icq0[0] == 0x48 && icq0[1] == 0x83 && (icq0[2] & 0xf8) == 0xf8 && icq0[3] == 0) { // CMP 0 → TEST.
 +           icq = icq0;
 +           putIcX64("48_85_%0c", (IntP) (AInt) ((icq0[2] & 7) * 9 + 0xc0), 0, 0, 0);
 +       }
 +       if (icq0[0] == 0x49 && icq0[1] == 0x83 && (icq0[2] & 0xf8) == 0xf8 && icq0[3] == 0) { // CMP 0 → TEST.
 +           icq = icq0;
 +           putIcX64("4d_85_%0c", (IntP) (AInt) ((icq0[2] & 7) * 9 + 0xc0), 0, 0, 0);
 +       }
--これらは、以下のような最適化をします。
--「48_83_c0_01;」→「48_ff_c0;」（ADD 1 → INC）
--「48_83_e8_01;」→「48_ff_c8;」（SUB 1 → DEC）
--「48_83_f8_00;」→「48_85_c0;」（CMP 0 → TEST）

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


||HL-19a|HL-20|HL-20a|HL-20b|HL-21|HL-21a|
|mandel.c|RIGHT:1200|RIGHT:1088|RIGHT:989|RIGHT:989|RIGHT:856|RIGHT:763|
|maze.c|RIGHT:2331|RIGHT:2331|RIGHT:2331|RIGHT:2331|RIGHT:2077|RIGHT:1829|
|kcube.c|RIGHT:5207|RIGHT:5207|RIGHT:5207|RIGHT:5207|RIGHT:4286|RIGHT:4052|
|invader.c|RIGHT:3567|RIGHT:3567|RIGHT:3567|RIGHT:3567|RIGHT:3029|RIGHT:2639|


** 次回に続く
-次回: [[a21_txt02_12]]

*こめんと欄
#comment

     

Site admin: K

PukiWiki 1.4.7 Copyright © 2001-2006 PukiWiki Developers Team. License is GPL.
Based on "PukiWiki" 1.3 by yu-ji. Powered by PHP 5.6.40. HTML convert time: 0.021 sec.