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" 19249423Sdim#include "llvm/Support/raw_ostream.h" 20218887Sdim 21218887Sdimusing namespace clang; 22218887Sdimusing namespace ento; 23218887Sdim 24243830Sdimstatic const Expr *ignoreTransparentExprs(const Expr *E) { 25243830Sdim E = E->IgnoreParens(); 26243830Sdim 27243830Sdim switch (E->getStmtClass()) { 28243830Sdim case Stmt::OpaqueValueExprClass: 29243830Sdim E = cast<OpaqueValueExpr>(E)->getSourceExpr(); 30243830Sdim break; 31243830Sdim case Stmt::ExprWithCleanupsClass: 32243830Sdim E = cast<ExprWithCleanups>(E)->getSubExpr(); 33243830Sdim break; 34243830Sdim case Stmt::CXXBindTemporaryExprClass: 35243830Sdim E = cast<CXXBindTemporaryExpr>(E)->getSubExpr(); 36243830Sdim break; 37243830Sdim case Stmt::SubstNonTypeTemplateParmExprClass: 38243830Sdim E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement(); 39243830Sdim break; 40243830Sdim default: 41243830Sdim // This is the base case: we can't look through more than we already have. 42243830Sdim return E; 43243830Sdim } 44243830Sdim 45243830Sdim return ignoreTransparentExprs(E); 46243830Sdim} 47243830Sdim 48243830Sdimstatic const Stmt *ignoreTransparentExprs(const Stmt *S) { 49243830Sdim if (const Expr *E = dyn_cast<Expr>(S)) 50243830Sdim return ignoreTransparentExprs(E); 51243830Sdim return S; 52243830Sdim} 53243830Sdim 54243830SdimEnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L) 55243830Sdim : std::pair<const Stmt *, 56243830Sdim const StackFrameContext *>(ignoreTransparentExprs(S), 57243830Sdim L ? L->getCurrentStackFrame() : 0) {} 58243830Sdim 59234353SdimSVal Environment::lookupExpr(const EnvironmentEntry &E) const { 60218887Sdim const SVal* X = ExprBindings.lookup(E); 61218887Sdim if (X) { 62218887Sdim SVal V = *X; 63218887Sdim return V; 64218887Sdim } 65218887Sdim return UnknownVal(); 66218887Sdim} 67218887Sdim 68234353SdimSVal Environment::getSVal(const EnvironmentEntry &Entry, 69243830Sdim SValBuilder& svalBuilder) const { 70243830Sdim const Stmt *S = Entry.getStmt(); 71243830Sdim const LocationContext *LCtx = Entry.getLocationContext(); 72221345Sdim 73243830Sdim switch (S->getStmtClass()) { 74243830Sdim case Stmt::CXXBindTemporaryExprClass: 75243830Sdim case Stmt::ExprWithCleanupsClass: 76243830Sdim case Stmt::GenericSelectionExprClass: 77243830Sdim case Stmt::OpaqueValueExprClass: 78243830Sdim case Stmt::ParenExprClass: 79243830Sdim case Stmt::SubstNonTypeTemplateParmExprClass: 80243830Sdim llvm_unreachable("Should have been handled by ignoreTransparentExprs"); 81243830Sdim 82243830Sdim case Stmt::AddrLabelExprClass: 83251662Sdim case Stmt::CharacterLiteralClass: 84243830Sdim case Stmt::CXXBoolLiteralExprClass: 85243830Sdim case Stmt::CXXScalarValueInitExprClass: 86251662Sdim case Stmt::ImplicitValueInitExprClass: 87243830Sdim case Stmt::IntegerLiteralClass: 88243830Sdim case Stmt::ObjCBoolLiteralExprClass: 89243830Sdim case Stmt::CXXNullPtrLiteralExprClass: 90251662Sdim case Stmt::ObjCStringLiteralClass: 91251662Sdim case Stmt::StringLiteralClass: 92251662Sdim // Known constants; defer to SValBuilder. 93251662Sdim return svalBuilder.getConstantVal(cast<Expr>(S)).getValue(); 94243830Sdim 95243830Sdim case Stmt::ReturnStmtClass: { 96243830Sdim const ReturnStmt *RS = cast<ReturnStmt>(S); 97243830Sdim if (const Expr *RE = RS->getRetValue()) 98243830Sdim return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder); 99243830Sdim return UndefinedVal(); 100243830Sdim } 101243830Sdim 102243830Sdim // Handle all other Stmt* using a lookup. 103243830Sdim default: 104251662Sdim return lookupExpr(EnvironmentEntry(S, LCtx)); 105218887Sdim } 106218887Sdim} 107218887Sdim 108234353SdimEnvironment EnvironmentManager::bindExpr(Environment Env, 109234353Sdim const EnvironmentEntry &E, 110234353Sdim SVal V, 111234353Sdim bool Invalidate) { 112218887Sdim if (V.isUnknown()) { 113218887Sdim if (Invalidate) 114234353Sdim return Environment(F.remove(Env.ExprBindings, E)); 115218887Sdim else 116218887Sdim return Env; 117218887Sdim } 118234353Sdim return Environment(F.add(Env.ExprBindings, E, V)); 119218887Sdim} 120218887Sdim 121218887Sdimnamespace { 122218887Sdimclass MarkLiveCallback : public SymbolVisitor { 123218887Sdim SymbolReaper &SymReaper; 124218887Sdimpublic: 125218887Sdim MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {} 126234353Sdim bool VisitSymbol(SymbolRef sym) { 127234353Sdim SymReaper.markLive(sym); 128234353Sdim return true; 129234353Sdim } 130234353Sdim bool VisitMemRegion(const MemRegion *R) { 131234353Sdim SymReaper.markLive(R); 132234353Sdim return true; 133234353Sdim } 134218887Sdim}; 135218887Sdim} // end anonymous namespace 136218887Sdim 137218887Sdim// removeDeadBindings: 138218887Sdim// - Remove subexpression bindings. 139218887Sdim// - Remove dead block expression bindings. 140218887Sdim// - Keep live block expression bindings: 141218887Sdim// - Mark their reachable symbols live in SymbolReaper, 142218887Sdim// see ScanReachableSymbols. 143218887Sdim// - Mark the region in DRoots if the binding is a loc::MemRegionVal. 144218887SdimEnvironment 145218887SdimEnvironmentManager::removeDeadBindings(Environment Env, 146218887Sdim SymbolReaper &SymReaper, 147234353Sdim ProgramStateRef ST) { 148218887Sdim 149218887Sdim // We construct a new Environment object entirely, as this is cheaper than 150218887Sdim // individually removing all the subexpression bindings (which will greatly 151218887Sdim // outnumber block-level expression bindings). 152218887Sdim Environment NewEnv = getInitialEnvironment(); 153218887Sdim 154226633Sdim MarkLiveCallback CB(SymReaper); 155226633Sdim ScanReachableSymbols RSScaner(ST, CB); 156226633Sdim 157234353Sdim llvm::ImmutableMapRef<EnvironmentEntry,SVal> 158226633Sdim EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(), 159226633Sdim F.getTreeFactory()); 160226633Sdim 161218887Sdim // Iterate over the block-expr bindings. 162218887Sdim for (Environment::iterator I = Env.begin(), E = Env.end(); 163218887Sdim I != E; ++I) { 164218887Sdim 165234353Sdim const EnvironmentEntry &BlkExpr = I.getKey(); 166218887Sdim const SVal &X = I.getData(); 167218887Sdim 168234353Sdim if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) { 169218887Sdim // Copy the binding to the new map. 170226633Sdim EBMapRef = EBMapRef.add(BlkExpr, X); 171218887Sdim 172218887Sdim // If the block expr's value is a memory region, then mark that region. 173249423Sdim if (Optional<loc::MemRegionVal> R = X.getAs<loc::MemRegionVal>()) 174249423Sdim SymReaper.markLive(R->getRegion()); 175218887Sdim 176218887Sdim // Mark all symbols in the block expr's value live. 177226633Sdim RSScaner.scan(X); 178218887Sdim continue; 179249423Sdim } else { 180249423Sdim SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); 181249423Sdim for (; SI != SE; ++SI) 182249423Sdim SymReaper.maybeDead(*SI); 183218887Sdim } 184218887Sdim } 185218887Sdim 186226633Sdim NewEnv.ExprBindings = EBMapRef.asImmutableMap(); 187218887Sdim return NewEnv; 188218887Sdim} 189234353Sdim 190234353Sdimvoid Environment::print(raw_ostream &Out, const char *NL, 191234353Sdim const char *Sep) const { 192234353Sdim bool isFirst = true; 193234353Sdim 194234353Sdim for (Environment::iterator I = begin(), E = end(); I != E; ++I) { 195234353Sdim const EnvironmentEntry &En = I.getKey(); 196234353Sdim 197234353Sdim if (isFirst) { 198234353Sdim Out << NL << NL 199249423Sdim << "Expressions:" 200234353Sdim << NL; 201234353Sdim isFirst = false; 202234353Sdim } else { 203234353Sdim Out << NL; 204234353Sdim } 205234353Sdim 206234353Sdim const Stmt *S = En.getStmt(); 207234353Sdim 208243830Sdim Out << " (" << (const void*) En.getLocationContext() << ',' 209243830Sdim << (const void*) S << ") "; 210234353Sdim LangOptions LO; // FIXME. 211234353Sdim S->printPretty(Out, 0, PrintingPolicy(LO)); 212234353Sdim Out << " : " << I.getData(); 213234353Sdim } 214234353Sdim} 215