#include <crc-verification.h>

Collaboration diagram for crc_symbolic_execution:

[legend]

Public Member Functions
std::pair< tree, value * >	extract_polynomial (gphi , gphi , tree, bool)

bool	symb_execute_crc_loop ()

const vec< state * > &	get_final_states ()

bool	is_last_iteration ()

	crc_symbolic_execution (class loop loop, gphi output_crc)

	~crc_symbolic_execution ()

Private Member Functions
bool	is_used_outside_the_loop (tree)

bool	add_next_bbs (basic_block, state *, auto_vec< edge > &)

bool	add_edge (edge, auto_vec< edge > &)

bool	resolve_condition (const gcond *, auto_vec< edge > &)

bool	add_final_state (state *)

bool	keep_states ()

bool	execute_assign_statement (const gassign *)

bool	execute_bb_gimple_statements (basic_block, auto_vec< edge > &)

bool	execute_bb_phi_statements (basic_block, edge)

bool	execute_bb_statements (basic_block, edge, auto_vec< edge > &)

state *	create_initial_state (class loop *)

bool	traverse_function (function *)

bool	execute_crc_loop (gphi , gphi , bool)

Static Private Member Functions
static bool	add_condition (const gcond , state , state *)

Private Attributes
vec< state * >	m_states

vec< state * >	m_final_states

class loop *	m_crc_loop

gphi *	m_output_crc

bool	m_is_last_iteration

Detailed Description

Execute symbolically all paths of the loop.
   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/>.

Constructor & Destructor Documentation

◆ crc_symbolic_execution()

crc_symbolic_execution::crc_symbolic_execution	(	class loop *	loop,
		gphi *	output_crc )

inline

References false, m_crc_loop, m_final_states, m_is_last_iteration, m_output_crc, and m_states.

◆ ~crc_symbolic_execution()

crc_symbolic_execution::~crc_symbolic_execution ( )

inline

References m_final_states, and m_states.

Member Function Documentation

◆ add_condition()

bool crc_symbolic_execution::add_condition	(	const gcond *	cond,
		state *	current_state,
		state *	new_branch_state )

staticprivate

Add conditions depending on symbolic variables in the states.

Keep conditions of each branch execution in its state.
  Ex.
    if (a == 0)  // a's value is unknown

    new_branch_state.keep (a==0)
    current_state.keep (a!=0)

  The condition is kept in the bit level.
  For ex.
  If a's size is 8 and its value is {symb_a, 0, 0, 0, 0, 0, 0, 0},
  then for a == 0 we'll have symb_a == 0 condition.

References dump_file, dump_flags, gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), and TDF_DETAILS.

Referenced by resolve_condition().

◆ add_edge()

bool crc_symbolic_execution::add_edge	(	edge	e,
		auto_vec< edge > &	stack )

private

Add E edge into the STACK if it doesn't have an immediate
successor edge going to the loop header.

When loop counter is checked in the if condition,
we mustn't continue on real path as we want to stop the execution before
the second iteration.

References dump_file, dump_flags, EDGE_COUNT, EDGE_SUCC, keep_states(), m_crc_loop, and TDF_DETAILS.

Referenced by add_next_bbs().

◆ add_final_state()

bool crc_symbolic_execution::add_final_state ( state * final_state )

private

If final states are less than two, add new FINAL_STATE and return true.
Otherwise, return false.
Supported CRC cases may not have more than two final states.

References dump_file, and m_final_states.

Referenced by keep_states().

◆ add_next_bbs()

bool crc_symbolic_execution::add_next_bbs	(	basic_block	cond_bb,
		state *	new_branch_state,
		auto_vec< edge > &	stack )

private

Add next basic blocks of the conditional block COND_BB
for the execution path into the STACK.
If the condition depends on symbolic values, keep both edges.
If the condition is true, keep true edge, else - false edge.
Returns true if addition succeeds.  Otherwise - false.

References add_edge(), dump_file, dump_flags, extract_true_false_edges_from_block(), m_states, and TDF_DETAILS.

