[gcc(refs/users/rguenth/heads/slp-reorg)] remove SLP_TREE_TWO_OPERATORS
Richard Biener
rguenth@gcc.gnu.org
Mon Mar 23 16:01:14 GMT 2020
https://gcc.gnu.org/g:db28fe743a07ed971c2a8e44ee2fbdf5a999d051
commit db28fe743a07ed971c2a8e44ee2fbdf5a999d051
Author: Richard Biener <rguenther@suse.de>
Date: Mon Mar 16 15:07:24 2020 +0100
remove SLP_TREE_TWO_OPERATORS
This removes the SLP_TREE_TWO_OPERATORS hack in favor of having
explicit SLP nodes for both computations and the blend operation
thereby introducing a generic merge + select + permute SLP node
(with implementation limits).
TODO refactoring:
- make SLP node sharing work on ->ops[] rather than ->stmts[],
make SLP_TREE_TWO_OPERATORS lowering nodes properly shared then
- make use of SLP_TREE_CODE instead of relying on ->stmts[0]
- add stmt_vec_info_type to the SLP node
- populate SLP_TREE_TYPE where we otherwise compute the vectype
2020-03-13 Richard Biener <rguenther@suse.de>
* tree-vectorizer.h (_slp_tree::_slp_tree): Add CTOR.
(_slp_tree::~_slp_tree): Add DTOR.
(_slp_tree::classify): New method.
(_slp_tree::n_lanes): Likewise.
(_slp_tree::lane_permutation): New member.
(_slp_tree::vectype): Likewise.
(_slp_tree::code): Likewise.
(_slp_tree::two_operators): Remove.
(SLP_TREE_TWO_OPERATORS): Remove.
(SLP_TREE_LANE_PERMUTATION): New.
(SLP_TREE_CODE): Likewise.
(SLP_TREE_VECTYPE): Likewise.
* tree-vect-slp.c (_slp_tree::_slp_tree): Implement.
(_slp_tree::~_slp_tree): Likewise.
(vect_free_slp_tree): Use delete instead of free.
(vect_create_new_slp_node): Use new instead of XNEW.
(_slp_tree::classify): Implement.
(_slp_tree::n_lanes): Likewise.
(vect_build_slp_tree_2): When we have two different operators
build two computation SLP nodes and a blend.
(...): Adjustments for NULL ->stmts[] hack.
(vect_find_last_scalar_stmt_in_slp): Check children for
placement.
(vectorizable_slp_permutation): New function.
Diff:
---
gcc/tree-vect-slp.c | 528 +++++++++++++++++++++++++++++++++++---------------
gcc/tree-vect-stmts.c | 10 +-
gcc/tree-vectorizer.h | 22 ++-
3 files changed, 387 insertions(+), 173 deletions(-)
diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c
index a1f08814a62..0910d37e5f7 100644
--- a/gcc/tree-vect-slp.c
+++ b/gcc/tree-vect-slp.c
@@ -46,6 +46,39 @@ along with GCC; see the file COPYING3. If not see
#include "internal-fn.h"
+static bool vectorizable_slp_permutation (vec_info *, gimple_stmt_iterator *,
+ slp_tree, stmt_vector_for_cost *);
+
+/* Initialize a SLP node. */
+
+_slp_tree::_slp_tree ()
+{
+ SLP_TREE_SCALAR_STMTS (this) = vNULL;
+ SLP_TREE_SCALAR_OPS (this) = vNULL;
+ SLP_TREE_VEC_STMTS (this).create (0);
+ SLP_TREE_NUMBER_OF_VEC_STMTS (this) = 0;
+ SLP_TREE_CHILDREN (this) = vNULL;
+ SLP_TREE_LOAD_PERMUTATION (this) = vNULL;
+ SLP_TREE_LANE_PERMUTATION (this) = vNULL;
+ SLP_TREE_DEF_TYPE (this) = vect_internal_def;
+ SLP_TREE_CODE (this) = ERROR_MARK;
+ SLP_TREE_VECTYPE (this) = NULL_TREE;
+ this->refcnt = 1;
+ this->max_nunits = 1;
+}
+
+/* Tear down a SLP node. */
+
+_slp_tree::~_slp_tree ()
+{
+ SLP_TREE_CHILDREN (this).release ();
+ SLP_TREE_SCALAR_STMTS (this).release ();
+ SLP_TREE_SCALAR_OPS (this).release ();
+ SLP_TREE_VEC_STMTS (this).release ();
+ SLP_TREE_LOAD_PERMUTATION (this).release ();
+ SLP_TREE_LANE_PERMUTATION (this).release ();
+}
+
/* Recursively free the memory allocated for the SLP tree rooted at NODE.
FINAL_P is true if we have vectorized the instance or if we have
made a final decision not to vectorize the statements in any way. */
@@ -71,18 +104,13 @@ vect_free_slp_tree (slp_tree node, bool final_p)
stmt_vec_info stmt_info;
FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt_info)
{
+ if (!stmt_info) continue;
gcc_assert (STMT_VINFO_NUM_SLP_USES (stmt_info) > 0);
STMT_VINFO_NUM_SLP_USES (stmt_info)--;
}
}
- SLP_TREE_CHILDREN (node).release ();
- SLP_TREE_SCALAR_STMTS (node).release ();
- SLP_TREE_SCALAR_OPS (node).release ();
- SLP_TREE_VEC_STMTS (node).release ();
- SLP_TREE_LOAD_PERMUTATION (node).release ();
-
- free (node);
+ delete node;
}
/* Free the memory allocated for the SLP instance. FINAL_P is true if we
@@ -120,17 +148,10 @@ vect_create_new_slp_node (vec<stmt_vec_info> scalar_stmts)
else
return NULL;
- node = XNEW (struct _slp_tree);
+ node = new _slp_tree;
SLP_TREE_SCALAR_STMTS (node) = scalar_stmts;
- SLP_TREE_SCALAR_OPS (node) = vNULL;
- SLP_TREE_VEC_STMTS (node).create (0);
- SLP_TREE_NUMBER_OF_VEC_STMTS (node) = 0;
SLP_TREE_CHILDREN (node).create (nops);
- SLP_TREE_LOAD_PERMUTATION (node) = vNULL;
- SLP_TREE_TWO_OPERATORS (node) = false;
SLP_TREE_DEF_TYPE (node) = vect_internal_def;
- node->refcnt = 1;
- node->max_nunits = 1;
unsigned i;
FOR_EACH_VEC_ELT (scalar_stmts, i, stmt_info)
@@ -146,21 +167,41 @@ vect_create_new_slp_node (vec<tree> ops)
{
slp_tree node;
- node = XNEW (struct _slp_tree);
- SLP_TREE_SCALAR_STMTS (node) = vNULL;
+ node = new _slp_tree;
SLP_TREE_SCALAR_OPS (node) = ops;
- SLP_TREE_VEC_STMTS (node).create (0);
- SLP_TREE_NUMBER_OF_VEC_STMTS (node) = 0;
- SLP_TREE_CHILDREN (node) = vNULL;
- SLP_TREE_LOAD_PERMUTATION (node) = vNULL;
- SLP_TREE_TWO_OPERATORS (node) = false;
SLP_TREE_DEF_TYPE (node) = vect_external_def;
- node->refcnt = 1;
- node->max_nunits = 1;
return node;
}
+/* While in transient representation state provide a helper to
+ classify SLP node kinds. */
+
+_slp_tree::kind
+_slp_tree::classify ()
+{
+ if (lane_permutation.exists ())
+ /* concat children and apply permute mask. */
+ return SLP_CPERM;
+
+ return SLP_OTHER;
+}
+
+/* Returns the number of lanes in the node. */
+
+unsigned
+_slp_tree::n_lanes ()
+{
+ if (stmts.exists ())
+ return stmts.length ();
+ if (ops.exists ())
+ return ops.length ();
+ if (lane_permutation.exists ())
+ return lane_permutation.length ();
+ /* ??? If we introduce "pure" SLP non-permute ops we might want to
+ have an explicit number of lanes member. */
+ __builtin_unreachable ();
+}
/* This structure is used in creation of an SLP tree. Each instance
corresponds to the same operand in a group of scalar stmts in an SLP
@@ -721,35 +762,6 @@ vect_record_max_nunits (vec_info *vinfo, stmt_vec_info stmt_info,
return true;
}
-/* STMTS is a group of GROUP_SIZE SLP statements in which some
- statements do the same operation as the first statement and in which
- the others do ALT_STMT_CODE. Return true if we can take one vector
- of the first operation and one vector of the second and permute them
- to get the required result. VECTYPE is the type of the vector that
- would be permuted. */
-
-static bool
-vect_two_operations_perm_ok_p (vec<stmt_vec_info> stmts,
- unsigned int group_size, tree vectype,
- tree_code alt_stmt_code)
-{
- unsigned HOST_WIDE_INT count;
- if (!TYPE_VECTOR_SUBPARTS (vectype).is_constant (&count))
- return false;
-
- vec_perm_builder sel (count, count, 1);
- for (unsigned int i = 0; i < count; ++i)
- {
- unsigned int elt = i;
- gassign *stmt = as_a <gassign *> (stmts[i % group_size]->stmt);
- if (gimple_assign_rhs_code (stmt) == alt_stmt_code)
- elt += count;
- sel.quick_push (elt);
- }
- vec_perm_indices indices (sel, 2, count);
- return can_vec_perm_const_p (TYPE_MODE (vectype), indices);
-}
-
/* Verify if the scalar stmts STMTS are isomorphic, require data
permutation or are of unsupported types of operation. Return
true if they are, otherwise return false and indicate in *MATCHES
@@ -768,7 +780,7 @@ static bool
vect_build_slp_tree_1 (vec_info *vinfo, unsigned char *swap,
vec<stmt_vec_info> stmts, unsigned int group_size,
poly_uint64 *max_nunits, bool *matches,
- bool *two_operators)
+ bool *two_operators, tree *node_vectype)
{
unsigned int i;
stmt_vec_info first_stmt_info = stmts[0];
@@ -872,6 +884,7 @@ vect_build_slp_tree_1 (vec_info *vinfo, unsigned char *swap,
/* Check the operation. */
if (i == 0)
{
+ *node_vectype = vectype;
first_stmt_code = rhs_code;
/* Shift arguments should be equal in all the packed stmts for a
@@ -1112,24 +1125,6 @@ vect_build_slp_tree_1 (vec_info *vinfo, unsigned char *swap,
if (alt_stmt_code != ERROR_MARK
&& TREE_CODE_CLASS (alt_stmt_code) != tcc_reference)
{
- if (!vect_two_operations_perm_ok_p (stmts, group_size,
- vectype, alt_stmt_code))
- {
- for (i = 0; i < group_size; ++i)
- if (gimple_assign_rhs_code (stmts[i]->stmt) == alt_stmt_code)
- {
- matches[i] = false;
- if (dump_enabled_p ())
- {
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "Build SLP failed: different operation "
- "in stmt %G", stmts[i]->stmt);
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "original stmt %G", first_stmt_info->stmt);
- }
- }
- return false;
- }
*two_operators = true;
}
@@ -1289,8 +1284,10 @@ vect_build_slp_tree_2 (vec_info *vinfo,
bool two_operators = false;
unsigned char *swap = XALLOCAVEC (unsigned char, group_size);
+ tree vectype = NULL_TREE;
if (!vect_build_slp_tree_1 (vinfo, swap, stmts, group_size,
- &this_max_nunits, matches, &two_operators))
+ &this_max_nunits, matches, &two_operators,
+ &vectype))
return NULL;
/* If the SLP node is a load, terminate the recursion unless masked. */
@@ -1307,7 +1304,8 @@ vect_build_slp_tree_2 (vec_info *vinfo,
{
*max_nunits = this_max_nunits;
(*tree_size)++;
- node = vect_create_new_slp_node (stmts);
+ node = vect_create_new_slp_node (vinfo, defs, nops);
+ SLP_TREE_VECTYPE (node) = vectype;
/* And compute the load permutation. Whether it is actually
a permutation depends on the unrolling factor which is
decided later. */
@@ -1585,8 +1583,60 @@ fail:
*tree_size += this_tree_size + 1;
*max_nunits = this_max_nunits;
- node = vect_create_new_slp_node (stmts);
- SLP_TREE_TWO_OPERATORS (node) = two_operators;
+ if (two_operators)
+ {
+ /* ??? We'd likely want to either cache in bst_map sth like
+ { a+b, NULL, a+b, NULL } and { NULL, a-b, NULL, a-b } or
+ the true { a+b, a+b, a+b, a+b } ... but there we don't have
+ explicit stmts to put in so the keying on 'stmts' doesn't
+ work (but we have the same issue with nodes that use 'ops'). */
+ slp_tree one = new _slp_tree;
+ slp_tree two = new _slp_tree;
+ SLP_TREE_VECTYPE (one) = vectype;
+ SLP_TREE_VECTYPE (two) = vectype;
+ SLP_TREE_CHILDREN (one).safe_splice (children);
+ SLP_TREE_CHILDREN (two).safe_splice (children);
+ slp_tree child;
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (two), i, child)
+ child->refcnt++;
+
+ /* Here we record the original defs since this
+ node represents the final lane configuration. */
+ node = vect_create_new_slp_node (vinfo, defs, 2);
+ SLP_TREE_VECTYPE (node) = vectype;
+ SLP_TREE_CHILDREN (node).quick_push (one);
+ SLP_TREE_CHILDREN (node).quick_push (two);
+ gassign *stmt = as_a <gassign *> (stmts[0]->stmt);
+ enum tree_code code0 = gimple_assign_rhs_code (stmt);
+ enum tree_code ocode = ERROR_MARK;
+ stmt_vec_info ostmt_info;
+ unsigned j;
+ FOR_EACH_VEC_ELT (stmts, i, ostmt_info)
+ {
+ gassign *ostmt = as_a <gassign *> (ostmt_info->stmt);
+ if (gimple_assign_rhs_code (ostmt) != code0)
+ {
+ SLP_TREE_LANE_PERMUTATION (node).safe_push (std::make_pair (1, i));
+ ocode = gimple_assign_rhs_code (ostmt);
+ j = i;
+ }
+ else
+ SLP_TREE_LANE_PERMUTATION (node).safe_push (std::make_pair (0, i));
+ }
+ SLP_TREE_CODE (one) = code0;
+ SLP_TREE_CODE (two) = ocode;
+ /* Fake some stmts for now. */
+ SLP_TREE_SCALAR_STMTS (one).safe_grow_cleared (stmts.length ());
+ SLP_TREE_SCALAR_STMTS (two).safe_grow_cleared (stmts.length ());
+ SLP_TREE_SCALAR_STMTS (one)[0] = stmts[0];
+ STMT_VINFO_NUM_SLP_USES (stmts[0])++;
+ SLP_TREE_SCALAR_STMTS (two)[0] = stmts[j];
+ STMT_VINFO_NUM_SLP_USES (stmts[j])++;
+ return node;
+ }
+
+ node = vect_create_new_slp_node (vinfo, defs, nops);
+ SLP_TREE_VECTYPE (node) = vectype;
SLP_TREE_CHILDREN (node).splice (children);
return node;
}
@@ -1616,7 +1666,10 @@ vect_print_slp_tree (dump_flags_t dump_kind, dump_location_t loc,
estimated_poly_value (node->max_nunits), node->refcnt);
if (SLP_TREE_SCALAR_STMTS (node).exists ())
FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt_info)
- dump_printf_loc (metadata, user_loc, "\tstmt %u %G", i, stmt_info->stmt);
+ if (!stmt_info)
+ dump_printf_loc (metadata, user_loc, "\tNULL\n");
+ else
+ dump_printf_loc (metadata, user_loc, "\tstmt %u %G", i, stmt_info->stmt);
else
{
dump_printf_loc (metadata, user_loc, "\t{ ");
@@ -1666,7 +1719,7 @@ vect_mark_slp_stmts (slp_tree node, hash_set<slp_tree> &visited)
return;
FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt_info)
- STMT_SLP_TYPE (stmt_info) = pure_slp;
+ if (stmt_info) STMT_SLP_TYPE (stmt_info) = pure_slp;
FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
vect_mark_slp_stmts (child, visited);
@@ -1696,6 +1749,7 @@ vect_mark_slp_stmts_relevant (slp_tree node, hash_set<slp_tree> &visited)
FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt_info)
{
+ if (!stmt_info) continue;
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;
@@ -1933,11 +1987,24 @@ vect_find_last_scalar_stmt_in_slp (slp_tree node)
stmt_vec_info last = NULL;
stmt_vec_info stmt_vinfo;
+ bool check_ops = false;
for (int i = 0; SLP_TREE_SCALAR_STMTS (node).iterate (i, &stmt_vinfo); i++)
{
+ if (!stmt_vinfo) { check_ops = true; break; }
stmt_vinfo = vect_orig_stmt (stmt_vinfo);
last = last ? get_later_stmt (stmt_vinfo, last) : stmt_vinfo;
}
+ if (check_ops)
+ {
+ last = NULL;
+ int i;
+ slp_tree child;
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ {
+ stmt_vinfo = vect_find_last_scalar_stmt_in_slp (child);
+ last = last ? get_later_stmt (stmt_vinfo, last) : stmt_vinfo;
+ }
+ }
return last;
}
@@ -2514,9 +2581,6 @@ vect_detect_hybrid_slp_stmts (loop_vec_info loop_vinfo, slp_tree node,
imm_use_iterator imm_iter;
gimple *use_stmt;
stmt_vec_info use_vinfo;
- slp_tree child;
- loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
- int j;
/* We need to union stype over the incoming graph edges but we still
want to limit recursion to stay O(N+E). */
@@ -2524,6 +2588,7 @@ vect_detect_hybrid_slp_stmts (loop_vec_info loop_vinfo, slp_tree node,
gcc_assert (visited_cnt <= node->refcnt);
bool only_edge = (visited_cnt != node->refcnt);
+ if (stmt_vinfo) {
/* Propagate hybrid down the SLP tree. */
if (stype == hybrid)
;
@@ -2570,7 +2635,10 @@ vect_detect_hybrid_slp_stmts (loop_vec_info loop_vinfo, slp_tree node,
stmt_vinfo->stmt);
STMT_SLP_TYPE (stmt_vinfo) = hybrid;
}
+ }
+ slp_tree child;
+ int j;
if (!only_edge)
FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), j, child)
if (SLP_TREE_DEF_TYPE (child) != vect_external_def
@@ -2758,9 +2826,18 @@ vect_slp_analyze_node_operations_1 (vec_info *vinfo, slp_tree node,
= vect_get_num_vectors (vf * group_size, vectype);
}
+ /* Handle purely internal nodes. */
+ if (node->classify () == _slp_tree::SLP_CPERM)
+ return vectorizable_slp_permutation (vinfo, NULL, node, cost_vec);
+
bool dummy;
- return vect_analyze_stmt (vinfo, stmt_info, &dummy,
- node, node_instance, cost_vec);
+ dummy = vect_analyze_stmt (vinfo, stmt_info, &dummy,
+ node, node_instance, cost_vec);
+ /* We eventually expect vectorizable_* functions to guess and set the
+ output vector type from the inputs. */
+ if (!SLP_TREE_VECTYPE (node))
+ SLP_TREE_VECTYPE (node) = STMT_VINFO_VECTYPE (stmt_info);
+ return dummy;
}
/* Try to build NODE from scalars, returning true on success.
@@ -2932,6 +3009,8 @@ vect_slp_analyze_node_operations (vec_info *vinfo, slp_tree node,
"not vectorized: same operand with different "
"def type in stmt.\n");
+ //gcc_assert (SLP_TREE_VECTYPE (node));
+
if (res)
res = vect_slp_analyze_node_operations_1 (vinfo, node, node_instance,
cost_vec);
@@ -3022,6 +3101,8 @@ vect_bb_slp_scalar_cost (vec_info *vinfo, basic_block bb,
FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt_info)
{
+ if (!stmt_info)
+ continue;
gimple *stmt = stmt_info->stmt;
ssa_op_iter op_iter;
def_operand_p def_p;
@@ -3833,7 +3914,10 @@ vect_get_constant_vectors (vec_info *vinfo,
{
stmt_vec_info last_stmt_info
= vect_find_last_scalar_stmt_in_slp (slp_node);
- gsi = gsi_for_stmt (last_stmt_info->stmt);
+ if (is_a <gphi *> (last_stmt_info->stmt))
+ gsi = gsi_after_labels (gimple_bb (last_stmt_info->stmt));
+ else
+ gsi = gsi_for_stmt (last_stmt_info->stmt);
init = vect_init_vector (vinfo, stmt_vinfo, vec_cst,
vector_type, &gsi);
}
@@ -4152,10 +4236,190 @@ vect_transform_slp_perm_load (vec_info *vinfo,
return true;
}
+
+/* Vectorize SLP permutations. */
+
+static bool
+vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi,
+ slp_tree node, stmt_vector_for_cost *cost_vec)
+{
+ /* At analysis time compute the vector type.
+ ??? We currently only support all same vector input and output types
+ while the SLP IL should really do a concat + select and thus accept
+ arbitrary mismatches.
+ ??? Verification of the current limitation is missing here. */
+ if (!gsi)
+ SLP_TREE_VECTYPE (node) = SLP_TREE_VECTYPE (SLP_TREE_CHILDREN (node)[0]);
+ tree vectype = SLP_TREE_VECTYPE (node);
+
+ vec<std::pair<unsigned, unsigned> > &perm = SLP_TREE_LANE_PERMUTATION (node);
+
+ unsigned vf = 1;
+ if (loop_vec_info linfo = dyn_cast <loop_vec_info> (vinfo))
+ vf = LOOP_VINFO_VECT_FACTOR (linfo).to_constant ();
+ unsigned olanes = vf * node->n_lanes ();
+ gcc_assert (olanes % perm.length () == 0);
+ gcc_assert (multiple_p (olanes, TYPE_VECTOR_SUBPARTS (vectype)));
+
+ /* ??? Compute { op, vector-def, lane } permutation sequence, delaying
+ final index compute and thus combining vector-defs in a particular
+ order.
+ ??? As intermediate step to actually code-gen in the SLP tree
+ representation? */
+
+ auto_vec<unsigned> active_lane;
+ auto_vec<unsigned> defi;
+ active_lane.safe_grow_cleared (SLP_TREE_CHILDREN (node).length ());
+ defi.safe_grow_cleared (SLP_TREE_CHILDREN (node).length ());
+
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "vectorizing permutation");
+ for (unsigned i = 0; i < perm.length (); ++i)
+ dump_printf (MSG_NOTE, " op%u[%u]", perm[i].first, perm[i].second);
+ dump_printf (MSG_NOTE, "\n");
+ }
+
+ auto_vec<std::pair<std::pair<unsigned, unsigned>, unsigned> > vperm;
+ vperm.create (olanes);
+ for (unsigned i = 0; i < olanes / perm.length (); ++i)
+ {
+ for (unsigned pi = 0; pi < perm.length (); ++pi)
+ {
+ std::pair<unsigned, unsigned> p = perm[pi];
+ unsigned vnunits = TYPE_VECTOR_SUBPARTS
+ (SLP_TREE_VECTYPE (SLP_TREE_CHILDREN (node)[p.first])).to_constant ();
+ unsigned vi = (active_lane[p.first] + p.second) / vnunits;
+ unsigned vl = (active_lane[p.first] + p.second) % vnunits;
+ vperm.quick_push (std::make_pair (std::make_pair (p.first, vi), vl));
+ }
+ /* Advance to the next group. */
+ for (unsigned j = 0; j < SLP_TREE_CHILDREN (node).length (); ++j)
+ active_lane[j] += SLP_TREE_CHILDREN (node)[j]->n_lanes ();
+ }
+
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "as");
+ for (unsigned i = 0; i < vperm.length (); ++i)
+ {
+ if (i != 0 && multiple_p (i, TYPE_VECTOR_SUBPARTS (vectype)))
+ dump_printf (MSG_NOTE, ",");
+ dump_printf (MSG_NOTE, " vops%u[%u][%u]",
+ vperm[i].first.first, vperm[i].first.second,
+ vperm[i].first.second);
+ }
+ dump_printf (MSG_NOTE, "\n");
+ }
+
+ /* We can only handle two-vector permutes, everything else should
+ be lowered on the SLP level. */
+ std::pair<unsigned, unsigned> first_vec = std::make_pair (-1U, -1U);
+ std::pair<unsigned, unsigned> second_vec = std::make_pair (-1U, -1U);
+ unsigned int const_nunits = TYPE_VECTOR_SUBPARTS (vectype).to_constant ();
+ unsigned int index = 0;
+ unsigned int mask_element;
+ vec_perm_builder mask;
+ mask.new_vector (const_nunits, const_nunits, 1);
+ unsigned int count = mask.encoded_nelts ();
+ mask.quick_grow (count);
+ vec_perm_indices indices;
+ unsigned nperms = 0;
+ for (unsigned i = 0; i < vperm.length (); ++i)
+ {
+ mask_element = vperm[i].second;
+ if (first_vec.first == -1U
+ || first_vec == vperm[i].first)
+ first_vec = vperm[i].first;
+ else if (second_vec.first == -1U
+ || second_vec == vperm[i].first)
+ {
+ second_vec = vperm[i].first;
+ mask_element += const_nunits;
+ }
+ else
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "permutation requires at "
+ "least three vectors");
+ gcc_assert (!gsi);
+ return false;
+ }
+
+ mask[index++] = mask_element;
+
+ if (index == count)
+ {
+ indices.new_vector (mask, second_vec.first == -1U ? 1 : 2,
+ const_nunits);
+ if (!can_vec_perm_const_p (TYPE_MODE (vectype), indices))
+ {
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION,
+ vect_location,
+ "unsupported vect permute { ");
+ for (i = 0; i < count; ++i)
+ {
+ dump_dec (MSG_MISSED_OPTIMIZATION, mask[i]);
+ dump_printf (MSG_MISSED_OPTIMIZATION, " ");
+ }
+ dump_printf (MSG_MISSED_OPTIMIZATION, "}\n");
+ }
+ gcc_assert (!gsi);
+ return false;
+ }
+ }
+
+ if (index == count)
+ {
+ nperms++;
+
+ if (gsi)
+ {
+ tree mask_vec = vect_gen_perm_mask_checked (vectype, indices);
+
+ if (second_vec.first == -1U)
+ second_vec = first_vec;
+
+ /* Generate the permute statement if necessary. */
+ tree first_def = gimple_get_lhs (SLP_TREE_VEC_STMTS
+ (SLP_TREE_CHILDREN (node)[first_vec.first])[first_vec.second]->stmt);
+ tree second_def = gimple_get_lhs (SLP_TREE_VEC_STMTS
+ (SLP_TREE_CHILDREN (node)[second_vec.first])[second_vec.second]->stmt);
+ stmt_vec_info perm_stmt_info;
+ tree perm_dest = make_ssa_name (vectype);
+ gassign *perm_stmt
+ = gimple_build_assign (perm_dest, VEC_PERM_EXPR,
+ first_def, second_def,
+ mask_vec);
+ /* ??? Refactor vect_finish_stmt_generation. */
+ gsi_insert_before (gsi, perm_stmt, GSI_SAME_STMT);
+ perm_stmt_info = vinfo->add_stmt (perm_stmt);
+ /* Store the vector statement in NODE. */
+ SLP_TREE_VEC_STMTS (node).quick_push (perm_stmt_info);
+ }
+
+ index = 0;
+ first_vec = std::make_pair (-1U, -1U);
+ second_vec = std::make_pair (-1U, -1U);
+ }
+ }
+
+ if (!gsi)
+ record_stmt_cost (cost_vec, nperms, vec_perm, vectype, 0, vect_body);
+
+ return true;
+}
+
/* Vectorize SLP instance tree in postorder. */
static void
-vect_schedule_slp_instance (slp_tree node, slp_instance instance)
+vect_schedule_slp_instance (vec_info *vinfo,
+ slp_tree node, slp_instance instance)
{
gimple_stmt_iterator si;
stmt_vec_info stmt_info;
@@ -4173,7 +4437,7 @@ vect_schedule_slp_instance (slp_tree node, slp_instance instance)
return;
FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
- vect_schedule_slp_instance (child, instance);
+ vect_schedule_slp_instance (vinfo, child, instance);
/* Push SLP node def-type to stmts. */
FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
@@ -4202,83 +4466,24 @@ vect_schedule_slp_instance (slp_tree node, slp_instance instance)
/* Vectorized stmts go before the last scalar stmt which is where
all uses are ready. */
stmt_vec_info last_stmt_info = vect_find_last_scalar_stmt_in_slp (node);
- si = gsi_for_stmt (last_stmt_info->stmt);
+ if (is_a <gphi *> (last_stmt_info->stmt))
+ si = gsi_after_labels (gimple_bb (last_stmt_info->stmt));
+ else
+ si = gsi_for_stmt (last_stmt_info->stmt);
- /* Handle two-operation SLP nodes by vectorizing the group with
- both operations and then performing a merge. */
bool done_p = false;
- if (SLP_TREE_TWO_OPERATORS (node))
+
+ /* Handle purely internal nodes. */
+ if (node->classify () == _slp_tree::SLP_CPERM)
{
- gassign *stmt = as_a <gassign *> (stmt_info->stmt);
- enum tree_code code0 = gimple_assign_rhs_code (stmt);
- enum tree_code ocode = ERROR_MARK;
- stmt_vec_info ostmt_info;
- vec_perm_builder mask (group_size, group_size, 1);
- FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, ostmt_info)
- {
- gassign *ostmt = as_a <gassign *> (ostmt_info->stmt);
- if (gimple_assign_rhs_code (ostmt) != code0)
- {
- mask.quick_push (1);
- ocode = gimple_assign_rhs_code (ostmt);
- }
- else
- mask.quick_push (0);
- }
- if (ocode != ERROR_MARK)
- {
- vec<stmt_vec_info> v0;
- vec<stmt_vec_info> v1;
- unsigned j;
- tree tmask = NULL_TREE;
- vect_transform_stmt (stmt_info, &si, node, instance);
- v0 = SLP_TREE_VEC_STMTS (node).copy ();
- SLP_TREE_VEC_STMTS (node).truncate (0);
- gimple_assign_set_rhs_code (stmt, ocode);
- vect_transform_stmt (stmt_info, &si, node, instance);
- gimple_assign_set_rhs_code (stmt, code0);
- v1 = SLP_TREE_VEC_STMTS (node).copy ();
- SLP_TREE_VEC_STMTS (node).truncate (0);
- tree meltype = build_nonstandard_integer_type
- (GET_MODE_BITSIZE (SCALAR_TYPE_MODE (TREE_TYPE (vectype))), 1);
- tree mvectype = get_same_sized_vectype (meltype, vectype);
- unsigned k = 0, l;
- for (j = 0; j < v0.length (); ++j)
- {
- /* Enforced by vect_build_slp_tree, which rejects variable-length
- vectors for SLP_TREE_TWO_OPERATORS. */
- unsigned int const_nunits = nunits.to_constant ();
- tree_vector_builder melts (mvectype, const_nunits, 1);
- for (l = 0; l < const_nunits; ++l)
- {
- if (k >= group_size)
- k = 0;
- tree t = build_int_cst (meltype,
- mask[k++] * const_nunits + l);
- melts.quick_push (t);
- }
- tmask = melts.build ();
-
- /* ??? Not all targets support a VEC_PERM_EXPR with a
- constant mask that would translate to a vec_merge RTX
- (with their vec_perm_const_ok). We can either not
- vectorize in that case or let veclower do its job.
- Unfortunately that isn't too great and at least for
- plus/minus we'd eventually like to match targets
- vector addsub instructions. */
- gimple *vstmt;
- vstmt = gimple_build_assign (make_ssa_name (vectype),
- VEC_PERM_EXPR,
- gimple_assign_lhs (v0[j]->stmt),
- gimple_assign_lhs (v1[j]->stmt),
- tmask);
- SLP_TREE_VEC_STMTS (node).quick_push
- (vect_finish_stmt_generation (stmt_info, vstmt, &si));
- }
- v0.release ();
- v1.release ();
- done_p = true;
- }
+ /* ??? the transform kind is stored to STMT_VINFO_TYPE which might
+ be shared with different SLP nodes (but usually it's the same
+ operation apart from the case the stmt is only there for denoting
+ the actual scalar lane defs ...). So do not call vect_transform_stmt
+ but open-code it here (partly). */
+ bool done = vectorizable_slp_permutation (vinfo, &si, node, NULL);
+ gcc_assert (done);
+ done_p = true;
}
if (!done_p)
vect_transform_stmt (vinfo, stmt_info, &si, node, instance);
@@ -4320,6 +4525,7 @@ vect_remove_slp_scalar_calls (vec_info *vinfo,
FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt_info)
{
+ if (!stmt_info) continue;
gcall *stmt = dyn_cast <gcall *> (stmt_info->stmt);
if (!stmt || gimple_bb (stmt) == NULL)
continue;
@@ -4405,7 +4611,7 @@ vect_schedule_slp (vec_info *vinfo)
{
slp_tree node = SLP_INSTANCE_TREE (instance);
/* Schedule the tree of INSTANCE. */
- vect_schedule_slp_instance (node, instance);
+ vect_schedule_slp_instance (vinfo, node, instance);
if (SLP_INSTANCE_ROOT_STMT (instance))
vectorize_slp_instance_root_stmt (node, instance);
diff --git a/gcc/tree-vect-stmts.c b/gcc/tree-vect-stmts.c
index 1961cdcc5f8..ef90619f6f2 100644
--- a/gcc/tree-vect-stmts.c
+++ b/gcc/tree-vect-stmts.c
@@ -842,14 +842,6 @@ vect_model_simple_cost (vec_info *,
prologue_cost += record_stmt_cost (cost_vec, 1, scalar_to_vec,
stmt_info, 0, vect_prologue);
- /* Adjust for two-operator SLP nodes. */
- if (node && SLP_TREE_TWO_OPERATORS (node))
- {
- ncopies *= 2;
- inside_cost += record_stmt_cost (cost_vec, ncopies, vec_perm,
- stmt_info, 0, vect_body);
- }
-
/* Pass the inside-of-loop statements to the target-specific cost model. */
inside_cost += record_stmt_cost (cost_vec, ncopies, kind,
stmt_info, 0, vect_body);
@@ -10729,7 +10721,7 @@ can_vectorize_live_stmts (loop_vec_info loop_vinfo,
unsigned int i;
FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (slp_node), i, slp_stmt_info)
{
- if (STMT_VINFO_LIVE_P (slp_stmt_info)
+ if (slp_stmt_info && STMT_VINFO_LIVE_P (slp_stmt_info)
&& !vectorizable_live_operation (loop_vinfo,
slp_stmt_info, gsi, slp_node,
slp_node_instance, i,
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 5d1371d4efd..aeae98ad0ec 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -118,6 +118,15 @@ typedef struct _slp_tree *slp_tree;
/* A computation tree of an SLP instance. Each node corresponds to a group of
stmts to be packed in a SIMD stmt. */
struct _slp_tree {
+ _slp_tree();
+ ~_slp_tree();
+
+ enum kind { SLP_OTHER, SLP_CPERM };
+ kind classify ();
+
+ /* Number of (scalar) lanes produced by this node. */
+ unsigned n_lanes ();
+
/* Nodes that contain def-stmts of this node statements operands. */
vec<slp_tree> children;
@@ -129,7 +138,12 @@ struct _slp_tree {
/* Load permutation relative to the stores, NULL if there is no
permutation. */
vec<unsigned> load_permutation;
+ /* Lane permutation of the operands scalar lanes encoded as pairs
+ of { operand number, lane number }. The number of elements
+ denotes the number of output lanes. */
+ vec<std::pair<unsigned, unsigned> > lane_permutation;
+ tree vectype;
/* Vectorized stmt/s. */
vec<stmt_vec_info> vec_stmts;
/* Number of vector stmts that are created to replace the group of scalar
@@ -143,10 +157,10 @@ struct _slp_tree {
/* The maximum number of vector elements for the subtree rooted
at this node. */
poly_uint64 max_nunits;
- /* Whether the scalar computations use two different operators. */
- bool two_operators;
/* The DEF type of this node. */
enum vect_def_type def_type;
+ /* The operation of this node. */
+ enum tree_code code;
};
@@ -184,8 +198,10 @@ public:
#define SLP_TREE_VEC_STMTS(S) (S)->vec_stmts
#define SLP_TREE_NUMBER_OF_VEC_STMTS(S) (S)->vec_stmts_size
#define SLP_TREE_LOAD_PERMUTATION(S) (S)->load_permutation
-#define SLP_TREE_TWO_OPERATORS(S) (S)->two_operators
+#define SLP_TREE_LANE_PERMUTATION(S) (S)->lane_permutation
#define SLP_TREE_DEF_TYPE(S) (S)->def_type
+#define SLP_TREE_CODE(S) (S)->code
+#define SLP_TREE_VECTYPE(S) (S)->vectype
/* Key for map that records association between
scalar conditions and corresponding loop mask, and
More information about the Gcc-cvs
mailing list