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/SmallVector.h"
22#include "llvm/Support/TimeProfiler.h"
23#include "llvm/Support/raw_ostream.h"
24
25namespace clang::lifetimes::internal {
26
27// Prepass to find persistent origins. An origin is persistent if it is
28// referenced in more than one basic block.
29static llvm::BitVector computePersistentOrigins(const FactManager &FactMgr,
30 const CFG &C) {
31 llvm::TimeTraceScope("ComputePersistentOrigins");
32 unsigned NumOrigins = FactMgr.getOriginMgr().getNumOrigins();
33 llvm::BitVector PersistentOrigins(NumOrigins);
34
35 llvm::SmallVector<const CFGBlock *> OriginToFirstSeenBlock(NumOrigins,
36 nullptr);
37 for (const CFGBlock *B : C) {
38 for (const Fact *F : FactMgr.getFacts(B)) {
39 auto CheckOrigin = [&](OriginID OID) {
40 if (PersistentOrigins.test(Idx: OID.Value))
41 return;
42 auto &FirstSeenBlock = OriginToFirstSeenBlock[OID.Value];
43 if (FirstSeenBlock == nullptr)
44 FirstSeenBlock = B;
45 if (FirstSeenBlock != B) {
46 // We saw this origin in more than one block.
47 PersistentOrigins.set(OID.Value);
48 }
49 };
50
51 switch (F->getKind()) {
52 case Fact::Kind::Issue:
53 CheckOrigin(F->getAs<IssueFact>()->getOriginID());
54 break;
55 case Fact::Kind::OriginFlow: {
56 const auto *OF = F->getAs<OriginFlowFact>();
57 CheckOrigin(OF->getDestOriginID());
58 CheckOrigin(OF->getSrcOriginID());
59 break;
60 }
61 case Fact::Kind::Use:
62 for (const OriginList *Cur = F->getAs<UseFact>()->getUsedOrigins(); Cur;
63 Cur = Cur->peelOuterOrigin())
64 CheckOrigin(Cur->getOuterOriginID());
65 break;
66 case Fact::Kind::KillOrigin:
67 CheckOrigin(F->getAs<KillOriginFact>()->getKilledOrigin());
68 break;
69 case Fact::Kind::OriginEscapes:
70 // An escaping origin is read at the exit block but defined earlier, so
71 // it spans blocks and must participate in joins.
72 CheckOrigin(F->getAs<OriginEscapesFact>()->getEscapedOriginID());
73 break;
74 case Fact::Kind::MovedOrigin:
75 case Fact::Kind::Expire:
76 case Fact::Kind::TestPoint:
77 case Fact::Kind::InvalidateOrigin:
78 break;
79 }
80 }
81 }
82 return PersistentOrigins;
83}
84
85namespace {
86
87/// Represents the dataflow lattice for loan propagation.
88///
89/// This lattice tracks which loans each origin may hold at a given program
90/// point.The lattice has a finite height: An origin's loan set is bounded by
91/// the total number of loans in the function.
92struct Lattice {
93 /// The map from an origin to the set of loans it contains.
94 /// Origins that appear in multiple blocks. Participates in join operations.
95 OriginLoanMap PersistentOrigins = OriginLoanMap(nullptr);
96 /// Origins confined to a single block. Discarded at block boundaries.
97 OriginLoanMap BlockLocalOrigins = OriginLoanMap(nullptr);
98
99 explicit Lattice(const OriginLoanMap &Persistent,
100 const OriginLoanMap &BlockLocal)
101 : PersistentOrigins(Persistent), BlockLocalOrigins(BlockLocal) {}
102 Lattice() = default;
103
104 bool operator==(const Lattice &Other) const {
105 return PersistentOrigins == Other.PersistentOrigins &&
106 BlockLocalOrigins == Other.BlockLocalOrigins;
107 }
108 bool operator!=(const Lattice &Other) const { return !(*this == Other); }
109
110 void dump(llvm::raw_ostream &OS) const {
111 OS << "LoanPropagationLattice State:\n";
112 OS << " Persistent Origins:\n";
113 if (PersistentOrigins.isEmpty())
114 OS << " <empty>\n";
115 for (const auto &Entry : PersistentOrigins) {
116 if (Entry.second.isEmpty())
117 OS << " Origin " << Entry.first << " contains no loans\n";
118 for (const LoanID &LID : Entry.second)
119 OS << " Origin " << Entry.first << " contains Loan " << LID << "\n";
120 }
121 OS << " Block-Local Origins:\n";
122 if (BlockLocalOrigins.isEmpty())
123 OS << " <empty>\n";
124 for (const auto &Entry : BlockLocalOrigins) {
125 if (Entry.second.isEmpty())
126 OS << " Origin " << Entry.first << " contains no loans\n";
127 for (const LoanID &LID : Entry.second)
128 OS << " Origin " << Entry.first << " contains Loan " << LID << "\n";
129 }
130 }
131};
132
133class AnalysisImpl
134 : public DataflowAnalysis<AnalysisImpl, Lattice, Direction::Forward> {
135public:
136 AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
137 OriginLoanMap::Factory &OriginLoanMapFactory,
138 LoanSet::Factory &LoanSetFactory)
139 : DataflowAnalysis(C, AC, F), OriginLoanMapFactory(OriginLoanMapFactory),
140 LoanSetFactory(LoanSetFactory),
141 PersistentOrigins(computePersistentOrigins(FactMgr: F, C)) {}
142
143 using Base::transfer;
144
145 StringRef getAnalysisName() const { return "LoanPropagation"; }
146
147 Lattice getInitialState() { return Lattice{}; }
148
149 /// Merges two lattices by taking the union of loans for each origin.
150 /// Only persistent origins are joined; block-local origins are discarded.
151 Lattice join(Lattice A, Lattice B) {
152 OriginLoanMap JoinedOrigins = utils::join(
153 A: A.PersistentOrigins, B: B.PersistentOrigins, F&: OriginLoanMapFactory,
154 JoinValues: [&](const LoanSet *S1, const LoanSet *S2) {
155 assert((S1 || S2) && "unexpectedly merging 2 empty sets");
156 if (!S1)
157 return *S2;
158 if (!S2)
159 return *S1;
160 return utils::join(A: *S1, B: *S2, F&: LoanSetFactory);
161 },
162 // Asymmetric join is a performance win. For origins present only on one
163 // branch, the loan set can be carried over as-is.
164 Kind: utils::JoinKind::Asymmetric);
165 return Lattice(JoinedOrigins, OriginLoanMapFactory.getEmptyMap());
166 }
167
168 /// A new loan is issued to the origin. Old loans are erased.
169 Lattice transfer(Lattice In, const IssueFact &F) {
170 OriginID OID = F.getOriginID();
171 LoanID LID = F.getLoanID();
172 LoanSet NewLoans = LoanSetFactory.add(Old: LoanSetFactory.getEmptySet(), V: LID);
173 return setLoans(L: In, OID, Loans: NewLoans);
174 }
175
176 /// A flow from source to destination. If `KillDest` is true, this replaces
177 /// the destination's loans with the source's. Otherwise, the source's loans
178 /// are merged into the destination's.
179 Lattice transfer(Lattice In, const OriginFlowFact &F) {
180 OriginID DestOID = F.getDestOriginID();
181 OriginID SrcOID = F.getSrcOriginID();
182
183 LoanSet DestLoans =
184 F.getKillDest() ? LoanSetFactory.getEmptySet() : getLoans(L: In, OID: DestOID);
185 LoanSet SrcLoans = getLoans(L: In, OID: SrcOID);
186 LoanSet MergedLoans = utils::join(A: DestLoans, B: SrcLoans, F&: LoanSetFactory);
187
188 return setLoans(L: In, OID: DestOID, Loans: MergedLoans);
189 }
190
191 Lattice transfer(Lattice In, const KillOriginFact &F) {
192 return setLoans(L: In, OID: F.getKilledOrigin(), Loans: LoanSetFactory.getEmptySet());
193 }
194
195 Lattice transfer(Lattice In, const ExpireFact &F) {
196 if (auto OID = F.getOriginID())
197 return setLoans(L: In, OID: *OID, Loans: LoanSetFactory.getEmptySet());
198 return In;
199 }
200
201 LoanSet getLoans(OriginID OID, ProgramPoint P) const {
202 return getLoans(L: getState(P), OID);
203 }
204
205 llvm::SmallVector<OriginID>
206 buildOriginFlowChain(ProgramPoint StartPoint, const OriginID StartOID,
207 const LoanID TargetLoan) const {
208 assert(getLoans(StartOID, StartPoint).contains(TargetLoan) &&
209 "TargetLoan must be present in the StartOID at the StartPoint");
210
211 OriginID CurrOID = StartOID;
212 llvm::SmallVector<OriginID> OriginFlowChain;
213 llvm::ArrayRef<const Fact *> Facts = FactMgr.getBlockContaining(P: StartPoint);
214 const auto *StartIt = llvm::find(Range&: Facts, Val: StartPoint);
215 assert(StartIt != Facts.end());
216
217 for (const Fact *F :
218 llvm::reverse(C: llvm::make_range(x: Facts.begin(), y: StartIt))) {
219 if (const auto *IF = F->getAs<IssueFact>())
220 if (IF->getLoanID() == TargetLoan) {
221 assert(IF->getOriginID() == CurrOID);
222 return OriginFlowChain;
223 }
224
225 const auto *OFF = F->getAs<OriginFlowFact>();
226 if (!OFF)
227 continue;
228 if (OFF->getDestOriginID() != CurrOID)
229 continue;
230
231 const OriginID SrcOriginID = OFF->getSrcOriginID();
232 if (!getLoans(OID: SrcOriginID, P: OFF).contains(V: TargetLoan))
233 continue;
234 OriginFlowChain.push_back(Elt: SrcOriginID);
235 CurrOID = SrcOriginID;
236 }
237
238 // FIXME: Ideally, this return is unreachable and should be an assert
239 // because we expect to always finish at an IssueFact. But since current
240 // traversal is limited to a single CFG block, multi-block OriginFlowChain
241 // construction might miss the IssueFact. We should add llvm_unreachable
242 // here once multi-block support is implemented.
243 return {};
244 }
245
246 llvm::SmallVector<OriginID>
247 buildOriginFlowChain(const UseFact *UF, const LoanID TargetLoan) const {
248 for (const OriginList *Cur = UF->getUsedOrigins(); Cur;
249 Cur = Cur->peelOuterOrigin())
250 if (getLoans(OID: Cur->getOuterOriginID(), P: UF).contains(V: TargetLoan))
251 return buildOriginFlowChain(StartPoint: UF, StartOID: Cur->getOuterOriginID(), TargetLoan);
252
253 return {};
254 }
255
256private:
257 /// Returns true if the origin is persistent (referenced in multiple blocks).
258 bool isPersistent(OriginID OID) const {
259 return PersistentOrigins.test(Idx: OID.Value);
260 }
261
262 Lattice setLoans(Lattice L, OriginID OID, LoanSet Loans) {
263 if (isPersistent(OID))
264 return Lattice(OriginLoanMapFactory.add(Old: L.PersistentOrigins, K: OID, D: Loans),
265 L.BlockLocalOrigins);
266 return Lattice(L.PersistentOrigins,
267 OriginLoanMapFactory.add(Old: L.BlockLocalOrigins, K: OID, D: Loans));
268 }
269
270 LoanSet getLoans(Lattice L, OriginID OID) const {
271 const OriginLoanMap *Map =
272 isPersistent(OID) ? &L.PersistentOrigins : &L.BlockLocalOrigins;
273 if (auto *Loans = Map->lookup(K: OID))
274 return *Loans;
275 return LoanSetFactory.getEmptySet();
276 }
277
278 OriginLoanMap::Factory &OriginLoanMapFactory;
279 LoanSet::Factory &LoanSetFactory;
280 /// Boolean vector indexed by origin ID. If true, the origin appears in
281 /// multiple basic blocks and must participate in join operations. If false,
282 /// the origin is block-local and can be discarded at block boundaries.
283 llvm::BitVector PersistentOrigins;
284};
285} // namespace
286
287class LoanPropagationAnalysis::Impl final : public AnalysisImpl {
288 using AnalysisImpl::AnalysisImpl;
289};
290
291LoanPropagationAnalysis::LoanPropagationAnalysis(
292 const CFG &C, AnalysisDeclContext &AC, FactManager &F,
293 OriginLoanMap::Factory &OriginLoanMapFactory,
294 LoanSet::Factory &LoanSetFactory)
295 : PImpl(std::make_unique<Impl>(args: C, args&: AC, args&: F, args&: OriginLoanMapFactory,
296 args&: LoanSetFactory)) {
297 PImpl->run();
298}
299
300LoanPropagationAnalysis::~LoanPropagationAnalysis() = default;
301
302LoanSet LoanPropagationAnalysis::getLoans(OriginID OID, ProgramPoint P) const {
303 return PImpl->getLoans(OID, P);
304}
305
306llvm::SmallVector<OriginID>
307LoanPropagationAnalysis::buildOriginFlowChain(ProgramPoint StartPoint,
308 const OriginID StartOID,
309 const LoanID TargetLoan) const {
310 return PImpl->buildOriginFlowChain(StartPoint, StartOID, TargetLoan);
311}
312
313llvm::SmallVector<OriginID>
314LoanPropagationAnalysis::buildOriginFlowChain(const UseFact *UF,
315 const LoanID TargetLoan) const {
316 return PImpl->buildOriginFlowChain(UF, TargetLoan);
317}
318} // namespace clang::lifetimes::internal
319