ExprEngine.cpp revision c0e71a15bce9bb8c0d4ec1c42fab70c03140f9e0
1e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott//=-- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-= 2e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 3e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// The LLVM Compiler Infrastructure 4e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 5e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// This file is distributed under the University of Illinois Open Source 6e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// License. See LICENSE.TXT for details. 7e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 8e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott//===----------------------------------------------------------------------===// 9e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 10e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// This file defines a meta-engine for path-sensitive dataflow analysis that 11e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// is built on GREngine, but provides the boilerplate to execute transfer 12e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// functions and build the ExplodedGraph at the expression level. 13e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 14e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott//===----------------------------------------------------------------------===// 15e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 16e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#define DEBUG_TYPE "ExprEngine" 17e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 18e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/StaticAnalyzer/Core/CheckerManager.h" 19e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 20e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 21e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 22e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" 23e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/AST/CharUnits.h" 24e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/AST/ParentMap.h" 25e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/AST/StmtObjC.h" 26e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/AST/StmtCXX.h" 27e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/AST/DeclCXX.h" 28e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/Basic/Builtins.h" 29e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/Basic/SourceManager.h" 30e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "clang/Basic/PrettyStackTrace.h" 31e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "llvm/Support/raw_ostream.h" 32e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "llvm/ADT/ImmutableList.h" 33e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "llvm/ADT/Statistic.h" 34e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 35e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#ifndef NDEBUG 36e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "llvm/Support/GraphWriter.h" 37e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif 38e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 39e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottusing namespace clang; 40e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottusing namespace ento; 41e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottusing llvm::APSInt; 42e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 43e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick ScottSTATISTIC(NumRemoveDeadBindings, 44e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "The # of times RemoveDeadBindings is called"); 45e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick ScottSTATISTIC(NumMaxBlockCountReached, 46e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "The # of aborted paths due to reaching the maximum block count in " 47e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "a top level function"); 48e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick ScottSTATISTIC(NumMaxBlockCountReachedInInlined, 49e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "The # of aborted paths due to reaching the maximum block count in " 50e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "an inlined function"); 51e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick ScottSTATISTIC(NumTimesRetriedWithoutInlining, 52e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "The # of times we re-evaluated a call without inlining"); 53e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 54e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott//===----------------------------------------------------------------------===// 55e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// Utility functions. 56e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott//===----------------------------------------------------------------------===// 57e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 58e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstatic inline Selector GetNullarySelector(const char* name, ASTContext &Ctx) { 59e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott IdentifierInfo* II = &Ctx.Idents.get(name); 60e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return Ctx.Selectors.getSelector(0, &II); 61e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 62e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 63e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott//===----------------------------------------------------------------------===// 64e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// Engine construction and deletion. 65e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott//===----------------------------------------------------------------------===// 66e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 67e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick ScottExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled, 68e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SetOfConstDecls *VisitedCallees, 69e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott FunctionSummariesTy *FS) 70e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott : AMgr(mgr), 71e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), 72e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott Engine(*this, VisitedCallees, FS), 73e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott G(Engine.getGraph()), 74e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott StateMgr(getContext(), mgr.getStoreManagerCreator(), 75e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mgr.getConstraintManagerCreator(), G.getAllocator(), 76e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott *this), 77e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SymMgr(StateMgr.getSymbolManager()), 78e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott svalBuilder(StateMgr.getSValBuilder()), 79e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EntryNode(NULL), 80e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott currentStmt(NULL), currentStmtIdx(0), currentBuilderContext(0), 81e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL), 82e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott RaiseSel(GetNullarySelector("raise", getContext())), 83e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ObjCGCEnabled(gcEnabled), BR(mgr, *this) { 84e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 85e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (mgr.shouldEagerlyTrimExplodedGraph()) { 86e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Enable eager node reclaimation when constructing the ExplodedGraph. 87e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott G.enableNodeReclamation(); 88e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 89e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 90e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 91e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick ScottExprEngine::~ExprEngine() { 92e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott BR.FlushReports(); 93e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott delete [] NSExceptionInstanceRaiseSelectors; 94e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 95e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 96e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott//===----------------------------------------------------------------------===// 97e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// Utility methods. 98e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott//===----------------------------------------------------------------------===// 99e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 100e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick ScottProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { 101e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ProgramStateRef state = StateMgr.getInitialState(InitLoc); 102e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const Decl *D = InitLoc->getDecl(); 103e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 104e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Preconditions. 105e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // FIXME: It would be nice if we had a more general mechanism to add 106e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // such preconditions. Some day. 107e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott do { 108e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 109e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 110e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Precondition: the first argument of 'main' is an integer guaranteed 111e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // to be > 0. 112e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const IdentifierInfo *II = FD->getIdentifier(); 113e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (!II || !(II->getName() == "main" && FD->getNumParams() > 0)) 114e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott break; 115e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 116e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const ParmVarDecl *PD = FD->getParamDecl(0); 117e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott QualType T = PD->getType(); 118e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (!T->isIntegerType()) 119e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott break; 120e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 121e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const MemRegion *R = state->getRegion(PD, InitLoc); 122e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (!R) 123e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott break; 124e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 125e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SVal V = state->getSVal(loc::MemRegionVal(R)); 126e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SVal Constraint_untested = evalBinOp(state, BO_GT, V, 127e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott svalBuilder.makeZeroVal(T), 128e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott getContext().IntTy); 129e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 130e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott DefinedOrUnknownSVal *Constraint = 131e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott dyn_cast<DefinedOrUnknownSVal>(&Constraint_untested); 132e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 133e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (!Constraint) 134e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott break; 135e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 136e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (ProgramStateRef newState = state->assume(*Constraint, true)) 137e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott state = newState; 138e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 139e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott break; 140e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 141e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott while (0); 142e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 143e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) { 144e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Precondition: 'self' is always non-null upon entry to an Objective-C 145e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // method. 146e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const ImplicitParamDecl *SelfD = MD->getSelfDecl(); 147e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const MemRegion *R = state->getRegion(SelfD, InitLoc); 148e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SVal V = state->getSVal(loc::MemRegionVal(R)); 149e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 150e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (const Loc *LV = dyn_cast<Loc>(&V)) { 151e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Assume that the pointer value in 'self' is non-null. 152e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott state = state->assume(*LV, true); 153e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott assert(state && "'self' cannot be null"); 154e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 155e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 156e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 157e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) { 158e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (!MD->isStatic()) { 159e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Precondition: 'this' is always non-null upon entry to the 160e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // top-level function. This is our starting assumption for 161e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // analyzing an "open" program. 162e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const StackFrameContext *SFC = InitLoc->getCurrentStackFrame(); 163e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (SFC->getParent() == 0) { 164e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott loc::MemRegionVal L(getCXXThisRegion(MD, SFC)); 165e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SVal V = state->getSVal(L); 166e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (const Loc *LV = dyn_cast<Loc>(&V)) { 167e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott state = state->assume(*LV, true); 168e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott assert(state && "'this' cannot be null"); 169e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 170e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 171e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 172e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 173e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 174e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return state; 175e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 176e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 177e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott//===----------------------------------------------------------------------===// 178e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// Top-level transfer function logic (Dispatcher). 179e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott//===----------------------------------------------------------------------===// 180e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 181e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott/// evalAssume - Called by ConstraintManager. Used to call checker-specific 182e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott/// logic for handling assumptions on symbolic values. 183e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick ScottProgramStateRef ExprEngine::processAssume(ProgramStateRef state, 184e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SVal cond, bool assumption) { 185e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption); 186e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 187e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 188e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottbool ExprEngine::wantsRegionChangeUpdate(ProgramStateRef state) { 189e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return getCheckerManager().wantsRegionChangeUpdate(state); 190e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 191e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 192e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick ScottProgramStateRef 193e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick ScottExprEngine::processRegionChanges(ProgramStateRef state, 194e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const StoreManager::InvalidatedSymbols *invalidated, 195e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ArrayRef<const MemRegion *> Explicits, 196e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ArrayRef<const MemRegion *> Regions, 197e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const CallOrObjCMessage *Call) { 198e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return getCheckerManager().runCheckersForRegionChanges(state, invalidated, 199e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott Explicits, Regions, Call); 200e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 201e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 202e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid ExprEngine::printState(raw_ostream &Out, ProgramStateRef State, 203e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const char *NL, const char *Sep) { 204e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep); 205e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 206e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 207e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid ExprEngine::processEndWorklist(bool hasWorkRemaining) { 208e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); 209e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 210e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 211e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, 212e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott unsigned StmtIdx, NodeBuilderContext *Ctx) { 213e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott currentStmtIdx = StmtIdx; 214e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott currentBuilderContext = Ctx; 215e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 216e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott switch (E.getKind()) { 217e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott case CFGElement::Invalid: 218e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott llvm_unreachable("Unexpected CFGElement kind."); 219e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott case CFGElement::Statement: 220e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ProcessStmt(const_cast<Stmt*>(E.getAs<CFGStmt>()->getStmt()), Pred); 221e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return; 222e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott case CFGElement::Initializer: 223e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ProcessInitializer(E.getAs<CFGInitializer>()->getInitializer(), Pred); 224e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return; 225e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott case CFGElement::AutomaticObjectDtor: 226e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott case CFGElement::BaseDtor: 227e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott case CFGElement::MemberDtor: 228e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott case CFGElement::TemporaryDtor: 229e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ProcessImplicitDtor(*E.getAs<CFGImplicitDtor>(), Pred); 230e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return; 231e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 232e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott currentBuilderContext = 0; 233e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 234e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 235e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstatic bool shouldRemoveDeadBindings(AnalysisManager &AMgr, 236e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const CFGStmt S, 237e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const ExplodedNode *Pred, 238e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const LocationContext *LC) { 239e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 240e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Are we never purging state values? 241e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (AMgr.getPurgeMode() == PurgeNone) 242e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return false; 243e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 244e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Is this the beginning of a basic block? 245e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (isa<BlockEntrance>(Pred->getLocation())) 246e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return true; 247e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 248e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Is this on a non-expression? 249e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (!isa<Expr>(S.getStmt())) 250e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return true; 251e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 252e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Run before processing a call. 253e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (CallOrObjCMessage::canBeInlined(S.getStmt())) 254e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return true; 255e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 256e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Is this an expression that is consumed by another expression? If so, 257e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // postpone cleaning out the state. 258e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap(); 259e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return !PM.isConsumedExpr(cast<Expr>(S.getStmt())); 260e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 261e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 262e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out, 263e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const Stmt *ReferenceStmt, 264e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const LocationContext *LC, 265e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const Stmt *DiagnosticStmt, 266e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ProgramPoint::Kind K) { 267e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind || 268e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ReferenceStmt == 0) && "PreStmt is not generally supported by " 269e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "the SymbolReaper yet"); 270e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott NumRemoveDeadBindings++; 271e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CleanedState = Pred->getState(); 272e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SymbolReaper SymReaper(LC, ReferenceStmt, SymMgr, getStoreManager()); 273e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 274e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper); 275e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 276e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Create a state in which dead bindings are removed from the environment 277e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // and the store. TODO: The function should just return new env and store, 278e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // not a new state. 279e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const StackFrameContext *SFC = LC->getCurrentStackFrame(); 280e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper); 281e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 282e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Process any special transfer function for dead symbols. 283e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // A tag to track convenience transitions, which can be removed at cleanup. 284e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node"); 285e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (!SymReaper.hasDeadSymbols()) { 286e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Generate a CleanedNode that has the environment and store cleaned 287e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // up. Since no symbols are dead, we can optimize and not clean out 288e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // the constraint manager. 289e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott StmtNodeBuilder Bldr(Pred, Out, *currentBuilderContext); 290e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, false, &cleanupTag,K); 291e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 292e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } else { 293e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Call checkers with the non-cleaned state so that they could query the 294e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // values of the soon to be dead symbols. 295e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ExplodedNodeSet CheckedSet; 296e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper, 297e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott DiagnosticStmt, *this, K); 298e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 299e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // For each node in CheckedSet, generate CleanedNodes that have the 300e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // environment, the store, and the constraints cleaned up but have the 301e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // user-supplied states as the predecessors. 302e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott StmtNodeBuilder Bldr(CheckedSet, Out, *currentBuilderContext); 303e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for (ExplodedNodeSet::const_iterator 304e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) { 305e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ProgramStateRef CheckerState = (*I)->getState(); 306e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 307e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // The constraint manager has not been cleaned up yet, so clean up now. 308e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CheckerState = getConstraintManager().removeDeadBindings(CheckerState, 309e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SymReaper); 310e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 311e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) && 312e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "Checkers are not allowed to modify the Environment as a part of " 313e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "checkDeadSymbols processing."); 314e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) && 315e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "Checkers are not allowed to modify the Store as a part of " 316e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "checkDeadSymbols processing."); 317e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 318e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Create a state based on CleanedState with CheckerState GDM and 319e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // generate a transition to that state. 320e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ProgramStateRef CleanedCheckerSt = 321e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState); 322e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott Bldr.generateNode(DiagnosticStmt, *I, CleanedCheckerSt, false, 323e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott &cleanupTag, K); 324e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 325e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 326e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 327e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 328e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid ExprEngine::ProcessStmt(const CFGStmt S, 329e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ExplodedNode *Pred) { 330e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Reclaim any unnecessary nodes in the ExplodedGraph. 331e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott G.reclaimRecentlyAllocatedNodes(); 332e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 333e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott currentStmt = S.getStmt(); 334e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 335e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott currentStmt->getLocStart(), 336e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "Error evaluating statement"); 337e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 338e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Remove dead bindings and symbols. 339e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EntryNode = Pred; 340e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ExplodedNodeSet CleanedStates; 341e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (shouldRemoveDeadBindings(AMgr, S, Pred, EntryNode->getLocationContext())){ 342e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott removeDead(EntryNode, CleanedStates, currentStmt, 343e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott Pred->getLocationContext(), currentStmt); 344e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } else 345e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CleanedStates.Add(EntryNode); 346e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 347e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Visit the statement. 348e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ExplodedNodeSet Dst; 349e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for (ExplodedNodeSet::iterator I = CleanedStates.begin(), 350e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott E = CleanedStates.end(); I != E; ++I) { 351e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ExplodedNodeSet DstI; 352e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Visit the statement. 353e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott Visit(currentStmt, *I, DstI); 354e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott Dst.insert(DstI); 355e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 356e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 357e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Enqueue the new nodes onto the work list. 358e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); 359e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 360e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // NULL out these variables to cleanup. 361e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott CleanedState = NULL; 362e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EntryNode = NULL; 363e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott currentStmt = 0; 364e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 365 366void ExprEngine::ProcessInitializer(const CFGInitializer Init, 367 ExplodedNode *Pred) { 368 ExplodedNodeSet Dst; 369 370 // We don't set EntryNode and currentStmt. And we don't clean up state. 371 const CXXCtorInitializer *BMI = Init.getInitializer(); 372 const StackFrameContext *stackFrame = 373 cast<StackFrameContext>(Pred->getLocationContext()); 374 const CXXConstructorDecl *decl = 375 cast<CXXConstructorDecl>(stackFrame->getDecl()); 376 const CXXThisRegion *thisReg = getCXXThisRegion(decl, stackFrame); 377 378 SVal thisVal = Pred->getState()->getSVal(thisReg); 379 380 if (BMI->isAnyMemberInitializer()) { 381 // Evaluate the initializer. 382 383 StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 384 ProgramStateRef state = Pred->getState(); 385 386 const FieldDecl *FD = BMI->getAnyMember(); 387 388 SVal FieldLoc = state->getLValue(FD, thisVal); 389 SVal InitVal = state->getSVal(BMI->getInit(), Pred->getLocationContext()); 390 state = state->bindLoc(FieldLoc, InitVal); 391 392 // Use a custom node building process. 393 PostInitializer PP(BMI, stackFrame); 394 // Builder automatically add the generated node to the deferred set, 395 // which are processed in the builder's dtor. 396 Bldr.generateNode(PP, Pred, state); 397 } else { 398 assert(BMI->isBaseInitializer()); 399 400 // Get the base class declaration. 401 const CXXConstructExpr *ctorExpr = cast<CXXConstructExpr>(BMI->getInit()); 402 403 // Create the base object region. 404 SVal baseVal = 405 getStoreManager().evalDerivedToBase(thisVal, ctorExpr->getType()); 406 const MemRegion *baseReg = baseVal.getAsRegion(); 407 assert(baseReg); 408 409 VisitCXXConstructExpr(ctorExpr, baseReg, Pred, Dst); 410 } 411 412 // Enqueue the new nodes onto the work list. 413 Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); 414} 415 416void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, 417 ExplodedNode *Pred) { 418 ExplodedNodeSet Dst; 419 switch (D.getKind()) { 420 case CFGElement::AutomaticObjectDtor: 421 ProcessAutomaticObjDtor(cast<CFGAutomaticObjDtor>(D), Pred, Dst); 422 break; 423 case CFGElement::BaseDtor: 424 ProcessBaseDtor(cast<CFGBaseDtor>(D), Pred, Dst); 425 break; 426 case CFGElement::MemberDtor: 427 ProcessMemberDtor(cast<CFGMemberDtor>(D), Pred, Dst); 428 break; 429 case CFGElement::TemporaryDtor: 430 ProcessTemporaryDtor(cast<CFGTemporaryDtor>(D), Pred, Dst); 431 break; 432 default: 433 llvm_unreachable("Unexpected dtor kind."); 434 } 435 436 // Enqueue the new nodes onto the work list. 437 Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); 438} 439 440void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, 441 ExplodedNode *Pred, 442 ExplodedNodeSet &Dst) { 443 ProgramStateRef state = Pred->getState(); 444 const VarDecl *varDecl = Dtor.getVarDecl(); 445 446 QualType varType = varDecl->getType(); 447 448 if (const ReferenceType *refType = varType->getAs<ReferenceType>()) 449 varType = refType->getPointeeType(); 450 451 const CXXRecordDecl *recordDecl = varType->getAsCXXRecordDecl(); 452 assert(recordDecl && "get CXXRecordDecl fail"); 453 const CXXDestructorDecl *dtorDecl = recordDecl->getDestructor(); 454 455 Loc dest = state->getLValue(varDecl, Pred->getLocationContext()); 456 457 VisitCXXDestructor(dtorDecl, cast<loc::MemRegionVal>(dest).getRegion(), 458 Dtor.getTriggerStmt(), Pred, Dst); 459} 460 461void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, 462 ExplodedNode *Pred, ExplodedNodeSet &Dst) {} 463 464void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, 465 ExplodedNode *Pred, ExplodedNodeSet &Dst) {} 466 467void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, 468 ExplodedNode *Pred, 469 ExplodedNodeSet &Dst) {} 470 471void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, 472 ExplodedNodeSet &DstTop) { 473 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 474 S->getLocStart(), 475 "Error evaluating statement"); 476 ExplodedNodeSet Dst; 477 StmtNodeBuilder Bldr(Pred, DstTop, *currentBuilderContext); 478 479 // Expressions to ignore. 480 if (const Expr *Ex = dyn_cast<Expr>(S)) 481 S = Ex->IgnoreParens(); 482 483 // FIXME: add metadata to the CFG so that we can disable 484 // this check when we KNOW that there is no block-level subexpression. 485 // The motivation is that this check requires a hashtable lookup. 486 487 if (S != currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S)) 488 return; 489 490 switch (S->getStmtClass()) { 491 // C++ and ARC stuff we don't support yet. 492 case Expr::ObjCIndirectCopyRestoreExprClass: 493 case Stmt::CXXDependentScopeMemberExprClass: 494 case Stmt::CXXPseudoDestructorExprClass: 495 case Stmt::CXXTryStmtClass: 496 case Stmt::CXXTypeidExprClass: 497 case Stmt::CXXUuidofExprClass: 498 case Stmt::CXXUnresolvedConstructExprClass: 499 case Stmt::DependentScopeDeclRefExprClass: 500 case Stmt::UnaryTypeTraitExprClass: 501 case Stmt::BinaryTypeTraitExprClass: 502 case Stmt::TypeTraitExprClass: 503 case Stmt::ArrayTypeTraitExprClass: 504 case Stmt::ExpressionTraitExprClass: 505 case Stmt::UnresolvedLookupExprClass: 506 case Stmt::UnresolvedMemberExprClass: 507 case Stmt::CXXNoexceptExprClass: 508 case Stmt::PackExpansionExprClass: 509 case Stmt::SubstNonTypeTemplateParmPackExprClass: 510 case Stmt::SEHTryStmtClass: 511 case Stmt::SEHExceptStmtClass: 512 case Stmt::LambdaExprClass: 513 case Stmt::SEHFinallyStmtClass: { 514 const ExplodedNode *node = Bldr.generateNode(S, Pred, Pred->getState(), 515 /* sink */ true); 516 Engine.addAbortedBlock(node, currentBuilderContext->getBlock()); 517 break; 518 } 519 520 // We don't handle default arguments either yet, but we can fake it 521 // for now by just skipping them. 522 case Stmt::SubstNonTypeTemplateParmExprClass: 523 case Stmt::CXXDefaultArgExprClass: 524 break; 525 526 case Stmt::ParenExprClass: 527 llvm_unreachable("ParenExprs already handled."); 528 case Stmt::GenericSelectionExprClass: 529 llvm_unreachable("GenericSelectionExprs already handled."); 530 // Cases that should never be evaluated simply because they shouldn't 531 // appear in the CFG. 532 case Stmt::BreakStmtClass: 533 case Stmt::CaseStmtClass: 534 case Stmt::CompoundStmtClass: 535 case Stmt::ContinueStmtClass: 536 case Stmt::CXXForRangeStmtClass: 537 case Stmt::DefaultStmtClass: 538 case Stmt::DoStmtClass: 539 case Stmt::ForStmtClass: 540 case Stmt::GotoStmtClass: 541 case Stmt::IfStmtClass: 542 case Stmt::IndirectGotoStmtClass: 543 case Stmt::LabelStmtClass: 544 case Stmt::AttributedStmtClass: 545 case Stmt::NoStmtClass: 546 case Stmt::NullStmtClass: 547 case Stmt::SwitchStmtClass: 548 case Stmt::WhileStmtClass: 549 case Expr::MSDependentExistsStmtClass: 550 llvm_unreachable("Stmt should not be in analyzer evaluation loop"); 551 552 case Stmt::GNUNullExprClass: { 553 // GNU __null is a pointer-width integer, not an actual pointer. 554 ProgramStateRef state = Pred->getState(); 555 state = state->BindExpr(S, Pred->getLocationContext(), 556 svalBuilder.makeIntValWithPtrWidth(0, false)); 557 Bldr.generateNode(S, Pred, state); 558 break; 559 } 560 561 case Stmt::ObjCAtSynchronizedStmtClass: 562 Bldr.takeNodes(Pred); 563 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst); 564 Bldr.addNodes(Dst); 565 break; 566 567 // FIXME. 568 case Stmt::ObjCSubscriptRefExprClass: 569 break; 570 571 case Stmt::ObjCPropertyRefExprClass: 572 // Implicitly handled by Environment::getSVal(). 573 break; 574 575 case Stmt::ExprWithCleanupsClass: 576 // Handled due to fully linearised CFG. 577 break; 578 579 // Cases not handled yet; but will handle some day. 580 case Stmt::DesignatedInitExprClass: 581 case Stmt::ExtVectorElementExprClass: 582 case Stmt::ImaginaryLiteralClass: 583 case Stmt::ObjCAtCatchStmtClass: 584 case Stmt::ObjCAtFinallyStmtClass: 585 case Stmt::ObjCAtTryStmtClass: 586 case Stmt::ObjCAutoreleasePoolStmtClass: 587 case Stmt::ObjCEncodeExprClass: 588 case Stmt::ObjCIsaExprClass: 589 case Stmt::ObjCProtocolExprClass: 590 case Stmt::ObjCSelectorExprClass: 591 case Stmt::ParenListExprClass: 592 case Stmt::PredefinedExprClass: 593 case Stmt::ShuffleVectorExprClass: 594 case Stmt::VAArgExprClass: 595 case Stmt::CUDAKernelCallExprClass: 596 case Stmt::OpaqueValueExprClass: 597 case Stmt::AsTypeExprClass: 598 case Stmt::AtomicExprClass: 599 // Fall through. 600 601 // Currently all handling of 'throw' just falls to the CFG. We 602 // can consider doing more if necessary. 603 case Stmt::CXXThrowExprClass: 604 // Fall through. 605 606 // Cases we intentionally don't evaluate, since they don't need 607 // to be explicitly evaluated. 608 case Stmt::AddrLabelExprClass: 609 case Stmt::IntegerLiteralClass: 610 case Stmt::CharacterLiteralClass: 611 case Stmt::ImplicitValueInitExprClass: 612 case Stmt::CXXScalarValueInitExprClass: 613 case Stmt::CXXBoolLiteralExprClass: 614 case Stmt::ObjCBoolLiteralExprClass: 615 case Stmt::FloatingLiteralClass: 616 case Stmt::SizeOfPackExprClass: 617 case Stmt::StringLiteralClass: 618 case Stmt::ObjCStringLiteralClass: 619 case Stmt::CXXBindTemporaryExprClass: 620 case Stmt::CXXNullPtrLiteralExprClass: { 621 Bldr.takeNodes(Pred); 622 ExplodedNodeSet preVisit; 623 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 624 getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this); 625 Bldr.addNodes(Dst); 626 break; 627 } 628 629 case Expr::ObjCArrayLiteralClass: 630 case Expr::ObjCDictionaryLiteralClass: 631 // FIXME: explicitly model with a region and the actual contents 632 // of the container. For now, conjure a symbol. 633 case Expr::ObjCBoxedExprClass: { 634 Bldr.takeNodes(Pred); 635 636 ExplodedNodeSet preVisit; 637 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 638 639 ExplodedNodeSet Tmp; 640 StmtNodeBuilder Bldr2(preVisit, Tmp, *currentBuilderContext); 641 642 const Expr *Ex = cast<Expr>(S); 643 QualType resultType = Ex->getType(); 644 645 for (ExplodedNodeSet::iterator it = preVisit.begin(), et = preVisit.end(); 646 it != et; ++it) { 647 ExplodedNode *N = *it; 648 const LocationContext *LCtx = N->getLocationContext(); 649 SVal result = 650 svalBuilder.getConjuredSymbolVal(0, Ex, LCtx, resultType, 651 currentBuilderContext->getCurrentBlockCount()); 652 ProgramStateRef state = N->getState()->BindExpr(Ex, LCtx, result); 653 Bldr2.generateNode(S, N, state); 654 } 655 656 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); 657 Bldr.addNodes(Dst); 658 break; 659 } 660 661 case Stmt::ArraySubscriptExprClass: 662 Bldr.takeNodes(Pred); 663 VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); 664 Bldr.addNodes(Dst); 665 break; 666 667 case Stmt::AsmStmtClass: 668 Bldr.takeNodes(Pred); 669 VisitAsmStmt(cast<AsmStmt>(S), Pred, Dst); 670 Bldr.addNodes(Dst); 671 break; 672 673 case Stmt::BlockExprClass: 674 Bldr.takeNodes(Pred); 675 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst); 676 Bldr.addNodes(Dst); 677 break; 678 679 case Stmt::BinaryOperatorClass: { 680 const BinaryOperator* B = cast<BinaryOperator>(S); 681 if (B->isLogicalOp()) { 682 Bldr.takeNodes(Pred); 683 VisitLogicalExpr(B, Pred, Dst); 684 Bldr.addNodes(Dst); 685 break; 686 } 687 else if (B->getOpcode() == BO_Comma) { 688 ProgramStateRef state = Pred->getState(); 689 Bldr.generateNode(B, Pred, 690 state->BindExpr(B, Pred->getLocationContext(), 691 state->getSVal(B->getRHS(), 692 Pred->getLocationContext()))); 693 break; 694 } 695 696 Bldr.takeNodes(Pred); 697 698 if (AMgr.shouldEagerlyAssume() && 699 (B->isRelationalOp() || B->isEqualityOp())) { 700 ExplodedNodeSet Tmp; 701 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp); 702 evalEagerlyAssume(Dst, Tmp, cast<Expr>(S)); 703 } 704 else 705 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 706 707 Bldr.addNodes(Dst); 708 break; 709 } 710 711 case Stmt::CallExprClass: 712 case Stmt::CXXOperatorCallExprClass: 713 case Stmt::CXXMemberCallExprClass: 714 case Stmt::UserDefinedLiteralClass: { 715 Bldr.takeNodes(Pred); 716 VisitCallExpr(cast<CallExpr>(S), Pred, Dst); 717 Bldr.addNodes(Dst); 718 break; 719 } 720 721 case Stmt::CXXCatchStmtClass: { 722 Bldr.takeNodes(Pred); 723 VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst); 724 Bldr.addNodes(Dst); 725 break; 726 } 727 728 case Stmt::CXXTemporaryObjectExprClass: 729 case Stmt::CXXConstructExprClass: { 730 const CXXConstructExpr *C = cast<CXXConstructExpr>(S); 731 // For block-level CXXConstructExpr, we don't have a destination region. 732 // Let VisitCXXConstructExpr() create one. 733 Bldr.takeNodes(Pred); 734 VisitCXXConstructExpr(C, 0, Pred, Dst); 735 Bldr.addNodes(Dst); 736 break; 737 } 738 739 case Stmt::CXXNewExprClass: { 740 Bldr.takeNodes(Pred); 741 const CXXNewExpr *NE = cast<CXXNewExpr>(S); 742 VisitCXXNewExpr(NE, Pred, Dst); 743 Bldr.addNodes(Dst); 744 break; 745 } 746 747 case Stmt::CXXDeleteExprClass: { 748 Bldr.takeNodes(Pred); 749 const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S); 750 VisitCXXDeleteExpr(CDE, Pred, Dst); 751 Bldr.addNodes(Dst); 752 break; 753 } 754 // FIXME: ChooseExpr is really a constant. We need to fix 755 // the CFG do not model them as explicit control-flow. 756 757 case Stmt::ChooseExprClass: { // __builtin_choose_expr 758 Bldr.takeNodes(Pred); 759 const ChooseExpr *C = cast<ChooseExpr>(S); 760 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst); 761 Bldr.addNodes(Dst); 762 break; 763 } 764 765 case Stmt::CompoundAssignOperatorClass: 766 Bldr.takeNodes(Pred); 767 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 768 Bldr.addNodes(Dst); 769 break; 770 771 case Stmt::CompoundLiteralExprClass: 772 Bldr.takeNodes(Pred); 773 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst); 774 Bldr.addNodes(Dst); 775 break; 776 777 case Stmt::BinaryConditionalOperatorClass: 778 case Stmt::ConditionalOperatorClass: { // '?' operator 779 Bldr.takeNodes(Pred); 780 const AbstractConditionalOperator *C 781 = cast<AbstractConditionalOperator>(S); 782 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst); 783 Bldr.addNodes(Dst); 784 break; 785 } 786 787 case Stmt::CXXThisExprClass: 788 Bldr.takeNodes(Pred); 789 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst); 790 Bldr.addNodes(Dst); 791 break; 792 793 case Stmt::DeclRefExprClass: { 794 Bldr.takeNodes(Pred); 795 const DeclRefExpr *DE = cast<DeclRefExpr>(S); 796 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst); 797 Bldr.addNodes(Dst); 798 break; 799 } 800 801 case Stmt::DeclStmtClass: 802 Bldr.takeNodes(Pred); 803 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst); 804 Bldr.addNodes(Dst); 805 break; 806 807 case Stmt::ImplicitCastExprClass: 808 case Stmt::CStyleCastExprClass: 809 case Stmt::CXXStaticCastExprClass: 810 case Stmt::CXXDynamicCastExprClass: 811 case Stmt::CXXReinterpretCastExprClass: 812 case Stmt::CXXConstCastExprClass: 813 case Stmt::CXXFunctionalCastExprClass: 814 case Stmt::ObjCBridgedCastExprClass: { 815 Bldr.takeNodes(Pred); 816 const CastExpr *C = cast<CastExpr>(S); 817 // Handle the previsit checks. 818 ExplodedNodeSet dstPrevisit; 819 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this); 820 821 // Handle the expression itself. 822 ExplodedNodeSet dstExpr; 823 for (ExplodedNodeSet::iterator i = dstPrevisit.begin(), 824 e = dstPrevisit.end(); i != e ; ++i) { 825 VisitCast(C, C->getSubExpr(), *i, dstExpr); 826 } 827 828 // Handle the postvisit checks. 829 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this); 830 Bldr.addNodes(Dst); 831 break; 832 } 833 834 case Expr::MaterializeTemporaryExprClass: { 835 Bldr.takeNodes(Pred); 836 const MaterializeTemporaryExpr *Materialize 837 = cast<MaterializeTemporaryExpr>(S); 838 if (Materialize->getType()->isRecordType()) 839 Dst.Add(Pred); 840 else 841 CreateCXXTemporaryObject(Materialize, Pred, Dst); 842 Bldr.addNodes(Dst); 843 break; 844 } 845 846 case Stmt::InitListExprClass: 847 Bldr.takeNodes(Pred); 848 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst); 849 Bldr.addNodes(Dst); 850 break; 851 852 case Stmt::MemberExprClass: 853 Bldr.takeNodes(Pred); 854 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst); 855 Bldr.addNodes(Dst); 856 break; 857 858 case Stmt::ObjCIvarRefExprClass: 859 Bldr.takeNodes(Pred); 860 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst); 861 Bldr.addNodes(Dst); 862 break; 863 864 case Stmt::ObjCForCollectionStmtClass: 865 Bldr.takeNodes(Pred); 866 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst); 867 Bldr.addNodes(Dst); 868 break; 869 870 case Stmt::ObjCMessageExprClass: { 871 Bldr.takeNodes(Pred); 872 // Is this a property access? 873 const ParentMap &PM = Pred->getLocationContext()->getParentMap(); 874 const ObjCMessageExpr *ME = cast<ObjCMessageExpr>(S); 875 bool evaluated = false; 876 877 if (const PseudoObjectExpr *PO = 878 dyn_cast_or_null<PseudoObjectExpr>(PM.getParent(S))) { 879 const Expr *syntactic = PO->getSyntacticForm(); 880 if (const ObjCPropertyRefExpr *PR = 881 dyn_cast<ObjCPropertyRefExpr>(syntactic)) { 882 bool isSetter = ME->getNumArgs() > 0; 883 VisitObjCMessage(ObjCMessage(ME, PR, isSetter), Pred, Dst); 884 evaluated = true; 885 } 886 else if (isa<BinaryOperator>(syntactic)) { 887 VisitObjCMessage(ObjCMessage(ME, 0, true), Pred, Dst); 888 } 889 } 890 891 if (!evaluated) 892 VisitObjCMessage(ME, Pred, Dst); 893 894 Bldr.addNodes(Dst); 895 break; 896 } 897 898 case Stmt::ObjCAtThrowStmtClass: { 899 // FIXME: This is not complete. We basically treat @throw as 900 // an abort. 901 Bldr.generateNode(S, Pred, Pred->getState()); 902 break; 903 } 904 905 case Stmt::ReturnStmtClass: 906 Bldr.takeNodes(Pred); 907 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst); 908 Bldr.addNodes(Dst); 909 break; 910 911 case Stmt::OffsetOfExprClass: 912 Bldr.takeNodes(Pred); 913 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst); 914 Bldr.addNodes(Dst); 915 break; 916 917 case Stmt::UnaryExprOrTypeTraitExprClass: 918 Bldr.takeNodes(Pred); 919 VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 920 Pred, Dst); 921 Bldr.addNodes(Dst); 922 break; 923 924 case Stmt::StmtExprClass: { 925 const StmtExpr *SE = cast<StmtExpr>(S); 926 927 if (SE->getSubStmt()->body_empty()) { 928 // Empty statement expression. 929 assert(SE->getType() == getContext().VoidTy 930 && "Empty statement expression must have void type."); 931 break; 932 } 933 934 if (Expr *LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) { 935 ProgramStateRef state = Pred->getState(); 936 Bldr.generateNode(SE, Pred, 937 state->BindExpr(SE, Pred->getLocationContext(), 938 state->getSVal(LastExpr, 939 Pred->getLocationContext()))); 940 } 941 break; 942 } 943 944 case Stmt::UnaryOperatorClass: { 945 Bldr.takeNodes(Pred); 946 const UnaryOperator *U = cast<UnaryOperator>(S); 947 if (AMgr.shouldEagerlyAssume() && (U->getOpcode() == UO_LNot)) { 948 ExplodedNodeSet Tmp; 949 VisitUnaryOperator(U, Pred, Tmp); 950 evalEagerlyAssume(Dst, Tmp, U); 951 } 952 else 953 VisitUnaryOperator(U, Pred, Dst); 954 Bldr.addNodes(Dst); 955 break; 956 } 957 958 case Stmt::PseudoObjectExprClass: { 959 Bldr.takeNodes(Pred); 960 ProgramStateRef state = Pred->getState(); 961 const PseudoObjectExpr *PE = cast<PseudoObjectExpr>(S); 962 if (const Expr *Result = PE->getResultExpr()) { 963 SVal V = state->getSVal(Result, Pred->getLocationContext()); 964 Bldr.generateNode(S, Pred, 965 state->BindExpr(S, Pred->getLocationContext(), V)); 966 } 967 else 968 Bldr.generateNode(S, Pred, 969 state->BindExpr(S, Pred->getLocationContext(), 970 UnknownVal())); 971 972 Bldr.addNodes(Dst); 973 break; 974 } 975 } 976} 977 978bool ExprEngine::replayWithoutInlining(ExplodedNode *N, 979 const LocationContext *CalleeLC) { 980 const StackFrameContext *CalleeSF = CalleeLC->getCurrentStackFrame(); 981 const StackFrameContext *CallerSF = CalleeSF->getParent()->getCurrentStackFrame(); 982 assert(CalleeSF && CallerSF); 983 ExplodedNode *BeforeProcessingCall = 0; 984 985 // Find the first node before we started processing the call expression. 986 while (N) { 987 ProgramPoint L = N->getLocation(); 988 BeforeProcessingCall = N; 989 N = N->pred_empty() ? NULL : *(N->pred_begin()); 990 991 // Skip the nodes corresponding to the inlined code. 992 if (L.getLocationContext()->getCurrentStackFrame() != CallerSF) 993 continue; 994 // We reached the caller. Find the node right before we started 995 // processing the CallExpr. 996 if (L.isPurgeKind()) 997 continue; 998 if (const StmtPoint *SP = dyn_cast<StmtPoint>(&L)) 999 if (SP->getStmt() == CalleeSF->getCallSite()) 1000 continue; 1001 break; 1002 } 1003 1004 if (!BeforeProcessingCall) 1005 return false; 1006 1007 // TODO: Clean up the unneeded nodes. 1008 1009 // Build an Epsilon node from which we will restart the analyzes. 1010 const Stmt *CE = CalleeSF->getCallSite(); 1011 ProgramPoint NewNodeLoc = 1012 EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE); 1013 // Add the special flag to GDM to signal retrying with no inlining. 1014 // Note, changing the state ensures that we are not going to cache out. 1015 ProgramStateRef NewNodeState = BeforeProcessingCall->getState(); 1016 NewNodeState = NewNodeState->set<ReplayWithoutInlining>((void*)CE); 1017 1018 // Make the new node a successor of BeforeProcessingCall. 1019 bool IsNew = false; 1020 ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew); 1021 // We cached out at this point. Caching out is common due to us backtracking 1022 // from the inlined function, which might spawn several paths. 1023 if (!IsNew) 1024 return true; 1025 1026 NewNode->addPredecessor(BeforeProcessingCall, G); 1027 1028 // Add the new node to the work list. 1029 Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(), 1030 CalleeSF->getIndex()); 1031 NumTimesRetriedWithoutInlining++; 1032 return true; 1033} 1034 1035/// Block entrance. (Update counters). 1036void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, 1037 NodeBuilderWithSinks &nodeBuilder) { 1038 1039 // FIXME: Refactor this into a checker. 1040 ExplodedNode *pred = nodeBuilder.getContext().getPred(); 1041 1042 if (nodeBuilder.getContext().getCurrentBlockCount() >= AMgr.getMaxVisit()) { 1043 static SimpleProgramPointTag tag("ExprEngine : Block count exceeded"); 1044 const ExplodedNode *Sink = 1045 nodeBuilder.generateNode(pred->getState(), pred, &tag, true); 1046 1047 // Check if we stopped at the top level function or not. 1048 // Root node should have the location context of the top most function. 1049 const LocationContext *CalleeLC = pred->getLocation().getLocationContext(); 1050 const LocationContext *CalleeSF = CalleeLC->getCurrentStackFrame(); 1051 const LocationContext *RootLC = 1052 (*G.roots_begin())->getLocation().getLocationContext(); 1053 if (RootLC->getCurrentStackFrame() != CalleeSF) { 1054 Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl()); 1055 1056 // Re-run the call evaluation without inlining it, by storing the 1057 // no-inlining policy in the state and enqueuing the new work item on 1058 // the list. Replay should almost never fail. Use the stats to catch it 1059 // if it does. 1060 if ((!AMgr.NoRetryExhausted && replayWithoutInlining(pred, CalleeLC))) 1061 return; 1062 NumMaxBlockCountReachedInInlined++; 1063 } else 1064 NumMaxBlockCountReached++; 1065 1066 // Make sink nodes as exhausted(for stats) only if retry failed. 1067 Engine.blocksExhausted.push_back(std::make_pair(L, Sink)); 1068 } 1069} 1070 1071//===----------------------------------------------------------------------===// 1072// Branch processing. 1073//===----------------------------------------------------------------------===// 1074 1075ProgramStateRef ExprEngine::MarkBranch(ProgramStateRef state, 1076 const Stmt *Terminator, 1077 const LocationContext *LCtx, 1078 bool branchTaken) { 1079 1080 switch (Terminator->getStmtClass()) { 1081 default: 1082 return state; 1083 1084 case Stmt::BinaryOperatorClass: { // '&&' and '||' 1085 1086 const BinaryOperator* B = cast<BinaryOperator>(Terminator); 1087 BinaryOperator::Opcode Op = B->getOpcode(); 1088 1089 assert (Op == BO_LAnd || Op == BO_LOr); 1090 1091 // For &&, if we take the true branch, then the value of the whole 1092 // expression is that of the RHS expression. 1093 // 1094 // For ||, if we take the false branch, then the value of the whole 1095 // expression is that of the RHS expression. 1096 1097 const Expr *Ex = (Op == BO_LAnd && branchTaken) || 1098 (Op == BO_LOr && !branchTaken) 1099 ? B->getRHS() : B->getLHS(); 1100 1101 return state->BindExpr(B, LCtx, UndefinedVal(Ex)); 1102 } 1103 1104 case Stmt::BinaryConditionalOperatorClass: 1105 case Stmt::ConditionalOperatorClass: { // ?: 1106 const AbstractConditionalOperator* C 1107 = cast<AbstractConditionalOperator>(Terminator); 1108 1109 // For ?, if branchTaken == true then the value is either the LHS or 1110 // the condition itself. (GNU extension). 1111 1112 const Expr *Ex; 1113 1114 if (branchTaken) 1115 Ex = C->getTrueExpr(); 1116 else 1117 Ex = C->getFalseExpr(); 1118 1119 return state->BindExpr(C, LCtx, UndefinedVal(Ex)); 1120 } 1121 1122 case Stmt::ChooseExprClass: { // ?: 1123 1124 const ChooseExpr *C = cast<ChooseExpr>(Terminator); 1125 1126 const Expr *Ex = branchTaken ? C->getLHS() : C->getRHS(); 1127 return state->BindExpr(C, LCtx, UndefinedVal(Ex)); 1128 } 1129 } 1130} 1131 1132/// RecoverCastedSymbol - A helper function for ProcessBranch that is used 1133/// to try to recover some path-sensitivity for casts of symbolic 1134/// integers that promote their values (which are currently not tracked well). 1135/// This function returns the SVal bound to Condition->IgnoreCasts if all the 1136// cast(s) did was sign-extend the original value. 1137static SVal RecoverCastedSymbol(ProgramStateManager& StateMgr, 1138 ProgramStateRef state, 1139 const Stmt *Condition, 1140 const LocationContext *LCtx, 1141 ASTContext &Ctx) { 1142 1143 const Expr *Ex = dyn_cast<Expr>(Condition); 1144 if (!Ex) 1145 return UnknownVal(); 1146 1147 uint64_t bits = 0; 1148 bool bitsInit = false; 1149 1150 while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 1151 QualType T = CE->getType(); 1152 1153 if (!T->isIntegerType()) 1154 return UnknownVal(); 1155 1156 uint64_t newBits = Ctx.getTypeSize(T); 1157 if (!bitsInit || newBits < bits) { 1158 bitsInit = true; 1159 bits = newBits; 1160 } 1161 1162 Ex = CE->getSubExpr(); 1163 } 1164 1165 // We reached a non-cast. Is it a symbolic value? 1166 QualType T = Ex->getType(); 1167 1168 if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits) 1169 return UnknownVal(); 1170 1171 return state->getSVal(Ex, LCtx); 1172} 1173 1174void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, 1175 NodeBuilderContext& BldCtx, 1176 ExplodedNode *Pred, 1177 ExplodedNodeSet &Dst, 1178 const CFGBlock *DstT, 1179 const CFGBlock *DstF) { 1180 currentBuilderContext = &BldCtx; 1181 1182 // Check for NULL conditions; e.g. "for(;;)" 1183 if (!Condition) { 1184 BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF); 1185 NullCondBldr.markInfeasible(false); 1186 NullCondBldr.generateNode(Pred->getState(), true, Pred); 1187 return; 1188 } 1189 1190 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 1191 Condition->getLocStart(), 1192 "Error evaluating branch"); 1193 1194 ExplodedNodeSet CheckersOutSet; 1195 getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet, 1196 Pred, *this); 1197 // We generated only sinks. 1198 if (CheckersOutSet.empty()) 1199 return; 1200 1201 BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF); 1202 for (NodeBuilder::iterator I = CheckersOutSet.begin(), 1203 E = CheckersOutSet.end(); E != I; ++I) { 1204 ExplodedNode *PredI = *I; 1205 1206 if (PredI->isSink()) 1207 continue; 1208 1209 ProgramStateRef PrevState = Pred->getState(); 1210 SVal X = PrevState->getSVal(Condition, Pred->getLocationContext()); 1211 1212 if (X.isUnknownOrUndef()) { 1213 // Give it a chance to recover from unknown. 1214 if (const Expr *Ex = dyn_cast<Expr>(Condition)) { 1215 if (Ex->getType()->isIntegerType()) { 1216 // Try to recover some path-sensitivity. Right now casts of symbolic 1217 // integers that promote their values are currently not tracked well. 1218 // If 'Condition' is such an expression, try and recover the 1219 // underlying value and use that instead. 1220 SVal recovered = RecoverCastedSymbol(getStateManager(), 1221 PrevState, Condition, 1222 Pred->getLocationContext(), 1223 getContext()); 1224 1225 if (!recovered.isUnknown()) { 1226 X = recovered; 1227 } 1228 } 1229 } 1230 } 1231 1232 const LocationContext *LCtx = PredI->getLocationContext(); 1233 1234 // If the condition is still unknown, give up. 1235 if (X.isUnknownOrUndef()) { 1236 builder.generateNode(MarkBranch(PrevState, Term, LCtx, true), 1237 true, PredI); 1238 builder.generateNode(MarkBranch(PrevState, Term, LCtx, false), 1239 false, PredI); 1240 continue; 1241 } 1242 1243 DefinedSVal V = cast<DefinedSVal>(X); 1244 1245 // Process the true branch. 1246 if (builder.isFeasible(true)) { 1247 if (ProgramStateRef state = PrevState->assume(V, true)) 1248 builder.generateNode(MarkBranch(state, Term, LCtx, true), 1249 true, PredI); 1250 else 1251 builder.markInfeasible(true); 1252 } 1253 1254 // Process the false branch. 1255 if (builder.isFeasible(false)) { 1256 if (ProgramStateRef state = PrevState->assume(V, false)) 1257 builder.generateNode(MarkBranch(state, Term, LCtx, false), 1258 false, PredI); 1259 else 1260 builder.markInfeasible(false); 1261 } 1262 } 1263 currentBuilderContext = 0; 1264} 1265 1266/// processIndirectGoto - Called by CoreEngine. Used to generate successor 1267/// nodes by processing the 'effects' of a computed goto jump. 1268void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { 1269 1270 ProgramStateRef state = builder.getState(); 1271 SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext()); 1272 1273 // Three possibilities: 1274 // 1275 // (1) We know the computed label. 1276 // (2) The label is NULL (or some other constant), or Undefined. 1277 // (3) We have no clue about the label. Dispatch to all targets. 1278 // 1279 1280 typedef IndirectGotoNodeBuilder::iterator iterator; 1281 1282 if (isa<loc::GotoLabel>(V)) { 1283 const LabelDecl *L = cast<loc::GotoLabel>(V).getLabel(); 1284 1285 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) { 1286 if (I.getLabel() == L) { 1287 builder.generateNode(I, state); 1288 return; 1289 } 1290 } 1291 1292 llvm_unreachable("No block with label."); 1293 } 1294 1295 if (isa<loc::ConcreteInt>(V) || isa<UndefinedVal>(V)) { 1296 // Dispatch to the first target and mark it as a sink. 1297 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); 1298 // FIXME: add checker visit. 1299 // UndefBranches.insert(N); 1300 return; 1301 } 1302 1303 // This is really a catch-all. We don't support symbolics yet. 1304 // FIXME: Implement dispatch for symbolic pointers. 1305 1306 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) 1307 builder.generateNode(I, state); 1308} 1309 1310/// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path 1311/// nodes when the control reaches the end of a function. 1312void ExprEngine::processEndOfFunction(NodeBuilderContext& BC) { 1313 StateMgr.EndPath(BC.Pred->getState()); 1314 ExplodedNodeSet Dst; 1315 getCheckerManager().runCheckersForEndPath(BC, Dst, *this); 1316 Engine.enqueueEndOfFunction(Dst); 1317} 1318 1319/// ProcessSwitch - Called by CoreEngine. Used to generate successor 1320/// nodes by processing the 'effects' of a switch statement. 1321void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { 1322 typedef SwitchNodeBuilder::iterator iterator; 1323 ProgramStateRef state = builder.getState(); 1324 const Expr *CondE = builder.getCondition(); 1325 SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext()); 1326 1327 if (CondV_untested.isUndef()) { 1328 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true); 1329 // FIXME: add checker 1330 //UndefBranches.insert(N); 1331 1332 return; 1333 } 1334 DefinedOrUnknownSVal CondV = cast<DefinedOrUnknownSVal>(CondV_untested); 1335 1336 ProgramStateRef DefaultSt = state; 1337 1338 iterator I = builder.begin(), EI = builder.end(); 1339 bool defaultIsFeasible = I == EI; 1340 1341 for ( ; I != EI; ++I) { 1342 // Successor may be pruned out during CFG construction. 1343 if (!I.getBlock()) 1344 continue; 1345 1346 const CaseStmt *Case = I.getCase(); 1347 1348 // Evaluate the LHS of the case value. 1349 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext()); 1350 assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType())); 1351 1352 // Get the RHS of the case, if it exists. 1353 llvm::APSInt V2; 1354 if (const Expr *E = Case->getRHS()) 1355 V2 = E->EvaluateKnownConstInt(getContext()); 1356 else 1357 V2 = V1; 1358 1359 // FIXME: Eventually we should replace the logic below with a range 1360 // comparison, rather than concretize the values within the range. 1361 // This should be easy once we have "ranges" for NonLVals. 1362 1363 do { 1364 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1)); 1365 DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state, 1366 CondV, CaseVal); 1367 1368 // Now "assume" that the case matches. 1369 if (ProgramStateRef stateNew = state->assume(Res, true)) { 1370 builder.generateCaseStmtNode(I, stateNew); 1371 1372 // If CondV evaluates to a constant, then we know that this 1373 // is the *only* case that we can take, so stop evaluating the 1374 // others. 1375 if (isa<nonloc::ConcreteInt>(CondV)) 1376 return; 1377 } 1378 1379 // Now "assume" that the case doesn't match. Add this state 1380 // to the default state (if it is feasible). 1381 if (DefaultSt) { 1382 if (ProgramStateRef stateNew = DefaultSt->assume(Res, false)) { 1383 defaultIsFeasible = true; 1384 DefaultSt = stateNew; 1385 } 1386 else { 1387 defaultIsFeasible = false; 1388 DefaultSt = NULL; 1389 } 1390 } 1391 1392 // Concretize the next value in the range. 1393 if (V1 == V2) 1394 break; 1395 1396 ++V1; 1397 assert (V1 <= V2); 1398 1399 } while (true); 1400 } 1401 1402 if (!defaultIsFeasible) 1403 return; 1404 1405 // If we have switch(enum value), the default branch is not 1406 // feasible if all of the enum constants not covered by 'case:' statements 1407 // are not feasible values for the switch condition. 1408 // 1409 // Note that this isn't as accurate as it could be. Even if there isn't 1410 // a case for a particular enum value as long as that enum value isn't 1411 // feasible then it shouldn't be considered for making 'default:' reachable. 1412 const SwitchStmt *SS = builder.getSwitch(); 1413 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts(); 1414 if (CondExpr->getType()->getAs<EnumType>()) { 1415 if (SS->isAllEnumCasesCovered()) 1416 return; 1417 } 1418 1419 builder.generateDefaultCaseNode(DefaultSt); 1420} 1421 1422//===----------------------------------------------------------------------===// 1423// Transfer functions: Loads and stores. 1424//===----------------------------------------------------------------------===// 1425 1426void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, 1427 ExplodedNode *Pred, 1428 ExplodedNodeSet &Dst) { 1429 StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 1430 1431 ProgramStateRef state = Pred->getState(); 1432 const LocationContext *LCtx = Pred->getLocationContext(); 1433 1434 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { 1435 assert(Ex->isGLValue()); 1436 SVal V = state->getLValue(VD, Pred->getLocationContext()); 1437 1438 // For references, the 'lvalue' is the pointer address stored in the 1439 // reference region. 1440 if (VD->getType()->isReferenceType()) { 1441 if (const MemRegion *R = V.getAsRegion()) 1442 V = state->getSVal(R); 1443 else 1444 V = UnknownVal(); 1445 } 1446 1447 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), false, 0, 1448 ProgramPoint::PostLValueKind); 1449 return; 1450 } 1451 if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) { 1452 assert(!Ex->isGLValue()); 1453 SVal V = svalBuilder.makeIntVal(ED->getInitVal()); 1454 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V)); 1455 return; 1456 } 1457 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 1458 SVal V = svalBuilder.getFunctionPointer(FD); 1459 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), false, 0, 1460 ProgramPoint::PostLValueKind); 1461 return; 1462 } 1463 if (isa<FieldDecl>(D)) { 1464 // FIXME: Compute lvalue of fields. 1465 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, UnknownVal()), 1466 false, 0, ProgramPoint::PostLValueKind); 1467 return; 1468 } 1469 1470 assert (false && 1471 "ValueDecl support for this ValueDecl not implemented."); 1472} 1473 1474/// VisitArraySubscriptExpr - Transfer function for array accesses 1475void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A, 1476 ExplodedNode *Pred, 1477 ExplodedNodeSet &Dst){ 1478 1479 const Expr *Base = A->getBase()->IgnoreParens(); 1480 const Expr *Idx = A->getIdx()->IgnoreParens(); 1481 1482 1483 ExplodedNodeSet checkerPreStmt; 1484 getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this); 1485 1486 StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currentBuilderContext); 1487 1488 for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(), 1489 ei = checkerPreStmt.end(); it != ei; ++it) { 1490 const LocationContext *LCtx = (*it)->getLocationContext(); 1491 ProgramStateRef state = (*it)->getState(); 1492 SVal V = state->getLValue(A->getType(), 1493 state->getSVal(Idx, LCtx), 1494 state->getSVal(Base, LCtx)); 1495 assert(A->isGLValue()); 1496 Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 1497 false, 0, ProgramPoint::PostLValueKind); 1498 } 1499} 1500 1501/// VisitMemberExpr - Transfer function for member expressions. 1502void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, 1503 ExplodedNodeSet &TopDst) { 1504 1505 StmtNodeBuilder Bldr(Pred, TopDst, *currentBuilderContext); 1506 ExplodedNodeSet Dst; 1507 Decl *member = M->getMemberDecl(); 1508 if (VarDecl *VD = dyn_cast<VarDecl>(member)) { 1509 assert(M->isGLValue()); 1510 Bldr.takeNodes(Pred); 1511 VisitCommonDeclRefExpr(M, VD, Pred, Dst); 1512 Bldr.addNodes(Dst); 1513 return; 1514 } 1515 1516 FieldDecl *field = dyn_cast<FieldDecl>(member); 1517 if (!field) // FIXME: skipping member expressions for non-fields 1518 return; 1519 1520 Expr *baseExpr = M->getBase()->IgnoreParens(); 1521 ProgramStateRef state = Pred->getState(); 1522 const LocationContext *LCtx = Pred->getLocationContext(); 1523 SVal baseExprVal = state->getSVal(baseExpr, Pred->getLocationContext()); 1524 if (isa<nonloc::LazyCompoundVal>(baseExprVal) || 1525 isa<nonloc::CompoundVal>(baseExprVal) || 1526 // FIXME: This can originate by conjuring a symbol for an unknown 1527 // temporary struct object, see test/Analysis/fields.c: 1528 // (p = getit()).x 1529 isa<nonloc::SymbolVal>(baseExprVal)) { 1530 Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, UnknownVal())); 1531 return; 1532 } 1533 1534 // FIXME: Should we insert some assumption logic in here to determine 1535 // if "Base" is a valid piece of memory? Before we put this assumption 1536 // later when using FieldOffset lvals (which we no longer have). 1537 1538 // For all other cases, compute an lvalue. 1539 SVal L = state->getLValue(field, baseExprVal); 1540 if (M->isGLValue()) 1541 Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), false, 0, 1542 ProgramPoint::PostLValueKind); 1543 else { 1544 Bldr.takeNodes(Pred); 1545 evalLoad(Dst, M, M, Pred, state, L); 1546 Bldr.addNodes(Dst); 1547 } 1548} 1549 1550/// evalBind - Handle the semantics of binding a value to a specific location. 1551/// This method is used by evalStore and (soon) VisitDeclStmt, and others. 1552void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, 1553 ExplodedNode *Pred, 1554 SVal location, SVal Val, bool atDeclInit) { 1555 1556 // Do a previsit of the bind. 1557 ExplodedNodeSet CheckedSet; 1558 getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val, 1559 StoreE, *this, 1560 ProgramPoint::PostStmtKind); 1561 1562 ExplodedNodeSet TmpDst; 1563 StmtNodeBuilder Bldr(CheckedSet, TmpDst, *currentBuilderContext); 1564 1565 const LocationContext *LC = Pred->getLocationContext(); 1566 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 1567 I!=E; ++I) { 1568 ExplodedNode *PredI = *I; 1569 ProgramStateRef state = PredI->getState(); 1570 1571 if (atDeclInit) { 1572 const VarRegion *VR = 1573 cast<VarRegion>(cast<loc::MemRegionVal>(location).getRegion()); 1574 1575 state = state->bindDecl(VR, Val); 1576 } else { 1577 state = state->bindLoc(location, Val); 1578 } 1579 1580 const MemRegion *LocReg = 0; 1581 if (loc::MemRegionVal *LocRegVal = dyn_cast<loc::MemRegionVal>(&location)) 1582 LocReg = LocRegVal->getRegion(); 1583 1584 const ProgramPoint L = PostStore(StoreE, LC, LocReg, 0); 1585 Bldr.generateNode(L, PredI, state, false); 1586 } 1587 1588 Dst.insert(TmpDst); 1589} 1590 1591/// evalStore - Handle the semantics of a store via an assignment. 1592/// @param Dst The node set to store generated state nodes 1593/// @param AssignE The assignment expression if the store happens in an 1594/// assignment. 1595/// @param LocatioinE The location expression that is stored to. 1596/// @param state The current simulation state 1597/// @param location The location to store the value 1598/// @param Val The value to be stored 1599void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, 1600 const Expr *LocationE, 1601 ExplodedNode *Pred, 1602 ProgramStateRef state, SVal location, SVal Val, 1603 const ProgramPointTag *tag) { 1604 // Proceed with the store. We use AssignE as the anchor for the PostStore 1605 // ProgramPoint if it is non-NULL, and LocationE otherwise. 1606 const Expr *StoreE = AssignE ? AssignE : LocationE; 1607 1608 if (isa<loc::ObjCPropRef>(location)) { 1609 assert(false); 1610 } 1611 1612 // Evaluate the location (checks for bad dereferences). 1613 ExplodedNodeSet Tmp; 1614 evalLocation(Tmp, AssignE, LocationE, Pred, state, location, tag, false); 1615 1616 if (Tmp.empty()) 1617 return; 1618 1619 if (location.isUndef()) 1620 return; 1621 1622 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) 1623 evalBind(Dst, StoreE, *NI, location, Val, false); 1624} 1625 1626void ExprEngine::evalLoad(ExplodedNodeSet &Dst, 1627 const Expr *NodeEx, 1628 const Expr *BoundEx, 1629 ExplodedNode *Pred, 1630 ProgramStateRef state, 1631 SVal location, 1632 const ProgramPointTag *tag, 1633 QualType LoadTy) 1634{ 1635 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc."); 1636 assert(!isa<loc::ObjCPropRef>(location)); 1637 1638 // Are we loading from a region? This actually results in two loads; one 1639 // to fetch the address of the referenced value and one to fetch the 1640 // referenced value. 1641 if (const TypedValueRegion *TR = 1642 dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { 1643 1644 QualType ValTy = TR->getValueType(); 1645 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) { 1646 static SimpleProgramPointTag 1647 loadReferenceTag("ExprEngine : Load Reference"); 1648 ExplodedNodeSet Tmp; 1649 evalLoadCommon(Tmp, NodeEx, BoundEx, Pred, state, 1650 location, &loadReferenceTag, 1651 getContext().getPointerType(RT->getPointeeType())); 1652 1653 // Perform the load from the referenced value. 1654 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) { 1655 state = (*I)->getState(); 1656 location = state->getSVal(BoundEx, (*I)->getLocationContext()); 1657 evalLoadCommon(Dst, NodeEx, BoundEx, *I, state, location, tag, LoadTy); 1658 } 1659 return; 1660 } 1661 } 1662 1663 evalLoadCommon(Dst, NodeEx, BoundEx, Pred, state, location, tag, LoadTy); 1664} 1665 1666void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst, 1667 const Expr *NodeEx, 1668 const Expr *BoundEx, 1669 ExplodedNode *Pred, 1670 ProgramStateRef state, 1671 SVal location, 1672 const ProgramPointTag *tag, 1673 QualType LoadTy) { 1674 assert(NodeEx); 1675 assert(BoundEx); 1676 // Evaluate the location (checks for bad dereferences). 1677 ExplodedNodeSet Tmp; 1678 evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, tag, true); 1679 if (Tmp.empty()) 1680 return; 1681 1682 StmtNodeBuilder Bldr(Tmp, Dst, *currentBuilderContext); 1683 if (location.isUndef()) 1684 return; 1685 1686 // Proceed with the load. 1687 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) { 1688 state = (*NI)->getState(); 1689 const LocationContext *LCtx = (*NI)->getLocationContext(); 1690 1691 if (location.isUnknown()) { 1692 // This is important. We must nuke the old binding. 1693 Bldr.generateNode(NodeEx, *NI, 1694 state->BindExpr(BoundEx, LCtx, UnknownVal()), 1695 false, tag, 1696 ProgramPoint::PostLoadKind); 1697 } 1698 else { 1699 if (LoadTy.isNull()) 1700 LoadTy = BoundEx->getType(); 1701 SVal V = state->getSVal(cast<Loc>(location), LoadTy); 1702 Bldr.generateNode(NodeEx, *NI, 1703 state->bindExprAndLocation(BoundEx, LCtx, location, V), 1704 false, tag, ProgramPoint::PostLoadKind); 1705 } 1706 } 1707} 1708 1709void ExprEngine::evalLocation(ExplodedNodeSet &Dst, 1710 const Stmt *NodeEx, 1711 const Stmt *BoundEx, 1712 ExplodedNode *Pred, 1713 ProgramStateRef state, 1714 SVal location, 1715 const ProgramPointTag *tag, 1716 bool isLoad) { 1717 StmtNodeBuilder BldrTop(Pred, Dst, *currentBuilderContext); 1718 // Early checks for performance reason. 1719 if (location.isUnknown()) { 1720 return; 1721 } 1722 1723 ExplodedNodeSet Src; 1724 BldrTop.takeNodes(Pred); 1725 StmtNodeBuilder Bldr(Pred, Src, *currentBuilderContext); 1726 if (Pred->getState() != state) { 1727 // Associate this new state with an ExplodedNode. 1728 // FIXME: If I pass null tag, the graph is incorrect, e.g for 1729 // int *p; 1730 // p = 0; 1731 // *p = 0xDEADBEEF; 1732 // "p = 0" is not noted as "Null pointer value stored to 'p'" but 1733 // instead "int *p" is noted as 1734 // "Variable 'p' initialized to a null pointer value" 1735 1736 // FIXME: why is 'tag' not used instead of etag? 1737 static SimpleProgramPointTag etag("ExprEngine: Location"); 1738 Bldr.generateNode(NodeEx, Pred, state, false, &etag); 1739 } 1740 ExplodedNodeSet Tmp; 1741 getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad, 1742 NodeEx, BoundEx, *this); 1743 BldrTop.addNodes(Tmp); 1744} 1745 1746std::pair<const ProgramPointTag *, const ProgramPointTag*> 1747ExprEngine::getEagerlyAssumeTags() { 1748 static SimpleProgramPointTag 1749 EagerlyAssumeTrue("ExprEngine : Eagerly Assume True"), 1750 EagerlyAssumeFalse("ExprEngine : Eagerly Assume False"); 1751 return std::make_pair(&EagerlyAssumeTrue, &EagerlyAssumeFalse); 1752} 1753 1754void ExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src, 1755 const Expr *Ex) { 1756 StmtNodeBuilder Bldr(Src, Dst, *currentBuilderContext); 1757 1758 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) { 1759 ExplodedNode *Pred = *I; 1760 // Test if the previous node was as the same expression. This can happen 1761 // when the expression fails to evaluate to anything meaningful and 1762 // (as an optimization) we don't generate a node. 1763 ProgramPoint P = Pred->getLocation(); 1764 if (!isa<PostStmt>(P) || cast<PostStmt>(P).getStmt() != Ex) { 1765 continue; 1766 } 1767 1768 ProgramStateRef state = Pred->getState(); 1769 SVal V = state->getSVal(Ex, Pred->getLocationContext()); 1770 nonloc::SymbolVal *SEV = dyn_cast<nonloc::SymbolVal>(&V); 1771 if (SEV && SEV->isExpression()) { 1772 const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags = 1773 getEagerlyAssumeTags(); 1774 1775 // First assume that the condition is true. 1776 if (ProgramStateRef StateTrue = state->assume(*SEV, true)) { 1777 SVal Val = svalBuilder.makeIntVal(1U, Ex->getType()); 1778 StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val); 1779 Bldr.generateNode(Ex, Pred, StateTrue, false, tags.first); 1780 } 1781 1782 // Next, assume that the condition is false. 1783 if (ProgramStateRef StateFalse = state->assume(*SEV, false)) { 1784 SVal Val = svalBuilder.makeIntVal(0U, Ex->getType()); 1785 StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val); 1786 Bldr.generateNode(Ex, Pred, StateFalse, false, tags.second); 1787 } 1788 } 1789 } 1790} 1791 1792void ExprEngine::VisitAsmStmt(const AsmStmt *A, ExplodedNode *Pred, 1793 ExplodedNodeSet &Dst) { 1794 StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 1795 // We have processed both the inputs and the outputs. All of the outputs 1796 // should evaluate to Locs. Nuke all of their values. 1797 1798 // FIXME: Some day in the future it would be nice to allow a "plug-in" 1799 // which interprets the inline asm and stores proper results in the 1800 // outputs. 1801 1802 ProgramStateRef state = Pred->getState(); 1803 1804 for (AsmStmt::const_outputs_iterator OI = A->begin_outputs(), 1805 OE = A->end_outputs(); OI != OE; ++OI) { 1806 SVal X = state->getSVal(*OI, Pred->getLocationContext()); 1807 assert (!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef. 1808 1809 if (isa<Loc>(X)) 1810 state = state->bindLoc(cast<Loc>(X), UnknownVal()); 1811 } 1812 1813 Bldr.generateNode(A, Pred, state); 1814} 1815 1816//===----------------------------------------------------------------------===// 1817// Visualization. 1818//===----------------------------------------------------------------------===// 1819 1820#ifndef NDEBUG 1821static ExprEngine* GraphPrintCheckerState; 1822static SourceManager* GraphPrintSourceManager; 1823 1824namespace llvm { 1825template<> 1826struct DOTGraphTraits<ExplodedNode*> : 1827 public DefaultDOTGraphTraits { 1828 1829 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 1830 1831 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not 1832 // work. 1833 static std::string getNodeAttributes(const ExplodedNode *N, void*) { 1834 1835#if 0 1836 // FIXME: Replace with a general scheme to tell if the node is 1837 // an error node. 1838 if (GraphPrintCheckerState->isImplicitNullDeref(N) || 1839 GraphPrintCheckerState->isExplicitNullDeref(N) || 1840 GraphPrintCheckerState->isUndefDeref(N) || 1841 GraphPrintCheckerState->isUndefStore(N) || 1842 GraphPrintCheckerState->isUndefControlFlow(N) || 1843 GraphPrintCheckerState->isUndefResult(N) || 1844 GraphPrintCheckerState->isBadCall(N) || 1845 GraphPrintCheckerState->isUndefArg(N)) 1846 return "color=\"red\",style=\"filled\""; 1847 1848 if (GraphPrintCheckerState->isNoReturnCall(N)) 1849 return "color=\"blue\",style=\"filled\""; 1850#endif 1851 return ""; 1852 } 1853 1854 static std::string getNodeLabel(const ExplodedNode *N, void*){ 1855 1856 std::string sbuf; 1857 llvm::raw_string_ostream Out(sbuf); 1858 1859 // Program Location. 1860 ProgramPoint Loc = N->getLocation(); 1861 1862 switch (Loc.getKind()) { 1863 case ProgramPoint::BlockEntranceKind: { 1864 Out << "Block Entrance: B" 1865 << cast<BlockEntrance>(Loc).getBlock()->getBlockID(); 1866 if (const NamedDecl *ND = 1867 dyn_cast<NamedDecl>(Loc.getLocationContext()->getDecl())) { 1868 Out << " ("; 1869 ND->printName(Out); 1870 Out << ")"; 1871 } 1872 break; 1873 } 1874 1875 case ProgramPoint::BlockExitKind: 1876 assert (false); 1877 break; 1878 1879 case ProgramPoint::CallEnterKind: 1880 Out << "CallEnter"; 1881 break; 1882 1883 case ProgramPoint::CallExitBeginKind: 1884 Out << "CallExitBegin"; 1885 break; 1886 1887 case ProgramPoint::CallExitEndKind: 1888 Out << "CallExitEnd"; 1889 break; 1890 1891 case ProgramPoint::PostStmtPurgeDeadSymbolsKind: 1892 Out << "PostStmtPurgeDeadSymbols"; 1893 break; 1894 1895 case ProgramPoint::PreStmtPurgeDeadSymbolsKind: 1896 Out << "PreStmtPurgeDeadSymbols"; 1897 break; 1898 1899 case ProgramPoint::EpsilonKind: 1900 Out << "Epsilon Point"; 1901 break; 1902 1903 default: { 1904 if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) { 1905 const Stmt *S = L->getStmt(); 1906 SourceLocation SLoc = S->getLocStart(); 1907 1908 Out << S->getStmtClassName() << ' ' << (void*) S << ' '; 1909 LangOptions LO; // FIXME. 1910 S->printPretty(Out, 0, PrintingPolicy(LO)); 1911 1912 if (SLoc.isFileID()) { 1913 Out << "\\lline=" 1914 << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 1915 << " col=" 1916 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc) 1917 << "\\l"; 1918 } 1919 1920 if (isa<PreStmt>(Loc)) 1921 Out << "\\lPreStmt\\l;"; 1922 else if (isa<PostLoad>(Loc)) 1923 Out << "\\lPostLoad\\l;"; 1924 else if (isa<PostStore>(Loc)) 1925 Out << "\\lPostStore\\l"; 1926 else if (isa<PostLValue>(Loc)) 1927 Out << "\\lPostLValue\\l"; 1928 1929#if 0 1930 // FIXME: Replace with a general scheme to determine 1931 // the name of the check. 1932 if (GraphPrintCheckerState->isImplicitNullDeref(N)) 1933 Out << "\\|Implicit-Null Dereference.\\l"; 1934 else if (GraphPrintCheckerState->isExplicitNullDeref(N)) 1935 Out << "\\|Explicit-Null Dereference.\\l"; 1936 else if (GraphPrintCheckerState->isUndefDeref(N)) 1937 Out << "\\|Dereference of undefialied value.\\l"; 1938 else if (GraphPrintCheckerState->isUndefStore(N)) 1939 Out << "\\|Store to Undefined Loc."; 1940 else if (GraphPrintCheckerState->isUndefResult(N)) 1941 Out << "\\|Result of operation is undefined."; 1942 else if (GraphPrintCheckerState->isNoReturnCall(N)) 1943 Out << "\\|Call to function marked \"noreturn\"."; 1944 else if (GraphPrintCheckerState->isBadCall(N)) 1945 Out << "\\|Call to NULL/Undefined."; 1946 else if (GraphPrintCheckerState->isUndefArg(N)) 1947 Out << "\\|Argument in call is undefined"; 1948#endif 1949 1950 break; 1951 } 1952 1953 const BlockEdge &E = cast<BlockEdge>(Loc); 1954 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B" 1955 << E.getDst()->getBlockID() << ')'; 1956 1957 if (const Stmt *T = E.getSrc()->getTerminator()) { 1958 1959 SourceLocation SLoc = T->getLocStart(); 1960 1961 Out << "\\|Terminator: "; 1962 LangOptions LO; // FIXME. 1963 E.getSrc()->printTerminator(Out, LO); 1964 1965 if (SLoc.isFileID()) { 1966 Out << "\\lline=" 1967 << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 1968 << " col=" 1969 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc); 1970 } 1971 1972 if (isa<SwitchStmt>(T)) { 1973 const Stmt *Label = E.getDst()->getLabel(); 1974 1975 if (Label) { 1976 if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) { 1977 Out << "\\lcase "; 1978 LangOptions LO; // FIXME. 1979 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO)); 1980 1981 if (const Stmt *RHS = C->getRHS()) { 1982 Out << " .. "; 1983 RHS->printPretty(Out, 0, PrintingPolicy(LO)); 1984 } 1985 1986 Out << ":"; 1987 } 1988 else { 1989 assert (isa<DefaultStmt>(Label)); 1990 Out << "\\ldefault:"; 1991 } 1992 } 1993 else 1994 Out << "\\l(implicit) default:"; 1995 } 1996 else if (isa<IndirectGotoStmt>(T)) { 1997 // FIXME 1998 } 1999 else { 2000 Out << "\\lCondition: "; 2001 if (*E.getSrc()->succ_begin() == E.getDst()) 2002 Out << "true"; 2003 else 2004 Out << "false"; 2005 } 2006 2007 Out << "\\l"; 2008 } 2009 2010#if 0 2011 // FIXME: Replace with a general scheme to determine 2012 // the name of the check. 2013 if (GraphPrintCheckerState->isUndefControlFlow(N)) { 2014 Out << "\\|Control-flow based on\\lUndefined value.\\l"; 2015 } 2016#endif 2017 } 2018 } 2019 2020 ProgramStateRef state = N->getState(); 2021 Out << "\\|StateID: " << (void*) state.getPtr() 2022 << " NodeID: " << (void*) N << "\\|"; 2023 state->printDOT(Out); 2024 2025 Out << "\\l"; 2026 2027 if (const ProgramPointTag *tag = Loc.getTag()) { 2028 Out << "\\|Tag: " << tag->getTagDescription(); 2029 Out << "\\l"; 2030 } 2031 return Out.str(); 2032 } 2033}; 2034} // end llvm namespace 2035#endif 2036 2037#ifndef NDEBUG 2038template <typename ITERATOR> 2039ExplodedNode *GetGraphNode(ITERATOR I) { return *I; } 2040 2041template <> ExplodedNode* 2042GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator> 2043 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) { 2044 return I->first; 2045} 2046#endif 2047 2048void ExprEngine::ViewGraph(bool trim) { 2049#ifndef NDEBUG 2050 if (trim) { 2051 std::vector<ExplodedNode*> Src; 2052 2053 // Flush any outstanding reports to make sure we cover all the nodes. 2054 // This does not cause them to get displayed. 2055 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I) 2056 const_cast<BugType*>(*I)->FlushReports(BR); 2057 2058 // Iterate through the reports and get their nodes. 2059 for (BugReporter::EQClasses_iterator 2060 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) { 2061 ExplodedNode *N = const_cast<ExplodedNode*>(EI->begin()->getErrorNode()); 2062 if (N) Src.push_back(N); 2063 } 2064 2065 ViewGraph(&Src[0], &Src[0]+Src.size()); 2066 } 2067 else { 2068 GraphPrintCheckerState = this; 2069 GraphPrintSourceManager = &getContext().getSourceManager(); 2070 2071 llvm::ViewGraph(*G.roots_begin(), "ExprEngine"); 2072 2073 GraphPrintCheckerState = NULL; 2074 GraphPrintSourceManager = NULL; 2075 } 2076#endif 2077} 2078 2079void ExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) { 2080#ifndef NDEBUG 2081 GraphPrintCheckerState = this; 2082 GraphPrintSourceManager = &getContext().getSourceManager(); 2083 2084 std::auto_ptr<ExplodedGraph> TrimmedG(G.Trim(Beg, End).first); 2085 2086 if (!TrimmedG.get()) 2087 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; 2088 else 2089 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine"); 2090 2091 GraphPrintCheckerState = NULL; 2092 GraphPrintSourceManager = NULL; 2093#endif 2094} 2095