CbC/CbC_gcc: gcc/tree-ssa-loop-prefetch.c comparison

comparison gcc/tree-ssa-loop-prefetch.c @ 63:b7f97abdc517 gcc-4.6-20100522

update gcc from gcc-4.5.0 to gcc-4.6

author	ryoma <e075725@ie.u-ryukyu.ac.jp>
date	Mon, 24 May 2010 12:47:05 +0900
parents	77e2b8dfacca
children	f6334be47118

comparison

equal deleted inserted replaced

-:3c8a44c06a95
+:b7f97abdc517
 /* Array prefetching.
-Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc.
+Copyright (C) 2005, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
 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
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
 #include "tm.h"
 #include "tree.h"
-#include "rtl.h"
 #include "tm_p.h"
-#include "hard-reg-set.h"
 #include "basic-block.h"
 #include "output.h"
 #include "diagnostic.h"
+#include "tree-pretty-print.h"
 #include "tree-flow.h"
 #include "tree-dump.h"
 #include "timevar.h"
 #include "cfgloop.h"
-#include "varray.h"
 #include "expr.h"
 #include "tree-pass.h"
-#include "ggc.h"
 #include "insn-config.h"
 #include "recog.h"
 #include "hashtab.h"
 #include "tree-chrec.h"
 #include "tree-scalar-evolution.h"
 #ifndef FENCE_FOLLOWING_MOVNT
 #define FENCE_FOLLOWING_MOVNT NULL_TREE
 #endif
+/* It is not profitable to prefetch when the trip count is not at
+least TRIP_COUNT_TO_AHEAD_RATIO times the prefetch ahead distance.
+For example, in a loop with a prefetch ahead distance of 10,
+supposing that TRIP_COUNT_TO_AHEAD_RATIO is equal to 4, it is
+profitable to prefetch when the trip count is greater or equal to
+40.  In that case, 30 out of the 40 iterations will benefit from
+prefetching.  */
+#ifndef TRIP_COUNT_TO_AHEAD_RATIO
+#define TRIP_COUNT_TO_AHEAD_RATIO 4
+#endif
 /* The group of references between that reuse may occur.  */
 struct mem_ref_group
 {
 tree base;			/* Base of the reference.  */
-HOST_WIDE_INT step;		/* Step of the reference.  */
+tree step;			/* Step of the reference.  */
 struct mem_ref *refs;		/* References in the group.  */
 struct mem_ref_group *next;	/* Next group of references.  */
 };
 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched.  */
 #define PREFETCH_ALL		(~(unsigned HOST_WIDE_INT) 0)
