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
)
227 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
235 /* Get the defs for the rhs of STMT (collect them in OPRNDS_INFO), check that
236 they are of a valid type and that they match the defs of the first stmt of
237 the SLP group (stored in OPRNDS_INFO). If there was a fatal error
238 return -1, if the error could be corrected by swapping operands of the
239 operation return 1, if everything is ok return 0. */
242 vect_get_and_check_slp_defs (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
243 gimple stmt
, bool first
,
244 vec
<slp_oprnd_info
> *oprnds_info
)
247 unsigned int i
, number_of_oprnds
;
250 enum vect_def_type dt
= vect_uninitialized_def
;
251 struct loop
*loop
= NULL
;
252 bool pattern
= false;
253 slp_oprnd_info oprnd_info
;
254 int first_op_idx
= 1;
255 bool commutative
= false;
256 bool first_op_cond
= false;
259 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
261 if (is_gimple_call (stmt
))
263 number_of_oprnds
= gimple_call_num_args (stmt
);
266 else if (is_gimple_assign (stmt
))
268 enum tree_code code
= gimple_assign_rhs_code (stmt
);
269 number_of_oprnds
= gimple_num_ops (stmt
) - 1;
270 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
272 first_op_cond
= true;
277 commutative
= commutative_tree_code (code
);
282 bool swapped
= false;
283 for (i
= 0; i
< number_of_oprnds
; i
++)
288 if (i
== 0 || i
== 1)
289 oprnd
= TREE_OPERAND (gimple_op (stmt
, first_op_idx
),
292 oprnd
= gimple_op (stmt
, first_op_idx
+ i
- 1);
295 oprnd
= gimple_op (stmt
, first_op_idx
+ (swapped
? !i
: i
));
297 oprnd_info
= (*oprnds_info
)[i
];
299 if (!vect_is_simple_use (oprnd
, NULL
, loop_vinfo
, bb_vinfo
, &def_stmt
,
301 || (!def_stmt
&& dt
!= vect_constant_def
))
303 if (dump_enabled_p ())
305 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
306 "Build SLP failed: can't find def for ");
307 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
308 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
314 /* Check if DEF_STMT is a part of a pattern in LOOP and get the def stmt
315 from the pattern. Check that all the stmts of the node are in the
317 if (def_stmt
&& gimple_bb (def_stmt
)
318 && ((loop
&& flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
)))
319 || (!loop
&& gimple_bb (def_stmt
) == BB_VINFO_BB (bb_vinfo
)
320 && gimple_code (def_stmt
) != GIMPLE_PHI
))
321 && vinfo_for_stmt (def_stmt
)
322 && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (def_stmt
))
323 && !STMT_VINFO_RELEVANT (vinfo_for_stmt (def_stmt
))
324 && !STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt
)))
327 if (!first
&& !oprnd_info
->first_pattern
)
337 if (dump_enabled_p ())
339 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
340 "Build SLP failed: some of the stmts"
341 " are in a pattern, and others are not ");
342 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
343 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
349 def_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
));
350 dt
= STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
));
352 if (dt
== vect_unknown_def_type
)
354 if (dump_enabled_p ())
355 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
356 "Unsupported pattern.\n");
360 switch (gimple_code (def_stmt
))
363 def
= gimple_phi_result (def_stmt
);
367 def
= gimple_assign_lhs (def_stmt
);
371 if (dump_enabled_p ())
372 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
373 "unsupported defining stmt:\n");
380 oprnd_info
->first_dt
= dt
;
381 oprnd_info
->first_pattern
= pattern
;
382 oprnd_info
->first_op_type
= TREE_TYPE (oprnd
);
386 /* Not first stmt of the group, check that the def-stmt/s match
387 the def-stmt/s of the first stmt. Allow different definition
388 types for reduction chains: the first stmt must be a
389 vect_reduction_def (a phi node), and the rest
390 vect_internal_def. */
391 if (((oprnd_info
->first_dt
!= dt
392 && !(oprnd_info
->first_dt
== vect_reduction_def
393 && dt
== vect_internal_def
)
394 && !((oprnd_info
->first_dt
== vect_external_def
395 || oprnd_info
->first_dt
== vect_constant_def
)
396 && (dt
== vect_external_def
397 || dt
== vect_constant_def
)))
398 || !types_compatible_p (oprnd_info
->first_op_type
,
401 /* Try swapping operands if we got a mismatch. */
410 if (dump_enabled_p ())
411 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
412 "Build SLP failed: different types\n");
418 /* Check the types of the definitions. */
421 case vect_constant_def
:
422 case vect_external_def
:
423 case vect_reduction_def
:
426 case vect_internal_def
:
427 oprnd_info
->def_stmts
.quick_push (def_stmt
);
431 /* FORNOW: Not supported. */
432 if (dump_enabled_p ())
434 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
435 "Build SLP failed: illegal type of def ");
436 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, def
);
437 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
449 tree cond
= gimple_assign_rhs1 (stmt
);
450 swap_ssa_operands (stmt
, &TREE_OPERAND (cond
, 0),
451 &TREE_OPERAND (cond
, 1));
452 TREE_SET_CODE (cond
, swap_tree_comparison (TREE_CODE (cond
)));
455 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
456 gimple_assign_rhs2_ptr (stmt
));
463 /* Verify if the scalar stmts STMTS are isomorphic, require data
464 permutation or are of unsupported types of operation. Return
465 true if they are, otherwise return false and indicate in *MATCHES
466 which stmts are not isomorphic to the first one. If MATCHES[0]
467 is false then this indicates the comparison could not be
468 carried out or the stmts will never be vectorized by SLP. */
471 vect_build_slp_tree_1 (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
472 vec
<gimple
> stmts
, unsigned int group_size
,
473 unsigned nops
, unsigned int *max_nunits
,
474 unsigned int vectorization_factor
, bool *matches
)
477 gimple stmt
= stmts
[0];
478 enum tree_code first_stmt_code
= ERROR_MARK
, rhs_code
= ERROR_MARK
;
479 enum tree_code first_cond_code
= ERROR_MARK
;
481 bool need_same_oprnds
= false;
482 tree vectype
, scalar_type
, first_op1
= NULL_TREE
;
485 machine_mode optab_op2_mode
;
486 machine_mode vec_mode
;
487 struct data_reference
*first_dr
;
489 gimple first_load
= NULL
, prev_first_load
= NULL
, old_first_load
= NULL
;
492 /* For every stmt in NODE find its def stmt/s. */
493 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
497 if (dump_enabled_p ())
499 dump_printf_loc (MSG_NOTE
, vect_location
, "Build SLP for ");
500 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
501 dump_printf (MSG_NOTE
, "\n");
504 /* Fail to vectorize statements marked as unvectorizable. */
505 if (!STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt
)))
507 if (dump_enabled_p ())
509 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
510 "Build SLP failed: unvectorizable statement ");
511 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
512 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
514 /* Fatal mismatch. */
519 lhs
= gimple_get_lhs (stmt
);
520 if (lhs
== NULL_TREE
)
522 if (dump_enabled_p ())
524 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
525 "Build SLP failed: not GIMPLE_ASSIGN nor "
527 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
528 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
530 /* Fatal mismatch. */
535 if (is_gimple_assign (stmt
)
536 && gimple_assign_rhs_code (stmt
) == COND_EXPR
537 && (cond
= gimple_assign_rhs1 (stmt
))
538 && !COMPARISON_CLASS_P (cond
))
540 if (dump_enabled_p ())
542 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
543 "Build SLP failed: condition is not "
545 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
546 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
548 /* Fatal mismatch. */
553 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
, &dummy
);
554 vectype
= get_vectype_for_scalar_type (scalar_type
);
557 if (dump_enabled_p ())
559 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
560 "Build SLP failed: unsupported data-type ");
561 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
563 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
565 /* Fatal mismatch. */
570 /* In case of multiple types we need to detect the smallest type. */
571 if (*max_nunits
< TYPE_VECTOR_SUBPARTS (vectype
))
573 *max_nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
575 vectorization_factor
= *max_nunits
;
578 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
580 rhs_code
= CALL_EXPR
;
581 if (gimple_call_internal_p (call_stmt
)
582 || gimple_call_tail_p (call_stmt
)
583 || gimple_call_noreturn_p (call_stmt
)
584 || !gimple_call_nothrow_p (call_stmt
)
585 || gimple_call_chain (call_stmt
))
587 if (dump_enabled_p ())
589 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
590 "Build SLP failed: unsupported call type ");
591 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
593 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
595 /* Fatal mismatch. */
601 rhs_code
= gimple_assign_rhs_code (stmt
);
603 /* Check the operation. */
606 first_stmt_code
= rhs_code
;
608 /* Shift arguments should be equal in all the packed stmts for a
609 vector shift with scalar shift operand. */
610 if (rhs_code
== LSHIFT_EXPR
|| rhs_code
== RSHIFT_EXPR
611 || rhs_code
== LROTATE_EXPR
612 || rhs_code
== RROTATE_EXPR
)
614 vec_mode
= TYPE_MODE (vectype
);
616 /* First see if we have a vector/vector shift. */
617 optab
= optab_for_tree_code (rhs_code
, vectype
,
621 || optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
623 /* No vector/vector shift, try for a vector/scalar shift. */
624 optab
= optab_for_tree_code (rhs_code
, vectype
,
629 if (dump_enabled_p ())
630 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
631 "Build SLP failed: no optab.\n");
632 /* Fatal mismatch. */
636 icode
= (int) optab_handler (optab
, vec_mode
);
637 if (icode
== CODE_FOR_nothing
)
639 if (dump_enabled_p ())
640 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
642 "op not supported by target.\n");
643 /* Fatal mismatch. */
647 optab_op2_mode
= insn_data
[icode
].operand
[2].mode
;
648 if (!VECTOR_MODE_P (optab_op2_mode
))
650 need_same_oprnds
= true;
651 first_op1
= gimple_assign_rhs2 (stmt
);
655 else if (rhs_code
== WIDEN_LSHIFT_EXPR
)
657 need_same_oprnds
= true;
658 first_op1
= gimple_assign_rhs2 (stmt
);
663 if (first_stmt_code
!= rhs_code
664 && (first_stmt_code
!= IMAGPART_EXPR
665 || rhs_code
!= REALPART_EXPR
)
666 && (first_stmt_code
!= REALPART_EXPR
667 || rhs_code
!= IMAGPART_EXPR
)
668 && !(STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
669 && (first_stmt_code
== ARRAY_REF
670 || first_stmt_code
== BIT_FIELD_REF
671 || first_stmt_code
== INDIRECT_REF
672 || first_stmt_code
== COMPONENT_REF
673 || first_stmt_code
== MEM_REF
)))
675 if (dump_enabled_p ())
677 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
678 "Build SLP failed: different operation "
680 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
681 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
688 && !operand_equal_p (first_op1
, gimple_assign_rhs2 (stmt
), 0))
690 if (dump_enabled_p ())
692 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
693 "Build SLP failed: different shift "
695 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
696 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
702 if (rhs_code
== CALL_EXPR
)
704 gimple first_stmt
= stmts
[0];
705 if (gimple_call_num_args (stmt
) != nops
706 || !operand_equal_p (gimple_call_fn (first_stmt
),
707 gimple_call_fn (stmt
), 0)
708 || gimple_call_fntype (first_stmt
)
709 != gimple_call_fntype (stmt
))
711 if (dump_enabled_p ())
713 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
714 "Build SLP failed: different calls in ");
715 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
717 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
725 /* Grouped store or load. */
726 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
728 if (REFERENCE_CLASS_P (lhs
))
736 unsigned unrolling_factor
737 = least_common_multiple
738 (*max_nunits
, group_size
) / group_size
;
739 /* FORNOW: Check that there is no gap between the loads
740 and no gap between the groups when we need to load
741 multiple groups at once.
742 ??? We should enhance this to only disallow gaps
744 if ((unrolling_factor
> 1
745 && ((GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) == stmt
746 && GROUP_GAP (vinfo_for_stmt (stmt
)) != 0)
747 /* If the group is split up then GROUP_GAP
748 isn't correct here, nor is GROUP_FIRST_ELEMENT. */
749 || GROUP_SIZE (vinfo_for_stmt (stmt
)) > group_size
))
750 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) != stmt
751 && GROUP_GAP (vinfo_for_stmt (stmt
)) != 1))
753 if (dump_enabled_p ())
755 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
756 "Build SLP failed: grouped "
758 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
760 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
762 /* Fatal mismatch. */
767 /* Check that the size of interleaved loads group is not
768 greater than the SLP group size. */
770 = vectorization_factor
/ TYPE_VECTOR_SUBPARTS (vectype
);
772 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) == stmt
773 && ((GROUP_SIZE (vinfo_for_stmt (stmt
))
774 - GROUP_GAP (vinfo_for_stmt (stmt
)))
775 > ncopies
* group_size
))
777 if (dump_enabled_p ())
779 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
780 "Build SLP failed: the number "
781 "of interleaved loads is greater than "
782 "the SLP group size ");
783 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
785 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
787 /* Fatal mismatch. */
792 old_first_load
= first_load
;
793 first_load
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
));
796 /* Check that there are no loads from different interleaving
797 chains in the same node. */
798 if (prev_first_load
!= first_load
)
800 if (dump_enabled_p ())
802 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
804 "Build SLP failed: different "
805 "interleaving chains in one node ");
806 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
808 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
815 prev_first_load
= first_load
;
817 /* In some cases a group of loads is just the same load
818 repeated N times. Only analyze its cost once. */
819 if (first_load
== stmt
&& old_first_load
!= first_load
)
821 first_dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
));
822 if (vect_supportable_dr_alignment (first_dr
, false)
823 == dr_unaligned_unsupported
)
825 if (dump_enabled_p ())
827 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
829 "Build SLP failed: unsupported "
831 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
833 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
835 /* Fatal mismatch. */
841 } /* Grouped access. */
844 if (TREE_CODE_CLASS (rhs_code
) == tcc_reference
)
846 /* Not grouped load. */
847 if (dump_enabled_p ())
849 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
850 "Build SLP failed: not grouped load ");
851 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
852 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
855 /* FORNOW: Not grouped loads are not supported. */
856 /* Fatal mismatch. */
861 /* Not memory operation. */
862 if (TREE_CODE_CLASS (rhs_code
) != tcc_binary
863 && TREE_CODE_CLASS (rhs_code
) != tcc_unary
864 && rhs_code
!= COND_EXPR
865 && rhs_code
!= CALL_EXPR
)
867 if (dump_enabled_p ())
869 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
870 "Build SLP failed: operation");
871 dump_printf (MSG_MISSED_OPTIMIZATION
, " unsupported ");
872 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
873 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
875 /* Fatal mismatch. */
880 if (rhs_code
== COND_EXPR
)
882 tree cond_expr
= gimple_assign_rhs1 (stmt
);
885 first_cond_code
= TREE_CODE (cond_expr
);
886 else if (first_cond_code
!= TREE_CODE (cond_expr
))
888 if (dump_enabled_p ())
890 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
891 "Build SLP failed: different"
893 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
895 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
906 for (i
= 0; i
< group_size
; ++i
)
913 /* Recursively build an SLP tree starting from NODE.
914 Fail (and return a value not equal to zero) if def-stmts are not
915 isomorphic, require data permutation or are of unsupported types of
916 operation. Otherwise, return 0.
917 The value returned is the depth in the SLP tree where a mismatch
921 vect_build_slp_tree (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
922 slp_tree
*node
, unsigned int group_size
,
923 unsigned int *max_nunits
,
924 vec
<slp_tree
> *loads
,
925 unsigned int vectorization_factor
,
926 bool *matches
, unsigned *npermutes
, unsigned *tree_size
,
927 unsigned max_tree_size
)
929 unsigned nops
, i
, this_tree_size
= 0;
934 stmt
= SLP_TREE_SCALAR_STMTS (*node
)[0];
935 if (is_gimple_call (stmt
))
936 nops
= gimple_call_num_args (stmt
);
937 else if (is_gimple_assign (stmt
))
939 nops
= gimple_num_ops (stmt
) - 1;
940 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
946 if (!vect_build_slp_tree_1 (loop_vinfo
, bb_vinfo
,
947 SLP_TREE_SCALAR_STMTS (*node
), group_size
, nops
,
948 max_nunits
, vectorization_factor
, matches
))
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
== 0), &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 oprnd_info
->def_stmts
= vNULL
;
1016 SLP_TREE_CHILDREN (*node
).quick_push (child
);
1020 /* If the SLP build for operand zero failed and operand zero
1021 and one can be commutated try that for the scalar stmts
1022 that failed the match. */
1024 /* A first scalar stmt mismatch signals a fatal mismatch. */
1026 /* ??? For COND_EXPRs we can swap the comparison operands
1027 as well as the arms under some constraints. */
1029 && oprnds_info
[1]->first_dt
== vect_internal_def
1030 && is_gimple_assign (stmt
)
1031 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
1032 /* Do so only if the number of not successful permutes was nor more
1033 than a cut-ff as re-trying the recursive match on
1034 possibly each level of the tree would expose exponential
1039 slp_tree grandchild
;
1042 *max_nunits
= old_max_nunits
;
1043 loads
->truncate (old_nloads
);
1044 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1045 vect_free_slp_tree (grandchild
);
1046 SLP_TREE_CHILDREN (child
).truncate (0);
1048 /* Swap mismatched definition stmts. */
1049 dump_printf_loc (MSG_NOTE
, vect_location
,
1050 "Re-trying with swapped operands of stmts ");
1051 for (j
= 0; j
< group_size
; ++j
)
1054 gimple tem
= oprnds_info
[0]->def_stmts
[j
];
1055 oprnds_info
[0]->def_stmts
[j
] = oprnds_info
[1]->def_stmts
[j
];
1056 oprnds_info
[1]->def_stmts
[j
] = tem
;
1057 dump_printf (MSG_NOTE
, "%d ", j
);
1059 dump_printf (MSG_NOTE
, "\n");
1060 /* And try again ... */
1061 if (vect_build_slp_tree (loop_vinfo
, bb_vinfo
, &child
,
1062 group_size
, max_nunits
, loads
,
1063 vectorization_factor
,
1064 matches
, npermutes
, &this_tree_size
,
1067 oprnd_info
->def_stmts
= vNULL
;
1068 SLP_TREE_CHILDREN (*node
).quick_push (child
);
1075 oprnd_info
->def_stmts
= vNULL
;
1076 vect_free_slp_tree (child
);
1077 vect_free_oprnd_info (oprnds_info
);
1082 *tree_size
+= this_tree_size
;
1084 vect_free_oprnd_info (oprnds_info
);
1088 /* Dump a slp tree NODE using flags specified in DUMP_KIND. */
1091 vect_print_slp_tree (int dump_kind
, slp_tree node
)
1100 dump_printf (dump_kind
, "node ");
1101 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1103 dump_printf (dump_kind
, "\n\tstmt %d ", i
);
1104 dump_gimple_stmt (dump_kind
, TDF_SLIM
, stmt
, 0);
1106 dump_printf (dump_kind
, "\n");
1108 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1109 vect_print_slp_tree (dump_kind
, child
);
1113 /* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
1114 If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
1115 J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
1116 stmts in NODE are to be marked. */
1119 vect_mark_slp_stmts (slp_tree node
, enum slp_vect_type mark
, int j
)
1128 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1129 if (j
< 0 || i
== j
)
1130 STMT_SLP_TYPE (vinfo_for_stmt (stmt
)) = mark
;
1132 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1133 vect_mark_slp_stmts (child
, mark
, j
);
1137 /* Mark the statements of the tree rooted at NODE as relevant (vect_used). */
1140 vect_mark_slp_stmts_relevant (slp_tree node
)
1144 stmt_vec_info stmt_info
;
1150 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1152 stmt_info
= vinfo_for_stmt (stmt
);
1153 gcc_assert (!STMT_VINFO_RELEVANT (stmt_info
)
1154 || STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
);
1155 STMT_VINFO_RELEVANT (stmt_info
) = vect_used_in_scope
;
1158 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1159 vect_mark_slp_stmts_relevant (child
);
1163 /* Rearrange the statements of NODE according to PERMUTATION. */
1166 vect_slp_rearrange_stmts (slp_tree node
, unsigned int group_size
,
1167 vec
<unsigned> permutation
)
1170 vec
<gimple
> tmp_stmts
;
1174 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1175 vect_slp_rearrange_stmts (child
, group_size
, permutation
);
1177 gcc_assert (group_size
== SLP_TREE_SCALAR_STMTS (node
).length ());
1178 tmp_stmts
.create (group_size
);
1179 tmp_stmts
.quick_grow_cleared (group_size
);
1181 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1182 tmp_stmts
[permutation
[i
]] = stmt
;
1184 SLP_TREE_SCALAR_STMTS (node
).release ();
1185 SLP_TREE_SCALAR_STMTS (node
) = tmp_stmts
;
1189 /* Check if the required load permutations in the SLP instance
1190 SLP_INSTN are supported. */
1193 vect_supported_load_permutation_p (slp_instance slp_instn
)
1195 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1196 unsigned int i
, j
, k
, next
;
1199 gimple stmt
, load
, next_load
, first_load
;
1200 struct data_reference
*dr
;
1202 if (dump_enabled_p ())
1204 dump_printf_loc (MSG_NOTE
, vect_location
, "Load permutation ");
1205 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1206 if (node
->load_permutation
.exists ())
1207 FOR_EACH_VEC_ELT (node
->load_permutation
, j
, next
)
1208 dump_printf (MSG_NOTE
, "%d ", next
);
1210 for (k
= 0; k
< group_size
; ++k
)
1211 dump_printf (MSG_NOTE
, "%d ", k
);
1212 dump_printf (MSG_NOTE
, "\n");
1215 /* In case of reduction every load permutation is allowed, since the order
1216 of the reduction statements is not important (as opposed to the case of
1217 grouped stores). The only condition we need to check is that all the
1218 load nodes are of the same size and have the same permutation (and then
1219 rearrange all the nodes of the SLP instance according to this
1222 /* Check that all the load nodes are of the same size. */
1223 /* ??? Can't we assert this? */
1224 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1225 if (SLP_TREE_SCALAR_STMTS (node
).length () != (unsigned) group_size
)
1228 node
= SLP_INSTANCE_TREE (slp_instn
);
1229 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1231 /* Reduction (there are no data-refs in the root).
1232 In reduction chain the order of the loads is important. */
1233 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))
1234 && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1239 /* Compare all the permutation sequences to the first one. We know
1240 that at least one load is permuted. */
1241 node
= SLP_INSTANCE_LOADS (slp_instn
)[0];
1242 if (!node
->load_permutation
.exists ())
1244 for (i
= 1; SLP_INSTANCE_LOADS (slp_instn
).iterate (i
, &load
); ++i
)
1246 if (!load
->load_permutation
.exists ())
1248 FOR_EACH_VEC_ELT (load
->load_permutation
, j
, lidx
)
1249 if (lidx
!= node
->load_permutation
[j
])
1253 /* Check that the loads in the first sequence are different and there
1254 are no gaps between them. */
1255 load_index
= sbitmap_alloc (group_size
);
1256 bitmap_clear (load_index
);
1257 FOR_EACH_VEC_ELT (node
->load_permutation
, i
, lidx
)
1259 if (bitmap_bit_p (load_index
, lidx
))
1261 sbitmap_free (load_index
);
1264 bitmap_set_bit (load_index
, lidx
);
1266 for (i
= 0; i
< group_size
; i
++)
1267 if (!bitmap_bit_p (load_index
, i
))
1269 sbitmap_free (load_index
);
1272 sbitmap_free (load_index
);
1274 /* This permutation is valid for reduction. Since the order of the
1275 statements in the nodes is not important unless they are memory
1276 accesses, we can rearrange the statements in all the nodes
1277 according to the order of the loads. */
1278 vect_slp_rearrange_stmts (SLP_INSTANCE_TREE (slp_instn
), group_size
,
1279 node
->load_permutation
);
1281 /* We are done, no actual permutations need to be generated. */
1282 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1283 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1287 /* In basic block vectorization we allow any subchain of an interleaving
1289 FORNOW: not supported in loop SLP because of realignment compications. */
1290 if (STMT_VINFO_BB_VINFO (vinfo_for_stmt (stmt
)))
1292 /* Check that for every node in the instance the loads
1294 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1297 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), j
, load
)
1299 if (j
!= 0 && next_load
!= load
)
1301 next_load
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (load
));
1305 /* Check that the alignment of the first load in every subchain, i.e.,
1306 the first statement in every load node, is supported.
1307 ??? This belongs in alignment checking. */
1308 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1310 first_load
= SLP_TREE_SCALAR_STMTS (node
)[0];
1311 if (first_load
!= GROUP_FIRST_ELEMENT (vinfo_for_stmt (first_load
)))
1313 dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (first_load
));
1314 if (vect_supportable_dr_alignment (dr
, false)
1315 == dr_unaligned_unsupported
)
1317 if (dump_enabled_p ())
1319 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
1321 "unsupported unaligned load ");
1322 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
1324 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1331 /* We are done, no actual permutations need to be generated. */
1332 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1333 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1337 /* FORNOW: the only supported permutation is 0..01..1.. of length equal to
1338 GROUP_SIZE and where each sequence of same drs is of GROUP_SIZE length as
1339 well (unless it's reduction). */
1340 if (SLP_INSTANCE_LOADS (slp_instn
).length () != group_size
)
1342 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1343 if (!node
->load_permutation
.exists ())
1346 load_index
= sbitmap_alloc (group_size
);
1347 bitmap_clear (load_index
);
1348 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1350 unsigned int lidx
= node
->load_permutation
[0];
1351 if (bitmap_bit_p (load_index
, lidx
))
1353 sbitmap_free (load_index
);
1356 bitmap_set_bit (load_index
, lidx
);
1357 FOR_EACH_VEC_ELT (node
->load_permutation
, j
, k
)
1360 sbitmap_free (load_index
);
1364 for (i
= 0; i
< group_size
; i
++)
1365 if (!bitmap_bit_p (load_index
, i
))
1367 sbitmap_free (load_index
);
1370 sbitmap_free (load_index
);
1372 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1373 if (node
->load_permutation
.exists ()
1374 && !vect_transform_slp_perm_load
1376 SLP_INSTANCE_UNROLLING_FACTOR (slp_instn
), slp_instn
, true))
1382 /* Find the last store in SLP INSTANCE. */
1385 vect_find_last_scalar_stmt_in_slp (slp_tree node
)
1387 gimple last
= NULL
, stmt
;
1389 for (int i
= 0; SLP_TREE_SCALAR_STMTS (node
).iterate (i
, &stmt
); i
++)
1391 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
1392 if (is_pattern_stmt_p (stmt_vinfo
))
1393 last
= get_later_stmt (STMT_VINFO_RELATED_STMT (stmt_vinfo
), last
);
1395 last
= get_later_stmt (stmt
, last
);
1401 /* Compute the cost for the SLP node NODE in the SLP instance INSTANCE. */
1404 vect_analyze_slp_cost_1 (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1405 slp_instance instance
, slp_tree node
,
1406 stmt_vector_for_cost
*prologue_cost_vec
,
1407 unsigned ncopies_for_cost
)
1409 stmt_vector_for_cost
*body_cost_vec
= &SLP_INSTANCE_BODY_COST_VEC (instance
);
1414 stmt_vec_info stmt_info
;
1416 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1418 /* Recurse down the SLP tree. */
1419 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1420 vect_analyze_slp_cost_1 (loop_vinfo
, bb_vinfo
,
1421 instance
, child
, prologue_cost_vec
,
1424 /* Look at the first scalar stmt to determine the cost. */
1425 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1426 stmt_info
= vinfo_for_stmt (stmt
);
1427 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1429 if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info
)))
1430 vect_model_store_cost (stmt_info
, ncopies_for_cost
, false,
1431 vect_uninitialized_def
,
1432 node
, prologue_cost_vec
, body_cost_vec
);
1436 gcc_checking_assert (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)));
1437 vect_model_load_cost (stmt_info
, ncopies_for_cost
, false,
1438 node
, prologue_cost_vec
, body_cost_vec
);
1439 /* If the load is permuted record the cost for the permutation.
1440 ??? Loads from multiple chains are let through here only
1441 for a single special case involving complex numbers where
1442 in the end no permutation is necessary. */
1443 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, s
)
1444 if ((STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo_for_stmt (s
))
1445 == STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
))
1446 && vect_get_place_in_interleaving_chain
1447 (s
, STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
)) != i
)
1449 record_stmt_cost (body_cost_vec
, group_size
, vec_perm
,
1450 stmt_info
, 0, vect_body
);
1456 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1457 stmt_info
, 0, vect_body
);
1459 /* Scan operands and account for prologue cost of constants/externals.
1460 ??? This over-estimates cost for multiple uses and should be
1462 lhs
= gimple_get_lhs (stmt
);
1463 for (i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1465 tree def
, op
= gimple_op (stmt
, i
);
1467 enum vect_def_type dt
;
1468 if (!op
|| op
== lhs
)
1470 if (vect_is_simple_use (op
, NULL
, loop_vinfo
, bb_vinfo
,
1471 &def_stmt
, &def
, &dt
))
1473 /* Without looking at the actual initializer a vector of
1474 constants can be implemented as load from the constant pool.
1475 ??? We need to pass down stmt_info for a vector type
1476 even if it points to the wrong stmt. */
1477 if (dt
== vect_constant_def
)
1478 record_stmt_cost (prologue_cost_vec
, 1, vector_load
,
1479 stmt_info
, 0, vect_prologue
);
1480 else if (dt
== vect_external_def
)
1481 record_stmt_cost (prologue_cost_vec
, 1, vec_construct
,
1482 stmt_info
, 0, vect_prologue
);
1487 /* Compute the cost for the SLP instance INSTANCE. */
1490 vect_analyze_slp_cost (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1491 slp_instance instance
, unsigned nunits
)
1493 stmt_vector_for_cost body_cost_vec
, prologue_cost_vec
;
1494 unsigned ncopies_for_cost
;
1495 stmt_info_for_cost
*si
;
1498 /* Calculate the number of vector stmts to create based on the unrolling
1499 factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
1500 GROUP_SIZE / NUNITS otherwise. */
1501 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1502 ncopies_for_cost
= least_common_multiple (nunits
, group_size
) / nunits
;
1504 prologue_cost_vec
.create (10);
1505 body_cost_vec
.create (10);
1506 SLP_INSTANCE_BODY_COST_VEC (instance
) = body_cost_vec
;
1507 vect_analyze_slp_cost_1 (loop_vinfo
, bb_vinfo
,
1508 instance
, SLP_INSTANCE_TREE (instance
),
1509 &prologue_cost_vec
, ncopies_for_cost
);
1511 /* Record the prologue costs, which were delayed until we were
1512 sure that SLP was successful. Unlike the body costs, we know
1513 the final values now regardless of the loop vectorization factor. */
1514 void *data
= (loop_vinfo
? LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
)
1515 : BB_VINFO_TARGET_COST_DATA (bb_vinfo
));
1516 FOR_EACH_VEC_ELT (prologue_cost_vec
, i
, si
)
1518 struct _stmt_vec_info
*stmt_info
1519 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1520 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1521 si
->misalign
, vect_prologue
);
1524 prologue_cost_vec
.release ();
1527 /* Analyze an SLP instance starting from a group of grouped stores. Call
1528 vect_build_slp_tree to build a tree of packed stmts if possible.
1529 Return FALSE if it's impossible to SLP any stmt in the loop. */
1532 vect_analyze_slp_instance (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1533 gimple stmt
, unsigned max_tree_size
)
1535 slp_instance new_instance
;
1537 unsigned int group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1538 unsigned int unrolling_factor
= 1, nunits
;
1539 tree vectype
, scalar_type
= NULL_TREE
;
1541 unsigned int vectorization_factor
= 0;
1543 unsigned int max_nunits
= 0;
1544 vec
<slp_tree
> loads
;
1545 struct data_reference
*dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
));
1546 vec
<gimple
> scalar_stmts
;
1548 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1552 scalar_type
= TREE_TYPE (DR_REF (dr
));
1553 vectype
= get_vectype_for_scalar_type (scalar_type
);
1557 gcc_assert (loop_vinfo
);
1558 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1561 group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1565 gcc_assert (loop_vinfo
);
1566 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1567 group_size
= LOOP_VINFO_REDUCTIONS (loop_vinfo
).length ();
1572 if (dump_enabled_p ())
1574 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1575 "Build SLP failed: unsupported data-type ");
1576 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, scalar_type
);
1577 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1583 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
1585 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1587 vectorization_factor
= nunits
;
1589 /* Calculate the unrolling factor. */
1590 unrolling_factor
= least_common_multiple (nunits
, group_size
) / group_size
;
1591 if (unrolling_factor
!= 1 && !loop_vinfo
)
1593 if (dump_enabled_p ())
1594 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1595 "Build SLP failed: unrolling required in basic"
1601 /* Create a node (a root of the SLP tree) for the packed grouped stores. */
1602 scalar_stmts
.create (group_size
);
1604 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1606 /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
1609 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next
))
1610 && STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)))
1611 scalar_stmts
.safe_push (
1612 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)));
1614 scalar_stmts
.safe_push (next
);
1615 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
1620 /* Collect reduction statements. */
1621 vec
<gimple
> reductions
= LOOP_VINFO_REDUCTIONS (loop_vinfo
);
1622 for (i
= 0; reductions
.iterate (i
, &next
); i
++)
1623 scalar_stmts
.safe_push (next
);
1626 node
= vect_create_new_slp_node (scalar_stmts
);
1628 loads
.create (group_size
);
1630 /* Build the tree for the SLP instance. */
1631 bool *matches
= XALLOCAVEC (bool, group_size
);
1632 unsigned npermutes
= 0;
1633 if (vect_build_slp_tree (loop_vinfo
, bb_vinfo
, &node
, group_size
,
1634 &max_nunits
, &loads
,
1635 vectorization_factor
, matches
, &npermutes
, NULL
,
1638 /* Calculate the unrolling factor based on the smallest type. */
1639 if (max_nunits
> nunits
)
1640 unrolling_factor
= least_common_multiple (max_nunits
, group_size
)
1643 if (unrolling_factor
!= 1 && !loop_vinfo
)
1645 if (dump_enabled_p ())
1646 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1647 "Build SLP failed: unrolling required in basic"
1649 vect_free_slp_tree (node
);
1654 /* Create a new SLP instance. */
1655 new_instance
= XNEW (struct _slp_instance
);
1656 SLP_INSTANCE_TREE (new_instance
) = node
;
1657 SLP_INSTANCE_GROUP_SIZE (new_instance
) = group_size
;
1658 SLP_INSTANCE_UNROLLING_FACTOR (new_instance
) = unrolling_factor
;
1659 SLP_INSTANCE_BODY_COST_VEC (new_instance
) = vNULL
;
1660 SLP_INSTANCE_LOADS (new_instance
) = loads
;
1662 /* Compute the load permutation. */
1664 bool loads_permuted
= false;
1665 FOR_EACH_VEC_ELT (loads
, i
, load_node
)
1667 vec
<unsigned> load_permutation
;
1669 gimple load
, first_stmt
;
1670 bool this_load_permuted
= false;
1671 load_permutation
.create (group_size
);
1672 first_stmt
= GROUP_FIRST_ELEMENT
1673 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node
)[0]));
1674 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node
), j
, load
)
1677 = vect_get_place_in_interleaving_chain (load
, first_stmt
);
1678 gcc_assert (load_place
!= -1);
1679 if (load_place
!= j
)
1680 this_load_permuted
= true;
1681 load_permutation
.safe_push (load_place
);
1683 if (!this_load_permuted
)
1685 load_permutation
.release ();
1688 SLP_TREE_LOAD_PERMUTATION (load_node
) = load_permutation
;
1689 loads_permuted
= true;
1694 if (!vect_supported_load_permutation_p (new_instance
))
1696 if (dump_enabled_p ())
1698 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1699 "Build SLP failed: unsupported load "
1701 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
1702 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1704 vect_free_slp_instance (new_instance
);
1712 /* Compute the costs of this SLP instance. Delay this for BB
1713 vectorization as we don't have vector types computed yet. */
1714 vect_analyze_slp_cost (loop_vinfo
, bb_vinfo
,
1715 new_instance
, TYPE_VECTOR_SUBPARTS (vectype
));
1716 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).safe_push (new_instance
);
1719 BB_VINFO_SLP_INSTANCES (bb_vinfo
).safe_push (new_instance
);
1721 if (dump_enabled_p ())
1722 vect_print_slp_tree (MSG_NOTE
, node
);
1727 /* Failed to SLP. */
1728 /* Free the allocated memory. */
1729 vect_free_slp_tree (node
);
1736 /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
1737 trees of packed scalar stmts if SLP is possible. */
1740 vect_analyze_slp (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1741 unsigned max_tree_size
)
1744 vec
<gimple
> grouped_stores
;
1745 vec
<gimple
> reductions
= vNULL
;
1746 vec
<gimple
> reduc_chains
= vNULL
;
1747 gimple first_element
;
1750 if (dump_enabled_p ())
1751 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_analyze_slp ===\n");
1755 grouped_stores
= LOOP_VINFO_GROUPED_STORES (loop_vinfo
);
1756 reduc_chains
= LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
);
1757 reductions
= LOOP_VINFO_REDUCTIONS (loop_vinfo
);
1760 grouped_stores
= BB_VINFO_GROUPED_STORES (bb_vinfo
);
1762 /* Find SLP sequences starting from groups of grouped stores. */
1763 FOR_EACH_VEC_ELT (grouped_stores
, i
, first_element
)
1764 if (vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, first_element
,
1768 if (bb_vinfo
&& !ok
)
1770 if (dump_enabled_p ())
1771 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1772 "Failed to SLP the basic block.\n");
1778 && LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
).length () > 0)
1780 /* Find SLP sequences starting from reduction chains. */
1781 FOR_EACH_VEC_ELT (reduc_chains
, i
, first_element
)
1782 if (vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, first_element
,
1788 /* Don't try to vectorize SLP reductions if reduction chain was
1793 /* Find SLP sequences starting from groups of reductions. */
1794 if (loop_vinfo
&& LOOP_VINFO_REDUCTIONS (loop_vinfo
).length () > 1
1795 && vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, reductions
[0],
1803 /* For each possible SLP instance decide whether to SLP it and calculate overall
1804 unrolling factor needed to SLP the loop. Return TRUE if decided to SLP at
1805 least one instance. */
1808 vect_make_slp_decision (loop_vec_info loop_vinfo
)
1810 unsigned int i
, unrolling_factor
= 1;
1811 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
1812 slp_instance instance
;
1813 int decided_to_slp
= 0;
1815 if (dump_enabled_p ())
1816 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_make_slp_decision ==="
1819 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
1821 /* FORNOW: SLP if you can. */
1822 if (unrolling_factor
< SLP_INSTANCE_UNROLLING_FACTOR (instance
))
1823 unrolling_factor
= SLP_INSTANCE_UNROLLING_FACTOR (instance
);
1825 /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
1826 call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
1827 loop-based vectorization. Such stmts will be marked as HYBRID. */
1828 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
1832 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
) = unrolling_factor
;
1834 if (decided_to_slp
&& dump_enabled_p ())
1835 dump_printf_loc (MSG_NOTE
, vect_location
,
1836 "Decided to SLP %d instances. Unrolling factor %d\n",
1837 decided_to_slp
, unrolling_factor
);
1839 return (decided_to_slp
> 0);
1843 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
1844 can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
1847 vect_detect_hybrid_slp_stmts (slp_tree node
, unsigned i
, slp_vect_type stype
)
1849 gimple stmt
= SLP_TREE_SCALAR_STMTS (node
)[i
];
1850 imm_use_iterator imm_iter
;
1852 stmt_vec_info use_vinfo
, stmt_vinfo
= vinfo_for_stmt (stmt
);
1854 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
1855 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1858 /* Propagate hybrid down the SLP tree. */
1859 if (stype
== hybrid
)
1861 else if (HYBRID_SLP_STMT (stmt_vinfo
))
1865 /* Check if a pure SLP stmt has uses in non-SLP stmts. */
1866 gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo
));
1867 if (TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
1868 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, gimple_op (stmt
, 0))
1869 if (gimple_bb (use_stmt
)
1870 && flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
))
1871 && (use_vinfo
= vinfo_for_stmt (use_stmt
))
1872 && !STMT_SLP_TYPE (use_vinfo
)
1873 && (STMT_VINFO_RELEVANT (use_vinfo
)
1874 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo
))
1875 || (STMT_VINFO_IN_PATTERN_P (use_vinfo
)
1876 && STMT_VINFO_RELATED_STMT (use_vinfo
)
1877 && !STMT_SLP_TYPE (vinfo_for_stmt
1878 (STMT_VINFO_RELATED_STMT (use_vinfo
)))))
1879 && !(gimple_code (use_stmt
) == GIMPLE_PHI
1880 && STMT_VINFO_DEF_TYPE (use_vinfo
) == vect_reduction_def
))
1884 if (stype
== hybrid
)
1885 STMT_SLP_TYPE (stmt_vinfo
) = hybrid
;
1887 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
1888 vect_detect_hybrid_slp_stmts (child
, i
, stype
);
1891 /* Helpers for vect_detect_hybrid_slp walking pattern stmt uses. */
1894 vect_detect_hybrid_slp_1 (tree
*tp
, int *, void *data
)
1896 walk_stmt_info
*wi
= (walk_stmt_info
*)data
;
1897 struct loop
*loopp
= (struct loop
*)wi
->info
;
1902 if (TREE_CODE (*tp
) == SSA_NAME
1903 && !SSA_NAME_IS_DEFAULT_DEF (*tp
))
1905 gimple def_stmt
= SSA_NAME_DEF_STMT (*tp
);
1906 if (flow_bb_inside_loop_p (loopp
, gimple_bb (def_stmt
))
1907 && PURE_SLP_STMT (vinfo_for_stmt (def_stmt
)))
1908 STMT_SLP_TYPE (vinfo_for_stmt (def_stmt
)) = hybrid
;
1915 vect_detect_hybrid_slp_2 (gimple_stmt_iterator
*gsi
, bool *handled
,
1918 /* If the stmt is in a SLP instance then this isn't a reason
1919 to mark use definitions in other SLP instances as hybrid. */
1920 if (STMT_SLP_TYPE (vinfo_for_stmt (gsi_stmt (*gsi
))) != loop_vect
)
1925 /* Find stmts that must be both vectorized and SLPed. */
1928 vect_detect_hybrid_slp (loop_vec_info loop_vinfo
)
1931 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
1932 slp_instance instance
;
1934 if (dump_enabled_p ())
1935 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_detect_hybrid_slp ==="
1938 /* First walk all pattern stmt in the loop and mark defs of uses as
1939 hybrid because immediate uses in them are not recorded. */
1940 for (i
= 0; i
< LOOP_VINFO_LOOP (loop_vinfo
)->num_nodes
; ++i
)
1942 basic_block bb
= LOOP_VINFO_BBS (loop_vinfo
)[i
];
1943 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1946 gimple stmt
= gsi_stmt (gsi
);
1947 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1948 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
1951 memset (&wi
, 0, sizeof (wi
));
1952 wi
.info
= LOOP_VINFO_LOOP (loop_vinfo
);
1953 gimple_stmt_iterator gsi2
1954 = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info
));
1955 walk_gimple_stmt (&gsi2
, vect_detect_hybrid_slp_2
,
1956 vect_detect_hybrid_slp_1
, &wi
);
1957 walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
),
1958 vect_detect_hybrid_slp_2
,
1959 vect_detect_hybrid_slp_1
, &wi
);
1964 /* Then walk the SLP instance trees marking stmts with uses in
1965 non-SLP stmts as hybrid, also propagating hybrid down the
1966 SLP tree, collecting the above info on-the-fly. */
1967 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
1969 for (unsigned i
= 0; i
< SLP_INSTANCE_GROUP_SIZE (instance
); ++i
)
1970 vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance
),
1976 /* Create and initialize a new bb_vec_info struct for BB, as well as
1977 stmt_vec_info structs for all the stmts in it. */
1980 new_bb_vec_info (basic_block bb
)
1982 bb_vec_info res
= NULL
;
1983 gimple_stmt_iterator gsi
;
1985 res
= (bb_vec_info
) xcalloc (1, sizeof (struct _bb_vec_info
));
1986 BB_VINFO_BB (res
) = bb
;
1988 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1990 gimple stmt
= gsi_stmt (gsi
);
1991 gimple_set_uid (stmt
, 0);
1992 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, NULL
, res
));
1995 BB_VINFO_GROUPED_STORES (res
).create (10);
1996 BB_VINFO_SLP_INSTANCES (res
).create (2);
1997 BB_VINFO_TARGET_COST_DATA (res
) = init_cost (NULL
);
2004 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
2005 stmts in the basic block. */
2008 destroy_bb_vec_info (bb_vec_info bb_vinfo
)
2010 vec
<slp_instance
> slp_instances
;
2011 slp_instance instance
;
2013 gimple_stmt_iterator si
;
2019 bb
= BB_VINFO_BB (bb_vinfo
);
2021 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2023 gimple stmt
= gsi_stmt (si
);
2024 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2027 /* Free stmt_vec_info. */
2028 free_stmt_vec_info (stmt
);
2031 vect_destroy_datarefs (NULL
, bb_vinfo
);
2032 free_dependence_relations (BB_VINFO_DDRS (bb_vinfo
));
2033 BB_VINFO_GROUPED_STORES (bb_vinfo
).release ();
2034 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2035 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2036 vect_free_slp_instance (instance
);
2037 BB_VINFO_SLP_INSTANCES (bb_vinfo
).release ();
2038 destroy_cost_data (BB_VINFO_TARGET_COST_DATA (bb_vinfo
));
2044 /* Analyze statements contained in SLP tree node after recursively analyzing
2045 the subtree. Return TRUE if the operations are supported. */
2048 vect_slp_analyze_node_operations (bb_vec_info bb_vinfo
, slp_tree node
)
2058 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2059 if (!vect_slp_analyze_node_operations (bb_vinfo
, child
))
2062 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2064 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2065 gcc_assert (stmt_info
);
2066 gcc_assert (PURE_SLP_STMT (stmt_info
));
2068 if (!vect_analyze_stmt (stmt
, &dummy
, node
))
2076 /* Analyze statements in SLP instances of the basic block. Return TRUE if the
2077 operations are supported. */
2080 vect_slp_analyze_operations (bb_vec_info bb_vinfo
)
2082 vec
<slp_instance
> slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2083 slp_instance instance
;
2086 for (i
= 0; slp_instances
.iterate (i
, &instance
); )
2088 if (!vect_slp_analyze_node_operations (bb_vinfo
,
2089 SLP_INSTANCE_TREE (instance
)))
2091 vect_free_slp_instance (instance
);
2092 slp_instances
.ordered_remove (i
);
2098 if (!slp_instances
.length ())
2105 /* Compute the scalar cost of the SLP node NODE and its children
2106 and return it. Do not account defs that are marked in LIFE and
2107 update LIFE according to uses of NODE. */
2110 vect_bb_slp_scalar_cost (basic_block bb
,
2111 slp_tree node
, vec
<bool, va_heap
> *life
)
2113 unsigned scalar_cost
= 0;
2118 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2121 ssa_op_iter op_iter
;
2122 def_operand_p def_p
;
2123 stmt_vec_info stmt_info
;
2128 /* If there is a non-vectorized use of the defs then the scalar
2129 stmt is kept live in which case we do not account it or any
2130 required defs in the SLP children in the scalar cost. This
2131 way we make the vectorization more costly when compared to
2133 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
2135 imm_use_iterator use_iter
;
2137 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, DEF_FROM_PTR (def_p
))
2138 if (!is_gimple_debug (use_stmt
)
2139 && (gimple_code (use_stmt
) == GIMPLE_PHI
2140 || gimple_bb (use_stmt
) != bb
2141 || !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (use_stmt
))))
2144 BREAK_FROM_IMM_USE_STMT (use_iter
);
2150 stmt_info
= vinfo_for_stmt (stmt
);
2151 if (STMT_VINFO_DATA_REF (stmt_info
))
2153 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)))
2154 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2156 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2159 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2161 scalar_cost
+= stmt_cost
;
2164 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2165 scalar_cost
+= vect_bb_slp_scalar_cost (bb
, child
, life
);
2170 /* Check if vectorization of the basic block is profitable. */
2173 vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo
)
2175 vec
<slp_instance
> slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2176 slp_instance instance
;
2178 unsigned int vec_inside_cost
= 0, vec_outside_cost
= 0, scalar_cost
= 0;
2179 unsigned int vec_prologue_cost
= 0, vec_epilogue_cost
= 0;
2180 void *target_cost_data
= BB_VINFO_TARGET_COST_DATA (bb_vinfo
);
2181 stmt_vec_info stmt_info
= NULL
;
2182 stmt_vector_for_cost body_cost_vec
;
2183 stmt_info_for_cost
*ci
;
2185 /* Calculate vector costs. */
2186 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2188 body_cost_vec
= SLP_INSTANCE_BODY_COST_VEC (instance
);
2190 FOR_EACH_VEC_ELT (body_cost_vec
, j
, ci
)
2192 stmt_info
= ci
->stmt
? vinfo_for_stmt (ci
->stmt
) : NULL
;
2193 (void) add_stmt_cost (target_cost_data
, ci
->count
, ci
->kind
,
2194 stmt_info
, ci
->misalign
, vect_body
);
2198 /* Calculate scalar cost. */
2199 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2201 auto_vec
<bool, 20> life
;
2202 life
.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance
));
2203 scalar_cost
+= vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo
),
2204 SLP_INSTANCE_TREE (instance
),
2208 /* Complete the target-specific cost calculation. */
2209 finish_cost (BB_VINFO_TARGET_COST_DATA (bb_vinfo
), &vec_prologue_cost
,
2210 &vec_inside_cost
, &vec_epilogue_cost
);
2212 vec_outside_cost
= vec_prologue_cost
+ vec_epilogue_cost
;
2214 if (dump_enabled_p ())
2216 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2217 dump_printf (MSG_NOTE
, " Vector inside of basic block cost: %d\n",
2219 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n", vec_prologue_cost
);
2220 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n", vec_epilogue_cost
);
2221 dump_printf (MSG_NOTE
, " Scalar cost of basic block: %d\n", scalar_cost
);
2224 /* Vectorization is profitable if its cost is less than the cost of scalar
2226 if (vec_outside_cost
+ vec_inside_cost
>= scalar_cost
)
2232 /* Check if the basic block can be vectorized. */
2235 vect_slp_analyze_bb_1 (basic_block bb
)
2237 bb_vec_info bb_vinfo
;
2238 vec
<slp_instance
> slp_instances
;
2239 slp_instance instance
;
2242 unsigned n_stmts
= 0;
2244 bb_vinfo
= new_bb_vec_info (bb
);
2248 if (!vect_analyze_data_refs (NULL
, bb_vinfo
, &min_vf
, &n_stmts
))
2250 if (dump_enabled_p ())
2251 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2252 "not vectorized: unhandled data-ref in basic "
2255 destroy_bb_vec_info (bb_vinfo
);
2259 if (BB_VINFO_DATAREFS (bb_vinfo
).length () < 2)
2261 if (dump_enabled_p ())
2262 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2263 "not vectorized: not enough data-refs in "
2266 destroy_bb_vec_info (bb_vinfo
);
2270 if (!vect_analyze_data_ref_accesses (NULL
, bb_vinfo
))
2272 if (dump_enabled_p ())
2273 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2274 "not vectorized: unhandled data access in "
2277 destroy_bb_vec_info (bb_vinfo
);
2281 vect_pattern_recog (NULL
, bb_vinfo
);
2283 if (!vect_analyze_data_refs_alignment (NULL
, bb_vinfo
))
2285 if (dump_enabled_p ())
2286 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2287 "not vectorized: bad data alignment in basic "
2290 destroy_bb_vec_info (bb_vinfo
);
2294 /* Check the SLP opportunities in the basic block, analyze and build SLP
2296 if (!vect_analyze_slp (NULL
, bb_vinfo
, n_stmts
))
2298 if (dump_enabled_p ())
2299 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2300 "not vectorized: failed to find SLP opportunities "
2301 "in basic block.\n");
2303 destroy_bb_vec_info (bb_vinfo
);
2307 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2309 /* Mark all the statements that we want to vectorize as pure SLP and
2311 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2313 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2314 vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance
));
2317 /* Mark all the statements that we do not want to vectorize. */
2318 for (gimple_stmt_iterator gsi
= gsi_start_bb (BB_VINFO_BB (bb_vinfo
));
2319 !gsi_end_p (gsi
); gsi_next (&gsi
))
2321 stmt_vec_info vinfo
= vinfo_for_stmt (gsi_stmt (gsi
));
2322 if (STMT_SLP_TYPE (vinfo
) != pure_slp
)
2323 STMT_VINFO_VECTORIZABLE (vinfo
) = false;
2326 /* Analyze dependences. At this point all stmts not participating in
2327 vectorization have to be marked. Dependence analysis assumes
2328 that we either vectorize all SLP instances or none at all. */
2329 if (!vect_slp_analyze_data_ref_dependences (bb_vinfo
))
2331 if (dump_enabled_p ())
2332 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2333 "not vectorized: unhandled data dependence "
2334 "in basic block.\n");
2336 destroy_bb_vec_info (bb_vinfo
);
2340 if (!vect_verify_datarefs_alignment (NULL
, bb_vinfo
))
2342 if (dump_enabled_p ())
2343 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2344 "not vectorized: unsupported alignment in basic "
2346 destroy_bb_vec_info (bb_vinfo
);
2350 if (!vect_slp_analyze_operations (bb_vinfo
))
2352 if (dump_enabled_p ())
2353 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2354 "not vectorized: bad operation in basic block.\n");
2356 destroy_bb_vec_info (bb_vinfo
);
2360 /* Compute the costs of the SLP instances. */
2361 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2363 gimple stmt
= SLP_TREE_SCALAR_STMTS (SLP_INSTANCE_TREE (instance
))[0];
2364 tree vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
2365 vect_analyze_slp_cost (NULL
, bb_vinfo
,
2366 instance
, TYPE_VECTOR_SUBPARTS (vectype
));
2369 /* Cost model: check if the vectorization is worthwhile. */
2370 if (!unlimited_cost_model (NULL
)
2371 && !vect_bb_vectorization_profitable_p (bb_vinfo
))
2373 if (dump_enabled_p ())
2374 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2375 "not vectorized: vectorization is not "
2378 destroy_bb_vec_info (bb_vinfo
);
2382 if (dump_enabled_p ())
2383 dump_printf_loc (MSG_NOTE
, vect_location
,
2384 "Basic block will be vectorized using SLP\n");
2391 vect_slp_analyze_bb (basic_block bb
)
2393 bb_vec_info bb_vinfo
;
2395 gimple_stmt_iterator gsi
;
2396 unsigned int vector_sizes
;
2398 if (dump_enabled_p ())
2399 dump_printf_loc (MSG_NOTE
, vect_location
, "===vect_slp_analyze_bb===\n");
2401 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2403 gimple stmt
= gsi_stmt (gsi
);
2404 if (!is_gimple_debug (stmt
)
2405 && !gimple_nop_p (stmt
)
2406 && gimple_code (stmt
) != GIMPLE_LABEL
)
2410 if (insns
> PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB
))
2412 if (dump_enabled_p ())
2413 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2414 "not vectorized: too many instructions in "
2420 /* Autodetect first vector size we try. */
2421 current_vector_size
= 0;
2422 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2426 bb_vinfo
= vect_slp_analyze_bb_1 (bb
);
2430 destroy_bb_vec_info (bb_vinfo
);
2432 vector_sizes
&= ~current_vector_size
;
2433 if (vector_sizes
== 0
2434 || current_vector_size
== 0)
2437 /* Try the next biggest vector size. */
2438 current_vector_size
= 1 << floor_log2 (vector_sizes
);
2439 if (dump_enabled_p ())
2440 dump_printf_loc (MSG_NOTE
, vect_location
,
2441 "***** Re-trying analysis with "
2442 "vector size %d\n", current_vector_size
);
2447 /* SLP costs are calculated according to SLP instance unrolling factor (i.e.,
2448 the number of created vector stmts depends on the unrolling factor).
2449 However, the actual number of vector stmts for every SLP node depends on
2450 VF which is set later in vect_analyze_operations (). Hence, SLP costs
2451 should be updated. In this function we assume that the inside costs
2452 calculated in vect_model_xxx_cost are linear in ncopies. */
2455 vect_update_slp_costs_according_to_vf (loop_vec_info loop_vinfo
)
2457 unsigned int i
, j
, vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2458 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2459 slp_instance instance
;
2460 stmt_vector_for_cost body_cost_vec
;
2461 stmt_info_for_cost
*si
;
2462 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2464 if (dump_enabled_p ())
2465 dump_printf_loc (MSG_NOTE
, vect_location
,
2466 "=== vect_update_slp_costs_according_to_vf ===\n");
2468 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2470 /* We assume that costs are linear in ncopies. */
2471 int ncopies
= vf
/ SLP_INSTANCE_UNROLLING_FACTOR (instance
);
2473 /* Record the instance's instructions in the target cost model.
2474 This was delayed until here because the count of instructions
2475 isn't known beforehand. */
2476 body_cost_vec
= SLP_INSTANCE_BODY_COST_VEC (instance
);
2478 FOR_EACH_VEC_ELT (body_cost_vec
, j
, si
)
2479 (void) add_stmt_cost (data
, si
->count
* ncopies
, si
->kind
,
2480 vinfo_for_stmt (si
->stmt
), si
->misalign
,
2486 /* For constant and loop invariant defs of SLP_NODE this function returns
2487 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
2488 OP_NUM determines if we gather defs for operand 0 or operand 1 of the RHS of
2489 scalar stmts. NUMBER_OF_VECTORS is the number of vector defs to create.
2490 REDUC_INDEX is the index of the reduction operand in the statements, unless
2494 vect_get_constant_vectors (tree op
, slp_tree slp_node
,
2495 vec
<tree
> *vec_oprnds
,
2496 unsigned int op_num
, unsigned int number_of_vectors
,
2499 vec
<gimple
> stmts
= SLP_TREE_SCALAR_STMTS (slp_node
);
2500 gimple stmt
= stmts
[0];
2501 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2505 unsigned j
, number_of_places_left_in_vector
;
2508 int group_size
= stmts
.length ();
2509 unsigned int vec_num
, i
;
2510 unsigned number_of_copies
= 1;
2512 voprnds
.create (number_of_vectors
);
2513 bool constant_p
, is_store
;
2514 tree neutral_op
= NULL
;
2515 enum tree_code code
= gimple_expr_code (stmt
);
2518 gimple_seq ctor_seq
= NULL
;
2520 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_reduction_def
2521 && reduc_index
!= -1)
2523 op_num
= reduc_index
- 1;
2524 op
= gimple_op (stmt
, reduc_index
);
2525 /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
2526 we need either neutral operands or the original operands. See
2527 get_initial_def_for_reduction() for details. */
2530 case WIDEN_SUM_EXPR
:
2536 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2537 neutral_op
= build_real (TREE_TYPE (op
), dconst0
);
2539 neutral_op
= build_int_cst (TREE_TYPE (op
), 0);
2544 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2545 neutral_op
= build_real (TREE_TYPE (op
), dconst1
);
2547 neutral_op
= build_int_cst (TREE_TYPE (op
), 1);
2552 neutral_op
= build_int_cst (TREE_TYPE (op
), -1);
2555 /* For MIN/MAX we don't have an easy neutral operand but
2556 the initial values can be used fine here. Only for
2557 a reduction chain we have to force a neutral element. */
2560 if (!GROUP_FIRST_ELEMENT (stmt_vinfo
))
2564 def_stmt
= SSA_NAME_DEF_STMT (op
);
2565 loop
= (gimple_bb (stmt
))->loop_father
;
2566 neutral_op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2567 loop_preheader_edge (loop
));
2576 if (STMT_VINFO_DATA_REF (stmt_vinfo
))
2579 op
= gimple_assign_rhs1 (stmt
);
2586 if (CONSTANT_CLASS_P (op
))
2591 vector_type
= get_vectype_for_scalar_type (TREE_TYPE (op
));
2592 gcc_assert (vector_type
);
2593 nunits
= TYPE_VECTOR_SUBPARTS (vector_type
);
2595 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
2596 created vectors. It is greater than 1 if unrolling is performed.
2598 For example, we have two scalar operands, s1 and s2 (e.g., group of
2599 strided accesses of size two), while NUNITS is four (i.e., four scalars
2600 of this type can be packed in a vector). The output vector will contain
2601 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
2604 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
2605 containing the operands.
2607 For example, NUNITS is four as before, and the group size is 8
2608 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
2609 {s5, s6, s7, s8}. */
2611 number_of_copies
= least_common_multiple (nunits
, group_size
) / group_size
;
2613 number_of_places_left_in_vector
= nunits
;
2614 elts
= XALLOCAVEC (tree
, nunits
);
2615 for (j
= 0; j
< number_of_copies
; j
++)
2617 for (i
= group_size
- 1; stmts
.iterate (i
, &stmt
); i
--)
2620 op
= gimple_assign_rhs1 (stmt
);
2626 if (op_num
== 0 || op_num
== 1)
2628 tree cond
= gimple_assign_rhs1 (stmt
);
2629 op
= TREE_OPERAND (cond
, op_num
);
2634 op
= gimple_assign_rhs2 (stmt
);
2636 op
= gimple_assign_rhs3 (stmt
);
2641 op
= gimple_call_arg (stmt
, op_num
);
2648 op
= gimple_op (stmt
, op_num
+ 1);
2649 /* Unlike the other binary operators, shifts/rotates have
2650 the shift count being int, instead of the same type as
2651 the lhs, so make sure the scalar is the right type if
2652 we are dealing with vectors of
2653 long long/long/short/char. */
2654 if (op_num
== 1 && TREE_CODE (op
) == INTEGER_CST
)
2655 op
= fold_convert (TREE_TYPE (vector_type
), op
);
2659 op
= gimple_op (stmt
, op_num
+ 1);
2664 if (reduc_index
!= -1)
2666 loop
= (gimple_bb (stmt
))->loop_father
;
2667 def_stmt
= SSA_NAME_DEF_STMT (op
);
2671 /* Get the def before the loop. In reduction chain we have only
2672 one initial value. */
2673 if ((j
!= (number_of_copies
- 1)
2674 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
2679 op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2680 loop_preheader_edge (loop
));
2683 /* Create 'vect_ = {op0,op1,...,opn}'. */
2684 number_of_places_left_in_vector
--;
2685 if (!types_compatible_p (TREE_TYPE (vector_type
), TREE_TYPE (op
)))
2687 if (CONSTANT_CLASS_P (op
))
2689 op
= fold_unary (VIEW_CONVERT_EXPR
,
2690 TREE_TYPE (vector_type
), op
);
2691 gcc_assert (op
&& CONSTANT_CLASS_P (op
));
2695 tree new_temp
= make_ssa_name (TREE_TYPE (vector_type
));
2697 op
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (vector_type
), op
);
2699 = gimple_build_assign (new_temp
, VIEW_CONVERT_EXPR
, op
);
2700 gimple_seq_add_stmt (&ctor_seq
, init_stmt
);
2704 elts
[number_of_places_left_in_vector
] = op
;
2705 if (!CONSTANT_CLASS_P (op
))
2708 if (number_of_places_left_in_vector
== 0)
2710 number_of_places_left_in_vector
= nunits
;
2713 vec_cst
= build_vector (vector_type
, elts
);
2716 vec
<constructor_elt
, va_gc
> *v
;
2718 vec_alloc (v
, nunits
);
2719 for (k
= 0; k
< nunits
; ++k
)
2720 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[k
]);
2721 vec_cst
= build_constructor (vector_type
, v
);
2723 voprnds
.quick_push (vect_init_vector (stmt
, vec_cst
,
2724 vector_type
, NULL
));
2725 if (ctor_seq
!= NULL
)
2727 gimple init_stmt
= SSA_NAME_DEF_STMT (voprnds
.last ());
2728 gimple_stmt_iterator gsi
= gsi_for_stmt (init_stmt
);
2729 gsi_insert_seq_before_without_update (&gsi
, ctor_seq
,
2737 /* Since the vectors are created in the reverse order, we should invert
2739 vec_num
= voprnds
.length ();
2740 for (j
= vec_num
; j
!= 0; j
--)
2742 vop
= voprnds
[j
- 1];
2743 vec_oprnds
->quick_push (vop
);
2748 /* In case that VF is greater than the unrolling factor needed for the SLP
2749 group of stmts, NUMBER_OF_VECTORS to be created is greater than
2750 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
2751 to replicate the vectors. */
2752 while (number_of_vectors
> vec_oprnds
->length ())
2754 tree neutral_vec
= NULL
;
2759 neutral_vec
= build_vector_from_val (vector_type
, neutral_op
);
2761 vec_oprnds
->quick_push (neutral_vec
);
2765 for (i
= 0; vec_oprnds
->iterate (i
, &vop
) && i
< vec_num
; i
++)
2766 vec_oprnds
->quick_push (vop
);
2772 /* Get vectorized definitions from SLP_NODE that contains corresponding
2773 vectorized def-stmts. */
2776 vect_get_slp_vect_defs (slp_tree slp_node
, vec
<tree
> *vec_oprnds
)
2779 gimple vec_def_stmt
;
2782 gcc_assert (SLP_TREE_VEC_STMTS (slp_node
).exists ());
2784 FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (slp_node
), i
, vec_def_stmt
)
2786 gcc_assert (vec_def_stmt
);
2787 vec_oprnd
= gimple_get_lhs (vec_def_stmt
);
2788 vec_oprnds
->quick_push (vec_oprnd
);
2793 /* Get vectorized definitions for SLP_NODE.
2794 If the scalar definitions are loop invariants or constants, collect them and
2795 call vect_get_constant_vectors() to create vector stmts.
2796 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
2797 must be stored in the corresponding child of SLP_NODE, and we call
2798 vect_get_slp_vect_defs () to retrieve them. */
2801 vect_get_slp_defs (vec
<tree
> ops
, slp_tree slp_node
,
2802 vec
<vec
<tree
> > *vec_oprnds
, int reduc_index
)
2805 int number_of_vects
= 0, i
;
2806 unsigned int child_index
= 0;
2807 HOST_WIDE_INT lhs_size_unit
, rhs_size_unit
;
2808 slp_tree child
= NULL
;
2811 bool vectorized_defs
;
2813 first_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[0];
2814 FOR_EACH_VEC_ELT (ops
, i
, oprnd
)
2816 /* For each operand we check if it has vectorized definitions in a child
2817 node or we need to create them (for invariants and constants). We
2818 check if the LHS of the first stmt of the next child matches OPRND.
2819 If it does, we found the correct child. Otherwise, we call
2820 vect_get_constant_vectors (), and not advance CHILD_INDEX in order
2821 to check this child node for the next operand. */
2822 vectorized_defs
= false;
2823 if (SLP_TREE_CHILDREN (slp_node
).length () > child_index
)
2825 child
= SLP_TREE_CHILDREN (slp_node
)[child_index
];
2827 /* We have to check both pattern and original def, if available. */
2828 gimple first_def
= SLP_TREE_SCALAR_STMTS (child
)[0];
2829 gimple related
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def
));
2831 if (operand_equal_p (oprnd
, gimple_get_lhs (first_def
), 0)
2833 && operand_equal_p (oprnd
, gimple_get_lhs (related
), 0)))
2835 /* The number of vector defs is determined by the number of
2836 vector statements in the node from which we get those
2838 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (child
);
2839 vectorized_defs
= true;
2844 if (!vectorized_defs
)
2848 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
2849 /* Number of vector stmts was calculated according to LHS in
2850 vect_schedule_slp_instance (), fix it by replacing LHS with
2851 RHS, if necessary. See vect_get_smallest_scalar_type () for
2853 vect_get_smallest_scalar_type (first_stmt
, &lhs_size_unit
,
2855 if (rhs_size_unit
!= lhs_size_unit
)
2857 number_of_vects
*= rhs_size_unit
;
2858 number_of_vects
/= lhs_size_unit
;
2863 /* Allocate memory for vectorized defs. */
2865 vec_defs
.create (number_of_vects
);
2867 /* For reduction defs we call vect_get_constant_vectors (), since we are
2868 looking for initial loop invariant values. */
2869 if (vectorized_defs
&& reduc_index
== -1)
2870 /* The defs are already vectorized. */
2871 vect_get_slp_vect_defs (child
, &vec_defs
);
2873 /* Build vectors from scalar defs. */
2874 vect_get_constant_vectors (oprnd
, slp_node
, &vec_defs
, i
,
2875 number_of_vects
, reduc_index
);
2877 vec_oprnds
->quick_push (vec_defs
);
2879 /* For reductions, we only need initial values. */
2880 if (reduc_index
!= -1)
2886 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
2887 building a vector of type MASK_TYPE from it) and two input vectors placed in
2888 DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
2889 shifting by STRIDE elements of DR_CHAIN for every copy.
2890 (STRIDE is the number of vectorized stmts for NODE divided by the number of
2892 VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
2893 the created stmts must be inserted. */
2896 vect_create_mask_and_perm (gimple stmt
, gimple next_scalar_stmt
,
2897 tree mask
, int first_vec_indx
, int second_vec_indx
,
2898 gimple_stmt_iterator
*gsi
, slp_tree node
,
2899 tree vectype
, vec
<tree
> dr_chain
,
2900 int ncopies
, int vect_stmts_counter
)
2903 gimple perm_stmt
= NULL
;
2904 stmt_vec_info next_stmt_info
;
2906 tree first_vec
, second_vec
, data_ref
;
2908 stride
= SLP_TREE_NUMBER_OF_VEC_STMTS (node
) / ncopies
;
2910 /* Initialize the vect stmts of NODE to properly insert the generated
2912 for (i
= SLP_TREE_VEC_STMTS (node
).length ();
2913 i
< (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node
); i
++)
2914 SLP_TREE_VEC_STMTS (node
).quick_push (NULL
);
2916 perm_dest
= vect_create_destination_var (gimple_assign_lhs (stmt
), vectype
);
2917 for (i
= 0; i
< ncopies
; i
++)
2919 first_vec
= dr_chain
[first_vec_indx
];
2920 second_vec
= dr_chain
[second_vec_indx
];
2922 /* Generate the permute statement. */
2923 perm_stmt
= gimple_build_assign (perm_dest
, VEC_PERM_EXPR
,
2924 first_vec
, second_vec
, mask
);
2925 data_ref
= make_ssa_name (perm_dest
, perm_stmt
);
2926 gimple_set_lhs (perm_stmt
, data_ref
);
2927 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
2929 /* Store the vector statement in NODE. */
2930 SLP_TREE_VEC_STMTS (node
)[stride
* i
+ vect_stmts_counter
] = perm_stmt
;
2932 first_vec_indx
+= stride
;
2933 second_vec_indx
+= stride
;
2936 /* Mark the scalar stmt as vectorized. */
2937 next_stmt_info
= vinfo_for_stmt (next_scalar_stmt
);
2938 STMT_VINFO_VEC_STMT (next_stmt_info
) = perm_stmt
;
2942 /* Given FIRST_MASK_ELEMENT - the mask element in element representation,
2943 return in CURRENT_MASK_ELEMENT its equivalent in target specific
2944 representation. Check that the mask is valid and return FALSE if not.
2945 Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
2946 the next vector, i.e., the current first vector is not needed. */
2949 vect_get_mask_element (gimple stmt
, int first_mask_element
, int m
,
2950 int mask_nunits
, bool only_one_vec
, int index
,
2951 unsigned char *mask
, int *current_mask_element
,
2952 bool *need_next_vector
, int *number_of_mask_fixes
,
2953 bool *mask_fixed
, bool *needs_first_vector
)
2957 /* Convert to target specific representation. */
2958 *current_mask_element
= first_mask_element
+ m
;
2959 /* Adjust the value in case it's a mask for second and third vectors. */
2960 *current_mask_element
-= mask_nunits
* (*number_of_mask_fixes
- 1);
2962 if (*current_mask_element
< mask_nunits
)
2963 *needs_first_vector
= true;
2965 /* We have only one input vector to permute but the mask accesses values in
2966 the next vector as well. */
2967 if (only_one_vec
&& *current_mask_element
>= mask_nunits
)
2969 if (dump_enabled_p ())
2971 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2972 "permutation requires at least two vectors ");
2973 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
2974 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2980 /* The mask requires the next vector. */
2981 while (*current_mask_element
>= mask_nunits
* 2)
2983 if (*needs_first_vector
|| *mask_fixed
)
2985 /* We either need the first vector too or have already moved to the
2986 next vector. In both cases, this permutation needs three
2988 if (dump_enabled_p ())
2990 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2991 "permutation requires at "
2992 "least three vectors ");
2993 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
2994 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3000 /* We move to the next vector, dropping the first one and working with
3001 the second and the third - we need to adjust the values of the mask
3003 *current_mask_element
-= mask_nunits
* *number_of_mask_fixes
;
3005 for (i
= 0; i
< index
; i
++)
3006 mask
[i
] -= mask_nunits
* *number_of_mask_fixes
;
3008 (*number_of_mask_fixes
)++;
3012 *need_next_vector
= *mask_fixed
;
3014 /* This was the last element of this mask. Start a new one. */
3015 if (index
== mask_nunits
- 1)
3017 *number_of_mask_fixes
= 1;
3018 *mask_fixed
= false;
3019 *needs_first_vector
= false;
3026 /* Generate vector permute statements from a list of loads in DR_CHAIN.
3027 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
3028 permute statements for the SLP node NODE of the SLP instance
3029 SLP_NODE_INSTANCE. */
3032 vect_transform_slp_perm_load (slp_tree node
, vec
<tree
> dr_chain
,
3033 gimple_stmt_iterator
*gsi
, int vf
,
3034 slp_instance slp_node_instance
, bool analyze_only
)
3036 gimple stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3037 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3038 tree mask_element_type
= NULL_TREE
, mask_type
;
3039 int i
, j
, k
, nunits
, vec_index
= 0, scalar_index
;
3040 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3041 gimple next_scalar_stmt
;
3042 int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_node_instance
);
3043 int first_mask_element
;
3044 int index
, unroll_factor
, current_mask_element
, ncopies
;
3045 unsigned char *mask
;
3046 bool only_one_vec
= false, need_next_vector
= false;
3047 int first_vec_index
, second_vec_index
, orig_vec_stmts_num
, vect_stmts_counter
;
3048 int number_of_mask_fixes
= 1;
3049 bool mask_fixed
= false;
3050 bool needs_first_vector
= false;
3053 mode
= TYPE_MODE (vectype
);
3055 if (!can_vec_perm_p (mode
, false, NULL
))
3057 if (dump_enabled_p ())
3059 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3060 "no vect permute for ");
3061 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3062 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3067 /* The generic VEC_PERM_EXPR code always uses an integral type of the
3068 same size as the vector element being permuted. */
3069 mask_element_type
= lang_hooks
.types
.type_for_mode
3070 (int_mode_for_mode (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3071 mask_type
= get_vectype_for_scalar_type (mask_element_type
);
3072 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3073 mask
= XALLOCAVEC (unsigned char, nunits
);
3074 unroll_factor
= SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3076 /* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
3077 unrolling factor. */
3078 orig_vec_stmts_num
= group_size
*
3079 SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
) / nunits
;
3080 if (orig_vec_stmts_num
== 1)
3081 only_one_vec
= true;
3083 /* Number of copies is determined by the final vectorization factor
3084 relatively to SLP_NODE_INSTANCE unrolling factor. */
3085 ncopies
= vf
/ SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3087 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3090 /* Generate permutation masks for every NODE. Number of masks for each NODE
3091 is equal to GROUP_SIZE.
3092 E.g., we have a group of three nodes with three loads from the same
3093 location in each node, and the vector size is 4. I.e., we have a
3094 a0b0c0a1b1c1... sequence and we need to create the following vectors:
3095 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
3096 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
3099 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9}.
3100 The last mask is illegal since we assume two operands for permute
3101 operation, and the mask element values can't be outside that range.
3102 Hence, the last mask must be converted into {2,5,5,5}.
3103 For the first two permutations we need the first and the second input
3104 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
3105 we need the second and the third vectors: {b1,c1,a2,b2} and
3111 vect_stmts_counter
= 0;
3113 first_vec_index
= vec_index
++;
3115 second_vec_index
= first_vec_index
;
3117 second_vec_index
= vec_index
++;
3119 for (j
= 0; j
< unroll_factor
; j
++)
3121 for (k
= 0; k
< group_size
; k
++)
3123 i
= SLP_TREE_LOAD_PERMUTATION (node
)[k
];
3124 first_mask_element
= i
+ j
* group_size
;
3125 if (!vect_get_mask_element (stmt
, first_mask_element
, 0,
3126 nunits
, only_one_vec
, index
,
3127 mask
, ¤t_mask_element
,
3129 &number_of_mask_fixes
, &mask_fixed
,
3130 &needs_first_vector
))
3132 gcc_assert (current_mask_element
< 2 * nunits
);
3133 mask
[index
++] = current_mask_element
;
3135 if (index
== nunits
)
3138 if (!can_vec_perm_p (mode
, false, mask
))
3140 if (dump_enabled_p ())
3142 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
3144 "unsupported vect permute { ");
3145 for (i
= 0; i
< nunits
; ++i
)
3146 dump_printf (MSG_MISSED_OPTIMIZATION
, "%d ",
3148 dump_printf (MSG_MISSED_OPTIMIZATION
, "}\n");
3156 tree mask_vec
, *mask_elts
;
3157 mask_elts
= XALLOCAVEC (tree
, nunits
);
3158 for (l
= 0; l
< nunits
; ++l
)
3159 mask_elts
[l
] = build_int_cst (mask_element_type
,
3161 mask_vec
= build_vector (mask_type
, mask_elts
);
3163 if (need_next_vector
)
3165 first_vec_index
= second_vec_index
;
3166 second_vec_index
= vec_index
;
3170 = SLP_TREE_SCALAR_STMTS (node
)[scalar_index
++];
3172 vect_create_mask_and_perm (stmt
, next_scalar_stmt
,
3173 mask_vec
, first_vec_index
, second_vec_index
,
3174 gsi
, node
, vectype
, dr_chain
,
3175 ncopies
, vect_stmts_counter
++);
3187 /* Vectorize SLP instance tree in postorder. */
3190 vect_schedule_slp_instance (slp_tree node
, slp_instance instance
,
3191 unsigned int vectorization_factor
)
3194 bool grouped_store
, is_store
;
3195 gimple_stmt_iterator si
;
3196 stmt_vec_info stmt_info
;
3197 unsigned int vec_stmts_size
, nunits
, group_size
;
3205 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3206 vect_schedule_slp_instance (child
, instance
, vectorization_factor
);
3208 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3209 stmt_info
= vinfo_for_stmt (stmt
);
3211 /* VECTYPE is the type of the destination. */
3212 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3213 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (vectype
);
3214 group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
3216 /* For each SLP instance calculate number of vector stmts to be created
3217 for the scalar stmts in each node of the SLP tree. Number of vector
3218 elements in one vector iteration is the number of scalar elements in
3219 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
3221 vec_stmts_size
= (vectorization_factor
* group_size
) / nunits
;
3223 if (!SLP_TREE_VEC_STMTS (node
).exists ())
3225 SLP_TREE_VEC_STMTS (node
).create (vec_stmts_size
);
3226 SLP_TREE_NUMBER_OF_VEC_STMTS (node
) = vec_stmts_size
;
3229 if (dump_enabled_p ())
3231 dump_printf_loc (MSG_NOTE
,vect_location
,
3232 "------>vectorizing SLP node starting from: ");
3233 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3234 dump_printf (MSG_NOTE
, "\n");
3237 /* Vectorized stmts go before the last scalar stmt which is where
3238 all uses are ready. */
3239 si
= gsi_for_stmt (vect_find_last_scalar_stmt_in_slp (node
));
3241 /* Mark the first element of the reduction chain as reduction to properly
3242 transform the node. In the analysis phase only the last element of the
3243 chain is marked as reduction. */
3244 if (GROUP_FIRST_ELEMENT (stmt_info
) && !STMT_VINFO_GROUPED_ACCESS (stmt_info
)
3245 && GROUP_FIRST_ELEMENT (stmt_info
) == stmt
)
3247 STMT_VINFO_DEF_TYPE (stmt_info
) = vect_reduction_def
;
3248 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
3251 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3255 /* Replace scalar calls from SLP node NODE with setting of their lhs to zero.
3256 For loop vectorization this is done in vectorizable_call, but for SLP
3257 it needs to be deferred until end of vect_schedule_slp, because multiple
3258 SLP instances may refer to the same scalar stmt. */
3261 vect_remove_slp_scalar_calls (slp_tree node
)
3263 gimple stmt
, new_stmt
;
3264 gimple_stmt_iterator gsi
;
3268 stmt_vec_info stmt_info
;
3273 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3274 vect_remove_slp_scalar_calls (child
);
3276 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
3278 if (!is_gimple_call (stmt
) || gimple_bb (stmt
) == NULL
)
3280 stmt_info
= vinfo_for_stmt (stmt
);
3281 if (stmt_info
== NULL
3282 || is_pattern_stmt_p (stmt_info
)
3283 || !PURE_SLP_STMT (stmt_info
))
3285 lhs
= gimple_call_lhs (stmt
);
3286 new_stmt
= gimple_build_assign (lhs
, build_zero_cst (TREE_TYPE (lhs
)));
3287 set_vinfo_for_stmt (new_stmt
, stmt_info
);
3288 set_vinfo_for_stmt (stmt
, NULL
);
3289 STMT_VINFO_STMT (stmt_info
) = new_stmt
;
3290 gsi
= gsi_for_stmt (stmt
);
3291 gsi_replace (&gsi
, new_stmt
, false);
3292 SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt
)) = new_stmt
;
3296 /* Generate vector code for all SLP instances in the loop/basic block. */
3299 vect_schedule_slp (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
)
3301 vec
<slp_instance
> slp_instances
;
3302 slp_instance instance
;
3304 bool is_store
= false;
3308 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
3309 vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3313 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
3317 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3319 /* Schedule the tree of INSTANCE. */
3320 is_store
= vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance
),
3322 if (dump_enabled_p ())
3323 dump_printf_loc (MSG_NOTE
, vect_location
,
3324 "vectorizing stmts using SLP.\n");
3327 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3329 slp_tree root
= SLP_INSTANCE_TREE (instance
);
3332 gimple_stmt_iterator gsi
;
3334 /* Remove scalar call stmts. Do not do this for basic-block
3335 vectorization as not all uses may be vectorized.
3336 ??? Why should this be necessary? DCE should be able to
3337 remove the stmts itself.
3338 ??? For BB vectorization we can as well remove scalar
3339 stmts starting from the SLP tree root if they have no
3342 vect_remove_slp_scalar_calls (root
);
3344 for (j
= 0; SLP_TREE_SCALAR_STMTS (root
).iterate (j
, &store
)
3345 && j
< SLP_INSTANCE_GROUP_SIZE (instance
); j
++)
3347 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store
)))
3350 if (is_pattern_stmt_p (vinfo_for_stmt (store
)))
3351 store
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (store
));
3352 /* Free the attached stmt_vec_info and remove the stmt. */
3353 gsi
= gsi_for_stmt (store
);
3354 unlink_stmt_vdef (store
);
3355 gsi_remove (&gsi
, true);
3356 release_defs (store
);
3357 free_stmt_vec_info (store
);
3365 /* Vectorize the basic block. */
3368 vect_slp_transform_bb (basic_block bb
)
3370 bb_vec_info bb_vinfo
= vec_info_for_bb (bb
);
3371 gimple_stmt_iterator si
;
3373 gcc_assert (bb_vinfo
);
3375 if (dump_enabled_p ())
3376 dump_printf_loc (MSG_NOTE
, vect_location
, "SLPing BB\n");
3378 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
3380 gimple stmt
= gsi_stmt (si
);
3381 stmt_vec_info stmt_info
;
3383 if (dump_enabled_p ())
3385 dump_printf_loc (MSG_NOTE
, vect_location
,
3386 "------>SLPing statement: ");
3387 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3388 dump_printf (MSG_NOTE
, "\n");
3391 stmt_info
= vinfo_for_stmt (stmt
);
3392 gcc_assert (stmt_info
);
3394 /* Schedule all the SLP instances when the first SLP stmt is reached. */
3395 if (STMT_SLP_TYPE (stmt_info
))
3397 vect_schedule_slp (NULL
, bb_vinfo
);
3402 if (dump_enabled_p ())
3403 dump_printf_loc (MSG_NOTE
, vect_location
,
3404 "BASIC BLOCK VECTORIZED\n");
3406 destroy_bb_vec_info (bb_vinfo
);