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