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-2026 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 20404 : size_t min (size_t a, size_t b, size_t c)
167 : {
168 20404 : size_t min = (a < b ? a : b);
169 20404 : 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 9993 : state::state (const state &s)
177 : {
178 196533 : for (auto iter = s.var_states.begin (); iter != s.var_states.end (); ++iter)
179 : {
180 93270 : value val ((*iter).second.length (), (*iter).second.is_unsigned);
181 3298366 : for (size_t i = 0; i < (*iter).second.length (); i++)
182 3205096 : val.push ((*iter).second[i]->copy ());
183 :
184 93270 : var_states.put ((*iter).first, val);
185 93270 : }
186 :
187 16303 : for (auto iter = s.conditions.begin (); iter != s.conditions.end (); ++iter)
188 6310 : conditions.add (as_a<bit_expression *> ((*iter)->copy ()));
189 9993 : }
190 :
191 :
192 : /* Destructor for state. */
193 :
194 13424 : state::~state ()
195 : {
196 13424 : clear_conditions ();
197 13424 : }
198 :
199 :
200 : /* Checks whether state for variable with specified name already
201 : exists or not. */
202 :
203 : bool
204 158179 : state::is_declared (tree var)
205 : {
206 158179 : return var_states.get (var) != NULL;
207 : }
208 :
209 :
210 : /* Declares given variable if it has not been declared yet. */
211 :
212 : void
213 128171 : state::declare_if_needed (tree var, size_t size)
214 : {
215 128171 : if (TREE_CODE (var) != INTEGER_CST && !is_declared (var))
216 : {
217 48847 : make_symbolic (var, size);
218 48847 : if (dump_file && (dump_flags & TDF_DETAILS))
219 : {
220 42145 : fprintf (dump_file,
221 : "Declaring var ");
222 42145 : print_generic_expr (dump_file, var, dump_flags);
223 42145 : fprintf (dump_file,
224 : " with size %zd\n", size);
225 : }
226 : }
227 128171 : }
228 :
229 :
230 : /* Get value of the given variable. */
231 :
232 : value *
233 18267 : state::get_value (tree var)
234 : {
235 18267 : 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 12616 : state::get_conditions ()
252 : {
253 12616 : return conditions;
254 : }
255 :
256 :
257 : /* Checks if sizes of arguments and destination are compatible. */
258 :
259 : bool
260 27147 : state::check_args_compatibility (tree arg1, tree arg2, tree dest)
261 : {
262 27147 : if (!(get_var_size (arg1) == get_var_size (dest)
263 2 : || TREE_CODE (arg1) == INTEGER_CST)
264 27149 : || !(get_var_size (arg2) == get_var_size (dest)
265 25257 : || 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 45408 : state::create_val_for_const (tree var, size_t size)
282 : {
283 45408 : unsigned HOST_WIDE_INT val = TYPE_UNSIGNED (TREE_TYPE (var))
284 45408 : ? tree_to_uhwi (var) : tree_to_shwi (var);
285 45408 : value result (size, TYPE_UNSIGNED (TREE_TYPE (var)));
286 :
287 1612712 : for (size_t i = 0; i < size; i++)
288 : {
289 1567304 : result.push (new bit (val & 1));
290 1567304 : val >>= 1;
291 : }
292 :
293 45408 : 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 3945 : state::remove_states (vec<state *> *states)
337 : {
338 10531 : while (!states->is_empty ())
339 : {
340 6586 : delete states->last ();
341 6586 : states->pop ();
342 : }
343 3945 : }
344 :
345 :
346 : /* Remove all states from the states' vector and release the vector. */
347 :
348 : void
349 1028 : state::clear_states (vec<state *> *states)
350 : {
351 1028 : remove_states (states);
352 1028 : states->release ();
353 1028 : }
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 13424 : state::clear_conditions ()
369 : {
370 38664 : for (auto iter = conditions.begin (); iter != conditions.end (); ++iter)
371 12620 : delete (*iter);
372 13424 : conditions.empty ();
373 13424 : }
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 57880 : state::and_var_const (const value_bit *var1, const bit *const_bit)
389 : {
390 57880 : if (const_bit->get_val () == 1)
391 1755 : return var1->copy ();
392 :
393 56125 : return new bit (0);
394 : }
395 :
396 :
397 : /* Performs AND operation for 2 constant bit operands. */
398 :
399 : bit *
400 1412800 : state::and_const_bits (const bit *const_bit1, const bit *const_bit2)
401 : {
402 1412800 : if (const_bit1->get_val () == const_bit2->get_val ())
403 682137 : return new bit (*const_bit1);
404 :
405 730663 : 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 699648 : state::or_const_bits (const bit *const_bit1, const bit *const_bit2)
434 : {
435 699648 : if (const_bit1->get_val () == const_bit2->get_val ())
436 463108 : return new bit (*const_bit1);
437 :
438 236540 : return new bit (1);
439 : }
440 :
441 :
442 : /* Adds an empty state for the given variable. */
443 :
444 : bool
445 273 : state::decl_var (tree var, unsigned size)
446 : {
447 273 : if (is_declared (var))
448 : return false;
449 :
450 273 : value val (size, TYPE_UNSIGNED (TREE_TYPE (var)));
451 6065 : for (unsigned i = 0; i < size; i++)
452 5792 : val.push (nullptr);
453 :
454 273 : return var_states.put (var, val);
455 273 : }
456 :
457 :
458 : /* Returns size of the given variable. */
459 :
460 : unsigned
461 333077 : state::get_var_size (tree var)
462 : {
463 333077 : value *content = var_states.get (var);
464 333077 : if (content == NULL)
465 : return 0;
466 :
467 307818 : 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 48847 : state::make_symbolic (tree var, unsigned size)
476 : {
477 48847 : if (is_declared (var))
478 : return false;
479 :
480 48847 : value val (size, TYPE_UNSIGNED (TREE_TYPE (var)));
481 : /* Initialize each bit of a variable with unknown value. */
482 1707887 : for (size_t i = 0; i < size; i++)
483 1659040 : val.push (new symbolic_bit (i, var));
484 :
485 48847 : return var_states.put (var, val);
486 48847 : }
487 :
488 :
489 : /* Performs AND operation on two bits. */
490 :
491 : value_bit *
492 1470680 : state::and_two_bits (value_bit *arg1, value_bit *arg2)
493 : {
494 1470680 : value_bit *result = nullptr;
495 :
496 2883480 : if (is_a<bit *> (arg1) && is_a<bit *> (arg2))
497 1412800 : result = and_const_bits (as_a<bit *> (arg1), as_a<bit *> (arg2));
498 :
499 57880 : 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 57880 : else if ((is_a<symbolic_bit *> (arg1)
504 149711 : || (is_a<bit_expression *> (arg1))) && is_a<bit *> (arg2))
505 57880 : result = and_var_const (arg1, as_a<bit *> (arg2));
506 :
507 : else
508 0 : result = and_sym_bits (arg1, arg2);
509 :
510 1470680 : 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 259624 : state::operate_bits (bit_func bit_op, value_bit *bit1, value_bit *bit2,
519 : value_bit **)
520 : {
521 259624 : 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 466376 : state::operate_bits (bit_func3 bit_op, value_bit *bit1, value_bit *bit2,
530 : value_bit **bit3)
531 : {
532 466376 : 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 27147 : state::do_binary_operation (tree arg1, tree arg2, tree dest,
541 : binary_func bin_func)
542 : {
543 27147 : declare_if_needed (dest, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest))));
544 27147 : declare_if_needed (arg1, var_states.get (dest)->allocated ());
545 27147 : declare_if_needed (arg2, var_states.get (dest)->allocated ());
546 :
547 27147 : if (!check_args_compatibility (arg1, arg2, dest))
548 : return false;
549 :
550 27147 : size_t dest_size = var_states.get (dest)->length ();
551 :
552 27147 : value *arg1_val = var_states.get (arg1);
553 27147 : value arg1_const_val (dest_size, false);
554 27147 : 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 27147 : value *arg2_val = var_states.get (arg2);
561 27147 : value arg2_const_val (dest_size, false);
562 27147 : if (arg2_val == NULL && TREE_CODE (arg2) == INTEGER_CST)
563 : {
564 25257 : arg2_const_val = create_val_for_const (arg2, dest_size);
565 25257 : arg2_val = &arg2_const_val;
566 : }
567 :
568 27147 : (this->*bin_func) (arg1_val, arg2_val, dest);
569 27147 : print_value (var_states.get (dest));
570 27147 : return true;
571 27147 : }
572 :
573 :
574 : /* Performs AND operation on given values. The result is stored in dest. */
575 :
576 : void
577 1926 : 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 1926 : operate (arg1, arg2, nullptr, dest, &state::and_two_bits);
583 1926 : }
584 :
585 :
586 : /* Performs OR operation on two bits. */
587 :
588 : value_bit *
589 699648 : state::or_two_bits (value_bit *arg1_bit, value_bit *arg2_bit)
590 : {
591 699648 : value_bit *result = nullptr;
592 :
593 1399296 : if (is_a<bit *> (arg1_bit) && is_a<bit *> (arg2_bit))
594 699648 : 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 699648 : 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 1588867 : state::xor_two_bits (value_bit *arg1_bit, value_bit *arg2_bit)
627 : {
628 1588867 : value_bit *result = nullptr;
629 :
630 3015646 : if (is_a<bit *> (arg1_bit) && is_a<bit *> (arg2_bit))
631 1420235 : result = xor_const_bits (as_a<bit *> (arg1_bit), as_a<bit *> (arg2_bit));
632 :
633 175176 : 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 162088 : else if ((is_a<symbolic_bit *> (arg1_bit)
638 0 : || is_a<bit_expression *> (arg1_bit))
639 324176 : && is_a<bit *> (arg2_bit))
640 104189 : result = xor_var_const (arg1_bit, as_a<bit *> (arg2_bit));
641 :
642 : else
643 57899 : result = xor_sym_bits (arg1_bit, arg2_bit);
644 :
645 1588867 : return result;
646 : }
647 :
648 :
649 : /* Performs XOR operation on given values. The result is stored in dest. */
650 :
651 : void
652 5281 : state::do_xor (value *arg1, value *arg2, tree dest)
653 : {
654 5281 : operate (arg1, arg2, nullptr, dest, &state::xor_two_bits);
655 5281 : }
656 :
657 :
658 : /* Shifts value right by size of shift_value. */
659 :
660 : value *
661 3007 : state::shift_right_by_const (value *var, size_t shift_value)
662 : {
663 3007 : value *shift_result = new value (var->length (), var->is_unsigned);
664 3007 : 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 95584 : for (; i < var->length () - shift_value; ++i)
671 92579 : shift_result->push (((*var)[shift_value + i])->copy ());
672 :
673 11994 : for (; i < var->length (); ++i)
674 9493 : shift_result->push (var->is_unsigned ? new bit (0)
675 504 : : var->last ()->copy ());
676 : }
677 3007 : return shift_result;
678 : }
679 :
680 :
681 : /* Checks if all bits of the given value have constant bit type. */
682 :
683 : bool
684 41414 : state::is_bit_vector (const value *var)
685 : {
686 41414 : if (var == nullptr || !var->exists ())
687 0 : return false;
688 :
689 1556638 : for (size_t i = 0; i < var->length (); i++)
690 1521534 : 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 15679 : state::make_number (const value *var)
700 : {
701 15679 : unsigned HOST_WIDE_INT
702 15679 : number = 0;
703 15679 : int value_size = var->length ();
704 640407 : for (int i = value_size - 1; i >= 0; i--)
705 : {
706 624728 : if (is_a<bit *> ((*var)[i]))
707 624728 : 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 3730 : state::do_shift_left (value *arg1, value *arg2, tree dest)
729 : {
730 3730 : if (is_bit_vector (arg2))
731 : {
732 3730 : size_t shift_value = make_number (arg2);
733 3730 : value *result = shift_left_by_const (arg1, shift_value);
734 119850 : for (size_t i = 0; i < get_var_size (dest); i++)
735 : {
736 116120 : delete (*var_states.get (dest))[i];
737 116120 : (*var_states.get (dest))[i] = (*result)[i]->copy ();
738 : }
739 3730 : delete result;
740 : }
741 : else
742 0 : operate (arg1, arg2, nullptr, dest, &state::shift_left_sym_bits);
743 3730 : }
744 :
745 :
746 : /* Performs shift right operation on given values.
747 : The result is stored in dest. */
748 :
749 : void
750 3007 : state::do_shift_right (value *arg1, value *arg2, tree dest)
751 : {
752 3007 : if (is_bit_vector (arg2))
753 : {
754 3007 : size_t shift_value = make_number (arg2);
755 3007 : value *result = shift_right_by_const (arg1, shift_value);
756 104639 : for (size_t i = 0; i < get_var_size (dest); i++)
757 : {
758 101632 : delete (*var_states.get (dest))[i];
759 101632 : (*var_states.get (dest))[i] = (*result)[i]->copy ();
760 : }
761 :
762 3007 : delete result;
763 : }
764 : else
765 0 : operate (arg1, arg2, nullptr, dest, &state::shift_right_sym_bits);
766 3007 : }
767 :
768 :
769 : /* Adds two bits and carry value.
770 : Resturn result and stores new carry bit in "carry". */
771 :
772 : value_bit *
773 699544 : state::full_adder (value_bit *var1, value_bit *var2, value_bit **carry)
774 : {
775 699544 : value_bit *new_carry = and_two_bits (var1, var2);
776 699544 : value_bit *sum = xor_two_bits (var1, var2);
777 :
778 699544 : value_bit *result = xor_two_bits (sum, *carry);
779 699544 : value_bit *sum_and_carry = and_two_bits (sum, *carry);
780 :
781 699544 : delete *carry;
782 699544 : delete sum;
783 :
784 699544 : *carry = or_two_bits (sum_and_carry, new_carry);
785 :
786 699544 : delete sum_and_carry;
787 699544 : delete new_carry;
788 :
789 699544 : return result;
790 : }
791 :
792 :
793 : /* Adds given values. The result is stored in dest. */
794 :
795 : void
796 13193 : state::do_add (value *arg1, value *arg2, tree dest)
797 : {
798 13193 : value_bit *carry = new bit (0);
799 13193 : operate (arg1, arg2, &carry, dest, &state::full_adder);
800 13193 : delete carry;
801 13193 : }
802 :
803 :
804 : /* Returns the additive inverse of the given number. */
805 :
806 : value *
807 6576 : state::additive_inverse (const value *number)
808 : {
809 6576 : value *result = new value (number->length (), number->is_unsigned);
810 6576 : value one (number->length (), number->is_unsigned);
811 :
812 6576 : size_t size = number->length ();
813 6576 : one.push (new bit (1));
814 6576 : result->push (complement_a_bit ((*number)[0]));
815 :
816 232976 : for (size_t i = 1; i < size; i++)
817 : {
818 226400 : one.push (new bit (0));
819 226400 : result->push (complement_a_bit ((*number)[i]));
820 : }
821 :
822 6576 : value_bit *carry = new bit (0);
823 239552 : for (size_t i = 0; i < size; ++i)
824 : {
825 232976 : value_bit *cur_bit = (*result)[i];
826 232976 : (*result)[i] = full_adder (cur_bit, one[i], &carry);
827 232976 : delete cur_bit;
828 : }
829 :
830 6576 : delete carry;
831 13152 : return result;
832 6576 : }
833 :
834 :
835 : /* Subtracks second value from the first. The result is stored in dest. */
836 :
837 : void
838 6576 : state::do_sub (value *arg1, value *arg2, tree dest)
839 : {
840 6576 : value *neg_arg2 = additive_inverse (arg2);
841 6576 : do_add (arg1, neg_arg2, dest);
842 6576 : delete neg_arg2;
843 6576 : }
844 :
845 :
846 : /* Performs complement operation on a bit. */
847 :
848 : value_bit *
849 232976 : state::complement_a_bit (value_bit *var)
850 : {
851 232976 : value_bit *result = nullptr;
852 232976 : if (is_a<bit *> (var))
853 232976 : result = complement_const_bit (as_a<bit *> (var));
854 : else
855 0 : result = complement_sym_bit (var);
856 :
857 232976 : 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 16791 : state::do_assign (tree arg, tree dest)
904 : {
905 16791 : declare_if_needed (dest, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest))));
906 16791 : if (TREE_CODE (arg) != INTEGER_CST)
907 9790 : declare_if_needed (arg, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (arg))));
908 : else
909 7001 : declare_if_needed (arg, var_states.get (dest)->allocated ());
910 :
911 16791 : value *dest_val = var_states.get (dest);
912 :
913 : /* If the argument is already defined, then we must just copy its bits. */
914 16791 : if (auto arg_val = var_states.get (arg))
915 : {
916 316214 : for (size_t i = 0; i < dest_val->length (); i++)
917 : {
918 306424 : value_bit *new_val = nullptr;
919 306424 : if (i < arg_val->length ())
920 286216 : new_val = (*arg_val)[i]->copy ();
921 : else
922 20208 : new_val = new bit (0);
923 :
924 306424 : delete (*dest_val)[i];
925 306424 : (*dest_val)[i] = new_val;
926 : }
927 : }
928 : /* If the argument is a constant, we must save it as sequence of bits. */
929 7001 : else if (TREE_CODE (arg) == INTEGER_CST)
930 : {
931 7001 : value arg_val
932 7001 : = create_val_for_const (arg, dest_val->length ());
933 251913 : for (size_t i = 0; i < dest_val->length (); i++)
934 : {
935 244912 : delete (*dest_val)[i];
936 244912 : (*dest_val)[i] = arg_val[i]->copy ();
937 : }
938 7001 : }
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 16791 : print_value (var_states.get (dest));
949 16791 : return true;
950 : }
951 :
952 :
953 : /* Assigns pow 2 value. */
954 :
955 : bool
956 273 : state::do_assign_pow2 (tree dest, unsigned pow)
957 : {
958 273 : value *dest_val = var_states.get (dest);
959 0 : unsigned dest_size = dest_val ? dest_val->allocated ()
960 273 : : tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest)));
961 273 : 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 273 : if (!dest_val)
970 : {
971 273 : decl_var (dest, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest))));
972 273 : dest_val = var_states.get (dest);
973 : }
974 : else
975 0 : dest_val->free_bits ();
976 :
977 6065 : for (unsigned i = 0; i < dest_val->length (); i++)
978 : {
979 5792 : if (i == pow)
980 273 : (*dest_val)[i] = new bit (1);
981 : else
982 5519 : (*dest_val)[i] = new bit (0);
983 : }
984 :
985 273 : print_value (dest_val);
986 273 : return true;
987 : }
988 :
989 :
990 : /* Performs NOT operation for constant bit. */
991 :
992 : bit *
993 232976 : state::complement_const_bit (const bit *const_bit)
994 : {
995 232976 : 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 57899 : state::xor_sym_bits (const value_bit *var1, const value_bit *var2)
1012 : {
1013 57899 : value_bit *var2_copy = var2->copy ();
1014 57899 : bit_expression *node2_with_const_child = nullptr;
1015 57899 : bit_expression *parent_of_node2_with_child = nullptr;
1016 57899 : get_parent_with_const_child (var2_copy, node2_with_const_child,
1017 : parent_of_node2_with_child);
1018 :
1019 57899 : 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 57899 : delete var2_copy;
1093 57899 : 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 1420235 : state::xor_const_bits (const bit *const_bit1, const bit *const_bit2)
1101 : {
1102 1420235 : 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 110733 : state::xor_var_const (const value_bit *var, const bit *const_bit)
1110 : {
1111 110733 : if (const_bit->get_val () == 0)
1112 74536 : return var->copy ();
1113 :
1114 36197 : value_bit *var_copy = var->copy ();
1115 36197 : bit_expression *node_with_const_child = nullptr;
1116 36197 : bit_expression *tmp = nullptr;
1117 36197 : get_parent_with_const_child (var_copy, node_with_const_child, tmp);
1118 :
1119 36197 : 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 36197 : delete var_copy;
1139 36197 : 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 94096 : state::get_parent_with_const_child (value_bit *root, bit_expression *&parent,
1148 : bit_expression *&parent_of_parent)
1149 : {
1150 94096 : parent_of_parent = nullptr;
1151 94096 : parent = nullptr;
1152 :
1153 94096 : if (!is_a<bit_expression *> (root))
1154 94096 : 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 3922 : state::shift_left_by_const (const value *number, size_t shift_value)
1199 : {
1200 3922 : value *shift_result = new value (number->length (), number->is_unsigned);
1201 3922 : 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 7844 : for (; i < shift_value; ++i)
1209 3922 : shift_result->push (new bit (0));
1210 122264 : for (size_t j = 0; i < number->length (); ++i, j++)
1211 118342 : shift_result->push (((*number)[j])->copy ());
1212 : }
1213 3922 : 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 5849 : state::check_const_value_equality (value *arg1, value *arg2)
1294 : {
1295 214809 : for (size_t i = 0; i < arg1->length (); i++)
1296 417922 : if (as_a<bit *> ((*arg1)[i])->get_val ()
1297 208961 : != 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 1708 : state::add_equal_cond (tree arg1, tree arg2)
1307 : {
1308 1708 : return add_binary_cond (arg1, arg2, &state::add_equal_cond);
1309 : }
1310 :
1311 :
1312 : /* Adds equality condition for two values. */
1313 :
1314 : void
1315 1708 : state::add_equal_cond (value *arg1, value *arg2)
1316 : {
1317 :
1318 : /* If both arguments are constants then we can evaluate it. */
1319 1708 : 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 67523 : for (size_t i = 0; i < arg1->length (); i++)
1330 : {
1331 129925 : if (is_a<bit *> ((*arg1)[i]) && is_a<bit *> ((*arg2)[i])
1332 194034 : && as_a<bit *> ((*arg1)[i])->get_val ()
1333 64109 : != as_a<bit *> ((*arg2)[i])->get_val ())
1334 : {
1335 0 : last_cond_status = condition_status::CS_FALSE;
1336 0 : return;
1337 : }
1338 : }
1339 :
1340 67523 : 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 65816 : if (is_a<bit *> ((*arg1)[i]) && is_a<bit *> ((*arg2)[i]))
1345 64109 : continue;
1346 :
1347 3414 : conditions.add (new bit_condition ((*arg1)[i]->copy (),
1348 1707 : (*arg2)[i]->copy (),
1349 5121 : EQ_EXPR));
1350 : }
1351 1707 : 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 6738 : state::check_const_value_are_not_equal (value *arg1, value *arg2)
1359 : {
1360 27228 : for (size_t i = 0; i < arg1->length (); i++)
1361 53484 : if (as_a<bit *> ((*arg1)[i])->get_val ()
1362 26742 : != 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 8445 : state::add_not_equal_cond (tree arg1, tree arg2)
1372 : {
1373 8445 : 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 8445 : state::add_not_equal_cond (value *arg1, value *arg2)
1381 : {
1382 8445 : if (is_bit_vector (arg1) && is_bit_vector (arg2))
1383 : {
1384 6738 : bool result = check_const_value_are_not_equal (arg1, arg2);
1385 6738 : last_cond_status = result ? condition_status::CS_TRUE
1386 : : condition_status::CS_FALSE;
1387 6738 : 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 67523 : for (size_t i = 0; i < arg1->length (); i++)
1393 : {
1394 129925 : if (is_a<bit *> ((*arg1)[i]) && is_a<bit *> ((*arg2)[i])
1395 194034 : && as_a<bit *> ((*arg1)[i])->get_val ()
1396 64109 : != as_a<bit *> ((*arg2)[i])->get_val ())
1397 : {
1398 0 : last_cond_status = condition_status::CS_TRUE;
1399 0 : return;
1400 : }
1401 : }
1402 :
1403 1707 : bit_expression *prev = nullptr;
1404 67523 : 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 65816 : if (is_a<bit *> ((*arg1)[i]) && is_a<bit *> ((*arg2)[i]))
1409 64109 : continue;
1410 :
1411 1707 : bit_condition *new_cond = new bit_condition ((*arg1)[i]->copy (),
1412 1707 : (*arg2)[i]->copy (),
1413 5121 : NE_EXPR);
1414 1707 : if (prev)
1415 0 : prev = new bit_or_expression (prev, new_cond);
1416 : else
1417 1707 : prev = new_cond;
1418 : }
1419 :
1420 1707 : last_cond_status = condition_status::CS_SYM;
1421 1707 : 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 1547 : state::add_less_than_cond (tree arg1, tree arg2)
1578 : {
1579 1547 : 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 1547 : state::add_less_than_cond (value *arg1, value *arg2)
1587 : {
1588 1646 : if (is_bit_vector (arg1) && is_bit_vector (arg2)
1589 1646 : && (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 1547 : return;
1595 : }
1596 :
1597 1547 : last_cond_status = condition_status::CS_SYM;
1598 1547 : if (is_bit_vector (arg2) && make_number (arg2) == 0 && !arg1->is_unsigned)
1599 : {
1600 1547 : if (is_a<bit *> (arg1->last ()))
1601 : {
1602 99 : if (as_a<bit *> (arg1->last ())->get_val () == 1)
1603 99 : last_cond_status = condition_status::CS_TRUE;
1604 : else
1605 0 : last_cond_status = condition_status::CS_FALSE;
1606 : }
1607 : else
1608 2896 : conditions.add (new bit_condition (arg1->last ()->copy (), new bit (1),
1609 2896 : EQ_EXPR));
1610 :
1611 1547 : 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 1448 : state::add_greater_or_equal_cond (tree arg1, tree arg2)
1687 : {
1688 1448 : 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 1448 : state::add_greater_or_equal_cond (value *arg1, value *arg2)
1696 : {
1697 1448 : if (is_bit_vector (arg1) && is_bit_vector (arg2)
1698 1448 : && (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 1448 : last_cond_status = condition_status::CS_SYM;
1710 1448 : if (is_bit_vector (arg2) && make_number (arg2) == 0 && !arg1->is_unsigned)
1711 : {
1712 1448 : 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 2896 : conditions.add (new bit_condition (arg1->last ()->copy (), new bit (0),
1721 2896 : EQ_EXPR));
1722 :
1723 1448 : 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 13148 : state::add_binary_cond (tree arg1, tree arg2, binary_cond_func cond_func)
1830 : {
1831 13148 : bool arg1_is_declared = is_declared (arg1);
1832 13148 : bool arg2_is_declared = is_declared (arg2);
1833 :
1834 13148 : 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 13148 : if (arg1_is_declared)
1844 13148 : declare_if_needed (arg2, var_states.get (arg1)->length ());
1845 :
1846 13148 : if (arg2_is_declared)
1847 0 : declare_if_needed (arg1, var_states.get (arg2)->length ());
1848 :
1849 13148 : value *arg1_val = var_states.get (arg1);
1850 13148 : value arg1_const_val (MAX_VALUE_SIZE, false);
1851 :
1852 13148 : 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 13148 : value *arg2_val = var_states.get (arg2);
1860 13148 : value arg2_const_val (MAX_VALUE_SIZE, false);
1861 13148 : if (arg2_val == NULL && TREE_CODE (arg2) == INTEGER_CST)
1862 : {
1863 26296 : arg2_const_val = create_val_for_const (arg2,
1864 26296 : var_states.get (arg1)->length ());
1865 13148 : arg2_val = &arg2_const_val;
1866 : }
1867 :
1868 13148 : (this->*cond_func) (arg1_val, arg2_val);
1869 13148 : print_conditions ();
1870 13148 : return true;
1871 13148 : }
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 288951 : value::value (unsigned size, bool is_unsigned) : is_unsigned (is_unsigned)
1920 : {
1921 288951 : number.create (size);
1922 288951 : }
1923 :
1924 :
1925 : /* Copy constructor for value. */
1926 :
1927 215416 : value::value (const value &other) : is_unsigned (other.is_unsigned)
1928 : {
1929 215416 : number.create (other.length ());
1930 7847768 : for (size_t i = 0; i < other.length (); ++i)
1931 : {
1932 7632352 : value_bit *temp = other[i] ? other[i]->copy () : other[i];
1933 7632352 : number.quick_push (temp);
1934 : }
1935 215416 : }
1936 :
1937 :
1938 : /* Returns pushed bits count. */
1939 :
1940 : unsigned
1941 15100899 : value::length () const
1942 : {
1943 15100899 : return number.length ();
1944 : }
1945 :
1946 :
1947 : /* Wrapper of vec<..>::operator[] for the bit-vector. */
1948 :
1949 : value_bit *&
1950 11943086 : value::operator[] (unsigned i)
1951 : {
1952 11943086 : 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 38407 : value::operator= (const value &other)
1961 : {
1962 76814 : unsigned smallest = number.allocated () < other.length ()
1963 38407 : ? number.allocated () : other.length ();
1964 :
1965 1360799 : for (size_t i = 0; i < smallest; i++)
1966 1322392 : if (i < number.length ())
1967 : {
1968 0 : delete number[i];
1969 0 : number[i] = other[i]->copy ();
1970 : }
1971 : else
1972 1322392 : number.quick_push (other[i]->copy ());
1973 :
1974 425687 : for (size_t i = smallest; i < number.allocated (); i++)
1975 387280 : 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 774560 : number.quick_push (other.is_unsigned
1983 387280 : ? new bit (0) : other[other.length () - 1]->copy ());
1984 :
1985 38407 : return (*this);
1986 : }
1987 :
1988 :
1989 : /* Wrapper of vec<..>::operator[] const for the bit-vector. */
1990 :
1991 : value_bit *
1992 20614668 : value::operator[] (unsigned i) const
1993 : {
1994 20614668 : return number[i];
1995 : }
1996 :
1997 :
1998 : /* Wrapper of vec<..>.exists for the bit-vector. */
1999 :
2000 : bool
2001 41414 : value::exists () const
2002 : {
2003 41414 : return number.exists ();
2004 : }
2005 :
2006 :
2007 : /* Returns the size in bits. */
2008 :
2009 : unsigned
2010 369113 : value::allocated () const
2011 : {
2012 369113 : return number.allocated ();
2013 : }
2014 :
2015 :
2016 : /* Returns a reference the last bit. */
2017 :
2018 : value_bit *&
2019 6494 : value::last ()
2020 : {
2021 6494 : 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 27311 : state::get_last_cond_status ()
2043 : {
2044 27311 : return last_cond_status;
2045 : }
2046 :
2047 :
2048 : /* Prints the given value. */
2049 :
2050 : void
2051 49897 : state::print_value (value *var)
2052 : {
2053 49897 : if (!dump_file || !(dump_flags & TDF_DETAILS))
2054 : return;
2055 :
2056 43627 : fprintf (dump_file, "{");
2057 1514795 : for (int i = var->length () - 1; i >= 0; i--)
2058 : {
2059 1471168 : (*var)[i]->print ();
2060 :
2061 1471168 : if (i)
2062 1427541 : fprintf (dump_file, ", ");
2063 : }
2064 43627 : fprintf (dump_file, "}\n");
2065 : }
2066 :
2067 :
2068 : /* Create LFSR value for the reversed CRC. */
2069 :
2070 : void
2071 125 : state::create_reversed_lfsr (value &lfsr, const value &crc,
2072 : const value &polynomial)
2073 : {
2074 125 : size_t size = polynomial.length ();
2075 :
2076 : /* Determine values of all bits, except MSB. */
2077 3608 : for (size_t i = 0; i < size - 1; i++)
2078 : {
2079 3483 : if (as_a<bit *> (polynomial[i])->get_val ())
2080 1038 : lfsr.push (state::xor_two_bits (crc[i + 1], crc[0]));
2081 : else
2082 2445 : lfsr.push (crc[i + 1]->copy ());
2083 : }
2084 :
2085 : /* Determine value of MSB. */
2086 125 : if (as_a<bit *> (polynomial[size - 1])->get_val ())
2087 117 : lfsr.push (crc[0]->copy ());
2088 : else
2089 8 : lfsr.push (new bit (0));
2090 125 : }
2091 :
2092 :
2093 : /* Create LFSR value for the forward CRC. */
2094 :
2095 : void
2096 116 : state::create_forward_lfsr (value &lfsr, const value &crc,
2097 : const value &polynomial)
2098 : {
2099 116 : size_t size = polynomial.length ();
2100 : /* Determine value of LSB. */
2101 116 : if (as_a<bit *> (polynomial[0])->get_val ())
2102 101 : lfsr.push (crc[size - 1]->copy ());
2103 : else
2104 15 : lfsr.push (new bit (0));
2105 :
2106 : /* Determine values of remaining bits. */
2107 2504 : for (size_t i = 1; i < size; i++)
2108 : {
2109 2388 : if (as_a<bit *> (polynomial[i])->get_val ())
2110 813 : lfsr.push (state::xor_two_bits (crc[i - 1], crc[size - 1]));
2111 : else
2112 1575 : lfsr.push (crc[i - 1]->copy ());
2113 : }
2114 116 : }
2115 :
2116 :
2117 : /* Get the last 1 bit index. */
2118 :
2119 : size_t
2120 261 : last_set_bit (const value &polynomial)
2121 : {
2122 1192 : for (size_t i = 0; i < polynomial.length (); ++i)
2123 : {
2124 1180 : if (as_a<bit *> (polynomial[polynomial.length () - i - 1])->get_val ())
2125 249 : return polynomial.length () - i - 1;
2126 : }
2127 : return 0;
2128 : }
2129 :
2130 :
2131 : /* Create LFSR value. */
2132 :
2133 : value *
2134 261 : state::create_lfsr (tree crc, value *polynomial, bool is_bit_forward)
2135 : {
2136 : /* Check size compatibility․ */
2137 261 : unsigned HOST_WIDE_INT polynomial_length = polynomial->length ();
2138 261 : unsigned HOST_WIDE_INT crc_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (crc)));
2139 261 : 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 261 : 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 261 : if (required_polynomial_size == 0
2156 261 : || 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 241 : value crc_value (polynomial_length, TYPE_UNSIGNED (TREE_TYPE (crc)));
2166 :
2167 6353 : for (unsigned HOST_WIDE_INT i = 0; i < polynomial_length; i++)
2168 6112 : crc_value.push (new symbolic_bit (i, crc));
2169 :
2170 : /* create LFSR vector. */
2171 241 : value *lfsr = new value (polynomial_length, TYPE_UNSIGNED (TREE_TYPE (crc)));
2172 :
2173 : /* Calculate values for LFSR. */
2174 241 : if (is_bit_forward)
2175 116 : create_forward_lfsr (*lfsr, crc_value, *polynomial);
2176 : else
2177 125 : create_reversed_lfsr (*lfsr, crc_value, *polynomial);
2178 :
2179 241 : return lfsr;
2180 241 : }
2181 :
2182 :
2183 : /* Prints added conditions. */
2184 :
2185 : void
2186 13148 : state::print_conditions ()
2187 : {
2188 13148 : if (!dump_file || !(dump_flags & TDF_DETAILS))
2189 2130 : return;
2190 :
2191 11018 : fprintf (dump_file, "Conditions {");
2192 11018 : auto iter = conditions.begin ();
2193 11018 : while (true)
2194 : {
2195 11018 : if (iter != conditions.end ())
2196 : {
2197 10624 : (*iter)->print ();
2198 10624 : ++iter;
2199 : }
2200 :
2201 11018 : if (iter != conditions.end ())
2202 0 : fprintf (dump_file, ", ");
2203 : else
2204 : break;
2205 : }
2206 11018 : fprintf (dump_file, "}\n");
2207 : }
2208 :
2209 :
2210 : /* Pushes the given bit to the end of the bit vector. */
2211 :
2212 : value_bit **
2213 7139304 : value::push (value_bit *elem)
2214 : {
2215 7139304 : return number.quick_push (elem);
2216 : }
2217 :
2218 :
2219 : /* Destructor for value. */
2220 :
2221 504367 : value::~value ()
2222 : {
2223 504367 : free_bits ();
2224 504367 : number.release ();
2225 504367 : }
2226 :
2227 :
2228 : /* Removes given sequence of bits. */
2229 :
2230 : void
2231 504367 : value::free_bits ()
2232 : {
2233 504367 : if (!number.exists ())
2234 : return;
2235 :
2236 16985695 : for (size_t i = 0; i < number.length (); i++)
2237 : {
2238 16481328 : delete number[i];
2239 16481328 : 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 43938 : state::do_operation (tree_code op_code, tree arg1, tree arg2, tree dest)
2386 : {
2387 43938 : switch (op_code)
2388 : {
2389 0 : case BIT_NOT_EXPR:
2390 0 : return do_complement (arg1, dest);
2391 16791 : case NOP_EXPR:
2392 16791 : case SSA_NAME:
2393 16791 : case VAR_DECL:
2394 16791 : case INTEGER_CST:
2395 16791 : return do_assign (arg1, dest);
2396 3730 : case LSHIFT_EXPR:
2397 3730 : return do_binary_operation (arg1, arg2, dest, &state::do_shift_left);
2398 3007 : case RSHIFT_EXPR:
2399 3007 : return do_binary_operation (arg1, arg2, dest, &state::do_shift_right);
2400 1926 : case BIT_AND_EXPR:
2401 1926 : 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 5281 : case BIT_XOR_EXPR:
2405 5281 : return do_binary_operation (arg1, arg2, dest, &state::do_xor);
2406 6617 : case PLUS_EXPR:
2407 6617 : return do_binary_operation (arg1, arg2, dest, &state::do_add);
2408 6576 : case MINUS_EXPR:
2409 6576 : 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 : }
|
