[WPD/LowerTypeTests] Delay lowering/removal of type tests until after ICP

[tejohnson]

Summary

Currently type test assume sequences inserted for devirtualization are
removed during WPD. This patch delays their removal until later in the
optimization pipeline. This is an enabler for upcoming enhancements to
indirect call promotion, for example streamlined promotion guard
sequences that compare against vtable address instead of the target
function, when there are small number of possible vtables (either
determined via WPD or by in-progress type profiling). We need the type
tests to correlate the callsites with the address point offset needed in
the compare sequence, and optionally to associated type summary info
computed during WPD.

This depends on work in D71913 to enable invocation of LowerTypeTests to
drop type test assume sequences, which will now be invoked following ICP
in the ThinLTO post-LTO link pipelines, and also after the existing
export phase LowerTypeTests invocation in regular LTO (which is already
after ICP). We cannot simply move the existing import phase
LowerTypeTests pass later in the ThinLTO post link pipelines, as the
comment in PassBuilder.cpp notes (it must run early because when
performing CFI other passes may disturb the sequences it looks for).

This necessitated adding a new type test resolution "Unknown" that we
can use on the type test assume sequences previously removed by WPD,
that we now want LTT to ignore.

Depends on D71913.

[tejohnson]

llvm/test/Transforms/WholeProgramDevirt/uniform-retval.ll

28

This change is to distinguish the indirect call here that should have been removed from the @llvm.type.test and @llvm.assume calls that are no longer removed at this point.

[evgeny777]

This is an enabler for upcoming enhancements to indirect call promotion, for example streamlined promotion guard sequences that compare against vtable address instead of the target function

Can you please describe the whole approach in more detail? At the moment ICP is capable to do (a sort of) devirtualization is replacing indirect vtbl call with sequence of function address comparisons and direct calls.
Are you going to speedup this by means of comparing vtable pointers instead of function pointers (thus eliminating a single load per each vtbl call) or there is also something else in mind? If that's true, what's the next
step? Make ICP pass analyze type test intrinsics?

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1695

This change seems to be unrelated

[tejohnson]

In D73242#1847051, @evgeny777 wrote:

This is an enabler for upcoming enhancements to indirect call promotion, for example streamlined promotion guard sequences that compare against vtable address instead of the target function

Can you please describe the whole approach in more detail? At the moment ICP is capable to do (a sort of) devirtualization is replacing indirect vtbl call with sequence of function address comparisons and direct calls.
Are you going to speedup this by means of comparing vtable pointers instead of function pointers (thus eliminating a single load per each vtbl call) or there is also something else in mind?

That's exactly what we want to do here. We found a relatively significant number of cycles are being spent on virtual function pointer loads in these sequences, and by doing a vtable comparison instead, that is moved off the critical path. I had prototyped something like this in ICP awhile back and found a speedup in an important app.

If that's true, what's the next
step? Make ICP pass analyze type test intrinsics?

There are a few ways to do the alternate ICP compare sequences, one is using statically available info from the vtable definitions in the module that utilize the profiled target. This relies on ThinLTO to import all the relevant vtable definitions. The other is to profile vtable addresses with FDO (not just the target function pointer) - I've got the type profiling implemented, but it needs some cleanup before I send for review. Both of these approaches need the type tests to determine the correct address point offset (the offset in the type test) to use in the compare sequence. And in both cases you want to trade off the number of comparisons needed for the two approaches to determine whether a vtable compare or a target function compare is better. I.e. if there are a lot of vtable definitions that utilize a hot target, it is likely better to do a single target function comparison.

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1695

It is needed to have the TypeId available outside this if statement (see the map check below).

[tejohnson]

In D73242#1849484, @tejohnson wrote:

Both of these approaches need the type tests to determine the correct address point offset (the offset in the type test) to use in the compare sequence.

I typed this too fast - the offset is in the type metadata, but we need the type tests to correlate them with the indirect call sites.

[evgeny777]

This patch is to be rebased against D73094

llvm/include/llvm/IR/ModuleSummaryIndex.h

830

I don't think such implicit conversion of Unsat to Unknown is good idea. I guess problem will arise for legacy index files: for those ByteArray resolution will become Unsat and so on. I suggest moving Unknown the end of the list and bumping index version respectively (parseTypeIdSummaryRecord doesn't verify TheKind).

llvm/lib/Passes/PassBuilder.cpp

1381

Can we get rid of two identical passes here (and in other places also)? For instance

MPM.addPass(LowerTypeTestsPass(ExportSummary, nullptr, true));

can both lower type metadata and do final cleanup.

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1713

I don't think, I understand this.
It looks like that if (a) we have type.test in the module and (b) we don't have vtable definition with corresponding type metadata in the same module then we'll remove type.test/assume sequence before even getting to ICP. This seems strange in the context of previous discussion because virtual function may be called in different module from one where vtable is defined, like so:

struct A { virtual int foo() { return 42; } };

// calls pA->foo
extern int callFoo(A *pA);
int main() { A a; return callFoo(&a); }

[tejohnson]

llvm/include/llvm/IR/ModuleSummaryIndex.h

830

Sounds like a good idea, will do.

llvm/lib/Passes/PassBuilder.cpp

1381

The problem is that currently under DropTypeTests=true, LTT will drop the type tests up front and return without doing any other lowering. Which is what we want in the already existing callers of LTT with DropTypeTests=true. Here, we want LTT to perform its usual lowering, and only afterwards do the dropping. We want to do this only during regular LTO, but unfortunately we can't just key off of the ExportSummary (e.g. drop at the start if ExportSummary is nullptr, and drop at the end if ExportSummary is non-nullptr), since in some cases here ExportSummary may be nullptr (i.e. regular LTO invoked via the old LTO API). So I would need to introduce another option to essentially say "drop them after lowering". I can certainly do this if you think it would be better (I was thinking about that before, but thought it might be more confusing). WDYT?

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1713

We will only be able to do ICP this way if we have the target vtable in the module (similar to how we currently can only do ICP if the target function is in the module). I anticipate doing something similar for vtable defs as to what we do for virtual functions, where a fake call edge is added to the summary based on the value profile results to ensure they are imported before the LTO backend ICP.

[evgeny777]

llvm/lib/Passes/PassBuilder.cpp

1381

So I would need to introduce another option to essentially say "drop them after lowering". I can certainly do this if you think it would be better (I was thinking about that before, but thought it might be more confusing). WDYT?

Ok, I see. I don't think having this another option is significantly better. So let's leave it as is for now

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1713

We will only be able to do ICP this way if we have the target vtable in the module (similar to how we currently can only do ICP if the target function is in the module).

I was thinking of slightly different approach: it seems you have required type information in combined index together with type name in the module, so you probably can add external declarations of required vtables (this may require promotion) to the module in the ICP pass and run ICP over them. Do you think this can work?

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1713

Possibly, but we'd still need to have type metadata on those vtable declarations, because the type metadata provides the address point offset which is needed in the comparison sequence.

[evgeny777]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1713

Possibly, but we'd still need to have type metadata on those vtable declarations, because the type metadata provides the address point offset which is needed in the comparison sequence.

I think it's stored in the index in VFuncId structures. Isn't it?

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1713

I think it's stored in the index in VFuncId structures. Isn't it?

No, that holds the offset from the address point to the virtual function within the vtable def, not the address point offset itself, which is what we need from the type metadata. But actually, we need both offsets:

Consider the following example:

class A {
   virtual void foo();
}

void bar(A *a) {
   a->foo();
}

The indirect call sequence will look like (not showing the type test for simplicity):

%0 = bitcast %class.A* %a to i32 (%class.A*)***
 %vtable = load i32 (%class.A*)**, i32 (%class.A*)*** %0
 %1 = load i32 (%class.A*)*, i32 (%class.A*)** %vtable
 %call = tail call i32 %1(%class.A* %a)

With type profiling we will profile the value of %vtable, and figure out that it is associated with the symbol for A's vtable (the profiling support uses symbol table info for this), which is:

@_ZTV1A = dso_local unnamed_addr constant { [3 x i8*] } { [3 x i8*] [i8* null, i8* bitcast ({ i8*, i8* }* @_ZTI1A to i8*), i8* bitcast (i32 (%class.A*)* @_ZN1A3fooEv to i8*)] }, align 8, !type !0

!0 = !{i64 16, !"_ZTS1A"}

When we promote the call using the vtable profile results, we need to add the address point offset (16) from the type metadata to the profiled result which will be the symbol @_ZTV1A, before comparing against %vtable.

We then need to look at the IR and compute the offset to the function address used there (0 in the above IR), and add it to the address point offset, resulting in 16 here, looking in the vtable def to see what function is at the combined offset (_ZN1A3fooEv here), so that we insert a direct call to that function.

