Collaboration diagram for pcom_worker:

Public Member Functions
	pcom_worker (loop_p l)

	~pcom_worker ()

	pcom_worker (const pcom_worker &)=delete

pcom_worker &	operator= (const pcom_worker &)=delete

unsigned	tree_predictive_commoning_loop (bool allow_unroll_p)

void	execute_pred_commoning (bitmap tmp_vars)

Private Types
typedef hash_map< tree, name_expansion * >	tree_expand_map_t

Private Member Functions
struct component *	split_data_refs_to_components ()

struct component *	filter_suitable_components (struct component *comps)

void	determine_roots (struct component *comps)

void	prepare_initializers ()

bool	prepare_finalizers ()

void	try_combine_chains ()

void	release_chains ()

void	release_chain (chain_p chain)

bool	prepare_initializers_chain (chain_p chain)

bool	prepare_finalizers_chain (chain_p chain)

void	aff_combination_dr_offset (struct data_reference dr, aff_tree offset)

bool	determine_offset (struct data_reference a, struct data_reference b, poly_widest_int *off)

bool	suitable_component_p (struct component *comp)

bool	valid_initializer_p (struct data_reference ref, unsigned distance, struct data_reference root)

gphi *	find_looparound_phi (dref ref, dref root)

void	determine_roots_comp (struct component *comp)

void	add_looparound_copies (chain_p chain)

gimple *	single_nonlooparound_use (tree name)

void	remove_stmt (gimple *stmt)

void	execute_pred_commoning_chain (chain_p chain, bitmap tmp_vars)

gimple *	find_use_stmt (tree *name)

gimple *	find_associative_operation_root (gimple stmt, unsigned distance)

gimple *	find_common_use_stmt (tree name1, tree name2)

bool	combinable_refs_p (dref r1, dref r2, enum tree_code code, bool swap, tree *rslt_type)

gimple *	reassociate_to_the_same_stmt (tree name1, tree name2)

gimple *	stmt_combining_refs (dref r1, dref r2)

chain_p	combine_chains (chain_p ch1, chain_p ch2)

Private Attributes
loop_p	m_loop

auto_vec< data_reference_p, 10 >	m_datarefs

auto_vec< ddr_p, 10 >	m_dependences

auto_vec< chain_p >	m_chains

auto_bitmap	m_looparound_phis

tree_expand_map_t *	m_cache

Detailed Description

A class to encapsulate the global states used for predictive
commoning work on top of one given LOOP.

Member Typedef Documentation

◆ tree_expand_map_t

typedef hash_map<tree, name_expansion *> pcom_worker::tree_expand_map_t

private

Constructor & Destructor Documentation

◆ pcom_worker() [1/2]

pcom_worker::pcom_worker ( loop_p l )

inline

◆ ~pcom_worker()

pcom_worker::~pcom_worker ( )

inline

References free_affine_expand_cache(), free_data_refs(), free_dependence_relations(), m_cache, m_datarefs, m_dependences, and release_chains().

◆ pcom_worker() [2/2]

pcom_worker::pcom_worker ( const pcom_worker & )

delete

Member Function Documentation

◆ add_looparound_copies()

void pcom_worker::add_looparound_copies ( chain_p chain )

private

For references in CHAIN that are copied around the loop (created previously
by PRE, or by user), add the results of such copies to the chain.  This
enables us to remove the copies by unrolling, and may need less registers
(also, it may allow us to combine chains together).

References bitmap_set_bit, CT_STORE_STORE, find_looparound_phi(), FOR_EACH_VEC_ELT, get_chain_root(), i, insert_looparound_copy(), m_looparound_phis, PHI_RESULT, chain::refs, SSA_NAME_VERSION, and chain::type.

Referenced by determine_roots_comp().

◆ aff_combination_dr_offset()

void pcom_worker::aff_combination_dr_offset	(	struct data_reference *	dr,
		aff_tree *	offset )

private

Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET.

