#include "tm.h"
#include "ggc.h"
#include "tree.h"
+#include "stor-layout.h"
#include "target.h"
#include "basic-block.h"
#include "gimple-pretty-print.h"
-#include "tree-flow.h"
+#include "gimple.h"
+#include "gimplify.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 "cfgloop.h"
#include "expr.h"
#include "optabs.h"
tree *);
static gimple vect_recog_widen_shift_pattern (vec<gimple> *,
tree *, tree *);
+static gimple vect_recog_rotate_pattern (vec<gimple> *, tree *, tree *);
static gimple vect_recog_vector_vector_shift_pattern (vec<gimple> *,
tree *, tree *);
static gimple vect_recog_divmod_pattern (vec<gimple> *,
vect_recog_pow_pattern,
vect_recog_widen_shift_pattern,
vect_recog_over_widening_pattern,
+ vect_recog_rotate_pattern,
vect_recog_vector_vector_shift_pattern,
vect_recog_divmod_pattern,
vect_recog_mixed_size_cond_pattern,
|| !promotion)
return NULL;
oprnd00 = gimple_assign_rhs1 (def_stmt);
- if (!type_conversion_p (oprnd0, stmt, true, &half_type1, &def_stmt,
+ if (!type_conversion_p (oprnd1, stmt, true, &half_type1, &def_stmt,
&promotion)
|| !promotion)
return NULL;
dump_printf_loc (MSG_NOTE, vect_location,
"vect_recog_dot_prod_pattern: detected: ");
dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
+ dump_printf (MSG_NOTE, "\n");
}
/* We don't allow changing the order of the computation in the inner-loop
&& vect_handle_widen_op_by_const (last_stmt, MULT_EXPR, oprnd1,
&oprnd0, stmts, type,
&half_type0, def_stmt0))
- half_type1 = half_type0;
+ {
+ half_type1 = half_type0;
+ oprnd1 = fold_convert (half_type1, oprnd1);
+ }
else
return NULL;
}
/* Pattern detected. */
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
- "vect_recog_widen_mult_pattern: detected: ");
+ "vect_recog_widen_mult_pattern: detected:\n");
/* Check target support */
vectype = get_vectype_for_scalar_type (half_type0);
*type_out = NULL_TREE;
/* Catch squaring. */
- if ((host_integerp (exp, 0)
- && tree_low_cst (exp, 0) == 2)
+ if ((tree_fits_shwi_p (exp)
+ && tree_to_shwi (exp) == 2)
|| (TREE_CODE (exp) == REAL_CST
&& REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconst2)))
{
dump_printf_loc (MSG_NOTE, vect_location,
"vect_recog_widen_sum_pattern: detected: ");
dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
+ dump_printf (MSG_NOTE, "\n");
}
/* We don't allow changing the order of the computation in the inner-loop
dump_printf_loc (MSG_NOTE, vect_location,
"created pattern stmt: ");
dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
+ dump_printf (MSG_NOTE, "\n");
}
type = gimple_expr_type (stmt);
dump_printf_loc (MSG_NOTE, vect_location,
"vect_recog_over_widening_pattern: detected: ");
dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
+ dump_printf (MSG_NOTE, "\n");
}
return pattern_stmt;
/* Pattern detected. */
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
- "vect_recog_widen_shift_pattern: detected: ");
+ "vect_recog_widen_shift_pattern: detected:\n");
/* Check target support. */
vectype = get_vectype_for_scalar_type (half_type0);
return pattern_stmt;
}
+/* Detect a rotate pattern wouldn't be otherwise vectorized:
+
+ type a_t, b_t, c_t;
+
+ S0 a_t = b_t r<< c_t;
+
+ Input/Output:
+
+ * STMTS: Contains a stmt from which the pattern search begins,
+ i.e. the shift/rotate stmt. The original stmt (S0) is replaced
+ with a sequence:
+
+ S1 d_t = -c_t;
+ S2 e_t = d_t & (B - 1);
+ S3 f_t = b_t << c_t;
+ S4 g_t = b_t >> e_t;
+ S0 a_t = f_t | g_t;
+
+ where B is element bitsize of type.
+
+ Output:
+
+ * TYPE_IN: The type of the input arguments to the pattern.
+
+ * TYPE_OUT: The type of the output of this pattern.
+
+ * Return value: A new stmt that will be used to replace the rotate
+ S0 stmt. */
+
+static gimple
+vect_recog_rotate_pattern (vec<gimple> *stmts, tree *type_in, tree *type_out)
+{
+ gimple last_stmt = stmts->pop ();
+ tree oprnd0, oprnd1, lhs, var, var1, var2, vectype, type, stype, def, def2;
+ gimple pattern_stmt, def_stmt;
+ enum tree_code rhs_code;
+ stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
+ loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
+ bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_vinfo);
+ enum vect_def_type dt;
+ optab optab1, optab2;
+ edge ext_def = NULL;
+
+ if (!is_gimple_assign (last_stmt))
+ return NULL;
+
+ rhs_code = gimple_assign_rhs_code (last_stmt);
+ switch (rhs_code)
+ {
+ case LROTATE_EXPR:
+ case RROTATE_EXPR:
+ break;
+ default:
+ return NULL;
+ }
+
+ if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
+ return NULL;
+
+ lhs = gimple_assign_lhs (last_stmt);
+ oprnd0 = gimple_assign_rhs1 (last_stmt);
+ type = TREE_TYPE (oprnd0);
+ oprnd1 = gimple_assign_rhs2 (last_stmt);
+ if (TREE_CODE (oprnd0) != SSA_NAME
+ || TYPE_PRECISION (TREE_TYPE (lhs)) != TYPE_PRECISION (type)
+ || !INTEGRAL_TYPE_P (type)
+ || !TYPE_UNSIGNED (type))
+ return NULL;
+
+ if (!vect_is_simple_use (oprnd1, last_stmt, loop_vinfo, bb_vinfo, &def_stmt,
+ &def, &dt))
+ return NULL;
+
+ if (dt != vect_internal_def
+ && dt != vect_constant_def
+ && dt != vect_external_def)
+ return NULL;
+
+ vectype = get_vectype_for_scalar_type (type);
+ if (vectype == NULL_TREE)
+ return NULL;
+
+ /* If vector/vector or vector/scalar rotate is supported by the target,
+ don't do anything here. */
+ optab1 = optab_for_tree_code (rhs_code, vectype, optab_vector);
+ if (optab1
+ && optab_handler (optab1, TYPE_MODE (vectype)) != CODE_FOR_nothing)
+ return NULL;
+
+ if (bb_vinfo != NULL || dt != vect_internal_def)
+ {
+ optab2 = optab_for_tree_code (rhs_code, vectype, optab_scalar);
+ if (optab2
+ && optab_handler (optab2, TYPE_MODE (vectype)) != CODE_FOR_nothing)
+ return NULL;
+ }
+
+ /* If vector/vector or vector/scalar shifts aren't supported by the target,
+ don't do anything here either. */
+ optab1 = optab_for_tree_code (LSHIFT_EXPR, vectype, optab_vector);
+ optab2 = optab_for_tree_code (RSHIFT_EXPR, vectype, optab_vector);
+ if (!optab1
+ || optab_handler (optab1, TYPE_MODE (vectype)) == CODE_FOR_nothing
+ || !optab2
+ || optab_handler (optab2, TYPE_MODE (vectype)) == CODE_FOR_nothing)
+ {
+ if (bb_vinfo == NULL && dt == vect_internal_def)
+ return NULL;
+ optab1 = optab_for_tree_code (LSHIFT_EXPR, vectype, optab_scalar);
+ optab2 = optab_for_tree_code (RSHIFT_EXPR, vectype, optab_scalar);
+ if (!optab1
+ || optab_handler (optab1, TYPE_MODE (vectype)) == CODE_FOR_nothing
+ || !optab2
+ || optab_handler (optab2, TYPE_MODE (vectype)) == CODE_FOR_nothing)
+ return NULL;
+ }
+
+ *type_in = vectype;
+ *type_out = vectype;
+ if (*type_in == NULL_TREE)
+ return NULL;
+
+ if (dt == vect_external_def
+ && TREE_CODE (oprnd1) == SSA_NAME
+ && loop_vinfo)
+ {
+ struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
+ ext_def = loop_preheader_edge (loop);
+ if (!SSA_NAME_IS_DEFAULT_DEF (oprnd1))
+ {
+ basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (oprnd1));
+ if (bb == NULL
+ || !dominated_by_p (CDI_DOMINATORS, ext_def->dest, bb))
+ ext_def = NULL;
+ }
+ }
+
+ def = NULL_TREE;
+ if (TREE_CODE (oprnd1) == INTEGER_CST
+ || TYPE_MODE (TREE_TYPE (oprnd1)) == TYPE_MODE (type))
+ def = oprnd1;
+ else if (def_stmt && gimple_assign_cast_p (def_stmt))
+ {
+ tree rhs1 = gimple_assign_rhs1 (def_stmt);
+ if (TYPE_MODE (TREE_TYPE (rhs1)) == TYPE_MODE (type)
+ && TYPE_PRECISION (TREE_TYPE (rhs1))
+ == TYPE_PRECISION (type))
+ def = rhs1;
+ }
+
+ STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
+ if (def == NULL_TREE)
+ {
+ def = vect_recog_temp_ssa_var (type, NULL);
+ def_stmt = gimple_build_assign_with_ops (NOP_EXPR, def, oprnd1,
+ NULL_TREE);
+ if (ext_def)
+ {
+ basic_block new_bb
+ = gsi_insert_on_edge_immediate (ext_def, def_stmt);
+ gcc_assert (!new_bb);
+ }
+ else
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+ }
+ stype = TREE_TYPE (def);
+
+ if (TREE_CODE (def) == INTEGER_CST)
+ {
+ if (!tree_fits_uhwi_p (def)
+ || tree_to_uhwi (def) >= GET_MODE_PRECISION (TYPE_MODE (type))
+ || integer_zerop (def))
+ return NULL;
+ def2 = build_int_cst (stype,
+ GET_MODE_PRECISION (TYPE_MODE (type))
+ - tree_to_uhwi (def));
+ }
+ else
+ {
+ tree vecstype = get_vectype_for_scalar_type (stype);
+ stmt_vec_info def_stmt_vinfo;
+
+ if (vecstype == NULL_TREE)
+ return NULL;
+ def2 = vect_recog_temp_ssa_var (stype, NULL);
+ def_stmt = gimple_build_assign_with_ops (NEGATE_EXPR, def2, def,
+ NULL_TREE);
+ if (ext_def)
+ {
+ basic_block new_bb
+ = gsi_insert_on_edge_immediate (ext_def, def_stmt);
+ gcc_assert (!new_bb);
+ }
+ else
+ {
+ def_stmt_vinfo = new_stmt_vec_info (def_stmt, loop_vinfo, bb_vinfo);
+ set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
+ STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecstype;
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+ }
+
+ def2 = vect_recog_temp_ssa_var (stype, NULL);
+ tree mask
+ = build_int_cst (stype, GET_MODE_PRECISION (TYPE_MODE (stype)) - 1);
+ def_stmt = gimple_build_assign_with_ops (BIT_AND_EXPR, def2,
+ gimple_assign_lhs (def_stmt),
+ mask);
+ if (ext_def)
+ {
+ basic_block new_bb
+ = gsi_insert_on_edge_immediate (ext_def, def_stmt);
+ gcc_assert (!new_bb);
+ }
+ else
+ {
+ def_stmt_vinfo = new_stmt_vec_info (def_stmt, loop_vinfo, bb_vinfo);
+ set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
+ STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecstype;
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+ }
+ }
+
+ var1 = vect_recog_temp_ssa_var (type, NULL);
+ def_stmt = gimple_build_assign_with_ops (rhs_code == LROTATE_EXPR
+ ? LSHIFT_EXPR : RSHIFT_EXPR,
+ var1, oprnd0, def);
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+
+ var2 = vect_recog_temp_ssa_var (type, NULL);
+ def_stmt = gimple_build_assign_with_ops (rhs_code == LROTATE_EXPR
+ ? RSHIFT_EXPR : LSHIFT_EXPR,
+ var2, oprnd0, def2);
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+
+ /* Pattern detected. */
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "vect_recog_rotate_pattern: detected:\n");
+
+ /* Pattern supported. Create a stmt to be used to replace the pattern. */
+ var = vect_recog_temp_ssa_var (type, NULL);
+ pattern_stmt = gimple_build_assign_with_ops (BIT_IOR_EXPR, var, var1, var2);
+
+ if (dump_enabled_p ())
+ dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0);
+
+ stmts->safe_push (last_stmt);
+ return pattern_stmt;
+}
+
/* Detect a vector by vector shift pattern that wouldn't be otherwise
vectorized:
/* Pattern detected. */
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
- "vect_recog_vector_vector_shift_pattern: detected: ");
+ "vect_recog_vector_vector_shift_pattern: detected:\n");
/* Pattern supported. Create a stmt to be used to replace the pattern. */
var = vect_recog_temp_ssa_var (TREE_TYPE (oprnd0), NULL);
/* Pattern detected. */
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
- "vect_recog_divmod_pattern: detected: ");
+ "vect_recog_divmod_pattern: detected:\n");
cond = build2 (LT_EXPR, boolean_type_node, oprnd0,
build_int_cst (itype, 0));
return pattern_stmt;
}
- if (!host_integerp (oprnd1, TYPE_UNSIGNED (itype))
- || integer_zerop (oprnd1)
- || prec > HOST_BITS_PER_WIDE_INT)
+ if (prec > HOST_BITS_PER_WIDE_INT
+ || integer_zerop (oprnd1))
return NULL;
if (!can_mult_highpart_p (TYPE_MODE (vectype), TYPE_UNSIGNED (itype)))
{
unsigned HOST_WIDE_INT mh, ml;
int pre_shift, post_shift;
- unsigned HOST_WIDE_INT d = tree_low_cst (oprnd1, 1)
- & GET_MODE_MASK (TYPE_MODE (itype));
+ unsigned HOST_WIDE_INT d = (TREE_INT_CST_LOW (oprnd1)
+ & GET_MODE_MASK (TYPE_MODE (itype)));
tree t1, t2, t3, t4;
if (d >= ((unsigned HOST_WIDE_INT) 1 << (prec - 1)))
{
unsigned HOST_WIDE_INT ml;
int post_shift;
- HOST_WIDE_INT d = tree_low_cst (oprnd1, 0);
+ HOST_WIDE_INT d = TREE_INT_CST_LOW (oprnd1);
unsigned HOST_WIDE_INT abs_d;
bool add = false;
tree t1, t2, t3, t4;
if (post_shift >= prec)
return NULL;
- /* t1 = oprnd1 h* ml; */
+ /* t1 = oprnd0 h* ml; */
t1 = vect_recog_temp_ssa_var (itype, NULL);
def_stmt
= gimple_build_assign_with_ops (MULT_HIGHPART_EXPR, t1, oprnd0,
build_int_cst (itype, ml));
- append_pattern_def_seq (stmt_vinfo, def_stmt);
if (add)
{
/* t2 = t1 + oprnd0; */
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
t2 = vect_recog_temp_ssa_var (itype, NULL);
def_stmt
= gimple_build_assign_with_ops (PLUS_EXPR, t2, t1, oprnd0);
- append_pattern_def_seq (stmt_vinfo, def_stmt);
}
else
t2 = t1;
if (post_shift)
{
/* t3 = t2 >> post_shift; */
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
t3 = vect_recog_temp_ssa_var (itype, NULL);
def_stmt
= gimple_build_assign_with_ops (RSHIFT_EXPR, t3, t2,
build_int_cst (itype, post_shift));
- append_pattern_def_seq (stmt_vinfo, def_stmt);
}
else
t3 = t2;
- /* t4 = oprnd0 >> (prec - 1); */
- t4 = vect_recog_temp_ssa_var (itype, NULL);
- def_stmt
- = gimple_build_assign_with_ops (RSHIFT_EXPR, t4, oprnd0,
- build_int_cst (itype, prec - 1));
- append_pattern_def_seq (stmt_vinfo, def_stmt);
+ widest_int oprnd0_min, oprnd0_max;
+ int msb = 1;
+ if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max) == VR_RANGE)
+ {
+ if (!wi::neg_p (oprnd0_min))
+ msb = 0;
+ else if (wi::neg_p (oprnd0_max))
+ msb = -1;
+ }
- /* q = t3 - t4; or q = t4 - t3; */
- q = vect_recog_temp_ssa_var (itype, NULL);
- pattern_stmt
- = gimple_build_assign_with_ops (MINUS_EXPR, q, d < 0 ? t4 : t3,
- d < 0 ? t3 : t4);
+ if (msb == 0 && d >= 0)
+ {
+ /* q = t3; */
+ q = t3;
+ pattern_stmt = def_stmt;
+ }
+ else
+ {
+ /* t4 = oprnd0 >> (prec - 1);
+ or if we know from VRP that oprnd0 >= 0
+ t4 = 0;
+ or if we know from VRP that oprnd0 < 0
+ t4 = -1; */
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+ t4 = vect_recog_temp_ssa_var (itype, NULL);
+ if (msb != 1)
+ def_stmt
+ = gimple_build_assign_with_ops (INTEGER_CST,
+ t4, build_int_cst (itype, msb),
+ NULL_TREE);
+ else
+ def_stmt
+ = gimple_build_assign_with_ops (RSHIFT_EXPR, t4, oprnd0,
+ build_int_cst (itype, prec - 1));
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+
+ /* q = t3 - t4; or q = t4 - t3; */
+ q = vect_recog_temp_ssa_var (itype, NULL);
+ pattern_stmt
+ = gimple_build_assign_with_ops (MINUS_EXPR, q, d < 0 ? t4 : t3,
+ d < 0 ? t3 : t4);
+ }
}
if (rhs_code == TRUNC_MOD_EXPR)
dump_printf_loc (MSG_NOTE, vect_location,
"vect_recog_divmod_pattern: detected: ");
dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
+ dump_printf (MSG_NOTE, "\n");
}
stmts->safe_push (last_stmt);
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
- "vect_recog_mixed_size_cond_pattern: detected: ");
+ "vect_recog_mixed_size_cond_pattern: detected:\n");
return pattern_stmt;
}
stmts->safe_push (last_stmt);
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
- "vect_recog_bool_pattern: detected: ");
+ "vect_recog_bool_pattern: detected:\n");
return pattern_stmt;
}
stmts->safe_push (last_stmt);
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
- "vect_recog_bool_pattern: detected: ");
+ "vect_recog_bool_pattern: detected:\n");
return pattern_stmt;
}
else
dump_printf_loc (MSG_NOTE, vect_location,
"pattern recognized: ");
dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
+ dump_printf (MSG_NOTE, "\n");
}
/* Mark the stmts that are involved in the pattern. */
dump_printf_loc (MSG_NOTE, vect_location,
"additional pattern stmt: ");
dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
+ dump_printf (MSG_NOTE, "\n");
}
vect_mark_pattern_stmts (stmt, pattern_stmt, NULL_TREE);
gimple_stmt_iterator si;
unsigned int i, j;
vect_recog_func_ptr vect_recog_func;
- vec<gimple> stmts_to_replace;
- stmts_to_replace.create (1);
+ stack_vec<gimple, 1> stmts_to_replace;
gimple stmt;
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
- "=== vect_pattern_recog ===");
+ "=== vect_pattern_recog ===\n");
if (loop_vinfo)
{
}
}
}
-
- stmts_to_replace.release ();
}