1 /* SLP - Basic Block Vectorization
2 Copyright (C) 2007-2015 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
4 and Ira Rosen <irar@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
30 #include "double-int.h"
37 #include "fold-const.h"
38 #include "stor-layout.h"
41 #include "hard-reg-set.h"
43 #include "basic-block.h"
44 #include "gimple-pretty-print.h"
45 #include "tree-ssa-alias.h"
46 #include "internal-fn.h"
47 #include "gimple-expr.h"
50 #include "gimple-iterator.h"
51 #include "gimple-ssa.h"
52 #include "tree-phinodes.h"
53 #include "ssa-iterators.h"
54 #include "stringpool.h"
55 #include "tree-ssanames.h"
56 #include "tree-pass.h"
61 #include "statistics.h"
63 #include "fixed-value.h"
64 #include "insn-config.h"
73 #include "recog.h" /* FIXME: for insn_data */
74 #include "insn-codes.h"
76 #include "tree-vectorizer.h"
77 #include "langhooks.h"
78 #include "gimple-walk.h"
80 /* Extract the location of the basic block in the source code.
81 Return the basic block location if succeed and NULL if not. */
84 find_bb_location (basic_block bb
)
87 gimple_stmt_iterator si
;
90 return UNKNOWN_LOCATION
;
92 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
95 if (gimple_location (stmt
) != UNKNOWN_LOCATION
)
96 return gimple_location (stmt
);
99 return UNKNOWN_LOCATION
;
103 /* Recursively free the memory allocated for the SLP tree rooted at NODE. */
106 vect_free_slp_tree (slp_tree node
)
114 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
115 vect_free_slp_tree (child
);
117 SLP_TREE_CHILDREN (node
).release ();
118 SLP_TREE_SCALAR_STMTS (node
).release ();
119 SLP_TREE_VEC_STMTS (node
).release ();
120 SLP_TREE_LOAD_PERMUTATION (node
).release ();
126 /* Free the memory allocated for the SLP instance. */
129 vect_free_slp_instance (slp_instance instance
)
131 vect_free_slp_tree (SLP_INSTANCE_TREE (instance
));
132 SLP_INSTANCE_LOADS (instance
).release ();
133 SLP_INSTANCE_BODY_COST_VEC (instance
).release ();
138 /* Create an SLP node for SCALAR_STMTS. */
141 vect_create_new_slp_node (vec
<gimple
> scalar_stmts
)
144 gimple stmt
= scalar_stmts
[0];
147 if (is_gimple_call (stmt
))
148 nops
= gimple_call_num_args (stmt
);
149 else if (is_gimple_assign (stmt
))
151 nops
= gimple_num_ops (stmt
) - 1;
152 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
158 node
= XNEW (struct _slp_tree
);
159 SLP_TREE_SCALAR_STMTS (node
) = scalar_stmts
;
160 SLP_TREE_VEC_STMTS (node
).create (0);
161 SLP_TREE_CHILDREN (node
).create (nops
);
162 SLP_TREE_LOAD_PERMUTATION (node
) = vNULL
;
168 /* Allocate operands info for NOPS operands, and GROUP_SIZE def-stmts for each
170 static vec
<slp_oprnd_info
>
171 vect_create_oprnd_info (int nops
, int group_size
)
174 slp_oprnd_info oprnd_info
;
175 vec
<slp_oprnd_info
> oprnds_info
;
177 oprnds_info
.create (nops
);
178 for (i
= 0; i
< nops
; i
++)
180 oprnd_info
= XNEW (struct _slp_oprnd_info
);
181 oprnd_info
->def_stmts
.create (group_size
);
182 oprnd_info
->first_dt
= vect_uninitialized_def
;
183 oprnd_info
->first_op_type
= NULL_TREE
;
184 oprnd_info
->first_pattern
= false;
185 oprnds_info
.quick_push (oprnd_info
);
192 /* Free operands info. */
195 vect_free_oprnd_info (vec
<slp_oprnd_info
> &oprnds_info
)
198 slp_oprnd_info oprnd_info
;
200 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
202 oprnd_info
->def_stmts
.release ();
203 XDELETE (oprnd_info
);
206 oprnds_info
.release ();
210 /* Find the place of the data-ref in STMT in the interleaving chain that starts
211 from FIRST_STMT. Return -1 if the data-ref is not a part of the chain. */
214 vect_get_place_in_interleaving_chain (gimple stmt
, gimple first_stmt
)
216 gimple next_stmt
= first_stmt
;
219 if (first_stmt
!= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
224 if (next_stmt
== stmt
)
226 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
228 result
+= GROUP_GAP (vinfo_for_stmt (next_stmt
));
236 /* Get the defs for the rhs of STMT (collect them in OPRNDS_INFO), check that
237 they are of a valid type and that they match the defs of the first stmt of
238 the SLP group (stored in OPRNDS_INFO). If there was a fatal error
239 return -1, if the error could be corrected by swapping operands of the
240 operation return 1, if everything is ok return 0. */
243 vect_get_and_check_slp_defs (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
244 gimple stmt
, bool first
,
245 vec
<slp_oprnd_info
> *oprnds_info
)
248 unsigned int i
, number_of_oprnds
;
251 enum vect_def_type dt
= vect_uninitialized_def
;
252 struct loop
*loop
= NULL
;
253 bool pattern
= false;
254 slp_oprnd_info oprnd_info
;
255 int first_op_idx
= 1;
256 bool commutative
= false;
257 bool first_op_cond
= false;
260 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
262 if (is_gimple_call (stmt
))
264 number_of_oprnds
= gimple_call_num_args (stmt
);
267 else if (is_gimple_assign (stmt
))
269 enum tree_code code
= gimple_assign_rhs_code (stmt
);
270 number_of_oprnds
= gimple_num_ops (stmt
) - 1;
271 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
273 first_op_cond
= true;
278 commutative
= commutative_tree_code (code
);
283 bool swapped
= false;
284 for (i
= 0; i
< number_of_oprnds
; i
++)
289 if (i
== 0 || i
== 1)
290 oprnd
= TREE_OPERAND (gimple_op (stmt
, first_op_idx
),
293 oprnd
= gimple_op (stmt
, first_op_idx
+ i
- 1);
296 oprnd
= gimple_op (stmt
, first_op_idx
+ (swapped
? !i
: i
));
298 oprnd_info
= (*oprnds_info
)[i
];
300 if (!vect_is_simple_use (oprnd
, NULL
, loop_vinfo
, bb_vinfo
, &def_stmt
,
302 || (!def_stmt
&& dt
!= vect_constant_def
))
304 if (dump_enabled_p ())
306 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
307 "Build SLP failed: can't find def for ");
308 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
309 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
315 /* Check if DEF_STMT is a part of a pattern in LOOP and get the def stmt
316 from the pattern. Check that all the stmts of the node are in the
318 if (def_stmt
&& gimple_bb (def_stmt
)
319 && ((loop
&& flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
)))
320 || (!loop
&& gimple_bb (def_stmt
) == BB_VINFO_BB (bb_vinfo
)
321 && gimple_code (def_stmt
) != GIMPLE_PHI
))
322 && vinfo_for_stmt (def_stmt
)
323 && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (def_stmt
))
324 && !STMT_VINFO_RELEVANT (vinfo_for_stmt (def_stmt
))
325 && !STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt
)))
328 if (!first
&& !oprnd_info
->first_pattern
)
338 if (dump_enabled_p ())
340 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
341 "Build SLP failed: some of the stmts"
342 " are in a pattern, and others are not ");
343 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
344 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
350 def_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
));
351 dt
= STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
));
353 if (dt
== vect_unknown_def_type
)
355 if (dump_enabled_p ())
356 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
357 "Unsupported pattern.\n");
361 switch (gimple_code (def_stmt
))
364 def
= gimple_phi_result (def_stmt
);
368 def
= gimple_assign_lhs (def_stmt
);
372 if (dump_enabled_p ())
373 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
374 "unsupported defining stmt:\n");
381 oprnd_info
->first_dt
= dt
;
382 oprnd_info
->first_pattern
= pattern
;
383 oprnd_info
->first_op_type
= TREE_TYPE (oprnd
);
387 /* Not first stmt of the group, check that the def-stmt/s match
388 the def-stmt/s of the first stmt. Allow different definition
389 types for reduction chains: the first stmt must be a
390 vect_reduction_def (a phi node), and the rest
391 vect_internal_def. */
392 if (((oprnd_info
->first_dt
!= dt
393 && !(oprnd_info
->first_dt
== vect_reduction_def
394 && dt
== vect_internal_def
)
395 && !((oprnd_info
->first_dt
== vect_external_def
396 || oprnd_info
->first_dt
== vect_constant_def
)
397 && (dt
== vect_external_def
398 || dt
== vect_constant_def
)))
399 || !types_compatible_p (oprnd_info
->first_op_type
,
402 /* Try swapping operands if we got a mismatch. */
411 if (dump_enabled_p ())
412 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
413 "Build SLP failed: different types\n");
419 /* Check the types of the definitions. */
422 case vect_constant_def
:
423 case vect_external_def
:
424 case vect_reduction_def
:
427 case vect_internal_def
:
428 oprnd_info
->def_stmts
.quick_push (def_stmt
);
432 /* FORNOW: Not supported. */
433 if (dump_enabled_p ())
435 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
436 "Build SLP failed: illegal type of def ");
437 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, def
);
438 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
450 tree cond
= gimple_assign_rhs1 (stmt
);
451 swap_ssa_operands (stmt
, &TREE_OPERAND (cond
, 0),
452 &TREE_OPERAND (cond
, 1));
453 TREE_SET_CODE (cond
, swap_tree_comparison (TREE_CODE (cond
)));
456 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
457 gimple_assign_rhs2_ptr (stmt
));
464 /* Verify if the scalar stmts STMTS are isomorphic, require data
465 permutation or are of unsupported types of operation. Return
466 true if they are, otherwise return false and indicate in *MATCHES
467 which stmts are not isomorphic to the first one. If MATCHES[0]
468 is false then this indicates the comparison could not be
469 carried out or the stmts will never be vectorized by SLP. */
472 vect_build_slp_tree_1 (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
473 vec
<gimple
> stmts
, unsigned int group_size
,
474 unsigned nops
, unsigned int *max_nunits
,
475 unsigned int vectorization_factor
, bool *matches
)
478 gimple stmt
= stmts
[0];
479 enum tree_code first_stmt_code
= ERROR_MARK
, rhs_code
= ERROR_MARK
;
480 enum tree_code first_cond_code
= ERROR_MARK
;
482 bool need_same_oprnds
= false;
483 tree vectype
, scalar_type
, first_op1
= NULL_TREE
;
486 machine_mode optab_op2_mode
;
487 machine_mode vec_mode
;
488 struct data_reference
*first_dr
;
490 gimple first_load
= NULL
, prev_first_load
= NULL
, old_first_load
= NULL
;
493 /* For every stmt in NODE find its def stmt/s. */
494 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
498 if (dump_enabled_p ())
500 dump_printf_loc (MSG_NOTE
, vect_location
, "Build SLP for ");
501 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
502 dump_printf (MSG_NOTE
, "\n");
505 /* Fail to vectorize statements marked as unvectorizable. */
506 if (!STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt
)))
508 if (dump_enabled_p ())
510 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
511 "Build SLP failed: unvectorizable statement ");
512 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
513 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
515 /* Fatal mismatch. */
520 lhs
= gimple_get_lhs (stmt
);
521 if (lhs
== NULL_TREE
)
523 if (dump_enabled_p ())
525 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
526 "Build SLP failed: not GIMPLE_ASSIGN nor "
528 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
529 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
531 /* Fatal mismatch. */
536 if (is_gimple_assign (stmt
)
537 && gimple_assign_rhs_code (stmt
) == COND_EXPR
538 && (cond
= gimple_assign_rhs1 (stmt
))
539 && !COMPARISON_CLASS_P (cond
))
541 if (dump_enabled_p ())
543 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
544 "Build SLP failed: condition is not "
546 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
547 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
549 /* Fatal mismatch. */
554 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
, &dummy
);
555 vectype
= get_vectype_for_scalar_type (scalar_type
);
558 if (dump_enabled_p ())
560 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
561 "Build SLP failed: unsupported data-type ");
562 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
564 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
566 /* Fatal mismatch. */
571 /* In case of multiple types we need to detect the smallest type. */
572 if (*max_nunits
< TYPE_VECTOR_SUBPARTS (vectype
))
574 *max_nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
576 vectorization_factor
= *max_nunits
;
579 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
581 rhs_code
= CALL_EXPR
;
582 if (gimple_call_internal_p (call_stmt
)
583 || gimple_call_tail_p (call_stmt
)
584 || gimple_call_noreturn_p (call_stmt
)
585 || !gimple_call_nothrow_p (call_stmt
)
586 || gimple_call_chain (call_stmt
))
588 if (dump_enabled_p ())
590 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
591 "Build SLP failed: unsupported call type ");
592 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
594 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
596 /* Fatal mismatch. */
602 rhs_code
= gimple_assign_rhs_code (stmt
);
604 /* Check the operation. */
607 first_stmt_code
= rhs_code
;
609 /* Shift arguments should be equal in all the packed stmts for a
610 vector shift with scalar shift operand. */
611 if (rhs_code
== LSHIFT_EXPR
|| rhs_code
== RSHIFT_EXPR
612 || rhs_code
== LROTATE_EXPR
613 || rhs_code
== RROTATE_EXPR
)
615 vec_mode
= TYPE_MODE (vectype
);
617 /* First see if we have a vector/vector shift. */
618 optab
= optab_for_tree_code (rhs_code
, vectype
,
622 || optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
624 /* No vector/vector shift, try for a vector/scalar shift. */
625 optab
= optab_for_tree_code (rhs_code
, vectype
,
630 if (dump_enabled_p ())
631 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
632 "Build SLP failed: no optab.\n");
633 /* Fatal mismatch. */
637 icode
= (int) optab_handler (optab
, vec_mode
);
638 if (icode
== CODE_FOR_nothing
)
640 if (dump_enabled_p ())
641 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
643 "op not supported by target.\n");
644 /* Fatal mismatch. */
648 optab_op2_mode
= insn_data
[icode
].operand
[2].mode
;
649 if (!VECTOR_MODE_P (optab_op2_mode
))
651 need_same_oprnds
= true;
652 first_op1
= gimple_assign_rhs2 (stmt
);
656 else if (rhs_code
== WIDEN_LSHIFT_EXPR
)
658 need_same_oprnds
= true;
659 first_op1
= gimple_assign_rhs2 (stmt
);
664 if (first_stmt_code
!= rhs_code
665 && (first_stmt_code
!= IMAGPART_EXPR
666 || rhs_code
!= REALPART_EXPR
)
667 && (first_stmt_code
!= REALPART_EXPR
668 || rhs_code
!= IMAGPART_EXPR
)
669 && !(STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
670 && (first_stmt_code
== ARRAY_REF
671 || first_stmt_code
== BIT_FIELD_REF
672 || first_stmt_code
== INDIRECT_REF
673 || first_stmt_code
== COMPONENT_REF
674 || first_stmt_code
== MEM_REF
)))
676 if (dump_enabled_p ())
678 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
679 "Build SLP failed: different operation "
681 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
682 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
689 && !operand_equal_p (first_op1
, gimple_assign_rhs2 (stmt
), 0))
691 if (dump_enabled_p ())
693 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
694 "Build SLP failed: different shift "
696 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
697 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
703 if (rhs_code
== CALL_EXPR
)
705 gimple first_stmt
= stmts
[0];
706 if (gimple_call_num_args (stmt
) != nops
707 || !operand_equal_p (gimple_call_fn (first_stmt
),
708 gimple_call_fn (stmt
), 0)
709 || gimple_call_fntype (first_stmt
)
710 != gimple_call_fntype (stmt
))
712 if (dump_enabled_p ())
714 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
715 "Build SLP failed: different calls in ");
716 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
718 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
726 /* Grouped store or load. */
727 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
729 if (REFERENCE_CLASS_P (lhs
))
737 unsigned unrolling_factor
738 = least_common_multiple
739 (*max_nunits
, group_size
) / group_size
;
740 /* FORNOW: Check that there is no gap between the loads
741 and no gap between the groups when we need to load
742 multiple groups at once.
743 ??? We should enhance this to only disallow gaps
745 if ((unrolling_factor
> 1
746 && ((GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) == stmt
747 && GROUP_GAP (vinfo_for_stmt (stmt
)) != 0)
748 /* If the group is split up then GROUP_GAP
749 isn't correct here, nor is GROUP_FIRST_ELEMENT. */
750 || GROUP_SIZE (vinfo_for_stmt (stmt
)) > group_size
))
751 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) != stmt
752 && GROUP_GAP (vinfo_for_stmt (stmt
)) != 1))
754 if (dump_enabled_p ())
756 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
757 "Build SLP failed: grouped "
759 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
761 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
763 /* Fatal mismatch. */
768 /* Check that the size of interleaved loads group is not
769 greater than the SLP group size. */
771 = vectorization_factor
/ TYPE_VECTOR_SUBPARTS (vectype
);
773 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) == stmt
774 && ((GROUP_SIZE (vinfo_for_stmt (stmt
))
775 - GROUP_GAP (vinfo_for_stmt (stmt
)))
776 > ncopies
* group_size
))
778 if (dump_enabled_p ())
780 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
781 "Build SLP failed: the number "
782 "of interleaved loads is greater than "
783 "the SLP group size ");
784 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
786 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
788 /* Fatal mismatch. */
793 old_first_load
= first_load
;
794 first_load
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
));
797 /* Check that there are no loads from different interleaving
798 chains in the same node. */
799 if (prev_first_load
!= first_load
)
801 if (dump_enabled_p ())
803 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
805 "Build SLP failed: different "
806 "interleaving chains in one node ");
807 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
809 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
816 prev_first_load
= first_load
;
818 /* In some cases a group of loads is just the same load
819 repeated N times. Only analyze its cost once. */
820 if (first_load
== stmt
&& old_first_load
!= first_load
)
822 first_dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
));
823 if (vect_supportable_dr_alignment (first_dr
, false)
824 == dr_unaligned_unsupported
)
826 if (dump_enabled_p ())
828 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
830 "Build SLP failed: unsupported "
832 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
834 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
836 /* Fatal mismatch. */
842 } /* Grouped access. */
845 if (TREE_CODE_CLASS (rhs_code
) == tcc_reference
)
847 /* Not grouped load. */
848 if (dump_enabled_p ())
850 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
851 "Build SLP failed: not grouped load ");
852 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
853 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
856 /* FORNOW: Not grouped loads are not supported. */
857 /* Fatal mismatch. */
862 /* Not memory operation. */
863 if (TREE_CODE_CLASS (rhs_code
) != tcc_binary
864 && TREE_CODE_CLASS (rhs_code
) != tcc_unary
865 && rhs_code
!= COND_EXPR
866 && rhs_code
!= CALL_EXPR
)
868 if (dump_enabled_p ())
870 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
871 "Build SLP failed: operation");
872 dump_printf (MSG_MISSED_OPTIMIZATION
, " unsupported ");
873 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
874 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
876 /* Fatal mismatch. */
881 if (rhs_code
== COND_EXPR
)
883 tree cond_expr
= gimple_assign_rhs1 (stmt
);
886 first_cond_code
= TREE_CODE (cond_expr
);
887 else if (first_cond_code
!= TREE_CODE (cond_expr
))
889 if (dump_enabled_p ())
891 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
892 "Build SLP failed: different"
894 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
896 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
907 for (i
= 0; i
< group_size
; ++i
)
914 /* Recursively build an SLP tree starting from NODE.
915 Fail (and return a value not equal to zero) if def-stmts are not
916 isomorphic, require data permutation or are of unsupported types of
917 operation. Otherwise, return 0.
918 The value returned is the depth in the SLP tree where a mismatch
922 vect_build_slp_tree (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
923 slp_tree
*node
, unsigned int group_size
,
924 unsigned int *max_nunits
,
925 vec
<slp_tree
> *loads
,
926 unsigned int vectorization_factor
,
927 bool *matches
, unsigned *npermutes
, unsigned *tree_size
,
928 unsigned max_tree_size
)
930 unsigned nops
, i
, this_tree_size
= 0;
935 stmt
= SLP_TREE_SCALAR_STMTS (*node
)[0];
936 if (is_gimple_call (stmt
))
937 nops
= gimple_call_num_args (stmt
);
938 else if (is_gimple_assign (stmt
))
940 nops
= gimple_num_ops (stmt
) - 1;
941 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
947 if (!vect_build_slp_tree_1 (loop_vinfo
, bb_vinfo
,
948 SLP_TREE_SCALAR_STMTS (*node
), group_size
, nops
,
949 max_nunits
, vectorization_factor
, matches
))
952 /* If the SLP node is a load, terminate the recursion. */
953 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
954 && DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
956 loads
->safe_push (*node
);
960 /* Get at the operands, verifying they are compatible. */
961 vec
<slp_oprnd_info
> oprnds_info
= vect_create_oprnd_info (nops
, group_size
);
962 slp_oprnd_info oprnd_info
;
963 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (*node
), i
, stmt
)
965 switch (vect_get_and_check_slp_defs (loop_vinfo
, bb_vinfo
,
966 stmt
, (i
== 0), &oprnds_info
))
972 vect_free_oprnd_info (oprnds_info
);
979 for (i
= 0; i
< group_size
; ++i
)
982 vect_free_oprnd_info (oprnds_info
);
986 stmt
= SLP_TREE_SCALAR_STMTS (*node
)[0];
988 /* Create SLP_TREE nodes for the definition node/s. */
989 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
992 unsigned old_nloads
= loads
->length ();
993 unsigned old_max_nunits
= *max_nunits
;
995 if (oprnd_info
->first_dt
!= vect_internal_def
)
998 if (++this_tree_size
> max_tree_size
)
1000 vect_free_oprnd_info (oprnds_info
);
1004 child
= vect_create_new_slp_node (oprnd_info
->def_stmts
);
1007 vect_free_oprnd_info (oprnds_info
);
1011 if (vect_build_slp_tree (loop_vinfo
, bb_vinfo
, &child
,
1012 group_size
, max_nunits
, loads
,
1013 vectorization_factor
, matches
,
1014 npermutes
, &this_tree_size
, max_tree_size
))
1016 oprnd_info
->def_stmts
= vNULL
;
1017 SLP_TREE_CHILDREN (*node
).quick_push (child
);
1021 /* If the SLP build failed fatally and we analyze a basic-block
1022 simply treat nodes we fail to build as externally defined
1023 (and thus build vectors from the scalar defs).
1024 The cost model will reject outright expensive cases.
1025 ??? This doesn't treat cases where permutation ultimatively
1026 fails (or we don't try permutation below). Ideally we'd
1027 even compute a permutation that will end up with the maximum
1031 /* ??? Rejecting patterns this way doesn't work. We'd have to
1032 do extra work to cancel the pattern so the uses see the
1034 && !is_pattern_stmt_p (vinfo_for_stmt (stmt
)))
1036 dump_printf_loc (MSG_NOTE
, vect_location
,
1037 "Building vector operands from scalars\n");
1038 oprnd_info
->def_stmts
= vNULL
;
1039 vect_free_slp_tree (child
);
1040 SLP_TREE_CHILDREN (*node
).quick_push (NULL
);
1044 /* If the SLP build for operand zero failed and operand zero
1045 and one can be commutated try that for the scalar stmts
1046 that failed the match. */
1048 /* A first scalar stmt mismatch signals a fatal mismatch. */
1050 /* ??? For COND_EXPRs we can swap the comparison operands
1051 as well as the arms under some constraints. */
1053 && oprnds_info
[1]->first_dt
== vect_internal_def
1054 && is_gimple_assign (stmt
)
1055 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
1056 /* Do so only if the number of not successful permutes was nor more
1057 than a cut-ff as re-trying the recursive match on
1058 possibly each level of the tree would expose exponential
1063 slp_tree grandchild
;
1066 *max_nunits
= old_max_nunits
;
1067 loads
->truncate (old_nloads
);
1068 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1069 vect_free_slp_tree (grandchild
);
1070 SLP_TREE_CHILDREN (child
).truncate (0);
1072 /* Swap mismatched definition stmts. */
1073 dump_printf_loc (MSG_NOTE
, vect_location
,
1074 "Re-trying with swapped operands of stmts ");
1075 for (j
= 0; j
< group_size
; ++j
)
1078 gimple tem
= oprnds_info
[0]->def_stmts
[j
];
1079 oprnds_info
[0]->def_stmts
[j
] = oprnds_info
[1]->def_stmts
[j
];
1080 oprnds_info
[1]->def_stmts
[j
] = tem
;
1081 dump_printf (MSG_NOTE
, "%d ", j
);
1083 dump_printf (MSG_NOTE
, "\n");
1084 /* And try again with scratch 'matches' ... */
1085 bool *tem
= XALLOCAVEC (bool, group_size
);
1086 if (vect_build_slp_tree (loop_vinfo
, bb_vinfo
, &child
,
1087 group_size
, max_nunits
, loads
,
1088 vectorization_factor
,
1089 tem
, npermutes
, &this_tree_size
,
1092 /* ... so if successful we can apply the operand swapping
1093 to the GIMPLE IL. This is necessary because for example
1094 vect_get_slp_defs uses operand indexes and thus expects
1095 canonical operand order. */
1096 for (j
= 0; j
< group_size
; ++j
)
1099 gimple stmt
= SLP_TREE_SCALAR_STMTS (*node
)[j
];
1100 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
1101 gimple_assign_rhs2_ptr (stmt
));
1103 oprnd_info
->def_stmts
= vNULL
;
1104 SLP_TREE_CHILDREN (*node
).quick_push (child
);
1111 oprnd_info
->def_stmts
= vNULL
;
1112 vect_free_slp_tree (child
);
1113 vect_free_oprnd_info (oprnds_info
);
1118 *tree_size
+= this_tree_size
;
1120 vect_free_oprnd_info (oprnds_info
);
1124 /* Dump a slp tree NODE using flags specified in DUMP_KIND. */
1127 vect_print_slp_tree (int dump_kind
, slp_tree node
)
1136 dump_printf (dump_kind
, "node ");
1137 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1139 dump_printf (dump_kind
, "\n\tstmt %d ", i
);
1140 dump_gimple_stmt (dump_kind
, TDF_SLIM
, stmt
, 0);
1142 dump_printf (dump_kind
, "\n");
1144 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1145 vect_print_slp_tree (dump_kind
, child
);
1149 /* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
1150 If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
1151 J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
1152 stmts in NODE are to be marked. */
1155 vect_mark_slp_stmts (slp_tree node
, enum slp_vect_type mark
, int j
)
1164 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1165 if (j
< 0 || i
== j
)
1166 STMT_SLP_TYPE (vinfo_for_stmt (stmt
)) = mark
;
1168 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1169 vect_mark_slp_stmts (child
, mark
, j
);
1173 /* Mark the statements of the tree rooted at NODE as relevant (vect_used). */
1176 vect_mark_slp_stmts_relevant (slp_tree node
)
1180 stmt_vec_info stmt_info
;
1186 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1188 stmt_info
= vinfo_for_stmt (stmt
);
1189 gcc_assert (!STMT_VINFO_RELEVANT (stmt_info
)
1190 || STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
);
1191 STMT_VINFO_RELEVANT (stmt_info
) = vect_used_in_scope
;
1194 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1195 vect_mark_slp_stmts_relevant (child
);
1199 /* Rearrange the statements of NODE according to PERMUTATION. */
1202 vect_slp_rearrange_stmts (slp_tree node
, unsigned int group_size
,
1203 vec
<unsigned> permutation
)
1206 vec
<gimple
> tmp_stmts
;
1210 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1211 vect_slp_rearrange_stmts (child
, group_size
, permutation
);
1213 gcc_assert (group_size
== SLP_TREE_SCALAR_STMTS (node
).length ());
1214 tmp_stmts
.create (group_size
);
1215 tmp_stmts
.quick_grow_cleared (group_size
);
1217 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1218 tmp_stmts
[permutation
[i
]] = stmt
;
1220 SLP_TREE_SCALAR_STMTS (node
).release ();
1221 SLP_TREE_SCALAR_STMTS (node
) = tmp_stmts
;
1225 /* Check if the required load permutations in the SLP instance
1226 SLP_INSTN are supported. */
1229 vect_supported_load_permutation_p (slp_instance slp_instn
)
1231 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1232 unsigned int i
, j
, k
, next
;
1235 gimple stmt
, load
, next_load
, first_load
;
1236 struct data_reference
*dr
;
1238 if (dump_enabled_p ())
1240 dump_printf_loc (MSG_NOTE
, vect_location
, "Load permutation ");
1241 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1242 if (node
->load_permutation
.exists ())
1243 FOR_EACH_VEC_ELT (node
->load_permutation
, j
, next
)
1244 dump_printf (MSG_NOTE
, "%d ", next
);
1246 for (k
= 0; k
< group_size
; ++k
)
1247 dump_printf (MSG_NOTE
, "%d ", k
);
1248 dump_printf (MSG_NOTE
, "\n");
1251 /* In case of reduction every load permutation is allowed, since the order
1252 of the reduction statements is not important (as opposed to the case of
1253 grouped stores). The only condition we need to check is that all the
1254 load nodes are of the same size and have the same permutation (and then
1255 rearrange all the nodes of the SLP instance according to this
1258 /* Check that all the load nodes are of the same size. */
1259 /* ??? Can't we assert this? */
1260 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1261 if (SLP_TREE_SCALAR_STMTS (node
).length () != (unsigned) group_size
)
1264 node
= SLP_INSTANCE_TREE (slp_instn
);
1265 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1267 /* Reduction (there are no data-refs in the root).
1268 In reduction chain the order of the loads is important. */
1269 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))
1270 && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1275 /* Compare all the permutation sequences to the first one. We know
1276 that at least one load is permuted. */
1277 node
= SLP_INSTANCE_LOADS (slp_instn
)[0];
1278 if (!node
->load_permutation
.exists ())
1280 for (i
= 1; SLP_INSTANCE_LOADS (slp_instn
).iterate (i
, &load
); ++i
)
1282 if (!load
->load_permutation
.exists ())
1284 FOR_EACH_VEC_ELT (load
->load_permutation
, j
, lidx
)
1285 if (lidx
!= node
->load_permutation
[j
])
1289 /* Check that the loads in the first sequence are different and there
1290 are no gaps between them. */
1291 load_index
= sbitmap_alloc (group_size
);
1292 bitmap_clear (load_index
);
1293 FOR_EACH_VEC_ELT (node
->load_permutation
, i
, lidx
)
1295 if (bitmap_bit_p (load_index
, lidx
))
1297 sbitmap_free (load_index
);
1300 bitmap_set_bit (load_index
, lidx
);
1302 for (i
= 0; i
< group_size
; i
++)
1303 if (!bitmap_bit_p (load_index
, i
))
1305 sbitmap_free (load_index
);
1308 sbitmap_free (load_index
);
1310 /* This permutation is valid for reduction. Since the order of the
1311 statements in the nodes is not important unless they are memory
1312 accesses, we can rearrange the statements in all the nodes
1313 according to the order of the loads. */
1314 vect_slp_rearrange_stmts (SLP_INSTANCE_TREE (slp_instn
), group_size
,
1315 node
->load_permutation
);
1317 /* We are done, no actual permutations need to be generated. */
1318 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1319 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1323 /* In basic block vectorization we allow any subchain of an interleaving
1325 FORNOW: not supported in loop SLP because of realignment compications. */
1326 if (STMT_VINFO_BB_VINFO (vinfo_for_stmt (stmt
)))
1328 /* Check whether the loads in an instance form a subchain and thus
1329 no permutation is necessary. */
1330 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1332 bool subchain_p
= true;
1334 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), j
, load
)
1336 if (j
!= 0 && next_load
!= load
)
1341 next_load
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (load
));
1344 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1347 /* Verify the permutation can be generated. */
1349 if (!vect_transform_slp_perm_load (node
, tem
, NULL
,
1350 1, slp_instn
, true))
1352 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
1354 "unsupported load permutation\n");
1360 /* Check that the alignment of the first load in every subchain, i.e.,
1361 the first statement in every load node, is supported.
1362 ??? This belongs in alignment checking. */
1363 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1365 first_load
= SLP_TREE_SCALAR_STMTS (node
)[0];
1366 if (first_load
!= GROUP_FIRST_ELEMENT (vinfo_for_stmt (first_load
)))
1368 dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (first_load
));
1369 if (vect_supportable_dr_alignment (dr
, false)
1370 == dr_unaligned_unsupported
)
1372 if (dump_enabled_p ())
1374 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
1376 "unsupported unaligned load ");
1377 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
1379 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1389 /* FORNOW: the only supported permutation is 0..01..1.. of length equal to
1390 GROUP_SIZE and where each sequence of same drs is of GROUP_SIZE length as
1391 well (unless it's reduction). */
1392 if (SLP_INSTANCE_LOADS (slp_instn
).length () != group_size
)
1394 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1395 if (!node
->load_permutation
.exists ())
1398 load_index
= sbitmap_alloc (group_size
);
1399 bitmap_clear (load_index
);
1400 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1402 unsigned int lidx
= node
->load_permutation
[0];
1403 if (bitmap_bit_p (load_index
, lidx
))
1405 sbitmap_free (load_index
);
1408 bitmap_set_bit (load_index
, lidx
);
1409 FOR_EACH_VEC_ELT (node
->load_permutation
, j
, k
)
1412 sbitmap_free (load_index
);
1416 for (i
= 0; i
< group_size
; i
++)
1417 if (!bitmap_bit_p (load_index
, i
))
1419 sbitmap_free (load_index
);
1422 sbitmap_free (load_index
);
1424 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1425 if (node
->load_permutation
.exists ()
1426 && !vect_transform_slp_perm_load
1428 SLP_INSTANCE_UNROLLING_FACTOR (slp_instn
), slp_instn
, true))
1434 /* Find the last store in SLP INSTANCE. */
1437 vect_find_last_scalar_stmt_in_slp (slp_tree node
)
1439 gimple last
= NULL
, stmt
;
1441 for (int i
= 0; SLP_TREE_SCALAR_STMTS (node
).iterate (i
, &stmt
); i
++)
1443 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
1444 if (is_pattern_stmt_p (stmt_vinfo
))
1445 last
= get_later_stmt (STMT_VINFO_RELATED_STMT (stmt_vinfo
), last
);
1447 last
= get_later_stmt (stmt
, last
);
1453 /* Compute the cost for the SLP node NODE in the SLP instance INSTANCE. */
1456 vect_analyze_slp_cost_1 (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1457 slp_instance instance
, slp_tree node
,
1458 stmt_vector_for_cost
*prologue_cost_vec
,
1459 unsigned ncopies_for_cost
)
1461 stmt_vector_for_cost
*body_cost_vec
= &SLP_INSTANCE_BODY_COST_VEC (instance
);
1466 stmt_vec_info stmt_info
;
1468 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1470 /* Recurse down the SLP tree. */
1471 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1473 vect_analyze_slp_cost_1 (loop_vinfo
, bb_vinfo
,
1474 instance
, child
, prologue_cost_vec
,
1477 /* Look at the first scalar stmt to determine the cost. */
1478 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1479 stmt_info
= vinfo_for_stmt (stmt
);
1480 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1482 if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info
)))
1483 vect_model_store_cost (stmt_info
, ncopies_for_cost
, false,
1484 vect_uninitialized_def
,
1485 node
, prologue_cost_vec
, body_cost_vec
);
1489 gcc_checking_assert (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)));
1490 vect_model_load_cost (stmt_info
, ncopies_for_cost
, false,
1491 node
, prologue_cost_vec
, body_cost_vec
);
1492 /* If the load is permuted record the cost for the permutation.
1493 ??? Loads from multiple chains are let through here only
1494 for a single special case involving complex numbers where
1495 in the end no permutation is necessary. */
1496 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, s
)
1497 if ((STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo_for_stmt (s
))
1498 == STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
))
1499 && vect_get_place_in_interleaving_chain
1500 (s
, STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
)) != i
)
1502 record_stmt_cost (body_cost_vec
, group_size
, vec_perm
,
1503 stmt_info
, 0, vect_body
);
1509 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1510 stmt_info
, 0, vect_body
);
1512 /* Scan operands and account for prologue cost of constants/externals.
1513 ??? This over-estimates cost for multiple uses and should be
1515 lhs
= gimple_get_lhs (stmt
);
1516 for (i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1518 tree def
, op
= gimple_op (stmt
, i
);
1520 enum vect_def_type dt
;
1521 if (!op
|| op
== lhs
)
1523 if (vect_is_simple_use (op
, NULL
, loop_vinfo
, bb_vinfo
,
1524 &def_stmt
, &def
, &dt
))
1526 /* Without looking at the actual initializer a vector of
1527 constants can be implemented as load from the constant pool.
1528 ??? We need to pass down stmt_info for a vector type
1529 even if it points to the wrong stmt. */
1530 if (dt
== vect_constant_def
)
1531 record_stmt_cost (prologue_cost_vec
, 1, vector_load
,
1532 stmt_info
, 0, vect_prologue
);
1533 else if (dt
== vect_external_def
)
1534 record_stmt_cost (prologue_cost_vec
, 1, vec_construct
,
1535 stmt_info
, 0, vect_prologue
);
1540 /* Compute the cost for the SLP instance INSTANCE. */
1543 vect_analyze_slp_cost (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1544 slp_instance instance
, unsigned nunits
)
1546 stmt_vector_for_cost body_cost_vec
, prologue_cost_vec
;
1547 unsigned ncopies_for_cost
;
1548 stmt_info_for_cost
*si
;
1551 /* Calculate the number of vector stmts to create based on the unrolling
1552 factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
1553 GROUP_SIZE / NUNITS otherwise. */
1554 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1555 ncopies_for_cost
= least_common_multiple (nunits
, group_size
) / nunits
;
1557 prologue_cost_vec
.create (10);
1558 body_cost_vec
.create (10);
1559 SLP_INSTANCE_BODY_COST_VEC (instance
) = body_cost_vec
;
1560 vect_analyze_slp_cost_1 (loop_vinfo
, bb_vinfo
,
1561 instance
, SLP_INSTANCE_TREE (instance
),
1562 &prologue_cost_vec
, ncopies_for_cost
);
1564 /* Record the prologue costs, which were delayed until we were
1565 sure that SLP was successful. Unlike the body costs, we know
1566 the final values now regardless of the loop vectorization factor. */
1567 void *data
= (loop_vinfo
? LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
)
1568 : BB_VINFO_TARGET_COST_DATA (bb_vinfo
));
1569 FOR_EACH_VEC_ELT (prologue_cost_vec
, i
, si
)
1571 struct _stmt_vec_info
*stmt_info
1572 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1573 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1574 si
->misalign
, vect_prologue
);
1577 prologue_cost_vec
.release ();
1580 /* Analyze an SLP instance starting from a group of grouped stores. Call
1581 vect_build_slp_tree to build a tree of packed stmts if possible.
1582 Return FALSE if it's impossible to SLP any stmt in the loop. */
1585 vect_analyze_slp_instance (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1586 gimple stmt
, unsigned max_tree_size
)
1588 slp_instance new_instance
;
1590 unsigned int group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1591 unsigned int unrolling_factor
= 1, nunits
;
1592 tree vectype
, scalar_type
= NULL_TREE
;
1594 unsigned int vectorization_factor
= 0;
1596 unsigned int max_nunits
= 0;
1597 vec
<slp_tree
> loads
;
1598 struct data_reference
*dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
));
1599 vec
<gimple
> scalar_stmts
;
1601 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1605 scalar_type
= TREE_TYPE (DR_REF (dr
));
1606 vectype
= get_vectype_for_scalar_type (scalar_type
);
1610 gcc_assert (loop_vinfo
);
1611 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1614 group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1618 gcc_assert (loop_vinfo
);
1619 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1620 group_size
= LOOP_VINFO_REDUCTIONS (loop_vinfo
).length ();
1625 if (dump_enabled_p ())
1627 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1628 "Build SLP failed: unsupported data-type ");
1629 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, scalar_type
);
1630 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1636 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
1638 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1640 vectorization_factor
= nunits
;
1642 /* Calculate the unrolling factor. */
1643 unrolling_factor
= least_common_multiple (nunits
, group_size
) / group_size
;
1644 if (unrolling_factor
!= 1 && !loop_vinfo
)
1646 if (dump_enabled_p ())
1647 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1648 "Build SLP failed: unrolling required in basic"
1654 /* Create a node (a root of the SLP tree) for the packed grouped stores. */
1655 scalar_stmts
.create (group_size
);
1657 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1659 /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
1662 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next
))
1663 && STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)))
1664 scalar_stmts
.safe_push (
1665 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)));
1667 scalar_stmts
.safe_push (next
);
1668 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
1673 /* Collect reduction statements. */
1674 vec
<gimple
> reductions
= LOOP_VINFO_REDUCTIONS (loop_vinfo
);
1675 for (i
= 0; reductions
.iterate (i
, &next
); i
++)
1676 scalar_stmts
.safe_push (next
);
1679 node
= vect_create_new_slp_node (scalar_stmts
);
1681 loads
.create (group_size
);
1683 /* Build the tree for the SLP instance. */
1684 bool *matches
= XALLOCAVEC (bool, group_size
);
1685 unsigned npermutes
= 0;
1686 if (vect_build_slp_tree (loop_vinfo
, bb_vinfo
, &node
, group_size
,
1687 &max_nunits
, &loads
,
1688 vectorization_factor
, matches
, &npermutes
, NULL
,
1691 /* Calculate the unrolling factor based on the smallest type. */
1692 if (max_nunits
> nunits
)
1693 unrolling_factor
= least_common_multiple (max_nunits
, group_size
)
1696 if (unrolling_factor
!= 1 && !loop_vinfo
)
1698 if (dump_enabled_p ())
1699 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1700 "Build SLP failed: unrolling required in basic"
1702 vect_free_slp_tree (node
);
1707 /* Create a new SLP instance. */
1708 new_instance
= XNEW (struct _slp_instance
);
1709 SLP_INSTANCE_TREE (new_instance
) = node
;
1710 SLP_INSTANCE_GROUP_SIZE (new_instance
) = group_size
;
1711 SLP_INSTANCE_UNROLLING_FACTOR (new_instance
) = unrolling_factor
;
1712 SLP_INSTANCE_BODY_COST_VEC (new_instance
) = vNULL
;
1713 SLP_INSTANCE_LOADS (new_instance
) = loads
;
1715 /* Compute the load permutation. */
1717 bool loads_permuted
= false;
1718 FOR_EACH_VEC_ELT (loads
, i
, load_node
)
1720 vec
<unsigned> load_permutation
;
1722 gimple load
, first_stmt
;
1723 bool this_load_permuted
= false;
1724 load_permutation
.create (group_size
);
1725 first_stmt
= GROUP_FIRST_ELEMENT
1726 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node
)[0]));
1727 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node
), j
, load
)
1730 = vect_get_place_in_interleaving_chain (load
, first_stmt
);
1731 gcc_assert (load_place
!= -1);
1732 if (load_place
!= j
)
1733 this_load_permuted
= true;
1734 load_permutation
.safe_push (load_place
);
1736 if (!this_load_permuted
)
1738 load_permutation
.release ();
1741 SLP_TREE_LOAD_PERMUTATION (load_node
) = load_permutation
;
1742 loads_permuted
= true;
1747 if (!vect_supported_load_permutation_p (new_instance
))
1749 if (dump_enabled_p ())
1751 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1752 "Build SLP failed: unsupported load "
1754 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
1755 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1757 vect_free_slp_instance (new_instance
);
1765 /* Compute the costs of this SLP instance. Delay this for BB
1766 vectorization as we don't have vector types computed yet. */
1767 vect_analyze_slp_cost (loop_vinfo
, bb_vinfo
,
1768 new_instance
, TYPE_VECTOR_SUBPARTS (vectype
));
1769 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).safe_push (new_instance
);
1772 BB_VINFO_SLP_INSTANCES (bb_vinfo
).safe_push (new_instance
);
1774 if (dump_enabled_p ())
1775 vect_print_slp_tree (MSG_NOTE
, node
);
1780 /* Failed to SLP. */
1781 /* Free the allocated memory. */
1782 vect_free_slp_tree (node
);
1789 /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
1790 trees of packed scalar stmts if SLP is possible. */
1793 vect_analyze_slp (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1794 unsigned max_tree_size
)
1797 vec
<gimple
> grouped_stores
;
1798 vec
<gimple
> reductions
= vNULL
;
1799 vec
<gimple
> reduc_chains
= vNULL
;
1800 gimple first_element
;
1803 if (dump_enabled_p ())
1804 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_analyze_slp ===\n");
1808 grouped_stores
= LOOP_VINFO_GROUPED_STORES (loop_vinfo
);
1809 reduc_chains
= LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
);
1810 reductions
= LOOP_VINFO_REDUCTIONS (loop_vinfo
);
1813 grouped_stores
= BB_VINFO_GROUPED_STORES (bb_vinfo
);
1815 /* Find SLP sequences starting from groups of grouped stores. */
1816 FOR_EACH_VEC_ELT (grouped_stores
, i
, first_element
)
1817 if (vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, first_element
,
1821 if (bb_vinfo
&& !ok
)
1823 if (dump_enabled_p ())
1824 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1825 "Failed to SLP the basic block.\n");
1831 && LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
).length () > 0)
1833 /* Find SLP sequences starting from reduction chains. */
1834 FOR_EACH_VEC_ELT (reduc_chains
, i
, first_element
)
1835 if (vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, first_element
,
1841 /* Don't try to vectorize SLP reductions if reduction chain was
1846 /* Find SLP sequences starting from groups of reductions. */
1847 if (loop_vinfo
&& LOOP_VINFO_REDUCTIONS (loop_vinfo
).length () > 1
1848 && vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, reductions
[0],
1856 /* For each possible SLP instance decide whether to SLP it and calculate overall
1857 unrolling factor needed to SLP the loop. Return TRUE if decided to SLP at
1858 least one instance. */
1861 vect_make_slp_decision (loop_vec_info loop_vinfo
)
1863 unsigned int i
, unrolling_factor
= 1;
1864 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
1865 slp_instance instance
;
1866 int decided_to_slp
= 0;
1868 if (dump_enabled_p ())
1869 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_make_slp_decision ==="
1872 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
1874 /* FORNOW: SLP if you can. */
1875 if (unrolling_factor
< SLP_INSTANCE_UNROLLING_FACTOR (instance
))
1876 unrolling_factor
= SLP_INSTANCE_UNROLLING_FACTOR (instance
);
1878 /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
1879 call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
1880 loop-based vectorization. Such stmts will be marked as HYBRID. */
1881 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
1885 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
) = unrolling_factor
;
1887 if (decided_to_slp
&& dump_enabled_p ())
1888 dump_printf_loc (MSG_NOTE
, vect_location
,
1889 "Decided to SLP %d instances. Unrolling factor %d\n",
1890 decided_to_slp
, unrolling_factor
);
1892 return (decided_to_slp
> 0);
1896 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
1897 can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
1900 vect_detect_hybrid_slp_stmts (slp_tree node
, unsigned i
, slp_vect_type stype
)
1902 gimple stmt
= SLP_TREE_SCALAR_STMTS (node
)[i
];
1903 imm_use_iterator imm_iter
;
1905 stmt_vec_info use_vinfo
, stmt_vinfo
= vinfo_for_stmt (stmt
);
1907 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
1908 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1911 /* Propagate hybrid down the SLP tree. */
1912 if (stype
== hybrid
)
1914 else if (HYBRID_SLP_STMT (stmt_vinfo
))
1918 /* Check if a pure SLP stmt has uses in non-SLP stmts. */
1919 gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo
));
1920 if (TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
1921 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, gimple_op (stmt
, 0))
1922 if (gimple_bb (use_stmt
)
1923 && flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
))
1924 && (use_vinfo
= vinfo_for_stmt (use_stmt
))
1925 && !STMT_SLP_TYPE (use_vinfo
)
1926 && (STMT_VINFO_RELEVANT (use_vinfo
)
1927 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo
))
1928 || (STMT_VINFO_IN_PATTERN_P (use_vinfo
)
1929 && STMT_VINFO_RELATED_STMT (use_vinfo
)
1930 && !STMT_SLP_TYPE (vinfo_for_stmt
1931 (STMT_VINFO_RELATED_STMT (use_vinfo
)))))
1932 && !(gimple_code (use_stmt
) == GIMPLE_PHI
1933 && STMT_VINFO_DEF_TYPE (use_vinfo
) == vect_reduction_def
))
1937 if (stype
== hybrid
)
1938 STMT_SLP_TYPE (stmt_vinfo
) = hybrid
;
1940 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
1942 vect_detect_hybrid_slp_stmts (child
, i
, stype
);
1945 /* Helpers for vect_detect_hybrid_slp walking pattern stmt uses. */
1948 vect_detect_hybrid_slp_1 (tree
*tp
, int *, void *data
)
1950 walk_stmt_info
*wi
= (walk_stmt_info
*)data
;
1951 struct loop
*loopp
= (struct loop
*)wi
->info
;
1956 if (TREE_CODE (*tp
) == SSA_NAME
1957 && !SSA_NAME_IS_DEFAULT_DEF (*tp
))
1959 gimple def_stmt
= SSA_NAME_DEF_STMT (*tp
);
1960 if (flow_bb_inside_loop_p (loopp
, gimple_bb (def_stmt
))
1961 && PURE_SLP_STMT (vinfo_for_stmt (def_stmt
)))
1962 STMT_SLP_TYPE (vinfo_for_stmt (def_stmt
)) = hybrid
;
1969 vect_detect_hybrid_slp_2 (gimple_stmt_iterator
*gsi
, bool *handled
,
1972 /* If the stmt is in a SLP instance then this isn't a reason
1973 to mark use definitions in other SLP instances as hybrid. */
1974 if (STMT_SLP_TYPE (vinfo_for_stmt (gsi_stmt (*gsi
))) != loop_vect
)
1979 /* Find stmts that must be both vectorized and SLPed. */
1982 vect_detect_hybrid_slp (loop_vec_info loop_vinfo
)
1985 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
1986 slp_instance instance
;
1988 if (dump_enabled_p ())
1989 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_detect_hybrid_slp ==="
1992 /* First walk all pattern stmt in the loop and mark defs of uses as
1993 hybrid because immediate uses in them are not recorded. */
1994 for (i
= 0; i
< LOOP_VINFO_LOOP (loop_vinfo
)->num_nodes
; ++i
)
1996 basic_block bb
= LOOP_VINFO_BBS (loop_vinfo
)[i
];
1997 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2000 gimple stmt
= gsi_stmt (gsi
);
2001 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2002 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
2005 memset (&wi
, 0, sizeof (wi
));
2006 wi
.info
= LOOP_VINFO_LOOP (loop_vinfo
);
2007 gimple_stmt_iterator gsi2
2008 = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info
));
2009 walk_gimple_stmt (&gsi2
, vect_detect_hybrid_slp_2
,
2010 vect_detect_hybrid_slp_1
, &wi
);
2011 walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
),
2012 vect_detect_hybrid_slp_2
,
2013 vect_detect_hybrid_slp_1
, &wi
);
2018 /* Then walk the SLP instance trees marking stmts with uses in
2019 non-SLP stmts as hybrid, also propagating hybrid down the
2020 SLP tree, collecting the above info on-the-fly. */
2021 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2023 for (unsigned i
= 0; i
< SLP_INSTANCE_GROUP_SIZE (instance
); ++i
)
2024 vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance
),
2030 /* Create and initialize a new bb_vec_info struct for BB, as well as
2031 stmt_vec_info structs for all the stmts in it. */
2034 new_bb_vec_info (basic_block bb
)
2036 bb_vec_info res
= NULL
;
2037 gimple_stmt_iterator gsi
;
2039 res
= (bb_vec_info
) xcalloc (1, sizeof (struct _bb_vec_info
));
2040 BB_VINFO_BB (res
) = bb
;
2042 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2044 gimple stmt
= gsi_stmt (gsi
);
2045 gimple_set_uid (stmt
, 0);
2046 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, NULL
, res
));
2049 BB_VINFO_GROUPED_STORES (res
).create (10);
2050 BB_VINFO_SLP_INSTANCES (res
).create (2);
2051 BB_VINFO_TARGET_COST_DATA (res
) = init_cost (NULL
);
2058 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
2059 stmts in the basic block. */
2062 destroy_bb_vec_info (bb_vec_info bb_vinfo
)
2064 vec
<slp_instance
> slp_instances
;
2065 slp_instance instance
;
2067 gimple_stmt_iterator si
;
2073 bb
= BB_VINFO_BB (bb_vinfo
);
2075 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2077 gimple stmt
= gsi_stmt (si
);
2078 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2081 /* Free stmt_vec_info. */
2082 free_stmt_vec_info (stmt
);
2085 vect_destroy_datarefs (NULL
, bb_vinfo
);
2086 free_dependence_relations (BB_VINFO_DDRS (bb_vinfo
));
2087 BB_VINFO_GROUPED_STORES (bb_vinfo
).release ();
2088 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2089 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2090 vect_free_slp_instance (instance
);
2091 BB_VINFO_SLP_INSTANCES (bb_vinfo
).release ();
2092 destroy_cost_data (BB_VINFO_TARGET_COST_DATA (bb_vinfo
));
2098 /* Analyze statements contained in SLP tree node after recursively analyzing
2099 the subtree. Return TRUE if the operations are supported. */
2102 vect_slp_analyze_node_operations (bb_vec_info bb_vinfo
, slp_tree node
)
2112 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2113 if (!vect_slp_analyze_node_operations (bb_vinfo
, child
))
2116 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2118 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2119 gcc_assert (stmt_info
);
2120 gcc_assert (PURE_SLP_STMT (stmt_info
));
2122 if (!vect_analyze_stmt (stmt
, &dummy
, node
))
2130 /* Analyze statements in SLP instances of the basic block. Return TRUE if the
2131 operations are supported. */
2134 vect_slp_analyze_operations (bb_vec_info bb_vinfo
)
2136 vec
<slp_instance
> slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2137 slp_instance instance
;
2140 for (i
= 0; slp_instances
.iterate (i
, &instance
); )
2142 if (!vect_slp_analyze_node_operations (bb_vinfo
,
2143 SLP_INSTANCE_TREE (instance
)))
2145 vect_free_slp_instance (instance
);
2146 slp_instances
.ordered_remove (i
);
2152 if (!slp_instances
.length ())
2159 /* Compute the scalar cost of the SLP node NODE and its children
2160 and return it. Do not account defs that are marked in LIFE and
2161 update LIFE according to uses of NODE. */
2164 vect_bb_slp_scalar_cost (basic_block bb
,
2165 slp_tree node
, vec
<bool, va_heap
> *life
)
2167 unsigned scalar_cost
= 0;
2172 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2175 ssa_op_iter op_iter
;
2176 def_operand_p def_p
;
2177 stmt_vec_info stmt_info
;
2182 /* If there is a non-vectorized use of the defs then the scalar
2183 stmt is kept live in which case we do not account it or any
2184 required defs in the SLP children in the scalar cost. This
2185 way we make the vectorization more costly when compared to
2187 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
2189 imm_use_iterator use_iter
;
2191 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, DEF_FROM_PTR (def_p
))
2192 if (!is_gimple_debug (use_stmt
)
2193 && (gimple_code (use_stmt
) == GIMPLE_PHI
2194 || gimple_bb (use_stmt
) != bb
2195 || !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (use_stmt
))))
2198 BREAK_FROM_IMM_USE_STMT (use_iter
);
2204 stmt_info
= vinfo_for_stmt (stmt
);
2205 if (STMT_VINFO_DATA_REF (stmt_info
))
2207 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)))
2208 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2210 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2213 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2215 scalar_cost
+= stmt_cost
;
2218 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2220 scalar_cost
+= vect_bb_slp_scalar_cost (bb
, child
, life
);
2225 /* Check if vectorization of the basic block is profitable. */
2228 vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo
)
2230 vec
<slp_instance
> slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2231 slp_instance instance
;
2233 unsigned int vec_inside_cost
= 0, vec_outside_cost
= 0, scalar_cost
= 0;
2234 unsigned int vec_prologue_cost
= 0, vec_epilogue_cost
= 0;
2235 void *target_cost_data
= BB_VINFO_TARGET_COST_DATA (bb_vinfo
);
2236 stmt_vec_info stmt_info
= NULL
;
2237 stmt_vector_for_cost body_cost_vec
;
2238 stmt_info_for_cost
*ci
;
2240 /* Calculate vector costs. */
2241 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2243 body_cost_vec
= SLP_INSTANCE_BODY_COST_VEC (instance
);
2245 FOR_EACH_VEC_ELT (body_cost_vec
, j
, ci
)
2247 stmt_info
= ci
->stmt
? vinfo_for_stmt (ci
->stmt
) : NULL
;
2248 (void) add_stmt_cost (target_cost_data
, ci
->count
, ci
->kind
,
2249 stmt_info
, ci
->misalign
, vect_body
);
2253 /* Calculate scalar cost. */
2254 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2256 auto_vec
<bool, 20> life
;
2257 life
.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance
));
2258 scalar_cost
+= vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo
),
2259 SLP_INSTANCE_TREE (instance
),
2263 /* Complete the target-specific cost calculation. */
2264 finish_cost (BB_VINFO_TARGET_COST_DATA (bb_vinfo
), &vec_prologue_cost
,
2265 &vec_inside_cost
, &vec_epilogue_cost
);
2267 vec_outside_cost
= vec_prologue_cost
+ vec_epilogue_cost
;
2269 if (dump_enabled_p ())
2271 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2272 dump_printf (MSG_NOTE
, " Vector inside of basic block cost: %d\n",
2274 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n", vec_prologue_cost
);
2275 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n", vec_epilogue_cost
);
2276 dump_printf (MSG_NOTE
, " Scalar cost of basic block: %d\n", scalar_cost
);
2279 /* Vectorization is profitable if its cost is less than the cost of scalar
2281 if (vec_outside_cost
+ vec_inside_cost
>= scalar_cost
)
2287 /* Check if the basic block can be vectorized. */
2290 vect_slp_analyze_bb_1 (basic_block bb
)
2292 bb_vec_info bb_vinfo
;
2293 vec
<slp_instance
> slp_instances
;
2294 slp_instance instance
;
2297 unsigned n_stmts
= 0;
2299 bb_vinfo
= new_bb_vec_info (bb
);
2303 if (!vect_analyze_data_refs (NULL
, bb_vinfo
, &min_vf
, &n_stmts
))
2305 if (dump_enabled_p ())
2306 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2307 "not vectorized: unhandled data-ref in basic "
2310 destroy_bb_vec_info (bb_vinfo
);
2314 if (BB_VINFO_DATAREFS (bb_vinfo
).length () < 2)
2316 if (dump_enabled_p ())
2317 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2318 "not vectorized: not enough data-refs in "
2321 destroy_bb_vec_info (bb_vinfo
);
2325 if (!vect_analyze_data_ref_accesses (NULL
, bb_vinfo
))
2327 if (dump_enabled_p ())
2328 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2329 "not vectorized: unhandled data access in "
2332 destroy_bb_vec_info (bb_vinfo
);
2336 vect_pattern_recog (NULL
, bb_vinfo
);
2338 if (!vect_analyze_data_refs_alignment (NULL
, bb_vinfo
))
2340 if (dump_enabled_p ())
2341 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2342 "not vectorized: bad data alignment in basic "
2345 destroy_bb_vec_info (bb_vinfo
);
2349 /* Check the SLP opportunities in the basic block, analyze and build SLP
2351 if (!vect_analyze_slp (NULL
, bb_vinfo
, n_stmts
))
2353 if (dump_enabled_p ())
2354 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2355 "not vectorized: failed to find SLP opportunities "
2356 "in basic block.\n");
2358 destroy_bb_vec_info (bb_vinfo
);
2362 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2364 /* Mark all the statements that we want to vectorize as pure SLP and
2366 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2368 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2369 vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance
));
2372 /* Mark all the statements that we do not want to vectorize. */
2373 for (gimple_stmt_iterator gsi
= gsi_start_bb (BB_VINFO_BB (bb_vinfo
));
2374 !gsi_end_p (gsi
); gsi_next (&gsi
))
2376 stmt_vec_info vinfo
= vinfo_for_stmt (gsi_stmt (gsi
));
2377 if (STMT_SLP_TYPE (vinfo
) != pure_slp
)
2378 STMT_VINFO_VECTORIZABLE (vinfo
) = false;
2381 /* Analyze dependences. At this point all stmts not participating in
2382 vectorization have to be marked. Dependence analysis assumes
2383 that we either vectorize all SLP instances or none at all. */
2384 if (!vect_slp_analyze_data_ref_dependences (bb_vinfo
))
2386 if (dump_enabled_p ())
2387 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2388 "not vectorized: unhandled data dependence "
2389 "in basic block.\n");
2391 destroy_bb_vec_info (bb_vinfo
);
2395 if (!vect_verify_datarefs_alignment (NULL
, bb_vinfo
))
2397 if (dump_enabled_p ())
2398 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2399 "not vectorized: unsupported alignment in basic "
2401 destroy_bb_vec_info (bb_vinfo
);
2405 if (!vect_slp_analyze_operations (bb_vinfo
))
2407 if (dump_enabled_p ())
2408 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2409 "not vectorized: bad operation in basic block.\n");
2411 destroy_bb_vec_info (bb_vinfo
);
2415 /* Compute the costs of the SLP instances. */
2416 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2418 gimple stmt
= SLP_TREE_SCALAR_STMTS (SLP_INSTANCE_TREE (instance
))[0];
2419 tree vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
2420 vect_analyze_slp_cost (NULL
, bb_vinfo
,
2421 instance
, TYPE_VECTOR_SUBPARTS (vectype
));
2424 /* Cost model: check if the vectorization is worthwhile. */
2425 if (!unlimited_cost_model (NULL
)
2426 && !vect_bb_vectorization_profitable_p (bb_vinfo
))
2428 if (dump_enabled_p ())
2429 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2430 "not vectorized: vectorization is not "
2433 destroy_bb_vec_info (bb_vinfo
);
2437 if (dump_enabled_p ())
2438 dump_printf_loc (MSG_NOTE
, vect_location
,
2439 "Basic block will be vectorized using SLP\n");
2446 vect_slp_analyze_bb (basic_block bb
)
2448 bb_vec_info bb_vinfo
;
2450 gimple_stmt_iterator gsi
;
2451 unsigned int vector_sizes
;
2453 if (dump_enabled_p ())
2454 dump_printf_loc (MSG_NOTE
, vect_location
, "===vect_slp_analyze_bb===\n");
2456 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2458 gimple stmt
= gsi_stmt (gsi
);
2459 if (!is_gimple_debug (stmt
)
2460 && !gimple_nop_p (stmt
)
2461 && gimple_code (stmt
) != GIMPLE_LABEL
)
2465 if (insns
> PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB
))
2467 if (dump_enabled_p ())
2468 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2469 "not vectorized: too many instructions in "
2475 /* Autodetect first vector size we try. */
2476 current_vector_size
= 0;
2477 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2481 bb_vinfo
= vect_slp_analyze_bb_1 (bb
);
2485 destroy_bb_vec_info (bb_vinfo
);
2487 vector_sizes
&= ~current_vector_size
;
2488 if (vector_sizes
== 0
2489 || current_vector_size
== 0)
2492 /* Try the next biggest vector size. */
2493 current_vector_size
= 1 << floor_log2 (vector_sizes
);
2494 if (dump_enabled_p ())
2495 dump_printf_loc (MSG_NOTE
, vect_location
,
2496 "***** Re-trying analysis with "
2497 "vector size %d\n", current_vector_size
);
2502 /* SLP costs are calculated according to SLP instance unrolling factor (i.e.,
2503 the number of created vector stmts depends on the unrolling factor).
2504 However, the actual number of vector stmts for every SLP node depends on
2505 VF which is set later in vect_analyze_operations (). Hence, SLP costs
2506 should be updated. In this function we assume that the inside costs
2507 calculated in vect_model_xxx_cost are linear in ncopies. */
2510 vect_update_slp_costs_according_to_vf (loop_vec_info loop_vinfo
)
2512 unsigned int i
, j
, vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2513 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2514 slp_instance instance
;
2515 stmt_vector_for_cost body_cost_vec
;
2516 stmt_info_for_cost
*si
;
2517 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2519 if (dump_enabled_p ())
2520 dump_printf_loc (MSG_NOTE
, vect_location
,
2521 "=== vect_update_slp_costs_according_to_vf ===\n");
2523 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2525 /* We assume that costs are linear in ncopies. */
2526 int ncopies
= vf
/ SLP_INSTANCE_UNROLLING_FACTOR (instance
);
2528 /* Record the instance's instructions in the target cost model.
2529 This was delayed until here because the count of instructions
2530 isn't known beforehand. */
2531 body_cost_vec
= SLP_INSTANCE_BODY_COST_VEC (instance
);
2533 FOR_EACH_VEC_ELT (body_cost_vec
, j
, si
)
2534 (void) add_stmt_cost (data
, si
->count
* ncopies
, si
->kind
,
2535 vinfo_for_stmt (si
->stmt
), si
->misalign
,
2541 /* For constant and loop invariant defs of SLP_NODE this function returns
2542 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
2543 OP_NUM determines if we gather defs for operand 0 or operand 1 of the RHS of
2544 scalar stmts. NUMBER_OF_VECTORS is the number of vector defs to create.
2545 REDUC_INDEX is the index of the reduction operand in the statements, unless
2549 vect_get_constant_vectors (tree op
, slp_tree slp_node
,
2550 vec
<tree
> *vec_oprnds
,
2551 unsigned int op_num
, unsigned int number_of_vectors
,
2554 vec
<gimple
> stmts
= SLP_TREE_SCALAR_STMTS (slp_node
);
2555 gimple stmt
= stmts
[0];
2556 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2560 unsigned j
, number_of_places_left_in_vector
;
2563 int group_size
= stmts
.length ();
2564 unsigned int vec_num
, i
;
2565 unsigned number_of_copies
= 1;
2567 voprnds
.create (number_of_vectors
);
2568 bool constant_p
, is_store
;
2569 tree neutral_op
= NULL
;
2570 enum tree_code code
= gimple_expr_code (stmt
);
2573 gimple_seq ctor_seq
= NULL
;
2575 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_reduction_def
2576 && reduc_index
!= -1)
2578 op_num
= reduc_index
- 1;
2579 op
= gimple_op (stmt
, reduc_index
);
2580 /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
2581 we need either neutral operands or the original operands. See
2582 get_initial_def_for_reduction() for details. */
2585 case WIDEN_SUM_EXPR
:
2591 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2592 neutral_op
= build_real (TREE_TYPE (op
), dconst0
);
2594 neutral_op
= build_int_cst (TREE_TYPE (op
), 0);
2599 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2600 neutral_op
= build_real (TREE_TYPE (op
), dconst1
);
2602 neutral_op
= build_int_cst (TREE_TYPE (op
), 1);
2607 neutral_op
= build_int_cst (TREE_TYPE (op
), -1);
2610 /* For MIN/MAX we don't have an easy neutral operand but
2611 the initial values can be used fine here. Only for
2612 a reduction chain we have to force a neutral element. */
2615 if (!GROUP_FIRST_ELEMENT (stmt_vinfo
))
2619 def_stmt
= SSA_NAME_DEF_STMT (op
);
2620 loop
= (gimple_bb (stmt
))->loop_father
;
2621 neutral_op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2622 loop_preheader_edge (loop
));
2631 if (STMT_VINFO_DATA_REF (stmt_vinfo
))
2634 op
= gimple_assign_rhs1 (stmt
);
2641 if (CONSTANT_CLASS_P (op
))
2646 vector_type
= get_vectype_for_scalar_type (TREE_TYPE (op
));
2647 gcc_assert (vector_type
);
2648 nunits
= TYPE_VECTOR_SUBPARTS (vector_type
);
2650 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
2651 created vectors. It is greater than 1 if unrolling is performed.
2653 For example, we have two scalar operands, s1 and s2 (e.g., group of
2654 strided accesses of size two), while NUNITS is four (i.e., four scalars
2655 of this type can be packed in a vector). The output vector will contain
2656 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
2659 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
2660 containing the operands.
2662 For example, NUNITS is four as before, and the group size is 8
2663 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
2664 {s5, s6, s7, s8}. */
2666 number_of_copies
= least_common_multiple (nunits
, group_size
) / group_size
;
2668 number_of_places_left_in_vector
= nunits
;
2669 elts
= XALLOCAVEC (tree
, nunits
);
2670 bool place_after_defs
= false;
2671 for (j
= 0; j
< number_of_copies
; j
++)
2673 for (i
= group_size
- 1; stmts
.iterate (i
, &stmt
); i
--)
2676 op
= gimple_assign_rhs1 (stmt
);
2682 if (op_num
== 0 || op_num
== 1)
2684 tree cond
= gimple_assign_rhs1 (stmt
);
2685 op
= TREE_OPERAND (cond
, op_num
);
2690 op
= gimple_assign_rhs2 (stmt
);
2692 op
= gimple_assign_rhs3 (stmt
);
2697 op
= gimple_call_arg (stmt
, op_num
);
2704 op
= gimple_op (stmt
, op_num
+ 1);
2705 /* Unlike the other binary operators, shifts/rotates have
2706 the shift count being int, instead of the same type as
2707 the lhs, so make sure the scalar is the right type if
2708 we are dealing with vectors of
2709 long long/long/short/char. */
2710 if (op_num
== 1 && TREE_CODE (op
) == INTEGER_CST
)
2711 op
= fold_convert (TREE_TYPE (vector_type
), op
);
2715 op
= gimple_op (stmt
, op_num
+ 1);
2720 if (reduc_index
!= -1)
2722 loop
= (gimple_bb (stmt
))->loop_father
;
2723 def_stmt
= SSA_NAME_DEF_STMT (op
);
2727 /* Get the def before the loop. In reduction chain we have only
2728 one initial value. */
2729 if ((j
!= (number_of_copies
- 1)
2730 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
2735 op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2736 loop_preheader_edge (loop
));
2739 /* Create 'vect_ = {op0,op1,...,opn}'. */
2740 number_of_places_left_in_vector
--;
2742 if (!types_compatible_p (TREE_TYPE (vector_type
), TREE_TYPE (op
)))
2744 if (CONSTANT_CLASS_P (op
))
2746 op
= fold_unary (VIEW_CONVERT_EXPR
,
2747 TREE_TYPE (vector_type
), op
);
2748 gcc_assert (op
&& CONSTANT_CLASS_P (op
));
2752 tree new_temp
= make_ssa_name (TREE_TYPE (vector_type
));
2754 op
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (vector_type
), op
);
2756 = gimple_build_assign (new_temp
, VIEW_CONVERT_EXPR
, op
);
2757 gimple_seq_add_stmt (&ctor_seq
, init_stmt
);
2761 elts
[number_of_places_left_in_vector
] = op
;
2762 if (!CONSTANT_CLASS_P (op
))
2764 if (TREE_CODE (orig_op
) == SSA_NAME
2765 && !SSA_NAME_IS_DEFAULT_DEF (orig_op
)
2766 && STMT_VINFO_BB_VINFO (stmt_vinfo
)
2767 && (STMT_VINFO_BB_VINFO (stmt_vinfo
)->bb
2768 == gimple_bb (SSA_NAME_DEF_STMT (orig_op
))))
2769 place_after_defs
= true;
2771 if (number_of_places_left_in_vector
== 0)
2773 number_of_places_left_in_vector
= nunits
;
2776 vec_cst
= build_vector (vector_type
, elts
);
2779 vec
<constructor_elt
, va_gc
> *v
;
2781 vec_alloc (v
, nunits
);
2782 for (k
= 0; k
< nunits
; ++k
)
2783 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[k
]);
2784 vec_cst
= build_constructor (vector_type
, v
);
2787 gimple_stmt_iterator gsi
;
2788 if (place_after_defs
)
2791 (vect_find_last_scalar_stmt_in_slp (slp_node
));
2792 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, &gsi
);
2795 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, NULL
);
2796 if (ctor_seq
!= NULL
)
2798 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (init
));
2799 gsi_insert_seq_before_without_update (&gsi
, ctor_seq
,
2803 voprnds
.quick_push (init
);
2804 place_after_defs
= false;
2809 /* Since the vectors are created in the reverse order, we should invert
2811 vec_num
= voprnds
.length ();
2812 for (j
= vec_num
; j
!= 0; j
--)
2814 vop
= voprnds
[j
- 1];
2815 vec_oprnds
->quick_push (vop
);
2820 /* In case that VF is greater than the unrolling factor needed for the SLP
2821 group of stmts, NUMBER_OF_VECTORS to be created is greater than
2822 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
2823 to replicate the vectors. */
2824 while (number_of_vectors
> vec_oprnds
->length ())
2826 tree neutral_vec
= NULL
;
2831 neutral_vec
= build_vector_from_val (vector_type
, neutral_op
);
2833 vec_oprnds
->quick_push (neutral_vec
);
2837 for (i
= 0; vec_oprnds
->iterate (i
, &vop
) && i
< vec_num
; i
++)
2838 vec_oprnds
->quick_push (vop
);
2844 /* Get vectorized definitions from SLP_NODE that contains corresponding
2845 vectorized def-stmts. */
2848 vect_get_slp_vect_defs (slp_tree slp_node
, vec
<tree
> *vec_oprnds
)
2851 gimple vec_def_stmt
;
2854 gcc_assert (SLP_TREE_VEC_STMTS (slp_node
).exists ());
2856 FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (slp_node
), i
, vec_def_stmt
)
2858 gcc_assert (vec_def_stmt
);
2859 vec_oprnd
= gimple_get_lhs (vec_def_stmt
);
2860 vec_oprnds
->quick_push (vec_oprnd
);
2865 /* Get vectorized definitions for SLP_NODE.
2866 If the scalar definitions are loop invariants or constants, collect them and
2867 call vect_get_constant_vectors() to create vector stmts.
2868 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
2869 must be stored in the corresponding child of SLP_NODE, and we call
2870 vect_get_slp_vect_defs () to retrieve them. */
2873 vect_get_slp_defs (vec
<tree
> ops
, slp_tree slp_node
,
2874 vec
<vec
<tree
> > *vec_oprnds
, int reduc_index
)
2877 int number_of_vects
= 0, i
;
2878 unsigned int child_index
= 0;
2879 HOST_WIDE_INT lhs_size_unit
, rhs_size_unit
;
2880 slp_tree child
= NULL
;
2883 bool vectorized_defs
;
2885 first_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[0];
2886 FOR_EACH_VEC_ELT (ops
, i
, oprnd
)
2888 /* For each operand we check if it has vectorized definitions in a child
2889 node or we need to create them (for invariants and constants). We
2890 check if the LHS of the first stmt of the next child matches OPRND.
2891 If it does, we found the correct child. Otherwise, we call
2892 vect_get_constant_vectors (), and not advance CHILD_INDEX in order
2893 to check this child node for the next operand. */
2894 vectorized_defs
= false;
2895 if (SLP_TREE_CHILDREN (slp_node
).length () > child_index
)
2897 child
= SLP_TREE_CHILDREN (slp_node
)[child_index
];
2899 /* We have to check both pattern and original def, if available. */
2902 gimple first_def
= SLP_TREE_SCALAR_STMTS (child
)[0];
2904 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def
));
2906 if (operand_equal_p (oprnd
, gimple_get_lhs (first_def
), 0)
2908 && operand_equal_p (oprnd
, gimple_get_lhs (related
), 0)))
2910 /* The number of vector defs is determined by the number of
2911 vector statements in the node from which we get those
2913 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (child
);
2914 vectorized_defs
= true;
2922 if (!vectorized_defs
)
2926 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
2927 /* Number of vector stmts was calculated according to LHS in
2928 vect_schedule_slp_instance (), fix it by replacing LHS with
2929 RHS, if necessary. See vect_get_smallest_scalar_type () for
2931 vect_get_smallest_scalar_type (first_stmt
, &lhs_size_unit
,
2933 if (rhs_size_unit
!= lhs_size_unit
)
2935 number_of_vects
*= rhs_size_unit
;
2936 number_of_vects
/= lhs_size_unit
;
2941 /* Allocate memory for vectorized defs. */
2943 vec_defs
.create (number_of_vects
);
2945 /* For reduction defs we call vect_get_constant_vectors (), since we are
2946 looking for initial loop invariant values. */
2947 if (vectorized_defs
&& reduc_index
== -1)
2948 /* The defs are already vectorized. */
2949 vect_get_slp_vect_defs (child
, &vec_defs
);
2951 /* Build vectors from scalar defs. */
2952 vect_get_constant_vectors (oprnd
, slp_node
, &vec_defs
, i
,
2953 number_of_vects
, reduc_index
);
2955 vec_oprnds
->quick_push (vec_defs
);
2957 /* For reductions, we only need initial values. */
2958 if (reduc_index
!= -1)
2964 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
2965 building a vector of type MASK_TYPE from it) and two input vectors placed in
2966 DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
2967 shifting by STRIDE elements of DR_CHAIN for every copy.
2968 (STRIDE is the number of vectorized stmts for NODE divided by the number of
2970 VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
2971 the created stmts must be inserted. */
2974 vect_create_mask_and_perm (gimple stmt
, gimple next_scalar_stmt
,
2975 tree mask
, int first_vec_indx
, int second_vec_indx
,
2976 gimple_stmt_iterator
*gsi
, slp_tree node
,
2977 tree vectype
, vec
<tree
> dr_chain
,
2978 int ncopies
, int vect_stmts_counter
)
2981 gimple perm_stmt
= NULL
;
2982 stmt_vec_info next_stmt_info
;
2984 tree first_vec
, second_vec
, data_ref
;
2986 stride
= SLP_TREE_NUMBER_OF_VEC_STMTS (node
) / ncopies
;
2988 /* Initialize the vect stmts of NODE to properly insert the generated
2990 for (i
= SLP_TREE_VEC_STMTS (node
).length ();
2991 i
< (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node
); i
++)
2992 SLP_TREE_VEC_STMTS (node
).quick_push (NULL
);
2994 perm_dest
= vect_create_destination_var (gimple_assign_lhs (stmt
), vectype
);
2995 for (i
= 0; i
< ncopies
; i
++)
2997 first_vec
= dr_chain
[first_vec_indx
];
2998 second_vec
= dr_chain
[second_vec_indx
];
3000 /* Generate the permute statement. */
3001 perm_stmt
= gimple_build_assign (perm_dest
, VEC_PERM_EXPR
,
3002 first_vec
, second_vec
, mask
);
3003 data_ref
= make_ssa_name (perm_dest
, perm_stmt
);
3004 gimple_set_lhs (perm_stmt
, data_ref
);
3005 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
3007 /* Store the vector statement in NODE. */
3008 SLP_TREE_VEC_STMTS (node
)[stride
* i
+ vect_stmts_counter
] = perm_stmt
;
3010 first_vec_indx
+= stride
;
3011 second_vec_indx
+= stride
;
3014 /* Mark the scalar stmt as vectorized. */
3015 next_stmt_info
= vinfo_for_stmt (next_scalar_stmt
);
3016 STMT_VINFO_VEC_STMT (next_stmt_info
) = perm_stmt
;
3020 /* Given FIRST_MASK_ELEMENT - the mask element in element representation,
3021 return in CURRENT_MASK_ELEMENT its equivalent in target specific
3022 representation. Check that the mask is valid and return FALSE if not.
3023 Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
3024 the next vector, i.e., the current first vector is not needed. */
3027 vect_get_mask_element (gimple stmt
, int first_mask_element
, int m
,
3028 int mask_nunits
, bool only_one_vec
, int index
,
3029 unsigned char *mask
, int *current_mask_element
,
3030 bool *need_next_vector
, int *number_of_mask_fixes
,
3031 bool *mask_fixed
, bool *needs_first_vector
)
3035 /* Convert to target specific representation. */
3036 *current_mask_element
= first_mask_element
+ m
;
3037 /* Adjust the value in case it's a mask for second and third vectors. */
3038 *current_mask_element
-= mask_nunits
* (*number_of_mask_fixes
- 1);
3040 if (*current_mask_element
< 0)
3042 if (dump_enabled_p ())
3044 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3045 "permutation requires past vector ");
3046 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3047 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3052 if (*current_mask_element
< mask_nunits
)
3053 *needs_first_vector
= true;
3055 /* We have only one input vector to permute but the mask accesses values in
3056 the next vector as well. */
3057 if (only_one_vec
&& *current_mask_element
>= mask_nunits
)
3059 if (dump_enabled_p ())
3061 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3062 "permutation requires at least two vectors ");
3063 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3064 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3070 /* The mask requires the next vector. */
3071 while (*current_mask_element
>= mask_nunits
* 2)
3073 if (*needs_first_vector
|| *mask_fixed
)
3075 /* We either need the first vector too or have already moved to the
3076 next vector. In both cases, this permutation needs three
3078 if (dump_enabled_p ())
3080 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3081 "permutation requires at "
3082 "least three vectors ");
3083 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3084 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3090 /* We move to the next vector, dropping the first one and working with
3091 the second and the third - we need to adjust the values of the mask
3093 *current_mask_element
-= mask_nunits
* *number_of_mask_fixes
;
3095 for (i
= 0; i
< index
; i
++)
3096 mask
[i
] -= mask_nunits
* *number_of_mask_fixes
;
3098 (*number_of_mask_fixes
)++;
3102 *need_next_vector
= *mask_fixed
;
3104 /* This was the last element of this mask. Start a new one. */
3105 if (index
== mask_nunits
- 1)
3107 *number_of_mask_fixes
= 1;
3108 *mask_fixed
= false;
3109 *needs_first_vector
= false;
3116 /* Generate vector permute statements from a list of loads in DR_CHAIN.
3117 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
3118 permute statements for the SLP node NODE of the SLP instance
3119 SLP_NODE_INSTANCE. */
3122 vect_transform_slp_perm_load (slp_tree node
, vec
<tree
> dr_chain
,
3123 gimple_stmt_iterator
*gsi
, int vf
,
3124 slp_instance slp_node_instance
, bool analyze_only
)
3126 gimple stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3127 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3128 tree mask_element_type
= NULL_TREE
, mask_type
;
3129 int i
, j
, k
, nunits
, vec_index
= 0, scalar_index
;
3130 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3131 gimple next_scalar_stmt
;
3132 int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_node_instance
);
3133 int first_mask_element
;
3134 int index
, unroll_factor
, current_mask_element
, ncopies
;
3135 unsigned char *mask
;
3136 bool only_one_vec
= false, need_next_vector
= false;
3137 int first_vec_index
, second_vec_index
, orig_vec_stmts_num
, vect_stmts_counter
;
3138 int number_of_mask_fixes
= 1;
3139 bool mask_fixed
= false;
3140 bool needs_first_vector
= false;
3143 mode
= TYPE_MODE (vectype
);
3145 if (!can_vec_perm_p (mode
, false, NULL
))
3147 if (dump_enabled_p ())
3149 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3150 "no vect permute for ");
3151 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3152 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3157 /* The generic VEC_PERM_EXPR code always uses an integral type of the
3158 same size as the vector element being permuted. */
3159 mask_element_type
= lang_hooks
.types
.type_for_mode
3160 (int_mode_for_mode (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3161 mask_type
= get_vectype_for_scalar_type (mask_element_type
);
3162 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3163 mask
= XALLOCAVEC (unsigned char, nunits
);
3164 unroll_factor
= SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3166 /* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
3167 unrolling factor. */
3168 orig_vec_stmts_num
= group_size
*
3169 SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
) / nunits
;
3170 if (orig_vec_stmts_num
== 1)
3171 only_one_vec
= true;
3173 /* Number of copies is determined by the final vectorization factor
3174 relatively to SLP_NODE_INSTANCE unrolling factor. */
3175 ncopies
= vf
/ SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3177 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3180 /* Generate permutation masks for every NODE. Number of masks for each NODE
3181 is equal to GROUP_SIZE.
3182 E.g., we have a group of three nodes with three loads from the same
3183 location in each node, and the vector size is 4. I.e., we have a
3184 a0b0c0a1b1c1... sequence and we need to create the following vectors:
3185 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
3186 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
3189 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9}.
3190 The last mask is illegal since we assume two operands for permute
3191 operation, and the mask element values can't be outside that range.
3192 Hence, the last mask must be converted into {2,5,5,5}.
3193 For the first two permutations we need the first and the second input
3194 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
3195 we need the second and the third vectors: {b1,c1,a2,b2} and
3201 vect_stmts_counter
= 0;
3203 first_vec_index
= vec_index
++;
3205 second_vec_index
= first_vec_index
;
3207 second_vec_index
= vec_index
++;
3209 for (j
= 0; j
< unroll_factor
; j
++)
3211 for (k
= 0; k
< group_size
; k
++)
3213 i
= SLP_TREE_LOAD_PERMUTATION (node
)[k
];
3214 first_mask_element
= i
+ j
* group_size
;
3215 if (!vect_get_mask_element (stmt
, first_mask_element
, 0,
3216 nunits
, only_one_vec
, index
,
3217 mask
, ¤t_mask_element
,
3219 &number_of_mask_fixes
, &mask_fixed
,
3220 &needs_first_vector
))
3222 gcc_assert (current_mask_element
>= 0
3223 && current_mask_element
< 2 * nunits
);
3224 mask
[index
++] = current_mask_element
;
3226 if (index
== nunits
)
3229 if (!can_vec_perm_p (mode
, false, mask
))
3231 if (dump_enabled_p ())
3233 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
3235 "unsupported vect permute { ");
3236 for (i
= 0; i
< nunits
; ++i
)
3237 dump_printf (MSG_MISSED_OPTIMIZATION
, "%d ",
3239 dump_printf (MSG_MISSED_OPTIMIZATION
, "}\n");
3247 tree mask_vec
, *mask_elts
;
3248 mask_elts
= XALLOCAVEC (tree
, nunits
);
3249 for (l
= 0; l
< nunits
; ++l
)
3250 mask_elts
[l
] = build_int_cst (mask_element_type
,
3252 mask_vec
= build_vector (mask_type
, mask_elts
);
3254 if (need_next_vector
)
3256 first_vec_index
= second_vec_index
;
3257 second_vec_index
= vec_index
;
3261 = SLP_TREE_SCALAR_STMTS (node
)[scalar_index
++];
3263 vect_create_mask_and_perm (stmt
, next_scalar_stmt
,
3264 mask_vec
, first_vec_index
, second_vec_index
,
3265 gsi
, node
, vectype
, dr_chain
,
3266 ncopies
, vect_stmts_counter
++);
3278 /* Vectorize SLP instance tree in postorder. */
3281 vect_schedule_slp_instance (slp_tree node
, slp_instance instance
,
3282 unsigned int vectorization_factor
)
3285 bool grouped_store
, is_store
;
3286 gimple_stmt_iterator si
;
3287 stmt_vec_info stmt_info
;
3288 unsigned int vec_stmts_size
, nunits
, group_size
;
3296 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3297 vect_schedule_slp_instance (child
, instance
, vectorization_factor
);
3299 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3300 stmt_info
= vinfo_for_stmt (stmt
);
3302 /* VECTYPE is the type of the destination. */
3303 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3304 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (vectype
);
3305 group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
3307 /* For each SLP instance calculate number of vector stmts to be created
3308 for the scalar stmts in each node of the SLP tree. Number of vector
3309 elements in one vector iteration is the number of scalar elements in
3310 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
3312 vec_stmts_size
= (vectorization_factor
* group_size
) / nunits
;
3314 if (!SLP_TREE_VEC_STMTS (node
).exists ())
3316 SLP_TREE_VEC_STMTS (node
).create (vec_stmts_size
);
3317 SLP_TREE_NUMBER_OF_VEC_STMTS (node
) = vec_stmts_size
;
3320 if (dump_enabled_p ())
3322 dump_printf_loc (MSG_NOTE
,vect_location
,
3323 "------>vectorizing SLP node starting from: ");
3324 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3325 dump_printf (MSG_NOTE
, "\n");
3328 /* Vectorized stmts go before the last scalar stmt which is where
3329 all uses are ready. */
3330 si
= gsi_for_stmt (vect_find_last_scalar_stmt_in_slp (node
));
3332 /* Mark the first element of the reduction chain as reduction to properly
3333 transform the node. In the analysis phase only the last element of the
3334 chain is marked as reduction. */
3335 if (GROUP_FIRST_ELEMENT (stmt_info
) && !STMT_VINFO_GROUPED_ACCESS (stmt_info
)
3336 && GROUP_FIRST_ELEMENT (stmt_info
) == stmt
)
3338 STMT_VINFO_DEF_TYPE (stmt_info
) = vect_reduction_def
;
3339 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
3342 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3346 /* Replace scalar calls from SLP node NODE with setting of their lhs to zero.
3347 For loop vectorization this is done in vectorizable_call, but for SLP
3348 it needs to be deferred until end of vect_schedule_slp, because multiple
3349 SLP instances may refer to the same scalar stmt. */
3352 vect_remove_slp_scalar_calls (slp_tree node
)
3354 gimple stmt
, new_stmt
;
3355 gimple_stmt_iterator gsi
;
3359 stmt_vec_info stmt_info
;
3364 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3365 vect_remove_slp_scalar_calls (child
);
3367 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
3369 if (!is_gimple_call (stmt
) || gimple_bb (stmt
) == NULL
)
3371 stmt_info
= vinfo_for_stmt (stmt
);
3372 if (stmt_info
== NULL
3373 || is_pattern_stmt_p (stmt_info
)
3374 || !PURE_SLP_STMT (stmt_info
))
3376 lhs
= gimple_call_lhs (stmt
);
3377 new_stmt
= gimple_build_assign (lhs
, build_zero_cst (TREE_TYPE (lhs
)));
3378 set_vinfo_for_stmt (new_stmt
, stmt_info
);
3379 set_vinfo_for_stmt (stmt
, NULL
);
3380 STMT_VINFO_STMT (stmt_info
) = new_stmt
;
3381 gsi
= gsi_for_stmt (stmt
);
3382 gsi_replace (&gsi
, new_stmt
, false);
3383 SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt
)) = new_stmt
;
3387 /* Generate vector code for all SLP instances in the loop/basic block. */
3390 vect_schedule_slp (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
)
3392 vec
<slp_instance
> slp_instances
;
3393 slp_instance instance
;
3395 bool is_store
= false;
3399 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
3400 vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3404 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
3408 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3410 /* Schedule the tree of INSTANCE. */
3411 is_store
= vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance
),
3413 if (dump_enabled_p ())
3414 dump_printf_loc (MSG_NOTE
, vect_location
,
3415 "vectorizing stmts using SLP.\n");
3418 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3420 slp_tree root
= SLP_INSTANCE_TREE (instance
);
3423 gimple_stmt_iterator gsi
;
3425 /* Remove scalar call stmts. Do not do this for basic-block
3426 vectorization as not all uses may be vectorized.
3427 ??? Why should this be necessary? DCE should be able to
3428 remove the stmts itself.
3429 ??? For BB vectorization we can as well remove scalar
3430 stmts starting from the SLP tree root if they have no
3433 vect_remove_slp_scalar_calls (root
);
3435 for (j
= 0; SLP_TREE_SCALAR_STMTS (root
).iterate (j
, &store
)
3436 && j
< SLP_INSTANCE_GROUP_SIZE (instance
); j
++)
3438 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store
)))
3441 if (is_pattern_stmt_p (vinfo_for_stmt (store
)))
3442 store
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (store
));
3443 /* Free the attached stmt_vec_info and remove the stmt. */
3444 gsi
= gsi_for_stmt (store
);
3445 unlink_stmt_vdef (store
);
3446 gsi_remove (&gsi
, true);
3447 release_defs (store
);
3448 free_stmt_vec_info (store
);
3456 /* Vectorize the basic block. */
3459 vect_slp_transform_bb (basic_block bb
)
3461 bb_vec_info bb_vinfo
= vec_info_for_bb (bb
);
3462 gimple_stmt_iterator si
;
3464 gcc_assert (bb_vinfo
);
3466 if (dump_enabled_p ())
3467 dump_printf_loc (MSG_NOTE
, vect_location
, "SLPing BB\n");
3469 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
3471 gimple stmt
= gsi_stmt (si
);
3472 stmt_vec_info stmt_info
;
3474 if (dump_enabled_p ())
3476 dump_printf_loc (MSG_NOTE
, vect_location
,
3477 "------>SLPing statement: ");
3478 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3479 dump_printf (MSG_NOTE
, "\n");
3482 stmt_info
= vinfo_for_stmt (stmt
);
3483 gcc_assert (stmt_info
);
3485 /* Schedule all the SLP instances when the first SLP stmt is reached. */
3486 if (STMT_SLP_TYPE (stmt_info
))
3488 vect_schedule_slp (NULL
, bb_vinfo
);
3493 if (dump_enabled_p ())
3494 dump_printf_loc (MSG_NOTE
, vect_location
,
3495 "BASIC BLOCK VECTORIZED\n");
3497 destroy_bb_vec_info (bb_vinfo
);