From a03a032ab877b5af72f3b6fb352c4a4d642fd2ec Mon Sep 17 00:00:00 2001 From: Mariam Arutunian Date: Fri, 13 Jan 2023 17:47:45 +0400 Subject: Changes in CRC detection v6: - Fixed memeory leaks caused by get_loop_body_in_dom_order function. - Added function, to find if in if implementations. The case, when after checking the MSB/LSB being 1, there is another check, where crc;s value is modified. - Refactored and added missing description of can_not_be_shift_of_crc function. Changes in Traverse and execute CRC function v10: - Added a check for debug statements, skipped those statments during symbolic execution. Changes in LFSR creation v6: - Return null if there is no one in the polynomial, when searching for last one in last_set_bit. - Create resuced size LFSR in create_forward_lfsr function. Addition in testsuit: - Added crc-26.c, crc-crc-reverse.c, crc-crc.c, crc-if-in-if.c tests. --- gcc/crc_verification.cc | 6 +- gcc/gimple-crc-optimization.cc | 149 +++++++++++++++++++++++---------- gcc/sym-exec/state.cc | 7 +- gcc/testsuite/gcc.dg/crc-26.c | 28 +++++++ gcc/testsuite/gcc.dg/crc-crc-reverse.c | 29 +++++++ gcc/testsuite/gcc.dg/crc-crc.c | 31 +++++++ gcc/testsuite/gcc.dg/crc-if-in-if.c | 38 +++++++++ 7 files changed, 242 insertions(+), 46 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/crc-26.c create mode 100644 gcc/testsuite/gcc.dg/crc-crc-reverse.c create mode 100644 gcc/testsuite/gcc.dg/crc-crc.c create mode 100644 gcc/testsuite/gcc.dg/crc-if-in-if.c diff --git a/gcc/crc_verification.cc b/gcc/crc_verification.cc index df010742112..0f02212dd5b 100644 --- a/gcc/crc_verification.cc +++ b/gcc/crc_verification.cc @@ -548,6 +548,9 @@ crc_symbolic_execution::execute_bb_gimple_statements (basic_block bb, return false; return true; } + /* Just skip debug statements. */ + case GIMPLE_DEBUG: + break; default: { if (dump_file) @@ -817,7 +820,8 @@ crc_symbolic_execution::execute_crc_loop (class loop *crc_loop, gphi *crc, if (states.length () != 1) { if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "The number of states is not one.\n"); + fprintf (dump_file, "The number of states is not one when executed " + "the loop for calculating the polynomial.\n"); return false; } return true; diff --git a/gcc/gimple-crc-optimization.cc b/gcc/gimple-crc-optimization.cc index b362ea3e84e..7820214c1a4 100644 --- a/gcc/gimple-crc-optimization.cc +++ b/gcc/gimple-crc-optimization.cc @@ -92,29 +92,34 @@ class crc_optimization { } /* This is the main function which checks whether given function - calculates CRC and extracts the details of the CRC calculation. - The main idea is to find innermost loop with 8, 16, 24, 32 iterations. - Find xor in the loop (xor is the key operation for naive crc calculation). - Check that before/after being xor-ed the variable is shifted by one. - Xor must be done under condition of MSB/LSB being 1. */ + calculates CRC and extracts the details of the CRC calculation. + The main idea is to find innermost loop with 8, 16, 24, 32 iterations. + Find xor in the loop (xor is the key operation for naive crc calculation). + Check that before/after being xor-ed the variable is shifted by one. + Xor must be done under condition of MSB/LSB being 1. */ bool function_may_calculate_crc (function *fun); /* Checks the loop iteration number. - The loop for CRC calculation may do 8, 16, 24, 32 iterations. */ + The loop for CRC calculation may do 8, 16, 24, 32 iterations. */ bool maybe_crc_iteration_count (class loop *func_loop); + /* Finds and returns the block of a condition which is the destination + block of the block containing the check of MSB/LSB being 1. + If the block is found returns it, else returns nullptr. */ + basic_block find_block_of_internal_condition (basic_block xor_bb); + /* Check whether found xor_stmt is for calculating crc. - The function crc_fun calculates crc only if there is a shift operation - in the crc_loop. */ + The function crc_fun calculates crc only if there is a shift operation + in the crc_loop. */ bool xor_calculates_crc (function *crc_fun, class loop *crc_loop, const gimple *stmt); /* This function goes up through the def-chain of the name, - until doesn't encounter a phi statement or - if it does not meet certain conditions - depending on the passed continue_to_check_dep function. - The continue_to_check_dep may be the check_def_stmt_for_xor - or check_def_stmt_for_if function. */ + until doesn't encounter a phi statement or + if it does not meet certain conditions + depending on the passed continue_to_check_dep function. + The continue_to_check_dep may be the check_def_stmt_for_xor + or check_def_stmt_for_if function. */ void get_dep (tree name, bool (crc_optimization::*continue_to_check_dep) (gimple *stmt)); @@ -135,14 +140,14 @@ class crc_optimization { bool continue_to_check_dep_for_if (gimple *stmt); /* This function checks that xor is done under the condition - of MSB/LSB being one. - Checks that if condition's variable and xor-ed variable - depend on same variable and if there is a shift 1 in the same block with xor, - on the opposite branch must be another shift 1 to the same direction. - xor_bb is the basic block, where xor operation is done. - pred_bb is the predecessor basic block of the xor_bb, - it is assumed that the last stmt of pred_bb checks the condition - under which xor is done. */ + of MSB/LSB being one. + Checks that if condition's variable and xor-ed variable + depend on same variable and if there is a shift 1 in the same block with + xor, on the opposite branch must be another shift 1 to the same direction. + xor_bb is the basic block, where xor operation is done. + pred_bb is the predecessor basic block of the xor_bb, + it is assumed that the last stmt of pred_bb checks the condition + under which xor is done. */ bool crc_cond_and_shift (const basic_block &pred_bb, const basic_block &xor_bb); @@ -161,6 +166,12 @@ class crc_optimization { otherwise the loop isn't calculating CRC. */ void find_shift_after_xor (class loop *crc_loop, tree lhs); + /* Checks whether assigment statement does shift operation + (checks that shift 1 is done), + if it doesn't - checks whether it is acceptable operation + to be between shift and xor. + find_shift_before_xor argument is for checking whether we search for shift + before xor or after. */ bool can_not_be_shift_of_crc (gimple *assign_stmt, bool find_shift_before_xor); @@ -213,6 +224,7 @@ set_loop_statements_not_visited (class loop *loop) gimple_set_visited (stmt, false); } } + free (bbs); } @@ -761,6 +773,47 @@ crc_optimization::continue_to_check_dep_for_if (gimple *def_stmt) return true; } +/* In the case when xor's block doesn't have single predecessor, + we need to check whether it's parent blocks have single predecessor, + and it's the same block for both predecessor blocks. + If it is, most probably that block's predecessor may contain the check + for MSB/LSB being one. + + This function searches the block of a condition which is the destination + block of the block containing the check of MSB/LSB being 1. + If the block is found returns it, else returns nullptr. + + Here we can detect implementations like the following: + if ((crc & 0x80) != 0) + { + crc = (byte)(crc << 1); + crc = ((byte)(b & (1 << i)) != 0) //block_of_internal_condition + ? (byte)(crc | 0x01) : (byte)(crc & 0xFE); + crc = (byte)(crc ^ generator); + } + else + { + crc = (byte)(crc << 1); + crc = ((byte)(b & (1 << i)) != 0) + ? (byte)(crc | 0x01) : (byte)(crc & 0xFE); + } +*/ + +basic_block +crc_optimization::find_block_of_internal_condition (basic_block xor_bb) +{ + basic_block parent_bb = EDGE_PRED (xor_bb, 0)->src; + basic_block block_of_internal_condition = EDGE_PRED (parent_bb, 0)->src; + + for (size_t i = 1; i < EDGE_COUNT (xor_bb->preds); ++i) + { + edge e = EDGE_PRED (xor_bb, i); + if (!(single_pred_p (e->src) + && EDGE_PRED (e->src, 0)->src == block_of_internal_condition)) + return nullptr; + } + return block_of_internal_condition; +} /* Check whether found xor_stmt is for calculating crc. The function crc_fun calculates crc only if there is a shift operation @@ -804,37 +857,43 @@ crc_optimization::xor_calculates_crc (function *crc_fun, class loop *crc_loop, check for its pair in another branch. If all checks succeed, then it is a crc. */ basic_block bb = gimple_bb (xor_stmt); - if (single_pred_p (bb)) + if (!single_pred_p (bb)) { - if (crc_cond_and_shift (single_pred (bb), bb)) + bb = find_block_of_internal_condition (bb); + if (!bb || !single_pred_p (bb)) { - set_all_statements_not_visited (crc_fun); - bool crc_is_returned = returned_value_depends_on_crc (crc_var); if (dump_file) - { - if (crc_is_returned) - { - fprintf (dump_file, - "\n%s function maybe calculates CRC " - "and returns it.\n", - function_name (crc_fun)); - } - else - { - fprintf (dump_file, - "\n%s function maybe calculates CRC.\n", - function_name (crc_fun)); - } - } - return true; + fprintf (dump_file, + "Xor bb doesn't have single predecessor.\n"); + return false; } } - else + + basic_block block_of_condition = single_pred (bb); + + if (crc_cond_and_shift (block_of_condition, bb)) { + set_all_statements_not_visited (crc_fun); + bool crc_is_returned = returned_value_depends_on_crc (crc_var); if (dump_file) - fprintf (dump_file, - "Xor bb doesn't have single predecessor.\n"); + { + if (crc_is_returned) + { + fprintf (dump_file, + "\n%s function maybe calculates CRC " + "and returns it.\n", + function_name (crc_fun)); + } + else + { + fprintf (dump_file, + "\n%s function maybe calculates CRC.\n", + function_name (crc_fun)); + } + } + return true; } + return false; } @@ -924,11 +983,13 @@ crc_optimization::function_may_calculate_crc (function *fun) { set_return_value_size (fun); print_crc_information (); + free (bbs); return true; } } } } + free (bbs); } return false; } diff --git a/gcc/sym-exec/state.cc b/gcc/sym-exec/state.cc index 1dc685a85ab..ab92f5bc86f 100644 --- a/gcc/sym-exec/state.cc +++ b/gcc/sym-exec/state.cc @@ -1955,6 +1955,7 @@ last_set_bit (const value &polynomial) if (as_a (polynomial[polynomial.length () - i - 1])->get_val ()) return polynomial.length () - i - 1; } + return 0; } /* Create LFSR value for the reversed CRC. */ @@ -1966,6 +1967,8 @@ state::create_reversed_lfsr (value &lfsr, const value &crc, /* Get the minimal byte size to keep the polynomial. Ie, if the last 1 bit of the polynomial is at 6 index, size will be 8. */ size_t size = ((last_set_bit (polynomial)/8) + 1) * 8; + if (size == 0) + return; /* Determine values of all bits, except MSB. */ for (size_t i = 0; i < size - 1; i++) @@ -1990,7 +1993,9 @@ void state::create_forward_lfsr (value &lfsr, const value &crc, const value &polynomial) { - size_t size = crc.length (); + size_t size = ((last_set_bit (polynomial)/8) + 1) * 8; + if (size == 0) + return; /* Determine value of LSB. */ if (as_a (polynomial[0])->get_val ()) diff --git a/gcc/testsuite/gcc.dg/crc-26.c b/gcc/testsuite/gcc.dg/crc-26.c new file mode 100644 index 00000000000..298fb39c375 --- /dev/null +++ b/gcc/testsuite/gcc.dg/crc-26.c @@ -0,0 +1,28 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-crc-details" } */ + +#include + +typedef unsigned char uint8_t; + +uint8_t gencrc (uint8_t *data) +{ + uint8_t crc = 0xff; + size_t j; + crc ^= *data; + for (j = 0; j < 8; j++) + { + if ((crc & 0x80) != 0) + crc = (uint8_t) ((crc << 1) ^ 0x31); + else + crc <<= 1; + } + return crc; +} + +/* { dg-final { scan-tree-dump "gencrc function maybe calculates CRC and returns it." "crc"} } */ +/* { dg-final { scan-tree-dump "Return size is 8" "crc"} } */ +/* { dg-final { scan-tree-dump "Loop iteration number is 7" "crc"} } */ +/* { dg-final { scan-tree-dump "Bit forward" "crc"} } */ +/* { dg-final { scan-tree-dump "Executing \[a-zA-Z_\]\[a-zA-Z0-9_\]* = \[a-zA-Z_\]\[a-zA-Z0-9_\]* \\\^ \[a-zA-Z0-9_\]+\(\\\(\[a-zA-Z\]\\\)\)?;" "crc" } } */ +/* { dg-final { scan-tree-dump "Executing \[a-zA-Z_\]\[a-zA-Z0-9_\]* = \[a-zA-Z_\]\[a-zA-Z0-9_\]* \(<<|>>\) \[0-9]+;" "crc" } } */ \ No newline at end of file diff --git a/gcc/testsuite/gcc.dg/crc-crc-reverse.c b/gcc/testsuite/gcc.dg/crc-crc-reverse.c new file mode 100644 index 00000000000..3b959fe0d13 --- /dev/null +++ b/gcc/testsuite/gcc.dg/crc-crc-reverse.c @@ -0,0 +1,29 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-crc-details" } */ + + #include + uint32_t crc24_reverse(uint32_t crc, const uint8_t *data, uint8_t len) + { + uint32_t state = crc; + uint8_t i; + + for (i = 0; i < len; i++) { + uint8_t n, cur = data[len - i - 1]; + + for (n = 0; n < 8; n++) { + int top_bit = state >> 23; + + state = (state << 1) & 0xffffff; + state |= top_bit ^ ((cur >> (7 - n)) & 1); + if (top_bit) + state ^= 0xb4c000; + } + } + + return state; + } + +/* { dg-final { scan-tree-dump "crc24_reverse function maybe calculates CRC and returns it." "crc"} } */ +/* { dg-final { scan-tree-dump "Return size is 32" "crc"} } */ +/* { dg-final { scan-tree-dump "Loop iteration number is 7" "crc"} } */ +/* { dg-final { scan-tree-dump "Bit forward" "crc"} } */ \ No newline at end of file diff --git a/gcc/testsuite/gcc.dg/crc-crc.c b/gcc/testsuite/gcc.dg/crc-crc.c new file mode 100644 index 00000000000..e501c9f8c39 --- /dev/null +++ b/gcc/testsuite/gcc.dg/crc-crc.c @@ -0,0 +1,31 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-crc-details" } */ + +#include +uint32_t crc24_calculate(uint32_t preset, const uint8_t *data, uint8_t len) +{ + uint32_t state = preset; + uint8_t i; + + for (i = 0; i < len; i++) { + uint8_t n, cur = data[i]; + + for (n = 0; n < 8; n++) { + int next_bit = (state ^ cur) & 1; + + cur >>= 1; + state >>= 1; + if (next_bit) { + state |= 1 << 23; + state ^= 0x5a6000; + } + } + } + + return state; +} + +/* { dg-final { scan-tree-dump "crc24_calculate function maybe calculates CRC and returns it." "crc"} } */ +/* { dg-final { scan-tree-dump "Return size is 32" "crc"} } */ +/* { dg-final { scan-tree-dump "Loop iteration number is 7" "crc"} } */ +/* { dg-final { scan-tree-dump "Bit reverse" "crc"} } */ \ No newline at end of file diff --git a/gcc/testsuite/gcc.dg/crc-if-in-if.c b/gcc/testsuite/gcc.dg/crc-if-in-if.c new file mode 100644 index 00000000000..df8258e2bcd --- /dev/null +++ b/gcc/testsuite/gcc.dg/crc-if-in-if.c @@ -0,0 +1,38 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-crc" } */ +#include +typedef uint8_t byte; +byte Compute_CRC8_Simple_OneByte_ShiftReg (byte byteVal) +{ + const byte generator = 0x1D; + byte crc = 0; /* init crc register with 0 */ + byte b = byteVal; + for (int i = 7; i >= 0; i--) + { + /* check if MSB is set */ + if ((crc & 0x80) != 0) + { /* MSB set, shift it out of the register */ + crc = (byte) (crc << 1); + /* shift in next bit of input stream: + * If it's 1, set LSB of crc to 1. + * If it's 0, set LSB of crc to 0. */ + crc = ((byte) (b & (1 << i)) != 0) ? (byte) (crc | 0x01) + : (byte) (crc & 0xFE); + /* Perform the 'division' by XORing the crc register with the generator polynomial */ + crc = (byte) (crc ^ generator); + } + else + { /* MSB not set, shift it out and shift in next bit of input stream. Same as above, just no division */ + crc = (byte) (crc << 1); + crc = ((byte) (b & (1 << i)) != 0) ? (byte) (crc | 0x01) + : (byte) (crc & 0xFE); + } + } + return crc; +} +/* { dg-final { scan-tree-dump "Compute_CRC8_Simple_OneByte_ShiftReg function maybe calculates CRC and returns it." "crc"} } */ +/* { dg-final { scan-tree-dump "Return size is 8" "crc"} } */ +/* { dg-final { scan-tree-dump "Loop iteration number is 7" "crc"} } */ +/* { dg-final { scan-tree-dump "Bit forward" "crc"} } */ + + -- cgit v1.2.1