1//===- Facts.cpp - Lifetime Analysis Facts Implementation -------*- 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/Facts.h"
10#include "clang/AST/Decl.h"
11#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h"
12#include "clang/Analysis/Analyses/PostOrderCFGView.h"
13#include "llvm/Support/TimeProfiler.h"
14
15namespace clang::lifetimes::internal {
16
17void FactManager::computePersistentOrigins(const CFG &Cfg) {
18 llvm::TimeTraceScope TimeProfile("ComputePersistentOrigins");
19
20 unsigned NumOrigins = OriginMgr.getNumOrigins();
21 PersistentOrigins.resize(N: NumOrigins);
22 llvm::SmallVector<const CFGBlock *> OriginToFirstSeenBlock(NumOrigins,
23 nullptr);
24 for (const CFGBlock *B : Cfg) {
25 for (const Fact *F : getFacts(B)) {
26 auto CheckOrigin = [&](OriginID OID) {
27 if (PersistentOrigins.test(Idx: OID.Value))
28 return;
29 auto &FirstSeenBlock = OriginToFirstSeenBlock[OID.Value];
30 if (FirstSeenBlock == nullptr)
31 FirstSeenBlock = B;
32 if (FirstSeenBlock != B) {
33 // We saw this origin in more than one block.
34 PersistentOrigins.set(OID.Value);
35 }
36 };
37
38 switch (F->getKind()) {
39 case Fact::Kind::Issue:
40 CheckOrigin(F->getAs<IssueFact>()->getOriginID());
41 break;
42 case Fact::Kind::OriginFlow: {
43 const auto *OF = F->getAs<OriginFlowFact>();
44 CheckOrigin(OF->getDestOriginID());
45 CheckOrigin(OF->getSrcOriginID());
46 break;
47 }
48 case Fact::Kind::Use:
49 for (const OriginList *Cur = F->getAs<UseFact>()->getUsedOrigins(); Cur;
50 Cur = Cur->peelOuterOrigin())
51 CheckOrigin(Cur->getOuterOriginID());
52 break;
53 case Fact::Kind::KillOrigin:
54 CheckOrigin(F->getAs<KillOriginFact>()->getKilledOrigin());
55 break;
56 case Fact::Kind::OriginEscapes:
57 // An escaping origin is read at the exit block but defined earlier, so
58 // it spans blocks and must participate in joins.
59 CheckOrigin(F->getAs<OriginEscapesFact>()->getEscapedOriginID());
60 break;
61 // `Expire` and `InvalidateOrigin` only ever clear an origin, so
62 // misclassifying one is harmless: the clear becomes a no-op.
63 case Fact::Kind::MovedOrigin:
64 case Fact::Kind::Expire:
65 case Fact::Kind::TestPoint:
66 case Fact::Kind::InvalidateOrigin:
67 break;
68 }
69 }
70 }
71}
72
73void Fact::dump(llvm::raw_ostream &OS, const LoanManager &,
74 const OriginManager &, const LoanPropagationAnalysis *) const {
75 OS << "Fact (Kind: " << static_cast<int>(K) << ")\n";
76}
77
78void IssueFact::dump(llvm::raw_ostream &OS, const LoanManager &LM,
79 const OriginManager &OM,
80 const LoanPropagationAnalysis *) const {
81 OS << "Issue (";
82 LM.getLoan(ID: getLoanID())->dump(OS);
83 OS << ", ToOrigin: ";
84 OM.dump(OID: getOriginID(), OS);
85 OS << ")\n";
86}
87
88void ExpireFact::dump(llvm::raw_ostream &OS, const LoanManager &LM,
89 const OriginManager &OM,
90 const LoanPropagationAnalysis *LPA) const {
91 OS << "Expire (";
92 getAccessPath().dump(OS);
93 if (auto OID = getOriginID()) {
94 OS << ", Origin: ";
95 OM.dump(OID: *OID, OS);
96 }
97 OS << ")\n";
98}
99
100void OriginFlowFact::dump(llvm::raw_ostream &OS, const LoanManager &LM,
101 const OriginManager &OM,
102 const LoanPropagationAnalysis *LPA) const {
103 OS << "OriginFlow: \n";
104 OS << "\tDest: ";
105 OM.dump(OID: getDestOriginID(), OS);
106 if (LPA) {
107 LoanSet DestinationLoans = LPA->getLoans(OID: getDestOriginID(), P: this);
108 if (DestinationLoans.isEmpty())
109 OS << " has no loans";
110 else {
111 OS << " has loans to { ";
112 for (LoanID LID : DestinationLoans) {
113 LM.getLoan(ID: LID)->getAccessPath().dump(OS);
114 OS << " ";
115 }
116 OS << "}";
117 }
118 }
119 OS << "\n";
120 OS << "\tSrc: ";
121 OM.dump(OID: getSrcOriginID(), OS);
122 OS << (getKillDest() ? "" : ", Merge");
123 OS << "\n";
124}
125
126void MovedOriginFact::dump(llvm::raw_ostream &OS, const LoanManager &,
127 const OriginManager &OM,
128 const LoanPropagationAnalysis *) const {
129 OS << "MovedOrigins (";
130 OM.dump(OID: getMovedOrigin(), OS);
131 OS << ")\n";
132}
133
134void ReturnEscapeFact::dump(llvm::raw_ostream &OS, const LoanManager &,
135 const OriginManager &OM,
136 const LoanPropagationAnalysis *) const {
137 OS << "OriginEscapes (";
138 OM.dump(OID: getEscapedOriginID(), OS);
139 OS << ", via Return)\n";
140}
141
142void FieldEscapeFact::dump(llvm::raw_ostream &OS, const LoanManager &,
143 const OriginManager &OM,
144 const LoanPropagationAnalysis *) const {
145 OS << "OriginEscapes (";
146 OM.dump(OID: getEscapedOriginID(), OS);
147 OS << ", via Field)\n";
148}
149
150void GlobalEscapeFact::dump(llvm::raw_ostream &OS, const LoanManager &,
151 const OriginManager &OM,
152 const LoanPropagationAnalysis *) const {
153 OS << "OriginEscapes (";
154 OM.dump(OID: getEscapedOriginID(), OS);
155 OS << ", via Global)\n";
156}
157
158void ThisEscapeFact::dump(llvm::raw_ostream &OS, const LoanManager &,
159 const OriginManager &OM,
160 const LoanPropagationAnalysis *) const {
161 OS << "OriginEscapes (";
162 OM.dump(OID: getEscapedOriginID(), OS);
163 OS << ", via This)\n";
164}
165
166void ParamEscapeFact::dump(llvm::raw_ostream &OS, const LoanManager &,
167 const OriginManager &OM,
168 const LoanPropagationAnalysis *) const {
169 OS << "OriginEscapes (";
170 OM.dump(OID: getEscapedOriginID(), OS);
171 OS << ", via Param " << Param->getName() << ")\n";
172}
173
174void UseFact::dump(llvm::raw_ostream &OS, const LoanManager &,
175 const OriginManager &OM,
176 const LoanPropagationAnalysis *) const {
177 OS << "Use (";
178 size_t NumUsedOrigins = getUsedOrigins()->getLength();
179 size_t I = 0;
180 for (const OriginList *Cur = getUsedOrigins(); Cur;
181 Cur = Cur->peelOuterOrigin(), ++I) {
182 OM.dump(OID: Cur->getOuterOriginID(), OS);
183 if (I < NumUsedOrigins - 1)
184 OS << ", ";
185 }
186 OS << ")\n";
187}
188
189void InvalidateOriginFact::dump(llvm::raw_ostream &OS, const LoanManager &,
190 const OriginManager &OM,
191 const LoanPropagationAnalysis *) const {
192 OS << "InvalidateOrigin (";
193 OM.dump(OID: getInvalidatedOrigin(), OS);
194 OS << ")\n";
195}
196
197void TestPointFact::dump(llvm::raw_ostream &OS, const LoanManager &,
198 const OriginManager &,
199 const LoanPropagationAnalysis *) const {
200 OS << "TestPoint (Annotation: \"" << getAnnotation() << "\")\n";
201}
202
203void KillOriginFact::dump(llvm::raw_ostream &OS, const LoanManager &,
204 const OriginManager &OM,
205 const LoanPropagationAnalysis *) const {
206 OS << "KillOrigin (";
207 OM.dump(OID: getKilledOrigin(), OS);
208 OS << ")\n";
209}
210
211llvm::StringMap<ProgramPoint> FactManager::getTestPoints() const {
212 llvm::StringMap<ProgramPoint> AnnotationToPointMap;
213 for (const auto &BlockFacts : BlockToFacts) {
214 for (const Fact *F : BlockFacts) {
215 if (const auto *TPF = F->getAs<TestPointFact>()) {
216 StringRef PointName = TPF->getAnnotation();
217 assert(!AnnotationToPointMap.contains(PointName) &&
218 "more than one test points with the same name");
219 AnnotationToPointMap[PointName] = F;
220 }
221 }
222 }
223 return AnnotationToPointMap;
224}
225
226void FactManager::dump(const CFG &Cfg, AnalysisDeclContext &AC,
227 const LoanPropagationAnalysis *LPA) const {
228 llvm::dbgs() << "==========================================\n";
229 llvm::dbgs() << " Lifetime Analysis Facts:\n";
230 llvm::dbgs() << "==========================================\n";
231 if (const Decl *D = AC.getDecl())
232 if (const auto *ND = dyn_cast<NamedDecl>(Val: D))
233 llvm::dbgs() << "Function: " << ND->getQualifiedNameAsString() << "\n";
234 // Print blocks in the order as they appear in code for a stable ordering.
235 for (const CFGBlock *B : *AC.getAnalysis<PostOrderCFGView>()) {
236 llvm::dbgs() << " Block B" << B->getBlockID() << ":\n";
237 for (const Fact *F : getFacts(B)) {
238 llvm::dbgs() << " ";
239 F->dump(OS&: llvm::dbgs(), LoanMgr, OriginMgr, LPA);
240 }
241 llvm::dbgs() << " End of Block\n";
242 }
243}
244
245llvm::ArrayRef<const Fact *>
246FactManager::getBlockContaining(ProgramPoint P) const {
247 return BlockToFacts[getBlockID(P)];
248}
249
250size_t FactManager::getBlockID(ProgramPoint P) const {
251 for (size_t i = 0; i < BlockToFacts.size(); ++i)
252 for (const Fact *F : BlockToFacts[i])
253 if (F == P)
254 return i;
255 llvm_unreachable("Failed to find BlockID for given ProgramPoint");
256}
257} // namespace clang::lifetimes::internal
258