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), 57276479Sdim L ? L->getCurrentStackFrame() 58276479Sdim : nullptr) {} 59243830Sdim 60234353SdimSVal Environment::lookupExpr(const EnvironmentEntry &E) const { 61218887Sdim const SVal* X = ExprBindings.lookup(E); 62218887Sdim if (X) { 63218887Sdim SVal V = *X; 64218887Sdim return V; 65218887Sdim } 66218887Sdim return UnknownVal(); 67218887Sdim} 68218887Sdim 69234353SdimSVal Environment::getSVal(const EnvironmentEntry &Entry, 70243830Sdim SValBuilder& svalBuilder) const { 71243830Sdim const Stmt *S = Entry.getStmt(); 72243830Sdim const LocationContext *LCtx = Entry.getLocationContext(); 73221345Sdim 74243830Sdim switch (S->getStmtClass()) { 75243830Sdim case Stmt::CXXBindTemporaryExprClass: 76243830Sdim case Stmt::ExprWithCleanupsClass: 77243830Sdim case Stmt::GenericSelectionExprClass: 78243830Sdim case Stmt::OpaqueValueExprClass: 79243830Sdim case Stmt::ParenExprClass: 80243830Sdim case Stmt::SubstNonTypeTemplateParmExprClass: 81243830Sdim llvm_unreachable("Should have been handled by ignoreTransparentExprs"); 82243830Sdim 83243830Sdim case Stmt::AddrLabelExprClass: 84251662Sdim case Stmt::CharacterLiteralClass: 85243830Sdim case Stmt::CXXBoolLiteralExprClass: 86243830Sdim case Stmt::CXXScalarValueInitExprClass: 87251662Sdim case Stmt::ImplicitValueInitExprClass: 88243830Sdim case Stmt::IntegerLiteralClass: 89243830Sdim case Stmt::ObjCBoolLiteralExprClass: 90243830Sdim case Stmt::CXXNullPtrLiteralExprClass: 91251662Sdim case Stmt::ObjCStringLiteralClass: 92251662Sdim case Stmt::StringLiteralClass: 93296417Sdim case Stmt::TypeTraitExprClass: 94251662Sdim // Known constants; defer to SValBuilder. 95251662Sdim return svalBuilder.getConstantVal(cast<Expr>(S)).getValue(); 96243830Sdim 97243830Sdim case Stmt::ReturnStmtClass: { 98243830Sdim const ReturnStmt *RS = cast<ReturnStmt>(S); 99243830Sdim if (const Expr *RE = RS->getRetValue()) 100243830Sdim return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder); 101296417Sdim return UndefinedVal(); 102243830Sdim } 103296417Sdim 104243830Sdim // Handle all other Stmt* using a lookup. 105243830Sdim default: 106251662Sdim return lookupExpr(EnvironmentEntry(S, LCtx)); 107218887Sdim } 108218887Sdim} 109218887Sdim 110234353SdimEnvironment EnvironmentManager::bindExpr(Environment Env, 111234353Sdim const EnvironmentEntry &E, 112234353Sdim SVal V, 113234353Sdim bool Invalidate) { 114218887Sdim if (V.isUnknown()) { 115218887Sdim if (Invalidate) 116234353Sdim return Environment(F.remove(Env.ExprBindings, E)); 117218887Sdim else 118218887Sdim return Env; 119218887Sdim } 120234353Sdim return Environment(F.add(Env.ExprBindings, E, V)); 121218887Sdim} 122218887Sdim 123218887Sdimnamespace { 124296417Sdimclass MarkLiveCallback final : public SymbolVisitor { 125218887Sdim SymbolReaper &SymReaper; 126218887Sdimpublic: 127218887Sdim MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {} 128276479Sdim bool VisitSymbol(SymbolRef sym) override { 129234353Sdim SymReaper.markLive(sym); 130234353Sdim return true; 131234353Sdim } 132276479Sdim bool VisitMemRegion(const MemRegion *R) override { 133234353Sdim SymReaper.markLive(R); 134234353Sdim return true; 135234353Sdim } 136218887Sdim}; 137218887Sdim} // end anonymous namespace 138218887Sdim 139218887Sdim// removeDeadBindings: 140218887Sdim// - Remove subexpression bindings. 141218887Sdim// - Remove dead block expression bindings. 142218887Sdim// - Keep live block expression bindings: 143218887Sdim// - Mark their reachable symbols live in SymbolReaper, 144218887Sdim// see ScanReachableSymbols. 145218887Sdim// - Mark the region in DRoots if the binding is a loc::MemRegionVal. 146218887SdimEnvironment 147218887SdimEnvironmentManager::removeDeadBindings(Environment Env, 148218887Sdim SymbolReaper &SymReaper, 149234353Sdim ProgramStateRef ST) { 150218887Sdim 151218887Sdim // We construct a new Environment object entirely, as this is cheaper than 152218887Sdim // individually removing all the subexpression bindings (which will greatly 153218887Sdim // outnumber block-level expression bindings). 154218887Sdim Environment NewEnv = getInitialEnvironment(); 155218887Sdim 156226633Sdim MarkLiveCallback CB(SymReaper); 157226633Sdim ScanReachableSymbols RSScaner(ST, CB); 158226633Sdim 159234353Sdim llvm::ImmutableMapRef<EnvironmentEntry,SVal> 160226633Sdim EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(), 161226633Sdim F.getTreeFactory()); 162226633Sdim 163218887Sdim // Iterate over the block-expr bindings. 164218887Sdim for (Environment::iterator I = Env.begin(), E = Env.end(); 165218887Sdim I != E; ++I) { 166218887Sdim 167234353Sdim const EnvironmentEntry &BlkExpr = I.getKey(); 168218887Sdim const SVal &X = I.getData(); 169218887Sdim 170234353Sdim if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) { 171218887Sdim // Copy the binding to the new map. 172226633Sdim EBMapRef = EBMapRef.add(BlkExpr, X); 173218887Sdim 174218887Sdim // Mark all symbols in the block expr's value live. 175226633Sdim RSScaner.scan(X); 176218887Sdim continue; 177249423Sdim } else { 178249423Sdim SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); 179249423Sdim for (; SI != SE; ++SI) 180249423Sdim SymReaper.maybeDead(*SI); 181218887Sdim } 182218887Sdim } 183218887Sdim 184226633Sdim NewEnv.ExprBindings = EBMapRef.asImmutableMap(); 185218887Sdim return NewEnv; 186218887Sdim} 187234353Sdim 188234353Sdimvoid Environment::print(raw_ostream &Out, const char *NL, 189234353Sdim const char *Sep) const { 190234353Sdim bool isFirst = true; 191234353Sdim 192234353Sdim for (Environment::iterator I = begin(), E = end(); I != E; ++I) { 193234353Sdim const EnvironmentEntry &En = I.getKey(); 194296417Sdim 195234353Sdim if (isFirst) { 196234353Sdim Out << NL << NL 197249423Sdim << "Expressions:" 198296417Sdim << NL; 199234353Sdim isFirst = false; 200234353Sdim } else { 201234353Sdim Out << NL; 202234353Sdim } 203296417Sdim 204234353Sdim const Stmt *S = En.getStmt(); 205276479Sdim assert(S != nullptr && "Expected non-null Stmt"); 206276479Sdim 207243830Sdim Out << " (" << (const void*) En.getLocationContext() << ',' 208243830Sdim << (const void*) S << ") "; 209234353Sdim LangOptions LO; // FIXME. 210276479Sdim S->printPretty(Out, nullptr, PrintingPolicy(LO)); 211234353Sdim Out << " : " << I.getData(); 212234353Sdim } 213234353Sdim} 214