a25_kharcs2 のバックアップ(No.11)

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

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• a25_kharcs2 へ行く。
  • 1 (2025-06-09 (月) 08:10:53)
  • 2 (2025-06-09 (月) 10:02:13)
  • 3 (2025-06-09 (月) 13:39:46)
  • 4 (2025-06-09 (月) 16:08:49)
  • 5 (2025-06-09 (月) 16:08:49)
  • 6 (2025-06-10 (火) 18:09:52)
  • 7 (2025-06-10 (火) 18:09:52)
  • 8 (2025-06-11 (水) 12:00:16)
  • 9 (2025-06-12 (木) 16:15:05)
  • 10 (2025-06-12 (木) 16:15:05)
  • 11 (2025-06-12 (木) 16:15:05)

---

kharcs #2

• (by K, 2025.06.09)

(0) これはなに？

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

• 今回説明したいこと： ～この順番でCコンパイラを作ったら早くできたよ！～
  • [1]関数定義、インラインアセンブラ（2日目）
  • [2]変数宣言、インラインアセンブラ内でのラベル宣言（3日目）
  • [3]四則演算、return、関数呼び出し（4日目）
  • [4]普通のラベル宣言、条件分岐（5日目）
  • [5]for構文、while構文、do～while構文（6日目）
  • [6]ブロックif構文、アセンブラ、エミュレータ、JITコンパイラ（7日目）

(1) 関数定義、インラインアセンブラ（2日目：6/5）

• とりあえず、以下の記述くらいならできるようになりました。

  int func(int i)
  {
      asm { LodRMd(R0,SP,$i); AddRI(R0,3); } // R0=i+3;
  }

• 受け取った引数に3を足すだけのヘボ関数です。コンパイルすると以下のようになります。

  LbI(1); // func()
   SubAI(SP,8);
   StoAMd(RP,SP,0); // RP値を保存している（とりあえず今は無条件でやっている）.
   LodRMd(R0,SP,8); AddRI(R0,3); // （ここはasmの中身）$iが8に置換されている.
   LodAMd(RP,SP,0); // RP値を復元している.
   AddAI(SP,8);
   Ret();

• 引数に名前を付けて参照できるので、どこに何があるのかを人間が管理しなくてもよくなりました（前に作っていたアセンブラではすべて番号でしか管理できませんでしたので、大きな進歩です）。

(2) 変数宣言、インラインアセンブラ内でのラベル宣言（3日目：6/6）

• ローカル変数の宣言を可能にして、スタック内がどうなっているか、コンパイラに管理してもらえるようにしました。

  void main()
  {
      params(1); // このmain内で行われる関数呼び出しは、引数が最大で1つだという意味（もしインラインアセンブラ内で関数呼び出ししないなら、この記述はいらない）.
      asm {
          MovRI(R0,46); StoRMd(R0,SP,0); CalII($fib,@lb0:); // R0 = fib(46);
          return R0;
      }
  }
  
  int fib(int i)
  {
      int tmp;
      params(1);
      asm {
          LodRMd(R0,SP,$i); CmpJleRII(R0,1,@skip); // if (i <= 1) goto skip;
                            SubRI(R0,2); StoRMd(R0,SP,0); CalII($fib,@lb0:); StoRMd(R0,SP,$tmp); // tmp = fib(i-2);
          LodRMd(R0,SP,$i); SubRI(R0,1); StoRMd(R0,SP,0); CalII($fib,@lb1:); // R0 = fib(i-1);
          LodRMd(R1,SP,$tmp); AddRR(R0,R1); // R0 += tmp;
          LbI(@skip:);
      }
  }

