From 42dd10f9936c6a9be158842f482cc7ebd4a972ed Mon Sep 17 00:00:00 2001 From: yoni206 Date: Wed, 14 Oct 2020 12:40:13 -0700 Subject: [PATCH] bv2int: implementing the iand-sum mode (#5265) There are 3 potential modes to lazily treat the iand operator: (1) by value (typical CEGAR loop) (2) by sum (lazily expanding each iand node into a sum of ITEs) (3) by bit-wise equalities (lazily expanding each iand node into bit-wise equalities) This PR implements (2). The relevant option is added to existing tests, and a new test is added. In a few other tests, some options are removed to make them run faster. --- src/theory/arith/inference_id.cpp | 1 + src/theory/arith/inference_id.h | 2 ++ src/theory/arith/nl/iand_solver.cpp | 17 ++++++++++++++++- src/theory/arith/nl/iand_solver.h | 9 +++++++++ src/theory/arith/nl/iand_table.cpp | 5 ++++- test/regress/CMakeLists.txt | 1 + test/regress/regress0/bv/bv_to_int1.smt2 | 3 --- test/regress/regress1/nl/iand-native-1.smt2 | 1 + test/regress/regress1/nl/iand-native-2.smt2 | 15 +++++++++++++++ test/regress/regress2/bv_to_int2.smt2 | 2 -- test/regress/regress2/bv_to_int_ashr.smt2 | 1 - test/regress/regress2/bv_to_int_bitwise.smt2 | 3 ++- test/regress/regress2/bv_to_int_bvmul1.smt2 | 2 -- .../regress2/bv_to_int_mask_array_1.smt2 | 3 ++- .../regress2/bv_to_int_mask_array_2.smt2 | 3 ++- ...check_bvsge_bvashr0_4bit.smt2.minimized.smt2 | 3 +-- ...check_bvsgt_bvlshr0_4bit.smt2.minimized.smt2 | 8 +++----- ...nt_input_mouser_detect.c.smt2.minimized.smt2 | 1 + 18 files changed, 60 insertions(+), 20 deletions(-) create mode 100644 test/regress/regress1/nl/iand-native-2.smt2 diff --git a/src/theory/arith/inference_id.cpp b/src/theory/arith/inference_id.cpp index a0dc19d81..a93a980ba 100644 --- a/src/theory/arith/inference_id.cpp +++ b/src/theory/arith/inference_id.cpp @@ -40,6 +40,7 @@ const char* toString(InferenceId i) case InferenceId::NL_T_TANGENT: return "T_TANGENT"; case InferenceId::NL_IAND_INIT_REFINE: return "IAND_INIT_REFINE"; case InferenceId::NL_IAND_VALUE_REFINE: return "IAND_VALUE_REFINE"; + case InferenceId::NL_IAND_SUM_REFINE: return "IAND_SUM_REFINE"; case InferenceId::NL_CAD_CONFLICT: return "CAD_CONFLICT"; case InferenceId::NL_CAD_EXCLUDED_INTERVAL: return "CAD_EXCLUDED_INTERVAL"; case InferenceId::NL_ICP_CONFLICT: return "ICP_CONFLICT"; diff --git a/src/theory/arith/inference_id.h b/src/theory/arith/inference_id.h index 1940e2ef3..c01cd2c8e 100644 --- a/src/theory/arith/inference_id.h +++ b/src/theory/arith/inference_id.h @@ -71,6 +71,8 @@ enum class InferenceId : uint32_t NL_IAND_INIT_REFINE, // value refinements (IAndSolver::checkFullRefine) NL_IAND_VALUE_REFINE, + // sum refinements (IAndSulver::checkFullRefine) + NL_IAND_SUM_REFINE, //-------------------- cad solver // conflict / infeasible subset obtained from cad NL_CAD_CONFLICT, diff --git a/src/theory/arith/nl/iand_solver.cpp b/src/theory/arith/nl/iand_solver.cpp index 954f921ce..30441a8f4 100644 --- a/src/theory/arith/nl/iand_solver.cpp +++ b/src/theory/arith/nl/iand_solver.cpp @@ -148,7 +148,10 @@ void IAndSolver::checkFullRefine() // ************* additional lemma schemas go here if (options::iandMode() == options::IandMode::SUM) { - // add lemmas based on sum mode + Node lem = sumBasedLemma(i); // add lemmas based on sum mode + Trace("iand-lemma") + << "IAndSolver::Lemma: " << lem << " ; SUM_REFINE" << std::endl; + d_im.addPendingArithLemma(lem, InferenceId::NL_IAND_SUM_REFINE, true); } else if (options::iandMode() == options::IandMode::BITWISE) { @@ -245,6 +248,18 @@ Node IAndSolver::valueBasedLemma(Node i) return lem; } +Node IAndSolver::sumBasedLemma(Node i) +{ + Assert(i.getKind() == IAND); + Node x = i[0]; + Node y = i[1]; + size_t bvsize = i.getOperator().getConst().d_size; + uint64_t granularity = options::BVAndIntegerGranularity(); + NodeManager* nm = NodeManager::currentNM(); + Node lem = nm->mkNode( + EQUAL, i, d_iandTable.createBitwiseNode(x, y, bvsize, granularity)); + return lem; +} } // namespace nl } // namespace arith diff --git a/src/theory/arith/nl/iand_solver.h b/src/theory/arith/nl/iand_solver.h index d74365784..e00cb92a9 100644 --- a/src/theory/arith/nl/iand_solver.h +++ b/src/theory/arith/nl/iand_solver.h @@ -22,6 +22,7 @@ #include "expr/node.h" #include "theory/arith/arith_state.h" #include "theory/arith/inference_manager.h" +#include "theory/arith/nl/iand_table.h" #include "theory/arith/nl/nl_lemma_utils.h" #include "theory/arith/nl/nl_model.h" @@ -88,6 +89,7 @@ class IAndSolver Node d_two; Node d_true; Node d_false; + IAndTable d_iandTable; /** IAND terms that have been given initial refinement lemmas */ NodeSet d_initRefine; /** all IAND terms, for each bit-width */ @@ -118,6 +120,13 @@ class IAndSolver * ((_ iand k) x y) = Rewriter::rewrite(((_ iand k) M(x) M(y))) */ Node valueBasedLemma(Node i); + /** + * Sum-based refinement lemma for i of the form ((_ iand k) x y). Returns: + * i = 2^0*min(x[0],y[0])+...2^{k-1}*min(x[k-1],y[k-1]) + * where x[i] is x div i mod 2 + * and min is defined with an ite. + */ + Node sumBasedLemma(Node i); }; /* class IAndSolver */ } // namespace nl diff --git a/src/theory/arith/nl/iand_table.cpp b/src/theory/arith/nl/iand_table.cpp index 12e06ed58..050e6baed 100644 --- a/src/theory/arith/nl/iand_table.cpp +++ b/src/theory/arith/nl/iand_table.cpp @@ -198,7 +198,7 @@ void IAndTable::addDefaultValue( } // compute the most common result - uint64_t most_common_result; + uint64_t most_common_result = 0; uint64_t max_num_of_occ = 0; for (uint64_t i = 0; i <= num_of_values; i++) { @@ -208,6 +208,9 @@ void IAndTable::addDefaultValue( most_common_result = i; } } + // sanity check: some value appears at least once. + Assert(max_num_of_occ != 0); + // -1 is the default case of the table. // add it to the table table[std::make_pair(-1, -1)] = most_common_result; diff --git a/test/regress/CMakeLists.txt b/test/regress/CMakeLists.txt index aedc27924..428d35f8d 100644 --- a/test/regress/CMakeLists.txt +++ b/test/regress/CMakeLists.txt @@ -1433,6 +1433,7 @@ set(regress_1_tests regress1/nl/exp_monotone.smt2 regress1/nl/factor_agg_s.smt2 regress1/nl/iand-native-1.smt2 + regress1/nl/iand-native-2.smt2 regress1/nl/issue3300-approx-sqrt-witness.smt2 regress1/nl/issue3441.smt2 regress1/nl/issue3617.smt2 diff --git a/test/regress/regress0/bv/bv_to_int1.smt2 b/test/regress/regress0/bv/bv_to_int1.smt2 index 8410d04b9..3908cdb16 100644 --- a/test/regress/regress0/bv/bv_to_int1.smt2 +++ b/test/regress/regress0/bv/bv_to_int1.smt2 @@ -1,7 +1,4 @@ ; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=1 -; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=2 -; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=3 -; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=4 ; EXPECT: unsat (set-logic QF_BV) (declare-fun x () (_ BitVec 4)) diff --git a/test/regress/regress1/nl/iand-native-1.smt2 b/test/regress/regress1/nl/iand-native-1.smt2 index 685922f88..e6a25bcc4 100644 --- a/test/regress/regress1/nl/iand-native-1.smt2 +++ b/test/regress/regress1/nl/iand-native-1.smt2 @@ -1,4 +1,5 @@ ; COMMAND-LINE: --iand-mode=value +; COMMAND-LINE: --iand-mode=sum --bvand-integer-granularity=1 --finite-model-find ; EXPECT: sat (set-logic QF_NIA) (set-info :status sat) diff --git a/test/regress/regress1/nl/iand-native-2.smt2 b/test/regress/regress1/nl/iand-native-2.smt2 new file mode 100644 index 000000000..6b39598ea --- /dev/null +++ b/test/regress/regress1/nl/iand-native-2.smt2 @@ -0,0 +1,15 @@ +; COMMAND-LINE: --iand-mode=value +; COMMAND-LINE: --iand-mode=sum --bvand-integer-granularity=1 +; EXPECT: unsat +(set-logic QF_NIA) +(set-info :status unsat) +(declare-fun x () Int) +(declare-fun y () Int) + +(assert (and (<= 0 x) (< x 16))) +(assert (and (<= 0 y) (< y 16))) +(assert (> ((_ iand 4) x y) 0)) +(assert (= (* x y) 0)) +(assert (= (+ x y) 15)) + +(check-sat) diff --git a/test/regress/regress2/bv_to_int2.smt2 b/test/regress/regress2/bv_to_int2.smt2 index 4c1ca0c00..424e95b27 100644 --- a/test/regress/regress2/bv_to_int2.smt2 +++ b/test/regress/regress2/bv_to_int2.smt2 @@ -1,6 +1,4 @@ ; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=1 -; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=5 -; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=8 ; EXPECT: sat (set-logic QF_BV) (declare-fun a () (_ BitVec 8)) diff --git a/test/regress/regress2/bv_to_int_ashr.smt2 b/test/regress/regress2/bv_to_int_ashr.smt2 index b95dc6b7f..0c6768546 100644 --- a/test/regress/regress2/bv_to_int_ashr.smt2 +++ b/test/regress/regress2/bv_to_int_ashr.smt2 @@ -1,5 +1,4 @@ ; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=1 -; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=8 ; EXPECT: unsat (set-logic QF_BV) (declare-fun a () (_ BitVec 8)) diff --git a/test/regress/regress2/bv_to_int_bitwise.smt2 b/test/regress/regress2/bv_to_int_bitwise.smt2 index 373f9c323..66d9e2379 100644 --- a/test/regress/regress2/bv_to_int_bitwise.smt2 +++ b/test/regress/regress2/bv_to_int_bitwise.smt2 @@ -1,6 +1,7 @@ ; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=1 --no-check-unsat-cores ; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=5 --no-check-unsat-cores -; COMMAND-LINE: --solve-bv-as-int=iand --no-check-unsat-cores +; COMMAND-LINE: --solve-bv-as-int=iand --iand-mode=value --no-check-unsat-cores +; COMMAND-LINE: --solve-bv-as-int=iand --iand-mode=sum --no-check-unsat-cores ; COMMAND-LINE: --solve-bv-as-int=bv --no-check-unsat-cores ; EXPECT: unsat (set-logic QF_BV) diff --git a/test/regress/regress2/bv_to_int_bvmul1.smt2 b/test/regress/regress2/bv_to_int_bvmul1.smt2 index cfd5c4b9a..232959f33 100644 --- a/test/regress/regress2/bv_to_int_bvmul1.smt2 +++ b/test/regress/regress2/bv_to_int_bvmul1.smt2 @@ -1,6 +1,4 @@ ; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=1 -; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=4 -; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=8 ; EXPECT: sat (set-logic QF_BV) (declare-fun a () (_ BitVec 8)) diff --git a/test/regress/regress2/bv_to_int_mask_array_1.smt2 b/test/regress/regress2/bv_to_int_mask_array_1.smt2 index b1c8b9509..d587735e5 100644 --- a/test/regress/regress2/bv_to_int_mask_array_1.smt2 +++ b/test/regress/regress2/bv_to_int_mask_array_1.smt2 @@ -1,5 +1,6 @@ ; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=1 --no-check-unsat-cores -; COMMAND-LINE: --solve-bv-as-int=iand --no-check-unsat-cores +; COMMAND-LINE: --solve-bv-as-int=iand --iand-mode=value --no-check-unsat-cores +; COMMAND-LINE: --solve-bv-as-int=iand --iand-mode=sum --no-check-unsat-cores ; COMMAND-LINE: --solve-bv-as-int=bv --no-check-unsat-cores ; EXPECT: unsat (set-logic ALL) diff --git a/test/regress/regress2/bv_to_int_mask_array_2.smt2 b/test/regress/regress2/bv_to_int_mask_array_2.smt2 index c054f9693..edcc14149 100644 --- a/test/regress/regress2/bv_to_int_mask_array_2.smt2 +++ b/test/regress/regress2/bv_to_int_mask_array_2.smt2 @@ -1,5 +1,6 @@ ; COMMAND-LINE: --solve-bv-as-int=sum --bvand-integer-granularity=1 -; COMMAND-LINE: --solve-bv-as-int=iand +; COMMAND-LINE: --solve-bv-as-int=iand --iand-mode=value +; COMMAND-LINE: --solve-bv-as-int=iand --iand-mode=sum ; COMMAND-LINE: --solve-bv-as-int=bv ; EXPECT: sat (set-logic ALL) diff --git a/test/regress/regress3/bv_to_int_check_bvsge_bvashr0_4bit.smt2.minimized.smt2 b/test/regress/regress3/bv_to_int_check_bvsge_bvashr0_4bit.smt2.minimized.smt2 index 67f8f69ad..5c96417d5 100644 --- a/test/regress/regress3/bv_to_int_check_bvsge_bvashr0_4bit.smt2.minimized.smt2 +++ b/test/regress/regress3/bv_to_int_check_bvsge_bvashr0_4bit.smt2.minimized.smt2 @@ -1,5 +1,4 @@ -; COMMAND-LINE: --cegqi-all --full-saturate-quant --bvand-integer-granularity=1 --solve-bv-as-int=sum --no-check-models -; COMMAND-LINE: --cegqi-all --full-saturate-quant --bvand-integer-granularity=2 --solve-bv-as-int=sum --no-check-models +; COMMAND-LINE: --solve-bv-as-int=sum --no-check-models ; EXPECT: sat (set-logic BV) (declare-fun s () (_ BitVec 3)) diff --git a/test/regress/regress3/bv_to_int_check_bvsgt_bvlshr0_4bit.smt2.minimized.smt2 b/test/regress/regress3/bv_to_int_check_bvsgt_bvlshr0_4bit.smt2.minimized.smt2 index 300883882..ed8543050 100644 --- a/test/regress/regress3/bv_to_int_check_bvsgt_bvlshr0_4bit.smt2.minimized.smt2 +++ b/test/regress/regress3/bv_to_int_check_bvsgt_bvlshr0_4bit.smt2.minimized.smt2 @@ -1,9 +1,7 @@ ; COMMAND-LINE: --solve-bv-as-int=bv -; COMMAND-LINE: --cegqi-all --full-saturate-quant --bvand-integer-granularity=1 --solve-bv-as-int=sum -; COMMAND-LINE: --cegqi-all --full-saturate-quant --bvand-integer-granularity=1 --solve-bv-as-int=iand --iand-mode=sum -; COMMAND-LINE: --cegqi-all --full-saturate-quant --bvand-integer-granularity=1 --solve-bv-as-int=iand --iand-mode=bitwise -; COMMAND-LINE: --cegqi-all --full-saturate-quant --bvand-integer-granularity=1 --solve-bv-as-int=iand -; COMMAND-LINE: --cegqi-all --full-saturate-quant --bvand-integer-granularity=2 --solve-bv-as-int=sum +; COMMAND-LINE: --solve-bv-as-int=sum +; COMMAND-LINE: --solve-bv-as-int=iand --iand-mode=sum +; COMMAND-LINE: --solve-bv-as-int=iand --iand-mode=value ; EXPECT: unsat (set-logic ALL) (declare-fun t () (_ BitVec 4)) diff --git a/test/regress/regress3/bv_to_int_input_mouser_detect.c.smt2.minimized.smt2 b/test/regress/regress3/bv_to_int_input_mouser_detect.c.smt2.minimized.smt2 index 576ebf962..dd7e11a50 100644 --- a/test/regress/regress3/bv_to_int_input_mouser_detect.c.smt2.minimized.smt2 +++ b/test/regress/regress3/bv_to_int_input_mouser_detect.c.smt2.minimized.smt2 @@ -1,3 +1,4 @@ +; COMMAND-LINE: --solve-bv-as-int=bv --no-check-models ; COMMAND-LINE: --bvand-integer-granularity=1 --solve-bv-as-int=sum --full-saturate-quant --cegqi-all --no-check-models ;EXPECT: sat (set-logic BV) -- 2.30.2