a21_hlx001 のバックアップ(No.14)

HLX-001

(by K, 2021.06.20)

↑

(0)

HLXは、a21_txt01やその続編で作ったHLシリーズ（はりぼて言語）をベースに、Kが望む理想の言語を作るプロジェクトです。
- 中・長期の目標はa21_hlx000に書いてあります。
HLX-001はその最初のバージョンです。まあHL-23みたいなものです。

↑

(1) 概要

HLX-001は、HL-9a, HL-16a, HL-22aの3つを統合し、さらに改良を加えたものです。
- ということで「できること」はこれら3つと同じです。
統合されているので、モードを切り替えて使います。
- [codemode 0] HL-9a相当の実行モードで、JITコンパイルせずに中間コードを実行します。x86, x64以外でも（ソースからHLX-001をコンパイルすれば）動くはずです。
- [codemode 1] HL-16a相当の実行モードで、x86の32bitの機械語をJITコンパイラで生成します。
- [codemode 2] HL-22a相当の実行モードで、x64の64bitの機械語をJITコンパイラで生成します（MS-Windows系のABI）。
- [codemode 3] HL-22a相当の実行モードで、x64の64bitの機械語をJITコンパイラで生成します（System V系のABI）。

[Q]そもそもなぜ3つを統合する必要があるの？
- [A]HLシリーズを拡張していくにあたって、それぞれの改造を3つのバージョンに別々に適用していくのは大変なので、まず1つに統合して、それから拡張していきたかったのです。
- さらに統合することで、3つを別々に持つよりもコンパクトにできるのではないかと考えています。
- あと、これ一つであれもこれもできる！っていうのが好きなんです（笑）。

http://k.osask.jp/files/hlx001b.zip (75.2KB)
http://k.osask.jp/files/hlx001c.zip (76.4KB) [最新版]
- [内容](サイズ・行数はhlx001b時点)
- hlx001_32.exe : 32bit版の実行ファイル(21.5KB)
- hlx001_64.exe : 64bit版の実行ファイル(54.0KB)
- mandel.cなどのサンプルプログラム
- hlx001src/
  - hlx001.c (935行) - ソースコードから共通中間コードに変換
  - esvm.c (831行) - 共通中間コードを最適化する
  - esvm_run.c (200行) - 共通中間コードをインタプリタで実行
  - esvm_x864.c (1027行) - 共通中間コードをx86/x64の機械語に変換

↑

(2) 特徴（なにがすごいのか） →「こんなに小さくても、それなりの最適化ができた！」

[1]処理系の小ささ

HL-9a, HL-16a, HL-22aの3つは以下のようになっていました。それらに対し、こんなにコンパクトにまとまっています。

	ソース行数	.exeのサイズ（無圧縮）	.exeのサイズ（UPX適用）
HL-9a	772行	20.0KB	11.5KB
HL-16a	1081行	24.5KB	13.5KB
HL-22a	1223行	41.5KB	21.0KB
(合計)	(3076行)	(86.0KB)	(46.0KB)

HLX-001	2993行	40.0KB	21.5KB

あれ？ソース行数的には、それほどコンパクトでもないな・・・。
まあでも実行ファイル的には明らかにコンパクトになっています。
上記3つは似たような部分が多いため、1つにまとめることで共通な部分が省かれて、このような結果になっています。

[2]生成コードの質の向上
- mandel.cを使って比較してみました。

