/* Analysis Utilities for Loop Vectorization.
- Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
- Free Software Foundation, Inc.
+ Copyright (C) 2006-2013 Free Software Foundation, Inc.
Contributed by Dorit Nuzman <dorit@il.ibm.com>
This file is part of GCC.
#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 "tree-dump.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"
#include "params.h"
#include "tree-data-ref.h"
#include "tree-vectorizer.h"
-#include "recog.h"
+#include "recog.h" /* FIXME: for insn_data */
#include "diagnostic-core.h"
+#include "dumpfile.h"
/* Pattern recognition functions */
-static gimple vect_recog_widen_sum_pattern (VEC (gimple, heap) **, tree *,
+static gimple vect_recog_widen_sum_pattern (vec<gimple> *, tree *,
tree *);
-static gimple vect_recog_widen_mult_pattern (VEC (gimple, heap) **, tree *,
+static gimple vect_recog_widen_mult_pattern (vec<gimple> *, tree *,
tree *);
-static gimple vect_recog_dot_prod_pattern (VEC (gimple, heap) **, tree *,
+static gimple vect_recog_dot_prod_pattern (vec<gimple> *, tree *,
tree *);
-static gimple vect_recog_pow_pattern (VEC (gimple, heap) **, tree *, tree *);
-static gimple vect_recog_over_widening_pattern (VEC (gimple, heap) **, tree *,
+static gimple vect_recog_pow_pattern (vec<gimple> *, tree *, tree *);
+static gimple vect_recog_over_widening_pattern (vec<gimple> *, tree *,
tree *);
-static gimple vect_recog_widen_shift_pattern (VEC (gimple, heap) **,
+static gimple vect_recog_widen_shift_pattern (vec<gimple> *,
tree *, tree *);
-static gimple vect_recog_vector_vector_shift_pattern (VEC (gimple, heap) **,
+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_sdivmod_pow2_pattern (VEC (gimple, heap) **,
- tree *, tree *);
-static gimple vect_recog_mixed_size_cond_pattern (VEC (gimple, heap) **,
+static gimple vect_recog_divmod_pattern (vec<gimple> *,
+ tree *, tree *);
+static gimple vect_recog_mixed_size_cond_pattern (vec<gimple> *,
tree *, tree *);
-static gimple vect_recog_bool_pattern (VEC (gimple, heap) **, tree *, tree *);
+static gimple vect_recog_bool_pattern (vec<gimple> *, tree *, tree *);
static vect_recog_func_ptr vect_vect_recog_func_ptrs[NUM_PATTERNS] = {
vect_recog_widen_mult_pattern,
vect_recog_widen_sum_pattern,
vect_recog_dot_prod_pattern,
vect_recog_pow_pattern,
- vect_recog_over_widening_pattern,
vect_recog_widen_shift_pattern,
+ vect_recog_over_widening_pattern,
+ vect_recog_rotate_pattern,
vect_recog_vector_vector_shift_pattern,
- vect_recog_sdivmod_pow2_pattern,
+ vect_recog_divmod_pattern,
vect_recog_mixed_size_cond_pattern,
vect_recog_bool_pattern};
append_pattern_def_seq (stmt_info, stmt);
}
-/* Function widened_name_p
+/* Check whether STMT2 is in the same loop or basic block as STMT1.
+ Which of the two applies depends on whether we're currently doing
+ loop-based or basic-block-based vectorization, as determined by
+ the vinfo_for_stmt for STMT1 (which must be defined).
+
+ If this returns true, vinfo_for_stmt for STMT2 is guaranteed
+ to be defined as well. */
+
+static bool
+vect_same_loop_or_bb_p (gimple stmt1, gimple stmt2)
+{
+ stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt1);
+ loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
+ bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_vinfo);
+
+ if (!gimple_bb (stmt2))
+ return false;
+
+ if (loop_vinfo)
+ {
+ struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
+ if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt2)))
+ return false;
+ }
+ else
+ {
+ if (gimple_bb (stmt2) != BB_VINFO_BB (bb_vinfo)
+ || gimple_code (stmt2) == GIMPLE_PHI)
+ return false;
+ }
+
+ gcc_assert (vinfo_for_stmt (stmt2));
+ return true;
+}
+
+/* If the LHS of DEF_STMT has a single use, and that statement is
+ in the same loop or basic block, return it. */
+
+static gimple
+vect_single_imm_use (gimple def_stmt)
+{
+ tree lhs = gimple_assign_lhs (def_stmt);
+ use_operand_p use_p;
+ gimple use_stmt;
+
+ if (!single_imm_use (lhs, &use_p, &use_stmt))
+ return NULL;
+
+ if (!vect_same_loop_or_bb_p (def_stmt, use_stmt))
+ return NULL;
+
+ return use_stmt;
+}
- Check whether NAME, an ssa-name used in USE_STMT,
- is a result of a type-promotion, such that:
+/* Check whether NAME, an ssa-name used in USE_STMT,
+ is a result of a type promotion or demotion, such that:
DEF_STMT: NAME = NOP (name0)
- where the type of name0 (HALF_TYPE) is smaller than the type of NAME.
+ where the type of name0 (ORIG_TYPE) is smaller/bigger than the type of NAME.
If CHECK_SIGN is TRUE, check that either both types are signed or both are
unsigned. */
static bool
-widened_name_p (tree name, gimple use_stmt, tree *half_type, gimple *def_stmt,
- bool check_sign)
+type_conversion_p (tree name, gimple use_stmt, bool check_sign,
+ tree *orig_type, gimple *def_stmt, bool *promotion)
{
tree dummy;
gimple dummy_gimple;
tree oprnd0;
enum vect_def_type dt;
tree def;
+ bb_vec_info bb_vinfo;
stmt_vinfo = vinfo_for_stmt (use_stmt);
loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
-
- if (!vect_is_simple_use (name, loop_vinfo, NULL, def_stmt, &def, &dt))
+ bb_vinfo = STMT_VINFO_BB_VINFO (stmt_vinfo);
+ if (!vect_is_simple_use (name, use_stmt, loop_vinfo, bb_vinfo, def_stmt,
+ &def, &dt))
return false;
if (dt != vect_internal_def
&& dt != vect_external_def && dt != vect_constant_def)
return false;
- if (! *def_stmt)
+ if (!*def_stmt)
return false;
if (!is_gimple_assign (*def_stmt))
return false;
- if (gimple_assign_rhs_code (*def_stmt) != NOP_EXPR)
+ if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (*def_stmt)))
return false;
oprnd0 = gimple_assign_rhs1 (*def_stmt);
- *half_type = TREE_TYPE (oprnd0);
- if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*half_type)
- || ((TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*half_type)) && check_sign)
- || (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 2)))
+ *orig_type = TREE_TYPE (oprnd0);
+ if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*orig_type)
+ || ((TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*orig_type)) && check_sign))
+ return false;
+
+ if (TYPE_PRECISION (type) >= (TYPE_PRECISION (*orig_type) * 2))
+ *promotion = true;
+ else if (TYPE_PRECISION (*orig_type) >= (TYPE_PRECISION (type) * 2))
+ *promotion = false;
+ else
return false;
- if (!vect_is_simple_use (oprnd0, loop_vinfo, NULL, &dummy_gimple, &dummy,
- &dt))
+ if (!vect_is_simple_use (oprnd0, *def_stmt, loop_vinfo,
+ bb_vinfo, &dummy_gimple, &dummy, &dt))
return false;
return true;
static tree
vect_recog_temp_ssa_var (tree type, gimple stmt)
{
- tree var = create_tmp_var (type, "patt");
-
- add_referenced_var (var);
- var = make_ssa_name (var, stmt);
- return var;
+ return make_temp_ssa_name (type, stmt, "patt");
}
/* Function vect_recog_dot_prod_pattern
inner-loop nested in an outer-loop that us being vectorized). */
static gimple
-vect_recog_dot_prod_pattern (VEC (gimple, heap) **stmts, tree *type_in,
+vect_recog_dot_prod_pattern (vec<gimple> *stmts, tree *type_in,
tree *type_out)
{
- gimple stmt, last_stmt = VEC_index (gimple, *stmts, 0);
+ gimple stmt, last_stmt = (*stmts)[0];
tree oprnd0, oprnd1;
tree oprnd00, oprnd01;
stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
gimple pattern_stmt;
tree prod_type;
loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
- struct loop *loop = LOOP_VINFO_LOOP (loop_info);
+ struct loop *loop;
tree var;
+ bool promotion;
+
+ if (!loop_info)
+ return NULL;
+
+ loop = LOOP_VINFO_LOOP (loop_info);
if (!is_gimple_assign (last_stmt))
return NULL;
return NULL;
stmt = last_stmt;
- if (widened_name_p (oprnd0, stmt, &half_type, &def_stmt, true))
+ if (type_conversion_p (oprnd0, stmt, true, &half_type, &def_stmt,
+ &promotion)
+ && promotion)
{
stmt = def_stmt;
oprnd0 = gimple_assign_rhs1 (stmt);
if (!types_compatible_p (TREE_TYPE (oprnd0), prod_type)
|| !types_compatible_p (TREE_TYPE (oprnd1), prod_type))
return NULL;
- if (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt, true))
+ if (!type_conversion_p (oprnd0, stmt, true, &half_type0, &def_stmt,
+ &promotion)
+ || !promotion)
return NULL;
oprnd00 = gimple_assign_rhs1 (def_stmt);
- if (!widened_name_p (oprnd1, stmt, &half_type1, &def_stmt, true))
+ if (!type_conversion_p (oprnd1, stmt, true, &half_type1, &def_stmt,
+ &promotion)
+ || !promotion)
return NULL;
oprnd01 = gimple_assign_rhs1 (def_stmt);
if (!types_compatible_p (half_type0, half_type1))
/* Pattern detected. Create a stmt to be used to replace the pattern: */
var = vect_recog_temp_ssa_var (type, NULL);
- pattern_stmt = gimple_build_assign_with_ops3 (DOT_PROD_EXPR, var,
- oprnd00, oprnd01, oprnd1);
+ pattern_stmt = gimple_build_assign_with_ops (DOT_PROD_EXPR, var,
+ oprnd00, oprnd01, oprnd1);
- if (vect_print_dump_info (REPORT_DETAILS))
+ if (dump_enabled_p ())
{
- fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: ");
- print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+ 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
static bool
vect_handle_widen_op_by_const (gimple stmt, enum tree_code code,
tree const_oprnd, tree *oprnd,
- VEC (gimple, heap) **stmts, tree type,
+ vec<gimple> *stmts, tree type,
tree *half_type, gimple def_stmt)
{
- tree new_type, new_oprnd, tmp;
+ tree new_type, new_oprnd;
gimple new_stmt;
- loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (vinfo_for_stmt (stmt));
- struct loop *loop = LOOP_VINFO_LOOP (loop_info);
if (code != MULT_EXPR && code != LSHIFT_EXPR)
return false;
return true;
}
- if (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 4)
- || !gimple_bb (def_stmt)
- || !flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
- || !vinfo_for_stmt (def_stmt))
+ if (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 4))
+ return false;
+
+ if (!vect_same_loop_or_bb_p (stmt, def_stmt))
return false;
/* TYPE is 4 times bigger than HALF_TYPE, try widening operation for
|| TREE_TYPE (gimple_assign_lhs (new_stmt)) != new_type)
return false;
- VEC_safe_push (gimple, heap, *stmts, def_stmt);
+ stmts->safe_push (def_stmt);
*oprnd = gimple_assign_lhs (new_stmt);
}
else
{
/* Create a_T = (NEW_TYPE) a_t; */
*oprnd = gimple_assign_rhs1 (def_stmt);
- tmp = create_tmp_var (new_type, NULL);
- add_referenced_var (tmp);
- new_oprnd = make_ssa_name (tmp, NULL);
+ new_oprnd = make_ssa_name (new_type, NULL);
new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd, *oprnd,
NULL_TREE);
STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)) = new_stmt;
- VEC_safe_push (gimple, heap, *stmts, def_stmt);
+ stmts->safe_push (def_stmt);
*oprnd = new_oprnd;
}
where type 'TYPE' is at least double the size of type 'type'.
- Also detect unsgigned cases:
+ Also detect unsigned cases:
unsigned type a_t, b_t;
unsigned TYPE u_prod_T;
*/
static gimple
-vect_recog_widen_mult_pattern (VEC (gimple, heap) **stmts,
+vect_recog_widen_mult_pattern (vec<gimple> *stmts,
tree *type_in, tree *type_out)
{
- gimple last_stmt = VEC_pop (gimple, *stmts);
+ gimple last_stmt = stmts->pop ();
gimple def_stmt0, def_stmt1;
tree oprnd0, oprnd1;
tree type, half_type0, half_type1;
gimple pattern_stmt;
tree vectype, vectype_out = NULL_TREE;
- tree dummy;
tree var;
enum tree_code dummy_code;
int dummy_int;
- VEC (tree, heap) *dummy_vec;
+ vec<tree> dummy_vec;
bool op1_ok;
+ bool promotion;
if (!is_gimple_assign (last_stmt))
return NULL;
return NULL;
/* Check argument 0. */
- if (!widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0, false))
- return NULL;
+ if (!type_conversion_p (oprnd0, last_stmt, false, &half_type0, &def_stmt0,
+ &promotion)
+ || !promotion)
+ return NULL;
/* Check argument 1. */
- op1_ok = widened_name_p (oprnd1, last_stmt, &half_type1, &def_stmt1, false);
+ op1_ok = type_conversion_p (oprnd1, last_stmt, false, &half_type1,
+ &def_stmt1, &promotion);
- if (op1_ok)
+ if (op1_ok && promotion)
{
oprnd0 = gimple_assign_rhs1 (def_stmt0);
oprnd1 = gimple_assign_rhs1 (def_stmt1);
&& 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;
}
Use unsigned TYPE as the type for WIDEN_MULT_EXPR. */
if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (half_type0))
{
- tree lhs = gimple_assign_lhs (last_stmt), use_lhs;
- imm_use_iterator imm_iter;
- use_operand_p use_p;
- int nuses = 0;
- gimple use_stmt = NULL;
+ gimple use_stmt;
+ tree use_lhs;
tree use_type;
if (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (half_type1))
return NULL;
- FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
- {
- if (is_gimple_debug (USE_STMT (use_p)))
- continue;
- use_stmt = USE_STMT (use_p);
- nuses++;
- }
-
- if (nuses != 1 || !is_gimple_assign (use_stmt)
- || gimple_assign_rhs_code (use_stmt) != NOP_EXPR)
+ use_stmt = vect_single_imm_use (last_stmt);
+ if (!use_stmt || !is_gimple_assign (use_stmt)
+ || gimple_assign_rhs_code (use_stmt) != NOP_EXPR)
return NULL;
use_lhs = gimple_assign_lhs (use_stmt);
return NULL;
/* Pattern detected. */
- if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "vect_recog_widen_mult_pattern: detected: ");
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "vect_recog_widen_mult_pattern: detected:\n");
/* Check target support */
vectype = get_vectype_for_scalar_type (half_type0);
|| !vectype_out
|| !supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt,
vectype_out, vectype,
- &dummy, &dummy, &dummy_code,
- &dummy_code, &dummy_int, &dummy_vec))
+ &dummy_code, &dummy_code,
+ &dummy_int, &dummy_vec))
return NULL;
*type_in = vectype;
pattern_stmt = gimple_build_assign_with_ops (WIDEN_MULT_EXPR, var, oprnd0,
oprnd1);
- if (vect_print_dump_info (REPORT_DETAILS))
- print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+ if (dump_enabled_p ())
+ dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0);
- VEC_safe_push (gimple, heap, *stmts, last_stmt);
+ stmts->safe_push (last_stmt);
return pattern_stmt;
}
*/
static gimple
-vect_recog_pow_pattern (VEC (gimple, heap) **stmts, tree *type_in,
+vect_recog_pow_pattern (vec<gimple> *stmts, tree *type_in,
tree *type_out)
{
- gimple last_stmt = VEC_index (gimple, *stmts, 0);
+ gimple last_stmt = (*stmts)[0];
tree fn, base, exp = NULL;
gimple stmt;
tree var;
*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)))
{
inner-loop nested in an outer-loop that us being vectorized). */
static gimple
-vect_recog_widen_sum_pattern (VEC (gimple, heap) **stmts, tree *type_in,
+vect_recog_widen_sum_pattern (vec<gimple> *stmts, tree *type_in,
tree *type_out)
{
- gimple stmt, last_stmt = VEC_index (gimple, *stmts, 0);
+ gimple stmt, last_stmt = (*stmts)[0];
tree oprnd0, oprnd1;
stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
tree type, half_type;
gimple pattern_stmt;
loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
- struct loop *loop = LOOP_VINFO_LOOP (loop_info);
+ struct loop *loop;
tree var;
+ bool promotion;
+
+ if (!loop_info)
+ return NULL;
+
+ loop = LOOP_VINFO_LOOP (loop_info);
if (!is_gimple_assign (last_stmt))
return NULL;
Left to check that oprnd0 is defined by a cast from type 'type' to type
'TYPE'. */
- if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt, true))
- return NULL;
+ if (!type_conversion_p (oprnd0, last_stmt, true, &half_type, &stmt,
+ &promotion)
+ || !promotion)
+ return NULL;
oprnd0 = gimple_assign_rhs1 (stmt);
*type_in = half_type;
pattern_stmt = gimple_build_assign_with_ops (WIDEN_SUM_EXPR, var,
oprnd0, oprnd1);
- if (vect_print_dump_info (REPORT_DETAILS))
+ if (dump_enabled_p ())
{
- fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: ");
- print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+ 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
static bool
vect_operation_fits_smaller_type (gimple stmt, tree def, tree *new_type,
tree *op0, tree *op1, gimple *new_def_stmt,
- VEC (gimple, heap) **stmts)
+ vec<gimple> *stmts)
{
enum tree_code code;
tree const_oprnd, oprnd;
- tree interm_type = NULL_TREE, half_type, tmp, new_oprnd, type;
+ tree interm_type = NULL_TREE, half_type, new_oprnd, type;
gimple def_stmt, new_stmt;
bool first = false;
- loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (vinfo_for_stmt (stmt));
- struct loop *loop = LOOP_VINFO_LOOP (loop_info);
+ bool promotion;
+ *op0 = NULL_TREE;
+ *op1 = NULL_TREE;
*new_def_stmt = NULL;
if (!is_gimple_assign (stmt))
|| TREE_CODE (const_oprnd) != INTEGER_CST)
return false;
+ /* If oprnd has other uses besides that in stmt we cannot mark it
+ as being part of a pattern only. */
+ if (!has_single_use (oprnd))
+ return false;
+
/* If we are in the middle of a sequence, we use DEF from a previous
statement. Otherwise, OPRND has to be a result of type promotion. */
if (*new_type)
else
{
first = true;
- if (!widened_name_p (oprnd, stmt, &half_type, &def_stmt, false)
- || !gimple_bb (def_stmt)
- || !flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
- || !vinfo_for_stmt (def_stmt))
+ if (!type_conversion_p (oprnd, stmt, false, &half_type, &def_stmt,
+ &promotion)
+ || !promotion
+ || !vect_same_loop_or_bb_p (stmt, def_stmt))
return false;
}
|| TREE_TYPE (gimple_assign_lhs (new_stmt)) != interm_type)
return false;
- VEC_safe_push (gimple, heap, *stmts, def_stmt);
+ stmts->safe_push (def_stmt);
oprnd = gimple_assign_lhs (new_stmt);
}
else
{
/* Create NEW_OPRND = (INTERM_TYPE) OPRND. */
oprnd = gimple_assign_rhs1 (def_stmt);
- tmp = create_tmp_reg (interm_type, NULL);
- add_referenced_var (tmp);
- new_oprnd = make_ssa_name (tmp, NULL);
+ new_oprnd = make_ssa_name (interm_type, NULL);
new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd,
oprnd, NULL_TREE);
STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)) = new_stmt;
- VEC_safe_push (gimple, heap, *stmts, def_stmt);
+ stmts->safe_push (def_stmt);
oprnd = new_oprnd;
}
}
if (interm_type)
{
/* Create a type conversion HALF_TYPE->INTERM_TYPE. */
- tmp = create_tmp_reg (interm_type, NULL);
- add_referenced_var (tmp);
- new_oprnd = make_ssa_name (tmp, NULL);
+ new_oprnd = make_ssa_name (interm_type, NULL);
new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd,
oprnd, NULL_TREE);
oprnd = new_oprnd;
demotion operation. We also check that S3 and S4 have only one use. */
static gimple
-vect_recog_over_widening_pattern (VEC (gimple, heap) **stmts,
+vect_recog_over_widening_pattern (vec<gimple> *stmts,
tree *type_in, tree *type_out)
{
- gimple stmt = VEC_pop (gimple, *stmts);
+ gimple stmt = stmts->pop ();
gimple pattern_stmt = NULL, new_def_stmt, prev_stmt = NULL, use_stmt = NULL;
- tree op0, op1, vectype = NULL_TREE, lhs, use_lhs, use_type;
- imm_use_iterator imm_iter;
- use_operand_p use_p;
- int nuses = 0;
- tree var = NULL_TREE, new_type = NULL_TREE, tmp, new_oprnd;
+ tree op0, op1, vectype = NULL_TREE, use_lhs, use_type;
+ tree var = NULL_TREE, new_type = NULL_TREE, new_oprnd;
bool first;
- struct loop *loop = (gimple_bb (stmt))->loop_father;
tree type = NULL;
first = true;
}
/* STMT can be performed on a smaller type. Check its uses. */
- lhs = gimple_assign_lhs (stmt);
- nuses = 0;
- FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
- {
- if (is_gimple_debug (USE_STMT (use_p)))
- continue;
- use_stmt = USE_STMT (use_p);
- nuses++;
- }
-
- if (nuses != 1 || !is_gimple_assign (use_stmt)
- || !gimple_bb (use_stmt)
- || !flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
+ use_stmt = vect_single_imm_use (stmt);
+ if (!use_stmt || !is_gimple_assign (use_stmt))
return NULL;
/* Create pattern statement for STMT. */
in the sequence. Therefore, we only add the original statement to
the list if we know that it is not the last. */
if (prev_stmt)
- VEC_safe_push (gimple, heap, *stmts, prev_stmt);
+ stmts->safe_push (prev_stmt);
var = vect_recog_temp_ssa_var (new_type, NULL);
pattern_stmt
STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt)) = pattern_stmt;
new_pattern_def_seq (vinfo_for_stmt (stmt), new_def_stmt);
- if (vect_print_dump_info (REPORT_DETAILS))
+ if (dump_enabled_p ())
{
- fprintf (vect_dump, "created pattern stmt: ");
- print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+ 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);
{
use_lhs = gimple_assign_lhs (use_stmt);
use_type = TREE_TYPE (use_lhs);
- /* Support only type promotion or signedess change. Check that USE_TYPE
- is not bigger than the original type. */
+ /* Support only type demotion or signedess change. */
if (!INTEGRAL_TYPE_P (use_type)
- || TYPE_PRECISION (new_type) > TYPE_PRECISION (use_type)
- || TYPE_PRECISION (type) < TYPE_PRECISION (use_type))
+ || TYPE_PRECISION (type) <= TYPE_PRECISION (use_type))
return NULL;
+ /* Check that NEW_TYPE is not bigger than the conversion result. */
+ if (TYPE_PRECISION (new_type) > TYPE_PRECISION (use_type))
+ return NULL;
+
if (TYPE_UNSIGNED (new_type) != TYPE_UNSIGNED (use_type)
|| TYPE_PRECISION (new_type) != TYPE_PRECISION (use_type))
{
/* Create NEW_TYPE->USE_TYPE conversion. */
- tmp = create_tmp_reg (use_type, NULL);
- add_referenced_var (tmp);
- new_oprnd = make_ssa_name (tmp, NULL);
+ new_oprnd = make_ssa_name (use_type, NULL);
pattern_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd,
var, NULL_TREE);
STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use_stmt)) = pattern_stmt;
statement created for PREV_STMT. Therefore, we add PREV_STMT
to the list in order to mark it later in vect_pattern_recog_1. */
if (prev_stmt)
- VEC_safe_push (gimple, heap, *stmts, prev_stmt);
+ stmts->safe_push (prev_stmt);
}
else
{
*type_out = NULL_TREE;
}
- VEC_safe_push (gimple, heap, *stmts, use_stmt);
+ stmts->safe_push (use_stmt);
}
else
/* TODO: support general case, create a conversion to the correct type. */
return NULL;
/* Pattern detected. */
- if (vect_print_dump_info (REPORT_DETAILS))
+ if (dump_enabled_p ())
{
- fprintf (vect_dump, "vect_recog_over_widening_pattern: detected: ");
- print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+ 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;
where type 'TYPE' is at least double the size of type 'type'.
- Also detect unsigned cases:
+ Also detect cases where the shift result is immediately converted
+ to another type 'result_type' that is no larger in size than 'TYPE'.
+ In those cases we perform a widen-shift that directly results in
+ 'result_type', to avoid a possible over-widening situation:
- unsigned type a_t;
- unsigned TYPE u_res_T;
+ type a_t;
TYPE a_T, res_T;
+ result_type res_result;
S1 a_t = ;
S2 a_T = (TYPE) a_t;
S3 res_T = a_T << CONST;
- S4 u_res_T = (unsigned TYPE) res_T;
+ S4 res_result = (result_type) res_T;
+ '--> res_result' = a_t w<< CONST;
And a case when 'TYPE' is 4 times bigger than 'type'. In that case we
create an additional pattern stmt for S2 to create a variable of an
WIDEN_LSHIFT_EXPR <a_t, CONST>. */
static gimple
-vect_recog_widen_shift_pattern (VEC (gimple, heap) **stmts,
+vect_recog_widen_shift_pattern (vec<gimple> *stmts,
tree *type_in, tree *type_out)
{
- gimple last_stmt = VEC_pop (gimple, *stmts);
+ gimple last_stmt = stmts->pop ();
gimple def_stmt0;
tree oprnd0, oprnd1;
tree type, half_type0;
- gimple pattern_stmt, orig_stmt = NULL;
+ gimple pattern_stmt;
tree vectype, vectype_out = NULL_TREE;
- tree dummy;
tree var;
enum tree_code dummy_code;
int dummy_int;
- VEC (tree, heap) * dummy_vec;
- gimple use_stmt = NULL;
- bool over_widen = false;
+ vec<tree> dummy_vec;
+ gimple use_stmt;
+ bool promotion;
if (!is_gimple_assign (last_stmt) || !vinfo_for_stmt (last_stmt))
return NULL;
- orig_stmt = last_stmt;
if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (last_stmt)))
- {
- /* This statement was also detected as over-widening operation (it can't
- be any other pattern, because only over-widening detects shifts).
- LAST_STMT is the final type demotion statement, but its related
- statement is shift. We analyze the related statement to catch cases:
-
- orig code:
- type a_t;
- itype res;
- TYPE a_T, res_T;
-
- S1 a_T = (TYPE) a_t;
- S2 res_T = a_T << CONST;
- S3 res = (itype)res_T;
-
- (size of type * 2 <= size of itype
- and size of itype * 2 <= size of TYPE)
-
- code after over-widening pattern detection:
-
- S1 a_T = (TYPE) a_t;
- --> a_it = (itype) a_t;
- S2 res_T = a_T << CONST;
- S3 res = (itype)res_T; <--- LAST_STMT
- --> res = a_it << CONST;
-
- after widen_shift:
-
- S1 a_T = (TYPE) a_t;
- --> a_it = (itype) a_t; - redundant
- S2 res_T = a_T << CONST;
- S3 res = (itype)res_T;
- --> res = a_t w<< CONST;
-
- i.e., we replace the three statements with res = a_t w<< CONST. */
- last_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (last_stmt));
- over_widen = true;
- }
+ return NULL;
if (gimple_assign_rhs_code (last_stmt) != LSHIFT_EXPR)
return NULL;
return NULL;
/* Check operand 0: it has to be defined by a type promotion. */
- if (!widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0, false))
- return NULL;
+ if (!type_conversion_p (oprnd0, last_stmt, false, &half_type0, &def_stmt0,
+ &promotion)
+ || !promotion)
+ return NULL;
/* Check operand 1: has to be positive. We check that it fits the type
in vect_handle_widen_op_by_const (). */
oprnd0 = gimple_assign_rhs1 (def_stmt0);
type = gimple_expr_type (last_stmt);
+ /* Check for subsequent conversion to another type. */
+ use_stmt = vect_single_imm_use (last_stmt);
+ if (use_stmt && is_gimple_assign (use_stmt)
+ && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt))
+ && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt)))
+ {
+ tree use_lhs = gimple_assign_lhs (use_stmt);
+ tree use_type = TREE_TYPE (use_lhs);
+
+ if (INTEGRAL_TYPE_P (use_type)
+ && TYPE_PRECISION (use_type) <= TYPE_PRECISION (type))
+ {
+ last_stmt = use_stmt;
+ type = use_type;
+ }
+ }
+
/* Check if this a widening operation. */
if (!vect_handle_widen_op_by_const (last_stmt, LSHIFT_EXPR, oprnd1,
&oprnd0, stmts,
type, &half_type0, def_stmt0))
return NULL;
- /* Handle unsigned case. Look for
- S4 u_res_T = (unsigned TYPE) res_T;
- Use unsigned TYPE as the type for WIDEN_LSHIFT_EXPR. */
- if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (half_type0))
- {
- tree lhs = gimple_assign_lhs (last_stmt), use_lhs;
- imm_use_iterator imm_iter;
- use_operand_p use_p;
- int nuses = 0;
- tree use_type;
-
- if (over_widen)
- {
- /* In case of over-widening pattern, S4 should be ORIG_STMT itself.
- We check here that TYPE is the correct type for the operation,
- i.e., it's the type of the original result. */
- tree orig_type = gimple_expr_type (orig_stmt);
- if ((TYPE_UNSIGNED (type) != TYPE_UNSIGNED (orig_type))
- || (TYPE_PRECISION (type) != TYPE_PRECISION (orig_type)))
- return NULL;
- }
- else
- {
- FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
- {
- if (is_gimple_debug (USE_STMT (use_p)))
- continue;
- use_stmt = USE_STMT (use_p);
- nuses++;
- }
-
- if (nuses != 1 || !is_gimple_assign (use_stmt)
- || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
- return NULL;
-
- use_lhs = gimple_assign_lhs (use_stmt);
- use_type = TREE_TYPE (use_lhs);
-
- if (!INTEGRAL_TYPE_P (use_type)
- || (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (use_type))
- || (TYPE_PRECISION (type) != TYPE_PRECISION (use_type)))
- return NULL;
-
- type = use_type;
- }
- }
-
/* Pattern detected. */
- if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "vect_recog_widen_shift_pattern: detected: ");
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "vect_recog_widen_shift_pattern: detected:\n");
/* Check target support. */
vectype = get_vectype_for_scalar_type (half_type0);
|| !vectype_out
|| !supportable_widening_operation (WIDEN_LSHIFT_EXPR, last_stmt,
vectype_out, vectype,
- &dummy, &dummy, &dummy_code,
- &dummy_code, &dummy_int,
- &dummy_vec))
+ &dummy_code, &dummy_code,
+ &dummy_int, &dummy_vec))
return NULL;
*type_in = vectype;
pattern_stmt =
gimple_build_assign_with_ops (WIDEN_LSHIFT_EXPR, var, oprnd0, oprnd1);
- if (vect_print_dump_info (REPORT_DETAILS))
- print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+ 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 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 (use_stmt)
- last_stmt = use_stmt;
+ 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
- last_stmt = orig_stmt;
+ {
+ 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);
- VEC_safe_push (gimple, heap, *stmts, last_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;
}
S3 stmt. */
static gimple
-vect_recog_vector_vector_shift_pattern (VEC (gimple, heap) **stmts,
+vect_recog_vector_vector_shift_pattern (vec<gimple> *stmts,
tree *type_in, tree *type_out)
{
- gimple last_stmt = VEC_pop (gimple, *stmts);
+ gimple last_stmt = stmts->pop ();
tree oprnd0, oprnd1, lhs, var;
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;
tree def;
!= TYPE_PRECISION (TREE_TYPE (oprnd0)))
return NULL;
- if (!vect_is_simple_use (oprnd1, loop_vinfo, NULL, &def_stmt, &def, &dt))
+ if (!vect_is_simple_use (oprnd1, last_stmt, loop_vinfo, bb_vinfo, &def_stmt,
+ &def, &dt))
return NULL;
if (dt != vect_internal_def)
}
/* Pattern detected. */
- if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "vect_recog_vector_vector_shift_pattern: detected: ");
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "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_stmt = gimple_build_assign_with_ops (rhs_code, var, oprnd0, def);
- if (vect_print_dump_info (REPORT_DETAILS))
- print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+ if (dump_enabled_p ())
+ dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0);
- VEC_safe_push (gimple, heap, *stmts, last_stmt);
+ stmts->safe_push (last_stmt);
return pattern_stmt;
}
-/* Detect a signed division by power of two constant that wouldn't be
+/* Detect a signed division by a constant that wouldn't be
otherwise vectorized:
type a_t, b_t;
S1 a_t = b_t / N;
- where type 'type' is a signed integral type and N is a constant positive
- power of two.
+ where type 'type' is an integral type and N is a constant.
- Similarly handle signed modulo by power of two constant:
+ Similarly handle modulo by a constant:
S4 a_t = b_t % N;
Input/Output:
* STMTS: Contains a stmt from which the pattern search begins,
- i.e. the division stmt. S1 is replaced by:
+ i.e. the division stmt. S1 is replaced by if N is a power
+ of two constant and type is signed:
S3 y_t = b_t < 0 ? N - 1 : 0;
S2 x_t = b_t + y_t;
S1' a_t = x_t >> log2 (N);
- S4 is replaced by (where *_T temporaries have unsigned type):
+ S4 is replaced if N is a power of two constant and
+ type is signed by (where *_T temporaries have unsigned type):
S9 y_T = b_t < 0 ? -1U : 0U;
S8 z_T = y_T >> (sizeof (type_t) * CHAR_BIT - log2 (N));
S7 z_t = (type) z_T;
S1 or modulo S4 stmt. */
static gimple
-vect_recog_sdivmod_pow2_pattern (VEC (gimple, heap) **stmts,
- tree *type_in, tree *type_out)
+vect_recog_divmod_pattern (vec<gimple> *stmts,
+ tree *type_in, tree *type_out)
{
- gimple last_stmt = VEC_pop (gimple, *stmts);
+ gimple last_stmt = stmts->pop ();
tree oprnd0, oprnd1, vectype, itype, cond;
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);
optab optab;
+ tree q;
+ int dummy_int, prec;
+ stmt_vec_info def_stmt_vinfo;
if (!is_gimple_assign (last_stmt))
return NULL;
if (TREE_CODE (oprnd0) != SSA_NAME
|| TREE_CODE (oprnd1) != INTEGER_CST
|| TREE_CODE (itype) != INTEGER_TYPE
- || TYPE_UNSIGNED (itype)
- || TYPE_PRECISION (itype) != GET_MODE_PRECISION (TYPE_MODE (itype))
- || !integer_pow2p (oprnd1)
- || tree_int_cst_sgn (oprnd1) != 1)
+ || TYPE_PRECISION (itype) != GET_MODE_PRECISION (TYPE_MODE (itype)))
return NULL;
vectype = get_vectype_for_scalar_type (itype);
/* If the target can handle vectorized division or modulo natively,
don't attempt to optimize this. */
optab = optab_for_tree_code (rhs_code, vectype, optab_default);
- if (optab != NULL)
+ if (optab != unknown_optab)
{
enum machine_mode vec_mode = TYPE_MODE (vectype);
int icode = (int) optab_handler (optab, vec_mode);
- if (icode != CODE_FOR_nothing
- || GET_MODE_SIZE (vec_mode) == UNITS_PER_WORD)
+ if (icode != CODE_FOR_nothing)
return NULL;
}
- /* Pattern detected. */
- if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "vect_recog_sdivmod_pow2_pattern: detected: ");
-
- cond = build2 (LT_EXPR, boolean_type_node, oprnd0, build_int_cst (itype, 0));
- if (rhs_code == TRUNC_DIV_EXPR)
+ prec = TYPE_PRECISION (itype);
+ if (integer_pow2p (oprnd1))
{
- tree var = vect_recog_temp_ssa_var (itype, NULL);
- def_stmt
- = gimple_build_assign_with_ops3 (COND_EXPR, var, cond,
- fold_build2 (MINUS_EXPR, itype,
- oprnd1,
- build_int_cst (itype,
- 1)),
- build_int_cst (itype, 0));
- new_pattern_def_seq (stmt_vinfo, def_stmt);
- var = vect_recog_temp_ssa_var (itype, NULL);
- def_stmt
- = gimple_build_assign_with_ops (PLUS_EXPR, var, oprnd0,
- gimple_assign_lhs (def_stmt));
- append_pattern_def_seq (stmt_vinfo, def_stmt);
+ if (TYPE_UNSIGNED (itype) || tree_int_cst_sgn (oprnd1) != 1)
+ return NULL;
- pattern_stmt
- = gimple_build_assign_with_ops (RSHIFT_EXPR,
- vect_recog_temp_ssa_var (itype, NULL),
- var,
- build_int_cst (itype,
- tree_log2 (oprnd1)));
+ /* Pattern detected. */
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "vect_recog_divmod_pattern: detected:\n");
+
+ cond = build2 (LT_EXPR, boolean_type_node, oprnd0,
+ build_int_cst (itype, 0));
+ if (rhs_code == TRUNC_DIV_EXPR)
+ {
+ tree var = vect_recog_temp_ssa_var (itype, NULL);
+ tree shift;
+ def_stmt
+ = gimple_build_assign_with_ops (COND_EXPR, var, cond,
+ fold_build2 (MINUS_EXPR, itype,
+ oprnd1,
+ build_int_cst (itype,
+ 1)),
+ build_int_cst (itype, 0));
+ new_pattern_def_seq (stmt_vinfo, def_stmt);
+ var = vect_recog_temp_ssa_var (itype, NULL);
+ def_stmt
+ = gimple_build_assign_with_ops (PLUS_EXPR, var, oprnd0,
+ gimple_assign_lhs (def_stmt));
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+
+ shift = build_int_cst (itype, tree_log2 (oprnd1));
+ pattern_stmt
+ = gimple_build_assign_with_ops (RSHIFT_EXPR,
+ vect_recog_temp_ssa_var (itype,
+ NULL),
+ var, shift);
+ }
+ else
+ {
+ tree signmask;
+ STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
+ if (compare_tree_int (oprnd1, 2) == 0)
+ {
+ signmask = vect_recog_temp_ssa_var (itype, NULL);
+ def_stmt
+ = gimple_build_assign_with_ops (COND_EXPR, signmask, cond,
+ build_int_cst (itype, 1),
+ build_int_cst (itype, 0));
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+ }
+ else
+ {
+ tree utype
+ = build_nonstandard_integer_type (prec, 1);
+ tree vecutype = get_vectype_for_scalar_type (utype);
+ tree shift
+ = build_int_cst (utype, GET_MODE_BITSIZE (TYPE_MODE (itype))
+ - tree_log2 (oprnd1));
+ tree var = vect_recog_temp_ssa_var (utype, NULL);
+
+ def_stmt
+ = gimple_build_assign_with_ops (COND_EXPR, var, cond,
+ build_int_cst (utype, -1),
+ build_int_cst (utype, 0));
+ 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) = vecutype;
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+ var = vect_recog_temp_ssa_var (utype, NULL);
+ def_stmt
+ = gimple_build_assign_with_ops (RSHIFT_EXPR, var,
+ gimple_assign_lhs (def_stmt),
+ shift);
+ 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) = vecutype;
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+ signmask = vect_recog_temp_ssa_var (itype, NULL);
+ def_stmt
+ = gimple_build_assign_with_ops (NOP_EXPR, signmask, var,
+ NULL_TREE);
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+ }
+ def_stmt
+ = gimple_build_assign_with_ops (PLUS_EXPR,
+ vect_recog_temp_ssa_var (itype,
+ NULL),
+ oprnd0, signmask);
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+ def_stmt
+ = gimple_build_assign_with_ops (BIT_AND_EXPR,
+ vect_recog_temp_ssa_var (itype,
+ NULL),
+ gimple_assign_lhs (def_stmt),
+ fold_build2 (MINUS_EXPR, itype,
+ oprnd1,
+ build_int_cst (itype,
+ 1)));
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+
+ pattern_stmt
+ = gimple_build_assign_with_ops (MINUS_EXPR,
+ vect_recog_temp_ssa_var (itype,
+ NULL),
+ gimple_assign_lhs (def_stmt),
+ signmask);
+ }
+
+ if (dump_enabled_p ())
+ dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt,
+ 0);
+
+ stmts->safe_push (last_stmt);
+
+ *type_in = vectype;
+ *type_out = vectype;
+ return pattern_stmt;
}
- else
+
+ if (prec > HOST_BITS_PER_WIDE_INT
+ || integer_zerop (oprnd1))
+ return NULL;
+
+ if (!can_mult_highpart_p (TYPE_MODE (vectype), TYPE_UNSIGNED (itype)))
+ return NULL;
+
+ STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
+
+ if (TYPE_UNSIGNED (itype))
{
- tree signmask;
- STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
- if (compare_tree_int (oprnd1, 2) == 0)
+ unsigned HOST_WIDE_INT mh, ml;
+ int pre_shift, post_shift;
+ 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)))
+ /* FIXME: Can transform this into oprnd0 >= oprnd1 ? 1 : 0. */
+ return NULL;
+
+ /* Find a suitable multiplier and right shift count
+ instead of multiplying with D. */
+ mh = choose_multiplier (d, prec, prec, &ml, &post_shift, &dummy_int);
+
+ /* If the suggested multiplier is more than SIZE bits, we can do better
+ for even divisors, using an initial right shift. */
+ if (mh != 0 && (d & 1) == 0)
+ {
+ pre_shift = floor_log2 (d & -d);
+ mh = choose_multiplier (d >> pre_shift, prec, prec - pre_shift,
+ &ml, &post_shift, &dummy_int);
+ gcc_assert (!mh);
+ }
+ else
+ pre_shift = 0;
+
+ if (mh != 0)
{
- signmask = vect_recog_temp_ssa_var (itype, NULL);
+ if (post_shift - 1 >= prec)
+ return NULL;
+
+ /* t1 = oprnd0 h* ml;
+ t2 = oprnd0 - t1;
+ t3 = t2 >> 1;
+ t4 = t1 + t3;
+ q = t4 >> (post_shift - 1); */
+ t1 = vect_recog_temp_ssa_var (itype, NULL);
def_stmt
- = gimple_build_assign_with_ops3 (COND_EXPR, signmask, cond,
- build_int_cst (itype, 1),
- build_int_cst (itype, 0));
+ = gimple_build_assign_with_ops (MULT_HIGHPART_EXPR, t1, oprnd0,
+ build_int_cst (itype, ml));
append_pattern_def_seq (stmt_vinfo, def_stmt);
+
+ t2 = vect_recog_temp_ssa_var (itype, NULL);
+ def_stmt
+ = gimple_build_assign_with_ops (MINUS_EXPR, t2, oprnd0, t1);
+ 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,
+ integer_one_node);
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+
+ t4 = vect_recog_temp_ssa_var (itype, NULL);
+ def_stmt
+ = gimple_build_assign_with_ops (PLUS_EXPR, t4, t1, t3);
+
+ if (post_shift != 1)
+ {
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+
+ q = vect_recog_temp_ssa_var (itype, NULL);
+ pattern_stmt
+ = gimple_build_assign_with_ops (RSHIFT_EXPR, q, t4,
+ build_int_cst (itype,
+ post_shift
+ - 1));
+ }
+ else
+ {
+ q = t4;
+ pattern_stmt = def_stmt;
+ }
}
else
{
- tree utype
- = build_nonstandard_integer_type (TYPE_PRECISION (itype), 1);
- tree vecutype = get_vectype_for_scalar_type (utype);
- tree shift
- = build_int_cst (utype, GET_MODE_BITSIZE (TYPE_MODE (itype))
- - tree_log2 (oprnd1));
- tree var = vect_recog_temp_ssa_var (utype, NULL);
- stmt_vec_info def_stmt_vinfo;
+ if (pre_shift >= prec || post_shift >= prec)
+ return NULL;
+
+ /* t1 = oprnd0 >> pre_shift;
+ t2 = t1 h* ml;
+ q = t2 >> post_shift; */
+ if (pre_shift)
+ {
+ t1 = vect_recog_temp_ssa_var (itype, NULL);
+ def_stmt
+ = gimple_build_assign_with_ops (RSHIFT_EXPR, t1, oprnd0,
+ build_int_cst (NULL,
+ pre_shift));
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+ }
+ else
+ t1 = oprnd0;
+ t2 = vect_recog_temp_ssa_var (itype, NULL);
def_stmt
- = gimple_build_assign_with_ops3 (COND_EXPR, var, cond,
- build_int_cst (utype, -1),
- build_int_cst (utype, 0));
- def_stmt_vinfo = new_stmt_vec_info (def_stmt, loop_vinfo, NULL);
- set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
- STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecutype;
+ = gimple_build_assign_with_ops (MULT_HIGHPART_EXPR, t2, t1,
+ build_int_cst (itype, ml));
+
+ if (post_shift)
+ {
+ append_pattern_def_seq (stmt_vinfo, def_stmt);
+
+ q = vect_recog_temp_ssa_var (itype, NULL);
+ def_stmt
+ = gimple_build_assign_with_ops (RSHIFT_EXPR, q, t2,
+ build_int_cst (itype,
+ post_shift));
+ }
+ else
+ q = t2;
+
+ pattern_stmt = def_stmt;
+ }
+ }
+ else
+ {
+ unsigned HOST_WIDE_INT ml;
+ int post_shift;
+ HOST_WIDE_INT d = TREE_INT_CST_LOW (oprnd1);
+ unsigned HOST_WIDE_INT abs_d;
+ bool add = false;
+ tree t1, t2, t3, t4;
+
+ /* Give up for -1. */
+ if (d == -1)
+ return NULL;
+
+ /* Since d might be INT_MIN, we have to cast to
+ unsigned HOST_WIDE_INT before negating to avoid
+ undefined signed overflow. */
+ abs_d = (d >= 0
+ ? (unsigned HOST_WIDE_INT) d
+ : - (unsigned HOST_WIDE_INT) d);
+
+ /* n rem d = n rem -d */
+ if (rhs_code == TRUNC_MOD_EXPR && d < 0)
+ {
+ d = abs_d;
+ oprnd1 = build_int_cst (itype, abs_d);
+ }
+ else if (HOST_BITS_PER_WIDE_INT >= prec
+ && abs_d == (unsigned HOST_WIDE_INT) 1 << (prec - 1))
+ /* This case is not handled correctly below. */
+ return NULL;
+
+ choose_multiplier (abs_d, prec, prec - 1, &ml, &post_shift, &dummy_int);
+ if (ml >= (unsigned HOST_WIDE_INT) 1 << (prec - 1))
+ {
+ add = true;
+ ml |= (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
+ }
+ if (post_shift >= prec)
+ return NULL;
+
+ /* 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));
+
+ if (add)
+ {
+ /* t2 = t1 + oprnd0; */
append_pattern_def_seq (stmt_vinfo, def_stmt);
- var = vect_recog_temp_ssa_var (utype, NULL);
+ t2 = vect_recog_temp_ssa_var (itype, NULL);
def_stmt
- = gimple_build_assign_with_ops (RSHIFT_EXPR, var,
- gimple_assign_lhs (def_stmt),
- shift);
- def_stmt_vinfo = new_stmt_vec_info (def_stmt, loop_vinfo, NULL);
- set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
- STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecutype;
+ = gimple_build_assign_with_ops (PLUS_EXPR, t2, t1, oprnd0);
+ }
+ else
+ t2 = t1;
+
+ if (post_shift)
+ {
+ /* t3 = t2 >> post_shift; */
append_pattern_def_seq (stmt_vinfo, def_stmt);
- signmask = vect_recog_temp_ssa_var (itype, NULL);
+ t3 = vect_recog_temp_ssa_var (itype, NULL);
def_stmt
- = gimple_build_assign_with_ops (NOP_EXPR, signmask, var,
- NULL_TREE);
+ = gimple_build_assign_with_ops (RSHIFT_EXPR, t3, t2,
+ build_int_cst (itype, post_shift));
+ }
+ else
+ t3 = t2;
+
+ 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;
+ }
+
+ 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)
+ {
+ tree r, t1;
+
+ /* We divided. Now finish by:
+ t1 = q * oprnd1;
+ r = oprnd0 - t1; */
+ append_pattern_def_seq (stmt_vinfo, pattern_stmt);
+
+ t1 = vect_recog_temp_ssa_var (itype, NULL);
def_stmt
- = gimple_build_assign_with_ops (PLUS_EXPR,
- vect_recog_temp_ssa_var (itype, NULL),
- oprnd0, signmask);
- append_pattern_def_seq (stmt_vinfo, def_stmt);
- def_stmt
- = gimple_build_assign_with_ops (BIT_AND_EXPR,
- vect_recog_temp_ssa_var (itype, NULL),
- gimple_assign_lhs (def_stmt),
- fold_build2 (MINUS_EXPR, itype,
- oprnd1,
- build_int_cst (itype,
- 1)));
+ = gimple_build_assign_with_ops (MULT_EXPR, t1, q, oprnd1);
append_pattern_def_seq (stmt_vinfo, def_stmt);
+ r = vect_recog_temp_ssa_var (itype, NULL);
pattern_stmt
- = gimple_build_assign_with_ops (MINUS_EXPR,
- vect_recog_temp_ssa_var (itype, NULL),
- gimple_assign_lhs (def_stmt),
- signmask);
+ = gimple_build_assign_with_ops (MINUS_EXPR, r, oprnd0, t1);
}
- if (vect_print_dump_info (REPORT_DETAILS))
- print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+ /* Pattern detected. */
+ if (dump_enabled_p ())
+ {
+ 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");
+ }
- VEC_safe_push (gimple, heap, *stmts, last_stmt);
+ stmts->safe_push (last_stmt);
*type_in = vectype;
*type_out = vectype;
S1 a_T = x_t CMP y_t ? b_T : c_T;
where type 'TYPE' is an integral type which has different size
- from 'type'. b_T and c_T are constants and if 'TYPE' is wider
+ from 'type'. b_T and c_T are either constants (and if 'TYPE' is wider
than 'type', the constants need to fit into an integer type
- with the same width as 'type'.
+ with the same width as 'type') or results of conversion from 'type'.
Input:
a_T = (TYPE) a_it; */
static gimple
-vect_recog_mixed_size_cond_pattern (VEC (gimple, heap) **stmts, tree *type_in,
+vect_recog_mixed_size_cond_pattern (vec<gimple> *stmts, tree *type_in,
tree *type_out)
{
- gimple last_stmt = VEC_index (gimple, *stmts, 0);
+ gimple last_stmt = (*stmts)[0];
tree cond_expr, then_clause, else_clause;
stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt), def_stmt_info;
- tree type, vectype, comp_vectype, itype, vecitype;
+ tree type, vectype, comp_vectype, itype = NULL_TREE, vecitype;
enum machine_mode cmpmode;
gimple pattern_stmt, def_stmt;
loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
+ bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_vinfo);
+ tree orig_type0 = NULL_TREE, orig_type1 = NULL_TREE;
+ gimple def_stmt0 = NULL, def_stmt1 = NULL;
+ bool promotion;
+ tree comp_scalar_type;
if (!is_gimple_assign (last_stmt)
|| gimple_assign_rhs_code (last_stmt) != COND_EXPR
then_clause = gimple_assign_rhs2 (last_stmt);
else_clause = gimple_assign_rhs3 (last_stmt);
- if (TREE_CODE (then_clause) != INTEGER_CST
- || TREE_CODE (else_clause) != INTEGER_CST)
- return NULL;
-
if (!COMPARISON_CLASS_P (cond_expr))
return NULL;
- comp_vectype
- = get_vectype_for_scalar_type (TREE_TYPE (TREE_OPERAND (cond_expr, 0)));
+ comp_scalar_type = TREE_TYPE (TREE_OPERAND (cond_expr, 0));
+ comp_vectype = get_vectype_for_scalar_type (comp_scalar_type);
if (comp_vectype == NULL_TREE)
return NULL;
type = gimple_expr_type (last_stmt);
+ if (types_compatible_p (type, comp_scalar_type)
+ || ((TREE_CODE (then_clause) != INTEGER_CST
+ || TREE_CODE (else_clause) != INTEGER_CST)
+ && !INTEGRAL_TYPE_P (comp_scalar_type))
+ || !INTEGRAL_TYPE_P (type))
+ return NULL;
+
+ if ((TREE_CODE (then_clause) != INTEGER_CST
+ && !type_conversion_p (then_clause, last_stmt, false, &orig_type0,
+ &def_stmt0, &promotion))
+ || (TREE_CODE (else_clause) != INTEGER_CST
+ && !type_conversion_p (else_clause, last_stmt, false, &orig_type1,
+ &def_stmt1, &promotion)))
+ return NULL;
+
+ if (orig_type0 && orig_type1
+ && !types_compatible_p (orig_type0, orig_type1))
+ return NULL;
+
+ if (orig_type0)
+ {
+ if (!types_compatible_p (orig_type0, comp_scalar_type))
+ return NULL;
+ then_clause = gimple_assign_rhs1 (def_stmt0);
+ itype = orig_type0;
+ }
+
+ if (orig_type1)
+ {
+ if (!types_compatible_p (orig_type1, comp_scalar_type))
+ return NULL;
+ else_clause = gimple_assign_rhs1 (def_stmt1);
+ itype = orig_type1;
+ }
+
cmpmode = GET_MODE_INNER (TYPE_MODE (comp_vectype));
if (GET_MODE_BITSIZE (TYPE_MODE (type)) == GET_MODE_BITSIZE (cmpmode))
if (expand_vec_cond_expr_p (vectype, comp_vectype))
return NULL;
- itype = build_nonstandard_integer_type (GET_MODE_BITSIZE (cmpmode),
- TYPE_UNSIGNED (type));
+ if (itype == NULL_TREE)
+ itype = build_nonstandard_integer_type (GET_MODE_BITSIZE (cmpmode),
+ TYPE_UNSIGNED (type));
+
if (itype == NULL_TREE
|| GET_MODE_BITSIZE (TYPE_MODE (itype)) != GET_MODE_BITSIZE (cmpmode))
return NULL;
if (GET_MODE_BITSIZE (TYPE_MODE (type)) > GET_MODE_BITSIZE (cmpmode))
{
- if (!int_fits_type_p (then_clause, itype)
- || !int_fits_type_p (else_clause, itype))
+ if ((TREE_CODE (then_clause) == INTEGER_CST
+ && !int_fits_type_p (then_clause, itype))
+ || (TREE_CODE (else_clause) == INTEGER_CST
+ && !int_fits_type_p (else_clause, itype)))
return NULL;
}
def_stmt
- = gimple_build_assign_with_ops3 (COND_EXPR,
- vect_recog_temp_ssa_var (itype, NULL),
- unshare_expr (cond_expr),
- fold_convert (itype, then_clause),
- fold_convert (itype, else_clause));
+ = gimple_build_assign_with_ops (COND_EXPR,
+ vect_recog_temp_ssa_var (itype, NULL),
+ unshare_expr (cond_expr),
+ fold_convert (itype, then_clause),
+ fold_convert (itype, else_clause));
pattern_stmt
= gimple_build_assign_with_ops (NOP_EXPR,
vect_recog_temp_ssa_var (type, NULL),
gimple_assign_lhs (def_stmt), NULL_TREE);
new_pattern_def_seq (stmt_vinfo, def_stmt);
- def_stmt_info = new_stmt_vec_info (def_stmt, loop_vinfo, NULL);
+ def_stmt_info = new_stmt_vec_info (def_stmt, loop_vinfo, bb_vinfo);
set_vinfo_for_stmt (def_stmt, def_stmt_info);
STMT_VINFO_VECTYPE (def_stmt_info) = vecitype;
*type_in = vecitype;
*type_out = vectype;
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "vect_recog_mixed_size_cond_pattern: detected:\n");
+
return pattern_stmt;
}
true if bool VAR can be optimized that way. */
static bool
-check_bool_pattern (tree var, loop_vec_info loop_vinfo)
+check_bool_pattern (tree var, loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
{
gimple def_stmt;
enum vect_def_type dt;
tree def, rhs1;
enum tree_code rhs_code;
- if (!vect_is_simple_use (var, loop_vinfo, NULL, &def_stmt, &def, &dt))
+ if (!vect_is_simple_use (var, NULL, loop_vinfo, bb_vinfo, &def_stmt, &def,
+ &dt))
return false;
if (dt != vect_internal_def)
switch (rhs_code)
{
case SSA_NAME:
- return check_bool_pattern (rhs1, loop_vinfo);
+ return check_bool_pattern (rhs1, loop_vinfo, bb_vinfo);
CASE_CONVERT:
if ((TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
|| !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
&& TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE)
return false;
- return check_bool_pattern (rhs1, loop_vinfo);
+ return check_bool_pattern (rhs1, loop_vinfo, bb_vinfo);
case BIT_NOT_EXPR:
- return check_bool_pattern (rhs1, loop_vinfo);
+ return check_bool_pattern (rhs1, loop_vinfo, bb_vinfo);
case BIT_AND_EXPR:
case BIT_IOR_EXPR:
case BIT_XOR_EXPR:
- if (!check_bool_pattern (rhs1, loop_vinfo))
+ if (!check_bool_pattern (rhs1, loop_vinfo, bb_vinfo))
return false;
- return check_bool_pattern (gimple_assign_rhs2 (def_stmt), loop_vinfo);
+ return check_bool_pattern (gimple_assign_rhs2 (def_stmt), loop_vinfo,
+ bb_vinfo);
default:
if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
{
tree vecitype, comp_vectype;
+ /* If the comparison can throw, then is_gimple_condexpr will be
+ false and we can't make a COND_EXPR/VEC_COND_EXPR out of it. */
+ if (stmt_could_throw_p (def_stmt))
+ return false;
+
comp_vectype = get_vectype_for_scalar_type (TREE_TYPE (rhs1));
if (comp_vectype == NULL_TREE)
return false;
static tree
adjust_bool_pattern (tree var, tree out_type, tree trueval,
- VEC (gimple, heap) **stmts)
+ vec<gimple> *stmts)
{
gimple stmt = SSA_NAME_DEF_STMT (var);
enum tree_code rhs_code, def_rhs_code;
gimple tstmt;
stmt_vec_info stmt_def_vinfo = vinfo_for_stmt (def_stmt);
irhs2 = adjust_bool_pattern (rhs2, out_type, irhs1, stmts);
- tstmt = VEC_pop (gimple, *stmts);
+ tstmt = stmts->pop ();
gcc_assert (tstmt == def_stmt);
- VEC_quick_push (gimple, *stmts, stmt);
+ stmts->quick_push (stmt);
STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt))
= STMT_VINFO_RELATED_STMT (stmt_def_vinfo);
gcc_assert (!STMT_VINFO_PATTERN_DEF_SEQ (stmt_def_vinfo));
gimple tstmt;
stmt_vec_info stmt_def_vinfo = vinfo_for_stmt (def_stmt);
irhs1 = adjust_bool_pattern (rhs1, out_type, irhs2, stmts);
- tstmt = VEC_pop (gimple, *stmts);
+ tstmt = stmts->pop ();
gcc_assert (tstmt == def_stmt);
- VEC_quick_push (gimple, *stmts, stmt);
+ stmts->quick_push (stmt);
STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt))
= STMT_VINFO_RELATED_STMT (stmt_def_vinfo);
gcc_assert (!STMT_VINFO_PATTERN_DEF_SEQ (stmt_def_vinfo));
default:
gcc_assert (TREE_CODE_CLASS (rhs_code) == tcc_comparison);
if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE
- || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
+ || !TYPE_UNSIGNED (TREE_TYPE (rhs1))
+ || (TYPE_PRECISION (TREE_TYPE (rhs1))
+ != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1)))))
{
enum machine_mode mode = TYPE_MODE (TREE_TYPE (rhs1));
itype
gcc_checking_assert (useless_type_conversion_p (itype,
TREE_TYPE (trueval)));
pattern_stmt
- = gimple_build_assign_with_ops3 (COND_EXPR,
- vect_recog_temp_ssa_var (itype, NULL),
- cond_expr, trueval,
- build_int_cst (itype, 0));
+ = gimple_build_assign_with_ops (COND_EXPR,
+ vect_recog_temp_ssa_var (itype, NULL),
+ cond_expr, trueval,
+ build_int_cst (itype, 0));
break;
}
- VEC_safe_push (gimple, heap, *stmts, stmt);
+ stmts->safe_push (stmt);
gimple_set_location (pattern_stmt, loc);
STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt)) = pattern_stmt;
return gimple_assign_lhs (pattern_stmt);
but the above is more efficient. */
static gimple
-vect_recog_bool_pattern (VEC (gimple, heap) **stmts, tree *type_in,
+vect_recog_bool_pattern (vec<gimple> *stmts, tree *type_in,
tree *type_out)
{
- gimple last_stmt = VEC_pop (gimple, *stmts);
+ gimple last_stmt = stmts->pop ();
enum tree_code rhs_code;
tree var, lhs, rhs, vectype;
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);
gimple pattern_stmt;
if (!is_gimple_assign (last_stmt))
if (vectype == NULL_TREE)
return NULL;
- if (!check_bool_pattern (var, loop_vinfo))
+ if (!check_bool_pattern (var, loop_vinfo, bb_vinfo))
return NULL;
rhs = adjust_bool_pattern (var, TREE_TYPE (lhs), NULL_TREE, stmts);
= gimple_build_assign_with_ops (NOP_EXPR, lhs, rhs, NULL_TREE);
*type_out = vectype;
*type_in = vectype;
- VEC_safe_push (gimple, heap, *stmts, last_stmt);
+ stmts->safe_push (last_stmt);
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "vect_recog_bool_pattern: detected:\n");
+
return pattern_stmt;
}
else if (rhs_code == SSA_NAME
gcc_assert (vectype != NULL_TREE);
if (!VECTOR_MODE_P (TYPE_MODE (vectype)))
return NULL;
- if (!check_bool_pattern (var, loop_vinfo))
+ if (!check_bool_pattern (var, loop_vinfo, bb_vinfo))
return NULL;
rhs = adjust_bool_pattern (var, TREE_TYPE (vectype), NULL_TREE, stmts);
}
pattern_stmt
= gimple_build_assign_with_ops (SSA_NAME, lhs, rhs, NULL_TREE);
- pattern_stmt_info = new_stmt_vec_info (pattern_stmt, loop_vinfo, NULL);
+ pattern_stmt_info = new_stmt_vec_info (pattern_stmt, loop_vinfo,
+ bb_vinfo);
set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
STMT_VINFO_DATA_REF (pattern_stmt_info)
= STMT_VINFO_DATA_REF (stmt_vinfo);
DR_STMT (STMT_VINFO_DATA_REF (stmt_vinfo)) = pattern_stmt;
*type_out = vectype;
*type_in = vectype;
- VEC_safe_push (gimple, heap, *stmts, last_stmt);
+ stmts->safe_push (last_stmt);
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "vect_recog_bool_pattern: detected:\n");
return pattern_stmt;
}
else
stmt_vec_info pattern_stmt_info, def_stmt_info;
stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (orig_stmt_info);
+ bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (orig_stmt_info);
gimple def_stmt;
pattern_stmt_info = vinfo_for_stmt (pattern_stmt);
if (pattern_stmt_info == NULL)
{
- pattern_stmt_info = new_stmt_vec_info (pattern_stmt, loop_vinfo, NULL);
+ pattern_stmt_info = new_stmt_vec_info (pattern_stmt, loop_vinfo,
+ bb_vinfo);
set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
}
gimple_set_bb (pattern_stmt, gimple_bb (orig_stmt));
def_stmt_info = vinfo_for_stmt (def_stmt);
if (def_stmt_info == NULL)
{
- def_stmt_info = new_stmt_vec_info (def_stmt, loop_vinfo, NULL);
+ def_stmt_info = new_stmt_vec_info (def_stmt, loop_vinfo,
+ bb_vinfo);
set_vinfo_for_stmt (def_stmt, def_stmt_info);
}
gimple_set_bb (def_stmt, gimple_bb (orig_stmt));
static void
vect_pattern_recog_1 (vect_recog_func_ptr vect_recog_func,
gimple_stmt_iterator si,
- VEC (gimple, heap) **stmts_to_replace)
+ vec<gimple> *stmts_to_replace)
{
gimple stmt = gsi_stmt (si), pattern_stmt;
stmt_vec_info stmt_info;
int i;
gimple next;
- VEC_truncate (gimple, *stmts_to_replace, 0);
- VEC_quick_push (gimple, *stmts_to_replace, stmt);
+ stmts_to_replace->truncate (0);
+ stmts_to_replace->quick_push (stmt);
pattern_stmt = (* vect_recog_func) (stmts_to_replace, &type_in, &type_out);
if (!pattern_stmt)
return;
- stmt = VEC_last (gimple, *stmts_to_replace);
+ stmt = stmts_to_replace->last ();
stmt_info = vinfo_for_stmt (stmt);
loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
}
/* Found a vectorizable pattern. */
- if (vect_print_dump_info (REPORT_DETAILS))
+ if (dump_enabled_p ())
{
- fprintf (vect_dump, "pattern recognized: ");
- print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+ 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. */
/* Patterns cannot be vectorized using SLP, because they change the order of
computation. */
- FOR_EACH_VEC_ELT (gimple, LOOP_VINFO_REDUCTIONS (loop_vinfo), i, next)
- if (next == stmt)
- VEC_ordered_remove (gimple, LOOP_VINFO_REDUCTIONS (loop_vinfo), i);
+ if (loop_vinfo)
+ FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTIONS (loop_vinfo), i, next)
+ if (next == stmt)
+ LOOP_VINFO_REDUCTIONS (loop_vinfo).ordered_remove (i);
/* It is possible that additional pattern stmts are created and inserted in
STMTS_TO_REPLACE. We create a stmt_info for each of them, and mark the
relevant statements. */
- for (i = 0; VEC_iterate (gimple, *stmts_to_replace, i, stmt)
- && (unsigned) i < (VEC_length (gimple, *stmts_to_replace) - 1);
+ for (i = 0; stmts_to_replace->iterate (i, &stmt)
+ && (unsigned) i < (stmts_to_replace->length () - 1);
i++)
{
stmt_info = vinfo_for_stmt (stmt);
pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
- if (vect_print_dump_info (REPORT_DETAILS))
+ if (dump_enabled_p ())
{
- fprintf (vect_dump, "additional pattern stmt: ");
- print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+ 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);
be recorded in S3. */
void
-vect_pattern_recog (loop_vec_info loop_vinfo)
+vect_pattern_recog (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
{
- struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
- basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
- unsigned int nbbs = loop->num_nodes;
+ struct loop *loop;
+ basic_block *bbs;
+ unsigned int nbbs;
gimple_stmt_iterator si;
unsigned int i, j;
vect_recog_func_ptr vect_recog_func;
- VEC (gimple, heap) *stmts_to_replace = VEC_alloc (gimple, heap, 1);
+ stack_vec<gimple, 1> stmts_to_replace;
+ gimple stmt;
- if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "=== vect_pattern_recog ===");
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "=== vect_pattern_recog ===\n");
+
+ if (loop_vinfo)
+ {
+ loop = LOOP_VINFO_LOOP (loop_vinfo);
+ bbs = LOOP_VINFO_BBS (loop_vinfo);
+ nbbs = loop->num_nodes;
+ }
+ else
+ {
+ bbs = &BB_VINFO_BB (bb_vinfo);
+ nbbs = 1;
+ }
/* Scan through the loop stmts, applying the pattern recognition
functions starting at each stmt visited: */
basic_block bb = bbs[i];
for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
{
+ if (bb_vinfo && (stmt = gsi_stmt (si))
+ && vinfo_for_stmt (stmt)
+ && !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt)))
+ continue;
+
/* Scan over all generic vect_recog_xxx_pattern functions. */
for (j = 0; j < NUM_PATTERNS; j++)
{
}
}
}
-
- VEC_free (gimple, heap, stmts_to_replace);
}
projects / thirdparty / gcc.git / blobdiff