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

  • (by K, 2021.05.18)

(1) HL-22a

  • HL-22までで、「簡単にできる」かつ「そこそこ効果がある」なことは全部やってしまったと思っていたのですが、急に一つ思いつきました。
  • 機械語の中で%mを使ってメモリアクセスしている回数を変数別に集計したら面白いのではないか、と。・・・さっそくやってみます。
  • これがわかれば、出現頻度が高いものからregVarに指定すれば、コードは最も小さくできるはずです(ただ、それはサイズ優先であって、使用頻度を優先したものではないので、性能が高いかどうかは不確かです。使用頻度を重視するならやはりコードを読んで重そうなところを探す必要があります)。

  • [1]optimizerX64()関数の宣言の直前に、以下の一行を追加
    int vc[MAX_TC + 1];
  • [2]optimizerX64()関数に6行追加
            if (icq0[0] == 0x48 && icq0[1] == 0x8b && isConstM(&icq0[2])) { // 48_8b.
                AInt reg = (icq0[2] >> 3) & 7, i = getConstM(&icq0[2]);
    +           vc[get32(&icq0[3]) / 8]--;
                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]);
    +           vc[get32(&icq0[3]) / 8]--;
                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]);
    +           vc[get32(&icq0[3]) / 8]--;
                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]);
    +           vc[get32(&icq0[3]) / 8]--;
                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]);
    +           vc[get32(&icq0[4]) / 8]--;
                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]);
    +           vc[get32(&icq0[4]) / 8]--;
                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); }
            }
  • [3]optimizerX64()関数に2行追加
            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;
    +           vc[i]--;
                if (TcTmp0 <= i && i <= TcTmp9) {
                    icq = icq1;	// 89命令も削除.
    +               vc[i]--;
                }
            }
  • [4]putIcX64_sub()関数に1行追加
                if (s[i + 2] == 'm') {	// mod r/m.
                    k = s[i + 3] - '0';
                    if (s[i + 3] >= 'a') { // もしかしたらこの記述は最後まで出番がないかも.
                        k = s[i + 3] - 'a' + 10;
                    }
                    i += 4;
    subcmd_m: ;
                    int rv = regVar(a[j]);
                    if (k >= 8) {
                        *putIcX64_rex += 4;
                        k -= 8;
                    }
                    if (rv < 0) {
                        *icq = 0x85 + k * 8 + addVal;
                        put32(icq + 1, (a[j] - var) * 8);
    +                   vc[a[j] - var]++;
                        icq += 5;
                    } else {
                        rv = regVarNo[rv];
                        if (rv >= 8) {
                            *putIcX64_rex += 1;
                            rv -= 8;
                        }
                        *icq = 0xc0 + rv + k * 8 + addVal;
                        icq++;
                    }
                    addVal = 0;
                    continue;
                }
  • [5]compile()関数に3行追加
    int compile(String s)
    {
        (中略)
        for (i = 0; i < 10; i++) {
            tmp_flag[i] = 0;
        }
        tmpLabelNo = 0;
    +   for (i = 0; i < MAX_TC + 1; i++) {
    +       vc[i] = 0;
    +   }
        bd = lbd = 0;
        toExit = tmpLabelAlloc();
        for (pc = 0; pc < pc1; ) { // コンパイル開始.
        (中略)
    }
  • [6]run()関数に5行追加
    int run(String s)
    {
        if (compile(s) < 0)
            return 1;
        if (codedump == 0) {
            void (*func)() = (void (*)()) ic;
            t0 = clock();
            func();
            if (win != 0) {
                aFlushAll(win);
            }
       } else {
           int i, i1 = dump1 - dump0;
           for (i = 0; i < i1; i++) {
               printf("%02x ", dump0[i]);
           }
           printf("\n(len=%d)\n", i1);
    +      for (i = 0; i < MAX_TC + 1; i++) {
    +          if (vc[i] != 0) {
    +              printf("#%04d: %06d: %s\n", i, vc[i], ts[i])
    +          }
    +       }
        }
        return 0;
    }

  • 以上すべての改造を終えると、プログラムは1223行になります。
  • それでは早速動かしてみます。
    >codedump 1
    
    (len=0)
    
    >run maze.c
    b9 f0 02 00 ... 
    (len=1638)
    #0036: 000032: _t0
    #0037: 000010: _t1
    #0038: 000008: _t2
    #0049: 000003: sub_xorShift
    #0050: 000009: sub_aGetPix
    #0056: 000007: sub_aFilRct0
    #0059: 000001: sub_opnWin
    #0060: 000001: sub_aWait
    #0089: 000001: w
    #0090: 000003: i
    #0091: 000009: x
    #0092: 000009: y
    #0093: 000014: xx
    #0094: 000014: yy
    #0095: 000004: d0
    #0096: 000004: d1
    #0097: 000004: d2
    #0098: 000004: d3
    #0099: 000002: d
    #0100: 000013: dd
    #0111: 000001: 23
    #0112: 000001: 15
  • これを見ると、変数xx, yy, ddの出現頻度が高そうです。あとはxとyが同列で並んでいます。さらに指定するとするとd0~d3でしょうか。今のHL-22aはregVarに7つしか指定できないので(それ以上指定しても無視されるので)、 regVar(0, xx, yy, dd, x, y, d0, d1); としてみます。
    >regVar(0, xx, yy, dd, x, y, d0, d1)
    48 8b 9d e8 ...
    (len=49)
    
    >run maze.c
    b8 f0 02 00 ...
    (len=1289)
    #0036: 000032: _t0
    #0037: 000010: _t1
    #0038: 000008: _t2
    #0049: 000003: sub_xorShift
    #0050: 000009: sub_aGetPix
    #0056: 000007: sub_aFilRct0
    #0059: 000001: sub_opnWin
    #0060: 000001: sub_aWait
    #0089: 000001: w
    #0090: 000003: i
    #0097: 000004: d2
    #0098: 000004: d3
    #0099: 000002: d
    #0111: 000001: 23
    #0112: 000001: 15
  • ということで、このregVarの設定ではプログラムの大きさが1638→1289バイトになったことがわかります。またregVar対象の変数は、%mでメモリアクセスにはならないので、変数アクセス回数にも表示されなくなっています(0回のものは表示しない仕様です)。

(2) プログラムの説明

  • まず変数vc[]を追加します。
  • そしてputIcX64_sub()関数で、%mで参照されるたびにvc[]を加算していきます。
  • あとはoptimizerX64()関数で最適化の結果、メモリ変数へのアクセスがなくなったら、vc[]を減じます。
  • 最後にcodedumpで機械語を出力するついでにvc[]の値を表示します。

(3) 成果の比較

  • 上記みたいなのはすごく特別でレアケースなのか、それともよくあるメジャーケースなのか、たぶん簡単には判断できないと思うので、いくつかのプログラムでcodedumpしてバイト数を比較してみました。
  • サイズが小さくなったからいいとか悪いとかではなく、「サイズが小さくなった=それだけ適用された」ということだと考えてください。
HL-19aHL-20HL-20aHL-20bHL-21HL-21aHL-22HL-22a備考
mandel.c12001088989989814719670670regVar(0,zx,zy,xx,yy,t,cx,cy)[HL-20以降]
maze.c23312331233123311909165416381289regVar(0,xx,yy,dd,x,y,d0,d1)[HL-22a以降]
kcube.c52075207520752074188394939483401regVar(0,i,l,squar,x,y,p1x,p1y)[HL-22a以降]
invader.c35673567356735673001259325321977regVar(0,i,j,ly,ix,pnt,iy,score)[HL-22a以降]

次回に続く

  • 次回: a21_txt02_13

こめんと欄


コメントお名前NameLink

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