a21_hlx001_2

HLX-001 の補足ページ#2

• (by K, 2021.08.23)

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

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

• [5-1] 「比較演算子の結果を0かどうか比較する」という処理を一度の比較にまとめます。
  • AEs_optimizeSub0() [24行] のアルゴリズム：

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

  • [例1]

    if ((a > 1) != 0) goto label; // HLX-001が内部的に生成する共通中間コードをC言語風に書いたもの
    
    1: CmpGt(a, 1);   // （最適前）上記を共通中間コードで表したもの
    2: SetCc(tmp);    // この2行目と3行目は最適化によって消される
    3: CmpNe(tmp, 0);
    4: Jcc(label);
    
    1: CmpGt(a, 1);   // （最適化後）このようにうまくいく
    2: Jcc(label);

• [Q] 「SetCcの結果をその先で一切使わない」ってどうやって判定していますか？
  • [A] プログラムでは AEs_isVoid() で判定しています。
  • やっていることは単純で、先の命令を一つずつ順番に見ていって、もしその変数が何らかの命令の引数に使われていれば、それは「使われている」と判断してそこでおしまいです。
  • もしその変数に対して何らかの値が上書きされるか、OpVoid命令で無効化されたら、それは「使われていない」と判断しておしまいです。
  • JmpやJccに出会ってしまったら、その先でどうなるかは分からないので、「使われている」ということにしておしまいです。・・・いやJmpであればさらに追跡も可能そうではありますが、それで最適化ルーチンが無限ループに入ったらいやだなとか、それを回避するためにどの命令がチェック済みかを管理するのも手間だなと思って、やっていません。
  • 私としては、そこを頑張らせるよりは、「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の命令がJmpかJcc) {
            分岐先の命令を見る（NOPなどは読み飛ばす）
            もしJmpだったら、分岐先を修正
        }
    }

• [5-4] 宣言したけど使われていないラベルを除去します。
• [5-5] デッドコード（一度も実行されることのないコード）があればそれをすべて消します。
  • AEs_optimizeSub2() [87行] のアルゴリズム：

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

  • 宣言したけど使ってないラベルを消すのは結構有効です。上記の[5-2]や以下の[5-7]ではラベル宣言文があるとそこで最適化が止まってしまうからです。

• [5-6] 分岐先が次の命令を指している場合、その分岐命令はNOPと同じなので除去します。
  • AEs_optimizeSub2() [87行] のアルゴリズム：

    最適化範囲： p0 ～ p1
    for (p = p0; p < p1; p = 次の命令) {
        if (pの命令がJmpかJcc) {
            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の演算結果が次のCpyでしか使われていない) {
            Cpyの代入先へ直接代入するようにする
            そしてCpyは消す
            [註] ここは以下のようなコードを最適化する
            tmp = a + b; c = tmp; → c = a + b;
        }
        if (pの演算結果がその先で使われていない) {
            pの命令を消す
        }
    }

  • [Q] Cpy命令って何ですか？
    • [A] ただの代入命令です。 a = b; とかそういうやつです。 Cpy(a, b); になります。
  • [Q] 「使われていない」ってどうやって判定していますか？
    • [A] プログラムでは AEs_isVoid() で判定しています。これは上記の[5-1]で紹介したものと同じです。
  • [Q] なぜ最初に命令の頭出しまでして逆順に処理しようとするのですか？アルゴリズムを見ていると逆順にしなくても最適化できそうですが。
    • [A] 逆順にしなくても最適化ができるのはその通りです。
    • しかし、 b = a + 1; c = b + 2; d = c + 3; （そしてb, c, dはこの先で使われていない）、みたいな感じで命令が並んでいるとき、このアルゴリズムがまず最初に最適化で消せるのは「d = c + 3;」です。cやbは消せません。直後で使われているからです。そして「d = c + 3;」が消えると、次は「c = b + 2;」が消せると気づきます。こうして後ろから消えていくことになるので、AEs_optimizeSub3()を何度も呼び出しなおさなくても済むように、逆順で最適化の処理をしたかったのです。

• [5-8] HLX-001ではfor文の前に unroll(11) みたいなプリフィクスを付けるとループアンロールができます。
  • HLX-001におけるfor文のアンロールのやり方は次の通りです。
  • アンロール回数だけひたすらに展開し、最後にfor文を付けておく。
  • [例1]

    unroll(11) 
    for (s = i = 0; i <= 10; i++) {
        s = s + i;
    }
    print s;
    
    // アンロール結果：
    s = i = 0; if (i > 10) goto brk;
    s = s + i; i++; if (i > 10) goto brk;
    s = s + i; i++; if (i > 10) goto brk;
    s = s + i; i++; if (i > 10) goto brk;
    s = s + i; i++; if (i > 10) goto brk;
    s = s + i; i++; if (i > 10) goto brk;
    s = s + i; i++; if (i > 10) goto brk;
    s = s + i; i++; if (i > 10) goto brk;
    s = s + i; i++; if (i > 10) goto brk;
    s = s + i; i++; if (i > 10) goto brk;
    s = s + i; i++; if (i > 10) goto brk;
    s = s + i; i++; if (i > 10) goto brk;
    lop:
    s = s + 1; i++;
    if (i <= 10) goto lop;
    brk:
    print s;
    
    このあと、最適化によって、定数畳み込みや定数伝播がおきて、if文が消えたりただのgotoになったりして、使わないラベルや直後への分岐も消えて、
    
    print 55;
    
    だけになります。

こめんと欄