Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/preprocessing/passes/int_to_bv.cpp	Lines:	121	138	87.7 %
Date:	2021-08-15	Branches:	258	618	41.7 %


/******************************************************************************
 * Top contributors (to current version):
 *   Andres Noetzli, Yoni Zohar, Alex Ozdemir
 *
 * 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.
 * ****************************************************************************
 *
 * The IntToBV preprocessing pass.
 *
 * Converts integer operations into bitvector operations. The width of the
 * bitvectors is controlled through the `--solve-int-as-bv` command line
 * option.
 */

#include "preprocessing/passes/int_to_bv.h"

#include <string>
#include <unordered_map>
#include <vector>

#include "expr/node.h"
#include "expr/node_traversal.h"
#include "expr/skolem_manager.h"
#include "options/base_options.h"
#include "options/smt_options.h"
#include "preprocessing/assertion_pipeline.h"
#include "preprocessing/preprocessing_pass_context.h"
#include "theory/rewriter.h"
#include "theory/theory.h"
#include "util/bitvector.h"
#include "util/rational.h"

namespace cvc5 {
namespace preprocessing {
namespace passes {

using namespace std;
using namespace cvc5::theory;


namespace {

bool childrenTypesChanged(Node n, NodeMap& cache) {
  for (Node child : n) {
    TypeNode originalType = child.getType();
    TypeNode newType = cache[child].getType();
    if (! newType.isSubtypeOf(originalType)) {
      return true;
    }
  }
  return false;
}


Node intToBVMakeBinary(TNode n, NodeMap& cache)
{
  for (TNode current : NodeDfsIterable(n, VisitOrder::POSTORDER,
           [&cache](TNode nn) { return cache.count(nn) > 0; }))
  {
    Node result;
    NodeManager* nm = NodeManager::currentNM();
    if (current.getNumChildren() == 0)
    {
      result = current;
    }
    else if (current.getNumChildren() > 2
             && (current.getKind() == kind::PLUS
                 || current.getKind() == kind::MULT
                 || current.getKind() == kind::NONLINEAR_MULT))
    {
      Assert(cache.find(current[0]) != cache.end());
      result = cache[current[0]];
      for (unsigned i = 1; i < current.getNumChildren(); ++i)
      {
        Assert(cache.find(current[i]) != cache.end());
        Node child = current[i];
        Node childRes = cache[current[i]];
        result = nm->mkNode(current.getKind(), result, childRes);
      }
    }
    else
    {
      NodeBuilder builder(current.getKind());
      if (current.getMetaKind() == kind::metakind::PARAMETERIZED) {
        builder << current.getOperator();
      }

      for (unsigned i = 0; i < current.getNumChildren(); ++i)
      {
        Assert(cache.find(current[i]) != cache.end());
        builder << cache[current[i]];
      }
      result = builder;
    }
    cache[current] = result;
  }
  return cache[n];
}
}  // namespace

Node IntToBV::intToBV(TNode n, NodeMap& cache)
{
  int size = options::solveIntAsBV();
  AlwaysAssert(size > 0);
  AlwaysAssert(!options::incrementalSolving());

  NodeManager* nm = NodeManager::currentNM();
  SkolemManager* sm = nm->getSkolemManager();
  NodeMap binaryCache;
  Node n_binary = intToBVMakeBinary(n, binaryCache);

  for (TNode current : NodeDfsIterable(n_binary, VisitOrder::POSTORDER,
           [&cache](TNode nn) { return cache.count(nn) > 0; }))
  {
    if (current.getNumChildren() > 0)
    {
      // Not a leaf
      vector<Node> children;
      uint64_t max = 0;
      for (const Node& nc : current)
      {
        Assert(cache.find(nc) != cache.end());
        TNode childRes = cache[nc];
        TypeNode type = childRes.getType();
        if (type.isBitVector())
        {
          uint32_t bvsize = type.getBitVectorSize();
          if (bvsize > max)
          {
            max = bvsize;
          }
        }
        children.push_back(childRes);
      }

      kind::Kind_t newKind = current.getKind();
      if (max > 0)
      {
        switch (newKind)
        {
          case kind::PLUS:
            Assert(children.size() == 2);
            newKind = kind::BITVECTOR_ADD;
            max = max + 1;
            break;
          case kind::MULT:
          case kind::NONLINEAR_MULT:
            Assert(children.size() == 2);
            newKind = kind::BITVECTOR_MULT;
            max = max * 2;
            break;
          case kind::MINUS:
            Assert(children.size() == 2);
            newKind = kind::BITVECTOR_SUB;
            max = max + 1;
            break;
          case kind::UMINUS:
            Assert(children.size() == 1);
            newKind = kind::BITVECTOR_NEG;
            max = max + 1;
            break;
          case kind::LT: newKind = kind::BITVECTOR_SLT; break;
          case kind::LEQ: newKind = kind::BITVECTOR_SLE; break;
          case kind::GT: newKind = kind::BITVECTOR_SGT; break;
          case kind::GEQ: newKind = kind::BITVECTOR_SGE; break;
          case kind::EQUAL:
          case kind::ITE: break;
          default:
            if (childrenTypesChanged(current, cache)) {
              throw TypeCheckingExceptionPrivate(
                  current,
                  string("Cannot translate to BV: ") + current.toString());
            }
            break;
        }
        for (size_t i = 0, csize = children.size(); i < csize; ++i)
        {
          TypeNode type = children[i].getType();
          if (!type.isBitVector())
          {
            continue;
          }
          uint32_t bvsize = type.getBitVectorSize();
          if (bvsize < max)
          {
            // sign extend
            Node signExtendOp = nm->mkConst<BitVectorSignExtend>(
                BitVectorSignExtend(max - bvsize));
            children[i] = nm->mkNode(signExtendOp, children[i]);
          }
        }
      }
      NodeBuilder builder(newKind);
      if (current.getMetaKind() == kind::metakind::PARAMETERIZED) {
        builder << current.getOperator();
      }
      builder.append(children);
      // Mark the substitution and continue
      Node result = builder;

      result = Rewriter::rewrite(result);
      cache[current] = result;
    }
    else
    {
      // It's a leaf: could be a variable or a numeral
      Node result = current;
      if (current.isVar())
      {
        if (current.getType() == nm->integerType())
        {
          result = sm->mkDummySkolem("__intToBV_var",
                                     nm->mkBitVectorType(size),
                                     "Variable introduced in intToBV pass");
          Node bv2nat = nm->mkNode(kind::BITVECTOR_TO_NAT, result);
          d_preprocContext->addSubstitution(current, bv2nat);
        }
      }
      else if (current.isConst())
      {
        switch (current.getKind())
        {
          case kind::CONST_RATIONAL:
          {
            Rational constant = current.getConst<Rational>();
            if (constant.isIntegral()) {
              BitVector bv(size, constant.getNumerator());
              if (bv.toSignedInteger() != constant.getNumerator())
              {
                throw TypeCheckingExceptionPrivate(
                    current,
                    string("Not enough bits for constant in intToBV: ")
                        + current.toString());
              }
              result = nm->mkConst(bv);
            }
            break;
          }
          default: break;
        }
      }
      else
      {
        throw TypeCheckingExceptionPrivate(
            current, string("Cannot translate to BV: ") + current.toString());
      }
      cache[current] = result;
    }
  }
  Trace("int-to-bv-debug") << "original: " << n << std::endl;
  Trace("int-to-bv-debug") << "binary: " << n_binary << std::endl;
  Trace("int-to-bv-debug") << "result: " << cache[n_binary] << std::endl;
  return cache[n_binary];
}

IntToBV::IntToBV(PreprocessingPassContext* preprocContext)
    : PreprocessingPass(preprocContext, "int-to-bv"){};

PreprocessingPassResult IntToBV::applyInternal(
    AssertionPipeline* assertionsToPreprocess)
{
  NodeMap cache;
  for (unsigned i = 0; i < assertionsToPreprocess->size(); ++i)
  {
    assertionsToPreprocess->replace(
        i, intToBV((*assertionsToPreprocess)[i], cache));
  }
  return PreprocessingPassResult::NO_CONFLICT;
}


}  // namespace passes
}  // namespace preprocessing
}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Andres Noetzli, Yoni Zohar, Alex Ozdemir
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		* The IntToBV preprocessing pass.
14		*
15		* Converts integer operations into bitvector operations. The width of the
16		* bitvectors is controlled through the `--solve-int-as-bv` command line
17		* option.
18		*/
19
20		#include "preprocessing/passes/int_to_bv.h"
21
22		#include <string>
23		#include <unordered_map>
24		#include <vector>
25
26		#include "expr/node.h"
27		#include "expr/node_traversal.h"
28		#include "expr/skolem_manager.h"
29		#include "options/base_options.h"
30		#include "options/smt_options.h"
31		#include "preprocessing/assertion_pipeline.h"
32		#include "preprocessing/preprocessing_pass_context.h"
33		#include "theory/rewriter.h"
34		#include "theory/theory.h"
35		#include "util/bitvector.h"
36		#include "util/rational.h"
37
38		namespace cvc5 {
39		namespace preprocessing {
40		namespace passes {
41
42		using namespace std;
43		using namespace cvc5::theory;
44
45
46		namespace {
47
48	4	bool childrenTypesChanged(Node n, NodeMap& cache) {
49	8	for (Node child : n) {
50	8	TypeNode originalType = child.getType();
51	8	TypeNode newType = cache[child].getType();
52	4	if (! newType.isSubtypeOf(originalType)) {
53		return true;
54		}
55		}
56	4	return false;
57		}
58
59
60	41	Node intToBVMakeBinary(TNode n, NodeMap& cache)
61		{
62	128	for (TNode current : NodeDfsIterable(n, VisitOrder::POSTORDER,
63	338	[&cache](TNode nn) { return cache.count(nn) > 0; }))
64		{
65	256	Node result;
66	128	NodeManager* nm = NodeManager::currentNM();
67	128	if (current.getNumChildren() == 0)
68		{
69	77	result = current;
70		}
71	102	else if (current.getNumChildren() > 2
72	52	&& (current.getKind() == kind::PLUS
73	1	\|\| current.getKind() == kind::MULT
74	1	\|\| current.getKind() == kind::NONLINEAR_MULT))
75		{
76	1	Assert(cache.find(current[0]) != cache.end());
77	1	result = cache[current[0]];
78	3	for (unsigned i = 1; i < current.getNumChildren(); ++i)
79		{
80	2	Assert(cache.find(current[i]) != cache.end());
81	4	Node child = current[i];
82	4	Node childRes = cache[current[i]];
83	2	result = nm->mkNode(current.getKind(), result, childRes);
84		}
85		}
86		else
87		{
88	100	NodeBuilder builder(current.getKind());
89	50	if (current.getMetaKind() == kind::metakind::PARAMETERIZED) {
90	4	builder << current.getOperator();
91		}
92
93	140	for (unsigned i = 0; i < current.getNumChildren(); ++i)
94		{
95	90	Assert(cache.find(current[i]) != cache.end());
96	90	builder << cache[current[i]];
97		}
98	50	result = builder;
99		}
100	128	cache[current] = result;
101		}
102	41	return cache[n];
103		}
104		} // namespace
105
106	41	Node IntToBV::intToBV(TNode n, NodeMap& cache)
107		{
108	41	int size = options::solveIntAsBV();
109	41	AlwaysAssert(size > 0);
110	41	AlwaysAssert(!options::incrementalSolving());
111
112	41	NodeManager* nm = NodeManager::currentNM();
113	41	SkolemManager* sm = nm->getSkolemManager();
114	82	NodeMap binaryCache;
115	82	Node n_binary = intToBVMakeBinary(n, binaryCache);
116
117	109	for (TNode current : NodeDfsIterable(n_binary, VisitOrder::POSTORDER,
118	320	[&cache](TNode nn) { return cache.count(nn) > 0; }))
119		{
120	110	if (current.getNumChildren() > 0)
121		{
122		// Not a leaf
123	100	vector<Node> children;
124	50	uint64_t max = 0;
125	140	for (const Node& nc : current)
126		{
127	90	Assert(cache.find(nc) != cache.end());
128	180	TNode childRes = cache[nc];
129	180	TypeNode type = childRes.getType();
130	90	if (type.isBitVector())
131		{
132	68	uint32_t bvsize = type.getBitVectorSize();
133	68	if (bvsize > max)
134		{
135	41	max = bvsize;
136		}
137		}
138	90	children.push_back(childRes);
139		}
140
141	50	kind::Kind_t newKind = current.getKind();
142	50	if (max > 0)
143		{
144	36	switch (newKind)
145		{
146	3	case kind::PLUS:
147	3	Assert(children.size() == 2);
148	3	newKind = kind::BITVECTOR_ADD;
149	3	max = max + 1;
150	3	break;
151	11	case kind::MULT:
152		case kind::NONLINEAR_MULT:
153	11	Assert(children.size() == 2);
154	11	newKind = kind::BITVECTOR_MULT;
155	11	max = max * 2;
156	11	break;
157		case kind::MINUS:
158		Assert(children.size() == 2);
159		newKind = kind::BITVECTOR_SUB;
160		max = max + 1;
161		break;
162		case kind::UMINUS:
163		Assert(children.size() == 1);
164		newKind = kind::BITVECTOR_NEG;
165		max = max + 1;
166		break;
167		case kind::LT: newKind = kind::BITVECTOR_SLT; break;
168		case kind::LEQ: newKind = kind::BITVECTOR_SLE; break;
169		case kind::GT: newKind = kind::BITVECTOR_SGT; break;
170	7	case kind::GEQ: newKind = kind::BITVECTOR_SGE; break;
171	11	case kind::EQUAL:
172	11	case kind::ITE: break;
173	4	default:
174	4	if (childrenTypesChanged(current, cache)) {
175		throw TypeCheckingExceptionPrivate(
176		current,
177		string("Cannot translate to BV: ") + current.toString());
178		}
179	4	break;
180		}
181	104	for (size_t i = 0, csize = children.size(); i < csize; ++i)
182		{
183	136	TypeNode type = children[i].getType();
184	68	if (!type.isBitVector())
185		{
186		continue;
187		}
188	68	uint32_t bvsize = type.getBitVectorSize();
189	68	if (bvsize < max)
190		{
191		// sign extend
192		Node signExtendOp = nm->mkConst<BitVectorSignExtend>(
193	68	BitVectorSignExtend(max - bvsize));
194	34	children[i] = nm->mkNode(signExtendOp, children[i]);
195		}
196		}
197		}
198	100	NodeBuilder builder(newKind);
199	50	if (current.getMetaKind() == kind::metakind::PARAMETERIZED) {
200	4	builder << current.getOperator();
201		}
202	50	builder.append(children);
203		// Mark the substitution and continue
204	100	Node result = builder;
205
206	50	result = Rewriter::rewrite(result);
207	50	cache[current] = result;
208		}
209		else
210		{
211		// It's a leaf: could be a variable or a numeral
212	120	Node result = current;
213	60	if (current.isVar())
214		{
215	20	if (current.getType() == nm->integerType())
216		{
217	48	result = sm->mkDummySkolem("__intToBV_var",
218	32	nm->mkBitVectorType(size),
219		"Variable introduced in intToBV pass");
220	32	Node bv2nat = nm->mkNode(kind::BITVECTOR_TO_NAT, result);
221	16	d_preprocContext->addSubstitution(current, bv2nat);
222		}
223		}
224	40	else if (current.isConst())
225		{
226	40	switch (current.getKind())
227		{
228	18	case kind::CONST_RATIONAL:
229		{
230	36	Rational constant = current.getConst<Rational>();
231	18	if (constant.isIntegral()) {
232	36	BitVector bv(size, constant.getNumerator());
233	18	if (bv.toSignedInteger() != constant.getNumerator())
234		{
235		throw TypeCheckingExceptionPrivate(
236		current,
237	2	string("Not enough bits for constant in intToBV: ")
238	3	+ current.toString());
239		}
240	17	result = nm->mkConst(bv);
241		}
242	17	break;
243		}
244	22	default: break;
245		}
246		}
247		else
248		{
249		throw TypeCheckingExceptionPrivate(
250		current, string("Cannot translate to BV: ") + current.toString());
251		}
252	59	cache[current] = result;
253		}
254		}
255	40	Trace("int-to-bv-debug") << "original: " << n << std::endl;
256	40	Trace("int-to-bv-debug") << "binary: " << n_binary << std::endl;
257	40	Trace("int-to-bv-debug") << "result: " << cache[n_binary] << std::endl;
258	80	return cache[n_binary];
259		}
260
261	9851	IntToBV::IntToBV(PreprocessingPassContext* preprocContext)
262	9851	: PreprocessingPass(preprocContext, "int-to-bv"){};
263
264	15	PreprocessingPassResult IntToBV::applyInternal(
265		AssertionPipeline* assertionsToPreprocess)
266		{
267	30	NodeMap cache;
268	55	for (unsigned i = 0; i < assertionsToPreprocess->size(); ++i)
269		{
270	40	assertionsToPreprocess->replace(
271	81	i, intToBV((*assertionsToPreprocess)[i], cache));
272		}
273	28	return PreprocessingPassResult::NO_CONFLICT;
274		}
275
276
277		} // namespace passes
278		} // namespace preprocessing
279	29337	} // namespace cvc5