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