SymbolManager.cpp revision 243830
1218887Sdim//== SymbolManager.h - Management of Symbolic Values ------------*- C++ -*--==//
2218887Sdim//
3218887Sdim//                     The LLVM Compiler Infrastructure
4218887Sdim//
5218887Sdim// This file is distributed under the University of Illinois Open Source
6218887Sdim// License. See LICENSE.TXT for details.
7218887Sdim//
8218887Sdim//===----------------------------------------------------------------------===//
9218887Sdim//
10218887Sdim//  This file defines SymbolManager, a class that manages symbolic values
11218887Sdim//  created for use by ExprEngine and related classes.
12218887Sdim//
13218887Sdim//===----------------------------------------------------------------------===//
14218887Sdim
15218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
16218887Sdim#include "clang/Analysis/Analyses/LiveVariables.h"
17218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
18226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
19218887Sdim#include "llvm/Support/raw_ostream.h"
20218887Sdim
21218887Sdimusing namespace clang;
22218887Sdimusing namespace ento;
23218887Sdim
24234353Sdimvoid SymExpr::anchor() { }
25234353Sdim
26218887Sdimvoid SymExpr::dump() const {
27218887Sdim  dumpToStream(llvm::errs());
28218887Sdim}
29218887Sdim
30226633Sdimstatic void print(raw_ostream &os, BinaryOperator::Opcode Op) {
31218887Sdim  switch (Op) {
32218887Sdim    default:
33226633Sdim      llvm_unreachable("operator printing not implemented");
34218887Sdim    case BO_Mul: os << '*'  ; break;
35218887Sdim    case BO_Div: os << '/'  ; break;
36218887Sdim    case BO_Rem: os << '%'  ; break;
37218887Sdim    case BO_Add: os << '+'  ; break;
38218887Sdim    case BO_Sub: os << '-'  ; break;
39218887Sdim    case BO_Shl: os << "<<" ; break;
40218887Sdim    case BO_Shr: os << ">>" ; break;
41218887Sdim    case BO_LT:  os << "<"  ; break;
42218887Sdim    case BO_GT:  os << '>'  ; break;
43218887Sdim    case BO_LE:  os << "<=" ; break;
44218887Sdim    case BO_GE:  os << ">=" ; break;
45218887Sdim    case BO_EQ:  os << "==" ; break;
46218887Sdim    case BO_NE:  os << "!=" ; break;
47218887Sdim    case BO_And: os << '&'  ; break;
48218887Sdim    case BO_Xor: os << '^'  ; break;
49218887Sdim    case BO_Or:  os << '|'  ; break;
50218887Sdim  }
51218887Sdim}
52218887Sdim
53226633Sdimvoid SymIntExpr::dumpToStream(raw_ostream &os) const {
54218887Sdim  os << '(';
55218887Sdim  getLHS()->dumpToStream(os);
56218887Sdim  os << ") ";
57218887Sdim  print(os, getOpcode());
58218887Sdim  os << ' ' << getRHS().getZExtValue();
59218887Sdim  if (getRHS().isUnsigned()) os << 'U';
60218887Sdim}
61218887Sdim
62234353Sdimvoid IntSymExpr::dumpToStream(raw_ostream &os) const {
63234353Sdim  os << ' ' << getLHS().getZExtValue();
64234353Sdim  if (getLHS().isUnsigned()) os << 'U';
65234353Sdim  print(os, getOpcode());
66234353Sdim  os << '(';
67234353Sdim  getRHS()->dumpToStream(os);
68234353Sdim  os << ") ";
69234353Sdim}
70234353Sdim
71226633Sdimvoid SymSymExpr::dumpToStream(raw_ostream &os) const {
72218887Sdim  os << '(';
73218887Sdim  getLHS()->dumpToStream(os);
74218887Sdim  os << ") ";
75218887Sdim  os << '(';
76218887Sdim  getRHS()->dumpToStream(os);
77218887Sdim  os << ')';
78218887Sdim}
79218887Sdim
80234353Sdimvoid SymbolCast::dumpToStream(raw_ostream &os) const {
81234353Sdim  os << '(' << ToTy.getAsString() << ") (";
82234353Sdim  Operand->dumpToStream(os);
83234353Sdim  os << ')';
84234353Sdim}
85234353Sdim
86226633Sdimvoid SymbolConjured::dumpToStream(raw_ostream &os) const {
87218887Sdim  os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}';
88218887Sdim}
89218887Sdim
90226633Sdimvoid SymbolDerived::dumpToStream(raw_ostream &os) const {
91218887Sdim  os << "derived_$" << getSymbolID() << '{'
92218887Sdim     << getParentSymbol() << ',' << getRegion() << '}';
93218887Sdim}
94218887Sdim
95226633Sdimvoid SymbolExtent::dumpToStream(raw_ostream &os) const {
96218887Sdim  os << "extent_$" << getSymbolID() << '{' << getRegion() << '}';
97218887Sdim}
98218887Sdim
99226633Sdimvoid SymbolMetadata::dumpToStream(raw_ostream &os) const {
100218887Sdim  os << "meta_$" << getSymbolID() << '{'
101218887Sdim     << getRegion() << ',' << T.getAsString() << '}';
102218887Sdim}
103218887Sdim
104234353Sdimvoid SymbolData::anchor() { }
105234353Sdim
106226633Sdimvoid SymbolRegionValue::dumpToStream(raw_ostream &os) const {
107218887Sdim  os << "reg_$" << getSymbolID() << "<" << R << ">";
108218887Sdim}
109218887Sdim
110234353Sdimbool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {
111234353Sdim  return itr == X.itr;
112234353Sdim}
113234353Sdim
114234353Sdimbool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {
115234353Sdim  return itr != X.itr;
116234353Sdim}
117234353Sdim
118234353SdimSymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {
119234353Sdim  itr.push_back(SE);
120234353Sdim}
121234353Sdim
122234353SdimSymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() {
123234353Sdim  assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
124243830Sdim  expand();
125234353Sdim  return *this;
126234353Sdim}
127234353Sdim
128234353SdimSymbolRef SymExpr::symbol_iterator::operator*() {
129234353Sdim  assert(!itr.empty() && "attempting to dereference an 'end' iterator");
130243830Sdim  return itr.back();
131234353Sdim}
132234353Sdim
133234353Sdimvoid SymExpr::symbol_iterator::expand() {
134234353Sdim  const SymExpr *SE = itr.back();
135234353Sdim  itr.pop_back();
136234353Sdim
137234353Sdim  switch (SE->getKind()) {
138234353Sdim    case SymExpr::RegionValueKind:
139234353Sdim    case SymExpr::ConjuredKind:
140234353Sdim    case SymExpr::DerivedKind:
141234353Sdim    case SymExpr::ExtentKind:
142234353Sdim    case SymExpr::MetadataKind:
143234353Sdim      return;
144234353Sdim    case SymExpr::CastSymbolKind:
145234353Sdim      itr.push_back(cast<SymbolCast>(SE)->getOperand());
146234353Sdim      return;
147234353Sdim    case SymExpr::SymIntKind:
148234353Sdim      itr.push_back(cast<SymIntExpr>(SE)->getLHS());
149234353Sdim      return;
150234353Sdim    case SymExpr::IntSymKind:
151234353Sdim      itr.push_back(cast<IntSymExpr>(SE)->getRHS());
152234353Sdim      return;
153234353Sdim    case SymExpr::SymSymKind: {
154234353Sdim      const SymSymExpr *x = cast<SymSymExpr>(SE);
155234353Sdim      itr.push_back(x->getLHS());
156234353Sdim      itr.push_back(x->getRHS());
157234353Sdim      return;
158234353Sdim    }
159234353Sdim  }
160234353Sdim  llvm_unreachable("unhandled expansion case");
161234353Sdim}
162234353Sdim
163239462Sdimunsigned SymExpr::computeComplexity() const {
164239462Sdim  unsigned R = 0;
165239462Sdim  for (symbol_iterator I = symbol_begin(), E = symbol_end(); I != E; ++I)
166239462Sdim    R++;
167239462Sdim  return R;
168239462Sdim}
169239462Sdim
170218887Sdimconst SymbolRegionValue*
171226633SdimSymbolManager::getRegionValueSymbol(const TypedValueRegion* R) {
172218887Sdim  llvm::FoldingSetNodeID profile;
173218887Sdim  SymbolRegionValue::Profile(profile, R);
174226633Sdim  void *InsertPos;
175218887Sdim  SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
176218887Sdim  if (!SD) {
177218887Sdim    SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>();
178218887Sdim    new (SD) SymbolRegionValue(SymbolCounter, R);
179218887Sdim    DataSet.InsertNode(SD, InsertPos);
180218887Sdim    ++SymbolCounter;
181218887Sdim  }
182218887Sdim
183218887Sdim  return cast<SymbolRegionValue>(SD);
184218887Sdim}
185218887Sdim
186243830Sdimconst SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E,
187243830Sdim                                                   const LocationContext *LCtx,
188243830Sdim                                                   QualType T,
189243830Sdim                                                   unsigned Count,
190243830Sdim                                                   const void *SymbolTag) {
191218887Sdim  llvm::FoldingSetNodeID profile;
192234353Sdim  SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag);
193226633Sdim  void *InsertPos;
194218887Sdim  SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
195218887Sdim  if (!SD) {
196218887Sdim    SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>();
197234353Sdim    new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag);
198218887Sdim    DataSet.InsertNode(SD, InsertPos);
199218887Sdim    ++SymbolCounter;
200218887Sdim  }
201218887Sdim
202218887Sdim  return cast<SymbolConjured>(SD);
203218887Sdim}
204218887Sdim
205218887Sdimconst SymbolDerived*
206218887SdimSymbolManager::getDerivedSymbol(SymbolRef parentSymbol,
207226633Sdim                                const TypedValueRegion *R) {
208218887Sdim
209218887Sdim  llvm::FoldingSetNodeID profile;
210218887Sdim  SymbolDerived::Profile(profile, parentSymbol, R);
211226633Sdim  void *InsertPos;
212218887Sdim  SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
213218887Sdim  if (!SD) {
214218887Sdim    SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>();
215218887Sdim    new (SD) SymbolDerived(SymbolCounter, parentSymbol, R);
216218887Sdim    DataSet.InsertNode(SD, InsertPos);
217218887Sdim    ++SymbolCounter;
218218887Sdim  }
219218887Sdim
220218887Sdim  return cast<SymbolDerived>(SD);
221218887Sdim}
222218887Sdim
223218887Sdimconst SymbolExtent*
224218887SdimSymbolManager::getExtentSymbol(const SubRegion *R) {
225218887Sdim  llvm::FoldingSetNodeID profile;
226218887Sdim  SymbolExtent::Profile(profile, R);
227226633Sdim  void *InsertPos;
228218887Sdim  SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
229218887Sdim  if (!SD) {
230218887Sdim    SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>();
231218887Sdim    new (SD) SymbolExtent(SymbolCounter, R);
232218887Sdim    DataSet.InsertNode(SD, InsertPos);
233218887Sdim    ++SymbolCounter;
234218887Sdim  }
235218887Sdim
236218887Sdim  return cast<SymbolExtent>(SD);
237218887Sdim}
238218887Sdim
239218887Sdimconst SymbolMetadata*
240226633SdimSymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T,
241226633Sdim                                 unsigned Count, const void *SymbolTag) {
242218887Sdim
243218887Sdim  llvm::FoldingSetNodeID profile;
244218887Sdim  SymbolMetadata::Profile(profile, R, S, T, Count, SymbolTag);
245226633Sdim  void *InsertPos;
246218887Sdim  SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
247218887Sdim  if (!SD) {
248218887Sdim    SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>();
249218887Sdim    new (SD) SymbolMetadata(SymbolCounter, R, S, T, Count, SymbolTag);
250218887Sdim    DataSet.InsertNode(SD, InsertPos);
251218887Sdim    ++SymbolCounter;
252218887Sdim  }
253218887Sdim
254218887Sdim  return cast<SymbolMetadata>(SD);
255218887Sdim}
256218887Sdim
257234353Sdimconst SymbolCast*
258234353SdimSymbolManager::getCastSymbol(const SymExpr *Op,
259234353Sdim                             QualType From, QualType To) {
260234353Sdim  llvm::FoldingSetNodeID ID;
261234353Sdim  SymbolCast::Profile(ID, Op, From, To);
262234353Sdim  void *InsertPos;
263234353Sdim  SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
264234353Sdim  if (!data) {
265234353Sdim    data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>();
266234353Sdim    new (data) SymbolCast(Op, From, To);
267234353Sdim    DataSet.InsertNode(data, InsertPos);
268234353Sdim  }
269234353Sdim
270234353Sdim  return cast<SymbolCast>(data);
271234353Sdim}
272234353Sdim
273218887Sdimconst SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs,
274218887Sdim                                               BinaryOperator::Opcode op,
275218887Sdim                                               const llvm::APSInt& v,
276218887Sdim                                               QualType t) {
277218887Sdim  llvm::FoldingSetNodeID ID;
278218887Sdim  SymIntExpr::Profile(ID, lhs, op, v, t);
279218887Sdim  void *InsertPos;
280218887Sdim  SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
281218887Sdim
282218887Sdim  if (!data) {
283218887Sdim    data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>();
284218887Sdim    new (data) SymIntExpr(lhs, op, v, t);
285218887Sdim    DataSet.InsertNode(data, InsertPos);
286218887Sdim  }
287218887Sdim
288218887Sdim  return cast<SymIntExpr>(data);
289218887Sdim}
290218887Sdim
291234353Sdimconst IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs,
292234353Sdim                                               BinaryOperator::Opcode op,
293234353Sdim                                               const SymExpr *rhs,
294234353Sdim                                               QualType t) {
295234353Sdim  llvm::FoldingSetNodeID ID;
296234353Sdim  IntSymExpr::Profile(ID, lhs, op, rhs, t);
297234353Sdim  void *InsertPos;
298234353Sdim  SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
299234353Sdim
300234353Sdim  if (!data) {
301234353Sdim    data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>();
302234353Sdim    new (data) IntSymExpr(lhs, op, rhs, t);
303234353Sdim    DataSet.InsertNode(data, InsertPos);
304234353Sdim  }
305234353Sdim
306234353Sdim  return cast<IntSymExpr>(data);
307234353Sdim}
308234353Sdim
309218887Sdimconst SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs,
310218887Sdim                                               BinaryOperator::Opcode op,
311218887Sdim                                               const SymExpr *rhs,
312218887Sdim                                               QualType t) {
313218887Sdim  llvm::FoldingSetNodeID ID;
314218887Sdim  SymSymExpr::Profile(ID, lhs, op, rhs, t);
315218887Sdim  void *InsertPos;
316218887Sdim  SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
317218887Sdim
318218887Sdim  if (!data) {
319218887Sdim    data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>();
320218887Sdim    new (data) SymSymExpr(lhs, op, rhs, t);
321218887Sdim    DataSet.InsertNode(data, InsertPos);
322218887Sdim  }
323218887Sdim
324218887Sdim  return cast<SymSymExpr>(data);
325218887Sdim}
326218887Sdim
327243830SdimQualType SymbolConjured::getType() const {
328218887Sdim  return T;
329218887Sdim}
330218887Sdim
331243830SdimQualType SymbolDerived::getType() const {
332218887Sdim  return R->getValueType();
333218887Sdim}
334218887Sdim
335243830SdimQualType SymbolExtent::getType() const {
336243830Sdim  ASTContext &Ctx = R->getMemRegionManager()->getContext();
337218887Sdim  return Ctx.getSizeType();
338218887Sdim}
339218887Sdim
340243830SdimQualType SymbolMetadata::getType() const {
341218887Sdim  return T;
342218887Sdim}
343218887Sdim
344243830SdimQualType SymbolRegionValue::getType() const {
345218887Sdim  return R->getValueType();
346218887Sdim}
347218887Sdim
348226633SdimSymbolManager::~SymbolManager() {
349226633Sdim  for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(),
350226633Sdim       E = SymbolDependencies.end(); I != E; ++I) {
351226633Sdim    delete I->second;
352226633Sdim  }
353218887Sdim
354226633Sdim}
355226633Sdim
356218887Sdimbool SymbolManager::canSymbolicate(QualType T) {
357218887Sdim  T = T.getCanonicalType();
358218887Sdim
359218887Sdim  if (Loc::isLocType(T))
360218887Sdim    return true;
361218887Sdim
362218887Sdim  if (T->isIntegerType())
363218887Sdim    return T->isScalarType();
364218887Sdim
365218887Sdim  if (T->isRecordType() && !T->isUnionType())
366218887Sdim    return true;
367218887Sdim
368218887Sdim  return false;
369218887Sdim}
370218887Sdim
371226633Sdimvoid SymbolManager::addSymbolDependency(const SymbolRef Primary,
372226633Sdim                                        const SymbolRef Dependent) {
373226633Sdim  SymbolDependTy::iterator I = SymbolDependencies.find(Primary);
374226633Sdim  SymbolRefSmallVectorTy *dependencies = 0;
375226633Sdim  if (I == SymbolDependencies.end()) {
376226633Sdim    dependencies = new SymbolRefSmallVectorTy();
377226633Sdim    SymbolDependencies[Primary] = dependencies;
378226633Sdim  } else {
379226633Sdim    dependencies = I->second;
380226633Sdim  }
381226633Sdim  dependencies->push_back(Dependent);
382226633Sdim}
383226633Sdim
384226633Sdimconst SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
385226633Sdim                                                     const SymbolRef Primary) {
386226633Sdim  SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
387226633Sdim  if (I == SymbolDependencies.end())
388226633Sdim    return 0;
389226633Sdim  return I->second;
390226633Sdim}
391226633Sdim
392226633Sdimvoid SymbolReaper::markDependentsLive(SymbolRef sym) {
393226633Sdim  // Do not mark dependents more then once.
394226633Sdim  SymbolMapTy::iterator LI = TheLiving.find(sym);
395226633Sdim  assert(LI != TheLiving.end() && "The primary symbol is not live.");
396226633Sdim  if (LI->second == HaveMarkedDependents)
397226633Sdim    return;
398226633Sdim  LI->second = HaveMarkedDependents;
399226633Sdim
400226633Sdim  if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
401226633Sdim    for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(),
402226633Sdim                                                E = Deps->end(); I != E; ++I) {
403226633Sdim      if (TheLiving.find(*I) != TheLiving.end())
404226633Sdim        continue;
405226633Sdim      markLive(*I);
406226633Sdim    }
407226633Sdim  }
408226633Sdim}
409226633Sdim
410218887Sdimvoid SymbolReaper::markLive(SymbolRef sym) {
411226633Sdim  TheLiving[sym] = NotProcessed;
412218887Sdim  TheDead.erase(sym);
413226633Sdim  markDependentsLive(sym);
414218887Sdim}
415218887Sdim
416226633Sdimvoid SymbolReaper::markLive(const MemRegion *region) {
417226633Sdim  RegionRoots.insert(region);
418226633Sdim}
419226633Sdim
420218887Sdimvoid SymbolReaper::markInUse(SymbolRef sym) {
421218887Sdim  if (isa<SymbolMetadata>(sym))
422218887Sdim    MetadataInUse.insert(sym);
423218887Sdim}
424218887Sdim
425218887Sdimbool SymbolReaper::maybeDead(SymbolRef sym) {
426218887Sdim  if (isLive(sym))
427218887Sdim    return false;
428218887Sdim
429218887Sdim  TheDead.insert(sym);
430218887Sdim  return true;
431218887Sdim}
432218887Sdim
433226633Sdimbool SymbolReaper::isLiveRegion(const MemRegion *MR) {
434226633Sdim  if (RegionRoots.count(MR))
435226633Sdim    return true;
436226633Sdim
437218887Sdim  MR = MR->getBaseRegion();
438218887Sdim
439218887Sdim  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
440226633Sdim    return isLive(SR->getSymbol());
441218887Sdim
442218887Sdim  if (const VarRegion *VR = dyn_cast<VarRegion>(MR))
443226633Sdim    return isLive(VR, true);
444218887Sdim
445218887Sdim  // FIXME: This is a gross over-approximation. What we really need is a way to
446218887Sdim  // tell if anything still refers to this region. Unlike SymbolicRegions,
447218887Sdim  // AllocaRegions don't have associated symbols, though, so we don't actually
448218887Sdim  // have a way to track their liveness.
449218887Sdim  if (isa<AllocaRegion>(MR))
450218887Sdim    return true;
451218887Sdim
452218887Sdim  if (isa<CXXThisRegion>(MR))
453218887Sdim    return true;
454218887Sdim
455218887Sdim  if (isa<MemSpaceRegion>(MR))
456218887Sdim    return true;
457218887Sdim
458218887Sdim  return false;
459218887Sdim}
460218887Sdim
461218887Sdimbool SymbolReaper::isLive(SymbolRef sym) {
462226633Sdim  if (TheLiving.count(sym)) {
463226633Sdim    markDependentsLive(sym);
464218887Sdim    return true;
465226633Sdim  }
466243830Sdim
467243830Sdim  bool KnownLive;
468243830Sdim
469243830Sdim  switch (sym->getKind()) {
470243830Sdim  case SymExpr::RegionValueKind:
471243830Sdim    // FIXME: We should be able to use isLiveRegion here (this behavior
472243830Sdim    // predates isLiveRegion), but doing so causes test failures. Investigate.
473243830Sdim    KnownLive = true;
474243830Sdim    break;
475243830Sdim  case SymExpr::ConjuredKind:
476243830Sdim    KnownLive = false;
477243830Sdim    break;
478243830Sdim  case SymExpr::DerivedKind:
479243830Sdim    KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol());
480243830Sdim    break;
481243830Sdim  case SymExpr::ExtentKind:
482243830Sdim    KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion());
483243830Sdim    break;
484243830Sdim  case SymExpr::MetadataKind:
485243830Sdim    KnownLive = MetadataInUse.count(sym) &&
486243830Sdim                isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());
487243830Sdim    if (KnownLive)
488243830Sdim      MetadataInUse.erase(sym);
489243830Sdim    break;
490243830Sdim  case SymExpr::SymIntKind:
491243830Sdim    KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS());
492243830Sdim    break;
493243830Sdim  case SymExpr::IntSymKind:
494243830Sdim    KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS());
495243830Sdim    break;
496243830Sdim  case SymExpr::SymSymKind:
497243830Sdim    KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) &&
498243830Sdim                isLive(cast<SymSymExpr>(sym)->getRHS());
499243830Sdim    break;
500243830Sdim  case SymExpr::CastSymbolKind:
501243830Sdim    KnownLive = isLive(cast<SymbolCast>(sym)->getOperand());
502243830Sdim    break;
503218887Sdim  }
504218887Sdim
505243830Sdim  if (KnownLive)
506243830Sdim    markLive(sym);
507218887Sdim
508243830Sdim  return KnownLive;
509218887Sdim}
510218887Sdim
511234353Sdimbool
512234353SdimSymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const {
513243830Sdim  if (LCtx == 0)
514243830Sdim    return false;
515243830Sdim
516234353Sdim  if (LCtx != ELCtx) {
517234353Sdim    // If the reaper's location context is a parent of the expression's
518234353Sdim    // location context, then the expression value is now "out of scope".
519234353Sdim    if (LCtx->isParentOf(ELCtx))
520234353Sdim      return false;
521234353Sdim    return true;
522234353Sdim  }
523243830Sdim
524239462Sdim  // If no statement is provided, everything is this and parent contexts is live.
525239462Sdim  if (!Loc)
526239462Sdim    return true;
527234353Sdim
528226633Sdim  return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
529218887Sdim}
530218887Sdim
531226633Sdimbool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
532218887Sdim  const StackFrameContext *VarContext = VR->getStackFrame();
533243830Sdim
534243830Sdim  if (!VarContext)
535243830Sdim    return true;
536243830Sdim
537243830Sdim  if (!LCtx)
538243830Sdim    return false;
539218887Sdim  const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame();
540218887Sdim
541226633Sdim  if (VarContext == CurrentContext) {
542243830Sdim    // If no statement is provided, everything is live.
543239462Sdim    if (!Loc)
544239462Sdim      return true;
545239462Sdim
546226633Sdim    if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
547226633Sdim      return true;
548218887Sdim
549226633Sdim    if (!includeStoreBindings)
550226633Sdim      return false;
551226633Sdim
552226633Sdim    unsigned &cachedQuery =
553226633Sdim      const_cast<SymbolReaper*>(this)->includedRegionCache[VR];
554226633Sdim
555226633Sdim    if (cachedQuery) {
556226633Sdim      return cachedQuery == 1;
557226633Sdim    }
558226633Sdim
559226633Sdim    // Query the store to see if the region occurs in any live bindings.
560226633Sdim    if (Store store = reapedStore.getStore()) {
561226633Sdim      bool hasRegion =
562226633Sdim        reapedStore.getStoreManager().includedInBindings(store, VR);
563226633Sdim      cachedQuery = hasRegion ? 1 : 2;
564226633Sdim      return hasRegion;
565226633Sdim    }
566226633Sdim
567226633Sdim    return false;
568226633Sdim  }
569226633Sdim
570218887Sdim  return VarContext->isParentOf(CurrentContext);
571218887Sdim}
572218887Sdim
573218887SdimSymbolVisitor::~SymbolVisitor() {}
574