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 static void print(raw_ostream &os, BinaryOperator::Opcode Op) {
     31   switch (Op) {
     32     default:
     33       llvm_unreachable("operator printing not implemented");
     34     case BO_Mul: os << '*'  ; break;
     35     case BO_Div: os << '/'  ; break;
     36     case BO_Rem: os << '%'  ; break;
     37     case BO_Add: os << '+'  ; break;
     38     case BO_Sub: os << '-'  ; break;
     39     case BO_Shl: os << "<<" ; break;
     40     case BO_Shr: os << ">>" ; break;
     41     case BO_LT:  os << "<"  ; break;
     42     case BO_GT:  os << '>'  ; break;
     43     case BO_LE:  os << "<=" ; break;
     44     case BO_GE:  os << ">=" ; break;
     45     case BO_EQ:  os << "==" ; break;
     46     case BO_NE:  os << "!=" ; break;
     47     case BO_And: os << '&'  ; break;
     48     case BO_Xor: os << '^'  ; break;
     49     case BO_Or:  os << '|'  ; break;
     50   }
     51 }
     52 
     53 void SymIntExpr::dumpToStream(raw_ostream &os) const {
     54   os << '(';
     55   getLHS()->dumpToStream(os);
     56   os << ") ";
     57   print(os, getOpcode());
     58   os << ' ' << getRHS().getZExtValue();
     59   if (getRHS().isUnsigned()) os << 'U';
     60 }
     61 
     62 void IntSymExpr::dumpToStream(raw_ostream &os) const {
     63   os << ' ' << getLHS().getZExtValue();
     64   if (getLHS().isUnsigned()) os << 'U';
     65   print(os, getOpcode());
     66   os << '(';
     67   getRHS()->dumpToStream(os);
     68   os << ") ";
     69 }
     70 
     71 void SymSymExpr::dumpToStream(raw_ostream &os) const {
     72   os << '(';
     73   getLHS()->dumpToStream(os);
     74   os << ") ";
     75   os << '(';
     76   getRHS()->dumpToStream(os);
     77   os << ')';
     78 }
     79 
     80 void SymbolCast::dumpToStream(raw_ostream &os) const {
     81   os << '(' << ToTy.getAsString() << ") (";
     82   Operand->dumpToStream(os);
     83   os << ')';
     84 }
     85 
     86 void SymbolConjured::dumpToStream(raw_ostream &os) const {
     87   os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}';
     88 }
     89 
     90 void SymbolDerived::dumpToStream(raw_ostream &os) const {
     91   os << "derived_$" << getSymbolID() << '{'
     92      << getParentSymbol() << ',' << getRegion() << '}';
     93 }
     94 
     95 void SymbolExtent::dumpToStream(raw_ostream &os) const {
     96   os << "extent_$" << getSymbolID() << '{' << getRegion() << '}';
     97 }
     98 
     99 void SymbolMetadata::dumpToStream(raw_ostream &os) const {
    100   os << "meta_$" << getSymbolID() << '{'
    101      << getRegion() << ',' << T.getAsString() << '}';
    102 }
    103 
    104 void SymbolData::anchor() { }
    105 
    106 void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
    107   os << "reg_$" << getSymbolID() << "<" << R << ">";
    108 }
    109 
    110 bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {
    111   return itr == X.itr;
    112 }
    113 
    114 bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {
    115   return itr != X.itr;
    116 }
    117 
    118 SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {
    119   itr.push_back(SE);
    120   while (!isa<SymbolData>(itr.back())) expand();
    121 }
    122 
    123 SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() {
    124   assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
    125   assert(isa<SymbolData>(itr.back()));
    126   itr.pop_back();
    127   if (!itr.empty())
    128     while (!isa<SymbolData>(itr.back())) expand();
    129   return *this;
    130 }
    131 
    132 SymbolRef SymExpr::symbol_iterator::operator*() {
    133   assert(!itr.empty() && "attempting to dereference an 'end' iterator");
    134   return cast<SymbolData>(itr.back());
    135 }
    136 
    137 void SymExpr::symbol_iterator::expand() {
    138   const SymExpr *SE = itr.back();
    139   itr.pop_back();
    140 
    141   switch (SE->getKind()) {
    142     case SymExpr::RegionValueKind:
    143     case SymExpr::ConjuredKind:
    144     case SymExpr::DerivedKind:
    145     case SymExpr::ExtentKind:
    146     case SymExpr::MetadataKind:
    147       return;
    148     case SymExpr::CastSymbolKind:
    149       itr.push_back(cast<SymbolCast>(SE)->getOperand());
    150       return;
    151     case SymExpr::SymIntKind:
    152       itr.push_back(cast<SymIntExpr>(SE)->getLHS());
    153       return;
    154     case SymExpr::IntSymKind:
    155       itr.push_back(cast<IntSymExpr>(SE)->getRHS());
    156       return;
    157     case SymExpr::SymSymKind: {
    158       const SymSymExpr *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*
    184 SymbolManager::getConjuredSymbol(const Stmt *E, const LocationContext *LCtx,
    185                                  QualType T, unsigned Count,
    186                                  const void *SymbolTag) {
    187 
    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 
    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                                  unsigned Count, const void *SymbolTag) {
    239 
    240   llvm::FoldingSetNodeID profile;
    241   SymbolMetadata::Profile(profile, R, S, T, 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, 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(ASTContext&) const {
    325   return T;
    326 }
    327 
    328 QualType SymbolDerived::getType(ASTContext &Ctx) const {
    329   return R->getValueType();
    330 }
    331 
    332 QualType SymbolExtent::getType(ASTContext &Ctx) const {
    333   return Ctx.getSizeType();
    334 }
    335 
    336 QualType SymbolMetadata::getType(ASTContext&) const {
    337   return T;
    338 }
    339 
    340 QualType SymbolRegionValue::getType(ASTContext &C) const {
    341   return R->getValueType();
    342 }
    343 
    344 SymbolManager::~SymbolManager() {
    345   for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(),
    346        E = SymbolDependencies.end(); I != E; ++I) {
    347     delete I->second;
    348   }
    349 
    350 }
    351 
    352 bool SymbolManager::canSymbolicate(QualType T) {
    353   T = T.getCanonicalType();
    354 
    355   if (Loc::isLocType(T))
    356     return true;
    357 
    358   if (T->isIntegerType())
    359     return T->isScalarType();
    360 
    361   if (T->isRecordType() && !T->isUnionType())
    362     return true;
    363 
    364   return false;
    365 }
    366 
    367 void SymbolManager::addSymbolDependency(const SymbolRef Primary,
    368                                         const SymbolRef Dependent) {
    369   SymbolDependTy::iterator I = SymbolDependencies.find(Primary);
    370   SymbolRefSmallVectorTy *dependencies = 0;
    371   if (I == SymbolDependencies.end()) {
    372     dependencies = new SymbolRefSmallVectorTy();
    373     SymbolDependencies[Primary] = dependencies;
    374   } else {
    375     dependencies = I->second;
    376   }
    377   dependencies->push_back(Dependent);
    378 }
    379 
    380 const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
    381                                                      const SymbolRef Primary) {
    382   SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
    383   if (I == SymbolDependencies.end())
    384     return 0;
    385   return I->second;
    386 }
    387 
    388 void SymbolReaper::markDependentsLive(SymbolRef sym) {
    389   // Do not mark dependents more then once.
    390   SymbolMapTy::iterator LI = TheLiving.find(sym);
    391   assert(LI != TheLiving.end() && "The primary symbol is not live.");
    392   if (LI->second == HaveMarkedDependents)
    393     return;
    394   LI->second = HaveMarkedDependents;
    395 
    396   if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
    397     for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(),
    398                                                 E = Deps->end(); I != E; ++I) {
    399       if (TheLiving.find(*I) != TheLiving.end())
    400         continue;
    401       markLive(*I);
    402     }
    403   }
    404 }
    405 
    406 void SymbolReaper::markLive(SymbolRef sym) {
    407   TheLiving[sym] = NotProcessed;
    408   TheDead.erase(sym);
    409   markDependentsLive(sym);
    410 }
    411 
    412 void SymbolReaper::markLive(const MemRegion *region) {
    413   RegionRoots.insert(region);
    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   return false;
    455 }
    456 
    457 bool SymbolReaper::isLive(SymbolRef sym) {
    458   if (TheLiving.count(sym)) {
    459     markDependentsLive(sym);
    460     return true;
    461   }
    462 
    463   if (const SymbolDerived *derived = dyn_cast<SymbolDerived>(sym)) {
    464     if (isLive(derived->getParentSymbol())) {
    465       markLive(sym);
    466       return true;
    467     }
    468     return false;
    469   }
    470 
    471   if (const SymbolExtent *extent = dyn_cast<SymbolExtent>(sym)) {
    472     if (isLiveRegion(extent->getRegion())) {
    473       markLive(sym);
    474       return true;
    475     }
    476     return false;
    477   }
    478 
    479   if (const SymbolMetadata *metadata = dyn_cast<SymbolMetadata>(sym)) {
    480     if (MetadataInUse.count(sym)) {
    481       if (isLiveRegion(metadata->getRegion())) {
    482         markLive(sym);
    483         MetadataInUse.erase(sym);
    484         return true;
    485       }
    486     }
    487     return false;
    488   }
    489 
    490   // Interogate the symbol.  It may derive from an input value to
    491   // the analyzed function/method.
    492   return isa<SymbolRegionValue>(sym);
    493 }
    494 
    495 bool
    496 SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const {
    497   if (LCtx != ELCtx) {
    498     // If the reaper's location context is a parent of the expression's
    499     // location context, then the expression value is now "out of scope".
    500     if (LCtx->isParentOf(ELCtx))
    501       return false;
    502     return true;
    503   }
    504 
    505   return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
    506 }
    507 
    508 bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
    509   const StackFrameContext *VarContext = VR->getStackFrame();
    510   const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame();
    511 
    512   if (VarContext == CurrentContext) {
    513     if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
    514       return true;
    515 
    516     if (!includeStoreBindings)
    517       return false;
    518 
    519     unsigned &cachedQuery =
    520       const_cast<SymbolReaper*>(this)->includedRegionCache[VR];
    521 
    522     if (cachedQuery) {
    523       return cachedQuery == 1;
    524     }
    525 
    526     // Query the store to see if the region occurs in any live bindings.
    527     if (Store store = reapedStore.getStore()) {
    528       bool hasRegion =
    529         reapedStore.getStoreManager().includedInBindings(store, VR);
    530       cachedQuery = hasRegion ? 1 : 2;
    531       return hasRegion;
    532     }
    533 
    534     return false;
    535   }
    536 
    537   return VarContext->isParentOf(CurrentContext);
    538 }
    539 
    540 SymbolVisitor::~SymbolVisitor() {}
    541