Data Structures
struct	mem_ref_group
struct	mem_ref
struct	ar_data

Functions
static void	dump_mem_details (FILE *file, tree base, tree step, HOST_WIDE_INT delta, bool write_p)
static void	dump_mem_ref ()
static struct mem_ref_group *	find_or_create_group ()
static void	record_ref (struct mem_ref_group *group, gimple stmt, tree mem, HOST_WIDE_INT delta, bool write_p)
static void	release_mem_refs ()
static bool	idx_analyze_ref ()
static bool	analyze_ref (struct loop loop, tree ref_p, tree base, tree step, HOST_WIDE_INT *delta, gimple stmt)
static bool	gather_memory_references_ref (struct loop loop, struct mem_ref_group *refs, tree ref, bool write_p, gimple stmt)
static struct mem_ref_group *	gather_memory_references ()
static void	prune_ref_by_self_reuse ()
static HOST_WIDE_INT	ddown ()
static bool	is_miss_rate_acceptable (unsigned HOST_WIDE_INT cache_line_size, HOST_WIDE_INT step, HOST_WIDE_INT delta, unsigned HOST_WIDE_INT distinct_iters, int align_unit)
static void	prune_ref_by_group_reuse (struct mem_ref ref, struct mem_ref by, bool by_is_before)
static void	prune_ref_by_reuse ()
static void	prune_group_by_reuse ()
static void	prune_by_reuse ()
static bool	should_issue_prefetch_p ()
static bool	schedule_prefetches (struct mem_ref_group *groups, unsigned unroll_factor, unsigned ahead)
static bool	nothing_to_prefetch_p ()
static int	estimate_prefetch_count ()
static void	issue_prefetch_ref ()
static void	issue_prefetches (struct mem_ref_group *groups, unsigned unroll_factor, unsigned ahead)
static bool	nontemporal_store_p ()
static bool	mark_nontemporal_store ()
static void	emit_mfence_after_loop ()
static bool	may_use_storent_in_loop_p ()
static void	mark_nontemporal_stores ()
static bool	should_unroll_loop_p (struct loop loop, struct tree_niter_desc desc, unsigned factor)
static unsigned	determine_unroll_factor (struct loop loop, struct mem_ref_group refs, unsigned ninsns, struct tree_niter_desc *desc, HOST_WIDE_INT est_niter)
static unsigned	volume_of_references ()
static unsigned	volume_of_dist_vector ()
static void	add_subscript_strides (tree access_fn, unsigned stride, HOST_WIDE_INT strides, unsigned n, struct loop loop)
static unsigned	self_reuse_distance (data_reference_p dr, unsigned loop_sizes, unsigned n, struct loop loop)
static bool	determine_loop_nest_reuse (struct loop loop, struct mem_ref_group refs, bool no_other_refs)
static bool	trip_count_to_ahead_ratio_too_small_p ()
static bool	mem_ref_count_reasonable_p ()
static bool	insn_to_prefetch_ratio_too_small_p (unsigned ninsns, unsigned prefetch_count, unsigned unroll_factor)
static bool	loop_prefetch_arrays ()
unsigned int	tree_ssa_prefetch_arrays ()

Function Documentation

static void add_subscript_strides	(	tree	access_fn,
		unsigned	stride,
		HOST_WIDE_INT *	strides,
		unsigned	n,
		struct loop *	loop
	)

static

Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
   at the position corresponding to the loop of the step.  N is the depth
   of the considered loop nest, and, LOOP is its innermost loop.

References get_chrec_loop(), host_integerp(), HOST_WIDE_INT, loop_depth(), and tree_low_cst().

Referenced by self_reuse_distance().

static bool analyze_ref	(	struct loop *	loop,
		tree *	ref_p,
		tree *	base,
		tree *	step,
		HOST_WIDE_INT *	delta,
		gimple	stmt
	)

static

Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
   STEP are integer constants and iter is number of iterations of LOOP.  The
   reference occurs in statement STMT.  Strips nonaddressable component
   references from REF_P.

References ar_data::delta, for_each_index(), HOST_WIDE_INT, idx_analyze_ref(), int_size_in_bytes(), ar_data::loop, ar_data::step, ar_data::stmt, and unshare_expr().

Referenced by gather_memory_references_ref().

static HOST_WIDE_INT ddown ( )

static

Divides X by BY, rounding down.

Referenced by prune_ref_by_group_reuse().

