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