Collaboration diagram for loop_distribution:

Public Member Functions
int	get_bb_top_order_index_size (void)

int	get_bb_top_order_index (int i)

unsigned int	execute (function *fun)

Private Member Functions
bool	create_rdg_vertices (struct graph rdg, const vec< gimple > &stmts, loop_p loop)

void	stmts_from_loop (class loop loop, vec< gimple > *stmts)

struct graph *	build_rdg (class loop loop, control_dependences cd)

void	partition_merge_into (struct graph rdg, partition dest, partition *partition, enum fuse_type ft)

data_dependence_relation *	get_data_dependence (struct graph *rdg, data_reference_p a, data_reference_p b)

bool	data_dep_in_cycle_p (struct graph *rdg, data_reference_p dr1, data_reference_p dr2)

void	update_type_for_merge (struct graph rdg, partition partition1, partition *partition2)

partition *	build_rdg_partition_for_vertex (struct graph *rdg, int v)

void	classify_builtin_ldst (loop_p loop, struct graph rdg, partition partition, data_reference_p dst_dr, data_reference_p src_dr)

bool	classify_partition (loop_p loop, struct graph rdg, partition partition, bitmap stmt_in_all_partitions)

bool	share_memory_accesses (struct graph rdg, partition partition1, partition *partition2)

void	rdg_build_partitions (struct graph rdg, vec< gimple > starting_stmts, vec< partition * > *partitions)

int	pg_add_dependence_edges (struct graph rdg, int dir, bitmap drs1, bitmap drs2, vec< ddr_p > alias_ddrs)

struct graph *	build_partition_graph (struct graph rdg, vec< struct partition > *partitions, bool ignore_alias_p)

void	merge_dep_scc_partitions (struct graph rdg, vec< struct partition > *partitions, bool ignore_alias_p)

void	break_alias_scc_partitions (struct graph rdg, vec< struct partition > partitions, vec< ddr_p > alias_ddrs)

void	finalize_partitions (class loop loop, vec< struct partition > partitions, vec< ddr_p > alias_ddrs)

int	distribute_loop (class loop loop, const vec< gimple > &stmts, control_dependences cd, int nb_calls, bool *destroy_p, bool only_patterns_p)

bool	transform_reduction_loop (loop_p loop)

void	bb_top_order_init (void)

void	bb_top_order_destroy (void)

Private Attributes
vec< loop_p >	loop_nest

vec< data_reference_p >	datarefs_vec

bool	has_nonaddressable_dataref_p

hash_table< ddr_hasher > *	ddrs_table

int *	bb_top_order_index

int	bb_top_order_index_size

Member Function Documentation

◆ bb_top_order_destroy()

void loop_distribution::bb_top_order_destroy ( void )

private

References bb_top_order_index, bb_top_order_index_size, free(), and NULL.

Referenced by execute().

◆ bb_top_order_init()

void loop_distribution::bb_top_order_init ( void )

private

References bb_top_order_index, bb_top_order_index_size, BITMAP_ALLOC, BITMAP_FREE, bitmap_set_bit, cfun, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK, free(), i, last_basic_block_for_fn, n_basic_blocks_for_fn, NULL, NUM_FIXED_BLOCKS, rev_post_order_and_mark_dfs_back_seme(), and single_succ_edge().

Referenced by execute().

◆ break_alias_scc_partitions()

void loop_distribution::break_alias_scc_partitions	(	struct graph *	rdg,
		vec< struct partition * > *	partitions,
		vec< ddr_p > *	alias_ddrs )

private

This is the main function breaking strong conected components in
PARTITIONS giving reduced depdendence graph RDG.  Store data dependence
relations for runtime alias check in ALIAS_DDRS.

References pg_edge_callback_data::alias_ddrs, bitmap_bit_p, bitmap_clear_bit(), bitmap_count_bits(), bitmap_set_range(), build_partition_graph(), vertex::component, vertex::data, dump_data_dependence_relations(), dump_file, dump_flags, for_each_edge(), free(), free_graph(), free_partition_graph_edata_cb(), free_partition_graph_vdata(), FUSE_SAME_SCC, gcc_assert, graphds_scc(), i, graph::n_vertices, NULL, partition_builtin_p(), partition_free(), partition_merge_into(), partition_reduction_p(), pg_collect_alias_ddrs(), pg_skip_alias_edge(), pg_unmark_merged_alias_ddrs(), vertex::post, PTYPE_SEQUENTIAL, pg_edge_callback_data::sccs_to_merge, sort_partitions_by_post_order(), TDF_DETAILS, partition::type, graph::vertices, and pg_edge_callback_data::vertices_component.