static bool determine_loop_nest_reuse	(	struct loop *	loop,
		struct mem_ref_group *	refs,
		bool	no_other_refs
	)

static

Determines the distance till the first reuse of each reference in REFS
   in the loop nest of LOOP.  NO_OTHER_REFS is true if there are no other
   memory references in the loop.  Return false if the analysis fails.

References data_reference::aux, chrec_dont_know, chrec_known, compute_all_dependences(), create_data_ref(), DDR_A, DDR_ARE_DEPENDENT, DDR_B, DDR_DIST_VECT, DDR_NUM_DIST_VECTS, dump_file, dump_flags, estimated_stmt_executions_int(), expected_loop_iterations(), find_loop_nest(), free(), free_data_refs(), free_dependence_relations(), HOST_WIDE_INT, mem_ref::independent_p, loop::inner, lambda_vector_zerop(), loop_containing_stmt(), loop_outer(), mem_ref::mem, loop::next, mem_ref_group::next, mem_ref::next, mem_ref_group::refs, mem_ref::reuse_distance, self_reuse_distance(), mem_ref::stmt, vNULL, volume_of_dist_vector(), volume_of_references(), and mem_ref::write_p.

Referenced by loop_prefetch_arrays().

static unsigned determine_unroll_factor	(	struct loop *	loop,
		struct mem_ref_group *	refs,
		unsigned	ninsns,
		struct tree_niter_desc *	desc,
		HOST_WIDE_INT	est_niter
	)

static

Determine the coefficient by that unroll LOOP, from the information
   contained in the list of memory references REFS.  Description of
   umber of iterations of LOOP is stored to DESC.  NINSNS is the number of
   insns of the LOOP.  EST_NITER is the estimated number of iterations of
   the loop, or -1 if no estimate is available.

References HOST_WIDE_INT, least_common_multiple(), mem_ref_group::next, mem_ref::next, mem_ref::prefetch_mod, mem_ref_group::refs, should_issue_prefetch_p(), and should_unroll_loop_p().

Referenced by loop_prefetch_arrays().

static void dump_mem_details	(	FILE *	file,
		tree	base,
		tree	step,
		HOST_WIDE_INT	delta,
		bool	write_p
	)

static

Dumps information about memory reference

References cst_and_fits_in_hwi(), HOST_WIDE_INT_PRINT_DEC, int_cst_value(), and print_generic_expr().

Referenced by dump_mem_ref(), and gather_memory_references_ref().

static void dump_mem_ref ( )

static

Dumps information about reference REF to FILE.

References mem_ref_group::base, mem_ref::delta, dump_mem_details(), mem_ref::group, mem_ref_group::step, and mem_ref::write_p.

Referenced by record_ref().

static void emit_mfence_after_loop ( )

static

Issue a memory fence instruction after LOOP.

References edge_def::dest, edge_def::flags, get_loop_exit_edges(), gimple_build_call(), gsi_after_labels(), gsi_insert_before(), GSI_NEW_STMT, single_pred_p(), split_loop_exit_edge(), and update_ssa().

Referenced by mark_nontemporal_stores().

static int estimate_prefetch_count ( )

static

Estimate the number of prefetches in the given GROUPS.
   UNROLL_FACTOR is the factor by which LOOP was unrolled.

References mem_ref_group::next, mem_ref::next, mem_ref::prefetch_mod, mem_ref_group::refs, and should_issue_prefetch_p().

Referenced by loop_prefetch_arrays().

static struct mem_ref_group* find_or_create_group ( )

staticread

Finds a group with BASE and STEP in GROUPS, or creates one if it does not
   exist.

References mem_ref_group::base, cst_and_fits_in_hwi(), int_cst_value(), mem_ref_group::next, operand_equal_p(), mem_ref_group::refs, and mem_ref_group::step.

Referenced by gather_memory_references_ref().

static struct mem_ref_group* gather_memory_references ( )

staticread

Record the suitable memory references in LOOP.  NO_OTHER_REFS is set to
   true if there are no other memory references inside the loop.

