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.

7 files changed, 242 insertions, 46 deletions

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<bit *> (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<bit *> (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 <stdio.h>
+
+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 <stdint.h>
+ 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 <stdint.h>
+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 <stdint.h>
+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"} } */
+
+