Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/bv/bitblast/eager_bitblaster.cpp	Lines:	69	132	52.3 %
Date:	2021-09-10	Branches:	93	553	16.8 %


/******************************************************************************
 * Top contributors (to current version):
 *   Liana Hadarean, Mathias Preiner, Andres Noetzli
 *
 * This file is part of the cvc5 project.
 *
 * Copyright (c) 2009-2021 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.
 * ****************************************************************************
 *
 * Bitblaster for the eager bv solver.
 */

#include "theory/bv/bitblast/eager_bitblaster.h"

#include "cvc5_private.h"
#include "options/base_options.h"
#include "options/bv_options.h"
#include "options/smt_options.h"
#include "prop/cnf_stream.h"
#include "prop/sat_solver_factory.h"
#include "smt/smt_engine.h"
#include "smt/smt_statistics_registry.h"
#include "theory/bv/bv_solver_layered.h"
#include "theory/bv/theory_bv.h"
#include "theory/theory_model.h"

namespace cvc5 {
namespace theory {
namespace bv {

EagerBitblaster::EagerBitblaster(BVSolverLayered* theory_bv,
                                 context::Context* c)
    : TBitblaster<Node>(),
      d_context(c),
      d_satSolver(),
      d_bitblastingRegistrar(new BitblastingRegistrar(this)),
      d_bv(theory_bv),
      d_bbAtoms(),
      d_variables(),
      d_notify()
{
  prop::SatSolver *solver = nullptr;
  switch (options::bvSatSolver())
  {
    case options::SatSolverMode::MINISAT:
    {
      prop::BVSatSolverInterface* minisat =
          prop::SatSolverFactory::createMinisat(
              d_nullContext.get(),
              smtStatisticsRegistry(),
              "theory::bv::EagerBitblaster::");
      d_notify.reset(new MinisatEmptyNotify());
      minisat->setNotify(d_notify.get());
      solver = minisat;
      break;
    }
    case options::SatSolverMode::CADICAL:
      solver = prop::SatSolverFactory::createCadical(
          smtStatisticsRegistry(), "theory::bv::EagerBitblaster::");
      break;
    case options::SatSolverMode::CRYPTOMINISAT:
      solver = prop::SatSolverFactory::createCryptoMinisat(
          smtStatisticsRegistry(), "theory::bv::EagerBitblaster::");
      break;
    case options::SatSolverMode::KISSAT:
      solver = prop::SatSolverFactory::createKissat(
          smtStatisticsRegistry(), "theory::bv::EagerBitblaster::");
      break;
    default: Unreachable() << "Unknown SAT solver type";
  }
  d_satSolver.reset(solver);
  ResourceManager* rm = smt::currentResourceManager();
  d_cnfStream.reset(new prop::CnfStream(d_satSolver.get(),
                                        d_bitblastingRegistrar.get(),
                                        d_nullContext.get(),
                                        nullptr,
                                        rm,
                                        prop::FormulaLitPolicy::INTERNAL,
                                        "EagerBitblaster"));
}

EagerBitblaster::~EagerBitblaster() {}

void EagerBitblaster::bbFormula(TNode node)
{
  /* For incremental eager solving we assume formulas at context levels > 1. */
  if (options::incrementalSolving() && d_context->getLevel() > 1)
  {
    d_cnfStream->ensureLiteral(node);
  }
  else
  {
    d_cnfStream->convertAndAssert(node, false, false);
  }
}

/**
 * Bitblasts the atom, assigns it a marker literal, adding it to the SAT solver
 * NOTE: duplicate clauses are not detected because of marker literal
 * @param node the atom to be bitblasted
 *
 */
void EagerBitblaster::bbAtom(TNode node)
{
  node = node.getKind() == kind::NOT ? node[0] : node;
  if (node.getKind() == kind::BITVECTOR_BITOF
      || node.getKind() == kind::CONST_BOOLEAN || hasBBAtom(node))
  {
    return;
  }

  Debug("bitvector-bitblast") << "Bitblasting node " << node << "\n";

  // the bitblasted definition of the atom
  Node normalized = Rewriter::rewrite(node);
  Node atom_bb =
      normalized.getKind() != kind::CONST_BOOLEAN
          ? d_atomBBStrategies[normalized.getKind()](normalized, this)
          : normalized;

  atom_bb = Rewriter::rewrite(atom_bb);

  // asserting that the atom is true iff the definition holds
  Node atom_definition =
      NodeManager::currentNM()->mkNode(kind::EQUAL, node, atom_bb);

  AlwaysAssert(options::bitblastMode() == options::BitblastMode::EAGER);
  storeBBAtom(node, atom_bb);
  d_cnfStream->convertAndAssert(atom_definition, false, false);
}

void EagerBitblaster::storeBBAtom(TNode atom, Node atom_bb) {
  d_bbAtoms.insert(atom);
}

void EagerBitblaster::storeBBTerm(TNode node, const Bits& bits) {
  d_termCache.insert(std::make_pair(node, bits));
}

bool EagerBitblaster::hasBBAtom(TNode atom) const {
  return d_bbAtoms.find(atom) != d_bbAtoms.end();
}

void EagerBitblaster::bbTerm(TNode node, Bits& bits) {
  Assert(node.getType().isBitVector());

  if (hasBBTerm(node)) {
    getBBTerm(node, bits);
    return;
  }

  d_bv->spendResource(Resource::BitblastStep);
  Debug("bitvector-bitblast") << "Bitblasting node " << node << "\n";

  d_termBBStrategies[node.getKind()](node, bits, this);

  Assert(bits.size() == utils::getSize(node));

  storeBBTerm(node, bits);
}

void EagerBitblaster::makeVariable(TNode var, Bits& bits) {
  Assert(bits.size() == 0);
  for (unsigned i = 0; i < utils::getSize(var); ++i) {
    bits.push_back(utils::mkBitOf(var, i));
  }
  d_variables.insert(var);
}

Node EagerBitblaster::getBBAtom(TNode node) const { return node; }

/**
 * Calls the solve method for the Sat Solver.
 *
 * @return true for sat, and false for unsat
 */

bool EagerBitblaster::solve() {
  if (Trace.isOn("bitvector")) {
    Trace("bitvector") << "EagerBitblaster::solve(). \n";
  }
  Debug("bitvector") << "EagerBitblaster::solve(). \n";
  // TODO: clear some memory
  // if (something) {
  //   NodeManager* nm= NodeManager::currentNM();
  //   Rewriter::garbageCollect();
  //   nm->reclaimZombiesUntil(options::zombieHuntThreshold());
  // }
  return prop::SAT_VALUE_TRUE == d_satSolver->solve();
}

bool EagerBitblaster::solve(const std::vector<Node>& assumptions)
{
  std::vector<prop::SatLiteral> assumpts;
  for (const Node& assumption : assumptions)
  {
    Assert(d_cnfStream->hasLiteral(assumption));
    assumpts.push_back(d_cnfStream->getLiteral(assumption));
  }
  return prop::SAT_VALUE_TRUE == d_satSolver->solve(assumpts);
}

/**
 * Returns the value a is currently assigned to in the SAT solver
 * or null if the value is completely unassigned.
 *
 * @param a
 * @param fullModel whether to create a "full model," i.e., add
 * constants to equivalence classes that don't already have them
 *
 * @return
 */
Node EagerBitblaster::getModelFromSatSolver(TNode a, bool fullModel) {
  if (!hasBBTerm(a)) {
    return fullModel ? utils::mkConst(utils::getSize(a), 0u) : Node();
  }

  Bits bits;
  getBBTerm(a, bits);
  Integer value(0);
  for (int i = bits.size() - 1; i >= 0; --i) {
    prop::SatValue bit_value;
    if (d_cnfStream->hasLiteral(bits[i])) {
      prop::SatLiteral bit = d_cnfStream->getLiteral(bits[i]);
      bit_value = d_satSolver->value(bit);
      Assert(bit_value != prop::SAT_VALUE_UNKNOWN);
    } else {
      if (!fullModel) return Node();
      // unconstrained bits default to false
      bit_value = prop::SAT_VALUE_FALSE;
    }
    Integer bit_int =
        bit_value == prop::SAT_VALUE_TRUE ? Integer(1) : Integer(0);
    value = value * 2 + bit_int;
  }
  return utils::mkConst(bits.size(), value);
}

bool EagerBitblaster::collectModelInfo(TheoryModel* m, bool fullModel)
{
  NodeManager* nm = NodeManager::currentNM();

  // Collect the values for the bit-vector variables
  TNodeSet::iterator it = d_variables.begin();
  for (; it != d_variables.end(); ++it) {
    TNode var = *it;
    if (d_bv->isLeaf(var) || isSharedTerm(var) ||
        (var.isVar() && var.getType().isBoolean())) {
      // only shared terms could not have been bit-blasted
      Assert(hasBBTerm(var) || isSharedTerm(var));

      Node const_value = getModelFromSatSolver(var, true);

      if (const_value != Node()) {
        Debug("bitvector-model")
            << "EagerBitblaster::collectModelInfo (assert (= " << var << " "
            << const_value << "))\n";
        if (!m->assertEquality(var, const_value, true))
        {
          return false;
        }
      }
    }
  }

  // Collect the values for the Boolean variables
  std::vector<TNode> vars;
  d_cnfStream->getBooleanVariables(vars);
  for (TNode var : vars)
  {
    Assert(d_cnfStream->hasLiteral(var));
    prop::SatLiteral bit = d_cnfStream->getLiteral(var);
    prop::SatValue value = d_satSolver->value(bit);
    Assert(value != prop::SAT_VALUE_UNKNOWN);
    if (!m->assertEquality(
            var, nm->mkConst(value == prop::SAT_VALUE_TRUE), true))
    {
      return false;
    }
  }
  return true;
}

bool EagerBitblaster::isSharedTerm(TNode node) {
  return d_bv->d_sharedTermsSet.find(node) != d_bv->d_sharedTermsSet.end();
}


}  // namespace bv
}  // namespace theory
}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Liana Hadarean, Mathias Preiner, Andres Noetzli
4		*
5		* This file is part of the cvc5 project.
6		*
7		* Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
8		* in the top-level source directory and their institutional affiliations.
9		* All rights reserved. See the file COPYING in the top-level source
10		* directory for licensing information.
11		* ****************************************************************************
12		*
13		* Bitblaster for the eager bv solver.
14		*/
15
16		#include "theory/bv/bitblast/eager_bitblaster.h"
17
18		#include "cvc5_private.h"
19		#include "options/base_options.h"
20		#include "options/bv_options.h"
21		#include "options/smt_options.h"
22		#include "prop/cnf_stream.h"
23		#include "prop/sat_solver_factory.h"
24		#include "smt/smt_engine.h"
25		#include "smt/smt_statistics_registry.h"
26		#include "theory/bv/bv_solver_layered.h"
27		#include "theory/bv/theory_bv.h"
28		#include "theory/theory_model.h"
29
30		namespace cvc5 {
31		namespace theory {
32		namespace bv {
33
34	2	EagerBitblaster::EagerBitblaster(BVSolverLayered* theory_bv,
35	2	context::Context* c)
36		: TBitblaster<Node>(),
37		d_context(c),
38		d_satSolver(),
39	2	d_bitblastingRegistrar(new BitblastingRegistrar(this)),
40		d_bv(theory_bv),
41		d_bbAtoms(),
42		d_variables(),
43	4	d_notify()
44		{
45	2	prop::SatSolver *solver = nullptr;
46	2	switch (options::bvSatSolver())
47		{
48	2	case options::SatSolverMode::MINISAT:
49		{
50		prop::BVSatSolverInterface* minisat =
51	4	prop::SatSolverFactory::createMinisat(
52		d_nullContext.get(),
53		smtStatisticsRegistry(),
54	2	"theory::bv::EagerBitblaster::");
55	2	d_notify.reset(new MinisatEmptyNotify());
56	2	minisat->setNotify(d_notify.get());
57	2	solver = minisat;
58	2	break;
59		}
60		case options::SatSolverMode::CADICAL:
61		solver = prop::SatSolverFactory::createCadical(
62		smtStatisticsRegistry(), "theory::bv::EagerBitblaster::");
63		break;
64		case options::SatSolverMode::CRYPTOMINISAT:
65		solver = prop::SatSolverFactory::createCryptoMinisat(
66		smtStatisticsRegistry(), "theory::bv::EagerBitblaster::");
67		break;
68		case options::SatSolverMode::KISSAT:
69		solver = prop::SatSolverFactory::createKissat(
70		smtStatisticsRegistry(), "theory::bv::EagerBitblaster::");
71		break;
72		default: Unreachable() << "Unknown SAT solver type";
73		}
74	2	d_satSolver.reset(solver);
75	2	ResourceManager* rm = smt::currentResourceManager();
76	6	d_cnfStream.reset(new prop::CnfStream(d_satSolver.get(),
77	2	d_bitblastingRegistrar.get(),
78	2	d_nullContext.get(),
79		nullptr,
80		rm,
81		prop::FormulaLitPolicy::INTERNAL,
82	2	"EagerBitblaster"));
83	2	}
84
85	4	EagerBitblaster::~EagerBitblaster() {}
86
87	4	void EagerBitblaster::bbFormula(TNode node)
88		{
89		/* For incremental eager solving we assume formulas at context levels > 1. */
90	4	if (options::incrementalSolving() && d_context->getLevel() > 1)
91		{
92		d_cnfStream->ensureLiteral(node);
93		}
94		else
95		{
96	4	d_cnfStream->convertAndAssert(node, false, false);
97		}
98	4	}
99
100		/**
101		* Bitblasts the atom, assigns it a marker literal, adding it to the SAT solver
102		* NOTE: duplicate clauses are not detected because of marker literal
103		* @param node the atom to be bitblasted
104		*
105		*/
106	68	void EagerBitblaster::bbAtom(TNode node)
107		{
108	68	node = node.getKind() == kind::NOT ? node[0] : node;
109	136	if (node.getKind() == kind::BITVECTOR_BITOF
110	136	\|\| node.getKind() == kind::CONST_BOOLEAN \|\| hasBBAtom(node))
111		{
112	64	return;
113		}
114
115	4	Debug("bitvector-bitblast") << "Bitblasting node " << node << "\n";
116
117		// the bitblasted definition of the atom
118	8	Node normalized = Rewriter::rewrite(node);
119		Node atom_bb =
120	4	normalized.getKind() != kind::CONST_BOOLEAN
121	4	? d_atomBBStrategies[normalized.getKind()](normalized, this)
122	12	: normalized;
123
124	4	atom_bb = Rewriter::rewrite(atom_bb);
125
126		// asserting that the atom is true iff the definition holds
127		Node atom_definition =
128	8	NodeManager::currentNM()->mkNode(kind::EQUAL, node, atom_bb);
129
130	4	AlwaysAssert(options::bitblastMode() == options::BitblastMode::EAGER);
131	4	storeBBAtom(node, atom_bb);
132	4	d_cnfStream->convertAndAssert(atom_definition, false, false);
133		}
134
135	4	void EagerBitblaster::storeBBAtom(TNode atom, Node atom_bb) {
136	4	d_bbAtoms.insert(atom);
137	4	}
138
139	12	void EagerBitblaster::storeBBTerm(TNode node, const Bits& bits) {
140	12	d_termCache.insert(std::make_pair(node, bits));
141	12	}
142
143	4	bool EagerBitblaster::hasBBAtom(TNode atom) const {
144	4	return d_bbAtoms.find(atom) != d_bbAtoms.end();
145		}
146
147	18	void EagerBitblaster::bbTerm(TNode node, Bits& bits) {
148	18	Assert(node.getType().isBitVector());
149
150	18	if (hasBBTerm(node)) {
151	6	getBBTerm(node, bits);
152	6	return;
153		}
154
155	12	d_bv->spendResource(Resource::BitblastStep);
156	12	Debug("bitvector-bitblast") << "Bitblasting node " << node << "\n";
157
158	12	d_termBBStrategies[node.getKind()](node, bits, this);
159
160	12	Assert(bits.size() == utils::getSize(node));
161
162	12	storeBBTerm(node, bits);
163		}
164
165	4	void EagerBitblaster::makeVariable(TNode var, Bits& bits) {
166	4	Assert(bits.size() == 0);
167	68	for (unsigned i = 0; i < utils::getSize(var); ++i) {
168	64	bits.push_back(utils::mkBitOf(var, i));
169		}
170	4	d_variables.insert(var);
171	4	}
172
173		Node EagerBitblaster::getBBAtom(TNode node) const { return node; }
174
175		/**
176		* Calls the solve method for the Sat Solver.
177		*
178		* @return true for sat, and false for unsat
179		*/
180
181	2	bool EagerBitblaster::solve() {
182	2	if (Trace.isOn("bitvector")) {
183		Trace("bitvector") << "EagerBitblaster::solve(). \n";
184		}
185	2	Debug("bitvector") << "EagerBitblaster::solve(). \n";
186		// TODO: clear some memory
187		// if (something) {
188		// NodeManager* nm= NodeManager::currentNM();
189		// Rewriter::garbageCollect();
190		// nm->reclaimZombiesUntil(options::zombieHuntThreshold());
191		// }
192	2	return prop::SAT_VALUE_TRUE == d_satSolver->solve();
193		}
194
195		bool EagerBitblaster::solve(const std::vector<Node>& assumptions)
196		{
197		std::vector<prop::SatLiteral> assumpts;
198		for (const Node& assumption : assumptions)
199		{
200		Assert(d_cnfStream->hasLiteral(assumption));
201		assumpts.push_back(d_cnfStream->getLiteral(assumption));
202		}
203		return prop::SAT_VALUE_TRUE == d_satSolver->solve(assumpts);
204		}
205
206		/**
207		* Returns the value a is currently assigned to in the SAT solver
208		* or null if the value is completely unassigned.
209		*
210		* @param a
211		* @param fullModel whether to create a "full model," i.e., add
212		* constants to equivalence classes that don't already have them
213		*
214		* @return
215		*/
216		Node EagerBitblaster::getModelFromSatSolver(TNode a, bool fullModel) {
217		if (!hasBBTerm(a)) {
218		return fullModel ? utils::mkConst(utils::getSize(a), 0u) : Node();
219		}
220
221		Bits bits;
222		getBBTerm(a, bits);
223		Integer value(0);
224		for (int i = bits.size() - 1; i >= 0; --i) {
225		prop::SatValue bit_value;
226		if (d_cnfStream->hasLiteral(bits[i])) {
227		prop::SatLiteral bit = d_cnfStream->getLiteral(bits[i]);
228		bit_value = d_satSolver->value(bit);
229		Assert(bit_value != prop::SAT_VALUE_UNKNOWN);
230		} else {
231		if (!fullModel) return Node();
232		// unconstrained bits default to false
233		bit_value = prop::SAT_VALUE_FALSE;
234		}
235		Integer bit_int =
236		bit_value == prop::SAT_VALUE_TRUE ? Integer(1) : Integer(0);
237		value = value * 2 + bit_int;
238		}
239		return utils::mkConst(bits.size(), value);
240		}
241
242		bool EagerBitblaster::collectModelInfo(TheoryModel* m, bool fullModel)
243		{
244		NodeManager* nm = NodeManager::currentNM();
245
246		// Collect the values for the bit-vector variables
247		TNodeSet::iterator it = d_variables.begin();
248		for (; it != d_variables.end(); ++it) {
249		TNode var = *it;
250		if (d_bv->isLeaf(var) \|\| isSharedTerm(var) \|\|
251		(var.isVar() && var.getType().isBoolean())) {
252		// only shared terms could not have been bit-blasted
253		Assert(hasBBTerm(var) \|\| isSharedTerm(var));
254
255		Node const_value = getModelFromSatSolver(var, true);
256
257		if (const_value != Node()) {
258		Debug("bitvector-model")
259		<< "EagerBitblaster::collectModelInfo (assert (= " << var << " "
260		<< const_value << "))\n";
261		if (!m->assertEquality(var, const_value, true))
262		{
263		return false;
264		}
265		}
266		}
267		}
268
269		// Collect the values for the Boolean variables
270		std::vector<TNode> vars;
271		d_cnfStream->getBooleanVariables(vars);
272		for (TNode var : vars)
273		{
274		Assert(d_cnfStream->hasLiteral(var));
275		prop::SatLiteral bit = d_cnfStream->getLiteral(var);
276		prop::SatValue value = d_satSolver->value(bit);
277		Assert(value != prop::SAT_VALUE_UNKNOWN);
278		if (!m->assertEquality(
279		var, nm->mkConst(value == prop::SAT_VALUE_TRUE), true))
280		{
281		return false;
282		}
283		}
284		return true;
285		}
286
287		bool EagerBitblaster::isSharedTerm(TNode node) {
288		return d_bv->d_sharedTermsSet.find(node) != d_bv->d_sharedTermsSet.end();
289		}
290
291
292		} // namespace bv
293		} // namespace theory
294	29502	} // namespace cvc5