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

  • (by K, 2019.06.29)

(13) TJ-03b

  • TJ-03aはTL-3dと比較すると圧倒的に高速でしたが、しかしまだ簡単に速くする余地が残っています。それをここで紹介したいと思います。
  • C言語には「レジスタ変数」という機能があります。しかし最近のCコンパイラはこの機能を使わなくても最適化によって自動的に同等の速さが出ます。だから自作言語でも、レジスタ変数をサポートすれば、C言語に負けない速さがでる・・・かもしれないのです。
  • どうですか?面白そうじゃないですか?ということでやってみましょう。
    #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, EBX = 3 }; // 定数宣言.
    
    void sub_print(int i) → TJ-03aと同じなので省略
    void sub_time() → TJ-03aと同じなので省略
    int put32(unsigned char *q, int i) → TJ-03aと同じなので省略
    
    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, regvar, 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];
        regvar = vars = i;
        code[qc++] = 0x60; // PUSHAD.
        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単語目が"=".
                if (varNum[pc + 3] == 0 /* ; */) { // 単純代入.
                    if (varNum[pc] == regvar && '0' <= varName[varNum[pc + 2]][0] && varName[varNum[pc + 2]][0] <= '9') { // regvar = const;
                        code[qc++] = 0xb8 + EBX;
                        qc += put32(&code[qc], var[varNum[pc + 2]]);
                    } else {
                        if (varNum[pc] == regvar || varNum[pc + 2] == regvar) goto err;
                        code[qc++] = 0x8b; // MOV EAX,[...]
                        code[qc++] = EAX * 8 + 0x05;
                        qc += put32(&code[qc], (int) &var[varNum[pc + 2]]);
                        code[qc++] = 0xa3; // MOV [...],EAX
                        qc += put32(&code[qc], (int) &var[varNum[pc]]);
                    }
                } else if (varNum[pc + 3] == 2 /* + */ && varNum[pc + 5] == 0 /* ; */) {  // 加算.
                    if (varNum[pc] == regvar && varNum[pc] == varNum[pc + 2] && '0' <= varName[varNum[pc + 4]][0] && varName[varNum[pc + 4]][0] <= '9') { // regvar = regvar + const;
                        code[qc++] = 0x81;
                        code[qc++] = 0xc0 + EBX;
                        qc += put32(&code[qc], var[varNum[pc + 4]]);
                    } else {
                        if (varNum[pc] == regvar || varNum[pc + 2] == regvar || varNum[pc + 4] == regvar) goto err;
                        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++] = 0x01;
                        code[qc++] = 0xc8;
                        code[qc++] = 0xa3; // MOV [...],EAX
                        qc += put32(&code[qc], (int) &var[varNum[pc]]);
                    }
                } else if (varNum[pc + 3] == 3 /* - */ && varNum[pc + 5] == 0 /* ; */) {  // 減算.
                    if (varNum[pc] == regvar || varNum[pc + 2] == regvar || varNum[pc + 4] == regvar) goto err;
                        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++] = 0x29;
                        code[qc++] = 0xc8;
                        code[qc++] = 0xa3; // MOV [...],EAX
                        qc += put32(&code[qc], (int) &var[varNum[pc]]);
                } else
                    goto err;
            } else if (varNum[pc] == 5 /* while */ && varNum[pc + 1] == 6 /* ( */ && varNum[pc + 3] == 7 /* < */ && varNum[pc + 5] == 8 /* ) */ && varNum[pc + 6] == 9 /* { */) {
                wqc = qc;
                if (varNum[pc + 2] == regvar && '0' <= varName[varNum[pc + 4]][0] && varName[varNum[pc + 4]][0] <= '9') {
                    code[qc++] = 0x81;
                    code[qc++] = 0xc0 + 7 * 8 + EBX;
                    qc += put32(&code[qc], var[varNum[pc + 4]]);
                } else {
                    if (varNum[pc + 2] == regvar || varNum[pc + 4] == regvar) goto err;
                    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.
                if (varNum[pc + 1] == regvar) {
                    code[qc++] = 0x89;
                    code[qc++] = 0x04 + EBX * 8;
                    code[qc++] = 0x24;
                } else {
                    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++] = 0x61; // POPAD.
        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);
    }
  • 結局どこを改造したのかというと、代入、加算、while、printで、引数が特定のパターンの時に特別なコード生成をしているだけです。なお、変数regvarというのは、レジスタ変数にする変数番号のことで、最初に出てきた変数名が該当します。内部的にはEBXレジスタに割り当てられます。
  • これにより、処理が以下のように単純化されます。
    処理普通の変数の場合レジスタ変数の場合
    i = 3;[2命令] MOV(EAX,[....]); MOV([....],EAX);[1命令] MOV(EBX,3);
    i = i + 5;[4命令] MOV(EAX,[...]); MOV(ECX,[...]); ADD(EAX,ECX); MOV([....],EAX);[1命令] ADD(EDX,5);
  • ということで、TJ-03aと比較して4倍くらい速くなります(1億回ループの場合)。まあCPUにもよりますが。
  • でもgccはさらに速いコードを生成しています。ということで、次回ではもっと速くする方法を紹介します。

次回に続く

こめんと欄


コメントお名前NameLink

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