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