---
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
@@ -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 \
@@ -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.
@@ -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)
@@ -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.
new file mode 100644
@@ -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);
+}
@@ -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. */
@@ -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);
@@ -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")
@@ -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
This patch adds a new compiler pass aimed at identifying naive CRC implementations, characterized by the presence of a loop calculating a CRC (polynomial long division). Upon detection of a potential CRC, the pass prints an informational message. Performs CRC optimization if optimization level is >= 2 and if fno_gimple_crc_optimization given. This pass is added for the detection and optimization of naive CRC implementations, improving the efficiency of CRC-related computations. This patch includes only initial fast checks for filtering out non-CRCs, detected possible CRCs verification and optimization parts will be provided in subsequent patches. gcc/ * Makefile.in (OBJS): Add gimple-crc-optimization.o. * common.opt (foptimize-crc): New option. * common.opt.urls: Regenerate to add foptimize-crc. * doc/invoke.texi (-foptimize-crc): Add documentation. * gimple-crc-optimization.cc: New file. * opts.cc (default_options_table): Add OPT_foptimize_crc. (enable_fdo_optimizations): Enable optimize_crc. * passes.def (pass_crc_optimization): Add new pass. * timevar.def (TV_GIMPLE_CRC_OPTIMIZATION): New timevar. * tree-pass.h (make_pass_crc_optimization): New extern function declaration. Signed-off-by: Mariam Arutunian <mariamarutunian@gmail.com> Mentored-by: Jeff Law <jlaw@ventanamicro.com>