References aff_combination_add(), aff_combination_const(), DR_INIT, DR_OFFSET, m_cache, offset, wi::to_poly_widest(), tree_to_aff_combination_expand(), and TREE_TYPE.

Referenced by determine_offset(), and valid_initializer_p().

◆ combinable_refs_p()

bool pcom_worker::combinable_refs_p	(	dref	r1,
		dref	r2,
		enum tree_code *	code,
		bool *	swap,
		tree *	rslt_type )

private

Checks whether R1 and R2 are combined together using CODE, with the result
in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
if it is true.  If CODE is ERROR_MARK, set these values instead.

References commutative_tree_code(), find_common_use_stmt(), gcc_assert, ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs_code(), gimple_bb(), name_for_ref(), NULL_TREE, and TREE_TYPE.

Referenced by combine_chains().

◆ combine_chains()

chain_p pcom_worker::combine_chains	(	chain_p	ch1,
		chain_p	ch2 )

private

Tries to combine chains CH1 and CH2 together.  If this succeeds, the
description of the new chain is returned, otherwise we return NULL.

References combinable_refs_p(), chain::combined, ggc_alloc(), i, chain::length, NULL, NULL_TREE, and chain::refs.

Referenced by try_combine_chains().

◆ determine_offset()

bool pcom_worker::determine_offset	(	struct data_reference *	a,
		struct data_reference *	b,
		poly_widest_int *	off )

private

Determines number of iterations of the innermost enclosing loop before B
refers to exactly the same location as A and stores it to OFF.  If A and
B do not have the same step, they never meet, or anything else fails,
returns false, otherwise returns true.  Both A and B are assumed to
satisfy suitable_reference_p.

References a, aff_combination_add(), aff_combination_constant_multiple_p(), aff_combination_dr_offset(), aff_combination_scale(), b, DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_REF, DR_STEP, ggc_alloc(), integer_zerop(), m_cache, operand_equal_p(), tree_to_aff_combination_expand(), TREE_TYPE, and useless_type_conversion_p().

Referenced by split_data_refs_to_components(), and suitable_component_p().

◆ determine_roots()

void pcom_worker::determine_roots ( struct component * comps )

private

Find roots of the values and determine distances in components COMPS, and
separates the references to chains.

References comp, determine_roots_comp(), and ggc_alloc().

Referenced by tree_predictive_commoning_loop().

◆ determine_roots_comp()

void pcom_worker::determine_roots_comp ( struct component * comp )

private

Find roots of the values and determine distances in the component COMP.
The references are redistributed into chains.

References a, add_looparound_copies(), add_ref_to_chain(), comp, CT_LOAD, CT_STORE_LOAD, DR_IS_READ, DR_IS_WRITE, FOR_EACH_VEC_ELT, free(), ggc_alloc(), i, wi::leu_p(), m_chains, make_invariant_chain(), make_rooted_chain(), MAX_DISTANCE, nontrivial_chain_p(), NULL, order_drefs(), release_chain(), RS_INVARIANT, type(), and chain::type.

Referenced by determine_roots().

◆ execute_pred_commoning()

void pcom_worker::execute_pred_commoning ( bitmap tmp_vars )

Perform the predictive commoning optimization for chains.
Uids of the newly created temporary variables are marked in TMP_VARS.

References a, chain::combined, CT_INVARIANT, execute_load_motion(), execute_pred_commoning_chain(), FOR_EACH_VEC_ELT, ggc_alloc(), i, m_chains, m_loop, chain::refs, remove_stmt(), and chain::type.

Referenced by execute_pred_commoning_cbck(), and tree_predictive_commoning_loop().

◆ execute_pred_commoning_chain()

void pcom_worker::execute_pred_commoning_chain	(	chain_p	chain,
		bitmap	tmp_vars )

private

Perform the predictive commoning optimization for a chain CHAIN.
Uids of the newly created temporary variables are marked in TMP_VARS.

