[NFC] Introduce ASTContext::isInSameModule()

[ChuanqiXu]

Summary

Previously, when we want to compare if two module units are in the same module, we need to compare their primary module name, which is string comparing. String comparing is expensive and we want to avoid it. So here is the patch. This one should be a NFC patch.

[erichkeane]

clang/lib/AST/ASTContext.cpp

6217

Please find another way to write this... this is about the most jarring way to compare these...

perhaps you can take advantage of the fact that the compare on 6222 basically does the other half to this:

if (!X || !Y)

replaces the next compare as well.

6232

Doesn't FindAndConstruct do something pretty similar here? This lambda is incredibly inefficient as it requires two 3 separate lookups into the map.

Instead, I believe FindAndConstruct will create a new entry (which can be 'set' if necessary', and then have its value returned.

[ChuanqiXu]

Address comments.

[ChuanqiXu]

clang/lib/AST/ASTContext.cpp

6232

On the one hand, FindAndConstruct would construct an empty value, which is not we want. We want the value to be a hash_value of the name. On the other hand, your comments makes sense the implementation could be optimized. Currently, there would be at most 2 lookups and the number should be 1 at the hot path.

[ilya-biryukov]

Thanks for working on this. I have a few major concerns here:

• Do we know that it's a bottleneck in practice? E.g. if the module name have different sizes, comparing strings is actually fast. If the module names are short, we are also in a pretty good situation. Having some benchmarks numbers would help to quantify whether the change is needed.
• llvm::hash_value is not a crypto hash, so we should expect collisions from it. OTOH, doing an extra string comparison when hashes match defeats the purpose of this optimization. Collisions are rare, but if someone hits one after the compiler is released there are literally no workarounds. Instead we can use llvm::SHA1 or llvm::SHA256. (possibly truncated to 128 bits? it's hard to tell how much this is needed without benchmarks.)
• Why not store the hash directly inside Module and compute it on construction after setting name? If we want these comparisons to be fast, we probably want to avoid even the overhead of hash table access.

[ChuanqiXu]

In D130864#3693019, @ilya-biryukov wrote:

Thanks for working on this. I have a few major concerns here:

• Do we know that it's a bottleneck in practice? E.g. if the module name have different sizes, comparing strings is actually fast. If the module names are short, we are also in a pretty good situation. Having some benchmarks numbers would help to quantify whether the change is needed.

No, we don't know it is a bottleneck in practice. (Currently there shouldn't be many users for C++20 Modules). The reason to do this is that we (Iain and me) feel bad to compare string frequently. Benchmarks would be good but I am afraid I can't. Since there are not enough existing benchmarks and it looks costful to construct the meaningful benchmarks. Let's not make the perfect to be the enemy of better.

• llvm::hash_value is not a crypto hash, so we should expect collisions from it. OTOH, doing an extra string comparison when hashes match defeats the purpose of this optimization. Collisions are rare, but if someone hits one after the compiler is released there are literally no workarounds. Instead we can use llvm::SHA1 or llvm::SHA256. (possibly truncated to 128 bits? it's hard to tell how much this is needed without benchmarks.)
• Why not store the hash directly inside Module and compute it on construction after setting name? If we want these comparisons to be fast, we probably want to avoid even the overhead of hash table access.

Good idea. Will try to do.

[iains]

In D130864#3693022, @ChuanqiXu wrote:

In D130864#3693019, @ilya-biryukov wrote:

Thanks for working on this. I have a few major concerns here:

• Do we know that it's a bottleneck in practice? E.g. if the module name have different sizes, comparing strings is actually fast. If the module names are short, we are also in a pretty good situation. Having some benchmarks numbers would help to quantify whether the change is needed.

No, we don't know it is a bottleneck in practice. (Currently there shouldn't be many users for C++20 Modules). The reason to do this is that we (Iain and me) feel bad to compare string frequently. Benchmarks would be good but I am afraid I can't. Since there are not enough existing benchmarks and it looks costful to construct the meaningful benchmarks. Let's not make the perfect to be the enemy of better.

We do not have benchmarks, it is true - initially, it seemed that the problem would be confined to the case of checking for the parent of a module partition which would be no concern - since it is one check per TU). However, in later parts of the implementation it has become necessary to check when merging or comparing individual decls - and that is a concern.

