川合のプログラミング言語自作のためのテキスト#0005

  • (by K, 2019.06.29)

(10) TJ-03a

  • お待たせしました。さあついにJITコンパイラです。プログラミング言語の最前線です。
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <time.h>
    #include <windows.h>
    
    typedef unsigned char *String;	// こう書くと String は unsigned char * の代用になる.
    
    void loadText(int argc, const char **argv, unsigned char *t, int siz) → TL-1cと同じなので省略
    int isAlphabet(unsigned char c) → TL-2cと同じなので省略
    int lexer(String s, String b, String t[]) → TL-2cと同じなので省略
    
    enum { EAX = 0, ECX = 1 }; // 定数宣言.
    
    void sub_print(int i)
    {
        printf("%d\n", i);
    }
    
    void sub_time()
    {
        printf("time=%.3f[sec]\n", clock() / (double) CLOCKS_PER_SEC);
    }
    
    int put32(unsigned char *q, int i)
    {
        q[0] =  i        & 0xff;
        q[1] = (i >>  8) & 0xff;
        q[2] = (i >> 16) & 0xff;
        q[3] = (i >> 24) & 0xff;
        return 4;
    }
    
    int main(int argc, const char **argv)
    {
        static String def[] = { ";", "=", "+", "-", "print", "while", "(", "<", ")", "{", "}", "time", 0 };
        int i, vars = 0, pc, pc1, qc = 0, wqc = 0, wqc2 = 0, var[256], varNum[1000];	// 変数と変数番号.
        String t[1000], varName[256];	// トークンと変数名.
        unsigned char txt[10000], buf[10000]; // ソースコードとトークン用のバッファ.
        unsigned char *code = VirtualAlloc(0, 1024 * 1024, MEM_COMMIT, PAGE_EXECUTE_READWRITE); // Windowsに対して、実行権限のあるメモリを特別に要求.
        void (*func)();	// funcは関数へのポインタ型の変数.
        loadText(argc, argv, txt, 10000);
        pc1 = lexer(txt, buf, t);
        t[pc1] = t[pc1 + 1] = t[pc1 + 2] = t[pc1 + 3] = "";	// エラー表示用のために末尾にいくつか長さ0の文字列を登録しておく.
        for (i = 0; def[i] != 0; i++)
            varName[i] = def[i];
        vars = i;
        code[qc++] = 0x83; // SUB ESP,124.  この命令でスタックを調整させる.
        code[qc++] = 0xec;
        code[qc++] = 0x7c;
        for (pc = 0; pc < pc1; pc++) {
            for (i = 0; i < vars; i++) { // 登録済みの中から探す.
                if (strcmp(t[pc], varName[i]) == 0)
                    break;
            }
            if (i == vars) {
                varName[i] = t[pc]; // 見つからなかったので新規登録.
                var[i] = strtol(t[pc], 0, 0);	// 初期値を設定.
                vars++;
            }
            varNum[pc] = i;
        }
        for (pc = 0; pc < pc1; pc++) {
            if (varNum[pc + 1] == 1 /* = */) { // 2単語目が"=".
                code[qc++] = 0x8b; // MOV EAX,[...]
                code[qc++] = EAX * 8 + 0x05;
                qc += put32(&code[qc], (int) &var[varNum[pc + 2]]);
                if (varNum[pc + 3] == 0 /* ; */) { // 単純代入.
                } else if (varNum[pc + 3] == 2 /* + */ && varNum[pc + 5] == 0 /* ; */) {  // 加算.
                    code[qc++] = 0x8b; // MOV ECX,[...]
                    code[qc++] = ECX * 8 + 0x05;
                    qc += put32(&code[qc], (int) &var[varNum[pc + 4]]);
                    code[qc++] = 0x01;
                    code[qc++] = 0xc8;
                } else if (varNum[pc + 3] == 3 /* - */ && varNum[pc + 5] == 0 /* ; */) {  // 減算.
                    code[qc++] = 0x8b; // MOV ECX,[...]
                    code[qc++] = ECX * 8 + 0x05;
                    qc += put32(&code[qc], (int) &var[varNum[pc + 4]]);
                    code[qc++] = 0x29;
                    code[qc++] = 0xc8;
                } else
                    goto err;
                code[qc++] = 0xa3; // MOV [...],EAX
                qc += put32(&code[qc], (int) &var[varNum[pc]]);
            } else if (varNum[pc] == 5 /* while */ && varNum[pc + 1] == 6 /* ( */ && varNum[pc + 3] == 7 /* < */ && varNum[pc + 5] == 8 /* ) */ && varNum[pc + 6] == 9 /* { */) {
                wqc = qc;
                code[qc++] = 0x8b; // MOV EAX,[...]
                code[qc++] = EAX * 8 + 0x05;
                qc += put32(&code[qc], (int) &var[varNum[pc + 2]]);
                code[qc++] = 0x8b; // MOV ECX,[...]
                code[qc++] = ECX * 8 + 0x05;
                qc += put32(&code[qc], (int) &var[varNum[pc + 4]]);
                code[qc++] = 0x39;
                code[qc++] = 0xc8;
                code[qc++] = 0x0f;
                code[qc++] = 0x8d;
                qc += put32(&code[qc], 0);
                wqc2 = qc;
                pc += 7 - 1;
                continue;
            } else if (varNum[pc] == 10 /* } */) {
                code[qc++] = 0xe9;
                qc += put32(&code[qc], &code[wqc] - &code[qc + 4]);
                put32(&code[wqc2 - 4], &code[qc] - &code[wqc2]);
                continue;
            } else if (varNum[pc] == 11 /* time */ && varNum[pc + 1] == 0 /* ; */) { // time.
                code[qc++] = 0xe8;
                qc += put32(&code[qc], (unsigned char *) sub_time - &code[qc + 4]);
            } else if (varNum[pc] == 4 /* print */ && varNum[pc + 2] == 0 /* ; */) { // print.
                code[qc++] = 0x8b; // MOV EAX,[...]
                code[qc++] = EAX * 8 + 0x05;
                qc += put32(&code[qc], (int) &var[varNum[pc + 1]]);
                code[qc++] = 0x89;
                code[qc++] = 0x04;
                code[qc++] = 0x24;
                code[qc++] = 0xe8;
                qc += put32(&code[qc], (unsigned char *) sub_print - &code[qc + 4]);
            } else
                goto err;
            while (varNum[pc] != 0 /* ; */)
                pc++;
        }
        code[qc++] = 0x83; // ADD ESP,124.  最初に調整したスタックを元に戻す.
        code[qc++] = 0xc4;
        code[qc++] = 0x7c;
        code[qc++] = 0xc3; // RET
        func = (void *) code;
        func();
        exit(0);
    err:
        printf("syntax error : %s %s %s %s\n", t[pc], t[pc + 1], t[pc + 2], t[pc + 3]);
        exit(1);
    }
  • 重要な注意点:
    • このプログラムはWindows用に書かれています。しかも32ビットアプリです。gccでコンパイルする場合は-m32オプションを忘れずにつけましょう。
    • もしWindows以外で実行したい場合は、以下のように書き換えてください。
  • [Q] macOSではどうやればTJ-03が動くの?
    • まず冒頭の #include <windows.h> を以下と入れ替えます。
      #include <mach/mach.h>
    • そんでもって、codeへの代入文を以下のように書き換えます。
      code = malloc(1024 * 1024); vm_protect(mach_task_self(), (vm_address_t) code, 1024 * 1024, FALSE, VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE);
    • これで行けるはずです。
    • 要するにメモリ領域code[]に実行可能権限を付ければいいのです。
    • そして32ビットアプリとしてコンパイルするのを忘れずに。
  • [Q] LinuxではどうやればTJ-03が動くの?
  • このTJ-03aはTL-3cやTL-3dと完全互換です。違うのは実行速度だけです。だから以下の1億回ループのプログラムもそのまま実行できます。
    i = 0;
    while (i < 100000000) {
        i = i + 1;
    }
    print i;
    time;
  • 実行速度を比較してみてください。TL-3dはTL-3cと比べて11.3倍の速さを誇っていましたが、TJ-03aはそのTL-3dと比較しても8.1倍の速さが出るはずです。・・・JITコンパイラがどれほどすごいか感じてもらえたのではないでしょうか?
  • しかもこのJITコンパイラはTL-3dと比べてコードを複雑にしないために結構手抜きをしています。つまりまだ速くなる余地を残しているのです。それでもこんなに速いのです。
  • 正直、プログラムの中身は良くわからないところがたくさんあると思います。でも行数的には全然大したことはないということにも気づいてください。JITコンパイラは複雑で難しい技術なのではなく、要するに機械語を知っているかどうかの知識の差でしかないのです。プログラミング的な難易度は大したことないのです。・・・これを手掛けない理由があるでしょうか!(笑)。・・・そしてこれを機械語の知識なしに書ける時代がもし来たら・・・。