References a, b, chain::combined, CT_COMBINATION, CT_STORE_LOAD, CT_STORE_STORE, DR_IS_WRITE, finalize_eliminated_stores(), gcc_assert, get_chain_last_write_before_load(), get_chain_root(), ggc_alloc(), gimple_assign_rhs1(), i, initialize_root_vars(), initialize_root_vars_store_elim_1(), initialize_root_vars_store_elim_2(), chain::inv_store_elimination, chain::length, m_loop, NULL, chain::refs, remove_stmt(), replace_ref_with(), chain::type, and chain::vars.

Referenced by execute_pred_commoning().

◆ filter_suitable_components()

struct component * pcom_worker::filter_suitable_components ( struct component * comps )

private

Check the conditions on references inside each of components COMPS,
and remove the unsuitable components from the list.  The new list
of components is returned.  The conditions are described in 2) at
the beginning of this file.

References comp, FOR_EACH_VEC_ELT, free(), ggc_alloc(), i, and suitable_component_p().

Referenced by tree_predictive_commoning_loop().

◆ find_associative_operation_root()

gimple * pcom_worker::find_associative_operation_root	(	gimple *	stmt,
		unsigned *	distance )

private

If the operation used in STMT is associative and commutative, go through the
tree of the same operations and returns its root.  Distance to the root
is stored in DISTANCE.

References find_use_stmt(), gcc_assert, ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs_code(), may_reassociate_p(), NULL, TREE_CODE, and TREE_TYPE.

Referenced by find_common_use_stmt(), and reassociate_to_the_same_stmt().

◆ find_common_use_stmt()

gimple * pcom_worker::find_common_use_stmt	(	tree *	name1,
		tree *	name2 )

private

Returns the common statement in that NAME1 and NAME2 have a use.  If there
is no such statement, returns NULL_TREE.  In case the operation used on
NAME1 and NAME2 is associative and commutative, returns the root of the
tree formed by this operation instead of the statement that uses NAME1 or
NAME2.

References find_associative_operation_root(), find_use_stmt(), ggc_alloc(), and NULL.

Referenced by combinable_refs_p().

◆ find_looparound_phi()

gphi * pcom_worker::find_looparound_phi	(	dref	ref,
		dref	root )

private

Finds looparound phi node of loop that copies the value of REF, and if its
initial value is correct (equal to initial value of REF shifted by one
iteration), returns the phi node.  Otherwise, NULL_TREE is returned.  ROOT
is the root of the current chain.

References ao_ref_init(), DECL_P, dr_analyze_innermost(), DR_INNERMOST, DR_IS_READ, DR_REF, DR_STMT, gcc_assert, ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_phi_result(), gimple_vuse(), gsi_end_p(), gsi_next(), gsi_start_phis(), is_gimple_assign(), loop_latch_edge(), loop_preheader_edge(), m_loop, NULL, NULL_TREE, PHI_ARG_DEF_FROM_EDGE, PHI_RESULT, REFERENCE_CLASS_P, SSA_NAME_DEF_STMT, stmt_may_clobber_ref_p_1(), TREE_CODE, valid_initializer_p(), and virtual_operand_p().

Referenced by add_looparound_copies().

◆ find_use_stmt()

gimple * pcom_worker::find_use_stmt ( tree * name )

private

Returns the modify statement that uses NAME.  Skips over assignment
statements, NAME is replaced with the actual name used in the returned
statement.

