a21_hlx001_3 のバックアップ(No.5)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
a21_hlx001_3 へ行く。
- 1 (2021-08-26 (木) 00:14:39)
- 2 (2021-08-26 (木) 01:15:56)
- 3 (2021-08-26 (木) 09:11:38)
- 4 (2021-08-27 (金) 01:00:04)
- 5 (2021-08-27 (金) 09:57:07)

HLX-001 の補足ページ#3

(by K, 2021.08.26)

↑

(9) その他の雑多な話

[Q] 共通中間コードについて質問です。基本的にHL-9aの内部コードとよく似ているということはよくわかりますが、大きな違いとして、(1)OpJeq～OpJgtの分岐命令が、OpCmpEq～OpCmpGt + OpJcc の2命令に分割されたこと、(2)OpVoid命令が追加されたこと、が、あると思います。このような変更をした理由を教えてください。

（編集中）

↑

(10) HLX-001内の細かい比較

hlx001a :
- 最初のバージョン。
hlx001b :
- hlx001aではビルドに失敗していたので、hlx001_64.exeを差し替えた。
hlx001c :
- hlx001bはunrollにバグがあったので修正。else ifが使えるように改造。最適化を少し改良。

↑

(11) FizzBuzzプログラムの最適化について

以下のような簡単なFizzBuzzプログラムを作りました。hlx001cからサポートされた、 else if 構文を使っています。

unroll(31)
for (i = 1; i <= 30; i++) {
    if (i % 15 == 0) {
        prints "FizzBuzz";
    } else if (i % 3 == 0) {
        prints "Fizz";
    } else if (i % 5 == 0) {
        prints "Buzz";
    } else {
        print i;
    }
}

これをcodemode=1, optmode=0（つまり、x86の速度優先モード）でコンパイルするとこうなりました（codedump 1にしてからrunすれば見えます）。

いうまでもないですが、codemode=2や3にしてx64の機械語を生成させるようにしても、機械語が変わるだけで同等の結果が得られます。

57 56 55 53 81 ec 8c 00 00 00 // スタックフレームの構築
b8 01 00 00 00 89 04 24 e8 2a 4c 24 fe // print 1;
b8 02 00 00 00 89 04 24 e8 1d 4c 24 fe // print 2;
b8 18 0d 3b 02 89 04 24 e8 02 4e 24 fe // prints "Fizz";
b8 04 00 00 00 89 04 24 e8 03 4c 24 fe // print 4;
b8 f0 0d 3b 02 89 04 24 e8 e8 4d 24 fe // prints "Buzz";
b8 18 0d 3b 02 89 04 24 e8 db 4d 24 fe // prints "Fizz";
b8 07 00 00 00 89 04 24 e8 dc 4b 24 fe // print 7;
b8 08 00 00 00 89 04 24 e8 cf 4b 24 fe // print 8;
...

つまり、もはやなにも計算せずにただprintしていくだけのプログラムになってしまったわけです。これはもちろん最適化の成果です。
これはなかなか「かっこいい成果」だと私などは思うわけですが、なぜこれが達成できたのか簡単に説明したいと思います。

まずはunroll()命令です。これは直後のfor文を指定回数だけアンロールする命令です。アンロールした結果は次のようになります。

i = 1; if (i > 30) goto brk;
if (i % 15 == 0) { prints "FizzBuzz"; } else if (i % 3 == 0) { prints "Fizz"; } else if (i % 5 == 0) { prints "Buzz"; } else { print i; } i++; if (i > 30) goto brk;
if (i % 15 == 0) { prints "FizzBuzz"; } else if (i % 3 == 0) { prints "Fizz"; } else if (i % 5 == 0) { prints "Buzz"; } else { print i; } i++; if (i > 30) goto brk;
if (i % 15 == 0) { prints "FizzBuzz"; } else if (i % 3 == 0) { prints "Fizz"; } else if (i % 5 == 0) { prints "Buzz"; } else { print i; } i++; if (i > 30) goto brk;
・・・中略・・・
if (i % 15 == 0) { prints "FizzBuzz"; } else if (i % 3 == 0) { prints "Fizz"; } else if (i % 5 == 0) { prints "Buzz"; } else { print i; } i++; if (i > 30) goto brk;
if (i % 15 == 0) { prints "FizzBuzz"; } else if (i % 3 == 0) { prints "Fizz"; } else if (i % 5 == 0) { prints "Buzz"; } else { print i; } i++; if (i > 30) goto brk;
if (i % 15 == 0) { prints "FizzBuzz"; } else if (i % 3 == 0) { prints "Fizz"; } else if (i % 5 == 0) { prints "Buzz"; } else { print i; } i++; if (i > 30) goto brk;
lop:
    if (i % 15 == 0) { prints "FizzBuzz"; } else if (i % 3 == 0) { prints "Fizz"; } else if (i % 5 == 0) { prints "Buzz"; } else { print i; }
    i++; if (i <= 30) goto lop;
brk:

アンロールが終わると、次は[5-2]の「定数畳み込み」と「定数伝播」を適用します。
それで、最初のif文は必ず成立しないことがわかるので消されます（1>30ではない）。次のif文も成立しないことがわかります（1%15は0ではない）。こういうことを繰り返していくと残るのはprint 1;だとわかります。
- この消していく過程では、以下が活躍します。
- [5-4] 宣言したけど使われていないラベルを除去します。
- [5-5] デッドコード（一度も実行されることのないコード）があればそれをすべて消します。
- [5-6] 分岐先が次の命令を指している場合、その分岐命令はNOPと同じなので除去します。
- [5-7] 演算した結果がその先で一切利用されないことが確実な場合、その演算をする必要はないので、削除してしまいます
- （これらの詳細説明はこちら→a21_hlx001_2）
そして次のi++はi=2に変換されて、その先のif文もどんどん消されて、結果的に先に示した通り、printとprints命令だけが残るというわけです。

↑

こめんと欄

コメント	お名前	NameLink