Environment.cpp revision 7affe151f5689b2d3547b8947c4099532c78a021
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 case Stmt::CXXDefaultArgExprClass: 41 E = cast<CXXDefaultArgExpr>(E)->getExpr(); 42 break; 43 default: 44 // This is the base case: we can't look through more than we already have. 45 return E; 46 } 47 48 return ignoreTransparentExprs(E); 49} 50 51static const Stmt *ignoreTransparentExprs(const Stmt *S) { 52 if (const Expr *E = dyn_cast<Expr>(S)) 53 return ignoreTransparentExprs(E); 54 return S; 55} 56 57EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L) 58 : std::pair<const Stmt *, 59 const StackFrameContext *>(ignoreTransparentExprs(S), 60 L ? L->getCurrentStackFrame() : 0) {} 61 62SVal Environment::lookupExpr(const EnvironmentEntry &E) const { 63 const SVal* X = ExprBindings.lookup(E); 64 if (X) { 65 SVal V = *X; 66 return V; 67 } 68 return UnknownVal(); 69} 70 71SVal Environment::getSVal(const EnvironmentEntry &Entry, 72 SValBuilder& svalBuilder) const { 73 const Stmt *S = Entry.getStmt(); 74 const LocationContext *LCtx = Entry.getLocationContext(); 75 76 switch (S->getStmtClass()) { 77 case Stmt::CXXBindTemporaryExprClass: 78 case Stmt::CXXDefaultArgExprClass: 79 case Stmt::ExprWithCleanupsClass: 80 case Stmt::GenericSelectionExprClass: 81 case Stmt::OpaqueValueExprClass: 82 case Stmt::ParenExprClass: 83 case Stmt::SubstNonTypeTemplateParmExprClass: 84 llvm_unreachable("Should have been handled by ignoreTransparentExprs"); 85 86 case Stmt::AddrLabelExprClass: 87 return svalBuilder.makeLoc(cast<AddrLabelExpr>(S)); 88 89 case Stmt::CharacterLiteralClass: { 90 const CharacterLiteral *C = cast<CharacterLiteral>(S); 91 return svalBuilder.makeIntVal(C->getValue(), C->getType()); 92 } 93 94 case Stmt::CXXBoolLiteralExprClass: 95 return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(S)); 96 97 case Stmt::CXXScalarValueInitExprClass: 98 case Stmt::ImplicitValueInitExprClass: { 99 QualType Ty = cast<Expr>(S)->getType(); 100 return svalBuilder.makeZeroVal(Ty); 101 } 102 103 case Stmt::IntegerLiteralClass: 104 return svalBuilder.makeIntVal(cast<IntegerLiteral>(S)); 105 106 case Stmt::ObjCBoolLiteralExprClass: 107 return svalBuilder.makeBoolVal(cast<ObjCBoolLiteralExpr>(S)); 108 109 // For special C0xx nullptr case, make a null pointer SVal. 110 case Stmt::CXXNullPtrLiteralExprClass: 111 return svalBuilder.makeNull(); 112 113 case Stmt::ObjCStringLiteralClass: { 114 MemRegionManager &MRMgr = svalBuilder.getRegionManager(); 115 const ObjCStringLiteral *SL = cast<ObjCStringLiteral>(S); 116 return svalBuilder.makeLoc(MRMgr.getObjCStringRegion(SL)); 117 } 118 119 case Stmt::StringLiteralClass: { 120 MemRegionManager &MRMgr = svalBuilder.getRegionManager(); 121 const StringLiteral *SL = cast<StringLiteral>(S); 122 return svalBuilder.makeLoc(MRMgr.getStringRegion(SL)); 123 } 124 125 case Stmt::ReturnStmtClass: { 126 const ReturnStmt *RS = cast<ReturnStmt>(S); 127 if (const Expr *RE = RS->getRetValue()) 128 return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder); 129 return UndefinedVal(); 130 } 131 132 // Handle all other Stmt* using a lookup. 133 default: 134 break; 135 } 136 137 return lookupExpr(EnvironmentEntry(S, LCtx)); 138} 139 140Environment EnvironmentManager::bindExpr(Environment Env, 141 const EnvironmentEntry &E, 142 SVal V, 143 bool Invalidate) { 144 if (V.isUnknown()) { 145 if (Invalidate) 146 return Environment(F.remove(Env.ExprBindings, E)); 147 else 148 return Env; 149 } 150 return Environment(F.add(Env.ExprBindings, 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// removeDeadBindings: 170// - Remove subexpression bindings. 171// - Remove dead block expression bindings. 172// - Keep live block expression bindings: 173// - Mark their reachable symbols live in SymbolReaper, 174// see ScanReachableSymbols. 175// - Mark the region in DRoots if the binding is a loc::MemRegionVal. 176Environment 177EnvironmentManager::removeDeadBindings(Environment Env, 178 SymbolReaper &SymReaper, 179 ProgramStateRef ST) { 180 181 // We construct a new Environment object entirely, as this is cheaper than 182 // individually removing all the subexpression bindings (which will greatly 183 // outnumber block-level expression bindings). 184 Environment NewEnv = getInitialEnvironment(); 185 186 MarkLiveCallback CB(SymReaper); 187 ScanReachableSymbols RSScaner(ST, CB); 188 189 llvm::ImmutableMapRef<EnvironmentEntry,SVal> 190 EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(), 191 F.getTreeFactory()); 192 193 // Iterate over the block-expr bindings. 194 for (Environment::iterator I = Env.begin(), E = Env.end(); 195 I != E; ++I) { 196 197 const EnvironmentEntry &BlkExpr = I.getKey(); 198 const SVal &X = I.getData(); 199 200 if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) { 201 // Copy the binding to the new map. 202 EBMapRef = EBMapRef.add(BlkExpr, X); 203 204 // If the block expr's value is a memory region, then mark that region. 205 if (isa<loc::MemRegionVal>(X)) { 206 const MemRegion *R = cast<loc::MemRegionVal>(X).getRegion(); 207 SymReaper.markLive(R); 208 } 209 210 // Mark all symbols in the block expr's value live. 211 RSScaner.scan(X); 212 continue; 213 } else { 214 SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); 215 for (; SI != SE; ++SI) 216 SymReaper.maybeDead(*SI); 217 } 218 } 219 220 NewEnv.ExprBindings = EBMapRef.asImmutableMap(); 221 return NewEnv; 222} 223 224void Environment::print(raw_ostream &Out, const char *NL, 225 const char *Sep) const { 226 bool isFirst = true; 227 228 for (Environment::iterator I = begin(), E = end(); I != E; ++I) { 229 const EnvironmentEntry &En = I.getKey(); 230 231 if (isFirst) { 232 Out << NL << NL 233 << "Expressions:" 234 << NL; 235 isFirst = false; 236 } else { 237 Out << NL; 238 } 239 240 const Stmt *S = En.getStmt(); 241 242 Out << " (" << (const void*) En.getLocationContext() << ',' 243 << (const void*) S << ") "; 244 LangOptions LO; // FIXME. 245 S->printPretty(Out, 0, PrintingPolicy(LO)); 246 Out << " : " << I.getData(); 247 } 248} 249