References get_gimple_rhs_class(), ggc_alloc(), gimple_assign_copy_p(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs_code(), GIMPLE_BINARY_RHS, NULL, single_nonlooparound_use(), and TREE_CODE.

Referenced by find_associative_operation_root(), find_common_use_stmt(), reassociate_to_the_same_stmt(), and stmt_combining_refs().

◆ operator=()

pcom_worker & pcom_worker::operator= ( const pcom_worker & )

delete

◆ prepare_finalizers()

bool pcom_worker::prepare_finalizers ( )

private

Generates finalizer memory reference for chains.  Returns true if
finalizer code generation for chains breaks loop closed ssa form.

References CT_STORE_STORE, ggc_alloc(), i, chain::length, m_chains, prepare_finalizers_chain(), release_chain(), and chain::type.

Referenced by tree_predictive_commoning_loop().

◆ prepare_finalizers_chain()

bool pcom_worker::prepare_finalizers_chain ( chain_p chain )

private

Generates finalizer memory references for CHAIN.  Returns true
if finalizer code for CHAIN can be generated, otherwise false.

References chain::all_always_accessed, chain::fini_seq, chain::finis, force_gimple_operand(), gcc_assert, get_chain_root(), ggc_alloc(), gimple_seq_add_seq_without_update(), i, chain::length, m_loop, NULL, NULL_TREE, number_of_latch_executions(), data_reference::ref, ref_at_iteration(), TREE_CODE, and unshare_expr().

Referenced by prepare_finalizers().

◆ prepare_initializers()

void pcom_worker::prepare_initializers ( )

private

Prepare initializers for chains, and free chains that cannot
be used because the initializers might trap.

References i, m_chains, prepare_initializers_chain(), and release_chain().

Referenced by tree_predictive_commoning_loop().

◆ prepare_initializers_chain()

bool pcom_worker::prepare_initializers_chain ( chain_p chain )

private

Prepare initializers for CHAIN.  Returns false if this is impossible
because one of these initializers may trap, true otherwise.

References chain::all_always_accessed, CT_INVARIANT, CT_STORE_STORE, FOR_EACH_VEC_ELT, gcc_assert, get_chain_root(), ggc_alloc(), gimple_seq_add_seq_without_update(), gimple_seq_discard(), i, chain::init_seq, chain::inits, chain::length, loop_preheader_edge(), m_loop, NULL, NULL_TREE, PHI_ARG_DEF_FROM_EDGE, prepare_initializers_chain_store_elim(), data_reference::ref, ref_at_iteration(), chain::refs, tree_could_trap_p(), and chain::type.

Referenced by prepare_initializers().

◆ reassociate_to_the_same_stmt()

gimple * pcom_worker::reassociate_to_the_same_stmt	(	tree	name1,
		tree	name2 )

private

Reassociates the expression in that NAME1 and NAME2 are used so that they
are combined in a single statement, and returns this statement.

References create_tmp_reg(), find_associative_operation_root(), find_use_stmt(), gcc_assert, ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_assign_set_rhs_with_ops(), gimple_build_assign(), gsi_for_stmt(), gsi_insert_before(), GSI_SAME_STMT, gsi_stmt(), make_ssa_name(), remove_name_from_operation(), TREE_TYPE, and update_stmt().

Referenced by stmt_combining_refs().

◆ release_chain()

void pcom_worker::release_chain ( chain_p chain )

private

Frees a chain CHAIN.

References chain::fini_seq, FOR_EACH_VEC_ELT, free(), gimple_seq_discard(), i, chain::init_seq, NULL, and chain::refs.

Referenced by determine_roots_comp(), prepare_finalizers(), prepare_initializers(), and release_chains().

◆ release_chains()

void pcom_worker::release_chains ( )

private

Frees CHAINS.

References FOR_EACH_VEC_ELT, i, m_chains, and release_chain().

Referenced by ~pcom_worker().

◆ remove_stmt()

void pcom_worker::remove_stmt ( gimple * stmt )

private

Remove statement STMT, as well as the chain of assignments in that it is
used.

References gcc_assert, ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_ssa_name_copy_p(), gimple_vdef(), gsi_for_stmt(), gsi_remove(), NULL, PHI_RESULT, release_defs(), remove_phi_node(), reset_debug_uses(), single_nonlooparound_use(), TREE_CODE, and unlink_stmt_vdef().

Referenced by execute_pred_commoning(), and execute_pred_commoning_chain().

◆ single_nonlooparound_use()

gimple * pcom_worker::single_nonlooparound_use ( tree name )

private

Returns the single statement in that NAME is used, excepting
the looparound phi nodes contained in one of the chains.  If there is no
such statement, or more statements, NULL is returned.

References bitmap_bit_p, FOR_EACH_IMM_USE_FAST, ggc_alloc(), is_gimple_debug(), m_looparound_phis, NULL, PHI_RESULT, SSA_NAME_VERSION, and USE_STMT.

Referenced by find_use_stmt(), and remove_stmt().

◆ split_data_refs_to_components()

struct component * pcom_worker::split_data_refs_to_components ( )

private

Splits dependence graph on DATAREFS described by DEPENDENCES to
components.

References data_reference::aux, bitmap_set_bit, CDI_DOMINATORS, chrec_dont_know, chrec_known, comp, component_of(), DDR_A, DDR_ARE_DEPENDENT, DDR_B, DDR_NUM_DIST_VECTS, determine_offset(), dominated_by_p(), DR_IS_READ, DR_IS_WRITE, DR_REF, DR_STMT, EXECUTE_IF_SET_IN_BITMAP, FOR_EACH_VEC_ELT, ggc_alloc(), gimple_bb(), i, is_gimple_call(), last_always_executed_block(), m_datarefs, m_dependences, m_loop, merge_comps(), NULL, NULL_TREE, number_of_latch_executions(), single_exit(), and suitable_reference_p().

Referenced by tree_predictive_commoning_loop().

◆ stmt_combining_refs()

gimple * pcom_worker::stmt_combining_refs	(	dref	r1,
		dref	r2 )

private

Returns the statement that combines references R1 and R2.  In case R1
and R2 are not used in the same statement, but they are used with an
associative and commutative operation in the same expression, reassociate
the expression so that they are used in the same statement.

References find_use_stmt(), ggc_alloc(), name_for_ref(), and reassociate_to_the_same_stmt().

◆ suitable_component_p()

bool pcom_worker::suitable_component_p ( struct component * comp )

private

Returns true if the component COMP satisfies the conditions
described in 2) at the beginning of this file.

