Changes in CRC code generation v3:

     - Added polynomial long division in GF (2^n) algorithm (gf2n_poly_long_div_quotient function).

    Changes in  Extract polynomial v3:

     - Split extract_poly_and_create_lfsr function into two functions.
     - Changed extract_poly_and_create_lfsr function's name to extract_polynomial, returnes pair of values,
        one for calculated polynomial, the other for the tree.

3 files changed, 95 insertions, 18 deletions

diff --git a/gcc/crc_verification.cc b/gcc/crc_verification.cc
index 942a8a704c0..d2addd45263 100644
--- a/gcc/crc_verification.cc
+++ b/gcc/crc_verification.cc
@@ -845,16 +845,26 @@ polynomial_is_known (const value *polynomial)
 
 
 /* Execute the loop, which is expected to calculate CRC,
-   to extract polynomial, assigning real numbers to crc and data.  */
-
-value *
-crc_symbolic_execution::extract_poly_and_create_lfsr (class loop *crc_loop,
-						      gphi *crc, gphi *data,
-						      bool is_shift_left)
+   to extract polynomial, assigning real numbers to crc and data.
+   Returns a pair, first value of the pair is the tree containing
+   the value of the polynomial,
+   second is the calculated polynomial. Pair may contain nullptr.  */
+
+std::pair <tree, value *>
+crc_symbolic_execution::extract_polynomial (class loop *crc_loop,
+					    gphi *crc, gphi *data,
+					    bool is_shift_left)
 {
   if (!execute_crc_loop (crc_loop, crc, data, is_shift_left))
-    return nullptr;
+    return std::make_pair (nullptr, nullptr);
 
+  if (states.length () != 1)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "There number of states isn't one "
+			    "after executing the loop.\n");
+      return std::make_pair (nullptr, nullptr);
+    }
   state *polynomial_state = states.last ();
 
   /* Get the tree which will contain the value of the polynomial
@@ -874,7 +884,7 @@ crc_symbolic_execution::extract_poly_and_create_lfsr (class loop *crc_loop,
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "Polynomial's value is null");
-      return nullptr;
+      return std::make_pair (nullptr, nullptr);
     }
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -892,10 +902,10 @@ crc_symbolic_execution::extract_poly_and_create_lfsr (class loop *crc_loop,
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "Polynomial's value is not constant.\n");
-      return nullptr;
+      return std::make_pair (nullptr, nullptr);
     }
 
-  return state::create_lfsr (calculated_crc, polynomial, is_shift_left);
+  return std::make_pair (calculated_crc, polynomial);
 }
 
 
diff --git a/gcc/crc_verification.h b/gcc/crc_verification.h
index 59f76298230..2b7dd31344a 100644
--- a/gcc/crc_verification.h
+++ b/gcc/crc_verification.h
@@ -91,8 +91,11 @@ class crc_symbolic_execution {
   bool execute (function *);
 
   /* Returns calculated polynomial by executing the loop
-     with concrete values.  */
-  value *extract_poly_and_create_lfsr (class loop *, gphi *, gphi *, bool);
+     with concrete values.
+     First value of the pair is the tree containing the value of the polynomial,
+     second is the calculated polynomial. Pair may contain nullptr.  */
+  std::pair <tree, value *>
+  extract_polynomial (class loop *, gphi *, gphi *, bool);
 
   const vec<state *> &get_final_states ()
   {
diff --git a/gcc/gimple-crc-optimization.cc b/gcc/gimple-crc-optimization.cc
index 48bd0efee16..c9bfd214cc3 100644
--- a/gcc/gimple-crc-optimization.cc
+++ b/gcc/gimple-crc-optimization.cc
@@ -205,7 +205,8 @@ class crc_optimization {
 
   /* Replaces function body with CRC_IFN call.
    Returns true if replacement is succeeded, otherwise false.  */
-  bool faster_crc_code_generation (function *fun);
+  bool
+  faster_crc_code_generation (function *fun, unsigned HOST_WIDE_INT quotient);
 
  public:
   unsigned int execute (function *fun);
@@ -1050,7 +1051,8 @@ remove_stmts_besides_return (function *fun, class loop *crc_loop)
 /* Replaces function body with CRC_IFN call.
    Returns true if replacement is succeeded, otherwise false.  */
 bool
-crc_optimization::faster_crc_code_generation (function *fun)
+crc_optimization::faster_crc_code_generation (function *fun,
+					      unsigned HOST_WIDE_INT quotient)
 {
   if (!(data && first_phi_for_crc))
    return false;
@@ -1058,6 +1060,8 @@ crc_optimization::faster_crc_code_generation (function *fun)
   // work correctly in case when data is xor-ed with crc before the loop.
   tree crc_arg = PHI_ARG_DEF (first_phi_for_crc, 1);
   tree data_arg = PHI_ARG_DEF (data, 1);
+  tree quotient_arg = build_int_cst (TREE_TYPE (crc_arg), quotient);
+
   if (!direct_internal_fn_supported_p
       (IFN_CRC, tree_pair (TREE_TYPE (data_arg), TREE_TYPE (crc_arg)),
        OPTIMIZE_FOR_BOTH))
@@ -1074,7 +1078,7 @@ crc_optimization::faster_crc_code_generation (function *fun)
       = gimple_build_call_internal (IFN_CRC, 3,
 				    crc_arg,
 				    data_arg,
-				    crc_arg); // must be changed to polynomial
+				    quotient_arg);
 
   tree result = make_ssa_name (TREE_TYPE (DECL_RESULT (fun->decl)));
   gimple_call_set_lhs (call, result);
@@ -1102,6 +1106,55 @@ crc_optimization::faster_crc_code_generation (function *fun)
   return true;
 }
 
+/* Calculate the quotient of polynomial long division of x^2n by the polynomial
+   in GF (2^n).  */
+unsigned HOST_WIDE_INT
+gf2n_poly_long_div_quotient (value *polynomial, bool is_left_shift)
+{
+  vec<int> x2n, pol, q;
+  size_t n = (*polynomial).length () * 2 + 1, m = (*polynomial).length () + 1;
+  x2n.create (n);
+  pol.create (m);
+
+  for (size_t i = 0; i < (*polynomial).length (); i++)
+    {
+      value_bit *const_bit;
+      if (is_left_shift)
+	const_bit = (*polynomial)[i];
+      else
+	const_bit = (*polynomial)[(*polynomial).length () - 1 - i];
+      pol.quick_push ((int) (as_a<bit *> (const_bit))->get_val ());
+    }
+
+  pol.quick_push (1);
+
+  for (size_t i = 0; i < n - 1; i++)
+    x2n.quick_push (0);
+  x2n.quick_push (1);
+
+  q.create (n - m + 1);
+  for (size_t i = 0; i < n - m + 1; i++)
+    q.quick_push (0);
+
+  for (int i = n - m; i >= 0; i--)
+    {
+      int d = x2n[i + m - 1];
+      if (d == 0)
+	continue;
+      for (int j = i + m - 1; j >= i; j--)
+	x2n[j] = x2n[j] ^ (pol[j - i] * d);
+      q[i] = d;
+    }
+  unsigned HOST_WIDE_INT quotient = 0;
+  for (size_t i = 0; i < q.length (); i++)
+    {
+      quotient <<= 1;
+      quotient = quotient | q[q.length () - i - 1];
+    }
+
+  return quotient;
+}
+
 unsigned int
 crc_optimization::execute (function *fun)
 {
@@ -1117,10 +1170,21 @@ crc_optimization::execute (function *fun)
 	}
 
       crc_symbolic_execution execute_loop;
-      value *lfsr
-	  = execute_loop.extract_poly_and_create_lfsr (crc_loop,
+      std::pair <tree, value *>
+	calc_polynom = execute_loop.extract_polynomial (crc_loop,
 						       first_phi_for_crc,
 						       data, is_left_shift);
+
+      if (!calc_polynom.second)
+	return 0;
+
+      unsigned HOST_WIDE_INT
+      quotient = gf2n_poly_long_div_quotient (calc_polynom.second,
+					      is_left_shift);
+
+      value *lfsr
+	= state::create_lfsr (calc_polynom.first,
+			      calc_polynom.second, is_left_shift);
       if (!lfsr)
 	{
 	  if (dump_file)
@@ -1141,7 +1205,7 @@ crc_optimization::execute (function *fun)
 	  if (dump_file)
 	    fprintf (dump_file, "%s function calculates CRC!\n",
 		     function_name (fun));
-	  if (!faster_crc_code_generation (fun))
+	  if (!faster_crc_code_generation (fun, quotient))
 	    {
 	      if (dump_file)
 		fprintf (dump_file, "Couldn't generate faster CRC code.\n");