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 // DFS loop to trace loan backwards through CFG
191 while (!PendingStates.empty()) {
192 DFSNode CurrNode = PendingStates.pop_back_val();
193 auto [CurrBlock, CurrOID] = CurrNode.CurrState;
194
195 // Trace origins within the current block
196 const auto [BuildResult, Complete] =
197 buildOriginFlowChain(Block: CurrBlock, StartOID: CurrOID, TargetLoan);
198 if (!BuildResult.empty()) {
199 for (OriginID OID : BuildResult)
200 CurrNode.OriginFlowChain =
201 OriginFlowChainFactory.add(Data&: OID, L: CurrNode.OriginFlowChain);
202 CurrOID = BuildResult.back();
203 }
204
205 // If we found the IssueFact, we're done
206 if (Complete) {
207 llvm::SmallVector<OriginID> Result(CurrNode.OriginFlowChain.begin(),
208 CurrNode.OriginFlowChain.end());
209 std::reverse(first: Result.begin(), last: Result.end());
210 return Result;
211 }
212
213 // Only explore predecessor blocks where the target loan is present in the
214 // current origin.
215 for (const CFGBlock *PredBlock : CurrBlock->preds()) {
216 SearchState NextState = {PredBlock, CurrOID};
217 if (getLoans(L: getOutState(B: PredBlock), OID: CurrOID).contains(V: TargetLoan) &&
218 VistedStates.insert(V: NextState).second)
219 PendingStates.push_back(Elt: {.CurrState: NextState, .OriginFlowChain: CurrNode.OriginFlowChain});
220 }
221 }
222
223 llvm_unreachable("Could not reconstruct origin flow. Search finished "
224 "without reaching IssueFact");
225 }
226
227 llvm::SmallVector<OriginID> buildOriginFlowChain(const UseFact *UF,
228 const LoanID TargetLoan,
229 const CFG *Cfg) const {
230 for (const OriginList *Cur = UF->getUsedOrigins(); Cur;
231 Cur = Cur->peelOuterOrigin())
232 if (getLoans(OID: Cur->getOuterOriginID(), P: UF).contains(V: TargetLoan))
233 return dropLeadingLoads(
234 Chain: buildOriginFlowChain(StartPoint: UF, StartOID: Cur->getOuterOriginID(), TargetLoan, Cfg));
235
236 return {};
237 }
238
239 llvm::SmallVector<OriginID> buildOriginFlowChain(const OriginEscapesFact *OEF,
240 const LoanID TargetLoan,
241 const CFG *Cfg) const {
242 OriginID OID = OEF->getEscapedOriginID();
243 if (!getLoans(OID, P: OEF).contains(V: TargetLoan))
244 return {};
245 return dropLeadingLoads(Chain: buildOriginFlowChain(StartPoint: OEF, StartOID: OID, TargetLoan, Cfg));
246 }
247
248private:
249 /// An expression's origin only receives loans from its subexpressions, so
250 /// until the chain reaches a declaration it is inside the expression the
251 /// chain starts from. Casts there just load its variable, so drop them.
252 llvm::SmallVector<OriginID>
253 dropLeadingLoads(llvm::SmallVector<OriginID> Chain) const {
254 const OriginManager &OM = FactMgr.getOriginMgr();
255 auto FirstDecl = llvm::find_if(
256 Range&: Chain, P: [&](OriginID OID) { return !OM.getOrigin(ID: OID).getExpr(); });
257 Chain.erase(CS: std::remove_if(first: Chain.begin(), last: FirstDecl,
258 pred: [&](OriginID OID) {
259 return isa<ImplicitCastExpr>(
260 Val: OM.getOrigin(ID: OID).getExpr());
261 }),
262 CE: FirstDecl);
263 return Chain;
264 }
265
266 /// Returns true if the origin is persistent (referenced in multiple blocks).
267 bool isPersistent(OriginID OID) const {
268 return PersistentOrigins.test(Idx: OID.Value);
269 }
270
271 Lattice setLoans(Lattice L, OriginID OID, LoanSet Loans) {
272 if (isPersistent(OID))
273 return Lattice(OriginLoanMapFactory.add(Old: L.PersistentOrigins, K: OID, D: Loans),
274 L.BlockLocalOrigins);
275 return Lattice(L.PersistentOrigins,
276 OriginLoanMapFactory.add(Old: L.BlockLocalOrigins, K: OID, D: Loans));
277 }
278
279 LoanSet getLoans(Lattice L, OriginID OID) const {
280 const OriginLoanMap *Map =
281 isPersistent(OID) ? &L.PersistentOrigins : &L.BlockLocalOrigins;
282 if (auto *Loans = Map->lookup(K: OID))
283 return *Loans;
284 return LoanSetFactory.getEmptySet();
285 }
286
287 /// Builds the chain of origins through which a loan has propagated.
288 ///
289 /// This procedure operates strictly within a single Block. Starting from the
290 /// last fact of the Block, it traces backwards through OriginFlowFacts to
291 /// identify the sequence of origins through which the loan flowed.
292 ///
293 /// Returns (chain, true) if the target loan origin is found during the
294 /// traversal, otherwise returns (chain, false).
295 std::pair<llvm::SmallVector<OriginID>, bool>
296 buildOriginFlowChain(const CFGBlock *Block, const OriginID StartOID,
297 const LoanID TargetLoan) const {
298 OriginID CurrOID = StartOID;
299 llvm::SmallVector<OriginID> OriginFlowChain;
300
301 for (const Fact *F : llvm::reverse(C: FactMgr.getFacts(B: Block))) {
302 if (const auto *IF = F->getAs<IssueFact>())
303 if (IF->getLoanID() == TargetLoan && IF->getOriginID() == CurrOID)
304 return {OriginFlowChain, true};
305
306 const auto *OFF = F->getAs<OriginFlowFact>();
307 if (!OFF || OFF->getDestOriginID() != CurrOID)
308 continue;
309
310 const OriginID SrcOriginID = OFF->getSrcOriginID();
311 if (!getLoans(OID: SrcOriginID, P: OFF).contains(V: TargetLoan))
312 continue;
313
314 OriginFlowChain.push_back(Elt: SrcOriginID);
315 CurrOID = SrcOriginID;
316 }
317
318 return {OriginFlowChain, false};
319 }
320
321 OriginLoanMap::Factory &OriginLoanMapFactory;
322 LoanSet::Factory &LoanSetFactory;
323 /// Origins referenced from more than one basic block; see
324 /// `FactManager::getPersistentOrigins`.
325 const llvm::BitVector &PersistentOrigins;
326};
327} // namespace
328
329class LoanPropagationAnalysis::Impl final : public AnalysisImpl {
330 using AnalysisImpl::AnalysisImpl;
331};
332
333LoanPropagationAnalysis::LoanPropagationAnalysis(
334 const CFG &C, AnalysisDeclContext &AC, FactManager &F,
335 OriginLoanMap::Factory &OriginLoanMapFactory,
336 LoanSet::Factory &LoanSetFactory)
337 : PImpl(std::make_unique<Impl>(args: C, args&: AC, args&: F, args&: OriginLoanMapFactory,
338 args&: LoanSetFactory)) {
339 PImpl->run();
340}
341
342LoanPropagationAnalysis::~LoanPropagationAnalysis() = default;
343
344LoanSet LoanPropagationAnalysis::getLoans(OriginID OID, ProgramPoint P) const {
345 return PImpl->getLoans(OID, P);
346}
347
348llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain(
349 ProgramPoint StartPoint, const OriginID StartOID, const LoanID TargetLoan,
350 const CFG *Cfg) const {
351 return PImpl->buildOriginFlowChain(StartPoint, StartOID, TargetLoan, Cfg);
352}
353
354llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain(
355 const UseFact *UF, const LoanID TargetLoan, const CFG *Cfg) const {
356 return PImpl->buildOriginFlowChain(UF, TargetLoan, Cfg);
357}
358llvm::SmallVector<OriginID>
359LoanPropagationAnalysis::buildOriginFlowChain(const OriginEscapesFact *OEF,
360 const LoanID TargetLoan,
361 const CFG *Cfg) const {
362 return PImpl->buildOriginFlowChain(OEF, TargetLoan, Cfg);
363}
364} // namespace clang::lifetimes::internal
365