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