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#include "llvm/Support/raw_ostream.h" 20 21using namespace clang; 22using namespace ento; 23 24static const Expr *ignoreTransparentExprs(const Expr *E) { 25 E = E->IgnoreParens(); 26 27 switch (E->getStmtClass()) { 28 case Stmt::OpaqueValueExprClass: 29 E = cast<OpaqueValueExpr>(E)->getSourceExpr(); 30 break; 31 case Stmt::ExprWithCleanupsClass: 32 E = cast<ExprWithCleanups>(E)->getSubExpr(); 33 break; 34 case Stmt::CXXBindTemporaryExprClass: 35 E = cast<CXXBindTemporaryExpr>(E)->getSubExpr(); 36 break; 37 case Stmt::SubstNonTypeTemplateParmExprClass: 38 E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement(); 39 break; 40 default: 41 // This is the base case: we can't look through more than we already have. 42 return E; 43 } 44 45 return ignoreTransparentExprs(E); 46} 47 48static const Stmt *ignoreTransparentExprs(const Stmt *S) { 49 if (const Expr *E = dyn_cast<Expr>(S)) 50 return ignoreTransparentExprs(E); 51 return S; 52} 53 54EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L) 55 : std::pair<const Stmt *, 56 const StackFrameContext *>(ignoreTransparentExprs(S), 57 L ? L->getCurrentStackFrame() 58 : nullptr) {} 59 60SVal Environment::lookupExpr(const EnvironmentEntry &E) const { 61 const SVal* X = ExprBindings.lookup(E); 62 if (X) { 63 SVal V = *X; 64 return V; 65 } 66 return UnknownVal(); 67} 68 69SVal Environment::getSVal(const EnvironmentEntry &Entry, 70 SValBuilder& svalBuilder) const { 71 const Stmt *S = Entry.getStmt(); 72 const LocationContext *LCtx = Entry.getLocationContext(); 73 74 switch (S->getStmtClass()) { 75 case Stmt::CXXBindTemporaryExprClass: 76 case Stmt::ExprWithCleanupsClass: 77 case Stmt::GenericSelectionExprClass: 78 case Stmt::OpaqueValueExprClass: 79 case Stmt::ParenExprClass: 80 case Stmt::SubstNonTypeTemplateParmExprClass: 81 llvm_unreachable("Should have been handled by ignoreTransparentExprs"); 82 83 case Stmt::AddrLabelExprClass: 84 case Stmt::CharacterLiteralClass: 85 case Stmt::CXXBoolLiteralExprClass: 86 case Stmt::CXXScalarValueInitExprClass: 87 case Stmt::ImplicitValueInitExprClass: 88 case Stmt::IntegerLiteralClass: 89 case Stmt::ObjCBoolLiteralExprClass: 90 case Stmt::CXXNullPtrLiteralExprClass: 91 case Stmt::ObjCStringLiteralClass: 92 case Stmt::StringLiteralClass: 93 // Known constants; defer to SValBuilder. 94 return svalBuilder.getConstantVal(cast<Expr>(S)).getValue(); 95 96 case Stmt::ReturnStmtClass: { 97 const ReturnStmt *RS = cast<ReturnStmt>(S); 98 if (const Expr *RE = RS->getRetValue()) 99 return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder); 100 return UndefinedVal(); 101 } 102 103 // Handle all other Stmt* using a lookup. 104 default: 105 return lookupExpr(EnvironmentEntry(S, LCtx)); 106 } 107} 108 109Environment EnvironmentManager::bindExpr(Environment Env, 110 const EnvironmentEntry &E, 111 SVal V, 112 bool Invalidate) { 113 if (V.isUnknown()) { 114 if (Invalidate) 115 return Environment(F.remove(Env.ExprBindings, E)); 116 else 117 return Env; 118 } 119 return Environment(F.add(Env.ExprBindings, E, V)); 120} 121 122namespace { 123class MarkLiveCallback : public SymbolVisitor { 124 SymbolReaper &SymReaper; 125public: 126 MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {} 127 bool VisitSymbol(SymbolRef sym) override { 128 SymReaper.markLive(sym); 129 return true; 130 } 131 bool VisitMemRegion(const MemRegion *R) override { 132 SymReaper.markLive(R); 133 return true; 134 } 135}; 136} // end anonymous namespace 137 138// removeDeadBindings: 139// - Remove subexpression bindings. 140// - Remove dead block expression bindings. 141// - Keep live block expression bindings: 142// - Mark their reachable symbols live in SymbolReaper, 143// see ScanReachableSymbols. 144// - Mark the region in DRoots if the binding is a loc::MemRegionVal. 145Environment 146EnvironmentManager::removeDeadBindings(Environment Env, 147 SymbolReaper &SymReaper, 148 ProgramStateRef ST) { 149 150 // We construct a new Environment object entirely, as this is cheaper than 151 // individually removing all the subexpression bindings (which will greatly 152 // outnumber block-level expression bindings). 153 Environment NewEnv = getInitialEnvironment(); 154 155 MarkLiveCallback CB(SymReaper); 156 ScanReachableSymbols RSScaner(ST, CB); 157 158 llvm::ImmutableMapRef<EnvironmentEntry,SVal> 159 EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(), 160 F.getTreeFactory()); 161 162 // Iterate over the block-expr bindings. 163 for (Environment::iterator I = Env.begin(), E = Env.end(); 164 I != E; ++I) { 165 166 const EnvironmentEntry &BlkExpr = I.getKey(); 167 const SVal &X = I.getData(); 168 169 if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) { 170 // Copy the binding to the new map. 171 EBMapRef = EBMapRef.add(BlkExpr, X); 172 173 // If the block expr's value is a memory region, then mark that region. 174 if (Optional<loc::MemRegionVal> R = X.getAs<loc::MemRegionVal>()) 175 SymReaper.markLive(R->getRegion()); 176 177 // Mark all symbols in the block expr's value live. 178 RSScaner.scan(X); 179 continue; 180 } else { 181 SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); 182 for (; SI != SE; ++SI) 183 SymReaper.maybeDead(*SI); 184 } 185 } 186 187 NewEnv.ExprBindings = EBMapRef.asImmutableMap(); 188 return NewEnv; 189} 190 191void Environment::print(raw_ostream &Out, const char *NL, 192 const char *Sep) const { 193 bool isFirst = true; 194 195 for (Environment::iterator I = begin(), E = end(); I != E; ++I) { 196 const EnvironmentEntry &En = I.getKey(); 197 198 if (isFirst) { 199 Out << NL << NL 200 << "Expressions:" 201 << NL; 202 isFirst = false; 203 } else { 204 Out << NL; 205 } 206 207 const Stmt *S = En.getStmt(); 208 assert(S != nullptr && "Expected non-null Stmt"); 209 210 Out << " (" << (const void*) En.getLocationContext() << ',' 211 << (const void*) S << ") "; 212 LangOptions LO; // FIXME. 213 S->printPretty(Out, nullptr, PrintingPolicy(LO)); 214 Out << " : " << I.getData(); 215 } 216} 217