[autovect] [patch] generic reduction patterns

[Dorit Naishlos <DORIT at il dot ibm dot com>]

In http://gcc.gnu.org/ml/gcc-patches/2005-04/msg00532.html I introduced
support for target specific reduction patterns. These patterns (e.g.
widening summation, dot product, sum of absolute differences) have
specialized support across several targets, and therefore we agreed in that
thread that it makes sense to introduce these patterns as generic patterns
rather than target specific ones. We tried to formulate the semantics of
these reduction idioms, and specifically idioms that involves widening (the
results is at least one machine mode bigger than the argument). The problem
was that different targets have different mechanisms to support these
idioms. E.g., in SSE the result of a widening sum of chars is short,
whereas in Altivec the result of a widening sum of chars is int. Instead of
trying to predefine the width of the result of a widen_sum_optab, we
decided to check the size of the result directly from the pattern of the
operation. I.e., we first get
      icode=widen_sum_optab->handlers[mode].insn_code exsits
and check if:
      icode!=CODE_FOR_nothing
and then get the width of the result:
      insn_data[icode].operand[0].mode
and check that it matches the mode of the result in the computation we want
to vectorize. This means we're going a bit deeper into the machine
description than we have so far, but it looks like things like that will
become unavoidable (see also the vector shifts problem -
http://gcc.gnu.org/ml/gcc/2005-09/msg00004.html).

This patch includes:
- new pattern-recognition-function to detect the widen-sum idiom
- new tree-code and optabs
- extended the reduction vectorization routines to also support reduction
patterns
- removed the previous target specific implementation of this pattern.

Yet to do:
- support summation of char->short even if a target doesn't support that
directly, but does support summation of char->int (by truncating the final
result).
- support more reduction patterns (e.g. dot product).

Bootstrapped (with vectorization enabled) on powerpc-suse-linux and
powerpc-darwin.

Will be committed as soon as the branch is syched with mainline (later this
week).
Also missing in this patch documentation for md.texi, which I will add
later.

dorit

ChangeLog:

        * expr.c (expand_expr_real_1): Add case WIDEN_SUM_EXPR.
        * genopinit.c (ssum_widen_optab): Init new optab.
        (usum_widen_optab): Likewise.
        * optabs.c (optab_for_tree_code): Add case WIDEN_SUM_EXPR.
        (expand_widen_pattern_expr): New function.
        (init_optabs): Initialize new optabs ssum_widen_optab and
        usum_widen_optab.
        * optabs.h (OTI_ssum_widen, OTI_usum_widen): New optabs.
        (ssum_widen_optab,  usum_widen_optab): New optabs.
        (expand_widen_pattern_expr): New function declaration.
        * tree-pretty-print.c (dump_generic_node): Add case WIDEN_SUM_EXPR.
        (op_prio): Add case WIDEN_SUM_EXPR.
        (op_symbol): Add case WIDEN_SUM_EXPR.
        * tree-vect-analyze.c (recog.h): Add include.
        (vect_pattern_recog_funcs): Add function to initialization.
        (vect_recog_widen_sum_pattern): New function.
        (vect_pattern_recog_1): Update documentation.
        * tree-vect-transform.c (vect_init_vector): Take vectype from the
        reduction variable instead of STMT_VINFO_VECTYPE.
        (get_initial_def_for_reduction): Likewise. Also add case
WIDEN_SUM_EXPR.
        (vect_create_epilog_for_reduction): Take vectype from the
        reduction variable instead of STMT_VINFO_VECTYPE. Take code,
        scalar_dest and scalar_type from orig_stmt if available. Add
assert.
        (vectorizable_reduction): Handle reduction patterns.
        * tree-vectorizer.c (vect_is_simple_reduction): Bring over fix from
        mainline.
        * tree-vectorizer.h (NUM_PATTERNS): Set to 2.
        (vect_recog_widen_sum_pattern): New function declaration.
        * tree.def (WIDEN_SUM_EXPR): New tree-code.
        * config/rs6000/altivec.md (widen_usum<mode>3): New pattern.
        (widen_ssumv16qi3, widen_ssumv8hi3): New patterns.
        * config/rs6000/rs6000.c (altivec_builtin_widening_summation):
Removed.
        (target_vect_pattern_recog_funcs): Remove initialization.
        (target_vect_recog_widening_summation_pattern): Function removed.
        (rs6000_expand_builtin): Removed handling of case
        ALTIVEC_BUILTIN_WIDENING_SUMMATION.
        (altivec_init_builtins): Remove initialization of builtin
        ALTIVEC_BUILTIN_WIDENING_SUMMATION.
        * config/rs6000/rs6000.h (TARGET_VECT_NUM_PATTERNS): Set to 0.

        * tree-pretty-print.c (op_symbol): Remove case REDUC_PLUS_EXPR.
        * tree-vect-analyze.c (vect_recog_unsigned_subsat_pattern): Move
        debug printout.


Patch and testcases:

(See attached file: widen-sum.sept6.txt)

(See attached file: vect-reduc-pattern-1.c)(See attached file:
vect-reduc-pattern-2.c)

Attachment: widen-sum.sept6.txt
Description: Text document

Attachment: vect-reduc-pattern-1.c
Description: Binary data

Attachment: vect-reduc-pattern-2.c
Description: Binary data