/* SLP - Basic Block Vectorization
- Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012
- Free Software Foundation, Inc.
+ Copyright (C) 2007-2015 Free Software Foundation, Inc.
Contributed by Dorit Naishlos <dorit@il.ibm.com>
and Ira Rosen <irar@il.ibm.com>
#include "coretypes.h"
#include "dumpfile.h"
#include "tm.h"
-#include "ggc.h"
+#include "alias.h"
+#include "symtab.h"
#include "tree.h"
+#include "fold-const.h"
+#include "stor-layout.h"
#include "target.h"
+#include "predict.h"
+#include "hard-reg-set.h"
+#include "function.h"
#include "basic-block.h"
#include "gimple-pretty-print.h"
-#include "tree-flow.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimple-ssa.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
#include "tree-pass.h"
#include "cfgloop.h"
+#include "rtl.h"
+#include "flags.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
#include "expr.h"
#include "recog.h" /* FIXME: for insn_data */
+#include "insn-codes.h"
#include "optabs.h"
#include "tree-vectorizer.h"
#include "langhooks.h"
+#include "gimple-walk.h"
/* Extract the location of the basic block in the source code.
Return the basic block location if succeed and NULL if not. */
-LOC
+source_location
find_bb_location (basic_block bb)
{
gimple stmt = NULL;
gimple_stmt_iterator si;
if (!bb)
- return UNKNOWN_LOC;
+ return UNKNOWN_LOCATION;
for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
{
stmt = gsi_stmt (si);
- if (gimple_location (stmt) != UNKNOWN_LOC)
+ if (gimple_location (stmt) != UNKNOWN_LOCATION)
return gimple_location (stmt);
}
- return UNKNOWN_LOC;
+ return UNKNOWN_LOCATION;
}
vect_free_slp_tree (slp_tree node)
{
int i;
- slp_void_p child;
+ slp_tree child;
if (!node)
return;
- FOR_EACH_VEC_ELT (slp_void_p, SLP_TREE_CHILDREN (node), i, child)
- vect_free_slp_tree ((slp_tree) child);
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ vect_free_slp_tree (child);
- VEC_free (slp_void_p, heap, SLP_TREE_CHILDREN (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));
+ SLP_TREE_CHILDREN (node).release ();
+ SLP_TREE_SCALAR_STMTS (node).release ();
+ SLP_TREE_VEC_STMTS (node).release ();
+ SLP_TREE_LOAD_PERMUTATION (node).release ();
free (node);
}
vect_free_slp_instance (slp_instance instance)
{
vect_free_slp_tree (SLP_INSTANCE_TREE (instance));
- VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (instance));
- VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (instance));
- VEC_free (stmt_info_for_cost, heap, SLP_INSTANCE_BODY_COST_VEC (instance));
+ SLP_INSTANCE_LOADS (instance).release ();
free (instance);
}
/* Create an SLP node for SCALAR_STMTS. */
static slp_tree
-vect_create_new_slp_node (VEC (gimple, heap) *scalar_stmts)
+vect_create_new_slp_node (vec<gimple> scalar_stmts)
{
slp_tree node;
- gimple stmt = VEC_index (gimple, scalar_stmts, 0);
+ gimple stmt = scalar_stmts[0];
unsigned int nops;
if (is_gimple_call (stmt))
node = XNEW (struct _slp_tree);
SLP_TREE_SCALAR_STMTS (node) = scalar_stmts;
- SLP_TREE_VEC_STMTS (node) = NULL;
- SLP_TREE_CHILDREN (node) = VEC_alloc (slp_void_p, heap, nops);
+ SLP_TREE_VEC_STMTS (node).create (0);
+ SLP_TREE_CHILDREN (node).create (nops);
+ SLP_TREE_LOAD_PERMUTATION (node) = vNULL;
+ SLP_TREE_TWO_OPERATORS (node) = false;
return node;
}
/* Allocate operands info for NOPS operands, and GROUP_SIZE def-stmts for each
operand. */
-static VEC (slp_oprnd_info, heap) *
+static vec<slp_oprnd_info>
vect_create_oprnd_info (int nops, int group_size)
{
int i;
slp_oprnd_info oprnd_info;
- VEC (slp_oprnd_info, heap) *oprnds_info;
+ vec<slp_oprnd_info> oprnds_info;
- oprnds_info = VEC_alloc (slp_oprnd_info, heap, nops);
+ oprnds_info.create (nops);
for (i = 0; i < nops; i++)
{
oprnd_info = XNEW (struct _slp_oprnd_info);
- oprnd_info->def_stmts = VEC_alloc (gimple, heap, group_size);
+ oprnd_info->def_stmts.create (group_size);
oprnd_info->first_dt = vect_uninitialized_def;
- oprnd_info->first_def_type = NULL_TREE;
- oprnd_info->first_const_oprnd = NULL_TREE;
+ oprnd_info->first_op_type = NULL_TREE;
oprnd_info->first_pattern = false;
- VEC_quick_push (slp_oprnd_info, oprnds_info, oprnd_info);
+ oprnd_info->second_pattern = false;
+ oprnds_info.quick_push (oprnd_info);
}
return oprnds_info;
/* Free operands info. */
static void
-vect_free_oprnd_info (VEC (slp_oprnd_info, heap) **oprnds_info)
+vect_free_oprnd_info (vec<slp_oprnd_info> &oprnds_info)
{
int i;
slp_oprnd_info oprnd_info;
- FOR_EACH_VEC_ELT (slp_oprnd_info, *oprnds_info, i, oprnd_info)
+ FOR_EACH_VEC_ELT (oprnds_info, i, oprnd_info)
{
- VEC_free (gimple, heap, oprnd_info->def_stmts);
+ oprnd_info->def_stmts.release ();
XDELETE (oprnd_info);
}
- VEC_free (slp_oprnd_info, heap, *oprnds_info);
+ oprnds_info.release ();
+}
+
+
+/* Find the place of the data-ref in STMT in the interleaving chain that starts
+ from FIRST_STMT. Return -1 if the data-ref is not a part of the chain. */
+
+static int
+vect_get_place_in_interleaving_chain (gimple stmt, gimple first_stmt)
+{
+ gimple next_stmt = first_stmt;
+ int result = 0;
+
+ if (first_stmt != GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
+ return -1;
+
+ do
+ {
+ if (next_stmt == stmt)
+ return result;
+ next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
+ if (next_stmt)
+ result += GROUP_GAP (vinfo_for_stmt (next_stmt));
+ }
+ while (next_stmt);
+
+ return -1;
}
/* Get the defs for the rhs of STMT (collect them in OPRNDS_INFO), check that
they are of a valid type and that they match the defs of the first stmt of
- the SLP group (stored in OPRNDS_INFO). */
+ the SLP group (stored in OPRNDS_INFO). If there was a fatal error
+ return -1, if the error could be corrected by swapping operands of the
+ operation return 1, if everything is ok return 0. */
-static bool
+static int
vect_get_and_check_slp_defs (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
- slp_tree slp_node, gimple stmt,
- int ncopies_for_cost, bool first,
- VEC (slp_oprnd_info, heap) **oprnds_info,
- stmt_vector_for_cost *prologue_cost_vec,
- stmt_vector_for_cost *body_cost_vec)
+ gimple stmt, unsigned stmt_num,
+ vec<slp_oprnd_info> *oprnds_info)
{
tree oprnd;
unsigned int i, number_of_oprnds;
- tree def, def_op0 = NULL_TREE;
+ tree def;
gimple def_stmt;
enum vect_def_type dt = vect_uninitialized_def;
- enum vect_def_type dt_op0 = vect_uninitialized_def;
- stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
- tree lhs = gimple_get_lhs (stmt);
struct loop *loop = NULL;
- enum tree_code rhs_code;
- bool different_types = false;
bool pattern = false;
- slp_oprnd_info oprnd_info, oprnd0_info, oprnd1_info;
- int op_idx = 1;
- tree compare_rhs = NULL_TREE;
+ slp_oprnd_info oprnd_info;
+ int first_op_idx = 1;
+ bool commutative = false;
+ bool first_op_cond = false;
+ bool first = stmt_num == 0;
+ bool second = stmt_num == 1;
if (loop_vinfo)
loop = LOOP_VINFO_LOOP (loop_vinfo);
if (is_gimple_call (stmt))
{
number_of_oprnds = gimple_call_num_args (stmt);
- op_idx = 3;
+ first_op_idx = 3;
}
else if (is_gimple_assign (stmt))
{
+ enum tree_code code = gimple_assign_rhs_code (stmt);
number_of_oprnds = gimple_num_ops (stmt) - 1;
if (gimple_assign_rhs_code (stmt) == COND_EXPR)
- number_of_oprnds++;
+ {
+ first_op_cond = true;
+ commutative = true;
+ number_of_oprnds++;
+ }
+ else
+ commutative = commutative_tree_code (code);
}
else
- return false;
+ return -1;
+ bool swapped = false;
for (i = 0; i < number_of_oprnds; i++)
{
- if (compare_rhs)
+again:
+ if (first_op_cond)
{
- oprnd = compare_rhs;
- compare_rhs = NULL_TREE;
+ if (i == 0 || i == 1)
+ oprnd = TREE_OPERAND (gimple_op (stmt, first_op_idx),
+ swapped ? !i : i);
+ else
+ oprnd = gimple_op (stmt, first_op_idx + i - 1);
}
else
- oprnd = gimple_op (stmt, op_idx++);
+ oprnd = gimple_op (stmt, first_op_idx + (swapped ? !i : i));
- oprnd_info = VEC_index (slp_oprnd_info, *oprnds_info, i);
-
- if (COMPARISON_CLASS_P (oprnd))
- {
- compare_rhs = TREE_OPERAND (oprnd, 1);
- oprnd = TREE_OPERAND (oprnd, 0);
- }
+ oprnd_info = (*oprnds_info)[i];
if (!vect_is_simple_use (oprnd, NULL, loop_vinfo, bb_vinfo, &def_stmt,
- &def, &dt)
- || (!def_stmt && dt != vect_constant_def))
+ &def, &dt))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "Build SLP failed: can't find def for ");
+ "Build SLP failed: can't analyze def for ");
dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, oprnd);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
- return false;
+ return -1;
}
/* Check if DEF_STMT is a part of a pattern in LOOP and get the def stmt
&& !STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt)))
{
pattern = true;
- if (!first && !oprnd_info->first_pattern)
+ if (!first && !oprnd_info->first_pattern
+ /* Allow different pattern state for the defs of the
+ first stmt in reduction chains. */
+ && (oprnd_info->first_dt != vect_reduction_def
+ || (!second && !oprnd_info->second_pattern)))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (i == 0
+ && !swapped
+ && commutative)
+ {
+ swapped = true;
+ goto again;
+ }
+
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: some of the stmts"
" are in a pattern, and others are not ");
dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, oprnd);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
- return false;
+ return 1;
}
def_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
if (dt == vect_unknown_def_type)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "Unsupported pattern.");
- return false;
+ "Unsupported pattern.\n");
+ return -1;
}
switch (gimple_code (def_stmt))
break;
default:
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "unsupported defining stmt: ");
- return false;
+ "unsupported defining stmt:\n");
+ return -1;
}
}
+ if (second)
+ oprnd_info->second_pattern = pattern;
+
if (first)
{
oprnd_info->first_dt = dt;
oprnd_info->first_pattern = pattern;
- if (def)
- {
- oprnd_info->first_def_type = TREE_TYPE (def);
- oprnd_info->first_const_oprnd = NULL_TREE;
- }
- else
- {
- oprnd_info->first_def_type = NULL_TREE;
- oprnd_info->first_const_oprnd = oprnd;
- }
-
- if (i == 0)
- {
- def_op0 = def;
- dt_op0 = dt;
- /* Analyze costs (for the first stmt of the group only). */
- if (REFERENCE_CLASS_P (lhs))
- /* Store. */
- vect_model_store_cost (stmt_info, ncopies_for_cost, false,
- dt, slp_node, prologue_cost_vec,
- body_cost_vec);
- else
- {
- enum vect_def_type dts[2];
- dts[0] = dt;
- dts[1] = vect_uninitialized_def;
- /* Not memory operation (we don't call this function for
- loads). */
- vect_model_simple_cost (stmt_info, ncopies_for_cost, dts,
- prologue_cost_vec, body_cost_vec);
- }
- }
+ oprnd_info->first_op_type = TREE_TYPE (oprnd);
}
else
{
vect_internal_def. */
if (((oprnd_info->first_dt != dt
&& !(oprnd_info->first_dt == vect_reduction_def
- && dt == vect_internal_def))
- || (oprnd_info->first_def_type != NULL_TREE
- && def
- && !types_compatible_p (oprnd_info->first_def_type,
- TREE_TYPE (def))))
- || (!def
- && !types_compatible_p (TREE_TYPE (oprnd_info->first_const_oprnd),
- TREE_TYPE (oprnd)))
- || different_types)
+ && dt == vect_internal_def)
+ && !((oprnd_info->first_dt == vect_external_def
+ || oprnd_info->first_dt == vect_constant_def)
+ && (dt == vect_external_def
+ || dt == vect_constant_def)))
+ || !types_compatible_p (oprnd_info->first_op_type,
+ TREE_TYPE (oprnd))))
{
- if (number_of_oprnds != 2)
+ /* Try swapping operands if we got a mismatch. */
+ if (i == 0
+ && !swapped
+ && commutative)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "Build SLP failed: different types ");
-
- return false;
- }
+ swapped = true;
+ goto again;
+ }
- /* Try to swap operands in case of binary operation. */
- if (i == 0)
- different_types = true;
- else
- {
- oprnd0_info = VEC_index (slp_oprnd_info, *oprnds_info, 0);
- if (is_gimple_assign (stmt)
- && (rhs_code = gimple_assign_rhs_code (stmt))
- && TREE_CODE_CLASS (rhs_code) == tcc_binary
- && commutative_tree_code (rhs_code)
- && oprnd0_info->first_dt == dt
- && oprnd_info->first_dt == dt_op0
- && def_op0 && def
- && !(oprnd0_info->first_def_type
- && !types_compatible_p (oprnd0_info->first_def_type,
- TREE_TYPE (def)))
- && !(oprnd_info->first_def_type
- && !types_compatible_p (oprnd_info->first_def_type,
- TREE_TYPE (def_op0))))
- {
- if (dump_kind_p (MSG_NOTE))
- {
- dump_printf_loc (MSG_NOTE, vect_location,
- "Swapping operands of ");
- dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
- }
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "Build SLP failed: different types\n");
- swap_tree_operands (stmt, gimple_assign_rhs1_ptr (stmt),
- gimple_assign_rhs2_ptr (stmt));
- }
- else
- {
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "Build SLP failed: different types ");
-
- return false;
- }
- }
+ return 1;
}
}
break;
case vect_internal_def:
- if (different_types)
- {
- oprnd0_info = VEC_index (slp_oprnd_info, *oprnds_info, 0);
- oprnd1_info = VEC_index (slp_oprnd_info, *oprnds_info, 0);
- if (i == 0)
- VEC_quick_push (gimple, oprnd1_info->def_stmts, def_stmt);
- else
- VEC_quick_push (gimple, oprnd0_info->def_stmts, def_stmt);
- }
- else
- VEC_quick_push (gimple, oprnd_info->def_stmts, def_stmt);
-
+ oprnd_info->def_stmts.quick_push (def_stmt);
break;
default:
/* FORNOW: Not supported. */
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: illegal type of def ");
dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, def);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
- return false;
+ return -1;
}
}
- return true;
+ /* Swap operands. */
+ if (swapped)
+ {
+ if (first_op_cond)
+ {
+ tree cond = gimple_assign_rhs1 (stmt);
+ swap_ssa_operands (stmt, &TREE_OPERAND (cond, 0),
+ &TREE_OPERAND (cond, 1));
+ TREE_SET_CODE (cond, swap_tree_comparison (TREE_CODE (cond)));
+ }
+ else
+ swap_ssa_operands (stmt, gimple_assign_rhs1_ptr (stmt),
+ gimple_assign_rhs2_ptr (stmt));
+ }
+
+ return 0;
}
-/* 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
- TRUE. */
+/* 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
+ which stmts are not isomorphic to the first one. If MATCHES[0]
+ is false then this indicates the comparison could not be
+ carried out or the stmts will never be vectorized by SLP. */
static bool
-vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
- slp_tree *node, unsigned int group_size, int *outside_cost,
- int ncopies_for_cost, unsigned int *max_nunits,
- VEC (int, heap) **load_permutation,
- VEC (slp_tree, heap) **loads,
- unsigned int vectorization_factor, bool *loads_permuted,
- stmt_vector_for_cost *prologue_cost_vec,
- stmt_vector_for_cost *body_cost_vec)
+vect_build_slp_tree_1 (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
+ vec<gimple> stmts, unsigned int group_size,
+ unsigned nops, unsigned int *max_nunits,
+ unsigned int vectorization_factor, bool *matches,
+ bool *two_operators)
{
unsigned int i;
- VEC (gimple, heap) *stmts = SLP_TREE_SCALAR_STMTS (*node);
- gimple stmt = VEC_index (gimple, stmts, 0);
- enum tree_code first_stmt_code = ERROR_MARK, rhs_code = ERROR_MARK;
+ gimple first_stmt = stmts[0], stmt = stmts[0];
+ enum tree_code first_stmt_code = ERROR_MARK;
+ enum tree_code alt_stmt_code = ERROR_MARK;
+ enum tree_code rhs_code = ERROR_MARK;
enum tree_code first_cond_code = ERROR_MARK;
tree lhs;
- bool stop_recursion = false, need_same_oprnds = false;
- tree vectype, scalar_type, first_op1 = NULL_TREE;
- unsigned int ncopies;
+ bool need_same_oprnds = false;
+ tree vectype = NULL_TREE, scalar_type, first_op1 = NULL_TREE;
optab optab;
int icode;
- enum machine_mode optab_op2_mode;
- enum machine_mode vec_mode;
- struct data_reference *first_dr;
+ machine_mode optab_op2_mode;
+ machine_mode vec_mode;
HOST_WIDE_INT dummy;
- bool permutation = false;
- unsigned int load_place;
- gimple first_load = NULL, prev_first_load = NULL, old_first_load = NULL;
- VEC (slp_oprnd_info, heap) *oprnds_info;
- unsigned int nops;
- slp_oprnd_info oprnd_info;
+ gimple first_load = NULL, prev_first_load = NULL;
tree cond;
- if (is_gimple_call (stmt))
- nops = gimple_call_num_args (stmt);
- else if (is_gimple_assign (stmt))
- {
- nops = gimple_num_ops (stmt) - 1;
- if (gimple_assign_rhs_code (stmt) == COND_EXPR)
- nops++;
- }
- else
- return false;
-
- oprnds_info = vect_create_oprnd_info (nops, group_size);
-
/* For every stmt in NODE find its def stmt/s. */
- FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
+ FOR_EACH_VEC_ELT (stmts, i, stmt)
{
- if (dump_kind_p (MSG_NOTE))
+ matches[i] = false;
+
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_NOTE, vect_location, "Build SLP for ");
dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_NOTE, "\n");
}
/* Fail to vectorize statements marked as unvectorizable. */
if (!STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt)))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: unvectorizable statement ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
- vect_free_oprnd_info (&oprnds_info);
+ /* Fatal mismatch. */
+ matches[0] = false;
return false;
}
lhs = gimple_get_lhs (stmt);
if (lhs == NULL_TREE)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: not GIMPLE_ASSIGN nor "
"GIMPLE_CALL ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
- vect_free_oprnd_info (&oprnds_info);
+ /* Fatal mismatch. */
+ matches[0] = false;
return false;
}
&& (cond = gimple_assign_rhs1 (stmt))
&& !COMPARISON_CLASS_P (cond))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: condition is not "
"comparison ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
- vect_free_oprnd_info (&oprnds_info);
+ /* Fatal mismatch. */
+ matches[0] = false;
return false;
}
vectype = get_vectype_for_scalar_type (scalar_type);
if (!vectype)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: unsupported data-type ");
dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
scalar_type);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
- vect_free_oprnd_info (&oprnds_info);
+ /* Fatal mismatch. */
+ matches[0] = false;
return false;
}
+ /* If populating the vector type requires unrolling then fail
+ before adjusting *max_nunits for basic-block vectorization. */
+ if (bb_vinfo
+ && TYPE_VECTOR_SUBPARTS (vectype) > group_size)
+ {
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "Build SLP failed: unrolling required "
+ "in basic block SLP\n");
+ /* Fatal mismatch. */
+ matches[0] = false;
+ return false;
+ }
+
/* In case of multiple types we need to detect the smallest type. */
if (*max_nunits < TYPE_VECTOR_SUBPARTS (vectype))
{
vectorization_factor = *max_nunits;
}
- ncopies = vectorization_factor / TYPE_VECTOR_SUBPARTS (vectype);
-
- if (is_gimple_call (stmt))
+ if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
{
rhs_code = CALL_EXPR;
- if (gimple_call_internal_p (stmt)
- || gimple_call_tail_p (stmt)
- || gimple_call_noreturn_p (stmt)
- || !gimple_call_nothrow_p (stmt)
- || gimple_call_chain (stmt))
+ if (gimple_call_internal_p (call_stmt)
+ || gimple_call_tail_p (call_stmt)
+ || gimple_call_noreturn_p (call_stmt)
+ || !gimple_call_nothrow_p (call_stmt)
+ || gimple_call_chain (call_stmt))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: unsupported call type ");
- dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
+ call_stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
- vect_free_oprnd_info (&oprnds_info);
+ /* Fatal mismatch. */
+ matches[0] = false;
return false;
}
}
if (!optab)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "Build SLP failed: no optab.");
- vect_free_oprnd_info (&oprnds_info);
+ "Build SLP failed: no optab.\n");
+ /* Fatal mismatch. */
+ matches[0] = false;
return false;
}
icode = (int) optab_handler (optab, vec_mode);
if (icode == CODE_FOR_nothing)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: "
- "op not supported by target.");
- vect_free_oprnd_info (&oprnds_info);
+ "op not supported by target.\n");
+ /* Fatal mismatch. */
+ matches[0] = false;
return false;
}
optab_op2_mode = insn_data[icode].operand[2].mode;
}
else
{
+ if (first_stmt_code != rhs_code
+ && alt_stmt_code == ERROR_MARK)
+ alt_stmt_code = rhs_code;
if (first_stmt_code != rhs_code
&& (first_stmt_code != IMAGPART_EXPR
|| rhs_code != REALPART_EXPR)
&& (first_stmt_code != REALPART_EXPR
|| rhs_code != IMAGPART_EXPR)
+ /* Handle mismatches in plus/minus by computing both
+ and merging the results. */
+ && !((first_stmt_code == PLUS_EXPR
+ || first_stmt_code == MINUS_EXPR)
+ && (alt_stmt_code == PLUS_EXPR
+ || alt_stmt_code == MINUS_EXPR)
+ && rhs_code == alt_stmt_code)
&& !(STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt))
&& (first_stmt_code == ARRAY_REF
+ || first_stmt_code == BIT_FIELD_REF
|| first_stmt_code == INDIRECT_REF
|| first_stmt_code == COMPONENT_REF
|| first_stmt_code == MEM_REF)))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: different operation "
"in stmt ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "original stmt ");
+ dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
+ first_stmt, 0);
}
-
- vect_free_oprnd_info (&oprnds_info);
- return false;
+ /* Mismatch. */
+ continue;
}
if (need_same_oprnds
&& !operand_equal_p (first_op1, gimple_assign_rhs2 (stmt), 0))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: different shift "
"arguments in ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
- vect_free_oprnd_info (&oprnds_info);
- return false;
+ /* Mismatch. */
+ continue;
}
if (rhs_code == CALL_EXPR)
{
- gimple first_stmt = VEC_index (gimple, stmts, 0);
+ gimple first_stmt = stmts[0];
if (gimple_call_num_args (stmt) != nops
|| !operand_equal_p (gimple_call_fn (first_stmt),
gimple_call_fn (stmt), 0)
|| gimple_call_fntype (first_stmt)
!= gimple_call_fntype (stmt))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: different calls in ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
- vect_free_oprnd_info (&oprnds_info);
- return false;
+ /* Mismatch. */
+ continue;
}
}
}
if (REFERENCE_CLASS_P (lhs))
{
/* Store. */
- if (!vect_get_and_check_slp_defs (loop_vinfo, bb_vinfo, *node,
- stmt, ncopies_for_cost,
- (i == 0), &oprnds_info,
- prologue_cost_vec,
- body_cost_vec))
- {
- vect_free_oprnd_info (&oprnds_info);
- return false;
- }
+ ;
}
else
{
/* Load. */
- /* FORNOW: Check that there is no gap between the loads. */
- if ((GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) == stmt
- && GROUP_GAP (vinfo_for_stmt (stmt)) != 0)
- || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) != stmt
- && GROUP_GAP (vinfo_for_stmt (stmt)) != 1))
- {
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- {
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "Build SLP failed: grouped "
- "loads have gaps ");
- dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
- stmt, 0);
- }
-
- vect_free_oprnd_info (&oprnds_info);
- return false;
- }
-
/* Check that the size of interleaved loads group is not
greater than the SLP group size. */
+ unsigned ncopies
+ = vectorization_factor / TYPE_VECTOR_SUBPARTS (vectype);
if (loop_vinfo
- && GROUP_SIZE (vinfo_for_stmt (stmt)) > ncopies * group_size)
+ && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) == stmt
+ && ((GROUP_SIZE (vinfo_for_stmt (stmt))
+ - GROUP_GAP (vinfo_for_stmt (stmt)))
+ > ncopies * group_size))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: the number "
"the SLP group size ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
- vect_free_oprnd_info (&oprnds_info);
+ /* Fatal mismatch. */
+ matches[0] = false;
return false;
}
- old_first_load = first_load;
first_load = GROUP_FIRST_ELEMENT (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)
+ chains in the same node. */
+ if (prev_first_load != first_load)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION,
vect_location,
"interleaving chains in one node ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
- vect_free_oprnd_info (&oprnds_info);
- return false;
+ /* Mismatch. */
+ continue;
}
}
else
prev_first_load = first_load;
-
- /* In some cases a group of loads is just the same load
- repeated N times. Only analyze its cost once. */
- if (first_load == stmt && old_first_load != first_load)
- {
- first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
- if (vect_supportable_dr_alignment (first_dr, false)
- == dr_unaligned_unsupported)
- {
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- {
- dump_printf_loc (MSG_MISSED_OPTIMIZATION,
- vect_location,
- "Build SLP failed: unsupported "
- "unaligned load ");
- dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
- stmt, 0);
- }
-
- vect_free_oprnd_info (&oprnds_info);
- return false;
- }
-
- /* Analyze costs (for the first stmt in the group). */
- vect_model_load_cost (vinfo_for_stmt (stmt),
- ncopies_for_cost, false, *node,
- prologue_cost_vec, body_cost_vec);
- }
-
- /* 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. */
- load_place = vect_get_place_in_interleaving_chain (stmt,
- 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;
}
} /* Grouped access. */
else
if (TREE_CODE_CLASS (rhs_code) == tcc_reference)
{
/* Not grouped load. */
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: not grouped load ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
/* FORNOW: Not grouped loads are not supported. */
- vect_free_oprnd_info (&oprnds_info);
+ /* Fatal mismatch. */
+ matches[0] = false;
return false;
}
/* Not memory operation. */
if (TREE_CODE_CLASS (rhs_code) != tcc_binary
&& TREE_CODE_CLASS (rhs_code) != tcc_unary
- && rhs_code != COND_EXPR
+ && TREE_CODE_CLASS (rhs_code) != tcc_expression
&& rhs_code != CALL_EXPR)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: operation");
dump_printf (MSG_MISSED_OPTIMIZATION, " unsupported ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
- vect_free_oprnd_info (&oprnds_info);
+ /* Fatal mismatch. */
+ matches[0] = false;
return false;
}
first_cond_code = TREE_CODE (cond_expr);
else if (first_cond_code != TREE_CODE (cond_expr))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: different"
" operation");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
- vect_free_oprnd_info (&oprnds_info);
- return false;
+ /* Mismatch. */
+ continue;
}
}
+ }
- /* Find the def-stmts. */
- if (!vect_get_and_check_slp_defs (loop_vinfo, bb_vinfo, *node, stmt,
- ncopies_for_cost, (i == 0),
- &oprnds_info, prologue_cost_vec,
- body_cost_vec))
- {
- vect_free_oprnd_info (&oprnds_info);
- return false;
- }
+ matches[i] = true;
+ }
+
+ for (i = 0; i < group_size; ++i)
+ if (!matches[i])
+ return false;
+
+ /* If we allowed a two-operation SLP node verify the target can cope
+ with the permute we are going to use. */
+ if (alt_stmt_code != ERROR_MARK
+ && TREE_CODE_CLASS (alt_stmt_code) != tcc_reference)
+ {
+ unsigned char *sel
+ = XALLOCAVEC (unsigned char, TYPE_VECTOR_SUBPARTS (vectype));
+ for (i = 0; i < TYPE_VECTOR_SUBPARTS (vectype); ++i)
+ {
+ sel[i] = i;
+ if (gimple_assign_rhs_code (stmts[i % group_size]) == alt_stmt_code)
+ sel[i] += TYPE_VECTOR_SUBPARTS (vectype);
}
+ if (!can_vec_perm_p (TYPE_MODE (vectype), false, sel))
+ {
+ for (i = 0; i < group_size; ++i)
+ if (gimple_assign_rhs_code (stmts[i]) == 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 ");
+ dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
+ stmts[i], 0);
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "original stmt ");
+ dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
+ first_stmt, 0);
+ }
+ }
+ return false;
+ }
+ *two_operators = true;
}
- /* Grouped loads were reached - stop the recursion. */
- if (stop_recursion)
+ return true;
+}
+
+/* Recursively build an SLP tree starting from NODE.
+ Fail (and return a value not equal to zero) if def-stmts are not
+ isomorphic, require data permutation or are of unsupported types of
+ operation. Otherwise, return 0.
+ The value returned is the depth in the SLP tree where a mismatch
+ was found. */
+
+static bool
+vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
+ slp_tree *node, unsigned int group_size,
+ unsigned int *max_nunits,
+ vec<slp_tree> *loads,
+ unsigned int vectorization_factor,
+ bool *matches, unsigned *npermutes, unsigned *tree_size,
+ unsigned max_tree_size)
+{
+ unsigned nops, i, this_tree_size = 0;
+ gimple stmt;
+
+ matches[0] = false;
+
+ stmt = SLP_TREE_SCALAR_STMTS (*node)[0];
+ if (is_gimple_call (stmt))
+ nops = gimple_call_num_args (stmt);
+ else if (is_gimple_assign (stmt))
{
- VEC_safe_push (slp_tree, heap, *loads, *node);
- if (permutation)
- {
- gimple first_stmt = VEC_index (gimple, stmts, 0);
- *loads_permuted = true;
- (void) record_stmt_cost (body_cost_vec, group_size, vec_perm,
- vinfo_for_stmt (first_stmt), 0, vect_body);
- }
- else
- {
- /* We don't check here complex numbers chains, so we set
- LOADS_PERMUTED for further check in
- vect_supported_load_permutation_p. */
- if (rhs_code == REALPART_EXPR || rhs_code == IMAGPART_EXPR)
- *loads_permuted = true;
- }
+ nops = gimple_num_ops (stmt) - 1;
+ if (gimple_assign_rhs_code (stmt) == COND_EXPR)
+ nops++;
+ }
+ else
+ return false;
+
+ bool two_operators = false;
+ if (!vect_build_slp_tree_1 (loop_vinfo, bb_vinfo,
+ SLP_TREE_SCALAR_STMTS (*node), group_size, nops,
+ max_nunits, vectorization_factor, matches,
+ &two_operators))
+ return false;
+ SLP_TREE_TWO_OPERATORS (*node) = two_operators;
- vect_free_oprnd_info (&oprnds_info);
+ /* If the SLP node is a load, terminate the recursion. */
+ if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt))
+ && DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt))))
+ {
+ loads->safe_push (*node);
return true;
}
+ /* Get at the operands, verifying they are compatible. */
+ vec<slp_oprnd_info> oprnds_info = vect_create_oprnd_info (nops, group_size);
+ slp_oprnd_info oprnd_info;
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (*node), i, stmt)
+ {
+ switch (vect_get_and_check_slp_defs (loop_vinfo, bb_vinfo,
+ stmt, i, &oprnds_info))
+ {
+ case 0:
+ break;
+ case -1:
+ matches[0] = false;
+ vect_free_oprnd_info (oprnds_info);
+ return false;
+ case 1:
+ matches[i] = false;
+ break;
+ }
+ }
+ for (i = 0; i < group_size; ++i)
+ if (!matches[i])
+ {
+ vect_free_oprnd_info (oprnds_info);
+ return false;
+ }
+
+ stmt = SLP_TREE_SCALAR_STMTS (*node)[0];
+
/* Create SLP_TREE nodes for the definition node/s. */
- FOR_EACH_VEC_ELT (slp_oprnd_info, oprnds_info, i, oprnd_info)
+ FOR_EACH_VEC_ELT (oprnds_info, i, oprnd_info)
{
slp_tree child;
+ unsigned old_nloads = loads->length ();
+ unsigned old_max_nunits = *max_nunits;
if (oprnd_info->first_dt != vect_internal_def)
continue;
+ if (++this_tree_size > max_tree_size)
+ {
+ vect_free_oprnd_info (oprnds_info);
+ return false;
+ }
+
child = vect_create_new_slp_node (oprnd_info->def_stmts);
- if (!child
- || !vect_build_slp_tree (loop_vinfo, bb_vinfo, &child, group_size,
- outside_cost, ncopies_for_cost,
- max_nunits, load_permutation, loads,
- vectorization_factor, loads_permuted,
- prologue_cost_vec, body_cost_vec))
- {
- if (child)
- oprnd_info->def_stmts = NULL;
+ if (!child)
+ {
+ vect_free_oprnd_info (oprnds_info);
+ return false;
+ }
+
+ if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &child,
+ group_size, max_nunits, loads,
+ vectorization_factor, matches,
+ npermutes, &this_tree_size, max_tree_size))
+ {
+ /* If we have all children of child built up from scalars then just
+ throw that away and build it up this node from scalars. */
+ if (!SLP_TREE_CHILDREN (child).is_empty ())
+ {
+ unsigned int j;
+ slp_tree grandchild;
+
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child), j, grandchild)
+ if (grandchild != NULL)
+ break;
+ if (!grandchild)
+ {
+ /* Roll back. */
+ *max_nunits = old_max_nunits;
+ loads->truncate (old_nloads);
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child), j, grandchild)
+ vect_free_slp_tree (grandchild);
+ SLP_TREE_CHILDREN (child).truncate (0);
+
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "Building parent vector operands from "
+ "scalars instead\n");
+ oprnd_info->def_stmts = vNULL;
+ vect_free_slp_tree (child);
+ SLP_TREE_CHILDREN (*node).quick_push (NULL);
+ continue;
+ }
+ }
+
+ oprnd_info->def_stmts = vNULL;
+ SLP_TREE_CHILDREN (*node).quick_push (child);
+ continue;
+ }
+
+ /* If the SLP build failed fatally and we analyze a basic-block
+ simply treat nodes we fail to build as externally defined
+ (and thus build vectors from the scalar defs).
+ The cost model will reject outright expensive cases.
+ ??? This doesn't treat cases where permutation ultimatively
+ fails (or we don't try permutation below). Ideally we'd
+ even compute a permutation that will end up with the maximum
+ SLP tree size... */
+ if (bb_vinfo
+ && !matches[0]
+ /* ??? Rejecting patterns this way doesn't work. We'd have to
+ do extra work to cancel the pattern so the uses see the
+ scalar version. */
+ && !is_pattern_stmt_p (vinfo_for_stmt (stmt)))
+ {
+ unsigned int j;
+ slp_tree grandchild;
+
+ /* Roll back. */
+ *max_nunits = old_max_nunits;
+ loads->truncate (old_nloads);
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child), j, grandchild)
+ vect_free_slp_tree (grandchild);
+ SLP_TREE_CHILDREN (child).truncate (0);
+
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "Building vector operands from scalars\n");
+ oprnd_info->def_stmts = vNULL;
vect_free_slp_tree (child);
- vect_free_oprnd_info (&oprnds_info);
- return false;
+ SLP_TREE_CHILDREN (*node).quick_push (NULL);
+ continue;
}
- oprnd_info->def_stmts = NULL;
- VEC_quick_push (slp_void_p, SLP_TREE_CHILDREN (*node), child);
+ /* If the SLP build for operand zero failed and operand zero
+ and one can be commutated try that for the scalar stmts
+ that failed the match. */
+ if (i == 0
+ /* A first scalar stmt mismatch signals a fatal mismatch. */
+ && matches[0]
+ /* ??? For COND_EXPRs we can swap the comparison operands
+ as well as the arms under some constraints. */
+ && nops == 2
+ && oprnds_info[1]->first_dt == vect_internal_def
+ && is_gimple_assign (stmt)
+ && commutative_tree_code (gimple_assign_rhs_code (stmt))
+ && !SLP_TREE_TWO_OPERATORS (*node)
+ /* Do so only if the number of not successful permutes was nor more
+ than a cut-ff as re-trying the recursive match on
+ possibly each level of the tree would expose exponential
+ behavior. */
+ && *npermutes < 4)
+ {
+ unsigned int j;
+ slp_tree grandchild;
+
+ /* Roll back. */
+ *max_nunits = old_max_nunits;
+ loads->truncate (old_nloads);
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child), j, grandchild)
+ vect_free_slp_tree (grandchild);
+ SLP_TREE_CHILDREN (child).truncate (0);
+
+ /* Swap mismatched definition stmts. */
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "Re-trying with swapped operands of stmts ");
+ for (j = 0; j < group_size; ++j)
+ if (!matches[j])
+ {
+ std::swap (oprnds_info[0]->def_stmts[j],
+ oprnds_info[1]->def_stmts[j]);
+ dump_printf (MSG_NOTE, "%d ", j);
+ }
+ dump_printf (MSG_NOTE, "\n");
+ /* And try again with scratch 'matches' ... */
+ bool *tem = XALLOCAVEC (bool, group_size);
+ if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &child,
+ group_size, max_nunits, loads,
+ vectorization_factor,
+ tem, npermutes, &this_tree_size,
+ max_tree_size))
+ {
+ /* ... so if successful we can apply the operand swapping
+ to the GIMPLE IL. This is necessary because for example
+ vect_get_slp_defs uses operand indexes and thus expects
+ canonical operand order. */
+ for (j = 0; j < group_size; ++j)
+ if (!matches[j])
+ {
+ gimple stmt = SLP_TREE_SCALAR_STMTS (*node)[j];
+ swap_ssa_operands (stmt, gimple_assign_rhs1_ptr (stmt),
+ gimple_assign_rhs2_ptr (stmt));
+ }
+ oprnd_info->def_stmts = vNULL;
+ SLP_TREE_CHILDREN (*node).quick_push (child);
+ continue;
+ }
+
+ ++*npermutes;
+ }
+
+ oprnd_info->def_stmts = vNULL;
+ vect_free_slp_tree (child);
+ vect_free_oprnd_info (oprnds_info);
+ return false;
}
- vect_free_oprnd_info (&oprnds_info);
+ if (tree_size)
+ *tree_size += this_tree_size;
+
+ vect_free_oprnd_info (oprnds_info);
return true;
}
{
int i;
gimple stmt;
- slp_void_p child;
+ slp_tree child;
if (!node)
return;
dump_printf (dump_kind, "node ");
- FOR_EACH_VEC_ELT (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt)
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
{
dump_printf (dump_kind, "\n\tstmt %d ", i);
dump_gimple_stmt (dump_kind, TDF_SLIM, stmt, 0);
}
dump_printf (dump_kind, "\n");
- FOR_EACH_VEC_ELT (slp_void_p, SLP_TREE_CHILDREN (node), i, child)
- vect_print_slp_tree (dump_kind, (slp_tree) child);
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ vect_print_slp_tree (dump_kind, child);
}
{
int i;
gimple stmt;
- slp_void_p child;
+ slp_tree child;
if (!node)
return;
- FOR_EACH_VEC_ELT (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt)
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
if (j < 0 || i == j)
STMT_SLP_TYPE (vinfo_for_stmt (stmt)) = mark;
- FOR_EACH_VEC_ELT (slp_void_p, SLP_TREE_CHILDREN (node), i, child)
- vect_mark_slp_stmts ((slp_tree) child, mark, j);
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ vect_mark_slp_stmts (child, mark, j);
}
int i;
gimple stmt;
stmt_vec_info stmt_info;
- slp_void_p child;
+ slp_tree child;
if (!node)
return;
- FOR_EACH_VEC_ELT (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt)
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
{
stmt_info = vinfo_for_stmt (stmt);
gcc_assert (!STMT_VINFO_RELEVANT (stmt_info)
STMT_VINFO_RELEVANT (stmt_info) = vect_used_in_scope;
}
- FOR_EACH_VEC_ELT (slp_void_p, SLP_TREE_CHILDREN (node), i, child)
- vect_mark_slp_stmts_relevant ((slp_tree) child);
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ vect_mark_slp_stmts_relevant (child);
}
-/* Check if the permutation required by the SLP INSTANCE is supported.
- Reorganize the SLP nodes stored in SLP_INSTANCE_LOADS if needed. */
+/* Rearrange the statements of NODE according to PERMUTATION. */
-static bool
-vect_supported_slp_permutation_p (slp_instance instance)
+static void
+vect_slp_rearrange_stmts (slp_tree node, unsigned int group_size,
+ vec<unsigned> permutation)
{
- slp_tree node = VEC_index (slp_tree, SLP_INSTANCE_LOADS (instance), 0);
- gimple stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
- gimple first_load = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt));
- VEC (slp_tree, heap) *sorted_loads = NULL;
- int index;
- slp_tree *tmp_loads = NULL;
- int group_size = SLP_INSTANCE_GROUP_SIZE (instance), i, j;
- slp_tree load;
-
- /* 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.
- 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);
- i += group_size, j++)
- {
- gimple scalar_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (load), 0);
- /* Check that the loads are all in the same interleaving chain. */
- if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (scalar_stmt)) != first_load)
- {
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- {
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "Build SLP failed: unsupported data "
- "permutation ");
- dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
- scalar_stmt, 0);
- }
-
- free (tmp_loads);
- return false;
- }
-
- tmp_loads[index] = load;
- }
+ gimple stmt;
+ vec<gimple> tmp_stmts;
+ unsigned int i;
+ slp_tree child;
- 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]);
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ vect_slp_rearrange_stmts (child, group_size, permutation);
- VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (instance));
- SLP_INSTANCE_LOADS (instance) = sorted_loads;
- free (tmp_loads);
+ gcc_assert (group_size == SLP_TREE_SCALAR_STMTS (node).length ());
+ tmp_stmts.create (group_size);
+ tmp_stmts.quick_grow_cleared (group_size);
- if (!vect_transform_slp_perm_load (stmt, NULL, NULL,
- SLP_INSTANCE_UNROLLING_FACTOR (instance),
- instance, true))
- return false;
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
+ tmp_stmts[permutation[i]] = stmt;
- return true;
+ SLP_TREE_SCALAR_STMTS (node).release ();
+ SLP_TREE_SCALAR_STMTS (node) = tmp_stmts;
}
-/* Rearrange the statements of NODE according to PERMUTATION. */
+/* Attempt to reorder stmts in a reduction chain so that we don't
+ require any load permutation. Return true if that was possible,
+ otherwise return false. */
-static void
-vect_slp_rearrange_stmts (slp_tree node, unsigned int group_size,
- VEC (int, heap) *permutation)
+static bool
+vect_attempt_slp_rearrange_stmts (slp_instance slp_instn)
{
- gimple stmt;
- VEC (gimple, heap) *tmp_stmts;
- unsigned int index, i;
- slp_void_p child;
-
- if (!node)
- return;
-
- FOR_EACH_VEC_ELT (slp_void_p, SLP_TREE_CHILDREN (node), i, child)
- vect_slp_rearrange_stmts ((slp_tree) child, group_size, permutation);
-
- gcc_assert (group_size == VEC_length (gimple, SLP_TREE_SCALAR_STMTS (node)));
- tmp_stmts = VEC_alloc (gimple, heap, group_size);
+ unsigned int group_size = SLP_INSTANCE_GROUP_SIZE (slp_instn);
+ unsigned int i, j;
+ sbitmap load_index;
+ unsigned int lidx;
+ slp_tree node, load;
- for (i = 0; i < group_size; i++)
- VEC_safe_push (gimple, heap, tmp_stmts, NULL);
+ /* Compare all the permutation sequences to the first one. We know
+ that at least one load is permuted. */
+ node = SLP_INSTANCE_LOADS (slp_instn)[0];
+ if (!node->load_permutation.exists ())
+ return false;
+ for (i = 1; SLP_INSTANCE_LOADS (slp_instn).iterate (i, &load); ++i)
+ {
+ if (!load->load_permutation.exists ())
+ return false;
+ FOR_EACH_VEC_ELT (load->load_permutation, j, lidx)
+ if (lidx != node->load_permutation[j])
+ return false;
+ }
- FOR_EACH_VEC_ELT (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt)
+ /* Check that the loads in the first sequence are different and there
+ are no gaps between them. */
+ load_index = sbitmap_alloc (group_size);
+ bitmap_clear (load_index);
+ FOR_EACH_VEC_ELT (node->load_permutation, i, lidx)
{
- index = VEC_index (int, permutation, i);
- VEC_replace (gimple, tmp_stmts, index, stmt);
+ if (bitmap_bit_p (load_index, lidx))
+ {
+ sbitmap_free (load_index);
+ return false;
+ }
+ bitmap_set_bit (load_index, lidx);
}
+ for (i = 0; i < group_size; i++)
+ if (!bitmap_bit_p (load_index, i))
+ {
+ sbitmap_free (load_index);
+ return false;
+ }
+ sbitmap_free (load_index);
- VEC_free (gimple, heap, SLP_TREE_SCALAR_STMTS (node));
- SLP_TREE_SCALAR_STMTS (node) = tmp_stmts;
-}
+ /* This permutation 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,
+ node->load_permutation);
+ /* We are done, no actual permutations need to be generated. */
+ FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
+ SLP_TREE_LOAD_PERMUTATION (node).release ();
+ return true;
+}
-/* 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 grouped stores that are
- the base of the SLP instance. */
+/* Check if the required load permutations in the SLP instance
+ SLP_INSTN are supported. */
static bool
-vect_supported_load_permutation_p (slp_instance slp_instn, int group_size,
- VEC (int, heap) *load_permutation)
+vect_supported_load_permutation_p (slp_instance slp_instn)
{
- int i = 0, j, prev = -1, next, k, number_of_groups;
- bool supported, bad_permutation = false;
- sbitmap load_index;
- slp_tree node, other_complex_node;
- gimple stmt, first = NULL, other_node_first, load, next_load, first_load;
- unsigned complex_numbers = 0;
+ unsigned int group_size = SLP_INSTANCE_GROUP_SIZE (slp_instn);
+ unsigned int i, j, k, next;
+ slp_tree node;
+ gimple stmt, load, next_load, first_load;
struct data_reference *dr;
- bb_vec_info bb_vinfo;
- /* FORNOW: permutations are only supported in SLP. */
- if (!slp_instn)
- return false;
-
- if (dump_kind_p (MSG_NOTE))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_NOTE, vect_location, "Load permutation ");
- FOR_EACH_VEC_ELT (int, load_permutation, i, next)
- dump_printf (MSG_NOTE, "%d ", next);
+ FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
+ if (node->load_permutation.exists ())
+ FOR_EACH_VEC_ELT (node->load_permutation, j, next)
+ dump_printf (MSG_NOTE, "%d ", next);
+ else
+ for (k = 0; k < group_size; ++k)
+ dump_printf (MSG_NOTE, "%d ", k);
+ dump_printf (MSG_NOTE, "\n");
}
/* In case of reduction every load permutation is allowed, since the order
permutation). */
/* Check that all the load nodes are of the same size. */
- FOR_EACH_VEC_ELT (slp_tree, SLP_INSTANCE_LOADS (slp_instn), i, node)
- {
- if (VEC_length (gimple, SLP_TREE_SCALAR_STMTS (node))
- != (unsigned) group_size)
- return false;
-
- stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
- if (is_gimple_assign (stmt)
- && (gimple_assign_rhs_code (stmt) == REALPART_EXPR
- || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR))
- complex_numbers++;
- }
-
- /* Complex operands can be swapped as following:
- real_c = real_b + real_a;
- imag_c = imag_a + imag_b;
- i.e., we have {real_b, imag_a} and {real_a, imag_b} instead of
- {real_a, imag_a} and {real_b, imag_b}. We check here that if interleaving
- chains are mixed, they match the above pattern. */
- if (complex_numbers)
- {
- FOR_EACH_VEC_ELT (slp_tree, SLP_INSTANCE_LOADS (slp_instn), i, node)
- {
- FOR_EACH_VEC_ELT (gimple, SLP_TREE_SCALAR_STMTS (node), j, stmt)
- {
- if (j == 0)
- first = stmt;
- else
- {
- if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) != first)
- {
- if (complex_numbers != 2)
- return false;
-
- if (i == 0)
- k = 1;
- else
- k = 0;
-
- other_complex_node = VEC_index (slp_tree,
- SLP_INSTANCE_LOADS (slp_instn), k);
- other_node_first = VEC_index (gimple,
- SLP_TREE_SCALAR_STMTS (other_complex_node), 0);
-
- if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt))
- != other_node_first)
- return false;
- }
- }
- }
- }
- }
+ /* ??? Can't we assert this? */
+ FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
+ if (SLP_TREE_SCALAR_STMTS (node).length () != (unsigned) group_size)
+ return false;
- /* We checked that this case ok, so there is no need to proceed with
- permutation tests. */
- if (complex_numbers == 2
- && VEC_length (slp_tree, SLP_INSTANCE_LOADS (slp_instn)) == 2)
- {
- VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (slp_instn));
- VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (slp_instn));
- return true;
- }
-
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;
+ stmt = SLP_TREE_SCALAR_STMTS (node)[0];
/* Reduction (there are no data-refs in the root).
- In reduction chain the order of the loads is important. */
+ In reduction chain the order of the loads is not important. */
if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt))
&& !GROUP_FIRST_ELEMENT (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)
- {
- /* Check that the loads in the first sequence are different and there
- are no gaps between them. */
- load_index = sbitmap_alloc (group_size);
- sbitmap_zero (load_index);
- for (k = 0; k < group_size; k++)
- {
- first_group_load_index = VEC_index (int, load_permutation, k);
- if (TEST_BIT (load_index, first_group_load_index))
- {
- bad_permutation = true;
- break;
- }
-
- SET_BIT (load_index, first_group_load_index);
- }
-
- if (!bad_permutation)
- for (k = 0; k < group_size; k++)
- if (!TEST_BIT (load_index, k))
- {
- bad_permutation = true;
- break;
- }
+ if (vect_attempt_slp_rearrange_stmts (slp_instn))
+ return true;
- sbitmap_free (load_index);
- }
-
- if (!bad_permutation)
- {
- /* This permutation 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;
- }
+ /* Fallthru to general load permutation handling. */
}
/* In basic block vectorization we allow any subchain of an interleaving
chain.
FORNOW: not supported in loop SLP because of realignment compications. */
- bb_vinfo = STMT_VINFO_BB_VINFO (vinfo_for_stmt (stmt));
- bad_permutation = false;
- /* Check that for every node in the instance the loads form a subchain. */
- if (bb_vinfo)
+ if (STMT_VINFO_BB_VINFO (vinfo_for_stmt (stmt)))
{
- FOR_EACH_VEC_ELT (slp_tree, SLP_INSTANCE_LOADS (slp_instn), i, node)
+ /* Check whether the loads in an instance form a subchain and thus
+ no permutation is necessary. */
+ FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
{
+ if (!SLP_TREE_LOAD_PERMUTATION (node).exists ())
+ continue;
+ bool subchain_p = true;
next_load = NULL;
- first_load = NULL;
- FOR_EACH_VEC_ELT (gimple, SLP_TREE_SCALAR_STMTS (node), j, load)
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), j, load)
{
- if (!first_load)
- first_load = GROUP_FIRST_ELEMENT (vinfo_for_stmt (load));
- else if (first_load
- != GROUP_FIRST_ELEMENT (vinfo_for_stmt (load)))
- {
- bad_permutation = true;
- break;
- }
-
- if (j != 0 && next_load != load)
- {
- bad_permutation = true;
- break;
- }
-
+ if (j != 0
+ && (next_load != load
+ || GROUP_GAP (vinfo_for_stmt (load)) != 1))
+ {
+ subchain_p = false;
+ break;
+ }
next_load = GROUP_NEXT_ELEMENT (vinfo_for_stmt (load));
}
-
- if (bad_permutation)
- break;
+ if (subchain_p)
+ SLP_TREE_LOAD_PERMUTATION (node).release ();
+ else
+ {
+ /* Verify the permutation can be generated. */
+ vec<tree> tem;
+ if (!vect_transform_slp_perm_load (node, tem, NULL,
+ 1, slp_instn, true))
+ {
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION,
+ vect_location,
+ "unsupported load permutation\n");
+ return false;
+ }
+ }
}
/* Check that the alignment of the first load in every subchain, i.e.,
- the first statement in every load node, is supported. */
- if (!bad_permutation)
- {
- FOR_EACH_VEC_ELT (slp_tree, SLP_INSTANCE_LOADS (slp_instn), i, node)
- {
- first_load = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
- if (first_load
- != GROUP_FIRST_ELEMENT (vinfo_for_stmt (first_load)))
- {
- dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_load));
- if (vect_supportable_dr_alignment (dr, false)
- == dr_unaligned_unsupported)
- {
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- {
- dump_printf_loc (MSG_MISSED_OPTIMIZATION,
- vect_location,
- "unsupported unaligned load ");
- dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
- first_load, 0);
- }
- bad_permutation = true;
- break;
- }
- }
- }
+ the first statement in every load node, is supported.
+ ??? This belongs in alignment checking. */
+ FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
+ {
+ first_load = SLP_TREE_SCALAR_STMTS (node)[0];
+ if (first_load != GROUP_FIRST_ELEMENT (vinfo_for_stmt (first_load)))
+ {
+ dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_load));
+ if (vect_supportable_dr_alignment (dr, false)
+ == dr_unaligned_unsupported)
+ {
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION,
+ vect_location,
+ "unsupported unaligned load ");
+ dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
+ first_load, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
+ }
+ return false;
+ }
+ }
+ }
- if (!bad_permutation)
- {
- VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (slp_instn));
- return true;
- }
- }
+ 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;
+ /* For loop vectorization verify we can generate the permutation. */
+ FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
+ if (node->load_permutation.exists ()
+ && !vect_transform_slp_perm_load
+ (node, vNULL, NULL,
+ SLP_INSTANCE_UNROLLING_FACTOR (slp_instn), slp_instn, true))
+ 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;
- VEC_iterate (int, load_permutation, i, next) && k < group_size;
- i++, k++)
- {
- if (i != j * group_size && next != prev)
- {
- supported = false;
- break;
- }
+ return true;
+}
- prev = next;
- }
- if (TEST_BIT (load_index, prev))
- {
- supported = false;
- break;
- }
+/* Find the last store in SLP INSTANCE. */
+
+static gimple
+vect_find_last_scalar_stmt_in_slp (slp_tree node)
+{
+ gimple last = NULL, stmt;
- SET_BIT (load_index, prev);
+ for (int i = 0; SLP_TREE_SCALAR_STMTS (node).iterate (i, &stmt); i++)
+ {
+ stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
+ if (is_pattern_stmt_p (stmt_vinfo))
+ last = get_later_stmt (STMT_VINFO_RELATED_STMT (stmt_vinfo), last);
+ else
+ last = get_later_stmt (stmt, last);
}
-
- for (j = 0; j < group_size; j++)
- if (!TEST_BIT (load_index, j))
- return false;
- sbitmap_free (load_index);
+ return last;
+}
- if (supported && i == group_size * group_size
- && vect_supported_slp_permutation_p (slp_instn))
- return true;
+/* Compute the cost for the SLP node NODE in the SLP instance INSTANCE. */
- return false;
-}
+static void
+vect_analyze_slp_cost_1 (slp_instance instance, slp_tree node,
+ stmt_vector_for_cost *prologue_cost_vec,
+ stmt_vector_for_cost *body_cost_vec,
+ unsigned ncopies_for_cost)
+{
+ unsigned i;
+ slp_tree child;
+ gimple stmt, s;
+ stmt_vec_info stmt_info;
+ tree lhs;
+ unsigned group_size = SLP_INSTANCE_GROUP_SIZE (instance);
+ /* Recurse down the SLP tree. */
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ if (child)
+ vect_analyze_slp_cost_1 (instance, child, prologue_cost_vec,
+ body_cost_vec, ncopies_for_cost);
-/* 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
- 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. */
+ /* Look at the first scalar stmt to determine the cost. */
+ stmt = SLP_TREE_SCALAR_STMTS (node)[0];
+ stmt_info = vinfo_for_stmt (stmt);
+ if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
+ {
+ if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info)))
+ vect_model_store_cost (stmt_info, ncopies_for_cost, false,
+ vect_uninitialized_def,
+ node, prologue_cost_vec, body_cost_vec);
+ else
+ {
+ int i;
+ gcc_checking_assert (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info)));
+ vect_model_load_cost (stmt_info, ncopies_for_cost, false,
+ node, prologue_cost_vec, body_cost_vec);
+ /* If the load is permuted record the cost for the permutation.
+ ??? Loads from multiple chains are let through here only
+ for a single special case involving complex numbers where
+ in the end no permutation is necessary. */
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, s)
+ if ((STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo_for_stmt (s))
+ == STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info))
+ && vect_get_place_in_interleaving_chain
+ (s, STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info)) != i)
+ {
+ record_stmt_cost (body_cost_vec, group_size, vec_perm,
+ stmt_info, 0, vect_body);
+ break;
+ }
+ }
+ }
+ else
+ {
+ record_stmt_cost (body_cost_vec, ncopies_for_cost, vector_stmt,
+ stmt_info, 0, vect_body);
+ if (SLP_TREE_TWO_OPERATORS (node))
+ {
+ record_stmt_cost (body_cost_vec, ncopies_for_cost, vector_stmt,
+ stmt_info, 0, vect_body);
+ record_stmt_cost (body_cost_vec, ncopies_for_cost, vec_perm,
+ stmt_info, 0, vect_body);
+ }
+ }
-static gimple
-vect_find_first_load_in_slp_instance (slp_instance instance)
-{
- int i, j;
- slp_tree load_node;
- gimple first_load = NULL, load;
+ /* Scan operands and account for prologue cost of constants/externals.
+ ??? This over-estimates cost for multiple uses and should be
+ re-engineered. */
+ lhs = gimple_get_lhs (stmt);
+ for (i = 0; i < gimple_num_ops (stmt); ++i)
+ {
+ tree def, op = gimple_op (stmt, i);
+ gimple def_stmt;
+ enum vect_def_type dt;
+ if (!op || op == lhs)
+ continue;
+ if (vect_is_simple_use (op, NULL, STMT_VINFO_LOOP_VINFO (stmt_info),
+ STMT_VINFO_BB_VINFO (stmt_info),
+ &def_stmt, &def, &dt))
+ {
+ /* Without looking at the actual initializer a vector of
+ constants can be implemented as load from the constant pool.
+ ??? We need to pass down stmt_info for a vector type
+ even if it points to the wrong stmt. */
+ if (dt == vect_constant_def)
+ record_stmt_cost (prologue_cost_vec, 1, vector_load,
+ stmt_info, 0, vect_prologue);
+ else if (dt == vect_external_def)
+ record_stmt_cost (prologue_cost_vec, 1, vec_construct,
+ stmt_info, 0, vect_prologue);
+ }
+ }
+}
- FOR_EACH_VEC_ELT (slp_tree, SLP_INSTANCE_LOADS (instance), i, load_node)
- FOR_EACH_VEC_ELT (gimple, SLP_TREE_SCALAR_STMTS (load_node), j, load)
- first_load = get_earlier_stmt (load, first_load);
+/* Compute the cost for the SLP instance INSTANCE. */
- return first_load;
-}
+static void
+vect_analyze_slp_cost (slp_instance instance, void *data)
+{
+ stmt_vector_for_cost body_cost_vec, prologue_cost_vec;
+ unsigned ncopies_for_cost;
+ stmt_info_for_cost *si;
+ unsigned i;
+ /* Calculate the number of vector stmts to create based on the unrolling
+ factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
+ GROUP_SIZE / NUNITS otherwise. */
+ unsigned group_size = SLP_INSTANCE_GROUP_SIZE (instance);
+ slp_tree node = SLP_INSTANCE_TREE (instance);
+ stmt_vec_info stmt_info = vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node)[0]);
+ /* Adjust the group_size by the vectorization factor which is always one
+ for basic-block vectorization. */
+ if (STMT_VINFO_LOOP_VINFO (stmt_info))
+ group_size *= LOOP_VINFO_VECT_FACTOR (STMT_VINFO_LOOP_VINFO (stmt_info));
+ unsigned nunits = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
+ /* For reductions look at a reduction operand in case the reduction
+ operation is widening like DOT_PROD or SAD. */
+ if (!STMT_VINFO_GROUPED_ACCESS (stmt_info))
+ {
+ gimple stmt = SLP_TREE_SCALAR_STMTS (node)[0];
+ switch (gimple_assign_rhs_code (stmt))
+ {
+ case DOT_PROD_EXPR:
+ case SAD_EXPR:
+ nunits = TYPE_VECTOR_SUBPARTS (get_vectype_for_scalar_type
+ (TREE_TYPE (gimple_assign_rhs1 (stmt))));
+ break;
+ default:;
+ }
+ }
+ ncopies_for_cost = least_common_multiple (nunits, group_size) / nunits;
-/* Find the last store in SLP INSTANCE. */
+ prologue_cost_vec.create (10);
+ body_cost_vec.create (10);
+ vect_analyze_slp_cost_1 (instance, SLP_INSTANCE_TREE (instance),
+ &prologue_cost_vec, &body_cost_vec,
+ ncopies_for_cost);
-static gimple
-vect_find_last_store_in_slp_instance (slp_instance instance)
-{
- int i;
- slp_tree node;
- gimple last_store = NULL, store;
+ /* Record the prologue costs, which were delayed until we were
+ sure that SLP was successful. */
+ FOR_EACH_VEC_ELT (prologue_cost_vec, i, si)
+ {
+ struct _stmt_vec_info *stmt_info
+ = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
+ (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
+ si->misalign, vect_prologue);
+ }
- node = SLP_INSTANCE_TREE (instance);
- for (i = 0;
- VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, store);
- i++)
- last_store = get_later_stmt (store, last_store);
+ /* Record the instance's instructions in the target cost model. */
+ FOR_EACH_VEC_ELT (body_cost_vec, i, si)
+ {
+ struct _stmt_vec_info *stmt_info
+ = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
+ (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
+ si->misalign, vect_body);
+ }
- return last_store;
+ prologue_cost_vec.release ();
+ body_cost_vec.release ();
}
-
/* Analyze an SLP instance starting from a group of grouped stores. Call
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
vect_analyze_slp_instance (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
- gimple stmt)
+ gimple stmt, unsigned max_tree_size)
{
slp_instance new_instance;
slp_tree node;
tree vectype, scalar_type = NULL_TREE;
gimple next;
unsigned int vectorization_factor = 0;
- int outside_cost = 0, ncopies_for_cost, i;
+ int i;
unsigned int max_nunits = 0;
- VEC (int, heap) *load_permutation;
- VEC (slp_tree, heap) *loads;
+ vec<slp_tree> loads;
struct data_reference *dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
- bool loads_permuted = false;
- VEC (gimple, heap) *scalar_stmts;
- stmt_vector_for_cost body_cost_vec, prologue_cost_vec;
- stmt_info_for_cost *si;
+ vec<gimple> scalar_stmts;
if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
{
{
gcc_assert (loop_vinfo);
vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
- group_size = VEC_length (gimple, LOOP_VINFO_REDUCTIONS (loop_vinfo));
+ group_size = LOOP_VINFO_REDUCTIONS (loop_vinfo).length ();
}
if (!vectype)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: unsupported data-type ");
dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, scalar_type);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
return false;
unrolling_factor = least_common_multiple (nunits, group_size) / group_size;
if (unrolling_factor != 1 && !loop_vinfo)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: unrolling required in basic"
- " block SLP");
+ " block SLP\n");
return false;
}
/* Create a node (a root of the SLP tree) for the packed grouped stores. */
- scalar_stmts = VEC_alloc (gimple, heap, group_size);
+ scalar_stmts.create (group_size);
next = stmt;
if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
{
{
if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next))
&& STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next)))
- VEC_safe_push (gimple, heap, scalar_stmts,
- STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next)));
+ scalar_stmts.safe_push (
+ STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next)));
else
- VEC_safe_push (gimple, heap, scalar_stmts, next);
+ scalar_stmts.safe_push (next);
next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next));
}
+ /* Mark the first element of the reduction chain as reduction to properly
+ transform the node. In the reduction analysis phase only the last
+ element of the chain is marked as reduction. */
+ if (!STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt)))
+ STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt)) = vect_reduction_def;
}
else
{
/* Collect reduction statements. */
- VEC (gimple, heap) *reductions = LOOP_VINFO_REDUCTIONS (loop_vinfo);
- for (i = 0; VEC_iterate (gimple, reductions, i, next); i++)
- VEC_safe_push (gimple, heap, scalar_stmts, next);
+ vec<gimple> reductions = LOOP_VINFO_REDUCTIONS (loop_vinfo);
+ for (i = 0; reductions.iterate (i, &next); i++)
+ scalar_stmts.safe_push (next);
}
node = vect_create_new_slp_node (scalar_stmts);
- /* Calculate the number of vector stmts to create based on the unrolling
- 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);
- prologue_cost_vec = VEC_alloc (stmt_info_for_cost, heap, 10);
- body_cost_vec = VEC_alloc (stmt_info_for_cost, heap, 10);
+ loads.create (group_size);
/* Build the tree for the SLP instance. */
+ bool *matches = XALLOCAVEC (bool, group_size);
+ unsigned npermutes = 0;
if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &node, group_size,
- &outside_cost, ncopies_for_cost,
- &max_nunits, &load_permutation, &loads,
- vectorization_factor, &loads_permuted,
- &prologue_cost_vec, &body_cost_vec))
+ &max_nunits, &loads,
+ vectorization_factor, matches, &npermutes, NULL,
+ max_tree_size))
{
- void *data = (loop_vinfo ? LOOP_VINFO_TARGET_COST_DATA (loop_vinfo)
- : BB_VINFO_TARGET_COST_DATA (bb_vinfo));
-
/* Calculate the unrolling factor based on the smallest type. */
if (max_nunits > nunits)
unrolling_factor = least_common_multiple (max_nunits, group_size)
if (unrolling_factor != 1 && !loop_vinfo)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: unrolling required in basic"
- " block SLP");
+ " block SLP\n");
vect_free_slp_tree (node);
- VEC_free (stmt_info_for_cost, heap, body_cost_vec);
- VEC_free (stmt_info_for_cost, heap, prologue_cost_vec);
- VEC_free (int, heap, load_permutation);
- VEC_free (slp_tree, heap, loads);
+ loads.release ();
return false;
}
SLP_INSTANCE_TREE (new_instance) = node;
SLP_INSTANCE_GROUP_SIZE (new_instance) = group_size;
SLP_INSTANCE_UNROLLING_FACTOR (new_instance) = unrolling_factor;
- SLP_INSTANCE_BODY_COST_VEC (new_instance) = body_cost_vec;
SLP_INSTANCE_LOADS (new_instance) = loads;
- SLP_INSTANCE_FIRST_LOAD_STMT (new_instance) = NULL;
- SLP_INSTANCE_LOAD_PERMUTATION (new_instance) = load_permutation;
+
+ /* Compute the load permutation. */
+ slp_tree load_node;
+ bool loads_permuted = false;
+ FOR_EACH_VEC_ELT (loads, i, load_node)
+ {
+ vec<unsigned> load_permutation;
+ int j;
+ gimple load, first_stmt;
+ bool this_load_permuted = false;
+ load_permutation.create (group_size);
+ first_stmt = GROUP_FIRST_ELEMENT
+ (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node)[0]));
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node), j, load)
+ {
+ int load_place
+ = vect_get_place_in_interleaving_chain (load, first_stmt);
+ gcc_assert (load_place != -1);
+ if (load_place != j)
+ this_load_permuted = true;
+ load_permutation.safe_push (load_place);
+ }
+ if (!this_load_permuted
+ /* The load requires permutation when unrolling exposes
+ a gap either because the group is larger than the SLP
+ group-size or because there is a gap between the groups. */
+ && (unrolling_factor == 1
+ || (group_size == GROUP_SIZE (vinfo_for_stmt (first_stmt))
+ && GROUP_GAP (vinfo_for_stmt (first_stmt)) == 0)))
+ {
+ load_permutation.release ();
+ continue;
+ }
+ SLP_TREE_LOAD_PERMUTATION (load_node) = load_permutation;
+ loads_permuted = true;
+ }
if (loads_permuted)
{
- if (!vect_supported_load_permutation_p (new_instance, group_size,
- load_permutation))
+ if (!vect_supported_load_permutation_p (new_instance))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"Build SLP failed: unsupported load "
"permutation ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
-
vect_free_slp_instance (new_instance);
- VEC_free (stmt_info_for_cost, heap, prologue_cost_vec);
return false;
}
-
- SLP_INSTANCE_FIRST_LOAD_STMT (new_instance)
- = vect_find_first_load_in_slp_instance (new_instance);
}
- else
- VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (new_instance));
-
- /* Record the prologue costs, which were delayed until we were
- sure that SLP was successful. Unlike the body costs, we know
- the final values now regardless of the loop vectorization factor. */
- FOR_EACH_VEC_ELT (stmt_info_for_cost, prologue_cost_vec, i, si)
- {
- struct _stmt_vec_info *stmt_info
- = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
- (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
- si->misalign, vect_prologue);
- }
- VEC_free (stmt_info_for_cost, heap, prologue_cost_vec);
if (loop_vinfo)
- VEC_safe_push (slp_instance, heap,
- LOOP_VINFO_SLP_INSTANCES (loop_vinfo),
- new_instance);
+ LOOP_VINFO_SLP_INSTANCES (loop_vinfo).safe_push (new_instance);
else
- VEC_safe_push (slp_instance, heap, BB_VINFO_SLP_INSTANCES (bb_vinfo),
- new_instance);
+ BB_VINFO_SLP_INSTANCES (bb_vinfo).safe_push (new_instance);
- if (dump_kind_p (MSG_NOTE))
+ if (dump_enabled_p ())
vect_print_slp_tree (MSG_NOTE, node);
return true;
}
- else
- {
- VEC_free (stmt_info_for_cost, heap, body_cost_vec);
- VEC_free (stmt_info_for_cost, heap, prologue_cost_vec);
- }
/* Failed to SLP. */
/* Free the allocated memory. */
vect_free_slp_tree (node);
- VEC_free (int, heap, load_permutation);
- VEC_free (slp_tree, heap, loads);
+ loads.release ();
return false;
}
trees of packed scalar stmts if SLP is possible. */
bool
-vect_analyze_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
+vect_analyze_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
+ unsigned max_tree_size)
{
unsigned int i;
- VEC (gimple, heap) *grouped_stores, *reductions = NULL, *reduc_chains = NULL;
+ vec<gimple> grouped_stores;
+ vec<gimple> reductions = vNULL;
+ vec<gimple> reduc_chains = vNULL;
gimple first_element;
bool ok = false;
- if (dump_kind_p (MSG_NOTE))
- dump_printf_loc (MSG_NOTE, vect_location, "=== vect_analyze_slp ===");
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location, "=== vect_analyze_slp ===\n");
if (loop_vinfo)
{
grouped_stores = BB_VINFO_GROUPED_STORES (bb_vinfo);
/* Find SLP sequences starting from groups of grouped stores. */
- FOR_EACH_VEC_ELT (gimple, grouped_stores, i, first_element)
- if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, first_element))
+ FOR_EACH_VEC_ELT (grouped_stores, i, first_element)
+ if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, first_element,
+ max_tree_size))
ok = true;
- if (bb_vinfo && !ok)
- {
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "Failed to SLP the basic block.");
-
- return false;
- }
-
- if (loop_vinfo
- && VEC_length (gimple, LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo)) > 0)
+ if (reduc_chains.length () > 0)
{
/* Find SLP sequences starting from reduction chains. */
- FOR_EACH_VEC_ELT (gimple, reduc_chains, i, first_element)
- if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, first_element))
+ FOR_EACH_VEC_ELT (reduc_chains, i, first_element)
+ if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, first_element,
+ max_tree_size))
ok = true;
else
return false;
}
/* Find SLP sequences starting from groups of reductions. */
- if (loop_vinfo && VEC_length (gimple, LOOP_VINFO_REDUCTIONS (loop_vinfo)) > 1
- && vect_analyze_slp_instance (loop_vinfo, bb_vinfo,
- VEC_index (gimple, reductions, 0)))
+ if (reductions.length () > 1
+ && vect_analyze_slp_instance (loop_vinfo, bb_vinfo, reductions[0],
+ max_tree_size))
ok = true;
return true;
vect_make_slp_decision (loop_vec_info loop_vinfo)
{
unsigned int i, unrolling_factor = 1;
- VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
+ vec<slp_instance> slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
slp_instance instance;
int decided_to_slp = 0;
- if (dump_kind_p (MSG_NOTE))
- dump_printf_loc (MSG_NOTE, vect_location, "=== vect_make_slp_decision ===");
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location, "=== vect_make_slp_decision ==="
+ "\n");
- FOR_EACH_VEC_ELT (slp_instance, slp_instances, i, instance)
+ FOR_EACH_VEC_ELT (slp_instances, i, instance)
{
/* FORNOW: SLP if you can. */
if (unrolling_factor < SLP_INSTANCE_UNROLLING_FACTOR (instance))
LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo) = unrolling_factor;
- if (decided_to_slp && dump_kind_p (MSG_OPTIMIZED_LOCATIONS))
- dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
- "Decided to SLP %d instances. Unrolling factor %d",
+ if (decided_to_slp && dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "Decided to SLP %d instances. Unrolling factor %d\n",
decided_to_slp, unrolling_factor);
return (decided_to_slp > 0);
can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
static void
-vect_detect_hybrid_slp_stmts (slp_tree node)
+vect_detect_hybrid_slp_stmts (slp_tree node, unsigned i, slp_vect_type stype)
{
- int i;
- VEC (gimple, heap) *stmts = SLP_TREE_SCALAR_STMTS (node);
- gimple stmt = VEC_index (gimple, stmts, 0);
+ gimple stmt = SLP_TREE_SCALAR_STMTS (node)[i];
imm_use_iterator imm_iter;
gimple use_stmt;
- stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
- slp_void_p child;
+ stmt_vec_info use_vinfo, stmt_vinfo = vinfo_for_stmt (stmt);
+ slp_tree child;
loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
- struct loop *loop = NULL;
- bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_vinfo);
- basic_block bb = NULL;
+ struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
+ int j;
+
+ /* Propagate hybrid down the SLP tree. */
+ if (stype == hybrid)
+ ;
+ else if (HYBRID_SLP_STMT (stmt_vinfo))
+ stype = hybrid;
+ else
+ {
+ /* Check if a pure SLP stmt has uses in non-SLP stmts. */
+ gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo));
+ /* We always get the pattern stmt here, but for immediate
+ uses we have to use the LHS of the original stmt. */
+ gcc_checking_assert (!STMT_VINFO_IN_PATTERN_P (stmt_vinfo));
+ if (STMT_VINFO_RELATED_STMT (stmt_vinfo))
+ stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
+ if (TREE_CODE (gimple_op (stmt, 0)) == SSA_NAME)
+ FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, gimple_op (stmt, 0))
+ {
+ if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
+ continue;
+ use_vinfo = vinfo_for_stmt (use_stmt);
+ if (STMT_VINFO_IN_PATTERN_P (use_vinfo)
+ && STMT_VINFO_RELATED_STMT (use_vinfo))
+ use_vinfo = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (use_vinfo));
+ if (!STMT_SLP_TYPE (use_vinfo)
+ && (STMT_VINFO_RELEVANT (use_vinfo)
+ || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo)))
+ && !(gimple_code (use_stmt) == GIMPLE_PHI
+ && STMT_VINFO_DEF_TYPE (use_vinfo) == vect_reduction_def))
+ {
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_NOTE, vect_location, "use of SLP "
+ "def in non-SLP stmt: ");
+ dump_gimple_stmt (MSG_NOTE, TDF_SLIM, use_stmt, 0);
+ }
+ stype = hybrid;
+ }
+ }
+ }
+
+ if (stype == hybrid
+ && !HYBRID_SLP_STMT (stmt_vinfo))
+ {
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_NOTE, vect_location, "marking hybrid: ");
+ dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
+ }
+ STMT_SLP_TYPE (stmt_vinfo) = hybrid;
+ }
- if (!node)
- return;
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), j, child)
+ if (child)
+ vect_detect_hybrid_slp_stmts (child, i, stype);
+}
- if (loop_vinfo)
- loop = LOOP_VINFO_LOOP (loop_vinfo);
- else
- bb = BB_VINFO_BB (bb_vinfo);
-
- FOR_EACH_VEC_ELT (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt)
- 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 (gimple_bb (use_stmt)
- && ((loop && flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
- || bb == gimple_bb (use_stmt))
- && (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 (stmt_vinfo)
- == vect_reduction_def))
- vect_mark_slp_stmts (node, hybrid, i);
-
- FOR_EACH_VEC_ELT (slp_void_p, SLP_TREE_CHILDREN (node), i, child)
- vect_detect_hybrid_slp_stmts ((slp_tree) child);
+/* Helpers for vect_detect_hybrid_slp walking pattern stmt uses. */
+
+static tree
+vect_detect_hybrid_slp_1 (tree *tp, int *, void *data)
+{
+ walk_stmt_info *wi = (walk_stmt_info *)data;
+ struct loop *loopp = (struct loop *)wi->info;
+
+ if (wi->is_lhs)
+ return NULL_TREE;
+
+ if (TREE_CODE (*tp) == SSA_NAME
+ && !SSA_NAME_IS_DEFAULT_DEF (*tp))
+ {
+ gimple def_stmt = SSA_NAME_DEF_STMT (*tp);
+ if (flow_bb_inside_loop_p (loopp, gimple_bb (def_stmt))
+ && PURE_SLP_STMT (vinfo_for_stmt (def_stmt)))
+ {
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_NOTE, vect_location, "marking hybrid: ");
+ dump_gimple_stmt (MSG_NOTE, TDF_SLIM, def_stmt, 0);
+ }
+ STMT_SLP_TYPE (vinfo_for_stmt (def_stmt)) = hybrid;
+ }
+ }
+
+ return NULL_TREE;
}
+static tree
+vect_detect_hybrid_slp_2 (gimple_stmt_iterator *gsi, bool *handled,
+ walk_stmt_info *)
+{
+ /* If the stmt is in a SLP instance then this isn't a reason
+ to mark use definitions in other SLP instances as hybrid. */
+ if (STMT_SLP_TYPE (vinfo_for_stmt (gsi_stmt (*gsi))) != loop_vect)
+ *handled = true;
+ return NULL_TREE;
+}
/* Find stmts that must be both vectorized and SLPed. */
vect_detect_hybrid_slp (loop_vec_info loop_vinfo)
{
unsigned int i;
- VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
+ vec<slp_instance> slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
slp_instance instance;
- if (dump_kind_p (MSG_NOTE))
- dump_printf_loc (MSG_NOTE, vect_location, "=== vect_detect_hybrid_slp ===");
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location, "=== vect_detect_hybrid_slp ==="
+ "\n");
+
+ /* First walk all pattern stmt in the loop and mark defs of uses as
+ hybrid because immediate uses in them are not recorded. */
+ for (i = 0; i < LOOP_VINFO_LOOP (loop_vinfo)->num_nodes; ++i)
+ {
+ basic_block bb = LOOP_VINFO_BBS (loop_vinfo)[i];
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+ stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+ if (STMT_VINFO_IN_PATTERN_P (stmt_info))
+ {
+ walk_stmt_info wi;
+ memset (&wi, 0, sizeof (wi));
+ wi.info = LOOP_VINFO_LOOP (loop_vinfo);
+ gimple_stmt_iterator gsi2
+ = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info));
+ walk_gimple_stmt (&gsi2, vect_detect_hybrid_slp_2,
+ vect_detect_hybrid_slp_1, &wi);
+ walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info),
+ vect_detect_hybrid_slp_2,
+ vect_detect_hybrid_slp_1, &wi);
+ }
+ }
+ }
- FOR_EACH_VEC_ELT (slp_instance, slp_instances, i, instance)
- vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance));
+ /* Then walk the SLP instance trees marking stmts with uses in
+ non-SLP stmts as hybrid, also propagating hybrid down the
+ SLP tree, collecting the above info on-the-fly. */
+ FOR_EACH_VEC_ELT (slp_instances, i, instance)
+ {
+ for (unsigned i = 0; i < SLP_INSTANCE_GROUP_SIZE (instance); ++i)
+ vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance),
+ i, pure_slp);
+ }
}
set_vinfo_for_stmt (stmt, new_stmt_vec_info (stmt, NULL, res));
}
- BB_VINFO_GROUPED_STORES (res) = VEC_alloc (gimple, heap, 10);
- BB_VINFO_SLP_INSTANCES (res) = VEC_alloc (slp_instance, heap, 2);
+ BB_VINFO_GROUPED_STORES (res).create (10);
+ BB_VINFO_SLP_INSTANCES (res).create (2);
BB_VINFO_TARGET_COST_DATA (res) = init_cost (NULL);
bb->aux = res;
static void
destroy_bb_vec_info (bb_vec_info bb_vinfo)
{
- VEC (slp_instance, heap) *slp_instances;
+ vec<slp_instance> slp_instances;
slp_instance instance;
basic_block bb;
gimple_stmt_iterator si;
free_stmt_vec_info (stmt);
}
- free_data_refs (BB_VINFO_DATAREFS (bb_vinfo));
+ vect_destroy_datarefs (NULL, bb_vinfo);
free_dependence_relations (BB_VINFO_DDRS (bb_vinfo));
- VEC_free (gimple, heap, BB_VINFO_GROUPED_STORES (bb_vinfo));
+ BB_VINFO_GROUPED_STORES (bb_vinfo).release ();
slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
- FOR_EACH_VEC_ELT (slp_instance, slp_instances, i, instance)
+ FOR_EACH_VEC_ELT (slp_instances, i, instance)
vect_free_slp_instance (instance);
- VEC_free (slp_instance, heap, BB_VINFO_SLP_INSTANCES (bb_vinfo));
+ BB_VINFO_SLP_INSTANCES (bb_vinfo).release ();
destroy_cost_data (BB_VINFO_TARGET_COST_DATA (bb_vinfo));
free (bb_vinfo);
bb->aux = NULL;
the subtree. Return TRUE if the operations are supported. */
static bool
-vect_slp_analyze_node_operations (bb_vec_info bb_vinfo, slp_tree node)
+vect_slp_analyze_node_operations (slp_tree node)
{
bool dummy;
int i;
gimple stmt;
- slp_void_p child;
+ slp_tree child;
if (!node)
return true;
- FOR_EACH_VEC_ELT (slp_void_p, SLP_TREE_CHILDREN (node), i, child)
- if (!vect_slp_analyze_node_operations (bb_vinfo, (slp_tree) child))
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ if (!vect_slp_analyze_node_operations (child))
return false;
- FOR_EACH_VEC_ELT (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt)
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
{
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
gcc_assert (stmt_info);
- gcc_assert (PURE_SLP_STMT (stmt_info));
+ gcc_assert (STMT_SLP_TYPE (stmt_info) != loop_vect);
if (!vect_analyze_stmt (stmt, &dummy, node))
- return false;
+ return false;
}
return true;
/* Analyze statements in SLP instances of the basic block. Return TRUE if the
operations are supported. */
-static bool
-vect_slp_analyze_operations (bb_vec_info bb_vinfo)
+bool
+vect_slp_analyze_operations (vec<slp_instance> slp_instances, void *data)
{
- VEC (slp_instance, heap) *slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
slp_instance instance;
int i;
- for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); )
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "=== vect_slp_analyze_operations ===\n");
+
+ for (i = 0; slp_instances.iterate (i, &instance); )
{
- if (!vect_slp_analyze_node_operations (bb_vinfo,
- SLP_INSTANCE_TREE (instance)))
+ if (!vect_slp_analyze_node_operations (SLP_INSTANCE_TREE (instance)))
{
- vect_free_slp_instance (instance);
- VEC_ordered_remove (slp_instance, slp_instances, i);
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "removing SLP instance operations starting from: ");
+ dump_gimple_stmt (MSG_NOTE, TDF_SLIM,
+ SLP_TREE_SCALAR_STMTS
+ (SLP_INSTANCE_TREE (instance))[0], 0);
+ vect_free_slp_instance (instance);
+ slp_instances.ordered_remove (i);
}
else
- i++;
+ {
+ /* Compute the costs of the SLP instance. */
+ vect_analyze_slp_cost (instance, data);
+ i++;
+ }
}
- if (!VEC_length (slp_instance, slp_instances))
+ if (!slp_instances.length ())
return false;
return true;
}
-/* Check if vectorization of the basic block is profitable. */
-static bool
-vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo)
+/* Compute the scalar cost of the SLP node NODE and its children
+ and return it. Do not account defs that are marked in LIFE and
+ update LIFE according to uses of NODE. */
+
+static unsigned
+vect_bb_slp_scalar_cost (basic_block bb,
+ slp_tree node, vec<bool, va_heap> *life)
{
- VEC (slp_instance, heap) *slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
- slp_instance instance;
- int i, j;
- unsigned int vec_inside_cost = 0, vec_outside_cost = 0, scalar_cost = 0;
- unsigned int vec_prologue_cost = 0, vec_epilogue_cost = 0;
- unsigned int stmt_cost;
+ unsigned scalar_cost = 0;
+ unsigned i;
gimple stmt;
- gimple_stmt_iterator si;
- basic_block bb = BB_VINFO_BB (bb_vinfo);
- void *target_cost_data = BB_VINFO_TARGET_COST_DATA (bb_vinfo);
- stmt_vec_info stmt_info = NULL;
- stmt_vector_for_cost body_cost_vec;
- stmt_info_for_cost *ci;
+ slp_tree child;
- /* Calculate vector costs. */
- FOR_EACH_VEC_ELT (slp_instance, slp_instances, i, instance)
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
{
- body_cost_vec = SLP_INSTANCE_BODY_COST_VEC (instance);
+ unsigned stmt_cost;
+ ssa_op_iter op_iter;
+ def_operand_p def_p;
+ stmt_vec_info stmt_info;
+
+ if ((*life)[i])
+ continue;
- FOR_EACH_VEC_ELT (stmt_info_for_cost, body_cost_vec, j, ci)
+ /* If there is a non-vectorized use of the defs then the scalar
+ stmt is kept live in which case we do not account it or any
+ required defs in the SLP children in the scalar cost. This
+ way we make the vectorization more costly when compared to
+ the scalar cost. */
+ FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_DEF)
{
- stmt_info = ci->stmt ? vinfo_for_stmt (ci->stmt) : NULL;
- (void) add_stmt_cost (target_cost_data, ci->count, ci->kind,
- stmt_info, ci->misalign, vect_body);
+ imm_use_iterator use_iter;
+ gimple use_stmt;
+ FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, DEF_FROM_PTR (def_p))
+ if (!is_gimple_debug (use_stmt)
+ && (gimple_code (use_stmt) == GIMPLE_PHI
+ || gimple_bb (use_stmt) != bb
+ || !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (use_stmt))))
+ {
+ (*life)[i] = true;
+ BREAK_FROM_IMM_USE_STMT (use_iter);
+ }
}
- }
+ if ((*life)[i])
+ continue;
- /* Calculate scalar cost. */
- for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
- {
- stmt = gsi_stmt (si);
stmt_info = vinfo_for_stmt (stmt);
-
- if (!stmt_info || !STMT_VINFO_VECTORIZABLE (stmt_info)
- || !PURE_SLP_STMT (stmt_info))
- continue;
-
if (STMT_VINFO_DATA_REF (stmt_info))
{
if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info)))
scalar_cost += stmt_cost;
}
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ if (child)
+ scalar_cost += vect_bb_slp_scalar_cost (bb, child, life);
+
+ return scalar_cost;
+}
+
+/* Check if vectorization of the basic block is profitable. */
+
+static bool
+vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo)
+{
+ vec<slp_instance> slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
+ slp_instance instance;
+ int i;
+ unsigned int vec_inside_cost = 0, vec_outside_cost = 0, scalar_cost = 0;
+ unsigned int vec_prologue_cost = 0, vec_epilogue_cost = 0;
+
+ /* Calculate scalar cost. */
+ FOR_EACH_VEC_ELT (slp_instances, i, instance)
+ {
+ auto_vec<bool, 20> life;
+ life.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance));
+ scalar_cost += vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo),
+ SLP_INSTANCE_TREE (instance),
+ &life);
+ }
+
/* Complete the target-specific cost calculation. */
finish_cost (BB_VINFO_TARGET_COST_DATA (bb_vinfo), &vec_prologue_cost,
&vec_inside_cost, &vec_epilogue_cost);
vec_outside_cost = vec_prologue_cost + vec_epilogue_cost;
- if (dump_kind_p (MSG_NOTE))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_NOTE, vect_location, "Cost model analysis: \n");
dump_printf (MSG_NOTE, " Vector inside of basic block cost: %d\n",
vec_inside_cost);
dump_printf (MSG_NOTE, " Vector prologue cost: %d\n", vec_prologue_cost);
dump_printf (MSG_NOTE, " Vector epilogue cost: %d\n", vec_epilogue_cost);
- dump_printf (MSG_NOTE, " Scalar cost of basic block: %d", scalar_cost);
+ dump_printf (MSG_NOTE, " Scalar cost of basic block: %d\n", scalar_cost);
}
/* Vectorization is profitable if its cost is less than the cost of scalar
vect_slp_analyze_bb_1 (basic_block bb)
{
bb_vec_info bb_vinfo;
- VEC (ddr_p, heap) *ddrs;
- VEC (slp_instance, heap) *slp_instances;
+ vec<slp_instance> slp_instances;
slp_instance instance;
int i;
int min_vf = 2;
- int max_vf = MAX_VECTORIZATION_FACTOR;
+ unsigned n_stmts = 0;
bb_vinfo = new_bb_vec_info (bb);
if (!bb_vinfo)
return NULL;
- if (!vect_analyze_data_refs (NULL, bb_vinfo, &min_vf))
+ if (!vect_analyze_data_refs (NULL, bb_vinfo, &min_vf, &n_stmts))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"not vectorized: unhandled data-ref in basic "
"block.\n");
return NULL;
}
- ddrs = BB_VINFO_DDRS (bb_vinfo);
- if (!VEC_length (ddr_p, ddrs))
+ if (BB_VINFO_DATAREFS (bb_vinfo).length () < 2)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"not vectorized: not enough data-refs in "
"basic block.\n");
return NULL;
}
- vect_pattern_recog (NULL, bb_vinfo);
+ if (!vect_analyze_data_ref_accesses (NULL, bb_vinfo))
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "not vectorized: unhandled data access in "
+ "basic block.\n");
- if (!vect_analyze_data_ref_dependences (NULL, bb_vinfo, &max_vf)
- || min_vf > max_vf)
- {
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "not vectorized: unhandled data dependence "
- "in basic block.\n");
+ destroy_bb_vec_info (bb_vinfo);
+ return NULL;
+ }
- destroy_bb_vec_info (bb_vinfo);
- return NULL;
- }
+ vect_pattern_recog (NULL, bb_vinfo);
if (!vect_analyze_data_refs_alignment (NULL, bb_vinfo))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"not vectorized: bad data alignment in basic "
"block.\n");
return NULL;
}
- if (!vect_analyze_data_ref_accesses (NULL, bb_vinfo))
- {
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "not vectorized: unhandled data access in "
- "basic block.\n");
-
- destroy_bb_vec_info (bb_vinfo);
- return NULL;
- }
-
/* Check the SLP opportunities in the basic block, analyze and build SLP
trees. */
- if (!vect_analyze_slp (NULL, bb_vinfo))
+ if (!vect_analyze_slp (NULL, bb_vinfo, n_stmts))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "not vectorized: failed to find SLP opportunities "
- "in basic block.\n");
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "Failed to SLP the basic block.\n");
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "not vectorized: failed to find SLP opportunities "
+ "in basic block.\n");
+ }
destroy_bb_vec_info (bb_vinfo);
return NULL;
/* Mark all the statements that we want to vectorize as pure SLP and
relevant. */
- FOR_EACH_VEC_ELT (slp_instance, slp_instances, i, instance)
+ FOR_EACH_VEC_ELT (slp_instances, i, instance)
{
vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance));
}
+ /* Mark all the statements that we do not want to vectorize. */
+ for (gimple_stmt_iterator gsi = gsi_start_bb (BB_VINFO_BB (bb_vinfo));
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ stmt_vec_info vinfo = vinfo_for_stmt (gsi_stmt (gsi));
+ if (STMT_SLP_TYPE (vinfo) != pure_slp)
+ STMT_VINFO_VECTORIZABLE (vinfo) = false;
+ }
+
+ /* Analyze dependences. At this point all stmts not participating in
+ vectorization have to be marked. Dependence analysis assumes
+ that we either vectorize all SLP instances or none at all. */
+ if (!vect_slp_analyze_data_ref_dependences (bb_vinfo))
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "not vectorized: unhandled data dependence "
+ "in basic block.\n");
+
+ destroy_bb_vec_info (bb_vinfo);
+ return NULL;
+ }
+
if (!vect_verify_datarefs_alignment (NULL, bb_vinfo))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"not vectorized: unsupported alignment in basic "
"block.\n");
return NULL;
}
- if (!vect_slp_analyze_operations (bb_vinfo))
+ if (!vect_slp_analyze_operations (BB_VINFO_SLP_INSTANCES (bb_vinfo),
+ BB_VINFO_TARGET_COST_DATA (bb_vinfo)))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"not vectorized: bad operation in basic block.\n");
destroy_bb_vec_info (bb_vinfo);
}
/* Cost model: check if the vectorization is worthwhile. */
- if (flag_vect_cost_model
+ if (!unlimited_cost_model (NULL)
&& !vect_bb_vectorization_profitable_p (bb_vinfo))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"not vectorized: vectorization is not "
"profitable.\n");
return NULL;
}
- if (dump_kind_p (MSG_NOTE))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
"Basic block will be vectorized using SLP\n");
gimple_stmt_iterator gsi;
unsigned int vector_sizes;
- if (dump_kind_p (MSG_NOTE))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location, "===vect_slp_analyze_bb===\n");
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
if (insns > PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"not vectorized: too many instructions in "
"basic block.\n");
/* Try the next biggest vector size. */
current_vector_size = 1 << floor_log2 (vector_sizes);
- if (dump_kind_p (MSG_NOTE))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
"***** Re-trying analysis with "
"vector size %d\n", current_vector_size);
}
-/* 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 vect_model_xxx_cost are linear in ncopies. */
-
-void
-vect_update_slp_costs_according_to_vf (loop_vec_info loop_vinfo)
-{
- unsigned int i, j, vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
- VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
- slp_instance instance;
- stmt_vector_for_cost body_cost_vec;
- stmt_info_for_cost *si;
- void *data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
-
- if (dump_kind_p (MSG_NOTE))
- dump_printf_loc (MSG_NOTE, vect_location,
- "=== vect_update_slp_costs_according_to_vf ===");
-
- FOR_EACH_VEC_ELT (slp_instance, slp_instances, i, instance)
- {
- /* We assume that costs are linear in ncopies. */
- int ncopies = vf / SLP_INSTANCE_UNROLLING_FACTOR (instance);
-
- /* Record the instance's instructions in the target cost model.
- This was delayed until here because the count of instructions
- isn't known beforehand. */
- body_cost_vec = SLP_INSTANCE_BODY_COST_VEC (instance);
-
- FOR_EACH_VEC_ELT (stmt_info_for_cost, body_cost_vec, j, si)
- (void) add_stmt_cost (data, si->count * ncopies, si->kind,
- vinfo_for_stmt (si->stmt), si->misalign,
- vect_body);
- }
-}
-
-
/* 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 RHS of
static void
vect_get_constant_vectors (tree op, slp_tree slp_node,
- VEC (tree, heap) **vec_oprnds,
+ vec<tree> *vec_oprnds,
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);
+ vec<gimple> stmts = SLP_TREE_SCALAR_STMTS (slp_node);
+ gimple stmt = stmts[0];
stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
unsigned nunits;
tree vec_cst;
unsigned j, number_of_places_left_in_vector;
tree vector_type;
tree vop;
- int group_size = VEC_length (gimple, stmts);
+ int group_size = stmts.length ();
unsigned int vec_num, i;
unsigned number_of_copies = 1;
- VEC (tree, heap) *voprnds = VEC_alloc (tree, heap, number_of_vectors);
+ vec<tree> voprnds;
+ voprnds.create (number_of_vectors);
bool constant_p, is_store;
tree neutral_op = NULL;
enum tree_code code = gimple_expr_code (stmt);
struct loop *loop;
gimple_seq ctor_seq = NULL;
+ vector_type = get_vectype_for_scalar_type (TREE_TYPE (op));
+ nunits = TYPE_VECTOR_SUBPARTS (vector_type);
+
if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
&& reduc_index != -1)
{
- op_num = reduc_index - 1;
- op = gimple_op (stmt, reduc_index);
+ op_num = reduc_index;
+ 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. */
{
case WIDEN_SUM_EXPR:
case DOT_PROD_EXPR:
+ case SAD_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
case BIT_IOR_EXPR:
neutral_op = build_int_cst (TREE_TYPE (op), -1);
break;
- case MAX_EXPR:
- case MIN_EXPR:
- def_stmt = SSA_NAME_DEF_STMT (op);
- loop = (gimple_bb (stmt))->loop_father;
- neutral_op = PHI_ARG_DEF_FROM_EDGE (def_stmt,
- loop_preheader_edge (loop));
- break;
+ /* For MIN/MAX we don't have an easy neutral operand but
+ the initial values can be used fine here. Only for
+ a reduction chain we have to force a neutral element. */
+ case MAX_EXPR:
+ case MIN_EXPR:
+ if (!GROUP_FIRST_ELEMENT (stmt_vinfo))
+ neutral_op = NULL;
+ else
+ {
+ def_stmt = SSA_NAME_DEF_STMT (op);
+ loop = (gimple_bb (stmt))->loop_father;
+ neutral_op = PHI_ARG_DEF_FROM_EDGE (def_stmt,
+ loop_preheader_edge (loop));
+ }
+ break;
default:
+ gcc_assert (!GROUP_FIRST_ELEMENT (stmt_vinfo));
neutral_op = NULL;
}
}
else
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.
(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_copies = nunits * number_of_vectors / group_size;
number_of_places_left_in_vector = nunits;
elts = XALLOCAVEC (tree, nunits);
+ bool place_after_defs = false;
for (j = 0; j < number_of_copies; j++)
{
- for (i = group_size - 1; VEC_iterate (gimple, stmts, i, stmt); i--)
+ for (i = group_size - 1; stmts.iterate (i, &stmt); i--)
{
if (is_store)
op = gimple_assign_rhs1 (stmt);
the lhs, so make sure the scalar is the right type if
we are dealing with vectors of
long long/long/short/char. */
- if (op_num == 1 && constant_p)
+ if (op_num == 1 && TREE_CODE (op) == INTEGER_CST)
op = fold_convert (TREE_TYPE (vector_type), op);
break;
/* Create 'vect_ = {op0,op1,...,opn}'. */
number_of_places_left_in_vector--;
+ tree orig_op = op;
if (!types_compatible_p (TREE_TYPE (vector_type), TREE_TYPE (op)))
{
- if (constant_p)
+ if (CONSTANT_CLASS_P (op))
{
op = fold_unary (VIEW_CONVERT_EXPR,
TREE_TYPE (vector_type), op);
}
else
{
- tree new_temp
- = make_ssa_name (TREE_TYPE (vector_type), NULL);
+ tree new_temp = make_ssa_name (TREE_TYPE (vector_type));
gimple init_stmt;
- op = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (vector_type),
- op);
+ op = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (vector_type), op);
init_stmt
- = gimple_build_assign_with_ops (VIEW_CONVERT_EXPR,
- new_temp, op, NULL_TREE);
+ = gimple_build_assign (new_temp, VIEW_CONVERT_EXPR, op);
gimple_seq_add_stmt (&ctor_seq, init_stmt);
op = new_temp;
}
}
elts[number_of_places_left_in_vector] = op;
+ if (!CONSTANT_CLASS_P (op))
+ constant_p = false;
+ if (TREE_CODE (orig_op) == SSA_NAME
+ && !SSA_NAME_IS_DEFAULT_DEF (orig_op)
+ && STMT_VINFO_BB_VINFO (stmt_vinfo)
+ && (STMT_VINFO_BB_VINFO (stmt_vinfo)->bb
+ == gimple_bb (SSA_NAME_DEF_STMT (orig_op))))
+ place_after_defs = true;
if (number_of_places_left_in_vector == 0)
{
vec_cst = build_vector (vector_type, elts);
else
{
- VEC(constructor_elt,gc) *v;
+ vec<constructor_elt, va_gc> *v;
unsigned k;
- v = VEC_alloc (constructor_elt, gc, nunits);
+ vec_alloc (v, nunits);
for (k = 0; k < nunits; ++k)
CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, elts[k]);
vec_cst = build_constructor (vector_type, v);
}
- VEC_quick_push (tree, voprnds,
- vect_init_vector (stmt, vec_cst,
- vector_type, NULL));
+ tree init;
+ gimple_stmt_iterator gsi;
+ if (place_after_defs)
+ {
+ gsi = gsi_for_stmt
+ (vect_find_last_scalar_stmt_in_slp (slp_node));
+ init = vect_init_vector (stmt, vec_cst, vector_type, &gsi);
+ }
+ else
+ init = vect_init_vector (stmt, vec_cst, vector_type, NULL);
if (ctor_seq != NULL)
{
- gimple init_stmt
- = SSA_NAME_DEF_STMT (VEC_last (tree, voprnds));
- gimple_stmt_iterator gsi = gsi_for_stmt (init_stmt);
+ gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (init));
gsi_insert_seq_before_without_update (&gsi, ctor_seq,
GSI_SAME_STMT);
ctor_seq = NULL;
}
+ voprnds.quick_push (init);
+ place_after_defs = false;
}
}
}
/* Since the vectors are created in the reverse order, we should invert
them. */
- vec_num = VEC_length (tree, voprnds);
+ vec_num = voprnds.length ();
for (j = vec_num; j != 0; j--)
{
- vop = VEC_index (tree, voprnds, j - 1);
- VEC_quick_push (tree, *vec_oprnds, vop);
+ vop = voprnds[j - 1];
+ vec_oprnds->quick_push (vop);
}
- VEC_free (tree, heap, voprnds);
+ voprnds.release ();
/* 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
to replicate the vectors. */
- while (number_of_vectors > VEC_length (tree, *vec_oprnds))
+ while (number_of_vectors > vec_oprnds->length ())
{
tree neutral_vec = NULL;
if (!neutral_vec)
neutral_vec = build_vector_from_val (vector_type, neutral_op);
- VEC_quick_push (tree, *vec_oprnds, neutral_vec);
+ vec_oprnds->quick_push (neutral_vec);
}
else
{
- for (i = 0; VEC_iterate (tree, *vec_oprnds, i, vop) && i < vec_num; i++)
- VEC_quick_push (tree, *vec_oprnds, vop);
+ for (i = 0; vec_oprnds->iterate (i, &vop) && i < vec_num; i++)
+ vec_oprnds->quick_push (vop);
}
}
}
vectorized def-stmts. */
static void
-vect_get_slp_vect_defs (slp_tree slp_node, VEC (tree,heap) **vec_oprnds)
+vect_get_slp_vect_defs (slp_tree slp_node, vec<tree> *vec_oprnds)
{
tree vec_oprnd;
gimple vec_def_stmt;
unsigned int i;
- gcc_assert (SLP_TREE_VEC_STMTS (slp_node));
+ gcc_assert (SLP_TREE_VEC_STMTS (slp_node).exists ());
- FOR_EACH_VEC_ELT (gimple, SLP_TREE_VEC_STMTS (slp_node), i, vec_def_stmt)
+ FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (slp_node), i, vec_def_stmt)
{
gcc_assert (vec_def_stmt);
vec_oprnd = gimple_get_lhs (vec_def_stmt);
- VEC_quick_push (tree, *vec_oprnds, vec_oprnd);
+ vec_oprnds->quick_push (vec_oprnd);
}
}
vect_get_slp_vect_defs () to retrieve them. */
void
-vect_get_slp_defs (VEC (tree, heap) *ops, slp_tree slp_node,
- VEC (slp_void_p, heap) **vec_oprnds, int reduc_index)
+vect_get_slp_defs (vec<tree> ops, slp_tree slp_node,
+ vec<vec<tree> > *vec_oprnds, int reduc_index)
{
- gimple first_stmt, first_def;
+ gimple first_stmt;
int number_of_vects = 0, i;
unsigned int child_index = 0;
HOST_WIDE_INT lhs_size_unit, rhs_size_unit;
slp_tree child = NULL;
- VEC (tree, heap) *vec_defs;
- tree oprnd, def_lhs;
+ vec<tree> vec_defs;
+ tree oprnd;
bool vectorized_defs;
- first_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0);
- FOR_EACH_VEC_ELT (tree, ops, i, oprnd)
+ first_stmt = SLP_TREE_SCALAR_STMTS (slp_node)[0];
+ FOR_EACH_VEC_ELT (ops, i, oprnd)
{
/* For each operand we check if it has vectorized definitions in a child
node or we need to create them (for invariants and constants). We
vect_get_constant_vectors (), and not advance CHILD_INDEX in order
to check this child node for the next operand. */
vectorized_defs = false;
- if (VEC_length (slp_void_p, SLP_TREE_CHILDREN (slp_node)) > child_index)
+ if (SLP_TREE_CHILDREN (slp_node).length () > child_index)
{
- child = (slp_tree) VEC_index (slp_void_p,
- SLP_TREE_CHILDREN (slp_node),
- child_index);
- first_def = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (child), 0);
-
- /* In the end of a pattern sequence we have a use of the original stmt,
- so we need to compare OPRND with the original def. */
- if (is_pattern_stmt_p (vinfo_for_stmt (first_def))
- && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (first_stmt))
- && !is_pattern_stmt_p (vinfo_for_stmt (first_stmt)))
- first_def = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def));
-
- if (is_gimple_call (first_def))
- def_lhs = gimple_call_lhs (first_def);
- else
- def_lhs = gimple_assign_lhs (first_def);
+ child = SLP_TREE_CHILDREN (slp_node)[child_index];
- if (operand_equal_p (oprnd, def_lhs, 0))
- {
- /* The number of vector defs is determined by the number of
- vector statements in the node from which we get those
- statements. */
- number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (child);
- vectorized_defs = true;
- child_index++;
- }
+ /* We have to check both pattern and original def, if available. */
+ if (child)
+ {
+ gimple first_def = SLP_TREE_SCALAR_STMTS (child)[0];
+ gimple related
+ = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def));
+
+ if (operand_equal_p (oprnd, gimple_get_lhs (first_def), 0)
+ || (related
+ && operand_equal_p (oprnd, gimple_get_lhs (related), 0)))
+ {
+ /* The number of vector defs is determined by the number of
+ vector statements in the node from which we get those
+ statements. */
+ number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (child);
+ vectorized_defs = true;
+ child_index++;
+ }
+ }
+ else
+ child_index++;
}
if (!vectorized_defs)
}
/* Allocate memory for vectorized defs. */
- vec_defs = VEC_alloc (tree, heap, number_of_vects);
+ vec_defs = vNULL;
+ vec_defs.create (number_of_vects);
/* For reduction defs we call vect_get_constant_vectors (), since we are
looking for initial loop invariant values. */
if (vectorized_defs && reduc_index == -1)
/* The defs are already vectorized. */
- vect_get_slp_vect_defs (child, &vec_defs);
+ vect_get_slp_vect_defs (child, &vec_defs);
else
/* Build vectors from scalar defs. */
- vect_get_constant_vectors (oprnd, slp_node, &vec_defs, i,
+ vect_get_constant_vectors (oprnd, slp_node, &vec_defs, i,
number_of_vects, reduc_index);
- VEC_quick_push (slp_void_p, *vec_oprnds, (slp_void_p) vec_defs);
+ vec_oprnds->quick_push (vec_defs);
/* For reductions, we only need initial values. */
if (reduc_index != -1)
the created stmts must be inserted. */
static inline void
-vect_create_mask_and_perm (gimple stmt, gimple next_scalar_stmt,
+vect_create_mask_and_perm (gimple stmt,
tree mask, int first_vec_indx, int second_vec_indx,
gimple_stmt_iterator *gsi, slp_tree node,
- tree vectype, VEC(tree,heap) *dr_chain,
+ tree vectype, vec<tree> dr_chain,
int ncopies, int vect_stmts_counter)
{
tree perm_dest;
gimple perm_stmt = NULL;
- stmt_vec_info next_stmt_info;
int i, stride;
tree first_vec, second_vec, data_ref;
/* 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 = SLP_TREE_VEC_STMTS (node).length ();
i < (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node); i++)
- VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (node), NULL);
+ SLP_TREE_VEC_STMTS (node).quick_push (NULL);
perm_dest = vect_create_destination_var (gimple_assign_lhs (stmt), vectype);
for (i = 0; i < ncopies; i++)
{
- first_vec = VEC_index (tree, dr_chain, first_vec_indx);
- second_vec = VEC_index (tree, dr_chain, second_vec_indx);
+ first_vec = dr_chain[first_vec_indx];
+ second_vec = dr_chain[second_vec_indx];
/* Generate the permute statement. */
- perm_stmt = gimple_build_assign_with_ops (VEC_PERM_EXPR, perm_dest,
- first_vec, second_vec, mask);
+ perm_stmt = gimple_build_assign (perm_dest, VEC_PERM_EXPR,
+ first_vec, second_vec, mask);
data_ref = make_ssa_name (perm_dest, perm_stmt);
gimple_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),
- stride * i + vect_stmts_counter, perm_stmt);
+ SLP_TREE_VEC_STMTS (node)[stride * i + vect_stmts_counter] = perm_stmt;
first_vec_indx += stride;
second_vec_indx += stride;
}
-
- /* Mark the scalar stmt as vectorized. */
- next_stmt_info = vinfo_for_stmt (next_scalar_stmt);
- STMT_VINFO_VEC_STMT (next_stmt_info) = perm_stmt;
}
/* Adjust the value in case it's a mask for second and third vectors. */
*current_mask_element -= mask_nunits * (*number_of_mask_fixes - 1);
+ if (*current_mask_element < 0)
+ {
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "permutation requires past vector ");
+ dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
+ }
+ return false;
+ }
+
if (*current_mask_element < mask_nunits)
*needs_first_vector = true;
the next vector as well. */
if (only_one_vec && *current_mask_element >= mask_nunits)
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"permutation requires at least two vectors ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
return false;
}
/* The mask requires the next vector. */
- if (*current_mask_element >= mask_nunits * 2)
+ while (*current_mask_element >= mask_nunits * 2)
{
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
vectors. */
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"permutation requires at "
"least three vectors ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
return false;
/* Generate vector permute statements from a list of loads in DR_CHAIN.
If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
- permute statements for SLP_NODE_INSTANCE. */
+ permute statements for the SLP node NODE of the SLP instance
+ SLP_NODE_INSTANCE. */
+
bool
-vect_transform_slp_perm_load (gimple stmt, VEC (tree, heap) *dr_chain,
+vect_transform_slp_perm_load (slp_tree node, vec<tree> dr_chain,
gimple_stmt_iterator *gsi, int vf,
slp_instance slp_node_instance, bool analyze_only)
{
+ gimple stmt = SLP_TREE_SCALAR_STMTS (node)[0];
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
tree mask_element_type = NULL_TREE, mask_type;
- int i, j, k, nunits, vec_index = 0, scalar_index;
- slp_tree node;
+ int i, j, k, nunits, vec_index = 0;
tree vectype = STMT_VINFO_VECTYPE (stmt_info);
- gimple next_scalar_stmt;
int group_size = SLP_INSTANCE_GROUP_SIZE (slp_node_instance);
int first_mask_element;
int index, unroll_factor, current_mask_element, ncopies;
int number_of_mask_fixes = 1;
bool mask_fixed = false;
bool needs_first_vector = false;
- enum machine_mode mode;
+ machine_mode mode;
+
+ if (!STMT_VINFO_GROUPED_ACCESS (stmt_info))
+ return false;
+
+ stmt_info = vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info));
mode = TYPE_MODE (vectype);
if (!can_vec_perm_p (mode, false, NULL))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"no vect permute for ");
dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
}
return false;
}
/* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
unrolling factor. */
- orig_vec_stmts_num = group_size *
- SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance) / nunits;
+ orig_vec_stmts_num
+ = (STMT_VINFO_GROUP_SIZE (stmt_info)
+ * SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance)
+ + nunits - 1) / nunits;
if (orig_vec_stmts_num == 1)
only_one_vec = true;
we need the second and the third vectors: {b1,c1,a2,b2} and
{c2,a3,b3,c3}. */
- FOR_EACH_VEC_ELT (slp_tree, SLP_INSTANCE_LOADS (slp_node_instance), i, node)
- {
- scalar_index = 0;
+ {
index = 0;
vect_stmts_counter = 0;
vec_index = 0;
{
for (k = 0; k < group_size; k++)
{
- first_mask_element = i + j * group_size;
+ i = SLP_TREE_LOAD_PERMUTATION (node)[k];
+ first_mask_element = i + j * STMT_VINFO_GROUP_SIZE (stmt_info);
if (!vect_get_mask_element (stmt, first_mask_element, 0,
nunits, only_one_vec, index,
mask, ¤t_mask_element,
&number_of_mask_fixes, &mask_fixed,
&needs_first_vector))
return false;
+ gcc_assert (current_mask_element >= 0
+ && current_mask_element < 2 * nunits);
mask[index++] = current_mask_element;
if (index == nunits)
{
- tree mask_vec, *mask_elts;
- int l;
-
+ index = 0;
if (!can_vec_perm_p (mode, false, mask))
{
- if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_MISSED_OPTIMIZATION,
vect_location,
return false;
}
- mask_elts = XALLOCAVEC (tree, nunits);
- for (l = 0; l < nunits; ++l)
- mask_elts[l] = build_int_cst (mask_element_type, mask[l]);
- mask_vec = build_vector (mask_type, mask_elts);
- index = 0;
-
if (!analyze_only)
{
- if (need_next_vector)
+ int l;
+ tree mask_vec, *mask_elts;
+ mask_elts = XALLOCAVEC (tree, nunits);
+ for (l = 0; l < nunits; ++l)
+ mask_elts[l] = build_int_cst (mask_element_type,
+ mask[l]);
+ mask_vec = build_vector (mask_type, mask_elts);
+
+ if (need_next_vector)
{
first_vec_index = second_vec_index;
second_vec_index = vec_index;
}
- next_scalar_stmt = VEC_index (gimple,
- SLP_TREE_SCALAR_STMTS (node), scalar_index++);
-
- vect_create_mask_and_perm (stmt, next_scalar_stmt,
+ vect_create_mask_and_perm (stmt,
mask_vec, first_vec_index, second_vec_index,
gsi, node, vectype, dr_chain,
ncopies, vect_stmts_counter++);
unsigned int vec_stmts_size, nunits, group_size;
tree vectype;
int i;
- slp_tree loads_node;
- slp_void_p child;
+ slp_tree child;
if (!node)
return false;
- FOR_EACH_VEC_ELT (slp_void_p, SLP_TREE_CHILDREN (node), i, child)
- vect_schedule_slp_instance ((slp_tree) child, instance,
- vectorization_factor);
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ vect_schedule_slp_instance (child, instance, vectorization_factor);
- stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
+ stmt = SLP_TREE_SCALAR_STMTS (node)[0];
stmt_info = vinfo_for_stmt (stmt);
/* VECTYPE is the type of the destination. */
for the scalar stmts in each node of the SLP tree. Number of vector
elements in one vector iteration is the number of scalar elements in
one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
- size. */
- vec_stmts_size = (vectorization_factor * group_size) / nunits;
-
- /* In case of load permutation we have to allocate vectorized statements for
- all the nodes that participate in that permutation. */
- if (SLP_INSTANCE_LOAD_PERMUTATION (instance))
- {
- FOR_EACH_VEC_ELT (slp_tree, SLP_INSTANCE_LOADS (instance), i, loads_node)
- {
- if (!SLP_TREE_VEC_STMTS (loads_node))
- {
- SLP_TREE_VEC_STMTS (loads_node) = VEC_alloc (gimple, heap,
- vec_stmts_size);
- SLP_TREE_NUMBER_OF_VEC_STMTS (loads_node) = vec_stmts_size;
- }
- }
- }
+ size.
+ Unless this is a SLP reduction in which case the number of vector
+ stmts is equal to the number of vector stmts of the children. */
+ if (GROUP_FIRST_ELEMENT (stmt_info)
+ && !STMT_VINFO_GROUPED_ACCESS (stmt_info))
+ vec_stmts_size = SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_CHILDREN (node)[0]);
+ else
+ vec_stmts_size = (vectorization_factor * group_size) / nunits;
- if (!SLP_TREE_VEC_STMTS (node))
+ if (!SLP_TREE_VEC_STMTS (node).exists ())
{
- SLP_TREE_VEC_STMTS (node) = VEC_alloc (gimple, heap, vec_stmts_size);
+ SLP_TREE_VEC_STMTS (node).create (vec_stmts_size);
SLP_TREE_NUMBER_OF_VEC_STMTS (node) = vec_stmts_size;
}
- if (dump_kind_p (MSG_NOTE))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_NOTE,vect_location,
"------>vectorizing SLP node starting from: ");
dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_NOTE, "\n");
}
- /* Loads should be inserted before the first load. */
- if (SLP_INSTANCE_FIRST_LOAD_STMT (instance)
- && STMT_VINFO_GROUPED_ACCESS (stmt_info)
- && !REFERENCE_CLASS_P (gimple_get_lhs (stmt))
- && SLP_INSTANCE_LOAD_PERMUTATION (instance))
- si = gsi_for_stmt (SLP_INSTANCE_FIRST_LOAD_STMT (instance));
- else if (is_pattern_stmt_p (stmt_info))
- si = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info));
- else
- si = gsi_for_stmt (stmt);
-
- /* Stores should be inserted just before the last store. */
- if (STMT_VINFO_GROUPED_ACCESS (stmt_info)
- && REFERENCE_CLASS_P (gimple_get_lhs (stmt)))
- {
- gimple last_store = vect_find_last_store_in_slp_instance (instance);
- if (is_pattern_stmt_p (vinfo_for_stmt (last_store)))
- last_store = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (last_store));
- si = gsi_for_stmt (last_store);
- }
+ /* Vectorized stmts go before the last scalar stmt which is where
+ all uses are ready. */
+ si = gsi_for_stmt (vect_find_last_scalar_stmt_in_slp (node));
/* Mark the first element of the reduction chain as reduction to properly
transform the node. In the analysis phase only the last element of the
STMT_VINFO_TYPE (stmt_info) = reduc_vec_info_type;
}
+ /* Handle two-operation SLP nodes by vectorizing the group with
+ both operations and then performing a merge. */
+ if (SLP_TREE_TWO_OPERATORS (node))
+ {
+ enum tree_code code0 = gimple_assign_rhs_code (stmt);
+ enum tree_code ocode;
+ gimple ostmt;
+ unsigned char *mask = XALLOCAVEC (unsigned char, group_size);
+ bool allsame = true;
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, ostmt)
+ if (gimple_assign_rhs_code (ostmt) != code0)
+ {
+ mask[i] = 1;
+ allsame = false;
+ ocode = gimple_assign_rhs_code (ostmt);
+ }
+ else
+ mask[i] = 0;
+ if (!allsame)
+ {
+ vec<gimple> v0;
+ vec<gimple> v1;
+ unsigned j;
+ tree tmask = NULL_TREE;
+ vect_transform_stmt (stmt, &si, &grouped_store, 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, &si, &grouped_store, 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 (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)
+ {
+ tree *melts = XALLOCAVEC (tree, TYPE_VECTOR_SUBPARTS (vectype));
+ for (l = 0; l < TYPE_VECTOR_SUBPARTS (vectype); ++l)
+ {
+ if (k >= group_size)
+ k = 0;
+ melts[l] = build_int_cst
+ (meltype, mask[k++] * TYPE_VECTOR_SUBPARTS (vectype) + l);
+ }
+ tmask = build_vector (mvectype, melts);
+
+ /* ??? 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]),
+ gimple_assign_lhs (v1[j]), tmask);
+ vect_finish_stmt_generation (stmt, vstmt, &si);
+ SLP_TREE_VEC_STMTS (node).quick_push (vstmt);
+ }
+ v0.release ();
+ v1.release ();
+ return false;
+ }
+ }
is_store = vect_transform_stmt (stmt, &si, &grouped_store, node, instance);
return is_store;
}
gimple stmt, new_stmt;
gimple_stmt_iterator gsi;
int i;
- slp_void_p child;
+ slp_tree child;
tree lhs;
stmt_vec_info stmt_info;
if (!node)
return;
- FOR_EACH_VEC_ELT (slp_void_p, SLP_TREE_CHILDREN (node), i, child)
- vect_remove_slp_scalar_calls ((slp_tree) child);
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ vect_remove_slp_scalar_calls (child);
- FOR_EACH_VEC_ELT (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt)
+ FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
{
if (!is_gimple_call (stmt) || gimple_bb (stmt) == NULL)
continue;
bool
vect_schedule_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
{
- VEC (slp_instance, heap) *slp_instances;
+ vec<slp_instance> slp_instances;
slp_instance instance;
unsigned int i, vf;
bool is_store = false;
vf = 1;
}
- FOR_EACH_VEC_ELT (slp_instance, slp_instances, i, instance)
+ FOR_EACH_VEC_ELT (slp_instances, i, instance)
{
/* Schedule the tree of INSTANCE. */
is_store = vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance),
instance, vf);
- if (dump_kind_p (MSG_NOTE))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
- "vectorizing stmts using SLP.");
+ "vectorizing stmts using SLP.\n");
}
- FOR_EACH_VEC_ELT (slp_instance, slp_instances, i, instance)
+ FOR_EACH_VEC_ELT (slp_instances, i, instance)
{
slp_tree root = SLP_INSTANCE_TREE (instance);
gimple store;
unsigned int j;
gimple_stmt_iterator gsi;
- vect_remove_slp_scalar_calls (root);
+ /* Remove scalar call stmts. Do not do this for basic-block
+ vectorization as not all uses may be vectorized.
+ ??? Why should this be necessary? DCE should be able to
+ remove the stmts itself.
+ ??? For BB vectorization we can as well remove scalar
+ stmts starting from the SLP tree root if they have no
+ uses. */
+ if (loop_vinfo)
+ vect_remove_slp_scalar_calls (root);
- for (j = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (root), j, store)
+ for (j = 0; SLP_TREE_SCALAR_STMTS (root).iterate (j, &store)
&& j < SLP_INSTANCE_GROUP_SIZE (instance); j++)
{
if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store)))
gcc_assert (bb_vinfo);
- if (dump_kind_p (MSG_NOTE))
+ if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location, "SLPing BB\n");
for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
gimple stmt = gsi_stmt (si);
stmt_vec_info stmt_info;
- if (dump_kind_p (MSG_NOTE))
+ if (dump_enabled_p ())
{
dump_printf_loc (MSG_NOTE, vect_location,
"------>SLPing statement: ");
dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
+ dump_printf (MSG_NOTE, "\n");
}
stmt_info = vinfo_for_stmt (stmt);
}
}
- if (dump_kind_p (MSG_OPTIMIZED_LOCATIONS))
- dump_printf (MSG_OPTIMIZED_LOCATIONS, "BASIC BLOCK VECTORIZED\n");
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "BASIC BLOCK VECTORIZED\n");
destroy_bb_vec_info (bb_vinfo);
}
projects / gcc.git / blobdiff