GCC Middle and Back End API Reference
|
Public Member Functions | |
crc_optimization () | |
~crc_optimization () | |
unsigned int | execute (function *fun) |
Static Private Member Functions | |
static bool | loop_contains_two_conditional_bb (basic_block *loop_bbs, unsigned loop_num_nodes) |
static bool | cond_true_is_checked_for_bit_one (const gcond *cond) |
static basic_block | get_xor_bb_opposite (basic_block pred_bb, basic_block xor_bb) |
static bool | is_acceptable_stmt_code (const tree_code &stmt_code) |
Private Attributes | |
bitmap | m_visited_stmts |
tree | m_crc_arg |
tree | m_data_arg |
gimple * | m_shift_stmt |
gphi * | m_phi_for_crc |
gphi * | m_phi_for_data |
class loop * | m_crc_loop |
unsigned HOST_WIDE_INT | m_polynomial |
bool | m_is_bit_forward |
CRC optimization. Copyright (C) 2022-2025 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.
|
inline |
References BITMAP_ALLOC, m_crc_loop, m_polynomial, m_visited_stmts, NULL, and set_initial_values().
|
inline |
References BITMAP_FREE, and m_visited_stmts.
Returns true if ASSIGN_STMT does shift with 1. Otherwise, returns false.
References dump_file, dump_flags, gimple_assign_rhs2(), gimple_assign_rhs_code(), integer_onep(), m_is_bit_forward, m_shift_stmt, and TDF_DETAILS.
Referenced by find_shift_after_xor(), and find_shift_before_xor().
Returns true if the operation done in ASSIGN_STMT can occur during CRC calculation. Otherwise, returns false.
References dump_file, dump_flags, get_tree_code_name(), gimple_assign_rhs_code(), is_acceptable_stmt_code(), and TDF_DETAILS.
Referenced by set_defs().
Returns true if the variable checked in the condition depends on possible CRC value. Otherwise, returns false.
References as_a(), bb_loop_header_p(), gimple_bb(), is_a(), m_phi_for_crc, and m_phi_for_data.
Referenced by is_crc_checked().
Returns true if condition COND checks MSB/LSB bit is 1. Otherwise, return false.
References gimple_cond_code(), gimple_cond_rhs(), integer_onep(), and integer_zerop().
Referenced by is_crc_satisfiable_cond().
|
private |
Convert polynomial to unsigned HOST_WIDE_INT.
References as_a(), i, m_is_bit_forward, and m_polynomial.
Referenced by execute().
|
private |
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.
References dump_file, dump_flags, gsi_last_bb(), gsi_stmt(), is_crc_checked(), is_crc_satisfiable_cond(), safe_dyn_cast(), and TDF_DETAILS.
Referenced by xor_calculates_crc().
|
private |
Prints extracted details of CRC calculation.
References dump_file, HOST_WIDE_INT_PRINT_UNSIGNED, m_crc_loop, m_is_bit_forward, and tree_to_uhwi().
Referenced by loop_may_calculate_crc().
unsigned int crc_optimization::execute | ( | function * | fun | ) |
References construct_constant_polynomial(), dump_file, dump_flags, crc_symbolic_execution::extract_polynomial(), function_name(), get_output_phi(), is_output_crc(), LI_ONLY_INNERMOST, loop_calculates_crc(), loop_latch_edge(), loop_may_calculate_crc(), m_crc_loop, m_is_bit_forward, m_phi_for_crc, m_phi_for_data, number_of_loops(), optimize_crc_loop(), PHI_ARG_DEF_FROM_EDGE, swap_crc_and_data_if_needed(), TDF_DETAILS, and validate_crc_and_data().
|
private |
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.
References gimple_assign_rhs2(), gimple_assign_rhs_code(), gsi_end_p(), gsi_next_nondebug(), gsi_start_nondebug_bb(), gsi_stmt(), integer_onep(), is_gimple_assign(), and m_shift_stmt.
Referenced by xor_calculates_crc().
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.
References bb_loop_header_p(), bitmap_bit_p, bitmap_set_bit, can_be_crc_shift(), find_shift_after_xor(), flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_FAST, gcc_assert, gimple_bb(), gimple_phi_result(), is_gimple_assign(), is_gimple_debug(), m_crc_loop, m_visited_stmts, SSA_NAME_VERSION, TREE_CODE, and USE_STMT.
Referenced by find_shift_after_xor(), and xor_calculates_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.
References can_be_crc_shift(), and is_a().
Referenced by xor_calculates_crc().
|
private |
Returns phi statement which may hold the calculated CRC.
References dump_file, dump_flags, gimple_phi_num_args(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), m_crc_loop, single_exit(), TDF_DETAILS, and virtual_operand_p().
Referenced by execute().
|
staticprivate |
Returns opposite block of the XOR_BB from PRED_BB's dest blocks.
References EDGE_COMPLEX, EDGE_COUNT, EDGE_SUCC, gcc_assert, and basic_block_def::succs.
Referenced by xor_calculates_crc().
Returns true if the statement with STMT_CODE may occur in CRC calculation. Otherwise, returns false.
References tcc_unary, and TREE_CODE_CLASS.
Referenced by can_not_be_crc_stmt().
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.
References bitmap_clear(), cond_depends_on_crc(), gimple_cond_lhs(), m_crc_loop, m_visited_stmts, set_defs(), and TREE_CODE.
Referenced by crc_cond().
|
private |
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.
References cond_true_is_checked_for_bit_one(), dump_file, dump_flags, extract_true_false_edges_from_block(), and TDF_DETAILS.
Referenced by crc_cond().
Returns true if OUTPUT_CRC's result is the input of M_PHI_FOR_CRC. Otherwise, returns false.
References dump_file, dump_flags, loop_latch_edge(), m_crc_loop, m_phi_for_crc, PHI_ARG_DEF_FROM_EDGE, print_gimple_expr(), single_exit(), and TDF_DETAILS.
Referenced by execute().
|
private |
Symbolically executes the loop and checks that LFSR and resulting states match. Returns true if it is verified that the loop calculates CRC. Otherwise, return false. OUTPUT_CRC is the phi statement which will hold the calculated CRC value after the loop exit.
References all_states_match_lfsr(), dump_file, dump_flags, crc_symbolic_execution::get_final_states(), crc_symbolic_execution::is_last_iteration(), m_crc_loop, m_is_bit_forward, PHI_ARG_DEF_FROM_EDGE, single_exit(), crc_symbolic_execution::symb_execute_crc_loop(), and TDF_DETAILS.
Referenced by execute().
|
staticprivate |
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.
References i, and single_succ_p().
Referenced by loop_may_calculate_crc().
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.
References cfun, dump_crc_information(), dump_file, dump_flags, free(), get_loop_body_in_dom_order(), gimple_assign_rhs_code(), gsi_end_p(), gsi_next_nondebug(), gsi_start_nondebug_bb(), gsi_stmt(), i, loop::inner, is_gimple_assign(), loop_contains_two_conditional_bb(), m_crc_loop, satisfies_crc_loop_iteration_count(), TDF_DETAILS, and xor_calculates_crc().
Referenced by execute().
Attempts to optimize a CRC calculation loop by replacing it with a call to an internal function (IFN_CRC or IFN_CRC_REV). Returns true if replacement succeeded, otherwise false.
References gimple::bb, build_int_cstu(), build_nonstandard_integer_type(), dump_file, dump_flags, EXPR_LOCATION, gcc_assert, get_loop_exit_condition(), gimple_build_call_internal(), gimple_call_set_lhs(), gimple_cond_make_false(), gimple_phi_result(), gimple_set_location(), gsi_for_stmt(), gsi_insert_before(), GSI_SAME_STMT, gsi_start_bb(), m_crc_arg, m_crc_loop, m_data_arg, m_is_bit_forward, m_polynomial, remove_phi_node(), si, TDF_DETAILS, tree_to_uhwi(), TREE_TYPE, and update_stmt().
Referenced by execute().
Returns true if we can get definition of the VARIABLE, and the definition is not outside the loop. Otherwise, returns false.
References flow_bb_inside_loop_p(), gimple_bb(), m_crc_loop, SSA_NAME_DEF_STMT, SSA_NAME_IS_DEFAULT_DEF, and TREE_CODE.
Referenced by set_defs().
Checks the FUNC_LOOP loop's iteration number. The loop for CRC calculation may do 8, 16, 24, 32, 64 iterations.
References chrec_dont_know, dump_file, dump_flags, HOST_WIDE_INT_PRINT_UNSIGNED, loop::nb_iterations, NULL_TREE, number_of_latch_executions(), TDF_DETAILS, tree_fits_uhwi_p(), and tree_to_uhwi().
Referenced by loop_may_calculate_crc().
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.
References as_a(), bb_loop_header_p(), dump_file, dump_flags, gimple_bb(), is_a(), m_phi_for_crc, m_phi_for_data, and TDF_DETAILS.
Referenced by xor_calculates_crc().
|
private |
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.
References bb_loop_header_p(), bitmap_bit_p, bitmap_set_bit, can_not_be_crc_stmt(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_bb(), gimple_phi_arg_def(), gimple_phi_num_args(), i, is_a(), m_visited_stmts, passes_checks_for_def_chain(), set_defs(), SSA_NAME_DEF_STMT, and SSA_NAME_VERSION.
Referenced by is_crc_checked(), set_defs(), and xor_calculates_crc().
|
private |
Sets initial values for the CRC analysis. This function is used multiple times during the analyses.
References m_crc_arg, m_data_arg, m_is_bit_forward, m_phi_for_crc, m_phi_for_data, and m_shift_stmt.
Referenced by crc_optimization(), and xor_calculates_crc().
|
private |
Swaps M_PHI_FOR_CRC and M_PHI_FOR_DATA if they are mixed.
References loop_latch_edge(), m_crc_loop, m_phi_for_crc, m_phi_for_data, PHI_ARG_DEF_FROM_EDGE, and single_exit().
Referenced by execute().
|
private |
Validates CRC and data arguments and sets them for potential CRC loop replacement. The function extracts the CRC and data arguments from PHI nodes and performs several checks to ensure that the CRC and data are suitable for replacing the CRC loop with a more efficient implementation. Returns true if the arguments are valid and the loop replacement is possible, false otherwise.
References dump_file, dump_flags, gcc_assert, loop_preheader_edge(), m_crc_arg, m_crc_loop, m_data_arg, m_phi_for_crc, m_phi_for_data, PHI_ARG_DEF_FROM_EDGE, TDF_DETAILS, tree_to_uhwi(), TREE_TYPE, and TYPE_PRECISION.
Referenced by execute().
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.
References bitmap_clear(), crc_cond(), dump_file, dump_flags, exists_shift_for_opp_xor_shift(), find_shift_after_xor(), find_shift_before_xor(), function_name(), get_xor_bb_opposite(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_bb(), m_crc_loop, m_shift_stmt, m_visited_stmts, set_crc_and_data_phi(), set_defs(), set_initial_values(), single_pred(), single_pred_p(), TDF_DETAILS, and TREE_CODE.
Referenced by loop_may_calculate_crc().
|
private |
Referenced by optimize_crc_loop(), set_initial_values(), and validate_crc_and_data().
|
private |
Referenced by crc_optimization(), dump_crc_information(), execute(), find_shift_after_xor(), get_output_phi(), is_crc_checked(), is_output_crc(), loop_calculates_crc(), loop_may_calculate_crc(), optimize_crc_loop(), passes_checks_for_def_chain(), swap_crc_and_data_if_needed(), validate_crc_and_data(), and xor_calculates_crc().
|
private |
Referenced by optimize_crc_loop(), set_initial_values(), and validate_crc_and_data().
|
private |
|
private |
|
private |
|
private |
Referenced by construct_constant_polynomial(), crc_optimization(), and optimize_crc_loop().
|
private |
Referenced by can_be_crc_shift(), exists_shift_for_opp_xor_shift(), set_initial_values(), and xor_calculates_crc().
|
private |
Referenced by crc_optimization(), find_shift_after_xor(), is_crc_checked(), set_defs(), xor_calculates_crc(), and ~crc_optimization().