GCC Middle and Back End API Reference
crc_optimization Class Reference
Collaboration diagram for crc_optimization:

Public Member Functions

 crc_optimization ()
 
 ~crc_optimization ()
 
unsigned int execute (function *fun)
 

Private Member Functions

void set_initial_values ()
 
bool loop_may_calculate_crc (class loop *loop)
 
bool loop_calculates_crc (gphi *output_crc, std::pair< tree, value * > calc_polynom)
 
bool satisfies_crc_loop_iteration_count (class loop *func_loop)
 
bool xor_calculates_crc (function *crc_fun, const gimple *xor_stmt)
 
bool passes_checks_for_def_chain (tree variable)
 
bool set_defs (tree name, auto_vec< gimple * > &use_defs, bool keep_only_header_phis)
 
bool set_crc_and_data_phi (auto_vec< gimple * > &stmts)
 
bool cond_depends_on_crc (auto_vec< gimple * > &stmts)
 
bool crc_cond (basic_block pred_bb, basic_block xor_bb)
 
bool is_crc_satisfiable_cond (basic_block pred_bb, basic_block xor_bb, gcond *cond)
 
bool is_crc_checked (gcond *cond)
 
bool exists_shift_for_opp_xor_shift (basic_block opposite_bb)
 
gimplefind_shift_after_xor (tree xored_crc)
 
gimplefind_shift_before_xor (const auto_vec< gimple * > &stmts)
 
bool can_be_crc_shift (gimple *assign_stmt)
 
bool can_not_be_crc_stmt (gimple *assign_stmt)
 
void dump_crc_information ()
 
bool is_output_crc (gphi *output_crc)
 
void swap_crc_and_data_if_needed (gphi *output_crc)
 
bool validate_crc_and_data ()
 
void construct_constant_polynomial (value *polynomial)
 
gphiget_output_phi ()
 
bool optimize_crc_loop (gphi *output_crc)
 

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
 
gimplem_shift_stmt
 
gphim_phi_for_crc
 
gphim_phi_for_data
 
class loopm_crc_loop
 
unsigned HOST_WIDE_INT m_polynomial
 
bool m_is_bit_forward
 

Detailed Description

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.   

Constructor & Destructor Documentation

◆ crc_optimization()

crc_optimization::crc_optimization ( )
inline

◆ ~crc_optimization()

crc_optimization::~crc_optimization ( )
inline

References BITMAP_FREE, and m_visited_stmts.

Member Function Documentation

◆ can_be_crc_shift()

bool crc_optimization::can_be_crc_shift ( gimple * assign_stmt)
private
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().

◆ can_not_be_crc_stmt()

bool crc_optimization::can_not_be_crc_stmt ( gimple * assign_stmt)
private
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().

◆ cond_depends_on_crc()

bool crc_optimization::cond_depends_on_crc ( auto_vec< gimple * > & stmts)
private
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().

◆ cond_true_is_checked_for_bit_one()

bool crc_optimization::cond_true_is_checked_for_bit_one ( const gcond * cond)
staticprivate
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().

◆ construct_constant_polynomial()

void crc_optimization::construct_constant_polynomial ( value * polynomial)
private
Convert polynomial to unsigned HOST_WIDE_INT.   

References as_a(), i, m_is_bit_forward, and m_polynomial.

Referenced by execute().

◆ crc_cond()

bool crc_optimization::crc_cond ( basic_block pred_bb,
basic_block xor_bb )
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().

◆ dump_crc_information()

void crc_optimization::dump_crc_information ( )
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().

◆ execute()

◆ exists_shift_for_opp_xor_shift()

bool crc_optimization::exists_shift_for_opp_xor_shift ( basic_block opposite_bb)
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().

◆ find_shift_after_xor()

gimple * crc_optimization::find_shift_after_xor ( tree xored_crc)
private
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().

◆ find_shift_before_xor()

gimple * crc_optimization::find_shift_before_xor ( const auto_vec< gimple * > & stmts)
private
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().

◆ get_output_phi()

gphi * crc_optimization::get_output_phi ( )
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().

◆ get_xor_bb_opposite()

basic_block crc_optimization::get_xor_bb_opposite ( basic_block pred_bb,
basic_block xor_bb )
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().

◆ is_acceptable_stmt_code()

bool crc_optimization::is_acceptable_stmt_code ( const tree_code & stmt_code)
staticprivate
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().

◆ is_crc_checked()

bool crc_optimization::is_crc_checked ( gcond * cond)
private
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().

◆ is_crc_satisfiable_cond()

bool crc_optimization::is_crc_satisfiable_cond ( basic_block pred_bb,
basic_block xor_bb,
gcond * 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().

◆ is_output_crc()

bool crc_optimization::is_output_crc ( gphi * output_crc)
private
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().

◆ loop_calculates_crc()

bool crc_optimization::loop_calculates_crc ( gphi * output_crc,
std::pair< tree, value * > calc_polynom )
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().

◆ loop_contains_two_conditional_bb()

bool crc_optimization::loop_contains_two_conditional_bb ( basic_block * loop_bbs,
unsigned loop_num_nodes )
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().

◆ loop_may_calculate_crc()

bool crc_optimization::loop_may_calculate_crc ( class loop * loop)
private
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().

◆ optimize_crc_loop()

bool crc_optimization::optimize_crc_loop ( gphi * output_crc)
private

◆ passes_checks_for_def_chain()

bool crc_optimization::passes_checks_for_def_chain ( tree variable)
private
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().

◆ satisfies_crc_loop_iteration_count()

bool crc_optimization::satisfies_crc_loop_iteration_count ( class loop * func_loop)
private
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().

◆ set_crc_and_data_phi()

bool crc_optimization::set_crc_and_data_phi ( auto_vec< gimple * > & stmts)
private
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().

◆ set_defs()

bool crc_optimization::set_defs ( tree name,
auto_vec< gimple * > & use_defs,
bool keep_only_header_phis = false )
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().

◆ set_initial_values()

void crc_optimization::set_initial_values ( )
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().

◆ swap_crc_and_data_if_needed()

void crc_optimization::swap_crc_and_data_if_needed ( gphi * output_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().

◆ validate_crc_and_data()

bool crc_optimization::validate_crc_and_data ( )
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().

◆ xor_calculates_crc()

bool crc_optimization::xor_calculates_crc ( function * crc_fun,
const gimple * xor_stmt )
private
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().

Field Documentation

◆ m_crc_arg

tree crc_optimization::m_crc_arg
private

◆ m_crc_loop

◆ m_data_arg

tree crc_optimization::m_data_arg
private

◆ m_is_bit_forward

◆ m_phi_for_crc

◆ m_phi_for_data

◆ m_polynomial

unsigned HOST_WIDE_INT crc_optimization::m_polynomial
private

◆ m_shift_stmt

gimple* crc_optimization::m_shift_stmt
private

◆ m_visited_stmts

bitmap crc_optimization::m_visited_stmts
private

The documentation for this class was generated from the following file: