LLVMのstd::uniform_real_distributionが遅い件のLLVM観点の原因を探ってみた

# はじめに

興味があったので以下の件についてLLVMの観点で原因を探ってみました。

https://qiita.com/k_nitadori/items/49490cc17a8ee89523b7

以下、デバッグビルドしたLLVM15.0.7を使ってみていきます。

## "std::uniform_real_distributionが遅い件"で問題とされた部分

```C++
        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()`となっているので、そのように置き換えます。

### 整形したコードによる結果確認。
```C++
#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)でコンパイルすると以下のような問題とされたアセンブリコードと同様のコードが生成されます。

```armasm: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)でコンパイルすると以下のような定数を返すアセンブリコードとなります。

```armasm:g++-12 -O3時のアセンブリコード
main:
.LFB981:  
        mov     w0, 1023
        ret
```
これをみると元記事にもあったとおりLLVMの定数最適化に問題がありそうです。

## 定数最適化を阻害している要因はなにか?

定数最適化を阻害している要因は何でしょうか。以下コードのように`std::log`関数の引数の型を`double`型した場合はどうでしょうか。

```c++
#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;                                                                              
}                                                                                              
```
以下のように置き換えた場合は、定数化されることが分かります。
```armasm:clang++ -O3時のアセンブリコード
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`型にキャストしたコードについて見ていきます。

```llvm: 定数化出来ている(double型にキャストした)コードのLLVM IRのログ
*** 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`型のコードの場合はどうでしょうか。

```llvm: 定数化できない(long double型のままの)コードのLLVM IRのログ
*** 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 で検索したところ以下見つけました。

https://discourse.llvm.org/t/rfc-constant-folding-math-functions-for-long-double/40598

今回の `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に関するネタが出来たらなにか投稿しようと思います。