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

  • (by K, 2021.05.08)

(1) HL-18

  • JITコンパイラ化は高速化のためにやっているのですから、やはりどのくらい速くなったのかを早く確認したいです。ということで、ループ処理くらいはできるところまで、JITコンパイラ対応を進めたいと思います。
(前略)

unsigned char *ic, *icq; // ic[]:内部コード、icq:ic[]への書き込み用ポインタ. [この行は前からある]
unsigned char *dump0, *dump1; // codedumpのための変数(HL-18aから使います). [この行追加]
int jmps[10000], jp; // ジャンプ命令の場所を記憶しておくためのもの. [この行追加]

void putIc(int op, IntP p0, IntP p1, IntP p2, IntP p3) → HL-17と同じなので省略

int getHex(int c) → HL-17と同じなので省略

int get32(unsigned char *p) → HL-17と同じなので省略

void put32(unsigned char *p, int i) → HL-17と同じなので省略

void putIcX64_sub(String s, IntP a[])
{
    int i, j, k;
    for (i = 0; s[i] != 0; ) {
        if (s[i] == ' ' || s[i] == '\t' || s[i] == '_' || s[i] == ':' || s[i] == ';') {
            i++;
        } else if (getHex(s[i]) >= 0 && getHex(s[i + 1]) >= 0) { // 16進数2桁.
            (中略)
        } else if (s[i] == '%') {
            (中略)
            if (s[i + 2] == 'q') {	// long long (qword).
                put32(icq,      (AInt) a[j]);
                put32(icq + 4, ((AInt) a[j]) >> 32);
                icq += 8;
            }
+           if (s[i + 2] == 'l') {	// label.
+               put32(icq, a[j] - var);
+               jmps[jp] = icq - ic; // ジャンプ命令のラベル番号を書いた場所を記憶.
+               jp++;
+               icq += 4;
+           }
            i += 3;
        } else {
            printf("putIcX64: error: '%s'\n", s);
            exit(1);
        }
    }
}

void putIcX64(String s, IntP p0, IntP p1, IntP p2, IntP p3) → HL-17と同じなので省略

///////////////////////////////////////////////////////////////////////////////

(中略)

///////////////////////////////////////////////////////////////////////////////

void sub_print(AInt i)
{
    printf("%d\n", (int) i);
}

clock_t t0; [この行追加]

void sub_time() [この関数追加]
{
    printf("time: %.3f[sec]\n", (clock() - t0) / (double) CLOCKS_PER_SEC);
}

void initTcSub()
{
    var[TcSubPrint] = (AInt) sub_print;
+   var[TcSubTime]  = (AInt) sub_time;
}

///////////////////////////////////////////////////////////////////////////////

(中略)

///////////////////////////////////////////////////////////////////////////////

(中略)

int tmpLabelAlloc() → HL-8と同じなので省略

void defLabel(int i) [この関数追加]
{
    var[i] = icq - ic;
}

#define BInfSiz		10

int binf[BInfSiz * 100], bd, lbd; // binf:block-info, bd:block-depth, lbd:loop-block-depth

(中略)

///////////////////////////////////////////////////////////////////////////////

int compile(String s)
{
    int pc, pc1, i, j;
    unsigned char *icq1, *icp;
    pc1 = lexer(s, tc);
    tc[pc1++] = TcSemi;	// 末尾に「;」を付け忘れることが多いので、付けてあげる.
    tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = TcDot;	// エラー表示用のために末尾にピリオドを登録しておく.
    icq = ic;
+   jp = 0;
    putIcX64("41_57; 41_56; 41_55; 41_54; 41_53; 41_52;", 0, 0, 0, 0);
    putIcX64("41_51; 41_50; 57; 56; 55; 54; 53; 52; 51; 50;", 0, 0, 0, 0);
    putIcX64("%R_81_ec_f8_01_00_00; %R_bd_%0q;", var, 0, 0, 0);
    (中略)
        } else if (phrCmp(10, "!!*0 = !!*1 + 1; if (!!*2 < !!*3) goto !!*4;", pc) && tc[wpc[0]] == tc[wpc[1]] && tc[wpc[0]] == tc[wpc[2]]) {
!           putIcX64("%R_8b_%1m0; %R_ff_c0; %R_89_%1m0; %R_3b_%2m0; 0f_8c_%0l;", &var[tc[wpc[4]]], &var[tc[wpc[0]]], &var[tc[wpc[3]]], 0);
        (中略)
        } else if (phrCmp( 0, "!!*0:", pc)) {	// ラベル定義命令.
!           defLabel(tc[wpc[0]]); // ラベルに対応するicqを記録しておく.
        (中略)
!       } else if (phrCmpPutIcX64( 7, "time;", pc, 0, 0, TcSubTime, &e0)) {
    (中略)
    putIcX64("%R_81_c4_f8_01_00_00;", 0, 0, 0, 0);
    putIcX64("58; 59; 5a; 5b; 5c; 5d; 5e; 5f; 41_58; 41_59;", 0, 0, 0, 0);
    putIcX64("41_5a; 41_5b; 41_5c; 41_5d; 41_5e; 41_5f; c3;", 0, 0, 0, 0);
    icq1 = icq;
+   for (i = 0; i < jp; i++) { // ジャンプ命令の最適化.
+       icq = jmps[i] + ic; // icq=飛び先のラベル番号を書いておいた場所.
+       j = var[get32(icq)]; // ラベル番号を取得.
+       icp = j + ic; // icp=飛び先の命令列の先頭.
+       while (*icp == 0xe9) {  // 飛び先がジャンプ命令だったら、さらにその先を読む.
+           put32(icq, get32(icp + 1));	// 飛び先のラベル番号を上書きする.
+           j = var[get32(icp + 1)];
+           icp = j + ic;
+       }
+   }
+   for (i = 0; i < jp; i++) { // ジャンプ先の設定(相対値にする).
+       icq = jmps[i] + ic;
+       j = var[get32(icq)]; // ラベル番号を取得.
+       icp = j + ic; // icp=飛び先の命令列の先頭.
+       put32(icq, icp - (icq + 4));
+   }
    return icq1 - ic;
err:
    printf("syntax error : %s %s %s %s\n", ts[tc[pc]], ts[tc[pc + 1]], ts[tc[pc + 2]], ts[tc[pc + 3]]);
    return -1;
}

