diff mbox series

avoid infinite loops in rpo fre

Message ID or1rnvivk9.fsf@livre.home
State New
Headers show
Series avoid infinite loops in rpo fre | expand

Commit Message

Alexandre Oliva May 7, 2020, 4 p.m. UTC 
gnat.dg/opt83.adb compiled with -O2+ would enter an infinite loop with
memory allocation within fre.  I don't think there is anything
Ada-specific in the bug, but the exact inlining and loop unrolling
circumstances needed to trigger the bug are quite fragile, so I didn't
try very hard to translate it to C.

The problem comes about while attempting to eliminate the last of the
following stmts, generated for 'R (0) := F;':

  A78b_144 = MEM <struct opt83__e[/*...*/]> [(struct opt83__e &)_41][0]{lb: _46 sz: 16}._tag;
  MEM <struct opt83__e[/*...*/]> [(struct opt83__e &)_41][0]{lb: _46 sz: 16} = f;
  MEM <struct opt83__e[/*...*/]> [(struct opt83__e &)_41][0]{lb: _46 sz: 16}._tag = A78b_144;

valueize_refs_1 takes a sequence of vn_reference_op_s with _41 in it, and
when it gets to that op, vn_valueize = rpo_vn_valueize replaces _41 with
_47, defined in the previous block as:

  _47 = &(*_41)[0]{lb: _46 sz: 16};

_47 is the first argument passed to the function synthesized to copy F
to the first element of array R, after checking that their addresses
do not compare equal.

There is another earlier def in the Value Numbering set associated with
_41, namely:

  _164 = &MEM[(struct ALLOC *)_163].ARRAY;

_163 is the newly-allocated storage for the 0..4 array.  Unfortunately
the logic in rpo_vn_valueize selects the former, and then we add the
_47 definition in _41's place in the op sequence.  Problem is _41 is
part of the expression, and thus of the expansion, so eventually we
reach it and replace it again, and again, and at every cycle we add
more ops than we remove, so the sequence grows unbounded.


Limiting the selection of alternate defs for the value to those that
dominate the def we're replacing should be enough to avoid the
problem, since we'd only perform replacements "up" the CFG.  Changing
the BB context for the selection of the value equivalence to that of
the name we're replacing, rather than that of the expression in which
we're replacing it, seems to be close enough.  It does solve the
problem without any codegen changes in a GCC bootstrap, despite a few
differences in eliminate_avail.

Regstrapped on x86_64-linux-gnu.  Ok to install?

As I prepare to post this, it occurs to me that maybe, instead of using
vn_context_bb for a default NAME like before, we should abandon the
attempt to substitute it, lest we might run into the same kind of
infinite loop in for e.g. _41(D).  WDYT?


for  gcc/ChangeLog

	* tree-ssa-sccvn.c (rpo_vn_valueize): Take the BB context from
	NAME.

for  gcc/testsuite/ChangeLog

	* gnat.dg/opt83.adb: New.
---
 gcc/testsuite/gnat.dg/opt83.adb |   33 +++++++++++++++++++++++++++++++++
 gcc/tree-ssa-sccvn.c            |    7 ++++++-
 2 files changed, 39 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gnat.dg/opt83.adb

Comments

Richard Biener May 8, 2020, 6:58 a.m. UTC | #1 
On Thu, May 7, 2020 at 6:27 PM Alexandre Oliva <oliva@adacore.com> wrote:
>
>
> gnat.dg/opt83.adb compiled with -O2+ would enter an infinite loop with
> memory allocation within fre.  I don't think there is anything
> Ada-specific in the bug, but the exact inlining and loop unrolling
> circumstances needed to trigger the bug are quite fragile, so I didn't
> try very hard to translate it to C.
>
> The problem comes about while attempting to eliminate the last of the
> following stmts, generated for 'R (0) := F;':
>
>   A78b_144 = MEM <struct opt83__e[/*...*/]> [(struct opt83__e &)_41][0]{lb: _46 sz: 16}._tag;
>   MEM <struct opt83__e[/*...*/]> [(struct opt83__e &)_41][0]{lb: _46 sz: 16} = f;
>   MEM <struct opt83__e[/*...*/]> [(struct opt83__e &)_41][0]{lb: _46 sz: 16}._tag = A78b_144;
>
> valueize_refs_1 takes a sequence of vn_reference_op_s with _41 in it, and
> when it gets to that op, vn_valueize = rpo_vn_valueize replaces _41 with
> _47, defined in the previous block as:
>
>   _47 = &(*_41)[0]{lb: _46 sz: 16};
>
> _47 is the first argument passed to the function synthesized to copy F
> to the first element of array R, after checking that their addresses
> do not compare equal.
>
> There is another earlier def in the Value Numbering set associated with
> _41, namely:
>
>   _164 = &MEM[(struct ALLOC *)_163].ARRAY;
>
> _163 is the newly-allocated storage for the 0..4 array.  Unfortunately
> the logic in rpo_vn_valueize selects the former, and then we add the
> _47 definition in _41's place in the op sequence.  Problem is _41 is
> part of the expression, and thus of the expansion, so eventually we
> reach it and replace it again, and again, and at every cycle we add
> more ops than we remove, so the sequence grows unbounded.

