"Fossies" - the Fresh Open Source Software Archive

Member "cfe-9.0.0.src/lib/StaticAnalyzer/Core/SymbolManager.cpp" (19 Jan 2019, 16953 Bytes) of package /linux/misc/cfe-9.0.0.src.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "SymbolManager.cpp": 8.0.1_vs_9.0.0.

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