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