Message ID | 87pnyavj7a.fsf@arm.com |
---|---|
State | New |
Headers | show |
Series | [1/2] Fix bogus double reduction (PR 86725) | expand |
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 } } } */
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 } } } */