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