a21_txt02_11a のバックアップ(No.2)

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

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 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) != 0x05) return 0;
      return isConst(((AInt *) get32(p + 1)) - var);
  }

  • これは%mの部分のポインタを渡すと、その引数が定数を指しているのか、それ以外なのかをチェックします。
• getConstM()関数

  int getConstM(unsigned char *p)
  {
      return *((AInt *) get32(p + 1));
  }

  • 定数だった場合に、その定数値を受け取ります。

---

• optimizerX86()関数の中（8b用）

  +       if (icq0[0] == 0x8b && isConstM(&icq0[1])) { // 8b.
  +           int reg = (icq0[1] >> 3) & 7, i = getConstM(&icq0[1]);
  +           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); }
  +       }

  • これは例えば「a = 0;」をHL-15でコンパイルすると「8b_05_1c_0a_42_00; 89_05_2c_0b_42_00;」になるのですが、このうちの最初の8b命令に関する最適化です。
  • [最適化対象例] 8b_05_1c_0a_42_00
  • [最適化結果例#1] 31_c0 （定数=0の場合）
  • [最適化結果例#2] b8_??_??_??_?? （それ以外の場合）

• optimizerX86()関数の中（03～3b用）

  +       if (icq0[0] <= 0x3f && (icq0[0] & 7) == 3 && isConstM(&icq0[1])) { // 03, 0b, 13, 1b, 23, 2b, 33, 3b.
  +           int reg = (icq0[1] >> 3) & 7, i = getConstM(&icq0[1]);
  +           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); }
  +       }

  • これは例えば「a = b + 2;」をHL-15でコンパイルすると「8b_05_30_0b_42_00; 03_05_24_0a_42_00; 89_05_2c_0b_42_00;」になるのですが、このうちの真ん中の03命令に関する最適化です。
  • [最適化対象例] 03_05_24_0a_42_00
  • [最適化結果例#1] 83_c0_?? （定数=-128～+127の場合）
  • [最適化結果例#2] 81_c0_??_??_??_?? （それ以外の場合）

• optimizerX86()関数の中（0f_af用）

  +       if (icq0[0] == 0x0f && icq0[1] == 0xaf && isConstM(&icq0[2])) { // 0f_af.
  +           int reg = (icq0[2] >> 3) & 7, i = getConstM(&icq0[2]);
  +           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); }
  +       }

  • これは例えば「a = b * 12;」をHL-15でコンパイルすると「8b_05_30_0b_42_00; 0f_af_05_34_0b_42_00; 89_05_2c_0b_42_00;」になるのですが、このうちの真ん中の0f_af命令に関する最適化です。
  • [最適化対象例] 0f_af_05_34_0b_42_00
  • [最適化結果例#1] 6b_c0_?? （定数=-128～+127の場合）
  • [最適化結果例#2] 69_c0_??_??_??_?? （それ以外の場合）

• optimizerX86()関数の中（さらに最適化）

  +       if (icq0[0] == 0x83 && (icq0[1] & 0xf8) == 0xc0 && icq0[2] == 1) { // ADD 1 → INC.
  +           icq = icq0;
  +           putIcX86("%0c", (IntP) ((icq0[1] & 7) + 0x40), 0, 0, 0);
  +       }
  +       if (icq0[0] == 0x83 && (icq0[1] & 0xf8) == 0xe8 && icq0[2] == 1) { // SUB 1 →DEC.
  +           icq = icq0;
  +           putIcX86("%0c", (IntP) ((icq0[1] & 7) + 0x48), 0, 0, 0);
  +       }
  +       if (icq0[0] == 0x83 && (icq0[1] & 0xf8) == 0xf8 && icq0[2] == 0) { // CMP 0 → TEST.
  +           icq = icq0;
  +           putIcX86("85_%0c", (IntP) ((icq0[1] & 7) * 9 + 0xc0), 0, 0, 0);
  +       }

  • これらは、以下のような最適化をします。
  • 「83_c0_01;」→「40;」（ADD 1 → INC）
  • 「83_e8_01;」→「48;」（SUB 1 → DEC）
  • 「83_f8_00;」→「85_c0;」（CMP 0 → TEST）

(3) プログラムの説明#2

• 基本的にはこれだけで十分に良いのですが、なんとそれだけだと10億回ループが20%くらい遅くなってしまいました。・・・コードは良くなっているはずなのに、なぜだー！
• これは実は命令長が短くなってしまったせいで、分岐先のアドレス（番地）が変わってしまって、速度が出なくなってしまったのです。
• それはあまりにも悲しいので、命令が短くなりすぎて速度が出せないアドレスになってしまいそうな時だけに、余計なNOP命令を入れて、速度低下しないようにalign命令を追加しました。
• align命令でアライン機能が有効な時は、defLabel()するときに、もし速度が出ないアドレスになっているときは（＝16で割った時にあまりが出るアドレスになっているときは）、適当にNOP命令を入れて、「よいアドレス」まで進めてから、defLabel()するようにしています。
• x86のアライン用のNOP命令

• align()命令では、カッコ内に数値を書かなければ、次の1つのラベルだけがアライン有効になります。数値を書いた場合は、数値の回数だけアラインが有効になります。
• 10億回ループのプログラムをrunする前に、align(100);とかを実行しておけば、HL-15aでも十分な速度で実行できるようになります。そしてそのあと、いつでもalign(0);などとすれば、多すぎたalign設定値をクリアすることができます。

(4) 成果の比較

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

次回に続く

• 次回: a21_txt02_6

こめんと欄

コメント	お名前	NameLink

     

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.012 sec.