CRC detection v1: - Added pass_crc_optimization. Detects CRC-like functions. - Added tests to check the correctness of the pass.

29 files changed, 1454 insertions, 0 deletions

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 6001c9e..c9bce29 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1647,6 +1647,7 @@ OBJS = \
 	tree-iterator.o \
 	tree-logical-location.o \
 	tree-loop-distribution.o \
+	gimple-crc-optimization.o \
 	tree-nested.o \
 	tree-nrv.o \
 	tree-object-size.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index 50bcc523..8989028 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2966,6 +2966,10 @@ ftree-loop-distribute-patterns
 Common Var(flag_tree_loop_distribute_patterns) Optimization
 Enable loop distribution for patterns transformed into a library call.
 
+fgimple-crc-optimization
+Common Var(flag_gimple_crc_optimization) Optimization
+Enable crc optimization on trees.
+
 ftree-loop-im
 Common Var(flag_tree_loop_im) Init(1) Optimization
 Enable loop invariant motion on trees.
diff --git a/gcc/gimple-crc-optimization.cc b/gcc/gimple-crc-optimization.cc
new file mode 100644
index 0000000..e57b3bc
--- /dev/null
+++ b/gcc/gimple-crc-optimization.cc
@@ -0,0 +1,879 @@
+/* CRC optimization.
+   Copyright (C) 2006-2022 Free Software Foundation, Inc.
+   Contributed by Mariam Arutunian <mariamarutunian@gmail.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.   */
+
+/* This pass performs crc optimization.  */
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "tree-ssa-loop-niter.h"
+#include "cfgloop.h"
+#include "gimple-range.h"
+#include "tree-scalar-evolution.h"
+#include "hwint.h"
+#include "gimple-pretty-print.h"
+
+class crc_optimization {
+ private:
+  /* shift_before_xor will contain the statement doing shift one operation
+     (if exists and satisfies the CRC) before xor operation.  */
+  gimple *shift_before_xor;
+
+  /* shift_after_xor will contain the statement doing shift one operation
+     (if shift_before_xor doesn't exist and satisfies the CRC) after xor
+     operation on the same variable.  */
+  gimple *shift_after_xor;
+
+  /* Phi statements result may be the crc variable.  */
+  gimple *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;
+
+  unsigned HOST_WIDE_INT loop_iteration_number;
+
+  /* Function's return value size.  */
+  unsigned HOST_WIDE_INT return_size;
+
+  /* Depending on the value, may be forward or reversed CRC.  */
+  bool is_left_shift;
+
+  /* Will be true, if crc variable and if condition depend on each other.  */
+  bool crc_if_dep;
+
+  /* If the value is false, then xor operation isn't for CRC calculation,
+     otherwise it may calculate CRC.  */
+  bool clean_xor_maybe_crc;
+
+
+  void set_initial_values ()
+  {
+    shift_before_xor = nullptr;
+    shift_after_xor = nullptr;
+    first_phi_for_crc = nullptr;
+    second_phi_for_crc = nullptr;
+    is_left_shift = false;
+    crc_if_dep = false;
+    clean_xor_maybe_crc = true;
+  }
+
+  /* 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.  */
+  bool function_may_calculate_crc (function *fun);
+
+  /* Checks the loop iteration number.
+   The loop for CRC calculation may do 8, 16, 24, 32 iterations.  */
+  bool is_loop_of_crc_calculation (class loop *func_loop);
+
+  /* Check whether found xor_stmt is for calculating crc.
+   The function fun calculates crc only if there is a shift operation
+   in the crc_loop.  */
+  bool xor_calculates_crc (function *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 check_dependency function.
+   The check_dependency may be the check_def_stmt_for_xor
+   or check_def_stmt_for_if function.  */
+  void
+  get_dep (tree name, void (crc_optimization::*check_dependency) (tree ssa));
+
+  /* Check whether the statement, dependent from xor's operands,
+   does shift operation (for calculating crc)
+   or is a phi statement.  */
+  void check_def_stmt_for_xor (tree ssa);
+
+  /* Walks through def-chain of if's condition and
+   checks whether if's condition and xor-ed variable
+   are dependent from the same variable.
+   (The crc variable is xor-ed if variable's MSB/LSB is 1).  */
+  void check_def_stmt_for_if (tree ssa);
+
+  /* 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 shift1 in the same block with xor,
+   on the opposite branch must be another shift1 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);
+
+  /* This function gets the condition cond and
+     returns true if MSB/LSB bit is checked for 1.  */
+  static bool cond_true_is_checked_for_bit_one (const gcond *cond);
+
+  /* This functions checks whether the pair of xor's shift exists
+     in the given bb.  If there is a shift with xor in the same block,
+     then in the opposite block must be another shift.  */
+  bool exists_shift_for_opp_xor_shift (basic_block bb);
+
+  /* This function walks through the uses of xor-ed variable
+     (within the crc_loop) and checks whether it is shifted one.
+     Operations which may corrupt crc value mustn't occur between xor and shift,
+     otherwise the loop isn't calculating CRC.  */
+  void find_shift_after_xor (class loop *crc_loop, tree lhs);
+
+  bool can_not_be_shift_of_crc (gimple *assign_stmt,
+				bool find_shift_before_xor);
+
+  /* Checks whether it's ok that the statement is between shift and xor.
+     This check is not that accurate.  But it's enough to filter not CRCs.  */
+  static bool is_acceptable_statement (const tree_code &stmt_code);
+
+  /* Get the return value size of the function
+     and assign to return_size member.  */
+  void get_return_value_size (function *fun);
+
+  /* This function checks whether calculated crc value
+     (maybe modified) is returned.
+     By walking down through the use-def chain of lhs
+     return true if we encounter return statement.  */
+  bool returned_value_depends_on_crc (tree lhs);
+
+  /* Prints extracted details of CRC calculation.  */
+  void print_crc_information ();
+
+ public:
+  unsigned int execute (function *fun);
+};
+
+
+/* Set GIMPLE_PHI and GIMPLE statements of the function not visited.  */
+
+static void
+set_all_statements_not_visited (function *fun)
+{
+  basic_block bb;
+  FOR_EACH_BB_FN (bb, fun)
+    {
+      for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
+	   gsi_next (&gsi))
+	{
+	  gphi *stmt = gsi.phi ();
+	  gimple_set_visited (stmt, false);
+	}
+      for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
+	   gsi_next (&gsi))
+	{
+	  gimple *stmt = gsi_stmt (gsi);
+	  gimple_set_visited (stmt, false);
+	}
+    }
+}
+
+
+/* Prints extracted details of CRC calculation.  */
+void
+crc_optimization::print_crc_information ()
+{
+  if (dump_file)
+    {
+      fprintf (dump_file,
+	       "Loop iteration number is %ld."
+	       "\nReturn size is %ld\n.",
+	       loop_iteration_number, return_size);
+      if (is_left_shift)
+	fprintf (dump_file, "Bit forward\n");
+      else
+	fprintf (dump_file, "Bit reversed\n");
+    }
+}
+
+
+/* This function checks whether calculated crc value
+   (maybe modified) is returned.
+   By walking down through the use-def chain of lhs
+   return true if we encounter return statement.  */
+
+bool
+crc_optimization::returned_value_depends_on_crc (tree lhs)
+{
+  bool crc_is_returned = false;
+  imm_use_iterator imm_iter;
+  use_operand_p use_p;
+  if (TREE_CODE (lhs) != SSA_NAME)
+    return false;
+
+  /* Iterate through the immediate uses of the current variable.
+     If we encounter return statement - return true.  */
+  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
+    {
+      gimple *stmt = USE_STMT (use_p);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	print_gimple_stmt (dump_file, stmt, 0);
+      if (gimple_visited_p (stmt))
+	return false;
+
+      gimple_set_visited (stmt, true);
+      if (gimple_code (stmt) == GIMPLE_RETURN)
+	return true;
+      else if (gimple_code (stmt) == GIMPLE_PHI)
+	crc_is_returned
+	    = returned_value_depends_on_crc (gimple_phi_result (stmt));
+      else if (is_gimple_assign (stmt))
+	crc_is_returned
+	    = returned_value_depends_on_crc (gimple_assign_lhs (stmt));
+      if (crc_is_returned)
+	return true;
+    }
+  return false;
+}
+
+
+/* Get the return value size of the function
+   and assign to return_size member.  */
+
+void
+crc_optimization::get_return_value_size (function *fun)
+{
+  return_size = 0;
+  tree tree_return_value_size = DECL_SIZE (DECL_RESULT (fun->decl));
+  if (tree_fits_uhwi_p (tree_return_value_size))
+    {
+      return_size = tree_to_uhwi (tree_return_value_size);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Return size is %ld\n", return_size);
+    }
+}
+
+
+/* This function walks through the uses of xor-ed variable (within the crc_loop)
+   and checks whether it is shifted one.
+   Operations which may corrupt crc value mustn't occur between xor and shift,
+   otherwise the loop isn't calculating CRC.  */
+
+void
+crc_optimization::find_shift_after_xor (class loop *crc_loop, tree lhs)
+{
+  imm_use_iterator imm_iter;
+  use_operand_p use_p;
+
+  if (TREE_CODE (lhs) != SSA_NAME)
+    return;
+
+  /* Iterate through the immediate uses of the current variable.
+     If there is a shift return true,
+     if before shift there is other instruction (besides phi) return false.  */
+  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
+    {
+      gimple *stmt = USE_STMT (use_p);
+      if (gimple_visited_p (stmt))
+	return;
+      gimple_set_visited (stmt, true);
+      // Consider only statements within the loop
+      if (!flow_bb_inside_loop_p (crc_loop, gimple_bb (stmt)))
+	return;
+
+      /* If encountered phi statement, check immediate use of its result
+	 otherwise, if encountered assign statement, check whether it does shift
+	 (some other operations are allowed to be between shift and xor).  */
+      if (gimple_code (stmt) == GIMPLE_PHI)
+	{
+	  /* Don't continue finding if encountered the loop's beginning.  */
+	  if (bb_loop_header_p (gimple_bb (stmt)))
+	    return;
+
+	  find_shift_after_xor
+	      (crc_loop, gimple_phi_result (stmt));
+	}
+      else if (is_gimple_assign (stmt))
+	if (can_not_be_shift_of_crc (stmt, false))
+	  {
+	    shift_after_xor = nullptr;
+	    return;
+	  }
+    }
+}
+
+
+/* This function checks whether the pair of xor's shift exists in the given bb.
+
+   If there is a shift with xor in the same block,
+   then in the opposite block must be another shift.  */
+
+bool
+crc_optimization::exists_shift_for_opp_xor_shift (basic_block bb)
+{
+  /* Walk through the instructions of given basic block.  */
+  for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (
+      bsi); gsi_next (
+      &bsi))
+    {
+      gimple *stmt = gsi_stmt (bsi);
+      /* Find assigment statement with shift operation.
+	 Check that shift's direction is same with the shift done
+	 on the path with xor.  */
+      if (is_gimple_assign (stmt))
+	{
+	  if (gimple_assign_rhs_code (stmt) == LSHIFT_EXPR && is_left_shift)
+	    return true;
+	  else if (gimple_assign_rhs_code (stmt) == RSHIFT_EXPR
+		   && !is_left_shift)
+	    return true;
+	}
+    }
+  /* If there is no shift, return false.  */
+  return false;
+}
+
+
+/* This function gets the condition cond and
+   returns true if MSB/LSB bit is checked for 1.  */
+
+bool
+crc_optimization::cond_true_is_checked_for_bit_one (const gcond *cond)
+{
+  if (!cond)
+    return false;
+  tree lhs = gimple_cond_lhs (cond);
+  tree rhs = gimple_cond_rhs (cond);
+  enum tree_code code = gimple_cond_code (cond);
+
+  /* If the condition is
+     something == 1 or 1 == something -> return true.  */
+  if ((integer_onep (lhs) || integer_onep (rhs)) && code == EQ_EXPR)
+    return true;
+
+  /* If the condition is
+     0 != something  or 0 > something -> return true.  */
+  if (integer_zerop (lhs) && (code == NE_EXPR || code == GT_EXPR))
+    return true;
+
+  /* If the condition is
+     something != 0  or something < 0 -> return true.  */
+  if (integer_zerop (rhs) && (code == NE_EXPR || code == LT_EXPR))
+    return true;
+
+  return false;
+}
+
+
+/* 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 shift1 in the same block with xor,
+   on the opposite branch must be another shift1 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_optimization::crc_cond_and_shift (const basic_block &pred_bb,
+				      const basic_block &xor_bb)
+{
+  gcond *cond = nullptr;
+  if (is_a<gcond *> (last_stmt (pred_bb)))
+    cond = as_a<gcond *> (last_stmt (pred_bb));
+  if (!cond)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "No condition.  Not crc.\n");
+      return false;
+    }
+
+  edge true_edge;
+  edge false_edge;
+  extract_true_false_edges_from_block (pred_bb, &true_edge, &false_edge);
+
+  basic_block xor_opposite_block;
+  /* Check that xor is done in case the MSB/LSB is 1.  */
+  if ((cond_true_is_checked_for_bit_one (cond) && true_edge->dest == xor_bb))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Xor is done on true branch\n");
+
+      xor_opposite_block = false_edge->dest;
+    }
+  else if (!cond_true_is_checked_for_bit_one (cond)
+	   && false_edge->dest == xor_bb)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Xor is done on false branch\n");
+
+      xor_opposite_block = true_edge->dest;
+    }
+  else
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "Xor is done if MSB/LSB is not one, not crc\n");
+
+      return false;
+    }
+
+  /* Check whether there is a dependence between
+     if condition's variable and xor-ed variable.  */
+  tree lhs = gimple_cond_lhs (cond);
+  tree rhs = gimple_cond_rhs (cond);
+  if (TREE_CODE (lhs) == SSA_NAME)
+    check_def_stmt_for_if (lhs);
+  else if (TREE_CODE (rhs) == SSA_NAME)
+    check_def_stmt_for_if (rhs);
+  else
+    return false; /* Both parts of condition are not SSA_NAME.  */
+
+  /* Return false if there is no dependence between if condition's variable
+     and xor-ed variable.  */
+  if (!crc_if_dep)
+    return false;
+
+  /* If the found shift is in the same block with xor,
+  check whether another shift exists in the opposite block.  */
+  if ((shift_before_xor && gimple_bb (shift_before_xor) == xor_bb)
+      || (shift_after_xor && gimple_bb (shift_after_xor) == xor_bb))
+    return exists_shift_for_opp_xor_shift (xor_opposite_block);
+  return true;
+}
+
+
+/* Checks whether it's ok that the statement is between shift and xor.
+  This check is not that accurate.  But it's enough to filter not CRCs.  */
+
+bool
+crc_optimization::is_acceptable_statement (const tree_code &stmt_code)
+{
+  return stmt_code == BIT_IOR_EXPR
+	 || stmt_code == BIT_AND_EXPR
+	 || stmt_code == BIT_XOR_EXPR
+	 || TREE_CODE_CLASS (stmt_code) == tcc_unary;
+}
+
+/* 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
+crc_optimization::can_not_be_shift_of_crc (gimple *assign_stmt,
+					   bool find_shift_before_xor)
+{
+  tree_code stmt_code = gimple_assign_rhs_code (assign_stmt);
+  if (stmt_code == LSHIFT_EXPR || stmt_code == RSHIFT_EXPR)
+    {
+      is_left_shift = (stmt_code == LSHIFT_EXPR);
+      /* Check that shift one is done,
+	 keep shift statement.  */
+      if (integer_onep (gimple_assign_rhs2 (assign_stmt)))
+	{
+	  if (find_shift_before_xor)
+	    {
+	      if (shift_before_xor)
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file,
+			     "Already there is one shift "
+			     "on the path to xor. not crc\n");
+
+		  clean_xor_maybe_crc = false;
+		  return true;
+		}
+	      shift_before_xor = assign_stmt;
+	    }
+	  else
+	    {
+	      shift_after_xor = assign_stmt;
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file,
+			 "Found shift1 after xor\n");
+	    }
+	  return false;
+	}
+      else
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "Found shift, but not with 1, not crc\n");
+	  clean_xor_maybe_crc = false;
+	  return true;
+	}
+
+    }
+    /* No need for more strict checks,
+       not CRCs may be filtered by the verification stage.  */
+  else if (!is_acceptable_statement (stmt_code))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "\nStmt with following operation "
+		 "code %s between xor and shift, "
+		 "may not be crc \n", get_tree_code_name (stmt_code));
+
+      return true;
+    }
+  return false;
+}
+
+
+/* This function goes up through the def-chain of the given name,
+   until doesn't encounter a phi statement or
+   if it does not meet certain conditions
+   depending on the passed check_dependency function.
+   The check_dependency may be the check_def_stmt_for_xor
+   or check_def_stmt_for_if function.  */
+
+void
+crc_optimization::get_dep (tree name,
+			   void (crc_optimization::*check_dependency) (
+			       tree ssa))
+{
+  if (!clean_xor_maybe_crc)
+    return;
+
+  tree ssa1 = NULL_TREE, ssa2 = NULL_TREE;
+
+  /* No definition chain for default defs.  */
+  if (SSA_NAME_IS_DEFAULT_DEF (name))
+    return;
+
+  gimple *stmt = SSA_NAME_DEF_STMT (name);
+
+  /* If it is an assigment statement - get first and second operand
+     if phi statement of loop's header bb - stop function's execution.  */
+  if (is_a<gassign *> (stmt))
+    {
+      ssa1 = gimple_assign_rhs1 (stmt);
+      ssa2 = gimple_assign_rhs2 (stmt);
+    }
+  else if (is_a<gphi *> (stmt)
+	   && (!bb_loop_header_p (gimple_bb (stmt))))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "Phi's definition IS NOT in loop header\n");
+
+      if (check_dependency == &crc_optimization::check_def_stmt_for_xor)
+	clean_xor_maybe_crc = false;
+      return;
+    }
+
+  /* Do some checks on definition statements of
+     assignment's first and second operands.  */
+  (this->*check_dependency) (ssa1);
+  (this->*check_dependency) (ssa2);
+  return;
+}
+
+
+/* Check whether the statement, dependent from xor's operands,
+   does shift operation (for calculating crc)
+   or is a phi statement.  */
+
+void
+crc_optimization::check_def_stmt_for_xor (tree dep)
+{
+  if (!gimple_range_ssa_p (dep))
+    return;
+  if (!clean_xor_maybe_crc)
+    return;
+
+  gimple *def_stmt = SSA_NAME_DEF_STMT (dep);
+
+  if (!def_stmt)
+    return;
+
+  if (is_gimple_assign (def_stmt))
+    if (can_not_be_shift_of_crc (def_stmt, true))
+      return;
+
+  /* Keep phi statement.  */
+  if (is_a<gphi *> (def_stmt))
+    {
+      if (first_phi_for_crc)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "Set second phi\n");
+
+	  second_phi_for_crc = def_stmt;
+	}
+      else
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "Set first phi\n");
+
+	  first_phi_for_crc = def_stmt;
+	}
+      return;
+    }
+
+  /* Get the def chain for the operand.  */
+  get_dep (dep, &crc_optimization::check_def_stmt_for_xor);
+}
+
+
+/* Walks through def-chain of if's condition and
+   checks whether if's condition and xor-ed variable
+   are dependent from the same variable.
+   (The crc variable is xor-ed if variable's MSB/LSB is 1).  */
+
+void
+crc_optimization::check_def_stmt_for_if (tree dep)
+{
+  if (!gimple_range_ssa_p (dep))
+    return;
+  gimple *def_stmt = SSA_NAME_DEF_STMT (dep);
+
+  if (!def_stmt)
+    return;
+
+  /* Checks whether if's condition and xor-ed variable are dependent
+     from the same variable.  */
+  if (is_a<gphi *> (def_stmt))
+    {
+      if ((first_phi_for_crc && first_phi_for_crc == def_stmt)
+	  || (second_phi_for_crc && second_phi_for_crc == def_stmt))
+	{
+	  crc_if_dep = true;
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "\nIf condition has dependence "
+		     "from the same variable as xor.\n");
+	}
+      return;
+    }
+
+  /* Get the def chain for the operand.  */
+  get_dep (dep, &crc_optimization::check_def_stmt_for_if);
+}
+
+
+/* Check whether found xor_stmt is for calculating crc.
+   The function fun calculates crc only if there is a shift operation
+   in the crc_loop.  */
+
+bool
+crc_optimization::xor_calculates_crc (function *fun, class loop *crc_loop,
+				      const gimple *xor_stmt)
+{
+  tree crc_var = gimple_assign_lhs (xor_stmt);
+  set_initial_values ();
+  get_dep (crc_var,
+	   &crc_optimization::check_def_stmt_for_xor);
+  if (!clean_xor_maybe_crc)
+    return false;
+
+  /* Check the case when shift is done after xor.  */
+  if (!shift_before_xor)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "No shift before xor\n");
+
+      set_all_statements_not_visited (fun);
+      find_shift_after_xor (crc_loop, crc_var);
+      if (!shift_after_xor)
+	return false;
+    }
+
+  /* Check that xor is done if MSB/LSB is one.
+     In presence of shift in the same loop with xor,
+     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 (crc_cond_and_shift (single_pred (bb), bb))
+	{
+	  set_all_statements_not_visited (fun);
+	  bool crc_is_returned = returned_value_depends_on_crc (crc_var);
+	  if (dump_file)
+	    {
+	      if (crc_is_returned)
+		{
+		  fprintf (dump_file,
+			   "\nAttention! %s function calculates CRC.\n",
+			   function_name (fun));
+		}
+	      else
+		{
+		  fprintf (dump_file,
+			   "\nFound naive crc implementation in %s.\n",
+			   function_name (fun));
+		}
+	    }
+	  return true;
+	}
+    }
+  return false;
+}
+
+
+/* Checks the loop iteration number.
+   The loop for CRC calculation may do 8, 16, 24, 32 iterations.  */
+
+bool
+crc_optimization::is_loop_of_crc_calculation (class loop *func_loop)
+{
+  loop_iteration_number = 0;
+  tree n_inters = number_of_latch_executions (func_loop);
+  if (n_inters == NULL_TREE || n_inters == chrec_dont_know)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "Loop iteration number is chrec_dont_know\n");
+
+    }
+  else if (tree_fits_uhwi_p (n_inters))
+    {
+      loop_iteration_number = tree_to_uhwi (n_inters);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Loop iteration number is %ld\n",
+		 loop_iteration_number);
+
+      if (!(loop_iteration_number == 7 || loop_iteration_number == 15
+	    || loop_iteration_number == 23 || loop_iteration_number == 31))
+	return false;
+    }
+  return true;
+}
+
+
+/* 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.  */
+
+bool
+crc_optimization::function_may_calculate_crc (function *fun)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\nExamining %s function\n",
+	     function_name (fun));
+
+  if (number_of_loops (fun) <= 1)
+    return false;
+
+  /* Get loops of the function.  */
+  auto loop_list = loops_list (fun, LI_ONLY_INNERMOST);
+  for (auto loop: loop_list)
+    {
+      /* Only examine innermost loops.  */
+      if (!loop || loop->inner)
+	continue;
+
+      if (!is_loop_of_crc_calculation (loop))
+	continue;
+
+      basic_block *bbs = get_loop_body_in_dom_order (loop);
+      /* Walk bbs of the loop.  */
+      for (unsigned int i = 0; i < loop->num_nodes; i++)
+	{
+	  basic_block bb = bbs[i];
+	  /* Walk instructions of bb.  */
+	  for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (
+	      bsi); gsi_next (&bsi))
+	    {
+	      gimple *stmt = gsi_stmt (bsi);
+	      /* If there is an xor instruction,
+		 check that it is calculating crc.  */
+	      if (is_gimple_assign (stmt)
+		  && gimple_assign_rhs_code (stmt) == BIT_XOR_EXPR)
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file,
+			     "Found xor, "
+			     "checking whether it is for crc calculation\n");
+
+		  if (xor_calculates_crc (fun, loop, stmt))
+		    {
+		      get_return_value_size (fun);
+		      print_crc_information ();
+		      return true;
+		    }
+		}
+	    }
+	}
+    }
+  return false;
+}
+
+unsigned int
+crc_optimization::execute (function *fun)
+{
+  function_may_calculate_crc (fun);
+  return 0;
+}
+
+namespace
+{
+
+    const pass_data pass_data_crc_optimization
+	= {
+	    GIMPLE_PASS, /* type */
+	    "crc", /* name */
+	    OPTGROUP_NONE, /* optinfo_flags */
+	    TV_GIMPLE_CRC_OPTIMIZATION, /* tv_id */
+	    (PROP_cfg | PROP_ssa), /* properties_required */
+	    0, /* properties_provided */
+	    0, /* properties_destroyed */
+	    0, /* todo_flags_start */
+	    0, /* todo_flags_finish */
+	};
+
+    class pass_crc_optimization : public gimple_opt_pass {
+     public:
+      pass_crc_optimization (gcc::context *ctxt)
+	  : gimple_opt_pass (pass_data_crc_optimization, ctxt)
+      {}
+
+      /* opt_pass methods: */
+      virtual bool gate (function *)
+      {
+	return flag_gimple_crc_optimization;
+      }
+
+      virtual unsigned int execute (function *);
+
+    }; // class pass_crc_optimization
+
+    unsigned int
+    pass_crc_optimization::execute (function *fun)
+    {
+      return crc_optimization ().execute (fun);
+    }
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_crc_optimization (gcc::context *ctxt)
+{
+  return new pass_crc_optimization (ctxt);
+}
diff --git a/gcc/opts.cc b/gcc/opts.cc
index a032cd4..cbcab1f 100644
--- a/gcc/opts.cc
+++ b/gcc/opts.cc
@@ -647,6 +647,7 @@ static const struct default_options default_options_table[] =
       VECT_COST_MODEL_VERY_CHEAP },
     { OPT_LEVELS_2_PLUS, OPT_finline_functions, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_ftree_loop_distribute_patterns, NULL, 1 },
