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