Implement caching for the linkage and visibility calculations of

declarations.

The motivation for this patch is that linkage/visibility computations
are linear in the number of redeclarations of an entity, and we've run
into a case where a single translation unit has > 6500 redeclarations
of the same (unused!) external variable. Since each redeclaration
involves a linkage check, the resulting quadratic behavior makes Clang
slow to a crawl. With this change, a simple test with 512
redeclarations of a variable syntax-checks ~20x faster than
before.

That said, I hate this change, and will probably end up reverting it
in a few hours. Reasons to hate it:
  - It makes NamedDecl larger, since we don't have enough free bits in
  Decl to squeeze in the extra information about caching.
  - There are way too many places where we need to invalidate this
  cache, because the visibility of a declaration can change due to
  redeclarations (!). Despite self-hosting and passing the testsuite,
  I have no confidence that I've found all of places where this cache
  needs to be invalidated.

llvm-svn: 120808

1 files changed, 73 insertions, 2 deletions

diff --git a/clang/lib/AST/Decl.cpp b/clang/lib/AST/Decl.cpp
index 9664fe26849..19fbf69d370 100644
--- a/clang/lib/AST/Decl.cpp
+++ b/clang/lib/AST/Decl.cpp
@@ -526,7 +526,57 @@ static LinkageInfo getLVForClassMember(const NamedDecl *D, LVFlags F) {
 }
 
 LinkageInfo NamedDecl::getLinkageAndVisibility() const {
-  return getLVForDecl(this, LVFlags());
+  // If we have already cached linkage and visibility, just return the
+  // cached information.
+  if (HasLinkageAndVisibilityCached) {
+#ifndef NDEBUG
+    LinkageInfo LI = getLVForDecl(this, LVFlags());
+    assert(LI.visibility() == CachedVisibility);
+    assert(LI.visibilityExplicit() == CachedVisibilityIsExplicit);
+    assert(LI.linkage() == CachedLinkage);
+#endif
+    return LinkageInfo(Linkage(CachedLinkage), Visibility(CachedVisibility),
+                       CachedVisibilityIsExplicit);
+  }
+  
+  LinkageInfo LI = getLVForDecl(this, LVFlags());
+  HasLinkageAndVisibilityCached = 1;
+  CachedVisibility = LI.visibility();
+  CachedVisibilityIsExplicit = LI.visibilityExplicit();
+  CachedLinkage = LI.linkage();
+  return LI;
+}
+
+void NamedDecl::ClearLinkageAndVisibilityCache() {
+  HasLinkageAndVisibilityCached = 0;
+  
+  if (VarDecl *VD = dyn_cast<VarDecl>(this)) {
+    for (VarDecl::redecl_iterator R = VD->redecls_begin(),
+                               REnd = VD->redecls_end();
+         R != REnd; ++R)
+      R->HasLinkageAndVisibilityCached = 0;
+    
+    return;
+  }
+  
+  if (FunctionDecl *FD = dyn_cast<FunctionDecl>(this)) {
+    for (FunctionDecl::redecl_iterator R = FD->redecls_begin(),
+                                    REnd = FD->redecls_end();
+         R != REnd; ++R)
+      R->HasLinkageAndVisibilityCached = 0;
+    
+    return;
+  }
+  
+  // Changing the linkage or visibility of a C++ class affect the linkage and
+  // visibility of all of its members. Clear their caches, too.
+  if (CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(this)) {
+    for (DeclContext::decl_iterator D = RD->decls_begin(),
+                                 DEnd = RD->decls_end();
+         D != DEnd; ++D)
+      if (NamedDecl *ND = dyn_cast<NamedDecl>(*D))
+        ND->ClearLinkageAndVisibilityCache();
+  }
 }
 
 static LinkageInfo getLVForDecl(const NamedDecl *D, LVFlags Flags) {
@@ -878,6 +928,14 @@ VarDecl *VarDecl::Create(ASTContext &C, DeclContext *DC, SourceLocation L,
   return new (C) VarDecl(Var, DC, L, Id, T, TInfo, S, SCAsWritten);
 }
 
+void VarDecl::setStorageClass(StorageClass SC) {
+  assert(isLegalForVariable(SC));
+  if (SClass != SC)
+    ClearLinkageAndVisibilityCache();
+  
+  SClass = SC;
+}
+
 SourceLocation VarDecl::getInnerLocStart() const {
   SourceLocation Start = getTypeSpecStartLoc();
   if (Start.isInvalid())
@@ -1096,6 +1154,7 @@ void VarDecl::setTemplateSpecializationKind(TemplateSpecializationKind TSK,
       PointOfInstantiation.isValid() &&
       MSI->getPointOfInstantiation().isInvalid())
     MSI->setPointOfInstantiation(PointOfInstantiation);
+  ClearLinkageAndVisibilityCache();
 }
 
 //===----------------------------------------------------------------------===//
@@ -1196,8 +1255,10 @@ Stmt *FunctionDecl::getBody(const FunctionDecl *&Definition) const {
 
 void FunctionDecl::setBody(Stmt *B) {
   Body = B;
-  if (B)
+  if (B) {
     EndRangeLoc = B->getLocEnd();
+    ClearLinkageAndVisibilityCache();
+  }
 }
 
 void FunctionDecl::setPure(bool P) {
@@ -1278,6 +1339,14 @@ FunctionDecl *FunctionDecl::getCanonicalDecl() {
   return getFirstDeclaration();
 }
 
+void FunctionDecl::setStorageClass(StorageClass SC) {
+  assert(isLegalForFunction(SC));
+  if (SClass != SC)
+    ClearLinkageAndVisibilityCache();
+  
+  SClass = SC;
+}
+
 /// \brief Returns a value indicating whether this function
 /// corresponds to a builtin function.
 ///
@@ -1710,6 +1779,7 @@ FunctionDecl::setTemplateSpecializationKind(TemplateSpecializationKind TSK,
       MSInfo->setPointOfInstantiation(PointOfInstantiation);
   } else
     assert(false && "Function cannot have a template specialization kind");
+  ClearLinkageAndVisibilityCache();
 }
 
 SourceLocation FunctionDecl::getPointOfInstantiation() const {
@@ -1788,6 +1858,7 @@ void TagDecl::setTypedefForAnonDecl(TypedefDecl *TDD) {
   TypedefDeclOrQualifier = TDD; 
   if (TypeForDecl)
     TypeForDecl->ClearLinkageCache();
+  ClearLinkageAndVisibilityCache();
 }
 
 void TagDecl::startDefinition() {