https://github.com/erichkeane created https://github.com/llvm/llvm-project/pull/113983
…it builds Note: this is a Draft until i can pass testing, clean this up, and figure out if this is of perf benefit. This is #2 here: https://github.com/llvm/llvm-project/issues/113950 >From 09c1c890394ecaa66b20cd933ba0d85c2141e34f Mon Sep 17 00:00:00 2001 From: erichkeane <eke...@nvidia.com> Date: Mon, 28 Oct 2024 17:00:38 -0700 Subject: [PATCH] First run at removing the linked-list for decls. Tests not run, but it builds --- clang/include/clang/AST/Decl.h | 4 +- clang/include/clang/AST/DeclBase.h | 70 +++++++----- clang/include/clang/AST/DeclCXX.h | 2 +- clang/lib/AST/Decl.cpp | 37 ++++-- clang/lib/AST/DeclBase.cpp | 173 ++++++++++++++++++----------- clang/lib/AST/DeclPrinter.cpp | 6 +- 6 files changed, 188 insertions(+), 104 deletions(-) diff --git a/clang/include/clang/AST/Decl.h b/clang/include/clang/AST/Decl.h index 7ff35d73df5997..641f790c67824f 100644 --- a/clang/include/clang/AST/Decl.h +++ b/clang/include/clang/AST/Decl.h @@ -4893,7 +4893,9 @@ class ExportDecl final : public Decl, public DeclContext { return RBraceLoc; // No braces: get the end location of the (only) declaration in context // (if present). - return decls_empty() ? getLocation() : decls_begin()->getEndLoc(); + // TODO: ERICH: is this going to be a problem? Previous iterator did a + // double-dereference, which doesn't seem right. + return decls_empty() ? getLocation() : (*decls_begin())->getEndLoc(); } SourceRange getSourceRange() const override LLVM_READONLY { diff --git a/clang/include/clang/AST/DeclBase.h b/clang/include/clang/AST/DeclBase.h index a3447d19909752..3c53658ecd41af 100644 --- a/clang/include/clang/AST/DeclBase.h +++ b/clang/include/clang/AST/DeclBase.h @@ -240,14 +240,6 @@ class alignas(8) Decl { ModulePrivate }; -protected: - /// The next declaration within the same lexical - /// DeclContext. These pointers form the linked list that is - /// traversed via DeclContext's decls_begin()/decls_end(). - /// - /// The extra three bits are used for the ModuleOwnershipKind. - llvm::PointerIntPair<Decl *, 3, ModuleOwnershipKind> NextInContextAndBits; - private: friend class DeclContext; @@ -351,6 +343,13 @@ class alignas(8) Decl { LLVM_PREFERRED_TYPE(Linkage) mutable unsigned CacheValidAndLinkage : 3; + // TODO: ERICH: Does this have to be protected? The PointerIntPair was, but it + // isn't clear that is necessary. + /// Kind of ownership the declaration has, for visibility purposes. See + /// declaration of `ModuleOwnershipKind`. + LLVM_PREFERRED_TYPE(ModuleOwnershipKind) + unsigned ModuleOwnership : 3; + /// Allocate memory for a deserialized declaration. /// /// This routine must be used to allocate memory for any declaration that is @@ -394,12 +393,12 @@ class alignas(8) Decl { protected: Decl(Kind DK, DeclContext *DC, SourceLocation L) - : NextInContextAndBits(nullptr, getModuleOwnershipKindForChildOf(DC)), - DeclCtx(DC), Loc(L), DeclKind(DK), InvalidDecl(false), HasAttrs(false), + : DeclCtx(DC), Loc(L), DeclKind(DK), InvalidDecl(false), HasAttrs(false), Implicit(false), Used(false), Referenced(false), TopLevelDeclInObjCContainer(false), Access(AS_none), FromASTFile(0), IdentifierNamespace(getIdentifierNamespaceForKind(DK)), - CacheValidAndLinkage(llvm::to_underlying(Linkage::Invalid)) { + CacheValidAndLinkage(llvm::to_underlying(Linkage::Invalid)), + ModuleOwnership(static_cast<unsigned>(getModuleOwnershipKindForChildOf(DC))) { if (StatisticsEnabled) add(DK); } @@ -449,8 +448,9 @@ class alignas(8) Decl { Kind getKind() const { return static_cast<Kind>(DeclKind); } const char *getDeclKindName() const; - Decl *getNextDeclInContext() { return NextInContextAndBits.getPointer(); } - const Decl *getNextDeclInContext() const {return NextInContextAndBits.getPointer();} + //TODO: ERICH: figure out how necessary these are? Can be implemented 'dumb-ly' + //Decl *getNextDeclInContext() { return NextInContextAndBits.getPointer(); } + //const Decl *getNextDeclInContext() const {return NextInContextAndBits.getPointer();} DeclContext *getDeclContext() { if (isInSemaDC()) @@ -867,7 +867,7 @@ class alignas(8) Decl { /// Get the kind of module ownership for this declaration. ModuleOwnershipKind getModuleOwnershipKind() const { - return NextInContextAndBits.getInt(); + return static_cast<ModuleOwnershipKind>(ModuleOwnership); } /// Set whether this declaration is hidden from name lookup. @@ -876,7 +876,7 @@ class alignas(8) Decl { MOK != ModuleOwnershipKind::Unowned && !isFromASTFile() && !hasLocalOwningModuleStorage()) && "no storage available for owning module for this declaration"); - NextInContextAndBits.setInt(MOK); + ModuleOwnership = static_cast<unsigned>(MOK); } unsigned getIdentifierNamespace() const { @@ -2060,19 +2060,21 @@ class DeclContext { /// FirstDecl - The first declaration stored within this declaration /// context. - mutable Decl *FirstDecl = nullptr; + ///mutable Decl *FirstDecl = nullptr; /// LastDecl - The last declaration stored within this declaration /// context. FIXME: We could probably cache this value somewhere /// outside of the DeclContext, to reduce the size of DeclContext by /// another pointer. - mutable Decl *LastDecl = nullptr; + ///mutable Decl *LastDecl = nullptr; /// Build up a chain of declarations. /// /// \returns the first/last pair of declarations. - static std::pair<Decl *, Decl *> - BuildDeclChain(ArrayRef<Decl*> Decls, bool FieldsAlreadyLoaded); + // TODO: ERICH: this ends up being just a filter if it doesn't need to update + // next decl. + //static std::pair<Decl *, Decl *> + //BuildDeclChain(ArrayRef<Decl*> Decls, bool FieldsAlreadyLoaded); DeclContext(Decl::Kind K); @@ -2305,6 +2307,8 @@ class DeclContext { /// for non-namespace contexts). void collectAllContexts(SmallVectorImpl<DeclContext *> &Contexts); + // TODO: ERICH: Remove +/* /// decl_iterator - Iterates through the declarations stored /// within this context. class decl_iterator { @@ -2345,14 +2349,22 @@ class DeclContext { return x.Current != y.Current; } }; + */ + + // TODO: ERICH: Put this somewhere better? Rename? + using DeclCollection = llvm::SmallVector<Decl*>; + mutable DeclCollection OurDecls; + using decl_iterator = DeclCollection::iterator; using decl_range = llvm::iterator_range<decl_iterator>; + /// decls_begin/decls_end - Iterate over the declarations stored in /// this context. decl_range decls() const { return decl_range(decls_begin(), decls_end()); } decl_iterator decls_begin() const; - decl_iterator decls_end() const { return decl_iterator(); } + // TODO: ERICH: Do we need to do the 'load' decls thing here too? + decl_iterator decls_end() const;// { return OurDecls.end(); } bool decls_empty() const; /// noload_decls_begin/end - Iterate over the declarations stored in this @@ -2361,14 +2373,15 @@ class DeclContext { decl_range noload_decls() const { return decl_range(noload_decls_begin(), noload_decls_end()); } - decl_iterator noload_decls_begin() const { return decl_iterator(FirstDecl); } - decl_iterator noload_decls_end() const { return decl_iterator(); } + decl_iterator noload_decls_begin() const { return OurDecls.begin(); } + decl_iterator noload_decls_end() const { return OurDecls.end(); } /// specific_decl_iterator - Iterates over a subrange of /// declarations stored in a DeclContext, providing only those that /// are of type SpecificDecl (or a class derived from it). This /// iterator is used, for example, to provide iteration over just /// the fields within a RecordDecl (with SpecificDecl = FieldDecl). + // TODO: ERICH: Could this just be a llvm_filter_range as well? template<typename SpecificDecl> class specific_decl_iterator { /// Current - The current, underlying declaration iterator, which @@ -2689,11 +2702,16 @@ class DeclContext { DeclContextBits.NeedToReconcileExternalVisibleStorage = true; } - /// Determine whether the given declaration is stored in the list of - /// declarations lexically within this context. + // TODO: ERICH: Used in ASTReader.cpp + ///// Determine whether the given declaration is stored in the list of + ///// declarations lexically within this context. bool isDeclInLexicalTraversal(const Decl *D) const { - return D && (D->NextInContextAndBits.getPointer() || D == FirstDecl || - D == LastDecl); + // TODO: ERICH: Not sure exactly what is happening here? Previous impl seems + // to be checking that D is either not last in its declaration, or is this + // first or last decl. + return D && llvm::find(OurDecls, D) != OurDecls.end(); + //return D && (D->NextInContextAndBits.getPointer() || D == FirstDecl || + // D == LastDecl); } void setUseQualifiedLookup(bool use = true) const { diff --git a/clang/include/clang/AST/DeclCXX.h b/clang/include/clang/AST/DeclCXX.h index 2693cc0e95b4b2..e564387f084415 100644 --- a/clang/include/clang/AST/DeclCXX.h +++ b/clang/include/clang/AST/DeclCXX.h @@ -2994,7 +2994,7 @@ class LinkageSpecDecl : public Decl, public DeclContext { return getRBraceLoc(); // No braces: get the end location of the (only) declaration in context // (if present). - return decls_empty() ? getLocation() : decls_begin()->getEndLoc(); + return decls_empty() ? getLocation() : (*decls_begin())->getEndLoc(); } SourceRange getSourceRange() const override LLVM_READONLY { diff --git a/clang/lib/AST/Decl.cpp b/clang/lib/AST/Decl.cpp index 86913763ef9ff5..c3a2779465ad68 100644 --- a/clang/lib/AST/Decl.cpp +++ b/clang/lib/AST/Decl.cpp @@ -5093,7 +5093,9 @@ RecordDecl::field_iterator RecordDecl::field_begin() const { // FIXME: Come up with a test case that breaks without definition. if (RecordDecl *D = getDefinition(); D && D != this) return D->field_begin(); - return field_iterator(decl_iterator(FirstDecl)); + + return field_iterator(decls_begin()); + //return field_iterator(decl_iterator(FirstDecl)); } /// completeDefinition - Notes that the definition of this type is now @@ -5124,8 +5126,19 @@ bool RecordDecl::isMsStruct(const ASTContext &C) const { } void RecordDecl::reorderDecls(const SmallVectorImpl<Decl *> &Decls) { - std::tie(FirstDecl, LastDecl) = DeclContext::BuildDeclChain(Decls, false); - LastDecl->NextInContextAndBits.setPointer(nullptr); + // std::tie(FirstDecl, LastDecl) = DeclContext::BuildDeclChain(Decls, false); + // TODO: ERICH: This function could possibly be used to steal decls, but i + // don't htink it is doing that, I think the purpose of it is to just have + // current decls reordered. This could presumably have leaked/stolen decls, + // but we'll assume nothing gets lost here. I also wonder if the uses of + // this could be replaced iwth some sort of std::sort here. + // We could also try harder on the assert here to make sure this is the same + // collection, just sorted differently. + + assert(Decls.size() == OurDecls.size() && "Reordering a different set of decls?"); + OurDecls.clear(); + OurDecls.insert(OurDecls.begin(), Decls.begin(), Decls.end()); + //LastDecl->NextInContextAndBits.setPointer(nullptr); setIsRandomized(true); } @@ -5151,13 +5164,17 @@ void RecordDecl::LoadFieldsFromExternalStorage() const { if (Decls.empty()) return; - auto [ExternalFirst, ExternalLast] = - BuildDeclChain(Decls, - /*FieldsAlreadyLoaded=*/false); - ExternalLast->NextInContextAndBits.setPointer(FirstDecl); - FirstDecl = ExternalFirst; - if (!LastDecl) - LastDecl = ExternalLast; + // TODO: ERICH: does an insert from the beginning. Also, the + // FieldsAlreadyLoaded removes the filter criteria, so this is just an + // 'insert'. + OurDecls.insert(OurDecls.begin(), Decls.begin(), Decls.end()); + //auto [ExternalFirst, ExternalLast] = + // BuildDeclChain(Decls, + // /*FieldsAlreadyLoaded=*/false); + //ExternalLast->NextInContextAndBits.setPointer(FirstDecl); + //FirstDecl = ExternalFirst; + //if (!LastDecl) + // LastDecl = ExternalLast; } bool RecordDecl::mayInsertExtraPadding(bool EmitRemark) const { diff --git a/clang/lib/AST/DeclBase.cpp b/clang/lib/AST/DeclBase.cpp index 48b91dca1f6d91..cc672915069ccd 100644 --- a/clang/lib/AST/DeclBase.cpp +++ b/clang/lib/AST/DeclBase.cpp @@ -1523,26 +1523,26 @@ void DeclContext::collectAllContexts(SmallVectorImpl<DeclContext *> &Contexts) { Contexts.push_back(this); } -std::pair<Decl *, Decl *> -DeclContext::BuildDeclChain(ArrayRef<Decl *> Decls, - bool FieldsAlreadyLoaded) { - // Build up a chain of declarations via the Decl::NextInContextAndBits field. - Decl *FirstNewDecl = nullptr; - Decl *PrevDecl = nullptr; - for (auto *D : Decls) { - if (FieldsAlreadyLoaded && isa<FieldDecl>(D)) - continue; - - if (PrevDecl) - PrevDecl->NextInContextAndBits.setPointer(D); - else - FirstNewDecl = D; - - PrevDecl = D; - } - - return std::make_pair(FirstNewDecl, PrevDecl); -} +//std::pair<Decl *, Decl *> +//DeclContext::BuildDeclChain(ArrayRef<Decl *> Decls, +// bool FieldsAlreadyLoaded) { +// // Build up a chain of declarations via the Decl::NextInContextAndBits field. +// Decl *FirstNewDecl = nullptr; +// Decl *PrevDecl = nullptr; +// for (auto *D : Decls) { +// if (FieldsAlreadyLoaded && isa<FieldDecl>(D)) +// continue; +// +// if (PrevDecl) +// PrevDecl->NextInContextAndBits.setPointer(D); +// else +// FirstNewDecl = D; +// +// PrevDecl = D; +// } +// +// return std::make_pair(FirstNewDecl, PrevDecl); +//} /// We have just acquired external visible storage, and we already have /// built a lookup map. For every name in the map, pull in the new names from @@ -1582,13 +1582,21 @@ DeclContext::LoadLexicalDeclsFromExternalStorage() const { // Splice the newly-read declarations into the beginning of the list // of declarations. - Decl *ExternalFirst, *ExternalLast; - std::tie(ExternalFirst, ExternalLast) = - BuildDeclChain(Decls, FieldsAlreadyLoaded); - ExternalLast->NextInContextAndBits.setPointer(FirstDecl); - FirstDecl = ExternalFirst; - if (!LastDecl) - LastDecl = ExternalLast; + //Decl *ExternalFirst, *ExternalLast; + //std::tie(ExternalFirst, ExternalLast) = + // BuildDeclChain(Decls, FieldsAlreadyLoaded); + //ExternalLast->NextInContextAndBits.setPointer(FirstDecl); + //FirstDecl = ExternalFirst; + //if (!LastDecl) + // LastDecl = ExternalLast; + + // TODO: ERICH: It isn't clear why these decls are going at the beginning, + // but we can do that. Also have to filter out the 'field decl' if fields are + // already loaded, so make_filter_range can do that. + auto NewDeclRange = llvm::make_filter_range(Decls, [=](Decl *NewD) { + return !FieldsAlreadyLoaded || !isa<FieldDecl>(NewD); + }); + OurDecls.insert(OurDecls.begin(), NewDeclRange.begin(), NewDeclRange.end()); return true; } @@ -1626,19 +1634,37 @@ ExternalASTSource::SetExternalVisibleDeclsForName(const DeclContext *DC, DeclContext::decl_iterator DeclContext::decls_begin() const { if (hasExternalLexicalStorage()) LoadLexicalDeclsFromExternalStorage(); - return decl_iterator(FirstDecl); + return OurDecls.begin(); + //return decl_iterator(FirstDecl); +} + +// TODO: ERICH: we need this now, since we don't know the order of the +// evaluation of args that use decls_begin/decls_end. +// LoadLexicalDeclsFromExternalStorage sets the hasExternalLexicalStorage while +// it is working, so only the 1st one will execute. Previously it was able to +// do this as just an 'empty' iterator, because all end iterators in the +// collection were identical, but we obviously cannot do that here. +DeclContext::decl_iterator DeclContext::decls_end() const { + if (hasExternalLexicalStorage()) + LoadLexicalDeclsFromExternalStorage(); + return OurDecls.end(); } bool DeclContext::decls_empty() const { if (hasExternalLexicalStorage()) LoadLexicalDeclsFromExternalStorage(); - return !FirstDecl; + return OurDecls.empty(); +// return !FirstDecl; } bool DeclContext::containsDecl(Decl *D) const { - return (D->getLexicalDeclContext() == this && - (D->NextInContextAndBits.getPointer() || D == LastDecl)); + return D->getLexicalDeclContext() == this && + llvm::find(OurDecls, D) != OurDecls.end(); + // TODO: ERICH: Again, this isn't really checking what it thinks it was + // checking? though at least it is ensuring the lexical context is this one. + // return (D->getLexicalDeclContext() == this && + // (D->NextInContextAndBits.getPointer() || D == LastDecl)); } bool DeclContext::containsDeclAndLoad(Decl *D) const { @@ -1689,28 +1715,36 @@ static bool shouldBeHidden(NamedDecl *D) { void DeclContext::removeDecl(Decl *D) { assert(D->getLexicalDeclContext() == this && "decl being removed from non-lexical context"); - assert((D->NextInContextAndBits.getPointer() || D == LastDecl) && - "decl is not in decls list"); - - // Remove D from the decl chain. This is O(n) but hopefully rare. - if (D == FirstDecl) { - if (D == LastDecl) - FirstDecl = LastDecl = nullptr; - else - FirstDecl = D->NextInContextAndBits.getPointer(); - } else { - for (Decl *I = FirstDecl; true; I = I->NextInContextAndBits.getPointer()) { - assert(I && "decl not found in linked list"); - if (I->NextInContextAndBits.getPointer() == D) { - I->NextInContextAndBits.setPointer(D->NextInContextAndBits.getPointer()); - if (D == LastDecl) LastDecl = I; - break; - } - } - } - - // Mark that D is no longer in the decl chain. - D->NextInContextAndBits.setPointer(nullptr); + // TODO: ERICH: Assert here isn't really meaningful anymore? Same problem as + // below, only checks to see if this is the not-last decl in _A_ context, or + // is LastDecl of THIS context. + // assert((D->NextInContextAndBits.getPointer() + // || D == LastDecl) && + // "decl is not in decls list"); + + const auto *Itr = llvm::find(OurDecls, D); + assert(Itr != OurDecls.end() && "decl not found in linked list"); + OurDecls.erase(Itr); + + //// Remove D from the decl chain. This is O(n) but hopefully rare.{ + //if (D == FirstDecl) { + // if (D == LastDecl) + // FirstDecl = LastDecl = nullptr; + // else + // FirstDecl = D->NextInContextAndBits.getPointer(); + //} else { + // for (Decl *I = FirstDecl; true; I = I->NextInContextAndBits.getPointer()) { + // assert(I && "decl not found in linked list"); + // if (I->NextInContextAndBits.getPointer() == D) { + // I->NextInContextAndBits.setPointer(D->NextInContextAndBits.getPointer()); + // if (D == LastDecl) LastDecl = I; + // break; + // } + // } + //} + + //// Mark that D is no longer in the decl chain. + //D->NextInContextAndBits.setPointer(nullptr); // Remove D from the lookup table if necessary. if (isa<NamedDecl>(D)) { @@ -1744,15 +1778,23 @@ void DeclContext::removeDecl(Decl *D) { void DeclContext::addHiddenDecl(Decl *D) { assert(D->getLexicalDeclContext() == this && "Decl inserted into wrong lexical context"); - assert(!D->getNextDeclInContext() && D != LastDecl && - "Decl already inserted into a DeclContext"); - - if (FirstDecl) { - LastDecl->NextInContextAndBits.setPointer(D); - LastDecl = D; - } else { - FirstDecl = LastDecl = D; - } + // TODO: ERICH: The original version here isn't really possible, though it + // wasn't really checking what it thought it was checking (it was checking: is + // already in a Decl-Context where it isn't last, AND isn't last in this + // decl). Best we can do I think is to see if it is in this decl context. + assert(llvm::find(OurDecls, D) == OurDecls.end() && + "decl already inserted into this DeclContext"); + // TODO: this isn't really possible now, + //assert(!D->getNextDeclInContext() && D != LastDecl && + // "Decl already inserted into a DeclContext"); + + OurDecls.push_back(D); +// if (FirstDecl) { +// LastDecl->NextInContextAndBits.setPointer(D); +// LastDecl = D; +// } else { +// FirstDecl = LastDecl = D; +// } // Notify a C++ record declaration that we've added a member, so it can // update its class-specific state. @@ -1982,7 +2024,12 @@ void DeclContext::localUncachedLookup(DeclarationName Name, // matches. // FIXME: If we have lazy external declarations, this will not find them! // FIXME: Should we CollectAllContexts and walk them all here? - for (Decl *D = FirstDecl; D; D = D->getNextDeclInContext()) { + //for (Decl *D = FirstDecl; D; D = D->getNextDeclInContext()) { + // if (auto *ND = dyn_cast<NamedDecl>(D)) + // if (ND->getDeclName() == Name) + // Results.push_back(ND); + //} + for (Decl *D : OurDecls) { if (auto *ND = dyn_cast<NamedDecl>(D)) if (ND->getDeclName() == Name) Results.push_back(ND); diff --git a/clang/lib/AST/DeclPrinter.cpp b/clang/lib/AST/DeclPrinter.cpp index 0d51fdbc7e1262..fa5ea3d63949c8 100644 --- a/clang/lib/AST/DeclPrinter.cpp +++ b/clang/lib/AST/DeclPrinter.cpp @@ -434,7 +434,7 @@ void DeclPrinter::VisitDeclContext(DeclContext *DC, bool Indent) { continue; // Skip over implicit declarations in pretty-printing mode. - if (D->isImplicit()) + if ((*D)->isImplicit()) continue; // Don't print implicit specializations, as they are printed when visiting @@ -480,7 +480,7 @@ void DeclPrinter::VisitDeclContext(DeclContext *DC, bool Indent) { if (isa<AccessSpecDecl>(*D)) { Indentation -= Policy.Indentation; this->Indent(); - Print(D->getAccess()); + Print((*D)->getAccess()); Out << ":\n"; Indentation += Policy.Indentation; continue; @@ -532,7 +532,7 @@ void DeclPrinter::VisitDeclContext(DeclContext *DC, bool Indent) { // Declare target attribute is special one, natural spelling for the pragma // assumes "ending" construct so print it here. - if (D->hasAttr<OMPDeclareTargetDeclAttr>()) + if ((*D)->hasAttr<OMPDeclareTargetDeclAttr>()) Out << "#pragma omp end declare target\n"; } _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
