cprover
boolbv_width.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module:
4 
5 Author: Daniel Kroening, kroening@kroening.com
6 
7 \*******************************************************************/
8 
9 #include "boolbv_width.h"
10 
11 #include <algorithm>
12 
13 #include <util/arith_tools.h>
14 #include <util/exception_utils.h>
15 #include <util/invariant.h>
16 #include <util/std_types.h>
17 
19 {
20 }
21 
23 {
24 }
25 
27 {
28  // check cache first
29 
30  std::pair<cachet::iterator, bool> cache_result=
31  cache.insert(std::pair<typet, entryt>(type, entryt()));
32 
33  entryt &entry=cache_result.first->second;
34 
35  if(!cache_result.second) // found!
36  return entry;
37 
38  entry.total_width=0;
39 
40  const irep_idt type_id=type.id();
41 
42  if(type_id==ID_struct)
43  {
44  const struct_typet::componentst &components=
45  to_struct_type(type).components();
46 
47  std::size_t offset=0;
48  entry.members.resize(components.size());
49 
50  for(std::size_t i=0; i<entry.members.size(); i++)
51  {
52  std::size_t sub_width=operator()(components[i].type());
53  entry.members[i].offset=offset;
54  entry.members[i].width=sub_width;
55  offset+=sub_width;
56  }
57 
58  entry.total_width=offset;
59  }
60  else if(type_id==ID_union)
61  {
62  const union_typet::componentst &components=
63  to_union_type(type).components();
64 
65  entry.members.resize(components.size());
66 
67  std::size_t max_width=0;
68 
69  for(std::size_t i=0; i<entry.members.size(); i++)
70  {
71  std::size_t sub_width=operator()(components[i].type());
72  entry.members[i].width=sub_width;
73  max_width=std::max(max_width, sub_width);
74  }
75 
76  entry.total_width=max_width;
77  }
78  else if(type_id==ID_bool)
79  entry.total_width=1;
80  else if(type_id==ID_c_bool)
81  {
82  entry.total_width=to_c_bool_type(type).get_width();
83  }
84  else if(type_id==ID_signedbv)
85  {
87  }
88  else if(type_id==ID_unsignedbv)
89  {
91  }
92  else if(type_id==ID_floatbv)
93  {
95  }
96  else if(type_id==ID_fixedbv)
97  {
99  }
100  else if(type_id==ID_bv)
101  {
102  entry.total_width=to_bv_type(type).get_width();
103  }
104  else if(type_id==ID_verilog_signedbv ||
105  type_id==ID_verilog_unsignedbv)
106  {
107  // we encode with two bits
108  std::size_t size = to_bitvector_type(type).get_width();
110  size > 0, "verilog bitvector width shall be greater than zero");
111  entry.total_width = size * 2;
112  }
113  else if(type_id==ID_range)
114  {
115  mp_integer from=string2integer(type.get_string(ID_from)),
116  to=string2integer(type.get_string(ID_to));
117 
118  mp_integer size=to-from+1;
119 
120  if(size>=1)
121  {
122  entry.total_width = address_bits(size);
123  CHECK_RETURN(entry.total_width > 0);
124  }
125  }
126  else if(type_id==ID_array)
127  {
128  const array_typet &array_type=to_array_type(type);
129  std::size_t sub_width=operator()(array_type.subtype());
130 
131  const auto array_size = numeric_cast<mp_integer>(array_type.size());
132 
133  if(!array_size.has_value())
134  {
135  // we can still use the theory of arrays for this
136  entry.total_width=0;
137  }
138  else
139  {
140  mp_integer total = *array_size * sub_width;
141  if(total>(1<<30)) // realistic limit
142  throw analysis_exceptiont("array too large for flattening");
143 
144  if(total < 0)
145  entry.total_width = 0;
146  else
147  entry.total_width = numeric_cast_v<std::size_t>(total);
148  }
149  }
150  else if(type_id==ID_vector)
151  {
152  const vector_typet &vector_type=to_vector_type(type);
153  std::size_t sub_width=operator()(vector_type.subtype());
154 
155  const auto vector_size = numeric_cast_v<mp_integer>(vector_type.size());
156 
157  mp_integer total = vector_size * sub_width;
158  if(total > (1 << 30)) // realistic limit
159  throw analysis_exceptiont("vector too large for flattening");
160 
161  entry.total_width = numeric_cast_v<std::size_t>(vector_size * sub_width);
162  }
163  else if(type_id==ID_complex)
164  {
165  const mp_integer sub_width = operator()(type.subtype());
166  entry.total_width = numeric_cast_v<std::size_t>(2 * sub_width);
167  }
168  else if(type_id==ID_code)
169  {
170  }
171  else if(type_id==ID_enumeration)
172  {
173  // get number of necessary bits
174  std::size_t size=to_enumeration_type(type).elements().size();
175  entry.total_width = address_bits(size);
176  CHECK_RETURN(entry.total_width > 0);
177  }
178  else if(type_id==ID_c_enum)
179  {
180  // these have a subtype
182  CHECK_RETURN(entry.total_width > 0);
183  }
184  else if(type_id==ID_pointer)
185  entry.total_width = type_checked_cast<pointer_typet>(type).get_width();
186  else if(type_id==ID_struct_tag)
188  else if(type_id==ID_union_tag)
190  else if(type_id==ID_c_enum_tag)
192  else if(type_id==ID_c_bit_field)
193  {
195  }
196  else if(type_id==ID_string)
197  entry.total_width=32;
198  else if(type_id != ID_empty)
200 
201  return entry;
202 }
203 
205  const struct_typet &type,
206  const irep_idt &member) const
207 {
208  std::size_t component_number=type.component_number(member);
209 
210  return get_entry(type).members[component_number];
211 }
to_c_bool_type
const c_bool_typet & to_c_bool_type(const typet &type)
Cast a typet to a c_bool_typet.
Definition: std_types.h:1636
struct_union_typet::components
const componentst & components() const
Definition: std_types.h:142
exception_utils.h
to_union_tag_type
const union_tag_typet & to_union_tag_type(const typet &type)
Cast a typet to a union_tag_typet.
Definition: std_types.h:555
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
to_c_enum_tag_type
const c_enum_tag_typet & to_c_enum_tag_type(const typet &type)
Cast a typet to a c_enum_tag_typet.
Definition: std_types.h:721
to_enumeration_type
const enumeration_typet & to_enumeration_type(const typet &type)
Cast a typet to a enumeration_typet.
Definition: std_types.h:605
typet::subtype
const typet & subtype() const
Definition: type.h:47
UNIMPLEMENTED
#define UNIMPLEMENTED
Definition: invariant.h:523
boolbv_widtht::membert
Definition: boolbv_width.h:28
arith_tools.h
boolbv_widtht::operator()
std::size_t operator()(const typet &type) const
Definition: boolbv_width.h:22
to_struct_type
const struct_typet & to_struct_type(const typet &type)
Cast a typet to a struct_typet.
Definition: std_types.h:303
CHECK_RETURN
#define CHECK_RETURN(CONDITION)
Definition: invariant.h:496
typet
The type of an expression, extends irept.
Definition: type.h:29
boolbv_widtht::get_entry
const entryt & get_entry(const typet &type) const
Definition: boolbv_width.cpp:26
mp_integer
BigInt mp_integer
Definition: mp_arith.h:19
string2integer
const mp_integer string2integer(const std::string &n, unsigned base)
Definition: mp_arith.cpp:57
invariant.h
struct_union_typet::componentst
std::vector< componentt > componentst
Definition: std_types.h:135
namespace_baset::follow_tag
const union_typet & follow_tag(const union_tag_typet &) const
Follow type tag of union type.
Definition: namespace.cpp:65
vector_typet
The vector type.
Definition: std_types.h:1750
struct_union_typet::component_number
std::size_t component_number(const irep_idt &component_name) const
Return the sequence number of the component with given name.
Definition: std_types.cpp:36
to_bv_type
const bv_typet & to_bv_type(const typet &type)
Cast a typet to a bv_typet.
Definition: std_types.h:1139
boolbv_widtht::entryt
Definition: boolbv_width.h:40
array_typet::size
const exprt & size() const
Definition: std_types.h:973
address_bits
std::size_t address_bits(const mp_integer &size)
ceil(log2(size))
Definition: arith_tools.cpp:176
namespacet
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:92
to_fixedbv_type
const fixedbv_typet & to_fixedbv_type(const typet &type)
Cast a typet to a fixedbv_typet.
Definition: std_types.h:1362
to_unsignedbv_type
const unsignedbv_typet & to_unsignedbv_type(const typet &type)
Cast a typet to an unsignedbv_typet.
Definition: std_types.h:1248
DATA_INVARIANT
#define DATA_INVARIANT(CONDITION, REASON)
This condition should be used to document that assumptions that are made on goto_functions,...
Definition: invariant.h:511
std_types.h
Pre-defined types.
to_c_bit_field_type
const c_bit_field_typet & to_c_bit_field_type(const typet &type)
Cast a typet to a c_bit_field_typet.
Definition: std_types.h:1471
irept::id
const irep_idt & id() const
Definition: irep.h:418
to_struct_tag_type
const struct_tag_typet & to_struct_tag_type(const typet &type)
Cast a typet to a struct_tag_typet.
Definition: std_types.h:515
boolbv_widtht::ns
const namespacet & ns
Definition: boolbv_width.h:37
vector_typet::size
const constant_exprt & size() const
Definition: std_types.cpp:268
boolbv_widtht::boolbv_widtht
boolbv_widtht(const namespacet &_ns)
Definition: boolbv_width.cpp:18
bitvector_typet::get_width
std::size_t get_width() const
Definition: std_types.h:1041
boolbv_widtht::cache
cachet cache
Definition: boolbv_width.h:48
irept::get_string
const std::string & get_string(const irep_namet &name) const
Definition: irep.h:431
enumeration_typet::elements
const irept::subt & elements() const
Definition: std_types.h:577
struct_typet
Structure type, corresponds to C style structs.
Definition: std_types.h:226
array_typet
Arrays with given size.
Definition: std_types.h:965
boolbv_widtht::entryt::total_width
std::size_t total_width
Definition: boolbv_width.h:41
boolbv_width.h
boolbv_widtht::entryt::members
std::vector< membert > members
Definition: boolbv_width.h:42
to_signedbv_type
const signedbv_typet & to_signedbv_type(const typet &type)
Cast a typet to a signedbv_typet.
Definition: std_types.h:1298
to_array_type
const array_typet & to_array_type(const typet &type)
Cast a typet to an array_typet.
Definition: std_types.h:1011
to_floatbv_type
const floatbv_typet & to_floatbv_type(const typet &type)
Cast a typet to a floatbv_typet.
Definition: std_types.h:1424
to_vector_type
const vector_typet & to_vector_type(const typet &type)
Cast a typet to a vector_typet.
Definition: std_types.h:1775
to_union_type
const union_typet & to_union_type(const typet &type)
Cast a typet to a union_typet.
Definition: std_types.h:422
boolbv_widtht::get_member
const membert & get_member(const struct_typet &type, const irep_idt &member) const
Definition: boolbv_width.cpp:204
boolbv_widtht::~boolbv_widtht
~boolbv_widtht()
Definition: boolbv_width.cpp:22
to_bitvector_type
const bitvector_typet & to_bitvector_type(const typet &type)
Cast a typet to a bitvector_typet.
Definition: std_types.h:1089
analysis_exceptiont
Thrown when an unexpected error occurs during the analysis (e.g., when the SAT solver returns an erro...
Definition: exception_utils.h:157