a21_hlx001 のバックアップの現在との差分(No.13)

追加された行はこの色です。
削除された行はこの色です。
* 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コンパイラで生成します。
//---64bit版でもこのモードを利用することができますが、64bit版は32bit用の機械語を実行できないので、 codedump 1 で機械語を表示することしかできません（将来のバージョンではアセンブラも出力できます）。
--[codemode 2] HL-22a相当の実行モードで、x64の64bitの機械語をJITコンパイラで生成します（MS-Windows系のABI）。
//---32bit版でもこのモードを利用することができますが、32bit版は64bit用の機械語を実行できないので、 codedump 1 で機械語を表示することしかできません（将来のバージョンではアセンブラも出力できます）。
--[codemode 3] HL-22a相当の実行モードで、x64の64bitの機械語をJITコンパイラで生成します（System V系のABI）。
//---以下同文。・・・しかし、codemode 3は全くデバッグしてないので、このバージョンではきちんと動かないかもしれません。

-[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) [最新版]
-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|RIGHT:772行|RIGHT:20.0KB|RIGHT:11.5KB|
|HL-16a|RIGHT:1081行|RIGHT:24.5KB|RIGHT:13.5KB|
|HL-22a|RIGHT:1223行|RIGHT:41.5KB|RIGHT:21.0KB|
|(合計)|RIGHT:(3076行)|RIGHT:(86.0KB)|RIGHT:(46.0KB)|
|||||
|HLX-001|RIGHT:2993行|RIGHT:40.0KB|RIGHT:21.5KB|
--あれ？ソース行数的には、それほどコンパクトでもないな・・・。
--まあでも実行ファイル的には明らかにコンパクトになっています。
--上記3つは似たような部分が多いため、1つにまとめることで共通な部分が省かれて、このような結果になっています。

~

-[2]生成コードの質の向上
-[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では、最適な命令長を自動で選んでいきます。

** (6) HLX-001の共通中間コード
-→[[a21_hlx001_1]]
** (7) HLX-001のx864の内部コード
-→[[a21_hlx001_1]]
** (8) HLX-001の最適化アルゴリズム
-→[[a21_hlx001_2]]
** (9) その他の雑多な話
-→[[a21_hlx001_3]]
** (10) HLX-001内の細かい比較（hlx001a～hlx001c）
-→[[a21_hlx001_3]]
** (11) FizzBuzzプログラムの最適化について
-→[[a21_hlx001_3]]


* こめんと欄
#comment