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