a25_kharcs4 のバックアップ(No.4)

kharcs #4

(by K, 2025.06.15)

↑

(0) これはなに？

（kharcsページは、kharc開発でわかったことを整理して説明するためのページ群です。）

今回説明したいこと：～この順番でCコンパイラを作ったら早くできたよ！～
- [1]～[6]→a25_kharcs2
- [7]→a25_kharcs3
- [8]最適化1（9日目）
- [9]最適化2（10日目）

↑

(8) 最適化1（9日目：6/14）

「1+a+2+b+3」という式があった時に、これを「a+b+6」にできたらいいなと考えました。
加算だけではなく、乗算や除算や減算が混ざっていてもうまく定数項をまとめたいです。「1+a/2-3*4」→「a/2-11」。
この日はSecHack365のオンラインイベントがあって、21時くらいまで開発はできませんでしたが、しかし若者が頑張っている様子を見ていたら自分も何かしたくなって、夜中に開発しました。
途中でバグに悩まされたりすることもありましたが、最終的にはうまくできました。
ということで、9日目の成果はこれだけです。・・・いや違った！

オンラインイベントの休み時間にちょっと試したことがあります。
これまでkharcの関数呼び出しは、リターン先をRPレジスタに代入してjmpするという方法を取っていました。しかしx86にJITコンパイルする際に、これをx86のCALL(e8)/RET(c3)に翻訳することができないかというと、できなくはないのです。
そして試しにやってみると、fib()のJITコンパイル後の実行速度が8%も短くなりました。おおおー。

↑

(9) 最適化2（10日目：6/16）

今までたくさん生成されて、ややうんざりしていたムダ命令を、きれいに全部消すようにしました。
最適化はkharcのバイナリを使って行いました。命令長が固定長なのでその方が作りやすいです。
しかしこれだけだと、最適化を終えたコードを確認するのが大変なので、逆アセンブラも作りました。31行です。

fib()でどのくらい改善したかを見るとこんな感じです。

LbI(9); // fib()
 SubAI(SP,24);
 StoAMd(RP,SP,20);
 LodRMd(R0,SP,24);
 CgtRI(R0,1);
 StoRMd(R0,SP,8); // 消される.
 LodRMd(R0,SP,8); // 消される.
 FreI(8);
 CmpJeqRII(R0,0,12);
 LodRMd(R0,SP,24);
 AddRI(R0,-2);
 StoRMd(R0,SP,8); // 消される.
 LodRMd(R0,SP,8); // 消される.
 FreI(8);
 StoRMd(R0,SP,0);
 CalII(9,10);
 FraI(8);
 StoRMd(R0,SP,8);
 LodRMd(R0,SP,24);
 AddRI(R0,-1);
 StoRMd(R0,SP,12); // 消される.
 LodRMd(R0,SP,12); // 消される.
 FreI(12);
 StoRMd(R0,SP,0);
 CalII(9,11);
 FraI(8);
 StoRMd(R0,SP,12); // 消される.
 LodRMd(R0,SP,12); // 消される.
 LodRMd(R1,SP,8);
 AddRR(R0,R1);
 FreR(R1);
 StoRMd(R0,SP,16); // 消される.
 FreI(8);
 FreI(12);
 LodRMd(R0,SP,16); // 消される.
 StoRMd(R0,SP,24);
 FreI(16);
LbI(12);
 LodRMd(R0,SP,24);
 JmpI(13);
LbI(13); // fib().ret:
 LodAMd(RP,SP,20);
 AddAI(SP,24);
 Ret();

fib(46)の実行速度の改善はこんな感じです。

mod=16	273.185[sec]	エミュレータ実行：最適化なし・ノーマルモード
mod=17	221.202[sec]	エミュレータ実行：最適化なし・高速モード
mod=18	14.931[sec]	x86JITコンパイラ実行：最適化なし・ノーマルモード
mod=19	13.653[sec]	x86JITコンパイラ実行：最適化なし・e8/c3利用モード
mod=0	241.998[sec]	エミュレータ実行：最適化あり・ノーマルモード
mod=1	165.459[sec]	エミュレータ実行：最適化あり・高速モード
mod=2	9.654[sec]	x86JITコンパイラ実行：最適化あり・ノーマルモード
mod=3	8.321[sec]	x86JITコンパイラ実行：最適化あり・e8/c3利用モード

JITコンパイラで8.3秒まで高速化できたので、とりあえず満足です！

↑

(10) 最適化3（11日目：6/17）

(9)の結果を見ると、 if (i > 1) { ... の部分のコンパイル結果が、
```
 LodRMd(R0,SP,24);
 CgtRI(R0,1);
 CmpJeqRII(R0,0,12);
```
となっているわけですが、CgtRI()命令で比較式を評価して、それでその結果が==0か!=0かで分岐するというのは、全くうまくありません（動作としては正しいけど、遅い）。Cgt+CmpJeq=CmpJleなので、これを利用して1命令減らしたいです。
でもそれをこのままやると、比較式の値を変数に代入して、さらにその値に応じて分岐したい場合にはうまくいかなくなりそうなので、CmpJcc命令の仕様を変更し、第一引数のレジスタを破壊する（かもしれない）という仕様にしました。こうすることで、もし比較式の値が必要なら、CmpJccより前に保存するようになります。そしてCgtとCmpJccの間にNop以外の命令が入っているなら、Cgt+CmpJeq=CmpJleの変換をしないことにします。
これに合わせて命令名も変えました。CmpRIしてFreRしてJccIするので、CmFJccRIIです。

fib(46)の実行速度の改善はこんな感じです。

mod=16	256.992[sec]	エミュレータ実行：最適化なし・ノーマルモード
mod=17	216.348[sec]	エミュレータ実行：最適化なし・高速モード
mod=18	14.958[sec]	x86JITコンパイラ実行：最適化なし・ノーマルモード
mod=19	13.648[sec]	x86JITコンパイラ実行：最適化なし・e8/c3利用モード
mod=0	231.065[sec]	エミュレータ実行：最適化あり・ノーマルモード
mod=1	157.459[sec]	エミュレータ実行：最適化あり・高速モード
mod=2	8.345[sec]	x86JITコンパイラ実行：最適化あり・ノーマルモード
mod=3	8.085[sec]	x86JITコンパイラ実行：最適化あり・e8/c3利用モード