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