---
 gcc/Makefile.in                |    1 +
 gcc/common.opt                 |   10 +
 gcc/common.opt.urls            |    3 +
 gcc/doc/invoke.texi            |   16 +-
 gcc/gimple-crc-optimization.cc | 1000 ++++++++++++++++++++++++++++++++
 gcc/opts.cc                    |    2 +
 gcc/passes.def                 |    1 +
 gcc/timevar.def                |    1 +
 gcc/tree-pass.h                |    1 +
 9 files changed, 1034 insertions(+), 1 deletion(-)
 create mode 100644 gcc/gimple-crc-optimization.cc

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 68fda1a7591..a7054eda9c5 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1717,6 +1717,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 ea39f87ae71..8395c100fe0 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2399,6 +2399,16 @@ fsave-optimization-record
 Common Var(flag_save_optimization_record) Optimization
 Write a SRCFILE.opt-record.json file detailing what optimizations were performed.
 
+foptimize-crc
+Common Var(flag_optimize_crc) Optimization
+Detect loops calculating CRC and replace with faster implementation.
+If the target supports CRC instruction and the CRC loop uses the same
+polynomial as the one used in the CRC instruction, directly replace with the
+corresponding CRC instruction.
+Otherwise, if the target supports carry-less-multiplication instruction,
+generate CRC using it.
+If neither case applies, generate table-based CRC.
+
 foptimize-register-move
 Common Ignore
 Does nothing. Preserved for backward compatibility.
