clang 22.0.0git
LifetimeSafety.cpp
Go to the documentation of this file.
1//===- LifetimeSafety.cpp - C++ Lifetime Safety Analysis -*--------- C++-*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
9#include "clang/AST/Decl.h"
10#include "clang/AST/Expr.h"
12#include "clang/AST/Type.h"
15#include "clang/Analysis/CFG.h"
17#include "llvm/ADT/FoldingSet.h"
18#include "llvm/ADT/ImmutableMap.h"
19#include "llvm/ADT/ImmutableSet.h"
20#include "llvm/ADT/PointerUnion.h"
21#include "llvm/ADT/SmallBitVector.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/TimeProfiler.h"
25#include <cstdint>
26#include <memory>
27
28namespace clang::lifetimes {
29namespace internal {
30
31/// Represents the storage location being borrowed, e.g., a specific stack
32/// variable.
33/// TODO: Model access paths of other types, e.g., s.field, heap and globals.
34struct AccessPath {
36
38};
39
40/// Information about a single borrow, or "Loan". A loan is created when a
41/// reference or pointer is created.
42struct Loan {
43 /// TODO: Represent opaque loans.
44 /// TODO: Represent nullptr: loans to no path. Accessing it UB! Currently it
45 /// is represented as empty LoanSet
48 /// The expression that creates the loan, e.g., &x.
50
52 : ID(id), Path(path), IssueExpr(IssueExpr) {}
53};
54
55/// An Origin is a symbolic identifier that represents the set of possible
56/// loans a pointer-like object could hold at any given time.
57/// TODO: Enhance the origin model to handle complex types, pointer
58/// indirection and reborrowing. The plan is to move from a single origin per
59/// variable/expression to a "list of origins" governed by the Type.
60/// For example, the type 'int**' would have two origins.
61/// See discussion:
62/// https://github.com/llvm/llvm-project/pull/142313/commits/0cd187b01e61b200d92ca0b640789c1586075142#r2137644238
63struct Origin {
65 /// A pointer to the AST node that this origin represents. This union
66 /// distinguishes between origins from declarations (variables or parameters)
67 /// and origins from expressions.
68 llvm::PointerUnion<const clang::ValueDecl *, const clang::Expr *> Ptr;
69
71 Origin(OriginID ID, const clang::Expr *E) : ID(ID), Ptr(E) {}
72
73 const clang::ValueDecl *getDecl() const {
74 return Ptr.dyn_cast<const clang::ValueDecl *>();
75 }
76 const clang::Expr *getExpr() const {
77 return Ptr.dyn_cast<const clang::Expr *>();
78 }
79};
80
81/// Manages the creation, storage and retrieval of loans.
83public:
84 LoanManager() = default;
85
86 Loan &addLoan(AccessPath Path, const Expr *IssueExpr) {
87 AllLoans.emplace_back(getNextLoanID(), Path, IssueExpr);
88 return AllLoans.back();
89 }
90
91 const Loan &getLoan(LoanID ID) const {
92 assert(ID.Value < AllLoans.size());
93 return AllLoans[ID.Value];
94 }
95 llvm::ArrayRef<Loan> getLoans() const { return AllLoans; }
96
97private:
98 LoanID getNextLoanID() { return NextLoanID++; }
99
100 LoanID NextLoanID{0};
101 /// TODO(opt): Profile and evaluate the usefullness of small buffer
102 /// optimisation.
104};
105
106/// Manages the creation, storage, and retrieval of origins for pointer-like
107/// variables and expressions.
109public:
110 OriginManager() = default;
111
113 AllOrigins.emplace_back(ID, &D);
114 return AllOrigins.back();
115 }
117 AllOrigins.emplace_back(ID, &E);
118 return AllOrigins.back();
119 }
120
121 OriginID get(const Expr &E) {
122 // Origin of DeclRefExpr is that of the declaration it refers to.
123 if (const auto *DRE = dyn_cast<DeclRefExpr>(&E))
124 return get(*DRE->getDecl());
125 auto It = ExprToOriginID.find(&E);
126 // TODO: This should be an assert(It != ExprToOriginID.end()). The current
127 // implementation falls back to getOrCreate to avoid crashing on
128 // yet-unhandled pointer expressions, creating an empty origin for them.
129 if (It == ExprToOriginID.end())
130 return getOrCreate(E);
131
132 return It->second;
133 }
134
136 auto It = DeclToOriginID.find(&D);
137 // TODO: This should be an assert(It != DeclToOriginID.end()). The current
138 // implementation falls back to getOrCreate to avoid crashing on
139 // yet-unhandled pointer expressions, creating an empty origin for them.
140 if (It == DeclToOriginID.end())
141 return getOrCreate(D);
142
143 return It->second;
144 }
145
147 auto It = ExprToOriginID.find(&E);
148 if (It != ExprToOriginID.end())
149 return It->second;
150
151 if (const auto *DRE = dyn_cast<DeclRefExpr>(&E)) {
152 // Origin of DeclRefExpr is that of the declaration it refers to.
153 return getOrCreate(*DRE->getDecl());
154 }
155 OriginID NewID = getNextOriginID();
156 addOrigin(NewID, E);
157 ExprToOriginID[&E] = NewID;
158 return NewID;
159 }
160
161 const Origin &getOrigin(OriginID ID) const {
162 assert(ID.Value < AllOrigins.size());
163 return AllOrigins[ID.Value];
164 }
165
166 llvm::ArrayRef<Origin> getOrigins() const { return AllOrigins; }
167
169 auto It = DeclToOriginID.find(&D);
170 if (It != DeclToOriginID.end())
171 return It->second;
172 OriginID NewID = getNextOriginID();
173 addOrigin(NewID, D);
174 DeclToOriginID[&D] = NewID;
175 return NewID;
176 }
177
178 void dump(OriginID OID, llvm::raw_ostream &OS) const {
179 OS << OID << " (";
180 Origin O = getOrigin(OID);
181 if (const ValueDecl *VD = O.getDecl())
182 OS << "Decl: " << VD->getNameAsString();
183 else if (const Expr *E = O.getExpr())
184 OS << "Expr: " << E->getStmtClassName();
185 else
186 OS << "Unknown";
187 OS << ")";
188 }
189
190private:
191 OriginID getNextOriginID() { return NextOriginID++; }
192
193 OriginID NextOriginID{0};
194 /// TODO(opt): Profile and evaluate the usefullness of small buffer
195 /// optimisation.
196 llvm::SmallVector<Origin> AllOrigins;
197 llvm::DenseMap<const clang::ValueDecl *, OriginID> DeclToOriginID;
198 llvm::DenseMap<const clang::Expr *, OriginID> ExprToOriginID;
199};
200
201/// An abstract base class for a single, atomic lifetime-relevant event.
202class Fact {
203
204public:
205 enum class Kind : uint8_t {
206 /// A new loan is issued from a borrow expression (e.g., &x).
207 Issue,
208 /// A loan expires as its underlying storage is freed (e.g., variable goes
209 /// out of scope).
210 Expire,
211 /// An origin is propagated from a source to a destination (e.g., p = q).
213 /// An origin escapes the function by flowing into the return value.
215 /// An origin is used (eg. dereferencing a pointer).
216 Use,
217 /// A marker for a specific point in the code, for testing.
218 TestPoint,
219 };
220
221private:
222 Kind K;
223
224protected:
225 Fact(Kind K) : K(K) {}
226
227public:
228 virtual ~Fact() = default;
229 Kind getKind() const { return K; }
230
231 template <typename T> const T *getAs() const {
232 if (T::classof(this))
233 return static_cast<const T *>(this);
234 return nullptr;
235 }
236
237 virtual void dump(llvm::raw_ostream &OS, const OriginManager &) const {
238 OS << "Fact (Kind: " << static_cast<int>(K) << ")\n";
239 }
240};
241
242class IssueFact : public Fact {
243 LoanID LID;
244 OriginID OID;
245
246public:
247 static bool classof(const Fact *F) { return F->getKind() == Kind::Issue; }
248
249 IssueFact(LoanID LID, OriginID OID) : Fact(Kind::Issue), LID(LID), OID(OID) {}
250 LoanID getLoanID() const { return LID; }
251 OriginID getOriginID() const { return OID; }
252 void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override {
253 OS << "Issue (LoanID: " << getLoanID() << ", ToOrigin: ";
254 OM.dump(getOriginID(), OS);
255 OS << ")\n";
256 }
257};
258
259class ExpireFact : public Fact {
260 LoanID LID;
261 SourceLocation ExpiryLoc;
262
263public:
264 static bool classof(const Fact *F) { return F->getKind() == Kind::Expire; }
265
267 : Fact(Kind::Expire), LID(LID), ExpiryLoc(ExpiryLoc) {}
268
269 LoanID getLoanID() const { return LID; }
270 SourceLocation getExpiryLoc() const { return ExpiryLoc; }
271
272 void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override {
273 OS << "Expire (LoanID: " << getLoanID() << ")\n";
274 }
275};
276
277class AssignOriginFact : public Fact {
278 OriginID OIDDest;
279 OriginID OIDSrc;
280
281public:
282 static bool classof(const Fact *F) {
283 return F->getKind() == Kind::AssignOrigin;
284 }
285
287 : Fact(Kind::AssignOrigin), OIDDest(OIDDest), OIDSrc(OIDSrc) {}
288 OriginID getDestOriginID() const { return OIDDest; }
289 OriginID getSrcOriginID() const { return OIDSrc; }
290 void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override {
291 OS << "AssignOrigin (Dest: ";
292 OM.dump(getDestOriginID(), OS);
293 OS << ", Src: ";
294 OM.dump(getSrcOriginID(), OS);
295 OS << ")\n";
296 }
297};
298
299class ReturnOfOriginFact : public Fact {
300 OriginID OID;
301
302public:
303 static bool classof(const Fact *F) {
304 return F->getKind() == Kind::ReturnOfOrigin;
305 }
306
308 OriginID getReturnedOriginID() const { return OID; }
309 void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override {
310 OS << "ReturnOfOrigin (";
311 OM.dump(getReturnedOriginID(), OS);
312 OS << ")\n";
313 }
314};
315
316class UseFact : public Fact {
317 OriginID UsedOrigin;
318 const Expr *UseExpr;
319
320public:
321 static bool classof(const Fact *F) { return F->getKind() == Kind::Use; }
322
323 UseFact(OriginID UsedOrigin, const Expr *UseExpr)
324 : Fact(Kind::Use), UsedOrigin(UsedOrigin), UseExpr(UseExpr) {}
325
326 OriginID getUsedOrigin() const { return UsedOrigin; }
327 const Expr *getUseExpr() const { return UseExpr; }
328
329 void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override {
330 OS << "Use (";
331 OM.dump(getUsedOrigin(), OS);
332 OS << ")\n";
333 }
334};
335
336/// A dummy-fact used to mark a specific point in the code for testing.
337/// It is generated by recognizing a `void("__lifetime_test_point_...")` cast.
338class TestPointFact : public Fact {
339 StringRef Annotation;
340
341public:
342 static bool classof(const Fact *F) { return F->getKind() == Kind::TestPoint; }
343
344 explicit TestPointFact(StringRef Annotation)
345 : Fact(Kind::TestPoint), Annotation(Annotation) {}
346
347 StringRef getAnnotation() const { return Annotation; }
348
349 void dump(llvm::raw_ostream &OS, const OriginManager &) const override {
350 OS << "TestPoint (Annotation: \"" << getAnnotation() << "\")\n";
351 }
352};
353
355public:
357 auto It = BlockToFactsMap.find(B);
358 if (It != BlockToFactsMap.end())
359 return It->second;
360 return {};
361 }
362
364 if (!NewFacts.empty())
365 BlockToFactsMap[B].assign(NewFacts.begin(), NewFacts.end());
366 }
367
368 template <typename FactType, typename... Args>
369 FactType *createFact(Args &&...args) {
370 void *Mem = FactAllocator.Allocate<FactType>();
371 return new (Mem) FactType(std::forward<Args>(args)...);
372 }
373
374 void dump(const CFG &Cfg, AnalysisDeclContext &AC) const {
375 llvm::dbgs() << "==========================================\n";
376 llvm::dbgs() << " Lifetime Analysis Facts:\n";
377 llvm::dbgs() << "==========================================\n";
378 if (const Decl *D = AC.getDecl())
379 if (const auto *ND = dyn_cast<NamedDecl>(D))
380 llvm::dbgs() << "Function: " << ND->getQualifiedNameAsString() << "\n";
381 // Print blocks in the order as they appear in code for a stable ordering.
382 for (const CFGBlock *B : *AC.getAnalysis<PostOrderCFGView>()) {
383 llvm::dbgs() << " Block B" << B->getBlockID() << ":\n";
384 auto It = BlockToFactsMap.find(B);
385 if (It != BlockToFactsMap.end()) {
386 for (const Fact *F : It->second) {
387 llvm::dbgs() << " ";
388 F->dump(llvm::dbgs(), OriginMgr);
389 }
390 }
391 llvm::dbgs() << " End of Block\n";
392 }
393 }
394
395 LoanManager &getLoanMgr() { return LoanMgr; }
396 OriginManager &getOriginMgr() { return OriginMgr; }
397
398private:
399 LoanManager LoanMgr;
400 OriginManager OriginMgr;
401 llvm::DenseMap<const clang::CFGBlock *, llvm::SmallVector<const Fact *>>
402 BlockToFactsMap;
403 llvm::BumpPtrAllocator FactAllocator;
404};
405
406class FactGenerator : public ConstStmtVisitor<FactGenerator> {
408
409public:
411 : FactMgr(FactMgr), AC(AC) {}
412
413 void run() {
414 llvm::TimeTraceScope TimeProfile("FactGenerator");
415 // Iterate through the CFG blocks in reverse post-order to ensure that
416 // initializations and destructions are processed in the correct sequence.
417 for (const CFGBlock *Block : *AC.getAnalysis<PostOrderCFGView>()) {
418 CurrentBlockFacts.clear();
419 for (unsigned I = 0; I < Block->size(); ++I) {
420 const CFGElement &Element = Block->Elements[I];
421 if (std::optional<CFGStmt> CS = Element.getAs<CFGStmt>())
422 Visit(CS->getStmt());
423 else if (std::optional<CFGAutomaticObjDtor> DtorOpt =
424 Element.getAs<CFGAutomaticObjDtor>())
425 handleDestructor(*DtorOpt);
426 }
427 FactMgr.addBlockFacts(Block, CurrentBlockFacts);
428 }
429 }
430
431 void VisitDeclStmt(const DeclStmt *DS) {
432 for (const Decl *D : DS->decls())
433 if (const auto *VD = dyn_cast<VarDecl>(D))
434 if (hasOrigin(VD->getType()))
435 if (const Expr *InitExpr = VD->getInit())
436 addAssignOriginFact(*VD, *InitExpr);
437 }
438
440 /// TODO: Handle nullptr expr as a special 'null' loan. Uninitialized
441 /// pointers can use the same type of loan.
442 FactMgr.getOriginMgr().getOrCreate(*N);
443 }
444
446 if (!hasOrigin(ICE->getType()))
447 return;
448 Visit(ICE->getSubExpr());
449 // An ImplicitCastExpr node itself gets an origin, which flows from the
450 // origin of its sub-expression (after stripping its own parens/casts).
451 // TODO: Consider if this is actually useful in practice. Alternatively, we
452 // could directly use the sub-expression's OriginID instead of creating a
453 // new one.
454 addAssignOriginFact(*ICE, *ICE->getSubExpr());
455 }
456
458 if (UO->getOpcode() == UO_AddrOf) {
459 const Expr *SubExpr = UO->getSubExpr();
460 if (const auto *DRE = dyn_cast<DeclRefExpr>(SubExpr)) {
461 if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
462 // Check if it's a local variable.
463 if (VD->hasLocalStorage()) {
464 OriginID OID = FactMgr.getOriginMgr().getOrCreate(*UO);
465 AccessPath AddrOfLocalVarPath(VD);
466 const Loan &L =
467 FactMgr.getLoanMgr().addLoan(AddrOfLocalVarPath, UO);
468 CurrentBlockFacts.push_back(
469 FactMgr.createFact<IssueFact>(L.ID, OID));
470 }
471 }
472 }
473 } else if (UO->getOpcode() == UO_Deref) {
474 // This is a pointer use, like '*p'.
475 OriginID OID = FactMgr.getOriginMgr().get(*UO->getSubExpr());
476 CurrentBlockFacts.push_back(FactMgr.createFact<UseFact>(OID, UO));
477 }
478 }
479
480 void VisitReturnStmt(const ReturnStmt *RS) {
481 if (const Expr *RetExpr = RS->getRetValue()) {
482 if (hasOrigin(RetExpr->getType())) {
483 OriginID OID = FactMgr.getOriginMgr().getOrCreate(*RetExpr);
484 CurrentBlockFacts.push_back(
485 FactMgr.createFact<ReturnOfOriginFact>(OID));
486 }
487 }
488 }
489
491 if (BO->isAssignmentOp()) {
492 const Expr *LHSExpr = BO->getLHS();
493 const Expr *RHSExpr = BO->getRHS();
494
495 // We are interested in assignments like `ptr1 = ptr2` or `ptr = &var`
496 // LHS must be a pointer/reference type that can be an origin.
497 // RHS must also represent an origin (either another pointer/ref or an
498 // address-of).
499 if (const auto *DRE_LHS = dyn_cast<DeclRefExpr>(LHSExpr))
500 if (const auto *VD_LHS =
501 dyn_cast<ValueDecl>(DRE_LHS->getDecl()->getCanonicalDecl());
502 VD_LHS && hasOrigin(VD_LHS->getType()))
503 addAssignOriginFact(*VD_LHS, *RHSExpr);
504 }
505 }
506
508 // Check if this is a test point marker. If so, we are done with this
509 // expression.
510 if (VisitTestPoint(FCE))
511 return;
512 // Visit as normal otherwise.
513 Base::VisitCXXFunctionalCastExpr(FCE);
514 }
515
516private:
517 // Check if a type has an origin.
518 bool hasOrigin(QualType QT) { return QT->isPointerOrReferenceType(); }
519
520 template <typename Destination, typename Source>
521 void addAssignOriginFact(const Destination &D, const Source &S) {
522 OriginID DestOID = FactMgr.getOriginMgr().getOrCreate(D);
523 OriginID SrcOID = FactMgr.getOriginMgr().get(S);
524 CurrentBlockFacts.push_back(
525 FactMgr.createFact<AssignOriginFact>(DestOID, SrcOID));
526 }
527
528 void handleDestructor(const CFGAutomaticObjDtor &DtorOpt) {
529 /// TODO: Also handle trivial destructors (e.g., for `int`
530 /// variables) which will never have a CFGAutomaticObjDtor node.
531 /// TODO: Handle loans to temporaries.
532 /// TODO: Consider using clang::CFG::BuildOptions::AddLifetime to reuse the
533 /// lifetime ends.
534 const VarDecl *DestructedVD = DtorOpt.getVarDecl();
535 if (!DestructedVD)
536 return;
537 // Iterate through all loans to see if any expire.
538 /// TODO(opt): Do better than a linear search to find loans associated with
539 /// 'DestructedVD'.
540 for (const Loan &L : FactMgr.getLoanMgr().getLoans()) {
541 const AccessPath &LoanPath = L.Path;
542 // Check if the loan is for a stack variable and if that variable
543 // is the one being destructed.
544 if (LoanPath.D == DestructedVD)
545 CurrentBlockFacts.push_back(FactMgr.createFact<ExpireFact>(
546 L.ID, DtorOpt.getTriggerStmt()->getEndLoc()));
547 }
548 }
549
550 /// Checks if the expression is a `void("__lifetime_test_point_...")` cast.
551 /// If so, creates a `TestPointFact` and returns true.
552 bool VisitTestPoint(const CXXFunctionalCastExpr *FCE) {
553 if (!FCE->getType()->isVoidType())
554 return false;
555
556 const auto *SubExpr = FCE->getSubExpr()->IgnoreParenImpCasts();
557 if (const auto *SL = dyn_cast<StringLiteral>(SubExpr)) {
558 llvm::StringRef LiteralValue = SL->getString();
559 const std::string Prefix = "__lifetime_test_point_";
560
561 if (LiteralValue.starts_with(Prefix)) {
562 StringRef Annotation = LiteralValue.drop_front(Prefix.length());
563 CurrentBlockFacts.push_back(
564 FactMgr.createFact<TestPointFact>(Annotation));
565 return true;
566 }
567 }
568 return false;
569 }
570
571 FactManager &FactMgr;
572 AnalysisDeclContext &AC;
573 llvm::SmallVector<Fact *> CurrentBlockFacts;
574};
575
576// ========================================================================= //
577// Generic Dataflow Analysis
578// ========================================================================= //
579
580enum class Direction { Forward, Backward };
581
582/// A `ProgramPoint` identifies a location in the CFG by pointing to a specific
583/// `Fact`. identified by a lifetime-related event (`Fact`).
584///
585/// A `ProgramPoint` has "after" semantics: it represents the location
586/// immediately after its corresponding `Fact`.
587using ProgramPoint = const Fact *;
588
589/// A generic, policy-based driver for dataflow analyses. It combines
590/// the dataflow runner and the transferer logic into a single class hierarchy.
591///
592/// The derived class is expected to provide:
593/// - A `Lattice` type.
594/// - `StringRef getAnalysisName() const`
595/// - `Lattice getInitialState();` The initial state of the analysis.
596/// - `Lattice join(Lattice, Lattice);` Merges states from multiple CFG paths.
597/// - `Lattice transfer(Lattice, const FactType&);` Defines how a single
598/// lifetime-relevant `Fact` transforms the lattice state. Only overloads
599/// for facts relevant to the analysis need to be implemented.
600///
601/// \tparam Derived The CRTP derived class that implements the specific
602/// analysis.
603/// \tparam LatticeType The dataflow lattice used by the analysis.
604/// \tparam Dir The direction of the analysis (Forward or Backward).
605/// TODO: Maybe use the dataflow framework! The framework might need changes
606/// to support the current comparison done at block-entry.
607template <typename Derived, typename LatticeType, Direction Dir>
609public:
610 using Lattice = LatticeType;
612
613private:
614 const CFG &Cfg;
616
617 /// The dataflow state before a basic block is processed.
618 llvm::DenseMap<const CFGBlock *, Lattice> InStates;
619 /// The dataflow state after a basic block is processed.
620 llvm::DenseMap<const CFGBlock *, Lattice> OutStates;
621 /// The dataflow state at a Program Point.
622 /// In a forward analysis, this is the state after the Fact at that point has
623 /// been applied, while in a backward analysis, it is the state before.
624 llvm::DenseMap<ProgramPoint, Lattice> PerPointStates;
625
626 static constexpr bool isForward() { return Dir == Direction::Forward; }
627
628protected:
630
632 FactManager &F)
633 : Cfg(C), AC(AC), AllFacts(F) {}
634
635public:
636 void run() {
637 Derived &D = static_cast<Derived &>(*this);
638 llvm::TimeTraceScope Time(D.getAnalysisName());
639
640 using Worklist =
641 std::conditional_t<Dir == Direction::Forward, ForwardDataflowWorklist,
643 Worklist W(Cfg, AC);
644
645 const CFGBlock *Start = isForward() ? &Cfg.getEntry() : &Cfg.getExit();
646 InStates[Start] = D.getInitialState();
647 W.enqueueBlock(Start);
648
649 llvm::SmallBitVector Visited(Cfg.getNumBlockIDs() + 1);
650
651 while (const CFGBlock *B = W.dequeue()) {
652 Lattice StateIn = getInState(B);
653 Lattice StateOut = transferBlock(B, StateIn);
654 OutStates[B] = StateOut;
655 Visited.set(B->getBlockID());
656 for (const CFGBlock *AdjacentB : isForward() ? B->succs() : B->preds()) {
657 if (!AdjacentB)
658 continue;
659 Lattice OldInState = getInState(AdjacentB);
660 Lattice NewInState = D.join(OldInState, StateOut);
661 // Enqueue the adjacent block if its in-state has changed or if we have
662 // never visited it.
663 if (!Visited.test(AdjacentB->getBlockID()) ||
664 NewInState != OldInState) {
665 InStates[AdjacentB] = NewInState;
666 W.enqueueBlock(AdjacentB);
667 }
668 }
669 }
670 }
671
672protected:
673 Lattice getState(ProgramPoint P) const { return PerPointStates.lookup(P); }
674
675 Lattice getInState(const CFGBlock *B) const { return InStates.lookup(B); }
676
677 Lattice getOutState(const CFGBlock *B) const { return OutStates.lookup(B); }
678
679 void dump() const {
680 const Derived *D = static_cast<const Derived *>(this);
681 llvm::dbgs() << "==========================================\n";
682 llvm::dbgs() << D->getAnalysisName() << " results:\n";
683 llvm::dbgs() << "==========================================\n";
684 const CFGBlock &B = isForward() ? Cfg.getExit() : Cfg.getEntry();
685 getOutState(&B).dump(llvm::dbgs());
686 }
687
688private:
689 /// Computes the state at one end of a block by applying all its facts
690 /// sequentially to a given state from the other end.
691 Lattice transferBlock(const CFGBlock *Block, Lattice State) {
692 auto Facts = AllFacts.getFacts(Block);
693 if constexpr (isForward()) {
694 for (const Fact *F : Facts) {
695 State = transferFact(State, F);
696 PerPointStates[F] = State;
697 }
698 } else {
699 for (const Fact *F : llvm::reverse(Facts)) {
700 // In backward analysis, capture the state before applying the fact.
701 PerPointStates[F] = State;
702 State = transferFact(State, F);
703 }
704 }
705 return State;
706 }
707
708 Lattice transferFact(Lattice In, const Fact *F) {
709 assert(F);
710 Derived *D = static_cast<Derived *>(this);
711 switch (F->getKind()) {
713 return D->transfer(In, *F->getAs<IssueFact>());
715 return D->transfer(In, *F->getAs<ExpireFact>());
717 return D->transfer(In, *F->getAs<AssignOriginFact>());
719 return D->transfer(In, *F->getAs<ReturnOfOriginFact>());
720 case Fact::Kind::Use:
721 return D->transfer(In, *F->getAs<UseFact>());
723 return D->transfer(In, *F->getAs<TestPointFact>());
724 }
725 llvm_unreachable("Unknown fact kind");
726 }
727
728public:
729 Lattice transfer(Lattice In, const IssueFact &) { return In; }
730 Lattice transfer(Lattice In, const ExpireFact &) { return In; }
731 Lattice transfer(Lattice In, const AssignOriginFact &) { return In; }
732 Lattice transfer(Lattice In, const ReturnOfOriginFact &) { return In; }
733 Lattice transfer(Lattice In, const UseFact &) { return In; }
734 Lattice transfer(Lattice In, const TestPointFact &) { return In; }
735};
736
737namespace utils {
738
739/// Computes the union of two ImmutableSets.
740template <typename T>
741static llvm::ImmutableSet<T> join(llvm::ImmutableSet<T> A,
742 llvm::ImmutableSet<T> B,
743 typename llvm::ImmutableSet<T>::Factory &F) {
744 if (A.getHeight() < B.getHeight())
745 std::swap(A, B);
746 for (const T &E : B)
747 A = F.add(A, E);
748 return A;
749}
750
751/// Checks if set A is a subset of set B.
752template <typename T>
753static bool isSubsetOf(const llvm::ImmutableSet<T> &A,
754 const llvm::ImmutableSet<T> &B) {
755 // Empty set is a subset of all sets.
756 if (A.isEmpty())
757 return true;
758
759 for (const T &Elem : A)
760 if (!B.contains(Elem))
761 return false;
762 return true;
763}
764
765/// Computes the key-wise union of two ImmutableMaps.
766// TODO(opt): This key-wise join is a performance bottleneck. A more
767// efficient merge could be implemented using a Patricia Trie or HAMT
768// instead of the current AVL-tree-based ImmutableMap.
769template <typename K, typename V, typename Joiner>
770static llvm::ImmutableMap<K, V>
771join(llvm::ImmutableMap<K, V> A, llvm::ImmutableMap<K, V> B,
772 typename llvm::ImmutableMap<K, V>::Factory &F, Joiner JoinValues) {
773 if (A.getHeight() < B.getHeight())
774 std::swap(A, B);
775
776 // For each element in B, join it with the corresponding element in A
777 // (or with an empty value if it doesn't exist in A).
778 for (const auto &Entry : B) {
779 const K &Key = Entry.first;
780 const V &ValB = Entry.second;
781 if (const V *ValA = A.lookup(Key))
782 A = F.add(A, Key, JoinValues(*ValA, ValB));
783 else
784 A = F.add(A, Key, ValB);
785 }
786 return A;
787}
788} // namespace utils
789
790// ========================================================================= //
791// Loan Propagation Analysis
792// ========================================================================= //
793
794using OriginLoanMap = llvm::ImmutableMap<OriginID, LoanSet>;
795using ExpiredLoanMap = llvm::ImmutableMap<LoanID, const ExpireFact *>;
796
797/// An object to hold the factories for immutable collections, ensuring
798/// that all created states share the same underlying memory management.
800 OriginLoanMap::Factory OriginMapFactory;
801 LoanSet::Factory LoanSetFactory;
802 ExpiredLoanMap::Factory ExpiredLoanMapFactory;
803};
804
805/// Represents the dataflow lattice for loan propagation.
806///
807/// This lattice tracks which loans each origin may hold at a given program
808/// point.The lattice has a finite height: An origin's loan set is bounded by
809/// the total number of loans in the function.
810/// TODO(opt): To reduce the lattice size, propagate origins of declarations,
811/// not expressions, because expressions are not visible across blocks.
813 /// The map from an origin to the set of loans it contains.
815
818
820 return Origins == Other.Origins;
821 }
823 return !(*this == Other);
824 }
825
826 void dump(llvm::raw_ostream &OS) const {
827 OS << "LoanPropagationLattice State:\n";
828 if (Origins.isEmpty())
829 OS << " <empty>\n";
830 for (const auto &Entry : Origins) {
831 if (Entry.second.isEmpty())
832 OS << " Origin " << Entry.first << " contains no loans\n";
833 for (const LoanID &LID : Entry.second)
834 OS << " Origin " << Entry.first << " contains Loan " << LID << "\n";
835 }
836 }
837};
838
839/// The analysis that tracks which loans belong to which origins.
841 : public DataflowAnalysis<LoanPropagationAnalysis, LoanPropagationLattice,
842 Direction::Forward> {
843 OriginLoanMap::Factory &OriginLoanMapFactory;
844 LoanSet::Factory &LoanSetFactory;
845
846public:
848 LifetimeFactory &LFactory)
849 : DataflowAnalysis(C, AC, F),
850 OriginLoanMapFactory(LFactory.OriginMapFactory),
851 LoanSetFactory(LFactory.LoanSetFactory) {}
852
853 using Base::transfer;
854
855 StringRef getAnalysisName() const { return "LoanPropagation"; }
856
858
859 /// Merges two lattices by taking the union of loans for each origin.
860 // TODO(opt): Keep the state small by removing origins which become dead.
862 OriginLoanMap JoinedOrigins =
863 utils::join(A.Origins, B.Origins, OriginLoanMapFactory,
864 [&](LoanSet S1, LoanSet S2) {
865 return utils::join(S1, S2, LoanSetFactory);
866 });
867 return Lattice(JoinedOrigins);
868 }
869
870 /// A new loan is issued to the origin. Old loans are erased.
872 OriginID OID = F.getOriginID();
873 LoanID LID = F.getLoanID();
874 return LoanPropagationLattice(OriginLoanMapFactory.add(
875 In.Origins, OID,
876 LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID)));
877 }
878
879 /// The destination origin's loan set is replaced by the source's.
880 /// This implicitly "resets" the old loans of the destination.
882 OriginID DestOID = F.getDestOriginID();
883 OriginID SrcOID = F.getSrcOriginID();
884 LoanSet SrcLoans = getLoans(In, SrcOID);
886 OriginLoanMapFactory.add(In.Origins, DestOID, SrcLoans));
887 }
888
890 return getLoans(getState(P), OID);
891 }
892
893private:
895 if (auto *Loans = L.Origins.lookup(OID))
896 return *Loans;
897 return LoanSetFactory.getEmptySet();
898 }
899};
900
901// ========================================================================= //
902// Expired Loans Analysis
903// ========================================================================= //
904
905/// The dataflow lattice for tracking the set of expired loans.
907 /// Map from an expired `LoanID` to the `ExpireFact` that made it expire.
909
910 ExpiredLattice() : Expired(nullptr) {};
912
913 bool operator==(const ExpiredLattice &Other) const {
914 return Expired == Other.Expired;
915 }
916 bool operator!=(const ExpiredLattice &Other) const {
917 return !(*this == Other);
918 }
919
920 void dump(llvm::raw_ostream &OS) const {
921 OS << "ExpiredLattice State:\n";
922 if (Expired.isEmpty())
923 OS << " <empty>\n";
924 for (const auto &[ID, _] : Expired)
925 OS << " Loan " << ID << " is expired\n";
926 }
927};
928
929/// The analysis that tracks which loans have expired.
931 : public DataflowAnalysis<ExpiredLoansAnalysis, ExpiredLattice,
932 Direction::Forward> {
933
934 ExpiredLoanMap::Factory &Factory;
935
936public:
938 LifetimeFactory &Factory)
939 : DataflowAnalysis(C, AC, F), Factory(Factory.ExpiredLoanMapFactory) {}
940
941 using Base::transfer;
942
943 StringRef getAnalysisName() const { return "ExpiredLoans"; }
944
945 Lattice getInitialState() { return Lattice(Factory.getEmptyMap()); }
946
947 /// Merges two lattices by taking the union of the two expired loans.
949 return Lattice(
950 utils::join(L1.Expired, L2.Expired, Factory,
951 // Take the last expiry fact to make this hermetic.
952 [](const ExpireFact *F1, const ExpireFact *F2) {
953 return F1->getExpiryLoc() > F2->getExpiryLoc() ? F1 : F2;
954 }));
955 }
956
958 return Lattice(Factory.add(In.Expired, F.getLoanID(), &F));
959 }
960
961 // Removes the loan from the set of expired loans.
962 //
963 // When a loan is re-issued (e.g., in a loop), it is no longer considered
964 // expired. A loan can be in the expired set at the point of issue due to
965 // the dataflow state from a previous loop iteration being propagated along
966 // a backedge in the CFG.
967 //
968 // Note: This has a subtle false-negative though where a loan from previous
969 // iteration is not overwritten by a reissue. This needs careful tracking
970 // of loans "across iterations" which can be considered for future
971 // enhancements.
972 //
973 // void foo(int safe) {
974 // int* p = &safe;
975 // int* q = &safe;
976 // while (condition()) {
977 // int x = 1;
978 // p = &x; // A loan to 'x' is issued to 'p' in every iteration.
979 // if (condition()) {
980 // q = p;
981 // }
982 // (void)*p; // OK — 'p' points to 'x' from new iteration.
983 // (void)*q; // UaF - 'q' still points to 'x' from previous iteration
984 // // which is now destroyed.
985 // }
986 // }
988 return Lattice(Factory.remove(In.Expired, F.getLoanID()));
989 }
990
992};
993
994// ========================================================================= //
995// Lifetime checker and Error reporter
996// ========================================================================= //
997
998/// Struct to store the complete context for a potential lifetime violation.
1000 SourceLocation ExpiryLoc; // Where the loan expired.
1001 const Expr *UseExpr; // Where the origin holding this loan was used.
1003};
1004
1006private:
1007 llvm::DenseMap<LoanID, PendingWarning> FinalWarningsMap;
1008 LoanPropagationAnalysis &LoanPropagation;
1009 ExpiredLoansAnalysis &ExpiredLoans;
1010 FactManager &FactMgr;
1012 LifetimeSafetyReporter *Reporter;
1013
1014public:
1017 LifetimeSafetyReporter *Reporter)
1018 : LoanPropagation(LPA), ExpiredLoans(ELA), FactMgr(FM), ADC(ADC),
1019 Reporter(Reporter) {}
1020
1021 void run() {
1022 llvm::TimeTraceScope TimeProfile("LifetimeChecker");
1023 for (const CFGBlock *B : *ADC.getAnalysis<PostOrderCFGView>())
1024 for (const Fact *F : FactMgr.getFacts(B))
1025 if (const auto *UF = F->getAs<UseFact>())
1026 checkUse(UF);
1028 }
1029
1030 /// Checks for use-after-free errors for a given use of an Origin.
1031 ///
1032 /// This method is called for each 'UseFact' identified in the control flow
1033 /// graph. It determines if the loans held by the used origin have expired
1034 /// at the point of use.
1035 void checkUse(const UseFact *UF) {
1036
1037 OriginID O = UF->getUsedOrigin();
1038
1039 // Get the set of loans that the origin might hold at this program point.
1040 LoanSet HeldLoans = LoanPropagation.getLoans(O, UF);
1041
1042 // Get the set of all loans that have expired at this program point.
1043 ExpiredLoanMap AllExpiredLoans = ExpiredLoans.getExpiredLoans(UF);
1044
1045 // If the pointer holds no loans or no loans have expired, there's nothing
1046 // to check.
1047 if (HeldLoans.isEmpty() || AllExpiredLoans.isEmpty())
1048 return;
1049
1050 // Identify loans that which have expired but are held by the pointer. Using
1051 // them is a use-after-free.
1052 llvm::SmallVector<LoanID> DefaultedLoans;
1053 // A definite UaF error occurs if all loans the origin might hold have
1054 // expired.
1055 bool IsDefiniteError = true;
1056 for (LoanID L : HeldLoans) {
1057 if (AllExpiredLoans.contains(L))
1058 DefaultedLoans.push_back(L);
1059 else
1060 // If at least one loan is not expired, this use is not a definite UaF.
1061 IsDefiniteError = false;
1062 }
1063 // If there are no defaulted loans, the use is safe.
1064 if (DefaultedLoans.empty())
1065 return;
1066
1067 // Determine the confidence level of the error (definite or maybe).
1068 Confidence CurrentConfidence =
1069 IsDefiniteError ? Confidence::Definite : Confidence::Maybe;
1070
1071 // For each expired loan, create a pending warning.
1072 for (LoanID DefaultedLoan : DefaultedLoans) {
1073 // If we already have a warning for this loan with a higher or equal
1074 // confidence, skip this one.
1075 if (FinalWarningsMap.count(DefaultedLoan) &&
1076 CurrentConfidence <= FinalWarningsMap[DefaultedLoan].ConfidenceLevel)
1077 continue;
1078
1079 auto *EF = AllExpiredLoans.lookup(DefaultedLoan);
1080 assert(EF && "Could not find ExpireFact for an expired loan.");
1081
1082 FinalWarningsMap[DefaultedLoan] = {/*ExpiryLoc=*/(*EF)->getExpiryLoc(),
1083 /*UseExpr=*/UF->getUseExpr(),
1084 /*ConfidenceLevel=*/CurrentConfidence};
1085 }
1086 }
1087
1089 if (!Reporter)
1090 return;
1091 for (const auto &[LID, Warning] : FinalWarningsMap) {
1092 const Loan &L = FactMgr.getLoanMgr().getLoan(LID);
1093 const Expr *IssueExpr = L.IssueExpr;
1094 Reporter->reportUseAfterFree(IssueExpr, Warning.UseExpr,
1095 Warning.ExpiryLoc, Warning.ConfidenceLevel);
1096 }
1097 }
1098};
1099
1100// ========================================================================= //
1101// LifetimeSafetyAnalysis Class Implementation
1102// ========================================================================= //
1103
1104// We need this here for unique_ptr with forward declared class.
1106
1108 LifetimeSafetyReporter *Reporter)
1109 : AC(AC), Reporter(Reporter), Factory(std::make_unique<LifetimeFactory>()),
1110 FactMgr(std::make_unique<FactManager>()) {}
1111
1113 llvm::TimeTraceScope TimeProfile("LifetimeSafetyAnalysis");
1114
1115 const CFG &Cfg = *AC.getCFG();
1116 DEBUG_WITH_TYPE("PrintCFG", Cfg.dump(AC.getASTContext().getLangOpts(),
1117 /*ShowColors=*/true));
1118
1119 FactGenerator FactGen(*FactMgr, AC);
1120 FactGen.run();
1121 DEBUG_WITH_TYPE("LifetimeFacts", FactMgr->dump(Cfg, AC));
1122
1123 /// TODO(opt): Consider optimizing individual blocks before running the
1124 /// dataflow analysis.
1125 /// 1. Expression Origins: These are assigned once and read at most once,
1126 /// forming simple chains. These chains can be compressed into a single
1127 /// assignment.
1128 /// 2. Block-Local Loans: Origins of expressions are never read by other
1129 /// blocks; only Decls are visible. Therefore, loans in a block that
1130 /// never reach an Origin associated with a Decl can be safely dropped by
1131 /// the analysis.
1132 /// 3. Collapse ExpireFacts belonging to same source location into a single
1133 /// Fact.
1134 LoanPropagation =
1135 std::make_unique<LoanPropagationAnalysis>(Cfg, AC, *FactMgr, *Factory);
1136 LoanPropagation->run();
1137
1138 ExpiredLoans =
1139 std::make_unique<ExpiredLoansAnalysis>(Cfg, AC, *FactMgr, *Factory);
1140 ExpiredLoans->run();
1141
1142 LifetimeChecker Checker(*LoanPropagation, *ExpiredLoans, *FactMgr, AC,
1143 Reporter);
1144 Checker.run();
1145}
1146
1148 ProgramPoint PP) const {
1149 assert(LoanPropagation && "Analysis has not been run.");
1150 return LoanPropagation->getLoans(OID, PP);
1151}
1152
1153std::vector<LoanID>
1155 assert(ExpiredLoans && "ExpiredLoansAnalysis has not been run.");
1156 std::vector<LoanID> Result;
1157 for (const auto &pair : ExpiredLoans->getExpiredLoans(PP))
1158 Result.push_back(pair.first);
1159 return Result;
1160}
1161
1162std::optional<OriginID>
1164 assert(FactMgr && "FactManager not initialized");
1165 // This assumes the OriginManager's `get` can find an existing origin.
1166 // We might need a `find` method on OriginManager to avoid `getOrCreate` logic
1167 // in a const-query context if that becomes an issue.
1168 return FactMgr->getOriginMgr().get(*D);
1169}
1170
1171std::vector<LoanID>
1173 assert(FactMgr && "FactManager not initialized");
1174 std::vector<LoanID> Result;
1175 for (const Loan &L : FactMgr->getLoanMgr().getLoans())
1176 if (L.Path.D == VD)
1177 Result.push_back(L.ID);
1178 return Result;
1179}
1180
1181llvm::StringMap<ProgramPoint> LifetimeSafetyAnalysis::getTestPoints() const {
1182 assert(FactMgr && "FactManager not initialized");
1183 llvm::StringMap<ProgramPoint> AnnotationToPointMap;
1184 for (const CFGBlock *Block : *AC.getCFG()) {
1185 for (const Fact *F : FactMgr->getFacts(Block)) {
1186 if (const auto *TPF = F->getAs<TestPointFact>()) {
1187 StringRef PointName = TPF->getAnnotation();
1188 assert(AnnotationToPointMap.find(PointName) ==
1189 AnnotationToPointMap.end() &&
1190 "more than one test points with the same name");
1191 AnnotationToPointMap[PointName] = F;
1192 }
1193 }
1194 }
1195 return AnnotationToPointMap;
1196}
1197} // namespace internal
1198
1200 LifetimeSafetyReporter *Reporter) {
1202 Analysis.run();
1203}
1204} // namespace clang::lifetimes
#define V(N, I)
Definition: ASTContext.h:3597
StringRef P
This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...
const Decl * D
IndirectLocalPath & Path
Expr * E
llvm::DenseSet< const void * > Visited
Definition: HTMLLogger.cpp:145
TypeErasedDataflowAnalysis & Analysis
The analysis to be run.
C Language Family Type Representation.
AnalysisDeclContext contains the context data for the function, method or block under analysis.
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3974
Expr * getLHS() const
Definition: Expr.h:4024
Expr * getRHS() const
Definition: Expr.h:4026
static bool isAssignmentOp(Opcode Opc)
Definition: Expr.h:4110
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
Definition: CFG.h:418
const VarDecl * getVarDecl() const
Definition: CFG.h:423
const Stmt * getTriggerStmt() const
Definition: CFG.h:428
Represents a single basic block in a source-level CFG.
Definition: CFG.h:605
Represents a top-level expression in a basic block.
Definition: CFG.h:55
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1222
CFGBlock & getExit()
Definition: CFG.h:1332
CFGBlock & getEntry()
Definition: CFG.h:1330
void dump(const LangOptions &LO, bool ShowColors) const
dump - A simple pretty printer of a CFG that outputs to stderr.
Definition: CFG.cpp:6218
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:1409
Represents an explicit C++ type conversion that uses "functional" notation (C++ [expr....
Definition: ExprCXX.h:1833
The null pointer literal (C++11 [lex.nullptr])
Definition: ExprCXX.h:768
Expr * getSubExpr()
Definition: Expr.h:3662
ConstStmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:196
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
Definition: Stmt.h:1622
decl_range decls()
Definition: Stmt.h:1670
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
This represents one expression.
Definition: Expr.h:112
QualType getType() const
Definition: Expr.h:144
ImplicitCastExpr - Allows us to explicitly represent implicit type conversions, which have no direct ...
Definition: Expr.h:3789
A (possibly-)qualified type.
Definition: TypeBase.h:937
ReturnStmt - This represents a return, optionally of an expression: return; return 4;.
Definition: Stmt.h:3129
Expr * getRetValue()
Definition: Stmt.h:3156
Encodes a location in the source.
RetTy Visit(PTR(Stmt) S, ParamTys... P)
Definition: StmtVisitor.h:45
SourceLocation getEndLoc() const LLVM_READONLY
Definition: Stmt.cpp:358
bool isPointerOrReferenceType() const
Definition: TypeBase.h:8584
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Definition: Expr.h:2246
Expr * getSubExpr() const
Definition: Expr.h:2287
Opcode getOpcode() const
Definition: Expr.h:2282
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:711
Represents a variable declaration or definition.
Definition: Decl.h:925
virtual void reportUseAfterFree(const Expr *IssueExpr, const Expr *UseExpr, SourceLocation FreeLoc, Confidence Confidence)
AssignOriginFact(OriginID OIDDest, OriginID OIDSrc)
void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override
A generic, policy-based driver for dataflow analyses.
Lattice getInState(const CFGBlock *B) const
Lattice transfer(Lattice In, const TestPointFact &)
Lattice getOutState(const CFGBlock *B) const
DataflowAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F)
Lattice transfer(Lattice In, const ReturnOfOriginFact &)
Lattice transfer(Lattice In, const UseFact &)
Lattice transfer(Lattice In, const IssueFact &)
Lattice transfer(Lattice In, const AssignOriginFact &)
Lattice transfer(Lattice In, const ExpireFact &)
static bool classof(const Fact *F)
void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override
ExpireFact(LoanID LID, SourceLocation ExpiryLoc)
The analysis that tracks which loans have expired.
Lattice transfer(Lattice In, const ExpireFact &F)
ExpiredLoanMap getExpiredLoans(ProgramPoint P)
Lattice transfer(Lattice In, const IssueFact &F)
ExpiredLoansAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F, LifetimeFactory &Factory)
Lattice join(Lattice L1, Lattice L2)
Merges two lattices by taking the union of the two expired loans.
void VisitUnaryOperator(const UnaryOperator *UO)
void VisitCXXNullPtrLiteralExpr(const CXXNullPtrLiteralExpr *N)
void VisitImplicitCastExpr(const ImplicitCastExpr *ICE)
void VisitBinaryOperator(const BinaryOperator *BO)
FactGenerator(FactManager &FactMgr, AnalysisDeclContext &AC)
void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *FCE)
void VisitReturnStmt(const ReturnStmt *RS)
llvm::ArrayRef< const Fact * > getFacts(const CFGBlock *B) const
FactType * createFact(Args &&...args)
void dump(const CFG &Cfg, AnalysisDeclContext &AC) const
void addBlockFacts(const CFGBlock *B, llvm::ArrayRef< Fact * > NewFacts)
An abstract base class for a single, atomic lifetime-relevant event.
@ TestPoint
A marker for a specific point in the code, for testing.
@ Expire
A loan expires as its underlying storage is freed (e.g., variable goes out of scope).
@ ReturnOfOrigin
An origin escapes the function by flowing into the return value.
@ Issue
A new loan is issued from a borrow expression (e.g., &x).
@ Use
An origin is used (eg. dereferencing a pointer).
@ AssignOrigin
An origin is propagated from a source to a destination (e.g., p = q).
virtual void dump(llvm::raw_ostream &OS, const OriginManager &) const
void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override
IssueFact(LoanID LID, OriginID OID)
static bool classof(const Fact *F)
LifetimeChecker(LoanPropagationAnalysis &LPA, ExpiredLoansAnalysis &ELA, FactManager &FM, AnalysisDeclContext &ADC, LifetimeSafetyReporter *Reporter)
void checkUse(const UseFact *UF)
Checks for use-after-free errors for a given use of an Origin.
Running the lifetime safety analysis and querying its results.
LoanSet getLoansAtPoint(OriginID OID, ProgramPoint PP) const
Returns the set of loans an origin holds at a specific program point.
std::optional< OriginID > getOriginIDForDecl(const ValueDecl *D) const
Finds the OriginID for a given declaration.
std::vector< LoanID > getExpiredLoansAtPoint(ProgramPoint PP) const
Returns the set of loans that have expired at a specific program point.
std::vector< LoanID > getLoanIDForVar(const VarDecl *VD) const
Finds the LoanID's for the loan created with the specific variable as their Path.
llvm::StringMap< ProgramPoint > getTestPoints() const
Retrieves program points that were specially marked in the source code for testing.
LifetimeSafetyAnalysis(AnalysisDeclContext &AC, LifetimeSafetyReporter *Reporter)
Manages the creation, storage and retrieval of loans.
const Loan & getLoan(LoanID ID) const
Loan & addLoan(AccessPath Path, const Expr *IssueExpr)
llvm::ArrayRef< Loan > getLoans() const
The analysis that tracks which loans belong to which origins.
LoanPropagationAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F, LifetimeFactory &LFactory)
Lattice transfer(Lattice In, const IssueFact &F)
A new loan is issued to the origin. Old loans are erased.
Lattice transfer(Lattice In, const AssignOriginFact &F)
The destination origin's loan set is replaced by the source's.
Lattice join(Lattice A, Lattice B)
Merges two lattices by taking the union of loans for each origin.
LoanSet getLoans(OriginID OID, ProgramPoint P)
Manages the creation, storage, and retrieval of origins for pointer-like variables and expressions.
OriginID getOrCreate(const ValueDecl &D)
const Origin & getOrigin(OriginID ID) const
Origin & addOrigin(OriginID ID, const clang::Expr &E)
llvm::ArrayRef< Origin > getOrigins() const
void dump(OriginID OID, llvm::raw_ostream &OS) const
Origin & addOrigin(OriginID ID, const clang::ValueDecl &D)
void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override
A dummy-fact used to mark a specific point in the code for testing.
void dump(llvm::raw_ostream &OS, const OriginManager &) const override
static bool classof(const Fact *F)
UseFact(OriginID UsedOrigin, const Expr *UseExpr)
void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override
static bool isSubsetOf(const llvm::ImmutableSet< T > &A, const llvm::ImmutableSet< T > &B)
Checks if set A is a subset of set B.
static llvm::ImmutableSet< T > join(llvm::ImmutableSet< T > A, llvm::ImmutableSet< T > B, typename llvm::ImmutableSet< T >::Factory &F)
Computes the union of two ImmutableSets.
llvm::ImmutableSet< LoanID > LoanSet
ID< struct OriginTag > OriginID
ID< struct LoanTag > LoanID
llvm::ImmutableMap< LoanID, const ExpireFact * > ExpiredLoanMap
llvm::ImmutableMap< OriginID, LoanSet > OriginLoanMap
void runLifetimeSafetyAnalysis(AnalysisDeclContext &AC, LifetimeSafetyReporter *Reporter)
The main entry point for the analysis.
Confidence
Enum to track the confidence level of a potential error.
@ Result
The result type of a method or function.
const FunctionProtoType * T
@ Other
Other implicit parameter.
A worklist implementation for backward dataflow analysis.
A worklist implementation for forward dataflow analysis.
Represents the storage location being borrowed, e.g., a specific stack variable.
AccessPath(const clang::ValueDecl *D)
The dataflow lattice for tracking the set of expired loans.
ExpiredLoanMap Expired
Map from an expired LoanID to the ExpireFact that made it expire.
bool operator==(const ExpiredLattice &Other) const
void dump(llvm::raw_ostream &OS) const
bool operator!=(const ExpiredLattice &Other) const
An object to hold the factories for immutable collections, ensuring that all created states share the...
Represents the dataflow lattice for loan propagation.
bool operator!=(const LoanPropagationLattice &Other) const
OriginLoanMap Origins
The map from an origin to the set of loans it contains.
bool operator==(const LoanPropagationLattice &Other) const
Information about a single borrow, or "Loan".
Loan(LoanID id, AccessPath path, const Expr *IssueExpr)
const Expr * IssueExpr
The expression that creates the loan, e.g., &x.
LoanID ID
TODO: Represent opaque loans.
An Origin is a symbolic identifier that represents the set of possible loans a pointer-like object co...
Origin(OriginID ID, const clang::Expr *E)
const clang::Expr * getExpr() const
const clang::ValueDecl * getDecl() const
llvm::PointerUnion< const clang::ValueDecl *, const clang::Expr * > Ptr
A pointer to the AST node that this origin represents.
Origin(OriginID ID, const clang::ValueDecl *D)
Struct to store the complete context for a potential lifetime violation.