1//===- MovedLoans.cpp - Moved Loans 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//===----------------------------------------------------------------------===//
8//
9// This file defines the MovedLoansAnalysis, a forward dataflow analysis that
10// tracks which loans have been moved out of their original storage location
11// at each program point.
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h"
16#include "Dataflow.h"
17#include "clang/Analysis/Analyses/LifetimeSafety/Facts.h"
18#include "clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h"
19#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h"
20#include "clang/Analysis/Analyses/LifetimeSafety/Loans.h"
21#include "clang/Analysis/Analyses/LifetimeSafety/Utils.h"
22
23namespace clang::lifetimes::internal {
24namespace {
25struct Lattice {
26 MovedLoansMap MovedLoans = MovedLoansMap(nullptr);
27
28 explicit Lattice(MovedLoansMap MovedLoans) : MovedLoans(MovedLoans) {}
29
30 Lattice() = default;
31
32 bool operator==(const Lattice &Other) const {
33 return MovedLoans == Other.MovedLoans;
34 }
35 bool operator!=(const Lattice &Other) const { return !(*this == Other); }
36};
37
38class AnalysisImpl
39 : public DataflowAnalysis<AnalysisImpl, Lattice, Direction::Forward> {
40public:
41 AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
42 const LoanPropagationAnalysis &LoanPropagation,
43 const LiveOriginsAnalysis &LiveOrigins,
44 const LoanManager &LoanMgr,
45 MovedLoansMap::Factory &MovedLoansMapFactory)
46 : DataflowAnalysis(C, AC, F), LoanPropagation(LoanPropagation),
47 LiveOrigins(LiveOrigins), LoanMgr(LoanMgr),
48 MovedLoansMapFactory(MovedLoansMapFactory) {}
49
50 using Base::transfer;
51
52 StringRef getAnalysisName() const { return "MovedLoans"; }
53
54 Lattice getInitialState() { return Lattice{}; }
55
56 /// Merges moved loan state from different control flow paths. When a loan
57 /// is moved on multiple paths, picks the lexically earliest move expression.
58 Lattice join(Lattice A, Lattice B) {
59 MovedLoansMap MovedLoans = utils::join(
60 A: A.MovedLoans, B: B.MovedLoans, F&: MovedLoansMapFactory,
61 JoinValues: [](const Expr *const *MoveA, const Expr *const *MoveB) -> const Expr * {
62 assert(MoveA || MoveB);
63 if (!MoveA)
64 return *MoveB;
65 if (!MoveB)
66 return *MoveA;
67 return (*MoveA)->getExprLoc() < (*MoveB)->getExprLoc() ? *MoveA
68 : *MoveB;
69 },
70 Kind: utils::JoinKind::Asymmetric);
71 return Lattice(MovedLoans);
72 }
73
74 /// Marks all live loans sharing the same access path as the moved origin as
75 /// potentially moved.
76 Lattice transfer(Lattice In, const MovedOriginFact &F) {
77 MovedLoansMap MovedLoans = In.MovedLoans;
78 OriginID MovedOrigin = F.getMovedOrigin();
79 LoanSet ImmediatelyMovedLoans = LoanPropagation.getLoans(OID: MovedOrigin, P: &F);
80 auto IsInvalidated = [&](const AccessPath &Path) {
81 for (LoanID LID : ImmediatelyMovedLoans) {
82 const Loan *MovedLoan = LoanMgr.getLoan(ID: LID);
83 auto *PL = dyn_cast<PathLoan>(Val: MovedLoan);
84 if (!PL)
85 continue;
86 if (PL->getAccessPath() == Path)
87 return true;
88 }
89 return false;
90 };
91 for (auto [O, _] : LiveOrigins.getLiveOriginsAt(P: &F))
92 for (LoanID LiveLoan : LoanPropagation.getLoans(OID: O, P: &F)) {
93 const Loan *LiveLoanPtr = LoanMgr.getLoan(ID: LiveLoan);
94 auto *PL = dyn_cast<PathLoan>(Val: LiveLoanPtr);
95 if (!PL)
96 continue;
97 if (IsInvalidated(PL->getAccessPath()))
98 MovedLoans =
99 MovedLoansMapFactory.add(Old: MovedLoans, K: LiveLoan, D: F.getMoveExpr());
100 }
101 return Lattice(MovedLoans);
102 }
103
104 MovedLoansMap getMovedLoans(ProgramPoint P) { return getState(P).MovedLoans; }
105
106private:
107 const LoanPropagationAnalysis &LoanPropagation;
108 const LiveOriginsAnalysis &LiveOrigins;
109 const LoanManager &LoanMgr;
110 MovedLoansMap::Factory &MovedLoansMapFactory;
111};
112} // namespace
113
114class MovedLoansAnalysis::Impl final : public AnalysisImpl {
115 using AnalysisImpl::AnalysisImpl;
116};
117
118MovedLoansAnalysis::MovedLoansAnalysis(
119 const CFG &C, AnalysisDeclContext &AC, FactManager &F,
120 const LoanPropagationAnalysis &LoanPropagation,
121 const LiveOriginsAnalysis &LiveOrigins, const LoanManager &LoanMgr,
122 MovedLoansMap::Factory &MovedLoansMapFactory)
123 : PImpl(std::make_unique<Impl>(args: C, args&: AC, args&: F, args: LoanPropagation, args: LiveOrigins,
124 args: LoanMgr, args&: MovedLoansMapFactory)) {
125 PImpl->run();
126}
127
128MovedLoansAnalysis::~MovedLoansAnalysis() = default;
129
130MovedLoansMap MovedLoansAnalysis::getMovedLoans(ProgramPoint P) const {
131 return PImpl->getMovedLoans(P);
132}
133} // namespace clang::lifetimes::internal
134