[Bug tree-optimization/105053] New: Wrong loop count for scalar code from vectorizer

[Bug tree-optimization/105053] New: Wrong loop count for scalar code from vectorizer

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

            Bug ID: 105053
           Summary: Wrong loop count for scalar code from vectorizer
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org
  Target Milestone: ---

#include <vector>
#include <tuple>
#include <algorithm>
#include <random>
#include <iostream>

int main(){
  const long n = 100000000;
  std::vector<std::tuple<int,int,double>> vec;
  vec.reserve(n);
  std::random_device rd;
  std::default_random_engine re(rd());
  std::uniform_int_distribution<int> rand_int;
  std::uniform_real_distribution<double> rand_dbl;
  for(int i=0;i<n;++i)
    vec.emplace_back(rand_int(re), rand_int(re), rand_dbl(re));
  {
    int sup = 0;
    for(int i=0;i<n;++i)
sup=std::max(sup,std::max(std::get<0>(vec[i]),std::get<1>(vec[i])));
    std::cout << sup << '\n';
  }
  {
    int sup = 0;
    for(int i=0;i<n;++i)
sup=std::max(std::max(sup,std::get<0>(vec[i])),std::get<1>(vec[i]));
    std::cout << sup << '\n';
  }
}

Can output for instance
2147483645
2147483637
compiled with -O3, whereas the 2 numbers should be the same.

If I compare what I get from the first loop with -O3 -fno-tree-loop-vectorize
to the second loop with just -O3, the code is almost identical, except that the
(scalar) code only iterates on 1/4 of the array, as if it was using a bound
meant for a vector. -fno-tree-loop-vectorize seems to be ok.

[Bug tree-optimization/105053] Wrong loop count for scalar code from vectorizer

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-03-25
           Keywords|                            |needs-bisection
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
It also reproduces with n == 16 for me - can you produce a testcase with a
static initializer that's known to fail please?

[Bug tree-optimization/105053] Wrong loop count for scalar code from vectorizer

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> It also reproduces with n == 16 for me - can you produce a testcase with a
> static initializer that's known to fail please?

And n == 4, but std::cout << vec; doesn't like me :P

