1 /* SLP - Basic Block Vectorization
2 Copyright (C) 2007-2016 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
)
54 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
55 vect_free_slp_tree (child
);
58 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
59 /* After transform some stmts are removed and thus their vinfo is gone. */
60 if (vinfo_for_stmt (stmt
))
62 gcc_assert (STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmt
)) > 0);
63 STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmt
))--;
66 SLP_TREE_CHILDREN (node
).release ();
67 SLP_TREE_SCALAR_STMTS (node
).release ();
68 SLP_TREE_VEC_STMTS (node
).release ();
69 SLP_TREE_LOAD_PERMUTATION (node
).release ();
75 /* Free the memory allocated for the SLP instance. */
78 vect_free_slp_instance (slp_instance instance
)
80 vect_free_slp_tree (SLP_INSTANCE_TREE (instance
));
81 SLP_INSTANCE_LOADS (instance
).release ();
86 /* Create an SLP node for SCALAR_STMTS. */
89 vect_create_new_slp_node (vec
<gimple
*> scalar_stmts
)
92 gimple
*stmt
= scalar_stmts
[0];
95 if (is_gimple_call (stmt
))
96 nops
= gimple_call_num_args (stmt
);
97 else if (is_gimple_assign (stmt
))
99 nops
= gimple_num_ops (stmt
) - 1;
100 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
106 node
= XNEW (struct _slp_tree
);
107 SLP_TREE_SCALAR_STMTS (node
) = scalar_stmts
;
108 SLP_TREE_VEC_STMTS (node
).create (0);
109 SLP_TREE_CHILDREN (node
).create (nops
);
110 SLP_TREE_LOAD_PERMUTATION (node
) = vNULL
;
111 SLP_TREE_TWO_OPERATORS (node
) = false;
112 SLP_TREE_DEF_TYPE (node
) = vect_internal_def
;
115 FOR_EACH_VEC_ELT (scalar_stmts
, i
, stmt
)
116 STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmt
))++;
122 /* This structure is used in creation of an SLP tree. Each instance
123 corresponds to the same operand in a group of scalar stmts in an SLP
125 typedef struct _slp_oprnd_info
127 /* Def-stmts for the operands. */
128 vec
<gimple
*> def_stmts
;
129 /* Information about the first statement, its vector def-type, type, the
130 operand itself in case it's constant, and an indication if it's a pattern
132 enum vect_def_type first_dt
;
139 /* Allocate operands info for NOPS operands, and GROUP_SIZE def-stmts for each
141 static vec
<slp_oprnd_info
>
142 vect_create_oprnd_info (int nops
, int group_size
)
145 slp_oprnd_info oprnd_info
;
146 vec
<slp_oprnd_info
> oprnds_info
;
148 oprnds_info
.create (nops
);
149 for (i
= 0; i
< nops
; i
++)
151 oprnd_info
= XNEW (struct _slp_oprnd_info
);
152 oprnd_info
->def_stmts
.create (group_size
);
153 oprnd_info
->first_dt
= vect_uninitialized_def
;
154 oprnd_info
->first_op_type
= NULL_TREE
;
155 oprnd_info
->first_pattern
= false;
156 oprnd_info
->second_pattern
= false;
157 oprnds_info
.quick_push (oprnd_info
);
164 /* Free operands info. */
167 vect_free_oprnd_info (vec
<slp_oprnd_info
> &oprnds_info
)
170 slp_oprnd_info oprnd_info
;
172 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
174 oprnd_info
->def_stmts
.release ();
175 XDELETE (oprnd_info
);
178 oprnds_info
.release ();
182 /* Find the place of the data-ref in STMT in the interleaving chain that starts
183 from FIRST_STMT. Return -1 if the data-ref is not a part of the chain. */
186 vect_get_place_in_interleaving_chain (gimple
*stmt
, gimple
*first_stmt
)
188 gimple
*next_stmt
= first_stmt
;
191 if (first_stmt
!= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
196 if (next_stmt
== stmt
)
198 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
200 result
+= GROUP_GAP (vinfo_for_stmt (next_stmt
));
208 /* Get the defs for the rhs of STMT (collect them in OPRNDS_INFO), check that
209 they are of a valid type and that they match the defs of the first stmt of
210 the SLP group (stored in OPRNDS_INFO). If there was a fatal error
211 return -1, if the error could be corrected by swapping operands of the
212 operation return 1, if everything is ok return 0. */
215 vect_get_and_check_slp_defs (vec_info
*vinfo
,
216 gimple
*stmt
, unsigned stmt_num
,
217 vec
<slp_oprnd_info
> *oprnds_info
)
220 unsigned int i
, number_of_oprnds
;
222 enum vect_def_type dt
= vect_uninitialized_def
;
223 bool pattern
= false;
224 slp_oprnd_info oprnd_info
;
225 int first_op_idx
= 1;
226 bool commutative
= false;
227 bool first_op_cond
= false;
228 bool first
= stmt_num
== 0;
229 bool second
= stmt_num
== 1;
231 if (is_gimple_call (stmt
))
233 number_of_oprnds
= gimple_call_num_args (stmt
);
236 else if (is_gimple_assign (stmt
))
238 enum tree_code code
= gimple_assign_rhs_code (stmt
);
239 number_of_oprnds
= gimple_num_ops (stmt
) - 1;
240 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
241 && COMPARISON_CLASS_P (gimple_assign_rhs1 (stmt
)))
243 first_op_cond
= true;
248 commutative
= commutative_tree_code (code
);
253 bool swapped
= false;
254 for (i
= 0; i
< number_of_oprnds
; i
++)
259 if (i
== 0 || i
== 1)
260 oprnd
= TREE_OPERAND (gimple_op (stmt
, first_op_idx
),
263 oprnd
= gimple_op (stmt
, first_op_idx
+ i
- 1);
266 oprnd
= gimple_op (stmt
, first_op_idx
+ (swapped
? !i
: i
));
268 oprnd_info
= (*oprnds_info
)[i
];
270 if (!vect_is_simple_use (oprnd
, vinfo
, &def_stmt
, &dt
))
272 if (dump_enabled_p ())
274 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
275 "Build SLP failed: can't analyze def for ");
276 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
277 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
283 /* Check if DEF_STMT is a part of a pattern in LOOP and get the def stmt
284 from the pattern. Check that all the stmts of the node are in the
286 if (def_stmt
&& gimple_bb (def_stmt
)
287 && vect_stmt_in_region_p (vinfo
, def_stmt
)
288 && vinfo_for_stmt (def_stmt
)
289 && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (def_stmt
))
290 && !STMT_VINFO_RELEVANT (vinfo_for_stmt (def_stmt
))
291 && !STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt
)))
294 if (!first
&& !oprnd_info
->first_pattern
295 /* Allow different pattern state for the defs of the
296 first stmt in reduction chains. */
297 && (oprnd_info
->first_dt
!= vect_reduction_def
298 || (!second
&& !oprnd_info
->second_pattern
)))
308 if (dump_enabled_p ())
310 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
311 "Build SLP failed: some of the stmts"
312 " are in a pattern, and others are not ");
313 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
314 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
320 def_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
));
321 dt
= STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
));
323 if (dt
== vect_unknown_def_type
)
325 if (dump_enabled_p ())
326 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
327 "Unsupported pattern.\n");
331 switch (gimple_code (def_stmt
))
338 if (dump_enabled_p ())
339 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
340 "unsupported defining stmt:\n");
346 oprnd_info
->second_pattern
= pattern
;
350 oprnd_info
->first_dt
= dt
;
351 oprnd_info
->first_pattern
= pattern
;
352 oprnd_info
->first_op_type
= TREE_TYPE (oprnd
);
356 /* Not first stmt of the group, check that the def-stmt/s match
357 the def-stmt/s of the first stmt. Allow different definition
358 types for reduction chains: the first stmt must be a
359 vect_reduction_def (a phi node), and the rest
360 vect_internal_def. */
361 if (((oprnd_info
->first_dt
!= dt
362 && !(oprnd_info
->first_dt
== vect_reduction_def
363 && dt
== vect_internal_def
)
364 && !((oprnd_info
->first_dt
== vect_external_def
365 || oprnd_info
->first_dt
== vect_constant_def
)
366 && (dt
== vect_external_def
367 || dt
== vect_constant_def
)))
368 || !types_compatible_p (oprnd_info
->first_op_type
,
371 /* Try swapping operands if we got a mismatch. */
380 if (dump_enabled_p ())
381 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
382 "Build SLP failed: different types\n");
388 /* Check the types of the definitions. */
391 case vect_constant_def
:
392 case vect_external_def
:
393 case vect_reduction_def
:
396 case vect_internal_def
:
397 oprnd_info
->def_stmts
.quick_push (def_stmt
);
401 /* FORNOW: Not supported. */
402 if (dump_enabled_p ())
404 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
405 "Build SLP failed: illegal type of def ");
406 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
407 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
417 /* If there are already uses of this stmt in a SLP instance then
418 we've committed to the operand order and can't swap it. */
419 if (STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmt
)) != 0)
421 if (dump_enabled_p ())
423 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
424 "Build SLP failed: cannot swap operands of "
426 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
433 tree cond
= gimple_assign_rhs1 (stmt
);
434 swap_ssa_operands (stmt
, &TREE_OPERAND (cond
, 0),
435 &TREE_OPERAND (cond
, 1));
436 TREE_SET_CODE (cond
, swap_tree_comparison (TREE_CODE (cond
)));
439 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
440 gimple_assign_rhs2_ptr (stmt
));
441 if (dump_enabled_p ())
443 dump_printf_loc (MSG_NOTE
, vect_location
,
444 "swapped operands to match def types in ");
445 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
453 /* Verify if the scalar stmts STMTS are isomorphic, require data
454 permutation or are of unsupported types of operation. Return
455 true if they are, otherwise return false and indicate in *MATCHES
456 which stmts are not isomorphic to the first one. If MATCHES[0]
457 is false then this indicates the comparison could not be
458 carried out or the stmts will never be vectorized by SLP. */
461 vect_build_slp_tree_1 (vec_info
*vinfo
,
462 vec
<gimple
*> stmts
, unsigned int group_size
,
463 unsigned nops
, unsigned int *max_nunits
,
464 bool *matches
, bool *two_operators
)
467 gimple
*first_stmt
= stmts
[0], *stmt
= stmts
[0];
468 enum tree_code first_stmt_code
= ERROR_MARK
;
469 enum tree_code alt_stmt_code
= ERROR_MARK
;
470 enum tree_code rhs_code
= ERROR_MARK
;
471 enum tree_code first_cond_code
= ERROR_MARK
;
473 bool need_same_oprnds
= false;
474 tree vectype
= NULL_TREE
, scalar_type
, first_op1
= NULL_TREE
;
477 machine_mode optab_op2_mode
;
478 machine_mode vec_mode
;
480 gimple
*first_load
= NULL
, *prev_first_load
= NULL
;
482 /* For every stmt in NODE find its def stmt/s. */
483 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
487 if (dump_enabled_p ())
489 dump_printf_loc (MSG_NOTE
, vect_location
, "Build SLP for ");
490 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
493 /* Fail to vectorize statements marked as unvectorizable. */
494 if (!STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt
)))
496 if (dump_enabled_p ())
498 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
499 "Build SLP failed: unvectorizable statement ");
500 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
501 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
503 /* Fatal mismatch. */
508 lhs
= gimple_get_lhs (stmt
);
509 if (lhs
== NULL_TREE
)
511 if (dump_enabled_p ())
513 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
514 "Build SLP failed: not GIMPLE_ASSIGN nor "
516 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
517 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
519 /* Fatal mismatch. */
524 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
, &dummy
);
525 vectype
= get_vectype_for_scalar_type (scalar_type
);
528 if (dump_enabled_p ())
530 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
531 "Build SLP failed: unsupported data-type ");
532 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
534 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
536 /* Fatal mismatch. */
541 /* If populating the vector type requires unrolling then fail
542 before adjusting *max_nunits for basic-block vectorization. */
543 if (is_a
<bb_vec_info
> (vinfo
)
544 && TYPE_VECTOR_SUBPARTS (vectype
) > group_size
)
546 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
547 "Build SLP failed: unrolling required "
548 "in basic block SLP\n");
549 /* Fatal mismatch. */
554 /* In case of multiple types we need to detect the smallest type. */
555 if (*max_nunits
< TYPE_VECTOR_SUBPARTS (vectype
))
556 *max_nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
558 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
560 rhs_code
= CALL_EXPR
;
561 if (gimple_call_internal_p (call_stmt
)
562 || gimple_call_tail_p (call_stmt
)
563 || gimple_call_noreturn_p (call_stmt
)
564 || !gimple_call_nothrow_p (call_stmt
)
565 || gimple_call_chain (call_stmt
))
567 if (dump_enabled_p ())
569 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
570 "Build SLP failed: unsupported call type ");
571 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
573 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
575 /* Fatal mismatch. */
581 rhs_code
= gimple_assign_rhs_code (stmt
);
583 /* Check the operation. */
586 first_stmt_code
= rhs_code
;
588 /* Shift arguments should be equal in all the packed stmts for a
589 vector shift with scalar shift operand. */
590 if (rhs_code
== LSHIFT_EXPR
|| rhs_code
== RSHIFT_EXPR
591 || rhs_code
== LROTATE_EXPR
592 || rhs_code
== RROTATE_EXPR
)
594 vec_mode
= TYPE_MODE (vectype
);
596 /* First see if we have a vector/vector shift. */
597 optab
= optab_for_tree_code (rhs_code
, vectype
,
601 || optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
603 /* No vector/vector shift, try for a vector/scalar shift. */
604 optab
= optab_for_tree_code (rhs_code
, vectype
,
609 if (dump_enabled_p ())
610 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
611 "Build SLP failed: no optab.\n");
612 /* Fatal mismatch. */
616 icode
= (int) optab_handler (optab
, vec_mode
);
617 if (icode
== CODE_FOR_nothing
)
619 if (dump_enabled_p ())
620 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
622 "op not supported by target.\n");
623 /* Fatal mismatch. */
627 optab_op2_mode
= insn_data
[icode
].operand
[2].mode
;
628 if (!VECTOR_MODE_P (optab_op2_mode
))
630 need_same_oprnds
= true;
631 first_op1
= gimple_assign_rhs2 (stmt
);
635 else if (rhs_code
== WIDEN_LSHIFT_EXPR
)
637 need_same_oprnds
= true;
638 first_op1
= gimple_assign_rhs2 (stmt
);
643 if (first_stmt_code
!= rhs_code
644 && alt_stmt_code
== ERROR_MARK
)
645 alt_stmt_code
= rhs_code
;
646 if (first_stmt_code
!= rhs_code
647 && (first_stmt_code
!= IMAGPART_EXPR
648 || rhs_code
!= REALPART_EXPR
)
649 && (first_stmt_code
!= REALPART_EXPR
650 || rhs_code
!= IMAGPART_EXPR
)
651 /* Handle mismatches in plus/minus by computing both
652 and merging the results. */
653 && !((first_stmt_code
== PLUS_EXPR
654 || first_stmt_code
== MINUS_EXPR
)
655 && (alt_stmt_code
== PLUS_EXPR
656 || alt_stmt_code
== MINUS_EXPR
)
657 && rhs_code
== alt_stmt_code
)
658 && !(STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
659 && (first_stmt_code
== ARRAY_REF
660 || first_stmt_code
== BIT_FIELD_REF
661 || first_stmt_code
== INDIRECT_REF
662 || first_stmt_code
== COMPONENT_REF
663 || first_stmt_code
== MEM_REF
)))
665 if (dump_enabled_p ())
667 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
668 "Build SLP failed: different operation "
670 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
671 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
673 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
681 && !operand_equal_p (first_op1
, gimple_assign_rhs2 (stmt
), 0))
683 if (dump_enabled_p ())
685 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
686 "Build SLP failed: different shift "
688 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
689 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
695 if (rhs_code
== CALL_EXPR
)
697 gimple
*first_stmt
= stmts
[0];
698 if (gimple_call_num_args (stmt
) != nops
699 || !operand_equal_p (gimple_call_fn (first_stmt
),
700 gimple_call_fn (stmt
), 0)
701 || gimple_call_fntype (first_stmt
)
702 != gimple_call_fntype (stmt
))
704 if (dump_enabled_p ())
706 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
707 "Build SLP failed: different calls in ");
708 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
710 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
718 /* Grouped store or load. */
719 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
721 if (REFERENCE_CLASS_P (lhs
))
729 first_load
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
));
732 /* Check that there are no loads from different interleaving
733 chains in the same node. */
734 if (prev_first_load
!= first_load
)
736 if (dump_enabled_p ())
738 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
740 "Build SLP failed: different "
741 "interleaving chains in one node ");
742 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
744 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
751 prev_first_load
= first_load
;
753 } /* Grouped access. */
756 if (TREE_CODE_CLASS (rhs_code
) == tcc_reference
)
758 /* Not grouped load. */
759 if (dump_enabled_p ())
761 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
762 "Build SLP failed: not grouped load ");
763 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
764 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
767 /* FORNOW: Not grouped loads are not supported. */
768 /* Fatal mismatch. */
773 /* Not memory operation. */
774 if (TREE_CODE_CLASS (rhs_code
) != tcc_binary
775 && TREE_CODE_CLASS (rhs_code
) != tcc_unary
776 && TREE_CODE_CLASS (rhs_code
) != tcc_expression
777 && TREE_CODE_CLASS (rhs_code
) != tcc_comparison
778 && rhs_code
!= CALL_EXPR
)
780 if (dump_enabled_p ())
782 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
783 "Build SLP failed: operation");
784 dump_printf (MSG_MISSED_OPTIMIZATION
, " unsupported ");
785 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
786 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
788 /* Fatal mismatch. */
793 if (rhs_code
== COND_EXPR
)
795 tree cond_expr
= gimple_assign_rhs1 (stmt
);
798 first_cond_code
= TREE_CODE (cond_expr
);
799 else if (first_cond_code
!= TREE_CODE (cond_expr
))
801 if (dump_enabled_p ())
803 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
804 "Build SLP failed: different"
806 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
808 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
819 for (i
= 0; i
< group_size
; ++i
)
823 /* If we allowed a two-operation SLP node verify the target can cope
824 with the permute we are going to use. */
825 if (alt_stmt_code
!= ERROR_MARK
826 && TREE_CODE_CLASS (alt_stmt_code
) != tcc_reference
)
829 = XALLOCAVEC (unsigned char, TYPE_VECTOR_SUBPARTS (vectype
));
830 for (i
= 0; i
< TYPE_VECTOR_SUBPARTS (vectype
); ++i
)
833 if (gimple_assign_rhs_code (stmts
[i
% group_size
]) == alt_stmt_code
)
834 sel
[i
] += TYPE_VECTOR_SUBPARTS (vectype
);
836 if (!can_vec_perm_p (TYPE_MODE (vectype
), false, sel
))
838 for (i
= 0; i
< group_size
; ++i
)
839 if (gimple_assign_rhs_code (stmts
[i
]) == alt_stmt_code
)
842 if (dump_enabled_p ())
844 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
845 "Build SLP failed: different operation "
847 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
849 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
851 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
857 *two_operators
= true;
863 /* Recursively build an SLP tree starting from NODE.
864 Fail (and return a value not equal to zero) if def-stmts are not
865 isomorphic, require data permutation or are of unsupported types of
866 operation. Otherwise, return 0.
867 The value returned is the depth in the SLP tree where a mismatch
871 vect_build_slp_tree (vec_info
*vinfo
,
872 vec
<gimple
*> stmts
, unsigned int group_size
,
873 unsigned int *max_nunits
,
874 vec
<slp_tree
> *loads
,
875 bool *matches
, unsigned *npermutes
, unsigned *tree_size
,
876 unsigned max_tree_size
)
878 unsigned nops
, i
, this_tree_size
= 0, this_max_nunits
= *max_nunits
;
885 if (is_gimple_call (stmt
))
886 nops
= gimple_call_num_args (stmt
);
887 else if (is_gimple_assign (stmt
))
889 nops
= gimple_num_ops (stmt
) - 1;
890 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
896 bool two_operators
= false;
897 if (!vect_build_slp_tree_1 (vinfo
,
898 stmts
, group_size
, nops
,
899 &this_max_nunits
, matches
, &two_operators
))
902 /* If the SLP node is a load, terminate the recursion. */
903 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
904 && DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
906 *max_nunits
= this_max_nunits
;
907 node
= vect_create_new_slp_node (stmts
);
908 loads
->safe_push (node
);
912 /* Get at the operands, verifying they are compatible. */
913 vec
<slp_oprnd_info
> oprnds_info
= vect_create_oprnd_info (nops
, group_size
);
914 slp_oprnd_info oprnd_info
;
915 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
917 switch (vect_get_and_check_slp_defs (vinfo
, stmt
, i
, &oprnds_info
))
923 vect_free_oprnd_info (oprnds_info
);
930 for (i
= 0; i
< group_size
; ++i
)
933 vect_free_oprnd_info (oprnds_info
);
937 auto_vec
<slp_tree
, 4> children
;
938 auto_vec
<slp_tree
> this_loads
;
942 /* Create SLP_TREE nodes for the definition node/s. */
943 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
946 unsigned old_nloads
= this_loads
.length ();
947 unsigned old_tree_size
= this_tree_size
;
950 if (oprnd_info
->first_dt
!= vect_internal_def
)
953 if (++this_tree_size
> max_tree_size
)
955 FOR_EACH_VEC_ELT (children
, j
, child
)
956 vect_free_slp_tree (child
);
957 vect_free_oprnd_info (oprnds_info
);
961 if ((child
= vect_build_slp_tree (vinfo
, oprnd_info
->def_stmts
,
962 group_size
, &this_max_nunits
,
963 &this_loads
, matches
, npermutes
,
965 max_tree_size
)) != NULL
)
967 /* If we have all children of child built up from scalars then just
968 throw that away and build it up this node from scalars. */
969 if (!SLP_TREE_CHILDREN (child
).is_empty ()
970 /* ??? Rejecting patterns this way doesn't work. We'd have to
971 do extra work to cancel the pattern so the uses see the
973 && !is_pattern_stmt_p
974 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child
)[0])))
978 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
979 if (SLP_TREE_DEF_TYPE (grandchild
) == vect_internal_def
)
984 this_loads
.truncate (old_nloads
);
985 this_tree_size
= old_tree_size
;
986 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
987 vect_free_slp_tree (grandchild
);
988 SLP_TREE_CHILDREN (child
).truncate (0);
990 dump_printf_loc (MSG_NOTE
, vect_location
,
991 "Building parent vector operands from "
992 "scalars instead\n");
993 oprnd_info
->def_stmts
= vNULL
;
994 SLP_TREE_DEF_TYPE (child
) = vect_external_def
;
995 children
.safe_push (child
);
1000 oprnd_info
->def_stmts
= vNULL
;
1001 children
.safe_push (child
);
1005 /* If the SLP build failed fatally and we analyze a basic-block
1006 simply treat nodes we fail to build as externally defined
1007 (and thus build vectors from the scalar defs).
1008 The cost model will reject outright expensive cases.
1009 ??? This doesn't treat cases where permutation ultimatively
1010 fails (or we don't try permutation below). Ideally we'd
1011 even compute a permutation that will end up with the maximum
1013 if (is_a
<bb_vec_info
> (vinfo
)
1015 /* ??? Rejecting patterns this way doesn't work. We'd have to
1016 do extra work to cancel the pattern so the uses see the
1018 && !is_pattern_stmt_p (vinfo_for_stmt (stmt
)))
1020 dump_printf_loc (MSG_NOTE
, vect_location
,
1021 "Building vector operands from scalars\n");
1022 child
= vect_create_new_slp_node (oprnd_info
->def_stmts
);
1023 SLP_TREE_DEF_TYPE (child
) = vect_external_def
;
1024 children
.safe_push (child
);
1025 oprnd_info
->def_stmts
= vNULL
;
1029 /* If the SLP build for operand zero failed and operand zero
1030 and one can be commutated try that for the scalar stmts
1031 that failed the match. */
1033 /* A first scalar stmt mismatch signals a fatal mismatch. */
1035 /* ??? For COND_EXPRs we can swap the comparison operands
1036 as well as the arms under some constraints. */
1038 && oprnds_info
[1]->first_dt
== vect_internal_def
1039 && is_gimple_assign (stmt
)
1040 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
1042 /* Do so only if the number of not successful permutes was nor more
1043 than a cut-ff as re-trying the recursive match on
1044 possibly each level of the tree would expose exponential
1048 /* Verify if we can safely swap or if we committed to a specific
1049 operand order already. */
1050 for (j
= 0; j
< group_size
; ++j
)
1052 && STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmts
[j
])) != 0)
1054 if (dump_enabled_p ())
1056 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1057 "Build SLP failed: cannot swap operands "
1059 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
1065 /* Swap mismatched definition stmts. */
1066 dump_printf_loc (MSG_NOTE
, vect_location
,
1067 "Re-trying with swapped operands of stmts ");
1068 for (j
= 0; j
< group_size
; ++j
)
1071 std::swap (oprnds_info
[0]->def_stmts
[j
],
1072 oprnds_info
[1]->def_stmts
[j
]);
1073 dump_printf (MSG_NOTE
, "%d ", j
);
1075 dump_printf (MSG_NOTE
, "\n");
1076 /* And try again with scratch 'matches' ... */
1077 bool *tem
= XALLOCAVEC (bool, group_size
);
1078 if ((child
= vect_build_slp_tree (vinfo
, oprnd_info
->def_stmts
,
1079 group_size
, &this_max_nunits
,
1080 &this_loads
, tem
, npermutes
,
1082 max_tree_size
)) != NULL
)
1084 /* ... so if successful we can apply the operand swapping
1085 to the GIMPLE IL. This is necessary because for example
1086 vect_get_slp_defs uses operand indexes and thus expects
1087 canonical operand order. This is also necessary even
1088 if we end up building the operand from scalars as
1089 we'll continue to process swapped operand two. */
1090 for (j
= 0; j
< group_size
; ++j
)
1092 gimple
*stmt
= stmts
[j
];
1093 gimple_set_plf (stmt
, GF_PLF_1
, false);
1095 for (j
= 0; j
< group_size
; ++j
)
1097 gimple
*stmt
= stmts
[j
];
1100 /* Avoid swapping operands twice. */
1101 if (gimple_plf (stmt
, GF_PLF_1
))
1103 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
1104 gimple_assign_rhs2_ptr (stmt
));
1105 gimple_set_plf (stmt
, GF_PLF_1
, true);
1108 /* Verify we swap all duplicates or none. */
1110 for (j
= 0; j
< group_size
; ++j
)
1112 gimple
*stmt
= stmts
[j
];
1113 gcc_assert (gimple_plf (stmt
, GF_PLF_1
) == ! matches
[j
]);
1116 /* If we have all children of child built up from scalars then
1117 just throw that away and build it up this node from scalars. */
1118 if (!SLP_TREE_CHILDREN (child
).is_empty ()
1119 /* ??? Rejecting patterns this way doesn't work. We'd have
1120 to do extra work to cancel the pattern so the uses see the
1122 && !is_pattern_stmt_p
1123 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child
)[0])))
1126 slp_tree grandchild
;
1128 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1129 if (SLP_TREE_DEF_TYPE (grandchild
) == vect_internal_def
)
1134 this_loads
.truncate (old_nloads
);
1135 this_tree_size
= old_tree_size
;
1136 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1137 vect_free_slp_tree (grandchild
);
1138 SLP_TREE_CHILDREN (child
).truncate (0);
1140 dump_printf_loc (MSG_NOTE
, vect_location
,
1141 "Building parent vector operands from "
1142 "scalars instead\n");
1143 oprnd_info
->def_stmts
= vNULL
;
1144 SLP_TREE_DEF_TYPE (child
) = vect_external_def
;
1145 children
.safe_push (child
);
1150 oprnd_info
->def_stmts
= vNULL
;
1151 children
.safe_push (child
);
1159 gcc_assert (child
== NULL
);
1160 FOR_EACH_VEC_ELT (children
, j
, child
)
1161 vect_free_slp_tree (child
);
1162 vect_free_oprnd_info (oprnds_info
);
1166 vect_free_oprnd_info (oprnds_info
);
1169 *tree_size
+= this_tree_size
;
1170 *max_nunits
= this_max_nunits
;
1171 loads
->safe_splice (this_loads
);
1173 node
= vect_create_new_slp_node (stmts
);
1174 SLP_TREE_TWO_OPERATORS (node
) = two_operators
;
1175 SLP_TREE_CHILDREN (node
).splice (children
);
1179 /* Dump a slp tree NODE using flags specified in DUMP_KIND. */
1182 vect_print_slp_tree (int dump_kind
, location_t loc
, slp_tree node
)
1188 dump_printf_loc (dump_kind
, loc
, "node%s\n",
1189 SLP_TREE_DEF_TYPE (node
) != vect_internal_def
1190 ? " (external)" : "");
1191 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1193 dump_printf_loc (dump_kind
, loc
, "\tstmt %d ", i
);
1194 dump_gimple_stmt (dump_kind
, TDF_SLIM
, stmt
, 0);
1196 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1197 vect_print_slp_tree (dump_kind
, loc
, child
);
1201 /* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
1202 If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
1203 J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
1204 stmts in NODE are to be marked. */
1207 vect_mark_slp_stmts (slp_tree node
, enum slp_vect_type mark
, int j
)
1213 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
1216 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1217 if (j
< 0 || i
== j
)
1218 STMT_SLP_TYPE (vinfo_for_stmt (stmt
)) = mark
;
1220 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1221 vect_mark_slp_stmts (child
, mark
, j
);
1225 /* Mark the statements of the tree rooted at NODE as relevant (vect_used). */
1228 vect_mark_slp_stmts_relevant (slp_tree node
)
1232 stmt_vec_info stmt_info
;
1235 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
1238 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1240 stmt_info
= vinfo_for_stmt (stmt
);
1241 gcc_assert (!STMT_VINFO_RELEVANT (stmt_info
)
1242 || STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
);
1243 STMT_VINFO_RELEVANT (stmt_info
) = vect_used_in_scope
;
1246 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1247 vect_mark_slp_stmts_relevant (child
);
1251 /* Rearrange the statements of NODE according to PERMUTATION. */
1254 vect_slp_rearrange_stmts (slp_tree node
, unsigned int group_size
,
1255 vec
<unsigned> permutation
)
1258 vec
<gimple
*> tmp_stmts
;
1262 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1263 vect_slp_rearrange_stmts (child
, group_size
, permutation
);
1265 gcc_assert (group_size
== SLP_TREE_SCALAR_STMTS (node
).length ());
1266 tmp_stmts
.create (group_size
);
1267 tmp_stmts
.quick_grow_cleared (group_size
);
1269 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1270 tmp_stmts
[permutation
[i
]] = stmt
;
1272 SLP_TREE_SCALAR_STMTS (node
).release ();
1273 SLP_TREE_SCALAR_STMTS (node
) = tmp_stmts
;
1277 /* Attempt to reorder stmts in a reduction chain so that we don't
1278 require any load permutation. Return true if that was possible,
1279 otherwise return false. */
1282 vect_attempt_slp_rearrange_stmts (slp_instance slp_instn
)
1284 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1288 slp_tree node
, load
;
1290 /* Compare all the permutation sequences to the first one. We know
1291 that at least one load is permuted. */
1292 node
= SLP_INSTANCE_LOADS (slp_instn
)[0];
1293 if (!node
->load_permutation
.exists ())
1295 for (i
= 1; SLP_INSTANCE_LOADS (slp_instn
).iterate (i
, &load
); ++i
)
1297 if (!load
->load_permutation
.exists ())
1299 FOR_EACH_VEC_ELT (load
->load_permutation
, j
, lidx
)
1300 if (lidx
!= node
->load_permutation
[j
])
1304 /* Check that the loads in the first sequence are different and there
1305 are no gaps between them. */
1306 load_index
= sbitmap_alloc (group_size
);
1307 bitmap_clear (load_index
);
1308 FOR_EACH_VEC_ELT (node
->load_permutation
, i
, lidx
)
1310 if (lidx
>= group_size
)
1312 sbitmap_free (load_index
);
1315 if (bitmap_bit_p (load_index
, lidx
))
1317 sbitmap_free (load_index
);
1320 bitmap_set_bit (load_index
, lidx
);
1322 for (i
= 0; i
< group_size
; i
++)
1323 if (!bitmap_bit_p (load_index
, i
))
1325 sbitmap_free (load_index
);
1328 sbitmap_free (load_index
);
1330 /* This permutation is valid for reduction. Since the order of the
1331 statements in the nodes is not important unless they are memory
1332 accesses, we can rearrange the statements in all the nodes
1333 according to the order of the loads. */
1334 vect_slp_rearrange_stmts (SLP_INSTANCE_TREE (slp_instn
), group_size
,
1335 node
->load_permutation
);
1337 /* We are done, no actual permutations need to be generated. */
1338 unsigned int unrolling_factor
= SLP_INSTANCE_UNROLLING_FACTOR (slp_instn
);
1339 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1341 gimple
*first_stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1342 first_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (first_stmt
));
1343 /* But we have to keep those permutations that are required because
1344 of handling of gaps. */
1345 if (unrolling_factor
== 1
1346 || (group_size
== GROUP_SIZE (vinfo_for_stmt (first_stmt
))
1347 && GROUP_GAP (vinfo_for_stmt (first_stmt
)) == 0))
1348 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1350 for (j
= 0; j
< SLP_TREE_LOAD_PERMUTATION (node
).length (); ++j
)
1351 SLP_TREE_LOAD_PERMUTATION (node
)[j
] = j
;
1357 /* Check if the required load permutations in the SLP instance
1358 SLP_INSTN are supported. */
1361 vect_supported_load_permutation_p (slp_instance slp_instn
)
1363 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1364 unsigned int i
, j
, k
, next
;
1366 gimple
*stmt
, *load
, *next_load
;
1368 if (dump_enabled_p ())
1370 dump_printf_loc (MSG_NOTE
, vect_location
, "Load permutation ");
1371 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1372 if (node
->load_permutation
.exists ())
1373 FOR_EACH_VEC_ELT (node
->load_permutation
, j
, next
)
1374 dump_printf (MSG_NOTE
, "%d ", next
);
1376 for (k
= 0; k
< group_size
; ++k
)
1377 dump_printf (MSG_NOTE
, "%d ", k
);
1378 dump_printf (MSG_NOTE
, "\n");
1381 /* In case of reduction every load permutation is allowed, since the order
1382 of the reduction statements is not important (as opposed to the case of
1383 grouped stores). The only condition we need to check is that all the
1384 load nodes are of the same size and have the same permutation (and then
1385 rearrange all the nodes of the SLP instance according to this
1388 /* Check that all the load nodes are of the same size. */
1389 /* ??? Can't we assert this? */
1390 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1391 if (SLP_TREE_SCALAR_STMTS (node
).length () != (unsigned) group_size
)
1394 node
= SLP_INSTANCE_TREE (slp_instn
);
1395 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1397 /* Reduction (there are no data-refs in the root).
1398 In reduction chain the order of the loads is not important. */
1399 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))
1400 && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1401 vect_attempt_slp_rearrange_stmts (slp_instn
);
1403 /* In basic block vectorization we allow any subchain of an interleaving
1405 FORNOW: not supported in loop SLP because of realignment compications. */
1406 if (STMT_VINFO_BB_VINFO (vinfo_for_stmt (stmt
)))
1408 /* Check whether the loads in an instance form a subchain and thus
1409 no permutation is necessary. */
1410 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1412 if (!SLP_TREE_LOAD_PERMUTATION (node
).exists ())
1414 bool subchain_p
= true;
1416 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), j
, load
)
1419 && (next_load
!= load
1420 || GROUP_GAP (vinfo_for_stmt (load
)) != 1))
1425 next_load
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (load
));
1428 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1431 /* Verify the permutation can be generated. */
1433 if (!vect_transform_slp_perm_load (node
, tem
, NULL
,
1434 1, slp_instn
, true))
1436 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
1438 "unsupported load permutation\n");
1446 /* For loop vectorization verify we can generate the permutation. */
1447 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1448 if (node
->load_permutation
.exists ()
1449 && !vect_transform_slp_perm_load
1451 SLP_INSTANCE_UNROLLING_FACTOR (slp_instn
), slp_instn
, true))
1458 /* Find the last store in SLP INSTANCE. */
1461 vect_find_last_scalar_stmt_in_slp (slp_tree node
)
1463 gimple
*last
= NULL
, *stmt
;
1465 for (int i
= 0; SLP_TREE_SCALAR_STMTS (node
).iterate (i
, &stmt
); i
++)
1467 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
1468 if (is_pattern_stmt_p (stmt_vinfo
))
1469 last
= get_later_stmt (STMT_VINFO_RELATED_STMT (stmt_vinfo
), last
);
1471 last
= get_later_stmt (stmt
, last
);
1477 /* Compute the cost for the SLP node NODE in the SLP instance INSTANCE. */
1480 vect_analyze_slp_cost_1 (slp_instance instance
, slp_tree node
,
1481 stmt_vector_for_cost
*prologue_cost_vec
,
1482 stmt_vector_for_cost
*body_cost_vec
,
1483 unsigned ncopies_for_cost
)
1488 stmt_vec_info stmt_info
;
1491 /* Recurse down the SLP tree. */
1492 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1493 if (SLP_TREE_DEF_TYPE (child
) == vect_internal_def
)
1494 vect_analyze_slp_cost_1 (instance
, child
, prologue_cost_vec
,
1495 body_cost_vec
, ncopies_for_cost
);
1497 /* Look at the first scalar stmt to determine the cost. */
1498 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1499 stmt_info
= vinfo_for_stmt (stmt
);
1500 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1502 if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info
)))
1503 vect_model_store_cost (stmt_info
, ncopies_for_cost
, false,
1504 vect_uninitialized_def
,
1505 node
, prologue_cost_vec
, body_cost_vec
);
1508 gcc_checking_assert (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)));
1509 if (SLP_TREE_LOAD_PERMUTATION (node
).exists ())
1511 /* If the load is permuted then the alignment is determined by
1512 the first group element not by the first scalar stmt DR. */
1513 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
1514 stmt_info
= vinfo_for_stmt (stmt
);
1515 /* Record the cost for the permutation. */
1516 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vec_perm
,
1517 stmt_info
, 0, vect_body
);
1518 /* And adjust the number of loads performed. */
1520 = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
1522 = (GROUP_SIZE (stmt_info
) - GROUP_GAP (stmt_info
)
1523 + nunits
- 1) / nunits
;
1524 ncopies_for_cost
*= SLP_INSTANCE_UNROLLING_FACTOR (instance
);
1526 /* Record the cost for the vector loads. */
1527 vect_model_load_cost (stmt_info
, ncopies_for_cost
, false,
1528 node
, prologue_cost_vec
, body_cost_vec
);
1534 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1535 stmt_info
, 0, vect_body
);
1536 if (SLP_TREE_TWO_OPERATORS (node
))
1538 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1539 stmt_info
, 0, vect_body
);
1540 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vec_perm
,
1541 stmt_info
, 0, vect_body
);
1545 /* Push SLP node def-type to stmts. */
1546 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1547 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
1548 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
1549 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = SLP_TREE_DEF_TYPE (child
);
1551 /* Scan operands and account for prologue cost of constants/externals.
1552 ??? This over-estimates cost for multiple uses and should be
1554 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1555 lhs
= gimple_get_lhs (stmt
);
1556 for (i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1558 tree op
= gimple_op (stmt
, i
);
1560 enum vect_def_type dt
;
1561 if (!op
|| op
== lhs
)
1563 if (vect_is_simple_use (op
, stmt_info
->vinfo
, &def_stmt
, &dt
))
1565 /* Without looking at the actual initializer a vector of
1566 constants can be implemented as load from the constant pool.
1567 ??? We need to pass down stmt_info for a vector type
1568 even if it points to the wrong stmt. */
1569 if (dt
== vect_constant_def
)
1570 record_stmt_cost (prologue_cost_vec
, 1, vector_load
,
1571 stmt_info
, 0, vect_prologue
);
1572 else if (dt
== vect_external_def
)
1573 record_stmt_cost (prologue_cost_vec
, 1, vec_construct
,
1574 stmt_info
, 0, vect_prologue
);
1578 /* Restore stmt def-types. */
1579 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1580 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
1581 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
1582 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_internal_def
;
1585 /* Compute the cost for the SLP instance INSTANCE. */
1588 vect_analyze_slp_cost (slp_instance instance
, void *data
)
1590 stmt_vector_for_cost body_cost_vec
, prologue_cost_vec
;
1591 unsigned ncopies_for_cost
;
1592 stmt_info_for_cost
*si
;
1595 if (dump_enabled_p ())
1596 dump_printf_loc (MSG_NOTE
, vect_location
,
1597 "=== vect_analyze_slp_cost ===\n");
1599 /* Calculate the number of vector stmts to create based on the unrolling
1600 factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
1601 GROUP_SIZE / NUNITS otherwise. */
1602 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1603 slp_tree node
= SLP_INSTANCE_TREE (instance
);
1604 stmt_vec_info stmt_info
= vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node
)[0]);
1605 /* Adjust the group_size by the vectorization factor which is always one
1606 for basic-block vectorization. */
1607 if (STMT_VINFO_LOOP_VINFO (stmt_info
))
1608 group_size
*= LOOP_VINFO_VECT_FACTOR (STMT_VINFO_LOOP_VINFO (stmt_info
));
1609 unsigned nunits
= TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
1610 /* For reductions look at a reduction operand in case the reduction
1611 operation is widening like DOT_PROD or SAD. */
1612 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1614 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1615 switch (gimple_assign_rhs_code (stmt
))
1619 nunits
= TYPE_VECTOR_SUBPARTS (get_vectype_for_scalar_type
1620 (TREE_TYPE (gimple_assign_rhs1 (stmt
))));
1625 ncopies_for_cost
= least_common_multiple (nunits
, group_size
) / nunits
;
1627 prologue_cost_vec
.create (10);
1628 body_cost_vec
.create (10);
1629 vect_analyze_slp_cost_1 (instance
, SLP_INSTANCE_TREE (instance
),
1630 &prologue_cost_vec
, &body_cost_vec
,
1633 /* Record the prologue costs, which were delayed until we were
1634 sure that SLP was successful. */
1635 FOR_EACH_VEC_ELT (prologue_cost_vec
, i
, si
)
1637 struct _stmt_vec_info
*stmt_info
1638 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1639 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1640 si
->misalign
, vect_prologue
);
1643 /* Record the instance's instructions in the target cost model. */
1644 FOR_EACH_VEC_ELT (body_cost_vec
, i
, si
)
1646 struct _stmt_vec_info
*stmt_info
1647 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1648 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1649 si
->misalign
, vect_body
);
1652 prologue_cost_vec
.release ();
1653 body_cost_vec
.release ();
1656 /* Splits a group of stores, currently beginning at FIRST_STMT, into two groups:
1657 one (still beginning at FIRST_STMT) of size GROUP1_SIZE (also containing
1658 the first GROUP1_SIZE stmts, since stores are consecutive), the second
1659 containing the remainder.
1660 Return the first stmt in the second group. */
1663 vect_split_slp_store_group (gimple
*first_stmt
, unsigned group1_size
)
1665 stmt_vec_info first_vinfo
= vinfo_for_stmt (first_stmt
);
1666 gcc_assert (GROUP_FIRST_ELEMENT (first_vinfo
) == first_stmt
);
1667 gcc_assert (group1_size
> 0);
1668 int group2_size
= GROUP_SIZE (first_vinfo
) - group1_size
;
1669 gcc_assert (group2_size
> 0);
1670 GROUP_SIZE (first_vinfo
) = group1_size
;
1672 gimple
*stmt
= first_stmt
;
1673 for (unsigned i
= group1_size
; i
> 1; i
--)
1675 stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
1676 gcc_assert (GROUP_GAP (vinfo_for_stmt (stmt
)) == 1);
1678 /* STMT is now the last element of the first group. */
1679 gimple
*group2
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
1680 GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
)) = 0;
1682 GROUP_SIZE (vinfo_for_stmt (group2
)) = group2_size
;
1683 for (stmt
= group2
; stmt
; stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
)))
1685 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = group2
;
1686 gcc_assert (GROUP_GAP (vinfo_for_stmt (stmt
)) == 1);
1689 /* For the second group, the GROUP_GAP is that before the original group,
1690 plus skipping over the first vector. */
1691 GROUP_GAP (vinfo_for_stmt (group2
)) =
1692 GROUP_GAP (first_vinfo
) + group1_size
;
1694 /* GROUP_GAP of the first group now has to skip over the second group too. */
1695 GROUP_GAP (first_vinfo
) += group2_size
;
1697 if (dump_enabled_p ())
1698 dump_printf_loc (MSG_NOTE
, vect_location
, "Split group into %d and %d\n",
1699 group1_size
, group2_size
);
1704 /* Analyze an SLP instance starting from a group of grouped stores. Call
1705 vect_build_slp_tree to build a tree of packed stmts if possible.
1706 Return FALSE if it's impossible to SLP any stmt in the loop. */
1709 vect_analyze_slp_instance (vec_info
*vinfo
,
1710 gimple
*stmt
, unsigned max_tree_size
)
1712 slp_instance new_instance
;
1714 unsigned int group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1715 unsigned int unrolling_factor
= 1, nunits
;
1716 tree vectype
, scalar_type
= NULL_TREE
;
1719 unsigned int max_nunits
= 0;
1720 vec
<slp_tree
> loads
;
1721 struct data_reference
*dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
));
1722 vec
<gimple
*> scalar_stmts
;
1724 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1728 scalar_type
= TREE_TYPE (DR_REF (dr
));
1729 vectype
= get_vectype_for_scalar_type (scalar_type
);
1733 gcc_assert (is_a
<loop_vec_info
> (vinfo
));
1734 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1737 group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1741 gcc_assert (is_a
<loop_vec_info
> (vinfo
));
1742 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1743 group_size
= as_a
<loop_vec_info
> (vinfo
)->reductions
.length ();
1748 if (dump_enabled_p ())
1750 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1751 "Build SLP failed: unsupported data-type ");
1752 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, scalar_type
);
1753 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1758 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
1760 /* Calculate the unrolling factor. */
1761 unrolling_factor
= least_common_multiple (nunits
, group_size
) / group_size
;
1762 if (unrolling_factor
!= 1 && is_a
<bb_vec_info
> (vinfo
))
1764 if (dump_enabled_p ())
1765 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1766 "Build SLP failed: unrolling required in basic"
1772 /* Create a node (a root of the SLP tree) for the packed grouped stores. */
1773 scalar_stmts
.create (group_size
);
1775 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1777 /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
1780 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next
))
1781 && STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)))
1782 scalar_stmts
.safe_push (
1783 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)));
1785 scalar_stmts
.safe_push (next
);
1786 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
1788 /* Mark the first element of the reduction chain as reduction to properly
1789 transform the node. In the reduction analysis phase only the last
1790 element of the chain is marked as reduction. */
1791 if (!STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
1792 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_reduction_def
;
1796 /* Collect reduction statements. */
1797 vec
<gimple
*> reductions
= as_a
<loop_vec_info
> (vinfo
)->reductions
;
1798 for (i
= 0; reductions
.iterate (i
, &next
); i
++)
1799 scalar_stmts
.safe_push (next
);
1802 loads
.create (group_size
);
1804 /* Build the tree for the SLP instance. */
1805 bool *matches
= XALLOCAVEC (bool, group_size
);
1806 unsigned npermutes
= 0;
1807 if ((node
= vect_build_slp_tree (vinfo
, scalar_stmts
, group_size
,
1808 &max_nunits
, &loads
, matches
, &npermutes
,
1809 NULL
, max_tree_size
)) != NULL
)
1811 /* Calculate the unrolling factor based on the smallest type. */
1812 if (max_nunits
> nunits
)
1813 unrolling_factor
= least_common_multiple (max_nunits
, group_size
)
1816 if (unrolling_factor
!= 1 && is_a
<bb_vec_info
> (vinfo
))
1818 if (dump_enabled_p ())
1819 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1820 "Build SLP failed: unrolling required in basic"
1822 vect_free_slp_tree (node
);
1827 /* Create a new SLP instance. */
1828 new_instance
= XNEW (struct _slp_instance
);
1829 SLP_INSTANCE_TREE (new_instance
) = node
;
1830 SLP_INSTANCE_GROUP_SIZE (new_instance
) = group_size
;
1831 SLP_INSTANCE_UNROLLING_FACTOR (new_instance
) = unrolling_factor
;
1832 SLP_INSTANCE_LOADS (new_instance
) = loads
;
1834 /* Compute the load permutation. */
1836 bool loads_permuted
= false;
1837 FOR_EACH_VEC_ELT (loads
, i
, load_node
)
1839 vec
<unsigned> load_permutation
;
1841 gimple
*load
, *first_stmt
;
1842 bool this_load_permuted
= false;
1843 load_permutation
.create (group_size
);
1844 first_stmt
= GROUP_FIRST_ELEMENT
1845 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node
)[0]));
1846 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node
), j
, load
)
1849 = vect_get_place_in_interleaving_chain (load
, first_stmt
);
1850 gcc_assert (load_place
!= -1);
1851 if (load_place
!= j
)
1852 this_load_permuted
= true;
1853 load_permutation
.safe_push (load_place
);
1855 if (!this_load_permuted
1856 /* The load requires permutation when unrolling exposes
1857 a gap either because the group is larger than the SLP
1858 group-size or because there is a gap between the groups. */
1859 && (unrolling_factor
== 1
1860 || (group_size
== GROUP_SIZE (vinfo_for_stmt (first_stmt
))
1861 && GROUP_GAP (vinfo_for_stmt (first_stmt
)) == 0)))
1863 load_permutation
.release ();
1866 SLP_TREE_LOAD_PERMUTATION (load_node
) = load_permutation
;
1867 loads_permuted
= true;
1872 if (!vect_supported_load_permutation_p (new_instance
))
1874 if (dump_enabled_p ())
1876 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1877 "Build SLP failed: unsupported load "
1879 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
1880 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1882 vect_free_slp_instance (new_instance
);
1887 /* If the loads and stores can be handled with load/store-lane
1888 instructions do not generate this SLP instance. */
1889 if (is_a
<loop_vec_info
> (vinfo
)
1891 && dr
&& vect_store_lanes_supported (vectype
, group_size
))
1894 FOR_EACH_VEC_ELT (loads
, i
, load_node
)
1896 gimple
*first_stmt
= GROUP_FIRST_ELEMENT
1897 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node
)[0]));
1898 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (first_stmt
);
1899 /* Use SLP for strided accesses (or if we can't load-lanes). */
1900 if (STMT_VINFO_STRIDED_P (stmt_vinfo
)
1901 || ! vect_load_lanes_supported
1902 (STMT_VINFO_VECTYPE (stmt_vinfo
),
1903 GROUP_SIZE (stmt_vinfo
)))
1906 if (i
== loads
.length ())
1908 if (dump_enabled_p ())
1909 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1910 "Built SLP cancelled: can use "
1911 "load/store-lanes\n");
1912 vect_free_slp_instance (new_instance
);
1917 vinfo
->slp_instances
.safe_push (new_instance
);
1919 if (dump_enabled_p ())
1921 dump_printf_loc (MSG_NOTE
, vect_location
,
1922 "Final SLP tree for instance:\n");
1923 vect_print_slp_tree (MSG_NOTE
, vect_location
, node
);
1929 /* Failed to SLP. */
1930 /* Free the allocated memory. */
1931 scalar_stmts
.release ();
1934 /* For basic block SLP, try to break the group up into multiples of the
1936 if (is_a
<bb_vec_info
> (vinfo
)
1937 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
1938 && STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
1940 /* We consider breaking the group only on VF boundaries from the existing
1942 for (i
= 0; i
< group_size
; i
++)
1943 if (!matches
[i
]) break;
1945 if (i
>= nunits
&& i
< group_size
)
1947 /* Split into two groups at the first vector boundary before i. */
1948 gcc_assert ((nunits
& (nunits
- 1)) == 0);
1949 unsigned group1_size
= i
& ~(nunits
- 1);
1951 gimple
*rest
= vect_split_slp_store_group (stmt
, group1_size
);
1952 bool res
= vect_analyze_slp_instance (vinfo
, stmt
, max_tree_size
);
1953 /* If the first non-match was in the middle of a vector,
1954 skip the rest of that vector. */
1955 if (group1_size
< i
)
1957 i
= group1_size
+ nunits
;
1959 rest
= vect_split_slp_store_group (rest
, nunits
);
1962 res
|= vect_analyze_slp_instance (vinfo
, rest
, max_tree_size
);
1965 /* Even though the first vector did not all match, we might be able to SLP
1966 (some) of the remainder. FORNOW ignore this possibility. */
1973 /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
1974 trees of packed scalar stmts if SLP is possible. */
1977 vect_analyze_slp (vec_info
*vinfo
, unsigned max_tree_size
)
1980 gimple
*first_element
;
1983 if (dump_enabled_p ())
1984 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_analyze_slp ===\n");
1986 /* Find SLP sequences starting from groups of grouped stores. */
1987 FOR_EACH_VEC_ELT (vinfo
->grouped_stores
, i
, first_element
)
1988 if (vect_analyze_slp_instance (vinfo
, first_element
, max_tree_size
))
1991 if (loop_vec_info loop_vinfo
= dyn_cast
<loop_vec_info
> (vinfo
))
1993 if (loop_vinfo
->reduction_chains
.length () > 0)
1995 /* Find SLP sequences starting from reduction chains. */
1996 FOR_EACH_VEC_ELT (loop_vinfo
->reduction_chains
, i
, first_element
)
1997 if (vect_analyze_slp_instance (vinfo
, first_element
,
2003 /* Don't try to vectorize SLP reductions if reduction chain was
2008 /* Find SLP sequences starting from groups of reductions. */
2009 if (loop_vinfo
->reductions
.length () > 1
2010 && vect_analyze_slp_instance (vinfo
, loop_vinfo
->reductions
[0],
2019 /* For each possible SLP instance decide whether to SLP it and calculate overall
2020 unrolling factor needed to SLP the loop. Return TRUE if decided to SLP at
2021 least one instance. */
2024 vect_make_slp_decision (loop_vec_info loop_vinfo
)
2026 unsigned int i
, unrolling_factor
= 1;
2027 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2028 slp_instance instance
;
2029 int decided_to_slp
= 0;
2031 if (dump_enabled_p ())
2032 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_make_slp_decision ==="
2035 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2037 /* FORNOW: SLP if you can. */
2038 if (unrolling_factor
< SLP_INSTANCE_UNROLLING_FACTOR (instance
))
2039 unrolling_factor
= SLP_INSTANCE_UNROLLING_FACTOR (instance
);
2041 /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
2042 call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
2043 loop-based vectorization. Such stmts will be marked as HYBRID. */
2044 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2048 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
) = unrolling_factor
;
2050 if (decided_to_slp
&& dump_enabled_p ())
2051 dump_printf_loc (MSG_NOTE
, vect_location
,
2052 "Decided to SLP %d instances. Unrolling factor %d\n",
2053 decided_to_slp
, unrolling_factor
);
2055 return (decided_to_slp
> 0);
2059 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
2060 can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
2063 vect_detect_hybrid_slp_stmts (slp_tree node
, unsigned i
, slp_vect_type stype
)
2065 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[i
];
2066 imm_use_iterator imm_iter
;
2068 stmt_vec_info use_vinfo
, stmt_vinfo
= vinfo_for_stmt (stmt
);
2070 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
2071 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2074 /* Propagate hybrid down the SLP tree. */
2075 if (stype
== hybrid
)
2077 else if (HYBRID_SLP_STMT (stmt_vinfo
))
2081 /* Check if a pure SLP stmt has uses in non-SLP stmts. */
2082 gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo
));
2083 /* If we get a pattern stmt here we have to use the LHS of the
2084 original stmt for immediate uses. */
2085 if (! STMT_VINFO_IN_PATTERN_P (stmt_vinfo
)
2086 && STMT_VINFO_RELATED_STMT (stmt_vinfo
))
2087 stmt
= STMT_VINFO_RELATED_STMT (stmt_vinfo
);
2088 if (TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2089 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, gimple_op (stmt
, 0))
2091 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2093 use_vinfo
= vinfo_for_stmt (use_stmt
);
2094 if (STMT_VINFO_IN_PATTERN_P (use_vinfo
)
2095 && STMT_VINFO_RELATED_STMT (use_vinfo
))
2096 use_vinfo
= vinfo_for_stmt (STMT_VINFO_RELATED_STMT (use_vinfo
));
2097 if (!STMT_SLP_TYPE (use_vinfo
)
2098 && (STMT_VINFO_RELEVANT (use_vinfo
)
2099 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo
)))
2100 && !(gimple_code (use_stmt
) == GIMPLE_PHI
2101 && STMT_VINFO_DEF_TYPE (use_vinfo
) == vect_reduction_def
))
2103 if (dump_enabled_p ())
2105 dump_printf_loc (MSG_NOTE
, vect_location
, "use of SLP "
2106 "def in non-SLP stmt: ");
2107 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, use_stmt
, 0);
2115 && !HYBRID_SLP_STMT (stmt_vinfo
))
2117 if (dump_enabled_p ())
2119 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2120 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
2122 STMT_SLP_TYPE (stmt_vinfo
) = hybrid
;
2125 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2126 if (SLP_TREE_DEF_TYPE (child
) != vect_external_def
)
2127 vect_detect_hybrid_slp_stmts (child
, i
, stype
);
2130 /* Helpers for vect_detect_hybrid_slp walking pattern stmt uses. */
2133 vect_detect_hybrid_slp_1 (tree
*tp
, int *, void *data
)
2135 walk_stmt_info
*wi
= (walk_stmt_info
*)data
;
2136 struct loop
*loopp
= (struct loop
*)wi
->info
;
2141 if (TREE_CODE (*tp
) == SSA_NAME
2142 && !SSA_NAME_IS_DEFAULT_DEF (*tp
))
2144 gimple
*def_stmt
= SSA_NAME_DEF_STMT (*tp
);
2145 if (flow_bb_inside_loop_p (loopp
, gimple_bb (def_stmt
))
2146 && PURE_SLP_STMT (vinfo_for_stmt (def_stmt
)))
2148 if (dump_enabled_p ())
2150 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2151 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2153 STMT_SLP_TYPE (vinfo_for_stmt (def_stmt
)) = hybrid
;
2161 vect_detect_hybrid_slp_2 (gimple_stmt_iterator
*gsi
, bool *handled
,
2164 /* If the stmt is in a SLP instance then this isn't a reason
2165 to mark use definitions in other SLP instances as hybrid. */
2166 if (STMT_SLP_TYPE (vinfo_for_stmt (gsi_stmt (*gsi
))) != loop_vect
)
2171 /* Find stmts that must be both vectorized and SLPed. */
2174 vect_detect_hybrid_slp (loop_vec_info loop_vinfo
)
2177 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2178 slp_instance instance
;
2180 if (dump_enabled_p ())
2181 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_detect_hybrid_slp ==="
2184 /* First walk all pattern stmt in the loop and mark defs of uses as
2185 hybrid because immediate uses in them are not recorded. */
2186 for (i
= 0; i
< LOOP_VINFO_LOOP (loop_vinfo
)->num_nodes
; ++i
)
2188 basic_block bb
= LOOP_VINFO_BBS (loop_vinfo
)[i
];
2189 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2192 gimple
*stmt
= gsi_stmt (gsi
);
2193 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2194 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
2197 memset (&wi
, 0, sizeof (wi
));
2198 wi
.info
= LOOP_VINFO_LOOP (loop_vinfo
);
2199 gimple_stmt_iterator gsi2
2200 = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info
));
2201 walk_gimple_stmt (&gsi2
, vect_detect_hybrid_slp_2
,
2202 vect_detect_hybrid_slp_1
, &wi
);
2203 walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
),
2204 vect_detect_hybrid_slp_2
,
2205 vect_detect_hybrid_slp_1
, &wi
);
2210 /* Then walk the SLP instance trees marking stmts with uses in
2211 non-SLP stmts as hybrid, also propagating hybrid down the
2212 SLP tree, collecting the above info on-the-fly. */
2213 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2215 for (unsigned i
= 0; i
< SLP_INSTANCE_GROUP_SIZE (instance
); ++i
)
2216 vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance
),
2222 /* Create and initialize a new bb_vec_info struct for BB, as well as
2223 stmt_vec_info structs for all the stmts in it. */
2226 new_bb_vec_info (gimple_stmt_iterator region_begin
,
2227 gimple_stmt_iterator region_end
)
2229 basic_block bb
= gsi_bb (region_begin
);
2230 bb_vec_info res
= NULL
;
2231 gimple_stmt_iterator gsi
;
2233 res
= (bb_vec_info
) xcalloc (1, sizeof (struct _bb_vec_info
));
2234 res
->kind
= vec_info::bb
;
2235 BB_VINFO_BB (res
) = bb
;
2236 res
->region_begin
= region_begin
;
2237 res
->region_end
= region_end
;
2239 for (gsi
= region_begin
; gsi_stmt (gsi
) != gsi_stmt (region_end
);
2242 gimple
*stmt
= gsi_stmt (gsi
);
2243 gimple_set_uid (stmt
, 0);
2244 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
));
2247 BB_VINFO_GROUPED_STORES (res
).create (10);
2248 BB_VINFO_SLP_INSTANCES (res
).create (2);
2249 BB_VINFO_TARGET_COST_DATA (res
) = init_cost (NULL
);
2256 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
2257 stmts in the basic block. */
2260 destroy_bb_vec_info (bb_vec_info bb_vinfo
)
2262 slp_instance instance
;
2268 vect_destroy_datarefs (bb_vinfo
);
2269 free_dependence_relations (BB_VINFO_DDRS (bb_vinfo
));
2270 BB_VINFO_GROUPED_STORES (bb_vinfo
).release ();
2271 FOR_EACH_VEC_ELT (BB_VINFO_SLP_INSTANCES (bb_vinfo
), i
, instance
)
2272 vect_free_slp_instance (instance
);
2273 BB_VINFO_SLP_INSTANCES (bb_vinfo
).release ();
2274 destroy_cost_data (BB_VINFO_TARGET_COST_DATA (bb_vinfo
));
2276 for (gimple_stmt_iterator si
= bb_vinfo
->region_begin
;
2277 gsi_stmt (si
) != gsi_stmt (bb_vinfo
->region_end
); gsi_next (&si
))
2279 gimple
*stmt
= gsi_stmt (si
);
2280 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2283 /* Free stmt_vec_info. */
2284 free_stmt_vec_info (stmt
);
2286 /* Reset region marker. */
2287 gimple_set_uid (stmt
, -1);
2290 BB_VINFO_BB (bb_vinfo
)->aux
= NULL
;
2295 /* Analyze statements contained in SLP tree node after recursively analyzing
2296 the subtree. Return TRUE if the operations are supported. */
2299 vect_slp_analyze_node_operations (slp_tree node
)
2306 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
2309 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2310 if (!vect_slp_analyze_node_operations (child
))
2314 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2316 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2317 gcc_assert (stmt_info
);
2318 gcc_assert (STMT_SLP_TYPE (stmt_info
) != loop_vect
);
2320 /* Push SLP node def-type to stmt operands. */
2321 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2322 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
2323 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child
)[i
]))
2324 = SLP_TREE_DEF_TYPE (child
);
2325 res
= vect_analyze_stmt (stmt
, &dummy
, node
);
2326 /* Restore def-types. */
2327 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2328 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
2329 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child
)[i
]))
2330 = vect_internal_def
;
2339 /* Analyze statements in SLP instances of the basic block. Return TRUE if the
2340 operations are supported. */
2343 vect_slp_analyze_operations (vec
<slp_instance
> slp_instances
, void *data
)
2345 slp_instance instance
;
2348 if (dump_enabled_p ())
2349 dump_printf_loc (MSG_NOTE
, vect_location
,
2350 "=== vect_slp_analyze_operations ===\n");
2352 for (i
= 0; slp_instances
.iterate (i
, &instance
); )
2354 if (!vect_slp_analyze_node_operations (SLP_INSTANCE_TREE (instance
)))
2356 dump_printf_loc (MSG_NOTE
, vect_location
,
2357 "removing SLP instance operations starting from: ");
2358 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
2359 SLP_TREE_SCALAR_STMTS
2360 (SLP_INSTANCE_TREE (instance
))[0], 0);
2361 vect_free_slp_instance (instance
);
2362 slp_instances
.ordered_remove (i
);
2366 /* Compute the costs of the SLP instance. */
2367 vect_analyze_slp_cost (instance
, data
);
2372 if (!slp_instances
.length ())
2379 /* Compute the scalar cost of the SLP node NODE and its children
2380 and return it. Do not account defs that are marked in LIFE and
2381 update LIFE according to uses of NODE. */
2384 vect_bb_slp_scalar_cost (basic_block bb
,
2385 slp_tree node
, vec
<bool, va_heap
> *life
)
2387 unsigned scalar_cost
= 0;
2392 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2395 ssa_op_iter op_iter
;
2396 def_operand_p def_p
;
2397 stmt_vec_info stmt_info
;
2402 /* If there is a non-vectorized use of the defs then the scalar
2403 stmt is kept live in which case we do not account it or any
2404 required defs in the SLP children in the scalar cost. This
2405 way we make the vectorization more costly when compared to
2407 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
2409 imm_use_iterator use_iter
;
2411 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, DEF_FROM_PTR (def_p
))
2412 if (!is_gimple_debug (use_stmt
)
2413 && (! vect_stmt_in_region_p (vinfo_for_stmt (stmt
)->vinfo
,
2415 || ! PURE_SLP_STMT (vinfo_for_stmt (use_stmt
))))
2418 BREAK_FROM_IMM_USE_STMT (use_iter
);
2424 /* Count scalar stmts only once. */
2425 if (gimple_visited_p (stmt
))
2427 gimple_set_visited (stmt
, true);
2429 stmt_info
= vinfo_for_stmt (stmt
);
2430 if (STMT_VINFO_DATA_REF (stmt_info
))
2432 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)))
2433 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2435 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2438 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2440 scalar_cost
+= stmt_cost
;
2443 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2444 if (SLP_TREE_DEF_TYPE (child
) == vect_internal_def
)
2445 scalar_cost
+= vect_bb_slp_scalar_cost (bb
, child
, life
);
2450 /* Check if vectorization of the basic block is profitable. */
2453 vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo
)
2455 vec
<slp_instance
> slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2456 slp_instance instance
;
2458 unsigned int vec_inside_cost
= 0, vec_outside_cost
= 0, scalar_cost
= 0;
2459 unsigned int vec_prologue_cost
= 0, vec_epilogue_cost
= 0;
2461 /* Calculate scalar cost. */
2462 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2464 auto_vec
<bool, 20> life
;
2465 life
.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance
));
2466 scalar_cost
+= vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo
),
2467 SLP_INSTANCE_TREE (instance
),
2471 /* Unset visited flag. */
2472 for (gimple_stmt_iterator gsi
= bb_vinfo
->region_begin
;
2473 gsi_stmt (gsi
) != gsi_stmt (bb_vinfo
->region_end
); gsi_next (&gsi
))
2474 gimple_set_visited (gsi_stmt (gsi
), false);
2476 /* Complete the target-specific cost calculation. */
2477 finish_cost (BB_VINFO_TARGET_COST_DATA (bb_vinfo
), &vec_prologue_cost
,
2478 &vec_inside_cost
, &vec_epilogue_cost
);
2480 vec_outside_cost
= vec_prologue_cost
+ vec_epilogue_cost
;
2482 if (dump_enabled_p ())
2484 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2485 dump_printf (MSG_NOTE
, " Vector inside of basic block cost: %d\n",
2487 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n", vec_prologue_cost
);
2488 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n", vec_epilogue_cost
);
2489 dump_printf (MSG_NOTE
, " Scalar cost of basic block: %d\n", scalar_cost
);
2492 /* Vectorization is profitable if its cost is more than the cost of scalar
2493 version. Note that we err on the vector side for equal cost because
2494 the cost estimate is otherwise quite pessimistic (constant uses are
2495 free on the scalar side but cost a load on the vector side for
2497 if (vec_outside_cost
+ vec_inside_cost
> scalar_cost
)
2503 /* Check if the basic block can be vectorized. Returns a bb_vec_info
2504 if so and sets fatal to true if failure is independent of
2505 current_vector_size. */
2508 vect_slp_analyze_bb_1 (gimple_stmt_iterator region_begin
,
2509 gimple_stmt_iterator region_end
,
2510 vec
<data_reference_p
> datarefs
, int n_stmts
,
2513 bb_vec_info bb_vinfo
;
2514 slp_instance instance
;
2518 /* The first group of checks is independent of the vector size. */
2521 if (n_stmts
> PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB
))
2523 if (dump_enabled_p ())
2524 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2525 "not vectorized: too many instructions in "
2527 free_data_refs (datarefs
);
2531 bb_vinfo
= new_bb_vec_info (region_begin
, region_end
);
2535 BB_VINFO_DATAREFS (bb_vinfo
) = datarefs
;
2537 /* Analyze the data references. */
2539 if (!vect_analyze_data_refs (bb_vinfo
, &min_vf
))
2541 if (dump_enabled_p ())
2542 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2543 "not vectorized: unhandled data-ref in basic "
2546 destroy_bb_vec_info (bb_vinfo
);
2550 if (BB_VINFO_DATAREFS (bb_vinfo
).length () < 2)
2552 if (dump_enabled_p ())
2553 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2554 "not vectorized: not enough data-refs in "
2557 destroy_bb_vec_info (bb_vinfo
);
2561 if (!vect_analyze_data_ref_accesses (bb_vinfo
))
2563 if (dump_enabled_p ())
2564 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2565 "not vectorized: unhandled data access in "
2568 destroy_bb_vec_info (bb_vinfo
);
2572 /* If there are no grouped stores in the region there is no need
2573 to continue with pattern recog as vect_analyze_slp will fail
2575 if (bb_vinfo
->grouped_stores
.is_empty ())
2577 if (dump_enabled_p ())
2578 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2579 "not vectorized: no grouped stores in "
2582 destroy_bb_vec_info (bb_vinfo
);
2586 /* While the rest of the analysis below depends on it in some way. */
2589 vect_pattern_recog (bb_vinfo
);
2591 /* Check the SLP opportunities in the basic block, analyze and build SLP
2593 if (!vect_analyze_slp (bb_vinfo
, n_stmts
))
2595 if (dump_enabled_p ())
2597 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2598 "Failed to SLP the basic block.\n");
2599 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2600 "not vectorized: failed to find SLP opportunities "
2601 "in basic block.\n");
2604 destroy_bb_vec_info (bb_vinfo
);
2608 /* Analyze and verify the alignment of data references and the
2609 dependence in the SLP instances. */
2610 for (i
= 0; BB_VINFO_SLP_INSTANCES (bb_vinfo
).iterate (i
, &instance
); )
2612 if (! vect_slp_analyze_and_verify_instance_alignment (instance
)
2613 || ! vect_slp_analyze_instance_dependence (instance
))
2615 dump_printf_loc (MSG_NOTE
, vect_location
,
2616 "removing SLP instance operations starting from: ");
2617 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
2618 SLP_TREE_SCALAR_STMTS
2619 (SLP_INSTANCE_TREE (instance
))[0], 0);
2620 vect_free_slp_instance (instance
);
2621 BB_VINFO_SLP_INSTANCES (bb_vinfo
).ordered_remove (i
);
2625 /* Mark all the statements that we want to vectorize as pure SLP and
2627 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2628 vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance
));
2632 if (! BB_VINFO_SLP_INSTANCES (bb_vinfo
).length ())
2634 destroy_bb_vec_info (bb_vinfo
);
2638 if (!vect_slp_analyze_operations (BB_VINFO_SLP_INSTANCES (bb_vinfo
),
2639 BB_VINFO_TARGET_COST_DATA (bb_vinfo
)))
2641 if (dump_enabled_p ())
2642 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2643 "not vectorized: bad operation in basic block.\n");
2645 destroy_bb_vec_info (bb_vinfo
);
2649 /* Cost model: check if the vectorization is worthwhile. */
2650 if (!unlimited_cost_model (NULL
)
2651 && !vect_bb_vectorization_profitable_p (bb_vinfo
))
2653 if (dump_enabled_p ())
2654 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2655 "not vectorized: vectorization is not "
2658 destroy_bb_vec_info (bb_vinfo
);
2662 if (dump_enabled_p ())
2663 dump_printf_loc (MSG_NOTE
, vect_location
,
2664 "Basic block will be vectorized using SLP\n");
2670 /* Main entry for the BB vectorizer. Analyze and transform BB, returns
2671 true if anything in the basic-block was vectorized. */
2674 vect_slp_bb (basic_block bb
)
2676 bb_vec_info bb_vinfo
;
2677 gimple_stmt_iterator gsi
;
2678 unsigned int vector_sizes
;
2679 bool any_vectorized
= false;
2681 if (dump_enabled_p ())
2682 dump_printf_loc (MSG_NOTE
, vect_location
, "===vect_slp_analyze_bb===\n");
2684 /* Autodetect first vector size we try. */
2685 current_vector_size
= 0;
2686 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2688 gsi
= gsi_start_bb (bb
);
2692 if (gsi_end_p (gsi
))
2695 gimple_stmt_iterator region_begin
= gsi
;
2696 vec
<data_reference_p
> datarefs
= vNULL
;
2699 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
2701 gimple
*stmt
= gsi_stmt (gsi
);
2702 if (is_gimple_debug (stmt
))
2706 if (gimple_location (stmt
) != UNKNOWN_LOCATION
)
2707 vect_location
= gimple_location (stmt
);
2709 if (!find_data_references_in_stmt (NULL
, stmt
, &datarefs
))
2713 /* Skip leading unhandled stmts. */
2714 if (gsi_stmt (region_begin
) == gsi_stmt (gsi
))
2720 gimple_stmt_iterator region_end
= gsi
;
2722 bool vectorized
= false;
2724 bb_vinfo
= vect_slp_analyze_bb_1 (region_begin
, region_end
,
2725 datarefs
, insns
, fatal
);
2727 && dbg_cnt (vect_slp
))
2729 if (dump_enabled_p ())
2730 dump_printf_loc (MSG_NOTE
, vect_location
, "SLPing BB part\n");
2732 vect_schedule_slp (bb_vinfo
);
2734 if (dump_enabled_p ())
2735 dump_printf_loc (MSG_NOTE
, vect_location
,
2736 "basic block part vectorized\n");
2738 destroy_bb_vec_info (bb_vinfo
);
2743 destroy_bb_vec_info (bb_vinfo
);
2745 any_vectorized
|= vectorized
;
2747 vector_sizes
&= ~current_vector_size
;
2749 || vector_sizes
== 0
2750 || current_vector_size
== 0
2751 /* If vect_slp_analyze_bb_1 signaled that analysis for all
2752 vector sizes will fail do not bother iterating. */
2755 if (gsi_end_p (region_end
))
2758 /* Skip the unhandled stmt. */
2761 /* And reset vector sizes. */
2762 current_vector_size
= 0;
2763 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2767 /* Try the next biggest vector size. */
2768 current_vector_size
= 1 << floor_log2 (vector_sizes
);
2769 if (dump_enabled_p ())
2770 dump_printf_loc (MSG_NOTE
, vect_location
,
2771 "***** Re-trying analysis with "
2772 "vector size %d\n", current_vector_size
);
2779 return any_vectorized
;
2783 /* Return 1 if vector type of boolean constant which is OPNUM
2784 operand in statement STMT is a boolean vector. */
2787 vect_mask_constant_operand_p (gimple
*stmt
, int opnum
)
2789 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2790 enum tree_code code
= gimple_expr_code (stmt
);
2793 enum vect_def_type dt
;
2795 /* For comparison and COND_EXPR type is chosen depending
2796 on the other comparison operand. */
2797 if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2800 op
= gimple_assign_rhs1 (stmt
);
2802 op
= gimple_assign_rhs2 (stmt
);
2804 if (!vect_is_simple_use (op
, stmt_vinfo
->vinfo
, &def_stmt
,
2808 return !vectype
|| VECTOR_BOOLEAN_TYPE_P (vectype
);
2811 if (code
== COND_EXPR
)
2813 tree cond
= gimple_assign_rhs1 (stmt
);
2815 if (TREE_CODE (cond
) == SSA_NAME
)
2819 op
= TREE_OPERAND (cond
, 1);
2821 op
= TREE_OPERAND (cond
, 0);
2823 if (!vect_is_simple_use (op
, stmt_vinfo
->vinfo
, &def_stmt
,
2827 return !vectype
|| VECTOR_BOOLEAN_TYPE_P (vectype
);
2830 return VECTOR_BOOLEAN_TYPE_P (STMT_VINFO_VECTYPE (stmt_vinfo
));
2834 /* For constant and loop invariant defs of SLP_NODE this function returns
2835 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
2836 OP_NUM determines if we gather defs for operand 0 or operand 1 of the RHS of
2837 scalar stmts. NUMBER_OF_VECTORS is the number of vector defs to create.
2838 REDUC_INDEX is the index of the reduction operand in the statements, unless
2842 vect_get_constant_vectors (tree op
, slp_tree slp_node
,
2843 vec
<tree
> *vec_oprnds
,
2844 unsigned int op_num
, unsigned int number_of_vectors
,
2847 vec
<gimple
*> stmts
= SLP_TREE_SCALAR_STMTS (slp_node
);
2848 gimple
*stmt
= stmts
[0];
2849 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2853 unsigned j
, number_of_places_left_in_vector
;
2856 int group_size
= stmts
.length ();
2857 unsigned int vec_num
, i
;
2858 unsigned number_of_copies
= 1;
2860 voprnds
.create (number_of_vectors
);
2861 bool constant_p
, is_store
;
2862 tree neutral_op
= NULL
;
2863 enum tree_code code
= gimple_expr_code (stmt
);
2866 gimple_seq ctor_seq
= NULL
;
2868 /* Check if vector type is a boolean vector. */
2869 if (TREE_CODE (TREE_TYPE (op
)) == BOOLEAN_TYPE
2870 && vect_mask_constant_operand_p (stmt
, op_num
))
2872 = build_same_sized_truth_vector_type (STMT_VINFO_VECTYPE (stmt_vinfo
));
2874 vector_type
= get_vectype_for_scalar_type (TREE_TYPE (op
));
2875 nunits
= TYPE_VECTOR_SUBPARTS (vector_type
);
2877 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_reduction_def
2878 && reduc_index
!= -1)
2880 op_num
= reduc_index
;
2881 op
= gimple_op (stmt
, op_num
+ 1);
2882 /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
2883 we need either neutral operands or the original operands. See
2884 get_initial_def_for_reduction() for details. */
2887 case WIDEN_SUM_EXPR
:
2894 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2895 neutral_op
= build_real (TREE_TYPE (op
), dconst0
);
2897 neutral_op
= build_int_cst (TREE_TYPE (op
), 0);
2902 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2903 neutral_op
= build_real (TREE_TYPE (op
), dconst1
);
2905 neutral_op
= build_int_cst (TREE_TYPE (op
), 1);
2910 neutral_op
= build_int_cst (TREE_TYPE (op
), -1);
2913 /* For MIN/MAX we don't have an easy neutral operand but
2914 the initial values can be used fine here. Only for
2915 a reduction chain we have to force a neutral element. */
2918 if (!GROUP_FIRST_ELEMENT (stmt_vinfo
))
2922 def_stmt
= SSA_NAME_DEF_STMT (op
);
2923 loop
= (gimple_bb (stmt
))->loop_father
;
2924 neutral_op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2925 loop_preheader_edge (loop
));
2930 gcc_assert (!GROUP_FIRST_ELEMENT (stmt_vinfo
));
2935 if (STMT_VINFO_DATA_REF (stmt_vinfo
))
2938 op
= gimple_assign_rhs1 (stmt
);
2945 if (CONSTANT_CLASS_P (op
))
2950 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
2951 created vectors. It is greater than 1 if unrolling is performed.
2953 For example, we have two scalar operands, s1 and s2 (e.g., group of
2954 strided accesses of size two), while NUNITS is four (i.e., four scalars
2955 of this type can be packed in a vector). The output vector will contain
2956 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
2959 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
2960 containing the operands.
2962 For example, NUNITS is four as before, and the group size is 8
2963 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
2964 {s5, s6, s7, s8}. */
2966 number_of_copies
= nunits
* number_of_vectors
/ group_size
;
2968 number_of_places_left_in_vector
= nunits
;
2969 elts
= XALLOCAVEC (tree
, nunits
);
2970 bool place_after_defs
= false;
2971 for (j
= 0; j
< number_of_copies
; j
++)
2973 for (i
= group_size
- 1; stmts
.iterate (i
, &stmt
); i
--)
2976 op
= gimple_assign_rhs1 (stmt
);
2983 tree cond
= gimple_assign_rhs1 (stmt
);
2984 if (TREE_CODE (cond
) == SSA_NAME
)
2985 op
= gimple_op (stmt
, op_num
+ 1);
2986 else if (op_num
== 0 || op_num
== 1)
2987 op
= TREE_OPERAND (cond
, op_num
);
2991 op
= gimple_assign_rhs2 (stmt
);
2993 op
= gimple_assign_rhs3 (stmt
);
2999 op
= gimple_call_arg (stmt
, op_num
);
3006 op
= gimple_op (stmt
, op_num
+ 1);
3007 /* Unlike the other binary operators, shifts/rotates have
3008 the shift count being int, instead of the same type as
3009 the lhs, so make sure the scalar is the right type if
3010 we are dealing with vectors of
3011 long long/long/short/char. */
3012 if (op_num
== 1 && TREE_CODE (op
) == INTEGER_CST
)
3013 op
= fold_convert (TREE_TYPE (vector_type
), op
);
3017 op
= gimple_op (stmt
, op_num
+ 1);
3022 if (reduc_index
!= -1)
3024 loop
= (gimple_bb (stmt
))->loop_father
;
3025 def_stmt
= SSA_NAME_DEF_STMT (op
);
3029 /* Get the def before the loop. In reduction chain we have only
3030 one initial value. */
3031 if ((j
!= (number_of_copies
- 1)
3032 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
3037 op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
3038 loop_preheader_edge (loop
));
3041 /* Create 'vect_ = {op0,op1,...,opn}'. */
3042 number_of_places_left_in_vector
--;
3044 if (!types_compatible_p (TREE_TYPE (vector_type
), TREE_TYPE (op
)))
3046 if (CONSTANT_CLASS_P (op
))
3048 if (VECTOR_BOOLEAN_TYPE_P (vector_type
))
3050 /* Can't use VIEW_CONVERT_EXPR for booleans because
3051 of possibly different sizes of scalar value and
3053 if (integer_zerop (op
))
3054 op
= build_int_cst (TREE_TYPE (vector_type
), 0);
3055 else if (integer_onep (op
))
3056 op
= build_int_cst (TREE_TYPE (vector_type
), 1);
3061 op
= fold_unary (VIEW_CONVERT_EXPR
,
3062 TREE_TYPE (vector_type
), op
);
3063 gcc_assert (op
&& CONSTANT_CLASS_P (op
));
3067 tree new_temp
= make_ssa_name (TREE_TYPE (vector_type
));
3069 if (VECTOR_BOOLEAN_TYPE_P (vector_type
))
3071 gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (op
)));
3072 init_stmt
= gimple_build_assign (new_temp
, NOP_EXPR
, op
);
3076 op
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (vector_type
),
3079 = gimple_build_assign (new_temp
, VIEW_CONVERT_EXPR
,
3082 gimple_seq_add_stmt (&ctor_seq
, init_stmt
);
3086 elts
[number_of_places_left_in_vector
] = op
;
3087 if (!CONSTANT_CLASS_P (op
))
3089 if (TREE_CODE (orig_op
) == SSA_NAME
3090 && !SSA_NAME_IS_DEFAULT_DEF (orig_op
)
3091 && STMT_VINFO_BB_VINFO (stmt_vinfo
)
3092 && (STMT_VINFO_BB_VINFO (stmt_vinfo
)->bb
3093 == gimple_bb (SSA_NAME_DEF_STMT (orig_op
))))
3094 place_after_defs
= true;
3096 if (number_of_places_left_in_vector
== 0)
3098 number_of_places_left_in_vector
= nunits
;
3101 vec_cst
= build_vector (vector_type
, elts
);
3104 vec
<constructor_elt
, va_gc
> *v
;
3106 vec_alloc (v
, nunits
);
3107 for (k
= 0; k
< nunits
; ++k
)
3108 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[k
]);
3109 vec_cst
= build_constructor (vector_type
, v
);
3112 gimple_stmt_iterator gsi
;
3113 if (place_after_defs
)
3116 (vect_find_last_scalar_stmt_in_slp (slp_node
));
3117 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, &gsi
);
3120 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, NULL
);
3121 if (ctor_seq
!= NULL
)
3123 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (init
));
3124 gsi_insert_seq_before_without_update (&gsi
, ctor_seq
,
3128 voprnds
.quick_push (init
);
3129 place_after_defs
= false;
3134 /* Since the vectors are created in the reverse order, we should invert
3136 vec_num
= voprnds
.length ();
3137 for (j
= vec_num
; j
!= 0; j
--)
3139 vop
= voprnds
[j
- 1];
3140 vec_oprnds
->quick_push (vop
);
3145 /* In case that VF is greater than the unrolling factor needed for the SLP
3146 group of stmts, NUMBER_OF_VECTORS to be created is greater than
3147 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
3148 to replicate the vectors. */
3149 while (number_of_vectors
> vec_oprnds
->length ())
3151 tree neutral_vec
= NULL
;
3156 neutral_vec
= build_vector_from_val (vector_type
, neutral_op
);
3158 vec_oprnds
->quick_push (neutral_vec
);
3162 for (i
= 0; vec_oprnds
->iterate (i
, &vop
) && i
< vec_num
; i
++)
3163 vec_oprnds
->quick_push (vop
);
3169 /* Get vectorized definitions from SLP_NODE that contains corresponding
3170 vectorized def-stmts. */
3173 vect_get_slp_vect_defs (slp_tree slp_node
, vec
<tree
> *vec_oprnds
)
3176 gimple
*vec_def_stmt
;
3179 gcc_assert (SLP_TREE_VEC_STMTS (slp_node
).exists ());
3181 FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (slp_node
), i
, vec_def_stmt
)
3183 gcc_assert (vec_def_stmt
);
3184 vec_oprnd
= gimple_get_lhs (vec_def_stmt
);
3185 vec_oprnds
->quick_push (vec_oprnd
);
3190 /* Get vectorized definitions for SLP_NODE.
3191 If the scalar definitions are loop invariants or constants, collect them and
3192 call vect_get_constant_vectors() to create vector stmts.
3193 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
3194 must be stored in the corresponding child of SLP_NODE, and we call
3195 vect_get_slp_vect_defs () to retrieve them. */
3198 vect_get_slp_defs (vec
<tree
> ops
, slp_tree slp_node
,
3199 vec
<vec
<tree
> > *vec_oprnds
, int reduc_index
)
3202 int number_of_vects
= 0, i
;
3203 unsigned int child_index
= 0;
3204 HOST_WIDE_INT lhs_size_unit
, rhs_size_unit
;
3205 slp_tree child
= NULL
;
3208 bool vectorized_defs
;
3210 first_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[0];
3211 FOR_EACH_VEC_ELT (ops
, i
, oprnd
)
3213 /* For each operand we check if it has vectorized definitions in a child
3214 node or we need to create them (for invariants and constants). We
3215 check if the LHS of the first stmt of the next child matches OPRND.
3216 If it does, we found the correct child. Otherwise, we call
3217 vect_get_constant_vectors (), and not advance CHILD_INDEX in order
3218 to check this child node for the next operand. */
3219 vectorized_defs
= false;
3220 if (SLP_TREE_CHILDREN (slp_node
).length () > child_index
)
3222 child
= SLP_TREE_CHILDREN (slp_node
)[child_index
];
3224 /* We have to check both pattern and original def, if available. */
3225 if (SLP_TREE_DEF_TYPE (child
) == vect_internal_def
)
3227 gimple
*first_def
= SLP_TREE_SCALAR_STMTS (child
)[0];
3229 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def
));
3231 if (operand_equal_p (oprnd
, gimple_get_lhs (first_def
), 0)
3233 && operand_equal_p (oprnd
, gimple_get_lhs (related
), 0)))
3235 /* The number of vector defs is determined by the number of
3236 vector statements in the node from which we get those
3238 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (child
);
3239 vectorized_defs
= true;
3247 if (!vectorized_defs
)
3251 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
3252 /* Number of vector stmts was calculated according to LHS in
3253 vect_schedule_slp_instance (), fix it by replacing LHS with
3254 RHS, if necessary. See vect_get_smallest_scalar_type () for
3256 vect_get_smallest_scalar_type (first_stmt
, &lhs_size_unit
,
3258 if (rhs_size_unit
!= lhs_size_unit
)
3260 number_of_vects
*= rhs_size_unit
;
3261 number_of_vects
/= lhs_size_unit
;
3266 /* Allocate memory for vectorized defs. */
3268 vec_defs
.create (number_of_vects
);
3270 /* For reduction defs we call vect_get_constant_vectors (), since we are
3271 looking for initial loop invariant values. */
3272 if (vectorized_defs
&& reduc_index
== -1)
3273 /* The defs are already vectorized. */
3274 vect_get_slp_vect_defs (child
, &vec_defs
);
3276 /* Build vectors from scalar defs. */
3277 vect_get_constant_vectors (oprnd
, slp_node
, &vec_defs
, i
,
3278 number_of_vects
, reduc_index
);
3280 vec_oprnds
->quick_push (vec_defs
);
3282 /* For reductions, we only need initial values. */
3283 if (reduc_index
!= -1)
3289 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
3290 building a vector of type MASK_TYPE from it) and two input vectors placed in
3291 DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
3292 shifting by STRIDE elements of DR_CHAIN for every copy.
3293 (STRIDE is the number of vectorized stmts for NODE divided by the number of
3295 VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
3296 the created stmts must be inserted. */
3299 vect_create_mask_and_perm (gimple
*stmt
,
3300 tree mask
, int first_vec_indx
, int second_vec_indx
,
3301 gimple_stmt_iterator
*gsi
, slp_tree node
,
3302 tree vectype
, vec
<tree
> dr_chain
,
3303 int ncopies
, int vect_stmts_counter
)
3306 gimple
*perm_stmt
= NULL
;
3307 int i
, stride_in
, stride_out
;
3308 tree first_vec
, second_vec
, data_ref
;
3310 stride_out
= SLP_TREE_NUMBER_OF_VEC_STMTS (node
) / ncopies
;
3311 stride_in
= dr_chain
.length () / ncopies
;
3313 /* Initialize the vect stmts of NODE to properly insert the generated
3315 for (i
= SLP_TREE_VEC_STMTS (node
).length ();
3316 i
< (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node
); i
++)
3317 SLP_TREE_VEC_STMTS (node
).quick_push (NULL
);
3319 perm_dest
= vect_create_destination_var (gimple_assign_lhs (stmt
), vectype
);
3320 for (i
= 0; i
< ncopies
; i
++)
3322 first_vec
= dr_chain
[first_vec_indx
];
3323 second_vec
= dr_chain
[second_vec_indx
];
3325 /* Generate the permute statement if necessary. */
3328 perm_stmt
= gimple_build_assign (perm_dest
, VEC_PERM_EXPR
,
3329 first_vec
, second_vec
, mask
);
3330 data_ref
= make_ssa_name (perm_dest
, perm_stmt
);
3331 gimple_set_lhs (perm_stmt
, data_ref
);
3332 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
3335 /* If mask was NULL_TREE generate the requested identity transform. */
3336 perm_stmt
= SSA_NAME_DEF_STMT (first_vec
);
3338 /* Store the vector statement in NODE. */
3339 SLP_TREE_VEC_STMTS (node
)[stride_out
* i
+ vect_stmts_counter
]
3342 first_vec_indx
+= stride_in
;
3343 second_vec_indx
+= stride_in
;
3348 /* Generate vector permute statements from a list of loads in DR_CHAIN.
3349 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
3350 permute statements for the SLP node NODE of the SLP instance
3351 SLP_NODE_INSTANCE. */
3354 vect_transform_slp_perm_load (slp_tree node
, vec
<tree
> dr_chain
,
3355 gimple_stmt_iterator
*gsi
, int vf
,
3356 slp_instance slp_node_instance
, bool analyze_only
)
3358 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3359 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3360 tree mask_element_type
= NULL_TREE
, mask_type
;
3361 int nunits
, vec_index
= 0;
3362 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3363 int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_node_instance
);
3364 int unroll_factor
, mask_element
, ncopies
;
3365 unsigned char *mask
;
3368 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3371 stmt_info
= vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info
));
3373 mode
= TYPE_MODE (vectype
);
3375 /* The generic VEC_PERM_EXPR code always uses an integral type of the
3376 same size as the vector element being permuted. */
3377 mask_element_type
= lang_hooks
.types
.type_for_mode
3378 (int_mode_for_mode (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3379 mask_type
= get_vectype_for_scalar_type (mask_element_type
);
3380 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3381 mask
= XALLOCAVEC (unsigned char, nunits
);
3382 unroll_factor
= SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3384 /* Number of copies is determined by the final vectorization factor
3385 relatively to SLP_NODE_INSTANCE unrolling factor. */
3386 ncopies
= vf
/ SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3388 /* Generate permutation masks for every NODE. Number of masks for each NODE
3389 is equal to GROUP_SIZE.
3390 E.g., we have a group of three nodes with three loads from the same
3391 location in each node, and the vector size is 4. I.e., we have a
3392 a0b0c0a1b1c1... sequence and we need to create the following vectors:
3393 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
3394 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
3397 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9}.
3398 The last mask is illegal since we assume two operands for permute
3399 operation, and the mask element values can't be outside that range.
3400 Hence, the last mask must be converted into {2,5,5,5}.
3401 For the first two permutations we need the first and the second input
3402 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
3403 we need the second and the third vectors: {b1,c1,a2,b2} and
3406 int vect_stmts_counter
= 0;
3408 int first_vec_index
= -1;
3409 int second_vec_index
= -1;
3412 for (int j
= 0; j
< unroll_factor
; j
++)
3414 for (int k
= 0; k
< group_size
; k
++)
3416 int i
= (SLP_TREE_LOAD_PERMUTATION (node
)[k
]
3417 + j
* STMT_VINFO_GROUP_SIZE (stmt_info
));
3418 vec_index
= i
/ nunits
;
3419 mask_element
= i
% nunits
;
3420 if (vec_index
== first_vec_index
3421 || first_vec_index
== -1)
3423 first_vec_index
= vec_index
;
3425 else if (vec_index
== second_vec_index
3426 || second_vec_index
== -1)
3428 second_vec_index
= vec_index
;
3429 mask_element
+= nunits
;
3433 if (dump_enabled_p ())
3435 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3436 "permutation requires at "
3437 "least three vectors ");
3438 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
3440 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3445 gcc_assert (mask_element
>= 0
3446 && mask_element
< 2 * nunits
);
3447 if (mask_element
!= index
)
3449 mask
[index
++] = mask_element
;
3451 if (index
== nunits
)
3454 && ! can_vec_perm_p (mode
, false, mask
))
3456 if (dump_enabled_p ())
3458 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
3460 "unsupported vect permute { ");
3461 for (i
= 0; i
< nunits
; ++i
)
3462 dump_printf (MSG_MISSED_OPTIMIZATION
, "%d ", mask
[i
]);
3463 dump_printf (MSG_MISSED_OPTIMIZATION
, "}\n");
3470 tree mask_vec
= NULL_TREE
;
3474 tree
*mask_elts
= XALLOCAVEC (tree
, nunits
);
3475 for (int l
= 0; l
< nunits
; ++l
)
3476 mask_elts
[l
] = build_int_cst (mask_element_type
,
3478 mask_vec
= build_vector (mask_type
, mask_elts
);
3481 if (second_vec_index
== -1)
3482 second_vec_index
= first_vec_index
;
3483 vect_create_mask_and_perm (stmt
, mask_vec
, first_vec_index
,
3485 gsi
, node
, vectype
, dr_chain
,
3486 ncopies
, vect_stmts_counter
++);
3490 first_vec_index
= -1;
3491 second_vec_index
= -1;
3502 /* Vectorize SLP instance tree in postorder. */
3505 vect_schedule_slp_instance (slp_tree node
, slp_instance instance
,
3506 unsigned int vectorization_factor
)
3509 bool grouped_store
, is_store
;
3510 gimple_stmt_iterator si
;
3511 stmt_vec_info stmt_info
;
3512 unsigned int vec_stmts_size
, nunits
, group_size
;
3517 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
3520 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3521 vect_schedule_slp_instance (child
, instance
, vectorization_factor
);
3523 /* Push SLP node def-type to stmts. */
3524 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3525 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
3526 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
3527 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = SLP_TREE_DEF_TYPE (child
);
3529 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3530 stmt_info
= vinfo_for_stmt (stmt
);
3532 /* VECTYPE is the type of the destination. */
3533 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3534 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (vectype
);
3535 group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
3537 /* For each SLP instance calculate number of vector stmts to be created
3538 for the scalar stmts in each node of the SLP tree. Number of vector
3539 elements in one vector iteration is the number of scalar elements in
3540 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
3542 Unless this is a SLP reduction in which case the number of vector
3543 stmts is equal to the number of vector stmts of the children. */
3544 if (GROUP_FIRST_ELEMENT (stmt_info
)
3545 && !STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3546 vec_stmts_size
= SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_CHILDREN (node
)[0]);
3548 vec_stmts_size
= (vectorization_factor
* group_size
) / nunits
;
3550 if (!SLP_TREE_VEC_STMTS (node
).exists ())
3552 SLP_TREE_VEC_STMTS (node
).create (vec_stmts_size
);
3553 SLP_TREE_NUMBER_OF_VEC_STMTS (node
) = vec_stmts_size
;
3556 if (dump_enabled_p ())
3558 dump_printf_loc (MSG_NOTE
,vect_location
,
3559 "------>vectorizing SLP node starting from: ");
3560 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3561 dump_printf (MSG_NOTE
, "\n");
3564 /* Vectorized stmts go before the last scalar stmt which is where
3565 all uses are ready. */
3566 si
= gsi_for_stmt (vect_find_last_scalar_stmt_in_slp (node
));
3568 /* Mark the first element of the reduction chain as reduction to properly
3569 transform the node. In the analysis phase only the last element of the
3570 chain is marked as reduction. */
3571 if (GROUP_FIRST_ELEMENT (stmt_info
) && !STMT_VINFO_GROUPED_ACCESS (stmt_info
)
3572 && GROUP_FIRST_ELEMENT (stmt_info
) == stmt
)
3574 STMT_VINFO_DEF_TYPE (stmt_info
) = vect_reduction_def
;
3575 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
3578 /* Handle two-operation SLP nodes by vectorizing the group with
3579 both operations and then performing a merge. */
3580 if (SLP_TREE_TWO_OPERATORS (node
))
3582 enum tree_code code0
= gimple_assign_rhs_code (stmt
);
3583 enum tree_code ocode
= ERROR_MARK
;
3585 unsigned char *mask
= XALLOCAVEC (unsigned char, group_size
);
3586 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, ostmt
)
3587 if (gimple_assign_rhs_code (ostmt
) != code0
)
3590 ocode
= gimple_assign_rhs_code (ostmt
);
3594 if (ocode
!= ERROR_MARK
)
3599 tree tmask
= NULL_TREE
;
3600 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3601 v0
= SLP_TREE_VEC_STMTS (node
).copy ();
3602 SLP_TREE_VEC_STMTS (node
).truncate (0);
3603 gimple_assign_set_rhs_code (stmt
, ocode
);
3604 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3605 gimple_assign_set_rhs_code (stmt
, code0
);
3606 v1
= SLP_TREE_VEC_STMTS (node
).copy ();
3607 SLP_TREE_VEC_STMTS (node
).truncate (0);
3608 tree meltype
= build_nonstandard_integer_type
3609 (GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3610 tree mvectype
= get_same_sized_vectype (meltype
, vectype
);
3612 for (j
= 0; j
< v0
.length (); ++j
)
3614 tree
*melts
= XALLOCAVEC (tree
, TYPE_VECTOR_SUBPARTS (vectype
));
3615 for (l
= 0; l
< TYPE_VECTOR_SUBPARTS (vectype
); ++l
)
3617 if (k
>= group_size
)
3619 melts
[l
] = build_int_cst
3620 (meltype
, mask
[k
++] * TYPE_VECTOR_SUBPARTS (vectype
) + l
);
3622 tmask
= build_vector (mvectype
, melts
);
3624 /* ??? Not all targets support a VEC_PERM_EXPR with a
3625 constant mask that would translate to a vec_merge RTX
3626 (with their vec_perm_const_ok). We can either not
3627 vectorize in that case or let veclower do its job.
3628 Unfortunately that isn't too great and at least for
3629 plus/minus we'd eventually like to match targets
3630 vector addsub instructions. */
3632 vstmt
= gimple_build_assign (make_ssa_name (vectype
),
3634 gimple_assign_lhs (v0
[j
]),
3635 gimple_assign_lhs (v1
[j
]), tmask
);
3636 vect_finish_stmt_generation (stmt
, vstmt
, &si
);
3637 SLP_TREE_VEC_STMTS (node
).quick_push (vstmt
);
3644 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3646 /* Restore stmt def-types. */
3647 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3648 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
3649 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
3650 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_internal_def
;
3655 /* Replace scalar calls from SLP node NODE with setting of their lhs to zero.
3656 For loop vectorization this is done in vectorizable_call, but for SLP
3657 it needs to be deferred until end of vect_schedule_slp, because multiple
3658 SLP instances may refer to the same scalar stmt. */
3661 vect_remove_slp_scalar_calls (slp_tree node
)
3663 gimple
*stmt
, *new_stmt
;
3664 gimple_stmt_iterator gsi
;
3668 stmt_vec_info stmt_info
;
3670 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
3673 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3674 vect_remove_slp_scalar_calls (child
);
3676 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
3678 if (!is_gimple_call (stmt
) || gimple_bb (stmt
) == NULL
)
3680 stmt_info
= vinfo_for_stmt (stmt
);
3681 if (stmt_info
== NULL
3682 || is_pattern_stmt_p (stmt_info
)
3683 || !PURE_SLP_STMT (stmt_info
))
3685 lhs
= gimple_call_lhs (stmt
);
3686 new_stmt
= gimple_build_assign (lhs
, build_zero_cst (TREE_TYPE (lhs
)));
3687 set_vinfo_for_stmt (new_stmt
, stmt_info
);
3688 set_vinfo_for_stmt (stmt
, NULL
);
3689 STMT_VINFO_STMT (stmt_info
) = new_stmt
;
3690 gsi
= gsi_for_stmt (stmt
);
3691 gsi_replace (&gsi
, new_stmt
, false);
3692 SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt
)) = new_stmt
;
3696 /* Generate vector code for all SLP instances in the loop/basic block. */
3699 vect_schedule_slp (vec_info
*vinfo
)
3701 vec
<slp_instance
> slp_instances
;
3702 slp_instance instance
;
3704 bool is_store
= false;
3706 slp_instances
= vinfo
->slp_instances
;
3707 if (is_a
<loop_vec_info
> (vinfo
))
3708 vf
= as_a
<loop_vec_info
> (vinfo
)->vectorization_factor
;
3712 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3714 /* Schedule the tree of INSTANCE. */
3715 is_store
= vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance
),
3717 if (dump_enabled_p ())
3718 dump_printf_loc (MSG_NOTE
, vect_location
,
3719 "vectorizing stmts using SLP.\n");
3722 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3724 slp_tree root
= SLP_INSTANCE_TREE (instance
);
3727 gimple_stmt_iterator gsi
;
3729 /* Remove scalar call stmts. Do not do this for basic-block
3730 vectorization as not all uses may be vectorized.
3731 ??? Why should this be necessary? DCE should be able to
3732 remove the stmts itself.
3733 ??? For BB vectorization we can as well remove scalar
3734 stmts starting from the SLP tree root if they have no
3736 if (is_a
<loop_vec_info
> (vinfo
))
3737 vect_remove_slp_scalar_calls (root
);
3739 for (j
= 0; SLP_TREE_SCALAR_STMTS (root
).iterate (j
, &store
)
3740 && j
< SLP_INSTANCE_GROUP_SIZE (instance
); j
++)
3742 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store
)))
3745 if (is_pattern_stmt_p (vinfo_for_stmt (store
)))
3746 store
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (store
));
3747 /* Free the attached stmt_vec_info and remove the stmt. */
3748 gsi
= gsi_for_stmt (store
);
3749 unlink_stmt_vdef (store
);
3750 gsi_remove (&gsi
, true);
3751 release_defs (store
);
3752 free_stmt_vec_info (store
);