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