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 UseFact::dump(llvm::raw_ostream &OS, const LoanManager &,
159 const OriginManager &OM,
160 const LoanPropagationAnalysis *) const {
161 OS << "Use (";
162 size_t NumUsedOrigins = getUsedOrigins()->getLength();
163 size_t I = 0;
164 for (const OriginList *Cur = getUsedOrigins(); Cur;
165 Cur = Cur->peelOuterOrigin(), ++I) {
166 OM.dump(OID: Cur->getOuterOriginID(), OS);
167 if (I < NumUsedOrigins - 1)
168 OS << ", ";
169 }
170 OS << ", " << (isWritten() ? "Write" : "Read") << ")\n";
171}
172
173void InvalidateOriginFact::dump(llvm::raw_ostream &OS, const LoanManager &,
174 const OriginManager &OM,
175 const LoanPropagationAnalysis *) const {
176 OS << "InvalidateOrigin (";
177 OM.dump(OID: getInvalidatedOrigin(), OS);
178 OS << ")\n";
179}
180
181void TestPointFact::dump(llvm::raw_ostream &OS, const LoanManager &,
182 const OriginManager &,
183 const LoanPropagationAnalysis *) const {
184 OS << "TestPoint (Annotation: \"" << getAnnotation() << "\")\n";
185}
186
187void KillOriginFact::dump(llvm::raw_ostream &OS, const LoanManager &,
188 const OriginManager &OM,
189 const LoanPropagationAnalysis *) const {
190 OS << "KillOrigin (";
191 OM.dump(OID: getKilledOrigin(), OS);
192 OS << ")\n";
193}
194
195llvm::StringMap<ProgramPoint> FactManager::getTestPoints() const {
196 llvm::StringMap<ProgramPoint> AnnotationToPointMap;
197 for (const auto &BlockFacts : BlockToFacts) {
198 for (const Fact *F : BlockFacts) {
199 if (const auto *TPF = F->getAs<TestPointFact>()) {
200 StringRef PointName = TPF->getAnnotation();
201 assert(!AnnotationToPointMap.contains(PointName) &&
202 "more than one test points with the same name");
203 AnnotationToPointMap[PointName] = F;
204 }
205 }
206 }
207 return AnnotationToPointMap;
208}
209
210void FactManager::dump(const CFG &Cfg, AnalysisDeclContext &AC,
211 const LoanPropagationAnalysis *LPA) const {
212 llvm::dbgs() << "==========================================\n";
213 llvm::dbgs() << " Lifetime Analysis Facts:\n";
214 llvm::dbgs() << "==========================================\n";
215 if (const Decl *D = AC.getDecl())
216 if (const auto *ND = dyn_cast<NamedDecl>(Val: D))
217 llvm::dbgs() << "Function: " << ND->getQualifiedNameAsString() << "\n";
218 // Print blocks in the order as they appear in code for a stable ordering.
219 for (const CFGBlock *B : *AC.getAnalysis<PostOrderCFGView>()) {
220 llvm::dbgs() << " Block B" << B->getBlockID() << ":\n";
221 for (const Fact *F : getFacts(B)) {
222 llvm::dbgs() << " ";
223 F->dump(OS&: llvm::dbgs(), LoanMgr, OriginMgr, LPA);
224 }
225 llvm::dbgs() << " End of Block\n";
226 }
227}
228
229llvm::ArrayRef<const Fact *>
230FactManager::getBlockContaining(ProgramPoint P) const {
231 return BlockToFacts[getBlockID(P)];
232}
233
234size_t FactManager::getBlockID(ProgramPoint P) const {
235 for (size_t i = 0; i < BlockToFacts.size(); ++i)
236 for (const Fact *F : BlockToFacts[i])
237 if (F == P)
238 return i;
239 llvm_unreachable("Failed to find BlockID for given ProgramPoint");
240}
241} // namespace clang::lifetimes::internal
242