https://github.com/aeft updated https://github.com/llvm/llvm-project/pull/194797
>From d07994e64d69acc7267c50cd007d2311ce3a27a8 Mon Sep 17 00:00:00 2001 From: Zhijie Wang <[email protected]> Date: Wed, 29 Apr 2026 00:10:40 -0700 Subject: [PATCH] [LifetimeSafety][NFC] Refactor OriginList to OriginNode tree --- .../Analysis/Analyses/LifetimeSafety/Facts.h | 11 +- .../Analyses/LifetimeSafety/FactsGenerator.h | 12 +- .../Analyses/LifetimeSafety/Origins.h | 72 +++-- clang/lib/Analysis/LifetimeSafety/Facts.cpp | 6 +- .../LifetimeSafety/FactsGenerator.cpp | 277 +++++++++--------- .../Analysis/LifetimeSafety/LiveOrigins.cpp | 6 +- .../LifetimeSafety/LoanPropagation.cpp | 6 +- clang/lib/Analysis/LifetimeSafety/Origins.cpp | 68 +++-- .../unittests/Analysis/LifetimeSafetyTest.cpp | 6 +- 9 files changed, 241 insertions(+), 223 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h index 88b509e1b94df..15d8abfb5439d 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h @@ -20,7 +20,6 @@ #include "clang/Analysis/Analyses/LifetimeSafety/Utils.h" #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" -#include "llvm/ADT/STLFunctionalExtras.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Debug.h" #include <cstdint> @@ -236,7 +235,7 @@ class GlobalEscapeFact : public OriginEscapesFact { class UseFact : public Fact { const Expr *UseExpr; - const OriginList *OList; + const OriginNode *ONode; // True if this use is a write operation (e.g., left-hand side of assignment). // Write operations are exempted from use-after-free checks. bool IsWritten = false; @@ -244,11 +243,11 @@ class UseFact : public Fact { public: static bool classof(const Fact *F) { return F->getKind() == Kind::Use; } - UseFact(const Expr *UseExpr, const OriginList *OList) - : Fact(Kind::Use), UseExpr(UseExpr), OList(OList) {} + UseFact(const Expr *UseExpr, const OriginNode *ONode) + : Fact(Kind::Use), UseExpr(UseExpr), ONode(ONode) {} - const OriginList *getUsedOrigins() const { return OList; } - void setUsedOrigins(const OriginList *NewList) { OList = NewList; } + const OriginNode *getUsedOrigins() const { return ONode; } + void setUsedOrigins(const OriginNode *NewONode) { ONode = NewONode; } const Expr *getUseExpr() const { return UseExpr; } void markAsWritten() { IsWritten = true; } bool isWritten() const { return IsWritten; } diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/FactsGenerator.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/FactsGenerator.h index 8f0670728bae9..e08f039691f0e 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/FactsGenerator.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/FactsGenerator.h @@ -57,13 +57,13 @@ class FactsGenerator : public ConstStmtVisitor<FactsGenerator> { void VisitCXXDeleteExpr(const CXXDeleteExpr *DE); private: - OriginList *getOriginsList(const ValueDecl &D); - OriginList *getOriginsList(const Expr &E); + OriginNode *getOriginNode(const ValueDecl &D); + OriginNode *getOriginNode(const Expr &E); bool hasOrigins(QualType QT) const; bool hasOrigins(const Expr *E) const; - void flow(OriginList *Dst, OriginList *Src, bool Kill); + void flow(OriginNode *Dst, OriginNode *Src, bool Kill); /// Handles assignment for both BinaryOperator and CXXOperatorCallExpr. /// @@ -76,7 +76,7 @@ class FactsGenerator : public ConstStmtVisitor<FactsGenerator> { void handlePointerArithmetic(const BinaryOperator *BO); - void handlePlacementNew(const CXXNewExpr *NE, OriginList *NewList); + void handlePlacementNew(const CXXNewExpr *NE, OriginNode *NewNode); void handleCXXCtorInitializer(const CXXCtorInitializer *CII); @@ -124,12 +124,12 @@ class FactsGenerator : public ConstStmtVisitor<FactsGenerator> { template <typename Destination, typename Source> void flowOrigin(const Destination &D, const Source &S) { - flow(getOriginsList(D), getOriginsList(S), /*Kill=*/false); + flow(getOriginNode(D), getOriginNode(S), /*Kill=*/false); } template <typename Destination, typename Source> void killAndFlowOrigin(const Destination &D, const Source &S) { - flow(getOriginsList(D), getOriginsList(S), /*Kill=*/true); + flow(getOriginNode(D), getOriginNode(S), /*Kill=*/true); } /// Checks if the expression is a `void("__lifetime_test_point_...")` cast. diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h index c2db59c579060..cacefc8aa62ad 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h @@ -36,7 +36,7 @@ inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, OriginID ID) { /// /// Each Origin corresponds to a single level of indirection. For complex types /// with multiple levels of indirection (e.g., `int**`), multiple Origins are -/// organized into an OriginList structure (see below). +/// organized into a tree structure (see below). struct Origin { OriginID ID; /// A pointer to the AST node that this origin represents. This union @@ -92,30 +92,40 @@ struct Origin { /// /// The list structure enables the analysis to track how loans flow through /// different levels of indirection when assignments and dereferences occur. -class OriginList { +/// +/// TODO: Currently list-shaped (each node has at most one pointee child). +/// Will become tree-shaped once field children are added to support +/// origin trees for records whose fields have origins. +class OriginNode { public: - OriginList(OriginID OID) : OuterOID(OID) {} + OriginNode(OriginID OID) : OID(OID) {} - OriginList *peelOuterOrigin() const { return InnerList; } - OriginID getOuterOriginID() const { return OuterOID; } + OriginNode *getPointeeChild() const { + return Children.empty() ? nullptr : Children[0]; + } - void setInnerOriginList(OriginList *Inner) { InnerList = Inner; } + OriginID getOriginID() const { return OID; } - // Used for assertion checks only (to ensure origin lists have matching + void setChildren(llvm::ArrayRef<OriginNode *> NewChildren) { + assert(Children.empty() && "children must be set at most once"); + Children = NewChildren; + } + + // Used for assertion checks only (to ensure pointee chains have matching // lengths). size_t getLength() const { size_t Length = 1; - const OriginList *T = this; - while (T->InnerList) { - T = T->InnerList; + const OriginNode *T = this; + while (auto *ON = T->getPointeeChild()) { + T = ON; Length++; } return Length; } private: - OriginID OuterOID; - OriginList *InnerList = nullptr; + OriginID OID; + llvm::ArrayRef<OriginNode *> Children; }; bool doesDeclHaveStorage(const ValueDecl *D); @@ -126,31 +136,31 @@ class OriginManager { public: explicit OriginManager(const AnalysisDeclContext &AC); - /// Gets or creates the OriginList for a given ValueDecl. + /// Gets or creates the OriginNode for a given ValueDecl. /// /// Creates a list structure mirroring the levels of indirection in the /// declaration's type (e.g., `int** p` creates list of size 2). /// - /// \returns The OriginList, or nullptr if the type is not pointer-like. - OriginList *getOrCreateList(const ValueDecl *D); + /// \returns The OriginNode, or nullptr if the type is not pointer-like. + OriginNode *getOrCreateNode(const ValueDecl *D); - /// Gets or creates the OriginList for a given Expr. + /// Gets or creates the OriginNode for a given Expr. /// /// Creates a list based on the expression's type and value category: /// - Lvalues get an implicit reference level (modeling addressability) /// - Rvalues of non-pointer type return nullptr (no trackable origin) /// - DeclRefExpr may reuse the underlying declaration's list /// - /// \returns The OriginList, or nullptr for non-pointer rvalues. - OriginList *getOrCreateList(const Expr *E); + /// \returns The OriginNode, or nullptr for non-pointer rvalues. + OriginNode *getOrCreateNode(const Expr *E); - /// Wraps an existing OriginID in a new single-element OriginList, so a fact - /// can refer to a single level of an existing OriginList. - OriginList *createSingleOriginList(OriginID OID); + /// Wraps an existing OriginID in a new single-element OriginNode, so a fact + /// can refer to a single level of an existing OriginNode. + OriginNode *createSingleOriginNode(OriginID OID); - /// Returns the OriginList for the implicit 'this' parameter if the current + /// Returns the OriginNode for the implicit 'this' parameter if the current /// declaration is an instance method. - std::optional<OriginList *> getThisOrigins() const { return ThisOrigins; } + std::optional<OriginNode *> getThisOrigins() const { return ThisOrigins; } const Origin &getOrigin(OriginID ID) const; @@ -169,11 +179,13 @@ class OriginManager { private: OriginID getNextOriginID() { return NextOriginID++; } - OriginList *createNode(const ValueDecl *D, QualType QT); - OriginList *createNode(const Expr *E, QualType QT); + OriginNode *createNode(const ValueDecl *D, QualType QT); + OriginNode *createNode(const Expr *E, QualType QT); + + void attachPointeeChild(OriginNode *Parent, OriginNode *Pointee); template <typename T> - OriginList *buildListForType(QualType QT, const T *Node); + OriginNode *buildNodeForType(QualType QT, const T *Node); void initializeThisOrigins(const Decl *D); @@ -188,10 +200,10 @@ class OriginManager { /// TODO(opt): Profile and evaluate the usefulness of small buffer /// optimisation. llvm::SmallVector<Origin> AllOrigins; - llvm::BumpPtrAllocator ListAllocator; - llvm::DenseMap<const clang::ValueDecl *, OriginList *> DeclToList; - llvm::DenseMap<const clang::Expr *, OriginList *> ExprToList; - std::optional<OriginList *> ThisOrigins; + llvm::BumpPtrAllocator Allocator; + llvm::DenseMap<const clang::ValueDecl *, OriginNode *> DeclToNode; + llvm::DenseMap<const clang::Expr *, OriginNode *> ExprToNode; + std::optional<OriginNode *> ThisOrigins; /// Types that are not inherently pointer-like but require origin tracking /// because of lifetime annotations (currently [[clang::lifetimebound]]) on /// functions that return them. diff --git a/clang/lib/Analysis/LifetimeSafety/Facts.cpp b/clang/lib/Analysis/LifetimeSafety/Facts.cpp index 3d7fbcdacc830..d04d3e9202952 100644 --- a/clang/lib/Analysis/LifetimeSafety/Facts.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Facts.cpp @@ -82,9 +82,9 @@ void UseFact::dump(llvm::raw_ostream &OS, const LoanManager &, OS << "Use ("; size_t NumUsedOrigins = getUsedOrigins()->getLength(); size_t I = 0; - for (const OriginList *Cur = getUsedOrigins(); Cur; - Cur = Cur->peelOuterOrigin(), ++I) { - OM.dump(Cur->getOuterOriginID(), OS); + for (const OriginNode *Cur = getUsedOrigins(); Cur; + Cur = Cur->getPointeeChild(), ++I) { + OM.dump(Cur->getOriginID(), OS); if (I < NumUsedOrigins - 1) OS << ", "; } diff --git a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp index 633f9ae57930b..3c70cc4a0bef9 100644 --- a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp +++ b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp @@ -30,11 +30,12 @@ namespace clang::lifetimes::internal { using llvm::isa_and_present; -OriginList *FactsGenerator::getOriginsList(const ValueDecl &D) { - return FactMgr.getOriginMgr().getOrCreateList(&D); +OriginNode *FactsGenerator::getOriginNode(const ValueDecl &D) { + return FactMgr.getOriginMgr().getOrCreateNode(&D); } -OriginList *FactsGenerator::getOriginsList(const Expr &E) { - return FactMgr.getOriginMgr().getOrCreateList(&E); + +OriginNode *FactsGenerator::getOriginNode(const Expr &E) { + return FactMgr.getOriginMgr().getOrCreateNode(&E); } bool FactsGenerator::hasOrigins(QualType QT) const { @@ -58,7 +59,7 @@ bool FactsGenerator::hasOrigins(const Expr *E) const { /// * Level 1: pp <- p's address /// * Level 2: (*pp) <- what p points to (i.e., &x) /// - `View v = obj;` flows origins from `obj` (depth 1) to `v` (depth 1) -void FactsGenerator::flow(OriginList *Dst, OriginList *Src, bool Kill) { +void FactsGenerator::flow(OriginNode *Dst, OriginNode *Src, bool Kill) { if (!Dst) return; assert(Src && @@ -68,9 +69,9 @@ void FactsGenerator::flow(OriginList *Dst, OriginList *Src, bool Kill) { while (Dst && Src) { CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - Dst->getOuterOriginID(), Src->getOuterOriginID(), Kill)); - Dst = Dst->peelOuterOrigin(); - Src = Src->peelOuterOrigin(); + Dst->getOriginID(), Src->getOriginID(), Kill)); + Dst = Dst->getPointeeChild(); + Src = Src->getPointeeChild(); } } @@ -146,22 +147,22 @@ void FactsGenerator::run() { /// /// Example: For `View& v`, returns the origin of what v points to, not v's /// storage. -static OriginList *getRValueOrigins(const Expr *E, OriginList *List) { - if (!List) +static OriginNode *getRValueOrigins(const Expr *E, OriginNode *Node) { + if (!Node) return nullptr; - return E->isGLValue() ? List->peelOuterOrigin() : List; + return E->isGLValue() ? Node->getPointeeChild() : Node; } void FactsGenerator::VisitDeclStmt(const DeclStmt *DS) { for (const Decl *D : DS->decls()) if (const auto *VD = dyn_cast<VarDecl>(D)) if (const Expr *InitExpr = VD->getInit()) { - OriginList *VDList = getOriginsList(*VD); - if (!VDList) + OriginNode *VDNode = getOriginNode(*VD); + if (!VDNode) continue; - OriginList *InitList = getOriginsList(*InitExpr); - assert(InitList && "VarDecl had origins but InitExpr did not"); - flow(VDList, InitList, /*Kill=*/true); + OriginNode *InitNode = getOriginNode(*InitExpr); + assert(InitNode && "VarDecl had origins but InitExpr did not"); + flow(VDNode, InitNode, /*Kill=*/true); } } @@ -182,13 +183,13 @@ void FactsGenerator::VisitDeclRefExpr(const DeclRefExpr *DRE) { if (doesDeclHaveStorage(DRE->getDecl())) { const Loan *L = createLoan(FactMgr, DRE); assert(L); - OriginList *List = getOriginsList(*DRE); - assert(List && + OriginNode *Node = getOriginNode(*DRE); + assert(Node && "gl-value DRE of non-pointer type should have an origin list"); // This loan specifically tracks borrowing the variable's storage location - // itself and is issued to outermost origin (List->OID). + // itself and is issued to outermost origin (Node->OID). CurrentBlockFacts.push_back( - FactMgr.createFact<IssueFact>(L->getID(), List->getOuterOriginID())); + FactMgr.createFact<IssueFact>(L->getID(), Node->getOriginID())); } } @@ -204,8 +205,8 @@ void FactsGenerator::VisitCXXConstructExpr(const CXXConstructExpr *CCE) { CCE->getConstructor()->isDefaulted() && CCE->getNumArgs() == 1 && hasOrigins(CCE->getType())) { const Expr *Arg = CCE->getArg(0); - if (OriginList *ArgList = getRValueOrigins(Arg, getOriginsList(*Arg))) { - flow(getOriginsList(*CCE), ArgList, /*Kill=*/true); + if (OriginNode *ArgNode = getRValueOrigins(Arg, getOriginNode(*Arg))) { + flow(getOriginNode(*CCE), ArgNode, /*Kill=*/true); return; } } @@ -214,8 +215,8 @@ void FactsGenerator::VisitCXXConstructExpr(const CXXConstructExpr *CCE) { if (const auto *RD = CCE->getType()->getAsCXXRecordDecl(); RD && isStdCallableWrapperType(RD) && CCE->getNumArgs() == 1) { const Expr *Arg = CCE->getArg(0); - if (OriginList *ArgList = getRValueOrigins(Arg, getOriginsList(*Arg))) { - flow(getOriginsList(*CCE), ArgList, /*Kill=*/true); + if (OriginNode *ArgNode = getRValueOrigins(Arg, getOriginNode(*Arg))) { + flow(getOriginNode(*CCE), ArgNode, /*Kill=*/true); return; } } @@ -263,14 +264,14 @@ void FactsGenerator::VisitMemberExpr(const MemberExpr *ME) { auto *MD = ME->getMemberDecl(); if (isa<FieldDecl>(MD) && doesDeclHaveStorage(MD)) { assert(ME->isGLValue() && "Field member should be GL value"); - OriginList *Dst = getOriginsList(*ME); + OriginNode *Dst = getOriginNode(*ME); assert(Dst && "Field member should have an origin list as it is GL value"); - OriginList *Src = getOriginsList(*ME->getBase()); + OriginNode *Src = getOriginNode(*ME->getBase()); assert(Src && "Base expression should be a pointer/reference type"); // The field's glvalue (outermost origin) holds the same loans as the base // expression. CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - Dst->getOuterOriginID(), Src->getOuterOriginID(), + Dst->getOriginID(), Src->getOriginID(), /*Kill=*/true)); } } @@ -284,15 +285,15 @@ void FactsGenerator::VisitCXXNullPtrLiteralExpr( const CXXNullPtrLiteralExpr *N) { /// TODO: Handle nullptr expr as a special 'null' loan. Uninitialized /// pointers can use the same type of loan. - getOriginsList(*N); + getOriginNode(*N); } void FactsGenerator::VisitCastExpr(const CastExpr *CE) { - OriginList *Dest = getOriginsList(*CE); + OriginNode *Dest = getOriginNode(*CE); if (!Dest) return; const Expr *SubExpr = CE->getSubExpr(); - OriginList *Src = getOriginsList(*SubExpr); + OriginNode *Src = getOriginNode(*SubExpr); switch (CE->getCastKind()) { case CK_LValueToRValue: @@ -304,11 +305,11 @@ void FactsGenerator::VisitCastExpr(const CastExpr *CE) { // `int *p, *q; p = q;`) should propagate the inner origin (what the pointer // points to), not the outer origin (the pointer's storage location). Strip // the outer lvalue origin. - flow(getOriginsList(*CE), getRValueOrigins(SubExpr, Src), + flow(getOriginNode(*CE), getRValueOrigins(SubExpr, Src), /*Kill=*/true); return; case CK_NullToPointer: - getOriginsList(*CE); + getOriginNode(*CE); // TODO: Flow into them a null origin. return; case CK_NoOp: @@ -326,7 +327,7 @@ void FactsGenerator::VisitCastExpr(const CastExpr *CE) { case CK_ArrayToPointerDecay: assert(Src && "Array expression should have origins as it is GL value"); CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - Dest->getOuterOriginID(), Src->getOuterOriginID(), /*Kill=*/true)); + Dest->getOriginID(), Src->getOriginID(), /*Kill=*/true)); return; case CK_FunctionToPointerDecay: case CK_BuiltinFnToFnPtr: @@ -366,10 +367,10 @@ void FactsGenerator::VisitUnaryOperator(const UnaryOperator *UO) { void FactsGenerator::VisitReturnStmt(const ReturnStmt *RS) { if (const Expr *RetExpr = RS->getRetValue()) { - if (OriginList *List = getOriginsList(*RetExpr)) - for (OriginList *L = List; L != nullptr; L = L->peelOuterOrigin()) - EscapesInCurrentBlock.push_back(FactMgr.createFact<ReturnEscapeFact>( - L->getOuterOriginID(), RetExpr)); + if (OriginNode *Node = getOriginNode(*RetExpr)) + for (OriginNode *L = Node; L != nullptr; L = L->getPointeeChild()) + EscapesInCurrentBlock.push_back( + FactMgr.createFact<ReturnEscapeFact>(L->getOriginID(), RetExpr)); } } @@ -377,28 +378,28 @@ void FactsGenerator::handleAssignment(const Expr *TargetExpr, const Expr *LHSExpr, const Expr *RHSExpr) { LHSExpr = LHSExpr->IgnoreParenImpCasts(); - OriginList *LHSList = nullptr; + OriginNode *LHSNode = nullptr; if (const auto *DRE_LHS = dyn_cast<DeclRefExpr>(LHSExpr)) { - LHSList = getOriginsList(*DRE_LHS); - assert(LHSList && "LHS is a DRE and should have an origin list"); + LHSNode = getOriginNode(*DRE_LHS); + assert(LHSNode && "LHS is a DRE and should have an origin list"); } // Handle assignment to member fields (e.g., `this->view = s` or `view = s`). // This enables detection of dangling fields when local values escape to // fields. if (const auto *ME_LHS = dyn_cast<MemberExpr>(LHSExpr)) { - LHSList = getOriginsList(*ME_LHS); - assert(LHSList && "LHS is a MemberExpr and should have an origin list"); + LHSNode = getOriginNode(*ME_LHS); + assert(LHSNode && "LHS is a MemberExpr and should have an origin list"); } - if (!LHSList) + if (!LHSNode) return; - OriginList *RHSList = getOriginsList(*RHSExpr); + OriginNode *RHSNode = getOriginNode(*RHSExpr); // For operator= with reference parameters (e.g., // `View& operator=(const View&)`), the RHS argument stays an lvalue, // unlike built-in assignment where LValueToRValue cast strips the outer // lvalue origin. Strip it manually to get the actual value origins being // assigned. - RHSList = getRValueOrigins(RHSExpr, RHSList); + RHSNode = getRValueOrigins(RHSExpr, RHSNode); if (const auto *DRE_LHS = dyn_cast<DeclRefExpr>(LHSExpr)) { QualType QT = DRE_LHS->getDecl()->getType(); @@ -409,12 +410,12 @@ void FactsGenerator::handleAssignment(const Expr *TargetExpr, // binding live) and a Write of the inner origins (killing the pointee's // liveness). if (UseFact *UF = UseFacts.lookup(DRE_LHS)) { - const OriginList *FullList = UF->getUsedOrigins(); - assert(FullList); - UF->setUsedOrigins(FactMgr.getOriginMgr().createSingleOriginList( - FullList->getOuterOriginID())); - if (const OriginList *InnerList = FullList->peelOuterOrigin()) { - UseFact *WriteUF = FactMgr.createFact<UseFact>(DRE_LHS, InnerList); + const OriginNode *FullNode = UF->getUsedOrigins(); + assert(FullNode); + UF->setUsedOrigins(FactMgr.getOriginMgr().createSingleOriginNode( + FullNode->getOriginID())); + if (const OriginNode *InnerNode = FullNode->getPointeeChild()) { + UseFact *WriteUF = FactMgr.createFact<UseFact>(DRE_LHS, InnerNode); WriteUF->markAsWritten(); CurrentBlockFacts.push_back(WriteUF); } @@ -423,18 +424,18 @@ void FactsGenerator::handleAssignment(const Expr *TargetExpr, } else markUseAsWrite(DRE_LHS); } - if (!RHSList) { + if (!RHSNode) { // RHS has no tracked origins (e.g., assigning a callable without origins // to std::function). Clear loans of the destination. - for (OriginList *LHSInner = LHSList->peelOuterOrigin(); LHSInner; - LHSInner = LHSInner->peelOuterOrigin()) + for (OriginNode *LHSInner = LHSNode->getPointeeChild(); LHSInner; + LHSInner = LHSInner->getPointeeChild()) CurrentBlockFacts.push_back( - FactMgr.createFact<KillOriginFact>(LHSInner->getOuterOriginID())); + FactMgr.createFact<KillOriginFact>(LHSInner->getOriginID())); return; } // Kill the old loans of the destination origin and flow the new loans // from the source origin. - flow(LHSList->peelOuterOrigin(), RHSList, /*Kill=*/true); + flow(LHSNode->getPointeeChild(), RHSNode, /*Kill=*/true); killAndFlowOrigin(*TargetExpr, *LHSExpr); } @@ -578,17 +579,17 @@ void FactsGenerator::VisitCXXBindTemporaryExpr( void FactsGenerator::VisitMaterializeTemporaryExpr( const MaterializeTemporaryExpr *MTE) { assert(MTE->isGLValue()); - OriginList *MTEList = getOriginsList(*MTE); - if (!MTEList) + OriginNode *MTENode = getOriginNode(*MTE); + if (!MTENode) return; - OriginList *SubExprList = getOriginsList(*MTE->getSubExpr()); - assert((!SubExprList || - MTEList->getLength() == (SubExprList->getLength() + 1)) && + OriginNode *SubExprNode = getOriginNode(*MTE->getSubExpr()); + assert((!SubExprNode || + MTENode->getLength() == (SubExprNode->getLength() + 1)) && "MTE top level origin should contain a loan to the MTE itself"); - OriginList *RValMTEList = getRValueOrigins(MTE, MTEList); - flow(RValMTEList, SubExprList, /*Kill=*/true); - OriginID OuterMTEID = MTEList->getOuterOriginID(); + OriginNode *RValMTENode = getRValueOrigins(MTE, MTENode); + flow(RValMTENode, SubExprNode, /*Kill=*/true); + OriginID OuterMTEID = MTENode->getOriginID(); if (MTE->getStorageDuration() == SD_FullExpression) { // Issue a loan to MTE for the storage location represented by MTE. const Loan *L = createLoan(FactMgr, MTE); @@ -601,38 +602,38 @@ void FactsGenerator::VisitLambdaExpr(const LambdaExpr *LE) { // The lambda gets a single merged origin that aggregates all captured // pointer-like origins. Currently we only need to detect whether the lambda // outlives any capture. - OriginList *LambdaList = getOriginsList(*LE); - if (!LambdaList) + OriginNode *LambdaNode = getOriginNode(*LE); + if (!LambdaNode) return; bool Kill = true; for (const Expr *Init : LE->capture_inits()) { if (!Init) continue; - OriginList *InitList = getOriginsList(*Init); - if (!InitList) + OriginNode *InitNode = getOriginNode(*Init); + if (!InitNode) continue; // FIXME: Consider flowing all origin levels once lambdas support more than // one origin. Currently only the outermost origin is flowed, so by-ref // captures like `[&p]` (where p is string_view) miss inner-level // invalidation. CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - LambdaList->getOuterOriginID(), InitList->getOuterOriginID(), Kill)); + LambdaNode->getOriginID(), InitNode->getOriginID(), Kill)); Kill = false; } } void FactsGenerator::VisitArraySubscriptExpr(const ArraySubscriptExpr *ASE) { assert(ASE->isGLValue() && "Array subscript should be a GL value"); - OriginList *Dst = getOriginsList(*ASE); + OriginNode *Dst = getOriginNode(*ASE); assert(Dst && "Array subscript should have origins as it is a GL value"); - OriginList *Src = getOriginsList(*ASE->getBase()); + OriginNode *Src = getOriginNode(*ASE->getBase()); assert(Src && "Base of array subscript should have origins"); CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - Dst->getOuterOriginID(), Src->getOuterOriginID(), /*Kill=*/true)); + Dst->getOriginID(), Src->getOriginID(), /*Kill=*/true)); } void FactsGenerator::handlePlacementNew(const CXXNewExpr *NE, - OriginList *NewList) { + OriginNode *NewNode) { // Model only the standard single-argument placement new form, where the // placement argument corresponds to a void* allocation-function parameter. // Other placement forms, such as std::nothrow, are not modeled as providing @@ -656,44 +657,44 @@ void FactsGenerator::handlePlacementNew(const CXXNewExpr *NE, ICE && ICE->getCastKind() == CK_BitCast && PlacementArg->getType()->isVoidPointerType()) PlacementArg = ICE->getSubExpr(); - OriginList *PlacementList = getOriginsList(*PlacementArg); + OriginNode *PlacementNode = getOriginNode(*PlacementArg); // FIXME: General placement arguments need separate handling to overwrite // the right origins. // The pointer returned by placement new comes from the placement // argument. - if (PlacementList) + if (PlacementNode) CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - NewList->getOuterOriginID(), PlacementList->getOuterOriginID(), true)); + NewNode->getOriginID(), PlacementNode->getOriginID(), true)); } void FactsGenerator::VisitCXXNewExpr(const CXXNewExpr *NE) { - OriginList *NewList = getOriginsList(*NE); + OriginNode *NewNode = getOriginNode(*NE); const Expr *Init = NE->getInitializer(); if (NE->getNumPlacementArgs() == 1) { - handlePlacementNew(NE, NewList); + handlePlacementNew(NE, NewNode); } else { const Loan *L = createLoan(FactMgr, NE); CurrentBlockFacts.push_back( - FactMgr.createFact<IssueFact>(L->getID(), NewList->getOuterOriginID())); + FactMgr.createFact<IssueFact>(L->getID(), NewNode->getOriginID())); } - NewList = NewList->peelOuterOrigin(); + NewNode = NewNode->getPointeeChild(); - if (!NewList || !Init) + if (!NewNode || !Init) return; - // FIXME: OriginList is null for `new[]` initializers. Remove this `Init` + // FIXME: OriginNode is null for `new[]` initializers. Remove this `Init` // check once array origins are supported. - if (OriginList *InitList = getOriginsList(*Init); InitList) - flow(NewList, InitList, true); + if (OriginNode *InitNode = getOriginNode(*Init); InitNode) + flow(NewNode, InitNode, true); } void FactsGenerator::VisitCXXDeleteExpr(const CXXDeleteExpr *DE) { - OriginList *List = getOriginsList(*DE->getArgument()); + OriginNode *Node = getOriginNode(*DE->getArgument()); CurrentBlockFacts.push_back( - FactMgr.createFact<InvalidateOriginFact>(List->getOuterOriginID(), DE)); + FactMgr.createFact<InvalidateOriginFact>(Node->getOriginID(), DE)); } bool FactsGenerator::escapesViaReturn(OriginID OID) const { @@ -711,8 +712,8 @@ void FactsGenerator::handleLifetimeEnds(const CFGLifetimeEnds &LifetimeEnds) { // Expire the origin when its variable's lifetime ends to ensure liveness // doesn't persist through loop back-edges. std::optional<OriginID> ExpiredOID; - if (OriginList *List = getOriginsList(*LifetimeEndsVD)) { - OriginID OID = List->getOuterOriginID(); + if (OriginNode *Node = getOriginNode(*LifetimeEndsVD)) { + OriginID OID = Node->getOriginID(); // Skip origins that escape via return; the escape checker needs their loans // to remain until the return statement is processed. if (!escapesViaReturn(OID)) @@ -753,22 +754,22 @@ void FactsGenerator::handleGSLPointerConstruction(const CXXConstructExpr *CCE) { const Expr *Arg = CCE->getArg(0); if (isGslPointerType(Arg->getType())) { - OriginList *ArgList = getOriginsList(*Arg); - assert(ArgList && "GSL pointer argument should have an origin list"); + OriginNode *ArgNode = getOriginNode(*Arg); + assert(ArgNode && "GSL pointer argument should have an origin list"); // GSL pointer is constructed from another gsl pointer. // Example: // View(View v); // View(const View &v); - ArgList = getRValueOrigins(Arg, ArgList); - flow(getOriginsList(*CCE), ArgList, /*Kill=*/true); + ArgNode = getRValueOrigins(Arg, ArgNode); + flow(getOriginNode(*CCE), ArgNode, /*Kill=*/true); } else if (Arg->getType()->isPointerType()) { // GSL pointer is constructed from a raw pointer. Flow only the outermost // raw pointer. Example: // View(const char*); // Span<int*>(const in**); - OriginList *ArgList = getOriginsList(*Arg); + OriginNode *ArgNode = getOriginNode(*Arg); CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - getOriginsList(*CCE)->getOuterOriginID(), ArgList->getOuterOriginID(), + getOriginNode(*CCE)->getOriginID(), ArgNode->getOriginID(), /*Kill=*/true)); } else { // This could be a new borrow. @@ -790,10 +791,10 @@ void FactsGenerator::handleMovedArgsInCall(const FunctionDecl *FD, // destructor runs after ownership has been transferred. if (isUniquePtrRelease(*MD)) { const Expr *UniquePtrExpr = Args[0]; - OriginList *MovedOrigins = getOriginsList(*UniquePtrExpr); + OriginNode *MovedOrigins = getOriginNode(*UniquePtrExpr); if (MovedOrigins) CurrentBlockFacts.push_back(FactMgr.createFact<MovedOriginFact>( - UniquePtrExpr, MovedOrigins->getOuterOriginID())); + UniquePtrExpr, MovedOrigins->getOriginID())); } } @@ -804,12 +805,12 @@ void FactsGenerator::handleMovedArgsInCall(const FunctionDecl *FD, if (!PVD->getType()->isRValueReferenceType()) continue; const Expr *Arg = Args[I]; - OriginList *MovedOrigins = getOriginsList(*Arg); + OriginNode *MovedOrigins = getOriginNode(*Arg); assert(MovedOrigins->getLength() >= 1 && "unexpected length for r-value reference param"); // Arg is being moved to this parameter. Mark the origin as moved. - CurrentBlockFacts.push_back(FactMgr.createFact<MovedOriginFact>( - Arg, MovedOrigins->getOuterOriginID())); + CurrentBlockFacts.push_back( + FactMgr.createFact<MovedOriginFact>(Arg, MovedOrigins->getOriginID())); } } @@ -829,10 +830,10 @@ void FactsGenerator::handleInvalidatingCall(const Expr *Call, if (!isa<DeclRefExpr>(Args[0]->IgnoreImpCasts())) return; - OriginList *ThisList = getOriginsList(*Args[0]); - if (ThisList) + OriginNode *ThisNode = getOriginNode(*Args[0]); + if (ThisNode) CurrentBlockFacts.push_back(FactMgr.createFact<InvalidateOriginFact>( - ThisList->getOuterOriginID(), Call)); + ThisNode->getOriginID(), Call)); } void FactsGenerator::handleDestructiveCall(const Expr *Call, @@ -840,10 +841,10 @@ void FactsGenerator::handleDestructiveCall(const Expr *Call, ArrayRef<const Expr *> Args) { if (!destructsFirstArg(*FD)) return; - OriginList *ArgList = getOriginsList(*Args[0]); - if (ArgList) - CurrentBlockFacts.push_back(FactMgr.createFact<InvalidateOriginFact>( - ArgList->getOuterOriginID(), Call)); + OriginNode *ArgNode = getOriginNode(*Args[0]); + if (ArgNode) + CurrentBlockFacts.push_back( + FactMgr.createFact<InvalidateOriginFact>(ArgNode->getOriginID(), Call)); } void FactsGenerator::handleImplicitObjectFieldUses(const Expr *Call, @@ -865,9 +866,9 @@ void FactsGenerator::handleImplicitObjectFieldUses(const Expr *Call, const auto UseFields = [&](const CXXRecordDecl *RD) { for (const auto *Field : RD->fields()) - if (auto *FieldList = getOriginsList(*Field)) + if (auto *FieldNode = getOriginNode(*Field)) CurrentBlockFacts.push_back( - FactMgr.createFact<UseFact>(Call, FieldList)); + FactMgr.createFact<UseFact>(Call, FieldNode)); }; UseFields(ClassDecl); @@ -905,10 +906,10 @@ void FactsGenerator::handleLifetimeCaptureBy(const FunctionDecl *FD, const LifetimeCaptureByAttr *Attr = getArgCaptureBy(I); if (!Attr) continue; - OriginList *CapturedOriginList = getOriginsList(*Args[I]); - if (!CapturedOriginList) + OriginNode *CapturedOriginNode = getOriginNode(*Args[I]); + if (!CapturedOriginNode) continue; - if (!CapturedOriginList) + if (!CapturedOriginNode) continue; for (int CapturingArgIdx : Attr->params()) { // FIXME: Add support for capturing to Global/unknown. @@ -923,8 +924,8 @@ void FactsGenerator::handleLifetimeCaptureBy(const FunctionDecl *FD, : CallArgs[CapturingArgIdx]; assert(CapturedByArg && "Capturer expression must be valid"); - OriginList *CapturingOriginList = getOriginsList(*CapturedByArg); - OriginList *Dest = getRValueOrigins(CapturedByArg, CapturingOriginList); + OriginNode *CapturingOriginNode = getOriginNode(*CapturedByArg); + OriginNode *Dest = getRValueOrigins(CapturedByArg, CapturingOriginNode); if (!Dest) continue; // KillDest=false because we cannot know if previous captures are being @@ -932,7 +933,7 @@ void FactsGenerator::handleLifetimeCaptureBy(const FunctionDecl *FD, // destination must all be tracked, so captured lifetimes are always // merged. CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - Dest->getOuterOriginID(), CapturedOriginList->getOuterOriginID(), + Dest->getOriginID(), CapturedOriginNode->getOriginID(), /*KillDest=*/false)); } } @@ -942,7 +943,7 @@ void FactsGenerator::handleFunctionCall(const Expr *Call, const FunctionDecl *FD, ArrayRef<const Expr *> Args, bool IsGslConstruction) { - OriginList *CallList = getOriginsList(*Call); + OriginNode *CallNode = getOriginNode(*Call); // Ignore functions returning values with no origin. FD = getDeclWithMergedLifetimeBoundAttrs(FD); if (!FD) @@ -955,14 +956,14 @@ void FactsGenerator::handleFunctionCall(const Expr *Call, handleMovedArgsInCall(FD, Args); handleImplicitObjectFieldUses(Call, FD); handleLifetimeCaptureBy(FD, Args); - if (!CallList) + if (!CallNode) return; if (isStdReferenceCast(FD)) { assert(Args.size() == 1 && "std reference cast builtins take exactly one argument"); // std reference-cast functions like std::move return a result that refers // to the same object as the argument, so propagate the full origins. - flow(CallList, getOriginsList(*Args[0]), /*Kill=*/true); + flow(CallNode, getOriginNode(*Args[0]), /*Kill=*/true); return; } auto IsArgLifetimeBound = [FD, &Args](unsigned I) -> bool { @@ -1001,23 +1002,22 @@ void FactsGenerator::handleFunctionCall(const Expr *Call, return; bool KillSrc = true; for (unsigned I = 0; I < Args.size(); ++I) { - OriginList *ArgList = getOriginsList(*Args[I]); - if (!ArgList) + OriginNode *ArgNode = getOriginNode(*Args[I]); + if (!ArgNode) continue; if (IsGslConstruction) { // TODO: document with code example. // std::string_view(const std::string_view& from) if (isGslPointerType(Args[I]->getType())) { - assert(!Args[I]->isGLValue() || ArgList->getLength() >= 2); - ArgList = getRValueOrigins(Args[I], ArgList); + assert(!Args[I]->isGLValue() || ArgNode->getLength() >= 2); + ArgNode = getRValueOrigins(Args[I], ArgNode); } if (isGslOwnerType(Args[I]->getType())) { // The constructed gsl::Pointer borrows from the Owner's storage, not // from what the Owner itself borrows, so only the outermost origin is // needed. CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - CallList->getOuterOriginID(), ArgList->getOuterOriginID(), - KillSrc)); + CallNode->getOriginID(), ArgNode->getOriginID(), KillSrc)); KillSrc = false; } else if (IsArgLifetimeBound(I)) { // Only flow the outer origin here. For lifetimebound args in @@ -1027,24 +1027,23 @@ void FactsGenerator::handleFunctionCall(const Expr *Call, // FIXME: Handle origin-shape mismatches gracefully so we can also flow // inner origins. CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - CallList->getOuterOriginID(), ArgList->getOuterOriginID(), - KillSrc)); + CallNode->getOriginID(), ArgNode->getOriginID(), KillSrc)); KillSrc = false; } } else if (shouldTrackPointerImplicitObjectArg(I)) { - assert(ArgList->getLength() >= 2 && + assert(ArgNode->getLength() >= 2 && "Object arg of pointer type should have at least two origins"); // See through the GSLPointer reference to see the pointer's value. CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - CallList->getOuterOriginID(), - ArgList->peelOuterOrigin()->getOuterOriginID(), KillSrc)); + CallNode->getOriginID(), ArgNode->getPointeeChild()->getOriginID(), + KillSrc)); KillSrc = false; } else if (IsArgLifetimeBound(I)) { // Lifetimebound on a non-GSL-ctor function means the returned // pointer/reference itself must not outlive the arguments. This // only constrains the top-level origin. CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - CallList->getOuterOriginID(), ArgList->getOuterOriginID(), KillSrc)); + CallNode->getOriginID(), ArgNode->getOriginID(), KillSrc)); KillSrc = false; } } @@ -1072,20 +1071,20 @@ bool FactsGenerator::handleTestPoint(const CXXFunctionalCastExpr *FCE) { } void FactsGenerator::handleUse(const Expr *E) { - OriginList *List = getOriginsList(*E); - if (!List) + OriginNode *Node = getOriginNode(*E); + if (!Node) return; // For DeclRefExpr: Remove the outer layer of origin which borrows from the // decl directly (e.g., when this is not a reference). This is a use of the // underlying decl. if (auto *DRE = dyn_cast<DeclRefExpr>(E); DRE && !DRE->getDecl()->getType()->isReferenceType()) - List = getRValueOrigins(DRE, List); + Node = getRValueOrigins(DRE, Node); // Skip if there is no inner origin (e.g., when it is not a pointer type). - if (!List) + if (!Node) return; if (!UseFacts.contains(E)) { - UseFact *UF = FactMgr.createFact<UseFact>(E, List); + UseFact *UF = FactMgr.createFact<UseFact>(E, Node); CurrentBlockFacts.push_back(UF); UseFacts[E] = UF; } @@ -1105,21 +1104,21 @@ llvm::SmallVector<Fact *> FactsGenerator::issuePlaceholderLoans() { llvm::SmallVector<Fact *> PlaceholderLoanFacts; if (auto ThisOrigins = FactMgr.getOriginMgr().getThisOrigins()) { - OriginList *List = *ThisOrigins; + OriginNode *Node = *ThisOrigins; const Loan *L = FactMgr.getLoanMgr().createLoan( AccessPath::Placeholder(cast<CXXMethodDecl>(FD)), /*IssuingExpr=*/nullptr); PlaceholderLoanFacts.push_back( - FactMgr.createFact<IssueFact>(L->getID(), List->getOuterOriginID())); + FactMgr.createFact<IssueFact>(L->getID(), Node->getOriginID())); } for (const ParmVarDecl *PVD : FD->parameters()) { - OriginList *List = getOriginsList(*PVD); - if (!List) + OriginNode *Node = getOriginNode(*PVD); + if (!Node) continue; const Loan *L = FactMgr.getLoanMgr().createLoan( AccessPath::Placeholder(PVD), /*IssuingExpr=*/nullptr); PlaceholderLoanFacts.push_back( - FactMgr.createFact<IssueFact>(L->getID(), List->getOuterOriginID())); + FactMgr.createFact<IssueFact>(L->getID(), Node->getOriginID())); } return PlaceholderLoanFacts; } diff --git a/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp b/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp index cfbcacf04b1b0..a23d7f224b4bc 100644 --- a/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp @@ -129,9 +129,9 @@ class AnalysisImpl /// the origin since it overwrites the value. Lattice transfer(Lattice In, const UseFact &UF) { Lattice Out = In; - for (const OriginList *Cur = UF.getUsedOrigins(); Cur; - Cur = Cur->peelOuterOrigin()) { - OriginID OID = Cur->getOuterOriginID(); + for (const OriginNode *Cur = UF.getUsedOrigins(); Cur; + Cur = Cur->getPointeeChild()) { + OriginID OID = Cur->getOriginID(); // Write kills liveness. if (UF.isWritten()) { Out = Lattice(Factory.remove(Out.LiveOrigins, OID)); diff --git a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp index 8c570cd29673b..2e6cf78356e58 100644 --- a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp @@ -59,9 +59,9 @@ static llvm::BitVector computePersistentOrigins(const FactManager &FactMgr, break; } case Fact::Kind::Use: - for (const OriginList *Cur = F->getAs<UseFact>()->getUsedOrigins(); Cur; - Cur = Cur->peelOuterOrigin()) - CheckOrigin(Cur->getOuterOriginID()); + for (const OriginNode *Cur = F->getAs<UseFact>()->getUsedOrigins(); Cur; + Cur = Cur->getPointeeChild()) + CheckOrigin(Cur->getOriginID()); break; case Fact::Kind::KillOrigin: CheckOrigin(F->getAs<KillOriginFact>()->getKilledOrigin()); diff --git a/clang/lib/Analysis/LifetimeSafety/Origins.cpp b/clang/lib/Analysis/LifetimeSafety/Origins.cpp index 37bd8a3ccc6bb..41d3adaaae59f 100644 --- a/clang/lib/Analysis/LifetimeSafety/Origins.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Origins.cpp @@ -29,14 +29,14 @@ class MissingOriginCollector : public RecursiveASTVisitor<MissingOriginCollector> { public: MissingOriginCollector( - const llvm::DenseMap<const clang::Expr *, OriginList *> &ExprToOriginList, + const llvm::DenseMap<const clang::Expr *, OriginNode *> &ExprToOriginNode, const OriginManager &OM, LifetimeSafetyStats &LSStats) - : ExprToOriginList(ExprToOriginList), OM(OM), LSStats(LSStats) {} + : ExprToOriginNode(ExprToOriginNode), OM(OM), LSStats(LSStats) {} bool VisitExpr(Expr *E) { if (!OM.hasOrigins(E)) return true; // Check if we have an origin for this expression. - if (!ExprToOriginList.contains(E)) { + if (!ExprToOriginNode.contains(E)) { // No origin found: count this as missing origin. LSStats.ExprTypeToMissingOriginCount[E->getType().getTypePtr()]++; LSStats.ExprStmtClassToMissingOriginCount[std::string( @@ -46,7 +46,7 @@ class MissingOriginCollector } private: - const llvm::DenseMap<const clang::Expr *, OriginList *> &ExprToOriginList; + const llvm::DenseMap<const clang::Expr *, OriginNode *> &ExprToOriginNode; const OriginManager &OM; LifetimeSafetyStats &LSStats; }; @@ -171,61 +171,68 @@ void OriginManager::initializeThisOrigins(const Decl *D) { // 'this' does not refer to the lambda object itself. if (const CXXRecordDecl *P = MD->getParent(); P && P->isLambda()) return; - ThisOrigins = buildListForType(MD->getThisType(), MD); + ThisOrigins = buildNodeForType(MD->getThisType(), MD); } -OriginList *OriginManager::createNode(const ValueDecl *D, QualType QT) { +OriginNode *OriginManager::createNode(const ValueDecl *D, QualType QT) { OriginID NewID = getNextOriginID(); AllOrigins.emplace_back(NewID, D, QT.getTypePtrOrNull()); - return new (ListAllocator.Allocate<OriginList>()) OriginList(NewID); + return new (Allocator.Allocate<OriginNode>()) OriginNode(NewID); } -OriginList *OriginManager::createNode(const Expr *E, QualType QT) { +OriginNode *OriginManager::createNode(const Expr *E, QualType QT) { OriginID NewID = getNextOriginID(); AllOrigins.emplace_back(NewID, E, QT.getTypePtrOrNull()); - return new (ListAllocator.Allocate<OriginList>()) OriginList(NewID); + return new (Allocator.Allocate<OriginNode>()) OriginNode(NewID); } -OriginList *OriginManager::createSingleOriginList(OriginID OID) { - return new (ListAllocator.Allocate<OriginList>()) OriginList(OID); +OriginNode *OriginManager::createSingleOriginNode(OriginID OID) { + return new (Allocator.Allocate<OriginNode>()) OriginNode(OID); +} + +void OriginManager::attachPointeeChild(OriginNode *Parent, + OriginNode *Pointee) { + assert(Pointee && "pointee subtree must be non-null"); + Parent->setChildren( + {new (Allocator.Allocate<OriginNode *>()) OriginNode *(Pointee), 1}); } template <typename T> -OriginList *OriginManager::buildListForType(QualType QT, const T *Node) { - assert(hasOrigins(QT) && "buildListForType called for non-pointer type"); - OriginList *Head = createNode(Node, QT); +OriginNode *OriginManager::buildNodeForType(QualType QT, const T *Node) { + assert(hasOrigins(QT) && "buildNodeForType called for non-pointer type"); + OriginNode *Head = createNode(Node, QT); if (QT->isPointerOrReferenceType()) { QualType PointeeTy = QT->getPointeeType(); // We recurse if the pointee type is pointer-like, to build the next // level in the origin tree. E.g., for T*& / View&. if (hasOrigins(PointeeTy)) - Head->setInnerOriginList(buildListForType(PointeeTy, Node)); + attachPointeeChild(Head, buildNodeForType(PointeeTy, Node)); } return Head; } -OriginList *OriginManager::getOrCreateList(const ValueDecl *D) { +OriginNode *OriginManager::getOrCreateNode(const ValueDecl *D) { if (!hasOrigins(D->getType())) return nullptr; - auto It = DeclToList.find(D); - if (It != DeclToList.end()) + auto It = DeclToNode.find(D); + if (It != DeclToNode.end()) return It->second; - return DeclToList[D] = buildListForType(D->getType(), D); + return DeclToNode[D] = buildNodeForType(D->getType(), D); } -OriginList *OriginManager::getOrCreateList(const Expr *E) { +OriginNode *OriginManager::getOrCreateNode(const Expr *E) { if (auto *ParenIgnored = E->IgnoreParens(); ParenIgnored != E) - return getOrCreateList(ParenIgnored); + return getOrCreateNode(ParenIgnored); // We do not see CFG stmts for ExprWithCleanups. Simply peel them. if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(E)) - return getOrCreateList(EWC->getSubExpr()); + return getOrCreateNode(EWC->getSubExpr()); if (!hasOrigins(E)) return nullptr; - auto It = ExprToList.find(E); - if (It != ExprToList.end()) + auto It = ExprToNode.find(E); + if (It != ExprToNode.end()) return It->second; QualType Type = E->getType(); @@ -244,7 +251,7 @@ OriginList *OriginManager::getOrCreateList(const Expr *E) { Field && isa<CXXThisExpr>(ME->getBase()->IgnoreParenImpCasts())) ReferencedDecl = Field; if (ReferencedDecl) { - OriginList *Head = nullptr; + OriginNode *Head = nullptr; // For non-reference declarations (e.g., `int* p`), the expression is an // lvalue (addressable) that can be borrowed, so we create an outer origin // for the lvalue itself, with the pointee being the declaration's list. @@ -254,15 +261,16 @@ OriginList *OriginManager::getOrCreateList(const Expr *E) { Head = createNode(E, QualType{}); // This ensures origin sharing: multiple expressions to the same // declaration share the same underlying origins. - Head->setInnerOriginList(getOrCreateList(ReferencedDecl)); + if (OriginNode *ON = getOrCreateNode(ReferencedDecl)) + attachPointeeChild(Head, ON); } else { // For reference-typed declarations (e.g., `int& r = p`) which have no // storage, the DeclRefExpr directly reuses the declaration's list since // references don't add an extra level of indirection at the expression // level. - Head = getOrCreateList(ReferencedDecl); + Head = getOrCreateNode(ReferencedDecl); } - return ExprToList[E] = Head; + return ExprToNode[E] = Head; } // If E is an lvalue , it refers to storage. We model this storage as the @@ -270,7 +278,7 @@ OriginList *OriginManager::getOrCreateList(const Expr *E) { // addressable. if (E->isGLValue() && !Type->isReferenceType()) Type = AST.getLValueReferenceType(Type); - return ExprToList[E] = buildListForType(Type, E); + return ExprToNode[E] = buildNodeForType(Type, E); } void OriginManager::dump(OriginID OID, llvm::raw_ostream &OS) const { @@ -299,7 +307,7 @@ const Origin &OriginManager::getOrigin(OriginID ID) const { void OriginManager::collectMissingOrigins(Stmt &FunctionBody, LifetimeSafetyStats &LSStats) { - MissingOriginCollector Collector(this->ExprToList, *this, LSStats); + MissingOriginCollector Collector(this->ExprToNode, *this, LSStats); Collector.TraverseStmt(const_cast<Stmt *>(&FunctionBody)); } diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index febecb472455a..909f1f9f17137 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -108,14 +108,14 @@ class LifetimeTestHelper { // This assumes the OriginManager's `get` can find an existing origin. // We might need a `find` method on OriginManager to avoid `getOrCreate` // logic in a const-query context if that becomes an issue. - OriginList *List = + OriginNode *List = const_cast<OriginManager &>(Analysis.getFactManager().getOriginMgr()) - .getOrCreateList(VD); + .getOrCreateNode(VD); if (!List) { ADD_FAILURE() << "No origin list found for Var '" << VarName << "'"; return std::nullopt; } - return List->getOuterOriginID(); + return List->getOriginID(); } std::vector<LoanID> getLoansForVar(llvm::StringRef VarName) { _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
