[ThinLTO] Add correctness check for RO/WO variable import

[evgeny777]

Summary

This was suggested in D70006. The check is a bit expensive so is put under NDEBUG

[tejohnson]

Thanks for doing this. I have some ideas on how to reduce the overhead of this checking below.

llvm/lib/Transforms/IPO/FunctionImport.cpp

653

There's presumably a number of duplicates across the various per module import lists, so I'm thinking it would be more efficient to flatten these sets first into a single set of imported GUIDs. Also, it should be more efficient to change the algorithm here to do something like:

Flatten ImportLists -> FlattenedImports
Change loop that walks Export lists to first check if each exported GUID is in the Flattened Imports, and only if not check if it IsReadOrWriteOnlyVar.

The advantage of this is that this avoids doing a hash table lookup for each exported GUID (looking it up in the index), so that we only do so for those that are potentially problematic (because they are not imported anywhere).

An alternative would be to compute the ReadOrWriteOnlyVars exported GUID set as the export lists are built during importing, but only under !NDEBUG. I'm not sure if that is necessary though after the restructuring I suggest above, which should hopefully streamline this so that it is reasonable in debug builds.

This also makes me think it might be a good idea to consider changing the ExportLists to hold the ValueInfos rather than GUIDs (not suggesting you do that here, more a note to self for future). After poking around at the uses of the export lists it seems very doable, and would avoid the need for index hash table lookups to locate the associated summaries here and anywhere else in the future...

[evgeny777]

Addressed

This also makes me think it might be a good idea to consider changing the ExportLists to hold the ValueInfos rather than GUIDs

Makes sense, I've done it for this patch as well.

[tejohnson]

Thanks for doing this! A minor suggestion and a spelling correction on the variable below, but otherwise lgtm. Please commit the ExportList type change as a separate prior NFC commit and the new assertion checking after as a distinct commit.

llvm/lib/LTO/LTO.cpp

424

Just do Index.getValueInfo(I)

llvm/lib/Transforms/IPO/FunctionImport.cpp

635

s/Flattended/Flattened/

639

I think this loop could be simplified to just:

FlattenedImports.insert(ExportPerModule.second.begin(), ExportPerModule.second.end());

llvm/include/llvm/LTO/LTO.h

