diff options
| -rw-r--r-- | gcc/ChangeLog | 26 | ||||
| -rw-r--r-- | gcc/cfgloop.h | 18 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 4 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/prefetch-5.c | 60 | ||||
| -rw-r--r-- | gcc/tree-data-ref.c | 32 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-niter.c | 191 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-prefetch.c | 8 |
7 files changed, 235 insertions, 104 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 0825b1b8439..520f824c6f5 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,31 @@ 2007-03-15 Zdenek Dvorak <dvorakz@suse.cz> + * tree-ssa-loop-niter.c (record_estimate): Add "upper" argument. + Update constant estimates of number of iterations. + (record_nonwrapping_iv): Add "upper" argument. "data_size_bounds_p" + argument renamed to "realistic". + (compute_estimated_nb_iterations): Removed. + (record_niter_bound): New function. + (idx_infer_loop_bounds): For possible but unlikely tail arrays, + call record_nonwrapping_iv with upper = false. + (infer_loop_bounds_from_signedness): Pass upper argument to + record_nonwrapping_iv. + (estimate_numbers_of_iterations_loop): Do not call + compute_estimated_nb_iterations. Record estimate based on profile + information. Initialize the constant estimates of number of + iterations. + * tree-data-ref.c (estimated_loop_iterations): Return the recorded + estimates. + * tree-ssa-loop-prefetch.c (loop_prefetch_arrays): Add dump when + number of iterations is too small. + * cfgloop.h (struct nb_iter_bound): Remove "realistic" field. + (EST_NOT_AVAILABLE): Removed. + (struct loop): Replace estimated_nb_iterations by any_upper_bound, + nb_iterations_upper_bound, any_estimate and nb_iterations_estimate + fields. + +2007-03-15 Zdenek Dvorak <dvorakz@suse.cz> + * tree-ssa-loop-niter.c (refine_bounds_using_guard, bound_difference): Handle NE_EXPR guards. diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index c6cd7221aa7..c5c1cf25b42 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -65,12 +65,6 @@ struct nb_iter_bound are executed at most BOUND times. */ bool is_exit; - /* True if the bound is "realistic" -- i.e., most likely the loop really has - number of iterations close to the bound. Exact bounds (if the number of - iterations of a loop is a constant) and bounds derived from the size of - data accessed in the loop are considered realistic. */ - bool realistic; - /* The next bound in the list. */ struct nb_iter_bound *next; }; @@ -148,12 +142,18 @@ struct loop { /* Estimate was not computed yet. */ EST_NOT_COMPUTED, - /* Estimate was computed, but we could derive no useful bound. */ - EST_NOT_AVAILABLE, /* Estimate is ready. */ EST_AVAILABLE } estimate_state; - double_int estimated_nb_iterations; + + /* An integer guaranteed to bound the number of iterations of the loop + from above. */ + bool any_upper_bound; + double_int nb_iterations_upper_bound; + + /* An integer giving the expected number of iterations of the loop. */ + bool any_estimate; + double_int nb_iterations_estimate; /* Upper bound on number of iterations of a loop. */ struct nb_iter_bound *bounds; diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index b56294f0df6..8e8b8e70884 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2007-03-15 Zdenek Dvorak <dvorakz@suse.cz> + + * gcc.dg/tree-ssa/prefetch-5.c: New test. + 2007-03-15 Manuel Lopez-Ibanez <manu@gcc.gnu.org> PR c++/30891 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/prefetch-5.c b/gcc/testsuite/gcc.dg/tree-ssa/prefetch-5.c new file mode 100644 index 00000000000..643ac8053e4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/prefetch-5.c @@ -0,0 +1,60 @@ +/* { dg-do compile { target i?86-*-* x86_64-*-* } } */ +/* { dg-require-effective-target ilp32 } */ +/* { dg-options "-O2 -fprefetch-loop-arrays -march=athlon -fdump-tree-aprefetch-details" } */ + +/* These are common idioms for writing variable-length arrays at the end + of structures. We should not deduce anything about the number of iterations + of the loops from them. */ + +struct tail0 +{ + int xxx; + int yyy[0]; +}; + +int loop0 (int n, struct tail0 *x) +{ + int i, s = 0; + + for (i = 0; i < n; i++) + s += x->yyy[i]; + + return s; +} + +struct tail1 +{ + int xxx; + int yyy[1]; +}; +int loop1 (int n, struct tail1 *x) +{ + int i, s = 0; + + for (i = 0; i < n; i++) + s += x->yyy[i]; + + return s; +} + +/* It is unlikely that this should be a tail array. We may deduce that most + likely, the loop iterates about 5 times, and the array is not worth prefetching. */ + +struct tail5 +{ + int xxx; + int yyy[5]; +}; +int loop5 (int n, struct tail5 *x) +{ + int i, s = 0; + + for (i = 0; i < n; i++) + s += x->yyy[i]; + + return s; +} + +/* { dg-final { scan-tree-dump-times "Issued prefetch" 2 "aprefetch" } } */ +/* { dg-final { scan-tree-dump-times "Not prefetching" 1 "aprefetch" } } */ +/* { dg-final { cleanup-tree-dump "aprefetch" } } */ diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index d59278c89f5..01bb71b5907 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -2556,33 +2556,23 @@ static bool estimated_loop_iterations (struct loop *loop, bool conservative, double_int *nit) { - tree numiter = number_of_exit_cond_executions (loop); - - /* If we have an exact value, use it. */ - if (TREE_CODE (numiter) == INTEGER_CST) + estimate_numbers_of_iterations_loop (loop); + if (conservative) { - *nit = tree_to_double_int (numiter); - return true; - } + if (!loop->any_upper_bound) + return false; - /* If we have a measured profile and we do not ask for a conservative bound, - use it. */ - if (!conservative && loop->header->count != 0) - { - *nit = uhwi_to_double_int (expected_loop_iterations (loop) + 1); - return true; + *nit = loop->nb_iterations_upper_bound; } - - /* Finally, try using a reliable estimate on number of iterations according - to the size of the accessed data, if available. */ - estimate_numbers_of_iterations_loop (loop); - if (loop->estimate_state == EST_AVAILABLE) + else { - *nit = loop->estimated_nb_iterations; - return true; + if (!loop->any_estimate) + return false; + + *nit = loop->nb_iterations_estimate; } - return false; + return true; } /* Similar to estimated_loop_iterations, but returns the estimate only diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 688bc3910f6..909f5fcd30a 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -2386,46 +2386,110 @@ derive_constant_upper_bound (tree val) } } +/* Records that every statement in LOOP is executed I_BOUND times. + REALISTIC is true if I_BOUND is expected to be close the the real number + of iterations. UPPER is true if we are sure the loop iterates at most + I_BOUND times. */ + +static void +record_niter_bound (struct loop *loop, double_int i_bound, bool realistic, + bool upper) +{ + /* Update the bounds only when there is no previous estimation, or when the current + estimation is smaller. */ + if (upper + && (!loop->any_upper_bound + || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0)) + { + loop->any_upper_bound = true; + loop->nb_iterations_upper_bound = i_bound; + } + if (realistic + && (!loop->any_estimate + || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0)) + { + loop->any_estimate = true; + loop->nb_iterations_estimate = i_bound; + } +} + /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT is true if the loop is exited immediately after STMT, and this exit is taken at last when the STMT is executed BOUND + 1 times. - REALISTIC is true if the estimate comes from a reliable source - (number of iterations analysis, or size of data accessed in the loop). - I_BOUND is an unsigned double_int upper estimate on BOUND. */ + REALISTIC is true if BOUND is expected to be close the the real number + of iterations. UPPER is true if we are sure the loop iterates at most + BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */ static void record_estimate (struct loop *loop, tree bound, double_int i_bound, - tree at_stmt, bool is_exit, bool realistic) + tree at_stmt, bool is_exit, bool realistic, bool upper) { - struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound)); + double_int delta; + edge exit; if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : ""); print_generic_expr (dump_file, at_stmt, TDF_SLIM); - fprintf (dump_file, " is executed at most "); + fprintf (dump_file, " is %sexecuted at most ", + upper ? "" : "probably "); print_generic_expr (dump_file, bound, TDF_SLIM); fprintf (dump_file, " (bounded by "); dump_double_int (dump_file, i_bound, true); fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num); } - elt->bound = i_bound; - elt->stmt = at_stmt; - elt->is_exit = is_exit; - elt->realistic = realistic && TREE_CODE (bound) == INTEGER_CST; - elt->next = loop->bounds; - loop->bounds = elt; + /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the + real number of iterations. */ + if (TREE_CODE (bound) != INTEGER_CST) + realistic = false; + if (!upper && !realistic) + return; + + /* If we have a guaranteed upper bound, record it in the appropriate + list. */ + if (upper) + { + struct nb_iter_bound *elt = XNEW (struct nb_iter_bound); + + elt->bound = i_bound; + elt->stmt = at_stmt; + elt->is_exit = is_exit; + elt->next = loop->bounds; + loop->bounds = elt; + } + + /* Update the number of iteration estimates according to the bound. + If at_stmt is an exit, then every statement in the loop is + executed at most BOUND + 1 times. If it is not an exit, then + some of the statements before it could be executed BOUND + 2 + times, if an exit of LOOP is before stmt. */ + exit = single_exit (loop); + if (is_exit + || (exit != NULL + && dominated_by_p (CDI_DOMINATORS, + exit->src, bb_for_stmt (at_stmt)))) + delta = double_int_one; + else + delta = double_int_two; + i_bound = double_int_add (i_bound, delta); + + /* If an overflow occured, ignore the result. */ + if (double_int_ucmp (i_bound, delta) < 0) + return; + + record_niter_bound (loop, i_bound, realistic, upper); } /* Record the estimate on number of iterations of LOOP based on the fact that the induction variable BASE + STEP * i evaluated in STMT does not wrap and - its values belong to the range <LOW, HIGH>. DATA_SIZE_BOUNDS_P is true if - LOW and HIGH are derived from the size of data. */ + its values belong to the range <LOW, HIGH>. REALISTIC is true if the + estimated number of iterations is expected to be close to the real one. + UPPER is true if we are sure the induction variable does not wrap. */ static void record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt, - tree low, tree high, bool data_size_bounds_p) + tree low, tree high, bool realistic, bool upper) { tree niter_bound, extreme, delta; tree type = TREE_TYPE (base), unsigned_type; @@ -2471,55 +2535,7 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt, would get out of the range. */ niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step); max = derive_constant_upper_bound (niter_bound); - record_estimate (loop, niter_bound, max, stmt, false, data_size_bounds_p); -} - -/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe - approximation of the number of iterations for LOOP. */ - -static void -compute_estimated_nb_iterations (struct loop *loop) -{ - struct nb_iter_bound *bound; - double_int bnd_val, delta; - edge exit; - - gcc_assert (loop->estimate_state == EST_NOT_AVAILABLE); - - for (bound = loop->bounds; bound; bound = bound->next) - { - if (!bound->realistic) - continue; - - bnd_val = bound->bound; - /* If bound->stmt is an exit, then every statement in the loop is - executed at most BND_VAL + 1 times. If it is not an exit, then - some of the statements before it could be executed BND_VAL + 2 - times, if an exit of LOOP is before stmt. */ - exit = single_exit (loop); - - if (bound->is_exit - || (exit != NULL - && dominated_by_p (CDI_DOMINATORS, - exit->src, bb_for_stmt (bound->stmt)))) - delta = double_int_one; - else - delta = double_int_two; - bnd_val = double_int_add (bnd_val, delta); - - /* If an overflow occured, ignore the result. */ - if (double_int_ucmp (bnd_val, delta) < 0) - continue; - - /* Update only when there is no previous estimation, or when the current - estimation is smaller. */ - if (loop->estimate_state == EST_NOT_AVAILABLE - || double_int_ucmp (bnd_val, loop->estimated_nb_iterations) < 0) - { - loop->estimate_state = EST_AVAILABLE; - loop->estimated_nb_iterations = bnd_val; - } - } + record_estimate (loop, niter_bound, max, stmt, false, realistic, upper); } /* Returns true if REF is a reference to an array at the end of a dynamically @@ -2579,13 +2595,18 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta) struct ilb_data *data = dta; tree ev, init, step; tree low, high, type, next; - bool sign; + bool sign, upper = true; struct loop *loop = data->loop; - if (TREE_CODE (base) != ARRAY_REF - || array_at_struct_end_p (base)) + if (TREE_CODE (base) != ARRAY_REF) return true; + /* For arrays at the end of the structure, we are not guaranteed that they + do not really extend over their declared size. However, for arrays of + size greater than one, this is unlikely to be intended. */ + if (array_at_struct_end_p (base)) + upper = false; + ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx)); init = initial_condition (ev); step = evolution_part_in_loop_num (ev, loop->num); @@ -2609,7 +2630,13 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta) return true; sign = tree_int_cst_sign_bit (step); type = TREE_TYPE (step); - + + /* The array of length 1 at the end of a structure most likely extends + beyond its bounds. */ + if (!upper + && operand_equal_p (low, high, 0)) + return true; + /* In case the relevant bound of the array does not fit in type, or it does, but bound + step (in type) still belongs into the range of the array, the index may wrap and still stay within the range of the array @@ -2633,7 +2660,7 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta) && tree_int_cst_compare (next, high) <= 0) return true; - record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true); + record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper); return true; } @@ -2722,7 +2749,7 @@ infer_loop_bounds_from_signedness (struct loop *loop, tree stmt) low = lower_bound_in_type (type, type); high = upper_bound_in_type (type, type); - record_nonwrapping_iv (loop, base, step, stmt, low, high, false); + record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true); } /* The following analyzers are extracting informations on the bounds @@ -2776,11 +2803,14 @@ estimate_numbers_of_iterations_loop (struct loop *loop) unsigned i; struct tree_niter_desc niter_desc; edge ex; + double_int bound; /* Give up if we already have tried to compute an estimation. */ if (loop->estimate_state != EST_NOT_COMPUTED) return; - loop->estimate_state = EST_NOT_AVAILABLE; + loop->estimate_state = EST_AVAILABLE; + loop->any_upper_bound = false; + loop->any_estimate = false; exits = get_loop_exit_edges (loop); for (i = 0; VEC_iterate (edge, exits, i, ex); i++) @@ -2796,12 +2826,27 @@ estimate_numbers_of_iterations_loop (struct loop *loop) niter); record_estimate (loop, niter, niter_desc.max, last_stmt (ex->src), - true, true); + true, true, true); } VEC_free (edge, heap, exits); infer_loop_bounds_from_undefined (loop); - compute_estimated_nb_iterations (loop); + + /* If we have a measured profile, use it to estimate the number of + iterations. */ + if (loop->header->count != 0) + { + bound = uhwi_to_double_int (expected_loop_iterations (loop) + 1); + record_niter_bound (loop, bound, true, false); + } + + /* If an upper bound is smaller than the realistic estimate of the + number of iterations, use the upper bound instead. */ + if (loop->any_upper_bound + && loop->any_estimate + && double_int_ucmp (loop->nb_iterations_upper_bound, + loop->nb_iterations_estimate) < 0) + loop->nb_iterations_estimate = loop->nb_iterations_upper_bound; } /* Records estimates on numbers of iterations of loops. */ diff --git a/gcc/tree-ssa-loop-prefetch.c b/gcc/tree-ssa-loop-prefetch.c index 53977d8bddd..a0d70cc382f 100644 --- a/gcc/tree-ssa-loop-prefetch.c +++ b/gcc/tree-ssa-loop-prefetch.c @@ -968,7 +968,13 @@ loop_prefetch_arrays (struct loop *loop) the loop rolls at least AHEAD times, prefetching the references does not make sense. */ if (est_niter >= 0 && est_niter <= (HOST_WIDE_INT) ahead) - goto fail; + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Not prefetching -- loop estimated to roll only %d times\n", + (int) est_niter); + goto fail; + } ninsns = tree_num_loop_insns (loop, &eni_size_weights); unroll_factor = determine_unroll_factor (loop, refs, ninsns, &desc, |