* [PATCH] Improve niters brute force (PR tree-optimization/77975)
@ 2017-03-09 21:21 Jakub Jelinek
2017-03-10 7:51 ` Richard Biener
0 siblings, 1 reply; 2+ messages in thread
From: Jakub Jelinek @ 2017-03-09 21:21 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
Hi!
As you know, this is mostly your patch, I've just added some comments,
testcase and a small optimization; I believe the fix is right, if next[j]
is constant in addition to val[j] (for both args or op[1-j] is constant),
the loop can have 0(1), 1(2) or infinite iterations, and we can just brute
force that one or 2 iterations to find out the outcome.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
2017-03-09 Richard Biener <rguenther@suse.de>
Jakub Jelinek <jakub@redhat.com>
PR tree-optimization/77975
* tree-ssa-loop-niter.c (get_base_for): Allow phi argument from latch
edge to be constant.
(get_val_for): For constant x return it. Formatting fix.
(loop_niter_by_eval): Avoid pointless looping if the next iteration
would use the same bases as the current one.
* gcc.dg/pr77975.c: New test.
--- gcc/tree-ssa-loop-niter.c.jj 2017-02-25 09:32:11.000000000 +0100
+++ gcc/tree-ssa-loop-niter.c 2017-03-09 14:28:28.826948753 +0100
@@ -2521,7 +2521,8 @@ chain_of_csts_start (struct loop *loop,
* the derivation of X consists only from operations with constants
* the initial value of the phi node is constant
* the value of the phi node in the next iteration can be derived from the
- value in the current iteration by a chain of operations with constants.
+ value in the current iteration by a chain of operations with constants,
+ or is also a constant
If such phi node exists, it is returned, otherwise NULL is returned. */
@@ -2541,13 +2542,11 @@ get_base_for (struct loop *loop, tree x)
init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
- if (TREE_CODE (next) != SSA_NAME)
- return NULL;
-
if (!is_gimple_min_invariant (init))
return NULL;
- if (chain_of_csts_start (loop, next) != phi)
+ if (TREE_CODE (next) == SSA_NAME
+ && chain_of_csts_start (loop, next) != phi)
return NULL;
return phi;
@@ -2556,6 +2555,7 @@ get_base_for (struct loop *loop, tree x)
/* Given an expression X, then
* if X is NULL_TREE, we return the constant BASE.
+ * if X is a constant, we return the constant X.
* otherwise X is a SSA name, whose value in the considered loop is derived
by a chain of operations with constant from a result of a phi node in
the header of the loop. Then we return value of X when the value of the
@@ -2570,6 +2570,8 @@ get_val_for (tree x, tree base)
if (!x)
return base;
+ else if (is_gimple_min_invariant (x))
+ return x;
stmt = SSA_NAME_DEF_STMT (x);
if (gimple_code (stmt) == GIMPLE_PHI)
@@ -2584,11 +2586,9 @@ get_val_for (tree x, tree base)
return get_val_for (gimple_assign_rhs1 (stmt), base);
else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
&& TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
- {
- return fold_build1 (gimple_assign_rhs_code (stmt),
- gimple_expr_type (stmt),
- get_val_for (gimple_assign_rhs1 (stmt), base));
- }
+ return fold_build1 (gimple_assign_rhs_code (stmt),
+ gimple_expr_type (stmt),
+ get_val_for (gimple_assign_rhs1 (stmt), base));
else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
{
tree rhs1 = gimple_assign_rhs1 (stmt);
@@ -2687,6 +2687,7 @@ loop_niter_by_eval (struct loop *loop, e
for (j = 0; j < 2; j++)
{
+ aval[j] = val[j];
val[j] = get_val_for (next[j], val[j]);
if (!is_gimple_min_invariant (val[j]))
{
@@ -2694,6 +2695,12 @@ loop_niter_by_eval (struct loop *loop, e
return chrec_dont_know;
}
}
+
+ /* If the next iteration would use the same base values
+ as the current one, there is no point looping further,
+ all following iterations will be the same as this one. */
+ if (val[0] == aval[0] && val[1] == aval[1])
+ break;
}
fold_undefer_and_ignore_overflow_warnings ();
--- gcc/testsuite/gcc.dg/pr77975.c.jj 2017-03-09 14:04:38.072778030 +0100
+++ gcc/testsuite/gcc.dg/pr77975.c 2017-03-09 14:04:23.000000000 +0100
@@ -0,0 +1,31 @@
+/* PR tree-optimization/77975 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivcanon-details" } */
+
+/* { dg-final { scan-tree-dump-times "Proved that loop 1 iterates 1 times using brute force" 1 "ivcanon" } } */
+
+unsigned int
+foo (unsigned int *b)
+{
+ unsigned int a = 3;
+ while (a)
+ {
+ a >>= 1;
+ *b += a;
+ }
+ return a;
+}
+
+/* { dg-final { scan-tree-dump-times "Proved that loop 1 iterates 2 times using brute force" 1 "ivcanon" } } */
+
+unsigned int
+bar (unsigned int *b)
+{
+ unsigned int a = 7;
+ while (a)
+ {
+ a >>= 1;
+ *b += a;
+ }
+ return a;
+}
Jakub
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH] Improve niters brute force (PR tree-optimization/77975)
2017-03-09 21:21 [PATCH] Improve niters brute force (PR tree-optimization/77975) Jakub Jelinek
@ 2017-03-10 7:51 ` Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2017-03-10 7:51 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: gcc-patches
On Thu, 9 Mar 2017, Jakub Jelinek wrote:
> Hi!
>
> As you know, this is mostly your patch, I've just added some comments,
> testcase and a small optimization; I believe the fix is right, if next[j]
> is constant in addition to val[j] (for both args or op[1-j] is constant),
> the loop can have 0(1), 1(2) or infinite iterations, and we can just brute
> force that one or 2 iterations to find out the outcome.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
Ok.
Thanks,
Richard.
> 2017-03-09 Richard Biener <rguenther@suse.de>
> Jakub Jelinek <jakub@redhat.com>
>
> PR tree-optimization/77975
> * tree-ssa-loop-niter.c (get_base_for): Allow phi argument from latch
> edge to be constant.
> (get_val_for): For constant x return it. Formatting fix.
> (loop_niter_by_eval): Avoid pointless looping if the next iteration
> would use the same bases as the current one.
>
> * gcc.dg/pr77975.c: New test.
>
> --- gcc/tree-ssa-loop-niter.c.jj 2017-02-25 09:32:11.000000000 +0100
> +++ gcc/tree-ssa-loop-niter.c 2017-03-09 14:28:28.826948753 +0100
> @@ -2521,7 +2521,8 @@ chain_of_csts_start (struct loop *loop,
> * the derivation of X consists only from operations with constants
> * the initial value of the phi node is constant
> * the value of the phi node in the next iteration can be derived from the
> - value in the current iteration by a chain of operations with constants.
> + value in the current iteration by a chain of operations with constants,
> + or is also a constant
>
> If such phi node exists, it is returned, otherwise NULL is returned. */
>
> @@ -2541,13 +2542,11 @@ get_base_for (struct loop *loop, tree x)
> init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
> next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
>
> - if (TREE_CODE (next) != SSA_NAME)
> - return NULL;
> -
> if (!is_gimple_min_invariant (init))
> return NULL;
>
> - if (chain_of_csts_start (loop, next) != phi)
> + if (TREE_CODE (next) == SSA_NAME
> + && chain_of_csts_start (loop, next) != phi)
> return NULL;
>
> return phi;
> @@ -2556,6 +2555,7 @@ get_base_for (struct loop *loop, tree x)
> /* Given an expression X, then
>
> * if X is NULL_TREE, we return the constant BASE.
> + * if X is a constant, we return the constant X.
> * otherwise X is a SSA name, whose value in the considered loop is derived
> by a chain of operations with constant from a result of a phi node in
> the header of the loop. Then we return value of X when the value of the
> @@ -2570,6 +2570,8 @@ get_val_for (tree x, tree base)
>
> if (!x)
> return base;
> + else if (is_gimple_min_invariant (x))
> + return x;
>
> stmt = SSA_NAME_DEF_STMT (x);
> if (gimple_code (stmt) == GIMPLE_PHI)
> @@ -2584,11 +2586,9 @@ get_val_for (tree x, tree base)
> return get_val_for (gimple_assign_rhs1 (stmt), base);
> else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
> && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
> - {
> - return fold_build1 (gimple_assign_rhs_code (stmt),
> - gimple_expr_type (stmt),
> - get_val_for (gimple_assign_rhs1 (stmt), base));
> - }
> + return fold_build1 (gimple_assign_rhs_code (stmt),
> + gimple_expr_type (stmt),
> + get_val_for (gimple_assign_rhs1 (stmt), base));
> else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
> {
> tree rhs1 = gimple_assign_rhs1 (stmt);
> @@ -2687,6 +2687,7 @@ loop_niter_by_eval (struct loop *loop, e
>
> for (j = 0; j < 2; j++)
> {
> + aval[j] = val[j];
> val[j] = get_val_for (next[j], val[j]);
> if (!is_gimple_min_invariant (val[j]))
> {
> @@ -2694,6 +2695,12 @@ loop_niter_by_eval (struct loop *loop, e
> return chrec_dont_know;
> }
> }
> +
> + /* If the next iteration would use the same base values
> + as the current one, there is no point looping further,
> + all following iterations will be the same as this one. */
> + if (val[0] == aval[0] && val[1] == aval[1])
> + break;
> }
>
> fold_undefer_and_ignore_overflow_warnings ();
> --- gcc/testsuite/gcc.dg/pr77975.c.jj 2017-03-09 14:04:38.072778030 +0100
> +++ gcc/testsuite/gcc.dg/pr77975.c 2017-03-09 14:04:23.000000000 +0100
> @@ -0,0 +1,31 @@
> +/* PR tree-optimization/77975 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-ivcanon-details" } */
> +
> +/* { dg-final { scan-tree-dump-times "Proved that loop 1 iterates 1 times using brute force" 1 "ivcanon" } } */
> +
> +unsigned int
> +foo (unsigned int *b)
> +{
> + unsigned int a = 3;
> + while (a)
> + {
> + a >>= 1;
> + *b += a;
> + }
> + return a;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Proved that loop 1 iterates 2 times using brute force" 1 "ivcanon" } } */
> +
> +unsigned int
> +bar (unsigned int *b)
> +{
> + unsigned int a = 7;
> + while (a)
> + {
> + a >>= 1;
> + *b += a;
> + }
> + return a;
> +}
>
> Jakub
>
>
--
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2017-03-10 7:51 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-03-09 21:21 [PATCH] Improve niters brute force (PR tree-optimization/77975) Jakub Jelinek
2017-03-10 7:51 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).