diff options
| -rw-r--r-- | gcc/ChangeLog | 17 | ||||
| -rw-r--r-- | gcc/cfgloop.h | 2 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 6 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.c-torture/execute/20100827-1.c | 23 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/vrp54.c | 34 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/vect/vect-outer-fir.c | 7 | ||||
| -rw-r--r-- | gcc/tree-data-ref.c | 2 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 2 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-niter.c | 14 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop.c | 2 | ||||
| -rw-r--r-- | gcc/tree-vrp.c | 192 |
11 files changed, 202 insertions, 99 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 355d4ea..2afb420 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,20 @@ +2010-09-01 Richard Guenther <rguenther@suse.de> + + * tree-vrp.c (adjust_range_with_scev): Use number of iteration + estimate. + (vrp_visit_phi_node): Delay using SCEV till we balloon the + range. + (execute_vrp): Compute number of iteration estimates. + * cfgloop.h (estimate_numbers_of_iterations_loop): Adjust prototype. + * tree-flow.h (estimate_numbers_of_iterations): Likewise. + * tree-data-ref.c (estimated_loop_iterations): Adjust. + * tree-ssa-loop-niter.c (estimate_numbers_of_iterations_loop): + Infer loop bounds from undefined behavior based on a new + parameter. + (estimate_numbers_of_iterations): Likewise. + (scev_probably_wraps_p): Adjust. + * tree-ssa-loop.c (tree_ssa_loop_bounds): Likewise. + 2010-09-01 Nick Clifton <nickc@redhat.com> * config/stormy16/stormy16.c: Use REG_P, MEM_P and CONST_INT_P diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 722aa33..bf2614e 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -276,7 +276,7 @@ gcov_type expected_loop_iterations_unbounded (const struct loop *); extern unsigned expected_loop_iterations (const struct loop *); extern rtx doloop_condition_get (rtx); -void estimate_numbers_of_iterations_loop (struct loop *); +void estimate_numbers_of_iterations_loop (struct loop *, bool); HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool); bool estimated_loop_iterations (struct loop *, bool, double_int *); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 3acadbc..67f5a20 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2010-09-01 Richard Guenther <rguenther@suse.de> + + * gcc.dg/vect/vect-outer-fir.c: Adjust. + * gcc.dg/tree-ssa/vrp54.c: New testcase. + * gcc.c-torture/execute/20100827-1.c: Likewise. + 2010-09-01 Francois-Xavier Coudert <fxcoudert@gcc.gnu.org> * gfortran.dg/execute_command_line_1.f90: New test. diff --git a/gcc/testsuite/gcc.c-torture/execute/20100827-1.c b/gcc/testsuite/gcc.c-torture/execute/20100827-1.c new file mode 100644 index 0000000..8a531b9 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/20100827-1.c @@ -0,0 +1,23 @@ +extern void abort (void); +int __attribute__((noinline,noclone)) +foo (char *p) +{ + int h = 0; + do + { + if (*p == '\0') + break; + ++h; + if (p == 0) + abort (); + ++p; + } + while (1); + return h; +} +int main() +{ + if (foo("a") != 1) + abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp54.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp54.c new file mode 100644 index 0000000..6e8da77 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp54.c @@ -0,0 +1,34 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-vrp1" } */ + +extern void link_error (void); +void foo (void) +{ + int j = 256; + do + { + if (j < 0 || j > 256) + link_error (); + j--; + } + while (j >= 0); + if (j != -1) + link_error (); +} +extern void link_error (void); +void bar (void) +{ + int j = 0; + do + { + if (j < 0 || j > 256) + link_error (); + j++; + } + while (j <= 256); + if (j != 257) + link_error (); +} + +/* { dg-final { scan-tree-dump-not "link_error" "vrp1" } } */ +/* { dg-final { cleanup-tree-dump "vrp1" } } */ diff --git a/gcc/testsuite/gcc.dg/vect/vect-outer-fir.c b/gcc/testsuite/gcc.dg/vect/vect-outer-fir.c index 30a1c15..af787b9 100644 --- a/gcc/testsuite/gcc.dg/vect/vect-outer-fir.c +++ b/gcc/testsuite/gcc.dg/vect/vect-outer-fir.c @@ -11,10 +11,6 @@ float out[N]; float fir_out[N]; /* Should be vectorized. Fixed misaligment in the inner-loop. */ -/* Currently not vectorized because we get too many BBs in the inner-loop, - because the compiler doesn't realize that the inner-loop executes at - least once (cause k<4), and so there's no need to create a guard code - to skip the inner-loop in case it doesn't execute. */ __attribute__ ((noinline)) void foo (){ int i,j,k; @@ -74,6 +70,5 @@ int main (void) return 0; } -/* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 2 "vect" { xfail *-*-* } } } */ -/* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 1 "vect" { xfail vect_no_align } } } */ +/* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 2 "vect" { xfail vect_no_align } } } */ /* { dg-final { cleanup-tree-dump "vect" } } */ diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 025368d..ee181a6 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1716,7 +1716,7 @@ bool estimated_loop_iterations (struct loop *loop, bool conservative, double_int *nit) { - estimate_numbers_of_iterations_loop (loop); + estimate_numbers_of_iterations_loop (loop, true); if (conservative) { if (!loop->any_upper_bound) diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 6731308..6b16234 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -684,7 +684,7 @@ bool number_of_iterations_exit (struct loop *, edge, tree find_loop_niter (struct loop *, edge *); tree loop_niter_by_eval (struct loop *, edge); tree find_loop_niter_by_eval (struct loop *, edge *); -void estimate_numbers_of_iterations (void); +void estimate_numbers_of_iterations (bool); bool array_at_struct_end_p (tree); bool scev_probably_wraps_p (tree, tree, gimple, struct loop *, bool); bool convert_affine_scev (struct loop *, tree, tree *, tree *, gimple, bool); diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 2118b97..94d150d 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -2933,10 +2933,11 @@ gcov_type_to_double_int (gcov_type val) return ret; } -/* Records estimates on numbers of iterations of LOOP. */ +/* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P + is true also use estimates derived from undefined behavior. */ void -estimate_numbers_of_iterations_loop (struct loop *loop) +estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p) { VEC (edge, heap) *exits; tree niter, type; @@ -2970,7 +2971,8 @@ estimate_numbers_of_iterations_loop (struct loop *loop) } VEC_free (edge, heap, exits); - infer_loop_bounds_from_undefined (loop); + if (use_undefined_p) + infer_loop_bounds_from_undefined (loop); /* If we have a measured profile, use it to estimate the number of iterations. */ @@ -2993,7 +2995,7 @@ estimate_numbers_of_iterations_loop (struct loop *loop) /* Records estimates on numbers of iterations of loops. */ void -estimate_numbers_of_iterations (void) +estimate_numbers_of_iterations (bool use_undefined_p) { loop_iterator li; struct loop *loop; @@ -3004,7 +3006,7 @@ estimate_numbers_of_iterations (void) FOR_EACH_LOOP (li, loop, 0) { - estimate_numbers_of_iterations_loop (loop); + estimate_numbers_of_iterations_loop (loop, use_undefined_p); } fold_undefer_and_ignore_overflow_warnings (); @@ -3200,7 +3202,7 @@ scev_probably_wraps_p (tree base, tree step, valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs); - estimate_numbers_of_iterations_loop (loop); + estimate_numbers_of_iterations_loop (loop, true); for (bound = loop->bounds; bound; bound = bound->next) { if (n_of_executions_at_most (at_stmt, bound, valid_niter)) diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c index 9523dab..a62098a 100644 --- a/gcc/tree-ssa-loop.c +++ b/gcc/tree-ssa-loop.c @@ -458,7 +458,7 @@ tree_ssa_loop_bounds (void) if (number_of_loops () <= 1) return 0; - estimate_numbers_of_iterations (); + estimate_numbers_of_iterations (true); scev_reset (); return 0; } diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index c5f1468..c005c53 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -3382,6 +3382,38 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, else tmax = TYPE_MAX_VALUE (type); + /* Try to use estimated number of iterations for the loop to constrain the + final value in the evolution. + We are interested in the number of executions of the latch, while + nb_iterations_upper_bound includes the last execution of the exit test. */ + if (TREE_CODE (step) == INTEGER_CST + && loop->any_upper_bound + && !double_int_zero_p (loop->nb_iterations_upper_bound) + && is_gimple_val (init) + && (TREE_CODE (init) != SSA_NAME + || get_value_range (init)->type == VR_RANGE)) + { + value_range_t maxvr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; + double_int dtmp; + dtmp = double_int_mul (tree_to_double_int (step), + double_int_sub (loop->nb_iterations_upper_bound, + double_int_one)); + tem = double_int_to_tree (TREE_TYPE (init), dtmp); + /* If the multiplication overflowed we can't do a meaningful + adjustment. */ + if (double_int_equal_p (dtmp, tree_to_double_int (tem))) + { + extract_range_from_binary_expr (&maxvr, PLUS_EXPR, + TREE_TYPE (init), init, tem); + /* Likewise if the addition did. */ + if (maxvr.type == VR_RANGE) + { + tmin = maxvr.min; + tmax = maxvr.max; + } + } + } + if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) { min = tmin; @@ -3414,40 +3446,35 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, /* INIT is the maximum value. If INIT is lower than VR->MAX but no smaller than VR->MIN, set VR->MAX to INIT. */ if (compare_values (init, max) == -1) - { - max = init; - - /* If we just created an invalid range with the minimum - greater than the maximum, we fail conservatively. - This should happen only in unreachable - parts of code, or for invalid programs. */ - if (compare_values (min, max) == 1) - return; - } + max = init; /* According to the loop information, the variable does not overflow. If we think it does, probably because of an overflow due to arithmetic on a different INF value, reset now. */ - if (is_negative_overflow_infinity (min)) + if (is_negative_overflow_infinity (min) + || compare_values (min, tmin) == -1) min = tmin; + } else { /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */ if (compare_values (init, min) == 1) - { - min = init; - - /* Again, avoid creating invalid range by failing. */ - if (compare_values (min, max) == 1) - return; - } + min = init; - if (is_positive_overflow_infinity (max)) + if (is_positive_overflow_infinity (max) + || compare_values (tmax, max) == -1) max = tmax; } + /* If we just created an invalid range with the minimum + greater than the maximum, we fail conservatively. + This should happen only in unreachable + parts of code, or for invalid programs. */ + if (compare_values (min, max) == 1) + return; + set_value_range (vr, VR_RANGE, min, max, vr->equiv); } } @@ -6509,8 +6536,6 @@ vrp_visit_phi_node (gimple phi) int edges, old_edges; struct loop *l; - copy_value_range (&vr_result, lhs_vr); - if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "\nVisiting PHI node: "); @@ -6571,13 +6596,6 @@ vrp_visit_phi_node (gimple phi) } } - /* If this is a loop PHI node SCEV may known more about its - value-range. */ - if (current_loops - && (l = loop_containing_stmt (phi)) - && l->header == gimple_bb (phi)) - adjust_range_with_scev (&vr_result, l, phi, lhs); - if (vr_result.type == VR_VARYING) goto varying; @@ -6589,61 +6607,63 @@ vrp_visit_phi_node (gimple phi) previous one. We don't do this if we have seen a new executable edge; this helps us avoid an overflow infinity for conditionals which are not in a loop. */ - if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE - && edges <= old_edges) - { - if (!POINTER_TYPE_P (TREE_TYPE (lhs))) - { - int cmp_min = compare_values (lhs_vr->min, vr_result.min); - int cmp_max = compare_values (lhs_vr->max, vr_result.max); - - /* If the new minimum is smaller or larger than the previous - one, go all the way to -INF. In the first case, to avoid - iterating millions of times to reach -INF, and in the - other case to avoid infinite bouncing between different - minimums. */ - if (cmp_min > 0 || cmp_min < 0) - { - /* If we will end up with a (-INF, +INF) range, set it to - VARYING. Same if the previous max value was invalid for - the type and we'd end up with vr_result.min > vr_result.max. */ - if (vrp_val_is_max (vr_result.max) - || compare_values (TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)), - vr_result.max) > 0) - goto varying; - - if (!needs_overflow_infinity (TREE_TYPE (vr_result.min)) - || !vrp_var_may_overflow (lhs, phi)) - vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); - else if (supports_overflow_infinity (TREE_TYPE (vr_result.min))) - vr_result.min = - negative_overflow_infinity (TREE_TYPE (vr_result.min)); - else - goto varying; - } - - /* Similarly, if the new maximum is smaller or larger than - the previous one, go all the way to +INF. */ - if (cmp_max < 0 || cmp_max > 0) - { - /* If we will end up with a (-INF, +INF) range, set it to - VARYING. Same if the previous min value was invalid for - the type and we'd end up with vr_result.max < vr_result.min. */ - if (vrp_val_is_min (vr_result.min) - || compare_values (TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)), - vr_result.min) < 0) - goto varying; - - if (!needs_overflow_infinity (TREE_TYPE (vr_result.max)) - || !vrp_var_may_overflow (lhs, phi)) - vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)); - else if (supports_overflow_infinity (TREE_TYPE (vr_result.max))) - vr_result.max = - positive_overflow_infinity (TREE_TYPE (vr_result.max)); - else - goto varying; - } - } + if (edges > 0 + && edges == old_edges) + { + int cmp_min = compare_values (lhs_vr->min, vr_result.min); + int cmp_max = compare_values (lhs_vr->max, vr_result.max); + + /* For non VR_RANGE or for pointers fall back to varying if + the range changed. */ + if ((lhs_vr->type != VR_RANGE || vr_result.type != VR_RANGE + || POINTER_TYPE_P (TREE_TYPE (lhs))) + && (cmp_min != 0 || cmp_max != 0)) + goto varying; + + /* If the new minimum is smaller or larger than the previous + one, go all the way to -INF. In the first case, to avoid + iterating millions of times to reach -INF, and in the + other case to avoid infinite bouncing between different + minimums. */ + if (cmp_min > 0 || cmp_min < 0) + { + if (!needs_overflow_infinity (TREE_TYPE (vr_result.min)) + || !vrp_var_may_overflow (lhs, phi)) + vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); + else if (supports_overflow_infinity (TREE_TYPE (vr_result.min))) + vr_result.min = + negative_overflow_infinity (TREE_TYPE (vr_result.min)); + } + + /* Similarly, if the new maximum is smaller or larger than + the previous one, go all the way to +INF. */ + if (cmp_max < 0 || cmp_max > 0) + { + if (!needs_overflow_infinity (TREE_TYPE (vr_result.max)) + || !vrp_var_may_overflow (lhs, phi)) + vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)); + else if (supports_overflow_infinity (TREE_TYPE (vr_result.max))) + vr_result.max = + positive_overflow_infinity (TREE_TYPE (vr_result.max)); + } + + /* If we dropped either bound to +-INF then if this is a loop + PHI node SCEV may known more about its value-range. */ + if ((cmp_min > 0 || cmp_min < 0 + || cmp_max < 0 || cmp_max > 0) + && current_loops + && (l = loop_containing_stmt (phi)) + && l->header == gimple_bb (phi)) + adjust_range_with_scev (&vr_result, l, phi, lhs); + + /* If we will end up with a (-INF, +INF) range, set it to + VARYING. Same if the previous max value was invalid for + the type and we end up with vr_result.min > vr_result.max. */ + if ((vrp_val_is_max (vr_result.max) + && vrp_val_is_min (vr_result.min)) + || compare_values (vr_result.min, + vr_result.max) > 0) + goto varying; } /* If the new range is different than the previous value, keep @@ -7650,6 +7670,12 @@ execute_vrp (void) rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); scev_initialize (); + /* Estimate number of iterations - but do not use undefined behavior + for this. We can't do this lazily as other functions may compute + this using undefined behavior. */ + free_numbers_of_iterations_estimates (); + estimate_numbers_of_iterations (false); + insert_range_assertions (); to_remove_edges = VEC_alloc (edge, heap, 10); |