1 /* Analysis Utilities for Loop Vectorization.
2 Copyright (C) 2006, 2007, 2008 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"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
38 #include "tree-data-ref.h"
39 #include "tree-vectorizer.h"
43 /* Function prototypes */
44 static void vect_pattern_recog_1
45 (gimple (* ) (gimple, tree *, tree *), gimple_stmt_iterator);
46 static bool widened_name_p (tree, gimple, tree *, gimple *);
48 /* Pattern recognition functions */
49 static gimple vect_recog_widen_sum_pattern (gimple, tree *, tree *);
50 static gimple vect_recog_widen_mult_pattern (gimple, tree *, tree *);
51 static gimple vect_recog_dot_prod_pattern (gimple, tree *, tree *);
52 static gimple vect_recog_pow_pattern (gimple, tree *, tree *);
53 static vect_recog_func_ptr vect_vect_recog_func_ptrs[NUM_PATTERNS] = {
54 vect_recog_widen_mult_pattern,
55 vect_recog_widen_sum_pattern,
56 vect_recog_dot_prod_pattern,
57 vect_recog_pow_pattern};
60 /* Function widened_name_p
62 Check whether NAME, an ssa-name used in USE_STMT,
63 is a result of a type-promotion, such that:
64 DEF_STMT: NAME = NOP (name0)
65 where the type of name0 (HALF_TYPE) is smaller than the type of NAME.
69 widened_name_p (tree name, gimple use_stmt, tree *half_type, gimple *def_stmt)
73 loop_vec_info loop_vinfo;
74 stmt_vec_info stmt_vinfo;
75 tree type = TREE_TYPE (name);
77 enum vect_def_type dt;
80 stmt_vinfo = vinfo_for_stmt (use_stmt);
81 loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
83 if (!vect_is_simple_use (name, loop_vinfo, def_stmt, &def, &dt))
86 if (dt != vect_loop_def
87 && dt != vect_invariant_def && dt != vect_constant_def)
93 if (!is_gimple_assign (*def_stmt))
96 if (gimple_assign_rhs_code (*def_stmt) != NOP_EXPR)
99 oprnd0 = gimple_assign_rhs1 (*def_stmt);
101 *half_type = TREE_TYPE (oprnd0);
102 if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*half_type)
103 || (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*half_type))
104 || (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 2)))
107 if (!vect_is_simple_use (oprnd0, loop_vinfo, &dummy_gimple, &dummy, &dt))
113 /* Helper to return a new temporary for pattern of TYPE for STMT. If STMT
114 is NULL, the caller must set SSA_NAME_DEF_STMT for the returned SSA var. */
117 vect_recog_temp_ssa_var (tree type, gimple stmt)
119 tree var = create_tmp_var (type, "patt");
121 add_referenced_var (var);
122 var = make_ssa_name (var, stmt);
126 /* Function vect_recog_dot_prod_pattern
128 Try to find the following pattern:
134 sum_0 = phi <init, sum_1>
137 S3 x_T = (TYPE1) x_t;
138 S4 y_T = (TYPE1) y_t;
140 [S6 prod = (TYPE2) prod; #optional]
141 S7 sum_1 = prod + sum_0;
143 where 'TYPE1' is exactly double the size of type 'type', and 'TYPE2' is the
144 same size of 'TYPE1' or bigger. This is a special case of a reduction
149 * LAST_STMT: A stmt from which the pattern search begins. In the example,
150 when this function is called with S7, the pattern {S3,S4,S5,S6,S7} will be
155 * TYPE_IN: The type of the input arguments to the pattern.
157 * TYPE_OUT: The type of the output of this pattern.
159 * Return value: A new stmt that will be used to replace the sequence of
160 stmts that constitute the pattern. In this case it will be:
161 WIDEN_DOT_PRODUCT <x_t, y_t, sum_0>
163 Note: The dot-prod idiom is a widening reduction pattern that is
164 vectorized without preserving all the intermediate results. It
165 produces only N/2 (widened) results (by summing up pairs of
166 intermediate results) rather than all N results. Therefore, we
167 cannot allow this pattern when we want to get all the results and in
168 the correct order (as is the case when this computation is in an
169 inner-loop nested in an outer-loop that us being vectorized). */
172 vect_recog_dot_prod_pattern (gimple last_stmt, tree *type_in, tree *type_out)
176 tree oprnd00, oprnd01;
177 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
178 tree type, half_type;
181 loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
182 struct loop *loop = LOOP_VINFO_LOOP (loop_info);
185 if (!is_gimple_assign (last_stmt))
188 type = gimple_expr_type (last_stmt);
190 /* Look for the following pattern
194 DDPROD = (TYPE2) DPROD;
195 sum_1 = DDPROD + sum_0;
197 - DX is double the size of X
198 - DY is double the size of Y
199 - DX, DY, DPROD all have the same type
200 - sum is the same size of DPROD or bigger
201 - sum has been recognized as a reduction variable.
203 This is equivalent to:
204 DPROD = X w* Y; #widen mult
205 sum_1 = DPROD w+ sum_0; #widen summation
207 DPROD = X w* Y; #widen mult
208 sum_1 = DPROD + sum_0; #summation
211 /* Starting from LAST_STMT, follow the defs of its uses in search
212 of the above pattern. */
214 if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
217 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
219 /* Has been detected as widening-summation? */
221 stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
222 type = gimple_expr_type (stmt);
223 if (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR)
225 oprnd0 = gimple_assign_rhs1 (stmt);
226 oprnd1 = gimple_assign_rhs2 (stmt);
227 half_type = TREE_TYPE (oprnd0);
233 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
235 oprnd0 = gimple_assign_rhs1 (last_stmt);
236 oprnd1 = gimple_assign_rhs2 (last_stmt);
237 if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
238 || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
242 if (widened_name_p (oprnd0, stmt, &half_type, &def_stmt))
245 oprnd0 = gimple_assign_rhs1 (stmt);
251 /* So far so good. Since last_stmt was detected as a (summation) reduction,
252 we know that oprnd1 is the reduction variable (defined by a loop-header
253 phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
254 Left to check that oprnd0 is defined by a (widen_)mult_expr */
256 prod_type = half_type;
257 stmt = SSA_NAME_DEF_STMT (oprnd0);
258 /* FORNOW. Can continue analyzing the def-use chain when this stmt in a phi
259 inside the loop (in case we are analyzing an outer-loop). */
260 if (!is_gimple_assign (stmt))
262 stmt_vinfo = vinfo_for_stmt (stmt);
263 gcc_assert (stmt_vinfo);
264 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_loop_def)
266 if (gimple_assign_rhs_code (stmt) != MULT_EXPR)
268 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
270 /* Has been detected as a widening multiplication? */
272 stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
273 if (gimple_assign_rhs_code (stmt) != WIDEN_MULT_EXPR)
275 stmt_vinfo = vinfo_for_stmt (stmt);
276 gcc_assert (stmt_vinfo);
277 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_loop_def);
278 oprnd00 = gimple_assign_rhs1 (stmt);
279 oprnd01 = gimple_assign_rhs2 (stmt);
283 tree half_type0, half_type1;
287 oprnd0 = gimple_assign_rhs1 (stmt);
288 oprnd1 = gimple_assign_rhs2 (stmt);
289 if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0))
290 != TYPE_MAIN_VARIANT (prod_type)
291 || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1))
292 != TYPE_MAIN_VARIANT (prod_type))
294 if (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt))
296 oprnd00 = gimple_assign_rhs1 (def_stmt);
297 if (!widened_name_p (oprnd1, stmt, &half_type1, &def_stmt))
299 oprnd01 = gimple_assign_rhs1 (def_stmt);
300 if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (half_type1))
302 if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2)
306 half_type = TREE_TYPE (oprnd00);
307 *type_in = half_type;
310 /* Pattern detected. Create a stmt to be used to replace the pattern: */
311 var = vect_recog_temp_ssa_var (type, NULL);
312 rhs = build3 (DOT_PROD_EXPR, type, oprnd00, oprnd01, oprnd1),
313 pattern_stmt = gimple_build_assign (var, rhs);
315 if (vect_print_dump_info (REPORT_DETAILS))
317 fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: ");
318 print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
321 /* We don't allow changing the order of the computation in the inner-loop
322 when doing outer-loop vectorization. */
323 if (nested_in_vect_loop_p (loop, last_stmt))
325 if (vect_print_dump_info (REPORT_DETAILS))
326 fprintf (vect_dump, "vect_recog_dot_prod_pattern: not allowed.");
333 /* Function vect_recog_widen_mult_pattern
335 Try to find the following pattern:
338 TYPE a_T, b_T, prod_T;
344 S5 prod_T = a_T * b_T;
346 where type 'TYPE' is at least double the size of type 'type'.
350 * LAST_STMT: A stmt from which the pattern search begins. In the example,
351 when this function is called with S5, the pattern {S3,S4,S5} is be detected.
355 * TYPE_IN: The type of the input arguments to the pattern.
357 * TYPE_OUT: The type of the output of this pattern.
359 * Return value: A new stmt that will be used to replace the sequence of
360 stmts that constitute the pattern. In this case it will be:
361 WIDEN_MULT <a_t, b_t>
365 vect_recog_widen_mult_pattern (gimple last_stmt,
369 gimple def_stmt0, def_stmt1;
371 tree type, half_type0, half_type1;
376 enum tree_code dummy_code;
378 VEC (tree, heap) *dummy_vec;
380 if (!is_gimple_assign (last_stmt))
383 type = gimple_expr_type (last_stmt);
385 /* Starting from LAST_STMT, follow the defs of its uses in search
386 of the above pattern. */
388 if (gimple_assign_rhs_code (last_stmt) != MULT_EXPR)
391 oprnd0 = gimple_assign_rhs1 (last_stmt);
392 oprnd1 = gimple_assign_rhs2 (last_stmt);
393 if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
394 || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
397 /* Check argument 0 */
398 if (!widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0))
400 oprnd0 = gimple_assign_rhs1 (def_stmt0);
402 /* Check argument 1 */
403 if (!widened_name_p (oprnd1, last_stmt, &half_type1, &def_stmt1))
405 oprnd1 = gimple_assign_rhs1 (def_stmt1);
407 if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (half_type1))
410 /* Pattern detected. */
411 if (vect_print_dump_info (REPORT_DETAILS))
412 fprintf (vect_dump, "vect_recog_widen_mult_pattern: detected: ");
414 /* Check target support */
415 vectype = get_vectype_for_scalar_type (half_type0);
417 || !supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt, vectype,
418 &dummy, &dummy, &dummy_code,
419 &dummy_code, &dummy_int, &dummy_vec))
423 *type_out = NULL_TREE;
425 /* Pattern supported. Create a stmt to be used to replace the pattern: */
426 var = vect_recog_temp_ssa_var (type, NULL);
427 pattern_stmt = gimple_build_assign_with_ops (WIDEN_MULT_EXPR, var, oprnd0,
429 SSA_NAME_DEF_STMT (var) = pattern_stmt;
431 if (vect_print_dump_info (REPORT_DETAILS))
432 print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
438 /* Function vect_recog_pow_pattern
440 Try to find the following pattern:
444 with POW being one of pow, powf, powi, powif and N being
449 * LAST_STMT: A stmt from which the pattern search begins.
453 * TYPE_IN: The type of the input arguments to the pattern.
455 * TYPE_OUT: The type of the output of this pattern.
457 * Return value: A new stmt that will be used to replace the sequence of
458 stmts that constitute the pattern. In this case it will be:
465 vect_recog_pow_pattern (gimple last_stmt, tree *type_in, tree *type_out)
468 tree fn, base, exp = NULL;
472 if (!is_gimple_call (last_stmt) || gimple_call_lhs (last_stmt) == NULL)
475 type = gimple_expr_type (last_stmt);
477 fn = gimple_call_fndecl (last_stmt);
478 if (fn == NULL_TREE || DECL_BUILT_IN_CLASS (fn) != BUILT_IN_NORMAL)
481 switch (DECL_FUNCTION_CODE (fn))
487 base = gimple_call_arg (last_stmt, 0);
488 exp = gimple_call_arg (last_stmt, 1);
489 if (TREE_CODE (exp) != REAL_CST
490 && TREE_CODE (exp) != INTEGER_CST)
498 /* We now have a pow or powi builtin function call with a constant
501 *type_out = NULL_TREE;
503 /* Catch squaring. */
504 if ((host_integerp (exp, 0)
505 && tree_low_cst (exp, 0) == 2)
506 || (TREE_CODE (exp) == REAL_CST
507 && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconst2)))
509 *type_in = TREE_TYPE (base);
511 var = vect_recog_temp_ssa_var (TREE_TYPE (base), NULL);
512 stmt = gimple_build_assign_with_ops (MULT_EXPR, var, base, base);
513 SSA_NAME_DEF_STMT (var) = stmt;
517 /* Catch square root. */
518 if (TREE_CODE (exp) == REAL_CST
519 && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconsthalf))
521 tree newfn = mathfn_built_in (TREE_TYPE (base), BUILT_IN_SQRT);
522 *type_in = get_vectype_for_scalar_type (TREE_TYPE (base));
525 gimple stmt = gimple_build_call (newfn, 1, base);
526 if (vectorizable_function (stmt, *type_in, *type_in)
529 var = vect_recog_temp_ssa_var (TREE_TYPE (base), stmt);
530 gimple_call_set_lhs (stmt, var);
540 /* Function vect_recog_widen_sum_pattern
542 Try to find the following pattern:
545 TYPE x_T, sum = init;
547 sum_0 = phi <init, sum_1>
550 S3 sum_1 = x_T + sum_0;
552 where type 'TYPE' is at least double the size of type 'type', i.e - we're
553 summing elements of type 'type' into an accumulator of type 'TYPE'. This is
554 a special case of a reduction computation.
558 * LAST_STMT: A stmt from which the pattern search begins. In the example,
559 when this function is called with S3, the pattern {S2,S3} will be detected.
563 * TYPE_IN: The type of the input arguments to the pattern.
565 * TYPE_OUT: The type of the output of this pattern.
567 * Return value: A new stmt that will be used to replace the sequence of
568 stmts that constitute the pattern. In this case it will be:
569 WIDEN_SUM <x_t, sum_0>
571 Note: The widening-sum idiom is a widening reduction pattern that is
572 vectorized without preserving all the intermediate results. It
573 produces only N/2 (widened) results (by summing up pairs of
574 intermediate results) rather than all N results. Therefore, we
575 cannot allow this pattern when we want to get all the results and in
576 the correct order (as is the case when this computation is in an
577 inner-loop nested in an outer-loop that us being vectorized). */
580 vect_recog_widen_sum_pattern (gimple last_stmt, tree *type_in, tree *type_out)
584 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
585 tree type, half_type;
587 loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
588 struct loop *loop = LOOP_VINFO_LOOP (loop_info);
591 if (!is_gimple_assign (last_stmt))
594 type = gimple_expr_type (last_stmt);
596 /* Look for the following pattern
599 In which DX is at least double the size of X, and sum_1 has been
600 recognized as a reduction variable.
603 /* Starting from LAST_STMT, follow the defs of its uses in search
604 of the above pattern. */
606 if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
609 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
612 oprnd0 = gimple_assign_rhs1 (last_stmt);
613 oprnd1 = gimple_assign_rhs2 (last_stmt);
614 if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
615 || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
618 /* So far so good. Since last_stmt was detected as a (summation) reduction,
619 we know that oprnd1 is the reduction variable (defined by a loop-header
620 phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
621 Left to check that oprnd0 is defined by a cast from type 'type' to type
624 if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt))
627 oprnd0 = gimple_assign_rhs1 (stmt);
628 *type_in = half_type;
631 /* Pattern detected. Create a stmt to be used to replace the pattern: */
632 var = vect_recog_temp_ssa_var (type, NULL);
633 pattern_stmt = gimple_build_assign_with_ops (WIDEN_SUM_EXPR, var,
635 SSA_NAME_DEF_STMT (var) = pattern_stmt;
637 if (vect_print_dump_info (REPORT_DETAILS))
639 fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: ");
640 print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
643 /* We don't allow changing the order of the computation in the inner-loop
644 when doing outer-loop vectorization. */
645 if (nested_in_vect_loop_p (loop, last_stmt))
647 if (vect_print_dump_info (REPORT_DETAILS))
648 fprintf (vect_dump, "vect_recog_widen_sum_pattern: not allowed.");
656 /* Function vect_pattern_recog_1
659 PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
661 STMT: A stmt from which the pattern search should start.
663 If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
664 expression that computes the same functionality and can be used to
665 replace the sequence of stmts that are involved in the pattern.
668 This function checks if the expression returned by PATTERN_RECOG_FUNC is
669 supported in vector form by the target. We use 'TYPE_IN' to obtain the
670 relevant vector type. If 'TYPE_IN' is already a vector type, then this
671 indicates that target support had already been checked by PATTERN_RECOG_FUNC.
672 If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
673 to the available target pattern.
675 This function also does some bookkeeping, as explained in the documentation
676 for vect_recog_pattern. */
679 vect_pattern_recog_1 (
680 gimple (* vect_recog_func) (gimple, tree *, tree *),
681 gimple_stmt_iterator si)
683 gimple stmt = gsi_stmt (si), pattern_stmt;
684 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
685 stmt_vec_info pattern_stmt_info;
686 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
687 tree pattern_vectype;
688 tree type_in, type_out;
691 pattern_stmt = (* vect_recog_func) (stmt, &type_in, &type_out);
695 if (VECTOR_MODE_P (TYPE_MODE (type_in)))
697 /* No need to check target support (already checked by the pattern
698 recognition function). */
699 pattern_vectype = type_in;
703 enum tree_code vec_mode;
704 enum insn_code icode;
707 /* Check target support */
708 pattern_vectype = get_vectype_for_scalar_type (type_in);
709 if (!pattern_vectype)
712 if (is_gimple_assign (pattern_stmt))
713 code = gimple_assign_rhs_code (pattern_stmt);
716 gcc_assert (is_gimple_call (pattern_stmt));
720 optab = optab_for_tree_code (code, pattern_vectype, optab_default);
721 vec_mode = TYPE_MODE (pattern_vectype);
723 || (icode = optab_handler (optab, vec_mode)->insn_code) ==
726 && (!get_vectype_for_scalar_type (type_out)
727 || (insn_data[icode].operand[0].mode !=
728 TYPE_MODE (get_vectype_for_scalar_type (type_out))))))
732 /* Found a vectorizable pattern. */
733 if (vect_print_dump_info (REPORT_DETAILS))
735 fprintf (vect_dump, "pattern recognized: ");
736 print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
739 /* Mark the stmts that are involved in the pattern. */
740 gsi_insert_before (&si, pattern_stmt, GSI_SAME_STMT);
741 set_vinfo_for_stmt (pattern_stmt,
742 new_stmt_vec_info (pattern_stmt, loop_vinfo));
743 pattern_stmt_info = vinfo_for_stmt (pattern_stmt);
745 STMT_VINFO_RELATED_STMT (pattern_stmt_info) = stmt;
746 STMT_VINFO_DEF_TYPE (pattern_stmt_info) = STMT_VINFO_DEF_TYPE (stmt_info);
747 STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
748 STMT_VINFO_IN_PATTERN_P (stmt_info) = true;
749 STMT_VINFO_RELATED_STMT (stmt_info) = pattern_stmt;
755 /* Function vect_pattern_recog
758 LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
761 Output - for each computation idiom that is detected we insert a new stmt
762 that provides the same functionality and that can be vectorized. We
763 also record some information in the struct_stmt_info of the relevant
764 stmts, as explained below:
766 At the entry to this function we have the following stmts, with the
767 following initial value in the STMT_VINFO fields:
769 stmt in_pattern_p related_stmt vec_stmt
771 S2: a_2 = ..use(a_i).. - - -
772 S3: a_1 = ..use(a_2).. - - -
773 S4: a_0 = ..use(a_1).. - - -
774 S5: ... = ..use(a_0).. - - -
776 Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
777 represented by a single stmt. We then:
778 - create a new stmt S6 that will replace the pattern.
779 - insert the new stmt S6 before the last stmt in the pattern
780 - fill in the STMT_VINFO fields as follows:
782 in_pattern_p related_stmt vec_stmt
784 S2: a_2 = ..use(a_i).. - - -
785 S3: a_1 = ..use(a_2).. - - -
786 > S6: a_new = .... - S4 -
787 S4: a_0 = ..use(a_1).. true S6 -
788 S5: ... = ..use(a_0).. - - -
790 (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
791 to each other through the RELATED_STMT field).
793 S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
794 of S4 because it will replace all its uses. Stmts {S1,S2,S3} will
795 remain irrelevant unless used by stmts other than S4.
797 If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
798 (because they are marked as irrelevant). It will vectorize S6, and record
799 a pointer to the new vector stmt VS6 both from S6 (as usual), and also
800 from S4. We do that so that when we get to vectorizing stmts that use the
801 def of S4 (like S5 that uses a_0), we'll know where to take the relevant
802 vector-def from. S4 will be skipped, and S5 will be vectorized as usual:
804 in_pattern_p related_stmt vec_stmt
806 S2: a_2 = ..use(a_i).. - - -
807 S3: a_1 = ..use(a_2).. - - -
808 > VS6: va_new = .... - - -
809 S6: a_new = .... - S4 VS6
810 S4: a_0 = ..use(a_1).. true S6 VS6
811 > VS5: ... = ..vuse(va_new).. - - -
812 S5: ... = ..use(a_0).. - - -
814 DCE could then get rid of {S1,S2,S3,S4,S5,S6} (if their defs are not used
815 elsewhere), and we'll end up with:
818 VS5: ... = ..vuse(va_new)..
820 If vectorization does not succeed, DCE will clean S6 away (its def is
821 not used), and we'll end up with the original sequence.
825 vect_pattern_recog (loop_vec_info loop_vinfo)
827 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
828 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
829 unsigned int nbbs = loop->num_nodes;
830 gimple_stmt_iterator si;
833 gimple (* vect_recog_func_ptr) (gimple, tree *, tree *);
835 if (vect_print_dump_info (REPORT_DETAILS))
836 fprintf (vect_dump, "=== vect_pattern_recog ===");
838 /* Scan through the loop stmts, applying the pattern recognition
839 functions starting at each stmt visited: */
840 for (i = 0; i < nbbs; i++)
842 basic_block bb = bbs[i];
843 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
845 stmt = gsi_stmt (si);
847 /* Scan over all generic vect_recog_xxx_pattern functions. */
848 for (j = 0; j < NUM_PATTERNS; j++)
850 vect_recog_func_ptr = vect_vect_recog_func_ptrs[j];
851 vect_pattern_recog_1 (vect_recog_func_ptr, si);