Environment.cpp revision 234353
1218887Sdim//== Environment.cpp - Map from Stmt* to Locations/Values -------*- C++ -*--==// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defined the Environment and EnvironmentManager classes. 11218887Sdim// 12218887Sdim//===----------------------------------------------------------------------===// 13218887Sdim 14234353Sdim#include "clang/AST/ExprCXX.h" 15226633Sdim#include "clang/AST/ExprObjC.h" 16218887Sdim#include "clang/Analysis/AnalysisContext.h" 17218887Sdim#include "clang/Analysis/CFG.h" 18226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 19218887Sdim 20218887Sdimusing namespace clang; 21218887Sdimusing namespace ento; 22218887Sdim 23234353SdimSVal Environment::lookupExpr(const EnvironmentEntry &E) const { 24218887Sdim const SVal* X = ExprBindings.lookup(E); 25218887Sdim if (X) { 26218887Sdim SVal V = *X; 27218887Sdim return V; 28218887Sdim } 29218887Sdim return UnknownVal(); 30218887Sdim} 31218887Sdim 32234353SdimSVal Environment::getSVal(const EnvironmentEntry &Entry, 33234353Sdim SValBuilder& svalBuilder, 34234353Sdim bool useOnlyDirectBindings) const { 35221345Sdim 36221345Sdim if (useOnlyDirectBindings) { 37221345Sdim // This branch is rarely taken, but can be exercised by 38221345Sdim // checkers that explicitly bind values to arbitrary 39221345Sdim // expressions. It is crucial that we do not ignore any 40221345Sdim // expression here, and do a direct lookup. 41234353Sdim return lookupExpr(Entry); 42221345Sdim } 43221345Sdim 44234353Sdim const Stmt *E = Entry.getStmt(); 45234353Sdim const LocationContext *LCtx = Entry.getLocationContext(); 46234353Sdim 47218887Sdim for (;;) { 48223017Sdim if (const Expr *Ex = dyn_cast<Expr>(E)) 49223017Sdim E = Ex->IgnoreParens(); 50223017Sdim 51218887Sdim switch (E->getStmtClass()) { 52218887Sdim case Stmt::AddrLabelExprClass: 53218887Sdim return svalBuilder.makeLoc(cast<AddrLabelExpr>(E)); 54219077Sdim case Stmt::OpaqueValueExprClass: { 55219077Sdim const OpaqueValueExpr *ope = cast<OpaqueValueExpr>(E); 56219077Sdim E = ope->getSourceExpr(); 57219077Sdim continue; 58219077Sdim } 59218887Sdim case Stmt::ParenExprClass: 60221345Sdim case Stmt::GenericSelectionExprClass: 61223017Sdim llvm_unreachable("ParenExprs and GenericSelectionExprs should " 62223017Sdim "have been handled by IgnoreParens()"); 63218887Sdim case Stmt::CharacterLiteralClass: { 64218887Sdim const CharacterLiteral* C = cast<CharacterLiteral>(E); 65218887Sdim return svalBuilder.makeIntVal(C->getValue(), C->getType()); 66218887Sdim } 67218887Sdim case Stmt::CXXBoolLiteralExprClass: { 68234353Sdim const SVal *X = ExprBindings.lookup(EnvironmentEntry(E, LCtx)); 69218887Sdim if (X) 70218887Sdim return *X; 71218887Sdim else 72218887Sdim return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(E)); 73218887Sdim } 74218887Sdim case Stmt::IntegerLiteralClass: { 75218887Sdim // In C++, this expression may have been bound to a temporary object. 76234353Sdim SVal const *X = ExprBindings.lookup(EnvironmentEntry(E, LCtx)); 77218887Sdim if (X) 78218887Sdim return *X; 79218887Sdim else 80218887Sdim return svalBuilder.makeIntVal(cast<IntegerLiteral>(E)); 81218887Sdim } 82234353Sdim case Stmt::ObjCBoolLiteralExprClass: 83234353Sdim return svalBuilder.makeBoolVal(cast<ObjCBoolLiteralExpr>(E)); 84234353Sdim 85221345Sdim // For special C0xx nullptr case, make a null pointer SVal. 86221345Sdim case Stmt::CXXNullPtrLiteralExprClass: 87221345Sdim return svalBuilder.makeNull(); 88218887Sdim case Stmt::ExprWithCleanupsClass: 89218887Sdim E = cast<ExprWithCleanups>(E)->getSubExpr(); 90218887Sdim continue; 91218887Sdim case Stmt::CXXBindTemporaryExprClass: 92218887Sdim E = cast<CXXBindTemporaryExpr>(E)->getSubExpr(); 93218887Sdim continue; 94226633Sdim case Stmt::ObjCPropertyRefExprClass: 95226633Sdim return loc::ObjCPropRef(cast<ObjCPropertyRefExpr>(E)); 96234353Sdim case Stmt::ObjCStringLiteralClass: { 97234353Sdim MemRegionManager &MRMgr = svalBuilder.getRegionManager(); 98234353Sdim const ObjCStringLiteral *SL = cast<ObjCStringLiteral>(E); 99234353Sdim return svalBuilder.makeLoc(MRMgr.getObjCStringRegion(SL)); 100234353Sdim } 101234353Sdim case Stmt::StringLiteralClass: { 102234353Sdim MemRegionManager &MRMgr = svalBuilder.getRegionManager(); 103234353Sdim const StringLiteral *SL = cast<StringLiteral>(E); 104234353Sdim return svalBuilder.makeLoc(MRMgr.getStringRegion(SL)); 105234353Sdim } 106234353Sdim case Stmt::ReturnStmtClass: { 107234353Sdim const ReturnStmt *RS = cast<ReturnStmt>(E); 108234353Sdim if (const Expr *RE = RS->getRetValue()) { 109234353Sdim E = RE; 110234353Sdim continue; 111234353Sdim } 112234353Sdim return UndefinedVal(); 113234353Sdim } 114226633Sdim 115218887Sdim // Handle all other Stmt* using a lookup. 116218887Sdim default: 117218887Sdim break; 118218887Sdim }; 119218887Sdim break; 120218887Sdim } 121234353Sdim return lookupExpr(EnvironmentEntry(E, LCtx)); 122218887Sdim} 123218887Sdim 124234353SdimEnvironment EnvironmentManager::bindExpr(Environment Env, 125234353Sdim const EnvironmentEntry &E, 126234353Sdim SVal V, 127234353Sdim bool Invalidate) { 128218887Sdim if (V.isUnknown()) { 129218887Sdim if (Invalidate) 130234353Sdim return Environment(F.remove(Env.ExprBindings, E)); 131218887Sdim else 132218887Sdim return Env; 133218887Sdim } 134234353Sdim return Environment(F.add(Env.ExprBindings, E, V)); 135218887Sdim} 136218887Sdim 137234353Sdimstatic inline EnvironmentEntry MakeLocation(const EnvironmentEntry &E) { 138234353Sdim const Stmt *S = E.getStmt(); 139234353Sdim S = (const Stmt*) (((uintptr_t) S) | 0x1); 140234353Sdim return EnvironmentEntry(S, E.getLocationContext()); 141218887Sdim} 142218887Sdim 143218887SdimEnvironment EnvironmentManager::bindExprAndLocation(Environment Env, 144234353Sdim const EnvironmentEntry &E, 145218887Sdim SVal location, SVal V) { 146234353Sdim return Environment(F.add(F.add(Env.ExprBindings, MakeLocation(E), location), 147234353Sdim E, V)); 148218887Sdim} 149218887Sdim 150218887Sdimnamespace { 151218887Sdimclass MarkLiveCallback : public SymbolVisitor { 152218887Sdim SymbolReaper &SymReaper; 153218887Sdimpublic: 154218887Sdim MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {} 155234353Sdim bool VisitSymbol(SymbolRef sym) { 156234353Sdim SymReaper.markLive(sym); 157234353Sdim return true; 158234353Sdim } 159234353Sdim bool VisitMemRegion(const MemRegion *R) { 160234353Sdim SymReaper.markLive(R); 161234353Sdim return true; 162234353Sdim } 163218887Sdim}; 164218887Sdim} // end anonymous namespace 165218887Sdim 166234353Sdim// In addition to mapping from EnvironmentEntry - > SVals in the Environment, 167234353Sdim// we also maintain a mapping from EnvironmentEntry -> SVals (locations) 168234353Sdim// that were used during a load and store. 169234353Sdimstatic inline bool IsLocation(const EnvironmentEntry &E) { 170234353Sdim const Stmt *S = E.getStmt(); 171218887Sdim return (bool) (((uintptr_t) S) & 0x1); 172218887Sdim} 173218887Sdim 174218887Sdim// removeDeadBindings: 175218887Sdim// - Remove subexpression bindings. 176218887Sdim// - Remove dead block expression bindings. 177218887Sdim// - Keep live block expression bindings: 178218887Sdim// - Mark their reachable symbols live in SymbolReaper, 179218887Sdim// see ScanReachableSymbols. 180218887Sdim// - Mark the region in DRoots if the binding is a loc::MemRegionVal. 181218887SdimEnvironment 182218887SdimEnvironmentManager::removeDeadBindings(Environment Env, 183218887Sdim SymbolReaper &SymReaper, 184234353Sdim ProgramStateRef ST) { 185218887Sdim 186218887Sdim // We construct a new Environment object entirely, as this is cheaper than 187218887Sdim // individually removing all the subexpression bindings (which will greatly 188218887Sdim // outnumber block-level expression bindings). 189218887Sdim Environment NewEnv = getInitialEnvironment(); 190218887Sdim 191234353Sdim SmallVector<std::pair<EnvironmentEntry, SVal>, 10> deferredLocations; 192218887Sdim 193226633Sdim MarkLiveCallback CB(SymReaper); 194226633Sdim ScanReachableSymbols RSScaner(ST, CB); 195226633Sdim 196234353Sdim llvm::ImmutableMapRef<EnvironmentEntry,SVal> 197226633Sdim EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(), 198226633Sdim F.getTreeFactory()); 199226633Sdim 200218887Sdim // Iterate over the block-expr bindings. 201218887Sdim for (Environment::iterator I = Env.begin(), E = Env.end(); 202218887Sdim I != E; ++I) { 203218887Sdim 204234353Sdim const EnvironmentEntry &BlkExpr = I.getKey(); 205218887Sdim // For recorded locations (used when evaluating loads and stores), we 206218887Sdim // consider them live only when their associated normal expression is 207218887Sdim // also live. 208218887Sdim // NOTE: This assumes that loads/stores that evaluated to UnknownVal 209218887Sdim // still have an entry in the map. 210218887Sdim if (IsLocation(BlkExpr)) { 211218887Sdim deferredLocations.push_back(std::make_pair(BlkExpr, I.getData())); 212218887Sdim continue; 213218887Sdim } 214218887Sdim const SVal &X = I.getData(); 215218887Sdim 216234353Sdim if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) { 217218887Sdim // Copy the binding to the new map. 218226633Sdim EBMapRef = EBMapRef.add(BlkExpr, X); 219218887Sdim 220218887Sdim // If the block expr's value is a memory region, then mark that region. 221218887Sdim if (isa<loc::MemRegionVal>(X)) { 222226633Sdim const MemRegion *R = cast<loc::MemRegionVal>(X).getRegion(); 223226633Sdim SymReaper.markLive(R); 224218887Sdim } 225218887Sdim 226218887Sdim // Mark all symbols in the block expr's value live. 227226633Sdim RSScaner.scan(X); 228218887Sdim continue; 229218887Sdim } 230218887Sdim 231218887Sdim // Otherwise the expression is dead with a couple exceptions. 232218887Sdim // Do not misclean LogicalExpr or ConditionalOperator. It is dead at the 233218887Sdim // beginning of itself, but we need its UndefinedVal to determine its 234218887Sdim // SVal. 235218887Sdim if (X.isUndef() && cast<UndefinedVal>(X).getData()) 236226633Sdim EBMapRef = EBMapRef.add(BlkExpr, X); 237218887Sdim } 238218887Sdim 239218887Sdim // Go through he deferred locations and add them to the new environment if 240218887Sdim // the correspond Stmt* is in the map as well. 241234353Sdim for (SmallVectorImpl<std::pair<EnvironmentEntry, SVal> >::iterator 242218887Sdim I = deferredLocations.begin(), E = deferredLocations.end(); I != E; ++I) { 243234353Sdim const EnvironmentEntry &En = I->first; 244234353Sdim const Stmt *S = (Stmt*) (((uintptr_t) En.getStmt()) & (uintptr_t) ~0x1); 245234353Sdim if (EBMapRef.lookup(EnvironmentEntry(S, En.getLocationContext()))) 246234353Sdim EBMapRef = EBMapRef.add(En, I->second); 247218887Sdim } 248218887Sdim 249226633Sdim NewEnv.ExprBindings = EBMapRef.asImmutableMap(); 250218887Sdim return NewEnv; 251218887Sdim} 252234353Sdim 253234353Sdimvoid Environment::print(raw_ostream &Out, const char *NL, 254234353Sdim const char *Sep) const { 255234353Sdim printAux(Out, false, NL, Sep); 256234353Sdim printAux(Out, true, NL, Sep); 257234353Sdim} 258234353Sdim 259234353Sdimvoid Environment::printAux(raw_ostream &Out, bool printLocations, 260234353Sdim const char *NL, 261234353Sdim const char *Sep) const{ 262234353Sdim 263234353Sdim bool isFirst = true; 264234353Sdim 265234353Sdim for (Environment::iterator I = begin(), E = end(); I != E; ++I) { 266234353Sdim const EnvironmentEntry &En = I.getKey(); 267234353Sdim if (IsLocation(En)) { 268234353Sdim if (!printLocations) 269234353Sdim continue; 270234353Sdim } 271234353Sdim else { 272234353Sdim if (printLocations) 273234353Sdim continue; 274234353Sdim } 275234353Sdim 276234353Sdim if (isFirst) { 277234353Sdim Out << NL << NL 278234353Sdim << (printLocations ? "Load/Store locations:" : "Expressions:") 279234353Sdim << NL; 280234353Sdim isFirst = false; 281234353Sdim } else { 282234353Sdim Out << NL; 283234353Sdim } 284234353Sdim 285234353Sdim const Stmt *S = En.getStmt(); 286234353Sdim if (printLocations) { 287234353Sdim S = (Stmt*) (((uintptr_t) S) & ((uintptr_t) ~0x1)); 288234353Sdim } 289234353Sdim 290234353Sdim Out << " (" << (void*) En.getLocationContext() << ',' << (void*) S << ") "; 291234353Sdim LangOptions LO; // FIXME. 292234353Sdim S->printPretty(Out, 0, PrintingPolicy(LO)); 293234353Sdim Out << " : " << I.getData(); 294234353Sdim } 295234353Sdim} 296