[patch] (4.1 stage 2 projects): vectorize reduction, part 1/n

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

First step towards merging vectorization of reduction into mainline. This
patch is mostly about preparing the ground for reduction support (update
data structures, reorganize code a bit), less about new functionality.
The changes included in this patch are:

1- A new field - STMT_VINFO_DEF_TYPE - was added to stmt_vec_info. It is
used to record what "type of computation" a stmt performs. The computation
types are with respect to the cross-iteration dependencies that the
computation creates. Each of these computation types is handled differenty
during vectorization:
- "vect_invariant_def", "vect_constant_def", "vect_loop_def": these are
computations that don't create a cross-iteration dependency.
- "vect_induction_def", "vect_reduction_def": these are computations that
create a cross-iteration dependency, but are special cases that we have a
special way to vectorize.
- "vect_unknown_def": these are computations that create a cross-iteration
dependecy that we don't know how to handle.

Phi nodes represent a cross-iteration def-use cycle and therefore typically
compute something that would be classified as induction or reduction. Other
stmts in the loop would be typically classified as "vect_loop_def"
computation (i.e. a regular computation that has no dependencies across
loop iterations).

In vect_analyze_scalar_cycles we scan all the loop-header phis; we used to
fail as soon as a cross-iteration cycles is detected. This is now changed
to just record the kind of def-use-cycle that was detected
(reduciton/induction/other) in STMT_VINFO_DEF_TYPE. Later analysis passes
will fail vectorization if an unsupported type of a def-use-cycle is used
in a relevant/live stmt. With this patch we don't yet detect reductions, so
anything that isn't an induction is classified as an unknown pattern.

2- Another new field - STMT_VINFO_LIVE_P - was added to stmt_vec_info. It
is used to mark if a def of a stmt is used after the loop. "relevant"
indicates that a stmt is used inside the loop in a computation that needs
to be vectorized. A stmt can be classified as live or relevant or both. We
currently don't support anything that is used out side the loop unless it
is loop invariant.

