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