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