1 /* Analysis Utilities for Loop Vectorization.
2 Copyright (C) 2006-2016 Free Software Foundation, Inc.
3 Contributed by Dorit Nuzman <dorit@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
30 #include "optabs-tree.h"
31 #include "insn-config.h"
32 #include "recog.h" /* FIXME: for insn_data */
33 #include "fold-const.h"
34 #include "stor-layout.h"
37 #include "gimple-iterator.h"
39 #include "tree-vectorizer.h"
42 #include "internal-fn.h"
43 #include "case-cfn-macros.h"
45 /* Pattern recognition functions */
46 static gimple
*vect_recog_widen_sum_pattern (vec
<gimple
*> *, tree
*,
48 static gimple
*vect_recog_widen_mult_pattern (vec
<gimple
*> *, tree
*,
50 static gimple
*vect_recog_dot_prod_pattern (vec
<gimple
*> *, tree
*,
52 static gimple
*vect_recog_sad_pattern (vec
<gimple
*> *, tree
*,
54 static gimple
*vect_recog_pow_pattern (vec
<gimple
*> *, tree
*, tree
*);
55 static gimple
*vect_recog_over_widening_pattern (vec
<gimple
*> *, tree
*,
57 static gimple
*vect_recog_widen_shift_pattern (vec
<gimple
*> *,
59 static gimple
*vect_recog_rotate_pattern (vec
<gimple
*> *, tree
*, tree
*);
60 static gimple
*vect_recog_vector_vector_shift_pattern (vec
<gimple
*> *,
62 static gimple
*vect_recog_divmod_pattern (vec
<gimple
*> *,
65 static gimple
*vect_recog_mult_pattern (vec
<gimple
*> *,
68 static gimple
*vect_recog_mixed_size_cond_pattern (vec
<gimple
*> *,
70 static gimple
*vect_recog_bool_pattern (vec
<gimple
*> *, tree
*, tree
*);
71 static gimple
*vect_recog_mask_conversion_pattern (vec
<gimple
*> *, tree
*, tree
*);
73 struct vect_recog_func
75 vect_recog_func_ptr fn
;
79 /* Note that ordering matters - the first pattern matching on a stmt
80 is taken which means usually the more complex one needs to preceed
81 the less comples onex (widen_sum only after dot_prod or sad for example). */
82 static vect_recog_func vect_vect_recog_func_ptrs
[NUM_PATTERNS
] = {
83 { vect_recog_widen_mult_pattern
, "widen_mult" },
84 { vect_recog_dot_prod_pattern
, "dot_prod" },
85 { vect_recog_sad_pattern
, "sad" },
86 { vect_recog_widen_sum_pattern
, "widen_sum" },
87 { vect_recog_pow_pattern
, "pow" },
88 { vect_recog_widen_shift_pattern
, "widen_shift" },
89 { vect_recog_over_widening_pattern
, "over_widening" },
90 { vect_recog_rotate_pattern
, "rotate" },
91 { vect_recog_vector_vector_shift_pattern
, "vector_vector_shift" },
92 { vect_recog_divmod_pattern
, "divmod" },
93 { vect_recog_mult_pattern
, "mult" },
94 { vect_recog_mixed_size_cond_pattern
, "mixed_size_cond" },
95 { vect_recog_bool_pattern
, "bool" },
96 { vect_recog_mask_conversion_pattern
, "mask_conversion" }
100 append_pattern_def_seq (stmt_vec_info stmt_info
, gimple
*stmt
)
102 gimple_seq_add_stmt_without_update (&STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
),
107 new_pattern_def_seq (stmt_vec_info stmt_info
, gimple
*stmt
)
109 STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
) = NULL
;
110 append_pattern_def_seq (stmt_info
, stmt
);
113 /* Check whether STMT2 is in the same loop or basic block as STMT1.
114 Which of the two applies depends on whether we're currently doing
115 loop-based or basic-block-based vectorization, as determined by
116 the vinfo_for_stmt for STMT1 (which must be defined).
118 If this returns true, vinfo_for_stmt for STMT2 is guaranteed
119 to be defined as well. */
122 vect_same_loop_or_bb_p (gimple
*stmt1
, gimple
*stmt2
)
124 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt1
);
125 return vect_stmt_in_region_p (stmt_vinfo
->vinfo
, stmt2
);
128 /* If the LHS of DEF_STMT has a single use, and that statement is
129 in the same loop or basic block, return it. */
132 vect_single_imm_use (gimple
*def_stmt
)
134 tree lhs
= gimple_assign_lhs (def_stmt
);
138 if (!single_imm_use (lhs
, &use_p
, &use_stmt
))
141 if (!vect_same_loop_or_bb_p (def_stmt
, use_stmt
))
147 /* Check whether NAME, an ssa-name used in USE_STMT,
148 is a result of a type promotion, such that:
149 DEF_STMT: NAME = NOP (name0)
150 If CHECK_SIGN is TRUE, check that either both types are signed or both are
154 type_conversion_p (tree name
, gimple
*use_stmt
, bool check_sign
,
155 tree
*orig_type
, gimple
**def_stmt
, bool *promotion
)
157 gimple
*dummy_gimple
;
158 stmt_vec_info stmt_vinfo
;
159 tree type
= TREE_TYPE (name
);
161 enum vect_def_type dt
;
163 stmt_vinfo
= vinfo_for_stmt (use_stmt
);
164 if (!vect_is_simple_use (name
, stmt_vinfo
->vinfo
, def_stmt
, &dt
))
167 if (dt
!= vect_internal_def
168 && dt
!= vect_external_def
&& dt
!= vect_constant_def
)
174 if (dt
== vect_internal_def
)
176 stmt_vec_info def_vinfo
= vinfo_for_stmt (*def_stmt
);
177 if (STMT_VINFO_IN_PATTERN_P (def_vinfo
))
181 if (!is_gimple_assign (*def_stmt
))
184 if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (*def_stmt
)))
187 oprnd0
= gimple_assign_rhs1 (*def_stmt
);
189 *orig_type
= TREE_TYPE (oprnd0
);
190 if (!INTEGRAL_TYPE_P (type
) || !INTEGRAL_TYPE_P (*orig_type
)
191 || ((TYPE_UNSIGNED (type
) != TYPE_UNSIGNED (*orig_type
)) && check_sign
))
194 if (TYPE_PRECISION (type
) >= (TYPE_PRECISION (*orig_type
) * 2))
199 if (!vect_is_simple_use (oprnd0
, stmt_vinfo
->vinfo
, &dummy_gimple
, &dt
))
205 /* Helper to return a new temporary for pattern of TYPE for STMT. If STMT
206 is NULL, the caller must set SSA_NAME_DEF_STMT for the returned SSA var. */
209 vect_recog_temp_ssa_var (tree type
, gimple
*stmt
)
211 return make_temp_ssa_name (type
, stmt
, "patt");
214 /* Function vect_recog_dot_prod_pattern
216 Try to find the following pattern:
222 sum_0 = phi <init, sum_1>
225 S3 x_T = (TYPE1) x_t;
226 S4 y_T = (TYPE1) y_t;
228 [S6 prod = (TYPE2) prod; #optional]
229 S7 sum_1 = prod + sum_0;
231 where 'TYPE1' is exactly double the size of type 'type', and 'TYPE2' is the
232 same size of 'TYPE1' or bigger. This is a special case of a reduction
237 * STMTS: Contains a stmt from which the pattern search begins. In the
238 example, when this function is called with S7, the pattern {S3,S4,S5,S6,S7}
243 * TYPE_IN: The type of the input arguments to the pattern.
245 * TYPE_OUT: The type of the output of this pattern.
247 * Return value: A new stmt that will be used to replace the sequence of
248 stmts that constitute the pattern. In this case it will be:
249 WIDEN_DOT_PRODUCT <x_t, y_t, sum_0>
251 Note: The dot-prod idiom is a widening reduction pattern that is
252 vectorized without preserving all the intermediate results. It
253 produces only N/2 (widened) results (by summing up pairs of
254 intermediate results) rather than all N results. Therefore, we
255 cannot allow this pattern when we want to get all the results and in
256 the correct order (as is the case when this computation is in an
257 inner-loop nested in an outer-loop that us being vectorized). */
260 vect_recog_dot_prod_pattern (vec
<gimple
*> *stmts
, tree
*type_in
,
263 gimple
*stmt
, *last_stmt
= (*stmts
)[0];
265 tree oprnd00
, oprnd01
;
266 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
267 tree type
, half_type
;
268 gimple
*pattern_stmt
;
270 loop_vec_info loop_info
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
278 loop
= LOOP_VINFO_LOOP (loop_info
);
280 /* We don't allow changing the order of the computation in the inner-loop
281 when doing outer-loop vectorization. */
282 if (loop
&& nested_in_vect_loop_p (loop
, last_stmt
))
285 if (!is_gimple_assign (last_stmt
))
288 type
= gimple_expr_type (last_stmt
);
290 /* Look for the following pattern
294 DDPROD = (TYPE2) DPROD;
295 sum_1 = DDPROD + sum_0;
297 - DX is double the size of X
298 - DY is double the size of Y
299 - DX, DY, DPROD all have the same type
300 - sum is the same size of DPROD or bigger
301 - sum has been recognized as a reduction variable.
303 This is equivalent to:
304 DPROD = X w* Y; #widen mult
305 sum_1 = DPROD w+ sum_0; #widen summation
307 DPROD = X w* Y; #widen mult
308 sum_1 = DPROD + sum_0; #summation
311 /* Starting from LAST_STMT, follow the defs of its uses in search
312 of the above pattern. */
314 if (gimple_assign_rhs_code (last_stmt
) != PLUS_EXPR
)
317 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
))
319 /* Has been detected as widening-summation? */
321 stmt
= STMT_VINFO_RELATED_STMT (stmt_vinfo
);
322 type
= gimple_expr_type (stmt
);
323 if (gimple_assign_rhs_code (stmt
) != WIDEN_SUM_EXPR
)
325 oprnd0
= gimple_assign_rhs1 (stmt
);
326 oprnd1
= gimple_assign_rhs2 (stmt
);
327 half_type
= TREE_TYPE (oprnd0
);
333 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) != vect_reduction_def
334 && ! STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_vinfo
))
336 oprnd0
= gimple_assign_rhs1 (last_stmt
);
337 oprnd1
= gimple_assign_rhs2 (last_stmt
);
338 if (!types_compatible_p (TREE_TYPE (oprnd0
), type
)
339 || !types_compatible_p (TREE_TYPE (oprnd1
), type
))
343 if (type_conversion_p (oprnd0
, stmt
, true, &half_type
, &def_stmt
,
348 oprnd0
= gimple_assign_rhs1 (stmt
);
354 /* So far so good. Since last_stmt was detected as a (summation) reduction,
355 we know that oprnd1 is the reduction variable (defined by a loop-header
356 phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
357 Left to check that oprnd0 is defined by a (widen_)mult_expr */
358 if (TREE_CODE (oprnd0
) != SSA_NAME
)
361 prod_type
= half_type
;
362 stmt
= SSA_NAME_DEF_STMT (oprnd0
);
364 /* It could not be the dot_prod pattern if the stmt is outside the loop. */
365 if (!gimple_bb (stmt
) || !flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
368 /* FORNOW. Can continue analyzing the def-use chain when this stmt in a phi
369 inside the loop (in case we are analyzing an outer-loop). */
370 if (!is_gimple_assign (stmt
))
372 stmt_vinfo
= vinfo_for_stmt (stmt
);
373 gcc_assert (stmt_vinfo
);
374 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) != vect_internal_def
)
376 if (gimple_assign_rhs_code (stmt
) != MULT_EXPR
)
378 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
))
380 /* Has been detected as a widening multiplication? */
382 stmt
= STMT_VINFO_RELATED_STMT (stmt_vinfo
);
383 if (gimple_assign_rhs_code (stmt
) != WIDEN_MULT_EXPR
)
385 stmt_vinfo
= vinfo_for_stmt (stmt
);
386 gcc_assert (stmt_vinfo
);
387 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_internal_def
);
388 oprnd00
= gimple_assign_rhs1 (stmt
);
389 oprnd01
= gimple_assign_rhs2 (stmt
);
390 STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (last_stmt
))
391 = STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo
);
395 tree half_type0
, half_type1
;
399 oprnd0
= gimple_assign_rhs1 (stmt
);
400 oprnd1
= gimple_assign_rhs2 (stmt
);
401 if (!types_compatible_p (TREE_TYPE (oprnd0
), prod_type
)
402 || !types_compatible_p (TREE_TYPE (oprnd1
), prod_type
))
404 if (!type_conversion_p (oprnd0
, stmt
, true, &half_type0
, &def_stmt
,
408 oprnd00
= gimple_assign_rhs1 (def_stmt
);
409 if (!type_conversion_p (oprnd1
, stmt
, true, &half_type1
, &def_stmt
,
413 oprnd01
= gimple_assign_rhs1 (def_stmt
);
414 if (!types_compatible_p (half_type0
, half_type1
))
416 if (TYPE_PRECISION (prod_type
) != TYPE_PRECISION (half_type0
) * 2)
420 half_type
= TREE_TYPE (oprnd00
);
421 *type_in
= half_type
;
424 /* Pattern detected. Create a stmt to be used to replace the pattern: */
425 var
= vect_recog_temp_ssa_var (type
, NULL
);
426 pattern_stmt
= gimple_build_assign (var
, DOT_PROD_EXPR
,
427 oprnd00
, oprnd01
, oprnd1
);
429 if (dump_enabled_p ())
431 dump_printf_loc (MSG_NOTE
, vect_location
,
432 "vect_recog_dot_prod_pattern: detected: ");
433 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
440 /* Function vect_recog_sad_pattern
442 Try to find the following Sum of Absolute Difference (SAD) pattern:
445 signed TYPE1 diff, abs_diff;
448 sum_0 = phi <init, sum_1>
451 S3 x_T = (TYPE1) x_t;
452 S4 y_T = (TYPE1) y_t;
454 S6 abs_diff = ABS_EXPR <diff>;
455 [S7 abs_diff = (TYPE2) abs_diff; #optional]
456 S8 sum_1 = abs_diff + sum_0;
458 where 'TYPE1' is at least double the size of type 'type', and 'TYPE2' is the
459 same size of 'TYPE1' or bigger. This is a special case of a reduction
464 * STMTS: Contains a stmt from which the pattern search begins. In the
465 example, when this function is called with S8, the pattern
466 {S3,S4,S5,S6,S7,S8} will be detected.
470 * TYPE_IN: The type of the input arguments to the pattern.
472 * TYPE_OUT: The type of the output of this pattern.
474 * Return value: A new stmt that will be used to replace the sequence of
475 stmts that constitute the pattern. In this case it will be:
476 SAD_EXPR <x_t, y_t, sum_0>
480 vect_recog_sad_pattern (vec
<gimple
*> *stmts
, tree
*type_in
,
483 gimple
*last_stmt
= (*stmts
)[0];
484 tree sad_oprnd0
, sad_oprnd1
;
485 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
487 loop_vec_info loop_info
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
494 loop
= LOOP_VINFO_LOOP (loop_info
);
496 /* We don't allow changing the order of the computation in the inner-loop
497 when doing outer-loop vectorization. */
498 if (loop
&& nested_in_vect_loop_p (loop
, last_stmt
))
501 if (!is_gimple_assign (last_stmt
))
504 tree sum_type
= gimple_expr_type (last_stmt
);
506 /* Look for the following pattern
510 DAD = ABS_EXPR <DDIFF>;
511 DDPROD = (TYPE2) DPROD;
514 - DX is at least double the size of X
515 - DY is at least double the size of Y
516 - DX, DY, DDIFF, DAD all have the same type
517 - sum is the same size of DAD or bigger
518 - sum has been recognized as a reduction variable.
520 This is equivalent to:
521 DDIFF = X w- Y; #widen sub
522 DAD = ABS_EXPR <DDIFF>;
523 sum_1 = DAD w+ sum_0; #widen summation
525 DDIFF = X w- Y; #widen sub
526 DAD = ABS_EXPR <DDIFF>;
527 sum_1 = DAD + sum_0; #summation
530 /* Starting from LAST_STMT, follow the defs of its uses in search
531 of the above pattern. */
533 if (gimple_assign_rhs_code (last_stmt
) != PLUS_EXPR
)
536 tree plus_oprnd0
, plus_oprnd1
;
538 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
))
540 /* Has been detected as widening-summation? */
542 gimple
*stmt
= STMT_VINFO_RELATED_STMT (stmt_vinfo
);
543 sum_type
= gimple_expr_type (stmt
);
544 if (gimple_assign_rhs_code (stmt
) != WIDEN_SUM_EXPR
)
546 plus_oprnd0
= gimple_assign_rhs1 (stmt
);
547 plus_oprnd1
= gimple_assign_rhs2 (stmt
);
548 half_type
= TREE_TYPE (plus_oprnd0
);
554 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) != vect_reduction_def
555 && ! STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_vinfo
))
557 plus_oprnd0
= gimple_assign_rhs1 (last_stmt
);
558 plus_oprnd1
= gimple_assign_rhs2 (last_stmt
);
559 if (!types_compatible_p (TREE_TYPE (plus_oprnd0
), sum_type
)
560 || !types_compatible_p (TREE_TYPE (plus_oprnd1
), sum_type
))
563 /* The type conversion could be promotion, demotion,
564 or just signed -> unsigned. */
565 if (type_conversion_p (plus_oprnd0
, last_stmt
, false,
566 &half_type
, &def_stmt
, &promotion
))
567 plus_oprnd0
= gimple_assign_rhs1 (def_stmt
);
569 half_type
= sum_type
;
572 /* So far so good. Since last_stmt was detected as a (summation) reduction,
573 we know that plus_oprnd1 is the reduction variable (defined by a loop-header
574 phi), and plus_oprnd0 is an ssa-name defined by a stmt in the loop body.
575 Then check that plus_oprnd0 is defined by an abs_expr. */
577 if (TREE_CODE (plus_oprnd0
) != SSA_NAME
)
580 tree abs_type
= half_type
;
581 gimple
*abs_stmt
= SSA_NAME_DEF_STMT (plus_oprnd0
);
583 /* It could not be the sad pattern if the abs_stmt is outside the loop. */
584 if (!gimple_bb (abs_stmt
) || !flow_bb_inside_loop_p (loop
, gimple_bb (abs_stmt
)))
587 /* FORNOW. Can continue analyzing the def-use chain when this stmt in a phi
588 inside the loop (in case we are analyzing an outer-loop). */
589 if (!is_gimple_assign (abs_stmt
))
592 stmt_vec_info abs_stmt_vinfo
= vinfo_for_stmt (abs_stmt
);
593 gcc_assert (abs_stmt_vinfo
);
594 if (STMT_VINFO_DEF_TYPE (abs_stmt_vinfo
) != vect_internal_def
)
596 if (gimple_assign_rhs_code (abs_stmt
) != ABS_EXPR
)
599 tree abs_oprnd
= gimple_assign_rhs1 (abs_stmt
);
600 if (!types_compatible_p (TREE_TYPE (abs_oprnd
), abs_type
))
602 if (TYPE_UNSIGNED (abs_type
))
605 /* We then detect if the operand of abs_expr is defined by a minus_expr. */
607 if (TREE_CODE (abs_oprnd
) != SSA_NAME
)
610 gimple
*diff_stmt
= SSA_NAME_DEF_STMT (abs_oprnd
);
612 /* It could not be the sad pattern if the diff_stmt is outside the loop. */
613 if (!gimple_bb (diff_stmt
)
614 || !flow_bb_inside_loop_p (loop
, gimple_bb (diff_stmt
)))
617 /* FORNOW. Can continue analyzing the def-use chain when this stmt in a phi
618 inside the loop (in case we are analyzing an outer-loop). */
619 if (!is_gimple_assign (diff_stmt
))
622 stmt_vec_info diff_stmt_vinfo
= vinfo_for_stmt (diff_stmt
);
623 gcc_assert (diff_stmt_vinfo
);
624 if (STMT_VINFO_DEF_TYPE (diff_stmt_vinfo
) != vect_internal_def
)
626 if (gimple_assign_rhs_code (diff_stmt
) != MINUS_EXPR
)
629 tree half_type0
, half_type1
;
632 tree minus_oprnd0
= gimple_assign_rhs1 (diff_stmt
);
633 tree minus_oprnd1
= gimple_assign_rhs2 (diff_stmt
);
635 if (!types_compatible_p (TREE_TYPE (minus_oprnd0
), abs_type
)
636 || !types_compatible_p (TREE_TYPE (minus_oprnd1
), abs_type
))
638 if (!type_conversion_p (minus_oprnd0
, diff_stmt
, false,
639 &half_type0
, &def_stmt
, &promotion
)
642 sad_oprnd0
= gimple_assign_rhs1 (def_stmt
);
644 if (!type_conversion_p (minus_oprnd1
, diff_stmt
, false,
645 &half_type1
, &def_stmt
, &promotion
)
648 sad_oprnd1
= gimple_assign_rhs1 (def_stmt
);
650 if (!types_compatible_p (half_type0
, half_type1
))
652 if (TYPE_PRECISION (abs_type
) < TYPE_PRECISION (half_type0
) * 2
653 || TYPE_PRECISION (sum_type
) < TYPE_PRECISION (half_type0
) * 2)
656 *type_in
= TREE_TYPE (sad_oprnd0
);
657 *type_out
= sum_type
;
659 /* Pattern detected. Create a stmt to be used to replace the pattern: */
660 tree var
= vect_recog_temp_ssa_var (sum_type
, NULL
);
661 gimple
*pattern_stmt
= gimple_build_assign (var
, SAD_EXPR
, sad_oprnd0
,
662 sad_oprnd1
, plus_oprnd1
);
664 if (dump_enabled_p ())
666 dump_printf_loc (MSG_NOTE
, vect_location
,
667 "vect_recog_sad_pattern: detected: ");
668 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
675 /* Handle widening operation by a constant. At the moment we support MULT_EXPR
678 For MULT_EXPR we check that CONST_OPRND fits HALF_TYPE, and for LSHIFT_EXPR
679 we check that CONST_OPRND is less or equal to the size of HALF_TYPE.
681 Otherwise, if the type of the result (TYPE) is at least 4 times bigger than
682 HALF_TYPE, and there is an intermediate type (2 times smaller than TYPE)
683 that satisfies the above restrictions, we can perform a widening opeartion
684 from the intermediate type to TYPE and replace a_T = (TYPE) a_t;
685 with a_it = (interm_type) a_t; Store such operation in *WSTMT. */
688 vect_handle_widen_op_by_const (gimple
*stmt
, enum tree_code code
,
689 tree const_oprnd
, tree
*oprnd
,
690 gimple
**wstmt
, tree type
,
691 tree
*half_type
, gimple
*def_stmt
)
693 tree new_type
, new_oprnd
;
695 if (code
!= MULT_EXPR
&& code
!= LSHIFT_EXPR
)
698 if (((code
== MULT_EXPR
&& int_fits_type_p (const_oprnd
, *half_type
))
699 || (code
== LSHIFT_EXPR
700 && compare_tree_int (const_oprnd
, TYPE_PRECISION (*half_type
))
702 && TYPE_PRECISION (type
) == (TYPE_PRECISION (*half_type
) * 2))
704 /* CONST_OPRND is a constant of HALF_TYPE. */
705 *oprnd
= gimple_assign_rhs1 (def_stmt
);
709 if (TYPE_PRECISION (type
) < (TYPE_PRECISION (*half_type
) * 4))
712 if (!vect_same_loop_or_bb_p (stmt
, def_stmt
))
715 /* TYPE is 4 times bigger than HALF_TYPE, try widening operation for
716 a type 2 times bigger than HALF_TYPE. */
717 new_type
= build_nonstandard_integer_type (TYPE_PRECISION (type
) / 2,
718 TYPE_UNSIGNED (type
));
719 if ((code
== MULT_EXPR
&& !int_fits_type_p (const_oprnd
, new_type
))
720 || (code
== LSHIFT_EXPR
721 && compare_tree_int (const_oprnd
, TYPE_PRECISION (new_type
)) == 1))
724 /* Use NEW_TYPE for widening operation and create a_T = (NEW_TYPE) a_t; */
725 *oprnd
= gimple_assign_rhs1 (def_stmt
);
726 new_oprnd
= make_ssa_name (new_type
);
727 *wstmt
= gimple_build_assign (new_oprnd
, NOP_EXPR
, *oprnd
);
730 *half_type
= new_type
;
735 /* Function vect_recog_widen_mult_pattern
737 Try to find the following pattern:
741 TYPE a_T, b_T, prod_T;
747 S5 prod_T = a_T * b_T;
749 where type 'TYPE' is at least double the size of type 'type1' and 'type2'.
751 Also detect unsigned cases:
755 unsigned TYPE u_prod_T;
756 TYPE a_T, b_T, prod_T;
762 S5 prod_T = a_T * b_T;
763 S6 u_prod_T = (unsigned TYPE) prod_T;
765 and multiplication by constants:
772 S5 prod_T = a_T * CONST;
774 A special case of multiplication by constants is when 'TYPE' is 4 times
775 bigger than 'type', but CONST fits an intermediate type 2 times smaller
776 than 'TYPE'. In that case we create an additional pattern stmt for S3
777 to create a variable of the intermediate type, and perform widen-mult
778 on the intermediate type as well:
782 TYPE a_T, prod_T, prod_T';
786 '--> a_it = (interm_type) a_t;
787 S5 prod_T = a_T * CONST;
788 '--> prod_T' = a_it w* CONST;
792 * STMTS: Contains a stmt from which the pattern search begins. In the
793 example, when this function is called with S5, the pattern {S3,S4,S5,(S6)}
794 is detected. In case of unsigned widen-mult, the original stmt (S5) is
795 replaced with S6 in STMTS. In case of multiplication by a constant
796 of an intermediate type (the last case above), STMTS also contains S3
797 (inserted before S5).
801 * TYPE_IN: The type of the input arguments to the pattern.
803 * TYPE_OUT: The type of the output of this pattern.
805 * Return value: A new stmt that will be used to replace the sequence of
806 stmts that constitute the pattern. In this case it will be:
807 WIDEN_MULT <a_t, b_t>
808 If the result of WIDEN_MULT needs to be converted to a larger type, the
809 returned stmt will be this type conversion stmt.
813 vect_recog_widen_mult_pattern (vec
<gimple
*> *stmts
,
814 tree
*type_in
, tree
*type_out
)
816 gimple
*last_stmt
= stmts
->pop ();
817 gimple
*def_stmt0
, *def_stmt1
;
819 tree type
, half_type0
, half_type1
;
820 gimple
*new_stmt
= NULL
, *pattern_stmt
= NULL
;
821 tree vectype
, vecitype
;
823 enum tree_code dummy_code
;
829 if (!is_gimple_assign (last_stmt
))
832 type
= gimple_expr_type (last_stmt
);
834 /* Starting from LAST_STMT, follow the defs of its uses in search
835 of the above pattern. */
837 if (gimple_assign_rhs_code (last_stmt
) != MULT_EXPR
)
840 oprnd0
= gimple_assign_rhs1 (last_stmt
);
841 oprnd1
= gimple_assign_rhs2 (last_stmt
);
842 if (!types_compatible_p (TREE_TYPE (oprnd0
), type
)
843 || !types_compatible_p (TREE_TYPE (oprnd1
), type
))
846 /* Check argument 0. */
847 if (!type_conversion_p (oprnd0
, last_stmt
, false, &half_type0
, &def_stmt0
,
851 /* Check argument 1. */
852 op1_ok
= type_conversion_p (oprnd1
, last_stmt
, false, &half_type1
,
853 &def_stmt1
, &promotion
);
855 if (op1_ok
&& promotion
)
857 oprnd0
= gimple_assign_rhs1 (def_stmt0
);
858 oprnd1
= gimple_assign_rhs1 (def_stmt1
);
862 if (TREE_CODE (oprnd1
) == INTEGER_CST
863 && TREE_CODE (half_type0
) == INTEGER_TYPE
864 && vect_handle_widen_op_by_const (last_stmt
, MULT_EXPR
, oprnd1
,
865 &oprnd0
, &new_stmt
, type
,
866 &half_type0
, def_stmt0
))
868 half_type1
= half_type0
;
869 oprnd1
= fold_convert (half_type1
, oprnd1
);
875 /* If the two arguments have different sizes, convert the one with
876 the smaller type into the larger type. */
877 if (TYPE_PRECISION (half_type0
) != TYPE_PRECISION (half_type1
))
879 /* If we already used up the single-stmt slot give up. */
884 gimple
*def_stmt
= NULL
;
886 if (TYPE_PRECISION (half_type0
) < TYPE_PRECISION (half_type1
))
888 def_stmt
= def_stmt0
;
889 half_type0
= half_type1
;
894 def_stmt
= def_stmt1
;
895 half_type1
= half_type0
;
899 tree old_oprnd
= gimple_assign_rhs1 (def_stmt
);
900 tree new_oprnd
= make_ssa_name (half_type0
);
901 new_stmt
= gimple_build_assign (new_oprnd
, NOP_EXPR
, old_oprnd
);
905 /* Handle unsigned case. Look for
906 S6 u_prod_T = (unsigned TYPE) prod_T;
907 Use unsigned TYPE as the type for WIDEN_MULT_EXPR. */
908 if (TYPE_UNSIGNED (type
) != TYPE_UNSIGNED (half_type0
))
914 if (TYPE_UNSIGNED (type
) == TYPE_UNSIGNED (half_type1
))
917 use_stmt
= vect_single_imm_use (last_stmt
);
918 if (!use_stmt
|| !is_gimple_assign (use_stmt
)
919 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt
)))
922 use_lhs
= gimple_assign_lhs (use_stmt
);
923 use_type
= TREE_TYPE (use_lhs
);
924 if (!INTEGRAL_TYPE_P (use_type
)
925 || (TYPE_UNSIGNED (type
) == TYPE_UNSIGNED (use_type
))
926 || (TYPE_PRECISION (type
) != TYPE_PRECISION (use_type
)))
930 last_stmt
= use_stmt
;
933 if (!types_compatible_p (half_type0
, half_type1
))
936 /* If TYPE is more than twice larger than HALF_TYPE, we use WIDEN_MULT
937 to get an intermediate result of type ITYPE. In this case we need
938 to build a statement to convert this intermediate result to type TYPE. */
940 if (TYPE_PRECISION (type
) > TYPE_PRECISION (half_type0
) * 2)
941 itype
= build_nonstandard_integer_type
942 (GET_MODE_BITSIZE (TYPE_MODE (half_type0
)) * 2,
943 TYPE_UNSIGNED (type
));
945 /* Pattern detected. */
946 if (dump_enabled_p ())
947 dump_printf_loc (MSG_NOTE
, vect_location
,
948 "vect_recog_widen_mult_pattern: detected:\n");
950 /* Check target support */
951 vectype
= get_vectype_for_scalar_type (half_type0
);
952 vecitype
= get_vectype_for_scalar_type (itype
);
955 || !supportable_widening_operation (WIDEN_MULT_EXPR
, last_stmt
,
957 &dummy_code
, &dummy_code
,
958 &dummy_int
, &dummy_vec
))
962 *type_out
= get_vectype_for_scalar_type (type
);
964 /* Pattern supported. Create a stmt to be used to replace the pattern: */
965 var
= vect_recog_temp_ssa_var (itype
, NULL
);
966 pattern_stmt
= gimple_build_assign (var
, WIDEN_MULT_EXPR
, oprnd0
, oprnd1
);
968 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
969 STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo
) = NULL
;
971 /* If the original two operands have different sizes, we may need to convert
972 the smaller one into the larget type. If this is the case, at this point
973 the new stmt is already built. */
976 append_pattern_def_seq (stmt_vinfo
, new_stmt
);
977 stmt_vec_info new_stmt_info
978 = new_stmt_vec_info (new_stmt
, stmt_vinfo
->vinfo
);
979 set_vinfo_for_stmt (new_stmt
, new_stmt_info
);
980 STMT_VINFO_VECTYPE (new_stmt_info
) = vectype
;
983 /* If ITYPE is not TYPE, we need to build a type convertion stmt to convert
984 the result of the widen-mult operation into type TYPE. */
987 append_pattern_def_seq (stmt_vinfo
, pattern_stmt
);
988 stmt_vec_info pattern_stmt_info
989 = new_stmt_vec_info (pattern_stmt
, stmt_vinfo
->vinfo
);
990 set_vinfo_for_stmt (pattern_stmt
, pattern_stmt_info
);
991 STMT_VINFO_VECTYPE (pattern_stmt_info
) = vecitype
;
992 pattern_stmt
= gimple_build_assign (vect_recog_temp_ssa_var (type
, NULL
),
994 gimple_assign_lhs (pattern_stmt
));
997 if (dump_enabled_p ())
998 dump_gimple_stmt_loc (MSG_NOTE
, vect_location
, TDF_SLIM
, pattern_stmt
, 0);
1000 stmts
->safe_push (last_stmt
);
1001 return pattern_stmt
;
1005 /* Function vect_recog_pow_pattern
1007 Try to find the following pattern:
1011 with POW being one of pow, powf, powi, powif and N being
1016 * LAST_STMT: A stmt from which the pattern search begins.
1020 * TYPE_IN: The type of the input arguments to the pattern.
1022 * TYPE_OUT: The type of the output of this pattern.
1024 * Return value: A new stmt that will be used to replace the sequence of
1025 stmts that constitute the pattern. In this case it will be:
1032 vect_recog_pow_pattern (vec
<gimple
*> *stmts
, tree
*type_in
,
1035 gimple
*last_stmt
= (*stmts
)[0];
1036 tree base
, exp
= NULL
;
1040 if (!is_gimple_call (last_stmt
) || gimple_call_lhs (last_stmt
) == NULL
)
1043 switch (gimple_call_combined_fn (last_stmt
))
1047 base
= gimple_call_arg (last_stmt
, 0);
1048 exp
= gimple_call_arg (last_stmt
, 1);
1049 if (TREE_CODE (exp
) != REAL_CST
1050 && TREE_CODE (exp
) != INTEGER_CST
)
1058 /* We now have a pow or powi builtin function call with a constant
1061 *type_out
= NULL_TREE
;
1063 /* Catch squaring. */
1064 if ((tree_fits_shwi_p (exp
)
1065 && tree_to_shwi (exp
) == 2)
1066 || (TREE_CODE (exp
) == REAL_CST
1067 && real_equal (&TREE_REAL_CST (exp
), &dconst2
)))
1069 *type_in
= TREE_TYPE (base
);
1071 var
= vect_recog_temp_ssa_var (TREE_TYPE (base
), NULL
);
1072 stmt
= gimple_build_assign (var
, MULT_EXPR
, base
, base
);
1076 /* Catch square root. */
1077 if (TREE_CODE (exp
) == REAL_CST
1078 && real_equal (&TREE_REAL_CST (exp
), &dconsthalf
))
1080 *type_in
= get_vectype_for_scalar_type (TREE_TYPE (base
));
1082 && direct_internal_fn_supported_p (IFN_SQRT
, *type_in
,
1083 OPTIMIZE_FOR_SPEED
))
1085 gcall
*stmt
= gimple_build_call_internal (IFN_SQRT
, 1, base
);
1086 var
= vect_recog_temp_ssa_var (TREE_TYPE (base
), stmt
);
1087 gimple_call_set_lhs (stmt
, var
);
1096 /* Function vect_recog_widen_sum_pattern
1098 Try to find the following pattern:
1101 TYPE x_T, sum = init;
1103 sum_0 = phi <init, sum_1>
1105 S2 x_T = (TYPE) x_t;
1106 S3 sum_1 = x_T + sum_0;
1108 where type 'TYPE' is at least double the size of type 'type', i.e - we're
1109 summing elements of type 'type' into an accumulator of type 'TYPE'. This is
1110 a special case of a reduction computation.
1114 * LAST_STMT: A stmt from which the pattern search begins. In the example,
1115 when this function is called with S3, the pattern {S2,S3} will be detected.
1119 * TYPE_IN: The type of the input arguments to the pattern.
1121 * TYPE_OUT: The type of the output of this pattern.
1123 * Return value: A new stmt that will be used to replace the sequence of
1124 stmts that constitute the pattern. In this case it will be:
1125 WIDEN_SUM <x_t, sum_0>
1127 Note: The widening-sum idiom is a widening reduction pattern that is
1128 vectorized without preserving all the intermediate results. It
1129 produces only N/2 (widened) results (by summing up pairs of
1130 intermediate results) rather than all N results. Therefore, we
1131 cannot allow this pattern when we want to get all the results and in
1132 the correct order (as is the case when this computation is in an
1133 inner-loop nested in an outer-loop that us being vectorized). */
1136 vect_recog_widen_sum_pattern (vec
<gimple
*> *stmts
, tree
*type_in
,
1139 gimple
*stmt
, *last_stmt
= (*stmts
)[0];
1140 tree oprnd0
, oprnd1
;
1141 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
1142 tree type
, half_type
;
1143 gimple
*pattern_stmt
;
1144 loop_vec_info loop_info
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
1152 loop
= LOOP_VINFO_LOOP (loop_info
);
1154 /* We don't allow changing the order of the computation in the inner-loop
1155 when doing outer-loop vectorization. */
1156 if (loop
&& nested_in_vect_loop_p (loop
, last_stmt
))
1159 if (!is_gimple_assign (last_stmt
))
1162 type
= gimple_expr_type (last_stmt
);
1164 /* Look for the following pattern
1167 In which DX is at least double the size of X, and sum_1 has been
1168 recognized as a reduction variable.
1171 /* Starting from LAST_STMT, follow the defs of its uses in search
1172 of the above pattern. */
1174 if (gimple_assign_rhs_code (last_stmt
) != PLUS_EXPR
)
1177 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) != vect_reduction_def
1178 && ! STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_vinfo
))
1181 oprnd0
= gimple_assign_rhs1 (last_stmt
);
1182 oprnd1
= gimple_assign_rhs2 (last_stmt
);
1183 if (!types_compatible_p (TREE_TYPE (oprnd0
), type
)
1184 || !types_compatible_p (TREE_TYPE (oprnd1
), type
))
1187 /* So far so good. Since last_stmt was detected as a (summation) reduction,
1188 we know that oprnd1 is the reduction variable (defined by a loop-header
1189 phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
1190 Left to check that oprnd0 is defined by a cast from type 'type' to type
1193 if (!type_conversion_p (oprnd0
, last_stmt
, true, &half_type
, &stmt
,
1198 oprnd0
= gimple_assign_rhs1 (stmt
);
1199 *type_in
= half_type
;
1202 /* Pattern detected. Create a stmt to be used to replace the pattern: */
1203 var
= vect_recog_temp_ssa_var (type
, NULL
);
1204 pattern_stmt
= gimple_build_assign (var
, WIDEN_SUM_EXPR
, oprnd0
, oprnd1
);
1206 if (dump_enabled_p ())
1208 dump_printf_loc (MSG_NOTE
, vect_location
,
1209 "vect_recog_widen_sum_pattern: detected: ");
1210 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
1213 return pattern_stmt
;
1217 /* Return TRUE if the operation in STMT can be performed on a smaller type.
1220 STMT - a statement to check.
1221 DEF - we support operations with two operands, one of which is constant.
1222 The other operand can be defined by a demotion operation, or by a
1223 previous statement in a sequence of over-promoted operations. In the
1224 later case DEF is used to replace that operand. (It is defined by a
1225 pattern statement we created for the previous statement in the
1229 NEW_TYPE - Output: a smaller type that we are trying to use. Input: if not
1230 NULL, it's the type of DEF.
1231 STMTS - additional pattern statements. If a pattern statement (type
1232 conversion) is created in this function, its original statement is
1236 OP0, OP1 - if the operation fits a smaller type, OP0 and OP1 are the new
1237 operands to use in the new pattern statement for STMT (will be created
1238 in vect_recog_over_widening_pattern ()).
1239 NEW_DEF_STMT - in case DEF has to be promoted, we create two pattern
1240 statements for STMT: the first one is a type promotion and the second
1241 one is the operation itself. We return the type promotion statement
1242 in NEW_DEF_STMT and further store it in STMT_VINFO_PATTERN_DEF_SEQ of
1243 the second pattern statement. */
1246 vect_operation_fits_smaller_type (gimple
*stmt
, tree def
, tree
*new_type
,
1247 tree
*op0
, tree
*op1
, gimple
**new_def_stmt
,
1248 vec
<gimple
*> *stmts
)
1250 enum tree_code code
;
1251 tree const_oprnd
, oprnd
;
1252 tree interm_type
= NULL_TREE
, half_type
, new_oprnd
, type
;
1253 gimple
*def_stmt
, *new_stmt
;
1259 *new_def_stmt
= NULL
;
1261 if (!is_gimple_assign (stmt
))
1264 code
= gimple_assign_rhs_code (stmt
);
1265 if (code
!= LSHIFT_EXPR
&& code
!= RSHIFT_EXPR
1266 && code
!= BIT_IOR_EXPR
&& code
!= BIT_XOR_EXPR
&& code
!= BIT_AND_EXPR
)
1269 oprnd
= gimple_assign_rhs1 (stmt
);
1270 const_oprnd
= gimple_assign_rhs2 (stmt
);
1271 type
= gimple_expr_type (stmt
);
1273 if (TREE_CODE (oprnd
) != SSA_NAME
1274 || TREE_CODE (const_oprnd
) != INTEGER_CST
)
1277 /* If oprnd has other uses besides that in stmt we cannot mark it
1278 as being part of a pattern only. */
1279 if (!has_single_use (oprnd
))
1282 /* If we are in the middle of a sequence, we use DEF from a previous
1283 statement. Otherwise, OPRND has to be a result of type promotion. */
1286 half_type
= *new_type
;
1292 if (!type_conversion_p (oprnd
, stmt
, false, &half_type
, &def_stmt
,
1295 || !vect_same_loop_or_bb_p (stmt
, def_stmt
))
1299 /* Can we perform the operation on a smaller type? */
1305 if (!int_fits_type_p (const_oprnd
, half_type
))
1307 /* HALF_TYPE is not enough. Try a bigger type if possible. */
1308 if (TYPE_PRECISION (type
) < (TYPE_PRECISION (half_type
) * 4))
1311 interm_type
= build_nonstandard_integer_type (
1312 TYPE_PRECISION (half_type
) * 2, TYPE_UNSIGNED (type
));
1313 if (!int_fits_type_p (const_oprnd
, interm_type
))
1320 /* Try intermediate type - HALF_TYPE is not enough for sure. */
1321 if (TYPE_PRECISION (type
) < (TYPE_PRECISION (half_type
) * 4))
1324 /* Check that HALF_TYPE size + shift amount <= INTERM_TYPE size.
1325 (e.g., if the original value was char, the shift amount is at most 8
1326 if we want to use short). */
1327 if (compare_tree_int (const_oprnd
, TYPE_PRECISION (half_type
)) == 1)
1330 interm_type
= build_nonstandard_integer_type (
1331 TYPE_PRECISION (half_type
) * 2, TYPE_UNSIGNED (type
));
1333 if (!vect_supportable_shift (code
, interm_type
))
1339 if (vect_supportable_shift (code
, half_type
))
1342 /* Try intermediate type - HALF_TYPE is not supported. */
1343 if (TYPE_PRECISION (type
) < (TYPE_PRECISION (half_type
) * 4))
1346 interm_type
= build_nonstandard_integer_type (
1347 TYPE_PRECISION (half_type
) * 2, TYPE_UNSIGNED (type
));
1349 if (!vect_supportable_shift (code
, interm_type
))
1358 /* There are four possible cases:
1359 1. OPRND is defined by a type promotion (in that case FIRST is TRUE, it's
1360 the first statement in the sequence)
1361 a. The original, HALF_TYPE, is not enough - we replace the promotion
1362 from HALF_TYPE to TYPE with a promotion to INTERM_TYPE.
1363 b. HALF_TYPE is sufficient, OPRND is set as the RHS of the original
1365 2. OPRND is defined by a pattern statement we created.
1366 a. Its type is not sufficient for the operation, we create a new stmt:
1367 a type conversion for OPRND from HALF_TYPE to INTERM_TYPE. We store
1368 this statement in NEW_DEF_STMT, and it is later put in
1369 STMT_VINFO_PATTERN_DEF_SEQ of the pattern statement for STMT.
1370 b. OPRND is good to use in the new statement. */
1375 /* Replace the original type conversion HALF_TYPE->TYPE with
1376 HALF_TYPE->INTERM_TYPE. */
1377 if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
)))
1379 new_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
));
1380 /* Check if the already created pattern stmt is what we need. */
1381 if (!is_gimple_assign (new_stmt
)
1382 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (new_stmt
))
1383 || TREE_TYPE (gimple_assign_lhs (new_stmt
)) != interm_type
)
1386 stmts
->safe_push (def_stmt
);
1387 oprnd
= gimple_assign_lhs (new_stmt
);
1391 /* Create NEW_OPRND = (INTERM_TYPE) OPRND. */
1392 oprnd
= gimple_assign_rhs1 (def_stmt
);
1393 new_oprnd
= make_ssa_name (interm_type
);
1394 new_stmt
= gimple_build_assign (new_oprnd
, NOP_EXPR
, oprnd
);
1395 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
)) = new_stmt
;
1396 stmts
->safe_push (def_stmt
);
1402 /* Retrieve the operand before the type promotion. */
1403 oprnd
= gimple_assign_rhs1 (def_stmt
);
1410 /* Create a type conversion HALF_TYPE->INTERM_TYPE. */
1411 new_oprnd
= make_ssa_name (interm_type
);
1412 new_stmt
= gimple_build_assign (new_oprnd
, NOP_EXPR
, oprnd
);
1414 *new_def_stmt
= new_stmt
;
1417 /* Otherwise, OPRND is already set. */
1421 *new_type
= interm_type
;
1423 *new_type
= half_type
;
1426 *op1
= fold_convert (*new_type
, const_oprnd
);
1432 /* Try to find a statement or a sequence of statements that can be performed
1436 TYPE x_T, res0_T, res1_T;
1439 S2 x_T = (TYPE) x_t;
1440 S3 res0_T = op (x_T, C0);
1441 S4 res1_T = op (res0_T, C1);
1442 S5 ... = () res1_T; - type demotion
1444 where type 'TYPE' is at least double the size of type 'type', C0 and C1 are
1446 Check if S3 and S4 can be done on a smaller type than 'TYPE', it can either
1447 be 'type' or some intermediate type. For now, we expect S5 to be a type
1448 demotion operation. We also check that S3 and S4 have only one use. */
1451 vect_recog_over_widening_pattern (vec
<gimple
*> *stmts
,
1452 tree
*type_in
, tree
*type_out
)
1454 gimple
*stmt
= stmts
->pop ();
1455 gimple
*pattern_stmt
= NULL
, *new_def_stmt
, *prev_stmt
= NULL
,
1457 tree op0
, op1
, vectype
= NULL_TREE
, use_lhs
, use_type
;
1458 tree var
= NULL_TREE
, new_type
= NULL_TREE
, new_oprnd
;
1465 if (!vinfo_for_stmt (stmt
)
1466 || STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (stmt
)))
1469 new_def_stmt
= NULL
;
1470 if (!vect_operation_fits_smaller_type (stmt
, var
, &new_type
,
1471 &op0
, &op1
, &new_def_stmt
,
1480 /* STMT can be performed on a smaller type. Check its uses. */
1481 use_stmt
= vect_single_imm_use (stmt
);
1482 if (!use_stmt
|| !is_gimple_assign (use_stmt
))
1485 /* Create pattern statement for STMT. */
1486 vectype
= get_vectype_for_scalar_type (new_type
);
1490 /* We want to collect all the statements for which we create pattern
1491 statetments, except for the case when the last statement in the
1492 sequence doesn't have a corresponding pattern statement. In such
1493 case we associate the last pattern statement with the last statement
1494 in the sequence. Therefore, we only add the original statement to
1495 the list if we know that it is not the last. */
1497 stmts
->safe_push (prev_stmt
);
1499 var
= vect_recog_temp_ssa_var (new_type
, NULL
);
1501 = gimple_build_assign (var
, gimple_assign_rhs_code (stmt
), op0
, op1
);
1502 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt
)) = pattern_stmt
;
1503 new_pattern_def_seq (vinfo_for_stmt (stmt
), new_def_stmt
);
1505 if (dump_enabled_p ())
1507 dump_printf_loc (MSG_NOTE
, vect_location
,
1508 "created pattern stmt: ");
1509 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
1512 type
= gimple_expr_type (stmt
);
1519 /* We got a sequence. We expect it to end with a type demotion operation.
1520 Otherwise, we quit (for now). There are three possible cases: the
1521 conversion is to NEW_TYPE (we don't do anything), the conversion is to
1522 a type bigger than NEW_TYPE and/or the signedness of USE_TYPE and
1523 NEW_TYPE differs (we create a new conversion statement). */
1524 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt
)))
1526 use_lhs
= gimple_assign_lhs (use_stmt
);
1527 use_type
= TREE_TYPE (use_lhs
);
1528 /* Support only type demotion or signedess change. */
1529 if (!INTEGRAL_TYPE_P (use_type
)
1530 || TYPE_PRECISION (type
) <= TYPE_PRECISION (use_type
))
1533 /* Check that NEW_TYPE is not bigger than the conversion result. */
1534 if (TYPE_PRECISION (new_type
) > TYPE_PRECISION (use_type
))
1537 if (TYPE_UNSIGNED (new_type
) != TYPE_UNSIGNED (use_type
)
1538 || TYPE_PRECISION (new_type
) != TYPE_PRECISION (use_type
))
1540 /* Create NEW_TYPE->USE_TYPE conversion. */
1541 new_oprnd
= make_ssa_name (use_type
);
1542 pattern_stmt
= gimple_build_assign (new_oprnd
, NOP_EXPR
, var
);
1543 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use_stmt
)) = pattern_stmt
;
1545 *type_in
= get_vectype_for_scalar_type (new_type
);
1546 *type_out
= get_vectype_for_scalar_type (use_type
);
1548 /* We created a pattern statement for the last statement in the
1549 sequence, so we don't need to associate it with the pattern
1550 statement created for PREV_STMT. Therefore, we add PREV_STMT
1551 to the list in order to mark it later in vect_pattern_recog_1. */
1553 stmts
->safe_push (prev_stmt
);
1558 STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (use_stmt
))
1559 = STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (prev_stmt
));
1562 *type_out
= NULL_TREE
;
1565 stmts
->safe_push (use_stmt
);
1568 /* TODO: support general case, create a conversion to the correct type. */
1571 /* Pattern detected. */
1572 if (dump_enabled_p ())
1574 dump_printf_loc (MSG_NOTE
, vect_location
,
1575 "vect_recog_over_widening_pattern: detected: ");
1576 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
1579 return pattern_stmt
;
1582 /* Detect widening shift pattern:
1588 S2 a_T = (TYPE) a_t;
1589 S3 res_T = a_T << CONST;
1591 where type 'TYPE' is at least double the size of type 'type'.
1593 Also detect cases where the shift result is immediately converted
1594 to another type 'result_type' that is no larger in size than 'TYPE'.
1595 In those cases we perform a widen-shift that directly results in
1596 'result_type', to avoid a possible over-widening situation:
1600 result_type res_result;
1603 S2 a_T = (TYPE) a_t;
1604 S3 res_T = a_T << CONST;
1605 S4 res_result = (result_type) res_T;
1606 '--> res_result' = a_t w<< CONST;
1608 And a case when 'TYPE' is 4 times bigger than 'type'. In that case we
1609 create an additional pattern stmt for S2 to create a variable of an
1610 intermediate type, and perform widen-shift on the intermediate type:
1614 TYPE a_T, res_T, res_T';
1617 S2 a_T = (TYPE) a_t;
1618 '--> a_it = (interm_type) a_t;
1619 S3 res_T = a_T << CONST;
1620 '--> res_T' = a_it <<* CONST;
1624 * STMTS: Contains a stmt from which the pattern search begins.
1625 In case of unsigned widen-shift, the original stmt (S3) is replaced with S4
1626 in STMTS. When an intermediate type is used and a pattern statement is
1627 created for S2, we also put S2 here (before S3).
1631 * TYPE_IN: The type of the input arguments to the pattern.
1633 * TYPE_OUT: The type of the output of this pattern.
1635 * Return value: A new stmt that will be used to replace the sequence of
1636 stmts that constitute the pattern. In this case it will be:
1637 WIDEN_LSHIFT_EXPR <a_t, CONST>. */
1640 vect_recog_widen_shift_pattern (vec
<gimple
*> *stmts
,
1641 tree
*type_in
, tree
*type_out
)
1643 gimple
*last_stmt
= stmts
->pop ();
1645 tree oprnd0
, oprnd1
;
1646 tree type
, half_type0
;
1647 gimple
*pattern_stmt
;
1648 tree vectype
, vectype_out
= NULL_TREE
;
1650 enum tree_code dummy_code
;
1652 vec
<tree
> dummy_vec
;
1656 if (!is_gimple_assign (last_stmt
) || !vinfo_for_stmt (last_stmt
))
1659 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (last_stmt
)))
1662 if (gimple_assign_rhs_code (last_stmt
) != LSHIFT_EXPR
)
1665 oprnd0
= gimple_assign_rhs1 (last_stmt
);
1666 oprnd1
= gimple_assign_rhs2 (last_stmt
);
1667 if (TREE_CODE (oprnd0
) != SSA_NAME
|| TREE_CODE (oprnd1
) != INTEGER_CST
)
1670 /* Check operand 0: it has to be defined by a type promotion. */
1671 if (!type_conversion_p (oprnd0
, last_stmt
, false, &half_type0
, &def_stmt0
,
1676 /* Check operand 1: has to be positive. We check that it fits the type
1677 in vect_handle_widen_op_by_const (). */
1678 if (tree_int_cst_compare (oprnd1
, size_zero_node
) <= 0)
1681 oprnd0
= gimple_assign_rhs1 (def_stmt0
);
1682 type
= gimple_expr_type (last_stmt
);
1684 /* Check for subsequent conversion to another type. */
1685 use_stmt
= vect_single_imm_use (last_stmt
);
1686 if (use_stmt
&& is_gimple_assign (use_stmt
)
1687 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt
))
1688 && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt
)))
1690 tree use_lhs
= gimple_assign_lhs (use_stmt
);
1691 tree use_type
= TREE_TYPE (use_lhs
);
1693 if (INTEGRAL_TYPE_P (use_type
)
1694 && TYPE_PRECISION (use_type
) <= TYPE_PRECISION (type
))
1696 last_stmt
= use_stmt
;
1701 /* Check if this a widening operation. */
1702 gimple
*wstmt
= NULL
;
1703 if (!vect_handle_widen_op_by_const (last_stmt
, LSHIFT_EXPR
, oprnd1
,
1705 type
, &half_type0
, def_stmt0
))
1708 /* Pattern detected. */
1709 if (dump_enabled_p ())
1710 dump_printf_loc (MSG_NOTE
, vect_location
,
1711 "vect_recog_widen_shift_pattern: detected:\n");
1713 /* Check target support. */
1714 vectype
= get_vectype_for_scalar_type (half_type0
);
1715 vectype_out
= get_vectype_for_scalar_type (type
);
1719 || !supportable_widening_operation (WIDEN_LSHIFT_EXPR
, last_stmt
,
1720 vectype_out
, vectype
,
1721 &dummy_code
, &dummy_code
,
1722 &dummy_int
, &dummy_vec
))
1726 *type_out
= vectype_out
;
1728 /* Pattern supported. Create a stmt to be used to replace the pattern. */
1729 var
= vect_recog_temp_ssa_var (type
, NULL
);
1731 gimple_build_assign (var
, WIDEN_LSHIFT_EXPR
, oprnd0
, oprnd1
);
1734 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
1735 new_pattern_def_seq (stmt_vinfo
, wstmt
);
1736 stmt_vec_info new_stmt_info
1737 = new_stmt_vec_info (wstmt
, stmt_vinfo
->vinfo
);
1738 set_vinfo_for_stmt (wstmt
, new_stmt_info
);
1739 STMT_VINFO_VECTYPE (new_stmt_info
) = vectype
;
1742 if (dump_enabled_p ())
1743 dump_gimple_stmt_loc (MSG_NOTE
, vect_location
, TDF_SLIM
, pattern_stmt
, 0);
1745 stmts
->safe_push (last_stmt
);
1746 return pattern_stmt
;
1749 /* Detect a rotate pattern wouldn't be otherwise vectorized:
1753 S0 a_t = b_t r<< c_t;
1757 * STMTS: Contains a stmt from which the pattern search begins,
1758 i.e. the shift/rotate stmt. The original stmt (S0) is replaced
1762 S2 e_t = d_t & (B - 1);
1763 S3 f_t = b_t << c_t;
1764 S4 g_t = b_t >> e_t;
1767 where B is element bitsize of type.
1771 * TYPE_IN: The type of the input arguments to the pattern.
1773 * TYPE_OUT: The type of the output of this pattern.
1775 * Return value: A new stmt that will be used to replace the rotate
1779 vect_recog_rotate_pattern (vec
<gimple
*> *stmts
, tree
*type_in
, tree
*type_out
)
1781 gimple
*last_stmt
= stmts
->pop ();
1782 tree oprnd0
, oprnd1
, lhs
, var
, var1
, var2
, vectype
, type
, stype
, def
, def2
;
1783 gimple
*pattern_stmt
, *def_stmt
;
1784 enum tree_code rhs_code
;
1785 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
1786 vec_info
*vinfo
= stmt_vinfo
->vinfo
;
1787 enum vect_def_type dt
;
1788 optab optab1
, optab2
;
1789 edge ext_def
= NULL
;
1791 if (!is_gimple_assign (last_stmt
))
1794 rhs_code
= gimple_assign_rhs_code (last_stmt
);
1804 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
))
1807 lhs
= gimple_assign_lhs (last_stmt
);
1808 oprnd0
= gimple_assign_rhs1 (last_stmt
);
1809 type
= TREE_TYPE (oprnd0
);
1810 oprnd1
= gimple_assign_rhs2 (last_stmt
);
1811 if (TREE_CODE (oprnd0
) != SSA_NAME
1812 || TYPE_PRECISION (TREE_TYPE (lhs
)) != TYPE_PRECISION (type
)
1813 || !INTEGRAL_TYPE_P (type
)
1814 || !TYPE_UNSIGNED (type
))
1817 if (!vect_is_simple_use (oprnd1
, vinfo
, &def_stmt
, &dt
))
1820 if (dt
!= vect_internal_def
1821 && dt
!= vect_constant_def
1822 && dt
!= vect_external_def
)
1825 vectype
= get_vectype_for_scalar_type (type
);
1826 if (vectype
== NULL_TREE
)
1829 /* If vector/vector or vector/scalar rotate is supported by the target,
1830 don't do anything here. */
1831 optab1
= optab_for_tree_code (rhs_code
, vectype
, optab_vector
);
1833 && optab_handler (optab1
, TYPE_MODE (vectype
)) != CODE_FOR_nothing
)
1836 if (is_a
<bb_vec_info
> (vinfo
) || dt
!= vect_internal_def
)
1838 optab2
= optab_for_tree_code (rhs_code
, vectype
, optab_scalar
);
1840 && optab_handler (optab2
, TYPE_MODE (vectype
)) != CODE_FOR_nothing
)
1844 /* If vector/vector or vector/scalar shifts aren't supported by the target,
1845 don't do anything here either. */
1846 optab1
= optab_for_tree_code (LSHIFT_EXPR
, vectype
, optab_vector
);
1847 optab2
= optab_for_tree_code (RSHIFT_EXPR
, vectype
, optab_vector
);
1849 || optab_handler (optab1
, TYPE_MODE (vectype
)) == CODE_FOR_nothing
1851 || optab_handler (optab2
, TYPE_MODE (vectype
)) == CODE_FOR_nothing
)
1853 if (! is_a
<bb_vec_info
> (vinfo
) && dt
== vect_internal_def
)
1855 optab1
= optab_for_tree_code (LSHIFT_EXPR
, vectype
, optab_scalar
);
1856 optab2
= optab_for_tree_code (RSHIFT_EXPR
, vectype
, optab_scalar
);
1858 || optab_handler (optab1
, TYPE_MODE (vectype
)) == CODE_FOR_nothing
1860 || optab_handler (optab2
, TYPE_MODE (vectype
)) == CODE_FOR_nothing
)
1865 *type_out
= vectype
;
1866 if (*type_in
== NULL_TREE
)
1869 if (dt
== vect_external_def
1870 && TREE_CODE (oprnd1
) == SSA_NAME
1871 && is_a
<loop_vec_info
> (vinfo
))
1873 struct loop
*loop
= as_a
<loop_vec_info
> (vinfo
)->loop
;
1874 ext_def
= loop_preheader_edge (loop
);
1875 if (!SSA_NAME_IS_DEFAULT_DEF (oprnd1
))
1877 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (oprnd1
));
1879 || !dominated_by_p (CDI_DOMINATORS
, ext_def
->dest
, bb
))
1885 if (TREE_CODE (oprnd1
) == INTEGER_CST
1886 || TYPE_MODE (TREE_TYPE (oprnd1
)) == TYPE_MODE (type
))
1888 else if (def_stmt
&& gimple_assign_cast_p (def_stmt
))
1890 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1891 if (TYPE_MODE (TREE_TYPE (rhs1
)) == TYPE_MODE (type
)
1892 && TYPE_PRECISION (TREE_TYPE (rhs1
))
1893 == TYPE_PRECISION (type
))
1897 STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo
) = NULL
;
1898 if (def
== NULL_TREE
)
1900 def
= vect_recog_temp_ssa_var (type
, NULL
);
1901 def_stmt
= gimple_build_assign (def
, NOP_EXPR
, oprnd1
);
1905 = gsi_insert_on_edge_immediate (ext_def
, def_stmt
);
1906 gcc_assert (!new_bb
);
1909 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
1911 stype
= TREE_TYPE (def
);
1913 if (TREE_CODE (def
) == INTEGER_CST
)
1915 if (!tree_fits_uhwi_p (def
)
1916 || tree_to_uhwi (def
) >= GET_MODE_PRECISION (TYPE_MODE (type
))
1917 || integer_zerop (def
))
1919 def2
= build_int_cst (stype
,
1920 GET_MODE_PRECISION (TYPE_MODE (type
))
1921 - tree_to_uhwi (def
));
1925 tree vecstype
= get_vectype_for_scalar_type (stype
);
1926 stmt_vec_info def_stmt_vinfo
;
1928 if (vecstype
== NULL_TREE
)
1930 def2
= vect_recog_temp_ssa_var (stype
, NULL
);
1931 def_stmt
= gimple_build_assign (def2
, NEGATE_EXPR
, def
);
1935 = gsi_insert_on_edge_immediate (ext_def
, def_stmt
);
1936 gcc_assert (!new_bb
);
1940 def_stmt_vinfo
= new_stmt_vec_info (def_stmt
, vinfo
);
1941 set_vinfo_for_stmt (def_stmt
, def_stmt_vinfo
);
1942 STMT_VINFO_VECTYPE (def_stmt_vinfo
) = vecstype
;
1943 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
1946 def2
= vect_recog_temp_ssa_var (stype
, NULL
);
1948 = build_int_cst (stype
, GET_MODE_PRECISION (TYPE_MODE (stype
)) - 1);
1949 def_stmt
= gimple_build_assign (def2
, BIT_AND_EXPR
,
1950 gimple_assign_lhs (def_stmt
), mask
);
1954 = gsi_insert_on_edge_immediate (ext_def
, def_stmt
);
1955 gcc_assert (!new_bb
);
1959 def_stmt_vinfo
= new_stmt_vec_info (def_stmt
, vinfo
);
1960 set_vinfo_for_stmt (def_stmt
, def_stmt_vinfo
);
1961 STMT_VINFO_VECTYPE (def_stmt_vinfo
) = vecstype
;
1962 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
1966 var1
= vect_recog_temp_ssa_var (type
, NULL
);
1967 def_stmt
= gimple_build_assign (var1
, rhs_code
== LROTATE_EXPR
1968 ? LSHIFT_EXPR
: RSHIFT_EXPR
,
1970 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
1972 var2
= vect_recog_temp_ssa_var (type
, NULL
);
1973 def_stmt
= gimple_build_assign (var2
, rhs_code
== LROTATE_EXPR
1974 ? RSHIFT_EXPR
: LSHIFT_EXPR
,
1976 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
1978 /* Pattern detected. */
1979 if (dump_enabled_p ())
1980 dump_printf_loc (MSG_NOTE
, vect_location
,
1981 "vect_recog_rotate_pattern: detected:\n");
1983 /* Pattern supported. Create a stmt to be used to replace the pattern. */
1984 var
= vect_recog_temp_ssa_var (type
, NULL
);
1985 pattern_stmt
= gimple_build_assign (var
, BIT_IOR_EXPR
, var1
, var2
);
1987 if (dump_enabled_p ())
1988 dump_gimple_stmt_loc (MSG_NOTE
, vect_location
, TDF_SLIM
, pattern_stmt
, 0);
1990 stmts
->safe_push (last_stmt
);
1991 return pattern_stmt
;
1994 /* Detect a vector by vector shift pattern that wouldn't be otherwise
2002 S3 res_T = b_T op a_t;
2004 where type 'TYPE' is a type with different size than 'type',
2005 and op is <<, >> or rotate.
2010 TYPE b_T, c_T, res_T;
2013 S1 a_t = (type) c_T;
2015 S3 res_T = b_T op a_t;
2019 * STMTS: Contains a stmt from which the pattern search begins,
2020 i.e. the shift/rotate stmt. The original stmt (S3) is replaced
2021 with a shift/rotate which has same type on both operands, in the
2022 second case just b_T op c_T, in the first case with added cast
2023 from a_t to c_T in STMT_VINFO_PATTERN_DEF_SEQ.
2027 * TYPE_IN: The type of the input arguments to the pattern.
2029 * TYPE_OUT: The type of the output of this pattern.
2031 * Return value: A new stmt that will be used to replace the shift/rotate
2035 vect_recog_vector_vector_shift_pattern (vec
<gimple
*> *stmts
,
2036 tree
*type_in
, tree
*type_out
)
2038 gimple
*last_stmt
= stmts
->pop ();
2039 tree oprnd0
, oprnd1
, lhs
, var
;
2040 gimple
*pattern_stmt
, *def_stmt
;
2041 enum tree_code rhs_code
;
2042 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
2043 vec_info
*vinfo
= stmt_vinfo
->vinfo
;
2044 enum vect_def_type dt
;
2046 if (!is_gimple_assign (last_stmt
))
2049 rhs_code
= gimple_assign_rhs_code (last_stmt
);
2061 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
))
2064 lhs
= gimple_assign_lhs (last_stmt
);
2065 oprnd0
= gimple_assign_rhs1 (last_stmt
);
2066 oprnd1
= gimple_assign_rhs2 (last_stmt
);
2067 if (TREE_CODE (oprnd0
) != SSA_NAME
2068 || TREE_CODE (oprnd1
) != SSA_NAME
2069 || TYPE_MODE (TREE_TYPE (oprnd0
)) == TYPE_MODE (TREE_TYPE (oprnd1
))
2070 || TYPE_PRECISION (TREE_TYPE (oprnd1
))
2071 != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (oprnd1
)))
2072 || TYPE_PRECISION (TREE_TYPE (lhs
))
2073 != TYPE_PRECISION (TREE_TYPE (oprnd0
)))
2076 if (!vect_is_simple_use (oprnd1
, vinfo
, &def_stmt
, &dt
))
2079 if (dt
!= vect_internal_def
)
2082 *type_in
= get_vectype_for_scalar_type (TREE_TYPE (oprnd0
));
2083 *type_out
= *type_in
;
2084 if (*type_in
== NULL_TREE
)
2087 tree def
= NULL_TREE
;
2088 stmt_vec_info def_vinfo
= vinfo_for_stmt (def_stmt
);
2089 if (!STMT_VINFO_IN_PATTERN_P (def_vinfo
) && gimple_assign_cast_p (def_stmt
))
2091 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
2092 if (TYPE_MODE (TREE_TYPE (rhs1
)) == TYPE_MODE (TREE_TYPE (oprnd0
))
2093 && TYPE_PRECISION (TREE_TYPE (rhs1
))
2094 == TYPE_PRECISION (TREE_TYPE (oprnd0
)))
2096 if (TYPE_PRECISION (TREE_TYPE (oprnd1
))
2097 >= TYPE_PRECISION (TREE_TYPE (rhs1
)))
2102 = build_low_bits_mask (TREE_TYPE (rhs1
),
2103 TYPE_PRECISION (TREE_TYPE (oprnd1
)));
2104 def
= vect_recog_temp_ssa_var (TREE_TYPE (rhs1
), NULL
);
2105 def_stmt
= gimple_build_assign (def
, BIT_AND_EXPR
, rhs1
, mask
);
2106 new_pattern_def_seq (stmt_vinfo
, def_stmt
);
2111 if (def
== NULL_TREE
)
2113 def
= vect_recog_temp_ssa_var (TREE_TYPE (oprnd0
), NULL
);
2114 def_stmt
= gimple_build_assign (def
, NOP_EXPR
, oprnd1
);
2115 new_pattern_def_seq (stmt_vinfo
, def_stmt
);
2118 /* Pattern detected. */
2119 if (dump_enabled_p ())
2120 dump_printf_loc (MSG_NOTE
, vect_location
,
2121 "vect_recog_vector_vector_shift_pattern: detected:\n");
2123 /* Pattern supported. Create a stmt to be used to replace the pattern. */
2124 var
= vect_recog_temp_ssa_var (TREE_TYPE (oprnd0
), NULL
);
2125 pattern_stmt
= gimple_build_assign (var
, rhs_code
, oprnd0
, def
);
2127 if (dump_enabled_p ())
2128 dump_gimple_stmt_loc (MSG_NOTE
, vect_location
, TDF_SLIM
, pattern_stmt
, 0);
2130 stmts
->safe_push (last_stmt
);
2131 return pattern_stmt
;
2134 /* Return true iff the target has a vector optab implementing the operation
2135 CODE on type VECTYPE. */
2138 target_has_vecop_for_code (tree_code code
, tree vectype
)
2140 optab voptab
= optab_for_tree_code (code
, vectype
, optab_vector
);
2142 && optab_handler (voptab
, TYPE_MODE (vectype
)) != CODE_FOR_nothing
;
2145 /* Verify that the target has optabs of VECTYPE to perform all the steps
2146 needed by the multiplication-by-immediate synthesis algorithm described by
2147 ALG and VAR. If SYNTH_SHIFT_P is true ensure that vector addition is
2148 present. Return true iff the target supports all the steps. */
2151 target_supports_mult_synth_alg (struct algorithm
*alg
, mult_variant var
,
2152 tree vectype
, bool synth_shift_p
)
2154 if (alg
->op
[0] != alg_zero
&& alg
->op
[0] != alg_m
)
2157 bool supports_vminus
= target_has_vecop_for_code (MINUS_EXPR
, vectype
);
2158 bool supports_vplus
= target_has_vecop_for_code (PLUS_EXPR
, vectype
);
2160 if (var
== negate_variant
2161 && !target_has_vecop_for_code (NEGATE_EXPR
, vectype
))
2164 /* If we must synthesize shifts with additions make sure that vector
2165 addition is available. */
2166 if ((var
== add_variant
|| synth_shift_p
) && !supports_vplus
)
2169 for (int i
= 1; i
< alg
->ops
; i
++)
2177 case alg_add_factor
:
2178 if (!supports_vplus
)
2183 case alg_sub_factor
:
2184 if (!supports_vminus
)
2190 case alg_impossible
:
2200 /* Synthesize a left shift of OP by AMNT bits using a series of additions and
2201 putting the final result in DEST. Append all statements but the last into
2202 VINFO. Return the last statement. */
2205 synth_lshift_by_additions (tree dest
, tree op
, HOST_WIDE_INT amnt
,
2206 stmt_vec_info vinfo
)
2209 tree itype
= TREE_TYPE (op
);
2211 gcc_assert (amnt
>= 0);
2212 for (i
= 0; i
< amnt
; i
++)
2214 tree tmp_var
= (i
< amnt
- 1) ? vect_recog_temp_ssa_var (itype
, NULL
)
2217 = gimple_build_assign (tmp_var
, PLUS_EXPR
, prev_res
, prev_res
);
2220 append_pattern_def_seq (vinfo
, stmt
);
2228 /* Helper for vect_synth_mult_by_constant. Apply a binary operation
2229 CODE to operands OP1 and OP2, creating a new temporary SSA var in
2230 the process if necessary. Append the resulting assignment statements
2231 to the sequence in STMT_VINFO. Return the SSA variable that holds the
2232 result of the binary operation. If SYNTH_SHIFT_P is true synthesize
2233 left shifts using additions. */
2236 apply_binop_and_append_stmt (tree_code code
, tree op1
, tree op2
,
2237 stmt_vec_info stmt_vinfo
, bool synth_shift_p
)
2239 if (integer_zerop (op2
)
2240 && (code
== LSHIFT_EXPR
2241 || code
== PLUS_EXPR
))
2243 gcc_assert (TREE_CODE (op1
) == SSA_NAME
);
2248 tree itype
= TREE_TYPE (op1
);
2249 tree tmp_var
= vect_recog_temp_ssa_var (itype
, NULL
);
2251 if (code
== LSHIFT_EXPR
2254 stmt
= synth_lshift_by_additions (tmp_var
, op1
, TREE_INT_CST_LOW (op2
),
2256 append_pattern_def_seq (stmt_vinfo
, stmt
);
2260 stmt
= gimple_build_assign (tmp_var
, code
, op1
, op2
);
2261 append_pattern_def_seq (stmt_vinfo
, stmt
);
2265 /* Synthesize a multiplication of OP by an INTEGER_CST VAL using shifts
2266 and simple arithmetic operations to be vectorized. Record the statements
2267 produced in STMT_VINFO and return the last statement in the sequence or
2268 NULL if it's not possible to synthesize such a multiplication.
2269 This function mirrors the behavior of expand_mult_const in expmed.c but
2270 works on tree-ssa form. */
2273 vect_synth_mult_by_constant (tree op
, tree val
,
2274 stmt_vec_info stmt_vinfo
)
2276 tree itype
= TREE_TYPE (op
);
2277 machine_mode mode
= TYPE_MODE (itype
);
2278 struct algorithm alg
;
2279 mult_variant variant
;
2280 if (!tree_fits_shwi_p (val
))
2283 /* Multiplication synthesis by shifts, adds and subs can introduce
2284 signed overflow where the original operation didn't. Perform the
2285 operations on an unsigned type and cast back to avoid this.
2286 In the future we may want to relax this for synthesis algorithms
2287 that we can prove do not cause unexpected overflow. */
2288 bool cast_to_unsigned_p
= !TYPE_OVERFLOW_WRAPS (itype
);
2290 tree multtype
= cast_to_unsigned_p
? unsigned_type_for (itype
) : itype
;
2292 /* Targets that don't support vector shifts but support vector additions
2293 can synthesize shifts that way. */
2294 bool synth_shift_p
= !vect_supportable_shift (LSHIFT_EXPR
, multtype
);
2296 HOST_WIDE_INT hwval
= tree_to_shwi (val
);
2297 /* Use MAX_COST here as we don't want to limit the sequence on rtx costs.
2298 The vectorizer's benefit analysis will decide whether it's beneficial
2300 bool possible
= choose_mult_variant (mode
, hwval
, &alg
,
2301 &variant
, MAX_COST
);
2305 tree vectype
= get_vectype_for_scalar_type (multtype
);
2308 || !target_supports_mult_synth_alg (&alg
, variant
,
2309 vectype
, synth_shift_p
))
2314 /* Clear out the sequence of statements so we can populate it below. */
2315 STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo
) = NULL
;
2316 gimple
*stmt
= NULL
;
2318 if (cast_to_unsigned_p
)
2320 tree tmp_op
= vect_recog_temp_ssa_var (multtype
, NULL
);
2321 stmt
= gimple_build_assign (tmp_op
, CONVERT_EXPR
, op
);
2322 append_pattern_def_seq (stmt_vinfo
, stmt
);
2326 if (alg
.op
[0] == alg_zero
)
2327 accumulator
= build_int_cst (multtype
, 0);
2331 bool needs_fixup
= (variant
== negate_variant
)
2332 || (variant
== add_variant
);
2334 for (int i
= 1; i
< alg
.ops
; i
++)
2336 tree shft_log
= build_int_cst (multtype
, alg
.log
[i
]);
2337 tree accum_tmp
= vect_recog_temp_ssa_var (multtype
, NULL
);
2338 tree tmp_var
= NULL_TREE
;
2345 = synth_lshift_by_additions (accum_tmp
, accumulator
, alg
.log
[i
],
2348 stmt
= gimple_build_assign (accum_tmp
, LSHIFT_EXPR
, accumulator
,
2353 = apply_binop_and_append_stmt (LSHIFT_EXPR
, op
, shft_log
,
2354 stmt_vinfo
, synth_shift_p
);
2355 stmt
= gimple_build_assign (accum_tmp
, PLUS_EXPR
, accumulator
,
2359 tmp_var
= apply_binop_and_append_stmt (LSHIFT_EXPR
, op
,
2360 shft_log
, stmt_vinfo
,
2362 /* In some algorithms the first step involves zeroing the
2363 accumulator. If subtracting from such an accumulator
2364 just emit the negation directly. */
2365 if (integer_zerop (accumulator
))
2366 stmt
= gimple_build_assign (accum_tmp
, NEGATE_EXPR
, tmp_var
);
2368 stmt
= gimple_build_assign (accum_tmp
, MINUS_EXPR
, accumulator
,
2373 = apply_binop_and_append_stmt (LSHIFT_EXPR
, accumulator
, shft_log
,
2374 stmt_vinfo
, synth_shift_p
);
2375 stmt
= gimple_build_assign (accum_tmp
, PLUS_EXPR
, tmp_var
, op
);
2379 = apply_binop_and_append_stmt (LSHIFT_EXPR
, accumulator
, shft_log
,
2380 stmt_vinfo
, synth_shift_p
);
2381 stmt
= gimple_build_assign (accum_tmp
, MINUS_EXPR
, tmp_var
, op
);
2383 case alg_add_factor
:
2385 = apply_binop_and_append_stmt (LSHIFT_EXPR
, accumulator
, shft_log
,
2386 stmt_vinfo
, synth_shift_p
);
2387 stmt
= gimple_build_assign (accum_tmp
, PLUS_EXPR
, accumulator
,
2390 case alg_sub_factor
:
2392 = apply_binop_and_append_stmt (LSHIFT_EXPR
, accumulator
, shft_log
,
2393 stmt_vinfo
, synth_shift_p
);
2394 stmt
= gimple_build_assign (accum_tmp
, MINUS_EXPR
, tmp_var
,
2400 /* We don't want to append the last stmt in the sequence to stmt_vinfo
2401 but rather return it directly. */
2403 if ((i
< alg
.ops
- 1) || needs_fixup
|| cast_to_unsigned_p
)
2404 append_pattern_def_seq (stmt_vinfo
, stmt
);
2405 accumulator
= accum_tmp
;
2407 if (variant
== negate_variant
)
2409 tree accum_tmp
= vect_recog_temp_ssa_var (multtype
, NULL
);
2410 stmt
= gimple_build_assign (accum_tmp
, NEGATE_EXPR
, accumulator
);
2411 accumulator
= accum_tmp
;
2412 if (cast_to_unsigned_p
)
2413 append_pattern_def_seq (stmt_vinfo
, stmt
);
2415 else if (variant
== add_variant
)
2417 tree accum_tmp
= vect_recog_temp_ssa_var (multtype
, NULL
);
2418 stmt
= gimple_build_assign (accum_tmp
, PLUS_EXPR
, accumulator
, op
);
2419 accumulator
= accum_tmp
;
2420 if (cast_to_unsigned_p
)
2421 append_pattern_def_seq (stmt_vinfo
, stmt
);
2423 /* Move back to a signed if needed. */
2424 if (cast_to_unsigned_p
)
2426 tree accum_tmp
= vect_recog_temp_ssa_var (itype
, NULL
);
2427 stmt
= gimple_build_assign (accum_tmp
, CONVERT_EXPR
, accumulator
);
2433 /* Detect multiplication by constant and convert it into a sequence of
2434 shifts and additions, subtractions, negations. We reuse the
2435 choose_mult_variant algorithms from expmed.c
2439 STMTS: Contains a stmt from which the pattern search begins,
2444 * TYPE_IN: The type of the input arguments to the pattern.
2446 * TYPE_OUT: The type of the output of this pattern.
2448 * Return value: A new stmt that will be used to replace
2449 the multiplication. */
2452 vect_recog_mult_pattern (vec
<gimple
*> *stmts
,
2453 tree
*type_in
, tree
*type_out
)
2455 gimple
*last_stmt
= stmts
->pop ();
2456 tree oprnd0
, oprnd1
, vectype
, itype
;
2457 gimple
*pattern_stmt
;
2458 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
2460 if (!is_gimple_assign (last_stmt
))
2463 if (gimple_assign_rhs_code (last_stmt
) != MULT_EXPR
)
2466 oprnd0
= gimple_assign_rhs1 (last_stmt
);
2467 oprnd1
= gimple_assign_rhs2 (last_stmt
);
2468 itype
= TREE_TYPE (oprnd0
);
2470 if (TREE_CODE (oprnd0
) != SSA_NAME
2471 || TREE_CODE (oprnd1
) != INTEGER_CST
2472 || !INTEGRAL_TYPE_P (itype
)
2473 || TYPE_PRECISION (itype
) != GET_MODE_PRECISION (TYPE_MODE (itype
)))
2476 vectype
= get_vectype_for_scalar_type (itype
);
2477 if (vectype
== NULL_TREE
)
2480 /* If the target can handle vectorized multiplication natively,
2481 don't attempt to optimize this. */
2482 optab mul_optab
= optab_for_tree_code (MULT_EXPR
, vectype
, optab_default
);
2483 if (mul_optab
!= unknown_optab
)
2485 machine_mode vec_mode
= TYPE_MODE (vectype
);
2486 int icode
= (int) optab_handler (mul_optab
, vec_mode
);
2487 if (icode
!= CODE_FOR_nothing
)
2491 pattern_stmt
= vect_synth_mult_by_constant (oprnd0
, oprnd1
, stmt_vinfo
);
2495 /* Pattern detected. */
2496 if (dump_enabled_p ())
2497 dump_printf_loc (MSG_NOTE
, vect_location
,
2498 "vect_recog_mult_pattern: detected:\n");
2500 if (dump_enabled_p ())
2501 dump_gimple_stmt_loc (MSG_NOTE
, vect_location
, TDF_SLIM
,
2504 stmts
->safe_push (last_stmt
);
2506 *type_out
= vectype
;
2508 return pattern_stmt
;
2511 /* Detect a signed division by a constant that wouldn't be
2512 otherwise vectorized:
2518 where type 'type' is an integral type and N is a constant.
2520 Similarly handle modulo by a constant:
2526 * STMTS: Contains a stmt from which the pattern search begins,
2527 i.e. the division stmt. S1 is replaced by if N is a power
2528 of two constant and type is signed:
2529 S3 y_t = b_t < 0 ? N - 1 : 0;
2531 S1' a_t = x_t >> log2 (N);
2533 S4 is replaced if N is a power of two constant and
2534 type is signed by (where *_T temporaries have unsigned type):
2535 S9 y_T = b_t < 0 ? -1U : 0U;
2536 S8 z_T = y_T >> (sizeof (type_t) * CHAR_BIT - log2 (N));
2537 S7 z_t = (type) z_T;
2539 S5 x_t = w_t & (N - 1);
2540 S4' a_t = x_t - z_t;
2544 * TYPE_IN: The type of the input arguments to the pattern.
2546 * TYPE_OUT: The type of the output of this pattern.
2548 * Return value: A new stmt that will be used to replace the division
2549 S1 or modulo S4 stmt. */
2552 vect_recog_divmod_pattern (vec
<gimple
*> *stmts
,
2553 tree
*type_in
, tree
*type_out
)
2555 gimple
*last_stmt
= stmts
->pop ();
2556 tree oprnd0
, oprnd1
, vectype
, itype
, cond
;
2557 gimple
*pattern_stmt
, *def_stmt
;
2558 enum tree_code rhs_code
;
2559 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
2560 vec_info
*vinfo
= stmt_vinfo
->vinfo
;
2563 int dummy_int
, prec
;
2564 stmt_vec_info def_stmt_vinfo
;
2566 if (!is_gimple_assign (last_stmt
))
2569 rhs_code
= gimple_assign_rhs_code (last_stmt
);
2572 case TRUNC_DIV_EXPR
:
2573 case TRUNC_MOD_EXPR
:
2579 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
))
2582 oprnd0
= gimple_assign_rhs1 (last_stmt
);
2583 oprnd1
= gimple_assign_rhs2 (last_stmt
);
2584 itype
= TREE_TYPE (oprnd0
);
2585 if (TREE_CODE (oprnd0
) != SSA_NAME
2586 || TREE_CODE (oprnd1
) != INTEGER_CST
2587 || TREE_CODE (itype
) != INTEGER_TYPE
2588 || TYPE_PRECISION (itype
) != GET_MODE_PRECISION (TYPE_MODE (itype
)))
2591 vectype
= get_vectype_for_scalar_type (itype
);
2592 if (vectype
== NULL_TREE
)
2595 /* If the target can handle vectorized division or modulo natively,
2596 don't attempt to optimize this. */
2597 optab
= optab_for_tree_code (rhs_code
, vectype
, optab_default
);
2598 if (optab
!= unknown_optab
)
2600 machine_mode vec_mode
= TYPE_MODE (vectype
);
2601 int icode
= (int) optab_handler (optab
, vec_mode
);
2602 if (icode
!= CODE_FOR_nothing
)
2606 prec
= TYPE_PRECISION (itype
);
2607 if (integer_pow2p (oprnd1
))
2609 if (TYPE_UNSIGNED (itype
) || tree_int_cst_sgn (oprnd1
) != 1)
2612 /* Pattern detected. */
2613 if (dump_enabled_p ())
2614 dump_printf_loc (MSG_NOTE
, vect_location
,
2615 "vect_recog_divmod_pattern: detected:\n");
2617 cond
= build2 (LT_EXPR
, boolean_type_node
, oprnd0
,
2618 build_int_cst (itype
, 0));
2619 if (rhs_code
== TRUNC_DIV_EXPR
)
2621 tree var
= vect_recog_temp_ssa_var (itype
, NULL
);
2624 = gimple_build_assign (var
, COND_EXPR
, cond
,
2625 fold_build2 (MINUS_EXPR
, itype
, oprnd1
,
2626 build_int_cst (itype
, 1)),
2627 build_int_cst (itype
, 0));
2628 new_pattern_def_seq (stmt_vinfo
, def_stmt
);
2629 var
= vect_recog_temp_ssa_var (itype
, NULL
);
2631 = gimple_build_assign (var
, PLUS_EXPR
, oprnd0
,
2632 gimple_assign_lhs (def_stmt
));
2633 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2635 shift
= build_int_cst (itype
, tree_log2 (oprnd1
));
2637 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
2638 RSHIFT_EXPR
, var
, shift
);
2643 STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo
) = NULL
;
2644 if (compare_tree_int (oprnd1
, 2) == 0)
2646 signmask
= vect_recog_temp_ssa_var (itype
, NULL
);
2647 def_stmt
= gimple_build_assign (signmask
, COND_EXPR
, cond
,
2648 build_int_cst (itype
, 1),
2649 build_int_cst (itype
, 0));
2650 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2655 = build_nonstandard_integer_type (prec
, 1);
2656 tree vecutype
= get_vectype_for_scalar_type (utype
);
2658 = build_int_cst (utype
, GET_MODE_BITSIZE (TYPE_MODE (itype
))
2659 - tree_log2 (oprnd1
));
2660 tree var
= vect_recog_temp_ssa_var (utype
, NULL
);
2662 def_stmt
= gimple_build_assign (var
, COND_EXPR
, cond
,
2663 build_int_cst (utype
, -1),
2664 build_int_cst (utype
, 0));
2665 def_stmt_vinfo
= new_stmt_vec_info (def_stmt
, vinfo
);
2666 set_vinfo_for_stmt (def_stmt
, def_stmt_vinfo
);
2667 STMT_VINFO_VECTYPE (def_stmt_vinfo
) = vecutype
;
2668 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2669 var
= vect_recog_temp_ssa_var (utype
, NULL
);
2670 def_stmt
= gimple_build_assign (var
, RSHIFT_EXPR
,
2671 gimple_assign_lhs (def_stmt
),
2673 def_stmt_vinfo
= new_stmt_vec_info (def_stmt
, vinfo
);
2674 set_vinfo_for_stmt (def_stmt
, def_stmt_vinfo
);
2675 STMT_VINFO_VECTYPE (def_stmt_vinfo
) = vecutype
;
2676 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2677 signmask
= vect_recog_temp_ssa_var (itype
, NULL
);
2679 = gimple_build_assign (signmask
, NOP_EXPR
, var
);
2680 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2683 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
2684 PLUS_EXPR
, oprnd0
, signmask
);
2685 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2687 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
2688 BIT_AND_EXPR
, gimple_assign_lhs (def_stmt
),
2689 fold_build2 (MINUS_EXPR
, itype
, oprnd1
,
2690 build_int_cst (itype
, 1)));
2691 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2694 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
2695 MINUS_EXPR
, gimple_assign_lhs (def_stmt
),
2699 if (dump_enabled_p ())
2700 dump_gimple_stmt_loc (MSG_NOTE
, vect_location
, TDF_SLIM
, pattern_stmt
,
2703 stmts
->safe_push (last_stmt
);
2706 *type_out
= vectype
;
2707 return pattern_stmt
;
2710 if (prec
> HOST_BITS_PER_WIDE_INT
2711 || integer_zerop (oprnd1
))
2714 if (!can_mult_highpart_p (TYPE_MODE (vectype
), TYPE_UNSIGNED (itype
)))
2717 STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo
) = NULL
;
2719 if (TYPE_UNSIGNED (itype
))
2721 unsigned HOST_WIDE_INT mh
, ml
;
2722 int pre_shift
, post_shift
;
2723 unsigned HOST_WIDE_INT d
= (TREE_INT_CST_LOW (oprnd1
)
2724 & GET_MODE_MASK (TYPE_MODE (itype
)));
2725 tree t1
, t2
, t3
, t4
;
2727 if (d
>= ((unsigned HOST_WIDE_INT
) 1 << (prec
- 1)))
2728 /* FIXME: Can transform this into oprnd0 >= oprnd1 ? 1 : 0. */
2731 /* Find a suitable multiplier and right shift count
2732 instead of multiplying with D. */
2733 mh
= choose_multiplier (d
, prec
, prec
, &ml
, &post_shift
, &dummy_int
);
2735 /* If the suggested multiplier is more than SIZE bits, we can do better
2736 for even divisors, using an initial right shift. */
2737 if (mh
!= 0 && (d
& 1) == 0)
2739 pre_shift
= floor_log2 (d
& -d
);
2740 mh
= choose_multiplier (d
>> pre_shift
, prec
, prec
- pre_shift
,
2741 &ml
, &post_shift
, &dummy_int
);
2749 if (post_shift
- 1 >= prec
)
2752 /* t1 = oprnd0 h* ml;
2756 q = t4 >> (post_shift - 1); */
2757 t1
= vect_recog_temp_ssa_var (itype
, NULL
);
2758 def_stmt
= gimple_build_assign (t1
, MULT_HIGHPART_EXPR
, oprnd0
,
2759 build_int_cst (itype
, ml
));
2760 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2762 t2
= vect_recog_temp_ssa_var (itype
, NULL
);
2764 = gimple_build_assign (t2
, MINUS_EXPR
, oprnd0
, t1
);
2765 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2767 t3
= vect_recog_temp_ssa_var (itype
, NULL
);
2769 = gimple_build_assign (t3
, RSHIFT_EXPR
, t2
, integer_one_node
);
2770 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2772 t4
= vect_recog_temp_ssa_var (itype
, NULL
);
2774 = gimple_build_assign (t4
, PLUS_EXPR
, t1
, t3
);
2776 if (post_shift
!= 1)
2778 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2780 q
= vect_recog_temp_ssa_var (itype
, NULL
);
2782 = gimple_build_assign (q
, RSHIFT_EXPR
, t4
,
2783 build_int_cst (itype
, post_shift
- 1));
2788 pattern_stmt
= def_stmt
;
2793 if (pre_shift
>= prec
|| post_shift
>= prec
)
2796 /* t1 = oprnd0 >> pre_shift;
2798 q = t2 >> post_shift; */
2801 t1
= vect_recog_temp_ssa_var (itype
, NULL
);
2803 = gimple_build_assign (t1
, RSHIFT_EXPR
, oprnd0
,
2804 build_int_cst (NULL
, pre_shift
));
2805 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2810 t2
= vect_recog_temp_ssa_var (itype
, NULL
);
2811 def_stmt
= gimple_build_assign (t2
, MULT_HIGHPART_EXPR
, t1
,
2812 build_int_cst (itype
, ml
));
2816 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2818 q
= vect_recog_temp_ssa_var (itype
, NULL
);
2820 = gimple_build_assign (q
, RSHIFT_EXPR
, t2
,
2821 build_int_cst (itype
, post_shift
));
2826 pattern_stmt
= def_stmt
;
2831 unsigned HOST_WIDE_INT ml
;
2833 HOST_WIDE_INT d
= TREE_INT_CST_LOW (oprnd1
);
2834 unsigned HOST_WIDE_INT abs_d
;
2836 tree t1
, t2
, t3
, t4
;
2838 /* Give up for -1. */
2842 /* Since d might be INT_MIN, we have to cast to
2843 unsigned HOST_WIDE_INT before negating to avoid
2844 undefined signed overflow. */
2846 ? (unsigned HOST_WIDE_INT
) d
2847 : - (unsigned HOST_WIDE_INT
) d
);
2849 /* n rem d = n rem -d */
2850 if (rhs_code
== TRUNC_MOD_EXPR
&& d
< 0)
2853 oprnd1
= build_int_cst (itype
, abs_d
);
2855 else if (HOST_BITS_PER_WIDE_INT
>= prec
2856 && abs_d
== (unsigned HOST_WIDE_INT
) 1 << (prec
- 1))
2857 /* This case is not handled correctly below. */
2860 choose_multiplier (abs_d
, prec
, prec
- 1, &ml
, &post_shift
, &dummy_int
);
2861 if (ml
>= (unsigned HOST_WIDE_INT
) 1 << (prec
- 1))
2864 ml
|= (~(unsigned HOST_WIDE_INT
) 0) << (prec
- 1);
2866 if (post_shift
>= prec
)
2869 /* t1 = oprnd0 h* ml; */
2870 t1
= vect_recog_temp_ssa_var (itype
, NULL
);
2871 def_stmt
= gimple_build_assign (t1
, MULT_HIGHPART_EXPR
, oprnd0
,
2872 build_int_cst (itype
, ml
));
2876 /* t2 = t1 + oprnd0; */
2877 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2878 t2
= vect_recog_temp_ssa_var (itype
, NULL
);
2879 def_stmt
= gimple_build_assign (t2
, PLUS_EXPR
, t1
, oprnd0
);
2886 /* t3 = t2 >> post_shift; */
2887 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2888 t3
= vect_recog_temp_ssa_var (itype
, NULL
);
2889 def_stmt
= gimple_build_assign (t3
, RSHIFT_EXPR
, t2
,
2890 build_int_cst (itype
, post_shift
));
2895 wide_int oprnd0_min
, oprnd0_max
;
2897 if (get_range_info (oprnd0
, &oprnd0_min
, &oprnd0_max
) == VR_RANGE
)
2899 if (!wi::neg_p (oprnd0_min
, TYPE_SIGN (itype
)))
2901 else if (wi::neg_p (oprnd0_max
, TYPE_SIGN (itype
)))
2905 if (msb
== 0 && d
>= 0)
2909 pattern_stmt
= def_stmt
;
2913 /* t4 = oprnd0 >> (prec - 1);
2914 or if we know from VRP that oprnd0 >= 0
2916 or if we know from VRP that oprnd0 < 0
2918 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2919 t4
= vect_recog_temp_ssa_var (itype
, NULL
);
2921 def_stmt
= gimple_build_assign (t4
, INTEGER_CST
,
2922 build_int_cst (itype
, msb
));
2924 def_stmt
= gimple_build_assign (t4
, RSHIFT_EXPR
, oprnd0
,
2925 build_int_cst (itype
, prec
- 1));
2926 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2928 /* q = t3 - t4; or q = t4 - t3; */
2929 q
= vect_recog_temp_ssa_var (itype
, NULL
);
2930 pattern_stmt
= gimple_build_assign (q
, MINUS_EXPR
, d
< 0 ? t4
: t3
,
2935 if (rhs_code
== TRUNC_MOD_EXPR
)
2939 /* We divided. Now finish by:
2942 append_pattern_def_seq (stmt_vinfo
, pattern_stmt
);
2944 t1
= vect_recog_temp_ssa_var (itype
, NULL
);
2945 def_stmt
= gimple_build_assign (t1
, MULT_EXPR
, q
, oprnd1
);
2946 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
2948 r
= vect_recog_temp_ssa_var (itype
, NULL
);
2949 pattern_stmt
= gimple_build_assign (r
, MINUS_EXPR
, oprnd0
, t1
);
2952 /* Pattern detected. */
2953 if (dump_enabled_p ())
2955 dump_printf_loc (MSG_NOTE
, vect_location
,
2956 "vect_recog_divmod_pattern: detected: ");
2957 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
2960 stmts
->safe_push (last_stmt
);
2963 *type_out
= vectype
;
2964 return pattern_stmt
;
2967 /* Function vect_recog_mixed_size_cond_pattern
2969 Try to find the following pattern:
2974 S1 a_T = x_t CMP y_t ? b_T : c_T;
2976 where type 'TYPE' is an integral type which has different size
2977 from 'type'. b_T and c_T are either constants (and if 'TYPE' is wider
2978 than 'type', the constants need to fit into an integer type
2979 with the same width as 'type') or results of conversion from 'type'.
2983 * LAST_STMT: A stmt from which the pattern search begins.
2987 * TYPE_IN: The type of the input arguments to the pattern.
2989 * TYPE_OUT: The type of the output of this pattern.
2991 * Return value: A new stmt that will be used to replace the pattern.
2992 Additionally a def_stmt is added.
2994 a_it = x_t CMP y_t ? b_it : c_it;
2995 a_T = (TYPE) a_it; */
2998 vect_recog_mixed_size_cond_pattern (vec
<gimple
*> *stmts
, tree
*type_in
,
3001 gimple
*last_stmt
= (*stmts
)[0];
3002 tree cond_expr
, then_clause
, else_clause
;
3003 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
), def_stmt_info
;
3004 tree type
, vectype
, comp_vectype
, itype
= NULL_TREE
, vecitype
;
3005 gimple
*pattern_stmt
, *def_stmt
;
3006 vec_info
*vinfo
= stmt_vinfo
->vinfo
;
3007 tree orig_type0
= NULL_TREE
, orig_type1
= NULL_TREE
;
3008 gimple
*def_stmt0
= NULL
, *def_stmt1
= NULL
;
3010 tree comp_scalar_type
;
3012 if (!is_gimple_assign (last_stmt
)
3013 || gimple_assign_rhs_code (last_stmt
) != COND_EXPR
3014 || STMT_VINFO_DEF_TYPE (stmt_vinfo
) != vect_internal_def
)
3017 cond_expr
= gimple_assign_rhs1 (last_stmt
);
3018 then_clause
= gimple_assign_rhs2 (last_stmt
);
3019 else_clause
= gimple_assign_rhs3 (last_stmt
);
3021 if (!COMPARISON_CLASS_P (cond_expr
))
3024 comp_scalar_type
= TREE_TYPE (TREE_OPERAND (cond_expr
, 0));
3025 comp_vectype
= get_vectype_for_scalar_type (comp_scalar_type
);
3026 if (comp_vectype
== NULL_TREE
)
3029 type
= gimple_expr_type (last_stmt
);
3030 if (types_compatible_p (type
, comp_scalar_type
)
3031 || ((TREE_CODE (then_clause
) != INTEGER_CST
3032 || TREE_CODE (else_clause
) != INTEGER_CST
)
3033 && !INTEGRAL_TYPE_P (comp_scalar_type
))
3034 || !INTEGRAL_TYPE_P (type
))
3037 if ((TREE_CODE (then_clause
) != INTEGER_CST
3038 && !type_conversion_p (then_clause
, last_stmt
, false, &orig_type0
,
3039 &def_stmt0
, &promotion
))
3040 || (TREE_CODE (else_clause
) != INTEGER_CST
3041 && !type_conversion_p (else_clause
, last_stmt
, false, &orig_type1
,
3042 &def_stmt1
, &promotion
)))
3045 if (orig_type0
&& orig_type1
3046 && !types_compatible_p (orig_type0
, orig_type1
))
3051 if (!types_compatible_p (orig_type0
, comp_scalar_type
))
3053 then_clause
= gimple_assign_rhs1 (def_stmt0
);
3059 if (!types_compatible_p (orig_type1
, comp_scalar_type
))
3061 else_clause
= gimple_assign_rhs1 (def_stmt1
);
3066 HOST_WIDE_INT cmp_mode_size
3067 = GET_MODE_UNIT_BITSIZE (TYPE_MODE (comp_vectype
));
3069 if (GET_MODE_BITSIZE (TYPE_MODE (type
)) == cmp_mode_size
)
3072 vectype
= get_vectype_for_scalar_type (type
);
3073 if (vectype
== NULL_TREE
)
3076 if (expand_vec_cond_expr_p (vectype
, comp_vectype
))
3079 if (itype
== NULL_TREE
)
3080 itype
= build_nonstandard_integer_type (cmp_mode_size
,
3081 TYPE_UNSIGNED (type
));
3083 if (itype
== NULL_TREE
3084 || GET_MODE_BITSIZE (TYPE_MODE (itype
)) != cmp_mode_size
)
3087 vecitype
= get_vectype_for_scalar_type (itype
);
3088 if (vecitype
== NULL_TREE
)
3091 if (!expand_vec_cond_expr_p (vecitype
, comp_vectype
))
3094 if (GET_MODE_BITSIZE (TYPE_MODE (type
)) > cmp_mode_size
)
3096 if ((TREE_CODE (then_clause
) == INTEGER_CST
3097 && !int_fits_type_p (then_clause
, itype
))
3098 || (TREE_CODE (else_clause
) == INTEGER_CST
3099 && !int_fits_type_p (else_clause
, itype
)))
3103 def_stmt
= gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
3104 COND_EXPR
, unshare_expr (cond_expr
),
3105 fold_convert (itype
, then_clause
),
3106 fold_convert (itype
, else_clause
));
3107 pattern_stmt
= gimple_build_assign (vect_recog_temp_ssa_var (type
, NULL
),
3108 NOP_EXPR
, gimple_assign_lhs (def_stmt
));
3110 new_pattern_def_seq (stmt_vinfo
, def_stmt
);
3111 def_stmt_info
= new_stmt_vec_info (def_stmt
, vinfo
);
3112 set_vinfo_for_stmt (def_stmt
, def_stmt_info
);
3113 STMT_VINFO_VECTYPE (def_stmt_info
) = vecitype
;
3114 *type_in
= vecitype
;
3115 *type_out
= vectype
;
3117 if (dump_enabled_p ())
3118 dump_printf_loc (MSG_NOTE
, vect_location
,
3119 "vect_recog_mixed_size_cond_pattern: detected:\n");
3121 return pattern_stmt
;
3125 /* Helper function of vect_recog_bool_pattern. Called recursively, return
3126 true if bool VAR can and should be optimized that way. Assume it shouldn't
3127 in case it's a result of a comparison which can be directly vectorized into
3128 a vector comparison. Fills in STMTS with all stmts visited during the
3132 check_bool_pattern (tree var
, vec_info
*vinfo
, hash_set
<gimple
*> &stmts
)
3135 enum vect_def_type dt
;
3137 enum tree_code rhs_code
;
3139 if (!vect_is_simple_use (var
, vinfo
, &def_stmt
, &dt
))
3142 if (dt
!= vect_internal_def
)
3145 if (!is_gimple_assign (def_stmt
))
3148 if (stmts
.contains (def_stmt
))
3151 rhs1
= gimple_assign_rhs1 (def_stmt
);
3152 rhs_code
= gimple_assign_rhs_code (def_stmt
);
3156 if (! check_bool_pattern (rhs1
, vinfo
, stmts
))
3161 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
3162 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
3163 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
3165 if (! check_bool_pattern (rhs1
, vinfo
, stmts
))
3170 if (! check_bool_pattern (rhs1
, vinfo
, stmts
))
3177 if (! check_bool_pattern (rhs1
, vinfo
, stmts
)
3178 || ! check_bool_pattern (gimple_assign_rhs2 (def_stmt
), vinfo
, stmts
))
3183 if (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
)
3185 tree vecitype
, comp_vectype
;
3187 /* If the comparison can throw, then is_gimple_condexpr will be
3188 false and we can't make a COND_EXPR/VEC_COND_EXPR out of it. */
3189 if (stmt_could_throw_p (def_stmt
))
3192 comp_vectype
= get_vectype_for_scalar_type (TREE_TYPE (rhs1
));
3193 if (comp_vectype
== NULL_TREE
)
3196 tree mask_type
= get_mask_type_for_scalar_type (TREE_TYPE (rhs1
));
3198 && expand_vec_cmp_expr_p (comp_vectype
, mask_type
))
3201 if (TREE_CODE (TREE_TYPE (rhs1
)) != INTEGER_TYPE
)
3203 machine_mode mode
= TYPE_MODE (TREE_TYPE (rhs1
));
3205 = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode
), 1);
3206 vecitype
= get_vectype_for_scalar_type (itype
);
3207 if (vecitype
== NULL_TREE
)
3211 vecitype
= comp_vectype
;
3212 if (! expand_vec_cond_expr_p (vecitype
, comp_vectype
))
3220 bool res
= stmts
.add (def_stmt
);
3221 /* We can't end up recursing when just visiting SSA defs but not PHIs. */
3228 /* Helper function of adjust_bool_pattern. Add a cast to TYPE to a previous
3229 stmt (SSA_NAME_DEF_STMT of VAR) adding a cast to STMT_INFOs
3230 pattern sequence. */
3233 adjust_bool_pattern_cast (tree type
, tree var
, stmt_vec_info stmt_info
)
3235 gimple
*cast_stmt
= gimple_build_assign (vect_recog_temp_ssa_var (type
, NULL
),
3237 stmt_vec_info patt_vinfo
= new_stmt_vec_info (cast_stmt
, stmt_info
->vinfo
);
3238 set_vinfo_for_stmt (cast_stmt
, patt_vinfo
);
3239 STMT_VINFO_VECTYPE (patt_vinfo
) = get_vectype_for_scalar_type (type
);
3240 append_pattern_def_seq (stmt_info
, cast_stmt
);
3241 return gimple_assign_lhs (cast_stmt
);
3244 /* Helper function of vect_recog_bool_pattern. Do the actual transformations.
3245 VAR is an SSA_NAME that should be transformed from bool to a wider integer
3246 type, OUT_TYPE is the desired final integer type of the whole pattern.
3247 STMT_INFO is the info of the pattern root and is where pattern stmts should
3248 be associated with. DEFS is a map of pattern defs. */
3251 adjust_bool_pattern (tree var
, tree out_type
,
3252 stmt_vec_info stmt_info
, hash_map
<tree
, tree
> &defs
)
3254 gimple
*stmt
= SSA_NAME_DEF_STMT (var
);
3255 enum tree_code rhs_code
, def_rhs_code
;
3256 tree itype
, cond_expr
, rhs1
, rhs2
, irhs1
, irhs2
;
3258 gimple
*pattern_stmt
, *def_stmt
;
3259 tree trueval
= NULL_TREE
;
3261 rhs1
= gimple_assign_rhs1 (stmt
);
3262 rhs2
= gimple_assign_rhs2 (stmt
);
3263 rhs_code
= gimple_assign_rhs_code (stmt
);
3264 loc
= gimple_location (stmt
);
3269 irhs1
= *defs
.get (rhs1
);
3270 itype
= TREE_TYPE (irhs1
);
3272 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
3277 irhs1
= *defs
.get (rhs1
);
3278 itype
= TREE_TYPE (irhs1
);
3280 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
3281 BIT_XOR_EXPR
, irhs1
, build_int_cst (itype
, 1));
3285 /* Try to optimize x = y & (a < b ? 1 : 0); into
3286 x = (a < b ? y : 0);
3292 S1 a_b = x1 CMP1 y1;
3293 S2 b_b = x2 CMP2 y2;
3295 S4 d_T = (TYPE) c_b;
3297 we would normally emit:
3299 S1' a_T = x1 CMP1 y1 ? 1 : 0;
3300 S2' b_T = x2 CMP2 y2 ? 1 : 0;
3301 S3' c_T = a_T & b_T;
3304 but we can save one stmt by using the
3305 result of one of the COND_EXPRs in the other COND_EXPR and leave
3306 BIT_AND_EXPR stmt out:
3308 S1' a_T = x1 CMP1 y1 ? 1 : 0;
3309 S3' c_T = x2 CMP2 y2 ? a_T : 0;
3312 At least when VEC_COND_EXPR is implemented using masks
3313 cond ? 1 : 0 is as expensive as cond ? var : 0, in both cases it
3314 computes the comparison masks and ands it, in one case with
3315 all ones vector, in the other case with a vector register.
3316 Don't do this for BIT_IOR_EXPR, because cond ? 1 : var; is
3317 often more expensive. */
3318 def_stmt
= SSA_NAME_DEF_STMT (rhs2
);
3319 def_rhs_code
= gimple_assign_rhs_code (def_stmt
);
3320 if (TREE_CODE_CLASS (def_rhs_code
) == tcc_comparison
)
3322 irhs1
= *defs
.get (rhs1
);
3323 tree def_rhs1
= gimple_assign_rhs1 (def_stmt
);
3324 if (TYPE_PRECISION (TREE_TYPE (irhs1
))
3325 == GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (def_rhs1
))))
3327 rhs_code
= def_rhs_code
;
3329 rhs2
= gimple_assign_rhs2 (def_stmt
);
3334 irhs2
= *defs
.get (rhs2
);
3337 def_stmt
= SSA_NAME_DEF_STMT (rhs1
);
3338 def_rhs_code
= gimple_assign_rhs_code (def_stmt
);
3339 if (TREE_CODE_CLASS (def_rhs_code
) == tcc_comparison
)
3341 irhs2
= *defs
.get (rhs2
);
3342 tree def_rhs1
= gimple_assign_rhs1 (def_stmt
);
3343 if (TYPE_PRECISION (TREE_TYPE (irhs2
))
3344 == GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (def_rhs1
))))
3346 rhs_code
= def_rhs_code
;
3348 rhs2
= gimple_assign_rhs2 (def_stmt
);
3353 irhs1
= *defs
.get (rhs1
);
3359 irhs1
= *defs
.get (rhs1
);
3360 irhs2
= *defs
.get (rhs2
);
3362 if (TYPE_PRECISION (TREE_TYPE (irhs1
))
3363 != TYPE_PRECISION (TREE_TYPE (irhs2
)))
3365 int prec1
= TYPE_PRECISION (TREE_TYPE (irhs1
));
3366 int prec2
= TYPE_PRECISION (TREE_TYPE (irhs2
));
3367 int out_prec
= TYPE_PRECISION (out_type
);
3368 if (absu_hwi (out_prec
- prec1
) < absu_hwi (out_prec
- prec2
))
3369 irhs2
= adjust_bool_pattern_cast (TREE_TYPE (irhs1
), irhs2
,
3371 else if (absu_hwi (out_prec
- prec1
) > absu_hwi (out_prec
- prec2
))
3372 irhs1
= adjust_bool_pattern_cast (TREE_TYPE (irhs2
), irhs1
,
3376 irhs1
= adjust_bool_pattern_cast (out_type
, irhs1
, stmt_info
);
3377 irhs2
= adjust_bool_pattern_cast (out_type
, irhs2
, stmt_info
);
3380 itype
= TREE_TYPE (irhs1
);
3382 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
3383 rhs_code
, irhs1
, irhs2
);
3388 gcc_assert (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
);
3389 if (TREE_CODE (TREE_TYPE (rhs1
)) != INTEGER_TYPE
3390 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
))
3391 || (TYPE_PRECISION (TREE_TYPE (rhs1
))
3392 != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1
)))))
3394 machine_mode mode
= TYPE_MODE (TREE_TYPE (rhs1
));
3396 = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode
), 1);
3399 itype
= TREE_TYPE (rhs1
);
3400 cond_expr
= build2_loc (loc
, rhs_code
, itype
, rhs1
, rhs2
);
3401 if (trueval
== NULL_TREE
)
3402 trueval
= build_int_cst (itype
, 1);
3404 gcc_checking_assert (useless_type_conversion_p (itype
,
3405 TREE_TYPE (trueval
)));
3407 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
3408 COND_EXPR
, cond_expr
, trueval
,
3409 build_int_cst (itype
, 0));
3413 gimple_set_location (pattern_stmt
, loc
);
3414 /* ??? Why does vect_mark_pattern_stmts set the vector type on all
3415 pattern def seq stmts instead of just letting auto-detection do
3417 stmt_vec_info patt_vinfo
= new_stmt_vec_info (pattern_stmt
, stmt_info
->vinfo
);
3418 set_vinfo_for_stmt (pattern_stmt
, patt_vinfo
);
3419 STMT_VINFO_VECTYPE (patt_vinfo
) = get_vectype_for_scalar_type (itype
);
3420 append_pattern_def_seq (stmt_info
, pattern_stmt
);
3421 defs
.put (var
, gimple_assign_lhs (pattern_stmt
));
3424 /* Comparison function to qsort a vector of gimple stmts after UID. */
3427 sort_after_uid (const void *p1
, const void *p2
)
3429 const gimple
*stmt1
= *(const gimple
* const *)p1
;
3430 const gimple
*stmt2
= *(const gimple
* const *)p2
;
3431 return gimple_uid (stmt1
) - gimple_uid (stmt2
);
3434 /* Create pattern stmts for all stmts participating in the bool pattern
3435 specified by BOOL_STMT_SET and its root STMT with the desired type
3436 OUT_TYPE. Return the def of the pattern root. */
3439 adjust_bool_stmts (hash_set
<gimple
*> &bool_stmt_set
,
3440 tree out_type
, gimple
*stmt
)
3442 /* Gather original stmts in the bool pattern in their order of appearance
3444 auto_vec
<gimple
*> bool_stmts (bool_stmt_set
.elements ());
3445 for (hash_set
<gimple
*>::iterator i
= bool_stmt_set
.begin ();
3446 i
!= bool_stmt_set
.end (); ++i
)
3447 bool_stmts
.quick_push (*i
);
3448 bool_stmts
.qsort (sort_after_uid
);
3450 /* Now process them in that order, producing pattern stmts. */
3451 hash_map
<tree
, tree
> defs
;
3452 for (unsigned i
= 0; i
< bool_stmts
.length (); ++i
)
3453 adjust_bool_pattern (gimple_assign_lhs (bool_stmts
[i
]),
3454 out_type
, vinfo_for_stmt (stmt
), defs
);
3456 /* Pop the last pattern seq stmt and install it as pattern root for STMT. */
3457 gimple
*pattern_stmt
3458 = gimple_seq_last_stmt (STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (stmt
)));
3459 return gimple_assign_lhs (pattern_stmt
);
3462 /* Return the proper type for converting bool VAR into
3463 an integer value or NULL_TREE if no such type exists.
3464 The type is chosen so that converted value has the
3465 same number of elements as VAR's vector type. */
3468 search_type_for_mask (tree var
, vec_info
*vinfo
)
3471 enum vect_def_type dt
;
3473 enum tree_code rhs_code
;
3474 tree res
= NULL_TREE
, res2
;
3476 if (TREE_CODE (var
) != SSA_NAME
)
3479 if ((TYPE_PRECISION (TREE_TYPE (var
)) != 1
3480 || !TYPE_UNSIGNED (TREE_TYPE (var
)))
3481 && TREE_CODE (TREE_TYPE (var
)) != BOOLEAN_TYPE
)
3484 if (!vect_is_simple_use (var
, vinfo
, &def_stmt
, &dt
))
3487 if (dt
!= vect_internal_def
)
3490 if (!is_gimple_assign (def_stmt
))
3493 rhs_code
= gimple_assign_rhs_code (def_stmt
);
3494 rhs1
= gimple_assign_rhs1 (def_stmt
);
3501 res
= search_type_for_mask (rhs1
, vinfo
);
3507 res
= search_type_for_mask (rhs1
, vinfo
);
3508 res2
= search_type_for_mask (gimple_assign_rhs2 (def_stmt
), vinfo
);
3509 if (!res
|| (res2
&& TYPE_PRECISION (res
) > TYPE_PRECISION (res2
)))
3514 if (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
)
3516 tree comp_vectype
, mask_type
;
3518 if (TREE_CODE (TREE_TYPE (rhs1
)) == BOOLEAN_TYPE
)
3520 res
= search_type_for_mask (rhs1
, vinfo
);
3521 res2
= search_type_for_mask (gimple_assign_rhs2 (def_stmt
), vinfo
);
3522 if (!res
|| (res2
&& TYPE_PRECISION (res
) > TYPE_PRECISION (res2
)))
3527 comp_vectype
= get_vectype_for_scalar_type (TREE_TYPE (rhs1
));
3528 if (comp_vectype
== NULL_TREE
)
3531 mask_type
= get_mask_type_for_scalar_type (TREE_TYPE (rhs1
));
3533 || !expand_vec_cmp_expr_p (comp_vectype
, mask_type
))
3536 if (TREE_CODE (TREE_TYPE (rhs1
)) != INTEGER_TYPE
3537 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
3539 machine_mode mode
= TYPE_MODE (TREE_TYPE (rhs1
));
3540 res
= build_nonstandard_integer_type (GET_MODE_BITSIZE (mode
), 1);
3543 res
= TREE_TYPE (rhs1
);
3551 /* Function vect_recog_bool_pattern
3553 Try to find pattern like following:
3555 bool a_b, b_b, c_b, d_b, e_b;
3558 S1 a_b = x1 CMP1 y1;
3559 S2 b_b = x2 CMP2 y2;
3561 S4 d_b = x3 CMP3 y3;
3563 S6 f_T = (TYPE) e_b;
3565 where type 'TYPE' is an integral type. Or a similar pattern
3568 S6 f_Y = e_b ? r_Y : s_Y;
3570 as results from if-conversion of a complex condition.
3574 * LAST_STMT: A stmt at the end from which the pattern
3575 search begins, i.e. cast of a bool to
3580 * TYPE_IN: The type of the input arguments to the pattern.
3582 * TYPE_OUT: The type of the output of this pattern.
3584 * Return value: A new stmt that will be used to replace the pattern.
3586 Assuming size of TYPE is the same as size of all comparisons
3587 (otherwise some casts would be added where needed), the above
3588 sequence we create related pattern stmts:
3589 S1' a_T = x1 CMP1 y1 ? 1 : 0;
3590 S3' c_T = x2 CMP2 y2 ? a_T : 0;
3591 S4' d_T = x3 CMP3 y3 ? 1 : 0;
3592 S5' e_T = c_T | d_T;
3595 Instead of the above S3' we could emit:
3596 S2' b_T = x2 CMP2 y2 ? 1 : 0;
3597 S3' c_T = a_T | b_T;
3598 but the above is more efficient. */
3601 vect_recog_bool_pattern (vec
<gimple
*> *stmts
, tree
*type_in
,
3604 gimple
*last_stmt
= stmts
->pop ();
3605 enum tree_code rhs_code
;
3606 tree var
, lhs
, rhs
, vectype
;
3607 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
3608 stmt_vec_info new_stmt_info
;
3609 vec_info
*vinfo
= stmt_vinfo
->vinfo
;
3610 gimple
*pattern_stmt
;
3612 if (!is_gimple_assign (last_stmt
))
3615 var
= gimple_assign_rhs1 (last_stmt
);
3616 lhs
= gimple_assign_lhs (last_stmt
);
3618 if ((TYPE_PRECISION (TREE_TYPE (var
)) != 1
3619 || !TYPE_UNSIGNED (TREE_TYPE (var
)))
3620 && TREE_CODE (TREE_TYPE (var
)) != BOOLEAN_TYPE
)
3623 hash_set
<gimple
*> bool_stmts
;
3625 rhs_code
= gimple_assign_rhs_code (last_stmt
);
3626 if (CONVERT_EXPR_CODE_P (rhs_code
))
3628 if (TREE_CODE (TREE_TYPE (lhs
)) != INTEGER_TYPE
3629 || TYPE_PRECISION (TREE_TYPE (lhs
)) == 1)
3631 vectype
= get_vectype_for_scalar_type (TREE_TYPE (lhs
));
3632 if (vectype
== NULL_TREE
)
3635 if (check_bool_pattern (var
, vinfo
, bool_stmts
))
3637 rhs
= adjust_bool_stmts (bool_stmts
, TREE_TYPE (lhs
), last_stmt
);
3638 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3639 if (useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
3640 pattern_stmt
= gimple_build_assign (lhs
, SSA_NAME
, rhs
);
3643 = gimple_build_assign (lhs
, NOP_EXPR
, rhs
);
3647 tree type
= search_type_for_mask (var
, vinfo
);
3648 tree cst0
, cst1
, tmp
;
3653 /* We may directly use cond with narrowed type to avoid
3654 multiple cond exprs with following result packing and
3655 perform single cond with packed mask instead. In case
3656 of widening we better make cond first and then extract
3658 if (TYPE_MODE (type
) == TYPE_MODE (TREE_TYPE (lhs
)))
3659 type
= TREE_TYPE (lhs
);
3661 cst0
= build_int_cst (type
, 0);
3662 cst1
= build_int_cst (type
, 1);
3663 tmp
= vect_recog_temp_ssa_var (type
, NULL
);
3664 pattern_stmt
= gimple_build_assign (tmp
, COND_EXPR
, var
, cst1
, cst0
);
3666 if (!useless_type_conversion_p (type
, TREE_TYPE (lhs
)))
3668 tree new_vectype
= get_vectype_for_scalar_type (type
);
3669 new_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
3670 set_vinfo_for_stmt (pattern_stmt
, new_stmt_info
);
3671 STMT_VINFO_VECTYPE (new_stmt_info
) = new_vectype
;
3672 new_pattern_def_seq (stmt_vinfo
, pattern_stmt
);
3674 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3675 pattern_stmt
= gimple_build_assign (lhs
, CONVERT_EXPR
, tmp
);
3679 *type_out
= vectype
;
3681 stmts
->safe_push (last_stmt
);
3682 if (dump_enabled_p ())
3683 dump_printf_loc (MSG_NOTE
, vect_location
,
3684 "vect_recog_bool_pattern: detected:\n");
3686 return pattern_stmt
;
3688 else if (rhs_code
== COND_EXPR
3689 && TREE_CODE (var
) == SSA_NAME
)
3691 vectype
= get_vectype_for_scalar_type (TREE_TYPE (lhs
));
3692 if (vectype
== NULL_TREE
)
3695 /* Build a scalar type for the boolean result that when
3696 vectorized matches the vector type of the result in
3697 size and number of elements. */
3699 = wi::udiv_trunc (TYPE_SIZE (vectype
),
3700 TYPE_VECTOR_SUBPARTS (vectype
)).to_uhwi ();
3702 = build_nonstandard_integer_type (prec
,
3703 TYPE_UNSIGNED (TREE_TYPE (var
)));
3704 if (get_vectype_for_scalar_type (type
) == NULL_TREE
)
3707 if (!check_bool_pattern (var
, vinfo
, bool_stmts
))
3710 rhs
= adjust_bool_stmts (bool_stmts
, type
, last_stmt
);
3712 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3714 = gimple_build_assign (lhs
, COND_EXPR
,
3715 build2 (NE_EXPR
, boolean_type_node
,
3716 rhs
, build_int_cst (type
, 0)),
3717 gimple_assign_rhs2 (last_stmt
),
3718 gimple_assign_rhs3 (last_stmt
));
3719 *type_out
= vectype
;
3721 stmts
->safe_push (last_stmt
);
3722 if (dump_enabled_p ())
3723 dump_printf_loc (MSG_NOTE
, vect_location
,
3724 "vect_recog_bool_pattern: detected:\n");
3726 return pattern_stmt
;
3728 else if (rhs_code
== SSA_NAME
3729 && STMT_VINFO_DATA_REF (stmt_vinfo
))
3731 stmt_vec_info pattern_stmt_info
;
3732 vectype
= STMT_VINFO_VECTYPE (stmt_vinfo
);
3733 gcc_assert (vectype
!= NULL_TREE
);
3734 if (!VECTOR_MODE_P (TYPE_MODE (vectype
)))
3737 if (check_bool_pattern (var
, vinfo
, bool_stmts
))
3738 rhs
= adjust_bool_stmts (bool_stmts
, TREE_TYPE (vectype
), last_stmt
);
3741 tree type
= search_type_for_mask (var
, vinfo
);
3742 tree cst0
, cst1
, new_vectype
;
3747 if (TYPE_MODE (type
) == TYPE_MODE (TREE_TYPE (vectype
)))
3748 type
= TREE_TYPE (vectype
);
3750 cst0
= build_int_cst (type
, 0);
3751 cst1
= build_int_cst (type
, 1);
3752 new_vectype
= get_vectype_for_scalar_type (type
);
3754 rhs
= vect_recog_temp_ssa_var (type
, NULL
);
3755 pattern_stmt
= gimple_build_assign (rhs
, COND_EXPR
, var
, cst1
, cst0
);
3757 pattern_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
3758 set_vinfo_for_stmt (pattern_stmt
, pattern_stmt_info
);
3759 STMT_VINFO_VECTYPE (pattern_stmt_info
) = new_vectype
;
3760 append_pattern_def_seq (stmt_vinfo
, pattern_stmt
);
3763 lhs
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (vectype
), lhs
);
3764 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
3766 tree rhs2
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3767 gimple
*cast_stmt
= gimple_build_assign (rhs2
, NOP_EXPR
, rhs
);
3768 append_pattern_def_seq (stmt_vinfo
, cast_stmt
);
3771 pattern_stmt
= gimple_build_assign (lhs
, SSA_NAME
, rhs
);
3772 pattern_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
3773 set_vinfo_for_stmt (pattern_stmt
, pattern_stmt_info
);
3774 STMT_VINFO_DATA_REF (pattern_stmt_info
)
3775 = STMT_VINFO_DATA_REF (stmt_vinfo
);
3776 STMT_VINFO_DR_BASE_ADDRESS (pattern_stmt_info
)
3777 = STMT_VINFO_DR_BASE_ADDRESS (stmt_vinfo
);
3778 STMT_VINFO_DR_INIT (pattern_stmt_info
) = STMT_VINFO_DR_INIT (stmt_vinfo
);
3779 STMT_VINFO_DR_OFFSET (pattern_stmt_info
)
3780 = STMT_VINFO_DR_OFFSET (stmt_vinfo
);
3781 STMT_VINFO_DR_STEP (pattern_stmt_info
) = STMT_VINFO_DR_STEP (stmt_vinfo
);
3782 STMT_VINFO_DR_ALIGNED_TO (pattern_stmt_info
)
3783 = STMT_VINFO_DR_ALIGNED_TO (stmt_vinfo
);
3784 DR_STMT (STMT_VINFO_DATA_REF (stmt_vinfo
)) = pattern_stmt
;
3785 *type_out
= vectype
;
3787 stmts
->safe_push (last_stmt
);
3788 if (dump_enabled_p ())
3789 dump_printf_loc (MSG_NOTE
, vect_location
,
3790 "vect_recog_bool_pattern: detected:\n");
3791 return pattern_stmt
;
3798 /* A helper for vect_recog_mask_conversion_pattern. Build
3799 conversion of MASK to a type suitable for masking VECTYPE.
3800 Built statement gets required vectype and is appended to
3801 a pattern sequence of STMT_VINFO.
3803 Return converted mask. */
3806 build_mask_conversion (tree mask
, tree vectype
, stmt_vec_info stmt_vinfo
,
3811 stmt_vec_info new_stmt_info
;
3813 masktype
= build_same_sized_truth_vector_type (vectype
);
3814 tmp
= vect_recog_temp_ssa_var (TREE_TYPE (masktype
), NULL
);
3815 stmt
= gimple_build_assign (tmp
, CONVERT_EXPR
, mask
);
3816 new_stmt_info
= new_stmt_vec_info (stmt
, vinfo
);
3817 set_vinfo_for_stmt (stmt
, new_stmt_info
);
3818 STMT_VINFO_VECTYPE (new_stmt_info
) = masktype
;
3819 append_pattern_def_seq (stmt_vinfo
, stmt
);
3825 /* Function vect_recog_mask_conversion_pattern
3827 Try to find statements which require boolean type
3828 converison. Additional conversion statements are
3829 added to handle such cases. For example:
3839 S4 c_1 = m_3 ? c_2 : c_3;
3841 Will be transformed into:
3845 S3'' m_2' = (_Bool[bitsize=32])m_2
3846 S3' m_3' = m_1 & m_2';
3847 S4'' m_3'' = (_Bool[bitsize=8])m_3'
3848 S4' c_1' = m_3'' ? c_2 : c_3; */
3851 vect_recog_mask_conversion_pattern (vec
<gimple
*> *stmts
, tree
*type_in
,
3854 gimple
*last_stmt
= stmts
->pop ();
3855 enum tree_code rhs_code
;
3856 tree lhs
= NULL_TREE
, rhs1
, rhs2
, tmp
, rhs1_type
, rhs2_type
;
3857 tree vectype1
, vectype2
;
3858 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
3859 stmt_vec_info pattern_stmt_info
;
3860 vec_info
*vinfo
= stmt_vinfo
->vinfo
;
3861 gimple
*pattern_stmt
;
3863 /* Check for MASK_LOAD ans MASK_STORE calls requiring mask conversion. */
3864 if (is_gimple_call (last_stmt
)
3865 && gimple_call_internal_p (last_stmt
)
3866 && (gimple_call_internal_fn (last_stmt
) == IFN_MASK_STORE
3867 || gimple_call_internal_fn (last_stmt
) == IFN_MASK_LOAD
))
3869 bool load
= (gimple_call_internal_fn (last_stmt
) == IFN_MASK_LOAD
);
3873 lhs
= gimple_call_lhs (last_stmt
);
3874 vectype1
= get_vectype_for_scalar_type (TREE_TYPE (lhs
));
3878 rhs2
= gimple_call_arg (last_stmt
, 3);
3879 vectype1
= get_vectype_for_scalar_type (TREE_TYPE (rhs2
));
3882 rhs1
= gimple_call_arg (last_stmt
, 2);
3883 rhs1_type
= search_type_for_mask (rhs1
, vinfo
);
3886 vectype2
= get_mask_type_for_scalar_type (rhs1_type
);
3888 if (!vectype1
|| !vectype2
3889 || TYPE_VECTOR_SUBPARTS (vectype1
) == TYPE_VECTOR_SUBPARTS (vectype2
))
3892 tmp
= build_mask_conversion (rhs1
, vectype1
, stmt_vinfo
, vinfo
);
3896 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3898 = gimple_build_call_internal (IFN_MASK_LOAD
, 3,
3899 gimple_call_arg (last_stmt
, 0),
3900 gimple_call_arg (last_stmt
, 1),
3902 gimple_call_set_lhs (pattern_stmt
, lhs
);
3906 = gimple_build_call_internal (IFN_MASK_STORE
, 4,
3907 gimple_call_arg (last_stmt
, 0),
3908 gimple_call_arg (last_stmt
, 1),
3910 gimple_call_arg (last_stmt
, 3));
3913 pattern_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
3914 set_vinfo_for_stmt (pattern_stmt
, pattern_stmt_info
);
3915 STMT_VINFO_DATA_REF (pattern_stmt_info
)
3916 = STMT_VINFO_DATA_REF (stmt_vinfo
);
3917 STMT_VINFO_DR_BASE_ADDRESS (pattern_stmt_info
)
3918 = STMT_VINFO_DR_BASE_ADDRESS (stmt_vinfo
);
3919 STMT_VINFO_DR_INIT (pattern_stmt_info
) = STMT_VINFO_DR_INIT (stmt_vinfo
);
3920 STMT_VINFO_DR_OFFSET (pattern_stmt_info
)
3921 = STMT_VINFO_DR_OFFSET (stmt_vinfo
);
3922 STMT_VINFO_DR_STEP (pattern_stmt_info
) = STMT_VINFO_DR_STEP (stmt_vinfo
);
3923 STMT_VINFO_DR_ALIGNED_TO (pattern_stmt_info
)
3924 = STMT_VINFO_DR_ALIGNED_TO (stmt_vinfo
);
3925 DR_STMT (STMT_VINFO_DATA_REF (stmt_vinfo
)) = pattern_stmt
;
3927 *type_out
= vectype1
;
3928 *type_in
= vectype1
;
3929 stmts
->safe_push (last_stmt
);
3930 if (dump_enabled_p ())
3931 dump_printf_loc (MSG_NOTE
, vect_location
,
3932 "vect_recog_mask_conversion_pattern: detected:\n");
3934 return pattern_stmt
;
3937 if (!is_gimple_assign (last_stmt
))
3940 lhs
= gimple_assign_lhs (last_stmt
);
3941 rhs1
= gimple_assign_rhs1 (last_stmt
);
3942 rhs_code
= gimple_assign_rhs_code (last_stmt
);
3944 /* Check for cond expression requiring mask conversion. */
3945 if (rhs_code
== COND_EXPR
)
3947 /* vect_recog_mixed_size_cond_pattern could apply.
3949 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
))
3952 vectype1
= get_vectype_for_scalar_type (TREE_TYPE (lhs
));
3954 if (TREE_CODE (rhs1
) == SSA_NAME
)
3956 rhs1_type
= search_type_for_mask (rhs1
, vinfo
);
3960 else if (COMPARISON_CLASS_P (rhs1
))
3961 rhs1_type
= TREE_TYPE (TREE_OPERAND (rhs1
, 0));
3965 vectype2
= get_mask_type_for_scalar_type (rhs1_type
);
3967 if (!vectype1
|| !vectype2
3968 || TYPE_VECTOR_SUBPARTS (vectype1
) == TYPE_VECTOR_SUBPARTS (vectype2
))
3971 /* If rhs1 is a comparison we need to move it into a
3972 separate statement. */
3973 if (TREE_CODE (rhs1
) != SSA_NAME
)
3975 tmp
= vect_recog_temp_ssa_var (TREE_TYPE (rhs1
), NULL
);
3976 pattern_stmt
= gimple_build_assign (tmp
, rhs1
);
3979 pattern_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
3980 set_vinfo_for_stmt (pattern_stmt
, pattern_stmt_info
);
3981 STMT_VINFO_VECTYPE (pattern_stmt_info
) = vectype2
;
3982 append_pattern_def_seq (stmt_vinfo
, pattern_stmt
);
3985 tmp
= build_mask_conversion (rhs1
, vectype1
, stmt_vinfo
, vinfo
);
3987 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3988 pattern_stmt
= gimple_build_assign (lhs
, COND_EXPR
, tmp
,
3989 gimple_assign_rhs2 (last_stmt
),
3990 gimple_assign_rhs3 (last_stmt
));
3992 *type_out
= vectype1
;
3993 *type_in
= vectype1
;
3994 stmts
->safe_push (last_stmt
);
3995 if (dump_enabled_p ())
3996 dump_printf_loc (MSG_NOTE
, vect_location
,
3997 "vect_recog_mask_conversion_pattern: detected:\n");
3999 return pattern_stmt
;
4002 /* Now check for binary boolean operations requiring conversion for
4004 if (TREE_CODE (TREE_TYPE (lhs
)) != BOOLEAN_TYPE
)
4007 if (rhs_code
!= BIT_IOR_EXPR
4008 && rhs_code
!= BIT_XOR_EXPR
4009 && rhs_code
!= BIT_AND_EXPR
4010 && TREE_CODE_CLASS (rhs_code
) != tcc_comparison
)
4013 rhs2
= gimple_assign_rhs2 (last_stmt
);
4015 rhs1_type
= search_type_for_mask (rhs1
, vinfo
);
4016 rhs2_type
= search_type_for_mask (rhs2
, vinfo
);
4018 if (!rhs1_type
|| !rhs2_type
4019 || TYPE_PRECISION (rhs1_type
) == TYPE_PRECISION (rhs2_type
))
4022 if (TYPE_PRECISION (rhs1_type
) < TYPE_PRECISION (rhs2_type
))
4024 vectype1
= get_mask_type_for_scalar_type (rhs1_type
);
4027 rhs2
= build_mask_conversion (rhs2
, vectype1
, stmt_vinfo
, vinfo
);
4031 vectype1
= get_mask_type_for_scalar_type (rhs2_type
);
4034 rhs1
= build_mask_conversion (rhs1
, vectype1
, stmt_vinfo
, vinfo
);
4037 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
4038 pattern_stmt
= gimple_build_assign (lhs
, rhs_code
, rhs1
, rhs2
);
4040 *type_out
= vectype1
;
4041 *type_in
= vectype1
;
4042 stmts
->safe_push (last_stmt
);
4043 if (dump_enabled_p ())
4044 dump_printf_loc (MSG_NOTE
, vect_location
,
4045 "vect_recog_mask_conversion_pattern: detected:\n");
4047 return pattern_stmt
;
4051 /* Mark statements that are involved in a pattern. */
4054 vect_mark_pattern_stmts (gimple
*orig_stmt
, gimple
*pattern_stmt
,
4055 tree pattern_vectype
)
4057 stmt_vec_info pattern_stmt_info
, def_stmt_info
;
4058 stmt_vec_info orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
4059 vec_info
*vinfo
= orig_stmt_info
->vinfo
;
4062 pattern_stmt_info
= vinfo_for_stmt (pattern_stmt
);
4063 if (pattern_stmt_info
== NULL
)
4065 pattern_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
4066 set_vinfo_for_stmt (pattern_stmt
, pattern_stmt_info
);
4068 gimple_set_bb (pattern_stmt
, gimple_bb (orig_stmt
));
4070 STMT_VINFO_RELATED_STMT (pattern_stmt_info
) = orig_stmt
;
4071 STMT_VINFO_DEF_TYPE (pattern_stmt_info
)
4072 = STMT_VINFO_DEF_TYPE (orig_stmt_info
);
4073 STMT_VINFO_VECTYPE (pattern_stmt_info
) = pattern_vectype
;
4074 STMT_VINFO_IN_PATTERN_P (orig_stmt_info
) = true;
4075 STMT_VINFO_RELATED_STMT (orig_stmt_info
) = pattern_stmt
;
4076 STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info
)
4077 = STMT_VINFO_PATTERN_DEF_SEQ (orig_stmt_info
);
4078 if (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info
))
4080 gimple_stmt_iterator si
;
4081 for (si
= gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info
));
4082 !gsi_end_p (si
); gsi_next (&si
))
4084 def_stmt
= gsi_stmt (si
);
4085 def_stmt_info
= vinfo_for_stmt (def_stmt
);
4086 if (def_stmt_info
== NULL
)
4088 def_stmt_info
= new_stmt_vec_info (def_stmt
, vinfo
);
4089 set_vinfo_for_stmt (def_stmt
, def_stmt_info
);
4091 gimple_set_bb (def_stmt
, gimple_bb (orig_stmt
));
4092 STMT_VINFO_RELATED_STMT (def_stmt_info
) = orig_stmt
;
4093 STMT_VINFO_DEF_TYPE (def_stmt_info
) = vect_internal_def
;
4094 if (STMT_VINFO_VECTYPE (def_stmt_info
) == NULL_TREE
)
4095 STMT_VINFO_VECTYPE (def_stmt_info
) = pattern_vectype
;
4100 /* Function vect_pattern_recog_1
4103 PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
4104 computation pattern.
4105 STMT: A stmt from which the pattern search should start.
4107 If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
4108 expression that computes the same functionality and can be used to
4109 replace the sequence of stmts that are involved in the pattern.
4112 This function checks if the expression returned by PATTERN_RECOG_FUNC is
4113 supported in vector form by the target. We use 'TYPE_IN' to obtain the
4114 relevant vector type. If 'TYPE_IN' is already a vector type, then this
4115 indicates that target support had already been checked by PATTERN_RECOG_FUNC.
4116 If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
4117 to the available target pattern.
4119 This function also does some bookkeeping, as explained in the documentation
4120 for vect_recog_pattern. */
4123 vect_pattern_recog_1 (vect_recog_func
*recog_func
,
4124 gimple_stmt_iterator si
,
4125 vec
<gimple
*> *stmts_to_replace
)
4127 gimple
*stmt
= gsi_stmt (si
), *pattern_stmt
;
4128 stmt_vec_info stmt_info
;
4129 loop_vec_info loop_vinfo
;
4130 tree pattern_vectype
;
4131 tree type_in
, type_out
;
4132 enum tree_code code
;
4136 stmts_to_replace
->truncate (0);
4137 stmts_to_replace
->quick_push (stmt
);
4138 pattern_stmt
= recog_func
->fn (stmts_to_replace
, &type_in
, &type_out
);
4142 stmt
= stmts_to_replace
->last ();
4143 stmt_info
= vinfo_for_stmt (stmt
);
4144 loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4146 if (VECTOR_BOOLEAN_TYPE_P (type_in
)
4147 || VECTOR_MODE_P (TYPE_MODE (type_in
)))
4149 /* No need to check target support (already checked by the pattern
4150 recognition function). */
4151 pattern_vectype
= type_out
? type_out
: type_in
;
4155 machine_mode vec_mode
;
4156 enum insn_code icode
;
4159 /* Check target support */
4160 type_in
= get_vectype_for_scalar_type (type_in
);
4164 type_out
= get_vectype_for_scalar_type (type_out
);
4169 pattern_vectype
= type_out
;
4171 if (is_gimple_assign (pattern_stmt
))
4172 code
= gimple_assign_rhs_code (pattern_stmt
);
4175 gcc_assert (is_gimple_call (pattern_stmt
));
4179 optab
= optab_for_tree_code (code
, type_in
, optab_default
);
4180 vec_mode
= TYPE_MODE (type_in
);
4182 || (icode
= optab_handler (optab
, vec_mode
)) == CODE_FOR_nothing
4183 || (insn_data
[icode
].operand
[0].mode
!= TYPE_MODE (type_out
)))
4187 /* Found a vectorizable pattern. */
4188 if (dump_enabled_p ())
4190 dump_printf_loc (MSG_NOTE
, vect_location
,
4191 "%s pattern recognized: ", recog_func
->name
);
4192 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
4195 /* Mark the stmts that are involved in the pattern. */
4196 vect_mark_pattern_stmts (stmt
, pattern_stmt
, pattern_vectype
);
4198 /* Patterns cannot be vectorized using SLP, because they change the order of
4201 FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTIONS (loop_vinfo
), i
, next
)
4203 LOOP_VINFO_REDUCTIONS (loop_vinfo
).ordered_remove (i
);
4205 /* It is possible that additional pattern stmts are created and inserted in
4206 STMTS_TO_REPLACE. We create a stmt_info for each of them, and mark the
4207 relevant statements. */
4208 for (i
= 0; stmts_to_replace
->iterate (i
, &stmt
)
4209 && (unsigned) i
< (stmts_to_replace
->length () - 1);
4212 stmt_info
= vinfo_for_stmt (stmt
);
4213 pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4214 if (dump_enabled_p ())
4216 dump_printf_loc (MSG_NOTE
, vect_location
,
4217 "additional pattern stmt: ");
4218 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
4221 vect_mark_pattern_stmts (stmt
, pattern_stmt
, NULL_TREE
);
4228 /* Function vect_pattern_recog
4231 LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
4234 Output - for each computation idiom that is detected we create a new stmt
4235 that provides the same functionality and that can be vectorized. We
4236 also record some information in the struct_stmt_info of the relevant
4237 stmts, as explained below:
4239 At the entry to this function we have the following stmts, with the
4240 following initial value in the STMT_VINFO fields:
4242 stmt in_pattern_p related_stmt vec_stmt
4243 S1: a_i = .... - - -
4244 S2: a_2 = ..use(a_i).. - - -
4245 S3: a_1 = ..use(a_2).. - - -
4246 S4: a_0 = ..use(a_1).. - - -
4247 S5: ... = ..use(a_0).. - - -
4249 Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
4250 represented by a single stmt. We then:
4251 - create a new stmt S6 equivalent to the pattern (the stmt is not
4252 inserted into the code)
4253 - fill in the STMT_VINFO fields as follows:
4255 in_pattern_p related_stmt vec_stmt
4256 S1: a_i = .... - - -
4257 S2: a_2 = ..use(a_i).. - - -
4258 S3: a_1 = ..use(a_2).. - - -
4259 S4: a_0 = ..use(a_1).. true S6 -
4260 '---> S6: a_new = .... - S4 -
4261 S5: ... = ..use(a_0).. - - -
4263 (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
4264 to each other through the RELATED_STMT field).
4266 S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
4267 of S4 because it will replace all its uses. Stmts {S1,S2,S3} will
4268 remain irrelevant unless used by stmts other than S4.
4270 If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
4271 (because they are marked as irrelevant). It will vectorize S6, and record
4272 a pointer to the new vector stmt VS6 from S6 (as usual).
4273 S4 will be skipped, and S5 will be vectorized as usual:
4275 in_pattern_p related_stmt vec_stmt
4276 S1: a_i = .... - - -
4277 S2: a_2 = ..use(a_i).. - - -
4278 S3: a_1 = ..use(a_2).. - - -
4279 > VS6: va_new = .... - - -
4280 S4: a_0 = ..use(a_1).. true S6 VS6
4281 '---> S6: a_new = .... - S4 VS6
4282 > VS5: ... = ..vuse(va_new).. - - -
4283 S5: ... = ..use(a_0).. - - -
4285 DCE could then get rid of {S1,S2,S3,S4,S5} (if their defs are not used
4286 elsewhere), and we'll end up with:
4289 VS5: ... = ..vuse(va_new)..
4291 In case of more than one pattern statements, e.g., widen-mult with
4295 S2 a_T = (TYPE) a_t;
4296 '--> S3: a_it = (interm_type) a_t;
4297 S4 prod_T = a_T * CONST;
4298 '--> S5: prod_T' = a_it w* CONST;
4300 there may be other users of a_T outside the pattern. In that case S2 will
4301 be marked as relevant (as well as S3), and both S2 and S3 will be analyzed
4302 and vectorized. The vector stmt VS2 will be recorded in S2, and VS3 will
4303 be recorded in S3. */
4306 vect_pattern_recog (vec_info
*vinfo
)
4311 gimple_stmt_iterator si
;
4313 auto_vec
<gimple
*, 1> stmts_to_replace
;
4316 if (dump_enabled_p ())
4317 dump_printf_loc (MSG_NOTE
, vect_location
,
4318 "=== vect_pattern_recog ===\n");
4320 if (loop_vec_info loop_vinfo
= dyn_cast
<loop_vec_info
> (vinfo
))
4322 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4323 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
4324 nbbs
= loop
->num_nodes
;
4326 /* Scan through the loop stmts, applying the pattern recognition
4327 functions starting at each stmt visited: */
4328 for (i
= 0; i
< nbbs
; i
++)
4330 basic_block bb
= bbs
[i
];
4331 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
4333 /* Scan over all generic vect_recog_xxx_pattern functions. */
4334 for (j
= 0; j
< NUM_PATTERNS
; j
++)
4335 if (vect_pattern_recog_1 (&vect_vect_recog_func_ptrs
[j
], si
,
4343 bb_vec_info bb_vinfo
= as_a
<bb_vec_info
> (vinfo
);
4344 for (si
= bb_vinfo
->region_begin
;
4345 gsi_stmt (si
) != gsi_stmt (bb_vinfo
->region_end
); gsi_next (&si
))
4347 if ((stmt
= gsi_stmt (si
))
4348 && vinfo_for_stmt (stmt
)
4349 && !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt
)))
4352 /* Scan over all generic vect_recog_xxx_pattern functions. */
4353 for (j
= 0; j
< NUM_PATTERNS
; j
++)
4354 if (vect_pattern_recog_1 (&vect_vect_recog_func_ptrs
[j
], si
,