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 ())
973 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
974 if (SLP_TREE_DEF_TYPE (grandchild
) == vect_internal_def
)
979 this_loads
.truncate (old_nloads
);
980 this_tree_size
= old_tree_size
;
981 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
982 vect_free_slp_tree (grandchild
);
983 SLP_TREE_CHILDREN (child
).truncate (0);
985 dump_printf_loc (MSG_NOTE
, vect_location
,
986 "Building parent vector operands from "
987 "scalars instead\n");
988 oprnd_info
->def_stmts
= vNULL
;
989 SLP_TREE_DEF_TYPE (child
) = vect_external_def
;
990 children
.safe_push (child
);
995 oprnd_info
->def_stmts
= vNULL
;
996 children
.safe_push (child
);
1000 /* If the SLP build failed fatally and we analyze a basic-block
1001 simply treat nodes we fail to build as externally defined
1002 (and thus build vectors from the scalar defs).
1003 The cost model will reject outright expensive cases.
1004 ??? This doesn't treat cases where permutation ultimatively
1005 fails (or we don't try permutation below). Ideally we'd
1006 even compute a permutation that will end up with the maximum
1008 if (is_a
<bb_vec_info
> (vinfo
)
1010 /* ??? Rejecting patterns this way doesn't work. We'd have to
1011 do extra work to cancel the pattern so the uses see the
1013 && !is_pattern_stmt_p (vinfo_for_stmt (stmt
)))
1015 dump_printf_loc (MSG_NOTE
, vect_location
,
1016 "Building vector operands from scalars\n");
1017 child
= vect_create_new_slp_node (oprnd_info
->def_stmts
);
1018 SLP_TREE_DEF_TYPE (child
) = vect_external_def
;
1019 children
.safe_push (child
);
1020 oprnd_info
->def_stmts
= vNULL
;
1024 /* If the SLP build for operand zero failed and operand zero
1025 and one can be commutated try that for the scalar stmts
1026 that failed the match. */
1028 /* A first scalar stmt mismatch signals a fatal mismatch. */
1030 /* ??? For COND_EXPRs we can swap the comparison operands
1031 as well as the arms under some constraints. */
1033 && oprnds_info
[1]->first_dt
== vect_internal_def
1034 && is_gimple_assign (stmt
)
1035 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
1037 /* Do so only if the number of not successful permutes was nor more
1038 than a cut-ff as re-trying the recursive match on
1039 possibly each level of the tree would expose exponential
1043 /* Verify if we can safely swap or if we committed to a specific
1044 operand order already. */
1045 for (j
= 0; j
< group_size
; ++j
)
1047 && STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmts
[j
])) != 0)
1049 if (dump_enabled_p ())
1051 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1052 "Build SLP failed: cannot swap operands "
1054 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
1060 /* Swap mismatched definition stmts. */
1061 dump_printf_loc (MSG_NOTE
, vect_location
,
1062 "Re-trying with swapped operands of stmts ");
1063 for (j
= 0; j
< group_size
; ++j
)
1066 std::swap (oprnds_info
[0]->def_stmts
[j
],
1067 oprnds_info
[1]->def_stmts
[j
]);
1068 dump_printf (MSG_NOTE
, "%d ", j
);
1070 dump_printf (MSG_NOTE
, "\n");
1071 /* And try again with scratch 'matches' ... */
1072 bool *tem
= XALLOCAVEC (bool, group_size
);
1073 if ((child
= vect_build_slp_tree (vinfo
, oprnd_info
->def_stmts
,
1074 group_size
, &this_max_nunits
,
1075 &this_loads
, tem
, npermutes
,
1077 max_tree_size
)) != NULL
)
1079 /* ... so if successful we can apply the operand swapping
1080 to the GIMPLE IL. This is necessary because for example
1081 vect_get_slp_defs uses operand indexes and thus expects
1082 canonical operand order. This is also necessary even
1083 if we end up building the operand from scalars as
1084 we'll continue to process swapped operand two. */
1085 for (j
= 0; j
< group_size
; ++j
)
1087 gimple
*stmt
= stmts
[j
];
1088 gimple_set_plf (stmt
, GF_PLF_1
, false);
1090 for (j
= 0; j
< group_size
; ++j
)
1092 gimple
*stmt
= stmts
[j
];
1095 /* Avoid swapping operands twice. */
1096 if (gimple_plf (stmt
, GF_PLF_1
))
1098 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
1099 gimple_assign_rhs2_ptr (stmt
));
1100 gimple_set_plf (stmt
, GF_PLF_1
, true);
1103 /* Verify we swap all duplicates or none. */
1105 for (j
= 0; j
< group_size
; ++j
)
1107 gimple
*stmt
= stmts
[j
];
1108 gcc_assert (gimple_plf (stmt
, GF_PLF_1
) == ! matches
[j
]);
1111 /* If we have all children of child built up from scalars then
1112 just throw that away and build it up this node from scalars. */
1113 if (!SLP_TREE_CHILDREN (child
).is_empty ())
1116 slp_tree grandchild
;
1118 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1119 if (SLP_TREE_DEF_TYPE (grandchild
) == vect_internal_def
)
1124 this_loads
.truncate (old_nloads
);
1125 this_tree_size
= old_tree_size
;
1126 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1127 vect_free_slp_tree (grandchild
);
1128 SLP_TREE_CHILDREN (child
).truncate (0);
1130 dump_printf_loc (MSG_NOTE
, vect_location
,
1131 "Building parent vector operands from "
1132 "scalars instead\n");
1133 oprnd_info
->def_stmts
= vNULL
;
1134 SLP_TREE_DEF_TYPE (child
) = vect_external_def
;
1135 children
.safe_push (child
);
1140 oprnd_info
->def_stmts
= vNULL
;
1141 children
.safe_push (child
);
1149 gcc_assert (child
== NULL
);
1150 FOR_EACH_VEC_ELT (children
, j
, child
)
1151 vect_free_slp_tree (child
);
1152 vect_free_oprnd_info (oprnds_info
);
1156 vect_free_oprnd_info (oprnds_info
);
1159 *tree_size
+= this_tree_size
;
1160 *max_nunits
= this_max_nunits
;
1161 loads
->safe_splice (this_loads
);
1163 node
= vect_create_new_slp_node (stmts
);
1164 SLP_TREE_TWO_OPERATORS (node
) = two_operators
;
1165 SLP_TREE_CHILDREN (node
).splice (children
);
1169 /* Dump a slp tree NODE using flags specified in DUMP_KIND. */
1172 vect_print_slp_tree (int dump_kind
, location_t loc
, slp_tree node
)
1178 dump_printf_loc (dump_kind
, loc
, "node%s\n",
1179 SLP_TREE_DEF_TYPE (node
) != vect_internal_def
1180 ? " (external)" : "");
1181 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1183 dump_printf_loc (dump_kind
, loc
, "\tstmt %d ", i
);
1184 dump_gimple_stmt (dump_kind
, TDF_SLIM
, stmt
, 0);
1186 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1187 vect_print_slp_tree (dump_kind
, loc
, child
);
1191 /* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
1192 If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
1193 J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
1194 stmts in NODE are to be marked. */
1197 vect_mark_slp_stmts (slp_tree node
, enum slp_vect_type mark
, int j
)
1203 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
1206 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1207 if (j
< 0 || i
== j
)
1208 STMT_SLP_TYPE (vinfo_for_stmt (stmt
)) = mark
;
1210 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1211 vect_mark_slp_stmts (child
, mark
, j
);
1215 /* Mark the statements of the tree rooted at NODE as relevant (vect_used). */
1218 vect_mark_slp_stmts_relevant (slp_tree node
)
1222 stmt_vec_info stmt_info
;
1225 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
1228 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1230 stmt_info
= vinfo_for_stmt (stmt
);
1231 gcc_assert (!STMT_VINFO_RELEVANT (stmt_info
)
1232 || STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
);
1233 STMT_VINFO_RELEVANT (stmt_info
) = vect_used_in_scope
;
1236 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1237 vect_mark_slp_stmts_relevant (child
);
1241 /* Rearrange the statements of NODE according to PERMUTATION. */
1244 vect_slp_rearrange_stmts (slp_tree node
, unsigned int group_size
,
1245 vec
<unsigned> permutation
)
1248 vec
<gimple
*> tmp_stmts
;
1252 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1253 vect_slp_rearrange_stmts (child
, group_size
, permutation
);
1255 gcc_assert (group_size
== SLP_TREE_SCALAR_STMTS (node
).length ());
1256 tmp_stmts
.create (group_size
);
1257 tmp_stmts
.quick_grow_cleared (group_size
);
1259 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1260 tmp_stmts
[permutation
[i
]] = stmt
;
1262 SLP_TREE_SCALAR_STMTS (node
).release ();
1263 SLP_TREE_SCALAR_STMTS (node
) = tmp_stmts
;
1267 /* Attempt to reorder stmts in a reduction chain so that we don't
1268 require any load permutation. Return true if that was possible,
1269 otherwise return false. */
1272 vect_attempt_slp_rearrange_stmts (slp_instance slp_instn
)
1274 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1278 slp_tree node
, load
;
1280 /* Compare all the permutation sequences to the first one. We know
1281 that at least one load is permuted. */
1282 node
= SLP_INSTANCE_LOADS (slp_instn
)[0];
1283 if (!node
->load_permutation
.exists ())
1285 for (i
= 1; SLP_INSTANCE_LOADS (slp_instn
).iterate (i
, &load
); ++i
)
1287 if (!load
->load_permutation
.exists ())
1289 FOR_EACH_VEC_ELT (load
->load_permutation
, j
, lidx
)
1290 if (lidx
!= node
->load_permutation
[j
])
1294 /* Check that the loads in the first sequence are different and there
1295 are no gaps between them. */
1296 load_index
= sbitmap_alloc (group_size
);
1297 bitmap_clear (load_index
);
1298 FOR_EACH_VEC_ELT (node
->load_permutation
, i
, lidx
)
1300 if (lidx
>= group_size
)
1302 if (bitmap_bit_p (load_index
, lidx
))
1304 sbitmap_free (load_index
);
1307 bitmap_set_bit (load_index
, lidx
);
1309 for (i
= 0; i
< group_size
; i
++)
1310 if (!bitmap_bit_p (load_index
, i
))
1312 sbitmap_free (load_index
);
1315 sbitmap_free (load_index
);
1317 /* This permutation is valid for reduction. Since the order of the
1318 statements in the nodes is not important unless they are memory
1319 accesses, we can rearrange the statements in all the nodes
1320 according to the order of the loads. */
1321 vect_slp_rearrange_stmts (SLP_INSTANCE_TREE (slp_instn
), group_size
,
1322 node
->load_permutation
);
1324 /* We are done, no actual permutations need to be generated. */
1325 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1326 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1330 /* Check if the required load permutations in the SLP instance
1331 SLP_INSTN are supported. */
1334 vect_supported_load_permutation_p (slp_instance slp_instn
)
1336 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1337 unsigned int i
, j
, k
, next
;
1339 gimple
*stmt
, *load
, *next_load
;
1341 if (dump_enabled_p ())
1343 dump_printf_loc (MSG_NOTE
, vect_location
, "Load permutation ");
1344 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1345 if (node
->load_permutation
.exists ())
1346 FOR_EACH_VEC_ELT (node
->load_permutation
, j
, next
)
1347 dump_printf (MSG_NOTE
, "%d ", next
);
1349 for (k
= 0; k
< group_size
; ++k
)
1350 dump_printf (MSG_NOTE
, "%d ", k
);
1351 dump_printf (MSG_NOTE
, "\n");
1354 /* In case of reduction every load permutation is allowed, since the order
1355 of the reduction statements is not important (as opposed to the case of
1356 grouped stores). The only condition we need to check is that all the
1357 load nodes are of the same size and have the same permutation (and then
1358 rearrange all the nodes of the SLP instance according to this
1361 /* Check that all the load nodes are of the same size. */
1362 /* ??? Can't we assert this? */
1363 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1364 if (SLP_TREE_SCALAR_STMTS (node
).length () != (unsigned) group_size
)
1367 node
= SLP_INSTANCE_TREE (slp_instn
);
1368 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1370 /* Reduction (there are no data-refs in the root).
1371 In reduction chain the order of the loads is not important. */
1372 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))
1373 && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1375 if (vect_attempt_slp_rearrange_stmts (slp_instn
))
1378 /* Fallthru to general load permutation handling. */
1381 /* In basic block vectorization we allow any subchain of an interleaving
1383 FORNOW: not supported in loop SLP because of realignment compications. */
1384 if (STMT_VINFO_BB_VINFO (vinfo_for_stmt (stmt
)))
1386 /* Check whether the loads in an instance form a subchain and thus
1387 no permutation is necessary. */
1388 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1390 if (!SLP_TREE_LOAD_PERMUTATION (node
).exists ())
1392 bool subchain_p
= true;
1394 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), j
, load
)
1397 && (next_load
!= load
1398 || GROUP_GAP (vinfo_for_stmt (load
)) != 1))
1403 next_load
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (load
));
1406 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1409 /* Verify the permutation can be generated. */
1411 if (!vect_transform_slp_perm_load (node
, tem
, NULL
,
1412 1, slp_instn
, true))
1414 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
1416 "unsupported load permutation\n");
1424 /* For loop vectorization verify we can generate the permutation. */
1425 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1426 if (node
->load_permutation
.exists ()
1427 && !vect_transform_slp_perm_load
1429 SLP_INSTANCE_UNROLLING_FACTOR (slp_instn
), slp_instn
, true))
1436 /* Find the last store in SLP INSTANCE. */
1439 vect_find_last_scalar_stmt_in_slp (slp_tree node
)
1441 gimple
*last
= NULL
, *stmt
;
1443 for (int i
= 0; SLP_TREE_SCALAR_STMTS (node
).iterate (i
, &stmt
); i
++)
1445 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
1446 if (is_pattern_stmt_p (stmt_vinfo
))
1447 last
= get_later_stmt (STMT_VINFO_RELATED_STMT (stmt_vinfo
), last
);
1449 last
= get_later_stmt (stmt
, last
);
1455 /* Compute the cost for the SLP node NODE in the SLP instance INSTANCE. */
1458 vect_analyze_slp_cost_1 (slp_instance instance
, slp_tree node
,
1459 stmt_vector_for_cost
*prologue_cost_vec
,
1460 stmt_vector_for_cost
*body_cost_vec
,
1461 unsigned ncopies_for_cost
)
1466 stmt_vec_info stmt_info
;
1469 /* Recurse down the SLP tree. */
1470 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1471 if (SLP_TREE_DEF_TYPE (child
) == vect_internal_def
)
1472 vect_analyze_slp_cost_1 (instance
, child
, prologue_cost_vec
,
1473 body_cost_vec
, ncopies_for_cost
);
1475 /* Look at the first scalar stmt to determine the cost. */
1476 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1477 stmt_info
= vinfo_for_stmt (stmt
);
1478 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1480 if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info
)))
1481 vect_model_store_cost (stmt_info
, ncopies_for_cost
, false,
1482 vect_uninitialized_def
,
1483 node
, prologue_cost_vec
, body_cost_vec
);
1486 gcc_checking_assert (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)));
1487 if (SLP_TREE_LOAD_PERMUTATION (node
).exists ())
1489 /* If the load is permuted then the alignment is determined by
1490 the first group element not by the first scalar stmt DR. */
1491 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
1492 stmt_info
= vinfo_for_stmt (stmt
);
1493 /* Record the cost for the permutation. */
1494 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vec_perm
,
1495 stmt_info
, 0, vect_body
);
1496 /* And adjust the number of loads performed. */
1498 = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
1500 = (GROUP_SIZE (stmt_info
) - GROUP_GAP (stmt_info
)
1501 + nunits
- 1) / nunits
;
1502 ncopies_for_cost
*= SLP_INSTANCE_UNROLLING_FACTOR (instance
);
1504 /* Record the cost for the vector loads. */
1505 vect_model_load_cost (stmt_info
, ncopies_for_cost
, false,
1506 node
, prologue_cost_vec
, body_cost_vec
);
1512 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1513 stmt_info
, 0, vect_body
);
1514 if (SLP_TREE_TWO_OPERATORS (node
))
1516 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1517 stmt_info
, 0, vect_body
);
1518 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vec_perm
,
1519 stmt_info
, 0, vect_body
);
1523 /* Push SLP node def-type to stmts. */
1524 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1525 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
1526 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
1527 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = SLP_TREE_DEF_TYPE (child
);
1529 /* Scan operands and account for prologue cost of constants/externals.
1530 ??? This over-estimates cost for multiple uses and should be
1532 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1533 lhs
= gimple_get_lhs (stmt
);
1534 for (i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1536 tree op
= gimple_op (stmt
, i
);
1538 enum vect_def_type dt
;
1539 if (!op
|| op
== lhs
)
1541 if (vect_is_simple_use (op
, stmt_info
->vinfo
, &def_stmt
, &dt
))
1543 /* Without looking at the actual initializer a vector of
1544 constants can be implemented as load from the constant pool.
1545 ??? We need to pass down stmt_info for a vector type
1546 even if it points to the wrong stmt. */
1547 if (dt
== vect_constant_def
)
1548 record_stmt_cost (prologue_cost_vec
, 1, vector_load
,
1549 stmt_info
, 0, vect_prologue
);
1550 else if (dt
== vect_external_def
)
1551 record_stmt_cost (prologue_cost_vec
, 1, vec_construct
,
1552 stmt_info
, 0, vect_prologue
);
1556 /* Restore stmt def-types. */
1557 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1558 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
1559 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
1560 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_internal_def
;
1563 /* Compute the cost for the SLP instance INSTANCE. */
1566 vect_analyze_slp_cost (slp_instance instance
, void *data
)
1568 stmt_vector_for_cost body_cost_vec
, prologue_cost_vec
;
1569 unsigned ncopies_for_cost
;
1570 stmt_info_for_cost
*si
;
1573 if (dump_enabled_p ())
1574 dump_printf_loc (MSG_NOTE
, vect_location
,
1575 "=== vect_analyze_slp_cost ===\n");
1577 /* Calculate the number of vector stmts to create based on the unrolling
1578 factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
1579 GROUP_SIZE / NUNITS otherwise. */
1580 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1581 slp_tree node
= SLP_INSTANCE_TREE (instance
);
1582 stmt_vec_info stmt_info
= vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node
)[0]);
1583 /* Adjust the group_size by the vectorization factor which is always one
1584 for basic-block vectorization. */
1585 if (STMT_VINFO_LOOP_VINFO (stmt_info
))
1586 group_size
*= LOOP_VINFO_VECT_FACTOR (STMT_VINFO_LOOP_VINFO (stmt_info
));
1587 unsigned nunits
= TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
1588 /* For reductions look at a reduction operand in case the reduction
1589 operation is widening like DOT_PROD or SAD. */
1590 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1592 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1593 switch (gimple_assign_rhs_code (stmt
))
1597 nunits
= TYPE_VECTOR_SUBPARTS (get_vectype_for_scalar_type
1598 (TREE_TYPE (gimple_assign_rhs1 (stmt
))));
1603 ncopies_for_cost
= least_common_multiple (nunits
, group_size
) / nunits
;
1605 prologue_cost_vec
.create (10);
1606 body_cost_vec
.create (10);
1607 vect_analyze_slp_cost_1 (instance
, SLP_INSTANCE_TREE (instance
),
1608 &prologue_cost_vec
, &body_cost_vec
,
1611 /* Record the prologue costs, which were delayed until we were
1612 sure that SLP was successful. */
1613 FOR_EACH_VEC_ELT (prologue_cost_vec
, i
, si
)
1615 struct _stmt_vec_info
*stmt_info
1616 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1617 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1618 si
->misalign
, vect_prologue
);
1621 /* Record the instance's instructions in the target cost model. */
1622 FOR_EACH_VEC_ELT (body_cost_vec
, i
, si
)
1624 struct _stmt_vec_info
*stmt_info
1625 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1626 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1627 si
->misalign
, vect_body
);
1630 prologue_cost_vec
.release ();
1631 body_cost_vec
.release ();
1634 /* Splits a group of stores, currently beginning at FIRST_STMT, into two groups:
1635 one (still beginning at FIRST_STMT) of size GROUP1_SIZE (also containing
1636 the first GROUP1_SIZE stmts, since stores are consecutive), the second
1637 containing the remainder.
1638 Return the first stmt in the second group. */
1641 vect_split_slp_store_group (gimple
*first_stmt
, unsigned group1_size
)
1643 stmt_vec_info first_vinfo
= vinfo_for_stmt (first_stmt
);
1644 gcc_assert (GROUP_FIRST_ELEMENT (first_vinfo
) == first_stmt
);
1645 gcc_assert (group1_size
> 0);
1646 int group2_size
= GROUP_SIZE (first_vinfo
) - group1_size
;
1647 gcc_assert (group2_size
> 0);
1648 GROUP_SIZE (first_vinfo
) = group1_size
;
1650 gimple
*stmt
= first_stmt
;
1651 for (unsigned i
= group1_size
; i
> 1; i
--)
1653 stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
1654 gcc_assert (GROUP_GAP (vinfo_for_stmt (stmt
)) == 1);
1656 /* STMT is now the last element of the first group. */
1657 gimple
*group2
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
1658 GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
)) = 0;
1660 GROUP_SIZE (vinfo_for_stmt (group2
)) = group2_size
;
1661 for (stmt
= group2
; stmt
; stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
)))
1663 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = group2
;
1664 gcc_assert (GROUP_GAP (vinfo_for_stmt (stmt
)) == 1);
1667 /* For the second group, the GROUP_GAP is that before the original group,
1668 plus skipping over the first vector. */
1669 GROUP_GAP (vinfo_for_stmt (group2
)) =
1670 GROUP_GAP (first_vinfo
) + group1_size
;
1672 /* GROUP_GAP of the first group now has to skip over the second group too. */
1673 GROUP_GAP (first_vinfo
) += group2_size
;
1675 if (dump_enabled_p ())
1676 dump_printf_loc (MSG_NOTE
, vect_location
, "Split group into %d and %d\n",
1677 group1_size
, group2_size
);
1682 /* Analyze an SLP instance starting from a group of grouped stores. Call
1683 vect_build_slp_tree to build a tree of packed stmts if possible.
1684 Return FALSE if it's impossible to SLP any stmt in the loop. */
1687 vect_analyze_slp_instance (vec_info
*vinfo
,
1688 gimple
*stmt
, unsigned max_tree_size
)
1690 slp_instance new_instance
;
1692 unsigned int group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1693 unsigned int unrolling_factor
= 1, nunits
;
1694 tree vectype
, scalar_type
= NULL_TREE
;
1697 unsigned int max_nunits
= 0;
1698 vec
<slp_tree
> loads
;
1699 struct data_reference
*dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
));
1700 vec
<gimple
*> scalar_stmts
;
1702 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1706 scalar_type
= TREE_TYPE (DR_REF (dr
));
1707 vectype
= get_vectype_for_scalar_type (scalar_type
);
1711 gcc_assert (is_a
<loop_vec_info
> (vinfo
));
1712 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1715 group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1719 gcc_assert (is_a
<loop_vec_info
> (vinfo
));
1720 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1721 group_size
= as_a
<loop_vec_info
> (vinfo
)->reductions
.length ();
1726 if (dump_enabled_p ())
1728 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1729 "Build SLP failed: unsupported data-type ");
1730 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, scalar_type
);
1731 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1736 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
1738 /* Calculate the unrolling factor. */
1739 unrolling_factor
= least_common_multiple (nunits
, group_size
) / group_size
;
1740 if (unrolling_factor
!= 1 && is_a
<bb_vec_info
> (vinfo
))
1742 if (dump_enabled_p ())
1743 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1744 "Build SLP failed: unrolling required in basic"
1750 /* Create a node (a root of the SLP tree) for the packed grouped stores. */
1751 scalar_stmts
.create (group_size
);
1753 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1755 /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
1758 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next
))
1759 && STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)))
1760 scalar_stmts
.safe_push (
1761 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)));
1763 scalar_stmts
.safe_push (next
);
1764 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
1766 /* Mark the first element of the reduction chain as reduction to properly
1767 transform the node. In the reduction analysis phase only the last
1768 element of the chain is marked as reduction. */
1769 if (!STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
1770 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_reduction_def
;
1774 /* Collect reduction statements. */
1775 vec
<gimple
*> reductions
= as_a
<loop_vec_info
> (vinfo
)->reductions
;
1776 for (i
= 0; reductions
.iterate (i
, &next
); i
++)
1777 scalar_stmts
.safe_push (next
);
1780 loads
.create (group_size
);
1782 /* Build the tree for the SLP instance. */
1783 bool *matches
= XALLOCAVEC (bool, group_size
);
1784 unsigned npermutes
= 0;
1785 if ((node
= vect_build_slp_tree (vinfo
, scalar_stmts
, group_size
,
1786 &max_nunits
, &loads
, matches
, &npermutes
,
1787 NULL
, max_tree_size
)) != NULL
)
1789 /* Calculate the unrolling factor based on the smallest type. */
1790 if (max_nunits
> nunits
)
1791 unrolling_factor
= least_common_multiple (max_nunits
, group_size
)
1794 if (unrolling_factor
!= 1 && is_a
<bb_vec_info
> (vinfo
))
1796 if (dump_enabled_p ())
1797 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1798 "Build SLP failed: unrolling required in basic"
1800 vect_free_slp_tree (node
);
1805 /* Create a new SLP instance. */
1806 new_instance
= XNEW (struct _slp_instance
);
1807 SLP_INSTANCE_TREE (new_instance
) = node
;
1808 SLP_INSTANCE_GROUP_SIZE (new_instance
) = group_size
;
1809 SLP_INSTANCE_UNROLLING_FACTOR (new_instance
) = unrolling_factor
;
1810 SLP_INSTANCE_LOADS (new_instance
) = loads
;
1812 /* Compute the load permutation. */
1814 bool loads_permuted
= false;
1815 FOR_EACH_VEC_ELT (loads
, i
, load_node
)
1817 vec
<unsigned> load_permutation
;
1819 gimple
*load
, *first_stmt
;
1820 bool this_load_permuted
= false;
1821 load_permutation
.create (group_size
);
1822 first_stmt
= GROUP_FIRST_ELEMENT
1823 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node
)[0]));
1824 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node
), j
, load
)
1827 = vect_get_place_in_interleaving_chain (load
, first_stmt
);
1828 gcc_assert (load_place
!= -1);
1829 if (load_place
!= j
)
1830 this_load_permuted
= true;
1831 load_permutation
.safe_push (load_place
);
1833 if (!this_load_permuted
1834 /* The load requires permutation when unrolling exposes
1835 a gap either because the group is larger than the SLP
1836 group-size or because there is a gap between the groups. */
1837 && (unrolling_factor
== 1
1838 || (group_size
== GROUP_SIZE (vinfo_for_stmt (first_stmt
))
1839 && GROUP_GAP (vinfo_for_stmt (first_stmt
)) == 0)))
1841 load_permutation
.release ();
1844 SLP_TREE_LOAD_PERMUTATION (load_node
) = load_permutation
;
1845 loads_permuted
= true;
1850 if (!vect_supported_load_permutation_p (new_instance
))
1852 if (dump_enabled_p ())
1854 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1855 "Build SLP failed: unsupported load "
1857 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
1858 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1860 vect_free_slp_instance (new_instance
);
1865 /* If the loads and stores can be handled with load/store-lane
1866 instructions do not generate this SLP instance. */
1867 if (is_a
<loop_vec_info
> (vinfo
)
1869 && dr
&& vect_store_lanes_supported (vectype
, group_size
))
1872 FOR_EACH_VEC_ELT (loads
, i
, load_node
)
1874 gimple
*first_stmt
= GROUP_FIRST_ELEMENT
1875 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node
)[0]));
1876 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (first_stmt
);
1877 /* Use SLP for strided accesses (or if we can't load-lanes). */
1878 if (STMT_VINFO_STRIDED_P (stmt_vinfo
)
1879 || ! vect_load_lanes_supported
1880 (STMT_VINFO_VECTYPE (stmt_vinfo
),
1881 GROUP_SIZE (stmt_vinfo
)))
1884 if (i
== loads
.length ())
1886 if (dump_enabled_p ())
1887 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1888 "Built SLP cancelled: can use "
1889 "load/store-lanes\n");
1890 vect_free_slp_instance (new_instance
);
1895 vinfo
->slp_instances
.safe_push (new_instance
);
1897 if (dump_enabled_p ())
1899 dump_printf_loc (MSG_NOTE
, vect_location
,
1900 "Final SLP tree for instance:\n");
1901 vect_print_slp_tree (MSG_NOTE
, vect_location
, node
);
1907 /* Failed to SLP. */
1908 /* Free the allocated memory. */
1909 scalar_stmts
.release ();
1912 /* For basic block SLP, try to break the group up into multiples of the
1914 if (is_a
<bb_vec_info
> (vinfo
)
1915 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
1916 && STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
1918 /* We consider breaking the group only on VF boundaries from the existing
1920 for (i
= 0; i
< group_size
; i
++)
1921 if (!matches
[i
]) break;
1923 if (i
>= nunits
&& i
< group_size
)
1925 /* Split into two groups at the first vector boundary before i. */
1926 gcc_assert ((nunits
& (nunits
- 1)) == 0);
1927 unsigned group1_size
= i
& ~(nunits
- 1);
1929 gimple
*rest
= vect_split_slp_store_group (stmt
, group1_size
);
1930 bool res
= vect_analyze_slp_instance (vinfo
, stmt
, max_tree_size
);
1931 /* If the first non-match was in the middle of a vector,
1932 skip the rest of that vector. */
1933 if (group1_size
< i
)
1935 i
= group1_size
+ nunits
;
1937 rest
= vect_split_slp_store_group (rest
, nunits
);
1940 res
|= vect_analyze_slp_instance (vinfo
, rest
, max_tree_size
);
1943 /* Even though the first vector did not all match, we might be able to SLP
1944 (some) of the remainder. FORNOW ignore this possibility. */
1951 /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
1952 trees of packed scalar stmts if SLP is possible. */
1955 vect_analyze_slp (vec_info
*vinfo
, unsigned max_tree_size
)
1958 gimple
*first_element
;
1961 if (dump_enabled_p ())
1962 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_analyze_slp ===\n");
1964 /* Find SLP sequences starting from groups of grouped stores. */
1965 FOR_EACH_VEC_ELT (vinfo
->grouped_stores
, i
, first_element
)
1966 if (vect_analyze_slp_instance (vinfo
, first_element
, max_tree_size
))
1969 if (loop_vec_info loop_vinfo
= dyn_cast
<loop_vec_info
> (vinfo
))
1971 if (loop_vinfo
->reduction_chains
.length () > 0)
1973 /* Find SLP sequences starting from reduction chains. */
1974 FOR_EACH_VEC_ELT (loop_vinfo
->reduction_chains
, i
, first_element
)
1975 if (vect_analyze_slp_instance (vinfo
, first_element
,
1981 /* Don't try to vectorize SLP reductions if reduction chain was
1986 /* Find SLP sequences starting from groups of reductions. */
1987 if (loop_vinfo
->reductions
.length () > 1
1988 && vect_analyze_slp_instance (vinfo
, loop_vinfo
->reductions
[0],
1997 /* For each possible SLP instance decide whether to SLP it and calculate overall
1998 unrolling factor needed to SLP the loop. Return TRUE if decided to SLP at
1999 least one instance. */
2002 vect_make_slp_decision (loop_vec_info loop_vinfo
)
2004 unsigned int i
, unrolling_factor
= 1;
2005 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2006 slp_instance instance
;
2007 int decided_to_slp
= 0;
2009 if (dump_enabled_p ())
2010 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_make_slp_decision ==="
2013 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2015 /* FORNOW: SLP if you can. */
2016 if (unrolling_factor
< SLP_INSTANCE_UNROLLING_FACTOR (instance
))
2017 unrolling_factor
= SLP_INSTANCE_UNROLLING_FACTOR (instance
);
2019 /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
2020 call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
2021 loop-based vectorization. Such stmts will be marked as HYBRID. */
2022 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2026 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
) = unrolling_factor
;
2028 if (decided_to_slp
&& dump_enabled_p ())
2029 dump_printf_loc (MSG_NOTE
, vect_location
,
2030 "Decided to SLP %d instances. Unrolling factor %d\n",
2031 decided_to_slp
, unrolling_factor
);
2033 return (decided_to_slp
> 0);
2037 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
2038 can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
2041 vect_detect_hybrid_slp_stmts (slp_tree node
, unsigned i
, slp_vect_type stype
)
2043 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[i
];
2044 imm_use_iterator imm_iter
;
2046 stmt_vec_info use_vinfo
, stmt_vinfo
= vinfo_for_stmt (stmt
);
2048 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
2049 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2052 /* Propagate hybrid down the SLP tree. */
2053 if (stype
== hybrid
)
2055 else if (HYBRID_SLP_STMT (stmt_vinfo
))
2059 /* Check if a pure SLP stmt has uses in non-SLP stmts. */
2060 gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo
));
2061 /* If we get a pattern stmt here we have to use the LHS of the
2062 original stmt for immediate uses. */
2063 if (! STMT_VINFO_IN_PATTERN_P (stmt_vinfo
)
2064 && STMT_VINFO_RELATED_STMT (stmt_vinfo
))
2065 stmt
= STMT_VINFO_RELATED_STMT (stmt_vinfo
);
2066 if (TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2067 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, gimple_op (stmt
, 0))
2069 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2071 use_vinfo
= vinfo_for_stmt (use_stmt
);
2072 if (STMT_VINFO_IN_PATTERN_P (use_vinfo
)
2073 && STMT_VINFO_RELATED_STMT (use_vinfo
))
2074 use_vinfo
= vinfo_for_stmt (STMT_VINFO_RELATED_STMT (use_vinfo
));
2075 if (!STMT_SLP_TYPE (use_vinfo
)
2076 && (STMT_VINFO_RELEVANT (use_vinfo
)
2077 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo
)))
2078 && !(gimple_code (use_stmt
) == GIMPLE_PHI
2079 && STMT_VINFO_DEF_TYPE (use_vinfo
) == vect_reduction_def
))
2081 if (dump_enabled_p ())
2083 dump_printf_loc (MSG_NOTE
, vect_location
, "use of SLP "
2084 "def in non-SLP stmt: ");
2085 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, use_stmt
, 0);
2093 && !HYBRID_SLP_STMT (stmt_vinfo
))
2095 if (dump_enabled_p ())
2097 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2098 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
2100 STMT_SLP_TYPE (stmt_vinfo
) = hybrid
;
2103 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2104 if (SLP_TREE_DEF_TYPE (child
) != vect_external_def
)
2105 vect_detect_hybrid_slp_stmts (child
, i
, stype
);
2108 /* Helpers for vect_detect_hybrid_slp walking pattern stmt uses. */
2111 vect_detect_hybrid_slp_1 (tree
*tp
, int *, void *data
)
2113 walk_stmt_info
*wi
= (walk_stmt_info
*)data
;
2114 struct loop
*loopp
= (struct loop
*)wi
->info
;
2119 if (TREE_CODE (*tp
) == SSA_NAME
2120 && !SSA_NAME_IS_DEFAULT_DEF (*tp
))
2122 gimple
*def_stmt
= SSA_NAME_DEF_STMT (*tp
);
2123 if (flow_bb_inside_loop_p (loopp
, gimple_bb (def_stmt
))
2124 && PURE_SLP_STMT (vinfo_for_stmt (def_stmt
)))
2126 if (dump_enabled_p ())
2128 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2129 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2131 STMT_SLP_TYPE (vinfo_for_stmt (def_stmt
)) = hybrid
;
2139 vect_detect_hybrid_slp_2 (gimple_stmt_iterator
*gsi
, bool *handled
,
2142 /* If the stmt is in a SLP instance then this isn't a reason
2143 to mark use definitions in other SLP instances as hybrid. */
2144 if (STMT_SLP_TYPE (vinfo_for_stmt (gsi_stmt (*gsi
))) != loop_vect
)
2149 /* Find stmts that must be both vectorized and SLPed. */
2152 vect_detect_hybrid_slp (loop_vec_info loop_vinfo
)
2155 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2156 slp_instance instance
;
2158 if (dump_enabled_p ())
2159 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_detect_hybrid_slp ==="
2162 /* First walk all pattern stmt in the loop and mark defs of uses as
2163 hybrid because immediate uses in them are not recorded. */
2164 for (i
= 0; i
< LOOP_VINFO_LOOP (loop_vinfo
)->num_nodes
; ++i
)
2166 basic_block bb
= LOOP_VINFO_BBS (loop_vinfo
)[i
];
2167 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2170 gimple
*stmt
= gsi_stmt (gsi
);
2171 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2172 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
2175 memset (&wi
, 0, sizeof (wi
));
2176 wi
.info
= LOOP_VINFO_LOOP (loop_vinfo
);
2177 gimple_stmt_iterator gsi2
2178 = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info
));
2179 walk_gimple_stmt (&gsi2
, vect_detect_hybrid_slp_2
,
2180 vect_detect_hybrid_slp_1
, &wi
);
2181 walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
),
2182 vect_detect_hybrid_slp_2
,
2183 vect_detect_hybrid_slp_1
, &wi
);
2188 /* Then walk the SLP instance trees marking stmts with uses in
2189 non-SLP stmts as hybrid, also propagating hybrid down the
2190 SLP tree, collecting the above info on-the-fly. */
2191 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2193 for (unsigned i
= 0; i
< SLP_INSTANCE_GROUP_SIZE (instance
); ++i
)
2194 vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance
),
2200 /* Create and initialize a new bb_vec_info struct for BB, as well as
2201 stmt_vec_info structs for all the stmts in it. */
2204 new_bb_vec_info (gimple_stmt_iterator region_begin
,
2205 gimple_stmt_iterator region_end
)
2207 basic_block bb
= gsi_bb (region_begin
);
2208 bb_vec_info res
= NULL
;
2209 gimple_stmt_iterator gsi
;
2211 res
= (bb_vec_info
) xcalloc (1, sizeof (struct _bb_vec_info
));
2212 res
->kind
= vec_info::bb
;
2213 BB_VINFO_BB (res
) = bb
;
2214 res
->region_begin
= region_begin
;
2215 res
->region_end
= region_end
;
2217 for (gsi
= region_begin
; gsi_stmt (gsi
) != gsi_stmt (region_end
);
2220 gimple
*stmt
= gsi_stmt (gsi
);
2221 gimple_set_uid (stmt
, 0);
2222 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
));
2225 BB_VINFO_GROUPED_STORES (res
).create (10);
2226 BB_VINFO_SLP_INSTANCES (res
).create (2);
2227 BB_VINFO_TARGET_COST_DATA (res
) = init_cost (NULL
);
2234 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
2235 stmts in the basic block. */
2238 destroy_bb_vec_info (bb_vec_info bb_vinfo
)
2240 slp_instance instance
;
2246 vect_destroy_datarefs (bb_vinfo
);
2247 free_dependence_relations (BB_VINFO_DDRS (bb_vinfo
));
2248 BB_VINFO_GROUPED_STORES (bb_vinfo
).release ();
2249 FOR_EACH_VEC_ELT (BB_VINFO_SLP_INSTANCES (bb_vinfo
), i
, instance
)
2250 vect_free_slp_instance (instance
);
2251 BB_VINFO_SLP_INSTANCES (bb_vinfo
).release ();
2252 destroy_cost_data (BB_VINFO_TARGET_COST_DATA (bb_vinfo
));
2254 for (gimple_stmt_iterator si
= bb_vinfo
->region_begin
;
2255 gsi_stmt (si
) != gsi_stmt (bb_vinfo
->region_end
); gsi_next (&si
))
2257 gimple
*stmt
= gsi_stmt (si
);
2258 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2261 /* Free stmt_vec_info. */
2262 free_stmt_vec_info (stmt
);
2264 /* Reset region marker. */
2265 gimple_set_uid (stmt
, -1);
2268 BB_VINFO_BB (bb_vinfo
)->aux
= NULL
;
2273 /* Analyze statements contained in SLP tree node after recursively analyzing
2274 the subtree. Return TRUE if the operations are supported. */
2277 vect_slp_analyze_node_operations (slp_tree node
)
2284 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
2287 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2288 if (!vect_slp_analyze_node_operations (child
))
2292 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2294 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2295 gcc_assert (stmt_info
);
2296 gcc_assert (STMT_SLP_TYPE (stmt_info
) != loop_vect
);
2298 /* Push SLP node def-type to stmt operands. */
2299 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2300 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
2301 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child
)[i
]))
2302 = SLP_TREE_DEF_TYPE (child
);
2303 res
= vect_analyze_stmt (stmt
, &dummy
, node
);
2304 /* Restore def-types. */
2305 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2306 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
2307 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child
)[i
]))
2308 = vect_internal_def
;
2317 /* Analyze statements in SLP instances of the basic block. Return TRUE if the
2318 operations are supported. */
2321 vect_slp_analyze_operations (vec
<slp_instance
> slp_instances
, void *data
)
2323 slp_instance instance
;
2326 if (dump_enabled_p ())
2327 dump_printf_loc (MSG_NOTE
, vect_location
,
2328 "=== vect_slp_analyze_operations ===\n");
2330 for (i
= 0; slp_instances
.iterate (i
, &instance
); )
2332 if (!vect_slp_analyze_node_operations (SLP_INSTANCE_TREE (instance
)))
2334 dump_printf_loc (MSG_NOTE
, vect_location
,
2335 "removing SLP instance operations starting from: ");
2336 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
2337 SLP_TREE_SCALAR_STMTS
2338 (SLP_INSTANCE_TREE (instance
))[0], 0);
2339 vect_free_slp_instance (instance
);
2340 slp_instances
.ordered_remove (i
);
2344 /* Compute the costs of the SLP instance. */
2345 vect_analyze_slp_cost (instance
, data
);
2350 if (!slp_instances
.length ())
2357 /* Compute the scalar cost of the SLP node NODE and its children
2358 and return it. Do not account defs that are marked in LIFE and
2359 update LIFE according to uses of NODE. */
2362 vect_bb_slp_scalar_cost (basic_block bb
,
2363 slp_tree node
, vec
<bool, va_heap
> *life
)
2365 unsigned scalar_cost
= 0;
2370 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2373 ssa_op_iter op_iter
;
2374 def_operand_p def_p
;
2375 stmt_vec_info stmt_info
;
2380 /* If there is a non-vectorized use of the defs then the scalar
2381 stmt is kept live in which case we do not account it or any
2382 required defs in the SLP children in the scalar cost. This
2383 way we make the vectorization more costly when compared to
2385 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
2387 imm_use_iterator use_iter
;
2389 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, DEF_FROM_PTR (def_p
))
2390 if (!is_gimple_debug (use_stmt
)
2391 && (! vect_stmt_in_region_p (vinfo_for_stmt (stmt
)->vinfo
,
2393 || ! PURE_SLP_STMT (vinfo_for_stmt (use_stmt
))))
2396 BREAK_FROM_IMM_USE_STMT (use_iter
);
2402 stmt_info
= vinfo_for_stmt (stmt
);
2403 if (STMT_VINFO_DATA_REF (stmt_info
))
2405 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)))
2406 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2408 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2411 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2413 scalar_cost
+= stmt_cost
;
2416 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2417 if (SLP_TREE_DEF_TYPE (child
) == vect_internal_def
)
2418 scalar_cost
+= vect_bb_slp_scalar_cost (bb
, child
, life
);
2423 /* Check if vectorization of the basic block is profitable. */
2426 vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo
)
2428 vec
<slp_instance
> slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2429 slp_instance instance
;
2431 unsigned int vec_inside_cost
= 0, vec_outside_cost
= 0, scalar_cost
= 0;
2432 unsigned int vec_prologue_cost
= 0, vec_epilogue_cost
= 0;
2434 /* Calculate scalar cost. */
2435 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2437 auto_vec
<bool, 20> life
;
2438 life
.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance
));
2439 scalar_cost
+= vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo
),
2440 SLP_INSTANCE_TREE (instance
),
2444 /* Complete the target-specific cost calculation. */
2445 finish_cost (BB_VINFO_TARGET_COST_DATA (bb_vinfo
), &vec_prologue_cost
,
2446 &vec_inside_cost
, &vec_epilogue_cost
);
2448 vec_outside_cost
= vec_prologue_cost
+ vec_epilogue_cost
;
2450 if (dump_enabled_p ())
2452 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2453 dump_printf (MSG_NOTE
, " Vector inside of basic block cost: %d\n",
2455 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n", vec_prologue_cost
);
2456 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n", vec_epilogue_cost
);
2457 dump_printf (MSG_NOTE
, " Scalar cost of basic block: %d\n", scalar_cost
);
2460 /* Vectorization is profitable if its cost is more than the cost of scalar
2461 version. Note that we err on the vector side for equal cost because
2462 the cost estimate is otherwise quite pessimistic (constant uses are
2463 free on the scalar side but cost a load on the vector side for
2465 if (vec_outside_cost
+ vec_inside_cost
> scalar_cost
)
2471 /* Check if the basic block can be vectorized. Returns a bb_vec_info
2472 if so and sets fatal to true if failure is independent of
2473 current_vector_size. */
2476 vect_slp_analyze_bb_1 (gimple_stmt_iterator region_begin
,
2477 gimple_stmt_iterator region_end
,
2478 vec
<data_reference_p
> datarefs
, int n_stmts
,
2481 bb_vec_info bb_vinfo
;
2482 slp_instance instance
;
2486 /* The first group of checks is independent of the vector size. */
2489 if (n_stmts
> PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB
))
2491 if (dump_enabled_p ())
2492 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2493 "not vectorized: too many instructions in "
2495 free_data_refs (datarefs
);
2499 bb_vinfo
= new_bb_vec_info (region_begin
, region_end
);
2503 BB_VINFO_DATAREFS (bb_vinfo
) = datarefs
;
2505 /* Analyze the data references. */
2507 if (!vect_analyze_data_refs (bb_vinfo
, &min_vf
))
2509 if (dump_enabled_p ())
2510 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2511 "not vectorized: unhandled data-ref in basic "
2514 destroy_bb_vec_info (bb_vinfo
);
2518 if (BB_VINFO_DATAREFS (bb_vinfo
).length () < 2)
2520 if (dump_enabled_p ())
2521 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2522 "not vectorized: not enough data-refs in "
2525 destroy_bb_vec_info (bb_vinfo
);
2529 if (!vect_analyze_data_ref_accesses (bb_vinfo
))
2531 if (dump_enabled_p ())
2532 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2533 "not vectorized: unhandled data access in "
2536 destroy_bb_vec_info (bb_vinfo
);
2540 /* If there are no grouped stores in the region there is no need
2541 to continue with pattern recog as vect_analyze_slp will fail
2543 if (bb_vinfo
->grouped_stores
.is_empty ())
2545 if (dump_enabled_p ())
2546 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2547 "not vectorized: no grouped stores in "
2550 destroy_bb_vec_info (bb_vinfo
);
2554 /* While the rest of the analysis below depends on it in some way. */
2557 vect_pattern_recog (bb_vinfo
);
2559 /* Check the SLP opportunities in the basic block, analyze and build SLP
2561 if (!vect_analyze_slp (bb_vinfo
, n_stmts
))
2563 if (dump_enabled_p ())
2565 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2566 "Failed to SLP the basic block.\n");
2567 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2568 "not vectorized: failed to find SLP opportunities "
2569 "in basic block.\n");
2572 destroy_bb_vec_info (bb_vinfo
);
2576 /* Analyze and verify the alignment of data references and the
2577 dependence in the SLP instances. */
2578 for (i
= 0; BB_VINFO_SLP_INSTANCES (bb_vinfo
).iterate (i
, &instance
); )
2580 if (! vect_slp_analyze_and_verify_instance_alignment (instance
)
2581 || ! vect_slp_analyze_instance_dependence (instance
))
2583 dump_printf_loc (MSG_NOTE
, vect_location
,
2584 "removing SLP instance operations starting from: ");
2585 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
2586 SLP_TREE_SCALAR_STMTS
2587 (SLP_INSTANCE_TREE (instance
))[0], 0);
2588 vect_free_slp_instance (instance
);
2589 BB_VINFO_SLP_INSTANCES (bb_vinfo
).ordered_remove (i
);
2593 /* Mark all the statements that we want to vectorize as pure SLP and
2595 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2596 vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance
));
2600 if (! BB_VINFO_SLP_INSTANCES (bb_vinfo
).length ())
2602 destroy_bb_vec_info (bb_vinfo
);
2606 if (!vect_slp_analyze_operations (BB_VINFO_SLP_INSTANCES (bb_vinfo
),
2607 BB_VINFO_TARGET_COST_DATA (bb_vinfo
)))
2609 if (dump_enabled_p ())
2610 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2611 "not vectorized: bad operation in basic block.\n");
2613 destroy_bb_vec_info (bb_vinfo
);
2617 /* Cost model: check if the vectorization is worthwhile. */
2618 if (!unlimited_cost_model (NULL
)
2619 && !vect_bb_vectorization_profitable_p (bb_vinfo
))
2621 if (dump_enabled_p ())
2622 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2623 "not vectorized: vectorization is not "
2626 destroy_bb_vec_info (bb_vinfo
);
2630 if (dump_enabled_p ())
2631 dump_printf_loc (MSG_NOTE
, vect_location
,
2632 "Basic block will be vectorized using SLP\n");
2638 /* Main entry for the BB vectorizer. Analyze and transform BB, returns
2639 true if anything in the basic-block was vectorized. */
2642 vect_slp_bb (basic_block bb
)
2644 bb_vec_info bb_vinfo
;
2645 gimple_stmt_iterator gsi
;
2646 unsigned int vector_sizes
;
2647 bool any_vectorized
= false;
2649 if (dump_enabled_p ())
2650 dump_printf_loc (MSG_NOTE
, vect_location
, "===vect_slp_analyze_bb===\n");
2652 /* Autodetect first vector size we try. */
2653 current_vector_size
= 0;
2654 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2656 gsi
= gsi_start_bb (bb
);
2660 if (gsi_end_p (gsi
))
2663 gimple_stmt_iterator region_begin
= gsi
;
2664 vec
<data_reference_p
> datarefs
= vNULL
;
2667 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
2669 gimple
*stmt
= gsi_stmt (gsi
);
2670 if (is_gimple_debug (stmt
))
2674 if (gimple_location (stmt
) != UNKNOWN_LOCATION
)
2675 vect_location
= gimple_location (stmt
);
2677 if (!find_data_references_in_stmt (NULL
, stmt
, &datarefs
))
2681 /* Skip leading unhandled stmts. */
2682 if (gsi_stmt (region_begin
) == gsi_stmt (gsi
))
2688 gimple_stmt_iterator region_end
= gsi
;
2690 bool vectorized
= false;
2692 bb_vinfo
= vect_slp_analyze_bb_1 (region_begin
, region_end
,
2693 datarefs
, insns
, fatal
);
2695 && dbg_cnt (vect_slp
))
2697 if (dump_enabled_p ())
2698 dump_printf_loc (MSG_NOTE
, vect_location
, "SLPing BB part\n");
2700 vect_schedule_slp (bb_vinfo
);
2702 if (dump_enabled_p ())
2703 dump_printf_loc (MSG_NOTE
, vect_location
,
2704 "basic block part vectorized\n");
2706 destroy_bb_vec_info (bb_vinfo
);
2711 destroy_bb_vec_info (bb_vinfo
);
2713 any_vectorized
|= vectorized
;
2715 vector_sizes
&= ~current_vector_size
;
2717 || vector_sizes
== 0
2718 || current_vector_size
== 0
2719 /* If vect_slp_analyze_bb_1 signaled that analysis for all
2720 vector sizes will fail do not bother iterating. */
2723 if (gsi_end_p (region_end
))
2726 /* Skip the unhandled stmt. */
2729 /* And reset vector sizes. */
2730 current_vector_size
= 0;
2731 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2735 /* Try the next biggest vector size. */
2736 current_vector_size
= 1 << floor_log2 (vector_sizes
);
2737 if (dump_enabled_p ())
2738 dump_printf_loc (MSG_NOTE
, vect_location
,
2739 "***** Re-trying analysis with "
2740 "vector size %d\n", current_vector_size
);
2747 return any_vectorized
;
2751 /* Return 1 if vector type of boolean constant which is OPNUM
2752 operand in statement STMT is a boolean vector. */
2755 vect_mask_constant_operand_p (gimple
*stmt
, int opnum
)
2757 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2758 enum tree_code code
= gimple_expr_code (stmt
);
2761 enum vect_def_type dt
;
2763 /* For comparison and COND_EXPR type is chosen depending
2764 on the other comparison operand. */
2765 if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2768 op
= gimple_assign_rhs1 (stmt
);
2770 op
= gimple_assign_rhs2 (stmt
);
2772 if (!vect_is_simple_use (op
, stmt_vinfo
->vinfo
, &def_stmt
,
2776 return !vectype
|| VECTOR_BOOLEAN_TYPE_P (vectype
);
2779 if (code
== COND_EXPR
)
2781 tree cond
= gimple_assign_rhs1 (stmt
);
2783 if (TREE_CODE (cond
) == SSA_NAME
)
2787 op
= TREE_OPERAND (cond
, 1);
2789 op
= TREE_OPERAND (cond
, 0);
2791 if (!vect_is_simple_use (op
, stmt_vinfo
->vinfo
, &def_stmt
,
2795 return !vectype
|| VECTOR_BOOLEAN_TYPE_P (vectype
);
2798 return VECTOR_BOOLEAN_TYPE_P (STMT_VINFO_VECTYPE (stmt_vinfo
));
2802 /* For constant and loop invariant defs of SLP_NODE this function returns
2803 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
2804 OP_NUM determines if we gather defs for operand 0 or operand 1 of the RHS of
2805 scalar stmts. NUMBER_OF_VECTORS is the number of vector defs to create.
2806 REDUC_INDEX is the index of the reduction operand in the statements, unless
2810 vect_get_constant_vectors (tree op
, slp_tree slp_node
,
2811 vec
<tree
> *vec_oprnds
,
2812 unsigned int op_num
, unsigned int number_of_vectors
,
2815 vec
<gimple
*> stmts
= SLP_TREE_SCALAR_STMTS (slp_node
);
2816 gimple
*stmt
= stmts
[0];
2817 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2821 unsigned j
, number_of_places_left_in_vector
;
2824 int group_size
= stmts
.length ();
2825 unsigned int vec_num
, i
;
2826 unsigned number_of_copies
= 1;
2828 voprnds
.create (number_of_vectors
);
2829 bool constant_p
, is_store
;
2830 tree neutral_op
= NULL
;
2831 enum tree_code code
= gimple_expr_code (stmt
);
2834 gimple_seq ctor_seq
= NULL
;
2836 /* Check if vector type is a boolean vector. */
2837 if (TREE_CODE (TREE_TYPE (op
)) == BOOLEAN_TYPE
2838 && vect_mask_constant_operand_p (stmt
, op_num
))
2840 = build_same_sized_truth_vector_type (STMT_VINFO_VECTYPE (stmt_vinfo
));
2842 vector_type
= get_vectype_for_scalar_type (TREE_TYPE (op
));
2843 nunits
= TYPE_VECTOR_SUBPARTS (vector_type
);
2845 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_reduction_def
2846 && reduc_index
!= -1)
2848 op_num
= reduc_index
;
2849 op
= gimple_op (stmt
, op_num
+ 1);
2850 /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
2851 we need either neutral operands or the original operands. See
2852 get_initial_def_for_reduction() for details. */
2855 case WIDEN_SUM_EXPR
:
2862 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2863 neutral_op
= build_real (TREE_TYPE (op
), dconst0
);
2865 neutral_op
= build_int_cst (TREE_TYPE (op
), 0);
2870 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2871 neutral_op
= build_real (TREE_TYPE (op
), dconst1
);
2873 neutral_op
= build_int_cst (TREE_TYPE (op
), 1);
2878 neutral_op
= build_int_cst (TREE_TYPE (op
), -1);
2881 /* For MIN/MAX we don't have an easy neutral operand but
2882 the initial values can be used fine here. Only for
2883 a reduction chain we have to force a neutral element. */
2886 if (!GROUP_FIRST_ELEMENT (stmt_vinfo
))
2890 def_stmt
= SSA_NAME_DEF_STMT (op
);
2891 loop
= (gimple_bb (stmt
))->loop_father
;
2892 neutral_op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2893 loop_preheader_edge (loop
));
2898 gcc_assert (!GROUP_FIRST_ELEMENT (stmt_vinfo
));
2903 if (STMT_VINFO_DATA_REF (stmt_vinfo
))
2906 op
= gimple_assign_rhs1 (stmt
);
2913 if (CONSTANT_CLASS_P (op
))
2918 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
2919 created vectors. It is greater than 1 if unrolling is performed.
2921 For example, we have two scalar operands, s1 and s2 (e.g., group of
2922 strided accesses of size two), while NUNITS is four (i.e., four scalars
2923 of this type can be packed in a vector). The output vector will contain
2924 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
2927 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
2928 containing the operands.
2930 For example, NUNITS is four as before, and the group size is 8
2931 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
2932 {s5, s6, s7, s8}. */
2934 number_of_copies
= nunits
* number_of_vectors
/ group_size
;
2936 number_of_places_left_in_vector
= nunits
;
2937 elts
= XALLOCAVEC (tree
, nunits
);
2938 bool place_after_defs
= false;
2939 for (j
= 0; j
< number_of_copies
; j
++)
2941 for (i
= group_size
- 1; stmts
.iterate (i
, &stmt
); i
--)
2944 op
= gimple_assign_rhs1 (stmt
);
2951 tree cond
= gimple_assign_rhs1 (stmt
);
2952 if (TREE_CODE (cond
) == SSA_NAME
)
2953 op
= gimple_op (stmt
, op_num
+ 1);
2954 else if (op_num
== 0 || op_num
== 1)
2955 op
= TREE_OPERAND (cond
, op_num
);
2959 op
= gimple_assign_rhs2 (stmt
);
2961 op
= gimple_assign_rhs3 (stmt
);
2967 op
= gimple_call_arg (stmt
, op_num
);
2974 op
= gimple_op (stmt
, op_num
+ 1);
2975 /* Unlike the other binary operators, shifts/rotates have
2976 the shift count being int, instead of the same type as
2977 the lhs, so make sure the scalar is the right type if
2978 we are dealing with vectors of
2979 long long/long/short/char. */
2980 if (op_num
== 1 && TREE_CODE (op
) == INTEGER_CST
)
2981 op
= fold_convert (TREE_TYPE (vector_type
), op
);
2985 op
= gimple_op (stmt
, op_num
+ 1);
2990 if (reduc_index
!= -1)
2992 loop
= (gimple_bb (stmt
))->loop_father
;
2993 def_stmt
= SSA_NAME_DEF_STMT (op
);
2997 /* Get the def before the loop. In reduction chain we have only
2998 one initial value. */
2999 if ((j
!= (number_of_copies
- 1)
3000 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
3005 op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
3006 loop_preheader_edge (loop
));
3009 /* Create 'vect_ = {op0,op1,...,opn}'. */
3010 number_of_places_left_in_vector
--;
3012 if (!types_compatible_p (TREE_TYPE (vector_type
), TREE_TYPE (op
)))
3014 if (CONSTANT_CLASS_P (op
))
3016 if (VECTOR_BOOLEAN_TYPE_P (vector_type
))
3018 /* Can't use VIEW_CONVERT_EXPR for booleans because
3019 of possibly different sizes of scalar value and
3021 if (integer_zerop (op
))
3022 op
= build_int_cst (TREE_TYPE (vector_type
), 0);
3023 else if (integer_onep (op
))
3024 op
= build_int_cst (TREE_TYPE (vector_type
), 1);
3029 op
= fold_unary (VIEW_CONVERT_EXPR
,
3030 TREE_TYPE (vector_type
), op
);
3031 gcc_assert (op
&& CONSTANT_CLASS_P (op
));
3035 tree new_temp
= make_ssa_name (TREE_TYPE (vector_type
));
3037 if (VECTOR_BOOLEAN_TYPE_P (vector_type
))
3039 gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (op
)));
3040 init_stmt
= gimple_build_assign (new_temp
, NOP_EXPR
, op
);
3044 op
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (vector_type
),
3047 = gimple_build_assign (new_temp
, VIEW_CONVERT_EXPR
,
3050 gimple_seq_add_stmt (&ctor_seq
, init_stmt
);
3054 elts
[number_of_places_left_in_vector
] = op
;
3055 if (!CONSTANT_CLASS_P (op
))
3057 if (TREE_CODE (orig_op
) == SSA_NAME
3058 && !SSA_NAME_IS_DEFAULT_DEF (orig_op
)
3059 && STMT_VINFO_BB_VINFO (stmt_vinfo
)
3060 && (STMT_VINFO_BB_VINFO (stmt_vinfo
)->bb
3061 == gimple_bb (SSA_NAME_DEF_STMT (orig_op
))))
3062 place_after_defs
= true;
3064 if (number_of_places_left_in_vector
== 0)
3066 number_of_places_left_in_vector
= nunits
;
3069 vec_cst
= build_vector (vector_type
, elts
);
3072 vec
<constructor_elt
, va_gc
> *v
;
3074 vec_alloc (v
, nunits
);
3075 for (k
= 0; k
< nunits
; ++k
)
3076 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[k
]);
3077 vec_cst
= build_constructor (vector_type
, v
);
3080 gimple_stmt_iterator gsi
;
3081 if (place_after_defs
)
3084 (vect_find_last_scalar_stmt_in_slp (slp_node
));
3085 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, &gsi
);
3088 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, NULL
);
3089 if (ctor_seq
!= NULL
)
3091 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (init
));
3092 gsi_insert_seq_before_without_update (&gsi
, ctor_seq
,
3096 voprnds
.quick_push (init
);
3097 place_after_defs
= false;
3102 /* Since the vectors are created in the reverse order, we should invert
3104 vec_num
= voprnds
.length ();
3105 for (j
= vec_num
; j
!= 0; j
--)
3107 vop
= voprnds
[j
- 1];
3108 vec_oprnds
->quick_push (vop
);
3113 /* In case that VF is greater than the unrolling factor needed for the SLP
3114 group of stmts, NUMBER_OF_VECTORS to be created is greater than
3115 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
3116 to replicate the vectors. */
3117 while (number_of_vectors
> vec_oprnds
->length ())
3119 tree neutral_vec
= NULL
;
3124 neutral_vec
= build_vector_from_val (vector_type
, neutral_op
);
3126 vec_oprnds
->quick_push (neutral_vec
);
3130 for (i
= 0; vec_oprnds
->iterate (i
, &vop
) && i
< vec_num
; i
++)
3131 vec_oprnds
->quick_push (vop
);
3137 /* Get vectorized definitions from SLP_NODE that contains corresponding
3138 vectorized def-stmts. */
3141 vect_get_slp_vect_defs (slp_tree slp_node
, vec
<tree
> *vec_oprnds
)
3144 gimple
*vec_def_stmt
;
3147 gcc_assert (SLP_TREE_VEC_STMTS (slp_node
).exists ());
3149 FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (slp_node
), i
, vec_def_stmt
)
3151 gcc_assert (vec_def_stmt
);
3152 vec_oprnd
= gimple_get_lhs (vec_def_stmt
);
3153 vec_oprnds
->quick_push (vec_oprnd
);
3158 /* Get vectorized definitions for SLP_NODE.
3159 If the scalar definitions are loop invariants or constants, collect them and
3160 call vect_get_constant_vectors() to create vector stmts.
3161 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
3162 must be stored in the corresponding child of SLP_NODE, and we call
3163 vect_get_slp_vect_defs () to retrieve them. */
3166 vect_get_slp_defs (vec
<tree
> ops
, slp_tree slp_node
,
3167 vec
<vec
<tree
> > *vec_oprnds
, int reduc_index
)
3170 int number_of_vects
= 0, i
;
3171 unsigned int child_index
= 0;
3172 HOST_WIDE_INT lhs_size_unit
, rhs_size_unit
;
3173 slp_tree child
= NULL
;
3176 bool vectorized_defs
;
3178 first_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[0];
3179 FOR_EACH_VEC_ELT (ops
, i
, oprnd
)
3181 /* For each operand we check if it has vectorized definitions in a child
3182 node or we need to create them (for invariants and constants). We
3183 check if the LHS of the first stmt of the next child matches OPRND.
3184 If it does, we found the correct child. Otherwise, we call
3185 vect_get_constant_vectors (), and not advance CHILD_INDEX in order
3186 to check this child node for the next operand. */
3187 vectorized_defs
= false;
3188 if (SLP_TREE_CHILDREN (slp_node
).length () > child_index
)
3190 child
= SLP_TREE_CHILDREN (slp_node
)[child_index
];
3192 /* We have to check both pattern and original def, if available. */
3193 if (SLP_TREE_DEF_TYPE (child
) == vect_internal_def
)
3195 gimple
*first_def
= SLP_TREE_SCALAR_STMTS (child
)[0];
3197 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def
));
3199 if (operand_equal_p (oprnd
, gimple_get_lhs (first_def
), 0)
3201 && operand_equal_p (oprnd
, gimple_get_lhs (related
), 0)))
3203 /* The number of vector defs is determined by the number of
3204 vector statements in the node from which we get those
3206 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (child
);
3207 vectorized_defs
= true;
3215 if (!vectorized_defs
)
3219 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
3220 /* Number of vector stmts was calculated according to LHS in
3221 vect_schedule_slp_instance (), fix it by replacing LHS with
3222 RHS, if necessary. See vect_get_smallest_scalar_type () for
3224 vect_get_smallest_scalar_type (first_stmt
, &lhs_size_unit
,
3226 if (rhs_size_unit
!= lhs_size_unit
)
3228 number_of_vects
*= rhs_size_unit
;
3229 number_of_vects
/= lhs_size_unit
;
3234 /* Allocate memory for vectorized defs. */
3236 vec_defs
.create (number_of_vects
);
3238 /* For reduction defs we call vect_get_constant_vectors (), since we are
3239 looking for initial loop invariant values. */
3240 if (vectorized_defs
&& reduc_index
== -1)
3241 /* The defs are already vectorized. */
3242 vect_get_slp_vect_defs (child
, &vec_defs
);
3244 /* Build vectors from scalar defs. */
3245 vect_get_constant_vectors (oprnd
, slp_node
, &vec_defs
, i
,
3246 number_of_vects
, reduc_index
);
3248 vec_oprnds
->quick_push (vec_defs
);
3250 /* For reductions, we only need initial values. */
3251 if (reduc_index
!= -1)
3257 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
3258 building a vector of type MASK_TYPE from it) and two input vectors placed in
3259 DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
3260 shifting by STRIDE elements of DR_CHAIN for every copy.
3261 (STRIDE is the number of vectorized stmts for NODE divided by the number of
3263 VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
3264 the created stmts must be inserted. */
3267 vect_create_mask_and_perm (gimple
*stmt
,
3268 tree mask
, int first_vec_indx
, int second_vec_indx
,
3269 gimple_stmt_iterator
*gsi
, slp_tree node
,
3270 tree vectype
, vec
<tree
> dr_chain
,
3271 int ncopies
, int vect_stmts_counter
)
3274 gimple
*perm_stmt
= NULL
;
3275 int i
, stride_in
, stride_out
;
3276 tree first_vec
, second_vec
, data_ref
;
3278 stride_out
= SLP_TREE_NUMBER_OF_VEC_STMTS (node
) / ncopies
;
3279 stride_in
= dr_chain
.length () / ncopies
;
3281 /* Initialize the vect stmts of NODE to properly insert the generated
3283 for (i
= SLP_TREE_VEC_STMTS (node
).length ();
3284 i
< (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node
); i
++)
3285 SLP_TREE_VEC_STMTS (node
).quick_push (NULL
);
3287 perm_dest
= vect_create_destination_var (gimple_assign_lhs (stmt
), vectype
);
3288 for (i
= 0; i
< ncopies
; i
++)
3290 first_vec
= dr_chain
[first_vec_indx
];
3291 second_vec
= dr_chain
[second_vec_indx
];
3293 /* Generate the permute statement if necessary. */
3296 perm_stmt
= gimple_build_assign (perm_dest
, VEC_PERM_EXPR
,
3297 first_vec
, second_vec
, mask
);
3298 data_ref
= make_ssa_name (perm_dest
, perm_stmt
);
3299 gimple_set_lhs (perm_stmt
, data_ref
);
3300 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
3303 /* If mask was NULL_TREE generate the requested identity transform. */
3304 perm_stmt
= SSA_NAME_DEF_STMT (first_vec
);
3306 /* Store the vector statement in NODE. */
3307 SLP_TREE_VEC_STMTS (node
)[stride_out
* i
+ vect_stmts_counter
]
3310 first_vec_indx
+= stride_in
;
3311 second_vec_indx
+= stride_in
;
3316 /* Generate vector permute statements from a list of loads in DR_CHAIN.
3317 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
3318 permute statements for the SLP node NODE of the SLP instance
3319 SLP_NODE_INSTANCE. */
3322 vect_transform_slp_perm_load (slp_tree node
, vec
<tree
> dr_chain
,
3323 gimple_stmt_iterator
*gsi
, int vf
,
3324 slp_instance slp_node_instance
, bool analyze_only
)
3326 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3327 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3328 tree mask_element_type
= NULL_TREE
, mask_type
;
3329 int nunits
, vec_index
= 0;
3330 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3331 int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_node_instance
);
3332 int unroll_factor
, mask_element
, ncopies
;
3333 unsigned char *mask
;
3336 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3339 stmt_info
= vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info
));
3341 mode
= TYPE_MODE (vectype
);
3343 /* The generic VEC_PERM_EXPR code always uses an integral type of the
3344 same size as the vector element being permuted. */
3345 mask_element_type
= lang_hooks
.types
.type_for_mode
3346 (int_mode_for_mode (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3347 mask_type
= get_vectype_for_scalar_type (mask_element_type
);
3348 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3349 mask
= XALLOCAVEC (unsigned char, nunits
);
3350 unroll_factor
= SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3352 /* Number of copies is determined by the final vectorization factor
3353 relatively to SLP_NODE_INSTANCE unrolling factor. */
3354 ncopies
= vf
/ SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3356 /* Generate permutation masks for every NODE. Number of masks for each NODE
3357 is equal to GROUP_SIZE.
3358 E.g., we have a group of three nodes with three loads from the same
3359 location in each node, and the vector size is 4. I.e., we have a
3360 a0b0c0a1b1c1... sequence and we need to create the following vectors:
3361 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
3362 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
3365 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9}.
3366 The last mask is illegal since we assume two operands for permute
3367 operation, and the mask element values can't be outside that range.
3368 Hence, the last mask must be converted into {2,5,5,5}.
3369 For the first two permutations we need the first and the second input
3370 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
3371 we need the second and the third vectors: {b1,c1,a2,b2} and
3374 int vect_stmts_counter
= 0;
3376 int first_vec_index
= -1;
3377 int second_vec_index
= -1;
3380 for (int j
= 0; j
< unroll_factor
; j
++)
3382 for (int k
= 0; k
< group_size
; k
++)
3384 int i
= (SLP_TREE_LOAD_PERMUTATION (node
)[k
]
3385 + j
* STMT_VINFO_GROUP_SIZE (stmt_info
));
3386 vec_index
= i
/ nunits
;
3387 mask_element
= i
% nunits
;
3388 if (vec_index
== first_vec_index
3389 || first_vec_index
== -1)
3391 first_vec_index
= vec_index
;
3393 else if (vec_index
== second_vec_index
3394 || second_vec_index
== -1)
3396 second_vec_index
= vec_index
;
3397 mask_element
+= nunits
;
3401 if (dump_enabled_p ())
3403 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3404 "permutation requires at "
3405 "least three vectors ");
3406 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
3408 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3413 gcc_assert (mask_element
>= 0
3414 && mask_element
< 2 * nunits
);
3415 if (mask_element
!= index
)
3417 mask
[index
++] = mask_element
;
3419 if (index
== nunits
)
3422 && ! can_vec_perm_p (mode
, false, mask
))
3424 if (dump_enabled_p ())
3426 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
3428 "unsupported vect permute { ");
3429 for (i
= 0; i
< nunits
; ++i
)
3430 dump_printf (MSG_MISSED_OPTIMIZATION
, "%d ", mask
[i
]);
3431 dump_printf (MSG_MISSED_OPTIMIZATION
, "}\n");
3438 tree mask_vec
= NULL_TREE
;
3442 tree
*mask_elts
= XALLOCAVEC (tree
, nunits
);
3443 for (int l
= 0; l
< nunits
; ++l
)
3444 mask_elts
[l
] = build_int_cst (mask_element_type
,
3446 mask_vec
= build_vector (mask_type
, mask_elts
);
3449 if (second_vec_index
== -1)
3450 second_vec_index
= first_vec_index
;
3451 vect_create_mask_and_perm (stmt
, mask_vec
, first_vec_index
,
3453 gsi
, node
, vectype
, dr_chain
,
3454 ncopies
, vect_stmts_counter
++);
3458 first_vec_index
= -1;
3459 second_vec_index
= -1;
3470 /* Vectorize SLP instance tree in postorder. */
3473 vect_schedule_slp_instance (slp_tree node
, slp_instance instance
,
3474 unsigned int vectorization_factor
)
3477 bool grouped_store
, is_store
;
3478 gimple_stmt_iterator si
;
3479 stmt_vec_info stmt_info
;
3480 unsigned int vec_stmts_size
, nunits
, group_size
;
3485 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
3488 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3489 vect_schedule_slp_instance (child
, instance
, vectorization_factor
);
3491 /* Push SLP node def-type to stmts. */
3492 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3493 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
3494 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
3495 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = SLP_TREE_DEF_TYPE (child
);
3497 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3498 stmt_info
= vinfo_for_stmt (stmt
);
3500 /* VECTYPE is the type of the destination. */
3501 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3502 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (vectype
);
3503 group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
3505 /* For each SLP instance calculate number of vector stmts to be created
3506 for the scalar stmts in each node of the SLP tree. Number of vector
3507 elements in one vector iteration is the number of scalar elements in
3508 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
3510 Unless this is a SLP reduction in which case the number of vector
3511 stmts is equal to the number of vector stmts of the children. */
3512 if (GROUP_FIRST_ELEMENT (stmt_info
)
3513 && !STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3514 vec_stmts_size
= SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_CHILDREN (node
)[0]);
3516 vec_stmts_size
= (vectorization_factor
* group_size
) / nunits
;
3518 if (!SLP_TREE_VEC_STMTS (node
).exists ())
3520 SLP_TREE_VEC_STMTS (node
).create (vec_stmts_size
);
3521 SLP_TREE_NUMBER_OF_VEC_STMTS (node
) = vec_stmts_size
;
3524 if (dump_enabled_p ())
3526 dump_printf_loc (MSG_NOTE
,vect_location
,
3527 "------>vectorizing SLP node starting from: ");
3528 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3529 dump_printf (MSG_NOTE
, "\n");
3532 /* Vectorized stmts go before the last scalar stmt which is where
3533 all uses are ready. */
3534 si
= gsi_for_stmt (vect_find_last_scalar_stmt_in_slp (node
));
3536 /* Mark the first element of the reduction chain as reduction to properly
3537 transform the node. In the analysis phase only the last element of the
3538 chain is marked as reduction. */
3539 if (GROUP_FIRST_ELEMENT (stmt_info
) && !STMT_VINFO_GROUPED_ACCESS (stmt_info
)
3540 && GROUP_FIRST_ELEMENT (stmt_info
) == stmt
)
3542 STMT_VINFO_DEF_TYPE (stmt_info
) = vect_reduction_def
;
3543 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
3546 /* Handle two-operation SLP nodes by vectorizing the group with
3547 both operations and then performing a merge. */
3548 if (SLP_TREE_TWO_OPERATORS (node
))
3550 enum tree_code code0
= gimple_assign_rhs_code (stmt
);
3551 enum tree_code ocode
;
3553 unsigned char *mask
= XALLOCAVEC (unsigned char, group_size
);
3554 bool allsame
= true;
3555 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, ostmt
)
3556 if (gimple_assign_rhs_code (ostmt
) != code0
)
3560 ocode
= gimple_assign_rhs_code (ostmt
);
3569 tree tmask
= NULL_TREE
;
3570 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3571 v0
= SLP_TREE_VEC_STMTS (node
).copy ();
3572 SLP_TREE_VEC_STMTS (node
).truncate (0);
3573 gimple_assign_set_rhs_code (stmt
, ocode
);
3574 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3575 gimple_assign_set_rhs_code (stmt
, code0
);
3576 v1
= SLP_TREE_VEC_STMTS (node
).copy ();
3577 SLP_TREE_VEC_STMTS (node
).truncate (0);
3578 tree meltype
= build_nonstandard_integer_type
3579 (GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3580 tree mvectype
= get_same_sized_vectype (meltype
, vectype
);
3582 for (j
= 0; j
< v0
.length (); ++j
)
3584 tree
*melts
= XALLOCAVEC (tree
, TYPE_VECTOR_SUBPARTS (vectype
));
3585 for (l
= 0; l
< TYPE_VECTOR_SUBPARTS (vectype
); ++l
)
3587 if (k
>= group_size
)
3589 melts
[l
] = build_int_cst
3590 (meltype
, mask
[k
++] * TYPE_VECTOR_SUBPARTS (vectype
) + l
);
3592 tmask
= build_vector (mvectype
, melts
);
3594 /* ??? Not all targets support a VEC_PERM_EXPR with a
3595 constant mask that would translate to a vec_merge RTX
3596 (with their vec_perm_const_ok). We can either not
3597 vectorize in that case or let veclower do its job.
3598 Unfortunately that isn't too great and at least for
3599 plus/minus we'd eventually like to match targets
3600 vector addsub instructions. */
3602 vstmt
= gimple_build_assign (make_ssa_name (vectype
),
3604 gimple_assign_lhs (v0
[j
]),
3605 gimple_assign_lhs (v1
[j
]), tmask
);
3606 vect_finish_stmt_generation (stmt
, vstmt
, &si
);
3607 SLP_TREE_VEC_STMTS (node
).quick_push (vstmt
);
3614 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3616 /* Restore stmt def-types. */
3617 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3618 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
3619 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
3620 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_internal_def
;
3625 /* Replace scalar calls from SLP node NODE with setting of their lhs to zero.
3626 For loop vectorization this is done in vectorizable_call, but for SLP
3627 it needs to be deferred until end of vect_schedule_slp, because multiple
3628 SLP instances may refer to the same scalar stmt. */
3631 vect_remove_slp_scalar_calls (slp_tree node
)
3633 gimple
*stmt
, *new_stmt
;
3634 gimple_stmt_iterator gsi
;
3638 stmt_vec_info stmt_info
;
3640 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
3643 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3644 vect_remove_slp_scalar_calls (child
);
3646 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
3648 if (!is_gimple_call (stmt
) || gimple_bb (stmt
) == NULL
)
3650 stmt_info
= vinfo_for_stmt (stmt
);
3651 if (stmt_info
== NULL
3652 || is_pattern_stmt_p (stmt_info
)
3653 || !PURE_SLP_STMT (stmt_info
))
3655 lhs
= gimple_call_lhs (stmt
);
3656 new_stmt
= gimple_build_assign (lhs
, build_zero_cst (TREE_TYPE (lhs
)));
3657 set_vinfo_for_stmt (new_stmt
, stmt_info
);
3658 set_vinfo_for_stmt (stmt
, NULL
);
3659 STMT_VINFO_STMT (stmt_info
) = new_stmt
;
3660 gsi
= gsi_for_stmt (stmt
);
3661 gsi_replace (&gsi
, new_stmt
, false);
3662 SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt
)) = new_stmt
;
3666 /* Generate vector code for all SLP instances in the loop/basic block. */
3669 vect_schedule_slp (vec_info
*vinfo
)
3671 vec
<slp_instance
> slp_instances
;
3672 slp_instance instance
;
3674 bool is_store
= false;
3676 slp_instances
= vinfo
->slp_instances
;
3677 if (is_a
<loop_vec_info
> (vinfo
))
3678 vf
= as_a
<loop_vec_info
> (vinfo
)->vectorization_factor
;
3682 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3684 /* Schedule the tree of INSTANCE. */
3685 is_store
= vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance
),
3687 if (dump_enabled_p ())
3688 dump_printf_loc (MSG_NOTE
, vect_location
,
3689 "vectorizing stmts using SLP.\n");
3692 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3694 slp_tree root
= SLP_INSTANCE_TREE (instance
);
3697 gimple_stmt_iterator gsi
;
3699 /* Remove scalar call stmts. Do not do this for basic-block
3700 vectorization as not all uses may be vectorized.
3701 ??? Why should this be necessary? DCE should be able to
3702 remove the stmts itself.
3703 ??? For BB vectorization we can as well remove scalar
3704 stmts starting from the SLP tree root if they have no
3706 if (is_a
<loop_vec_info
> (vinfo
))
3707 vect_remove_slp_scalar_calls (root
);
3709 for (j
= 0; SLP_TREE_SCALAR_STMTS (root
).iterate (j
, &store
)
3710 && j
< SLP_INSTANCE_GROUP_SIZE (instance
); j
++)
3712 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store
)))
3715 if (is_pattern_stmt_p (vinfo_for_stmt (store
)))
3716 store
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (store
));
3717 /* Free the attached stmt_vec_info and remove the stmt. */
3718 gsi
= gsi_for_stmt (store
);
3719 unlink_stmt_vdef (store
);
3720 gsi_remove (&gsi
, true);
3721 release_defs (store
);
3722 free_stmt_vec_info (store
);