(11) TJ-03aの説明

  • 機械語が得意でたまらないという奇特な人を除けば、さすがにこれを説明なしで理解することはできないでしょう。
  • まず、上記のサンプルプログラムが、どんな機械語に変換されているのかを示します。
    ソースコード生成された機械語(16進数)機械語をアセンブラで書き直したもの(参考用)アセンブラをさらにC言語っぽく書いてみたもの(参考用)補足説明
    83 EC 7CSUB ESP,124ESP -= 124;スタック領域に作業用スペースを確保(ソースコードに無関係に生成)
    i = 0;8B 05 xx xx xx xxMOV EAX,[xxxxx]EAX = [xxxx];xxxxは変数「0」に対応するアドレス
    A3 xx xx xx xxMOV [xxxx],EAX[xxxx] = EAX;xxxxは変数「i」に対応するアドレス
    while (i < 100000000) {8B 05 xx xx xx xxMOV EAX,[xxxx]EAX = [xxxx];xxxxは変数「i」に対応するアドレス
    8B 0D xx xx xx xxMOV ECX,[xxxx]ECX = [xxxx];xxxxは変数「100000000」に対応するアドレス
    39 C8CMP EAX,ECXif (EAX >= ECX)
    0F 8D 18 00 00 00JGE $+24goto 24バイト先このとび先は}を発見してから書き込んでいる
    i = i + 1;8B 05 xx xx xx xxMOV EAX,[xxxx]EAX = [xxxx];xxxxは変数「i」に対応するアドレス
    8B 0D xx xx xx xxMOV ECX,[xxxx]ECX = [xxxx];xxxxは変数「1」に対応するアドレス
    01 C8ADD EAX,ECXEAX += ECX;
    A3 xx xx xx xxMOV [xxxx],EAX[xxxx] = EAX;xxxxは変数「i」に対応するアドレス
    }E9 D4 FF FF FFJMP $-44goto 44バイト前これはwhile命令のところを指している
    print i;8B 05 xx xx xx xxMOV EAX,[xxxx]EAX = [xxxx];xxxxは変数「i」に対応するアドレス
    89 04 24MOV [ESP],EAX[ESP] = EAX;第一引数にセット(第一引数=スタックトップ)
    E8 xx xx xx xxCALL _sub_printsub_print();C言語で書かれた関数を呼び出す
    time;E8 xx xx xx xxCALL _sub_timesub_time();C言語で書かれた関数を呼び出す
    83 C4 7CADD ESP,124ESP += 124;スタック領域の作業用スペースを解放(ソースコードに無関係に生成)
    C3RETreturn;機械語関数を終了(ソースコードに無関係に生成)
  • x86の32ビットの機械語では、レジスタと呼ばれるCPU内の変数を使って処理を進めていきます。上記で出てきている、EAX, ECX, ESPというのはどれもレジスタ名です。他にも5つのレジスタがあり、合計8つのレジスタがあります(本当は他にもありますが、それらは用途がかなり特殊化されており、自由には使えません)。
    • またこのESPはスタックの管理のために使うレジスタなので、それほど自由には使えません。
  • TJ-03aでは変数iなどはvar[]の中にあり、つまりこれはメモリ上にあるので、MOV命令でレジスタに読み込んだり、MOV命令でレジスタから書き込んだりして処理を進めています。
  • 機械語は覚えるのが容易ではないので、コード表などから調べてきます。でもフル仕様のコード表はそれだけですごい量なので、簡易版を参照するといいかもしれません。