+    { OPT_LEVELS_2_PLUS, OPT_fgimple_crc_optimization, NULL, 1 },
 
     /* -O2 and above optimizations, but not -Os or -Og.  */
     { OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_falign_functions, NULL, 1 },
@@ -2044,6 +2045,8 @@ enable_fdo_optimizations (struct gcc_options *opts,
   SET_OPTION_IF_UNSET (opts, opts_set, flag_loop_interchange, value);
   SET_OPTION_IF_UNSET (opts, opts_set, flag_unroll_jam, value);
   SET_OPTION_IF_UNSET (opts, opts_set, flag_tree_loop_distribution, value);
+  SET_OPTION_IF_UNSET (opts, opts_set, flag_gimple_crc_optimization, value);
+
 }
 
 /* -f{,no-}sanitize{,-recover}= suboptions.  */
diff --git a/gcc/passes.def b/gcc/passes.def
index c9a8f19..762eaa7 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -285,6 +285,7 @@ along with GCC; see the file COPYING3.  If not see
 	  NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */);
 	  NEXT_PASS (pass_iv_canon);
 	  NEXT_PASS (pass_loop_distribution);
+	  NEXT_PASS (pass_crc_optimization);
 	  NEXT_PASS (pass_linterchange);
 	  NEXT_PASS (pass_copy_prop);
 	  NEXT_PASS (pass_graphite);