[2-1] HL-9aとの比較
HL-9a vs HLX-001 32bitモード（x86） 29.667秒 vs 23.220秒 1.28倍速
HL-9a vs HLX-001 64bitモード（x64） 26.904秒 vs 18.653秒 1.44倍速
- 表のように、HLX-001は中間コードの実行性能が上がっています。
- この成果は、主に「中間コードの最適化」（後述）がうまくいっているからです。
[2-2] HL-16aとの比較（32bitモード（x86））
HL-16a vs HLX-001 3.246秒(657バイト) vs 3.272秒(609バイト) 速度優先
HL-16a vs HLX-001 3.730秒(613バイト) vs 3.660秒(411バイト) サイズ優先
- 速度優先: regVar(0, zx, zy, xx, yy, t, cx, cy, n); optmode 0;
- サイズ優先: regVar(0, n, zx, zy, x, y, sx, sy, sn); optmode 1;
- 実行速度的にはHL-16aに対する優位性はないのですが、生成コードの長さは結構改善されています。

[2-3] HL-22aとの比較（64bitモード（x64））
HL-22a vs HLX-001 2.503秒(674バイト) vs 2.512秒(655バイト) 速度優先
HL-22a vs HLX-001 3.449秒(588バイト) vs 3.459秒(489バイト) サイズ優先
- 速度優先: regVar(0, zx, zy, xx, yy, t, cx, cy, n); optmode 0;
- サイズ優先: regVar(0, n, zx, zy, x, y, sx, sy, sn); optmode 1;
- 実行速度的にはHL-22aに対する優位性はないのですが、生成コードの長さは結構改善されています。

↑

(3) プログラムの構成

hlx001.c (935行)
- これはHL-9aから内部コード実行ルーチンを引いたようなものです。
- 内部コード（共通中間コード）を出力した後は、esvm.cやesvm_run.cやesvm_x864.cを使ってプログラムを実行します。
esvm.c (945行)
- 共通中間コードを最適化します。
esvm_run.c (200行)
- 共通中間コードをJITコンパイルせずに実行します。
esvm_x864.c (1027行)
- 共通中間コードからx86/x64の機械語をJITコンパイラで生成します。

この構成は、esvm.c, esvm_run.c, esvm_x864.cを再利用することを想定したものです。
将来また別の言語を作りたくなった時には、hlx001.cに相当する部分だけを作り替えるだけで、今回くらいの最適化が適用できるはずです。
- 935行のプログラムを書くだけで、いろんな方法で実行できる言語が21.5KBでできてしまうっていうのは、私にとっては相当に便利なことなのです。

↑

(4) 先送りされた課題

どれも「ちゃんとするまで仕上げるよりも、ひとまず動くようになった段階でHLX-001としてリリースしてしまおう」と考えたことによるものです。

hlx001.c側で、実行ターゲットに応じたセットアップをしている部分が残っていて、それがよくない（もっときれいに分けられるべき）。
hlx001.cではソースコードの長さが長すぎるとバッファオーバーランしてしまう。これを可変長にするべき。
HL-16bやHL-22bは「codedump 2」でアセンブラのソースが出力できたが、HLX-001にはその機能がない。
浮動小数点演算や構造体のサポートが全くできてない。配列のサポートも貧弱。

↑

(5) どんな最適化をしているか？

（大きな下請け関数が超がんばっている場合もあるので、行数は目安です。）

AEs_optimizeSub0() [24行]
- [5-1] 「比較演算子の結果を0かどうか比較する」というコードが、コンパイラの手抜きの関係で時々出現します。
  - HLX-001では、 if (式) を見つけると何も考えずに式を計算させて、その結果が==0か!=0かで処理するようになっています。
  - こんなやり方では、「比較演算子の結果を0かどうか比較する」というのが頻出します。
- これを一度の比較だけになるように整理する最適化です。
- 類似の処理は、HL-15(HL-21)でもやっていました。今回はこれを機械語レベルではなく中間コードレベルでやっているわけです。

AEs_optimizeSub4() [138行]
- [5-2] 「定数畳み込み」と「定数伝播」をやります。
  - 参考：https://ja.wikipedia.org/wiki/%E5%AE%9A%E6%95%B0%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF
  - 具体的には、変数の値が確定しているものを追跡し、確定しているものについては定数に置き換えます。定数のみの式を演算してしまって単一の定数にすることもします。
  - 条件分岐において、条件が定数式になってしまったら、無条件分岐命令か、もしくはNOPに変換します。
  - 定数引数のみの純関数の呼び出しであれば、コンパイル時に呼び出して定数化します。

