Add bitwise refinement mode for IAND (#5328)
authormakaimann <makaim@stanford.edu>
Mon, 7 Dec 2020 21:39:15 +0000 (13:39 -0800)
committerGitHub <noreply@github.com>
Mon, 7 Dec 2020 21:39:15 +0000 (22:39 +0100)
commite7caa82b1def3cab78a95b38841242264124efe7
tree5a05c7f7341c1fd068ec8eb143c9ac4f954878a3
parentc94d59516c62b481c7984830cf26753af16100a8
Add bitwise refinement mode for IAND (#5328)

Adds an option to do "bitwise" comparisons in the lazy IAND solver. Instead of creating an exact match for the value of a term using a sum, this would lazily fix groups of bits using integer extracts (divs and mods) when the abstract and concrete values differ at those bits.

For example, with a 1-bit granularity, you might learn a lemma like:

((_ iand 4) x y), value = 1
  actual (2, 3) = 2
  bv-value = #b0001
  bv-actual (#b0010, #b0011) = #b0010
IAndSolver::Lemma: (let ((_let_1 ((_ iand 4) x y)))
         (and (and true
                  (= (mod _let_1 2) (ite (and (= (mod x 2) 1) (= (mod y 2) 1)) 1 0)))
                  (= (mod (div _let_1 2) 2) (ite (and (= (mod (div x 2) 2) 1) (= (mod (div y 2) 2) 1)) 1 0))))
        ; BITWISE_REFINE

which is just forcing the bottom two bits of the iand operator result to implement bitwise-AND semantics.
17 files changed:
src/CMakeLists.txt
src/preprocessing/passes/bv_to_int.cpp
src/preprocessing/passes/bv_to_int.h
src/theory/arith/inference_id.cpp
src/theory/arith/inference_id.h
src/theory/arith/inference_manager.cpp
src/theory/arith/inference_manager.h
src/theory/arith/nl/iand_solver.cpp
src/theory/arith/nl/iand_solver.h
src/theory/arith/nl/iand_table.cpp [deleted file]
src/theory/arith/nl/iand_table.h [deleted file]
src/theory/arith/nl/iand_utils.cpp [new file with mode: 0644]
src/theory/arith/nl/iand_utils.h [new file with mode: 0644]
test/regress/regress1/nl/iand-native-1.smt2
test/regress/regress1/nl/iand-native-2.smt2
test/regress/regress1/nl/iand-native-granularities.smt2 [new file with mode: 0644]
test/regress/regress3/bv_to_int_check_bvsgt_bvlshr0_4bit.smt2.minimized.smt2