clang 22.0.0git
SymbolManager.cpp
Go to the documentation of this file.
1//===- SymbolManager.h - Management of Symbolic Values --------------------===//
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// This file defines SymbolManager, a class that manages symbolic values
10// created for use by ExprEngine and related classes.
11//
12//===----------------------------------------------------------------------===//
13
16#include "clang/AST/Expr.h"
19#include "clang/Basic/LLVM.h"
24#include "llvm/Support/Compiler.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/Support/raw_ostream.h"
27#include <cassert>
28
29using namespace clang;
30using namespace ento;
31
32void SymExpr::anchor() {}
33
34StringRef SymbolConjured::getKindStr() const { return "conj_$"; }
35StringRef SymbolDerived::getKindStr() const { return "derived_$"; }
36StringRef SymbolExtent::getKindStr() const { return "extent_$"; }
37StringRef SymbolMetadata::getKindStr() const { return "meta_$"; }
38StringRef SymbolRegionValue::getKindStr() const { return "reg_$"; }
39
40LLVM_DUMP_METHOD void SymExpr::dump() const { dumpToStream(llvm::errs()); }
41
42void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS, const SymExpr *Sym) {
43 OS << '(';
44 Sym->dumpToStream(OS);
45 OS << ')';
46}
47
49 const llvm::APSInt &Value) {
50 if (Value.isUnsigned())
51 OS << Value.getZExtValue();
52 else
53 OS << Value.getSExtValue();
54 if (Value.isUnsigned())
55 OS << 'U';
56}
57
60 OS << ' ' << BinaryOperator::getOpcodeStr(Op) << ' ';
61}
62
63void SymbolCast::dumpToStream(raw_ostream &os) const {
64 os << '(' << ToTy << ") (";
65 Operand->dumpToStream(os);
66 os << ')';
67}
68
69void UnarySymExpr::dumpToStream(raw_ostream &os) const {
71 bool Binary = isa<BinarySymExpr>(Operand);
72 if (Binary)
73 os << '(';
74 Operand->dumpToStream(os);
75 if (Binary)
76 os << ')';
77}
78
80 // Sometimes the CFG element is invalid, avoid dereferencing it.
81 if (Elem.getParent() == nullptr ||
82 Elem.getIndexInBlock() >= Elem.getParent()->size())
83 return nullptr;
84 switch (Elem->getKind()) {
86 if (const auto *Init = Elem->castAs<CFGInitializer>().getInitializer()) {
87 return Init->getInit();
88 }
89 return nullptr;
91 return Elem->castAs<CFGScopeBegin>().getTriggerStmt();
93 return Elem->castAs<CFGScopeEnd>().getTriggerStmt();
95 return Elem->castAs<CFGNewAllocator>().getAllocatorExpr();
97 return Elem->castAs<CFGLifetimeEnds>().getTriggerStmt();
99 return Elem->castAs<CFGLoopExit>().getLoopStmt();
101 return Elem->castAs<CFGStmt>().getStmt();
103 return Elem->castAs<CFGConstructor>().getStmt();
105 return Elem->castAs<CFGCXXRecordTypedCall>().getStmt();
107 return Elem->castAs<CFGAutomaticObjDtor>().getTriggerStmt();
109 return Elem->castAs<CFGDeleteDtor>().getDeleteExpr();
111 return nullptr;
113 return nullptr;
115 return Elem->castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
117 return nullptr;
118 }
119 return nullptr;
120}
121
122void SymbolConjured::dumpToStream(raw_ostream &os) const {
123 os << getKindStr() << getSymbolID() << '{' << T << ", LC" << LCtx->getID();
124 if (auto *S = getStmt())
125 os << ", S" << S->getID(LCtx->getDecl()->getASTContext());
126 else
127 os << ", no stmt";
128 os << ", #" << Count << '}';
129}
130
131void SymbolDerived::dumpToStream(raw_ostream &os) const {
132 os << getKindStr() << getSymbolID() << '{' << getParentSymbol() << ','
133 << getRegion() << '}';
134}
135
136void SymbolExtent::dumpToStream(raw_ostream &os) const {
137 os << getKindStr() << getSymbolID() << '{' << getRegion() << '}';
138}
139
140void SymbolMetadata::dumpToStream(raw_ostream &os) const {
141 os << getKindStr() << getSymbolID() << '{' << getRegion() << ',' << T << '}';
142}
143
144void SymbolData::anchor() {}
145
146void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
147 os << getKindStr() << getSymbolID() << '<' << getType() << ' ' << R << '>';
148}
149
151 return itr == X.itr;
152}
153
155 return itr != X.itr;
156}
157
159 itr.push_back(SE);
160}
161
163 assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
164 expand();
165 return *this;
166}
167
169 assert(!itr.empty() && "attempting to dereference an 'end' iterator");
170 return itr.back();
171}
172
173void SymExpr::symbol_iterator::expand() {
174 const SymExpr *SE = itr.pop_back_val();
175
176 switch (SE->getKind()) {
177 case SymExpr::SymbolRegionValueKind:
178 case SymExpr::SymbolConjuredKind:
179 case SymExpr::SymbolDerivedKind:
180 case SymExpr::SymbolExtentKind:
181 case SymExpr::SymbolMetadataKind:
182 return;
183 case SymExpr::SymbolCastKind:
184 itr.push_back(cast<SymbolCast>(SE)->getOperand());
185 return;
186 case SymExpr::UnarySymExprKind:
187 itr.push_back(cast<UnarySymExpr>(SE)->getOperand());
188 return;
189 case SymExpr::SymIntExprKind:
190 itr.push_back(cast<SymIntExpr>(SE)->getLHS());
191 return;
192 case SymExpr::IntSymExprKind:
193 itr.push_back(cast<IntSymExpr>(SE)->getRHS());
194 return;
195 case SymExpr::SymSymExprKind: {
196 const auto *x = cast<SymSymExpr>(SE);
197 itr.push_back(x->getLHS());
198 itr.push_back(x->getRHS());
199 return;
200 }
201 }
202 llvm_unreachable("unhandled expansion case");
203}
204
206 return T;
207}
208
210 return R->getValueType();
211}
212
214 ASTContext &Ctx = R->getMemRegionManager().getContext();
215 return Ctx.getSizeType();
216}
217
219 return T;
220}
221
223 return R->getValueType();
224}
225
227 T = T.getCanonicalType();
228
229 if (Loc::isLocType(T))
230 return true;
231
233 return true;
234
235 if (T->isRecordType() && !T->isUnionType())
236 return true;
237
238 return false;
239}
240
242 const SymbolRef Dependent) {
243 auto &dependencies = SymbolDependencies[Primary];
244 if (!dependencies) {
245 dependencies = std::make_unique<SymbolRefSmallVectorTy>();
246 }
247 dependencies->push_back(Dependent);
248}
249
251 const SymbolRef Primary) {
252 SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
253 if (I == SymbolDependencies.end())
254 return nullptr;
255 return I->second.get();
256}
257
258void SymbolReaper::markDependentsLive(SymbolRef sym) {
259 // Do not mark dependents more then once.
260 SymbolMapTy::iterator LI = TheLiving.find(sym);
261 assert(LI != TheLiving.end() && "The primary symbol is not live.");
262 if (LI->second == HaveMarkedDependents)
263 return;
264 LI->second = HaveMarkedDependents;
265
266 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
267 for (const auto I : *Deps) {
268 if (TheLiving.contains(I))
269 continue;
270 markLive(I);
271 }
272 }
273}
274
276 TheLiving[sym] = NotProcessed;
277 markDependentsLive(sym);
278}
279
281 LiveRegionRoots.insert(region->getBaseRegion());
282 markElementIndicesLive(region);
283}
284
286 LazilyCopiedRegionRoots.insert(region->getBaseRegion());
287}
288
290 for (auto SR = dyn_cast<SubRegion>(region); SR;
291 SR = dyn_cast<SubRegion>(SR->getSuperRegion())) {
292 if (const auto ER = dyn_cast<ElementRegion>(SR)) {
293 SVal Idx = ER->getIndex();
294 for (SymbolRef Sym : Idx.symbols())
295 markLive(Sym);
296 }
297 }
298}
299
301 if (isa<SymbolMetadata>(sym))
302 MetadataInUse.insert(sym);
303}
304
306 // TODO: For now, liveness of a memory region is equivalent to liveness of its
307 // base region. In fact we can do a bit better: say, if a particular FieldDecl
308 // is not used later in the path, we can diagnose a leak of a value within
309 // that field earlier than, say, the variable that contains the field dies.
310 MR = MR->getBaseRegion();
311 if (LiveRegionRoots.count(MR))
312 return true;
313
314 if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
315 return isLive(SR->getSymbol());
316
317 if (const auto *VR = dyn_cast<VarRegion>(MR))
318 return isLive(VR, true);
319
320 // FIXME: This is a gross over-approximation. What we really need is a way to
321 // tell if anything still refers to this region. Unlike SymbolicRegions,
322 // AllocaRegions don't have associated symbols, though, so we don't actually
323 // have a way to track their liveness.
324 return isa<AllocaRegion, CXXThisRegion, MemSpaceRegion, CodeTextRegion>(MR);
325}
326
327bool SymbolReaper::isLazilyCopiedRegion(const MemRegion *MR) const {
328 // TODO: See comment in isLiveRegion.
329 return LazilyCopiedRegionRoots.count(MR->getBaseRegion());
330}
331
332bool SymbolReaper::isReadableRegion(const MemRegion *MR) {
333 return isLiveRegion(MR) || isLazilyCopiedRegion(MR);
334}
335
337 if (TheLiving.count(sym)) {
338 markDependentsLive(sym);
339 return true;
340 }
341
342 bool KnownLive;
343
344 switch (sym->getKind()) {
345 case SymExpr::SymbolRegionValueKind:
346 KnownLive = isReadableRegion(cast<SymbolRegionValue>(sym)->getRegion());
347 break;
348 case SymExpr::SymbolConjuredKind:
349 KnownLive = false;
350 break;
351 case SymExpr::SymbolDerivedKind:
352 KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol());
353 break;
354 case SymExpr::SymbolExtentKind:
355 KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion());
356 break;
357 case SymExpr::SymbolMetadataKind:
358 KnownLive = MetadataInUse.count(sym) &&
359 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());
360 if (KnownLive)
361 MetadataInUse.erase(sym);
362 break;
363 case SymExpr::SymIntExprKind:
364 KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS());
365 break;
366 case SymExpr::IntSymExprKind:
367 KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS());
368 break;
369 case SymExpr::SymSymExprKind:
370 KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) &&
371 isLive(cast<SymSymExpr>(sym)->getRHS());
372 break;
373 case SymExpr::SymbolCastKind:
374 KnownLive = isLive(cast<SymbolCast>(sym)->getOperand());
375 break;
376 case SymExpr::UnarySymExprKind:
377 KnownLive = isLive(cast<UnarySymExpr>(sym)->getOperand());
378 break;
379 }
380
381 if (KnownLive)
382 markLive(sym);
383
384 return KnownLive;
385}
386
387bool
388SymbolReaper::isLive(const Expr *ExprVal, const LocationContext *ELCtx) const {
389 if (LCtx == nullptr)
390 return false;
391
392 if (LCtx != ELCtx) {
393 // If the reaper's location context is a parent of the expression's
394 // location context, then the expression value is now "out of scope".
395 if (LCtx->isParentOf(ELCtx))
396 return false;
397 return true;
398 }
399
400 // If no statement is provided, everything in this and parent contexts is
401 // live.
402 if (!Loc)
403 return true;
404
405 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
406}
407
408bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
409 const StackFrameContext *VarContext = VR->getStackFrame();
410
411 if (!VarContext)
412 return true;
413
414 if (!LCtx)
415 return false;
416 const StackFrameContext *CurrentContext = LCtx->getStackFrame();
417
418 if (VarContext == CurrentContext) {
419 // If no statement is provided, everything is live.
420 if (!Loc)
421 return true;
422
423 // Anonymous parameters of an inheriting constructor are live for the entire
424 // duration of the constructor.
425 if (isa<CXXInheritedCtorInitExpr>(Loc))
426 return true;
427
428 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
429 return true;
430
431 if (!includeStoreBindings)
432 return false;
433
434 unsigned &cachedQuery =
435 const_cast<SymbolReaper *>(this)->includedRegionCache[VR];
436
437 if (cachedQuery) {
438 return cachedQuery == 1;
439 }
440
441 // Query the store to see if the region occurs in any live bindings.
442 if (Store store = reapedStore.getStore()) {
443 bool hasRegion =
444 reapedStore.getStoreManager().includedInBindings(store, VR);
445 cachedQuery = hasRegion ? 1 : 2;
446 return hasRegion;
447 }
448
449 return false;
450 }
451
452 return VarContext->isParentOf(CurrentContext);
453}
Defines the clang::ASTContext interface.
This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...
static const MemRegion * getRegion(const CallEvent &Call, const MutexDescriptor &Descriptor, bool IsLock)
#define X(type, name)
Definition: Value.h:145
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:188
QualType getSizeType() const
Return the unique type for "size_t" (C99 7.17), defined in <stddef.h>.
StringRef getOpcodeStr() const
Definition: Expr.h:4040
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
Definition: CFG.h:418
Represents a function call that returns a C++ object by value.
Definition: CFG.h:186
Represents C++ constructor call.
Definition: CFG.h:157
Represents C++ object destructor generated from a call to delete.
Definition: CFG.h:443
@ CleanupFunction
Definition: CFG.h:79
@ LifetimeEnds
Definition: CFG.h:63
@ CXXRecordTypedCall
Definition: CFG.h:68
@ AutomaticObjectDtor
Definition: CFG.h:72
@ TemporaryDtor
Definition: CFG.h:76
@ NewAllocator
Definition: CFG.h:62
Represents C++ base or member initializer from constructor's initialization list.
Definition: CFG.h:228
CXXCtorInitializer * getInitializer() const
Definition: CFG.h:233
Represents the point where the lifetime of an automatic object ends.
Definition: CFG.h:293
Represents the point where a loop ends.
Definition: CFG.h:274
Represents C++ allocator call.
Definition: CFG.h:248
Represents beginning of a scope implicitly generated by the compiler on encountering a CompoundStmt.
Definition: CFG.h:318
Represents end of a scope implicitly generated by the compiler after the last Stmt in a CompoundStmt'...
Definition: CFG.h:344
Represents C++ object destructor implicitly generated at the end of full expression for temporary obj...
Definition: CFG.h:511
ASTContext & getASTContext() const LLVM_READONLY
Definition: DeclBase.cpp:524
This represents one expression.
Definition: Expr.h:112
bool isLive(const CFGBlock *B, const VarDecl *D)
Return true if a variable is live at the end of a specified block.
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
bool isParentOf(const LocationContext *LC) const
const Decl * getDecl() const
const StackFrameContext * getStackFrame() const
A (possibly-)qualified type.
Definition: TypeBase.h:937
It represents a stack frame of the call stack (based on CallEvent).
Stmt - This represents one statement.
Definition: Stmt.h:85
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: TypeBase.h:9054
bool isRecordType() const
Definition: TypeBase.h:8707
bool isUnionType() const
Definition: Type.cpp:718
static StringRef getOpcodeStr(Opcode Op)
getOpcodeStr - Turn an Opcode enum value into the punctuation char it corresponds to,...
Definition: Expr.cpp:1402
static void dumpToStreamImpl(raw_ostream &os, const SymExpr *Value)
static bool isLocType(QualType T)
Definition: SVals.h:262
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:98
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getBaseRegion() const
Definition: MemRegion.cpp:1422
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
Definition: SVals.h:56
llvm::iterator_range< SymExpr::symbol_iterator > symbols() const
Definition: SVals.h:156
Iterator over symbols that the current symbol depends on.
Definition: SymExpr.h:91
bool operator!=(const symbol_iterator &X) const
bool operator==(const symbol_iterator &X) const
Symbolic value.
Definition: SymExpr.h:32
virtual void dumpToStream(raw_ostream &os) const
Definition: SymExpr.h:81
Kind getKind() const
Definition: SymExpr.h:69
virtual void dump() const
SymbolID getSymbolID() const
Get a unique identifier for this symbol.
Definition: SymExpr.h:77
void dumpToStream(raw_ostream &os) const override
const Stmt * getStmt() const
StringRef getKindStr() const override
Get a string representation of the kind of the region.
void dumpToStream(raw_ostream &os) const override
QualType getType() const override
LLVM_ATTRIBUTE_RETURNS_NONNULL SymbolRef getParentSymbol() const
StringRef getKindStr() const override
Get a string representation of the kind of the region.
void dumpToStream(raw_ostream &os) const override
QualType getType() const override
LLVM_ATTRIBUTE_RETURNS_NONNULL const TypedValueRegion * getRegion() const
LLVM_ATTRIBUTE_RETURNS_NONNULL const SubRegion * getRegion() const
void dumpToStream(raw_ostream &os) const override
QualType getType() const override
StringRef getKindStr() const override
Get a string representation of the kind of the region.
void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent)
Add artificial symbol dependency.
const SymbolRefSmallVectorTy * getDependentSymbols(const SymbolRef Primary)
static bool canSymbolicate(QualType T)
void dumpToStream(raw_ostream &os) const override
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getRegion() const
StringRef getKindStr() const override
Get a string representation of the kind of the region.
QualType getType() const override
A class responsible for cleaning up unused symbols.
void markLive(SymbolRef sym)
Unconditionally marks a symbol as live.
void markElementIndicesLive(const MemRegion *region)
void markInUse(SymbolRef sym)
Marks a symbol as important to a checker.
bool isLiveRegion(const MemRegion *region)
void markLazilyCopied(const MemRegion *region)
bool isLive(SymbolRef sym)
void dumpToStream(raw_ostream &os) const override
QualType getType() const override
StringRef getKindStr() const override
Get a string representation of the kind of the region.
void dumpToStream(raw_ostream &os) const override
const VarDecl * getDecl() const override=0
const StackFrameContext * getStackFrame() const
It might return null.
Definition: MemRegion.cpp:166
@ OS
Indicates that the tracking object is a descendant of a referenced-counted OSObject,...
const void * Store
Store - This opaque type encapsulates an immutable mapping from locations to values.
Definition: StoreRef.h:27
The JSON file list parser is used to communicate input to InstallAPI.
BinaryOperatorKind
@ Dependent
Parse the block as a dependent block, which may be used in some template instantiations but not other...
const FunctionProtoType * T