On Wed, Mar 25, 2015 at 6:01 PM, Sean Silva <[email protected]> wrote:
> > > 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. > It's guaranteed constant time to get the canonical decl (because every decl either is it or has a pointer to it) and to find the previous decl (although the constant on that is a bit higher if there are multiple redeclarations, as is the memory usage). > -- 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 > >
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
