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 LivenessMap LiveOrigins;
22
23 Lattice() : LiveOrigins(nullptr) {};
24
25 explicit Lattice(LivenessMap L) : LiveOrigins(L) {}
26
27 bool operator==(const Lattice &Other) const {
28 return LiveOrigins == Other.LiveOrigins;
29 }
30
31 bool operator!=(const Lattice &Other) const { return !(*this == Other); }
32
33 void dump(llvm::raw_ostream &OS, const OriginManager &OM) const {
34 if (LiveOrigins.isEmpty())
35 OS << " <empty>\n";
36 for (const auto &Entry : LiveOrigins) {
37 OriginID OID = Entry.first;
38 const LivenessInfo &Info = Entry.second;
39 OS << " ";
40 OM.dump(OID, OS);
41 OS << " is ";
42 switch (Info.Kind) {
43 case LivenessKind::Must:
44 OS << "definitely";
45 break;
46 case LivenessKind::Maybe:
47 OS << "maybe";
48 break;
49 case LivenessKind::Dead:
50 llvm_unreachable("liveness kind of live origins should not be dead.");
51 }
52 OS << " live at this point\n";
53 }
54 }
55};
56
57static SourceLocation GetFactLoc(CausingFactType F) {
58 if (const auto *UF = F.dyn_cast<const UseFact *>())
59 return UF->getUseExpr()->getExprLoc();
60 if (const auto *OEF = F.dyn_cast<const OriginEscapesFact *>()) {
61 if (auto *ReturnEsc = dyn_cast<ReturnEscapeFact>(Val: OEF))
62 return ReturnEsc->getReturnExpr()->getExprLoc();
63 if (auto *FieldEsc = dyn_cast<FieldEscapeFact>(Val: OEF))
64 return FieldEsc->getFieldDecl()->getLocation();
65 if (auto *GlobalEsc = dyn_cast<GlobalEscapeFact>(Val: OEF))
66 return GlobalEsc->getGlobal()->getLocation();
67 }
68 llvm_unreachable("unhandled causing fact in PointerUnion");
69}
70
71/// The analysis that tracks which origins are live, with granular information
72/// about the causing use fact and confidence level. This is a backward
73/// analysis.
74class AnalysisImpl
75 : public DataflowAnalysis<AnalysisImpl, Lattice, Direction::Backward> {
76
77public:
78 AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
79 LivenessMap::Factory &SF)
80 : DataflowAnalysis(C, AC, F), FactMgr(F), Factory(SF) {}
81 using DataflowAnalysis<AnalysisImpl, Lattice, Direction::Backward>::transfer;
82
83 StringRef getAnalysisName() const { return "LiveOrigins"; }
84
85 Lattice getInitialState() { return Lattice(Factory.getEmptyMap()); }
86
87 /// Merges two lattices by combining liveness information.
88 /// When the same origin has different confidence levels, we take the lower
89 /// one.
90 Lattice join(Lattice L1, Lattice L2) const {
91 LivenessMap Merged = L1.LiveOrigins;
92 // Take the earliest Fact to make the join hermetic and commutative.
93 auto CombineCausingFact = [](CausingFactType A,
94 CausingFactType B) -> CausingFactType {
95 if (!A)
96 return B;
97 if (!B)
98 return A;
99 return GetFactLoc(F: A) < GetFactLoc(F: B) ? A : B;
100 };
101 auto CombineLivenessKind = [](LivenessKind K1,
102 LivenessKind K2) -> LivenessKind {
103 assert(K1 != LivenessKind::Dead && "LivenessKind should not be dead.");
104 assert(K2 != LivenessKind::Dead && "LivenessKind should not be dead.");
105 // Only return "Must" if both paths are "Must", otherwise Maybe.
106 if (K1 == LivenessKind::Must && K2 == LivenessKind::Must)
107 return LivenessKind::Must;
108 return LivenessKind::Maybe;
109 };
110 auto CombineLivenessInfo = [&](const LivenessInfo *L1,
111 const LivenessInfo *L2) -> LivenessInfo {
112 assert((L1 || L2) && "unexpectedly merging 2 empty sets");
113 if (!L1)
114 return LivenessInfo(L2->CausingFact, LivenessKind::Maybe);
115 if (!L2)
116 return LivenessInfo(L1->CausingFact, LivenessKind::Maybe);
117 return LivenessInfo(CombineCausingFact(L1->CausingFact, L2->CausingFact),
118 CombineLivenessKind(L1->Kind, L2->Kind));
119 };
120 return Lattice(utils::join(
121 A: L1.LiveOrigins, B: L2.LiveOrigins, F&: Factory, JoinValues: CombineLivenessInfo,
122 // A symmetric join is required here. If an origin is live on one
123 // branch but not the other, its confidence must be demoted to `Maybe`.
124 Kind: utils::JoinKind::Symmetric));
125 }
126
127 /// A read operation makes the origin live with definite confidence, as it
128 /// dominates this program point. A write operation kills the liveness of
129 /// the origin since it overwrites the value.
130 Lattice transfer(Lattice In, const UseFact &UF) {
131 Lattice Out = In;
132 for (const OriginList *Cur = UF.getUsedOrigins(); Cur;
133 Cur = Cur->peelOuterOrigin()) {
134 OriginID OID = Cur->getOuterOriginID();
135 // Write kills liveness.
136 if (UF.isWritten()) {
137 Out = Lattice(Factory.remove(Old: Out.LiveOrigins, K: OID));
138 } else {
139 // Read makes origin live with definite confidence (dominates this
140 // point).
141 Out = Lattice(Factory.add(Old: Out.LiveOrigins, K: OID,
142 D: LivenessInfo(&UF, LivenessKind::Must)));
143 }
144 }
145 return Out;
146 }
147
148 /// An escaping origin (e.g., via return) makes the origin live with definite
149 /// confidence, as it dominates this program point.
150 Lattice transfer(Lattice In, const OriginEscapesFact &OEF) {
151 OriginID OID = OEF.getEscapedOriginID();
152 return Lattice(Factory.add(Old: In.LiveOrigins, K: OID,
153 D: LivenessInfo(&OEF, LivenessKind::Must)));
154 }
155
156 /// Issuing a new loan to an origin kills its liveness.
157 Lattice transfer(Lattice In, const IssueFact &IF) {
158 return Lattice(Factory.remove(Old: In.LiveOrigins, K: IF.getOriginID()));
159 }
160
161 /// An OriginFlow kills the liveness of the destination origin if `KillDest`
162 /// is true. Otherwise, it propagates liveness from destination to source.
163 Lattice transfer(Lattice In, const OriginFlowFact &OF) {
164 Lattice Out = In;
165 OriginID Dest = OF.getDestOriginID();
166 OriginID Src = OF.getSrcOriginID();
167 // If the destination of the flow is live, the source of the flow must also
168 // be marked live before this point as its value will flow into the
169 // destination.
170 if (In.LiveOrigins.contains(K: Dest)) {
171 const LivenessInfo *DestInfo = In.LiveOrigins.lookup(K: Dest);
172 assert(DestInfo);
173 Out = Lattice(Factory.add(Old: Out.LiveOrigins, K: Src, D: *DestInfo));
174 }
175 if (OF.getKillDest())
176 Out = Lattice(Factory.remove(Old: Out.LiveOrigins, K: Dest));
177 return Out;
178 }
179
180 Lattice transfer(Lattice In, const KillOriginFact &F) {
181 return Lattice(Factory.remove(Old: In.LiveOrigins, K: F.getKilledOrigin()));
182 }
183
184 Lattice transfer(Lattice In, const ExpireFact &F) {
185 if (auto OID = F.getOriginID())
186 return Lattice(Factory.remove(Old: In.LiveOrigins, K: *OID));
187 return In;
188 }
189
190 LivenessMap getLiveOriginsAt(ProgramPoint P) const {
191 return getState(P).LiveOrigins;
192 }
193
194 // Dump liveness values on all test points in the program.
195 void dump(llvm::raw_ostream &OS,
196 const llvm::StringMap<ProgramPoint> &TestPoints) const {
197 llvm::dbgs() << "==========================================\n";
198 llvm::dbgs() << getAnalysisName() << " results:\n";
199 llvm::dbgs() << "==========================================\n";
200 for (const auto &Entry : TestPoints) {
201 OS << "TestPoint: " << Entry.getKey() << "\n";
202 getState(P: Entry.getValue()).dump(OS, OM: FactMgr.getOriginMgr());
203 }
204 }
205
206private:
207 FactManager &FactMgr;
208 LivenessMap::Factory &Factory;
209};
210} // namespace
211
212// PImpl wrapper implementation
213class LiveOriginsAnalysis::Impl : public AnalysisImpl {
214 using AnalysisImpl::AnalysisImpl;
215};
216
217LiveOriginsAnalysis::LiveOriginsAnalysis(const CFG &C, AnalysisDeclContext &AC,
218 FactManager &F,
219 LivenessMap::Factory &SF)
220 : PImpl(std::make_unique<Impl>(args: C, args&: AC, args&: F, args&: SF)) {
221 PImpl->run();
222}
223
224LiveOriginsAnalysis::~LiveOriginsAnalysis() = default;
225
226LivenessMap LiveOriginsAnalysis::getLiveOriginsAt(ProgramPoint P) const {
227 return PImpl->getLiveOriginsAt(P);
228}
229
230void LiveOriginsAnalysis::dump(
231 llvm::raw_ostream &OS,
232 const llvm::StringMap<ProgramPoint> &TestPoints) const {
233 PImpl->dump(OS, TestPoints);
234}
235} // namespace clang::lifetimes::internal
236