• このfib()部分のコンパイル結果はこうなります。

  LbI(4); // fib()
   SubAI(SP,16);
   StoAMd(RP,SP,12);
   LodRMd(R0,SP,16); CmpJleRII(R0,1,7); // if (i <= 1) goto skip;
                     SubRI(R0,2); StoRMd(R0,SP,0); CalII(4,5); StoRMd(R0,SP,8); // tmp = fib(i-2);
   LodRMd(R0,SP,16); SubRI(R0,1); StoRMd(R0,SP,0); CalII(4,6); // R0 = fib(i-1);
   LodRMd(R1,SP,8); AddRR(R0,R1); // R0 += tmp;
  LbI(7); // skip:
   LodAMd(RP,SP,12);
   AddAI(SP,16);
   Ret();

• 変数オフセットやラベルなどがすべて無事に数値化できています。
• スタックはこんな感じになっています。

  { [SP+0:引数用の領域8バイト] [SP+8:変数tmp] [SP+12:RP保存領域] } [SP+16:引数i]

(3) 四則演算、return、関数呼び出し（4日目：6/9）

• 式の評価をできるようにしました。四則演算と、代入と、関数呼び出しと、returnができます。

  void main()
  {
      fib(46); asm { return R0; }
  }
  
  int fib(int i)
  {
      asm { LodRMd(R0,SP,$i); CmpJleRII(R0,1,@skip); }
  
      i = fib(i - 2) + fib(i - 1); // ← ここがかっこいい！
  
      asm { LbI(@skip:); }
      return i;
  }

• インラインアセンブラじゃないところは、すごくC言語っぽいです！かっこいい！！
• 上記をコンパイルするとこうなります。fib()の部分を見てみましょう。

  LbI(4); // fib()
   SubAI(SP,24);
   StoAMd(RP,SP,20);
   LodRMd(R0,SP,24); CmpJleRII(R0,1,7); // （ここはasmの中身）
   LodRMd(R0,SP,24); // ムダ
   SubRI(R0,2);
   StoRMd(R0,SP,8); // ムダ
   LodRMd(R0,SP,8); // ムダ
   FreI(8);
   StoRMd(R0,SP,0);
   CalII(4,5);
   StoRMd(R0,SP,8);
   LodRMd(R0,SP,24);
   SubRI(R0,1);
   StoRMd(R0,SP,12); // ムダ
   LodRMd(R0,SP,12); // ムダ
   FreI(12);
   StoRMd(R0,SP,0);
   CalII(4,6);
   StoRMd(R0,SP,12);
   LodRMd(R0,SP,8);
   LodRMd(R1,SP,12);
   AddRR(R0,R1);
   StoRMd(R0,SP,16);
   FreI(8);
   FreI(12);
   LodRMd(R0,SP,16);
   StoRMd(R0,SP,24);
   FreI(16);
  LbI(7);  LodRMd(R0,SP,24); // （ここはasmの中身）
   JmpI(8); // ムダ
  LbI(8); // fib().ret:
   LodAMd(RP,SP,20);
   AddAI(SP,24);
   Ret();
  
  // { [SP+0:引数用の領域8バイト] [SP+8:内部生成した一時変数tmp0] [SP+12:tmp1] [SP+16:tmp2] [SP+20:RP保存領域] } [SP+24:引数i]

• FreI()命令は、何もしないコメント命令ですので、ひとまず無視してください（内部生成した一時変数の解放タイミングを示しています）。
• 明らかなムダ命令が6命令も入っていますが、それを除けば、なかなか頑張っている感じはします。
• ムダ命令は将来的に簡単なオプティマイザ（最適化処理）を入れてうまく消すことします。FreI()命令を入れているのは、将来オプティマイザを作りやすくするための工夫です。

---

• 最適化と言えば、定数式のコンパイル時の評価とかもやっています。

  int func()
  {
      int i, j, k;
      i = j = k = 1 + 2 * 3;
      i = (j = 4) + 5;
  }