So value-numbering value-numbered _41 and _47 the same which
looks sensible only if _46 is zero.  But at the _47 definition we should
not have recorded _47 as another available name for _41 so we should
not have valueized to _47.

I'll try to debug this myself, the proposed patch looks wrong to me.

Richard.

>
> Limiting the selection of alternate defs for the value to those that
> dominate the def we're replacing should be enough to avoid the
> problem, since we'd only perform replacements "up" the CFG.  Changing
> the BB context for the selection of the value equivalence to that of
> the name we're replacing, rather than that of the expression in which
> we're replacing it, seems to be close enough.  It does solve the
> problem without any codegen changes in a GCC bootstrap, despite a few
> differences in eliminate_avail.
>
> Regstrapped on x86_64-linux-gnu.  Ok to install?
>
> As I prepare to post this, it occurs to me that maybe, instead of using
> vn_context_bb for a default NAME like before, we should abandon the
> attempt to substitute it, lest we might run into the same kind of
> infinite loop in for e.g. _41(D).  WDYT?
>
>
> for  gcc/ChangeLog
>
>         * tree-ssa-sccvn.c (rpo_vn_valueize): Take the BB context from
>         NAME.
>
> for  gcc/testsuite/ChangeLog
>
>         * gnat.dg/opt83.adb: New.
> ---
>  gcc/testsuite/gnat.dg/opt83.adb |   33 +++++++++++++++++++++++++++++++++
>  gcc/tree-ssa-sccvn.c            |    7 ++++++-
>  2 files changed, 39 insertions(+), 1 deletion(-)
>  create mode 100644 gcc/testsuite/gnat.dg/opt83.adb
>
> diff --git a/gcc/testsuite/gnat.dg/opt83.adb b/gcc/testsuite/gnat.dg/opt83.adb
> new file mode 100644
> index 00000000..7418520
> --- /dev/null
> +++ b/gcc/testsuite/gnat.dg/opt83.adb
> @@ -0,0 +1,33 @@
> +--  { dg-do compile }
> +--  { dg-options "-O2" }
> +
> +--  rpo fre3 used to loop indefinitely replacing _2 with _8 and back,
> +--  given MEM[(struct test__e &)_2][0]{lb: _7 sz: 16}._tag = A23s_29;
> +--  and an earlier _8 = &*_2[0]{lb: _7 sz: 16}.
> +
> +procedure Opt83 is
> +
> +   type E is tagged record
> +      I : Natural := 0;
> +   end record;
> +
> +   type A is array (Natural range <>) of aliased E;
> +
> +   F : E;
> +
> +   R : access A;
> +
> +   procedure N is
> +   begin
> +      if R = null then
> +        R := new A (0 .. 4);
> +      end if;
> +   end N;
> +
> +begin
> +
> +   N;
> +
> +   R (0) := F;
> +
> +end Opt83;
> diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
> index 8a4af91..9008724 100644
> --- a/gcc/tree-ssa-sccvn.c
> +++ b/gcc/tree-ssa-sccvn.c
> @@ -6790,9 +6790,14 @@ rpo_vn_valueize (tree name)
>             {
>               if (TREE_CODE (tem) != SSA_NAME)
>                 return tem;
> +             basic_block bb = vn_context_bb;
> +             /* Avoid replacing name with anything whose definition
> +                could refer back to name.  */
> +             if (! SSA_NAME_IS_DEFAULT_DEF (name))
> +               bb = gimple_bb (SSA_NAME_DEF_STMT (name));
>               /* For all values we only valueize to an available leader
>                  which means we can use SSA name info without restriction.  */
> -             tem = rpo_avail->eliminate_avail (vn_context_bb, tem);
> +             tem = rpo_avail->eliminate_avail (bb, tem);
>               if (tem)
>                 return tem;
>             }
>
> --
> Alexandre Oliva, freedom fighter    he/him    https://FSFLA.org/blogs/lxo/
> Free Software Evangelist              Stallman was right, but he's left :(
> GNU Toolchain Engineer           Live long and free, and prosper ethically
Richard Biener May 8, 2020, 8:29 a.m. UTC | #2 
On Fri, May 8, 2020 at 8:58 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Thu, May 7, 2020 at 6:27 PM Alexandre Oliva <oliva@adacore.com> wrote:
> >
> >
> > gnat.dg/opt83.adb compiled with -O2+ would enter an infinite loop with
> > memory allocation within fre.  I don't think there is anything
> > Ada-specific in the bug, but the exact inlining and loop unrolling
> > circumstances needed to trigger the bug are quite fragile, so I didn't
> > try very hard to translate it to C.
> >
> > The problem comes about while attempting to eliminate the last of the
> > following stmts, generated for 'R (0) := F;':
> >
> >   A78b_144 = MEM <struct opt83__e[/*...*/]> [(struct opt83__e &)_41][0]{lb: _46 sz: 16}._tag;
> >   MEM <struct opt83__e[/*...*/]> [(struct opt83__e &)_41][0]{lb: _46 sz: 16} = f;
> >   MEM <struct opt83__e[/*...*/]> [(struct opt83__e &)_41][0]{lb: _46 sz: 16}._tag = A78b_144;
> >
> > valueize_refs_1 takes a sequence of vn_reference_op_s with _41 in it, and
> > when it gets to that op, vn_valueize = rpo_vn_valueize replaces _41 with
> > _47, defined in the previous block as:
> >
> >   _47 = &(*_41)[0]{lb: _46 sz: 16};
> >
> > _47 is the first argument passed to the function synthesized to copy F
> > to the first element of array R, after checking that their addresses
> > do not compare equal.
> >
> > There is another earlier def in the Value Numbering set associated with
> > _41, namely:
> >
> >   _164 = &MEM[(struct ALLOC *)_163].ARRAY;
> >
> > _163 is the newly-allocated storage for the 0..4 array.  Unfortunately
> > the logic in rpo_vn_valueize selects the former, and then we add the
> > _47 definition in _41's place in the op sequence.  Problem is _41 is
> > part of the expression, and thus of the expansion, so eventually we
> > reach it and replace it again, and again, and at every cycle we add
> > more ops than we remove, so the sequence grows unbounded.
>
> So value-numbering value-numbered _41 and _47 the same which
> looks sensible only if _46 is zero.  But at the _47 definition we should
> not have recorded _47 as another available name for _41 so we should
> not have valueized to _47.
>
> I'll try to debug this myself, the proposed patch looks wrong to me.

