[WPD/LTT] Lower type test feeding assumes via phi correctly

[tejohnson]

Summary

This fixes https://github.com/llvm/llvm-project/issues/57616.

Type test lowering in ThinLTO modules relies on having type id
summaries set up for the referenced types, which provide the type
test resolution. If there is no summary, the type tests are lowered
to false. At the very least, a default type id summary gives the
type tests a resolution of Unknown, which is handled correctly (ignored
by the first invocation of LTT, and lowered to true by the second).

WPD sets up the type id summaries (with a default type test resolution)
as it is processing the type tests, but only does this for the patterns
handled by WPD, which is a type test directly feeding an assume. In the
case of type tests feeding an assume via a phi, the type id summary was
not being set up, leading to the type tests being lowered to false
incorrectly.

Fix this by adding the default type id summary entries for all type ids
used on globals during index-only WPD.

This is not an issue for hybrid (split-lto-unit) LTO, as in that case
the type test resolution is determined and set up during LTT, since the
type definitions are in the regular LTO split module, and exported via
the summary to the ThinLTO split module.

[aeubanks]

thanks for the quick turnaround!

llvm/test/ThinLTO/X86/lower_type_test_phi.ll

51

can you simplify the IR? e.g. remove hidden, noundef, tbaa metadata, etc

[aeubanks]

verified that this fixes the issue we're seeing

[tejohnson]

