1 /* SLP - Basic Block Vectorization
2 Copyright (C) 2007-2015 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
4 and Ira Rosen <irar@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
33 #include "fold-const.h"
34 #include "stor-layout.h"
36 #include "gimple-pretty-print.h"
37 #include "internal-fn.h"
38 #include "gimple-iterator.h"
39 #include "tree-pass.h"
42 #include "insn-config.h"
51 #include "recog.h" /* FIXME: for insn_data */
52 #include "insn-codes.h"
54 #include "tree-vectorizer.h"
55 #include "langhooks.h"
56 #include "gimple-walk.h"
58 /* Extract the location of the basic block in the source code.
59 Return the basic block location if succeed and NULL if not. */
62 find_bb_location (basic_block bb
)
65 gimple_stmt_iterator si
;
68 return UNKNOWN_LOCATION
;
70 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
73 if (gimple_location (stmt
) != UNKNOWN_LOCATION
)
74 return gimple_location (stmt
);
77 return UNKNOWN_LOCATION
;
81 /* Recursively free the memory allocated for the SLP tree rooted at NODE. */
84 vect_free_slp_tree (slp_tree node
)
92 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
93 vect_free_slp_tree (child
);
95 SLP_TREE_CHILDREN (node
).release ();
96 SLP_TREE_SCALAR_STMTS (node
).release ();
97 SLP_TREE_VEC_STMTS (node
).release ();
98 SLP_TREE_LOAD_PERMUTATION (node
).release ();
104 /* Free the memory allocated for the SLP instance. */
107 vect_free_slp_instance (slp_instance instance
)
109 vect_free_slp_tree (SLP_INSTANCE_TREE (instance
));
110 SLP_INSTANCE_LOADS (instance
).release ();
115 /* Create an SLP node for SCALAR_STMTS. */
118 vect_create_new_slp_node (vec
<gimple
> scalar_stmts
)
121 gimple stmt
= scalar_stmts
[0];
124 if (is_gimple_call (stmt
))
125 nops
= gimple_call_num_args (stmt
);
126 else if (is_gimple_assign (stmt
))
128 nops
= gimple_num_ops (stmt
) - 1;
129 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
135 node
= XNEW (struct _slp_tree
);
136 SLP_TREE_SCALAR_STMTS (node
) = scalar_stmts
;
137 SLP_TREE_VEC_STMTS (node
).create (0);
138 SLP_TREE_CHILDREN (node
).create (nops
);
139 SLP_TREE_LOAD_PERMUTATION (node
) = vNULL
;
140 SLP_TREE_TWO_OPERATORS (node
) = false;
146 /* Allocate operands info for NOPS operands, and GROUP_SIZE def-stmts for each
148 static vec
<slp_oprnd_info
>
149 vect_create_oprnd_info (int nops
, int group_size
)
152 slp_oprnd_info oprnd_info
;
153 vec
<slp_oprnd_info
> oprnds_info
;
155 oprnds_info
.create (nops
);
156 for (i
= 0; i
< nops
; i
++)
158 oprnd_info
= XNEW (struct _slp_oprnd_info
);
159 oprnd_info
->def_stmts
.create (group_size
);
160 oprnd_info
->first_dt
= vect_uninitialized_def
;
161 oprnd_info
->first_op_type
= NULL_TREE
;
162 oprnd_info
->first_pattern
= false;
163 oprnd_info
->second_pattern
= false;
164 oprnds_info
.quick_push (oprnd_info
);
171 /* Free operands info. */
174 vect_free_oprnd_info (vec
<slp_oprnd_info
> &oprnds_info
)
177 slp_oprnd_info oprnd_info
;
179 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
181 oprnd_info
->def_stmts
.release ();
182 XDELETE (oprnd_info
);
185 oprnds_info
.release ();
189 /* Find the place of the data-ref in STMT in the interleaving chain that starts
190 from FIRST_STMT. Return -1 if the data-ref is not a part of the chain. */
193 vect_get_place_in_interleaving_chain (gimple stmt
, gimple first_stmt
)
195 gimple next_stmt
= first_stmt
;
198 if (first_stmt
!= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
203 if (next_stmt
== stmt
)
205 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
207 result
+= GROUP_GAP (vinfo_for_stmt (next_stmt
));
215 /* Get the defs for the rhs of STMT (collect them in OPRNDS_INFO), check that
216 they are of a valid type and that they match the defs of the first stmt of
217 the SLP group (stored in OPRNDS_INFO). If there was a fatal error
218 return -1, if the error could be corrected by swapping operands of the
219 operation return 1, if everything is ok return 0. */
222 vect_get_and_check_slp_defs (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
223 gimple stmt
, unsigned stmt_num
,
224 vec
<slp_oprnd_info
> *oprnds_info
)
227 unsigned int i
, number_of_oprnds
;
230 enum vect_def_type dt
= vect_uninitialized_def
;
231 struct loop
*loop
= NULL
;
232 bool pattern
= false;
233 slp_oprnd_info oprnd_info
;
234 int first_op_idx
= 1;
235 bool commutative
= false;
236 bool first_op_cond
= false;
237 bool first
= stmt_num
== 0;
238 bool second
= stmt_num
== 1;
241 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
243 if (is_gimple_call (stmt
))
245 number_of_oprnds
= gimple_call_num_args (stmt
);
248 else if (is_gimple_assign (stmt
))
250 enum tree_code code
= gimple_assign_rhs_code (stmt
);
251 number_of_oprnds
= gimple_num_ops (stmt
) - 1;
252 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
254 first_op_cond
= true;
259 commutative
= commutative_tree_code (code
);
264 bool swapped
= false;
265 for (i
= 0; i
< number_of_oprnds
; i
++)
270 if (i
== 0 || i
== 1)
271 oprnd
= TREE_OPERAND (gimple_op (stmt
, first_op_idx
),
274 oprnd
= gimple_op (stmt
, first_op_idx
+ i
- 1);
277 oprnd
= gimple_op (stmt
, first_op_idx
+ (swapped
? !i
: i
));
279 oprnd_info
= (*oprnds_info
)[i
];
281 if (!vect_is_simple_use (oprnd
, NULL
, loop_vinfo
, bb_vinfo
, &def_stmt
,
284 if (dump_enabled_p ())
286 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
287 "Build SLP failed: can't analyze def for ");
288 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
289 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
295 /* Check if DEF_STMT is a part of a pattern in LOOP and get the def stmt
296 from the pattern. Check that all the stmts of the node are in the
298 if (def_stmt
&& gimple_bb (def_stmt
)
299 && ((loop
&& flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
)))
300 || (!loop
&& gimple_bb (def_stmt
) == BB_VINFO_BB (bb_vinfo
)
301 && gimple_code (def_stmt
) != GIMPLE_PHI
))
302 && vinfo_for_stmt (def_stmt
)
303 && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (def_stmt
))
304 && !STMT_VINFO_RELEVANT (vinfo_for_stmt (def_stmt
))
305 && !STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt
)))
308 if (!first
&& !oprnd_info
->first_pattern
309 /* Allow different pattern state for the defs of the
310 first stmt in reduction chains. */
311 && (oprnd_info
->first_dt
!= vect_reduction_def
312 || (!second
&& !oprnd_info
->second_pattern
)))
322 if (dump_enabled_p ())
324 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
325 "Build SLP failed: some of the stmts"
326 " are in a pattern, and others are not ");
327 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
328 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
334 def_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
));
335 dt
= STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
));
337 if (dt
== vect_unknown_def_type
)
339 if (dump_enabled_p ())
340 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
341 "Unsupported pattern.\n");
345 switch (gimple_code (def_stmt
))
348 def
= gimple_phi_result (def_stmt
);
352 def
= gimple_assign_lhs (def_stmt
);
356 if (dump_enabled_p ())
357 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
358 "unsupported defining stmt:\n");
364 oprnd_info
->second_pattern
= pattern
;
368 oprnd_info
->first_dt
= dt
;
369 oprnd_info
->first_pattern
= pattern
;
370 oprnd_info
->first_op_type
= TREE_TYPE (oprnd
);
374 /* Not first stmt of the group, check that the def-stmt/s match
375 the def-stmt/s of the first stmt. Allow different definition
376 types for reduction chains: the first stmt must be a
377 vect_reduction_def (a phi node), and the rest
378 vect_internal_def. */
379 if (((oprnd_info
->first_dt
!= dt
380 && !(oprnd_info
->first_dt
== vect_reduction_def
381 && dt
== vect_internal_def
)
382 && !((oprnd_info
->first_dt
== vect_external_def
383 || oprnd_info
->first_dt
== vect_constant_def
)
384 && (dt
== vect_external_def
385 || dt
== vect_constant_def
)))
386 || !types_compatible_p (oprnd_info
->first_op_type
,
389 /* Try swapping operands if we got a mismatch. */
398 if (dump_enabled_p ())
399 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
400 "Build SLP failed: different types\n");
406 /* Check the types of the definitions. */
409 case vect_constant_def
:
410 case vect_external_def
:
411 case vect_reduction_def
:
414 case vect_internal_def
:
415 oprnd_info
->def_stmts
.quick_push (def_stmt
);
419 /* FORNOW: Not supported. */
420 if (dump_enabled_p ())
422 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
423 "Build SLP failed: illegal type of def ");
424 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, def
);
425 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
437 tree cond
= gimple_assign_rhs1 (stmt
);
438 swap_ssa_operands (stmt
, &TREE_OPERAND (cond
, 0),
439 &TREE_OPERAND (cond
, 1));
440 TREE_SET_CODE (cond
, swap_tree_comparison (TREE_CODE (cond
)));
443 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
444 gimple_assign_rhs2_ptr (stmt
));
451 /* Verify if the scalar stmts STMTS are isomorphic, require data
452 permutation or are of unsupported types of operation. Return
453 true if they are, otherwise return false and indicate in *MATCHES
454 which stmts are not isomorphic to the first one. If MATCHES[0]
455 is false then this indicates the comparison could not be
456 carried out or the stmts will never be vectorized by SLP. */
459 vect_build_slp_tree_1 (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
460 vec
<gimple
> stmts
, unsigned int group_size
,
461 unsigned nops
, unsigned int *max_nunits
,
462 unsigned int vectorization_factor
, bool *matches
,
466 gimple first_stmt
= stmts
[0], stmt
= stmts
[0];
467 enum tree_code first_stmt_code
= ERROR_MARK
;
468 enum tree_code alt_stmt_code
= ERROR_MARK
;
469 enum tree_code rhs_code
= ERROR_MARK
;
470 enum tree_code first_cond_code
= ERROR_MARK
;
472 bool need_same_oprnds
= false;
473 tree vectype
= NULL_TREE
, scalar_type
, first_op1
= NULL_TREE
;
476 machine_mode optab_op2_mode
;
477 machine_mode vec_mode
;
479 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);
491 dump_printf (MSG_NOTE
, "\n");
494 /* Fail to vectorize statements marked as unvectorizable. */
495 if (!STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt
)))
497 if (dump_enabled_p ())
499 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
500 "Build SLP failed: unvectorizable statement ");
501 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
502 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
504 /* Fatal mismatch. */
509 lhs
= gimple_get_lhs (stmt
);
510 if (lhs
== NULL_TREE
)
512 if (dump_enabled_p ())
514 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
515 "Build SLP failed: not GIMPLE_ASSIGN nor "
517 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
518 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
520 /* Fatal mismatch. */
525 if (is_gimple_assign (stmt
)
526 && gimple_assign_rhs_code (stmt
) == COND_EXPR
527 && (cond
= gimple_assign_rhs1 (stmt
))
528 && !COMPARISON_CLASS_P (cond
))
530 if (dump_enabled_p ())
532 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
533 "Build SLP failed: condition is not "
535 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
536 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
538 /* Fatal mismatch. */
543 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
, &dummy
);
544 vectype
= get_vectype_for_scalar_type (scalar_type
);
547 if (dump_enabled_p ())
549 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
550 "Build SLP failed: unsupported data-type ");
551 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
553 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
555 /* Fatal mismatch. */
560 /* If populating the vector type requires unrolling then fail
561 before adjusting *max_nunits for basic-block vectorization. */
563 && TYPE_VECTOR_SUBPARTS (vectype
) > group_size
)
565 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
566 "Build SLP failed: unrolling required "
567 "in basic block SLP\n");
568 /* Fatal mismatch. */
573 /* In case of multiple types we need to detect the smallest type. */
574 if (*max_nunits
< TYPE_VECTOR_SUBPARTS (vectype
))
576 *max_nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
578 vectorization_factor
= *max_nunits
;
581 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
583 rhs_code
= CALL_EXPR
;
584 if (gimple_call_internal_p (call_stmt
)
585 || gimple_call_tail_p (call_stmt
)
586 || gimple_call_noreturn_p (call_stmt
)
587 || !gimple_call_nothrow_p (call_stmt
)
588 || gimple_call_chain (call_stmt
))
590 if (dump_enabled_p ())
592 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
593 "Build SLP failed: unsupported call type ");
594 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
596 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
598 /* Fatal mismatch. */
604 rhs_code
= gimple_assign_rhs_code (stmt
);
606 /* Check the operation. */
609 first_stmt_code
= rhs_code
;
611 /* Shift arguments should be equal in all the packed stmts for a
612 vector shift with scalar shift operand. */
613 if (rhs_code
== LSHIFT_EXPR
|| rhs_code
== RSHIFT_EXPR
614 || rhs_code
== LROTATE_EXPR
615 || rhs_code
== RROTATE_EXPR
)
617 vec_mode
= TYPE_MODE (vectype
);
619 /* First see if we have a vector/vector shift. */
620 optab
= optab_for_tree_code (rhs_code
, vectype
,
624 || optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
626 /* No vector/vector shift, try for a vector/scalar shift. */
627 optab
= optab_for_tree_code (rhs_code
, vectype
,
632 if (dump_enabled_p ())
633 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
634 "Build SLP failed: no optab.\n");
635 /* Fatal mismatch. */
639 icode
= (int) optab_handler (optab
, vec_mode
);
640 if (icode
== CODE_FOR_nothing
)
642 if (dump_enabled_p ())
643 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
645 "op not supported by target.\n");
646 /* Fatal mismatch. */
650 optab_op2_mode
= insn_data
[icode
].operand
[2].mode
;
651 if (!VECTOR_MODE_P (optab_op2_mode
))
653 need_same_oprnds
= true;
654 first_op1
= gimple_assign_rhs2 (stmt
);
658 else if (rhs_code
== WIDEN_LSHIFT_EXPR
)
660 need_same_oprnds
= true;
661 first_op1
= gimple_assign_rhs2 (stmt
);
666 if (first_stmt_code
!= rhs_code
667 && alt_stmt_code
== ERROR_MARK
)
668 alt_stmt_code
= rhs_code
;
669 if (first_stmt_code
!= rhs_code
670 && (first_stmt_code
!= IMAGPART_EXPR
671 || rhs_code
!= REALPART_EXPR
)
672 && (first_stmt_code
!= REALPART_EXPR
673 || rhs_code
!= IMAGPART_EXPR
)
674 /* Handle mismatches in plus/minus by computing both
675 and merging the results. */
676 && !((first_stmt_code
== PLUS_EXPR
677 || first_stmt_code
== MINUS_EXPR
)
678 && (alt_stmt_code
== PLUS_EXPR
679 || alt_stmt_code
== MINUS_EXPR
)
680 && rhs_code
== alt_stmt_code
)
681 && !(STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
682 && (first_stmt_code
== ARRAY_REF
683 || first_stmt_code
== BIT_FIELD_REF
684 || first_stmt_code
== INDIRECT_REF
685 || first_stmt_code
== COMPONENT_REF
686 || first_stmt_code
== MEM_REF
)))
688 if (dump_enabled_p ())
690 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
691 "Build SLP failed: different operation "
693 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
694 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
696 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
704 && !operand_equal_p (first_op1
, gimple_assign_rhs2 (stmt
), 0))
706 if (dump_enabled_p ())
708 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
709 "Build SLP failed: different shift "
711 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
712 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
718 if (rhs_code
== CALL_EXPR
)
720 gimple first_stmt
= stmts
[0];
721 if (gimple_call_num_args (stmt
) != nops
722 || !operand_equal_p (gimple_call_fn (first_stmt
),
723 gimple_call_fn (stmt
), 0)
724 || gimple_call_fntype (first_stmt
)
725 != gimple_call_fntype (stmt
))
727 if (dump_enabled_p ())
729 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
730 "Build SLP failed: different calls in ");
731 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
733 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
741 /* Grouped store or load. */
742 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
744 if (REFERENCE_CLASS_P (lhs
))
752 /* Check that the size of interleaved loads group is not
753 greater than the SLP group size. */
755 = vectorization_factor
/ TYPE_VECTOR_SUBPARTS (vectype
);
757 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) == stmt
758 && ((GROUP_SIZE (vinfo_for_stmt (stmt
))
759 - GROUP_GAP (vinfo_for_stmt (stmt
)))
760 > ncopies
* group_size
))
762 if (dump_enabled_p ())
764 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
765 "Build SLP failed: the number "
766 "of interleaved loads is greater than "
767 "the SLP group size ");
768 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
770 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
772 /* Fatal mismatch. */
777 first_load
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
));
780 /* Check that there are no loads from different interleaving
781 chains in the same node. */
782 if (prev_first_load
!= first_load
)
784 if (dump_enabled_p ())
786 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
788 "Build SLP failed: different "
789 "interleaving chains in one node ");
790 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
792 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
799 prev_first_load
= first_load
;
801 } /* Grouped access. */
804 if (TREE_CODE_CLASS (rhs_code
) == tcc_reference
)
806 /* Not grouped load. */
807 if (dump_enabled_p ())
809 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
810 "Build SLP failed: not grouped load ");
811 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
812 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
815 /* FORNOW: Not grouped loads are not supported. */
816 /* Fatal mismatch. */
821 /* Not memory operation. */
822 if (TREE_CODE_CLASS (rhs_code
) != tcc_binary
823 && TREE_CODE_CLASS (rhs_code
) != tcc_unary
824 && TREE_CODE_CLASS (rhs_code
) != tcc_expression
825 && rhs_code
!= CALL_EXPR
)
827 if (dump_enabled_p ())
829 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
830 "Build SLP failed: operation");
831 dump_printf (MSG_MISSED_OPTIMIZATION
, " unsupported ");
832 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
833 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
835 /* Fatal mismatch. */
840 if (rhs_code
== COND_EXPR
)
842 tree cond_expr
= gimple_assign_rhs1 (stmt
);
845 first_cond_code
= TREE_CODE (cond_expr
);
846 else if (first_cond_code
!= TREE_CODE (cond_expr
))
848 if (dump_enabled_p ())
850 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
851 "Build SLP failed: different"
853 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
855 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
866 for (i
= 0; i
< group_size
; ++i
)
870 /* If we allowed a two-operation SLP node verify the target can cope
871 with the permute we are going to use. */
872 if (alt_stmt_code
!= ERROR_MARK
873 && TREE_CODE_CLASS (alt_stmt_code
) != tcc_reference
)
876 = XALLOCAVEC (unsigned char, TYPE_VECTOR_SUBPARTS (vectype
));
877 for (i
= 0; i
< TYPE_VECTOR_SUBPARTS (vectype
); ++i
)
880 if (gimple_assign_rhs_code (stmts
[i
% group_size
]) == alt_stmt_code
)
881 sel
[i
] += TYPE_VECTOR_SUBPARTS (vectype
);
883 if (!can_vec_perm_p (TYPE_MODE (vectype
), false, sel
))
885 for (i
= 0; i
< group_size
; ++i
)
886 if (gimple_assign_rhs_code (stmts
[i
]) == alt_stmt_code
)
889 if (dump_enabled_p ())
891 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
892 "Build SLP failed: different operation "
894 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
896 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
898 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
904 *two_operators
= true;
910 /* Recursively build an SLP tree starting from NODE.
911 Fail (and return a value not equal to zero) if def-stmts are not
912 isomorphic, require data permutation or are of unsupported types of
913 operation. Otherwise, return 0.
914 The value returned is the depth in the SLP tree where a mismatch
918 vect_build_slp_tree (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
919 slp_tree
*node
, unsigned int group_size
,
920 unsigned int *max_nunits
,
921 vec
<slp_tree
> *loads
,
922 unsigned int vectorization_factor
,
923 bool *matches
, unsigned *npermutes
, unsigned *tree_size
,
924 unsigned max_tree_size
)
926 unsigned nops
, i
, this_tree_size
= 0;
931 stmt
= SLP_TREE_SCALAR_STMTS (*node
)[0];
932 if (is_gimple_call (stmt
))
933 nops
= gimple_call_num_args (stmt
);
934 else if (is_gimple_assign (stmt
))
936 nops
= gimple_num_ops (stmt
) - 1;
937 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
943 bool two_operators
= false;
944 if (!vect_build_slp_tree_1 (loop_vinfo
, bb_vinfo
,
945 SLP_TREE_SCALAR_STMTS (*node
), group_size
, nops
,
946 max_nunits
, vectorization_factor
, matches
,
949 SLP_TREE_TWO_OPERATORS (*node
) = two_operators
;
951 /* If the SLP node is a load, terminate the recursion. */
952 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
953 && DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
955 loads
->safe_push (*node
);
959 /* Get at the operands, verifying they are compatible. */
960 vec
<slp_oprnd_info
> oprnds_info
= vect_create_oprnd_info (nops
, group_size
);
961 slp_oprnd_info oprnd_info
;
962 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (*node
), i
, stmt
)
964 switch (vect_get_and_check_slp_defs (loop_vinfo
, bb_vinfo
,
965 stmt
, i
, &oprnds_info
))
971 vect_free_oprnd_info (oprnds_info
);
978 for (i
= 0; i
< group_size
; ++i
)
981 vect_free_oprnd_info (oprnds_info
);
985 stmt
= SLP_TREE_SCALAR_STMTS (*node
)[0];
987 /* Create SLP_TREE nodes for the definition node/s. */
988 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
991 unsigned old_nloads
= loads
->length ();
992 unsigned old_max_nunits
= *max_nunits
;
994 if (oprnd_info
->first_dt
!= vect_internal_def
)
997 if (++this_tree_size
> max_tree_size
)
999 vect_free_oprnd_info (oprnds_info
);
1003 child
= vect_create_new_slp_node (oprnd_info
->def_stmts
);
1006 vect_free_oprnd_info (oprnds_info
);
1010 if (vect_build_slp_tree (loop_vinfo
, bb_vinfo
, &child
,
1011 group_size
, max_nunits
, loads
,
1012 vectorization_factor
, matches
,
1013 npermutes
, &this_tree_size
, max_tree_size
))
1015 /* If we have all children of child built up from scalars then just
1016 throw that away and build it up this node from scalars. */
1017 if (!SLP_TREE_CHILDREN (child
).is_empty ())
1020 slp_tree grandchild
;
1022 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1023 if (grandchild
!= NULL
)
1028 *max_nunits
= old_max_nunits
;
1029 loads
->truncate (old_nloads
);
1030 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1031 vect_free_slp_tree (grandchild
);
1032 SLP_TREE_CHILDREN (child
).truncate (0);
1034 dump_printf_loc (MSG_NOTE
, vect_location
,
1035 "Building parent vector operands from "
1036 "scalars instead\n");
1037 oprnd_info
->def_stmts
= vNULL
;
1038 vect_free_slp_tree (child
);
1039 SLP_TREE_CHILDREN (*node
).quick_push (NULL
);
1044 oprnd_info
->def_stmts
= vNULL
;
1045 SLP_TREE_CHILDREN (*node
).quick_push (child
);
1049 /* If the SLP build failed fatally and we analyze a basic-block
1050 simply treat nodes we fail to build as externally defined
1051 (and thus build vectors from the scalar defs).
1052 The cost model will reject outright expensive cases.
1053 ??? This doesn't treat cases where permutation ultimatively
1054 fails (or we don't try permutation below). Ideally we'd
1055 even compute a permutation that will end up with the maximum
1059 /* ??? Rejecting patterns this way doesn't work. We'd have to
1060 do extra work to cancel the pattern so the uses see the
1062 && !is_pattern_stmt_p (vinfo_for_stmt (stmt
)))
1065 slp_tree grandchild
;
1068 *max_nunits
= old_max_nunits
;
1069 loads
->truncate (old_nloads
);
1070 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1071 vect_free_slp_tree (grandchild
);
1072 SLP_TREE_CHILDREN (child
).truncate (0);
1074 dump_printf_loc (MSG_NOTE
, vect_location
,
1075 "Building vector operands from scalars\n");
1076 oprnd_info
->def_stmts
= vNULL
;
1077 vect_free_slp_tree (child
);
1078 SLP_TREE_CHILDREN (*node
).quick_push (NULL
);
1082 /* If the SLP build for operand zero failed and operand zero
1083 and one can be commutated try that for the scalar stmts
1084 that failed the match. */
1086 /* A first scalar stmt mismatch signals a fatal mismatch. */
1088 /* ??? For COND_EXPRs we can swap the comparison operands
1089 as well as the arms under some constraints. */
1091 && oprnds_info
[1]->first_dt
== vect_internal_def
1092 && is_gimple_assign (stmt
)
1093 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
1094 && !SLP_TREE_TWO_OPERATORS (*node
)
1095 /* Do so only if the number of not successful permutes was nor more
1096 than a cut-ff as re-trying the recursive match on
1097 possibly each level of the tree would expose exponential
1102 slp_tree grandchild
;
1105 *max_nunits
= old_max_nunits
;
1106 loads
->truncate (old_nloads
);
1107 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1108 vect_free_slp_tree (grandchild
);
1109 SLP_TREE_CHILDREN (child
).truncate (0);
1111 /* Swap mismatched definition stmts. */
1112 dump_printf_loc (MSG_NOTE
, vect_location
,
1113 "Re-trying with swapped operands of stmts ");
1114 for (j
= 0; j
< group_size
; ++j
)
1117 std::swap (oprnds_info
[0]->def_stmts
[j
],
1118 oprnds_info
[1]->def_stmts
[j
]);
1119 dump_printf (MSG_NOTE
, "%d ", j
);
1121 dump_printf (MSG_NOTE
, "\n");
1122 /* And try again with scratch 'matches' ... */
1123 bool *tem
= XALLOCAVEC (bool, group_size
);
1124 if (vect_build_slp_tree (loop_vinfo
, bb_vinfo
, &child
,
1125 group_size
, max_nunits
, loads
,
1126 vectorization_factor
,
1127 tem
, npermutes
, &this_tree_size
,
1130 /* ... so if successful we can apply the operand swapping
1131 to the GIMPLE IL. This is necessary because for example
1132 vect_get_slp_defs uses operand indexes and thus expects
1133 canonical operand order. */
1134 for (j
= 0; j
< group_size
; ++j
)
1137 gimple stmt
= SLP_TREE_SCALAR_STMTS (*node
)[j
];
1138 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
1139 gimple_assign_rhs2_ptr (stmt
));
1141 oprnd_info
->def_stmts
= vNULL
;
1142 SLP_TREE_CHILDREN (*node
).quick_push (child
);
1149 oprnd_info
->def_stmts
= vNULL
;
1150 vect_free_slp_tree (child
);
1151 vect_free_oprnd_info (oprnds_info
);
1156 *tree_size
+= this_tree_size
;
1158 vect_free_oprnd_info (oprnds_info
);
1162 /* Dump a slp tree NODE using flags specified in DUMP_KIND. */
1165 vect_print_slp_tree (int dump_kind
, slp_tree node
)
1174 dump_printf (dump_kind
, "node ");
1175 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1177 dump_printf (dump_kind
, "\n\tstmt %d ", i
);
1178 dump_gimple_stmt (dump_kind
, TDF_SLIM
, stmt
, 0);
1180 dump_printf (dump_kind
, "\n");
1182 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1183 vect_print_slp_tree (dump_kind
, child
);
1187 /* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
1188 If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
1189 J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
1190 stmts in NODE are to be marked. */
1193 vect_mark_slp_stmts (slp_tree node
, enum slp_vect_type mark
, int j
)
1202 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1203 if (j
< 0 || i
== j
)
1204 STMT_SLP_TYPE (vinfo_for_stmt (stmt
)) = mark
;
1206 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1207 vect_mark_slp_stmts (child
, mark
, j
);
1211 /* Mark the statements of the tree rooted at NODE as relevant (vect_used). */
1214 vect_mark_slp_stmts_relevant (slp_tree node
)
1218 stmt_vec_info stmt_info
;
1224 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1226 stmt_info
= vinfo_for_stmt (stmt
);
1227 gcc_assert (!STMT_VINFO_RELEVANT (stmt_info
)
1228 || STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
);
1229 STMT_VINFO_RELEVANT (stmt_info
) = vect_used_in_scope
;
1232 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1233 vect_mark_slp_stmts_relevant (child
);
1237 /* Rearrange the statements of NODE according to PERMUTATION. */
1240 vect_slp_rearrange_stmts (slp_tree node
, unsigned int group_size
,
1241 vec
<unsigned> permutation
)
1244 vec
<gimple
> tmp_stmts
;
1248 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1249 vect_slp_rearrange_stmts (child
, group_size
, permutation
);
1251 gcc_assert (group_size
== SLP_TREE_SCALAR_STMTS (node
).length ());
1252 tmp_stmts
.create (group_size
);
1253 tmp_stmts
.quick_grow_cleared (group_size
);
1255 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1256 tmp_stmts
[permutation
[i
]] = stmt
;
1258 SLP_TREE_SCALAR_STMTS (node
).release ();
1259 SLP_TREE_SCALAR_STMTS (node
) = tmp_stmts
;
1263 /* Attempt to reorder stmts in a reduction chain so that we don't
1264 require any load permutation. Return true if that was possible,
1265 otherwise return false. */
1268 vect_attempt_slp_rearrange_stmts (slp_instance slp_instn
)
1270 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1274 slp_tree node
, load
;
1276 /* Compare all the permutation sequences to the first one. We know
1277 that at least one load is permuted. */
1278 node
= SLP_INSTANCE_LOADS (slp_instn
)[0];
1279 if (!node
->load_permutation
.exists ())
1281 for (i
= 1; SLP_INSTANCE_LOADS (slp_instn
).iterate (i
, &load
); ++i
)
1283 if (!load
->load_permutation
.exists ())
1285 FOR_EACH_VEC_ELT (load
->load_permutation
, j
, lidx
)
1286 if (lidx
!= node
->load_permutation
[j
])
1290 /* Check that the loads in the first sequence are different and there
1291 are no gaps between them. */
1292 load_index
= sbitmap_alloc (group_size
);
1293 bitmap_clear (load_index
);
1294 FOR_EACH_VEC_ELT (node
->load_permutation
, i
, lidx
)
1296 if (bitmap_bit_p (load_index
, lidx
))
1298 sbitmap_free (load_index
);
1301 bitmap_set_bit (load_index
, lidx
);
1303 for (i
= 0; i
< group_size
; i
++)
1304 if (!bitmap_bit_p (load_index
, i
))
1306 sbitmap_free (load_index
);
1309 sbitmap_free (load_index
);
1311 /* This permutation is valid for reduction. Since the order of the
1312 statements in the nodes is not important unless they are memory
1313 accesses, we can rearrange the statements in all the nodes
1314 according to the order of the loads. */
1315 vect_slp_rearrange_stmts (SLP_INSTANCE_TREE (slp_instn
), group_size
,
1316 node
->load_permutation
);
1318 /* We are done, no actual permutations need to be generated. */
1319 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1320 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1324 /* Check if the required load permutations in the SLP instance
1325 SLP_INSTN are supported. */
1328 vect_supported_load_permutation_p (slp_instance slp_instn
)
1330 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1331 unsigned int i
, j
, k
, next
;
1333 gimple stmt
, load
, next_load
, first_load
;
1334 struct data_reference
*dr
;
1336 if (dump_enabled_p ())
1338 dump_printf_loc (MSG_NOTE
, vect_location
, "Load permutation ");
1339 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1340 if (node
->load_permutation
.exists ())
1341 FOR_EACH_VEC_ELT (node
->load_permutation
, j
, next
)
1342 dump_printf (MSG_NOTE
, "%d ", next
);
1344 for (k
= 0; k
< group_size
; ++k
)
1345 dump_printf (MSG_NOTE
, "%d ", k
);
1346 dump_printf (MSG_NOTE
, "\n");
1349 /* In case of reduction every load permutation is allowed, since the order
1350 of the reduction statements is not important (as opposed to the case of
1351 grouped stores). The only condition we need to check is that all the
1352 load nodes are of the same size and have the same permutation (and then
1353 rearrange all the nodes of the SLP instance according to this
1356 /* Check that all the load nodes are of the same size. */
1357 /* ??? Can't we assert this? */
1358 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1359 if (SLP_TREE_SCALAR_STMTS (node
).length () != (unsigned) group_size
)
1362 node
= SLP_INSTANCE_TREE (slp_instn
);
1363 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1365 /* Reduction (there are no data-refs in the root).
1366 In reduction chain the order of the loads is not important. */
1367 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))
1368 && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1370 if (vect_attempt_slp_rearrange_stmts (slp_instn
))
1373 /* Fallthru to general load permutation handling. */
1376 /* In basic block vectorization we allow any subchain of an interleaving
1378 FORNOW: not supported in loop SLP because of realignment compications. */
1379 if (STMT_VINFO_BB_VINFO (vinfo_for_stmt (stmt
)))
1381 /* Check whether the loads in an instance form a subchain and thus
1382 no permutation is necessary. */
1383 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1385 if (!SLP_TREE_LOAD_PERMUTATION (node
).exists ())
1387 bool subchain_p
= true;
1389 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), j
, load
)
1392 && (next_load
!= load
1393 || GROUP_GAP (vinfo_for_stmt (load
)) != 1))
1398 next_load
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (load
));
1401 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1404 /* Verify the permutation can be generated. */
1406 if (!vect_transform_slp_perm_load (node
, tem
, NULL
,
1407 1, slp_instn
, true))
1409 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
1411 "unsupported load permutation\n");
1417 /* Check that the alignment of the first load in every subchain, i.e.,
1418 the first statement in every load node, is supported.
1419 ??? This belongs in alignment checking. */
1420 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1422 first_load
= SLP_TREE_SCALAR_STMTS (node
)[0];
1423 if (first_load
!= GROUP_FIRST_ELEMENT (vinfo_for_stmt (first_load
)))
1425 dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (first_load
));
1426 if (vect_supportable_dr_alignment (dr
, false)
1427 == dr_unaligned_unsupported
)
1429 if (dump_enabled_p ())
1431 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
1433 "unsupported unaligned load ");
1434 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
1436 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1446 /* For loop vectorization verify we can generate the permutation. */
1447 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1448 if (node
->load_permutation
.exists ()
1449 && !vect_transform_slp_perm_load
1451 SLP_INSTANCE_UNROLLING_FACTOR (slp_instn
), slp_instn
, true))
1458 /* Find the last store in SLP INSTANCE. */
1461 vect_find_last_scalar_stmt_in_slp (slp_tree node
)
1463 gimple last
= NULL
, stmt
;
1465 for (int i
= 0; SLP_TREE_SCALAR_STMTS (node
).iterate (i
, &stmt
); i
++)
1467 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
1468 if (is_pattern_stmt_p (stmt_vinfo
))
1469 last
= get_later_stmt (STMT_VINFO_RELATED_STMT (stmt_vinfo
), last
);
1471 last
= get_later_stmt (stmt
, last
);
1477 /* Compute the cost for the SLP node NODE in the SLP instance INSTANCE. */
1480 vect_analyze_slp_cost_1 (slp_instance instance
, slp_tree node
,
1481 stmt_vector_for_cost
*prologue_cost_vec
,
1482 stmt_vector_for_cost
*body_cost_vec
,
1483 unsigned ncopies_for_cost
)
1488 stmt_vec_info stmt_info
;
1490 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1492 /* Recurse down the SLP tree. */
1493 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1495 vect_analyze_slp_cost_1 (instance
, child
, prologue_cost_vec
,
1496 body_cost_vec
, ncopies_for_cost
);
1498 /* Look at the first scalar stmt to determine the cost. */
1499 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1500 stmt_info
= vinfo_for_stmt (stmt
);
1501 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1503 if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info
)))
1504 vect_model_store_cost (stmt_info
, ncopies_for_cost
, false,
1505 vect_uninitialized_def
,
1506 node
, prologue_cost_vec
, body_cost_vec
);
1510 gcc_checking_assert (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)));
1511 vect_model_load_cost (stmt_info
, ncopies_for_cost
, false,
1512 node
, prologue_cost_vec
, body_cost_vec
);
1513 /* If the load is permuted record the cost for the permutation.
1514 ??? Loads from multiple chains are let through here only
1515 for a single special case involving complex numbers where
1516 in the end no permutation is necessary. */
1517 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, s
)
1518 if ((STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo_for_stmt (s
))
1519 == STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
))
1520 && vect_get_place_in_interleaving_chain
1521 (s
, STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
)) != i
)
1523 record_stmt_cost (body_cost_vec
, group_size
, vec_perm
,
1524 stmt_info
, 0, vect_body
);
1531 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1532 stmt_info
, 0, vect_body
);
1533 if (SLP_TREE_TWO_OPERATORS (node
))
1535 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1536 stmt_info
, 0, vect_body
);
1537 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vec_perm
,
1538 stmt_info
, 0, vect_body
);
1542 /* Scan operands and account for prologue cost of constants/externals.
1543 ??? This over-estimates cost for multiple uses and should be
1545 lhs
= gimple_get_lhs (stmt
);
1546 for (i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1548 tree def
, op
= gimple_op (stmt
, i
);
1550 enum vect_def_type dt
;
1551 if (!op
|| op
== lhs
)
1553 if (vect_is_simple_use (op
, NULL
, STMT_VINFO_LOOP_VINFO (stmt_info
),
1554 STMT_VINFO_BB_VINFO (stmt_info
),
1555 &def_stmt
, &def
, &dt
))
1557 /* Without looking at the actual initializer a vector of
1558 constants can be implemented as load from the constant pool.
1559 ??? We need to pass down stmt_info for a vector type
1560 even if it points to the wrong stmt. */
1561 if (dt
== vect_constant_def
)
1562 record_stmt_cost (prologue_cost_vec
, 1, vector_load
,
1563 stmt_info
, 0, vect_prologue
);
1564 else if (dt
== vect_external_def
)
1565 record_stmt_cost (prologue_cost_vec
, 1, vec_construct
,
1566 stmt_info
, 0, vect_prologue
);
1571 /* Compute the cost for the SLP instance INSTANCE. */
1574 vect_analyze_slp_cost (slp_instance instance
, void *data
)
1576 stmt_vector_for_cost body_cost_vec
, prologue_cost_vec
;
1577 unsigned ncopies_for_cost
;
1578 stmt_info_for_cost
*si
;
1581 /* Calculate the number of vector stmts to create based on the unrolling
1582 factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
1583 GROUP_SIZE / NUNITS otherwise. */
1584 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1585 slp_tree node
= SLP_INSTANCE_TREE (instance
);
1586 stmt_vec_info stmt_info
= vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node
)[0]);
1587 /* Adjust the group_size by the vectorization factor which is always one
1588 for basic-block vectorization. */
1589 if (STMT_VINFO_LOOP_VINFO (stmt_info
))
1590 group_size
*= LOOP_VINFO_VECT_FACTOR (STMT_VINFO_LOOP_VINFO (stmt_info
));
1591 unsigned nunits
= TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
1592 /* For reductions look at a reduction operand in case the reduction
1593 operation is widening like DOT_PROD or SAD. */
1594 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1596 gimple stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1597 switch (gimple_assign_rhs_code (stmt
))
1601 nunits
= TYPE_VECTOR_SUBPARTS (get_vectype_for_scalar_type
1602 (TREE_TYPE (gimple_assign_rhs1 (stmt
))));
1607 ncopies_for_cost
= least_common_multiple (nunits
, group_size
) / nunits
;
1609 prologue_cost_vec
.create (10);
1610 body_cost_vec
.create (10);
1611 vect_analyze_slp_cost_1 (instance
, SLP_INSTANCE_TREE (instance
),
1612 &prologue_cost_vec
, &body_cost_vec
,
1615 /* Record the prologue costs, which were delayed until we were
1616 sure that SLP was successful. */
1617 FOR_EACH_VEC_ELT (prologue_cost_vec
, i
, si
)
1619 struct _stmt_vec_info
*stmt_info
1620 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1621 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1622 si
->misalign
, vect_prologue
);
1625 /* Record the instance's instructions in the target cost model. */
1626 FOR_EACH_VEC_ELT (body_cost_vec
, i
, si
)
1628 struct _stmt_vec_info
*stmt_info
1629 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1630 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1631 si
->misalign
, vect_body
);
1634 prologue_cost_vec
.release ();
1635 body_cost_vec
.release ();
1638 /* Analyze an SLP instance starting from a group of grouped stores. Call
1639 vect_build_slp_tree to build a tree of packed stmts if possible.
1640 Return FALSE if it's impossible to SLP any stmt in the loop. */
1643 vect_analyze_slp_instance (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1644 gimple stmt
, unsigned max_tree_size
)
1646 slp_instance new_instance
;
1648 unsigned int group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1649 unsigned int unrolling_factor
= 1, nunits
;
1650 tree vectype
, scalar_type
= NULL_TREE
;
1652 unsigned int vectorization_factor
= 0;
1654 unsigned int max_nunits
= 0;
1655 vec
<slp_tree
> loads
;
1656 struct data_reference
*dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
));
1657 vec
<gimple
> scalar_stmts
;
1659 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1663 scalar_type
= TREE_TYPE (DR_REF (dr
));
1664 vectype
= get_vectype_for_scalar_type (scalar_type
);
1668 gcc_assert (loop_vinfo
);
1669 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1672 group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1676 gcc_assert (loop_vinfo
);
1677 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1678 group_size
= LOOP_VINFO_REDUCTIONS (loop_vinfo
).length ();
1683 if (dump_enabled_p ())
1685 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1686 "Build SLP failed: unsupported data-type ");
1687 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, scalar_type
);
1688 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1694 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
1696 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1698 vectorization_factor
= nunits
;
1700 /* Calculate the unrolling factor. */
1701 unrolling_factor
= least_common_multiple (nunits
, group_size
) / group_size
;
1702 if (unrolling_factor
!= 1 && !loop_vinfo
)
1704 if (dump_enabled_p ())
1705 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1706 "Build SLP failed: unrolling required in basic"
1712 /* Create a node (a root of the SLP tree) for the packed grouped stores. */
1713 scalar_stmts
.create (group_size
);
1715 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1717 /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
1720 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next
))
1721 && STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)))
1722 scalar_stmts
.safe_push (
1723 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)));
1725 scalar_stmts
.safe_push (next
);
1726 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
1728 /* Mark the first element of the reduction chain as reduction to properly
1729 transform the node. In the reduction analysis phase only the last
1730 element of the chain is marked as reduction. */
1731 if (!STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
1732 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_reduction_def
;
1736 /* Collect reduction statements. */
1737 vec
<gimple
> reductions
= LOOP_VINFO_REDUCTIONS (loop_vinfo
);
1738 for (i
= 0; reductions
.iterate (i
, &next
); i
++)
1739 scalar_stmts
.safe_push (next
);
1742 node
= vect_create_new_slp_node (scalar_stmts
);
1744 loads
.create (group_size
);
1746 /* Build the tree for the SLP instance. */
1747 bool *matches
= XALLOCAVEC (bool, group_size
);
1748 unsigned npermutes
= 0;
1749 if (vect_build_slp_tree (loop_vinfo
, bb_vinfo
, &node
, group_size
,
1750 &max_nunits
, &loads
,
1751 vectorization_factor
, matches
, &npermutes
, NULL
,
1754 /* Calculate the unrolling factor based on the smallest type. */
1755 if (max_nunits
> nunits
)
1756 unrolling_factor
= least_common_multiple (max_nunits
, group_size
)
1759 if (unrolling_factor
!= 1 && !loop_vinfo
)
1761 if (dump_enabled_p ())
1762 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1763 "Build SLP failed: unrolling required in basic"
1765 vect_free_slp_tree (node
);
1770 /* Create a new SLP instance. */
1771 new_instance
= XNEW (struct _slp_instance
);
1772 SLP_INSTANCE_TREE (new_instance
) = node
;
1773 SLP_INSTANCE_GROUP_SIZE (new_instance
) = group_size
;
1774 SLP_INSTANCE_UNROLLING_FACTOR (new_instance
) = unrolling_factor
;
1775 SLP_INSTANCE_LOADS (new_instance
) = loads
;
1777 /* Compute the load permutation. */
1779 bool loads_permuted
= false;
1780 FOR_EACH_VEC_ELT (loads
, i
, load_node
)
1782 vec
<unsigned> load_permutation
;
1784 gimple load
, first_stmt
;
1785 bool this_load_permuted
= false;
1786 load_permutation
.create (group_size
);
1787 first_stmt
= GROUP_FIRST_ELEMENT
1788 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node
)[0]));
1789 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node
), j
, load
)
1792 = vect_get_place_in_interleaving_chain (load
, first_stmt
);
1793 gcc_assert (load_place
!= -1);
1794 if (load_place
!= j
)
1795 this_load_permuted
= true;
1796 load_permutation
.safe_push (load_place
);
1798 if (!this_load_permuted
1799 /* The load requires permutation when unrolling exposes
1800 a gap either because the group is larger than the SLP
1801 group-size or because there is a gap between the groups. */
1802 && (unrolling_factor
== 1
1803 || (group_size
== GROUP_SIZE (vinfo_for_stmt (first_stmt
))
1804 && GROUP_GAP (vinfo_for_stmt (first_stmt
)) == 0)))
1806 load_permutation
.release ();
1809 SLP_TREE_LOAD_PERMUTATION (load_node
) = load_permutation
;
1810 loads_permuted
= true;
1815 if (!vect_supported_load_permutation_p (new_instance
))
1817 if (dump_enabled_p ())
1819 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1820 "Build SLP failed: unsupported load "
1822 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
1823 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1825 vect_free_slp_instance (new_instance
);
1832 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).safe_push (new_instance
);
1834 BB_VINFO_SLP_INSTANCES (bb_vinfo
).safe_push (new_instance
);
1836 if (dump_enabled_p ())
1837 vect_print_slp_tree (MSG_NOTE
, node
);
1842 /* Failed to SLP. */
1843 /* Free the allocated memory. */
1844 vect_free_slp_tree (node
);
1851 /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
1852 trees of packed scalar stmts if SLP is possible. */
1855 vect_analyze_slp (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1856 unsigned max_tree_size
)
1859 vec
<gimple
> grouped_stores
;
1860 vec
<gimple
> reductions
= vNULL
;
1861 vec
<gimple
> reduc_chains
= vNULL
;
1862 gimple first_element
;
1865 if (dump_enabled_p ())
1866 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_analyze_slp ===\n");
1870 grouped_stores
= LOOP_VINFO_GROUPED_STORES (loop_vinfo
);
1871 reduc_chains
= LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
);
1872 reductions
= LOOP_VINFO_REDUCTIONS (loop_vinfo
);
1875 grouped_stores
= BB_VINFO_GROUPED_STORES (bb_vinfo
);
1877 /* Find SLP sequences starting from groups of grouped stores. */
1878 FOR_EACH_VEC_ELT (grouped_stores
, i
, first_element
)
1879 if (vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, first_element
,
1883 if (reduc_chains
.length () > 0)
1885 /* Find SLP sequences starting from reduction chains. */
1886 FOR_EACH_VEC_ELT (reduc_chains
, i
, first_element
)
1887 if (vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, first_element
,
1893 /* Don't try to vectorize SLP reductions if reduction chain was
1898 /* Find SLP sequences starting from groups of reductions. */
1899 if (reductions
.length () > 1
1900 && vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, reductions
[0],
1908 /* For each possible SLP instance decide whether to SLP it and calculate overall
1909 unrolling factor needed to SLP the loop. Return TRUE if decided to SLP at
1910 least one instance. */
1913 vect_make_slp_decision (loop_vec_info loop_vinfo
)
1915 unsigned int i
, unrolling_factor
= 1;
1916 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
1917 slp_instance instance
;
1918 int decided_to_slp
= 0;
1920 if (dump_enabled_p ())
1921 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_make_slp_decision ==="
1924 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
1926 /* FORNOW: SLP if you can. */
1927 if (unrolling_factor
< SLP_INSTANCE_UNROLLING_FACTOR (instance
))
1928 unrolling_factor
= SLP_INSTANCE_UNROLLING_FACTOR (instance
);
1930 /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
1931 call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
1932 loop-based vectorization. Such stmts will be marked as HYBRID. */
1933 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
1937 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
) = unrolling_factor
;
1939 if (decided_to_slp
&& dump_enabled_p ())
1940 dump_printf_loc (MSG_NOTE
, vect_location
,
1941 "Decided to SLP %d instances. Unrolling factor %d\n",
1942 decided_to_slp
, unrolling_factor
);
1944 return (decided_to_slp
> 0);
1948 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
1949 can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
1952 vect_detect_hybrid_slp_stmts (slp_tree node
, unsigned i
, slp_vect_type stype
)
1954 gimple stmt
= SLP_TREE_SCALAR_STMTS (node
)[i
];
1955 imm_use_iterator imm_iter
;
1957 stmt_vec_info use_vinfo
, stmt_vinfo
= vinfo_for_stmt (stmt
);
1959 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
1960 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1963 /* Propagate hybrid down the SLP tree. */
1964 if (stype
== hybrid
)
1966 else if (HYBRID_SLP_STMT (stmt_vinfo
))
1970 /* Check if a pure SLP stmt has uses in non-SLP stmts. */
1971 gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo
));
1972 /* We always get the pattern stmt here, but for immediate
1973 uses we have to use the LHS of the original stmt. */
1974 gcc_checking_assert (!STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
1975 if (STMT_VINFO_RELATED_STMT (stmt_vinfo
))
1976 stmt
= STMT_VINFO_RELATED_STMT (stmt_vinfo
);
1977 if (TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
1978 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, gimple_op (stmt
, 0))
1980 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
1982 use_vinfo
= vinfo_for_stmt (use_stmt
);
1983 if (STMT_VINFO_IN_PATTERN_P (use_vinfo
)
1984 && STMT_VINFO_RELATED_STMT (use_vinfo
))
1985 use_vinfo
= vinfo_for_stmt (STMT_VINFO_RELATED_STMT (use_vinfo
));
1986 if (!STMT_SLP_TYPE (use_vinfo
)
1987 && (STMT_VINFO_RELEVANT (use_vinfo
)
1988 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo
)))
1989 && !(gimple_code (use_stmt
) == GIMPLE_PHI
1990 && STMT_VINFO_DEF_TYPE (use_vinfo
) == vect_reduction_def
))
1992 if (dump_enabled_p ())
1994 dump_printf_loc (MSG_NOTE
, vect_location
, "use of SLP "
1995 "def in non-SLP stmt: ");
1996 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, use_stmt
, 0);
2004 && !HYBRID_SLP_STMT (stmt_vinfo
))
2006 if (dump_enabled_p ())
2008 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2009 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
2011 STMT_SLP_TYPE (stmt_vinfo
) = hybrid
;
2014 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2016 vect_detect_hybrid_slp_stmts (child
, i
, stype
);
2019 /* Helpers for vect_detect_hybrid_slp walking pattern stmt uses. */
2022 vect_detect_hybrid_slp_1 (tree
*tp
, int *, void *data
)
2024 walk_stmt_info
*wi
= (walk_stmt_info
*)data
;
2025 struct loop
*loopp
= (struct loop
*)wi
->info
;
2030 if (TREE_CODE (*tp
) == SSA_NAME
2031 && !SSA_NAME_IS_DEFAULT_DEF (*tp
))
2033 gimple def_stmt
= SSA_NAME_DEF_STMT (*tp
);
2034 if (flow_bb_inside_loop_p (loopp
, gimple_bb (def_stmt
))
2035 && PURE_SLP_STMT (vinfo_for_stmt (def_stmt
)))
2037 if (dump_enabled_p ())
2039 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2040 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2042 STMT_SLP_TYPE (vinfo_for_stmt (def_stmt
)) = hybrid
;
2050 vect_detect_hybrid_slp_2 (gimple_stmt_iterator
*gsi
, bool *handled
,
2053 /* If the stmt is in a SLP instance then this isn't a reason
2054 to mark use definitions in other SLP instances as hybrid. */
2055 if (STMT_SLP_TYPE (vinfo_for_stmt (gsi_stmt (*gsi
))) != loop_vect
)
2060 /* Find stmts that must be both vectorized and SLPed. */
2063 vect_detect_hybrid_slp (loop_vec_info loop_vinfo
)
2066 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2067 slp_instance instance
;
2069 if (dump_enabled_p ())
2070 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_detect_hybrid_slp ==="
2073 /* First walk all pattern stmt in the loop and mark defs of uses as
2074 hybrid because immediate uses in them are not recorded. */
2075 for (i
= 0; i
< LOOP_VINFO_LOOP (loop_vinfo
)->num_nodes
; ++i
)
2077 basic_block bb
= LOOP_VINFO_BBS (loop_vinfo
)[i
];
2078 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2081 gimple stmt
= gsi_stmt (gsi
);
2082 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2083 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
2086 memset (&wi
, 0, sizeof (wi
));
2087 wi
.info
= LOOP_VINFO_LOOP (loop_vinfo
);
2088 gimple_stmt_iterator gsi2
2089 = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info
));
2090 walk_gimple_stmt (&gsi2
, vect_detect_hybrid_slp_2
,
2091 vect_detect_hybrid_slp_1
, &wi
);
2092 walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
),
2093 vect_detect_hybrid_slp_2
,
2094 vect_detect_hybrid_slp_1
, &wi
);
2099 /* Then walk the SLP instance trees marking stmts with uses in
2100 non-SLP stmts as hybrid, also propagating hybrid down the
2101 SLP tree, collecting the above info on-the-fly. */
2102 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2104 for (unsigned i
= 0; i
< SLP_INSTANCE_GROUP_SIZE (instance
); ++i
)
2105 vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance
),
2111 /* Create and initialize a new bb_vec_info struct for BB, as well as
2112 stmt_vec_info structs for all the stmts in it. */
2115 new_bb_vec_info (basic_block bb
)
2117 bb_vec_info res
= NULL
;
2118 gimple_stmt_iterator gsi
;
2120 res
= (bb_vec_info
) xcalloc (1, sizeof (struct _bb_vec_info
));
2121 BB_VINFO_BB (res
) = bb
;
2123 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2125 gimple stmt
= gsi_stmt (gsi
);
2126 gimple_set_uid (stmt
, 0);
2127 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, NULL
, res
));
2130 BB_VINFO_GROUPED_STORES (res
).create (10);
2131 BB_VINFO_SLP_INSTANCES (res
).create (2);
2132 BB_VINFO_TARGET_COST_DATA (res
) = init_cost (NULL
);
2139 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
2140 stmts in the basic block. */
2143 destroy_bb_vec_info (bb_vec_info bb_vinfo
)
2145 vec
<slp_instance
> slp_instances
;
2146 slp_instance instance
;
2148 gimple_stmt_iterator si
;
2154 bb
= BB_VINFO_BB (bb_vinfo
);
2156 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2158 gimple stmt
= gsi_stmt (si
);
2159 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2162 /* Free stmt_vec_info. */
2163 free_stmt_vec_info (stmt
);
2166 vect_destroy_datarefs (NULL
, bb_vinfo
);
2167 free_dependence_relations (BB_VINFO_DDRS (bb_vinfo
));
2168 BB_VINFO_GROUPED_STORES (bb_vinfo
).release ();
2169 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2170 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2171 vect_free_slp_instance (instance
);
2172 BB_VINFO_SLP_INSTANCES (bb_vinfo
).release ();
2173 destroy_cost_data (BB_VINFO_TARGET_COST_DATA (bb_vinfo
));
2179 /* Analyze statements contained in SLP tree node after recursively analyzing
2180 the subtree. Return TRUE if the operations are supported. */
2183 vect_slp_analyze_node_operations (slp_tree node
)
2193 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2194 if (!vect_slp_analyze_node_operations (child
))
2197 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2199 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2200 gcc_assert (stmt_info
);
2201 gcc_assert (STMT_SLP_TYPE (stmt_info
) != loop_vect
);
2203 if (!vect_analyze_stmt (stmt
, &dummy
, node
))
2211 /* Analyze statements in SLP instances of the basic block. Return TRUE if the
2212 operations are supported. */
2215 vect_slp_analyze_operations (vec
<slp_instance
> slp_instances
, void *data
)
2217 slp_instance instance
;
2220 if (dump_enabled_p ())
2221 dump_printf_loc (MSG_NOTE
, vect_location
,
2222 "=== vect_slp_analyze_operations ===\n");
2224 for (i
= 0; slp_instances
.iterate (i
, &instance
); )
2226 if (!vect_slp_analyze_node_operations (SLP_INSTANCE_TREE (instance
)))
2228 dump_printf_loc (MSG_NOTE
, vect_location
,
2229 "removing SLP instance operations starting from: ");
2230 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
2231 SLP_TREE_SCALAR_STMTS
2232 (SLP_INSTANCE_TREE (instance
))[0], 0);
2233 vect_free_slp_instance (instance
);
2234 slp_instances
.ordered_remove (i
);
2238 /* Compute the costs of the SLP instance. */
2239 vect_analyze_slp_cost (instance
, data
);
2244 if (!slp_instances
.length ())
2251 /* Compute the scalar cost of the SLP node NODE and its children
2252 and return it. Do not account defs that are marked in LIFE and
2253 update LIFE according to uses of NODE. */
2256 vect_bb_slp_scalar_cost (basic_block bb
,
2257 slp_tree node
, vec
<bool, va_heap
> *life
)
2259 unsigned scalar_cost
= 0;
2264 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2267 ssa_op_iter op_iter
;
2268 def_operand_p def_p
;
2269 stmt_vec_info stmt_info
;
2274 /* If there is a non-vectorized use of the defs then the scalar
2275 stmt is kept live in which case we do not account it or any
2276 required defs in the SLP children in the scalar cost. This
2277 way we make the vectorization more costly when compared to
2279 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
2281 imm_use_iterator use_iter
;
2283 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, DEF_FROM_PTR (def_p
))
2284 if (!is_gimple_debug (use_stmt
)
2285 && (gimple_code (use_stmt
) == GIMPLE_PHI
2286 || gimple_bb (use_stmt
) != bb
2287 || !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (use_stmt
))))
2290 BREAK_FROM_IMM_USE_STMT (use_iter
);
2296 stmt_info
= vinfo_for_stmt (stmt
);
2297 if (STMT_VINFO_DATA_REF (stmt_info
))
2299 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)))
2300 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2302 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2305 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2307 scalar_cost
+= stmt_cost
;
2310 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2312 scalar_cost
+= vect_bb_slp_scalar_cost (bb
, child
, life
);
2317 /* Check if vectorization of the basic block is profitable. */
2320 vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo
)
2322 vec
<slp_instance
> slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2323 slp_instance instance
;
2325 unsigned int vec_inside_cost
= 0, vec_outside_cost
= 0, scalar_cost
= 0;
2326 unsigned int vec_prologue_cost
= 0, vec_epilogue_cost
= 0;
2328 /* Calculate scalar cost. */
2329 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2331 auto_vec
<bool, 20> life
;
2332 life
.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance
));
2333 scalar_cost
+= vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo
),
2334 SLP_INSTANCE_TREE (instance
),
2338 /* Complete the target-specific cost calculation. */
2339 finish_cost (BB_VINFO_TARGET_COST_DATA (bb_vinfo
), &vec_prologue_cost
,
2340 &vec_inside_cost
, &vec_epilogue_cost
);
2342 vec_outside_cost
= vec_prologue_cost
+ vec_epilogue_cost
;
2344 if (dump_enabled_p ())
2346 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2347 dump_printf (MSG_NOTE
, " Vector inside of basic block cost: %d\n",
2349 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n", vec_prologue_cost
);
2350 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n", vec_epilogue_cost
);
2351 dump_printf (MSG_NOTE
, " Scalar cost of basic block: %d\n", scalar_cost
);
2354 /* Vectorization is profitable if its cost is less than the cost of scalar
2356 if (vec_outside_cost
+ vec_inside_cost
>= scalar_cost
)
2362 /* Check if the basic block can be vectorized. */
2365 vect_slp_analyze_bb_1 (basic_block bb
)
2367 bb_vec_info bb_vinfo
;
2368 vec
<slp_instance
> slp_instances
;
2369 slp_instance instance
;
2372 unsigned n_stmts
= 0;
2374 bb_vinfo
= new_bb_vec_info (bb
);
2378 if (!vect_analyze_data_refs (NULL
, bb_vinfo
, &min_vf
, &n_stmts
))
2380 if (dump_enabled_p ())
2381 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2382 "not vectorized: unhandled data-ref in basic "
2385 destroy_bb_vec_info (bb_vinfo
);
2389 if (BB_VINFO_DATAREFS (bb_vinfo
).length () < 2)
2391 if (dump_enabled_p ())
2392 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2393 "not vectorized: not enough data-refs in "
2396 destroy_bb_vec_info (bb_vinfo
);
2400 if (!vect_analyze_data_ref_accesses (NULL
, bb_vinfo
))
2402 if (dump_enabled_p ())
2403 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2404 "not vectorized: unhandled data access in "
2407 destroy_bb_vec_info (bb_vinfo
);
2411 vect_pattern_recog (NULL
, bb_vinfo
);
2413 if (!vect_analyze_data_refs_alignment (NULL
, bb_vinfo
))
2415 if (dump_enabled_p ())
2416 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2417 "not vectorized: bad data alignment in basic "
2420 destroy_bb_vec_info (bb_vinfo
);
2424 /* Check the SLP opportunities in the basic block, analyze and build SLP
2426 if (!vect_analyze_slp (NULL
, bb_vinfo
, n_stmts
))
2428 if (dump_enabled_p ())
2430 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2431 "Failed to SLP the basic block.\n");
2432 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2433 "not vectorized: failed to find SLP opportunities "
2434 "in basic block.\n");
2437 destroy_bb_vec_info (bb_vinfo
);
2441 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2443 /* Mark all the statements that we want to vectorize as pure SLP and
2445 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2447 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2448 vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance
));
2451 /* Mark all the statements that we do not want to vectorize. */
2452 for (gimple_stmt_iterator gsi
= gsi_start_bb (BB_VINFO_BB (bb_vinfo
));
2453 !gsi_end_p (gsi
); gsi_next (&gsi
))
2455 stmt_vec_info vinfo
= vinfo_for_stmt (gsi_stmt (gsi
));
2456 if (STMT_SLP_TYPE (vinfo
) != pure_slp
)
2457 STMT_VINFO_VECTORIZABLE (vinfo
) = false;
2460 /* Analyze dependences. At this point all stmts not participating in
2461 vectorization have to be marked. Dependence analysis assumes
2462 that we either vectorize all SLP instances or none at all. */
2463 if (!vect_slp_analyze_data_ref_dependences (bb_vinfo
))
2465 if (dump_enabled_p ())
2466 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2467 "not vectorized: unhandled data dependence "
2468 "in basic block.\n");
2470 destroy_bb_vec_info (bb_vinfo
);
2474 if (!vect_verify_datarefs_alignment (NULL
, bb_vinfo
))
2476 if (dump_enabled_p ())
2477 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2478 "not vectorized: unsupported alignment in basic "
2480 destroy_bb_vec_info (bb_vinfo
);
2484 if (!vect_slp_analyze_operations (BB_VINFO_SLP_INSTANCES (bb_vinfo
),
2485 BB_VINFO_TARGET_COST_DATA (bb_vinfo
)))
2487 if (dump_enabled_p ())
2488 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2489 "not vectorized: bad operation in basic block.\n");
2491 destroy_bb_vec_info (bb_vinfo
);
2495 /* Cost model: check if the vectorization is worthwhile. */
2496 if (!unlimited_cost_model (NULL
)
2497 && !vect_bb_vectorization_profitable_p (bb_vinfo
))
2499 if (dump_enabled_p ())
2500 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2501 "not vectorized: vectorization is not "
2504 destroy_bb_vec_info (bb_vinfo
);
2508 if (dump_enabled_p ())
2509 dump_printf_loc (MSG_NOTE
, vect_location
,
2510 "Basic block will be vectorized using SLP\n");
2517 vect_slp_analyze_bb (basic_block bb
)
2519 bb_vec_info bb_vinfo
;
2521 gimple_stmt_iterator gsi
;
2522 unsigned int vector_sizes
;
2524 if (dump_enabled_p ())
2525 dump_printf_loc (MSG_NOTE
, vect_location
, "===vect_slp_analyze_bb===\n");
2527 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2529 gimple stmt
= gsi_stmt (gsi
);
2530 if (!is_gimple_debug (stmt
)
2531 && !gimple_nop_p (stmt
)
2532 && gimple_code (stmt
) != GIMPLE_LABEL
)
2536 if (insns
> PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB
))
2538 if (dump_enabled_p ())
2539 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2540 "not vectorized: too many instructions in "
2546 /* Autodetect first vector size we try. */
2547 current_vector_size
= 0;
2548 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2552 bb_vinfo
= vect_slp_analyze_bb_1 (bb
);
2556 destroy_bb_vec_info (bb_vinfo
);
2558 vector_sizes
&= ~current_vector_size
;
2559 if (vector_sizes
== 0
2560 || current_vector_size
== 0)
2563 /* Try the next biggest vector size. */
2564 current_vector_size
= 1 << floor_log2 (vector_sizes
);
2565 if (dump_enabled_p ())
2566 dump_printf_loc (MSG_NOTE
, vect_location
,
2567 "***** Re-trying analysis with "
2568 "vector size %d\n", current_vector_size
);
2573 /* For constant and loop invariant defs of SLP_NODE this function returns
2574 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
2575 OP_NUM determines if we gather defs for operand 0 or operand 1 of the RHS of
2576 scalar stmts. NUMBER_OF_VECTORS is the number of vector defs to create.
2577 REDUC_INDEX is the index of the reduction operand in the statements, unless
2581 vect_get_constant_vectors (tree op
, slp_tree slp_node
,
2582 vec
<tree
> *vec_oprnds
,
2583 unsigned int op_num
, unsigned int number_of_vectors
,
2586 vec
<gimple
> stmts
= SLP_TREE_SCALAR_STMTS (slp_node
);
2587 gimple stmt
= stmts
[0];
2588 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2592 unsigned j
, number_of_places_left_in_vector
;
2595 int group_size
= stmts
.length ();
2596 unsigned int vec_num
, i
;
2597 unsigned number_of_copies
= 1;
2599 voprnds
.create (number_of_vectors
);
2600 bool constant_p
, is_store
;
2601 tree neutral_op
= NULL
;
2602 enum tree_code code
= gimple_expr_code (stmt
);
2605 gimple_seq ctor_seq
= NULL
;
2607 vector_type
= get_vectype_for_scalar_type (TREE_TYPE (op
));
2608 nunits
= TYPE_VECTOR_SUBPARTS (vector_type
);
2610 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_reduction_def
2611 && reduc_index
!= -1)
2613 op_num
= reduc_index
;
2614 op
= gimple_op (stmt
, op_num
+ 1);
2615 /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
2616 we need either neutral operands or the original operands. See
2617 get_initial_def_for_reduction() for details. */
2620 case WIDEN_SUM_EXPR
:
2627 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2628 neutral_op
= build_real (TREE_TYPE (op
), dconst0
);
2630 neutral_op
= build_int_cst (TREE_TYPE (op
), 0);
2635 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2636 neutral_op
= build_real (TREE_TYPE (op
), dconst1
);
2638 neutral_op
= build_int_cst (TREE_TYPE (op
), 1);
2643 neutral_op
= build_int_cst (TREE_TYPE (op
), -1);
2646 /* For MIN/MAX we don't have an easy neutral operand but
2647 the initial values can be used fine here. Only for
2648 a reduction chain we have to force a neutral element. */
2651 if (!GROUP_FIRST_ELEMENT (stmt_vinfo
))
2655 def_stmt
= SSA_NAME_DEF_STMT (op
);
2656 loop
= (gimple_bb (stmt
))->loop_father
;
2657 neutral_op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2658 loop_preheader_edge (loop
));
2663 gcc_assert (!GROUP_FIRST_ELEMENT (stmt_vinfo
));
2668 if (STMT_VINFO_DATA_REF (stmt_vinfo
))
2671 op
= gimple_assign_rhs1 (stmt
);
2678 if (CONSTANT_CLASS_P (op
))
2683 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
2684 created vectors. It is greater than 1 if unrolling is performed.
2686 For example, we have two scalar operands, s1 and s2 (e.g., group of
2687 strided accesses of size two), while NUNITS is four (i.e., four scalars
2688 of this type can be packed in a vector). The output vector will contain
2689 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
2692 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
2693 containing the operands.
2695 For example, NUNITS is four as before, and the group size is 8
2696 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
2697 {s5, s6, s7, s8}. */
2699 number_of_copies
= nunits
* number_of_vectors
/ group_size
;
2701 number_of_places_left_in_vector
= nunits
;
2702 elts
= XALLOCAVEC (tree
, nunits
);
2703 bool place_after_defs
= false;
2704 for (j
= 0; j
< number_of_copies
; j
++)
2706 for (i
= group_size
- 1; stmts
.iterate (i
, &stmt
); i
--)
2709 op
= gimple_assign_rhs1 (stmt
);
2715 if (op_num
== 0 || op_num
== 1)
2717 tree cond
= gimple_assign_rhs1 (stmt
);
2718 op
= TREE_OPERAND (cond
, op_num
);
2723 op
= gimple_assign_rhs2 (stmt
);
2725 op
= gimple_assign_rhs3 (stmt
);
2730 op
= gimple_call_arg (stmt
, op_num
);
2737 op
= gimple_op (stmt
, op_num
+ 1);
2738 /* Unlike the other binary operators, shifts/rotates have
2739 the shift count being int, instead of the same type as
2740 the lhs, so make sure the scalar is the right type if
2741 we are dealing with vectors of
2742 long long/long/short/char. */
2743 if (op_num
== 1 && TREE_CODE (op
) == INTEGER_CST
)
2744 op
= fold_convert (TREE_TYPE (vector_type
), op
);
2748 op
= gimple_op (stmt
, op_num
+ 1);
2753 if (reduc_index
!= -1)
2755 loop
= (gimple_bb (stmt
))->loop_father
;
2756 def_stmt
= SSA_NAME_DEF_STMT (op
);
2760 /* Get the def before the loop. In reduction chain we have only
2761 one initial value. */
2762 if ((j
!= (number_of_copies
- 1)
2763 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
2768 op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2769 loop_preheader_edge (loop
));
2772 /* Create 'vect_ = {op0,op1,...,opn}'. */
2773 number_of_places_left_in_vector
--;
2775 if (!types_compatible_p (TREE_TYPE (vector_type
), TREE_TYPE (op
)))
2777 if (CONSTANT_CLASS_P (op
))
2779 op
= fold_unary (VIEW_CONVERT_EXPR
,
2780 TREE_TYPE (vector_type
), op
);
2781 gcc_assert (op
&& CONSTANT_CLASS_P (op
));
2785 tree new_temp
= make_ssa_name (TREE_TYPE (vector_type
));
2787 op
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (vector_type
), op
);
2789 = gimple_build_assign (new_temp
, VIEW_CONVERT_EXPR
, op
);
2790 gimple_seq_add_stmt (&ctor_seq
, init_stmt
);
2794 elts
[number_of_places_left_in_vector
] = op
;
2795 if (!CONSTANT_CLASS_P (op
))
2797 if (TREE_CODE (orig_op
) == SSA_NAME
2798 && !SSA_NAME_IS_DEFAULT_DEF (orig_op
)
2799 && STMT_VINFO_BB_VINFO (stmt_vinfo
)
2800 && (STMT_VINFO_BB_VINFO (stmt_vinfo
)->bb
2801 == gimple_bb (SSA_NAME_DEF_STMT (orig_op
))))
2802 place_after_defs
= true;
2804 if (number_of_places_left_in_vector
== 0)
2806 number_of_places_left_in_vector
= nunits
;
2809 vec_cst
= build_vector (vector_type
, elts
);
2812 vec
<constructor_elt
, va_gc
> *v
;
2814 vec_alloc (v
, nunits
);
2815 for (k
= 0; k
< nunits
; ++k
)
2816 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[k
]);
2817 vec_cst
= build_constructor (vector_type
, v
);
2820 gimple_stmt_iterator gsi
;
2821 if (place_after_defs
)
2824 (vect_find_last_scalar_stmt_in_slp (slp_node
));
2825 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, &gsi
);
2828 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, NULL
);
2829 if (ctor_seq
!= NULL
)
2831 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (init
));
2832 gsi_insert_seq_before_without_update (&gsi
, ctor_seq
,
2836 voprnds
.quick_push (init
);
2837 place_after_defs
= false;
2842 /* Since the vectors are created in the reverse order, we should invert
2844 vec_num
= voprnds
.length ();
2845 for (j
= vec_num
; j
!= 0; j
--)
2847 vop
= voprnds
[j
- 1];
2848 vec_oprnds
->quick_push (vop
);
2853 /* In case that VF is greater than the unrolling factor needed for the SLP
2854 group of stmts, NUMBER_OF_VECTORS to be created is greater than
2855 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
2856 to replicate the vectors. */
2857 while (number_of_vectors
> vec_oprnds
->length ())
2859 tree neutral_vec
= NULL
;
2864 neutral_vec
= build_vector_from_val (vector_type
, neutral_op
);
2866 vec_oprnds
->quick_push (neutral_vec
);
2870 for (i
= 0; vec_oprnds
->iterate (i
, &vop
) && i
< vec_num
; i
++)
2871 vec_oprnds
->quick_push (vop
);
2877 /* Get vectorized definitions from SLP_NODE that contains corresponding
2878 vectorized def-stmts. */
2881 vect_get_slp_vect_defs (slp_tree slp_node
, vec
<tree
> *vec_oprnds
)
2884 gimple vec_def_stmt
;
2887 gcc_assert (SLP_TREE_VEC_STMTS (slp_node
).exists ());
2889 FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (slp_node
), i
, vec_def_stmt
)
2891 gcc_assert (vec_def_stmt
);
2892 vec_oprnd
= gimple_get_lhs (vec_def_stmt
);
2893 vec_oprnds
->quick_push (vec_oprnd
);
2898 /* Get vectorized definitions for SLP_NODE.
2899 If the scalar definitions are loop invariants or constants, collect them and
2900 call vect_get_constant_vectors() to create vector stmts.
2901 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
2902 must be stored in the corresponding child of SLP_NODE, and we call
2903 vect_get_slp_vect_defs () to retrieve them. */
2906 vect_get_slp_defs (vec
<tree
> ops
, slp_tree slp_node
,
2907 vec
<vec
<tree
> > *vec_oprnds
, int reduc_index
)
2910 int number_of_vects
= 0, i
;
2911 unsigned int child_index
= 0;
2912 HOST_WIDE_INT lhs_size_unit
, rhs_size_unit
;
2913 slp_tree child
= NULL
;
2916 bool vectorized_defs
;
2918 first_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[0];
2919 FOR_EACH_VEC_ELT (ops
, i
, oprnd
)
2921 /* For each operand we check if it has vectorized definitions in a child
2922 node or we need to create them (for invariants and constants). We
2923 check if the LHS of the first stmt of the next child matches OPRND.
2924 If it does, we found the correct child. Otherwise, we call
2925 vect_get_constant_vectors (), and not advance CHILD_INDEX in order
2926 to check this child node for the next operand. */
2927 vectorized_defs
= false;
2928 if (SLP_TREE_CHILDREN (slp_node
).length () > child_index
)
2930 child
= SLP_TREE_CHILDREN (slp_node
)[child_index
];
2932 /* We have to check both pattern and original def, if available. */
2935 gimple first_def
= SLP_TREE_SCALAR_STMTS (child
)[0];
2937 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def
));
2939 if (operand_equal_p (oprnd
, gimple_get_lhs (first_def
), 0)
2941 && operand_equal_p (oprnd
, gimple_get_lhs (related
), 0)))
2943 /* The number of vector defs is determined by the number of
2944 vector statements in the node from which we get those
2946 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (child
);
2947 vectorized_defs
= true;
2955 if (!vectorized_defs
)
2959 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
2960 /* Number of vector stmts was calculated according to LHS in
2961 vect_schedule_slp_instance (), fix it by replacing LHS with
2962 RHS, if necessary. See vect_get_smallest_scalar_type () for
2964 vect_get_smallest_scalar_type (first_stmt
, &lhs_size_unit
,
2966 if (rhs_size_unit
!= lhs_size_unit
)
2968 number_of_vects
*= rhs_size_unit
;
2969 number_of_vects
/= lhs_size_unit
;
2974 /* Allocate memory for vectorized defs. */
2976 vec_defs
.create (number_of_vects
);
2978 /* For reduction defs we call vect_get_constant_vectors (), since we are
2979 looking for initial loop invariant values. */
2980 if (vectorized_defs
&& reduc_index
== -1)
2981 /* The defs are already vectorized. */
2982 vect_get_slp_vect_defs (child
, &vec_defs
);
2984 /* Build vectors from scalar defs. */
2985 vect_get_constant_vectors (oprnd
, slp_node
, &vec_defs
, i
,
2986 number_of_vects
, reduc_index
);
2988 vec_oprnds
->quick_push (vec_defs
);
2990 /* For reductions, we only need initial values. */
2991 if (reduc_index
!= -1)
2997 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
2998 building a vector of type MASK_TYPE from it) and two input vectors placed in
2999 DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
3000 shifting by STRIDE elements of DR_CHAIN for every copy.
3001 (STRIDE is the number of vectorized stmts for NODE divided by the number of
3003 VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
3004 the created stmts must be inserted. */
3007 vect_create_mask_and_perm (gimple stmt
,
3008 tree mask
, int first_vec_indx
, int second_vec_indx
,
3009 gimple_stmt_iterator
*gsi
, slp_tree node
,
3010 tree vectype
, vec
<tree
> dr_chain
,
3011 int ncopies
, int vect_stmts_counter
)
3014 gimple perm_stmt
= NULL
;
3016 tree first_vec
, second_vec
, data_ref
;
3018 stride
= SLP_TREE_NUMBER_OF_VEC_STMTS (node
) / ncopies
;
3020 /* Initialize the vect stmts of NODE to properly insert the generated
3022 for (i
= SLP_TREE_VEC_STMTS (node
).length ();
3023 i
< (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node
); i
++)
3024 SLP_TREE_VEC_STMTS (node
).quick_push (NULL
);
3026 perm_dest
= vect_create_destination_var (gimple_assign_lhs (stmt
), vectype
);
3027 for (i
= 0; i
< ncopies
; i
++)
3029 first_vec
= dr_chain
[first_vec_indx
];
3030 second_vec
= dr_chain
[second_vec_indx
];
3032 /* Generate the permute statement. */
3033 perm_stmt
= gimple_build_assign (perm_dest
, VEC_PERM_EXPR
,
3034 first_vec
, second_vec
, mask
);
3035 data_ref
= make_ssa_name (perm_dest
, perm_stmt
);
3036 gimple_set_lhs (perm_stmt
, data_ref
);
3037 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
3039 /* Store the vector statement in NODE. */
3040 SLP_TREE_VEC_STMTS (node
)[stride
* i
+ vect_stmts_counter
] = perm_stmt
;
3042 first_vec_indx
+= stride
;
3043 second_vec_indx
+= stride
;
3048 /* Given FIRST_MASK_ELEMENT - the mask element in element representation,
3049 return in CURRENT_MASK_ELEMENT its equivalent in target specific
3050 representation. Check that the mask is valid and return FALSE if not.
3051 Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
3052 the next vector, i.e., the current first vector is not needed. */
3055 vect_get_mask_element (gimple stmt
, int first_mask_element
, int m
,
3056 int mask_nunits
, bool only_one_vec
, int index
,
3057 unsigned char *mask
, int *current_mask_element
,
3058 bool *need_next_vector
, int *number_of_mask_fixes
,
3059 bool *mask_fixed
, bool *needs_first_vector
)
3063 /* Convert to target specific representation. */
3064 *current_mask_element
= first_mask_element
+ m
;
3065 /* Adjust the value in case it's a mask for second and third vectors. */
3066 *current_mask_element
-= mask_nunits
* (*number_of_mask_fixes
- 1);
3068 if (*current_mask_element
< 0)
3070 if (dump_enabled_p ())
3072 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3073 "permutation requires past vector ");
3074 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3075 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3080 if (*current_mask_element
< mask_nunits
)
3081 *needs_first_vector
= true;
3083 /* We have only one input vector to permute but the mask accesses values in
3084 the next vector as well. */
3085 if (only_one_vec
&& *current_mask_element
>= mask_nunits
)
3087 if (dump_enabled_p ())
3089 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3090 "permutation requires at least two vectors ");
3091 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3092 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3098 /* The mask requires the next vector. */
3099 while (*current_mask_element
>= mask_nunits
* 2)
3101 if (*needs_first_vector
|| *mask_fixed
)
3103 /* We either need the first vector too or have already moved to the
3104 next vector. In both cases, this permutation needs three
3106 if (dump_enabled_p ())
3108 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3109 "permutation requires at "
3110 "least three vectors ");
3111 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3112 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3118 /* We move to the next vector, dropping the first one and working with
3119 the second and the third - we need to adjust the values of the mask
3121 *current_mask_element
-= mask_nunits
* *number_of_mask_fixes
;
3123 for (i
= 0; i
< index
; i
++)
3124 mask
[i
] -= mask_nunits
* *number_of_mask_fixes
;
3126 (*number_of_mask_fixes
)++;
3130 *need_next_vector
= *mask_fixed
;
3132 /* This was the last element of this mask. Start a new one. */
3133 if (index
== mask_nunits
- 1)
3135 *number_of_mask_fixes
= 1;
3136 *mask_fixed
= false;
3137 *needs_first_vector
= false;
3144 /* Generate vector permute statements from a list of loads in DR_CHAIN.
3145 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
3146 permute statements for the SLP node NODE of the SLP instance
3147 SLP_NODE_INSTANCE. */
3150 vect_transform_slp_perm_load (slp_tree node
, vec
<tree
> dr_chain
,
3151 gimple_stmt_iterator
*gsi
, int vf
,
3152 slp_instance slp_node_instance
, bool analyze_only
)
3154 gimple stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3155 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3156 tree mask_element_type
= NULL_TREE
, mask_type
;
3157 int i
, j
, k
, nunits
, vec_index
= 0;
3158 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3159 int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_node_instance
);
3160 int first_mask_element
;
3161 int index
, unroll_factor
, current_mask_element
, ncopies
;
3162 unsigned char *mask
;
3163 bool only_one_vec
= false, need_next_vector
= false;
3164 int first_vec_index
, second_vec_index
, orig_vec_stmts_num
, vect_stmts_counter
;
3165 int number_of_mask_fixes
= 1;
3166 bool mask_fixed
= false;
3167 bool needs_first_vector
= false;
3170 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3173 stmt_info
= vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info
));
3175 mode
= TYPE_MODE (vectype
);
3177 if (!can_vec_perm_p (mode
, false, NULL
))
3179 if (dump_enabled_p ())
3181 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3182 "no vect permute for ");
3183 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3184 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3189 /* The generic VEC_PERM_EXPR code always uses an integral type of the
3190 same size as the vector element being permuted. */
3191 mask_element_type
= lang_hooks
.types
.type_for_mode
3192 (int_mode_for_mode (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3193 mask_type
= get_vectype_for_scalar_type (mask_element_type
);
3194 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3195 mask
= XALLOCAVEC (unsigned char, nunits
);
3196 unroll_factor
= SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3198 /* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
3199 unrolling factor. */
3201 = (STMT_VINFO_GROUP_SIZE (stmt_info
)
3202 * SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
)
3203 + nunits
- 1) / nunits
;
3204 if (orig_vec_stmts_num
== 1)
3205 only_one_vec
= true;
3207 /* Number of copies is determined by the final vectorization factor
3208 relatively to SLP_NODE_INSTANCE unrolling factor. */
3209 ncopies
= vf
/ SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3211 /* Generate permutation masks for every NODE. Number of masks for each NODE
3212 is equal to GROUP_SIZE.
3213 E.g., we have a group of three nodes with three loads from the same
3214 location in each node, and the vector size is 4. I.e., we have a
3215 a0b0c0a1b1c1... sequence and we need to create the following vectors:
3216 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
3217 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
3220 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9}.
3221 The last mask is illegal since we assume two operands for permute
3222 operation, and the mask element values can't be outside that range.
3223 Hence, the last mask must be converted into {2,5,5,5}.
3224 For the first two permutations we need the first and the second input
3225 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
3226 we need the second and the third vectors: {b1,c1,a2,b2} and
3231 vect_stmts_counter
= 0;
3233 first_vec_index
= vec_index
++;
3235 second_vec_index
= first_vec_index
;
3237 second_vec_index
= vec_index
++;
3239 for (j
= 0; j
< unroll_factor
; j
++)
3241 for (k
= 0; k
< group_size
; k
++)
3243 i
= SLP_TREE_LOAD_PERMUTATION (node
)[k
];
3244 first_mask_element
= i
+ j
* STMT_VINFO_GROUP_SIZE (stmt_info
);
3245 if (!vect_get_mask_element (stmt
, first_mask_element
, 0,
3246 nunits
, only_one_vec
, index
,
3247 mask
, ¤t_mask_element
,
3249 &number_of_mask_fixes
, &mask_fixed
,
3250 &needs_first_vector
))
3252 gcc_assert (current_mask_element
>= 0
3253 && current_mask_element
< 2 * nunits
);
3254 mask
[index
++] = current_mask_element
;
3256 if (index
== nunits
)
3259 if (!can_vec_perm_p (mode
, false, mask
))
3261 if (dump_enabled_p ())
3263 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
3265 "unsupported vect permute { ");
3266 for (i
= 0; i
< nunits
; ++i
)
3267 dump_printf (MSG_MISSED_OPTIMIZATION
, "%d ",
3269 dump_printf (MSG_MISSED_OPTIMIZATION
, "}\n");
3277 tree mask_vec
, *mask_elts
;
3278 mask_elts
= XALLOCAVEC (tree
, nunits
);
3279 for (l
= 0; l
< nunits
; ++l
)
3280 mask_elts
[l
] = build_int_cst (mask_element_type
,
3282 mask_vec
= build_vector (mask_type
, mask_elts
);
3284 if (need_next_vector
)
3286 first_vec_index
= second_vec_index
;
3287 second_vec_index
= vec_index
;
3290 vect_create_mask_and_perm (stmt
,
3291 mask_vec
, first_vec_index
, second_vec_index
,
3292 gsi
, node
, vectype
, dr_chain
,
3293 ncopies
, vect_stmts_counter
++);
3305 /* Vectorize SLP instance tree in postorder. */
3308 vect_schedule_slp_instance (slp_tree node
, slp_instance instance
,
3309 unsigned int vectorization_factor
)
3312 bool grouped_store
, is_store
;
3313 gimple_stmt_iterator si
;
3314 stmt_vec_info stmt_info
;
3315 unsigned int vec_stmts_size
, nunits
, group_size
;
3323 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3324 vect_schedule_slp_instance (child
, instance
, vectorization_factor
);
3326 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3327 stmt_info
= vinfo_for_stmt (stmt
);
3329 /* VECTYPE is the type of the destination. */
3330 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3331 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (vectype
);
3332 group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
3334 /* For each SLP instance calculate number of vector stmts to be created
3335 for the scalar stmts in each node of the SLP tree. Number of vector
3336 elements in one vector iteration is the number of scalar elements in
3337 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
3339 Unless this is a SLP reduction in which case the number of vector
3340 stmts is equal to the number of vector stmts of the children. */
3341 if (GROUP_FIRST_ELEMENT (stmt_info
)
3342 && !STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3343 vec_stmts_size
= SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_CHILDREN (node
)[0]);
3345 vec_stmts_size
= (vectorization_factor
* group_size
) / nunits
;
3347 if (!SLP_TREE_VEC_STMTS (node
).exists ())
3349 SLP_TREE_VEC_STMTS (node
).create (vec_stmts_size
);
3350 SLP_TREE_NUMBER_OF_VEC_STMTS (node
) = vec_stmts_size
;
3353 if (dump_enabled_p ())
3355 dump_printf_loc (MSG_NOTE
,vect_location
,
3356 "------>vectorizing SLP node starting from: ");
3357 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3358 dump_printf (MSG_NOTE
, "\n");
3361 /* Vectorized stmts go before the last scalar stmt which is where
3362 all uses are ready. */
3363 si
= gsi_for_stmt (vect_find_last_scalar_stmt_in_slp (node
));
3365 /* Mark the first element of the reduction chain as reduction to properly
3366 transform the node. In the analysis phase only the last element of the
3367 chain is marked as reduction. */
3368 if (GROUP_FIRST_ELEMENT (stmt_info
) && !STMT_VINFO_GROUPED_ACCESS (stmt_info
)
3369 && GROUP_FIRST_ELEMENT (stmt_info
) == stmt
)
3371 STMT_VINFO_DEF_TYPE (stmt_info
) = vect_reduction_def
;
3372 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
3375 /* Handle two-operation SLP nodes by vectorizing the group with
3376 both operations and then performing a merge. */
3377 if (SLP_TREE_TWO_OPERATORS (node
))
3379 enum tree_code code0
= gimple_assign_rhs_code (stmt
);
3380 enum tree_code ocode
;
3382 unsigned char *mask
= XALLOCAVEC (unsigned char, group_size
);
3383 bool allsame
= true;
3384 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, ostmt
)
3385 if (gimple_assign_rhs_code (ostmt
) != code0
)
3389 ocode
= gimple_assign_rhs_code (ostmt
);
3398 tree tmask
= NULL_TREE
;
3399 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3400 v0
= SLP_TREE_VEC_STMTS (node
).copy ();
3401 SLP_TREE_VEC_STMTS (node
).truncate (0);
3402 gimple_assign_set_rhs_code (stmt
, ocode
);
3403 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3404 gimple_assign_set_rhs_code (stmt
, code0
);
3405 v1
= SLP_TREE_VEC_STMTS (node
).copy ();
3406 SLP_TREE_VEC_STMTS (node
).truncate (0);
3407 tree meltype
= build_nonstandard_integer_type
3408 (GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3409 tree mvectype
= get_same_sized_vectype (meltype
, vectype
);
3411 for (j
= 0; j
< v0
.length (); ++j
)
3413 tree
*melts
= XALLOCAVEC (tree
, TYPE_VECTOR_SUBPARTS (vectype
));
3414 for (l
= 0; l
< TYPE_VECTOR_SUBPARTS (vectype
); ++l
)
3416 if (k
>= group_size
)
3418 melts
[l
] = build_int_cst
3419 (meltype
, mask
[k
++] * TYPE_VECTOR_SUBPARTS (vectype
) + l
);
3421 tmask
= build_vector (mvectype
, melts
);
3423 /* ??? Not all targets support a VEC_PERM_EXPR with a
3424 constant mask that would translate to a vec_merge RTX
3425 (with their vec_perm_const_ok). We can either not
3426 vectorize in that case or let veclower do its job.
3427 Unfortunately that isn't too great and at least for
3428 plus/minus we'd eventually like to match targets
3429 vector addsub instructions. */
3431 vstmt
= gimple_build_assign (make_ssa_name (vectype
),
3433 gimple_assign_lhs (v0
[j
]),
3434 gimple_assign_lhs (v1
[j
]), tmask
);
3435 vect_finish_stmt_generation (stmt
, vstmt
, &si
);
3436 SLP_TREE_VEC_STMTS (node
).quick_push (vstmt
);
3443 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3447 /* Replace scalar calls from SLP node NODE with setting of their lhs to zero.
3448 For loop vectorization this is done in vectorizable_call, but for SLP
3449 it needs to be deferred until end of vect_schedule_slp, because multiple
3450 SLP instances may refer to the same scalar stmt. */
3453 vect_remove_slp_scalar_calls (slp_tree node
)
3455 gimple stmt
, new_stmt
;
3456 gimple_stmt_iterator gsi
;
3460 stmt_vec_info stmt_info
;
3465 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3466 vect_remove_slp_scalar_calls (child
);
3468 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
3470 if (!is_gimple_call (stmt
) || gimple_bb (stmt
) == NULL
)
3472 stmt_info
= vinfo_for_stmt (stmt
);
3473 if (stmt_info
== NULL
3474 || is_pattern_stmt_p (stmt_info
)
3475 || !PURE_SLP_STMT (stmt_info
))
3477 lhs
= gimple_call_lhs (stmt
);
3478 new_stmt
= gimple_build_assign (lhs
, build_zero_cst (TREE_TYPE (lhs
)));
3479 set_vinfo_for_stmt (new_stmt
, stmt_info
);
3480 set_vinfo_for_stmt (stmt
, NULL
);
3481 STMT_VINFO_STMT (stmt_info
) = new_stmt
;
3482 gsi
= gsi_for_stmt (stmt
);
3483 gsi_replace (&gsi
, new_stmt
, false);
3484 SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt
)) = new_stmt
;
3488 /* Generate vector code for all SLP instances in the loop/basic block. */
3491 vect_schedule_slp (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
)
3493 vec
<slp_instance
> slp_instances
;
3494 slp_instance instance
;
3496 bool is_store
= false;
3500 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
3501 vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3505 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
3509 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3511 /* Schedule the tree of INSTANCE. */
3512 is_store
= vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance
),
3514 if (dump_enabled_p ())
3515 dump_printf_loc (MSG_NOTE
, vect_location
,
3516 "vectorizing stmts using SLP.\n");
3519 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3521 slp_tree root
= SLP_INSTANCE_TREE (instance
);
3524 gimple_stmt_iterator gsi
;
3526 /* Remove scalar call stmts. Do not do this for basic-block
3527 vectorization as not all uses may be vectorized.
3528 ??? Why should this be necessary? DCE should be able to
3529 remove the stmts itself.
3530 ??? For BB vectorization we can as well remove scalar
3531 stmts starting from the SLP tree root if they have no
3534 vect_remove_slp_scalar_calls (root
);
3536 for (j
= 0; SLP_TREE_SCALAR_STMTS (root
).iterate (j
, &store
)
3537 && j
< SLP_INSTANCE_GROUP_SIZE (instance
); j
++)
3539 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store
)))
3542 if (is_pattern_stmt_p (vinfo_for_stmt (store
)))
3543 store
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (store
));
3544 /* Free the attached stmt_vec_info and remove the stmt. */
3545 gsi
= gsi_for_stmt (store
);
3546 unlink_stmt_vdef (store
);
3547 gsi_remove (&gsi
, true);
3548 release_defs (store
);
3549 free_stmt_vec_info (store
);
3557 /* Vectorize the basic block. */
3560 vect_slp_transform_bb (basic_block bb
)
3562 bb_vec_info bb_vinfo
= vec_info_for_bb (bb
);
3563 gimple_stmt_iterator si
;
3565 gcc_assert (bb_vinfo
);
3567 if (dump_enabled_p ())
3568 dump_printf_loc (MSG_NOTE
, vect_location
, "SLPing BB\n");
3570 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
3572 gimple stmt
= gsi_stmt (si
);
3573 stmt_vec_info stmt_info
;
3575 if (dump_enabled_p ())
3577 dump_printf_loc (MSG_NOTE
, vect_location
,
3578 "------>SLPing statement: ");
3579 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3580 dump_printf (MSG_NOTE
, "\n");
3583 stmt_info
= vinfo_for_stmt (stmt
);
3584 gcc_assert (stmt_info
);
3586 /* Schedule all the SLP instances when the first SLP stmt is reached. */
3587 if (STMT_SLP_TYPE (stmt_info
))
3589 vect_schedule_slp (NULL
, bb_vinfo
);
3594 if (dump_enabled_p ())
3595 dump_printf_loc (MSG_NOTE
, vect_location
,
3596 "BASIC BLOCK VECTORIZED\n");
3598 destroy_bb_vec_info (bb_vinfo
);