1 /* Analysis Utilities for Loop Vectorization.
2 Copyright (C) 2006-2017 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
);
1088 gimple_call_set_nothrow (stmt
, true);
1097 /* Function vect_recog_widen_sum_pattern
1099 Try to find the following pattern:
1102 TYPE x_T, sum = init;
1104 sum_0 = phi <init, sum_1>
1106 S2 x_T = (TYPE) x_t;
1107 S3 sum_1 = x_T + sum_0;
1109 where type 'TYPE' is at least double the size of type 'type', i.e - we're
1110 summing elements of type 'type' into an accumulator of type 'TYPE'. This is
1111 a special case of a reduction computation.
1115 * LAST_STMT: A stmt from which the pattern search begins. In the example,
1116 when this function is called with S3, the pattern {S2,S3} will be detected.
1120 * TYPE_IN: The type of the input arguments to the pattern.
1122 * TYPE_OUT: The type of the output of this pattern.
1124 * Return value: A new stmt that will be used to replace the sequence of
1125 stmts that constitute the pattern. In this case it will be:
1126 WIDEN_SUM <x_t, sum_0>
1128 Note: The widening-sum idiom is a widening reduction pattern that is
1129 vectorized without preserving all the intermediate results. It
1130 produces only N/2 (widened) results (by summing up pairs of
1131 intermediate results) rather than all N results. Therefore, we
1132 cannot allow this pattern when we want to get all the results and in
1133 the correct order (as is the case when this computation is in an
1134 inner-loop nested in an outer-loop that us being vectorized). */
1137 vect_recog_widen_sum_pattern (vec
<gimple
*> *stmts
, tree
*type_in
,
1140 gimple
*stmt
, *last_stmt
= (*stmts
)[0];
1141 tree oprnd0
, oprnd1
;
1142 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
1143 tree type
, half_type
;
1144 gimple
*pattern_stmt
;
1145 loop_vec_info loop_info
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
1153 loop
= LOOP_VINFO_LOOP (loop_info
);
1155 /* We don't allow changing the order of the computation in the inner-loop
1156 when doing outer-loop vectorization. */
1157 if (loop
&& nested_in_vect_loop_p (loop
, last_stmt
))
1160 if (!is_gimple_assign (last_stmt
))
1163 type
= gimple_expr_type (last_stmt
);
1165 /* Look for the following pattern
1168 In which DX is at least double the size of X, and sum_1 has been
1169 recognized as a reduction variable.
1172 /* Starting from LAST_STMT, follow the defs of its uses in search
1173 of the above pattern. */
1175 if (gimple_assign_rhs_code (last_stmt
) != PLUS_EXPR
)
1178 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) != vect_reduction_def
1179 && ! STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_vinfo
))
1182 oprnd0
= gimple_assign_rhs1 (last_stmt
);
1183 oprnd1
= gimple_assign_rhs2 (last_stmt
);
1184 if (!types_compatible_p (TREE_TYPE (oprnd0
), type
)
1185 || !types_compatible_p (TREE_TYPE (oprnd1
), type
))
1188 /* So far so good. Since last_stmt was detected as a (summation) reduction,
1189 we know that oprnd1 is the reduction variable (defined by a loop-header
1190 phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
1191 Left to check that oprnd0 is defined by a cast from type 'type' to type
1194 if (!type_conversion_p (oprnd0
, last_stmt
, true, &half_type
, &stmt
,
1199 oprnd0
= gimple_assign_rhs1 (stmt
);
1200 *type_in
= half_type
;
1203 /* Pattern detected. Create a stmt to be used to replace the pattern: */
1204 var
= vect_recog_temp_ssa_var (type
, NULL
);
1205 pattern_stmt
= gimple_build_assign (var
, WIDEN_SUM_EXPR
, oprnd0
, oprnd1
);
1207 if (dump_enabled_p ())
1209 dump_printf_loc (MSG_NOTE
, vect_location
,
1210 "vect_recog_widen_sum_pattern: detected: ");
1211 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
1214 return pattern_stmt
;
1218 /* Return TRUE if the operation in STMT can be performed on a smaller type.
1221 STMT - a statement to check.
1222 DEF - we support operations with two operands, one of which is constant.
1223 The other operand can be defined by a demotion operation, or by a
1224 previous statement in a sequence of over-promoted operations. In the
1225 later case DEF is used to replace that operand. (It is defined by a
1226 pattern statement we created for the previous statement in the
1230 NEW_TYPE - Output: a smaller type that we are trying to use. Input: if not
1231 NULL, it's the type of DEF.
1232 STMTS - additional pattern statements. If a pattern statement (type
1233 conversion) is created in this function, its original statement is
1237 OP0, OP1 - if the operation fits a smaller type, OP0 and OP1 are the new
1238 operands to use in the new pattern statement for STMT (will be created
1239 in vect_recog_over_widening_pattern ()).
1240 NEW_DEF_STMT - in case DEF has to be promoted, we create two pattern
1241 statements for STMT: the first one is a type promotion and the second
1242 one is the operation itself. We return the type promotion statement
1243 in NEW_DEF_STMT and further store it in STMT_VINFO_PATTERN_DEF_SEQ of
1244 the second pattern statement. */
1247 vect_operation_fits_smaller_type (gimple
*stmt
, tree def
, tree
*new_type
,
1248 tree
*op0
, tree
*op1
, gimple
**new_def_stmt
,
1249 vec
<gimple
*> *stmts
)
1251 enum tree_code code
;
1252 tree const_oprnd
, oprnd
;
1253 tree interm_type
= NULL_TREE
, half_type
, new_oprnd
, type
;
1254 gimple
*def_stmt
, *new_stmt
;
1260 *new_def_stmt
= NULL
;
1262 if (!is_gimple_assign (stmt
))
1265 code
= gimple_assign_rhs_code (stmt
);
1266 if (code
!= LSHIFT_EXPR
&& code
!= RSHIFT_EXPR
1267 && code
!= BIT_IOR_EXPR
&& code
!= BIT_XOR_EXPR
&& code
!= BIT_AND_EXPR
)
1270 oprnd
= gimple_assign_rhs1 (stmt
);
1271 const_oprnd
= gimple_assign_rhs2 (stmt
);
1272 type
= gimple_expr_type (stmt
);
1274 if (TREE_CODE (oprnd
) != SSA_NAME
1275 || TREE_CODE (const_oprnd
) != INTEGER_CST
)
1278 /* If oprnd has other uses besides that in stmt we cannot mark it
1279 as being part of a pattern only. */
1280 if (!has_single_use (oprnd
))
1283 /* If we are in the middle of a sequence, we use DEF from a previous
1284 statement. Otherwise, OPRND has to be a result of type promotion. */
1287 half_type
= *new_type
;
1293 if (!type_conversion_p (oprnd
, stmt
, false, &half_type
, &def_stmt
,
1296 || !vect_same_loop_or_bb_p (stmt
, def_stmt
))
1300 /* Can we perform the operation on a smaller type? */
1306 if (!int_fits_type_p (const_oprnd
, half_type
))
1308 /* HALF_TYPE is not enough. Try a bigger type if possible. */
1309 if (TYPE_PRECISION (type
) < (TYPE_PRECISION (half_type
) * 4))
1312 interm_type
= build_nonstandard_integer_type (
1313 TYPE_PRECISION (half_type
) * 2, TYPE_UNSIGNED (type
));
1314 if (!int_fits_type_p (const_oprnd
, interm_type
))
1321 /* Try intermediate type - HALF_TYPE is not enough for sure. */
1322 if (TYPE_PRECISION (type
) < (TYPE_PRECISION (half_type
) * 4))
1325 /* Check that HALF_TYPE size + shift amount <= INTERM_TYPE size.
1326 (e.g., if the original value was char, the shift amount is at most 8
1327 if we want to use short). */
1328 if (compare_tree_int (const_oprnd
, TYPE_PRECISION (half_type
)) == 1)
1331 interm_type
= build_nonstandard_integer_type (
1332 TYPE_PRECISION (half_type
) * 2, TYPE_UNSIGNED (type
));
1334 if (!vect_supportable_shift (code
, interm_type
))
1340 if (vect_supportable_shift (code
, half_type
))
1343 /* Try intermediate type - HALF_TYPE is not supported. */
1344 if (TYPE_PRECISION (type
) < (TYPE_PRECISION (half_type
) * 4))
1347 interm_type
= build_nonstandard_integer_type (
1348 TYPE_PRECISION (half_type
) * 2, TYPE_UNSIGNED (type
));
1350 if (!vect_supportable_shift (code
, interm_type
))
1359 /* There are four possible cases:
1360 1. OPRND is defined by a type promotion (in that case FIRST is TRUE, it's
1361 the first statement in the sequence)
1362 a. The original, HALF_TYPE, is not enough - we replace the promotion
1363 from HALF_TYPE to TYPE with a promotion to INTERM_TYPE.
1364 b. HALF_TYPE is sufficient, OPRND is set as the RHS of the original
1366 2. OPRND is defined by a pattern statement we created.
1367 a. Its type is not sufficient for the operation, we create a new stmt:
1368 a type conversion for OPRND from HALF_TYPE to INTERM_TYPE. We store
1369 this statement in NEW_DEF_STMT, and it is later put in
1370 STMT_VINFO_PATTERN_DEF_SEQ of the pattern statement for STMT.
1371 b. OPRND is good to use in the new statement. */
1376 /* Replace the original type conversion HALF_TYPE->TYPE with
1377 HALF_TYPE->INTERM_TYPE. */
1378 if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
)))
1380 new_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
));
1381 /* Check if the already created pattern stmt is what we need. */
1382 if (!is_gimple_assign (new_stmt
)
1383 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (new_stmt
))
1384 || TREE_TYPE (gimple_assign_lhs (new_stmt
)) != interm_type
)
1387 stmts
->safe_push (def_stmt
);
1388 oprnd
= gimple_assign_lhs (new_stmt
);
1392 /* Create NEW_OPRND = (INTERM_TYPE) OPRND. */
1393 oprnd
= gimple_assign_rhs1 (def_stmt
);
1394 new_oprnd
= make_ssa_name (interm_type
);
1395 new_stmt
= gimple_build_assign (new_oprnd
, NOP_EXPR
, oprnd
);
1396 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
)) = new_stmt
;
1397 stmts
->safe_push (def_stmt
);
1403 /* Retrieve the operand before the type promotion. */
1404 oprnd
= gimple_assign_rhs1 (def_stmt
);
1411 /* Create a type conversion HALF_TYPE->INTERM_TYPE. */
1412 new_oprnd
= make_ssa_name (interm_type
);
1413 new_stmt
= gimple_build_assign (new_oprnd
, NOP_EXPR
, oprnd
);
1415 *new_def_stmt
= new_stmt
;
1418 /* Otherwise, OPRND is already set. */
1422 *new_type
= interm_type
;
1424 *new_type
= half_type
;
1427 *op1
= fold_convert (*new_type
, const_oprnd
);
1433 /* Try to find a statement or a sequence of statements that can be performed
1437 TYPE x_T, res0_T, res1_T;
1440 S2 x_T = (TYPE) x_t;
1441 S3 res0_T = op (x_T, C0);
1442 S4 res1_T = op (res0_T, C1);
1443 S5 ... = () res1_T; - type demotion
1445 where type 'TYPE' is at least double the size of type 'type', C0 and C1 are
1447 Check if S3 and S4 can be done on a smaller type than 'TYPE', it can either
1448 be 'type' or some intermediate type. For now, we expect S5 to be a type
1449 demotion operation. We also check that S3 and S4 have only one use. */
1452 vect_recog_over_widening_pattern (vec
<gimple
*> *stmts
,
1453 tree
*type_in
, tree
*type_out
)
1455 gimple
*stmt
= stmts
->pop ();
1456 gimple
*pattern_stmt
= NULL
, *new_def_stmt
, *prev_stmt
= NULL
,
1458 tree op0
, op1
, vectype
= NULL_TREE
, use_lhs
, use_type
;
1459 tree var
= NULL_TREE
, new_type
= NULL_TREE
, new_oprnd
;
1466 if (!vinfo_for_stmt (stmt
)
1467 || STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (stmt
)))
1470 new_def_stmt
= NULL
;
1471 if (!vect_operation_fits_smaller_type (stmt
, var
, &new_type
,
1472 &op0
, &op1
, &new_def_stmt
,
1481 /* STMT can be performed on a smaller type. Check its uses. */
1482 use_stmt
= vect_single_imm_use (stmt
);
1483 if (!use_stmt
|| !is_gimple_assign (use_stmt
))
1486 /* Create pattern statement for STMT. */
1487 vectype
= get_vectype_for_scalar_type (new_type
);
1491 /* We want to collect all the statements for which we create pattern
1492 statetments, except for the case when the last statement in the
1493 sequence doesn't have a corresponding pattern statement. In such
1494 case we associate the last pattern statement with the last statement
1495 in the sequence. Therefore, we only add the original statement to
1496 the list if we know that it is not the last. */
1498 stmts
->safe_push (prev_stmt
);
1500 var
= vect_recog_temp_ssa_var (new_type
, NULL
);
1502 = gimple_build_assign (var
, gimple_assign_rhs_code (stmt
), op0
, op1
);
1503 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt
)) = pattern_stmt
;
1504 new_pattern_def_seq (vinfo_for_stmt (stmt
), new_def_stmt
);
1506 if (dump_enabled_p ())
1508 dump_printf_loc (MSG_NOTE
, vect_location
,
1509 "created pattern stmt: ");
1510 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
1513 type
= gimple_expr_type (stmt
);
1520 /* We got a sequence. We expect it to end with a type demotion operation.
1521 Otherwise, we quit (for now). There are three possible cases: the
1522 conversion is to NEW_TYPE (we don't do anything), the conversion is to
1523 a type bigger than NEW_TYPE and/or the signedness of USE_TYPE and
1524 NEW_TYPE differs (we create a new conversion statement). */
1525 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt
)))
1527 use_lhs
= gimple_assign_lhs (use_stmt
);
1528 use_type
= TREE_TYPE (use_lhs
);
1529 /* Support only type demotion or signedess change. */
1530 if (!INTEGRAL_TYPE_P (use_type
)
1531 || TYPE_PRECISION (type
) <= TYPE_PRECISION (use_type
))
1534 /* Check that NEW_TYPE is not bigger than the conversion result. */
1535 if (TYPE_PRECISION (new_type
) > TYPE_PRECISION (use_type
))
1538 if (TYPE_UNSIGNED (new_type
) != TYPE_UNSIGNED (use_type
)
1539 || TYPE_PRECISION (new_type
) != TYPE_PRECISION (use_type
))
1541 /* Create NEW_TYPE->USE_TYPE conversion. */
1542 new_oprnd
= make_ssa_name (use_type
);
1543 pattern_stmt
= gimple_build_assign (new_oprnd
, NOP_EXPR
, var
);
1544 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use_stmt
)) = pattern_stmt
;
1546 *type_in
= get_vectype_for_scalar_type (new_type
);
1547 *type_out
= get_vectype_for_scalar_type (use_type
);
1549 /* We created a pattern statement for the last statement in the
1550 sequence, so we don't need to associate it with the pattern
1551 statement created for PREV_STMT. Therefore, we add PREV_STMT
1552 to the list in order to mark it later in vect_pattern_recog_1. */
1554 stmts
->safe_push (prev_stmt
);
1559 STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (use_stmt
))
1560 = STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (prev_stmt
));
1563 *type_out
= NULL_TREE
;
1566 stmts
->safe_push (use_stmt
);
1569 /* TODO: support general case, create a conversion to the correct type. */
1572 /* Pattern detected. */
1573 if (dump_enabled_p ())
1575 dump_printf_loc (MSG_NOTE
, vect_location
,
1576 "vect_recog_over_widening_pattern: detected: ");
1577 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
1580 return pattern_stmt
;
1583 /* Detect widening shift pattern:
1589 S2 a_T = (TYPE) a_t;
1590 S3 res_T = a_T << CONST;
1592 where type 'TYPE' is at least double the size of type 'type'.
1594 Also detect cases where the shift result is immediately converted
1595 to another type 'result_type' that is no larger in size than 'TYPE'.
1596 In those cases we perform a widen-shift that directly results in
1597 'result_type', to avoid a possible over-widening situation:
1601 result_type res_result;
1604 S2 a_T = (TYPE) a_t;
1605 S3 res_T = a_T << CONST;
1606 S4 res_result = (result_type) res_T;
1607 '--> res_result' = a_t w<< CONST;
1609 And a case when 'TYPE' is 4 times bigger than 'type'. In that case we
1610 create an additional pattern stmt for S2 to create a variable of an
1611 intermediate type, and perform widen-shift on the intermediate type:
1615 TYPE a_T, res_T, res_T';
1618 S2 a_T = (TYPE) a_t;
1619 '--> a_it = (interm_type) a_t;
1620 S3 res_T = a_T << CONST;
1621 '--> res_T' = a_it <<* CONST;
1625 * STMTS: Contains a stmt from which the pattern search begins.
1626 In case of unsigned widen-shift, the original stmt (S3) is replaced with S4
1627 in STMTS. When an intermediate type is used and a pattern statement is
1628 created for S2, we also put S2 here (before S3).
1632 * TYPE_IN: The type of the input arguments to the pattern.
1634 * TYPE_OUT: The type of the output of this pattern.
1636 * Return value: A new stmt that will be used to replace the sequence of
1637 stmts that constitute the pattern. In this case it will be:
1638 WIDEN_LSHIFT_EXPR <a_t, CONST>. */
1641 vect_recog_widen_shift_pattern (vec
<gimple
*> *stmts
,
1642 tree
*type_in
, tree
*type_out
)
1644 gimple
*last_stmt
= stmts
->pop ();
1646 tree oprnd0
, oprnd1
;
1647 tree type
, half_type0
;
1648 gimple
*pattern_stmt
;
1649 tree vectype
, vectype_out
= NULL_TREE
;
1651 enum tree_code dummy_code
;
1653 vec
<tree
> dummy_vec
;
1657 if (!is_gimple_assign (last_stmt
) || !vinfo_for_stmt (last_stmt
))
1660 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (last_stmt
)))
1663 if (gimple_assign_rhs_code (last_stmt
) != LSHIFT_EXPR
)
1666 oprnd0
= gimple_assign_rhs1 (last_stmt
);
1667 oprnd1
= gimple_assign_rhs2 (last_stmt
);
1668 if (TREE_CODE (oprnd0
) != SSA_NAME
|| TREE_CODE (oprnd1
) != INTEGER_CST
)
1671 /* Check operand 0: it has to be defined by a type promotion. */
1672 if (!type_conversion_p (oprnd0
, last_stmt
, false, &half_type0
, &def_stmt0
,
1677 /* Check operand 1: has to be positive. We check that it fits the type
1678 in vect_handle_widen_op_by_const (). */
1679 if (tree_int_cst_compare (oprnd1
, size_zero_node
) <= 0)
1682 oprnd0
= gimple_assign_rhs1 (def_stmt0
);
1683 type
= gimple_expr_type (last_stmt
);
1685 /* Check for subsequent conversion to another type. */
1686 use_stmt
= vect_single_imm_use (last_stmt
);
1687 if (use_stmt
&& is_gimple_assign (use_stmt
)
1688 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt
))
1689 && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt
)))
1691 tree use_lhs
= gimple_assign_lhs (use_stmt
);
1692 tree use_type
= TREE_TYPE (use_lhs
);
1694 if (INTEGRAL_TYPE_P (use_type
)
1695 && TYPE_PRECISION (use_type
) <= TYPE_PRECISION (type
))
1697 last_stmt
= use_stmt
;
1702 /* Check if this a widening operation. */
1703 gimple
*wstmt
= NULL
;
1704 if (!vect_handle_widen_op_by_const (last_stmt
, LSHIFT_EXPR
, oprnd1
,
1706 type
, &half_type0
, def_stmt0
))
1709 /* Pattern detected. */
1710 if (dump_enabled_p ())
1711 dump_printf_loc (MSG_NOTE
, vect_location
,
1712 "vect_recog_widen_shift_pattern: detected:\n");
1714 /* Check target support. */
1715 vectype
= get_vectype_for_scalar_type (half_type0
);
1716 vectype_out
= get_vectype_for_scalar_type (type
);
1720 || !supportable_widening_operation (WIDEN_LSHIFT_EXPR
, last_stmt
,
1721 vectype_out
, vectype
,
1722 &dummy_code
, &dummy_code
,
1723 &dummy_int
, &dummy_vec
))
1727 *type_out
= vectype_out
;
1729 /* Pattern supported. Create a stmt to be used to replace the pattern. */
1730 var
= vect_recog_temp_ssa_var (type
, NULL
);
1732 gimple_build_assign (var
, WIDEN_LSHIFT_EXPR
, oprnd0
, oprnd1
);
1735 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
1736 new_pattern_def_seq (stmt_vinfo
, wstmt
);
1737 stmt_vec_info new_stmt_info
1738 = new_stmt_vec_info (wstmt
, stmt_vinfo
->vinfo
);
1739 set_vinfo_for_stmt (wstmt
, new_stmt_info
);
1740 STMT_VINFO_VECTYPE (new_stmt_info
) = vectype
;
1743 if (dump_enabled_p ())
1744 dump_gimple_stmt_loc (MSG_NOTE
, vect_location
, TDF_SLIM
, pattern_stmt
, 0);
1746 stmts
->safe_push (last_stmt
);
1747 return pattern_stmt
;
1750 /* Detect a rotate pattern wouldn't be otherwise vectorized:
1754 S0 a_t = b_t r<< c_t;
1758 * STMTS: Contains a stmt from which the pattern search begins,
1759 i.e. the shift/rotate stmt. The original stmt (S0) is replaced
1763 S2 e_t = d_t & (B - 1);
1764 S3 f_t = b_t << c_t;
1765 S4 g_t = b_t >> e_t;
1768 where B is element bitsize of type.
1772 * TYPE_IN: The type of the input arguments to the pattern.
1774 * TYPE_OUT: The type of the output of this pattern.
1776 * Return value: A new stmt that will be used to replace the rotate
1780 vect_recog_rotate_pattern (vec
<gimple
*> *stmts
, tree
*type_in
, tree
*type_out
)
1782 gimple
*last_stmt
= stmts
->pop ();
1783 tree oprnd0
, oprnd1
, lhs
, var
, var1
, var2
, vectype
, type
, stype
, def
, def2
;
1784 gimple
*pattern_stmt
, *def_stmt
;
1785 enum tree_code rhs_code
;
1786 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
1787 vec_info
*vinfo
= stmt_vinfo
->vinfo
;
1788 enum vect_def_type dt
;
1789 optab optab1
, optab2
;
1790 edge ext_def
= NULL
;
1792 if (!is_gimple_assign (last_stmt
))
1795 rhs_code
= gimple_assign_rhs_code (last_stmt
);
1805 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
))
1808 lhs
= gimple_assign_lhs (last_stmt
);
1809 oprnd0
= gimple_assign_rhs1 (last_stmt
);
1810 type
= TREE_TYPE (oprnd0
);
1811 oprnd1
= gimple_assign_rhs2 (last_stmt
);
1812 if (TREE_CODE (oprnd0
) != SSA_NAME
1813 || TYPE_PRECISION (TREE_TYPE (lhs
)) != TYPE_PRECISION (type
)
1814 || !INTEGRAL_TYPE_P (type
)
1815 || !TYPE_UNSIGNED (type
))
1818 if (!vect_is_simple_use (oprnd1
, vinfo
, &def_stmt
, &dt
))
1821 if (dt
!= vect_internal_def
1822 && dt
!= vect_constant_def
1823 && dt
!= vect_external_def
)
1826 vectype
= get_vectype_for_scalar_type (type
);
1827 if (vectype
== NULL_TREE
)
1830 /* If vector/vector or vector/scalar rotate is supported by the target,
1831 don't do anything here. */
1832 optab1
= optab_for_tree_code (rhs_code
, vectype
, optab_vector
);
1834 && optab_handler (optab1
, TYPE_MODE (vectype
)) != CODE_FOR_nothing
)
1837 if (is_a
<bb_vec_info
> (vinfo
) || dt
!= vect_internal_def
)
1839 optab2
= optab_for_tree_code (rhs_code
, vectype
, optab_scalar
);
1841 && optab_handler (optab2
, TYPE_MODE (vectype
)) != CODE_FOR_nothing
)
1845 /* If vector/vector or vector/scalar shifts aren't supported by the target,
1846 don't do anything here either. */
1847 optab1
= optab_for_tree_code (LSHIFT_EXPR
, vectype
, optab_vector
);
1848 optab2
= optab_for_tree_code (RSHIFT_EXPR
, vectype
, optab_vector
);
1850 || optab_handler (optab1
, TYPE_MODE (vectype
)) == CODE_FOR_nothing
1852 || optab_handler (optab2
, TYPE_MODE (vectype
)) == CODE_FOR_nothing
)
1854 if (! is_a
<bb_vec_info
> (vinfo
) && dt
== vect_internal_def
)
1856 optab1
= optab_for_tree_code (LSHIFT_EXPR
, vectype
, optab_scalar
);
1857 optab2
= optab_for_tree_code (RSHIFT_EXPR
, vectype
, optab_scalar
);
1859 || optab_handler (optab1
, TYPE_MODE (vectype
)) == CODE_FOR_nothing
1861 || optab_handler (optab2
, TYPE_MODE (vectype
)) == CODE_FOR_nothing
)
1866 *type_out
= vectype
;
1867 if (*type_in
== NULL_TREE
)
1870 if (dt
== vect_external_def
1871 && TREE_CODE (oprnd1
) == SSA_NAME
1872 && is_a
<loop_vec_info
> (vinfo
))
1874 struct loop
*loop
= as_a
<loop_vec_info
> (vinfo
)->loop
;
1875 ext_def
= loop_preheader_edge (loop
);
1876 if (!SSA_NAME_IS_DEFAULT_DEF (oprnd1
))
1878 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (oprnd1
));
1880 || !dominated_by_p (CDI_DOMINATORS
, ext_def
->dest
, bb
))
1886 if (TREE_CODE (oprnd1
) == INTEGER_CST
1887 || TYPE_MODE (TREE_TYPE (oprnd1
)) == TYPE_MODE (type
))
1889 else if (def_stmt
&& gimple_assign_cast_p (def_stmt
))
1891 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1892 if (TYPE_MODE (TREE_TYPE (rhs1
)) == TYPE_MODE (type
)
1893 && TYPE_PRECISION (TREE_TYPE (rhs1
))
1894 == TYPE_PRECISION (type
))
1898 STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo
) = NULL
;
1899 if (def
== NULL_TREE
)
1901 def
= vect_recog_temp_ssa_var (type
, NULL
);
1902 def_stmt
= gimple_build_assign (def
, NOP_EXPR
, oprnd1
);
1906 = gsi_insert_on_edge_immediate (ext_def
, def_stmt
);
1907 gcc_assert (!new_bb
);
1910 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
1912 stype
= TREE_TYPE (def
);
1914 if (TREE_CODE (def
) == INTEGER_CST
)
1916 if (!tree_fits_uhwi_p (def
)
1917 || tree_to_uhwi (def
) >= GET_MODE_PRECISION (TYPE_MODE (type
))
1918 || integer_zerop (def
))
1920 def2
= build_int_cst (stype
,
1921 GET_MODE_PRECISION (TYPE_MODE (type
))
1922 - tree_to_uhwi (def
));
1926 tree vecstype
= get_vectype_for_scalar_type (stype
);
1927 stmt_vec_info def_stmt_vinfo
;
1929 if (vecstype
== NULL_TREE
)
1931 def2
= vect_recog_temp_ssa_var (stype
, NULL
);
1932 def_stmt
= gimple_build_assign (def2
, NEGATE_EXPR
, def
);
1936 = gsi_insert_on_edge_immediate (ext_def
, def_stmt
);
1937 gcc_assert (!new_bb
);
1941 def_stmt_vinfo
= new_stmt_vec_info (def_stmt
, vinfo
);
1942 set_vinfo_for_stmt (def_stmt
, def_stmt_vinfo
);
1943 STMT_VINFO_VECTYPE (def_stmt_vinfo
) = vecstype
;
1944 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
1947 def2
= vect_recog_temp_ssa_var (stype
, NULL
);
1949 = build_int_cst (stype
, GET_MODE_PRECISION (TYPE_MODE (stype
)) - 1);
1950 def_stmt
= gimple_build_assign (def2
, BIT_AND_EXPR
,
1951 gimple_assign_lhs (def_stmt
), mask
);
1955 = gsi_insert_on_edge_immediate (ext_def
, def_stmt
);
1956 gcc_assert (!new_bb
);
1960 def_stmt_vinfo
= new_stmt_vec_info (def_stmt
, vinfo
);
1961 set_vinfo_for_stmt (def_stmt
, def_stmt_vinfo
);
1962 STMT_VINFO_VECTYPE (def_stmt_vinfo
) = vecstype
;
1963 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
1967 var1
= vect_recog_temp_ssa_var (type
, NULL
);
1968 def_stmt
= gimple_build_assign (var1
, rhs_code
== LROTATE_EXPR
1969 ? LSHIFT_EXPR
: RSHIFT_EXPR
,
1971 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
1973 var2
= vect_recog_temp_ssa_var (type
, NULL
);
1974 def_stmt
= gimple_build_assign (var2
, rhs_code
== LROTATE_EXPR
1975 ? RSHIFT_EXPR
: LSHIFT_EXPR
,
1977 append_pattern_def_seq (stmt_vinfo
, def_stmt
);
1979 /* Pattern detected. */
1980 if (dump_enabled_p ())
1981 dump_printf_loc (MSG_NOTE
, vect_location
,
1982 "vect_recog_rotate_pattern: detected:\n");
1984 /* Pattern supported. Create a stmt to be used to replace the pattern. */
1985 var
= vect_recog_temp_ssa_var (type
, NULL
);
1986 pattern_stmt
= gimple_build_assign (var
, BIT_IOR_EXPR
, var1
, var2
);
1988 if (dump_enabled_p ())
1989 dump_gimple_stmt_loc (MSG_NOTE
, vect_location
, TDF_SLIM
, pattern_stmt
, 0);
1991 stmts
->safe_push (last_stmt
);
1992 return pattern_stmt
;
1995 /* Detect a vector by vector shift pattern that wouldn't be otherwise
2003 S3 res_T = b_T op a_t;
2005 where type 'TYPE' is a type with different size than 'type',
2006 and op is <<, >> or rotate.
2011 TYPE b_T, c_T, res_T;
2014 S1 a_t = (type) c_T;
2016 S3 res_T = b_T op a_t;
2020 * STMTS: Contains a stmt from which the pattern search begins,
2021 i.e. the shift/rotate stmt. The original stmt (S3) is replaced
2022 with a shift/rotate which has same type on both operands, in the
2023 second case just b_T op c_T, in the first case with added cast
2024 from a_t to c_T in STMT_VINFO_PATTERN_DEF_SEQ.
2028 * TYPE_IN: The type of the input arguments to the pattern.
2030 * TYPE_OUT: The type of the output of this pattern.
2032 * Return value: A new stmt that will be used to replace the shift/rotate
2036 vect_recog_vector_vector_shift_pattern (vec
<gimple
*> *stmts
,
2037 tree
*type_in
, tree
*type_out
)
2039 gimple
*last_stmt
= stmts
->pop ();
2040 tree oprnd0
, oprnd1
, lhs
, var
;
2041 gimple
*pattern_stmt
, *def_stmt
;
2042 enum tree_code rhs_code
;
2043 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
2044 vec_info
*vinfo
= stmt_vinfo
->vinfo
;
2045 enum vect_def_type dt
;
2047 if (!is_gimple_assign (last_stmt
))
2050 rhs_code
= gimple_assign_rhs_code (last_stmt
);
2062 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
))
2065 lhs
= gimple_assign_lhs (last_stmt
);
2066 oprnd0
= gimple_assign_rhs1 (last_stmt
);
2067 oprnd1
= gimple_assign_rhs2 (last_stmt
);
2068 if (TREE_CODE (oprnd0
) != SSA_NAME
2069 || TREE_CODE (oprnd1
) != SSA_NAME
2070 || TYPE_MODE (TREE_TYPE (oprnd0
)) == TYPE_MODE (TREE_TYPE (oprnd1
))
2071 || !type_has_mode_precision_p (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_has_mode_precision_p (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_has_mode_precision_p (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
>= (HOST_WIDE_INT_1U
<< (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
= ctz_or_zero (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
== HOST_WIDE_INT_1U
<< (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
>= HOST_WIDE_INT_1U
<< (prec
- 1))
2864 ml
|= HOST_WIDE_INT_M1U
<< (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
, TREE_CODE (cond_expr
)))
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
, TREE_CODE (cond_expr
)))
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 (!VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (rhs1
)))
3163 if (! check_bool_pattern (rhs1
, vinfo
, stmts
))
3168 if (! check_bool_pattern (rhs1
, vinfo
, stmts
))
3175 if (! check_bool_pattern (rhs1
, vinfo
, stmts
)
3176 || ! check_bool_pattern (gimple_assign_rhs2 (def_stmt
), vinfo
, stmts
))
3181 if (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
)
3183 tree vecitype
, comp_vectype
;
3185 /* If the comparison can throw, then is_gimple_condexpr will be
3186 false and we can't make a COND_EXPR/VEC_COND_EXPR out of it. */
3187 if (stmt_could_throw_p (def_stmt
))
3190 comp_vectype
= get_vectype_for_scalar_type (TREE_TYPE (rhs1
));
3191 if (comp_vectype
== NULL_TREE
)
3194 tree mask_type
= get_mask_type_for_scalar_type (TREE_TYPE (rhs1
));
3196 && expand_vec_cmp_expr_p (comp_vectype
, mask_type
, rhs_code
))
3199 if (TREE_CODE (TREE_TYPE (rhs1
)) != INTEGER_TYPE
)
3201 machine_mode mode
= TYPE_MODE (TREE_TYPE (rhs1
));
3203 = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode
), 1);
3204 vecitype
= get_vectype_for_scalar_type (itype
);
3205 if (vecitype
== NULL_TREE
)
3209 vecitype
= comp_vectype
;
3210 if (! expand_vec_cond_expr_p (vecitype
, comp_vectype
, rhs_code
))
3218 bool res
= stmts
.add (def_stmt
);
3219 /* We can't end up recursing when just visiting SSA defs but not PHIs. */
3226 /* Helper function of adjust_bool_pattern. Add a cast to TYPE to a previous
3227 stmt (SSA_NAME_DEF_STMT of VAR) adding a cast to STMT_INFOs
3228 pattern sequence. */
3231 adjust_bool_pattern_cast (tree type
, tree var
, stmt_vec_info stmt_info
)
3233 gimple
*cast_stmt
= gimple_build_assign (vect_recog_temp_ssa_var (type
, NULL
),
3235 stmt_vec_info patt_vinfo
= new_stmt_vec_info (cast_stmt
, stmt_info
->vinfo
);
3236 set_vinfo_for_stmt (cast_stmt
, patt_vinfo
);
3237 STMT_VINFO_VECTYPE (patt_vinfo
) = get_vectype_for_scalar_type (type
);
3238 append_pattern_def_seq (stmt_info
, cast_stmt
);
3239 return gimple_assign_lhs (cast_stmt
);
3242 /* Helper function of vect_recog_bool_pattern. Do the actual transformations.
3243 VAR is an SSA_NAME that should be transformed from bool to a wider integer
3244 type, OUT_TYPE is the desired final integer type of the whole pattern.
3245 STMT_INFO is the info of the pattern root and is where pattern stmts should
3246 be associated with. DEFS is a map of pattern defs. */
3249 adjust_bool_pattern (tree var
, tree out_type
,
3250 stmt_vec_info stmt_info
, hash_map
<tree
, tree
> &defs
)
3252 gimple
*stmt
= SSA_NAME_DEF_STMT (var
);
3253 enum tree_code rhs_code
, def_rhs_code
;
3254 tree itype
, cond_expr
, rhs1
, rhs2
, irhs1
, irhs2
;
3256 gimple
*pattern_stmt
, *def_stmt
;
3257 tree trueval
= NULL_TREE
;
3259 rhs1
= gimple_assign_rhs1 (stmt
);
3260 rhs2
= gimple_assign_rhs2 (stmt
);
3261 rhs_code
= gimple_assign_rhs_code (stmt
);
3262 loc
= gimple_location (stmt
);
3267 irhs1
= *defs
.get (rhs1
);
3268 itype
= TREE_TYPE (irhs1
);
3270 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
3275 irhs1
= *defs
.get (rhs1
);
3276 itype
= TREE_TYPE (irhs1
);
3278 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
3279 BIT_XOR_EXPR
, irhs1
, build_int_cst (itype
, 1));
3283 /* Try to optimize x = y & (a < b ? 1 : 0); into
3284 x = (a < b ? y : 0);
3290 S1 a_b = x1 CMP1 y1;
3291 S2 b_b = x2 CMP2 y2;
3293 S4 d_T = (TYPE) c_b;
3295 we would normally emit:
3297 S1' a_T = x1 CMP1 y1 ? 1 : 0;
3298 S2' b_T = x2 CMP2 y2 ? 1 : 0;
3299 S3' c_T = a_T & b_T;
3302 but we can save one stmt by using the
3303 result of one of the COND_EXPRs in the other COND_EXPR and leave
3304 BIT_AND_EXPR stmt out:
3306 S1' a_T = x1 CMP1 y1 ? 1 : 0;
3307 S3' c_T = x2 CMP2 y2 ? a_T : 0;
3310 At least when VEC_COND_EXPR is implemented using masks
3311 cond ? 1 : 0 is as expensive as cond ? var : 0, in both cases it
3312 computes the comparison masks and ands it, in one case with
3313 all ones vector, in the other case with a vector register.
3314 Don't do this for BIT_IOR_EXPR, because cond ? 1 : var; is
3315 often more expensive. */
3316 def_stmt
= SSA_NAME_DEF_STMT (rhs2
);
3317 def_rhs_code
= gimple_assign_rhs_code (def_stmt
);
3318 if (TREE_CODE_CLASS (def_rhs_code
) == tcc_comparison
)
3320 irhs1
= *defs
.get (rhs1
);
3321 tree def_rhs1
= gimple_assign_rhs1 (def_stmt
);
3322 if (TYPE_PRECISION (TREE_TYPE (irhs1
))
3323 == GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (def_rhs1
))))
3325 rhs_code
= def_rhs_code
;
3327 rhs2
= gimple_assign_rhs2 (def_stmt
);
3332 irhs2
= *defs
.get (rhs2
);
3335 def_stmt
= SSA_NAME_DEF_STMT (rhs1
);
3336 def_rhs_code
= gimple_assign_rhs_code (def_stmt
);
3337 if (TREE_CODE_CLASS (def_rhs_code
) == tcc_comparison
)
3339 irhs2
= *defs
.get (rhs2
);
3340 tree def_rhs1
= gimple_assign_rhs1 (def_stmt
);
3341 if (TYPE_PRECISION (TREE_TYPE (irhs2
))
3342 == GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (def_rhs1
))))
3344 rhs_code
= def_rhs_code
;
3346 rhs2
= gimple_assign_rhs2 (def_stmt
);
3351 irhs1
= *defs
.get (rhs1
);
3357 irhs1
= *defs
.get (rhs1
);
3358 irhs2
= *defs
.get (rhs2
);
3360 if (TYPE_PRECISION (TREE_TYPE (irhs1
))
3361 != TYPE_PRECISION (TREE_TYPE (irhs2
)))
3363 int prec1
= TYPE_PRECISION (TREE_TYPE (irhs1
));
3364 int prec2
= TYPE_PRECISION (TREE_TYPE (irhs2
));
3365 int out_prec
= TYPE_PRECISION (out_type
);
3366 if (absu_hwi (out_prec
- prec1
) < absu_hwi (out_prec
- prec2
))
3367 irhs2
= adjust_bool_pattern_cast (TREE_TYPE (irhs1
), irhs2
,
3369 else if (absu_hwi (out_prec
- prec1
) > absu_hwi (out_prec
- prec2
))
3370 irhs1
= adjust_bool_pattern_cast (TREE_TYPE (irhs2
), irhs1
,
3374 irhs1
= adjust_bool_pattern_cast (out_type
, irhs1
, stmt_info
);
3375 irhs2
= adjust_bool_pattern_cast (out_type
, irhs2
, stmt_info
);
3378 itype
= TREE_TYPE (irhs1
);
3380 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
3381 rhs_code
, irhs1
, irhs2
);
3386 gcc_assert (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
);
3387 if (TREE_CODE (TREE_TYPE (rhs1
)) != INTEGER_TYPE
3388 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
))
3389 || (TYPE_PRECISION (TREE_TYPE (rhs1
))
3390 != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1
)))))
3392 machine_mode mode
= TYPE_MODE (TREE_TYPE (rhs1
));
3394 = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode
), 1);
3397 itype
= TREE_TYPE (rhs1
);
3398 cond_expr
= build2_loc (loc
, rhs_code
, itype
, rhs1
, rhs2
);
3399 if (trueval
== NULL_TREE
)
3400 trueval
= build_int_cst (itype
, 1);
3402 gcc_checking_assert (useless_type_conversion_p (itype
,
3403 TREE_TYPE (trueval
)));
3405 = gimple_build_assign (vect_recog_temp_ssa_var (itype
, NULL
),
3406 COND_EXPR
, cond_expr
, trueval
,
3407 build_int_cst (itype
, 0));
3411 gimple_set_location (pattern_stmt
, loc
);
3412 /* ??? Why does vect_mark_pattern_stmts set the vector type on all
3413 pattern def seq stmts instead of just letting auto-detection do
3415 stmt_vec_info patt_vinfo
= new_stmt_vec_info (pattern_stmt
, stmt_info
->vinfo
);
3416 set_vinfo_for_stmt (pattern_stmt
, patt_vinfo
);
3417 STMT_VINFO_VECTYPE (patt_vinfo
) = get_vectype_for_scalar_type (itype
);
3418 append_pattern_def_seq (stmt_info
, pattern_stmt
);
3419 defs
.put (var
, gimple_assign_lhs (pattern_stmt
));
3422 /* Comparison function to qsort a vector of gimple stmts after UID. */
3425 sort_after_uid (const void *p1
, const void *p2
)
3427 const gimple
*stmt1
= *(const gimple
* const *)p1
;
3428 const gimple
*stmt2
= *(const gimple
* const *)p2
;
3429 return gimple_uid (stmt1
) - gimple_uid (stmt2
);
3432 /* Create pattern stmts for all stmts participating in the bool pattern
3433 specified by BOOL_STMT_SET and its root STMT with the desired type
3434 OUT_TYPE. Return the def of the pattern root. */
3437 adjust_bool_stmts (hash_set
<gimple
*> &bool_stmt_set
,
3438 tree out_type
, gimple
*stmt
)
3440 /* Gather original stmts in the bool pattern in their order of appearance
3442 auto_vec
<gimple
*> bool_stmts (bool_stmt_set
.elements ());
3443 for (hash_set
<gimple
*>::iterator i
= bool_stmt_set
.begin ();
3444 i
!= bool_stmt_set
.end (); ++i
)
3445 bool_stmts
.quick_push (*i
);
3446 bool_stmts
.qsort (sort_after_uid
);
3448 /* Now process them in that order, producing pattern stmts. */
3449 hash_map
<tree
, tree
> defs
;
3450 for (unsigned i
= 0; i
< bool_stmts
.length (); ++i
)
3451 adjust_bool_pattern (gimple_assign_lhs (bool_stmts
[i
]),
3452 out_type
, vinfo_for_stmt (stmt
), defs
);
3454 /* Pop the last pattern seq stmt and install it as pattern root for STMT. */
3455 gimple
*pattern_stmt
3456 = gimple_seq_last_stmt (STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (stmt
)));
3457 return gimple_assign_lhs (pattern_stmt
);
3460 /* Helper for search_type_for_mask. */
3463 search_type_for_mask_1 (tree var
, vec_info
*vinfo
,
3464 hash_map
<gimple
*, tree
> &cache
)
3467 enum vect_def_type dt
;
3469 enum tree_code rhs_code
;
3470 tree res
= NULL_TREE
, res2
;
3472 if (TREE_CODE (var
) != SSA_NAME
)
3475 if (!VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (var
)))
3478 if (!vect_is_simple_use (var
, vinfo
, &def_stmt
, &dt
))
3481 if (dt
!= vect_internal_def
)
3484 if (!is_gimple_assign (def_stmt
))
3487 tree
*c
= cache
.get (def_stmt
);
3491 rhs_code
= gimple_assign_rhs_code (def_stmt
);
3492 rhs1
= gimple_assign_rhs1 (def_stmt
);
3499 res
= search_type_for_mask_1 (rhs1
, vinfo
, cache
);
3505 res
= search_type_for_mask_1 (rhs1
, vinfo
, cache
);
3506 res2
= search_type_for_mask_1 (gimple_assign_rhs2 (def_stmt
), vinfo
,
3508 if (!res
|| (res2
&& TYPE_PRECISION (res
) > TYPE_PRECISION (res2
)))
3513 if (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
)
3515 tree comp_vectype
, mask_type
;
3517 if (VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (rhs1
)))
3519 res
= search_type_for_mask_1 (rhs1
, vinfo
, cache
);
3520 res2
= search_type_for_mask_1 (gimple_assign_rhs2 (def_stmt
),
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
)
3534 mask_type
= get_mask_type_for_scalar_type (TREE_TYPE (rhs1
));
3536 || !expand_vec_cmp_expr_p (comp_vectype
, mask_type
, rhs_code
))
3542 if (TREE_CODE (TREE_TYPE (rhs1
)) != INTEGER_TYPE
3543 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
3545 machine_mode mode
= TYPE_MODE (TREE_TYPE (rhs1
));
3546 res
= build_nonstandard_integer_type (GET_MODE_BITSIZE (mode
), 1);
3549 res
= TREE_TYPE (rhs1
);
3553 cache
.put (def_stmt
, res
);
3557 /* Return the proper type for converting bool VAR into
3558 an integer value or NULL_TREE if no such type exists.
3559 The type is chosen so that converted value has the
3560 same number of elements as VAR's vector type. */
3563 search_type_for_mask (tree var
, vec_info
*vinfo
)
3565 hash_map
<gimple
*, tree
> cache
;
3566 return search_type_for_mask_1 (var
, vinfo
, cache
);
3569 /* Function vect_recog_bool_pattern
3571 Try to find pattern like following:
3573 bool a_b, b_b, c_b, d_b, e_b;
3576 S1 a_b = x1 CMP1 y1;
3577 S2 b_b = x2 CMP2 y2;
3579 S4 d_b = x3 CMP3 y3;
3581 S6 f_T = (TYPE) e_b;
3583 where type 'TYPE' is an integral type. Or a similar pattern
3586 S6 f_Y = e_b ? r_Y : s_Y;
3588 as results from if-conversion of a complex condition.
3592 * LAST_STMT: A stmt at the end from which the pattern
3593 search begins, i.e. cast of a bool to
3598 * TYPE_IN: The type of the input arguments to the pattern.
3600 * TYPE_OUT: The type of the output of this pattern.
3602 * Return value: A new stmt that will be used to replace the pattern.
3604 Assuming size of TYPE is the same as size of all comparisons
3605 (otherwise some casts would be added where needed), the above
3606 sequence we create related pattern stmts:
3607 S1' a_T = x1 CMP1 y1 ? 1 : 0;
3608 S3' c_T = x2 CMP2 y2 ? a_T : 0;
3609 S4' d_T = x3 CMP3 y3 ? 1 : 0;
3610 S5' e_T = c_T | d_T;
3613 Instead of the above S3' we could emit:
3614 S2' b_T = x2 CMP2 y2 ? 1 : 0;
3615 S3' c_T = a_T | b_T;
3616 but the above is more efficient. */
3619 vect_recog_bool_pattern (vec
<gimple
*> *stmts
, tree
*type_in
,
3622 gimple
*last_stmt
= stmts
->pop ();
3623 enum tree_code rhs_code
;
3624 tree var
, lhs
, rhs
, vectype
;
3625 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
3626 stmt_vec_info new_stmt_info
;
3627 vec_info
*vinfo
= stmt_vinfo
->vinfo
;
3628 gimple
*pattern_stmt
;
3630 if (!is_gimple_assign (last_stmt
))
3633 var
= gimple_assign_rhs1 (last_stmt
);
3634 lhs
= gimple_assign_lhs (last_stmt
);
3636 if (!VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (var
)))
3639 hash_set
<gimple
*> bool_stmts
;
3641 rhs_code
= gimple_assign_rhs_code (last_stmt
);
3642 if (CONVERT_EXPR_CODE_P (rhs_code
))
3644 if (TREE_CODE (TREE_TYPE (lhs
)) != INTEGER_TYPE
3645 || TYPE_PRECISION (TREE_TYPE (lhs
)) == 1)
3647 vectype
= get_vectype_for_scalar_type (TREE_TYPE (lhs
));
3648 if (vectype
== NULL_TREE
)
3651 if (check_bool_pattern (var
, vinfo
, bool_stmts
))
3653 rhs
= adjust_bool_stmts (bool_stmts
, TREE_TYPE (lhs
), last_stmt
);
3654 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3655 if (useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
3656 pattern_stmt
= gimple_build_assign (lhs
, SSA_NAME
, rhs
);
3659 = gimple_build_assign (lhs
, NOP_EXPR
, rhs
);
3663 tree type
= search_type_for_mask (var
, vinfo
);
3664 tree cst0
, cst1
, tmp
;
3669 /* We may directly use cond with narrowed type to avoid
3670 multiple cond exprs with following result packing and
3671 perform single cond with packed mask instead. In case
3672 of widening we better make cond first and then extract
3674 if (TYPE_MODE (type
) == TYPE_MODE (TREE_TYPE (lhs
)))
3675 type
= TREE_TYPE (lhs
);
3677 cst0
= build_int_cst (type
, 0);
3678 cst1
= build_int_cst (type
, 1);
3679 tmp
= vect_recog_temp_ssa_var (type
, NULL
);
3680 pattern_stmt
= gimple_build_assign (tmp
, COND_EXPR
, var
, cst1
, cst0
);
3682 if (!useless_type_conversion_p (type
, TREE_TYPE (lhs
)))
3684 tree new_vectype
= get_vectype_for_scalar_type (type
);
3685 new_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
3686 set_vinfo_for_stmt (pattern_stmt
, new_stmt_info
);
3687 STMT_VINFO_VECTYPE (new_stmt_info
) = new_vectype
;
3688 new_pattern_def_seq (stmt_vinfo
, pattern_stmt
);
3690 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3691 pattern_stmt
= gimple_build_assign (lhs
, CONVERT_EXPR
, tmp
);
3695 *type_out
= vectype
;
3697 stmts
->safe_push (last_stmt
);
3698 if (dump_enabled_p ())
3699 dump_printf_loc (MSG_NOTE
, vect_location
,
3700 "vect_recog_bool_pattern: detected:\n");
3702 return pattern_stmt
;
3704 else if (rhs_code
== COND_EXPR
3705 && TREE_CODE (var
) == SSA_NAME
)
3707 vectype
= get_vectype_for_scalar_type (TREE_TYPE (lhs
));
3708 if (vectype
== NULL_TREE
)
3711 /* Build a scalar type for the boolean result that when
3712 vectorized matches the vector type of the result in
3713 size and number of elements. */
3715 = wi::udiv_trunc (TYPE_SIZE (vectype
),
3716 TYPE_VECTOR_SUBPARTS (vectype
)).to_uhwi ();
3718 = build_nonstandard_integer_type (prec
,
3719 TYPE_UNSIGNED (TREE_TYPE (var
)));
3720 if (get_vectype_for_scalar_type (type
) == NULL_TREE
)
3723 if (!check_bool_pattern (var
, vinfo
, bool_stmts
))
3726 rhs
= adjust_bool_stmts (bool_stmts
, type
, last_stmt
);
3728 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3730 = gimple_build_assign (lhs
, COND_EXPR
,
3731 build2 (NE_EXPR
, boolean_type_node
,
3732 rhs
, build_int_cst (type
, 0)),
3733 gimple_assign_rhs2 (last_stmt
),
3734 gimple_assign_rhs3 (last_stmt
));
3735 *type_out
= vectype
;
3737 stmts
->safe_push (last_stmt
);
3738 if (dump_enabled_p ())
3739 dump_printf_loc (MSG_NOTE
, vect_location
,
3740 "vect_recog_bool_pattern: detected:\n");
3742 return pattern_stmt
;
3744 else if (rhs_code
== SSA_NAME
3745 && STMT_VINFO_DATA_REF (stmt_vinfo
))
3747 stmt_vec_info pattern_stmt_info
;
3748 vectype
= STMT_VINFO_VECTYPE (stmt_vinfo
);
3749 gcc_assert (vectype
!= NULL_TREE
);
3750 if (!VECTOR_MODE_P (TYPE_MODE (vectype
)))
3753 if (check_bool_pattern (var
, vinfo
, bool_stmts
))
3754 rhs
= adjust_bool_stmts (bool_stmts
, TREE_TYPE (vectype
), last_stmt
);
3757 tree type
= search_type_for_mask (var
, vinfo
);
3758 tree cst0
, cst1
, new_vectype
;
3763 if (TYPE_MODE (type
) == TYPE_MODE (TREE_TYPE (vectype
)))
3764 type
= TREE_TYPE (vectype
);
3766 cst0
= build_int_cst (type
, 0);
3767 cst1
= build_int_cst (type
, 1);
3768 new_vectype
= get_vectype_for_scalar_type (type
);
3770 rhs
= vect_recog_temp_ssa_var (type
, NULL
);
3771 pattern_stmt
= gimple_build_assign (rhs
, COND_EXPR
, var
, cst1
, cst0
);
3773 pattern_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
3774 set_vinfo_for_stmt (pattern_stmt
, pattern_stmt_info
);
3775 STMT_VINFO_VECTYPE (pattern_stmt_info
) = new_vectype
;
3776 append_pattern_def_seq (stmt_vinfo
, pattern_stmt
);
3779 lhs
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (vectype
), lhs
);
3780 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
3782 tree rhs2
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3783 gimple
*cast_stmt
= gimple_build_assign (rhs2
, NOP_EXPR
, rhs
);
3784 append_pattern_def_seq (stmt_vinfo
, cast_stmt
);
3787 pattern_stmt
= gimple_build_assign (lhs
, SSA_NAME
, rhs
);
3788 pattern_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
3789 set_vinfo_for_stmt (pattern_stmt
, pattern_stmt_info
);
3790 STMT_VINFO_DATA_REF (pattern_stmt_info
)
3791 = STMT_VINFO_DATA_REF (stmt_vinfo
);
3792 STMT_VINFO_DR_WRT_VEC_LOOP (pattern_stmt_info
)
3793 = STMT_VINFO_DR_WRT_VEC_LOOP (stmt_vinfo
);
3794 DR_STMT (STMT_VINFO_DATA_REF (stmt_vinfo
)) = pattern_stmt
;
3795 *type_out
= vectype
;
3797 stmts
->safe_push (last_stmt
);
3798 if (dump_enabled_p ())
3799 dump_printf_loc (MSG_NOTE
, vect_location
,
3800 "vect_recog_bool_pattern: detected:\n");
3801 return pattern_stmt
;
3808 /* A helper for vect_recog_mask_conversion_pattern. Build
3809 conversion of MASK to a type suitable for masking VECTYPE.
3810 Built statement gets required vectype and is appended to
3811 a pattern sequence of STMT_VINFO.
3813 Return converted mask. */
3816 build_mask_conversion (tree mask
, tree vectype
, stmt_vec_info stmt_vinfo
,
3821 stmt_vec_info new_stmt_info
;
3823 masktype
= build_same_sized_truth_vector_type (vectype
);
3824 tmp
= vect_recog_temp_ssa_var (TREE_TYPE (masktype
), NULL
);
3825 stmt
= gimple_build_assign (tmp
, CONVERT_EXPR
, mask
);
3826 new_stmt_info
= new_stmt_vec_info (stmt
, vinfo
);
3827 set_vinfo_for_stmt (stmt
, new_stmt_info
);
3828 STMT_VINFO_VECTYPE (new_stmt_info
) = masktype
;
3829 append_pattern_def_seq (stmt_vinfo
, stmt
);
3835 /* Function vect_recog_mask_conversion_pattern
3837 Try to find statements which require boolean type
3838 converison. Additional conversion statements are
3839 added to handle such cases. For example:
3849 S4 c_1 = m_3 ? c_2 : c_3;
3851 Will be transformed into:
3855 S3'' m_2' = (_Bool[bitsize=32])m_2
3856 S3' m_3' = m_1 & m_2';
3857 S4'' m_3'' = (_Bool[bitsize=8])m_3'
3858 S4' c_1' = m_3'' ? c_2 : c_3; */
3861 vect_recog_mask_conversion_pattern (vec
<gimple
*> *stmts
, tree
*type_in
,
3864 gimple
*last_stmt
= stmts
->pop ();
3865 enum tree_code rhs_code
;
3866 tree lhs
= NULL_TREE
, rhs1
, rhs2
, tmp
, rhs1_type
, rhs2_type
;
3867 tree vectype1
, vectype2
;
3868 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (last_stmt
);
3869 stmt_vec_info pattern_stmt_info
;
3870 vec_info
*vinfo
= stmt_vinfo
->vinfo
;
3872 /* Check for MASK_LOAD ans MASK_STORE calls requiring mask conversion. */
3873 if (is_gimple_call (last_stmt
)
3874 && gimple_call_internal_p (last_stmt
)
3875 && (gimple_call_internal_fn (last_stmt
) == IFN_MASK_STORE
3876 || gimple_call_internal_fn (last_stmt
) == IFN_MASK_LOAD
))
3878 gcall
*pattern_stmt
;
3879 bool load
= (gimple_call_internal_fn (last_stmt
) == IFN_MASK_LOAD
);
3883 lhs
= gimple_call_lhs (last_stmt
);
3884 vectype1
= get_vectype_for_scalar_type (TREE_TYPE (lhs
));
3888 rhs2
= gimple_call_arg (last_stmt
, 3);
3889 vectype1
= get_vectype_for_scalar_type (TREE_TYPE (rhs2
));
3892 rhs1
= gimple_call_arg (last_stmt
, 2);
3893 rhs1_type
= search_type_for_mask (rhs1
, vinfo
);
3896 vectype2
= get_mask_type_for_scalar_type (rhs1_type
);
3898 if (!vectype1
|| !vectype2
3899 || TYPE_VECTOR_SUBPARTS (vectype1
) == TYPE_VECTOR_SUBPARTS (vectype2
))
3902 tmp
= build_mask_conversion (rhs1
, vectype1
, stmt_vinfo
, vinfo
);
3906 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3908 = gimple_build_call_internal (IFN_MASK_LOAD
, 3,
3909 gimple_call_arg (last_stmt
, 0),
3910 gimple_call_arg (last_stmt
, 1),
3912 gimple_call_set_lhs (pattern_stmt
, lhs
);
3916 = gimple_build_call_internal (IFN_MASK_STORE
, 4,
3917 gimple_call_arg (last_stmt
, 0),
3918 gimple_call_arg (last_stmt
, 1),
3920 gimple_call_arg (last_stmt
, 3));
3922 gimple_call_set_nothrow (pattern_stmt
, true);
3924 pattern_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
3925 set_vinfo_for_stmt (pattern_stmt
, pattern_stmt_info
);
3926 STMT_VINFO_DATA_REF (pattern_stmt_info
)
3927 = STMT_VINFO_DATA_REF (stmt_vinfo
);
3928 STMT_VINFO_DR_WRT_VEC_LOOP (pattern_stmt_info
)
3929 = STMT_VINFO_DR_WRT_VEC_LOOP (stmt_vinfo
);
3930 DR_STMT (STMT_VINFO_DATA_REF (stmt_vinfo
)) = pattern_stmt
;
3932 *type_out
= vectype1
;
3933 *type_in
= vectype1
;
3934 stmts
->safe_push (last_stmt
);
3935 if (dump_enabled_p ())
3936 dump_printf_loc (MSG_NOTE
, vect_location
,
3937 "vect_recog_mask_conversion_pattern: detected:\n");
3939 return pattern_stmt
;
3942 if (!is_gimple_assign (last_stmt
))
3945 gimple
*pattern_stmt
;
3946 lhs
= gimple_assign_lhs (last_stmt
);
3947 rhs1
= gimple_assign_rhs1 (last_stmt
);
3948 rhs_code
= gimple_assign_rhs_code (last_stmt
);
3950 /* Check for cond expression requiring mask conversion. */
3951 if (rhs_code
== COND_EXPR
)
3953 /* vect_recog_mixed_size_cond_pattern could apply.
3955 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
))
3958 vectype1
= get_vectype_for_scalar_type (TREE_TYPE (lhs
));
3960 if (TREE_CODE (rhs1
) == SSA_NAME
)
3962 rhs1_type
= search_type_for_mask (rhs1
, vinfo
);
3966 else if (COMPARISON_CLASS_P (rhs1
))
3967 rhs1_type
= TREE_TYPE (TREE_OPERAND (rhs1
, 0));
3971 vectype2
= get_mask_type_for_scalar_type (rhs1_type
);
3973 if (!vectype1
|| !vectype2
3974 || TYPE_VECTOR_SUBPARTS (vectype1
) == TYPE_VECTOR_SUBPARTS (vectype2
))
3977 /* If rhs1 is a comparison we need to move it into a
3978 separate statement. */
3979 if (TREE_CODE (rhs1
) != SSA_NAME
)
3981 tmp
= vect_recog_temp_ssa_var (TREE_TYPE (rhs1
), NULL
);
3982 pattern_stmt
= gimple_build_assign (tmp
, rhs1
);
3985 pattern_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
3986 set_vinfo_for_stmt (pattern_stmt
, pattern_stmt_info
);
3987 STMT_VINFO_VECTYPE (pattern_stmt_info
) = vectype2
;
3988 append_pattern_def_seq (stmt_vinfo
, pattern_stmt
);
3991 tmp
= build_mask_conversion (rhs1
, vectype1
, stmt_vinfo
, vinfo
);
3993 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
3994 pattern_stmt
= gimple_build_assign (lhs
, COND_EXPR
, tmp
,
3995 gimple_assign_rhs2 (last_stmt
),
3996 gimple_assign_rhs3 (last_stmt
));
3998 *type_out
= vectype1
;
3999 *type_in
= vectype1
;
4000 stmts
->safe_push (last_stmt
);
4001 if (dump_enabled_p ())
4002 dump_printf_loc (MSG_NOTE
, vect_location
,
4003 "vect_recog_mask_conversion_pattern: detected:\n");
4005 return pattern_stmt
;
4008 /* Now check for binary boolean operations requiring conversion for
4010 if (!VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (lhs
)))
4013 if (rhs_code
!= BIT_IOR_EXPR
4014 && rhs_code
!= BIT_XOR_EXPR
4015 && rhs_code
!= BIT_AND_EXPR
4016 && TREE_CODE_CLASS (rhs_code
) != tcc_comparison
)
4019 rhs2
= gimple_assign_rhs2 (last_stmt
);
4021 rhs1_type
= search_type_for_mask (rhs1
, vinfo
);
4022 rhs2_type
= search_type_for_mask (rhs2
, vinfo
);
4024 if (!rhs1_type
|| !rhs2_type
4025 || TYPE_PRECISION (rhs1_type
) == TYPE_PRECISION (rhs2_type
))
4028 if (TYPE_PRECISION (rhs1_type
) < TYPE_PRECISION (rhs2_type
))
4030 vectype1
= get_mask_type_for_scalar_type (rhs1_type
);
4033 rhs2
= build_mask_conversion (rhs2
, vectype1
, stmt_vinfo
, vinfo
);
4037 vectype1
= get_mask_type_for_scalar_type (rhs2_type
);
4040 rhs1
= build_mask_conversion (rhs1
, vectype1
, stmt_vinfo
, vinfo
);
4043 lhs
= vect_recog_temp_ssa_var (TREE_TYPE (lhs
), NULL
);
4044 pattern_stmt
= gimple_build_assign (lhs
, rhs_code
, rhs1
, rhs2
);
4046 *type_out
= vectype1
;
4047 *type_in
= vectype1
;
4048 stmts
->safe_push (last_stmt
);
4049 if (dump_enabled_p ())
4050 dump_printf_loc (MSG_NOTE
, vect_location
,
4051 "vect_recog_mask_conversion_pattern: detected:\n");
4053 return pattern_stmt
;
4057 /* Mark statements that are involved in a pattern. */
4060 vect_mark_pattern_stmts (gimple
*orig_stmt
, gimple
*pattern_stmt
,
4061 tree pattern_vectype
)
4063 stmt_vec_info pattern_stmt_info
, def_stmt_info
;
4064 stmt_vec_info orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
4065 vec_info
*vinfo
= orig_stmt_info
->vinfo
;
4068 pattern_stmt_info
= vinfo_for_stmt (pattern_stmt
);
4069 if (pattern_stmt_info
== NULL
)
4071 pattern_stmt_info
= new_stmt_vec_info (pattern_stmt
, vinfo
);
4072 set_vinfo_for_stmt (pattern_stmt
, pattern_stmt_info
);
4074 gimple_set_bb (pattern_stmt
, gimple_bb (orig_stmt
));
4076 STMT_VINFO_RELATED_STMT (pattern_stmt_info
) = orig_stmt
;
4077 STMT_VINFO_DEF_TYPE (pattern_stmt_info
)
4078 = STMT_VINFO_DEF_TYPE (orig_stmt_info
);
4079 STMT_VINFO_VECTYPE (pattern_stmt_info
) = pattern_vectype
;
4080 STMT_VINFO_IN_PATTERN_P (orig_stmt_info
) = true;
4081 STMT_VINFO_RELATED_STMT (orig_stmt_info
) = pattern_stmt
;
4082 STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info
)
4083 = STMT_VINFO_PATTERN_DEF_SEQ (orig_stmt_info
);
4084 if (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info
))
4086 gimple_stmt_iterator si
;
4087 for (si
= gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info
));
4088 !gsi_end_p (si
); gsi_next (&si
))
4090 def_stmt
= gsi_stmt (si
);
4091 def_stmt_info
= vinfo_for_stmt (def_stmt
);
4092 if (def_stmt_info
== NULL
)
4094 def_stmt_info
= new_stmt_vec_info (def_stmt
, vinfo
);
4095 set_vinfo_for_stmt (def_stmt
, def_stmt_info
);
4097 gimple_set_bb (def_stmt
, gimple_bb (orig_stmt
));
4098 STMT_VINFO_RELATED_STMT (def_stmt_info
) = orig_stmt
;
4099 STMT_VINFO_DEF_TYPE (def_stmt_info
) = vect_internal_def
;
4100 if (STMT_VINFO_VECTYPE (def_stmt_info
) == NULL_TREE
)
4101 STMT_VINFO_VECTYPE (def_stmt_info
) = pattern_vectype
;
4106 /* Function vect_pattern_recog_1
4109 PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
4110 computation pattern.
4111 STMT: A stmt from which the pattern search should start.
4113 If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
4114 expression that computes the same functionality and can be used to
4115 replace the sequence of stmts that are involved in the pattern.
4118 This function checks if the expression returned by PATTERN_RECOG_FUNC is
4119 supported in vector form by the target. We use 'TYPE_IN' to obtain the
4120 relevant vector type. If 'TYPE_IN' is already a vector type, then this
4121 indicates that target support had already been checked by PATTERN_RECOG_FUNC.
4122 If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
4123 to the available target pattern.
4125 This function also does some bookkeeping, as explained in the documentation
4126 for vect_recog_pattern. */
4129 vect_pattern_recog_1 (vect_recog_func
*recog_func
,
4130 gimple_stmt_iterator si
,
4131 vec
<gimple
*> *stmts_to_replace
)
4133 gimple
*stmt
= gsi_stmt (si
), *pattern_stmt
;
4134 stmt_vec_info stmt_info
;
4135 loop_vec_info loop_vinfo
;
4136 tree pattern_vectype
;
4137 tree type_in
, type_out
;
4138 enum tree_code code
;
4142 stmts_to_replace
->truncate (0);
4143 stmts_to_replace
->quick_push (stmt
);
4144 pattern_stmt
= recog_func
->fn (stmts_to_replace
, &type_in
, &type_out
);
4148 stmt
= stmts_to_replace
->last ();
4149 stmt_info
= vinfo_for_stmt (stmt
);
4150 loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4152 if (VECTOR_BOOLEAN_TYPE_P (type_in
)
4153 || VECTOR_MODE_P (TYPE_MODE (type_in
)))
4155 /* No need to check target support (already checked by the pattern
4156 recognition function). */
4157 pattern_vectype
= type_out
? type_out
: type_in
;
4161 machine_mode vec_mode
;
4162 enum insn_code icode
;
4165 /* Check target support */
4166 type_in
= get_vectype_for_scalar_type (type_in
);
4170 type_out
= get_vectype_for_scalar_type (type_out
);
4175 pattern_vectype
= type_out
;
4177 if (is_gimple_assign (pattern_stmt
))
4178 code
= gimple_assign_rhs_code (pattern_stmt
);
4181 gcc_assert (is_gimple_call (pattern_stmt
));
4185 optab
= optab_for_tree_code (code
, type_in
, optab_default
);
4186 vec_mode
= TYPE_MODE (type_in
);
4188 || (icode
= optab_handler (optab
, vec_mode
)) == CODE_FOR_nothing
4189 || (insn_data
[icode
].operand
[0].mode
!= TYPE_MODE (type_out
)))
4193 /* Found a vectorizable pattern. */
4194 if (dump_enabled_p ())
4196 dump_printf_loc (MSG_NOTE
, vect_location
,
4197 "%s pattern recognized: ", recog_func
->name
);
4198 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
4201 /* Mark the stmts that are involved in the pattern. */
4202 vect_mark_pattern_stmts (stmt
, pattern_stmt
, pattern_vectype
);
4204 /* Patterns cannot be vectorized using SLP, because they change the order of
4207 FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTIONS (loop_vinfo
), i
, next
)
4209 LOOP_VINFO_REDUCTIONS (loop_vinfo
).ordered_remove (i
);
4211 /* It is possible that additional pattern stmts are created and inserted in
4212 STMTS_TO_REPLACE. We create a stmt_info for each of them, and mark the
4213 relevant statements. */
4214 for (i
= 0; stmts_to_replace
->iterate (i
, &stmt
)
4215 && (unsigned) i
< (stmts_to_replace
->length () - 1);
4218 stmt_info
= vinfo_for_stmt (stmt
);
4219 pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4220 if (dump_enabled_p ())
4222 dump_printf_loc (MSG_NOTE
, vect_location
,
4223 "additional pattern stmt: ");
4224 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, pattern_stmt
, 0);
4227 vect_mark_pattern_stmts (stmt
, pattern_stmt
, NULL_TREE
);
4234 /* Function vect_pattern_recog
4237 LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
4240 Output - for each computation idiom that is detected we create a new stmt
4241 that provides the same functionality and that can be vectorized. We
4242 also record some information in the struct_stmt_info of the relevant
4243 stmts, as explained below:
4245 At the entry to this function we have the following stmts, with the
4246 following initial value in the STMT_VINFO fields:
4248 stmt in_pattern_p related_stmt vec_stmt
4249 S1: a_i = .... - - -
4250 S2: a_2 = ..use(a_i).. - - -
4251 S3: a_1 = ..use(a_2).. - - -
4252 S4: a_0 = ..use(a_1).. - - -
4253 S5: ... = ..use(a_0).. - - -
4255 Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
4256 represented by a single stmt. We then:
4257 - create a new stmt S6 equivalent to the pattern (the stmt is not
4258 inserted into the code)
4259 - fill in the STMT_VINFO fields as follows:
4261 in_pattern_p related_stmt vec_stmt
4262 S1: a_i = .... - - -
4263 S2: a_2 = ..use(a_i).. - - -
4264 S3: a_1 = ..use(a_2).. - - -
4265 S4: a_0 = ..use(a_1).. true S6 -
4266 '---> S6: a_new = .... - S4 -
4267 S5: ... = ..use(a_0).. - - -
4269 (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
4270 to each other through the RELATED_STMT field).
4272 S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
4273 of S4 because it will replace all its uses. Stmts {S1,S2,S3} will
4274 remain irrelevant unless used by stmts other than S4.
4276 If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
4277 (because they are marked as irrelevant). It will vectorize S6, and record
4278 a pointer to the new vector stmt VS6 from S6 (as usual).
4279 S4 will be skipped, and S5 will be vectorized as usual:
4281 in_pattern_p related_stmt vec_stmt
4282 S1: a_i = .... - - -
4283 S2: a_2 = ..use(a_i).. - - -
4284 S3: a_1 = ..use(a_2).. - - -
4285 > VS6: va_new = .... - - -
4286 S4: a_0 = ..use(a_1).. true S6 VS6
4287 '---> S6: a_new = .... - S4 VS6
4288 > VS5: ... = ..vuse(va_new).. - - -
4289 S5: ... = ..use(a_0).. - - -
4291 DCE could then get rid of {S1,S2,S3,S4,S5} (if their defs are not used
4292 elsewhere), and we'll end up with:
4295 VS5: ... = ..vuse(va_new)..
4297 In case of more than one pattern statements, e.g., widen-mult with
4301 S2 a_T = (TYPE) a_t;
4302 '--> S3: a_it = (interm_type) a_t;
4303 S4 prod_T = a_T * CONST;
4304 '--> S5: prod_T' = a_it w* CONST;
4306 there may be other users of a_T outside the pattern. In that case S2 will
4307 be marked as relevant (as well as S3), and both S2 and S3 will be analyzed
4308 and vectorized. The vector stmt VS2 will be recorded in S2, and VS3 will
4309 be recorded in S3. */
4312 vect_pattern_recog (vec_info
*vinfo
)
4317 gimple_stmt_iterator si
;
4319 auto_vec
<gimple
*, 1> stmts_to_replace
;
4322 if (dump_enabled_p ())
4323 dump_printf_loc (MSG_NOTE
, vect_location
,
4324 "=== vect_pattern_recog ===\n");
4326 if (loop_vec_info loop_vinfo
= dyn_cast
<loop_vec_info
> (vinfo
))
4328 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4329 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
4330 nbbs
= loop
->num_nodes
;
4332 /* Scan through the loop stmts, applying the pattern recognition
4333 functions starting at each stmt visited: */
4334 for (i
= 0; i
< nbbs
; i
++)
4336 basic_block bb
= bbs
[i
];
4337 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
4339 /* Scan over all generic vect_recog_xxx_pattern functions. */
4340 for (j
= 0; j
< NUM_PATTERNS
; j
++)
4341 if (vect_pattern_recog_1 (&vect_vect_recog_func_ptrs
[j
], si
,
4349 bb_vec_info bb_vinfo
= as_a
<bb_vec_info
> (vinfo
);
4350 for (si
= bb_vinfo
->region_begin
;
4351 gsi_stmt (si
) != gsi_stmt (bb_vinfo
->region_end
); gsi_next (&si
))
4353 if ((stmt
= gsi_stmt (si
))
4354 && vinfo_for_stmt (stmt
)
4355 && !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt
)))
4358 /* Scan over all generic vect_recog_xxx_pattern functions. */
4359 for (j
= 0; j
< NUM_PATTERNS
; j
++)
4360 if (vect_pattern_recog_1 (&vect_vect_recog_func_ptrs
[j
], si
,