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.
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
