a25_kharcs4
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* 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日目）
--[12]最適化4、ベンチマーク（15日目）
--[13]ポインタ実装1（16日目）
--[14]ポインタ実装2（17日目）
** (8) 最適化1（9日目：6/14）
-「1+a+2+b+3」という式があった時に、これを「a+b+6」にでき...
-加算だけではなく、乗算や除算や減算が混ざっていてもうまく...
-この日はSecHack365のオンラインイベントがあって、21時くら...
-途中でバグに悩まされたりすることもありましたが、最終的に...
-ということで、9日目の成果はこれだけです。・・・いや違っ...
-オンラインイベントの休み時間にちょっと試したことがありま...
-これまでkharcの関数呼び出しは、リターン先をRPレジスタに...
-そして試しにやってみると、fib()のJITコンパイル後の実行速...
** (9) 最適化2（10日目：6/16）
-今までたくさん生成されて、ややうんざりしていたムダ命令を...
-最適化はkharcのバイナリを使って行いました。命令長が固定...
-しかしこれだけだと、最適化を終えたコードを確認するのが大...
-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|RIGHT:273.185[sec]|エミュレータ実行：最適化なし・...
|mod=17|RIGHT:221.202[sec]|エミュレータ実行：最適化なし・...
|mod=18|RIGHT:14.931[sec]|x86JITコンパイラ実行：最適化な...
|mod=19|RIGHT:13.653[sec]|x86JITコンパイラ実行：最適化な...
|mod=0|RIGHT:241.998[sec]|エミュレータ実行：最適化あり・...
|mod=1|RIGHT:''165.459[sec]''|エミュレータ実行：最適化あ...
|mod=2|RIGHT:9.654[sec]|x86JITコンパイラ実行：最適化あり...
|mod=3|RIGHT:''8.321[sec]''|x86JITコンパイラ実行：最適化...
-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()命令で比較式を評価して、...
-でもそれをこのままやると、比較式の値を変数に代入して、さ...
-これに合わせて命令名も変えました。CmpRIしてFreRしてJccI...
-fib(46)の実行速度の改善はこんな感じです。
|mod=16|RIGHT:256.992[sec]|エミュレータ実行：最適化なし・...
|mod=17|RIGHT:216.348[sec]|エミュレータ実行：最適化なし・...
|mod=18|RIGHT:14.958[sec]|x86JITコンパイラ実行：最適化な...
|mod=19|RIGHT:13.648[sec]|x86JITコンパイラ実行：最適化な...
|mod=0|RIGHT:231.065[sec]|エミュレータ実行：最適化あり・...
|mod=1|RIGHT:''157.459[sec]''|エミュレータ実行：最適化あ...
|mod=2|RIGHT:8.345[sec]|x86JITコンパイラ実行：最適化あり...
|mod=3|RIGHT:''8.085[sec]''|x86JITコンパイラ実行：最適化...
----
-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の...
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のやり方はレジスタスタックに十分な余裕があれば大変有...
--ちなみにkharcでは、レジスタスタックは常に2段までしか使...
--(2)一方で、kharcがうまくいっていないところは、ローカル...
--次の呼び出しのための2バイト、fib(i-2)の結果をしまってお...
--じゃあ残りの6バイトは何なのかというと、2バイトがリター...
--(3)ちなみにkharcでは https://github.com/buntan-pc/bunta...
--使い方がわかればすぐに対応できるようにしてあります。
--(4)レジスタマシンを想定したコンパイラがここまでスタック...
----
-ここまでの結果を踏まえて考えました。
-今のkccは内部でいきなりテキスト状態のアセンブラを出力し...
-また最適化するタイミングもよくないです。スタックフレーム...
-ということで、そろそろリファクタリングですかね・・・。
** (11) リファクタリング（12～14日目）
-12日目（6/18）はリファクタリングで、主に内部機械語の仕様...
--変更前： struct KhaBinInst { unsigned char op, prm[3]; ...
--変更後： struct KhaBinInst { int op; unsigned char prm[...
-こうすることで、Aux命令は不要になります（最適化の時にAux...
-命令番号も8bitに収めるために工夫するよりは余裕を持たせて...
----
-13日目（6/19）もリファクタリングです。今回のリファクタリ...
-コンパイラはアセンブラを生成せず、いきなり機械語を生成す...
-それで全部移行できたら、今度はテキストで保持する方法をや...
----
-14日目（6/20）もリファクタリングです。
-インラインアセンブラをどうするか悩みましたが、結局インラ...
-インラインアセンブラで本当にアセンブラだけ書いてあるなら...
-残りの部分も組み立てて「コンパイラはバイナリを出力して、...
-ソースコードを出力する必要がある時は、逆アセンブルして出...
** (12) 最適化4、ベンチマーク（15日目：6/23）
-[最適化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のアセンブラを...
--(3)fib46をkccで書いて、kccのmod=3でJITコンパイル実行し...
--同様のことをmandelでも行いました。
--ちなみにどれも32bit版でやっています。
| |fib46 |mandel |
|(1)|RIGHT:4.608[sec](1.00倍)|RIGHT:1.874[sec](1.00倍)|
|(2)|RIGHT:7.279[sec](1.57倍)|RIGHT:3.373[sec](1.80倍)|
|(3)|RIGHT:8.179[sec](1.77倍)|RIGHT:2.919[sec](1.56倍)|
-これをみると、kcc用でプログラムを書いた場合、最初からgcc...
-つまりもし仮にkccにgccを超えるような便利機能を入れたとし...
-これを気にならない差だと思うなら、kccの中で暮らせるとい...
-うーん、もうちょっと速くなって、1.2倍くらいで収まってく...
** (13) ポインタ実装1（16日目：6/24）
-ポインタの実装を始めました。今日はここまでできるようにな...
#include "kharc.h"
int main()
{
int i, *p;
p = &i;
i=12345678;
*p = 123;
return i;
}
-ちゃんと123が返ってきます。
** (14) ポインタ実装2（17日目：6/25）
-ポインタの実装を進めて、配列が使えるようになりました。ま...
#include "kharc.h"
int main()
{
int i, a[11];
a[0] = 0; a[1] = 1;
for (i = 2; i < 11; i++) {
a[i] = a[i - 2] + a[i - 1];
}
i = a[10];
return i;
}
終了行:
* 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日目）
--[12]最適化4、ベンチマーク（15日目）
--[13]ポインタ実装1（16日目）
--[14]ポインタ実装2（17日目）
** (8) 最適化1（9日目：6/14）
-「1+a+2+b+3」という式があった時に、これを「a+b+6」にでき...
-加算だけではなく、乗算や除算や減算が混ざっていてもうまく...
-この日はSecHack365のオンラインイベントがあって、21時くら...
-途中でバグに悩まされたりすることもありましたが、最終的に...
-ということで、9日目の成果はこれだけです。・・・いや違っ...
-オンラインイベントの休み時間にちょっと試したことがありま...
-これまでkharcの関数呼び出しは、リターン先をRPレジスタに...
-そして試しにやってみると、fib()のJITコンパイル後の実行速...
** (9) 最適化2（10日目：6/16）
-今までたくさん生成されて、ややうんざりしていたムダ命令を...
-最適化はkharcのバイナリを使って行いました。命令長が固定...
-しかしこれだけだと、最適化を終えたコードを確認するのが大...
-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|RIGHT:273.185[sec]|エミュレータ実行：最適化なし・...
|mod=17|RIGHT:221.202[sec]|エミュレータ実行：最適化なし・...
|mod=18|RIGHT:14.931[sec]|x86JITコンパイラ実行：最適化な...
|mod=19|RIGHT:13.653[sec]|x86JITコンパイラ実行：最適化な...
|mod=0|RIGHT:241.998[sec]|エミュレータ実行：最適化あり・...
|mod=1|RIGHT:''165.459[sec]''|エミュレータ実行：最適化あ...
|mod=2|RIGHT:9.654[sec]|x86JITコンパイラ実行：最適化あり...
|mod=3|RIGHT:''8.321[sec]''|x86JITコンパイラ実行：最適化...
-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()命令で比較式を評価して、...
-でもそれをこのままやると、比較式の値を変数に代入して、さ...
-これに合わせて命令名も変えました。CmpRIしてFreRしてJccI...
-fib(46)の実行速度の改善はこんな感じです。
|mod=16|RIGHT:256.992[sec]|エミュレータ実行：最適化なし・...
|mod=17|RIGHT:216.348[sec]|エミュレータ実行：最適化なし・...
|mod=18|RIGHT:14.958[sec]|x86JITコンパイラ実行：最適化な...
|mod=19|RIGHT:13.648[sec]|x86JITコンパイラ実行：最適化な...
|mod=0|RIGHT:231.065[sec]|エミュレータ実行：最適化あり・...
|mod=1|RIGHT:''157.459[sec]''|エミュレータ実行：最適化あ...
|mod=2|RIGHT:8.345[sec]|x86JITコンパイラ実行：最適化あり...
|mod=3|RIGHT:''8.085[sec]''|x86JITコンパイラ実行：最適化...
----
-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の...
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のやり方はレジスタスタックに十分な余裕があれば大変有...
--ちなみにkharcでは、レジスタスタックは常に2段までしか使...
--(2)一方で、kharcがうまくいっていないところは、ローカル...
--次の呼び出しのための2バイト、fib(i-2)の結果をしまってお...
--じゃあ残りの6バイトは何なのかというと、2バイトがリター...
--(3)ちなみにkharcでは https://github.com/buntan-pc/bunta...
--使い方がわかればすぐに対応できるようにしてあります。
--(4)レジスタマシンを想定したコンパイラがここまでスタック...
----
-ここまでの結果を踏まえて考えました。
-今のkccは内部でいきなりテキスト状態のアセンブラを出力し...
-また最適化するタイミングもよくないです。スタックフレーム...
-ということで、そろそろリファクタリングですかね・・・。
** (11) リファクタリング（12～14日目）
-12日目（6/18）はリファクタリングで、主に内部機械語の仕様...
--変更前： struct KhaBinInst { unsigned char op, prm[3]; ...
--変更後： struct KhaBinInst { int op; unsigned char prm[...
-こうすることで、Aux命令は不要になります（最適化の時にAux...
-命令番号も8bitに収めるために工夫するよりは余裕を持たせて...
----
-13日目（6/19）もリファクタリングです。今回のリファクタリ...
-コンパイラはアセンブラを生成せず、いきなり機械語を生成す...
-それで全部移行できたら、今度はテキストで保持する方法をや...
----
-14日目（6/20）もリファクタリングです。
-インラインアセンブラをどうするか悩みましたが、結局インラ...
-インラインアセンブラで本当にアセンブラだけ書いてあるなら...
-残りの部分も組み立てて「コンパイラはバイナリを出力して、...
-ソースコードを出力する必要がある時は、逆アセンブルして出...
** (12) 最適化4、ベンチマーク（15日目：6/23）
-[最適化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のアセンブラを...
--(3)fib46をkccで書いて、kccのmod=3でJITコンパイル実行し...
--同様のことをmandelでも行いました。
--ちなみにどれも32bit版でやっています。
| |fib46 |mandel |
|(1)|RIGHT:4.608[sec](1.00倍)|RIGHT:1.874[sec](1.00倍)|
|(2)|RIGHT:7.279[sec](1.57倍)|RIGHT:3.373[sec](1.80倍)|
|(3)|RIGHT:8.179[sec](1.77倍)|RIGHT:2.919[sec](1.56倍)|
-これをみると、kcc用でプログラムを書いた場合、最初からgcc...
-つまりもし仮にkccにgccを超えるような便利機能を入れたとし...
-これを気にならない差だと思うなら、kccの中で暮らせるとい...
-うーん、もうちょっと速くなって、1.2倍くらいで収まってく...
** (13) ポインタ実装1（16日目：6/24）
-ポインタの実装を始めました。今日はここまでできるようにな...
#include "kharc.h"
int main()
{
int i, *p;
p = &i;
i=12345678;
*p = 123;
return i;
}
-ちゃんと123が返ってきます。
** (14) ポインタ実装2（17日目：6/25）
-ポインタの実装を進めて、配列が使えるようになりました。ま...
#include "kharc.h"
int main()
{
int i, a[11];
a[0] = 0; a[1] = 1;
for (i = 2; i < 11; i++) {
a[i] = a[i - 2] + a[i - 1];
}
i = a[10];
return i;
}
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
