30年振りにコンパイラの定数整数除算を改善した

Kernel/VM探検隊@東京 No19
https://kernelvm.connpass.com/event/395390/

Transcript

1. 30年振りにコンパイラの定数整数除算を改善した 光成滋生 Kernel/VM探検隊@東京 No19 2026/08/17 1 / 14
2. 自己紹介 暗号と高速実装のR&D@サイボウズ・ラボ 高度な最適化のためのJITアセンブラXbyak oneDNN, Open VINO, AMD EPYC用GEMMなどのエンジン 最近は中国勢によるXbyak_riscvを用いた開発も盛ん ペアリング暗号・BLS署名ライブラリmcl-wasm npmパッケージは延べ3400万DL, 22万dependents Claude for OSPやMicrosoft MVP受賞 Claude Max 20xやGitHub Copilot Maxが半年~1年無料で使える 最近やってること 暗号の計算で多用される割り算を速くするアルゴリズムの研究 その中で得た知見を元にコンパイラを改善する 2 / 14
3. 去年のkernel/VM探検隊での発表のおさらい コンパイラが生成する「x/7」のアセンブリコードが複雑だなと思った ので改善アルゴリズムを考えた // コンパイラのコード(org) // 改良アルゴリズム uint32_t udiv7(uint32_t x) { uint64_t v = x * uint64_t(c); v >>= 32; uint32_t t = ((x - v) >> 1) + v; return t >> 2; } uint32_t div7opti(uint32_t x) { uint64_t v = x * uint64_t(c); v >>= 32; v += x; return uint32_t(v >> 3); } ⇒ コード中のcは除数7に対するマジックナンバー0x24924925 「x/7」→「乗算x1+シフトx3+減算x1+加算x1」→「乗算x1+シフトx2+加算x1」 に改善 オリジナルのアルゴリズム [GM94] Granlund, Montgomery, "Division by invariant integers using multiplication" 3 / 14 Xbyakによる実装実験で1.25~1.28倍速
4. その後、更に改良したアルゴリズム 「乗算x1+シフトx3+減算x1+加算x1」が「乗算x1」になった // 改良アルゴリズム2 // コンパイラのコード(org) uint32_t udiv7(uint32_t x) { uint64_t v = x * uint64_t(c); v >>= 32; uint32_t t = ((x - v) >> 1) + v; return t >> 2; } ⇒ const uint128_t c2 = (c|(uint128_t(1)<<32)) << (64 - 3); uint32_t div7opti(uint32_t x) { return (uint32_t)((x * c2) >> 64); } 定数c2をcとシフト量からの事前計算 実際の計算は64bit x 64bit→128bit乗算の上位64bit取得 通常64bit CPUでは上位64bitと下位64bitに分かれるので64bit右シフトは実質不要 ループの中で効果が高そう…… コンパイラに組み込みたい コンパイラの改善は昔ならとても大変だが今はAIがある 4 / 14
5. llvm-project(llvm-20)を改造してみた 規模感 項目 ファイル数 行数 C/C++（テスト除く） 26509 9.34M DSL(.td) 1244 0.97M 合計 27753 10.3M どこから手をつけてよいのやら しかしAIはすごい 数日ぐらいの工数でそれっぽくパッチを当てられるようになった しかし最初はバグで常に0を返すコードになっていた もうしばらく試行錯誤して望みのコードを出してくれるようになった 5 / 14
6. Clang-20でベンチマークを取ってみた Clang-20でLLVM-IR(.ll)を生成し、それから改造llvm-20で.s出力 int bench(uint32_t ret) { for (int i = 0; i < 1000000000; i++) { ret ^= (i ^ ret) / 7; ret ^= (i ^ ret) / 19; ret ^= (i ^ ret) / 107; } return ret; } CPU Before (sec) After (sec) Speedup Intel Xeon 6.33 3.80 x1.67 Apple M4 6.70 3.38 x1.98 Apple M4で2倍近く速くなった 6 / 14
7. llvmが生成したコード(x86-64) llvm-20オリジナル .lp: movl %ecx, %esi xorl %eax, %esi imulq $613566757, %rsi, %rdi shrq $32, %rdi subl %edi, %esi shrl %esi addl %edi, %esi shrl $2, %esi xorl %eax, %esi movl %esi, %edi xorl %ecx, %edi movq %rdi, %rax imulq %rdx, %rax shrq $32, %rax subl %eax, %edi shrl %edi addl %eax, %edi shrl $4, %edi xorl %esi, %edi movl %edi, %eax xorl %ecx, %eax imulq $842937507, %rax, %rsi shrq $32, %rsi subl %esi, %eax shrl %eax addl %esi, %eax shrl $6, %eax xorl %edi, %eax incl %ecx cmpl $1000000000, %ecx jne .lp 改良版 ⇒ .lp: movl %ecx, %edx xorl %eax, %edx mulxq %rsi, %r9, %r9 xorl %eax, %r9d movl %r9d, %edx xorl %ecx, %edx mulxq %rdi, %r10, %r10 xorl %r9d, %r10d movl %r10d, %edx xorl %ecx, %edx mulxq %r8, %rax, %rax xorl %r10d, %eax incl %ecx cmpl $1000000000, %ecx jne .lp 想定通り、定数設定はループ外に出されてループ内で 「乗算x1+シフトx3+減算x1+加算x1」が「乗算x1」になった Apple M4やRISCV64も同じ効果を得られた 7 / 14
8. 本家に取り込んでもらうには そこからの方がずっと大変だった プロジェクトの流儀・お作法に合わせる コーディング規約, テストの書き方, テスト方法（このあたりはAI様様） レビュワーに正しく動くことの説明・説得 1回のフルテストで数時間とか（112core 384GiBメモリマシンがあってよかった） コンパイラは沢山の環境で動くのでできるだけ汎用的にする しかし, 新しい最適化手法が遅くなる環境には適用されないようにする 約1カ月でmergeされた 2/13にPRを出して3/7にmergeされた #181288 その後@kariya_mitsuruさんのアイデアをベースにx/14なども最適化対象に入れた #207634 8 / 14
9. 横展開 llvm（コンパイラ基盤）に対する改善なので Clang(C/C++)だけでなくRust, Swift, Julia, Zig, D, Kotlinなども恩恵を受ける GCC 同じことをGCCにもやってみる AIにさせるやりかたは同じなので勘どころも分かり, すぐ動くようになった しかし開発者の文化の違いに戸惑う llvmはGitHub上のPR+review+merge → 今どきのやり方 → 分かりやすい GCCはMLが舞台（メーリングリスト, not マシーンラーニング） パッチ（プレーンテキスト）を送る/大量のメールにすぐ埋もれる 誰にCc:すればよいのやら → これもAIに教えてもらう Thank youやHelloなどの挨拶不要: 簡潔なメールが望ましい 9 / 14
10. 3.5カ月かかってmergeされた trunkに入ってる 3/25に最初のパッチを送り、9回作り直して7/12にmergeされた より汎用的になったのでuint8_tやuint16_tも最適化対象になった GoにもPRしてmergeされた こちらもまた異なる文化: go-reviewという独自のツール上でやりとりする 自分のgmailアドレスを登録して証明書を発行する インタフェースも慣れないと見落とす（送信したつもりがdraftのままだったとか） Go 1.28（2027年2月release）予定 他の人もやってくれた AppleのWebKitのJavaScriptエンジンに適用してくれた 作者は昔サイボウズ・ラボユースで私が担当した@Constellation さん 10 / 14
11. GCCに対する実際のパッチ gcc/expmed.c (c585baad310) static rtx expand_wide_mulh_udiv (scalar_int_mode int_mode, rtx op0, unsigned HOST_WIDE_INT ml, int size, int post_shift, int extra_cost, int max_cost, bool speed) { scalar_int_mode wide_mode; if (post_shift < 1 || !GET_MODE_2XWIDER_MODE (int_mode).exists (&wide_mode) || GET_MODE_BITSIZE (wide_mode) > BITS_PER_WORD || GET_MODE_BITSIZE (wide_mode) > HOST_BITS_PER_WIDE_INT) return NULL_RTX; unsigned HOST_WIDE_INT magic = ((HOST_WIDE_INT_1U << size) + ml) << (size - post_shift); start_sequence (); rtx x_wide = convert_to_mode (wide_mode, op0, 1); rtx hi = expmed_mult_highpart (wide_mode, x_wide, gen_int_mode (magic, wide_mode), NULL_RTX, 1, max_cost); rtx quotient = hi ? convert_to_mode (int_mode, hi, 1) : NULL_RTX; rtx_insn *insns = end_sequence (); unsigned classic_cost = mul_highpart_cost (speed, int_mode) + extra_cost; if (quotient == NULL_RTX || seq_cost (insns, speed) > classic_cost) return NULL_RTX; emit_insn (insns); return quotient; } ⇒ 対象のビット長を持つか確認 ⇒ マジックナンバーを計算 ⇒ 64bit乗算の上位bitを取り出す ⇒ 最適化前よりコストがかかってるなら棄却 ⇒ 構築した命令を発行する 11 / 14
12. GCCの今回の最適化対象の歴史 GM94のご本人Granlundさんが1994年にコミットしていた >gcc% git show 55c2d311c4f commit 55c2d311c4fa96040ac08766048a14e4cd8d1c54 Author: Torbjorn Granlund <tege@gnu.org> Date: Wed Jun 29 00:23:02 1994 +0000 当時の64bit CPU DEC Alpha（1992年）は32bit乗算が21cycle, umulh(IMULQ)が23cycleだった 今回の32bit定数整数除算最適化手法は当時のAlphaに対しても有効だったと思われる x86-64では初代64bit CPUのAMD K8 Opteron（2003年）でも有効 12 / 14
13. おまけの細かい話 mulx H, L, R [H:L] = R * rdx: Rレジスタとrdxを掛けて上位64bitがH, 下位64bitがLに入る クイズ mulx A, A, Aはどうなる?（Aは同じレジスタ） 1. 未定義 2. Aに上位64bitが入る 3. Aに下位64bitが入る 答え 2のAに上位64bitが入るAArch64のumulh相当 上位64bitを得るumulhと下位64bitを得るumulがある（一度に128bit得る命令は無い） GCCはこれに対応していなかったのでそのパッチも送ってmergeされた(3cca524e337) 13 / 14
14. おまけのおまけ 定数は小さい方がいい マジックナンバーとして 的な値を使うやりかたもある が, これだと0じゃない部分のビット長が今回の方法よりも長くなる 今回のc2は桁数最小であることが証明できる x64ではmovに64bit定数を使える AArch64やRISC-V(RV64)では複数命令が必要なので定数は小さい方がうれしい 14 / 14