Fix thinlto cache key computation for cfi-icall.

[eugenis]

Summary

Fixes PR33966.

CFI code generation for users (not just callers) of a function depends
on whether this function has a jumptable entry or not. This
information needs to be encoded in thinlto cache key.

We filter the jumptable list against functions that are actually
referenced in the current module.

[pcc]

llvm/lib/LTO/LTO.cpp

260

We are recomputing this map (and the one below) once for each input file, which would seem to create O(NM) complexity. Can we avoid that by moving the map computation into the InProcessThinBackend? See for example how we handle TypeIdSummariesByGuid.

283

I think you can move the body of this loop into AddTypeIdSummary (after giving it a better name).

285

I think you also need to include calls().

llvm/test/ThinLTO/X86/Inputs/cache-icall-no.ll

1 ↗

(On Diff #109843)

Do you need this file as part of your test case? I think you just need to *not* provide an LTO definition of f. That's basically what the reproducer in the PR is doing.

[eugenis]

Addressed pcc's comments.

[pcc]

LGTM

llvm/lib/LTO/LTO.cpp

179

So GS can't be null here? If so, you can use dyn_cast below.

867

I think you need to call GlobalValue::dropLLVMManglingEscape on the function name here (same below).

[eugenis]

add a null check && dropLLVMManglingEscape

[eugenis]

llvm/lib/LTO/LTO.cpp

179

in fact, it can (but not in the test suite)

[eugenis]

typo

llvm/lib/LTO/LTO.cpp

 // export/import and other global analysis results.
 // The hash is produced in \p Key.
 static void computeCacheKey(
     SmallString<40> &Key, const Config &Conf, const ModuleSummaryIndex &Index,
     StringRef ModuleID, const FunctionImporter::ImportMapTy &ImportList,
     const FunctionImporter::ExportSetTy &ExportList,
     const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
     const GVSummaryMapTy &DefinedGlobals,
-    const TypeIdSummariesByGuidTy &TypeIdSummariesByGuid) {
+    const TypeIdSummariesByGuidTy &TypeIdSummariesByGuid,
+    const std::set<GlobalValue::GUID> &CfiFunctionDefs,
+    const std::set<GlobalValue::GUID> &CfiFunctionDecls) {
   // Compute the unique hash for this entry.
   // This is based on the current compiler version, the module itself, the
   // export list, the hash for every single module in the import list, the
   // list of ResolvedODR for the module, and the list of preserved symbols.
   SHA1 Hasher;
 
   // Start with the compiler revision
   Hasher.update(LLVM_VERSION_STRING);
#endif
   // Include the hash for the resolved ODR.
   for (auto &Entry : ResolvedODR) {
     Hasher.update(ArrayRef<uint8_t>((const uint8_t *)&Entry.first,
                                     sizeof(GlobalValue::GUID)));
     Hasher.update(ArrayRef<uint8_t>((const uint8_t *)&Entry.second,
                                     sizeof(GlobalValue::LinkageTypes)));
   }
 
+  // Members of CfiFunctionDefs and CfiFunctionDecls that are referenced or
+  // defined in this module.
+  std::set<GlobalValue::GUID> UsedCfiDefs;
+  std::set<GlobalValue::GUID> UsedCfiDecls;
+
+  // Typeids used in this module.
   std::set<GlobalValue::GUID> UsedTypeIds;
 
-  auto AddUsedTypeIds = [&](GlobalValueSummary *GS) {
-    auto *FS = dyn_cast_or_null<FunctionSummary>(GS);
-    if (!FS)
-      return;
+  auto AddUsedCfiGlobal = [&](GlobalValue::GUID ValueGUID) {
+    if (CfiFunctionDefs.count(ValueGUID))
+      UsedCfiDefs.insert(ValueGUID);
+    if (CfiFunctionDecls.count(ValueGUID))
+      UsedCfiDecls.insert(ValueGUID);
+  };
+
+  auto AddUsedThings = [&](GlobalValueSummary *GS) {
+    for (const ValueInfo &VI : GS->refs())
+      AddUsedCfiGlobal(VI.getGUID());
+    if (auto *FS = dyn_cast_or_null<FunctionSummary>(GS)) {
       for (auto &TT : FS->type_tests())
         UsedTypeIds.insert(TT);
       for (auto &TT : FS->type_test_assume_vcalls())
         UsedTypeIds.insert(TT.GUID);
       for (auto &TT : FS->type_checked_load_vcalls())
         UsedTypeIds.insert(TT.GUID);
       for (auto &TT : FS->type_test_assume_const_vcalls())
         UsedTypeIds.insert(TT.VFunc.GUID);
       for (auto &TT : FS->type_checked_load_const_vcalls())
         UsedTypeIds.insert(TT.VFunc.GUID);
+      for (auto &ET : FS->calls())
+        AddUsedCfiGlobal(ET.first.getGUID());
+    }
   };
 
   // Include the hash for the linkage type to reflect internalization and weak
   // resolution, and collect any used type identifier resolutions.
   for (auto &GS : DefinedGlobals) {
     GlobalValue::LinkageTypes Linkage = GS.second->linkage();
     Hasher.update(
         ArrayRef<uint8_t>((const uint8_t *)&Linkage, sizeof(Linkage)));
-    AddUsedTypeIds(GS.second);
+    AddUsedCfiGlobal(GS.first);
+    AddUsedThings(GS.second);
   }
 
   // Imported functions may introduce new uses of type identifier resolutions,
   // so we need to collect their used resolutions as well.
   for (auto &ImpM : ImportList)
     for (auto &ImpF : ImpM.second)
-      AddUsedTypeIds(Index.findSummaryInModule(ImpF.first, ImpM.first()));
+      AddUsedThings(Index.findSummaryInModule(ImpF.first, ImpM.first()));
 
   auto AddTypeIdSummary = [&](StringRef TId, const TypeIdSummary &S) {
     AddString(TId);
 
     AddUnsigned(S.TTRes.TheKind);
     AddUnsigned(S.TTRes.SizeM1BitWidth);
 
     AddUint64(S.WPDRes.size());
#endif
   // Include the hash for all type identifiers used by this module.
   for (GlobalValue::GUID TId : UsedTypeIds) {
     auto SummariesI = TypeIdSummariesByGuid.find(TId);
     if (SummariesI != TypeIdSummariesByGuid.end())
       for (auto *Summary : SummariesI->second)
         AddTypeIdSummary(Summary->first, Summary->second);
   }
 
+  AddUnsigned(UsedCfiDefs.size());
+  for (auto &V : UsedCfiDefs)
+    AddUint64(V);
+
+  AddUnsigned(UsedCfiDecls.size());
+  for (auto &V : UsedCfiDecls)
+    AddUint64(V);
+
   if (!Conf.SampleProfile.empty()) {
     auto FileOrErr = MemoryBuffer::getFile(Conf.SampleProfile);
     if (FileOrErr)
       Hasher.update(FileOrErr.get()->getBuffer());
   }
 
   Key = toHex(Hasher.result());
 }
 
 static void thinLTOResolveWeakForLinkerGUID(
     GlobalValueSummaryList &GVSummaryList, GlobalValue::GUID GUID,
     DenseSet<GlobalValueSummary *> &GlobalInvolvedWithAlias,
     function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
         isPrevailing,
     function_ref<void(StringRef, GlobalValue::GUID, GlobalValue::LinkageTypes)>
         recordNewLinkage) {
   for (auto &S : GVSummaryList) {
     GlobalValue::LinkageTypes OriginalLinkage = S->linkage();
     if (!GlobalValue::isWeakForLinker(OriginalLinkage))
       continue;
     // We need to emit only one of these. The prevailing module will keep it,
     // but turned into a weak, while the others will drop it when possible.
     // This is both a compile-time optimization and a correctness
     // transformation. This is necessary for correctness when we have exported
     // a reference - we need to convert the linkonce to weak to
     // ensure a copy is kept to satisfy the exported reference.
     // FIXME: We may want to split the compile time and correctness
     // aspects into separate routines.
     if (isPrevailing(GUID, S.get())) {
       if (GlobalValue::isLinkOnceLinkage(OriginalLinkage))
         S->setLinkage(GlobalValue::getWeakLinkage(
             GlobalValue::isLinkOnceODRLinkage(OriginalLinkage)));
     }
     // Alias and aliasee can't be turned into available_externally.
     else if (!isa<AliasSummary>(S.get()) &&
              !GlobalInvolvedWithAlias.count(S.get()))
       S->setLinkage(GlobalValue::AvailableExternallyLinkage);
     if (S->linkage() != OriginalLinkage)
       recordNewLinkage(S->modulePath(), GUID, S->linkage());
   }
 }
 

 };
 
 namespace {
 class InProcessThinBackend : public ThinBackendProc {
   ThreadPool BackendThreadPool;
   AddStreamFn AddStream;
   NativeObjectCache Cache;
   TypeIdSummariesByGuidTy TypeIdSummariesByGuid;
+  std::set<GlobalValue::GUID> CfiFunctionDefs;
+  std::set<GlobalValue::GUID> CfiFunctionDecls;
 
   Optional<Error> Err;
   std::mutex ErrMu;
 
 public:
   InProcessThinBackend(
       Config &Conf, ModuleSummaryIndex &CombinedIndex,
       unsigned ThinLTOParallelismLevel,
       const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
       AddStreamFn AddStream, NativeObjectCache Cache)
       : ThinBackendProc(Conf, CombinedIndex, ModuleToDefinedGVSummaries),
         BackendThreadPool(ThinLTOParallelismLevel),
         AddStream(std::move(AddStream)), Cache(std::move(Cache)) {
     // Create a mapping from type identifier GUIDs to type identifier summaries.
     // This allows backends to use the type identifier GUIDs stored in the
     // function summaries to determine which type identifier summaries affect
     // each function without needing to compute GUIDs in each backend.
     for (auto &TId : CombinedIndex.typeIds())
       TypeIdSummariesByGuid[GlobalValue::getGUID(TId.first)].push_back(&TId);
+    for (auto &Name : CombinedIndex.cfiFunctionDefs())
+      CfiFunctionDefs.insert(GlobalValue::getGUID(Name));
+    for (auto &Name : CombinedIndex.cfiFunctionDecls())
+      CfiFunctionDecls.insert(GlobalValue::getGUID(Name));
   }
 
   Error runThinLTOBackendThread(
       AddStreamFn AddStream, NativeObjectCache Cache, unsigned Task,
       BitcodeModule BM, ModuleSummaryIndex &CombinedIndex,
       const FunctionImporter::ImportMapTy &ImportList,
       const FunctionImporter::ExportSetTy &ExportList,
       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
if (!Cache || !CombinedIndex.modulePaths().count(ModuleID) ||
                [](uint32_t V) { return V == 0; }))
       // Cache disabled or no entry for this module in the combined index or
       // no module hash.
       return RunThinBackend(AddStream);
 
     SmallString<40> Key;
     // The module may be cached, this helps handling it.
     computeCacheKey(Key, Conf, CombinedIndex, ModuleID, ImportList, ExportList,
-                    ResolvedODR, DefinedGlobals, TypeIdSummariesByGuid);
+                    ResolvedODR, DefinedGlobals, TypeIdSummariesByGuid,
+                    CfiFunctionDefs, CfiFunctionDecls);
     if (AddStreamFn CacheAddStream = Cache(Task, Key))
       return RunThinBackend(CacheAddStream);
 
     return Error::success();
   }
 
   Error start(
       unsigned Task, BitcodeModule BM,

llvm/test/ThinLTO/X86/Inputs/cache-icall.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @f() !type !0 {
+entry:
+  ret void
+}
+
+!0 = !{i64 0, !"_ZTSFvvE"}

llvm/test/ThinLTO/X86/cache-icall.ll

+; Test that the list of CFI jumptable entries is part of ThinLTO cache key.
+
+; Linking Inputs/cache-icall.ll results in f() being added to CFI jumptable; otherwise it is not.
+; This affects code generated for any users of f(). Make sure that we don't pull a stale object
+; file for %t.o from the cache.
+
+; RUN: opt -module-hash -module-summary -thinlto-bc %s -o %t.bc
+; RUN: opt -module-hash -module-summary -thinlto-bc %p/Inputs/cache-icall.ll -o %t2.bc
+
+; RUN: rm -Rf %t.cache && mkdir %t.cache
+
+; RUN: llvm-lto2 run -o %t-no.o %t.bc -cache-dir %t.cache \
+; RUN:   -r=%t.bc,_start,px \
+; RUN:   -r=%t.bc,f,
+
+; RUN: llvm-readelf -symbols %t-no.o.* | FileCheck %s --check-prefix=SYMBOLS-NO
+
+; RUN: llvm-lto2 run -o %t-yes.o %t.bc %t2.bc -cache-dir %t.cache \
+; RUN:   -r=%t.bc,_start,px \
+; RUN:   -r=%t.bc,f, \
+; RUN:   -r=%t2.bc,f,p
+
+; RUN: llvm-readelf -symbols %t-yes.o.* | FileCheck %s --check-prefix=SYMBOLS-YES
+
+; SYMBOLS-NO-DAG: {{FUNC .* f.cfi_jt$}}
+; SYMBOLS-NO-DAG: {{NOTYPE .* UND f.cfi_jt$}}
+
+; SYMBOLS-YES-NOT: f.cfi_jt
+; SYMBOLS-YES-DAG: {{FUNC .* f.cfi$}}
+; SYMBOLS-YES-DAG: {{NOTYPE .* UND f.cfi$}}
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i8* @_start(void ()* %p) !type !0 {
+entry:
+  %0 = bitcast void ()* %p to i8*
+  %1 = tail call i1 @llvm.type.test(i8* %0, metadata !"_ZTSFvvE")
+  br i1 %1, label %cont, label %trap
+
+trap:                                             ; preds = %entry
+  tail call void @llvm.trap()
+  unreachable
+
+cont:                                             ; preds = %entry
+  tail call void %p()
+  ret i8* bitcast (void ()* @f to i8*)
+}
+
+declare i1 @llvm.type.test(i8*, metadata)
+declare void @llvm.trap()
+declare !type !1 void @f()
+
+!0 = !{i64 0, !"_ZTSFPvPFvvEE"}
+!1 = !{i64 0, !"_ZTSFvvE"}