00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #define _CVC3_TRUSTED_
00030
00031 #include "bitvector_theorem_producer.h"
00032 #include "common_proof_rules.h"
00033 #include "theory_core.h"
00034 #include "theory_bitvector.h"
00035
00036 using namespace std;
00037 using namespace CVC3;
00038
00039
00040
00041
00042 BitvectorProofRules*
00043 TheoryBitvector::createProofRules() {
00044 return new BitvectorTheoremProducer(this);
00045 }
00046
00047
00048 BitvectorTheoremProducer::BitvectorTheoremProducer(TheoryBitvector* theoryBV)
00049 : TheoremProducer(theoryBV->theoryCore()->getTM()),
00050 d_theoryBitvector(theoryBV) {
00051
00052 vector<bool> bits(1);
00053 bits[0]=false;
00054 d_bvZero = d_theoryBitvector->newBVConstExpr(bits);
00055 bits[0]=true;
00056 d_bvOne = d_theoryBitvector->newBVConstExpr(bits);
00057 }
00058
00059
00060
00061
00062
00063 Theorem BitvectorTheoremProducer::bitvectorFalseRule(const Theorem& thm) {
00064 if(CHECK_PROOFS) {
00065 const Expr e = thm.getExpr();
00066 CHECK_SOUND(e.isIff() && e[0].isIff(),
00067 "TheoryBitvector::bitvectorFalseRule: "
00068 "premise must be a iff theorem:\n e = "
00069 +e.toString());
00070 CHECK_SOUND(e[1].isFalse(),
00071 "TheoryBitvector::bitvectorFalseRule: "
00072 "premise must be iff Theorem, with False as the RHS:\n e = "
00073 +e.toString());
00074 CHECK_SOUND(e[0][0].getOpKind() == BOOLEXTRACT &&
00075 e[0][1].getOpKind() == BOOLEXTRACT,
00076 "TheoryBitvector::bitvectorFalseRule: "
00077 "premise must be iff Theorem, with False as the RHS:\n e = "
00078 +e.toString());
00079 CHECK_SOUND(d_theoryBitvector->getBoolExtractIndex(e[0][0]) ==
00080 d_theoryBitvector->getBoolExtractIndex(e[0][1]),
00081 "TheoryBitvector::bitvectorFalseRule: "
00082 "premise must be iff Theorem, with False as the RHS:\n e = "
00083 +e.toString());
00084 }
00085 const Expr& e = thm.getExpr();
00086 const Expr& t1 = e[0][0][0];
00087 const Expr& t2 = e[0][1][0];
00088
00089 Proof pf;
00090 if(withProof())
00091 pf = newPf("bitvector_false_rule", e, thm.getProof());
00092 return newRWTheorem(t1.eqExpr(t2), e[1], thm.getAssumptionsRef(), pf);
00093 }
00094
00095 Theorem BitvectorTheoremProducer::bitvectorTrueRule(const Theorem& thm) {
00096 if(CHECK_PROOFS) {
00097 const Expr e = thm.getExpr();
00098 CHECK_SOUND(e.isIff() && e[0].isIff(),
00099 "TheoryBitvector::bitvectorFalseRule: "
00100 "premise must be a iff theorem:\n e = "
00101 +e.toString());
00102 CHECK_SOUND(e[1].isTrue(),
00103 "TheoryBitvector::bitvectorFalseRule: "
00104 "premise must be iff Theorem, with False as the RHS:\n e = "
00105 +e.toString());
00106 CHECK_SOUND(e[0][0].getKind() == NOT &&
00107 e[0][0][0].getOpKind() == BOOLEXTRACT &&
00108 e[0][1].getOpKind() == BOOLEXTRACT,
00109 "TheoryBitvector::bitvectorFalseRule: "
00110 "premise must be iff Theorem, with False as the RHS:\n e = "
00111 +e.toString());
00112 CHECK_SOUND(d_theoryBitvector->getBoolExtractIndex(e[0][0][0]) ==
00113 d_theoryBitvector->getBoolExtractIndex(e[0][1]),
00114 "TheoryBitvector::bitvectorFalseRule: "
00115 "premise must be iff Theorem, with False as the RHS:\n e = "
00116 +e.toString());
00117 }
00118 const Expr& e = thm.getExpr();
00119
00120
00121 const Expr& t1 = e[0][0][0][0];
00122 const Expr& t2 = e[0][1][0];
00123
00124 Proof pf;
00125 if(withProof())
00126 pf = newPf("bitvector_true_rule", e, thm.getProof());
00127 return newRWTheorem(t1.eqExpr(t2).negate(), e[1], thm.getAssumptionsRef(), pf);
00128 }
00129
00130 Theorem BitvectorTheoremProducer::bitBlastEqnRule(const Expr& e,
00131 const Expr& f) {
00132 if(CHECK_PROOFS) {
00133 CHECK_SOUND(e.isEq(),
00134 "TheoryBitvector::bitBlastEqnRule: "
00135 "premise must be a rewrite theorem:\n e = "
00136 +e.toString());
00137 const Expr& lhs = e[0];
00138 const Expr& rhs = e[1];
00139 const Type& leftType = lhs.getType();
00140 const Type& rightType = rhs.getType();
00141 CHECK_SOUND(BITVECTOR == leftType.getExpr().getOpKind() &&
00142 BITVECTOR == rightType.getExpr().getOpKind(),
00143 "TheoryBitvector::bitBlastEqnRule: "
00144 "lhs & rhs must be bitvectors:\n e ="
00145 +e.toString());
00146 int lhsLength = d_theoryBitvector->BVSize(lhs);
00147 int rhsLength = d_theoryBitvector->BVSize(rhs);
00148 CHECK_SOUND(lhsLength == rhsLength,
00149 "TheoryBitvector::bitBlastEqnRule: "
00150 "lhs & rhs must be bitvectors of same bvLength.\n size(lhs) = "
00151 + int2string(lhsLength)
00152 +"\n size(rhs) = "
00153 + int2string(rhsLength)
00154 +"\n e = "+e.toString());
00155 int bvLength = d_theoryBitvector->BVSize(leftType.getExpr());
00156 CHECK_SOUND(f.isAnd(),
00157 "TheoryBitvector::bitBlastEqnRule: "
00158 "consequence of the rule must be an AND.\n f = "
00159 +f.toString());
00160 CHECK_SOUND(bvLength == f.arity(),
00161 "TheoryBitvector::bitBlastEqnRule: "
00162 "the arity of the consequence AND must "
00163 "equal the bvLength of the bitvector:\n f = "
00164 +f.toString()+"\n bvLength = "+ int2string(bvLength));
00165 for(int i=0; i <bvLength; i++) {
00166 const Expr& conjunct = f[i];
00167 CHECK_SOUND(conjunct.isIff() && 2 == conjunct.arity(),
00168 "TheoryBitvector::bitBlastEqnRule: "
00169 "each conjunct in consequent must be an IFF.\n f = "
00170 +f.toString());
00171 const Expr& leftExtract = conjunct[0];
00172 const Expr& rightExtract = conjunct[1];
00173 CHECK_SOUND(BOOLEXTRACT == leftExtract.getOpKind(),
00174 "TheoryBitvector::bitBlastEqnRule: "
00175 "each conjunct in consequent must be boolextract.\n"
00176 " f["+int2string(i)+"] = "+conjunct.toString());
00177 CHECK_SOUND(BOOLEXTRACT == rightExtract.getOpKind(),
00178 "TheoryBitvector::bitBlastEqnRule: "
00179 "each conjunct in consequent must be boolextract.\n"
00180 " f["+int2string(i)+"] = "+conjunct.toString());
00181 const Expr& leftBV = leftExtract[0];
00182 const Expr& rightBV = rightExtract[0];
00183 CHECK_SOUND(leftBV == lhs && rightBV == rhs,
00184 "TheoryBitvector::bitBlastEqnRule: each boolextract"
00185 " must be applied to the correct bitvector.\n conjunct = "
00186 +conjunct.toString()
00187 +"\n leftBV = "+ leftBV.toString()
00188 +"\n lhs = "+ lhs.toString()
00189 +"\n rightBV = "+rightBV.toString()
00190 +"\n rhs = "+rhs.toString());
00191 int leftBitPosition =
00192 d_theoryBitvector->getBoolExtractIndex(leftExtract);
00193 int rightBitPosition =
00194 d_theoryBitvector->getBoolExtractIndex(rightExtract);
00195 CHECK_SOUND(leftBitPosition == i && rightBitPosition == i,
00196 "TheoryBitvector::bitBlastEqnRule: "
00197 "boolextract positions must match i= "+int2string(i)
00198 +"\n conjunct = "+conjunct.toString());
00199 }
00200 }
00201
00202 Proof pf;
00203 if(withProof())
00204 pf = newPf("bit_blast_equations", e, f);
00205 return newRWTheorem(e, f, Assumptions::emptyAssump(), pf);
00206 }
00207
00208
00209
00210
00211
00212
00213 Theorem BitvectorTheoremProducer::bitBlastDisEqnRule(const Theorem& notE,
00214 const Expr& f){
00215
00216 TRACE("bitvector", "input to bitBlastDisEqnRule(", notE.toString(), ")");
00217 DebugAssert(notE.getExpr().isNot() && (notE.getExpr())[0].isEq(),
00218 "TheoryBitvector::bitBlastDisEqnRule:"
00219 "expecting an equation" + notE.getExpr().toString());
00220
00221 const Expr& e = (notE.getExpr())[0];
00222 if(CHECK_PROOFS) {
00223 CHECK_SOUND(e.isEq(),
00224 "TheoryBitvector::bitBlastDisEqnRule:"
00225 "premise must be a rewrite theorem" + e.toString());
00226 const Expr& lhs = e[0];
00227 const Expr& rhs = e[1];
00228 const Type& leftType = lhs.getType();
00229 const Type& rightType = rhs.getType();
00230 CHECK_SOUND(BITVECTOR == leftType.getExpr().getOpKind() &&
00231 BITVECTOR == rightType.getExpr().getOpKind(),
00232 "TheoryBitvector::bitBlastDisEqnRule:"
00233 "lhs & rhs must be bitvectors" + e.toString());
00234 CHECK_SOUND(d_theoryBitvector->BVSize(leftType.getExpr()) ==
00235 d_theoryBitvector->BVSize(rightType.getExpr()),
00236 "TheoryBitvector::bitBlastDisEqnRule:"
00237 "lhs & rhs must be bitvectors of same bvLength");
00238 int bvLength = d_theoryBitvector->BVSize(leftType.getExpr());
00239 CHECK_SOUND(f.isOr(),
00240 "TheoryBitvector::bitBlastDisEqnRule:"
00241 "consequence of the rule must be an OR" + f.toString());
00242 CHECK_SOUND(bvLength == f.arity(),
00243 "TheoryBitvector::bitBlastDisEqnRule:"
00244 "the arity of the consequence OR must be"
00245 "equal to the bvLength of the bitvector" +
00246 f.toString() + int2string(bvLength));
00247 for(int i=0; i <bvLength; i++) {
00248 const Expr& disjunct = f[i];
00249 CHECK_SOUND(disjunct.isIff() &&
00250 2 == disjunct.arity() && disjunct[0].isNot(),
00251 "TheoryBitvector::bitBlastDisEqnRule:"
00252 "each conjunct in consequent must be an Iff"+f.toString());
00253 const Expr& leftExtract = (disjunct[0])[0];
00254 const Expr& rightExtract = disjunct[1];
00255 CHECK_SOUND(BOOLEXTRACT == leftExtract.getOpKind(),
00256 "TheoryBitvector::bitBlastDisEqnRule:"
00257 "each disjunct in consequent must be boolextract" +
00258 disjunct.toString());
00259 CHECK_SOUND(BOOLEXTRACT == rightExtract.getOpKind(),
00260 "TheoryBitvector::bitBlastDisEqnRule:"
00261 "each conjunct in consequent must be boolextract" +
00262 disjunct.toString());
00263 const Expr& leftBV = leftExtract[0];
00264 const Expr& rightBV = rightExtract[0];
00265 CHECK_SOUND(leftBV == lhs && rightBV == rhs,
00266 "TheoryBitvector::bitBlastDisEqnRule:"
00267 "each boolextract must be applied to the correct bitvector"+
00268 disjunct.toString() + leftBV.toString() + lhs.toString() +
00269 rightBV.toString() + rhs.toString());
00270 int leftBitPosition =
00271 d_theoryBitvector->getBoolExtractIndex(leftExtract);
00272 int rightBitPosition =
00273 d_theoryBitvector->getBoolExtractIndex(rightExtract);
00274 CHECK_SOUND(leftBitPosition == i && rightBitPosition == i,
00275 "TheoryBitvector::bitBlastDisEqnRule:"
00276 "boolextract positions must match" + disjunct.toString());
00277 }
00278 }
00279
00280 Proof pf;
00281 if(withProof())
00282 pf = newPf("bit_blast_disequations", notE.getExpr(), f, notE.getProof());
00283 return newTheorem(f, notE.getAssumptionsRef(), pf);
00284 }
00285
00286
00287
00288
00289
00290
00291
00292 Theorem
00293 BitvectorTheoremProducer::padBVLTRule(const Expr& e, int len) {
00294 if(CHECK_PROOFS) {
00295 CHECK_SOUND((BVLT == e.getOpKind() || BVLE == e.getOpKind()) &&
00296 e.arity()==2,
00297 "BitvectorTheoremProducer::padBVLTRule: "
00298 "input must e be a BVLT/BVLE: e = " + e.toString());
00299 CHECK_SOUND(BITVECTOR==e[0].getType().getExpr().getOpKind() &&
00300 BITVECTOR==e[1].getType().getExpr().getOpKind(),
00301 "BitvectorTheoremProducer::padBVLTRule: "
00302 "for BVMULT terms e[0],e[1] must be a BV: " + e.toString());
00303 CHECK_SOUND(0<len,
00304 "BitvectorTheoremProducer::padBVLTRule: "
00305 "input len must be >=0 and an integer: len = " +
00306 int2string(len));
00307 }
00308 Expr e0 = pad(len, e[0]);
00309 Expr e1 = pad(len, e[1]);
00310 int kind = e.getOpKind();
00311
00312 Expr output;
00313 if(kind == BVLT)
00314 output = d_theoryBitvector->newBVLTExpr(e0,e1);
00315 else
00316 output = d_theoryBitvector->newBVLEExpr(e0,e1);
00317
00318 Proof pf;
00319 if(withProof())
00320 pf = newPf("pad_bvlt_rule", e);
00321 Theorem result(newRWTheorem(e,output,Assumptions::emptyAssump(),pf));
00322 return result;
00323 }
00324
00325
00326 Theorem
00327 BitvectorTheoremProducer::signExtendRule(const Expr& e) {
00328 if(CHECK_PROOFS) {
00329 CHECK_SOUND(BITVECTOR==e.getType().getExpr().getOpKind(),
00330 "input must be a bitvector. \n e = " + e.toString());
00331 CHECK_SOUND(SX == e.getOpKind(),
00332 "input must be SX(e).\n e = " + e.toString());
00333 CHECK_SOUND(SX != e[0].getOpKind(),
00334 "input cannot have nested SX.\n e = " + e.toString());
00335 }
00336 Expr input0 = e[0];
00337
00338 while(SX == input0.getOpKind())
00339 input0 = input0[0];
00340
00341 int bvLength = d_theoryBitvector->BVSize(e);
00342 int bvLength0 = d_theoryBitvector->BVSize(input0);
00343
00344 Expr output;
00345 if(bvLength0 == bvLength) {
00346 output = input0;
00347 } else if(bvLength0 < bvLength) {
00348 std::vector<Expr> k;
00349 int c = bvLength - bvLength0;
00350 Expr topBit =
00351 d_theoryBitvector->newBVExtractExpr(input0,bvLength0-1,bvLength0-1);
00352 while(c--)
00353 k.push_back(topBit);
00354 k.push_back(input0);
00355 output = d_theoryBitvector->newConcatExpr(k);
00356 } else
00357 output = d_theoryBitvector->newBVExtractExpr(input0, bvLength-1, 0);
00358
00359 Proof pf;
00360 if(withProof())
00361 pf = newPf("sign_extend_rule", e);
00362 Theorem result(newRWTheorem(e,output,Assumptions::emptyAssump(),pf));
00363 return result;
00364 }
00365
00366
00367 Theorem
00368 BitvectorTheoremProducer::bitExtractSXRule(const Expr& e, int i) {
00369
00370
00371 Theorem thm = signExtendRule(e);
00372 Expr e_i = d_theoryBitvector->newBoolExtractExpr(e,i);
00373 Expr newE_i = d_theoryBitvector->newBoolExtractExpr(thm.getRHS(),i);
00374
00375 Proof pf;
00376 if(withProof())
00377 pf = newPf("bitExtract_SX_rule",e,rat(i));
00378 Theorem result(newRWTheorem(e_i,newE_i,Assumptions::emptyAssump(),pf));
00379 return result;
00380 }
00381
00382
00383
00384 Theorem
00385 BitvectorTheoremProducer::padBVSLTRule(const Expr& e, int len) {
00386 if(CHECK_PROOFS) {
00387 CHECK_SOUND((BVSLT == e.getOpKind() || BVSLE == e.getOpKind()) &&
00388 e.arity()==2,
00389 "BitvectorTheoremProducer::padBVSLTRule: "
00390 "input must e be a BVSLT/BVSLE: e = " + e.toString());
00391 CHECK_SOUND(BITVECTOR==e[0].getType().getExpr().getOpKind() &&
00392 BITVECTOR==e[1].getType().getExpr().getOpKind(),
00393 "BitvectorTheoremProducer::padBVSLTRule: "
00394 "for BVMULT terms e[0],e[1] must be a BV: " + e.toString());
00395 CHECK_SOUND(0<=len,
00396 "BitvectorTheoremProducer::padBVSLTRule: "
00397 "input len must be >=0 and an integer: len = " +
00398 int2string(len));
00399 }
00400 Expr e0 = d_theoryBitvector->newSXExpr(e[0], len);
00401 Expr e1 = d_theoryBitvector->newSXExpr(e[1], len);
00402 int kind = e.getOpKind();
00403
00404 Expr output;
00405 if(kind == BVSLT)
00406 output = d_theoryBitvector->newBVSLTExpr(e0,e1);
00407 else
00408 output = d_theoryBitvector->newBVSLEExpr(e0,e1);
00409
00410 Proof pf;
00411 if(withProof())
00412 pf = newPf("pad_bvslt_rule", e);
00413 Theorem result(newRWTheorem(e,output,Assumptions::emptyAssump(),pf));
00414 return result;
00415 }
00416
00417
00418
00419
00420
00421
00422
00423
00424 Theorem
00425 BitvectorTheoremProducer::signBVLTRule(const Expr& e,
00426 const Theorem& topBit0,
00427 const Theorem& topBit1){
00428 if(CHECK_PROOFS) {
00429 CHECK_SOUND((BVSLT == e.getOpKind() || BVSLE == e.getOpKind()) &&
00430 e.arity()==2,
00431 "BitvectorTheoremProducer::signedBVLTRule: "
00432 "input must e be a BVSLT/BVSLE: e = " + e.toString());
00433 CHECK_SOUND(BITVECTOR==e[0].getType().getExpr().getOpKind() &&
00434 BITVECTOR==e[1].getType().getExpr().getOpKind(),
00435 "BitvectorTheoremProducer::signedBVLTRule: "
00436 "for BVMULT terms e[0],e[1] must be a BV: " + e.toString());
00437 }
00438 const Expr e0 = e[0];
00439 const Expr e1 = e[1];
00440 int e0len = d_theoryBitvector->BVSize(e0);
00441 int e1len = d_theoryBitvector->BVSize(e1);
00442
00443 if(CHECK_PROOFS) {
00444 const Expr e0ext =
00445 d_theoryBitvector->newBVExtractExpr(e0,e0len-1,e0len-1);
00446 const Expr e1ext =
00447 d_theoryBitvector->newBVExtractExpr(e1,e1len-1,e1len-1);
00448 CHECK_SOUND(e0ext == topBit0.getLHS(),
00449 "BitvectorTheoremProducer::signedBVLTRule: "
00450 "topBit0.getLHS() is the un-rewritten form of MSB of e0\n"
00451 "topBit0 is screwed up: topBit0 = " +
00452 topBit0.getExpr().toString());
00453 CHECK_SOUND(e1ext == topBit1.getLHS(),
00454 "BitvectorTheoremProducer::signedBVLTRule: "
00455 "topBit1.getLHS() is the un-rewritten form of MSB of e1\n"
00456 "topBit1 is screwed up: topBit1 = " +
00457 topBit1.getExpr().toString());
00458 CHECK_SOUND(e0len == e1len,
00459 "BitvectorTheoremProducer::signedBVLTRule: "
00460 "both e[0] and e[1] must have the same length\n. e =" +
00461 e.toString());
00462 }
00463 const Expr MSB0 = topBit0.getRHS();
00464 const Expr MSB1 = topBit1.getRHS();
00465
00466 int eKind = e.getOpKind();
00467 Expr output;
00468
00469
00470
00471
00472
00473
00474
00475 Rational b0 = -1;
00476 Rational b1 = -1;
00477 if(MSB0.getKind() == BVCONST) b0 = d_theoryBitvector->computeBVConst(MSB0);
00478 if(MSB1.getKind() == BVCONST) b1 = d_theoryBitvector->computeBVConst(MSB1);
00479
00480
00481 const Expr tExpr = d_theoryBitvector->trueExpr();
00482 const Expr fExpr = d_theoryBitvector->falseExpr();
00483 const Expr MSB0isZero = MSB0.eqExpr(bvZero());
00484 const Expr MSB0isOne = MSB0.eqExpr(bvOne());
00485 const Expr MSB1isZero = MSB1.eqExpr(bvZero());
00486 const Expr MSB1isOne = MSB1.eqExpr(bvOne());
00487
00488
00489
00490
00491 if(e0len == 1) {
00492 if(b0==0 && b1==0)
00493 output = eKind==BVSLT ? fExpr : tExpr;
00494 else if(b0==0 && b1==1)
00495 output = fExpr;
00496 else if(b0==1 && b1==0)
00497 output = tExpr;
00498 else if(b0==1 && b1==1)
00499 output = eKind==BVSLT ? fExpr : tExpr;
00500 else if(b0==0 && b1==-1)
00501 output = eKind==BVSLT ? fExpr : MSB1isZero;
00502 else if(b0==1 && b1==-1)
00503 output = eKind==BVSLT ? MSB1isZero : tExpr;
00504 else if(b0==-1 && b1==0)
00505 output = eKind==BVSLT ? MSB0isOne : tExpr;
00506 else if(b0==-1 && b1==1)
00507 output = eKind==BVSLT ? fExpr : MSB0isOne;
00508 else
00509
00510 output =
00511 eKind==BVSLT ?
00512 MSB0isOne.andExpr(MSB1isZero) :
00513 MSB0isOne.orExpr(MSB1isZero);
00514 } else {
00515
00516 Expr newE0 = d_theoryBitvector->newBVExtractExpr(e0,e0len-2,0);
00517 Expr newE1 = d_theoryBitvector->newBVExtractExpr(e1,e1len-2,0);
00518 Expr newBVLT =
00519 eKind==BVSLT ?
00520 d_theoryBitvector->newBVLTExpr(newE0,newE1):
00521 d_theoryBitvector->newBVLEExpr(newE0,newE1);
00522
00523
00524
00525
00526
00527
00528
00529 if(-1 != b0 && -1 !=b1) {
00530
00531 if(b0 == 1 && b1 == 0)
00532 output = tExpr;
00533
00534 else if(b0 == 0 && b1 == 1)
00535 output = fExpr;
00536
00537 else {
00538 output = newBVLT;
00539 }
00540 }
00541 else if(-1 != b0 && -1 == b1) {
00542
00543
00544
00545
00546
00547
00548
00549 output =
00550 (b0==0) ?
00551
00552 MSB1isZero.andExpr(newBVLT) :
00553
00554 MSB1isZero.orExpr(MSB1isOne.andExpr(newBVLT));
00555 }
00556 else if(-1 == b0 && -1 != b1) {
00557
00558
00559
00560
00561
00562
00563
00564 output =
00565 (b1==0) ?
00566
00567 MSB0isOne.orExpr(MSB0isZero.andExpr(newBVLT)) :
00568
00569 MSB0isOne.andExpr(newBVLT);
00570 } else {
00571
00572
00573
00574 Expr k0 = MSB0isOne.andExpr(MSB1isZero);
00575
00576
00577 Expr k1 = MSB0.eqExpr(MSB1);
00578
00579
00580
00581 output = k0.orExpr(k1.andExpr(newBVLT));
00582 }
00583 }
00584
00585 Proof pf;
00586 if(withProof())
00587 pf = newPf("sign_bvlt_rule", e);
00588 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
00589 }
00590
00591
00592
00593
00594
00595 Theorem BitvectorTheoremProducer::notBVLTRule(const Expr& e, int kind) {
00596 if(CHECK_PROOFS) {
00597 CHECK_SOUND(e.getKind() == NOT,
00598 "BitvectorTheoremProducer::notBVLTRule: "
00599 "input kind must be a NOT:\n e = " + e.toString());
00600 CHECK_SOUND(e[0].getOpKind() == BVLT ||
00601 e[0].getOpKind() == BVLE,
00602 "BitvectorTheoremProducer::notBVLTRule: "
00603 "e[0] must be BVLT or BVLE: \n e = " + e.toString());
00604 CHECK_SOUND(kind == e[0].getOpKind(),
00605 "BitvectorTheoremProducer::notBVLTRule: "
00606 "input kind must be the correct one: e[0] = " +
00607 e[0].toString());
00608 }
00609 Expr output;
00610
00611 const Expr& e00 = e[0][0];
00612 const Expr& e01 = e[0][1];
00613 if(BVLT == e[0].getOpKind())
00614 output = d_theoryBitvector->newBVLEExpr(e01,e00);
00615 else
00616 output = d_theoryBitvector->newBVLTExpr(e01,e00);
00617
00618 Proof pf;
00619 if(withProof())
00620 pf = newPf("not_bvlt_rule", e);
00621 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
00622 }
00623
00624
00625 Theorem BitvectorTheoremProducer::lhsEqRhsIneqn(const Expr& e, int kind) {
00626 if(CHECK_PROOFS) {
00627 CHECK_SOUND(BVLT == e.getOpKind() || BVLE == e.getOpKind(),
00628 "BitvectorTheoremProducer::lhsEqRhsIneqn: "
00629 "input kind must be BVLT or BVLE: e = " + e.toString());
00630 CHECK_SOUND(kind == e.getOpKind(),
00631 "BitvectorTheoremProducer::lhsEqRhsIneqn: "
00632 "input kind must match e.getOpKind(): "
00633 "\n e = " + e.toString());
00634 CHECK_SOUND((e.arity()==2) && (e[0]==e[1]),
00635 "BitvectorTheoremProducer::lhsEqRhsIneqn: "
00636 "input arity must be 2, and e[0] must be equal to e[1]: "
00637 "\ne = " + e.toString());
00638 }
00639 Expr output;
00640 if(kind == BVLT)
00641 output = d_theoryBitvector->falseExpr();
00642 else
00643 output = d_theoryBitvector->trueExpr();
00644
00645 Proof pf;
00646 if(withProof())
00647 pf = newPf("lhs_eq_rhs_ineqn", e);
00648 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
00649 }
00650
00651
00652
00653 Theorem BitvectorTheoremProducer::zeroLeq(const Expr& e) {
00654 if(CHECK_PROOFS) {
00655 CHECK_SOUND(BVLE == e.getOpKind(),
00656 "BitvectorTheoremProducer::zeroLeq: "
00657 "input kind must be BVLE: e = " + e.toString());
00658 CHECK_SOUND(e.arity()==2 && e[0].getOpKind() == BVCONST &&
00659 computeBVConst(e[0]) == 0,
00660 "BitvectorTheoremProducer::zeroLeq: "
00661 "unexpected input: e = " + e.toString());
00662 }
00663 Proof pf;
00664 if(withProof())
00665 pf = newPf("zeroLeq", e);
00666 return newRWTheorem(e, d_theoryBitvector->trueExpr(), Assumptions::emptyAssump(), pf);
00667 }
00668
00669
00670
00671 Theorem BitvectorTheoremProducer::bvConstIneqn(const Expr& e, int kind) {
00672 if(CHECK_PROOFS) {
00673 CHECK_SOUND(BVLT == e.getOpKind() || BVLE == e.getOpKind(),
00674 "BitvectorTheoremProducer::bvConstIneqn: "
00675 "input kind must be BVLT or BVLE: e = " + e.toString());
00676 CHECK_SOUND(kind == e.getOpKind(),
00677 "BitvectorTheoremProducer::bvConstIneqn: "
00678 "input kind must match e.getOpKind(): "
00679 "\n e = " + e.toString());
00680 CHECK_SOUND((e.arity()==2),
00681 "BitvectorTheoremProducer::bvConstIneqn: "
00682 "input arity must be 2: \ne = " + e.toString());
00683 CHECK_SOUND(BVCONST == e[0].getKind() && BVCONST == e[1].getKind(),
00684 "BitvectorTheoremProducer::bvConstIneqn: "
00685 "e[0] and e[1] must both be constants:\n e = " +
00686 e.toString());
00687 }
00688
00689 int e0len = d_theoryBitvector->BVSize(e[0]);
00690 int e1len = d_theoryBitvector->BVSize(e[1]);
00691 if(CHECK_PROOFS)
00692 CHECK_SOUND(e0len == e1len,
00693 "BitvectorTheoremProducer::bvConstIneqn: "
00694 "e[0] and e[1] must have the same bvLength:\ne = " +
00695 e.toString());
00696
00697 Rational lhsVal = d_theoryBitvector->computeBVConst(e[0]);
00698 Rational rhsVal = d_theoryBitvector->computeBVConst(e[1]);
00699 Expr output;
00700
00701 if(BVLT == kind) {
00702 if(lhsVal < rhsVal)
00703 output = d_theoryBitvector->trueExpr();
00704 else
00705 output = d_theoryBitvector->falseExpr();
00706 } else {
00707 if(lhsVal <= rhsVal)
00708 output = d_theoryBitvector->trueExpr();
00709 else
00710 output = d_theoryBitvector->falseExpr();
00711 }
00712
00713 Proof pf;
00714 if(withProof())
00715 pf = newPf("bv_const_ineqn", e);
00716 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
00717 }
00718
00719 Theorem BitvectorTheoremProducer::generalIneqn(const Expr& e,
00720 const Theorem& lhs_i,
00721 const Theorem& rhs_i,
00722 int kind) {
00723 if(CHECK_PROOFS) {
00724 CHECK_SOUND(BVLT == e.getOpKind() || BVLE == e.getOpKind(),
00725 "BitvectorTheoremProducer::generalIneqn: "
00726 "input kind must be BVLT or BVLE: e = " + e.toString());
00727 CHECK_SOUND(kind == e.getOpKind(),
00728 "BitvectorTheoremProducer::generalIneqn: "
00729 "input kind must match e.getOpKind(): "
00730 "\n e = " + e.toString());
00731 CHECK_SOUND((e.arity()==2),
00732 "BitvectorTheoremProducer::generalIneqn: "
00733 "input arity must be 2: \ne = " + e.toString());
00734 CHECK_SOUND(lhs_i.isRewrite() && rhs_i.isRewrite(),
00735 "BitvectorTheoremProducer::generalIneqn: "
00736 "lhs_i and rhs_i must be rewrite theorems: "
00737 "\nlhs_i = " + lhs_i.toString() +
00738 "\nrhs_i = " + rhs_i.toString());
00739 }
00740
00741 int e0len = d_theoryBitvector->BVSize(e[0]);
00742 int e1len = d_theoryBitvector->BVSize(e[1]);
00743 const Expr& e0_iBit = lhs_i.getLHS();
00744 const Expr& e1_iBit = rhs_i.getLHS();
00745 if(CHECK_PROOFS) {
00746 CHECK_SOUND(BOOLEXTRACT == e0_iBit.getOpKind() &&
00747 BOOLEXTRACT == e1_iBit.getOpKind(),
00748 "BitvectorTheoremProducer::generalIneqn: "
00749 "lhs_i.getRHS() and rhs_i.getRHS() must be BOOLEXTRACTs:"
00750 "\nlhs_i = " + lhs_i.toString() +
00751 "\nrhs_i = " + rhs_i.toString());
00752 CHECK_SOUND(e[0] == e0_iBit[0],
00753 "BitvectorTheoremProducer::generalIneqn: "
00754 "e[0] must be equal to LHS of lhs_i: \nlhs_i = " +
00755 lhs_i.toString() + "\n e[0] = " + e[0].toString());
00756 CHECK_SOUND(e[1] == e1_iBit[0],
00757 "BitvectorTheoremProducer::generalIneqn: "
00758 "e[1] must be equal to LHS of rhs_i: \nrhs_i = " +
00759 rhs_i.toString() + "\n e[1] = " + e[1].toString());
00760 CHECK_SOUND(e0len == e1len,
00761 "BitvectorTheoremProducer::generalIneqn: "
00762 "e[0] and e[1] must have the same bvLength:\ne = " +
00763 e.toString());
00764 int e0_iBitIndex =
00765 d_theoryBitvector->getBoolExtractIndex(e0_iBit);
00766 int e1_iBitIndex =
00767 d_theoryBitvector->getBoolExtractIndex(e1_iBit);
00768 CHECK_SOUND(e0_iBitIndex == e1_iBitIndex &&
00769 e0_iBitIndex == e0len-1,
00770 "BitvectorTheoremProducer::generalIneqn: "
00771 "e0_iBit & e1_iBit must have same extract index: "
00772 "\ne0_iBit = " + e0_iBit.toString() +
00773 "\ne1_iBit = " + e1_iBit.toString());
00774 }
00775
00776
00777
00778 const Expr& b1 = lhs_i.getRHS();
00779 const Expr& b2 = rhs_i.getRHS();
00780 const Expr& trueExpression = d_theoryBitvector->trueExpr();
00781 const Expr& falseExpression = d_theoryBitvector->falseExpr();
00782
00783 if(CHECK_PROOFS) {
00784 CHECK_SOUND(b1.getType().isBool(),
00785 "BitvectorTheoremProducer::generalIneqn: "
00786 "b1 must be a boolean type: "
00787 "\n b1 = " + b1.toString());
00788 CHECK_SOUND(b2.getType().isBool(),
00789 "BitvectorTheoremProducer::generalIneqn: "
00790 "b2 must be boolean type: "
00791 "\n b2 = " + b2.toString());
00792 }
00793
00794 Expr output;
00795
00796 if(b1.isFalse() && b2.isTrue())
00797 output = trueExpression;
00798 else if(b1.isTrue() && b2.isFalse())
00799 output = falseExpression;
00800
00801
00802
00803
00804
00805
00806
00807
00808
00809 if(output.isNull()) {
00810
00811
00812 Expr b1_0 = b1.notExpr();
00813
00814
00815 Expr b2_1 = b2;
00816
00817 Expr b1_eq_b2 = b1.iffExpr(b2);
00818
00819
00820 output = (kind==BVLT) ?
00821 b1_0.andExpr(b2_1) :
00822 (e0len==1) ? b1_0.orExpr(b2_1) : b1_0.andExpr(b2_1);
00823
00824
00825
00826 if(e0len > 1) {
00827
00828 Expr e0_extract =
00829 d_theoryBitvector->newBVExtractExpr(e[0],e0len-2,0);
00830
00831 Expr e1_extract =
00832 d_theoryBitvector->newBVExtractExpr(e[1],e1len-2,0);
00833
00834 Expr a;
00835 if(kind==BVLT)
00836
00837 a = d_theoryBitvector->newBVLTExpr(e0_extract,e1_extract);
00838 else
00839
00840 a = d_theoryBitvector->newBVLEExpr(e0_extract,e1_extract);
00841
00842
00843 Expr b1_eq_b2_and_a = b1_eq_b2.andExpr(a);
00844
00845 output = output.orExpr(b1_eq_b2_and_a);
00846 }
00847 }
00848
00849 Proof pf;
00850 if(withProof())
00851 pf = newPf("general_ineqn", e);
00852 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
00853 }
00854
00855
00856
00857
00858
00859
00860 Theorem BitvectorTheoremProducer::bitExtractToExtract(const Theorem& thm) {
00861 const Expr& e = thm.getExpr();
00862 if(CHECK_PROOFS) {
00863 CHECK_SOUND((e.isNot() && e[0].getOpKind() == BOOLEXTRACT)
00864 || (e.getOpKind() == BOOLEXTRACT),
00865 "BitvectorTheoremProducer::bitExtractToExtract:\n e = "
00866 +e.toString());
00867 }
00868 bool negative = e.isNot();
00869 const Expr& boolExtract = negative? e[0] : e;
00870 int i = d_theoryBitvector->getBoolExtractIndex(boolExtract);
00871 Expr lhs = d_theoryBitvector->newBVExtractExpr(boolExtract[0], i, i);
00872
00873 Proof pf;
00874 if(withProof())
00875 pf = newPf("bit_extract_to_extract", e, thm.getProof());
00876 return newRWTheorem(lhs, negative? bvZero() : bvOne(), thm.getAssumptionsRef(), pf);
00877 }
00878
00879
00880
00881 Theorem BitvectorTheoremProducer::bitExtractRewrite(const Expr& x) {
00882 if(CHECK_PROOFS) {
00883 CHECK_SOUND(x.getOpKind() == BOOLEXTRACT,
00884 "BitvectorTheoremProducer::bitExtractRewrite: x = "
00885 +x.toString());
00886 }
00887
00888 int i = d_theoryBitvector->getBoolExtractIndex(x);
00889 const Expr& t = x[0];
00890 int bvLength = d_theoryBitvector->BVSize(t);
00891
00892 if(CHECK_PROOFS) {
00893 CHECK_SOUND(0<=i && i<bvLength,
00894 "BitvectorTheoremProducer::bitExtractRewrite:"
00895 "\n bvLength = "
00896 + int2string(bvLength)
00897 +"\n i = "+ int2string(i)
00898 +"\n x = "+ x.toString());
00899 }
00900 Proof pf;
00901 if(withProof())
00902 pf = newPf("bit_extract_rewrite", x);
00903 Expr res = d_theoryBitvector->newBVExtractExpr(t, i, i);
00904 res = d_theoryBitvector->newBoolExtractExpr(res, 0);
00905 return newRWTheorem(x, res, Assumptions::emptyAssump(), pf);
00906 }
00907
00908
00909 Theorem BitvectorTheoremProducer::bitExtractConstant(const Expr & x,
00910 int i)
00911 {
00912 TRACE("bitvector", "bitExtractConstant(", x, ", "+ int2string(i) +" ) {");
00913 if(CHECK_PROOFS) {
00914
00915 CHECK_SOUND(BVCONST == x.getKind(),
00916 "BitvectorTheoremProducer::bitExtractConstant:"
00917 "the bitvector must be a constant.");
00918
00919 CHECK_SOUND(0 <= i && (unsigned)i < d_theoryBitvector->getBVConstSize(x),
00920 "BitvectorTheoremProducer::bitExtractConstant:"
00921 "illegal extraction attempted on the bitvector x = "
00922 + x.toString()
00923 + "\nat the position i = "
00924 + int2string(i));
00925 }
00926
00927 const Expr bitExtract = d_theoryBitvector->newBoolExtractExpr(x, i);
00928
00929
00930
00931
00932 Expr output;
00933 if(!d_theoryBitvector->getBVConstValue(x, i))
00934 output = d_theoryBitvector->falseExpr();
00935 else
00936 output = d_theoryBitvector->trueExpr();
00937
00938 Proof pf;
00939 if(withProof()) pf = newPf("bit_extract_constant", x, rat(i));
00940 Theorem result(newRWTheorem(bitExtract,output,Assumptions::emptyAssump(),pf));
00941 TRACE("bitvector", "bitExtractConstant => ", result, " }");
00942 return result;
00943 }
00944
00945
00946 Theorem BitvectorTheoremProducer::bitExtractConcatenation(const Expr & x,
00947 int i) {
00948 TRACE("bitvector", "bitExtractConcatenation(",
00949 x.toString(), ", "+ int2string(i) + " ) {");
00950 Type type = d_theoryBitvector->getBaseType(x);
00951 if(CHECK_PROOFS) {
00952
00953 CHECK_SOUND(BITVECTOR == type.getExpr().getOpKind(),
00954 "BitvectorTheoremProducer::bitExtractConcatenation: "
00955 "term must be bitvector:\n x = "+x.toString());
00956 CHECK_SOUND(CONCAT == x.getOpKind() && x.arity() >= 2,
00957 "BitvectorTheoremProducer::bitExtractConcatenation: "
00958 "the bitvector must be a concat:\n x = " + x.toString());
00959 }
00960
00961
00962 int bvLength = d_theoryBitvector->BVSize(x);
00963 if(CHECK_PROOFS) {
00964 CHECK_SOUND(0 <= i && i < bvLength,
00965 "BitvectorTheoremProducer::bitExtractNot:"
00966 "illegal boolean extraction was attempted at position i = "
00967 + int2string(i)
00968 + "\non bitvector x = " + x.toString()
00969 + "\nwhose bvLength is = " +
00970 int2string(bvLength));
00971 }
00972
00973
00974 const Expr bitExtract = d_theoryBitvector->newBoolExtractExpr(x, i);
00975
00976 int numOfKids = x.arity();
00977 int lenOfKidsSeen = 0;
00978 Expr bitExtractKid;
00979 for(int count = numOfKids-1; count >= 0; --count) {
00980 int bvLengthOfKid = d_theoryBitvector->BVSize(x[count]);
00981 if(lenOfKidsSeen <= i && i < bvLengthOfKid + lenOfKidsSeen) {
00982 bitExtractKid =
00983 d_theoryBitvector->newBoolExtractExpr(x[count], i - lenOfKidsSeen);
00984 break;
00985 }
00986 lenOfKidsSeen += bvLengthOfKid;
00987 }
00988 DebugAssert(!bitExtractKid.isNull(),
00989 "BitvectorTheoremProducer::bitExtractConcatenation: "
00990 "something's broken...");
00991
00992 Proof pf;
00993 if(withProof())
00994 pf = newPf("bit_extract_concatenation", x, rat(i));
00995 Theorem result(newRWTheorem(bitExtract, bitExtractKid, Assumptions::emptyAssump(), pf));
00996 TRACE("bitvector", "bitExtractConcatenation => ", result, " }");
00997 return result;
00998 }
00999
01000 Theorem BitvectorTheoremProducer::bitExtractConstBVMult(const Expr& t,
01001 int i)
01002 {
01003 TRACE("bitvector", "input to bitExtractConstBVMult(", t.toString(), ")");
01004 TRACE("bitvector", "input to bitExtractConstBVMult(", int2string(i), ")");
01005
01006 Type type = t.getType();
01007 int bvLength = d_theoryBitvector->BVSize(t);
01008 if(CHECK_PROOFS) {
01009 CHECK_SOUND(BITVECTOR == type.getExpr().getOpKind(),
01010 "BitvectorTheoremProducer::bitExtractConstBVMult:"
01011 "the term must be a bitvector" + t.toString());
01012 CHECK_SOUND(BVMULT == t.getOpKind() && 2 == t.arity(),
01013 "BitvectorTheoremProducer::bitExtractConstBVMult:"
01014 "the term must be a bitvector" + t.toString());
01015
01016 CHECK_SOUND(0 <= i && i < bvLength,
01017 "BitvectorTheoremProducer::bitExtractNot:"
01018 "illegal boolean extraction was attempted at position i = "
01019 + int2string(i)
01020 + "\non bitvector x = " + t.toString()
01021 + "\nwhose bvLength is = " +
01022 int2string(bvLength));
01023 CHECK_SOUND(BVCONST == t[0].getKind(),
01024 "BitvectorTheoremProducer::bitExtractConstBVMult:"
01025 "illegal BVMULT expression" + t.toString());
01026 }
01027 int len = d_theoryBitvector->BVSize(t[0]);
01028 std::vector<Expr> k;
01029 Expr t1 = pad(bvLength, t[1]);
01030 for(int j=0; j < len; ++j)
01031 if (d_theoryBitvector->getBVConstValue(t[0], j)) {
01032 Expr leftshiftTerm =
01033 d_theoryBitvector->newFixedConstWidthLeftShiftExpr(t1, j);
01034 k.push_back(leftshiftTerm);
01035 }
01036
01037 Expr mult;
01038
01039 switch(k.size()) {
01040 case 0:
01041
01042 mult = d_theoryBitvector->newBVZeroString(bvLength);
01043 break;
01044 case 1:
01045 mult = k[0];
01046 break;
01047 default:
01048 mult = d_theoryBitvector->newBVPlusExpr(bvLength, k);
01049 break;
01050 }
01051 Expr output = d_theoryBitvector->newBoolExtractExpr(mult, i);
01052
01053
01054 const Expr bitExtract =
01055 d_theoryBitvector->newBoolExtractExpr(t, i);
01056
01057 Proof pf;
01058 if(withProof()) pf = newPf("bit_extract_const_bvmult", t, rat(i));
01059 const Theorem result = newRWTheorem(bitExtract,output,Assumptions::emptyAssump(),pf);
01060 TRACE("bitvector",
01061 "output of bitExtract_const_bvmult(", result, ")");
01062 return result;
01063 }
01064
01065
01066 Theorem BitvectorTheoremProducer::bitExtractBVMult(const Expr& t,
01067 int i)
01068 {
01069 TRACE("bitvector", "input to bitExtractBVMult(", t.toString(), ")");
01070 TRACE("bitvector", "input to bitExtractBVMult(", int2string(i), ")");
01071
01072 Type type = t.getType();
01073 if(CHECK_PROOFS) {
01074 CHECK_SOUND(BITVECTOR == type.getExpr().getOpKind(),
01075 "BitvectorTheoremProducer::bitExtractBVMult:"
01076 "the term must be a bitvector" + t.toString());
01077 CHECK_SOUND(BVMULT == t.getOpKind() && 2 == t.arity(),
01078 "BitvectorTheoremProducer::bitExtractBVMult:"
01079 "the term must be a bitvector" + t.toString());
01080 int bvLength= d_theoryBitvector->BVSize(t);
01081 CHECK_SOUND(0 <= i && i < bvLength,
01082 "BitvectorTheoremProducer::bitExtractNot:"
01083 "illegal boolean extraction was attempted at position i = "
01084 + int2string(i)
01085 + "\non bitvector t = " + t.toString()
01086 + "\nwhose Length is = " +
01087 int2string(bvLength));
01088 CHECK_SOUND(BVCONST != t[0].getOpKind(),
01089 "BitvectorTheoremProducer::bitExtractBVMult:"
01090 "illegal BVMULT expression" + t.toString());
01091 }
01092 int len = d_theoryBitvector->BVSize(t[0]);
01093 Expr trueExpression = d_theoryBitvector->trueExpr();
01094 std::vector<Expr> k;
01095 for(int j=len-1; j >= 0; j--) {
01096 Expr boolExt = d_theoryBitvector->newBoolExtractExpr(t[0],j);
01097 Expr cond = trueExpression.iffExpr(boolExt);
01098 Expr lShiftTerm = d_theoryBitvector->newFixedLeftShiftExpr(t[1], j);
01099 int shiftLen = d_theoryBitvector->BVSize(lShiftTerm);
01100 Expr zeroString = d_theoryBitvector->newBVZeroString(shiftLen);
01101 Expr iteTerm = cond.iteExpr(lShiftTerm, zeroString);
01102 k.push_back(iteTerm);
01103 }
01104
01105 if(CHECK_PROOFS)
01106 CHECK_SOUND(k.size() > 0,
01107 "BitvectorTheoremProducer::bitExtractBVMult:"
01108 "size of output vector must be > 0");
01109
01110 int bvLength = d_theoryBitvector->BVSize(t);
01111 Expr mult;
01112 if(k.size() >= 2)
01113 mult = d_theoryBitvector->newBVPlusExpr(bvLength, k);
01114 else
01115 mult = k[0];
01116 Expr output = d_theoryBitvector->newBoolExtractExpr(mult, i);
01117
01118
01119 const Expr bitExtract = d_theoryBitvector->newBoolExtractExpr(t, i);
01120
01121 Proof pf;
01122 if(withProof()) pf = newPf("bit_extract_bvmult", t, rat(i));
01123 const Theorem result = newRWTheorem(bitExtract,output,Assumptions::emptyAssump(),pf);
01124 TRACE("bitvector","output of bitExtract_bvmult(", result, ")");
01125 return result;
01126 }
01127
01128 Theorem BitvectorTheoremProducer::bitExtractExtraction(const Expr & x,
01129 int i)
01130 {
01131 TRACE("bitvector", "input to bitExtractExtraction(", x.toString(), ")");
01132 TRACE("bitvector", "input to bitExtractExtraction(", int2string(i), ")");
01133
01134 Type type = x.getType();
01135 if(CHECK_PROOFS) {
01136
01137 CHECK_SOUND(BITVECTOR == type.getExpr().getOpKind(),
01138 "BitvectorTheoremProducer::bitExtract-Extraction:"
01139 "term must be bitvector.");
01140 CHECK_SOUND(EXTRACT == x.getOpKind() && 1 == x.arity(),
01141 "BitvectorTheoremProducer::bitExtract-Extraction:"
01142 "the bitvector must be an extract." + x.toString());
01143
01144 int bvLength= d_theoryBitvector->BVSize(type.getExpr());
01145 CHECK_SOUND(0 <= i && i < bvLength,
01146 "BitvectorTheoremProducer::bitExtractNot:"
01147 "illegal boolean extraction was attempted at position i = "
01148 + int2string(i)
01149 + "\non bitvector t = " + x.toString()
01150 + "\nwhose Length is = " +
01151 int2string(bvLength));
01152 int extractLeft = d_theoryBitvector->getExtractHi(x);
01153 int extractRight = d_theoryBitvector->getExtractLow(x);
01154 CHECK_SOUND(extractLeft >= extractRight && extractLeft >= 0,
01155 "BitvectorTheoremProducer::bitExtract-Extraction:"
01156 "illegal boolean extraction was attempted." + int2string(i) +
01157 int2string(extractLeft) + int2string(extractRight));
01158 CHECK_SOUND(0 <= i && i < extractLeft-extractRight+1,
01159 "BitvectorTheoremProducer::bitExtract-Extraction:"
01160 "illegal boolean extraction was attempted." + int2string(i) +
01161 int2string(extractLeft) + int2string(extractRight));
01162 }
01163
01164 const Expr bitExtract = d_theoryBitvector->newBoolExtractExpr(x, i);
01165 const Expr bitExtractExtraction =
01166 d_theoryBitvector->newBoolExtractExpr(x[0], i +
01167 d_theoryBitvector->getExtractLow(x));
01168
01169 Proof pf;
01170 if(withProof()) pf = newPf("bit_extract_extraction", x, rat(i));
01171 Theorem result(newRWTheorem(bitExtract, bitExtractExtraction, Assumptions::emptyAssump(), pf));
01172 TRACE("bitvector",
01173 "output of bitExtractExtraction(", result, ")");
01174 return result;
01175 }
01176
01177 Theorem
01178 BitvectorTheoremProducer::
01179 bitExtractBVPlus(const std::vector<Theorem>& t1BitExtractThms,
01180 const std::vector<Theorem>& t2BitExtractThms,
01181 const Expr& bvPlusTerm, int bitPos)
01182 {
01183 TRACE("bitvector","input to bitExtractBVPlus(", bvPlusTerm.toString(), ")");
01184 TRACE("bitvector","input to bitExtractBVPlus(", int2string(bitPos), ")");
01185
01186 if(CHECK_PROOFS) {
01187 CHECK_SOUND(BVPLUS == bvPlusTerm.getOpKind() && 2 == bvPlusTerm.arity(),
01188 "BitvectorTheoremProducer::bitExtractBVPlus:"
01189 "illegal bitvector fed to the function." +
01190 bvPlusTerm.toString());
01191 CHECK_SOUND(d_theoryBitvector->getBVPlusParam(bvPlusTerm) >= 0,
01192 "BitvectorTheoremProducer::bitExtractBVPlus:"
01193 "illegal bitvector fed to the function." +
01194 bvPlusTerm.toString());
01195 CHECK_SOUND(bitPos+1 == (int)t1BitExtractThms.size() &&
01196 bitPos+1 == (int)t2BitExtractThms.size(),
01197 "BitvectorTheoremProducer::bitExtractBVPlus:"
01198 "illegal bitvector fed to the function." +
01199 int2string(bitPos));
01200 const Expr& t1 = bvPlusTerm[0];
01201 const Expr& t2 = bvPlusTerm[1];
01202 std::vector<Theorem>::const_iterator i = t1BitExtractThms.begin();
01203 std::vector<Theorem>::const_iterator iend = t1BitExtractThms.end();
01204 std::vector<Theorem>::const_iterator j = t2BitExtractThms.begin();
01205 for(; i !=iend; ++i, ++j) {
01206 const Expr& t1Expr = i->getLHS();
01207 const Expr& t2Expr = j->getLHS();
01208 CHECK_SOUND(t1Expr[0] == t1 && t2Expr[0] == t2,
01209 "BitvectorTheoremProducer::bitExtractBVPlus:"
01210 "illegal bitvector fed to the function." +
01211 t1Expr.toString() + " ==\n" +
01212 t1.toString() + "\n" +
01213 t2.toString() + " == \n" +
01214 t2Expr.toString());
01215 }
01216 }
01217 const Expr lhs =
01218 d_theoryBitvector->newBoolExtractExpr(bvPlusTerm, bitPos);
01219 Expr rhs;
01220 const Expr& t1_iBit = (t1BitExtractThms[bitPos]).getRHS();
01221 const Expr& t2_iBit = (t2BitExtractThms[bitPos]).getRHS();
01222 if(0 != bitPos) {
01223 const Expr carry_iBit =
01224 computeCarry(t1BitExtractThms, t2BitExtractThms, bitPos);
01225
01226
01227
01228
01229 rhs = t1_iBit.iffExpr(t2_iBit).iffExpr(carry_iBit);
01230
01231
01232
01233 } else
01234
01235 rhs = !(t1_iBit.iffExpr(t2_iBit));
01236
01237 Proof pf;
01238 if(withProof())
01239 pf = newPf("bit_extract_BVPlus_rule",bvPlusTerm,rat(bitPos));
01240 Theorem result = newRWTheorem(lhs, rhs, Assumptions::emptyAssump(), pf);
01241 TRACE("bitvector","output of bitExtractBVPlus(", result, ")");
01242 return result;
01243 }
01244
01245 Expr
01246 BitvectorTheoremProducer::
01247 computeCarry(const std::vector<Theorem>& t1BitExtractThms,
01248 const std::vector<Theorem>& t2BitExtractThms,
01249 int i){
01250 vector<Expr> carry;
01251 int bitPos = i;
01252 DebugAssert(bitPos >= 0,
01253 "computeCarry: negative bitExtract_Pos is illegal");
01254 if(0 == bitPos) {
01255 const Expr& t1Thm = t1BitExtractThms[bitPos].getRHS();
01256 const Expr& t2Thm = t2BitExtractThms[bitPos].getRHS();
01257 carry.push_back(t1Thm.andExpr(t2Thm));
01258 }
01259 else {
01260 const Expr& t1Thm = t1BitExtractThms[bitPos-1].getRHS();
01261 const Expr& t2Thm = t2BitExtractThms[bitPos-1].getRHS();
01262 const Expr iMinusOneTerm = t1Thm.andExpr(t2Thm);
01263 carry.push_back(iMinusOneTerm);
01264
01265 const Expr iMinusOneCarry =
01266 computeCarry(t1BitExtractThms,t2BitExtractThms,bitPos-1);
01267 const Expr secondTerm = t1Thm.andExpr(iMinusOneCarry);
01268 carry.push_back(secondTerm);
01269
01270 const Expr thirdTerm = t2Thm.andExpr(iMinusOneCarry);
01271
01272 carry.push_back(thirdTerm);
01273 }
01274 return orExpr(carry);
01275 }
01276
01277 Theorem
01278 BitvectorTheoremProducer::
01279 bitExtractBVPlusPreComputed(const Theorem& t1_i,
01280 const Theorem& t2_i,
01281 const Expr& bvPlusTerm,
01282 int bitPos,
01283 int precomputedFlag)
01284 {
01285 DebugAssert(0 != precomputedFlag,
01286 "precomputedFlag cannot be 0");
01287 TRACE("bitvector","input to bitExtractBVPlus(", bvPlusTerm.toString(), ")");
01288 TRACE("bitvector","input to bitExtractBVPlus(", int2string(bitPos), ")");
01289
01290 if(CHECK_PROOFS) {
01291 CHECK_SOUND(BVPLUS == bvPlusTerm.getOpKind() && 2 == bvPlusTerm.arity(),
01292 "BitvectorTheoremProducer::bitExtractBVPlus:"
01293 "illegal bitvector fed to the function." +
01294 bvPlusTerm.toString());
01295 CHECK_SOUND(d_theoryBitvector->getBVPlusParam(bvPlusTerm) >= 0,
01296 "BitvectorTheoremProducer::bitExtractBVPlus:"
01297 "illegal bitvector fed to the function." +
01298 bvPlusTerm.toString());
01299 const Expr& t1 = bvPlusTerm[0];
01300 const Expr& t2 = bvPlusTerm[1];
01301 CHECK_SOUND(t1_i.getLHS()[0] == t1 &&
01302 t2_i.getLHS()[0] == t2,
01303 "BitvectorTheoremProducer::bitExtractBVPlus:"
01304 "illegal theorems fed to the function. Theorem1 = " +
01305 t1_i.toString() + "\nTheorem2 = " + t2_i.toString());
01306 CHECK_SOUND(t1_i.getLHS().getOpKind() == BOOLEXTRACT &&
01307 t2_i.getLHS().getOpKind() == BOOLEXTRACT,
01308 "BitvectorTheoremProducer::bitExtractBVPlus:"
01309 "illegal theorems fed to the function. Theorem1 = " +
01310 t1_i.toString() + "\nTheorem2 = " + t2_i.toString());
01311 CHECK_SOUND(d_theoryBitvector->getBoolExtractIndex(t1_i.getLHS()) == bitPos &&
01312 d_theoryBitvector->getBoolExtractIndex(t2_i.getLHS()) == bitPos,
01313 "BitvectorTheoremProducer::bitExtractBVPlus:"
01314 "illegal theorems fed to the function. Theorem1 = " +
01315 t1_i.toString() + "\nTheorem2 = " + t2_i.toString());
01316 }
01317 const Expr lhs =
01318 d_theoryBitvector->newBoolExtractExpr(bvPlusTerm, bitPos);
01319 Expr rhs;
01320 const Expr& t1_iBit = t1_i.getRHS();
01321 const Expr& t2_iBit = t2_i.getRHS();
01322
01323 const Expr carry_iBit = computeCarryPreComputed(t1_i, t2_i, bitPos, precomputedFlag);
01324
01325 if(0 != bitPos) {
01326
01327
01328
01329
01330 rhs = t1_iBit.iffExpr(t2_iBit).iffExpr(carry_iBit);
01331
01332 } else
01333
01334 rhs = !(t1_iBit.iffExpr(t2_iBit));
01335
01336 Proof pf;
01337 if(withProof())
01338 pf = newPf("bit_extract_BVPlus_precomputed_rule",bvPlusTerm,rat(bitPos));
01339 Theorem result = newRWTheorem(lhs, rhs, Assumptions::emptyAssump(), pf);
01340 TRACE("bitvector","output of bitExtractBVPlus(", result, ")");
01341 return result;
01342 }
01343
01344
01345
01346 Expr
01347 BitvectorTheoremProducer::
01348 computeCarryPreComputed(const Theorem& t1_i,
01349 const Theorem& t2_i,
01350 int bitPos, int preComputed){
01351 DebugAssert(1 == preComputed ||
01352 2 == preComputed,
01353 "cannot happen");
01354 Expr carryout;
01355 Expr carryin;
01356 DebugAssert(bitPos >= 0,
01357 "computeCarry: negative bitExtract_Pos is illegal");
01358
01359 const Expr& t1Thm = t1_i.getRHS();
01360 const Expr& t2Thm = t2_i.getRHS();
01361 Expr x = t1Thm.andExpr(t2Thm);
01362 const Expr& t1 = t1_i.getLHS()[0];
01363 const Expr& t2 = t2_i.getLHS()[0];
01364 Expr t1Andt2 = t1.andExpr(t2);
01365 Expr index = t1Andt2.andExpr(rat(bitPos));
01366
01367 if(0 == bitPos) {
01368 if(1 == preComputed)
01369 d_theoryBitvector->d_bvPlusCarryCacheLeftBV.insert(index,x);
01370 else
01371 d_theoryBitvector->d_bvPlusCarryCacheRightBV.insert(index,x);
01372 carryout = x;
01373
01374 }
01375 else {
01376 if(1 == preComputed) {
01377 Expr indexMinusOne = t1Andt2.andExpr(rat(bitPos-1));
01378 if(d_theoryBitvector->d_bvPlusCarryCacheLeftBV.find(indexMinusOne) ==
01379 d_theoryBitvector->d_bvPlusCarryCacheLeftBV.end())
01380 DebugAssert(false,
01381 "this should not happen");
01382 carryin =
01383 (d_theoryBitvector->d_bvPlusCarryCacheLeftBV).find(indexMinusOne)->second;
01384 Expr secondTerm = t1Thm.andExpr(carryin);
01385 Expr thirdTerm = t2Thm.andExpr(carryin);
01386
01387 carryout = (x.orExpr(secondTerm)).orExpr(thirdTerm);
01388 d_theoryBitvector->d_bvPlusCarryCacheLeftBV.insert(index,carryout);
01389 }
01390 else {
01391 Expr indexMinusOne = t1Andt2.andExpr(rat(bitPos-1));
01392 if(d_theoryBitvector->d_bvPlusCarryCacheRightBV.find(indexMinusOne) ==
01393 d_theoryBitvector->d_bvPlusCarryCacheRightBV.end())
01394 DebugAssert(false,
01395 "this should not happen");
01396 carryin =
01397 (d_theoryBitvector->d_bvPlusCarryCacheRightBV).find(indexMinusOne)->second;
01398
01399 Expr secondTerm = t1Thm.andExpr(carryin);
01400 Expr thirdTerm = t2Thm.andExpr(carryin);
01401
01402 carryout = (x.orExpr(secondTerm)).orExpr(thirdTerm);
01403 d_theoryBitvector->d_bvPlusCarryCacheRightBV.insert(index,carryout);
01404 }
01405 }
01406
01407 return carryin;
01408 }
01409
01410 Theorem
01411 BitvectorTheoremProducer::
01412 zeroPaddingRule(const Expr& e, int i) {
01413 if(CHECK_PROOFS) {
01414 CHECK_SOUND(BITVECTOR == e.getType().getExpr().getOpKind(),
01415 "BitvectorTheoremProducer::zeroPaddingRule:"
01416 "Wrong Input: Input must be a bitvector. But the input is: " +
01417 e.toString());
01418 }
01419
01420 int bvLength =
01421 d_theoryBitvector->BVSize(d_theoryBitvector->getBaseType(e).getExpr());
01422
01423 if(CHECK_PROOFS) {
01424 CHECK_SOUND(0 <= i && i >= bvLength,
01425 "BitvectorTheoremProducer::zeroPaddingRule:"
01426 "bitPosition of extraction must be greater than bvLength" +
01427 int2string(i) + "bvLength:" + int2string(bvLength));
01428 }
01429 const Expr boolExtractExpr = d_theoryBitvector->newBoolExtractExpr(e, i);
01430
01431 Proof pf;
01432 if(withProof())
01433 pf = newPf("zeropadding_rule", e, rat(i));
01434 return newRWTheorem(boolExtractExpr, d_theoryBitvector->falseExpr(), Assumptions::emptyAssump(), pf);
01435 }
01436
01437 Theorem
01438 BitvectorTheoremProducer::
01439 bvPlusAssociativityRule(const Expr& bvPlusTerm)
01440 {
01441 TRACE("bitvector",
01442 "input to bvPlusAssociativityRule(", bvPlusTerm.toString(), ")");
01443
01444 Type type = bvPlusTerm.getType();
01445 if(CHECK_PROOFS) {
01446 CHECK_SOUND(BITVECTOR == type.getExpr().getOpKind(),
01447 "BitvectorTheoremProducer::bvPlusAssociativityRule:"
01448 "term must be BITVECTOR type.");
01449 CHECK_SOUND(BVPLUS == bvPlusTerm.getOpKind(),
01450 "BitvectorTheoremProducer::bvPlusAssociativityRule:"
01451 "term must have the kind BVPLUS.");
01452 CHECK_SOUND(2 < bvPlusTerm.arity(),
01453 "BitvectorTheoremProducer::bvPlusAssociativityRule:"
01454 "term must have arity() greater than 2 for associativity.");
01455 }
01456 std::vector<Expr> BVPlusTerms0;
01457 std::vector<Expr>::const_iterator j = (bvPlusTerm.getKids()).begin();
01458 std::vector<Expr>::const_iterator jend = (bvPlusTerm.getKids()).end();
01459
01460 j++;
01461 BVPlusTerms0.insert(BVPlusTerms0.end(), j, jend);
01462 int bvLength = d_theoryBitvector->BVSize(bvPlusTerm);
01463 const Expr bvplus0 = d_theoryBitvector->newBVPlusExpr(bvLength,
01464 BVPlusTerms0);
01465
01466 std::vector<Expr> BVPlusTerms1;
01467 BVPlusTerms1.push_back(*((bvPlusTerm.getKids()).begin()));
01468 BVPlusTerms1.push_back(bvplus0);
01469 const Expr bvplusOutput = d_theoryBitvector->newBVPlusExpr(bvLength,
01470 BVPlusTerms1);
01471
01472 Proof pf;
01473 if(withProof()) pf = newPf("bv_plus_associativityrule", bvPlusTerm);
01474 const Theorem result(newRWTheorem(bvPlusTerm, bvplusOutput, Assumptions::emptyAssump(), pf));
01475 TRACE("bitvector",
01476 "output of bvPlusAssociativityRule(", result, ")");
01477 return result;
01478 }
01479
01480
01481 Theorem BitvectorTheoremProducer::bitExtractNot(const Expr & x,
01482 int i) {
01483 TRACE("bitvector", "input to bitExtractNot(", x.toString(), ")");
01484 TRACE("bitvector", "input to bitExtractNot(", int2string(i), ")");
01485
01486 Type type = x.getType();
01487 if(CHECK_PROOFS) {
01488
01489 CHECK_SOUND(BITVECTOR == type.getExpr().getOpKind(),
01490 "BitvectorTheoremProducer::bitExtractNot:"
01491 "term must be bitvector.");
01492 CHECK_SOUND(BVNEG == x.getOpKind() && 1 == x.arity(),
01493 "BitvectorTheoremProducer::bitExtractNot:"
01494 "the bitvector must be an bitwise negation." + x.toString());
01495
01496 int bvLength= d_theoryBitvector->BVSize(type.getExpr());
01497 CHECK_SOUND(0 <= i && i < bvLength,
01498 "BitvectorTheoremProducer::bitExtractNot:"
01499 "illegal boolean extraction was attempted at position i = "
01500 + int2string(i)
01501 + "\non bitvector x = " + x.toString()
01502 + "\nwhose Length is = " +
01503 int2string(bvLength));
01504 }
01505
01506 const Expr bitExtract = d_theoryBitvector->newBoolExtractExpr(x, i);
01507 const Expr bitNegTerm = d_theoryBitvector->newBoolExtractExpr(x[0], i);
01508
01509 Proof pf;
01510 if(withProof()) pf = newPf("bit_extract_bitwiseneg", x, rat(i));
01511 const Theorem result(newRWTheorem(bitExtract,!bitNegTerm,Assumptions::emptyAssump(),pf));
01512 TRACE("bitvector","output of bitExtractNot(", result, ")");
01513 return result;
01514 }
01515
01516 Theorem
01517 BitvectorTheoremProducer::bitExtractBitwise(const Expr & x,
01518 int i, int kind) {
01519 string funName = (kind==BVAND)? "bitExtractAnd" : "bitExtractOr";
01520 string pfName = (kind==BVAND)? "bit_extract_and" : "bit_extract_or";
01521 TRACE("bitvector", funName+"(", x, ", "+ int2string(i)+") {");
01522 Type type = x.getType();
01523 if(CHECK_PROOFS) {
01524 CHECK_SOUND(kind == BVAND || kind == BVOR,
01525 "BitvectorTheoremProducer::"+funName+": kind = "
01526 +d_theoryBitvector->getEM()->getKindName(kind));
01527
01528 CHECK_SOUND(BITVECTOR == type.getExpr().getOpKind(),
01529 "BitvectorTheoremProducer::"+funName+": "
01530 "term must be bitvector.\n x = "+x.toString()
01531 +" : "+type.toString());
01532 CHECK_SOUND(x.getOpKind() == kind && 2 <= x.arity(),
01533 "BitvectorTheoremProducer::"+funName+": "
01534 "the bitvector must be a bitwise AND.\n x = "
01535 + x.toString());
01536
01537 int size = d_theoryBitvector->BVSize(x);
01538 CHECK_SOUND(0 <= i && i < size,
01539 "BitvectorTheoremProducer::"+funName+": "
01540 "illegal boolean extraction was attempted.\n i = "
01541 + int2string(i) + "\n size = "+ int2string(size));
01542 }
01543
01544 const Expr bitExtract = d_theoryBitvector->newBoolExtractExpr(x, i);
01545 vector<Expr> kids;
01546 for(Expr::iterator j=x.begin(), jend=x.end(); j!=jend; ++j) {
01547 kids.push_back(d_theoryBitvector->newBoolExtractExpr(*j, i));
01548 }
01549
01550 Expr rhs = (kind==BVAND)? andExpr(kids) : orExpr(kids);
01551
01552 Proof pf;
01553 if(withProof()) pf = newPf(pfName,x,rat(i));
01554 const Theorem result(newRWTheorem(bitExtract, rhs, Assumptions::emptyAssump(), pf));
01555 TRACE("bitvector", funName+" => ", result.toString(), " }");
01556 return result;
01557 }
01558
01559
01560 Theorem
01561 BitvectorTheoremProducer::bitExtractAnd(const Expr & x, int i) {
01562 return bitExtractBitwise(x, i, BVAND);
01563 }
01564
01565
01566 Theorem
01567 BitvectorTheoremProducer::bitExtractOr(const Expr & x, int i) {
01568 return bitExtractBitwise(x, i, BVOR);
01569 }
01570
01571
01572 Theorem BitvectorTheoremProducer::bitExtractFixedLeftShift(const Expr & x,
01573 int i) {
01574 TRACE("bitvector", "input to bitExtractFixedleftshift(", x.toString(), ")");
01575 TRACE("bitvector", "input to bitExtractFixedleftshift(", int2string(i), ")");
01576
01577 Type type = x.getType();
01578 if(CHECK_PROOFS) {
01579
01580 CHECK_SOUND(BITVECTOR == type.getExpr().getOpKind(),
01581 "BitvectorTheoremProducer::bitExtractFixedleftshift:"
01582 "term must be bitvector.");
01583 CHECK_SOUND((x.getOpKind() == LEFTSHIFT ||
01584 x.getOpKind() == CONST_WIDTH_LEFTSHIFT) && 1 == x.arity(),
01585 "BitvectorTheoremProducer::bitExtractFixedleftshift:"
01586 "the bitvector must be a bitwise LEFTSHIFT." +
01587 x.toString());
01588 CHECK_SOUND(d_theoryBitvector->getFixedLeftShiftParam(x) >= 0,
01589 "BitvectorTheoremProducer::bitExtractFixedleftshift:"
01590 "the bitvector must be a bitwise LEFTSHIFT." +
01591 x.toString());
01592
01593 int bvLength= d_theoryBitvector->BVSize(type.getExpr());
01594 CHECK_SOUND(0 <= i && i < bvLength,
01595 "BitvectorTheoremProducer::bitExtractNot:"
01596 "illegal boolean extraction was attempted at position i = "
01597 + int2string(i)
01598 + "\non bitvector x = " + x.toString()
01599 + "\nwhose bvLength is = " +
01600 int2string(bvLength));
01601 }
01602
01603 const Expr bitExtract = d_theoryBitvector->newBoolExtractExpr(x, i);
01604 int shiftLength = d_theoryBitvector->getFixedLeftShiftParam(x);
01605 Expr output;
01606 if(0 <= i && i < shiftLength)
01607 output = d_theoryBitvector->falseExpr();
01608 else
01609 output =
01610 d_theoryBitvector->newBoolExtractExpr(x[0], i-shiftLength);
01611
01612 Proof pf;
01613 if(withProof())
01614 pf = newPf("bit_extract_bitwisefixedleftshift", x,rat(i));
01615 const Theorem result = newRWTheorem(bitExtract, output, Assumptions::emptyAssump(), pf);
01616 TRACE("bitvector",
01617 "output of bitExtractFixedleftshift(", result, ")");
01618 return result;
01619 }
01620
01621 Theorem BitvectorTheoremProducer::bitExtractFixedRightShift(const Expr & x,
01622 int i) {
01623 TRACE("bitvector", "input to bitExtractFixedRightShift(", x.toString(), ")");
01624 TRACE("bitvector", "input to bitExtractFixedRightShift(", int2string(i), ")");
01625
01626 Type type = x.getType();
01627 if(CHECK_PROOFS) {
01628
01629 CHECK_SOUND(BITVECTOR == type.getExpr().getOpKind(),
01630 "BitvectorTheoremProducer::bitExtractFixedRightShift:"
01631 "term must be bitvector.");
01632 CHECK_SOUND(RIGHTSHIFT == x.getOpKind() && 1 == x.arity(),
01633 "BitvectorTheoremProducer::bitExtractFixedRightShift:"
01634 "the bitvector must be an bitwise RIGHTSHIFT." +
01635 x.toString());
01636 CHECK_SOUND(d_theoryBitvector->getFixedRightShiftParam(x) >= 0,
01637 "BitvectorTheoremProducer::bitExtractFixedRightShift:"
01638 "the bitvector must be an bitwise RIGHTSHIFT." +
01639 x.toString());
01640 }
01641
01642 int bvLength = d_theoryBitvector->BVSize(x);
01643 if(CHECK_PROOFS)
01644 CHECK_SOUND(0 <= i && i < bvLength,
01645 "BitvectorTheoremProducer::bitExtractNot:"
01646 "illegal boolean extraction was attempted at position i = "
01647 + int2string(i)
01648 + "\non bitvector t = " + x.toString()
01649 + "\nwhose Length is = " +
01650 int2string(bvLength));
01651
01652
01653 const Expr bitExtract = d_theoryBitvector->newBoolExtractExpr(x, i);
01654 int shiftLength = d_theoryBitvector->getFixedRightShiftParam(x);
01655 Expr output;
01656 if(bvLength > i && i > bvLength-shiftLength-1)
01657 output = d_theoryBitvector->falseExpr();
01658 else
01659 output =
01660 d_theoryBitvector->newBoolExtractExpr(x[0], i);
01661
01662 Proof pf;
01663 if(withProof())
01664 pf = newPf("bit_extract_bitwiseFixedRightShift", x,rat(i));
01665 const Theorem result = newRWTheorem(bitExtract, output, Assumptions::emptyAssump(), pf);
01666 TRACE("bitvector",
01667 "output of bitExtractFixedRightShift(", result, ")");
01668 return result;
01669 }
01670
01671
01672 static bool constantKids(const Expr& e) {
01673 for(Expr::iterator i=e.begin(), iend=e.end(); i!=iend; ++i)
01674 if(i->getOpKind() != BVCONST) return false;
01675 return true;
01676 }
01677
01678
01679
01680 Theorem BitvectorTheoremProducer::eqConst(const Expr& e) {
01681 if(CHECK_PROOFS) {
01682
01683 CHECK_SOUND(e.isEq(),
01684 "BitvectorTheoremProducer::eqConst: e = "+e.toString());
01685 CHECK_SOUND(constantKids(e),
01686 "BitvectorTheoremProducer::eqConst: e = "+e.toString());
01687 }
01688 Proof pf;
01689 if(withProof())
01690 pf = newPf("bitvector_eq_const", e);
01691 Expr res((e[0]==e[1])? d_theoryBitvector->trueExpr() :
01692 d_theoryBitvector->falseExpr());
01693 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
01694 }
01695
01696
01697
01698 Theorem BitvectorTheoremProducer::eqToBits(const Theorem& eq) {
01699 if(CHECK_PROOFS) {
01700 CHECK_SOUND(eq.isRewrite(),
01701 "BitvectorTheoremProducer::eqToBits: eq = "+eq.toString());
01702 }
01703
01704 const Expr& lhs = eq.getLHS();
01705 const Expr& rhs = eq.getRHS();
01706
01707 if(CHECK_PROOFS) {
01708 CHECK_SOUND(d_theoryBitvector->getBaseType(lhs).getExpr().getOpKind() == BITVECTOR,
01709 "BitvectorTheoremProducer::eqToBits: eq = "+eq.toString());
01710 CHECK_SOUND(d_theoryBitvector->BVSize(lhs)
01711 == d_theoryBitvector->BVSize(rhs),
01712 "BitvectorTheoremProducer::eqToBits: eq = "+eq.toString());
01713 }
01714
01715 int i=0, size=d_theoryBitvector->BVSize(lhs);
01716 vector<Expr> bitEqs;
01717 for(; i<size; i++) {
01718 Expr l = d_theoryBitvector->newBVExtractExpr(lhs, i, i);
01719 Expr r = d_theoryBitvector->newBVExtractExpr(rhs, i, i);
01720 bitEqs.push_back(l.eqExpr(r));
01721 }
01722 Expr res = andExpr(bitEqs);
01723 Proof pf;
01724 if(withProof())
01725 pf = newPf("eq_to_bits", eq.getExpr(), eq.getProof());
01726 return newTheorem(res, eq.getAssumptionsRef(), pf);
01727 }
01728
01729
01730
01731 Theorem BitvectorTheoremProducer::leftShiftToConcat(const Expr& e) {
01732 if(CHECK_PROOFS) {
01733
01734 CHECK_SOUND(e.getOpKind() == LEFTSHIFT && e.arity() == 1,
01735 "BitvectorTheoremProducer::leftShiftConst: e = "+e.toString());
01736 CHECK_SOUND(d_theoryBitvector->getFixedLeftShiftParam(e) >= 0,
01737 "BitvectorTheoremProducer::leftShiftConst: e = "+e.toString());
01738 }
01739 const Expr& e0 = e[0];
01740 Expr res(e0);
01741 int shiftSize=d_theoryBitvector->getFixedLeftShiftParam(e);
01742
01743 if (shiftSize != 0) {
01744 Expr padding = d_theoryBitvector->newBVConstExpr(Rational(0), shiftSize);
01745 res = d_theoryBitvector->newConcatExpr(e0, padding);
01746 }
01747
01748 Proof pf;
01749 if(withProof())
01750 pf = newPf("leftshift_to_concat", e);
01751 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
01752 }
01753
01754
01755 Theorem BitvectorTheoremProducer::constWidthLeftShiftToConcat(const Expr& e) {
01756 if(CHECK_PROOFS) {
01757
01758 CHECK_SOUND(e.getOpKind() == CONST_WIDTH_LEFTSHIFT && e.arity() == 1,
01759 "BitvectorTheoremProducer::leftShiftConst: e = "+e.toString());
01760 CHECK_SOUND(d_theoryBitvector->getFixedLeftShiftParam(e) >= 0,
01761 "BitvectorTheoremProducer::leftShiftConst: e = "+e.toString());
01762 }
01763 const Expr& e0 = e[0];
01764 Expr res;
01765
01766 int shiftSize=d_theoryBitvector->getFixedLeftShiftParam(e);
01767 if (shiftSize == 0)
01768 res = e0;
01769 else {
01770 int bvLength = d_theoryBitvector->BVSize(e);
01771 if (shiftSize >= bvLength)
01772 res = d_theoryBitvector->newBVConstExpr(Rational(0), bvLength);
01773 else {
01774 Expr padding = d_theoryBitvector->newBVConstExpr(Rational(0), shiftSize);
01775 res = d_theoryBitvector->newBVExtractExpr(e0, bvLength-shiftSize-1, 0);
01776 res = d_theoryBitvector->newConcatExpr(res, padding);
01777 }
01778 }
01779
01780 Proof pf;
01781 if(withProof())
01782 pf = newPf("constWidthLeftShift_to_concat", e);
01783 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
01784 }
01785
01786
01787 Theorem BitvectorTheoremProducer::rightShiftToConcat(const Expr& e) {
01788 if(CHECK_PROOFS) {
01789 CHECK_SOUND(e.getOpKind() == RIGHTSHIFT && e.arity() == 1,
01790 "BitvectorTheoremProducer::rightShiftConst: e = "+e.toString());
01791 CHECK_SOUND(d_theoryBitvector->getFixedRightShiftParam(e) >= 0,
01792 "BitvectorTheoremProducer::rightShiftConst: e = "+e.toString());
01793 }
01794 int bvLength = d_theoryBitvector->BVSize(e[0]);
01795
01796 int shiftSize=d_theoryBitvector->getFixedRightShiftParam(e);
01797 Expr padding = d_theoryBitvector->newBVZeroString(shiftSize);
01798
01799 Expr output;
01800 if(shiftSize >= bvLength)
01801 output = d_theoryBitvector->newBVZeroString(bvLength);
01802 else {
01803 Expr out0 =
01804 d_theoryBitvector->newBVExtractExpr(e[0],bvLength-1,shiftSize);
01805 output =
01806 d_theoryBitvector->newConcatExpr(padding,out0);
01807 }
01808
01809 DebugAssert(bvLength == d_theoryBitvector->BVSize(output),
01810 "BitvectorTheoremProducer::rightShiftConst: e = "+e.toString());
01811
01812 Proof pf;
01813 if(withProof())
01814 pf = newPf("rightshift_to_concat", e);
01815 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
01816 }
01817
01818
01819 Theorem BitvectorTheoremProducer::rewriteXOR(const Expr& e)
01820 {
01821 if (CHECK_PROOFS) {
01822 CHECK_SOUND(e.getKind() == BVXOR && e.arity() == 2,
01823 "Bad call to rewriteXOR");
01824 }
01825 Expr nege0 = d_theoryBitvector->newBVNegExpr(e[0]);
01826 Expr nege1 = d_theoryBitvector->newBVNegExpr(e[1]);
01827 Expr or1 = d_theoryBitvector->newBVAndExpr(nege0, e[1]);
01828 Expr or2 = d_theoryBitvector->newBVAndExpr(e[0], nege1);
01829
01830 Proof pf;
01831 if (withProof())
01832 pf = newPf("rewriteXOR", e);
01833 return newRWTheorem(e, d_theoryBitvector->newBVOrExpr(or1, or2),
01834 Assumptions::emptyAssump(), pf);
01835 }
01836
01837
01838 Theorem BitvectorTheoremProducer::rewriteXNOR(const Expr& e)
01839 {
01840 if (CHECK_PROOFS) {
01841 CHECK_SOUND(e.getKind() == BVXNOR && e.arity() == 2,
01842 "Bad call to rewriteXNOR");
01843 }
01844 Expr nege0 = d_theoryBitvector->newBVNegExpr(e[0]);
01845 Expr nege1 = d_theoryBitvector->newBVNegExpr(e[1]);
01846 Expr or1 = d_theoryBitvector->newBVAndExpr(nege0, nege1);
01847 Expr or2 = d_theoryBitvector->newBVAndExpr(e[0], e[1]);
01848
01849 Proof pf;
01850 if (withProof())
01851 pf = newPf("rewriteXNOR", e);
01852 return newRWTheorem(e, d_theoryBitvector->newBVOrExpr(or1, or2),
01853 Assumptions::emptyAssump(), pf);
01854 }
01855
01856
01857 Theorem BitvectorTheoremProducer::rewriteNAND(const Expr& e)
01858 {
01859 if (CHECK_PROOFS) {
01860 CHECK_SOUND(e.getKind() == BVNAND && e.arity() == 2,
01861 "Bad call to rewriteNAND");
01862 }
01863 Expr andExpr = d_theoryBitvector->newBVAndExpr(e[0], e[1]);
01864 Proof pf;
01865 if (withProof())
01866 pf = newPf("rewriteNAND", e);
01867 return newRWTheorem(e, d_theoryBitvector->newBVNegExpr(andExpr),
01868 Assumptions::emptyAssump(), pf);
01869 }
01870
01871
01872 Theorem BitvectorTheoremProducer::rewriteNOR(const Expr& e)
01873 {
01874 if (CHECK_PROOFS) {
01875 CHECK_SOUND(e.getKind() == BVNOR && e.arity() == 2,
01876 "Bad call to rewriteNOR");
01877 }
01878 Expr orExpr = d_theoryBitvector->newBVOrExpr(e[0], e[1]);
01879 Proof pf;
01880 if (withProof())
01881 pf = newPf("rewriteNOR", e);
01882 return newRWTheorem(e, d_theoryBitvector->newBVNegExpr(orExpr),
01883 Assumptions::emptyAssump(), pf);
01884 }
01885
01886
01887 Theorem BitvectorTheoremProducer::rewriteBVSub(const Expr& e)
01888 {
01889 if (CHECK_PROOFS) {
01890 CHECK_SOUND(e.getKind() == BVSUB && e.arity() == 2 &&
01891 d_theoryBitvector->BVSize(e[0]) ==
01892 d_theoryBitvector->BVSize(e[1]),
01893 "Bad call to rewriteBVSub");
01894 }
01895 int bvsize = d_theoryBitvector->BVSize(e[0]);
01896 vector<Expr> k;
01897 k.push_back(e[0]);
01898 k.push_back(d_theoryBitvector->newBVUminusExpr(e[1]));
01899
01900 Proof pf;
01901 if (withProof())
01902 pf = newPf("rewriteBVSub", e);
01903 return newRWTheorem(e, d_theoryBitvector->newBVPlusExpr(bvsize, k),
01904 Assumptions::emptyAssump(), pf);
01905 }
01906
01907
01908
01909
01910 Theorem BitvectorTheoremProducer::constMultToPlus(const Expr& e) {
01911 DebugAssert(false,
01912 "BitvectorTheoremProducer::constMultToPlus: this rule does not work\n");
01913 if(CHECK_PROOFS) {
01914 CHECK_SOUND(e.getOpKind() == BVMULT && e.arity() == 2
01915 && e[0].isRational() && e[0].getRational().isInteger(),
01916 "BitvectorTheoremProducer::constMultToPlus:\n e = "
01917 +e.toString());
01918 }
01919
01920 Rational k = e[0].getRational();
01921 const Expr& t = e[1];
01922 int resLength = d_theoryBitvector->BVSize(e);
01923 string coeffBinary = abs(k).toString(2);
01924 int len = coeffBinary.length();
01925 Expr res;
01926 if(k == 0) {
01927
01928 vector<bool> bits;
01929 int len = resLength;
01930 for(int i=0; i<len; ++i) bits.push_back(false);
01931 res = d_theoryBitvector->newBVConstExpr(bits);
01932 } else {
01933
01934 vector<Expr> kids;
01935 for(int i=0; i<len; ++i) {
01936 if(coeffBinary[i] == '1')
01937 kids.push_back(d_theoryBitvector->newFixedLeftShiftExpr(t, (len-1)-i));
01938 }
01939 res = (kids.size() == 1)? kids[0]
01940 : d_theoryBitvector->newBVPlusExpr(resLength, kids);
01941
01942 if(k < 0) {
01943 vector<Expr> kk;
01944 kk.push_back(d_theoryBitvector->newBVNegExpr(res));
01945 kk.push_back(rat(1));
01946 res = d_theoryBitvector->newBVPlusExpr(resLength, kk);
01947 }
01948 }
01949
01950 Proof pf;
01951 if(withProof())
01952 pf = newPf("const_mult_to_plus", e);
01953 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
01954 }
01955
01956
01957 Theorem
01958 BitvectorTheoremProducer::bvplusZeroConcatRule(const Expr& e) {
01959 if(CHECK_PROOFS) {
01960 CHECK_SOUND(e.getOpKind()==CONCAT && e.arity()==2,
01961 "BitvectorTheoremProducer::bvplusZeroConcatRule: e = "
01962 +e.toString());
01963 CHECK_SOUND(e[0].getKind()==BVCONST && e[1].getOpKind()==BVPLUS
01964 && d_theoryBitvector->computeBVConst(e[0])==0,
01965 "BitvectorTheoremProducer::bvplusZeroConcatRule: e = "
01966 +e.toString());
01967 }
01968
01969 int constSize = d_theoryBitvector->BVSize(e[0]);
01970 const Expr& bvplus = e[1];
01971 int bvplusSize = d_theoryBitvector->getBVPlusParam(bvplus);
01972
01973
01974 int maxKidSize(0);
01975 for(Expr::iterator i=bvplus.begin(), iend=bvplus.end(); i!=iend; ++i) {
01976 int size(d_theoryBitvector->BVSize(*i));
01977
01978 if(i->getOpKind()==CONCAT && i->arity()>=2
01979 && (*i)[0].getKind()==BVCONST && d_theoryBitvector->computeBVConst((*i)[0])==0)
01980 size -= d_theoryBitvector->BVSize((*i)[0]);
01981 if(size > maxKidSize) maxKidSize = size;
01982 }
01983 int numKids = bvplus.arity();
01984
01985 int log2 = 0;
01986 for(int i=1; i < numKids; i *=2, log2++);
01987 if(log2+maxKidSize > bvplusSize) {
01988
01989 TRACE("bv 0@+", "bvplusZeroConcatRule(", e, "): skipped");
01990 return d_theoryBitvector->reflexivityRule(e);
01991 }
01992
01993 Expr res(d_theoryBitvector->newBVPlusExpr(bvplusSize+constSize,
01994 bvplus.getKids()));
01995
01996 Proof pf;
01997 if(withProof())
01998 pf = newPf("bvplus_zero_concat", e);
01999 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
02000 }
02001
02002
02003
02004
02005 Theorem BitvectorTheoremProducer::extractConst(const Expr& e) {
02006 if(CHECK_PROOFS) {
02007
02008 CHECK_SOUND(e.getOpKind() == EXTRACT && e.arity() == 1,
02009 "BitvectorTheoremProducer::extractConst: e = "+e.toString());
02010 CHECK_SOUND(constantKids(e),
02011 "BitvectorTheoremProducer::extractConst: e = "+e.toString());
02012 }
02013
02014 int hi = d_theoryBitvector->getExtractHi(e);
02015 int low = d_theoryBitvector->getExtractLow(e);
02016 const Expr& e0 = e[0];
02017
02018 if(CHECK_PROOFS) {
02019 CHECK_SOUND(0 <= low && low <= hi,
02020 "BitvectorTheoremProducer::extractConst: e = "+e.toString());
02021 CHECK_SOUND((unsigned)hi < d_theoryBitvector->getBVConstSize(e0),
02022 "BitvectorTheoremProducer::extractConst: e = "+e.toString());
02023 }
02024 vector<bool> res;
02025
02026 for(int bit=low; bit <= hi; bit++)
02027 res.push_back(d_theoryBitvector->getBVConstValue(e0, bit));
02028
02029 Proof pf;
02030 if(withProof())
02031 pf = newPf("extract_const", e);
02032 return newRWTheorem(e, d_theoryBitvector->newBVConstExpr(res), Assumptions::emptyAssump(), pf);
02033 }
02034
02035
02036 Theorem
02037 BitvectorTheoremProducer::extractWhole(const Expr& e) {
02038 if(CHECK_PROOFS) {
02039 CHECK_SOUND(e.getOpKind() == EXTRACT && e.arity() == 1,
02040 "BitvectorTheoremProducer::extractWhole: e = "+e.toString());
02041 }
02042
02043 int hi = d_theoryBitvector->getExtractHi(e);
02044 int low = d_theoryBitvector->getExtractLow(e);
02045 const Expr& e0 = e[0];
02046
02047 if(CHECK_PROOFS) {
02048 CHECK_SOUND(low ==0 && hi == d_theoryBitvector->BVSize(e0) - 1,
02049 "BitvectorTheoremProducer::extractWhole: e = "+e.toString()
02050 +"\n BVSize(e) = "+ int2string(d_theoryBitvector->BVSize(e0)));
02051 }
02052 Proof pf;
02053 if(withProof())
02054 pf = newPf("extract_whole", e);
02055 return newRWTheorem(e, e0, Assumptions::emptyAssump(), pf);
02056 }
02057
02058
02059
02060 Theorem
02061 BitvectorTheoremProducer::extractExtract(const Expr& e) {
02062 if(CHECK_PROOFS) {
02063 CHECK_SOUND(e.getOpKind() == EXTRACT && e.arity() == 1,
02064 "BitvectorTheoremProducer::extractExtract: e = "+e.toString());
02065 }
02066
02067 int hi = d_theoryBitvector->getExtractHi(e);
02068 int low = d_theoryBitvector->getExtractLow(e);
02069 const Expr& e0 = e[0];
02070
02071 if(CHECK_PROOFS) {
02072
02073 CHECK_SOUND(0 <= low && low <= hi,
02074 "BitvectorTheoremProducer::extractExtract: e = "+e.toString());
02075
02076 CHECK_SOUND(e0.getOpKind() == EXTRACT && e0.arity() == 1,
02077 "BitvectorTheoremProducer::extractExtract: e0 = "
02078 +e0.toString());
02079 }
02080
02081 int hi0 = d_theoryBitvector->getExtractHi(e0);
02082 int low0 = d_theoryBitvector->getExtractLow(e0);
02083 const Expr& e00 = e0[0];
02084
02085 if(CHECK_PROOFS) {
02086
02087 CHECK_SOUND((0 <= low) && (low <= hi) && (hi <= hi0-low0),
02088 "BitvectorTheoremProducer::extractExtract:\n"
02089 " [hi:low][hi0:low0] = ["+ int2string(hi0)+":"+ int2string(low0)
02090 +"]["+ int2string(hi) + ":" + int2string(low)
02091 +"]\n e = "+e.toString());
02092 }
02093
02094 Expr res = d_theoryBitvector->newBVExtractExpr(e00, hi+low0, low+low0);
02095
02096 Proof pf;
02097 if(withProof())
02098 pf = newPf("extract_extract", e);
02099 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
02100 }
02101
02102
02103
02104 Theorem
02105 BitvectorTheoremProducer::extractConcat(const Expr& e) {
02106 TRACE("bitvector rules", "extractConcat(", e, ") {");
02107 if(CHECK_PROOFS) {
02108 CHECK_SOUND(e.getOpKind() == EXTRACT && e.arity() == 1,
02109 "BitvectorTheoremProducer::extractConcat: e = "+e.toString());
02110 }
02111
02112 int hi = d_theoryBitvector->getExtractHi(e);
02113 int low = d_theoryBitvector->getExtractLow(e);
02114 const Expr& e0 = e[0];
02115
02116 if(CHECK_PROOFS) {
02117
02118 CHECK_SOUND(0 <= low && low <= hi,
02119 "BitvectorTheoremProducer::extractConcat: e = "+e.toString());
02120 CHECK_SOUND(hi < d_theoryBitvector->BVSize(e0),
02121 "BitvectorTheoremProducer::extractConcat: e = "+e.toString()
02122 +"\n BVSize(e0) = "+ int2string(d_theoryBitvector->BVSize(e0)));
02123
02124 CHECK_SOUND(e0.getOpKind() == CONCAT,
02125 "BitvectorTheoremProducer::extractConcat: e0 = "
02126 +e0.toString());
02127 }
02128
02129 vector<Expr> kids;
02130 int width(d_theoryBitvector->BVSize(e0));
02131 TRACE("bitvector rules", "extractConcat: width=", width, "");
02132 for(Expr::iterator i=e0.begin(), iend=e0.end(); i!=iend && width>low; ++i) {
02133 TRACE("bitvector rules", "extractConcat: *i=", *i, "");
02134 int w(d_theoryBitvector->BVSize(*i));
02135 int newWidth = width-w;
02136 int l(0), h(0);
02137 TRACE("bitvector rules", "extractConcat: w=", w, "");
02138 TRACE("bitvector rules", "extractConcat: newWidth=", newWidth, "");
02139 if(width > hi) {
02140 if(hi >= newWidth) {
02141 h = hi-newWidth;
02142 l = (newWidth <= low)? low-newWidth : 0;
02143 TRACE("bitvector rules", "extractConcat[newWidth<=hi<width]: h=",
02144 h, ", l="+ int2string(l));
02145 kids.push_back(d_theoryBitvector->newBVExtractExpr(*i, h, l));
02146 }
02147 } else if(width > low) {
02148
02149 h = w-1;
02150 l = (newWidth <= low)? low-newWidth : 0;
02151 TRACE("bitvector rules", "extractConcat[low<width<=hi]: h=",
02152 h, ", l="+ int2string(l));
02153 kids.push_back(d_theoryBitvector->newBVExtractExpr(*i, h, l));
02154 }
02155 width=newWidth;
02156 TRACE("bitvector rules", "extractConcat: width=", width, "");
02157 }
02158 Expr res = (kids.size()==1)? kids[0]
02159 : d_theoryBitvector->newConcatExpr(kids);
02160 Proof pf;
02161 if(withProof())
02162 pf = newPf("extract_concat", e);
02163 Theorem thm(newRWTheorem(e, res, Assumptions::emptyAssump(), pf));
02164 TRACE("bitvector rules", "extractConcat => ", thm.getExpr(), " }");
02165 return thm;
02166 }
02167
02168
02169
02170
02171 Theorem
02172 BitvectorTheoremProducer::extractBitwise(const Expr& e, int kind,
02173 const string& pfName) {
02174 if(CHECK_PROOFS) {
02175 CHECK_SOUND(e.getOpKind() == EXTRACT && e.arity() == 1,
02176 "BitvectorTheoremProducer::"+pfName+": e = "+e.toString());
02177 CHECK_SOUND(kind == BVAND || kind == BVOR ||
02178 kind == BVNEG || kind == BVXOR ||
02179 kind == BVXNOR,
02180 "BitvectorTheoremProducer::"+pfName+": kind = "
02181 +d_theoryBitvector->getEM()->getKindName(kind));
02182 }
02183
02184 int hi = d_theoryBitvector->getExtractHi(e);
02185 int low = d_theoryBitvector->getExtractLow(e);
02186 const Expr& e0 = e[0];
02187
02188 if(CHECK_PROOFS) {
02189
02190 CHECK_SOUND(0 <= low && low <= hi,
02191 "BitvectorTheoremProducer::"+pfName+": e = "+e.toString());
02192
02193 CHECK_SOUND(e0.getOpKind() == kind,
02194 "BitvectorTheoremProducer::"+pfName+": e0 = "
02195 +e0.toString());
02196 }
02197
02198 vector<Expr> kids;
02199 for(Expr::iterator i=e0.begin(), iend=e0.end(); i!=iend; ++i) {
02200 kids.push_back(d_theoryBitvector->newBVExtractExpr(*i, hi, low));
02201 }
02202 Expr res = Expr(e0.getOp(), kids);
02203 Proof pf;
02204 if(withProof())
02205 pf = newPf(pfName, e);
02206 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
02207 }
02208
02209
02210 Theorem
02211 BitvectorTheoremProducer::extractAnd(const Expr& e) {
02212 return extractBitwise(e, BVAND, "extract_and");
02213 }
02214
02215
02216
02217 Theorem
02218 BitvectorTheoremProducer::extractOr(const Expr& e) {
02219 return extractBitwise(e, BVOR, "extract_or");
02220 }
02221
02222
02223
02224 Theorem
02225 BitvectorTheoremProducer::extractNeg(const Expr& e) {
02226 return extractBitwise(e, BVNEG, "extract_neg");
02227 }
02228
02229
02230 Theorem
02231 BitvectorTheoremProducer::iteExtractRule(const Expr& e) {
02232 if(CHECK_PROOFS) {
02233 CHECK_SOUND(e.getOpKind() == EXTRACT && e.arity()==1,
02234 "BitvectorTheoremProducer::iteExtractRule: "
02235 "input must be an bitvector EXTRACT expr:\n"+
02236 e.toString());
02237 }
02238 int hi = d_theoryBitvector->getExtractHi(e);
02239 int low = d_theoryBitvector->getExtractLow(e);
02240
02241 if(CHECK_PROOFS) {
02242 CHECK_SOUND(e[0].getKind() == ITE &&
02243 e[0].arity()==3 &&
02244 BITVECTOR == e[0].getType().getExpr().getOpKind(),
02245 "BitvectorTheoremProducer::iteExtractRule: "
02246 "input must be an bitvector EXTRACT expr over an ITE:\n" +
02247 e.toString());
02248 CHECK_SOUND(hi >= low && d_theoryBitvector->BVSize(e[0]) >= hi-low,
02249 "BitvectorTheoremProducer::iteExtractRule: "
02250 "i should be greater than j in e[i:j] = "
02251 +e.toString());
02252 }
02253 const Expr ite = e[0];
02254 Expr cond = ite[0];
02255 Expr e1 = d_theoryBitvector->newBVExtractExpr(ite[1],hi,low);
02256 Expr e2 = d_theoryBitvector->newBVExtractExpr(ite[2],hi,low);
02257 Expr output = Expr(CVC3::ITE,cond,e1,e2);
02258
02259 Proof pf;
02260 if(withProof())
02261 pf = newPf("ite_extract_rule", e);
02262 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
02263 }
02264
02265
02266 Theorem
02267 BitvectorTheoremProducer::iteBVnegRule(const Expr& e) {
02268 if(CHECK_PROOFS) {
02269 CHECK_SOUND(e.getOpKind() == BVNEG && e.arity()==1,
02270 "BitvectorTheoremProducer::itebvnegrule: "
02271 "input must be an bitvector EXTRACT expr:\n"+
02272 e.toString());
02273 }
02274 if(CHECK_PROOFS) {
02275 CHECK_SOUND(e[0].getKind() == ITE &&
02276 e[0].arity()==3 &&
02277 BITVECTOR == e[0].getType().getExpr().getOpKind(),
02278 "BitvectorTheoremProducer::itebvnegrule: "
02279 "input must be an bitvector EXTRACT expr over an ITE:\n" +
02280 e.toString());
02281 }
02282 const Expr ite = e[0];
02283 Expr cond = ite[0];
02284 Expr e1 = d_theoryBitvector->newBVNegExpr(ite[1]);
02285 Expr e2 = d_theoryBitvector->newBVNegExpr(ite[2]);
02286 Expr output = Expr(CVC3::ITE,cond,e1,e2);
02287
02288 Proof pf;
02289 if(withProof())
02290 pf = newPf("ite_bvneg_rule", e);
02291 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
02292 }
02293
02294
02295 Theorem BitvectorTheoremProducer::negConst(const Expr& e) {
02296 if(CHECK_PROOFS) {
02297
02298 CHECK_SOUND(e.getOpKind() == BVNEG && e.arity() == 1,
02299 "BitvectorTheoremProducer::negConst: e = "+e.toString());
02300 CHECK_SOUND(constantKids(e),
02301 "BitvectorTheoremProducer::negConst: e = "+e.toString());
02302 }
02303 const Expr& e0 = e[0];
02304 vector<bool> res;
02305
02306 for(int bit=0, size=d_theoryBitvector->getBVConstSize(e0); bit<size; bit++)
02307 res.push_back(!d_theoryBitvector->getBVConstValue(e0, bit));
02308
02309 Proof pf;
02310 if(withProof())
02311 pf = newPf("bitneg_const", e);
02312 return newRWTheorem(e, d_theoryBitvector->newBVConstExpr(res), Assumptions::emptyAssump(), pf);
02313 }
02314
02315
02316
02317 Theorem
02318 BitvectorTheoremProducer::negConcat(const Expr& e) {
02319 if(CHECK_PROOFS) {
02320
02321 CHECK_SOUND(e.getOpKind() == BVNEG && e.arity() == 1,
02322 "BitvectorTheoremProducer::negConcat: e = "+e.toString());
02323 CHECK_SOUND(e[0].getOpKind() == CONCAT,
02324 "BitvectorTheoremProducer::negConcat: e = "+e.toString());
02325 }
02326
02327 const Expr& e0 = e[0];
02328
02329 vector<Expr> kids;
02330 for(Expr::iterator i=e0.begin(), iend=e0.end(); i!=iend; ++i)
02331 kids.push_back(d_theoryBitvector->newBVNegExpr(*i));
02332
02333 Expr res = d_theoryBitvector->newConcatExpr(kids);
02334
02335 Proof pf;
02336 if(withProof())
02337 pf = newPf("bitneg_concat", e);
02338 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
02339 }
02340
02341
02342 Theorem
02343 BitvectorTheoremProducer::negNeg(const Expr& e) {
02344 if(CHECK_PROOFS) {
02345 CHECK_SOUND(e.getOpKind() == BVNEG && e.arity() == 1,
02346 "BitvectorTheoremProducer::negNeg: e = "+e.toString());
02347 CHECK_SOUND(e[0].getOpKind() == BVNEG && e[0].arity() == 1,
02348 "BitvectorTheoremProducer::negNeg: e = "+e.toString());
02349 }
02350
02351 Proof pf;
02352 if(withProof())
02353 pf = newPf("bitneg_neg", e);
02354 return newRWTheorem(e, e[0][0], Assumptions::emptyAssump(), pf);
02355 }
02356
02357
02358 Theorem
02359 BitvectorTheoremProducer::negBVand(const Expr& e) {
02360 if(CHECK_PROOFS) {
02361 CHECK_SOUND(e.getOpKind() == BVNEG && e.arity() == 1,
02362 "BitvectorTheoremProducer::negBVand: e = "+e.toString());
02363 CHECK_SOUND(e[0].getOpKind() == BVAND,
02364 "BitvectorTheoremProducer::negBVand: e = "+e.toString());
02365 }
02366 Expr output;
02367 std::vector<Expr> negated;
02368 for(Expr::iterator i = e[0].begin(),iend=e[0].end();i!=iend;++i)
02369 negated.push_back(d_theoryBitvector->newBVNegExpr(*i));
02370 output = d_theoryBitvector->newBVOrExpr(negated);
02371
02372 Proof pf;
02373 if(withProof())
02374 pf = newPf("bitneg_and", e);
02375 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
02376 }
02377
02378
02379
02380 Theorem
02381 BitvectorTheoremProducer::negBVor(const Expr& e) {
02382 if(CHECK_PROOFS) {
02383 CHECK_SOUND(e.getOpKind() == BVNEG && e.arity() == 1,
02384 "BitvectorTheoremProducer::negBVor: e = "+e.toString());
02385 CHECK_SOUND(e[0].getOpKind() == BVOR,
02386 "BitvectorTheoremProducer::negBVor: e = "+e.toString());
02387 }
02388
02389 Expr output;
02390 std::vector<Expr> negated;
02391 for(Expr::iterator i = e[0].begin(),iend=e[0].end();i!=iend;++i)
02392 negated.push_back(d_theoryBitvector->newBVNegExpr(*i));
02393 output = d_theoryBitvector->newBVAndExpr(negated);
02394
02395 Proof pf;
02396 if(withProof())
02397 pf = newPf("bitneg_or", e);
02398 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
02399 }
02400
02401
02402
02403 Theorem
02404 BitvectorTheoremProducer::negBVxor(const Expr& e) {
02405 if(CHECK_PROOFS) {
02406 CHECK_SOUND(e.getOpKind() == BVNEG && e.arity() == 1 && e[0].arity() > 0,
02407 "BitvectorTheoremProducer::negBVxor: e = "+e.toString());
02408 CHECK_SOUND(e[0].getOpKind() == BVXOR,
02409 "BitvectorTheoremProducer::negBVxor: e = "+e.toString());
02410 }
02411
02412 Expr output;
02413 std::vector<Expr> children;
02414 Expr::iterator i = e[0].begin(), iend = e[0].end();
02415 children.push_back(d_theoryBitvector->newBVNegExpr(*i));
02416 ++i;
02417 for(; i!=iend; ++i)
02418 children.push_back(*i);
02419 output = d_theoryBitvector->newBVXorExpr(children);
02420
02421 Proof pf;
02422 if(withProof())
02423 pf = newPf("bitneg_xor", e);
02424 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
02425 }
02426
02427
02428
02429 Theorem
02430 BitvectorTheoremProducer::negBVxnor(const Expr& e) {
02431 if(CHECK_PROOFS) {
02432 CHECK_SOUND(e.getOpKind() == BVNEG && e.arity() == 1 && e[0].arity() > 0,
02433 "BitvectorTheoremProducer::negBVxor: e = "+e.toString());
02434 CHECK_SOUND(e[0].getOpKind() == BVXNOR,
02435 "BitvectorTheoremProducer::negBVxor: e = "+e.toString());
02436 }
02437
02438 Expr t2 = e[0][1];
02439 if (e[0].arity() > 2) {
02440 std::vector<Expr> children;
02441 Expr::iterator i = e[0].begin(), iend = e[0].end();
02442 ++i;
02443 for(; i!=iend; ++i)
02444 children.push_back(*i);
02445 t2 = d_theoryBitvector->newBVXnorExpr(children);
02446 }
02447 Expr output = d_theoryBitvector->newBVXorExpr(e[0][0], t2);
02448
02449 Proof pf;
02450 if(withProof())
02451 pf = newPf("bitneg_xnor", e);
02452 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
02453 }
02454
02455
02456
02457
02458 Theorem BitvectorTheoremProducer::bitwiseConst(const Expr& e,
02459 const std::vector<int>& idxs,
02460 bool isAnd) {
02461 string funName(isAnd? "andConst" : "orConst");
02462 if(CHECK_PROOFS) {
02463
02464 CHECK_SOUND(e.getOpKind() == (isAnd ? BVAND : BVOR),
02465 "BitvectorTheoremProducer::"+funName+": e = "+e.toString());
02466 CHECK_SOUND(idxs.size() >= 2, "BitvectorTheoremProducer::"+funName
02467 +"():\n e = "+e.toString());
02468 for(size_t i=0; i<idxs.size(); ++i) {
02469 CHECK_SOUND(idxs[i] < e.arity(),
02470 "BitvectorTheoremProducer::"+funName+": idxs["
02471 +int2string(i)+"]="+int2string(idxs[i])
02472 +", e.arity() = "+int2string(e.arity())
02473 +"\n e = "+e.toString());
02474 CHECK_SOUND(e[idxs[i]].getKind() == BVCONST,
02475 "BitvectorTheoremProducer::"+funName+": e = "+e.toString());
02476 }
02477 }
02478 vector<bool> bits;
02479
02480 int size = d_theoryBitvector->BVSize(e);
02481 for(int bit=0; bit<size; bit++)
02482 bits.push_back(isAnd);
02483
02484 vector<Expr> kids(1);
02485 size_t ii(0);
02486 int idx(idxs[0]);
02487 for(int i=0, iend=e.arity(); i<iend; ++i) {
02488 const Expr& ei = e[i];
02489 if(i == idx) {
02490 if(CHECK_PROOFS) {
02491 CHECK_SOUND(ei.getKind() == BVCONST,
02492 "BitvectorTheoremProducer::"+funName+": e["
02493 +int2string(i)+"] = "+ei.toString());
02494 CHECK_SOUND(d_theoryBitvector->getBVConstSize(ei) == (unsigned)size,
02495 "BitvectorTheoremProducer::"+funName+": e["
02496 +int2string(i)+"] = "+ei.toString());
02497 }
02498
02499 for(int bit=0; bit<size; bit++)
02500 bits[bit] = isAnd ?
02501 (bits[bit] && d_theoryBitvector->getBVConstValue(ei, bit))
02502 : (bits[bit] || d_theoryBitvector->getBVConstValue(ei, bit));
02503
02504 if(ii < idxs.size())
02505 idx = idxs[++ii];
02506 else
02507 idx = e.arity();
02508 }
02509 else
02510 kids.push_back(ei);
02511 }
02512
02513 kids[0] = d_theoryBitvector->newBVConstExpr(bits);
02514
02515 Expr res = (kids.size() == 1)? kids[0]
02516 : isAnd? d_theoryBitvector->newBVAndExpr(kids)
02517 : d_theoryBitvector->newBVOrExpr(kids);
02518
02519 Proof pf;
02520 if(withProof()) {
02521
02522 vector<Expr> indices;
02523 for(size_t i=0, iend=idxs.size(); i<iend; ++i)
02524 indices.push_back(rat(idxs[i]));
02525 pf = newPf(isAnd? "bitand_const" : "bitor_const",
02526 e, Expr(RAW_LIST, indices));
02527 }
02528 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
02529 }
02530
02531
02532
02533
02534
02535
02536
02537
02538 Theorem
02539 BitvectorTheoremProducer::bitwiseConcat(const Expr& e, int idx, bool isAnd) {
02540 string funName(isAnd? "andConcat" : "orConcat");
02541 if(CHECK_PROOFS) {
02542 CHECK_SOUND(e.getOpKind() == (isAnd ? BVAND : BVOR),
02543 "BitvectorTheoremProducer::"+funName+": e = "+e.toString());
02544 CHECK_SOUND(idx < e.arity(),
02545 "BitvectorTheoremProducer::"+funName+": e = "+e.toString()
02546 +"\n idx = "+int2string(idx)
02547 +"\n e.arity() = "+int2string(e.arity()));
02548 CHECK_SOUND(e[idx].getOpKind() == CONCAT && e[idx].arity() > 0,
02549 "BitvectorTheoremProducer::"+funName+": e["+int2string(idx)
02550 +"] = "+e[idx].toString());
02551 }
02552
02553 int arity = e.arity();
02554 const Expr& ei = e[idx];
02555
02556
02557 vector<Expr> concatKids;
02558
02559 int hi=d_theoryBitvector->BVSize(e)-1;
02560 int low=hi-d_theoryBitvector->BVSize(ei[0])+1;
02561
02562 for(int i=0, iend=ei.arity(); i<iend; ++i) {
02563
02564 vector<Expr> kids;
02565 for(int j=0; j<arity; ++j) {
02566 if(j==idx)
02567 kids.push_back(ei[i]);
02568 else
02569 kids.push_back(d_theoryBitvector->newBVExtractExpr(e[j], hi, low));
02570 }
02571 if(isAnd)
02572 concatKids.push_back(d_theoryBitvector->newBVAndExpr(kids));
02573 else
02574 concatKids.push_back(d_theoryBitvector->newBVOrExpr(kids));
02575 if(i+1<iend) {
02576 int newHi = low-1;
02577 low = low - d_theoryBitvector->BVSize(ei[i+1]);
02578 hi = newHi;
02579 }
02580 }
02581 Expr res = d_theoryBitvector->newConcatExpr(concatKids);
02582 Proof pf;
02583 if(withProof())
02584 pf = newPf(isAnd? "bitand_concat" : "bitor_concat", e, rat(idx));
02585 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
02586 }
02587
02588
02589 Theorem
02590 BitvectorTheoremProducer::bitwiseFlatten(const Expr& e, bool isAnd) {
02591 string funName(isAnd? "andFlatten" : "orFlatten");
02592 int kind = isAnd? BVAND : BVOR;
02593
02594 if(CHECK_PROOFS) {
02595 CHECK_SOUND(e.getOpKind() == kind && e.arity()>=2,
02596 "BitvectorTheoremProducer::"+funName+": e = "+e.toString());
02597 }
02598 int bvLength = d_theoryBitvector->BVSize(e);
02599 Expr output;
02600 int flag = 0;
02601
02602
02603 std::vector<Expr> flattenkids;
02604 for(Expr::iterator i = e.begin(),iend=e.end();i!=iend; ++i) {
02605 if(i->getOpKind() == kind)
02606 flattenkids.insert(flattenkids.end(),
02607 i->getKids().begin(),i->getKids().end());
02608 else
02609 flattenkids.push_back(*i);
02610 }
02611
02612
02613 std::vector<Expr> outputkids;
02614 ExprMap<int> likeTerms;
02615 std::vector<Expr>::iterator j = flattenkids.begin();
02616 std::vector<Expr>::iterator jend = flattenkids.end();
02617 for(;j!=jend; ++j) {
02618
02619 flag = sameKidCheck(*j, likeTerms);
02620 switch(flag) {
02621 case 0:
02622
02623 outputkids.push_back(*j);
02624 break;
02625 case 1:
02626
02627 break;
02628 case -1:{
02629
02630 if(isAnd)
02631 output = d_theoryBitvector->newBVZeroString(bvLength);
02632 else
02633 output = d_theoryBitvector->newBVOneString(bvLength);
02634 break;
02635 }
02636 default:
02637 DebugAssert(false,
02638 "control should not reach here");
02639 break;
02640 }
02641 if(-1 == flag)
02642 break;
02643 }
02644
02645 if(flag != -1) {
02646 DebugAssert(outputkids.size()>0,
02647 "TheoryBitvector::bitwiseFlatten: fatal error");
02648
02649 if(CHECK_PROOFS)
02650 CHECK_SOUND(outputkids.size() > 0,
02651 "TheoryBitvector:bitwiseFlatten: fatal error");
02652 sort(outputkids.begin(), outputkids.end());
02653 if(outputkids.size() >= 2)
02654 output = Expr(e.getOp(), outputkids);
02655 else
02656 output = *(outputkids.begin());
02657 }
02658
02659 Proof pf;
02660 if(withProof())
02661 pf = newPf(isAnd? "bitand_flatten" : "bitor_flatten", e);
02662 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
02663 }
02664
02665
02666 Theorem BitvectorTheoremProducer::andConst(const Expr& e,
02667 const std::vector<int>& idxs) {
02668 return bitwiseConst(e, idxs, true);
02669 }
02670
02671
02672
02673
02674
02675 Theorem
02676 BitvectorTheoremProducer::andZero(const Expr& e, int idx) {
02677 if(CHECK_PROOFS) {
02678 CHECK_SOUND(e.getOpKind() == BVAND,
02679 "BitvectorTheoremProducer::andZero: e = "+e.toString());
02680 CHECK_SOUND(idx < e.arity(),
02681 "BitvectorTheoremProducer::andZero: e = "+e.toString()
02682 +"\n idx = "+int2string(idx)
02683 +"\n e.arity() = "+int2string(e.arity()));
02684 CHECK_SOUND(e[idx].getKind() == BVCONST &&
02685 0 == d_theoryBitvector->computeBVConst(e[idx]),
02686 "BitvectorTheoremProducer::andZero: e["+int2string(idx)
02687 +"] = "+e[idx].toString());
02688 }
02689
02690 Proof pf;
02691 if(withProof())
02692 pf = newPf("bitand_zero", e, rat(idx));
02693 return newRWTheorem(e, e[idx], Assumptions::emptyAssump(), pf);
02694 }
02695
02696
02697 Theorem
02698 BitvectorTheoremProducer::andOne(const Expr& e, const vector<int> idxs) {
02699 if(CHECK_PROOFS) {
02700 CHECK_SOUND(e.getOpKind() == BVAND,
02701 "BitvectorTheoremProducer::andOne: e = "+e.toString());
02702 CHECK_SOUND(idxs.size() > 0,
02703 "BitvectorTheoremProducer::andOne: e = "+e.toString());
02704 int lastIdx(-1);
02705 for(vector<int>::const_iterator i=idxs.begin(), iend=idxs.end();
02706 i!=iend; ++i) {
02707 CHECK_SOUND(lastIdx < (*i) && (*i) < e.arity(),
02708 "BitvectorTheoremProducer::andOne: e = "+e.toString()
02709 +"\n lastIdx = "+int2string(lastIdx)
02710 +"\n *i = "+int2string(*i)
02711 +"\n e.arity() = "+int2string(e.arity()));
02712 lastIdx=(*i);
02713 const Expr& ei = e[*i];
02714 CHECK_SOUND(ei.getKind() == BVCONST,
02715 "BitvectorTheoremProducer::andOne: e["+int2string(*i)
02716 +"] = "+ei.toString());
02717
02718 for(int j=0,jend=(int)d_theoryBitvector->getBVConstSize(ei); j<jend; ++j)
02719 CHECK_SOUND(d_theoryBitvector->getBVConstValue(ei, j),
02720 "BitvectorTheoremProducer::andOne: e["+int2string(j)
02721 +"] = "+ei.toString());
02722 }
02723 }
02724 Proof pf;
02725 if(withProof()) {
02726 vector<Expr> es;
02727 es.push_back(e);
02728 for(vector<int>::const_iterator i=idxs.begin(), iend=idxs.end();
02729 i!=iend; ++i)
02730 es.push_back(rat(*i));
02731 pf=newPf("bitand_one", es);
02732 }
02733
02734 vector<Expr> kids;
02735 size_t idx(0);
02736 for (int i=0; i<e.arity(); ++i) {
02737 if (idx < idxs.size() && i == idxs[idx]) idx++;
02738 else kids.push_back(e[i]);
02739 }
02740 Expr res;
02741 if(kids.size()>=2) res = Expr(e.getOp(), kids);
02742 else if(kids.size()==1) res = kids[0];
02743 else res = e[0];
02744 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
02745 }
02746
02747
02748
02749
02750
02751
02752
02753
02754 Theorem
02755 BitvectorTheoremProducer::andConcat(const Expr& e, int idx) {
02756 return bitwiseConcat(e, idx, true);
02757 }
02758
02759
02760
02761
02762 Theorem
02763 BitvectorTheoremProducer::andFlatten(const Expr& e) {
02764 return bitwiseFlatten(e, true);
02765 }
02766
02767
02768
02769
02770 Theorem BitvectorTheoremProducer::orConst(const Expr& e,
02771 const std::vector<int>& idxs) {
02772 return bitwiseConst(e, idxs, false);
02773 }
02774
02775
02776
02777
02778
02779
02780 Theorem
02781 BitvectorTheoremProducer::orOne(const Expr& e, int idx) {
02782 if(CHECK_PROOFS) {
02783 CHECK_SOUND(e.getOpKind() == BVOR,
02784 "BitvectorTheoremProducer::orOne: e = "+e.toString());
02785 CHECK_SOUND(idx < e.arity(),
02786 "BitvectorTheoremProducer::orOne: e = "+e.toString()
02787 +"\n idx = "+int2string(idx)
02788 +"\n e.arity() = "+int2string(e.arity()));
02789 CHECK_SOUND(e[idx].getKind() == BVCONST,
02790 "BitvectorTheoremProducer::orOne: e["+int2string(idx)
02791 +"] = "+e[idx].toString());
02792 }
02793
02794 const Expr& ei = e[idx];
02795
02796 if(CHECK_PROOFS) {
02797 for(int i=0, iend=d_theoryBitvector->getBVConstSize(ei); i<iend; ++i)
02798 CHECK_SOUND(d_theoryBitvector->getBVConstValue(ei,i),
02799 "BitvectorTheoremProducer::orOne: e["+int2string(idx)
02800 +"] = "+ei.toString());
02801 }
02802
02803 Proof pf;
02804 if(withProof())
02805 pf = newPf("bitand_zero", e, rat(idx));
02806 return newRWTheorem(e, e[idx], Assumptions::emptyAssump(), pf);
02807 }
02808
02809
02810 Theorem
02811 BitvectorTheoremProducer::orZero(const Expr& e, const vector<int> idxs) {
02812 if(CHECK_PROOFS) {
02813 CHECK_SOUND(e.getOpKind() == BVOR,
02814 "BitvectorTheoremProducer::orZero: e = "+e.toString());
02815 CHECK_SOUND(idxs.size() > 0,
02816 "BitvectorTheoremProducer::orZero: e = "+e.toString());
02817 int lastIdx(-1);
02818 for(vector<int>::const_iterator i=idxs.begin(), iend=idxs.end();
02819 i!=iend; ++i) {
02820 CHECK_SOUND(lastIdx < (*i) && (*i) < e.arity(),
02821 "BitvectorTheoremProducer::orZero: e = "+e.toString()
02822 +"\n lastIdx = "+int2string(lastIdx)
02823 +"\n *i = "+int2string(*i)
02824 +"\n e.arity() = "+int2string(e.arity()));
02825 lastIdx=(*i);
02826 const Expr& ei = e[*i];
02827 CHECK_SOUND(ei.getKind() == BVCONST &&
02828 d_theoryBitvector->computeBVConst(ei)==0,
02829 "BitvectorTheoremProducer::orZero: e["+int2string(*i)
02830 +"] = "+ei.toString());
02831 }
02832 }
02833 Proof pf;
02834 if(withProof()) {
02835 vector<Expr> es;
02836 es.push_back(e);
02837 for(vector<int>::const_iterator i=idxs.begin(), iend=idxs.end();
02838 i!=iend; ++i)
02839 es.push_back(rat(*i));
02840 pf=newPf("bitor_zero", es);
02841 }
02842
02843 vector<Expr> kids;
02844 size_t idx(0);
02845 for(int i=0; i<e.arity(); ++i) {
02846 if (idx < idxs.size() && i == idxs[idx]) idx++;
02847 else kids.push_back(e[i]);
02848 }
02849 Expr res;
02850 if(kids.size()>=2) res = Expr(e.getOp(), kids);
02851 else if(kids.size()==1) res = kids[0];
02852 else res = e[0];
02853 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
02854 }
02855
02856
02857
02858
02859
02860
02861
02862
02863 int BitvectorTheoremProducer::sameKidCheck(const Expr& e,
02864 ExprMap<int>& likeTerms) {
02865
02866 int flag = 0;
02867
02868
02869 ExprMap<int>::iterator it = likeTerms.find(e);
02870
02871
02872 if(it==likeTerms.end()) {
02873 switch(e.getOpKind()) {
02874 case BVNEG: {
02875 likeTerms[e] = 1;
02876 ExprMap<int>::iterator it0 = likeTerms.find(e[0]);
02877 if(it0!=likeTerms.end())
02878 flag = -1;
02879 break;
02880 }
02881 default: {
02882 likeTerms[e] = 1;
02883 Expr bvNeg = d_theoryBitvector->newBVNegExpr(e);
02884 ExprMap<int>::iterator negIt = likeTerms.find(bvNeg);
02885 if(negIt!=likeTerms.end())
02886 flag=-1;
02887 break;
02888 }
02889 }
02890 return flag;
02891 }
02892
02893
02894 flag = 1;
02895 switch(e.getOpKind()) {
02896 case BVNEG: {
02897 ExprMap<int>::iterator it0 = likeTerms.find(e[0]);
02898 if(it0!=likeTerms.end())
02899 flag = -1;
02900 break;
02901 }
02902 default: {
02903 Expr bvNeg = d_theoryBitvector->newBVNegExpr(e);
02904 ExprMap<int>::iterator negIt = likeTerms.find(bvNeg);
02905 if(negIt!=likeTerms.end())
02906 flag=-1;
02907 break;
02908 }
02909 }
02910 return flag;
02911 }
02912
02913
02914
02915
02916
02917
02918
02919 Theorem
02920 BitvectorTheoremProducer::orConcat(const Expr& e, int idx) {
02921 return bitwiseConcat(e, idx, false);
02922 }
02923
02924
02925
02926
02927 Theorem
02928 BitvectorTheoremProducer::orFlatten(const Expr& e) {
02929 return bitwiseFlatten(e, false);
02930 }
02931
02932
02933
02934
02935 Theorem BitvectorTheoremProducer::concatConst(const Expr& e) {
02936 if(CHECK_PROOFS) {
02937
02938 CHECK_SOUND(e.getOpKind() == CONCAT,
02939 "BitvectorTheoremProducer::concatConst: e = "+e.toString());
02940 CHECK_SOUND(constantKids(e),
02941 "BitvectorTheoremProducer::concatConst: e = "+e.toString());
02942 }
02943 vector<bool> res;
02944 for(int i=e.arity()-1; i >= 0; --i) {
02945 for(int bit=0, size=d_theoryBitvector->getBVConstSize(e[i]); bit < size; bit++)
02946 res.push_back(d_theoryBitvector->getBVConstValue(e[i], bit));
02947 }
02948 Proof pf;
02949 if(withProof())
02950 pf = newPf("concat_const", e);
02951 return newRWTheorem(e, d_theoryBitvector->newBVConstExpr(res), Assumptions::emptyAssump(), pf);
02952 }
02953
02954
02955
02956 Theorem
02957 BitvectorTheoremProducer::concatFlatten(const Expr& e) {
02958 if(CHECK_PROOFS) {
02959 CHECK_SOUND(e.getOpKind() == CONCAT && e.arity() >= 2,
02960 "BitvectorTheoremProducer::concatFlatten: e = "+e.toString());
02961 }
02962
02963 vector<Expr> kids;
02964 for(Expr::iterator i=e.begin(), iend=e.end(); i!=iend; ++i) {
02965 if(i->getOpKind() == CONCAT)
02966 kids.insert(kids.end(), i->getKids().begin(), i->getKids().end());
02967 else
02968 kids.push_back(*i);
02969 }
02970 Proof pf;
02971 if(withProof())
02972 pf = newPf("concat_flatten", e);
02973 return newRWTheorem(e, Expr(e.getOp(), kids), Assumptions::emptyAssump(), pf);
02974 }
02975
02976
02977
02978 Theorem
02979 BitvectorTheoremProducer::concatMergeExtract(const Expr& e) {
02980 if(CHECK_PROOFS) {
02981 CHECK_SOUND(e.getOpKind() == CONCAT && e.arity() >= 2,
02982 "BitvectorTheoremProducer::concatMergeExtract: e = "
02983 +e.toString());
02984 CHECK_SOUND(e[0].getOpKind() == EXTRACT,
02985 "BitvectorTheoremProducer::concatMergeExtract: e = "
02986 +e.toString());
02987 CHECK_SOUND(d_theoryBitvector->getExtractHi(e[0]) >= d_theoryBitvector->getExtractLow(e[0]),
02988 "BitvectorTheoremProducer::concatMergeExtract: e = "
02989 +e.toString());
02990 }
02991
02992 const Expr& base = e[0][0];
02993
02994 if(CHECK_PROOFS) {
02995
02996 int low = d_theoryBitvector->getExtractLow(e[0]);
02997 for(int i=1, iend=e.arity(); i<iend; ++i) {
02998 const Expr& ei = e[i];
02999 CHECK_SOUND(ei.getOpKind() == EXTRACT && ei[0] == base,
03000 "BitvectorTheoremProducer::concatMergeExtract: e["
03001 +int2string(i)+"] = "+ei.toString()
03002 +"\n base = "+base.toString());
03003 CHECK_SOUND(d_theoryBitvector->getExtractHi(ei) >= d_theoryBitvector->getExtractLow(ei),
03004 "BitvectorTheoremProducer::concatMergeExtract: e["
03005 +int2string(i)+"] = "+e.toString());
03006
03007 int newHi = d_theoryBitvector->getExtractHi(ei);
03008
03009 CHECK_SOUND(0 <= newHi && newHi == low-1,
03010 "BitvectorTheoremProducer::concatMergeExtract:\n e["
03011 +int2string(i-1)+"] = "+e[i-1].toString()
03012 +"\n e["+int2string(i)+"] = "+ei.toString());
03013 low = d_theoryBitvector->getExtractLow(ei);
03014 }
03015 }
03016
03017 int hi = d_theoryBitvector->getExtractHi(e[0]);
03018 int low = d_theoryBitvector->getExtractLow(e[e.arity()-1]);
03019 Expr res = d_theoryBitvector->newBVExtractExpr(base, hi, low);
03020
03021 Proof pf;
03022 if(withProof())
03023 pf = newPf("concat_merge_extract", e);
03024 return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
03025 }
03026
03027
03028
03029
03030 Theorem BitvectorTheoremProducer::bvplusConst(const Expr& e) {
03031 if(CHECK_PROOFS) {
03032
03033 CHECK_SOUND(e.getOpKind() == BVPLUS,
03034 "BitvectorTheoremProducer::extractConst: e = "+e.toString());
03035 CHECK_SOUND(constantKids(e),
03036 "BitvectorTheoremProducer::extractConst: e = "+e.toString());
03037 CHECK_SOUND(d_theoryBitvector->getBVPlusParam(e) > 0,
03038 "BitvectorTheoremProducer::extractConst: e = "+e.toString());
03039 }
03040
03041
03042 Rational acc(0);
03043 for(Expr::iterator i=e.begin(), iend=e.end(); i!=iend; ++i) {
03044 Rational x = d_theoryBitvector->computeBVConst(*i);
03045 TRACE("bitvector rewrite", "bvplusConst: x(", *i, ") = "+x.toString());
03046 acc += x;
03047 TRACE("bitvector rewrite", "bvplusConst: acc = ", acc, "");
03048 }
03049
03050 int resSize = d_theoryBitvector->getBVPlusParam(e);
03051 vector<bool> res(resSize);
03052 for(int i=0; i<resSize; i++) {
03053 res[i] = (mod(acc, 2) == 1);
03054 TRACE("bitvector rewrite", "bvplusConst: acc = ", acc, "");
03055 TRACE("bitvector rewrite", "bvplusConst: res["+int2string(i)+"] = ",
03056 res[i], "");
03057 acc = floor(acc/2);
03058 }
03059
03060 Proof pf;
03061 if(withProof())
03062 pf = newPf("bvplus_const", e);
03063 return newRWTheorem(e, d_theoryBitvector->newBVConstExpr(res), Assumptions::emptyAssump(), pf);
03064 }
03065
03066
03067
03068
03069 Theorem BitvectorTheoremProducer::bvmultConst(const Expr& e) {
03070 if(CHECK_PROOFS) {
03071
03072 CHECK_SOUND(e.getOpKind() == BVMULT,
03073 "BitvectorTheoremProducer::extractConst: e = "+e.toString());
03074 CHECK_SOUND(constantKids(e),
03075 "BitvectorTheoremProducer::extractConst: e = "+e.toString());
03076 }
03077 Rational c = d_theoryBitvector->computeBVConst(e[0]);
03078
03079 Rational x = d_theoryBitvector->computeBVConst(e[1]) * c;
03080
03081
03082 int resSize = d_theoryBitvector->BVSize(e.getType().getExpr());
03083 vector<bool> res(resSize);
03084 for(int i=0; i<resSize; i++) {
03085 res[i] = (mod(x, 2) == 1);
03086 x = floor(x/2);
03087 }
03088
03089 Proof pf;
03090 if(withProof())
03091 pf = newPf("bvmult_const", e);
03092 return newRWTheorem(e, d_theoryBitvector->newBVConstExpr(res), Assumptions::emptyAssump(), pf);
03093 }
03094
03095 Theorem
03096 BitvectorTheoremProducer::zeroCoeffBVMult(const Expr& e) {
03097 if(CHECK_PROOFS) {
03098 CHECK_SOUND(e.getOpKind() == BVMULT && e.arity() == 2,
03099 "BitvectorTheoremProducer::zeroCoeffBVMult: e = "+e.toString());
03100 CHECK_SOUND(BVCONST == e[0].getKind(),
03101 "BitvectorTheoremProducer::zeroCoeffBVMult: e = "+e.toString());
03102 Rational c = d_theoryBitvector->computeBVConst(e[0]);
03103 CHECK_SOUND(0 == c,
03104 "BitvectorTheoremProducer::zeroCoeffBVMult:"
03105 "coeff must be zero:\n e = " +e.toString());
03106 }
03107 int size = d_theoryBitvector->BVSize(e);
03108 Expr output = d_theoryBitvector->newBVZeroString(size);
03109
03110 Proof pf;
03111 if(withProof())
03112 pf = newPf("zerocoeff_bvmult", e);
03113 Theorem result(newRWTheorem(e,output,Assumptions::emptyAssump(),pf));
03114 return result;
03115 }
03116
03117 Theorem
03118 BitvectorTheoremProducer::oneCoeffBVMult(const Expr& e) {
03119 if(CHECK_PROOFS) {
03120 CHECK_SOUND(e.getOpKind() == BVMULT && e.arity() == 2,
03121 "BitvectorTheoremProducer::oneCoeffBVMult: e = "
03122 +e.toString());
03123 CHECK_SOUND(BVCONST == e[0].getKind(),
03124 "BitvectorTheoremProducer::oneCoeffBVMult: e = "
03125 +e.toString());
03126 Rational c = d_theoryBitvector->computeBVConst(e[0]);
03127 CHECK_SOUND(1 == c,
03128 "BitvectorTheoremProducer::oneCoeffBVMult:"
03129 "coeff must be one:\n e = " +e.toString());
03130 }
03131 int size = d_theoryBitvector->BVSize(e);
03132 Expr output = pad(size,e);
03133
03134 Proof pf;
03135 if(withProof())
03136 pf = newPf("onecoeff_bvmult", e);
03137 Theorem result(newRWTheorem(e,output,Assumptions::emptyAssump(),pf));
03138 return result;
03139 }
03140
03141
03142 Theorem
03143 BitvectorTheoremProducer::flipBVMult(const Expr& e) {
03144 if(CHECK_PROOFS) {
03145 CHECK_SOUND(e.arity()==2 && BVMULT == e.getOpKind(),
03146 "BVMULT must have exactly 2 kids: " + e.toString());
03147 }
03148 int len = d_theoryBitvector->BVSize(e);
03149 Expr output = d_theoryBitvector->newBVMultExpr(len,e[1],e[0]);
03150
03151 Proof pf;
03152 if(withProof())
03153 pf = newPf("flip_bvmult", e);
03154 Theorem result(newRWTheorem(e,output,Assumptions::emptyAssump(),pf));
03155 return result;
03156 }
03157
03158
03159
03160
03161
03162
03163 Expr
03164 BitvectorTheoremProducer::pad(int len, const Expr& e) {
03165 DebugAssert(len > 0,
03166 "TheoryBitvector::pad:"
03167 "padding bvLength must be a non-negative integer: "+
03168 int2string(len));
03169 DebugAssert(BITVECTOR == e.getType().getExpr().getOpKind(),
03170 "TheoryBitvector::newBVPlusExpr:"
03171 "input must be a BITVECTOR: " + e.toString());
03172
03173 int size = d_theoryBitvector->BVSize(e);
03174 Expr res;
03175 if(size == len)
03176 res = e;
03177 else if (len < size)
03178 res = d_theoryBitvector->newBVExtractExpr(e,len-1,0);
03179 else {
03180
03181 Expr zero = d_theoryBitvector->newBVZeroString(len-size);
03182 res = d_theoryBitvector->newConcatExpr(zero,e);
03183 }
03184 return res;
03185 }
03186
03187
03188 Theorem
03189 BitvectorTheoremProducer::padBVPlus(const Expr& e) {
03190 if(CHECK_PROOFS) {
03191 CHECK_SOUND(BVPLUS == e.getOpKind() && e.arity()>1,
03192 "BitvectorTheoremProducer::padBVPlus: "
03193 "input must be a BVPLUS: " + e.toString());
03194 }
03195 int len = d_theoryBitvector->BVSize(e);
03196 vector<Expr> kids;
03197 for(Expr::iterator i=e.begin(), iend=e.end(); i!=iend; ++i) {
03198 if(i->getOpKind() == BVMULT) {
03199 Expr e0 = pad(len, (*i)[0]);
03200 Expr e1 = pad(len, (*i)[1]);
03201 Expr out = d_theoryBitvector->newBVMultExpr(len,e0,e1);
03202 kids.push_back(out);
03203 }
03204 else
03205 kids.push_back(pad(len, *i));
03206 }
03207
03208 Expr output = d_theoryBitvector->newBVPlusExpr(len, kids);
03209
03210 Proof pf;
03211 if(withProof())
03212 pf = newPf("pad_bvplus", e);
03213 Theorem result(newRWTheorem(e,output,Assumptions::emptyAssump(),pf));
03214 return result;
03215 }
03216
03217
03218 Theorem
03219 BitvectorTheoremProducer::padBVMult(const Expr& e) {
03220 if(CHECK_PROOFS) {
03221 CHECK_SOUND(BVMULT == e.getOpKind() && e.arity()==2,
03222 "BitvectorTheoremProducer::padBVMult: "
03223 "input must be a BVMULT: " + e.toString());
03224 CHECK_SOUND(BITVECTOR==e[0].getType().getExpr().getOpKind() &&
03225 BITVECTOR==e[1].getType().getExpr().getOpKind(),
03226 "for BVMULT terms e[0],e[1] must be a BV: " + e.toString());
03227 }
03228 int len = d_theoryBitvector->BVSize(e);
03229 Expr e0 = pad(len, e[0]);
03230 Expr e1 = pad(len, e[1]);
03231
03232 Expr output = d_theoryBitvector->newBVMultExpr(len,e0,e1);
03233
03234 Proof pf;
03235 if(withProof())
03236 pf = newPf("pad_bvmult", e);
03237 Theorem result(newRWTheorem(e,output,Assumptions::emptyAssump(),pf));
03238 return result;
03239 }
03240
03241
03242 Theorem
03243 BitvectorTheoremProducer::bvConstMultAssocRule(const Expr& e) {
03244 if(CHECK_PROOFS) {
03245 CHECK_SOUND(BVMULT == e.getOpKind() && e.arity() == 2,
03246 "BitvectorTheoremProducer::bvConstMultAssocRule: "
03247 "input must be a BVMULT: " + e.toString());
03248 CHECK_SOUND(BVMULT == e[1].getOpKind(),
03249 "BitvectorTheoremProducer::bvConstMultAssocRule: "
03250 "e[1] must be a BVMULT:\n e= " + e.toString());
03251 CHECK_SOUND(BVCONST == e[0].getKind() &&
03252 BVCONST == e[1][0].getKind(),
03253 "BitvectorTheoremProducer::bvConstMultAssocRule: "
03254 "e[0] & e[1][0] must be a BVCONST:\n e = " + e.toString());
03255 }
03256 int len = d_theoryBitvector->BVSize(e);
03257 int len0 = d_theoryBitvector->BVSize(e[0]);
03258 int len10 = d_theoryBitvector->BVSize(e[1][0]);
03259 int len11 = d_theoryBitvector->BVSize(e[1][1]);
03260 if(CHECK_PROOFS) {
03261 CHECK_SOUND(len == len0 && len0 == len10 && len0 == len11,
03262 "BitvectorTheoremProducer::bvConstMultAssocRule: "
03263 "kids of BVMULT must be equibvLength: ");
03264 }
03265 Rational e0 = d_theoryBitvector->computeBVConst(e[0]);
03266 Rational e10 = d_theoryBitvector->computeBVConst(e[1][0]);
03267 Expr c = d_theoryBitvector->newBVConstExpr(e0*e10, len);
03268 Expr output = d_theoryBitvector->newBVMultExpr(len, c, e[1][1]);
03269
03270 Proof pf;
03271 if(withProof())
03272 pf = newPf("bvconstmult_assoc_rule", e);
03273 Theorem result(newRWTheorem(e,output,Assumptions::emptyAssump(),pf));
03274 return result;
03275 }
03276
03277
03278
03279
03280 Theorem
03281 BitvectorTheoremProducer::bvMultAssocRule(const Expr& e) {
03282 if(CHECK_PROOFS) {
03283 CHECK_SOUND(BVMULT == e.getOpKind() && e.arity() == 2,
03284 "BitvectorTheoremProducer::bvMultAssocRule: "
03285 "input must be a BVMULT: " + e.toString());
03286 CHECK_SOUND(BVMULT == e[0].getOpKind() ||
03287 BVMULT == e[1].getOpKind(),
03288 "BitvectorTheoremProducer::bvMultAssocRule: "
03289 "e[0] or e[1] must be a BVMULT:\n e= " + e.toString());
03290 CHECK_SOUND(!(BVCONST == e[0].getOpKind() &&
03291 BVCONST == e[1][0].getOpKind()),
03292 "BitvectorTheoremProducer::bvMultAssocRule: "
03293 "e[0] & e[1][0] cannot be a BVCONST:\n e = " +
03294 e.toString());
03295 }
03296 int len = d_theoryBitvector->BVSize(e);
03297 int len0 = d_theoryBitvector->BVSize(e[0]);
03298 int len1 = d_theoryBitvector->BVSize(e[1]);
03299 if(CHECK_PROOFS)
03300 CHECK_SOUND(len == len0 && len0 == len1,
03301 "BitvectorTheoremProducer::bvMultAssocRule: "
03302 "kids of BVMULT must be equibvLength: ");
03303 Expr e0, e1;
03304 e0 = e[0];
03305 e1 = e[1];
03306
03307 std::vector<Expr> outputkids;
03308 if(BVMULT == e[0].getOpKind() && BVMULT != e[1].getOpKind()) {
03309 outputkids.push_back(e0[0]);
03310 outputkids.push_back(e0[1]);
03311 outputkids.push_back(e1);
03312
03313 } else if(BVMULT != e[0].getOpKind() && BVMULT == e[1].getOpKind()) {
03314 outputkids.push_back(e1[0]);
03315 outputkids.push_back(e1[1]);
03316 outputkids.push_back(e0);
03317 } else {
03318
03319 outputkids.push_back(e0[0]);
03320 outputkids.push_back(e0[1]);
03321 outputkids.push_back(e1[0]);
03322 outputkids.push_back(e1[1]);
03323 }
03324 sort(outputkids.begin(),outputkids.end());
03325
03326 Expr output;
03327 switch(outputkids.size()) {
03328 case 3: {
03329 Expr out1 =
03330 d_theoryBitvector->newBVMultExpr(len, outputkids[1],outputkids[2]);
03331 output =
03332 d_theoryBitvector->newBVMultExpr(len, outputkids[0], out1);
03333 break;
03334 }
03335 case 4: {
03336 Expr out0 =
03337 d_theoryBitvector->newBVMultExpr(len, outputkids[0], outputkids[1]);
03338 Expr out1 =
03339 d_theoryBitvector->newBVMultExpr(len, outputkids[2], outputkids[3]);
03340 output =
03341 d_theoryBitvector->newBVMultExpr(len, out0, out1);
03342 break;
03343 }
03344 }
03345
03346 Proof pf;
03347 if(withProof())
03348 pf = newPf("bvmult_assoc_rule", e);
03349 Theorem result(newRWTheorem(e,output,Assumptions::emptyAssump(),pf));
03350 return result;
03351 }
03352
03353
03354 Theorem
03355 BitvectorTheoremProducer::bvMultDistRule(const Expr& e) {
03356 if(CHECK_PROOFS) {
03357 CHECK_SOUND(BVMULT == e.getOpKind() && e.arity() == 2,
03358 "BitvectorTheoremProducer::bvMultDistRule: "
03359 "input must be a BVMULT: " + e.toString());
03360 CHECK_SOUND(BVPLUS == e[1].getOpKind(),
03361 "BitvectorTheoremProducer::bvMultDistRule: "
03362 "input must be of the form a*(t1+...+tn): " + e.toString());
03363 }
03364 int bvLength= d_theoryBitvector->BVSize(e);
03365 int e0len = d_theoryBitvector->BVSize(e[0]);
03366 int e1len = d_theoryBitvector->BVSize(e[1]);
03367 if(CHECK_PROOFS) {
03368 CHECK_SOUND(bvLength== e0len && e0len == e1len,
03369 "BitvectorTheoremProducer::bvMultDistRule: "
03370 "all subterms must of equal bvLength: " + e.toString());
03371 }
03372 const Expr& e0 = e[0];
03373 const Expr& e1 = e[1];
03374
03375 std::vector<Expr> v;
03376 Expr::iterator i = e1.begin();
03377 Expr::iterator iend = e1.end();
03378 for(;i != iend; ++i) {
03379 Expr s = d_theoryBitvector->newBVMultExpr(bvLength, e0, *i);
03380 v.push_back(s);
03381 }
03382 Expr output = d_theoryBitvector->newBVPlusExpr(bvLength,v);
03383
03384 Proof pf;
03385 if(withProof())
03386 pf = newPf("bvmult_distributivity_rule", e);
03387 Theorem result(newRWTheorem(e,output,Assumptions::emptyAssump(),pf));
03388 return result;
03389 }
03390
03391
03392
03393
03394 Theorem
03395 BitvectorTheoremProducer::flattenBVPlus(const Expr& e) {
03396 if(CHECK_PROOFS) {
03397 CHECK_SOUND(e.getOpKind() == BVPLUS && e.arity() >= 2,
03398 "BitvectorTheoremProducer::flattenBVPlus: e = "+e.toString());
03399 }
03400 int bvLength= d_theoryBitvector->BVSize(e);
03401 const int numOfKids = e.arity();
03402
03403 if(CHECK_PROOFS) {
03404 for(int i=0; i<numOfKids; ++i)
03405 CHECK_SOUND(d_theoryBitvector->BVSize(e[i]) == bvLength,
03406 "BitvectorTheoremProducer::flattenBVPlus: "
03407 "summands must be of the same bvLength as BVPLUS:\n e = "
03408 +e.toString());
03409 }
03410
03411
03412
03413 std::vector<Expr> v;
03414 for(int i = 0; i < numOfKids; ++i) {
03415 if(e[i].getOpKind() == BVPLUS) {
03416 const Expr& bvplusKid = e[i];
03417 const int bvplusArity = bvplusKid.arity();
03418 for(int j=0; j < bvplusArity; ++j)
03419 v.push_back(bvplusKid[j]);
03420 } else
03421 v.push_back(e[i]);
03422 }
03423 Expr eprime = d_theoryBitvector->newBVPlusExpr(bvLength, v);
03424
03425 Proof pf;
03426 if(withProof())
03427 pf = newPf("flatten_bvplus", e);
03428 return newRWTheorem(e, eprime, Assumptions::emptyAssump(), pf);
03429 }
03430
03431 void
03432 BitvectorTheoremProducer::collectOneTermOfPlus(const Rational & coefficient,
03433 const Expr& term,
03434 ExprMap<Rational> & likeTerms,
03435 Rational & plusConstant)
03436 {
03437 ExprMap<Rational>::iterator it = likeTerms.find(term);
03438
03439 if(it!=likeTerms.end())
03440 likeTerms[term] += coefficient;
03441 else {
03442
03443 bool foundNegated= false;
03444 if (!likeTerms.empty()) {
03445 Expr negTerm= d_theoryBitvector->pushNegationRec(term, true).getRHS();
03446 it = likeTerms.find(negTerm);
03447 if (it!= likeTerms.end()) {
03448 foundNegated = true;
03449
03450
03451 likeTerms[negTerm] += -coefficient;
03452 plusConstant+= -1;
03453 }
03454 }
03455 if (!foundNegated)
03456
03457 likeTerms[term] = coefficient;
03458 }
03459 }
03460
03461 void
03462 BitvectorTheoremProducer::collectLikeTermsOfPlus(const Expr& e,
03463 ExprMap<Rational> & likeTerms,
03464 Rational & plusConstant) {
03465 likeTerms.clear();
03466 Expr::iterator i = e.begin();
03467 Expr::iterator iend = e.end();
03468 plusConstant= 0;
03469
03470 for(; i!=iend; ++i) {
03471 const Expr s = *i;
03472 switch(s.getOpKind()) {
03473 case BVMULT: {
03474
03475 if (s[0].getKind() == BVCONST) {
03476 Rational coefficient= d_theoryBitvector->computeBVConst(s[0]);
03477 const Expr& var = s[1];
03478 collectOneTermOfPlus(coefficient, var, likeTerms, plusConstant);
03479 }
03480 else {
03481 if(CHECK_PROOFS) {
03482 CHECK_SOUND(BVCONST != s[1].getKind(),
03483 "TheoryBitvector::combineLikeTerms: "
03484 "Unexpected MULT syntax:\n\n s = " + s.toString()
03485 +"\n\n in e = "+e.toString());
03486 }
03487 collectOneTermOfPlus(1, s, likeTerms, plusConstant);
03488 }
03489 break;
03490 }
03491 case BVUMINUS:
03492 collectOneTermOfPlus(-1, s[0], likeTerms, plusConstant);
03493 break;
03494 case BVCONST:
03495 plusConstant += d_theoryBitvector->computeBVConst(s);
03496 break;
03497 default:
03498
03499 collectOneTermOfPlus(1, s, likeTerms, plusConstant);
03500 break;
03501 }
03502 }
03503 }
03504
03505 static Rational boundedModulo(const Rational & value, const Rational & modulo,
03506 const Rational & lowerBound) {
03507 Rational ret = mod(value, modulo);
03508 if(ret == 0)
03509 return ret;
03510
03511 if (ret< lowerBound)
03512 ret+= modulo;
03513 else {
03514
03515 Rational end= modulo+lowerBound;
03516 if (ret >= end)
03517 ret-= modulo;
03518 }
03519 return ret;
03520 }
03521
03522 void
03523 BitvectorTheoremProducer::
03524 createNewPlusCollection(const Expr & e,
03525 const ExprMap<Rational> & likeTerms,
03526 Rational & plusConstant,
03527 std::vector<Expr> & result) {
03528 int bvplusLength= d_theoryBitvector->BVSize(e);
03529
03530 Rational power2(1);
03531 for(int i=0; i<bvplusLength; i += 1) power2 *= 2;
03532
03533 ExprMap<Rational>::iterator j = likeTerms.begin();
03534 ExprMap<Rational>::iterator jend = likeTerms.end();
03535 for(; j!=jend; ++j) {
03536
03537
03538
03539 Rational coefficient = boundedModulo(j->second, power2, -power2/2+1);
03540 if(coefficient == 0)
03541 continue;
03542 Expr multiplicand = j->first;
03543 Expr monomial;
03544 if (coefficient<0) {
03545
03546
03547 multiplicand=
03548 d_theoryBitvector->pushNegationRec(multiplicand, true).getRHS();
03549 coefficient= coefficient*-1;
03550 plusConstant +=coefficient;
03551 }
03552 if(coefficient == 1)
03553 monomial = multiplicand;
03554 else {
03555 Expr coeffExpr =
03556 d_theoryBitvector->newBVConstExpr(coefficient, bvplusLength);
03557 monomial =
03558 d_theoryBitvector->newBVMultExpr(bvplusLength, coeffExpr,multiplicand);
03559 }
03560 if(CHECK_PROOFS) {
03561 CHECK_SOUND(BITVECTOR==monomial.getType().getExpr().getOpKind(),
03562 "TheoryBitvector::combineLikeTerms:"
03563 "each monomial must be a bitvector:\n"
03564 "monomial = " + monomial.toString());
03565 CHECK_SOUND(bvplusLength == d_theoryBitvector->BVSize(monomial),
03566 "TheoryBitvector::combineLikeTerms:"
03567 "bvLength of each monomial must be the same as e:\n"
03568 "monomial = " + monomial.toString() + "\n e = " + e.toString());
03569 }
03570 result.push_back(monomial);
03571 }
03572
03573 plusConstant = boundedModulo(plusConstant, power2, 0);
03574
03575
03576 if(plusConstant != 0) {
03577 const Expr c =
03578 d_theoryBitvector->newBVConstExpr(plusConstant, bvplusLength);
03579 result.push_back(c);
03580 }
03581 }
03582
03583 Expr
03584 BitvectorTheoremProducer::sumNormalizedElements(int bvplusLength,
03585 const std::vector<Expr>&items){
03586
03587
03588 switch(items.size()) {
03589 case 0:
03590
03591 return d_theoryBitvector->newBVZeroString(bvplusLength);
03592
03593 case 1:
03594
03595 return items[0];
03596
03597 default:
03598
03599 return d_theoryBitvector->newBVPlusExpr(bvplusLength, items);
03600 }
03601 }
03602
03603 Theorem
03604 BitvectorTheoremProducer::combineLikeTermsRule(const Expr& e) {
03605 TRACE("bitvector rewrite", "combineLikeTermsRule(",e.toString(), ") {");
03606 if(CHECK_PROOFS) {
03607 CHECK_SOUND(BVPLUS == e.getOpKind() && e.arity()>=2,
03608 "TheoryBitvector::combineLikeTerms: "
03609 "input must be a BVPLUS term:\n e = " + e.toString());
03610 int bvplusLength = d_theoryBitvector->BVSize(e);
03611 Expr::iterator i = e.begin();
03612 Expr::iterator iend = e.end();
03613 for(;i!=iend;++i) {
03614 const Expr& s = *i;
03615 if(s.getOpKind() == BVPLUS) {
03616 CHECK_SOUND(s.getOpKind() != BVPLUS,
03617 "TheoryBitvector::combineLikeTerms: "
03618 "BVPLUS must be flattened:\n e = " + e.toString());
03619 }
03620
03621 int bvLength= d_theoryBitvector->BVSize(s);
03622
03623 CHECK_SOUND(bvLength==bvplusLength,
03624 "TheoryBitvector::combineLikeTerms: "
03625 "BVPLUS must be padded:\n e = " + e.toString());
03626
03627 if(s.getOpKind()==BVMULT) {
03628 int s0len = d_theoryBitvector->BVSize(s[0]);
03629 int s1len = d_theoryBitvector->BVSize(s[1]);
03630 CHECK_SOUND(bvplusLength == s0len && s0len== s1len,
03631 "all monoms must have the samebvLength "
03632 "as the bvplus term: " + e.toString());
03633 }
03634 }
03635 }
03636 int bvplusLength = d_theoryBitvector->BVSize(e);
03637 ExprMap<Rational> likeTerms;
03638 Rational theConstant(0);
03639 collectLikeTermsOfPlus(e, likeTerms, theConstant);
03640
03641 std::vector<Expr> collection;
03642 createNewPlusCollection(e, likeTerms, theConstant, collection);
03643
03644 Expr output= sumNormalizedElements(bvplusLength, collection);
03645
03646 TRACE("bitvector rewrite",
03647 "combineLikeTermsRule =>",output.toString(), "}");
03648 Proof pf;
03649 if(withProof())
03650 pf=newPf("bvplus_combine_like_terms", e);
03651 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
03652 }
03653
03654 Theorem
03655 BitvectorTheoremProducer::lhsMinusRhsRule(const Expr& e) {
03656 if(CHECK_PROOFS) {
03657 CHECK_SOUND(EQ == e.getKind() && e.arity() == 2,
03658 "BitvectorTheoremProducer::lhsMinusRhsRule: "
03659 "input must be an EQ: e = " +e.toString());
03660 CHECK_SOUND(BVPLUS == e[0].getOpKind() ||
03661 BVPLUS == e[1].getOpKind(),
03662 "BitvectorTheoremProducer::lhsMinusRhsRule: "
03663 "atleast one of the input subterms must be BVPLUS:"
03664 "e = " +e.toString());
03665 int bvLength0 = d_theoryBitvector->BVSize(e[0]);
03666 int bvLength1 = d_theoryBitvector->BVSize(e[1]);
03667 CHECK_SOUND(bvLength0 == bvLength1,
03668 "BitvectorTheoremProducer::lhsMinusRhsRule: "
03669 "both sides of EQ must be same Length. e = " +e.toString());
03670 for(Expr::iterator i=e[0].begin(),iend=e[0].end();i!=iend;++i) {
03671 int bvLength= d_theoryBitvector->BVSize(*i);
03672 CHECK_SOUND(bvLength0 == bvLength,
03673 "BitvectorTheoremProducer::lhsMinusRhsRule: "
03674 "all subterms of e[0] must be of same Length."
03675 "e = " +e.toString());
03676 }
03677 for(Expr::iterator i=e[1].begin(),iend=e[1].end();i!=iend;++i) {
03678 int bvLength= d_theoryBitvector->BVSize(*i);
03679 CHECK_SOUND(bvLength1 == bvLength,
03680 "BitvectorTheoremProducer::lhsMinusRhsRule: "
03681 "all subterms of e[1] must be of same Length."
03682 "e = " +e.toString());
03683 }
03684 }
03685 Expr output;
03686 int bvLength = d_theoryBitvector->BVSize(e[0]);
03687 std::vector<Expr> k;
03688
03689
03690 Expr zeroStr = d_theoryBitvector->newBVZeroString(bvLength);
03691
03692 if(e[0] == e[1])
03693 output = Expr(EQ, zeroStr, zeroStr);
03694 else {
03695
03696 std::vector<Expr> e0K = e[0].getKids();
03697 std::vector<Expr> e1K = e[1].getKids();
03698 for(vector<Expr>::iterator i=e0K.begin(),iend=e0K.end();i!=iend;++i){
03699 for(vector<Expr>::iterator j=e1K.begin(),jend=e1K.end();j!=jend;++j){
03700 if(*i == *j) {
03701 e0K.erase(i);
03702 e1K.erase(j);
03703 break;
03704 }
03705 }
03706 }
03707 Expr newLhs = d_theoryBitvector->newBVPlusExpr(bvLength, e0K);
03708 k.push_back(newLhs);
03709 Expr newRhs = d_theoryBitvector->newBVPlusExpr(bvLength, e1K);
03710
03711 Expr uminus = d_theoryBitvector->newBVUminusExpr(newRhs);
03712
03713 k.push_back(uminus);
03714
03715 Expr lhsMinusRhs = d_theoryBitvector->newBVPlusExpr(bvLength,k);
03716
03717 output = Expr(EQ, lhsMinusRhs, zeroStr);
03718 }
03719
03720 Proof pf;
03721 if(withProof())
03722 pf = newPf("lhs_minus_rhs_rule", e);
03723 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
03724 }
03725
03726
03727 Theorem
03728 BitvectorTheoremProducer::bvuminusToBVPlus(const Expr& e) {
03729 if(CHECK_PROOFS) {
03730 CHECK_SOUND(BVUMINUS == e.getOpKind(),
03731 "BitvectorTheoremProducer::bvuminusBitBlastRule: "
03732 "input must be bvuminus: e = " + e.toString());
03733 }
03734 int bvLength = d_theoryBitvector->BVSize(e);
03735 std::vector<Expr> k;
03736 Expr negE0 = d_theoryBitvector->newBVNegExpr(e[0]);
03737 k.push_back(negE0);
03738 Expr plusOne = d_theoryBitvector->newBVConstExpr(1, bvLength);
03739 k.push_back(plusOne);
03740
03741 Expr output = d_theoryBitvector->newBVPlusExpr(bvLength, k);
03742 Proof pf;
03743 if(withProof())
03744 pf = newPf("bvuminus_bitblast_rule", e);
03745 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
03746 }
03747
03748
03749 Theorem
03750 BitvectorTheoremProducer::bvuminusBVConst(const Expr& e) {
03751 if(CHECK_PROOFS) {
03752 CHECK_SOUND(BVUMINUS == e.getOpKind() &&
03753 BVCONST == e[0].getKind(),
03754 "BitvectorTheoremProducer::bvuminusBVConst: "
03755 "e should be bvuminus, e[0] should be bvconst: e = " +
03756 e.toString());
03757 }
03758 Expr output;
03759 int e0Length = d_theoryBitvector->BVSize(e[0]);
03760
03761 if(d_theoryBitvector->computeBVConst(e[0]) == 0)
03762 output = e[0];
03763 else {
03764
03765 Rational x = d_theoryBitvector->computeNegBVConst(e[0]);
03766 output = d_theoryBitvector->newBVConstExpr(x, e0Length);
03767 }
03768
03769 Proof pf;
03770 if(withProof())
03771 pf = newPf("bvuminus_bvconst_rule", e);
03772 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
03773 }
03774
03775
03776 Theorem
03777 BitvectorTheoremProducer::bvuminusBVMult(const Expr& e) {
03778 if(CHECK_PROOFS) {
03779 CHECK_SOUND(BVUMINUS == e.getOpKind(),
03780 "BitvectorTheoremProducer::bvuminusBVMult: "
03781 "e should be bvuminus: e =" + e.toString());
03782 CHECK_SOUND(BVMULT == e[0].getOpKind(),
03783 "Bitvectortheoremproducer::bvuminusBVMult: "
03784 "in input expression e = " + e.toString() +
03785 "\ne[0] should be bvmult: e[0] = " + e[0].toString());
03786 CHECK_SOUND(BVCONST == e[0][0].getKind(),
03787 "Bitvectortheoremproducer::bvuminusBVMult: "
03788 "in input expression e = " + e.toString() +
03789 "\ne[0][0] should be bvconst: e[0][0] = " + e[0][0].toString());
03790 int bvLength = d_theoryBitvector->BVSize(e);
03791 int e0Length = d_theoryBitvector->BVSize(e[0]);
03792 int e00Length = d_theoryBitvector->BVSize(e[0][0]);
03793 CHECK_SOUND(bvLength == e0Length && e0Length == e00Length,
03794 "Bitvectortheoremproducer::bvuminusBVMult: "
03795 "in input expression e = " + e.toString() +
03796 "\nLengths of all subexprs must be equal: e = " + e.toString());
03797 }
03798
03799 Expr output;
03800 int e0Length = d_theoryBitvector->BVSize(e[0]);
03801
03802 Rational coeff = d_theoryBitvector->computeNegBVConst(e[0][0]);
03803 if(0 == coeff)
03804
03805 output = d_theoryBitvector->newBVZeroString(e0Length);
03806 else if (1 == coeff)
03807
03808 output = e[0][1];
03809 else {
03810
03811 Expr newcoeff = d_theoryBitvector->newBVConstExpr(coeff, e0Length);
03812 output = d_theoryBitvector->newBVMultExpr(e0Length, newcoeff, e[0][1]);
03813 }
03814
03815 Proof pf;
03816 if(withProof())
03817 pf = newPf("bvuminus_bvmult_rule", e);
03818 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
03819 }
03820
03821
03822 Theorem
03823 BitvectorTheoremProducer::bvuminusBVUminus(const Expr& e) {
03824 if(CHECK_PROOFS) {
03825 CHECK_SOUND(BVUMINUS == e.getOpKind(),
03826 "BitvectorTheoremProducer::bvuminusBVUminus: "
03827 "e should be bvuminus: e =" + e.toString());
03828 CHECK_SOUND(BVUMINUS == e[0].getOpKind(),
03829 "Bitvectortheoremproducer::bvuminusBVUminus: "
03830 "in input expression e = " + e.toString() +
03831 "\ne[0] should be bvmult: e[0] = " + e[0].toString());
03832 }
03833 Expr output;
03834
03835 output = e[0][0];
03836 Proof pf;
03837 if(withProof())
03838 pf = newPf("bvuminus_bvuminus_rule", e);
03839 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
03840 }
03841
03842
03843 Theorem
03844 BitvectorTheoremProducer::bvuminusVar(const Expr& e) {
03845 if(CHECK_PROOFS) {
03846 CHECK_SOUND(BVUMINUS == e.getOpKind(),
03847 "BitvectorTheoremProducer::bvuminusVar: "
03848 "e should be bvuminus: e =" + e.toString());
03849 }
03850 Expr output;
03851 std::vector<bool> res;
03852 int e0Length = d_theoryBitvector->BVSize(e[0]);
03853 for(int i=0; i<e0Length; ++i) {
03854 res.push_back(true);
03855 }
03856 Expr coeff = d_theoryBitvector->newBVConstExpr(res);
03857 output = d_theoryBitvector->newBVMultExpr(e0Length, coeff, e[0]);
03858
03859 Proof pf;
03860 if(withProof())
03861 pf = newPf("bvuminus_var_rule", e);
03862 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
03863 }
03864
03865
03866 Theorem
03867 BitvectorTheoremProducer::bvmultBVUminus(const Expr& e) {
03868 if(CHECK_PROOFS) {
03869 CHECK_SOUND(BVUMINUS == e.getOpKind(),
03870 "BitvectorTheoremProducer::bvmultBVUminus: "
03871 "e should be bvuminus: e =" + e.toString());
03872 CHECK_SOUND(BVMULT == e[0].getOpKind() &&
03873 BVCONST == e[0][0].getKind() &&
03874 BVUMINUS == e[0][1].getOpKind(),
03875 "Bitvectortheoremproducer::bvmultBVUminus: "
03876 "in input expression e = " + e.toString() +
03877 "\ne[0] has to be bvmult"
03878 "e[0][1] must be bvuminus: e[0] = " + e[0].toString());
03879 int bvLength = d_theoryBitvector->BVSize(e);
03880 int e00Length = d_theoryBitvector->BVSize(e[0][0]);
03881 int e01Length = d_theoryBitvector->BVSize(e[0][1]);
03882 CHECK_SOUND(bvLength == e00Length && e00Length == e01Length,
03883 "Bitvectortheoremproducer::bvmultBVUminus: "
03884 "in input expression e = " + e.toString() +
03885 "\nLengths of all subexprs must be equal.");
03886 }
03887 Expr output;
03888 int bvLength = d_theoryBitvector->BVSize(e);
03889 const Expr& coeff = e[0][0];
03890 Rational negatedcoeff = d_theoryBitvector->computeNegBVConst(coeff);
03891 const Expr& e010 = e[0][1][0];
03892
03893 if(0 == negatedcoeff)
03894
03895 output = d_theoryBitvector->newBVZeroString(bvLength);
03896 else if (1 == negatedcoeff)
03897
03898 output = e010;
03899 else {
03900
03901 Expr newcoeff = d_theoryBitvector->newBVConstExpr(negatedcoeff, bvLength);
03902 output = d_theoryBitvector->newBVMultExpr(bvLength, newcoeff, e010);
03903 }
03904
03905 Proof pf;
03906 if(withProof())
03907 pf = newPf("bvmult_bvuminus_rule", e);
03908 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
03909 }
03910
03911
03912 Theorem
03913 BitvectorTheoremProducer::bvuminusBVPlus(const Expr& e) {
03914
03915
03916
03917
03918
03919
03920
03921
03922
03923
03924
03925
03926
03927
03928
03929
03930
03931
03932
03933
03934
03935
03936
03937
03938
03939
03940
03941 Proof pf;
03942 if(withProof())
03943 pf = newPf("bvminus_bvplus_rule", e);
03944 return newRWTheorem(e, e, Assumptions::emptyAssump(), pf);
03945 }
03946
03947 Theorem
03948 BitvectorTheoremProducer::extractBVMult(const Expr& e) {
03949 if(CHECK_PROOFS) {
03950 CHECK_SOUND(e.getOpKind() == EXTRACT &&
03951 e[0].getOpKind() == BVMULT &&
03952 e[0].arity() == 2,
03953 "BitvectorTheoremProducer::extractBVMult: "
03954 "input must be an EXTRACT over BVMULT:\n e = "+e.toString());
03955 }
03956 const Expr& bvmult = e[0];
03957 int bvmultLen = d_theoryBitvector->BVSize(bvmult);
03958 int extractHi = d_theoryBitvector->getExtractHi(e);
03959 int extractLow = d_theoryBitvector->getExtractLow(e);
03960
03961 if(CHECK_PROOFS) {
03962 CHECK_SOUND(bvmultLen > extractHi,
03963 "BitvectorTheoremProducer::extractBVMult: "
03964 "bvmult Length must be greater than extract Length:\n e = "
03965 +e.toString());
03966 }
03967
03968 Expr output = d_theoryBitvector->newBVMultExpr(extractHi+1, bvmult[0],
03969 bvmult[1]);
03970 if(extractLow > 0)
03971 output=d_theoryBitvector->newBVExtractExpr(output, extractHi, extractLow);
03972
03973 Proof pf;
03974 if(withProof())
03975 pf = newPf("extract_bvmult_rule", e);
03976 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
03977 }
03978
03979 Theorem
03980 BitvectorTheoremProducer::extractBVPlus(const Expr& e) {
03981 if(CHECK_PROOFS) {
03982 CHECK_SOUND(e.getOpKind() == EXTRACT && e[0].getOpKind() == BVPLUS,
03983 "BitvectorTheoremProducer::extractBVPlus: "
03984 "input must be an EXTRACT over BVPLUS:\n e = "+e.toString());
03985 }
03986 const Expr& bvplus = e[0];
03987 int bvplusLen = d_theoryBitvector->BVSize(bvplus);
03988 int extractHi = d_theoryBitvector->getExtractHi(e);
03989 int extractLow = d_theoryBitvector->getExtractLow(e);
03990
03991 if(CHECK_PROOFS) {
03992 CHECK_SOUND(bvplusLen > extractHi,
03993 "BitvectorTheoremProducer::extractBVPlus: "
03994 "bvplus Length must be greater than extract bvLength:\n e = "
03995 +e.toString());
03996 }
03997
03998
03999 if(bvplusLen == extractHi+1)
04000 return d_theoryBitvector->reflexivityRule(e);
04001
04002
04003 Expr output(d_theoryBitvector->newBVPlusExpr(extractHi+1, bvplus.getKids()));
04004 if(extractLow > 0)
04005 output=d_theoryBitvector->newBVExtractExpr(output, extractHi, extractLow);
04006
04007 Proof pf;
04008 if(withProof())
04009 pf = newPf("extract_bvplus_rule", e);
04010 return newRWTheorem(e, output, Assumptions::emptyAssump(), pf);
04011 }
04012
04013
04014
04015 Theorem
04016 BitvectorTheoremProducer::typePredBit(const Expr& e) {
04017 if(CHECK_PROOFS) {
04018 CHECK_SOUND(d_theoryBitvector->getBaseType(e).getExpr().getOpKind() == BITVECTOR,
04019 "BitvectorTheoremProducer::typePredBit: e = "+e.toString());
04020 CHECK_SOUND(d_theoryBitvector->BVSize(e) == 1,
04021 "BitvectorTheoremProducer::typePredBit: e = "+e.toString());
04022 }
04023
04024 Proof pf;
04025 if(withProof())
04026 pf=newPf("type_pred_bit", e);
04027 return newTheorem(e.eqExpr(bvZero()) || e.eqExpr(bvOne()), Assumptions::emptyAssump(), pf);
04028 }
04029
04030
04031
04032 Theorem
04033 BitvectorTheoremProducer::expandTypePred(const Theorem& tp) {
04034 Expr tpExpr = tp.getExpr();
04035 if(CHECK_PROOFS) {
04036 CHECK_SOUND(tpExpr.getOpKind() == BVTYPEPRED ||
04037 (tpExpr.getKind() == NOT && tpExpr[0].getOpKind() == BVTYPEPRED),
04038 "BitvectorTheoremProducer::expandTypePred: "
04039 "Expected BV_TYPE_PRED wrapper:\n tp = "
04040 +tpExpr.toString());
04041 }
04042 Expr res;
04043 if(tpExpr.getKind() == NOT)
04044 res = d_theoryBitvector->falseExpr();
04045 else {
04046 Type t(d_theoryBitvector->getTypePredType(tpExpr));
04047 const Expr& e(d_theoryBitvector->getTypePredExpr(tpExpr));
04048 int size(d_theoryBitvector->getBitvectorTypeParam(t));
04049
04050
04051 if(size >= 2) {
04052 vector<Expr> kids;
04053 for(int i=0; i<size; i++) {
04054 Expr bit(d_theoryBitvector->newBVExtractExpr(e, i, i));
04055 kids.push_back(bit.eqExpr(bvZero()) || bit.eqExpr(bvOne()));
04056 }
04057 res = andExpr(kids);
04058 } else {
04059 res = (e.eqExpr(bvZero()) || e.eqExpr(bvOne()));
04060 }
04061 }
04062 Proof pf;
04063 if(withProof())
04064 pf = newPf("expand_type_pred", tp.getExpr(), tp.getProof());
04065
04066 return newTheorem(res, tp.getAssumptionsRef(), pf);
04067 }