コグノスケ

CoreMarkのコンパイルオプションをチューンする

目次: RISC-V

以前（2022年12月22日の日記参照）の日記でCoreMarkのスコアを測って表にしました。実はCoreMarkはOfastのみでは最速にはならず、コンパイルオプションをガチガチにチューンすると結構差が出ます。実際にNSITEXE NS31Aの測定結果でお見せしたいと思います。

どうしてNS31Aかというと、非常にシンプルなCPU＆自分の会社で作っているので素性が明確であるためです。複雑なCPU、中身の分からないCPUになればなるほど、総当たりでオプションの組み合わせを試す不毛な作業になりがちです。今回はそういう組み合わせ問題を解きたいわけじゃないんで、簡単な奴で行きます。

まずはベースとなるOfastの結果です。実はO3でも結果は同じです。

2K performance run parameters for coremark.
CoreMark Size    : 666
Total ticks      : 18912
Total time (secs): 18.912000
Iterations/Sec   : 58.164129
Iterations       : 1100
Compiler version : GCC12.2.0
Compiler flags   : -Ofast -gdwarf-4 -march=rv32im -mabi=ilp32 -mcmodel=medany
Memory location  : Please put data memory location here
                        (e.g. code in flash, data on heap etc)
seedcrc          : 0xe9f5
[0]crclist       : 0xe714
[0]crcmatrix     : 0x1fd7
[0]crcstate      : 0x8e3a
[0]crcfinal      : 0x33ff
Correct operation validated. See README.md for run and reporting rules.
CoreMark 1.0 : 58.164129 / GCC12.2.0 -Ofast -gdwarf-4 -march=rv32im -mabi=ilp32 -mcmodel=medany   / Heap

動作周波数は25MHzですので、58.164129 / 25 = 2.326 CM/MHz です。

コンパイルオプションを足そう

最適化の基本となる、ループアンローリング、インライン化（-funroll-all-loops, -finline-functions）を足します。

キャッシュラインが32バイトなので、関数の先頭を32バイト境界に配置します（-falign-functions=32）。関数先頭で命令キャッシュミスヒットが発生したときに、同じキャッシュラインに後続の命令（1ラインに32 / 4 = 8命令）が載ります。後続の命令フェッチがキャッシュヒットすれば、最初のミスヒットを挽回できるだろうという目的です。

ジャンプやループの際に実行しない命令が中途半端にキャッシュに取り込まれないよう（= 利用効率の向上）、ジャンプやループの位置は8バイト境界に配置します（-falign-jumps=8 -falign-loops=8）。これも32バイト境界にすべきかと思いましたが、コード領域が散逸しすぎるためか逆に遅いです。

基本的に関数はインライン化した方がcall, retを省略、レジスタ共用など全体的に最適化できて速いです。しかしNS31Aは命令キャッシュが小さめ（FPGA向けコンフィグでは16KB）なので、無差別に関数をインライン化すると命令キャッシュがあふれてキャッシュミスヒットが発生してしまい、逆に遅くなります。

従ってあまりにも大きな関数はインライン化しないように設定します（-finline-limit=300）。デフォルト値600の1/2にしています（※）。

2K performance run parameters for coremark.
CoreMark Size    : 666
Total ticks      : 15819
Total time (secs): 15.819000
Iterations/Sec   : 69.536633
Iterations       : 1100
Compiler version : GCC12.2.0
Compiler flags   : -Ofast -gdwarf-4 -march=rv32im -mabi=ilp32 -mcmodel=medany -funroll-all-loops -finline-functions -finline-limit=300 -falign-functions=32 -falign-jumps=8 -falign-loops=8
Memory location  : Please put data memory location here
                        (e.g. code in flash, data on heap etc)
seedcrc          : 0xe9f5
[0]crclist       : 0xe714
[0]crcmatrix     : 0x1fd7
[0]crcstate      : 0x8e3a
[0]crcfinal      : 0x33ff
Correct operation validated. See README.md for run and reporting rules.
CoreMark 1.0 : 69.536633 / GCC12.2.0 -Ofast -gdwarf-4 -march=rv32im -mabi=ilp32 -mcmodel=medany -funroll-all-loops -finline-functions -finline-limit=300 -falign-functions=32 -falign-jumps=8 -falign-loops=8  / Heap

動作周波数は25MHzですので、69.536633 / 25 = 2.781 CM/MHzです。ハードウェアは何も変えていませんが、性能1.2倍です。コンパイルオプションの威力恐るべし。

（※）この数値はGCC内部で使う仮想命令のライン数らしく、300が本当に適切か示すのは不可能です。マニュアルを見ると1/2や1/4に調整することが多いようなので、それに倣っています（参考: GCCのマニュアル）。

卵が割れる階数は？問題

Twitterで見かけて面白かった問題、解法をメモしておきます。

100階建てのビルから卵を落とします。卵はある階よりも低ければ割れませんが、ある階よりも高いと割れます。卵を2つ持っているとき、卵が何階で割れるか調べる方法を提示してください。そのとき卵を落とす最大の回数をできる限り小さくしてください。

という問題です。

基本的な考え方

1階から順に落とせば確実にわかりますが、最大の投擲回数が100回（卵が割れる階数が100Fのとき）になり、最適な方法ではありません。

卵が2個あることを利用し、1個目は複数階を一気に飛ばして（例10F, 20F, 30F, ...）投擲します。例えば10F飛ばしで試すとすると10F, 20F, 30Fで割れず40Fで割れたら、2個目は「最後に割れなかった階の1つ上の階」すなわち31Fから投擲します。このように試すともっと早く卵が割れる階数がわかります。

卵の投擲回数の最大値を計算すると、例えば10F飛ばしであれば1個目が最大10回（10F, 20F, 30F, ..., 90F, 100F）、2個目が最大で9回（x1F〜x9F）なので、19回（卵が割れる階数が99Fのとき）です。100回と比べるとだいぶ少なくなりましたが、まだ無駄が残っています。

答え

固定階数を飛ばす方法だと1個目と2個目の最大の投擲回数の和を見たとき、上の階になるほど悪化します。例えば、

• 卵が割れる階数が39F: 10F〜30Fまでで3回、31F〜39Fで最大9回 = 12回
• 卵が割れる階数が99F: 10F〜90Fまでで9回、91F〜99Fで最大9回 = 18回

1個目の投擲方法を変えて最初は10F飛ばし、次は9F飛ばし、その次は8F飛ばし、のようにすると投擲回数の最大値が悪化しないことに気づくと思います。

こんな表で示すとわかりやすいでしょうか。

1個目は12F, 25F, 37F, 48F, 58F, 67F, 75F, 82F, 88F, 93F, 97F, 100Fの順に投擲します。最大で12回です。割れたら最後に成功した階の1つ上の階から投擲すると、最大14回で卵が割れる階数がわかります。

最大の回数になるケースは12通りですが、一例として卵が割れる階数が99Fの場合を示します。12, 25, ..., 100（1個目が割れる）, 98, 99（2個目が割れる）の14回になります。

他には1個目を投げる階数を下記のようにしても良いです。

• 9F, 22F, 34F, 45F, 55F, 64F, 72F, 79F, 85F, 90F, 94F, 97F, 99F, 100F
• 10F, 23F, 35F, 48F, 56F, 65F, 73F, 80F, 86F, 91F, 95F, 98F, 100F

いずれも投擲回数は最大14回となります。

C言語でlongをintにキャストしたらどうなるの？

目次: C言語とlibc

最近RISC-V 64bit向けのLinuxシステムコールの実装を調べていました（2023年2月1日の日記など）。そのなかでlong型をintにキャストし、負の値として解釈している部分がありました。

C言語に詳しい方は「あれ？」と思ったかもしれません。一見して問題なさそうな操作ですが、C言語の仕様によれば結果は実装依存（implementation-defined）です。アーキテクチャやコンパイラ次第で結果が変わるということです。

条件はlongよりintの方が大きい（sizeof(long) > sizeof(int) になる）ときです。現代では64bit環境が該当するでしょう。32bit環境は大抵longとintが同じ値域なので問題は発生しません。

概要をお伝えしたところで、言語仕様を見てみましょう。

6.3.1.3 Signed and unsigned integers

When a value with integer type is converted to another integer type other than
_Bool, if the value can be represented by the new type, it is unchanged.

Otherwise, if the new type is unsigned, the value is converted by repeatedly
adding or subtracting one more than the maximum value that can be represented
in the new type until the value is in the range of the new type.

Otherwise, the new type is signed and the value cannot be represented in it;
either the result is implementation-defined or an implementation-defined signal
is raised.


（ざっくり和訳）

整数型の値が _Bool以外の整数型に変換される場合、もし値が新しい型で表現できるなら
値は変化しません。

新しい型が符号なしで表現できないならば、新しい型の範囲に入るまで、新しい型が表現できる
最大値より1多い値を繰り返し加算または減算して値を変換します。

（訳注）
パディング等も認められているのでややこしい言い方になっている。
元の型が32bit整数で0x2_3456、新しい型が16bit整数で最大値0xffffだとする。
このとき新しい型の最大値 + 1 = 0x1_0000である。

元の型の値0x2_3456は新しい型の範囲より大きいので、最大値 + 1を減算し続ける。
・0x2_3456 - 0x1_0000 = 0x1_3456 → 新しい型の範囲に入っていない
・0x1_3456 - 0x1_0000 = 0x0_3456 → 新しい型の範囲に入った
よって新しい型の値は0x3456となる。

