[LifetimeSafety][NFC] Add field-labeled child edges to OriginNode and generalize subtree walks
diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h index cacefc8..0b75387 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h
@@ -66,54 +66,94 @@ } }; -/// A list of origins representing levels of indirection for pointer-like types. +/// A tree of origins representing the structure of a pointer-like or +/// record type. /// -/// Each node in the list contains an OriginID representing a level of -/// indirection. The list structure captures the multi-level nature of -/// pointer and reference types in the lifetime analysis. +/// Each node carries an OriginID and is connected to children via labeled +/// edges: either a pointee edge (one level of pointer/reference indirection) +/// or a field edge (a named field of a record). Pointer-like types form a +/// pointee chain; record types fan out via field edges. /// /// Examples: -/// - For `int& x`, the list has size 2: -/// * Outer: origin for the reference storage itself (the lvalue `x`) -/// * Inner: origin for what `x` refers to +/// - For `int& x`, a single origin: what `x` refers to. /// -/// - For `int* p`, the list has size 2: -/// * Outer: origin for the pointer variable `p` -/// * Inner: origin for what `p` points to +/// - For `int* p`, the chain has length 2: +/// Outer: the pointer variable `p` +/// +-pointee-> Inner: what `p` points to /// -/// - For `View v` (where View is gsl::Pointer), the list has size 2: -/// * Outer: origin for the view object itself -/// * Inner: origin for what the view refers to +/// - For `View v` (View is gsl::Pointer), the chain has length 2: +/// Outer: the view object itself +/// +-pointee-> Inner: what the view refers to /// -/// - For `int** pp`, the list has size 3: -/// * Outer: origin for `pp` itself -/// * Inner: origin for `*pp` (what `pp` points to) -/// * Inner->Inner: origin for `**pp` (what `*pp` points to) +/// - For `int** pp`, the chain has length 3: +/// Outer: `pp` itself +/// +-pointee-> Inner: `*pp` (what `pp` points to) +/// +-pointee-> Inner->Inner: `**pp` (what `*pp` points to) /// -/// The list structure enables the analysis to track how loans flow through -/// different levels of indirection when assignments and dereferences occur. +/// - For `struct S { View a; Inner b; }` (with `struct Inner { View c; }`), +/// the node fans out into a tree, one `field` edge per field with origins: +/// O_s: the record `s` (holds no loans directly) +/// +-field a-> O_a: what the `View` field `s.a` refers to +/// +-field b-> O_b: the record `s.b` (holds no loans directly) +/// +-field c-> O_c: what the `View` field `s.b.c` refers to /// -/// 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. +/// The structure enables the analysis to track how loans flow through +/// levels of indirection and across record fields when assignments and +/// dereferences occur. class OriginNode { public: - OriginNode(OriginID OID) : OID(OID) {} + /// A labeled edge from this node to a child. The `FD` label determines the + /// edge type: + /// - null `FD`: a pointee edge (one level of pointer/reference indirection) + /// - non-null `FD`: a field edge (the named field of a record type) + /// + /// The label allows the same child subtree to be reachable via different + /// relationships. For example, the subtree for field `v` in `s.v` can be + /// reached both + /// (1) as a field child from `s`'s node (with FD=v), and + /// (2) as a pointee child from the lvalue node for `s.v` (with FD=null). + struct Edge { + const FieldDecl *FD; + OriginNode *Child; + }; - OriginNode *getPointeeChild() const { - return Children.empty() ? nullptr : Children[0]; - } + OriginNode(OriginID OID) : OID(OID) {} OriginID getOriginID() const { return OID; } - void setChildren(llvm::ArrayRef<OriginNode *> NewChildren) { + llvm::ArrayRef<Edge> children() const { return Children; } + + template <typename Fn> void forEachOrigin(Fn F) const { + llvm::SmallVector<const OriginNode *, 4> Worklist{this}; + while (!Worklist.empty()) { + const OriginNode *N = Worklist.pop_back_val(); + F(N); + for (const Edge &E : N->children()) + Worklist.push_back(E.Child); + } + } + + OriginNode *getPointeeChild() const { + for (const Edge &E : Children) + if (!E.FD) + return E.Child; + return nullptr; + } + + OriginNode *getFieldChild(const FieldDecl &F) const { + for (const Edge &E : Children) + if (E.FD == &F) + return E.Child; + return nullptr; + } + + void setChildren(llvm::ArrayRef<Edge> 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 { + // Used to compare two chains' lengths. + size_t getPointeeChainLength() const { size_t Length = 1; const OriginNode *T = this; while (auto *ON = T->getPointeeChild()) { @@ -125,7 +165,7 @@ private: OriginID OID; - llvm::ArrayRef<OriginNode *> Children; + llvm::ArrayRef<Edge> Children; }; bool doesDeclHaveStorage(const ValueDecl *D); @@ -138,18 +178,19 @@ /// 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). + /// Creates a tree structure mirroring the levels of indirection in the + /// declaration's type (e.g., `int* p` creates a chain of length 2). /// /// \returns The OriginNode, or nullptr if the type is not pointer-like. OriginNode *getOrCreateNode(const ValueDecl *D); /// Gets or creates the OriginNode for a given Expr. /// - /// Creates a list based on the expression's type and value category: + /// Creates a tree structure 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 + /// - DeclRefExpr may reuse the underlying declaration's tree /// /// \returns The OriginNode, or nullptr for non-pointer rvalues. OriginNode *getOrCreateNode(const Expr *E); @@ -171,7 +212,8 @@ bool hasOrigins(QualType QT) const; bool hasOrigins(const Expr *E) const; - void dump(OriginID OID, llvm::raw_ostream &OS) const; + void dump(OriginID OID, llvm::raw_ostream &OS, + const FieldDecl *FD = nullptr) const; /// Collects statistics about expressions that lack associated origins. void collectMissingOrigins(Stmt &FunctionBody, LifetimeSafetyStats &LSStats);
diff --git a/clang/lib/Analysis/LifetimeSafety/Facts.cpp b/clang/lib/Analysis/LifetimeSafety/Facts.cpp index d04d3e9..d2f668c 100644 --- a/clang/lib/Analysis/LifetimeSafety/Facts.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Facts.cpp
@@ -77,17 +77,27 @@ OS << ", via Global)\n"; } +// Prints every origin in the subtree in DFS pre-order, each labeled by the +// field edge it was reached through, so a field's origin stays next to the +// record it belongs to. +static void dumpUsedOrigins(const OriginNode *N, const FieldDecl *FD, + const OriginManager &OM, llvm::raw_ostream &OS, + bool &First) { + if (!N) + return; + if (!First) + OS << ", "; + First = false; + OM.dump(N->getOriginID(), OS, FD); + for (const OriginNode::Edge &E : N->children()) + dumpUsedOrigins(E.Child, E.FD, OM, OS, First); +} + void UseFact::dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &OM) const { OS << "Use ("; - size_t NumUsedOrigins = getUsedOrigins()->getLength(); - size_t I = 0; - for (const OriginNode *Cur = getUsedOrigins(); Cur; - Cur = Cur->getPointeeChild(), ++I) { - OM.dump(Cur->getOriginID(), OS); - if (I < NumUsedOrigins - 1) - OS << ", "; - } + bool First = true; + dumpUsedOrigins(getUsedOrigins(), nullptr, OM, OS, First); OS << ", " << (isWritten() ? "Write" : "Read") << ")\n"; }
diff --git a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp index 3c70cc4..d8a0e5c 100644 --- a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp +++ b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp
@@ -49,9 +49,13 @@ /// Propagates origin information from Src to Dst through all levels of /// indirection, creating OriginFlowFacts at each level. /// -/// This function enforces a critical type-safety invariant: both lists must -/// have the same shape (same depth/structure). This invariant ensures that -/// origins flow only between compatible types during expression evaluation. +/// This function enforces a critical type-safety invariant: both trees +/// must have the same pointee-chain depth, and field children are +/// matched by `FieldDecl`. This invariant ensures that origins flow only +/// between compatible types during expression evaluation. Field pairs +/// found on both sides recurse; unmatched fields are skipped, which is +/// exercised by `CK_DerivedToBase` flows where Base's and Derived's +/// trees carry distinct direct-field FDs. /// /// Examples: /// - `int* p = &x;` flows origins from `&x` (depth 1) to `p` (depth 1) @@ -59,19 +63,31 @@ /// * 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) +/// - `S s2 = s;` flows the top-level origin and recursively flows each +/// matching `FieldDecl` subtree, so loans on `s.v.inner` propagate to +/// `s2.v.inner`. void FactsGenerator::flow(OriginNode *Dst, OriginNode *Src, bool Kill) { if (!Dst) return; - assert(Src && - "Dst is non-null but Src is null. List must have the same length"); - assert(Dst->getLength() == Src->getLength() && - "Lists must have the same length"); - while (Dst && Src) { - CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - Dst->getOriginID(), Src->getOriginID(), Kill)); - Dst = Dst->getPointeeChild(); - Src = Src->getPointeeChild(); + assert(Src && "Dst node has no paired Src node"); + + llvm::SmallVector<std::pair<OriginNode *, OriginNode *>, 4> Worklist{ + {Dst, Src}}; + while (!Worklist.empty()) { + auto [D, S] = Worklist.pop_back_val(); + assert(D->getPointeeChainLength() == S->getPointeeChainLength() && + "matched Dst/Src nodes must have equal pointee-chain length"); + while (D && S) { + CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( + D->getOriginID(), S->getOriginID(), Kill)); + for (const OriginNode::Edge &E : D->children()) + if (E.FD) + if (OriginNode *SrcF = S->getFieldChild(*E.FD)) + Worklist.push_back({E.Child, SrcF}); + D = D->getPointeeChild(); + S = S->getPointeeChild(); + } } } @@ -321,7 +337,8 @@ case CK_DerivedToBase: // It is possible that the derived class and base class have different // gsl::Pointer annotations. Skip if their origin shape differ. - if (Dest && Src && Dest->getLength() == Src->getLength()) + if (Dest && Src && + Dest->getPointeeChainLength() == Src->getPointeeChainLength()) flow(Dest, Src, /*Kill=*/true); return; case CK_ArrayToPointerDecay: @@ -336,7 +353,8 @@ case CK_BitCast: // OriginLists for Src and Dst may differ here. For example when casting // from int** to void* - if (Src && Dest && Dest->getLength() == Src->getLength()) + if (Src && Dest && + Dest->getPointeeChainLength() == Src->getPointeeChainLength()) flow(Dest, Src, /*Kill=*/true); return; default: @@ -366,12 +384,16 @@ } void FactsGenerator::VisitReturnStmt(const ReturnStmt *RS) { - if (const Expr *RetExpr = RS->getRetValue()) { - if (OriginNode *Node = getOriginNode(*RetExpr)) - for (OriginNode *L = Node; L != nullptr; L = L->getPointeeChild()) - EscapesInCurrentBlock.push_back( - FactMgr.createFact<ReturnEscapeFact>(L->getOriginID(), RetExpr)); - } + const Expr *RetExpr = RS->getRetValue(); + if (!RetExpr) + return; + OriginNode *Root = getOriginNode(*RetExpr); + if (!Root) + return; + Root->forEachOrigin([this, RetExpr](const OriginNode *Cur) { + EscapesInCurrentBlock.push_back( + FactMgr.createFact<ReturnEscapeFact>(Cur->getOriginID(), RetExpr)); + }); } void FactsGenerator::handleAssignment(const Expr *TargetExpr, @@ -583,8 +605,8 @@ if (!MTENode) return; OriginNode *SubExprNode = getOriginNode(*MTE->getSubExpr()); - assert((!SubExprNode || - MTENode->getLength() == (SubExprNode->getLength() + 1)) && + assert((!SubExprNode || MTENode->getPointeeChainLength() == + (SubExprNode->getPointeeChainLength() + 1)) && "MTE top level origin should contain a loan to the MTE itself"); OriginNode *RValMTENode = getRValueOrigins(MTE, MTENode); @@ -806,7 +828,7 @@ continue; const Expr *Arg = Args[I]; OriginNode *MovedOrigins = getOriginNode(*Arg); - assert(MovedOrigins->getLength() >= 1 && + assert(MovedOrigins->getPointeeChainLength() >= 1 && "unexpected length for r-value reference param"); // Arg is being moved to this parameter. Mark the origin as moved. CurrentBlockFacts.push_back( @@ -1009,7 +1031,7 @@ // TODO: document with code example. // std::string_view(const std::string_view& from) if (isGslPointerType(Args[I]->getType())) { - assert(!Args[I]->isGLValue() || ArgNode->getLength() >= 2); + assert(!Args[I]->isGLValue() || ArgNode->getPointeeChainLength() >= 2); ArgNode = getRValueOrigins(Args[I], ArgNode); } if (isGslOwnerType(Args[I]->getType())) { @@ -1031,7 +1053,7 @@ KillSrc = false; } } else if (shouldTrackPointerImplicitObjectArg(I)) { - assert(ArgNode->getLength() >= 2 && + assert(ArgNode->getPointeeChainLength() >= 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>(
diff --git a/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp b/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp index a23d7f2..efae173 100644 --- a/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp
@@ -127,10 +127,15 @@ /// A read operation makes the origin live with definite confidence, as it /// dominates this program point. A write operation kills the liveness of /// the origin since it overwrites the value. + /// + /// Walks the full subtree so loans held by any descendant (pointee + /// chain or field child) become visible at the use site. Lattice transfer(Lattice In, const UseFact &UF) { + const OriginNode *Root = UF.getUsedOrigins(); + if (!Root) + return In; Lattice Out = In; - for (const OriginNode *Cur = UF.getUsedOrigins(); Cur; - Cur = Cur->getPointeeChild()) { + Root->forEachOrigin([this, &UF, &Out](const OriginNode *Cur) { OriginID OID = Cur->getOriginID(); // Write kills liveness. if (UF.isWritten()) { @@ -141,7 +146,7 @@ Out = Lattice(Factory.add(Out.LiveOrigins, OID, LivenessInfo(&UF, LivenessKind::Must))); } - } + }); return Out; }
diff --git a/clang/lib/Analysis/LifetimeSafety/Origins.cpp b/clang/lib/Analysis/LifetimeSafety/Origins.cpp index 41d3ada..c4cd935 100644 --- a/clang/lib/Analysis/LifetimeSafety/Origins.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Origins.cpp
@@ -193,8 +193,9 @@ void OriginManager::attachPointeeChild(OriginNode *Parent, OriginNode *Pointee) { assert(Pointee && "pointee subtree must be non-null"); - Parent->setChildren( - {new (Allocator.Allocate<OriginNode *>()) OriginNode *(Pointee), 1}); + auto *E = new (Allocator.Allocate<OriginNode::Edge>()) + OriginNode::Edge{nullptr, Pointee}; + Parent->setChildren({E, 1}); } template <typename T> @@ -281,7 +282,8 @@ return ExprToNode[E] = buildNodeForType(Type, E); } -void OriginManager::dump(OriginID OID, llvm::raw_ostream &OS) const { +void OriginManager::dump(OriginID OID, llvm::raw_ostream &OS, + const FieldDecl *FD) const { OS << OID << " ("; Origin O = getOrigin(OID); if (const ValueDecl *VD = O.getDecl()) { @@ -297,6 +299,8 @@ } if (O.Ty) OS << ", Type : " << QualType(O.Ty, 0).getAsString(); + if (FD) + OS << ", Field: " << FD->getName(); OS << ")"; }