References a, CDI_DOMINATORS, comp, DECL_BIT_FIELD, determine_offset(), dominated_by_p(), DR_IS_WRITE, DR_REF, DR_STEP, FOR_EACH_VEC_ELT, gcc_assert, gcc_checking_assert, ggc_alloc(), gimple_bb(), i, just_once_each_iteration_p(), m_loop, wi::multiple_of_p(), offset, RS_ANY, RS_NONZERO, SIGNED, suitable_reference_p(), wi::to_offset(), TREE_CODE, TREE_OPERAND, TREE_TYPE, and TYPE_SIZE_UNIT.

Referenced by filter_suitable_components().

◆ tree_predictive_commoning_loop()

unsigned pcom_worker::tree_predictive_commoning_loop ( bool allow_unroll_p )

Performs predictive commoning for LOOP.  Sets bit 1<<1 of return value
if LOOP was unrolled; Sets bit 1<<2 of return value if loop closed ssa
form was corrupted.  Non-zero return value indicates some changes were
applied to this loop.

References can_unroll_loop_p(), compute_data_dependences_for_loop(), determine_roots(), determine_unroll_factor(), dump_chains(), dump_components(), dump_data_dependence_relations(), dump_file, dump_flags, eliminate_temp_copies(), execute_pred_commoning(), execute_pred_commoning_cbck(), filter_suitable_components(), get_max_loop_iterations_int(), ggc_alloc(), insert_init_seqs(), m_chains, m_datarefs, m_dependences, m_loop, prepare_finalizers(), prepare_initializers(), release_components(), replace_phis_by_defined_names(), split_data_refs_to_components(), TDF_DETAILS, tree_transform_and_unroll_loop(), and try_combine_chains().

◆ try_combine_chains()

void pcom_worker::try_combine_chains ( )

private

Try to combine the chains.

