Awesome performance numbers! When we discussed this previously, one alternative (should we ever need it; not sure we do) if the memory overhead is excessive is to use a waymarking scheme to find the canonical decl in constant time (unlike Use http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm , we don't have random access, but we can instead take advantage of the stable address of the canonical decl and directly store bits of the stable address).
-- Sean Silva On Wed, Mar 25, 2015 at 4:18 PM, Manuel Klimek <[email protected]> wrote: > Author: klimek > Date: Wed Mar 25 18:18:30 2015 > New Revision: 233228 > > URL: http://llvm.org/viewvc/llvm-project?rev=233228&view=rev > Log: > Keep track of canonical decls in Redeclarable. > > More than 2x speedup on modules builds with large redecl chains. > Roughly 15-20% speedup on non-modules builds for very large TUs. > Between 2-3% cost in memory on large TUs. > > Modified: > cfe/trunk/include/clang/AST/Decl.h > cfe/trunk/include/clang/AST/Redeclarable.h > cfe/trunk/lib/Serialization/ASTReaderDecl.cpp > > Modified: cfe/trunk/include/clang/AST/Decl.h > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/AST/Decl.h?rev=233228&r1=233227&r2=233228&view=diff > > ============================================================================== > --- cfe/trunk/include/clang/AST/Decl.h (original) > +++ cfe/trunk/include/clang/AST/Decl.h Wed Mar 25 18:18:30 2015 > @@ -3738,8 +3738,6 @@ void Redeclarable<decl_type>::setPreviou > assert(RedeclLink.NextIsLatest() && > "setPreviousDecl on a decl already in a redeclaration chain"); > > - 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 > > Modified: cfe/trunk/include/clang/AST/Redeclarable.h > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/AST/Redeclarable.h?rev=233228&r1=233227&r2=233228&view=diff > > ============================================================================== > --- cfe/trunk/include/clang/AST/Redeclarable.h (original) > +++ cfe/trunk/include/clang/AST/Redeclarable.h Wed Mar 25 18:18:30 2015 > @@ -121,14 +121,15 @@ protected: > /// > /// If there is only one declaration, it is <pointer to self, true> > DeclLink RedeclLink; > + decl_type *First; > > decl_type *getNextRedeclaration() const { > return RedeclLink.getNext(static_cast<const decl_type *>(this)); > } > > public: > - Redeclarable(const ASTContext &Ctx) > - : RedeclLink(LatestDeclLink(Ctx)) {} > + Redeclarable(const ASTContext &Ctx) > + : RedeclLink(LatestDeclLink(Ctx)), First(static_cast<decl_type > *>(this)) {} > > /// \brief Return the previous declaration of this declaration or NULL > if this > /// is the first declaration. > @@ -144,21 +145,11 @@ public: > > /// \brief Return the first declaration of this declaration or itself > if this > /// is the only declaration. > - decl_type *getFirstDecl() { > - decl_type *D = static_cast<decl_type*>(this); > - while (D->getPreviousDecl()) > - D = D->getPreviousDecl(); > - return D; > - } > + decl_type *getFirstDecl() { return First; } > > /// \brief Return the first declaration of this declaration or itself > if this > /// is the only declaration. > - const decl_type *getFirstDecl() const { > - const decl_type *D = static_cast<const decl_type*>(this); > - while (D->getPreviousDecl()) > - D = D->getPreviousDecl(); > - return D; > - } > + const decl_type *getFirstDecl() const { return First; } > > /// \brief True if this is the first declaration in its redeclaration > chain. > bool isFirstDecl() const { return RedeclLink.NextIsLatest(); } > > Modified: cfe/trunk/lib/Serialization/ASTReaderDecl.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Serialization/ASTReaderDecl.cpp?rev=233228&r1=233227&r2=233228&view=diff > > ============================================================================== > --- cfe/trunk/lib/Serialization/ASTReaderDecl.cpp (original) > +++ cfe/trunk/lib/Serialization/ASTReaderDecl.cpp Wed Mar 25 18:18:30 2015 > @@ -2106,6 +2106,7 @@ ASTDeclReader::VisitRedeclarable(Redecla > // which is the one that matters and mark the real previous DeclID to > be > // loaded & attached later on. > D->RedeclLink = Redeclarable<T>::PreviousDeclLink(FirstDecl); > + D->First = FirstDecl->getCanonicalDecl(); > } > > // Note that this declaration has been deserialized. > @@ -2209,6 +2210,7 @@ void ASTDeclReader::mergeRedeclarable(Re > // of the existing declaration, so that this declaration has the > // appropriate canonical declaration. > D->RedeclLink = Redeclarable<T>::PreviousDeclLink(ExistingCanon); > + D->First = ExistingCanon; > > // When we merge a namespace, update its pointer to the first > namespace. > // We cannot have loaded any redeclarations of this declaration yet, > so > @@ -2828,6 +2830,7 @@ void ASTDeclReader::attachPreviousDeclIm > Redeclarable<DeclT> *D, > Decl *Previous, Decl *Canon) { > D->RedeclLink.setPrevious(cast<DeclT>(Previous)); > + D->First = cast<DeclT>(Previous)->First; > } > namespace clang { > template<> > @@ -2838,6 +2841,7 @@ void ASTDeclReader::attachPreviousDeclIm > FunctionDecl *PrevFD = cast<FunctionDecl>(Previous); > > FD->RedeclLink.setPrevious(PrevFD); > + FD->First = PrevFD->First; > > // If the previous declaration is an inline function declaration, then > this > // declaration is too. > > > _______________________________________________ > cfe-commits mailing list > [email protected] > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits >
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