この処理は新しい型から溢れた上位ビット（つまりこの例でいえば16bit以上の上位ビット）を
全て0クリアする処理に相当する。
（訳注、終わり）

新しい型が符号付きで値を表現できないならば、結果は実装定義になるか、もしくは実装定義の
シグナルが生成されます。

Linuxは対象とするアーキテクチャとコンパイラが限定（GCCかClang）されており、実装依存の動きを把握した上で使っていると思われます。承知の上というやつですね。

どの実装で使われるかわからないコードを書くなら、longからintへのキャストは常に結果が同じとは限らないので、キャストの結果で何が起きるか理解して使う必要があります。

気にしすぎても仕方がない

建前は上記の通りですが「全てのCコンパイラで動作するコード」を書く機会って、ほぼないと思います。基本的には細かい仕様を気にしすぎて何も進まなくなるより、時代で受け入れられる常識的な制約を付けて進めて、後で困ったら直せば良いんじゃない？と思います。

一方で2038年問題のように、プログラムが書かれた時代は常識的な制約だったしみんな使っていたけど、何十年も経ってから大問題になるケースもあります。「常識的な制約 = ずっと無罪放免」かどうかは誰にもわかりません。

今の64bitアーキテクチャに由来する時間や容量の制約は十分余裕があると思われますが、100年後の世界なんてわかりません。「誰が64bit決め打ちの実装にした！？100年前の奴らだと……？？」って泣きながら直している人がいても不思議じゃないですよね。

RISC-V 64bit Linuxとシステムコールと32bitの引数 その6 - SYSCALL_DEFINE() を全部展開

目次: RISC-V

昨日の続きです。「64bit環境においてシステムコールの引数がレジスタ長（= 64bit）以下だった場合（例えばintが典型例）、どう扱うか？」コードの解説編です。

どうして符号拡張されるのか？逆アセンブルで説明したつもりになってはいけない、逃げてはダメだ！という熱心なあなたのために、マクロを展開しながら説明します。今回の解説は __MAP(), __SC_LONG(), __SC_CAST() マクロの意味や実装です。

SYSCALL_DEFINE() の展開

今までのSYSCALL_DEFINE(), __MAP(), __SC_LONG(), __SC_CAST() マクロを全部合体させて展開して、組み込み関数などを外すとこうなるはずです。

asmlinkage long __se_sys_reboot(__MAP(4,__SC_LONG,int, magic1, int, magic2, unsigned int, cmd, void __user *, arg))
{
	long ret = __do_sys_reboot(__MAP(4,__SC_CAST,int, magic1, int, magic2, unsigned int, cmd, void __user *, arg));
	__MAP(4,__SC_TEST,int, magic1, int, magic2, unsigned int, cmd, void __user *, arg);
	__PROTECT(4, ret,__MAP(4,__SC_ARGS,int, magic1, int, magic2, unsigned int, cmd, void __user *, arg));
	return ret;
}

↓こうなる

asmlinkage long __se_sys_reboot(long magic1, long magic2, long cmd, long arg)
{
	long ret = __do_sys_reboot((int)magic1, (int)magic2, (unsigned int)cmd, (void __user *)arg));
	//__SC_TEST() による型のチェック、チェックに引っかかったらコンパイルエラー
	//__PROTECT(magic1, magic2, cmd, arg) に展開されるがRISC-V 64bitでは何も意味はない
	return ret;
}

つまり __se_sys_reboot() ではシステムコールからの引数はlong long, unsigned long longを除いて常にlong型の引数として扱い（__SC_LONGマクロの働き）、システムコールの本体 __do_sys_reboot() にはシステムコールが定義する本来の型にキャストして渡します（__SC_CASTマクロの働き）。

例えばmusl libcのreboot() のmagic1にあたるレジスタa0には0x00000000_fee1deadが渡されます。longの値として解釈すると正の数4276215469ですが、__do_sys_reboot() の呼び出し時にintにキャストして渡すため0xfee1dead = -18751827であると解釈されます（たぶん、大抵は）。

キャストされた負のint型の値を __do_sys_reboot() はlong型の引数で受け取ります。このときlong型で -18751827と解釈される値（= 0xfee1deadを64bitに符号拡張した0xffffffff_fee1dead）をレジスタa0に格納して、関数呼び出しを行います。

(gdb) b __do_sys_reboot
Breakpoint 1 at 0xffffffff8002d860: file kernel/reboot.c, line 702.

(gdb) c
Continuing.

Breakpoint 1, __do_sys_reboot (magic1=-18751827, magic2=672274793,
    cmd=1126301404, arg=0x4321fedc) at kernel/reboot.c:702
702     {

(gdb) p/x $a0
$1 = 0xfffffffffee1dead

なので __do_sys_reboot() でブレークしてレジスタa0の内容を表示すると、0xffffffff_fee1deadになっていたわけです。

いやー長かった。マクロの魔術ですね。