int run(String s)
{
    if (compile(s) < 0)
        return 1;
    void (*func)() = (void (*)()) ic;
+   t0 = clock();
    func();
    return 0;
}

(後略)
  • プログラムは795行になりました。これで毎度の以下のプログラムが実行できます(HL-3のときと同じものです)。
        i = 0;
    label:
        i = i + 1;
        if (i < 100000000) goto label;
        time;
  • さっそく実行してみましょう。・・・おお、HL-9aと比べてちょっとだけ速くなりました。
    a21_txt01_3HL-3148行7.0KB条件分岐などをサポートしてループ処理が可能に1520倍
    a21_txt01_5HL-5214行7.5KB少し高速化260倍
    a21_txt01_6HL-6284行8.0KBもっと高速化(がんばった!)13.2倍
    a21_txt01_6aHL-6a297行8.5KBさらに高速化!(これをやるかどうかは好みが分かれるかも)5.5倍
    a21_txt01_9aHL-9a772行20.0KBC言語っぽく改造5.5倍
    a21_txt02_2HL-12745行16.0KBループ速度の測定ができるところまで(x86, 32bit)5.3倍
    a21_txt02_8HL-18795行27.0KBループ速度の測定ができるところまで(x64, 64bit)4.2倍
  • しかし、なぜHL-12とHL-18で違う結果になったのでしょうか。64bitだから速いという短絡的な説明も可能ですが、しかし10億回ループなら32bitで64bitでも同じはずです。64bitなCPUで32bit命令を実行するとペナルティがあるのでしょうか。それともコードアラインの都合でしょうか。
    • (以下は余談です。)
    • コードアラインのせいかもしれないと思ったので、HL-12aでcode命令を使って実験しました。
    • 実験の結果、コードアラインは関係ありませんでした。
    • INC命令を「40」から「ff c0」に変更してみましたが、これも実行速度に影響しませんでした。
    • そしてメモリアクセスを[EBP+?]の形式に変更してみたところ・・・おお、HL-18と同じ速さになりました!・・・これかー!!
    • しかもさらに実験してみたところ、[EBP+?]の?の部分が大きいと、元の速さに戻ってしまうこともわかりました。だからEBP=0にして、mod r/mを05→85にするだけでは全く速くならないこともわかりました。
    • ?の部分が1バイトに収まるかどうかは重要ではなく、それよりも大きい時でも高速化されます。その境界がどのあたりにあるのかは、まだ調べ切れていません。

(2) プログラムの説明

  • 主な改造ポイント
  • [1] putIcX64()が %l を受け付けられるようにしました。
    • これは、 %l を書くとそこにラベルと同名の変数のポインタを書き込みます。これは仮の値です。
    • なぜそんなことをするのかというと、飛び先のアドレスが決まるのは先かもしれないので、今は飛び先のアドレスがどこに書いてあるのかだけを記録しておいて、最後に(=確実にアドレスが全部決まった段階で)一気に再計算します。それはcompile()の「ジャンプ先の設定(相対値にする)」のところでやっています。
    • 最初にひとまず仮の値を書いておいて、あとで本来の値を計算するという方式そのものは、HL-6と同じです。
  • [2] defLabel()関数を作りました。
    • 現状でやっていることは「var[i] = icq - ic;」だけなので、それならHL-6のころと全く同じです。だから現時点で関数にする必要はないのですが、この先で最適化に取り組むとラベル定義時にいろいろやりたくなるので、今のうちから関数化しておくことにします。
  • [3] compile()にジャンプ命令の最適化を入れました。
    • これはHL-8で導入した、ジャンプ先がgoto命令だったらそこへいきなり分岐するように飛び先を上書きする機能と同等のものです。プログラムでは命令e9を見つけたら飛び先の上書をしています。e9というのはx64におけるgoto命令のことです。
    • とはいえ、現状ではプログラムは命令e9を生成することはありません。だからHL-18の段階ではこの部分は全くの役立たずです。

次回に続く

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-06-03 (木) 19:56:57 (115d)