/****************************************************************************** * Top contributors (to current version): * Liana Hadarean, Aina Niemetz, Gereon Kremer * * This file is part of the cvc5 project. * * Copyright (c) 2009-2025 by the authors listed in the file AUTHORS * in the top-level source directory and their institutional affiliations. * All rights reserved. See the file COPYING in the top-level source * directory for licensing information. * **************************************************************************** * * Implementation of bitblasting functions for various operators. */ #include "cvc5_private.h" #ifndef CVC5__THEORY__BV__BITBLAST__BITBLAST_STRATEGIES_TEMPLATE_H #define CVC5__THEORY__BV__BITBLAST__BITBLAST_STRATEGIES_TEMPLATE_H #include #include #include "expr/node.h" #include "theory/bv/bitblast/bitblast_utils.h" #include "theory/bv/theory_bv_utils.h" #include "util/bitvector.h" namespace cvc5::internal { namespace theory { namespace bv { /** * Default Atom Bitblasting strategies: * * @param node the atom to be bitblasted * @param bb the bitblaster */ template T UndefinedAtomBBStrategy(TNode node, TBitblaster* bb) { Trace("bitvector") << "TheoryBV::Bitblaster Undefined bitblasting strategy for kind: " << node.getKind() << "\n"; Unreachable(); } template T DefaultEqBB(TNode node, TBitblaster* bb) { Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; Assert(node.getKind() == Kind::EQUAL); std::vector lhs, rhs; bb->bbTerm(node[0], lhs); bb->bbTerm(node[1], rhs); Assert(lhs.size() == rhs.size()); std::vector bits_eq; for (unsigned i = 0; i < lhs.size(); i++) { T bit_eq = mkIff(lhs[i], rhs[i]); bits_eq.push_back(bit_eq); } T bv_eq = mkAnd(node.getNodeManager(), bits_eq); return bv_eq; } template T AdderUltBB(TNode node, TBitblaster* bb) { Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_ULT); std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); Assert(a.size() == b.size()); // a < b <=> ~ (add(a, ~b, 1).carry_out) std::vector not_b; negateBits(b, not_b); T carry = mkTrue(node.getNodeManager()); for (unsigned i = 0 ; i < a.size(); ++i) { carry = mkOr( mkAnd(a[i], not_b[i]), mkAnd( mkXor(a[i], not_b[i]), carry)); } return mkNot(carry); } template T DefaultUltBB(TNode node, TBitblaster* bb) { Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_ULT); std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); Assert(a.size() == b.size()); // construct bitwise comparison T res = uLessThanBB(a, b, false); return res; } template T DefaultUleBB(TNode node, TBitblaster* bb){ Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_ULE); std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); Assert(a.size() == b.size()); // construct bitwise comparison T res = uLessThanBB(a, b, true); return res; } template T DefaultUgtBB(TNode node, TBitblaster* bb){ Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; // should be rewritten Unimplemented(); } template T DefaultUgeBB(TNode node, TBitblaster* bb){ Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; // should be rewritten Unimplemented(); } template T DefaultSltBB(TNode node, TBitblaster* bb){ Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); Assert(a.size() == b.size()); T res = sLessThanBB(a, b, false); return res; } template T DefaultSleBB(TNode node, TBitblaster* bb){ Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); Assert(a.size() == b.size()); T res = sLessThanBB(a, b, true); return res; } template T DefaultSgtBB(TNode node, TBitblaster* bb){ Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; // should be rewritten Unimplemented(); } template T DefaultSgeBB(TNode node, TBitblaster* bb){ Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; // should be rewritten Unimplemented(); } /// Term bitblasting strategies /** * Default Term Bitblasting strategies * * @param node the term to be bitblasted * @param bits [output parameter] bits representing the new term * @param bb the bitblaster in which the clauses are added */ template void UndefinedTermBBStrategy(TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector") << "theory::bv:: Undefined bitblasting strategy for kind: " << node.getKind() << "\n"; Unreachable(); } template void DefaultVarBB (TNode node, std::vector& bits, TBitblaster* bb) { Assert(bits.size() == 0); bb->makeVariable(node, bits); if(TraceIsOn("bitvector-bb")) { Trace("bitvector-bb") << "theory::bv::DefaultVarBB bitblasting " << node << "\n"; Trace("bitvector-bb") << " with bits " << toString(bits); } } template void DefaultConstBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultConstBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::CONST_BITVECTOR); Assert(bits.size() == 0); NodeManager* nm = node.getNodeManager(); for (unsigned i = 0; i < utils::getSize(node); ++i) { Integer bit = node.getConst().extract(i, i).getValue(); if(bit == Integer(0)){ bits.push_back(mkFalse(nm)); } else { Assert(bit == Integer(1)); bits.push_back(mkTrue(nm)); } } if(TraceIsOn("bitvector-bb")) { Trace("bitvector-bb") << "with bits: " << toString(bits) << "\n"; } } template void DefaultNotBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultNotBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_NOT); Assert(bits.size() == 0); std::vector bv; bb->bbTerm(node[0], bv); negateBits(bv, bits); } template void DefaultConcatBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultConcatBB bitblasting " << node << "\n"; Assert(bits.size() == 0); Assert(node.getKind() == Kind::BITVECTOR_CONCAT); for (int i = node.getNumChildren() -1 ; i >= 0; --i ) { TNode current = node[i]; std::vector current_bits; bb->bbTerm(current, current_bits); for(unsigned j = 0; j < utils::getSize(current); ++j) { bits.push_back(current_bits[j]); } } Assert(bits.size() == utils::getSize(node)); if(TraceIsOn("bitvector-bb")) { Trace("bitvector-bb") << "with bits: " << toString(bits) << "\n"; } } template void DefaultAndBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultAndBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_AND && bits.size() == 0); bb->bbTerm(node[0], bits); std::vector current; for(unsigned j = 1; j < node.getNumChildren(); ++j) { bb->bbTerm(node[j], current); for (unsigned i = 0; i < utils::getSize(node); ++i) { bits[i] = mkAnd(bits[i], current[i]); } current.clear(); } Assert(bits.size() == utils::getSize(node)); } template void DefaultOrBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultOrBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_OR && bits.size() == 0); bb->bbTerm(node[0], bits); std::vector current; for(unsigned j = 1; j < node.getNumChildren(); ++j) { bb->bbTerm(node[j], current); for (unsigned i = 0; i < utils::getSize(node); ++i) { bits[i] = mkOr(bits[i], current[i]); } current.clear(); } Assert(bits.size() == utils::getSize(node)); } template void DefaultXorBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultXorBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_XOR && bits.size() == 0); bb->bbTerm(node[0], bits); std::vector current; for(unsigned j = 1; j < node.getNumChildren(); ++j) { bb->bbTerm(node[j], current); for (unsigned i = 0; i < utils::getSize(node); ++i) { bits[i] = mkXor(bits[i], current[i]); } current.clear(); } Assert(bits.size() == utils::getSize(node)); } template void DefaultXnorBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultXnorBB bitblasting " << node << "\n"; Assert(node.getNumChildren() == 2 && node.getKind() == Kind::BITVECTOR_XNOR && bits.size() == 0); std::vector lhs, rhs; bb->bbTerm(node[0], lhs); bb->bbTerm(node[1], rhs); Assert(lhs.size() == rhs.size()); for (unsigned i = 0; i < lhs.size(); ++i) { bits.push_back(mkIff(lhs[i], rhs[i])); } } template void DefaultNandBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector") << "theory::bv:: Unimplemented kind " << node.getKind() << "\n"; Unimplemented(); } template void DefaultNorBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector") << "theory::bv:: Unimplemented kind " << node.getKind() << "\n"; Unimplemented(); } template void DefaultCompBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector") << "theory::bv:: DefaultCompBB bitblasting "<< node << "\n"; Assert(utils::getSize(node) == 1 && bits.size() == 0 && node.getKind() == Kind::BITVECTOR_COMP); std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); std::vector bit_eqs; for (unsigned i = 0; i < a.size(); ++i) { T eq = mkIff(a[i], b[i]); bit_eqs.push_back(eq); } T a_eq_b = mkAnd(node.getNodeManager(), bit_eqs); bits.push_back(a_eq_b); } template void DefaultMultBB (TNode node, std::vector& res, TBitblaster* bb) { Trace("bitvector") << "theory::bv:: DefaultMultBB bitblasting "<< node << "\n"; Assert(res.size() == 0 && node.getKind() == Kind::BITVECTOR_MULT); // if (node.getNumChildren() == 2) { // std::vector a; // std::vector b; // bb->bbTerm(node[0], a); // bb->bbTerm(node[1], b); // unsigned bw = utils::getSize(node); // unsigned thresh = bw % 2 ? bw/2 : bw/2 - 1; // bool no_overflow = true; // for (unsigned i = thresh; i < bw; ++i) { // if (a[i] != mkFalse || b[i] != mkFalse ) { // no_overflow = false; // } // } // if (no_overflow) { // shiftAddMultiplier(); // return; // } // } std::vector newres; bb->bbTerm(node[0], res); NodeManager* nm = node.getNodeManager(); for(unsigned i = 1; i < node.getNumChildren(); ++i) { std::vector current; bb->bbTerm(node[i], current); newres.clear(); // constructs a simple shift and add multiplier building the result // in res shiftAddMultiplier(nm, res, current, newres); res = newres; } if(TraceIsOn("bitvector-bb")) { Trace("bitvector-bb") << "with bits: " << toString(res) << "\n"; } } template void DefaultAddBB(TNode node, std::vector& res, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultAddBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_ADD && res.size() == 0); bb->bbTerm(node[0], res); std::vector newres; NodeManager* nm = node.getNodeManager(); for(unsigned i = 1; i < node.getNumChildren(); ++i) { std::vector current; bb->bbTerm(node[i], current); newres.clear(); rippleCarryAdder(res, current, newres, mkFalse(nm)); res = newres; } Assert(res.size() == utils::getSize(node)); } template void DefaultSubBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultSubBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_SUB && node.getNumChildren() == 2 && bits.size() == 0); std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); Assert(a.size() == b.size() && utils::getSize(node) == a.size()); // bvsub a b = adder(a, ~b, 1) std::vector not_b; negateBits(b, not_b); rippleCarryAdder(a, not_b, bits, mkTrue(node.getNodeManager())); } template void DefaultNegBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultNegBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_NEG); std::vector a; bb->bbTerm(node[0], a); Assert(utils::getSize(node) == a.size()); NodeManager* nm = node.getNodeManager(); // -a = add(~a, 0, 1). std::vector not_a; negateBits(a, not_a); std::vector zero; makeZero(nm, zero, utils::getSize(node)); rippleCarryAdder(not_a, zero, bits, mkTrue(nm)); } template void uDivModRec(NodeManager* nm, const std::vector& a, const std::vector& b, std::vector& q, std::vector& r, unsigned rec_width) { Assert(q.size() == 0 && r.size() == 0); if (rec_width == 0 || isZero(nm, a)) { makeZero(nm, q, a.size()); makeZero(nm, r, a.size()); return; } std::vector q1, r1; std::vector a1 = a; rshift(nm, a1, 1); uDivModRec(nm, a1, b, q1, r1, rec_width - 1); // shift the quotient and remainder (i.e. multiply by two) and add 1 to remainder if a is odd lshift(nm, q1, 1); lshift(nm, r1, 1); T is_odd = mkIff(a[0], mkTrue(nm)); T one_if_odd = mkIte(is_odd, mkTrue(nm), mkFalse(nm)); std::vector zero; makeZero(nm, zero, b.size()); std::vector r1_shift_add; // account for a being odd rippleCarryAdder(r1, zero, r1_shift_add, one_if_odd); // now check if the remainder is greater than b std::vector not_b; negateBits(b, not_b); std::vector r_minus_b; T co1; // use adder because we need r_minus_b anyway co1 = rippleCarryAdder(r1_shift_add, not_b, r_minus_b, mkTrue(nm)); // sign is true if r1 < b T sign = mkNot(co1); q1[0] = mkIte(sign, q1[0], mkTrue(nm)); // would be nice to have a high level ITE instead of bitwise for(unsigned i = 0; i < a.size(); ++i) { r1_shift_add[i] = mkIte(sign, r1_shift_add[i], r_minus_b[i]); } // check if a < b std::vector a_minus_b; T co2 = rippleCarryAdder(a, not_b, a_minus_b, mkTrue(nm)); // Node a_lt_b = a_minus_b.back(); T a_lt_b = mkNot(co2); for(unsigned i = 0; i < a.size(); ++i) { T qval = mkIte(a_lt_b, mkFalse(nm), q1[i]); T rval = mkIte(a_lt_b, a[i], r1_shift_add[i]); q.push_back(qval); r.push_back(rval); } } template void UdivUremBB(TNode node, std::vector& quot, std::vector& rem, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultUdivBB bitblasting " << node << "\n"; Assert(quot.empty()); Assert(rem.empty()); Assert(node.getKind() == Kind::BITVECTOR_UDIV || node.getKind() == Kind::BITVECTOR_UREM); std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); NodeManager* nm = node.getNodeManager(); uDivModRec(nm, a, b, quot, rem, utils::getSize(node)); // adding a special case for division by 0 std::vector iszero; for (size_t i = 0, size = b.size(); i < size; ++i) { iszero.push_back(mkIff(b[i], mkFalse(nm))); } T b_is_0 = mkAnd(nm, iszero); for (size_t i = 0, size = quot.size(); i < size; ++i) { quot[i] = mkIte(b_is_0, mkTrue(nm), quot[i]); // a udiv 0 is 11..11 rem[i] = mkIte(b_is_0, a[i], rem[i]); // a urem 0 is a } } template void DefaultUdivBB(TNode node, std::vector& quot, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultUdivBB bitblasting " << node << "\n"; Assert(quot.empty()); Assert(node.getKind() == Kind::BITVECTOR_UDIV); std::vector r; UdivUremBB(node, quot, r, bb); } template void DefaultUremBB(TNode node, std::vector& rem, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultUremBB bitblasting " << node << "\n"; Assert(rem.empty()); Assert(node.getKind() == Kind::BITVECTOR_UREM); std::vector q; UdivUremBB(node, q, rem, bb); } template void DefaultSdivBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector") << "theory::bv:: Unimplemented kind " << node.getKind() << "\n"; Unimplemented(); } template void DefaultSremBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector") << "theory::bv:: Unimplemented kind " << node.getKind() << "\n"; Unimplemented(); } template void DefaultSmodBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector") << "theory::bv:: Unimplemented kind " << node.getKind() << "\n"; Unimplemented(); } template void DefaultShlBB(TNode node, std::vector& res, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultShlBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_SHL && res.size() == 0); std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); NodeManager* nm = node.getNodeManager(); // check for b < log2(n) unsigned size = utils::getSize(node); unsigned log2_size = std::ceil(log2((double)size)); Node a_size = utils::mkConst(nm, size, size); std::vector a_size_bits; DefaultConstBB(a_size, a_size_bits, bb); T b_ult_a_size = uLessThanBB(b, a_size_bits, false); std::vector prev_res; res = a; // we only need to look at the bits bellow log2_a_size for (unsigned s = 0; s < log2_size; ++s) { // barrel shift stage: at each stage you can either shift by 2^s bits // or leave the previous stage untouched prev_res = res; unsigned threshold = pow(2, s); for (unsigned i = 0; i < a.size(); ++i) { if (i < threshold) { // if b[s] is true then we must have shifted by at least 2^b bits so // all bits bellow 2^s will be 0, otherwise just use previous shift // value res[i] = mkIte(b[s], mkFalse(nm), prev_res[i]); } else { // if b[s]= 0, use previous value, otherwise shift by threshold bits Assert(i >= threshold); res[i] = mkIte(b[s], prev_res[i - threshold], prev_res[i]); } } } prev_res = res; for (unsigned i = 0; i < b.size(); ++i) { // this is fine because b_ult_a_size has been bit-blasted res[i] = mkIte(b_ult_a_size, prev_res[i], mkFalse(nm)); } if (TraceIsOn("bitvector-bb")) { Trace("bitvector-bb") << "with bits: " << toString(res) << "\n"; } } template void DefaultLshrBB(TNode node, std::vector& res, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultLshrBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_LSHR && res.size() == 0); std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); NodeManager* nm = node.getNodeManager(); // check for b < log2(n) unsigned size = utils::getSize(node); unsigned log2_size = std::ceil(log2((double)size)); Node a_size = utils::mkConst(nm, size, size); std::vector a_size_bits; DefaultConstBB(a_size, a_size_bits, bb); T b_ult_a_size = uLessThanBB(b, a_size_bits, false); res = a; std::vector prev_res; for (unsigned s = 0; s < log2_size; ++s) { // barrel shift stage: at each stage you can either shift by 2^s bits // or leave the previous stage untouched prev_res = res; int threshold = pow(2, s); for (unsigned i = 0; i < a.size(); ++i) { if (i + threshold >= a.size()) { // if b[s] is true then we must have shifted by at least 2^b bits so // all bits above 2^s will be 0, otherwise just use previous shift value res[i] = mkIte(b[s], mkFalse(nm), prev_res[i]); } else { // if b[s]= 0, use previous value, otherwise shift by threshold bits Assert(i + threshold < a.size()); res[i] = mkIte(mkNot(b[s]), prev_res[i], prev_res[i + threshold]); } } } prev_res = res; for (unsigned i = 0; i < b.size(); ++i) { // this is fine because b_ult_a_size has been bit-blasted res[i] = mkIte(b_ult_a_size, prev_res[i], mkFalse(nm)); } if (TraceIsOn("bitvector-bb")) { Trace("bitvector-bb") << "with bits: " << toString(res) << "\n"; } } template void DefaultAshrBB(TNode node, std::vector& res, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultAshrBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_ASHR && res.size() == 0); std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); NodeManager* nm = node.getNodeManager(); // check for b < n unsigned size = utils::getSize(node); unsigned log2_size = std::ceil(log2((double)size)); Node a_size = utils::mkConst(nm, size, size); std::vector a_size_bits; DefaultConstBB(a_size, a_size_bits, bb); T b_ult_a_size = uLessThanBB(b, a_size_bits, false); res = a; T sign_bit = a.back(); std::vector prev_res; for (unsigned s = 0; s < log2_size; ++s) { // barrel shift stage: at each stage you can either shift by 2^s bits // or leave the previous stage untouched prev_res = res; int threshold = pow(2, s); for (unsigned i = 0; i < a.size(); ++i) { if (i + threshold >= a.size()) { // if b[s] is true then we must have shifted by at least 2^b bits so // all bits above 2^s will be the sign bit, otherwise just use previous // shift value res[i] = mkIte(b[s], sign_bit, prev_res[i]); } else { // if b[s]= 0, use previous value, otherwise shift by threshold bits Assert(i + threshold < a.size()); res[i] = mkIte(mkNot(b[s]), prev_res[i], prev_res[i + threshold]); } } } prev_res = res; for (unsigned i = 0; i < b.size(); ++i) { // this is fine because b_ult_a_size has been bit-blasted res[i] = mkIte(b_ult_a_size, prev_res[i], sign_bit); } if (TraceIsOn("bitvector-bb")) { Trace("bitvector-bb") << "with bits: " << toString(res) << "\n"; } } template void DefaultUltbvBB (TNode node, std::vector& res, TBitblaster* bb) { Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_ULTBV); std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); Assert(a.size() == b.size()); // construct bitwise comparison res.push_back(uLessThanBB(a, b, false)); } template void DefaultSltbvBB (TNode node, std::vector& res, TBitblaster* bb) { Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_SLTBV); std::vector a, b; bb->bbTerm(node[0], a); bb->bbTerm(node[1], b); Assert(a.size() == b.size()); // construct bitwise comparison res.push_back(sLessThanBB(a, b, false)); } template void DefaultIteBB (TNode node, std::vector& res, TBitblaster* bb) { Trace("bitvector-bb") << "Bitblasting node " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_ITE); std::vector cond, thenpart, elsepart; bb->bbTerm(node[0], cond); bb->bbTerm(node[1], thenpart); bb->bbTerm(node[2], elsepart); Assert(cond.size() == 1); Assert(thenpart.size() == elsepart.size()); for (unsigned i = 0; i < thenpart.size(); ++i) { // (~cond OR thenpart) AND (cond OR elsepart) res.push_back(mkAnd(mkOr(mkNot(cond[0]),thenpart[i]),mkOr(cond[0],elsepart[i]))); } } template void DefaultExtractBB (TNode node, std::vector& bits, TBitblaster* bb) { Assert(node.getKind() == Kind::BITVECTOR_EXTRACT); Assert(bits.size() == 0); std::vector base_bits; bb->bbTerm(node[0], base_bits); unsigned high = utils::getExtractHigh(node); unsigned low = utils::getExtractLow(node); for (unsigned i = low; i <= high; ++i) { bits.push_back(base_bits[i]); } Assert(bits.size() == high - low + 1); if(TraceIsOn("bitvector-bb")) { Trace("bitvector-bb") << "theory::bv::DefaultExtractBB bitblasting " << node << "\n"; Trace("bitvector-bb") << " with bits " << toString(bits); } } template void DefaultRepeatBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector") << "theory::bv:: Unimplemented kind " << node.getKind() << "\n"; // this should be rewritten Unimplemented(); } template void DefaultZeroExtendBB (TNode node, std::vector& res_bits, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultZeroExtendBB bitblasting " << node << "\n"; // this should be rewritten Unimplemented(); } template void DefaultSignExtendBB (TNode node, std::vector& res_bits, TBitblaster* bb) { Trace("bitvector-bb") << "theory::bv::DefaultSignExtendBB bitblasting " << node << "\n"; Assert(node.getKind() == Kind::BITVECTOR_SIGN_EXTEND && res_bits.size() == 0); std::vector bits; bb->bbTerm(node[0], bits); T sign_bit = bits.back(); unsigned amount = node.getOperator().getConst().d_signExtendAmount; for (unsigned i = 0; i < bits.size(); ++i ) { res_bits.push_back(bits[i]); } for (unsigned i = 0 ; i < amount ; ++i ) { res_bits.push_back(sign_bit); } Assert(res_bits.size() == amount + bits.size()); } template void DefaultRotateRightBB (TNode node, std::vector& res, TBitblaster* bb) { Trace("bitvector") << "theory::bv:: Unimplemented kind " << node.getKind() << "\n"; Unimplemented(); } template void DefaultRotateLeftBB (TNode node, std::vector& bits, TBitblaster* bb) { Trace("bitvector") << "theory::bv:: Unimplemented kind " << node.getKind() << "\n"; Unimplemented(); } } } } // namespace cvc5::internal #endif