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