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

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/hlx001a.zip (75.3KB)
- [内容]
- hlx001_32.exe : 32bit版の実行ファイル(21.5KB)
- hlx001_64.exe : 64bit版の実行ファイル(29.0KB)
- mandel.cなどのサンプルプログラム
- hlx001src/
  - hlx001.c (935行) - ソースコードから共通中間コードに変換
  - esvm.c (945行) - 共通中間コードを最適化する
  - 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	3017行	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);
- サイズ優先: regVar(0, n, zx, zy, x, y, sx, sy, sn);
- 実行速度的には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);
- サイズ優先: regVar(0, n, zx, zy, x, y, sx, sy, sn);
- 実行速度的には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] 演算した結果がその先で一切利用されないことが確実な場合、その演算をする必要はないので、NOPに変換します。

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

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

（以下編集中）

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バイト)	サイズ優先