1 //===- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ----------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines a meta-engine for path-sensitive dataflow analysis that 10 // is built on GREngine, but provides the boilerplate to execute transfer 11 // functions and build the ExplodedGraph at the expression level. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 16 #include "PrettyStackTraceLocationContext.h" 17 #include "clang/AST/ASTContext.h" 18 #include "clang/AST/Decl.h" 19 #include "clang/AST/DeclBase.h" 20 #include "clang/AST/DeclCXX.h" 21 #include "clang/AST/DeclObjC.h" 22 #include "clang/AST/Expr.h" 23 #include "clang/AST/ExprCXX.h" 24 #include "clang/AST/ExprObjC.h" 25 #include "clang/AST/ParentMap.h" 26 #include "clang/AST/PrettyPrinter.h" 27 #include "clang/AST/Stmt.h" 28 #include "clang/AST/StmtCXX.h" 29 #include "clang/AST/StmtObjC.h" 30 #include "clang/AST/Type.h" 31 #include "clang/Analysis/AnalysisDeclContext.h" 32 #include "clang/Analysis/CFG.h" 33 #include "clang/Analysis/ConstructionContext.h" 34 #include "clang/Analysis/ProgramPoint.h" 35 #include "clang/Basic/IdentifierTable.h" 36 #include "clang/Basic/JsonSupport.h" 37 #include "clang/Basic/LLVM.h" 38 #include "clang/Basic/LangOptions.h" 39 #include "clang/Basic/PrettyStackTrace.h" 40 #include "clang/Basic/SourceLocation.h" 41 #include "clang/Basic/SourceManager.h" 42 #include "clang/Basic/Specifiers.h" 43 #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" 44 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 45 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 46 #include "clang/StaticAnalyzer/Core/CheckerManager.h" 47 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 48 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 49 #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" 50 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" 51 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 52 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" 53 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h" 54 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 55 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 56 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 57 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" 58 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 59 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 60 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 61 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 62 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 63 #include "llvm/ADT/APSInt.h" 64 #include "llvm/ADT/DenseMap.h" 65 #include "llvm/ADT/ImmutableMap.h" 66 #include "llvm/ADT/ImmutableSet.h" 67 #include "llvm/ADT/Optional.h" 68 #include "llvm/ADT/SmallVector.h" 69 #include "llvm/ADT/Statistic.h" 70 #include "llvm/Support/Casting.h" 71 #include "llvm/Support/Compiler.h" 72 #include "llvm/Support/DOTGraphTraits.h" 73 #include "llvm/Support/ErrorHandling.h" 74 #include "llvm/Support/GraphWriter.h" 75 #include "llvm/Support/SaveAndRestore.h" 76 #include "llvm/Support/raw_ostream.h" 77 #include <cassert> 78 #include <cstdint> 79 #include <memory> 80 #include <string> 81 #include <tuple> 82 #include <utility> 83 #include <vector> 84 85 using namespace clang; 86 using namespace ento; 87 88 #define DEBUG_TYPE "ExprEngine" 89 90 STATISTIC(NumRemoveDeadBindings, 91 "The # of times RemoveDeadBindings is called"); 92 STATISTIC(NumMaxBlockCountReached, 93 "The # of aborted paths due to reaching the maximum block count in " 94 "a top level function"); 95 STATISTIC(NumMaxBlockCountReachedInInlined, 96 "The # of aborted paths due to reaching the maximum block count in " 97 "an inlined function"); 98 STATISTIC(NumTimesRetriedWithoutInlining, 99 "The # of times we re-evaluated a call without inlining"); 100 101 //===----------------------------------------------------------------------===// 102 // Internal program state traits. 103 //===----------------------------------------------------------------------===// 104 105 namespace { 106 107 // When modeling a C++ constructor, for a variety of reasons we need to track 108 // the location of the object for the duration of its ConstructionContext. 109 // ObjectsUnderConstruction maps statements within the construction context 110 // to the object's location, so that on every such statement the location 111 // could have been retrieved. 112 113 /// ConstructedObjectKey is used for being able to find the path-sensitive 114 /// memory region of a freshly constructed object while modeling the AST node 115 /// that syntactically represents the object that is being constructed. 116 /// Semantics of such nodes may sometimes require access to the region that's 117 /// not otherwise present in the program state, or to the very fact that 118 /// the construction context was present and contained references to these 119 /// AST nodes. 120 class ConstructedObjectKey { 121 typedef std::pair<ConstructionContextItem, const LocationContext *> 122 ConstructedObjectKeyImpl; 123 124 const ConstructedObjectKeyImpl Impl; 125 126 const void *getAnyASTNodePtr() const { 127 if (const Stmt *S = getItem().getStmtOrNull()) 128 return S; 129 else 130 return getItem().getCXXCtorInitializer(); 131 } 132 133 public: 134 explicit ConstructedObjectKey(const ConstructionContextItem &Item, 135 const LocationContext *LC) 136 : Impl(Item, LC) {} 137 138 const ConstructionContextItem &getItem() const { return Impl.first; } 139 const LocationContext *getLocationContext() const { return Impl.second; } 140 141 ASTContext &getASTContext() const { 142 return getLocationContext()->getDecl()->getASTContext(); 143 } 144 145 void printJson(llvm::raw_ostream &Out, PrinterHelper *Helper, 146 PrintingPolicy &PP) const { 147 const Stmt *S = getItem().getStmtOrNull(); 148 const CXXCtorInitializer *I = nullptr; 149 if (!S) 150 I = getItem().getCXXCtorInitializer(); 151 152 if (S) 153 Out << "\"stmt_id\": " << S->getID(getASTContext()); 154 else 155 Out << "\"init_id\": " << I->getID(getASTContext()); 156 157 // Kind 158 Out << ", \"kind\": \"" << getItem().getKindAsString() 159 << "\", \"argument_index\": "; 160 161 if (getItem().getKind() == ConstructionContextItem::ArgumentKind) 162 Out << getItem().getIndex(); 163 else 164 Out << "null"; 165 166 // Pretty-print 167 Out << ", \"pretty\": "; 168 169 if (S) { 170 S->printJson(Out, Helper, PP, /*AddQuotes=*/true); 171 } else { 172 Out << '\"' << I->getAnyMember()->getNameAsString() << '\"'; 173 } 174 } 175 176 void Profile(llvm::FoldingSetNodeID &ID) const { 177 ID.Add(Impl.first); 178 ID.AddPointer(Impl.second); 179 } 180 181 bool operator==(const ConstructedObjectKey &RHS) const { 182 return Impl == RHS.Impl; 183 } 184 185 bool operator<(const ConstructedObjectKey &RHS) const { 186 return Impl < RHS.Impl; 187 } 188 }; 189 } // namespace 190 191 typedef llvm::ImmutableMap<ConstructedObjectKey, SVal> 192 ObjectsUnderConstructionMap; 193 REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction, 194 ObjectsUnderConstructionMap) 195 196 //===----------------------------------------------------------------------===// 197 // Engine construction and deletion. 198 //===----------------------------------------------------------------------===// 199 200 static const char* TagProviderName = "ExprEngine"; 201 202 ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU, 203 AnalysisManager &mgr, 204 SetOfConstDecls *VisitedCalleesIn, 205 FunctionSummariesTy *FS, 206 InliningModes HowToInlineIn) 207 : CTU(CTU), AMgr(mgr), 208 AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), 209 Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()), 210 StateMgr(getContext(), mgr.getStoreManagerCreator(), 211 mgr.getConstraintManagerCreator(), G.getAllocator(), 212 this), 213 SymMgr(StateMgr.getSymbolManager()), 214 MRMgr(StateMgr.getRegionManager()), 215 svalBuilder(StateMgr.getSValBuilder()), 216 ObjCNoRet(mgr.getASTContext()), 217 BR(mgr, *this), 218 VisitedCallees(VisitedCalleesIn), 219 HowToInline(HowToInlineIn) 220 { 221 unsigned TrimInterval = mgr.options.GraphTrimInterval; 222 if (TrimInterval != 0) { 223 // Enable eager node reclamation when constructing the ExplodedGraph. 224 G.enableNodeReclamation(TrimInterval); 225 } 226 } 227 228 //===----------------------------------------------------------------------===// 229 // Utility methods. 230 //===----------------------------------------------------------------------===// 231 232 ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { 233 ProgramStateRef state = StateMgr.getInitialState(InitLoc); 234 const Decl *D = InitLoc->getDecl(); 235 236 // Preconditions. 237 // FIXME: It would be nice if we had a more general mechanism to add 238 // such preconditions. Some day. 239 do { 240 if (const auto *FD = dyn_cast<FunctionDecl>(D)) { 241 // Precondition: the first argument of 'main' is an integer guaranteed 242 // to be > 0. 243 const IdentifierInfo *II = FD->getIdentifier(); 244 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0)) 245 break; 246 247 const ParmVarDecl *PD = FD->getParamDecl(0); 248 QualType T = PD->getType(); 249 const auto *BT = dyn_cast<BuiltinType>(T); 250 if (!BT || !BT->isInteger()) 251 break; 252 253 const MemRegion *R = state->getRegion(PD, InitLoc); 254 if (!R) 255 break; 256 257 SVal V = state->getSVal(loc::MemRegionVal(R)); 258 SVal Constraint_untested = evalBinOp(state, BO_GT, V, 259 svalBuilder.makeZeroVal(T), 260 svalBuilder.getConditionType()); 261 262 Optional<DefinedOrUnknownSVal> Constraint = 263 Constraint_untested.getAs<DefinedOrUnknownSVal>(); 264 265 if (!Constraint) 266 break; 267 268 if (ProgramStateRef newState = state->assume(*Constraint, true)) 269 state = newState; 270 } 271 break; 272 } 273 while (false); 274 275 if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) { 276 // Precondition: 'self' is always non-null upon entry to an Objective-C 277 // method. 278 const ImplicitParamDecl *SelfD = MD->getSelfDecl(); 279 const MemRegion *R = state->getRegion(SelfD, InitLoc); 280 SVal V = state->getSVal(loc::MemRegionVal(R)); 281 282 if (Optional<Loc> LV = V.getAs<Loc>()) { 283 // Assume that the pointer value in 'self' is non-null. 284 state = state->assume(*LV, true); 285 assert(state && "'self' cannot be null"); 286 } 287 } 288 289 if (const auto *MD = dyn_cast<CXXMethodDecl>(D)) { 290 if (!MD->isStatic()) { 291 // Precondition: 'this' is always non-null upon entry to the 292 // top-level function. This is our starting assumption for 293 // analyzing an "open" program. 294 const StackFrameContext *SFC = InitLoc->getStackFrame(); 295 if (SFC->getParent() == nullptr) { 296 loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC); 297 SVal V = state->getSVal(L); 298 if (Optional<Loc> LV = V.getAs<Loc>()) { 299 state = state->assume(*LV, true); 300 assert(state && "'this' cannot be null"); 301 } 302 } 303 } 304 } 305 306 return state; 307 } 308 309 ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded( 310 ProgramStateRef State, const LocationContext *LC, 311 const Expr *InitWithAdjustments, const Expr *Result, 312 const SubRegion **OutRegionWithAdjustments) { 313 // FIXME: This function is a hack that works around the quirky AST 314 // we're often having with respect to C++ temporaries. If only we modelled 315 // the actual execution order of statements properly in the CFG, 316 // all the hassle with adjustments would not be necessary, 317 // and perhaps the whole function would be removed. 318 SVal InitValWithAdjustments = State->getSVal(InitWithAdjustments, LC); 319 if (!Result) { 320 // If we don't have an explicit result expression, we're in "if needed" 321 // mode. Only create a region if the current value is a NonLoc. 322 if (!InitValWithAdjustments.getAs<NonLoc>()) { 323 if (OutRegionWithAdjustments) 324 *OutRegionWithAdjustments = nullptr; 325 return State; 326 } 327 Result = InitWithAdjustments; 328 } else { 329 // We need to create a region no matter what. For sanity, make sure we don't 330 // try to stuff a Loc into a non-pointer temporary region. 331 assert(!InitValWithAdjustments.getAs<Loc>() || 332 Loc::isLocType(Result->getType()) || 333 Result->getType()->isMemberPointerType()); 334 } 335 336 ProgramStateManager &StateMgr = State->getStateManager(); 337 MemRegionManager &MRMgr = StateMgr.getRegionManager(); 338 StoreManager &StoreMgr = StateMgr.getStoreManager(); 339 340 // MaterializeTemporaryExpr may appear out of place, after a few field and 341 // base-class accesses have been made to the object, even though semantically 342 // it is the whole object that gets materialized and lifetime-extended. 343 // 344 // For example: 345 // 346 // `-MaterializeTemporaryExpr 347 // `-MemberExpr 348 // `-CXXTemporaryObjectExpr 349 // 350 // instead of the more natural 351 // 352 // `-MemberExpr 353 // `-MaterializeTemporaryExpr 354 // `-CXXTemporaryObjectExpr 355 // 356 // Use the usual methods for obtaining the expression of the base object, 357 // and record the adjustments that we need to make to obtain the sub-object 358 // that the whole expression 'Ex' refers to. This trick is usual, 359 // in the sense that CodeGen takes a similar route. 360 361 SmallVector<const Expr *, 2> CommaLHSs; 362 SmallVector<SubobjectAdjustment, 2> Adjustments; 363 364 const Expr *Init = InitWithAdjustments->skipRValueSubobjectAdjustments( 365 CommaLHSs, Adjustments); 366 367 // Take the region for Init, i.e. for the whole object. If we do not remember 368 // the region in which the object originally was constructed, come up with 369 // a new temporary region out of thin air and copy the contents of the object 370 // (which are currently present in the Environment, because Init is an rvalue) 371 // into that region. This is not correct, but it is better than nothing. 372 const TypedValueRegion *TR = nullptr; 373 if (const auto *MT = dyn_cast<MaterializeTemporaryExpr>(Result)) { 374 if (Optional<SVal> V = getObjectUnderConstruction(State, MT, LC)) { 375 State = finishObjectConstruction(State, MT, LC); 376 State = State->BindExpr(Result, LC, *V); 377 return State; 378 } else { 379 StorageDuration SD = MT->getStorageDuration(); 380 // If this object is bound to a reference with static storage duration, we 381 // put it in a different region to prevent "address leakage" warnings. 382 if (SD == SD_Static || SD == SD_Thread) { 383 TR = MRMgr.getCXXStaticTempObjectRegion(Init); 384 } else { 385 TR = MRMgr.getCXXTempObjectRegion(Init, LC); 386 } 387 } 388 } else { 389 TR = MRMgr.getCXXTempObjectRegion(Init, LC); 390 } 391 392 SVal Reg = loc::MemRegionVal(TR); 393 SVal BaseReg = Reg; 394 395 // Make the necessary adjustments to obtain the sub-object. 396 for (auto I = Adjustments.rbegin(), E = Adjustments.rend(); I != E; ++I) { 397 const SubobjectAdjustment &Adj = *I; 398 switch (Adj.Kind) { 399 case SubobjectAdjustment::DerivedToBaseAdjustment: 400 Reg = StoreMgr.evalDerivedToBase(Reg, Adj.DerivedToBase.BasePath); 401 break; 402 case SubobjectAdjustment::FieldAdjustment: 403 Reg = StoreMgr.getLValueField(Adj.Field, Reg); 404 break; 405 case SubobjectAdjustment::MemberPointerAdjustment: 406 // FIXME: Unimplemented. 407 State = State->invalidateRegions(Reg, InitWithAdjustments, 408 currBldrCtx->blockCount(), LC, true, 409 nullptr, nullptr, nullptr); 410 return State; 411 } 412 } 413 414 // What remains is to copy the value of the object to the new region. 415 // FIXME: In other words, what we should always do is copy value of the 416 // Init expression (which corresponds to the bigger object) to the whole 417 // temporary region TR. However, this value is often no longer present 418 // in the Environment. If it has disappeared, we instead invalidate TR. 419 // Still, what we can do is assign the value of expression Ex (which 420 // corresponds to the sub-object) to the TR's sub-region Reg. At least, 421 // values inside Reg would be correct. 422 SVal InitVal = State->getSVal(Init, LC); 423 if (InitVal.isUnknown()) { 424 InitVal = getSValBuilder().conjureSymbolVal(Result, LC, Init->getType(), 425 currBldrCtx->blockCount()); 426 State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false); 427 428 // Then we'd need to take the value that certainly exists and bind it 429 // over. 430 if (InitValWithAdjustments.isUnknown()) { 431 // Try to recover some path sensitivity in case we couldn't 432 // compute the value. 433 InitValWithAdjustments = getSValBuilder().conjureSymbolVal( 434 Result, LC, InitWithAdjustments->getType(), 435 currBldrCtx->blockCount()); 436 } 437 State = 438 State->bindLoc(Reg.castAs<Loc>(), InitValWithAdjustments, LC, false); 439 } else { 440 State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false); 441 } 442 443 // The result expression would now point to the correct sub-region of the 444 // newly created temporary region. Do this last in order to getSVal of Init 445 // correctly in case (Result == Init). 446 if (Result->isGLValue()) { 447 State = State->BindExpr(Result, LC, Reg); 448 } else { 449 State = State->BindExpr(Result, LC, InitValWithAdjustments); 450 } 451 452 // Notify checkers once for two bindLoc()s. 453 State = processRegionChange(State, TR, LC); 454 455 if (OutRegionWithAdjustments) 456 *OutRegionWithAdjustments = cast<SubRegion>(Reg.getAsRegion()); 457 return State; 458 } 459 460 ProgramStateRef 461 ExprEngine::addObjectUnderConstruction(ProgramStateRef State, 462 const ConstructionContextItem &Item, 463 const LocationContext *LC, SVal V) { 464 ConstructedObjectKey Key(Item, LC->getStackFrame()); 465 // FIXME: Currently the state might already contain the marker due to 466 // incorrect handling of temporaries bound to default parameters. 467 assert(!State->get<ObjectsUnderConstruction>(Key) || 468 Key.getItem().getKind() == 469 ConstructionContextItem::TemporaryDestructorKind); 470 return State->set<ObjectsUnderConstruction>(Key, V); 471 } 472 473 Optional<SVal> 474 ExprEngine::getObjectUnderConstruction(ProgramStateRef State, 475 const ConstructionContextItem &Item, 476 const LocationContext *LC) { 477 ConstructedObjectKey Key(Item, LC->getStackFrame()); 478 return Optional<SVal>::create(State->get<ObjectsUnderConstruction>(Key)); 479 } 480 481 ProgramStateRef 482 ExprEngine::finishObjectConstruction(ProgramStateRef State, 483 const ConstructionContextItem &Item, 484 const LocationContext *LC) { 485 ConstructedObjectKey Key(Item, LC->getStackFrame()); 486 assert(State->contains<ObjectsUnderConstruction>(Key)); 487 return State->remove<ObjectsUnderConstruction>(Key); 488 } 489 490 ProgramStateRef ExprEngine::elideDestructor(ProgramStateRef State, 491 const CXXBindTemporaryExpr *BTE, 492 const LocationContext *LC) { 493 ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC); 494 // FIXME: Currently the state might already contain the marker due to 495 // incorrect handling of temporaries bound to default parameters. 496 return State->set<ObjectsUnderConstruction>(Key, UnknownVal()); 497 } 498 499 ProgramStateRef 500 ExprEngine::cleanupElidedDestructor(ProgramStateRef State, 501 const CXXBindTemporaryExpr *BTE, 502 const LocationContext *LC) { 503 ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC); 504 assert(State->contains<ObjectsUnderConstruction>(Key)); 505 return State->remove<ObjectsUnderConstruction>(Key); 506 } 507 508 bool ExprEngine::isDestructorElided(ProgramStateRef State, 509 const CXXBindTemporaryExpr *BTE, 510 const LocationContext *LC) { 511 ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC); 512 return State->contains<ObjectsUnderConstruction>(Key); 513 } 514 515 bool ExprEngine::areAllObjectsFullyConstructed(ProgramStateRef State, 516 const LocationContext *FromLC, 517 const LocationContext *ToLC) { 518 const LocationContext *LC = FromLC; 519 while (LC != ToLC) { 520 assert(LC && "ToLC must be a parent of FromLC!"); 521 for (auto I : State->get<ObjectsUnderConstruction>()) 522 if (I.first.getLocationContext() == LC) 523 return false; 524 525 LC = LC->getParent(); 526 } 527 return true; 528 } 529 530 531 //===----------------------------------------------------------------------===// 532 // Top-level transfer function logic (Dispatcher). 533 //===----------------------------------------------------------------------===// 534 535 /// evalAssume - Called by ConstraintManager. Used to call checker-specific 536 /// logic for handling assumptions on symbolic values. 537 ProgramStateRef ExprEngine::processAssume(ProgramStateRef state, 538 SVal cond, bool assumption) { 539 return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption); 540 } 541 542 ProgramStateRef 543 ExprEngine::processRegionChanges(ProgramStateRef state, 544 const InvalidatedSymbols *invalidated, 545 ArrayRef<const MemRegion *> Explicits, 546 ArrayRef<const MemRegion *> Regions, 547 const LocationContext *LCtx, 548 const CallEvent *Call) { 549 return getCheckerManager().runCheckersForRegionChanges(state, invalidated, 550 Explicits, Regions, 551 LCtx, Call); 552 } 553 554 static void 555 printObjectsUnderConstructionJson(raw_ostream &Out, ProgramStateRef State, 556 const char *NL, const LocationContext *LCtx, 557 unsigned int Space = 0, bool IsDot = false) { 558 PrintingPolicy PP = 559 LCtx->getAnalysisDeclContext()->getASTContext().getPrintingPolicy(); 560 561 ++Space; 562 bool HasItem = false; 563 564 // Store the last key. 565 const ConstructedObjectKey *LastKey = nullptr; 566 for (const auto &I : State->get<ObjectsUnderConstruction>()) { 567 const ConstructedObjectKey &Key = I.first; 568 if (Key.getLocationContext() != LCtx) 569 continue; 570 571 if (!HasItem) { 572 Out << "[" << NL; 573 HasItem = true; 574 } 575 576 LastKey = &Key; 577 } 578 579 for (const auto &I : State->get<ObjectsUnderConstruction>()) { 580 const ConstructedObjectKey &Key = I.first; 581 SVal Value = I.second; 582 if (Key.getLocationContext() != LCtx) 583 continue; 584 585 Indent(Out, Space, IsDot) << "{ "; 586 Key.printJson(Out, nullptr, PP); 587 Out << ", \"value\": \"" << Value << "\" }"; 588 589 if (&Key != LastKey) 590 Out << ','; 591 Out << NL; 592 } 593 594 if (HasItem) 595 Indent(Out, --Space, IsDot) << ']'; // End of "location_context". 596 else { 597 Out << "null "; 598 } 599 } 600 601 void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State, 602 const LocationContext *LCtx, const char *NL, 603 unsigned int Space, bool IsDot) const { 604 Indent(Out, Space, IsDot) << "\"constructing_objects\": "; 605 606 if (LCtx && !State->get<ObjectsUnderConstruction>().isEmpty()) { 607 ++Space; 608 Out << '[' << NL; 609 LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) { 610 printObjectsUnderConstructionJson(Out, State, NL, LC, Space, IsDot); 611 }); 612 613 --Space; 614 Indent(Out, Space, IsDot) << "]," << NL; // End of "constructing_objects". 615 } else { 616 Out << "null," << NL; 617 } 618 619 getCheckerManager().runCheckersForPrintStateJson(Out, State, NL, Space, 620 IsDot); 621 } 622 623 void ExprEngine::processEndWorklist() { 624 getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); 625 } 626 627 void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, 628 unsigned StmtIdx, NodeBuilderContext *Ctx) { 629 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 630 currStmtIdx = StmtIdx; 631 currBldrCtx = Ctx; 632 633 switch (E.getKind()) { 634 case CFGElement::Statement: 635 case CFGElement::Constructor: 636 case CFGElement::CXXRecordTypedCall: 637 ProcessStmt(E.castAs<CFGStmt>().getStmt(), Pred); 638 return; 639 case CFGElement::Initializer: 640 ProcessInitializer(E.castAs<CFGInitializer>(), Pred); 641 return; 642 case CFGElement::NewAllocator: 643 ProcessNewAllocator(E.castAs<CFGNewAllocator>().getAllocatorExpr(), 644 Pred); 645 return; 646 case CFGElement::AutomaticObjectDtor: 647 case CFGElement::DeleteDtor: 648 case CFGElement::BaseDtor: 649 case CFGElement::MemberDtor: 650 case CFGElement::TemporaryDtor: 651 ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred); 652 return; 653 case CFGElement::LoopExit: 654 ProcessLoopExit(E.castAs<CFGLoopExit>().getLoopStmt(), Pred); 655 return; 656 case CFGElement::LifetimeEnds: 657 case CFGElement::ScopeBegin: 658 case CFGElement::ScopeEnd: 659 return; 660 } 661 } 662 663 static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, 664 const Stmt *S, 665 const ExplodedNode *Pred, 666 const LocationContext *LC) { 667 // Are we never purging state values? 668 if (AMgr.options.AnalysisPurgeOpt == PurgeNone) 669 return false; 670 671 // Is this the beginning of a basic block? 672 if (Pred->getLocation().getAs<BlockEntrance>()) 673 return true; 674 675 // Is this on a non-expression? 676 if (!isa<Expr>(S)) 677 return true; 678 679 // Run before processing a call. 680 if (CallEvent::isCallStmt(S)) 681 return true; 682 683 // Is this an expression that is consumed by another expression? If so, 684 // postpone cleaning out the state. 685 ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap(); 686 return !PM.isConsumedExpr(cast<Expr>(S)); 687 } 688 689 void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out, 690 const Stmt *ReferenceStmt, 691 const LocationContext *LC, 692 const Stmt *DiagnosticStmt, 693 ProgramPoint::Kind K) { 694 assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind || 695 ReferenceStmt == nullptr || isa<ReturnStmt>(ReferenceStmt)) 696 && "PostStmt is not generally supported by the SymbolReaper yet"); 697 assert(LC && "Must pass the current (or expiring) LocationContext"); 698 699 if (!DiagnosticStmt) { 700 DiagnosticStmt = ReferenceStmt; 701 assert(DiagnosticStmt && "Required for clearing a LocationContext"); 702 } 703 704 NumRemoveDeadBindings++; 705 ProgramStateRef CleanedState = Pred->getState(); 706 707 // LC is the location context being destroyed, but SymbolReaper wants a 708 // location context that is still live. (If this is the top-level stack 709 // frame, this will be null.) 710 if (!ReferenceStmt) { 711 assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind && 712 "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext"); 713 LC = LC->getParent(); 714 } 715 716 const StackFrameContext *SFC = LC ? LC->getStackFrame() : nullptr; 717 SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager()); 718 719 for (auto I : CleanedState->get<ObjectsUnderConstruction>()) { 720 if (SymbolRef Sym = I.second.getAsSymbol()) 721 SymReaper.markLive(Sym); 722 if (const MemRegion *MR = I.second.getAsRegion()) 723 SymReaper.markLive(MR); 724 } 725 726 getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper); 727 728 // Create a state in which dead bindings are removed from the environment 729 // and the store. TODO: The function should just return new env and store, 730 // not a new state. 731 CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper); 732 733 // Process any special transfer function for dead symbols. 734 // A tag to track convenience transitions, which can be removed at cleanup. 735 static SimpleProgramPointTag cleanupTag(TagProviderName, "Clean Node"); 736 // Call checkers with the non-cleaned state so that they could query the 737 // values of the soon to be dead symbols. 738 ExplodedNodeSet CheckedSet; 739 getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper, 740 DiagnosticStmt, *this, K); 741 742 // For each node in CheckedSet, generate CleanedNodes that have the 743 // environment, the store, and the constraints cleaned up but have the 744 // user-supplied states as the predecessors. 745 StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx); 746 for (const auto I : CheckedSet) { 747 ProgramStateRef CheckerState = I->getState(); 748 749 // The constraint manager has not been cleaned up yet, so clean up now. 750 CheckerState = 751 getConstraintManager().removeDeadBindings(CheckerState, SymReaper); 752 753 assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) && 754 "Checkers are not allowed to modify the Environment as a part of " 755 "checkDeadSymbols processing."); 756 assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) && 757 "Checkers are not allowed to modify the Store as a part of " 758 "checkDeadSymbols processing."); 759 760 // Create a state based on CleanedState with CheckerState GDM and 761 // generate a transition to that state. 762 ProgramStateRef CleanedCheckerSt = 763 StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState); 764 Bldr.generateNode(DiagnosticStmt, I, CleanedCheckerSt, &cleanupTag, K); 765 } 766 } 767 768 void ExprEngine::ProcessStmt(const Stmt *currStmt, ExplodedNode *Pred) { 769 // Reclaim any unnecessary nodes in the ExplodedGraph. 770 G.reclaimRecentlyAllocatedNodes(); 771 772 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 773 currStmt->getBeginLoc(), 774 "Error evaluating statement"); 775 776 // Remove dead bindings and symbols. 777 ExplodedNodeSet CleanedStates; 778 if (shouldRemoveDeadBindings(AMgr, currStmt, Pred, 779 Pred->getLocationContext())) { 780 removeDead(Pred, CleanedStates, currStmt, 781 Pred->getLocationContext()); 782 } else 783 CleanedStates.Add(Pred); 784 785 // Visit the statement. 786 ExplodedNodeSet Dst; 787 for (const auto I : CleanedStates) { 788 ExplodedNodeSet DstI; 789 // Visit the statement. 790 Visit(currStmt, I, DstI); 791 Dst.insert(DstI); 792 } 793 794 // Enqueue the new nodes onto the work list. 795 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 796 } 797 798 void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) { 799 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 800 S->getBeginLoc(), 801 "Error evaluating end of the loop"); 802 ExplodedNodeSet Dst; 803 Dst.Add(Pred); 804 NodeBuilder Bldr(Pred, Dst, *currBldrCtx); 805 ProgramStateRef NewState = Pred->getState(); 806 807 if(AMgr.options.ShouldUnrollLoops) 808 NewState = processLoopEnd(S, NewState); 809 810 LoopExit PP(S, Pred->getLocationContext()); 811 Bldr.generateNode(PP, NewState, Pred); 812 // Enqueue the new nodes onto the work list. 813 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 814 } 815 816 void ExprEngine::ProcessInitializer(const CFGInitializer CFGInit, 817 ExplodedNode *Pred) { 818 const CXXCtorInitializer *BMI = CFGInit.getInitializer(); 819 const Expr *Init = BMI->getInit()->IgnoreImplicit(); 820 const LocationContext *LC = Pred->getLocationContext(); 821 822 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 823 BMI->getSourceLocation(), 824 "Error evaluating initializer"); 825 826 // We don't clean up dead bindings here. 827 const auto *stackFrame = cast<StackFrameContext>(Pred->getLocationContext()); 828 const auto *decl = cast<CXXConstructorDecl>(stackFrame->getDecl()); 829 830 ProgramStateRef State = Pred->getState(); 831 SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame)); 832 833 ExplodedNodeSet Tmp; 834 SVal FieldLoc; 835 836 // Evaluate the initializer, if necessary 837 if (BMI->isAnyMemberInitializer()) { 838 // Constructors build the object directly in the field, 839 // but non-objects must be copied in from the initializer. 840 if (getObjectUnderConstruction(State, BMI, LC)) { 841 // The field was directly constructed, so there is no need to bind. 842 // But we still need to stop tracking the object under construction. 843 State = finishObjectConstruction(State, BMI, LC); 844 NodeBuilder Bldr(Pred, Tmp, *currBldrCtx); 845 PostStore PS(Init, LC, /*Loc*/ nullptr, /*tag*/ nullptr); 846 Bldr.generateNode(PS, State, Pred); 847 } else { 848 const ValueDecl *Field; 849 if (BMI->isIndirectMemberInitializer()) { 850 Field = BMI->getIndirectMember(); 851 FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal); 852 } else { 853 Field = BMI->getMember(); 854 FieldLoc = State->getLValue(BMI->getMember(), thisVal); 855 } 856 857 SVal InitVal; 858 if (Init->getType()->isArrayType()) { 859 // Handle arrays of trivial type. We can represent this with a 860 // primitive load/copy from the base array region. 861 const ArraySubscriptExpr *ASE; 862 while ((ASE = dyn_cast<ArraySubscriptExpr>(Init))) 863 Init = ASE->getBase()->IgnoreImplicit(); 864 865 SVal LValue = State->getSVal(Init, stackFrame); 866 if (!Field->getType()->isReferenceType()) 867 if (Optional<Loc> LValueLoc = LValue.getAs<Loc>()) 868 InitVal = State->getSVal(*LValueLoc); 869 870 // If we fail to get the value for some reason, use a symbolic value. 871 if (InitVal.isUnknownOrUndef()) { 872 SValBuilder &SVB = getSValBuilder(); 873 InitVal = SVB.conjureSymbolVal(BMI->getInit(), stackFrame, 874 Field->getType(), 875 currBldrCtx->blockCount()); 876 } 877 } else { 878 InitVal = State->getSVal(BMI->getInit(), stackFrame); 879 } 880 881 PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame); 882 evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP); 883 } 884 } else { 885 assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer()); 886 Tmp.insert(Pred); 887 // We already did all the work when visiting the CXXConstructExpr. 888 } 889 890 // Construct PostInitializer nodes whether the state changed or not, 891 // so that the diagnostics don't get confused. 892 PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame); 893 ExplodedNodeSet Dst; 894 NodeBuilder Bldr(Tmp, Dst, *currBldrCtx); 895 for (const auto I : Tmp) { 896 ProgramStateRef State = I->getState(); 897 Bldr.generateNode(PP, State, I); 898 } 899 900 // Enqueue the new nodes onto the work list. 901 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 902 } 903 904 void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, 905 ExplodedNode *Pred) { 906 ExplodedNodeSet Dst; 907 switch (D.getKind()) { 908 case CFGElement::AutomaticObjectDtor: 909 ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst); 910 break; 911 case CFGElement::BaseDtor: 912 ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst); 913 break; 914 case CFGElement::MemberDtor: 915 ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst); 916 break; 917 case CFGElement::TemporaryDtor: 918 ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst); 919 break; 920 case CFGElement::DeleteDtor: 921 ProcessDeleteDtor(D.castAs<CFGDeleteDtor>(), Pred, Dst); 922 break; 923 default: 924 llvm_unreachable("Unexpected dtor kind."); 925 } 926 927 // Enqueue the new nodes onto the work list. 928 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 929 } 930 931 void ExprEngine::ProcessNewAllocator(const CXXNewExpr *NE, 932 ExplodedNode *Pred) { 933 ExplodedNodeSet Dst; 934 AnalysisManager &AMgr = getAnalysisManager(); 935 AnalyzerOptions &Opts = AMgr.options; 936 // TODO: We're not evaluating allocators for all cases just yet as 937 // we're not handling the return value correctly, which causes false 938 // positives when the alpha.cplusplus.NewDeleteLeaks check is on. 939 if (Opts.MayInlineCXXAllocator) 940 VisitCXXNewAllocatorCall(NE, Pred, Dst); 941 else { 942 NodeBuilder Bldr(Pred, Dst, *currBldrCtx); 943 const LocationContext *LCtx = Pred->getLocationContext(); 944 PostImplicitCall PP(NE->getOperatorNew(), NE->getBeginLoc(), LCtx); 945 Bldr.generateNode(PP, Pred->getState(), Pred); 946 } 947 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 948 } 949 950 void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, 951 ExplodedNode *Pred, 952 ExplodedNodeSet &Dst) { 953 const VarDecl *varDecl = Dtor.getVarDecl(); 954 QualType varType = varDecl->getType(); 955 956 ProgramStateRef state = Pred->getState(); 957 SVal dest = state->getLValue(varDecl, Pred->getLocationContext()); 958 const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion(); 959 960 if (varType->isReferenceType()) { 961 const MemRegion *ValueRegion = state->getSVal(Region).getAsRegion(); 962 if (!ValueRegion) { 963 // FIXME: This should not happen. The language guarantees a presence 964 // of a valid initializer here, so the reference shall not be undefined. 965 // It seems that we're calling destructors over variables that 966 // were not initialized yet. 967 return; 968 } 969 Region = ValueRegion->getBaseRegion(); 970 varType = cast<TypedValueRegion>(Region)->getValueType(); 971 } 972 973 // FIXME: We need to run the same destructor on every element of the array. 974 // This workaround will just run the first destructor (which will still 975 // invalidate the entire array). 976 EvalCallOptions CallOpts; 977 Region = makeZeroElementRegion(state, loc::MemRegionVal(Region), varType, 978 CallOpts.IsArrayCtorOrDtor).getAsRegion(); 979 980 VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(), 981 /*IsBase=*/false, Pred, Dst, CallOpts); 982 } 983 984 void ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor, 985 ExplodedNode *Pred, 986 ExplodedNodeSet &Dst) { 987 ProgramStateRef State = Pred->getState(); 988 const LocationContext *LCtx = Pred->getLocationContext(); 989 const CXXDeleteExpr *DE = Dtor.getDeleteExpr(); 990 const Stmt *Arg = DE->getArgument(); 991 QualType DTy = DE->getDestroyedType(); 992 SVal ArgVal = State->getSVal(Arg, LCtx); 993 994 // If the argument to delete is known to be a null value, 995 // don't run destructor. 996 if (State->isNull(ArgVal).isConstrainedTrue()) { 997 QualType BTy = getContext().getBaseElementType(DTy); 998 const CXXRecordDecl *RD = BTy->getAsCXXRecordDecl(); 999 const CXXDestructorDecl *Dtor = RD->getDestructor(); 1000 1001 PostImplicitCall PP(Dtor, DE->getBeginLoc(), LCtx); 1002 NodeBuilder Bldr(Pred, Dst, *currBldrCtx); 1003 Bldr.generateNode(PP, Pred->getState(), Pred); 1004 return; 1005 } 1006 1007 EvalCallOptions CallOpts; 1008 const MemRegion *ArgR = ArgVal.getAsRegion(); 1009 if (DE->isArrayForm()) { 1010 // FIXME: We need to run the same destructor on every element of the array. 1011 // This workaround will just run the first destructor (which will still 1012 // invalidate the entire array). 1013 CallOpts.IsArrayCtorOrDtor = true; 1014 // Yes, it may even be a multi-dimensional array. 1015 while (const auto *AT = getContext().getAsArrayType(DTy)) 1016 DTy = AT->getElementType(); 1017 if (ArgR) 1018 ArgR = getStoreManager().GetElementZeroRegion(cast<SubRegion>(ArgR), DTy); 1019 } 1020 1021 VisitCXXDestructor(DTy, ArgR, DE, /*IsBase=*/false, Pred, Dst, CallOpts); 1022 } 1023 1024 void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, 1025 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 1026 const LocationContext *LCtx = Pred->getLocationContext(); 1027 1028 const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl()); 1029 Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor, 1030 LCtx->getStackFrame()); 1031 SVal ThisVal = Pred->getState()->getSVal(ThisPtr); 1032 1033 // Create the base object region. 1034 const CXXBaseSpecifier *Base = D.getBaseSpecifier(); 1035 QualType BaseTy = Base->getType(); 1036 SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy, 1037 Base->isVirtual()); 1038 1039 EvalCallOptions CallOpts; 1040 VisitCXXDestructor(BaseTy, BaseVal.getAsRegion(), CurDtor->getBody(), 1041 /*IsBase=*/true, Pred, Dst, CallOpts); 1042 } 1043 1044 void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, 1045 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 1046 const FieldDecl *Member = D.getFieldDecl(); 1047 QualType T = Member->getType(); 1048 ProgramStateRef State = Pred->getState(); 1049 const LocationContext *LCtx = Pred->getLocationContext(); 1050 1051 const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl()); 1052 Loc ThisStorageLoc = 1053 getSValBuilder().getCXXThis(CurDtor, LCtx->getStackFrame()); 1054 Loc ThisLoc = State->getSVal(ThisStorageLoc).castAs<Loc>(); 1055 SVal FieldVal = State->getLValue(Member, ThisLoc); 1056 1057 // FIXME: We need to run the same destructor on every element of the array. 1058 // This workaround will just run the first destructor (which will still 1059 // invalidate the entire array). 1060 EvalCallOptions CallOpts; 1061 FieldVal = makeZeroElementRegion(State, FieldVal, T, 1062 CallOpts.IsArrayCtorOrDtor); 1063 1064 VisitCXXDestructor(T, FieldVal.getAsRegion(), CurDtor->getBody(), 1065 /*IsBase=*/false, Pred, Dst, CallOpts); 1066 } 1067 1068 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, 1069 ExplodedNode *Pred, 1070 ExplodedNodeSet &Dst) { 1071 const CXXBindTemporaryExpr *BTE = D.getBindTemporaryExpr(); 1072 ProgramStateRef State = Pred->getState(); 1073 const LocationContext *LC = Pred->getLocationContext(); 1074 const MemRegion *MR = nullptr; 1075 1076 if (Optional<SVal> V = 1077 getObjectUnderConstruction(State, D.getBindTemporaryExpr(), 1078 Pred->getLocationContext())) { 1079 // FIXME: Currently we insert temporary destructors for default parameters, 1080 // but we don't insert the constructors, so the entry in 1081 // ObjectsUnderConstruction may be missing. 1082 State = finishObjectConstruction(State, D.getBindTemporaryExpr(), 1083 Pred->getLocationContext()); 1084 MR = V->getAsRegion(); 1085 } 1086 1087 // If copy elision has occurred, and the constructor corresponding to the 1088 // destructor was elided, we need to skip the destructor as well. 1089 if (isDestructorElided(State, BTE, LC)) { 1090 State = cleanupElidedDestructor(State, BTE, LC); 1091 NodeBuilder Bldr(Pred, Dst, *currBldrCtx); 1092 PostImplicitCall PP(D.getDestructorDecl(getContext()), 1093 D.getBindTemporaryExpr()->getBeginLoc(), 1094 Pred->getLocationContext()); 1095 Bldr.generateNode(PP, State, Pred); 1096 return; 1097 } 1098 1099 ExplodedNodeSet CleanDtorState; 1100 StmtNodeBuilder StmtBldr(Pred, CleanDtorState, *currBldrCtx); 1101 StmtBldr.generateNode(D.getBindTemporaryExpr(), Pred, State); 1102 1103 QualType T = D.getBindTemporaryExpr()->getSubExpr()->getType(); 1104 // FIXME: Currently CleanDtorState can be empty here due to temporaries being 1105 // bound to default parameters. 1106 assert(CleanDtorState.size() <= 1); 1107 ExplodedNode *CleanPred = 1108 CleanDtorState.empty() ? Pred : *CleanDtorState.begin(); 1109 1110 EvalCallOptions CallOpts; 1111 CallOpts.IsTemporaryCtorOrDtor = true; 1112 if (!MR) { 1113 // If we have no MR, we still need to unwrap the array to avoid destroying 1114 // the whole array at once. Regardless, we'd eventually need to model array 1115 // destructors properly, element-by-element. 1116 while (const ArrayType *AT = getContext().getAsArrayType(T)) { 1117 T = AT->getElementType(); 1118 CallOpts.IsArrayCtorOrDtor = true; 1119 } 1120 } else { 1121 // We'd eventually need to makeZeroElementRegion() trick here, 1122 // but for now we don't have the respective construction contexts, 1123 // so MR would always be null in this case. Do nothing for now. 1124 } 1125 VisitCXXDestructor(T, MR, D.getBindTemporaryExpr(), 1126 /*IsBase=*/false, CleanPred, Dst, CallOpts); 1127 } 1128 1129 void ExprEngine::processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, 1130 NodeBuilderContext &BldCtx, 1131 ExplodedNode *Pred, 1132 ExplodedNodeSet &Dst, 1133 const CFGBlock *DstT, 1134 const CFGBlock *DstF) { 1135 BranchNodeBuilder TempDtorBuilder(Pred, Dst, BldCtx, DstT, DstF); 1136 ProgramStateRef State = Pred->getState(); 1137 const LocationContext *LC = Pred->getLocationContext(); 1138 if (getObjectUnderConstruction(State, BTE, LC)) { 1139 TempDtorBuilder.markInfeasible(false); 1140 TempDtorBuilder.generateNode(State, true, Pred); 1141 } else { 1142 TempDtorBuilder.markInfeasible(true); 1143 TempDtorBuilder.generateNode(State, false, Pred); 1144 } 1145 } 1146 1147 void ExprEngine::VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE, 1148 ExplodedNodeSet &PreVisit, 1149 ExplodedNodeSet &Dst) { 1150 // This is a fallback solution in case we didn't have a construction 1151 // context when we were constructing the temporary. Otherwise the map should 1152 // have been populated there. 1153 if (!getAnalysisManager().options.ShouldIncludeTemporaryDtorsInCFG) { 1154 // In case we don't have temporary destructors in the CFG, do not mark 1155 // the initialization - we would otherwise never clean it up. 1156 Dst = PreVisit; 1157 return; 1158 } 1159 StmtNodeBuilder StmtBldr(PreVisit, Dst, *currBldrCtx); 1160 for (ExplodedNode *Node : PreVisit) { 1161 ProgramStateRef State = Node->getState(); 1162 const LocationContext *LC = Node->getLocationContext(); 1163 if (!getObjectUnderConstruction(State, BTE, LC)) { 1164 // FIXME: Currently the state might also already contain the marker due to 1165 // incorrect handling of temporaries bound to default parameters; for 1166 // those, we currently skip the CXXBindTemporaryExpr but rely on adding 1167 // temporary destructor nodes. 1168 State = addObjectUnderConstruction(State, BTE, LC, UnknownVal()); 1169 } 1170 StmtBldr.generateNode(BTE, Node, State); 1171 } 1172 } 1173 1174 ProgramStateRef ExprEngine::escapeValue(ProgramStateRef State, SVal V, 1175 PointerEscapeKind K) const { 1176 class CollectReachableSymbolsCallback final : public SymbolVisitor { 1177 InvalidatedSymbols Symbols; 1178 1179 public: 1180 explicit CollectReachableSymbolsCallback(ProgramStateRef) {} 1181 1182 const InvalidatedSymbols &getSymbols() const { return Symbols; } 1183 1184 bool VisitSymbol(SymbolRef Sym) override { 1185 Symbols.insert(Sym); 1186 return true; 1187 } 1188 }; 1189 1190 const CollectReachableSymbolsCallback &Scanner = 1191 State->scanReachableSymbols<CollectReachableSymbolsCallback>(V); 1192 return getCheckerManager().runCheckersForPointerEscape( 1193 State, Scanner.getSymbols(), /*CallEvent*/ nullptr, K, nullptr); 1194 } 1195 1196 void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, 1197 ExplodedNodeSet &DstTop) { 1198 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 1199 S->getBeginLoc(), "Error evaluating statement"); 1200 ExplodedNodeSet Dst; 1201 StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx); 1202 1203 assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens()); 1204 1205 switch (S->getStmtClass()) { 1206 // C++, OpenMP and ARC stuff we don't support yet. 1207 case Expr::ObjCIndirectCopyRestoreExprClass: 1208 case Stmt::CXXDependentScopeMemberExprClass: 1209 case Stmt::CXXInheritedCtorInitExprClass: 1210 case Stmt::CXXTryStmtClass: 1211 case Stmt::CXXTypeidExprClass: 1212 case Stmt::CXXUuidofExprClass: 1213 case Stmt::CXXFoldExprClass: 1214 case Stmt::MSPropertyRefExprClass: 1215 case Stmt::MSPropertySubscriptExprClass: 1216 case Stmt::CXXUnresolvedConstructExprClass: 1217 case Stmt::DependentScopeDeclRefExprClass: 1218 case Stmt::ArrayTypeTraitExprClass: 1219 case Stmt::ExpressionTraitExprClass: 1220 case Stmt::UnresolvedLookupExprClass: 1221 case Stmt::UnresolvedMemberExprClass: 1222 case Stmt::TypoExprClass: 1223 case Stmt::CXXNoexceptExprClass: 1224 case Stmt::PackExpansionExprClass: 1225 case Stmt::SubstNonTypeTemplateParmPackExprClass: 1226 case Stmt::FunctionParmPackExprClass: 1227 case Stmt::CoroutineBodyStmtClass: 1228 case Stmt::CoawaitExprClass: 1229 case Stmt::DependentCoawaitExprClass: 1230 case Stmt::CoreturnStmtClass: 1231 case Stmt::CoyieldExprClass: 1232 case Stmt::SEHTryStmtClass: 1233 case Stmt::SEHExceptStmtClass: 1234 case Stmt::SEHLeaveStmtClass: 1235 case Stmt::SEHFinallyStmtClass: 1236 case Stmt::OMPParallelDirectiveClass: 1237 case Stmt::OMPSimdDirectiveClass: 1238 case Stmt::OMPForDirectiveClass: 1239 case Stmt::OMPForSimdDirectiveClass: 1240 case Stmt::OMPSectionsDirectiveClass: 1241 case Stmt::OMPSectionDirectiveClass: 1242 case Stmt::OMPSingleDirectiveClass: 1243 case Stmt::OMPMasterDirectiveClass: 1244 case Stmt::OMPCriticalDirectiveClass: 1245 case Stmt::OMPParallelForDirectiveClass: 1246 case Stmt::OMPParallelForSimdDirectiveClass: 1247 case Stmt::OMPParallelSectionsDirectiveClass: 1248 case Stmt::OMPTaskDirectiveClass: 1249 case Stmt::OMPTaskyieldDirectiveClass: 1250 case Stmt::OMPBarrierDirectiveClass: 1251 case Stmt::OMPTaskwaitDirectiveClass: 1252 case Stmt::OMPTaskgroupDirectiveClass: 1253 case Stmt::OMPFlushDirectiveClass: 1254 case Stmt::OMPOrderedDirectiveClass: 1255 case Stmt::OMPAtomicDirectiveClass: 1256 case Stmt::OMPTargetDirectiveClass: 1257 case Stmt::OMPTargetDataDirectiveClass: 1258 case Stmt::OMPTargetEnterDataDirectiveClass: 1259 case Stmt::OMPTargetExitDataDirectiveClass: 1260 case Stmt::OMPTargetParallelDirectiveClass: 1261 case Stmt::OMPTargetParallelForDirectiveClass: 1262 case Stmt::OMPTargetUpdateDirectiveClass: 1263 case Stmt::OMPTeamsDirectiveClass: 1264 case Stmt::OMPCancellationPointDirectiveClass: 1265 case Stmt::OMPCancelDirectiveClass: 1266 case Stmt::OMPTaskLoopDirectiveClass: 1267 case Stmt::OMPTaskLoopSimdDirectiveClass: 1268 case Stmt::OMPMasterTaskLoopDirectiveClass: 1269 case Stmt::OMPMasterTaskLoopSimdDirectiveClass: 1270 case Stmt::OMPParallelMasterTaskLoopDirectiveClass: 1271 case Stmt::OMPDistributeDirectiveClass: 1272 case Stmt::OMPDistributeParallelForDirectiveClass: 1273 case Stmt::OMPDistributeParallelForSimdDirectiveClass: 1274 case Stmt::OMPDistributeSimdDirectiveClass: 1275 case Stmt::OMPTargetParallelForSimdDirectiveClass: 1276 case Stmt::OMPTargetSimdDirectiveClass: 1277 case Stmt::OMPTeamsDistributeDirectiveClass: 1278 case Stmt::OMPTeamsDistributeSimdDirectiveClass: 1279 case Stmt::OMPTeamsDistributeParallelForSimdDirectiveClass: 1280 case Stmt::OMPTeamsDistributeParallelForDirectiveClass: 1281 case Stmt::OMPTargetTeamsDirectiveClass: 1282 case Stmt::OMPTargetTeamsDistributeDirectiveClass: 1283 case Stmt::OMPTargetTeamsDistributeParallelForDirectiveClass: 1284 case Stmt::OMPTargetTeamsDistributeParallelForSimdDirectiveClass: 1285 case Stmt::OMPTargetTeamsDistributeSimdDirectiveClass: 1286 case Stmt::CapturedStmtClass: { 1287 const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState()); 1288 Engine.addAbortedBlock(node, currBldrCtx->getBlock()); 1289 break; 1290 } 1291 1292 case Stmt::ParenExprClass: 1293 llvm_unreachable("ParenExprs already handled."); 1294 case Stmt::GenericSelectionExprClass: 1295 llvm_unreachable("GenericSelectionExprs already handled."); 1296 // Cases that should never be evaluated simply because they shouldn't 1297 // appear in the CFG. 1298 case Stmt::BreakStmtClass: 1299 case Stmt::CaseStmtClass: 1300 case Stmt::CompoundStmtClass: 1301 case Stmt::ContinueStmtClass: 1302 case Stmt::CXXForRangeStmtClass: 1303 case Stmt::DefaultStmtClass: 1304 case Stmt::DoStmtClass: 1305 case Stmt::ForStmtClass: 1306 case Stmt::GotoStmtClass: 1307 case Stmt::IfStmtClass: 1308 case Stmt::IndirectGotoStmtClass: 1309 case Stmt::LabelStmtClass: 1310 case Stmt::NoStmtClass: 1311 case Stmt::NullStmtClass: 1312 case Stmt::SwitchStmtClass: 1313 case Stmt::WhileStmtClass: 1314 case Expr::MSDependentExistsStmtClass: 1315 llvm_unreachable("Stmt should not be in analyzer evaluation loop"); 1316 1317 case Stmt::ObjCSubscriptRefExprClass: 1318 case Stmt::ObjCPropertyRefExprClass: 1319 llvm_unreachable("These are handled by PseudoObjectExpr"); 1320 1321 case Stmt::GNUNullExprClass: { 1322 // GNU __null is a pointer-width integer, not an actual pointer. 1323 ProgramStateRef state = Pred->getState(); 1324 state = state->BindExpr(S, Pred->getLocationContext(), 1325 svalBuilder.makeIntValWithPtrWidth(0, false)); 1326 Bldr.generateNode(S, Pred, state); 1327 break; 1328 } 1329 1330 case Stmt::ObjCAtSynchronizedStmtClass: 1331 Bldr.takeNodes(Pred); 1332 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst); 1333 Bldr.addNodes(Dst); 1334 break; 1335 1336 case Expr::ConstantExprClass: 1337 case Stmt::ExprWithCleanupsClass: 1338 // Handled due to fully linearised CFG. 1339 break; 1340 1341 case Stmt::CXXBindTemporaryExprClass: { 1342 Bldr.takeNodes(Pred); 1343 ExplodedNodeSet PreVisit; 1344 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 1345 ExplodedNodeSet Next; 1346 VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), PreVisit, Next); 1347 getCheckerManager().runCheckersForPostStmt(Dst, Next, S, *this); 1348 Bldr.addNodes(Dst); 1349 break; 1350 } 1351 1352 // Cases not handled yet; but will handle some day. 1353 case Stmt::DesignatedInitExprClass: 1354 case Stmt::DesignatedInitUpdateExprClass: 1355 case Stmt::ArrayInitLoopExprClass: 1356 case Stmt::ArrayInitIndexExprClass: 1357 case Stmt::ExtVectorElementExprClass: 1358 case Stmt::ImaginaryLiteralClass: 1359 case Stmt::ObjCAtCatchStmtClass: 1360 case Stmt::ObjCAtFinallyStmtClass: 1361 case Stmt::ObjCAtTryStmtClass: 1362 case Stmt::ObjCAutoreleasePoolStmtClass: 1363 case Stmt::ObjCEncodeExprClass: 1364 case Stmt::ObjCIsaExprClass: 1365 case Stmt::ObjCProtocolExprClass: 1366 case Stmt::ObjCSelectorExprClass: 1367 case Stmt::ParenListExprClass: 1368 case Stmt::ShuffleVectorExprClass: 1369 case Stmt::ConvertVectorExprClass: 1370 case Stmt::VAArgExprClass: 1371 case Stmt::CUDAKernelCallExprClass: 1372 case Stmt::OpaqueValueExprClass: 1373 case Stmt::AsTypeExprClass: 1374 case Stmt::ConceptSpecializationExprClass: 1375 case Stmt::CXXRewrittenBinaryOperatorClass: 1376 // Fall through. 1377 1378 // Cases we intentionally don't evaluate, since they don't need 1379 // to be explicitly evaluated. 1380 case Stmt::PredefinedExprClass: 1381 case Stmt::AddrLabelExprClass: 1382 case Stmt::AttributedStmtClass: 1383 case Stmt::IntegerLiteralClass: 1384 case Stmt::FixedPointLiteralClass: 1385 case Stmt::CharacterLiteralClass: 1386 case Stmt::ImplicitValueInitExprClass: 1387 case Stmt::CXXScalarValueInitExprClass: 1388 case Stmt::CXXBoolLiteralExprClass: 1389 case Stmt::ObjCBoolLiteralExprClass: 1390 case Stmt::ObjCAvailabilityCheckExprClass: 1391 case Stmt::FloatingLiteralClass: 1392 case Stmt::NoInitExprClass: 1393 case Stmt::SizeOfPackExprClass: 1394 case Stmt::StringLiteralClass: 1395 case Stmt::SourceLocExprClass: 1396 case Stmt::ObjCStringLiteralClass: 1397 case Stmt::CXXPseudoDestructorExprClass: 1398 case Stmt::SubstNonTypeTemplateParmExprClass: 1399 case Stmt::CXXNullPtrLiteralExprClass: 1400 case Stmt::OMPArraySectionExprClass: 1401 case Stmt::TypeTraitExprClass: { 1402 Bldr.takeNodes(Pred); 1403 ExplodedNodeSet preVisit; 1404 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 1405 getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this); 1406 Bldr.addNodes(Dst); 1407 break; 1408 } 1409 1410 case Stmt::CXXDefaultArgExprClass: 1411 case Stmt::CXXDefaultInitExprClass: { 1412 Bldr.takeNodes(Pred); 1413 ExplodedNodeSet PreVisit; 1414 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 1415 1416 ExplodedNodeSet Tmp; 1417 StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx); 1418 1419 const Expr *ArgE; 1420 if (const auto *DefE = dyn_cast<CXXDefaultArgExpr>(S)) 1421 ArgE = DefE->getExpr(); 1422 else if (const auto *DefE = dyn_cast<CXXDefaultInitExpr>(S)) 1423 ArgE = DefE->getExpr(); 1424 else 1425 llvm_unreachable("unknown constant wrapper kind"); 1426 1427 bool IsTemporary = false; 1428 if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(ArgE)) { 1429 ArgE = MTE->GetTemporaryExpr(); 1430 IsTemporary = true; 1431 } 1432 1433 Optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE); 1434 if (!ConstantVal) 1435 ConstantVal = UnknownVal(); 1436 1437 const LocationContext *LCtx = Pred->getLocationContext(); 1438 for (const auto I : PreVisit) { 1439 ProgramStateRef State = I->getState(); 1440 State = State->BindExpr(S, LCtx, *ConstantVal); 1441 if (IsTemporary) 1442 State = createTemporaryRegionIfNeeded(State, LCtx, 1443 cast<Expr>(S), 1444 cast<Expr>(S)); 1445 Bldr2.generateNode(S, I, State); 1446 } 1447 1448 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); 1449 Bldr.addNodes(Dst); 1450 break; 1451 } 1452 1453 // Cases we evaluate as opaque expressions, conjuring a symbol. 1454 case Stmt::CXXStdInitializerListExprClass: 1455 case Expr::ObjCArrayLiteralClass: 1456 case Expr::ObjCDictionaryLiteralClass: 1457 case Expr::ObjCBoxedExprClass: { 1458 Bldr.takeNodes(Pred); 1459 1460 ExplodedNodeSet preVisit; 1461 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 1462 1463 ExplodedNodeSet Tmp; 1464 StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx); 1465 1466 const auto *Ex = cast<Expr>(S); 1467 QualType resultType = Ex->getType(); 1468 1469 for (const auto N : preVisit) { 1470 const LocationContext *LCtx = N->getLocationContext(); 1471 SVal result = svalBuilder.conjureSymbolVal(nullptr, Ex, LCtx, 1472 resultType, 1473 currBldrCtx->blockCount()); 1474 ProgramStateRef State = N->getState()->BindExpr(Ex, LCtx, result); 1475 1476 // Escape pointers passed into the list, unless it's an ObjC boxed 1477 // expression which is not a boxable C structure. 1478 if (!(isa<ObjCBoxedExpr>(Ex) && 1479 !cast<ObjCBoxedExpr>(Ex)->getSubExpr() 1480 ->getType()->isRecordType())) 1481 for (auto Child : Ex->children()) { 1482 assert(Child); 1483 SVal Val = State->getSVal(Child, LCtx); 1484 State = escapeValue(State, Val, PSK_EscapeOther); 1485 } 1486 1487 Bldr2.generateNode(S, N, State); 1488 } 1489 1490 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); 1491 Bldr.addNodes(Dst); 1492 break; 1493 } 1494 1495 case Stmt::ArraySubscriptExprClass: 1496 Bldr.takeNodes(Pred); 1497 VisitArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); 1498 Bldr.addNodes(Dst); 1499 break; 1500 1501 case Stmt::GCCAsmStmtClass: 1502 Bldr.takeNodes(Pred); 1503 VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst); 1504 Bldr.addNodes(Dst); 1505 break; 1506 1507 case Stmt::MSAsmStmtClass: 1508 Bldr.takeNodes(Pred); 1509 VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst); 1510 Bldr.addNodes(Dst); 1511 break; 1512 1513 case Stmt::BlockExprClass: 1514 Bldr.takeNodes(Pred); 1515 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst); 1516 Bldr.addNodes(Dst); 1517 break; 1518 1519 case Stmt::LambdaExprClass: 1520 if (AMgr.options.ShouldInlineLambdas) { 1521 Bldr.takeNodes(Pred); 1522 VisitLambdaExpr(cast<LambdaExpr>(S), Pred, Dst); 1523 Bldr.addNodes(Dst); 1524 } else { 1525 const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState()); 1526 Engine.addAbortedBlock(node, currBldrCtx->getBlock()); 1527 } 1528 break; 1529 1530 case Stmt::BinaryOperatorClass: { 1531 const auto *B = cast<BinaryOperator>(S); 1532 if (B->isLogicalOp()) { 1533 Bldr.takeNodes(Pred); 1534 VisitLogicalExpr(B, Pred, Dst); 1535 Bldr.addNodes(Dst); 1536 break; 1537 } 1538 else if (B->getOpcode() == BO_Comma) { 1539 ProgramStateRef state = Pred->getState(); 1540 Bldr.generateNode(B, Pred, 1541 state->BindExpr(B, Pred->getLocationContext(), 1542 state->getSVal(B->getRHS(), 1543 Pred->getLocationContext()))); 1544 break; 1545 } 1546 1547 Bldr.takeNodes(Pred); 1548 1549 if (AMgr.options.ShouldEagerlyAssume && 1550 (B->isRelationalOp() || B->isEqualityOp())) { 1551 ExplodedNodeSet Tmp; 1552 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp); 1553 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S)); 1554 } 1555 else 1556 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 1557 1558 Bldr.addNodes(Dst); 1559 break; 1560 } 1561 1562 case Stmt::CXXOperatorCallExprClass: { 1563 const auto *OCE = cast<CXXOperatorCallExpr>(S); 1564 1565 // For instance method operators, make sure the 'this' argument has a 1566 // valid region. 1567 const Decl *Callee = OCE->getCalleeDecl(); 1568 if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) { 1569 if (MD->isInstance()) { 1570 ProgramStateRef State = Pred->getState(); 1571 const LocationContext *LCtx = Pred->getLocationContext(); 1572 ProgramStateRef NewState = 1573 createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0)); 1574 if (NewState != State) { 1575 Pred = Bldr.generateNode(OCE, Pred, NewState, /*tag=*/nullptr, 1576 ProgramPoint::PreStmtKind); 1577 // Did we cache out? 1578 if (!Pred) 1579 break; 1580 } 1581 } 1582 } 1583 // FALLTHROUGH 1584 LLVM_FALLTHROUGH; 1585 } 1586 1587 case Stmt::CallExprClass: 1588 case Stmt::CXXMemberCallExprClass: 1589 case Stmt::UserDefinedLiteralClass: 1590 Bldr.takeNodes(Pred); 1591 VisitCallExpr(cast<CallExpr>(S), Pred, Dst); 1592 Bldr.addNodes(Dst); 1593 break; 1594 1595 case Stmt::CXXCatchStmtClass: 1596 Bldr.takeNodes(Pred); 1597 VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst); 1598 Bldr.addNodes(Dst); 1599 break; 1600 1601 case Stmt::CXXTemporaryObjectExprClass: 1602 case Stmt::CXXConstructExprClass: 1603 Bldr.takeNodes(Pred); 1604 VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst); 1605 Bldr.addNodes(Dst); 1606 break; 1607 1608 case Stmt::CXXNewExprClass: { 1609 Bldr.takeNodes(Pred); 1610 1611 ExplodedNodeSet PreVisit; 1612 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 1613 1614 ExplodedNodeSet PostVisit; 1615 for (const auto i : PreVisit) 1616 VisitCXXNewExpr(cast<CXXNewExpr>(S), i, PostVisit); 1617 1618 getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this); 1619 Bldr.addNodes(Dst); 1620 break; 1621 } 1622 1623 case Stmt::CXXDeleteExprClass: { 1624 Bldr.takeNodes(Pred); 1625 ExplodedNodeSet PreVisit; 1626 const auto *CDE = cast<CXXDeleteExpr>(S); 1627 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 1628 1629 for (const auto i : PreVisit) 1630 VisitCXXDeleteExpr(CDE, i, Dst); 1631 1632 Bldr.addNodes(Dst); 1633 break; 1634 } 1635 // FIXME: ChooseExpr is really a constant. We need to fix 1636 // the CFG do not model them as explicit control-flow. 1637 1638 case Stmt::ChooseExprClass: { // __builtin_choose_expr 1639 Bldr.takeNodes(Pred); 1640 const auto *C = cast<ChooseExpr>(S); 1641 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst); 1642 Bldr.addNodes(Dst); 1643 break; 1644 } 1645 1646 case Stmt::CompoundAssignOperatorClass: 1647 Bldr.takeNodes(Pred); 1648 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 1649 Bldr.addNodes(Dst); 1650 break; 1651 1652 case Stmt::CompoundLiteralExprClass: 1653 Bldr.takeNodes(Pred); 1654 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst); 1655 Bldr.addNodes(Dst); 1656 break; 1657 1658 case Stmt::BinaryConditionalOperatorClass: 1659 case Stmt::ConditionalOperatorClass: { // '?' operator 1660 Bldr.takeNodes(Pred); 1661 const auto *C = cast<AbstractConditionalOperator>(S); 1662 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst); 1663 Bldr.addNodes(Dst); 1664 break; 1665 } 1666 1667 case Stmt::CXXThisExprClass: 1668 Bldr.takeNodes(Pred); 1669 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst); 1670 Bldr.addNodes(Dst); 1671 break; 1672 1673 case Stmt::DeclRefExprClass: { 1674 Bldr.takeNodes(Pred); 1675 const auto *DE = cast<DeclRefExpr>(S); 1676 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst); 1677 Bldr.addNodes(Dst); 1678 break; 1679 } 1680 1681 case Stmt::DeclStmtClass: 1682 Bldr.takeNodes(Pred); 1683 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst); 1684 Bldr.addNodes(Dst); 1685 break; 1686 1687 case Stmt::ImplicitCastExprClass: 1688 case Stmt::CStyleCastExprClass: 1689 case Stmt::CXXStaticCastExprClass: 1690 case Stmt::CXXDynamicCastExprClass: 1691 case Stmt::CXXReinterpretCastExprClass: 1692 case Stmt::CXXConstCastExprClass: 1693 case Stmt::CXXFunctionalCastExprClass: 1694 case Stmt::BuiltinBitCastExprClass: 1695 case Stmt::ObjCBridgedCastExprClass: { 1696 Bldr.takeNodes(Pred); 1697 const auto *C = cast<CastExpr>(S); 1698 ExplodedNodeSet dstExpr; 1699 VisitCast(C, C->getSubExpr(), Pred, dstExpr); 1700 1701 // Handle the postvisit checks. 1702 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this); 1703 Bldr.addNodes(Dst); 1704 break; 1705 } 1706 1707 case Expr::MaterializeTemporaryExprClass: { 1708 Bldr.takeNodes(Pred); 1709 const auto *MTE = cast<MaterializeTemporaryExpr>(S); 1710 ExplodedNodeSet dstPrevisit; 1711 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this); 1712 ExplodedNodeSet dstExpr; 1713 for (const auto i : dstPrevisit) 1714 CreateCXXTemporaryObject(MTE, i, dstExpr); 1715 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this); 1716 Bldr.addNodes(Dst); 1717 break; 1718 } 1719 1720 case Stmt::InitListExprClass: 1721 Bldr.takeNodes(Pred); 1722 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst); 1723 Bldr.addNodes(Dst); 1724 break; 1725 1726 case Stmt::MemberExprClass: 1727 Bldr.takeNodes(Pred); 1728 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst); 1729 Bldr.addNodes(Dst); 1730 break; 1731 1732 case Stmt::AtomicExprClass: 1733 Bldr.takeNodes(Pred); 1734 VisitAtomicExpr(cast<AtomicExpr>(S), Pred, Dst); 1735 Bldr.addNodes(Dst); 1736 break; 1737 1738 case Stmt::ObjCIvarRefExprClass: 1739 Bldr.takeNodes(Pred); 1740 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst); 1741 Bldr.addNodes(Dst); 1742 break; 1743 1744 case Stmt::ObjCForCollectionStmtClass: 1745 Bldr.takeNodes(Pred); 1746 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst); 1747 Bldr.addNodes(Dst); 1748 break; 1749 1750 case Stmt::ObjCMessageExprClass: 1751 Bldr.takeNodes(Pred); 1752 VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst); 1753 Bldr.addNodes(Dst); 1754 break; 1755 1756 case Stmt::ObjCAtThrowStmtClass: 1757 case Stmt::CXXThrowExprClass: 1758 // FIXME: This is not complete. We basically treat @throw as 1759 // an abort. 1760 Bldr.generateSink(S, Pred, Pred->getState()); 1761 break; 1762 1763 case Stmt::ReturnStmtClass: 1764 Bldr.takeNodes(Pred); 1765 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst); 1766 Bldr.addNodes(Dst); 1767 break; 1768 1769 case Stmt::OffsetOfExprClass: { 1770 Bldr.takeNodes(Pred); 1771 ExplodedNodeSet PreVisit; 1772 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 1773 1774 ExplodedNodeSet PostVisit; 1775 for (const auto Node : PreVisit) 1776 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Node, PostVisit); 1777 1778 getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this); 1779 Bldr.addNodes(Dst); 1780 break; 1781 } 1782 1783 case Stmt::UnaryExprOrTypeTraitExprClass: 1784 Bldr.takeNodes(Pred); 1785 VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 1786 Pred, Dst); 1787 Bldr.addNodes(Dst); 1788 break; 1789 1790 case Stmt::StmtExprClass: { 1791 const auto *SE = cast<StmtExpr>(S); 1792 1793 if (SE->getSubStmt()->body_empty()) { 1794 // Empty statement expression. 1795 assert(SE->getType() == getContext().VoidTy 1796 && "Empty statement expression must have void type."); 1797 break; 1798 } 1799 1800 if (const auto *LastExpr = 1801 dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) { 1802 ProgramStateRef state = Pred->getState(); 1803 Bldr.generateNode(SE, Pred, 1804 state->BindExpr(SE, Pred->getLocationContext(), 1805 state->getSVal(LastExpr, 1806 Pred->getLocationContext()))); 1807 } 1808 break; 1809 } 1810 1811 case Stmt::UnaryOperatorClass: { 1812 Bldr.takeNodes(Pred); 1813 const auto *U = cast<UnaryOperator>(S); 1814 if (AMgr.options.ShouldEagerlyAssume && (U->getOpcode() == UO_LNot)) { 1815 ExplodedNodeSet Tmp; 1816 VisitUnaryOperator(U, Pred, Tmp); 1817 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U); 1818 } 1819 else 1820 VisitUnaryOperator(U, Pred, Dst); 1821 Bldr.addNodes(Dst); 1822 break; 1823 } 1824 1825 case Stmt::PseudoObjectExprClass: { 1826 Bldr.takeNodes(Pred); 1827 ProgramStateRef state = Pred->getState(); 1828 const auto *PE = cast<PseudoObjectExpr>(S); 1829 if (const Expr *Result = PE->getResultExpr()) { 1830 SVal V = state->getSVal(Result, Pred->getLocationContext()); 1831 Bldr.generateNode(S, Pred, 1832 state->BindExpr(S, Pred->getLocationContext(), V)); 1833 } 1834 else 1835 Bldr.generateNode(S, Pred, 1836 state->BindExpr(S, Pred->getLocationContext(), 1837 UnknownVal())); 1838 1839 Bldr.addNodes(Dst); 1840 break; 1841 } 1842 } 1843 } 1844 1845 bool ExprEngine::replayWithoutInlining(ExplodedNode *N, 1846 const LocationContext *CalleeLC) { 1847 const StackFrameContext *CalleeSF = CalleeLC->getStackFrame(); 1848 const StackFrameContext *CallerSF = CalleeSF->getParent()->getStackFrame(); 1849 assert(CalleeSF && CallerSF); 1850 ExplodedNode *BeforeProcessingCall = nullptr; 1851 const Stmt *CE = CalleeSF->getCallSite(); 1852 1853 // Find the first node before we started processing the call expression. 1854 while (N) { 1855 ProgramPoint L = N->getLocation(); 1856 BeforeProcessingCall = N; 1857 N = N->pred_empty() ? nullptr : *(N->pred_begin()); 1858 1859 // Skip the nodes corresponding to the inlined code. 1860 if (L.getStackFrame() != CallerSF) 1861 continue; 1862 // We reached the caller. Find the node right before we started 1863 // processing the call. 1864 if (L.isPurgeKind()) 1865 continue; 1866 if (L.getAs<PreImplicitCall>()) 1867 continue; 1868 if (L.getAs<CallEnter>()) 1869 continue; 1870 if (Optional<StmtPoint> SP = L.getAs<StmtPoint>()) 1871 if (SP->getStmt() == CE) 1872 continue; 1873 break; 1874 } 1875 1876 if (!BeforeProcessingCall) 1877 return false; 1878 1879 // TODO: Clean up the unneeded nodes. 1880 1881 // Build an Epsilon node from which we will restart the analyzes. 1882 // Note that CE is permitted to be NULL! 1883 ProgramPoint NewNodeLoc = 1884 EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE); 1885 // Add the special flag to GDM to signal retrying with no inlining. 1886 // Note, changing the state ensures that we are not going to cache out. 1887 ProgramStateRef NewNodeState = BeforeProcessingCall->getState(); 1888 NewNodeState = 1889 NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE)); 1890 1891 // Make the new node a successor of BeforeProcessingCall. 1892 bool IsNew = false; 1893 ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew); 1894 // We cached out at this point. Caching out is common due to us backtracking 1895 // from the inlined function, which might spawn several paths. 1896 if (!IsNew) 1897 return true; 1898 1899 NewNode->addPredecessor(BeforeProcessingCall, G); 1900 1901 // Add the new node to the work list. 1902 Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(), 1903 CalleeSF->getIndex()); 1904 NumTimesRetriedWithoutInlining++; 1905 return true; 1906 } 1907 1908 /// Block entrance. (Update counters). 1909 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, 1910 NodeBuilderWithSinks &nodeBuilder, 1911 ExplodedNode *Pred) { 1912 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 1913 // If we reach a loop which has a known bound (and meets 1914 // other constraints) then consider completely unrolling it. 1915 if(AMgr.options.ShouldUnrollLoops) { 1916 unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath; 1917 const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt(); 1918 if (Term) { 1919 ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(), 1920 Pred, maxBlockVisitOnPath); 1921 if (NewState != Pred->getState()) { 1922 ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred); 1923 if (!UpdatedNode) 1924 return; 1925 Pred = UpdatedNode; 1926 } 1927 } 1928 // Is we are inside an unrolled loop then no need the check the counters. 1929 if(isUnrolledState(Pred->getState())) 1930 return; 1931 } 1932 1933 // If this block is terminated by a loop and it has already been visited the 1934 // maximum number of times, widen the loop. 1935 unsigned int BlockCount = nodeBuilder.getContext().blockCount(); 1936 if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 && 1937 AMgr.options.ShouldWidenLoops) { 1938 const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt(); 1939 if (!(Term && 1940 (isa<ForStmt>(Term) || isa<WhileStmt>(Term) || isa<DoStmt>(Term)))) 1941 return; 1942 // Widen. 1943 const LocationContext *LCtx = Pred->getLocationContext(); 1944 ProgramStateRef WidenedState = 1945 getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term); 1946 nodeBuilder.generateNode(WidenedState, Pred); 1947 return; 1948 } 1949 1950 // FIXME: Refactor this into a checker. 1951 if (BlockCount >= AMgr.options.maxBlockVisitOnPath) { 1952 static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded"); 1953 const ExplodedNode *Sink = 1954 nodeBuilder.generateSink(Pred->getState(), Pred, &tag); 1955 1956 // Check if we stopped at the top level function or not. 1957 // Root node should have the location context of the top most function. 1958 const LocationContext *CalleeLC = Pred->getLocation().getLocationContext(); 1959 const LocationContext *CalleeSF = CalleeLC->getStackFrame(); 1960 const LocationContext *RootLC = 1961 (*G.roots_begin())->getLocation().getLocationContext(); 1962 if (RootLC->getStackFrame() != CalleeSF) { 1963 Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl()); 1964 1965 // Re-run the call evaluation without inlining it, by storing the 1966 // no-inlining policy in the state and enqueuing the new work item on 1967 // the list. Replay should almost never fail. Use the stats to catch it 1968 // if it does. 1969 if ((!AMgr.options.NoRetryExhausted && 1970 replayWithoutInlining(Pred, CalleeLC))) 1971 return; 1972 NumMaxBlockCountReachedInInlined++; 1973 } else 1974 NumMaxBlockCountReached++; 1975 1976 // Make sink nodes as exhausted(for stats) only if retry failed. 1977 Engine.blocksExhausted.push_back(std::make_pair(L, Sink)); 1978 } 1979 } 1980 1981 //===----------------------------------------------------------------------===// 1982 // Branch processing. 1983 //===----------------------------------------------------------------------===// 1984 1985 /// RecoverCastedSymbol - A helper function for ProcessBranch that is used 1986 /// to try to recover some path-sensitivity for casts of symbolic 1987 /// integers that promote their values (which are currently not tracked well). 1988 /// This function returns the SVal bound to Condition->IgnoreCasts if all the 1989 // cast(s) did was sign-extend the original value. 1990 static SVal RecoverCastedSymbol(ProgramStateRef state, 1991 const Stmt *Condition, 1992 const LocationContext *LCtx, 1993 ASTContext &Ctx) { 1994 1995 const auto *Ex = dyn_cast<Expr>(Condition); 1996 if (!Ex) 1997 return UnknownVal(); 1998 1999 uint64_t bits = 0; 2000 bool bitsInit = false; 2001 2002 while (const auto *CE = dyn_cast<CastExpr>(Ex)) { 2003 QualType T = CE->getType(); 2004 2005 if (!T->isIntegralOrEnumerationType()) 2006 return UnknownVal(); 2007 2008 uint64_t newBits = Ctx.getTypeSize(T); 2009 if (!bitsInit || newBits < bits) { 2010 bitsInit = true; 2011 bits = newBits; 2012 } 2013 2014 Ex = CE->getSubExpr(); 2015 } 2016 2017 // We reached a non-cast. Is it a symbolic value? 2018 QualType T = Ex->getType(); 2019 2020 if (!bitsInit || !T->isIntegralOrEnumerationType() || 2021 Ctx.getTypeSize(T) > bits) 2022 return UnknownVal(); 2023 2024 return state->getSVal(Ex, LCtx); 2025 } 2026 2027 #ifndef NDEBUG 2028 static const Stmt *getRightmostLeaf(const Stmt *Condition) { 2029 while (Condition) { 2030 const auto *BO = dyn_cast<BinaryOperator>(Condition); 2031 if (!BO || !BO->isLogicalOp()) { 2032 return Condition; 2033 } 2034 Condition = BO->getRHS()->IgnoreParens(); 2035 } 2036 return nullptr; 2037 } 2038 #endif 2039 2040 // Returns the condition the branch at the end of 'B' depends on and whose value 2041 // has been evaluated within 'B'. 2042 // In most cases, the terminator condition of 'B' will be evaluated fully in 2043 // the last statement of 'B'; in those cases, the resolved condition is the 2044 // given 'Condition'. 2045 // If the condition of the branch is a logical binary operator tree, the CFG is 2046 // optimized: in that case, we know that the expression formed by all but the 2047 // rightmost leaf of the logical binary operator tree must be true, and thus 2048 // the branch condition is at this point equivalent to the truth value of that 2049 // rightmost leaf; the CFG block thus only evaluates this rightmost leaf 2050 // expression in its final statement. As the full condition in that case was 2051 // not evaluated, and is thus not in the SVal cache, we need to use that leaf 2052 // expression to evaluate the truth value of the condition in the current state 2053 // space. 2054 static const Stmt *ResolveCondition(const Stmt *Condition, 2055 const CFGBlock *B) { 2056 if (const auto *Ex = dyn_cast<Expr>(Condition)) 2057 Condition = Ex->IgnoreParens(); 2058 2059 const auto *BO = dyn_cast<BinaryOperator>(Condition); 2060 if (!BO || !BO->isLogicalOp()) 2061 return Condition; 2062 2063 assert(B->getTerminator().isStmtBranch() && 2064 "Other kinds of branches are handled separately!"); 2065 2066 // For logical operations, we still have the case where some branches 2067 // use the traditional "merge" approach and others sink the branch 2068 // directly into the basic blocks representing the logical operation. 2069 // We need to distinguish between those two cases here. 2070 2071 // The invariants are still shifting, but it is possible that the 2072 // last element in a CFGBlock is not a CFGStmt. Look for the last 2073 // CFGStmt as the value of the condition. 2074 CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend(); 2075 for (; I != E; ++I) { 2076 CFGElement Elem = *I; 2077 Optional<CFGStmt> CS = Elem.getAs<CFGStmt>(); 2078 if (!CS) 2079 continue; 2080 const Stmt *LastStmt = CS->getStmt(); 2081 assert(LastStmt == Condition || LastStmt == getRightmostLeaf(Condition)); 2082 return LastStmt; 2083 } 2084 llvm_unreachable("could not resolve condition"); 2085 } 2086 2087 void ExprEngine::processBranch(const Stmt *Condition, 2088 NodeBuilderContext& BldCtx, 2089 ExplodedNode *Pred, 2090 ExplodedNodeSet &Dst, 2091 const CFGBlock *DstT, 2092 const CFGBlock *DstF) { 2093 assert((!Condition || !isa<CXXBindTemporaryExpr>(Condition)) && 2094 "CXXBindTemporaryExprs are handled by processBindTemporary."); 2095 const LocationContext *LCtx = Pred->getLocationContext(); 2096 PrettyStackTraceLocationContext StackCrashInfo(LCtx); 2097 currBldrCtx = &BldCtx; 2098 2099 // Check for NULL conditions; e.g. "for(;;)" 2100 if (!Condition) { 2101 BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF); 2102 NullCondBldr.markInfeasible(false); 2103 NullCondBldr.generateNode(Pred->getState(), true, Pred); 2104 return; 2105 } 2106 2107 if (const auto *Ex = dyn_cast<Expr>(Condition)) 2108 Condition = Ex->IgnoreParens(); 2109 2110 Condition = ResolveCondition(Condition, BldCtx.getBlock()); 2111 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 2112 Condition->getBeginLoc(), 2113 "Error evaluating branch"); 2114 2115 ExplodedNodeSet CheckersOutSet; 2116 getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet, 2117 Pred, *this); 2118 // We generated only sinks. 2119 if (CheckersOutSet.empty()) 2120 return; 2121 2122 BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF); 2123 for (const auto PredI : CheckersOutSet) { 2124 if (PredI->isSink()) 2125 continue; 2126 2127 ProgramStateRef PrevState = PredI->getState(); 2128 SVal X = PrevState->getSVal(Condition, PredI->getLocationContext()); 2129 2130 if (X.isUnknownOrUndef()) { 2131 // Give it a chance to recover from unknown. 2132 if (const auto *Ex = dyn_cast<Expr>(Condition)) { 2133 if (Ex->getType()->isIntegralOrEnumerationType()) { 2134 // Try to recover some path-sensitivity. Right now casts of symbolic 2135 // integers that promote their values are currently not tracked well. 2136 // If 'Condition' is such an expression, try and recover the 2137 // underlying value and use that instead. 2138 SVal recovered = RecoverCastedSymbol(PrevState, Condition, 2139 PredI->getLocationContext(), 2140 getContext()); 2141 2142 if (!recovered.isUnknown()) { 2143 X = recovered; 2144 } 2145 } 2146 } 2147 } 2148 2149 // If the condition is still unknown, give up. 2150 if (X.isUnknownOrUndef()) { 2151 builder.generateNode(PrevState, true, PredI); 2152 builder.generateNode(PrevState, false, PredI); 2153 continue; 2154 } 2155 2156 DefinedSVal V = X.castAs<DefinedSVal>(); 2157 2158 ProgramStateRef StTrue, StFalse; 2159 std::tie(StTrue, StFalse) = PrevState->assume(V); 2160 2161 // Process the true branch. 2162 if (builder.isFeasible(true)) { 2163 if (StTrue) 2164 builder.generateNode(StTrue, true, PredI); 2165 else 2166 builder.markInfeasible(true); 2167 } 2168 2169 // Process the false branch. 2170 if (builder.isFeasible(false)) { 2171 if (StFalse) 2172 builder.generateNode(StFalse, false, PredI); 2173 else 2174 builder.markInfeasible(false); 2175 } 2176 } 2177 currBldrCtx = nullptr; 2178 } 2179 2180 /// The GDM component containing the set of global variables which have been 2181 /// previously initialized with explicit initializers. 2182 REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet, 2183 llvm::ImmutableSet<const VarDecl *>) 2184 2185 void ExprEngine::processStaticInitializer(const DeclStmt *DS, 2186 NodeBuilderContext &BuilderCtx, 2187 ExplodedNode *Pred, 2188 ExplodedNodeSet &Dst, 2189 const CFGBlock *DstT, 2190 const CFGBlock *DstF) { 2191 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 2192 currBldrCtx = &BuilderCtx; 2193 2194 const auto *VD = cast<VarDecl>(DS->getSingleDecl()); 2195 ProgramStateRef state = Pred->getState(); 2196 bool initHasRun = state->contains<InitializedGlobalsSet>(VD); 2197 BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF); 2198 2199 if (!initHasRun) { 2200 state = state->add<InitializedGlobalsSet>(VD); 2201 } 2202 2203 builder.generateNode(state, initHasRun, Pred); 2204 builder.markInfeasible(!initHasRun); 2205 2206 currBldrCtx = nullptr; 2207 } 2208 2209 /// processIndirectGoto - Called by CoreEngine. Used to generate successor 2210 /// nodes by processing the 'effects' of a computed goto jump. 2211 void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { 2212 ProgramStateRef state = builder.getState(); 2213 SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext()); 2214 2215 // Three possibilities: 2216 // 2217 // (1) We know the computed label. 2218 // (2) The label is NULL (or some other constant), or Undefined. 2219 // (3) We have no clue about the label. Dispatch to all targets. 2220 // 2221 2222 using iterator = IndirectGotoNodeBuilder::iterator; 2223 2224 if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) { 2225 const LabelDecl *L = LV->getLabel(); 2226 2227 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) { 2228 if (I.getLabel() == L) { 2229 builder.generateNode(I, state); 2230 return; 2231 } 2232 } 2233 2234 llvm_unreachable("No block with label."); 2235 } 2236 2237 if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) { 2238 // Dispatch to the first target and mark it as a sink. 2239 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); 2240 // FIXME: add checker visit. 2241 // UndefBranches.insert(N); 2242 return; 2243 } 2244 2245 // This is really a catch-all. We don't support symbolics yet. 2246 // FIXME: Implement dispatch for symbolic pointers. 2247 2248 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) 2249 builder.generateNode(I, state); 2250 } 2251 2252 void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC, 2253 ExplodedNode *Pred, 2254 ExplodedNodeSet &Dst, 2255 const BlockEdge &L) { 2256 SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC); 2257 getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this); 2258 } 2259 2260 /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path 2261 /// nodes when the control reaches the end of a function. 2262 void ExprEngine::processEndOfFunction(NodeBuilderContext& BC, 2263 ExplodedNode *Pred, 2264 const ReturnStmt *RS) { 2265 ProgramStateRef State = Pred->getState(); 2266 2267 if (!Pred->getStackFrame()->inTopFrame()) 2268 State = finishArgumentConstruction( 2269 State, *getStateManager().getCallEventManager().getCaller( 2270 Pred->getStackFrame(), Pred->getState())); 2271 2272 // FIXME: We currently cannot assert that temporaries are clear, because 2273 // lifetime extended temporaries are not always modelled correctly. In some 2274 // cases when we materialize the temporary, we do 2275 // createTemporaryRegionIfNeeded(), and the region changes, and also the 2276 // respective destructor becomes automatic from temporary. So for now clean up 2277 // the state manually before asserting. Ideally, this braced block of code 2278 // should go away. 2279 { 2280 const LocationContext *FromLC = Pred->getLocationContext(); 2281 const LocationContext *ToLC = FromLC->getStackFrame()->getParent(); 2282 const LocationContext *LC = FromLC; 2283 while (LC != ToLC) { 2284 assert(LC && "ToLC must be a parent of FromLC!"); 2285 for (auto I : State->get<ObjectsUnderConstruction>()) 2286 if (I.first.getLocationContext() == LC) { 2287 // The comment above only pardons us for not cleaning up a 2288 // temporary destructor. If any other statements are found here, 2289 // it must be a separate problem. 2290 assert(I.first.getItem().getKind() == 2291 ConstructionContextItem::TemporaryDestructorKind || 2292 I.first.getItem().getKind() == 2293 ConstructionContextItem::ElidedDestructorKind); 2294 State = State->remove<ObjectsUnderConstruction>(I.first); 2295 } 2296 LC = LC->getParent(); 2297 } 2298 } 2299 2300 // Perform the transition with cleanups. 2301 if (State != Pred->getState()) { 2302 ExplodedNodeSet PostCleanup; 2303 NodeBuilder Bldr(Pred, PostCleanup, BC); 2304 Pred = Bldr.generateNode(Pred->getLocation(), State, Pred); 2305 if (!Pred) { 2306 // The node with clean temporaries already exists. We might have reached 2307 // it on a path on which we initialize different temporaries. 2308 return; 2309 } 2310 } 2311 2312 assert(areAllObjectsFullyConstructed(Pred->getState(), 2313 Pred->getLocationContext(), 2314 Pred->getStackFrame()->getParent())); 2315 2316 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 2317 2318 ExplodedNodeSet Dst; 2319 if (Pred->getLocationContext()->inTopFrame()) { 2320 // Remove dead symbols. 2321 ExplodedNodeSet AfterRemovedDead; 2322 removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead); 2323 2324 // Notify checkers. 2325 for (const auto I : AfterRemovedDead) 2326 getCheckerManager().runCheckersForEndFunction(BC, Dst, I, *this, RS); 2327 } else { 2328 getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this, RS); 2329 } 2330 2331 Engine.enqueueEndOfFunction(Dst, RS); 2332 } 2333 2334 /// ProcessSwitch - Called by CoreEngine. Used to generate successor 2335 /// nodes by processing the 'effects' of a switch statement. 2336 void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { 2337 using iterator = SwitchNodeBuilder::iterator; 2338 2339 ProgramStateRef state = builder.getState(); 2340 const Expr *CondE = builder.getCondition(); 2341 SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext()); 2342 2343 if (CondV_untested.isUndef()) { 2344 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true); 2345 // FIXME: add checker 2346 //UndefBranches.insert(N); 2347 2348 return; 2349 } 2350 DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>(); 2351 2352 ProgramStateRef DefaultSt = state; 2353 2354 iterator I = builder.begin(), EI = builder.end(); 2355 bool defaultIsFeasible = I == EI; 2356 2357 for ( ; I != EI; ++I) { 2358 // Successor may be pruned out during CFG construction. 2359 if (!I.getBlock()) 2360 continue; 2361 2362 const CaseStmt *Case = I.getCase(); 2363 2364 // Evaluate the LHS of the case value. 2365 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext()); 2366 assert(V1.getBitWidth() == getContext().getIntWidth(CondE->getType())); 2367 2368 // Get the RHS of the case, if it exists. 2369 llvm::APSInt V2; 2370 if (const Expr *E = Case->getRHS()) 2371 V2 = E->EvaluateKnownConstInt(getContext()); 2372 else 2373 V2 = V1; 2374 2375 ProgramStateRef StateCase; 2376 if (Optional<NonLoc> NL = CondV.getAs<NonLoc>()) 2377 std::tie(StateCase, DefaultSt) = 2378 DefaultSt->assumeInclusiveRange(*NL, V1, V2); 2379 else // UnknownVal 2380 StateCase = DefaultSt; 2381 2382 if (StateCase) 2383 builder.generateCaseStmtNode(I, StateCase); 2384 2385 // Now "assume" that the case doesn't match. Add this state 2386 // to the default state (if it is feasible). 2387 if (DefaultSt) 2388 defaultIsFeasible = true; 2389 else { 2390 defaultIsFeasible = false; 2391 break; 2392 } 2393 } 2394 2395 if (!defaultIsFeasible) 2396 return; 2397 2398 // If we have switch(enum value), the default branch is not 2399 // feasible if all of the enum constants not covered by 'case:' statements 2400 // are not feasible values for the switch condition. 2401 // 2402 // Note that this isn't as accurate as it could be. Even if there isn't 2403 // a case for a particular enum value as long as that enum value isn't 2404 // feasible then it shouldn't be considered for making 'default:' reachable. 2405 const SwitchStmt *SS = builder.getSwitch(); 2406 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts(); 2407 if (CondExpr->getType()->getAs<EnumType>()) { 2408 if (SS->isAllEnumCasesCovered()) 2409 return; 2410 } 2411 2412 builder.generateDefaultCaseNode(DefaultSt); 2413 } 2414 2415 //===----------------------------------------------------------------------===// 2416 // Transfer functions: Loads and stores. 2417 //===----------------------------------------------------------------------===// 2418 2419 void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, 2420 ExplodedNode *Pred, 2421 ExplodedNodeSet &Dst) { 2422 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 2423 2424 ProgramStateRef state = Pred->getState(); 2425 const LocationContext *LCtx = Pred->getLocationContext(); 2426 2427 if (const auto *VD = dyn_cast<VarDecl>(D)) { 2428 // C permits "extern void v", and if you cast the address to a valid type, 2429 // you can even do things with it. We simply pretend 2430 assert(Ex->isGLValue() || VD->getType()->isVoidType()); 2431 const LocationContext *LocCtxt = Pred->getLocationContext(); 2432 const Decl *D = LocCtxt->getDecl(); 2433 const auto *MD = dyn_cast_or_null<CXXMethodDecl>(D); 2434 const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Ex); 2435 Optional<std::pair<SVal, QualType>> VInfo; 2436 2437 if (AMgr.options.ShouldInlineLambdas && DeclRefEx && 2438 DeclRefEx->refersToEnclosingVariableOrCapture() && MD && 2439 MD->getParent()->isLambda()) { 2440 // Lookup the field of the lambda. 2441 const CXXRecordDecl *CXXRec = MD->getParent(); 2442 llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields; 2443 FieldDecl *LambdaThisCaptureField; 2444 CXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField); 2445 2446 // Sema follows a sequence of complex rules to determine whether the 2447 // variable should be captured. 2448 if (const FieldDecl *FD = LambdaCaptureFields[VD]) { 2449 Loc CXXThis = 2450 svalBuilder.getCXXThis(MD, LocCtxt->getStackFrame()); 2451 SVal CXXThisVal = state->getSVal(CXXThis); 2452 VInfo = std::make_pair(state->getLValue(FD, CXXThisVal), FD->getType()); 2453 } 2454 } 2455 2456 if (!VInfo) 2457 VInfo = std::make_pair(state->getLValue(VD, LocCtxt), VD->getType()); 2458 2459 SVal V = VInfo->first; 2460 bool IsReference = VInfo->second->isReferenceType(); 2461 2462 // For references, the 'lvalue' is the pointer address stored in the 2463 // reference region. 2464 if (IsReference) { 2465 if (const MemRegion *R = V.getAsRegion()) 2466 V = state->getSVal(R); 2467 else 2468 V = UnknownVal(); 2469 } 2470 2471 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr, 2472 ProgramPoint::PostLValueKind); 2473 return; 2474 } 2475 if (const auto *ED = dyn_cast<EnumConstantDecl>(D)) { 2476 assert(!Ex->isGLValue()); 2477 SVal V = svalBuilder.makeIntVal(ED->getInitVal()); 2478 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V)); 2479 return; 2480 } 2481 if (const auto *FD = dyn_cast<FunctionDecl>(D)) { 2482 SVal V = svalBuilder.getFunctionPointer(FD); 2483 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr, 2484 ProgramPoint::PostLValueKind); 2485 return; 2486 } 2487 if (isa<FieldDecl>(D) || isa<IndirectFieldDecl>(D)) { 2488 // FIXME: Compute lvalue of field pointers-to-member. 2489 // Right now we just use a non-null void pointer, so that it gives proper 2490 // results in boolean contexts. 2491 // FIXME: Maybe delegate this to the surrounding operator&. 2492 // Note how this expression is lvalue, however pointer-to-member is NonLoc. 2493 SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy, 2494 currBldrCtx->blockCount()); 2495 state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true); 2496 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr, 2497 ProgramPoint::PostLValueKind); 2498 return; 2499 } 2500 if (isa<BindingDecl>(D)) { 2501 // FIXME: proper support for bound declarations. 2502 // For now, let's just prevent crashing. 2503 return; 2504 } 2505 2506 llvm_unreachable("Support for this Decl not implemented."); 2507 } 2508 2509 /// VisitArraySubscriptExpr - Transfer function for array accesses 2510 void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A, 2511 ExplodedNode *Pred, 2512 ExplodedNodeSet &Dst){ 2513 const Expr *Base = A->getBase()->IgnoreParens(); 2514 const Expr *Idx = A->getIdx()->IgnoreParens(); 2515 2516 ExplodedNodeSet CheckerPreStmt; 2517 getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, A, *this); 2518 2519 ExplodedNodeSet EvalSet; 2520 StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx); 2521 2522 bool IsVectorType = A->getBase()->getType()->isVectorType(); 2523 2524 // The "like" case is for situations where C standard prohibits the type to 2525 // be an lvalue, e.g. taking the address of a subscript of an expression of 2526 // type "void *". 2527 bool IsGLValueLike = A->isGLValue() || 2528 (A->getType().isCForbiddenLValueType() && !AMgr.getLangOpts().CPlusPlus); 2529 2530 for (auto *Node : CheckerPreStmt) { 2531 const LocationContext *LCtx = Node->getLocationContext(); 2532 ProgramStateRef state = Node->getState(); 2533 2534 if (IsGLValueLike) { 2535 QualType T = A->getType(); 2536 2537 // One of the forbidden LValue types! We still need to have sensible 2538 // symbolic locations to represent this stuff. Note that arithmetic on 2539 // void pointers is a GCC extension. 2540 if (T->isVoidType()) 2541 T = getContext().CharTy; 2542 2543 SVal V = state->getLValue(T, 2544 state->getSVal(Idx, LCtx), 2545 state->getSVal(Base, LCtx)); 2546 Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr, 2547 ProgramPoint::PostLValueKind); 2548 } else if (IsVectorType) { 2549 // FIXME: non-glvalue vector reads are not modelled. 2550 Bldr.generateNode(A, Node, state, nullptr); 2551 } else { 2552 llvm_unreachable("Array subscript should be an lValue when not \ 2553 a vector and not a forbidden lvalue type"); 2554 } 2555 } 2556 2557 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, A, *this); 2558 } 2559 2560 /// VisitMemberExpr - Transfer function for member expressions. 2561 void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, 2562 ExplodedNodeSet &Dst) { 2563 // FIXME: Prechecks eventually go in ::Visit(). 2564 ExplodedNodeSet CheckedSet; 2565 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, M, *this); 2566 2567 ExplodedNodeSet EvalSet; 2568 ValueDecl *Member = M->getMemberDecl(); 2569 2570 // Handle static member variables and enum constants accessed via 2571 // member syntax. 2572 if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) { 2573 for (const auto I : CheckedSet) 2574 VisitCommonDeclRefExpr(M, Member, I, EvalSet); 2575 } else { 2576 StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx); 2577 ExplodedNodeSet Tmp; 2578 2579 for (const auto I : CheckedSet) { 2580 ProgramStateRef state = I->getState(); 2581 const LocationContext *LCtx = I->getLocationContext(); 2582 Expr *BaseExpr = M->getBase(); 2583 2584 // Handle C++ method calls. 2585 if (const auto *MD = dyn_cast<CXXMethodDecl>(Member)) { 2586 if (MD->isInstance()) 2587 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr); 2588 2589 SVal MDVal = svalBuilder.getFunctionPointer(MD); 2590 state = state->BindExpr(M, LCtx, MDVal); 2591 2592 Bldr.generateNode(M, I, state); 2593 continue; 2594 } 2595 2596 // Handle regular struct fields / member variables. 2597 const SubRegion *MR = nullptr; 2598 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr, 2599 /*Result=*/nullptr, 2600 /*OutRegionWithAdjustments=*/&MR); 2601 SVal baseExprVal = 2602 MR ? loc::MemRegionVal(MR) : state->getSVal(BaseExpr, LCtx); 2603 2604 const auto *field = cast<FieldDecl>(Member); 2605 SVal L = state->getLValue(field, baseExprVal); 2606 2607 if (M->isGLValue() || M->getType()->isArrayType()) { 2608 // We special-case rvalues of array type because the analyzer cannot 2609 // reason about them, since we expect all regions to be wrapped in Locs. 2610 // We instead treat these as lvalues and assume that they will decay to 2611 // pointers as soon as they are used. 2612 if (!M->isGLValue()) { 2613 assert(M->getType()->isArrayType()); 2614 const auto *PE = 2615 dyn_cast<ImplicitCastExpr>(I->getParentMap().getParentIgnoreParens(M)); 2616 if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) { 2617 llvm_unreachable("should always be wrapped in ArrayToPointerDecay"); 2618 } 2619 } 2620 2621 if (field->getType()->isReferenceType()) { 2622 if (const MemRegion *R = L.getAsRegion()) 2623 L = state->getSVal(R); 2624 else 2625 L = UnknownVal(); 2626 } 2627 2628 Bldr.generateNode(M, I, state->BindExpr(M, LCtx, L), nullptr, 2629 ProgramPoint::PostLValueKind); 2630 } else { 2631 Bldr.takeNodes(I); 2632 evalLoad(Tmp, M, M, I, state, L); 2633 Bldr.addNodes(Tmp); 2634 } 2635 } 2636 } 2637 2638 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, M, *this); 2639 } 2640 2641 void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred, 2642 ExplodedNodeSet &Dst) { 2643 ExplodedNodeSet AfterPreSet; 2644 getCheckerManager().runCheckersForPreStmt(AfterPreSet, Pred, AE, *this); 2645 2646 // For now, treat all the arguments to C11 atomics as escaping. 2647 // FIXME: Ideally we should model the behavior of the atomics precisely here. 2648 2649 ExplodedNodeSet AfterInvalidateSet; 2650 StmtNodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx); 2651 2652 for (const auto I : AfterPreSet) { 2653 ProgramStateRef State = I->getState(); 2654 const LocationContext *LCtx = I->getLocationContext(); 2655 2656 SmallVector<SVal, 8> ValuesToInvalidate; 2657 for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; SI++) { 2658 const Expr *SubExpr = AE->getSubExprs()[SI]; 2659 SVal SubExprVal = State->getSVal(SubExpr, LCtx); 2660 ValuesToInvalidate.push_back(SubExprVal); 2661 } 2662 2663 State = State->invalidateRegions(ValuesToInvalidate, AE, 2664 currBldrCtx->blockCount(), 2665 LCtx, 2666 /*CausedByPointerEscape*/true, 2667 /*Symbols=*/nullptr); 2668 2669 SVal ResultVal = UnknownVal(); 2670 State = State->BindExpr(AE, LCtx, ResultVal); 2671 Bldr.generateNode(AE, I, State, nullptr, 2672 ProgramPoint::PostStmtKind); 2673 } 2674 2675 getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this); 2676 } 2677 2678 // A value escapes in four possible cases: 2679 // (1) We are binding to something that is not a memory region. 2680 // (2) We are binding to a MemRegion that does not have stack storage. 2681 // (3) We are binding to a top-level parameter region with a non-trivial 2682 // destructor. We won't see the destructor during analysis, but it's there. 2683 // (4) We are binding to a MemRegion with stack storage that the store 2684 // does not understand. 2685 ProgramStateRef 2686 ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc, 2687 SVal Val, const LocationContext *LCtx) { 2688 2689 // Cases (1) and (2). 2690 const MemRegion *MR = Loc.getAsRegion(); 2691 if (!MR || !MR->hasStackStorage()) 2692 return escapeValue(State, Val, PSK_EscapeOnBind); 2693 2694 // Case (3). 2695 if (const auto *VR = dyn_cast<VarRegion>(MR->getBaseRegion())) 2696 if (VR->hasStackParametersStorage() && VR->getStackFrame()->inTopFrame()) 2697 if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl()) 2698 if (!RD->hasTrivialDestructor()) 2699 return escapeValue(State, Val, PSK_EscapeOnBind); 2700 2701 // Case (4): in order to test that, generate a new state with the binding 2702 // added. If it is the same state, then it escapes (since the store cannot 2703 // represent the binding). 2704 // Do this only if we know that the store is not supposed to generate the 2705 // same state. 2706 SVal StoredVal = State->getSVal(MR); 2707 if (StoredVal != Val) 2708 if (State == (State->bindLoc(loc::MemRegionVal(MR), Val, LCtx))) 2709 return escapeValue(State, Val, PSK_EscapeOnBind); 2710 2711 return State; 2712 } 2713 2714 ProgramStateRef 2715 ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, 2716 const InvalidatedSymbols *Invalidated, 2717 ArrayRef<const MemRegion *> ExplicitRegions, 2718 const CallEvent *Call, 2719 RegionAndSymbolInvalidationTraits &ITraits) { 2720 if (!Invalidated || Invalidated->empty()) 2721 return State; 2722 2723 if (!Call) 2724 return getCheckerManager().runCheckersForPointerEscape(State, 2725 *Invalidated, 2726 nullptr, 2727 PSK_EscapeOther, 2728 &ITraits); 2729 2730 // If the symbols were invalidated by a call, we want to find out which ones 2731 // were invalidated directly due to being arguments to the call. 2732 InvalidatedSymbols SymbolsDirectlyInvalidated; 2733 for (const auto I : ExplicitRegions) { 2734 if (const SymbolicRegion *R = I->StripCasts()->getAs<SymbolicRegion>()) 2735 SymbolsDirectlyInvalidated.insert(R->getSymbol()); 2736 } 2737 2738 InvalidatedSymbols SymbolsIndirectlyInvalidated; 2739 for (const auto &sym : *Invalidated) { 2740 if (SymbolsDirectlyInvalidated.count(sym)) 2741 continue; 2742 SymbolsIndirectlyInvalidated.insert(sym); 2743 } 2744 2745 if (!SymbolsDirectlyInvalidated.empty()) 2746 State = getCheckerManager().runCheckersForPointerEscape(State, 2747 SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits); 2748 2749 // Notify about the symbols that get indirectly invalidated by the call. 2750 if (!SymbolsIndirectlyInvalidated.empty()) 2751 State = getCheckerManager().runCheckersForPointerEscape(State, 2752 SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits); 2753 2754 return State; 2755 } 2756 2757 /// evalBind - Handle the semantics of binding a value to a specific location. 2758 /// This method is used by evalStore and (soon) VisitDeclStmt, and others. 2759 void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, 2760 ExplodedNode *Pred, 2761 SVal location, SVal Val, 2762 bool atDeclInit, const ProgramPoint *PP) { 2763 const LocationContext *LC = Pred->getLocationContext(); 2764 PostStmt PS(StoreE, LC); 2765 if (!PP) 2766 PP = &PS; 2767 2768 // Do a previsit of the bind. 2769 ExplodedNodeSet CheckedSet; 2770 getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val, 2771 StoreE, *this, *PP); 2772 2773 StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx); 2774 2775 // If the location is not a 'Loc', it will already be handled by 2776 // the checkers. There is nothing left to do. 2777 if (!location.getAs<Loc>()) { 2778 const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr, 2779 /*tag*/nullptr); 2780 ProgramStateRef state = Pred->getState(); 2781 state = processPointerEscapedOnBind(state, location, Val, LC); 2782 Bldr.generateNode(L, state, Pred); 2783 return; 2784 } 2785 2786 for (const auto PredI : CheckedSet) { 2787 ProgramStateRef state = PredI->getState(); 2788 2789 state = processPointerEscapedOnBind(state, location, Val, LC); 2790 2791 // When binding the value, pass on the hint that this is a initialization. 2792 // For initializations, we do not need to inform clients of region 2793 // changes. 2794 state = state->bindLoc(location.castAs<Loc>(), 2795 Val, LC, /* notifyChanges = */ !atDeclInit); 2796 2797 const MemRegion *LocReg = nullptr; 2798 if (Optional<loc::MemRegionVal> LocRegVal = 2799 location.getAs<loc::MemRegionVal>()) { 2800 LocReg = LocRegVal->getRegion(); 2801 } 2802 2803 const ProgramPoint L = PostStore(StoreE, LC, LocReg, nullptr); 2804 Bldr.generateNode(L, state, PredI); 2805 } 2806 } 2807 2808 /// evalStore - Handle the semantics of a store via an assignment. 2809 /// @param Dst The node set to store generated state nodes 2810 /// @param AssignE The assignment expression if the store happens in an 2811 /// assignment. 2812 /// @param LocationE The location expression that is stored to. 2813 /// @param state The current simulation state 2814 /// @param location The location to store the value 2815 /// @param Val The value to be stored 2816 void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, 2817 const Expr *LocationE, 2818 ExplodedNode *Pred, 2819 ProgramStateRef state, SVal location, SVal Val, 2820 const ProgramPointTag *tag) { 2821 // Proceed with the store. We use AssignE as the anchor for the PostStore 2822 // ProgramPoint if it is non-NULL, and LocationE otherwise. 2823 const Expr *StoreE = AssignE ? AssignE : LocationE; 2824 2825 // Evaluate the location (checks for bad dereferences). 2826 ExplodedNodeSet Tmp; 2827 evalLocation(Tmp, AssignE, LocationE, Pred, state, location, false); 2828 2829 if (Tmp.empty()) 2830 return; 2831 2832 if (location.isUndef()) 2833 return; 2834 2835 for (const auto I : Tmp) 2836 evalBind(Dst, StoreE, I, location, Val, false); 2837 } 2838 2839 void ExprEngine::evalLoad(ExplodedNodeSet &Dst, 2840 const Expr *NodeEx, 2841 const Expr *BoundEx, 2842 ExplodedNode *Pred, 2843 ProgramStateRef state, 2844 SVal location, 2845 const ProgramPointTag *tag, 2846 QualType LoadTy) { 2847 assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc."); 2848 assert(NodeEx); 2849 assert(BoundEx); 2850 // Evaluate the location (checks for bad dereferences). 2851 ExplodedNodeSet Tmp; 2852 evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, true); 2853 if (Tmp.empty()) 2854 return; 2855 2856 StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx); 2857 if (location.isUndef()) 2858 return; 2859 2860 // Proceed with the load. 2861 for (const auto I : Tmp) { 2862 state = I->getState(); 2863 const LocationContext *LCtx = I->getLocationContext(); 2864 2865 SVal V = UnknownVal(); 2866 if (location.isValid()) { 2867 if (LoadTy.isNull()) 2868 LoadTy = BoundEx->getType(); 2869 V = state->getSVal(location.castAs<Loc>(), LoadTy); 2870 } 2871 2872 Bldr.generateNode(NodeEx, I, state->BindExpr(BoundEx, LCtx, V), tag, 2873 ProgramPoint::PostLoadKind); 2874 } 2875 } 2876 2877 void ExprEngine::evalLocation(ExplodedNodeSet &Dst, 2878 const Stmt *NodeEx, 2879 const Stmt *BoundEx, 2880 ExplodedNode *Pred, 2881 ProgramStateRef state, 2882 SVal location, 2883 bool isLoad) { 2884 StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx); 2885 // Early checks for performance reason. 2886 if (location.isUnknown()) { 2887 return; 2888 } 2889 2890 ExplodedNodeSet Src; 2891 BldrTop.takeNodes(Pred); 2892 StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx); 2893 if (Pred->getState() != state) { 2894 // Associate this new state with an ExplodedNode. 2895 // FIXME: If I pass null tag, the graph is incorrect, e.g for 2896 // int *p; 2897 // p = 0; 2898 // *p = 0xDEADBEEF; 2899 // "p = 0" is not noted as "Null pointer value stored to 'p'" but 2900 // instead "int *p" is noted as 2901 // "Variable 'p' initialized to a null pointer value" 2902 2903 static SimpleProgramPointTag tag(TagProviderName, "Location"); 2904 Bldr.generateNode(NodeEx, Pred, state, &tag); 2905 } 2906 ExplodedNodeSet Tmp; 2907 getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad, 2908 NodeEx, BoundEx, *this); 2909 BldrTop.addNodes(Tmp); 2910 } 2911 2912 std::pair<const ProgramPointTag *, const ProgramPointTag*> 2913 ExprEngine::geteagerlyAssumeBinOpBifurcationTags() { 2914 static SimpleProgramPointTag 2915 eagerlyAssumeBinOpBifurcationTrue(TagProviderName, 2916 "Eagerly Assume True"), 2917 eagerlyAssumeBinOpBifurcationFalse(TagProviderName, 2918 "Eagerly Assume False"); 2919 return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue, 2920 &eagerlyAssumeBinOpBifurcationFalse); 2921 } 2922 2923 void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst, 2924 ExplodedNodeSet &Src, 2925 const Expr *Ex) { 2926 StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx); 2927 2928 for (const auto Pred : Src) { 2929 // Test if the previous node was as the same expression. This can happen 2930 // when the expression fails to evaluate to anything meaningful and 2931 // (as an optimization) we don't generate a node. 2932 ProgramPoint P = Pred->getLocation(); 2933 if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) { 2934 continue; 2935 } 2936 2937 ProgramStateRef state = Pred->getState(); 2938 SVal V = state->getSVal(Ex, Pred->getLocationContext()); 2939 Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>(); 2940 if (SEV && SEV->isExpression()) { 2941 const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags = 2942 geteagerlyAssumeBinOpBifurcationTags(); 2943 2944 ProgramStateRef StateTrue, StateFalse; 2945 std::tie(StateTrue, StateFalse) = state->assume(*SEV); 2946 2947 // First assume that the condition is true. 2948 if (StateTrue) { 2949 SVal Val = svalBuilder.makeIntVal(1U, Ex->getType()); 2950 StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val); 2951 Bldr.generateNode(Ex, Pred, StateTrue, tags.first); 2952 } 2953 2954 // Next, assume that the condition is false. 2955 if (StateFalse) { 2956 SVal Val = svalBuilder.makeIntVal(0U, Ex->getType()); 2957 StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val); 2958 Bldr.generateNode(Ex, Pred, StateFalse, tags.second); 2959 } 2960 } 2961 } 2962 } 2963 2964 void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred, 2965 ExplodedNodeSet &Dst) { 2966 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 2967 // We have processed both the inputs and the outputs. All of the outputs 2968 // should evaluate to Locs. Nuke all of their values. 2969 2970 // FIXME: Some day in the future it would be nice to allow a "plug-in" 2971 // which interprets the inline asm and stores proper results in the 2972 // outputs. 2973 2974 ProgramStateRef state = Pred->getState(); 2975 2976 for (const Expr *O : A->outputs()) { 2977 SVal X = state->getSVal(O, Pred->getLocationContext()); 2978 assert(!X.getAs<NonLoc>()); // Should be an Lval, or unknown, undef. 2979 2980 if (Optional<Loc> LV = X.getAs<Loc>()) 2981 state = state->bindLoc(*LV, UnknownVal(), Pred->getLocationContext()); 2982 } 2983 2984 Bldr.generateNode(A, Pred, state); 2985 } 2986 2987 void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred, 2988 ExplodedNodeSet &Dst) { 2989 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 2990 Bldr.generateNode(A, Pred, Pred->getState()); 2991 } 2992 2993 //===----------------------------------------------------------------------===// 2994 // Visualization. 2995 //===----------------------------------------------------------------------===// 2996 2997 #ifndef NDEBUG 2998 namespace llvm { 2999 3000 template<> 3001 struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits { 3002 DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} 3003 3004 static bool nodeHasBugReport(const ExplodedNode *N) { 3005 BugReporter &BR = static_cast<ExprEngine &>( 3006 N->getState()->getStateManager().getOwningEngine()).getBugReporter(); 3007 3008 const auto EQClasses = 3009 llvm::make_range(BR.EQClasses_begin(), BR.EQClasses_end()); 3010 3011 for (const auto &EQ : EQClasses) { 3012 for (const auto &I : EQ.getReports()) { 3013 const auto *PR = dyn_cast<PathSensitiveBugReport>(I.get()); 3014 if (!PR) 3015 continue; 3016 const ExplodedNode *EN = PR->getErrorNode(); 3017 if (EN->getState() == N->getState() && 3018 EN->getLocation() == N->getLocation()) 3019 return true; 3020 } 3021 } 3022 return false; 3023 } 3024 3025 /// \p PreCallback: callback before break. 3026 /// \p PostCallback: callback after break. 3027 /// \p Stop: stop iteration if returns {@code true} 3028 /// \return Whether {@code Stop} ever returned {@code true}. 3029 static bool traverseHiddenNodes( 3030 const ExplodedNode *N, 3031 llvm::function_ref<void(const ExplodedNode *)> PreCallback, 3032 llvm::function_ref<void(const ExplodedNode *)> PostCallback, 3033 llvm::function_ref<bool(const ExplodedNode *)> Stop) { 3034 while (true) { 3035 PreCallback(N); 3036 if (Stop(N)) 3037 return true; 3038 3039 if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc())) 3040 break; 3041 PostCallback(N); 3042 3043 N = N->getFirstSucc(); 3044 } 3045 return false; 3046 } 3047 3048 static bool isNodeHidden(const ExplodedNode *N) { 3049 return N->isTrivial(); 3050 } 3051 3052 static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){ 3053 std::string Buf; 3054 llvm::raw_string_ostream Out(Buf); 3055 3056 const bool IsDot = true; 3057 const unsigned int Space = 1; 3058 ProgramStateRef State = N->getState(); 3059 3060 Out << "{ \"state_id\": " << State->getID() 3061 << ",\\l"; 3062 3063 Indent(Out, Space, IsDot) << "\"program_points\": [\\l"; 3064 3065 // Dump program point for all the previously skipped nodes. 3066 traverseHiddenNodes( 3067 N, 3068 [&](const ExplodedNode *OtherNode) { 3069 Indent(Out, Space + 1, IsDot) << "{ "; 3070 OtherNode->getLocation().printJson(Out, /*NL=*/"\\l"); 3071 Out << ", \"tag\": "; 3072 if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag()) 3073 Out << '\"' << Tag->getTagDescription() << "\""; 3074 else 3075 Out << "null"; 3076 Out << ", \"node_id\": " << OtherNode->getID() << 3077 ", \"is_sink\": " << OtherNode->isSink() << 3078 ", \"has_report\": " << nodeHasBugReport(OtherNode) << " }"; 3079 }, 3080 // Adds a comma and a new-line between each program point. 3081 [&](const ExplodedNode *) { Out << ",\\l"; }, 3082 [&](const ExplodedNode *) { return false; }); 3083 3084 Out << "\\l"; // Adds a new-line to the last program point. 3085 Indent(Out, Space, IsDot) << "],\\l"; 3086 3087 State->printDOT(Out, N->getLocationContext(), Space); 3088 3089 Out << "\\l}\\l"; 3090 return Out.str(); 3091 } 3092 }; 3093 3094 } // namespace llvm 3095 #endif 3096 3097 void ExprEngine::ViewGraph(bool trim) { 3098 #ifndef NDEBUG 3099 std::string Filename = DumpGraph(trim); 3100 llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT); 3101 #endif 3102 llvm::errs() << "Warning: viewing graph requires assertions" << "\n"; 3103 } 3104 3105 3106 void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) { 3107 #ifndef NDEBUG 3108 std::string Filename = DumpGraph(Nodes); 3109 llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT); 3110 #endif 3111 llvm::errs() << "Warning: viewing graph requires assertions" << "\n"; 3112 } 3113 3114 std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) { 3115 #ifndef NDEBUG 3116 if (trim) { 3117 std::vector<const ExplodedNode *> Src; 3118 3119 // Iterate through the reports and get their nodes. 3120 for (BugReporter::EQClasses_iterator 3121 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) { 3122 const auto *R = 3123 dyn_cast<PathSensitiveBugReport>(EI->getReports()[0].get()); 3124 if (!R) 3125 continue; 3126 const auto *N = const_cast<ExplodedNode *>(R->getErrorNode()); 3127 Src.push_back(N); 3128 } 3129 return DumpGraph(Src, Filename); 3130 } else { 3131 return llvm::WriteGraph(&G, "ExprEngine", /*ShortNames=*/false, 3132 /*Title=*/"Exploded Graph", /*Filename=*/Filename); 3133 } 3134 #endif 3135 llvm::errs() << "Warning: dumping graph requires assertions" << "\n"; 3136 return ""; 3137 } 3138 3139 std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode*> Nodes, 3140 StringRef Filename) { 3141 #ifndef NDEBUG 3142 std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes)); 3143 3144 if (!TrimmedG.get()) { 3145 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; 3146 } else { 3147 return llvm::WriteGraph(TrimmedG.get(), "TrimmedExprEngine", 3148 /*ShortNames=*/false, 3149 /*Title=*/"Trimmed Exploded Graph", 3150 /*Filename=*/Filename); 3151 } 3152 #endif 3153 llvm::errs() << "Warning: dumping graph requires assertions" << "\n"; 3154 return ""; 3155 } 3156 3157 void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() { 3158 static int index = 0; 3159 return &index; 3160 } 3161