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

  • (by K, 2021.04.14)

(1) HL-12

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

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

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

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

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

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

void putIcX86_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] == 'r') {	// relative.
                put32(icq, (int) a[j] - (int) (icq + 4));
                icq += 4;
            }
+           if (s[i + 2] == 'l') {	// label.
+               put32(icq, (int) a[j]);
+               jmps[jp] = icq - ic; // ジャンプ命令のラベル番号を書いた場所を記憶.
+               jp++;
+               icq += 4;
+           }
            i += 3;
        } else {
            printf("putIcX86: error: '%s'\n", s);
            exit(1);
        }
    }
}

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

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

(中略)

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

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

clock_t t0; [この行追加]

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

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

(中略)

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

(中略)

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;
    putIcX86("60; 83_ec_7c;", 0, 0, 0, 0); // PUSHAD(); SUB(ESP,124);
    (中略)
        } 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]]) {
!           putIcX86("8b_%1m0; 40; 89_%1m0; 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 (phrCmpPutIcX86( 7, "time;", pc, 0, 0, sub_time, &e0)) {
    (中略)
    putIcX86("83_c4_7c; 61; c3;", 0, 0, 0, 0); // ADD(ESP,124); POPAD(); RET();
    icq1 = icq;
+   for (i = 0; i < jp; i++) { // ジャンプ命令の最適化.
+       icq = jmps[i] + ic; // icq=飛び先のラベル番号を書いておいた場所.
+       j = *(IntP) get32(icq); // ラベル番号を取得.
+       icp = j + ic; // icp=飛び先の命令列の先頭.
+       while (*icp == 0xe9) {  // 飛び先がジャンプ命令だったら、さらにその先を読む.
+           put32(icq, get32(icp + 1));	// 飛び先のラベル番号を上書きする.
+           j = *(IntP) get32(icp + 1);
+           icp = j + ic;
+       }
+   }
+   for (i = 0; i < jp; i++) { // ジャンプ先の設定(相対値にする).
+       icq = jmps[i] + ic;
+       j = *(IntP) 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;
}

(後略)
  • プログラムは745行になりました。これで毎度の以下のプログラムが実行できます(HL-3のときと同じものです)。
        i = 0;
    label:
        i = i + 1;
        if (i < 100000000) goto label;
        time;
  • さっそく実行してみましょう。・・・あれ?HL-9aと比べて、ほんの少ししか速くなっていません。せっかくJITコンパイラ化までしてがんばったのに・・・。
    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ループ速度の測定ができるところまで5.3倍

(2) なぜ速くならなかったのか?

  • 理由は、つまり、もとのHL-9aが速すぎたんです。JITコンパイラなしでgcc-O3比で5.5倍っていうのは、かなり驚異的なスピードです。普通はこんなにうまくいきません。
  • しかし、そうだとしても、この結果はあまりにさみしいです。JITコンパイラ化したせいでプログラムはCPUに依存するようになっているというのに、こんな小さな成果しか出ないなんて・・・。
  • そもそもJITコンパイラは機械語を生成して実行しているわけですよね。それなら究極的にはgccと同じくらいに速くなってもいいじゃないですか。こんな程度で妥協したくありません。
  • そしてなにより私はHL-12がどうも信じられません。だって挙動がHL-9aのときと全く同じじゃないですか。これ、本当に機械語を作っているんでしょうか?
  • 疑いを持つのはいいことです。では、次回のHL-12aでは、これらの疑問を解決するための改造をやることにします。

(3) プログラムの説明

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

次回に続く

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-04-15 (木) 13:02:31 (191d)