llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-temporal-safety Author: Utkarsh Saxena (usx95) <details> <summary>Changes</summary> Refactored the loan system to use access paths instead of loan IDs for expiry tracking, consolidating PathLoan and PlaceholderLoan into a unified Loan class. This is a non-functional refactoring to move towards more granular paths. This also removes a quadratic complexity of `handleLifetimeEnds` where we iterated over all loans to find which loans expired. --- Patch is 33.65 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/187708.diff 10 Files Affected: - (modified) clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h (+9-4) - (modified) clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h (+84-107) - (modified) clang/lib/Analysis/LifetimeSafety/Checker.cpp (+41-60) - (modified) clang/lib/Analysis/LifetimeSafety/Facts.cpp (+1-4) - (modified) clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp (+16-37) - (modified) clang/lib/Analysis/LifetimeSafety/Loans.cpp (+32-9) - (modified) clang/lib/Analysis/LifetimeSafety/MovedLoans.cpp (+2-8) - (modified) clang/test/Sema/warn-lifetime-safety-dataflow.cpp (+10-10) - (modified) clang/test/Sema/warn-lifetime-safety.cpp (+8-8) - (modified) clang/unittests/Analysis/LifetimeSafetyTest.cpp (+9-9) ``````````diff diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h index fdcf317c69cbf..0f848abd913d3 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h @@ -102,8 +102,13 @@ class IssueFact : public Fact { const OriginManager &OM) const override; }; +/// When an AccessPath expires (e.g., a variable goes out of scope), all loans +/// that are associated with this path expire. For example, if `x` expires, then +/// the loan to `x` expires. class ExpireFact : public Fact { - LoanID LID; + // The access path that expires. + AccessPath AP; + // Expired origin (e.g., its variable goes out of scope). std::optional<OriginID> OID; SourceLocation ExpiryLoc; @@ -111,11 +116,11 @@ class ExpireFact : public Fact { public: static bool classof(const Fact *F) { return F->getKind() == Kind::Expire; } - ExpireFact(LoanID LID, SourceLocation ExpiryLoc, + ExpireFact(AccessPath AP, SourceLocation ExpiryLoc, std::optional<OriginID> OID = std::nullopt) - : Fact(Kind::Expire), LID(LID), OID(OID), ExpiryLoc(ExpiryLoc) {} + : Fact(Kind::Expire), AP(AP), OID(OID), ExpiryLoc(ExpiryLoc) {} - LoanID getLoanID() const { return LID; } + const AccessPath &getAccessPath() const { return AP; } std::optional<OriginID> getOriginID() const { return OID; } SourceLocation getExpiryLoc() const { return ExpiryLoc; } diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h index 9aaf4627ce5ad..bb3e2cd907e0e 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h @@ -27,120 +27,96 @@ inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, LoanID ID) { return OS << ID.Value; } +/// Represents the base of a placeholder access path, which is either a +/// function parameter or the implicit 'this' object of an instance method. +/// Placeholder paths never expire within the function scope, as they represent +/// storage from the caller's scope. +class PlaceholderBase { + llvm::PointerUnion<const ParmVarDecl *, const CXXMethodDecl *> ParamOrMethod; +public: + PlaceholderBase(const ParmVarDecl *PVD) : ParamOrMethod(PVD) {} + PlaceholderBase(const CXXMethodDecl *MD) : ParamOrMethod(MD) {} + const ParmVarDecl *getParmVarDecl() const { + return ParamOrMethod.dyn_cast<const ParmVarDecl *>(); + } + const CXXMethodDecl *getMethodDecl() const { + return ParamOrMethod.dyn_cast<const CXXMethodDecl *>(); + } +}; + /// Represents the storage location being borrowed, e.g., a specific stack -/// variable. -/// TODO: Model access paths of other types, e.g., s.field, heap and globals. +/// variable or a field within it: var.field.* +/// +/// An AccessPath consists of: +/// - A base: either a ValueDecl, MaterializeTemporaryExpr, or PlaceholderBase +/// - A sequence of PathElements representing field accesses or interior +/// regions +/// +/// Examples: +/// - `x` -> Base=x, Elements=[] +/// - `x.field` -> Base=x, Elements=[.field] +/// - `x.*` (e.g., string_view from string) -> Base=x, Elements=[.*] +/// - `x.field.*` -> Base=x, Elements=[.field, .*] +/// - `$param.field` -> Base=$param, Elements=[.field] +/// +/// TODO: Model access paths of other types, e.g. heap and globals. class AccessPath { - // An access path can be: - // - ValueDecl * , to represent the storage location corresponding to the - // variable declared in ValueDecl. - // - MaterializeTemporaryExpr * , to represent the storage location of the - // temporary object materialized via this MaterializeTemporaryExpr. + /// The base of the access path: a variable, temporary, or placeholder. const llvm::PointerUnion<const clang::ValueDecl *, - const clang::MaterializeTemporaryExpr *> - P; - + const clang::MaterializeTemporaryExpr *, + const PlaceholderBase *> + Base; public: - AccessPath(const clang::ValueDecl *D) : P(D) {} - AccessPath(const clang::MaterializeTemporaryExpr *MTE) : P(MTE) {} - + AccessPath(const clang::ValueDecl *D) : Base(D) {} + AccessPath(const clang::MaterializeTemporaryExpr *MTE) : Base(MTE) {} + AccessPath(const PlaceholderBase *PB) : Base(PB) {} + /// Creates an extended access path by appending a path element. + /// Example: AccessPath(x_path, field) creates path to `x.field`. + AccessPath(const AccessPath &Other) + : Base(Other.Base){ + } const clang::ValueDecl *getAsValueDecl() const { - return P.dyn_cast<const clang::ValueDecl *>(); + return Base.dyn_cast<const clang::ValueDecl *>(); } - const clang::MaterializeTemporaryExpr *getAsMaterializeTemporaryExpr() const { - return P.dyn_cast<const clang::MaterializeTemporaryExpr *>(); + return Base.dyn_cast<const clang::MaterializeTemporaryExpr *>(); } - - bool operator==(const AccessPath &RHS) const { return P == RHS.P; } + const PlaceholderBase *getAsPlaceholderBase() const { + return Base.dyn_cast<const PlaceholderBase *>(); + } + bool operator==(const AccessPath &RHS) const { + return Base == RHS.Base; + } + bool operator!=(const AccessPath &RHS) const { + return !(Base == RHS.Base); + } + void dump(llvm::raw_ostream &OS) const; }; -/// An abstract base class for a single "Loan" which represents lending a -/// storage in memory. +/// Represents lending a storage location. +// +/// A loan tracks the borrowing relationship created by operations like +/// taking a pointer/reference (&x), creating a view (std::string_view sv = s), +/// or receiving a parameter. +/// +/// Examples: +/// - `int* p = &x;` creates a loan to `x` +/// - `std::string_view v = s;` creates a loan to `s.*` (interior) [FIXME] +/// - `int* p = &obj.field;` creates a loan to `obj.field` [FIXME] +/// - Parameter loans have no IssueExpr (created at function entry) class Loan { - /// TODO: Represent opaque loans. - /// TODO: Represent nullptr: loans to no path. Accessing it UB! Currently it - /// is represented as empty LoanSet -public: - enum class Kind : uint8_t { - /// A loan with an access path to a storage location. - Path, - /// A non-expiring placeholder loan for a parameter, representing a borrow - /// from the function's caller. - Placeholder - }; - - Loan(Kind K, LoanID ID) : K(K), ID(ID) {} - virtual ~Loan() = default; - - Kind getKind() const { return K; } - LoanID getID() const { return ID; } - - virtual void dump(llvm::raw_ostream &OS) const = 0; - -private: - const Kind K; const LoanID ID; -}; - -/// PathLoan represents lending a storage location that is visible within the -/// function's scope (e.g., a local variable on stack). -class PathLoan : public Loan { - AccessPath Path; - /// The expression that creates the loan, e.g., &x. + const AccessPath Path; + /// The expression that creates the loan, e.g., &x. Null for placeholder + /// loans. const Expr *IssueExpr; - public: - PathLoan(LoanID ID, AccessPath Path, const Expr *IssueExpr) - : Loan(Kind::Path, ID), Path(Path), IssueExpr(IssueExpr) {} - + Loan(LoanID ID, AccessPath Path, const Expr *IssueExpr = nullptr) + : ID(ID), Path(Path), IssueExpr(IssueExpr) {} + LoanID getID() const { return ID; } const AccessPath &getAccessPath() const { return Path; } const Expr *getIssueExpr() const { return IssueExpr; } - - void dump(llvm::raw_ostream &OS) const override; - - static bool classof(const Loan *L) { return L->getKind() == Kind::Path; } -}; - -/// A placeholder loan held by a function parameter or an implicit 'this' -/// object, representing a borrow from the caller's scope. -/// -/// Created at function entry for each pointer or reference parameter or for -/// the implicit 'this' parameter of instance methods, with an -/// origin. Unlike PathLoan, placeholder loans: -/// - Have no IssueExpr (created at function entry, not at a borrow site) -/// - Have no AccessPath (the borrowed object is not visible to the function) -/// - Do not currently expire, but may in the future when modeling function -/// invalidations (e.g., vector::push_back) -/// -/// When a placeholder loan escapes the function (e.g., via return), it -/// indicates the parameter or method should be marked [[clang::lifetimebound]], -/// enabling lifetime annotation suggestions. -class PlaceholderLoan : public Loan { - /// The function parameter or method (representing 'this') that holds this - /// placeholder loan. - llvm::PointerUnion<const ParmVarDecl *, const CXXMethodDecl *> ParamOrMethod; - -public: - PlaceholderLoan(LoanID ID, const ParmVarDecl *PVD) - : Loan(Kind::Placeholder, ID), ParamOrMethod(PVD) {} - - PlaceholderLoan(LoanID ID, const CXXMethodDecl *MD) - : Loan(Kind::Placeholder, ID), ParamOrMethod(MD) {} - - const ParmVarDecl *getParmVarDecl() const { - return ParamOrMethod.dyn_cast<const ParmVarDecl *>(); - } - - const CXXMethodDecl *getMethodDecl() const { - return ParamOrMethod.dyn_cast<const CXXMethodDecl *>(); - } - - void dump(llvm::raw_ostream &OS) const override; - - static bool classof(const Loan *L) { - return L->getKind() == Kind::Placeholder; - } + void dump(llvm::raw_ostream &OS) const; }; /// Manages the creation, storage and retrieval of loans. @@ -148,23 +124,23 @@ class LoanManager { public: LoanManager() = default; - template <typename LoanType, typename... Args> - LoanType *createLoan(Args &&...args) { - static_assert( - std::is_same_v<LoanType, PathLoan> || - std::is_same_v<LoanType, PlaceholderLoan>, - "createLoan can only be used with PathLoan or PlaceholderLoan"); - void *Mem = LoanAllocator.Allocate<LoanType>(); - auto *NewLoan = - new (Mem) LoanType(getNextLoanID(), std::forward<Args>(args)...); + Loan *createLoan(AccessPath Path, const Expr *IssueExpr = nullptr) { + void *Mem = LoanAllocator.Allocate<Loan>(); + auto *NewLoan = new (Mem) Loan(getNextLoanID(), Path, IssueExpr); AllLoans.push_back(NewLoan); return NewLoan; + } const Loan *getLoan(LoanID ID) const { assert(ID.Value < AllLoans.size()); return AllLoans[ID.Value]; } + + /// Gets or creates a placeholder base for a given parameter or method. + const PlaceholderBase *getOrCreatePlaceholderBase(const ParmVarDecl *PVD); + const PlaceholderBase *getOrCreatePlaceholderBase(const CXXMethodDecl *MD); + llvm::ArrayRef<const Loan *> getLoans() const { return AllLoans; } private: @@ -174,6 +150,7 @@ class LoanManager { /// TODO(opt): Profile and evaluate the usefullness of small buffer /// optimisation. llvm::SmallVector<const Loan *> AllLoans; + llvm::DenseMap<const Decl*, const PlaceholderBase*> PlaceholderBases; llvm::BumpPtrAllocator LoanAllocator; }; } // namespace clang::lifetimes::internal diff --git a/clang/lib/Analysis/LifetimeSafety/Checker.cpp b/clang/lib/Analysis/LifetimeSafety/Checker.cpp index db87f511a230f..86c7d5c70558f 100644 --- a/clang/lib/Analysis/LifetimeSafety/Checker.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Checker.cpp @@ -139,60 +139,47 @@ class LifetimeChecker { }; for (LoanID LID : EscapedLoans) { const Loan *L = FactMgr.getLoanMgr().getLoan(LID); - const auto *PL = dyn_cast<PlaceholderLoan>(L); - if (!PL) + const PlaceholderBase *PB = L->getAccessPath().getAsPlaceholderBase(); + if (!PB) continue; - if (const auto *PVD = PL->getParmVarDecl()) + if (const auto *PVD = PB->getParmVarDecl()) CheckParam(PVD); - else if (const auto *MD = PL->getMethodDecl()) + else if (const auto *MD = PB->getMethodDecl()) CheckImplicitThis(MD); } } - /// Checks for use-after-free & use-after-return errors when a loan expires. + /// Checks for use-after-free & use-after-return errors when an access path + /// expires (e.g., a variable goes out of scope). /// - /// This method examines all live origins at the expiry point and determines - /// if any of them hold the expiring loan. If so, it creates a pending - /// warning. - /// - /// Note: This implementation considers only the confidence of origin - /// liveness. Future enhancements could also consider the confidence of loan - /// propagation (e.g., a loan may only be held on some execution paths). + /// When a path expires, all loans having this path expires. + /// This method examines all live origins and reports warnings for loans they + /// hold that are prefixed by the expired path. void checkExpiry(const ExpireFact *EF) { - LoanID ExpiredLoan = EF->getLoanID(); - const Expr *MovedExpr = nullptr; - if (auto *ME = MovedLoans.getMovedLoans(EF).lookup(ExpiredLoan)) - MovedExpr = *ME; - + const AccessPath &ExpiredPath = EF->getAccessPath(); LivenessMap Origins = LiveOrigins.getLiveOriginsAt(EF); - bool CurDomination = false; - // The UseFact or OriginEscapesFact most indicative of a lifetime error, - // prioritized by earlier source location. - llvm::PointerUnion<const UseFact *, const OriginEscapesFact *> CausingFact = - nullptr; - for (auto &[OID, LiveInfo] : Origins) { LoanSet HeldLoans = LoanPropagation.getLoans(OID, EF); - if (!HeldLoans.contains(ExpiredLoan)) - continue; - // Loan is defaulted. - - if (!CurDomination || causingFactDominatesExpiry(LiveInfo.Kind)) - CausingFact = LiveInfo.CausingFact; + for (LoanID HeldLoanID : HeldLoans) { + const Loan *HeldLoan = FactMgr.getLoanMgr().getLoan(HeldLoanID); + if (ExpiredPath != HeldLoan->getAccessPath()) + continue; + // HeldLoan is expired because its AccessPath is expired. + PendingWarning &CurWarning = FinalWarningsMap[HeldLoan->getID()]; + const Expr *MovedExpr = nullptr; + if (auto *ME = MovedLoans.getMovedLoans(EF).lookup(HeldLoanID)) + MovedExpr = *ME; + // Skip if we already have a dominating causing fact. + if (CurWarning.CausingFactDominatesExpiry) + continue; + if (causingFactDominatesExpiry(LiveInfo.Kind)) + CurWarning.CausingFactDominatesExpiry = true; + CurWarning.CausingFact = LiveInfo.CausingFact; + CurWarning.ExpiryLoc = EF->getExpiryLoc(); + CurWarning.MovedExpr = MovedExpr; + CurWarning.InvalidatedByExpr = nullptr; + } } - if (!CausingFact) - return; - - bool LastDomination = - FinalWarningsMap.lookup(ExpiredLoan).CausingFactDominatesExpiry; - if (LastDomination) - return; - FinalWarningsMap[ExpiredLoan] = { - /*ExpiryLoc=*/EF->getExpiryLoc(), - /*CausingFact=*/CausingFact, - /*MovedExpr=*/MovedExpr, - /*InvalidatedByExpr=*/nullptr, - /*CausingFactDominatesExpiry=*/CurDomination}; } /// Checks for use-after-invalidation errors when a container is modified. @@ -206,18 +193,9 @@ class LifetimeChecker { LoanSet DirectlyInvalidatedLoans = LoanPropagation.getLoans(InvalidatedOrigin, IOF); auto IsInvalidated = [&](const Loan *L) { - auto *PathL = dyn_cast<PathLoan>(L); - auto *PlaceholderL = dyn_cast<PlaceholderLoan>(L); for (LoanID InvalidID : DirectlyInvalidatedLoans) { - const Loan *L = FactMgr.getLoanMgr().getLoan(InvalidID); - auto *InvalidPathL = dyn_cast<PathLoan>(L); - auto *InvalidPlaceholderL = dyn_cast<PlaceholderLoan>(L); - if (PathL && InvalidPathL && - PathL->getAccessPath() == InvalidPathL->getAccessPath()) - return true; - if (PlaceholderL && InvalidPlaceholderL && - PlaceholderL->getParmVarDecl() == - InvalidPlaceholderL->getParmVarDecl()) + const Loan *InvalidL = FactMgr.getLoanMgr().getLoan(InvalidID); + if (InvalidL->getAccessPath() == L->getAccessPath()) return true; } return false; @@ -248,13 +226,10 @@ class LifetimeChecker { return; for (const auto &[LID, Warning] : FinalWarningsMap) { const Loan *L = FactMgr.getLoanMgr().getLoan(LID); - - const Expr *IssueExpr = nullptr; - if (const auto *BL = dyn_cast<PathLoan>(L)) - IssueExpr = BL->getIssueExpr(); + const Expr *IssueExpr = L->getIssueExpr(); const ParmVarDecl *InvalidatedPVD = nullptr; - if (const auto *PL = dyn_cast<PlaceholderLoan>(L)) - InvalidatedPVD = PL->getParmVarDecl(); + if (const PlaceholderBase *PB = L->getAccessPath().getAsPlaceholderBase()) + InvalidatedPVD = PB->getParmVarDecl(); llvm::PointerUnion<const UseFact *, const OriginEscapesFact *> CausingFact = Warning.CausingFact; const Expr *MovedExpr = Warning.MovedExpr; @@ -263,24 +238,30 @@ class LifetimeChecker { if (const auto *UF = CausingFact.dyn_cast<const UseFact *>()) { if (Warning.InvalidatedByExpr) { if (IssueExpr) + // Use-after-invalidation of an object on stack. SemaHelper->reportUseAfterInvalidation(IssueExpr, UF->getUseExpr(), Warning.InvalidatedByExpr); - if (InvalidatedPVD) + else if (InvalidatedPVD) + // Use-after-invalidation of a parameter. SemaHelper->reportUseAfterInvalidation( InvalidatedPVD, UF->getUseExpr(), Warning.InvalidatedByExpr); } else + // Scope-based expiry (use-after-scope). SemaHelper->reportUseAfterFree(IssueExpr, UF->getUseExpr(), MovedExpr, ExpiryLoc); } else if (const auto *OEF = CausingFact.dyn_cast<const OriginEscapesFact *>()) { if (const auto *RetEscape = dyn_cast<ReturnEscapeFact>(OEF)) + // Return stack address. SemaHelper->reportUseAfterReturn( IssueExpr, RetEscape->getReturnExpr(), MovedExpr, ExpiryLoc); else if (const auto *FieldEscape = dyn_cast<FieldEscapeFact>(OEF)) + // Dangling field. SemaHelper->reportDanglingField( IssueExpr, FieldEscape->getFieldDecl(), MovedExpr, ExpiryLoc); else if (const auto *GlobalEscape = dyn_cast<GlobalEscapeFact>(OEF)) + // Global escape. SemaHelper->reportDanglingGlobal(IssueExpr, GlobalEscape->getGlobal(), MovedExpr, ExpiryLoc); else diff --git a/clang/lib/Analysis/LifetimeSafety/Facts.cpp b/clang/lib/Analysis/LifetimeSafety/Facts.cpp index 535da2a014273..1bc0521a72359 100644 --- a/clang/lib/Analysis/LifetimeSafety/Facts.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Facts.cpp @@ -8,10 +8,7 @@ #include "clang/Analysis/Analyses/LifetimeSafety/Facts.h" #include "clang/AST/Decl.h" -#include "clang/AST/DeclID.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" -#include "clang/Analysis/FlowSensitive/DataflowWorklist.h" -#include "llvm/ADT/STLFunctionalExtras.h" namespace clang::lifetimes::internal { @@ -32,7 +29,7 @@ void IssueFact::dump(llvm::raw_ostream &OS, const LoanManager &LM, void ExpireFact::dump(llvm::raw_ostream &OS, const LoanManager &LM, const OriginManager &OM) const { OS << "Expire ("; - LM.getLoan(getLoanID())->dump(OS); + getAccessPath().dump(OS); if (auto OID = getOriginID()) { OS << ", Origin: "; OM.dump(*OID, OS); diff --git a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp index 3259505584c9f..42cc4d17c39da 100644 --- a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp +++ b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp @@ -69,12 +69,11 @@ void FactsGenerator::flow(OriginList *Dst, OriginList *Src, bool Kill) { /// This function should be called whenever a DeclRefExpr represents a borrow. /// \param DRE The declaration reference expression that initiates the borrow. /// \return The new Loan on success, nullptr otherwise. -static const PathLoan *createLoan(FactManager &FactMgr, - const DeclRefExpr *DRE) { +static const Loan *createLoan(FactManager &FactMgr, const DeclRefExpr *DRE) { if (const auto *VD = dyn_cast<ValueDecl>(DRE->getDecl())... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/187708 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
