1 /* SLP - Basic Block Vectorization
2 Copyright (C) 2007-2015 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
4 and Ira Rosen <irar@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
30 #include "tree-pass.h"
32 #include "optabs-tree.h"
33 #include "insn-config.h"
34 #include "recog.h" /* FIXME: for insn_data */
36 #include "fold-const.h"
37 #include "stor-layout.h"
38 #include "gimple-iterator.h"
40 #include "tree-vectorizer.h"
41 #include "langhooks.h"
42 #include "gimple-walk.h"
46 /* Recursively free the memory allocated for the SLP tree rooted at NODE. */
49 vect_free_slp_tree (slp_tree node
)
57 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
58 vect_free_slp_tree (child
);
60 SLP_TREE_CHILDREN (node
).release ();
61 SLP_TREE_SCALAR_STMTS (node
).release ();
62 SLP_TREE_VEC_STMTS (node
).release ();
63 SLP_TREE_LOAD_PERMUTATION (node
).release ();
69 /* Free the memory allocated for the SLP instance. */
72 vect_free_slp_instance (slp_instance instance
)
74 vect_free_slp_tree (SLP_INSTANCE_TREE (instance
));
75 SLP_INSTANCE_LOADS (instance
).release ();
80 /* Create an SLP node for SCALAR_STMTS. */
83 vect_create_new_slp_node (vec
<gimple
*> scalar_stmts
)
86 gimple
*stmt
= scalar_stmts
[0];
89 if (is_gimple_call (stmt
))
90 nops
= gimple_call_num_args (stmt
);
91 else if (is_gimple_assign (stmt
))
93 nops
= gimple_num_ops (stmt
) - 1;
94 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
100 node
= XNEW (struct _slp_tree
);
101 SLP_TREE_SCALAR_STMTS (node
) = scalar_stmts
;
102 SLP_TREE_VEC_STMTS (node
).create (0);
103 SLP_TREE_CHILDREN (node
).create (nops
);
104 SLP_TREE_LOAD_PERMUTATION (node
) = vNULL
;
105 SLP_TREE_TWO_OPERATORS (node
) = false;
111 /* This structure is used in creation of an SLP tree. Each instance
112 corresponds to the same operand in a group of scalar stmts in an SLP
114 typedef struct _slp_oprnd_info
116 /* Def-stmts for the operands. */
117 vec
<gimple
*> def_stmts
;
118 /* Information about the first statement, its vector def-type, type, the
119 operand itself in case it's constant, and an indication if it's a pattern
121 enum vect_def_type first_dt
;
128 /* Allocate operands info for NOPS operands, and GROUP_SIZE def-stmts for each
130 static vec
<slp_oprnd_info
>
131 vect_create_oprnd_info (int nops
, int group_size
)
134 slp_oprnd_info oprnd_info
;
135 vec
<slp_oprnd_info
> oprnds_info
;
137 oprnds_info
.create (nops
);
138 for (i
= 0; i
< nops
; i
++)
140 oprnd_info
= XNEW (struct _slp_oprnd_info
);
141 oprnd_info
->def_stmts
.create (group_size
);
142 oprnd_info
->first_dt
= vect_uninitialized_def
;
143 oprnd_info
->first_op_type
= NULL_TREE
;
144 oprnd_info
->first_pattern
= false;
145 oprnd_info
->second_pattern
= false;
146 oprnds_info
.quick_push (oprnd_info
);
153 /* Free operands info. */
156 vect_free_oprnd_info (vec
<slp_oprnd_info
> &oprnds_info
)
159 slp_oprnd_info oprnd_info
;
161 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
163 oprnd_info
->def_stmts
.release ();
164 XDELETE (oprnd_info
);
167 oprnds_info
.release ();
171 /* Find the place of the data-ref in STMT in the interleaving chain that starts
172 from FIRST_STMT. Return -1 if the data-ref is not a part of the chain. */
175 vect_get_place_in_interleaving_chain (gimple
*stmt
, gimple
*first_stmt
)
177 gimple
*next_stmt
= first_stmt
;
180 if (first_stmt
!= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
185 if (next_stmt
== stmt
)
187 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
189 result
+= GROUP_GAP (vinfo_for_stmt (next_stmt
));
197 /* Get the defs for the rhs of STMT (collect them in OPRNDS_INFO), check that
198 they are of a valid type and that they match the defs of the first stmt of
199 the SLP group (stored in OPRNDS_INFO). If there was a fatal error
200 return -1, if the error could be corrected by swapping operands of the
201 operation return 1, if everything is ok return 0. */
204 vect_get_and_check_slp_defs (vec_info
*vinfo
,
205 gimple
*stmt
, unsigned stmt_num
,
206 vec
<slp_oprnd_info
> *oprnds_info
)
209 unsigned int i
, number_of_oprnds
;
211 enum vect_def_type dt
= vect_uninitialized_def
;
212 bool pattern
= false;
213 slp_oprnd_info oprnd_info
;
214 int first_op_idx
= 1;
215 bool commutative
= false;
216 bool first_op_cond
= false;
217 bool first
= stmt_num
== 0;
218 bool second
= stmt_num
== 1;
220 if (is_gimple_call (stmt
))
222 number_of_oprnds
= gimple_call_num_args (stmt
);
225 else if (is_gimple_assign (stmt
))
227 enum tree_code code
= gimple_assign_rhs_code (stmt
);
228 number_of_oprnds
= gimple_num_ops (stmt
) - 1;
229 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
230 && COMPARISON_CLASS_P (gimple_assign_rhs1 (stmt
)))
232 first_op_cond
= true;
237 commutative
= commutative_tree_code (code
);
242 bool swapped
= false;
243 for (i
= 0; i
< number_of_oprnds
; i
++)
248 if (i
== 0 || i
== 1)
249 oprnd
= TREE_OPERAND (gimple_op (stmt
, first_op_idx
),
252 oprnd
= gimple_op (stmt
, first_op_idx
+ i
- 1);
255 oprnd
= gimple_op (stmt
, first_op_idx
+ (swapped
? !i
: i
));
257 oprnd_info
= (*oprnds_info
)[i
];
259 if (!vect_is_simple_use (oprnd
, vinfo
, &def_stmt
, &dt
))
261 if (dump_enabled_p ())
263 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
264 "Build SLP failed: can't analyze def for ");
265 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
266 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
272 /* Check if DEF_STMT is a part of a pattern in LOOP and get the def stmt
273 from the pattern. Check that all the stmts of the node are in the
275 if (def_stmt
&& gimple_bb (def_stmt
)
276 && vect_stmt_in_region_p (vinfo
, def_stmt
)
277 && vinfo_for_stmt (def_stmt
)
278 && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (def_stmt
))
279 && !STMT_VINFO_RELEVANT (vinfo_for_stmt (def_stmt
))
280 && !STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt
)))
283 if (!first
&& !oprnd_info
->first_pattern
284 /* Allow different pattern state for the defs of the
285 first stmt in reduction chains. */
286 && (oprnd_info
->first_dt
!= vect_reduction_def
287 || (!second
&& !oprnd_info
->second_pattern
)))
297 if (dump_enabled_p ())
299 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
300 "Build SLP failed: some of the stmts"
301 " are in a pattern, and others are not ");
302 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
303 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
309 def_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
));
310 dt
= STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
));
312 if (dt
== vect_unknown_def_type
)
314 if (dump_enabled_p ())
315 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
316 "Unsupported pattern.\n");
320 switch (gimple_code (def_stmt
))
327 if (dump_enabled_p ())
328 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
329 "unsupported defining stmt:\n");
335 oprnd_info
->second_pattern
= pattern
;
339 oprnd_info
->first_dt
= dt
;
340 oprnd_info
->first_pattern
= pattern
;
341 oprnd_info
->first_op_type
= TREE_TYPE (oprnd
);
345 /* Not first stmt of the group, check that the def-stmt/s match
346 the def-stmt/s of the first stmt. Allow different definition
347 types for reduction chains: the first stmt must be a
348 vect_reduction_def (a phi node), and the rest
349 vect_internal_def. */
350 if (((oprnd_info
->first_dt
!= dt
351 && !(oprnd_info
->first_dt
== vect_reduction_def
352 && dt
== vect_internal_def
)
353 && !((oprnd_info
->first_dt
== vect_external_def
354 || oprnd_info
->first_dt
== vect_constant_def
)
355 && (dt
== vect_external_def
356 || dt
== vect_constant_def
)))
357 || !types_compatible_p (oprnd_info
->first_op_type
,
360 /* Try swapping operands if we got a mismatch. */
369 if (dump_enabled_p ())
370 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
371 "Build SLP failed: different types\n");
377 /* Check the types of the definitions. */
380 case vect_constant_def
:
381 case vect_external_def
:
382 case vect_reduction_def
:
385 case vect_internal_def
:
386 oprnd_info
->def_stmts
.quick_push (def_stmt
);
390 /* FORNOW: Not supported. */
391 if (dump_enabled_p ())
393 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
394 "Build SLP failed: illegal type of def ");
395 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
396 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
408 tree cond
= gimple_assign_rhs1 (stmt
);
409 swap_ssa_operands (stmt
, &TREE_OPERAND (cond
, 0),
410 &TREE_OPERAND (cond
, 1));
411 TREE_SET_CODE (cond
, swap_tree_comparison (TREE_CODE (cond
)));
414 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
415 gimple_assign_rhs2_ptr (stmt
));
422 /* Verify if the scalar stmts STMTS are isomorphic, require data
423 permutation or are of unsupported types of operation. Return
424 true if they are, otherwise return false and indicate in *MATCHES
425 which stmts are not isomorphic to the first one. If MATCHES[0]
426 is false then this indicates the comparison could not be
427 carried out or the stmts will never be vectorized by SLP. */
430 vect_build_slp_tree_1 (vec_info
*vinfo
,
431 vec
<gimple
*> stmts
, unsigned int group_size
,
432 unsigned nops
, unsigned int *max_nunits
,
433 unsigned int vectorization_factor
, bool *matches
,
437 gimple
*first_stmt
= stmts
[0], *stmt
= stmts
[0];
438 enum tree_code first_stmt_code
= ERROR_MARK
;
439 enum tree_code alt_stmt_code
= ERROR_MARK
;
440 enum tree_code rhs_code
= ERROR_MARK
;
441 enum tree_code first_cond_code
= ERROR_MARK
;
443 bool need_same_oprnds
= false;
444 tree vectype
= NULL_TREE
, scalar_type
, first_op1
= NULL_TREE
;
447 machine_mode optab_op2_mode
;
448 machine_mode vec_mode
;
450 gimple
*first_load
= NULL
, *prev_first_load
= NULL
;
452 /* For every stmt in NODE find its def stmt/s. */
453 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
457 if (dump_enabled_p ())
459 dump_printf_loc (MSG_NOTE
, vect_location
, "Build SLP for ");
460 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
463 /* Fail to vectorize statements marked as unvectorizable. */
464 if (!STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt
)))
466 if (dump_enabled_p ())
468 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
469 "Build SLP failed: unvectorizable statement ");
470 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
471 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
473 /* Fatal mismatch. */
478 lhs
= gimple_get_lhs (stmt
);
479 if (lhs
== NULL_TREE
)
481 if (dump_enabled_p ())
483 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
484 "Build SLP failed: not GIMPLE_ASSIGN nor "
486 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
487 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
489 /* Fatal mismatch. */
494 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
, &dummy
);
495 vectype
= get_vectype_for_scalar_type (scalar_type
);
498 if (dump_enabled_p ())
500 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
501 "Build SLP failed: unsupported data-type ");
502 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
504 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
506 /* Fatal mismatch. */
511 /* If populating the vector type requires unrolling then fail
512 before adjusting *max_nunits for basic-block vectorization. */
513 if (is_a
<bb_vec_info
> (vinfo
)
514 && TYPE_VECTOR_SUBPARTS (vectype
) > group_size
)
516 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
517 "Build SLP failed: unrolling required "
518 "in basic block SLP\n");
519 /* Fatal mismatch. */
524 /* In case of multiple types we need to detect the smallest type. */
525 if (*max_nunits
< TYPE_VECTOR_SUBPARTS (vectype
))
527 *max_nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
528 if (is_a
<bb_vec_info
> (vinfo
))
529 vectorization_factor
= *max_nunits
;
532 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
534 rhs_code
= CALL_EXPR
;
535 if (gimple_call_internal_p (call_stmt
)
536 || gimple_call_tail_p (call_stmt
)
537 || gimple_call_noreturn_p (call_stmt
)
538 || !gimple_call_nothrow_p (call_stmt
)
539 || gimple_call_chain (call_stmt
))
541 if (dump_enabled_p ())
543 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
544 "Build SLP failed: unsupported call type ");
545 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
547 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
549 /* Fatal mismatch. */
555 rhs_code
= gimple_assign_rhs_code (stmt
);
557 /* Check the operation. */
560 first_stmt_code
= rhs_code
;
562 /* Shift arguments should be equal in all the packed stmts for a
563 vector shift with scalar shift operand. */
564 if (rhs_code
== LSHIFT_EXPR
|| rhs_code
== RSHIFT_EXPR
565 || rhs_code
== LROTATE_EXPR
566 || rhs_code
== RROTATE_EXPR
)
568 vec_mode
= TYPE_MODE (vectype
);
570 /* First see if we have a vector/vector shift. */
571 optab
= optab_for_tree_code (rhs_code
, vectype
,
575 || optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
577 /* No vector/vector shift, try for a vector/scalar shift. */
578 optab
= optab_for_tree_code (rhs_code
, vectype
,
583 if (dump_enabled_p ())
584 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
585 "Build SLP failed: no optab.\n");
586 /* Fatal mismatch. */
590 icode
= (int) optab_handler (optab
, vec_mode
);
591 if (icode
== CODE_FOR_nothing
)
593 if (dump_enabled_p ())
594 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
596 "op not supported by target.\n");
597 /* Fatal mismatch. */
601 optab_op2_mode
= insn_data
[icode
].operand
[2].mode
;
602 if (!VECTOR_MODE_P (optab_op2_mode
))
604 need_same_oprnds
= true;
605 first_op1
= gimple_assign_rhs2 (stmt
);
609 else if (rhs_code
== WIDEN_LSHIFT_EXPR
)
611 need_same_oprnds
= true;
612 first_op1
= gimple_assign_rhs2 (stmt
);
617 if (first_stmt_code
!= rhs_code
618 && alt_stmt_code
== ERROR_MARK
)
619 alt_stmt_code
= rhs_code
;
620 if (first_stmt_code
!= rhs_code
621 && (first_stmt_code
!= IMAGPART_EXPR
622 || rhs_code
!= REALPART_EXPR
)
623 && (first_stmt_code
!= REALPART_EXPR
624 || rhs_code
!= IMAGPART_EXPR
)
625 /* Handle mismatches in plus/minus by computing both
626 and merging the results. */
627 && !((first_stmt_code
== PLUS_EXPR
628 || first_stmt_code
== MINUS_EXPR
)
629 && (alt_stmt_code
== PLUS_EXPR
630 || alt_stmt_code
== MINUS_EXPR
)
631 && rhs_code
== alt_stmt_code
)
632 && !(STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
633 && (first_stmt_code
== ARRAY_REF
634 || first_stmt_code
== BIT_FIELD_REF
635 || first_stmt_code
== INDIRECT_REF
636 || first_stmt_code
== COMPONENT_REF
637 || first_stmt_code
== MEM_REF
)))
639 if (dump_enabled_p ())
641 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
642 "Build SLP failed: different operation "
644 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
645 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
647 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
655 && !operand_equal_p (first_op1
, gimple_assign_rhs2 (stmt
), 0))
657 if (dump_enabled_p ())
659 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
660 "Build SLP failed: different shift "
662 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
663 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
669 if (rhs_code
== CALL_EXPR
)
671 gimple
*first_stmt
= stmts
[0];
672 if (gimple_call_num_args (stmt
) != nops
673 || !operand_equal_p (gimple_call_fn (first_stmt
),
674 gimple_call_fn (stmt
), 0)
675 || gimple_call_fntype (first_stmt
)
676 != gimple_call_fntype (stmt
))
678 if (dump_enabled_p ())
680 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
681 "Build SLP failed: different calls in ");
682 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
684 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
692 /* Grouped store or load. */
693 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
695 if (REFERENCE_CLASS_P (lhs
))
703 /* Check that the size of interleaved loads group is not
704 greater than the SLP group size. */
706 = vectorization_factor
/ TYPE_VECTOR_SUBPARTS (vectype
);
707 if (is_a
<loop_vec_info
> (vinfo
)
708 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) == stmt
709 && ((GROUP_SIZE (vinfo_for_stmt (stmt
))
710 - GROUP_GAP (vinfo_for_stmt (stmt
)))
711 > ncopies
* group_size
))
713 if (dump_enabled_p ())
715 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
716 "Build SLP failed: the number "
717 "of interleaved loads is greater than "
718 "the SLP group size ");
719 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
721 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
723 /* Fatal mismatch. */
728 first_load
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
));
731 /* Check that there are no loads from different interleaving
732 chains in the same node. */
733 if (prev_first_load
!= first_load
)
735 if (dump_enabled_p ())
737 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
739 "Build SLP failed: different "
740 "interleaving chains in one node ");
741 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
743 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
750 prev_first_load
= first_load
;
752 } /* Grouped access. */
755 if (TREE_CODE_CLASS (rhs_code
) == tcc_reference
)
757 /* Not grouped load. */
758 if (dump_enabled_p ())
760 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
761 "Build SLP failed: not grouped load ");
762 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
763 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
766 /* FORNOW: Not grouped loads are not supported. */
767 /* Fatal mismatch. */
772 /* Not memory operation. */
773 if (TREE_CODE_CLASS (rhs_code
) != tcc_binary
774 && TREE_CODE_CLASS (rhs_code
) != tcc_unary
775 && TREE_CODE_CLASS (rhs_code
) != tcc_expression
776 && TREE_CODE_CLASS (rhs_code
) != tcc_comparison
777 && rhs_code
!= CALL_EXPR
)
779 if (dump_enabled_p ())
781 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
782 "Build SLP failed: operation");
783 dump_printf (MSG_MISSED_OPTIMIZATION
, " unsupported ");
784 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
785 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
787 /* Fatal mismatch. */
792 if (rhs_code
== COND_EXPR
)
794 tree cond_expr
= gimple_assign_rhs1 (stmt
);
797 first_cond_code
= TREE_CODE (cond_expr
);
798 else if (first_cond_code
!= TREE_CODE (cond_expr
))
800 if (dump_enabled_p ())
802 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
803 "Build SLP failed: different"
805 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
807 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
818 for (i
= 0; i
< group_size
; ++i
)
822 /* If we allowed a two-operation SLP node verify the target can cope
823 with the permute we are going to use. */
824 if (alt_stmt_code
!= ERROR_MARK
825 && TREE_CODE_CLASS (alt_stmt_code
) != tcc_reference
)
828 = XALLOCAVEC (unsigned char, TYPE_VECTOR_SUBPARTS (vectype
));
829 for (i
= 0; i
< TYPE_VECTOR_SUBPARTS (vectype
); ++i
)
832 if (gimple_assign_rhs_code (stmts
[i
% group_size
]) == alt_stmt_code
)
833 sel
[i
] += TYPE_VECTOR_SUBPARTS (vectype
);
835 if (!can_vec_perm_p (TYPE_MODE (vectype
), false, sel
))
837 for (i
= 0; i
< group_size
; ++i
)
838 if (gimple_assign_rhs_code (stmts
[i
]) == alt_stmt_code
)
841 if (dump_enabled_p ())
843 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
844 "Build SLP failed: different operation "
846 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
848 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
850 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
856 *two_operators
= true;
862 /* Recursively build an SLP tree starting from NODE.
863 Fail (and return a value not equal to zero) if def-stmts are not
864 isomorphic, require data permutation or are of unsupported types of
865 operation. Otherwise, return 0.
866 The value returned is the depth in the SLP tree where a mismatch
870 vect_build_slp_tree (vec_info
*vinfo
,
871 slp_tree
*node
, unsigned int group_size
,
872 unsigned int *max_nunits
,
873 vec
<slp_tree
> *loads
,
874 unsigned int vectorization_factor
,
875 bool *matches
, unsigned *npermutes
, unsigned *tree_size
,
876 unsigned max_tree_size
)
878 unsigned nops
, i
, this_tree_size
= 0;
883 stmt
= SLP_TREE_SCALAR_STMTS (*node
)[0];
884 if (is_gimple_call (stmt
))
885 nops
= gimple_call_num_args (stmt
);
886 else if (is_gimple_assign (stmt
))
888 nops
= gimple_num_ops (stmt
) - 1;
889 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
895 bool two_operators
= false;
896 if (!vect_build_slp_tree_1 (vinfo
,
897 SLP_TREE_SCALAR_STMTS (*node
), group_size
, nops
,
898 max_nunits
, vectorization_factor
, matches
,
901 SLP_TREE_TWO_OPERATORS (*node
) = two_operators
;
903 /* If the SLP node is a load, terminate the recursion. */
904 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
905 && DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
907 loads
->safe_push (*node
);
911 /* Get at the operands, verifying they are compatible. */
912 vec
<slp_oprnd_info
> oprnds_info
= vect_create_oprnd_info (nops
, group_size
);
913 slp_oprnd_info oprnd_info
;
914 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (*node
), i
, stmt
)
916 switch (vect_get_and_check_slp_defs (vinfo
, stmt
, i
, &oprnds_info
))
922 vect_free_oprnd_info (oprnds_info
);
929 for (i
= 0; i
< group_size
; ++i
)
932 vect_free_oprnd_info (oprnds_info
);
936 stmt
= SLP_TREE_SCALAR_STMTS (*node
)[0];
938 /* Create SLP_TREE nodes for the definition node/s. */
939 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
942 unsigned old_nloads
= loads
->length ();
943 unsigned old_max_nunits
= *max_nunits
;
945 if (oprnd_info
->first_dt
!= vect_internal_def
)
948 if (++this_tree_size
> max_tree_size
)
950 vect_free_oprnd_info (oprnds_info
);
954 child
= vect_create_new_slp_node (oprnd_info
->def_stmts
);
957 vect_free_oprnd_info (oprnds_info
);
961 if (vect_build_slp_tree (vinfo
, &child
,
962 group_size
, max_nunits
, loads
,
963 vectorization_factor
, matches
,
964 npermutes
, &this_tree_size
, max_tree_size
))
966 /* If we have all children of child built up from scalars then just
967 throw that away and build it up this node from scalars. */
968 if (!SLP_TREE_CHILDREN (child
).is_empty ())
973 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
974 if (grandchild
!= NULL
)
979 *max_nunits
= old_max_nunits
;
980 loads
->truncate (old_nloads
);
981 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
982 vect_free_slp_tree (grandchild
);
983 SLP_TREE_CHILDREN (child
).truncate (0);
985 dump_printf_loc (MSG_NOTE
, vect_location
,
986 "Building parent vector operands from "
987 "scalars instead\n");
988 oprnd_info
->def_stmts
= vNULL
;
989 vect_free_slp_tree (child
);
990 SLP_TREE_CHILDREN (*node
).quick_push (NULL
);
995 oprnd_info
->def_stmts
= vNULL
;
996 SLP_TREE_CHILDREN (*node
).quick_push (child
);
1000 /* If the SLP build failed fatally and we analyze a basic-block
1001 simply treat nodes we fail to build as externally defined
1002 (and thus build vectors from the scalar defs).
1003 The cost model will reject outright expensive cases.
1004 ??? This doesn't treat cases where permutation ultimatively
1005 fails (or we don't try permutation below). Ideally we'd
1006 even compute a permutation that will end up with the maximum
1008 if (is_a
<bb_vec_info
> (vinfo
)
1010 /* ??? Rejecting patterns this way doesn't work. We'd have to
1011 do extra work to cancel the pattern so the uses see the
1013 && !is_pattern_stmt_p (vinfo_for_stmt (stmt
)))
1016 slp_tree grandchild
;
1019 *max_nunits
= old_max_nunits
;
1020 loads
->truncate (old_nloads
);
1021 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1022 vect_free_slp_tree (grandchild
);
1023 SLP_TREE_CHILDREN (child
).truncate (0);
1025 dump_printf_loc (MSG_NOTE
, vect_location
,
1026 "Building vector operands from scalars\n");
1027 oprnd_info
->def_stmts
= vNULL
;
1028 vect_free_slp_tree (child
);
1029 SLP_TREE_CHILDREN (*node
).quick_push (NULL
);
1033 /* If the SLP build for operand zero failed and operand zero
1034 and one can be commutated try that for the scalar stmts
1035 that failed the match. */
1037 /* A first scalar stmt mismatch signals a fatal mismatch. */
1039 /* ??? For COND_EXPRs we can swap the comparison operands
1040 as well as the arms under some constraints. */
1042 && oprnds_info
[1]->first_dt
== vect_internal_def
1043 && is_gimple_assign (stmt
)
1044 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
1045 && !SLP_TREE_TWO_OPERATORS (*node
)
1046 /* Do so only if the number of not successful permutes was nor more
1047 than a cut-ff as re-trying the recursive match on
1048 possibly each level of the tree would expose exponential
1053 slp_tree grandchild
;
1056 *max_nunits
= old_max_nunits
;
1057 loads
->truncate (old_nloads
);
1058 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1059 vect_free_slp_tree (grandchild
);
1060 SLP_TREE_CHILDREN (child
).truncate (0);
1062 /* Swap mismatched definition stmts. */
1063 dump_printf_loc (MSG_NOTE
, vect_location
,
1064 "Re-trying with swapped operands of stmts ");
1065 for (j
= 0; j
< group_size
; ++j
)
1068 std::swap (oprnds_info
[0]->def_stmts
[j
],
1069 oprnds_info
[1]->def_stmts
[j
]);
1070 dump_printf (MSG_NOTE
, "%d ", j
);
1072 dump_printf (MSG_NOTE
, "\n");
1073 /* And try again with scratch 'matches' ... */
1074 bool *tem
= XALLOCAVEC (bool, group_size
);
1075 if (vect_build_slp_tree (vinfo
, &child
,
1076 group_size
, max_nunits
, loads
,
1077 vectorization_factor
,
1078 tem
, npermutes
, &this_tree_size
,
1081 /* ... so if successful we can apply the operand swapping
1082 to the GIMPLE IL. This is necessary because for example
1083 vect_get_slp_defs uses operand indexes and thus expects
1084 canonical operand order. */
1085 for (j
= 0; j
< group_size
; ++j
)
1088 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (*node
)[j
];
1089 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
1090 gimple_assign_rhs2_ptr (stmt
));
1092 oprnd_info
->def_stmts
= vNULL
;
1093 SLP_TREE_CHILDREN (*node
).quick_push (child
);
1100 oprnd_info
->def_stmts
= vNULL
;
1101 vect_free_slp_tree (child
);
1102 vect_free_oprnd_info (oprnds_info
);
1107 *tree_size
+= this_tree_size
;
1109 vect_free_oprnd_info (oprnds_info
);
1113 /* Dump a slp tree NODE using flags specified in DUMP_KIND. */
1116 vect_print_slp_tree (int dump_kind
, location_t loc
, slp_tree node
)
1125 dump_printf_loc (dump_kind
, loc
, "node\n");
1126 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1128 dump_printf_loc (dump_kind
, loc
, "\tstmt %d ", i
);
1129 dump_gimple_stmt (dump_kind
, TDF_SLIM
, stmt
, 0);
1131 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1132 vect_print_slp_tree (dump_kind
, loc
, child
);
1136 /* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
1137 If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
1138 J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
1139 stmts in NODE are to be marked. */
1142 vect_mark_slp_stmts (slp_tree node
, enum slp_vect_type mark
, int j
)
1151 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1152 if (j
< 0 || i
== j
)
1153 STMT_SLP_TYPE (vinfo_for_stmt (stmt
)) = mark
;
1155 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1156 vect_mark_slp_stmts (child
, mark
, j
);
1160 /* Mark the statements of the tree rooted at NODE as relevant (vect_used). */
1163 vect_mark_slp_stmts_relevant (slp_tree node
)
1167 stmt_vec_info stmt_info
;
1173 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1175 stmt_info
= vinfo_for_stmt (stmt
);
1176 gcc_assert (!STMT_VINFO_RELEVANT (stmt_info
)
1177 || STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
);
1178 STMT_VINFO_RELEVANT (stmt_info
) = vect_used_in_scope
;
1181 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1182 vect_mark_slp_stmts_relevant (child
);
1186 /* Rearrange the statements of NODE according to PERMUTATION. */
1189 vect_slp_rearrange_stmts (slp_tree node
, unsigned int group_size
,
1190 vec
<unsigned> permutation
)
1193 vec
<gimple
*> tmp_stmts
;
1197 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1198 vect_slp_rearrange_stmts (child
, group_size
, permutation
);
1200 gcc_assert (group_size
== SLP_TREE_SCALAR_STMTS (node
).length ());
1201 tmp_stmts
.create (group_size
);
1202 tmp_stmts
.quick_grow_cleared (group_size
);
1204 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1205 tmp_stmts
[permutation
[i
]] = stmt
;
1207 SLP_TREE_SCALAR_STMTS (node
).release ();
1208 SLP_TREE_SCALAR_STMTS (node
) = tmp_stmts
;
1212 /* Attempt to reorder stmts in a reduction chain so that we don't
1213 require any load permutation. Return true if that was possible,
1214 otherwise return false. */
1217 vect_attempt_slp_rearrange_stmts (slp_instance slp_instn
)
1219 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1223 slp_tree node
, load
;
1225 /* Compare all the permutation sequences to the first one. We know
1226 that at least one load is permuted. */
1227 node
= SLP_INSTANCE_LOADS (slp_instn
)[0];
1228 if (!node
->load_permutation
.exists ())
1230 for (i
= 1; SLP_INSTANCE_LOADS (slp_instn
).iterate (i
, &load
); ++i
)
1232 if (!load
->load_permutation
.exists ())
1234 FOR_EACH_VEC_ELT (load
->load_permutation
, j
, lidx
)
1235 if (lidx
!= node
->load_permutation
[j
])
1239 /* Check that the loads in the first sequence are different and there
1240 are no gaps between them. */
1241 load_index
= sbitmap_alloc (group_size
);
1242 bitmap_clear (load_index
);
1243 FOR_EACH_VEC_ELT (node
->load_permutation
, i
, lidx
)
1245 if (bitmap_bit_p (load_index
, lidx
))
1247 sbitmap_free (load_index
);
1250 bitmap_set_bit (load_index
, lidx
);
1252 for (i
= 0; i
< group_size
; i
++)
1253 if (!bitmap_bit_p (load_index
, i
))
1255 sbitmap_free (load_index
);
1258 sbitmap_free (load_index
);
1260 /* This permutation is valid for reduction. Since the order of the
1261 statements in the nodes is not important unless they are memory
1262 accesses, we can rearrange the statements in all the nodes
1263 according to the order of the loads. */
1264 vect_slp_rearrange_stmts (SLP_INSTANCE_TREE (slp_instn
), group_size
,
1265 node
->load_permutation
);
1267 /* We are done, no actual permutations need to be generated. */
1268 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1269 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1273 /* Check if the required load permutations in the SLP instance
1274 SLP_INSTN are supported. */
1277 vect_supported_load_permutation_p (slp_instance slp_instn
)
1279 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1280 unsigned int i
, j
, k
, next
;
1282 gimple
*stmt
, *load
, *next_load
;
1284 if (dump_enabled_p ())
1286 dump_printf_loc (MSG_NOTE
, vect_location
, "Load permutation ");
1287 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1288 if (node
->load_permutation
.exists ())
1289 FOR_EACH_VEC_ELT (node
->load_permutation
, j
, next
)
1290 dump_printf (MSG_NOTE
, "%d ", next
);
1292 for (k
= 0; k
< group_size
; ++k
)
1293 dump_printf (MSG_NOTE
, "%d ", k
);
1294 dump_printf (MSG_NOTE
, "\n");
1297 /* In case of reduction every load permutation is allowed, since the order
1298 of the reduction statements is not important (as opposed to the case of
1299 grouped stores). The only condition we need to check is that all the
1300 load nodes are of the same size and have the same permutation (and then
1301 rearrange all the nodes of the SLP instance according to this
1304 /* Check that all the load nodes are of the same size. */
1305 /* ??? Can't we assert this? */
1306 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1307 if (SLP_TREE_SCALAR_STMTS (node
).length () != (unsigned) group_size
)
1310 node
= SLP_INSTANCE_TREE (slp_instn
);
1311 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1313 /* Reduction (there are no data-refs in the root).
1314 In reduction chain the order of the loads is not important. */
1315 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))
1316 && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1318 if (vect_attempt_slp_rearrange_stmts (slp_instn
))
1321 /* Fallthru to general load permutation handling. */
1324 /* In basic block vectorization we allow any subchain of an interleaving
1326 FORNOW: not supported in loop SLP because of realignment compications. */
1327 if (STMT_VINFO_BB_VINFO (vinfo_for_stmt (stmt
)))
1329 /* Check whether the loads in an instance form a subchain and thus
1330 no permutation is necessary. */
1331 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1333 if (!SLP_TREE_LOAD_PERMUTATION (node
).exists ())
1335 bool subchain_p
= true;
1337 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), j
, load
)
1340 && (next_load
!= load
1341 || GROUP_GAP (vinfo_for_stmt (load
)) != 1))
1346 next_load
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (load
));
1349 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1352 /* Verify the permutation can be generated. */
1354 if (!vect_transform_slp_perm_load (node
, tem
, NULL
,
1355 1, slp_instn
, true))
1357 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
1359 "unsupported load permutation\n");
1367 /* For loop vectorization verify we can generate the permutation. */
1368 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1369 if (node
->load_permutation
.exists ()
1370 && !vect_transform_slp_perm_load
1372 SLP_INSTANCE_UNROLLING_FACTOR (slp_instn
), slp_instn
, true))
1379 /* Find the last store in SLP INSTANCE. */
1382 vect_find_last_scalar_stmt_in_slp (slp_tree node
)
1384 gimple
*last
= NULL
, *stmt
;
1386 for (int i
= 0; SLP_TREE_SCALAR_STMTS (node
).iterate (i
, &stmt
); i
++)
1388 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
1389 if (is_pattern_stmt_p (stmt_vinfo
))
1390 last
= get_later_stmt (STMT_VINFO_RELATED_STMT (stmt_vinfo
), last
);
1392 last
= get_later_stmt (stmt
, last
);
1398 /* Compute the cost for the SLP node NODE in the SLP instance INSTANCE. */
1401 vect_analyze_slp_cost_1 (slp_instance instance
, slp_tree node
,
1402 stmt_vector_for_cost
*prologue_cost_vec
,
1403 stmt_vector_for_cost
*body_cost_vec
,
1404 unsigned ncopies_for_cost
)
1409 stmt_vec_info stmt_info
;
1411 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1413 /* Recurse down the SLP tree. */
1414 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1416 vect_analyze_slp_cost_1 (instance
, child
, prologue_cost_vec
,
1417 body_cost_vec
, ncopies_for_cost
);
1419 /* Look at the first scalar stmt to determine the cost. */
1420 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1421 stmt_info
= vinfo_for_stmt (stmt
);
1422 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1424 if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info
)))
1425 vect_model_store_cost (stmt_info
, ncopies_for_cost
, false,
1426 vect_uninitialized_def
,
1427 node
, prologue_cost_vec
, body_cost_vec
);
1431 gcc_checking_assert (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)));
1432 /* If the load is permuted then the alignment is determined by
1433 the first group element not by the first scalar stmt DR. */
1434 if (SLP_TREE_LOAD_PERMUTATION (node
).exists ())
1436 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
1437 stmt_info
= vinfo_for_stmt (stmt
);
1439 vect_model_load_cost (stmt_info
, ncopies_for_cost
, false,
1440 node
, prologue_cost_vec
, body_cost_vec
);
1441 /* If the load is permuted record the cost for the permutation.
1442 ??? Loads from multiple chains are let through here only
1443 for a single special case involving complex numbers where
1444 in the end no permutation is necessary. */
1445 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, s
)
1446 if ((STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo_for_stmt (s
))
1447 == STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
))
1448 && vect_get_place_in_interleaving_chain
1449 (s
, STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
)) != i
)
1451 record_stmt_cost (body_cost_vec
, group_size
, vec_perm
,
1452 stmt_info
, 0, vect_body
);
1459 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1460 stmt_info
, 0, vect_body
);
1461 if (SLP_TREE_TWO_OPERATORS (node
))
1463 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1464 stmt_info
, 0, vect_body
);
1465 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vec_perm
,
1466 stmt_info
, 0, vect_body
);
1470 /* Scan operands and account for prologue cost of constants/externals.
1471 ??? This over-estimates cost for multiple uses and should be
1473 lhs
= gimple_get_lhs (stmt
);
1474 for (i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1476 tree op
= gimple_op (stmt
, i
);
1478 enum vect_def_type dt
;
1479 if (!op
|| op
== lhs
)
1481 if (vect_is_simple_use (op
, stmt_info
->vinfo
, &def_stmt
, &dt
))
1483 /* Without looking at the actual initializer a vector of
1484 constants can be implemented as load from the constant pool.
1485 ??? We need to pass down stmt_info for a vector type
1486 even if it points to the wrong stmt. */
1487 if (dt
== vect_constant_def
)
1488 record_stmt_cost (prologue_cost_vec
, 1, vector_load
,
1489 stmt_info
, 0, vect_prologue
);
1490 else if (dt
== vect_external_def
)
1491 record_stmt_cost (prologue_cost_vec
, 1, vec_construct
,
1492 stmt_info
, 0, vect_prologue
);
1497 /* Compute the cost for the SLP instance INSTANCE. */
1500 vect_analyze_slp_cost (slp_instance instance
, void *data
)
1502 stmt_vector_for_cost body_cost_vec
, prologue_cost_vec
;
1503 unsigned ncopies_for_cost
;
1504 stmt_info_for_cost
*si
;
1507 if (dump_enabled_p ())
1508 dump_printf_loc (MSG_NOTE
, vect_location
,
1509 "=== vect_analyze_slp_cost ===\n");
1511 /* Calculate the number of vector stmts to create based on the unrolling
1512 factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
1513 GROUP_SIZE / NUNITS otherwise. */
1514 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1515 slp_tree node
= SLP_INSTANCE_TREE (instance
);
1516 stmt_vec_info stmt_info
= vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node
)[0]);
1517 /* Adjust the group_size by the vectorization factor which is always one
1518 for basic-block vectorization. */
1519 if (STMT_VINFO_LOOP_VINFO (stmt_info
))
1520 group_size
*= LOOP_VINFO_VECT_FACTOR (STMT_VINFO_LOOP_VINFO (stmt_info
));
1521 unsigned nunits
= TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
1522 /* For reductions look at a reduction operand in case the reduction
1523 operation is widening like DOT_PROD or SAD. */
1524 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1526 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1527 switch (gimple_assign_rhs_code (stmt
))
1531 nunits
= TYPE_VECTOR_SUBPARTS (get_vectype_for_scalar_type
1532 (TREE_TYPE (gimple_assign_rhs1 (stmt
))));
1537 ncopies_for_cost
= least_common_multiple (nunits
, group_size
) / nunits
;
1539 prologue_cost_vec
.create (10);
1540 body_cost_vec
.create (10);
1541 vect_analyze_slp_cost_1 (instance
, SLP_INSTANCE_TREE (instance
),
1542 &prologue_cost_vec
, &body_cost_vec
,
1545 /* Record the prologue costs, which were delayed until we were
1546 sure that SLP was successful. */
1547 FOR_EACH_VEC_ELT (prologue_cost_vec
, i
, si
)
1549 struct _stmt_vec_info
*stmt_info
1550 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1551 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1552 si
->misalign
, vect_prologue
);
1555 /* Record the instance's instructions in the target cost model. */
1556 FOR_EACH_VEC_ELT (body_cost_vec
, i
, si
)
1558 struct _stmt_vec_info
*stmt_info
1559 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1560 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1561 si
->misalign
, vect_body
);
1564 prologue_cost_vec
.release ();
1565 body_cost_vec
.release ();
1568 /* Splits a group of stores, currently beginning at FIRST_STMT, into two groups:
1569 one (still beginning at FIRST_STMT) of size GROUP1_SIZE (also containing
1570 the first GROUP1_SIZE stmts, since stores are consecutive), the second
1571 containing the remainder.
1572 Return the first stmt in the second group. */
1575 vect_split_slp_store_group (gimple
*first_stmt
, unsigned group1_size
)
1577 stmt_vec_info first_vinfo
= vinfo_for_stmt (first_stmt
);
1578 gcc_assert (GROUP_FIRST_ELEMENT (first_vinfo
) == first_stmt
);
1579 gcc_assert (group1_size
> 0);
1580 int group2_size
= GROUP_SIZE (first_vinfo
) - group1_size
;
1581 gcc_assert (group2_size
> 0);
1582 GROUP_SIZE (first_vinfo
) = group1_size
;
1584 gimple
*stmt
= first_stmt
;
1585 for (unsigned i
= group1_size
; i
> 1; i
--)
1587 stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
1588 gcc_assert (GROUP_GAP (vinfo_for_stmt (stmt
)) == 1);
1590 /* STMT is now the last element of the first group. */
1591 gimple
*group2
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
1592 GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
)) = 0;
1594 GROUP_SIZE (vinfo_for_stmt (group2
)) = group2_size
;
1595 for (stmt
= group2
; stmt
; stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
)))
1597 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = group2
;
1598 gcc_assert (GROUP_GAP (vinfo_for_stmt (stmt
)) == 1);
1601 /* For the second group, the GROUP_GAP is that before the original group,
1602 plus skipping over the first vector. */
1603 GROUP_GAP (vinfo_for_stmt (group2
)) =
1604 GROUP_GAP (first_vinfo
) + group1_size
;
1606 /* GROUP_GAP of the first group now has to skip over the second group too. */
1607 GROUP_GAP (first_vinfo
) += group2_size
;
1609 if (dump_enabled_p ())
1610 dump_printf_loc (MSG_NOTE
, vect_location
, "Split group into %d and %d\n",
1611 group1_size
, group2_size
);
1616 /* Analyze an SLP instance starting from a group of grouped stores. Call
1617 vect_build_slp_tree to build a tree of packed stmts if possible.
1618 Return FALSE if it's impossible to SLP any stmt in the loop. */
1621 vect_analyze_slp_instance (vec_info
*vinfo
,
1622 gimple
*stmt
, unsigned max_tree_size
)
1624 slp_instance new_instance
;
1626 unsigned int group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1627 unsigned int unrolling_factor
= 1, nunits
;
1628 tree vectype
, scalar_type
= NULL_TREE
;
1630 unsigned int vectorization_factor
= 0;
1632 unsigned int max_nunits
= 0;
1633 vec
<slp_tree
> loads
;
1634 struct data_reference
*dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
));
1635 vec
<gimple
*> scalar_stmts
;
1637 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1641 scalar_type
= TREE_TYPE (DR_REF (dr
));
1642 vectype
= get_vectype_for_scalar_type (scalar_type
);
1646 gcc_assert (is_a
<loop_vec_info
> (vinfo
));
1647 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1650 group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1654 gcc_assert (is_a
<loop_vec_info
> (vinfo
));
1655 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1656 group_size
= as_a
<loop_vec_info
> (vinfo
)->reductions
.length ();
1661 if (dump_enabled_p ())
1663 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1664 "Build SLP failed: unsupported data-type ");
1665 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, scalar_type
);
1666 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1672 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
1673 if (is_a
<loop_vec_info
> (vinfo
))
1674 vectorization_factor
= as_a
<loop_vec_info
> (vinfo
)->vectorization_factor
;
1676 vectorization_factor
= nunits
;
1678 /* Calculate the unrolling factor. */
1679 unrolling_factor
= least_common_multiple (nunits
, group_size
) / group_size
;
1680 if (unrolling_factor
!= 1 && is_a
<bb_vec_info
> (vinfo
))
1682 if (dump_enabled_p ())
1683 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1684 "Build SLP failed: unrolling required in basic"
1690 /* Create a node (a root of the SLP tree) for the packed grouped stores. */
1691 scalar_stmts
.create (group_size
);
1693 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1695 /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
1698 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next
))
1699 && STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)))
1700 scalar_stmts
.safe_push (
1701 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)));
1703 scalar_stmts
.safe_push (next
);
1704 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
1706 /* Mark the first element of the reduction chain as reduction to properly
1707 transform the node. In the reduction analysis phase only the last
1708 element of the chain is marked as reduction. */
1709 if (!STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
1710 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_reduction_def
;
1714 /* Collect reduction statements. */
1715 vec
<gimple
*> reductions
= as_a
<loop_vec_info
> (vinfo
)->reductions
;
1716 for (i
= 0; reductions
.iterate (i
, &next
); i
++)
1717 scalar_stmts
.safe_push (next
);
1720 node
= vect_create_new_slp_node (scalar_stmts
);
1722 loads
.create (group_size
);
1724 /* Build the tree for the SLP instance. */
1725 bool *matches
= XALLOCAVEC (bool, group_size
);
1726 unsigned npermutes
= 0;
1727 if (vect_build_slp_tree (vinfo
, &node
, group_size
,
1728 &max_nunits
, &loads
,
1729 vectorization_factor
, matches
, &npermutes
, NULL
,
1732 /* Calculate the unrolling factor based on the smallest type. */
1733 if (max_nunits
> nunits
)
1734 unrolling_factor
= least_common_multiple (max_nunits
, group_size
)
1737 if (unrolling_factor
!= 1 && is_a
<bb_vec_info
> (vinfo
))
1739 if (dump_enabled_p ())
1740 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1741 "Build SLP failed: unrolling required in basic"
1743 vect_free_slp_tree (node
);
1748 /* Create a new SLP instance. */
1749 new_instance
= XNEW (struct _slp_instance
);
1750 SLP_INSTANCE_TREE (new_instance
) = node
;
1751 SLP_INSTANCE_GROUP_SIZE (new_instance
) = group_size
;
1752 SLP_INSTANCE_UNROLLING_FACTOR (new_instance
) = unrolling_factor
;
1753 SLP_INSTANCE_LOADS (new_instance
) = loads
;
1755 /* Compute the load permutation. */
1757 bool loads_permuted
= false;
1758 FOR_EACH_VEC_ELT (loads
, i
, load_node
)
1760 vec
<unsigned> load_permutation
;
1762 gimple
*load
, *first_stmt
;
1763 bool this_load_permuted
= false;
1764 load_permutation
.create (group_size
);
1765 first_stmt
= GROUP_FIRST_ELEMENT
1766 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node
)[0]));
1767 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node
), j
, load
)
1770 = vect_get_place_in_interleaving_chain (load
, first_stmt
);
1771 gcc_assert (load_place
!= -1);
1772 if (load_place
!= j
)
1773 this_load_permuted
= true;
1774 load_permutation
.safe_push (load_place
);
1776 if (!this_load_permuted
1777 /* The load requires permutation when unrolling exposes
1778 a gap either because the group is larger than the SLP
1779 group-size or because there is a gap between the groups. */
1780 && (unrolling_factor
== 1
1781 || (group_size
== GROUP_SIZE (vinfo_for_stmt (first_stmt
))
1782 && GROUP_GAP (vinfo_for_stmt (first_stmt
)) == 0)))
1784 load_permutation
.release ();
1787 SLP_TREE_LOAD_PERMUTATION (load_node
) = load_permutation
;
1788 loads_permuted
= true;
1793 if (!vect_supported_load_permutation_p (new_instance
))
1795 if (dump_enabled_p ())
1797 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1798 "Build SLP failed: unsupported load "
1800 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
1801 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1803 vect_free_slp_instance (new_instance
);
1808 vinfo
->slp_instances
.safe_push (new_instance
);
1810 if (dump_enabled_p ())
1812 dump_printf_loc (MSG_NOTE
, vect_location
,
1813 "Final SLP tree for instance:\n");
1814 vect_print_slp_tree (MSG_NOTE
, vect_location
, node
);
1820 /* Failed to SLP. */
1821 /* Free the allocated memory. */
1822 vect_free_slp_tree (node
);
1825 /* For basic block SLP, try to break the group up into multiples of the
1826 vectorization factor. */
1827 if (is_a
<bb_vec_info
> (vinfo
)
1828 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
1829 && STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
1831 /* We consider breaking the group only on VF boundaries from the existing
1833 for (i
= 0; i
< group_size
; i
++)
1834 if (!matches
[i
]) break;
1836 if (i
>= vectorization_factor
&& i
< group_size
)
1838 /* Split into two groups at the first vector boundary before i. */
1839 gcc_assert ((vectorization_factor
& (vectorization_factor
- 1)) == 0);
1840 unsigned group1_size
= i
& ~(vectorization_factor
- 1);
1842 gimple
*rest
= vect_split_slp_store_group (stmt
, group1_size
);
1843 bool res
= vect_analyze_slp_instance (vinfo
, stmt
, max_tree_size
);
1844 /* If the first non-match was in the middle of a vector,
1845 skip the rest of that vector. */
1846 if (group1_size
< i
)
1848 i
= group1_size
+ vectorization_factor
;
1850 rest
= vect_split_slp_store_group (rest
, vectorization_factor
);
1853 res
|= vect_analyze_slp_instance (vinfo
, rest
, max_tree_size
);
1856 /* Even though the first vector did not all match, we might be able to SLP
1857 (some) of the remainder. FORNOW ignore this possibility. */
1864 /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
1865 trees of packed scalar stmts if SLP is possible. */
1868 vect_analyze_slp (vec_info
*vinfo
, unsigned max_tree_size
)
1871 gimple
*first_element
;
1874 if (dump_enabled_p ())
1875 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_analyze_slp ===\n");
1877 /* Find SLP sequences starting from groups of grouped stores. */
1878 FOR_EACH_VEC_ELT (vinfo
->grouped_stores
, i
, first_element
)
1879 if (vect_analyze_slp_instance (vinfo
, first_element
, max_tree_size
))
1882 if (loop_vec_info loop_vinfo
= dyn_cast
<loop_vec_info
> (vinfo
))
1884 if (loop_vinfo
->reduction_chains
.length () > 0)
1886 /* Find SLP sequences starting from reduction chains. */
1887 FOR_EACH_VEC_ELT (loop_vinfo
->reduction_chains
, i
, first_element
)
1888 if (vect_analyze_slp_instance (vinfo
, first_element
,
1894 /* Don't try to vectorize SLP reductions if reduction chain was
1899 /* Find SLP sequences starting from groups of reductions. */
1900 if (loop_vinfo
->reductions
.length () > 1
1901 && vect_analyze_slp_instance (vinfo
, loop_vinfo
->reductions
[0],
1910 /* For each possible SLP instance decide whether to SLP it and calculate overall
1911 unrolling factor needed to SLP the loop. Return TRUE if decided to SLP at
1912 least one instance. */
1915 vect_make_slp_decision (loop_vec_info loop_vinfo
)
1917 unsigned int i
, unrolling_factor
= 1;
1918 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
1919 slp_instance instance
;
1920 int decided_to_slp
= 0;
1922 if (dump_enabled_p ())
1923 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_make_slp_decision ==="
1926 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
1928 /* FORNOW: SLP if you can. */
1929 if (unrolling_factor
< SLP_INSTANCE_UNROLLING_FACTOR (instance
))
1930 unrolling_factor
= SLP_INSTANCE_UNROLLING_FACTOR (instance
);
1932 /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
1933 call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
1934 loop-based vectorization. Such stmts will be marked as HYBRID. */
1935 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
1939 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
) = unrolling_factor
;
1941 if (decided_to_slp
&& dump_enabled_p ())
1942 dump_printf_loc (MSG_NOTE
, vect_location
,
1943 "Decided to SLP %d instances. Unrolling factor %d\n",
1944 decided_to_slp
, unrolling_factor
);
1946 return (decided_to_slp
> 0);
1950 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
1951 can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
1954 vect_detect_hybrid_slp_stmts (slp_tree node
, unsigned i
, slp_vect_type stype
)
1956 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[i
];
1957 imm_use_iterator imm_iter
;
1959 stmt_vec_info use_vinfo
, stmt_vinfo
= vinfo_for_stmt (stmt
);
1961 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
1962 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1965 /* Propagate hybrid down the SLP tree. */
1966 if (stype
== hybrid
)
1968 else if (HYBRID_SLP_STMT (stmt_vinfo
))
1972 /* Check if a pure SLP stmt has uses in non-SLP stmts. */
1973 gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo
));
1974 /* We always get the pattern stmt here, but for immediate
1975 uses we have to use the LHS of the original stmt. */
1976 gcc_checking_assert (!STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
1977 if (STMT_VINFO_RELATED_STMT (stmt_vinfo
))
1978 stmt
= STMT_VINFO_RELATED_STMT (stmt_vinfo
);
1979 if (TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
1980 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, gimple_op (stmt
, 0))
1982 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
1984 use_vinfo
= vinfo_for_stmt (use_stmt
);
1985 if (STMT_VINFO_IN_PATTERN_P (use_vinfo
)
1986 && STMT_VINFO_RELATED_STMT (use_vinfo
))
1987 use_vinfo
= vinfo_for_stmt (STMT_VINFO_RELATED_STMT (use_vinfo
));
1988 if (!STMT_SLP_TYPE (use_vinfo
)
1989 && (STMT_VINFO_RELEVANT (use_vinfo
)
1990 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo
)))
1991 && !(gimple_code (use_stmt
) == GIMPLE_PHI
1992 && STMT_VINFO_DEF_TYPE (use_vinfo
) == vect_reduction_def
))
1994 if (dump_enabled_p ())
1996 dump_printf_loc (MSG_NOTE
, vect_location
, "use of SLP "
1997 "def in non-SLP stmt: ");
1998 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, use_stmt
, 0);
2006 && !HYBRID_SLP_STMT (stmt_vinfo
))
2008 if (dump_enabled_p ())
2010 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2011 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
2013 STMT_SLP_TYPE (stmt_vinfo
) = hybrid
;
2016 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2018 vect_detect_hybrid_slp_stmts (child
, i
, stype
);
2021 /* Helpers for vect_detect_hybrid_slp walking pattern stmt uses. */
2024 vect_detect_hybrid_slp_1 (tree
*tp
, int *, void *data
)
2026 walk_stmt_info
*wi
= (walk_stmt_info
*)data
;
2027 struct loop
*loopp
= (struct loop
*)wi
->info
;
2032 if (TREE_CODE (*tp
) == SSA_NAME
2033 && !SSA_NAME_IS_DEFAULT_DEF (*tp
))
2035 gimple
*def_stmt
= SSA_NAME_DEF_STMT (*tp
);
2036 if (flow_bb_inside_loop_p (loopp
, gimple_bb (def_stmt
))
2037 && PURE_SLP_STMT (vinfo_for_stmt (def_stmt
)))
2039 if (dump_enabled_p ())
2041 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2042 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2044 STMT_SLP_TYPE (vinfo_for_stmt (def_stmt
)) = hybrid
;
2052 vect_detect_hybrid_slp_2 (gimple_stmt_iterator
*gsi
, bool *handled
,
2055 /* If the stmt is in a SLP instance then this isn't a reason
2056 to mark use definitions in other SLP instances as hybrid. */
2057 if (STMT_SLP_TYPE (vinfo_for_stmt (gsi_stmt (*gsi
))) != loop_vect
)
2062 /* Find stmts that must be both vectorized and SLPed. */
2065 vect_detect_hybrid_slp (loop_vec_info loop_vinfo
)
2068 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2069 slp_instance instance
;
2071 if (dump_enabled_p ())
2072 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_detect_hybrid_slp ==="
2075 /* First walk all pattern stmt in the loop and mark defs of uses as
2076 hybrid because immediate uses in them are not recorded. */
2077 for (i
= 0; i
< LOOP_VINFO_LOOP (loop_vinfo
)->num_nodes
; ++i
)
2079 basic_block bb
= LOOP_VINFO_BBS (loop_vinfo
)[i
];
2080 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2083 gimple
*stmt
= gsi_stmt (gsi
);
2084 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2085 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
2088 memset (&wi
, 0, sizeof (wi
));
2089 wi
.info
= LOOP_VINFO_LOOP (loop_vinfo
);
2090 gimple_stmt_iterator gsi2
2091 = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info
));
2092 walk_gimple_stmt (&gsi2
, vect_detect_hybrid_slp_2
,
2093 vect_detect_hybrid_slp_1
, &wi
);
2094 walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
),
2095 vect_detect_hybrid_slp_2
,
2096 vect_detect_hybrid_slp_1
, &wi
);
2101 /* Then walk the SLP instance trees marking stmts with uses in
2102 non-SLP stmts as hybrid, also propagating hybrid down the
2103 SLP tree, collecting the above info on-the-fly. */
2104 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2106 for (unsigned i
= 0; i
< SLP_INSTANCE_GROUP_SIZE (instance
); ++i
)
2107 vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance
),
2113 /* Create and initialize a new bb_vec_info struct for BB, as well as
2114 stmt_vec_info structs for all the stmts in it. */
2117 new_bb_vec_info (gimple_stmt_iterator region_begin
,
2118 gimple_stmt_iterator region_end
)
2120 basic_block bb
= gsi_bb (region_begin
);
2121 bb_vec_info res
= NULL
;
2122 gimple_stmt_iterator gsi
;
2124 res
= (bb_vec_info
) xcalloc (1, sizeof (struct _bb_vec_info
));
2125 res
->kind
= vec_info::bb
;
2126 BB_VINFO_BB (res
) = bb
;
2127 res
->region_begin
= region_begin
;
2128 res
->region_end
= region_end
;
2130 for (gsi
= region_begin
; gsi_stmt (gsi
) != gsi_stmt (region_end
);
2133 gimple
*stmt
= gsi_stmt (gsi
);
2134 gimple_set_uid (stmt
, 0);
2135 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
));
2138 BB_VINFO_GROUPED_STORES (res
).create (10);
2139 BB_VINFO_SLP_INSTANCES (res
).create (2);
2140 BB_VINFO_TARGET_COST_DATA (res
) = init_cost (NULL
);
2147 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
2148 stmts in the basic block. */
2151 destroy_bb_vec_info (bb_vec_info bb_vinfo
)
2153 vec
<slp_instance
> slp_instances
;
2154 slp_instance instance
;
2156 gimple_stmt_iterator si
;
2162 bb
= BB_VINFO_BB (bb_vinfo
);
2164 for (si
= bb_vinfo
->region_begin
;
2165 gsi_stmt (si
) != gsi_stmt (bb_vinfo
->region_end
); gsi_next (&si
))
2167 gimple
*stmt
= gsi_stmt (si
);
2168 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2171 /* Free stmt_vec_info. */
2172 free_stmt_vec_info (stmt
);
2174 /* Reset region marker. */
2175 gimple_set_uid (stmt
, -1);
2178 vect_destroy_datarefs (bb_vinfo
);
2179 free_dependence_relations (BB_VINFO_DDRS (bb_vinfo
));
2180 BB_VINFO_GROUPED_STORES (bb_vinfo
).release ();
2181 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2182 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2183 vect_free_slp_instance (instance
);
2184 BB_VINFO_SLP_INSTANCES (bb_vinfo
).release ();
2185 destroy_cost_data (BB_VINFO_TARGET_COST_DATA (bb_vinfo
));
2191 /* Analyze statements contained in SLP tree node after recursively analyzing
2192 the subtree. Return TRUE if the operations are supported. */
2195 vect_slp_analyze_node_operations (slp_tree node
)
2205 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2206 if (!vect_slp_analyze_node_operations (child
))
2209 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2211 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2212 gcc_assert (stmt_info
);
2213 gcc_assert (STMT_SLP_TYPE (stmt_info
) != loop_vect
);
2215 if (!vect_analyze_stmt (stmt
, &dummy
, node
))
2223 /* Analyze statements in SLP instances of the basic block. Return TRUE if the
2224 operations are supported. */
2227 vect_slp_analyze_operations (vec
<slp_instance
> slp_instances
, void *data
)
2229 slp_instance instance
;
2232 if (dump_enabled_p ())
2233 dump_printf_loc (MSG_NOTE
, vect_location
,
2234 "=== vect_slp_analyze_operations ===\n");
2236 for (i
= 0; slp_instances
.iterate (i
, &instance
); )
2238 if (!vect_slp_analyze_node_operations (SLP_INSTANCE_TREE (instance
)))
2240 dump_printf_loc (MSG_NOTE
, vect_location
,
2241 "removing SLP instance operations starting from: ");
2242 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
2243 SLP_TREE_SCALAR_STMTS
2244 (SLP_INSTANCE_TREE (instance
))[0], 0);
2245 vect_free_slp_instance (instance
);
2246 slp_instances
.ordered_remove (i
);
2250 /* Compute the costs of the SLP instance. */
2251 vect_analyze_slp_cost (instance
, data
);
2256 if (!slp_instances
.length ())
2263 /* Compute the scalar cost of the SLP node NODE and its children
2264 and return it. Do not account defs that are marked in LIFE and
2265 update LIFE according to uses of NODE. */
2268 vect_bb_slp_scalar_cost (basic_block bb
,
2269 slp_tree node
, vec
<bool, va_heap
> *life
)
2271 unsigned scalar_cost
= 0;
2276 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2279 ssa_op_iter op_iter
;
2280 def_operand_p def_p
;
2281 stmt_vec_info stmt_info
;
2286 /* If there is a non-vectorized use of the defs then the scalar
2287 stmt is kept live in which case we do not account it or any
2288 required defs in the SLP children in the scalar cost. This
2289 way we make the vectorization more costly when compared to
2291 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
2293 imm_use_iterator use_iter
;
2295 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, DEF_FROM_PTR (def_p
))
2296 if (!is_gimple_debug (use_stmt
)
2297 && (! vect_stmt_in_region_p (vinfo_for_stmt (stmt
)->vinfo
,
2299 || !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (use_stmt
))))
2302 BREAK_FROM_IMM_USE_STMT (use_iter
);
2308 stmt_info
= vinfo_for_stmt (stmt
);
2309 if (STMT_VINFO_DATA_REF (stmt_info
))
2311 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)))
2312 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2314 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2317 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2319 scalar_cost
+= stmt_cost
;
2322 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2324 scalar_cost
+= vect_bb_slp_scalar_cost (bb
, child
, life
);
2329 /* Check if vectorization of the basic block is profitable. */
2332 vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo
)
2334 vec
<slp_instance
> slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2335 slp_instance instance
;
2337 unsigned int vec_inside_cost
= 0, vec_outside_cost
= 0, scalar_cost
= 0;
2338 unsigned int vec_prologue_cost
= 0, vec_epilogue_cost
= 0;
2340 /* Calculate scalar cost. */
2341 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2343 auto_vec
<bool, 20> life
;
2344 life
.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance
));
2345 scalar_cost
+= vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo
),
2346 SLP_INSTANCE_TREE (instance
),
2350 /* Complete the target-specific cost calculation. */
2351 finish_cost (BB_VINFO_TARGET_COST_DATA (bb_vinfo
), &vec_prologue_cost
,
2352 &vec_inside_cost
, &vec_epilogue_cost
);
2354 vec_outside_cost
= vec_prologue_cost
+ vec_epilogue_cost
;
2356 if (dump_enabled_p ())
2358 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2359 dump_printf (MSG_NOTE
, " Vector inside of basic block cost: %d\n",
2361 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n", vec_prologue_cost
);
2362 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n", vec_epilogue_cost
);
2363 dump_printf (MSG_NOTE
, " Scalar cost of basic block: %d\n", scalar_cost
);
2366 /* Vectorization is profitable if its cost is more than the cost of scalar
2367 version. Note that we err on the vector side for equal cost because
2368 the cost estimate is otherwise quite pessimistic (constant uses are
2369 free on the scalar side but cost a load on the vector side for
2371 if (vec_outside_cost
+ vec_inside_cost
> scalar_cost
)
2377 /* Check if the basic block can be vectorized. Returns a bb_vec_info
2378 if so and sets fatal to true if failure is independent of
2379 current_vector_size. */
2382 vect_slp_analyze_bb_1 (gimple_stmt_iterator region_begin
,
2383 gimple_stmt_iterator region_end
,
2384 vec
<data_reference_p
> datarefs
, int n_stmts
,
2387 bb_vec_info bb_vinfo
;
2388 slp_instance instance
;
2392 /* The first group of checks is independent of the vector size. */
2395 if (n_stmts
> PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB
))
2397 if (dump_enabled_p ())
2398 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2399 "not vectorized: too many instructions in "
2401 free_data_refs (datarefs
);
2405 bb_vinfo
= new_bb_vec_info (region_begin
, region_end
);
2409 BB_VINFO_DATAREFS (bb_vinfo
) = datarefs
;
2411 /* Analyze the data references. */
2413 if (!vect_analyze_data_refs (bb_vinfo
, &min_vf
))
2415 if (dump_enabled_p ())
2416 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2417 "not vectorized: unhandled data-ref in basic "
2420 destroy_bb_vec_info (bb_vinfo
);
2424 if (BB_VINFO_DATAREFS (bb_vinfo
).length () < 2)
2426 if (dump_enabled_p ())
2427 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2428 "not vectorized: not enough data-refs in "
2431 destroy_bb_vec_info (bb_vinfo
);
2435 if (!vect_analyze_data_ref_accesses (bb_vinfo
))
2437 if (dump_enabled_p ())
2438 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2439 "not vectorized: unhandled data access in "
2442 destroy_bb_vec_info (bb_vinfo
);
2446 /* If there are no grouped stores in the region there is no need
2447 to continue with pattern recog as vect_analyze_slp will fail
2449 if (bb_vinfo
->grouped_stores
.is_empty ())
2451 if (dump_enabled_p ())
2452 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2453 "not vectorized: no grouped stores in "
2456 destroy_bb_vec_info (bb_vinfo
);
2460 /* While the rest of the analysis below depends on it in some way. */
2463 vect_pattern_recog (bb_vinfo
);
2465 /* Check the SLP opportunities in the basic block, analyze and build SLP
2467 if (!vect_analyze_slp (bb_vinfo
, n_stmts
))
2469 if (dump_enabled_p ())
2471 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2472 "Failed to SLP the basic block.\n");
2473 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2474 "not vectorized: failed to find SLP opportunities "
2475 "in basic block.\n");
2478 destroy_bb_vec_info (bb_vinfo
);
2482 /* Analyze and verify the alignment of data references and the
2483 dependence in the SLP instances. */
2484 for (i
= 0; BB_VINFO_SLP_INSTANCES (bb_vinfo
).iterate (i
, &instance
); )
2486 if (! vect_slp_analyze_and_verify_instance_alignment (instance
)
2487 || ! vect_slp_analyze_instance_dependence (instance
))
2489 dump_printf_loc (MSG_NOTE
, vect_location
,
2490 "removing SLP instance operations starting from: ");
2491 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
2492 SLP_TREE_SCALAR_STMTS
2493 (SLP_INSTANCE_TREE (instance
))[0], 0);
2494 vect_free_slp_instance (instance
);
2495 BB_VINFO_SLP_INSTANCES (bb_vinfo
).ordered_remove (i
);
2499 /* Mark all the statements that we want to vectorize as pure SLP and
2501 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2502 vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance
));
2506 if (! BB_VINFO_SLP_INSTANCES (bb_vinfo
).length ())
2508 destroy_bb_vec_info (bb_vinfo
);
2512 /* Mark all the statements that we do not want to vectorize. */
2513 for (gimple_stmt_iterator gsi
= bb_vinfo
->region_begin
;
2514 gsi_stmt (gsi
) != gsi_stmt (bb_vinfo
->region_end
); gsi_next (&gsi
))
2516 stmt_vec_info vinfo
= vinfo_for_stmt (gsi_stmt (gsi
));
2517 if (STMT_SLP_TYPE (vinfo
) != pure_slp
)
2518 STMT_VINFO_VECTORIZABLE (vinfo
) = false;
2521 if (!vect_slp_analyze_operations (BB_VINFO_SLP_INSTANCES (bb_vinfo
),
2522 BB_VINFO_TARGET_COST_DATA (bb_vinfo
)))
2524 if (dump_enabled_p ())
2525 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2526 "not vectorized: bad operation in basic block.\n");
2528 destroy_bb_vec_info (bb_vinfo
);
2532 /* Cost model: check if the vectorization is worthwhile. */
2533 if (!unlimited_cost_model (NULL
)
2534 && !vect_bb_vectorization_profitable_p (bb_vinfo
))
2536 if (dump_enabled_p ())
2537 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2538 "not vectorized: vectorization is not "
2541 destroy_bb_vec_info (bb_vinfo
);
2545 if (dump_enabled_p ())
2546 dump_printf_loc (MSG_NOTE
, vect_location
,
2547 "Basic block will be vectorized using SLP\n");
2553 /* Main entry for the BB vectorizer. Analyze and transform BB, returns
2554 true if anything in the basic-block was vectorized. */
2557 vect_slp_bb (basic_block bb
)
2559 bb_vec_info bb_vinfo
;
2560 gimple_stmt_iterator gsi
;
2561 unsigned int vector_sizes
;
2562 bool any_vectorized
= false;
2564 if (dump_enabled_p ())
2565 dump_printf_loc (MSG_NOTE
, vect_location
, "===vect_slp_analyze_bb===\n");
2567 /* Autodetect first vector size we try. */
2568 current_vector_size
= 0;
2569 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2571 gsi
= gsi_start_bb (bb
);
2575 if (gsi_end_p (gsi
))
2578 gimple_stmt_iterator region_begin
= gsi
;
2579 vec
<data_reference_p
> datarefs
= vNULL
;
2582 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
2584 gimple
*stmt
= gsi_stmt (gsi
);
2585 if (is_gimple_debug (stmt
))
2589 if (gimple_location (stmt
) != UNKNOWN_LOCATION
)
2590 vect_location
= gimple_location (stmt
);
2592 if (!find_data_references_in_stmt (NULL
, stmt
, &datarefs
))
2596 /* Skip leading unhandled stmts. */
2597 if (gsi_stmt (region_begin
) == gsi_stmt (gsi
))
2603 gimple_stmt_iterator region_end
= gsi
;
2605 bool vectorized
= false;
2607 bb_vinfo
= vect_slp_analyze_bb_1 (region_begin
, region_end
,
2608 datarefs
, insns
, fatal
);
2610 && dbg_cnt (vect_slp
))
2612 if (dump_enabled_p ())
2613 dump_printf_loc (MSG_NOTE
, vect_location
, "SLPing BB part\n");
2615 vect_schedule_slp (bb_vinfo
);
2617 if (dump_enabled_p ())
2618 dump_printf_loc (MSG_NOTE
, vect_location
,
2619 "basic block part vectorized\n");
2621 destroy_bb_vec_info (bb_vinfo
);
2626 destroy_bb_vec_info (bb_vinfo
);
2628 any_vectorized
|= vectorized
;
2630 vector_sizes
&= ~current_vector_size
;
2632 || vector_sizes
== 0
2633 || current_vector_size
== 0
2634 /* If vect_slp_analyze_bb_1 signaled that analysis for all
2635 vector sizes will fail do not bother iterating. */
2638 if (gsi_end_p (region_end
))
2641 /* Skip the unhandled stmt. */
2644 /* And reset vector sizes. */
2645 current_vector_size
= 0;
2646 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2650 /* Try the next biggest vector size. */
2651 current_vector_size
= 1 << floor_log2 (vector_sizes
);
2652 if (dump_enabled_p ())
2653 dump_printf_loc (MSG_NOTE
, vect_location
,
2654 "***** Re-trying analysis with "
2655 "vector size %d\n", current_vector_size
);
2662 return any_vectorized
;
2666 /* Return 1 if vector type of boolean constant which is OPNUM
2667 operand in statement STMT is a boolean vector. */
2670 vect_mask_constant_operand_p (gimple
*stmt
, int opnum
)
2672 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2673 enum tree_code code
= gimple_expr_code (stmt
);
2676 enum vect_def_type dt
;
2678 /* For comparison and COND_EXPR type is chosen depending
2679 on the other comparison operand. */
2680 if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2683 op
= gimple_assign_rhs1 (stmt
);
2685 op
= gimple_assign_rhs2 (stmt
);
2687 if (!vect_is_simple_use (op
, stmt_vinfo
->vinfo
, &def_stmt
,
2691 return !vectype
|| VECTOR_BOOLEAN_TYPE_P (vectype
);
2694 if (code
== COND_EXPR
)
2696 tree cond
= gimple_assign_rhs1 (stmt
);
2698 if (TREE_CODE (cond
) == SSA_NAME
)
2702 op
= TREE_OPERAND (cond
, 1);
2704 op
= TREE_OPERAND (cond
, 0);
2706 if (!vect_is_simple_use (op
, stmt_vinfo
->vinfo
, &def_stmt
,
2710 return !vectype
|| VECTOR_BOOLEAN_TYPE_P (vectype
);
2713 return VECTOR_BOOLEAN_TYPE_P (STMT_VINFO_VECTYPE (stmt_vinfo
));
2717 /* For constant and loop invariant defs of SLP_NODE this function returns
2718 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
2719 OP_NUM determines if we gather defs for operand 0 or operand 1 of the RHS of
2720 scalar stmts. NUMBER_OF_VECTORS is the number of vector defs to create.
2721 REDUC_INDEX is the index of the reduction operand in the statements, unless
2725 vect_get_constant_vectors (tree op
, slp_tree slp_node
,
2726 vec
<tree
> *vec_oprnds
,
2727 unsigned int op_num
, unsigned int number_of_vectors
,
2730 vec
<gimple
*> stmts
= SLP_TREE_SCALAR_STMTS (slp_node
);
2731 gimple
*stmt
= stmts
[0];
2732 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2736 unsigned j
, number_of_places_left_in_vector
;
2739 int group_size
= stmts
.length ();
2740 unsigned int vec_num
, i
;
2741 unsigned number_of_copies
= 1;
2743 voprnds
.create (number_of_vectors
);
2744 bool constant_p
, is_store
;
2745 tree neutral_op
= NULL
;
2746 enum tree_code code
= gimple_expr_code (stmt
);
2749 gimple_seq ctor_seq
= NULL
;
2751 /* Check if vector type is a boolean vector. */
2752 if (TREE_CODE (TREE_TYPE (op
)) == BOOLEAN_TYPE
2753 && vect_mask_constant_operand_p (stmt
, op_num
))
2755 = build_same_sized_truth_vector_type (STMT_VINFO_VECTYPE (stmt_vinfo
));
2757 vector_type
= get_vectype_for_scalar_type (TREE_TYPE (op
));
2758 nunits
= TYPE_VECTOR_SUBPARTS (vector_type
);
2760 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_reduction_def
2761 && reduc_index
!= -1)
2763 op_num
= reduc_index
;
2764 op
= gimple_op (stmt
, op_num
+ 1);
2765 /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
2766 we need either neutral operands or the original operands. See
2767 get_initial_def_for_reduction() for details. */
2770 case WIDEN_SUM_EXPR
:
2777 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2778 neutral_op
= build_real (TREE_TYPE (op
), dconst0
);
2780 neutral_op
= build_int_cst (TREE_TYPE (op
), 0);
2785 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2786 neutral_op
= build_real (TREE_TYPE (op
), dconst1
);
2788 neutral_op
= build_int_cst (TREE_TYPE (op
), 1);
2793 neutral_op
= build_int_cst (TREE_TYPE (op
), -1);
2796 /* For MIN/MAX we don't have an easy neutral operand but
2797 the initial values can be used fine here. Only for
2798 a reduction chain we have to force a neutral element. */
2801 if (!GROUP_FIRST_ELEMENT (stmt_vinfo
))
2805 def_stmt
= SSA_NAME_DEF_STMT (op
);
2806 loop
= (gimple_bb (stmt
))->loop_father
;
2807 neutral_op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2808 loop_preheader_edge (loop
));
2813 gcc_assert (!GROUP_FIRST_ELEMENT (stmt_vinfo
));
2818 if (STMT_VINFO_DATA_REF (stmt_vinfo
))
2821 op
= gimple_assign_rhs1 (stmt
);
2828 if (CONSTANT_CLASS_P (op
))
2833 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
2834 created vectors. It is greater than 1 if unrolling is performed.
2836 For example, we have two scalar operands, s1 and s2 (e.g., group of
2837 strided accesses of size two), while NUNITS is four (i.e., four scalars
2838 of this type can be packed in a vector). The output vector will contain
2839 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
2842 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
2843 containing the operands.
2845 For example, NUNITS is four as before, and the group size is 8
2846 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
2847 {s5, s6, s7, s8}. */
2849 number_of_copies
= nunits
* number_of_vectors
/ group_size
;
2851 number_of_places_left_in_vector
= nunits
;
2852 elts
= XALLOCAVEC (tree
, nunits
);
2853 bool place_after_defs
= false;
2854 for (j
= 0; j
< number_of_copies
; j
++)
2856 for (i
= group_size
- 1; stmts
.iterate (i
, &stmt
); i
--)
2859 op
= gimple_assign_rhs1 (stmt
);
2866 tree cond
= gimple_assign_rhs1 (stmt
);
2867 if (TREE_CODE (cond
) == SSA_NAME
)
2868 op
= gimple_op (stmt
, op_num
+ 1);
2869 else if (op_num
== 0 || op_num
== 1)
2870 op
= TREE_OPERAND (cond
, op_num
);
2874 op
= gimple_assign_rhs2 (stmt
);
2876 op
= gimple_assign_rhs3 (stmt
);
2882 op
= gimple_call_arg (stmt
, op_num
);
2889 op
= gimple_op (stmt
, op_num
+ 1);
2890 /* Unlike the other binary operators, shifts/rotates have
2891 the shift count being int, instead of the same type as
2892 the lhs, so make sure the scalar is the right type if
2893 we are dealing with vectors of
2894 long long/long/short/char. */
2895 if (op_num
== 1 && TREE_CODE (op
) == INTEGER_CST
)
2896 op
= fold_convert (TREE_TYPE (vector_type
), op
);
2900 op
= gimple_op (stmt
, op_num
+ 1);
2905 if (reduc_index
!= -1)
2907 loop
= (gimple_bb (stmt
))->loop_father
;
2908 def_stmt
= SSA_NAME_DEF_STMT (op
);
2912 /* Get the def before the loop. In reduction chain we have only
2913 one initial value. */
2914 if ((j
!= (number_of_copies
- 1)
2915 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
2920 op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2921 loop_preheader_edge (loop
));
2924 /* Create 'vect_ = {op0,op1,...,opn}'. */
2925 number_of_places_left_in_vector
--;
2927 if (!types_compatible_p (TREE_TYPE (vector_type
), TREE_TYPE (op
)))
2929 if (CONSTANT_CLASS_P (op
))
2931 if (VECTOR_BOOLEAN_TYPE_P (vector_type
))
2933 /* Can't use VIEW_CONVERT_EXPR for booleans because
2934 of possibly different sizes of scalar value and
2936 if (integer_zerop (op
))
2937 op
= build_int_cst (TREE_TYPE (vector_type
), 0);
2938 else if (integer_onep (op
))
2939 op
= build_int_cst (TREE_TYPE (vector_type
), 1);
2944 op
= fold_unary (VIEW_CONVERT_EXPR
,
2945 TREE_TYPE (vector_type
), op
);
2946 gcc_assert (op
&& CONSTANT_CLASS_P (op
));
2950 tree new_temp
= make_ssa_name (TREE_TYPE (vector_type
));
2952 op
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (vector_type
), op
);
2954 = gimple_build_assign (new_temp
, VIEW_CONVERT_EXPR
, op
);
2955 gimple_seq_add_stmt (&ctor_seq
, init_stmt
);
2959 elts
[number_of_places_left_in_vector
] = op
;
2960 if (!CONSTANT_CLASS_P (op
))
2962 if (TREE_CODE (orig_op
) == SSA_NAME
2963 && !SSA_NAME_IS_DEFAULT_DEF (orig_op
)
2964 && STMT_VINFO_BB_VINFO (stmt_vinfo
)
2965 && (STMT_VINFO_BB_VINFO (stmt_vinfo
)->bb
2966 == gimple_bb (SSA_NAME_DEF_STMT (orig_op
))))
2967 place_after_defs
= true;
2969 if (number_of_places_left_in_vector
== 0)
2971 number_of_places_left_in_vector
= nunits
;
2974 vec_cst
= build_vector (vector_type
, elts
);
2977 vec
<constructor_elt
, va_gc
> *v
;
2979 vec_alloc (v
, nunits
);
2980 for (k
= 0; k
< nunits
; ++k
)
2981 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[k
]);
2982 vec_cst
= build_constructor (vector_type
, v
);
2985 gimple_stmt_iterator gsi
;
2986 if (place_after_defs
)
2989 (vect_find_last_scalar_stmt_in_slp (slp_node
));
2990 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, &gsi
);
2993 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, NULL
);
2994 if (ctor_seq
!= NULL
)
2996 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (init
));
2997 gsi_insert_seq_before_without_update (&gsi
, ctor_seq
,
3001 voprnds
.quick_push (init
);
3002 place_after_defs
= false;
3007 /* Since the vectors are created in the reverse order, we should invert
3009 vec_num
= voprnds
.length ();
3010 for (j
= vec_num
; j
!= 0; j
--)
3012 vop
= voprnds
[j
- 1];
3013 vec_oprnds
->quick_push (vop
);
3018 /* In case that VF is greater than the unrolling factor needed for the SLP
3019 group of stmts, NUMBER_OF_VECTORS to be created is greater than
3020 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
3021 to replicate the vectors. */
3022 while (number_of_vectors
> vec_oprnds
->length ())
3024 tree neutral_vec
= NULL
;
3029 neutral_vec
= build_vector_from_val (vector_type
, neutral_op
);
3031 vec_oprnds
->quick_push (neutral_vec
);
3035 for (i
= 0; vec_oprnds
->iterate (i
, &vop
) && i
< vec_num
; i
++)
3036 vec_oprnds
->quick_push (vop
);
3042 /* Get vectorized definitions from SLP_NODE that contains corresponding
3043 vectorized def-stmts. */
3046 vect_get_slp_vect_defs (slp_tree slp_node
, vec
<tree
> *vec_oprnds
)
3049 gimple
*vec_def_stmt
;
3052 gcc_assert (SLP_TREE_VEC_STMTS (slp_node
).exists ());
3054 FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (slp_node
), i
, vec_def_stmt
)
3056 gcc_assert (vec_def_stmt
);
3057 vec_oprnd
= gimple_get_lhs (vec_def_stmt
);
3058 vec_oprnds
->quick_push (vec_oprnd
);
3063 /* Get vectorized definitions for SLP_NODE.
3064 If the scalar definitions are loop invariants or constants, collect them and
3065 call vect_get_constant_vectors() to create vector stmts.
3066 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
3067 must be stored in the corresponding child of SLP_NODE, and we call
3068 vect_get_slp_vect_defs () to retrieve them. */
3071 vect_get_slp_defs (vec
<tree
> ops
, slp_tree slp_node
,
3072 vec
<vec
<tree
> > *vec_oprnds
, int reduc_index
)
3075 int number_of_vects
= 0, i
;
3076 unsigned int child_index
= 0;
3077 HOST_WIDE_INT lhs_size_unit
, rhs_size_unit
;
3078 slp_tree child
= NULL
;
3081 bool vectorized_defs
;
3083 first_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[0];
3084 FOR_EACH_VEC_ELT (ops
, i
, oprnd
)
3086 /* For each operand we check if it has vectorized definitions in a child
3087 node or we need to create them (for invariants and constants). We
3088 check if the LHS of the first stmt of the next child matches OPRND.
3089 If it does, we found the correct child. Otherwise, we call
3090 vect_get_constant_vectors (), and not advance CHILD_INDEX in order
3091 to check this child node for the next operand. */
3092 vectorized_defs
= false;
3093 if (SLP_TREE_CHILDREN (slp_node
).length () > child_index
)
3095 child
= SLP_TREE_CHILDREN (slp_node
)[child_index
];
3097 /* We have to check both pattern and original def, if available. */
3100 gimple
*first_def
= SLP_TREE_SCALAR_STMTS (child
)[0];
3102 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def
));
3104 if (operand_equal_p (oprnd
, gimple_get_lhs (first_def
), 0)
3106 && operand_equal_p (oprnd
, gimple_get_lhs (related
), 0)))
3108 /* The number of vector defs is determined by the number of
3109 vector statements in the node from which we get those
3111 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (child
);
3112 vectorized_defs
= true;
3120 if (!vectorized_defs
)
3124 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
3125 /* Number of vector stmts was calculated according to LHS in
3126 vect_schedule_slp_instance (), fix it by replacing LHS with
3127 RHS, if necessary. See vect_get_smallest_scalar_type () for
3129 vect_get_smallest_scalar_type (first_stmt
, &lhs_size_unit
,
3131 if (rhs_size_unit
!= lhs_size_unit
)
3133 number_of_vects
*= rhs_size_unit
;
3134 number_of_vects
/= lhs_size_unit
;
3139 /* Allocate memory for vectorized defs. */
3141 vec_defs
.create (number_of_vects
);
3143 /* For reduction defs we call vect_get_constant_vectors (), since we are
3144 looking for initial loop invariant values. */
3145 if (vectorized_defs
&& reduc_index
== -1)
3146 /* The defs are already vectorized. */
3147 vect_get_slp_vect_defs (child
, &vec_defs
);
3149 /* Build vectors from scalar defs. */
3150 vect_get_constant_vectors (oprnd
, slp_node
, &vec_defs
, i
,
3151 number_of_vects
, reduc_index
);
3153 vec_oprnds
->quick_push (vec_defs
);
3155 /* For reductions, we only need initial values. */
3156 if (reduc_index
!= -1)
3162 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
3163 building a vector of type MASK_TYPE from it) and two input vectors placed in
3164 DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
3165 shifting by STRIDE elements of DR_CHAIN for every copy.
3166 (STRIDE is the number of vectorized stmts for NODE divided by the number of
3168 VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
3169 the created stmts must be inserted. */
3172 vect_create_mask_and_perm (gimple
*stmt
,
3173 tree mask
, int first_vec_indx
, int second_vec_indx
,
3174 gimple_stmt_iterator
*gsi
, slp_tree node
,
3175 tree vectype
, vec
<tree
> dr_chain
,
3176 int ncopies
, int vect_stmts_counter
)
3179 gimple
*perm_stmt
= NULL
;
3181 tree first_vec
, second_vec
, data_ref
;
3183 stride
= SLP_TREE_NUMBER_OF_VEC_STMTS (node
) / ncopies
;
3185 /* Initialize the vect stmts of NODE to properly insert the generated
3187 for (i
= SLP_TREE_VEC_STMTS (node
).length ();
3188 i
< (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node
); i
++)
3189 SLP_TREE_VEC_STMTS (node
).quick_push (NULL
);
3191 perm_dest
= vect_create_destination_var (gimple_assign_lhs (stmt
), vectype
);
3192 for (i
= 0; i
< ncopies
; i
++)
3194 first_vec
= dr_chain
[first_vec_indx
];
3195 second_vec
= dr_chain
[second_vec_indx
];
3197 /* Generate the permute statement. */
3198 perm_stmt
= gimple_build_assign (perm_dest
, VEC_PERM_EXPR
,
3199 first_vec
, second_vec
, mask
);
3200 data_ref
= make_ssa_name (perm_dest
, perm_stmt
);
3201 gimple_set_lhs (perm_stmt
, data_ref
);
3202 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
3204 /* Store the vector statement in NODE. */
3205 SLP_TREE_VEC_STMTS (node
)[stride
* i
+ vect_stmts_counter
] = perm_stmt
;
3207 first_vec_indx
+= stride
;
3208 second_vec_indx
+= stride
;
3213 /* Given FIRST_MASK_ELEMENT - the mask element in element representation,
3214 return in CURRENT_MASK_ELEMENT its equivalent in target specific
3215 representation. Check that the mask is valid and return FALSE if not.
3216 Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
3217 the next vector, i.e., the current first vector is not needed. */
3220 vect_get_mask_element (gimple
*stmt
, int first_mask_element
, int m
,
3221 int mask_nunits
, bool only_one_vec
, int index
,
3222 unsigned char *mask
, int *current_mask_element
,
3223 bool *need_next_vector
, int *number_of_mask_fixes
,
3224 bool *mask_fixed
, bool *needs_first_vector
)
3228 /* Convert to target specific representation. */
3229 *current_mask_element
= first_mask_element
+ m
;
3230 /* Adjust the value in case it's a mask for second and third vectors. */
3231 *current_mask_element
-= mask_nunits
* (*number_of_mask_fixes
- 1);
3233 if (*current_mask_element
< 0)
3235 if (dump_enabled_p ())
3237 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3238 "permutation requires past vector ");
3239 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3240 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3245 if (*current_mask_element
< mask_nunits
)
3246 *needs_first_vector
= true;
3248 /* We have only one input vector to permute but the mask accesses values in
3249 the next vector as well. */
3250 if (only_one_vec
&& *current_mask_element
>= mask_nunits
)
3252 if (dump_enabled_p ())
3254 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3255 "permutation requires at least two vectors ");
3256 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3257 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3263 /* The mask requires the next vector. */
3264 while (*current_mask_element
>= mask_nunits
* 2)
3266 if (*needs_first_vector
|| *mask_fixed
)
3268 /* We either need the first vector too or have already moved to the
3269 next vector. In both cases, this permutation needs three
3271 if (dump_enabled_p ())
3273 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3274 "permutation requires at "
3275 "least three vectors ");
3276 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3277 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3283 /* We move to the next vector, dropping the first one and working with
3284 the second and the third - we need to adjust the values of the mask
3286 *current_mask_element
-= mask_nunits
* *number_of_mask_fixes
;
3288 for (i
= 0; i
< index
; i
++)
3289 mask
[i
] -= mask_nunits
* *number_of_mask_fixes
;
3291 (*number_of_mask_fixes
)++;
3295 *need_next_vector
= *mask_fixed
;
3297 /* This was the last element of this mask. Start a new one. */
3298 if (index
== mask_nunits
- 1)
3300 *number_of_mask_fixes
= 1;
3301 *mask_fixed
= false;
3302 *needs_first_vector
= false;
3309 /* Generate vector permute statements from a list of loads in DR_CHAIN.
3310 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
3311 permute statements for the SLP node NODE of the SLP instance
3312 SLP_NODE_INSTANCE. */
3315 vect_transform_slp_perm_load (slp_tree node
, vec
<tree
> dr_chain
,
3316 gimple_stmt_iterator
*gsi
, int vf
,
3317 slp_instance slp_node_instance
, bool analyze_only
)
3319 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3320 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3321 tree mask_element_type
= NULL_TREE
, mask_type
;
3322 int i
, j
, k
, nunits
, vec_index
= 0;
3323 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3324 int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_node_instance
);
3325 int first_mask_element
;
3326 int index
, unroll_factor
, current_mask_element
, ncopies
;
3327 unsigned char *mask
;
3328 bool only_one_vec
= false, need_next_vector
= false;
3329 int first_vec_index
, second_vec_index
, orig_vec_stmts_num
, vect_stmts_counter
;
3330 int number_of_mask_fixes
= 1;
3331 bool mask_fixed
= false;
3332 bool needs_first_vector
= false;
3335 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3338 stmt_info
= vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info
));
3340 mode
= TYPE_MODE (vectype
);
3342 if (!can_vec_perm_p (mode
, false, NULL
))
3344 if (dump_enabled_p ())
3346 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3347 "no vect permute for ");
3348 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3349 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3354 /* The generic VEC_PERM_EXPR code always uses an integral type of the
3355 same size as the vector element being permuted. */
3356 mask_element_type
= lang_hooks
.types
.type_for_mode
3357 (int_mode_for_mode (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3358 mask_type
= get_vectype_for_scalar_type (mask_element_type
);
3359 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3360 mask
= XALLOCAVEC (unsigned char, nunits
);
3361 unroll_factor
= SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3363 /* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
3364 unrolling factor. */
3366 = (STMT_VINFO_GROUP_SIZE (stmt_info
)
3367 * SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
)
3368 + nunits
- 1) / nunits
;
3369 if (orig_vec_stmts_num
== 1)
3370 only_one_vec
= true;
3372 /* Number of copies is determined by the final vectorization factor
3373 relatively to SLP_NODE_INSTANCE unrolling factor. */
3374 ncopies
= vf
/ SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3376 /* Generate permutation masks for every NODE. Number of masks for each NODE
3377 is equal to GROUP_SIZE.
3378 E.g., we have a group of three nodes with three loads from the same
3379 location in each node, and the vector size is 4. I.e., we have a
3380 a0b0c0a1b1c1... sequence and we need to create the following vectors:
3381 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
3382 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
3385 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9}.
3386 The last mask is illegal since we assume two operands for permute
3387 operation, and the mask element values can't be outside that range.
3388 Hence, the last mask must be converted into {2,5,5,5}.
3389 For the first two permutations we need the first and the second input
3390 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
3391 we need the second and the third vectors: {b1,c1,a2,b2} and
3396 vect_stmts_counter
= 0;
3398 first_vec_index
= vec_index
++;
3400 second_vec_index
= first_vec_index
;
3402 second_vec_index
= vec_index
++;
3404 for (j
= 0; j
< unroll_factor
; j
++)
3406 for (k
= 0; k
< group_size
; k
++)
3408 i
= SLP_TREE_LOAD_PERMUTATION (node
)[k
];
3409 first_mask_element
= i
+ j
* STMT_VINFO_GROUP_SIZE (stmt_info
);
3410 if (!vect_get_mask_element (stmt
, first_mask_element
, 0,
3411 nunits
, only_one_vec
, index
,
3412 mask
, ¤t_mask_element
,
3414 &number_of_mask_fixes
, &mask_fixed
,
3415 &needs_first_vector
))
3417 gcc_assert (current_mask_element
>= 0
3418 && current_mask_element
< 2 * nunits
);
3419 mask
[index
++] = current_mask_element
;
3421 if (index
== nunits
)
3424 if (!can_vec_perm_p (mode
, false, mask
))
3426 if (dump_enabled_p ())
3428 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
3430 "unsupported vect permute { ");
3431 for (i
= 0; i
< nunits
; ++i
)
3432 dump_printf (MSG_MISSED_OPTIMIZATION
, "%d ",
3434 dump_printf (MSG_MISSED_OPTIMIZATION
, "}\n");
3442 tree mask_vec
, *mask_elts
;
3443 mask_elts
= XALLOCAVEC (tree
, nunits
);
3444 for (l
= 0; l
< nunits
; ++l
)
3445 mask_elts
[l
] = build_int_cst (mask_element_type
,
3447 mask_vec
= build_vector (mask_type
, mask_elts
);
3449 if (need_next_vector
)
3451 first_vec_index
= second_vec_index
;
3452 second_vec_index
= vec_index
;
3455 vect_create_mask_and_perm (stmt
,
3456 mask_vec
, first_vec_index
, second_vec_index
,
3457 gsi
, node
, vectype
, dr_chain
,
3458 ncopies
, vect_stmts_counter
++);
3470 /* Vectorize SLP instance tree in postorder. */
3473 vect_schedule_slp_instance (slp_tree node
, slp_instance instance
,
3474 unsigned int vectorization_factor
)
3477 bool grouped_store
, is_store
;
3478 gimple_stmt_iterator si
;
3479 stmt_vec_info stmt_info
;
3480 unsigned int vec_stmts_size
, nunits
, group_size
;
3488 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3489 vect_schedule_slp_instance (child
, instance
, vectorization_factor
);
3491 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3492 stmt_info
= vinfo_for_stmt (stmt
);
3494 /* VECTYPE is the type of the destination. */
3495 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3496 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (vectype
);
3497 group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
3499 /* For each SLP instance calculate number of vector stmts to be created
3500 for the scalar stmts in each node of the SLP tree. Number of vector
3501 elements in one vector iteration is the number of scalar elements in
3502 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
3504 Unless this is a SLP reduction in which case the number of vector
3505 stmts is equal to the number of vector stmts of the children. */
3506 if (GROUP_FIRST_ELEMENT (stmt_info
)
3507 && !STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3508 vec_stmts_size
= SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_CHILDREN (node
)[0]);
3510 vec_stmts_size
= (vectorization_factor
* group_size
) / nunits
;
3512 if (!SLP_TREE_VEC_STMTS (node
).exists ())
3514 SLP_TREE_VEC_STMTS (node
).create (vec_stmts_size
);
3515 SLP_TREE_NUMBER_OF_VEC_STMTS (node
) = vec_stmts_size
;
3518 if (dump_enabled_p ())
3520 dump_printf_loc (MSG_NOTE
,vect_location
,
3521 "------>vectorizing SLP node starting from: ");
3522 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3523 dump_printf (MSG_NOTE
, "\n");
3526 /* Vectorized stmts go before the last scalar stmt which is where
3527 all uses are ready. */
3528 si
= gsi_for_stmt (vect_find_last_scalar_stmt_in_slp (node
));
3530 /* Mark the first element of the reduction chain as reduction to properly
3531 transform the node. In the analysis phase only the last element of the
3532 chain is marked as reduction. */
3533 if (GROUP_FIRST_ELEMENT (stmt_info
) && !STMT_VINFO_GROUPED_ACCESS (stmt_info
)
3534 && GROUP_FIRST_ELEMENT (stmt_info
) == stmt
)
3536 STMT_VINFO_DEF_TYPE (stmt_info
) = vect_reduction_def
;
3537 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
3540 /* Handle two-operation SLP nodes by vectorizing the group with
3541 both operations and then performing a merge. */
3542 if (SLP_TREE_TWO_OPERATORS (node
))
3544 enum tree_code code0
= gimple_assign_rhs_code (stmt
);
3545 enum tree_code ocode
;
3547 unsigned char *mask
= XALLOCAVEC (unsigned char, group_size
);
3548 bool allsame
= true;
3549 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, ostmt
)
3550 if (gimple_assign_rhs_code (ostmt
) != code0
)
3554 ocode
= gimple_assign_rhs_code (ostmt
);
3563 tree tmask
= NULL_TREE
;
3564 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3565 v0
= SLP_TREE_VEC_STMTS (node
).copy ();
3566 SLP_TREE_VEC_STMTS (node
).truncate (0);
3567 gimple_assign_set_rhs_code (stmt
, ocode
);
3568 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3569 gimple_assign_set_rhs_code (stmt
, code0
);
3570 v1
= SLP_TREE_VEC_STMTS (node
).copy ();
3571 SLP_TREE_VEC_STMTS (node
).truncate (0);
3572 tree meltype
= build_nonstandard_integer_type
3573 (GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3574 tree mvectype
= get_same_sized_vectype (meltype
, vectype
);
3576 for (j
= 0; j
< v0
.length (); ++j
)
3578 tree
*melts
= XALLOCAVEC (tree
, TYPE_VECTOR_SUBPARTS (vectype
));
3579 for (l
= 0; l
< TYPE_VECTOR_SUBPARTS (vectype
); ++l
)
3581 if (k
>= group_size
)
3583 melts
[l
] = build_int_cst
3584 (meltype
, mask
[k
++] * TYPE_VECTOR_SUBPARTS (vectype
) + l
);
3586 tmask
= build_vector (mvectype
, melts
);
3588 /* ??? Not all targets support a VEC_PERM_EXPR with a
3589 constant mask that would translate to a vec_merge RTX
3590 (with their vec_perm_const_ok). We can either not
3591 vectorize in that case or let veclower do its job.
3592 Unfortunately that isn't too great and at least for
3593 plus/minus we'd eventually like to match targets
3594 vector addsub instructions. */
3596 vstmt
= gimple_build_assign (make_ssa_name (vectype
),
3598 gimple_assign_lhs (v0
[j
]),
3599 gimple_assign_lhs (v1
[j
]), tmask
);
3600 vect_finish_stmt_generation (stmt
, vstmt
, &si
);
3601 SLP_TREE_VEC_STMTS (node
).quick_push (vstmt
);
3608 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3612 /* Replace scalar calls from SLP node NODE with setting of their lhs to zero.
3613 For loop vectorization this is done in vectorizable_call, but for SLP
3614 it needs to be deferred until end of vect_schedule_slp, because multiple
3615 SLP instances may refer to the same scalar stmt. */
3618 vect_remove_slp_scalar_calls (slp_tree node
)
3620 gimple
*stmt
, *new_stmt
;
3621 gimple_stmt_iterator gsi
;
3625 stmt_vec_info stmt_info
;
3630 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3631 vect_remove_slp_scalar_calls (child
);
3633 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
3635 if (!is_gimple_call (stmt
) || gimple_bb (stmt
) == NULL
)
3637 stmt_info
= vinfo_for_stmt (stmt
);
3638 if (stmt_info
== NULL
3639 || is_pattern_stmt_p (stmt_info
)
3640 || !PURE_SLP_STMT (stmt_info
))
3642 lhs
= gimple_call_lhs (stmt
);
3643 new_stmt
= gimple_build_assign (lhs
, build_zero_cst (TREE_TYPE (lhs
)));
3644 set_vinfo_for_stmt (new_stmt
, stmt_info
);
3645 set_vinfo_for_stmt (stmt
, NULL
);
3646 STMT_VINFO_STMT (stmt_info
) = new_stmt
;
3647 gsi
= gsi_for_stmt (stmt
);
3648 gsi_replace (&gsi
, new_stmt
, false);
3649 SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt
)) = new_stmt
;
3653 /* Generate vector code for all SLP instances in the loop/basic block. */
3656 vect_schedule_slp (vec_info
*vinfo
)
3658 vec
<slp_instance
> slp_instances
;
3659 slp_instance instance
;
3661 bool is_store
= false;
3663 slp_instances
= vinfo
->slp_instances
;
3664 if (is_a
<loop_vec_info
> (vinfo
))
3665 vf
= as_a
<loop_vec_info
> (vinfo
)->vectorization_factor
;
3669 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3671 /* Schedule the tree of INSTANCE. */
3672 is_store
= vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance
),
3674 if (dump_enabled_p ())
3675 dump_printf_loc (MSG_NOTE
, vect_location
,
3676 "vectorizing stmts using SLP.\n");
3679 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3681 slp_tree root
= SLP_INSTANCE_TREE (instance
);
3684 gimple_stmt_iterator gsi
;
3686 /* Remove scalar call stmts. Do not do this for basic-block
3687 vectorization as not all uses may be vectorized.
3688 ??? Why should this be necessary? DCE should be able to
3689 remove the stmts itself.
3690 ??? For BB vectorization we can as well remove scalar
3691 stmts starting from the SLP tree root if they have no
3693 if (is_a
<loop_vec_info
> (vinfo
))
3694 vect_remove_slp_scalar_calls (root
);
3696 for (j
= 0; SLP_TREE_SCALAR_STMTS (root
).iterate (j
, &store
)
3697 && j
< SLP_INSTANCE_GROUP_SIZE (instance
); j
++)
3699 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store
)))
3702 if (is_pattern_stmt_p (vinfo_for_stmt (store
)))
3703 store
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (store
));
3704 /* Free the attached stmt_vec_info and remove the stmt. */
3705 gsi
= gsi_for_stmt (store
);
3706 unlink_stmt_vdef (store
);
3707 gsi_remove (&gsi
, true);
3708 release_defs (store
);
3709 free_stmt_vec_info (store
);