summaryrefslogtreecommitdiffstats
path: root/clang/lib/Analysis/SymbolManager.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Split libAnalysis into two libraries: libAnalysis and libChecker.Ted Kremenek2010-01-251-228/+0
| | | | | | | | | | | | | | | | | | | | | | | | | (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. llvm-svn: 94406
* Fix: <rdar://problem/7468209> SymbolManager::isLive() should not crash on ↵Ted Kremenek2009-12-141-1/+2
| | | | | | captured block variables that are passed by reference llvm-svn: 91348
* Replace SymbolReaper::isLive(VarDecl) with SymbolReaper::isLive(VarRegion).Ted Kremenek2009-12-041-0/+4
| | | | llvm-svn: 90582
* Remove tabs, and whitespace cleanups.Mike Stump2009-09-091-31/+31
| | | | llvm-svn: 81346
* Replace uses of ImmutableSet in SymbolReaper with DenseSet. This wasTed Kremenek2009-09-021-4/+4
| | | | | | | | | | | 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). llvm-svn: 80765
* This is a fairly large patch, which resulted from a cascade of changesTed Kremenek2009-08-011-1/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 77782
* canSymbolicate() should only return true for integer types that are scalars.Ted Kremenek2009-07-291-1/+1
| | | | llvm-svn: 77479
* Introduced the notion of a "derived symbol" using the class SymbolDerived.Ted Kremenek2009-07-151-0/+28
| | | | | | | | 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. llvm-svn: 75728
* Change pretty-printing API for SymExprs and MemRegions to use a naming ↵Ted Kremenek2009-07-131-28/+15
| | | | | | convention and style similar to other elements in Clang. llvm-svn: 75548
* Remove uses of std::ostream from libAnalysis.Ted Kremenek2009-06-241-6/+0
| | | | llvm-svn: 74136
* A further step of r73690: associate the cast-to type with the created symbol,Zhongxing Xu2009-06-191-3/+6
| | | | | | | because the type of the symbol is used to create the default range. We need the sign to be consistent. llvm-svn: 73756
* Rename:Zhongxing Xu2009-05-091-9/+9
| | | | | | | SymbolRegionRValue => SymbolRegionValue SymExpr::RegionRValue => SymExpr::RegionValueKind llvm-svn: 71322
* As discussed with Ted, rename TypedRegion::getObjectType() to Zhongxing Xu2009-05-091-1/+1
| | | | | | TypedRegion::getValueType(). llvm-svn: 71321
* rename: MemRegion:Zhongxing Xu2009-05-091-1/+1
| | | | | | | | | RValueType => ObjectType LValueType => LocationType No functionality change. llvm-svn: 71304
* analyzer infrastructure: make a bunch of changes to symbolic expressions thatTed Kremenek2009-03-261-78/+117
| | | | | | | | | | | | | | | | 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. llvm-svn: 67731
* This patch adds two more SymbolData subclasses: SymIntExpr and SymSymExpr, forZhongxing Xu2009-03-251-0/+41
| | | | | | | | 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. llvm-svn: 67678
* analyzer: Fix embarrassing regression in BasicStore when invalidating structTed Kremenek2009-03-231-0/+4
| | | | | | values passed-by-reference to unknown functions. llvm-svn: 67519
* GRExprEngine:Ted Kremenek2009-03-201-1/+2
| | | | | | | | - Conjure symbols at '--' and '++' unary operations - Add utility method SVal::GetConjuredSymbolVal() and constify some arguments along the way. llvm-svn: 67395
* Add an optional "tag" to conjured symbols that allows us to distinguish betweenTed Kremenek2009-03-041-3/+4
| | | | | | | | 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. llvm-svn: 66092
* Rework use of loc::SymbolVal in the retain/release checker to use the new methodTed Kremenek2009-03-031-3/+17
| | | | | | | | | | | 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'. llvm-svn: 65972
* Added GRStateManager::scanReachableSymbols(), a method which scans the reachableTed Kremenek2009-02-141-1/+2
| | | | | | | | | | | | | 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. llvm-svn: 64534
* SymbolReaper::isLive(SymbolRef) now always returns true for ↵Ted Kremenek2009-01-221-1/+6
| | | | | | 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. llvm-svn: 62771
* Static analyzer: Remove a bunch of outdated SymbolData objects andTed Kremenek2009-01-221-99/+18
| | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 62769
* Static Analyzer: Replace LiveSymbols/DeadSymbols sets with a new object ↵Ted Kremenek2009-01-211-0/+18
| | | | | | 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. llvm-svn: 62722
* Fix some unused variable, control reaches end of non-void function,Daniel Dunbar2009-01-151-2/+2
| | | | | | and uninitialized use options. llvm-svn: 62270
* Lazy bingding for region-store manager.Zhongxing Xu2008-12-201-2/+24
| | | | | | | | | | | | | * 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. llvm-svn: 61274
* Add SymbolRef::print() and have SymbolicRegion::print() use this method ↵Ted Kremenek2008-12-051-0/+5
| | | | | | instead of calling SymbolRef::getNumber(). llvm-svn: 60578
* Rename SymbolID to SymbolRef. This is a precursor to some overhauling of ↵Ted Kremenek2008-12-051-5/+5
| | | | | | the representation of symbolic values. llvm-svn: 60575
* Remove SymbolDataContentsOf (unused).Ted Kremenek2008-12-051-28/+1
| | | | llvm-svn: 60572
* Add SymbolData for array elements and struct fields.Zhongxing Xu2008-11-191-0/+35
| | | | llvm-svn: 59618
* Conjured symbols now bind to Stmt* instead of Expr*.Ted Kremenek2008-11-121-1/+1
| | | | llvm-svn: 59154
* Add a QualType to ConjuredSymbol to represent the type and size of the symbol.Ted Kremenek2008-10-011-4/+4
| | | | | | 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. llvm-svn: 56894
* Initialize tracked local variables to undefined.Ted Kremenek2008-08-131-1/+2
| | | | llvm-svn: 54716
* Make a major restructuring of the clang tree: introduce a top-levelChris Lattner2008-03-151-0/+124
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. llvm-svn: 48402
OpenPOWER on IntegriCloud