Field sensitive goto-symex#2574
Conversation
|
+1 #doeswant |
src/goto-symex/field_sensitivity.cpp
Outdated
| Forall_operands(it, expr) | ||
| operator()(ns, *it, write); | ||
|
|
||
| if(expr.id()==ID_symbol && |
src/goto-symex/field_sensitivity.cpp
Outdated
| bool write) const | ||
| { | ||
| #if 1 | ||
| if(expr.id()!=ID_address_of) |
There was a problem hiding this comment.
Comment here why address-of is special?
src/goto-symex/field_sensitivity.cpp
Outdated
| { | ||
| member_exprt &member=to_member_expr(expr); | ||
|
|
||
| if(member.struct_op().id()==ID_symbol && |
src/goto-symex/field_sensitivity.cpp
Outdated
|
|
||
| member.struct_op()=tmp.get_original_expr(); | ||
|
|
||
| tmp.type()=member.type(); |
There was a problem hiding this comment.
Does tmp retain any aspect of the original struct-op here?
src/goto-symex/field_sensitivity.cpp
Outdated
| ++it, ++number) | ||
| { | ||
| member_exprt member_rhs(lhs, it->get_name(), it->type()); | ||
| exprt member_lhs=lhs_fs.operands()[number]; |
src/goto-symex/field_sensitivity.cpp
Outdated
| for(unsigned i=0; i<array_size_u; ++i) | ||
| { | ||
| index_rhs.index()=from_integer(i, index_type()); | ||
| exprt index_lhs=lhs_fs.operands()[i]; |
src/goto-symex/field_sensitivity.cpp
Outdated
| field_assignments_rec(ns, state, target, member_lhs, member_rhs); | ||
| } | ||
| } | ||
| else if(followed_type.id()==ID_array) |
There was a problem hiding this comment.
Worth retaining the ability to represent a whole-array assignment compactly? String constants are the main thing that springs to mind -- then break it down into smaller pieces once the program starts making individual array cell assignments?
src/goto-symex/symex_assign.cpp
Outdated
| tmp_ssa_rhs.swap(ssa_rhs); | ||
| } | ||
|
|
||
| state.field_sensitivity(ns, ssa_rhs, false); |
There was a problem hiding this comment.
Unclear whether this does anything or just accrues state -- give the function name a verb
src/goto-symex/field_sensitivity.cpp
Outdated
|
|
||
| Purpose: | ||
|
|
||
| \*******************************************************************/ |
src/goto-symex/field_sensitivity.cpp
Outdated
| dest=struct_exprt(ssa_expr.type()); | ||
| dest.reserve_operands(components.size()); | ||
|
|
||
| for(struct_union_typet::componentst::const_iterator |
src/goto-symex/field_sensitivity.cpp
Outdated
| const struct_union_typet::componentst &components= | ||
| type.components(); | ||
|
|
||
| assert(components.empty() || |
src/goto-symex/field_sensitivity.cpp
Outdated
| (lhs_fs.has_operands() && | ||
| lhs_fs.operands().size()==components.size())); | ||
|
|
||
| unsigned number=0; |
src/goto-symex/field_sensitivity.cpp
Outdated
| for(exprt::operandst::const_iterator it=lhs.operands().begin(); | ||
| it!=lhs.operands().end(); | ||
| ++it, ++fs_it) | ||
| field_assignments_rec(ns, state, target, *fs_it, *it); |
src/goto-symex/field_sensitivity.cpp
Outdated
| mp_integer array_size; | ||
| if(to_integer(type.size(), array_size)) | ||
| assert(false); | ||
| unsigned array_size_u=integer2unsigned(array_size); |
src/goto-symex/field_sensitivity.cpp
Outdated
| exprt &expr, | ||
| bool write) const | ||
| { | ||
| #if 1 |
There was a problem hiding this comment.
Shall we have command line options to turn on/off field-sensitivity for structs/arrays to make it easier to perform experiments with it?
src/goto-symex/symex_assign.cpp
Outdated
| } | ||
| #endif | ||
|
|
||
| std::cerr << from_expr(ns, "", ssa_rhs) << std::endl; |
| ^EXIT=0$ | ||
| ^SIGNAL=0$ | ||
| ^VERIFICATION SUCCESSFUL$ | ||
| \(Starting CEGAR Loop\|VCC(s), 0 remaining after simplification$\) |
There was a problem hiding this comment.
What is the CEGAR Loop here? ^^
src/goto-symex/symex_assign.cpp
Outdated
|
|
||
| ssa_exprt lhs_mod=lhs; | ||
|
|
||
| if(ssa_rhs.id()==ID_byte_update_little_endian || |
There was a problem hiding this comment.
Is there a test that triggers this case?
ad814f9 to
d5b7a9b
Compare
src/goto-symex/symex_assign.cpp
Outdated
|
|
||
| do_simplify(ssa_rhs); | ||
|
|
||
| ssa_exprt ssa_lhs=lhs; |
There was a problem hiding this comment.
| ssa_exprt ssa_lhs=lhs; | |
| ssa_exprt ssa_lhs = lhs_mod; |
This makes regression/cbmc/Anonymous_Struct2 pass, and a few others.
src/goto-symex/field_sensitivity.h
Outdated
| /// \param ns: a namespace to resolve type symbols/tag types | ||
| /// \param state: symbolic execution state | ||
| /// \param target: symbolic execution equation store | ||
| /// \param lhs_f: expanded symbol |
src/goto-symex/goto_symex_state.cpp
Outdated
| (!ns.lookup(obj_identifier).is_shared() && !(dirty)(obj_identifier))) | ||
| return false; | ||
|
|
||
| // is it an indivisible object being accessed? |
There was a problem hiding this comment.
Comment here on why in that case the rest of this function is inapplicable
d5b7a9b to
0bfb212
Compare
0bfb212 to
705eaeb
Compare
2b6ea5c to
04ad940
Compare
romainbrenguier
left a comment
There was a problem hiding this comment.
I've only partially reviewed the first commit and I think it should be split into several commits.
Ensure ssa_expr's l1-identifier is consistent with its identifier [blocks: #2574]
fda57d0 to
1708b90
Compare
allredj
left a comment
There was a problem hiding this comment.
This PR failed Diffblue compatibility checks (cbmc commit: 1708b90).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/106352811
Status will be re-evaluated on next push.
Common spurious failures include: the cbmc commit has disappeared in the mean time (e.g. in a force-push); the author is not in the list of contributors (e.g. first-time contributors); compatibility was already broken by an earlier merge.
allredj
left a comment
There was a problem hiding this comment.
✔️
Passed Diffblue compatibility checks (cbmc commit: 5a5be49).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/106386612
allredj
left a comment
There was a problem hiding this comment.
✔️
Passed Diffblue compatibility checks (cbmc commit: ec20a71).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/106426448
allredj
left a comment
There was a problem hiding this comment.
This PR failed Diffblue compatibility checks (cbmc commit: fbf7d7f).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/107048557
Status will be re-evaluated on next push.
Common spurious failures include: the cbmc commit has disappeared in the mean time (e.g. in a force-push); the author is not in the list of contributors (e.g. first-time contributors); compatibility was already broken by an earlier merge.
allredj
left a comment
There was a problem hiding this comment.
✔️
Passed Diffblue compatibility checks (cbmc commit: 78f75c7).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/107051561
allredj
left a comment
There was a problem hiding this comment.
This PR failed Diffblue compatibility checks (cbmc commit: b38a424).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/107119069
Status will be re-evaluated on next push.
Common spurious failures include: the cbmc commit has disappeared in the mean time (e.g. in a force-push); the author is not in the list of contributors (e.g. first-time contributors); compatibility was already broken by an earlier merge.
allredj
left a comment
There was a problem hiding this comment.
This PR failed Diffblue compatibility checks (cbmc commit: 28293c7).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/107327902
Status will be re-evaluated on next push.
Common spurious failures include: the cbmc commit has disappeared in the mean time (e.g. in a force-push); the author is not in the list of contributors (e.g. first-time contributors); compatibility was already broken by an earlier merge.
allredj
left a comment
There was a problem hiding this comment.
This PR failed Diffblue compatibility checks (cbmc commit: 7f16d25).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/107604152
Status will be re-evaluated on next push.
Common spurious failures include: the cbmc commit has disappeared in the mean time (e.g. in a force-push); the author is not in the list of contributors (e.g. first-time contributors); compatibility was already broken by an earlier merge.
allredj
left a comment
There was a problem hiding this comment.
This PR failed Diffblue compatibility checks (cbmc commit: 4c23625).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/107608202
Status will be re-evaluated on next push.
Common spurious failures include: the cbmc commit has disappeared in the mean time (e.g. in a force-push); the author is not in the list of contributors (e.g. first-time contributors); compatibility was already broken by an earlier merge.
allredj
left a comment
There was a problem hiding this comment.
✔️
Passed Diffblue compatibility checks (cbmc commit: 092d8fb).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/107795688
allredj
left a comment
There was a problem hiding this comment.
✔️
Passed Diffblue compatibility checks (cbmc commit: 5b86aba).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/108113827
allredj
left a comment
There was a problem hiding this comment.
✔️
Passed Diffblue compatibility checks (cbmc commit: 098c0cb).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/108161278
allredj
left a comment
There was a problem hiding this comment.
✔️
Passed Diffblue compatibility checks (cbmc commit: 9329cc2).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/108198940
allredj
left a comment
There was a problem hiding this comment.
✔️
Passed Diffblue compatibility checks (cbmc commit: 5dd0b3a).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/108226499
field_sensitivity::apply needs to avoid expanding struct-typed symbols into fields when they're being used as lvalues.
Struct member and array index expressions are replaced by new SSA symbols such that updates to individual fields of structs or arrays do not affect the SSA index of the remaining object. This enables more fine-grained constant propagation, which should be particularly beneficial to Java (where structs/classes prevail).
The Array_Propagation1 test is no longer solved during symex in this case.
This makes it easier to read the difference between an atomic symbol and a field of a composite.
Previously this could turn e.g. struct@x#y into struct.field@x#y, regardless of whether the L2 generation #y for that field existed or not. This meant that when an L2 name was passed through field-sensitivity expansion it could end up referring to an unbound symbol, whereas an L1 name would remain coherent (e.g. struct@x -> struct.field@x), later being renamed using the ordinary level2_names map. That means the generation numbers for structs and their fields may get out of sync, but that should be harmless so long as "latest generation" is used consistently. We can now also remove constant propagator lookup after applying field sensitivity, because field_sensitivity::apply uses state.rename to apply L2 renaming, which itself consults the constant propagator. Also make is_divisible test cheaper, at the expense that synchronisation with get_fields needs to be maintained manually.
This is because a pointer into the middle of a struct can resolve into something like &struct.field, in which case we need to rewrite that as the field-sensitive SSA symbol before any further dereferencing.
…updated
Otherwise e.g. in "memset2" we had the whole object being initialised
with "{0, 0}" (which is stored in const prop and then expanded to
individual fields), then later any operation that needed the
whole-struct representation (such as the memset-of-one-field in that
test, which expanded to "whole_struct = byte_update(whole_struct,
offset, int, 0)") would get the whole-struct definition stored in
const-prop, disregarding any intermediate updates that were able to
directly reference a single field.
This avoids having two different versions of a symbol (the
field-of-composite and the indivisible field versions) in the most
direct way possible.
…mations The function name was previously incorrect (it did more than it said), so now I just call both transformations from symex_assign.
Otherwise while everything works correctly for the state, the target sees the field expansions before the composite definition, which is a problem if the values are non-constant and so the expansion RHSes refer to the composite!
…s already L2
For an L1 or lower expression, get_fields already recursed, e.g. to turn
`x` -> `{ { x..a..g, x..a..h }, x..b }` rather than `{ x..a, a..b }`
when its `a` member is itself struct-typed. However this recursion was
omitted in the case where the input expression is already L2 renamed.
allredj
left a comment
There was a problem hiding this comment.
✔️
Passed Diffblue compatibility checks (cbmc commit: 8cd443c).
Build URL: https://travis-ci.com/diffblue/test-gen/builds/108538361

This is the rebased version of an old patch collection. It's likely broken at present, but should be a starting point for discussing and evaluating this.@smowton Has put a lot of work into this, and this PR now reflects our combined effort. It is now ready for review.