contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/Environment.cpp

   1 //== Environment.cpp - Map from Stmt* to Locations/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 defined the Environment and EnvironmentManager classes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/AST/ExprCXX.h"
  15 #include "clang/AST/ExprObjC.h"
  16 #include "clang/Analysis/AnalysisContext.h"
  17 #include "clang/Analysis/CFG.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  19
  20 using namespace clang;
  21 using namespace ento;
  22
  23 static const Expr *ignoreTransparentExprs(const Expr *E) {
  24   E = E->IgnoreParens();
  25
  26   switch (E->getStmtClass()) {
  27   case Stmt::OpaqueValueExprClass:
  28     E = cast<OpaqueValueExpr>(E)->getSourceExpr();
  29     break;
  30   case Stmt::ExprWithCleanupsClass:
  31     E = cast<ExprWithCleanups>(E)->getSubExpr();
  32     break;
  33   case Stmt::CXXBindTemporaryExprClass:
  34     E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
  35     break;
  36   case Stmt::SubstNonTypeTemplateParmExprClass:
  37     E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
  38     break;
  39   case Stmt::CXXDefaultArgExprClass:
  40     E = cast<CXXDefaultArgExpr>(E)->getExpr();
  41     break;
  42   default:
  43     // This is the base case: we can't look through more than we already have.
  44     return E;
  45   }
  46
  47   return ignoreTransparentExprs(E);
  48 }
  49
  50 static const Stmt *ignoreTransparentExprs(const Stmt *S) {
  51   if (const Expr *E = dyn_cast<Expr>(S))
  52     return ignoreTransparentExprs(E);
  53   return S;
  54 }
  55
  56 EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
  57   : std::pair<const Stmt *,
  58               const StackFrameContext *>(ignoreTransparentExprs(S),
  59                                          L ? L->getCurrentStackFrame() : 0) {}
  60
  61 SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
  62   const SVal* X = ExprBindings.lookup(E);
  63   if (X) {
  64     SVal V = *X;
  65     return V;
  66   }
  67   return UnknownVal();
  68 }
  69
  70 SVal Environment::getSVal(const EnvironmentEntry &Entry,
  71                           SValBuilder& svalBuilder) const {
  72   const Stmt *S = Entry.getStmt();
  73   const LocationContext *LCtx = Entry.getLocationContext();
  74
  75   switch (S->getStmtClass()) {
  76   case Stmt::CXXBindTemporaryExprClass:
  77   case Stmt::CXXDefaultArgExprClass:
  78   case Stmt::ExprWithCleanupsClass:
  79   case Stmt::GenericSelectionExprClass:
  80   case Stmt::OpaqueValueExprClass:
  81   case Stmt::ParenExprClass:
  82   case Stmt::SubstNonTypeTemplateParmExprClass:
  83     llvm_unreachable("Should have been handled by ignoreTransparentExprs");
  84
  85   case Stmt::AddrLabelExprClass:
  86     return svalBuilder.makeLoc(cast<AddrLabelExpr>(S));
  87
  88   case Stmt::CharacterLiteralClass: {
  89     const CharacterLiteral *C = cast<CharacterLiteral>(S);
  90     return svalBuilder.makeIntVal(C->getValue(), C->getType());
  91   }
  92
  93   case Stmt::CXXBoolLiteralExprClass:
  94     return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(S));
  95
  96   case Stmt::CXXScalarValueInitExprClass:
  97   case Stmt::ImplicitValueInitExprClass: {
  98     QualType Ty = cast<Expr>(S)->getType();
  99     return svalBuilder.makeZeroVal(Ty);
 100   }
 101
 102   case Stmt::IntegerLiteralClass:
 103     return svalBuilder.makeIntVal(cast<IntegerLiteral>(S));
 104
 105   case Stmt::ObjCBoolLiteralExprClass:
 106     return svalBuilder.makeBoolVal(cast<ObjCBoolLiteralExpr>(S));
 107
 108   // For special C0xx nullptr case, make a null pointer SVal.
 109   case Stmt::CXXNullPtrLiteralExprClass:
 110     return svalBuilder.makeNull();
 111
 112   case Stmt::ObjCStringLiteralClass: {
 113     MemRegionManager &MRMgr = svalBuilder.getRegionManager();
 114     const ObjCStringLiteral *SL = cast<ObjCStringLiteral>(S);
 115     return svalBuilder.makeLoc(MRMgr.getObjCStringRegion(SL));
 116   }
 117
 118   case Stmt::StringLiteralClass: {
 119     MemRegionManager &MRMgr = svalBuilder.getRegionManager();
 120     const StringLiteral *SL = cast<StringLiteral>(S);
 121     return svalBuilder.makeLoc(MRMgr.getStringRegion(SL));
 122   }
 123
 124   case Stmt::ReturnStmtClass: {
 125     const ReturnStmt *RS = cast<ReturnStmt>(S);
 126     if (const Expr *RE = RS->getRetValue())
 127       return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
 128     return UndefinedVal();
 129   }
 130
 131   // Handle all other Stmt* using a lookup.
 132   default:
 133     break;
 134   }
 135
 136   return lookupExpr(EnvironmentEntry(S, LCtx));
 137 }
 138
 139 Environment EnvironmentManager::bindExpr(Environment Env,
 140                                          const EnvironmentEntry &E,
 141                                          SVal V,
 142                                          bool Invalidate) {
 143   if (V.isUnknown()) {
 144     if (Invalidate)
 145       return Environment(F.remove(Env.ExprBindings, E));
 146     else
 147       return Env;
 148   }
 149   return Environment(F.add(Env.ExprBindings, E, V));
 150 }
 151
 152 EnvironmentEntry EnvironmentEntry::makeLocation() const {
 153   EnvironmentEntry Result = *this;
 154   reinterpret_cast<uintptr_t &>(Result.first) |= 0x1;
 155   return Result;
 156 }
 157
 158 Environment EnvironmentManager::bindExprAndLocation(Environment Env,
 159                                                     const EnvironmentEntry &E,
 160                                                     SVal location, SVal V) {
 161   return Environment(F.add(F.add(Env.ExprBindings, E.makeLocation(), location),
 162                            E, V));
 163 }
 164
 165 namespace {
 166 class MarkLiveCallback : public SymbolVisitor {
 167   SymbolReaper &SymReaper;
 168 public:
 169   MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
 170   bool VisitSymbol(SymbolRef sym) {
 171     SymReaper.markLive(sym);
 172     return true;
 173   }
 174   bool VisitMemRegion(const MemRegion *R) {
 175     SymReaper.markLive(R);
 176     return true;
 177   }
 178 };
 179 } // end anonymous namespace
 180
 181 // In addition to mapping from EnvironmentEntry - > SVals in the Environment,
 182 // we also maintain a mapping from EnvironmentEntry -> SVals (locations)
 183 // that were used during a load and store.
 184 static inline bool IsLocation(const EnvironmentEntry &E) {
 185   const Stmt *S = E.getStmt();
 186   return (bool) (((uintptr_t) S) & 0x1);
 187 }
 188
 189 // removeDeadBindings:
 190 //  - Remove subexpression bindings.
 191 //  - Remove dead block expression bindings.
 192 //  - Keep live block expression bindings:
 193 //   - Mark their reachable symbols live in SymbolReaper,
 194 //     see ScanReachableSymbols.
 195 //   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
 196 Environment
 197 EnvironmentManager::removeDeadBindings(Environment Env,
 198                                        SymbolReaper &SymReaper,
 199                                        ProgramStateRef ST) {
 200
 201   // We construct a new Environment object entirely, as this is cheaper than
 202   // individually removing all the subexpression bindings (which will greatly
 203   // outnumber block-level expression bindings).
 204   Environment NewEnv = getInitialEnvironment();
 205
 206   SmallVector<std::pair<EnvironmentEntry, SVal>, 10> deferredLocations;
 207
 208   MarkLiveCallback CB(SymReaper);
 209   ScanReachableSymbols RSScaner(ST, CB);
 210
 211   llvm::ImmutableMapRef<EnvironmentEntry,SVal>
 212     EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
 213              F.getTreeFactory());
 214
 215   // Iterate over the block-expr bindings.
 216   for (Environment::iterator I = Env.begin(), E = Env.end();
 217        I != E; ++I) {
 218
 219     const EnvironmentEntry &BlkExpr = I.getKey();
 220     // For recorded locations (used when evaluating loads and stores), we
 221     // consider them live only when their associated normal expression is
 222     // also live.
 223     // NOTE: This assumes that loads/stores that evaluated to UnknownVal
 224     // still have an entry in the map.
 225     if (IsLocation(BlkExpr)) {
 226       deferredLocations.push_back(std::make_pair(BlkExpr, I.getData()));
 227       continue;
 228     }
 229     const SVal &X = I.getData();
 230
 231     if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
 232       // Copy the binding to the new map.
 233       EBMapRef = EBMapRef.add(BlkExpr, X);
 234
 235       // If the block expr's value is a memory region, then mark that region.
 236       if (isa<loc::MemRegionVal>(X)) {
 237         const MemRegion *R = cast<loc::MemRegionVal>(X).getRegion();
 238         SymReaper.markLive(R);
 239       }
 240
 241       // Mark all symbols in the block expr's value live.
 242       RSScaner.scan(X);
 243       continue;
 244     }
 245   }
 246
 247   // Go through he deferred locations and add them to the new environment if
 248   // the correspond Stmt* is in the map as well.
 249   for (SmallVectorImpl<std::pair<EnvironmentEntry, SVal> >::iterator
 250       I = deferredLocations.begin(), E = deferredLocations.end(); I != E; ++I) {
 251     const EnvironmentEntry &En = I->first;
 252     const Stmt *S = (Stmt*) (((uintptr_t) En.getStmt()) & (uintptr_t) ~0x1);
 253     if (EBMapRef.lookup(EnvironmentEntry(S, En.getLocationContext())))
 254       EBMapRef = EBMapRef.add(En, I->second);
 255   }
 256
 257   NewEnv.ExprBindings = EBMapRef.asImmutableMap();
 258   return NewEnv;
 259 }
 260
 261 void Environment::print(raw_ostream &Out, const char *NL,
 262                         const char *Sep) const {
 263   printAux(Out, false, NL, Sep);
 264   printAux(Out, true, NL, Sep);
 265 }
 266
 267 void Environment::printAux(raw_ostream &Out, bool printLocations,
 268                            const char *NL,
 269                            const char *Sep) const{
 270
 271   bool isFirst = true;
 272
 273   for (Environment::iterator I = begin(), E = end(); I != E; ++I) {
 274     const EnvironmentEntry &En = I.getKey();
 275     if (IsLocation(En)) {
 276       if (!printLocations)
 277         continue;
 278     }
 279     else {
 280       if (printLocations)
 281         continue;
 282     }
 283
 284     if (isFirst) {
 285       Out << NL << NL
 286           << (printLocations ? "Load/Store locations:" : "Expressions:")
 287           << NL;
 288       isFirst = false;
 289     } else {
 290       Out << NL;
 291     }
 292
 293     const Stmt *S = En.getStmt();
 294     if (printLocations) {
 295       S = (Stmt*) (((uintptr_t) S) & ((uintptr_t) ~0x1));
 296     }
 297
 298     Out << " (" << (const void*) En.getLocationContext() << ','
 299       << (const void*) S << ") ";
 300     LangOptions LO; // FIXME.
 301     S->printPretty(Out, 0, PrintingPolicy(LO));
 302     Out << " : " << I.getData();
 303   }
 304 }