References chain_can_be_combined_p(), combine_chains(), chain::combined, CT_COMBINATION, FOR_EACH_VEC_ELT, free(), get_chain_root(), get_loop_body_in_dom_order(), ggc_alloc(), gimple_uid(), chain::has_max_use_after, i, chain::length, m_chains, m_loop, order_drefs_by_pos(), pcom_stmt_dominates_stmt_p(), qsort, chain::refs, renumber_gimple_stmt_uids_in_blocks(), chain::type, update_pos_for_combined_chains(), and worklist.

Referenced by tree_predictive_commoning_loop().

◆ valid_initializer_p()

bool pcom_worker::valid_initializer_p	(	struct data_reference *	ref,
		unsigned	distance,
		struct data_reference *	root )

private

Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
iterations of the innermost enclosing loop).

References aff_combination_add(), aff_combination_constant_multiple_p(), aff_combination_dr_offset(), aff_combination_scale(), DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_STEP, gcc_assert, ggc_alloc(), integer_zerop(), m_cache, operand_equal_p(), tree_to_aff_combination_expand(), and TREE_TYPE.

Referenced by find_looparound_phi().

Field Documentation

◆ m_cache

tree_expand_map_t* pcom_worker::m_cache

private

Referenced by aff_combination_dr_offset(), determine_offset(), valid_initializer_p(), and ~pcom_worker().

◆ m_chains

auto_vec<chain_p> pcom_worker::m_chains

private

Referenced by determine_roots_comp(), execute_pred_commoning(), prepare_finalizers(), prepare_initializers(), release_chains(), tree_predictive_commoning_loop(), and try_combine_chains().

◆ m_datarefs

auto_vec<data_reference_p, 10> pcom_worker::m_datarefs

private

Referenced by split_data_refs_to_components(), tree_predictive_commoning_loop(), and ~pcom_worker().

◆ m_dependences

auto_vec<ddr_p, 10> pcom_worker::m_dependences

private

Referenced by split_data_refs_to_components(), tree_predictive_commoning_loop(), and ~pcom_worker().

◆ m_loop

loop_p pcom_worker::m_loop

private

Referenced by execute_pred_commoning(), execute_pred_commoning_chain(), find_looparound_phi(), prepare_finalizers_chain(), prepare_initializers_chain(), split_data_refs_to_components(), suitable_component_p(), tree_predictive_commoning_loop(), and try_combine_chains().

◆ m_looparound_phis

auto_bitmap pcom_worker::m_looparound_phis

private

Referenced by add_looparound_copies(), and single_nonlooparound_use().

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

tree-predcom.cc

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ tree_expand_map_t

Constructor & Destructor Documentation

◆ pcom_worker() [1/2]

◆ ~pcom_worker()

◆ pcom_worker() [2/2]

Member Function Documentation

◆ add_looparound_copies()

◆ aff_combination_dr_offset()

◆ combinable_refs_p()

◆ combine_chains()

◆ determine_offset()

◆ determine_roots()

◆ determine_roots_comp()

◆ execute_pred_commoning()

◆ execute_pred_commoning_chain()

◆ filter_suitable_components()

◆ find_associative_operation_root()

◆ find_common_use_stmt()

◆ find_looparound_phi()

◆ find_use_stmt()

◆ operator=()

◆ prepare_finalizers()

◆ prepare_finalizers_chain()

◆ prepare_initializers()

◆ prepare_initializers_chain()

◆ reassociate_to_the_same_stmt()

◆ release_chain()

◆ release_chains()

◆ remove_stmt()

◆ single_nonlooparound_use()

◆ split_data_refs_to_components()

◆ stmt_combining_refs()

◆ suitable_component_p()

◆ tree_predictive_commoning_loop()

◆ try_combine_chains()

◆ valid_initializer_p()

Field Documentation

◆ m_cache

◆ m_chains

◆ m_datarefs

◆ m_dependences

◆ m_loop

◆ m_looparound_phis