Clang C++コンパイラは関数内でデストラクタのある構造体が確保された場合スコープを区切っても末尾呼び出し最適化を行わない場合がある?

C++の規格には詳しくないのですが,本の虫: C++入門書で再帰について解説しようとしたら思わぬ最適化できないコードに出くわしたを読んで試してみました.

コンパイルコマンドはclang++ -std=c++17 -O2 tco.cpp.

これはsegmentation fault (core dumped)します.

これは1分ほど回してもsegvしません.

デストラクタで副作用のある関数が呼び出されることを考慮して破棄を後に回しているのでないでしょうか.

ここまではわかります.

では何故次はsegvするのでしょうか?

これは末尾呼び出しの前にスコープを抜けているのでデストラクタが呼び出されているので,破棄を先に回せるはずです.

clang++ -std=c++17 -O2 tco.cpp -c -S -emit-llvmでLLVM IRを吐き出して見てみましょう.(長いので記事内では省略)

LLVM IRを見ると,デストラクタがない構造体はそもそもインライン化によって消滅していることがわかりました.

そして以下はsegvしません.

それはそれとして,非inlineのスコープ区切り版の当該関数は以下のようなLLVM IRになります.

; Function Attrs: uwtable
define void @_Z9recursionv() local_unnamed_addr #3 {
  %1 = alloca %struct.raii, align 1
  %2 = getelementptr inbounds %struct.raii, %struct.raii* %1, i64 0, i32 0
  call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull %2) #2
  %3 = tail call dereferenceable(272) %"class.std::basic_ostream"* @_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l(%"class.std::basic_ostream"* nonnull dereferenceable(272) @_ZSt4cout, i8* nonnull getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0), i64 11)
  %4 = load i8*, i8** bitcast (%"class.std::basic_ostream"* @_ZSt4cout to i8**), align 8, !tbaa !2
  %5 = getelementptr i8, i8* %4, i64 -24
  %6 = bitcast i8* %5 to i64*
  %7 = load i64, i64* %6, align 8
  %8 = getelementptr inbounds i8, i8* bitcast (%"class.std::basic_ostream"* @_ZSt4cout to i8*), i64 %7
  %9 = getelementptr inbounds i8, i8* %8, i64 240
  %10 = bitcast i8* %9 to %"class.std::ctype"**
  %11 = load %"class.std::ctype"*, %"class.std::ctype"** %10, align 8, !tbaa !5
  %12 = icmp eq %"class.std::ctype"* %11, null
  br i1 %12, label %13, label %14

; <label>:13: ; preds = %0
  tail call void @_ZSt16__throw_bad_castv() #9
  unreachable

; <label>:14: ; preds = %0
  %15 = getelementptr inbounds %"class.std::ctype", %"class.std::ctype"* %11, i64 0, i32 8
  %16 = load i8, i8* %15, align 8, !tbaa !10
  %17 = icmp eq i8 %16, 0
  br i1 %17, label %21, label %18

; <label>:18: ; preds = %14
  %19 = getelementptr inbounds %"class.std::ctype", %"class.std::ctype"* %11, i64 0, i32 9, i64 10
  %20 = load i8, i8* %19, align 1, !tbaa !12
  br label %27

; <label>:21: ; preds = %14
  tail call void @_ZNKSt5ctypeIcE13_M_widen_initEv(%"class.std::ctype"* nonnull %11)
  %22 = bitcast %"class.std::ctype"* %11 to i8 (%"class.std::ctype"*, i8)***
  %23 = load i8 (%"class.std::ctype"*, i8)**, i8 (%"class.std::ctype"*, i8)*** %22, align 8, !tbaa !2
  %24 = getelementptr inbounds i8 (%"class.std::ctype"*, i8)*, i8 (%"class.std::ctype"*, i8)** %23, i64 6
  %25 = load i8 (%"class.std::ctype"*, i8)*, i8 (%"class.std::ctype"*, i8)** %24, align 8
  %26 = tail call signext i8 %25(%"class.std::ctype"* nonnull %11, i8 signext 10)
  br label %27

; <label>:27: ; preds = %18, %21
  %28 = phi i8 [ %20, %18 ], [ %26, %21 ]
  %29 = tail call dereferenceable(272) %"class.std::basic_ostream"* @_ZNSo3putEc(%"class.std::basic_ostream"* nonnull @_ZSt4cout, i8 signext %28)
  %30 = tail call dereferenceable(272) %"class.std::basic_ostream"* @_ZNSo5flushEv(%"class.std::basic_ostream"* nonnull %29)
  call void @_ZN4raiiD2Ev(%struct.raii* nonnull %1) #2
  call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull %2) #2
  call void @_Z9recursionv()
  ret void
}

これを見ると,最後のcall void @_Z9recursionv()はtail callになっていないようですね.このLLVM IRを手入力で修正してtail call void @_Z9recursionv()に変換してclang++ -std=c++17 -O3 tco.llでコンパイルしてみましょう.

そうするとsegvしません.

よって原因はllvmレイヤーにあるのではなくclangレイヤーにあることがわかりました.

おそらく関数内にデストラクタのある型があるかどうかでtall callするかどうか切り替えているのではないでしょうか.

本当はclangのソースコードをちゃんと読んで判別したかったのですが,それを調べるには,私の昼休みは不足しています.

g++でも同じ結果になるけれど,同じようなアルゴリズムを使っているのですかね?

元記事のコメントにもデストラクタのパターンと末尾呼び出し最適化されるかのパターンが書かれていましたが,まるで意味が分からない.というか,NGパターンでもこちらの環境だと末尾呼び出し最適化されてsegvしなかったものがありました.

原理的にここを末尾呼び出し最適化してはいけない理由があるのでしょうかね.このパターンでは不明ですが…

このエントリーをはてなブックマークに追加 fb-like g-plusone pocket