Added Extract polynomial v1: - Execute crc loop with concete numbers to calculate polynomial.

Changes in CRC detection v4:
  - Keep gphi * instead of gimple * for data and crc.

3 files changed, 203 insertions, 6 deletions

diff --git a/gcc/gimple-crc-optimization.cc b/gcc/gimple-crc-optimization.cc
index dc2074687a8..f810dc40367 100644
--- a/gcc/gimple-crc-optimization.cc
+++ b/gcc/gimple-crc-optimization.cc
@@ -48,15 +48,15 @@ class crc_optimization {
   gimple *shift_after_xor;
 
   /* Phi statement, result may be the crc variable.  */
-  gimple *first_phi_for_crc;
+  gphi *first_phi_for_crc;
 
   /* Sometimes polynomial may not be constant
      and xor-ed variable may depend on two variables.
      The result of phi statement may contain the polynomial.  */
-  gimple *second_phi_for_crc;
+  gphi *second_phi_for_crc;
 
   /* Phi statement, result maybe data (if exists).  */
-  gimple * data;
+  gphi * data;
 
   /* The loop, which probably calculates CRC.  */
   loop *crc_loop;
@@ -674,7 +674,7 @@ crc_optimization::continue_to_check_dep_for_xor (gimple *def_stmt)
 	     a phi statement.  */
 	  if (first_phi_for_crc)
 	    {
-	      second_phi_for_crc = def_stmt;
+	      second_phi_for_crc = as_a <gphi *> (def_stmt);
 	      if (dump_file && (dump_flags & TDF_DETAILS))
 		fprintf (dump_file, "Set second phi.\n");
 	    }
@@ -682,7 +682,7 @@ crc_optimization::continue_to_check_dep_for_xor (gimple *def_stmt)
 	    {
 	      if (dump_file && (dump_flags & TDF_DETAILS))
 		fprintf (dump_file, "Set first phi.\n");
-	      first_phi_for_crc = def_stmt;
+	      first_phi_for_crc = as_a <gphi *> (def_stmt);
 	    }
 	  return true;
 	}
@@ -743,7 +743,7 @@ crc_optimization::continue_to_check_dep_for_if (gimple *def_stmt)
 	      return false;
 	    }
 
-	  data = def_stmt;
+	  data = as_a <gphi *> (def_stmt);
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    {
 	      fprintf (dump_file,
@@ -935,7 +935,24 @@ crc_optimization::execute (function *fun)
       {
 	if (dump_file)
 	  fprintf (dump_file, "\nAttention! Not the CRC we want!\n");
+	return 0;
       }
+
+      crc_symb_execution execute_loop;
+      vec<value*> * polynomial
+      = execute_loop.extract_polynomial (crc_loop, first_phi_for_crc,
+					 data, is_left_shift);
+
+    if (!polynomial)
+      {
+	if (dump_file)
+	  fprintf (dump_file, "\nCouldn't determine the polynomial!\n");
+	return 0;
+      }
+
+    /* TODO: Create LFSR state.  */
+
+    /* TODO: Match LFSR.  */
   }
   return 0;
 }
diff --git a/gcc/symb-execute-all-paths.cc b/gcc/symb-execute-all-paths.cc
index f8843a6d2ca..1a20a538ed7 100644
--- a/gcc/symb-execute-all-paths.cc
+++ b/gcc/symb-execute-all-paths.cc
@@ -595,3 +595,174 @@ crc_symb_execution::execute_function (function *fun)
   /* Execute function's statements, keeping a state for each path.  */
   return traverse_function (fun);
 }
