From 1c76a5f50d28e0ca91fef42884a5b9068a8ad61e Mon Sep 17 00:00:00 2001 From: Mariam Arutunian Date: Fri, 9 Dec 2022 16:55:18 +0400 Subject: Added LFSR matching v1: - Added functions to check whether LFSR and returned states match (it's not complete). Changes in Traverse and execute CRC function v7: - Pass correct tree to do_mem_ref function Changes in Sym_exec v8: - Added get_first_value () function in state class to get state's first value. --- gcc/gimple-crc-optimization.cc | 17 ++++- gcc/sym-exec/state.cc | 7 ++ gcc/sym-exec/state.h | 3 + gcc/symb-execute-all-paths.cc | 155 ++++++++++++++++++++++++++++++++++++++++- gcc/symb-execute-all-paths.h | 7 ++ 5 files changed, 186 insertions(+), 3 deletions(-) diff --git a/gcc/gimple-crc-optimization.cc b/gcc/gimple-crc-optimization.cc index dd1595ad261..12868acd337 100644 --- a/gcc/gimple-crc-optimization.cc +++ b/gcc/gimple-crc-optimization.cc @@ -957,7 +957,22 @@ crc_optimization::execute (function *fun) state::print_bits (lfsr); } } - /* TODO: Match LFSR. */ + + if (symb_exec.states_match_lfsr (lfsr)) + { + if (dump_file) + { + fprintf (dump_file, "The function really calculates CRC " + "and returns it!\n"); + } + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Returned state and LFSR differ.\n"); + } + } } return 0; } diff --git a/gcc/sym-exec/state.cc b/gcc/sym-exec/state.cc index 301f11acef6..b32239dae90 100644 --- a/gcc/sym-exec/state.cc +++ b/gcc/sym-exec/state.cc @@ -58,6 +58,13 @@ state::get_bits (tree var) return var_states.get (var); } +/* Get the value of the tree, which is in the beginning of the var_states. */ + +vec * +state::get_first_value () +{ + return &(*(var_states.begin ())).second; +} const hash_set& state::get_conditions () diff --git a/gcc/sym-exec/state.h b/gcc/sym-exec/state.h index c032212aa9c..9a4231cfe1d 100644 --- a/gcc/sym-exec/state.h +++ b/gcc/sym-exec/state.h @@ -230,6 +230,9 @@ class state { vec * get_bits (tree var); + /* Get the value of the tree, which is in the beginning of the var_states. */ + vec * get_first_value (); + const hash_set& get_conditions (); /* Adds a variable with unknown value to state. Such variables are diff --git a/gcc/symb-execute-all-paths.cc b/gcc/symb-execute-all-paths.cc index 07b4b7238c8..a9db491ee5c 100644 --- a/gcc/symb-execute-all-paths.cc +++ b/gcc/symb-execute-all-paths.cc @@ -141,7 +141,10 @@ crc_symb_execution::execute_assign_statement (const gassign *gs) return true; return false; case MEM_REF: - if (current_state->do_mem_ref (op1, lhs)) + /* FIXME: There can be something like + MEM[(some_type *)data + 1B], + in this case we just pass data. */ + if (current_state->do_mem_ref (TREE_OPERAND (op1, 0), lhs)) return true; return false; case NOP_EXPR: @@ -682,7 +685,7 @@ bool crc_symb_execution::execute_crc_loop (loop *crc_loop, gphi *crc, gphi *data, bool is_shift_left) { - if (dump_file) + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "\n\nTrying to calculate the polynomial.\n\n"); states.quick_push (new state); @@ -786,4 +789,152 @@ crc_symb_execution::extract_poly_and_create_lfsr (loop *crc_loop, } return state::create_lfsr (calculated_crc, polynomial, is_shift_left); +} + +bool +condition_is_true () +{ + return true; +} + +bool +condition_is_false () +{ + return true; +} + + +/* Returns true if the symb_exp is a bit_xor_expression and const_bit equals 1. + Otherwise, returns false. */ +bool +is_one (value * const_bit) +{ + return is_a (const_bit) + && (as_a (const_bit))->get_val () == 1; +} + + +/* Returns true if bit is symbolic and its index differs from LFSR bit's index + by a factor of 8. + Sometimes calculated crc value is returned + after being shifted by 8's factor. */ +bool +is_a_valid_symb (value* bit, size_t lfsr_bit_index) +{ + if (!is_a (bit)) + return false; + + size_t sym_bit_index = (as_a (bit))->get_index (); + + size_t diff; + if (sym_bit_index > lfsr_bit_index) + diff = sym_bit_index - lfsr_bit_index; + else + diff = lfsr_bit_index - sym_bit_index; + + /* Indexes of the symbolic bit may differ by 0, 8, 16, 24, 32, ... */ + return diff % 8 == 0; +} + + +/* Returns true if bit is a bit_xor_expression + and xor-ed values are valid symbolic bits. + Otherwise, returns false. */ +bool +is_a_valid_xor (value* bit, size_t index) +{ + return is_a (bit) + && is_a_valid_symb ((as_a (bit))->get_left (), + index) + && is_a_valid_symb ((as_a (bit))->get_right (), + index); +} + + +/* Returns true if bit is a valid bit_xor_expression with 1. + Otherwise, returns false. */ +bool +is_a_valid_xor_one (value* bit, size_t index) +{ + if (is_a (bit)) + { + value * symb_exp = nullptr; + bit_xor_expression * xor_exp = as_a (bit); + if (is_one (xor_exp->get_right ())) + symb_exp = xor_exp->get_left (); + else if (is_one (xor_exp->get_left ())) + symb_exp = xor_exp->get_right (); + else + return false; + return is_a_valid_xor (symb_exp, index) + || is_a_valid_symb (symb_exp, index); + } + else + return false; +} + + +/* Returns true if the state matches the LFSR, otherwise - false. */ +bool +crc_symb_execution::state_matches_lfsr (const vec &lfsr, + const vec &crc_state) +{ + for (size_t i = 0; i < lfsr.length () && crc_state.length (); i++) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Checking %lu-th bit.\n", i); + + if (is_a (lfsr[i])) + { + size_t index = (as_a (lfsr[i]))->get_left () + ->get_index (); + if (!(((is_a_valid_xor_one (crc_state[i], index) + && condition_is_true ()) + || (is_a_valid_symb (crc_state[i], index) && condition_is_false ())) + || ((is_a_valid_xor_one (crc_state[i], index) && condition_is_true ()) + || (is_a_valid_xor (crc_state[i], index) && condition_is_false ())))) + return false; + } + else if (is_a (lfsr[i])) + { + size_t index = (as_a (lfsr[i]))->get_index (); + if (!(is_a_valid_symb (crc_state[i], index) + || is_a_valid_xor (crc_state[i], index) + || condition_is_false ())) + return false; + } + else if (is_a (lfsr[i])) + { + if (!is_a (crc_state[i]) || as_a (lfsr[i])->get_val () + != as_a (crc_state[i])->get_val ()) + return false; + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Not expected expression in LFSR.\n"); + return false; + } + } + return true; +} + +/* Returns true if all states match the LFSR, otherwise - false. */ +bool +crc_symb_execution::states_match_lfsr (vec * lfsr) +{ + while (!final_states.is_empty ()) + { + state * final_state = final_states.last (); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Matching LFSR and following returned state.\n"); + state::print_bits (final_state->get_first_value ()); + } + if (!state_matches_lfsr (*lfsr, *(final_state->get_first_value ()))) + return false; + final_states.pop (); + delete final_state; + } + return true; } \ No newline at end of file diff --git a/gcc/symb-execute-all-paths.h b/gcc/symb-execute-all-paths.h index 7177a3fc222..4d07498d32b 100644 --- a/gcc/symb-execute-all-paths.h +++ b/gcc/symb-execute-all-paths.h @@ -94,7 +94,11 @@ class crc_symb_execution { to calculate the polynomial. */ bool execute_crc_loop (loop *, gphi *, gphi *, bool); + /* Returns true if the state matches the LFSR, otherwise - false. */ + bool state_matches_lfsr (const vec &, const vec &); + public: + /* Symbolically execute the function and keep final states. */ bool execute_function (function *); @@ -102,6 +106,9 @@ class crc_symb_execution { with concrete values. */ vec * extract_poly_and_create_lfsr (loop *, gphi *, gphi *, bool); + /* Returns true if all states match the LFSR, otherwise - false. */ + bool states_match_lfsr (vec *lfsr); + crc_symb_execution () { /* Reserve memory for the vectors of states. */ -- cgit v1.2.1