ProgramState.cpp revision e0d24eb1060a213ec9820dc02c45f26b2d5b348b
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- C++ -*--= 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file implements ProgramState and ProgramStateManager. 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/Analysis/CFG.h" 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 16868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h" 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/raw_ostream.h" 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 22868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)using namespace clang; 2390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)using namespace ento; 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Give the vtable for ConstraintManager somewhere to live. 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// FIXME: Move this elsewhere. 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ConstraintManager::~ConstraintManager() {} 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace clang { namespace ento { 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// Increments the number of times this state is referenced. 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ProgramStateRetain(const ProgramState *state) { 333551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) ++const_cast<ProgramState*>(state)->refCount; 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// Decrement the number of times this state is referenced. 3758e6fbe4ee35d65e14b626c557d37565bf8ad179Ben Murdochvoid ProgramStateRelease(const ProgramState *state) { 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(state->refCount > 0); 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ProgramState *s = const_cast<ProgramState*>(state); 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (--s->refCount == 0) { 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ProgramStateManager &Mgr = s->getStateManager(); 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Mgr.StateSet.RemoveNode(s); 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->~ProgramState(); 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Mgr.freeStates.push_back(s); 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}} 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreRef st, GenericDataMap gdm) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : stateMgr(mgr), 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Env(env), 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) store(st.getStore()), 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GDM(gdm), 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) refCount(0) { 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) stateMgr->getStoreManager().incrementReferenceCount(store); 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ProgramState::ProgramState(const ProgramState &RHS) 60868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) : llvm::FoldingSetNode(), 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stateMgr(RHS.stateMgr), 627d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) Env(RHS.Env), 637d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) store(RHS.store), 647d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) GDM(RHS.GDM), 657d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) refCount(0) { 667d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) stateMgr->getStoreManager().incrementReferenceCount(store); 677d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)} 687d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 697d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)ProgramState::~ProgramState() { 707d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) if (store) 717d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) stateMgr->getStoreManager().decrementReferenceCount(store); 727d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)} 737d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 747d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)ProgramStateManager::ProgramStateManager(ASTContext &Ctx, 757d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) StoreManagerCreator CreateSMgr, 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ConstraintManagerCreator CreateCMgr, 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) llvm::BumpPtrAllocator &alloc, 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubEngine &SubEng) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : Eng(&SubEng), EnvMgr(alloc), GDMFactory(alloc), 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)), 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) { 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreMgr.reset((*CreateSMgr)(*this)); 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ConstraintMgr.reset((*CreateCMgr)(*this, SubEng)); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateManager::~ProgramStateManager() { 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); 89eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch I!=E; ++I) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I->second.second(I->second.first); 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateManager::removeDeadBindings(ProgramStateRef state, 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StackFrameContext *LCtx, 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SymbolReaper& SymReaper) { 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This code essentially performs a "mark-and-sweep" of the VariableBindings. 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The roots are any Block-level exprs and Decls that our liveness algorithm 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // tells us are live. We then see what Decls they may reference, and keep 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // those around. This code more than likely can be made faster, and the 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // frequency of which this method is called should be experimented with 103eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch // for optimum performance. 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ProgramState NewState = *state; 105eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Clean up the store. 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx, 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SymReaper); 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NewState.setStore(newStore); 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SymReaper.setReapedStore(newStore); 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getPersistentState(NewState); 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef ProgramStateManager::MarshalState(ProgramStateRef state, 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StackFrameContext *InitLoc) { 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // make up an empty state for now. 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ProgramState State(this, 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EnvMgr.getInitialEnvironment(), 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreMgr->getInitialStore(InitLoc), 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GDMFactory.getEmptyMap()); 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getPersistentState(State); 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef ProgramState::bindCompoundLiteral(const CompoundLiteralExpr *CL, 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const LocationContext *LC, 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SVal V) const { 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StoreRef &newStore = 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) getStateManager().StoreMgr->BindCompoundLiteral(getStore(), CL, LC, V); 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return makeWithStore(newStore); 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef ProgramState::bindDecl(const VarRegion* VR, SVal IVal) const { 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StoreRef &newStore = 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) getStateManager().StoreMgr->BindDecl(getStore(), VR, IVal); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return makeWithStore(newStore); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef ProgramState::bindDeclWithNoInit(const VarRegion* VR) const { 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StoreRef &newStore = 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) getStateManager().StoreMgr->BindDeclWithNoInit(getStore(), VR); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return makeWithStore(newStore); 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef ProgramState::bindLoc(Loc LV, SVal V) const { 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateManager &Mgr = getStateManager(); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(), 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LV, V)); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const MemRegion *MR = LV.getAsRegion(); 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MR && Mgr.getOwningEngine()) 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Mgr.getOwningEngine()->processRegionChange(newState, MR); 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return newState; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 158eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef ProgramState::bindDefault(SVal loc, SVal V) const { 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateManager &Mgr = getStateManager(); 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const MemRegion *R = cast<loc::MemRegionVal>(loc).getRegion(); 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StoreRef &newStore = Mgr.StoreMgr->BindDefault(getStore(), R, V); 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateRef new_state = makeWithStore(newStore); 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Mgr.getOwningEngine() ? 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Mgr.getOwningEngine()->processRegionChange(new_state, R) : 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_state; 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramState::invalidateRegions(ArrayRef<const MemRegion *> Regions, 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Expr *E, unsigned Count, 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const LocationContext *LCtx, 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreManager::InvalidatedSymbols *IS, 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const CallEvent *Call) const { 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!IS) { 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreManager::InvalidatedSymbols invalidated; 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return invalidateRegionsImpl(Regions, E, Count, LCtx, 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) invalidated, Call); 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return invalidateRegionsImpl(Regions, E, Count, LCtx, *IS, Call); 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramState::invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions, 185868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) const Expr *E, unsigned Count, 186868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) const LocationContext *LCtx, 187868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) StoreManager::InvalidatedSymbols &IS, 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const CallEvent *Call) const { 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateManager &Mgr = getStateManager(); 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubEngine* Eng = Mgr.getOwningEngine(); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Eng && Eng->wantsRegionChangeUpdate(this)) { 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreManager::InvalidatedRegions Invalidated; 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StoreRef &newStore 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) = Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, LCtx, IS, 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Call, &Invalidated); 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateRef newState = makeWithStore(newStore); 1982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return Eng->processRegionChanges(newState, &IS, Regions, Invalidated, Call); 1992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const StoreRef &newStore = 2022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, LCtx, IS, 203868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Call, NULL); 204868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return makeWithStore(newStore); 205868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 206868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 207868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)ProgramStateRef ProgramState::unbindLoc(Loc LV) const { 208868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) assert(!isa<loc::MemRegionVal>(LV) && "Use invalidateRegion instead."); 209868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 210868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Store OldStore = getStore(); 211868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) const StoreRef &newStore = getStateManager().StoreMgr->Remove(OldStore, LV); 212868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 213868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (newStore.getStore() == OldStore) 214868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return this; 215868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 216868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return makeWithStore(newStore); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ProgramStateRef 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramState::enterStackFrame(const CallEvent &Call, 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StackFrameContext *CalleeCtx) const { 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StoreRef &NewStore = 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx); 2242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return makeWithStore(NewStore); 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const { 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We only want to do fetches from regions that we can actually bind 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // values. For example, SymbolicRegions of type 'id<...>' cannot 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // have direct bindings (but their can be bindings on their subregions). 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!R->isBoundable()) 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return UnknownVal(); 2332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 2352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) QualType T = TR->getValueType(); 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Loc::isLocType(T) || T->isIntegerType()) 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getSVal(R); 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return UnknownVal(); 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SVal ProgramState::getSVal(Loc location, QualType T) const { 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SVal V = getRawSVal(cast<Loc>(location), T); 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If 'V' is a symbolic value that is *perfectly* constrained to 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // be a constant value, use that value instead to lessen the burden 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // on later analysis stages (so we have less symbolic values to reason 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // about). 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!T.isNull()) { 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (SymbolRef sym = V.getAsSymbol()) { 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (const llvm::APSInt *Int = getSymVal(sym)) { 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // FIXME: Because we don't correctly model (yet) sign-extension 2542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // and truncation of symbolic values, we need to convert 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the integer value to the correct signedness and bitwidth. 2562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This shows up in the following: 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // char foo(); 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // unsigned x = foo(); 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if (x == 54) 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ... 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The symbolic value stored to 'x' is actually the conjured 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // symbol for the call to foo(); the type of that symbol is 'char', 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // not unsigned. 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int); 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (isa<Loc>(V)) 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return loc::ConcreteInt(NewV); 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return nonloc::ConcreteInt(NewV); 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return V; 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef ProgramState::BindExpr(const Stmt *S, 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const LocationContext *LCtx, 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SVal V, bool Invalidate) const{ 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Environment NewEnv = 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V, 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Invalidate); 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (NewEnv == Env) 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return this; 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramState NewSt = *this; 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NewSt.Env = NewEnv; 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getStateManager().getPersistentState(NewSt); 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramState::bindExprAndLocation(const Stmt *S, const LocationContext *LCtx, 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SVal location, 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SVal V) const { 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Environment NewEnv = 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) getStateManager().EnvMgr.bindExprAndLocation(Env, 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EnvironmentEntry(S, LCtx), 3012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) location, V); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (NewEnv == Env) 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return this; 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 306eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch ProgramState NewSt = *this; 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NewSt.Env = NewEnv; 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getStateManager().getPersistentState(NewSt); 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DefinedOrUnknownSVal UpperBound, 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Assumption, 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QualType indexTy) const { 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Idx.isUnknown() || UpperBound.isUnknown()) 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return this; 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Build an expression for 0 <= Idx < UpperBound. 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed. 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // FIXME: This should probably be part of SValBuilder. 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateManager &SM = getStateManager(); 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SValBuilder &svalBuilder = SM.getSValBuilder(); 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASTContext &Ctx = svalBuilder.getContext(); 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get the offset: the minimum value of the array index type. 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // FIXME: This should be using ValueManager::ArrayindexTy...somehow. 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (indexTy.isNull()) 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) indexTy = Ctx.IntTy; 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) nonloc::ConcreteInt Min(BVF.getMinValue(indexTy)); 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Adjust the index. 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add, 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cast<NonLoc>(Idx), Min, indexTy); 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (newIdx.isUnknownOrUndef()) 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return this; 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Adjust the upper bound. 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SVal newBound = 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) svalBuilder.evalBinOpNN(this, BO_Add, cast<NonLoc>(UpperBound), 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Min, indexTy); 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (newBound.isUnknownOrUndef()) 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return this; 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 346868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // Build the actual comparison. 3472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, 3482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cast<NonLoc>(newIdx), cast<NonLoc>(newBound), 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Ctx.IntTy); 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (inBound.isUnknownOrUndef()) 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return this; 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Finally, let the constraint manager take care of it. 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ConstraintManager &CM = SM.getConstraintManager(); 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CM.assume(this, cast<DefinedSVal>(inBound), Assumption); 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) { 3592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ProgramState State(this, 3602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EnvMgr.getInitialEnvironment(), 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StoreMgr->getInitialStore(InitLoc), 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GDMFactory.getEmptyMap()); 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getPersistentState(State); 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef ProgramStateManager::getPersistentStateWithGDM( 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateRef FromState, 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateRef GDMState) { 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramState NewState(*FromState); 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NewState.GDM = GDMState->GDM; 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getPersistentState(NewState); 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 374424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) { 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) llvm::FoldingSetNodeID ID; 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) State.Profile(ID); 3797d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void *InsertPos; 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos)) 38258e6fbe4ee35d65e14b626c557d37565bf8ad179Ben Murdoch return I; 38358e6fbe4ee35d65e14b626c557d37565bf8ad179Ben Murdoch 38458e6fbe4ee35d65e14b626c557d37565bf8ad179Ben Murdoch ProgramState *newState = 0; 38558e6fbe4ee35d65e14b626c557d37565bf8ad179Ben Murdoch if (!freeStates.empty()) { 386424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) newState = freeStates.back(); 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) freeStates.pop_back(); 388424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 389424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) else { 390424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) newState = (ProgramState*) Alloc.Allocate<ProgramState>(); 391424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new (newState) ProgramState(State); 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StateSet.InsertNode(newState, InsertPos); 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return newState; 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 39658e6fbe4ee35d65e14b626c557d37565bf8ad179Ben Murdoch 397424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)ProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const { 398868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) ProgramState NewSt(*this); 3992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) NewSt.setStore(store); 4002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return getStateManager().getPersistentState(NewSt); 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 403424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)void ProgramState::setStore(const StoreRef &newStore) { 404424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) Store newStoreStore = newStore.getStore(); 405424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) if (newStoreStore) 406424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) stateMgr->getStoreManager().incrementReferenceCount(newStoreStore); 407424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) if (store) 408424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) stateMgr->getStoreManager().decrementReferenceCount(store); 409424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) store = newStoreStore; 410424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} 411424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 412424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)//===----------------------------------------------------------------------===// 413424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)// State pretty-printing. 414424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)//===----------------------------------------------------------------------===// 415424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 416424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)void ProgramState::print(raw_ostream &Out, 417424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const char *NL, const char *Sep) const { 418424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // Print the store. 419424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) ProgramStateManager &Mgr = getStateManager(); 420424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) Mgr.getStoreManager().print(getStore(), Out, NL, Sep); 421424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 422424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // Print out the environment. 423424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) Env.print(Out, NL, Sep); 424424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 425424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // Print out the constraints. 426424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) Mgr.getConstraintManager().print(this, Out, NL, Sep); 427424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 428424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // Print checker-specific data. 429424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) Mgr.getOwningEngine()->printState(Out, this, NL, Sep); 430424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} 431424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 432424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)void ProgramState::printDOT(raw_ostream &Out) const { 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) print(Out, "\\l", "\\|"); 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void ProgramState::dump() const { 4372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) print(llvm::errs()); 4382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void ProgramState::printTaint(raw_ostream &Out, 4412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const char *NL, const char *Sep) const { 442424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) TaintMapImpl TM = get<TaintMap>(); 443868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 4442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!TM.isEmpty()) 4452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Out <<"Tainted Symbols:" << NL; 4462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (TaintMapImpl::iterator I = TM.begin(), E = TM.end(); I != E; ++I) { 4482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Out << I->first << " : " << I->second << NL; 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void ProgramState::dumpTaint() const { 4532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) printTaint(llvm::errs()); 4542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 455868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 4562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 4572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Generic Data Map. 4582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void *const* ProgramState::FindGDM(void *K) const { 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return GDM.lookup(K); 4622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void* 4652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ProgramStateManager::FindGDMContext(void *K, 4662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void *(*CreateContext)(llvm::BumpPtrAllocator&), 4672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void (*DeleteContext)(void*)) { 4682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; 4702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!p.first) { 4712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) p.first = CreateContext(Alloc); 4722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) p.second = DeleteContext; 4732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return p.first; 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 477424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 47890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)ProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){ 47990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) ProgramState::GenericDataMap M1 = St->getGDM(); 48090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data); 48190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 482868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (M1 == M2) 48390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return St; 48490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 48590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) ProgramState NewSt = *St; 486424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) NewSt.GDM = M2; 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getPersistentState(NewSt); 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 490ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) { 491 ProgramState::GenericDataMap OldM = state->getGDM(); 492 ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key); 493 494 if (NewM == OldM) 495 return state; 496 497 ProgramState NewState = *state; 498 NewState.GDM = NewM; 499 return getPersistentState(NewState); 500} 501 502bool ScanReachableSymbols::scan(nonloc::CompoundVal val) { 503 for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) 504 if (!scan(*I)) 505 return false; 506 507 return true; 508} 509 510bool ScanReachableSymbols::scan(const SymExpr *sym) { 511 unsigned &isVisited = visited[sym]; 512 if (isVisited) 513 return true; 514 isVisited = 1; 515 516 if (!visitor.VisitSymbol(sym)) 517 return false; 518 519 // TODO: should be rewritten using SymExpr::symbol_iterator. 520 switch (sym->getKind()) { 521 case SymExpr::RegionValueKind: 522 case SymExpr::ConjuredKind: 523 case SymExpr::DerivedKind: 524 case SymExpr::ExtentKind: 525 case SymExpr::MetadataKind: 526 break; 527 case SymExpr::CastSymbolKind: 528 return scan(cast<SymbolCast>(sym)->getOperand()); 529 case SymExpr::SymIntKind: 530 return scan(cast<SymIntExpr>(sym)->getLHS()); 531 case SymExpr::IntSymKind: 532 return scan(cast<IntSymExpr>(sym)->getRHS()); 533 case SymExpr::SymSymKind: { 534 const SymSymExpr *x = cast<SymSymExpr>(sym); 535 return scan(x->getLHS()) && scan(x->getRHS()); 536 } 537 } 538 return true; 539} 540 541bool ScanReachableSymbols::scan(SVal val) { 542 if (loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(&val)) 543 return scan(X->getRegion()); 544 545 if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&val)) 546 return scan(X->getLoc()); 547 548 if (SymbolRef Sym = val.getAsSymbol()) 549 return scan(Sym); 550 551 if (const SymExpr *Sym = val.getAsSymbolicExpression()) 552 return scan(Sym); 553 554 if (nonloc::CompoundVal *X = dyn_cast<nonloc::CompoundVal>(&val)) 555 return scan(*X); 556 557 return true; 558} 559 560bool ScanReachableSymbols::scan(const MemRegion *R) { 561 if (isa<MemSpaceRegion>(R)) 562 return true; 563 564 unsigned &isVisited = visited[R]; 565 if (isVisited) 566 return true; 567 isVisited = 1; 568 569 570 if (!visitor.VisitMemRegion(R)) 571 return false; 572 573 // If this is a symbolic region, visit the symbol for the region. 574 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 575 if (!visitor.VisitSymbol(SR->getSymbol())) 576 return false; 577 578 // If this is a subregion, also visit the parent regions. 579 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) { 580 const MemRegion *Super = SR->getSuperRegion(); 581 if (!scan(Super)) 582 return false; 583 584 // When we reach the topmost region, scan all symbols in it. 585 if (isa<MemSpaceRegion>(Super)) { 586 StoreManager &StoreMgr = state->getStateManager().getStoreManager(); 587 if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this)) 588 return false; 589 } 590 } 591 592 // Regions captured by a block are also implicitly reachable. 593 if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) { 594 BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(), 595 E = BDR->referenced_vars_end(); 596 for ( ; I != E; ++I) { 597 if (!scan(I.getCapturedRegion())) 598 return false; 599 } 600 } 601 602 return true; 603} 604 605bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { 606 ScanReachableSymbols S(this, visitor); 607 return S.scan(val); 608} 609 610bool ProgramState::scanReachableSymbols(const SVal *I, const SVal *E, 611 SymbolVisitor &visitor) const { 612 ScanReachableSymbols S(this, visitor); 613 for ( ; I != E; ++I) { 614 if (!S.scan(*I)) 615 return false; 616 } 617 return true; 618} 619 620bool ProgramState::scanReachableSymbols(const MemRegion * const *I, 621 const MemRegion * const *E, 622 SymbolVisitor &visitor) const { 623 ScanReachableSymbols S(this, visitor); 624 for ( ; I != E; ++I) { 625 if (!S.scan(*I)) 626 return false; 627 } 628 return true; 629} 630 631ProgramStateRef ProgramState::addTaint(const Stmt *S, 632 const LocationContext *LCtx, 633 TaintTagType Kind) const { 634 if (const Expr *E = dyn_cast_or_null<Expr>(S)) 635 S = E->IgnoreParens(); 636 637 SymbolRef Sym = getSVal(S, LCtx).getAsSymbol(); 638 if (Sym) 639 return addTaint(Sym, Kind); 640 641 const MemRegion *R = getSVal(S, LCtx).getAsRegion(); 642 addTaint(R, Kind); 643 644 // Cannot add taint, so just return the state. 645 return this; 646} 647 648ProgramStateRef ProgramState::addTaint(const MemRegion *R, 649 TaintTagType Kind) const { 650 if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R)) 651 return addTaint(SR->getSymbol(), Kind); 652 return this; 653} 654 655ProgramStateRef ProgramState::addTaint(SymbolRef Sym, 656 TaintTagType Kind) const { 657 // If this is a symbol cast, remove the cast before adding the taint. Taint 658 // is cast agnostic. 659 while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) 660 Sym = SC->getOperand(); 661 662 ProgramStateRef NewState = set<TaintMap>(Sym, Kind); 663 assert(NewState); 664 return NewState; 665} 666 667bool ProgramState::isTainted(const Stmt *S, const LocationContext *LCtx, 668 TaintTagType Kind) const { 669 if (const Expr *E = dyn_cast_or_null<Expr>(S)) 670 S = E->IgnoreParens(); 671 672 SVal val = getSVal(S, LCtx); 673 return isTainted(val, Kind); 674} 675 676bool ProgramState::isTainted(SVal V, TaintTagType Kind) const { 677 if (const SymExpr *Sym = V.getAsSymExpr()) 678 return isTainted(Sym, Kind); 679 if (const MemRegion *Reg = V.getAsRegion()) 680 return isTainted(Reg, Kind); 681 return false; 682} 683 684bool ProgramState::isTainted(const MemRegion *Reg, TaintTagType K) const { 685 if (!Reg) 686 return false; 687 688 // Element region (array element) is tainted if either the base or the offset 689 // are tainted. 690 if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg)) 691 return isTainted(ER->getSuperRegion(), K) || isTainted(ER->getIndex(), K); 692 693 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) 694 return isTainted(SR->getSymbol(), K); 695 696 if (const SubRegion *ER = dyn_cast<SubRegion>(Reg)) 697 return isTainted(ER->getSuperRegion(), K); 698 699 return false; 700} 701 702bool ProgramState::isTainted(SymbolRef Sym, TaintTagType Kind) const { 703 if (!Sym) 704 return false; 705 706 // Traverse all the symbols this symbol depends on to see if any are tainted. 707 bool Tainted = false; 708 for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end(); 709 SI != SE; ++SI) { 710 assert(isa<SymbolData>(*SI)); 711 const TaintTagType *Tag = get<TaintMap>(*SI); 712 Tainted = (Tag && *Tag == Kind); 713 714 // If this is a SymbolDerived with a tainted parent, it's also tainted. 715 if (const SymbolDerived *SD = dyn_cast<SymbolDerived>(*SI)) 716 Tainted = Tainted || isTainted(SD->getParentSymbol(), Kind); 717 718 // If memory region is tainted, data is also tainted. 719 if (const SymbolRegionValue *SRV = dyn_cast<SymbolRegionValue>(*SI)) 720 Tainted = Tainted || isTainted(SRV->getRegion(), Kind); 721 722 // If If this is a SymbolCast from a tainted value, it's also tainted. 723 if (const SymbolCast *SC = dyn_cast<SymbolCast>(*SI)) 724 Tainted = Tainted || isTainted(SC->getOperand(), Kind); 725 726 if (Tainted) 727 return true; 728 } 729 730 return Tainted; 731} 732 733/// The GDM component containing the dynamic type info. This is a map from a 734/// symbol to it's most likely type. 735namespace clang { 736namespace ento { 737struct DynamicTypeMap {}; 738typedef llvm::ImmutableMap<SymbolRef, DynamicTypeInfo> DynamicTypeMapImpl; 739template<> struct ProgramStateTrait<DynamicTypeMap> 740 : public ProgramStatePartialTrait<DynamicTypeMapImpl> { 741 static void *GDMIndex() { static int index; return &index; } 742}; 743}} 744 745DynamicTypeInfo ProgramState::getDynamicTypeInfo(const MemRegion *Reg) const { 746 if (const TypedRegion *TR = dyn_cast<TypedRegion>(Reg)) 747 return DynamicTypeInfo(TR->getLocationType()); 748 749 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) { 750 SymbolRef Sym = SR->getSymbol(); 751 // Lookup the dynamic type in the GDM. 752 const DynamicTypeInfo *GDMType = get<DynamicTypeMap>(Sym); 753 if (GDMType) 754 return *GDMType; 755 756 // Else, lookup the type at point of symbol creation. 757 return DynamicTypeInfo(Sym->getType(getStateManager().getContext())); 758 } 759 return DynamicTypeInfo(); 760} 761 762ProgramStateRef ProgramState::addDynamicTypeInfo(const MemRegion *Reg, 763 DynamicTypeInfo NewTy) const { 764 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) { 765 SymbolRef Sym = SR->getSymbol(); 766 // TODO: Instead of resetting the type info, check the old type info and 767 // merge and pick the most precise type. 768 ProgramStateRef NewState = set<DynamicTypeMap>(Sym, NewTy); 769 assert(NewState); 770 return NewState; 771 } 772 return this; 773} 774