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 20 using namespace clang; 21 using namespace ento; 22 23 SVal Environment::lookupExpr(const EnvironmentEntry &E) const { 24 const SVal* X = ExprBindings.lookup(E); 25 if (X) { 26 SVal V = *X; 27 return V; 28 } 29 return UnknownVal(); 30 } 31 32 SVal Environment::getSVal(const EnvironmentEntry &Entry, 33 SValBuilder& svalBuilder, 34 bool useOnlyDirectBindings) const { 35 36 if (useOnlyDirectBindings) { 37 // This branch is rarely taken, but can be exercised by 38 // checkers that explicitly bind values to arbitrary 39 // expressions. It is crucial that we do not ignore any 40 // expression here, and do a direct lookup. 41 return lookupExpr(Entry); 42 } 43 44 const Stmt *E = Entry.getStmt(); 45 const LocationContext *LCtx = Entry.getLocationContext(); 46 47 for (;;) { 48 if (const Expr *Ex = dyn_cast<Expr>(E)) 49 E = Ex->IgnoreParens(); 50 51 switch (E->getStmtClass()) { 52 case Stmt::AddrLabelExprClass: 53 return svalBuilder.makeLoc(cast<AddrLabelExpr>(E)); 54 case Stmt::OpaqueValueExprClass: { 55 const OpaqueValueExpr *ope = cast<OpaqueValueExpr>(E); 56 E = ope->getSourceExpr(); 57 continue; 58 } 59 case Stmt::ParenExprClass: 60 case Stmt::GenericSelectionExprClass: 61 llvm_unreachable("ParenExprs and GenericSelectionExprs should " 62 "have been handled by IgnoreParens()"); 63 case Stmt::CharacterLiteralClass: { 64 const CharacterLiteral* C = cast<CharacterLiteral>(E); 65 return svalBuilder.makeIntVal(C->getValue(), C->getType()); 66 } 67 case Stmt::CXXBoolLiteralExprClass: { 68 const SVal *X = ExprBindings.lookup(EnvironmentEntry(E, LCtx)); 69 if (X) 70 return *X; 71 else 72 return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(E)); 73 } 74 case Stmt::IntegerLiteralClass: { 75 // In C++, this expression may have been bound to a temporary object. 76 SVal const *X = ExprBindings.lookup(EnvironmentEntry(E, LCtx)); 77 if (X) 78 return *X; 79 else 80 return svalBuilder.makeIntVal(cast<IntegerLiteral>(E)); 81 } 82 case Stmt::ObjCBoolLiteralExprClass: 83 return svalBuilder.makeBoolVal(cast<ObjCBoolLiteralExpr>(E)); 84 85 // For special C0xx nullptr case, make a null pointer SVal. 86 case Stmt::CXXNullPtrLiteralExprClass: 87 return svalBuilder.makeNull(); 88 case Stmt::ExprWithCleanupsClass: 89 E = cast<ExprWithCleanups>(E)->getSubExpr(); 90 continue; 91 case Stmt::CXXBindTemporaryExprClass: 92 E = cast<CXXBindTemporaryExpr>(E)->getSubExpr(); 93 continue; 94 case Stmt::ObjCPropertyRefExprClass: 95 return loc::ObjCPropRef(cast<ObjCPropertyRefExpr>(E)); 96 case Stmt::ObjCStringLiteralClass: { 97 MemRegionManager &MRMgr = svalBuilder.getRegionManager(); 98 const ObjCStringLiteral *SL = cast<ObjCStringLiteral>(E); 99 return svalBuilder.makeLoc(MRMgr.getObjCStringRegion(SL)); 100 } 101 case Stmt::StringLiteralClass: { 102 MemRegionManager &MRMgr = svalBuilder.getRegionManager(); 103 const StringLiteral *SL = cast<StringLiteral>(E); 104 return svalBuilder.makeLoc(MRMgr.getStringRegion(SL)); 105 } 106 case Stmt::ReturnStmtClass: { 107 const ReturnStmt *RS = cast<ReturnStmt>(E); 108 if (const Expr *RE = RS->getRetValue()) { 109 E = RE; 110 continue; 111 } 112 return UndefinedVal(); 113 } 114 115 // Handle all other Stmt* using a lookup. 116 default: 117 break; 118 }; 119 break; 120 } 121 return lookupExpr(EnvironmentEntry(E, LCtx)); 122 } 123 124 Environment EnvironmentManager::bindExpr(Environment Env, 125 const EnvironmentEntry &E, 126 SVal V, 127 bool Invalidate) { 128 if (V.isUnknown()) { 129 if (Invalidate) 130 return Environment(F.remove(Env.ExprBindings, E)); 131 else 132 return Env; 133 } 134 return Environment(F.add(Env.ExprBindings, E, V)); 135 } 136 137 static inline EnvironmentEntry MakeLocation(const EnvironmentEntry &E) { 138 const Stmt *S = E.getStmt(); 139 S = (const Stmt*) (((uintptr_t) S) | 0x1); 140 return EnvironmentEntry(S, E.getLocationContext()); 141 } 142 143 Environment EnvironmentManager::bindExprAndLocation(Environment Env, 144 const EnvironmentEntry &E, 145 SVal location, SVal V) { 146 return Environment(F.add(F.add(Env.ExprBindings, MakeLocation(E), location), 147 E, V)); 148 } 149 150 namespace { 151 class MarkLiveCallback : public SymbolVisitor { 152 SymbolReaper &SymReaper; 153 public: 154 MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {} 155 bool VisitSymbol(SymbolRef sym) { 156 SymReaper.markLive(sym); 157 return true; 158 } 159 bool VisitMemRegion(const MemRegion *R) { 160 SymReaper.markLive(R); 161 return true; 162 } 163 }; 164 } // end anonymous namespace 165 166 // In addition to mapping from EnvironmentEntry - > SVals in the Environment, 167 // we also maintain a mapping from EnvironmentEntry -> SVals (locations) 168 // that were used during a load and store. 169 static inline bool IsLocation(const EnvironmentEntry &E) { 170 const Stmt *S = E.getStmt(); 171 return (bool) (((uintptr_t) S) & 0x1); 172 } 173 174 // removeDeadBindings: 175 // - Remove subexpression bindings. 176 // - Remove dead block expression bindings. 177 // - Keep live block expression bindings: 178 // - Mark their reachable symbols live in SymbolReaper, 179 // see ScanReachableSymbols. 180 // - Mark the region in DRoots if the binding is a loc::MemRegionVal. 181 Environment 182 EnvironmentManager::removeDeadBindings(Environment Env, 183 SymbolReaper &SymReaper, 184 ProgramStateRef ST) { 185 186 // We construct a new Environment object entirely, as this is cheaper than 187 // individually removing all the subexpression bindings (which will greatly 188 // outnumber block-level expression bindings). 189 Environment NewEnv = getInitialEnvironment(); 190 191 SmallVector<std::pair<EnvironmentEntry, SVal>, 10> deferredLocations; 192 193 MarkLiveCallback CB(SymReaper); 194 ScanReachableSymbols RSScaner(ST, CB); 195 196 llvm::ImmutableMapRef<EnvironmentEntry,SVal> 197 EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(), 198 F.getTreeFactory()); 199 200 // Iterate over the block-expr bindings. 201 for (Environment::iterator I = Env.begin(), E = Env.end(); 202 I != E; ++I) { 203 204 const EnvironmentEntry &BlkExpr = I.getKey(); 205 // For recorded locations (used when evaluating loads and stores), we 206 // consider them live only when their associated normal expression is 207 // also live. 208 // NOTE: This assumes that loads/stores that evaluated to UnknownVal 209 // still have an entry in the map. 210 if (IsLocation(BlkExpr)) { 211 deferredLocations.push_back(std::make_pair(BlkExpr, I.getData())); 212 continue; 213 } 214 const SVal &X = I.getData(); 215 216 if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) { 217 // Copy the binding to the new map. 218 EBMapRef = EBMapRef.add(BlkExpr, X); 219 220 // If the block expr's value is a memory region, then mark that region. 221 if (isa<loc::MemRegionVal>(X)) { 222 const MemRegion *R = cast<loc::MemRegionVal>(X).getRegion(); 223 SymReaper.markLive(R); 224 } 225 226 // Mark all symbols in the block expr's value live. 227 RSScaner.scan(X); 228 continue; 229 } 230 231 // Otherwise the expression is dead with a couple exceptions. 232 // Do not misclean LogicalExpr or ConditionalOperator. It is dead at the 233 // beginning of itself, but we need its UndefinedVal to determine its 234 // SVal. 235 if (X.isUndef() && cast<UndefinedVal>(X).getData()) 236 EBMapRef = EBMapRef.add(BlkExpr, X); 237 } 238 239 // Go through he deferred locations and add them to the new environment if 240 // the correspond Stmt* is in the map as well. 241 for (SmallVectorImpl<std::pair<EnvironmentEntry, SVal> >::iterator 242 I = deferredLocations.begin(), E = deferredLocations.end(); I != E; ++I) { 243 const EnvironmentEntry &En = I->first; 244 const Stmt *S = (Stmt*) (((uintptr_t) En.getStmt()) & (uintptr_t) ~0x1); 245 if (EBMapRef.lookup(EnvironmentEntry(S, En.getLocationContext()))) 246 EBMapRef = EBMapRef.add(En, I->second); 247 } 248 249 NewEnv.ExprBindings = EBMapRef.asImmutableMap(); 250 return NewEnv; 251 } 252 253 void Environment::print(raw_ostream &Out, const char *NL, 254 const char *Sep) const { 255 printAux(Out, false, NL, Sep); 256 printAux(Out, true, NL, Sep); 257 } 258 259 void Environment::printAux(raw_ostream &Out, bool printLocations, 260 const char *NL, 261 const char *Sep) const{ 262 263 bool isFirst = true; 264 265 for (Environment::iterator I = begin(), E = end(); I != E; ++I) { 266 const EnvironmentEntry &En = I.getKey(); 267 if (IsLocation(En)) { 268 if (!printLocations) 269 continue; 270 } 271 else { 272 if (printLocations) 273 continue; 274 } 275 276 if (isFirst) { 277 Out << NL << NL 278 << (printLocations ? "Load/Store locations:" : "Expressions:") 279 << NL; 280 isFirst = false; 281 } else { 282 Out << NL; 283 } 284 285 const Stmt *S = En.getStmt(); 286 if (printLocations) { 287 S = (Stmt*) (((uintptr_t) S) & ((uintptr_t) ~0x1)); 288 } 289 290 Out << " (" << (void*) En.getLocationContext() << ',' << (void*) S << ") "; 291 LangOptions LO; // FIXME. 292 S->printPretty(Out, 0, PrintingPolicy(LO)); 293 Out << " : " << I.getData(); 294 } 295 } 296