For the address point offset, we only have it in the summary for index-only WPD (TypeIdCompatibleVtableMap). However, I don't want to restrict the ICP improvements to that build mode.

For the latter, the VFuncId does summarize the offsets, but we can compute it from the IR as I described above (it's the amount added to %vtable before loading the virtual function pointer) and don't need the summary. And in any case the VFuncId doesn't tell us which function is at the aggregate offset, we need the vtable def to tell us that (or the vTableFuncs array saved on the GlobalVarSummary, again only in index-only WPD mode).

Also, I believe we can support this type profiling based ICP in non-ThinLTO mode as well - with my recent changes to make WPD rely on vcall visibility info, we should be able to insert both the type tests and the type metadata into the code stream in non-ThinLTO mode. In that case, similar to the way ICP currently behaves for target functions, the def would have to happen to already be in the current module for the vtable compare promotion to be occur.

For the above reasons, I'd prefer to rely on the type metadata on vtable defs, with the defs imported as much as possible in ThinLTO mode.

[tejohnson]

Rebase and implement suggestion (move Unknown to end and bump index version)

[evgeny777]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1713

Okay, got it. One question: why do you insist on removing such type.test/assume sequences here, instead of simply ignoring them in ICP and eliminating them altogether in LowerTypeTests?

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1713

ICP isn't the issue, it is what will happen in LTT. Without any associated type metadata, as noted in my comment here, LTT will think they are Unsat and lower to false, which is incorrect and results in an llvm.assume(false) which will turn into an unreachable, resulting in runtime failures.

[evgeny777]

LGTM

[thakis]

This makes lld crash when linking chromium's base_unittests and probably does the same for most other binaries that use both thinlto and cfi: https://bugs.chromium.org/p/chromium/issues/detail?id=1049434

[tejohnson]

In D73242#1861111, @thakis wrote:

This makes lld crash when linking chromium's base_unittests and probably does the same for most other binaries that use both thinlto and cfi: https://bugs.chromium.org/p/chromium/issues/detail?id=1049434

Reverted at 25aa2eef993e17708889abf56ed1ffad5074a9f4. Will investigate using repro @thakis sent off patch.

[tejohnson]

In D73242#1861125, @tejohnson wrote:

In D73242#1861111, @thakis wrote:

This makes lld crash when linking chromium's base_unittests and probably does the same for most other binaries that use both thinlto and cfi: https://bugs.chromium.org/p/chromium/issues/detail?id=1049434

Reverted at 25aa2eef993e17708889abf56ed1ffad5074a9f4. Will investigate using repro @thakis sent off patch.

Recommitted with fix and additional test case at 80d0a137a5aba6998fadb764f1e11cb901aae233.

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1999

The fix needed for the Chromium issue was to guard the TypeIdSummary creation here by whether the TypeID exists in the TypeIdMap (which makes it match the comment in fact), as we don't want to create a summary if the type id is not used on a global (in which case it should in fact be Unsat). The equivalent code in the index-only WPD is essentially already guarded by that condition, because of the way the CallSlots are created (and in fact there is an assert in that code that we have a use on a vtable, i.e. that a TypeIdCompatibleVtableSummary is found for the TypeID).

[aganea]

There seems to be still an issue with this patch, when linking the LLVM unit tests on a two-stage build, it ends with:

FAILED: tools/clang/unittests/StaticAnalyzer/StaticAnalysisTests.exe
cmd.exe /C "cd . && "C:\Program Files\CMake\bin\cmake.exe" -E vs_link_exe --intdir=tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir --rc=C:\PROGRA~2\WI3CF2~1\10\bin\100183~1.0\x64\rc.exe --mt=C:\PROGRA~2\WI3CF2~1\10\bin\100183~1.0\x64\mt.exe --manifests  -- D:\llvm-project\buildninjaRel\bin\lld-link.exe /nologo tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\AnalyzerOptionsTest.cpp.obj tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\CallDescriptionTest.cpp.obj tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\StoreTest.cpp.obj tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\RegisterCustomCheckersTest.cpp.obj tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\SymbolReaperTest.cpp.obj tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\D_\llvm-project\llvm\resources\windows_version_resource.rc.res  /out:tools\clang\unittests\StaticAnalyzer\StaticAnalysisTests.exe /implib:tools\clang\unittests\StaticAnalyzer\StaticAnalysisTests.lib /pdb:tools\clang\unittests\StaticAnalyzer\StaticAnalysisTests.pdb /version:0.0  /machine:x64 -fuse-ld=lld /STACK:10000000 /DEBUG /OPT:REF /OPT:ICF /lldltocache:D:/llvm-project/buildninjaRelMiMalloc/lto.cache /INCREMENTAL:NO /subsystem:console  lib\LLVMSupport.lib  lib\LLVMSupport.lib  lib\gtest_main.lib  lib\gtest.lib  lib\clangBasic.lib  lib\clangAnalysis.lib  lib\clangAST.lib  lib\clangASTMatchers.lib  lib\clangCrossTU.lib  lib\clangFrontend.lib  lib\clangSerialization.lib  lib\clangStaticAnalyzerCore.lib  lib\clangStaticAnalyzerFrontend.lib  lib\clangTooling.lib  lib\clangStaticAnalyzerCheckers.lib  lib\clangStaticAnalyzerCore.lib  lib\clangCrossTU.lib  lib\clangIndex.lib  lib\clangFrontend.lib  lib\clangParse.lib  lib\clangSerialization.lib  lib\clangSema.lib  lib\clangAnalysis.lib  lib\clangASTMatchers.lib  lib\clangEdit.lib  lib\clangDriver.lib  version.lib  lib\LLVMOption.lib  lib\clangFormat.lib  lib\clangToolingInclusions.lib  lib\clangToolingCore.lib  lib\clangAST.lib  lib\LLVMFrontendOpenMP.lib  lib\LLVMTransformUtils.lib  lib\LLVMAnalysis.lib  lib\LLVMProfileData.lib  lib\LLVMObject.lib  lib\LLVMBitReader.lib  lib\LLVMMCParser.lib  lib\LLVMTextAPI.lib  lib\clangRewrite.lib  lib\clangLex.lib  lib\clangBasic.lib  lib\LLVMCore.lib  lib\LLVMRemarks.lib  lib\LLVMBitstreamReader.lib  lib\LLVMMC.lib  lib\LLVMBinaryFormat.lib  lib\LLVMDebugInfoCodeView.lib  lib\LLVMDebugInfoMSF.lib  lib\LLVMSupport.lib  psapi.lib  shell32.lib  ole32.lib  uuid.lib  advapi32.lib  delayimp.lib  -delayload:shell32.dll  -delayload:ole32.dll  lib\LLVMDemangle.lib  kernel32.lib user32.lib gdi32.lib winspool.lib shell32.lib ole32.lib oleaut32.lib uuid.lib comdlg32.lib advapi32.lib && cd ."
LINK: command "D:\llvm-project\buildninjaRel\bin\lld-link.exe /nologo tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\AnalyzerOptionsTest.cpp.obj tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\CallDescriptionTest.cpp.obj tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\StoreTest.cpp.obj tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\RegisterCustomCheckersTest.cpp.obj tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\SymbolReaperTest.cpp.obj tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\D_\llvm-project\llvm\resources\windows_version_resource.rc.res /out:tools\clang\unittests\StaticAnalyzer\StaticAnalysisTests.exe /implib:tools\clang\unittests\StaticAnalyzer\StaticAnalysisTests.lib /pdb:tools\clang\unittests\StaticAnalyzer\StaticAnalysisTests.pdb /version:0.0 /machine:x64 -fuse-ld=lld /STACK:10000000 /DEBUG /OPT:REF /OPT:ICF /lldltocache:D:/llvm-project/buildninjaRelMiMalloc/lto.cache /INCREMENTAL:NO /subsystem:console lib\LLVMSupport.lib lib\LLVMSupport.lib lib\gtest_main.lib lib\gtest.lib lib\clangBasic.lib lib\clangAnalysis.lib lib\clangAST.lib lib\clangASTMatchers.lib lib\clangCrossTU.lib lib\clangFrontend.lib lib\clangSerialization.lib lib\clangStaticAnalyzerCore.lib lib\clangStaticAnalyzerFrontend.lib lib\clangTooling.lib lib\clangStaticAnalyzerCheckers.lib lib\clangStaticAnalyzerCore.lib lib\clangCrossTU.lib lib\clangIndex.lib lib\clangFrontend.lib lib\clangParse.lib lib\clangSerialization.lib lib\clangSema.lib lib\clangAnalysis.lib lib\clangASTMatchers.lib lib\clangEdit.lib lib\clangDriver.lib version.lib lib\LLVMOption.lib lib\clangFormat.lib lib\clangToolingInclusions.lib lib\clangToolingCore.lib lib\clangAST.lib lib\LLVMFrontendOpenMP.lib lib\LLVMTransformUtils.lib lib\LLVMAnalysis.lib lib\LLVMProfileData.lib lib\LLVMObject.lib lib\LLVMBitReader.lib lib\LLVMMCParser.lib lib\LLVMTextAPI.lib lib\clangRewrite.lib lib\clangLex.lib lib\clangBasic.lib lib\LLVMCore.lib lib\LLVMRemarks.lib lib\LLVMBitstreamReader.lib lib\LLVMMC.lib lib\LLVMBinaryFormat.lib lib\LLVMDebugInfoCodeView.lib lib\LLVMDebugInfoMSF.lib lib\LLVMSupport.lib psapi.lib shell32.lib ole32.lib uuid.lib advapi32.lib delayimp.lib -delayload:shell32.dll -delayload:ole32.dll lib\LLVMDemangle.lib kernel32.lib user32.lib gdi32.lib winspool.lib shell32.lib ole32.lib oleaut32.lib uuid.lib comdlg32.lib advapi32.lib /MANIFEST /MANIFESTFILE:tools\clang\unittests\StaticAnalyzer\StaticAnalysisTests.exe.manifest" failed (exit code 0) with the following output:
lld-link: warning: ignoring unknown argument '-fuse-ld=lld'
LLVM ERROR: Second argument of llvm.type.test must be a metadata string
Stack dump:
0.      Running pass 'Lower type metadata' on module 'tools\clang\unittests\StaticAnalyzer\CMakeFiles\StaticAnalysisTests.dir\RegisterCustomCheckersTest.cpp.obj'.
 #0 0x00007ff62cc8f056 HandleAbort D:\llvm-project\llvm\lib\Support\Windows\Signals.inc:408:0
 #1 0x00007ff62f6912f1 raise D:\llvm-project\buildninjaRel\minkernel\crts\ucrt\src\appcrt\misc\signal.cpp:547:0
 #2 0x00007ff62f687c08 abort D:\llvm-project\buildninjaRel\minkernel\crts\ucrt\src\appcrt\startup\abort.cpp:71:0
 #3 0x00007ff62cc88e98 llvm::report_fatal_error(class llvm::Twine const &, bool) D:\llvm-project\llvm\lib\Support\ErrorHandling.cpp:126:0
 #4 0x00007ff62cc88cb1 llvm::report_fatal_error(char const *, bool) D:\llvm-project\llvm\lib\Support\ErrorHandling.cpp:83:0
 #5 0x00007ff62ec3db75 `anonymous namespace'::LowerTypeTestsModule::lower D:\llvm-project\llvm\lib\Transforms\IPO\LowerTypeTests.cpp:0:0
 #6 0x00007ff62ec3e0ce `anonymous namespace'::LowerTypeTests::runOnModule D:\llvm-project\llvm\lib\Transforms\IPO\LowerTypeTests.cpp:539:0
 #7 0x00007ff62d3d6f82 llvm::legacy::PassManagerImpl::run(class llvm::Module &) D:\llvm-project\llvm\lib\IR\LegacyPassManager.cpp:1695:0
 #8 0x00007ff62d6350c0 `anonymous namespace'::opt D:\llvm-project\llvm\lib\LTO\LTOBackend.cpp:314:0
 #9 0x00007ff62d637a48 llvm::lto::thinBackend(struct llvm::lto::Config const &, unsigned int, class std::function<(unsigned int)>, class llvm::Module &, class llvm::ModuleSummaryIndex const &, class llvm::StringMap<class std::unordered_set<unsigned __int64, struct std::hash<unsigned __int64>, struct std::equal_to<unsigned __int64>, class std::allocator<unsigned __int64>>, class llvm::MallocAllocator> const &, class llvm::DenseMap<unsigned __int64, class llvm::GlobalValueSummary *, struct llvm::DenseMapInfo<unsigned __int64>, struct llvm::detail::DenseMapPair<unsigned __int64, class llvm::GlobalValueSummary *>> const &, class llvm::MapVector<class llvm::StringRef, class llvm::BitcodeModule, class llvm::DenseMap<class llvm::StringRef, unsigned int, struct llvm::DenseMapInfo<class llvm::StringRef>, struct llvm::detail::DenseMapPair<class llvm::StringRef, unsigned int>>, class std::vector<struct std::pair<class llvm::StringRef, class llvm::BitcodeModule>, class std::allocator<struct std::pair<class llvm::StringRef, class llvm::BitcodeModule>>>> &) D:\llvm-project\llvm\lib\LTO\LTOBackend.cpp:555:0
#10 0x00007ff62cefc945 `anonymous namespace'::InProcessThinBackend::runThinLTOBackendThread::<unnamed-tag>::operator() D:\llvm-project\llvm\lib\LTO\LTO.cpp:1124:0
#11 0x00007ff62cefc7d3 std::_Func_impl_no_alloc<std::_Binder<std::_Unforced,`lambda at D:\llvm-project\llvm\lib\LTO\LTO.cpp:1157:9',llvm::BitcodeModule &,std::reference_wrapper<llvm::ModuleSummaryIndex>,std::reference_wrapper<const llvm::StringMap<std::unordered_set<unsigned long long,std::hash<unsigned long long>,std::equal_to<unsigned long long>,std::allocator<unsigned long long> >,llvm::MallocAllocator> >,std::reference_wrapper<const llvm::DenseSet<llvm::ValueInfo,llvm::DenseMapInfo<llvm::ValueInfo> > >,std::reference_wrapper<const std::map<unsigned long long,llvm::GlobalValue::LinkageTypes,std::less<unsigned long long>,std::allocator<std::pair<const unsigned long long,llvm::GlobalValue::LinkageTypes> > > >,std::reference_wrapper<const llvm::DenseMap<unsigned long long,llvm::GlobalValueSummary *,llvm::DenseMapInfo<unsigned long long>,llvm::detail::DenseMapPair<unsigned long long,llvm::GlobalValueSummary *> > >,std::reference_wrapper<llvm::MapVector<llvm::StringRef,llvm::BitcodeModule,llvm::DenseMap<llvm::StringRef,unsigned int,llvm::DenseMapInfo<llvm::StringRef>,llvm::detail::DenseMapPair<llvm::StringRef,unsigned int> >,std::vector<std::pair<llvm::StringRef,llvm::BitcodeModule>,std::allocator<std::pair<llvm::StringRef,llvm::BitcodeModule> > > > > >,void>::_Do_call C:\Program Files (x86)\Microsoft Visual Studio\2019\Professional\VC\Tools\MSVC\14.24.28314\include\functional:926:0
#12 0x00007ff62d63d427 std::packaged_task<(void)>::operator()(void) C:\Program Files (x86)\Microsoft Visual Studio\2019\Professional\VC\Tools\MSVC\14.24.28314\include\future:1394:0
#13 0x00007ff62d63d33d std::thread::_Invoke<std::tuple<`lambda at D:\llvm-project\llvm\lib\Support\ThreadPool.cpp:30:26'>,0> C:\Program Files (x86)\Microsoft Visual Studio\2019\Professional\VC\Tools\MSVC\14.24.28314\include\thread:43:0
#14 0x00007ff62f682f04 thread_start<unsigned int (__cdecl*)(void *),1> D:\llvm-project\buildninjaRel\minkernel\crts\ucrt\src\appcrt\startup\thread.cpp:97:0
#15 0x00007ffa95737bd4 (C:\WINDOWS\System32\KERNEL32.DLL+0x17bd4)
#16 0x00007ffa972eced1 (C:\WINDOWS\SYSTEM32\ntdll.dll+0x6ced1)
[4617/4685] Linking CXX executable tools\clang\unittests\Analysis\ClangAnalysisTests.exe
lld-link: warning: ignoring unknown argument '-fuse-ld=lld'
ninja: build stopped: subcommand failed.

I'm at rG6f846c85045ca814b57ee495d9f85a7b0496e947. Building on Windows 10 version 1909, on a VS2019 cmd shell, version 16.4.4. The first stage is built with LLVM 9.0.1.

The cmake I used for stage 1:

set LLVM=c:/Program Files/LLVM
set OPT_AVX=/GS- /D_ITERATOR_DEBUG_LEVEL=0 /arch:AVX
cmake "-DLLVM_LIT_ARGS=-sv -j 36" -GNinja %ROOT%/llvm -DCMAKE_BUILD_TYPE=Release -DLLVM_OPTIMIZED_TABLEGEN=ON -DLLVM_ENABLE_ASSERTIONS=ON -DLLVM_ENABLE_LIBXML2=OFF -DCMAKE_C_COMPILER="%LLVM%/bin/clang-cl.EXE" -DCMAKE_CXX_COMPILER="%LLVM%/bin/clang-cl.EXE" -DCMAKE_LINKER="%LLVM%/bin/lld-link.EXE" -DLLVM_ENABLE_PROJECTS="llvm;clang;lld" -DLLVM_ENABLE_PDB=ON -DLLVM_ENABLE_LLD=ON -DLLVM_USE_CRT_RELEASE=MT -DCMAKE_CXX_FLAGS="%OPT_AVX%" -DCMAKE_C_FLAGS="%OPT_AVX%"

For stage 2:

set OPT_SKYLAKE=/GS- /D_ITERATOR_DEBUG_LEVEL=0 -Xclang -O3 -Xclang -fwhole-program-vtables -fstrict-aliasing -march=skylake-avx512
set LLVM_LOCAL=%ROOT%/buildninjaRel
cmake "-DLLVM_LIT_ARGS=-sv -j 36" -G"Ninja" %ROOT%/llvm -DCMAKE_BUILD_TYPE=Release -DLLVM_OPTIMIZED_TABLEGEN=true -DLLVM_ENABLE_LIBXML2=OFF -DLLVM_USE_CRT_RELEASE=MT -DCMAKE_C_COMPILER="%LLVM_LOCAL%/bin/clang-cl.exe" -DCMAKE_CXX_COMPILER="%LLVM_LOCAL%/bin/clang-cl.exe" -DCMAKE_LINKER="%LLVM_LOCAL%/bin/lld-link.exe" -DLLVM_ENABLE_LLD=ON -DLLVM_ENABLE_PDB=ON -DLLVM_ENABLE_PROJECTS="llvm;clang;lld" -DCMAKE_CXX_FLAGS="%OPT_SKYLAKE%" -DCMAKE_C_FLAGS="%OPT_SKYLAKE%" -DLLVM_ENABLE_LTO=THIN -DCLANG_TABLEGEN="%LLVM_LOCAL%/bin/clang-tblgen.exe" -DLLVM_TABLEGEN="%LLVM_LOCAL%/bin/llvm-tblgen.exe"

Building both stages with ninja check-all.

[tejohnson]

FYI I have reproduced the failure, and am starting to debug.

[tejohnson]

In D73242#1888295, @tejohnson wrote:

FYI I have reproduced the failure, and am starting to debug.

I see what is going on and have a simple fix, just need to create a test case. Expect to send a patch to fix this today, hopefully this morning.

[aganea]

In D73242#1893506, @tejohnson wrote:

In D73242#1888295, @tejohnson wrote:

FYI I have reproduced the failure, and am starting to debug.

I see what is going on and have a simple fix, just need to create a test case. Expect to send a patch to fix this today, hopefully this morning.

Thanks! Let me know, I'll test right away.

I'm seeing another (new?) bug with latest trunk, I'm not sure if it's related or not. The repro is the same, just sync the latest, and do the two-stage build, then ninja check-lld, all the LTO tests fail with this stack:

 #0 0x00007ff63bd7e891 `anonymous namespace'::RealFile::`scalar deleting dtor'(unsigned int) (d:\llvm-project\buildninjarelmimalloc\bin\ld.lld.exe+0x1e891)
 #1 0x00007ff63c47d4ac llvm::FPPassManager::~FPPassManager D:\llvm-project\llvm\include\llvm\IR\LegacyPassManagers.h:461:0
 #2 0x00007ff63c47c98c `anonymous namespace'::MPPassManager::~MPPassManager D:\llvm-project\llvm\lib\IR\LegacyPassManager.cpp:407:0
 #3 0x00007ff63c475fac llvm::PMTopLevelManager::~PMTopLevelManager(void) D:\llvm-project\llvm\lib\IR\LegacyPassManager.cpp:855:0
 #4 0x00007ff63c47c3bc llvm::legacy::FunctionPassManagerImpl::`scalar deleting dtor'(unsigned int) D:\llvm-project\llvm\lib\IR\LegacyPassManager.cpp:324:0
 #5 0x00007ff63c39aa41 `anonymous namespace'::codegen D:\llvm-project\llvm\lib\LTO\LTOBackend.cpp:373:0
 #6 0x00007ff63c39732c llvm::lto::backend(struct llvm::lto::Config const &, class std::function<(unsigned int)>, unsigned int, class std::unique_ptr<class llvm::Module, struct std::default_delete<class llvm::Module>>, class llvm::ModuleSummaryIndex &) D:\llvm-project\llvm\lib\LTO\LTOBackend.cpp:466:0
 #7 0x00007ff63be8a49a llvm::lto::LTO::run(class std::function<(unsigned int)>, class std::function<(unsigned int, class llvm::StringRef)>) D:\llvm-project\llvm\lib\LTO\LTO.cpp:942:0
 #8 0x00007ff63c153eb5 lld::elf::BitcodeCompiler::compile(void) D:\llvm-project\lld\ELF\LTO.cpp:261:0
 #9 0x00007ff63bdc0b01 lld::elf::LinkerDriver::main D:\llvm-project\lld\ELF\Driver.cpp:522:0
#10 0x00007ff63bdba6dc lld::elf::link(class llvm::ArrayRef<char const *>, bool, class llvm::raw_ostream &, class llvm::raw_ostream &) D:\llvm-project\lld\ELF\Driver.cpp:117:0
#11 0x00007ff63bd61807 main D:\llvm-project\lld\tools\lld\lld.cpp:166:0
#12 0x00007ff63e9cf914 __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]

Sent fix for review in D75201.

If the new problem showed up later and not when this one first went in, then it seems likely it is different than this issue. I'll see if I can reproduce and take a look.

[tejohnson]

In D73242#1894146, @tejohnson wrote:

Sent fix for review in D75201.

If the new problem showed up later and not when this one first went in, then it seems likely it is different than this issue. I'll see if I can reproduce and take a look.

I am not seeing this, although my client is from Friday. So it is likely something committed subsequently that caused it.

[tejohnson]

Reverted in 80bf137fa132ea33204e98bbefa924afe9258a4e

[tejohnson]

Updating with fixes since this was reverted in 80bf137fa132ea33204e98bbefa924afe9258a4e.

[tejohnson]

Includes fixe for 2-stage clang bootstrap test failures and an expanded
fix for Chromium issue, plus new tests.

[tejohnson]

PTAL

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1759

Here is the fix for the issue with the multi-stage clang bootstrap test failures described in D75201. I also restructured this code to try to make it clearer (rather than an early continue when we don't need to remove type test assumes, make it an explicit removal when needed).

Added new test llvm/test/ThinLTO/X86/type_test_noindircall.ll for this.

1999

Improved the fix I had made here for Chromium as it wasn't robust enough to handle all cases. Specifically, if we came through this code multiple times with the same type id, the TypeIdMap entry would no longer be missing since we unconditionally created it in the call to tryFindVirtualCallTargets below (via the operator[]). Changed it to check for a non-empty set (after more eagerly calling operator[]). I beefed up the test I had for this issue (llvm/test/ThinLTO/X86/cfi-unsat.ll) to cover this additional case.

[evgeny777]

This needs to be rebased

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1759

Can you please also test the case when LTO unit is split?

[tejohnson]

In D73242#1963451, @evgeny777 wrote:

This needs to be rebased

Sorry for the delay, I've been side tracked on other work. Rebased and beefed up the test as requested.

[tejohnson]

Rebase and beef up test

[evgeny777]

LGTM

llvm/include/llvm/IR/ModuleSummaryIndex.h

 };
 
 struct TypeTestResolution {
   /// Specifies which kind of type check we should emit for this byte array.
   /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
   /// details on each kind of check; the enumerators are described with
   /// reference to that document.
   enum Kind {
     Unsat,     ///< Unsatisfiable type (i.e. no global has this type metadata)
     ByteArray, ///< Test a byte array (first example)
     Inline,    ///< Inlined bit vector ("Short Inline Bit Vectors")
     Single,    ///< Single element (last example in "Short Inline Bit Vectors")
     AllOnes,   ///< All-ones bit vector ("Eliminating Bit Vector Checks for
                ///  All-Ones Bit Vectors")
-  } TheKind = Unsat;
+    Unknown,   ///< Unknown (analysis not performed, don't lower)
+  } TheKind = Unknown;
 
   /// Range of size-1 expressed as a bit width. For example, if the size is in
   /// range [1,256], this number will be 8. This helps generate the most compact
   /// instruction sequences.
   unsigned SizeM1BitWidth = 0;
 
   // The following fields are only used if the target does not support the use
   // of absolute symbols to store constants. Their meanings are the same as the
ModuleSummaryIndex(bool HaveGVs, bool EnableSplitLTOUnit = false)
       : HaveGVs(HaveGVs), EnableSplitLTOUnit(EnableSplitLTOUnit), Saver(Alloc) {
   }
 
   // Current version for the module summary in bitcode files.
   // The BitcodeSummaryVersion should be bumped whenever we introduce changes
   // in the way some record are interpreted, like flags for instance.
   // Note that incrementing this may require changes in both BitcodeReader.cpp
   // and BitcodeWriter.cpp.
-  static constexpr uint64_t BitcodeSummaryVersion = 8;
+  static constexpr uint64_t BitcodeSummaryVersion = 9;
 
   // Regular LTO module name for ASM writer
   static constexpr const char *getRegularLTOModuleName() {
     return "[Regular LTO]";
   }
 
   bool haveGVs() const { return HaveGVs; }
 

llvm/include/llvm/IR/ModuleSummaryIndexYAML.h

 #include "llvm/IR/ModuleSummaryIndex.h"
 #include "llvm/Support/YAMLTraits.h"
 
 namespace llvm {
 namespace yaml {
 
 template <> struct ScalarEnumerationTraits<TypeTestResolution::Kind> {
   static void enumeration(IO &io, TypeTestResolution::Kind &value) {
+    io.enumCase(value, "Unknown", TypeTestResolution::Unknown);
     io.enumCase(value, "Unsat", TypeTestResolution::Unsat);
     io.enumCase(value, "ByteArray", TypeTestResolution::ByteArray);
     io.enumCase(value, "Inline", TypeTestResolution::Inline);
     io.enumCase(value, "Single", TypeTestResolution::Single);
     io.enumCase(value, "AllOnes", TypeTestResolution::AllOnes);
   }
 };
 

llvm/lib/AsmParser/LLParser.cpp

bool LLParser::ParseTypeTestResolution(TypeTestResolution &TTRes) {
   if (ParseToken(lltok::kw_typeTestRes, "expected 'typeTestRes' here") ||
       ParseToken(lltok::colon, "expected ':' here") ||
       ParseToken(lltok::lparen, "expected '(' here") ||
       ParseToken(lltok::kw_kind, "expected 'kind' here") ||
       ParseToken(lltok::colon, "expected ':' here"))
     return true;
 
   switch (Lex.getKind()) {
+  case lltok::kw_unknown:
+    TTRes.TheKind = TypeTestResolution::Unknown;
+    break;
   case lltok::kw_unsat:
     TTRes.TheKind = TypeTestResolution::Unsat;
     break;
   case lltok::kw_byteArray:
     TTRes.TheKind = TypeTestResolution::ByteArray;
     break;
   case lltok::kw_inline:
     TTRes.TheKind = TypeTestResolution::Inline;

llvm/lib/IR/AsmWriter.cpp

static const char *getWholeProgDevirtResByArgKindName(
   case WholeProgramDevirtResolution::ByArg::VirtualConstProp:
     return "virtualConstProp";
   }
   llvm_unreachable("invalid WholeProgramDevirtResolution::ByArg kind");
 }
 
 static const char *getTTResKindName(TypeTestResolution::Kind K) {
   switch (K) {
+  case TypeTestResolution::Unknown:
+    return "unknown";
   case TypeTestResolution::Unsat:
     return "unsat";
   case TypeTestResolution::ByteArray:
     return "byteArray";
   case TypeTestResolution::Inline:
     return "inline";
   case TypeTestResolution::Single:
     return "single";

llvm/lib/Passes/PassBuilder.cpp

if (Phase != ThinLTOPhase::PreLink)
       // We perform early indirect call promotion here, before globalopt.
       // This is important for the ThinLTO backend phase because otherwise
       // imported available_externally functions look unreferenced and are
       // removed.
       MPM.addPass(PGOIndirectCallPromotion(Phase == ThinLTOPhase::PostLink,
                                            true /* SamplePGO */));
   }
 
+  // Lower type metadata and the type.test intrinsic in the ThinLTO
+  // post link pipeline after ICP. This is to enable usage of the type
+  // tests in ICP sequences.
+  if (Phase == ThinLTOPhase::PostLink)
+    MPM.addPass(LowerTypeTestsPass(nullptr, nullptr, true));
+
   // Interprocedural constant propagation now that basic cleanup has occurred
   // and prior to optimizing globals.
   // FIXME: This position in the pipeline hasn't been carefully considered in
   // years, it should be re-analyzed.
   MPM.addPass(IPSCCPPass());
 
   // Attach metadata to indirect call sites indicating the set of functions
   // they may target at run-time. This should follow IPSCCP.
PassBuilder::buildLTODefaultPipeline(OptimizationLevel Level, bool DebugLogging,
                                      ModuleSummaryIndex *ExportSummary) {
   ModulePassManager MPM(DebugLogging);
 
   if (Level == OptimizationLevel::O0) {
     // The WPD and LowerTypeTest passes need to run at -O0 to lower type
     // metadata and intrinsics.
     MPM.addPass(WholeProgramDevirtPass(ExportSummary, nullptr));
     MPM.addPass(LowerTypeTestsPass(ExportSummary, nullptr));
+    // Run a second time to clean up any type tests left behind by WPD for use
+    // in ICP.
+    MPM.addPass(LowerTypeTestsPass(nullptr, nullptr, true));
     return MPM;
   }
 
   if (PGOOpt && PGOOpt->Action == PGOOptions::SampleUse) {
     // Load sample profile before running the LTO optimization pipeline.
     MPM.addPass(SampleProfileLoaderPass(PGOOpt->ProfileFile,
                                         PGOOpt->ProfileRemappingFile,
                                         false /* ThinLTOPhase::PreLink */));
PassBuilder::buildLTODefaultPipeline(OptimizationLevel Level, bool DebugLogging,
   // is fixed.
   MPM.addPass(WholeProgramDevirtPass(ExportSummary, nullptr));
 
   // Stop here at -O1.
   if (Level == OptimizationLevel::O1) {
     // The LowerTypeTestsPass needs to run to lower type metadata and the
     // type.test intrinsics. The pass does nothing if CFI is disabled.
     MPM.addPass(LowerTypeTestsPass(ExportSummary, nullptr));
+    // Run a second time to clean up any type tests left behind by WPD for use
+    // in ICP (which is performed earlier than this in the regular LTO
+    // pipeline).
+    MPM.addPass(LowerTypeTestsPass(nullptr, nullptr, true));
     return MPM;
   }
 
   // Optimize globals to try and fold them into constants.
   MPM.addPass(GlobalOptPass());
 
   // Promote any localized globals to SSA registers.
   MPM.addPass(createModuleToFunctionPassAdaptor(PromotePass()));
#endif
   // targets in the current module.
   MPM.addPass(CrossDSOCFIPass());
 
   // Lower type metadata and the type.test intrinsic. This pass supports
   // clang's control flow integrity mechanisms (-fsanitize=cfi*) and needs
   // to be run at link time if CFI is enabled. This pass does nothing if
   // CFI is disabled.
   MPM.addPass(LowerTypeTestsPass(ExportSummary, nullptr));
+  // Run a second time to clean up any type tests left behind by WPD for use
+  // in ICP (which is performed earlier than this in the regular LTO pipeline).
+  MPM.addPass(LowerTypeTestsPass(nullptr, nullptr, true));
 
   // Enable splitting late in the FullLTO post-link pipeline. This is done in
   // the same stage in the old pass manager (\ref addLateLTOOptimizationPasses).
   if (EnableHotColdSplit)
     MPM.addPass(HotColdSplittingPass());
 
   // Add late LTO optimization passes.
   // Delete basic blocks, which optimization passes may have killed.

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL,
 
   return false;
 }
 
 /// Lower a llvm.type.test call to its implementation. Returns the value to
 /// replace the call with.
 Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
                                                const TypeIdLowering &TIL) {
+  // Delay lowering if the resolution is currently unknown.
+  if (TIL.TheKind == TypeTestResolution::Unknown)
+    return nullptr;
   if (TIL.TheKind == TypeTestResolution::Unsat)
     return ConstantInt::getFalse(M.getContext());
 
   Value *Ptr = CI->getArgOperand(0);
   const DataLayout &DL = M.getDataLayout();
   if (isKnownTypeIdMember(TypeId, DL, Ptr, 0))
     return ConstantInt::getTrue(M.getContext());
 
void LowerTypeTestsModule::importTypeTest(CallInst *CI) {
 
   auto TypeIdStr = dyn_cast<MDString>(TypeIdMDVal->getMetadata());
   if (!TypeIdStr)
     report_fatal_error(
         "Second argument of llvm.type.test must be a metadata string");
 
   TypeIdLowering TIL = importTypeId(TypeIdStr->getString());
   Value *Lowered = lowerTypeTestCall(TypeIdStr, CI, TIL);
+  if (Lowered) {
     CI->replaceAllUsesWith(Lowered);
     CI->eraseFromParent();
   }
+}
 
 // ThinLTO backend: the function F has a jump table entry; update this module
 // accordingly. isJumpTableCanonical describes the type of the jump table entry.
 void LowerTypeTestsModule::importFunction(
     Function *F, bool isJumpTableCanonical,
     std::vector<GlobalAlias *> &AliasesToErase) {
   assert(F->getType()->getAddressSpace() == 0);
 
if (TIUI.IsExported) {
       if (BAI)
         BAI->MaskPtr = MaskPtr;
     }
 
     // Lower each call to llvm.type.test for this type identifier.
     for (CallInst *CI : TIUI.CallSites) {
       ++NumTypeTestCallsLowered;
       Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL);
+      if (Lowered) {
         CI->replaceAllUsesWith(Lowered);
         CI->eraseFromParent();
       }
     }
   }
+}
 
 void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) {
   if (Type->getNumOperands() != 2)
     report_fatal_error("All operands of type metadata must have 2 elements");
 
   if (GO->isThreadLocal())
     report_fatal_error("Bit set element may not be thread-local");
   if (isa<GlobalVariable>(GO) && GO->hasSection())

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

if (OptLevel == 0) {
     // the pass manager to get the same behavior as EP_OptimizerLast in non-O0
     // builds. The function merging pass is
     if (MergeFunctions)
       MPM.add(createMergeFunctionsPass());
     else if (GlobalExtensionsNotEmpty() || !Extensions.empty())
       MPM.add(createBarrierNoopPass());
 
     if (PerformThinLTO) {
+      MPM.add(createLowerTypeTestsPass(nullptr, nullptr, true));
       // Drop available_externally and unreferenced globals. This is necessary
       // with ThinLTO in order to avoid leaving undefined references to dead
       // globals in the object file.
       MPM.add(createEliminateAvailableExternallyPass());
       MPM.add(createGlobalDCEPass());
     }
 
     addExtensionsToPM(EP_EnabledOnOptLevel0, MPM);
void PassManagerBuilder::populateModulePassManager(
 
   // For ThinLTO there are two passes of indirect call promotion. The
   // first is during the compile phase when PerformThinLTO=false and
   // intra-module indirect call targets are promoted. The second is during
   // the ThinLTO backend when PerformThinLTO=true, when we promote imported
   // inter-module indirect calls. For that we perform indirect call promotion
   // earlier in the pass pipeline, here before globalopt. Otherwise imported
   // available_externally functions look unreferenced and are removed.
-  if (PerformThinLTO)
+  if (PerformThinLTO) {
     MPM.add(createPGOIndirectCallPromotionLegacyPass(/*InLTO = */ true,
                                                      !PGOSampleUse.empty()));
+    MPM.add(createLowerTypeTestsPass(nullptr, nullptr, true));
+  }
 
   // For SamplePGO in ThinLTO compile phase, we do not want to unroll loops
   // as it will change the CFG too much to make the 2nd profile annotation
   // in backend more difficult.
   bool PrepareForThinLTOUsingPGOSampleProfile =
       PrepareForThinLTO && !PGOSampleUse.empty();
   if (PrepareForThinLTOUsingPGOSampleProfile)
     DisableUnrollLoops = true;
void PassManagerBuilder::populateThinLTOPassManager(
   PerformThinLTO = true;
   if (LibraryInfo)
     PM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
 
   if (VerifyInput)
     PM.add(createVerifierPass());
 
   if (ImportSummary) {
-    // These passes import type identifier resolutions for whole-program
-    // devirtualization and CFI. They must run early because other passes may
+    // This pass imports type identifier resolutions for whole-program
+    // devirtualization and CFI. It must run early because other passes may
     // disturb the specific instruction patterns that these passes look for,
     // creating dependencies on resolutions that may not appear in the summary.
     //
     // For example, GVN may transform the pattern assume(type.test) appearing in
     // two basic blocks into assume(phi(type.test, type.test)), which would
     // transform a dependency on a WPD resolution into a dependency on a type
     // identifier resolution for CFI.
     //
void PassManagerBuilder::populateLTOPassManager(legacy::PassManagerBase &PM) {
   // Create a function that performs CFI checks for cross-DSO calls with targets
   // in the current module.
   PM.add(createCrossDSOCFIPass());
 
   // Lower type metadata and the type.test intrinsic. This pass supports Clang's
   // control flow integrity mechanisms (-fsanitize=cfi*) and needs to run at
   // link time if CFI is enabled. The pass does nothing if CFI is disabled.
   PM.add(createLowerTypeTestsPass(ExportSummary, nullptr));
+  // Run a second time to clean up any type tests left behind by WPD for use
+  // in ICP (which is performed earlier than this in the regular LTO pipeline).
+  PM.add(createLowerTypeTestsPass(nullptr, nullptr, true));
 
   if (OptLevel != 0)
     addLateLTOOptimizationPasses(PM);
 
   addExtensionsToPM(EP_FullLinkTimeOptimizationLast, PM);
 
   if (VerifyOutput)
     PM.add(createVerifierPass());

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

DevirtModule(Module &M, function_ref<AAResults &(Function &)> AARGetter,
         Int64Ty(Type::getInt64Ty(M.getContext())),
         IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),
         RemarksEnabled(areRemarksEnabled()), OREGetter(OREGetter) {
     assert(!(ExportSummary && ImportSummary));
   }
 
   bool areRemarksEnabled();
 
-  void scanTypeTestUsers(Function *TypeTestFunc);
+  void
+  scanTypeTestUsers(Function *TypeTestFunc,
+                    DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
   void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);
 
   void buildTypeIdentifierMap(
       std::vector<VTableBits> &Bits,
       DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
   bool
   tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
                             const std::set<TypeMemberInfo> &TypeMemberInfos,
for (const Function &Fn : FL) {
     if (BBL.empty())
       continue;
     auto DI = OptimizationRemark(DEBUG_TYPE, "", DebugLoc(), &BBL.front());
     return DI.isEnabled();
   }
   return false;
 }
 
-void DevirtModule::scanTypeTestUsers(Function *TypeTestFunc) {
+void DevirtModule::scanTypeTestUsers(
+    Function *TypeTestFunc,
+    DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
   // Find all virtual calls via a virtual table pointer %p under an assumption
   // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p
   // points to a member of the type identifier %md. Group calls by (type ID,
   // offset) pair (effectively the identity of the virtual function) and store
   // to CallSlots.
   DenseSet<CallSite> SeenCallSites;
   for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end();
        I != E;) {
     auto CI = dyn_cast<CallInst>(I->getUser());
     ++I;
     if (!CI)
       continue;
 
     // Search for virtual calls based on %p and add them to DevirtCalls.
     SmallVector<DevirtCallSite, 1> DevirtCalls;
     SmallVector<CallInst *, 1> Assumes;
     auto &DT = LookupDomTree(*CI->getFunction());
     findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
 
-    // If we found any, add them to CallSlots.
-    if (!Assumes.empty()) {
-      Metadata *TypeId =
-          cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();
+    // If we found any, add them to CallSlots.
+    if (!Assumes.empty()) {
       Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();
       for (DevirtCallSite Call : DevirtCalls) {
         // Only add this CallSite if we haven't seen it before. The vtable
         // pointer may have been CSE'd with pointers from other call sites,
         // and we don't want to process call sites multiple times. We can't
         // just skip the vtable Ptr if it has been seen before, however, since
         // it may be shared by type tests that dominate different calls.
         if (SeenCallSites.insert(Call.CS).second)
           CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS, nullptr);
       }
     }
 
+    // If we have any uses on type metadata, keep the type test assumes for
+    // later analysis. Otherwise remove as they aren't useful, and
+    // LowerTypeTests will think they are Unsat and lower to False, which
+    // breaks any uses on assumes.
+    if (TypeIdMap.count(TypeId))
+      continue;
+
     // We no longer need the assumes or the type test.
     for (auto Assume : Assumes)
       Assume->eraseFromParent();
     // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we
     // may use the vtable argument later.
     if (CI->use_empty())
       CI->eraseFromParent();
   }
for (auto I = TypeCheckedLoadFunc->use_begin(),
     // pointer from the vtable and performs the type check. If possible, we will
     // eliminate the load and the type check later.
 
     // If possible, only generate the load at the point where it is used.
     // This helps avoid unnecessary spills.
     IRBuilder<> LoadB(
         (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
     Value *GEP = LoadB.CreateGEP(Int8Ty, Ptr, Offset);
     Value *GEPPtr = LoadB.CreateBitCast(GEP, PointerType::getUnqual(Int8PtrTy));
     Value *LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEPPtr);
 
     for (Instruction *LoadedPtr : LoadedPtrs) {
       LoadedPtr->replaceAllUsesWith(LoadedValue);
       LoadedPtr->eraseFromParent();
     }
 
     // Likewise for the type test.
bool DevirtModule::run() {
   // module, this pass has nothing to do. But if we are exporting, we also need
   // to handle any users that appear only in the function summaries.
   if (!ExportSummary &&
       (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
        AssumeFunc->use_empty()) &&
       (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()))
     return false;
 
+  // Rebuild type metadata into a map for easy lookup.
+  std::vector<VTableBits> Bits;
+  DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap;
+  buildTypeIdentifierMap(Bits, TypeIdMap);
+
   if (TypeTestFunc && AssumeFunc)
-    scanTypeTestUsers(TypeTestFunc);
+    scanTypeTestUsers(TypeTestFunc, TypeIdMap);
 
   if (TypeCheckedLoadFunc)
     scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
 
   if (ImportSummary) {
     for (auto &S : CallSlots)
       importResolution(S.first, S.second);
 
     removeRedundantTypeTests();
 
     // We have lowered or deleted the type instrinsics, so we will no
     // longer have enough information to reason about the liveness of virtual
     // function pointers in GlobalDCE.
     for (GlobalVariable &GV : M.globals())
       GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
 
     // The rest of the code is only necessary when exporting or during regular
     // LTO, so we are done.
     return true;
   }
 
-  // Rebuild type metadata into a map for easy lookup.
-  std::vector<VTableBits> Bits;
-  DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap;
-  buildTypeIdentifierMap(Bits, TypeIdMap);
   if (TypeIdMap.empty())
     return true;
 
   // Collect information from summary about which calls to try to devirtualize.
   if (ExportSummary) {
     DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
     for (auto &P : TypeIdMap) {
       if (auto *TypeId = dyn_cast<MDString>(P.first))
bool DevirtModule::run() {
   // For each (type, offset) pair:
   bool DidVirtualConstProp = false;
   std::map<std::string, Function*> DevirtTargets;
   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<VirtualCallTarget> TargetsForSlot;
-    if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
-                                  S.first.ByteOffset)) {
-      WholeProgramDevirtResolution *Res = nullptr;
-      if (ExportSummary && isa<MDString>(S.first.TypeID))
-        Res = &ExportSummary
-                   ->getOrInsertTypeIdSummary(
-                       cast<MDString>(S.first.TypeID)->getString())
-                   .WPDRes[S.first.ByteOffset];
+      // 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.
+    if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
+                                  S.first.ByteOffset)) {
 
       if (!trySingleImplDevirt(ExportSummary, TargetsForSlot, S.second, Res)) {
         DidVirtualConstProp |=
             tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first);
 
         tryICallBranchFunnel(TargetsForSlot, S.second, Res, S.first);
       }
 
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);
-    if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary,
-                                  S.first.ByteOffset)) {
-      WholeProgramDevirtResolution *Res =
-          &ExportSummary.getOrInsertTypeIdSummary(S.first.TypeID)
-               .WPDRes[S.first.ByteOffset];
+    // 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.
+    if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary,
+                                  S.first.ByteOffset)) {
 
       if (!trySingleImplDevirt(TargetsForSlot, S.first, S.second, Res,
                                DevirtTargets))
         continue;
     }
   }
 
   // Optionally have the thin link print message for each devirtualized
   // function.
   if (PrintSummaryDevirt)
     for (const auto &DT : DevirtTargets)
       errs() << "Devirtualized call to " << DT << "\n";
 
   return;
 }

llvm/test/Bitcode/summary_version.ll

 ; Check summary versioning
 ; RUN: opt  -module-summary  %s -o - | llvm-bcanalyzer -dump | FileCheck %s
 
 ; CHECK: <GLOBALVAL_SUMMARY_BLOCK
-; CHECK: <VERSION op0=8/>
+; CHECK: <VERSION op0=9/>
 
 
 
 ; Need a function for the summary to be populated.
 define void @foo() {
     ret void
 }

llvm/test/Other/new-pm-lto-defaults.ll

 ; CHECK-O2-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-O2-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}PostOrderFunctionAttrsPass>
 ; CHECK-O2-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O2-NEXT: Running analysis: MemoryDependenceAnalysis
 ; CHECK-O2-NEXT: Running analysis: PhiValuesAnalysis
 ; CHECK-O2-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O2-NEXT: Running pass: CrossDSOCFIPass
 ; CHECK-O2-NEXT: Running pass: LowerTypeTestsPass
+; CHECK-O-NEXT: Running pass: LowerTypeTestsPass
 ; CHECK-O2-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}SimplifyCFGPass>
 ; CHECK-O2-NEXT: Running pass: EliminateAvailableExternallyPass
 ; CHECK-O2-NEXT: Running pass: GlobalDCEPass
 ; CHECK-O-NEXT: Finished llvm::Module pass manager run.
 ; CHECK-O-NEXT: Running pass: PrintModulePass
 
 ; Make sure we get the IR back out without changes when we print the module.
 ; CHECK-O-LABEL: define void @foo(i32 %n) local_unnamed_addr {

llvm/test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-O-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: LowerExpectIntrinsicPass
 ; CHECK-O3-NEXT: Running pass: CallSiteSplittingPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
+; CHECK-POSTLINK-O-NEXT: Running pass: LowerTypeTestsPass
 ; CHECK-O-NEXT: Running pass: IPSCCPPass
 ; CHECK-O-NEXT: Running pass: CalledValuePropagationPass
 ; CHECK-O-NEXT: Running pass: GlobalOptPass
 ; CHECK-O-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PromotePass>
 ; CHECK-O-NEXT: Running pass: DeadArgumentEliminationPass
 ; CHECK-O-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: InstCombinePass

llvm/test/Other/new-pm-thinlto-postlink-pgo-defaults.ll

 ; CHECK-O-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: LowerExpectIntrinsicPass
 ; CHECK-O3-NEXT: Running pass: CallSiteSplittingPass
 ; CHECK-O-NEXT: Finished {{.*}}Function pass manager run.
+; CHECK-O-NEXT: Running pass: LowerTypeTestsPass
 ; CHECK-O-NEXT: Running pass: IPSCCPPass
 ; CHECK-O-NEXT: Running pass: CalledValuePropagationPass
 ; CHECK-O-NEXT: Running pass: GlobalOptPass
 ; CHECK-O-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PromotePass>
 ; CHECK-O-NEXT: Running pass: DeadArgumentEliminationPass
 ; CHECK-O-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting {{.*}}Function pass manager run.
 ; CHECK-O-NEXT: Running pass: InstCombinePass

llvm/test/Other/new-pm-thinlto-postlink-samplepgo-defaults.ll

 ; CHECK-O-NEXT: Running analysis: AAManager on foo
 ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy
 ; CHECK-O-NEXT: Finished {{.*}}Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SampleProfileLoaderPass
 ; CHECK-O-NEXT: Running analysis: ProfileSummaryAnalysis
 ; CHECK-O-NEXT: Running analysis: CallGraphAnalysis
 ; CHECK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}ProfileSummaryAnalysis
 ; CHECK-O-NEXT: Running pass: PGOIndirectCallPromotion
+; CHECK-O-NEXT: Running pass: LowerTypeTestsPass
 ; CHECK-O-NEXT: Running pass: IPSCCPPass
 ; CHECK-O-NEXT: Running pass: CalledValuePropagationPass
 ; CHECK-O-NEXT: Running pass: GlobalOptPass
 ; CHECK-O-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PromotePass>
 ; CHECK-O-NEXT: Running pass: DeadArgumentEliminationPass
 ; CHECK-O-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting {{.*}}Function pass manager run.
 ; CHECK-O-NEXT: Running pass: InstCombinePass

llvm/test/Transforms/WholeProgramDevirt/branch-funnel.ll

 ; RUN: opt -S -wholeprogramdevirt -whole-program-visibility %s | FileCheck --check-prefixes=CHECK,RETP %s
 ; RUN: sed -e 's,+retpoline,-retpoline,g' %s | opt -S -wholeprogramdevirt -whole-program-visibility | FileCheck --check-prefixes=CHECK,NORETP %s
 
 ; RUN: opt -wholeprogramdevirt -whole-program-visibility -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck --check-prefixes=CHECK,RETP %s
 
 ; RUN: opt -wholeprogramdevirt -whole-program-visibility -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t  -O3 -S -o - %s | FileCheck --check-prefixes=CHECK %s
 
 ; RUN: FileCheck --check-prefix=SUMMARY %s < %t
 
 ; SUMMARY:      TypeIdMap:       
 ; SUMMARY-NEXT:   typeid3:
 ; SUMMARY-NEXT:     TTRes:           
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:          
 ; SUMMARY-NEXT:       0:               
 ; SUMMARY-NEXT:         Kind:            BranchFunnel
 ; SUMMARY-NEXT:         SingleImplName:  ''
 ; SUMMARY-NEXT:         ResByArg:        
 ; SUMMARY-NEXT:   typeid1:
 ; SUMMARY-NEXT:     TTRes:           
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:          
 ; SUMMARY-NEXT:       0:               
 ; SUMMARY-NEXT:         Kind:            BranchFunnel
 ; SUMMARY-NEXT:         SingleImplName:  ''
 ; SUMMARY-NEXT:         ResByArg:        
 ; SUMMARY-NEXT:   typeid2:
 ; SUMMARY-NEXT:     TTRes:           
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:          
 ; SUMMARY-NEXT:       0:               
 ; SUMMARY-NEXT:         Kind:            Indir

llvm/test/Transforms/WholeProgramDevirt/devirt-single-impl2.ll

 ; Check that we can run WPD export using opt -wholeprogramdevirt while
 ; loading/saving index from/to bitcode
 ; RUN: llvm-as %s -o %t.bc
 ; RUN: llvm-as %p/Inputs/devirt-single-impl2-index.ll -o %t.index.bc
 ; RUN: opt %s -S -wholeprogramdevirt -whole-program-visibility -wholeprogramdevirt-read-summary=%t.index.bc \
 ; RUN:     -wholeprogramdevirt-summary-action=export \
 ; RUN:     -wholeprogramdevirt-write-summary=%t2.index.bc -o /dev/null
 ; RUN: llvm-dis %t2.index.bc -o - | FileCheck %s
 
 ; Check that opt fails to use summaries which don't contain regular LTO module
 ; when performing export.
 ; RUN: llvm-as %p/Inputs/devirt-bad-index.ll -o %t-bad.index.bc
 ; RUN: not opt %s -S -wholeprogramdevirt -whole-program-visibility -wholeprogramdevirt-read-summary=%t-bad.index.bc \
 ; RUN:     -wholeprogramdevirt-summary-action=export -o /dev/null 2>&1 | FileCheck %s --check-prefix=MISSING-MODULE
 
 ; Check single impl devirtulation in summary
-; CHECK: typeid: (name: "_ZTS1A", summary: (typeTestRes: (kind: unsat, sizeM1BitWidth: 0), wpdResolutions: ((offset: 0, wpdRes: (kind: singleImpl, singleImplName: "_ZNK1A1fEv"))))) ; guid
+; CHECK: typeid: (name: "_ZTS1A", summary: (typeTestRes: (kind: unknown, sizeM1BitWidth: 0), wpdResolutions: ((offset: 0, wpdRes: (kind: singleImpl, singleImplName: "_ZNK1A1fEv"))))) ; guid
 
 ; MISSING-MODULE: combined summary should contain Regular LTO module
 
 source_filename = "ld-temp.o"
 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"
 
 %struct.A = type { i32 (...)** }

llvm/test/Transforms/WholeProgramDevirt/export-single-impl.ll

 ; RUN: opt -wholeprogramdevirt -whole-program-visibility -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck %s
 ; RUN: FileCheck --check-prefix=SUMMARY %s < %t
 
 ; SUMMARY:      TypeIdMap:
 ; SUMMARY-NEXT:   typeid3:
 ; SUMMARY-NEXT:     TTRes:
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            SingleImpl
 ; SUMMARY-NEXT:         SingleImplName:  'vf3$merged'
 ; SUMMARY-NEXT:         ResByArg:
 ; SUMMARY-NEXT:   typeid1:
 ; SUMMARY-NEXT:     TTRes:
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            SingleImpl
 ; SUMMARY-NEXT:         SingleImplName:  vf1
 ; SUMMARY-NEXT:         ResByArg:
 ; SUMMARY-NEXT:   typeid2:
 ; SUMMARY-NEXT:     TTRes:
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            SingleImpl
 ; SUMMARY-NEXT:         SingleImplName:  vf2
 ; SUMMARY-NEXT:         ResByArg:
 ; SUMMARY-NEXT:   typeid4:
 ; SUMMARY-NEXT:     TTRes:
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            SingleImpl

llvm/test/Transforms/WholeProgramDevirt/export-uniform-ret-val.ll

 ; RUN: opt -wholeprogramdevirt -whole-program-visibility -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck %s
 ; RUN: FileCheck --check-prefix=SUMMARY %s < %t
 
 ; SUMMARY-NOT: TypeTests:
 
 ; SUMMARY:      TypeIdMap:
 ; SUMMARY-NEXT:   typeid4:
 ; SUMMARY-NEXT:     TTRes:
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            Indir

llvm/test/Transforms/WholeProgramDevirt/export-unique-ret-val.ll

 ; RUN: opt -wholeprogramdevirt -whole-program-visibility -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck %s
 ; RUN: FileCheck --check-prefix=SUMMARY %s < %t
 
 ; SUMMARY-NOT:  TypeTests:
 
 ; SUMMARY:      TypeIdMap:
 ; SUMMARY-NEXT:   typeid3:
 ; SUMMARY-NEXT:     TTRes:
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            Indir
 ; SUMMARY-NEXT:         SingleImplName:  ''
 ; SUMMARY-NEXT:         ResByArg:
 ; SUMMARY-NEXT:           12,24:
 ; SUMMARY-NEXT:             Kind:            UniqueRetVal
 ; SUMMARY-NEXT:             Info:            0
 ; SUMMARY-NEXT:             Byte:            0
 ; SUMMARY-NEXT:             Bit:             0
 ; SUMMARY-NEXT:   typeid4:
 ; SUMMARY-NEXT:     TTRes:
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            Indir

llvm/test/Transforms/WholeProgramDevirt/export-vcp.ll

 ; RUN: opt -mtriple=x86_64-unknown-linux-gnu -wholeprogramdevirt -whole-program-visibility -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck --check-prefixes=CHECK,X86 %s
 ; RUN: FileCheck --check-prefixes=SUMMARY,SUMMARY-X86 %s < %t
 
 ; RUN: opt -mtriple=armv7-unknown-linux-gnu -wholeprogramdevirt -whole-program-visibility -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck --check-prefixes=CHECK,ARM %s
 ; RUN: FileCheck --check-prefixes=SUMMARY,SUMMARY-ARM %s < %t
 
 target datalayout = "e-p:64:64"
 
 ; SUMMARY:      TypeIdMap:
 ; SUMMARY-NEXT:   typeid3:
 ; SUMMARY-NEXT:     TTRes:
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            Indir
 ; SUMMARY-NEXT:         SingleImplName:  ''
 ; SUMMARY-NEXT:         ResByArg:
 ; SUMMARY-NEXT:           12,24:
 ; SUMMARY-NEXT:             Kind:            VirtualConstProp
 ; SUMMARY-NEXT:             Info:            0
 ; SUMMARY-X86-NEXT:         Byte:            0
 ; SUMMARY-X86-NEXT:         Bit:             0
 ; SUMMARY-ARM-NEXT:         Byte:            4294967295
 ; SUMMARY-ARM-NEXT:         Bit:             1
 ; SUMMARY-NEXT:   typeid4:
 ; SUMMARY-NEXT:     TTRes:
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            Indir

llvm/test/Transforms/WholeProgramDevirt/import-indir.ll

 ; SUMMARY-NEXT:      TypeCheckedLoadConstVCalls:
 ; SUMMARY-NEXT:        - VFunc:
 ; SUMMARY-NEXT:            GUID:            456
 ; SUMMARY-NEXT:            Offset:          8
 ; SUMMARY-NEXT:          Args: [ 24, 12 ]
 ; SUMMARY-NEXT: TypeIdMap:
 ; SUMMARY-NEXT:   typeid1:
 ; SUMMARY-NEXT:     TTRes:
-; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       Kind:            Unknown
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            Indir

llvm/test/Transforms/WholeProgramDevirt/uniform-retval.ll

define i32 @call(i8* %obj) {
   %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
   %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
   %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid")
   call void @llvm.assume(i1 %p)
   %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
   %fptr = load i8*, i8** %fptrptr
   %fptr_casted = bitcast i8* %fptr to i32 (i8*)*
   %result = call i32 %fptr_casted(i8* %obj)
-  ; CHECK-NOT: call
+  ; CHECK-NOT: call i32 %
   ; CHECK: ret i32 123
   ret i32 %result
 }
 
 declare i1 @llvm.type.test(i8*, metadata)
 declare void @llvm.assume(i1)
 
 !0 = !{i32 0, !"typeid"}