OK, so I think the issue is that we are using RPO availability during
the DOM elimination walk at all - there can be easily disconnects
between what RPO iteration left us with and what the DOM walk
eliminates.  Fixing this fixes the testcase.

There's also the missed optimization of not figuring &(*_41)[0]{lb: _46 sz: 16};
is simply _41 during valueization and forwarding of the address.  I
have a fix for that as well and that also fixes the issue independently
on the above fix.

So testing the attached.

Richard.

> Richard.
>
> >
> > Limiting the selection of alternate defs for the value to those that
> > dominate the def we're replacing should be enough to avoid the
> > problem, since we'd only perform replacements "up" the CFG.  Changing
> > the BB context for the selection of the value equivalence to that of
> > the name we're replacing, rather than that of the expression in which
> > we're replacing it, seems to be close enough.  It does solve the
> > problem without any codegen changes in a GCC bootstrap, despite a few
> > differences in eliminate_avail.
> >
> > Regstrapped on x86_64-linux-gnu.  Ok to install?
> >
> > As I prepare to post this, it occurs to me that maybe, instead of using
> > vn_context_bb for a default NAME like before, we should abandon the
> > attempt to substitute it, lest we might run into the same kind of
> > infinite loop in for e.g. _41(D).  WDYT?
> >
> >
> > for  gcc/ChangeLog
> >
> >         * tree-ssa-sccvn.c (rpo_vn_valueize): Take the BB context from
> >         NAME.
> >
> > for  gcc/testsuite/ChangeLog
> >
> >         * gnat.dg/opt83.adb: New.
> > ---
> >  gcc/testsuite/gnat.dg/opt83.adb |   33 +++++++++++++++++++++++++++++++++
> >  gcc/tree-ssa-sccvn.c            |    7 ++++++-
> >  2 files changed, 39 insertions(+), 1 deletion(-)
> >  create mode 100644 gcc/testsuite/gnat.dg/opt83.adb
> >
> > diff --git a/gcc/testsuite/gnat.dg/opt83.adb b/gcc/testsuite/gnat.dg/opt83.adb
> > new file mode 100644
> > index 00000000..7418520
> > --- /dev/null
> > +++ b/gcc/testsuite/gnat.dg/opt83.adb
> > @@ -0,0 +1,33 @@
> > +--  { dg-do compile }
> > +--  { dg-options "-O2" }
> > +
> > +--  rpo fre3 used to loop indefinitely replacing _2 with _8 and back,
> > +--  given MEM[(struct test__e &)_2][0]{lb: _7 sz: 16}._tag = A23s_29;
> > +--  and an earlier _8 = &*_2[0]{lb: _7 sz: 16}.
> > +
> > +procedure Opt83 is
> > +
> > +   type E is tagged record
> > +      I : Natural := 0;
> > +   end record;
> > +
> > +   type A is array (Natural range <>) of aliased E;
> > +
> > +   F : E;
> > +
> > +   R : access A;
> > +
> > +   procedure N is
> > +   begin
> > +      if R = null then
> > +        R := new A (0 .. 4);
> > +      end if;
> > +   end N;
> > +
> > +begin
> > +
> > +   N;
> > +
> > +   R (0) := F;
> > +
> > +end Opt83;
> > diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
> > index 8a4af91..9008724 100644
> > --- a/gcc/tree-ssa-sccvn.c
> > +++ b/gcc/tree-ssa-sccvn.c
> > @@ -6790,9 +6790,14 @@ rpo_vn_valueize (tree name)
> >             {
> >               if (TREE_CODE (tem) != SSA_NAME)
> >                 return tem;
> > +             basic_block bb = vn_context_bb;
> > +             /* Avoid replacing name with anything whose definition
> > +                could refer back to name.  */
> > +             if (! SSA_NAME_IS_DEFAULT_DEF (name))
> > +               bb = gimple_bb (SSA_NAME_DEF_STMT (name));
> >               /* For all values we only valueize to an available leader
> >                  which means we can use SSA name info without restriction.  */
> > -             tem = rpo_avail->eliminate_avail (vn_context_bb, tem);
> > +             tem = rpo_avail->eliminate_avail (bb, tem);
> >               if (tem)
> >                 return tem;
> >             }
> >
> > --
> > Alexandre Oliva, freedom fighter    he/him    https://FSFLA.org/blogs/lxo/
> > Free Software Evangelist              Stallman was right, but he's left :(
> > GNU Toolchain Engineer           Live long and free, and prosper ethically
Alexandre Oliva May 8, 2020, 8:57 p.m. UTC | #3 
On May  8, 2020, Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:

