1//===- LoanPropagation.cpp - Loan Propagation 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#include <algorithm>
9#include <cassert>
10#include <memory>
11
12#include "Dataflow.h"
13#include "clang/AST/Expr.h"
14#include "clang/Analysis/Analyses/LifetimeSafety/Facts.h"
15#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h"
16#include "clang/Analysis/Analyses/LifetimeSafety/Loans.h"
17#include "clang/Analysis/Analyses/LifetimeSafety/Origins.h"
18#include "clang/Analysis/Analyses/LifetimeSafety/Utils.h"
19#include "clang/Analysis/AnalysisDeclContext.h"
20#include "clang/Analysis/CFG.h"
21#include "clang/Basic/LLVM.h"
22#include "llvm/ADT/BitVector.h"
23#include "llvm/ADT/ImmutableList.h"
24#include "llvm/ADT/SmallSet.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/Support/raw_ostream.h"
27
28namespace clang::lifetimes::internal {
29
30namespace {
31
32/// Represents the dataflow lattice for loan propagation.
33///
34/// This lattice tracks which loans each origin may hold at a given program
35/// point.The lattice has a finite height: An origin's loan set is bounded by
36/// the total number of loans in the function.
37struct Lattice {
38 /// The map from an origin to the set of loans it contains.
39 /// Origins that appear in multiple blocks. Participates in join operations.
40 OriginLoanMap PersistentOrigins = OriginLoanMap(nullptr);
41 /// Origins confined to a single block. Discarded at block boundaries.
42 OriginLoanMap BlockLocalOrigins = OriginLoanMap(nullptr);
43
44 explicit Lattice(const OriginLoanMap &Persistent,
45 const OriginLoanMap &BlockLocal)
46 : PersistentOrigins(Persistent), BlockLocalOrigins(BlockLocal) {}
47 Lattice() = default;
48
49 bool operator==(const Lattice &Other) const {
50 return PersistentOrigins == Other.PersistentOrigins &&
51 BlockLocalOrigins == Other.BlockLocalOrigins;
52 }
53 bool operator!=(const Lattice &Other) const { return !(*this == Other); }
54
55 void dump(llvm::raw_ostream &OS) const {
56 OS << "LoanPropagationLattice State:\n";
57 OS << " Persistent Origins:\n";
58 if (PersistentOrigins.isEmpty())
59 OS << " <empty>\n";
60 for (const auto &Entry : PersistentOrigins) {
61 if (Entry.second.isEmpty())
62 OS << " Origin " << Entry.first << " contains no loans\n";
63 for (const LoanID &LID : Entry.second)
64 OS << " Origin " << Entry.first << " contains Loan " << LID << "\n";
65 }
66 OS << " Block-Local Origins:\n";
67 if (BlockLocalOrigins.isEmpty())
68 OS << " <empty>\n";
69 for (const auto &Entry : BlockLocalOrigins) {
70 if (Entry.second.isEmpty())
71 OS << " Origin " << Entry.first << " contains no loans\n";
72 for (const LoanID &LID : Entry.second)
73 OS << " Origin " << Entry.first << " contains Loan " << LID << "\n";
74 }
75 }
76};
77
78class AnalysisImpl
79 : public DataflowAnalysis<AnalysisImpl, Lattice, Direction::Forward> {
80public:
81 AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
82 OriginLoanMap::Factory &OriginLoanMapFactory,
83 LoanSet::Factory &LoanSetFactory)
84 : DataflowAnalysis(C, AC, F), OriginLoanMapFactory(OriginLoanMapFactory),
85 LoanSetFactory(LoanSetFactory),
86 PersistentOrigins(F.getPersistentOrigins()) {}
87
88 using Base::transfer;
89
90 StringRef getAnalysisName() const { return "LoanPropagation"; }
91
92 Lattice getInitialState() { return Lattice{}; }
93
94 /// Merges two lattices by taking the union of loans for each origin.
95 Lattice join(Lattice A, Lattice B) {
96 assert(A.BlockLocalOrigins.isEmpty() && B.BlockLocalOrigins.isEmpty() &&
97 "block-local origins must not reach a block boundary");
98 OriginLoanMap JoinedOrigins = utils::join(
99 A: A.PersistentOrigins, B: B.PersistentOrigins, F&: OriginLoanMapFactory,
100 JoinValues: [&](const LoanSet *S1, const LoanSet *S2) {
101 assert((S1 || S2) && "unexpectedly merging 2 empty sets");
102 if (!S1)
103 return *S2;
104 if (!S2)
105 return *S1;
106 return utils::join(A: *S1, B: *S2, F&: LoanSetFactory);
107 },
108 // Asymmetric join is a performance win. For origins present only on one
109 // branch, the loan set can be carried over as-is.
110 Kind: utils::JoinKind::Asymmetric);
111 return Lattice(JoinedOrigins, OriginLoanMapFactory.getEmptyMap());
112 }
113
114 /// Block-local origins are not referenced outside the block that computed
115 /// them, so they are dropped here rather than propagated to adjacent blocks.
116 /// Dropping them at the boundary (instead of in `join`) also covers edges
117 /// where `join` is never called, such as blocks with a single predecessor.
118 Lattice transferAtBlockExit(Lattice L) {
119 return Lattice(L.PersistentOrigins, OriginLoanMapFactory.getEmptyMap());
120 }
121
122 /// A new loan is issued to the origin. Old loans are erased.
123 Lattice transfer(Lattice In, const IssueFact &F) {
124 OriginID OID = F.getOriginID();
125 LoanID LID = F.getLoanID();
126 LoanSet NewLoans = LoanSetFactory.add(Old: LoanSetFactory.getEmptySet(), V: LID);
127 return setLoans(L: In, OID, Loans: NewLoans);
128 }
129
130 /// A flow from source to destination. If `KillDest` is true, this replaces
131 /// the destination's loans with the source's. Otherwise, the source's loans
132 /// are merged into the destination's.
133 Lattice transfer(Lattice In, const OriginFlowFact &F) {
134 OriginID DestOID = F.getDestOriginID();
135 OriginID SrcOID = F.getSrcOriginID();
136
137 LoanSet DestLoans =
138 F.getKillDest() ? LoanSetFactory.getEmptySet() : getLoans(L: In, OID: DestOID);
139 LoanSet SrcLoans = getLoans(L: In, OID: SrcOID);
140 LoanSet MergedLoans = utils::join(A: DestLoans, B: SrcLoans, F&: LoanSetFactory);
141
142 return setLoans(L: In, OID: DestOID, Loans: MergedLoans);
143 }
144
145 Lattice transfer(Lattice In, const KillOriginFact &F) {
146 return setLoans(L: In, OID: F.getKilledOrigin(), Loans: LoanSetFactory.getEmptySet());
147 }
148
149 Lattice transfer(Lattice In, const ExpireFact &F) {
150 if (auto OID = F.getOriginID())
151 return setLoans(L: In, OID: *OID, Loans: LoanSetFactory.getEmptySet());
152 return In;
153 }
154
155 LoanSet getLoans(OriginID OID, ProgramPoint P) const {
156 return getLoans(L: getState(P), OID);
157 }
158
159 llvm::SmallVector<OriginID> buildOriginFlowChain(ProgramPoint StartPoint,
160 const OriginID StartOID,
161 const LoanID TargetLoan,
162 const CFG *Cfg) const {
163 assert(getLoans(StartOID, StartPoint).contains(TargetLoan) &&
164 "TargetLoan must be present in the StartOID at the StartPoint");
165
166 // Locate the CFG block containing the StartPoint
167 const CFGBlock *EndBlock = nullptr;
168 size_t BlockID = FactMgr.getBlockID(P: StartPoint);
169 for (const CFGBlock *Block : *Cfg)
170 if (Block->getBlockID() == BlockID) {
171 EndBlock = Block;
172 break;
173 }
174
175 // Set up DFS traversal state
176 // SearchState tracks which block we're in and which origin we're tracing
177 // Each DFSNode maintains its own OriginFlowChain.
178 using SearchState = std::pair<const CFGBlock *, OriginID>;
179 struct DFSNode {
180 SearchState CurrState;
181 llvm::ImmutableList<OriginID> OriginFlowChain;
182 };
183
184 llvm::SmallVector<DFSNode> PendingStates;
185 llvm::SmallSet<SearchState, 16> VistedStates;
186 llvm::ImmutableList<OriginID>::Factory OriginFlowChainFactory;
187 PendingStates.push_back(
188 Elt: {.CurrState: {EndBlock, StartOID}, .OriginFlowChain: OriginFlowChainFactory.getEmptyList()});
189
190 // The loans held at StartPoint cannot come from later flows, so the first
191 // scan starts there. A loop may lead back to StartPoint's block; that visit
192 // is its previous iteration, which ran entirely before StartPoint, so scan
193 // the whole block.
194 ProgramPoint ScanFrom = StartPoint;
195
196 // DFS loop to trace loan backwards through CFG
197 while (!PendingStates.empty()) {
198 DFSNode CurrNode = PendingStates.pop_back_val();
199 auto [CurrBlock, CurrOID] = CurrNode.CurrState;
200
201 // Trace origins within the current block
202 const auto [BuildResult, Complete] =
203 buildOriginFlowChain(Block: CurrBlock, StartOID: CurrOID, TargetLoan, ScanFrom);
204 ScanFrom = nullptr;
205 if (!BuildResult.empty()) {
206 for (OriginID OID : BuildResult)
207 CurrNode.OriginFlowChain =
208 OriginFlowChainFactory.add(Data&: OID, L: CurrNode.OriginFlowChain);
209 CurrOID = BuildResult.back();
210 }
211
212 // If we found the IssueFact, we're done
213 if (Complete) {
214 llvm::SmallVector<OriginID> Result(CurrNode.OriginFlowChain.begin(),
215 CurrNode.OriginFlowChain.end());
216 std::reverse(first: Result.begin(), last: Result.end());
217 return Result;
218 }
219
220 // Only explore predecessor blocks where the target loan is present in the
221 // current origin.
222 for (const CFGBlock *PredBlock : CurrBlock->preds()) {
223 SearchState NextState = {PredBlock, CurrOID};
224 if (getLoans(L: getOutState(B: PredBlock), OID: CurrOID).contains(V: TargetLoan) &&
225 VistedStates.insert(V: NextState).second)
226 PendingStates.push_back(Elt: {.CurrState: NextState, .OriginFlowChain: CurrNode.OriginFlowChain});
227 }
228 }
229
230 llvm_unreachable("Could not reconstruct origin flow. Search finished "
231 "without reaching IssueFact");
232 }
233
234 llvm::SmallVector<OriginID> buildOriginFlowChain(const UseFact *UF,
235 const LoanID TargetLoan,
236 const CFG *Cfg) const {
237 for (const OriginList *Cur = UF->getUsedOrigins(); Cur;
238 Cur = Cur->peelOuterOrigin())
239 if (getLoans(OID: Cur->getOuterOriginID(), P: UF).contains(V: TargetLoan))
240 return dropLeadingLoads(
241 StartOID: Cur->getOuterOriginID(),
242 Chain: buildOriginFlowChain(StartPoint: UF, StartOID: Cur->getOuterOriginID(), TargetLoan, Cfg));
243
244 return {};
245 }
246
247 llvm::SmallVector<OriginID> buildOriginFlowChain(const OriginEscapesFact *OEF,
248 const LoanID TargetLoan,
249 const CFG *Cfg) const {
250 OriginID OID = OEF->getEscapedOriginID();
251 if (!getLoans(OID, P: OEF).contains(V: TargetLoan))
252 return {};
253 return dropLeadingLoads(StartOID: OID,
254 Chain: buildOriginFlowChain(StartPoint: OEF, StartOID: OID, TargetLoan, Cfg));
255 }
256
257private:
258 /// An expression's origin only receives loans from its subexpressions, so
259 /// until the chain reaches a declaration it is inside the expression the
260 /// chain starts from. Casts there just load its variable, so drop them.
261 llvm::SmallVector<OriginID>
262 dropLeadingLoads(OriginID StartOID, llvm::SmallVector<OriginID> Chain) const {
263 const OriginManager &OM = FactMgr.getOriginMgr();
264 // When the chain starts from a declaration, e.g. field `p_` read by a
265 // member call, the leading casts come from the write that stored the loan
266 // in it, such as `p` loaded in `p_ = p`. They name the alias, so keep them.
267 if (!OM.getOrigin(ID: StartOID).getExpr())
268 return Chain;
269 auto FirstDecl = llvm::find_if(
270 Range&: Chain, P: [&](OriginID OID) { return !OM.getOrigin(ID: OID).getExpr(); });
271 Chain.erase(CS: std::remove_if(first: Chain.begin(), last: FirstDecl,
272 pred: [&](OriginID OID) {
273 return isa<ImplicitCastExpr>(
274 Val: OM.getOrigin(ID: OID).getExpr());
275 }),
276 CE: FirstDecl);
277 return Chain;
278 }
279
280 /// Returns true if the origin is persistent (referenced in multiple blocks).
281 bool isPersistent(OriginID OID) const {
282 return PersistentOrigins.test(Idx: OID.Value);
283 }
284
285 Lattice setLoans(Lattice L, OriginID OID, LoanSet Loans) {
286 if (isPersistent(OID))
287 return Lattice(OriginLoanMapFactory.add(Old: L.PersistentOrigins, K: OID, D: Loans),
288 L.BlockLocalOrigins);
289 return Lattice(L.PersistentOrigins,
290 OriginLoanMapFactory.add(Old: L.BlockLocalOrigins, K: OID, D: Loans));
291 }
292
293 LoanSet getLoans(Lattice L, OriginID OID) const {
294 const OriginLoanMap *Map =
295 isPersistent(OID) ? &L.PersistentOrigins : &L.BlockLocalOrigins;
296 if (auto *Loans = Map->lookup(K: OID))
297 return *Loans;
298 return LoanSetFactory.getEmptySet();
299 }
300
301 /// Builds the chain of origins through which a loan has propagated.
302 ///
303 /// This procedure operates strictly within a single Block. Starting from
304 /// \p ScanFrom, or from the last fact of the Block if it is null, it traces
305 /// backwards through OriginFlowFacts to identify the sequence of origins
306 /// through which the loan flowed.
307 ///
308 /// Returns (chain, true) if the target loan origin is found during the
309 /// traversal, otherwise returns (chain, false).
310 std::pair<llvm::SmallVector<OriginID>, bool>
311 buildOriginFlowChain(const CFGBlock *Block, const OriginID StartOID,
312 const LoanID TargetLoan, ProgramPoint ScanFrom) const {
313 OriginID CurrOID = StartOID;
314 llvm::SmallVector<OriginID> OriginFlowChain;
315
316 auto Facts = llvm::reverse(C: FactMgr.getFacts(B: Block));
317 auto Begin = Facts.begin();
318 if (ScanFrom) {
319 Begin = llvm::find(Range&: Facts, Val: ScanFrom);
320 assert(Begin != Facts.end() && "ScanFrom must be in Block");
321 }
322 for (const Fact *F : llvm::make_range(x: Begin, y: Facts.end())) {
323 if (const auto *IF = F->getAs<IssueFact>())
324 if (IF->getLoanID() == TargetLoan && IF->getOriginID() == CurrOID)
325 return {OriginFlowChain, true};
326
327 const auto *OFF = F->getAs<OriginFlowFact>();
328 if (!OFF || OFF->getDestOriginID() != CurrOID)
329 continue;
330
331 const OriginID SrcOriginID = OFF->getSrcOriginID();
332 if (!getLoans(OID: SrcOriginID, P: OFF).contains(V: TargetLoan))
333 continue;
334
335 OriginFlowChain.push_back(Elt: SrcOriginID);
336 CurrOID = SrcOriginID;
337 }
338
339 return {OriginFlowChain, false};
340 }
341
342 OriginLoanMap::Factory &OriginLoanMapFactory;
343 LoanSet::Factory &LoanSetFactory;
344 /// Origins referenced from more than one basic block; see
345 /// `FactManager::getPersistentOrigins`.
346 const llvm::BitVector &PersistentOrigins;
347};
348} // namespace
349
350class LoanPropagationAnalysis::Impl final : public AnalysisImpl {
351 using AnalysisImpl::AnalysisImpl;
352};
353
354LoanPropagationAnalysis::LoanPropagationAnalysis(
355 const CFG &C, AnalysisDeclContext &AC, FactManager &F,
356 OriginLoanMap::Factory &OriginLoanMapFactory,
357 LoanSet::Factory &LoanSetFactory)
358 : PImpl(std::make_unique<Impl>(args: C, args&: AC, args&: F, args&: OriginLoanMapFactory,
359 args&: LoanSetFactory)) {
360 PImpl->run();
361}
362
363LoanPropagationAnalysis::~LoanPropagationAnalysis() = default;
364
365LoanSet LoanPropagationAnalysis::getLoans(OriginID OID, ProgramPoint P) const {
366 return PImpl->getLoans(OID, P);
367}
368
369llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain(
370 ProgramPoint StartPoint, const OriginID StartOID, const LoanID TargetLoan,
371 const CFG *Cfg) const {
372 return PImpl->buildOriginFlowChain(StartPoint, StartOID, TargetLoan, Cfg);
373}
374
375llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain(
376 const Fact *F, const LoanID TargetLoan, const CFG *Cfg) const {
377 if (const auto *UF = llvm::dyn_cast<UseFact>(Val: F))
378 return PImpl->buildOriginFlowChain(UF, TargetLoan, Cfg);
379 if (const auto *OEF = llvm::dyn_cast<OriginEscapesFact>(Val: F))
380 return PImpl->buildOriginFlowChain(OEF, TargetLoan, Cfg);
381 llvm_unreachable("Unhandled Fact type");
382}
383} // namespace clang::lifetimes::internal
384