clang  9.0.0svn
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 
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/Expr.h"
19 #include "clang/Basic/LLVM.h"
24 #include "llvm/ADT/FoldingSet.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/Support/Casting.h"
27 #include "llvm/Support/Compiler.h"
28 #include "llvm/Support/ErrorHandling.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include <cassert>
31 
32 using namespace clang;
33 using namespace ento;
34 
35 void SymExpr::anchor() {}
36 
37 LLVM_DUMP_METHOD void SymExpr::dump() const {
38  dumpToStream(llvm::errs());
39 }
40 
41 void SymIntExpr::dumpToStream(raw_ostream &os) const {
42  os << '(';
43  getLHS()->dumpToStream(os);
44  os << ") "
46  if (getRHS().isUnsigned())
47  os << getRHS().getZExtValue();
48  else
49  os << getRHS().getSExtValue();
50  if (getRHS().isUnsigned())
51  os << 'U';
52 }
53 
54 void IntSymExpr::dumpToStream(raw_ostream &os) const {
55  if (getLHS().isUnsigned())
56  os << getLHS().getZExtValue();
57  else
58  os << getLHS().getSExtValue();
59  if (getLHS().isUnsigned())
60  os << 'U';
61  os << ' '
63  << " (";
64  getRHS()->dumpToStream(os);
65  os << ')';
66 }
67 
68 void SymSymExpr::dumpToStream(raw_ostream &os) const {
69  os << '(';
70  getLHS()->dumpToStream(os);
71  os << ") "
73  << " (";
74  getRHS()->dumpToStream(os);
75  os << ')';
76 }
77 
78 void SymbolCast::dumpToStream(raw_ostream &os) const {
79  os << '(' << ToTy.getAsString() << ") (";
80  Operand->dumpToStream(os);
81  os << ')';
82 }
83 
84 void SymbolConjured::dumpToStream(raw_ostream &os) const {
85  os << "conj_$" << getSymbolID() << '{' << T.getAsString() << ", LC"
86  << LCtx->getID();
87  if (S)
88  os << ", S" << S->getID(LCtx->getDecl()->getASTContext());
89  else
90  os << ", no stmt";
91  os << ", #" << Count << '}';
92 }
93 
94 void SymbolDerived::dumpToStream(raw_ostream &os) const {
95  os << "derived_$" << getSymbolID() << '{'
96  << getParentSymbol() << ',' << getRegion() << '}';
97 }
98 
99 void SymbolExtent::dumpToStream(raw_ostream &os) const {
100  os << "extent_$" << getSymbolID() << '{' << getRegion() << '}';
101 }
102 
103 void SymbolMetadata::dumpToStream(raw_ostream &os) const {
104  os << "meta_$" << getSymbolID() << '{'
105  << getRegion() << ',' << T.getAsString() << '}';
106 }
107 
108 void SymbolData::anchor() {}
109 
110 void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
111  os << "reg_$" << getSymbolID()
112  << '<' << getType().getAsString() << ' ' << R << '>';
113 }
114 
115 bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {
116  return itr == X.itr;
117 }
118 
119 bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {
120  return itr != X.itr;
121 }
122 
123 SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {
124  itr.push_back(SE);
125 }
126 
127 SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() {
128  assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
129  expand();
130  return *this;
131 }
132 
133 SymbolRef SymExpr::symbol_iterator::operator*() {
134  assert(!itr.empty() && "attempting to dereference an 'end' iterator");
135  return itr.back();
136 }
137 
138 void SymExpr::symbol_iterator::expand() {
139  const SymExpr *SE = itr.pop_back_val();
140 
141  switch (SE->getKind()) {
142  case SymExpr::SymbolRegionValueKind:
143  case SymExpr::SymbolConjuredKind:
144  case SymExpr::SymbolDerivedKind:
145  case SymExpr::SymbolExtentKind:
146  case SymExpr::SymbolMetadataKind:
147  return;
148  case SymExpr::SymbolCastKind:
149  itr.push_back(cast<SymbolCast>(SE)->getOperand());
150  return;
151  case SymExpr::SymIntExprKind:
152  itr.push_back(cast<SymIntExpr>(SE)->getLHS());
153  return;
154  case SymExpr::IntSymExprKind:
155  itr.push_back(cast<IntSymExpr>(SE)->getRHS());
156  return;
157  case SymExpr::SymSymExprKind: {
158  const auto *x = cast<SymSymExpr>(SE);
159  itr.push_back(x->getLHS());
160  itr.push_back(x->getRHS());
161  return;
162  }
163  }
164  llvm_unreachable("unhandled expansion case");
165 }
166 
167 const SymbolRegionValue*
168 SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) {
169  llvm::FoldingSetNodeID profile;
170  SymbolRegionValue::Profile(profile, R);
171  void *InsertPos;
172  SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
173  if (!SD) {
174  SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>();
175  new (SD) SymbolRegionValue(SymbolCounter, R);
176  DataSet.InsertNode(SD, InsertPos);
177  ++SymbolCounter;
178  }
179 
180  return cast<SymbolRegionValue>(SD);
181 }
182 
183 const SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E,
184  const LocationContext *LCtx,
185  QualType T,
186  unsigned Count,
187  const void *SymbolTag) {
188  llvm::FoldingSetNodeID profile;
189  SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag);
190  void *InsertPos;
191  SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
192  if (!SD) {
193  SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>();
194  new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag);
195  DataSet.InsertNode(SD, InsertPos);
196  ++SymbolCounter;
197  }
198 
199  return cast<SymbolConjured>(SD);
200 }
201 
202 const SymbolDerived*
203 SymbolManager::getDerivedSymbol(SymbolRef parentSymbol,
204  const TypedValueRegion *R) {
205  llvm::FoldingSetNodeID profile;
206  SymbolDerived::Profile(profile, parentSymbol, R);
207  void *InsertPos;
208  SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
209  if (!SD) {
210  SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>();
211  new (SD) SymbolDerived(SymbolCounter, parentSymbol, R);
212  DataSet.InsertNode(SD, InsertPos);
213  ++SymbolCounter;
214  }
215 
216  return cast<SymbolDerived>(SD);
217 }
218 
219 const SymbolExtent*
220 SymbolManager::getExtentSymbol(const SubRegion *R) {
221  llvm::FoldingSetNodeID profile;
222  SymbolExtent::Profile(profile, R);
223  void *InsertPos;
224  SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
225  if (!SD) {
226  SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>();
227  new (SD) SymbolExtent(SymbolCounter, R);
228  DataSet.InsertNode(SD, InsertPos);
229  ++SymbolCounter;
230  }
231 
232  return cast<SymbolExtent>(SD);
233 }
234 
235 const SymbolMetadata *
236 SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T,
237  const LocationContext *LCtx,
238  unsigned Count, const void *SymbolTag) {
239  llvm::FoldingSetNodeID profile;
240  SymbolMetadata::Profile(profile, R, S, T, LCtx, Count, SymbolTag);
241  void *InsertPos;
242  SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
243  if (!SD) {
244  SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>();
245  new (SD) SymbolMetadata(SymbolCounter, R, S, T, LCtx, Count, SymbolTag);
246  DataSet.InsertNode(SD, InsertPos);
247  ++SymbolCounter;
248  }
249 
250  return cast<SymbolMetadata>(SD);
251 }
252 
253 const SymbolCast*
254 SymbolManager::getCastSymbol(const SymExpr *Op,
255  QualType From, QualType To) {
256  llvm::FoldingSetNodeID ID;
257  SymbolCast::Profile(ID, Op, From, To);
258  void *InsertPos;
259  SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
260  if (!data) {
261  data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>();
262  new (data) SymbolCast(Op, From, To);
263  DataSet.InsertNode(data, InsertPos);
264  }
265 
266  return cast<SymbolCast>(data);
267 }
268 
269 const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs,
270  BinaryOperator::Opcode op,
271  const llvm::APSInt& v,
272  QualType t) {
273  llvm::FoldingSetNodeID ID;
274  SymIntExpr::Profile(ID, lhs, op, v, t);
275  void *InsertPos;
276  SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
277 
278  if (!data) {
279  data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>();
280  new (data) SymIntExpr(lhs, op, v, t);
281  DataSet.InsertNode(data, InsertPos);
282  }
283 
284  return cast<SymIntExpr>(data);
285 }
286 
287 const IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs,
288  BinaryOperator::Opcode op,
289  const SymExpr *rhs,
290  QualType t) {
291  llvm::FoldingSetNodeID ID;
292  IntSymExpr::Profile(ID, lhs, op, rhs, t);
293  void *InsertPos;
294  SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
295 
296  if (!data) {
297  data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>();
298  new (data) IntSymExpr(lhs, op, rhs, t);
299  DataSet.InsertNode(data, InsertPos);
300  }
301 
302  return cast<IntSymExpr>(data);
303 }
304 
305 const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs,
306  BinaryOperator::Opcode op,
307  const SymExpr *rhs,
308  QualType t) {
309  llvm::FoldingSetNodeID ID;
310  SymSymExpr::Profile(ID, lhs, op, rhs, t);
311  void *InsertPos;
312  SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
313 
314  if (!data) {
315  data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>();
316  new (data) SymSymExpr(lhs, op, rhs, t);
317  DataSet.InsertNode(data, InsertPos);
318  }
319 
320  return cast<SymSymExpr>(data);
321 }
322 
323 QualType SymbolConjured::getType() const {
324  return T;
325 }
326 
327 QualType SymbolDerived::getType() const {
328  return R->getValueType();
329 }
330 
331 QualType SymbolExtent::getType() const {
332  ASTContext &Ctx = R->getMemRegionManager()->getContext();
333  return Ctx.getSizeType();
334 }
335 
336 QualType SymbolMetadata::getType() const {
337  return T;
338 }
339 
340 QualType SymbolRegionValue::getType() const {
341  return R->getValueType();
342 }
343 
344 SymbolManager::~SymbolManager() {
345  llvm::DeleteContainerSeconds(SymbolDependencies);
346 }
347 
348 bool SymbolManager::canSymbolicate(QualType T) {
349  T = T.getCanonicalType();
350 
351  if (Loc::isLocType(T))
352  return true;
353 
354  if (T->isIntegralOrEnumerationType())
355  return true;
356 
357  if (T->isRecordType() && !T->isUnionType())
358  return true;
359 
360  return false;
361 }
362 
363 void SymbolManager::addSymbolDependency(const SymbolRef Primary,
364  const SymbolRef Dependent) {
365  SymbolDependTy::iterator I = SymbolDependencies.find(Primary);
366  SymbolRefSmallVectorTy *dependencies = nullptr;
367  if (I == SymbolDependencies.end()) {
368  dependencies = new SymbolRefSmallVectorTy();
369  SymbolDependencies[Primary] = dependencies;
370  } else {
371  dependencies = I->second;
372  }
373  dependencies->push_back(Dependent);
374 }
375 
376 const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
377  const SymbolRef Primary) {
378  SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
379  if (I == SymbolDependencies.end())
380  return nullptr;
381  return I->second;
382 }
383 
384 void SymbolReaper::markDependentsLive(SymbolRef sym) {
385  // Do not mark dependents more then once.
386  SymbolMapTy::iterator LI = TheLiving.find(sym);
387  assert(LI != TheLiving.end() && "The primary symbol is not live.");
388  if (LI->second == HaveMarkedDependents)
389  return;
390  LI->second = HaveMarkedDependents;
391 
392  if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
393  for (const auto I : *Deps) {
394  if (TheLiving.find(I) != TheLiving.end())
395  continue;
396  markLive(I);
397  }
398  }
399 }
400 
401 void SymbolReaper::markLive(SymbolRef sym) {
402  TheLiving[sym] = NotProcessed;
403  markDependentsLive(sym);
404 }
405 
406 void SymbolReaper::markLive(const MemRegion *region) {
407  RegionRoots.insert(region->getBaseRegion());
408  markElementIndicesLive(region);
409 }
410 
411 void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
412  for (auto SR = dyn_cast<SubRegion>(region); SR;
413  SR = dyn_cast<SubRegion>(SR->getSuperRegion())) {
414  if (const auto ER = dyn_cast<ElementRegion>(SR)) {
415  SVal Idx = ER->getIndex();
416  for (auto SI = Idx.symbol_begin(), SE = Idx.symbol_end(); SI != SE; ++SI)
417  markLive(*SI);
418  }
419  }
420 }
421 
422 void SymbolReaper::markInUse(SymbolRef sym) {
423  if (isa<SymbolMetadata>(sym))
424  MetadataInUse.insert(sym);
425 }
426 
427 bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
428  // TODO: For now, liveness of a memory region is equivalent to liveness of its
429  // base region. In fact we can do a bit better: say, if a particular FieldDecl
430  // is not used later in the path, we can diagnose a leak of a value within
431  // that field earlier than, say, the variable that contains the field dies.
432  MR = MR->getBaseRegion();
433 
434  if (RegionRoots.count(MR))
435  return true;
436 
437  if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
438  return isLive(SR->getSymbol());
439 
440  if (const auto *VR = dyn_cast<VarRegion>(MR))
441  return isLive(VR, true);
442 
443  // FIXME: This is a gross over-approximation. What we really need is a way to
444  // tell if anything still refers to this region. Unlike SymbolicRegions,
445  // AllocaRegions don't have associated symbols, though, so we don't actually
446  // have a way to track their liveness.
447  if (isa<AllocaRegion>(MR))
448  return true;
449 
450  if (isa<CXXThisRegion>(MR))
451  return true;
452 
453  if (isa<MemSpaceRegion>(MR))
454  return true;
455 
456  if (isa<CodeTextRegion>(MR))
457  return true;
458 
459  return false;
460 }
461 
462 bool SymbolReaper::isLive(SymbolRef sym) {
463  if (TheLiving.count(sym)) {
464  markDependentsLive(sym);
465  return true;
466  }
467 
468  bool KnownLive;
469 
470  switch (sym->getKind()) {
471  case SymExpr::SymbolRegionValueKind:
472  KnownLive = isLiveRegion(cast<SymbolRegionValue>(sym)->getRegion());
473  break;
474  case SymExpr::SymbolConjuredKind:
475  KnownLive = false;
476  break;
477  case SymExpr::SymbolDerivedKind:
478  KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol());
479  break;
480  case SymExpr::SymbolExtentKind:
481  KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion());
482  break;
483  case SymExpr::SymbolMetadataKind:
484  KnownLive = MetadataInUse.count(sym) &&
485  isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());
486  if (KnownLive)
487  MetadataInUse.erase(sym);
488  break;
489  case SymExpr::SymIntExprKind:
490  KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS());
491  break;
492  case SymExpr::IntSymExprKind:
493  KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS());
494  break;
495  case SymExpr::SymSymExprKind:
496  KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) &&
497  isLive(cast<SymSymExpr>(sym)->getRHS());
498  break;
499  case SymExpr::SymbolCastKind:
500  KnownLive = isLive(cast<SymbolCast>(sym)->getOperand());
501  break;
502  }
503 
504  if (KnownLive)
505  markLive(sym);
506 
507  return KnownLive;
508 }
509 
510 bool
511 SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const {
512  if (LCtx == nullptr)
513  return false;
514 
515  if (LCtx != ELCtx) {
516  // If the reaper's location context is a parent of the expression's
517  // location context, then the expression value is now "out of scope".
518  if (LCtx->isParentOf(ELCtx))
519  return false;
520  return true;
521  }
522 
523  // If no statement is provided, everything is this and parent contexts is live.
524  if (!Loc)
525  return true;
526 
527  return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
528 }
529 
530 bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
531  const StackFrameContext *VarContext = VR->getStackFrame();
532 
533  if (!VarContext)
534  return true;
535 
536  if (!LCtx)
537  return false;
538  const StackFrameContext *CurrentContext = LCtx->getStackFrame();
539 
540  if (VarContext == CurrentContext) {
541  // If no statement is provided, everything is live.
542  if (!Loc)
543  return true;
544 
545  if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
546  return true;
547 
548  if (!includeStoreBindings)
549  return false;
550 
551  unsigned &cachedQuery =
552  const_cast<SymbolReaper *>(this)->includedRegionCache[VR];
553 
554  if (cachedQuery) {
555  return cachedQuery == 1;
556  }
557 
558  // Query the store to see if the region occurs in any live bindings.
559  if (Store store = reapedStore.getStore()) {
560  bool hasRegion =
561  reapedStore.getStoreManager().includedInBindings(store, VR);
562  cachedQuery = hasRegion ? 1 : 2;
563  return hasRegion;
564  }
565 
566  return false;
567  }
568 
569  return VarContext->isParentOf(CurrentContext);
570 }
Defines the clang::ASTContext interface.
void dumpToStream(raw_ostream &os) const override
virtual void dump() const
void dumpToStream(raw_ostream &os) const override
StringRef getOpcodeStr() const
Definition: Expr.h:3374
virtual void dumpToStream(raw_ostream &os) const
Definition: SymExpr.h:60
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
virtual QualType getType() const =0
void dumpToStream(raw_ostream &os) const override
void dumpToStream(raw_ostream &os) const override
Dataflow Directional Tag Classes.
BinaryOperator::Opcode getOpcode(const SymExpr *SE)
static std::string getAsString(SplitQualType split, const PrintingPolicy &Policy)
Definition: Type.h:972
void dumpToStream(raw_ostream &os) const override
void dumpToStream(raw_ostream &os) const override
void dumpToStream(raw_ostream &os) const override
void dumpToStream(raw_ostream &os) const override
void dumpToStream(raw_ostream &os) const override