1//===- LiveOrigins.cpp - Live Origins 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
9#include "clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h"
10#include "Dataflow.h"
11#include "clang/Analysis/Analyses/LifetimeSafety/Facts.h"
12#include "llvm/Support/ErrorHandling.h"
13
14namespace clang::lifetimes::internal {
15namespace {
16
17/// The dataflow lattice for origin liveness analysis.
18/// It tracks which origins are live, why they're live (which UseFact),
19/// and the confidence level of that liveness.
20struct Lattice {
21 /// Origins referenced from more than one block. Participates in joins.
22 LivenessMap Persistent;
23 /// Origins confined to a single block. Discarded at block boundaries.
24 LivenessMap BlockLocal;
25
26 Lattice() : Persistent(nullptr), BlockLocal(nullptr) {};
27
28 Lattice(LivenessMap Persistent, LivenessMap BlockLocal)
29 : Persistent(Persistent), BlockLocal(BlockLocal) {}
30
31 bool operator==(const Lattice &Other) const {
32 return Persistent == Other.Persistent && BlockLocal == Other.BlockLocal;
33 }
34
35 bool operator!=(const Lattice &Other) const { return !(*this == Other); }
36
37 void dump(llvm::raw_ostream &OS, const OriginManager &OM) const {
38 if (Persistent.isEmpty() && BlockLocal.isEmpty())
39 OS << " <empty>\n";
40 for (const LivenessMap &Live : {Persistent, BlockLocal})
41 for (const auto &Entry : Live) {
42 OriginID OID = Entry.first;
43 const LivenessInfo &Info = Entry.second;
44 OS << " ";
45 OM.dump(OID, OS);
46 OS << " is ";
47 switch (Info.Kind) {
48 case LivenessKind::Must:
49 OS << "definitely";
50 break;
51 case LivenessKind::Maybe:
52 OS << "maybe";
53 break;
54 case LivenessKind::Dead:
55 llvm_unreachable("liveness kind of live origins should not be dead.");
56 }
57 OS << " live at this point\n";
58 }
59 }
60};
61
62static SourceLocation GetFactLoc(CausingFactType F) {
63 if (const auto *UF = F.dyn_cast<const UseFact *>())
64 return UF->getUseExpr()->getExprLoc();
65 if (const auto *OEF = F.dyn_cast<const OriginEscapesFact *>()) {
66 if (auto *ReturnEsc = dyn_cast<ReturnEscapeFact>(Val: OEF))
67 return ReturnEsc->getReturnExpr()->getExprLoc();
68 if (auto *FieldEsc = dyn_cast<FieldEscapeFact>(Val: OEF))
69 return FieldEsc->getFieldDecl()->getLocation();
70 if (auto *GlobalEsc = dyn_cast<GlobalEscapeFact>(Val: OEF))
71 return GlobalEsc->getGlobal()->getLocation();
72 }
73 llvm_unreachable("unhandled causing fact in PointerUnion");
74}
75
76/// The analysis that tracks which origins are live, with granular information
77/// about the causing use fact and confidence level. This is a backward
78/// analysis.
79class AnalysisImpl
80 : public DataflowAnalysis<AnalysisImpl, Lattice, Direction::Backward> {
81
82public:
83 AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
84 LivenessMap::Factory &SF)
85 : DataflowAnalysis(C, AC, F), FactMgr(F), Factory(SF),
86 PersistentOrigins(F.getPersistentOrigins()) {}
87 using DataflowAnalysis<AnalysisImpl, Lattice, Direction::Backward>::transfer;
88
89 StringRef getAnalysisName() const { return "LiveOrigins"; }
90
91 Lattice getInitialState() {
92 return Lattice(Factory.getEmptyMap(), Factory.getEmptyMap());
93 }
94
95 /// An origin referenced from a single block need not be live outside it.
96 ///
97 /// Loans only ever enter an origin through an `IssueFact` or an
98 /// `OriginFlowFact` naming it as the destination, and both would make the
99 /// origin persistent if they lived in another block. So a block-local origin
100 /// holds no loans anywhere outside its own block, and every consumer of
101 /// liveness intersects it with the origin's loans. Dropping these here keeps
102 /// them out of the joins and out of the block-entry state comparison.
103 Lattice transferAtBlockExit(Lattice L) {
104 return Lattice(L.Persistent, Factory.getEmptyMap());
105 }
106
107 /// Merges two lattices by combining liveness information.
108 /// When the same origin has different confidence levels, we take the lower
109 /// one.
110 Lattice join(Lattice L1, Lattice L2) const {
111 assert(L1.BlockLocal.isEmpty() && L2.BlockLocal.isEmpty() &&
112 "block-local origins must not reach a block boundary");
113 // Take the earliest Fact to make the join hermetic and commutative.
114 auto CombineCausingFact = [](CausingFactType A,
115 CausingFactType B) -> CausingFactType {
116 if (!A)
117 return B;
118 if (!B)
119 return A;
120 return GetFactLoc(F: A) < GetFactLoc(F: B) ? A : B;
121 };
122 auto CombineLivenessKind = [](LivenessKind K1,
123 LivenessKind K2) -> LivenessKind {
124 assert(K1 != LivenessKind::Dead && "LivenessKind should not be dead.");
125 assert(K2 != LivenessKind::Dead && "LivenessKind should not be dead.");
126 // Only return "Must" if both paths are "Must", otherwise Maybe.
127 if (K1 == LivenessKind::Must && K2 == LivenessKind::Must)
128 return LivenessKind::Must;
129 return LivenessKind::Maybe;
130 };
131 auto CombineLivenessInfo = [&](const LivenessInfo *L1,
132 const LivenessInfo *L2) -> LivenessInfo {
133 assert((L1 || L2) && "unexpectedly merging 2 empty sets");
134 if (!L1)
135 return LivenessInfo(L2->CausingFact, LivenessKind::Maybe);
136 if (!L2)
137 return LivenessInfo(L1->CausingFact, LivenessKind::Maybe);
138 return LivenessInfo(CombineCausingFact(L1->CausingFact, L2->CausingFact),
139 CombineLivenessKind(L1->Kind, L2->Kind));
140 };
141 // A symmetric join is required here. If an origin is live on one branch but
142 // not the other, its confidence must be demoted to `Maybe`.
143 LivenessMap Joined =
144 utils::join(A: L1.Persistent, B: L2.Persistent, F&: Factory, JoinValues: CombineLivenessInfo,
145 Kind: utils::JoinKind::Symmetric);
146 return Lattice(Joined, Factory.getEmptyMap());
147 }
148
149 /// A read operation makes the origin live with definite confidence, as it
150 /// dominates this program point. A write operation kills the liveness of
151 /// the origin since it overwrites the value.
152 Lattice transfer(Lattice In, const UseFact &UF) {
153 Lattice Out = In;
154 for (const OriginList *Cur = UF.getUsedOrigins(); Cur;
155 Cur = Cur->peelOuterOrigin()) {
156 OriginID OID = Cur->getOuterOriginID();
157 // Write kills liveness.
158 if (UF.isWritten())
159 Out = removeLive(L: Out, OID);
160 else
161 // Read makes origin live with definite confidence (dominates this
162 // point).
163 Out = addLive(L: Out, OID, Info: LivenessInfo(&UF, LivenessKind::Must));
164 }
165 return Out;
166 }
167
168 /// An escaping origin (e.g., via return) makes the origin live with definite
169 /// confidence, as it dominates this program point.
170 Lattice transfer(Lattice In, const OriginEscapesFact &OEF) {
171 return addLive(L: In, OID: OEF.getEscapedOriginID(),
172 Info: LivenessInfo(&OEF, LivenessKind::Must));
173 }
174
175 /// Issuing a new loan to an origin kills its liveness.
176 Lattice transfer(Lattice In, const IssueFact &IF) {
177 return removeLive(L: In, OID: IF.getOriginID());
178 }
179
180 /// An OriginFlow kills the liveness of the destination origin if `KillDest`
181 /// is true. Otherwise, it propagates liveness from destination to source.
182 Lattice transfer(Lattice In, const OriginFlowFact &OF) {
183 Lattice Out = In;
184 OriginID Dest = OF.getDestOriginID();
185 // If the destination of the flow is live, the source of the flow must also
186 // be marked live before this point as its value will flow into the
187 // destination.
188 if (const LivenessInfo *DestInfo = lookupLive(L: In, OID: Dest))
189 Out = addLive(L: Out, OID: OF.getSrcOriginID(), Info: *DestInfo);
190 if (OF.getKillDest())
191 Out = removeLive(L: Out, OID: Dest);
192 return Out;
193 }
194
195 Lattice transfer(Lattice In, const KillOriginFact &F) {
196 return removeLive(L: In, OID: F.getKilledOrigin());
197 }
198
199 Lattice transfer(Lattice In, const ExpireFact &F) {
200 if (auto OID = F.getOriginID())
201 return removeLive(L: In, OID: *OID);
202 return In;
203 }
204
205 LiveOriginSet getLiveOriginsAt(ProgramPoint P) const {
206 Lattice L = getState(P);
207 return LiveOriginSet{.Persistent: L.Persistent, .BlockLocal: L.BlockLocal};
208 }
209
210 // Dump liveness values on all test points in the program.
211 void dump(llvm::raw_ostream &OS,
212 const llvm::StringMap<ProgramPoint> &TestPoints) const {
213 llvm::dbgs() << "==========================================\n";
214 llvm::dbgs() << getAnalysisName() << " results:\n";
215 llvm::dbgs() << "==========================================\n";
216 for (const auto &Entry : TestPoints) {
217 OS << "TestPoint: " << Entry.getKey() << "\n";
218 getState(P: Entry.getValue()).dump(OS, OM: FactMgr.getOriginMgr());
219 }
220 }
221
222private:
223 /// Routes an origin to the half of the lattice it belongs to.
224 bool isPersistent(OriginID OID) const {
225 return PersistentOrigins.test(Idx: OID.Value);
226 }
227
228 Lattice addLive(Lattice L, OriginID OID, LivenessInfo Info) {
229 if (isPersistent(OID))
230 return Lattice(Factory.add(Old: L.Persistent, K: OID, D: Info), L.BlockLocal);
231 return Lattice(L.Persistent, Factory.add(Old: L.BlockLocal, K: OID, D: Info));
232 }
233
234 Lattice removeLive(Lattice L, OriginID OID) {
235 if (isPersistent(OID))
236 return Lattice(Factory.remove(Old: L.Persistent, K: OID), L.BlockLocal);
237 return Lattice(L.Persistent, Factory.remove(Old: L.BlockLocal, K: OID));
238 }
239
240 const LivenessInfo *lookupLive(const Lattice &L, OriginID OID) const {
241 return isPersistent(OID) ? L.Persistent.lookup(K: OID)
242 : L.BlockLocal.lookup(K: OID);
243 }
244
245 FactManager &FactMgr;
246 LivenessMap::Factory &Factory;
247 /// Origins referenced from more than one basic block; see
248 /// `FactManager::getPersistentOrigins`.
249 const llvm::BitVector &PersistentOrigins;
250};
251} // namespace
252
253// PImpl wrapper implementation
254class LiveOriginsAnalysis::Impl : public AnalysisImpl {
255 using AnalysisImpl::AnalysisImpl;
256};
257
258LiveOriginsAnalysis::LiveOriginsAnalysis(const CFG &C, AnalysisDeclContext &AC,
259 FactManager &F,
260 LivenessMap::Factory &SF)
261 : PImpl(std::make_unique<Impl>(args: C, args&: AC, args&: F, args&: SF)) {
262 PImpl->run();
263}
264
265LiveOriginsAnalysis::~LiveOriginsAnalysis() = default;
266
267LiveOriginSet LiveOriginsAnalysis::getLiveOriginsAt(ProgramPoint P) const {
268 return PImpl->getLiveOriginsAt(P);
269}
270
271void LiveOriginsAnalysis::dump(
272 llvm::raw_ostream &OS,
273 const llvm::StringMap<ProgramPoint> &TestPoints) const {
274 PImpl->dump(OS, TestPoints);
275}
276} // namespace clang::lifetimes::internal
277