aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/SymbolManager.cpp
AgeCommit message (Collapse)Author
2010-01-25Split libAnalysis into two libraries: libAnalysis and libChecker.Ted Kremenek
(1) libAnalysis is a generic analysis library that can be used by Sema. It defines the CFG, basic dataflow analysis primitives, and inexpensive flow-sensitive analyses (e.g. LiveVariables). (2) libChecker contains the guts of the static analyzer, incuding the path-sensitive analysis engine and domain-specific checks. Now any clients that want to use the frontend to build their own tools don't need to link in the entire static analyzer. This change exposes various obvious cleanups that can be made to the layout of files and headers in libChecker. More changes pending. :) This change also exposed a layering violation between AnalysisContext and MemRegion. BlockInvocationContext shouldn't explicitly know about BlockDataRegions. For now I've removed the BlockDataRegion* from BlockInvocationContext (removing context-sensitivity; although this wasn't used yet). We need to have a better way to extend BlockInvocationContext (and any LocationContext) to add context-sensitivty. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@94406 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-14Fix: <rdar://problem/7468209> SymbolManager::isLive() should not crash on ↵Ted Kremenek
captured block variables that are passed by reference git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@91348 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-04Replace SymbolReaper::isLive(VarDecl) with SymbolReaper::isLive(VarRegion).Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@90582 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-09Remove tabs, and whitespace cleanups.Mike Stump
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@81346 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-02Replace uses of ImmutableSet in SymbolReaper with DenseSet. This wasTed Kremenek
motivated from Shark profiles that shows that 'markLive' was very heavy when using --analyzer-store=region. On my benchmark file, this reduces the analysis time for --analyzer-store=region from 19.5s to 13.5s and for --analyzer-store=basic from 5.3s to 3.5s. For the benchmark file, this is a reduction of about 30% analysis time for both analysis modes (a huge win). git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@80765 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-01This is a fairly large patch, which resulted from a cascade of changesTed Kremenek
made to RegionStore (and related classes) in order to handle some analyzer failures involving casts and manipulation of symbolic memory. The root of the change is in StoreManager::CastRegion(). Instead of using ad hoc heuristics to decide when to layer an ElementRegion on a casted MemRegion, we now always layer an ElementRegion when the cast type is different than the original type of the region. This carries the current cast information associated with a region around without resorting to the error prone recording of "casted types" in GRState. Along with this new policy of layering ElementRegions, I added a new algorithm to strip away existing ElementRegions when they simply represented casts of a base memory object. This algorithm computes the raw "byte offset" that an ElementRegion represents from the base region, and allows the new ElementRegion to be based off that offset. The added benefit is that this naturally handles a series of casts of a MemRegion without building up a set of redundant ElementRegions (thus canonicalizing the region view). Other related changes that cascaded from this one (as tests were failing in RegionStore): - Revamped RegionStoreManager::InvalidateRegion() to completely remove all bindings and default values from a region and all subregions. Now invalidated fields are not bound directly to new symbolic values; instead the base region has a "default" symbol value from which "derived symbols" can be created. The main advantage of this approach is that it allows us to invalidate a region hierarchy and then lazily instantiate new values no matter how deep the hierarchy went (i.e., regardless of the number of field accesses, e.g. x->f->y->z->...). The previous approach did not do this. - Slightly reworked RegionStoreManager::RemoveDeadBindings() to also incorporate live symbols and live regions that do not have direct bindings but also have "default values" used for lazy instantiation. The changes to 'InvalidateRegion' revealed that these were necessary in order to achieve lazy instantiation of values in the region store with those bindings being removed too early. - The changes to InvalidateRegion() and RemoveDeadBindings() revealed a serious bug in 'getSubRegionMap()' where not all region -> subregion relationships involved in actually bindings (explicit and implicit) were being recorded. This has been fixed by using a worklist algorithm to iteratively fill in the region map. - Added special support to RegionStoreManager::Bind()/Retrieve() to handle OSAtomicCompareAndSwap in light of the new 'CastRegion' changes and the layering of ElementRegions. - Fixed a bug in SymbolReaper::isLive() where derived symbols were not being marked live if the symbol they were derived from was also live. This fix was critical for getting lazy instantiation in RegionStore to work. - Tidied up the implementation of ValueManager::getXXXSymbolVal() methods to use SymbolManager::canSymbolicate() to decide whether or not a symbol should be symbolicated. - 'test/Analysis/misc-ps-xfail.m' now passes; that test case has been moved to 'test/Analysis/misc-ps.m'. - Tweaked some pretty-printing of MemRegions, and implemented 'ElementRegion::getRawOffset()' for use with the CastRegion changes. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@77782 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-29canSymbolicate() should only return true for integer types that are scalars.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@77479 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-15Introduced the notion of a "derived symbol" using the class SymbolDerived.Ted Kremenek
SymbolDerived allows us to model symbolic values that are related to other symbols via a region hierarchy. For example, SymbolDerived can be used to model individual values of a symbolic array. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@75728 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-13Change pretty-printing API for SymExprs and MemRegions to use a naming ↵Ted Kremenek
convention and style similar to other elements in Clang. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@75548 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Remove uses of std::ostream from libAnalysis.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@74136 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-19A further step of r73690: associate the cast-to type with the created symbol,Zhongxing Xu
because the type of the symbol is used to create the default range. We need the sign to be consistent. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@73756 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-09Rename:Zhongxing Xu
SymbolRegionRValue => SymbolRegionValue SymExpr::RegionRValue => SymExpr::RegionValueKind git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@71322 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-09As discussed with Ted, rename TypedRegion::getObjectType() to Zhongxing Xu
TypedRegion::getValueType(). git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@71321 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-09rename: MemRegion:Zhongxing Xu
RValueType => ObjectType LValueType => LocationType No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@71304 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-26analyzer infrastructure: make a bunch of changes to symbolic expressions thatTed Kremenek
Zhongxing and I discussed by email. Main changes: - Removed SymIntConstraintVal and SymIntConstraint - Added SymExpr as a parent class to SymbolData, SymSymExpr, SymIntExpr - Added nonloc::SymExprVal to wrap SymExpr - SymbolRef is now just a typedef of 'const SymbolData*' - Bunch of minor code cleanups in how some methods were invoked (no functionality change) This changes are part of a long-term plan to have full symbolic expression trees. This will be useful for lazily evaluating complicated expressions. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@67731 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-25This patch adds two more SymbolData subclasses: SymIntExpr and SymSymExpr, forZhongxing Xu
representing symbolic expressions like 'x'+3 and 'x'+'y'. The design is subjected to change later when we fix the class hierarchy of symbolic expressions. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@67678 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-23analyzer: Fix embarrassing regression in BasicStore when invalidating structTed Kremenek
values passed-by-reference to unknown functions. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@67519 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-20GRExprEngine:Ted Kremenek
- Conjure symbols at '--' and '++' unary operations - Add utility method SVal::GetConjuredSymbolVal() and constify some arguments along the way. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@67395 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-04Add an optional "tag" to conjured symbols that allows us to distinguish betweenTed Kremenek
multiple symbols conjured at the same location. All that is required of the tag is that it is a fixed void* value that points to an memory address that remains valid throughout the remainder of the lifetime of the SymbolManager. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@66092 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-03Rework use of loc::SymbolVal in the retain/release checker to use the new methodTed Kremenek
SVal::getAsLocSymbol(). This simplifies the code and allows the retain/release checker to (I believe) also correctly reason about location symbols wrapped in SymbolicRegions. Along the way I cleaned up SymbolRef a little, disallowing implicit casts to 'unsigned'. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@65972 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-14Added GRStateManager::scanReachableSymbols(), a method which scans the reachableTed Kremenek
symbols from an SVal. - Fixed a bug in EnvironmentManager::RemoveDeadBindings() where it did not mark live all the symbols reachable from a live block-level expression. - Fixed a bug in the retain/release checker where it did not stop tracking symbols that 'escaped' via compound literals being assigned to something the BasicStoreManager didn't reason about. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@64534 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-22SymbolReaper::isLive(SymbolRef) now always returns true for ↵Ted Kremenek
SymbolRegionRvalues because these represent the symbolic values for parameters/globals upon entry to the function. These values are always ;live' because they represent constraints on the context of how the function was called. This will be useful for both summary generation but is also necessary to get RegionStore's lazy-binding of locations to symbols to work in practice with RemoveDeadBindings. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@62771 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-22Static analyzer: Remove a bunch of outdated SymbolData objects andTed Kremenek
their associated APIs. We no longer need separate SymbolData objects for fields, variables, etc. Instead, we now associated symbols with the "rvalue" of a MemRegion (i.e., the value stored at that region). Now we only have two kinds of SymbolData objects: SymbolRegionRValue and SymbolConjured. This cleanup also makes the distinction between a SymbolicRegion and a symbolic value that is a location much clearer. A SymbolicRegion represents a chunk of symbolic memory, while a symbolic location is just a "pointer" with different possible values. Without any specific knowledge, a symbolic location resolves (i.e., via a dereference) to a SymbolicRegion. In the future, when we do better alias reasoning, a symbolic location can become an alias for another location, thus merging the constraints on the referred SymbolicRegion with the other region. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@62769 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-21Static Analyzer: Replace LiveSymbols/DeadSymbols sets with a new object ↵Ted Kremenek
called "SymbolReaper". Right now it just consolidates the two and cleans up some client code, but shortly it will be used to enable "lazy computation" of live symbols for use with RegionStore. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@62722 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-15Fix some unused variable, control reaches end of non-void function,Daniel Dunbar
and uninitialized use options. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@62270 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-20Lazy bingding for region-store manager.Zhongxing Xu
* Now Bind() methods take and return GRState* because binding could also alter GDM. * No variables are initialized except those declared with initial values. * failed C test cases are due to bugs in RemoveDeadBindings(), which removes constraints that is still alive. This will be fixed in later patch. * default value of array and struct regions will be implemented in later patch. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@61274 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-05Add SymbolRef::print() and have SymbolicRegion::print() use this method ↵Ted Kremenek
instead of calling SymbolRef::getNumber(). git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@60578 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-05Rename SymbolID to SymbolRef. This is a precursor to some overhauling of ↵Ted Kremenek
the representation of symbolic values. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@60575 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-05Remove SymbolDataContentsOf (unused).Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@60572 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-19Add SymbolData for array elements and struct fields.Zhongxing Xu
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@59618 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-12Conjured symbols now bind to Stmt* instead of Expr*.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@59154 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-01Add a QualType to ConjuredSymbol to represent the type and size of the symbol.Ted Kremenek
Use this updated interface when invalidating arguments passed by reference; the type of symbol is of the object passed by reference, not the reference itself. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@56894 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-13Initialize tracked local variables to undefined.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@54716 91177308-0d34-0410-b5e6-96231b3b80d8
2008-03-15Make a major restructuring of the clang tree: introduce a top-levelChris Lattner
lib dir and move all the libraries into it. This follows the main llvm tree, and allows the libraries to be built in parallel. The top level now enforces that all the libs are built before Driver, but we don't care what order the libs are built in. This speeds up parallel builds, particularly incremental ones. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@48402 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-30 12:24:09 +0000