diff options
author | Mariam Arutunian <mariamarutunian@gmail.com> | 2022-11-11 12:24:56 +0400 |
---|---|---|
committer | Jeff Law <jlaw@ventanamicro> | 2023-03-21 09:03:17 -0600 |
commit | 05690566c28fc9e97806f341e4f396b0dd38b8fd (patch) | |
tree | a45e76a7233fba27b03c2848fc2679f8d937871e /gcc | |
parent | 6aa1f40a3263741d964ef4716e85a0df5cec83b6 (diff) | |
download | gcc-05690566c28fc9e97806f341e4f396b0dd38b8fd.zip gcc-05690566c28fc9e97806f341e4f396b0dd38b8fd.tar.gz gcc-05690566c28fc9e97806f341e4f396b0dd38b8fd.tar.bz2 |
CRC detection v1: - Added pass_crc_optimization. Detects CRC-like functions. - Added tests to check the correctness of the pass.
Diffstat (limited to 'gcc')
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); |