On Fri, May 8, 2020 at 8:58 AM Richard Biener
<richard.guent...@gmail.com> wrote:
>
> On Thu, May 7, 2020 at 6:27 PM Alexandre Oliva <ol...@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
p
Description: Binary data
