#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-vectorizer.h"
+#include "toplev.h"
/* Main analysis functions. */
static loop_vec_info vect_analyze_loop_form (struct loop *);
static bool vect_can_advance_ivs_p (loop_vec_info);
static void vect_update_misalignment_for_peel
(struct data_reference *, struct data_reference *, int npeel);
-
/* Function vect_determine_vectorization_factor
int nbbs = loop->num_nodes;
block_stmt_iterator si;
unsigned int vectorization_factor = 0;
- int i;
tree scalar_type;
+ tree phi;
+ tree vectype;
+ unsigned int nunits;
+ stmt_vec_info stmt_info;
+ int i;
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "=== vect_determine_vectorization_factor ===");
{
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))
+ {
+ fprintf (vect_dump, "==> examining phi: ");
+ print_generic_expr (vect_dump, phi, TDF_SLIM);
+ }
+
+ gcc_assert (stmt_info);
+
+ /* Two cases of "relevant" phis: those that define an
+ induction that is used in the loop, and those that
+ define a reduction. */
+ if ((STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_loop
+ && STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
+ || (STMT_VINFO_RELEVANT (stmt_info) == vect_used_by_reduction
+ && STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def))
+ {
+ gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
+ scalar_type = TREE_TYPE (PHI_RESULT (phi));
+
+ if (vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "get vectype for scalar type: ");
+ print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
+ }
+
+ vectype = get_vectype_for_scalar_type (scalar_type);
+ if (!vectype)
+ {
+ if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
+ {
+ fprintf (vect_dump,
+ "not vectorized: unsupported data-type ");
+ print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
+ }
+ return false;
+ }
+ STMT_VINFO_VECTYPE (stmt_info) = vectype;
+
+ if (vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "vectype: ");
+ print_generic_expr (vect_dump, vectype, TDF_SLIM);
+ }
+
+ nunits = TYPE_VECTOR_SUBPARTS (vectype);
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "nunits = %d", nunits);
+
+ if (!vectorization_factor
+ || (nunits > vectorization_factor))
+ vectorization_factor = nunits;
+ }
+ }
+
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
- tree stmt = bsi_stmt (si);
- unsigned int nunits;
- stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
- tree vectype;
+ tree stmt = bsi_stmt (si);
+ stmt_info = vinfo_for_stmt (stmt);
- if (vect_print_dump_info (REPORT_DETAILS))
- {
- fprintf (vect_dump, "==> examining statement: ");
- print_generic_expr (vect_dump, stmt, TDF_SLIM);
- }
+ if (vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "==> examining statement: ");
+ print_generic_expr (vect_dump, stmt, TDF_SLIM);
+ }
+
+ if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
+ continue;
- gcc_assert (stmt_info);
- /* skip stmts which do not need to be vectorized. */
- if (!STMT_VINFO_RELEVANT_P (stmt_info)
+ gcc_assert (stmt_info);
+
+ /* skip stmts which do not need to be vectorized. */
+ if (!STMT_VINFO_RELEVANT_P (stmt_info)
&& !STMT_VINFO_LIVE_P (stmt_info))
- {
- if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "skip.");
- continue;
- }
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "skip.");
+ continue;
+ }
- if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))))
- {
- if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
- {
- fprintf (vect_dump, "not vectorized: vector stmt in loop:");
- print_generic_expr (vect_dump, stmt, TDF_SLIM);
- }
- return false;
- }
+ if (!GIMPLE_STMT_P (stmt)
+ && VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))))
+ {
+ if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
+ {
+ fprintf (vect_dump, "not vectorized: vector stmt in loop:");
+ print_generic_expr (vect_dump, stmt, TDF_SLIM);
+ }
+ return false;
+ }
if (STMT_VINFO_VECTYPE (stmt_info))
{
+ /* The only case when a vectype had been already set is for stmts
+ that contain a dataref, or for "pattern-stmts" (stmts generated
+ by the vectorizer to represent/replace a certain idiom). */
+ gcc_assert (STMT_VINFO_DATA_REF (stmt_info)
+ || is_pattern_stmt_p (stmt_info));
vectype = STMT_VINFO_VECTYPE (stmt_info);
- scalar_type = TREE_TYPE (vectype);
}
else
{
- if (STMT_VINFO_DATA_REF (stmt_info))
- scalar_type =
- TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (stmt_info)));
- else if (TREE_CODE (stmt) == MODIFY_EXPR)
- scalar_type = TREE_TYPE (TREE_OPERAND (stmt, 0));
- else
- scalar_type = TREE_TYPE (stmt);
+ gcc_assert (! STMT_VINFO_DATA_REF (stmt_info)
+ && !is_pattern_stmt_p (stmt_info));
+
+ /* We set the vectype according to the type of the result (lhs).
+ For stmts whose result-type is different than the type of the
+ arguments (e.g. demotion, promotion), vectype will be reset
+ appropriately (later). Note that we have to visit the smallest
+ datatype in this function, because that determines the VF.
+ If the smallest datatype in the loop is present only as the
+ rhs of a promotion operation - we'd miss it here.
+ However, in such a case, that a variable of this datatype
+ does not appear in the lhs anywhere in the loop, it shouldn't
+ affect the vectorization factor. */
+ scalar_type = TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 0));
if (vect_print_dump_info (REPORT_DETAILS))
{
STMT_VINFO_VECTYPE (stmt_info) = vectype;
}
- if (vect_print_dump_info (REPORT_DETAILS))
- {
- fprintf (vect_dump, "vectype: ");
- print_generic_expr (vect_dump, vectype, TDF_SLIM);
- }
+ if (vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "vectype: ");
+ print_generic_expr (vect_dump, vectype, TDF_SLIM);
+ }
- nunits = TYPE_VECTOR_SUBPARTS (vectype);
- if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "nunits = %d", nunits);
+ nunits = TYPE_VECTOR_SUBPARTS (vectype);
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "nunits = %d", nunits);
if (!vectorization_factor
- || (nunits > vectorization_factor))
- vectorization_factor = nunits;
+ || (nunits > vectorization_factor))
+ vectorization_factor = nunits;
+
}
}
return false;
}
- if (STMT_VINFO_RELEVANT_P (stmt_info))
+ if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_loop
+ && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
{
/* Most likely a reduction-like computation that is used
- in the loop. */
+ in the loop. */
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
fprintf (vect_dump, "not vectorized: unsupported pattern.");
return false;
if (STMT_VINFO_RELEVANT_P (stmt_info))
{
- gcc_assert (!VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))));
+ gcc_assert (GIMPLE_STMT_P (stmt)
+ || !VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))));
gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
ok = (vectorizable_type_promotion (stmt, NULL, NULL)
|| vectorizable_type_demotion (stmt, NULL, NULL)
+ || vectorizable_conversion (stmt, NULL, NULL)
|| vectorizable_operation (stmt, NULL, NULL)
|| vectorizable_assignment (stmt, NULL, NULL)
|| vectorizable_load (stmt, NULL, NULL)
+ || vectorizable_call (stmt, NULL, NULL)
|| vectorizable_store (stmt, NULL, NULL)
|| vectorizable_condition (stmt, NULL, NULL));
vectorization_factor, LOOP_VINFO_INT_NITERS (loop_vinfo));
if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
- && LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor)
+ && ((LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor)
+ || (LOOP_VINFO_INT_NITERS (loop_vinfo) <=
+ ((unsigned) (PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND))
+ * vectorization_factor))))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
fprintf (vect_dump, "not vectorized: iteration count too small.");
Therefore, all we need to check is if STMT falls into the
first case, and whether var corresponds to USE. */
- if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
+ if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME)
return false;
- operand = TREE_OPERAND (stmt, 1);
+ operand = GIMPLE_STMT_OPERAND (stmt, 1);
if (TREE_CODE (operand) != SSA_NAME)
return false;
tree phi;
struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
basic_block bb = loop->header;
- tree dummy;
+ tree dumy;
+ VEC(tree,heap) *worklist = VEC_alloc (tree, heap, 64);
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
+ /* First - identify all inductions. */
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))
{
- fprintf (vect_dump, "Analyze phi: ");
- print_generic_expr (vect_dump, phi, TDF_SLIM);
+ fprintf (vect_dump, "Analyze phi: ");
+ print_generic_expr (vect_dump, phi, TDF_SLIM);
}
/* 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 (def)))
- {
- if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "virtual phi. skip.");
- continue;
- }
+ continue;
STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
/* Analyze the evolution function. */
-
access_fn = analyze_scalar_evolution (loop, def);
+ if (access_fn && vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "Access function of PHI: ");
+ print_generic_expr (vect_dump, access_fn, TDF_SLIM);
+ }
- if (!access_fn)
- continue;
+ if (!access_fn
+ || !vect_is_simple_iv_evolution (loop->num, access_fn, &dumy, &dumy))
+ {
+ VEC_safe_push (tree, heap, worklist, phi);
+ continue;
+ }
if (vect_print_dump_info (REPORT_DETAILS))
- {
- fprintf (vect_dump, "Access function of PHI: ");
- print_generic_expr (vect_dump, access_fn, TDF_SLIM);
- }
+ fprintf (vect_dump, "Detected induction.");
+ STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
+ }
- if (vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy))
- {
- if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "Detected induction.");
- STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
- continue;
- }
- /* TODO: handle invariant phis */
+ /* Second - identify all reductions. */
+ while (VEC_length (tree, worklist) > 0)
+ {
+ tree phi = VEC_pop (tree, worklist);
+ tree def = PHI_RESULT (phi);
+ stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
+ tree reduc_stmt;
+
+ if (vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "Analyze phi: ");
+ print_generic_expr (vect_dump, phi, TDF_SLIM);
+ }
+
+ gcc_assert (is_gimple_reg (SSA_NAME_VAR (def)));
+ gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_unknown_def_type);
reduc_stmt = vect_is_simple_reduction (loop, phi);
if (reduc_stmt)
else
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "Unknown def-use cycle pattern.");
-
}
+ VEC_free (tree, heap, worklist);
return;
}
+/* Function vect_insert_into_interleaving_chain.
+
+ Insert DRA into the interleaving chain of DRB according to DRA's INIT. */
+
+static void
+vect_insert_into_interleaving_chain (struct data_reference *dra,
+ struct data_reference *drb)
+{
+ tree prev, next, next_init;
+ stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
+ stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
+
+ prev = DR_GROUP_FIRST_DR (stmtinfo_b);
+ next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
+ while (next)
+ {
+ next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
+ if (tree_int_cst_compare (next_init, DR_INIT (dra)) > 0)
+ {
+ /* Insert here. */
+ DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = DR_STMT (dra);
+ DR_GROUP_NEXT_DR (stmtinfo_a) = next;
+ return;
+ }
+ prev = next;
+ next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
+ }
+
+ /* We got to the end of the list. Insert here. */
+ DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = DR_STMT (dra);
+ DR_GROUP_NEXT_DR (stmtinfo_a) = NULL_TREE;
+}
+
+
+/* Function vect_update_interleaving_chain.
+
+ For two data-refs DRA and DRB that are a part of a chain interleaved data
+ accesses, update the interleaving chain. DRB's INIT is smaller than DRA's.
+
+ There are four possible cases:
+ 1. New stmts - both DRA and DRB are not a part of any chain:
+ FIRST_DR = DRB
+ NEXT_DR (DRB) = DRA
+ 2. DRB is a part of a chain and DRA is not:
+ no need to update FIRST_DR
+ no need to insert DRB
+ insert DRA according to init
+ 3. DRA is a part of a chain and DRB is not:
+ if (init of FIRST_DR > init of DRB)
+ FIRST_DR = DRB
+ NEXT(FIRST_DR) = previous FIRST_DR
+ else
+ insert DRB according to its init
+ 4. both DRA and DRB are in some interleaving chains:
+ choose the chain with the smallest init of FIRST_DR
+ insert the nodes of the second chain into the first one. */
+
+static void
+vect_update_interleaving_chain (struct data_reference *drb,
+ struct data_reference *dra)
+{
+ stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
+ stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
+ tree next_init, init_dra_chain, init_drb_chain, first_a, first_b;
+ tree node, prev, next, node_init, first_stmt;
+
+ /* 1. New stmts - both DRA and DRB are not a part of any chain. */
+ if (!DR_GROUP_FIRST_DR (stmtinfo_a) && !DR_GROUP_FIRST_DR (stmtinfo_b))
+ {
+ DR_GROUP_FIRST_DR (stmtinfo_a) = DR_STMT (drb);
+ DR_GROUP_FIRST_DR (stmtinfo_b) = DR_STMT (drb);
+ DR_GROUP_NEXT_DR (stmtinfo_b) = DR_STMT (dra);
+ return;
+ }
+
+ /* 2. DRB is a part of a chain and DRA is not. */
+ if (!DR_GROUP_FIRST_DR (stmtinfo_a) && DR_GROUP_FIRST_DR (stmtinfo_b))
+ {
+ DR_GROUP_FIRST_DR (stmtinfo_a) = DR_GROUP_FIRST_DR (stmtinfo_b);
+ /* Insert DRA into the chain of DRB. */
+ vect_insert_into_interleaving_chain (dra, drb);
+ return;
+ }
+
+ /* 3. DRA is a part of a chain and DRB is not. */
+ if (DR_GROUP_FIRST_DR (stmtinfo_a) && !DR_GROUP_FIRST_DR (stmtinfo_b))
+ {
+ tree old_first_stmt = DR_GROUP_FIRST_DR (stmtinfo_a);
+ tree init_old = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (
+ old_first_stmt)));
+ tree tmp;
+
+ if (tree_int_cst_compare (init_old, DR_INIT (drb)) > 0)
+ {
+ /* DRB's init is smaller than the init of the stmt previously marked
+ as the first stmt of the interleaving chain of DRA. Therefore, we
+ update FIRST_STMT and put DRB in the head of the list. */
+ DR_GROUP_FIRST_DR (stmtinfo_b) = DR_STMT (drb);
+ DR_GROUP_NEXT_DR (stmtinfo_b) = old_first_stmt;
+
+ /* Update all the stmts in the list to point to the new FIRST_STMT. */
+ tmp = old_first_stmt;
+ while (tmp)
+ {
+ DR_GROUP_FIRST_DR (vinfo_for_stmt (tmp)) = DR_STMT (drb);
+ tmp = DR_GROUP_NEXT_DR (vinfo_for_stmt (tmp));
+ }
+ }
+ else
+ {
+ /* Insert DRB in the list of DRA. */
+ vect_insert_into_interleaving_chain (drb, dra);
+ DR_GROUP_FIRST_DR (stmtinfo_b) = DR_GROUP_FIRST_DR (stmtinfo_a);
+ }
+ return;
+ }
+
+ /* 4. both DRA and DRB are in some interleaving chains. */
+ first_a = DR_GROUP_FIRST_DR (stmtinfo_a);
+ first_b = DR_GROUP_FIRST_DR (stmtinfo_b);
+ if (first_a == first_b)
+ return;
+ init_dra_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_a)));
+ init_drb_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_b)));
+
+ if (tree_int_cst_compare (init_dra_chain, init_drb_chain) > 0)
+ {
+ /* Insert the nodes of DRA chain into the DRB chain.
+ After inserting a node, continue from this node of the DRB chain (don't
+ start from the beginning. */
+ node = DR_GROUP_FIRST_DR (stmtinfo_a);
+ prev = DR_GROUP_FIRST_DR (stmtinfo_b);
+ first_stmt = first_b;
+ }
+ else
+ {
+ /* Insert the nodes of DRB chain into the DRA chain.
+ After inserting a node, continue from this node of the DRA chain (don't
+ start from the beginning. */
+ node = DR_GROUP_FIRST_DR (stmtinfo_b);
+ prev = DR_GROUP_FIRST_DR (stmtinfo_a);
+ first_stmt = first_a;
+ }
+
+ while (node)
+ {
+ node_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (node)));
+ next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
+ while (next)
+ {
+ next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
+ if (tree_int_cst_compare (next_init, node_init) > 0)
+ {
+ /* Insert here. */
+ DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = node;
+ DR_GROUP_NEXT_DR (vinfo_for_stmt (node)) = next;
+ prev = node;
+ break;
+ }
+ prev = next;
+ next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
+ }
+ if (!next)
+ {
+ /* We got to the end of the list. Insert here. */
+ DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = node;
+ DR_GROUP_NEXT_DR (vinfo_for_stmt (node)) = NULL_TREE;
+ prev = node;
+ }
+ DR_GROUP_FIRST_DR (vinfo_for_stmt (node)) = first_stmt;
+ node = DR_GROUP_NEXT_DR (vinfo_for_stmt (node));
+ }
+}
+
+
+/* Function vect_equal_offsets.
+
+ Check if OFFSET1 and OFFSET2 are identical expressions. */
+
+static bool
+vect_equal_offsets (tree offset1, tree offset2)
+{
+ bool res0, res1;
+
+ STRIP_NOPS (offset1);
+ STRIP_NOPS (offset2);
+
+ if (offset1 == offset2)
+ return true;
+
+ if (TREE_CODE (offset1) != TREE_CODE (offset2)
+ || !BINARY_CLASS_P (offset1)
+ || !BINARY_CLASS_P (offset2))
+ return false;
+
+ res0 = vect_equal_offsets (TREE_OPERAND (offset1, 0),
+ TREE_OPERAND (offset2, 0));
+ res1 = vect_equal_offsets (TREE_OPERAND (offset1, 1),
+ TREE_OPERAND (offset2, 1));
+
+ return (res0 && res1);
+}
+
+
+/* Function vect_check_interleaving.
+
+ Check if DRA and DRB are a part of interleaving. In case they are, insert
+ DRA and DRB in an interleaving chain. */
+
+static void
+vect_check_interleaving (struct data_reference *dra,
+ struct data_reference *drb)
+{
+ HOST_WIDE_INT type_size_a, type_size_b, diff_mod_size, step, init_a, init_b;
+
+ /* Check that the data-refs have same first location (except init) and they
+ are both either store or load (not load and store). */
+ if ((DR_BASE_ADDRESS (dra) != DR_BASE_ADDRESS (drb)
+ && (TREE_CODE (DR_BASE_ADDRESS (dra)) != ADDR_EXPR
+ || TREE_CODE (DR_BASE_ADDRESS (drb)) != ADDR_EXPR
+ || TREE_OPERAND (DR_BASE_ADDRESS (dra), 0)
+ != TREE_OPERAND (DR_BASE_ADDRESS (drb),0)))
+ || !vect_equal_offsets (DR_OFFSET (dra), DR_OFFSET (drb))
+ || !tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb))
+ || DR_IS_READ (dra) != DR_IS_READ (drb))
+ return;
+
+ /* Check:
+ 1. data-refs are of the same type
+ 2. their steps are equal
+ 3. the step is greater than the difference between data-refs' inits */
+ type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
+ type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
+
+ if (type_size_a != type_size_b
+ || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb)))
+ return;
+
+ init_a = TREE_INT_CST_LOW (DR_INIT (dra));
+ init_b = TREE_INT_CST_LOW (DR_INIT (drb));
+ step = TREE_INT_CST_LOW (DR_STEP (dra));
+
+ if (init_a > init_b)
+ {
+ /* If init_a == init_b + the size of the type * k, we have an interleaving,
+ and DRB is accessed before DRA. */
+ diff_mod_size = (init_a - init_b) % type_size_a;
+
+ if ((init_a - init_b) > step)
+ return;
+
+ if (diff_mod_size == 0)
+ {
+ vect_update_interleaving_chain (drb, dra);
+ if (vect_print_dump_info (REPORT_DR_DETAILS))
+ {
+ fprintf (vect_dump, "Detected interleaving ");
+ print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
+ fprintf (vect_dump, " and ");
+ print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
+ }
+ return;
+ }
+ }
+ else
+ {
+ /* If init_b == init_a + the size of the type * k, we have an
+ interleaving, and DRA is accessed before DRB. */
+ diff_mod_size = (init_b - init_a) % type_size_a;
+
+ if ((init_b - init_a) > step)
+ return;
+
+ if (diff_mod_size == 0)
+ {
+ vect_update_interleaving_chain (dra, drb);
+ if (vect_print_dump_info (REPORT_DR_DETAILS))
+ {
+ fprintf (vect_dump, "Detected interleaving ");
+ print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
+ fprintf (vect_dump, " and ");
+ print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
+ }
+ return;
+ }
+ }
+}
+
+
/* Function vect_analyze_data_ref_dependence.
Return TRUE if there (might) exist a dependence between a memory-reference
unsigned int loop_depth;
if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ {
+ /* Independent data accesses. */
+ vect_check_interleaving (dra, drb);
+ return false;
+ }
+
+ if ((DR_IS_READ (dra) && DR_IS_READ (drb)) || dra == drb)
return false;
if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
fprintf (vect_dump, " and ");
print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
}
- continue;
+
+ /* For interleaving, mark that there is a read-write dependency if
+ necessary. We check before that one of the data-refs is store. */
+ if (DR_IS_READ (dra))
+ DR_GROUP_READ_WRITE_DEPENDENCE (stmtinfo_a) = true;
+ else
+ {
+ if (DR_IS_READ (drb))
+ DR_GROUP_READ_WRITE_DEPENDENCE (stmtinfo_b) = true;
+ }
+
+ continue;
}
if (abs (dist) >= vectorization_factor)
struct data_reference *current_dr;
int dr_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
int dr_peel_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr_peel))));
+ stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
+ stmt_vec_info peel_stmt_info = vinfo_for_stmt (DR_STMT (dr_peel));
+
+ /* For interleaved data accesses the step in the loop must be multiplied by
+ the size of the interleaving group. */
+ if (DR_GROUP_FIRST_DR (stmt_info))
+ dr_size *= DR_GROUP_SIZE (vinfo_for_stmt (DR_GROUP_FIRST_DR (stmt_info)));
+ if (DR_GROUP_FIRST_DR (peel_stmt_info))
+ dr_peel_size *= DR_GROUP_SIZE (peel_stmt_info);
if (known_alignment_for_access_p (dr)
&& known_alignment_for_access_p (dr_peel)
- && (DR_MISALIGNMENT (dr)/dr_size ==
- DR_MISALIGNMENT (dr_peel)/dr_peel_size))
+ && (DR_MISALIGNMENT (dr) / dr_size ==
+ DR_MISALIGNMENT (dr_peel) / dr_peel_size))
{
DR_MISALIGNMENT (dr) = 0;
return;
{
if (current_dr != dr)
continue;
- gcc_assert (DR_MISALIGNMENT (dr)/dr_size ==
- DR_MISALIGNMENT (dr_peel)/dr_peel_size);
+ gcc_assert (DR_MISALIGNMENT (dr) / dr_size ==
+ DR_MISALIGNMENT (dr_peel) / dr_peel_size);
DR_MISALIGNMENT (dr) = 0;
return;
}
if (known_alignment_for_access_p (dr)
&& known_alignment_for_access_p (dr_peel))
- {
+ {
DR_MISALIGNMENT (dr) += npeel * dr_size;
DR_MISALIGNMENT (dr) %= UNITS_PER_SIMD_WORD;
return;
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
{
+ tree stmt = DR_STMT (dr);
+ stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+
+ /* For interleaving, only the alignment of the first access matters. */
+ if (DR_GROUP_FIRST_DR (stmt_info)
+ && DR_GROUP_FIRST_DR (stmt_info) != stmt)
+ continue;
+
supportable_dr_alignment = vect_supportable_dr_alignment (dr);
if (!supportable_dr_alignment)
{
bool do_peeling = false;
bool do_versioning = false;
bool stat;
+ tree stmt;
+ stmt_vec_info stmt_info;
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "=== vect_enhance_data_refs_alignment ===");
can make all data references satisfy vect_supportable_dr_alignment.
If so, update data structures as needed and return true. Note that
at this time vect_supportable_dr_alignment is known to return false
- for a a misaligned write.
+ for a misaligned write.
B) If peeling wasn't possible and there is a data reference with an
unknown misalignment that does not satisfy vect_supportable_dr_alignment
TODO: Use a cost model. */
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
- if (!DR_IS_READ (dr) && !aligned_access_p (dr))
- {
- dr0 = dr;
- do_peeling = true;
- break;
- }
+ {
+ stmt = DR_STMT (dr);
+ stmt_info = vinfo_for_stmt (stmt);
+
+ /* For interleaving, only the alignment of the first access
+ matters. */
+ if (DR_GROUP_FIRST_DR (stmt_info)
+ && DR_GROUP_FIRST_DR (stmt_info) != stmt)
+ continue;
+
+ if (!DR_IS_READ (dr) && !aligned_access_p (dr))
+ {
+ if (DR_GROUP_FIRST_DR (stmt_info))
+ {
+ /* For interleaved access we peel only if number of iterations in
+ the prolog loop ({VF - misalignment}), is a multiple of the
+ number of the interleaved accesses. */
+ int elem_size, mis_in_elements;
+ int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
+
+ /* FORNOW: handle only known alignment. */
+ if (!known_alignment_for_access_p (dr))
+ {
+ do_peeling = false;
+ break;
+ }
+
+ elem_size = UNITS_PER_SIMD_WORD / vf;
+ mis_in_elements = DR_MISALIGNMENT (dr) / elem_size;
+
+ if ((vf - mis_in_elements) % DR_GROUP_SIZE (stmt_info))
+ {
+ do_peeling = false;
+ break;
+ }
+ }
+ dr0 = dr;
+ do_peeling = true;
+ break;
+ }
+ }
/* Often peeling for alignment will require peeling for loop-bound, which in
turn requires that we know how to adjust the loop ivs after the loop. */
mis = DR_MISALIGNMENT (dr0);
mis /= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0))));
npeel = LOOP_VINFO_VECT_FACTOR (loop_vinfo) - mis;
+
+ /* For interleaved data access every iteration accesses all the
+ members of the group, therefore we divide the number of iterations
+ by the group size. */
+ stmt_info = vinfo_for_stmt (DR_STMT (dr0));
+ if (DR_GROUP_FIRST_DR (stmt_info))
+ npeel /= DR_GROUP_SIZE (stmt_info);
+
if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "Try peeling by %d",npeel);
+ fprintf (vect_dump, "Try peeling by %d", npeel);
}
/* Ensure that all data refs can be vectorized after the peel. */
if (dr == dr0)
continue;
+ stmt = DR_STMT (dr);
+ stmt_info = vinfo_for_stmt (stmt);
+ /* For interleaving, only the alignment of the first access
+ matters. */
+ if (DR_GROUP_FIRST_DR (stmt_info)
+ && DR_GROUP_FIRST_DR (stmt_info) != stmt)
+ continue;
+
save_misalignment = DR_MISALIGNMENT (dr);
vect_update_misalignment_for_peel (dr, dr0, npeel);
supportable_dr_alignment = vect_supportable_dr_alignment (dr);
{
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
{
- if (aligned_access_p (dr))
- continue;
+ stmt = DR_STMT (dr);
+ stmt_info = vinfo_for_stmt (stmt);
+
+ /* For interleaving, only the alignment of the first access
+ matters. */
+ if (aligned_access_p (dr)
+ || (DR_GROUP_FIRST_DR (stmt_info)
+ && DR_GROUP_FIRST_DR (stmt_info) != stmt))
+ continue;
- supportable_dr_alignment = vect_supportable_dr_alignment (dr);
+ supportable_dr_alignment = vect_supportable_dr_alignment (dr);
if (!supportable_dr_alignment)
{
vect_analyze_data_ref_access (struct data_reference *dr)
{
tree step = DR_STEP (dr);
+ HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
tree scalar_type = TREE_TYPE (DR_REF (dr));
+ HOST_WIDE_INT type_size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
+ tree stmt = DR_STMT (dr);
+ /* For interleaving, STRIDE is STEP counted in elements, i.e., the size of the
+ interleaving group (including gaps). */
+ HOST_WIDE_INT stride = dr_step / type_size;
+
+ if (!step)
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "bad data-ref access");
+ return false;
+ }
- if (!step || tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)))
+ /* Consecutive? */
+ if (!tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)))
{
+ /* Mark that it is not interleaving. */
+ DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) = NULL_TREE;
+ return true;
+ }
+
+ /* Not consecutive access is possible only if it is a part of interleaving. */
+ if (!DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)))
+ {
+ /* Check if it this DR is a part of interleaving, and is a single
+ element of the group that is accessed in the loop. */
+
+ /* Gaps are supported only for loads. STEP must be a multiple of the type
+ size. The size of the group must be a power of 2. */
+ if (DR_IS_READ (dr)
+ && (dr_step % type_size) == 0
+ && stride > 0
+ && exact_log2 (stride) != -1)
+ {
+ DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) = stmt;
+ DR_GROUP_SIZE (vinfo_for_stmt (stmt)) = stride;
+ if (vect_print_dump_info (REPORT_DR_DETAILS))
+ {
+ fprintf (vect_dump, "Detected single element interleaving %d ",
+ DR_GROUP_SIZE (vinfo_for_stmt (stmt)));
+ print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
+ fprintf (vect_dump, " step ");
+ print_generic_expr (vect_dump, step, TDF_SLIM);
+ }
+ return true;
+ }
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "not consecutive access");
return false;
}
+
+ if (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) == stmt)
+ {
+ /* First stmt in the interleaving chain. Check the chain. */
+ tree next = DR_GROUP_NEXT_DR (vinfo_for_stmt (stmt));
+ struct data_reference *data_ref = dr;
+ unsigned int count = 1;
+ tree next_step;
+ tree prev_init = DR_INIT (data_ref);
+ tree prev = stmt;
+ HOST_WIDE_INT diff, count_in_bytes;
+
+ while (next)
+ {
+ /* Skip same data-refs. In case that two or more stmts share data-ref
+ (supported only for loads), we vectorize only the first stmt, and
+ the rest get their vectorized loads from the first one. */
+ if (!tree_int_cst_compare (DR_INIT (data_ref),
+ DR_INIT (STMT_VINFO_DATA_REF (
+ vinfo_for_stmt (next)))))
+ {
+ if (!DR_IS_READ (data_ref))
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "Two store stmts share the same dr.");
+ return false;
+ }
+
+ /* Check that there is no load-store dependencies for this loads
+ to prevent a case of load-store-load to the same location. */
+ if (DR_GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (next))
+ || DR_GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (prev)))
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump,
+ "READ_WRITE dependence in interleaving.");
+ return false;
+ }
+
+ /* For load use the same data-ref load. */
+ DR_GROUP_SAME_DR_STMT (vinfo_for_stmt (next)) = prev;
+
+ prev = next;
+ next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
+ continue;
+ }
+ prev = next;
+
+ /* Check that all the accesses have the same STEP. */
+ next_step = DR_STEP (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
+ if (tree_int_cst_compare (step, next_step))
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "not consecutive access in interleaving");
+ return false;
+ }
+
+ data_ref = STMT_VINFO_DATA_REF (vinfo_for_stmt (next));
+ /* Check that the distance between two accesses is equal to the type
+ size. Otherwise, we have gaps. */
+ diff = (TREE_INT_CST_LOW (DR_INIT (data_ref))
+ - TREE_INT_CST_LOW (prev_init)) / type_size;
+ if (!DR_IS_READ (data_ref) && diff != 1)
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "interleaved store with gaps");
+ return false;
+ }
+ /* Store the gap from the previous member of the group. If there is no
+ gap in the access, DR_GROUP_GAP is always 1. */
+ DR_GROUP_GAP (vinfo_for_stmt (next)) = diff;
+
+ prev_init = DR_INIT (data_ref);
+ next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
+ /* Count the number of data-refs in the chain. */
+ count++;
+ }
+
+ /* COUNT is the number of accesses found, we multiply it by the size of
+ the type to get COUNT_IN_BYTES. */
+ count_in_bytes = type_size * count;
+
+ /* Check that the size of the interleaving is not greater than STEP. */
+ if (dr_step < count_in_bytes)
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "interleaving size is greater than step for ");
+ print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
+ }
+ return false;
+ }
+
+ /* Check that the size of the interleaving is equal to STEP for stores,
+ i.e., that there are no gaps. */
+ if (!DR_IS_READ (dr) && dr_step != count_in_bytes)
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "interleaved store with gaps");
+ return false;
+ }
+
+ /* Check that STEP is a multiple of type size. */
+ if ((dr_step % type_size) != 0)
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "step is not a multiple of type size: step ");
+ print_generic_expr (vect_dump, step, TDF_SLIM);
+ fprintf (vect_dump, " size ");
+ print_generic_expr (vect_dump, TYPE_SIZE_UNIT (scalar_type),
+ TDF_SLIM);
+ }
+ return false;
+ }
+
+ /* FORNOW: we handle only interleaving that is a power of 2. */
+ if (exact_log2 (stride) == -1)
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "interleaving is not a power of 2");
+ return false;
+ }
+ DR_GROUP_SIZE (vinfo_for_stmt (stmt)) = stride;
+ }
return true;
}
tree scalar_type;
if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "=== vect_analyze_data_refs ===");
+ fprintf (vect_dump, "=== vect_analyze_data_refs ===\n");
- compute_data_dependences_for_loop (loop, false,
+ compute_data_dependences_for_loop (loop, true,
&LOOP_VINFO_DATAREFS (loop_vinfo),
&LOOP_VINFO_DDRS (loop_vinfo));
/* Update DR field in stmt_vec_info struct. */
stmt = DR_STMT (dr);
stmt_info = vinfo_for_stmt (stmt);
-
+
if (STMT_VINFO_DATA_REF (stmt_info))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
(case 2)
If STMT has been identified as defining a reduction variable, then
- we have two cases:
- (case 2.1)
- The last use of STMT is the reduction-variable, which is defined
- by a loop-header-phi. We don't want to mark the phi as live or
- relevant (because it does not need to be vectorized, it is handled
- as part of the vectorization of the reduction), so in this case we
- skip the call to vect_mark_relevant.
- (case 2.2)
- The rest of the uses of STMT are defined in the loop body. For
- the def_stmt of these uses we want to set liveness/relevance
- as follows:
+ we want to set liveness/relevance as follows:
STMT_VINFO_LIVE_P (DEF_STMT_info) <-- false
STMT_VINFO_RELEVANT (DEF_STMT_info) <-- vect_used_by_reduction
because even though STMT is classified as live (since it defines a
is not used inside the loop), it will be vectorized, and therefore
the corresponding DEF_STMTs need to marked as relevant.
We distinguish between two kinds of relevant stmts - those that are
- used by a reduction conputation, and those that are (also) used by a regular computation. This allows us later on to identify stmts
+ used by a reduction computation, and those that are (also) used by
+ a regular computation. This allows us later on to identify stmts
that are used solely by a reduction, and therefore the order of
the results that they produce does not have to be kept.
*/
/* case 2.2: */
if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
- {
- gcc_assert (relevant == vect_unused_in_loop && live_p);
- relevant = vect_used_by_reduction;
- live_p = false;
- }
+ {
+ gcc_assert (relevant == vect_unused_in_loop && live_p);
+ relevant = vect_used_by_reduction;
+ live_p = false;
+ }
+ i = 0;
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
+ if (vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "worklist: examine use %d: ", i++);
+ print_generic_expr (vect_dump, use, TDF_SLIM);
+ }
+
/* case 1: we are only interested in uses that need to be vectorized.
Uses that are used for address computation are not considered
relevant.
continue;
if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt))
- {
- if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
- fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
+ {
+ if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
+ fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
VEC_free (tree, heap, worklist);
- return false;
+ return false;
}
if (!def_stmt || IS_EMPTY_STMT (def_stmt))
continue;
- if (vect_print_dump_info (REPORT_DETAILS))
- {
- fprintf (vect_dump, "worklist: examine use %d: ", i);
- print_generic_expr (vect_dump, use, TDF_SLIM);
- }
-
bb = bb_for_stmt (def_stmt);
- if (!flow_bb_inside_loop_p (loop, bb))
- continue;
-
- /* case 2.1: the reduction-use does not mark the defining-phi
- as relevant. */
- if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
- && TREE_CODE (def_stmt) == PHI_NODE)
+ if (!flow_bb_inside_loop_p (loop, bb))
continue;
-
vect_mark_relevant (&worklist, def_stmt, relevant, live_p);
}
} /* while worklist */
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "=== get_loop_niters ===");
- niters = number_of_iterations_in_loop (loop);
+ niters = number_of_exit_cond_executions (loop);
if (niters != NULL_TREE
&& niters != chrec_dont_know)
OSDN Git Service