References free(), gather_memory_references_ref(), get_loop_body_in_dom_order(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_call_flags(), gimple_vuse(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), is_gimple_call(), basic_block_def::loop_father, loop::num_nodes, and refs.

Referenced by loop_prefetch_arrays().

static bool gather_memory_references_ref	(	struct loop *	loop,
		struct mem_ref_group **	refs,
		tree	ref,
		bool	write_p,
		gimple	stmt
	)

static

Record a memory reference REF to the list REFS.  The reference occurs in
   LOOP in statement STMT and it is write if WRITE_P.  Returns true if the
   reference was recorded, false otherwise.

References analyze_ref(), cst_and_fits_in_hwi(), ar_data::delta, dump_file, dump_flags, dump_mem_details(), expr_invariant_in_loop_p(), find_or_create_group(), get_base_address(), HOST_WIDE_INT, loop::inner, loop_outermost(), may_be_nonaddressable_p(), print_generic_expr(), record_ref(), and ar_data::step.

Referenced by gather_memory_references().

static bool idx_analyze_ref ( )

static

Analyzes a single INDEX of a memory reference to obtain information
   described at analyze_ref.  Callback for for_each_index.

References array_ref_element_size(), affine_iv::base, build_int_cst(), cst_and_fits_in_hwi(), ar_data::delta, HOST_WIDE_INT, int_cst_value(), ar_data::loop, loop_containing_stmt(), simple_iv(), ar_data::step, affine_iv::step, and ar_data::stmt.

Referenced by analyze_ref().

static bool insn_to_prefetch_ratio_too_small_p	(	unsigned	ninsns,
		unsigned	prefetch_count,
		unsigned	unroll_factor
	)

static

Determine whether or not the instruction to prefetch ratio in the loop is
   too small based on the profitablity consideration.
   NINSNS: estimated number of instructions in the loop,
   PREFETCH_COUNT: an estimate of the number of prefetches,
   UNROLL_FACTOR:  the factor to unroll the loop if prefetching.

References dump_file, and dump_flags.

Referenced by loop_prefetch_arrays().

static bool is_miss_rate_acceptable	(	unsigned HOST_WIDE_INT	cache_line_size,
		HOST_WIDE_INT	step,
		HOST_WIDE_INT	delta,
		unsigned HOST_WIDE_INT	distinct_iters,
		int	align_unit
	)

static

Given a CACHE_LINE_SIZE and two inductive memory references
   with a common STEP greater than CACHE_LINE_SIZE and an address
   difference DELTA, compute the probability that they will fall
   in different cache lines.  Return true if the computed miss rate
   is not greater than the ACCEPTABLE_MISS_RATE.  DISTINCT_ITERS is the
   number of distinct iterations after which the pattern repeats itself.
   ALIGN_UNIT is the unit of alignment in bytes.

References HOST_WIDE_INT.

Referenced by prune_ref_by_group_reuse().

static void issue_prefetch_ref ( )

static

Issue prefetches for the reference REF into loop as decided before.
   HEAD is the number of iterations to prefetch ahead.  UNROLL_FACTOR
   is the factor by which LOOP was unrolled.

References builtin_decl_explicit(), cst_and_fits_in_hwi(), mem_ref::delta, dump_file, dump_flags, force_gimple_operand_gsi(), gimple_build_call(), mem_ref::group, gsi_for_stmt(), gsi_insert_before(), GSI_SAME_STMT, HOST_WIDE_INT, int_cst_value(), mem_ref::mem, mem_ref::prefetch_mod, mem_ref::reuse_distance, mem_ref_group::step, mem_ref::stmt, unshare_expr(), and mem_ref::write_p.

Referenced by issue_prefetches().

static void issue_prefetches	(	struct mem_ref_group *	groups,
		unsigned	unroll_factor,
		unsigned	ahead
	)

static

Issue prefetches for the references in GROUPS into loop as decided before.
   HEAD is the number of iterations to prefetch ahead.  UNROLL_FACTOR is the
   factor by that LOOP was unrolled.

References mem_ref::issue_prefetch_p, issue_prefetch_ref(), mem_ref_group::next, mem_ref::next, and mem_ref_group::refs.

Referenced by loop_prefetch_arrays().

static bool loop_prefetch_arrays ( )

static

Issue prefetch instructions for array references in LOOP.  Returns
   true if the LOOP was unrolled.

References determine_loop_nest_reuse(), determine_unroll_factor(), dump_file, dump_flags, eni_size_weights, eni_time_weights, estimate_prefetch_count(), estimated_stmt_executions_int(), gather_memory_references(), HOST_WIDE_INT, HOST_WIDE_INT_PRINT_DEC, insn_to_prefetch_ratio_too_small_p(), issue_prefetches(), mark_nontemporal_stores(), max_stmt_executions_int(), mem_ref_count_reasonable_p(), nothing_to_prefetch_p(), optimize_loop_nest_for_size_p(), prune_by_reuse(), refs, release_mem_refs(), schedule_prefetches(), single_dom_exit(), tree_num_loop_insns(), tree_unroll_loop(), and trip_count_to_ahead_ratio_too_small_p().

Referenced by tree_ssa_prefetch_arrays().

static bool mark_nontemporal_store ( )

static

If REF is a nontemporal store, we mark the corresponding modify statement
   and return true.  Otherwise, we return false.

References dump_file, dump_flags, gimple_assign_set_nontemporal_move(), nontemporal_store_p(), mem_ref::stmt, and mem_ref::storent_p.

Referenced by mark_nontemporal_stores().

static void mark_nontemporal_stores ( )

static

Marks nontemporal stores in LOOP.  GROUPS contains the description of memory
   references in the loop.

References emit_mfence_after_loop(), mark_nontemporal_store(), may_use_storent_in_loop_p(), mem_ref_group::next, mem_ref::next, and mem_ref_group::refs.

Referenced by loop_prefetch_arrays().

static bool may_use_storent_in_loop_p ( )

static

Returns true if we can use storent in loop, false otherwise.

References edge_def::dest, edge_def::flags, get_loop_exit_edges(), and loop::inner.

Referenced by mark_nontemporal_stores().

static bool mem_ref_count_reasonable_p ( )

static

Determine whether or not the number of memory references in the loop is
   reasonable based on the profitablity and compilation time considerations.
   NINSNS: estimated number of instructions in the loop,
   MEM_REF_COUNT: total number of memory references in the loop.

References dump_file, and dump_flags.

Referenced by loop_prefetch_arrays().

static bool nontemporal_store_p ( )

static

Returns true if REF is a memory write for that a nontemporal store insn
   can be used.

References mem_ref::independent_p, mem_ref::mem, optab_handler(), mem_ref::reuse_distance, and mem_ref::write_p.

Referenced by mark_nontemporal_store().

static bool nothing_to_prefetch_p ( )

static

Return TRUE if no prefetch is going to be generated in the given
   GROUPS.

References mem_ref_group::next, mem_ref::next, mem_ref_group::refs, and should_issue_prefetch_p().

Referenced by loop_prefetch_arrays().

static void prune_by_reuse ( )

static

Prune the list of prefetch candidates GROUPS using the reuse analysis.

References mem_ref_group::next, and prune_group_by_reuse().

Referenced by loop_prefetch_arrays().

static void prune_group_by_reuse ( )

static

Prune the prefetch candidates in GROUP using the reuse analysis.

References dump_file, dump_flags, HOST_WIDE_INT_PRINT_DEC, mem_ref::next, mem_ref::prefetch_before, mem_ref::prefetch_mod, prune_ref_by_reuse(), and mem_ref_group::refs.

Referenced by prune_by_reuse().

static void prune_ref_by_group_reuse	(	struct mem_ref *	ref,
		struct mem_ref *	by,
		bool	by_is_before
	)

static

Prune the prefetch candidate REF using the reuse with BY.
   If BY_IS_BEFORE is true, BY is before REF in the loop.

References absu_hwi(), cst_and_fits_in_hwi(), ddown(), mem_ref::delta, mem_ref::group, HOST_WIDE_INT, int_cst_value(), is_miss_rate_acceptable(), mem_ref::mem, mem_ref::prefetch_before, and mem_ref_group::step.

Referenced by prune_ref_by_reuse().

static void prune_ref_by_reuse ( )

static

Prune the prefetch candidate REF using the reuses with other references
   in REFS.

References mem_ref::next, prune_ref_by_group_reuse(), prune_ref_by_self_reuse(), and mem_ref::write_p.

Referenced by prune_group_by_reuse().

static void prune_ref_by_self_reuse ( )

static

Prune the prefetch candidate REF using the self-reuse.

References cst_and_fits_in_hwi(), mem_ref::group, HOST_WIDE_INT, int_cst_value(), mem_ref::prefetch_before, mem_ref::prefetch_mod, and mem_ref_group::step.

Referenced by prune_ref_by_reuse().

static void record_ref	(	struct mem_ref_group *	group,
		gimple	stmt,
		tree	mem,
		HOST_WIDE_INT	delta,
		bool	write_p
	)

static

Records a memory reference MEM in GROUP with offset DELTA and write status
   WRITE_P.  The reference occurs in statement STMT.

References mem_ref::delta, dump_file, dump_flags, dump_mem_ref(), mem_ref::group, mem_ref::mem, mem_ref_group::next, mem_ref::next, mem_ref_group::refs, mem_ref::stmt, and mem_ref::write_p.

Referenced by gather_memory_references_ref().

static void release_mem_refs ( )

static

Release memory references in GROUPS.

References free(), mem_ref_group::next, mem_ref::next, and mem_ref_group::refs.

Referenced by loop_prefetch_arrays().

static bool schedule_prefetches	(	struct mem_ref_group *	groups,
		unsigned	unroll_factor,
		unsigned	ahead
	)

static

Decide which of the prefetch candidates in GROUPS to prefetch.
   AHEAD is the number of iterations to prefetch ahead (which corresponds
   to the number of simultaneous instances of one prefetch running at a
   time).  UNROLL_FACTOR is the factor by that the loop is going to be
   unrolled.  Returns true if there is anything to prefetch.

References dump_file, dump_flags, mem_ref::issue_prefetch_p, mem_ref_group::next, mem_ref::next, mem_ref::prefetch_mod, mem_ref_group::refs, and should_issue_prefetch_p().

Referenced by loop_prefetch_arrays().

static unsigned self_reuse_distance	(	data_reference_p	dr,
		unsigned *	loop_sizes,
		unsigned	n,
		struct loop *	loop
	)

static

Returns the volume of memory references accessed between two consecutive
   self-reuses of the reference DR.  We consider the subscripts of DR in N
   loops, and LOOP_SIZES contains the volumes of accesses in each of the
   loops.  LOOP is the innermost loop of the current loop nest.

References add_subscript_strides(), DR_ACCESS_FNS, DR_REF, free(), handled_component_p(), host_integerp(), HOST_WIDE_INT, and tree_low_cst().

Referenced by determine_loop_nest_reuse().

static bool should_issue_prefetch_p ( )

static

Returns true if we should issue prefetch for REF.

References dump_file, dump_flags, mem_ref::prefetch_before, and mem_ref::storent_p.

Referenced by determine_unroll_factor(), estimate_prefetch_count(), nothing_to_prefetch_p(), and schedule_prefetches().

static bool should_unroll_loop_p	(	struct loop *	loop,
		struct tree_niter_desc *	desc,
		unsigned	factor
	)

static

Determines whether we can profitably unroll LOOP FACTOR times, and if
   this is the case, fill in DESC by the description of number of
   iterations.

References can_unroll_loop_p(), and loop::num_nodes.

Referenced by determine_unroll_factor().

unsigned int tree_ssa_prefetch_arrays ( void )

Issue prefetch instructions for array references in loops.

References add_builtin_function(), build_function_type_list(), BUILT_IN_NORMAL, builtin_decl_explicit_p(), dump_file, dump_flags, free_original_copy_tables(), initialize_original_copy_tables(), LI_FROM_INNERMOST, loop_prefetch_arrays(), loop::num, scev_reset(), and set_builtin_decl().

Referenced by tree_ssa_loop_prefetch().

static bool trip_count_to_ahead_ratio_too_small_p ( )

static

Determine whether or not the trip count to ahead ratio is too small based
   on prefitablility consideration.
   AHEAD: the iteration ahead distance,
   EST_NITER: the estimated trip count.

References dump_file, dump_flags, and HOST_WIDE_INT.

Referenced by loop_prefetch_arrays().

static unsigned volume_of_dist_vector ( )

static

Returns the volume of memory references accessed across VEC iterations of
   loops, whose sizes are described in the LOOP_SIZES array.  N is the number
   of the loops in the nest (length of VEC and LOOP_SIZES vectors).

Referenced by determine_loop_nest_reuse().

static unsigned volume_of_references ( )

static

Returns the total volume of the memory references REFS, taking into account
   reuses in the innermost loop and cache line size.  TODO -- we should also
   take into account reuses across the iterations of the loops in the loop
   nest.

References mem_ref_group::next, mem_ref::next, mem_ref::prefetch_before, mem_ref::prefetch_mod, and mem_ref_group::refs.

Referenced by determine_loop_nest_reuse().

Data Structures

Functions

Function Documentation