Referenced by resolve_condition().

◆ create_initial_state()

state * crc_symbolic_execution::create_initial_state ( class loop * crc_loop )

private

Create initial state of the CRC_LOOP's header BB variables which have
constant values.
If it is the first iteration of the loop, initialise variables with the
initial values, otherwise initialise the variable with the value calculated
during the previous execution.

References assign_calc_vals_to_header_phis(), assign_known_vals_to_header_phis(), and m_final_states.

Referenced by symb_execute_crc_loop().

◆ execute_assign_statement()

bool crc_symbolic_execution::execute_assign_statement ( const gassign * gs )

private

Calculate value of the rhs operation of GS assigment statement
and assign it to lhs variable.

References dump_file, dump_flags, get_tree_code_name(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_num_ops(), is_used_outside_the_loop(), m_output_crc, m_states, TDF_DETAILS, and TREE_CODE.

Referenced by execute_bb_gimple_statements().

◆ execute_bb_gimple_statements()

bool crc_symbolic_execution::execute_bb_gimple_statements	(	basic_block	bb,
		auto_vec< edge > &	stack )

private

Execute gimple statements of BB.
Keeping values of variables in the state.

References as_a(), dump_file, dump_flags, execute_assign_statement(), FOR_EACH_EDGE, gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), m_crc_loop, print_gimple_stmt(), resolve_condition(), basic_block_def::succs, and TDF_DETAILS.

Referenced by execute_bb_statements(), execute_crc_loop(), and symb_execute_crc_loop().

◆ execute_bb_phi_statements()

bool crc_symbolic_execution::execute_bb_phi_statements	(	basic_block	bb,
		edge	incoming_edge )

private

Assign values of phi instruction to its result.
Keep updated values in the state.

References dump_file, dump_flags, gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), is_used_outside_the_loop(), m_output_crc, m_states, PHI_ARG_DEF_FROM_EDGE, print_gimple_stmt(), TDF_DETAILS, and virtual_operand_p().

Referenced by execute_bb_statements().

◆ execute_bb_statements()

bool crc_symbolic_execution::execute_bb_statements	(	basic_block	bb,
		edge	incoming_edge,
		auto_vec< edge > &	stack )

private

Execute all statements of BB.
Keeping values of variables in the state.

References execute_bb_gimple_statements(), and execute_bb_phi_statements().

Referenced by execute_crc_loop(), and symb_execute_crc_loop().

◆ execute_crc_loop()

bool crc_symbolic_execution::execute_crc_loop	(	gphi *	crc_phi,
		gphi *	data_phi,
		bool	is_shift_left )

private

Execute the loop, which calculates CRC with initial values,
to calculate the polynomial.

References assign_vals_to_header_phis(), dump_file, dump_flags, execute_bb_gimple_statements(), execute_bb_statements(), flow_bb_inside_loop_p(), m_crc_loop, m_final_states, m_states, and TDF_DETAILS.

Referenced by extract_polynomial().

◆ extract_polynomial()

std::pair< tree, value * > crc_symbolic_execution::extract_polynomial	(	gphi *	crc_phi,
		gphi *	data_phi,
		tree	calculated_crc,
		bool	is_shift_left )

Execute the loop, which is expected to calculate CRC,
to extract polynomial, assigning real numbers to CRC and data.
Returns a pair, first value of the pair is the tree containing
the value of the polynomial, second is the calculated polynomial.
The pair may contain nullptr.

References dump_file, dump_flags, execute_crc_loop(), m_final_states, polynomial_is_known(), print_generic_expr(), and TDF_DETAILS.

Referenced by crc_optimization::execute().

◆ get_final_states()

const vec< state * > & crc_symbolic_execution::get_final_states ( )

inline

References m_final_states.

Referenced by crc_optimization::loop_calculates_crc().

◆ is_last_iteration()

bool crc_symbolic_execution::is_last_iteration ( )

inline

References m_is_last_iteration.

Referenced by crc_optimization::loop_calculates_crc().