diff --git a/gcc/common.opt.urls b/gcc/common.opt.urls
index b917f90b0ff..8b61a371c05 100644
--- a/gcc/common.opt.urls
+++ b/gcc/common.opt.urls
@@ -1007,6 +1007,9 @@ UrlSuffix(gcc/Developer-Options.html#index-fopt-info)
 fsave-optimization-record
 UrlSuffix(gcc/Developer-Options.html#index-fsave-optimization-record)
 
+foptimize-crc
+UrlSuffix(gcc/Optimize-Options.html#index-foptimize-crc)
+
 foptimize-sibling-calls
 UrlSuffix(gcc/Optimize-Options.html#index-foptimize-sibling-calls)
 
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 019e0a5ca80..2b10e7d4bdc 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -598,7 +598,7 @@ Objective-C and Objective-C++ Dialects}.
 -fno-peephole2  -fno-printf-return-value  -fno-sched-interblock
 -fno-sched-spec  -fno-signed-zeros
 -fno-toplevel-reorder  -fno-trapping-math  -fno-zero-initialized-in-bss
--fomit-frame-pointer  -foptimize-sibling-calls
+-fomit-frame-pointer  -foptimize-crc  -foptimize-sibling-calls
 -fpartial-inlining  -fpeel-loops  -fpredictive-commoning
 -fprefetch-loop-arrays
 -fprofile-correction
@@ -12664,6 +12664,7 @@ also turns on the following optimization flags:
 -fipa-ra  -fipa-sra  -fipa-vrp
 -fisolate-erroneous-paths-dereference
 -flra-remat
+-foptimize-crc
 -foptimize-sibling-calls
 -foptimize-strlen
 -fpartial-inlining
@@ -12828,6 +12829,19 @@ leaf functions.
 
 Enabled by default at @option{-O1} and higher.
 
+@opindex foptimize-crc
+@item -foptimize-crc
+Detect loops calculating CRC (performing polynomial long division) and
+replace them with a faster implementation.  Detect 8, 16, 32, and 64 bit CRC,
+with a constant polynomial without the leading 1 bit,
+for both bit-forward and bit-reversed cases.
+If the target supports a CRC instruction and the polynomial used in the source
+code matches the polynomial used in the CRC instruction, generate that CRC
+instruction.  Otherwise, if the target supports a carry-less-multiplication
+instruction, generate CRC using it; otherwise generate table-based CRC.
+
+Enabled by default at @option{-O2} and higher.
+
 @opindex foptimize-sibling-calls
 @item -foptimize-sibling-calls
 Optimize sibling and tail recursive calls.
diff --git a/gcc/gimple-crc-optimization.cc b/gcc/gimple-crc-optimization.cc
new file mode 100644
index 00000000000..c67b0fd38c3
--- /dev/null
+++ b/gcc/gimple-crc-optimization.cc
@@ -0,0 +1,1000 @@
+/* CRC optimization.
+   Copyright (C) 2022-2024 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 "cfgloop.h"
+#include "tree-scalar-evolution.h"
+
+class crc_optimization {
+ private:
+  /* The statement doing shift 1 operation before/after xor operation.  */
+  gimple *m_shift_stmt;
+
+  /* Phi statement from the head of the loop for CRC.  */
+  gphi *m_phi_for_crc;
+
+  /* Phi statement for the data from the head of the loop if exists,
+     otherwise - nullptr.  */
+  gphi *m_phi_for_data;
+
+  /* The loop, which probably calculates CRC.  */
+  class loop *m_crc_loop;
+
+  /* Depending on the value of M_IS_BIT_FORWARD, may be forward or reversed CRC.
+     If M_IS_BIT_FORWARD, then it is bit-forward implementation,
+     otherwise bit-reversed.  */
+  bool m_is_bit_forward;
+
+  /* Sets initial values for CRC analyses.  */
+  void set_initial_values ();
+
+  /* This is the main function that checks whether the given LOOP
+     calculates CRC and extracts details of the CRC calculation.
+
+     The main idea is to find the innermost loop with 8, 16, 24, 32, 64
+     iterations and xor instruction (xor is the key operation for naive CRC
+     calculation). Then, checks that the variable is shifted by one before/after
+     being used in xor.
+     Xor must be done under the condition of MSB/LSB being 1.  */
+  bool loop_may_calculate_crc (class loop *loop);
+
+  /* Returns true if there is only two conditional blocks in the loop
+     (one may be for the CRC bit check and the other for the loop counter).
+     This may filter out some real CRCs, where more than one condition
+     is checked for the CRC calculation.  */
+  static bool loop_contains_two_conditional_bb (basic_block *loop_bbs,
+						unsigned loop_num_nodes);
+
+  /* Checks the FUNC_LOOP loop's iteration number.
+     The loop for CRC calculation may do 8, 16, 24, 32, 64 iterations.  */
+  bool satisfies_crc_loop_iteration_count (class loop *func_loop);
+
+  /* This function checks if the XOR_STMT is used for CRC calculation.
+     It verifies the presence of a shift operation in the CRC_FUN function
+     inside the CRC loop.  It examines operands of XOR, its dependencies, the
+     relative position of the shift operation, and the existence of a shift
+     operation in the opposite branch of conditional statements.  It also
+     checks if XOR is performed when MSB/LSB is one.
+     If these conditions are met, the XOR operation may be part of a CRC
+     calculation.  The function returns true if these conditions are fulfilled,
+     otherwise, it returns false.  */
+  bool xor_calculates_crc (function *crc_fun, const gimple *xor_stmt);
+
+  /* Returns true if we can get definition of the VARIABLE, and the definition
+     it's not outside the loop.  Otherwise, returns false.  */
+  bool passes_checks_for_def_chain (tree variable);
+
+  /* This function goes up through the def-use chains of the parameter NAME.
+     Gathers all the statements within the loop,
+     from which the variable depends on and adds to the USE_DEFS.
+     Returns false, if there is a statement that may not exist in the CRC
+     loop.  Otherwise, returns true.  */
+  bool set_defs (tree name, auto_vec<gimple *>& use_defs,
+		 bool keep_only_header_phis);
+
+  /* Set M_PHI_FOR_CRC and M_PHI_FOR_DATA fields.
+     Returns false if there are more than two (as in CRC calculation only CRC's
+     and data's phi may exist) or no phi statements in STMTS (at least there
+     must be CRC's phi).
+     Otherwise, returns true.  */
+  bool set_crc_and_data_phi (auto_vec<gimple *>& stmts);
+
+  /*  Returns true if the variable checked in the condition depends on possible
+      CRC value.  Otherwise, returns false.  */
+  bool cond_depends_on_crc (auto_vec<gimple *>& stmts);
+
+
+  /* Checks that the condition is for checking CRC.
+     Returns true if xor is done under the condition of MSB/LSB being 1, and
+     the condition's variable and xor-ed variable depend on the same variable.
+     Otherwise, returns false.
+     XOR_BB is the basic block, where the 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 (basic_block pred_bb, basic_block xor_bb);
+
+  /* Returns true if xor is done in case the MSB/LSB is 1.
+     Otherwise, returns false.
+     In CRC calculation algorithms CRC is xor-ed with the polynomial only
+     if MSB/LSB is 1.
+
+     PRED_BB is the block containing the condition for the xor.
+     XOR_BB is the one of the successor blocks of PRED_BB, it is assumed that
+     CRC is xor-ed with the polynomial in XOR_BB.
+     COND is the condition, which is checked to satisfy the CRC condition.  */
+  bool is_crc_satisfiable_cond (basic_block pred_bb, basic_block xor_bb,
+				gcond *cond);
+
+  /* Checks that the variable used in the condition COND is the assumed CRC
+     (or depends on the assumed CRC).
+     Also sets data member m_phi_for_data if it isn't set and exists.  */
+  bool is_crc_checked (gcond *cond);
+
+  /* Returns true if condition COND checks MSB/LSB bit is 1.
+     Otherwise, return false.  */
+  static bool cond_true_is_checked_for_bit_one (const gcond *cond);
+
+  /* Returns opposite block of the XOR_BB from PRED_BB's dest blocks.  */
+  static basic_block get_xor_bb_opposite (basic_block pred_bb,
+					  basic_block xor_bb);
+
+  /* Checks whether the pair of xor's shift exists in the opposite
+     basic block (OPPOSITE_BB).
+     If there is a shift and xor in the same block,
+     then in the opposite block must be another shift.  */
+  bool exists_shift_for_opp_xor_shift (basic_block opposite_bb);
+
+  /* Follow def-use chains of XORED_CRC and return the statement where
+     XORED_CRC is shifted by one bit position.  Only PHI statements are
+     allowed between XORED_CRC and the shift in the def-use chain.
+
+   If no such statement is found, return NULL.  */
+  gimple *find_shift_after_xor (tree xored_crc);
+
+  /* Returns the statement which does shift 1 operation.
+     If there is no such statement, returns nullptr.
+     STMTS - are the statements within the loop before xor operation on
+     which possible CRC variable depends.  */
+  gimple *find_shift_before_xor (const auto_vec <gimple *> &stmts);
+
+  /* Returns true if ASSIGN_STMT does shift with 1.
+     Otherwise, returns false.  */
+  bool can_be_crc_shift (gimple *assign_stmt);
+
+  /* Returns true if the operation done in ASSIGN_STMT can occur during CRC
+     calculation.  Otherwise, returns false.  */
+  bool can_not_be_crc_stmt (gimple *assign_stmt);
+
+  /* Returns true if the statement with STMT_CODE may occur in CRC calculation.
+     Otherwise, returns false.  */
+  static bool is_acceptable_stmt_code (const tree_code &stmt_code);
+
+  /* Prints extracted details of CRC calculation.  */
+  void dump_crc_information ();
+
+ public:
+  crc_optimization () : m_visited_stmts (BITMAP_ALLOC (NULL)),
+			m_crc_loop (nullptr)
+  {
+    set_initial_values ();
+  }
+  ~crc_optimization ()
+  {
+    BITMAP_FREE (m_visited_stmts);
+  }
+  unsigned int execute (function *fun);
+};
+
+/* Prints extracted details of CRC calculation.  */
+
+void
+crc_optimization::dump_crc_information ()
+{
+  if (dump_file)
+    {
+      fprintf (dump_file,
+	       "Loop iteration number is " HOST_WIDE_INT_PRINT_UNSIGNED ".\n",
+	       tree_to_uhwi (m_crc_loop->nb_iterations));
+      if (m_is_bit_forward)
+	fprintf (dump_file, "Bit forward.\n");
+      else
+	fprintf (dump_file, "Bit reversed.\n");
+    }
+}
+
+/* Goes down by def-use chain (within the CRC loop) and returns the statement
+   where variable (dependent on xor-ed variable) is shifted with 1.
+   Between xor and shift operations only phi statements are allowed.
+   Otherwise, returns nullptr.  */
+
+gimple *
+crc_optimization::find_shift_after_xor (tree xored_crc)
+{
+  imm_use_iterator imm_iter;
+  use_operand_p use_p;
+
+  gcc_assert (TREE_CODE (xored_crc) == SSA_NAME);
+
+  unsigned v = SSA_NAME_VERSION (xored_crc);
+  if (bitmap_bit_p (m_visited_stmts, v))
+    return nullptr;
+  bitmap_set_bit (m_visited_stmts, v);
+
+  /* Iterate through the immediate uses of the XORED_CRC.
+     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, xored_crc)
+    {
+      gimple *stmt = USE_STMT (use_p);
+      // Consider only statements within the loop
+      if (!flow_bb_inside_loop_p (m_crc_loop, gimple_bb (stmt)))
+	continue;
+
+      /* 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 searching if encountered the loop's beginning.  */
+	  if (bb_loop_header_p (gimple_bb (stmt)))
+	    continue;
+
+	  return find_shift_after_xor (gimple_phi_result (stmt));
+	}
+      else if (is_gimple_assign (stmt))
+	{
+	  /* Check that stmt does shift by 1.
+	     There are no other statements between
+	     xor and shift, in CRC cases we detect.  */
+	  if (can_be_crc_shift (stmt))
+	    return stmt;
+	  return nullptr;
+	}
+      else if (!is_gimple_debug (stmt))
+	return  nullptr;
+    }
+    return nullptr;
+}
+
+/* Returns opposite block of the XOR_BB from PRED_BB's dest blocks.  */
+
+basic_block
+crc_optimization::get_xor_bb_opposite (basic_block pred_bb, basic_block xor_bb)
+{
+  /* Check that the predecessor block has exactly two successors.  */
+  if (EDGE_COUNT (pred_bb->succs) != 2)
+    return nullptr;
+
+  edge e0 = EDGE_SUCC (pred_bb, 0);
+  edge e1 = EDGE_SUCC (pred_bb, 1);
+
+  /* Ensure neither outgoing edge is marked as complex.  */
+  if ((e0->flags & EDGE_COMPLEX)
+      || (e1->flags & EDGE_COMPLEX))
+    return nullptr;
+
+  /* Check that one of the successors is indeed XOR_BB.  */
+  gcc_assert ((e0->dest == xor_bb)
+	      || (e1->dest == xor_bb));
+
+  /* Return the opposite block of XOR_BB.  */
+  if (EDGE_SUCC (pred_bb, 0)->dest != xor_bb)
+    return e0->dest;
+  return e1->dest;
+}
+
+/* Checks whether the pair of xor's shift exists in the opposite
+   basic block (OPPOSITE_BB).
+   If there is a shift and 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 opposite_bb)
+{
+  if (!opposite_bb)
+    return false;
+
+  /* Walk through the instructions of given basic block.  */
+  for (gimple_stmt_iterator bsi = gsi_start_nondebug_bb (opposite_bb);
+       !gsi_end_p (bsi); gsi_next_nondebug (&bsi))
+    {
+      gimple *stmt = gsi_stmt (bsi);
+      /* Find assignment statement with shift operation.
+	 Check that shift's direction is same with the shift done
+	 on the path with xor, and it is a shift by one.  */
+      if (is_gimple_assign (stmt))
+	{
+	  if (gimple_assign_rhs_code (stmt)
+	      == gimple_assign_rhs_code (m_shift_stmt)
+	      && integer_onep (gimple_assign_rhs2 (stmt)))
+	    return true;
+	}
+    }
+  /* If there is no shift, return false.  */
+  return false;
+}
+
+/* Returns true if condition COND checks MSB/LSB bit is 1.
+   Otherwise, return false.  */
+
+bool
+crc_optimization::cond_true_is_checked_for_bit_one (const gcond *cond)
+{
+  if (!cond)
+    return false;
+
+  tree rhs = gimple_cond_rhs (cond);
+  enum tree_code code = gimple_cond_code (cond);
+
+  /* If the condition is something == 1 -> return true.  */
+  if (code == EQ_EXPR && integer_onep (rhs))
+    return true;
+
+  /* If the condition is something != 0  or something < 0 -> return true.  */
+  if ((code == NE_EXPR || code == LT_EXPR)
+       && integer_zerop (rhs))
+    return true;
+
+  return false;
+}
+
+/* Returns true if xor is done in case the MSB/LSB is 1.
+   Otherwise, returns false.
+   In CRC calculation algorithms CRC is xor-ed with the polynomial only
+   if MSB/LSB is 1.
+
+   PRED_BB is the block containing the condition for the xor.
+   XOR_BB is the one of the successor blocks of PRED_BB, it is assumed that CRC
+   is xor-ed with the polynomial in XOR_BB.
+   COND is the condition, which is checked to satisfy the CRC condition.  */
+
+bool
+crc_optimization::is_crc_satisfiable_cond (basic_block pred_bb,
+					   basic_block xor_bb,
+					   gcond *cond)
+{
+  edge true_edge;
+  edge false_edge;
+  extract_true_false_edges_from_block (pred_bb, &true_edge, &false_edge);
+  bool cond_is_checked_for_bit_one = cond_true_is_checked_for_bit_one (cond);
+  /* Check that xor is done in case the MSB/LSB is 1.  */
+  if (cond_is_checked_for_bit_one && true_edge->dest == xor_bb)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Xor is done on true branch.\n");
+    }
+  else if (!cond_is_checked_for_bit_one && false_edge->dest == xor_bb)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Xor is done on false branch.\n");
+    }
+  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;
+    }
+  return true;
+}
+
+/* Checks that the variable used in the condition COND is the assumed CRC
+  (or depends on the assumed CRC).
+  Also sets data member m_phi_for_data if it isn't set and exists.  */
+
+bool
+crc_optimization::is_crc_checked (gcond *cond)
+{
+  tree lhs = gimple_cond_lhs (cond);
+
+  /* As conditions are in canonical form, only left part must be an
+    SSA_NAME.  */
+  if (TREE_CODE (lhs) == SSA_NAME)
+    {
+      /* Return whether there is a dependence between if condition's variable
+	 and xor-ed variable.  Also set phi statement of data if it is not
+	 determined earlier and is used in the loop.  */
+      auto_vec<gimple *> cond_dep_stmts (m_crc_loop->num_nodes);
+      bool set_defs_succeeded = set_defs (lhs, cond_dep_stmts, true);
+      bitmap_clear (m_visited_stmts);
+      if (!set_defs_succeeded)
+	return false;
+      return cond_depends_on_crc (cond_dep_stmts);
+    }
+
+  /* Return false if there is no dependence between if condition's variable
+     and xor-ed variable.  */
+  return false;
+}
+
+/* Checks that the condition is for checking CRC.
+   Returns true if xor is done under the condition of MSB/LSB being 1, and
+   the condition's variable and xor-ed variable depend on the same variable.
+   Otherwise, returns false.
+   XOR_BB is the basic block, where the 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 (basic_block pred_bb, basic_block xor_bb)
+{
+  /* Check whether PRED_BB contains condition.  We will consider only those
+     cases when xor is done immediately under the condition.  */
+  gcond *cond = safe_dyn_cast<gcond *> (gsi_stmt (gsi_last_bb (pred_bb)));
+  if (!cond)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "No condition.\n");
+      return false;
+    }
+
+  /* Check that xor is done in case the MSB/LSB is 1.  */
+  if (!is_crc_satisfiable_cond (pred_bb, xor_bb, cond))
+    return false;
+
+  /* Check that CRC's MSB/LSB is checked in the condition.
+     Set data member if not set and exists.  */
+  if (!is_crc_checked (cond))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "The condition is not related to the CRC check.\n");
+      return false;
+    }
+  return true;
+}
+
+/* Returns true if the statement with STMT_CODE may occur in CRC calculation.
+   Otherwise, returns false.  */
+
+bool
+crc_optimization::is_acceptable_stmt_code (const tree_code &stmt_code)
+{
+  return (stmt_code == BIT_IOR_EXPR)
+	 || (stmt_code == BIT_AND_EXPR)
+	 || (stmt_code == BIT_XOR_EXPR)
+	 || (stmt_code == MINUS_EXPR)
+	 || (stmt_code == PLUS_EXPR)
+	 || (stmt_code == RSHIFT_EXPR)
+	 || (stmt_code == LSHIFT_EXPR)
+	 || (TREE_CODE_CLASS (stmt_code) == tcc_unary);
+}
+
+/* Returns true if ASSIGN_STMT does shift with 1.  Otherwise, returns false.  */
+
+bool
+crc_optimization::can_be_crc_shift (gimple *assign_stmt)
+{
+  tree_code stmt_code = gimple_assign_rhs_code (assign_stmt);
+  if (stmt_code == LSHIFT_EXPR || stmt_code == RSHIFT_EXPR)
+    {
+      m_is_bit_forward = (stmt_code == LSHIFT_EXPR);
+      /* Check that shift one is done, keep shift statement.  */
+      if (integer_onep (gimple_assign_rhs2 (assign_stmt)))
+	{
+	  if (m_shift_stmt)
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file,
+			 "Already there is one shift.\n");
+	      return false;
+	    }
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "Found <<1 or >>1.\n");
+	  return true;
+	}
+      /* This filters out cases, when xor-ed variable is shifted by values
+	 other than 1.  */
+    }
+    return false;
+}
+
+/* Returns true if the operation done in ASSIGN_STMT can occur during CRC
+   calculation.  Otherwise, returns false.  */
+
+bool
+crc_optimization::can_not_be_crc_stmt (gimple *assign_stmt)
+{
+  tree_code stmt_code = gimple_assign_rhs_code (assign_stmt);
+  if (!is_acceptable_stmt_code (stmt_code))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "\nStmt with the following operation "
+		 "code %s between xor and shift, "
+		 "may not be CRC.\n", get_tree_code_name (stmt_code));
+
+      return true;
+    }
+  return false;
+}
+
+/* Returns true if we can get definition of the VARIABLE, and the definition
+   is not outside the loop.  Otherwise, returns false.  */
+
+bool
+crc_optimization::passes_checks_for_def_chain (tree variable)
+{
+  if (!(variable && TREE_CODE (variable) == SSA_NAME))
+    return false;
+
+  /* No definition chain for default defs.  */
+  if (SSA_NAME_IS_DEFAULT_DEF (variable))
+    return false;
+
+  gimple *stmt = SSA_NAME_DEF_STMT (variable);
+
+  if (!stmt)
+    return false;
+
+  /* Don't go outside the loop.  */
+  if (!flow_bb_inside_loop_p (m_crc_loop, gimple_bb (stmt)))
+    return false;
+
+  return true;
+}
+
+/* This function goes up through the def-use chains of the parameter NAME.
+   Gathers all the statements within the loop,
+   from which the variable depends on and adds to the USE_DEFS.
+   Returns false, if there is a statement that may not exist in the CRC
+   loop.  Otherwise, returns true.  */
+
+bool
+crc_optimization::set_defs (tree name, auto_vec<gimple *> &use_defs,
+			    bool keep_only_header_phis = false)
+{
+  if (!passes_checks_for_def_chain (name))
+    return true;
+
+  /* Don't consider already visited names.  */
+  unsigned v = SSA_NAME_VERSION (name);
+  if (bitmap_bit_p (m_visited_stmts, v))
+    return true;
+  bitmap_set_bit (m_visited_stmts, v);
+
+  /* In CRC implementations with constant polynomial maximum 12 use_def
+     statements may occur.  This limit is based on an analysis of various CRC
+     implementations as well as theoretical possibilities.
+     TODO: Find a better solution.  */
+  if (use_defs.length () > 12)
+    return false;
+
+  gimple *stmt = SSA_NAME_DEF_STMT (name);
+
+  /* If it's not specified to keep only header phi's,
+     then keep all statements.  */
+  if (!keep_only_header_phis)
+    use_defs.safe_push (stmt);
+
+  /* If it is an assignment statement,
+     get and check def-use chain for the first and second operands.  */
+  if (is_a<gassign *> (stmt))
+    {
+      if (can_not_be_crc_stmt (stmt))
+	return false;
+
+      tree ssa1 = gimple_assign_rhs1 (stmt);
+      tree ssa2 = gimple_assign_rhs2 (stmt);
+      if (!set_defs (ssa1, use_defs, keep_only_header_phis))
+	return false;
+      if (!set_defs (ssa2, use_defs, keep_only_header_phis))
+	return false;
+      return true;
+    }
+  /* If it's a phi statement, not declared in loop's header,
+     get and check def-use chain for its values.  For the one declared in loop's
+     header just return true and keep it, if keep_only_header_phis is true.  */
+  else if (is_a<gphi *> (stmt))
+    {
+      if (bb_loop_header_p (gimple_bb (stmt)))
+	{
+	  /* If it's specified to keep only header phi's, keep it.  */
+	  if (keep_only_header_phis)
+	    use_defs.safe_push (stmt);
+	}
+      else
+	{
+	  for (unsigned i = 0; i < gimple_phi_num_args (stmt); i++)
+	    {
+	      tree val = gimple_phi_arg_def (stmt, i);
+	      if (!set_defs (val, use_defs, keep_only_header_phis))
+		return false;
+	    }
+	}
+      return true;
+    }
+
+  /* Return false for other than assigment and phi statement.  */
+  return false;
+}
+
+/* Returns the statement which does shift 1 operation.
+   If there is no such statement, returns nullptr.
+   STMTS - are the statements within the loop before xor operation on
+   which possible CRC variable depends.  */
+
+gimple *
+crc_optimization::find_shift_before_xor (const auto_vec<gimple *> &stmts)
+{
+  for (auto stmt_it = stmts.begin (); stmt_it != stmts.end (); stmt_it++)
+    {
+      /* If it is an assignment statement, check that is does shift 1.  */
+      if (is_a<gassign *> (*stmt_it))
+	{
+	  if (can_be_crc_shift (*stmt_it))
+	    return *stmt_it;
+	}
+    }
+  return nullptr;
+}
+
+/* This function sets M_PHI_FOR_CRC and M_PHI_FOR_DATA fields.
+   At this step phi nodes for CRC and data may be mixed in places.
+   It is fixed later with the "swap_crc_and_data_if_needed" function.
+   The function returns false if there are more than two (as in CRC calculation
+   only CRC's and data's phi may exist) or no phi statements in STMTS (at least
+   there must be CRC's phi).
+   Otherwise, returns true.  */
+
+bool
+crc_optimization::set_crc_and_data_phi (auto_vec<gimple *> &stmts)
+{
+  for (auto stmt_it = stmts.begin (); stmt_it != stmts.end (); stmt_it++)
+    {
+      if (is_a<gphi *> (*stmt_it) && bb_loop_header_p (gimple_bb (*stmt_it)))
+	{
+	  if (!m_phi_for_crc)
+	    m_phi_for_crc = as_a<gphi *> (*stmt_it);
+	  else if (!m_phi_for_data)
+	    m_phi_for_data = as_a<gphi *> (*stmt_it);
+	  else
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "Xor-ed variable depends on more than 2 "
+				    "phis.\n");
+	      return false;
+	    }
+	}
+    }
+  return m_phi_for_crc;
+}
+
+/*  Returns true if the variable checked in the condition depends on possible
+    CRC value.  Otherwise, returns false.  */
+
+bool
+crc_optimization::cond_depends_on_crc (auto_vec<gimple *>& stmts)
+{
+  bool con_depends_on_crc = false;
+
+  /* The condition may depend maximum on data and CRC phi's.  */
+  if (stmts.length () > 2)
+    return false;
+
+  for (auto stmt_it = stmts.begin (); stmt_it != stmts.end (); stmt_it++)
+    {
+      if (is_a<gphi *> (*stmt_it) && bb_loop_header_p (gimple_bb (*stmt_it)))
+	{
+	  /* Check whether variable checked in the condition depends on
+	     M_PHI_FOR_CRC.
+	     Here don't stop the check, to set data if needed.  */
+	  if (m_phi_for_crc == (*stmt_it))
+	    con_depends_on_crc = true;
+	  else if (m_phi_for_data && m_phi_for_data == (*stmt_it))
+	    return true;
+	  /* If M_PHI_FOR_DATA isn't determined, the phi statement maybe for the
+	     data.  Just set it.  */
+	  else if (!m_phi_for_data)
+	    m_phi_for_data = as_a<gphi *> (*stmt_it);
+	}
+    }
+  return con_depends_on_crc;
+}
+
+/* Sets initial values for the CRC analysis.
+   This function is used multiple times during the analyses.  */
+
+void
+crc_optimization::set_initial_values ()
+{
+  m_shift_stmt = nullptr;
+  m_phi_for_crc = nullptr;
+  m_phi_for_data = nullptr;
+  m_is_bit_forward = false;
+}
+
+/* This function checks if the XOR_STMT is used for CRC calculation.
+   It verifies the presence of a shift operation in the CRC_FUN function inside
+   the CRC loop.  It examines operands of XOR, its dependencies, the relative
+   position of the shift operation, and the existence of a shift operation in
+   the opposite branch of conditional statements.  It also checks if XOR is
+   performed when MSB/LSB is one.
+   If these conditions are met, the XOR operation may be part of a CRC
+   calculation.  The function returns true if these conditions are fulfilled,
+   otherwise, it returns false.  */
+
+bool
+crc_optimization::xor_calculates_crc (function *crc_fun,
+				      const gimple *xor_stmt)
+{
+  tree crc_var = gimple_assign_lhs (xor_stmt);
+  set_initial_values ();
+  tree ssa1 = gimple_assign_rhs1 (xor_stmt);
+  tree ssa2 = gimple_assign_rhs2 (xor_stmt);
+  if (TREE_CODE (ssa2) != INTEGER_CST)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Second operand of the "
+			    "xor statement isn't an integer constant.\n");
+      return false;
+    }
+
+  /* Get the statements within the loop on which xor-ed variable depends.  */
+  auto_vec<gimple *> xor_dep_stmts (m_crc_loop->num_nodes);
+  bool set_defs_succeeded = set_defs (ssa1, xor_dep_stmts);
+  bitmap_clear (m_visited_stmts);
+  if (!set_defs_succeeded)
+    {
+      xor_dep_stmts.release ();
+      return false;
+    }
+
+  m_shift_stmt = find_shift_before_xor (xor_dep_stmts);
+
+  if (!set_crc_and_data_phi (xor_dep_stmts))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Xor isn't used for CRC calculation.\n");
+      return false;
+    }
+
+  /* Check the case when shift is done after xor.  */
+  if (!m_shift_stmt)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "No shift before xor, trying to find after xor.\n");
+
+      m_shift_stmt = find_shift_after_xor (crc_var);
+      bitmap_clear (m_visited_stmts);
+      if (!m_shift_stmt)
+	return false;
+    }
+
+  /* Get the basic block where xor operation is done.  */
+  basic_block xor_bb = gimple_bb (xor_stmt);
+
+  /* Get the predecessor basic block of xor's block.  */
+  if (!single_pred_p (xor_bb))
+    return false;
+  basic_block block_of_condition = single_pred (xor_bb);
+
+
+  /* If the found shift operation is in the same block as the xor operation,
+     verify whether another shift exists in the opposite branch of the
+     conditional statements.  */
+  if (m_shift_stmt && gimple_bb (m_shift_stmt) == xor_bb)
+    {
+      basic_block opposite_block = get_xor_bb_opposite (block_of_condition,
+							xor_bb);
+      if (!exists_shift_for_opp_xor_shift (opposite_block))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "Opposite block doesn't contain shift's pair.\n");
+	  return false;
+	}
+    }
+
+  /* Check that xor is done if MSB/LSB is one.
+     If all checks succeed, then it may be a CRC.  */
+  if (crc_cond (block_of_condition, xor_bb))
+    {
+      if (dump_file)
+	fprintf (dump_file,
+		 "\n%s function maybe contains CRC calculation.\n",
+		 function_name (crc_fun));
+      return true;
+    }
+
+  return false;
+}
+
+/* Returns true if there is only two conditional blocks in the loop,
+   one may be for the CRC bit check and the other for the loop counter.
+   This may filter out some real CRCs, where more than one condition
+   is checked for the CRC calculation and branch-less CRCs.  */
+
+bool
+crc_optimization::loop_contains_two_conditional_bb (basic_block *loop_bbs,
+						    unsigned loop_num_nodes)
+{
+  unsigned conditional_bb_count = 0;
+  /* Iterate through the loop until the conditional branches count
+     is below 3.  */
+  for (unsigned i = 0; i < loop_num_nodes && conditional_bb_count <= 2; i++)
+    {
+      basic_block bb = loop_bbs[i];
+      if (!single_succ_p (bb))
+	conditional_bb_count++;
+    }
+  return conditional_bb_count == 2;
+}
+
+/* Checks the FUNC_LOOP loop's iteration number.
+   The loop for CRC calculation may do 8, 16, 24, 32, 64 iterations.  */
+
+bool
+crc_optimization::satisfies_crc_loop_iteration_count (class loop *func_loop)
+{
+  /* Calculate the number of times the latch of the loop is executed.
+     The function sets NB_ITERATIONS field of the loop.  */
+  number_of_latch_executions (func_loop);
+  tree n_inters = func_loop->nb_iterations;
+  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");
+      return false;
+
+    }
+  else if (tree_fits_uhwi_p (n_inters))
+    {
+      unsigned HOST_WIDE_INT
+      loop_iteration_number = tree_to_uhwi (n_inters);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Loop iteration number is "
+		 HOST_WIDE_INT_PRINT_UNSIGNED ".\n", loop_iteration_number);
+
+      if ((loop_iteration_number == 7 || loop_iteration_number == 15
+	   || loop_iteration_number == 23 || loop_iteration_number == 31
+	   || loop_iteration_number == 63))
+	return true;
+    }
+  if (stderr && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Loop iteration number isn't a constant.\n");
+  return false;
+}
+
+/* This is the main function that checks whether the given LOOP
+   calculates CRC and extracts details of the CRC calculation.
+
+   The main idea is to find the innermost loop with 8, 16, 24, 32, 64
+   iterations and xor instruction (xor is the key operation for naive CRC
+   calculation). Then, checks that the variable is shifted by one before/after
+   being used in xor.
+   Xor must be done under the condition of MSB/LSB being 1.  */
+
+bool
+crc_optimization::loop_may_calculate_crc (class loop *loop)
+{
+  /* Only examine innermost loops.  */
+  if (!loop || loop->inner)
+    return false;
+
+  if (!satisfies_crc_loop_iteration_count (loop))
+    return false;
+
+  m_crc_loop = loop;
+  basic_block *loop_bbs = get_loop_body_in_dom_order (m_crc_loop);
+
+  /* Filter out the cases, which don't have exactly two conditions in the loop.
+     One for the CRC bit check, the other for the loop counter.  */
+  if (!loop_contains_two_conditional_bb (loop_bbs, m_crc_loop->num_nodes))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "The number of conditional "
+		 "branches in the loop isn't 2.\n");
+      return false;
+    }
+
+  unsigned short checked_xor_count = 0;
+  /* Walk bbs of the loop.  */
+  for (unsigned int i = 0; i < m_crc_loop->num_nodes; i++)
+    {
+      basic_block bb = loop_bbs[i];
+      /* Walk instructions of the bb.  */
+      for (gimple_stmt_iterator bsi = gsi_start_nondebug_bb (bb);
+	   !gsi_end_p (bsi); gsi_next_nondebug (&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 (cfun, stmt))
+		{
+		  dump_crc_information ();
+		  free (loop_bbs);
+		  return true;
+		}
+
+		if (++checked_xor_count == 2)
+		  return false;
+	    }
+	}
+    }
+  free (loop_bbs);
+  return false;
+}
+
+unsigned int
+crc_optimization::execute (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 0;
+
+  /* Get loops of the function.  */
+  auto loop_list = loops_list (fun, LI_ONLY_INNERMOST);
+  for (auto loop: loop_list)
+    {
+      /* Perform initial checks to filter out non-CRCs.  */
+      loop_may_calculate_crc (loop);
+    }
+  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_optimize_crc;
+      }
+
+      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 fc6abf6f582..66ba8773bab 100644
--- a/gcc/opts.cc
+++ b/gcc/opts.cc
@@ -666,6 +666,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_foptimize_crc, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_flate_combine_instructions, NULL, 1 },
 
     /* -O2 and above optimizations, but not -Os or -Og.  */
@@ -2097,6 +2098,7 @@ 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_optimize_crc, value);
 }
 
 /* -f{,no-}sanitize{,-recover}= suboptions.  */
diff --git a/gcc/passes.def b/gcc/passes.def
index 40162ac20a0..6c5dd46edc7 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -294,6 +294,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/timevar.def b/gcc/timevar.def
index 0f9d2c0b032..37460def292 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -313,6 +313,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 a928cbe4557..7c778f600b5 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -388,6 +388,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);
-- 
2.25.1

