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