+/* Do not generate a prefetch if the unroll factor is significantly less
+than what is required by the prefetch.  This is to avoid redundant
+prefetches.  For example, if prefetch_mod is 16 and unroll_factor is
+1, this means prefetching requires unrolling the loop 16 times, but
+the loop is not going to be unrolled.  In this case (ratio = 16),
+prefetching is not likely to be beneficial.  */
+#ifndef PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
+#define PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO 8
+#endif
 /* The memory reference.  */
 struct mem_ref
 {
 fprintf (file, "Reference %p:\n", (void *) ref);
 fprintf (file, "  group %p (base ", (void *) ref->group);
 print_generic_expr (file, ref->group->base, TDF_SLIM);
 fprintf (file, ", step ");
-fprintf (file, HOST_WIDE_INT_PRINT_DEC, ref->group->step);
+if (cst_and_fits_in_hwi (ref->group->step))
+fprintf (file, HOST_WIDE_INT_PRINT_DEC, int_cst_value (ref->group->step));
+else
+print_generic_expr (file, ref->group->step, TDF_TREE);
 fprintf (file, ")\n");
 fprintf (file, "  delta ");
 fprintf (file, HOST_WIDE_INT_PRINT_DEC, ref->delta);
 fprintf (file, "\n");
 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
 exist.  */
 static struct mem_ref_group *
-find_or_create_group (struct mem_ref_group **groups, tree base,
+find_or_create_group (struct mem_ref_group **groups, tree base, tree step)
-		      HOST_WIDE_INT step)
 {
 struct mem_ref_group *group;
 for (; *groups; groups = &(*groups)->next)
 {
-if ((*groups)->step == step
+if (operand_equal_p ((*groups)->step, step, 0)
 	  && operand_equal_p ((*groups)->base, base, 0))
 	return *groups;
-/* Keep the list of groups sorted by decreasing step.  */
+/* If step is an integer constant, keep the list of groups sorted
-if ((*groups)->step < step)
+by decreasing step.  */
+if (cst_and_fits_in_hwi ((*groups)->step) && cst_and_fits_in_hwi (step)
+&& int_cst_value ((*groups)->step) < int_cst_value (step))
 	break;
 }
 group = XNEW (struct mem_ref_group);
 group->base = base;
 struct ar_data
 {
 struct loop *loop;			/* Loop of the reference.  */
 gimple stmt;				/* Statement of the reference.  */
-HOST_WIDE_INT *step;			/* Step of the memory reference.  */
+tree *step;				/* Step of the memory reference.  */
 HOST_WIDE_INT *delta;			/* Offset of the memory reference.  */
 };
 /* Analyzes a single INDEX of a memory reference to obtain information
 described at analyze_ref.  Callback for for_each_index.  */
 static bool
 idx_analyze_ref (tree base, tree *index, void *data)
 {
 struct ar_data *ar_data = (struct ar_data *) data;
 tree ibase, step, stepsize;
-HOST_WIDE_INT istep, idelta = 0, imult = 1;
+HOST_WIDE_INT idelta = 0, imult = 1;
 affine_iv iv;
 if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
 || TREE_CODE (base) == ALIGN_INDIRECT_REF)
 return false;
 if (!simple_iv (ar_data->loop, loop_containing_stmt (ar_data->stmt),
-		  *index, &iv, false))
+		  *index, &iv, true))
 return false;
 ibase = iv.base;
 step = iv.step;
-if (!cst_and_fits_in_hwi (step))
-return false;
-istep = int_cst_value (step);
 if (TREE_CODE (ibase) == POINTER_PLUS_EXPR
 && cst_and_fits_in_hwi (TREE_OPERAND (ibase, 1)))
 {
 idelta = int_cst_value (TREE_OPERAND (ibase, 1));
 ibase = TREE_OPERAND (ibase, 0);
 {
 idelta += int_cst_value (ibase);
 ibase = build_int_cst (TREE_TYPE (ibase), 0);
 }
+if (*ar_data->step == NULL_TREE)
+*ar_data->step = step;
+else
+*ar_data->step = fold_build2 (PLUS_EXPR, sizetype,
+				  fold_convert (sizetype, *ar_data->step),
+				  fold_convert (sizetype, step));
 if (TREE_CODE (base) == ARRAY_REF)
 {
 stepsize = array_ref_element_size (base);
 if (!cst_and_fits_in_hwi (stepsize))
 	return false;
 imult = int_cst_value (stepsize);
-istep *= imult;
+*ar_data->step = fold_build2 (MULT_EXPR, sizetype,
+				    fold_convert (sizetype, *ar_data->step),
+				    fold_convert (sizetype, step));
 idelta *= imult;
 }
-*ar_data->step += istep;
 *ar_data->delta += idelta;
 *index = ibase;
 return true;
 }
 reference occurs in statement STMT.  Strips nonaddressable component
 references from REF_P.  */
 static bool
 analyze_ref (struct loop *loop, tree *ref_p, tree *base,
-	     HOST_WIDE_INT *step, HOST_WIDE_INT *delta,
+	     tree *step, HOST_WIDE_INT *delta,
 	     gimple stmt)
 {
 struct ar_data ar_data;
 tree off;
 HOST_WIDE_INT bit_offset;
 tree ref = *ref_p;
-*step = 0;
+*step = NULL_TREE;
 *delta = 0;
 /* First strip off the component references.  Ignore bitfields.  */
 if (TREE_CODE (ref) == COMPONENT_REF
 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref, 1)))
 static bool
 gather_memory_references_ref (struct loop *loop, struct mem_ref_group **refs,
 			      tree ref, bool write_p, gimple stmt)
 {
-tree base;
+tree base, step;
-HOST_WIDE_INT step, delta;
+HOST_WIDE_INT delta;
 struct mem_ref_group *agrp;
 if (get_base_address (ref) == NULL)
 return false;
 if (!analyze_ref (loop, &ref, &base, &step, &delta, stmt))
+return false;
+/* If analyze_ref fails the default is a NULL_TREE.  We can stop here.  */
+if (step == NULL_TREE)
 return false;
 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
 are integer constants.  */
 agrp = find_or_create_group (refs, base, step);
 /* Prune the prefetch candidate REF using the self-reuse.  */
 static void
 prune_ref_by_self_reuse (struct mem_ref *ref)
 {
-HOST_WIDE_INT step = ref->group->step;
+HOST_WIDE_INT step;
-bool backward = step < 0;
+bool backward;
+/* If the step size is non constant, we cannot calculate prefetch_mod.  */
+if (!cst_and_fits_in_hwi (ref->group->step))
+return;
+step = int_cst_value (ref->group->step);
+backward = step < 0;
 if (step == 0)
 {
 /* Prefetch references to invariant address just once.  */
 ref->prefetch_before = 1;
 static void
 prune_ref_by_group_reuse (struct mem_ref *ref, struct mem_ref *by,
 			  bool by_is_before)
 {
-HOST_WIDE_INT step = ref->group->step;
+HOST_WIDE_INT step;
-bool backward = step < 0;
+bool backward;
 HOST_WIDE_INT delta_r = ref->delta, delta_b = by->delta;
 HOST_WIDE_INT delta = delta_b - delta_r;
 HOST_WIDE_INT hit_from;
 unsigned HOST_WIDE_INT prefetch_before, prefetch_block;
 int miss_rate;
 HOST_WIDE_INT reduced_step;
 unsigned HOST_WIDE_INT reduced_prefetch_block;
 tree ref_type;
 int align_unit;
+/* If the step is non constant we cannot calculate prefetch_before.  */
+if (!cst_and_fits_in_hwi (ref->group->step)) {
+return;
+}
+step = int_cst_value (ref->group->step);
+backward = step < 0;
 if (delta == 0)
 {
 /* If the references has the same address, only prefetch the
 	 former.  */
 if (by_is_before)
 {
 /* The accesses are sure to meet.  Let us check when.  */
 hit_from = ddown (delta_b, PREFETCH_BLOCK) * PREFETCH_BLOCK;
 prefetch_before = (hit_from - delta_r + step - 1) / step;
+/* Do not reduce prefetch_before if we meet beyond cache size.  */
+if (prefetch_before > (unsigned) abs (L2_CACHE_SIZE_BYTES / step))
+prefetch_before = PREFETCH_ALL;
 if (prefetch_before < ref->prefetch_before)
 	ref->prefetch_before = prefetch_before;
 return;
 }
 align_unit = TYPE_ALIGN (ref_type) / 8;
 miss_rate = compute_miss_rate(prefetch_block, step, delta,
 				reduced_prefetch_block, align_unit);
 if (miss_rate <= ACCEPTABLE_MISS_RATE)
 {
+/* Do not reduce prefetch_before if we meet beyond cache size.  */
+if (prefetch_before > L2_CACHE_SIZE_BYTES / PREFETCH_BLOCK)
+prefetch_before = PREFETCH_ALL;
 if (prefetch_before < ref->prefetch_before)
 	ref->prefetch_before = prefetch_before;
 return;
 }
 should_issue_prefetch_p (struct mem_ref *ref)
 {
 /* For now do not issue prefetches for only first few of the
 iterations.  */
 if (ref->prefetch_before != PREFETCH_ALL)
-return false;
+{
+if (dump_file && (dump_flags & TDF_DETAILS))
+fprintf (dump_file, "Ignoring %p due to prefetch_before\n",
+		 (void *) ref);
+return false;
+}
 /* Do not prefetch nontemporal stores.  */
 if (ref->storent_p)
-return false;
+{
+if (dump_file && (dump_flags & TDF_DETAILS))
+fprintf (dump_file, "Ignoring nontemporal store %p\n", (void *) ref);
+return false;
+}
 return true;
 }
 /* Decide which of the prefetch candidates in GROUPS to prefetch.
 for (ref = groups->refs; ref; ref = ref->next)
 {
 	if (!should_issue_prefetch_p (ref))
 	  continue;
+/* The loop is far from being sufficiently unrolled for this
+prefetch.  Do not generate prefetch to avoid many redudant
+prefetches.  */
+if (ref->prefetch_mod / unroll_factor > PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO)
+continue;
 	/* If we need to prefetch the reference each PREFETCH_MOD iterations,
 	   and we unroll the loop UNROLL_FACTOR times, we need to insert
 	   ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
 	   iteration.  */
 	n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
 static void
 issue_prefetch_ref (struct mem_ref *ref, unsigned unroll_factor, unsigned ahead)
 {
 HOST_WIDE_INT delta;
-tree addr, addr_base, write_p, local;
+tree addr, addr_base, write_p, local, forward;
 gimple prefetch;
 gimple_stmt_iterator bsi;
 unsigned n_prefetches, ap;
 bool nontemporal = ref->reuse_distance >= L2_CACHE_SIZE_BYTES;
 write_p = ref->write_p ? integer_one_node : integer_zero_node;
 local = build_int_cst (integer_type_node, nontemporal ? 0 : 3);
 for (ap = 0; ap < n_prefetches; ap++)
 {
-/* Determine the address to prefetch.  */
+if (cst_and_fits_in_hwi (ref->group->step))
-delta = (ahead + ap * ref->prefetch_mod) * ref->group->step;
+{
-addr = fold_build2 (POINTER_PLUS_EXPR, ptr_type_node,
+/* Determine the address to prefetch.  */
-			  addr_base, size_int (delta));
+delta = (ahead + ap * ref->prefetch_mod) *
-addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true, NULL,
+		   int_cst_value (ref->group->step);
-				       true, GSI_SAME_STMT);
+addr = fold_build2 (POINTER_PLUS_EXPR, ptr_type_node,
+addr_base, size_int (delta));
+addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true, NULL,
+true, GSI_SAME_STMT);
+}
+else
+{
+/* The step size is non-constant but loop-invariant.  We use the
+heuristic to simply prefetch ahead iterations ahead.  */
+forward = fold_build2 (MULT_EXPR, sizetype,
+fold_convert (sizetype, ref->group->step),
+fold_convert (sizetype, size_int (ahead)));
+addr = fold_build2 (POINTER_PLUS_EXPR, ptr_type_node, addr_base,
+			      forward);
+addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true,
+					   NULL, true, GSI_SAME_STMT);
+}
 /* Create the prefetch instruction.  */
 prefetch = gimple_build_call (built_in_decls[BUILT_IN_PREFETCH],
 				    3, addr, write_p, local);
 gsi_insert_before (&bsi, prefetch, GSI_SAME_STMT);
 }
 MEM_REF_COUNT: total number of memory references in the loop.  */
 static bool
 is_loop_prefetching_profitable (unsigned ahead, HOST_WIDE_INT est_niter,
 				unsigned ninsns, unsigned prefetch_count,
-				unsigned mem_ref_count)
+				unsigned mem_ref_count, unsigned unroll_factor)
 {
 int insn_to_mem_ratio, insn_to_prefetch_ratio;
 if (mem_ref_count == 0)
 return false;
 for each CPU or memory op in the loop. Time estimates for memory ops
 should account for cache misses.  */
 insn_to_mem_ratio = ninsns / mem_ref_count;
 if (insn_to_mem_ratio < PREFETCH_MIN_INSN_TO_MEM_RATIO)
-return false;
+{
+if (dump_file && (dump_flags & TDF_DETAILS))
-/* Profitability of prefetching is highly dependent on the trip count.
+fprintf (dump_file,
-For a given AHEAD distance, the first AHEAD iterations do not benefit
+		 "Not prefetching -- instruction to memory reference ratio (%d) too small\n",
-from prefetching, and the last AHEAD iterations execute useless
+		 insn_to_mem_ratio);
-prefetches.  So, if the trip count is not large enough relative to AHEAD,
+return false;
-prefetching may cause serious performance degradation.  To avoid this
+}
-problem when the trip count is not known at compile time, we
-conservatively skip loops with high prefetching costs.  For now, only
+/* Prefetching most likely causes performance degradation when the instruction
-the I-cache cost is considered.  The relative I-cache cost is estimated
+to prefetch ratio is too small.  Too many prefetch instructions in a loop
-by taking the ratio between the number of prefetches and the total
+may reduce the I-cache performance.
-number of instructions.  Since we are using integer arithmetic, we
+(unroll_factor * ninsns) is used to estimate the number of instructions in
-compute the reciprocal of this ratio.
+the unrolled loop.  This implementation is a bit simplistic -- the number
-TODO: Account for loop unrolling, which may reduce the costs of
+of issued prefetch instructions is also affected by unrolling.  So,
-shorter stride prefetches.  Note that not accounting for loop
+prefetch_mod and the unroll factor should be taken into account when
-unrolling over-estimates the cost and hence gives more conservative
+determining prefetch_count.  Also, the number of insns of the unrolled
-results.  */
+loop will usually be significantly smaller than the number of insns of the
+original loop * unroll_factor (at least the induction variable increases
+and the exit branches will get eliminated), so it might be better to use
+tree_estimate_loop_size + estimated_unrolled_size.  */
+insn_to_prefetch_ratio = (unroll_factor * ninsns) / prefetch_count;
+if (insn_to_prefetch_ratio < MIN_INSN_TO_PREFETCH_RATIO)
+{
+if (dump_file && (dump_flags & TDF_DETAILS))
+fprintf (dump_file,
+		 "Not prefetching -- instruction to prefetch ratio (%d) too small\n",
+		 insn_to_prefetch_ratio);
+return false;
+}
+/* Could not do further estimation if the trip count is unknown.  Just assume
+prefetching is profitable. Too aggressive???  */
 if (est_niter < 0)
-{
+return true;
-insn_to_prefetch_ratio = ninsns / prefetch_count;
-return insn_to_prefetch_ratio >= MIN_INSN_TO_PREFETCH_RATIO;
+if (est_niter < (HOST_WIDE_INT) (TRIP_COUNT_TO_AHEAD_RATIO * ahead))
-}
-if (est_niter <= (HOST_WIDE_INT) ahead)
 {
 if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
 		 "Not prefetching -- loop estimated to roll only %d times\n",
 		 (int) est_niter);
 	     HOST_WIDE_INT_PRINT_DEC "\n"
 	     "insn count %d, mem ref count %d, prefetch count %d\n",
 	     ahead, unroll_factor, est_niter,
 	     ninsns, mem_ref_count, prefetch_count);
-if (!is_loop_prefetching_profitable (ahead, est_niter, ninsns,
+if (!is_loop_prefetching_profitable (ahead, est_niter, ninsns, prefetch_count,
-				       prefetch_count, mem_ref_count))
+				       mem_ref_count, unroll_factor))
 goto fail;
 mark_nontemporal_stores (loop, refs);
 /* Step 4: what to prefetch?  */

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-loop-prefetch.c @ 63:b7f97abdc517 gcc-4.6-20100522