◆ is_used_outside_the_loop()

bool crc_symbolic_execution::is_used_outside_the_loop ( tree def )

private

Execute symbolically all paths of the loop.
   Calculate the value of the polynomial by executing loop with real values to
   create LFSR state.
   After each iteration check that final states of calculated CRC values match
   determined LFSR.
   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/>.

Check whether defined variable is used outside the loop, only
CRC's definition is allowed to be used outside the loop.

References as_a(), gimple::bb, dump_file, flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_STMT, is_a(), m_crc_loop, and m_output_crc.

Referenced by execute_assign_statement(), and execute_bb_phi_statements().

◆ keep_states()

bool crc_symbolic_execution::keep_states ( )

private

Keep the state of the executed path in final states.

References add_final_state(), dump_file, dump_flags, m_states, and TDF_DETAILS.

Referenced by add_edge(), and symb_execute_crc_loop().

◆ resolve_condition()

bool crc_symbolic_execution::resolve_condition	(	const gcond *	cond,
		auto_vec< edge > &	stack )

private

Create new states for true and false branches.
Keep conditions in new created states.

References add_condition(), add_next_bbs(), gimple::bb, and m_states.

Referenced by execute_bb_gimple_statements().

◆ symb_execute_crc_loop()

bool crc_symbolic_execution::symb_execute_crc_loop ( )

Symbolically execute the CRC loop, doing one iteration.

References create_initial_state(), dump_file, dump_flags, execute_bb_gimple_statements(), execute_bb_statements(), flow_bb_inside_loop_p(), keep_states(), m_crc_loop, m_is_last_iteration, m_states, and TDF_DETAILS.

Referenced by crc_optimization::loop_calculates_crc().

◆ traverse_function()

bool crc_symbolic_execution::traverse_function ( function * )

private

Traverse function fun's all paths from the first basic block to the last.
Each time iterate loops only once.
Symbolically execute statements of each path.

Field Documentation

◆ m_crc_loop

class loop* crc_symbolic_execution::m_crc_loop

private

Referenced by add_edge(), crc_symbolic_execution(), execute_bb_gimple_statements(), execute_crc_loop(), is_used_outside_the_loop(), and symb_execute_crc_loop().

◆ m_final_states

vec<state *> crc_symbolic_execution::m_final_states

private

Referenced by add_final_state(), crc_symbolic_execution(), create_initial_state(), execute_crc_loop(), extract_polynomial(), get_final_states(), and ~crc_symbolic_execution().

◆ m_is_last_iteration

bool crc_symbolic_execution::m_is_last_iteration

private

Referenced by crc_symbolic_execution(), is_last_iteration(), and symb_execute_crc_loop().

◆ m_output_crc

gphi* crc_symbolic_execution::m_output_crc

private

Referenced by crc_symbolic_execution(), execute_assign_statement(), execute_bb_phi_statements(), and is_used_outside_the_loop().

◆ m_states

vec<state *> crc_symbolic_execution::m_states

private

Referenced by add_next_bbs(), crc_symbolic_execution(), execute_assign_statement(), execute_bb_phi_statements(), execute_crc_loop(), keep_states(), resolve_condition(), symb_execute_crc_loop(), and ~crc_symbolic_execution().

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

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ crc_symbolic_execution()

◆ ~crc_symbolic_execution()

Member Function Documentation

◆ add_condition()

◆ add_edge()

◆ add_final_state()

◆ add_next_bbs()

◆ create_initial_state()

◆ execute_assign_statement()

◆ execute_bb_gimple_statements()

◆ execute_bb_phi_statements()

◆ execute_bb_statements()

◆ execute_crc_loop()

◆ extract_polynomial()

◆ get_final_states()

◆ is_last_iteration()

◆ is_used_outside_the_loop()

◆ keep_states()

◆ resolve_condition()

◆ symb_execute_crc_loop()

◆ traverse_function()

Field Documentation

◆ m_crc_loop

◆ m_final_states

◆ m_is_last_iteration

◆ m_output_crc

◆ m_states