This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [2/2] Fix bogus inner induction (PR 86725)
- From: Richard Biener <richard dot guenther at gmail dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>, Richard Sandiford <richard dot sandiford at arm dot com>
- Date: Wed, 22 Aug 2018 14:06:47 +0200
- Subject: Re: [2/2] Fix bogus inner induction (PR 86725)
- References: <87pnyavj7a.fsf@arm.com>
On Wed, Aug 22, 2018 at 11:34 AM Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> This patch is the second part of the fix for PR 86725. The problem
> in the original test is that for:
>
> outer1:
> x_1 = PHI <x_4(outer2), ...>;
> ...
>
> inner:
> x_2 = PHI <x_1(outer1), x_3(...)>;
> ...
> x_3 = ...;
> ...
>
> outer2:
> x_4 = PHI <x_3(inner)>;
> ...
>
> there are corner cases in which it is possible to classify the
> inner phi as an induction but not the outer phi. The -4.c test
> is a more direct example.
>
> After failing to classify x_1 as an induction, we go on to
> classify it as a double reduction (which is basically true).
> But we still classified the inner phi as an induction rather
> than as part of a reduction, leading to an ICE when trying
> to vectorise the outer phi.
>
> We analyse the phis for outer loops first, so the simplest
> fix is not to classify the phi as an induction if outer loop
> analysis said that it should be a reduction.
>
> The -2.c test is from the original PR. The -3.c test is a
> version in which "wo" really is used a reduction; this was
> already correctly rejected, but for the wrong reason ("inner-loop
> induction only used outside of the outer vectorized loop").
> The -4.c test is another way of tickling the original problem
> without relying on the undefinedness of signed overflow.
> The -5.c test shows an (uninteresting) example in which the
> patch prevents a spurious failure to vectorise the outer loop.
>
> Tested on aarch64-linux-gnu (with and without SVE), aarch64_be-elf
> and x86_64-linux-gnu. OK for trunk and GCC 8?
OK.
Thanks,
Richard.
> Richard
>
>
> 2018-08-22 Richard Sandiford <richard.sandiford@arm.com>
>
> gcc/
> PR tree-optimization/86725
> * tree-vect-loop.c (vect_inner_phi_in_double_reduction_p): New
> function.
> (vect_analyze_scalar_cycles_1): Check it.
>
> gcc/testsuite/
> PR tree-optimization/86725
> * gcc.dg/vect/no-scevccp-pr86725-2.c: New test.
> * gcc.dg/vect/no-scevccp-pr86725-3.c: Likewise.
> * gcc.dg/vect/no-scevccp-pr86725-4.c: Likewise.
> * gcc.dg/vect/no-scevccp-pr86725-5.c: Likewise.
>
> Index: gcc/tree-vect-loop.c
> ===================================================================
> --- gcc/tree-vect-loop.c 2018-08-22 10:25:06.682099699 +0100
> +++ gcc/tree-vect-loop.c 2018-08-22 10:25:09.586074995 +0100
> @@ -462,6 +462,40 @@ vect_is_simple_iv_evolution (unsigned lo
> return true;
> }
>
> +/* Return true if PHI, described by STMT_INFO, is the inner PHI in
> + what we are assuming is a double reduction. For example, given
> + a structure like this:
> +
> + outer1:
> + x_1 = PHI <x_4(outer2), ...>;
> + ...
> +
> + inner:
> + x_2 = PHI <x_1(outer1), ...>;
> + ...
> + x_3 = ...;
> + ...
> +
> + outer2:
> + x_4 = PHI <x_3(inner)>;
> + ...
> +
> + outer loop analysis would treat x_1 as a double reduction phi and
> + this function would then return true for x_2. */
> +
> +static bool
> +vect_inner_phi_in_double_reduction_p (stmt_vec_info stmt_info, gphi *phi)
> +{
> + loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
> + use_operand_p use_p;
> + ssa_op_iter op_iter;
> + FOR_EACH_PHI_ARG (use_p, phi, op_iter, SSA_OP_USE)
> + if (stmt_vec_info def_info = loop_vinfo->lookup_def (USE_FROM_PTR (use_p)))
> + if (STMT_VINFO_DEF_TYPE (def_info) == vect_double_reduction_def)
> + return true;
> + return false;
> +}
> +
> /* Function vect_analyze_scalar_cycles_1.
>
> Examine the cross iteration def-use cycles of scalar variables
> @@ -522,6 +556,7 @@ vect_analyze_scalar_cycles_1 (loop_vec_i
> }
>
> if (!access_fn
> + || vect_inner_phi_in_double_reduction_p (stmt_vinfo, phi)
> || !vect_is_simple_iv_evolution (loop->num, access_fn, &init, &step)
> || (LOOP_VINFO_LOOP (loop_vinfo) != loop
> && TREE_CODE (step) != INTEGER_CST))
> Index: gcc/testsuite/gcc.dg/vect/no-scevccp-pr86725-2.c
> ===================================================================
> --- /dev/null 2018-07-26 10:26:13.137955424 +0100
> +++ gcc/testsuite/gcc.dg/vect/no-scevccp-pr86725-2.c 2018-08-22 10:25:09.582075029 +0100
> @@ -0,0 +1,23 @@
> +/* { dg-do compile } */
> +/* { dg-additional-options "-O -w" } */
> +
> +int
> +nr (int xe)
> +{
> + int oo, wo = 0;
> +
> + for (oo = 0; oo < 4; ++oo)
> + {
> + int qq;
> +
> + for (qq = 0; qq < 2; ++qq)
> + {
> + wo += 0x80000000;
> + xe += wo;
> + }
> + }
> + return xe;
> +}
> +
> +/* { dg-final { scan-tree-dump "reduction used in loop" "vect" { target vect_int } } } */
> +/* { dg-final { scan-tree-dump-not "OUTER LOOP VECTORIZED" "vect" } } */
> Index: gcc/testsuite/gcc.dg/vect/no-scevccp-pr86725-3.c
> ===================================================================
> --- /dev/null 2018-07-26 10:26:13.137955424 +0100
> +++ gcc/testsuite/gcc.dg/vect/no-scevccp-pr86725-3.c 2018-08-22 10:25:09.582075029 +0100
> @@ -0,0 +1,25 @@
> +/* { dg-do compile } */
> +/* { dg-additional-options "-O -w" } */
> +
> +int foo;
> +int
> +nr (int xe)
> +{
> + int oo, wo = 0;
> +
> + for (oo = 0; oo < 4; ++oo)
> + {
> + int qq;
> +
> + for (qq = 0; qq < 2; ++qq)
> + {
> + wo += 0x80000000;
> + xe += wo;
> + }
> + }
> + foo = wo;
> + return xe;
> +}
> +
> +/* { dg-final { scan-tree-dump "reduction used in loop" "vect" { target vect_int } } } */
> +/* { dg-final { scan-tree-dump-not "OUTER LOOP VECTORIZED" "vect" } } */
> Index: gcc/testsuite/gcc.dg/vect/no-scevccp-pr86725-4.c
> ===================================================================
> --- /dev/null 2018-07-26 10:26:13.137955424 +0100
> +++ gcc/testsuite/gcc.dg/vect/no-scevccp-pr86725-4.c 2018-08-22 10:25:09.582075029 +0100
> @@ -0,0 +1,23 @@
> +/* { dg-do compile } */
> +/* { dg-additional-options "-O -w" } */
> +
> +int
> +nr (unsigned int xe, unsigned int qqn)
> +{
> + unsigned int oo, wo = 0;
> +
> + for (oo = 0; oo < 4; ++oo)
> + {
> + unsigned int qq = qqn;
> + do
> + {
> + wo += 1;
> + xe += wo;
> + }
> + while (qq-- > 0);
> + }
> + return xe;
> +}
> +
> +/* { dg-final { scan-tree-dump "reduction used in loop" "vect" { target vect_int } } } */
> +/* { dg-final { scan-tree-dump-not "OUTER LOOP VECTORIZED" "vect" } } */
> Index: gcc/testsuite/gcc.dg/vect/no-scevccp-pr86725-5.c
> ===================================================================
> --- /dev/null 2018-07-26 10:26:13.137955424 +0100
> +++ gcc/testsuite/gcc.dg/vect/no-scevccp-pr86725-5.c 2018-08-22 10:25:09.582075029 +0100
> @@ -0,0 +1,24 @@
> +/* { dg-do compile } */
> +/* { dg-additional-options "-O -w" } */
> +
> +unsigned int foo;
> +int
> +nr (unsigned int xe, unsigned int qqn)
> +{
> + unsigned int oo, wo = 0;
> +
> + for (oo = 0; oo < 4; ++oo)
> + {
> + unsigned int qq = qqn;
> + do
> + {
> + wo += 1;
> + xe += qq;
> + }
> + while (qq-- > 0);
> + }
> + foo = wo;
> + return xe;
> +}
> +
> +/* { dg-final { scan-tree-dump "OUTER LOOP VECTORIZED" "vect" { target vect_int } } } */