(12) なぜ32ビットコードにしたのか?

  • 今は64ビット対応のCPUがかなり普及して、OSやコンパイラも64ビット対応したものが入手しやすくなっています。だから64ビットで作ってしまえば、先進的でよさそうに思うかもしません。
  • 64ビット化することで大きく変わるのは、使えるレジスタの数です。32ビットでは自由に使えるレジスタが7本ありますが、64ビットでは15本になります。それ以外では、32ビットモードではポインタが4バイトで64ビットモードではポインタが8バイトになるくらいの違いしかありません。・・・レジスタはキャッシュメモリみたいな効果があります。だからキャッシュメモリが倍増すると思ってください。ただしキャッシュメモリとは違って、コンパイラが上手にレジスタ割り当てを行わなければ性能は出ません。だからJITコンパイラでレジスタ割り当てを頑張る気がないのであれば、64ビットに手を出しても自己満足以上のものは得られません(まあ2GBを超える巨大な配列を扱えるというメリットもありますが)。
  • 仮に割り付けを十分に頑張ったとして、レジスタが倍増すると速度も倍増するでしょうか?いいえ、違います。上位7個の頻出変数をレジスタにキープするだけで全体のアクセスのかなりの割合がカバーできます。そしてそれが15個に増えてもカバー率はせいぜい1割くらいしか向上しません。だから速度もその程度しか変わりません(だから一般にアプリやOSが64ビット化しても実行速度は大きくは向上しないわけです)。
  • また64ビットの機械語はややこしいことになっているので、32ビットの機械語よりも複雑です。さらに64ビットではC言語での呼び出し規約がOS間で統一されていないという問題もあります。・・・ということでいきなり64ビットのJITコンパイラに挑戦して失敗のリスクを上げても、得られるメリットは大きくないので、お勧めしがたいのです。
  • もちろん32ビットのJITコンパイラが書けるようになってから、64ビットのJITコンパイラに挑戦してみるというのは、十分によい選択肢だと思います。差異はそれほど大きくはありませんので、32ビットでできるようになった後なら、きっと乗り越えられるでしょう。

次回に続く

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-06-29 (土) 19:46:55 (84d)