diff --git a/gcc/testsuite/gcc.dg/crc-1.c b/gcc/testsuite/gcc.dg/crc-1.c
new file mode 100644
index 0000000..8f61f15
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-1.c
@@ -0,0 +1,59 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdio.h>
+#include <stdint.h>
+
+#define CRC16 0x8005
+
+uint16_t gen_crc16(const uint8_t *data, uint16_t size) {
+    uint16_t out = 0;
+    int bits_read = 0, bit_flag;
+
+    printf("buffer in function %s\n", data);
+
+    if (data == NULL)
+        return 0;
+
+    while (size > 0) {
+        bit_flag = out >> 15;
+
+        out <<= 1;
+        out |= (*data >> bits_read) & 1;
+
+        bits_read++;
+        if (bits_read > 7) {
+            bits_read = 0;
+            data++;
+            size--;
+        }
+
+        if (bit_flag)
+            out ^= CRC16;
+
+    }
+
+    int i;
+    for (i = 0; i < 16; ++i) {
+        bit_flag = out >> 15;
+        out <<= 1;
+        if (bit_flag)
+            out ^= CRC16;
+    }
+
+    uint16_t crc = 0;
+    i = 0x8000;
+    int j = 0x0001;
+    for (; i != 0; i >>= 1, j <<= 1) {
+        if (i & out) crc |= j;
+    }
+
+    return crc;
+}
+
+/* { dg-final { scan-tree-dump "Found naive crc implementation in gen_crc16." "crc"} } */
+/* { dg-final { scan-tree-dump "Return size is 16" "crc"} } */
+/* { dg-final { scan-tree-dump "Loop iteration number is 15" "crc"} } */
+/* { dg-final { scan-tree-dump "Bit forward" "crc"} } */
+
+
diff --git a/gcc/testsuite/gcc.dg/crc-10.c b/gcc/testsuite/gcc.dg/crc-10.c
new file mode 100644
index 0000000..33aa760
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-10.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+#define POLY (0x1070U << 3)
+#define u8 uint8_t
+#define u16 uint16_t
+
+u8 crc8(u16 data) {
+    int i;
+    for (i = 0; i < 8; i++) {
+        if (data & 0x8000)
+            data = data ^ POLY;
+        data = data << 1;
+    }
+    return (u8)(data >> 8);
+}
+
+/* { dg-final { scan-tree-dump "Attention! crc8 function calculates CRC." "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"} } */
+
+
diff --git a/gcc/testsuite/gcc.dg/crc-11.c b/gcc/testsuite/gcc.dg/crc-11.c
new file mode 100644
index 0000000..89d12f8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-11.c
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+typedef unsigned short ee_u16;
+typedef unsigned char ee_u8;
+
+//loop iteration number is 5
+ee_u16 not_crcu8(ee_u8 data, ee_u16 crc) {
+    ee_u8 i = 0, x16 = 0, carry = 0;
+    for (i = 0; i < 5; i++) {
+        x16 = (ee_u8) ((data & 1) ^ ((ee_u8) crc & 1));
+        data >>= 1;
+        if (x16 == 1) {
+            crc ^= 0x4002;
+            carry = 1;
+        } else
+            carry = 0;
+        crc >>= 1;
+        if (carry)
+            crc |= 0x8000;
+        else
+            crc &= 0x7fff;
+    }
+    return crc;
+}
+/* { dg-final { scan-tree-dump-times "Attention! crcu8 function calculates CRC." 0 "crc"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-12.c b/gcc/testsuite/gcc.dg/crc-12.c
new file mode 100644
index 0000000..66c6743
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-12.c
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+typedef uint8_t crc;
+#define TOPBIT (1 << 7)
+
+//shift not by one
+crc
+notCrc(uint8_t const message[], int nBytes) {
+    crc remainder = 0;
+    for (int byte = 0; byte < nBytes; ++byte) {
+        remainder ^= message[byte] ;
+        for (uint8_t bit = 8; bit > 0; --bit) {
+            if (remainder & TOPBIT) {
+                remainder = (remainder << 3) ^ 1234;
+            } else {
+                remainder = (remainder << 9);
+            }
+        }
+    }
+    return (remainder);
+}
+
+/* { dg-final { scan-tree-dump-times "Attention! notCrc function calculates CRC." 0 "crc"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-13.c b/gcc/testsuite/gcc.dg/crc-13.c
new file mode 100644
index 0000000..ee4edde
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-13.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+//no shift in case of xor
+uint16_t not_crc16_update(uint16_t crc, uint8_t a) {
+	
+    int i;
+    crc ^= a;
+    for (i = 0; i < 8; ++i) {
+        if (crc & 1)
+            crc = crc ^ 0xA001;
+        else
+            crc = (crc >> 1);
+    }
+    return crc;
+}
+
+/* { dg-final { scan-tree-dump-times "Attention! not_crc16_update function calculates CRC." 0 "crc"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-14.c b/gcc/testsuite/gcc.dg/crc-14.c
new file mode 100644
index 0000000..ab1cf04
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-14.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+//shift and xor only if lsb is 1
+uint16_t not_crc(uint16_t crc, uint8_t a) {
+    int i;
+    crc ^= a;
+    for (i = 0; i < 8; ++i) {
+        if (crc & 1)
+            crc = (crc >> 1) ^ 0xA001;
+    }
+    return crc;
+}
+
+/* { dg-final { scan-tree-dump-times "Attention! not_crc function calculates CRC." 0 "crc"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-15.c b/gcc/testsuite/gcc.dg/crc-15.c
new file mode 100644
index 0000000..a9f8c84
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-15.c
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdio.h>
+
+typedef unsigned char uint8_t;
+
+//no xor
+uint8_t not_crc(uint8_t *data, size_t len) {
+    uint8_t crc = 0xff;
+    size_t i, j;
+    for (i = 0; i < len; i++) {
+        crc ^= data[i];
+        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-times "Attention! not_crc function calculates CRC." 0 "crc"} } */
+
+
diff --git a/gcc/testsuite/gcc.dg/crc-16.c b/gcc/testsuite/gcc.dg/crc-16.c
new file mode 100644
index 0000000..4e0983a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-16.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+#define POLY (0x1070U << 3)
+#define u8 uint8_t
+#define u16 uint16_t
+
+//xor in case 0
+u8 not_crc(u16 data) {
+    int i;
+    for (i = 0; i < 8; i++) {
+        if (data & 0x0000)
+            data = data ^ POLY;
+        data = data << 1;
+    }
+    return (u8)(data >> 8);
+}
+
+/* { dg-final { scan-tree-dump-times "Attention! not_crc function calculates CRC." 0 "crc"} } */
+
+
diff --git a/gcc/testsuite/gcc.dg/crc-17.c b/gcc/testsuite/gcc.dg/crc-17.c
new file mode 100644
index 0000000..9f04c04
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-17.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+//in one case is called shift left, in another shift right
+uint16_t not_crc(uint16_t crc, uint8_t a) {
+    int i;
+    crc ^= a;
+    for (i = 0; i < 8; ++i) {
+        if (crc & 1)
+            crc = (crc << 1) ^ 0xA001;
+        else
+            crc = crc >> 1;
+    }
+    return crc;
+}
+
+/* { dg-final { scan-tree-dump-times "Attention! not_crc function calculates CRC." 0 "crc"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-18.c b/gcc/testsuite/gcc.dg/crc-18.c
new file mode 100644
index 0000000..b023fc2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-18.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+//xor is done in case lsb is 0
+int16_t not_crc(int16_t crc, int8_t a) {
+    int i;
+    crc ^= a;
+    for (i = 0; i < 8; ++i) {
+        if (crc << 15 == 0)
+            crc = (crc >> 1) ^ 0xA001;
+        else
+            crc = crc >> 1;
+    }
+    return crc;
+}
+
+/* { dg-final { scan-tree-dump-times "Attention! not_crc function calculates CRC." 0 "crc"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-19.c b/gcc/testsuite/gcc.dg/crc-19.c
new file mode 100644
index 0000000..eea073d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-19.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+//no conditional xor
+uint16_t not_crc(uint16_t crc, uint8_t a) {
+    int i;
+    crc ^= a;
+    for (i = 0; i < 8; ++i) {
+            crc = (crc << 1) ^ 0xA001;
+    }
+    return crc;
+}
+
+/* { dg-final { scan-tree-dump-times "Attention! not_crc function calculates CRC." 0 "crc"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-2.c b/gcc/testsuite/gcc.dg/crc-2.c
new file mode 100644
index 0000000..99319e9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-2.c
@@ -0,0 +1,28 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#define CRC16_CCITT     0x102
+#define POLYNOM         CRC16_CCITT
+
+unsigned int crc16(unsigned int crcValue, unsigned char newByte) {
+    unsigned char i;
+
+    for (i = 0; i < 8; i++) {
+
+        if (((crcValue & 0x8000) >> 8) ^ (newByte & 0x80)) {
+            crcValue = (crcValue << 1) ^ POLYNOM;
+        } else {
+            crcValue = (crcValue << 1);
+        }
+
+        newByte <<= 1;
+    }
+
+    return crcValue;
+}
+
+/* { dg-final { scan-tree-dump "Attention! crc16 function calculates CRC." "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"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-20.c b/gcc/testsuite/gcc.dg/crc-20.c
new file mode 100644
index 0000000..e9b6897
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-20.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+//Spoiled crc value
+uint16_t not_crc(uint16_t crc, uint8_t a) {
+    int i;
+    crc ^= a;
+    for (i = 0; i < 8; ++i) {
+        if (crc & 1) {
+            crc = 0;
+            crc = (crc << 1) ^ 0xA001;
+        }
+        else
+            crc = crc >> 1;
+    }
+    return crc;
+}
+
+/* { dg-final { scan-tree-dump-times "Attention! not_crc function calculates CRC." 0 "crc"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-21.c b/gcc/testsuite/gcc.dg/crc-21.c
new file mode 100644
index 0000000..c54920a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-21.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+typedef unsigned short ee_u16;
+typedef unsigned char ee_u8;
+
+ee_u16 not_crc(ee_u8 data, ee_u16 crc) {
+    ee_u8 i = 0, carry = 0;
+    for (i = 0; i < 8; i++) {
+        data >>= 1;
+        if (data == 1) {
+            crc ^= 0x4002;
+            carry = 1;
+        } else
+            carry = 0;
+        crc >>= 1;
+        if (carry)
+            crc |= 0x8000;
+        else
+            crc &= 0x7fff;
+    }
+    return crc;
+}
+
+/* { dg-final { scan-tree-dump-times "Attention! not_crc function calculates CRC." 0 "crc"} } */
\ No newline at end of file
diff --git a/gcc/testsuite/gcc.dg/crc-22.c b/gcc/testsuite/gcc.dg/crc-22.c
new file mode 100644
index 0000000..153eb6b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-22.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+uint8_t not_crc(uint8_t crc, uint8_t data) {
+    uint8_t i;
+    crc = crc ^ data;
+    for (i = 0; i < 8; i++) {
+        if (data & 0x01)
+            crc = (crc >> 1) ^ 0x8C;
+        else
+            crc >>= 1;
+    }
+    return crc;
+}
+/* { dg-final { scan-tree-dump-times "Attention! not_crc function calculates CRC." 0 "crc"} } */
diff --git a/gcc/testsuite/gcc.dg/crc-3.c b/gcc/testsuite/gcc.dg/crc-3.c
new file mode 100644
index 0000000..71c57ad
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-3.c
@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+unsigned short crc16(char *data_p, unsigned short length) {
+    unsigned char i;
+    unsigned int data;
+    unsigned int crc = 0xffff;
+
+    if (length == 0)
+        return (~crc);
+
+    do {
+        for (i = 0, data = (unsigned int) 0xff & *data_p++;
+             i < 8;
+             i++, data >>= 1) {
+            if ((crc & 0x0001) ^ (data & 0x0001))
+                crc = (crc >> 1) ^ 0x8408;
+            else crc >>= 1;
+        }
+    } while (--length);
+
+    crc = ~crc;
+    data = crc;
+    crc = (crc << 8) | (data >> 8 & 0xff);
+
+    return (crc);
+}
+
+/* { dg-final { scan-tree-dump "Attention! crc16 function calculates CRC." "crc"} } */
+/* { dg-final { scan-tree-dump "Return size is 16" "crc"} } */
+/* { dg-final { scan-tree-dump "Loop iteration number is 7" "crc"} } */
+/* { dg-final { scan-tree-dump "Bit reversed" "crc"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-4.c b/gcc/testsuite/gcc.dg/crc-4.c
new file mode 100644
index 0000000..0aa1156
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-4.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+uint16_t crc16_update(uint16_t crc, uint8_t a) {
+    int i;
+    crc ^= a;
+    for (i = 0; i < 8; ++i) {
+        if (crc & 1)
+            crc = (crc >> 1) ^ 0xA001;
+        else
+            crc = (crc >> 1);
+    }
+    return crc;
+}
+
+/* { dg-final { scan-tree-dump "Attention! crc16_update function calculates CRC." "crc"} } */
+/* { dg-final { scan-tree-dump "Return size is 16" "crc"} } */
+/* { dg-final { scan-tree-dump "Loop iteration number is 7" "crc"} } */
+/* { dg-final { scan-tree-dump "Bit reversed" "crc"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-5.c b/gcc/testsuite/gcc.dg/crc-5.c
new file mode 100644
index 0000000..9014937
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-5.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+typedef unsigned short ee_u16;
+typedef unsigned char ee_u8;
+
+ee_u16 crcu8(ee_u8 data, ee_u16 crc) {
+    ee_u8 i = 0, x16 = 0, carry = 0;
+    for (i = 0; i < 8; i++) {
+        x16 = (ee_u8) ((data & 1) ^ ((ee_u8) crc & 1));
+        data >>= 1;
+        if (x16 == 1) {
+            crc ^= 0x4002;
+            carry = 1;
+        } else
+            carry = 0;
+        crc >>= 1;
+        if (carry)
+            crc |= 0x8000;
+        else
+            crc &= 0x7fff;
+    }
+    return crc;
+}
+/* { dg-final { scan-tree-dump "Attention! crcu8 function calculates CRC." "crc"} } */
+/* { dg-final { scan-tree-dump "Return size is 16" "crc"} } */
+/* { dg-final { scan-tree-dump "Loop iteration number is 7" "crc"} } */
+/* { dg-final { scan-tree-dump "Bit reversed" "crc"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-6.c b/gcc/testsuite/gcc.dg/crc-6.c
new file mode 100644
index 0000000..7fa60b2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-6.c
@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+typedef uint8_t crc;
+#define WIDTH (8 * sizeof(crc))
+#define TOPBIT (1 << (WIDTH - 1))
+
+crc
+crcSlow(uint8_t const message[], int nBytes) {
+    crc remainder = 0;
+/*
+* Perform modulo-2 division, a byte at a time.
+*/
+    for (int byte = 0; byte < nBytes; ++byte) {
+        remainder ^= (message[byte] << (WIDTH - 8));
+        for (uint8_t bit = 8; bit > 0; --bit) {
+            if (remainder & TOPBIT) {
+                remainder = (remainder << 1) ^ 1234;
+            } else {
+                remainder = (remainder << 1);
+            }
+        }
+    }
+    return (remainder);
+}
+
+/* { dg-final { scan-tree-dump "Attention! crcSlow function calculates CRC." "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"} } */
+
diff --git a/gcc/testsuite/gcc.dg/crc-7.c b/gcc/testsuite/gcc.dg/crc-7.c
new file mode 100644
index 0000000..e6815c0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-7.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+uint16_t crc_xmodem_update(uint16_t crc, uint8_t data) {
+    int i;
+    crc = crc ^ ((uint16_t) data << 8);
+    for (i = 0; i < 8; i++) {
+        if (crc & 0x8000)
+            crc = (crc << 1) ^ 0x1021;
+        else
+            crc <<= 1;
+    }
+    return crc;
+}
+
+/* { dg-final { scan-tree-dump "Attention! crc_xmodem_update function calculates CRC." "crc"} } */
+/* { dg-final { scan-tree-dump "Return size is 16" "crc"} } */
+/* { dg-final { scan-tree-dump "Loop iteration number is 7" "crc"} } */
+/* { dg-final { scan-tree-dump "Bit forward" "crc"} } */
+
+
diff --git a/gcc/testsuite/gcc.dg/crc-8.c b/gcc/testsuite/gcc.dg/crc-8.c
new file mode 100644
index 0000000..730b7a9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-8.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdint.h>
+
+uint8_t _crc_ibutton_update(uint8_t crc, uint8_t data) {
+    uint8_t i;
+    crc = crc ^ data;
+    for (i = 0; i < 8; i++) {
+        if (crc & 0x01)
+            crc = (crc >> 1) ^ 0x8C;
+        else
+            crc >>= 1;
+    }
+    return crc;
+}
+
+/* { dg-final { scan-tree-dump "Attention! _crc_ibutton_update function calculates CRC." "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 reversed" "crc"} } */
+
+
diff --git a/gcc/testsuite/gcc.dg/crc-9.c b/gcc/testsuite/gcc.dg/crc-9.c
new file mode 100644
index 0000000..2eb7967
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/crc-9.c
@@ -0,0 +1,28 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-crc" } */
+
+#include <stdio.h>
+
+typedef unsigned char uint8_t;
+
+uint8_t gencrc(uint8_t *data, size_t len) {
+    uint8_t crc = 0xff;
+    size_t i, j;
+    for (i = 0; i < len; i++) {
+        crc ^= data[i];
+        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 "Attention! gencrc function calculates CRC." "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"} } */
+
+
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 9523598..8d28645 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -311,6 +311,7 @@ DEFTIMEVAR (TV_INITIALIZE_RTL        , "initialize rtl")
 DEFTIMEVAR (TV_GIMPLE_LADDRESS       , "address lowering")
 DEFTIMEVAR (TV_TREE_LOOP_IFCVT       , "tree loop if-conversion")
 DEFTIMEVAR (TV_WARN_ACCESS           , "access analysis")
+DEFTIMEVAR (TV_GIMPLE_CRC_OPTIMIZATION, "crc optimization")
 
 /* Everything else in rest_of_compilation not included above.  */
 DEFTIMEVAR (TV_EARLY_LOCAL	     , "early local passes")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 6cdaed7..a4a781c 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -387,6 +387,7 @@ extern gimple_opt_pass *make_pass_graphite_transforms (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_if_conversion (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_if_to_switch (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_loop_distribution (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_crc_optimization (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_vectorize (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_simduid_cleanup (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_slp_vectorize (gcc::context *ctxt);