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

  • (by K, 2019.06.29)

(14) TJ-03c

  • TJ-03bではgccの速さに到達できなかったので、さらにもう一つの高速化テクニックを紹介します。
  • TJ-03bとgccでは、機械語はこんな感じになっています(読みやすさのためにアセンブラで書いて代用しています)。
    // TJ-03b.
        MOV EBX,0
    cont:
        CMP EBX,100000000  // ループ処理.
        JGE break;         // ループ処理.
        ADD EBX,1
        JMP cont           // ループ処理.
    break:
        (print i;の機械語)
        (time;の機械語)
    
    
    // gccの場合.
        MOV EBX,0
    cont:
        ADD EBX,1
        CMP EBX,100000000  // ループ処理.
        JL  cont           // ループ処理.
    break:
        (print i;の機械語)
        (time;の機械語)
  • つまり、TJ-03bのレジスタ変数の導入によって i = i + 1; が4命令から1命令になったのは快挙だったのですが、それでもループ処理はまだ3命令もあり、gccはこれを2命令にまで減らしているのです。だからむやみに速いのです。
  • TJ-03aではループ処理は5命令でした。それがTJ-03bでは3命令になりました。そしてTJ-03cではこれをgccと同じ2命令にしようと考えているのです。
  • まずgccが内部で何をやっているのかを説明しましょう。gccはwhileループを以下のdo~whileループに書き換えます。
    • [書き換え前] i = 0; while (i < 100000000) { i = i + 1; }
    • [書き換え後] i = 0; do { i = i + 1; } while (i < 100000000);
  • まずこの書き換えによって処理内容に違いがないことを確認してください。
  • さてではなぜこの書き換えをするかですが、do~whileにするとJMP命令を省略できるようになるからです。より詳しく言うと、比較の後の条件ジャンプがループ先頭へ戻るためのJMP命令を兼ねられるようになるのです。
  • ということでなぜgccがTJ-03bよりも高速になっているのかはこれで分かりました。
  • ではTJ-03cではどうしたらいいでしょうか。gccみたいに「書き換えができるケースは自動的に書き換えを実施する」・・・のをここでやるのはちょっと面倒なので、新規にdo { ~ } while構文を追加して、この構文を使えばgccと同じくらいに高速になるよー、ということにします。
    → mainより前の部分はTJ-03bと同じなので省略
    
    int main(int argc, const char **argv)
    {
        static String def[] = { ";", "=", "+", "-", "print", "while", "(", "<", ")", "{", "}", "time", "do", 0 };
        → この部分もTJ-03bと同じなので省略
        for (pc = 0; pc < pc1; pc++) {
            if (varNum[pc + 1] == 1 /* = */) { // 2単語目が"=".
                → この部分もTJ-03bと同じなので省略
            } else if (varNum[pc] == 12 /* do */ && varNum[pc + 1] == 9 /* { */) {
                wqc = qc;
                pc++;
                continue;
            } else if (varNum[pc] == 10 /* } */ && varNum[pc + 1] == 5 /* while */ && varNum[pc + 2] == 6 /* ( */ && varNum[pc + 4] == 7 /* < */ && varNum[pc + 6] == 8 /* ) */ && varNum[pc + 7] == 0 /* ; */) {
                if (varNum[pc + 3] == regvar && '0' <= varName[varNum[pc + 5]][0] && varName[varNum[pc + 5]][0] <= '9') {
                    code[qc++] = 0x81;
                    code[qc++] = 0xc0 + 7 * 8 + EBX;
                    qc += put32(&code[qc], var[varNum[pc + 5]]);
                } else {
                    if (varNum[pc + 3] == regvar || varNum[pc + 5] == regvar) goto err;
                    code[qc++] = 0x8b; // MOV EAX,[...]
                    code[qc++] = EAX * 8 + 0x05;
                    qc += put32(&code[qc], (int) &var[varNum[pc + 3]]);
                    code[qc++] = 0x8b; // MOV ECX,[...]
                    code[qc++] = ECX * 8 + 0x05;
                    qc += put32(&code[qc], (int) &var[varNum[pc + 5]]);
                    code[qc++] = 0x39;
                    code[qc++] = 0xc8;
                }
                code[qc++] = 0x0f;
                code[qc++] = 0x8c;
                qc += put32(&code[qc], &code[wqc] - &code[qc + 4]);
            } else if (varNum[pc] == 5 /* while */ && varNum[pc + 1] == 6 /* ( */ && varNum[pc + 3] == 7 /* < */ && varNum[pc + 5] == 8 /* ) */ && varNum[pc + 6] == 9 /* { */) {
                → この部分もTJ-03bと同じなので省略
            } else if (varNum[pc] == 10 /* } */) {
                → この部分もTJ-03bと同じなので省略
            } else if (varNum[pc] == 11 /* time */ && varNum[pc + 1] == 0 /* ; */) { // time.
                → この部分もTJ-03bと同じなので省略
            } else if (varNum[pc] == 4 /* print */ && varNum[pc + 2] == 0 /* ; */) { // print.
                → この部分もTJ-03bと同じなので省略
            } else
                goto err;
            while (varNum[pc] != 0 /* ; */)
                pc++;
        }
        → この部分もTJ-03bと同じなので省略
    }
  • do~whileを使った1億回ループのサンプルプログラムを以下に示します。
    i = 0;
    do {
        i = i + 1;
    } while (i < 100000000);
    print i;
    time;

次回に続く

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-06-30 (日) 07:24:36 (139d)