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 : :
24 : : #ifndef SYM_EXEC_STATE_H
25 : : #define SYM_EXEC_STATE_H
26 : :
27 : : #define MAX_VALUE_SIZE 64
28 : :
29 : : #include "sym-exec-expr-is-a-helper.h"
30 : :
31 : : /* Struct used for representing values. */
32 : :
33 : : struct value {
34 : : private:
35 : : /* bit-vector that represents the value. */
36 : : vec<value_bit *> number;
37 : :
38 : : public:
39 : : /* Used for denoting whether the number is unsigned. */
40 : : const bool is_unsigned;
41 : :
42 : : /* Constructor for value. The first argument is the size of the bit-vector
43 : : and the second argument is the sign of the number. */
44 : : value (unsigned size, bool is_unsigned);
45 : :
46 : : /* Copy constructor for value. */
47 : : value (const value &other);
48 : :
49 : : /* Pushes the given bit to the end of the bit-vector. */
50 : : value_bit **push (value_bit *elem);
51 : :
52 : : /* Returns pushed bits count. */
53 : : unsigned length () const;
54 : :
55 : : /* Returns a reference the last bit. */
56 : : value_bit *&last ();
57 : :
58 : : /* Returns the size in bits. */
59 : : unsigned allocated () const;
60 : :
61 : : /* Wrapper of vec<..>.exists for the bit-vector. */
62 : : bool exists () const;
63 : :
64 : : /* Wrapper of vec<..>::operator[] for the bit-vector. */
65 : : value_bit *&operator[] (unsigned i);
66 : :
67 : : /* Assignment operator. If the specified value's size is smaller,
68 : : then 0 constant bit will be assigned to the remaining upper bits. */
69 : : value &operator= (const value &other);
70 : :
71 : : /* Wrapper of vec<..>::operator[] const for the bit-vector. */
72 : : value_bit *operator[] (unsigned i) const;
73 : :
74 : : /* Destructor for value. */
75 : : ~value ();
76 : :
77 : : /* Removes given sequence of bits. */
78 : : void free_bits ();
79 : : };
80 : :
81 : :
82 : : /* Stores states of variables' values on bit-level. */
83 : :
84 : : class state {
85 : : typedef void (state::*binary_func) (value *arg1, value *arg2, tree dest);
86 : : typedef value_bit *(*bit_func) (value_bit *bit1, value_bit *bit2);
87 : : typedef value_bit *(*bit_func3) (value_bit *var1, value_bit *var2,
88 : : value_bit **var3);
89 : : typedef void (state::*binary_cond_func) (value *arg1, value *arg2);
90 : :
91 : : private:
92 : :
93 : : /* Here is stored values by bits of each variable. */
94 : : hash_map<tree, value> var_states;
95 : :
96 : : /* Here is stored conditions of symbolic bits. */
97 : : hash_set<bit_expression *> conditions;
98 : :
99 : : /* The result of last added condition. */
100 : : condition_status last_cond_status = condition_status::CS_NO_COND;
101 : :
102 : : /* Creates value for given constant tree. */
103 : : static value create_val_for_const (tree var, size_t size);
104 : :
105 : : /* Checks if sizes of arguments and destination are compatible. */
106 : : bool check_args_compatibility (tree arg1, tree arg2, tree dest);
107 : :
108 : : /* Adds equality condition for two values. */
109 : : void add_equal_cond (value *arg1, value *arg2);
110 : :
111 : : /* Adds not equal condition for two values. */
112 : : void add_not_equal_cond (value *arg1, value *arg2);
113 : :
114 : : /* Adds greater than condition for two values. */
115 : : void add_greater_than_cond (value *arg1, value *arg2);
116 : :
117 : : /* Adds less than condition for two values. */
118 : : void add_less_than_cond (value *arg1, value *arg2);
119 : :
120 : : /* Adds greater or equal condition for two values. */
121 : : void add_greater_or_equal_cond (value *arg1, value *arg2);
122 : :
123 : : /* Adds less or equal condition for two values. */
124 : : void add_less_or_equal_cond (value *arg1, value *arg2);
125 : :
126 : : /* Does preprocessing and postprocessing for condition adding.
127 : : Handles value creation for constants and their removement in the end. */
128 : : bool add_binary_cond (tree arg1, tree arg2, binary_cond_func cond_func);
129 : :
130 : : /* Constructs expression trees of greater than condition for given values. */
131 : : bit_expression *construct_great_than_cond (value *arg1, value *arg2);
132 : :
133 : : /* Constructs expression trees of less than condition for given values. */
134 : : bit_expression *construct_less_than_cond (value *arg1, value *arg2);
135 : :
136 : : /* Constructs expression trees of equal condition for given values. */
137 : : bit_expression *construct_equal_cond (value *arg1, value *arg2);
138 : :
139 : : /* A wrapper for operations on two bits.
140 : : Operation and operands are passed as arguments. */
141 : : static value_bit *operate_bits (bit_func bit_op, value_bit *bit1,
142 : : value_bit *bit2, value_bit **bit3);
143 : :
144 : : /* A wrapper for operations on three bits.
145 : : Operation and operands are passed as arguments. */
146 : : static value_bit *operate_bits (bit_func3 bit_op, value_bit *bit1,
147 : : value_bit *bit2, value_bit **bit3);
148 : :
149 : : /* Performs the given operation on passed arguments.
150 : : The result is stored in dest. */
151 : : template<class func>
152 : : void operate (value *arg1, value *arg2, value_bit **bit_arg, tree dest,
153 : : func bit_op);
154 : :
155 : : /* Does preprocessing and postprocessing for expressions with tree operands.
156 : : Handles value creation for constant and their removement in the end. */
157 : : bool do_binary_operation (tree arg1, tree arg2, tree dest,
158 : : binary_func bin_func);
159 : :
160 : : /* Performs AND operation on given values. The result is stored in dest. */
161 : : void do_and (value *arg1, value *arg2, tree dest);
162 : :
163 : : /* Performs OR operation on given values. The result is stored in dest. */
164 : : void do_or (value *arg1, value *arg2, tree dest);
165 : :
166 : : /* Performs XOR operation on given values. The result is stored in dest. */
167 : : void do_xor (value *arg1, value *arg2, tree dest);
168 : :
169 : : /* Performs shift right operation on given values.
170 : : The result is stored in dest. */
171 : : void do_shift_right (value *arg1, value *arg2, tree dest);
172 : :
173 : : /* Performs shift left operation on given values.
174 : : The result is stored in dest. */
175 : : void do_shift_left (value *arg1, value *arg2, tree dest);
176 : :
177 : : /* Adds given values. The result is stored in dest. */
178 : : void do_add (value *arg1, value *arg2, tree dest);
179 : :
180 : : /* Subtracks second value from the first. The result is stored in dest. */
181 : : void do_sub (value *arg1, value *arg2, tree dest);
182 : :
183 : : /* Performs AND operation on two bits. */
184 : : static value_bit *and_two_bits (value_bit *arg1, value_bit *arg2);
185 : :
186 : : /* ANDs every bit of the value with var_bit, stroes the result in var1. */
187 : : void and_number_bit (value *var1, value_bit *var_bit);
188 : :
189 : : /* Multiplies given values. The result is stored in dest. */
190 : : void do_mul (value *arg1, value *arg2, tree dest);
191 : :
192 : : /* Performs AND operation for 2 symbolic_bit operands. */
193 : : static value_bit *and_sym_bits (const value_bit *var1,
194 : : const value_bit *var2);
195 : :
196 : : /* Performs AND operation for a symbolic_bit and const_bit operands. */
197 : : static value_bit *and_var_const (const value_bit *var1,
198 : : const bit *const_bit);
199 : :
200 : : /* Performs AND operation for 2 constant bit operands. */
201 : : static bit *and_const_bits (const bit *const_bit1, const bit *const_bit2);
202 : :
203 : : /* Performs OR operation on two bits. */
204 : : static value_bit *or_two_bits (value_bit *arg1_bit, value_bit *arg2_bit);
205 : :
206 : : /* Performs OR operation for 2 symbolic_bit operands. */
207 : : static value_bit *or_sym_bits (const value_bit *var1,
208 : : const value_bit *var2);
209 : :
210 : : /* Performs OR operation for a symbolic_bit and a constant bit operands. */
211 : : static value_bit *or_var_const (const value_bit *var1,
212 : : const bit *const_bit);
213 : :
214 : : /* Performs OR operation for 2 constant bit operands. */
215 : : static bit *or_const_bits (const bit *const_bit1, const bit *const_bit2);
216 : :
217 : : /* Performs complement operation on a bit. */
218 : : static value_bit *complement_a_bit (value_bit *var);
219 : :
220 : : /* Performs NOT operation for constant bit. */
221 : : static bit *complement_const_bit (const bit *const_bit);
222 : :
223 : : /* Performs NOT operation for symbolic_bit. */
224 : : static value_bit *complement_sym_bit (const value_bit *var);
225 : :
226 : : /* Performs XOR operation on two bits. */
227 : : static value_bit *xor_two_bits (value_bit *var1, value_bit *var2);
228 : :
229 : : /* Performs XOR operation for 2 symbolic_bit operands. */
230 : : static value_bit *xor_sym_bits (const value_bit *var1,
231 : : const value_bit *var2);
232 : :
233 : : /* Performs XOR operation for 2 constant bit operands. */
234 : : static bit *xor_const_bits (const bit *const_bit1, const bit *const_bit2);
235 : :
236 : : /* Performs XOR operation for a symbolic_bit and const_bit operands. */
237 : : static value_bit *xor_var_const (const value_bit *var,
238 : : const bit *const_bit);
239 : :
240 : : /* Shift_right operation. Case: var2 is a symbolic value. */
241 : : static value_bit *shift_right_sym_bits (value_bit *var1, value_bit *var2);
242 : :
243 : : /* Shift_left operation. Case: var2 is a symbolic value. */
244 : : static value_bit *shift_left_sym_bits (value_bit *var1, value_bit *var2);
245 : :
246 : : /* Shifts var right by size of shift_value. */
247 : : value *shift_right_by_const (value *var, size_t shift_value);
248 : :
249 : : /* Return node which has a const bit child. Traversal is done based
250 : : on safe branching. */
251 : : static void get_parent_with_const_child (value_bit *root,
252 : : bit_expression *&parent,
253 : : bit_expression *&parent_of_parent);
254 : :
255 : : /* Checks whether state for variable with specified name already
256 : : exists or not. */
257 : : bool is_declared (tree var);
258 : :
259 : : /* Declares given variable if it has not been declared yet. */
260 : : void declare_if_needed (tree var, size_t size);
261 : :
262 : : /* Shifts number left by size of shift_value. */
263 : : value *shift_left_by_const (const value *number, size_t shift_value);
264 : :
265 : : /* Adds two bits and carry value.
266 : : Resturn result and stores new carry bit in "carry". */
267 : : static value_bit *full_adder (value_bit *var1, value_bit *var2,
268 : : value_bit **carry);
269 : :
270 : : /* Returns the additive inverse of the given number. */
271 : : value *additive_inverse (const value *number);
272 : :
273 : : /* Adds two values, stores the result in the first one. */
274 : : void add_numbers (value *var1, const value *var2);
275 : :
276 : : /* Make a copy of given bits. */
277 : : static vec<value_bit *> *make_copy (vec<value_bit *> *bits);
278 : :
279 : : /* Create LFSR value for the reversed CRC. */
280 : : static void create_reversed_lfsr (value &lfsr, const value &crc,
281 : : const value &polynomial);
282 : :
283 : : /* Create LFSR value for the forward CRC. */
284 : : static void create_forward_lfsr (value &lfsr, const value &crc,
285 : : const value &polynomial);
286 : :
287 : : public:
288 : : /* Default constructor for state. */
289 : 3275 : state () = default;
290 : :
291 : : /* Destructor for state. */
292 : : ~state ();
293 : :
294 : : /* Adds an empty state for the given variable. */
295 : : bool decl_var (tree name, unsigned size);
296 : :
297 : : /* Copy constructor for state. It copies all variables and conditions
298 : : of the given state. */
299 : : state (const state &s);
300 : :
301 : : /* Adds the given variable to state. */
302 : : bool add_var_state (tree var, value *state);
303 : :
304 : : /* Remove all states from the states' vector. */
305 : : static void remove_states (vec<state *> *states);
306 : :
307 : : /* Remove all states from the states' vector and release the vector. */
308 : : static void clear_states (vec<state *> *states);
309 : :
310 : : /* Removes all variables added to the state. */
311 : : void clear_var_states ();
312 : :
313 : : /* Removes all conditions added to the state. */
314 : : void clear_conditions ();
315 : :
316 : : /* Adds the given condition to the state. */
317 : : bool add_condition (bit_expression *cond);
318 : :
319 : : /* Bulk add the given conditions to the state. */
320 : : bool bulk_add_conditions (const hash_set<bit_expression *> &conds);
321 : :
322 : : /* Get value of the given variable. */
323 : : value *get_value (tree var);
324 : :
325 : : /* Get the value of the tree, which is in the beginning of the var_states. */
326 : : value *get_first_value ();
327 : :
328 : : /* Returns the list of conditions in the state. */
329 : : const hash_set<bit_expression *> &get_conditions ();
330 : :
331 : : /* Adds a variable with unknown value to state. Such variables are
332 : : represented as sequence of symbolic bits. */
333 : : bool make_symbolic (tree var, unsigned size);
334 : :
335 : : /* Returns size of the given variable. */
336 : : unsigned get_var_size (tree var);
337 : :
338 : : /* Prints the given value. */
339 : : static void print_value (value *var);
340 : :
341 : : /* Prints added conditions. */
342 : : void print_conditions ();
343 : :
344 : : /* Returns the number represented by the value. */
345 : : static unsigned HOST_WIDE_INT
346 : : make_number (const value *var);
347 : :
348 : : /* Checks if all bits of the given value have constant bit type. */
349 : : static bool is_bit_vector (const value *var);
350 : :
351 : : /* Performs the specified operation on passed variables. */
352 : : bool do_operation (tree_code op_code, tree arg1, tree arg2, tree dest);
353 : :
354 : : /* Does Assignment. */
355 : : bool do_assign (tree arg, tree dest);
356 : :
357 : : /* Assigns pow 2 value. */
358 : : bool do_assign_pow2 (tree dest, unsigned pow);
359 : :
360 : : /* Negates given variable. */
361 : : bool do_complement (tree arg, tree dest);
362 : :
363 : : /* Adds EQUAL condition of given variables to state. */
364 : : bool add_equal_cond (tree arg1, tree arg2);
365 : :
366 : : /* Adds NOT EQUAL condition of given variables to state. */
367 : : bool add_not_equal_cond (tree arg1, tree arg2);
368 : :
369 : : /* Adds GREATER THAN condition of given variables to state. */
370 : : bool add_greater_than_cond (tree arg1, tree arg2);
371 : :
372 : : /* Adds LESS THAN condition of given variables to state. */
373 : : bool add_less_than_cond (tree arg1, tree arg2);
374 : :
375 : : /* Adds GREATER OR EQUAL condition of given variables to state. */
376 : : bool add_greater_or_equal_cond (tree arg1, tree arg2);
377 : :
378 : : /* Adds LESS OR EQUAL condition of given variables to state. */
379 : : bool add_less_or_equal_cond (tree arg1, tree arg2);
380 : :
381 : : /* Adds a bool condition to state. */
382 : : bool add_bool_cond (tree arg);
383 : :
384 : : /* Checks whether the given two constant values are equal. */
385 : : static bool check_const_value_equality (value *arg1, value *arg2);
386 : :
387 : : /* Checks whether the given two constant values are not equal. */
388 : : static bool check_const_value_are_not_equal (value *arg1, value *arg2);
389 : :
390 : : /* Checks whether the first given constant value
391 : : is greater than the second one. */
392 : : static bool check_const_value_is_greater_than (value *arg1, value *arg2);
393 : :
394 : : /* Checks whether the first given constant value
395 : : is less than the second one. */
396 : : static bool check_const_value_is_less_than (value *arg1, value *arg2);
397 : :
398 : : /* For the given value_bit, iterates over its expression tree, complements
399 : : those bit which came from the given origin. */
400 : : static value_bit *complement_bits_with_origin (value_bit *root, tree origin);
401 : :
402 : : /* Iterates over every bit of the given value and complements their
403 : : expression trees' those bits, that came from the given origin. */
404 : : static void complement_val_bits_with_origin (value *val, tree origin);
405 : :
406 : : /* Complements all bits of all values that came from the given origin. */
407 : : void complement_all_vars_bits_with_origin (tree origin);
408 : :
409 : : /* Complements all bits with the given origin of all added conditions. */
410 : : void complement_conditions_with_origin (tree origin);
411 : :
412 : : /* Complements all bits with the given origin of all values
413 : : and added conditions. */
414 : : void complement_state_with_origin (tree origin);
415 : :
416 : : /* Returns status of last added condition. */
417 : : condition_status get_last_cond_status ();
418 : :
419 : : /* Create LFSR value. */
420 : : static value *create_lfsr (tree crc, value *polynomial, bool is_bit_forward);
421 : : };
422 : :
423 : :
424 : : /* Returns the minimum of A, B, C. */
425 : :
426 : : size_t min (size_t a, size_t b, size_t c);
427 : :
428 : :
429 : : /* Performs the given operation on passed arguments.
430 : : The result is stored in dest. */
431 : :
432 : : template<class func>
433 : : void
434 : 19558 : state::operate (value *arg1, value *arg2, value_bit **bit_arg, tree dest,
435 : : func bit_op)
436 : : {
437 : 19558 : value *dest_var = var_states.get (dest);
438 : 19558 : size_t min_iter = min (arg1->length (), arg2->length (), dest_var->length ());
439 : :
440 : 19558 : size_t i = 0;
441 : 717910 : for (; i < min_iter; i++)
442 : : {
443 : 698352 : value_bit *temp = (*var_states.get (dest))[i];
444 : 698352 : (*var_states.get (dest))[i] = operate_bits (bit_op, (*arg1)[i],
445 : : (*arg2)[i], bit_arg);
446 : 698352 : delete temp;
447 : : }
448 : :
449 : 19558 : if (i >= dest_var->length ())
450 : : return;
451 : :
452 : 0 : value *biggest = arg1;
453 : 0 : value_bit *sign_bit = (*arg2)[i - 1];
454 : 0 : if (arg2->length () > arg1->length ())
455 : : {
456 : 0 : biggest = arg2;
457 : 0 : sign_bit = (*arg1)[i - 1];
458 : : }
459 : :
460 : 0 : min_iter = min (biggest->length (), dest_var->length (), dest_var->length ());
461 : 0 : for (; i < min_iter; i++)
462 : : {
463 : 0 : value_bit *temp = (*var_states.get (dest))[i];
464 : 0 : (*var_states.get (dest))[i] = operate_bits (bit_op, (*biggest)[i],
465 : : sign_bit, bit_arg);
466 : 0 : delete temp;
467 : : }
468 : :
469 : 0 : if (i >= dest_var->length ())
470 : : return;
471 : :
472 : 0 : sign_bit = (*biggest)[i - 1];
473 : 0 : for (; i < dest_var->length (); i++)
474 : : {
475 : 0 : value_bit *temp = (*var_states.get (dest))[i];
476 : 0 : (*var_states.get (dest))[i] = operate_bits (bit_op, sign_bit, sign_bit,
477 : : bit_arg);
478 : 0 : delete temp;
479 : : }
480 : : }
481 : :
482 : : #endif /* SYM_EXEC_STATE_H. */
|
