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(ASTContext&) const {
328  return T;
329}
330
331QualType SymbolDerived::getType(ASTContext &Ctx) const {
332  return R->getValueType();
333}
334
335QualType SymbolExtent::getType(ASTContext &Ctx) const {
336  return Ctx.getSizeType();
337}
338
339QualType SymbolMetadata::getType(ASTContext&) const {
340  return T;
341}
342
343QualType SymbolRegionValue::getType(ASTContext &C) const {
344  return R->getValueType();
345}
346
347SymbolManager::~SymbolManager() {
348  for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(),
349       E = SymbolDependencies.end(); I != E; ++I) {
350    delete I->second;
351  }
352
353}
354
355bool SymbolManager::canSymbolicate(QualType T) {
356  T = T.getCanonicalType();
357
358  if (Loc::isLocType(T))
359    return true;
360
361  if (T->isIntegerType())
362    return T->isScalarType();
363
364  if (T->isRecordType() && !T->isUnionType())
365    return true;
366
367  return false;
368}
369
370void SymbolManager::addSymbolDependency(const SymbolRef Primary,
371                                        const SymbolRef Dependent) {
372  SymbolDependTy::iterator I = SymbolDependencies.find(Primary);
373  SymbolRefSmallVectorTy *dependencies = 0;
374  if (I == SymbolDependencies.end()) {
375    dependencies = new SymbolRefSmallVectorTy();
376    SymbolDependencies[Primary] = dependencies;
377  } else {
378    dependencies = I->second;
379  }
380  dependencies->push_back(Dependent);
381}
382
383const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
384                                                     const SymbolRef Primary) {
385  SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
386  if (I == SymbolDependencies.end())
387    return 0;
388  return I->second;
389}
390
391void SymbolReaper::markDependentsLive(SymbolRef sym) {
392  // Do not mark dependents more then once.
393  SymbolMapTy::iterator LI = TheLiving.find(sym);
394  assert(LI != TheLiving.end() && "The primary symbol is not live.");
395  if (LI->second == HaveMarkedDependents)
396    return;
397  LI->second = HaveMarkedDependents;
398
399  if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
400    for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(),
401                                                E = Deps->end(); I != E; ++I) {
402      if (TheLiving.find(*I) != TheLiving.end())
403        continue;
404      markLive(*I);
405    }
406  }
407}
408
409void SymbolReaper::markLive(SymbolRef sym) {
410  TheLiving[sym] = NotProcessed;
411  TheDead.erase(sym);
412  markDependentsLive(sym);
413}
414
415void SymbolReaper::markLive(const MemRegion *region) {
416  RegionRoots.insert(region);
417}
418
419void SymbolReaper::markInUse(SymbolRef sym) {
420  if (isa<SymbolMetadata>(sym))
421    MetadataInUse.insert(sym);
422}
423
424bool SymbolReaper::maybeDead(SymbolRef sym) {
425  if (isLive(sym))
426    return false;
427
428  TheDead.insert(sym);
429  return true;
430}
431
432bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
433  if (RegionRoots.count(MR))
434    return true;
435
436  MR = MR->getBaseRegion();
437
438  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
439    return isLive(SR->getSymbol());
440
441  if (const VarRegion *VR = dyn_cast<VarRegion>(MR))
442    return isLive(VR, true);
443
444  // FIXME: This is a gross over-approximation. What we really need is a way to
445  // tell if anything still refers to this region. Unlike SymbolicRegions,
446  // AllocaRegions don't have associated symbols, though, so we don't actually
447  // have a way to track their liveness.
448  if (isa<AllocaRegion>(MR))
449    return true;
450
451  if (isa<CXXThisRegion>(MR))
452    return true;
453
454  if (isa<MemSpaceRegion>(MR))
455    return true;
456
457  return false;
458}
459
460bool SymbolReaper::isLive(SymbolRef sym) {
461  if (TheLiving.count(sym)) {
462    markDependentsLive(sym);
463    return true;
464  }
465
466  if (const SymbolDerived *derived = dyn_cast<SymbolDerived>(sym)) {
467    if (isLive(derived->getParentSymbol())) {
468      markLive(sym);
469      return true;
470    }
471    return false;
472  }
473
474  if (const SymbolExtent *extent = dyn_cast<SymbolExtent>(sym)) {
475    if (isLiveRegion(extent->getRegion())) {
476      markLive(sym);
477      return true;
478    }
479    return false;
480  }
481
482  if (const SymbolMetadata *metadata = dyn_cast<SymbolMetadata>(sym)) {
483    if (MetadataInUse.count(sym)) {
484      if (isLiveRegion(metadata->getRegion())) {
485        markLive(sym);
486        MetadataInUse.erase(sym);
487        return true;
488      }
489    }
490    return false;
491  }
492
493  // Interogate the symbol.  It may derive from an input value to
494  // the analyzed function/method.
495  return isa<SymbolRegionValue>(sym);
496}
497
498bool
499SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const {
500  if (LCtx != ELCtx) {
501    // If the reaper's location context is a parent of the expression's
502    // location context, then the expression value is now "out of scope".
503    if (LCtx->isParentOf(ELCtx))
504      return false;
505    return true;
506  }
507  // If no statement is provided, everything is this and parent contexts is live.
508  if (!Loc)
509    return true;
510
511  return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
512}
513
514bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
515  const StackFrameContext *VarContext = VR->getStackFrame();
516  const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame();
517
518  if (VarContext == CurrentContext) {
519    // If no statement is provided, everything is live.
520    if (!Loc)
521      return true;
522
523    if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
524      return true;
525
526    if (!includeStoreBindings)
527      return false;
528
529    unsigned &cachedQuery =
530      const_cast<SymbolReaper*>(this)->includedRegionCache[VR];
531
532    if (cachedQuery) {
533      return cachedQuery == 1;
534    }
535
536    // Query the store to see if the region occurs in any live bindings.
537    if (Store store = reapedStore.getStore()) {
538      bool hasRegion =
539        reapedStore.getStoreManager().includedInBindings(store, VR);
540      cachedQuery = hasRegion ? 1 : 2;
541      return hasRegion;
542    }
543
544    return false;
545  }
546
547  return !VarContext || VarContext->isParentOf(CurrentContext);
548}
549
550SymbolVisitor::~SymbolVisitor() {}
551