[Bug tree-optimization/105053] Wrong loop count for scalar code from vectorizer

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #2)
> (In reply to Richard Biener from comment #1)
> > It also reproduces with n == 16 for me - can you produce a testcase with a
> > static initializer that's known to fail please?
> 
> And n == 4, but std::cout << vec; doesn't like me :P

1597201307 1817606674
1380347796 1721941769
837975613 1032707773
1173654292 2020064272

Testcase:

#include <vector>
#include <tuple>
#include <algorithm>

int main()
{
  const int n = 4;
  std::vector<std::tuple<int,int,double>> vec
      = { { 1597201307, 1817606674, 0. },
            { 1380347796, 1721941769, 0.},
            {837975613, 1032707773, 0.},
            {1173654292, 2020064272, 0.} } ;
  int sup1 = 0;
  for(int i=0;i<n;++i)
    sup1=std::max(sup1,std::max(std::get<0>(vec[i]),std::get<1>(vec[i])));
  int sup2 = 0;
  for(int i=0;i<n;++i)
    sup2=std::max(std::max(sup2,std::get<0>(vec[i])),std::get<1>(vec[i]));
  if (sup1 != sup2)
    std::abort ();
  return 0;
}

[Bug tree-optimization/105053] Wrong loop count for scalar code from vectorizer

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
One notable difference is that the first loop is detected to require peeling
for gaps while the second one is not (probably an artifact of the low trip
count).
The second is that the first loop is detected as reduction path while the
second one as reduction chain.

OK, so I think I see what goes wrong.  We elided the load permutation but
the load is still biased wrongly.

  vectp.67_112 = _93 + 8;

  <bb 12> [local count: 405853744]:
  # i_98 = PHI <i_44(21), 0(11)>
  # prephitmp_7 = PHI <prephitmp_97(21), 0(11)>
  # ivtmp_31 = PHI <ivtmp_37(21), 4(11)>
  # vectp.66_105 = PHI <vectp.66_68(21), vectp.67_112(11)>
  # vect_prephitmp_7.71_61 = PHI <vect__26.72_62(21), { 0, 0, 0, 0 }(11)>
  # ivtmp_58 = PHI <ivtmp_81(21), 0(11)>
  _3 = (long unsigned int) i_98;
  _59 = _3 * 16;
  _60 = _93 + _59;
  _106 = MEM <vector(2) int> [(const int &)vectp.66_105];
  vect__54.68_113 = {_106, { 0, 0 }};
  vectp.66_95 = vectp.66_105 + 16;
  _89 = MEM <vector(2) int> [(const int &)vectp.66_95];
  vect__54.69_90 = {_89, { 0, 0 }};
  vect__51.70_78 = VEC_PERM_EXPR <vect__54.68_113, vect__54.69_90, { 0, 1, 4, 5
}>;

possibly because the SLP representative is unchanged when we transform

t.C:17:16: note:   node 0x3382280 (max_nunits=4, refcnt=2) const vector(4) int
t.C:17:16: note:   op template: _54 = MEM[(const int &)_60 + 12];
t.C:17:16: note:        stmt 0 _54 = MEM[(const int &)_60 + 12];
t.C:17:16: note:        stmt 1 _51 = MEM[(const int &)_60 + 8];
t.C:17:16: note:        load permutation { 1 0 }

into

t.C:17:16: note:   node 0x3382280 (max_nunits=4, refcnt=1) const vector(4) int
t.C:17:16: note:   op template: _54 = MEM[(const int &)_60 + 12];
t.C:17:16: note:        stmt 0 _51 = MEM[(const int &)_60 + 8];
t.C:17:16: note:        stmt 1 _54 = MEM[(const int &)_60 + 12];
t.C:17:16: note:        load permutation { 0 1 }

during SLP optimize.

[Bug tree-optimization/105053] Wrong loop count for scalar code from vectorizer

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Err, no - the reduction epilogue is simply incomplete:

  <bb 46> [local count: 202926872]:
  # prephitmp_27 = PHI <prephitmp_97(12)>
  # vect__26.72_63 = PHI <vect__26.72_62(12)>
  _64 = .REDUC_MAX (vect__26.72_63);
  if (prephitmp_27 != prephitmp_35)
    goto <bb 18>; [0.00%]
  else
    goto <bb 19>; [100.00%]

  <bb 18> [count: 0]:
  abort ();

and the reason is that live_out_stmts has the wrong entry and we fail to
adjust the PHI nodes.  Now that's a missed optimization and should still
keep the scalar code live of course.

In fact

    /* The last statement in the reduction chain produces the live-out
       value.  */
    single_live_out_stmt[0] = SLP_TREE_SCALAR_STMTS (slp_node)[group_size - 1];

is wrong.  Or rather the way to get at it is.

The following fixes this and the testcase.

@@ -5271,9 +5275,17 @@ vect_create_epilog_for_reduction (loop_vec_info
loop_vinfo,
     /* All statements produce live-out values.  */
     live_out_stmts = SLP_TREE_SCALAR_STMTS (slp_node);
   else if (slp_node)
-    /* The last statement in the reduction chain produces the live-out
-       value.  */
-    single_live_out_stmt[0] = SLP_TREE_SCALAR_STMTS (slp_node)[group_size -
1];
+    {
+      /* The last statement in the reduction chain produces the live-out
+        value.  Note SLP optimization can shuffle scalar stmts to
+        optimize permutations so we have to search for the last stmt.  */
+      for (k = 0; k < group_size; ++k)
+       if (!REDUC_GROUP_NEXT_ELEMENT (SLP_TREE_SCALAR_STMTS (slp_node)[k]))
+         {
+           single_live_out_stmt[0] = SLP_TREE_SCALAR_STMTS (slp_node)[k];
+           break;
+         }
+    }

   unsigned vec_num;
   int ncopies;

[Bug tree-optimization/105053] Wrong loop count for scalar code from vectorizer

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:fe705dce2e1e3e4e5e0c69d7f9adaf7f2777cdc8

commit r12-7816-gfe705dce2e1e3e4e5e0c69d7f9adaf7f2777cdc8
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Mar 25 14:31:25 2022 +0100

    tree-optimization/105053 - fix reduction chain epilogue generation

    When we optimize permutations in a reduction chain we have to
    be careful to select the correct live-out stmt, otherwise the
    reduction result will be unused and the retained scalar code will
    execute only the number of vector iterations.

    2022-03-25  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/105053
            * tree-vect-loop.cc (vect_create_epilog_for_reduction): Pick
            the correct live-out stmt for a reduction chain.

            * g++.dg/vect/pr105053.cc: New testcase.

[Bug tree-optimization/105053] Wrong loop count for scalar code from vectorizer

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |12.0

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Should be fixed on trunk.  It might be latent on the 11 branch, I have to
double-check.

[Bug tree-optimization/105053] Wrong loop count for scalar code from vectorizer

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

--- Comment #8 from Marc Glisse <glisse at gcc dot gnu.org> ---
Thank you.
I originally noticed the problem with 11.2.0-18 (Debian), so I believe this
will be needed on that branch as well. 10.3.0 looked ok...

[Bug tree-optimization/105053] Wrong loop count for scalar code from vectorizer

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|needs-bisection             |

--- Comment #9 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #3)
> (In reply to Richard Biener from comment #2)
> > (In reply to Richard Biener from comment #1)
> > > It also reproduces with n == 16 for me - can you produce a testcase with a
> > > static initializer that's known to fail please?
> > 
> > And n == 4, but std::cout << vec; doesn't like me :P
> 
> 1597201307 1817606674
> 1380347796 1721941769
> 837975613 1032707773
> 1173654292 2020064272
> 
> Testcase:
> 
> #include <vector>
> #include <tuple>
> #include <algorithm>
> 
> int main()
> {
>   const int n = 4;
>   std::vector<std::tuple<int,int,double>> vec
>       = { { 1597201307, 1817606674, 0. },
>             { 1380347796, 1721941769, 0.},
>             {837975613, 1032707773, 0.},
>             {1173654292, 2020064272, 0.} } ;
>   int sup1 = 0;
>   for(int i=0;i<n;++i)
>     sup1=std::max(sup1,std::max(std::get<0>(vec[i]),std::get<1>(vec[i])));
>   int sup2 = 0;
>   for(int i=0;i<n;++i)
>     sup2=std::max(std::max(sup2,std::get<0>(vec[i])),std::get<1>(vec[i]));
>   if (sup1 != sup2)
>     std::abort ();
>   return 0;
> }

This one started failing with r11-4428-g4a369d199bf2f34e.

[Bug tree-optimization/105053] [11 Regression] Wrong loop count for scalar code from vectorizer

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|12.0                        |11.2.0
            Summary|Wrong loop count for scalar |[11 Regression] Wrong loop
                   |code from vectorizer        |count for scalar code from
                   |                            |vectorizer
      Known to fail|                            |11.2.0
   Target Milestone|---                         |11.3
           Priority|P3                          |P2

[Bug tree-optimization/105053] [11 Regression] Wrong loop count for scalar code from vectorizer

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:825151e16373760527678df8ad524bd725e36c7b

commit r11-9784-g825151e16373760527678df8ad524bd725e36c7b
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Mar 25 14:31:25 2022 +0100

    tree-optimization/105053 - fix reduction chain epilogue generation

    When we optimize permutations in a reduction chain we have to
    be careful to select the correct live-out stmt, otherwise the
    reduction result will be unused and the retained scalar code will
    execute only the number of vector iterations.

    2022-03-25  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/105053
            * tree-vect-loop.c (vect_create_epilog_for_reduction): Pick
            the correct live-out stmt for a reduction chain.

            * g++.dg/vect/pr105053.cc: New testcase.

[Bug tree-optimization/105053] [11 Regression] Wrong loop count for scalar code from vectorizer

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105053

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |11.2.1
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Should be fixed in GCC 11 as well now (but the code is quite different there).