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