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