Simplify test case and fix comment typo

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

 
 void DevirtIndex::run() {
   if (ExportSummary.typeIdCompatibleVtableMap().empty())
     return;
 
   DenseMap<GlobalValue::GUID, std::vector<StringRef>> NameByGUID;
   for (const auto &P : ExportSummary.typeIdCompatibleVtableMap()) {
     NameByGUID[GlobalValue::getGUID(P.first)].push_back(P.first);
+    // Create the type id summary resolution regardlness of whether we can
+    // devirtualize, so that lower type tests knows the type id is used on
+    // a global and not Unsat. We do this here rather than in the loop over the
+    // CallSlots, since we that handling will only see type tests that directly
+    // feed assumes, and we would miss any that aren't currently handled by WPD
+    // (such as type tests that feed assumes via phis).
+    ExportSummary.getOrInsertTypeIdSummary(P.first);
   }
 
   // Collect information from summary about which calls to try to devirtualize.
   for (auto &P : ExportSummary) {
     for (auto &S : P.second.SummaryList) {
       auto *FS = dyn_cast<FunctionSummary>(S.get());
       if (!FS)
         continue;
void DevirtIndex::run() {
   // For each (type, offset) pair:
   for (auto &S : CallSlots) {
     // Search each of the members of the type identifier for the virtual
     // function implementation at offset S.first.ByteOffset, and add to
     // TargetsForSlot.
     std::vector<ValueInfo> TargetsForSlot;
     auto TidSummary = ExportSummary.getTypeIdCompatibleVtableSummary(S.first.TypeID);
     assert(TidSummary);
-    // Create the type id summary resolution regardlness of whether we can
-    // devirtualize, so that lower type tests knows the type id is used on
-    // a global and not Unsat.
+    // The type id summary would have been created while building the NameByGUID
+    // map earlier.
     WholeProgramDevirtResolution *Res =
-        &ExportSummary.getOrInsertTypeIdSummary(S.first.TypeID)
-             .WPDRes[S.first.ByteOffset];
+        &ExportSummary.getTypeIdSummary(S.first.TypeID)
+             ->WPDRes[S.first.ByteOffset];
     if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary,
                                   S.first.ByteOffset)) {
 
       if (!trySingleImplDevirt(TargetsForSlot, S.first, S.second, Res,
                                DevirtTargets))
         continue;
     }
   }

llvm/test/ThinLTO/X86/lower_type_test_phi.ll

+; Test to ensure that type tests feeding assumes via a phi are lowered
+; correctly after ThinLTO index-only WPD, which needs to set up the necessary
+; type id summaries.
+
+; RUN: rm -rf %t && split-file %s %t && cd %t
+
+; RUN: opt -thinlto-bc y.ll -o y.bc
+; RUN: opt -thinlto-bc z.ll -o z.bc
+
+; RUN: llvm-lto2 run y.bc z.bc -o out \
+; RUN:  -r y.bc,main,plx \
+; RUN:  -r y.bc,_Z2b1v, \
+; RUN:  -r y.bc,_Z2b2v, \
+; RUN:  -r z.bc,_Z2b1v,pl \
+; RUN:  -r z.bc,_Znwm, \
+; RUN:  -r z.bc,_Z2b2v,pl \
+; RUN:  -r z.bc,_ZN2D11fEv,pl \
+; RUN:  -r z.bc,_ZN1B1fEv,pl \
+; RUN:  -r z.bc,_ZN2D21fEv,pl \
+; RUN:  -r z.bc,_ZTV2D1,pl \
+; RUN:  -r z.bc,_ZTV1B,pl \
+; RUN:  -r z.bc,_ZTV2D2,pl \
+; RUN:  -print-after=lowertypetests -filter-print-funcs=main 2>&1 | FileCheck %s
+
+; The first LTT should leave the type tests as is (instead of lowering
+; them to false incorrectly).
+; CHECK: *** IR Dump After LowerTypeTestsPass on [module] ***
+; CHECK: 4:
+; CHECK:   %7 = tail call i1 @llvm.type.test(ptr %6, metadata !"_ZTS2D1")
+; CHECK:   br label %12
+; CHECK: 8:
+; CHECK:   %11 = tail call i1 @llvm.type.test(ptr %10, metadata !"_ZTS2D2")
+; CHECK:   br label %12
+; CHECK: 12:
+; CHECK:   %13 = phi i1 [ %11, %8 ], [ %7, %4 ]
+
+; The second LTT should lower them to true.
+; CHECK: *** IR Dump After LowerTypeTestsPass on [module] ***
+; CHECK-NOT: @llvm.type.test
+; CHECK: 10:
+; CHECK:   %11 = phi i1 [ true, %7 ], [ true, %4 ]
+
+
+;--- y.ll
+; ModuleID = 'y.cc'
+source_filename = "y.cc"
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: mustprogress norecurse uwtable
+define hidden noundef i32 @main(i32 noundef %argc, ptr nocapture noundef readnone %argv) local_unnamed_addr #0 {
+entry:
+  %tobool.not = icmp eq i32 %argc, 0
+  br i1 %tobool.not, label %if.else, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call noundef ptr @_Z2b1v()
+  %vtable = load ptr, ptr %call, align 8, !tbaa !6
+  %0 = tail call i1 @llvm.type.test(ptr %vtable, metadata !"_ZTS2D1")
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %call1 = tail call noundef ptr @_Z2b2v()
+  %vtable2 = load ptr, ptr %call1, align 8, !tbaa !6
+  %1 = tail call i1 @llvm.type.test(ptr %vtable2, metadata !"_ZTS2D2")
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %.sink = phi i1 [ %1, %if.else ], [ %0, %if.then ]
+  %vtable2.sink = phi ptr [ %vtable2, %if.else ], [ %vtable, %if.then ]
+  %call1.sink = phi ptr [ %call1, %if.else ], [ %call, %if.then ]
+  tail call void @llvm.assume(i1 %.sink)
+  %2 = load ptr, ptr %vtable2.sink, align 8
+  tail call void %2(ptr noundef nonnull align 8 dereferenceable(8) %call1.sink)
+  ret i32 0
+}
+
+declare noundef ptr @_Z2b1v() local_unnamed_addr #1
+
+; Function Attrs: mustprogress nocallback nofree nosync nounwind readnone speculatable willreturn
+declare i1 @llvm.type.test(ptr, metadata) #2
+
+; Function Attrs: inaccessiblememonly mustprogress nocallback nofree nosync nounwind willreturn
+declare void @llvm.assume(i1 noundef) #3
+
+declare noundef ptr @_Z2b2v() local_unnamed_addr #1
+
+attributes #0 = { mustprogress norecurse uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+attributes #1 = { "frame-pointer"="none" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+attributes #2 = { mustprogress nocallback nofree nosync nounwind readnone speculatable willreturn }
+attributes #3 = { inaccessiblememonly mustprogress nocallback nofree nosync nounwind willreturn }
+
+!llvm.module.flags = !{!0, !1, !2, !3, !4}
+!llvm.ident = !{!5}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{i32 1, !"Virtual Function Elim", i32 0}
+!2 = !{i32 7, !"PIC Level", i32 2}
+!3 = !{i32 7, !"PIE Level", i32 2}
+!4 = !{i32 7, !"uwtable", i32 2}
+!5 = !{!"clang version 15.0.0 ([e-mail]:llvm/llvm-project.git e6f39e3f31ba88f2084a5d987f9a827aff4e17b1)"}
+!6 = !{!7, !7, i64 0}
+!7 = !{!"vtable pointer", !8, i64 0}
+!8 = !{!"Simple C++ TBAA"}
+
+;--- z.ll
+; ModuleID = 'z.cc'
+source_filename = "z.cc"
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+$_ZN2D11fEv = comdat any
+
+$_ZN1B1fEv = comdat any
+
+$_ZN2D21fEv = comdat any
+
+$_ZTV2D1 = comdat any
+
+$_ZTV1B = comdat any
+
+$_ZTV2D2 = comdat any
+
+@_ZTV2D1 = linkonce_odr hidden unnamed_addr constant { [3 x ptr] } { [3 x ptr] [ptr null, ptr null, ptr @_ZN2D11fEv] }, comdat, align 8, !type !0, !type !1, !type !2, !type !3, !vcall_visibility !4
+@_ZTV1B = linkonce_odr hidden unnamed_addr constant { [3 x ptr] } { [3 x ptr] [ptr null, ptr null, ptr @_ZN1B1fEv] }, comdat, align 8, !type !0, !type !1, !vcall_visibility !4
+@_ZTV2D2 = linkonce_odr hidden unnamed_addr constant { [3 x ptr] } { [3 x ptr] [ptr null, ptr null, ptr @_ZN2D21fEv] }, comdat, align 8, !type !0, !type !1, !type !5, !type !6, !vcall_visibility !4
+
+; Function Attrs: uwtable
+define hidden noalias noundef nonnull ptr @_Z2b1v() local_unnamed_addr #0 {
+entry:
+  %call = tail call noalias noundef nonnull dereferenceable(8) ptr @_Znwm(i64 noundef 8) #3
+  store ptr getelementptr inbounds ({ [3 x ptr] }, ptr @_ZTV2D1, i64 0, inrange i32 0, i64 2), ptr %call, align 8, !tbaa !13
+  ret ptr %call
+}
+
+; Function Attrs: nobuiltin allocsize(0)
+declare noundef nonnull ptr @_Znwm(i64 noundef) local_unnamed_addr #1
+
+; Function Attrs: uwtable
+define hidden noalias noundef nonnull ptr @_Z2b2v() local_unnamed_addr #0 {
+entry:
+  %call = tail call noalias noundef nonnull dereferenceable(8) ptr @_Znwm(i64 noundef 8) #3
+  store ptr getelementptr inbounds ({ [3 x ptr] }, ptr @_ZTV2D2, i64 0, inrange i32 0, i64 2), ptr %call, align 8, !tbaa !13
+  ret ptr %call
+}
+
+; Function Attrs: mustprogress nounwind uwtable
+define linkonce_odr hidden void @_ZN2D11fEv(ptr noundef nonnull align 8 dereferenceable(8) %this) unnamed_addr #2 comdat align 2 {
+entry:
+  ret void
+}
+
+; Function Attrs: mustprogress nounwind uwtable
+define linkonce_odr hidden void @_ZN1B1fEv(ptr noundef nonnull align 8 dereferenceable(8) %this) unnamed_addr #2 comdat align 2 {
+entry:
+  ret void
+}
+
+; Function Attrs: mustprogress nounwind uwtable
+define linkonce_odr hidden void @_ZN2D21fEv(ptr noundef nonnull align 8 dereferenceable(8) %this) unnamed_addr #2 comdat align 2 {
+entry:
+  ret void
+}
+
+attributes #0 = { uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+attributes #1 = { nobuiltin allocsize(0) "frame-pointer"="none" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+attributes #2 = { mustprogress nounwind uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+attributes #3 = { builtin allocsize(0) }
+
+!llvm.module.flags = !{!7, !8, !9, !10, !11}
+!llvm.ident = !{!12}
+
+!0 = !{i64 16, !"_ZTS1B"}
+!1 = !{i64 16, !"_ZTSM1BFvvE.virtual"}
+!2 = !{i64 16, !"_ZTS2D1"}
+!3 = !{i64 16, !"_ZTSM2D1FvvE.virtual"}
+!4 = !{i64 1}
+!5 = !{i64 16, !"_ZTS2D2"}
+!6 = !{i64 16, !"_ZTSM2D2FvvE.virtual"}
+!7 = !{i32 1, !"wchar_size", i32 4}
+!8 = !{i32 1, !"Virtual Function Elim", i32 0}
+!9 = !{i32 7, !"PIC Level", i32 2}
+!10 = !{i32 7, !"PIE Level", i32 2}
+!11 = !{i32 7, !"uwtable", i32 2}
+!12 = !{!"clang version 15.0.0 ([e-mail]:llvm/llvm-project.git e6f39e3f31ba88f2084a5d987f9a827aff4e17b1)"}
+!13 = !{!14, !14, i64 0}
+!14 = !{!"vtable pointer", !15, i64 0}
+!15 = !{!"Simple C++ TBAA"}