/* Analysis Utilities for Loop Vectorization.
- Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
+ Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012
Free Software Foundation, Inc.
Contributed by Dorit Nuzman <dorit@il.ibm.com>
static gimple vect_recog_pow_pattern (VEC (gimple, heap) **, tree *, tree *);
static gimple vect_recog_over_widening_pattern (VEC (gimple, heap) **, tree *,
tree *);
+static gimple vect_recog_widen_shift_pattern (VEC (gimple, heap) **,
+ tree *, tree *);
+static gimple vect_recog_vector_vector_shift_pattern (VEC (gimple, heap) **,
+ 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) **,
+ tree *, tree *);
+static gimple vect_recog_bool_pattern (VEC (gimple, heap) **, 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_vector_vector_shift_pattern,
+ vect_recog_sdivmod_pow2_pattern,
+ vect_recog_mixed_size_cond_pattern,
+ vect_recog_bool_pattern};
+static inline void
+append_pattern_def_seq (stmt_vec_info stmt_info, gimple stmt)
+{
+ gimple_seq_add_stmt_without_update (&STMT_VINFO_PATTERN_DEF_SEQ (stmt_info),
+ stmt);
+}
+
+static inline void
+new_pattern_def_seq (stmt_vec_info stmt_info, gimple stmt)
+{
+ STMT_VINFO_PATTERN_DEF_SEQ (stmt_info) = NULL;
+ append_pattern_def_seq (stmt_info, stmt);
+}
+
+/* If the LHS of DEF_STMT has a single use, and that statement is
+ in the same loop, return it. */
+
+static gimple
+vect_single_imm_use (gimple def_stmt)
+{
+ stmt_vec_info stmt_vinfo = vinfo_for_stmt (def_stmt);
+ loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
+ struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
+ 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 (!gimple_bb (use_stmt))
+ return NULL;
+
+ if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
+ return NULL;
+
+ gcc_assert (vinfo_for_stmt (use_stmt));
+ return use_stmt;
+}
/* Function widened_name_p
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))
+ if (!vect_is_simple_use (name, use_stmt, loop_vinfo, NULL, def_stmt, &def,
+ &dt))
return false;
if (dt != vect_internal_def
|| (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 2)))
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,
+ NULL, &dummy_gimple, &dummy, &dt))
return false;
return true;
}
-/* Handle two cases of multiplication by a constant. The first one is when
- the constant, CONST_OPRND, fits the type (HALF_TYPE) of the second
- operand (OPRND). In that case, we can peform widen-mult from HALF_TYPE to
- TYPE.
+/* Handle widening operation by a constant. At the moment we support MULT_EXPR
+ and LSHIFT_EXPR.
+
+ For MULT_EXPR we check that CONST_OPRND fits HALF_TYPE, and for LSHIFT_EXPR
+ we check that CONST_OPRND is less or equal to the size of HALF_TYPE.
Otherwise, if the type of the result (TYPE) is at least 4 times bigger than
- HALF_TYPE, and CONST_OPRND fits an intermediate type (2 times smaller than
- TYPE), we can perform widen-mult from the intermediate type to TYPE and
- replace a_T = (TYPE) a_t; with a_it - (interm_type) a_t; */
+ HALF_TYPE, and there is an intermediate type (2 times smaller than TYPE)
+ that satisfies the above restrictions, we can perform a widening opeartion
+ from the intermediate type to TYPE and replace a_T = (TYPE) a_t;
+ with a_it = (interm_type) a_t; */
static bool
-vect_handle_widen_mult_by_const (gimple stmt, tree const_oprnd, tree *oprnd,
- VEC (gimple, heap) **stmts, tree type,
- tree *half_type, gimple def_stmt)
+vect_handle_widen_op_by_const (gimple stmt, enum tree_code code,
+ tree const_oprnd, tree *oprnd,
+ VEC (gimple, heap) **stmts, tree type,
+ tree *half_type, gimple def_stmt)
{
tree new_type, new_oprnd, tmp;
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 (int_fits_type_p (const_oprnd, *half_type))
+ if (code != MULT_EXPR && code != LSHIFT_EXPR)
+ return false;
+
+ if (((code == MULT_EXPR && int_fits_type_p (const_oprnd, *half_type))
+ || (code == LSHIFT_EXPR
+ && compare_tree_int (const_oprnd, TYPE_PRECISION (*half_type))
+ != 1))
+ && TYPE_PRECISION (type) == (TYPE_PRECISION (*half_type) * 2))
{
/* CONST_OPRND is a constant of HALF_TYPE. */
*oprnd = gimple_assign_rhs1 (def_stmt);
|| !vinfo_for_stmt (def_stmt))
return false;
- /* TYPE is 4 times bigger than HALF_TYPE, try widen-mult for
+ /* TYPE is 4 times bigger than HALF_TYPE, try widening operation for
a type 2 times bigger than HALF_TYPE. */
new_type = build_nonstandard_integer_type (TYPE_PRECISION (type) / 2,
TYPE_UNSIGNED (type));
- if (!int_fits_type_p (const_oprnd, new_type))
+ if ((code == MULT_EXPR && !int_fits_type_p (const_oprnd, new_type))
+ || (code == LSHIFT_EXPR
+ && compare_tree_int (const_oprnd, TYPE_PRECISION (new_type)) == 1))
return false;
- /* Use NEW_TYPE for widen_mult. */
+ /* Use NEW_TYPE for widening operation. */
if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)))
{
new_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
|| TREE_TYPE (gimple_assign_lhs (new_stmt)) != new_type)
return false;
+ VEC_safe_push (gimple, heap, *stmts, def_stmt);
*oprnd = gimple_assign_lhs (new_stmt);
}
else
enum tree_code dummy_code;
int dummy_int;
VEC (tree, heap) *dummy_vec;
- bool op0_ok, op1_ok;
+ bool op1_ok;
if (!is_gimple_assign (last_stmt))
return NULL;
return NULL;
/* Check argument 0. */
- op0_ok = widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0, false);
+ if (!widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0, false))
+ return NULL;
/* Check argument 1. */
op1_ok = widened_name_p (oprnd1, last_stmt, &half_type1, &def_stmt1, false);
- /* In case of multiplication by a constant one of the operands may not match
- the pattern, but not both. */
- if (!op0_ok && !op1_ok)
- return NULL;
-
- if (op0_ok && op1_ok)
+ if (op1_ok)
{
oprnd0 = gimple_assign_rhs1 (def_stmt0);
oprnd1 = gimple_assign_rhs1 (def_stmt1);
}
- else if (!op0_ok)
- {
- if (TREE_CODE (oprnd0) == INTEGER_CST
- && TREE_CODE (half_type1) == INTEGER_TYPE
- && vect_handle_widen_mult_by_const (last_stmt, oprnd0, &oprnd1,
- stmts, type,
- &half_type1, def_stmt1))
- half_type0 = half_type1;
- else
- return NULL;
- }
- else if (!op1_ok)
+ else
{
if (TREE_CODE (oprnd1) == INTEGER_CST
&& TREE_CODE (half_type0) == INTEGER_TYPE
- && vect_handle_widen_mult_by_const (last_stmt, oprnd1, &oprnd0,
- stmts, type,
- &half_type0, def_stmt0))
+ && vect_handle_widen_op_by_const (last_stmt, MULT_EXPR, oprnd1,
+ &oprnd0, stmts, type,
+ &half_type0, def_stmt0))
half_type1 = half_type0;
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)
+ 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;
NEW_DEF_STMT - in case DEF has to be promoted, we create two pattern
statements for STMT: the first one is a type promotion and the second
one is the operation itself. We return the type promotion statement
- in NEW_DEF_STMT and further store it in STMT_VINFO_PATTERN_DEF_STMT of
+ in NEW_DEF_STMT and further store it in STMT_VINFO_PATTERN_DEF_SEQ of
the second pattern statement. */
static bool
loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (vinfo_for_stmt (stmt));
struct loop *loop = LOOP_VINFO_LOOP (loop_info);
+ *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)
a. Its type is not sufficient for the operation, we create a new stmt:
a type conversion for OPRND from HALF_TYPE to INTERM_TYPE. We store
this statement in NEW_DEF_STMT, and it is later put in
- STMT_VINFO_PATTERN_DEF_STMT of the pattern statement for STMT.
+ STMT_VINFO_PATTERN_DEF_SEQ of the pattern statement for STMT.
b. OPRND is good to use in the new statement. */
if (first)
{
|| TREE_TYPE (gimple_assign_lhs (new_stmt)) != interm_type)
return false;
+ VEC_safe_push (gimple, heap, *stmts, def_stmt);
oprnd = gimple_assign_lhs (new_stmt);
}
else
constants.
Check if S3 and S4 can be done on a smaller type than 'TYPE', it can either
be 'type' or some intermediate type. For now, we expect S5 to be a type
- demotion operation. We also check that S3 and S4 have only one use.
-.
+ demotion operation. We also check that S3 and S4 have only one use. */
-*/
static gimple
vect_recog_over_widening_pattern (VEC (gimple, heap) **stmts,
tree *type_in, tree *type_out)
{
gimple stmt = VEC_pop (gimple, *stmts);
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 op0, op1, vectype = NULL_TREE, use_lhs, use_type;
tree var = NULL_TREE, new_type = NULL_TREE, tmp, new_oprnd;
bool first;
- struct loop *loop = (gimple_bb (stmt))->loop_father;
+ tree type = NULL;
first = true;
while (1)
}
/* 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. */
statetments, except for the case when the last statement in the
sequence doesn't have a corresponding pattern statement. In such
case we associate the last pattern statement with the last statement
- in the sequence. Therefore, we only add an original statetement to
+ 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);
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), var,
op0, op1);
STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt)) = pattern_stmt;
- STMT_VINFO_PATTERN_DEF_STMT (vinfo_for_stmt (stmt)) = new_def_stmt;
+ new_pattern_def_seq (vinfo_for_stmt (stmt), new_def_stmt);
if (vect_print_dump_info (REPORT_DETAILS))
{
print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
}
+ type = gimple_expr_type (stmt);
prev_stmt = stmt;
stmt = use_stmt;
{
use_lhs = gimple_assign_lhs (use_stmt);
use_type = TREE_TYPE (use_lhs);
- /* Support only type promotion or signedess change. */
+ /* 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))
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))
{
else
{
if (prev_stmt)
- STMT_VINFO_PATTERN_DEF_STMT (vinfo_for_stmt (use_stmt))
- = STMT_VINFO_PATTERN_DEF_STMT (vinfo_for_stmt (prev_stmt));
+ STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (use_stmt))
+ = STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (prev_stmt));
*type_in = vectype;
*type_out = NULL_TREE;
return pattern_stmt;
}
+/* Detect widening shift pattern:
+
+ type a_t;
+ TYPE a_T, res_T;
+
+ S1 a_t = ;
+ S2 a_T = (TYPE) a_t;
+ S3 res_T = a_T << CONST;
+
+ where type 'TYPE' is at least double the size of type 'type'.
+
+ 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:
+
+ 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 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
+ intermediate type, and perform widen-shift on the intermediate type:
+
+ type a_t;
+ interm_type a_it;
+ TYPE a_T, res_T, res_T';
+
+ S1 a_t = ;
+ S2 a_T = (TYPE) a_t;
+ '--> a_it = (interm_type) a_t;
+ S3 res_T = a_T << CONST;
+ '--> res_T' = a_it <<* CONST;
+
+ Input/Output:
+
+ * STMTS: Contains a stmt from which the pattern search begins.
+ In case of unsigned widen-shift, the original stmt (S3) is replaced with S4
+ in STMTS. When an intermediate type is used and a pattern statement is
+ created for S2, we also put S2 here (before S3).
+
+ 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 sequence of
+ stmts that constitute the pattern. In this case it will be:
+ WIDEN_LSHIFT_EXPR <a_t, CONST>. */
+
+static gimple
+vect_recog_widen_shift_pattern (VEC (gimple, heap) **stmts,
+ tree *type_in, tree *type_out)
+{
+ gimple last_stmt = VEC_pop (gimple, *stmts);
+ gimple def_stmt0;
+ tree oprnd0, oprnd1;
+ tree type, half_type0;
+ 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;
+
+ if (!is_gimple_assign (last_stmt) || !vinfo_for_stmt (last_stmt))
+ return NULL;
+
+ if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (last_stmt)))
+ return NULL;
+
+ if (gimple_assign_rhs_code (last_stmt) != LSHIFT_EXPR)
+ return NULL;
+
+ oprnd0 = gimple_assign_rhs1 (last_stmt);
+ oprnd1 = gimple_assign_rhs2 (last_stmt);
+ if (TREE_CODE (oprnd0) != SSA_NAME || TREE_CODE (oprnd1) != INTEGER_CST)
+ 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;
+
+ /* Check operand 1: has to be positive. We check that it fits the type
+ in vect_handle_widen_op_by_const (). */
+ if (tree_int_cst_compare (oprnd1, size_zero_node) <= 0)
+ return NULL;
+
+ 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;
+
+ /* Pattern detected. */
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "vect_recog_widen_shift_pattern: detected: ");
+
+ /* Check target support. */
+ vectype = get_vectype_for_scalar_type (half_type0);
+ vectype_out = get_vectype_for_scalar_type (type);
+
+ if (!vectype
+ || !vectype_out
+ || !supportable_widening_operation (WIDEN_LSHIFT_EXPR, last_stmt,
+ vectype_out, vectype,
+ &dummy, &dummy, &dummy_code,
+ &dummy_code, &dummy_int,
+ &dummy_vec))
+ return NULL;
+
+ *type_in = vectype;
+ *type_out = vectype_out;
+
+ /* 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 (WIDEN_LSHIFT_EXPR, var, oprnd0, oprnd1);
+
+ if (vect_print_dump_info (REPORT_DETAILS))
+ print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+
+ VEC_safe_push (gimple, heap, *stmts, last_stmt);
+ return pattern_stmt;
+}
+
+/* Detect a vector by vector shift pattern that wouldn't be otherwise
+ vectorized:
+
+ type a_t;
+ TYPE b_T, res_T;
+
+ S1 a_t = ;
+ S2 b_T = ;
+ S3 res_T = b_T op a_t;
+
+ where type 'TYPE' is a type with different size than 'type',
+ and op is <<, >> or rotate.
+
+ Also detect cases:
+
+ type a_t;
+ TYPE b_T, c_T, res_T;
+
+ S0 c_T = ;
+ S1 a_t = (type) c_T;
+ S2 b_T = ;
+ S3 res_T = b_T op a_t;
+
+ Input/Output:
+
+ * STMTS: Contains a stmt from which the pattern search begins,
+ i.e. the shift/rotate stmt. The original stmt (S3) is replaced
+ with a shift/rotate which has same type on both operands, in the
+ second case just b_T op c_T, in the first case with added cast
+ from a_t to c_T in STMT_VINFO_PATTERN_DEF_SEQ.
+
+ 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 shift/rotate
+ S3 stmt. */
+
+static gimple
+vect_recog_vector_vector_shift_pattern (VEC (gimple, heap) **stmts,
+ tree *type_in, tree *type_out)
+{
+ gimple last_stmt = VEC_pop (gimple, *stmts);
+ 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);
+ enum vect_def_type dt;
+ tree def;
+
+ if (!is_gimple_assign (last_stmt))
+ return NULL;
+
+ rhs_code = gimple_assign_rhs_code (last_stmt);
+ switch (rhs_code)
+ {
+ case LSHIFT_EXPR:
+ case RSHIFT_EXPR:
+ 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);
+ oprnd1 = gimple_assign_rhs2 (last_stmt);
+ if (TREE_CODE (oprnd0) != SSA_NAME
+ || TREE_CODE (oprnd1) != SSA_NAME
+ || TYPE_MODE (TREE_TYPE (oprnd0)) == TYPE_MODE (TREE_TYPE (oprnd1))
+ || TYPE_PRECISION (TREE_TYPE (oprnd1))
+ != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (oprnd1)))
+ || TYPE_PRECISION (TREE_TYPE (lhs))
+ != TYPE_PRECISION (TREE_TYPE (oprnd0)))
+ return NULL;
+
+ if (!vect_is_simple_use (oprnd1, last_stmt, loop_vinfo, NULL, &def_stmt,
+ &def, &dt))
+ return NULL;
+
+ if (dt != vect_internal_def)
+ return NULL;
+
+ *type_in = get_vectype_for_scalar_type (TREE_TYPE (oprnd0));
+ *type_out = *type_in;
+ if (*type_in == NULL_TREE)
+ return NULL;
+
+ def = NULL_TREE;
+ if (gimple_assign_cast_p (def_stmt))
+ {
+ tree rhs1 = gimple_assign_rhs1 (def_stmt);
+ if (TYPE_MODE (TREE_TYPE (rhs1)) == TYPE_MODE (TREE_TYPE (oprnd0))
+ && TYPE_PRECISION (TREE_TYPE (rhs1))
+ == TYPE_PRECISION (TREE_TYPE (oprnd0)))
+ def = rhs1;
+ }
+
+ if (def == NULL_TREE)
+ {
+ def = vect_recog_temp_ssa_var (TREE_TYPE (oprnd0), NULL);
+ def_stmt = gimple_build_assign_with_ops (NOP_EXPR, def, oprnd1,
+ NULL_TREE);
+ new_pattern_def_seq (stmt_vinfo, def_stmt);
+ }
+
+ /* Pattern detected. */
+ if (vect_print_dump_info (REPORT_DETAILS))
+ fprintf (vect_dump, "vect_recog_vector_vector_shift_pattern: detected: ");
+
+ /* 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);
+
+ VEC_safe_push (gimple, heap, *stmts, last_stmt);
+ return pattern_stmt;
+}
+
+/* Detect a signed division by power of two 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.
+
+ Similarly handle signed modulo by power of two 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:
+ 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):
+ 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;
+ S6 w_t = b_t + z_t;
+ S5 x_t = w_t & (N - 1);
+ S4' a_t = x_t - z_t;
+
+ 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 division
+ S1 or modulo S4 stmt. */
+
+static gimple
+vect_recog_sdivmod_pow2_pattern (VEC (gimple, heap) **stmts,
+ tree *type_in, tree *type_out)
+{
+ gimple last_stmt = VEC_pop (gimple, *stmts);
+ 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);
+ optab optab;
+
+ if (!is_gimple_assign (last_stmt))
+ return NULL;
+
+ rhs_code = gimple_assign_rhs_code (last_stmt);
+ switch (rhs_code)
+ {
+ case TRUNC_DIV_EXPR:
+ case TRUNC_MOD_EXPR:
+ break;
+ default:
+ return NULL;
+ }
+
+ if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
+ return NULL;
+
+ oprnd0 = gimple_assign_rhs1 (last_stmt);
+ oprnd1 = gimple_assign_rhs2 (last_stmt);
+ itype = TREE_TYPE (oprnd0);
+ 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)
+ return NULL;
+
+ vectype = get_vectype_for_scalar_type (itype);
+ if (vectype == NULL_TREE)
+ return NULL;
+
+ /* 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)
+ {
+ 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)
+ 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)
+ {
+ 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);
+
+ pattern_stmt
+ = gimple_build_assign_with_ops (RSHIFT_EXPR,
+ vect_recog_temp_ssa_var (itype, NULL),
+ var,
+ build_int_cst (itype,
+ tree_log2 (oprnd1)));
+ }
+ 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_ops3 (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 (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;
+
+ 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;
+ 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, NULL);
+ 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 (vect_print_dump_info (REPORT_DETAILS))
+ print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
+
+ VEC_safe_push (gimple, heap, *stmts, last_stmt);
+
+ *type_in = vectype;
+ *type_out = vectype;
+ return pattern_stmt;
+}
+
+/* Function vect_recog_mixed_size_cond_pattern
+
+ Try to find the following pattern:
+
+ type x_t, y_t;
+ TYPE a_T, b_T, c_T;
+ loop:
+ 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
+ than 'type', the constants need to fit into an integer type
+ with the same width as 'type'.
+
+ Input:
+
+ * LAST_STMT: A stmt from which the pattern search begins.
+
+ 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 pattern.
+ Additionally a def_stmt is added.
+
+ a_it = x_t CMP y_t ? b_it : c_it;
+ a_T = (TYPE) a_it; */
+
+static gimple
+vect_recog_mixed_size_cond_pattern (VEC (gimple, heap) **stmts, tree *type_in,
+ tree *type_out)
+{
+ gimple last_stmt = VEC_index (gimple, *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;
+ enum machine_mode cmpmode;
+ gimple pattern_stmt, def_stmt;
+ loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
+
+ if (!is_gimple_assign (last_stmt)
+ || gimple_assign_rhs_code (last_stmt) != COND_EXPR
+ || STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_internal_def)
+ return NULL;
+
+ cond_expr = gimple_assign_rhs1 (last_stmt);
+ 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)));
+ if (comp_vectype == NULL_TREE)
+ return NULL;
+
+ type = gimple_expr_type (last_stmt);
+ cmpmode = GET_MODE_INNER (TYPE_MODE (comp_vectype));
+
+ if (GET_MODE_BITSIZE (TYPE_MODE (type)) == GET_MODE_BITSIZE (cmpmode))
+ return NULL;
+
+ vectype = get_vectype_for_scalar_type (type);
+ if (vectype == NULL_TREE)
+ return NULL;
+
+ 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
+ || GET_MODE_BITSIZE (TYPE_MODE (itype)) != GET_MODE_BITSIZE (cmpmode))
+ return NULL;
+
+ vecitype = get_vectype_for_scalar_type (itype);
+ if (vecitype == NULL_TREE)
+ return NULL;
+
+ if (!expand_vec_cond_expr_p (vecitype, comp_vectype))
+ 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))
+ 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));
+ 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);
+ set_vinfo_for_stmt (def_stmt, def_stmt_info);
+ STMT_VINFO_VECTYPE (def_stmt_info) = vecitype;
+ *type_in = vecitype;
+ *type_out = vectype;
+
+ return pattern_stmt;
+}
+
+
+/* Helper function of vect_recog_bool_pattern. Called recursively, return
+ true if bool VAR can be optimized that way. */
+
+static bool
+check_bool_pattern (tree var, loop_vec_info loop_vinfo)
+{
+ gimple def_stmt;
+ enum vect_def_type dt;
+ tree def, rhs1;
+ enum tree_code rhs_code;
+
+ if (!vect_is_simple_use (var, NULL, loop_vinfo, NULL, &def_stmt, &def, &dt))
+ return false;
+
+ if (dt != vect_internal_def)
+ return false;
+
+ if (!is_gimple_assign (def_stmt))
+ return false;
+
+ if (!has_single_use (def))
+ return false;
+
+ rhs1 = gimple_assign_rhs1 (def_stmt);
+ rhs_code = gimple_assign_rhs_code (def_stmt);
+ switch (rhs_code)
+ {
+ case SSA_NAME:
+ return check_bool_pattern (rhs1, loop_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);
+
+ case BIT_NOT_EXPR:
+ return check_bool_pattern (rhs1, loop_vinfo);
+
+ case BIT_AND_EXPR:
+ case BIT_IOR_EXPR:
+ case BIT_XOR_EXPR:
+ if (!check_bool_pattern (rhs1, loop_vinfo))
+ return false;
+ return check_bool_pattern (gimple_assign_rhs2 (def_stmt), loop_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;
+
+ if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE)
+ {
+ enum machine_mode mode = TYPE_MODE (TREE_TYPE (rhs1));
+ tree itype
+ = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode), 1);
+ vecitype = get_vectype_for_scalar_type (itype);
+ if (vecitype == NULL_TREE)
+ return false;
+ }
+ else
+ vecitype = comp_vectype;
+ return expand_vec_cond_expr_p (vecitype, comp_vectype);
+ }
+ return false;
+ }
+}
+
+
+/* Helper function of adjust_bool_pattern. Add a cast to TYPE to a previous
+ stmt (SSA_NAME_DEF_STMT of VAR) by moving the COND_EXPR from RELATED_STMT
+ to PATTERN_DEF_SEQ and adding a cast as RELATED_STMT. */
+
+static tree
+adjust_bool_pattern_cast (tree type, tree var)
+{
+ stmt_vec_info stmt_vinfo = vinfo_for_stmt (SSA_NAME_DEF_STMT (var));
+ gimple cast_stmt, pattern_stmt;
+
+ gcc_assert (!STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo));
+ pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
+ new_pattern_def_seq (stmt_vinfo, pattern_stmt);
+ cast_stmt
+ = gimple_build_assign_with_ops (NOP_EXPR,
+ vect_recog_temp_ssa_var (type, NULL),
+ gimple_assign_lhs (pattern_stmt),
+ NULL_TREE);
+ STMT_VINFO_RELATED_STMT (stmt_vinfo) = cast_stmt;
+ return gimple_assign_lhs (cast_stmt);
+}
+
+
+/* Helper function of vect_recog_bool_pattern. Do the actual transformations,
+ recursively. VAR is an SSA_NAME that should be transformed from bool
+ to a wider integer type, OUT_TYPE is the desired final integer type of
+ the whole pattern, TRUEVAL should be NULL unless optimizing
+ BIT_AND_EXPR into a COND_EXPR with one integer from one of the operands
+ in the then_clause, STMTS is where statements with added pattern stmts
+ should be pushed to. */
+
+static tree
+adjust_bool_pattern (tree var, tree out_type, tree trueval,
+ VEC (gimple, heap) **stmts)
+{
+ gimple stmt = SSA_NAME_DEF_STMT (var);
+ enum tree_code rhs_code, def_rhs_code;
+ tree itype, cond_expr, rhs1, rhs2, irhs1, irhs2;
+ location_t loc;
+ gimple pattern_stmt, def_stmt;
+
+ rhs1 = gimple_assign_rhs1 (stmt);
+ rhs2 = gimple_assign_rhs2 (stmt);
+ rhs_code = gimple_assign_rhs_code (stmt);
+ loc = gimple_location (stmt);
+ switch (rhs_code)
+ {
+ case SSA_NAME:
+ CASE_CONVERT:
+ irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
+ itype = TREE_TYPE (irhs1);
+ pattern_stmt
+ = gimple_build_assign_with_ops (SSA_NAME,
+ vect_recog_temp_ssa_var (itype, NULL),
+ irhs1, NULL_TREE);
+ break;
+
+ case BIT_NOT_EXPR:
+ irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
+ itype = TREE_TYPE (irhs1);
+ pattern_stmt
+ = gimple_build_assign_with_ops (BIT_XOR_EXPR,
+ vect_recog_temp_ssa_var (itype, NULL),
+ irhs1, build_int_cst (itype, 1));
+ break;
+
+ case BIT_AND_EXPR:
+ /* Try to optimize x = y & (a < b ? 1 : 0); into
+ x = (a < b ? y : 0);
+
+ E.g. for:
+ bool a_b, b_b, c_b;
+ TYPE d_T;
+
+ S1 a_b = x1 CMP1 y1;
+ S2 b_b = x2 CMP2 y2;
+ S3 c_b = a_b & b_b;
+ S4 d_T = (TYPE) c_b;
+
+ we would normally emit:
+
+ S1' a_T = x1 CMP1 y1 ? 1 : 0;
+ S2' b_T = x2 CMP2 y2 ? 1 : 0;
+ S3' c_T = a_T & b_T;
+ S4' d_T = c_T;
+
+ but we can save one stmt by using the
+ result of one of the COND_EXPRs in the other COND_EXPR and leave
+ BIT_AND_EXPR stmt out:
+
+ S1' a_T = x1 CMP1 y1 ? 1 : 0;
+ S3' c_T = x2 CMP2 y2 ? a_T : 0;
+ S4' f_T = c_T;
+
+ At least when VEC_COND_EXPR is implemented using masks
+ cond ? 1 : 0 is as expensive as cond ? var : 0, in both cases it
+ computes the comparison masks and ands it, in one case with
+ all ones vector, in the other case with a vector register.
+ Don't do this for BIT_IOR_EXPR, because cond ? 1 : var; is
+ often more expensive. */
+ def_stmt = SSA_NAME_DEF_STMT (rhs2);
+ def_rhs_code = gimple_assign_rhs_code (def_stmt);
+ if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison)
+ {
+ tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
+ irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
+ if (TYPE_PRECISION (TREE_TYPE (irhs1))
+ == GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (def_rhs1))))
+ {
+ 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);
+ gcc_assert (tstmt == def_stmt);
+ VEC_quick_push (gimple, *stmts, 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));
+ STMT_VINFO_RELATED_STMT (stmt_def_vinfo) = NULL;
+ return irhs2;
+ }
+ else
+ irhs2 = adjust_bool_pattern (rhs2, out_type, NULL_TREE, stmts);
+ goto and_ior_xor;
+ }
+ def_stmt = SSA_NAME_DEF_STMT (rhs1);
+ def_rhs_code = gimple_assign_rhs_code (def_stmt);
+ if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison)
+ {
+ tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
+ irhs2 = adjust_bool_pattern (rhs2, out_type, NULL_TREE, stmts);
+ if (TYPE_PRECISION (TREE_TYPE (irhs2))
+ == GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (def_rhs1))))
+ {
+ 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);
+ gcc_assert (tstmt == def_stmt);
+ VEC_quick_push (gimple, *stmts, 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));
+ STMT_VINFO_RELATED_STMT (stmt_def_vinfo) = NULL;
+ return irhs1;
+ }
+ else
+ irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
+ goto and_ior_xor;
+ }
+ /* FALLTHRU */
+ case BIT_IOR_EXPR:
+ case BIT_XOR_EXPR:
+ irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
+ irhs2 = adjust_bool_pattern (rhs2, out_type, NULL_TREE, stmts);
+ and_ior_xor:
+ if (TYPE_PRECISION (TREE_TYPE (irhs1))
+ != TYPE_PRECISION (TREE_TYPE (irhs2)))
+ {
+ int prec1 = TYPE_PRECISION (TREE_TYPE (irhs1));
+ int prec2 = TYPE_PRECISION (TREE_TYPE (irhs2));
+ int out_prec = TYPE_PRECISION (out_type);
+ if (absu_hwi (out_prec - prec1) < absu_hwi (out_prec - prec2))
+ irhs2 = adjust_bool_pattern_cast (TREE_TYPE (irhs1), rhs2);
+ else if (absu_hwi (out_prec - prec1) > absu_hwi (out_prec - prec2))
+ irhs1 = adjust_bool_pattern_cast (TREE_TYPE (irhs2), rhs1);
+ else
+ {
+ irhs1 = adjust_bool_pattern_cast (out_type, rhs1);
+ irhs2 = adjust_bool_pattern_cast (out_type, rhs2);
+ }
+ }
+ itype = TREE_TYPE (irhs1);
+ pattern_stmt
+ = gimple_build_assign_with_ops (rhs_code,
+ vect_recog_temp_ssa_var (itype, NULL),
+ irhs1, irhs2);
+ break;
+
+ default:
+ gcc_assert (TREE_CODE_CLASS (rhs_code) == tcc_comparison);
+ if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE
+ || !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
+ = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode), 1);
+ }
+ else
+ itype = TREE_TYPE (rhs1);
+ cond_expr = build2_loc (loc, rhs_code, itype, rhs1, rhs2);
+ if (trueval == NULL_TREE)
+ trueval = build_int_cst (itype, 1);
+ else
+ 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));
+ break;
+ }
+
+ VEC_safe_push (gimple, heap, *stmts, stmt);
+ gimple_set_location (pattern_stmt, loc);
+ STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt)) = pattern_stmt;
+ return gimple_assign_lhs (pattern_stmt);
+}
+
+
+/* Function vect_recog_bool_pattern
+
+ Try to find pattern like following:
+
+ bool a_b, b_b, c_b, d_b, e_b;
+ TYPE f_T;
+ loop:
+ S1 a_b = x1 CMP1 y1;
+ S2 b_b = x2 CMP2 y2;
+ S3 c_b = a_b & b_b;
+ S4 d_b = x3 CMP3 y3;
+ S5 e_b = c_b | d_b;
+ S6 f_T = (TYPE) e_b;
+
+ where type 'TYPE' is an integral type.
+
+ Input:
+
+ * LAST_STMT: A stmt at the end from which the pattern
+ search begins, i.e. cast of a bool to
+ an integer 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 pattern.
+
+ Assuming size of TYPE is the same as size of all comparisons
+ (otherwise some casts would be added where needed), the above
+ sequence we create related pattern stmts:
+ S1' a_T = x1 CMP1 y1 ? 1 : 0;
+ S3' c_T = x2 CMP2 y2 ? a_T : 0;
+ S4' d_T = x3 CMP3 y3 ? 1 : 0;
+ S5' e_T = c_T | d_T;
+ S6' f_T = e_T;
+
+ Instead of the above S3' we could emit:
+ S2' b_T = x2 CMP2 y2 ? 1 : 0;
+ S3' c_T = a_T | b_T;
+ but the above is more efficient. */
+
+static gimple
+vect_recog_bool_pattern (VEC (gimple, heap) **stmts, tree *type_in,
+ tree *type_out)
+{
+ gimple last_stmt = VEC_pop (gimple, *stmts);
+ 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);
+ gimple pattern_stmt;
+
+ if (!is_gimple_assign (last_stmt))
+ return NULL;
+
+ var = gimple_assign_rhs1 (last_stmt);
+ lhs = gimple_assign_lhs (last_stmt);
+
+ if ((TYPE_PRECISION (TREE_TYPE (var)) != 1
+ || !TYPE_UNSIGNED (TREE_TYPE (var)))
+ && TREE_CODE (TREE_TYPE (var)) != BOOLEAN_TYPE)
+ return NULL;
+
+ rhs_code = gimple_assign_rhs_code (last_stmt);
+ if (CONVERT_EXPR_CODE_P (rhs_code))
+ {
+ if (TREE_CODE (TREE_TYPE (lhs)) != INTEGER_TYPE
+ || TYPE_PRECISION (TREE_TYPE (lhs)) == 1)
+ return NULL;
+ vectype = get_vectype_for_scalar_type (TREE_TYPE (lhs));
+ if (vectype == NULL_TREE)
+ return NULL;
+
+ if (!check_bool_pattern (var, loop_vinfo))
+ return NULL;
+
+ rhs = adjust_bool_pattern (var, TREE_TYPE (lhs), NULL_TREE, stmts);
+ lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
+ if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
+ pattern_stmt
+ = gimple_build_assign_with_ops (SSA_NAME, lhs, rhs, NULL_TREE);
+ else
+ pattern_stmt
+ = 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);
+ return pattern_stmt;
+ }
+ else if (rhs_code == SSA_NAME
+ && STMT_VINFO_DATA_REF (stmt_vinfo))
+ {
+ stmt_vec_info pattern_stmt_info;
+ vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
+ gcc_assert (vectype != NULL_TREE);
+ if (!VECTOR_MODE_P (TYPE_MODE (vectype)))
+ return NULL;
+ if (!check_bool_pattern (var, loop_vinfo))
+ return NULL;
+
+ rhs = adjust_bool_pattern (var, TREE_TYPE (vectype), NULL_TREE, stmts);
+ lhs = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (vectype), lhs);
+ if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
+ {
+ tree rhs2 = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
+ gimple cast_stmt
+ = gimple_build_assign_with_ops (NOP_EXPR, rhs2, rhs, NULL_TREE);
+ new_pattern_def_seq (stmt_vinfo, cast_stmt);
+ rhs = rhs2;
+ }
+ 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);
+ set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
+ STMT_VINFO_DATA_REF (pattern_stmt_info)
+ = STMT_VINFO_DATA_REF (stmt_vinfo);
+ STMT_VINFO_DR_BASE_ADDRESS (pattern_stmt_info)
+ = STMT_VINFO_DR_BASE_ADDRESS (stmt_vinfo);
+ STMT_VINFO_DR_INIT (pattern_stmt_info) = STMT_VINFO_DR_INIT (stmt_vinfo);
+ STMT_VINFO_DR_OFFSET (pattern_stmt_info)
+ = STMT_VINFO_DR_OFFSET (stmt_vinfo);
+ STMT_VINFO_DR_STEP (pattern_stmt_info) = STMT_VINFO_DR_STEP (stmt_vinfo);
+ STMT_VINFO_DR_ALIGNED_TO (pattern_stmt_info)
+ = STMT_VINFO_DR_ALIGNED_TO (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);
+ return pattern_stmt;
+ }
+ else
+ return NULL;
+}
+
/* Mark statements that are involved in a pattern. */
loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (orig_stmt_info);
gimple def_stmt;
- set_vinfo_for_stmt (pattern_stmt,
- new_stmt_vec_info (pattern_stmt, loop_vinfo, NULL));
- gimple_set_bb (pattern_stmt, gimple_bb (orig_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);
+ set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
+ }
+ gimple_set_bb (pattern_stmt, gimple_bb (orig_stmt));
STMT_VINFO_RELATED_STMT (pattern_stmt_info) = orig_stmt;
STMT_VINFO_DEF_TYPE (pattern_stmt_info)
- = STMT_VINFO_DEF_TYPE (orig_stmt_info);
+ = STMT_VINFO_DEF_TYPE (orig_stmt_info);
STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
STMT_VINFO_IN_PATTERN_P (orig_stmt_info) = true;
STMT_VINFO_RELATED_STMT (orig_stmt_info) = pattern_stmt;
- STMT_VINFO_PATTERN_DEF_STMT (pattern_stmt_info)
- = STMT_VINFO_PATTERN_DEF_STMT (orig_stmt_info);
- if (STMT_VINFO_PATTERN_DEF_STMT (pattern_stmt_info))
+ STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info)
+ = STMT_VINFO_PATTERN_DEF_SEQ (orig_stmt_info);
+ if (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info))
{
- def_stmt = STMT_VINFO_PATTERN_DEF_STMT (pattern_stmt_info);
- set_vinfo_for_stmt (def_stmt,
- new_stmt_vec_info (def_stmt, loop_vinfo, NULL));
- gimple_set_bb (def_stmt, gimple_bb (orig_stmt));
- def_stmt_info = vinfo_for_stmt (def_stmt);
- STMT_VINFO_RELATED_STMT (def_stmt_info) = orig_stmt;
- STMT_VINFO_DEF_TYPE (def_stmt_info)
- = STMT_VINFO_DEF_TYPE (orig_stmt_info);
- STMT_VINFO_VECTYPE (def_stmt_info) = pattern_vectype;
+ gimple_stmt_iterator si;
+ for (si = gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info));
+ !gsi_end_p (si); gsi_next (&si))
+ {
+ def_stmt = gsi_stmt (si);
+ 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);
+ set_vinfo_for_stmt (def_stmt, def_stmt_info);
+ }
+ gimple_set_bb (def_stmt, gimple_bb (orig_stmt));
+ STMT_VINFO_RELATED_STMT (def_stmt_info) = orig_stmt;
+ STMT_VINFO_DEF_TYPE (def_stmt_info)
+ = STMT_VINFO_DEF_TYPE (orig_stmt_info);
+ if (STMT_VINFO_VECTYPE (def_stmt_info) == NULL_TREE)
+ STMT_VINFO_VECTYPE (def_stmt_info) = pattern_vectype;
+ }
}
}
{
/* No need to check target support (already checked by the pattern
recognition function). */
- if (type_out)
- gcc_assert (VECTOR_MODE_P (TYPE_MODE (type_out)));
pattern_vectype = type_out ? type_out : type_in;
}
else