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