• これをコンパイルするとこうなります。

  LbI(1); // func()
   SubAI(SP,16);
   StoAMd(RP,SP,12);
   MovRI(R0,7); // 1+2*3 をコンパイル時に計算して 7 にしている.
   StoRMd(R0,SP,8); // k
   MovRI(R0,7);
   StoRMd(R0,SP,4); // j
   MovRI(R0,7);
   StoRMd(R0,SP,0); // i
   MovRI(R0,4);
   StoRMd(R0,SP,4); // j
   MovRI(R0,9); // 4+5 をコンパイル時に計算して 9 にしている.
   StoRMd(R0,SP,0); // i
  LbI(2); // func().ret:
   LodAMd(RP,SP,12);
   AddAI(SP,16);
   Ret();

• これはなかなかかしこいです。1日で作ったにしてはよくできてます。

(4) 普通のラベル宣言、条件分岐（5日目：6/10）

• 次は普通のラベル定義と比較演算子とif文を作って、インラインアセンブラを使わずに、fib()を書けるようにしました！

  void main()
  {
      fib(46); asm { return R0; }
  }
  
  int fib(int i)
  {
      if (i <= 1) goto skip;
      i = fib(i - 2) + fib(i - 1);
  skip:
      return i;
  }

• ついにfib()内からはインラインアセンブラを追放できました！すごくC言語っぽいです！！
• gotoがちょっとかっこ悪いので、次はブロックのifを作りたいです。

(5) for構文、while構文、do～while構文（6日目：6/11）

• 昨日の予定ではifのブロック構文を作る予定でしたが、 else if をどうやったらうまく処理できるかなーと考えているうちにループ処理を書く方が簡単そうだと思って、これを先にやることにしました。
• これでブロック処理に慣れたので、次はすぐにifのブロック構文書けそうです。

  int main()
  {
      int i;
      for (i = 0x20; i <= 0x7e; i++) {
          putchar(i);
      }
      putchar(0x0a);
      asm { return 0; }
  }
  
  void putchar(int c)
  {
      asm { LodRMd(R0,SP,$c); putchar(R0); }
  }

• ++演算子もつけて、もうすっかりC言語っぽいです！（いやもちろんC言語なんだけど）。

(6) ブロックif構文、アセンブラ、エミュレータ、JITコンパイラ（7日目：6/12）

• ブロックif構文はすぐにできました。

  int main()
  {
      int i;
      for (i = 1; i <= 100; i++) {
          if (i % 15 == 0) {
              asm { printf("FizzBuzz\n"); }
          } else if (i % 3 == 0) {
              asm { printf("Fizz\n"); }
          } else if (i % 5 == 0) {
              asm { printf("Buzz\n"); }
          } else {
              asm { LodRMd(R0,SP,$i); printf("%d\n", R0); }
          }
      }
      asm { End(); }
  }

• ちょっとインラインアセンブラが多すぎる気はしますが、とにかく無事にFizzBuzzできたので、if構文はうまくいっているようです。
• 構文的には「インラインアセンブラ」ではありますが、実質的にはインラインCになっていますね（笑）。

---

• さて、これだけで終わったら簡単すぎてつまらないので、もっとやります。ポインタとか配列とか構造体とかfloat/doubleなどが未着手の課題として残っているわけですが、それはやればできそうな気はするので、必要になったらやればいいやと先送りしましょう（え？）。
• 目下の関心事としてはたくさん生成されているムダ命令の除去もやりたいところですが、最適化はやり始めると面白くなってしばらく帰ってこられない気がするので（笑）、それもいったん先送りにします。
• それで思いついたのは、kharcのエミュレータを作るのはどのくらい大変なんだろうかということです。
• kharcはa25_kharcs1の(2)にある通り、20個くらいしか命令がありません。まあ演算系の命令を増やしたので今では30個くらいにはなっていますが、それでもたかが知れている感じです。x86みたいな実在のCPUと比べたら比較にならないほどシンプルな命令セットです。
• 「すごく大変そうだったら、途中でやめればいいやー。とりあえず1時間くらいでどこまでできるかやってみよー」とよく考えずに始めたところ、結局2時間でできてしまいました。それを以下で説明します。

• まずアセンブラのソースコードのままでは実行しにくいので、これをバイナリに変換します。

  struct KharcBinInst { unsigned char op, prm[3]; int imm; };