Referenced by distribute_loop().

◆ build_partition_graph()

struct graph * loop_distribution::build_partition_graph	(	struct graph *	rdg,
		vec< struct partition * > *	partitions,
		bool	ignore_alias_p )

private

Build and return partition dependence graph for PARTITIONS.  RDG is
reduced dependence graph for the loop to be distributed.  If IGNORE_ALIAS_P
is true, data dependence caused by possible alias between references
is ignored, as if it doesn't exist at all; otherwise all depdendences
are considered.

References add_partition_graph_edge(), partition::datarefs, i, init_partition_graph_vertices(), new_graph(), NULL, partition_reduction_p(), and pg_add_dependence_edges().

Referenced by break_alias_scc_partitions(), and merge_dep_scc_partitions().

◆ build_rdg()

struct graph * loop_distribution::build_rdg	(	class loop *	loop,
		control_dependences *	cd )

private

References cd, create_rdg_cd_edges(), create_rdg_flow_edges(), create_rdg_vertices(), free_rdg(), new_graph(), NULL, and stmts_from_loop().

Referenced by distribute_loop(), and transform_reduction_loop().

◆ build_rdg_partition_for_vertex()

partition * loop_distribution::build_rdg_partition_for_vertex	(	struct graph *	rdg,
		int	v )

private

References bitmap_set_bit, partition::datarefs, datarefs_vec, DR_BASE_ADDRESS, DR_INDEX, DR_INIT, DR_OFFSET, DR_STEP, FOR_EACH_VEC_ELT, gcc_assert, graphds_dfs(), i, NULL, partition_alloc(), PTYPE_SEQUENTIAL, RDG_DATAREFS, partition::stmts, partition::type, and update_type_for_merge().

Referenced by rdg_build_partitions().

◆ classify_builtin_ldst()

void loop_distribution::classify_builtin_ldst	(	loop_p	loop,
		struct graph *	rdg,
		partition *	partition,
		data_reference_p	dst_dr,
		data_reference_p	src_dr )

private

Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
if it forms builtin memcpy or memmove call.

References alloc_builtin(), partition::builtin, chrec_dont_know, chrec_known, compute_access_range(), DDR_ARE_DEPENDENT, DDR_DIST_VECTS, DDR_LOOP_NEST, DDR_NUM_DIST_VECTS, DDR_REVERSED_P, dependence_level(), DR_REF, FOR_EACH_VEC_ELT, get_data_dependence(), i, partition::kind, operand_equal_p(), PKIND_MEMCPY, PKIND_MEMMOVE, and reverse_storage_order_for_component_p().

Referenced by classify_partition().

◆ classify_partition()

bool loop_distribution::classify_partition	(	loop_p	loop,
		struct graph *	rdg,
		partition *	partition,
		bitmap	stmt_in_all_partitions )

private

