ProgramState.cpp revision dbd658e139b3e0bf084f75feaea8d844af9e319f
1//= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- C++ -*--= 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements ProgramState and ProgramStateManager. 11// 12//===----------------------------------------------------------------------===// 13 14#include "clang/Analysis/CFG.h" 15#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 16#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/TransferFuncs.h" 19#include "llvm/Support/raw_ostream.h" 20 21using namespace clang; 22using namespace ento; 23 24// Give the vtable for ConstraintManager somewhere to live. 25// FIXME: Move this elsewhere. 26ConstraintManager::~ConstraintManager() {} 27 28ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, 29 StoreRef st, GenericDataMap gdm) 30 : stateMgr(mgr), 31 Env(env), 32 store(st.getStore()), 33 GDM(gdm), 34 refCount(0) { 35 stateMgr->getStoreManager().incrementReferenceCount(store); 36} 37 38ProgramState::ProgramState(const ProgramState &RHS) 39 : llvm::FoldingSetNode(), 40 stateMgr(RHS.stateMgr), 41 Env(RHS.Env), 42 store(RHS.store), 43 GDM(RHS.GDM), 44 refCount(0) { 45 stateMgr->getStoreManager().incrementReferenceCount(store); 46} 47 48ProgramState::~ProgramState() { 49 if (store) 50 stateMgr->getStoreManager().decrementReferenceCount(store); 51} 52 53ProgramStateManager::~ProgramStateManager() { 54 for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); 55 I!=E; ++I) 56 I->second.second(I->second.first); 57} 58 59const ProgramState* 60ProgramStateManager::removeDeadBindings(const ProgramState *state, 61 const StackFrameContext *LCtx, 62 SymbolReaper& SymReaper) { 63 64 // This code essentially performs a "mark-and-sweep" of the VariableBindings. 65 // The roots are any Block-level exprs and Decls that our liveness algorithm 66 // tells us are live. We then see what Decls they may reference, and keep 67 // those around. This code more than likely can be made faster, and the 68 // frequency of which this method is called should be experimented with 69 // for optimum performance. 70 ProgramState NewState = *state; 71 72 NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state); 73 74 // Clean up the store. 75 StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx, 76 SymReaper); 77 NewState.setStore(newStore); 78 SymReaper.setReapedStore(newStore); 79 80 return getPersistentState(NewState); 81} 82 83const ProgramState *ProgramStateManager::MarshalState(const ProgramState *state, 84 const StackFrameContext *InitLoc) { 85 // make up an empty state for now. 86 ProgramState State(this, 87 EnvMgr.getInitialEnvironment(), 88 StoreMgr->getInitialStore(InitLoc), 89 GDMFactory.getEmptyMap()); 90 91 return getPersistentState(State); 92} 93 94const ProgramState *ProgramState::bindCompoundLiteral(const CompoundLiteralExpr *CL, 95 const LocationContext *LC, 96 SVal V) const { 97 const StoreRef &newStore = 98 getStateManager().StoreMgr->BindCompoundLiteral(getStore(), CL, LC, V); 99 return makeWithStore(newStore); 100} 101 102const ProgramState *ProgramState::bindDecl(const VarRegion* VR, SVal IVal) const { 103 const StoreRef &newStore = 104 getStateManager().StoreMgr->BindDecl(getStore(), VR, IVal); 105 return makeWithStore(newStore); 106} 107 108const ProgramState *ProgramState::bindDeclWithNoInit(const VarRegion* VR) const { 109 const StoreRef &newStore = 110 getStateManager().StoreMgr->BindDeclWithNoInit(getStore(), VR); 111 return makeWithStore(newStore); 112} 113 114const ProgramState *ProgramState::bindLoc(Loc LV, SVal V) const { 115 ProgramStateManager &Mgr = getStateManager(); 116 const ProgramState *newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(), 117 LV, V)); 118 const MemRegion *MR = LV.getAsRegion(); 119 if (MR && Mgr.getOwningEngine()) 120 return Mgr.getOwningEngine()->processRegionChange(newState, MR); 121 122 return newState; 123} 124 125const ProgramState *ProgramState::bindDefault(SVal loc, SVal V) const { 126 ProgramStateManager &Mgr = getStateManager(); 127 const MemRegion *R = cast<loc::MemRegionVal>(loc).getRegion(); 128 const StoreRef &newStore = Mgr.StoreMgr->BindDefault(getStore(), R, V); 129 const ProgramState *new_state = makeWithStore(newStore); 130 return Mgr.getOwningEngine() ? 131 Mgr.getOwningEngine()->processRegionChange(new_state, R) : 132 new_state; 133} 134 135const ProgramState * 136ProgramState::invalidateRegions(ArrayRef<const MemRegion *> Regions, 137 const Expr *E, unsigned Count, 138 StoreManager::InvalidatedSymbols *IS, 139 bool invalidateGlobals) const { 140 if (!IS) { 141 StoreManager::InvalidatedSymbols invalidated; 142 return invalidateRegionsImpl(Regions, E, Count, 143 invalidated, invalidateGlobals); 144 } 145 return invalidateRegionsImpl(Regions, E, Count, *IS, invalidateGlobals); 146} 147 148const ProgramState * 149ProgramState::invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions, 150 const Expr *E, unsigned Count, 151 StoreManager::InvalidatedSymbols &IS, 152 bool invalidateGlobals) const { 153 ProgramStateManager &Mgr = getStateManager(); 154 SubEngine* Eng = Mgr.getOwningEngine(); 155 156 if (Eng && Eng->wantsRegionChangeUpdate(this)) { 157 StoreManager::InvalidatedRegions Invalidated; 158 const StoreRef &newStore 159 = Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, IS, 160 invalidateGlobals, &Invalidated); 161 const ProgramState *newState = makeWithStore(newStore); 162 return Eng->processRegionChanges(newState, &IS, Regions, Invalidated); 163 } 164 165 const StoreRef &newStore = 166 Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, IS, 167 invalidateGlobals, NULL); 168 return makeWithStore(newStore); 169} 170 171const ProgramState *ProgramState::unbindLoc(Loc LV) const { 172 assert(!isa<loc::MemRegionVal>(LV) && "Use invalidateRegion instead."); 173 174 Store OldStore = getStore(); 175 const StoreRef &newStore = getStateManager().StoreMgr->Remove(OldStore, LV); 176 177 if (newStore.getStore() == OldStore) 178 return this; 179 180 return makeWithStore(newStore); 181} 182 183const ProgramState *ProgramState::enterStackFrame(const StackFrameContext *frame) const { 184 const StoreRef &new_store = 185 getStateManager().StoreMgr->enterStackFrame(this, frame); 186 return makeWithStore(new_store); 187} 188 189SVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const { 190 // We only want to do fetches from regions that we can actually bind 191 // values. For example, SymbolicRegions of type 'id<...>' cannot 192 // have direct bindings (but their can be bindings on their subregions). 193 if (!R->isBoundable()) 194 return UnknownVal(); 195 196 if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 197 QualType T = TR->getValueType(); 198 if (Loc::isLocType(T) || T->isIntegerType()) 199 return getSVal(R); 200 } 201 202 return UnknownVal(); 203} 204 205SVal ProgramState::getSVal(Loc location, QualType T) const { 206 SVal V = getRawSVal(cast<Loc>(location), T); 207 208 // If 'V' is a symbolic value that is *perfectly* constrained to 209 // be a constant value, use that value instead to lessen the burden 210 // on later analysis stages (so we have less symbolic values to reason 211 // about). 212 if (!T.isNull()) { 213 if (SymbolRef sym = V.getAsSymbol()) { 214 if (const llvm::APSInt *Int = getSymVal(sym)) { 215 // FIXME: Because we don't correctly model (yet) sign-extension 216 // and truncation of symbolic values, we need to convert 217 // the integer value to the correct signedness and bitwidth. 218 // 219 // This shows up in the following: 220 // 221 // char foo(); 222 // unsigned x = foo(); 223 // if (x == 54) 224 // ... 225 // 226 // The symbolic value stored to 'x' is actually the conjured 227 // symbol for the call to foo(); the type of that symbol is 'char', 228 // not unsigned. 229 const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int); 230 231 if (isa<Loc>(V)) 232 return loc::ConcreteInt(NewV); 233 else 234 return nonloc::ConcreteInt(NewV); 235 } 236 } 237 } 238 239 return V; 240} 241 242const ProgramState *ProgramState::BindExpr(const Stmt *S, SVal V, bool Invalidate) const{ 243 Environment NewEnv = getStateManager().EnvMgr.bindExpr(Env, S, V, 244 Invalidate); 245 if (NewEnv == Env) 246 return this; 247 248 ProgramState NewSt = *this; 249 NewSt.Env = NewEnv; 250 return getStateManager().getPersistentState(NewSt); 251} 252 253const ProgramState *ProgramState::bindExprAndLocation(const Stmt *S, SVal location, 254 SVal V) const { 255 Environment NewEnv = 256 getStateManager().EnvMgr.bindExprAndLocation(Env, S, location, V); 257 258 if (NewEnv == Env) 259 return this; 260 261 ProgramState NewSt = *this; 262 NewSt.Env = NewEnv; 263 return getStateManager().getPersistentState(NewSt); 264} 265 266const ProgramState *ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, 267 DefinedOrUnknownSVal UpperBound, 268 bool Assumption) const { 269 if (Idx.isUnknown() || UpperBound.isUnknown()) 270 return this; 271 272 // Build an expression for 0 <= Idx < UpperBound. 273 // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed. 274 // FIXME: This should probably be part of SValBuilder. 275 ProgramStateManager &SM = getStateManager(); 276 SValBuilder &svalBuilder = SM.getSValBuilder(); 277 ASTContext &Ctx = svalBuilder.getContext(); 278 279 // Get the offset: the minimum value of the array index type. 280 BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); 281 // FIXME: This should be using ValueManager::ArrayindexTy...somehow. 282 QualType indexTy = Ctx.IntTy; 283 nonloc::ConcreteInt Min(BVF.getMinValue(indexTy)); 284 285 // Adjust the index. 286 SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add, 287 cast<NonLoc>(Idx), Min, indexTy); 288 if (newIdx.isUnknownOrUndef()) 289 return this; 290 291 // Adjust the upper bound. 292 SVal newBound = 293 svalBuilder.evalBinOpNN(this, BO_Add, cast<NonLoc>(UpperBound), 294 Min, indexTy); 295 296 if (newBound.isUnknownOrUndef()) 297 return this; 298 299 // Build the actual comparison. 300 SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, 301 cast<NonLoc>(newIdx), cast<NonLoc>(newBound), 302 Ctx.IntTy); 303 if (inBound.isUnknownOrUndef()) 304 return this; 305 306 // Finally, let the constraint manager take care of it. 307 ConstraintManager &CM = SM.getConstraintManager(); 308 return CM.assume(this, cast<DefinedSVal>(inBound), Assumption); 309} 310 311const ProgramState *ProgramStateManager::getInitialState(const LocationContext *InitLoc) { 312 ProgramState State(this, 313 EnvMgr.getInitialEnvironment(), 314 StoreMgr->getInitialStore(InitLoc), 315 GDMFactory.getEmptyMap()); 316 317 return getPersistentState(State); 318} 319 320void ProgramStateManager::recycleUnusedStates() { 321 for (std::vector<ProgramState*>::iterator i = recentlyAllocatedStates.begin(), 322 e = recentlyAllocatedStates.end(); i != e; ++i) { 323 ProgramState *state = *i; 324 if (state->referencedByExplodedNode()) 325 continue; 326 StateSet.RemoveNode(state); 327 freeStates.push_back(state); 328 state->~ProgramState(); 329 } 330 recentlyAllocatedStates.clear(); 331} 332 333const ProgramState *ProgramStateManager::getPersistentStateWithGDM( 334 const ProgramState *FromState, 335 const ProgramState *GDMState) { 336 ProgramState NewState = *FromState; 337 NewState.GDM = GDMState->GDM; 338 return getPersistentState(NewState); 339} 340 341const ProgramState *ProgramStateManager::getPersistentState(ProgramState &State) { 342 343 llvm::FoldingSetNodeID ID; 344 State.Profile(ID); 345 void *InsertPos; 346 347 if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos)) 348 return I; 349 350 ProgramState *newState = 0; 351 if (!freeStates.empty()) { 352 newState = freeStates.back(); 353 freeStates.pop_back(); 354 } 355 else { 356 newState = (ProgramState*) Alloc.Allocate<ProgramState>(); 357 } 358 new (newState) ProgramState(State); 359 StateSet.InsertNode(newState, InsertPos); 360 recentlyAllocatedStates.push_back(newState); 361 return newState; 362} 363 364const ProgramState *ProgramState::makeWithStore(const StoreRef &store) const { 365 ProgramState NewSt = *this; 366 NewSt.setStore(store); 367 return getStateManager().getPersistentState(NewSt); 368} 369 370void ProgramState::setStore(const StoreRef &newStore) { 371 Store newStoreStore = newStore.getStore(); 372 if (newStoreStore) 373 stateMgr->getStoreManager().incrementReferenceCount(newStoreStore); 374 if (store) 375 stateMgr->getStoreManager().decrementReferenceCount(store); 376 store = newStoreStore; 377} 378 379//===----------------------------------------------------------------------===// 380// State pretty-printing. 381//===----------------------------------------------------------------------===// 382 383static bool IsEnvLoc(const Stmt *S) { 384 // FIXME: This is a layering violation. Should be in environment. 385 return (bool) (((uintptr_t) S) & 0x1); 386} 387 388void ProgramState::print(raw_ostream &Out, CFG &C, 389 const char *NL, const char *Sep) const { 390 // Print the store. 391 ProgramStateManager &Mgr = getStateManager(); 392 Mgr.getStoreManager().print(getStore(), Out, NL, Sep); 393 394 // Print Subexpression bindings. 395 bool isFirst = true; 396 397 // FIXME: All environment printing should be moved inside Environment. 398 for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { 399 if (C.isBlkExpr(I.getKey()) || IsEnvLoc(I.getKey())) 400 continue; 401 402 if (isFirst) { 403 Out << NL << NL << "Sub-Expressions:" << NL; 404 isFirst = false; 405 } else { 406 Out << NL; 407 } 408 409 Out << " (" << (void*) I.getKey() << ") "; 410 LangOptions LO; // FIXME. 411 I.getKey()->printPretty(Out, 0, PrintingPolicy(LO)); 412 Out << " : " << I.getData(); 413 } 414 415 // Print block-expression bindings. 416 isFirst = true; 417 418 for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { 419 if (!C.isBlkExpr(I.getKey())) 420 continue; 421 422 if (isFirst) { 423 Out << NL << NL << "Block-level Expressions:" << NL; 424 isFirst = false; 425 } else { 426 Out << NL; 427 } 428 429 Out << " (" << (void*) I.getKey() << ") "; 430 LangOptions LO; // FIXME. 431 I.getKey()->printPretty(Out, 0, PrintingPolicy(LO)); 432 Out << " : " << I.getData(); 433 } 434 435 // Print locations. 436 isFirst = true; 437 438 for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { 439 if (!IsEnvLoc(I.getKey())) 440 continue; 441 442 if (isFirst) { 443 Out << NL << NL << "Load/store locations:" << NL; 444 isFirst = false; 445 } else { 446 Out << NL; 447 } 448 449 const Stmt *S = (Stmt*) (((uintptr_t) I.getKey()) & ((uintptr_t) ~0x1)); 450 451 Out << " (" << (void*) S << ") "; 452 LangOptions LO; // FIXME. 453 S->printPretty(Out, 0, PrintingPolicy(LO)); 454 Out << " : " << I.getData(); 455 } 456 457 Mgr.getConstraintManager().print(this, Out, NL, Sep); 458 459 // Print checker-specific data. 460 Mgr.getOwningEngine()->printState(Out, this, NL, Sep); 461} 462 463void ProgramState::printDOT(raw_ostream &Out, CFG &C) const { 464 print(Out, C, "\\l", "\\|"); 465} 466 467void ProgramState::printStdErr(CFG &C) const { 468 print(llvm::errs(), C); 469} 470 471//===----------------------------------------------------------------------===// 472// Generic Data Map. 473//===----------------------------------------------------------------------===// 474 475void *const* ProgramState::FindGDM(void *K) const { 476 return GDM.lookup(K); 477} 478 479void* 480ProgramStateManager::FindGDMContext(void *K, 481 void *(*CreateContext)(llvm::BumpPtrAllocator&), 482 void (*DeleteContext)(void*)) { 483 484 std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; 485 if (!p.first) { 486 p.first = CreateContext(Alloc); 487 p.second = DeleteContext; 488 } 489 490 return p.first; 491} 492 493const ProgramState *ProgramStateManager::addGDM(const ProgramState *St, void *Key, void *Data){ 494 ProgramState::GenericDataMap M1 = St->getGDM(); 495 ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data); 496 497 if (M1 == M2) 498 return St; 499 500 ProgramState NewSt = *St; 501 NewSt.GDM = M2; 502 return getPersistentState(NewSt); 503} 504 505const ProgramState *ProgramStateManager::removeGDM(const ProgramState *state, void *Key) { 506 ProgramState::GenericDataMap OldM = state->getGDM(); 507 ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key); 508 509 if (NewM == OldM) 510 return state; 511 512 ProgramState NewState = *state; 513 NewState.GDM = NewM; 514 return getPersistentState(NewState); 515} 516 517//===----------------------------------------------------------------------===// 518// Utility. 519//===----------------------------------------------------------------------===// 520 521namespace { 522class ScanReachableSymbols : public SubRegionMap::Visitor { 523 typedef llvm::DenseMap<const void*, unsigned> VisitedItems; 524 525 VisitedItems visited; 526 const ProgramState *state; 527 SymbolVisitor &visitor; 528 llvm::OwningPtr<SubRegionMap> SRM; 529public: 530 531 ScanReachableSymbols(const ProgramState *st, SymbolVisitor& v) 532 : state(st), visitor(v) {} 533 534 bool scan(nonloc::CompoundVal val); 535 bool scan(SVal val); 536 bool scan(const MemRegion *R); 537 bool scan(const SymExpr *sym); 538 539 // From SubRegionMap::Visitor. 540 bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) { 541 return scan(SubRegion); 542 } 543}; 544} 545 546bool ScanReachableSymbols::scan(nonloc::CompoundVal val) { 547 for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) 548 if (!scan(*I)) 549 return false; 550 551 return true; 552} 553 554bool ScanReachableSymbols::scan(const SymExpr *sym) { 555 unsigned &isVisited = visited[sym]; 556 if (isVisited) 557 return true; 558 isVisited = 1; 559 560 if (const SymbolData *sData = dyn_cast<SymbolData>(sym)) 561 if (!visitor.VisitSymbol(sData)) 562 return false; 563 564 switch (sym->getKind()) { 565 case SymExpr::RegionValueKind: 566 case SymExpr::ConjuredKind: 567 case SymExpr::DerivedKind: 568 case SymExpr::ExtentKind: 569 case SymExpr::MetadataKind: 570 break; 571 case SymExpr::SymIntKind: 572 return scan(cast<SymIntExpr>(sym)->getLHS()); 573 case SymExpr::SymSymKind: { 574 const SymSymExpr *x = cast<SymSymExpr>(sym); 575 return scan(x->getLHS()) && scan(x->getRHS()); 576 } 577 } 578 return true; 579} 580 581bool ScanReachableSymbols::scan(SVal val) { 582 if (loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(&val)) 583 return scan(X->getRegion()); 584 585 if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&val)) 586 return scan(X->getLoc()); 587 588 if (SymbolRef Sym = val.getAsSymbol()) 589 return scan(Sym); 590 591 if (const SymExpr *Sym = val.getAsSymbolicExpression()) 592 return scan(Sym); 593 594 if (nonloc::CompoundVal *X = dyn_cast<nonloc::CompoundVal>(&val)) 595 return scan(*X); 596 597 return true; 598} 599 600bool ScanReachableSymbols::scan(const MemRegion *R) { 601 if (isa<MemSpaceRegion>(R)) 602 return true; 603 604 unsigned &isVisited = visited[R]; 605 if (isVisited) 606 return true; 607 isVisited = 1; 608 609 // If this is a symbolic region, visit the symbol for the region. 610 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 611 if (!visitor.VisitSymbol(SR->getSymbol())) 612 return false; 613 614 // If this is a subregion, also visit the parent regions. 615 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) 616 if (!scan(SR->getSuperRegion())) 617 return false; 618 619 // Now look at the binding to this region (if any). 620 if (!scan(state->getSValAsScalarOrLoc(R))) 621 return false; 622 623 // Now look at the subregions. 624 if (!SRM.get()) 625 SRM.reset(state->getStateManager().getStoreManager(). 626 getSubRegionMap(state->getStore())); 627 628 return SRM->iterSubRegions(R, *this); 629} 630 631bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { 632 ScanReachableSymbols S(this, visitor); 633 return S.scan(val); 634} 635 636bool ProgramState::scanReachableSymbols(const SVal *I, const SVal *E, 637 SymbolVisitor &visitor) const { 638 ScanReachableSymbols S(this, visitor); 639 for ( ; I != E; ++I) { 640 if (!S.scan(*I)) 641 return false; 642 } 643 return true; 644} 645 646bool ProgramState::scanReachableSymbols(const MemRegion * const *I, 647 const MemRegion * const *E, 648 SymbolVisitor &visitor) const { 649 ScanReachableSymbols S(this, visitor); 650 for ( ; I != E; ++I) { 651 if (!S.scan(*I)) 652 return false; 653 } 654 return true; 655} 656