From 2357207a5753547740c70a12c3b37f71afa93f8a Mon Sep 17 00:00:00 2001 From: Douglas Gregor Date: Fri, 3 Dec 2010 17:11:42 +0000 Subject: [PATCH] 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. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@120808 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/AST/Decl.h | 95 ++++++++++++++++++++++++++--- include/clang/AST/DeclBase.h | 9 +-- include/clang/AST/DeclTemplate.h | 2 + include/clang/AST/Redeclarable.h | 22 +------ lib/AST/Decl.cpp | 75 ++++++++++++++++++++++- lib/AST/DeclBase.cpp | 32 ++++++++++ lib/AST/DeclCXX.cpp | 2 + lib/Serialization/ASTReaderDecl.cpp | 4 +- 8 files changed, 200 insertions(+), 41 deletions(-) diff --git a/include/clang/AST/Decl.h b/include/clang/AST/Decl.h index 9540804e3a..fca141a6b8 100644 --- a/include/clang/AST/Decl.h +++ b/include/clang/AST/Decl.h @@ -99,10 +99,25 @@ class NamedDecl : public Decl { /// constructor, Objective-C selector, etc.) DeclarationName Name; + /// \brief Whether we have already cached linkage and visibility. + mutable unsigned HasLinkageAndVisibilityCached : 1; + + /// \brief The cached visibility, if \c HasLinkageAndVisibilityCached is + /// non-zero. + mutable unsigned CachedVisibility : 2; + + /// \brief Whether the cached visibility was explicitly placed on this + /// declaration. + mutable unsigned CachedVisibilityIsExplicit : 1; + + /// \brief The cached linkage, if \c HasLinkageAndVisibilityCached is + /// non-zero. + mutable unsigned CachedLinkage : 2; + protected: NamedDecl(Kind DK, DeclContext *DC, SourceLocation L, DeclarationName N) - : Decl(DK, DC, L), Name(N) { } - + : Decl(DK, DC, L), Name(N), HasLinkageAndVisibilityCached(0) { } + public: /// getIdentifier - Get the identifier that names this declaration, /// if there is one. This will return NULL if this declaration has @@ -272,6 +287,13 @@ public: /// \brief Determines the linkage and visibility of this entity. LinkageInfo getLinkageAndVisibility() const; + /// \brief Clear the linkage and visibility cache in response to a change + /// to the declaration. + /// + /// \param Redeclarations When true, we also have to clear out the linkage + /// and visibility cache for all redeclarations. + void ClearLinkageAndVisibilityCache(); + /// \brief Looks through UsingDecls and ObjCCompatibleAliasDecls for /// the underlying named decl. NamedDecl *getUnderlyingDecl(); @@ -625,6 +647,8 @@ private: bool NRVOVariable : 1; friend class StmtIteratorBase; + friend class ASTDeclReader; + protected: VarDecl(Kind DK, DeclContext *DC, SourceLocation L, IdentifierInfo *Id, QualType T, TypeSourceInfo *TInfo, StorageClass SC, @@ -660,10 +684,7 @@ public: StorageClass getStorageClassAsWritten() const { return (StorageClass) SClassAsWritten; } - void setStorageClass(StorageClass SC) { - assert(isLegalForVariable(SC)); - SClass = SC; - } + void setStorageClass(StorageClass SC); void setStorageClassAsWritten(StorageClass SC) { assert(isLegalForVariable(SC)); SClassAsWritten = SC; @@ -1478,10 +1499,7 @@ public: } StorageClass getStorageClass() const { return StorageClass(SClass); } - void setStorageClass(StorageClass SC) { - assert(isLegalForFunction(SC)); - SClass = SC; - } + void setStorageClass(StorageClass SC); StorageClass getStorageClassAsWritten() const { return StorageClass(SClassAsWritten); @@ -2545,6 +2563,63 @@ inline const DiagnosticBuilder &operator<<(const DiagnosticBuilder &DB, return DB; } +template +void Redeclarable::setPreviousDeclaration(decl_type *PrevDecl) { + // Note: This routine is implemented here because we need both NamedDecl + // and Redeclarable to be defined. + decl_type *First; + + if (PrevDecl) { + // Point to previous. Make sure that this is actually the most recent + // redeclaration, or we can build invalid chains. If the most recent + // redeclaration is invalid, it won't be PrevDecl, but we want it anyway. + RedeclLink = PreviousDeclLink(llvm::cast( + PrevDecl->getMostRecentDeclaration())); + First = PrevDecl->getFirstDeclaration(); + assert(First->RedeclLink.NextIsLatest() && "Expected first"); + } else { + // Make this first. + First = static_cast(this); + } + + // First one will point to this one as latest. + First->RedeclLink = LatestDeclLink(static_cast(this)); + + // If this declaration has a visibility attribute that differs from the + // previous visibility attribute, or has private extern storage while the + // previous declaration merely had extern storage, clear out the linkage and + ///visibility cache. This is required because declarations after the first + // declaration can change the visibility for all previous and future + // declarations. + if (NamedDecl *ND = dyn_cast(static_cast(this))) { + bool MustClear = false; + if (VisibilityAttr *Visibility = ND->getAttr()) { + VisibilityAttr *PrevVisibility + = PrevDecl->template getAttr(); + if (!PrevVisibility || + PrevVisibility->getVisibility() != Visibility->getVisibility()) + MustClear = true; + } + + if (!MustClear) { + if (VarDecl *VD = dyn_cast(ND)) { + if (VD->getStorageClass() != cast(PrevDecl)->getStorageClass()) + MustClear = true; + } else if (FunctionDecl *FD = dyn_cast(ND)) { + FunctionDecl *PrevFD = cast(PrevDecl); + if (FD->getStorageClass() != PrevFD->getStorageClass()) + MustClear = true; + else if (FD->isInlineSpecified() && !PrevFD->isInlined()) + MustClear = true; + } + } + + if (MustClear) + ND->ClearLinkageAndVisibilityCache(); + } +} + + } // end namespace clang #endif diff --git a/include/clang/AST/DeclBase.h b/include/clang/AST/DeclBase.h index 0aa60ce978..699950ef6b 100644 --- a/include/clang/AST/DeclBase.h +++ b/include/clang/AST/DeclBase.h @@ -198,7 +198,7 @@ private: return DeclCtx.get(); } - /// Loc - The location that this decl. + /// Loc - The location of this decl. SourceLocation Loc; /// DeclKind - This indicates which class this is. @@ -316,12 +316,7 @@ public: void swapAttrs(Decl *D); void dropAttrs(); - void addAttr(Attr *A) { - if (hasAttrs()) - getAttrs().push_back(A); - else - setAttrs(AttrVec(1, A)); - } + void addAttr(Attr *A); typedef AttrVec::const_iterator attr_iterator; diff --git a/include/clang/AST/DeclTemplate.h b/include/clang/AST/DeclTemplate.h index bde2e24e19..9d743200c0 100644 --- a/include/clang/AST/DeclTemplate.h +++ b/include/clang/AST/DeclTemplate.h @@ -1241,6 +1241,8 @@ public: } void setSpecializationKind(TemplateSpecializationKind TSK) { + if (SpecializationKind != TSK) + ClearLinkageAndVisibilityCache(); SpecializationKind = TSK; } diff --git a/include/clang/AST/Redeclarable.h b/include/clang/AST/Redeclarable.h index ba778293ba..4a1c1d0018 100644 --- a/include/clang/AST/Redeclarable.h +++ b/include/clang/AST/Redeclarable.h @@ -109,26 +109,8 @@ public: /// \brief Set the previous declaration. If PrevDecl is NULL, set this as the /// first and only declaration. - void setPreviousDeclaration(decl_type *PrevDecl) { - decl_type *First; - - if (PrevDecl) { - // Point to previous. Make sure that this is actually the most recent - // redeclaration, or we can build invalid chains. If the most recent - // redeclaration is invalid, it won't be PrevDecl, but we want it anyway. - RedeclLink = PreviousDeclLink(llvm::cast( - PrevDecl->getMostRecentDeclaration())); - First = PrevDecl->getFirstDeclaration(); - assert(First->RedeclLink.NextIsLatest() && "Expected first"); - } else { - // Make this first. - First = static_cast(this); - } - - // First one will point to this one as latest. - First->RedeclLink = LatestDeclLink(static_cast(this)); - } - + void setPreviousDeclaration(decl_type *PrevDecl); + /// \brief Iterates through all the redeclarations of the same decl. class redecl_iterator { /// Current - The current declaration. diff --git a/lib/AST/Decl.cpp b/lib/AST/Decl.cpp index 9664fe2684..19fbf69d37 100644 --- a/lib/AST/Decl.cpp +++ b/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(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(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(this)) { + for (DeclContext::decl_iterator D = RD->decls_begin(), + DEnd = RD->decls_end(); + D != DEnd; ++D) + if (NamedDecl *ND = dyn_cast(*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() { diff --git a/lib/AST/DeclBase.cpp b/lib/AST/DeclBase.cpp index 843e907dea..3758ca1065 100644 --- a/lib/AST/DeclBase.cpp +++ b/lib/AST/DeclBase.cpp @@ -337,6 +337,38 @@ void Decl::dropAttrs() { getASTContext().eraseDeclAttrs(this); } +void Decl::addAttr(Attr *A) { + if (NamedDecl *ND = dyn_cast(this)) + if (VisibilityAttr *Visibility = dyn_cast(A)) { + bool ClearVisibility = true; + if (VarDecl *VD = dyn_cast(this)) { + if (VD->getPreviousDeclaration()) { + VisibilityAttr *PrevVisibility + = VD->getPreviousDeclaration()->getAttr(); + if (PrevVisibility && + PrevVisibility->getVisibility() == Visibility->getVisibility()) + ClearVisibility = false; + } + } else if (FunctionDecl *FD = dyn_cast(this)) { + if (FD->getPreviousDeclaration()) { + VisibilityAttr *PrevVisibility + = FD->getPreviousDeclaration()->getAttr(); + if (PrevVisibility && + PrevVisibility->getVisibility() == Visibility->getVisibility()) + ClearVisibility = false; + } + } + + if (ClearVisibility) + ND->ClearLinkageAndVisibilityCache(); + } + + if (hasAttrs()) + getAttrs().push_back(A); + else + setAttrs(AttrVec(1, A)); +} + const AttrVec &Decl::getAttrs() const { assert(HasAttrs && "No attrs to get!"); return getASTContext().getDeclAttrs(this); diff --git a/lib/AST/DeclCXX.cpp b/lib/AST/DeclCXX.cpp index 547a70a7a5..9e9b5ab7ea 100644 --- a/lib/AST/DeclCXX.cpp +++ b/lib/AST/DeclCXX.cpp @@ -792,6 +792,8 @@ CXXRecordDecl::setTemplateSpecializationKind(TemplateSpecializationKind TSK) { } if (MemberSpecializationInfo *MSInfo = getMemberSpecializationInfo()) { + if (MSInfo->getTemplateSpecializationKind() != TSK) + ClearLinkageAndVisibilityCache(); MSInfo->setTemplateSpecializationKind(TSK); return; } diff --git a/lib/Serialization/ASTReaderDecl.cpp b/lib/Serialization/ASTReaderDecl.cpp index b1e46a623e..c21dfc2b1f 100644 --- a/lib/Serialization/ASTReaderDecl.cpp +++ b/lib/Serialization/ASTReaderDecl.cpp @@ -383,7 +383,7 @@ void ASTDeclReader::VisitFunctionDecl(FunctionDecl *FD) { // FunctionDecl's body is handled last at ASTDeclReader::Visit, // after everything else is read. - FD->setStorageClass((StorageClass)Record[Idx++]); + FD->SClass = (StorageClass)Record[Idx++]; FD->setStorageClassAsWritten((StorageClass)Record[Idx++]); FD->setInlineSpecified(Record[Idx++]); FD->setVirtualAsWritten(Record[Idx++]); @@ -650,7 +650,7 @@ void ASTDeclReader::VisitIndirectFieldDecl(IndirectFieldDecl *FD) { void ASTDeclReader::VisitVarDecl(VarDecl *VD) { VisitDeclaratorDecl(VD); VisitRedeclarable(VD); - VD->setStorageClass((StorageClass)Record[Idx++]); + VD->SClass = (StorageClass)Record[Idx++]; VD->setStorageClassAsWritten((StorageClass)Record[Idx++]); VD->setThreadSpecified(Record[Idx++]); VD->setCXXDirectInitializer(Record[Idx++]); -- 2.40.0