Branch data Line data Source code
1 : : /* State will store states of variables for a function's single execution path.
2 : : It will be used for bit-level symbolic execution to determine values of bits
3 : : of function's return value and symbolic marked arguments.
4 : : Copyright (C) 2022-2024 Free Software Foundation, Inc.
5 : : Contributed by Matevos Mehrabyan <matevosmehrabyan@gmail.com>
6 : :
7 : : This file is part of GCC.
8 : :
9 : : GCC is free software; you can redistribute it and/or modify it under
10 : : the terms of the GNU General Public License as published by the Free
11 : : Software Foundation; either version 3, or (at your option) any later
12 : : version.
13 : :
14 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 : : for more details.
18 : :
19 : : You should have received a copy of the GNU General Public License
20 : : along with GCC; see the file COPYING3. If not see
21 : : <http://www.gnu.org/licenses/>. */
22 : :
23 : : /* This symbolic executor is designed to handle operations on the bit level.
24 : : It can save values of variables on the bit level. For example byte x = 9
25 : : would be represented by the bit-vector x = <0, 0, 0, 0, 1, 0, 1, 0> of
26 : : size 8. Variables without values will be represented by bit-vectors of
27 : : symbolic bits: x = <x[size - 1], ..., x[1], x[0]> where x[i] is the value
28 : : of bit i of variable x.
29 : :
30 : : Operations are also performed on the bit level. For example, for operation
31 : : z = x & y
32 : : where
33 : : x = <x[size - 1], ..., x[1], x[0]>
34 : : y = <y[size - 1], ..., y[1], y[0]>
35 : : z will have the value
36 : : z = <x[size - 1] & y[size - 1], ..., x[1] & y[1], x[0] & y[0]>
37 : :
38 : : Each bit of variable can be accessed and examined separately if needed.
39 : : Moreover, it does basic optimizations in place.
40 : : For example, for operation
41 : : z = x | y
42 : : where
43 : : x = <x[size - 1], ..., x[1], x[0]>,
44 : : y = <1, ..., 0, 1>,
45 : : z will have the value
46 : : z = <1, ..., x[1], 1>
47 : : as x | 0 == x and x | 1 == 1
48 : :
49 : : Besides variables, the symbolic executor can also store
50 : : conditions on the bit level.
51 : : For example, for x == y
52 : : It would add {x[size - 1] == y[size - 1], ..., x[1] == y[1], x[0] == y[0]}
53 : : conditions.
54 : :
55 : : For a more complex condition x > y, it would add
56 : : {x[size - 1] > y[size - 1] || (x[size - 1] == y[size -1]
57 : : && (x[size - 2] > y[size - 2] || (x[size - 2] == y[size - 2]
58 : : && ... (x[0] >= y[0])...)}
59 : :
60 : : The symbolic executor doesn't run by itself. Instead, it must be dictated
61 : : what to do. This makes it flexible and allows for various pre- and
62 : : post-processing tasks. Developers adding new operation support must consider
63 : : that the operation must be represented on the bit level. Because of
64 : : this restriction, it may be hard to add support for some operations.
65 : :
66 : : To use the symbolic executor, you must create a state object. It is the main
67 : : object that contains variables as bit-vectors and conditions.
68 : : It is the state object that provides operations for symbolic execution.
69 : :
70 : : If you are going to execute multiple execution paths, you should clone
71 : : the state at branching instructions and execute one state for the execution
72 : : path where the branching condition evaluates to 'true', and
73 : : the other state for the execution path where the branching condition
74 : : evaluates to 'false'. Besides that, you should add the corresponding
75 : : conditions to states if you need them.
76 : :
77 : : Variables are stored in the state's 'var_states' field. It maps the tree
78 : : object of the variable to its bit-vector. Path conditions are stored in
79 : : the 'conditions' field.
80 : :
81 : : To declare a variable, you should use 'declare_if_needed' method of state.
82 : : It declares the variable if it was not previously declared.
83 : : 'create_val_for_const' is used for constant declaration.
84 : :
85 : : The list of supported operations can be found in 'state::do_operation'
86 : : method. It calls the corresponding operation based on the specified
87 : : tree_code operation. This is the method that you should use to dictate
88 : : to the symbolic executor what operations to perform. You can execute the
89 : : desired operations explicitly if needed. Variables for participant
90 : : operands will be created implicitly if it was not previously declared.
91 : : To add conditions to the state, you should use 'state::add_*_cond' methods.
92 : :
93 : : A sample usage of the symbolic executor:
94 : :
95 : : // Example.
96 : :
97 : : unsigned char foo (unsigned char x, unsigned char y)
98 : : {
99 : : unsigned char D.2352;
100 : : unsigned char result;
101 : :
102 : : result = x & y;
103 : : result = result | 9;
104 : : if (result == 23) goto <D.2350>; else goto <D.2351>;
105 : : <D.2350>:
106 : : result = result ^ y;
107 : : <D.2351>:
108 : : D.2352 = result;
109 : : return D.2352;
110 : : }
111 : :
112 : : // Now, we create the initial state and add the variables to it.
113 : : state s;
114 : : s.declare_if_needed (x, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (x))));
115 : : s.declare_if_needed (y, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (y))));
116 : : s.declare_if_needed (d_2352, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (d_2352))));
117 : : s.declare_if_needed (result, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (result))));
118 : :
119 : : s.do_operation (BIT_AND_EXPR, x, y, result);
120 : : s.do_operation (BIT_OR_EXPR, result, 9, result);
121 : :
122 : : state s2 (s); // We duplicate the state to save values for each branch.
123 : : s.add_equal_cond (result, 23);
124 : : s2.add_not_equal_cond (result, 23);
125 : :
126 : : s.do_operation (BIT_XOR_EXPR, result, y, result);
127 : : s.do_assign (result, d_2352);
128 : : s2.do_assign (result, d_2352);
129 : :
130 : : // Now, we have variable values for each execution branch, and we can examine
131 : : // them to make decisions.
132 : :
133 : : value * res = s.get_value (result);
134 : : if (is_a<bit_expression *> ((*res)[0]))
135 : : {
136 : : bit_expression * expr = is_a<bit_expression *> ((*res)[0]);
137 : : if (is_a<bit *> (expr->get_left ())
138 : : && as_a<bit *> (expr->get_left ())->get_val () == 0)
139 : : {
140 : : ... // Do something.
141 : : }
142 : : }
143 : :
144 : : A more general usage would be to iterate over instructions and
145 : : call the executor:
146 : :
147 : : state s;
148 : : ...
149 : :
150 : : for (inst : instructions)
151 : : {
152 : : enum tree_code rhs_code = gimple_assign_rhs_code (inst);
153 : : tree op1 = gimple_assign_rhs1 (gs);
154 : : tree op2 = gimple_assign_rhs2 (gs);
155 : : tree lhs = gimple_assign_lhs (gs);
156 : : s.do_operation (rhs_code, op1, op2, lhs);
157 : : ...
158 : : }
159 : :
160 : : */
161 : :
162 : : #include "sym-exec-state.h"
163 : :
164 : : /* Returns the minimum of A, B, C. */
165 : :
166 : 19558 : size_t min (size_t a, size_t b, size_t c)
167 : : {
168 : 19558 : size_t min = (a < b ? a : b);
169 : 19558 : return min < c ? min : c;
170 : : }
171 : :
172 : :
173 : : /* Copy constructor for state. It copies all variables and conditions
174 : : of the given state. */
175 : :
176 : 9547 : state::state (const state &s)
177 : : {
178 : 189273 : for (auto iter = s.var_states.begin (); iter != s.var_states.end (); ++iter)
179 : : {
180 : 89863 : value val ((*iter).second.length (), (*iter).second.is_unsigned);
181 : 3198599 : for (size_t i = 0; i < (*iter).second.length (); i++)
182 : 3108736 : val.push ((*iter).second[i]->copy ());
183 : :
184 : 89863 : var_states.put ((*iter).first, val);
185 : 89863 : }
186 : :
187 : 15585 : for (auto iter = s.conditions.begin (); iter != s.conditions.end (); ++iter)
188 : 6038 : conditions.add (as_a<bit_expression *> ((*iter)->copy ()));
189 : 9547 : }
190 : :
191 : :
192 : : /* Destructor for state. */
193 : :
194 : 12822 : state::~state ()
195 : : {
196 : 12822 : clear_conditions ();
197 : 12822 : }
198 : :
199 : :
200 : : /* Checks whether state for variable with specified name already
201 : : exists or not. */
202 : :
203 : : bool
204 : 151781 : state::is_declared (tree var)
205 : : {
206 : 151781 : return var_states.get (var) != NULL;
207 : : }
208 : :
209 : :
210 : : /* Declares given variable if it has not been declared yet. */
211 : :
212 : : void
213 : 123107 : state::declare_if_needed (tree var, size_t size)
214 : : {
215 : 123107 : if (TREE_CODE (var) != INTEGER_CST && !is_declared (var))
216 : : {
217 : 46911 : make_symbolic (var, size);
218 : 46911 : if (dump_file && (dump_flags & TDF_DETAILS))
219 : : {
220 : 41837 : fprintf (dump_file,
221 : : "Declaring var ");
222 : 41837 : print_generic_expr (dump_file, var, dump_flags);
223 : 41837 : fprintf (dump_file,
224 : : " with size %zd\n", size);
225 : : }
226 : : }
227 : 123107 : }
228 : :
229 : :
230 : : /* Get value of the given variable. */
231 : :
232 : : value *
233 : 17501 : state::get_value (tree var)
234 : : {
235 : 17501 : return var_states.get (var);
236 : : }
237 : :
238 : :
239 : : /* Get the value of the tree, which is in the beginning of the var_states. */
240 : :
241 : : value *
242 : 0 : state::get_first_value ()
243 : : {
244 : 0 : return &(*(var_states.begin ())).second;
245 : : }
246 : :
247 : :
248 : : /* Returns the list of conditions in the state. */
249 : :
250 : : const hash_set<bit_expression *> &
251 : 12072 : state::get_conditions ()
252 : : {
253 : 12072 : return conditions;
254 : : }
255 : :
256 : :
257 : : /* Checks if sizes of arguments and destination are compatible. */
258 : :
259 : : bool
260 : 26249 : state::check_args_compatibility (tree arg1, tree arg2, tree dest)
261 : : {
262 : 26249 : if (!(get_var_size (arg1) == get_var_size (dest)
263 : 2 : || TREE_CODE (arg1) == INTEGER_CST)
264 : 26251 : || !(get_var_size (arg2) == get_var_size (dest)
265 : 24368 : || TREE_CODE (arg2) == INTEGER_CST))
266 : : {
267 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
268 : 0 : fprintf (dump_file, "Sym-Exec: Incompatible destination"
269 : : "and argument sizes.\n");
270 : :
271 : 0 : return false;
272 : : }
273 : :
274 : : return true;
275 : : }
276 : :
277 : :
278 : : /* Creates value for given constant tree. */
279 : :
280 : : value
281 : 43623 : state::create_val_for_const (tree var, size_t size)
282 : : {
283 : 43623 : unsigned HOST_WIDE_INT val = TYPE_UNSIGNED (TREE_TYPE (var))
284 : 43623 : ? tree_to_uhwi (var) : tree_to_shwi (var);
285 : 43623 : value result (size, TYPE_UNSIGNED (TREE_TYPE (var)));
286 : :
287 : 1553239 : for (size_t i = 0; i < size; i++)
288 : : {
289 : 1509616 : result.push (new bit (val & 1));
290 : 1509616 : val >>= 1;
291 : : }
292 : :
293 : 43623 : return result;
294 : : }
295 : :
296 : :
297 : : /* Adds the given variable to state. */
298 : :
299 : : bool
300 : 0 : state::add_var_state (tree var, value *vstate)
301 : : {
302 : 0 : size_t size = vstate->length ();
303 : 0 : value val (size, vstate->is_unsigned);
304 : 0 : for (size_t i = 0; i < size; i++)
305 : 0 : val.push ((*vstate)[i]->copy ());
306 : :
307 : 0 : return var_states.put (var, val);
308 : 0 : }
309 : :
310 : :
311 : : /* Adds the given condition to the state. */
312 : :
313 : : bool
314 : 0 : state::add_condition (bit_expression *cond)
315 : : {
316 : 0 : return conditions.add (as_a<bit_expression *> (cond->copy ()));
317 : : }
318 : :
319 : :
320 : : /* Bulk add the given conditions to the state. */
321 : :
322 : : bool
323 : 0 : state::bulk_add_conditions (const hash_set<bit_expression *> &conds)
324 : : {
325 : 0 : bool status = true;
326 : 0 : for (auto iter = conds.begin (); iter != conds.end (); ++iter)
327 : 0 : status &= add_condition (*iter);
328 : :
329 : 0 : return status;
330 : : }
331 : :
332 : :
333 : : /* Remove all states from the states' vector. */
334 : :
335 : : void
336 : 3752 : state::remove_states (vec<state *> *states)
337 : : {
338 : 10046 : while (!states->is_empty ())
339 : : {
340 : 6294 : delete states->last ();
341 : 6294 : states->pop ();
342 : : }
343 : 3752 : }
344 : :
345 : :
346 : : /* Remove all states from the states' vector and release the vector. */
347 : :
348 : : void
349 : 954 : state::clear_states (vec<state *> *states)
350 : : {
351 : 954 : remove_states (states);
352 : 954 : states->release ();
353 : 954 : }
354 : :
355 : :
356 : : /* Removes all variables added to the state. */
357 : :
358 : : void
359 : 0 : state::clear_var_states ()
360 : : {
361 : 0 : var_states.empty ();
362 : 0 : }
363 : :
364 : :
365 : : /* Removes all conditions added to the state. */
366 : :
367 : : void
368 : 12822 : state::clear_conditions ()
369 : : {
370 : 36974 : for (auto iter = conditions.begin (); iter != conditions.end (); ++iter)
371 : 12076 : delete (*iter);
372 : 12822 : conditions.empty ();
373 : 12822 : }
374 : :
375 : :
376 : : /* Performs AND operation for 2 symbolic_bit operands. */
377 : :
378 : : value_bit *
379 : 0 : state::and_sym_bits (const value_bit *var1, const value_bit *var2)
380 : : {
381 : 0 : return new bit_and_expression (var1->copy (), var2->copy ());
382 : : }
383 : :
384 : :
385 : : /* Performs AND operation for a symbolic_bit and const_bit operands. */
386 : :
387 : : value_bit *
388 : 55064 : state::and_var_const (const value_bit *var1, const bit *const_bit)
389 : : {
390 : 55064 : if (const_bit->get_val () == 1)
391 : 1667 : return var1->copy ();
392 : :
393 : 53397 : return new bit (0);
394 : : }
395 : :
396 : :
397 : : /* Performs AND operation for 2 constant bit operands. */
398 : :
399 : : bit *
400 : 1350320 : state::and_const_bits (const bit *const_bit1, const bit *const_bit2)
401 : : {
402 : 1350320 : if (const_bit1->get_val () == const_bit2->get_val ())
403 : 654562 : return new bit (*const_bit1);
404 : :
405 : 695758 : return new bit (0);
406 : : }
407 : :
408 : :
409 : : /* Performs OR operation for 2 symbolic_bit operands. */
410 : :
411 : : value_bit *
412 : 0 : state::or_sym_bits (const value_bit *var1, const value_bit *var2)
413 : : {
414 : 0 : return new bit_or_expression (var1->copy (), var2->copy ());
415 : : }
416 : :
417 : :
418 : : /* Performs OR operation for a symbolic_bit and a constant bit operands. */
419 : :
420 : : value_bit *
421 : 0 : state::or_var_const (const value_bit *var1, const bit *const_bit)
422 : : {
423 : 0 : if (const_bit->get_val () == 0)
424 : 0 : return var1->copy ();
425 : :
426 : 0 : return new bit (1);
427 : : }
428 : :
429 : :
430 : : /* Performs OR operation for 2 constant bit operands. */
431 : :
432 : : bit *
433 : 668592 : state::or_const_bits (const bit *const_bit1, const bit *const_bit2)
434 : : {
435 : 668592 : if (const_bit1->get_val () == const_bit2->get_val ())
436 : 445425 : return new bit (*const_bit1);
437 : :
438 : 223167 : return new bit (1);
439 : : }
440 : :
441 : :
442 : : /* Adds an empty state for the given variable. */
443 : :
444 : : bool
445 : 254 : state::decl_var (tree var, unsigned size)
446 : : {
447 : 254 : if (is_declared (var))
448 : : return false;
449 : :
450 : 254 : value val (size, TYPE_UNSIGNED (TREE_TYPE (var)));
451 : 5606 : for (unsigned i = 0; i < size; i++)
452 : 5352 : val.push (nullptr);
453 : :
454 : 254 : return var_states.put (var, val);
455 : 254 : }
456 : :
457 : :
458 : : /* Returns size of the given variable. */
459 : :
460 : : unsigned
461 : 327641 : state::get_var_size (tree var)
462 : : {
463 : 327641 : value *content = var_states.get (var);
464 : 327641 : if (content == NULL)
465 : : return 0;
466 : :
467 : 303271 : return content->allocated ();
468 : : }
469 : :
470 : :
471 : : /* Adds a variable with unknown value to state. Such variables are
472 : : represented as sequence of symbolic bits. */
473 : :
474 : : bool
475 : 46911 : state::make_symbolic (tree var, unsigned size)
476 : : {
477 : 46911 : if (is_declared (var))
478 : : return false;
479 : :
480 : 46911 : value val (size, TYPE_UNSIGNED (TREE_TYPE (var)));
481 : : /* Initialize each bit of a variable with unknown value. */
482 : 1651543 : for (size_t i = 0; i < size; i++)
483 : 1604632 : val.push (new symbolic_bit (i, var));
484 : :
485 : 46911 : return var_states.put (var, val);
486 : 46911 : }
487 : :
488 : :
489 : : /* Performs AND operation on two bits. */
490 : :
491 : : value_bit *
492 : 1405384 : state::and_two_bits (value_bit *arg1, value_bit *arg2)
493 : : {
494 : 1405384 : value_bit *result = nullptr;
495 : :
496 : 2755704 : if (is_a<bit *> (arg1) && is_a<bit *> (arg2))
497 : 1350320 : result = and_const_bits (as_a<bit *> (arg1), as_a<bit *> (arg2));
498 : :
499 : 55064 : else if (is_a<bit *> (arg1) && (is_a<symbolic_bit *> (arg2)
500 : 0 : || (is_a<bit_expression *> (arg2))))
501 : 0 : result = and_var_const (arg2, as_a<bit *> (arg1));
502 : :
503 : 55064 : else if ((is_a<symbolic_bit *> (arg1)
504 : 144079 : || (is_a<bit_expression *> (arg1))) && is_a<bit *> (arg2))
505 : 55064 : result = and_var_const (arg1, as_a<bit *> (arg2));
506 : :
507 : : else
508 : 0 : result = and_sym_bits (arg1, arg2);
509 : :
510 : 1405384 : return result;
511 : : }
512 : :
513 : :
514 : : /* A wrapper for operations on two bits.
515 : : Operation and operands are passed as arguments. */
516 : :
517 : : value_bit *
518 : 252680 : state::operate_bits (bit_func bit_op, value_bit *bit1, value_bit *bit2,
519 : : value_bit **)
520 : : {
521 : 252680 : return (bit_op) (bit1, bit2);
522 : : }
523 : :
524 : :
525 : : /* A wrapper for operations on three bits.
526 : : Operation and operands are passed as arguments. */
527 : :
528 : : value_bit *
529 : 445672 : state::operate_bits (bit_func3 bit_op, value_bit *bit1, value_bit *bit2,
530 : : value_bit **bit3)
531 : : {
532 : 445672 : return (bit_op) (bit1, bit2, bit3);
533 : : }
534 : :
535 : :
536 : : /* Does preprocessing and postprocessing for expressions with tree operands.
537 : : Handles value creation for constant and their removement in the end. */
538 : :
539 : : bool
540 : 26249 : state::do_binary_operation (tree arg1, tree arg2, tree dest,
541 : : binary_func bin_func)
542 : : {
543 : 26249 : declare_if_needed (dest, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest))));
544 : 26249 : declare_if_needed (arg1, var_states.get (dest)->allocated ());
545 : 26249 : declare_if_needed (arg2, var_states.get (dest)->allocated ());
546 : :
547 : 26249 : if (!check_args_compatibility (arg1, arg2, dest))
548 : : return false;
549 : :
550 : 26249 : size_t dest_size = var_states.get (dest)->length ();
551 : :
552 : 26249 : value *arg1_val = var_states.get (arg1);
553 : 26249 : value arg1_const_val (dest_size, false);
554 : 26249 : if (arg1_val == NULL && TREE_CODE (arg1) == INTEGER_CST)
555 : : {
556 : 2 : arg1_const_val = create_val_for_const (arg1, dest_size);
557 : 2 : arg1_val = &arg1_const_val;
558 : : }
559 : :
560 : 26249 : value *arg2_val = var_states.get (arg2);
561 : 26249 : value arg2_const_val (dest_size, false);
562 : 26249 : if (arg2_val == NULL && TREE_CODE (arg2) == INTEGER_CST)
563 : : {
564 : 24368 : arg2_const_val = create_val_for_const (arg2, dest_size);
565 : 24368 : arg2_val = &arg2_const_val;
566 : : }
567 : :
568 : 26249 : (this->*bin_func) (arg1_val, arg2_val, dest);
569 : 26249 : print_value (var_states.get (dest));
570 : 26249 : return true;
571 : 26249 : }
572 : :
573 : :
574 : : /* Performs AND operation on given values. The result is stored in dest. */
575 : :
576 : : void
577 : 1825 : state::do_and (value *arg1, value *arg2, tree dest)
578 : : {
579 : : /* Creating AND expressions for every bit pair of given arguments
580 : : and store them as a new state for given destination. */
581 : :
582 : 1825 : operate (arg1, arg2, nullptr, dest, &state::and_two_bits);
583 : 1825 : }
584 : :
585 : :
586 : : /* Performs OR operation on two bits. */
587 : :
588 : : value_bit *
589 : 668592 : state::or_two_bits (value_bit *arg1_bit, value_bit *arg2_bit)
590 : : {
591 : 668592 : value_bit *result = nullptr;
592 : :
593 : 1337184 : if (is_a<bit *> (arg1_bit) && is_a<bit *> (arg2_bit))
594 : 668592 : result = or_const_bits (as_a<bit *> (arg1_bit), as_a<bit *> (arg2_bit));
595 : :
596 : 0 : else if (is_a<bit *> (arg1_bit) && (is_a<symbolic_bit *> (arg2_bit)
597 : 0 : || is_a<bit_expression *> (arg2_bit)))
598 : 0 : result = or_var_const (arg2_bit, as_a<bit *> (arg1_bit));
599 : :
600 : 0 : else if ((is_a<symbolic_bit *> (arg1_bit)
601 : 0 : || is_a<bit_expression *> (arg1_bit))
602 : 0 : && is_a<bit *> (arg2_bit))
603 : 0 : result = or_var_const (arg1_bit, as_a<bit *> (arg2_bit));
604 : :
605 : : else
606 : 0 : result = or_sym_bits (arg1_bit, arg2_bit);
607 : :
608 : 668592 : return result;
609 : : }
610 : :
611 : :
612 : : /* Performs OR operation on given values. The result is stored in dest. */
613 : :
614 : : void
615 : 4 : state::do_or (value *arg1, value *arg2, tree dest)
616 : : {
617 : : /* Creating OR expressions for every bit pair of given arguments
618 : : and store them as a new state for given destination. */
619 : 4 : operate (arg1, arg2, nullptr, dest, &state::or_two_bits);
620 : 4 : }
621 : :
622 : :
623 : : /* Performs XOR operation on two bits. */
624 : :
625 : : value_bit *
626 : 1522853 : state::xor_two_bits (value_bit *arg1_bit, value_bit *arg2_bit)
627 : : {
628 : 1522853 : value_bit *result = nullptr;
629 : :
630 : 2886952 : if (is_a<bit *> (arg1_bit) && is_a<bit *> (arg2_bit))
631 : 1357555 : result = xor_const_bits (as_a<bit *> (arg1_bit), as_a<bit *> (arg2_bit));
632 : :
633 : 171842 : else if (is_a<bit *> (arg1_bit) && (is_a<symbolic_bit *> (arg2_bit)
634 : 0 : || is_a<bit_expression *> (arg2_bit)))
635 : 6544 : result = xor_var_const (arg2_bit, as_a<bit *> (arg1_bit));
636 : :
637 : 158754 : else if ((is_a<symbolic_bit *> (arg1_bit)
638 : 0 : || is_a<bit_expression *> (arg1_bit))
639 : 317508 : && is_a<bit *> (arg2_bit))
640 : 101061 : result = xor_var_const (arg1_bit, as_a<bit *> (arg2_bit));
641 : :
642 : : else
643 : 57693 : result = xor_sym_bits (arg1_bit, arg2_bit);
644 : :
645 : 1522853 : return result;
646 : : }
647 : :
648 : :
649 : : /* Performs XOR operation on given values. The result is stored in dest. */
650 : :
651 : : void
652 : 5118 : state::do_xor (value *arg1, value *arg2, tree dest)
653 : : {
654 : 5118 : operate (arg1, arg2, nullptr, dest, &state::xor_two_bits);
655 : 5118 : }
656 : :
657 : :
658 : : /* Shifts value right by size of shift_value. */
659 : :
660 : : value *
661 : 3042 : state::shift_right_by_const (value *var, size_t shift_value)
662 : : {
663 : 3042 : value *shift_result = new value (var->length (), var->is_unsigned);
664 : 3042 : if (var->length () <= shift_value)
665 : 66 : for (size_t i = 0; i < var->length (); i++)
666 : 64 : shift_result->push (new bit (0));
667 : : else
668 : : {
669 : : size_t i = 0;
670 : 92656 : for (; i < var->length () - shift_value; ++i)
671 : 89616 : shift_result->push (((*var)[shift_value + i])->copy ());
672 : :
673 : 13968 : for (; i < var->length (); ++i)
674 : 11432 : shift_result->push (var->is_unsigned ? new bit (0)
675 : 504 : : var->last ()->copy ());
676 : : }
677 : 3042 : return shift_result;
678 : : }
679 : :
680 : :
681 : : /* Checks if all bits of the given value have constant bit type. */
682 : :
683 : : bool
684 : 39628 : state::is_bit_vector (const value *var)
685 : : {
686 : 39628 : if (var == nullptr || !var->exists ())
687 : 0 : return false;
688 : :
689 : 1481996 : for (size_t i = 0; i < var->length (); i++)
690 : 1448406 : if (!(is_a<bit *> ((*var)[i])))
691 : : return false;
692 : : return true;
693 : : }
694 : :
695 : :
696 : : /* Returns the number represented by the value. */
697 : :
698 : : unsigned HOST_WIDE_INT
699 : 15009 : state::make_number (const value *var)
700 : : {
701 : 15009 : unsigned HOST_WIDE_INT
702 : 15009 : number = 0;
703 : 15009 : int value_size = var->length ();
704 : 605113 : for (int i = value_size - 1; i >= 0; i--)
705 : : {
706 : 590104 : if (is_a<bit *> ((*var)[i]))
707 : 590104 : number = (number << 1) | as_a<bit *> ((*var)[i])->get_val ();
708 : : else
709 : : return 0;
710 : : }
711 : : return number;
712 : : }
713 : :
714 : :
715 : : /* Shift_left operation. Case: var2 is a symbolic value. */
716 : :
717 : : value_bit *
718 : 0 : state::shift_left_sym_bits (value_bit *var1, value_bit *var2)
719 : : {
720 : 0 : return new shift_left_expression (var1->copy (), var2->copy ());
721 : : }
722 : :
723 : :
724 : : /* Performs shift left operation on given values.
725 : : The result is stored in dest. */
726 : :
727 : : void
728 : 3643 : state::do_shift_left (value *arg1, value *arg2, tree dest)
729 : : {
730 : 3643 : if (is_bit_vector (arg2))
731 : : {
732 : 3643 : size_t shift_value = make_number (arg2);
733 : 3643 : value *result = shift_left_by_const (arg1, shift_value);
734 : 118995 : for (size_t i = 0; i < get_var_size (dest); i++)
735 : : {
736 : 115352 : delete (*var_states.get (dest))[i];
737 : 115352 : (*var_states.get (dest))[i] = (*result)[i]->copy ();
738 : : }
739 : 3643 : delete result;
740 : : }
741 : : else
742 : 0 : operate (arg1, arg2, nullptr, dest, &state::shift_left_sym_bits);
743 : 3643 : }
744 : :
745 : :
746 : : /* Performs shift right operation on given values.
747 : : The result is stored in dest. */
748 : :
749 : : void
750 : 3042 : state::do_shift_right (value *arg1, value *arg2, tree dest)
751 : : {
752 : 3042 : if (is_bit_vector (arg2))
753 : : {
754 : 3042 : size_t shift_value = make_number (arg2);
755 : 3042 : value *result = shift_right_by_const (arg1, shift_value);
756 : 103650 : for (size_t i = 0; i < get_var_size (dest); i++)
757 : : {
758 : 100608 : delete (*var_states.get (dest))[i];
759 : 100608 : (*var_states.get (dest))[i] = (*result)[i]->copy ();
760 : : }
761 : :
762 : 3042 : delete result;
763 : : }
764 : : else
765 : 0 : operate (arg1, arg2, nullptr, dest, &state::shift_right_sym_bits);
766 : 3042 : }
767 : :
768 : :
769 : : /* Adds two bits and carry value.
770 : : Resturn result and stores new carry bit in "carry". */
771 : :
772 : : value_bit *
773 : 668488 : state::full_adder (value_bit *var1, value_bit *var2, value_bit **carry)
774 : : {
775 : 668488 : value_bit *new_carry = and_two_bits (var1, var2);
776 : 668488 : value_bit *sum = xor_two_bits (var1, var2);
777 : :
778 : 668488 : value_bit *result = xor_two_bits (sum, *carry);
779 : 668488 : value_bit *sum_and_carry = and_two_bits (sum, *carry);
780 : :
781 : 668488 : delete *carry;
782 : 668488 : delete sum;
783 : :
784 : 668488 : *carry = or_two_bits (sum_and_carry, new_carry);
785 : :
786 : 668488 : delete sum_and_carry;
787 : 668488 : delete new_carry;
788 : :
789 : 668488 : return result;
790 : : }
791 : :
792 : :
793 : : /* Adds given values. The result is stored in dest. */
794 : :
795 : : void
796 : 12611 : state::do_add (value *arg1, value *arg2, tree dest)
797 : : {
798 : 12611 : value_bit *carry = new bit (0);
799 : 12611 : operate (arg1, arg2, &carry, dest, &state::full_adder);
800 : 12611 : delete carry;
801 : 12611 : }
802 : :
803 : :
804 : : /* Returns the additive inverse of the given number. */
805 : :
806 : : value *
807 : 6285 : state::additive_inverse (const value *number)
808 : : {
809 : 6285 : value *result = new value (number->length (), number->is_unsigned);
810 : 6285 : value one (number->length (), number->is_unsigned);
811 : :
812 : 6285 : size_t size = number->length ();
813 : 6285 : one.push (new bit (1));
814 : 6285 : result->push (complement_a_bit ((*number)[0]));
815 : :
816 : 222624 : for (size_t i = 1; i < size; i++)
817 : : {
818 : 216339 : one.push (new bit (0));
819 : 216339 : result->push (complement_a_bit ((*number)[i]));
820 : : }
821 : :
822 : 6285 : value_bit *carry = new bit (0);
823 : 228909 : for (size_t i = 0; i < size; ++i)
824 : : {
825 : 222624 : value_bit *cur_bit = (*result)[i];
826 : 222624 : (*result)[i] = full_adder (cur_bit, one[i], &carry);
827 : 222624 : delete cur_bit;
828 : : }
829 : :
830 : 6285 : delete carry;
831 : 12570 : return result;
832 : 6285 : }
833 : :
834 : :
835 : : /* Subtracks second value from the first. The result is stored in dest. */
836 : :
837 : : void
838 : 6285 : state::do_sub (value *arg1, value *arg2, tree dest)
839 : : {
840 : 6285 : value *neg_arg2 = additive_inverse (arg2);
841 : 6285 : do_add (arg1, neg_arg2, dest);
842 : 6285 : delete neg_arg2;
843 : 6285 : }
844 : :
845 : :
846 : : /* Performs complement operation on a bit. */
847 : :
848 : : value_bit *
849 : 222624 : state::complement_a_bit (value_bit *var)
850 : : {
851 : 222624 : value_bit *result = nullptr;
852 : 222624 : if (is_a<bit *> (var))
853 : 222624 : result = complement_const_bit (as_a<bit *> (var));
854 : : else
855 : 0 : result = complement_sym_bit (var);
856 : :
857 : 222624 : return result;
858 : : }
859 : :
860 : :
861 : : /* Negates given variable. */
862 : :
863 : : bool
864 : 0 : state::do_complement (tree arg, tree dest)
865 : : {
866 : 0 : declare_if_needed (dest, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest))));
867 : 0 : declare_if_needed (arg, var_states.get (dest)->allocated ());
868 : :
869 : : /* Creating complement expressions for every bit the given argument
870 : : and store it as a new state for given destination. */
871 : 0 : size_t iter_count = min (get_var_size (dest), get_var_size (arg),
872 : 0 : get_var_size (arg));
873 : :
874 : 0 : size_t i = 0;
875 : 0 : for (; i < iter_count; i++)
876 : : {
877 : 0 : value_bit *result = complement_a_bit ((*var_states.get (arg))[i]);
878 : 0 : delete (*var_states.get (dest))[i];
879 : 0 : (*var_states.get (dest))[i] = result;
880 : : }
881 : :
882 : 0 : if (i >= get_var_size (dest))
883 : : {
884 : 0 : print_value (var_states.get (dest));
885 : 0 : return true;
886 : : }
887 : :
888 : 0 : for (; i < get_var_size (dest); i++)
889 : : {
890 : 0 : delete (*var_states.get (dest))[i];
891 : 0 : bit tmp (0);
892 : 0 : (*var_states.get (dest))[i] = complement_a_bit (&tmp);
893 : 0 : }
894 : :
895 : 0 : print_value (var_states.get (dest));
896 : 0 : return true;
897 : : }
898 : :
899 : :
900 : : /* Does Assignment. */
901 : :
902 : : bool
903 : 15897 : state::do_assign (tree arg, tree dest)
904 : : {
905 : 15897 : declare_if_needed (dest, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest))));
906 : 15897 : if (TREE_CODE (arg) != INTEGER_CST)
907 : 9210 : declare_if_needed (arg, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (arg))));
908 : : else
909 : 6687 : declare_if_needed (arg, var_states.get (dest)->allocated ());
910 : :
911 : 15897 : value *dest_val = var_states.get (dest);
912 : :
913 : : /* If the argument is already defined, then we must just copy its bits. */
914 : 15897 : if (auto arg_val = var_states.get (arg))
915 : : {
916 : 305010 : for (size_t i = 0; i < dest_val->length (); i++)
917 : : {
918 : 295800 : value_bit *new_val = nullptr;
919 : 295800 : if (i < arg_val->length ())
920 : 275632 : new_val = (*arg_val)[i]->copy ();
921 : : else
922 : 20168 : new_val = new bit (0);
923 : :
924 : 295800 : delete (*dest_val)[i];
925 : 295800 : (*dest_val)[i] = new_val;
926 : : }
927 : : }
928 : : /* If the argument is a constant, we must save it as sequence of bits. */
929 : 6687 : else if (TREE_CODE (arg) == INTEGER_CST)
930 : : {
931 : 6687 : value arg_val
932 : 6687 : = create_val_for_const (arg, dest_val->length ());
933 : 240583 : for (size_t i = 0; i < dest_val->length (); i++)
934 : : {
935 : 233896 : delete (*dest_val)[i];
936 : 233896 : (*dest_val)[i] = arg_val[i]->copy ();
937 : : }
938 : 6687 : }
939 : : else
940 : : {
941 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
942 : 0 : fprintf (dump_file, "Sym-Exec: Unsupported assignment"
943 : : " for given argument.\n");
944 : :
945 : 0 : return false;
946 : : }
947 : :
948 : 15897 : print_value (var_states.get (dest));
949 : 15897 : return true;
950 : : }
951 : :
952 : :
953 : : /* Assigns pow 2 value. */
954 : :
955 : : bool
956 : 254 : state::do_assign_pow2 (tree dest, unsigned pow)
957 : : {
958 : 254 : value *dest_val = var_states.get (dest);
959 : 0 : unsigned dest_size = dest_val ? dest_val->allocated ()
960 : 254 : : tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest)));
961 : 254 : if (pow > dest_size)
962 : : {
963 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
964 : 0 : fprintf (dump_file, "Sym-Exec: pow %u of 2 won't fit in"
965 : : " specified destination\n", pow);
966 : 0 : return false;
967 : : }
968 : :
969 : 254 : if (!dest_val)
970 : : {
971 : 254 : decl_var (dest, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest))));
972 : 254 : dest_val = var_states.get (dest);
973 : : }
974 : : else
975 : 0 : dest_val->free_bits ();
976 : :
977 : 5606 : for (unsigned i = 0; i < dest_val->length (); i++)
978 : : {
979 : 5352 : if (i == pow)
980 : 254 : (*dest_val)[i] = new bit (1);
981 : : else
982 : 5098 : (*dest_val)[i] = new bit (0);
983 : : }
984 : :
985 : 254 : print_value (dest_val);
986 : 254 : return true;
987 : : }
988 : :
989 : :
990 : : /* Performs NOT operation for constant bit. */
991 : :
992 : : bit *
993 : 222624 : state::complement_const_bit (const bit *const_bit)
994 : : {
995 : 222624 : return new bit (1u ^ const_bit->get_val ());
996 : : }
997 : :
998 : :
999 : : /* Performs NOT operation for symbolic_bit. */
1000 : :
1001 : : value_bit *
1002 : 0 : state::complement_sym_bit (const value_bit *var)
1003 : : {
1004 : 0 : return new bit_complement_expression (var->copy ());
1005 : : }
1006 : :
1007 : :
1008 : : /* Performs XOR operation for 2 symbolic_bit operands. */
1009 : :
1010 : : value_bit *
1011 : 57693 : state::xor_sym_bits (const value_bit *var1, const value_bit *var2)
1012 : : {
1013 : 57693 : value_bit *var2_copy = var2->copy ();
1014 : 57693 : bit_expression *node2_with_const_child = nullptr;
1015 : 57693 : bit_expression *parent_of_node2_with_child = nullptr;
1016 : 57693 : get_parent_with_const_child (var2_copy, node2_with_const_child,
1017 : : parent_of_node2_with_child);
1018 : :
1019 : 57693 : if (node2_with_const_child != nullptr)
1020 : : {
1021 : 0 : value_bit *var1_copy = var1->copy ();
1022 : 0 : bit_expression *node1_with_const_child = nullptr;
1023 : 0 : bit_expression *parent_of_node1_with_child = nullptr;
1024 : 0 : get_parent_with_const_child (var1_copy, node1_with_const_child,
1025 : : parent_of_node1_with_child);
1026 : :
1027 : : /* If both subtrees have constant bit nodes,
1028 : : we can merge them together. */
1029 : 0 : if (node1_with_const_child != nullptr)
1030 : : {
1031 : 0 : value_bit *var1_reformed = nullptr;
1032 : 0 : value_bit *var2_reformed = nullptr;
1033 : :
1034 : : /* If var1's const bit is in its left subtree. */
1035 : 0 : value_bit *var1_left = node1_with_const_child->get_left ();
1036 : 0 : if (var1_left != nullptr && is_a<bit *> (var1_left))
1037 : : {
1038 : 0 : var1_reformed = node1_with_const_child->get_right ()->copy ();
1039 : 0 : value_bit *var2_left = node2_with_const_child->get_left ();
1040 : :
1041 : : /* If var2's const bit is in its left subtree. */
1042 : 0 : if (var2_left != nullptr && is_a<bit *> (var2_left))
1043 : 0 : var2_reformed = node2_with_const_child->get_right ()->copy ();
1044 : : else /* Var2's const bit is in its right subtree. */
1045 : 0 : var2_reformed = node2_with_const_child->get_left ()->copy ();
1046 : : }
1047 : : else /* Var1's const bit is in its right subtree. */
1048 : : {
1049 : 0 : var1_reformed = node1_with_const_child->get_left ()->copy ();
1050 : 0 : value_bit *var2_left = node2_with_const_child->get_left ();
1051 : :
1052 : : /* If var2's const bit is in its left subtree. */
1053 : 0 : if (var2_left != nullptr && is_a<bit *> (var2_left))
1054 : 0 : var2_reformed = node2_with_const_child->get_right ()->copy ();
1055 : : else /* Var2's const bit is in its right subtree. */
1056 : 0 : var2_reformed = node2_with_const_child->get_left ()->copy ();
1057 : : }
1058 : :
1059 : 0 : if (parent_of_node1_with_child)
1060 : : {
1061 : 0 : parent_of_node1_with_child->get_left ()
1062 : 0 : == node1_with_const_child
1063 : 0 : ? parent_of_node1_with_child->set_left (var1_reformed)
1064 : 0 : : parent_of_node1_with_child->set_right (var1_reformed);
1065 : 0 : delete node1_with_const_child;
1066 : : }
1067 : : else
1068 : : {
1069 : 0 : delete var1_copy;
1070 : : var1_copy = var1_reformed;
1071 : : }
1072 : :
1073 : 0 : if (parent_of_node2_with_child)
1074 : : {
1075 : 0 : parent_of_node2_with_child->get_left ()
1076 : 0 : == node2_with_const_child
1077 : 0 : ? parent_of_node2_with_child->set_left (var2_reformed)
1078 : 0 : : parent_of_node2_with_child->set_right (var2_reformed);
1079 : 0 : delete node2_with_const_child;
1080 : : }
1081 : : else
1082 : : {
1083 : 0 : delete var2_copy;
1084 : : var2_copy = var2_reformed;
1085 : : }
1086 : :
1087 : 0 : return new bit_xor_expression (var1_copy, var2_copy);
1088 : : }
1089 : 0 : delete var1_copy;
1090 : : }
1091 : :
1092 : 57693 : delete var2_copy;
1093 : 57693 : return new bit_xor_expression (var1->copy (), var2->copy ());
1094 : : }
1095 : :
1096 : :
1097 : : /* Performs XOR operation for 2 constant bit operands. */
1098 : :
1099 : : bit *
1100 : 1357555 : state::xor_const_bits (const bit *const_bit1, const bit *const_bit2)
1101 : : {
1102 : 1357555 : return new bit (const_bit1->get_val () ^ const_bit2->get_val ());
1103 : : }
1104 : :
1105 : :
1106 : : /* Performs XOR operation for a symbolic_bit and const_bit operands. */
1107 : :
1108 : : value_bit *
1109 : 107605 : state::xor_var_const (const value_bit *var, const bit *const_bit)
1110 : : {
1111 : 107605 : if (const_bit->get_val () == 0)
1112 : 72528 : return var->copy ();
1113 : :
1114 : 35077 : value_bit *var_copy = var->copy ();
1115 : 35077 : bit_expression *node_with_const_child = nullptr;
1116 : 35077 : bit_expression *tmp = nullptr;
1117 : 35077 : get_parent_with_const_child (var_copy, node_with_const_child, tmp);
1118 : :
1119 : 35077 : if (node_with_const_child != nullptr)
1120 : : {
1121 : 0 : value_bit *left = node_with_const_child->get_left ();
1122 : 0 : if (left != nullptr && is_a<bit *> (left))
1123 : : {
1124 : 0 : bit *new_left = xor_const_bits (as_a<bit *> (left), const_bit);
1125 : 0 : delete left;
1126 : 0 : node_with_const_child->set_left (new_left);
1127 : : }
1128 : : else
1129 : : {
1130 : 0 : value_bit *right = node_with_const_child->get_right ();
1131 : 0 : bit *new_right = xor_const_bits (as_a<bit *> (right), const_bit);
1132 : 0 : delete right;
1133 : 0 : node_with_const_child->set_right (new_right);
1134 : : }
1135 : 0 : return var_copy;
1136 : : }
1137 : :
1138 : 35077 : delete var_copy;
1139 : 35077 : return new bit_xor_expression (var->copy (), const_bit->copy ());
1140 : : }
1141 : :
1142 : :
1143 : : /* Return node which has a const bit child. Traversal is done based
1144 : : on safe branching. */
1145 : :
1146 : : void
1147 : 92770 : state::get_parent_with_const_child (value_bit *root, bit_expression *&parent,
1148 : : bit_expression *&parent_of_parent)
1149 : : {
1150 : 92770 : parent_of_parent = nullptr;
1151 : 92770 : parent = nullptr;
1152 : :
1153 : 92770 : if (!is_a<bit_expression *> (root))
1154 : 92770 : return;
1155 : :
1156 : 0 : bit_expression *expr_root = as_a<bit_expression *> (root);
1157 : 0 : hash_set < bit_expression * > nodes_to_consider;
1158 : 0 : nodes_to_consider.add (expr_root);
1159 : :
1160 : 0 : hash_map < bit_expression * , bit_expression * > node_to_parent;
1161 : 0 : node_to_parent.put (expr_root, nullptr);
1162 : :
1163 : : /* Traversing expression tree:
1164 : : considering only comutative expression nodes. */
1165 : 0 : while (!nodes_to_consider.is_empty ())
1166 : : {
1167 : 0 : bit_expression *cur_element = *nodes_to_consider.begin ();
1168 : 0 : nodes_to_consider.remove (cur_element);
1169 : :
1170 : 0 : value_bit *left = cur_element->get_left ();
1171 : 0 : value_bit *right = cur_element->get_right ();
1172 : :
1173 : 0 : if ((left != nullptr && is_a<bit *> (left))
1174 : 0 : || (right != nullptr && is_a<bit *> (right)))
1175 : : {
1176 : 0 : parent = cur_element;
1177 : 0 : parent_of_parent = *node_to_parent.get (cur_element);
1178 : : }
1179 : :
1180 : 0 : if (left != nullptr && is_a<bit_xor_expression *> (left))
1181 : : {
1182 : 0 : nodes_to_consider.add (as_a<bit_expression *> (left));
1183 : 0 : node_to_parent.put (as_a<bit_expression *> (left), cur_element);
1184 : : }
1185 : :
1186 : 0 : if (right != nullptr && is_a<bit_xor_expression *> (right))
1187 : : {
1188 : 0 : nodes_to_consider.add (as_a<bit_expression *> (right));
1189 : 0 : node_to_parent.put (as_a<bit_expression *> (right), cur_element);
1190 : : }
1191 : : }
1192 : 0 : }
1193 : :
1194 : :
1195 : : /* Shifts number left by size of shift_value. */
1196 : :
1197 : : value *
1198 : 3835 : state::shift_left_by_const (const value *number, size_t shift_value)
1199 : : {
1200 : 3835 : value *shift_result = new value (number->length (), number->is_unsigned);
1201 : 3835 : if (number->length () <= shift_value)
1202 : 0 : for (size_t i = 0; i < number->length (); i++)
1203 : 0 : shift_result->push (new bit (0));
1204 : :
1205 : : else
1206 : : {
1207 : : size_t i = 0;
1208 : 7670 : for (; i < shift_value; ++i)
1209 : 3835 : shift_result->push (new bit (0));
1210 : 121496 : for (size_t j = 0; i < number->length (); ++i, j++)
1211 : 117661 : shift_result->push (((*number)[j])->copy ());
1212 : : }
1213 : 3835 : return shift_result;
1214 : : }
1215 : :
1216 : :
1217 : : /* Shift_right operation. Case: var2 is a symbolic value. */
1218 : :
1219 : : value_bit *
1220 : 0 : state::shift_right_sym_bits (value_bit *var1, value_bit *var2)
1221 : : {
1222 : 0 : return new shift_right_expression (var1->copy (), var2->copy ());
1223 : : }
1224 : :
1225 : :
1226 : : /* Adds two values, stores the result in the first one. */
1227 : :
1228 : : void
1229 : 6 : state::add_numbers (value *var1, const value *var2)
1230 : : {
1231 : 6 : value_bit *carry = new bit (0);
1232 : 198 : for (unsigned i = 0; i < var1->length (); i++)
1233 : : {
1234 : 192 : value_bit *temp = (*var1)[i];
1235 : 192 : (*var1)[i] = full_adder ((*var1)[i], (*var2)[i], &carry);
1236 : 192 : delete temp;
1237 : : }
1238 : 6 : delete carry;
1239 : 6 : }
1240 : :
1241 : :
1242 : : /* ANDs every bit of the vector with var_bit, stroes the result in var1. */
1243 : :
1244 : : void
1245 : 0 : state::and_number_bit (value *var1, value_bit *var_bit)
1246 : : {
1247 : 0 : for (unsigned i = 0; i < var1->length (); i++)
1248 : : {
1249 : 0 : value_bit *tmp = (*var1)[i];
1250 : 0 : (*var1)[i] = and_two_bits ((*var1)[i], var_bit);
1251 : 0 : delete tmp;
1252 : : }
1253 : :
1254 : 0 : }
1255 : :
1256 : :
1257 : : /* Multiplies given values. The result is stored in dest. */
1258 : :
1259 : : void
1260 : 6 : state::do_mul (value *arg1, value *arg2, tree dest)
1261 : : {
1262 : 6 : value *shifted = new value (*arg1);
1263 : 6 : value *dest_val = var_states.get (dest);
1264 : :
1265 : 198 : for (unsigned i = 0; i < dest_val->length (); i++)
1266 : : {
1267 : 192 : delete (*dest_val)[i];
1268 : 192 : (*dest_val)[i] = new bit (0);
1269 : : }
1270 : :
1271 : 198 : for (unsigned i = arg2->length (); i != 0; --i)
1272 : : {
1273 : 192 : if (is_a<bit *> ((*arg2)[i - 1])
1274 : 192 : && as_a<bit *> ((*arg2)[i - 1])->get_val () != 0)
1275 : 6 : add_numbers (dest_val, shifted);
1276 : 186 : else if (is_a<symbolic_bit *> ((*arg2)[i - 1]))
1277 : : {
1278 : 0 : and_number_bit (shifted, as_a<symbolic_bit *> ((*arg2)[i - 1]));
1279 : 0 : add_numbers (dest_val, shifted);
1280 : : }
1281 : :
1282 : 192 : value *temp = shifted;
1283 : 192 : shifted = shift_left_by_const (shifted, 1);
1284 : 192 : delete temp;
1285 : : }
1286 : 6 : delete shifted;
1287 : 6 : }
1288 : :
1289 : :
1290 : : /* Checks whether the given two constant values are equal. */
1291 : :
1292 : : bool
1293 : 5611 : state::check_const_value_equality (value *arg1, value *arg2)
1294 : : {
1295 : 206059 : for (size_t i = 0; i < arg1->length (); i++)
1296 : 400898 : if (as_a<bit *> ((*arg1)[i])->get_val ()
1297 : 200449 : != as_a<bit *> ((*arg2)[i])->get_val ())
1298 : : return false;
1299 : : return true;
1300 : : }
1301 : :
1302 : :
1303 : : /* Adds EQUAL condition of given variables to state. */
1304 : :
1305 : : bool
1306 : 1748 : state::add_equal_cond (tree arg1, tree arg2)
1307 : : {
1308 : 1748 : return add_binary_cond (arg1, arg2, &state::add_equal_cond);
1309 : : }
1310 : :
1311 : :
1312 : : /* Adds equality condition for two values. */
1313 : :
1314 : : void
1315 : 1748 : state::add_equal_cond (value *arg1, value *arg2)
1316 : : {
1317 : :
1318 : : /* If both arguments are constants then we can evaluate it. */
1319 : 1748 : if (is_bit_vector (arg1) && is_bit_vector (arg2))
1320 : : {
1321 : 1 : bool result = check_const_value_equality (arg1, arg2);
1322 : 1 : last_cond_status = result ? condition_status::CS_TRUE
1323 : : : condition_status::CS_FALSE;
1324 : 1 : return;
1325 : : }
1326 : :
1327 : : /* When some of bits are constants and they differ by value,
1328 : : then we can evalate it to be false. */
1329 : 66795 : for (size_t i = 0; i < arg1->length (); i++)
1330 : : {
1331 : 128349 : if (is_a<bit *> ((*arg1)[i]) && is_a<bit *> ((*arg2)[i])
1332 : 191650 : && as_a<bit *> ((*arg1)[i])->get_val ()
1333 : 63301 : != as_a<bit *> ((*arg2)[i])->get_val ())
1334 : : {
1335 : 0 : last_cond_status = condition_status::CS_FALSE;
1336 : 0 : return;
1337 : : }
1338 : : }
1339 : :
1340 : 66795 : for (size_t i = 0; i < arg1->length (); i++)
1341 : : {
1342 : : /* If there is a constant bit pair, then they are equal
1343 : : as we checked not equality above. */
1344 : 65048 : if (is_a<bit *> ((*arg1)[i]) && is_a<bit *> ((*arg2)[i]))
1345 : 63301 : continue;
1346 : :
1347 : 3494 : conditions.add (new bit_condition ((*arg1)[i]->copy (),
1348 : 1747 : (*arg2)[i]->copy (),
1349 : 5241 : EQ_EXPR));
1350 : : }
1351 : 1747 : last_cond_status = condition_status::CS_SYM;
1352 : : }
1353 : :
1354 : :
1355 : : /* Checks whether the given two constant values are not equal. */
1356 : :
1357 : : bool
1358 : 6442 : state::check_const_value_are_not_equal (value *arg1, value *arg2)
1359 : : {
1360 : 25572 : for (size_t i = 0; i < arg1->length (); i++)
1361 : 50242 : if (as_a<bit *> ((*arg1)[i])->get_val ()
1362 : 25121 : != as_a<bit *> ((*arg2)[i])->get_val ())
1363 : : return true;
1364 : : return false;
1365 : : }
1366 : :
1367 : :
1368 : : /* Adds NOT EQUAL condition of given variables to state. */
1369 : :
1370 : : bool
1371 : 8189 : state::add_not_equal_cond (tree arg1, tree arg2)
1372 : : {
1373 : 8189 : return add_binary_cond (arg1, arg2, &state::add_not_equal_cond);
1374 : : }
1375 : :
1376 : :
1377 : : /* Adds not equal condition for two values. */
1378 : :
1379 : : void
1380 : 8189 : state::add_not_equal_cond (value *arg1, value *arg2)
1381 : : {
1382 : 8189 : if (is_bit_vector (arg1) && is_bit_vector (arg2))
1383 : : {
1384 : 6442 : bool result = check_const_value_are_not_equal (arg1, arg2);
1385 : 6442 : last_cond_status = result ? condition_status::CS_TRUE
1386 : : : condition_status::CS_FALSE;
1387 : 6442 : return;
1388 : : }
1389 : :
1390 : : /* When some of bits are constants and they differ by value,
1391 : : then we can evalate it to be true. */
1392 : 66795 : for (size_t i = 0; i < arg1->length (); i++)
1393 : : {
1394 : 128349 : if (is_a<bit *> ((*arg1)[i]) && is_a<bit *> ((*arg2)[i])
1395 : 191650 : && as_a<bit *> ((*arg1)[i])->get_val ()
1396 : 63301 : != as_a<bit *> ((*arg2)[i])->get_val ())
1397 : : {
1398 : 0 : last_cond_status = condition_status::CS_TRUE;
1399 : 0 : return;
1400 : : }
1401 : : }
1402 : :
1403 : 1747 : bit_expression *prev = nullptr;
1404 : 66795 : for (size_t i = 0; i < arg1->length (); i++)
1405 : : {
1406 : : /* If there is a constant bit pair, then they are equal
1407 : : as we checked not equality above. */
1408 : 65048 : if (is_a<bit *> ((*arg1)[i]) && is_a<bit *> ((*arg2)[i]))
1409 : 63301 : continue;
1410 : :
1411 : 1747 : bit_condition *new_cond = new bit_condition ((*arg1)[i]->copy (),
1412 : 1747 : (*arg2)[i]->copy (),
1413 : 5241 : NE_EXPR);
1414 : 1747 : if (prev)
1415 : 0 : prev = new bit_or_expression (prev, new_cond);
1416 : : else
1417 : 1747 : prev = new_cond;
1418 : : }
1419 : :
1420 : 1747 : last_cond_status = condition_status::CS_SYM;
1421 : 1747 : conditions.add (prev);
1422 : : }
1423 : :
1424 : :
1425 : : /* Checks whether the first given constant value
1426 : : is greater than the second one. */
1427 : :
1428 : : bool
1429 : 0 : state::check_const_value_is_greater_than (value *arg1, value *arg2)
1430 : : {
1431 : 0 : for (int i = arg1->length () - 1; i >= 0; i--)
1432 : : {
1433 : 0 : if (as_a<bit *> ((*arg1)[i])->get_val ()
1434 : 0 : > as_a<bit *> ((*arg2)[i])->get_val ())
1435 : : return true;
1436 : 0 : else if (as_a<bit *> ((*arg1)[i])->get_val ()
1437 : 0 : < as_a<bit *> ((*arg2)[i])->get_val ())
1438 : : return false;
1439 : : }
1440 : : return false;
1441 : : }
1442 : :
1443 : :
1444 : : /* Adds GREATER THAN condition of given variables to state. */
1445 : :
1446 : : bool
1447 : 0 : state::add_greater_than_cond (tree arg1, tree arg2)
1448 : : {
1449 : 0 : return add_binary_cond (arg1, arg2, &state::add_greater_than_cond);
1450 : : }
1451 : :
1452 : :
1453 : : /* Adds greater than condition for two values. */
1454 : :
1455 : : void
1456 : 0 : state::add_greater_than_cond (value *arg1, value *arg2)
1457 : : {
1458 : 0 : if (is_bit_vector (arg1) && is_bit_vector (arg2))
1459 : : {
1460 : 0 : bool result = check_const_value_is_greater_than (arg1, arg2);
1461 : 0 : last_cond_status = result ? condition_status::CS_TRUE
1462 : : : condition_status::CS_FALSE;
1463 : 0 : return;
1464 : : }
1465 : :
1466 : 0 : if (is_bit_vector (arg2) && is_a<bit *> (arg1->last ())
1467 : 0 : && make_number (arg2) == 0 && !arg1->is_unsigned)
1468 : : {
1469 : 0 : if (as_a<bit *> (arg1->last ())->get_val () == 1)
1470 : 0 : last_cond_status = condition_status::CS_FALSE;
1471 : : else
1472 : : {
1473 : 0 : for (size_t i = 0; i < arg1->length (); i++)
1474 : 0 : if (is_a<bit *> ((*arg1)[i])
1475 : 0 : && as_a<bit *> ((*arg1)[i])->get_val ())
1476 : : {
1477 : 0 : last_cond_status = condition_status::CS_TRUE;
1478 : 0 : return;
1479 : : }
1480 : : }
1481 : : }
1482 : :
1483 : 0 : bit_expression *gt_cond = construct_great_than_cond (arg1, arg2);
1484 : 0 : if (gt_cond)
1485 : : {
1486 : : /* Otherwise its status is already set. */
1487 : 0 : last_cond_status = condition_status::CS_SYM;
1488 : 0 : conditions.add (gt_cond);
1489 : : }
1490 : : }
1491 : :
1492 : :
1493 : : /* Constructs expression trees of greater than condition for given values. */
1494 : :
1495 : : bit_expression *
1496 : 0 : state::construct_great_than_cond (value *arg1, value *arg2)
1497 : : {
1498 : 0 : bit_expression *prev = nullptr;
1499 : 0 : int i = arg1->length () - 1;
1500 : 0 : for (; i >= 0; i--)
1501 : : {
1502 : 0 : if (is_a<bit *> ((*arg1)[i]) && is_a<bit *> ((*arg2)[i]))
1503 : : {
1504 : 0 : if (as_a<bit *> ((*arg1)[i])->get_val ()
1505 : 0 : > as_a<bit *> ((*arg2)[i])->get_val ())
1506 : : {
1507 : 0 : if (!prev)
1508 : 0 : last_cond_status = condition_status::CS_TRUE;
1509 : 0 : return prev;
1510 : : }
1511 : 0 : else if (as_a<bit *> ((*arg1)[i])->get_val ()
1512 : 0 : < as_a<bit *> ((*arg2)[i])->get_val ())
1513 : : {
1514 : 0 : if (prev)
1515 : : {
1516 : 0 : bit_expression *ret_val
1517 : 0 : = as_a<bit_expression *> (prev->get_left ()->copy ());
1518 : 0 : delete prev;
1519 : 0 : return ret_val;
1520 : : }
1521 : : else
1522 : : {
1523 : 0 : last_cond_status = condition_status::CS_FALSE;
1524 : 0 : return nullptr;
1525 : : }
1526 : : }
1527 : : }
1528 : : else
1529 : : {
1530 : 0 : bit_condition *gt_cond
1531 : 0 : = new bit_condition ((*arg1)[i]->copy (), (*arg2)[i]->copy (),
1532 : 0 : GT_EXPR);
1533 : 0 : bit_expression *expr = nullptr;
1534 : 0 : if (i)
1535 : : {
1536 : 0 : bit_condition *eq_cond
1537 : 0 : = new bit_condition ((*arg1)[i]->copy (), (*arg2)[i]->copy (),
1538 : 0 : EQ_EXPR);
1539 : 0 : expr = new bit_or_expression (gt_cond, eq_cond);
1540 : : }
1541 : : else
1542 : : expr = gt_cond;
1543 : :
1544 : 0 : if (prev)
1545 : 0 : prev = new bit_and_expression (expr, prev);
1546 : : else
1547 : : prev = expr;
1548 : : }
1549 : : }
1550 : :
1551 : : return prev;
1552 : : }
1553 : :
1554 : :
1555 : : /* Checks whether the first given constant value
1556 : : is less than the second one. */
1557 : :
1558 : : bool
1559 : 0 : state::check_const_value_is_less_than (value *arg1, value *arg2)
1560 : : {
1561 : 0 : for (int i = arg1->length () - 1; i >= 0; i--)
1562 : : {
1563 : 0 : if (as_a<bit *> ((*arg1)[i])->get_val ()
1564 : 0 : < as_a<bit *> ((*arg2)[i])->get_val ())
1565 : : return true;
1566 : 0 : else if (as_a<bit *> ((*arg1)[i])->get_val ()
1567 : 0 : > as_a<bit *> ((*arg2)[i])->get_val ())
1568 : : return false;
1569 : : }
1570 : : return false;
1571 : : }
1572 : :
1573 : :
1574 : : /* Adds LESS THAN condition of given variables to state. */
1575 : :
1576 : : bool
1577 : 1357 : state::add_less_than_cond (tree arg1, tree arg2)
1578 : : {
1579 : 1357 : return add_binary_cond (arg1, arg2, &state::add_less_than_cond);
1580 : : }
1581 : :
1582 : :
1583 : : /* Adds less than condition for two values. */
1584 : :
1585 : : void
1586 : 1357 : state::add_less_than_cond (value *arg1, value *arg2)
1587 : : {
1588 : 1442 : if (is_bit_vector (arg1) && is_bit_vector (arg2)
1589 : 1442 : && (make_number (arg2) != 0 || arg1->is_unsigned))
1590 : : {
1591 : 0 : bool result = check_const_value_is_less_than (arg1, arg2);
1592 : 0 : last_cond_status = result ? condition_status::CS_TRUE
1593 : : : condition_status::CS_FALSE;
1594 : 1357 : return;
1595 : : }
1596 : :
1597 : 1357 : last_cond_status = condition_status::CS_SYM;
1598 : 1357 : if (is_bit_vector (arg2) && make_number (arg2) == 0 && !arg1->is_unsigned)
1599 : : {
1600 : 1357 : if (is_a<bit *> (arg1->last ()))
1601 : : {
1602 : 85 : if (as_a<bit *> (arg1->last ())->get_val () == 1)
1603 : 85 : last_cond_status = condition_status::CS_TRUE;
1604 : : else
1605 : 0 : last_cond_status = condition_status::CS_FALSE;
1606 : : }
1607 : : else
1608 : 2544 : conditions.add (new bit_condition (arg1->last ()->copy (), new bit (1),
1609 : 2544 : EQ_EXPR));
1610 : :
1611 : 1357 : return;
1612 : : }
1613 : :
1614 : 0 : bit_expression *lt_cond = construct_less_than_cond (arg1, arg2);
1615 : 0 : if (lt_cond)
1616 : : /* Otherwise its status is already set. */
1617 : 0 : conditions.add (lt_cond);
1618 : : }
1619 : :
1620 : :
1621 : : /* Constructs expression trees of less than condition for given values. */
1622 : :
1623 : : bit_expression *
1624 : 0 : state::construct_less_than_cond (value *arg1, value *arg2)
1625 : : {
1626 : 0 : bit_expression *prev = nullptr;
1627 : 0 : int i = arg1->length () - 1;
1628 : 0 : for (; i >= 0; i--)
1629 : : {
1630 : 0 : if (is_a<bit *> ((*arg1)[i]) && is_a<bit *> ((*arg2)[i]))
1631 : : {
1632 : 0 : if (as_a<bit *> ((*arg1)[i])->get_val ()
1633 : 0 : < as_a<bit *> ((*arg2)[i])->get_val ())
1634 : : {
1635 : 0 : if (!prev)
1636 : 0 : last_cond_status = condition_status::CS_TRUE;
1637 : 0 : return prev;
1638 : : }
1639 : 0 : else if (as_a<bit *> ((*arg1)[i])->get_val ()
1640 : 0 : > as_a<bit *> ((*arg2)[i])->get_val ())
1641 : : {
1642 : 0 : if (prev)
1643 : : {
1644 : 0 : bit_expression *ret_val
1645 : 0 : = as_a<bit_expression *> (prev->get_left ()->copy ());
1646 : 0 : delete prev;
1647 : 0 : return ret_val;
1648 : : }
1649 : : else
1650 : : {
1651 : 0 : last_cond_status = condition_status::CS_FALSE;
1652 : 0 : return nullptr;
1653 : : }
1654 : : }
1655 : : }
1656 : : else
1657 : : {
1658 : 0 : bit_condition *lt_cond
1659 : 0 : = new bit_condition ((*arg1)[i]->copy (), (*arg2)[i]->copy (),
1660 : 0 : LT_EXPR);
1661 : 0 : bit_expression *expr = nullptr;
1662 : 0 : if (i)
1663 : : {
1664 : 0 : bit_condition *eq_cond
1665 : 0 : = new bit_condition ((*arg1)[i]->copy (), (*arg2)[i]->copy (),
1666 : 0 : EQ_EXPR);
1667 : 0 : expr = new bit_or_expression (lt_cond, eq_cond);
1668 : : }
1669 : : else
1670 : : expr = lt_cond;
1671 : :
1672 : 0 : if (prev)
1673 : 0 : prev = new bit_and_expression (expr, prev);
1674 : : else
1675 : : prev = expr;
1676 : : }
1677 : : }
1678 : :
1679 : : return prev;
1680 : : }
1681 : :
1682 : :
1683 : : /* Adds GREATER OR EQUAL condition of given variables to state. */
1684 : :
1685 : : bool
1686 : 1272 : state::add_greater_or_equal_cond (tree arg1, tree arg2)
1687 : : {
1688 : 1272 : return add_binary_cond (arg1, arg2, &state::add_greater_or_equal_cond);
1689 : : }
1690 : :
1691 : :
1692 : : /* Adds greater or equal condition for two values. */
1693 : :
1694 : : void
1695 : 1272 : state::add_greater_or_equal_cond (value *arg1, value *arg2)
1696 : : {
1697 : 1272 : if (is_bit_vector (arg1) && is_bit_vector (arg2)
1698 : 1272 : && (make_number (arg2) != 0 || arg1->is_unsigned))
1699 : : {
1700 : 0 : bool is_greater_than = check_const_value_is_greater_than (arg1,
1701 : : arg2);
1702 : 0 : bool is_equal = check_const_value_equality (arg1, arg2);
1703 : 0 : last_cond_status = (is_greater_than | is_equal)
1704 : 0 : ? condition_status::CS_TRUE
1705 : : : condition_status::CS_FALSE;
1706 : 0 : return;
1707 : : }
1708 : :
1709 : 1272 : last_cond_status = condition_status::CS_SYM;
1710 : 1272 : if (is_bit_vector (arg2) && make_number (arg2) == 0 && !arg1->is_unsigned)
1711 : : {
1712 : 1272 : if (is_a<bit *> (arg1->last ()))
1713 : : {
1714 : 0 : if (as_a<bit *> (arg1->last ())->get_val () == 1)
1715 : 0 : last_cond_status = condition_status::CS_FALSE;
1716 : : else
1717 : 0 : last_cond_status = condition_status::CS_TRUE;
1718 : : }
1719 : : else
1720 : 2544 : conditions.add (new bit_condition (arg1->last ()->copy (), new bit (0),
1721 : 2544 : EQ_EXPR));
1722 : :
1723 : 1272 : return;
1724 : : }
1725 : :
1726 : 0 : bit_expression *eq_cond = construct_equal_cond (arg1, arg2);
1727 : 0 : if (!eq_cond)
1728 : : return;
1729 : :
1730 : 0 : bit_expression *gt_cond = construct_great_than_cond (arg1, arg2);
1731 : 0 : if (gt_cond)
1732 : : /* Otherwise its status is already set. */
1733 : 0 : conditions.add (new bit_or_expression (eq_cond, gt_cond));
1734 : : }
1735 : :
1736 : :
1737 : : /* Adds LESS OR EQUAL condition of given variables to state. */
1738 : :
1739 : : bool
1740 : 0 : state::add_less_or_equal_cond (tree arg1, tree arg2)
1741 : : {
1742 : 0 : return add_binary_cond (arg1, arg2, &state::add_less_or_equal_cond);
1743 : : }
1744 : :
1745 : :
1746 : : /* Adds less or equal condition for two values. */
1747 : :
1748 : : void
1749 : 0 : state::add_less_or_equal_cond (value *arg1, value *arg2)
1750 : : {
1751 : 0 : if (is_bit_vector (arg1) && is_bit_vector (arg2))
1752 : : {
1753 : 0 : bool is_less_than = check_const_value_is_less_than (arg1, arg2);
1754 : 0 : bool is_equal = check_const_value_equality (arg1, arg2);
1755 : 0 : last_cond_status = (is_less_than | is_equal)
1756 : 0 : ? condition_status::CS_TRUE
1757 : : : condition_status::CS_FALSE;
1758 : 0 : return;
1759 : : }
1760 : :
1761 : 0 : last_cond_status = condition_status::CS_SYM;
1762 : 0 : bit_expression *eq_cond = construct_equal_cond (arg1, arg2);
1763 : 0 : if (!eq_cond)
1764 : : return;
1765 : :
1766 : 0 : bit_expression *lt_cond = construct_less_than_cond (arg1, arg2);
1767 : 0 : if (lt_cond)
1768 : : /* Otherwise its status is already set. */
1769 : 0 : conditions.add (new bit_or_expression (eq_cond, lt_cond));
1770 : : }
1771 : :
1772 : :
1773 : : /* Adds a bool condition to state. */
1774 : :
1775 : : bool
1776 : 0 : state::add_bool_cond (tree arg)
1777 : : {
1778 : 0 : if (!is_declared (arg))
1779 : : {
1780 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1781 : 0 : fprintf (dump_file, "Sym-Exec: Argument must be declared "
1782 : : "for bool condition.\n");
1783 : :
1784 : 0 : return false;
1785 : : }
1786 : :
1787 : 0 : value *arg_bits = var_states.get (arg);
1788 : 0 : for (size_t i = 0; i < arg_bits->length (); i++)
1789 : 0 : if (is_a<bit *> ((*arg_bits)[i])
1790 : 0 : && as_a<bit *> ((*arg_bits)[i])->get_val () != 0)
1791 : : {
1792 : 0 : last_cond_status = condition_status::CS_TRUE;
1793 : 0 : print_conditions ();
1794 : 0 : return true;
1795 : : }
1796 : :
1797 : 0 : if (is_bit_vector (arg_bits))
1798 : : {
1799 : 0 : last_cond_status = condition_status::CS_FALSE;
1800 : 0 : print_conditions ();
1801 : 0 : return true;
1802 : : }
1803 : :
1804 : 0 : bit_expression *prev = nullptr;
1805 : 0 : for (size_t i = 0; i < arg_bits->length (); i++)
1806 : : {
1807 : 0 : if (is_a<bit *> ((*arg_bits)[i]))
1808 : 0 : continue;
1809 : :
1810 : 0 : bit_condition *not_eq_cond
1811 : 0 : = new bit_condition ((*arg_bits)[i], new bit (0), NE_EXPR);
1812 : 0 : if (prev)
1813 : 0 : prev = new bit_or_expression (not_eq_cond, prev);
1814 : : else
1815 : 0 : prev = not_eq_cond;
1816 : : }
1817 : :
1818 : 0 : last_cond_status = condition_status::CS_SYM;
1819 : 0 : conditions.add (prev);
1820 : 0 : print_conditions ();
1821 : 0 : return true;
1822 : : }
1823 : :
1824 : :
1825 : : /* Does preprocessing and postprocessing for condition adding.
1826 : : Handles value creation for constants and their removement in the end. */
1827 : :
1828 : : bool
1829 : 12566 : state::add_binary_cond (tree arg1, tree arg2, binary_cond_func cond_func)
1830 : : {
1831 : 12566 : bool arg1_is_declared = is_declared (arg1);
1832 : 12566 : bool arg2_is_declared = is_declared (arg2);
1833 : :
1834 : 12566 : if (!arg1_is_declared && !arg2_is_declared)
1835 : : {
1836 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1837 : 0 : fprintf (dump_file, "Sym-Exec: At least one of arguments must be"
1838 : : " declared for adding the condition.\n");
1839 : :
1840 : 0 : return false;
1841 : : }
1842 : :
1843 : 12566 : if (arg1_is_declared)
1844 : 12566 : declare_if_needed (arg2, var_states.get (arg1)->length ());
1845 : :
1846 : 12566 : if (arg2_is_declared)
1847 : 0 : declare_if_needed (arg1, var_states.get (arg2)->length ());
1848 : :
1849 : 12566 : value *arg1_val = var_states.get (arg1);
1850 : 12566 : value arg1_const_val (MAX_VALUE_SIZE, false);
1851 : :
1852 : 12566 : if (arg1_val == NULL && TREE_CODE (arg1) == INTEGER_CST)
1853 : : {
1854 : 0 : arg1_const_val = create_val_for_const (arg1,
1855 : 0 : var_states.get (arg2)->length ());
1856 : 0 : arg1_val = &arg1_const_val;
1857 : : }
1858 : :
1859 : 12566 : value *arg2_val = var_states.get (arg2);
1860 : 12566 : value arg2_const_val (MAX_VALUE_SIZE, false);
1861 : 12566 : if (arg2_val == NULL && TREE_CODE (arg2) == INTEGER_CST)
1862 : : {
1863 : 25132 : arg2_const_val = create_val_for_const (arg2,
1864 : 25132 : var_states.get (arg1)->length ());
1865 : 12566 : arg2_val = &arg2_const_val;
1866 : : }
1867 : :
1868 : 12566 : (this->*cond_func) (arg1_val, arg2_val);
1869 : 12566 : print_conditions ();
1870 : 12566 : return true;
1871 : 12566 : }
1872 : :
1873 : :
1874 : : /* Constructs expression trees of equal condition for given values. */
1875 : :
1876 : : bit_expression *
1877 : 0 : state::construct_equal_cond (value *arg1, value *arg2)
1878 : : {
1879 : : /* If both arguments are constants then we can evaluate it. */
1880 : 0 : if (is_bit_vector (arg1) && is_bit_vector (arg2))
1881 : : {
1882 : 0 : bool result = check_const_value_equality (arg1, arg2);
1883 : 0 : last_cond_status = result ? condition_status::CS_TRUE
1884 : : : condition_status::CS_FALSE;
1885 : 0 : return nullptr;
1886 : : }
1887 : :
1888 : : /* When some bits are constants, and they differ by value,
1889 : : then we can evaluate it to be false. */
1890 : 0 : for (size_t i = 0; i < arg1->length (); i++)
1891 : : {
1892 : 0 : if (is_a<bit *> ((*arg1)[i]) && is_a<bit *> ((*arg2)[i])
1893 : 0 : && as_a<bit *> ((*arg1)[i])->get_val ()
1894 : 0 : != as_a<bit *> ((*arg2)[i])->get_val ())
1895 : : {
1896 : 0 : last_cond_status = condition_status::CS_FALSE;
1897 : 0 : return nullptr;
1898 : : }
1899 : : }
1900 : :
1901 : : bit_expression *prev = nullptr;
1902 : 0 : for (size_t i = 0; i < arg1->length (); i++)
1903 : : {
1904 : 0 : bit_condition *eq_expr = new bit_condition ((*arg1)[i]->copy (),
1905 : 0 : (*arg2)[i]->copy (), EQ_EXPR);
1906 : 0 : if (prev)
1907 : 0 : prev = new bit_and_expression (eq_expr, prev);
1908 : : else
1909 : : prev = eq_expr;
1910 : : }
1911 : :
1912 : : return prev;
1913 : : }
1914 : :
1915 : :
1916 : : /* Constructor for value. The first argument is the size of the bit-vector
1917 : : and the second argument is the sign of the number. */
1918 : :
1919 : 278174 : value::value (unsigned size, bool is_unsigned) : is_unsigned (is_unsigned)
1920 : : {
1921 : 278174 : number.create (size);
1922 : 278174 : }
1923 : :
1924 : :
1925 : : /* Copy constructor for value. */
1926 : :
1927 : 209714 : value::value (const value &other) : is_unsigned (other.is_unsigned)
1928 : : {
1929 : 209714 : number.create (other.length ());
1930 : 7677890 : for (size_t i = 0; i < other.length (); ++i)
1931 : : {
1932 : 7468176 : value_bit *temp = other[i] ? other[i]->copy () : other[i];
1933 : 7468176 : number.quick_push (temp);
1934 : : }
1935 : 209714 : }
1936 : :
1937 : :
1938 : : /* Returns pushed bits count. */
1939 : :
1940 : : unsigned
1941 : 14679179 : value::length () const
1942 : : {
1943 : 14679179 : return number.length ();
1944 : : }
1945 : :
1946 : :
1947 : : /* Wrapper of vec<..>::operator[] for the bit-vector. */
1948 : :
1949 : : value_bit *&
1950 : 11591825 : value::operator[] (unsigned i)
1951 : : {
1952 : 11591825 : return number[i];
1953 : : }
1954 : :
1955 : :
1956 : : /* Assignment operator. If the specified value's size is smaller,
1957 : : then 0 constant bit will be assigned to the remaining upper bits. */
1958 : :
1959 : : value &
1960 : 36936 : value::operator= (const value &other)
1961 : : {
1962 : 73872 : unsigned smallest = number.allocated () < other.length ()
1963 : 36936 : ? number.allocated () : other.length ();
1964 : :
1965 : 1312656 : for (size_t i = 0; i < smallest; i++)
1966 : 1275720 : if (i < number.length ())
1967 : : {
1968 : 0 : delete number[i];
1969 : 0 : number[i] = other[i]->copy ();
1970 : : }
1971 : : else
1972 : 1275720 : number.quick_push (other[i]->copy ());
1973 : :
1974 : 404272 : for (size_t i = smallest; i < number.allocated (); i++)
1975 : 367336 : if (i < number.length ())
1976 : : {
1977 : 0 : delete number[i];
1978 : 0 : number[i] = other.is_unsigned ? new bit (0)
1979 : 0 : : other[other.length () - 1]->copy ();
1980 : : }
1981 : : else
1982 : 734672 : number.quick_push (other.is_unsigned
1983 : 367336 : ? new bit (0) : other[other.length () - 1]->copy ());
1984 : :
1985 : 36936 : return (*this);
1986 : : }
1987 : :
1988 : :
1989 : : /* Wrapper of vec<..>::operator[] const for the bit-vector. */
1990 : :
1991 : : value_bit *
1992 : 20054260 : value::operator[] (unsigned i) const
1993 : : {
1994 : 20054260 : return number[i];
1995 : : }
1996 : :
1997 : :
1998 : : /* Wrapper of vec<..>.exists for the bit-vector. */
1999 : :
2000 : : bool
2001 : 39628 : value::exists () const
2002 : : {
2003 : 39628 : return number.exists ();
2004 : : }
2005 : :
2006 : :
2007 : : /* Returns the size in bits. */
2008 : :
2009 : : unsigned
2010 : 362456 : value::allocated () const
2011 : : {
2012 : 362456 : return number.allocated ();
2013 : : }
2014 : :
2015 : :
2016 : : /* Returns a reference the last bit. */
2017 : :
2018 : : value_bit *&
2019 : 5762 : value::last ()
2020 : : {
2021 : 5762 : return number.last ();
2022 : : }
2023 : :
2024 : :
2025 : : /* Make a copy of given bits. */
2026 : :
2027 : : vec<value_bit *> *
2028 : 0 : state::make_copy (vec<value_bit *> *bits)
2029 : : {
2030 : 0 : vec < value_bit * > *copied_bits = new vec<value_bit *> ();
2031 : 0 : copied_bits->create (bits->length ());
2032 : 0 : for (size_t i = 0; i < bits->length (); i++)
2033 : 0 : copied_bits->quick_push ((*bits)[i]->copy ());
2034 : :
2035 : 0 : return copied_bits;
2036 : : }
2037 : :
2038 : :
2039 : : /* Returns status of last added condition. */
2040 : :
2041 : : condition_status
2042 : 26074 : state::get_last_cond_status ()
2043 : : {
2044 : 26074 : return last_cond_status;
2045 : : }
2046 : :
2047 : :
2048 : : /* Prints the given value. */
2049 : :
2050 : : void
2051 : 48048 : state::print_value (value *var)
2052 : : {
2053 : 48048 : if (!dump_file || !(dump_flags & TDF_DETAILS))
2054 : : return;
2055 : :
2056 : 43301 : fprintf (dump_file, "{");
2057 : 1505909 : for (int i = var->length () - 1; i >= 0; i--)
2058 : : {
2059 : 1462608 : (*var)[i]->print ();
2060 : :
2061 : 1462608 : if (i)
2062 : 1419307 : fprintf (dump_file, ", ");
2063 : : }
2064 : 43301 : fprintf (dump_file, "}\n");
2065 : : }
2066 : :
2067 : :
2068 : : /* Create LFSR value for the reversed CRC. */
2069 : :
2070 : : void
2071 : 113 : state::create_reversed_lfsr (value &lfsr, const value &crc,
2072 : : const value &polynomial)
2073 : : {
2074 : 113 : size_t size = polynomial.length ();
2075 : :
2076 : : /* Determine values of all bits, except MSB. */
2077 : 3240 : for (size_t i = 0; i < size - 1; i++)
2078 : : {
2079 : 3127 : if (as_a<bit *> (polynomial[i])->get_val ())
2080 : 908 : lfsr.push (state::xor_two_bits (crc[i + 1], crc[0]));
2081 : : else
2082 : 2219 : lfsr.push (crc[i + 1]->copy ());
2083 : : }
2084 : :
2085 : : /* Determine value of MSB. */
2086 : 113 : if (as_a<bit *> (polynomial[size - 1])->get_val ())
2087 : 111 : lfsr.push (crc[0]->copy ());
2088 : : else
2089 : 2 : lfsr.push (new bit (0));
2090 : 113 : }
2091 : :
2092 : :
2093 : : /* Create LFSR value for the forward CRC. */
2094 : :
2095 : : void
2096 : 110 : state::create_forward_lfsr (value &lfsr, const value &crc,
2097 : : const value &polynomial)
2098 : : {
2099 : 110 : size_t size = polynomial.length ();
2100 : : /* Determine value of LSB. */
2101 : 110 : if (as_a<bit *> (polynomial[0])->get_val ())
2102 : 95 : lfsr.push (crc[size - 1]->copy ());
2103 : : else
2104 : 15 : lfsr.push (new bit (0));
2105 : :
2106 : : /* Determine values of remaining bits. */
2107 : 2448 : for (size_t i = 1; i < size; i++)
2108 : : {
2109 : 2338 : if (as_a<bit *> (polynomial[i])->get_val ())
2110 : 801 : lfsr.push (state::xor_two_bits (crc[i - 1], crc[size - 1]));
2111 : : else
2112 : 1537 : lfsr.push (crc[i - 1]->copy ());
2113 : : }
2114 : 110 : }
2115 : :
2116 : :
2117 : : /* Get the last 1 bit index. */
2118 : :
2119 : : size_t
2120 : 243 : last_set_bit (const value &polynomial)
2121 : : {
2122 : 1113 : for (size_t i = 0; i < polynomial.length (); ++i)
2123 : : {
2124 : 1101 : if (as_a<bit *> (polynomial[polynomial.length () - i - 1])->get_val ())
2125 : 231 : return polynomial.length () - i - 1;
2126 : : }
2127 : : return 0;
2128 : : }
2129 : :
2130 : :
2131 : : /* Create LFSR value. */
2132 : :
2133 : : value *
2134 : 243 : state::create_lfsr (tree crc, value *polynomial, bool is_bit_forward)
2135 : : {
2136 : : /* Check size compatibility․ */
2137 : 243 : unsigned HOST_WIDE_INT polynomial_length = polynomial->length ();
2138 : 243 : unsigned HOST_WIDE_INT crc_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (crc)));
2139 : 243 : if (crc_size < polynomial_length)
2140 : : {
2141 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
2142 : 0 : fprintf (dump_file, "LFSR state creation: "
2143 : : "Polynomial doesn't fit into the crc.\n");
2144 : :
2145 : 0 : return nullptr;
2146 : : }
2147 : :
2148 : : /* Get the minimal byte size to keep the polynomial.
2149 : : Ie, if the last 1 bit of the polynomial is at 6 index, size will be 8. */
2150 : 243 : size_t required_polynomial_size = ((last_set_bit (*polynomial)/8) + 1) * 8;
2151 : :
2152 : : /* Polynomial's length actually equals to the CRC variable's size.
2153 : : Now we detect only those CRC calculation algorithms, where leading 1 of the
2154 : : polynomial isn't kept. */
2155 : 243 : if (required_polynomial_size == 0
2156 : 243 : || required_polynomial_size != polynomial_length)
2157 : : {
2158 : 20 : if (dump_file && (dump_flags & TDF_DETAILS))
2159 : 14 : fprintf (dump_file, "Polynomial's all bits are zeros "
2160 : : "or the size of the polynomial is uncertain.\n");
2161 : 20 : return nullptr;
2162 : : }
2163 : :
2164 : : /* Create vector of symbolic bits for crc. */
2165 : 223 : value crc_value (polynomial_length, TYPE_UNSIGNED (TREE_TYPE (crc)));
2166 : :
2167 : 5911 : for (unsigned HOST_WIDE_INT i = 0; i < polynomial_length; i++)
2168 : 5688 : crc_value.push (new symbolic_bit (i, crc));
2169 : :
2170 : : /* create LFSR vector. */
2171 : 223 : value *lfsr = new value (polynomial_length, TYPE_UNSIGNED (TREE_TYPE (crc)));
2172 : :
2173 : : /* Calculate values for LFSR. */
2174 : 223 : if (is_bit_forward)
2175 : 110 : create_forward_lfsr (*lfsr, crc_value, *polynomial);
2176 : : else
2177 : 113 : create_reversed_lfsr (*lfsr, crc_value, *polynomial);
2178 : :
2179 : 223 : return lfsr;
2180 : 223 : }
2181 : :
2182 : :
2183 : : /* Prints added conditions. */
2184 : :
2185 : : void
2186 : 12566 : state::print_conditions ()
2187 : : {
2188 : 12566 : if (!dump_file || !(dump_flags & TDF_DETAILS))
2189 : 1620 : return;
2190 : :
2191 : 10946 : fprintf (dump_file, "Conditions {");
2192 : 10946 : auto iter = conditions.begin ();
2193 : 10946 : while (true)
2194 : : {
2195 : 10946 : if (iter != conditions.end ())
2196 : : {
2197 : 10560 : (*iter)->print ();
2198 : 10560 : ++iter;
2199 : : }
2200 : :
2201 : 10946 : if (iter != conditions.end ())
2202 : 0 : fprintf (dump_file, ", ");
2203 : : else
2204 : : break;
2205 : : }
2206 : 10946 : fprintf (dump_file, "}\n");
2207 : : }
2208 : :
2209 : :
2210 : : /* Pushes the given bit to the end of the bit vector. */
2211 : :
2212 : : value_bit **
2213 : 6907064 : value::push (value_bit *elem)
2214 : : {
2215 : 6907064 : return number.quick_push (elem);
2216 : : }
2217 : :
2218 : :
2219 : : /* Destructor for value. */
2220 : :
2221 : 487888 : value::~value ()
2222 : : {
2223 : 487888 : free_bits ();
2224 : 487888 : number.release ();
2225 : 487888 : }
2226 : :
2227 : :
2228 : : /* Removes given sequence of bits. */
2229 : :
2230 : : void
2231 : 487888 : value::free_bits ()
2232 : : {
2233 : 487888 : if (!number.exists ())
2234 : : return;
2235 : :
2236 : 16506184 : for (size_t i = 0; i < number.length (); i++)
2237 : : {
2238 : 16018296 : delete number[i];
2239 : 16018296 : number[i] = nullptr;
2240 : : }
2241 : : }
2242 : :
2243 : :
2244 : : /* For the given value_bit, iterates over its expression tree, complements
2245 : : those bit which came from the given origin. */
2246 : :
2247 : : value_bit *
2248 : 0 : state::complement_bits_with_origin (value_bit *root, tree origin)
2249 : : {
2250 : : /* Be careful. This function doesn't make a full copy of the bit. */
2251 : 0 : if (!is_a<bit_expression *> (root))
2252 : : {
2253 : 0 : if (is_a<symbolic_bit *> (root)
2254 : 0 : && as_a<symbolic_bit *> (root)->get_origin () == origin)
2255 : 0 : root = new bit_complement_expression (root);
2256 : :
2257 : 0 : return root;
2258 : : }
2259 : :
2260 : 0 : bit_expression *expr_root = as_a<bit_expression *> (root);
2261 : 0 : hash_set <value_bit *> nodes_to_consider;
2262 : 0 : nodes_to_consider.add (expr_root);
2263 : 0 : hash_map <value_bit *, value_bit *> node_to_parent;
2264 : 0 : node_to_parent.put (expr_root, nullptr);
2265 : :
2266 : : /* Traversing expression tree. */
2267 : 0 : while (!nodes_to_consider.is_empty ())
2268 : : {
2269 : 0 : value_bit *cur_element = *nodes_to_consider.begin ();
2270 : 0 : nodes_to_consider.remove (cur_element);
2271 : :
2272 : 0 : if (is_a<symbolic_bit *> (cur_element))
2273 : : {
2274 : 0 : if (as_a<symbolic_bit *> (cur_element)->get_origin () != origin)
2275 : 0 : continue;
2276 : :
2277 : 0 : bit_expression *parent
2278 : 0 : = as_a<bit_expression *> (*node_to_parent.get (cur_element));
2279 : 0 : if (is_a<bit_complement_expression *> (parent))
2280 : : {
2281 : 0 : value_bit *parent_of_parent = *node_to_parent.get (parent);
2282 : 0 : if (parent_of_parent)
2283 : : {
2284 : 0 : bit_expression *parent_of_parent_expr
2285 : 0 : = as_a<bit_expression *> (parent_of_parent);
2286 : 0 : parent->set_right (nullptr);
2287 : 0 : delete parent;
2288 : 0 : parent_of_parent_expr->get_left () == parent
2289 : 0 : ? parent_of_parent_expr->set_left (cur_element)
2290 : 0 : : parent_of_parent_expr->set_right (cur_element);
2291 : : }
2292 : : else
2293 : : {
2294 : : /* Parent is our root. */
2295 : 0 : as_a<bit_expression *> (root)->set_right (nullptr);
2296 : 0 : delete root;
2297 : : root = cur_element;
2298 : : }
2299 : : }
2300 : : else
2301 : : {
2302 : 0 : value_bit* new_bit = new bit_complement_expression (cur_element);
2303 : 0 : parent->get_left () == cur_element ? parent->set_left (new_bit)
2304 : 0 : : parent->set_right (new_bit);
2305 : : }
2306 : 0 : continue;
2307 : 0 : }
2308 : :
2309 : 0 : bit_expression* cur_elem_expr = as_a<bit_expression *> (cur_element);
2310 : 0 : value_bit *left = cur_elem_expr->get_left ();
2311 : 0 : value_bit *right = cur_elem_expr->get_right ();
2312 : 0 : if (left != nullptr && !is_a<bit *> (left))
2313 : : {
2314 : 0 : nodes_to_consider.add (left);
2315 : 0 : node_to_parent.put (left, cur_element);
2316 : : }
2317 : :
2318 : 0 : if (right != nullptr && !is_a<bit *> (right))
2319 : : {
2320 : 0 : nodes_to_consider.add (right);
2321 : 0 : node_to_parent.put (right, cur_element);
2322 : : }
2323 : : }
2324 : :
2325 : 0 : return root;
2326 : 0 : }
2327 : :
2328 : :
2329 : : /* Iterates over every bit of the given value and complements their
2330 : : expression trees' those bits, that came from the given origin. */
2331 : :
2332 : : void
2333 : 0 : state::complement_val_bits_with_origin (value *val, tree origin)
2334 : : {
2335 : 0 : for (size_t i = 0; i < val->length (); i++)
2336 : : {
2337 : 0 : (*val)[i] = complement_bits_with_origin ((*val)[i], origin);
2338 : : }
2339 : 0 : }
2340 : :
2341 : :
2342 : : /* Complements all bits of all values that came from the given origin. */
2343 : :
2344 : : void
2345 : 0 : state::complement_all_vars_bits_with_origin (tree origin)
2346 : : {
2347 : 0 : for (auto iter = var_states.begin (); iter != var_states.end (); ++iter)
2348 : : {
2349 : 0 : complement_val_bits_with_origin (&(*iter).second, origin);
2350 : : }
2351 : 0 : }
2352 : :
2353 : :
2354 : : /* Complements all bits with the given origin of all added conditions. */
2355 : :
2356 : : void
2357 : 0 : state::complement_conditions_with_origin (tree origin)
2358 : : {
2359 : 0 : hash_set<bit_expression *> updated_conditions;
2360 : 0 : for (auto iter = conditions.begin (); iter != conditions.end (); ++iter)
2361 : 0 : updated_conditions.add (as_a<bit_expression *> (
2362 : 0 : complement_bits_with_origin (*iter, origin)));
2363 : :
2364 : 0 : conditions.empty ();
2365 : 0 : for (auto iter = updated_conditions.begin ();
2366 : 0 : iter != updated_conditions.end (); ++iter)
2367 : 0 : conditions.add (*iter);
2368 : 0 : }
2369 : :
2370 : :
2371 : : /* Complements all bits with the given origin of all values
2372 : : and added conditions. */
2373 : :
2374 : : void
2375 : 0 : state::complement_state_with_origin (tree origin)
2376 : : {
2377 : 0 : complement_all_vars_bits_with_origin (origin);
2378 : 0 : complement_conditions_with_origin (origin);
2379 : 0 : }
2380 : :
2381 : :
2382 : : /* Performs the specified operation on passed variables. */
2383 : :
2384 : : bool
2385 : 42146 : state::do_operation (tree_code op_code, tree arg1, tree arg2, tree dest)
2386 : : {
2387 : 42146 : switch (op_code)
2388 : : {
2389 : 0 : case BIT_NOT_EXPR:
2390 : 0 : return do_complement (arg1, dest);
2391 : 15897 : case NOP_EXPR:
2392 : 15897 : case SSA_NAME:
2393 : 15897 : case VAR_DECL:
2394 : 15897 : case INTEGER_CST:
2395 : 15897 : return do_assign (arg1, dest);
2396 : 3643 : case LSHIFT_EXPR:
2397 : 3643 : return do_binary_operation (arg1, arg2, dest, &state::do_shift_left);
2398 : 3042 : case RSHIFT_EXPR:
2399 : 3042 : return do_binary_operation (arg1, arg2, dest, &state::do_shift_right);
2400 : 1825 : case BIT_AND_EXPR:
2401 : 1825 : return do_binary_operation (arg1, arg2, dest, &state::do_and);
2402 : 4 : case BIT_IOR_EXPR:
2403 : 4 : return do_binary_operation (arg1, arg2, dest, &state::do_or);
2404 : 5118 : case BIT_XOR_EXPR:
2405 : 5118 : return do_binary_operation (arg1, arg2, dest, &state::do_xor);
2406 : 6326 : case PLUS_EXPR:
2407 : 6326 : return do_binary_operation (arg1, arg2, dest, &state::do_add);
2408 : 6285 : case MINUS_EXPR:
2409 : 6285 : return do_binary_operation (arg1, arg2, dest, &state::do_sub);
2410 : 6 : case MULT_EXPR:
2411 : 6 : return do_binary_operation (arg1, arg2, dest, &state::do_mul);
2412 : 0 : default:
2413 : 0 : {
2414 : 0 : if (dump_file)
2415 : 0 : fprintf (dump_file,
2416 : : "Warning, encountered unsupported operation "
2417 : : "with %s code while executing assign statement!\n",
2418 : : get_tree_code_name (op_code));
2419 : : return false;
2420 : : }
2421 : : }
2422 : : }
|
