[4.1 PATCH] Fix recently introduced number of loop iterations regression (PR tree-optimization/27285)
Jakub Jelinek
jakub@redhat.com
Tue Apr 25 17:36:00 GMT 2006
Hi!
This backport fixes a recently introduced regression on gcc-4_1-branch
(by
2006-04-04 Paul Brook <paul@codesourcery.com>
Backport form mainline.
2006-01-14 Zdenek Dvorak <dvorakz@suse.cz>
...
). Bootstrapped/regtested on 7 linux arches.
Ok for 4.1? Is the testcase ok for trunk as well (apparently
the PR25985 fix didn't come with any testcase)?
2006-04-25 Jakub Jelinek <jakub@redhat.com>
PR tree-optimization/27285
Backport from mainline:
2006-03-28 Zdenek Dvorak <dvorakz@suse.cz>
PR tree-optimization/25985
* tree-ssa-loop-niter.c (number_of_iterations_le,
number_of_iterations_ne): Make comments more precise.
(number_of_iterations_cond): Add only_exit argument. Use the
fact that signed variables do not overflow only when only_exit
is true.
(loop_only_exit_p): New.
(number_of_iterations_exit): Pass result of loop_only_exit_p to
number_of_iterations_cond.
* gcc.c-torture/execute/pr27285.c: New test.
--- gcc/tree-ssa-loop-niter.c (revision 112483)
+++ gcc/tree-ssa-loop-niter.c (revision 112484)
@@ -129,9 +129,9 @@ inverse (tree x, tree mask)
/* Determines number of iterations of loop whose ending condition
is IV <> FINAL. TYPE is the type of the iv. The number of
iterations is stored to NITER. NEVER_INFINITE is true if
- we know that the loop cannot be infinite (we derived this
- earlier, and possibly set NITER->assumptions to make sure this
- is the case. */
+ we know that the exit must be taken eventually, i.e., that the IV
+ ever reaches the value FINAL (we derived this earlier, and possibly set
+ NITER->assumptions to make sure this is the case). */
static bool
number_of_iterations_ne (tree type, affine_iv *iv, tree final,
@@ -492,9 +492,9 @@ number_of_iterations_lt (tree type, affi
/* Determines number of iterations of loop whose ending condition
is IV0 <= IV1. TYPE is the type of the iv. The number of
iterations is stored to NITER. NEVER_INFINITE is true if
- we know that the loop cannot be infinite (we derived this
+ we know that this condition must eventually become false (we derived this
earlier, and possibly set NITER->assumptions to make sure this
- is the case. */
+ is the case). */
static bool
number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
@@ -538,6 +538,11 @@ number_of_iterations_le (tree type, affi
is IV0, the right-hand side is IV1. Both induction variables must have
type TYPE, which must be an integer or pointer type. The steps of the
ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
+
+ ONLY_EXIT is true if we are sure this is the only way the loop could be
+ exited (including possibly non-returning function calls, exceptions, etc.)
+ -- in this case we can use the information whether the control induction
+ variables can overflow or not in a more efficient way.
The results (number of iterations and assumptions as described in
comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
@@ -546,7 +551,8 @@ number_of_iterations_le (tree type, affi
static bool
number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code,
- affine_iv *iv1, struct tree_niter_desc *niter)
+ affine_iv *iv1, struct tree_niter_desc *niter,
+ bool only_exit)
{
bool never_infinite;
@@ -572,13 +578,30 @@ number_of_iterations_cond (tree type, af
code = swap_tree_comparison (code);
}
+ if (!only_exit)
+ {
+ /* If this is not the only possible exit from the loop, the information
+ that the induction variables cannot overflow as derived from
+ signedness analysis cannot be relied upon. We use them e.g. in the
+ following way: given loop for (i = 0; i <= n; i++), if i is
+ signed, it cannot overflow, thus this loop is equivalent to
+ for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
+ is exited in some other way before i overflows, this transformation
+ is incorrect (the new loop exits immediately). */
+ iv0->no_overflow = false;
+ iv1->no_overflow = false;
+ }
+
if (POINTER_TYPE_P (type))
{
/* Comparison of pointers is undefined unless both iv0 and iv1 point
to the same object. If they do, the control variable cannot wrap
(as wrap around the bounds of memory will never return a pointer
that would be guaranteed to point to the same object, even if we
- avoid undefined behavior by casting to size_t and back). */
+ avoid undefined behavior by casting to size_t and back). The
+ restrictions on pointer arithmetics and comparisons of pointers
+ ensure that using the no-overflow assumptions is correct in this
+ case even if ONLY_EXIT is false. */
iv0->no_overflow = true;
iv1->no_overflow = true;
}
@@ -963,6 +986,37 @@ simplify_using_outer_evolutions (struct
return expr;
}
+/* Returns true if EXIT is the only possible exit from LOOP. */
+
+static bool
+loop_only_exit_p (struct loop *loop, edge exit)
+{
+ basic_block *body;
+ block_stmt_iterator bsi;
+ unsigned i;
+ tree call;
+
+ if (exit != loop->single_exit)
+ return false;
+
+ body = get_loop_body (loop);
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ call = get_call_expr_in (bsi_stmt (bsi));
+ if (call && TREE_SIDE_EFFECTS (call))
+ {
+ free (body);
+ return false;
+ }
+ }
+ }
+
+ free (body);
+ return true;
+}
+
/* Stores description of number of iterations of LOOP derived from
EXIT (an exit edge of the LOOP) in NITER. Returns true if some
useful information could be derived (and fields of NITER has
@@ -1023,7 +1077,8 @@ number_of_iterations_exit (struct loop *
iv0.base = expand_simple_operations (iv0.base);
iv1.base = expand_simple_operations (iv1.base);
- if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter))
+ if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter,
+ loop_only_exit_p (loop, exit)))
return false;
if (optimize >= 3)
--- gcc/testsuite/gcc.c-torture/execute/pr27285.c 2006-04-19 19:21:31.748476000 +0200
+++ gcc/testsuite/gcc.c-torture/execute/pr27285.c 2006-04-24 17:00:35.000000000 +0200
@@ -0,0 +1,46 @@
+/* PR tree-optimization/27285 */
+
+extern void abort (void);
+
+struct S { unsigned char a, b, c, d[16]; };
+
+void __attribute__ ((noinline))
+foo (struct S *x, struct S *y)
+{
+ int a, b;
+ unsigned char c, *d, *e;
+
+ b = x->b;
+ d = x->d;
+ e = y->d;
+ a = 0;
+ while (b)
+ {
+ if (b >= 8)
+ {
+ c = 0xff;
+ b -= 8;
+ }
+ else
+ {
+ c = 0xff << (8 - b);
+ b = 0;
+ }
+
+ e[a] = d[a] & c;
+ a++;
+ }
+}
+
+int
+main (void)
+{
+ struct S x = { 0, 25, 0, { 0xaa, 0xbb, 0xcc, 0xdd }};
+ struct S y = { 0, 0, 0, { 0 }};
+
+ foo (&x, &y);
+ if (x.d[0] != y.d[0] || x.d[1] != y.d[1]
+ || x.d[2] != y.d[2] || (x.d[3] & 0x80) != y.d[3])
+ abort ();
+ return 0;
+}
Jakub
More information about the Gcc-patches
mailing list