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