From 4f1bb5e1949ccdbd7b272c6ebca35d0b81a8645d Mon Sep 17 00:00:00 2001 From: George Burgess IV Date: Wed, 9 Aug 2017 04:12:17 +0000 Subject: [PATCH] [AST] Cache intermediate visibility/linkage results This is a follow-up to r310436 with actual functional changes. Please see that commit message for a description of why a cache is appearing here. Suggestions for less-bad ways of testing this are appreciated. :) This fixes PR29160. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@310437 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/AST/Decl.cpp | 12 +++++++---- lib/AST/Linkage.h | 43 +++++++++++++++++++++++++++++++++++++ lib/AST/Type.cpp | 4 ++-- test/CodeGenCXX/pr29160.cpp | 41 +++++++++++++++++++++++++++++++++++ 4 files changed, 94 insertions(+), 6 deletions(-) create mode 100644 test/CodeGenCXX/pr29160.cpp diff --git a/lib/AST/Decl.cpp b/lib/AST/Decl.cpp index 317b493ad6..a3bb025eaa 100644 --- a/lib/AST/Decl.cpp +++ b/lib/AST/Decl.cpp @@ -192,7 +192,7 @@ LinkageInfo LinkageComputer::getLVForType(const Type &T, LVComputationKind computation) { if (computation == LVForLinkageOnly) return LinkageInfo(T.getLinkage(), DefaultVisibility, true); - return T.getLinkageAndVisibility(); + return getTypeLinkageAndVisibility(&T); } /// \brief Get the most restrictive linkage for the types in the given @@ -224,7 +224,7 @@ LinkageInfo LinkageComputer::getLVForTemplateParameterList( for (unsigned i = 0, n = NTTP->getNumExpansionTypes(); i != n; ++i) { QualType type = NTTP->getExpansionType(i); if (!type->isDependentType()) - LV.merge(type->getLinkageAndVisibility()); + LV.merge(getTypeLinkageAndVisibility(type)); } continue; } @@ -291,7 +291,7 @@ LinkageComputer::getLVForTemplateArgumentList(ArrayRef Args, continue; case TemplateArgument::NullPtr: - LV.merge(Arg.getNullPtrType()->getLinkageAndVisibility()); + LV.merge(getTypeLinkageAndVisibility(Arg.getNullPtrType())); continue; case TemplateArgument::Template: @@ -610,7 +610,7 @@ LinkageComputer::getLVForNamespaceScopeDecl(const NamedDecl *D, PrevVar = PrevVar->getPreviousDecl()) { if (PrevVar->getStorageClass() == SC_PrivateExtern && Var->getStorageClass() == SC_None) - return PrevVar->getLinkageAndVisibility(); + return getDeclLinkageAndVisibility(PrevVar); // Explicitly declared static. if (PrevVar->getStorageClass() == SC_Static) return getInternalLinkageFor(Var); @@ -1358,11 +1358,15 @@ LinkageInfo LinkageComputer::getLVForDecl(const NamedDecl *D, if (computation == LVForLinkageOnly && D->hasCachedLinkage()) return LinkageInfo(D->getCachedLinkage(), DefaultVisibility, false); + if (llvm::Optional LI = lookup(D, computation)) + return *LI; + LinkageInfo LV = computeLVForDecl(D, computation); if (D->hasCachedLinkage()) assert(D->getCachedLinkage() == LV.getLinkage()); D->setCachedLinkage(LV.getLinkage()); + cache(D, computation, LV); #ifndef NDEBUG // In C (because of gnu inline) and in c++ with microsoft extensions an diff --git a/lib/AST/Linkage.h b/lib/AST/Linkage.h index 592002e089..5f3458dfb6 100644 --- a/lib/AST/Linkage.h +++ b/lib/AST/Linkage.h @@ -19,6 +19,7 @@ #include "clang/AST/DeclCXX.h" #include "clang/AST/Type.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/Optional.h" namespace clang { enum : unsigned { @@ -54,8 +55,50 @@ enum LVComputationKind { LVForLinkageOnly = LVForValue | IgnoreExplicitVisibilityBit | IgnoreAllVisibilityBit }; +} // namespace clang + +namespace llvm { +template <> struct DenseMapInfo { + static inline clang::LVComputationKind getEmptyKey() { + return static_cast(-1); + } + static inline clang::LVComputationKind getTombstoneKey() { + return static_cast(-2); + } + static unsigned getHashValue(const clang::LVComputationKind &Val) { + return Val; + } + static bool isEqual(const clang::LVComputationKind &LHS, + const clang::LVComputationKind &RHS) { + return LHS == RHS; + } +}; +} // namespace llvm +namespace clang { class LinkageComputer { + // We have a cache for repeated linkage/visibility computations. This saves us + // from exponential behavior in heavily templated code, such as: + // + // template struct {}; + // using A = int; + // using B = Foo; + // using C = Foo; + // using D = Foo; + using QueryType = std::pair; + llvm::SmallDenseMap CachedLinkageInfo; + llvm::Optional lookup(const NamedDecl *ND, + LVComputationKind Kind) const { + auto Iter = CachedLinkageInfo.find(std::make_pair(ND, Kind)); + if (Iter == CachedLinkageInfo.end()) + return None; + return Iter->second; + } + + void cache(const NamedDecl *ND, LVComputationKind Kind, LinkageInfo Info) { + CachedLinkageInfo[std::make_pair(ND, Kind)] = Info; + } + LinkageInfo getLVForTemplateArgumentList(ArrayRef Args, LVComputationKind computation); diff --git a/lib/AST/Type.cpp b/lib/AST/Type.cpp index 9050e899c6..93510b244f 100644 --- a/lib/AST/Type.cpp +++ b/lib/AST/Type.cpp @@ -3453,7 +3453,7 @@ LinkageInfo LinkageComputer::computeTypeLinkageInfo(const Type *T) { case Type::Record: case Type::Enum: - return cast(T)->getDecl()->getLinkageAndVisibility(); + return getDeclLinkageAndVisibility(cast(T)->getDecl()); case Type::Complex: return computeTypeLinkageInfo(cast(T)->getElementType()); @@ -3487,7 +3487,7 @@ LinkageInfo LinkageComputer::computeTypeLinkageInfo(const Type *T) { return LV; } case Type::ObjCInterface: - return cast(T)->getDecl()->getLinkageAndVisibility(); + return getDeclLinkageAndVisibility(cast(T)->getDecl()); case Type::ObjCObject: return computeTypeLinkageInfo(cast(T)->getBaseType()); case Type::ObjCObjectPointer: diff --git a/test/CodeGenCXX/pr29160.cpp b/test/CodeGenCXX/pr29160.cpp new file mode 100644 index 0000000000..9c9238e8a0 --- /dev/null +++ b/test/CodeGenCXX/pr29160.cpp @@ -0,0 +1,41 @@ +// RUN: %clang_cc1 -std=c++11 %s -o /dev/null -S +// +// This test's failure mode is running ~forever. (For some value of "forever" +// that's greater than 25 minutes on my machine) + +template +struct Foo { + template + static void ignore() {} + Foo() { ignore(); } +}; + +struct Base { + Base(); + ~Base(); +}; + +#define STAMP(thiz, prev) using thiz = Foo< \ + prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, \ + prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, \ + prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev \ + >; +STAMP(A, Base); +STAMP(B, A); +STAMP(C, B); +STAMP(D, C); +STAMP(E, D); +STAMP(F, E); +STAMP(G, F); +STAMP(H, G); +STAMP(I, H); +STAMP(J, I); +STAMP(K, J); +STAMP(L, K); +STAMP(M, L); +STAMP(N, M); +STAMP(O, N); +STAMP(P, O); +STAMP(Q, P); + +int main() { Q q; } -- 2.40.0