> OK, so I think the issue is that we are using RPO availability during
> the DOM elimination walk at all - there can be easily disconnects
> between what RPO iteration left us with and what the DOM walk
> eliminates.  Fixing this fixes the testcase.

> There's also the missed optimization of not figuring &(*_41)[0]{lb: _46 sz: 16};
> is simply _41 during valueization and forwarding of the address.  I
> have a fix for that as well and that also fixes the issue independently
> on the above fix.

Cool!, two fixes in one! :-)

Thanks for looking into it, and for the patch.


I'm still a little concerned that other circumstances that still use
rpo_vn_valueize might run into such loops as the one I've seen.

AFAICT the specific situation that failed won't any more, not just
because of the improved forward propagation, but also because the
eliminate_dom_walker always seems to eliminate SSA_NAMEs in favor of
earlier definitions, so there's no risk of an infinite loop there.

However, it appears that rpo_vn_valueize might still replace a SSA_NAME
with a later definition, that could bring us back to the one just
eliminated.  Do you by any chance have a simple argument to rule out
this possibility?


Thanks in advance,
Richard Biener May 9, 2020, 6:21 a.m. UTC | #4 
On May 8, 2020 10:57:35 PM GMT+02:00, Alexandre Oliva <oliva@adacore.com> wrote:
>On May  8, 2020, Richard Biener via Gcc-patches
><gcc-patches@gcc.gnu.org> wrote:
>
>> OK, so I think the issue is that we are using RPO availability during
>> the DOM elimination walk at all - there can be easily disconnects
>> between what RPO iteration left us with and what the DOM walk
>> eliminates.  Fixing this fixes the testcase.
>
>> There's also the missed optimization of not figuring &(*_41)[0]{lb:
>_46 sz: 16};
>> is simply _41 during valueization and forwarding of the address.  I
>> have a fix for that as well and that also fixes the issue
>independently
>> on the above fix.
>
>Cool!, two fixes in one! :-)
>
>Thanks for looking into it, and for the patch.
>
>
>I'm still a little concerned that other circumstances that still use
>rpo_vn_valueize might run into such loops as the one I've seen.
>
>AFAICT the specific situation that failed won't any more, not just
>because of the improved forward propagation, but also because the
>eliminate_dom_walker always seems to eliminate SSA_NAMEs in favor of
>earlier definitions, so there's no risk of an infinite loop there.
>
>However, it appears that rpo_vn_valueize might still replace a SSA_NAME
>with a later definition, that could bring us back to the one just
>eliminated.  Do you by any chance have a simple argument to rule out
>this possibility?

