From 39a85cc99f3b9f3d203490f5918ebe56bd916d64 Mon Sep 17 00:00:00 2001 From: Andrew Reynolds Date: Fri, 13 Oct 2017 00:12:02 -0500 Subject: CBQI BV quick heuristics (#1239) Adds two heuristics for cbqi-bv, both disabled by default. The first optimistically solves for boundary points of inequalities. The second randomly interleaves inversion and value instantiations. Adds some newly solved regressions from SMT LIB. --- test/regress/regress0/quantifiers/Makefile.am | 7 ++++++- ...ntersection-example-onelane.proof-node22337.smt2 | 20 ++++++++++++++++++++ .../nested9_true-unreach-call.i_575.smt2 | 21 +++++++++++++++++++++ .../quantifiers/small-pipeline-fixpoint-3.smt2 | 7 +++++++ 4 files changed, 54 insertions(+), 1 deletion(-) create mode 100644 test/regress/regress0/quantifiers/intersection-example-onelane.proof-node22337.smt2 create mode 100644 test/regress/regress0/quantifiers/nested9_true-unreach-call.i_575.smt2 create mode 100644 test/regress/regress0/quantifiers/small-pipeline-fixpoint-3.smt2 (limited to 'test') diff --git a/test/regress/regress0/quantifiers/Makefile.am b/test/regress/regress0/quantifiers/Makefile.am index 14e5244b4..ec24fdd8b 100644 --- a/test/regress/regress0/quantifiers/Makefile.am +++ b/test/regress/regress0/quantifiers/Makefile.am @@ -103,7 +103,12 @@ TESTS = \ qbv-simple-2vars-vo.smt2 \ qbv-test-urem-rewrite.smt2 \ qbv-inequality2.smt2 \ - qbv-test-invert-bvult-1.smt2 + qbv-test-invert-bvult-1.smt2 \ + intersection-example-onelane.proof-node22337.smt2 + +# solved, but fail an assertion due to unhandled EXTRACT case +# nested9_true-unreach-call.i_575.smt2 +# small-pipeline-fixpoint-3.smt2 # regression can be solved with --finite-model-find --fmf-inst-engine diff --git a/test/regress/regress0/quantifiers/intersection-example-onelane.proof-node22337.smt2 b/test/regress/regress0/quantifiers/intersection-example-onelane.proof-node22337.smt2 new file mode 100644 index 000000000..38a4ed127 --- /dev/null +++ b/test/regress/regress0/quantifiers/intersection-example-onelane.proof-node22337.smt2 @@ -0,0 +1,20 @@ +; COMMAND-LINE: --cbqi-bv +; EXPECT: sat +(set-logic BV) +(set-info :status sat) +(declare-fun xI () (_ BitVec 32)) +(declare-fun A () (_ BitVec 32)) +(declare-fun B () (_ BitVec 32)) +(declare-fun vuscore2dollarskuscore80 () (_ BitVec 32)) +(declare-fun I1 () (_ BitVec 32)) +(declare-fun xuscore2dollarskuscore74 () (_ BitVec 32)) +(declare-fun v () (_ BitVec 32)) +(declare-fun ts49uscore0 () (_ BitVec 32)) +(declare-fun V () (_ BitVec 32)) +(declare-fun t87uscore0dollarskuscore0 () (_ BitVec 32)) +(declare-fun ep () (_ BitVec 32)) +(declare-fun I1uscore2dollarskuscore74 () (_ BitVec 32)) +(declare-fun x () (_ BitVec 32)) +(assert (not (exists ((ts49uscore0 (_ BitVec 32))) (let ((?v_0 (bvsge vuscore2dollarskuscore80 (_ bv0 32))) (?v_1 (bvsle vuscore2dollarskuscore80 V)) (?v_3 (bvsdiv (bvmul vuscore2dollarskuscore80 vuscore2dollarskuscore80) (bvmul (_ bv2 32) B))) (?v_2 (bvmul (bvsdiv (_ bv1 32) (_ bv2 32)) (bvadd (bvmul (bvmul (_ bv2 32) t87uscore0dollarskuscore0) vuscore2dollarskuscore80) (bvmul (_ bv2 32) xuscore2dollarskuscore74))))) (=> (and (and (and (and (and (and (and (and (and (and (and (and (and (and (= I1uscore2dollarskuscore74 (_ bv2 32)) (=> (and (bvsle (_ bv0 32) ts49uscore0) (bvsle ts49uscore0 t87uscore0dollarskuscore0)) (and (and ?v_0 ?v_1) (bvsle ts49uscore0 ep)))) (bvsge t87uscore0dollarskuscore0 (_ bv0 32))) (= vuscore2dollarskuscore80 (_ bv0 32))) ?v_0) ?v_1) (bvsgt xI (bvadd xuscore2dollarskuscore74 ?v_3))) (= I1 (_ bv2 32))) (bvslt xI x)) (bvsgt B (_ bv0 32))) (bvsge v (_ bv0 32))) (bvsle v V)) (bvsge A (_ bv0 32))) (bvsgt V (_ bv0 32))) (bvsgt ep (_ bv0 32))) (or (or (= xI xuscore2dollarskuscore74) (bvslt xI ?v_2)) (bvsgt xI (bvadd ?v_2 ?v_3)))))))) +(check-sat) +(exit) diff --git a/test/regress/regress0/quantifiers/nested9_true-unreach-call.i_575.smt2 b/test/regress/regress0/quantifiers/nested9_true-unreach-call.i_575.smt2 new file mode 100644 index 000000000..2a46d2a21 --- /dev/null +++ b/test/regress/regress0/quantifiers/nested9_true-unreach-call.i_575.smt2 @@ -0,0 +1,21 @@ +; COMMAND-LINE: --cbqi-bv +; EXPECT: unsat +(set-logic BV) +(set-info :status unsat) +(declare-fun c_main_~i~6 () (_ BitVec 32)) +(declare-fun c_main_~j~6 () (_ BitVec 32)) +(declare-fun c_main_~k~6 () (_ BitVec 32)) +(assert + (and (bvsle c_main_~i~6 (_ bv3 32)) (bvsle c_main_~i~6 (_ bv2 32)) + (exists ((v_nnf_34 (_ BitVec 32))) + (and (bvsle (bvadd v_nnf_34 (_ bv3 32)) c_main_~k~6) + (bvsle v_nnf_34 (_ bv3 32)) (bvsle c_main_~j~6 (bvadd (bvmul (_ bv2 32) v_nnf_34) (_ bv1 32))))))) +(assert + (not + (and (bvsle c_main_~i~6 (_ bv3 32)) (bvsle c_main_~i~6 (_ bv2 32)) + (exists ((v_nnf_30 (_ BitVec 32))) + (and (bvsle (bvadd v_nnf_30 (_ bv1 32)) c_main_~k~6) + (bvsle v_nnf_30 (_ bv3 32)) (bvsle c_main_~j~6 (bvadd (bvmul (_ bv2 32) v_nnf_30) (_ bv1 32)))))))) +(check-sat) +(exit) + diff --git a/test/regress/regress0/quantifiers/small-pipeline-fixpoint-3.smt2 b/test/regress/regress0/quantifiers/small-pipeline-fixpoint-3.smt2 new file mode 100644 index 000000000..378912490 --- /dev/null +++ b/test/regress/regress0/quantifiers/small-pipeline-fixpoint-3.smt2 @@ -0,0 +1,7 @@ +; COMMAND-LINE: --cbqi-bv --no-check-models +; EXPECT: unsat +(set-logic BV) +(set-info :status unsat) +(assert (forall ((Verilog__main.dataOut_64_0 (_ BitVec 32))) (forall ((Verilog__main.stageOne_64_0 (_ BitVec 32))) (forall ((Verilog__main.stageTwo_64_0 (_ BitVec 32))) (forall ((Verilog__main.tmp_stageOne_64_0 (_ BitVec 32))) (forall ((Verilog__main.tmp_stageTwo_64_0 (_ BitVec 32))) (forall ((Verilog__main.dataOut_64_1 (_ BitVec 32))) (forall ((Verilog__main.reset_64_0 Bool)) (forall ((Verilog__main.stageOne_64_1 (_ BitVec 32))) (forall ((Verilog__main.dataIn_64_0 (_ BitVec 32))) (forall ((Verilog__main.c1_64_0 (_ BitVec 32))) (forall ((Verilog__main.stageTwo_64_1 (_ BitVec 32))) (forall ((Verilog__main.c2_64_0 (_ BitVec 32))) (forall ((Verilog__main.tmp_stageOne_64_1 (_ BitVec 32))) (forall ((Verilog__main.tmp_stageTwo_64_1 (_ BitVec 32))) (forall ((Verilog__main.dataOut_64_2 (_ BitVec 32))) (forall ((Verilog__main.reset_64_1 Bool)) (forall ((Verilog__main.stageOne_64_2 (_ BitVec 32))) (forall ((Verilog__main.dataIn_64_1 (_ BitVec 32))) (forall ((Verilog__main.c1_64_1 (_ BitVec 32))) (forall ((Verilog__main.stageTwo_64_2 (_ BitVec 32))) (forall ((Verilog__main.c2_64_1 (_ BitVec 32))) (forall ((Verilog__main.tmp_stageOne_64_2 (_ BitVec 32))) (forall ((Verilog__main.tmp_stageTwo_64_2 (_ BitVec 32))) (forall ((Verilog__main.dataOut_64_3 (_ BitVec 32))) (forall ((Verilog__main.reset_64_2 Bool)) (forall ((Verilog__main.stageOne_64_3 (_ BitVec 32))) (forall ((Verilog__main.dataIn_64_2 (_ BitVec 32))) (forall ((Verilog__main.c1_64_2 (_ BitVec 32))) (forall ((Verilog__main.stageTwo_64_3 (_ BitVec 32))) (forall ((Verilog__main.c2_64_2 (_ BitVec 32))) (forall ((Verilog__main.tmp_stageOne_64_3 (_ BitVec 32))) (forall ((Verilog__main.tmp_stageTwo_64_3 (_ BitVec 32))) (exists ((Verilog__main.dataOut_64_0_39_ (_ BitVec 32))) (exists ((Verilog__main.stageOne_64_0_39_ (_ BitVec 32))) (exists ((Verilog__main.stageTwo_64_0_39_ (_ BitVec 32))) (exists ((Verilog__main.tmp_stageOne_64_0_39_ (_ BitVec 32))) (exists ((Verilog__main.tmp_stageTwo_64_0_39_ (_ BitVec 32))) (exists ((Verilog__main.dataOut_64_1_39_ (_ BitVec 32))) (exists ((Verilog__main.reset_64_0_39_ Bool)) (exists ((Verilog__main.stageOne_64_1_39_ (_ BitVec 32))) (exists ((Verilog__main.dataIn_64_0_39_ (_ BitVec 32))) (exists ((Verilog__main.c1_64_0_39_ (_ BitVec 32))) (exists ((Verilog__main.stageTwo_64_1_39_ (_ BitVec 32))) (exists ((Verilog__main.c2_64_0_39_ (_ BitVec 32))) (exists ((Verilog__main.tmp_stageOne_64_1_39_ (_ BitVec 32))) (exists ((Verilog__main.tmp_stageTwo_64_1_39_ (_ BitVec 32))) (exists ((Verilog__main.dataOut_64_2_39_ (_ BitVec 32))) (exists ((Verilog__main.reset_64_1_39_ Bool)) (exists ((Verilog__main.stageOne_64_2_39_ (_ BitVec 32))) (exists ((Verilog__main.dataIn_64_1_39_ (_ BitVec 32))) (exists ((Verilog__main.c1_64_1_39_ (_ BitVec 32))) (exists ((Verilog__main.stageTwo_64_2_39_ (_ BitVec 32))) (exists ((Verilog__main.c2_64_1_39_ (_ BitVec 32))) (exists ((Verilog__main.tmp_stageOne_64_2_39_ (_ BitVec 32))) (exists ((Verilog__main.tmp_stageTwo_64_2_39_ (_ BitVec 32))) (=> (and (and (= Verilog__main.dataOut_64_0 (_ bv0 32)) (= Verilog__main.stageOne_64_0 (_ bv0 32)) (= Verilog__main.stageTwo_64_0 (_ bv0 32)) (= Verilog__main.tmp_stageOne_64_0 (_ bv0 32)) (= Verilog__main.tmp_stageTwo_64_0 (_ bv0 32))) (and (= Verilog__main.dataOut_64_1 (ite (not Verilog__main.reset_64_0) (bvadd Verilog__main.stageTwo_64_0 Verilog__main.stageOne_64_0) (_ bv0 32))) (= Verilog__main.stageOne_64_1 (bvadd Verilog__main.dataIn_64_0 Verilog__main.c1_64_0)) (= Verilog__main.stageTwo_64_1 (bvand Verilog__main.stageOne_64_0 Verilog__main.c2_64_0)) (= Verilog__main.tmp_stageOne_64_1 Verilog__main.stageOne_64_0) (= Verilog__main.tmp_stageTwo_64_1 Verilog__main.stageTwo_64_0)) (and (= Verilog__main.dataOut_64_2 (ite (not Verilog__main.reset_64_1) (bvadd Verilog__main.stageTwo_64_1 Verilog__main.stageOne_64_1) (_ bv0 32))) (= Verilog__main.stageOne_64_2 (bvadd Verilog__main.dataIn_64_1 Verilog__main.c1_64_1)) (= Verilog__main.stageTwo_64_2 (bvand Verilog__main.stageOne_64_1 Verilog__main.c2_64_1)) (= Verilog__main.tmp_stageOne_64_2 Verilog__main.stageOne_64_1) (= Verilog__main.tmp_stageTwo_64_2 Verilog__main.stageTwo_64_1)) (and (= Verilog__main.dataOut_64_3 (ite (not Verilog__main.reset_64_2) (bvadd Verilog__main.stageTwo_64_2 Verilog__main.stageOne_64_2) (_ bv0 32))) (= Verilog__main.stageOne_64_3 (bvadd Verilog__main.dataIn_64_2 Verilog__main.c1_64_2)) (= Verilog__main.stageTwo_64_3 (bvand Verilog__main.stageOne_64_2 Verilog__main.c2_64_2)) (= Verilog__main.tmp_stageOne_64_3 Verilog__main.stageOne_64_2) (= Verilog__main.tmp_stageTwo_64_3 Verilog__main.stageTwo_64_2))) (and (and (and (= Verilog__main.dataOut_64_0_39_ (_ bv0 32)) (= Verilog__main.stageOne_64_0_39_ (_ bv0 32)) (= Verilog__main.stageTwo_64_0_39_ (_ bv0 32)) (= Verilog__main.tmp_stageOne_64_0_39_ (_ bv0 32)) (= Verilog__main.tmp_stageTwo_64_0_39_ (_ bv0 32))) (and (= Verilog__main.dataOut_64_1_39_ (ite (not Verilog__main.reset_64_0_39_) (bvadd Verilog__main.stageTwo_64_0_39_ Verilog__main.stageOne_64_0_39_) (_ bv0 32))) (= Verilog__main.stageOne_64_1_39_ (bvadd Verilog__main.dataIn_64_0_39_ Verilog__main.c1_64_0_39_)) (= Verilog__main.stageTwo_64_1_39_ (bvand Verilog__main.stageOne_64_0_39_ Verilog__main.c2_64_0_39_)) (= Verilog__main.tmp_stageOne_64_1_39_ Verilog__main.stageOne_64_0_39_) (= Verilog__main.tmp_stageTwo_64_1_39_ Verilog__main.stageTwo_64_0_39_)) (and (= Verilog__main.dataOut_64_2_39_ (ite (not Verilog__main.reset_64_1_39_) (bvadd Verilog__main.stageTwo_64_1_39_ Verilog__main.stageOne_64_1_39_) (_ bv0 32))) (= Verilog__main.stageOne_64_2_39_ (bvadd Verilog__main.dataIn_64_1_39_ Verilog__main.c1_64_1_39_)) (= Verilog__main.stageTwo_64_2_39_ (bvand Verilog__main.stageOne_64_1_39_ Verilog__main.c2_64_1_39_)) (= Verilog__main.tmp_stageOne_64_2_39_ Verilog__main.stageOne_64_1_39_) (= Verilog__main.tmp_stageTwo_64_2_39_ Verilog__main.stageTwo_64_1_39_))) (or (and (= Verilog__main.dataOut_64_3 Verilog__main.dataOut_64_0_39_) (= Verilog__main.stageOne_64_3 Verilog__main.stageOne_64_0_39_) (= Verilog__main.stageTwo_64_3 Verilog__main.stageTwo_64_0_39_) (= Verilog__main.tmp_stageOne_64_3 Verilog__main.tmp_stageOne_64_0_39_) (= Verilog__main.tmp_stageTwo_64_3 Verilog__main.tmp_stageTwo_64_0_39_)) (and (= Verilog__main.dataOut_64_3 Verilog__main.dataOut_64_1_39_) (= Verilog__main.stageOne_64_3 Verilog__main.stageOne_64_1_39_) (= Verilog__main.stageTwo_64_3 Verilog__main.stageTwo_64_1_39_) (= Verilog__main.tmp_stageOne_64_3 Verilog__main.tmp_stageOne_64_1_39_) (= Verilog__main.tmp_stageTwo_64_3 Verilog__main.tmp_stageTwo_64_1_39_)) (and (= Verilog__main.dataOut_64_3 Verilog__main.dataOut_64_2_39_) (= Verilog__main.stageOne_64_3 Verilog__main.stageOne_64_2_39_) (= Verilog__main.stageTwo_64_3 Verilog__main.stageTwo_64_2_39_) (= Verilog__main.tmp_stageOne_64_3 Verilog__main.tmp_stageOne_64_2_39_) (= Verilog__main.tmp_stageTwo_64_3 Verilog__main.tmp_stageTwo_64_2_39_))))) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )) +(check-sat) +(exit) -- cgit v1.2.3