diff options
| author | Anton Yartsev <anton.yartsev@gmail.com> | 2013-09-24 23:47:29 +0000 |
|---|---|---|
| committer | Anton Yartsev <anton.yartsev@gmail.com> | 2013-09-24 23:47:29 +0000 |
| commit | 424ad95fa73cfe7c917c63fd94977b7c13a2b036 (patch) | |
| tree | 548dc6328c2b6c383e21bef6cb42049dc08229c3 /clang/lib | |
| parent | 8db1eddc072cb606f24689f8e0a438a44ee6aa4d (diff) | |
| download | bcm5719-llvm-424ad95fa73cfe7c917c63fd94977b7c13a2b036.tar.gz bcm5719-llvm-424ad95fa73cfe7c917c63fd94977b7c13a2b036.zip | |
[analyzer] This patch removes passing around of const-invalidation vs regular-invalidation info by passing around a datastructure that maps regions and symbols to the type of invalidation they experience. This simplifies the code and would allow to associate more different invalidation types in the future.
With this patch things like preserving contents of regions (either hi- or low-level ones) or processing of the only top-level region can be implemented easily without passing around extra parameters.
This patch is a first step towards adequate modeling of memcpy() by the CStringChecker checker and towards eliminating of majority of false-positives produced by the NewDeleteLeaks checker.
llvm-svn: 191342
Diffstat (limited to 'clang/lib')
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/CallEvent.cpp | 13 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/CheckerManager.cpp | 10 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 21 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/MemRegion.cpp | 42 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/ProgramState.cpp | 90 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/RegionStore.cpp | 88 |
6 files changed, 133 insertions, 131 deletions
diff --git a/clang/lib/StaticAnalyzer/Core/CallEvent.cpp b/clang/lib/StaticAnalyzer/Core/CallEvent.cpp index 64a4f8d69e2..556f93b7cfb 100644 --- a/clang/lib/StaticAnalyzer/Core/CallEvent.cpp +++ b/clang/lib/StaticAnalyzer/Core/CallEvent.cpp @@ -140,8 +140,8 @@ ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount, ProgramStateRef Orig) const { ProgramStateRef Result = (Orig ? Orig : getState()); - SmallVector<SVal, 8> ConstValues; SmallVector<SVal, 8> ValuesToInvalidate; + RegionAndSymbolInvalidationTraits ETraits; getExtraInvalidatedValues(ValuesToInvalidate); @@ -154,9 +154,12 @@ ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount, // Mark this region for invalidation. We batch invalidate regions // below for efficiency. if (PreserveArgs.count(Idx)) - ConstValues.push_back(getArgSVal(Idx)); - else - ValuesToInvalidate.push_back(getArgSVal(Idx)); + if (const MemRegion *MR = getArgSVal(Idx).getAsRegion()) + ETraits.setTrait(MR->StripCasts(), + RegionAndSymbolInvalidationTraits::TK_PreserveContents); + // TODO: Factor this out + handle the lower level const pointers. + + ValuesToInvalidate.push_back(getArgSVal(Idx)); } // Invalidate designated regions using the batch invalidation API. @@ -165,7 +168,7 @@ ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount, return Result->invalidateRegions(ValuesToInvalidate, getOriginExpr(), BlockCount, getLocationContext(), /*CausedByPointerEscape*/ true, - /*Symbols=*/0, this, ConstValues); + /*Symbols=*/0, this, &ETraits); } ProgramPoint CallEvent::getProgramPoint(bool IsPreVisit, diff --git a/clang/lib/StaticAnalyzer/Core/CheckerManager.cpp b/clang/lib/StaticAnalyzer/Core/CheckerManager.cpp index aaf1ea25ba0..c1ae7e9d812 100644 --- a/clang/lib/StaticAnalyzer/Core/CheckerManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/CheckerManager.cpp @@ -487,10 +487,10 @@ CheckerManager::runCheckersForRegionChanges(ProgramStateRef state, /// \brief Run checkers to process symbol escape event. ProgramStateRef CheckerManager::runCheckersForPointerEscape(ProgramStateRef State, - const InvalidatedSymbols &Escaped, - const CallEvent *Call, - PointerEscapeKind Kind, - bool IsConst) { + const InvalidatedSymbols &Escaped, + const CallEvent *Call, + PointerEscapeKind Kind, + RegionAndSymbolInvalidationTraits *ETraits) { assert((Call != NULL || (Kind != PSK_DirectEscapeOnCall && Kind != PSK_IndirectEscapeOnCall)) && @@ -500,7 +500,7 @@ CheckerManager::runCheckersForPointerEscape(ProgramStateRef State, // way), bail out. if (!State) return NULL; - State = PointerEscapeCheckers[i](State, Escaped, Call, Kind, IsConst); + State = PointerEscapeCheckers[i](State, Escaped, Call, Kind, ETraits); } return State; } diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 52d22edc93e..91acd55bc7f 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -1876,7 +1876,8 @@ ProgramStateRef ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, State = getCheckerManager().runCheckersForPointerEscape(State, EscapedSymbols, /*CallEvent*/ 0, - PSK_EscapeOnBind); + PSK_EscapeOnBind, + 0); return State; } @@ -1887,7 +1888,7 @@ ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, ArrayRef<const MemRegion *> ExplicitRegions, ArrayRef<const MemRegion *> Regions, const CallEvent *Call, - bool IsConst) { + RegionAndSymbolInvalidationTraits &ITraits) { if (!Invalidated || Invalidated->empty()) return State; @@ -1897,17 +1898,7 @@ ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, *Invalidated, 0, PSK_EscapeOther, - IsConst); - - // Note: Due to current limitations of RegionStore, we only process the top - // level const pointers correctly. The lower level const pointers are - // currently treated as non-const. - if (IsConst) - return getCheckerManager().runCheckersForPointerEscape(State, - *Invalidated, - Call, - PSK_DirectEscapeOnCall, - true); + &ITraits); // If the symbols were invalidated by a call, we want to find out which ones // were invalidated directly due to being arguments to the call. @@ -1929,12 +1920,12 @@ ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, if (!SymbolsDirectlyInvalidated.empty()) State = getCheckerManager().runCheckersForPointerEscape(State, - SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall); + SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits); // Notify about the symbols that get indirectly invalidated by the call. if (!SymbolsIndirectlyInvalidated.empty()) State = getCheckerManager().runCheckersForPointerEscape(State, - SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall); + SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits); return State; } diff --git a/clang/lib/StaticAnalyzer/Core/MemRegion.cpp b/clang/lib/StaticAnalyzer/Core/MemRegion.cpp index 9051d5a13ef..1be5840a20b 100644 --- a/clang/lib/StaticAnalyzer/Core/MemRegion.cpp +++ b/clang/lib/StaticAnalyzer/Core/MemRegion.cpp @@ -1450,3 +1450,45 @@ const VarRegion *BlockDataRegion::getOriginalRegion(const VarRegion *R) const { } return 0; } + +//===----------------------------------------------------------------------===// +// RegionAndSymbolInvalidationTraits +//===----------------------------------------------------------------------===// + +void RegionAndSymbolInvalidationTraits::setTrait(SymbolRef Sym, + InvalidationKinds IK) { + SymTraitsMap[Sym] |= IK; +} + +void RegionAndSymbolInvalidationTraits::setTrait(const MemRegion *MR, + InvalidationKinds IK) { + assert(MR); + if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) + setTrait(SR->getSymbol(), IK); + else + MRTraitsMap[MR] |= IK; +} + +bool RegionAndSymbolInvalidationTraits::hasTrait(SymbolRef Sym, + InvalidationKinds IK) { + const_symbol_iterator I = SymTraitsMap.find(Sym); + if (I != SymTraitsMap.end()) + return I->second & IK; + + return false; +} + +bool RegionAndSymbolInvalidationTraits::hasTrait(const MemRegion *MR, + InvalidationKinds IK) { + if (!MR) + return false; + + if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) + return hasTrait(SR->getSymbol(), IK); + + const_region_iterator I = MRTraitsMap.find(MR); + if (I != MRTraitsMap.end()) + return I->second & IK; + + return false; +} diff --git a/clang/lib/StaticAnalyzer/Core/ProgramState.cpp b/clang/lib/StaticAnalyzer/Core/ProgramState.cpp index fbd3fc526d3..6e236681440 100644 --- a/clang/lib/StaticAnalyzer/Core/ProgramState.cpp +++ b/clang/lib/StaticAnalyzer/Core/ProgramState.cpp @@ -137,48 +137,32 @@ typedef ArrayRef<SVal> ValueList; ProgramStateRef ProgramState::invalidateRegions(RegionList Regions, - const Expr *E, unsigned Count, - const LocationContext *LCtx, - bool CausedByPointerEscape, - InvalidatedSymbols *IS, - const CallEvent *Call, - RegionList ConstRegions) const { + const Expr *E, unsigned Count, + const LocationContext *LCtx, + bool CausedByPointerEscape, + InvalidatedSymbols *IS, + const CallEvent *Call, + RegionAndSymbolInvalidationTraits *ITraits) const { SmallVector<SVal, 8> Values; for (RegionList::const_iterator I = Regions.begin(), End = Regions.end(); I != End; ++I) Values.push_back(loc::MemRegionVal(*I)); - SmallVector<SVal, 8> ConstValues; - for (RegionList::const_iterator I = ConstRegions.begin(), - End = ConstRegions.end(); I != End; ++I) - ConstValues.push_back(loc::MemRegionVal(*I)); - - if (!IS) { - InvalidatedSymbols invalidated; - return invalidateRegionsImpl(Values, E, Count, LCtx, - CausedByPointerEscape, - invalidated, Call, ConstValues); - } return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, - *IS, Call, ConstValues); + IS, ITraits, Call); } ProgramStateRef ProgramState::invalidateRegions(ValueList Values, - const Expr *E, unsigned Count, - const LocationContext *LCtx, - bool CausedByPointerEscape, - InvalidatedSymbols *IS, - const CallEvent *Call, - ValueList ConstValues) const { - if (!IS) { - InvalidatedSymbols invalidated; - return invalidateRegionsImpl(Values, E, Count, LCtx, - CausedByPointerEscape, - invalidated, Call, ConstValues); - } + const Expr *E, unsigned Count, + const LocationContext *LCtx, + bool CausedByPointerEscape, + InvalidatedSymbols *IS, + const CallEvent *Call, + RegionAndSymbolInvalidationTraits *ITraits) const { + return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, - *IS, Call, ConstValues); + IS, ITraits, Call); } ProgramStateRef @@ -186,49 +170,45 @@ ProgramState::invalidateRegionsImpl(ValueList Values, const Expr *E, unsigned Count, const LocationContext *LCtx, bool CausedByPointerEscape, - InvalidatedSymbols &IS, - const CallEvent *Call, - ValueList ConstValues) const { + InvalidatedSymbols *IS, + RegionAndSymbolInvalidationTraits *ITraits, + const CallEvent *Call) const { ProgramStateManager &Mgr = getStateManager(); SubEngine* Eng = Mgr.getOwningEngine(); InvalidatedSymbols ConstIS; + InvalidatedSymbols Invalidated; + if (!IS) + IS = &Invalidated; + + RegionAndSymbolInvalidationTraits ITraitsLocal; + if (!ITraits) + ITraits = &ITraitsLocal; + if (Eng) { StoreManager::InvalidatedRegions TopLevelInvalidated; - StoreManager::InvalidatedRegions TopLevelConstInvalidated; StoreManager::InvalidatedRegions Invalidated; const StoreRef &newStore - = Mgr.StoreMgr->invalidateRegions(getStore(), Values, ConstValues, - E, Count, LCtx, Call, - IS, ConstIS, - &TopLevelInvalidated, - &TopLevelConstInvalidated, + = Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, + *IS, *ITraits, &TopLevelInvalidated, &Invalidated); ProgramStateRef newState = makeWithStore(newStore); if (CausedByPointerEscape) { - newState = Eng->notifyCheckersOfPointerEscape(newState, &IS, + newState = Eng->notifyCheckersOfPointerEscape(newState, IS, TopLevelInvalidated, - Invalidated, Call); - if (!ConstValues.empty()) { - StoreManager::InvalidatedRegions Empty; - newState = Eng->notifyCheckersOfPointerEscape(newState, &ConstIS, - TopLevelConstInvalidated, - Empty, Call, - true); - } + Invalidated, Call, + *ITraits); } - return Eng->processRegionChanges(newState, &IS, - TopLevelInvalidated, Invalidated, - Call); + return Eng->processRegionChanges(newState, IS, TopLevelInvalidated, + Invalidated, Call); } const StoreRef &newStore = - Mgr.StoreMgr->invalidateRegions(getStore(), Values, ConstValues, - E, Count, LCtx, Call, - IS, ConstIS, NULL, NULL, NULL); + Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, + *IS, *ITraits, NULL, NULL); return makeWithStore(newStore); } diff --git a/clang/lib/StaticAnalyzer/Core/RegionStore.cpp b/clang/lib/StaticAnalyzer/Core/RegionStore.cpp index 50186fbaa5a..bc998d80ec1 100644 --- a/clang/lib/StaticAnalyzer/Core/RegionStore.cpp +++ b/clang/lib/StaticAnalyzer/Core/RegionStore.cpp @@ -349,7 +349,6 @@ private: /// regions. void populateWorkList(invalidateRegionsWorker &W, ArrayRef<SVal> Values, - bool IsArrayOfConstRegions, InvalidatedRegions *TopLevelRegions); public: @@ -395,15 +394,13 @@ public: StoreRef invalidateRegions(Store store, ArrayRef<SVal> Values, - ArrayRef<SVal> ConstValues, const Expr *E, unsigned Count, const LocationContext *LCtx, const CallEvent *Call, InvalidatedSymbols &IS, - InvalidatedSymbols &ConstIS, + RegionAndSymbolInvalidationTraits &ITraits, InvalidatedRegions *Invalidated, - InvalidatedRegions *InvalidatedTopLevel, - InvalidatedRegions *InvalidatedTopLevelConst); + InvalidatedRegions *InvalidatedTopLevel); bool scanReachableSymbols(Store S, const MemRegion *R, ScanReachableSymbols &Callbacks); @@ -648,7 +645,7 @@ template <typename DERIVED> class ClusterAnalysis { protected: typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap; - typedef llvm::PointerIntPair<const MemRegion *, 1, bool> WorkListElement; + typedef const MemRegion * WorkListElement; typedef SmallVector<WorkListElement, 10> WorkList; llvm::SmallPtrSet<const ClusterBindings *, 16> Visited; @@ -720,18 +717,17 @@ public: return true; } - bool AddToWorkList(const MemRegion *R, bool Flag = false) { + bool AddToWorkList(const MemRegion *R) { const MemRegion *BaseR = R->getBaseRegion(); - return AddToWorkList(WorkListElement(BaseR, Flag), getCluster(BaseR)); + return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR)); } void RunWorkList() { while (!WL.empty()) { WorkListElement E = WL.pop_back_val(); - const MemRegion *BaseR = E.getPointer(); + const MemRegion *BaseR = E; - static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR), - E.getInt()); + static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR)); } } @@ -951,7 +947,7 @@ class invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker> unsigned Count; const LocationContext *LCtx; InvalidatedSymbols &IS; - InvalidatedSymbols &ConstIS; + RegionAndSymbolInvalidationTraits &ITraits; StoreManager::InvalidatedRegions *Regions; public: invalidateRegionsWorker(RegionStoreManager &rm, @@ -960,16 +956,15 @@ public: const Expr *ex, unsigned count, const LocationContext *lctx, InvalidatedSymbols &is, - InvalidatedSymbols &inConstIS, + RegionAndSymbolInvalidationTraits &ITraitsIn, StoreManager::InvalidatedRegions *r, GlobalsFilterKind GFK) : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, GFK), - Ex(ex), Count(count), LCtx(lctx), IS(is), ConstIS(inConstIS), Regions(r){} + Ex(ex), Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r){} /// \param IsConst Specifies if the region we are invalidating is constant. /// If it is, we invalidate all subregions, but not the base region itself. - void VisitCluster(const MemRegion *baseR, const ClusterBindings *C, - bool IsConst); + void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); void VisitBinding(SVal V); }; } @@ -1000,14 +995,18 @@ void invalidateRegionsWorker::VisitBinding(SVal V) { } void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, - const ClusterBindings *C, - bool IsConst) { + const ClusterBindings *C) { + + bool PreserveRegionsContents = + ITraits.hasTrait(baseR, + RegionAndSymbolInvalidationTraits::TK_PreserveContents); + if (C) { for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) VisitBinding(I.getData()); - // Invalidate the contents of a non-const base region. - if (!IsConst) + // Invalidate regions contents. + if (!PreserveRegionsContents) B = B.remove(baseR); } @@ -1039,18 +1038,11 @@ void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, } // Symbolic region? - if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { - SymbolRef RegionSym = SR->getSymbol(); - - // Mark that symbol touched by the invalidation. - if (IsConst) - ConstIS.insert(RegionSym); - else - IS.insert(RegionSym); - } + if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) + IS.insert(SR->getSymbol()); - // Nothing else should be done for a const region. - if (IsConst) + // Nothing else should be done in the case when we preserve regions context. + if (PreserveRegionsContents) return; // Otherwise, we have a normal data region. Record that we touched the region. @@ -1059,7 +1051,7 @@ void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) { // Invalidate the region by setting its default value to - // conjured symbol. The type of the symbol is irrelavant. + // conjured symbol. The type of the symbol is irrelevant. DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); B = B.addBinding(baseR, BindingKey::Default, V); @@ -1081,7 +1073,7 @@ void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, if (T->isStructureOrClassType()) { // Invalidate the region by setting its default value to - // conjured symbol. The type of the symbol is irrelavant. + // conjured symbol. The type of the symbol is irrelevant. DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); B = B.addBinding(baseR, BindingKey::Default, V); @@ -1130,7 +1122,6 @@ RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, void RegionStoreManager::populateWorkList(invalidateRegionsWorker &W, ArrayRef<SVal> Values, - bool IsArrayOfConstRegions, InvalidatedRegions *TopLevelRegions) { for (ArrayRef<SVal>::iterator I = Values.begin(), E = Values.end(); I != E; ++I) { @@ -1145,7 +1136,7 @@ void RegionStoreManager::populateWorkList(invalidateRegionsWorker &W, // Note: the last argument is false here because these are // non-top-level regions. if (const MemRegion *R = (*I).getAsRegion()) - W.AddToWorkList(R, /*IsConst=*/ false); + W.AddToWorkList(R); } continue; } @@ -1153,7 +1144,7 @@ void RegionStoreManager::populateWorkList(invalidateRegionsWorker &W, if (const MemRegion *R = V.getAsRegion()) { if (TopLevelRegions) TopLevelRegions->push_back(R); - W.AddToWorkList(R, /*IsConst=*/ IsArrayOfConstRegions); + W.AddToWorkList(R); continue; } } @@ -1161,16 +1152,14 @@ void RegionStoreManager::populateWorkList(invalidateRegionsWorker &W, StoreRef RegionStoreManager::invalidateRegions(Store store, - ArrayRef<SVal> Values, - ArrayRef<SVal> ConstValues, - const Expr *Ex, unsigned Count, - const LocationContext *LCtx, - const CallEvent *Call, - InvalidatedSymbols &IS, - InvalidatedSymbols &ConstIS, - InvalidatedRegions *TopLevelRegions, - InvalidatedRegions *TopLevelConstRegions, - InvalidatedRegions *Invalidated) { + ArrayRef<SVal> Values, + const Expr *Ex, unsigned Count, + const LocationContext *LCtx, + const CallEvent *Call, + InvalidatedSymbols &IS, + RegionAndSymbolInvalidationTraits &ITraits, + InvalidatedRegions *TopLevelRegions, + InvalidatedRegions *Invalidated) { GlobalsFilterKind GlobalsFilter; if (Call) { if (Call->isInSystemHeader()) @@ -1182,17 +1171,14 @@ RegionStoreManager::invalidateRegions(Store store, } RegionBindingsRef B = getRegionBindings(store); - invalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ConstIS, + invalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ITraits, Invalidated, GlobalsFilter); // Scan the bindings and generate the clusters. W.GenerateClusters(); // Add the regions to the worklist. - populateWorkList(W, Values, /*IsArrayOfConstRegions*/ false, - TopLevelRegions); - populateWorkList(W, ConstValues, /*IsArrayOfConstRegions*/ true, - TopLevelConstRegions); + populateWorkList(W, Values, TopLevelRegions); W.RunWorkList(); |