Both use availability and should never replace with a later definition. The issue is when you mix availability data from both, which might differ, you can run into this behavior. 

Maybe I should experiment with removal of this dual implentation... (I kept it for compile time reasons, but there without doing any measurements). 

Richard. 

>
>Thanks in advance,
diff mbox series

Patch

diff --git a/gcc/testsuite/gnat.dg/opt83.adb b/gcc/testsuite/gnat.dg/opt83.adb
new file mode 100644
index 00000000..7418520
--- /dev/null
+++ b/gcc/testsuite/gnat.dg/opt83.adb
@@ -0,0 +1,33 @@ 
+--  { dg-do compile }
+--  { dg-options "-O2" }
+
+--  rpo fre3 used to loop indefinitely replacing _2 with _8 and back,
+--  given MEM[(struct test__e &)_2][0]{lb: _7 sz: 16}._tag = A23s_29;
+--  and an earlier _8 = &*_2[0]{lb: _7 sz: 16}.
+
+procedure Opt83 is
+
+   type E is tagged record
+      I : Natural := 0;
+   end record;
+
+   type A is array (Natural range <>) of aliased E;
+
+   F : E;
+
+   R : access A;
+
+   procedure N is 
+   begin
+      if R = null then
+	 R := new A (0 .. 4);
+      end if;
+   end N;
+
+begin
+
+   N;
+
+   R (0) := F;
+
+end Opt83;
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 8a4af91..9008724 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -6790,9 +6790,14 @@  rpo_vn_valueize (tree name)
 	    {
 	      if (TREE_CODE (tem) != SSA_NAME)
 		return tem;
+	      basic_block bb = vn_context_bb;
+	      /* Avoid replacing name with anything whose definition
+		 could refer back to name.  */
+	      if (! SSA_NAME_IS_DEFAULT_DEF (name))
+		bb = gimple_bb (SSA_NAME_DEF_STMT (name));
 	      /* For all values we only valueize to an available leader
 		 which means we can use SSA name info without restriction.  */
-	      tem = rpo_avail->eliminate_avail (vn_context_bb, tem);
+	      tem = rpo_avail->eliminate_avail (bb, tem);
 	      if (tem)
 		return tem;
 	    }