cprover
simplify_expr_struct.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 "simplify_expr_class.h"
10 
11 #include "arith_tools.h"
12 #include "byte_operators.h"
13 #include "invariant.h"
14 #include "namespace.h"
15 #include "pointer_offset_size.h"
16 #include "simplify_utils.h"
17 #include "std_expr.h"
18 
21 {
22  const irep_idt &component_name=
24 
25  const exprt &op = expr.compound();
26  const typet &op_type=ns.follow(op.type());
27 
28  if(op.id()==ID_with)
29  {
30  // the following optimization only works on structs,
31  // and not on unions
32 
33  if(op.operands().size()>=3 &&
34  op_type.id()==ID_struct)
35  {
36  exprt::operandst new_operands = op.operands();
37 
38  while(new_operands.size() > 1)
39  {
40  exprt &op1 = new_operands[new_operands.size() - 2];
41  exprt &op2 = new_operands[new_operands.size() - 1];
42 
43  if(op1.get(ID_component_name)==component_name)
44  {
45  // found it!
47  op2.type() == expr.type(),
48  "member expression type must match component type");
49  exprt tmp;
50  tmp.swap(op2);
51 
52  // do this recursively
53  return changed(simplify_rec(tmp));
54  }
55  else // something else, get rid of it
56  new_operands.resize(new_operands.size() - 2);
57  }
58 
59  DATA_INVARIANT(new_operands.size() == 1, "post-condition of loop");
60 
61  auto new_member_expr = expr;
62  new_member_expr.struct_op() = new_operands.front();
63  // do this recursively
64  return changed(simplify_member(new_member_expr));
65  }
66  else if(op_type.id()==ID_union)
67  {
68  const with_exprt &with_expr=to_with_expr(op);
69 
70  if(with_expr.where().get(ID_component_name)==component_name)
71  {
72  // WITH(s, .m, v).m -> v
73  auto tmp = with_expr.new_value();
74 
75  // do this recursively
76  return changed(simplify_rec(tmp));
77  }
78  }
79  }
80  else if(op.id()==ID_update)
81  {
82  if(op.operands().size()==3 &&
83  op_type.id()==ID_struct)
84  {
85  const update_exprt &update_expr=to_update_expr(op);
86  const exprt::operandst &designator=update_expr.designator();
87 
88  // look at very first designator
89  if(designator.size()==1 &&
90  designator.front().id()==ID_member_designator)
91  {
92  if(designator.front().get(ID_component_name)==component_name)
93  {
94  // UPDATE(s, .m, v).m -> v
95  exprt tmp=update_expr.new_value();
96 
97  // do this recursively
98  return changed(simplify_rec(tmp));
99  }
100  // the following optimization only works on structs,
101  // and not on unions
102  else if(op_type.id()==ID_struct)
103  {
104  // UPDATE(s, .m1, v).m2 -> s.m2
105  auto new_expr = expr;
106  new_expr.struct_op() = update_expr.old();
107 
108  // do this recursively
109  return changed(simplify_rec(new_expr));
110  }
111  }
112  }
113  }
114  else if(op.id()==ID_struct ||
115  op.id()==ID_constant)
116  {
117  if(op_type.id()==ID_struct)
118  {
119  // pull out the right member
120  const struct_typet &struct_type=to_struct_type(op_type);
121  if(struct_type.has_component(component_name))
122  {
123  std::size_t number=struct_type.component_number(component_name);
125  op.operands()[number].type() == expr.type(),
126  "member expression type must match component type");
127  return op.operands()[number];
128  }
129  }
130  }
131  else if(op.id()==ID_byte_extract_little_endian ||
132  op.id()==ID_byte_extract_big_endian)
133  {
134  const auto &byte_extract_expr = to_byte_extract_expr(op);
135 
136  if(op_type.id()==ID_struct)
137  {
138  // This rewrites byte_extract(s, o, struct_type).member
139  // to byte_extract(s, o+member_offset, member_type)
140 
141  const struct_typet &struct_type=to_struct_type(op_type);
143  struct_type.get_component(component_name);
144 
145  if(
146  component.is_nil() || component.type().id() == ID_c_bit_field ||
147  component.type().id() == ID_bool)
148  {
149  return unchanged(expr);
150  }
151 
152  // add member offset to index
153  auto offset_int = member_offset(struct_type, component_name, ns);
154  if(!offset_int.has_value())
155  return unchanged(expr);
156 
157  const exprt &struct_offset = byte_extract_expr.offset();
158  exprt member_offset = from_integer(*offset_int, struct_offset.type());
159  exprt final_offset =
160  simplify_node(plus_exprt(struct_offset, member_offset));
161 
162  byte_extract_exprt result(
163  op.id(), byte_extract_expr.op(), final_offset, expr.type());
164 
165  return changed(simplify_rec(result)); // recursive call
166  }
167  else if(op_type.id() == ID_union)
168  {
169  // rewrite byte_extract(X, 0).member to X
170  // if the type of X is that of the member
171  if(byte_extract_expr.offset().is_zero())
172  {
173  const union_typet &union_type = to_union_type(op_type);
174  const typet &subtype = union_type.component_type(component_name);
175 
176  if(subtype == byte_extract_expr.op().type())
177  return byte_extract_expr.op();
178  }
179  }
180  }
181  else if(op.id()==ID_union && op_type.id()==ID_union)
182  {
183  // trivial?
184  if(to_union_expr(op).op().type() == expr.type())
185  return to_union_expr(op).op();
186 
187  // need to convert!
188  auto target_size = pointer_offset_size(expr.type(), ns);
189 
190  if(target_size.has_value())
191  {
192  mp_integer target_bits = target_size.value() * 8;
193  const auto bits = expr2bits(op, true, ns);
194 
195  if(bits.has_value() &&
196  mp_integer(bits->size())>=target_bits)
197  {
198  std::string bits_cut =
199  std::string(*bits, 0, numeric_cast_v<std::size_t>(target_bits));
200 
201  auto tmp = bits2expr(bits_cut, expr.type(), true, ns);
202 
203  if(tmp.has_value())
204  return std::move(*tmp);
205  }
206  }
207  }
208  else if(op.id() == ID_typecast)
209  {
210  const auto &typecast_expr = to_typecast_expr(op);
211 
212  // Try to look through member(cast(x)) if the cast is between structurally
213  // identical types:
214  if(op_type == typecast_expr.op().type())
215  {
216  auto new_expr = expr;
217  new_expr.struct_op() = typecast_expr.op();
218  return changed(simplify_member(new_expr));
219  }
220 
221  // Try to translate into an equivalent member (perhaps nested) of the type
222  // being cast (for example, this might turn ((struct A)x).field1 into
223  // x.substruct.othersubstruct.field2, if field1 and field2 have the same
224  // type and offset with respect to x.
225  if(op_type.id() == ID_struct)
226  {
227  optionalt<mp_integer> requested_offset =
228  member_offset(to_struct_type(op_type), component_name, ns);
229  if(requested_offset.has_value())
230  {
231  auto equivalent_member = get_subexpression_at_offset(
232  typecast_expr.op(), *requested_offset, expr.type(), ns);
233 
234  // Guess: turning this into a byte-extract operation is not really an
235  // optimisation.
236  if(
237  equivalent_member.has_value() &&
238  equivalent_member.value().id() != ID_byte_extract_little_endian &&
239  equivalent_member.value().id() != ID_byte_extract_big_endian)
240  {
241  auto tmp = equivalent_member.value();
242  return changed(simplify_rec(tmp));
243  }
244  }
245  }
246  }
247  else if(op.id()==ID_if)
248  {
249  const if_exprt &if_expr=to_if_expr(op);
250  exprt cond=if_expr.cond();
251 
252  member_exprt member_false=to_member_expr(expr);
253  member_false.compound()=if_expr.false_case();
254 
255  member_exprt member_true = to_member_expr(expr);
256  member_true.compound() = if_expr.true_case();
257 
258  auto tmp = if_exprt(cond, member_true, member_false, expr.type());
259  return changed(simplify_rec(tmp));
260  }
261  else if(op.id() == ID_let)
262  {
263  // Push a member operator inside a let binding, to avoid the let bisecting
264  // structures we otherwise know how to analyse, such as
265  // (let x = 1 in ({x, x})).field1 --> let x = 1 in ({x, x}.field1) -->
266  // let x = 1 in x
267  member_exprt pushed_in_member = to_member_expr(expr);
268  pushed_in_member.op() = to_let_expr(op).where();
269  auto new_expr = op;
270  to_let_expr(new_expr).where() = pushed_in_member;
271  to_let_expr(new_expr).type() = to_let_expr(new_expr).where().type();
272 
273  return changed(simplify_rec(new_expr));
274  }
275 
276  return unchanged(expr);
277 }
with_exprt
Operator to update elements in structs and arrays.
Definition: std_expr.h:2173
simplify_exprt::simplify_rec
resultt simplify_rec(const exprt &)
Definition: simplify_expr.cpp:2434
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
pointer_offset_size.h
Pointer Logic.
to_update_expr
const update_exprt & to_update_expr(const exprt &expr)
Cast an exprt to an update_exprt.
Definition: std_expr.h:2422
simplify_expr_class.h
arith_tools.h
struct_union_typet::get_component
const componentt & get_component(const irep_idt &component_name) const
Get the reference to a component with given name.
Definition: std_types.cpp:67
to_struct_type
const struct_typet & to_struct_type(const typet &type)
Cast a typet to a struct_typet.
Definition: std_types.h:303
typet
The type of an expression, extends irept.
Definition: type.h:28
update_exprt::old
exprt & old()
Definition: std_expr.h:2369
to_byte_extract_expr
const byte_extract_exprt & to_byte_extract_expr(const exprt &expr)
Definition: byte_operators.h:57
to_if_expr
const if_exprt & to_if_expr(const exprt &expr)
Cast an exprt to an if_exprt.
Definition: std_expr.h:2152
bits2expr
optionalt< exprt > bits2expr(const std::string &bits, const typet &type, bool little_endian, const namespacet &ns)
Definition: simplify_utils.cpp:193
mp_integer
BigInt mp_integer
Definition: mp_arith.h:19
if_exprt
The trinary if-then-else operator.
Definition: std_expr.h:2087
with_exprt::new_value
exprt & new_value()
Definition: std_expr.h:2203
plus_exprt
The plus expression Associativity is not specified.
Definition: std_expr.h:831
struct_union_typet::component_type
const typet & component_type(const irep_idt &component_name) const
Definition: std_types.cpp:80
exprt
Base class for all expressions.
Definition: expr.h:54
to_union_expr
const union_exprt & to_union_expr(const exprt &expr)
Cast an exprt to a union_exprt.
Definition: std_expr.h:1563
component
auto component(T &struct_expr, const irep_idt &name, const namespacet &ns) -> decltype(struct_expr.op0())
Definition: std_expr.cpp:55
namespace.h
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:50
simplify_exprt::unchanged
static resultt unchanged(exprt expr)
Definition: simplify_expr_class.h:126
if_exprt::false_case
exprt & false_case()
Definition: std_expr.h:2124
simplify_exprt::simplify_node
resultt simplify_node(exprt)
Definition: simplify_expr.cpp:2192
exprt::type
typet & type()
Return the type of the expression.
Definition: expr.h:82
byte_operators.h
Expression classes for byte-level operators.
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
member_exprt::compound
const exprt & compound() const
Definition: std_expr.h:2569
member_exprt::struct_op
const exprt & struct_op() const
Definition: std_expr.h:2558
simplify_exprt::changed
static resultt changed(resultt<> result)
Definition: simplify_expr_class.h:131
to_let_expr
const let_exprt & to_let_expr(const exprt &expr)
Cast an exprt to a let_exprt.
Definition: std_expr.h:2940
irept::swap
void swap(irept &irep)
Definition: irep.h:452
struct_union_typet::has_component
bool has_component(const irep_idt &component_name) const
Definition: std_types.h:152
irept::id
const irep_idt & id() const
Definition: irep.h:407
exprt::operandst
std::vector< exprt > operandst
Definition: expr.h:56
union_typet
The union type.
Definition: std_types.h:393
unary_exprt::op
const exprt & op() const
Definition: std_expr.h:294
simplify_exprt::resultt
Definition: simplify_expr_class.h:93
optionalt
nonstd::optional< T > optionalt
Definition: optional.h:35
to_with_expr
const with_exprt & to_with_expr(const exprt &expr)
Cast an exprt to a with_exprt.
Definition: std_expr.h:2235
update_exprt
Operator to update elements in structs and arrays.
Definition: std_expr.h:2357
update_exprt::designator
exprt::operandst & designator()
Definition: std_expr.h:2383
expr2bits
optionalt< std::string > expr2bits(const exprt &expr, bool little_endian, const namespacet &ns)
Definition: simplify_utils.cpp:405
member_exprt
Extract member of struct or union.
Definition: std_expr.h:2528
struct_union_typet::componentt
Definition: std_types.h:64
simplify_exprt::simplify_member
resultt simplify_member(const member_exprt &)
Definition: simplify_expr_struct.cpp:20
struct_typet
Structure type, corresponds to C style structs.
Definition: std_types.h:226
pointer_offset_size
optionalt< mp_integer > pointer_offset_size(const typet &type, const namespacet &ns)
Compute the size of a type in bytes, rounding up to full bytes.
Definition: pointer_offset_size.cpp:89
if_exprt::true_case
exprt & true_case()
Definition: std_expr.h:2114
namespace_baset::follow
const typet & follow(const typet &) const
Resolve type symbol to the type it points to.
Definition: namespace.cpp:51
irept::get
const irep_idt & get(const irep_namet &name) const
Definition: irep.cpp:51
update_exprt::new_value
exprt & new_value()
Definition: std_expr.h:2393
from_integer
constant_exprt from_integer(const mp_integer &int_value, const typet &type)
Definition: arith_tools.cpp:99
to_typecast_expr
const typecast_exprt & to_typecast_expr(const exprt &expr)
Cast an exprt to a typecast_exprt.
Definition: std_expr.h:1815
get_subexpression_at_offset
optionalt< exprt > get_subexpression_at_offset(const exprt &expr, const mp_integer &offset_bytes, const typet &target_type_raw, const namespacet &ns)
Definition: pointer_offset_size.cpp:605
if_exprt::cond
exprt & cond()
Definition: std_expr.h:2104
invariant.h
byte_extract_exprt
Expression of type type extracted from some object op starting at position offset (given in number of...
Definition: byte_operators.h:29
simplify_exprt::ns
const namespacet & ns
Definition: simplify_expr_class.h:238
to_member_expr
const member_exprt & to_member_expr(const exprt &expr)
Cast an exprt to a member_exprt.
Definition: std_expr.h:2612
member_exprt::get_component_name
irep_idt get_component_name() const
Definition: std_expr.h:2542
exprt::operands
operandst & operands()
Definition: expr.h:96
to_union_type
const union_typet & to_union_type(const typet &type)
Cast a typet to a union_typet.
Definition: std_types.h:430
simplify_utils.h
let_exprt::where
exprt & where()
convenience accessor for binding().where()
Definition: std_expr.h:2909
std_expr.h
API to expression classes.
with_exprt::where
exprt & where()
Definition: std_expr.h:2193
member_offset
optionalt< mp_integer > member_offset(const struct_typet &type, const irep_idt &member, const namespacet &ns)
Definition: pointer_offset_size.cpp:23