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 if (MovedLoan->getAccessPath() == Path)
84 return true;
85 }
86 return false;
87 };
88 for (auto [O, _] : LiveOrigins.getLiveOriginsAt(P: &F))
89 for (LoanID LiveLoan : LoanPropagation.getLoans(OID: O, P: &F)) {
90 const Loan *LiveLoanPtr = LoanMgr.getLoan(ID: LiveLoan);
91 if (IsInvalidated(LiveLoanPtr->getAccessPath()))
92 MovedLoans =
93 MovedLoansMapFactory.add(Old: MovedLoans, K: LiveLoan, D: F.getMoveExpr());
94 }
95 return Lattice(MovedLoans);
96 }
97
98 MovedLoansMap getMovedLoans(ProgramPoint P) { return getState(P).MovedLoans; }
99
100private:
101 const LoanPropagationAnalysis &LoanPropagation;
102 const LiveOriginsAnalysis &LiveOrigins;
103 const LoanManager &LoanMgr;
104 MovedLoansMap::Factory &MovedLoansMapFactory;
105};
106} // namespace
107
108class MovedLoansAnalysis::Impl final : public AnalysisImpl {
109 using AnalysisImpl::AnalysisImpl;
110};
111
112MovedLoansAnalysis::MovedLoansAnalysis(
113 const CFG &C, AnalysisDeclContext &AC, FactManager &F,
114 const LoanPropagationAnalysis &LoanPropagation,
115 const LiveOriginsAnalysis &LiveOrigins, const LoanManager &LoanMgr,
116 MovedLoansMap::Factory &MovedLoansMapFactory)
117 : PImpl(std::make_unique<Impl>(args: C, args&: AC, args&: F, args: LoanPropagation, args: LiveOrigins,
118 args: LoanMgr, args&: MovedLoansMapFactory)) {
119 PImpl->run();
120}
121
122MovedLoansAnalysis::~MovedLoansAnalysis() = default;
123
124MovedLoansMap MovedLoansAnalysis::getMovedLoans(ProgramPoint P) const {
125 return PImpl->getMovedLoans(P);
126}
127} // namespace clang::lifetimes::internal
128