Fix: <rdar://problem/7468209> SymbolManager::isLive() should not crash on captured block variables that are passed by reference

llvm-svn: 91348

llvm-svn: 90582

llvm-svn: 81346

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

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

llvm-svn: 77479

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 convention and style similar to other elements in Clang.

llvm-svn: 75548

llvm-svn: 74136

because the type of the symbol is used to create the default range. We need the
sign to be consistent.

llvm-svn: 73756

  SymbolRegionRValue => SymbolRegionValue
  SymExpr::RegionRValue => SymExpr::RegionValueKind

llvm-svn: 71322

TypedRegion::getValueType().

llvm-svn: 71321

 RValueType => ObjectType
 LValueType => LocationType

No functionality change.

llvm-svn: 71304

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

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

values passed-by-reference to unknown functions.

llvm-svn: 67519

- Conjure symbols at '--' and '++' unary operations
- Add utility method SVal::GetConjuredSymbolVal() and constify some arguments
  along the way.

llvm-svn: 67395

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

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

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 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

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 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

and uninitialized use options.

llvm-svn: 62270

* 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 instead of calling SymbolRef::getNumber().

llvm-svn: 60578

Rename SymbolID to SymbolRef.  This is a precursor to some overhauling of the representation of symbolic values.

llvm-svn: 60575

llvm-svn: 60572

llvm-svn: 59618

llvm-svn: 59154

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

llvm-svn: 54716

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

Changed CallRetValSymbol to SymbolConjured to allow "conjured" symbols to be created for any expression, not just CallExprs.
Added experimental support for conjuring symbols during assingments where the RHS is "unknown".  This allows more value tracking for path-sensitivity.
Fixed bug in "assumption" logic when processing symbolic constraints; we would improperly mark constraints we didn't support as infeasible.

llvm-svn: 48306

llvm-svn: 48272

llvm-svn: 47995

Added recording of divide-by-zero and divide-by-uninitialized nodes.

llvm-svn: 47586

another symbolic value.

llvm-svn: 47339

their own [.cpp;.h] files.

llvm-svn: 47201