[Bug tree-optimization/104579] New: vectorizer failed to reduce max & index search together

[Bug tree-optimization/104579] New: vectorizer failed to reduce max & index search together

[crazylht at gmail dot com]

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

            Bug ID: 104579
           Summary: vectorizer failed to reduce max & index search
                    together
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: crazylht at gmail dot com
  Target Milestone: ---

int max (int *src, int n, int *position)
{
  int maxInt;
  int maxIndex;
  int i;

  maxInt = src[0];
  maxIndex = 0;
  for (i = 1; i < n; i++) {
    if (maxInt < src[i]) {
      maxInt = src[i];
      maxIndex = i;
    }
  }
  *position = maxIndex;
  return (maxInt);
}

GCC can reduce max and index search separately, but not together.

[Bug tree-optimization/104579] vectorizer failed to reduce max & index search together

[crazylht at gmail dot com]

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

--- Comment #1 from Hongtao.liu <crazylht at gmail dot com> ---
------------cut ------------
/* Function vect_is_simple_reduction

   (1) Detect a cross-iteration def-use cycle that represents a simple
   reduction computation.  We look for the following pattern:

   loop_header:
     a1 = phi < a0, a2 >
     a3 = ...
     a2 = operation (a3, a1)

   or

   a3 = ...
   loop_header:
     a1 = phi < a0, a2 >
     a2 = operation (a3, a1)

   such that:
   1. operation is commutative and associative and it is safe to
      change the order of the computation
   2. no uses for a2 in the loop (a2 is used out of the loop)
   3. no uses of a1 in the loop besides the reduction operation
---------end------------------


----dump vect-------
  <bb 3> [local count: 955630225]:
  # maxInt_19 = PHI <maxInt_7(8), maxInt_14(18)>
  # maxIndex_20 = PHI <maxIndex_9(8), 0(18)>
  # i_24 = PHI <i_18(8), 1(18)>
  _1 = (long unsigned int) i_24;
  _2 = _1 * 4;
  _3 = src_13(D) + _2;
  _4 = *_3;
  maxInt_7 = MAX_EXPR <_4, maxInt_19>; ------ reduction operation
  maxIndex_9 = _4 <= maxInt_19 ? maxIndex_20 : i_24; --- another use here.
  i_18 = i_24 + 1;
  if (n_15(D) > i_18)
----dump end---------

For the case in the PR, there's 2 uses for a1(maxInt_19), one in reduction
operation(MAX_EXPR <_4, maxInt_19>), another in 4 <= maxInt_19 ? maxIndex_20 :
i_24), and it failed.

[Bug tree-optimization/104579] vectorizer failed to reduce max & index search together

[crazylht at gmail dot com]

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

--- Comment #2 from Hongtao.liu <crazylht at gmail dot com> ---
One possible way is sink maxInt = src[i] out of loop, when there's synchronised
index search in the loop, just like below.

int max (int *src, int n, int *position)
{
  int maxInt;
  int maxIndex;
  int i;

  maxInt = src[0];
  maxIndex = 0;
  for (i = 1; i < n; i++) {
    if (maxInt < src[i]) {
      maxIndex = i;
    }
  }
  maxInt = src[maxIndex];
  *position = maxIndex;
  return (maxInt);
}

[Bug tree-optimization/104579] vectorizer failed to reduce max & index search together

[crazylht at gmail dot com]

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

--- Comment #3 from Hongtao.liu <crazylht at gmail dot com> ---
(In reply to Hongtao.liu from comment #2)
> One possible way is sink maxInt = src[i] out of loop, when there's
> synchronised index search in the loop, just like below.
> 
For scalar part, it's 1 conditional movement in loop vs. 1 load out of loop.

[Bug tree-optimization/104579] vectorizer failed to reduce max & index search together

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
             Blocks|                            |53947
   Last reconfirmed|                            |2022-02-17

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Yes, you can re-materialize maxInt outside of the loop but you have to update
it during the loop as well which will end up not fixing the issue.

Btw, this bug has a duplicate somewhere.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=53947
[Bug 53947] [meta-bug] vectorizer missed-optimizations

[Bug tree-optimization/104579] vectorizer failed to reduce max & index search together

[crazylht at gmail dot com]

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

--- Comment #5 from Hongtao.liu <crazylht at gmail dot com> ---
PR50374?

It's from Fotran minloc/maxloc intrinsics.

[Bug tree-optimization/104579] vectorizer failed to reduce max & index search together

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement