| Age | Commit message (Collapse) | Author |
|---|
|
* Add unittest to check that the `Assignment` class can evaluate
expressions containing a `NotOptimizedExpr`.
* Fix the `AssignmentTest.FoldNotOptimized` unit test by
teaching the `ExprEvaluator` to fold `NotOptimizedExpr` nodes.
|
|
|
|
The address of KLEE-internal data structures should not influence the
order arrays are printed out.
Order arrays by name.
|
|
a message stating this.
|
|
that it's possible to call it from gdb.
|
|
|
|
The implementation of the constructor calls a method on a ``ConstantExpr``
which means the type must be complete (i.e. a forward declaration of
``ConstantExpr`` is insufficient) which creates an unnecessary ordering
Dependency in ``Expr.h``.
|
|
the ``ParserImpl`` it wouldn't free allocated ``Identifier``s
|
|
Some of these leaks were introduced by the factory constructor for Array
objects (f049ff3bc04daead8c3bb9f06e89e71e2054c82a) but a few others have
been around for far longer.
This leak was fixed by introducing a ``ArrayCache`` object which has two
purposes
* Retains ownership of all created ``Array`` objects and destroys them when
the ``ArrayCache`` destructor is called.
* Mimic the caching behaviour for symbolic arrays that was introduced
by f049ff3bc04daead8c3bb9f06e89e71e2054c82a where arrays with the same
name and size get "uniqued".
The Executor now maintains a ``arrayCache`` member that it uses and
passes by pointer to objects that need to construct ``Array`` objects (i.e.
``ObjectState``). This way when the Executor is destroyed all the
``Array`` objects get freed which seems like the right time to do this.
For Kleaver the ``ParserImpl`` has a ``TheArrayCache`` member that is
used for building ``Array`` objects. This means that the Parser must
live as long as the built expressions will be used otherwise we will
have a use after free. I'm not sure this is the right design choice.
It might be better to transfer ownership of the ``Array`` objects to
the root ``Decl`` returned by the parser.
|
|
The overloaded assignment operator previously only deleted the head
``UpdateNode`` if the ``UpdateList`` had exclusive ownership which left the remaining
list of ``UpdateNode``s dangling if those nodes had ``refCount`` of 1.
To fix this the logic that was previously in the ``UpdateList`` destructor
for deleting nodes that were exclusively referenced by the UpdateList
has been moved into ``UpdateList::tryFreeNodes()`` so that it can be
called from ``UpdateList::operator=()``.
It looks like this bug has been in KLEE since the beginning.
|
|
always goes to zero (matches LLVM's APInt::ashr(...)). This is meant
to partially address issue #218.
There are a few problems with this commit
* It is possible for AShrExpr to not be abbreviated because the scan
methods will not see that we print the 0th child of the AShrExpr twice
* The added test case should really be run through an SMT solver (
i.e. STP) but that requires infrastructure changes.
|
|
the optimisation that rewrites existing constraints when an equality with a constant is added
|
|
patch.
|
|
holycrap872-ArrayFactory
|
|
The way that Arrays were handled in the past led to the possibility of
aliasing issues. This occured whenever a new branch discovered an array
for the first time. Each branch would create a new instance of the same
array without seeing if it had been created before. Therefore, should a
new branch encounter the same state as some previous branch, the
previous branch's solution wouldn't satisfy the new state since they
didn't recognize they were referencing the same array. By creating an
array factory that creates a single symbolic array, that problem is
handled. Note: Concrete arrays should not be created by the factory
method since their values are never shared between branches.
The factory works by seeing if an array with a similar hash has been
created before (the hash is based on the name and size of array). If
there has been it then searches through all of the arrays with the same
hash (stored in a vector) to see if there is one with an exact match.
If there is one, the address of this previously created equivalent
array is returned. Otherwise, the newly created array is unique, it is
added to the map, and it's address is returned.
This aliasing issue can be seen by comparing the output of the
Dogfood/ImmutableSet.cpp test cases with and with out this commit.
Both act correctly, but the number of queries making it to the solver
in the previous version is much greater 244 vs 211. This is because
the UBTree in the CexCachingSolver and the cache in the CachingSolver
do not recognize queries whose solutions were previously calculated
because it doesn't think the arrays in the two queries are the same.
While this does not cause an error, it does mean that extra calls are
made.
|
|
than writing "(not (= a b))". This makes the code simpler and queries
slightly simpler.
|
|
ExprSMTLIBPrinter
|
|
|
|
|
|
This patch introduces nested let-abbreviations in the ExprSMTLIBPrinter
to reduce the size of the SMTLIBv2 queries and the corresponding processing
time (bugfix for #170).
The current implementation of the let abbreviation mode does not consider
expression intra-dependencies and prints all abbreviations in the same
let scope. For a (simplified) example, it prints
(assert (let ( (?B1 (A + B)) (?B2 (A + B + C)) ) (= ?B1 ?B2) ) ).
This is extremely inefficient if the expressions (and there many of these!)
extensively reuse their subexpressions. Therefore, it's better to print
the query with nested let-expressions by reusing existing expression bindings
in the new let scope:
(assert (let ( (?B1 (A + B)) ) (let ( (?B2 (?B1 + C)) ) (= ?B1 ?B2) ) ) ).
This patch adds a new function ExprSMTLIBPrinter::scanBindingExprDeps() that
scans bindings for expression dependencies. The result is a vector of
new bindings (orderedBindings) that represents the expression dependency tree.
When printing in the let-abbreviation mode, the new code starts with
abbreviating expressions that have no dependencies and then gradually makes
these new bindings available in the upcoming let-scopes where expressions
with dependencies reuse them.
The effect of nested let-abbreviations is comparable to :named abbreviations.
However, the latter mode is not supported by the majority of the solvers.
|
|
|
|
|
|
single method with two different implementations.
There is one version of this method for human readability
(printHumanReadableQuery()) and a version for machine consumption
(printMachineReadableQuery()).
The reason for having two versions is because different behaviour is
needed in different scenarios
* In machine readable mode the entire query is printed inside a single
``(assert ...)``. This is done to allow ``(let ...)`` to abbreviate
as much as possible.
* In human readable mode each constraint and query expression is printed
inside its own ``(assert ...)`` unless the abbreviation mode is
ABBR_LET in which case all constraints and query expr are printed
inside a single ``(assert ...)`` much like in the machine readable mode
Whilst I was here I also fixed a bug handling identation when printing
``(let ...)`` expressions in printAssert()
|
|
* Set the default abbreviation mode to let (ExprSMTLIBPrinter::ABBR_LET)
* Remove the now defunct ExprSMTLIBLetPrinter
* Improve performance of ExprSMTLIBPrinter::scan() by keeping
track of visited Expr to avoid visiting them again
* Rename ExprSMTLIBPrinter::printQuery() to ExprSMTLIBPrinter::printQueryExpr()
|
|
|
|
|
|
iostream injects static constructor function into every compilation unit.
Remove this to avoid it.
|
|
According to LLVM: lightweight and simpler implementation of streams.
|
|
This now corresponds to the sorts of the operations we emit, as far as I
can tell.
Read is one example of an operation that now works correctly (with 1-bit
array ranges).
It's also possible (but not very useful, and I don't think KLEE can
produce it) for other operations such as Add to operate on 1-bit values,
and this patch also fixes those.
|
|
lists can have NULL roots, e.g. in MemoryObject instances with concrete
contents, where root is allocated lazily only when the updates are required).
Also checking whether array updates are typed correctly in UpdateList::extend()
rather than in the constructor of UpdateNode (only for update lists with
non-NULL roots).
|
|
|
|
This change makes it possible to more reliably write unit tests which check
that an expression is equivalent to an expected pretty printed string.
|
|
(alphabetical) order.
|
|
|
|
|
|
|
|
Make KLEE compile with LLVM 2.3.
|
|
|
|
Major changes are:
- Switching to llvm-link to build archive files
- Use GetMallocUsage instead of GetTotalMemoryUsage (be aware of bug in
LLVM 3.3 http://llvm.org/bugs/show_bug.cgi?id=16847)
- intrinsic library functions like memcpy/mov/set use weak linkage to be
replaced by e.g. uclibc functions
- rewrote linking with library
- enhanced MemoryLimit test case to check if mallocs were successful
|
|
NotExpr::computeHash() will have a local variable with the name
"hashValue" and assign the newly computed hash to that instead of the
member variable with the same name that should be set by the
computeHash method of every Expr subclass."
git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@186102 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
negateQueryExpression() to make it clear what it does."
git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@181445 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@167382 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
SMTLIB format (part of his MSc project work).
git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@166556 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
it can be used by other classes. It has also been improved so it can
be used with the soon to be added ExprSMTLIBPrinter classes."
git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@166555 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
optional radix (base e.g. 2,10,16). This will be needed by the
ExprSMTLIBPrinter that will soon be added."
git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@166553 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
arrays from the Array and UpdateNode classes.
git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@166214 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
Patch by arrowdodger!
git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@154237 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@142310 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
recent changes to array names. Modified FastCexSolver.pc to catch
this issue.
git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@135896 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
version codes. This makes the preprocessor-based version tests more
concise and less error prone.
Also, fix the version tests in lib/Expr/Parser.cpp (immutable zext
and trunc were introduced in LLVM 2.9); now 2.9 passes "make test".
git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@135583 91177308-0d34-0410-b5e6-96231b3b80d8
|
