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