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.

4 files changed, 54 insertions, 1 deletions

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)