On Wed, Mar 25, 2015 at 5:56 PM, Sean Silva <[email protected]> wrote:
> 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). > D'oh, just saw the review thread and https://llvm.org/bugs/show_bug.cgi?id=21264 where Richard suggests a more elaborate (but not guaranteed constant time?) scheme. -- Sean Silva > > -- 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
