「10日くらいでできる！プログラミング言語自作入門」の続編#1-5a

  • (by K, 2021.04.27)
↑

(1) HL-15a

  • HL-15まででは、整数の定数があってもそれはすべて変数扱いになっていました。しかしx86は整数の定数を高速かつコンパクトに扱う命令をたくさん持っています。HL-15aではそれに対応させたいと思います。
  • [1]optimizerX86()関数を以下のものと差し替え 
    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) != 0x05) return 0;
    return isConst(((AInt *) get32(p + 1)) - var);
}

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

void putIcX86(String s, IntP p0, IntP p1, IntP p2, IntP p3); // プロトタイプ宣言.

void optimizerX86()
{
    int i;
    if (icq0 != icq) {
        if (icq0[0] == 0x0f && 0x90 <= icq0[1] && icq0[1] <= 0x9f) {	// SETcc
            icqSet = icq0;
        }
+       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); }
+       }
+       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); }
+       }
+       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); }
+       }
+       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);
+       }
        if (icq0[0] == 0x8b && icq1 != 0 && icq1[0] == 0x89 && icq0[1] == 0x05 && icq1[1] == 0x05 && get32(icq0 + 2) == get32(icq1 + 2)) {
            icq = icq0;	// 	8b命令は削除.
            i = (IntP) get32(icq1 + 2) - var;
            if (TcTmp0 <= i && i <= TcTmp9) {
                icq = icq1;	// 89命令も削除.
            }
        }
        icq1 = icq0;
        icq0 = icq;
    }
    if (icqSet + 14 == icq && memcmp(&icqSet[2], "\xc0\x0f\xb6\xc0\x85\xc0\x0f", 7) == 0 && 0x84 <= icqSet[9] && icqSet[9] <= 0x85) {
        memcpy(&icqSet[2], &icqSet[10], 4);
        icqSet[1] -= 0x10;	// SETcc → Jcc.
        if (icqSet[9] == 0x84) {
            icqSet[1] ^= 1; // 条件反転.
        }
        icq0 = icq = icqSet + 6;
        icq1 = icqSet = 0;
        jmps[jp - 1] = icq - 4 - ic;
    }
}
  • [2]defLabel()関数を以下のものと差し替え 
    int align;

void defLabel(int i)
{
+   if (align > 0) {
+       int j = (icq - ic) & 15;	// 0-15.
+       if (j > 0 && j <= 7) {
+           putIcX86("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"
+           };
+           putIcX86(table[j - 8], 0, 0, 0, 0);
+       }
+       align--;
+   }
    var[i] = icq - ic;
    icq1 = icqSet = 0;
}
  • [3]compile()関数に以下を追加 
    +       } else if (phrCmp(39, "align();", pc)) {
+           align = 1;
+       } else if (phrCmp(40, "align(!!*0);", pc)) {
+           align = var[tc[wpc[0]]];
  • 以上すべての改造を終えると、プログラムは1012行になります。
↑

(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命令
1バイトのNOP90;
2バイトのNOP66_90;
3バイトのNOP0f_1f_00;
4バイトのNOP0f_1f_40_00;
5バイトのNOP0f_1f_44_00_00;
6バイトのNOP66_0f_1f_44_00_00;
7バイトのNOP0f_1f_80_00_00_00_00;
8バイトのNOP0f_1f_84_00_00_00_00_00;
9バイトのNOP66_0f_1f_84_00_00_00_00_00;
  • align()命令では、カッコ内に数値を書かなければ、次の1つのラベルだけがアライン有効になります。数値を書いた場合は、数値の回数だけアラインが有効になります。
  • 10億回ループのプログラムをrunする前に、align(100);とかを実行しておけば、HL-15aでも十分な速度で実行できるようになります。そしてそのあと、いつでもalign(0);などとすれば、多すぎたalign設定値をクリアすることができます。
↑

(4) 成果の比較

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

次回に続く

↑

こめんと欄


コメントお名前NameLink
トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-04-27 (火) 19:50:30 (1088d)