+
+/* Determine which bit of data must be 1.  */
+unsigned HOST_WIDE_INT
+determine_index (tree data, bool is_shift_left)
+{
+  if (is_shift_left)
+    // FIXME: may be the data's size is larger,
+    //  but MSB is checked for the middle bit.
+    return tree_to_uhwi (TYPE_SIZE (TREE_TYPE (data))) - 1;
+  else
+    return 0;
+}
+
+
+/* Assign appropriate values to data, crc
+   and other phi results to calculate the polynomial.  */
+void
+assign_vals_to_header_phis (state * polynomial_state, basic_block bb,
+			    gphi *crc, gphi *data,
+			    bool is_shift_left)
+{
+  for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
+       gsi_next (&gsi))
+    {
+
+      gphi *phi = gsi.phi ();
+      tree lhs = gimple_phi_result (phi);
+
+      /* Don't consider virtual operands.  */
+      if (virtual_operand_p (lhs))
+	continue;
+
+
+      if ((data && phi == data) || (!data && phi == crc))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Assigning the required value to ");
+	      print_generic_expr (dump_file, lhs, dump_flags);
+	      fprintf (dump_file, " variable.\n");
+	    }
+	  polynomial_state->do_assign_pow2 (lhs,
+					    determine_index (lhs,
+							      is_shift_left));
+	}
+      else if (phi == crc)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Assigning 0 value to ");
+	      print_generic_expr (dump_file, lhs, dump_flags);
+	      fprintf (dump_file, " variable.\n");
+	    }
+	  polynomial_state->do_assign (build_zero_cst (TREE_TYPE (lhs)), lhs);
+	}
+      else if (TREE_CODE (PHI_ARG_DEF (phi, phi->nargs-1)) == INTEGER_CST)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "First value of phi is a constant, "
+				  "assigning the number to ");
+	      print_generic_expr (dump_file, lhs, dump_flags);
+	      fprintf (dump_file, " variable.\n");
+	    }
+	  polynomial_state->do_assign (PHI_ARG_DEF (phi, phi->nargs-1), lhs);
+	}
+      else
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "First value of phi isn't constant, "
+				  "assigning to ");
+	      print_generic_expr (dump_file, lhs, dump_flags);
+	      fprintf (dump_file, " variable.\n");
+	    }
+	  polynomial_state->do_assign (build_zero_cst (TREE_TYPE (lhs)), lhs);
+	}
+    }
+}
+
+
+/* Execute the loop, which calculates crc with initial values,
+   to calculate the polynomial.  */
+bool
+crc_symb_execution::execute_crc_loop (loop *crc_loop, gphi *crc, gphi *data,
+				      bool is_shift_left)
+{
+  basic_block bb = crc_loop->header;
+  assign_vals_to_header_phis (states.last (), bb, crc, data, is_shift_left);
+
+  auto_vec<edge, 20> stack (crc_loop->num_nodes);
+
+  execute_bb_gimple_statements (bb, stack);
+
+  /* stack may not be empty.  Successor BB's are added into the stack
+     from the execute_bb_gimple_statements function.  */
+  while (!stack.is_empty ())
+    {
+      /* Look at the edge on the top of the stack.  */
+      edge e = stack.last ();
+      stack.pop ();
+
+      /* Get dest block of the edge.  */
+      basic_block bb = e->dest;
+
+      /* Execute only basic blocks of the crc_loop.  */
+      if (!flow_bb_inside_loop_p (crc_loop, bb))
+	continue;
+
+
+      /* Execute statements.  */
+      if (!execute_bb_statements (bb, e, stack))
+	return false;
+    }
+  return true;
+}
+
+
+/* Execute the loop, which is expected to calculate CRC,
+   to extract polynomial, assigning real numbers to crc and data.  */
+vec<value*> *
+crc_symb_execution::extract_polynomial (loop *crc_loop,
+					gphi *crc, gphi *data,
+					bool is_shift_left)
+{
+  if (dump_file)
+    fprintf (dump_file, "\n\nTrying to calculate the polynomial.\n\n");
+
+  state * polynomial_state = new state;
+  states.quick_push (polynomial_state);
+
+  execute_crc_loop (crc_loop, crc, data, is_shift_left);
+
+  if (states.length () != 1)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "The number of states is not one.\n");
+      return nullptr;
+    }
+
+  /* Get the tree which will contain the value of the polynomial
+     at the end of the loop.  */
+  tree calculated_crc = PHI_ARG_DEF (crc, 0);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Getting the value of ");
+      print_generic_expr (dump_file, calculated_crc, dump_flags);
+      fprintf (dump_file, " variable.\n");
+    }
+
+
+  /* Get the value of the tree.  */
+  vec<value*> * polynomial = polynomial_state->get_bits (calculated_crc);
+  if (polynomial == nullptr)
+   {
+    if (dump_file && (dump_flags & TDF_DETAILS))
+       fprintf (dump_file, "Polynomial's value is null");
+    return nullptr;
+   }
+
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     {
+	/* Note: It may not be the real polynomial.
+	   If it's a bit reflected crc, then to get a real polynomial,
+	   it must be reflected and 1 bit added.  */
+	fprintf (dump_file, "Polynomial's value is ");
+	state::print_bits (polynomial);
+     }
+  return polynomial;
+}
\ No newline at end of file
diff --git a/gcc/symb-execute-all-paths.h b/gcc/symb-execute-all-paths.h
index ef184cb9bd7..3f664f8404e 100644
--- a/gcc/symb-execute-all-paths.h
+++ b/gcc/symb-execute-all-paths.h
@@ -90,9 +90,18 @@ class crc_symb_execution {
    Symbolically execute statements of each path.  */
   bool traverse_function (function *);
 
+  /* Execute the loop, which calculates crc with initial values,
+   to calculate the polynomial.  */
+  bool execute_crc_loop (loop *, gphi *, gphi *, bool);
+
  public:
+  /* Symbolically execute the function and keep final states.  */
   bool execute_function (function *);
 
+  /* Returns calculated polynomial by executing the loop
+     with concrete values.  */
+  vec<value*> * extract_polynomial (loop *, gphi *, gphi *, bool);
+
   crc_symb_execution ()
   {
     /* Reserve memory for the vectors of states.  */