[Bug middle-end/106408] New: PRE with infinite loops

[Bug middle-end/106408] New: PRE with infinite loops

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106408

            Bug ID: 106408
           Summary: PRE with infinite loops
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org
  Target Milestone: ---

int array[10000];
volatile int val;
int test(short *b,int s)
{
        for (int i = 0; i<10000;i++)
          {
            for (int j = 0; j < 10; j+=s)
                val++;
            array[i]+=*b;
          }
}

shows we PRE the *b load from both GIMPLE and RTL PRE across the possibly
infinite loop (with s == 0).  The function makes progress by means of
the volatile access which is considered I/O.

[Bug middle-end/106408] PRE with infinite loops

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106408

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
An incomplete solution on the GIMPLE level is the following.  It's incomplete
because there's a hole for irreducible regions which we do not represent
explicitely (nor their sub-irreducible regions). 
rev_post_order_and_mark_dfs_back_seme has a simplified loop discovery code
that would properly compute this.

Just considering all blocks in irreducible regions as BB_MAY_NORETURN will
inhibit all in-region PRE which is probably undesirable.  OTOH the code
below will unnecessarily pessimize "well written" loops while leaving the
bug open for the bad ones.

diff --git a/gcc/tree-ssa-pre.cc b/gcc/tree-ssa-pre.cc
index e029bd36da3..76dbef4cff3 100644
--- a/gcc/tree-ssa-pre.cc
+++ b/gcc/tree-ssa-pre.cc
@@ -52,6 +52,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-cfgcleanup.h"
 #include "alias.h"
 #include "gimple-range.h"
+#include "tree-ssa-loop-niter.h"

 /* Even though this file is called tree-ssa-pre.cc, we actually
    implement a bit more than just PRE here.  All of them piggy-back
@@ -3939,6 +3940,12 @@ compute_avail (function *fun)

       BB_MAY_NOTRETURN (block) = 0;

+      /* If block is a loop that is possibly infinite we should not
+        hoist across it.  */
+      if (block->loop_father->header == block
+         && !finite_loop_p (block->loop_father))
+       BB_MAY_NOTRETURN (block) = 1;
+
       /* Now compute value numbers and populate value sets with all
         the expressions computed in BLOCK.  */
       bool set_bb_may_notreturn = false;

[Bug middle-end/106408] PRE with infinite loops

[hubicka at ucw dot cz]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106408

--- Comment #2 from Jan Hubicka <hubicka at ucw dot cz> ---
> +      /* If block is a loop that is possibly infinite we should not
> +        hoist across it.  */
> +      if (block->loop_father->header == block
> +         && !finite_loop_p (block->loop_father))
> +       BB_MAY_NOTRETURN (block) = 1;
> +
Don't you just need to handle also BBs that have backedge out that is
not a latch of loop?
(it is an ugly issue overall)

Honza

[Bug middle-end/106408] PRE with infinite loops

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106408

--- Comment #3 from rguenther at suse dot de <rguenther at suse dot de> ---
On Fri, 22 Jul 2022, hubicka at ucw dot cz wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106408
> 
> --- Comment #2 from Jan Hubicka <hubicka at ucw dot cz> ---
> > +      /* If block is a loop that is possibly infinite we should not
> > +        hoist across it.  */
> > +      if (block->loop_father->header == block
> > +         && !finite_loop_p (block->loop_father))
> > +       BB_MAY_NOTRETURN (block) = 1;
> > +
> Don't you just need to handle also BBs that have backedge out that is
> not a latch of loop?

I would need to handle all blocks with an incoming backedge,
and for non-irreducible regions can use finite_loop_p, yes.
Not sure what you mean with backedge out.

So the following would handle loops and irreducible regions correctly
I think.

diff --git a/gcc/tree-ssa-pre.cc b/gcc/tree-ssa-pre.cc
index e029bd36da3..a2d8b52f872 100644
--- a/gcc/tree-ssa-pre.cc
+++ b/gcc/tree-ssa-pre.cc
@@ -52,6 +52,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-cfgcleanup.h"
 #include "alias.h"
 #include "gimple-range.h"
+#include "tree-ssa-loop-niter.h"

 /* Even though this file is called tree-ssa-pre.cc, we actually
    implement a bit more than just PRE here.  All of them piggy-back
@@ -3939,6 +3940,16 @@ compute_avail (function *fun)

       BB_MAY_NOTRETURN (block) = 0;

+      /* If this block is an entry into a CFG cycle that is possibly 
infinite
+        we should not hoist across it.  */
+      edge_iterator ei;
+      edge e;
+      FOR_EACH_EDGE (e, ei, block->preds)
+       if ((e->flags & EDGE_DFS_BACK)
+           && (block->loop_father->header != block
+               || !finite_loop_p (block->loop_father)))
+         BB_MAY_NOTRETURN (block) = 1;
+
       /* Now compute value numbers and populate value sets with all
         the expressions computed in BLOCK.  */
       bool set_bb_may_notreturn = false;

[Bug middle-end/106408] PRE with infinite loops

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106408

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to rguenther@suse.de from comment #3)
> On Fri, 22 Jul 2022, hubicka at ucw dot cz wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106408
> > 
> > --- Comment #2 from Jan Hubicka <hubicka at ucw dot cz> ---
> > > +      /* If block is a loop that is possibly infinite we should not
> > > +        hoist across it.  */
> > > +      if (block->loop_father->header == block
> > > +         && !finite_loop_p (block->loop_father))
> > > +       BB_MAY_NOTRETURN (block) = 1;
> > > +
> > Don't you just need to handle also BBs that have backedge out that is
> > not a latch of loop?
> 
> I would need to handle all blocks with an incoming backedge,
> and for non-irreducible regions can use finite_loop_p, yes.
> Not sure what you mean with backedge out.
> 
> So the following would handle loops and irreducible regions correctly
> I think.
> 
> diff --git a/gcc/tree-ssa-pre.cc b/gcc/tree-ssa-pre.cc
> index e029bd36da3..a2d8b52f872 100644
> --- a/gcc/tree-ssa-pre.cc
> +++ b/gcc/tree-ssa-pre.cc
> @@ -52,6 +52,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "tree-cfgcleanup.h"
>  #include "alias.h"
>  #include "gimple-range.h"
> +#include "tree-ssa-loop-niter.h"
>  
>  /* Even though this file is called tree-ssa-pre.cc, we actually
>     implement a bit more than just PRE here.  All of them piggy-back
> @@ -3939,6 +3940,16 @@ compute_avail (function *fun)
>  
>        BB_MAY_NOTRETURN (block) = 0;
>  
> +      /* If this block is an entry into a CFG cycle that is possibly 
> infinite
> +        we should not hoist across it.  */
> +      edge_iterator ei;
> +      edge e;
> +      FOR_EACH_EDGE (e, ei, block->preds)
> +       if ((e->flags & EDGE_DFS_BACK)
> +           && (block->loop_father->header != block
> +               || !finite_loop_p (block->loop_father)))
> +         BB_MAY_NOTRETURN (block) = 1;
> +
>        /* Now compute value numbers and populate value sets with all
>          the expressions computed in BLOCK.  */
>        bool set_bb_may_notreturn = false;

It regresses

FAIL: gcc.dg/tree-ssa/loadpre10.c scan-tree-dump-times pre "Eliminated: 1" 1
FAIL: gcc.dg/tree-ssa/loadpre8.c scan-tree-dump-times pre "Eliminated: 1" 1     
FAIL: gcc.dg/tree-ssa/pr21417.c scan-tree-dump-times thread2 "jump thread" 1