Chnages in testsuit: - Added -fdisable-tree-phiopt2 -fdisable-tree-phiopt3 flags in test1 and test24.

Changes in Extract polynomial v2 and CRC detection v4:
  - Specify loop type by writing 'class loop'.

Changes in LFSR matching v2:
  - Wrote function to check conditions.
  - Added acceptable_diff, may_be_xors_condition, marginal_case_matches, match_lfsr_case1, state_matches_lfsr.
  - Modified condition_is_true/false, is_a_valid_xor_one functions.
  - Old state_matches_lfsr function name changed to state_matches_lfsr_all_cases.

5 files changed, 385 insertions, 103 deletions

diff --git a/gcc/gimple-crc-optimization.cc b/gcc/gimple-crc-optimization.cc
index 12868acd337..fe9e4beeff4 100644
--- a/gcc/gimple-crc-optimization.cc
+++ b/gcc/gimple-crc-optimization.cc
@@ -59,7 +59,7 @@ class crc_optimization {
   gphi * data;
 
   /* The loop, which probably calculates CRC.  */
-  loop *crc_loop;
+  class loop *crc_loop;
 
   unsigned HOST_WIDE_INT loop_iteration_number;
 
@@ -186,7 +186,7 @@ class crc_optimization {
 
 /* Set GIMPLE_PHI and GIMPLE statements of the crc loop not visited.  */
 void
-set_loop_statements_not_visited (loop *loop)
+set_loop_statements_not_visited (class loop *loop)
 {
   basic_block *bbs = get_loop_body_in_dom_order (loop);
   for (unsigned int i = 0; i < loop->num_nodes; i++)
@@ -958,7 +958,7 @@ crc_optimization::execute (function *fun)
 	    }
 	}
 
-      if (symb_exec.states_match_lfsr (lfsr))
+      if (symb_exec.states_match_lfsr (lfsr, is_left_shift))
 	{
 	  if (dump_file)
 	    {
diff --git a/gcc/symb-execute-all-paths.cc b/gcc/symb-execute-all-paths.cc
index a9db491ee5c..cb428bfb766 100644
--- a/gcc/symb-execute-all-paths.cc
+++ b/gcc/symb-execute-all-paths.cc
@@ -526,7 +526,7 @@ crc_symb_execution::execute_bb_phi_statements (basic_block bb,
       if (!current_state->do_assign (rhs, lhs))
 	return false;
     }
-    return true;
+  return true;
 }
 
 /* Execute all statements of BB.
@@ -534,10 +534,10 @@ crc_symb_execution::execute_bb_phi_statements (basic_block bb,
 bool
 crc_symb_execution::execute_bb_statements (basic_block bb,
 					   edge incoming_edge,
-					   auto_vec<edge, 20>& stack)
+					   auto_vec<edge, 20> &stack)
 {
   if (!execute_bb_phi_statements (bb, incoming_edge))
-      return false;
+    return false;
 
   return execute_bb_gimple_statements (bb, stack);
 }
@@ -577,7 +577,7 @@ crc_symb_execution::traverse_function (function *fun)
       if (!execute_bb_statements (bb, e, stack))
 	return false;
     }
-    return true;
+  return true;
 }
 
 bool
@@ -611,11 +611,10 @@ determine_index (tree data, bool is_shift_left)
     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,
+assign_vals_to_header_phis (state *polynomial_state, basic_block bb,
 			    gphi *crc, gphi *data,
 			    bool is_shift_left)
 {
@@ -630,7 +629,6 @@ assign_vals_to_header_phis (state * polynomial_state, basic_block bb,
       if (virtual_operand_p (lhs))
 	continue;
 
-
       if ((data && phi == data) || (!data && phi == crc))
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
@@ -641,7 +639,7 @@ assign_vals_to_header_phis (state * polynomial_state, basic_block bb,
 	    }
 	  polynomial_state->do_assign_pow2 (lhs,
 					    determine_index (lhs,
-							      is_shift_left));
+							     is_shift_left));
 	}
       else if (phi == crc)
 	{
@@ -653,7 +651,7 @@ assign_vals_to_header_phis (state * polynomial_state, basic_block bb,
 	    }
 	  polynomial_state->do_assign (build_zero_cst (TREE_TYPE (lhs)), lhs);
 	}
-      else if (TREE_CODE (PHI_ARG_DEF (phi, phi->nargs-1)) == INTEGER_CST)
+      else if (TREE_CODE (PHI_ARG_DEF (phi, phi->nargs - 1)) == INTEGER_CST)
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    {
@@ -662,7 +660,7 @@ assign_vals_to_header_phis (state * polynomial_state, basic_block bb,
 	      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);
+	  polynomial_state->do_assign (PHI_ARG_DEF (phi, phi->nargs - 1), lhs);
 	}
       else
 	{
@@ -682,7 +680,8 @@ assign_vals_to_header_phis (state * polynomial_state, basic_block bb,
 /* 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,
+crc_symb_execution::execute_crc_loop (class loop *crc_loop, gphi *crc,
+				      gphi *data,
 				      bool is_shift_left)
 {
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -729,19 +728,19 @@ crc_symb_execution::execute_crc_loop (loop *crc_loop, gphi *crc, gphi *data,
 
 /* Return true if all bits of the polynomial are constants (0 or 1).
    Otherwise return false.  */
-bool polynomial_is_known (const vec<value*> &polynomial)
+bool polynomial_is_known (const vec<value *> &polynomial)
 {
-  for (size_t i=0; i<polynomial.length (); i++)
+  for (size_t i = 0; i < polynomial.length (); i++)
     {
-      if (!is_a <bit *> (polynomial[i]))
-      return false;
+      if (!is_a<bit *> (polynomial[i]))
+	return false;
     }
-    return true;
+  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_poly_and_create_lfsr (loop *crc_loop,
+vec<value *> *
+crc_symb_execution::extract_poly_and_create_lfsr (class loop *crc_loop,
 						  gphi *crc, gphi *data,
 						  bool is_shift_left)
 {
@@ -761,8 +760,8 @@ crc_symb_execution::extract_poly_and_create_lfsr (loop *crc_loop,
       fprintf (dump_file, " variable.\n");
     }
 
-  /* Get the value of the tree.  */
-  vec<value*> * polynomial = polynomial_state->get_bits (calculated_crc);
+  /* Get the value (bit vector) of the tree (it may be the polynomial).  */
+  vec<value *> *polynomial = polynomial_state->get_bits (calculated_crc);
   if (!polynomial)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
@@ -772,13 +771,15 @@ crc_symb_execution::extract_poly_and_create_lfsr (loop *crc_loop,
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
-      /* Note: It may not be the real polynomial.  If it's a bit reflected crc,
+      /* 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);
     }
 
+  /* Check that polynomial's all bits are constants.  */
   if (!polynomial_is_known (*polynomial))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
@@ -791,26 +792,105 @@ crc_symb_execution::extract_poly_and_create_lfsr (loop *crc_loop,
   return state::create_lfsr (calculated_crc, polynomial, is_shift_left);
 }
 
+
+bool acceptable_diff (size_t index1, size_t index2)
+{
+  size_t diff;
+  if (index1 > index2)
+    diff = index1 - index2;
+  else
+    diff = index2 - index1;
+
+  /* Indexes of the symbolic bit may differ by 0, 8, 16, 24, 32, ...  */
+  return diff % 8 == 0;
+}
+
+/* Check whether the condition_exp and refernce_exp match.  */
+bool may_be_xors_condition (value *reference_exp, value *condition_exp)
+{
+  if (is_a<symbolic_bit *> (reference_exp)
+      && is_a<symbolic_bit *> (condition_exp))
+    {
+      symbolic_bit *condition_symbolic = as_a<symbolic_bit *> (condition_exp);
+      symbolic_bit *reference_symbolic = as_a<symbolic_bit *> (reference_exp);
+      return reference_symbolic->get_origin ()
+	     == condition_symbolic->get_origin ()
+	// FixMe: check correct index
+	/* && acceptable_diff (index, condition_symbolic->get_index ())*/;
+    }
+  if (is_a<symbolic_bit *> (reference_exp)
+      && is_a<bit_xor_expression *> (condition_exp))
+    {
+      return may_be_xors_condition (reference_exp,
+				    as_a<bit_xor_expression *>
+					(condition_exp)->get_left ())
+	     || may_be_xors_condition (reference_exp,
+				       as_a<bit_xor_expression *>
+					   (condition_exp)->get_right ());
+    }
+  if (is_a<bit_xor_expression *> (reference_exp)
+      && is_a<bit_xor_expression *> (condition_exp))
+    {
+      return may_be_xors_condition (as_a<bit_xor_expression *>
+					(reference_exp)->get_left (),
+				    as_a<bit_xor_expression *>
+					(condition_exp)->get_left ())
+	     && may_be_xors_condition (as_a<bit_xor_expression *>
+					   (reference_exp)->get_right (),
+				       as_a<bit_xor_expression *>
+					   (condition_exp)->get_right ());
+    }
+  return false;
+}
+
+
+/* Check whether there is a condition containing symb_exp
+   and the value is 1.  */
 bool
-condition_is_true ()
+crc_symb_execution::condition_is_true (value *symb_exp)
 {
-  return true;
+  state *final_state = final_states.last ();
+  for (auto iter = final_state->get_conditions ().begin ();
+       iter != final_state->get_conditions ().end (); ++iter)
+    {
+      value *cond_exp = (*iter)->get_left ();
+      if (may_be_xors_condition (symb_exp, cond_exp))
+	{
+	  //todo check is true
+	  return true;
+	}
+    }
+  return false;
 }
 
+
+/* Check whether there is a condition containing symb_exp
+   and the value is 0.  */
 bool
-condition_is_false ()
+crc_symb_execution::condition_is_false (value *symb_exp)
 {
-  return true;
+  state *final_state = final_states.last ();
+  for (auto iter = final_state->get_conditions ().begin ();
+       iter != final_state->get_conditions ().end (); ++iter)
+    {
+      value *cond_exp = (*iter)->get_left ();
+      if (may_be_xors_condition (symb_exp, cond_exp))
+	{
+	  //todo check is false
+	  return true;
+	}
+    }
+  return false;
 }
 
 
 /* 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)
+is_one (value *const_bit)
 {
-  return is_a <bit *> (const_bit)
-      && (as_a <bit *> (const_bit))->get_val () == 1;
+  return is_a<bit *> (const_bit)
+	 && (as_a<bit *> (const_bit))->get_val () == 1;
 }
 
 
@@ -819,21 +899,13 @@ is_one (value * const_bit)
    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)
+is_a_valid_symb (value *bit, size_t lfsr_bit_index)
 {
-  if (!is_a <symbolic_bit *> (bit))
+  if (!is_a<symbolic_bit *> (bit))
     return false;
 
-  size_t sym_bit_index = (as_a <symbolic_bit *> (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;
+  size_t sym_bit_index = (as_a<symbolic_bit *> (bit))->get_index ();
+  return acceptable_diff (sym_bit_index, lfsr_bit_index);
 }
 
 
@@ -841,100 +913,296 @@ is_a_valid_symb (value* bit, size_t lfsr_bit_index)
    and xor-ed values are valid symbolic bits.
    Otherwise, returns false.  */
 bool
-is_a_valid_xor (value* bit, size_t index)
+is_a_valid_xor (value *bit, size_t index)
 {
-  return is_a <bit_xor_expression *> (bit)
-	 && is_a_valid_symb ((as_a <bit_xor_expression *> (bit))->get_left (),
+  return is_a<bit_xor_expression *> (bit)
+	 && is_a_valid_symb ((as_a<bit_xor_expression *> (bit))->get_left (),
 			     index)
-	 && is_a_valid_symb ((as_a <bit_xor_expression *> (bit))->get_right (),
+	 && is_a_valid_symb ((as_a<bit_xor_expression *> (bit))->get_right (),
 			     index);
 }
 
 
-/* Returns true if bit is a valid bit_xor_expression with 1.
+/* Returns true if the bit is a valid bit_xor_expression with 1.
    Otherwise, returns false.  */
 bool
-is_a_valid_xor_one (value* bit, size_t index)
+is_a_valid_xor_one (value *bit, size_t index)
+{
+  if (is_a<bit_xor_expression *> (bit))
+    {
+      value *symb_exp = nullptr;
+      bit_xor_expression *xor_exp = as_a<bit_xor_expression *> (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;
+}
+
+
+bool crc_symb_execution::marginal_case_matches (value *crc, value *lfsr,
+						value *conditions_crc)
 {
-   if (is_a <bit_xor_expression *> (bit))
+  if (is_a<bit *> (lfsr))
+    {
+      if (!((is_a<bit *> (crc)
+	     && as_a<bit *> (crc)->get_val ()
+		== as_a<bit *> (lfsr)->get_val ())))
+	return false;
+      return true;
+    }
+  else if (is_a<symbolic_bit *> (lfsr))
+    {
+      if (!(is_a<bit *> (crc) && ((as_a<bit *> (crc)->get_val () == 0
+				   && condition_is_false (conditions_crc))
+				  || (as_a<bit *> (crc)->get_val () == 1
+				      && condition_is_true (conditions_crc)))))
+	return false;
+      return true;
+    }
+  /* else if (is_a <bit_xor_expression *> (lfsr))
      {
-       value * symb_exp = nullptr;
-       bit_xor_expression * xor_exp = as_a <bit_xor_expression *> (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
+       size_t index = (as_a<bit_xor_expression *> (lfsr))->get_left ()
+	   ->get_index ();
+       if (!((is_a_valid_xor_one (crc, index)
+	      && condition_is_true (
+		  as_a <bit_xor_expression *> (crc)->get_left ()))
+	     || (is_a_valid_symb (crc, index)
+		 && condition_is_false (crc))))
 	 return false;
-       return is_a_valid_xor (symb_exp, index)
-	      || is_a_valid_symb (symb_exp, index);
-     }
-   else
-     return false;
+       return true;
+     }*/
+  return false;
 }
 
 
-/* Returns true if the state matches the LFSR, otherwise - false.  */
+/* Match the crc to the lfsr, where crc's all bit values are symbolic_bits
+   or symbolic_bits ^ 1, besides MSB/LSB (it may be constant).
+
+  Under this are considered the cases,
+  1.  When sizes of crc and data are same.
+
+  2.  When data is xored with crc before the loop.
+  3.  When data is xor-ed with crc only for the condition.
+      xor is done on crc only.  */
 bool
-crc_symb_execution::state_matches_lfsr (const vec<value*> &lfsr,
-					const vec<value*> &crc_state)
+crc_symb_execution::match_lfsr_case1 (const vec<value *> &lfsr,
+				      const vec<value *> &crc_state,
+				      bool is_left_shift,
+				      symbolic_bit *symb_val,
+				      size_t i, size_t it_end)
 {
-  for (size_t i = 0; i < lfsr.length () && crc_state.length (); i++)
+  /* Check whether significant bits of LFSR and CRC match.  */
+  if (is_left_shift)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Checking 0 bit.\n");
+
+      if (!marginal_case_matches (crc_state[0], lfsr[0], symb_val))
+	return false;
+    }
+  else
     {
-       if (dump_file && (dump_flags & TDF_DETAILS))
-	 fprintf (dump_file, "Checking %lu-th bit.\n", i);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Checking %lu bit.\n", it_end);
+
+      if (!marginal_case_matches (crc_state[it_end],
+				  lfsr[it_end], symb_val))
+	return false;
+    }
 
-      if (is_a <bit_xor_expression *> (lfsr[i]))
+  for (; i < it_end; i++)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Checking %lu bit.\n", i);
+
+      if (is_a<bit_xor_expression *> (lfsr[i]))
 	{
-	  size_t index = (as_a <bit_xor_expression *> (lfsr[i]))->get_left ()
+	  size_t index = (as_a<bit_xor_expression *> (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 ()))))
+	  if (!((is_a_valid_xor_one (crc_state[i], index)
+		 && condition_is_true (
+		     as_a<bit_xor_expression *> (crc_state[i])->get_left ()))
+		|| (is_a_valid_symb (crc_state[i], index)
+		    && condition_is_false (crc_state[i]))))
 	    return false;
 	}
-      else if (is_a <symbolic_bit *> (lfsr[i]))
+      else if (is_a<symbolic_bit *> (lfsr[i]))
 	{
 	  size_t index = (as_a<symbolic_bit *> (lfsr[i]))->get_index ();
 	  if (!(is_a_valid_symb (crc_state[i], index)
-		|| is_a_valid_xor (crc_state[i], index)
-		|| condition_is_false ()))
+		&& condition_is_false (crc_state[i])))
+	    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 the state matches the LFSR, otherwise - false.  */
+bool
+crc_symb_execution::state_matches_lfsr_all_cases (const vec<value *> &lfsr,
+						  const vec<value *> &crc_state,
+						  bool is_left_shift)
+{
+  size_t i = 0, it_end = lfsr.length () < crc_state.length ()
+			 ? lfsr.length () : crc_state.length ();
+  if (is_left_shift)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Checking 0 bit.\n");
+
+      i = 1;
+      if (!marginal_case_matches (crc_state[0], lfsr[0], crc_state[1]))
+	return false;
+    }
+  else
+    {
+      --it_end;
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Checking %lu bit.\n", it_end);
+
+      if (!marginal_case_matches (crc_state[it_end],
+				  lfsr[it_end], crc_state[it_end - 1]))
+	return false;
+    }
+
+  for (; i < it_end; i++)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Checking %lu bit.\n", i);
+
+      if (is_a<bit_xor_expression *> (lfsr[i]))
+	{
+	  size_t index = (as_a<bit_xor_expression *> (lfsr[i]))->get_left ()
+	      ->get_index ();
+	  if (!(((is_a_valid_xor_one (crc_state[i], index)
+		  && condition_is_true (crc_state[i]))
+		 || (is_a_valid_symb (crc_state[i], index)
+		     && condition_is_false (crc_state[i])))
+		|| ((is_a_valid_xor_one (crc_state[i], index)
+		     && condition_is_true (crc_state[i]))
+		    || (is_a_valid_xor (crc_state[i], index)
+			&& condition_is_false (crc_state[i])))))
 	    return false;
 	}
-      else if (is_a <bit *> (lfsr[i]))
+      else if (is_a<symbolic_bit *> (lfsr[i]))
 	{
-	  if (!is_a <bit*> (crc_state[i]) || as_a <bit*> (lfsr[i])->get_val ()
-	      != as_a <bit*> (crc_state[i])->get_val ())
+	  size_t index = (as_a<symbolic_bit *> (lfsr[i]))->get_index ();
+	  // TODO: check the case when calculated crc is constant.
+	  if (!((is_a_valid_symb (crc_state[i], index)
+		 || is_a_valid_xor (crc_state[i], index))
+		&& condition_is_false (crc_state[i])))
 	    return false;
 	}
       else
 	{
-	 if (dump_file && (dump_flags & TDF_DETAILS))
-	   fprintf (dump_file, "Not expected expression in LFSR.\n");
-	 return false;
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "Not expected expression in LFSR.\n");
+	  return false;
 	}
     }
   return true;
 }
 
+
+/* Returns true if the state matches the LFSR, otherwise - false.  */
+bool
+crc_symb_execution::state_matches_lfsr (const vec<value *> &lfsr,
+					const vec<value *> &crc_state,
+					bool is_left_shift)
+{
+  unsigned constant = 0;
+  symbolic_bit *symb_bit = nullptr;
+  value *simple_xor_left = nullptr, *simple_xor_right = nullptr;
+  bit_xor_expression *xor_exp = nullptr, *complicated_xor = nullptr;
+  bool has_const = false, has_other_val = false;
+
+  size_t it_beg = 0, it_end = lfsr.length () < crc_state.length ()
+			      ? lfsr.length () : crc_state.length ();
+  if (is_left_shift)
+    it_beg = 1;
+  else
+    --it_end;
+
+  for (unsigned j = it_beg; j < crc_state.length (); ++j)
+    {
+      (crc_state[j])->print ();
+      switch (crc_state[j]->get_type ())
+	{
+	  case SYMBOLIC_BIT:
+	    symb_bit = as_a<symbolic_bit *> (crc_state[j]);
+	    break;
+	  case BIT:
+	    has_const = true;
+	    constant = as_a<bit *> (crc_state[j])->get_val ();
+	    break;
+	  case BIT_XOR_EXPRESSION:
+	    {
+	      /* Calculated CRC may contain crc[]^data[],
+		 or crc[]^1, or crc[]^data[]^1.  */
+	      xor_exp
+		  = as_a<bit_xor_expression *> (crc_state[j]);
+
+	      if (is_a<symbolic_bit *> (xor_exp->get_left ()))
+		simple_xor_left = xor_exp->get_left ();
+	      else if (is_a<bit_xor_expression *> (xor_exp->get_left ()))
+		complicated_xor = as_a<bit_xor_expression *>
+		    (xor_exp->get_left ());
+
+	      if (is_a<bit *> (xor_exp->get_right ())
+		  || is_a<symbolic_bit *> (xor_exp->get_right ()))
+		simple_xor_right = xor_exp->get_right ();
+	      break;
+	    }
+	  default:
+	    has_other_val = true;
+	}
+    }
+
+  if (has_other_val)
+    return false;
+
+  if (symb_bit && !complicated_xor
+      && (!simple_xor_right
+	  || (simple_xor_right && is_a<bit *> (simple_xor_right)))
+      && !has_other_val)
+    return match_lfsr_case1 (lfsr, crc_state, is_left_shift,
+			     symb_bit, it_beg, it_end);
+  return false;
+}
+
+
 /* Returns true if all states match the LFSR, otherwise - false.  */
 bool
-crc_symb_execution::states_match_lfsr (vec<value*> * lfsr)
+crc_symb_execution::states_match_lfsr (vec<value *> *lfsr, bool is_left_shift)
 {
   while (!final_states.is_empty ())
     {
-      state * final_state = final_states.last ();
+      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 ());
+	  final_state->print_conditions ();
 	}
-      if (!state_matches_lfsr (*lfsr, *(final_state->get_first_value ())))
+      if (!state_matches_lfsr (*lfsr, *(final_state->get_first_value ()),
+			       is_left_shift))
 	return false;
       final_states.pop ();
       delete final_state;
     }
- return true;
+  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 4d07498d32b..71e42c002b6 100644
--- a/gcc/symb-execute-all-paths.h
+++ b/gcc/symb-execute-all-paths.h
@@ -43,11 +43,11 @@ class crc_symb_execution {
 
  private:
   /* A vector of states to keep the current state of each executed path.  */
-  vec<state*> states;
+  vec<state *> states;
 
   /* A vector of final states
      to keep the returned_value and path conditions.  */
-  vec<state*> final_states;
+  vec<state *> final_states;
 
 /* Assign symbolic values to the arguments of the function
    and keep in the state.  */
@@ -60,22 +60,22 @@ class crc_symb_execution {
 
   /* Add next basic blocks of the conditional block
      for the execution path into the stack.  */
-  void add_next_bbs (basic_block, state *, auto_vec<edge, 20>&);
+  void add_next_bbs (basic_block, state *, auto_vec<edge, 20> &);
 
   /* Keep conditions depending on symbolic variables in the states.  */
-  static bool add_condition (const gcond*, state*, state*);
+  static bool add_condition (const gcond *, state *, state *);
 
   /* Create new state for true and false branch.
      Keep conditions in new created states.  */
-  bool resolve_condition (const gcond*, auto_vec<edge, 20>&);
+  bool resolve_condition (const gcond *, auto_vec<edge, 20> &);
 
   /* Keep the calculated value of the return value
      and the conditions of the executed path.  */
-  bool keep_return_val_and_conditions (const greturn*);
+  bool keep_return_val_and_conditions (const greturn *);
 
   /* Execute gimple statements of the basic block.
      Keeping values of variables in the state.  */
-  bool execute_bb_gimple_statements (basic_block, auto_vec<edge, 20>&);
+  bool execute_bb_gimple_statements (basic_block, auto_vec<edge, 20> &);
 
   /* Assign values of phi instruction to its result.
      Keep updated values in the state.  */
@@ -83,7 +83,7 @@ class crc_symb_execution {
 
   /* Execute all statements of the basic block.
     Keeping values of variables in the state.  */
-  bool execute_bb_statements (basic_block, edge, auto_vec<edge, 20>&);
+  bool execute_bb_statements (basic_block, edge, auto_vec<edge, 20> &);
 
 /* Traverse function fun's all paths from the first basic block to the last.
    Each time iterate loops only once.
@@ -92,10 +92,23 @@ class crc_symb_execution {
 
   /* Execute the loop, which calculates crc with initial values,
    to calculate the polynomial.  */
-  bool execute_crc_loop (loop *, gphi *, gphi *, bool);
+  bool execute_crc_loop (class loop *, gphi *, gphi *, bool);
 
   /* Returns true if the state matches the LFSR, otherwise - false.  */
-  bool state_matches_lfsr (const vec<value*> &, const vec<value*> &);
+  bool state_matches_lfsr_all_cases (const vec<value *> &, const vec<value *> &,
+				     bool);
+
+  /* Returns true if the state matches the LFSR, otherwise - false.  */
+  bool match_lfsr_case1 (const vec<value *> &, const vec<value *> &,
+			 bool, symbolic_bit *, size_t, size_t);
+
+  bool state_matches_lfsr (const vec<value *> &, const vec<value *> &, bool);
+
+  bool condition_is_true (value *);
+
+  bool condition_is_false (value *);
+
+  bool marginal_case_matches (value *, value *, value *);
 
  public:
 
@@ -104,10 +117,11 @@ class crc_symb_execution {
 
   /* Returns calculated polynomial by executing the loop
      with concrete values.  */
-  vec<value*> * extract_poly_and_create_lfsr (loop *, gphi *, gphi *, bool);
+  vec<value *> *extract_poly_and_create_lfsr (class loop *, gphi *,
+					      gphi *, bool);
 
   /* Returns true if all states match the LFSR, otherwise - false.  */
-  bool states_match_lfsr (vec<value*> *lfsr);
+  bool states_match_lfsr (vec<value *> *, bool);
 
   crc_symb_execution ()
   {
@@ -118,7 +132,7 @@ class crc_symb_execution {
 
   ~crc_symb_execution ()
   {
-     /* Free memory.  */
+    /* Free memory.  */
     states.release ();
     final_states.release ();
   }
diff --git a/gcc/testsuite/gcc.dg/crc-1.c b/gcc/testsuite/gcc.dg/crc-1.c
index acad4a3dc6e..9027ecd3dfe 100644
--- a/gcc/testsuite/gcc.dg/crc-1.c
+++ b/gcc/testsuite/gcc.dg/crc-1.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-crc-details" } */
+/* { dg-options "-O2 -fdump-tree-crc-details -fdisable-tree-phiopt2 -fdisable-tree-phiopt3" } */
 
 #include <stdio.h>
 #include <stdint.h>
diff --git a/gcc/testsuite/gcc.dg/crc-24.c b/gcc/testsuite/gcc.dg/crc-24.c
index 8f61f15f798..ee015da5400 100644
--- a/gcc/testsuite/gcc.dg/crc-24.c
+++ b/gcc/testsuite/gcc.dg/crc-24.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-crc" } */
+/* { dg-options "-O2 -fdump-tree-crc -fdisable-tree-phiopt2 -fdisable-tree-phiopt3" } */
 
 #include <stdio.h>
 #include <stdint.h>