a21_hlx001_2 のバックアップ(No.4)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
a21_hlx001_2 へ行く。
- 1 (2021-08-23 (月) 15:51:16)
- 2 (2021-08-23 (月) 17:04:42)
- 3 (2021-08-23 (月) 23:44:56)
- 4 (2021-08-24 (火) 16:01:47)
- 5 (2021-08-24 (火) 16:28:11)
- 6 (2021-08-25 (水) 00:56:10)

HLX-001 の補足ページ#2

(by K, 2021.08.23)

(8) HLX-001の最適化アルゴリズム

HLX-001は、いろいろな最適化を比較的コンパクトに実現できていると思うのですが、そのアルゴリズムの詳細や、なぜそういう仕様にしたのかの説明を書いておけば、誰かの参考になるかもしれないと思ったので書いておきます。

[5-1] 「比較演算子の結果を0かどうか比較する」という処理を一度の比較にまとめます。

AEs_optimizeSub0() [24行] のアルゴリズム：

最適化の範囲： p0 ～ p1
for (p = p0; p < p1; p = 次の命令) {
    if (pの命令がAEs_OpCmpEq～AEs_OpCmpRnz) { r = p; （この命令の場所を覚えておく） }
    if (pの命令がAEs_OpSetCc && 次の命令がAEs_OpCmpEqかAEs_OpCmpNeで定数0との比較 && OpSetCcの結果をその先で一切使わない) {
        if (次の命令がAEs_OpCmpEq) { rに書いてある命令の比較条件を反転させる }
        pのSetCc命令をNopにしてしまう
        pの次のAEs_OpCmpEq/AEs_OpCmpNe命令もNopにしてしまう
    }
}

[例1]

if ((a > 1) != 0) goto label; // HLX-001が内部的に生成してしまう共通中間コードをC言語風に書いたもの

1: OpCmpGt(a, 1);   // （最適前）上記を共通中間コードにしたもの
2: OpSetCc(tmp);    // この2行目と3行目は最適化によって消される
3: OpCmpNe(tmp, 0);
4: Op0Jcc(label);

1: OpCmpGt(a, 1);   // （最適化後）このようにうまくいく
2: Op0Jcc(label);

[Q] 「OpSetCcの結果をその先で一切使わない」ってどうやって判定していますか？
- [A] プログラムでは AEs_isVoid() で判定しています。
- やっていることは単純で、その先の命令を一つずつ順番に見ていって、もしその変数が何らかの命令の引数に使われていれば、それは「使われている」と判断してそこでおしまいです。
- もしその変数に対して何らかの値が上書きされるか、OpVoid命令で無効化されたら、それは「使われていない」と判断しておしまいです。
- Op0JmpやOp0Jccに出会ってしまったら、その先でどうなるかは分からないので、「使われている」ということにしておしまいです。・・・いやOp0Jmpであればさらに追跡も可能そうではありますが、それで最適化ルーチンが無限ループに入ったらいやだなとか、それを回避するためにどの命令がチェック済みかを管理するのも手間だなと思って、やっていません。
- 私としては、そこを頑張らせるよりは、「a = void;」みたいな命令をHLX-001にサポートさせて、プログラム内で「この変数はこの先で値を使わないよ」って明示できるようにしたいです。そうすればコンパイラが追跡を頑張らなくても、同等の最適化結果が得られるようになるので。

[5-2] 「定数畳み込み」と「定数伝播」をやります。

AEs_optimizeSub4() [138行] のアルゴリズム：

最適化の範囲： p0 ～ p1
変数の値を記憶するテーブルを初期化
for (p = p0; p < p1; p = 次の命令) {
    定数代入命令があったら、テーブルに変数の値を登録
    その他、結果が定数になるような演算があれば、それも結果をテーブルに登録
    もし定数のみの演算ではなく結果が定数じゃないかもしれないと思われるときは、テーブルから変数に関する行を削除
    命令の中で変数が使われていたら、その変数がテーブルに登録されていないかを確認し、登録されていれば定数値に置換する。
    ラベル宣言文に当たったら、テーブルをいったん全クリアする（もうどの変数に定数値がはいっているか分からないので）
}

[Q] この処理のどこが行数を食っていますか？（全体で138行もあるので）
- [A] 加算で0を足している部分があれば、それは単純代入にできるので置換する、「b = a - a;」のように減算で同じものの引き算になっていたら、答えは定数のゼロに決まっているのでそのようにするなど、そういうパターンの網羅にかなりの行数が費やされています。

[5-3] 分岐命令で分岐した先が無条件分岐命令だったら、最初からそこに行くように分岐先を修正します。

AEs_optimizeSub2() [87行] のアルゴリズム：

最適化の範囲： p0 ～ p1
for (p = p0; p < p1; p = 次の命令) {
    if (pの命令がOp0JmpかOp0Jcc) {
        分岐先の命令を見る（NOPなどは読み飛ばす）
        もしOp0Jmpだったら、分岐先を修正
    }
}

[5-4] 宣言したけど使われていないラベルを除去します。

AEs_optimizeSub2() [87行] のアルゴリズム：

最適化範囲： p0 ～ p1
範囲内のプログラムの、Op0JmpやOp0Jcc命令を探してラベルの参照回数をカウントする
そして参照回数が0回のラベル宣言文は削除してしまう

[5-5] デッドコード（一度も実行されることのないコード）があればそれをすべて消します。

AEs_optimizeSub2() [87行] のアルゴリズム：

最適化範囲： p0 ～ p1
関数の先頭から見て行って、Op0Jccを見つけたら、スタックにそのラベルを登録。Op0RetやOp0Jmpを見つけたら、そこで終わり。
終わったら、スタックを見に行って、もしラベルが登録されていればそこからまた見て行ってOp0Jccが来たらスタックに登録。・・・これを繰り返す。
同じラベルを二度見に行かないようにフラグで管理。
こうすることで、どうやっても到達しないラベルにはフラグが付いていないことになるので、フラグのないラベルは消す。
その上で、Op0Jmpの後でラベル宣言命令までの間は、どうやっても到達しないコードになるので、これを削る。

[5-6] 分岐先が次の命令を指している場合、その分岐命令はNOPと同じなので除去します。

AEs_optimizeSub2() [87行] のアルゴリズム：

最適化範囲： p0 ～ p1
for (p = p0; p < p1; p = 次の命令) {
    if (pの命令がOp0JmpかOp0Jcc) {
        if (pの次の命令がラベル宣言 && そのラベルはpの分岐先と同じ) {
            pの分岐命令を消す
        }
    }
}

[5-7] 演算した結果がその先で一切利用されないことが確実な場合、その演算をする必要はないので、削除してしまいます。

AEs_optimizeSub3() [34行] のアルゴリズム：

最適化範囲： p0 ～ p1
for (p = p0; p < p1; p = 次の命令) {
    命令の開始位置を配列t[i]に記憶させる（以下で、命令を逆順にたどりたいので）
}
for (i--; i >= 0; i--) {
    p = t[i];
    if (pの演算結果が次のOpCpyでしか使われていない) {
        OpCpyの代入先へ直接代入するようにする
        そしてOpCpyは消す
        [註] ここは以下のようなコードを最適化する
        tmp = a + b; c = tmp; → c = a + b;
    }
    if (pの演算結果がその先で使われていない) {
        pの命令を消す
    }
}

[Q] 「使われていない」ってどうやって判定していますか？
- [A] プログラムでは AEs_isVoid() で判定しています。これは上記の[5-1]で紹介したものと同じです。