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

  • (by K, 2021.05.12)

(1) HL-20

  • さて、とにかくJITコンパイラにはなったものの、生成している機械語の質が低いので、gcc-O3と比べるとまだまだ速度で負けています。
ページ名名前行数.exeの大きさ説明速度のめやす1速度のめやす2
[ a21_txt01 ]HL-1~HL-9a49行~772行6.0KB~20.0KB「10日くらいでできる!プログラミング言語自作入門」1520倍~5.5倍6.4倍
a21_txt02_7HL-17741行25.0KBx64に対応したJITコンパイラ第1号計測不能計測不能
a21_txt02_7aHL-17a756行26.0KB簡単な演算もサポート計測不能計測不能
a21_txt02_8HL-18795行27.0KBループ速度の測定ができるところまで4.2倍計測不能
a21_txt02_8aHL-18a816行27.5KBcodedumpコマンドと、codeコマンドの追加4.2倍計測不能
a21_txt02_9HL-19893行35.5KB配列以外は全部JITコンパイラ対応させる(mandel.cで速さを実感!)4.2倍1.8倍
a21_txt02_9aHL-19a899行36.0KB配列もJITコンパイラ対応させる(ついに機能的にはHL-9a相当に!)4.2倍1.8倍
  • さすがに追いついたり追い越したりはできないと思いますが、でももうちょっと近づきたいとは思うので、ここからしばらくは最適化をやってスピードアップをしたいと思います。

  • 最適化をどこからやるかですが、おそらく効果が一番あるのは「レジスタ変数」のサポートです。HL-19aでは、変数はすべてメモリ上にありました。これをRAXレジスタに読み込ませて、演算をして、RAXに結果が生成されて、それをメモリ書き戻しています。多くの場合この一連の処理の中で一番のボトルネックはメモリへの読み書きで、これをなくしてレジスタ内の演算だけにすればきっと速くなると思われます。
  • x64の場合、演算に使えそうなレジスタは、RAXのほかにRCX、RDX、RBX、RBP、RSI、RDI、R08~R15があって合計15個です。でもこのうちのRAX、RCX、RDXの3つは、割り算やシフト命令や配列アクセスなどで使用するために、そこそこの頻度で値が壊される危険があります。またHL-19aではRBPも var[ ] へのアクセスのために多用しているので使えません。
  • その上、関数呼び出しで破壊されるレジスタがたくさんあります。結局、自由に使えるのは以下のものだけになります。
    • [ABI_MSW64のとき] RBX、RSI、RDI、R12~R15 (合計7つ)
    • [ABI_SYSV64のとき] RBX、R12~R15 (合計5つ)
  • 一方で、プログラムで使われる変数は5個よりも多いことが普通で、だからすべての変数をレジスタ変数に割り当てることはできません。一般には使用頻度の高い変数をレジスタ変数に割り当てることになります。・・・それで、どの変数をレジスタ変数に割り当てるべきか、gccなどのコンパイラはプログラムを解析してすごい努力をして決定しています。おそらコンパイルに時間がかかっている主たる理由はこれなのではないかと私は思っています。
  • ではHL-20ではどうしましょうか。人間が見れば、この変数をレジスタ変数にしたらよさそうだなっていうのは結構簡単にわかります。ループの最も内側で使っている変数とかを速くすればいいだけなのです。しかしそれを自動判定するプログラムは、きっとすごく大変なので、私はここで扱いたくありません。ということで、人間が自由に指定することにします。機械が得意なことは機械がやって、人間が得意なことは人間がやればいいのです。
  • ということで regVar()コマンドを作ります。
    regVar(0, x); regVar(1, y); regVar(2, z);
  • とすると、xを優先度0でレジスタ変数化してほしくて(=最優先)、yを優先度1でレジスタ変数化してほしくて、zを優先度2でレジスタ変数化してほしい、ということにしました。というのは、HLシリーズはx64以外のCPUにも対応していくかもしれません。そしたら使えるレジスタ変数の数もきっと変わるでしょう。その場合は優先度を見て、順番に割り当てさせることにします。もしレジスタが足りなくなったら、優先度の低いものについてはメモリ割り付けのままにします。
  • 上記のように三回もregVarと入力するのは面倒なので、
    regVar(0, x, y, z);
  • という省略形も使えるようにします。
  • 関数の形にしているのは、プログラム内で使った時にC言語との互換性を維持できるようにするためです。C言語で使うときは、
    #define regVar(...)
  • などと書いて、regVar()命令を無視させるようにします。

  • [1]putIcX64_sub()関数の前に以下を追加
    #if (ABI_MSW64 != 0)
        #define RegVarLen 7
        int regVarNo[7] = { 3, 6, 7, 12, 13, 14, 15 }; // レジスタ変数番号から、レジスタ番号に変換.
    #elif (ABI_SYSV64 != 0)
        #define RegVarLen 5
        int regVarNo[5] = { 3, 12, 13, 14, 15 }; // レジスタ変数番号から、レジスタ番号に変換.
    #endif
    IntP regVarTbl[RegVarLen]; // レジスタ変数の割り当て状況を記憶.
    
    int regVar(IntP v) // もし変数vがレジスタに割り当てられていれば、0~7を返す. そうでなければ-1を返す.
    {
        int i;
        for (i = 0; i < RegVarLen; i++) {
            if (regVarTbl[i] == v)
                return i;
            }
            return -1;
    }
  • [2]putIcX64_sub()関数の一部を改造
                if (s[i + 2] == 'm') {	// mod r/m.
                    k = s[i + 3] - '0';
                    if (s[i + 3] >= 'a') { // もしかしたらこの記述は最後まで出番がないかも.
                        k = s[i + 3] - 'a' + 10;
                    }
    +               if (k >= 8) {
    +                   *putIcX64_rex += 4;
    +                   k -= 8;
    +               }
    +               int rv = regVar(a[j]);
    +               if (rv < 0) {
                        *icq = 0x85 + k * 8;
                        put32(icq + 1, (a[j] - var) * 8);
                        icq += 5;
    +               } else {
    +                   rv = regVarNo[rv];
    +                   if (rv >= 8) {
    +                       *putIcX64_rex += 1;
    +                       rv -= 8;
    +                   }
    +                   *icq = 0xc0 + rv + k * 8;
    +                   icq++;
    +               }
                    i += 4;
                    continue;
                }
  • [3]putIcX64()関数の宣言の後に以下を追加
    enum { RvSave = 0x89, RvLoad = 0x8b };
    
    void regVarSaveLoad(int op) // レジスタ変数を準備するor書き戻す.
    {
        int i, rv, rex;
        for (i = 0; i < RegVarLen; i++) {
            if (regVarTbl[i] != 0) {
                rv = regVarNo[i];
                rex = 0x48;
                if (rv >= 8) {
                    rex = 0x48 + 4;
                    rv -= 8;
                }
                putIcX64("%0c_%1c_%2c_%3i;", (IntP) (AInt) rex, (IntP) (AInt) op, (IntP) (AInt) (0x85 + rv * 8), (IntP) (AInt) ((regVarTbl[i] - var) * 8));
            }
        }
    }
  • [4]compile()関数に1行追加(1)
        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);
    +   regVarSaveLoad(RvLoad);
        dump0 = icq;
  • [5]compile()関数に14行追加
    +       } else if (phrCmp(37, "regVar(!!*0", pc)) {
    +           i = tc[wpc[0]] - Tc0;
    +           regVarSaveLoad(RvSave);
    +           for (pc = ppc1; tc[pc] != TcBrCls; pc++) {
    +               if (tc[pc] == TcComma) continue;
    +               if (0 <= i && i < RegVarLen) {
    +                   regVarTbl[i] = &var[tc[pc]];
    +                   if (tc[pc] == Tc0)
    +                       regVarTbl[i] = 0;
    +               }
    +               i++;
    +           }
    +           regVarSaveLoad(RvLoad);
    +           ppc1 = pc + 2;
  • [6]compile()関数に1行追加(2)
        defLabel(toExit);
        dump1 = icq;
    +   regVarSaveLoad(RvSave);
        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;

  • 以上すべての改造を終えると、プログラムは964行になります。

(2) プログラムの説明

  • 今回の改造で最も重要なのは、putIcX86_sub()関数の改造のところです。
                if (s[i + 2] == 'm') {	// mod r/m.
                    k = s[i + 3] - '0';
                    if (s[i + 3] >= 'a') { // もしかしたらこの記述は最後まで出番がないかも.
                        k = s[i + 3] - 'a' + 10;
                    }
    +               if (k >= 8) {
    +                   *putIcX64_rex += 4;
    +                   k -= 8;
    +               }
    +               int rv = regVar(a[j]);
    +               if (rv < 0) {
                        *icq = 0x85 + k * 8;
                        put32(icq + 1, (a[j] - var) * 8);
                        icq += 5;
    +               } else {
    +                   rv = regVarNo[rv];
    +                   if (rv >= 8) {
    +                       *putIcX64_rex += 1;
    +                       rv -= 8;
    +                   }
    +                   *icq = 0xc0 + rv + k * 8;
    +                   icq++;
    +               }
                    i += 4;
                    continue;
                }
  • これはつまり、%mで変数を指定されたときにレジスタ変数でなければ従来通りの機械語を生成しますが、レジスタ変数であればmod r/mのmodをメモリ指定モードではなくレジスタ指定モードに切り替えて、r/mのところでレジスタ番号を指定するようにしているのです。
  • またレジスタ番号が8以上になってあふれた時は、REX命令のところに+1して、レジスタ番号が8以上であることをCPUに伝えています。
  • あとはcompile()の最初のところで、レジスタ変数の場合はメモリ上にある変数の値をレジスタに読み込ませます。そしてcompile()の最後のところで、レジスタの内容をメモリに書き戻します。そうすれば次回実行時にもレジスタ変数の値は引き継がれます。
  • またregVar()命令でレジスタ変数の設定状況を変更するときは、まずregVarSaveLoad()でレジスタ変数の値をメモリ書き戻させて、その次に設定を変更し、最後に変更された設定に従ってレジスタ変数を読み込ませています。
  • なおregVar()命令で、変数名の代わりに0を指定すると、その優先度のレジスタ変数の設定は解除されます。つまり regVar(0, 0, 0, 0, 0, 0, 0, 0); とすればレジスタ変数を一切指定していない初期状態に戻るというわけです。

(3) さて、これでどのくらい高速化されるか?

  • 10億回ループを実行する前に、 regVar(0, i); を実行しておきます。
  • また、 run mandel.c する前には、 regVar(0, zx, zy, xx, yy, t, cx, cy); を実行しておきます。
ページ名名前行数.exeの大きさ説明速度のめやす1速度のめやす2
[ a21_txt01 ]HL-1~HL-9a49行~772行6.0KB~20.0KB「10日くらいでできる!プログラミング言語自作入門」1520倍~5.5倍6.4倍
a21_txt02_7HL-17741行25.0KBx64に対応したJITコンパイラ第1号計測不能計測不能
a21_txt02_7aHL-17a756行26.0KB簡単な演算もサポート計測不能計測不能
a21_txt02_8HL-18795行27.0KBループ速度の測定ができるところまで4.2倍計測不能
a21_txt02_8aHL-18a816行27.5KBcodedumpコマンドと、codeコマンドの追加4.2倍計測不能
a21_txt02_9HL-19893行35.5KB配列以外は全部JITコンパイラ対応させる(mandel.cで速さを実感!)4.2倍1.8倍
a21_txt02_9aHL-19a899行36.0KB配列もJITコンパイラ対応させる(ついに機能的にはHL-9a相当に!)4.2倍1.8倍
a21_txt02_10HL-20964行36.0KBレジスタ変数の導入(65行しか増えない簡単な改造だけど、結構な効果がある)2.1倍1.0倍
  • はっきりと効果が出ています!!

次回に続く

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-05-12 (水) 16:13:34 (164d)