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