[Bug tree-optimization/67683] New: Missed vectorization: shifts of an induction variable

[Bug tree-optimization/67683] New: Missed vectorization: shifts of an induction variable

[alalaw01 at gcc dot gnu.org]

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

            Bug ID: 67683
           Summary: Missed vectorization: shifts of an induction variable
           Product: gcc
           Version: 6.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: alalaw01 at gcc dot gnu.org
            Blocks: 53947
  Target Milestone: ---

This testcase:

void test (unsigned char *data, int max)
{
  unsigned short val = 0xcdef;
  for(int i = 0; i < max; i++) { 
          data[i] = (unsigned char)(val & 0xff);
          val >>= 1; 
  }
}

does not vectorize on AArch64 or x86_64 at -O3. (I haven't yet looked at
whether it's a mid-end deficiency or both back-ends are missing patterns.)


Referenced Bugs:

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

[Bug tree-optimization/67683] Missed vectorization: shifts of an induction variable

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-09-23
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
The issue is the unsupported induction (the PHI) of val

  <bb 5>:
  # val_16 = PHI <52719(4), val_11(7)>
  # i_17 = PHI <0(4), i_12(7)>
  _6 = (sizetype) i_17;
  _8 = data_7(D) + _6;
  _9 = (unsigned char) val_16;
  *_8 = _9;
  val_11 = val_16 >> 1;
  i_12 = i_17 + 1;
  if (max_5(D) > i_12)

SCEV already fails to analyze the evolution of val_16 so it doesn't appear
as "induction" to the vectorizer.  Reductions with shifts are not handled
either (but reduction uses inside the loop are not supported by the vectorizer
anyway).

[Bug tree-optimization/67683] Missed vectorization: shifts of an induction variable

[alalaw01 at gcc dot gnu.org]

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

alalaw01 at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=35226

--- Comment #2 from alalaw01 at gcc dot gnu.org ---
Is there a way to do this kind of thing other than extending polynomial_chrec's
to understand operations other than addition ? Whilst beneficial, that looks to
be quite a large task.

[Bug tree-optimization/67683] Missed vectorization: shifts of an induction variable

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Right shifts are divisions so the result isn't an affine evolution.

Yes, you could enhance the vectorizer to not rely on scalar evolutions (only)
for reduction detection.

[Bug tree-optimization/67683] Missed vectorization: shifts of an induction variable

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67683
Bug 67683 depends on bug 35226, which changed state.

Bug 35226 Summary: Induction with multiplication are not vectorized
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35226

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

[Bug tree-optimization/67683] Missed vectorization: shifts of an induction variable

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
/app/example.cpp:5:20: note:   vect_is_simple_use: operand # RANGE [irange]
short unsigned int [0, 2047][3294, 3294][6589, 6589][13179, 13179][26359,
26359][52719, 52719]
val_16 = PHI <val_11(6), 52719(5)>, type of def: induction

We detect it now.
But then it is still not vectorized ...

[Bug tree-optimization/67683] Missed vectorization: shifts of an induction variable

[liuhongt at gcc dot gnu.org]

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

Hongtao Liu <liuhongt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |liuhongt at gcc dot gnu.org

--- Comment #6 from Hongtao Liu <liuhongt at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #5)
> /app/example.cpp:5:20: note:   vect_is_simple_use: operand # RANGE [irange]
> short unsigned int [0, 2047][3294, 3294][6589, 6589][13179, 13179][26359,
> 26359][52719, 52719]
> val_16 = PHI <val_11(6), 52719(5)>, type of def: induction
> 
> We detect it now.
> But then it is still not vectorized ...

We don't know how to peel for variable niter, there could be UD if we peel it
like val(epilogue) = val >> (max / vf) * vf.