「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-19aHL-20HL-20aHL-20bHL-21HL-21a
mandel.c12001088989989814719
maze.c233123312331233119091654
kcube.c520752075207520741883949
invader.c356735673567356730012593

次回に続く

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-05-17 (月) 22:23:40 (132d)