[Bug tree-optimization/66558] New: Missed vectorization of loop with control flow

[Bug tree-optimization/66558] New: Missed vectorization of loop with control flow

[alalaw01 at gcc dot gnu.org]

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

            Bug ID: 66558
           Summary: Missed vectorization of loop with control flow
           Product: gcc
           Version: 6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: alalaw01 at gcc dot gnu.org
  Target Milestone: ---
            Target: x86_64

ICC manages to vectorize the following loop, variants of which appear in
several benchmarks:

#define N 256
int a[N];

int
find_last (int threshold)
{
   int last = -1;

   for (int i = 0; i < N; i++)
    if (a[i] > threshold)
      last = i;

   return last;
}

[Bug tree-optimization/66558] Missed vectorization of loop with control flow

[alalaw01 at gcc dot gnu.org]

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

--- Comment #1 from alalaw01 at gcc dot gnu.org ---
Strategy could be similar to https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54013
except finding the last bit rather than the first (and no jump out of the
loop).

That is, in the loop body:

  v_pred = (a[i] > threshold) for each element
  if (any element of v_pred set)
    v_save_pred = v_pred
    v_save_i = {i, i+1, i+2, i+3}
    v_last = v_save_i // or a different expression, as is assigned to 'last'

and in the epilogue,

  last = v_last[ rightmost set element in v_save_pred ]

where the rightmost set element could be done via narrow/trunc and 'bsr' (on
x86), or more generally,

  idx = reduc_max_expr (v_save_pred ? v_save_i : 0)
  // any reduction will do here, as only one element will be non-zero:
  last = reduc_max_expr (v_save_i == idx ? v_last : 0)
  // or alternatively:
  last = v_last[ idx & (vec_num_elts - 1) ]

[Bug tree-optimization/66558] Missed vectorization of loop with control flow

[alalaw01 at gcc dot gnu.org]

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

--- Comment #2 from alalaw01 at gcc dot gnu.org ---
This generalizes https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65947, but
vectorizing the predicate as a reduction is not sufficient here.