Skip to content

Fix verify errors on sv-benchmarks#827

Merged
sim642 merged 10 commits intomasterfrom
hoaredomain-new-bool-range
Sep 20, 2022
Merged

Fix verify errors on sv-benchmarks#827
sim642 merged 10 commits intomasterfrom
hoaredomain-new-bool-range

Conversation

@sim642
Copy link
Copy Markdown
Member

@sim642 sim642 commented Aug 23, 2022

This hopefully fixes all remaining ERROR (verify) results on sv-benchmarks (Full table).
It is on top of #809 since that causes significant changes to ERROR (verify) results.

Changes

  1. CilType.Exp.compare (and also CilType.Exp.equal) previously called CIL's Expcompare.compareExp to check for equality (confusingly not an int compare value) before falling back to the general compare logic implemented there.

    Expcompare.compareExp does some strange things though: it implements only few basic cases and falls back to trying to constant fold both arguments. Such logic is completely inconsistent with everything else in CilType.Exp, which doesn't do similar things for its own compare and hash logic, but which must have consistent behavior.

    In particular, this affected var_eq analysis's expression partition sets, which use compare. The problem is that in non-constant-fold-equal cases the ordering defined by our general logic doesn't account for the equivalences induced by constant folding for equality.

  2. All the verify errors in "ufo" benchmarks are about def_exc ranges for booleans. Under some unpredictable conditions, that range could unnecessarily worsen from [0,1] to [0,7].

    The problem seems to be GoblintCil.intKindForValue, which claims

    Return the smallest kind that will hold the integer's value.

    Except it doesn't always return the smallest kind: for 0 and 1 that should be IBool, not IUChar.

    Currently I made the fix in Goblint to quickly debug and benchmark the issue, but it should probably be ported over to CIL.

TODO

sim642 added 7 commits August 23, 2022 12:40
Expcompare.compareExp does additional transformations which are incompatible with the rest of compare.
This causes incorrect behavior in sets.
ValueDomain.determine_offset assumed CilType.Exp.equal would do constant folding in Expcompare.compareExp.
@sim642 sim642 added bug sv-comp SV-COMP (analyses, results), witnesses pr-dependency Depends or builds on another PR, which should be merged before labels Aug 23, 2022
@sim642 sim642 added this to the SV-COMP 2023 milestone Aug 23, 2022
@sim642 sim642 marked this pull request as ready for review August 24, 2022 07:32
@sim642
Copy link
Copy Markdown
Member Author

sim642 commented Sep 1, 2022

Merging of this depends on #809, which should also fix gobview properly.

Base automatically changed from hoaredomain-new to master September 20, 2022 11:34
@sim642 sim642 removed the pr-dependency Depends or builds on another PR, which should be merged before label Sep 20, 2022
@sim642 sim642 merged commit a20838e into master Sep 20, 2022
@sim642 sim642 deleted the hoaredomain-new-bool-range branch September 20, 2022 12:09
sim642 added a commit that referenced this pull request Sep 20, 2022
@sim642 sim642 mentioned this pull request Sep 29, 2022
6 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

bug sv-comp SV-COMP (analyses, results), witnesses

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants