2009-01-26 Kris Van Hees <kris.van.hees@oracle.com> Paolo Carlini <paolo.carlini@oracle.com> Backport from mainline 2006-05-02 Zdenek Dvorak <dvorakz@suse.cz> * tree.c (unsigned_type_for, signed_type_for): Make sure a type of the correct signedness is returned. 2006-05-01 Zdenek Dvorak <dvorakz@suse.cz> PR tree-optimization/27144 * tree-ssa-loop-niter.c (derive_constant_upper_bound): New function. (record_estimate): Only record constant upper bound. (infer_loop_bounds_from_undefined): Call compute_estimated_nb_iterations just once. (proved_non_wrapping_p): Renamed to ... (n_of_executions_at_most): ... this. Expect bound to be a constant. (scev_probably_wraps_p): Call n_of_executions_at_most instead of proved_non_wrapping_p. (substitute_in_loop_info): Do not replace values in bounds. * cfgloop.h (struct nb_iter_bound): Remove "additional" field. Update comments. * gcc.dg/tree-ssa/loop-16.c: New test. --- gcc/tree-ssa-loop-niter.c (revision 113424) +++ gcc/tree-ssa-loop-niter.c (revision 113425) @@ -1464,6 +1464,24 @@ find_loop_niter_by_eval (struct loop *lo */ +/* Returns a constant upper bound on the value of expression VAL. The + condition ADDITIONAL must be satisfied (for example, if VAL is + "(unsigned) n" and ADDITIONAL is "n > 0", then we can derive that + VAL is at most (unsigned) MAX_INT). + + TODO -- actually do something nontrivial here. */ + +static tree +derive_constant_upper_bound (tree val, tree additional ATTRIBUTE_UNUSED) +{ + tree type = TREE_TYPE (val); + tree unsigned_type = unsigned_type_for (type); + + if (TREE_CODE (val) != INTEGER_CST) + val = upper_bound_in_type (type, type); + return fold_convert (unsigned_type, val); +} + /* Records that AT_STMT is executed at most BOUND times in LOOP. The additional condition ADDITIONAL is recorded with the bound. */ @@ -1471,6 +1489,7 @@ void record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt) { struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound)); + tree c_bound = derive_constant_upper_bound (bound, additional); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -1478,12 +1497,13 @@ record_estimate (struct loop *loop, tree print_generic_expr (dump_file, at_stmt, TDF_SLIM); fprintf (dump_file, " are executed at most "); print_generic_expr (dump_file, bound, TDF_SLIM); - fprintf (dump_file, " times in loop %d.\n", loop->num); + fprintf (dump_file, " (bounded by "); + print_generic_expr (dump_file, c_bound, TDF_SLIM); + fprintf (dump_file, ") times in loop %d.\n", loop->num); } - elt->bound = bound; + elt->bound = c_bound; elt->at_stmt = at_stmt; - elt->additional = additional; elt->next = loop->bounds; loop->bounds = elt; } @@ -1497,12 +1517,16 @@ compute_estimated_nb_iterations (struct struct nb_iter_bound *bound; for (bound = loop->bounds; bound; bound = bound->next) - if (TREE_CODE (bound->bound) == INTEGER_CST - /* Update only when there is no previous estimation. */ - && (chrec_contains_undetermined (loop->estimated_nb_iterations) - /* Or when the current estimation is smaller. */ - || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations))) - loop->estimated_nb_iterations = bound->bound; + { + if (TREE_CODE (bound->bound) != INTEGER_CST) + continue; + + /* Update only when there is no previous estimation, or when the current + estimation is smaller. */ + if (chrec_contains_undetermined (loop->estimated_nb_iterations) + || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)) + loop->estimated_nb_iterations = bound->bound; + } } /* The following analyzers are extracting informations on the bounds @@ -1611,11 +1635,9 @@ infer_loop_bounds_from_undefined (struct break; } } - - if (chrec_contains_undetermined (loop->estimated_nb_iterations)) - compute_estimated_nb_iterations (loop); } + compute_estimated_nb_iterations (loop); free (bbs); } @@ -1729,73 +1751,41 @@ stmt_dominates_stmt_p (tree s1, tree s2) return dominated_by_p (CDI_DOMINATORS, bb2, bb1); } -/* Return true when it is possible to prove that the induction - variable does not wrap: vary outside the type specified bounds. - Checks whether BOUND < VALID_NITER that means in the context of iv - conversion that all the iterations in the loop are safe: not - producing wraps. - - The statement NITER_BOUND->AT_STMT is executed at most - NITER_BOUND->BOUND times in the loop. - - NITER_BOUND->ADDITIONAL is the additional condition recorded for - operands of the bound. This is useful in the following case, - created by loop header copying: - - i = 0; - if (n > 0) - do - { - something; - } while (++i < n) - - If the n > 0 condition is taken into account, the number of iterations of the - loop can be expressed as n - 1. If the type of n is signed, the ADDITIONAL - assumption "n > 0" says us that the value of the number of iterations is at - most MAX_TYPE - 1 (without this assumption, it might overflow). */ +/* Returns true when we can prove that the number of executions of + STMT in the loop is at most NITER, according to the fact + that the statement NITER_BOUND->at_stmt is executed at most + NITER_BOUND->bound times. */ static bool -proved_non_wrapping_p (tree at_stmt, - struct nb_iter_bound *niter_bound, - tree new_type, - tree valid_niter) +n_of_executions_at_most (tree stmt, + struct nb_iter_bound *niter_bound, + tree niter) { tree cond; tree bound = niter_bound->bound; + tree bound_type = TREE_TYPE (bound); + tree nit_type = TREE_TYPE (niter); enum tree_code cmp; - if (TYPE_PRECISION (new_type) > TYPE_PRECISION (TREE_TYPE (bound))) - bound = fold_convert (unsigned_type_for (new_type), bound); + gcc_assert (TYPE_UNSIGNED (bound_type) + && TYPE_UNSIGNED (nit_type) + && is_gimple_min_invariant (bound)); + if (TYPE_PRECISION (nit_type) > TYPE_PRECISION (bound_type)) + bound = fold_convert (nit_type, bound); else - valid_niter = fold_convert (TREE_TYPE (bound), valid_niter); - - /* Give up if BOUND was not folded to an INTEGER_CST, as in PR23434. */ - if (TREE_CODE (bound) != INTEGER_CST) - return false; + niter = fold_convert (bound_type, niter); /* After the statement niter_bound->at_stmt we know that anything is executed at most BOUND times. */ - if (at_stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, at_stmt)) + if (stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, stmt)) cmp = GE_EXPR; /* Before the statement niter_bound->at_stmt we know that anything is executed at most BOUND + 1 times. */ else cmp = GT_EXPR; - cond = fold_binary (cmp, boolean_type_node, valid_niter, bound); - if (nonzero_p (cond)) - return true; - - cond = build2 (cmp, boolean_type_node, valid_niter, bound); - /* Try taking additional conditions into account. */ - cond = fold_binary (TRUTH_OR_EXPR, boolean_type_node, - invert_truthvalue (niter_bound->additional), - cond); - - if (nonzero_p (cond)) - return true; - - return false; + cond = fold_binary (cmp, boolean_type_node, niter, bound); + return nonzero_p (cond); } /* Checks whether it is correct to count the induction variable BASE + @@ -2077,7 +2067,7 @@ scev_probably_wraps_p (tree type, tree b estimate_numbers_of_iterations_loop (loop); for (bound = loop->bounds; bound; bound = bound->next) - if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter)) + if (n_of_executions_at_most (at_stmt, bound, valid_niter)) return false; /* At this point we still don't have a proof that the iv does not @@ -2162,14 +2152,7 @@ free_numbers_of_iterations_estimates (st void substitute_in_loop_info (struct loop *loop, tree name, tree val) { - struct nb_iter_bound *bound; - loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val); loop->estimated_nb_iterations = simplify_replace_tree (loop->estimated_nb_iterations, name, val); - for (bound = loop->bounds; bound; bound = bound->next) - { - bound->bound = simplify_replace_tree (bound->bound, name, val); - bound->additional = simplify_replace_tree (bound->additional, name, val); - } } --- gcc/tree.c (revision 113481) +++ gcc/tree.c (revision 113482) @@ -6990,7 +6990,7 @@ tree unsigned_type_for (tree type) { if (POINTER_TYPE_P (type)) - return size_type_node; + return lang_hooks.types.unsigned_type (size_type_node); return lang_hooks.types.unsigned_type (type); } @@ -6999,6 +6999,8 @@ unsigned_type_for (tree type) tree signed_type_for (tree type) { + if (POINTER_TYPE_P (type)) + return lang_hooks.types.signed_type (size_type_node); return lang_hooks.types.signed_type (type); } --- gcc/cfgloop.h (revision 113424) +++ gcc/cfgloop.h (revision 113425) @@ -47,12 +47,10 @@ struct lpt_decision struct nb_iter_bound { - tree bound; /* The expression whose value is an upper bound on the - number of executions of anything after ... */ - tree at_stmt; /* ... this statement during one execution of loop. */ - tree additional; /* A conjunction of conditions the operands of BOUND - satisfy. The additional information about the value - of the bound may be derived from it. */ + tree bound; /* The constant expression whose value is an upper + bound on the number of executions of ... */ + tree at_stmt; /* ... this statement during one execution of + a loop. */ struct nb_iter_bound *next; /* The next bound in a list. */ }; --- gcc/testsuite/gcc.dg/tree-ssa/loop-16.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/loop-16.c (revision 113425) @@ -0,0 +1,24 @@ +/* A test for # of iterations estimation. We know that the loop is executed + at most 100 times, thus the (32-bit) induction variables do not overflow, + and we may use 64-bit variable to represent them. */ + +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-do compile { target x86_64-*-* } } */ + +unsigned a[100]; + +void foo(unsigned n) +{ + unsigned i; + + for (i = 0; i < n; i++) + a[i] = 4 * i; +} + +/* Check that the memory reference was replaced with MEM, and that there is no + multiplication. */ + +/* { dg-final { scan-tree-dump-times "MEM" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "\[^\\n\\r\]*= \\* " 0 "optimized" } } */ + +/* { dg-final { cleanup-tree-dump "optimized" } } */ --- gcc/testsuite/gcc.dg/tree-ssa/rh490513.c 2009-01-05 19:26:54.499712239 -0500 +++ gcc/testsuite/gcc.dg/tree-ssa/rh490513.c 2009-01-28 14:15:22.000000000 -0500 @@ -0,0 +1,17 @@ +/* Contributed by Kris Van Hees <kris.van.hees@oracle.com> */ +/* { dg-do compile } */ +/* { dg-options "-O1" } */ + +void foo () +{ + short x, y, z; + char a[3]; + + for (x = 0; x < 2; x++) + for (y = 0; y < 2; y++) + if (a[y]) + { + for (z = y - 1; z > -1; z--) + a[z]++; + } +}