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

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-08-27 (金) 09:57:07 (58d)