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

kharcs #4

(by K, 2025.06.15)

↑

(0) これはなに？

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

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

↑

(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、buntan-pcに挑戦（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利用モード

buntan-pc用のアセンブラ出力に挑戦しました。

以下のfib()をコンパイルして、標準のuccの出力と比較します。

int fib(int i)
{
    if (i > 1) {
        i = fib(i - 2) + fib(i - 1);
    }
    return i;
}

出力結果比較。左：kharcのCコンパイラ。右：buntan-pcの標準Cコンパイラucc。

L_0:             fib:
 add  fp,-10      add fp,-2
                  st fp+0
 ld   fp+10       push 1
 push 1           ld fp+0
 le               lt
 not
 jz   L_3         jz L_1
 ld   fp+10       ld fp+0       
 push 2           push 2
 sub              sub
 st   fp+0
 call L_0         call fib
 st   fp+2
 ld   fp+10       ld fp+0
 push 1           push 1
 sub              sub
 st   fp+0
 call L_0         call fib
 ld   fp+2
 add              add
 st   fp+10       st fp+0
L_3:             L_1:
 ld   fp+10       ld fp+0
 add  fp,10       add fp,2
 ret              ret

考察。
- (1)まずuccのほうが命令が少ないです。つまり速いです。ただし、これがいいかどうかは一概には言えません。
- kharcでは、関数の引数をすべてメモリに書き込んで渡します。したがってレジスタスタックを使い切ってしまう心配がありません。そのかわりメモリに書き込む分だけ命令数は増えます。
- また関数から戻ってきたときにkharcでは結果をローカル変数に保存しています。uccはレジスタスタックに積んだままにして、最後のaddでうまく計算しています。
- uccのやり方はレジスタスタックに十分な余裕があれば大変有効な方法ですが、そうでないならあふれる心配があります。
- ちなみにkharcでは、レジスタスタックは常に2段までしか使わないようにしています（どのくらい余裕があるのかわからなかったので）。
- (2)一方で、kharcがうまくいっていないところは、ローカル変数域として10バイトを要求しているところです。
- 次の呼び出しのための2バイト、fib(i-2)の結果をしまっておくための2バイトは必須ですが、それなら合計4バイトであるべきです。
- じゃあ残りの6バイトは何なのかというと、2バイトがリターンアドレスをしまうための領域で、4バイトは一時変数のために確保したものの、結局最適化で使わなくなってしまったものです。
- (3)ちなみにkharcでは https://github.com/buntan-pc/buntan-pc/blob/main/cpu/cpu.sv#L50 に書いてある「binop uimm10」に期待していて、これが使えるならpush命令を減らせます。
- 使い方がわかればすぐに対応できるようにしてあります。
- (4)レジスタマシンを想定したコンパイラがここまでスタックマシンに寄り添ったコード生成ができているということで、なかなか頑張ったと言えると自分では思っているのですが・・・。

ここまでの結果を踏まえて考えました。
今のkccは内部でいきなりテキスト状態のアセンブラを出力しているのですが、このために文字列処理が必要になって、小回りが利きません。バイナリからテキストに変換するのはすごく簡単になっているので、バイナリで生成すべきです。
また最適化するタイミングもよくないです。スタックフレームのサイズを決めてから最適化したら、こうやって無駄が出てしまいます。スタックフレームのサイズを決める前に最適化する必要があります。
ということで、そろそろリファクタリングですかね・・・。

↑

(11)

12日目（6/18）はリファクタリングで、主に内部機械語の仕様を変更しました。
- 変更前： struct KhaBinInst { unsigned char op, prm[3]; int imm; }; // 8バイト.
- 変更後： struct KhaBinInst { int op; unsigned char prm[4]; int imm[2]; }; // 16バイト.
こうすることで、Aux命令は不要になります（最適化の時にAux命令は不便だなと思ったのです）。
命令番号も8bitに収めるために工夫するよりは余裕を持たせて楽をしようと考えました。

13日目（6/19）もリファクタリングです。今回のリファクタリング、ちょっといつもと違った方法でやっています。
コンパイラはアセンブラを生成せず、いきなり機械語を生成するように書き換えています。しかし一気に全部書き換えが終わるまでテストランできないという状況になるのがなんだか嫌だなと思って、機械語を生成した場合はそれを逆アセンブルしてテキストに変換し、テキストで生成した場合はそのまま追記して、結局従来通りの出力をするという仕組みを作りました。こうすることで、段階的に移行できます。バグが大きくなる前に直せます。
それで全部移行できたら、今度はテキストで保持する方法をやめることにして、機械語のまま処理するようにします。・・・とりあえずインラインアセンブラ以外の部分は全部移行できました。