はじめに
興味があったので以下の件についてLLVMの観点で原因を探ってみました。
以下、デバッグビルドしたLLVM15.0.7を使ってみていきます。
"std::uniform_real_distributionが遅い件"で問題とされた部分
const long double __r = static_cast<long double>(__urng.max()) - static_cast<long double>(__urng.min()) + 1.0L;
const size_t __log2r = std::log(__r) / std::log(2.0L);
このままでは、コンパイル出来ないので整形します。上記コード中の__urng.max()と__urng.min()は、たどるとそれぞれstd::numeric_limitsのmax()とmin()となっているので、そのように置き換えます。
整形したコードによる結果確認。
#include <limits>
#include <cmath>
int main(){
double max = std::numeric_limits<double>::max();
double min = std::numeric_limits<double>::min();
const long double __r = static_cast<long double>(max) - static_cast<long double>(min) + 1.0L;
const size_t __log2r = std::log(__r) / std::log(2.0L);
return __log2r;
}
整形したコードをLLVM15.0.7のclang++(-O3)でコンパイルすると以下のような問題とされたアセンブリコードと同様のコードが生成されます。
main: // @main
sub sp, sp, #32
stp x29, x30, [sp, #16] // 16-byte Folded Spill
add x29, sp, #16
adrp x8, .LCPI0_0
ldr q0, [x8, :lo12:.LCPI0_0]
bl logl
adrp x8, .LCPI0_1
str q0, [sp] // 16-byte Folded Spill
ldr q0, [x8, :lo12:.LCPI0_1]
bl logl
mov v1.16b, v0.16b
ldr q0, [sp] // 16-byte Folded Reload
bl __divtf3
bl __fixunstfdi
ldp x29, x30, [sp, #16] // 16-byte Folded Reload
add sp, sp, #32
ret
また、g++-12(-O3)でコンパイルすると以下のような定数を返すアセンブリコードとなります。
main:
.LFB981:
mov w0, 1023
ret
これをみると元記事にもあったとおりLLVMの定数最適化に問題がありそうです。
定数最適化を阻害している要因はなにか?
定数最適化を阻害している要因は何でしょうか。以下コードのようにstd::log関数の引数の型をdouble型した場合はどうでしょうか。
#include <limits>
#include <cmath>
int main(){
double max = std::numeric_limits<double>::max();
double min = std::numeric_limits<double>::min();
const long double __r = static_cast<long double>(max) - static_cast<long double>(min) + 1.0L;
const size_t __log2r = std::log(static_cast<double>(__r)) / std::log(2.0);
return __log2r;
}
以下のように置き換えた場合は、定数化されることが分かります。
main: // @main
mov w0, #1024
ret
これによりlong double型の引数が指定された場合のstd::log関数の部分に原因があることが分かります。
LLVMで問題の定数最適化を行っている部分はどこか?
これを探るためにはデバッグビルドしたときに使用できる以下の2つオプションが役に立ちます。
- -mllvm -print-before-all
- -mllvm -print-after-all
これらのオプションをつけてコンパイルすると以下のような最適化処理の前後のLLVM IRのログを見ることが出来ます。
これらのオプションをつけて定数化が出来ているstd::log関数の引数をdouble型にキャストしたコードについて見ていきます。
*** IR Dump Before EarlyCSEPass on main ***
; Function Attrs: mustprogress nofree norecurse nounwind willreturn writeonly uwtable
define dso_local noundef i32 @main() local_unnamed_addr #0 {
entry:
%conv = fpext double 0x7FEFFFFFFFFFFFFF to fp128
%conv2 = fpext double 0x10000000000000 to fp128
%sub = fsub fp128 %conv, %conv2
%add = fadd fp128 %sub, 0xL00000000000000003FFF000000000000
%conv3 = fptrunc fp128 %add to double
%call4 = call double @log(double noundef %conv3) #2
%div = fdiv double %call4, 0x3FE62E42FEFA39EF
%conv6 = fptoui double %div to i64
%conv7 = trunc i64 %conv6 to i32
ret i32 %conv7
}
*** IR Dump After EarlyCSEPass on main ***
; Function Attrs: mustprogress nofree norecurse nounwind willreturn writeonly uwtable
define dso_local noundef i32 @main() local_unnamed_addr #0 {
entry:
ret i32 1024
}
このログによるとEarlyCSEPassにて定数化にまつわる最適化を行っていることが分かります。では定数化出来ていないstd::log関数の引数がlong double型のコードの場合はどうでしょうか。
*** IR Dump Before EarlyCSEPass on main ***
; Function Attrs: mustprogress nofree norecurse nounwind willreturn writeonly uwtable
define dso_local noundef i32 @main() local_unnamed_addr #0 {
entry:
%conv = fpext double 0x7FEFFFFFFFFFFFFF to fp128
%conv2 = fpext double 0x10000000000000 to fp128
%sub = fsub fp128 %conv, %conv2
%add = fadd fp128 %sub, 0xL00000000000000003FFF000000000000
%call.i = call fp128 @logl(fp128 noundef %add) #2
%call.i7 = call fp128 @logl(fp128 noundef 0xL00000000000000004000000000000000) #2
%div = fdiv fp128 %call.i, %call.i7
%conv5 = fptoui fp128 %div to i64
%conv6 = trunc i64 %conv5 to i32
ret i32 %conv6
}
*** IR Dump After EarlyCSEPass on main ***
; Function Attrs: mustprogress nofree norecurse nounwind willreturn writeonly uwtable
define dso_local noundef i32 @main() local_unnamed_addr #0 {
entry:
%call.i = call fp128 @logl(fp128 noundef 0xLF00000000000000043FEFFFFFFFFFFFF) #2
%call.i7 = call fp128 @logl(fp128 noundef 0xL00000000000000004000000000000000) #2
%div = fdiv fp128 %call.i, %call.i7
%conv5 = fptoui fp128 %div to i64
%conv6 = trunc i64 %conv5 to i32
ret i32 %conv6
}
LLVM IRではlong double型はfp128になりますので、やはりlong doubleでのstd::log関数が定数化出来ていないようです。LLVM IRだとlong double型のstd::log関数はloglに置き換わっているようです。おそらくこのloglに対する定数最適化処理がないと思われます。
とりあえず、定数化をしている最適化パスが特定出来たので、そのパスで起きているデバッグ用ログを確認してみます。そのためには以下のオプションをつけてコンパイルします。これもデバッグビルドしたclang/LLVMでのみ有効になるオプションです。
- -mllvm -debug-only=early-cse
見てみると、あまり情報を出力してくれなかったですが、logl関数の手前までは定数化を行ってくれていそうといことだけは分かりました。
EarlyCSE Simplify: %conv = fpext double 0x7FEFFFFFFFFFFFFF to fp128 to: fp128 0xLF00000000000000043FEFFFFFFFFFFFF
EarlyCSE Simplify: %conv2 = fpext double 0x10000000000000 to fp128 to: fp128 0xL00000000000000003C01000000000000
EarlyCSE Simplify: %sub = fsub fp128 0xLF00000000000000043FEFFFFFFFFFFFF, 0xL00000000000000003C01000000000000 to: fp128 0xLF00000000000000043FEFFFFFFFFFFFF
EarlyCSE Simplify: %add = fadd fp128 0xLF00000000000000043FEFFFFFFFFFFFF, 0xL00000000000000003FFF000000000000 to: fp128 0xLF00000000000000043FEFFFFFFFFFFFF
EarlyCSEPass のどこに問題があるのか?
ここから先はLLVMのソースを見ていく必要があります。ざっと確認した結果、少なくともlong double型を引数にとる数学関数に対する定数畳み込み処理がごっそり抜けていることが分かりました。このあたりを追加すれば、今回のlong double型の定数最適化も問題なくなると思われます。
LLVMとして修正するには、おそらく今回の問題となったlogl関数だけでなくlong double型を引数に取るような数学関数全般に対して修正をしていく展望を描いてからになると思います。修正すべき部分もそれなりにあるので工数的にもそれなりにありそうというのが今の感触になります。
LLVMコミュニティの動向
LLVMコミュニティは感知しているのかどうか気になり、LLVM Discource で検索したところ以下見つけました。
今回の std::uniform_real_distribution についても以下のようなコメントを残されている方がいました。
std::uniform_real_distribution x;
LLVM emits two calls to logl() with constant arguments, a fdiv and a fptoui.
Libc++'s implementation is consumed and folded much more nicely by LLVM,
but at the moment anyone comparing LLVM and GCC will think that GCC is around 40% better
for some workloads.
LLVM Phabricatorでみたところ、long doubleに関する定数畳み込み処理の修正がいくつか取り込まれ、数件がレビュー中といったところで(私が見つけきれてないかもですが)、数学関数関連はまだ修正パッチがないようでした。
最後に
今回、他の方が検出したLLVMが遅いコードを生成する件について調べてきました。LLVMの原因箇所と思われる部分にまではたどり着けたと思います。調べ始めたときには原因の修正が簡単なものなら仮修正までしようと思っていましたが、簡単ではなさそうだったので断念しました。またLLVMに関するネタが出来たらなにか投稿しようと思います。