function_ref<void(StringRef, GlobalValue::GUID, GlobalValue::LinkageTypes)>
         recordNewLinkage,
     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols);
 
 /// Update the linkages in the given \p Index to mark exported values
 /// as external and non-exported values as internal. The ThinLTO backends
 /// must apply the changes to the Module via thinLTOInternalizeModule.
 void thinLTOInternalizeAndPromoteInIndex(
     ModuleSummaryIndex &Index,
-    function_ref<bool(StringRef, GlobalValue::GUID)> isExported,
+    function_ref<bool(StringRef, ValueInfo)> isExported,
     function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
         isPrevailing);
 
 /// Computes a unique hash for the Module considering the current list of
 /// export/import and other global analysis results.
 /// The hash is produced in \p Key.
 void computeLTOCacheKey(
     SmallString<40> &Key, const lto::Config &Conf,

llvm/include/llvm/Transforms/IPO/FunctionImport.h

using ImportThresholdsTy =
                           std::unique_ptr<ImportFailureInfo>>>;
 
   /// The map contains an entry for every module to import from, the key being
   /// the module identifier to pass to the ModuleLoader. The value is the set of
   /// functions to import.
   using ImportMapTy = StringMap<FunctionsToImportTy>;
 
   /// The set contains an entry for every global value the module exports.
-  using ExportSetTy = std::unordered_set<GlobalValue::GUID>;
+  using ExportSetTy = DenseSet<ValueInfo>;
 
   /// A function of this type is used to load modules referenced by the index.
   using ModuleLoaderTy =
       std::function<Expected<std::unique_ptr<Module>>(StringRef Identifier)>;
 
   /// Create a Function Importer.
   FunctionImporter(const ModuleSummaryIndex &Index, ModuleLoaderTy ModuleLoader)
       : Index(Index), ModuleLoader(std::move(ModuleLoader)) {}

llvm/include/llvm/Transforms/IPO/WholeProgramDevirt.h

 void runWholeProgramDevirtOnIndex(
     ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
     std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
 
 /// Call after cross-module importing to update the recorded single impl
 /// devirt target names for any locals that were exported.
 void updateIndexWPDForExports(
     ModuleSummaryIndex &Summary,
-    function_ref<bool(StringRef, GlobalValue::GUID)> isExported,
+    function_ref<bool(StringRef, ValueInfo)> isExported,
     std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H

llvm/lib/LTO/LTO.cpp

#endif
   AddString(Conf.AAPipeline);
   AddString(Conf.OverrideTriple);
   AddString(Conf.DefaultTriple);
   AddString(Conf.DwoDir);
 
   // Include the hash for the current module
   auto ModHash = Index.getModuleHash(ModuleID);
   Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
-  for (auto F : ExportList)
+  for (const auto &VI : ExportList) {
+    auto GUID = VI.getGUID();
     // The export list can impact the internalization, be conservative here
-    Hasher.update(ArrayRef<uint8_t>((uint8_t *)&F, sizeof(F)));
+    Hasher.update(ArrayRef<uint8_t>((uint8_t *)&GUID, sizeof(GUID)));
+  }
 
   // Include the hash for every module we import functions from. The set of
   // imported symbols for each module may affect code generation and is
   // sensitive to link order, so include that as well.
   for (auto &Entry : ImportList) {
     auto ModHash = Index.getModuleHash(Entry.first());
     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
 
static bool isWeakObjectWithRWAccess(GlobalValueSummary *GVS) {
   if (auto *VarSummary = dyn_cast<GlobalVarSummary>(GVS->getBaseObject()))
     return !VarSummary->maybeReadOnly() && !VarSummary->maybeWriteOnly() &&
            (VarSummary->linkage() == GlobalValue::WeakODRLinkage ||
             VarSummary->linkage() == GlobalValue::LinkOnceODRLinkage);
   return false;
 }
 
 static void thinLTOInternalizeAndPromoteGUID(
-    GlobalValueSummaryList &GVSummaryList, GlobalValue::GUID GUID,
-    function_ref<bool(StringRef, GlobalValue::GUID)> isExported,
+    GlobalValueSummaryList &GVSummaryList, ValueInfo VI,
+    function_ref<bool(StringRef, ValueInfo)> isExported,
     function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
         isPrevailing) {
   for (auto &S : GVSummaryList) {
-    if (isExported(S->modulePath(), GUID)) {
+    if (isExported(S->modulePath(), VI)) {
       if (GlobalValue::isLocalLinkage(S->linkage()))
         S->setLinkage(GlobalValue::ExternalLinkage);
     } else if (EnableLTOInternalization &&
                // Ignore local and appending linkage values since the linker
                // doesn't resolve them.
                !GlobalValue::isLocalLinkage(S->linkage()) &&
                (!GlobalValue::isInterposableLinkage(S->linkage()) ||
-                isPrevailing(GUID, S.get())) &&
+                isPrevailing(VI.getGUID(), S.get())) &&
                S->linkage() != GlobalValue::AppendingLinkage &&
                // We can't internalize available_externally globals because this
                // can break function pointer equality.
                S->linkage() != GlobalValue::AvailableExternallyLinkage &&
                // Functions and read-only variables with linkonce_odr and
                // weak_odr linkage can be internalized. We can't internalize
                // linkonce_odr and weak_odr variables which are both modified
                // and read somewhere in the program because reads and writes
                // will become inconsistent.
                !isWeakObjectWithRWAccess(S.get()))
       S->setLinkage(GlobalValue::InternalLinkage);
   }
 }
 
 // Update the linkages in the given \p Index to mark exported values
 // as external and non-exported values as internal.
 void llvm::thinLTOInternalizeAndPromoteInIndex(
     ModuleSummaryIndex &Index,
-    function_ref<bool(StringRef, GlobalValue::GUID)> isExported,
+    function_ref<bool(StringRef, ValueInfo)> isExported,
     function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
         isPrevailing) {
   for (auto &I : Index)
-    thinLTOInternalizeAndPromoteGUID(I.second.SummaryList, I.first, isExported,
-                                     isPrevailing);
+    thinLTOInternalizeAndPromoteGUID(
+        I.second.SummaryList, Index.getValueInfo(I), isExported, isPrevailing);
 }
 
 // Requires a destructor for std::vector<InputModule>.
 InputFile::~InputFile() = default;
 
 Expected<std::unique_ptr<InputFile>> InputFile::create(MemoryBufferRef Object) {
   std::unique_ptr<InputFile> File(new InputFile);
 
Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache,
   }
 
   // Any functions referenced by the jump table in the regular LTO object must
   // be exported.
   for (auto &Def : ThinLTO.CombinedIndex.cfiFunctionDefs())
     ExportedGUIDs.insert(
         GlobalValue::getGUID(GlobalValue::dropLLVMManglingEscape(Def)));
 
-  auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) {
+  auto isExported = [&](StringRef ModuleIdentifier, ValueInfo VI) {
     const auto &ExportList = ExportLists.find(ModuleIdentifier);
-    return (ExportList != ExportLists.end() &&
-            ExportList->second.count(GUID)) ||
-           ExportedGUIDs.count(GUID);
+    return (ExportList != ExportLists.end() && ExportList->second.count(VI)) ||
+           ExportedGUIDs.count(VI.getGUID());
   };
 
   // Update local devirtualized targets that were exported by cross-module
   // importing or by other devirtualizations marked in the ExportedGUIDs set.
   updateIndexWPDForExports(ThinLTO.CombinedIndex, isExported,
                            LocalWPDTargetsMap);
 
   auto isPrevailing = [&](GlobalValue::GUID GUID,

llvm/lib/LTO/ThinLTOCodeGenerator.cpp

 struct IsExported {
   const StringMap<FunctionImporter::ExportSetTy> &ExportLists;
   const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols;
 
   IsExported(const StringMap<FunctionImporter::ExportSetTy> &ExportLists,
              const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols)
       : ExportLists(ExportLists), GUIDPreservedSymbols(GUIDPreservedSymbols) {}
 
-  bool operator()(StringRef ModuleIdentifier, GlobalValue::GUID GUID) const {
+  bool operator()(StringRef ModuleIdentifier, ValueInfo VI) const {
     const auto &ExportList = ExportLists.find(ModuleIdentifier);
-    return (ExportList != ExportLists.end() &&
-            ExportList->second.count(GUID)) ||
-           GUIDPreservedSymbols.count(GUID);
+    return (ExportList != ExportLists.end() && ExportList->second.count(VI)) ||
+           GUIDPreservedSymbols.count(VI.getGUID());
   }
 };
 
 struct IsPrevailing {
   const DenseMap<GlobalValue::GUID, const GlobalValueSummary *> &PrevailingCopy;
   IsPrevailing(const DenseMap<GlobalValue::GUID, const GlobalValueSummary *>
                    &PrevailingCopy)
       : PrevailingCopy(PrevailingCopy) {}

llvm/lib/Transforms/IPO/FunctionImport.cpp

for (auto &VI : Summary.refs()) {
     // was not distinguishing path.
     auto LocalNotInModule = [&](const GlobalValueSummary *RefSummary) -> bool {
       return GlobalValue::isLocalLinkage(RefSummary->linkage()) &&
              RefSummary->modulePath() != Summary.modulePath();
     };
 
     auto MarkExported = [&](const ValueInfo &VI, const GlobalValueSummary *S) {
       if (ExportLists)
-        (*ExportLists)[S->modulePath()].insert(VI.getGUID());
+        (*ExportLists)[S->modulePath()].insert(VI);
     };
 
     for (auto &RefSummary : VI.getSummaryList())
       if (isa<GlobalVarSummary>(RefSummary.get()) &&
           Index.canImportGlobalVar(RefSummary.get(), /* AnalyzeRefs */ true) &&
           !LocalNotInModule(RefSummary.get())) {
         auto ILI = ImportList[RefSummary->modulePath()].insert(VI.getGUID());
         // Only update stat if we haven't already imported this variable.
if (CalleeSummary) {
           NumImportedHotFunctionsThinLink++;
         if (IsCriticalCallsite)
           NumImportedCriticalFunctionsThinLink++;
       }
 
       // Make exports in the source module.
       if (ExportLists) {
         auto &ExportList = (*ExportLists)[ExportModulePath];
-        ExportList.insert(VI.getGUID());
+        ExportList.insert(VI);
         if (!PreviouslyImported) {
           // This is the first time this function was exported from its source
           // module, so mark all functions and globals it references as exported
           // to the outside if they are defined in the same source module.
           // For efficiency, we unconditionally add all the referenced GUIDs
           // to the ExportList for this module, and will prune out any not
           // defined in the module later in a single pass.
-          for (auto &Edge : ResolvedCalleeSummary->calls()) {
-            auto CalleeGUID = Edge.first.getGUID();
-            ExportList.insert(CalleeGUID);
-          }
-          for (auto &Ref : ResolvedCalleeSummary->refs()) {
-            auto GUID = Ref.getGUID();
-            ExportList.insert(GUID);
-          }
+          for (auto &Edge : ResolvedCalleeSummary->calls())
+            ExportList.insert(Edge.first);
+
+          for (auto &Ref : ResolvedCalleeSummary->refs())
+            ExportList.insert(Ref);
         }
       }
     }
 
     auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
       // Adjust the threshold for next level of imported functions.
       // The threshold is different for hot callsites because we can then
       // inline chains of hot calls.
static unsigned numGlobalVarSummaries(const ModuleSummaryIndex &Index,
   unsigned NumGVS = 0;
   for (auto &V : Cont)
     if (isGlobalVarSummary(Index, getGUID(V)))
       ++NumGVS;
   return NumGVS;
 }
 #endif
 
+static bool
+checkVariableImport(const ModuleSummaryIndex &Index,
+                    StringMap<FunctionImporter::ImportMapTy> &ImportLists,
+                    StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
+
+  DenseSet<GlobalValue::GUID> FlattenedImports;
+
+  for (auto &ImportPerModule : ImportLists)
+    for (auto &ExportPerModule : ImportPerModule.second)
+      FlattenedImports.insert(ExportPerModule.second.begin(),
+                              ExportPerModule.second.end());
+
+  // Checks that all GUIDs of read/writeonly vars we see in export lists
+  // are also in the import lists. Otherwise we my face linker undefs,
+  // because readonly and writeonly vars are internalized in their
+  // source modules.
+  auto IsReadOrWriteOnlyVar = [&](StringRef ModulePath, const ValueInfo &VI) {
+    auto *GVS = dyn_cast_or_null<GlobalVarSummary>(
+        Index.findSummaryInModule(VI, ModulePath));
+    return GVS && (Index.isReadOnly(GVS) || Index.isWriteOnly(GVS));
+  };
+
+  for (auto &ExportPerModule : ExportLists)
+    for (auto &VI : ExportPerModule.second)
+      if (!FlattenedImports.count(VI.getGUID()) &&
+          IsReadOrWriteOnlyVar(ExportPerModule.first(), VI))
+        return false;
+
+  return true;
+}
+
 /// Compute all the import and export for every module using the Index.
 void llvm::ComputeCrossModuleImport(
     const ModuleSummaryIndex &Index,
     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
     StringMap<FunctionImporter::ImportMapTy> &ImportLists,
     StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
   // For each module that has function defined, compute the import/export lists.
   for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
     auto &ImportList = ImportLists[DefinedGVSummaries.first()];
     LLVM_DEBUG(dbgs() << "Computing import for Module '"
                       << DefinedGVSummaries.first() << "'\n");
     ComputeImportForModule(DefinedGVSummaries.second, Index,
                            DefinedGVSummaries.first(), ImportList,
                            &ExportLists);
   }
 
   // When computing imports we added all GUIDs referenced by anything
   // imported from the module to its ExportList. Now we prune each ExportList
   // of any not defined in that module. This is more efficient than checking
   // while computing imports because some of the summary lists may be long
   // due to linkonce (comdat) copies.
   for (auto &ELI : ExportLists) {
     const auto &DefinedGVSummaries =
         ModuleToDefinedGVSummaries.lookup(ELI.first());
-    for (auto EI = ELI.second.begin(); EI != ELI.second.end();) {
-      if (!DefinedGVSummaries.count(*EI))
-        EI = ELI.second.erase(EI);
-      else
-        ++EI;
-    }
+    std::remove_if(ELI.second.begin(), ELI.second.end(),
+                   [&](const ValueInfo &VI) {
+                     return !DefinedGVSummaries.count(VI.getGUID());
+                   });
   }
 
+  assert(checkVariableImport(Index, ImportLists, ExportLists));
 #ifndef NDEBUG
   LLVM_DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size()
                     << " modules:\n");
   for (auto &ModuleImports : ImportLists) {
     auto ModName = ModuleImports.first();
     auto &Exports = ExportLists[ModName];
     unsigned NumGVS = numGlobalVarSummaries(Index, Exports);
     LLVM_DEBUG(dbgs() << "* Module " << ModName << " exports "

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

 void runWholeProgramDevirtOnIndex(
     ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
     std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
   DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap).run();
 }
 
 void updateIndexWPDForExports(
     ModuleSummaryIndex &Summary,
-    function_ref<bool(StringRef, GlobalValue::GUID)> isExported,
+    function_ref<bool(StringRef, ValueInfo)> isExported,
     std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
   for (auto &T : LocalWPDTargetsMap) {
     auto &VI = T.first;
     // This was enforced earlier during trySingleImplDevirt.
     assert(VI.getSummaryList().size() == 1 &&
            "Devirt of local target has more than one copy");
     auto &S = VI.getSummaryList()[0];
-    if (!isExported(S->modulePath(), VI.getGUID()))
+    if (!isExported(S->modulePath(), VI))
       continue;
 
     // It's been exported by a cross module import.
     for (auto &SlotSummary : T.second) {
       auto *TIdSum = Summary.getTypeIdSummary(SlotSummary.TypeID);
       assert(TIdSum);
       auto WPDRes = TIdSum->WPDRes.find(SlotSummary.ByteOffset);
       assert(WPDRes != TIdSum->WPDRes.end());

llvm/lib/Transforms/Utils/FunctionImportUtils.cpp

if (GlobalVariable *V = dyn_cast<GlobalVariable>(&GV)) {
       // same-named locals in different but same-named source files that were
       // compiled in their respective directories (so the source file name
       // and resulting GUID is the same). Find the one in this module.
       // Handle the case where there is no summary found in this module. That
       // can happen in the distributed ThinLTO backend, because the index only
       // contains summaries from the source modules if they are being imported.
       // We might have a non-null VI and get here even in that case if the name
       // matches one in this module (e.g. weak or appending linkage).
-      auto* GVS = dyn_cast_or_null<GlobalVarSummary>(
-          ImportIndex.findSummaryInModule(VI, M.getModuleIdentifier()));      
+      auto *GVS = dyn_cast_or_null<GlobalVarSummary>(
+          ImportIndex.findSummaryInModule(VI, M.getModuleIdentifier()));
       if (GVS &&
           (ImportIndex.isReadOnly(GVS) || ImportIndex.isWriteOnly(GVS))) {
         V->addAttribute("thinlto-internalize");
-        // Objects referenced by writeonly GV initializer should not be 
+        // Objects referenced by writeonly GV initializer should not be
         // promoted, because there is no any kind of read access to them
         // on behalf of this writeonly GV. To avoid promotion we convert
         // GV initializer to 'zeroinitializer'. This effectively drops
         // references in IR module (not in combined index), so we can
         // ignore them when computing import. We do not export references
         // of writeonly object. See computeImportForReferencedGlobals
         if (ImportIndex.isWriteOnly(GVS) && GVS->refs().size())
           V->setInitializer(Constant::getNullValue(V->getValueType()));