AEs_optimizeSub2() [87行]
- [5-3] 分岐命令で分岐した先が無条件分岐命令だったら、最初からそこに行くように分岐先を修正します。
  - これは同等のことをHL-8でもやっています。
- [5-4] 宣言したけど使われていないラベルを除去します。
  - 上記の5-2の最適化は、ラベル宣言命令があると変数の定数の追跡を断念するので、ラベルを減らすのは意外に有効な最適化なのです。
- [5-5] デッドコード（一度も実行されることのないコード）があればそれをすべて消します。
- [5-6] 分岐先が次の命令を指している場合、その分岐命令はNOPと同じなので除去します。

AEs_optimizeSub3() [34行]
- [5-7] 演算した結果がその先で一切利用されないことが確実な場合、その演算をする必要はないので、削除してしまいます。
- この「演算」には代入も含まれます。不要な代入は消します。
- 純関数の戻り値を使わないときは、呼び出しそのものもやめさせます。

[5-8] HLX-001ではfor文の前に unroll(11) みたいなプリフィクスを付けることができるようにしてあります。これを付けると、for文の最初の11回だけをループアンロールします。
このアンロール機能と上記の最適化が合わさると・・・
```
unroll(11)
for (s = i = 0; i <= 10; i++) {
    s = s + i;
}
print s;
```
というプログラムが最適化されて print 55; だけになってしまいます。それくらいに上記の最適化は効果があるのです。21.5KBしかない言語でここまでやれたので、私は楽しいです。

AEs_X864_optimize() [67行]
- [5-9] 機械語レベルでの最適化です。レジスタの値をメモリに書き、直後にそのメモリを読めば、当然ながら先ほどの値が読めます。そういう部分があった場合にメモリアクセスを減らすように不要な命令を除去します。
  - 類似の最適化をHL-15(HL-21)でもやっています。

AEs_X864_optBinSiz() [18行]
- [5-10] 今回最も苦労した最適化です。x86/x64には同じ命令でも命令長が異なるものがあります。たとえばJcc命令のSHORT形式とNEAR形式などです。もしくはmodr/mのdispのバイト数も0,1,4から選択しなければいけません。
- HLシリーズではこれらのことで悩む余裕などなかったので、どれも無条件に一番長い形式を選んでいました。短い形式を選んでオペランドが収まらなかったら、とても困るからです。
- esvm_x864.cでは、最適な命令長を自動で選んでいきます。

↑

こめんと欄

コメント	お名前	NameLink

HL-9a vs HLX-001	32bitモード（x86）	29.667秒 vs 23.220秒	1.28倍速
HL-9a vs HLX-001	64bitモード（x64）	26.904秒 vs 18.653秒	1.44倍速

HL-16a vs HLX-001	3.246秒(657バイト) vs 3.272秒(609バイト)	速度優先
HL-16a vs HLX-001	3.730秒(613バイト) vs 3.660秒(411バイト)	サイズ優先

HL-22a vs HLX-001	2.503秒(674バイト) vs 2.512秒(655バイト)	速度優先
HL-22a vs HLX-001	3.449秒(588バイト) vs 3.459秒(489バイト)	サイズ優先

a21_hlx001 のバックアップ(No.14)

HLX-001

(0)

(1) 概要

(2) 特徴（なにがすごいのか） →「こんなに小さくても、それなりの最適化ができた！」

(3) プログラムの構成

(4) 先送りされた課題

(5) どんな最適化をしているか？

(6) HLX-001の共通中間コード

(7) HLX-001のx864の内部コード

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

(9) その他の雑多な話

(10) HLX-001内の細かい比較（hlx001a～hlx001c）

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

こめんと欄