/* SLP - Basic Block Vectorization
- Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
- Foundation, Inc.
- Contributed by Dorit Naishlos <dorit@il.ibm.com>
+ Copyright (C) 2007, 2008, 2009, 2010
+ Free Software Foundation, Inc.
+ Contributed by Dorit Naishlos <dorit@il.ibm.com>
and Ira Rosen <irar@il.ibm.com>
This file is part of GCC.
if (SLP_TREE_LEFT (node))
vect_free_slp_tree (SLP_TREE_LEFT (node));
-
+
if (SLP_TREE_RIGHT (node))
vect_free_slp_tree (SLP_TREE_RIGHT (node));
-
+
VEC_free (gimple, heap, SLP_TREE_SCALAR_STMTS (node));
-
+
if (SLP_TREE_VEC_STMTS (node))
VEC_free (gimple, heap, SLP_TREE_VEC_STMTS (node));
static bool
vect_get_and_check_slp_defs (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
- slp_tree slp_node, gimple stmt,
+ slp_tree slp_node, gimple stmt,
VEC (gimple, heap) **def_stmts0,
VEC (gimple, heap) **def_stmts1,
enum vect_def_type *first_stmt_dt0,
enum vect_def_type *first_stmt_dt1,
- tree *first_stmt_def0_type,
+ tree *first_stmt_def0_type,
tree *first_stmt_def1_type,
tree *first_stmt_const_oprnd,
int ncopies_for_cost,
tree def;
gimple def_stmt;
enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
- stmt_vec_info stmt_info =
+ stmt_vec_info stmt_info =
vinfo_for_stmt (VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0));
enum gimple_rhs_class rhs_class;
struct loop *loop = NULL;
-
+
if (loop_vinfo)
loop = LOOP_VINFO_LOOP (loop_vinfo);
{
oprnd = gimple_op (stmt, i + 1);
- if (!vect_is_simple_use (oprnd, loop_vinfo, bb_vinfo, &def_stmt, &def,
+ if (!vect_is_simple_use (oprnd, loop_vinfo, bb_vinfo, &def_stmt, &def,
&dt[i])
|| (!def_stmt && dt[i] != vect_constant_def))
{
- if (vect_print_dump_info (REPORT_SLP))
+ if (vect_print_dump_info (REPORT_SLP))
{
fprintf (vect_dump, "Build SLP failed: can't find def for ");
print_generic_expr (vect_dump, oprnd, TDF_SLIM);
/* Store. */
vect_model_store_cost (stmt_info, ncopies_for_cost, dt[0], slp_node);
}
-
+
else
{
if (!*first_stmt_dt1 && i == 1)
*first_stmt_def1_type = TREE_TYPE (def);
else
{
- /* We assume that the stmt contains only one constant
+ /* We assume that the stmt contains only one constant
operand. We fail otherwise, to be on the safe side. */
if (*first_stmt_const_oprnd)
{
- if (vect_print_dump_info (REPORT_SLP))
+ if (vect_print_dump_info (REPORT_SLP))
fprintf (vect_dump, "Build SLP failed: two constant "
- "oprnds in stmt");
+ "oprnds in stmt");
return false;
}
*first_stmt_const_oprnd = oprnd;
}
else
{
- /* Not first stmt of the group, check that the def-stmt/s match
+ /* Not first stmt of the group, check that the def-stmt/s match
the def-stmt/s of the first stmt. */
- if ((i == 0
+ if ((i == 0
&& (*first_stmt_dt0 != dt[i]
|| (*first_stmt_def0_type && def
- && *first_stmt_def0_type != TREE_TYPE (def))))
- || (i == 1
+ && !types_compatible_p (*first_stmt_def0_type,
+ TREE_TYPE (def)))))
+ || (i == 1
&& (*first_stmt_dt1 != dt[i]
|| (*first_stmt_def1_type && def
- && *first_stmt_def1_type != TREE_TYPE (def))))
- || (!def
- && TREE_TYPE (*first_stmt_const_oprnd)
- != TREE_TYPE (oprnd)))
- {
- if (vect_print_dump_info (REPORT_SLP))
+ && !types_compatible_p (*first_stmt_def1_type,
+ TREE_TYPE (def)))))
+ || (!def
+ && !types_compatible_p (TREE_TYPE (*first_stmt_const_oprnd),
+ TREE_TYPE (oprnd))))
+ {
+ if (vect_print_dump_info (REPORT_SLP))
fprintf (vect_dump, "Build SLP failed: different types ");
-
+
return false;
}
}
case vect_constant_def:
case vect_external_def:
break;
-
+
case vect_internal_def:
+ case vect_reduction_def:
if (i == 0)
VEC_safe_push (gimple, heap, *def_stmts0, def_stmt);
else
default:
/* FORNOW: Not supported. */
- if (vect_print_dump_info (REPORT_SLP))
+ if (vect_print_dump_info (REPORT_SLP))
{
fprintf (vect_dump, "Build SLP failed: illegal type of def ");
print_generic_expr (vect_dump, def, TDF_SLIM);
/* Recursively build an SLP tree starting from NODE.
- Fail (and return FALSE) if def-stmts are not isomorphic, require data
- permutation or are of unsupported types of operation. Otherwise, return
+ Fail (and return FALSE) if def-stmts are not isomorphic, require data
+ permutation or are of unsupported types of operation. Otherwise, return
TRUE. */
static bool
-vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
+vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
slp_tree *node, unsigned int group_size,
int *inside_cost, int *outside_cost,
int ncopies_for_cost, unsigned int *max_nunits,
HOST_WIDE_INT dummy;
bool permutation = false;
unsigned int load_place;
- gimple first_load;
+ gimple first_load, prev_first_load = NULL;
/* For every stmt in NODE find its def stmt/s. */
for (i = 0; VEC_iterate (gimple, stmts, i, stmt); i++)
{
- if (vect_print_dump_info (REPORT_SLP))
+ if (vect_print_dump_info (REPORT_SLP))
{
fprintf (vect_dump, "Build SLP for ");
print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
lhs = gimple_get_lhs (stmt);
if (lhs == NULL_TREE)
{
- if (vect_print_dump_info (REPORT_SLP))
+ if (vect_print_dump_info (REPORT_SLP))
{
fprintf (vect_dump,
"Build SLP failed: not GIMPLE_ASSIGN nor GIMPLE_CALL");
print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
}
-
+
return false;
}
- scalar_type = vect_get_smallest_scalar_type (stmt, &dummy, &dummy);
+ scalar_type = vect_get_smallest_scalar_type (stmt, &dummy, &dummy);
vectype = get_vectype_for_scalar_type (scalar_type);
if (!vectype)
{
}
return false;
}
-
+
ncopies = vectorization_factor / TYPE_VECTOR_SUBPARTS (vectype);
if (ncopies != 1)
{
if (bb_vinfo)
return false;
}
-
+
/* In case of multiple types we need to detect the smallest type. */
if (*max_nunits < TYPE_VECTOR_SUBPARTS (vectype))
*max_nunits = TYPE_VECTOR_SUBPARTS (vectype);
-
+
if (is_gimple_call (stmt))
rhs_code = CALL_EXPR;
else
{
first_stmt_code = rhs_code;
- /* Shift arguments should be equal in all the packed stmts for a
+ /* Shift arguments should be equal in all the packed stmts for a
vector shift with scalar shift operand. */
if (rhs_code == LSHIFT_EXPR || rhs_code == RSHIFT_EXPR
|| rhs_code == LROTATE_EXPR
&& (first_stmt_code != REALPART_EXPR
|| rhs_code != IMAGPART_EXPR))
{
- if (vect_print_dump_info (REPORT_SLP))
+ if (vect_print_dump_info (REPORT_SLP))
{
- fprintf (vect_dump,
+ fprintf (vect_dump,
"Build SLP failed: different operation in stmt ");
print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
}
-
+
return false;
}
-
- if (need_same_oprnds
+
+ if (need_same_oprnds
&& !operand_equal_p (first_op1, gimple_assign_rhs2 (stmt), 0))
{
- if (vect_print_dump_info (REPORT_SLP))
+ if (vect_print_dump_info (REPORT_SLP))
{
- fprintf (vect_dump,
+ fprintf (vect_dump,
"Build SLP failed: different shift arguments in ");
print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
}
-
+
return false;
}
}
if (REFERENCE_CLASS_P (lhs))
{
/* Store. */
- if (!vect_get_and_check_slp_defs (loop_vinfo, bb_vinfo, *node,
- stmt, &def_stmts0, &def_stmts1,
- &first_stmt_dt0,
- &first_stmt_dt1,
- &first_stmt_def0_type,
+ if (!vect_get_and_check_slp_defs (loop_vinfo, bb_vinfo, *node,
+ stmt, &def_stmts0, &def_stmts1,
+ &first_stmt_dt0,
+ &first_stmt_dt1,
+ &first_stmt_def0_type,
&first_stmt_def1_type,
&first_stmt_const_oprnd,
ncopies_for_cost,
&pattern0, &pattern1))
return false;
}
- else
- {
- /* Load. */
- /* FORNOW: Check that there is no gap between the loads. */
- if ((DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) == stmt
- && DR_GROUP_GAP (vinfo_for_stmt (stmt)) != 0)
- || (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) != stmt
- && DR_GROUP_GAP (vinfo_for_stmt (stmt)) != 1))
- {
- if (vect_print_dump_info (REPORT_SLP))
- {
- fprintf (vect_dump, "Build SLP failed: strided "
- "loads have gaps ");
- print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
- }
-
- return false;
- }
-
- /* Check that the size of interleaved loads group is not
- greater than the SLP group size. */
- if (DR_GROUP_SIZE (vinfo_for_stmt (stmt))
- > ncopies * group_size)
- {
- if (vect_print_dump_info (REPORT_SLP))
- {
- fprintf (vect_dump, "Build SLP failed: the number of "
- "interleaved loads is greater than"
- " the SLP group size ");
- print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
- }
+ else
+ {
+ /* Load. */
+ /* FORNOW: Check that there is no gap between the loads. */
+ if ((DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) == stmt
+ && DR_GROUP_GAP (vinfo_for_stmt (stmt)) != 0)
+ || (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) != stmt
+ && DR_GROUP_GAP (vinfo_for_stmt (stmt)) != 1))
+ {
+ if (vect_print_dump_info (REPORT_SLP))
+ {
+ fprintf (vect_dump, "Build SLP failed: strided "
+ "loads have gaps ");
+ print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
+ }
- return false;
- }
-
- first_load = DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt));
+ return false;
+ }
+
+ /* Check that the size of interleaved loads group is not
+ greater than the SLP group size. */
+ if (DR_GROUP_SIZE (vinfo_for_stmt (stmt)) > ncopies * group_size)
+ {
+ if (vect_print_dump_info (REPORT_SLP))
+ {
+ fprintf (vect_dump, "Build SLP failed: the number of "
+ "interleaved loads is greater than"
+ " the SLP group size ");
+ print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
+ }
+
+ return false;
+ }
+
+ first_load = DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt));
+ if (prev_first_load)
+ {
+ /* Check that there are no loads from different interleaving
+ chains in the same node. The only exception is complex
+ numbers. */
+ if (prev_first_load != first_load
+ && rhs_code != REALPART_EXPR
+ && rhs_code != IMAGPART_EXPR)
+ {
+ if (vect_print_dump_info (REPORT_SLP))
+ {
+ fprintf (vect_dump, "Build SLP failed: different "
+ "interleaving chains in one node ");
+ print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
+ }
+ return false;
+ }
+ }
+ else
+ prev_first_load = first_load;
+
if (first_load == stmt)
{
first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
"unaligned load ");
print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
}
-
+
return false;
}
-
+
/* Analyze costs (for the first stmt in the group). */
vect_model_load_cost (vinfo_for_stmt (stmt),
ncopies_for_cost, *node);
}
-
+
/* Store the place of this load in the interleaving chain. In
case that permutation is needed we later decide if a specific
permutation is supported. */
first_load);
if (load_place != i)
permutation = true;
-
+
VEC_safe_push (int, heap, *load_permutation, load_place);
-
+
/* We stop the tree when we reach a group of loads. */
stop_recursion = true;
continue;
if (TREE_CODE_CLASS (rhs_code) == tcc_reference)
{
/* Not strided load. */
- if (vect_print_dump_info (REPORT_SLP))
+ if (vect_print_dump_info (REPORT_SLP))
{
fprintf (vect_dump, "Build SLP failed: not strided load ");
print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
if (TREE_CODE_CLASS (rhs_code) != tcc_binary
&& TREE_CODE_CLASS (rhs_code) != tcc_unary)
{
- if (vect_print_dump_info (REPORT_SLP))
+ if (vect_print_dump_info (REPORT_SLP))
{
fprintf (vect_dump, "Build SLP failed: operation");
fprintf (vect_dump, " unsupported ");
return false;
}
- /* Find the def-stmts. */
+ /* Find the def-stmts. */
if (!vect_get_and_check_slp_defs (loop_vinfo, bb_vinfo, *node, stmt,
&def_stmts0, &def_stmts1,
- &first_stmt_dt0, &first_stmt_dt1,
- &first_stmt_def0_type,
+ &first_stmt_dt0, &first_stmt_dt1,
+ &first_stmt_def0_type,
&first_stmt_def1_type,
&first_stmt_const_oprnd,
ncopies_for_cost,
}
/* Add the costs of the node to the overall instance costs. */
- *inside_cost += SLP_TREE_INSIDE_OF_LOOP_COST (*node);
+ *inside_cost += SLP_TREE_INSIDE_OF_LOOP_COST (*node);
*outside_cost += SLP_TREE_OUTSIDE_OF_LOOP_COST (*node);
/* Strided loads were reached - stop the recursion. */
{
if (permutation)
{
- VEC_safe_push (slp_tree, heap, *loads, *node);
- *inside_cost += TARG_VEC_PERMUTE_COST * group_size;
+ VEC_safe_push (slp_tree, heap, *loads, *node);
+ *inside_cost += TARG_VEC_PERMUTE_COST * group_size;
}
return true;
}
- /* Create SLP_TREE nodes for the definition node/s. */
+ /* Create SLP_TREE nodes for the definition node/s. */
if (first_stmt_dt0 == vect_internal_def)
{
slp_tree left_node = XNEW (struct _slp_tree);
SLP_TREE_RIGHT (left_node) = NULL;
SLP_TREE_OUTSIDE_OF_LOOP_COST (left_node) = 0;
SLP_TREE_INSIDE_OF_LOOP_COST (left_node) = 0;
- if (!vect_build_slp_tree (loop_vinfo, bb_vinfo, &left_node, group_size,
- inside_cost, outside_cost, ncopies_for_cost,
+ if (!vect_build_slp_tree (loop_vinfo, bb_vinfo, &left_node, group_size,
+ inside_cost, outside_cost, ncopies_for_cost,
max_nunits, load_permutation, loads,
vectorization_factor))
return false;
-
+
SLP_TREE_LEFT (*node) = left_node;
}
max_nunits, load_permutation, loads,
vectorization_factor))
return false;
-
+
SLP_TREE_RIGHT (*node) = right_node;
}
for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
{
fprintf (vect_dump, "\n\tstmt %d ", i);
- print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
+ print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
}
fprintf (vect_dump, "\n");
}
-/* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
- If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
- J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
+/* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
+ If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
+ J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
stmts in NODE are to be marked. */
static void
for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
{
stmt_info = vinfo_for_stmt (stmt);
- gcc_assert (!STMT_VINFO_RELEVANT (stmt_info)
+ gcc_assert (!STMT_VINFO_RELEVANT (stmt_info)
|| STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_scope);
STMT_VINFO_RELEVANT (stmt_info) = vect_used_in_scope;
}
}
-/* Check if the permutation required by the SLP INSTANCE is supported.
+/* Check if the permutation required by the SLP INSTANCE is supported.
Reorganize the SLP nodes stored in SLP_INSTANCE_LOADS if needed. */
static bool
VEC (slp_tree, heap) *sorted_loads = NULL;
int index;
slp_tree *tmp_loads = NULL;
- int group_size = SLP_INSTANCE_GROUP_SIZE (instance), i, j;
+ int group_size = SLP_INSTANCE_GROUP_SIZE (instance), i, j;
slp_tree load;
-
- /* FORNOW: The only supported loads permutation is loads from the same
+
+ /* FORNOW: The only supported loads permutation is loads from the same
location in all the loads in the node, when the data-refs in
- nodes of LOADS constitute an interleaving chain.
+ nodes of LOADS constitute an interleaving chain.
Sort the nodes according to the order of accesses in the chain. */
tmp_loads = (slp_tree *) xmalloc (sizeof (slp_tree) * group_size);
- for (i = 0, j = 0;
- VEC_iterate (int, SLP_INSTANCE_LOAD_PERMUTATION (instance), i, index)
- && VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), j, load);
+ for (i = 0, j = 0;
+ VEC_iterate (int, SLP_INSTANCE_LOAD_PERMUTATION (instance), i, index)
+ && VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), j, load);
i += group_size, j++)
{
gimple scalar_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (load), 0);
"permutation ");
print_gimple_stmt (vect_dump, scalar_stmt, 0, TDF_SLIM);
}
-
+
free (tmp_loads);
- return false;
+ return false;
}
tmp_loads[index] = load;
}
-
+
sorted_loads = VEC_alloc (slp_tree, heap, group_size);
for (i = 0; i < group_size; i++)
VEC_safe_push (slp_tree, heap, sorted_loads, tmp_loads[i]);
}
+/* Rearrange the statements of NODE according to PERMUTATION. */
+
+static void
+vect_slp_rearrange_stmts (slp_tree node, unsigned int group_size,
+ VEC (int, heap) *permutation)
+{
+ gimple stmt;
+ VEC (gimple, heap) *tmp_stmts;
+ unsigned int index, i;
+
+ if (!node)
+ return;
+
+ vect_slp_rearrange_stmts (SLP_TREE_LEFT (node), group_size, permutation);
+ vect_slp_rearrange_stmts (SLP_TREE_RIGHT (node), group_size, permutation);
+
+ gcc_assert (group_size == VEC_length (gimple, SLP_TREE_SCALAR_STMTS (node)));
+ tmp_stmts = VEC_alloc (gimple, heap, group_size);
+
+ for (i = 0; i < group_size; i++)
+ VEC_safe_push (gimple, heap, tmp_stmts, NULL);
+
+ for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
+ {
+ index = VEC_index (int, permutation, i);
+ VEC_replace (gimple, tmp_stmts, index, stmt);
+ }
+
+ VEC_free (gimple, heap, SLP_TREE_SCALAR_STMTS (node));
+ SLP_TREE_SCALAR_STMTS (node) = tmp_stmts;
+}
+
+
/* Check if the required load permutation is supported.
LOAD_PERMUTATION contains a list of indices of the loads.
In SLP this permutation is relative to the order of strided stores that are
vect_supported_load_permutation_p (slp_instance slp_instn, int group_size,
VEC (int, heap) *load_permutation)
{
- int i = 0, j, prev = -1, next, k;
- bool supported;
+ int i = 0, j, prev = -1, next, k, number_of_groups;
+ bool supported, bad_permutation = false;
+ sbitmap load_index;
+ slp_tree node;
+ gimple stmt;
/* FORNOW: permutations are only supported in SLP. */
if (!slp_instn)
fprintf (vect_dump, "%d ", next);
}
- /* FORNOW: the only supported permutation is 0..01..1.. of length equal to
- GROUP_SIZE and where each sequence of same drs is of GROUP_SIZE length as
- well. */
+ /* In case of reduction every load permutation is allowed, since the order
+ of the reduction statements is not important (as opposed to the case of
+ strided stores). The only condition we need to check is that all the
+ load nodes are of the same size and have the same permutation (and then
+ rearrange all the nodes of the SLP instance according to this
+ permutation). */
+
+ /* Check that all the load nodes are of the same size. */
+ for (i = 0;
+ VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (slp_instn), i, node);
+ i++)
+ if (VEC_length (gimple, SLP_TREE_SCALAR_STMTS (node))
+ != (unsigned) group_size)
+ return false;
+
+ node = SLP_INSTANCE_TREE (slp_instn);
+ stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
+ /* LOAD_PERMUTATION is a list of indices of all the loads of the SLP
+ instance, not all the loads belong to the same node or interleaving
+ group. Hence, we need to divide them into groups according to
+ GROUP_SIZE. */
+ number_of_groups = VEC_length (int, load_permutation) / group_size;
+
+ /* Reduction (there are no data-refs in the root). */
+ if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt)))
+ {
+ int first_group_load_index;
+
+ /* Compare all the permutation sequences to the first one. */
+ for (i = 1; i < number_of_groups; i++)
+ {
+ k = 0;
+ for (j = i * group_size; j < i * group_size + group_size; j++)
+ {
+ next = VEC_index (int, load_permutation, j);
+ first_group_load_index = VEC_index (int, load_permutation, k);
+
+ if (next != first_group_load_index)
+ {
+ bad_permutation = true;
+ break;
+ }
+
+ k++;
+ }
+
+ if (bad_permutation)
+ break;
+ }
+
+ if (!bad_permutation)
+ {
+ /* This permutaion is valid for reduction. Since the order of the
+ statements in the nodes is not important unless they are memory
+ accesses, we can rearrange the statements in all the nodes
+ according to the order of the loads. */
+ vect_slp_rearrange_stmts (SLP_INSTANCE_TREE (slp_instn), group_size,
+ load_permutation);
+ VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (slp_instn));
+ return true;
+ }
+ }
+
+ /* FORNOW: the only supported permutation is 0..01..1.. of length equal to
+ GROUP_SIZE and where each sequence of same drs is of GROUP_SIZE length as
+ well (unless it's reduction). */
if (VEC_length (int, load_permutation)
!= (unsigned int) (group_size * group_size))
return false;
supported = true;
+ load_index = sbitmap_alloc (group_size);
+ sbitmap_zero (load_index);
for (j = 0; j < group_size; j++)
{
for (i = j * group_size, k = 0;
}
prev = next;
- }
+ }
+
+ if (TEST_BIT (load_index, prev))
+ {
+ supported = false;
+ break;
+ }
+
+ SET_BIT (load_index, prev);
}
+
+ for (j = 0; j < group_size; j++)
+ if (!TEST_BIT (load_index, j))
+ return false;
+
+ sbitmap_free (load_index);
if (supported && i == group_size * group_size
&& vect_supported_slp_permutation_p (slp_instn))
return true;
- return false;
+ return false;
}
-/* Find the first load in the loop that belongs to INSTANCE.
+/* Find the first load in the loop that belongs to INSTANCE.
When loads are in several SLP nodes, there can be a case in which the first
- load does not appear in the first SLP node to be transformed, causing
+ load does not appear in the first SLP node to be transformed, causing
incorrect order of statements. Since we generate all the loads together,
they must be inserted before the first load of the SLP instance and not
before the first load of the first node of the instance. */
-static gimple
-vect_find_first_load_in_slp_instance (slp_instance instance)
+static gimple
+vect_find_first_load_in_slp_instance (slp_instance instance)
{
int i, j;
slp_tree load_node;
gimple first_load = NULL, load;
- for (i = 0;
- VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), i, load_node);
+ for (i = 0;
+ VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), i, load_node);
i++)
- for (j = 0;
+ for (j = 0;
VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (load_node), j, load);
j++)
first_load = get_earlier_stmt (load, first_load);
-
+
return first_load;
}
/* Analyze an SLP instance starting from a group of strided stores. Call
- vect_build_slp_tree to build a tree of packed stmts if possible.
+ vect_build_slp_tree to build a tree of packed stmts if possible.
Return FALSE if it's impossible to SLP any stmt in the loop. */
static bool
slp_tree node = XNEW (struct _slp_tree);
unsigned int group_size = DR_GROUP_SIZE (vinfo_for_stmt (stmt));
unsigned int unrolling_factor = 1, nunits;
- tree vectype, scalar_type;
+ tree vectype, scalar_type = NULL_TREE;
gimple next;
- unsigned int vectorization_factor = 0, ncopies;
- int inside_cost = 0, outside_cost = 0, ncopies_for_cost;
+ unsigned int vectorization_factor = 0;
+ int inside_cost = 0, outside_cost = 0, ncopies_for_cost, i;
unsigned int max_nunits = 0;
VEC (int, heap) *load_permutation;
VEC (slp_tree, heap) *loads;
-
- scalar_type = TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (
- vinfo_for_stmt (stmt))));
- vectype = get_vectype_for_scalar_type (scalar_type);
+ struct data_reference *dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
+
+ if (dr)
+ {
+ scalar_type = TREE_TYPE (DR_REF (dr));
+ vectype = get_vectype_for_scalar_type (scalar_type);
+ group_size = DR_GROUP_SIZE (vinfo_for_stmt (stmt));
+ }
+ else
+ {
+ gcc_assert (loop_vinfo);
+ vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
+ group_size = VEC_length (gimple, LOOP_VINFO_REDUCTIONS (loop_vinfo));
+ }
+
if (!vectype)
{
if (vect_print_dump_info (REPORT_SLP))
fprintf (vect_dump, "Build SLP failed: unsupported data-type ");
print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
}
+
return false;
}
/* No multitypes in BB SLP. */
vectorization_factor = nunits;
- ncopies = vectorization_factor / nunits;
-
/* Calculate the unrolling factor. */
unrolling_factor = least_common_multiple (nunits, group_size) / group_size;
if (unrolling_factor != 1 && !loop_vinfo)
{
if (vect_print_dump_info (REPORT_SLP))
- fprintf (vect_dump, "Build SLP failed: unrolling required in BB SLP");
-
+ fprintf (vect_dump, "Build SLP failed: unrolling required in basic"
+ " block SLP");
+
return false;
}
- /* Create a node (a root of the SLP tree) for the packed strided stores. */
+ /* Create a node (a root of the SLP tree) for the packed strided stores. */
SLP_TREE_SCALAR_STMTS (node) = VEC_alloc (gimple, heap, group_size);
next = stmt;
- /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
- while (next)
+ if (dr)
{
- VEC_safe_push (gimple, heap, SLP_TREE_SCALAR_STMTS (node), next);
- next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
+ /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
+ while (next)
+ {
+ VEC_safe_push (gimple, heap, SLP_TREE_SCALAR_STMTS (node), next);
+ next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
+ }
+ }
+ else
+ {
+ /* Collect reduction statements. */
+ for (i = 0; VEC_iterate (gimple, LOOP_VINFO_REDUCTIONS (loop_vinfo), i,
+ next);
+ i++)
+ {
+ VEC_safe_push (gimple, heap, SLP_TREE_SCALAR_STMTS (node), next);
+ if (vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "pushing reduction into node: ");
+ print_gimple_stmt (vect_dump, next, 0, TDF_SLIM);
+ }
+ }
}
SLP_TREE_VEC_STMTS (node) = NULL;
factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
GROUP_SIZE / NUNITS otherwise. */
ncopies_for_cost = unrolling_factor * group_size / nunits;
-
- load_permutation = VEC_alloc (int, heap, group_size * group_size);
- loads = VEC_alloc (slp_tree, heap, group_size);
+
+ load_permutation = VEC_alloc (int, heap, group_size * group_size);
+ loads = VEC_alloc (slp_tree, heap, group_size);
/* Build the tree for the SLP instance. */
- if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &node, group_size,
- &inside_cost, &outside_cost, ncopies_for_cost,
- &max_nunits, &load_permutation, &loads,
+ if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &node, group_size,
+ &inside_cost, &outside_cost, ncopies_for_cost,
+ &max_nunits, &load_permutation, &loads,
vectorization_factor))
{
- /* Create a new SLP instance. */
+ /* Create a new SLP instance. */
new_instance = XNEW (struct _slp_instance);
SLP_INSTANCE_TREE (new_instance) = node;
SLP_INSTANCE_GROUP_SIZE (new_instance) = group_size;
if (max_nunits > nunits)
unrolling_factor = least_common_multiple (max_nunits, group_size)
/ group_size;
-
+
SLP_INSTANCE_UNROLLING_FACTOR (new_instance) = unrolling_factor;
SLP_INSTANCE_OUTSIDE_OF_LOOP_COST (new_instance) = outside_cost;
SLP_INSTANCE_INSIDE_OF_LOOP_COST (new_instance) = inside_cost;
if (VEC_length (slp_tree, loads))
{
if (!vect_supported_load_permutation_p (new_instance, group_size,
- load_permutation))
+ load_permutation))
{
if (vect_print_dump_info (REPORT_SLP))
{
VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (new_instance));
if (loop_vinfo)
- VEC_safe_push (slp_instance, heap,
- LOOP_VINFO_SLP_INSTANCES (loop_vinfo),
+ VEC_safe_push (slp_instance, heap,
+ LOOP_VINFO_SLP_INSTANCES (loop_vinfo),
new_instance);
else
VEC_safe_push (slp_instance, heap, BB_VINFO_SLP_INSTANCES (bb_vinfo),
new_instance);
-
+
if (vect_print_dump_info (REPORT_SLP))
vect_print_slp_tree (node);
vect_free_slp_tree (node);
VEC_free (int, heap, load_permutation);
VEC_free (slp_tree, heap, loads);
-
+
return false;
}
vect_analyze_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
{
unsigned int i;
- VEC (gimple, heap) *strided_stores;
+ VEC (gimple, heap) *strided_stores, *reductions = NULL;
gimple store;
bool ok = false;
fprintf (vect_dump, "=== vect_analyze_slp ===");
if (loop_vinfo)
- strided_stores = LOOP_VINFO_STRIDED_STORES (loop_vinfo);
+ {
+ strided_stores = LOOP_VINFO_STRIDED_STORES (loop_vinfo);
+ reductions = LOOP_VINFO_REDUCTIONS (loop_vinfo);
+ }
else
strided_stores = BB_VINFO_STRIDED_STORES (bb_vinfo);
-
+
+ /* Find SLP sequences starting from groups of strided stores. */
for (i = 0; VEC_iterate (gimple, strided_stores, i, store); i++)
if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, store))
ok = true;
- if (bb_vinfo && !ok)
+ if (bb_vinfo && !ok)
{
if (vect_print_dump_info (REPORT_SLP))
fprintf (vect_dump, "Failed to SLP the basic block.");
return false;
}
+ /* Find SLP sequences starting from groups of reductions. */
+ if (loop_vinfo && VEC_length (gimple, LOOP_VINFO_REDUCTIONS (loop_vinfo))
+ && vect_analyze_slp_instance (loop_vinfo, bb_vinfo,
+ VEC_index (gimple, reductions, 0)))
+ ok = true;
+
return true;
}
if (unrolling_factor < SLP_INSTANCE_UNROLLING_FACTOR (instance))
unrolling_factor = SLP_INSTANCE_UNROLLING_FACTOR (instance);
- /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
- call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
+ /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
+ call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
loop-based vectorization. Such stmts will be marked as HYBRID. */
vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
decided_to_slp++;
LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo) = unrolling_factor;
- if (decided_to_slp && vect_print_dump_info (REPORT_SLP))
- fprintf (vect_dump, "Decided to SLP %d instances. Unrolling factor %d",
+ if (decided_to_slp && vect_print_dump_info (REPORT_SLP))
+ fprintf (vect_dump, "Decided to SLP %d instances. Unrolling factor %d",
decided_to_slp, unrolling_factor);
}
gimple stmt;
imm_use_iterator imm_iter;
gimple use_stmt;
+ stmt_vec_info stmt_vinfo;
if (!node)
return;
if (PURE_SLP_STMT (vinfo_for_stmt (stmt))
&& TREE_CODE (gimple_op (stmt, 0)) == SSA_NAME)
FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, gimple_op (stmt, 0))
- if (vinfo_for_stmt (use_stmt)
- && !STMT_SLP_TYPE (vinfo_for_stmt (use_stmt))
- && STMT_VINFO_RELEVANT (vinfo_for_stmt (use_stmt)))
+ if ((stmt_vinfo = vinfo_for_stmt (use_stmt))
+ && !STMT_SLP_TYPE (stmt_vinfo)
+ && (STMT_VINFO_RELEVANT (stmt_vinfo)
+ || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_vinfo)))
+ && !(gimple_code (use_stmt) == GIMPLE_PHI
+ && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (use_stmt))
+ == vect_reduction_def))
vect_mark_slp_stmts (node, hybrid, i);
vect_detect_hybrid_slp_stmts (SLP_TREE_LEFT (node));
/* Create and initialize a new bb_vec_info struct for BB, as well as
stmt_vec_info structs for all the stmts in it. */
-
+
static bb_vec_info
new_bb_vec_info (basic_block bb)
{
for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); )
{
- if (!vect_slp_analyze_node_operations (bb_vinfo,
+ if (!vect_slp_analyze_node_operations (bb_vinfo,
SLP_INSTANCE_TREE (instance)))
{
vect_free_slp_instance (instance);
}
else
i++;
- }
-
+ }
+
if (!VEC_length (slp_instance, slp_instances))
return false;
slp_instance instance;
int i, insns = 0;
gimple_stmt_iterator gsi;
+ int min_vf = 2;
+ int max_vf = MAX_VECTORIZATION_FACTOR;
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "===vect_slp_analyze_bb===\n");
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- insns++;
+ {
+ gimple stmt = gsi_stmt (gsi);
+ if (!is_gimple_debug (stmt)
+ && !gimple_nop_p (stmt)
+ && gimple_code (stmt) != GIMPLE_LABEL)
+ insns++;
+ }
if (insns > PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB))
{
if (!bb_vinfo)
return NULL;
- if (!vect_analyze_data_refs (NULL, bb_vinfo))
+ if (!vect_analyze_data_refs (NULL, bb_vinfo, &min_vf))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
fprintf (vect_dump, "not vectorized: unhandled data-ref in basic "
"block.\n");
-
+
destroy_bb_vec_info (bb_vinfo);
return NULL;
}
ddrs = BB_VINFO_DDRS (bb_vinfo);
- if (!VEC_length (ddr_p, ddrs))
+ if (!VEC_length (ddr_p, ddrs))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
fprintf (vect_dump, "not vectorized: not enough data-refs in basic "
return NULL;
}
+ if (!vect_analyze_data_ref_dependences (NULL, bb_vinfo, &max_vf)
+ || min_vf > max_vf)
+ {
+ if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
+ fprintf (vect_dump, "not vectorized: unhandled data dependence "
+ "in basic block.\n");
+
+ destroy_bb_vec_info (bb_vinfo);
+ return NULL;
+ }
+
if (!vect_analyze_data_refs_alignment (NULL, bb_vinfo))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
fprintf (vect_dump, "not vectorized: bad data alignment in basic "
"block.\n");
-
- destroy_bb_vec_info (bb_vinfo);
- return NULL;
- }
-
- if (!vect_analyze_data_ref_dependences (NULL, bb_vinfo))
- {
- if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
- fprintf (vect_dump, "not vectorized: unhandled data dependence in basic"
- " block.\n");
-
+
destroy_bb_vec_info (bb_vinfo);
return NULL;
}
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
fprintf (vect_dump, "not vectorized: unhandled data access in basic "
"block.\n");
-
+
destroy_bb_vec_info (bb_vinfo);
return NULL;
}
destroy_bb_vec_info (bb_vinfo);
return NULL;
}
-
+
slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
/* Mark all the statements that we want to vectorize as pure SLP and
{
vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance));
- }
+ }
if (!vect_slp_analyze_operations (bb_vinfo))
{
}
if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "BB will be vectorized using SLP\n");
+ fprintf (vect_dump, "Basic block will be vectorized using SLP\n");
return bb_vinfo;
}
-/* SLP costs are calculated according to SLP instance unrolling factor (i.e.,
+/* SLP costs are calculated according to SLP instance unrolling factor (i.e.,
the number of created vector stmts depends on the unrolling factor). However,
the actual number of vector stmts for every SLP node depends on VF which is
set later in vect_analyze_operations(). Hence, SLP costs should be updated.
- In this function we assume that the inside costs calculated in
+ In this function we assume that the inside costs calculated in
vect_model_xxx_cost are linear in ncopies. */
void
for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
/* We assume that costs are linear in ncopies. */
- SLP_INSTANCE_INSIDE_OF_LOOP_COST (instance) *= vf
- / SLP_INSTANCE_UNROLLING_FACTOR (instance);
+ SLP_INSTANCE_INSIDE_OF_LOOP_COST (instance) *= vf
+ / SLP_INSTANCE_UNROLLING_FACTOR (instance);
}
-/* For constant and loop invariant defs of SLP_NODE this function returns
- (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
+/* For constant and loop invariant defs of SLP_NODE this function returns
+ (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
OP_NUM determines if we gather defs for operand 0 or operand 1 of the scalar
- stmts. NUMBER_OF_VECTORS is the number of vector defs to create. */
+ stmts. NUMBER_OF_VECTORS is the number of vector defs to create.
+ REDUC_INDEX is the index of the reduction operand in the statements, unless
+ it is -1. */
static void
vect_get_constant_vectors (slp_tree slp_node, VEC(tree,heap) **vec_oprnds,
- unsigned int op_num, unsigned int number_of_vectors)
+ unsigned int op_num, unsigned int number_of_vectors,
+ int reduc_index)
{
VEC (gimple, heap) *stmts = SLP_TREE_SCALAR_STMTS (slp_node);
gimple stmt = VEC_index (gimple, stmts, 0);
stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
- tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
int nunits;
tree vec_cst;
tree t = NULL_TREE;
int number_of_copies = 1;
VEC (tree, heap) *voprnds = VEC_alloc (tree, heap, number_of_vectors);
bool constant_p, is_store;
+ tree neutral_op = NULL;
+
+ if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
+ {
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ if (reduc_index == -1)
+ {
+ VEC_free (tree, heap, *vec_oprnds);
+ return;
+ }
+
+ op_num = reduc_index - 1;
+ op = gimple_op (stmt, op_num + 1);
+ /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
+ we need either neutral operands or the original operands. See
+ get_initial_def_for_reduction() for details. */
+ switch (code)
+ {
+ case WIDEN_SUM_EXPR:
+ case DOT_PROD_EXPR:
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ case BIT_IOR_EXPR:
+ case BIT_XOR_EXPR:
+ if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op)))
+ neutral_op = build_real (TREE_TYPE (op), dconst0);
+ else
+ neutral_op = build_int_cst (TREE_TYPE (op), 0);
+
+ break;
+
+ case MULT_EXPR:
+ case BIT_AND_EXPR:
+ if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op)))
+ neutral_op = build_real (TREE_TYPE (op), dconst1);
+ else
+ neutral_op = build_int_cst (TREE_TYPE (op), 1);
+
+ break;
+
+ default:
+ neutral_op = NULL;
+ }
+ }
if (STMT_VINFO_DATA_REF (stmt_vinfo))
{
}
if (CONSTANT_CLASS_P (op))
- {
- vector_type = vectype;
- constant_p = true;
- }
+ constant_p = true;
else
- {
- vector_type = get_vectype_for_scalar_type (TREE_TYPE (op));
- gcc_assert (vector_type);
- constant_p = false;
- }
+ constant_p = false;
+
+ vector_type = get_vectype_for_scalar_type (TREE_TYPE (op));
+ gcc_assert (vector_type);
nunits = TYPE_VECTOR_SUBPARTS (vector_type);
/* NUMBER_OF_COPIES is the number of times we need to use the same values in
- created vectors. It is greater than 1 if unrolling is performed.
+ created vectors. It is greater than 1 if unrolling is performed.
For example, we have two scalar operands, s1 and s2 (e.g., group of
strided accesses of size two), while NUNITS is four (i.e., four scalars
two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
will be 2).
- If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
+ If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
containing the operands.
For example, NUNITS is four as before, and the group size is 8
(s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
{s5, s6, s7, s8}. */
-
+
number_of_copies = least_common_multiple (nunits, group_size) / group_size;
number_of_places_left_in_vector = nunits;
op = gimple_assign_rhs1 (stmt);
else
op = gimple_op (stmt, op_num + 1);
-
+
+ if (reduc_index != -1)
+ {
+ struct loop *loop = (gimple_bb (stmt))->loop_father;
+ gimple def_stmt = SSA_NAME_DEF_STMT (op);
+
+ gcc_assert (loop);
+ /* Get the def before the loop. */
+ op = PHI_ARG_DEF_FROM_EDGE (def_stmt,
+ loop_preheader_edge (loop));
+ if (j != (number_of_copies - 1) && neutral_op)
+ op = neutral_op;
+ }
+
/* Create 'vect_ = {op0,op1,...,opn}'. */
t = tree_cons (NULL_TREE, op, t);
}
}
- /* Since the vectors are created in the reverse order, we should invert
+ /* Since the vectors are created in the reverse order, we should invert
them. */
vec_num = VEC_length (tree, voprnds);
for (j = vec_num - 1; j >= 0; j--)
VEC_free (tree, heap, voprnds);
/* In case that VF is greater than the unrolling factor needed for the SLP
- group of stmts, NUMBER_OF_VECTORS to be created is greater than
- NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
+ group of stmts, NUMBER_OF_VECTORS to be created is greater than
+ NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
to replicate the vectors. */
while (number_of_vectors > VEC_length (tree, *vec_oprnds))
{
- for (i = 0; VEC_iterate (tree, *vec_oprnds, i, vop) && i < vec_num; i++)
- VEC_quick_push (tree, *vec_oprnds, vop);
+ tree neutral_vec = NULL;
+
+ if (neutral_op)
+ {
+ if (!neutral_vec)
+ {
+ t = NULL;
+ for (i = 0; i < (unsigned) nunits; i++)
+ t = tree_cons (NULL_TREE, neutral_op, t);
+ neutral_vec = build_vector (vector_type, t);
+ }
+
+ VEC_quick_push (tree, *vec_oprnds, neutral_vec);
+ }
+ else
+ {
+ for (i = 0; VEC_iterate (tree, *vec_oprnds, i, vop) && i < vec_num; i++)
+ VEC_quick_push (tree, *vec_oprnds, vop);
+ }
}
}
}
-/* Get vectorized definitions for SLP_NODE.
- If the scalar definitions are loop invariants or constants, collect them and
+/* Get vectorized definitions for SLP_NODE.
+ If the scalar definitions are loop invariants or constants, collect them and
call vect_get_constant_vectors() to create vector stmts.
Otherwise, the def-stmts must be already vectorized and the vectorized stmts
must be stored in the LEFT/RIGHT node of SLP_NODE, and we call
- vect_get_slp_vect_defs() to retrieve them.
+ vect_get_slp_vect_defs() to retrieve them.
If VEC_OPRNDS1 is NULL, don't get vector defs for the second operand (from
- the right node. This is used when the second operand must remain scalar. */
-
+ the right node. This is used when the second operand must remain scalar. */
+
void
vect_get_slp_defs (slp_tree slp_node, VEC (tree,heap) **vec_oprnds0,
- VEC (tree,heap) **vec_oprnds1)
+ VEC (tree,heap) **vec_oprnds1, int reduc_index)
{
gimple first_stmt;
enum tree_code code;
int number_of_vects;
- HOST_WIDE_INT lhs_size_unit, rhs_size_unit;
+ HOST_WIDE_INT lhs_size_unit, rhs_size_unit;
first_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0);
/* The number of vector defs is determined by the number of vector statements
in the node from which we get those statements. */
- if (SLP_TREE_LEFT (slp_node))
+ if (SLP_TREE_LEFT (slp_node))
number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_LEFT (slp_node));
else
{
*vec_oprnds0 = VEC_alloc (tree, heap, number_of_vects);
/* SLP_NODE corresponds either to a group of stores or to a group of
- unary/binary operations. We don't call this function for loads. */
- if (SLP_TREE_LEFT (slp_node))
+ unary/binary operations. We don't call this function for loads.
+ For reduction defs we call vect_get_constant_vectors(), since we are
+ looking for initial loop invariant values. */
+ if (SLP_TREE_LEFT (slp_node) && reduc_index == -1)
/* The defs are already vectorized. */
vect_get_slp_vect_defs (SLP_TREE_LEFT (slp_node), vec_oprnds0);
else
/* Build vectors from scalar defs. */
- vect_get_constant_vectors (slp_node, vec_oprnds0, 0, number_of_vects);
+ vect_get_constant_vectors (slp_node, vec_oprnds0, 0, number_of_vects,
+ reduc_index);
if (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt)))
/* Since we don't call this function with loads, this is a group of
stores. */
return;
+ /* For reductions, we only need initial values. */
+ if (reduc_index != -1)
+ return;
+
code = gimple_assign_rhs_code (first_stmt);
if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS || !vec_oprnds1)
return;
vect_get_slp_vect_defs (SLP_TREE_RIGHT (slp_node), vec_oprnds1);
else
/* Build vectors from scalar defs. */
- vect_get_constant_vectors (slp_node, vec_oprnds1, 1, number_of_vects);
+ vect_get_constant_vectors (slp_node, vec_oprnds1, 1, number_of_vects, -1);
}
-/* Create NCOPIES permutation statements using the mask MASK_BYTES (by
+/* Create NCOPIES permutation statements using the mask MASK_BYTES (by
building a vector of type MASK_TYPE from it) and two input vectors placed in
DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
shifting by STRIDE elements of DR_CHAIN for every copy.
(STRIDE is the number of vectorized stmts for NODE divided by the number of
- copies).
+ copies).
VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
the created stmts must be inserted. */
static inline void
-vect_create_mask_and_perm (gimple stmt, gimple next_scalar_stmt,
- int *mask_array, int mask_nunits,
- tree mask_element_type, tree mask_type,
- int first_vec_indx, int second_vec_indx,
- gimple_stmt_iterator *gsi, slp_tree node,
- tree builtin_decl, tree vectype,
+vect_create_mask_and_perm (gimple stmt, gimple next_scalar_stmt,
+ tree mask, int first_vec_indx, int second_vec_indx,
+ gimple_stmt_iterator *gsi, slp_tree node,
+ tree builtin_decl, tree vectype,
VEC(tree,heap) *dr_chain,
int ncopies, int vect_stmts_counter)
{
- tree t = NULL_TREE, mask_vec, mask, perm_dest;
+ tree perm_dest;
gimple perm_stmt = NULL;
stmt_vec_info next_stmt_info;
- int i, group_size, stride, dr_chain_size;
+ int i, stride;
tree first_vec, second_vec, data_ref;
VEC (tree, heap) *params = NULL;
- /* Create a vector mask. */
- for (i = mask_nunits - 1; i >= 0; --i)
- t = tree_cons (NULL_TREE, build_int_cst (mask_element_type, mask_array[i]),
- t);
- mask_vec = build_vector (mask_type, t);
- mask = vect_init_vector (stmt, mask_vec, mask_type, NULL);
-
- group_size = VEC_length (gimple, SLP_TREE_SCALAR_STMTS (node));
stride = SLP_TREE_NUMBER_OF_VEC_STMTS (node) / ncopies;
- dr_chain_size = VEC_length (tree, dr_chain);
- /* Initialize the vect stmts of NODE to properly insert the generated
+ /* Initialize the vect stmts of NODE to properly insert the generated
stmts later. */
- for (i = VEC_length (gimple, SLP_TREE_VEC_STMTS (node));
+ for (i = VEC_length (gimple, SLP_TREE_VEC_STMTS (node));
i < (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node); i++)
VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (node), NULL);
gimple_call_set_lhs (perm_stmt, data_ref);
vect_finish_stmt_generation (stmt, perm_stmt, gsi);
- /* Store the vector statement in NODE. */
- VEC_replace (gimple, SLP_TREE_VEC_STMTS (node),
+ /* Store the vector statement in NODE. */
+ VEC_replace (gimple, SLP_TREE_VEC_STMTS (node),
stride * i + vect_stmts_counter, perm_stmt);
first_vec_indx += stride;
}
-/* Given FIRST_MASK_ELEMENT - the mask element in element representation,
+/* Given FIRST_MASK_ELEMENT - the mask element in element representation,
return in CURRENT_MASK_ELEMENT its equivalent in target specific
- representation. Check that the mask is valid and return FALSE if not.
+ representation. Check that the mask is valid and return FALSE if not.
Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
the next vector, i.e., the current first vector is not needed. */
-
+
static bool
-vect_get_mask_element (gimple stmt, int first_mask_element, int m,
+vect_get_mask_element (gimple stmt, int first_mask_element, int m,
int mask_nunits, bool only_one_vec, int index,
- int *mask, int *current_mask_element,
+ int *mask, int *current_mask_element,
bool *need_next_vector)
{
int i;
if (needs_first_vector || mask_fixed)
{
/* We either need the first vector too or have already moved to the
- next vector. In both cases, this permutation needs three
+ next vector. In both cases, this permutation needs three
vectors. */
if (vect_print_dump_info (REPORT_DETAILS))
{
/* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
unrolling factor. */
- orig_vec_stmts_num = group_size *
+ orig_vec_stmts_num = group_size *
SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance) / nunits;
if (orig_vec_stmts_num == 1)
only_one_vec = true;
- /* Number of copies is determined by the final vectorization factor
+ /* Number of copies is determined by the final vectorization factor
relatively to SLP_NODE_INSTANCE unrolling factor. */
- ncopies = vf / SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance);
+ ncopies = vf / SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance);
- /* Generate permutation masks for every NODE. Number of masks for each NODE
- is equal to GROUP_SIZE.
- E.g., we have a group of three nodes with three loads from the same
- location in each node, and the vector size is 4. I.e., we have a
- a0b0c0a1b1c1... sequence and we need to create the following vectors:
+ /* Generate permutation masks for every NODE. Number of masks for each NODE
+ is equal to GROUP_SIZE.
+ E.g., we have a group of three nodes with three loads from the same
+ location in each node, and the vector size is 4. I.e., we have a
+ a0b0c0a1b1c1... sequence and we need to create the following vectors:
for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
...
The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9} (in target
scpecific type, e.g., in bytes for Altivec.
- The last mask is illegal since we assume two operands for permute
+ The last mask is illegal since we assume two operands for permute
operation, and the mask element values can't be outside that range. Hence,
the last mask must be converted into {2,5,5,5}.
- For the first two permutations we need the first and the second input
+ For the first two permutations we need the first and the second input
vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
- we need the second and the third vectors: {b1,c1,a2,b2} and
+ we need the second and the third vectors: {b1,c1,a2,b2} and
{c2,a3,b3,c3}. */
for (i = 0;
first_mask_element = (i + j * group_size) * scale;
for (m = 0; m < scale; m++)
{
- if (!vect_get_mask_element (stmt, first_mask_element, m,
+ if (!vect_get_mask_element (stmt, first_mask_element, m,
mask_nunits, only_one_vec, index, mask,
¤t_mask_element, &need_next_vector))
return false;
mask[index++] = current_mask_element;
- }
+ }
if (index == mask_nunits)
{
- index = 0;
+ tree mask_vec = NULL;
+
+ while (--index >= 0)
+ {
+ tree t = build_int_cst (mask_element_type, mask[index]);
+ mask_vec = tree_cons (NULL, t, mask_vec);
+ }
+ mask_vec = build_vector (mask_type, mask_vec);
+ index = 0;
+
+ if (!targetm.vectorize.builtin_vec_perm_ok (vectype,
+ mask_vec))
+ {
+ if (vect_print_dump_info (REPORT_DETAILS))
+ {
+ fprintf (vect_dump, "unsupported vect permute ");
+ print_generic_expr (vect_dump, mask_vec, 0);
+ }
+ free (mask);
+ return false;
+ }
+
if (!analyze_only)
{
if (need_next_vector)
SLP_TREE_SCALAR_STMTS (node), scalar_index++);
vect_create_mask_and_perm (stmt, next_scalar_stmt,
- mask, mask_nunits, mask_element_type, mask_type,
- first_vec_index, second_vec_index, gsi, node,
- builtin_decl, vectype, dr_chain, ncopies,
- vect_stmts_counter++);
+ mask_vec, first_vec_index, second_vec_index,
+ gsi, node, builtin_decl, vectype, dr_chain,
+ ncopies, vect_stmts_counter++);
}
- }
- }
- }
- }
+ }
+ }
+ }
+ }
free (mask);
return true;
vectorization_factor);
vect_schedule_slp_instance (SLP_TREE_RIGHT (node), instance,
vectorization_factor);
-
+
stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
stmt_info = vinfo_for_stmt (stmt);
/* VECTYPE is the type of the destination. */
- vectype = get_vectype_for_scalar_type (TREE_TYPE (gimple_assign_lhs (stmt)));
+ vectype = STMT_VINFO_VECTYPE (stmt_info);
nunits = (unsigned int) TYPE_VECTOR_SUBPARTS (vectype);
group_size = SLP_INSTANCE_GROUP_SIZE (instance);
{
fprintf (vect_dump, "------>vectorizing SLP node starting from: ");
print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
- }
+ }
/* Loads should be inserted before the first load. */
if (SLP_INSTANCE_FIRST_LOAD_STMT (instance)
si = gsi_for_stmt (SLP_INSTANCE_FIRST_LOAD_STMT (instance));
else
si = gsi_for_stmt (stmt);
-
- is_store = vect_transform_stmt (stmt, &si, &strided_store, node, instance);
- if (is_store)
- {
- if (DR_GROUP_FIRST_DR (stmt_info))
- /* If IS_STORE is TRUE, the vectorization of the
- interleaving chain was completed - free all the stores in
- the chain. */
- vect_remove_stores (DR_GROUP_FIRST_DR (stmt_info));
- else
- /* FORNOW: SLP originates only from strided stores. */
- gcc_unreachable ();
-
- return true;
- }
- /* FORNOW: SLP originates only from strided stores. */
- return false;
+ is_store = vect_transform_stmt (stmt, &si, &strided_store, node, instance);
+ return is_store;
}
{
slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
- }
+ }
else
{
slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
vf = 1;
- }
+ }
for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
{
fprintf (vect_dump, "vectorizing stmts using SLP.");
}
+ for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
+ {
+ slp_tree root = SLP_INSTANCE_TREE (instance);
+ gimple store;
+ unsigned int j;
+ gimple_stmt_iterator gsi;
+
+ for (j = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (root), j, store)
+ && j < SLP_INSTANCE_GROUP_SIZE (instance); j++)
+ {
+ if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store)))
+ break;
+
+ /* Free the attached stmt_vec_info and remove the stmt. */
+ gsi = gsi_for_stmt (store);
+ gsi_remove (&gsi, true);
+ free_stmt_vec_info (store);
+ }
+ }
+
return is_store;
}
update_ssa (TODO_update_ssa);
if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "BB VECTORIZED\n");
+ fprintf (vect_dump, "BASIC BLOCK VECTORIZED\n");
destroy_bb_vec_info (bb_vinfo);
}