• こんな感じの8バイトの構造体を考えて、これがkharcの1命令だということにしました。つまり固定長の命令セットですね。opに命令番号を入れて、prm[]にレジスタ番号を入れます。immに即値を入れます。即値を持たない命令やレジスタ指定を一切しない命令は、それらのフィールドは存在するけど参照しないということにします。
• CmpJneRII()みたいに、一部immフィールドを2つもつ命令がありますが、その場合は命令を2つつないで命令長16バイトということにして、2つ目の命令のopにはAux命令の命令番号を入れておくことにします（Aux命令っていうのは、さっき即席で考えました。命令長を伸ばすためだけの命令で、NOP命令みたいなものです）。これでimmが2つとかレジスタ指定が4個以上になっても大丈夫です。
• この仕様でアセンブラを作ったところ、85行でできてしまいました。もともとラベルとかなくて全部数値だったので、すごく簡単なのです。それに加えてMovRIとかLodRMdみたいに、みんな命令の末尾でパラメータの型を指定してくれているので、アセンブラはほとんどなにもすることがなくて、ただ淡々とバイナリ化していくだけで終わってしまいました（笑）。
• この仕様は大正解だなって思いました！（自画自賛）。

---

• それで次はエミュレータです。switch～caseで、opの値を見て分岐すればいいですよね。適当に書いただけでしたが、68行で書けました。あの簡単すぎたアセンブラよりも簡単にできるとは！
• そしてこんなものでもちゃんと動いてしまったのです。・・・これはヤバい。
• 上記FizzBuzzが、kccだけで実行できて結果が出ちゃうわけです。今までは出力されたアセンブラコードの前後に少し書き足して（まあコピペだから大した手間ではないですが）、それでgccして、それでできた実行ファイルを実行、だったのに。すっごい快適です！

• これで調子に乗ってfib(46)を計算すると・・・うーん、はい、さすがに遅いです。
• まあ当然ですよね、エミュレータなんだから。・・・-でもなんかくやしいわけです。
• こうなったら、JITコンパイラもやってみるしかないですよね？（笑）。

---

• 基本方針として、RxやAxを次のように実レジスタに割り当てました。なんかすごく少ないのですが、今のkccはR0,R1,SP,RPしか使ってないので（＝しょぼい）、とりあえずこれでしのげます。

  R0	R1	R2		SP	RP
  EAX	ECX	EDX		EBP	EBX

• あとは機械語を調べながら作りました。・・・ https://c9x.me/x86/ にかなり助けられました（感謝！）。
• 結局、60行で書けました。・・・はい、ちょっと自分でも何を言っているのかよくわかりません。60行でJITコンパイラって作れていいんでしたっけ？？
• 半信半疑というか、もうほとんど信じられなくて疑いしかないのですが、しかしそれでも問題なく動いて、「うおおおお！」となりました。

---

• さすがに疲れたので、fib(46)でベンチマークを取って今日は終わりにします。

  1.kccに内蔵させた自作のエミュレータで実行	191.798[sec]
  2.kccに内蔵させた自作のエミュレータで実行（改良版）	128.766[sec]
  3.kccに内蔵させた自作のJITコンパイラで実行	15.246[sec]
  4.kccが出力したアセンブラをgccでコンパイルして実行	12.715[sec]
  5.fibのプログラムをそのままgccでコンパイルして実行	4.577[sec]

• やっぱりgccは速いなあ（5）。・・・ムダ命令を削ったら、これに近づけるんだろうか。
• じゃあ、4のコードからムダ命令を手動で削って、どのくらい速くなるかやってみよう。・・・7.747[sec]でした。だから5の4.577[sec]まではいけないにしても、JITコンパイラで9秒台くらいは狙えそうです。
• 今回は速度を追及するための開発ではなくて、1のエミュレータ実行から少ない労力で改善できればいいっていう目的なので、それで十分かなと思います。

     

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.014 sec.