From 5f1fab5819256a0a30779d8d0c2fffc3ed2ee9c2 Mon Sep 17 00:00:00 2001 From: Richard Guenther Date: Thu, 12 Apr 2012 11:38:47 +0000 Subject: [PATCH] re PR tree-optimization/52943 (likely wrong code bug caused by predictive commoning) 2012-04-12 Richard Guenther PR tree-optimization/52943 * tree-chrec.h (chrec_is_positive): Remove. * tree-scalar-evolution.c (chrec_is_positive): Move ... * tree-data-ref.c (chrec_is_positive): ... here. Make static. Return false for a constant zero instead of negative. (analyze_siv_subscript_cst_affine): Handle zero difference in the initial condition explicitely. * gcc.dg/torture/pr52943.c: New testcase. From-SVN: r186374 --- gcc/ChangeLog | 10 ++++ gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/torture/pr52943.c | 20 +++++++ gcc/tree-chrec.h | 1 - gcc/tree-data-ref.c | 79 ++++++++++++++++++++++++++ gcc/tree-scalar-evolution.c | 59 ------------------- 6 files changed, 114 insertions(+), 60 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/torture/pr52943.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 7891046da8f..e6ece42cb58 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,13 @@ +2012-04-12 Richard Guenther + + PR tree-optimization/52943 + * tree-chrec.h (chrec_is_positive): Remove. + * tree-scalar-evolution.c (chrec_is_positive): Move ... + * tree-data-ref.c (chrec_is_positive): ... here. Make static. + Return false for a constant zero instead of negative. + (analyze_siv_subscript_cst_affine): Handle zero difference + in the initial condition explicitely. + 2012-04-12 Richard Guenther * tree-parloops.c (parallelize_loops): Also consult the upper diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 67c709983c3..8ebc0860da0 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2012-04-12 Richard Guenther + + PR tree-optimization/52943 + * gcc.dg/torture/pr52943.c: New testcase. + 2012-04-12 Oleg Endo PR target/50751 diff --git a/gcc/testsuite/gcc.dg/torture/pr52943.c b/gcc/testsuite/gcc.dg/torture/pr52943.c new file mode 100644 index 00000000000..da35c9d184b --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr52943.c @@ -0,0 +1,20 @@ +/* { dg-do run } */ + +extern void abort (void); +int a[] = { 0, 0, 0, 6 }; + +int b; +int +main () +{ + for (;;) + { + b = 3; + for (; b; b -= 1) + a[b] = a[3] > 1; + break; + } + if (a[1] != 0) + abort (); + return 0; +} diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h index bf9bff0f999..83678026752 100644 --- a/gcc/tree-chrec.h +++ b/gcc/tree-chrec.h @@ -77,7 +77,6 @@ extern void for_each_scev_op (tree *, bool (*) (tree *, void *), void *); /* Observers. */ extern bool eq_evolutions_p (const_tree, const_tree); extern bool is_multivariate_chrec (const_tree); -extern bool chrec_is_positive (tree, bool *); extern bool chrec_contains_symbols (const_tree); extern bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned); extern bool chrec_contains_undetermined (const_tree); diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index c4e78f3fe6e..1381b535bd3 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1718,6 +1718,76 @@ max_stmt_executions_tree (struct loop *loop) return double_int_to_tree (unsigned_type_node, nit); } +/* Determine whether the CHREC is always positive/negative. If the expression + cannot be statically analyzed, return false, otherwise set the answer into + VALUE. */ + +static bool +chrec_is_positive (tree chrec, bool *value) +{ + bool value0, value1, value2; + tree end_value, nb_iter; + + switch (TREE_CODE (chrec)) + { + case POLYNOMIAL_CHREC: + if (!chrec_is_positive (CHREC_LEFT (chrec), &value0) + || !chrec_is_positive (CHREC_RIGHT (chrec), &value1)) + return false; + + /* FIXME -- overflows. */ + if (value0 == value1) + { + *value = value0; + return true; + } + + /* Otherwise the chrec is under the form: "{-197, +, 2}_1", + and the proof consists in showing that the sign never + changes during the execution of the loop, from 0 to + loop->nb_iterations. */ + if (!evolution_function_is_affine_p (chrec)) + return false; + + nb_iter = number_of_latch_executions (get_chrec_loop (chrec)); + if (chrec_contains_undetermined (nb_iter)) + return false; + +#if 0 + /* TODO -- If the test is after the exit, we may decrease the number of + iterations by one. */ + if (after_exit) + nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1)); +#endif + + end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter); + + if (!chrec_is_positive (end_value, &value2)) + return false; + + *value = value0; + return value0 == value1; + + case INTEGER_CST: + switch (tree_int_cst_sgn (chrec)) + { + case -1: + *value = false; + break; + case 1: + *value = true; + break; + default: + return false; + } + return true; + + default: + return false; + } +} + + /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a constant, and CHREC_B is an affine function. *OVERLAPS_A and *OVERLAPS_B are initialized to the functions that describe the @@ -1741,6 +1811,15 @@ analyze_siv_subscript_cst_affine (tree chrec_a, chrec_b = chrec_convert (type, chrec_b, NULL); difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a); + /* Special case overlap in the first iteration. */ + if (integer_zerop (difference)) + { + *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); + *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node)); + *last_conflicts = integer_one_node; + return; + } + if (!chrec_is_positive (initial_condition (difference), &value0)) { if (dump_file && (dump_flags & TDF_DETAILS)) diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index c6631b856b8..21d1fd0a4a1 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -501,65 +501,6 @@ compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) return chrec_dont_know; } -/* Determine whether the CHREC is always positive/negative. If the expression - cannot be statically analyzed, return false, otherwise set the answer into - VALUE. */ - -bool -chrec_is_positive (tree chrec, bool *value) -{ - bool value0, value1, value2; - tree end_value, nb_iter; - - switch (TREE_CODE (chrec)) - { - case POLYNOMIAL_CHREC: - if (!chrec_is_positive (CHREC_LEFT (chrec), &value0) - || !chrec_is_positive (CHREC_RIGHT (chrec), &value1)) - return false; - - /* FIXME -- overflows. */ - if (value0 == value1) - { - *value = value0; - return true; - } - - /* Otherwise the chrec is under the form: "{-197, +, 2}_1", - and the proof consists in showing that the sign never - changes during the execution of the loop, from 0 to - loop->nb_iterations. */ - if (!evolution_function_is_affine_p (chrec)) - return false; - - nb_iter = number_of_latch_executions (get_chrec_loop (chrec)); - if (chrec_contains_undetermined (nb_iter)) - return false; - -#if 0 - /* TODO -- If the test is after the exit, we may decrease the number of - iterations by one. */ - if (after_exit) - nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1)); -#endif - - end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter); - - if (!chrec_is_positive (end_value, &value2)) - return false; - - *value = value0; - return value0 == value1; - - case INTEGER_CST: - *value = (tree_int_cst_sgn (chrec) == 1); - return true; - - default: - return false; - } -} - /* Associate CHREC to SCALAR. */ static void -- 2.30.2