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 }
66 llvm_unreachable("unhandled causing fact in PointerUnion");
67}
68
69/// The analysis that tracks which origins are live, with granular information
70/// about the causing use fact and confidence level. This is a backward
71/// analysis.
72class AnalysisImpl
73 : public DataflowAnalysis<AnalysisImpl, Lattice, Direction::Backward> {
74
75public:
76 AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
77 LivenessMap::Factory &SF)
78 : DataflowAnalysis(C, AC, F), FactMgr(F), Factory(SF) {}
79 using DataflowAnalysis<AnalysisImpl, Lattice, Direction::Backward>::transfer;
80
81 StringRef getAnalysisName() const { return "LiveOrigins"; }
82
83 Lattice getInitialState() { return Lattice(Factory.getEmptyMap()); }
84
85 /// Merges two lattices by combining liveness information.
86 /// When the same origin has different confidence levels, we take the lower
87 /// one.
88 Lattice join(Lattice L1, Lattice L2) const {
89 LivenessMap Merged = L1.LiveOrigins;
90 // Take the earliest Fact to make the join hermetic and commutative.
91 auto CombineCausingFact = [](CausingFactType A,
92 CausingFactType B) -> CausingFactType {
93 if (!A)
94 return B;
95 if (!B)
96 return A;
97 return GetFactLoc(F: A) < GetFactLoc(F: B) ? A : B;
98 };
99 auto CombineLivenessKind = [](LivenessKind K1,
100 LivenessKind K2) -> LivenessKind {
101 assert(K1 != LivenessKind::Dead && "LivenessKind should not be dead.");
102 assert(K2 != LivenessKind::Dead && "LivenessKind should not be dead.");
103 // Only return "Must" if both paths are "Must", otherwise Maybe.
104 if (K1 == LivenessKind::Must && K2 == LivenessKind::Must)
105 return LivenessKind::Must;
106 return LivenessKind::Maybe;
107 };
108 auto CombineLivenessInfo = [&](const LivenessInfo *L1,
109 const LivenessInfo *L2) -> LivenessInfo {
110 assert((L1 || L2) && "unexpectedly merging 2 empty sets");
111 if (!L1)
112 return LivenessInfo(L2->CausingFact, LivenessKind::Maybe);
113 if (!L2)
114 return LivenessInfo(L1->CausingFact, LivenessKind::Maybe);
115 return LivenessInfo(CombineCausingFact(L1->CausingFact, L2->CausingFact),
116 CombineLivenessKind(L1->Kind, L2->Kind));
117 };
118 return Lattice(utils::join(
119 A: L1.LiveOrigins, B: L2.LiveOrigins, F&: Factory, JoinValues: CombineLivenessInfo,
120 // A symmetric join is required here. If an origin is live on one
121 // branch but not the other, its confidence must be demoted to `Maybe`.
122 Kind: utils::JoinKind::Symmetric));
123 }
124
125 /// A read operation makes the origin live with definite confidence, as it
126 /// dominates this program point. A write operation kills the liveness of
127 /// the origin since it overwrites the value.
128 Lattice transfer(Lattice In, const UseFact &UF) {
129 Lattice Out = In;
130 for (const OriginList *Cur = UF.getUsedOrigins(); Cur;
131 Cur = Cur->peelOuterOrigin()) {
132 OriginID OID = Cur->getOuterOriginID();
133 // Write kills liveness.
134 if (UF.isWritten()) {
135 Out = Lattice(Factory.remove(Old: Out.LiveOrigins, K: OID));
136 } else {
137 // Read makes origin live with definite confidence (dominates this
138 // point).
139 Out = Lattice(Factory.add(Old: Out.LiveOrigins, K: OID,
140 D: LivenessInfo(&UF, LivenessKind::Must)));
141 }
142 }
143 return Out;
144 }
145
146 /// An escaping origin (e.g., via return) makes the origin live with definite
147 /// confidence, as it dominates this program point.
148 Lattice transfer(Lattice In, const OriginEscapesFact &OEF) {
149 OriginID OID = OEF.getEscapedOriginID();
150 return Lattice(Factory.add(Old: In.LiveOrigins, K: OID,
151 D: LivenessInfo(&OEF, LivenessKind::Must)));
152 }
153
154 /// Issuing a new loan to an origin kills its liveness.
155 Lattice transfer(Lattice In, const IssueFact &IF) {
156 return Lattice(Factory.remove(Old: In.LiveOrigins, K: IF.getOriginID()));
157 }
158
159 /// An OriginFlow kills the liveness of the destination origin if `KillDest`
160 /// is true. Otherwise, it propagates liveness from destination to source.
161 Lattice transfer(Lattice In, const OriginFlowFact &OF) {
162 if (!OF.getKillDest())
163 return In;
164 return Lattice(Factory.remove(Old: In.LiveOrigins, K: OF.getDestOriginID()));
165 }
166
167 LivenessMap getLiveOriginsAt(ProgramPoint P) const {
168 return getState(P).LiveOrigins;
169 }
170
171 // Dump liveness values on all test points in the program.
172 void dump(llvm::raw_ostream &OS,
173 const llvm::StringMap<ProgramPoint> &TestPoints) const {
174 llvm::dbgs() << "==========================================\n";
175 llvm::dbgs() << getAnalysisName() << " results:\n";
176 llvm::dbgs() << "==========================================\n";
177 for (const auto &Entry : TestPoints) {
178 OS << "TestPoint: " << Entry.getKey() << "\n";
179 getState(P: Entry.getValue()).dump(OS, OM: FactMgr.getOriginMgr());
180 }
181 }
182
183private:
184 FactManager &FactMgr;
185 LivenessMap::Factory &Factory;
186};
187} // namespace
188
189// PImpl wrapper implementation
190class LiveOriginsAnalysis::Impl : public AnalysisImpl {
191 using AnalysisImpl::AnalysisImpl;
192};
193
194LiveOriginsAnalysis::LiveOriginsAnalysis(const CFG &C, AnalysisDeclContext &AC,
195 FactManager &F,
196 LivenessMap::Factory &SF)
197 : PImpl(std::make_unique<Impl>(args: C, args&: AC, args&: F, args&: SF)) {
198 PImpl->run();
199}
200
201LiveOriginsAnalysis::~LiveOriginsAnalysis() = default;
202
203LivenessMap LiveOriginsAnalysis::getLiveOriginsAt(ProgramPoint P) const {
204 return PImpl->getLiveOriginsAt(P);
205}
206
207void LiveOriginsAnalysis::dump(
208 llvm::raw_ostream &OS,
209 const llvm::StringMap<ProgramPoint> &TestPoints) const {
210 PImpl->dump(OS, TestPoints);
211}
212} // namespace clang::lifetimes::internal
213