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 if (!OF.getKillDest())
165 return In;
166 return Lattice(Factory.remove(Old: In.LiveOrigins, K: OF.getDestOriginID()));
167 }
168
169 Lattice transfer(Lattice In, const ExpireFact &F) {
170 if (auto OID = F.getOriginID())
171 return Lattice(Factory.remove(Old: In.LiveOrigins, K: *OID));
172 return In;
173 }
174
175 LivenessMap getLiveOriginsAt(ProgramPoint P) const {
176 return getState(P).LiveOrigins;
177 }
178
179 // Dump liveness values on all test points in the program.
180 void dump(llvm::raw_ostream &OS,
181 const llvm::StringMap<ProgramPoint> &TestPoints) const {
182 llvm::dbgs() << "==========================================\n";
183 llvm::dbgs() << getAnalysisName() << " results:\n";
184 llvm::dbgs() << "==========================================\n";
185 for (const auto &Entry : TestPoints) {
186 OS << "TestPoint: " << Entry.getKey() << "\n";
187 getState(P: Entry.getValue()).dump(OS, OM: FactMgr.getOriginMgr());
188 }
189 }
190
191private:
192 FactManager &FactMgr;
193 LivenessMap::Factory &Factory;
194};
195} // namespace
196
197// PImpl wrapper implementation
198class LiveOriginsAnalysis::Impl : public AnalysisImpl {
199 using AnalysisImpl::AnalysisImpl;
200};
201
202LiveOriginsAnalysis::LiveOriginsAnalysis(const CFG &C, AnalysisDeclContext &AC,
203 FactManager &F,
204 LivenessMap::Factory &SF)
205 : PImpl(std::make_unique<Impl>(args: C, args&: AC, args&: F, args&: SF)) {
206 PImpl->run();
207}
208
209LiveOriginsAnalysis::~LiveOriginsAnalysis() = default;
210
211LivenessMap LiveOriginsAnalysis::getLiveOriginsAt(ProgramPoint P) const {
212 return PImpl->getLiveOriginsAt(P);
213}
214
215void LiveOriginsAnalysis::dump(
216 llvm::raw_ostream &OS,
217 const llvm::StringMap<ProgramPoint> &TestPoints) const {
218 PImpl->dump(OS, TestPoints);
219}
220} // namespace clang::lifetimes::internal
221