+2005-06-05 Dorit Nuzman <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-06-05 Eric Christopher <echristo@redhat.com>
* config/mips/mips.c (mips_rtx_costs): Remove unused variable.
+2005-06-05 Dorit Nuzman <dorit@il.ibm.com>
+
+ * gcc.dg/vect/vect-62: Check that second loop is not vectorized.
+ * gcc.dg/vect/vect-reduc-1.c: New.
+ * gcc.dg/vect/vect-reduc-2.c: New.
+ * gcc.dg/vect/vect-reduc-3.c: New.
+
2005-06-04 Dale Johannesen <dalej@apple.com>
* gcc.c-torture/execute/20050603-1.c: New.
}
/* Multidimensional array. Aligned. The "inner" dimensions
- are invariant in the inner loop. Store. */
+ are invariant in the inner loop. Vectorizable, but the
+ vectorizer detects that everything is invariant and that
+ the loop is better left untouched. (it should be optimized away). */
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
return main1 ();
}
-/* { dg-final { scan-tree-dump-times "vectorized 2 loops" 1 "vect" } } */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
/* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 0 "vect" } } */
+/* { dg-final { scan-tree-dump-times "not vectorized: redundant loop. no profit to vectorize." 1 "vect" } } */
/* { dg-final { cleanup-tree-dump "vect" } } */
--- /dev/null
+/* { dg-require-effective-target vect_int } */
+
+#include <stdarg.h>
+#include "tree-vect.h"
+
+#define N 16
+#define DIFF 242
+
+/* Test vectorization of reduction of unsigned-int. */
+/* Not supported yet. */
+
+int main1 (unsigned int x, unsigned int max_result)
+{
+ int i;
+ unsigned int ub[N] = {0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,45};
+ unsigned int uc[N] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
+ unsigned int udiff = 2;
+ unsigned int umax = x;
+ unsigned int umin = 10;
+
+ /* Summation. */
+ for (i = 0; i < N; i++) {
+ udiff += (ub[i] - uc[i]);
+ }
+
+ /* Maximum. */
+ for (i = 0; i < N; i++) {
+ umax = umax < uc[i] ? uc[i] : umax;
+ }
+
+ /* Minimum. */
+ for (i = 0; i < N; i++) {
+ umin = umin > uc[i] ? uc[i] : umin;
+ }
+
+ /* check results: */
+ if (udiff != DIFF)
+ abort ();
+ if (umax != max_result)
+ abort ();
+ if (umin != 0)
+ abort ();
+
+ return 0;
+}
+
+int main (void)
+{
+ check_vect ();
+
+ return main1 (100, 100);
+ return main1 (0, 15);
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 3 loops" 1 "vect" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "not vectorized: unsupported use in stmt." 3 "vect" } } */
--- /dev/null
+
+/* { dg-require-effective-target vect_int } */
+
+#include <stdarg.h>
+#include "tree-vect.h"
+
+#define N 16
+#define DIFF 242
+
+/* Test vectorization of reduction of signed-int. */
+/* Not supported yet. */
+
+int main1 (int x, int max_result)
+{
+ int i;
+ int b[N] = {0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,45};
+ int c[N] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
+ int diff = 2;
+ int max = x;
+ int min = 10;
+
+ for (i = 0; i < N; i++) {
+ diff += (b[i] - c[i]);
+ }
+
+ for (i = 0; i < N; i++) {
+ max = max < c[i] ? c[i] : max;
+ }
+
+ for (i = 0; i < N; i++) {
+ min = min > c[i] ? c[i] : min;
+ }
+
+ /* check results: */
+ if (diff != DIFF)
+ abort ();
+ if (max != max_result)
+ abort ();
+ if (min != 0)
+ abort ();
+
+ return 0;
+}
+
+int main (void)
+{
+ check_vect ();
+
+ return main1 (100, 100);
+ return main1 (0, 15);
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 3 loops" 1 "vect" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "not vectorized: unsupported use in stmt." 3 "vect" } } */
--- /dev/null
+/* { dg-require-effective-target vect_int } */
+
+#include <stdarg.h>
+#include "tree-vect.h"
+
+#define N 16
+#define DIFF 240
+
+/* Test vectorization of reduction of unsigned-int in the presence
+ of unknown-loop-bound. */
+/* Not supported yet. */
+
+int main1 (int n)
+{
+ int i;
+ unsigned int ub[N] = {0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,45};
+ unsigned int uc[N] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
+ unsigned int udiff;
+
+ udiff = 0;
+ for (i = 0; i < n; i++) {
+ udiff += (ub[i] - uc[i]);
+ }
+
+ /* check results: */
+ if (udiff != DIFF)
+ abort ();
+
+ return 0;
+}
+
+int main (void)
+{
+ check_vect ();
+
+ return main1 (N);
+ return main1 (N-1);
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "not vectorized: unsupported use in stmt." 1 "vect" } } */
/* Annotation type. */
enum tree_ann_type type;
+ /* Auxiliary info specific to a pass. At all times, this
+ should either point to valid data or be NULL. */
+ PTR GTY ((skip (""))) aux;
+
/* The value handle for this expression. Used by GVN-PRE. */
tree GTY((skip)) value_handle;
};
pass which needs statement UIDs. */
unsigned int uid;
- /* Auxiliary info specific to a pass. At all times, this
- should either point to valid data or be NULL. */
- PTR GTY ((skip (""))) aux;
-
/* Linked list of histograms for value-based profiling. This is really a
struct histogram_value*. We use void* to avoid having to export that
everywhere, and to avoid having to put it in GC memory. */
#define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
? NULL \
- : (struct lim_aux_data *) (stmt_ann (STMT)->aux))
+ : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
/* Description of a memory reference location for store motion. */
stmt = stmt1;
}
- stmt_ann (stmt)->aux = xcalloc (1, sizeof (struct lim_aux_data));
+ stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
LIM_DATA (stmt)->always_executed_in = outermost;
if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
cost = LIM_DATA (stmt)->cost;
level = LIM_DATA (stmt)->tgt_loop;
free_lim_aux_data (LIM_DATA (stmt));
- stmt_ann (stmt)->aux = NULL;
+ stmt_ann (stmt)->common.aux = NULL;
if (!level)
{
/* Emit the load & stores. */
load = build (MODIFY_EXPR, void_type_node, tmp_var, ref);
- get_stmt_ann (load)->aux = xcalloc (1, sizeof (struct lim_aux_data));
+ get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
LIM_DATA (load)->max_loop = loop;
LIM_DATA (load)->tgt_loop = loop;
static loop_vec_info vect_analyze_loop_form (struct loop *);
static bool vect_analyze_data_refs (loop_vec_info);
static bool vect_mark_stmts_to_be_vectorized (loop_vec_info);
-static bool vect_analyze_scalar_cycles (loop_vec_info);
+static void vect_analyze_scalar_cycles (loop_vec_info);
static bool vect_analyze_data_ref_accesses (loop_vec_info);
static bool vect_analyze_data_ref_dependences (loop_vec_info);
static bool vect_analyze_data_refs_alignment (loop_vec_info);
/* Utility functions for the analyses. */
static bool exist_non_indexing_operands_for_use_p (tree, tree);
-static void vect_mark_relevant (VEC(tree,heap) **, tree);
-static bool vect_stmt_relevant_p (tree, loop_vec_info);
+static void vect_mark_relevant (VEC(tree,heap) **, tree, bool, bool);
+static bool vect_stmt_relevant_p (tree, loop_vec_info, bool *, bool *);
static tree vect_get_loop_niters (struct loop *, tree *);
static bool vect_analyze_data_ref_dependence
(struct data_reference *, struct data_reference *, loop_vec_info);
gcc_assert (stmt_info);
/* skip stmts which do not need to be vectorized. */
- if (!STMT_VINFO_RELEVANT_P (stmt_info))
- continue;
+ if (!STMT_VINFO_RELEVANT_P (stmt_info)
+ && !STMT_VINFO_LIVE_P (stmt_info))
+ {
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "skip.");
+ continue;
+ }
if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))))
{
unsigned int vectorization_factor = 0;
int i;
bool ok;
+ tree phi;
+ stmt_vec_info stmt_info;
+ bool need_to_vectorize = false;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "=== vect_analyze_operations ===");
{
basic_block bb = bbs[i];
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ stmt_info = vinfo_for_stmt (phi);
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ {
+ fprintf (vect_dump, "examining phi: ");
+ print_generic_expr (vect_dump, phi, TDF_SLIM);
+ }
+
+ gcc_assert (stmt_info);
+
+ if (STMT_VINFO_LIVE_P (stmt_info))
+ {
+ /* FORNOW: not yet supported. */
+ if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
+ LOOP_LOC (loop_vinfo)))
+ fprintf (vect_dump, "not vectorized: value used after loop.");
+ return false;
+ }
+
+ gcc_assert (!STMT_VINFO_RELEVANT_P (stmt_info));
+ }
+
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
tree stmt = bsi_stmt (si);
- computations that are used only for array indexing or loop
control */
- if (!STMT_VINFO_RELEVANT_P (stmt_info))
+ if (!STMT_VINFO_RELEVANT_P (stmt_info)
+ && !STMT_VINFO_LIVE_P (stmt_info))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "irrelevant.");
continue;
}
-#ifdef ENABLE_CHECKING
if (STMT_VINFO_RELEVANT_P (stmt_info))
{
gcc_assert (!VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))));
gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
- }
-#endif
- ok = (vectorizable_operation (stmt, NULL, NULL)
- || vectorizable_assignment (stmt, NULL, NULL)
- || vectorizable_load (stmt, NULL, NULL)
- || vectorizable_store (stmt, NULL, NULL)
- || vectorizable_condition (stmt, NULL, NULL));
+ ok = (vectorizable_operation (stmt, NULL, NULL)
+ || vectorizable_assignment (stmt, NULL, NULL)
+ || vectorizable_load (stmt, NULL, NULL)
+ || vectorizable_store (stmt, NULL, NULL)
+ || vectorizable_condition (stmt, NULL, NULL));
+
+ if (!ok)
+ {
+ if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
+ LOOP_LOC (loop_vinfo)))
+ {
+ fprintf (vect_dump,
+ "not vectorized: relevant stmt not supported: ");
+ print_generic_expr (vect_dump, stmt, TDF_SLIM);
+ }
+ return false;
+ }
+ need_to_vectorize = true;
+ }
- if (!ok)
+ if (STMT_VINFO_LIVE_P (stmt_info))
{
- if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
- LOOP_LOC (loop_vinfo)))
+ ok = vectorizable_live_operation (stmt, NULL, NULL);
+
+ if (!ok)
{
- fprintf (vect_dump, "not vectorized: stmt not supported: ");
- print_generic_expr (vect_dump, stmt, TDF_SLIM);
+ if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
+ LOOP_LOC (loop_vinfo)))
+ {
+ fprintf (vect_dump,
+ "not vectorized: live stmt not supported: ");
+ print_generic_expr (vect_dump, stmt, TDF_SLIM);
+ }
+ return false;
}
- return false;
}
- }
- }
+ } /* stmts in bb */
+ } /* bbs */
/* TODO: Analyze cost. Decide if worth while to vectorize. */
+ /* All operations in the loop are either irrelevant (deal with loop
+ control, or dead), or only used outside the loop and can be moved
+ out of the loop (e.g. invariants, inductions). The loop can be
+ optimized away by scalar optimizations. We're better off not
+ touching this loop. */
+ if (!need_to_vectorize)
+ {
+ if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
+ fprintf (vect_dump,
+ "All the computation can be taken out of the loop.");
+ if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
+ LOOP_LOC (loop_vinfo)))
+ fprintf (vect_dump,
+ "not vectorized: redundant loop. no profit to vectorize.");
+ return false;
+ }
+
if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
&& vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump,
/* Function vect_analyze_scalar_cycles.
Examine the cross iteration def-use cycles of scalar variables, by
- analyzing the loop (scalar) PHIs; verify that the cross iteration def-use
- cycles that they represent do not impede vectorization.
+ analyzing the loop (scalar) PHIs; Classify each cycle as one of the
+ following: invariant, induction, reduction, unknown.
+
+ Some forms of scalar cycles are not yet supported.
+
+ Example1: reduction: (unsupported yet)
- FORNOW: Reduction as in the following loop, is not supported yet:
loop1:
for (i=0; i<N; i++)
sum += a[i];
- The cross-iteration cycle corresponding to variable 'sum' will be
- considered too complicated and will impede vectorization.
- FORNOW: Induction as in the following loop, is not supported yet:
+ Example2: induction: (unsupported yet)
+
loop2:
for (i=0; i<N; i++)
a[i] = i;
- However, the following loop *is* vectorizable:
+ Note: the following loop *is* vectorizable:
+
loop3:
for (i=0; i<N; i++)
a[i] = b[i];
- In both loops there exists a def-use cycle for the variable i:
+ even though it has a def-use cycle caused by the induction variable i:
+
loop: i_2 = PHI (i_0, i_1)
a[i_2] = ...;
i_1 = i_2 + 1;
GOTO loop;
- The evolution of the above cycle is considered simple enough,
- however, we also check that the cycle does not need to be
- vectorized, i.e - we check that the variable that this cycle
- defines is only used for array indexing or in stmts that do not
- need to be vectorized. This is not the case in loop2, but it
- *is* the case in loop3. */
+ because the def-use cycle in loop3 is considered "not relevant" - i.e.,
+ it does not need to be vectorized because it is only used for array
+ indexing (see 'mark_stmts_to_be_vectorized'). The def-use cycle in
+ loop2 on the other hand is relevant (it is being written to memory).
+*/
-static bool
+static void
vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
{
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree access_fn = NULL;
+ tree def = PHI_RESULT (phi);
+ stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
+ tree reduc_stmt;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
/* Skip virtual phi's. The data dependences that are associated with
virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
- if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
+ if (!is_gimple_reg (SSA_NAME_VAR (def)))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "virtual phi. skip.");
continue;
}
- /* Analyze the evolution function. */
-
- /* FORNOW: The only scalar cross-iteration cycles that we allow are
- those of loop induction variables; This property is verified here.
+ STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
- Furthermore, if that induction variable is used in an operation
- that needs to be vectorized (i.e, is not solely used to index
- arrays and check the exit condition) - we do not support its
- vectorization yet. This property is verified in vect_is_simple_use,
- during vect_analyze_operations. */
+ /* Analyze the evolution function. */
- access_fn = /* instantiate_parameters
- (loop,*/
- analyze_scalar_evolution (loop, PHI_RESULT (phi));
+ access_fn = analyze_scalar_evolution (loop, def);
if (!access_fn)
- {
- if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
- LOOP_LOC (loop_vinfo)))
- fprintf (vect_dump, "not vectorized: unsupported scalar cycle.");
- return false;
- }
+ continue;
if (vect_print_dump_info (REPORT_DETAILS,
LOOP_LOC (loop_vinfo)))
print_generic_expr (vect_dump, access_fn, TDF_SLIM);
}
- if (!vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy))
+ if (vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy))
{
- if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
- LOOP_LOC (loop_vinfo)))
- fprintf (vect_dump, "not vectorized: unsupported scalar cycle.");
- return false;
+ if (vect_print_dump_info (REPORT_DETAILS,LOOP_LOC (loop_vinfo)))
+ fprintf (vect_dump, "Detected induction.");
+ STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
+ continue;
}
+
+ /* TODO: handle invariant phis */
+
+ reduc_stmt = vect_is_simple_reduction (loop, phi);
+ if (reduc_stmt)
+ {
+ if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
+ fprintf (vect_dump, "Detected reduction.");
+ STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
+ STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
+ vect_reduction_def;
+ }
+ else
+ if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
+ fprintf (vect_dump, "Unknown def-use cycle pattern.");
+
}
- return true;
+ return;
}
Mark STMT as "relevant for vectorization" and add it to WORKLIST. */
static void
-vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt)
+vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt,
+ bool relevant_p, bool live_p)
{
- stmt_vec_info stmt_info;
+ stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+ bool save_relevant_p = STMT_VINFO_RELEVANT_P (stmt_info);
+ bool save_live_p = STMT_VINFO_LIVE_P (stmt_info);
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- fprintf (vect_dump, "mark relevant.");
+ fprintf (vect_dump, "mark relevant %d, live %d.",relevant_p, live_p);
- if (TREE_CODE (stmt) == PHI_NODE)
- {
- VEC_safe_push (tree, heap, *worklist, stmt);
- return;
- }
+ STMT_VINFO_LIVE_P (stmt_info) |= live_p;
- stmt_info = vinfo_for_stmt (stmt);
+ if (TREE_CODE (stmt) == PHI_NODE)
+ /* Don't mark as relevant because it's not going to vectorized. */
+ return;
- if (!stmt_info)
- {
- if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- {
- fprintf (vect_dump, "mark relevant: no stmt info!!.");
- print_generic_expr (vect_dump, stmt, TDF_SLIM);
- }
- return;
- }
+ STMT_VINFO_RELEVANT_P (stmt_info) |= relevant_p;
- if (STMT_VINFO_RELEVANT_P (stmt_info))
+ if (STMT_VINFO_RELEVANT_P (stmt_info) == save_relevant_p
+ && STMT_VINFO_LIVE_P (stmt_info) == save_live_p)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- fprintf (vect_dump, "already marked relevant.");
+ fprintf (vect_dump, "already marked relevant/live.");
return;
}
- STMT_VINFO_RELEVANT_P (stmt_info) = 1;
VEC_safe_push (tree, heap, *worklist, stmt);
}
CHECKME: what other side effects would the vectorizer allow? */
static bool
-vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo)
+vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo,
+ bool *relevant_p, bool *live_p)
{
struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
ssa_op_iter op_iter;
use_operand_p use_p;
def_operand_p def_p;
+ *relevant_p = false;
+ *live_p = false;
+
/* cond stmt other than loop exit cond. */
if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo)))
- return true;
+ *relevant_p = true;
/* changing memory. */
if (TREE_CODE (stmt) != PHI_NODE)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
- return true;
+ *relevant_p = true;
}
/* uses outside the loop. */
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
- return true;
+
+ /* We expect all such uses to be in the loop exit phis
+ (because of loop closed form) */
+ gcc_assert (TREE_CODE (USE_STMT (use_p)) == PHI_NODE);
+ gcc_assert (bb == loop->single_exit->dest);
+
+ *live_p = true;
}
}
}
- return false;
+ return (*live_p || *relevant_p);
}
unsigned int nbbs = loop->num_nodes;
block_stmt_iterator si;
tree stmt, use;
+ stmt_ann_t ann;
ssa_op_iter iter;
unsigned int i;
- int j;
- stmt_vec_info stmt_info;
+ stmt_vec_info stmt_vinfo;
basic_block bb;
tree phi;
+ bool relevant_p, live_p;
+ tree def, def_stmt;
+ enum vect_def_type dt;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
+ worklist = VEC_alloc (tree, heap, 64);
+
+ /* 1. Init worklist. */
+
bb = loop->header;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
print_generic_expr (vect_dump, phi, TDF_SLIM);
}
- if (vect_stmt_relevant_p (phi, loop_vinfo))
- {
- if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
- LOOP_LOC (loop_vinfo)))
- fprintf (vect_dump, "unsupported reduction/induction.");
- return false;
- }
+ if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant_p, &live_p))
+ vect_mark_relevant (&worklist, phi, relevant_p, live_p);
}
- worklist = VEC_alloc (tree, heap, 64);
-
- /* 1. Init worklist. */
-
for (i = 0; i < nbbs; i++)
{
bb = bbs[i];
print_generic_expr (vect_dump, stmt, TDF_SLIM);
}
- stmt_info = vinfo_for_stmt (stmt);
- STMT_VINFO_RELEVANT_P (stmt_info) = 0;
-
- if (vect_stmt_relevant_p (stmt, loop_vinfo))
- vect_mark_relevant (&worklist, stmt);
+ if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant_p, &live_p))
+ vect_mark_relevant (&worklist, stmt, relevant_p, live_p);
}
}
print_generic_expr (vect_dump, stmt, TDF_SLIM);
}
- /* Examine the USES in this statement. Mark all the statements which
- feed this statement's uses as "relevant", unless the USE is used as
- an array index. */
+ /* Examine the USEs of STMT. For each ssa-name USE thta is defined
+ in the loop, mark the stmt that defines it (DEF_STMT) as
+ relevant/irrelevant and live/dead according to the liveness and
+ relevance properties of STMT.
+ */
- if (TREE_CODE (stmt) == PHI_NODE)
- {
- /* follow the def-use chain inside the loop. */
- for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
- {
- tree arg = PHI_ARG_DEF (stmt, j);
- tree def_stmt = NULL_TREE;
- basic_block bb;
- if (!vect_is_simple_use (arg, loop_vinfo, &def_stmt))
- {
- if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
- LOOP_LOC (loop_vinfo)))
- fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
- VEC_free (tree, heap, worklist);
- return false;
- }
- if (!def_stmt)
- continue;
+ gcc_assert (TREE_CODE (stmt) != PHI_NODE);
- if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- {
- fprintf (vect_dump, "worklist: def_stmt: ");
- print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
- }
+ ann = stmt_ann (stmt);
+ stmt_vinfo = vinfo_for_stmt (stmt);
- bb = bb_for_stmt (def_stmt);
- if (flow_bb_inside_loop_p (loop, bb))
- vect_mark_relevant (&worklist, def_stmt);
- }
- }
+ relevant_p = STMT_VINFO_RELEVANT_P (stmt_vinfo);
+ live_p = STMT_VINFO_LIVE_P (stmt_vinfo);
+
+ /* Generally, the liveness and relevance properties of STMT are
+ propagated to the DEF_STMTs of its USEs:
+ STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p
+ STMT_VINFO_RELEVANT_P (DEF_STMT_info) <-- relevant_p
+
+ Exceptions:
+
+ - if USE is used only for address computations (e.g. array indexing),
+ which does not need to be directly vectorized, then the
+ liveness/relevance of the respective DEF_STMT is left unchanged.
+
+ - if STMT has been identified as defining a reduction variable, then:
+ STMT_VINFO_LIVE_P (DEF_STMT_info) <-- false
+ STMT_VINFO_RELEVANT_P (DEF_STMT_info) <-- true
+ because even though STMT is classified as live (since it defines a
+ value that is used across loop iterations) and irrelevant (since it
+ is not used inside the loop), it will be vectorized, and therefore
+ the corresponding DEF_STMTs need to marked as relevant.
+ */
+
+ if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
+ {
+ gcc_assert (!relevant_p && live_p);
+ relevant_p = true;
+ live_p = false;
+ }
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
-
/* We are only interested in uses that need to be vectorized. Uses
that are used for address computation are not considered relevant.
*/
if (exist_non_indexing_operands_for_use_p (use, stmt))
{
- tree def_stmt = NULL_TREE;
- basic_block bb;
- if (!vect_is_simple_use (use, loop_vinfo, &def_stmt))
+ if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
- fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
+ fprintf (vect_dump,
+ "not vectorized: unsupported use in stmt.");
VEC_free (tree, heap, worklist);
return false;
}
- if (!def_stmt)
+ if (!def_stmt || IS_EMPTY_STMT (def_stmt))
continue;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
}
bb = bb_for_stmt (def_stmt);
- if (flow_bb_inside_loop_p (loop, bb))
- vect_mark_relevant (&worklist, def_stmt);
+ if (!flow_bb_inside_loop_p (loop, bb))
+ continue;
+
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ {
+ fprintf (vect_dump, "def_stmt: ");
+ print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
+ }
+
+ vect_mark_relevant (&worklist, def_stmt, relevant_p, live_p);
}
}
} /* while worklist */
/* Analyze phi functions of the loop header. */
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "=== vect_can_advance_ivs_p ===");
+
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree access_fn = NULL;
evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
if (evolution_part == NULL_TREE)
- return false;
+ {
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "No evolution.");
+ return false;
+ }
/* FORNOW: We do not transform initial conditions of IVs
which evolution functions are a polynomial of degree >= 2. */
return NULL;
}
+ /* Classify all cross-iteration scalar data-flow cycles.
+ Cross-iteration cycles caused by virtual phis are analyzed separately. */
+
+ vect_analyze_scalar_cycles (loop_vinfo);
+
/* Data-flow analysis to detect stmts that do not need to be vectorized. */
ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
return NULL;
}
- /* Check that all cross-iteration scalar data-flow cycles are OK.
- Cross-iteration cycles caused by virtual phis are analyzed separately. */
-
- ok = vect_analyze_scalar_cycles (loop_vinfo);
- if (!ok)
- {
- if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
- fprintf (vect_dump, "bad scalar cycle.");
- destroy_loop_vec_info (loop_vinfo);
- return NULL;
- }
-
ok = vect_determine_vectorization_factor (loop_vinfo);
if (!ok)
{
create_iv (init, step, NULL_TREE, loop, &incr_bsi, insert_after,
&indx_before_incr, &indx_after_incr);
incr = bsi_stmt (incr_bsi);
- set_stmt_info (stmt_ann (incr), new_stmt_vec_info (incr, loop_vinfo));
+ set_stmt_info ((tree_ann_t)stmt_ann (incr), new_stmt_vec_info (incr, loop_vinfo));
return indx_before_incr;
}
tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
int nunits = TYPE_VECTOR_SUBPARTS (vectype);
loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
- struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
- basic_block bb;
tree vec_inv;
+ tree vec_cst;
tree t = NULL_TREE;
tree def;
int i;
+ enum vect_def_type dt;
+ bool is_simple_use;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
print_generic_expr (vect_dump, op, TDF_SLIM);
}
- /** ===> Case 1: operand is a constant. **/
-
- if (TREE_CODE (op) == INTEGER_CST || TREE_CODE (op) == REAL_CST)
+ is_simple_use = vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt);
+ gcc_assert (is_simple_use);
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
- /* Create 'vect_cst_ = {cst,cst,...,cst}' */
-
- tree vec_cst;
-
- /* Build a tree with vector elements. */
- if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits);
-
- for (i = nunits - 1; i >= 0; --i)
+ if (def)
{
- t = tree_cons (NULL_TREE, op, t);
+ fprintf (vect_dump, "def = ");
+ print_generic_expr (vect_dump, def, TDF_SLIM);
+ }
+ if (def_stmt)
+ {
+ fprintf (vect_dump, " def_stmt = ");
+ print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
}
- vec_cst = build_vector (vectype, t);
- return vect_init_vector (stmt, vec_cst);
- }
-
- gcc_assert (TREE_CODE (op) == SSA_NAME);
-
- /** ===> Case 2: operand is an SSA_NAME - find the stmt that defines it. **/
-
- def_stmt = SSA_NAME_DEF_STMT (op);
- def_stmt_info = vinfo_for_stmt (def_stmt);
-
- if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- {
- fprintf (vect_dump, "vect_get_vec_def_for_operand: def_stmt: ");
- print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
- }
-
-
- /** ==> Case 2.1: operand is defined inside the loop. **/
-
- if (def_stmt_info)
- {
- /* Get the def from the vectorized stmt. */
-
- vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
- gcc_assert (vec_stmt);
- vec_oprnd = TREE_OPERAND (vec_stmt, 0);
- return vec_oprnd;
}
+ /* FORNOW */
+ gcc_assert (dt != vect_reduction_def);
- /** ==> Case 2.2: operand is defined by the loop-header phi-node -
- it is a reduction/induction. **/
-
- bb = bb_for_stmt (def_stmt);
- if (TREE_CODE (def_stmt) == PHI_NODE && flow_bb_inside_loop_p (loop, bb))
+ switch (dt)
{
- if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- fprintf (vect_dump, "reduction/induction - unsupported.");
- internal_error ("no support for reduction/induction"); /* FORNOW */
- }
-
+ /* Case 1: operand is a constant. */
+ case vect_constant_def:
+ {
+ /* Create 'vect_cst_ = {cst,cst,...,cst}' */
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits);
+
+ for (i = nunits - 1; i >= 0; --i)
+ {
+ t = tree_cons (NULL_TREE, op, t);
+ }
+ vec_cst = build_vector (vectype, t);
+ return vect_init_vector (stmt, vec_cst);
+ }
+
+ /* Case 2: operand is defined outside the loop - loop invariant. */
+ case vect_invariant_def:
+ {
+ /* Create 'vec_inv = {inv,inv,..,inv}' */
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "Create vector_inv.");
+
+ for (i = nunits - 1; i >= 0; --i)
+ {
+ t = tree_cons (NULL_TREE, def, t);
+ }
+
+ vec_inv = build_constructor (vectype, t);
+ return vect_init_vector (stmt, vec_inv);
+ }
+
+ /* Case 3: operand is defined inside the loop. */
+ case vect_loop_def:
+ {
+ /* Get the def from the vectorized stmt. */
+ def_stmt_info = vinfo_for_stmt (def_stmt);
+ vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
+ gcc_assert (vec_stmt);
+ vec_oprnd = TREE_OPERAND (vec_stmt, 0);
+ return vec_oprnd;
+ }
+
+ /* Case 4: operand is defined by loop-header phi - induction. */
+ case vect_induction_def:
+ {
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "induction - unsupported.");
+ internal_error ("no support for induction"); /* FORNOW */
+ }
- /** ==> Case 2.3: operand is defined outside the loop -
- it is a loop invariant. */
-
- switch (TREE_CODE (def_stmt))
- {
- case PHI_NODE:
- def = PHI_RESULT (def_stmt);
- break;
- case MODIFY_EXPR:
- def = TREE_OPERAND (def_stmt, 0);
- break;
- case NOP_EXPR:
- def = TREE_OPERAND (def_stmt, 0);
- gcc_assert (IS_EMPTY_STMT (def_stmt));
- def = op;
- break;
default:
- if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- {
- fprintf (vect_dump, "unsupported defining stmt: ");
- print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
- }
- internal_error ("unsupported defining stmt");
- }
-
- /* Build a tree with vector elements.
- Create 'vec_inv = {inv,inv,..,inv}' */
-
- if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- fprintf (vect_dump, "Create vector_inv.");
-
- for (i = nunits - 1; i >= 0; --i)
- {
- t = tree_cons (NULL_TREE, def, t);
+ gcc_unreachable ();
}
-
- vec_inv = build_constructor (vectype, t);
- return vect_init_vector (stmt, vec_inv);
}
tree vectype = STMT_VINFO_VECTYPE (stmt_info);
loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
tree new_temp;
+ tree def, def_stmt;
+ enum vect_def_type dt;
/* Is vectorizable assignment? */
+ if (!STMT_VINFO_RELEVANT_P (stmt_info))
+ return false;
+
+ gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
return false;
op = TREE_OPERAND (stmt, 1);
- if (!vect_is_simple_use (op, loop_vinfo, NULL))
+ if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "use not simple.");
}
}
+
/* Function vectorizable_operation.
Check if STMT performs a binary or unary operation that can be vectorized.
int op_type;
tree op;
optab optab;
+ tree def, def_stmt;
+ enum vect_def_type dt;
/* Is STMT a vectorizable binary/unary operation? */
+ if (!STMT_VINFO_RELEVANT_P (stmt_info))
+ return false;
+
+ gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
+
+ if (STMT_VINFO_LIVE_P (stmt_info))
+ {
+ /* FORNOW: not yet supported. */
+ if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
+ fprintf (vect_dump, "value used after loop.");
+ return false;
+ }
+
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
for (i = 0; i < op_type; i++)
{
op = TREE_OPERAND (operation, i);
- if (!vect_is_simple_use (op, loop_vinfo, NULL))
+ if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "use not simple.");
enum machine_mode vec_mode;
tree dummy;
enum dr_alignment_support alignment_support_cheme;
- tree def;
ssa_op_iter iter;
+ tree def, def_stmt;
+ enum vect_def_type dt;
/* Is vectorizable store? */
return false;
op = TREE_OPERAND (stmt, 1);
- if (!vect_is_simple_use (op, loop_vinfo, NULL))
+ if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "use not simple.");
enum dr_alignment_support alignment_support_cheme;
/* Is vectorizable load? */
+ if (!STMT_VINFO_RELEVANT_P (stmt_info))
+ return false;
+
+ gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
+
+ if (STMT_VINFO_LIVE_P (stmt_info))
+ {
+ /* FORNOW: not yet supported. */
+ if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
+ fprintf (vect_dump, "value used after loop.");
+ return false;
+ }
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
return true;
}
+
+/* Function vectorizable_live_operation.
+
+ STMT computes a value that is used outside the loop. Check if
+ it can be supported. */
+
+bool
+vectorizable_live_operation (tree stmt,
+ block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
+ tree *vec_stmt ATTRIBUTE_UNUSED)
+{
+ tree operation;
+ stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+ loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
+ int i;
+ enum tree_code code;
+ int op_type;
+ tree op;
+ tree def, def_stmt;
+ enum vect_def_type dt;
+
+ if (!STMT_VINFO_LIVE_P (stmt_info))
+ return false;
+
+ if (TREE_CODE (stmt) != MODIFY_EXPR)
+ return false;
+
+ if (TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
+ return false;
+
+ operation = TREE_OPERAND (stmt, 1);
+ code = TREE_CODE (operation);
+
+ op_type = TREE_CODE_LENGTH (code);
+
+ /* FORNOW: support only if all uses are invariant. This means
+ that the scalar operations can remain in place, unvectorized.
+ The original last scalar value that they compute will be used. */
+
+ for (i = 0; i < op_type; i++)
+ {
+ op = TREE_OPERAND (operation, i);
+ if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
+ {
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "use not simple.");
+ return false;
+ }
+
+ if (dt != vect_invariant_def && dt != vect_constant_def)
+ return false;
+ }
+
+ /* No transformation is required for the cases we currently support. */
+ return true;
+}
+
+
/* Function vect_is_simple_cond.
Input:
vect_is_simple_cond (tree cond, loop_vec_info loop_vinfo)
{
tree lhs, rhs;
+ tree def;
+ enum vect_def_type dt;
if (!COMPARISON_CLASS_P (cond))
return false;
if (TREE_CODE (lhs) == SSA_NAME)
{
tree lhs_def_stmt = SSA_NAME_DEF_STMT (lhs);
- if (!vect_is_simple_use (lhs, loop_vinfo, &lhs_def_stmt))
+ if (!vect_is_simple_use (lhs, loop_vinfo, &lhs_def_stmt, &def, &dt))
return false;
}
else if (TREE_CODE (lhs) != INTEGER_CST && TREE_CODE (lhs) != REAL_CST)
if (TREE_CODE (rhs) == SSA_NAME)
{
tree rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
- if (!vect_is_simple_use (rhs, loop_vinfo, &rhs_def_stmt))
+ if (!vect_is_simple_use (rhs, loop_vinfo, &rhs_def_stmt, &def, &dt))
return false;
}
else if (TREE_CODE (rhs) != INTEGER_CST && TREE_CODE (rhs) != REAL_CST)
tree new_temp;
loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
enum machine_mode vec_mode;
+ tree def;
+ enum vect_def_type dt;
if (!STMT_VINFO_RELEVANT_P (stmt_info))
return false;
+ gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
+
+ if (STMT_VINFO_LIVE_P (stmt_info))
+ {
+ /* FORNOW: not yet supported. */
+ if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
+ fprintf (vect_dump, "value used after loop.");
+ return false;
+ }
+
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
if (TREE_CODE (then_clause) == SSA_NAME)
{
tree then_def_stmt = SSA_NAME_DEF_STMT (then_clause);
- if (!vect_is_simple_use (then_clause, loop_vinfo, &then_def_stmt))
+ if (!vect_is_simple_use (then_clause, loop_vinfo,
+ &then_def_stmt, &def, &dt))
return false;
}
else if (TREE_CODE (then_clause) != INTEGER_CST
if (TREE_CODE (else_clause) == SSA_NAME)
{
tree else_def_stmt = SSA_NAME_DEF_STMT (else_clause);
- if (!vect_is_simple_use (else_clause, loop_vinfo, &else_def_stmt))
+ if (!vect_is_simple_use (else_clause, loop_vinfo,
+ &else_def_stmt, &def, &dt))
return false;
}
else if (TREE_CODE (else_clause) != INTEGER_CST
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
bool done;
- switch (STMT_VINFO_TYPE (stmt_info))
+ if (STMT_VINFO_RELEVANT_P (stmt_info))
{
- case op_vec_info_type:
- done = vectorizable_operation (stmt, bsi, &vec_stmt);
- gcc_assert (done);
- break;
-
- case assignment_vec_info_type:
- done = vectorizable_assignment (stmt, bsi, &vec_stmt);
- gcc_assert (done);
- break;
-
- case load_vec_info_type:
- done = vectorizable_load (stmt, bsi, &vec_stmt);
- gcc_assert (done);
- break;
-
- case store_vec_info_type:
- done = vectorizable_store (stmt, bsi, &vec_stmt);
- gcc_assert (done);
- is_store = true;
- break;
+ switch (STMT_VINFO_TYPE (stmt_info))
+ {
+ case op_vec_info_type:
+ done = vectorizable_operation (stmt, bsi, &vec_stmt);
+ gcc_assert (done);
+ break;
+
+ case assignment_vec_info_type:
+ done = vectorizable_assignment (stmt, bsi, &vec_stmt);
+ gcc_assert (done);
+ break;
+
+ case load_vec_info_type:
+ done = vectorizable_load (stmt, bsi, &vec_stmt);
+ gcc_assert (done);
+ break;
+
+ case store_vec_info_type:
+ done = vectorizable_store (stmt, bsi, &vec_stmt);
+ gcc_assert (done);
+ is_store = true;
+ break;
+
+ case condition_vec_info_type:
+ done = vectorizable_condition (stmt, bsi, &vec_stmt);
+ gcc_assert (done);
+ break;
+
+ default:
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "stmt not supported.");
+ gcc_unreachable ();
+ }
+
+ STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
+ }
- case condition_vec_info_type:
- done = vectorizable_condition (stmt, bsi, &vec_stmt);
+ if (STMT_VINFO_LIVE_P (stmt_info))
+ {
+ done = vectorizable_live_operation (stmt, bsi, &vec_stmt);
gcc_assert (done);
- break;
-
- default:
- if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- fprintf (vect_dump, "stmt not supported.");
- gcc_unreachable ();
}
- STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
-
- return is_store;
+ return is_store;
}
tree var, stmt, ni, ni_name;
block_stmt_iterator last_bsi;
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ {
+ fprintf (vect_dump, "vect_update_ivs_after_vectorizer: phi: ");
+ print_generic_expr (vect_dump, phi, TDF_SLIM);
+ }
+
/* Skip virtual phi's. */
if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
{
/* Free the attached stmt_vec_info and remove the stmt. */
stmt_ann_t ann = stmt_ann (stmt);
free (stmt_info);
- set_stmt_info (ann, NULL);
+ set_stmt_info ((tree_ann_t)ann, NULL);
bsi_remove (&si);
continue;
}
STMT_VINFO_STMT (res) = stmt;
STMT_VINFO_LOOP_VINFO (res) = loop_vinfo;
STMT_VINFO_RELEVANT_P (res) = 0;
+ STMT_VINFO_LIVE_P (res) = 0;
STMT_VINFO_VECTYPE (res) = NULL;
STMT_VINFO_VEC_STMT (res) = NULL;
STMT_VINFO_DATA_REF (res) = NULL;
+ if (TREE_CODE (stmt) == PHI_NODE)
+ STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
+ else
+ STMT_VINFO_DEF_TYPE (res) = vect_loop_def;
STMT_VINFO_MEMTAG (res) = NULL;
STMT_VINFO_PTR_INFO (res) = NULL;
STMT_VINFO_SUBVARS (res) = NULL;
for (i = 0; i < loop->num_nodes; i++)
{
basic_block bb = bbs[i];
+ tree phi;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ tree_ann_t ann = get_tree_ann (phi);
+ set_stmt_info (ann, new_stmt_vec_info (phi, res));
+ }
+
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
tree stmt = bsi_stmt (si);
stmt_ann_t ann;
ann = stmt_ann (stmt);
- set_stmt_info (ann, new_stmt_vec_info (stmt, res));
+ set_stmt_info ((tree_ann_t)ann, new_stmt_vec_info (stmt, res));
}
}
for (j = 0; j < nbbs; j++)
{
basic_block bb = bbs[j];
+ tree phi;
+ stmt_vec_info stmt_info;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ tree_ann_t ann = get_tree_ann (phi);
+
+ stmt_info = vinfo_for_stmt (phi);
+ free (stmt_info);
+ set_stmt_info (ann, NULL);
+ }
+
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
tree stmt = bsi_stmt (si);
stmt_ann_t ann = stmt_ann (stmt);
+
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
free (stmt_info);
- set_stmt_info (ann, NULL);
+ set_stmt_info ((tree_ann_t)ann, NULL);
}
}
in reduction/induction computations). */
bool
-vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def)
+vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def_stmt,
+ tree *def, enum vect_def_type *dt)
{
- tree def_stmt;
basic_block bb;
+ stmt_vec_info stmt_vinfo;
struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
- if (def)
- *def = NULL_TREE;
-
+ *def_stmt = NULL_TREE;
+ *def = NULL_TREE;
+
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ {
+ fprintf (vect_dump, "vect_is_simple_use: operand ");
+ print_generic_expr (vect_dump, operand, TDF_SLIM);
+ }
+
if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST)
- return true;
-
+ {
+ *dt = vect_constant_def;
+ return true;
+ }
+
if (TREE_CODE (operand) != SSA_NAME)
- return false;
-
- def_stmt = SSA_NAME_DEF_STMT (operand);
- if (def_stmt == NULL_TREE )
+ {
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "not ssa-name.");
+ return false;
+ }
+
+ *def_stmt = SSA_NAME_DEF_STMT (operand);
+ if (*def_stmt == NULL_TREE )
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "no def_stmt.");
return false;
}
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ {
+ fprintf (vect_dump, "def_stmt: ");
+ print_generic_expr (vect_dump, *def_stmt, TDF_SLIM);
+ }
+
/* empty stmt is expected only in case of a function argument.
(Otherwise - we expect a phi_node or a modify_expr). */
- if (IS_EMPTY_STMT (def_stmt))
+ if (IS_EMPTY_STMT (*def_stmt))
{
- tree arg = TREE_OPERAND (def_stmt, 0);
+ tree arg = TREE_OPERAND (*def_stmt, 0);
if (TREE_CODE (arg) == INTEGER_CST || TREE_CODE (arg) == REAL_CST)
- return true;
+ {
+ *def = operand;
+ *dt = vect_invariant_def;
+ return true;
+ }
+
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- {
- fprintf (vect_dump, "Unexpected empty stmt: ");
- print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
- }
- return false;
+ fprintf (vect_dump, "Unexpected empty stmt.");
+ return false;
}
- /* phi_node inside the loop indicates an induction/reduction pattern.
- This is not supported yet. */
- bb = bb_for_stmt (def_stmt);
- if (TREE_CODE (def_stmt) == PHI_NODE && flow_bb_inside_loop_p (loop, bb))
+ bb = bb_for_stmt (*def_stmt);
+ if (!flow_bb_inside_loop_p (loop, bb))
+ *dt = vect_invariant_def;
+ else
+ {
+ stmt_vinfo = vinfo_for_stmt (*def_stmt);
+ *dt = STMT_VINFO_DEF_TYPE (stmt_vinfo);
+ }
+
+ if (*dt == vect_unknown_def_type)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
- fprintf (vect_dump, "reduction/induction - unsupported.");
- return false; /* FORNOW: not supported yet. */
+ fprintf (vect_dump, "Unsupported pattern.");
+ return false;
}
- /* Expecting a modify_expr or a phi_node. */
- if (TREE_CODE (def_stmt) == MODIFY_EXPR
- || TREE_CODE (def_stmt) == PHI_NODE)
+ /* stmts inside the loop that have been identified as performing
+ a reduction operation cannot have uses in the loop. */
+ if (*dt == vect_reduction_def && TREE_CODE (*def_stmt) != PHI_NODE)
{
- if (def)
- *def = def_stmt;
- return true;
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "reduction used in loop.");
+ return false;
+ }
+
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "type of def: %d.",*dt);
+
+ switch (TREE_CODE (*def_stmt))
+ {
+ case PHI_NODE:
+ *def = PHI_RESULT (*def_stmt);
+ gcc_assert (*dt == vect_induction_def || *dt == vect_reduction_def
+ || *dt == vect_invariant_def);
+ break;
+
+ case MODIFY_EXPR:
+ *def = TREE_OPERAND (*def_stmt, 0);
+ gcc_assert (*dt == vect_loop_def || *dt == vect_invariant_def);
+ break;
+
+ default:
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "unsupported defining stmt: ");
+ return false;
}
- return false;
+ if (*dt == vect_induction_def)
+ {
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "induction not supported.");
+ return false;
+ }
+
+ return true;
+}
+
+
+/* Function vect_is_simple_reduction
+
+ TODO:
+ Detect a cross-iteration def-use cucle that represents a simple
+ reduction computation. We look for the followng pattern:
+
+ loop_header:
+ a1 = phi < a0, a2 >
+ a3 = ...
+ a2 = operation (a3, a1)
+
+ such that:
+ 1. operation is...
+ 2. no uses for a2 in the loop (elsewhere) */
+
+tree
+vect_is_simple_reduction (struct loop *loop ATTRIBUTE_UNUSED,
+ tree phi ATTRIBUTE_UNUSED)
+{
+ /* FORNOW */
+ if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+ fprintf (vect_dump, "reduction: unknown pattern.");
+
+ return NULL_TREE;
}
dr_aligned
};
+/* Define type of def-use cross-iteraiton cycle. */
+enum vect_def_type {
+ vect_constant_def,
+ vect_invariant_def,
+ vect_loop_def,
+ vect_induction_def,
+ vect_reduction_def,
+ vect_unknown_def_type
+};
+
/* Define verbosity levels. */
enum verbosity_levels {
REPORT_NONE,
indicates whether the stmt needs to be vectorized. */
bool relevant;
+ /* Indicates whether this stmts is part of a computation whose result is
+ used outside the loop. */
+ bool live;
+
/* The vector type to be used. */
tree vectype;
/* Alignment information. The offset of the data-reference from its base
in bytes. */
tree misalignment;
+
+ /* Classify the def of this stmt. */
+ enum vect_def_type def_type;
+
} *stmt_vec_info;
/* Access Functions. */
#define STMT_VINFO_STMT(S) (S)->stmt
#define STMT_VINFO_LOOP_VINFO(S) (S)->loop_vinfo
#define STMT_VINFO_RELEVANT_P(S) (S)->relevant
+#define STMT_VINFO_LIVE_P(S) (S)->live
#define STMT_VINFO_VECTYPE(S) (S)->vectype
#define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt
#define STMT_VINFO_DATA_REF(S) (S)->data_ref_info
#define STMT_VINFO_VECT_STEP(S) (S)->step
#define STMT_VINFO_VECT_BASE_ALIGNED_P(S) (S)->base_aligned_p
#define STMT_VINFO_VECT_MISALIGNMENT(S) (S)->misalignment
+#define STMT_VINFO_DEF_TYPE(S) (S)->def_type
-static inline void set_stmt_info (stmt_ann_t ann, stmt_vec_info stmt_info);
+static inline void set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info);
static inline stmt_vec_info vinfo_for_stmt (tree stmt);
static inline void
-set_stmt_info (stmt_ann_t ann, stmt_vec_info stmt_info)
+set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info)
{
if (ann)
- ann->aux = (char *) stmt_info;
+ ann->common.aux = (char *) stmt_info;
}
static inline stmt_vec_info
vinfo_for_stmt (tree stmt)
{
- stmt_ann_t ann = stmt_ann (stmt);
- return ann ? (stmt_vec_info) ann->aux : NULL;
+ tree_ann_t ann = tree_ann (stmt);
+ return ann ? (stmt_vec_info) ann->common.aux : NULL;
}
/*-----------------------------------------------------------------*/
/** In tree-vectorizer.c **/
extern tree vect_strip_conversion (tree);
extern tree get_vectype_for_scalar_type (tree);
-extern bool vect_is_simple_use (tree , loop_vec_info, tree *);
+extern bool vect_is_simple_use (tree, loop_vec_info, tree *, tree *,
+ enum vect_def_type *);
extern bool vect_is_simple_iv_evolution (unsigned, tree, tree *, tree *);
+extern tree vect_is_simple_reduction (struct loop *, tree);
extern bool vect_can_force_dr_alignment_p (tree, unsigned int);
extern enum dr_alignment_support vect_supportable_dr_alignment
(struct data_reference *);
extern bool vectorizable_operation (tree, block_stmt_iterator *, tree *);
extern bool vectorizable_assignment (tree, block_stmt_iterator *, tree *);
extern bool vectorizable_condition (tree, block_stmt_iterator *, tree *);
+extern bool vectorizable_live_operation (tree, block_stmt_iterator *, tree *);
/* Driver for transformation stage. */
extern void vect_transform_loop (loop_vec_info, struct loops *);
OSDN Git Service
