[ThinLTO/LowerTypeTests] Handle unpromoted local type ids

[tejohnson]

Summary

Fixes an issue that cropped up after the changes in D73242 to delay
the lowering of type tests. LTT couldn't handle any type tests with
non-string type id (which happens for local vtables, which we try to
promote during the compile step but cannot always when there are no
exported symbols).

We can simply treat the same as having an Unknown resolution, which
delays their lowering, still allowing such type tests to be used in
subsequent optimization (e.g. planned usage during ICP). The final
lowering which simply removes these handles them fine.

Beefed up an existing ThinLTO test for such unpromoted type ids so that
the internal vtable isn't removed before lower type tests, which hides
the problem.

[aganea]

Tested & works. This patch fixes the issue initially reported here: https://reviews.llvm.org/D73242#1881924
Thanks @tejohnson !

[evgeny777]

I'm seeing crashes with this patch in two stage compilation, reported here: https://reviews.llvm.org/D73242#1893744. However the change seems reasonable, so I think it makes sense to push it and then investigate remaining issues. That said, LGTM

[evgeny777]

@tejohnson I think, I found the reason of crash, described in https://reviews.llvm.org/D73242#1893744. There is the following sequence of instructions in VirtualFileSystem.cpp.obj:

store i32 (...)** bitcast ({ [5 x i8*] }* @"??_7RealFile@?A0x1AE555D7@@6B@" to i32 (...)**), i32 (...)*** %1, align 8, !dbg !36936, !tbaa !15844
...
%3 = tail call i1 @llvm.type.test(i8* bitcast ({ [5 x i8*] }* @"??_7RealFile@?A0x1AE555D7@@6B@" to i8*), metadata !"1$f8264c715b0bffc7d68899cd8e73067d") #8, !dbg !36937
tail call void @llvm.assume(i1 %3) #8, !dbg !36937

The only users of VTable ??_7RealFile@?A0x1AE555D7@@6B@ are store instructions which is not reflected in summary index. This causes type.test not being eliminated during WPD and then lowering to false during LTT. So far we get unreachable in the linked image.

[aganea]

Shouldn't we add -D[CMAKE_C_FLAGS|CMAKE_CXX_FLAGS]="-fwhole-program-vtables" , or better -O3 -fwhole-program-vtables -fstrict-aliasing on the ThinLTO bots, on stage 3 & 4, so we can catch these issues?

[evgeny777]

Not sure about strict aliasing, but adding -fwhole-program-vtables seems like a good idea. I'd also add -flto-visibility-public-std.

[tejohnson]

In D75201#1901135, @evgeny777 wrote:

Thanks for tracking this down! I haven't reproduced yet, can you send me the bitcode file while I continue to try to repro? A couple questions below.

@tejohnson I think, I found the reason of crash, described in https://reviews.llvm.org/D73242#1893744. There is the following sequence of instructions in VirtualFileSystem.cpp.obj:

store i32 (...)** bitcast ({ [5 x i8*] }* @"??_7RealFile@?A0x1AE555D7@@6B@" to i32 (...)**), i32 (...)*** %1, align 8, !dbg !36936, !tbaa !15844
...
%3 = tail call i1 @llvm.type.test(i8* bitcast ({ [5 x i8*] }* @"??_7RealFile@?A0x1AE555D7@@6B@" to i8*), metadata !"1$f8264c715b0bffc7d68899cd8e73067d") #8, !dbg !36937
tail call void @llvm.assume(i1 %3) #8, !dbg !36937

The only users of VTable ??_7RealFile@?A0x1AE555D7@@6B@ are store instructions which is not reflected in summary index.

There should be a summary reference of this vtable on the function with the store. But I'm not sure how that helps with this:

This causes type.test not being eliminated during WPD and then lowering to false during LTT.

We would not eliminate in WPD only if its Type ID ("1$f8264c715b0bffc7d68899cd8e73067d") has a use on type metadata, in which case it should presumably not be Unsat in LTT.

So far we get unreachable in the linked image.

This should happen if the type ID has no use on type metadata, but then I think it should be removed by WPD.

[tejohnson]

In D75201#1901184, @aganea wrote:

