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::OriginEscapes:
67 case Fact::Kind::Expire:
68 case Fact::Kind::TestPoint:
69 break;
70 }
71 }
72 }
73 return PersistentOrigins;
74}
75
76namespace {
77
78/// Represents the dataflow lattice for loan propagation.
79///
80/// This lattice tracks which loans each origin may hold at a given program
81/// point.The lattice has a finite height: An origin's loan set is bounded by
82/// the total number of loans in the function.
83struct Lattice {
84 /// The map from an origin to the set of loans it contains.
85 /// Origins that appear in multiple blocks. Participates in join operations.
86 OriginLoanMap PersistentOrigins = OriginLoanMap(nullptr);
87 /// Origins confined to a single block. Discarded at block boundaries.
88 OriginLoanMap BlockLocalOrigins = OriginLoanMap(nullptr);
89
90 explicit Lattice(const OriginLoanMap &Persistent,
91 const OriginLoanMap &BlockLocal)
92 : PersistentOrigins(Persistent), BlockLocalOrigins(BlockLocal) {}
93 Lattice() = default;
94
95 bool operator==(const Lattice &Other) const {
96 return PersistentOrigins == Other.PersistentOrigins &&
97 BlockLocalOrigins == Other.BlockLocalOrigins;
98 }
99 bool operator!=(const Lattice &Other) const { return !(*this == Other); }
100
101 void dump(llvm::raw_ostream &OS) const {
102 OS << "LoanPropagationLattice State:\n";
103 OS << " Persistent Origins:\n";
104 if (PersistentOrigins.isEmpty())
105 OS << " <empty>\n";
106 for (const auto &Entry : PersistentOrigins) {
107 if (Entry.second.isEmpty())
108 OS << " Origin " << Entry.first << " contains no loans\n";
109 for (const LoanID &LID : Entry.second)
110 OS << " Origin " << Entry.first << " contains Loan " << LID << "\n";
111 }
112 OS << " Block-Local Origins:\n";
113 if (BlockLocalOrigins.isEmpty())
114 OS << " <empty>\n";
115 for (const auto &Entry : BlockLocalOrigins) {
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 }
122};
123
124class AnalysisImpl
125 : public DataflowAnalysis<AnalysisImpl, Lattice, Direction::Forward> {
126public:
127 AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
128 OriginLoanMap::Factory &OriginLoanMapFactory,
129 LoanSet::Factory &LoanSetFactory)
130 : DataflowAnalysis(C, AC, F), OriginLoanMapFactory(OriginLoanMapFactory),
131 LoanSetFactory(LoanSetFactory),
132 PersistentOrigins(computePersistentOrigins(FactMgr: F, C)) {}
133
134 using Base::transfer;
135
136 StringRef getAnalysisName() const { return "LoanPropagation"; }
137
138 Lattice getInitialState() { return Lattice{}; }
139
140 /// Merges two lattices by taking the union of loans for each origin.
141 /// Only persistent origins are joined; block-local origins are discarded.
142 Lattice join(Lattice A, Lattice B) {
143 OriginLoanMap JoinedOrigins = utils::join(
144 A: A.PersistentOrigins, B: B.PersistentOrigins, F&: OriginLoanMapFactory,
145 JoinValues: [&](const LoanSet *S1, const LoanSet *S2) {
146 assert((S1 || S2) && "unexpectedly merging 2 empty sets");
147 if (!S1)
148 return *S2;
149 if (!S2)
150 return *S1;
151 return utils::join(A: *S1, B: *S2, F&: LoanSetFactory);
152 },
153 // Asymmetric join is a performance win. For origins present only on one
154 // branch, the loan set can be carried over as-is.
155 Kind: utils::JoinKind::Asymmetric);
156 return Lattice(JoinedOrigins, OriginLoanMapFactory.getEmptyMap());
157 }
158
159 /// A new loan is issued to the origin. Old loans are erased.
160 Lattice transfer(Lattice In, const IssueFact &F) {
161 OriginID OID = F.getOriginID();
162 LoanID LID = F.getLoanID();
163 LoanSet NewLoans = LoanSetFactory.add(Old: LoanSetFactory.getEmptySet(), V: LID);
164 return setLoans(L: In, OID, Loans: NewLoans);
165 }
166
167 /// A flow from source to destination. If `KillDest` is true, this replaces
168 /// the destination's loans with the source's. Otherwise, the source's loans
169 /// are merged into the destination's.
170 Lattice transfer(Lattice In, const OriginFlowFact &F) {
171 OriginID DestOID = F.getDestOriginID();
172 OriginID SrcOID = F.getSrcOriginID();
173
174 LoanSet DestLoans =
175 F.getKillDest() ? LoanSetFactory.getEmptySet() : getLoans(L: In, OID: DestOID);
176 LoanSet SrcLoans = getLoans(L: In, OID: SrcOID);
177 LoanSet MergedLoans = utils::join(A: DestLoans, B: SrcLoans, F&: LoanSetFactory);
178
179 return setLoans(L: In, OID: DestOID, Loans: MergedLoans);
180 }
181
182 LoanSet getLoans(OriginID OID, ProgramPoint P) const {
183 return getLoans(L: getState(P), OID);
184 }
185
186private:
187 /// Returns true if the origin is persistent (referenced in multiple blocks).
188 bool isPersistent(OriginID OID) const {
189 return PersistentOrigins.test(Idx: OID.Value);
190 }
191
192 Lattice setLoans(Lattice L, OriginID OID, LoanSet Loans) {
193 if (isPersistent(OID))
194 return Lattice(OriginLoanMapFactory.add(Old: L.PersistentOrigins, K: OID, D: Loans),
195 L.BlockLocalOrigins);
196 return Lattice(L.PersistentOrigins,
197 OriginLoanMapFactory.add(Old: L.BlockLocalOrigins, K: OID, D: Loans));
198 }
199
200 LoanSet getLoans(Lattice L, OriginID OID) const {
201 const OriginLoanMap *Map =
202 isPersistent(OID) ? &L.PersistentOrigins : &L.BlockLocalOrigins;
203 if (auto *Loans = Map->lookup(K: OID))
204 return *Loans;
205 return LoanSetFactory.getEmptySet();
206 }
207
208 OriginLoanMap::Factory &OriginLoanMapFactory;
209 LoanSet::Factory &LoanSetFactory;
210 /// Boolean vector indexed by origin ID. If true, the origin appears in
211 /// multiple basic blocks and must participate in join operations. If false,
212 /// the origin is block-local and can be discarded at block boundaries.
213 llvm::BitVector PersistentOrigins;
214};
215} // namespace
216
217class LoanPropagationAnalysis::Impl final : public AnalysisImpl {
218 using AnalysisImpl::AnalysisImpl;
219};
220
221LoanPropagationAnalysis::LoanPropagationAnalysis(
222 const CFG &C, AnalysisDeclContext &AC, FactManager &F,
223 OriginLoanMap::Factory &OriginLoanMapFactory,
224 LoanSet::Factory &LoanSetFactory)
225 : PImpl(std::make_unique<Impl>(args: C, args&: AC, args&: F, args&: OriginLoanMapFactory,
226 args&: LoanSetFactory)) {
227 PImpl->run();
228}
229
230LoanPropagationAnalysis::~LoanPropagationAnalysis() = default;
231
232LoanSet LoanPropagationAnalysis::getLoans(OriginID OID, ProgramPoint P) const {
233 return PImpl->getLoans(OID, P);
234}
235} // namespace clang::lifetimes::internal
236