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