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