In vect_mark_stmts_to_be_vectorized we didn't use to distinguish between
live and relevant. Now that we're going to support reduction, which is used
outside the loop, but we want to make sure that it is not used inside the
loop (cause then we can't vectorize it), we need to keep track of the
liveness and relevance separately.

3- Phi nodes now also have a stmt_vec_info, because (1) we want to record
what kind of computation is involved in the def-use cycle that this phi is
part of (e.g. a form of reduction, or induction), and (2) we want to record
if the value that a phi node defines is used after the loop. For this, I
had to reverse this patch -
http://gcc.gnu.org/ml/gcc-patches/2005-04/msg02744.html, cause I need the
aux field also for phis.

The main differences throughout the code are to consider live and relevant
operations separately, and to also consider phis.

Testcases:

Added new testcases vect-reduc-[1,2,3].c that don't get vectorized yet, but
fail with the message:
"not vectorized: unsupported use in stmt" during
vect_mark_stmts_to_be_vectorized (when we examine the uses of the
live/relevant stmts and discover a use that is defined by a stmt that was
classified as 'vect_unknown_def_type'. When reduction support is merged,
the defining stmt will be classified as 'vect_reduction_def_type').

Testcase vect-62.c has a loop that contains only loop-invariant
computations. Regardless of the discussion what is the loop still doing
there, we want to avoid vectorizing this loop. With this patch the
vectorizer detects in vect_analyze_operations that no operation in the loop
need to be vectorized, and vectorization is avoided.


Bootstrapped (with vectorization) and tested on powerpc-darwin

Index: ChangeLog
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ChangeLog,v
retrieving revision 2.8910
diff -c -3 -p -r2.8910 ChangeLog
*** ChangeLog     26 May 2005 08:15:00 -0000    2.8910
--- ChangeLog     29 May 2005 14:18:30 -0000
***************
*** 1,3 ****
--- 1,66 ----
+ 2005-05-26  Dorit Naishlos  <dorit@il.ibm.com>
+
+     * tree-flow.h (stmt_ann_d): Move aux to ...
+     (tree_ann_common_d): ... here.
+     * tree-ssa-loop-im.c (LIM_DATA, determine_invariantness_stmt,
+     move_computations_stmt, schedule_sm): Update references to
+     aux.
+     * tree-vectorizer.h (set_stmt_info, vinfo_for_stmt): Likewise.
+     * tree-vect-transform.c (vect_create_index_for_vector_ref): Update
+     call to set_stmt_info.
+     (vect_transform_loop): Likewise.
+     * tree-vectorizer.c (new_loop_vec_info, destroy_loop_vec_info):
+     Likewise.
+
+     * tree-vect-analyze.c (vect_analyze_scalar_cycles): Made void instead of
+     bool.
+     (vect_mark_relevant): Takes two additional arguments - live_p and
+     relevant_p. Set RELEVANT_P and LIVE_P according to these arguments.
+     (vect_stmt_relevant_p): Differentiate between a live stmt and a
+     relevant stmt. Return two values = live_p and relevant_p.
+     (vect_mark_stmts_to_be_vectorized): Call vect_mark_relevant and
+     vect_stmt_relevant_p with additional arguments. Phis are no longer
+     put into the worklist (analyzed seperately in analyze_scalar_cycles).
+     (vect_determine_vectorization_factor): Also check for LIVE_P, because a
+     stmt that is marked as irrelevant and live, cause it's only used out
+     side the loop, may need to be vectorized (e.g. reduction).
+     (vect_analyze_operations): Examine phis. Call
+     vectorizable_live_operation for for LIVE_P stmts. Check if
+     need_to_vectorize.
+     (vect_analyze_scalar_cycles): Update documentation. Don't fail
+     vectorization - just classify the scalar cycles created by the loop
+     phis. Call vect_is_simple_reduction.
+     (vect_analyze_loop): Call to analyze_scalar_cycles moved earlier.
+     * tree-vect-transform.c (vect_create_index_for_vector_ref): Update
+     call to set_stmt_info.
+     (vect_get_vec_def_for_operand): Code reorganized - the code that
+     classifies the type of use was factored out to vect_is_simple_use.
+     (vectorizable_store, vect_is_simple_cond): Call vect_is_simple_use with
+     additional arguments.
+     (vectorizable_assignment):  Likewise. Also make sure the stmt is
+     relevant and computes a loop_vec_def.
+     (vectorizable_operation, vectorizable_load, vectorizable_condition):
+     Likewise.
+     (vectorizable_live_operation): New.
+     (vect_transform_stmt): Handle LIVE_P stmts.
+     * tree-vectorizer.c (new_stmt_vec_info): Initialize the new fields
+     STMT_VINFO_LIVE_P and STMT_VINFO_DEF_TYPE.
+     (new_loop_vec_info, destroy_loop_vec_info): Also handle phis.
+     (vect_is_simple_use): Determine the type of the def and return it
+     in a new function argument. Consider vect_reduction_def and
+     vect_induction_def, but for now these are not supported.
+     (vect_is_simple_reduction): New. Empty for now.
+     * tree-vectorizer.h (vect_def_type): New enum type.
+     (_stmt_vec_info): Added new fields - live and _stmt_vec_info.
+     (STMT_VINFO_LIVE_P, STMT_VINFO_DEF_TYPE): New accessor macros.
+     (vect_is_simple_use): New arguments added to function declaration.
+     (vect_is_simple_reduction): New function declaration.
+     (vectorizable_live_operation): New function declaration.
+
+     * tree-vect-analyze.c (vect_can_advance_ivs_p): Add debug printout.
+     (vect_can_advance_ivs_p): Likewise.
+     * tree-vect-transform.c (vect_update_ivs_after_vectorizer): Likewise.
+
  2005-05-26  Paolo Bonzini  <bonzini@gnu.org>

      * simplify-rtx.c (avoid_constant_pool_reference): Support

(See attached file: mainline.reduc.part1)

Attachment: mainline.reduc.part1
Description: Binary data