bitvector_theorem_producer.cpp

Go to the documentation of this file.
00001 /*****************************************************************************/
00002 /*!
00003  * \file bitvector_theorem_producer.cpp
00004  * 
00005  * Author: Vijay Ganesh
00006  * 
00007  * Created: Wed May  5 16:19:49 PST 2004
00008  *
00009  * <hr>
00010  *
00011  * License to use, copy, modify, sell and/or distribute this software
00012  * and its documentation for any purpose is hereby granted without
00013  * royalty, subject to the terms and conditions defined in the \ref
00014  * LICENSE file provided with this distribution.
00015  * 
00016  * <hr>
00017  * 
00018  */
00019 /*****************************************************************************/
00020 // CLASS: BitvectorProofRules
00021 //
00022 // AUTHOR: Vijay Ganesh,   05/30/2003
00023 //
00024 // Description: TRUSTED implementation of bitvector proof rules.
00025 //
00026 ///////////////////////////////////////////////////////////////////////////////
00027 
00028 // This code is trusted
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 // TheoryBitvector:trusted method for creating BitvectorTheoremProducer
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   // Cache constants 0bin0 and 0bin1
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 // BitBlasting rules for equations
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   //e is (~BE(t1,i)<=>BE(t2,i))<=>true. to extract t1 we have to go 4 level deep
00120   //FIXME: later
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 // BitBlasting rules for dis-equations: separate rule for disequations
00211 // for efficiency sake
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   //e is the equation
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 // Rules for Inequations
00288 ///////////////////////////////////////////////////////////////////////
00289 
00290 
00291 //! Pad the kids of BVLT/BVLE to make their bvLength equal
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 //! signExtendRule: pads the input e with topBit to length len
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   //strip the top level SX applications
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 //! bitExtractSXRule
00367 Theorem
00368 BitvectorTheoremProducer::bitExtractSXRule(const Expr& e, int i) {
00369   //little bit of cheating here. calling a rule from inside a rule.
00370   //just a shorthand
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 //! Pad the kids of SIGN BVLT/SIGN BVLE to make their bvLength equal
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 /*! input: e0 <=(s) e1. output depends on whether the topbits(MSB) of
00418  *  e0 and e1 are constants. If they are constants then optimizations
00419  *  are done, otherwise the following rule is implemented.
00420  *
00421  *  e0 <=(s) e1 <==> (e0[n-1] AND NOT e1[n-1]) OR 
00422  *                   (e0[n-1] = e1[n-1] AND e0[n-2:0] <= e1[n-2:0])
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   //if both MSBs are constants, then we can optimize the output.  we
00470   //know precisely the value of the signed comparison in cases where
00471   //topbit of e0 and e1 are constants. e.g. |-1@t0 < 0@t1 is clearly
00472   //|-TRUE.
00473 
00474   //-1 indicates that both topBits are not known to be BVCONSTS
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   //useful expressions to be used below
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   //handle single bit e0 <=(s) e1 in a special way. this is clumsy
00489   //(i.e. extra and redundant code) but much more efficient and easy
00490   //to read
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       //both b0 and b1 are -1
00510       output = 
00511   eKind==BVSLT ? 
00512   MSB0isOne.andExpr(MSB1isZero) : 
00513   MSB0isOne.orExpr(MSB1isZero);
00514   } else {
00515     //useful expressions to be used below
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 //     Expr newBVLTreverse = 
00523 //       eKind==BVSLT ?
00524 //       d_theoryBitvector->newBVLTExpr(newE1,newE0):
00525 //       d_theoryBitvector->newBVLEExpr(newE1,newE0);
00526 
00527     
00528     //both MSBs are simultaneously constants
00529     if(-1 != b0 && -1 !=b1) {
00530       //e0 is negative and e1 is positive
00531       if(b0 == 1 && b1 == 0)
00532   output = tExpr;
00533       //e0 is positive and e1 is negative
00534       else if(b0 == 0 && b1 == 1)
00535   output = fExpr;
00536       //e0 = e1, so result is determined by the rest of the bits
00537       else {
00538   output = newBVLT;
00539       }
00540     }
00541     else if(-1 != b0 && -1 == b1) {  
00542       //only b0 is a constant. Both topBits are not simultaneously constants. 
00543       
00544       //if (b0==0)
00545       //    e0 <=(s) e1 <==> NOT e1[n-1] AND e0[n-2:0] <= e1[n-2:0])
00546       //else
00547       //    e0 <=(s) e1 <==> NOT e1[n-1] OR (e1[n-1] AND e0[n-2:0] <= e1[n-2:0]))
00548 
00549       output = 
00550   (b0==0) ?
00551   //means that b1 has to be 0 and e0[n-2:0] <= e1[n-2:0] 
00552   MSB1isZero.andExpr(newBVLT) :
00553   //means that either b1 is 0 or (b1 is 1 and e0[n-2:0] <= e1[n-2:0])
00554   MSB1isZero.orExpr(MSB1isOne.andExpr(newBVLT));
00555     }
00556     else if(-1 == b0 && -1 != b1) {  
00557       //only b1 is a constant. Both topBits are not simultaneously constants.     
00558       
00559       //if (b1==0)
00560       //    e0 <=(s) e1 <==> e0[n-1] OR (NOT e0[n-1] AND e0[n-2:0] <= e1[n-2:0]))
00561       //else
00562       //    e0 <=(s) e1 <==> e0[n-1] AND e0[n-2:0] <= e1[n-2:0]))
00563       
00564       output = 
00565   (b1==0) ?
00566   //means that either b0 must be 1 or (b0 = 0 and e0[n-2:0] <= e1[n-2:0])
00567   MSB0isOne.orExpr(MSB0isZero.andExpr(newBVLT)) :
00568   //means that b0 must be 1 and e0[n-2:0] <= e1[n-2:0]
00569   MSB0isOne.andExpr(newBVLT);
00570     } else {
00571       //both top bits are not constants.
00572 
00573       //(e0[n-1] AND NOT e1[n-1])
00574       Expr k0 = MSB0isOne.andExpr(MSB1isZero);
00575       
00576       //(e0[n-1] = e1[n-1])
00577       Expr k1 = MSB0.eqExpr(MSB1);
00578       
00579       //e0 <=(s) e1 <==> (e0[n-1] AND NOT e1[n-1]) OR 
00580       //                 (e0[n-1] = e1[n-1] AND e0[n-2:0] <= e1[n-2:0])
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 /*! NOT(e[0][0] < e[0][1]) <==> (e[0][1] <= e[0][0]), 
00593  *  NOT(e[0][0] <= e[0][1]) <==> (e[0][1] < e[0][0])
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 //! if(lhs==rhs) then we have (lhs < rhs <==> false),(lhs <= rhs <==> true)
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 //! |= 0 <= foo <-> TRUE
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 //! if indeed e[0] < e[1] then (e<==>true) else (e<==>false)
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   //recall that lhs_i,rhs_i are produced by bitblastTerm(), and hence
00777   //are boolean terms. we need to make them bitvector terms
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   // Check for the shortcuts
00796   if(b1.isFalse() && b2.isTrue()) // b1 < b2
00797     output = trueExpression;
00798   else if(b1.isTrue() && b2.isFalse()) // b1 > b2
00799     output = falseExpression;
00800   //   else if(e0len==1) {
00801   // If this is the last bit, and one of them is a constant
00802   //     if(kind==BVLE && (b1.isFalse() || b2.isTrue())) // F <= x or x <= T
00803   //       output = trueExpression;
00804   //     else if(kind==BVLT && (b2.isFalse() || b1.isTrue())) // x < F or T < x
00805   //       output = falseExpression;
00806   //}
00807   
00808   // No shortcuts found
00809   if(output.isNull()) {   
00810     //construct b1<=>false
00811     //Expr b1_0 = b1.iffExpr(falseExpression);
00812     Expr b1_0 = b1.notExpr();
00813     //construct b2<=>true
00814     //Expr b2_1 = b2.iffExpr(trueExpression);    
00815     Expr b2_1 = b2;
00816     //construct (b1<=>b2)
00817     Expr b1_eq_b2 = b1.iffExpr(b2);
00818 
00819     //first process the top most bits
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     //if the bvLength of the vector > 1 processfurther, otherwise we are
00825     //done
00826     if(e0len > 1) {
00827       //construct e0[n-2:0]
00828       Expr e0_extract = 
00829   d_theoryBitvector->newBVExtractExpr(e[0],e0len-2,0);
00830       //construct e1[n-2:0]
00831       Expr e1_extract = 
00832   d_theoryBitvector->newBVExtractExpr(e[1],e1len-2,0);
00833 
00834       Expr a;
00835       if(kind==BVLT)
00836   //construct e0[n-2:0] < e1[n-2:0]
00837   a = d_theoryBitvector->newBVLTExpr(e0_extract,e1_extract);
00838       else
00839   //construct e0[n-2:0] <= e1[n-2:0]
00840   a = d_theoryBitvector->newBVLEExpr(e0_extract,e1_extract);
00841   
00842       //construct (b1=b2 and a)
00843       Expr b1_eq_b2_and_a = b1_eq_b2.andExpr(a);
00844       //construct (b1=0 and/or b2=1) or (b1=b2 and a)
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 // BitExtracting rules for terms
00857 ///////////////////////////////////////////////////////////////////////
00858 
00859 //! t[i] ==> t[i:i] = 0bin1   or    NOT t[i] ==> t[i:i] = 0bin0
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 //! t[i] <=> t[i:i][0]   (to use rewriter for simplifying t[i:i])
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     //check if the expr is indeed a bitvector constant.   
00915     CHECK_SOUND(BVCONST == x.getKind(),
00916     "BitvectorTheoremProducer::bitExtractConstant:"
00917     "the bitvector must be a constant.");
00918     //check if 0<= i < bvLength of bitvector constant    
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   // bool-extract of the bitvector constant
00927   const Expr bitExtract = d_theoryBitvector->newBoolExtractExpr(x, i);
00928   
00929   //extract the actual expr_value string, bitextract it at i and check
00930   //if the value is 'false'. if so then return c[i] <==> false else
00931   //return c[i] <==> true.
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     //check if the expr is indeed a bitvector term and a concat.   
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   //check if 0<= i < bvLength of bitvector constant    
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   // bool-extract of the bitvector constant
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   //size of k will always be >= 0
01039   switch(k.size()) {
01040   case 0:
01041     //the vector k will remain empty if all bits in coeff are 0's
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   // bool-extract of the bitvector term
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   // bool-extract of the bitvector term
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     //check if the expr is indeed a bitvector term and a concat.   
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     //check if 0<= i < bvLength of bitvector constant    
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   // bool-extract of the bitvector constant
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     //constructing an XOR of 3 exprs using equivalences.  Note that (x
01226     //\xor y \xor z) is the same as (x \iff y \iff z). but remember, x
01227     //\xor y is not the same as x \iff y, but is equal instead to x
01228     //\neg\iff y
01229     rhs = t1_iBit.iffExpr(t2_iBit).iffExpr(carry_iBit);
01230     //cout << "the addition output is : " << rhs.toString() << "\n";
01231     //TRACE("bitvector",
01232     //  "output of bitExtractBVPlus(", carry_iBit.toString(), ")");
01233   } else
01234     //bitblasting the 0th bit. construct NOT(t1_iBit <=> t2_iBit)
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     //constructing an XOR of 3 exprs using equivalences.  Note that (x
01327     //\xor y \xor z) is the same as (x \iff y \iff z). but remember, x
01328     //\xor y is not the same as x \iff y, but is equal instead to x
01329     //\neg\iff y
01330     rhs = t1_iBit.iffExpr(t2_iBit).iffExpr(carry_iBit);
01331     //cout << "the addition output is : " << rhs.toString() << "\n";
01332   } else
01333     //bitblasting the 0th bit. construct NOT(t1_iBit <=> t2_iBit)
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 //! compute carryout of the current bits and cache them, and return
01345 //carryin of the current bits
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     //carry.push_back(x);
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       //(*d_bvPlusCarryCacheRightBV.find(indexMinusOne)).second;
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   //cout << "the carry for" << index << " is : " << carryout << "\n";
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   //skip the first kid
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     //check if the expr is indeed a bitvector term and a concat.   
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     //check if 0<= i < Length of bitvector constant    
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   // bool-extract of the bitvector constant
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     //check if the expr is indeed a bitvector term and a concat.   
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     //check if 0<= i < Length of bitvector constant 
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   // bool-extract of the bitvector constant
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     //check if the expr is indeed a bitvector term and a left shift.
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     //check if 0<= i < bvLength of bitvector constant    
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   // bool-extract of the bitvector constant
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     //check if the expr is indeed a bitvector term and a concat.   
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   //check if 0<= i < bvLength of bitvector constant    
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   // bool-extract of the bitvector constant
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 //! Check that all the kids of e are BVCONST
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 //! c1=c2 <=> TRUE/FALSE (equality of constant bitvectors)
01680 Theorem BitvectorTheoremProducer::eqConst(const Expr& e) {
01681   if(CHECK_PROOFS) {
01682     // The kids must be constant expressions
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 //! |- c1=c2 ==> |- AND(c1[i:i] = c2[i:i]) - expanding equalities into bits
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 //! t<<n = c @ 0bin00...00, takes e == (t<<n)
01731 Theorem BitvectorTheoremProducer::leftShiftToConcat(const Expr& e) {
01732   if(CHECK_PROOFS) {
01733     // The kids must be constant expressions
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 //! t<<n = c @ 0bin00...00, takes e == (t<<n)
01755 Theorem BitvectorTheoremProducer::constWidthLeftShiftToConcat(const Expr& e) {
01756   if(CHECK_PROOFS) {
01757     // The kids must be constant expressions
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 //! t>>m = 0bin00...00 @ t[bvLength-1:m], takes e == (t>>n)
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 //! k*t = BVPLUS(n, <sum of shifts of t>) -- translation of k*t to BVPLUS
01909 /*! If k = 2^m, return k*t = t@0...0 */
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; // The resulting expression
01926   if(k == 0) {
01927     // Construct n-bit vector of 0's
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     // Construct the vector of shifts, the kids of the resulting BVPLUS
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     // For negative k, compute (~res+1), the 2's complement
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   // Check if we can apply the rewrite rule
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     // if kid is 0bin0 @ ..., then we can shorten its effective size
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   // Compute ceiling of log2(numKids)
01985   int log2 = 0;
01986   for(int i=1; i < numKids; i *=2, log2++);
01987   if(log2+maxKidSize > bvplusSize) {
01988     // Skip the rewrite, it's potentially unsound
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 //! c1[i:j] = c  (extraction from a constant bitvector)
02005 Theorem BitvectorTheoremProducer::extractConst(const Expr& e) {
02006   if(CHECK_PROOFS) {
02007     // The kids must be constant expressions
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 // t[n-1:0] = t  for n-bit t
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 //! t[i:j][k:l] = t[k+j:l+j]  (eliminate double extraction)
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     // Check the bounds
02073     CHECK_SOUND(0 <= low && low <= hi,
02074     "BitvectorTheoremProducer::extractExtract: e = "+e.toString());
02075     // The base expression must also be EXTRACT
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     // The extractions must be within the correct bounds
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 //! (t1 @ t2)[i:j] = t1[...] @ t2[...]  (push extraction through concat)
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     // Check the bounds
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     // The base expression  must be CONCAT
02124     CHECK_SOUND(e0.getOpKind() == CONCAT,
02125     "BitvectorTheoremProducer::extractConcat: e0 = "
02126     +e0.toString());
02127   }
02128   // Collect the relevant kids from concatenation
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) { // Previous kids were outside of extract window
02140       if(hi >= newWidth) { // The first relevant kid
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       // High end of the current kid is in the extract window
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     } // The remaining kids are outside of extract window, skip them
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 // (t1 op t2)[i:j] = t1[i:j] op t2[i:j] -- push extraction through
02170 // bit-wise operator
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     // Check the bounds
02190     CHECK_SOUND(0 <= low && low <= hi,
02191     "BitvectorTheoremProducer::"+pfName+": e = "+e.toString());
02192     // The base expression must also be EXTRACT
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 //! (t1 & t2)[i:j] = t1[i:j] & t2[i:j]  (push extraction through OR)
02210 Theorem
02211 BitvectorTheoremProducer::extractAnd(const Expr& e) {
02212   return extractBitwise(e, BVAND, "extract_and");
02213 }
02214 
02215 
02216 //! (t1 | t2)[i:j] = t1[i:j] | t2[i:j]  (push extraction through AND)
02217 Theorem
02218 BitvectorTheoremProducer::extractOr(const Expr& e) {
02219   return extractBitwise(e, BVOR, "extract_or");
02220 }
02221 
02222 
02223 //! (~t)[i:j] = ~(t[i:j]) (push extraction through NEG)
02224 Theorem
02225 BitvectorTheoremProducer::extractNeg(const Expr& e) {
02226   return extractBitwise(e, BVNEG, "extract_neg");
02227 }
02228 
02229 //! ite(c,t1,t2)[i:j] <=> ite(c,t1[i:j],t2[i:j])
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 //! ~ite(c,t1,t2) <=> ite(c,~t1,~t2)
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 //! ~c1 = c  (bit-wise negation of a constant bitvector)
02295 Theorem BitvectorTheoremProducer::negConst(const Expr& e) {
02296   if(CHECK_PROOFS) {
02297     // The kids must be constant expressions
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 //! ~(t1@...@tn) = (~t1)@...@(~tn) -- push negation through concat
02317 Theorem
02318 BitvectorTheoremProducer::negConcat(const Expr& e) {
02319   if(CHECK_PROOFS) {
02320     // The kids must be constant expressions
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 //! ~(~t) = t  -- eliminate double negation
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 //! ~(t1 & t2) = ~t1 | ~t2  -- DeMorgan's Laws
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 //! ~(t1 | t2) = ~t1 & ~t2  -- DeMorgan's Laws
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 //! ~(t1 xor t2) = ~t1 xor t2
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 //! ~(t1 xnor t2) = t1 xor t2
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 //! c1&c2 = c  (bit-wise AND constant bitvectors)
02457 //! c1 op c2 = c  -- bit-wise AND and OR of constant bitvectors
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     // The kids must be constant expressions
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   // Initialize 'bits' with all 1's or 0's, depending on isAnd value
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); // Reserve the first element for the constant bitvector
02485   size_t ii(0); // The next index of idxs to match
02486   int idx(idxs[0]); // The index of the next constant (for efficiency)
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       // "AND" in the constant bitvector
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       // Advance the index of idxs
02504       if(ii < idxs.size())
02505   idx = idxs[++ii];
02506       else
02507   idx = e.arity();
02508     }
02509     else // Not a constant, add to the list of kids
02510       kids.push_back(ei);
02511   }
02512   // Create the new constant bitvector and make it the first kid
02513   kids[0] = d_theoryBitvector->newBVConstExpr(bits);
02514   // Contruct the final expression.
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     // Construct a list of indices as a RAW_LIST Expr
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 //! ... & (t1@...@tk) & ... = (...& t1 &...)@...@(...& tk &...)
02533 /*!
02534  * Lifts concatenation to the top of bit-wise AND.  Takes the
02535  * bit-wise AND expression 'e' and the index 'i' of the
02536  * concatenation.
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   // Build the top-level concatenation
02557   vector<Expr> concatKids;
02558   // Current extraction window
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     // Kids of the current BVAND / BVOR
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   // flatten the nested ops
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   // drop duplicate subterms and detect conflicts like t, ~t
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     //check if *j is duplicated or its negation already occured
02619     flag = sameKidCheck(*j, likeTerms);
02620     switch(flag) {
02621     case 0: 
02622       //no duplicates
02623       outputkids.push_back(*j);
02624       break;
02625     case 1: 
02626       //duplicate detected. ignore the duplicate
02627       break;
02628     case -1:{
02629       //conflict detected
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     // Sort the kids according to operator<(Expr, Expr)
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());//iterator is cheaper than [0]      
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 //! c1&c2 = c  (bit-wise AND constant bitvectors)
02666 Theorem BitvectorTheoremProducer::andConst(const Expr& e,
02667              const std::vector<int>& idxs) {
02668   return bitwiseConst(e, idxs, true);
02669 }
02670 
02671 // 0bin0...0 & t = 0bin0...0  -- bit-wise AND with zero bitvector
02672 /* \param e is the bit-wise AND expr
02673  *  \param idx is the index of the zero bitvector
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]; // All kids are const bitvectors of 1's
02744   return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
02745 }
02746 
02747 
02748 //! ... & (t1@...@tk) & ... = (...& t1 &...)@...@(...& tk &...)
02749 /*!
02750  * Lifts concatenation to the top of bit-wise AND.  Takes the
02751  * bit-wise AND expression 'e' and the index 'i' of the
02752  * concatenation.
02753  */
02754 Theorem
02755 BitvectorTheoremProducer::andConcat(const Expr& e, int idx) {
02756   return bitwiseConcat(e, idx, true);
02757 }
02758 
02759 
02760 //! (t1 & (t2 & t3) & t4) = t1 & t2 & t3 & t4  -- flatten bit-wise AND
02761 /*! Also reorders the terms according to a fixed total ordering */
02762 Theorem
02763 BitvectorTheoremProducer::andFlatten(const Expr& e) {
02764   return bitwiseFlatten(e, true);
02765 }
02766 
02767 
02768 
02769 //! c1|c2 = c  (bit-wise OR of constant bitvectors)
02770 Theorem BitvectorTheoremProducer::orConst(const Expr& e,
02771             const std::vector<int>& idxs) {
02772   return bitwiseConst(e, idxs, false);
02773 }
02774 
02775 
02776 //! 0bin1...1 | t = 0bin1...1  -- bit-wise OR with bitvector of 1's
02777 /*! \param e is the bit-wise OR expr
02778  *  \param idx is the index of the bitvector of 1's
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]; // All kids are const bitvectors of 0's
02853   return newRWTheorem(e, res, Assumptions::emptyAssump(), pf);
02854 }
02855 
02856 /*! checks if e is already present in likeTerms without conflicts. 
02857  *  if yes return 1, else{ if conflict return -1 else return 0 }
02858  *  we have conflict if 
02859  *          1. the kind of e is BVNEG, 
02860  *                 and e[0] is already present in likeTerms
02861  *          2. ~e is present in likeTerms already
02862  */
02863 int BitvectorTheoremProducer::sameKidCheck(const Expr&  e, 
02864              ExprMap<int>& likeTerms) {  
02865   //initially flag = 0, i.e. we assume e is not in likeTerms
02866   int flag = 0;
02867   
02868   //look for e
02869   ExprMap<int>::iterator it = likeTerms.find(e);
02870 
02871   //no entry found for e
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   //found an entry for e 
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 //! ... | (t1@...@tk) | ... = (...| t1 |...)@...@(...| tk |...)
02914 /*!
02915  * Lifts concatenation to the top of bit-wise OR.  Takes the
02916  * bit-wise OR expression 'e' and the index 'i' of the
02917  * concatenation.
02918  */
02919 Theorem
02920 BitvectorTheoremProducer::orConcat(const Expr& e, int idx) {
02921   return bitwiseConcat(e, idx, false);
02922 }
02923 
02924 
02925 //! (t1 | (t2 | t3) | t4) = t1 | t2 | t3 | t4  -- flatten bit-wise OR
02926 /*! Also reorders the terms according to a fixed total ordering */
02927 Theorem
02928 BitvectorTheoremProducer::orFlatten(const Expr& e) {
02929   return bitwiseFlatten(e, false);
02930 }
02931 
02932 
02933 
02934 //! c1@c2@...@cn = c  (concatenation of constant bitvectors)
02935 Theorem BitvectorTheoremProducer::concatConst(const Expr& e) {
02936   if(CHECK_PROOFS) {
02937     // The kids must be constant expressions
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 //! Flatten one level of nested concatenation, e.g.: x@(y@z)@w = x@y@z@w
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   // Rebuild the expression: copy the kids and flatten the nested CONCATs
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 //! Merge n-ary concat. of adjacent extractions: x[15:8]@x[7:0] = x[15:0]
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]; // The common base of all extractions
02993 
02994   if(CHECK_PROOFS) {
02995     // Check that all extractions have the same base and are contiguous
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 //! BVPLUS(n, c1,c2,...,cn) = c  (bit-vector plus of constant bitvectors)
03030 Theorem BitvectorTheoremProducer::bvplusConst(const Expr& e) {
03031   if(CHECK_PROOFS) {
03032     // The kids must be constant expressions
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   // Transfer the values for each bitvector to a Rational, then add it
03041   // to the accumulator.
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   // Extract the bits of 'acc' into the vector
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 /*! @brief c0*c1 = c, multiplication of two BVCONST
03068  */
03069 Theorem BitvectorTheoremProducer::bvmultConst(const Expr& e) {
03070   if(CHECK_PROOFS) {
03071     // The kids must be constant expressions
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   // Do the multiplication
03079   Rational x = d_theoryBitvector->computeBVConst(e[1]) * c;
03080 
03081   // Extract the bits of 'x' into the vector
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 //! t1*a <==> a*t1
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 //! Converts e into a BVVECTOR of bvLength 'len'
03159 /*!
03160  * \param len is the desired bvLength of the resulting bitvector
03161  * \param e is the original bitvector of arbitrary bvLength
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     // size < len
03181     Expr zero = d_theoryBitvector->newBVZeroString(len-size);
03182     res = d_theoryBitvector->newConcatExpr(zero,e);
03183   }
03184   return res;
03185 }
03186 
03187 //! Pad the kids of BVMULT to make their bvLength = # of output-bits
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 //! Pad the kids of BVMULT to make their bvLength = # of output-bits
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 //! a*(b*t) <==> (a*b)*t, where a,b,t have same bvLength
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 //FIXME: make BVMULT n-ary
03279 //! (t1*t2)*t3 <==> t1*(t2*t3), where t1<t2<t3
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     //both must be BVMULTs
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 //! a*(t1+...+tn) <==> (a*t1+...+a*tn), where all kids are equibvLength
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 //! input BVPLUS expression e.output e <==> e', where e' has no BVPLUS
03392 //  kids. remember, the invariant is that kids are already in
03393 //  bvplus normal-form
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   //collect the kids of e in the vector v. if any kid is a BVPLUS,
03412   //then collect its kids into v. then construct a BVPLUS expr
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     // Check if there is a negated form of this term already in likeTerms map.
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   // Use the rule that ~(c*x) = -c*x-1 (based on the fact: -x= ~x+1).
03451   likeTerms[negTerm] += -coefficient;
03452   plusConstant+= -1;
03453       }
03454     }
03455     if (!foundNegated)
03456       // Negated form was not found, need to register the new positive form.
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   //go thru' bvplus term, one monom at a time
03470   for(; i!=iend; ++i) {
03471     const Expr s = *i;
03472     switch(s.getOpKind()) {
03473     case BVMULT: {
03474       //if monom is BVMULT, collect like terms using ExprMap
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 { // non-linear mult
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       //we have just a variable; check if variable in ExprMap
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       // end is one position beyond upper limit.
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   // Compute 2^n, to use as a modulus base
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     // The coefficient will be equivalent to j->second modulus of power2 
03537     // and in the range [-power2/2+1, power2/2]
03538     // FIXME: Need to reconsider the "best" coefficient normalization scheme.
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       // Make the coefficient positive: c<0 ;
03546       // (c*x)= (-c)*(-x)= (-c)*(~x+1)=(-c)*(~x) -c
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   // Positive modulo of the constant 
03573   plusConstant = boundedModulo(plusConstant, power2, 0);
03574 
03575   //make the constant a subterm of the BVPLUS expression
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   //construct a new BVPLUS term using the ExprMap.  if size of
03587   //likeTerms is less than 2, then do NOT construct BVPLUS
03588   switch(items.size()) {
03589   case 0:
03590     //items are empty. only constant 0 remains
03591     return d_theoryBitvector->newBVZeroString(bvplusLength);
03592     
03593   case 1:
03594     //items may contain a Expr of the form a*x or x or a
03595     return items[0];
03596     
03597   default:
03598     //items have 2 or more kids
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       //bvLength checks for BVCONST and variables
03623       CHECK_SOUND(bvLength==bvplusLength,
03624       "TheoryBitvector::combineLikeTerms: "
03625       "BVPLUS must be padded:\n e = " + e.toString());
03626       //Length checks for BVMULTs
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   //construct 0 of bvLength
03690   Expr zeroStr = d_theoryBitvector->newBVZeroString(bvLength);
03691 
03692   if(e[0] == e[1])
03693     output = Expr(EQ, zeroStr, zeroStr);
03694   else {
03695     //drop common subterms
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     //construct -rhs
03711     Expr uminus = d_theoryBitvector->newBVUminusExpr(newRhs);
03712     //push back -rhs
03713     k.push_back(uminus);  
03714     //construct lhs-rhs
03715     Expr lhsMinusRhs = d_theoryBitvector->newBVPlusExpr(bvLength,k);
03716     //construct lhs-rhs=0
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 //! generic rule used for bitblasting step. -e <==> ~e+1
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 //! -0 <==> 0, -c <==> ~c+1
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   // output == 0
03761   if(d_theoryBitvector->computeBVConst(e[0]) == 0)
03762     output = e[0];
03763   else {
03764     // Compute -c, which is ~c+1
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 //! -(c*t)<=>(-c)*t; if -c==0 return e<=>0. if(-c==1) return e<=>t
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   //e is of the form -(c*t)
03799   Expr output;
03800   int e0Length = d_theoryBitvector->BVSize(e[0]);
03801   //compute ~c+1 
03802   Rational coeff = d_theoryBitvector->computeNegBVConst(e[0][0]);
03803   if(0 == coeff)
03804     //if ~c+1 == 0
03805     output = d_theoryBitvector->newBVZeroString(e0Length);
03806   else if (1 == coeff)
03807     //if ~c+1 == 1
03808     output = e[0][1];
03809   else {
03810     //construct (~c+1)*t
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 //! -(-e) <==> e
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   // -(-e) <==> e
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 //! -v <==> -1*v
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 //! c*(-t) <==> (-c)*t
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     //if ~c+1 == 0
03895     output = d_theoryBitvector->newBVZeroString(bvLength);
03896   else if (1 == negatedcoeff)
03897     //if ~c+1 == 1
03898     output = e010;
03899   else {
03900     //construct (~c+1)*t
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 //! -(c1*t1+...+cn*tn) <==> (-(c1*t1)+...+-(cn*tn))
03912 Theorem 
03913 BitvectorTheoremProducer::bvuminusBVPlus(const Expr& e) {
03914 //   if(CHECK_PROOFS) {
03915 //     CHECK_SOUND(BVUMINUS == e.getOpKind(),
03916 //    "BitvectorTheoremProducer::bvuminusBVPlus: "
03917 //    "e should be bvuminus: e =" + e.toString());    
03918 //     CHECK_SOUND(BVPLUS == e[0].getOpKind(),
03919 //    "BitvectorTheoremProducer::bvuminusBVPlus: "
03920 //    "e[0] should be bvplus: e[0] =" + e[0].toString());    
03921 //   }
03922 //   int bvLength = d_theoryBitvector->BVSize(e);
03923 //   const Expr& e0 = e[0];
03924 //   Expr::iterator i = e0.begin();
03925 //   Expr::iterator iend = e0.end();
03926 //   std::vector<Expr> output;
03927 //   for(; i!=iend; ++i) {
03928 //     const Expr& s = *i;
03929 //     Expr t = d_theoryBitvector->newBVUminusExpr(s);
03930 //     output.push_back(t);
03931 //   }
03932 //   Expr outputPlus = 
03933 //     d_theoryBitvector->newBVPlusExpr(bvLength, output);
03934 
03935 //   Assumptions a;
03936 //   Proof pf;
03937 //   if(withProof())
03938 //     pf = newPf("bvminus_bvplus_rule", e);
03939 //   return newRWTheorem(e, outputPlus, a, pf);
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   // Shortcut
03999   if(bvplusLen == extractHi+1)
04000     return d_theoryBitvector->reflexivityRule(e);
04001 
04002   // Shorten the result width of the bvplus term
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 // |- t=0 OR t=1  for any 1-bit bitvector t
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 //! Expand the type predicate wrapper (compute the actual type predicate)
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     //   DebugAssert(BVSize(e)==size, "TheoryBitvector::computeTypePred: e="
04050     //        +e.toString()+", t="+t.toString());
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 }

Generated on Tue Jul 3 14:33:35 2007 for CVC3 by  doxygen 1.5.1