[PATCH] vectorizing conditional expressions (PR tree-optimization/65947)

[Alan Hayward]

Hi,
This patch (attached) adds support for vectorizing conditional expressions
(PR 65947), for example:

int condition_reduction (int *a, int min_v)
{
  int last = 0;
  for (int i = 0; i < N; i++)
    if (a[i] < min_v)
      last = a[i];
  return last;
}

To do this the loop is vectorised to create a vector of data results (ie
of matching a[i] values). Using an induction variable, an additional
vector is added containing the indexes where the matches occured. In the
function epilogue this is reduced to a single max value and then used to
index into the vector of data results.
When no values are matched in the loop, the indexes vector will contain
all zeroes, eventually matching the first entry in the data results vector.

To vectorize sucessfully, support is required for REDUC_MAX_EXPR. This is
supported by aarch64 and arm. On X86 and powerpc, gcc will complain that
REDUC_MAX_EXPR is not supported for the required modes, failing the
vectorization. On mips it complains that the required vcond expression is
not supported. It is suggested the relevant backend experts add the
required backend support.

Using a simple testcase based around a large number of N and run on an
aarch64 juno board, with the patch in use, the runtime reduced to 0.8 of
it's original time.

This patch caused binary differences in three spec2006 binaries on aarch64
- 4.16.gamess, 435.gromacs and 456.hmmer. Running them on a juno board
showed no improvement or degregation in runtime.


In the near future I hope to submit a further patch (as PR 66558) which
optimises the case where the result is simply the index of the loop, for
example:
int condition_reduction (int *a, int min_v)
{
  int last = 0;
  for (int i = 0; i < N; i++)
    if (a[i] < min_v)
      last = i;
  return last;
}
In this case a lot of the new code can be optimized away.

I have run check for aarch64, arm and x86 and have seen no regressions.


Changelog:

    2015-08-28  Alan Hayward <alan.hayward@arm.com>

        PR tree-optimization/65947
        * tree-vect-loop.c
        (vect_is_simple_reduction_1): Find condition reductions.
        (vect_model_reduction_cost): Add condition reduction costs.
        (get_initial_def_for_reduction): Add condition reduction initial
var.
        (vect_create_epilog_for_reduction): Add condition reduction epilog.
        (vectorizable_reduction): Condition reduction support.
        * tree-vect-stmts.c
        (vectorizable_condition): Add vect reduction arg
        * doc/sourcebuild.texi (Vector-specific attributes): Document
        vect_max_reduc

    testsuite/Changelog:

        PR tree-optimization/65947
        * lib/target-supports.exp
        (check_effective_target_vect_max_reduc): Add.
        * gcc.dg/vect/pr65947-1.c: New test.
        * gcc.dg/vect/pr65947-2.c: New test.
        * gcc.dg/vect/pr65947-3.c: New test.
        * gcc.dg/vect/pr65947-4.c: New test.
        * gcc.dg/vect/pr65947-5.c: New test.
        * gcc.dg/vect/pr65947-6.c: New test.
        * gcc.dg/vect/pr65947-7.c: New test.
        * gcc.dg/vect/pr65947-8.c: New test.
        * gcc.dg/vect/pr65947-9.c: New test.
        * gcc.dg/vect/pr65947-10.c: New test.
        * gcc.dg/vect/pr65947-11.c: New test.



Thanks,
Alan


-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Support-for-vectorizing-conditional-expressions.patch
Type: application/octet-stream
Size: 52309 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20150910/42210929/attachment.obj>