https://github.com/usx95 updated https://github.com/llvm/llvm-project/pull/168344
>From 43233fe663b442785209415fe7a274d36cd10473 Mon Sep 17 00:00:00 2001 From: Utkarsh Saxena <[email protected]> Date: Mon, 17 Nov 2025 10:53:05 +0000 Subject: [PATCH] lifetime-safety-multi-origin --- .../Analysis/Analyses/LifetimeSafety/Facts.h | 9 +- .../Analyses/LifetimeSafety/FactsGenerator.h | 19 +- .../Analyses/LifetimeSafety/Origins.h | 67 +++- clang/lib/Analysis/LifetimeSafety/Facts.cpp | 5 +- .../LifetimeSafety/FactsGenerator.cpp | 312 +++++++++++++----- .../Analysis/LifetimeSafety/LiveOrigins.cpp | 20 +- .../LifetimeSafety/LoanPropagation.cpp | 3 +- clang/lib/Analysis/LifetimeSafety/Origins.cpp | 143 +++++--- clang/test/Sema/warn-lifetime-safety.cpp | 127 +++++-- .../unittests/Analysis/LifetimeSafetyTest.cpp | 5 +- 10 files changed, 509 insertions(+), 201 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h index b9cad5340c940..3ae2458ebd239 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h @@ -152,7 +152,8 @@ class ReturnOfOriginFact : public Fact { class UseFact : public Fact { const Expr *UseExpr; - OriginID OID; + // The origins of the expression being used. + llvm::SmallVector<OriginID, 1> OIDs; // 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; @@ -160,10 +161,10 @@ class UseFact : public Fact { public: static bool classof(const Fact *F) { return F->getKind() == Kind::Use; } - UseFact(const Expr *UseExpr, OriginManager &OM) - : Fact(Kind::Use), UseExpr(UseExpr), OID(OM.get(*UseExpr)) {} + UseFact(const Expr *UseExpr, llvm::ArrayRef<OriginID> OIDs) + : Fact(Kind::Use), UseExpr(UseExpr), OIDs(OIDs.begin(), OIDs.end()) {} - OriginID getUsedOrigin() const { return OID; } + llvm::ArrayRef<OriginID> getUsedOrigins() const { return OIDs; } 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 4c8ab3f859a49..bf19f87f9e0b7 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/FactsGenerator.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/FactsGenerator.h @@ -50,6 +50,11 @@ class FactsGenerator : public ConstStmtVisitor<FactsGenerator> { void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *MTE); private: + OriginTree *getTree(const ValueDecl &D); + OriginTree *getTree(const Expr &E); + + void flow(OriginTree *Dst, OriginTree *Src, bool Kill); + void handleDestructor(const CFGAutomaticObjDtor &DtorOpt); void handleGSLPointerConstruction(const CXXConstructExpr *CCE); @@ -64,32 +69,24 @@ class FactsGenerator : public ConstStmtVisitor<FactsGenerator> { template <typename Destination, typename Source> void flowOrigin(const Destination &D, const Source &S) { - OriginID DestOID = FactMgr.getOriginMgr().getOrCreate(D); - OriginID SrcOID = FactMgr.getOriginMgr().get(S); - CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( - DestOID, SrcOID, /*KillDest=*/false)); + flow(getTree(D), getTree(S), /*Kill=*/false); } template <typename Destination, typename Source> void killAndFlowOrigin(const Destination &D, const Source &S) { - OriginID DestOID = FactMgr.getOriginMgr().getOrCreate(D); - OriginID SrcOID = FactMgr.getOriginMgr().get(S); - CurrentBlockFacts.push_back( - FactMgr.createFact<OriginFlowFact>(DestOID, SrcOID, /*KillDest=*/true)); + flow(getTree(D), getTree(S), /*Kill=*/true); } /// Checks if the expression is a `void("__lifetime_test_point_...")` cast. /// If so, creates a `TestPointFact` and returns true. bool handleTestPoint(const CXXFunctionalCastExpr *FCE); - void handleAssignment(const Expr *LHSExpr, const Expr *RHSExpr); - // A DeclRefExpr will be treated as a use of the referenced decl. It will be // checked for use-after-free unless it is later marked as being written to // (e.g. on the left-hand side of an assignment). void handleUse(const DeclRefExpr *DRE); - void markUseAsWrite(const DeclRefExpr *DRE); + void markUseAsWrite(const Expr *E); FactManager &FactMgr; AnalysisDeclContext &AC; diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h index 56b9010f41fa2..3f58e39b1e647 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h @@ -52,28 +52,45 @@ struct Origin { } }; +/// A tree of origins representing levels of indirection for pointer-like +/// types, or a single origin for non-pointer lvalues. +struct OriginTree { + OriginID OID; + OriginTree *Pointee = nullptr; + + OriginTree(OriginID OID) : OID(OID) {} + + size_t getDepth() const { + size_t Depth = 1; + const OriginTree *T = this; + while (T->Pointee) { + T = T->Pointee; + Depth++; + } + return Depth; + } +}; + +bool isGslPointerType(QualType QT); +bool isGslOwnerType(QualType QT); +bool isPointerType(QualType QT); + /// Manages the creation, storage, and retrieval of origins for pointer-like /// variables and expressions. class OriginManager { public: - OriginManager() = default; + /// Gets or creates the OriginTree for a given ValueDecl. + OriginTree *getOrCreateTree(const ValueDecl *D); - Origin &addOrigin(OriginID ID, const clang::ValueDecl &D); - Origin &addOrigin(OriginID ID, const clang::Expr &E); - - // TODO: Mark this method as const once we remove the call to getOrCreate. - OriginID get(const Expr &E); - - OriginID get(const ValueDecl &D); - - OriginID getOrCreate(const Expr &E); + /// Gets or creates the OriginTree for a given Expr. + /// Returns nullptr for rvalues of non-pointer type as these do not have + /// origins. + OriginTree *getOrCreateTree(const Expr *E, ASTContext &Ctx); const Origin &getOrigin(OriginID ID) const; llvm::ArrayRef<Origin> getOrigins() const { return AllOrigins; } - OriginID getOrCreate(const ValueDecl &D); - unsigned getNumOrigins() const { return NextOriginID.Value; } void dump(OriginID OID, llvm::raw_ostream &OS) const; @@ -81,12 +98,32 @@ class OriginManager { private: OriginID getNextOriginID() { return NextOriginID++; } + OriginID createOrigin(const ValueDecl *D) { + OriginID NewID = getNextOriginID(); + AllOrigins.emplace_back(NewID, D); + return NewID; + } + + OriginID createOrigin(const Expr *E) { + OriginID NewID = getNextOriginID(); + AllOrigins.emplace_back(NewID, E); + return NewID; + } + + OriginTree *createNode(OriginID OID) { + return new (TreeAllocator.Allocate<OriginTree>()) OriginTree(OID); + } + + template <typename T> + OriginTree *buildTreeForType(QualType QT, const T *Node); + OriginID NextOriginID{0}; - /// TODO(opt): Profile and evaluate the usefullness of small buffer + /// TODO(opt): Profile and evaluate the usefulness of small buffer /// optimisation. llvm::SmallVector<Origin> AllOrigins; - llvm::DenseMap<const clang::ValueDecl *, OriginID> DeclToOriginID; - llvm::DenseMap<const clang::Expr *, OriginID> ExprToOriginID; + llvm::BumpPtrAllocator TreeAllocator; + llvm::DenseMap<const clang::ValueDecl *, OriginTree *> DeclToTreeMap; + llvm::DenseMap<const clang::Expr *, OriginTree *> ExprToTreeMap; }; } // namespace clang::lifetimes::internal diff --git a/clang/lib/Analysis/LifetimeSafety/Facts.cpp b/clang/lib/Analysis/LifetimeSafety/Facts.cpp index 190c038f46401..4c97577dac6db 100644 --- a/clang/lib/Analysis/LifetimeSafety/Facts.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Facts.cpp @@ -53,7 +53,10 @@ void ReturnOfOriginFact::dump(llvm::raw_ostream &OS, const LoanManager &, void UseFact::dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &OM) const { OS << "Use ("; - OM.dump(getUsedOrigin(), OS); + for (OriginID OID : getUsedOrigins()) { + OM.dump(OID, OS); + OS << " "; + } OS << ", " << (isWritten() ? "Write" : "Read") << ")\n"; } diff --git a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp index 381ff99aae420..bea7d0986d8d9 100644 --- a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp +++ b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp @@ -6,6 +6,10 @@ // //===----------------------------------------------------------------------===// +#include <cassert> +#include <string> + +#include "clang/AST/OperationKinds.h" #include "clang/Analysis/Analyses/LifetimeSafety/FactsGenerator.h" #include "clang/Analysis/Analyses/LifetimeSafety/LifetimeAnnotations.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" @@ -15,28 +19,34 @@ namespace clang::lifetimes::internal { using llvm::isa_and_present; -static bool isGslPointerType(QualType QT) { - if (const auto *RD = QT->getAsCXXRecordDecl()) { - // We need to check the template definition for specializations. - if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(RD)) - return CTSD->getSpecializedTemplate() - ->getTemplatedDecl() - ->hasAttr<PointerAttr>(); - return RD->hasAttr<PointerAttr>(); - } - return false; -} - -static bool isPointerType(QualType QT) { - return QT->isPointerOrReferenceType() || isGslPointerType(QT); -} // Check if a type has an origin. static bool hasOrigin(const Expr *E) { return E->isGLValue() || isPointerType(E->getType()); } -static bool hasOrigin(const VarDecl *VD) { - return isPointerType(VD->getType()); +OriginTree *FactsGenerator::getTree(const ValueDecl &D) { + return FactMgr.getOriginMgr().getOrCreateTree(&D); +} +OriginTree *FactsGenerator::getTree(const Expr &E) { + return FactMgr.getOriginMgr().getOrCreateTree(&E, AC.getASTContext()); +} + +void FactsGenerator::flow(OriginTree *Dst, OriginTree *Src, bool Kill) { + if (!Dst) + return; + DEBUG_WITH_TYPE("multi", llvm::errs() + << "Dst depth = " << Dst->getDepth() << "\n"); + assert(Src); + DEBUG_WITH_TYPE("multi", llvm::errs() + << "Src depth = " << Src->getDepth() << "\n"); + assert(Dst->getDepth() == Src->getDepth() && "Trees must be same shape"); + + while (Dst && Src) { + CurrentBlockFacts.push_back( + FactMgr.createFact<OriginFlowFact>(Dst->OID, Src->OID, Kill)); + Dst = Dst->Pointee; + Src = Src->Pointee; + } } /// Creates a loan for the storage path of a given declaration reference. @@ -53,6 +63,19 @@ static const Loan *createLoan(FactManager &FactMgr, const DeclRefExpr *DRE) { } void FactsGenerator::run() { + + if (const Decl *D = AC.getDecl()) { + if (const auto *ND = dyn_cast<NamedDecl>(D)) { + DEBUG_WITH_TYPE("multi", + llvm::errs() + << "=============================================\n"); + DEBUG_WITH_TYPE("multi", llvm::dbgs() + << "Function: " + << ND->getQualifiedNameAsString() << "\n"); + // DEBUG_WITH_TYPE("multi", AC.getBody()->dumpColor()); + } + } + llvm::TimeTraceScope TimeProfile("FactGenerator"); // Iterate through the CFG blocks in reverse post-order to ensure that // initializations and destructions are processed in the correct sequence. @@ -60,10 +83,12 @@ void FactsGenerator::run() { CurrentBlockFacts.clear(); for (unsigned I = 0; I < Block->size(); ++I) { const CFGElement &Element = Block->Elements[I]; - if (std::optional<CFGStmt> CS = Element.getAs<CFGStmt>()) + if (std::optional<CFGStmt> CS = Element.getAs<CFGStmt>()) { + DEBUG_WITH_TYPE("multi", llvm::errs() << "Processing: \n"); + DEBUG_WITH_TYPE("multi", CS->getStmt()->dumpColor()); Visit(CS->getStmt()); - else if (std::optional<CFGAutomaticObjDtor> DtorOpt = - Element.getAs<CFGAutomaticObjDtor>()) + } else if (std::optional<CFGAutomaticObjDtor> DtorOpt = + Element.getAs<CFGAutomaticObjDtor>()) handleDestructor(*DtorOpt); } FactMgr.addBlockFacts(Block, CurrentBlockFacts); @@ -73,12 +98,33 @@ void FactsGenerator::run() { void FactsGenerator::VisitDeclStmt(const DeclStmt *DS) { for (const Decl *D : DS->decls()) if (const auto *VD = dyn_cast<VarDecl>(D)) - if (hasOrigin(VD)) - if (const Expr *InitExpr = VD->getInit()) - killAndFlowOrigin(*VD, *InitExpr); + if (const Expr *InitExpr = VD->getInit()) { + OriginTree *VDTree = getTree(*VD); // Dst + if (!VDTree) + continue; + OriginTree *InitTree = getTree(*InitExpr); // Src + if (!InitTree) + continue; + // TODO: Document escape hatch. + // e.g. Ranges&& constructed from move. + if (VD->getType()->isRValueReferenceType() && InitExpr->isXValue()) { + // If the variable is an rvalue reference or + // the initializer is an + flow(VDTree->Pointee, InitTree->Pointee, /*Kill=*/true); + continue; + } + // DS->dumpColor(); + // llvm::errs() << "VD: " << VD->getName() << "\n"; + // llvm::errs() << "isGslPointerType(VD->getType())" + // << isGslPointerType(VD->getType()) << "\n"; + // llvm::errs() << "VDTree depth = " << VDTree->getDepth() << "\n"; + flow(VDTree, InitTree, /*Kill=*/true); + } } void FactsGenerator::VisitDeclRefExpr(const DeclRefExpr *DRE) { + if (DRE->getFoundDecl()->isFunctionOrFunctionTemplate() || !DRE->isGLValue()) + return; handleUse(DRE); // For non-pointer/non-view types, a reference to the variable's storage // is a borrow. We create a loan for it. @@ -90,12 +136,14 @@ void FactsGenerator::VisitDeclRefExpr(const DeclRefExpr *DRE) { // single-origin model cannot distinguish between a loan to the variable's // storage and a loan to what it points to. A multi-origin model would be // required for this. - if (!isPointerType(DRE->getType())) { - if (const Loan *L = createLoan(FactMgr, DRE)) { - OriginID ExprOID = FactMgr.getOriginMgr().getOrCreate(*DRE); - CurrentBlockFacts.push_back( - FactMgr.createFact<IssueFact>(L->ID, ExprOID)); - } + if (!isPointerType(DRE->getType()) && + !DRE->getDecl()->getType()->isReferenceType()) { + const Loan *L = createLoan(FactMgr, DRE); + assert(L); + OriginTree *tree = getTree(*DRE); + assert(tree && "lvalue DRE of non-pointer type should have an origin tree"); + CurrentBlockFacts.push_back( + FactMgr.createFact<IssueFact>(L->ID, tree->OID)); } } @@ -109,12 +157,14 @@ void FactsGenerator::VisitCXXConstructExpr(const CXXConstructExpr *CCE) { void FactsGenerator::VisitCXXMemberCallExpr(const CXXMemberCallExpr *MCE) { // Specifically for conversion operators, // like `std::string_view p = std::string{};` - if (isGslPointerType(MCE->getType()) && - isa_and_present<CXXConversionDecl>(MCE->getCalleeDecl())) { + if (isa_and_present<CXXConversionDecl>(MCE->getCalleeDecl()) && + isGslPointerType(MCE->getType()) && + isGslOwnerType(MCE->getImplicitObjectArgument()->getType())) { // The argument is the implicit object itself. handleFunctionCall(MCE, MCE->getMethodDecl(), {MCE->getImplicitObjectArgument()}, /*IsGslConstruction=*/true); + return; } if (const CXXMethodDecl *Method = MCE->getMethodDecl()) { // Construct the argument list, with the implicit 'this' object as the @@ -136,15 +186,41 @@ void FactsGenerator::VisitCXXNullPtrLiteralExpr( const CXXNullPtrLiteralExpr *N) { /// TODO: Handle nullptr expr as a special 'null' loan. Uninitialized /// pointers can use the same type of loan. - FactMgr.getOriginMgr().getOrCreate(*N); + getTree(*N); } void FactsGenerator::VisitImplicitCastExpr(const ImplicitCastExpr *ICE) { - if (!hasOrigin(ICE)) + OriginTree *Dest = getTree(*ICE); + if (!Dest) + return; + OriginTree *SrcTree = getTree(*ICE->getSubExpr()); + + if (ICE->getCastKind() == CK_LValueToRValue) { + // TODO: Decide what to do for x-values here. + if (!ICE->getSubExpr()->isLValue()) + return; + + assert(SrcTree && "LValue being cast to RValue has no origin tree"); + // The result of an LValue-to-RValue cast on a reference-to-pointer like + // has the inner origin. Get rid of the outer origin. + flow(getTree(*ICE), SrcTree->Pointee, /*Kill=*/true); + return; + } + if (ICE->getCastKind() == CK_NullToPointer) { + getTree(*ICE); + // TODO: Flow into them a null origin. return; - // An ImplicitCastExpr node itself gets an origin, which flows from the - // origin of its sub-expression (after stripping its own parens/casts). - killAndFlowOrigin(*ICE, *ICE->getSubExpr()); + } + if (ICE->getCastKind() == CK_NoOp || + ICE->getCastKind() == CK_ConstructorConversion || + ICE->getCastKind() == CK_UserDefinedConversion) + flow(Dest, SrcTree, /*Kill=*/true); + if (ICE->getCastKind() == CK_FunctionToPointerDecay || + ICE->getCastKind() == CK_BuiltinFnToFnPtr || + ICE->getCastKind() == CK_ArrayToPointerDecay) { + // Ignore function-to-pointer decays. + return; + } } void FactsGenerator::VisitUnaryOperator(const UnaryOperator *UO) { @@ -164,19 +240,34 @@ void FactsGenerator::VisitUnaryOperator(const UnaryOperator *UO) { void FactsGenerator::VisitReturnStmt(const ReturnStmt *RS) { if (const Expr *RetExpr = RS->getRetValue()) { - if (hasOrigin(RetExpr)) { - OriginID OID = FactMgr.getOriginMgr().getOrCreate(*RetExpr); - CurrentBlockFacts.push_back(FactMgr.createFact<ReturnOfOriginFact>(OID)); - } + if (OriginTree *Tree = getTree(*RetExpr)) + CurrentBlockFacts.push_back( + FactMgr.createFact<ReturnOfOriginFact>(Tree->OID)); } } void FactsGenerator::VisitBinaryOperator(const BinaryOperator *BO) { - if (BO->isAssignmentOp()) - handleAssignment(BO->getLHS(), BO->getRHS()); + if (BO->isCompoundAssignmentOp()) + return; + if (BO->isAssignmentOp()) { + const Expr *LHSExpr = BO->getLHS(); + const Expr *RHSExpr = BO->getRHS(); + + if (const auto *DRE_LHS = + dyn_cast<DeclRefExpr>(LHSExpr->IgnoreParenImpCasts())) { + OriginTree *LHSTree = getTree(*DRE_LHS); + OriginTree *RHSTree = getTree(*RHSExpr); + // TODO: Handle reference types. + markUseAsWrite(DRE_LHS); + // Kill the old loans of the destination origin and flow the new loans + // from the source origin. + flow(LHSTree->Pointee, RHSTree, /*Kill=*/true); + } + } } void FactsGenerator::VisitConditionalOperator(const ConditionalOperator *CO) { + if (hasOrigin(CO)) { // Merge origins from both branches of the conditional operator. // We kill to clear the initial state and merge both origins into it. @@ -188,8 +279,26 @@ void FactsGenerator::VisitConditionalOperator(const ConditionalOperator *CO) { void FactsGenerator::VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE) { // Assignment operators have special "kill-then-propagate" semantics // and are handled separately. - if (OCE->isAssignmentOp() && OCE->getNumArgs() == 2) { - handleAssignment(OCE->getArg(0), OCE->getArg(1)); + if (OCE->getOperator() == OO_Equal && OCE->getNumArgs() == 2) { + + const Expr *LHSExpr = OCE->getArg(0); + const Expr *RHSExpr = OCE->getArg(1); + + if (const auto *DRE_LHS = + dyn_cast<DeclRefExpr>(LHSExpr->IgnoreParenImpCasts())) { + OriginTree *LHSTree = getTree(*DRE_LHS); + OriginTree *RHSTree = getTree(*RHSExpr); + + // TODO: Doc why. + // Construction of GSL! View &(const View &). + if (RHSExpr->isGLValue()) + RHSTree = RHSTree->Pointee; + // TODO: Handle reference types. + markUseAsWrite(DRE_LHS); + // Kill the old loans of the destination origin and flow the new loans + // from the source origin. + flow(LHSTree->Pointee, RHSTree, /*Kill=*/true); + } return; } handleFunctionCall(OCE, OCE->getDirectCallee(), @@ -218,11 +327,24 @@ void FactsGenerator::VisitInitListExpr(const InitListExpr *ILE) { void FactsGenerator::VisitMaterializeTemporaryExpr( const MaterializeTemporaryExpr *MTE) { - if (!hasOrigin(MTE)) + OriginTree *MTETree = getTree(*MTE); + OriginTree *SubExprTree = getTree(*MTE->getSubExpr()); + if (!MTETree) return; - // A temporary object's origin is the same as the origin of the - // expression that initializes it. - killAndFlowOrigin(*MTE, *MTE->getSubExpr()); + if (MTE->isGLValue()) { + assert(!SubExprTree || + MTETree->getDepth() == SubExprTree->getDepth() + 1 && "todo doc."); + // Issue a loan to the MTE. + // const Loan *L = createLoan(FactMgr, MTE); + // CurrentBlockFacts.push_back( + // FactMgr.createFact<IssueFact>(L->ID, MTETree->OID)); + if (SubExprTree) + flow(MTETree->Pointee, SubExprTree, /*Kill=*/true); + } else { + assert(MTE->isXValue()); + flow(MTETree, SubExprTree, /*Kill=*/true); + } + // TODO: MTE top level origin should contain a loan to the MTE itself. } void FactsGenerator::handleDestructor(const CFGAutomaticObjDtor &DtorOpt) { @@ -251,13 +373,23 @@ void FactsGenerator::handleGSLPointerConstruction(const CXXConstructExpr *CCE) { assert(isGslPointerType(CCE->getType())); if (CCE->getNumArgs() != 1) return; - if (hasOrigin(CCE->getArg(0))) - killAndFlowOrigin(*CCE, *CCE->getArg(0)); - else + + if (hasOrigin(CCE->getArg(0))) { + // TODO: Add code example here. + OriginTree *ArgTree = getTree(*CCE->getArg(0)); + assert(ArgTree && "GSL pointer argument should have an origin tree"); + // GSL pointer is constructed from another gsl pointer. + // TODO: Add proper assertions. + if (ArgTree->getDepth() == 2) + ArgTree = ArgTree->Pointee; + flow(getTree(*CCE), ArgTree, /*Kill=*/true); + } else { // This could be a new borrow. + // TODO: Add code example here. handleFunctionCall(CCE, CCE->getConstructor(), {CCE->getArgs(), CCE->getNumArgs()}, /*IsGslConstruction=*/true); + } } /// Checks if a call-like expression creates a borrow by passing a value to a @@ -268,8 +400,9 @@ void FactsGenerator::handleFunctionCall(const Expr *Call, const FunctionDecl *FD, ArrayRef<const Expr *> Args, bool IsGslConstruction) { + OriginTree *CallTree = getTree(*Call); // Ignore functions returning values with no origin. - if (!FD || !hasOrigin(Call)) + if (!FD || !CallTree) return; auto IsArgLifetimeBound = [FD](unsigned I) -> bool { const ParmVarDecl *PVD = nullptr; @@ -282,22 +415,39 @@ void FactsGenerator::handleFunctionCall(const Expr *Call, // For explicit arguments, find the corresponding parameter // declaration. PVD = Method->getParamDecl(I - 1); - } else if (I < FD->getNumParams()) + } else if (I < FD->getNumParams()) { // For free functions or static methods. PVD = FD->getParamDecl(I); + } return PVD ? PVD->hasAttr<clang::LifetimeBoundAttr>() : false; }; if (Args.empty()) return; - bool killedSrc = false; - for (unsigned I = 0; I < Args.size(); ++I) - if (IsGslConstruction || IsArgLifetimeBound(I)) { - if (!killedSrc) { - killedSrc = true; - killAndFlowOrigin(*Call, *Args[I]); - } else - flowOrigin(*Call, *Args[I]); + bool KillSrc = true; + for (unsigned I = 0; I < Args.size(); ++I) { + OriginTree *ArgTree = getTree(*Args[I]); + if (!ArgTree) + continue; + if (IsGslConstruction) { + // TODO: document with code example. + // std::string_view(const std::string_view& from) + if (isGslPointerType(Args[I]->getType()) && Args[I]->isGLValue()) { + assert(ArgTree->getDepth() >= 2); + ArgTree = ArgTree->Pointee; + } + // GSL construction creates a view that borrows from arguments. + // This implies flowing origins through the tree structure. + flow(CallTree, ArgTree, 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 constraints the top-level origin. + CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( + CallTree->OID, ArgTree->OID, KillSrc)); + KillSrc = false; } + } } /// Checks if the expression is a `void("__lifetime_test_point_...")` cast. @@ -321,35 +471,31 @@ bool FactsGenerator::handleTestPoint(const CXXFunctionalCastExpr *FCE) { return false; } -void FactsGenerator::handleAssignment(const Expr *LHSExpr, - const Expr *RHSExpr) { - if (!hasOrigin(LHSExpr)) - return; - // Find the underlying variable declaration for the left-hand side. - if (const auto *DRE_LHS = - dyn_cast<DeclRefExpr>(LHSExpr->IgnoreParenImpCasts())) { - markUseAsWrite(DRE_LHS); - if (const auto *VD_LHS = dyn_cast<ValueDecl>(DRE_LHS->getDecl())) { - // Kill the old loans of the destination origin and flow the new loans - // from the source origin. - killAndFlowOrigin(*VD_LHS, *RHSExpr); - } - } -} - // A DeclRefExpr will be treated as a use of the referenced decl. It will be // checked for use-after-free unless it is later marked as being written to // (e.g. on the left-hand side of an assignment). void FactsGenerator::handleUse(const DeclRefExpr *DRE) { - if (isPointerType(DRE->getType())) { - UseFact *UF = FactMgr.createFact<UseFact>(DRE, FactMgr.getOriginMgr()); - CurrentBlockFacts.push_back(UF); - assert(!UseFacts.contains(DRE)); - UseFacts[DRE] = UF; + if (!isPointerType(DRE->getType())) + return; + OriginTree *tree = getTree(*DRE); + if (!tree) + return; + llvm::SmallVector<OriginID, 1> UsedOrigins; + OriginTree *T = tree; + while (T) { + UsedOrigins.push_back(T->OID); + T = T->Pointee; } + UseFact *UF = FactMgr.createFact<UseFact>(DRE, UsedOrigins); + CurrentBlockFacts.push_back(UF); + assert(!UseFacts.contains(DRE)); + UseFacts[DRE] = UF; } -void FactsGenerator::markUseAsWrite(const DeclRefExpr *DRE) { +void FactsGenerator::markUseAsWrite(const Expr *E) { + auto *DRE = dyn_cast<DeclRefExpr>(E); + if (!DRE) + return; if (!isPointerType(DRE->getType())) return; assert(UseFacts.contains(DRE)); diff --git a/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp b/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp index 59f594e50fb46..eb054a3cc6761 100644 --- a/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp @@ -111,13 +111,19 @@ class AnalysisImpl /// dominates this program point. A write operation kills the liveness of /// the origin since it overwrites the value. Lattice transfer(Lattice In, const UseFact &UF) { - OriginID OID = UF.getUsedOrigin(); - // Write kills liveness. - if (UF.isWritten()) - return Lattice(Factory.remove(In.LiveOrigins, OID)); - // Read makes origin live with definite confidence (dominates this point). - return Lattice(Factory.add(In.LiveOrigins, OID, - LivenessInfo(&UF, LivenessKind::Must))); + Lattice Out = In; + for (OriginID OID : UF.getUsedOrigins()) { + // Write kills liveness. + if (UF.isWritten()) { + Out = Lattice(Factory.remove(Out.LiveOrigins, OID)); + } else { + // Read makes origin live with definite confidence (dominates this + // point). + Out = Lattice(Factory.add(Out.LiveOrigins, OID, + LivenessInfo(&UF, LivenessKind::Must))); + } + } + return Out; } /// Issuing a new loan to an origin kills its liveness. diff --git a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp index 0e6c194123df8..4511572215bd6 100644 --- a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp @@ -62,7 +62,8 @@ static llvm::BitVector computePersistentOrigins(const FactManager &FactMgr, CheckOrigin(F->getAs<ReturnOfOriginFact>()->getReturnedOriginID()); break; case Fact::Kind::Use: - CheckOrigin(F->getAs<UseFact>()->getUsedOrigin()); + for (OriginID OID : F->getAs<UseFact>()->getUsedOrigins()) + CheckOrigin(OID); break; case Fact::Kind::Expire: case Fact::Kind::TestPoint: diff --git a/clang/lib/Analysis/LifetimeSafety/Origins.cpp b/clang/lib/Analysis/LifetimeSafety/Origins.cpp index 0f2eaa94a5987..66cea3796889b 100644 --- a/clang/lib/Analysis/LifetimeSafety/Origins.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Origins.cpp @@ -7,70 +7,115 @@ //===----------------------------------------------------------------------===// #include "clang/Analysis/Analyses/LifetimeSafety/Origins.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/Attr.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/DeclTemplate.h" namespace clang::lifetimes::internal { +bool isGslPointerType(QualType QT) { + if (const auto *RD = QT->getAsCXXRecordDecl()) { + if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(RD)) + return CTSD->getSpecializedTemplate() + ->getTemplatedDecl() + ->hasAttr<PointerAttr>(); + return RD->hasAttr<PointerAttr>(); + } + return false; +} + +bool isGslOwnerType(QualType QT) { + if (const auto *RD = QT->getAsCXXRecordDecl()) { + if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(RD)) + return CTSD->getSpecializedTemplate() + ->getTemplatedDecl() + ->hasAttr<OwnerAttr>(); + return RD->hasAttr<OwnerAttr>(); + } + return false; +} + +bool isPointerType(QualType QT) { + return QT->isPointerOrReferenceType() || isGslPointerType(QT); +} + void OriginManager::dump(OriginID OID, llvm::raw_ostream &OS) const { OS << OID << " ("; Origin O = getOrigin(OID); - if (const ValueDecl *VD = O.getDecl()) + if (const ValueDecl *VD = O.getDecl()) { OS << "Decl: " << VD->getNameAsString(); - else if (const Expr *E = O.getExpr()) + } else if (const Expr *E = O.getExpr()) { OS << "Expr: " << E->getStmtClassName(); - else + if (auto *DRE = dyn_cast<DeclRefExpr>(E)) { + if (const ValueDecl *VD = DRE->getDecl()) + OS << "(" << VD->getNameAsString() << ")"; + } + } else { OS << "Unknown"; + } OS << ")"; } -Origin &OriginManager::addOrigin(OriginID ID, const clang::ValueDecl &D) { - AllOrigins.emplace_back(ID, &D); - return AllOrigins.back(); -} - -Origin &OriginManager::addOrigin(OriginID ID, const clang::Expr &E) { - AllOrigins.emplace_back(ID, &E); - return AllOrigins.back(); +template <typename T> +OriginTree *OriginManager::buildTreeForType(QualType QT, const T *Node) { + assert(isPointerType(QT) && "buildTreeForType called for non-pointer type"); + OriginTree *Root = createNode(createOrigin(Node)); + 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 (isPointerType(PointeeTy)) + Root->Pointee = buildTreeForType(PointeeTy, Node); + } + return Root; } -// TODO: Mark this method as const once we remove the call to getOrCreate. -OriginID OriginManager::get(const Expr &E) { - if (auto *ParenIgnored = E.IgnoreParens(); ParenIgnored != &E) - return get(*ParenIgnored); - auto It = ExprToOriginID.find(&E); - if (It != ExprToOriginID.end()) +OriginTree *OriginManager::getOrCreateTree(const ValueDecl *D) { + if (!isPointerType(D->getType())) + return nullptr; + auto It = DeclToTreeMap.find(D); + if (It != DeclToTreeMap.end()) return It->second; - // If the expression itself has no specific origin, and it's a reference - // to a declaration, its origin is that of the declaration it refers to. - // For pointer types, where we don't pre-emptively create an origin for the - // DeclRefExpr itself. - if (const auto *DRE = dyn_cast<DeclRefExpr>(&E)) - return get(*DRE->getDecl()); - // TODO: This should be an assert(It != ExprToOriginID.end()). The current - // implementation falls back to getOrCreate to avoid crashing on - // yet-unhandled pointer expressions, creating an empty origin for them. - return getOrCreate(E); + return DeclToTreeMap[D] = buildTreeForType(D->getType(), D); } -OriginID OriginManager::get(const ValueDecl &D) { - auto It = DeclToOriginID.find(&D); - // TODO: This should be an assert(It != DeclToOriginID.end()). The current - // implementation falls back to getOrCreate to avoid crashing on - // yet-unhandled pointer expressions, creating an empty origin for them. - if (It == DeclToOriginID.end()) - return getOrCreate(D); - - return It->second; -} +OriginTree *OriginManager::getOrCreateTree(const Expr *E, ASTContext &Ctx) { + // if (E->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNotNull)) + // return nullptr; + if (auto *ParenIgnored = E->IgnoreParens(); ParenIgnored != E) + return getOrCreateTree(ParenIgnored, Ctx); + // Rvalues of non-pointer type do not have origins. + if (!E->isGLValue() && !isPointerType(E->getType())) + return nullptr; -OriginID OriginManager::getOrCreate(const Expr &E) { - auto It = ExprToOriginID.find(&E); - if (It != ExprToOriginID.end()) + auto It = ExprToTreeMap.find(E); + if (It != ExprToTreeMap.end()) return It->second; - OriginID NewID = getNextOriginID(); - addOrigin(NewID, E); - ExprToOriginID[&E] = NewID; - return NewID; + QualType Type = E->getType(); + + // TODO: Doc. + // Why does reference type does not + if (auto *DRE = dyn_cast<DeclRefExpr>(E)) { + OriginTree *Root = nullptr; + if (DRE->getDecl()->getType()->isReferenceType()) { + Root = getOrCreateTree(DRE->getDecl()); + } else { + Root = createNode(createOrigin(DRE)); + Root->Pointee = getOrCreateTree(DRE->getDecl()); + } + // Create outer origin. Use inner tree from the underlying decl. + return ExprToTreeMap[E] = Root; + } + // If E is an lvalue , it refers to storage. We model this storage as the + // first level of origin tree, as if it were a reference, because l-values are + // addressable. + if (E->isGLValue() && !Type->isReferenceType()) { + Type = Ctx.getLValueReferenceType(Type); + } + ExprToTreeMap[E] = buildTreeForType(Type, E); + return ExprToTreeMap[E]; } const Origin &OriginManager::getOrigin(OriginID ID) const { @@ -78,14 +123,4 @@ const Origin &OriginManager::getOrigin(OriginID ID) const { return AllOrigins[ID.Value]; } -OriginID OriginManager::getOrCreate(const ValueDecl &D) { - auto It = DeclToOriginID.find(&D); - if (It != DeclToOriginID.end()) - return It->second; - OriginID NewID = getNextOriginID(); - addOrigin(NewID, D); - DeclToOriginID[&D] = NewID; - return NewID; -} - } // namespace clang::lifetimes::internal diff --git a/clang/test/Sema/warn-lifetime-safety.cpp b/clang/test/Sema/warn-lifetime-safety.cpp index b9368db550805..d8b166336ea0f 100644 --- a/clang/test/Sema/warn-lifetime-safety.cpp +++ b/clang/test/Sema/warn-lifetime-safety.cpp @@ -1,9 +1,13 @@ // RUN: %clang_cc1 -fsyntax-only -fexperimental-lifetime-safety -Wexperimental-lifetime-safety -verify %s -struct MyObj { +struct View; + +struct [[gsl::Owner]] MyObj { int id; ~MyObj() {} // Non-trivial destructor MyObj operator+(MyObj); + + View getView() const [[clang::lifetimebound]]; }; struct [[gsl::Pointer()]] View { @@ -220,6 +224,16 @@ void potential_for_loop_use_after_loop_body(MyObj safe) { (void)*p; // expected-note {{later used here}} } +void safe_for_loop_gsl() { + MyObj safe; + View v = safe; + for (int i = 0; i < 1; ++i) { + MyObj s; + v = s; + v.use(); + } +} + void potential_for_loop_gsl() { MyObj safe; View v = safe; @@ -444,13 +458,6 @@ MyObj* Identity(MyObj* v [[clang::lifetimebound]]); View Choose(bool cond, View a [[clang::lifetimebound]], View b [[clang::lifetimebound]]); MyObj* GetPointer(const MyObj& obj [[clang::lifetimebound]]); -struct [[gsl::Pointer()]] LifetimeBoundView { - LifetimeBoundView(); - LifetimeBoundView(const MyObj& obj [[clang::lifetimebound]]); - LifetimeBoundView pass() [[clang::lifetimebound]] { return *this; } - operator View() const [[clang::lifetimebound]]; -}; - void lifetimebound_simple_function() { View v; { @@ -497,25 +504,34 @@ void lifetimebound_mixed_args() { v.use(); // expected-note {{later used here}} } +struct LifetimeBoundMember { + LifetimeBoundMember(); + View get() const [[clang::lifetimebound]]; + operator View() const [[clang::lifetimebound]]; +}; + void lifetimebound_member_function() { - LifetimeBoundView lbv, lbv2; + View v; { MyObj obj; - lbv = obj; // expected-warning {{object whose reference is captured does not live long enough}} - lbv2 = lbv.pass(); - } // expected-note {{destroyed here}} - View v = lbv2; // expected-note {{later used here}} - v.use(); + v = obj.getView(); // expected-warning {{object whose reference is captured does not live long enough}} + } // expected-note {{destroyed here}} + v.use(); // expected-note {{later used here}} } +struct LifetimeBoundConversionView { + LifetimeBoundConversionView(); + ~LifetimeBoundConversionView(); + operator View() const [[clang::lifetimebound]]; +}; + void lifetimebound_conversion_operator() { View v; { - MyObj obj; - LifetimeBoundView lbv = obj; // expected-warning {{object whose reference is captured does not live long enough}} - v = lbv; // Conversion operator is lifetimebound - } // expected-note {{destroyed here}} - v.use(); // expected-note {{later used here}} + LifetimeBoundConversionView obj; + v = obj; // expected-warning {{object whose reference is captured does not live long enough}} + } // expected-note {{destroyed here}} + v.use(); // expected-note {{later used here}} } void lifetimebound_chained_calls() { @@ -556,18 +572,18 @@ void lifetimebound_partial_safety(bool cond) { v.use(); // expected-note {{later used here}} } -// FIXME: Creating reference from lifetimebound call doesn't propagate loans. +// TODO:Extensively test references types. const MyObj& GetObject(View v [[clang::lifetimebound]]); void lifetimebound_return_reference() { View v; const MyObj* ptr; { MyObj obj; - View temp_v = obj; + View temp_v = obj; // expected-warning {{object whose reference is captured does not live long enough}} const MyObj& ref = GetObject(temp_v); ptr = &ref; - } - (void)*ptr; + } // expected-note {{destroyed here}} + (void)*ptr; // expected-note {{later used here}} } // FIXME: No warning for non gsl::Pointer types. Origin tracking is only supported for pointer types. @@ -575,6 +591,7 @@ struct LifetimeBoundCtor { LifetimeBoundCtor(); LifetimeBoundCtor(const MyObj& obj [[clang::lifetimebound]]); }; + void lifetimebound_ctor() { LifetimeBoundCtor v; { @@ -686,3 +703,67 @@ void parentheses(bool cond) { } // expected-note 4 {{destroyed here}} (void)*p; // expected-note 4 {{later used here}} } + +namespace GH162834 { +template <class T> +struct StatusOr { + ~StatusOr() {} + const T& value() const& [[clang::lifetimebound]] { return data; } + + private: + T data; +}; + +StatusOr<View> getViewOr(); +StatusOr<MyObj> getStringOr(); +StatusOr<MyObj*> getPointerOr(); + +void foo() { + View view; + { + StatusOr<View> view_or = getViewOr(); + view = view_or.value(); + } + (void)view; +} + +void bar() { + MyObj* pointer; + { + StatusOr<MyObj*> pointer_or = getPointerOr(); + pointer = pointer_or.value(); + } + (void)*pointer; +} + +void foobar() { + View view; + { + StatusOr<MyObj> string_or = getStringOr(); + view = string_or. // expected-warning {{object whose reference is captured does not live long enough}} + value(); + } // expected-note {{destroyed here}} + (void)view; // expected-note {{later used here}} +} +} // namespace GH162834 + +namespace CppCoverage { + +int getInt(); + +void ReferenceParam(unsigned Value, unsigned &Ref) { + Value = getInt(); + Ref = getInt(); +} + +inline void normalize(int &exponent, int &mantissa) { + const int shift = 1; + exponent -= shift; + mantissa <<= shift; +} + +void add(int c, MyObj* node) { + MyObj* arr[10]; + arr[4] = node; +} +} // namespace CppCoverage diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index 601308c53f9a9..b63ddbb7367ac 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -101,8 +101,9 @@ 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. - return const_cast<OriginManager &>(Analysis.getFactManager().getOriginMgr()) - .get(*VD); + // return const_cast<OriginManager &>(Analysis.getFactManager().getOriginMgr()) + // .get(*VD); + return std::nullopt; } std::vector<LoanID> getLoansForVar(llvm::StringRef VarName) { _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