References bitmap_bit_p, classify_builtin_ldst(), classify_builtin_st(), DR_STMT, EXECUTE_IF_SET_IN_BITMAP, find_single_drs(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_has_volatile_ops(), gimple_location(), i, partition::loc, NULL, RDG_STMT, partition::reduction_p, stmt_has_scalar_dependences_outside_loop(), and partition::stmts.

Referenced by distribute_loop().

◆ create_rdg_vertices()

bool loop_distribution::create_rdg_vertices	(	struct graph *	rdg,
		const vec< gimple * > &	stmts,
		loop_p	loop )

private

References datarefs_vec, DR_IS_READ, find_data_references_in_stmt(), FOR_EACH_VEC_ELT, gimple_set_uid(), has_nonaddressable_dataref_p, i, may_be_nonaddressable_p(), RDGV_DATAREFS, RDGV_HAS_MEM_READS, RDGV_HAS_MEM_WRITE, RDGV_STMT, data_reference::ref, and graph::vertices.

Referenced by build_rdg().

◆ data_dep_in_cycle_p()

bool loop_distribution::data_dep_in_cycle_p	(	struct graph *	rdg,
		data_reference_p	dr1,
		data_reference_p	dr2 )

private

References chrec_dont_know, chrec_known, DDR_ARE_DEPENDENT, DDR_DIST_VECT, DDR_NB_LOOPS, DDR_NUM_DIST_VECTS, DDR_REVERSED_P, DR_STMT, get_data_dependence(), lambda_vector_zerop(), NULL, rdg_vertex_for_stmt(), and runtime_alias_check_p().

Referenced by update_type_for_merge().

◆ distribute_loop()

int loop_distribution::distribute_loop	(	class loop *	loop,
		const vec< gimple * > &	stmts,
		control_dependences *	cd,
		int *	nb_calls,
		bool *	destroy_p,
		bool	only_patterns_p )

private

Distributes the code from LOOP in such a way that producer statements
are placed before consumer statements.  Tries to separate only the
statements from STMTS into separate loops.  Returns the number of
distributed loops.  Set NB_CALLS to number of generated builtin calls.
Set *DESTROY_P to whether LOOP needs to be destroyed.

References hash_table< Descriptor, Lazy, Allocator >::begin(), bitmap_and_into(), bitmap_copy(), break_alias_scc_partitions(), build_rdg(), cd, changed, classify_partition(), datarefs_vec, ddrs_table, dump_file, dump_flags, dump_rdg(), dump_rdg_partitions(), hash_table< Descriptor, Lazy, Allocator >::end(), finalize_partitions(), find_loop_nest(), FOR_EACH_VEC_ELT, free_data_refs(), free_dependence_relation(), free_rdg(), FUSE_NON_BUILTIN, FUSE_REDUCTION, FUSE_SHARE_REF, generate_code_for_partition(), has_nonaddressable_dataref_p, i, loop::inner, partition::kind, loop_nest, MAX_DATAREFS_NUM, merge_dep_scc_partitions(), NULL, loop::num, partition_builtin_p(), partition_contains_all_rw(), partition_free(), partition_merge_into(), partition_reduction_p(), PKIND_NORMAL, rdg_build_partitions(), share_memory_accesses(), TDF_DETAILS, version_for_distribution_p(), and version_loop_by_alias_check().

Referenced by execute().

◆ execute()

unsigned int loop_distribution::execute ( function * fun )

References bb_top_order_destroy(), bb_top_order_index, bb_top_order_init(), calculate_dominance_info(), cd, CDI_DOMINATORS, CDI_POST_DOMINATORS, cfun, changed, checking_verify_loop_structure(), chrec_dont_know, datarefs_vec, destroy_loop(), distribute_loop(), dump_enabled_p(), dump_file, dump_flags, dump_printf_loc(), estimated_loop_iterations_int(), find_loop_location(), find_seed_stmts_for_distribution(), FOR_ALL_BB_FN, FOR_EACH_VEC_ELT, free_data_refs(), free_dominance_info(), gimple_set_uid(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), i, loop::inner, LI_ONLY_INNERMOST, likely_max_loop_iterations_int(), mark_virtual_operands_for_renaming(), MSG_OPTIMIZED_LOCATIONS, NULL, NULL_TREE, loop::num, number_of_latch_executions(), number_of_loops(), optimize_loop_for_speed_p(), prepare_perfect_loop_nest(), rewrite_into_loop_closed_ssa(), scev_reset(), single_exit(), TDF_DETAILS, TODO_cleanup_cfg, TODO_update_ssa, and transform_reduction_loop().

◆ finalize_partitions()

void loop_distribution::finalize_partitions	(	class loop *	loop,
		vec< struct partition * > *	partitions,
		vec< ddr_p > *	alias_ddrs )

private

References a, FUSE_FINALIZE, fuse_memset_builtins(), i, loop::inner, partition::kind, NULL, NUM_PARTITION_THRESHOLD, partition_builtin_p(), partition_free(), partition_merge_into(), PKIND_PARTIAL_MEMSET, and partition::type.

Referenced by distribute_loop().

◆ get_bb_top_order_index()

int loop_distribution::get_bb_top_order_index ( int i )

inline

References bb_top_order_index, and i.

Referenced by bb_top_order_cmp_r().

◆ get_bb_top_order_index_size()

int loop_distribution::get_bb_top_order_index_size ( void )

inline

References bb_top_order_index_size.

Referenced by bb_top_order_cmp_r().

◆ get_data_dependence()

data_dependence_relation * loop_distribution::get_data_dependence	(	struct graph *	rdg,
		data_reference_p	a,
		data_reference_p	b )

private

References a, data_dependence_relation::a, b, data_dependence_relation::b, compute_affine_dependence(), ddrs_table, DR_IS_WRITE, DR_STMT, hash_table< Descriptor, Lazy, Allocator >::find_slot(), gcc_assert, initialize_data_dependence_relation(), loop_nest, NULL, and rdg_vertex_for_stmt().

Referenced by classify_builtin_ldst(), data_dep_in_cycle_p(), and pg_add_dependence_edges().

◆ merge_dep_scc_partitions()

void loop_distribution::merge_dep_scc_partitions	(	struct graph *	rdg,
		vec< struct partition * > *	partitions,
		bool	ignore_alias_p )

private

References build_partition_graph(), vertex::component, vertex::data, for_each_edge(), free_graph(), free_partition_graph_edata_cb(), free_partition_graph_vdata(), FUSE_SAME_SCC, gcc_assert, graphds_scc(), i, NULL, partition_free(), partition_merge_into(), PTYPE_SEQUENTIAL, sort_partitions_by_post_order(), partition::type, and graph::vertices.

Referenced by distribute_loop().

◆ partition_merge_into()

void loop_distribution::partition_merge_into	(	struct graph *	rdg,
		partition *	dest,
		partition *	partition,
		enum fuse_type	ft )

private

Merge PARTITION into the partition DEST.  RDG is the reduced dependence
graph and we update type for result partition if it is non-NULL.

References bitmap_ior_into(), partition::datarefs, dump_bitmap(), dump_file, dump_flags, fuse_message, partition::kind, NULL, partition_reduction_p(), PKIND_NORMAL, PTYPE_PARALLEL, partition::reduction_p, partition::stmts, TDF_DETAILS, partition::type, and update_type_for_merge().

Referenced by break_alias_scc_partitions(), distribute_loop(), finalize_partitions(), and merge_dep_scc_partitions().

◆ pg_add_dependence_edges()

int loop_distribution::pg_add_dependence_edges	(	struct graph *	rdg,
		int	dir,
		bitmap	drs1,
		bitmap	drs2,
		vec< ddr_p > *	alias_ddrs )

private

◆ rdg_build_partitions()

void loop_distribution::rdg_build_partitions	(	struct graph *	rdg,
		vec< gimple * >	starting_stmts,
		vec< partition * > *	partitions )

private

For each seed statement in STARTING_STMTS, this function builds
partition for it by adding depended statements according to RDG.
All partitions are recorded in PARTITIONS.

References bitmap_bit_p, bitmap_ior_into(), bitmap_print(), build_rdg_partition_for_vertex(), dump_file, dump_flags, FOR_EACH_VEC_ELT, i, processed, PTYPE_PARALLEL, rdg_vertex_for_stmt(), partition::stmts, TDF_DETAILS, and partition::type.

Referenced by distribute_loop().

◆ share_memory_accesses()

bool loop_distribution::share_memory_accesses	(	struct graph *	rdg,
		partition *	partition1,
		partition *	partition2 )

private

References partition::datarefs, datarefs_vec, DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_STEP, EXECUTE_IF_AND_IN_BITMAP, EXECUTE_IF_SET_IN_BITMAP, i, operand_equal_p(), RDG_MEM_READS_STMT, RDG_MEM_WRITE_STMT, and partition::stmts.

Referenced by distribute_loop().

◆ stmts_from_loop()

void loop_distribution::stmts_from_loop	(	class loop *	loop,
		vec< gimple * > *	stmts )

private

References bb_top_order_cmp_r(), free(), get_loop_body_in_custom_order(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), i, is_gimple_debug(), loop::num_nodes, and virtual_operand_p().

Referenced by build_rdg().

◆ transform_reduction_loop()

bool loop_distribution::transform_reduction_loop ( loop_p loop )

private

Transform loops which mimic the effects of builtins rawmemchr or strlen and
replace them accordingly.  For example, a loop of the form

  for (; *p != 42; ++p);

is replaced by

  p = rawmemchr<MODE> (p, 42);

under the assumption that rawmemchr is available for a particular MODE.
Another example is

  int i;
  for (i = 42; s[i]; ++i);

which is replaced by

  i = (int)strlen (&s[42]) + 42;

for some character array S.  In case array S is not of type character array
we end up with

  i = (int)(rawmemchr<MODE> (&s[42], 0) - &s[42]) + 42;

assuming that rawmemchr is available for a particular MODE.

References affine_iv::base, bitmap_set_range(), build_fold_addr_expr, build_rdg(), builtin_decl_implicit(), char_type_node, determine_reduction_stmt(), direct_optab_handler(), DR_REF, DR_STMT, dump_file, dump_flags, find_single_drs(), free_rdg(), generate_rawmemchr_builtin(), generate_strlen_builtin(), generate_strlen_builtin_using_rawmemchr(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_single_p(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_get_lhs(), gimple_location(), gsi_last_bb(), integer_onep(), integer_zerop(), INTEGRAL_TYPE_P, graph::n_vertices, NULL, loop::num, operand_equal_p(), ptr_type_node, ptrdiff_type_node, reduction_var_overflows_first(), safe_dyn_cast(), simple_iv(), single_exit(), sizetype, SSA_NAME_DEF_STMT, affine_iv::step, TDF_DETAILS, TREE_CODE, TREE_OPERAND, TREE_TYPE, type_has_mode_precision_p(), TYPE_MODE, TYPE_OVERFLOW_UNDEFINED, TYPE_PRECISION, and TYPE_SIZE_UNIT.

Referenced by execute().

◆ update_type_for_merge()

void loop_distribution::update_type_for_merge	(	struct graph *	rdg,
		partition *	partition1,
		partition *	partition2 )

private

References data_dep_in_cycle_p(), partition::datarefs, datarefs_vec, DR_IS_READ, EXECUTE_IF_SET_IN_BITMAP, i, PTYPE_SEQUENTIAL, and partition::type.

Referenced by build_rdg_partition_for_vertex(), and partition_merge_into().

Field Documentation

◆ bb_top_order_index

int* loop_distribution::bb_top_order_index

private

Referenced by bb_top_order_destroy(), bb_top_order_init(), execute(), and get_bb_top_order_index().

◆ bb_top_order_index_size

int loop_distribution::bb_top_order_index_size

private

Referenced by bb_top_order_destroy(), bb_top_order_init(), and get_bb_top_order_index_size().

◆ datarefs_vec

vec<data_reference_p> loop_distribution::datarefs_vec

private

Referenced by build_rdg_partition_for_vertex(), create_rdg_vertices(), distribute_loop(), execute(), pg_add_dependence_edges(), share_memory_accesses(), and update_type_for_merge().

◆ ddrs_table

hash_table<ddr_hasher>* loop_distribution::ddrs_table

private

Referenced by distribute_loop(), and get_data_dependence().

◆ has_nonaddressable_dataref_p

bool loop_distribution::has_nonaddressable_dataref_p

private

Referenced by create_rdg_vertices(), and distribute_loop().

◆ loop_nest

vec<loop_p> loop_distribution::loop_nest

private

Referenced by distribute_loop(), and get_data_dependence().

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

tree-loop-distribution.cc

Public Member Functions

Private Member Functions

Private Attributes

Member Function Documentation

◆ bb_top_order_destroy()

◆ bb_top_order_init()

◆ break_alias_scc_partitions()

◆ build_partition_graph()

◆ build_rdg()

◆ build_rdg_partition_for_vertex()

◆ classify_builtin_ldst()

◆ classify_partition()

◆ create_rdg_vertices()

◆ data_dep_in_cycle_p()

◆ distribute_loop()

◆ execute()

◆ finalize_partitions()

◆ get_bb_top_order_index()

◆ get_bb_top_order_index_size()

◆ get_data_dependence()

◆ merge_dep_scc_partitions()

◆ partition_merge_into()

◆ pg_add_dependence_edges()

◆ rdg_build_partitions()

◆ share_memory_accesses()

◆ stmts_from_loop()

◆ transform_reduction_loop()

◆ update_type_for_merge()

Field Documentation

◆ bb_top_order_index

◆ bb_top_order_index_size

◆ datarefs_vec

◆ ddrs_table

◆ has_nonaddressable_dataref_p

◆ loop_nest