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