a21_hlx001_3

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命令だけが残るというわけです。

こめんと欄