Shouldn't we add -D[CMAKE_C_FLAGS|CMAKE_CXX_FLAGS]="-fwhole-program-vtables" , or better -O3 -fwhole-program-vtables -fstrict-aliasing on the ThinLTO bots, on stage 3 & 4, so we can catch these issues?

That's a good idea to add -fwhole-program-vtables. I will see if I can contact some of the ThinLTO bot owners about adding this.

[evgeny777]

@tejohnson

This should happen if the type ID has no use on type metadata, but then I think it should be removed by WPD.

It can't be removed or otherwise handled by WPD, because WPD doesn't even see this type.test (it doesn't exist in the index). The problem is
in the analysis phase of thin LTO compilation. I suggest you take a look at findDevirtualizableCallsForTypeTest function and then at
findLoadCallsAtConstantOffset. The latter can process three kind of vptr users: bitcast, load and gep. It can't process store with constant
expression. So far we don't reflect this type.test in summary index and WPD doesn't see it at all.

Here is an object file

v2.bc2 MBDownload

I'm using the following command to compile

lld-link  /dll v2.bc /out:a.dll /force:unresolved /nodefaultlib /lldsavetemps

Check ??_GRealFile@?A0x1AE555D7@@UEAAPEAXI@Z function in temps.

[aganea]

Just FYI, I'm also getting the following crash when doing ninja check-clang with the repro specified in: https://reviews.llvm.org/D73242#1881924
It appeared at about the same time as the bug described by Eugene above (it is probably the same thing).
This happens on many clang tests. I am at latest trunk.

 #0 0x00007ff67be7f2d1 clang::interp::ExprScope<class clang::interp::ByteCodeEmitter>::`scalar deleting dtor'(unsigned int) (d:\llvm-project\buildninjarelrpmalloc\bin\clang.exe+0x1f2d1)
 #1 0x00007ff67d8c9301 clang::SrcMgr::ContentCache::getBuffer(class clang::DiagnosticsEngine &, class clang::FileManager &, class clang::SourceLocation, bool *) const D:\llvm-project\clang\lib\Basic\SourceManager.cpp:172:0
 #2 0x00007ff67ee6f570 clang::SourceManager::getBuffer(class clang::FileID, class clang::SourceLocation, bool *) const D:\llvm-project\clang\include\clang\Basic\SourceManager.h:995:0
 #3 0x00007ff67ee6ee27 clang::Preprocessor::EnterSourceFile(class clang::FileID, class clang::DirectoryLookup const *, class clang::SourceLocation) D:\llvm-project\clang\lib\Lex\PPLexerChange.cpp:81:0
 #4 0x00007ff67dafc03d clang::Preprocessor::EnterMainSourceFile(void) D:\llvm-project\clang\lib\Lex\Preprocessor.cpp:551:0
 #5 0x00007ff67f4b9f15 clang::ParseAST(class clang::Sema &, bool, bool) D:\llvm-project\clang\lib\Parse\ParseAST.cpp:144:0
 #6 0x00007ff67dbe226c clang::FrontendAction::Execute(void) D:\llvm-project\clang\lib\Frontend\FrontendAction.cpp:944:0
 #7 0x00007ff67c6e6130 clang::CompilerInstance::ExecuteAction(class clang::FrontendAction &) D:\llvm-project\clang\lib\Frontend\CompilerInstance.cpp:969:0
 #8 0x00007ff67c74272d clang::ExecuteCompilerInvocation(class clang::CompilerInstance *) D:\llvm-project\clang\lib\FrontendTool\ExecuteCompilerInvocation.cpp:292:0
 #9 0x00007ff67be67f74 cc1_main(class llvm::ArrayRef<char const *>, char const *, void *) D:\llvm-project\clang\tools\driver\cc1_main.cpp:240:0
#10 0x00007ff67be64f4d ExecuteCC1Tool D:\llvm-project\clang\tools\driver\driver.cpp:328:0
#11 0x00007ff67be61d1d main D:\llvm-project\clang\tools\driver\driver.cpp:402:0
#12 0x00007ff680886ae8 __scrt_common_main_seh d:\agent\_work\5\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:288:0
#13 0x00007ffa95737bd4 (C:\WINDOWS\System32\KERNEL32.DLL+0x17bd4)
#14 0x00007ffa972eced1 (C:\WINDOWS\SYSTEM32\ntdll.dll+0x6ced1)

[tejohnson]

Thanks for the reproducer!

In D75201#1901357, @evgeny777 wrote:

@tejohnson

This should happen if the type ID has no use on type metadata, but then I think it should be removed by WPD.

It can't be removed or otherwise handled by WPD, because WPD doesn't even see this type.test (it doesn't exist in the index). The problem is
in the analysis phase of thin LTO compilation. I suggest you take a look at findDevirtualizableCallsForTypeTest function and then at
findLoadCallsAtConstantOffset. The latter can process three kind of vptr users: bitcast, load and gep. It can't process store with constant
expression. So far we don't reflect this type.test in summary index and WPD doesn't see it at all.

Ah ok - I misunderstood what reference you were talking about. Even if findDevirtualizableCallsForTypeTest and its descendants could process the reference on the store, it wouldn't automatically help since we are ultimately only looking for uses on virtual calls for devirtualization. And in this case there is no call. As a result WPD does not create a WPDResolution (which defaults to Unknown resolution), and therefore when we import the type id in LTT it appears Unsat.

I think if I expanded findLoadCallsAtConstantOffset to mark all other uses as HasNonCallUses, and when true added the type test to the list of summarized type tests (similar to the way findDevirtualizableCallsForTypeCheckedLoad and its caller in ModuleSummaryAnalysis.cpp behaves for non-call uses), then that might be enough to provoke the correct behavior from LTT.

Hmm, nope that isn't enough to fix it. I tested this change, rebuilt the index by disassembling v2.bc, manually stripping the index, and rebuilding it via "opt -module-summary". Disassembled again and confirmed that the enclosing function's summary now has a type test summary for it. Re-did the link but still see the unreachable in the function after optimization.

This needs more thought and investigation, so at this point I am going to revert the first patch and this follow on one so I can unblock your builds. I may have to table this work for a couple weeks in any case.

Here is an object file

v2.bc2 MBDownload

I'm using the following command to compile

lld-link  /dll v2.bc /out:a.dll /force:unresolved /nodefaultlib /lldsavetemps

Check ??_GRealFile@?A0x1AE555D7@@UEAAPEAXI@Z function in temps.

[tejohnson]

Reverted in 80bf137fa132ea33204e98bbefa924afe9258a4e

[tejohnson]

In D75201#1901704, @tejohnson wrote:

Thanks for the reproducer!

In D75201#1901357, @evgeny777 wrote:

@tejohnson

This should happen if the type ID has no use on type metadata, but then I think it should be removed by WPD.

It can't be removed or otherwise handled by WPD, because WPD doesn't even see this type.test (it doesn't exist in the index). The problem is
in the analysis phase of thin LTO compilation. I suggest you take a look at findDevirtualizableCallsForTypeTest function and then at
findLoadCallsAtConstantOffset. The latter can process three kind of vptr users: bitcast, load and gep. It can't process store with constant
expression. So far we don't reflect this type.test in summary index and WPD doesn't see it at all.

Ah ok - I misunderstood what reference you were talking about. Even if findDevirtualizableCallsForTypeTest and its descendants could process the reference on the store, it wouldn't automatically help since we are ultimately only looking for uses on virtual calls for devirtualization. And in this case there is no call. As a result WPD does not create a WPDResolution (which defaults to Unknown resolution), and therefore when we import the type id in LTT it appears Unsat.

I think if I expanded findLoadCallsAtConstantOffset to mark all other uses as HasNonCallUses, and when true added the type test to the list of summarized type tests (similar to the way findDevirtualizableCallsForTypeCheckedLoad and its caller in ModuleSummaryAnalysis.cpp behaves for non-call uses), then that might be enough to provoke the correct behavior from LTT.

Hmm, nope that isn't enough to fix it. I tested this change, rebuilt the index by disassembling v2.bc, manually stripping the index, and rebuilding it via "opt -module-summary". Disassembled again and confirmed that the enclosing function's summary now has a type test summary for it. Re-did the link but still see the unreachable in the function after optimization.

This needs more thought and investigation, so at this point I am going to revert the first patch and this follow on one so I can unblock your builds. I may have to table this work for a couple weeks in any case.

I finally had a chance to revisit this, and the solution is pretty straightforward. During WPD when we consider whether to remove the type test assume sequence (which was unconditional before this patch), we should remove them whenever we know that LTT will not get a proper resolution and think they are Unsat. With the earlier version of this patch, I was continuing to remove those sequences when there was no global with the type id, and with the new fixed version of the patch, that is extended to also remove if we are importing and there is no TypeIdSummary resolution, which means there was no vcall (and in that case it isn't useful for later analysis in ICP anyway).

BTW I was able to reproduce this failure (in the same file) on a 2-stage linux self build and test. With the new version of the patch this works correctly with no test failures. I will upload the new version of the patch to D73242, ptal. It includes a test for this situation.

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

 }
 
 void LowerTypeTestsModule::importTypeTest(CallInst *CI) {
   auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
   if (!TypeIdMDVal)
     report_fatal_error("Second argument of llvm.type.test must be metadata");
 
   auto TypeIdStr = dyn_cast<MDString>(TypeIdMDVal->getMetadata());
+  // If this is a local unpromoted type, which doesn't have a metadata string,
+  // treat as Unknown and delay lowering, so that we can still utilize it for
+  // later optimizations.
   if (!TypeIdStr)
-    report_fatal_error(
-        "Second argument of llvm.type.test must be a metadata string");
+    return;
 
   TypeIdLowering TIL = importTypeId(TypeIdStr->getString());
   Value *Lowered = lowerTypeTestCall(TypeIdStr, CI, TIL);
   if (Lowered) {
     CI->replaceAllUsesWith(Lowered);
     CI->eraseFromParent();
   }
 }

llvm/test/ThinLTO/X86/nodevirt-nonpromoted-typeid.ll

 ; RUN:   -o %t3 \
 ; RUN:   -r=%t2.o,test,plx \
 ; RUN:   -r=%t2.o,_ZN1D1mEi,
 ; RUN: llvm-dis %t3.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
 
 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-grtev4-linux-gnu"
 
[e-mail]_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @g, i8* null }]
+
 %struct.D = type { i32 (...)** }
 
 @_ZTV1D = internal constant { [3 x i8*] } { [3 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.D*, i32)* @_ZN1D1mEi to i8*)] }, !type !3
 
 ; CHECK-IR-LABEL: define weak_odr dso_local i32 @test
 define weak_odr i32 @test(%struct.D* %obj2, i32 %a) {
 entry:
   %0 = bitcast %struct.D* %obj2 to i8***
   %vtable2 = load i8**, i8*** %0
   %1 = bitcast i8** %vtable2 to i8*
   %p2 = call i1 @llvm.type.test(i8* %1, metadata !4)
   call void @llvm.assume(i1 %p2)
 
   %2 = bitcast i8** %vtable2 to i32 (%struct.D*, i32)**
   %fptr33 = load i32 (%struct.D*, i32)*, i32 (%struct.D*, i32)** %2, align 8
 
   ; Check that the call was not devirtualized.
   ; CHECK-IR: %call4 = tail call i32 %fptr33
   %call4 = tail call i32 %fptr33(%struct.D* nonnull %obj2, i32 0)
   ret i32 %call4
 }
 ; CHECK-IR-LABEL: ret i32
 ; CHECK-IR-LABEL: }
 
+; Function Attrs: inlinehint nounwind uwtable
+define internal void @_ZN1DC2Ev(%struct.D* %this) unnamed_addr align 2 {
+entry:
+  %this.addr = alloca %struct.D*, align 8
+  store %struct.D* %this, %struct.D** %this.addr, align 8
+  %this1 = load %struct.D*, %struct.D** %this.addr
+  %0 = bitcast %struct.D* %this1 to i32 (...)***
+  store i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*] }, { [3 x i8*] }* @_ZTV1D, i64 0, inrange i32 0, i64 2) to i32 (...)**), i32 (...)*** %0, align 8
+  ret void
+}
+
+define internal void @g() section ".text.startup" {
+  %d = alloca %struct.D, align 8
+  call void @_ZN1DC2Ev(%struct.D* %d)
+  ret void
+}
+
 declare i1 @llvm.type.test(i8*, metadata)
 declare void @llvm.assume(i1)
 
 declare i32 @_ZN1D1mEi(%struct.D* %this, i32 %a)
 
 !3 = !{i64 16, !4}
 !4 = distinct !{}