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/Analysis/AnalysisContext.h"
  15 #include "clang/Analysis/CFG.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h"
  17
  18 using namespace clang;
  19 using namespace ento;
  20
  21 SVal Environment::lookupExpr(const Stmt* E) const {
  22   const SVal* X = ExprBindings.lookup(E);
  23   if (X) {
  24     SVal V = *X;
  25     return V;
  26   }
  27   return UnknownVal();
  28 }
  29
  30 SVal Environment::getSVal(const Stmt *E, SValBuilder& svalBuilder,
  31                           bool useOnlyDirectBindings) const {
  32
  33   if (useOnlyDirectBindings) {
  34     // This branch is rarely taken, but can be exercised by
  35     // checkers that explicitly bind values to arbitrary
  36     // expressions.  It is crucial that we do not ignore any
  37     // expression here, and do a direct lookup.
  38     return lookupExpr(E);
  39   }
  40
  41   for (;;) {
  42     if (const Expr *Ex = dyn_cast<Expr>(E))
  43       E = Ex->IgnoreParens();
  44
  45     switch (E->getStmtClass()) {
  46       case Stmt::AddrLabelExprClass:
  47         return svalBuilder.makeLoc(cast<AddrLabelExpr>(E));
  48       case Stmt::OpaqueValueExprClass: {
  49         const OpaqueValueExpr *ope = cast<OpaqueValueExpr>(E);
  50         E = ope->getSourceExpr();
  51         continue;
  52       }
  53       case Stmt::ParenExprClass:
  54       case Stmt::GenericSelectionExprClass:
  55         llvm_unreachable("ParenExprs and GenericSelectionExprs should "
  56                          "have been handled by IgnoreParens()");
  57         return UnknownVal();
  58       case Stmt::CharacterLiteralClass: {
  59         const CharacterLiteral* C = cast<CharacterLiteral>(E);
  60         return svalBuilder.makeIntVal(C->getValue(), C->getType());
  61       }
  62       case Stmt::CXXBoolLiteralExprClass: {
  63         const SVal *X = ExprBindings.lookup(E);
  64         if (X)
  65           return *X;
  66         else
  67           return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(E));
  68       }
  69       case Stmt::IntegerLiteralClass: {
  70         // In C++, this expression may have been bound to a temporary object.
  71         SVal const *X = ExprBindings.lookup(E);
  72         if (X)
  73           return *X;
  74         else
  75           return svalBuilder.makeIntVal(cast<IntegerLiteral>(E));
  76       }
  77       // For special C0xx nullptr case, make a null pointer SVal.
  78       case Stmt::CXXNullPtrLiteralExprClass:
  79         return svalBuilder.makeNull();
  80       case Stmt::ExprWithCleanupsClass:
  81         E = cast<ExprWithCleanups>(E)->getSubExpr();
  82         continue;
  83       case Stmt::CXXBindTemporaryExprClass:
  84         E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
  85         continue;
  86       case Stmt::MaterializeTemporaryExprClass:
  87         E = cast<MaterializeTemporaryExpr>(E)->GetTemporaryExpr();
  88         continue;
  89       // Handle all other Stmt* using a lookup.
  90       default:
  91         break;
  92     };
  93     break;
  94   }
  95   return lookupExpr(E);
  96 }
  97
  98 Environment EnvironmentManager::bindExpr(Environment Env, const Stmt *S,
  99                                          SVal V, bool Invalidate) {
 100   assert(S);
 101
 102   if (V.isUnknown()) {
 103     if (Invalidate)
 104       return Environment(F.remove(Env.ExprBindings, S));
 105     else
 106       return Env;
 107   }
 108
 109   return Environment(F.add(Env.ExprBindings, S, V));
 110 }
 111
 112 static inline const Stmt *MakeLocation(const Stmt *S) {
 113   return (const Stmt*) (((uintptr_t) S) | 0x1);
 114 }
 115
 116 Environment EnvironmentManager::bindExprAndLocation(Environment Env,
 117                                                     const Stmt *S,
 118                                                     SVal location, SVal V) {
 119   return Environment(F.add(F.add(Env.ExprBindings, MakeLocation(S), location),
 120                            S, V));
 121 }
 122
 123 namespace {
 124 class MarkLiveCallback : public SymbolVisitor {
 125   SymbolReaper &SymReaper;
 126 public:
 127   MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
 128   bool VisitSymbol(SymbolRef sym) { SymReaper.markLive(sym); return true; }
 129 };
 130 } // end anonymous namespace
 131
 132 static bool isBlockExprInCallers(const Stmt *E, const LocationContext *LC) {
 133   const LocationContext *ParentLC = LC->getParent();
 134   while (ParentLC) {
 135     CFG &C = *ParentLC->getCFG();
 136     if (C.isBlkExpr(E))
 137       return true;
 138     ParentLC = ParentLC->getParent();
 139   }
 140
 141   return false;
 142 }
 143
 144 // In addition to mapping from Stmt * - > SVals in the Environment, we also
 145 // maintain a mapping from Stmt * -> SVals (locations) that were used during
 146 // a load and store.
 147 static inline bool IsLocation(const Stmt *S) {
 148   return (bool) (((uintptr_t) S) & 0x1);
 149 }
 150
 151 // removeDeadBindings:
 152 //  - Remove subexpression bindings.
 153 //  - Remove dead block expression bindings.
 154 //  - Keep live block expression bindings:
 155 //   - Mark their reachable symbols live in SymbolReaper,
 156 //     see ScanReachableSymbols.
 157 //   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
 158 Environment
 159 EnvironmentManager::removeDeadBindings(Environment Env,
 160                                        SymbolReaper &SymReaper,
 161                                        const GRState *ST,
 162                               llvm::SmallVectorImpl<const MemRegion*> &DRoots) {
 163
 164   CFG &C = *SymReaper.getLocationContext()->getCFG();
 165
 166   // We construct a new Environment object entirely, as this is cheaper than
 167   // individually removing all the subexpression bindings (which will greatly
 168   // outnumber block-level expression bindings).
 169   Environment NewEnv = getInitialEnvironment();
 170
 171   llvm::SmallVector<std::pair<const Stmt*, SVal>, 10> deferredLocations;
 172
 173   // Iterate over the block-expr bindings.
 174   for (Environment::iterator I = Env.begin(), E = Env.end();
 175        I != E; ++I) {
 176
 177     const Stmt *BlkExpr = I.getKey();
 178
 179     // For recorded locations (used when evaluating loads and stores), we
 180     // consider them live only when their associated normal expression is
 181     // also live.
 182     // NOTE: This assumes that loads/stores that evaluated to UnknownVal
 183     // still have an entry in the map.
 184     if (IsLocation(BlkExpr)) {
 185       deferredLocations.push_back(std::make_pair(BlkExpr, I.getData()));
 186       continue;
 187     }
 188
 189     const SVal &X = I.getData();
 190
 191     // Block-level expressions in callers are assumed always live.
 192     if (isBlockExprInCallers(BlkExpr, SymReaper.getLocationContext())) {
 193       NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, BlkExpr, X);
 194
 195       if (isa<loc::MemRegionVal>(X)) {
 196         const MemRegion* R = cast<loc::MemRegionVal>(X).getRegion();
 197         DRoots.push_back(R);
 198       }
 199
 200       // Mark all symbols in the block expr's value live.
 201       MarkLiveCallback cb(SymReaper);
 202       ST->scanReachableSymbols(X, cb);
 203       continue;
 204     }
 205
 206     // Not a block-level expression?
 207     if (!C.isBlkExpr(BlkExpr))
 208       continue;
 209
 210     if (SymReaper.isLive(BlkExpr)) {
 211       // Copy the binding to the new map.
 212       NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, BlkExpr, X);
 213
 214       // If the block expr's value is a memory region, then mark that region.
 215       if (isa<loc::MemRegionVal>(X)) {
 216         const MemRegion* R = cast<loc::MemRegionVal>(X).getRegion();
 217         DRoots.push_back(R);
 218       }
 219
 220       // Mark all symbols in the block expr's value live.
 221       MarkLiveCallback cb(SymReaper);
 222       ST->scanReachableSymbols(X, cb);
 223       continue;
 224     }
 225
 226     // Otherwise the expression is dead with a couple exceptions.
 227     // Do not misclean LogicalExpr or ConditionalOperator.  It is dead at the
 228     // beginning of itself, but we need its UndefinedVal to determine its
 229     // SVal.
 230     if (X.isUndef() && cast<UndefinedVal>(X).getData())
 231       NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, BlkExpr, X);
 232   }
 233
 234   // Go through he deferred locations and add them to the new environment if
 235   // the correspond Stmt* is in the map as well.
 236   for (llvm::SmallVectorImpl<std::pair<const Stmt*, SVal> >::iterator
 237       I = deferredLocations.begin(), E = deferredLocations.end(); I != E; ++I) {
 238     const Stmt *S = (Stmt*) (((uintptr_t) I->first) & (uintptr_t) ~0x1);
 239     if (NewEnv.ExprBindings.lookup(S))
 240       NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, I->first, I->second);
 241   }
 242
 243   return NewEnv;
 244 }