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

[ トップ ]   [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• a25_kharcs4 へ行く。
  • 1 (2025-06-15 (日) 20:58:58)
  • 2 (2025-06-15 (日) 21:19:49)
  • 3 (2025-06-16 (月) 17:22:38)
  • 4 (2025-06-17 (火) 10:01:19)
  • 5 (2025-06-17 (火) 10:01:19)
  • 6 (2025-06-17 (火) 23:21:01)
  • 7 (2025-06-19 (木) 09:35:36)
  • 8 (2025-06-20 (金) 11:17:33)
  • 9 (2025-06-21 (土) 09:30:32)
  • 10 (2025-06-21 (土) 09:30:32)
  • 11 (2025-06-23 (月) 10:35:40)
  • 12 (2025-06-23 (月) 14:43:48)
  • 13 (2025-06-24 (火) 01:21:19)
  • 14 (2025-06-24 (火) 22:39:28)
  • 15 (2025-06-24 (火) 22:39:28)
  • 16 (2025-06-25 (水) 22:49:53)

---

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日目）
  • [11]リファクタリング（12～14日目）

(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コンパイラkcc。右：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～14日目）

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

---

• 14日目（6/20）もリファクタリングです。
• インラインアセンブラをどうするか悩みましたが、結局インラインアセンブラを使わなくてもプログラムを書けるように改良して、インラインアセンブラの実現方法は後日考えることにしました。
• インラインアセンブラで本当にアセンブラだけ書いてあるなら解決はできるのですが、kccではインラインアセンブラでC言語を書いたりすることもあるので、その対応に苦慮していたんです。
• 残りの部分も組み立てて「コンパイラはバイナリを出力して、それを一度もテキストに変換することなく、バイナリのまま最適化してバイナリのまま実行するという仕組み」ができました。たぶんコンパイル速度も上がっています。
• ソースコードを出力する必要がある時は、逆アセンブルして出力します。

(12)

• [最適化4] 最適化によって一度もアクセスしなくなった一時変数をスタック上からも削除する。
  • ついにこれができるようになりました。だからbuntan-pc向けの出力もよくなりました！

    L_1:
     add  fp,-4
     ld   fp+4
     push 1
     le
     not
     jz   L_4
     ld   fp+4
     push -2
     add
     st   fp+0
     call L_1
     st   fp+2
     ld   fp+4
     push -1
     add
     st   fp+0
     call L_1
     ld   fp+2
     add
     st   fp+4
    L_4:
     ld   fp+4
     add  fp,4
     ret

  • これで意図通りです！

---

• ベンチマークをしました。
  • (1)fib46を普通のC言語で書いて、gcc -O3でビルドした場合。
  • (2)fib46をkccで書いて、kccのvmd=4でhkarcのアセンブラを出力させ、これをgcc -O3でビルドした場合。
  • (3)fib46をkccで書いて、kccのmod=3でJITコンパイル実行した場合。
  • 同様のことをmandelでも行いました。
  • ちなみにどれも32bit版でやっています。

    	fib46	mandel
    (1)	4.608[sec](1.00倍)	1.874[sec](1.00倍)
    (2)	7.279[sec](1.57倍)	3.373[sec](1.80倍)
    (3)	8.179[sec](1.77倍)	2.919[sec](1.56倍)

• これをみると、kcc用でプログラムを書いた場合、最初からgcc用に書いた場合と比べて1.5倍くらいの速度差があるとわかりました。
• つまりもし仮にkccにgccを超えるような便利機能を入れたとして、kccを普段使いのコンパイラにすると、実行速度では1.5倍くらい遅くなるというわけです。
• これを気にならない差だと思うなら、kccの中で暮らせるということになります。
• うーん、もうちょっと速くなって、1.2倍くらいで収まってくれればなあ・・・。

     

Site admin: K

PukiWiki 1.4.7 Copyright © 2001-2006 PukiWiki Developers Team. License is GPL.
Based on "PukiWiki" 1.3 by yu-ji. Powered by PHP 5.6.40. HTML convert time: 0.023 sec.