• llvm::hash_value is not a crypto hash, so we should expect collisions from it. OTOH, doing an extra string comparison when hashes match defeats the purpose of this optimization. Collisions are rare, but if someone hits one after the compiler is released there are literally no workarounds. Instead we can use llvm::SHA1 or llvm::SHA256. (possibly truncated to 128 bits? it's hard to tell how much this is needed without benchmarks.)
• Why not store the hash directly inside Module and compute it on construction after setting name? If we want these comparisons to be fast, we probably want to avoid even the overhead of hash table access.

Good idea. Will try to do.

+1.
if the string is stored locally to the Module, then would it not be sufficient to compare the address?
edit: ignore the second, that will not work.

clang/include/clang/AST/ASTContext.h

class ASTContext : public RefCountedBase<ASTContext> {
   ///
   /// This is lazily created.  This is intentionally not serialized.
   mutable llvm::StringMap<StringLiteral *> StringLiteralCache;
 
   /// MD5 hash of CUID. It is calculated when first used and cached by this
   /// data member.
   mutable std::string CUIDHash;
 
+  /// A cache mapping modules to the hash value of their primary module name.
+  ///
+  /// This is lazily created.  This is intentionally not serialized.
+  mutable llvm::DenseMap<const Module *, llvm::hash_code> PrimaryModuleHash;
+
   /// Representation of a "canonical" template template parameter that
   /// is used in canonical template names.
   class CanonicalTemplateTemplateParm : public llvm::FoldingSetNode {
     TemplateTemplateParmDecl *Parm;
 
   public:
     CanonicalTemplateTemplateParm(TemplateTemplateParmDecl *Parm)
         : Parm(Parm) {}
void mergeDefinitionIntoModule(NamedDecl *ND, Module *M,
                                  bool NotifyListeners = true);
 
   /// Clean up the merged definition list. Call this if you might have
   /// added duplicates into the list.
   void deduplicateMergedDefinitonsFor(NamedDecl *ND);
 
   /// Get the additional modules in which the definition \p Def has
   /// been merged.
-  ArrayRef<Module*> getModulesWithMergedDefinition(const NamedDecl *Def);
+  ArrayRef<Module *> getModulesWithMergedDefinition(const NamedDecl *Def) const;
 
   /// Add a declaration to the list of declarations that are initialized
   /// for a module. This will typically be a global variable (with internal
   /// linkage) that runs module initializers, such as the iostream initializer,
   /// or an ImportDecl nominating another module that has initializers.
   void addModuleInitializer(Module *M, Decl *Init);
 
   void addLazyModuleInitializers(Module *M, ArrayRef<uint32_t> IDs);
public:
   bool isSameTypeConstraint(const TypeConstraint *XTC,
                             const TypeConstraint *YTC) const;
 
   /// Determine whether two default template arguments are similar enough
   /// that they may be used in declarations of the same template.
   bool isSameDefaultTemplateArgument(const NamedDecl *X,
                                      const NamedDecl *Y) const;
 
+  /// Determine whether two module units lives in the same module.
+  /// Note that the term `Module` in implementation has different meanings
+  /// with the term in C++ spec. In C++ spec, a module could consist of
+  /// multiple module units and a module unit could consist of some of module
+  /// fragment. But `Module` in the implementation could be a clang map module,
+  /// header unit, a module unit or a module fragment.
+  bool isInSameModule(const Module *X, const Module *Y) const;
+
   /// Retrieve the "canonical" template argument.
   ///
   /// The canonical template argument is the simplest template argument
   /// (which may be a type, value, expression, or declaration) that
   /// expresses the value of the argument.
   TemplateArgument getCanonicalTemplateArgument(const TemplateArgument &Arg)
     const;
 

clang/include/clang/Sema/Sema.h

private:
 
   /// Enter the scope of the global module.
   Module *PushGlobalModuleFragment(SourceLocation BeginLoc, bool IsImplicit);
   /// Leave the scope of the global module.
   void PopGlobalModuleFragment();
 
   VisibleModuleSet VisibleModules;
 
-  /// Cache for module units which is usable for current module.
-  llvm::DenseSet<const Module *> UsableModuleUnitsCache;
-
-  bool isUsableModule(const Module *M);
+  bool isUsableModule(const Module *M) const;
 
   bool isAcceptableSlow(const NamedDecl *D, AcceptableKind Kind);
 
 public:
   /// Get the module unit whose scope we are currently within.
   Module *getCurrentModule() const {
     return ModuleScopes.empty() ? nullptr : ModuleScopes.back().Module;
   }
public:
   hasReachableDeclaration(const NamedDecl *D,
                           llvm::SmallVectorImpl<Module *> *Modules = nullptr) {
     return isReachable(D) || hasReachableDeclarationSlow(D, Modules);
   }
   bool hasReachableDeclarationSlow(
       const NamedDecl *D, llvm::SmallVectorImpl<Module *> *Modules = nullptr);
 
   bool hasVisibleMergedDefinition(NamedDecl *Def);
-  bool hasMergedDefinitionInCurrentModule(NamedDecl *Def);
+  bool hasMergedDefinitionInCurrentModule(NamedDecl *Def) const;
 
   /// Determine if \p D and \p Suggested have a structurally compatible
   /// layout as described in C11 6.2.7/1.
   bool hasStructuralCompatLayout(Decl *D, Decl *Suggested);
 
   /// Determine if \p D has a visible definition. If not, suggest a declaration
   /// that should be made visible to expose the definition.
   bool hasVisibleDefinition(NamedDecl *D, NamedDecl **Suggested,

clang/lib/AST/ASTContext.cpp

void ASTContext::deduplicateMergedDefinitonsFor(NamedDecl *ND) {
   llvm::DenseSet<Module*> Found;
   for (Module *&M : Merged)
     if (!Found.insert(M).second)
       M = nullptr;
   llvm::erase_value(Merged, nullptr);
 }
 
 ArrayRef<Module *>
-ASTContext::getModulesWithMergedDefinition(const NamedDecl *Def) {
+ASTContext::getModulesWithMergedDefinition(const NamedDecl *Def) const {
   auto MergedIt =
       MergedDefModules.find(cast<NamedDecl>(Def->getCanonicalDecl()));
   if (MergedIt == MergedDefModules.end())
     return None;
   return MergedIt->second;
 }
 
 void ASTContext::PerModuleInitializers::resolve(ASTContext &Ctx) {
TemplateArgument canonArgPack
       = getCanonicalTemplateArgument(subst->getArgumentPack());
     return getSubstTemplateTemplateParmPack(canonParameter, canonArgPack);
   }
   }
 
   llvm_unreachable("bad template name!");
 }
 
+bool ASTContext::isInSameModule(const Module *X, const Module *Y) const {
+  // If either one is not module unit, they must not be in the same module.
+  if (!X || !Y)
+    return false;
+
+  if (X == Y)
+    return true;
+
+  /// A header module won't be in the same module with a different address.
+  if (X->isHeaderLikeModule() || Y->isHeaderLikeModule())
+    return false;
+
+  auto getHashValueForPrimaryModule = [this](const Module *M) {
+    auto Iter = PrimaryModuleHash.find(M);
+    if (Iter == PrimaryModuleHash.end()) {
+      auto HashValue = llvm::hash_value(M->getPrimaryModuleInterfaceName());
+      PrimaryModuleHash.insert({M, HashValue});
+      return HashValue;
+    }
+    return Iter->second;
+  };
+
+  return getHashValueForPrimaryModule(X) == getHashValueForPrimaryModule(Y);
+}
+
 bool ASTContext::hasSameTemplateName(const TemplateName &X,
                                      const TemplateName &Y) const {
   return getCanonicalTemplateName(X).getAsVoidPointer() ==
          getCanonicalTemplateName(Y).getAsVoidPointer();
 }
 
 bool ASTContext::isSameConstraintExpr(const Expr *XCE, const Expr *YCE) const {
   if (!XCE != !YCE)

clang/lib/Sema/SemaDecl.cpp

if (OldM && OldM->isPrivateModule())
     OldM = OldM->Parent;
 
   if (NewM == OldM)
     return false;
 
   // Partitions are part of the module, but a partition could import another
   // module, so verify that the PMIs agree.
   if (NewM && OldM && (NewM->isModulePartition() || OldM->isModulePartition()))
-    return NewM->getPrimaryModuleInterfaceName() ==
-           OldM->getPrimaryModuleInterfaceName();
+    return getASTContext().isInSameModule(NewM, OldM);
 
   bool NewIsModuleInterface = NewM && NewM->isModulePurview();
   bool OldIsModuleInterface = OldM && OldM->isModulePurview();
   if (NewIsModuleInterface || OldIsModuleInterface) {
     // C++ Modules TS [basic.def.odr] 6.2/6.7 [sic]:
     //   if a declaration of D [...] appears in the purview of a module, all
     //   other such declarations shall appear in the purview of the same module
     Diag(New->getLocation(), diag::err_mismatched_owning_module)

clang/lib/Sema/SemaLookup.cpp

for (unsigned I = CodeSynthesisContextLookupModules.size();
     if (M && !LookupModulesCache.insert(M).second)
       M = nullptr;
     CodeSynthesisContextLookupModules.push_back(M);
   }
   return LookupModulesCache;
 }
 
 /// Determine if we could use all the declarations in the module.
-bool Sema::isUsableModule(const Module *M) {
+bool Sema::isUsableModule(const Module *M) const {
   assert(M && "We shouldn't check nullness for module here");
-  // Return quickly if we cached the result.
-  if (UsableModuleUnitsCache.count(M))
-    return true;
 
   // If M is the global module fragment of the current translation unit. So it
   // should be usable.
   // [module.global.frag]p1:
   //   The global module fragment can be used to provide declarations that are
   //   attached to the global module and usable within the module unit.
-  if (M == GlobalModuleFragment ||
-      // If M is the module we're parsing, it should be usable. This covers the
-      // private module fragment. The private module fragment is usable only if
-      // it is within the current module unit. And it must be the current
-      // parsing module unit if it is within the current module unit according
-      // to the grammar of the private module fragment. NOTE: This is covered by
-      // the following condition. The intention of the check is to avoid string
-      // comparison as much as possible.
-      M == getCurrentModule() ||
-      // The module unit which is in the same module with the current module
-      // unit is usable.
-      //
-      // FIXME: Here we judge if they are in the same module by comparing the
-      // string. Is there any better solution?
-      M->getPrimaryModuleInterfaceName() ==
-          llvm::StringRef(getLangOpts().CurrentModule).split(':').first) {
-    UsableModuleUnitsCache.insert(M);
-    return true;
-  }
-
-  return false;
+  //
+  // the following condition. The intention of the check is to avoid
+  // expensive comparison as much as possible.
+  //
+  return isModuleUnitOfCurrentTU(M) ||
+         getASTContext().isInSameModule(M, getCurrentModule());
 }
 
 bool Sema::hasVisibleMergedDefinition(NamedDecl *Def) {
   for (const Module *Merged : Context.getModulesWithMergedDefinition(Def))
     if (isModuleVisible(Merged))
       return true;
   return false;
 }
 
-bool Sema::hasMergedDefinitionInCurrentModule(NamedDecl *Def) {
+bool Sema::hasMergedDefinitionInCurrentModule(NamedDecl *Def) const {
   for (const Module *Merged : Context.getModulesWithMergedDefinition(Def))
     if (isUsableModule(Merged))
       return true;
   return false;
 }
 
 template <typename ParmDecl>
 static bool