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"
34 #include "fold-const.h"
35 #include "stor-layout.h"
38 #include "hard-reg-set.h"
40 #include "basic-block.h"
41 #include "gimple-pretty-print.h"
42 #include "tree-ssa-alias.h"
43 #include "internal-fn.h"
44 #include "gimple-expr.h"
47 #include "gimple-iterator.h"
48 #include "gimple-ssa.h"
49 #include "tree-phinodes.h"
50 #include "ssa-iterators.h"
51 #include "stringpool.h"
52 #include "tree-ssanames.h"
53 #include "tree-pass.h"
58 #include "statistics.h"
59 #include "insn-config.h"
68 #include "recog.h" /* FIXME: for insn_data */
69 #include "insn-codes.h"
71 #include "tree-vectorizer.h"
72 #include "langhooks.h"
73 #include "gimple-walk.h"
75 /* Extract the location of the basic block in the source code.
76 Return the basic block location if succeed and NULL if not. */
79 find_bb_location (basic_block bb
)
82 gimple_stmt_iterator si
;
85 return UNKNOWN_LOCATION
;
87 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
90 if (gimple_location (stmt
) != UNKNOWN_LOCATION
)
91 return gimple_location (stmt
);
94 return UNKNOWN_LOCATION
;
98 /* Recursively free the memory allocated for the SLP tree rooted at NODE. */
101 vect_free_slp_tree (slp_tree node
)
109 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
110 vect_free_slp_tree (child
);
112 SLP_TREE_CHILDREN (node
).release ();
113 SLP_TREE_SCALAR_STMTS (node
).release ();
114 SLP_TREE_VEC_STMTS (node
).release ();
115 SLP_TREE_LOAD_PERMUTATION (node
).release ();
121 /* Free the memory allocated for the SLP instance. */
124 vect_free_slp_instance (slp_instance instance
)
126 vect_free_slp_tree (SLP_INSTANCE_TREE (instance
));
127 SLP_INSTANCE_LOADS (instance
).release ();
132 /* Create an SLP node for SCALAR_STMTS. */
135 vect_create_new_slp_node (vec
<gimple
> scalar_stmts
)
138 gimple stmt
= scalar_stmts
[0];
141 if (is_gimple_call (stmt
))
142 nops
= gimple_call_num_args (stmt
);
143 else if (is_gimple_assign (stmt
))
145 nops
= gimple_num_ops (stmt
) - 1;
146 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
152 node
= XNEW (struct _slp_tree
);
153 SLP_TREE_SCALAR_STMTS (node
) = scalar_stmts
;
154 SLP_TREE_VEC_STMTS (node
).create (0);
155 SLP_TREE_CHILDREN (node
).create (nops
);
156 SLP_TREE_LOAD_PERMUTATION (node
) = vNULL
;
157 SLP_TREE_TWO_OPERATORS (node
) = false;
163 /* Allocate operands info for NOPS operands, and GROUP_SIZE def-stmts for each
165 static vec
<slp_oprnd_info
>
166 vect_create_oprnd_info (int nops
, int group_size
)
169 slp_oprnd_info oprnd_info
;
170 vec
<slp_oprnd_info
> oprnds_info
;
172 oprnds_info
.create (nops
);
173 for (i
= 0; i
< nops
; i
++)
175 oprnd_info
= XNEW (struct _slp_oprnd_info
);
176 oprnd_info
->def_stmts
.create (group_size
);
177 oprnd_info
->first_dt
= vect_uninitialized_def
;
178 oprnd_info
->first_op_type
= NULL_TREE
;
179 oprnd_info
->first_pattern
= false;
180 oprnd_info
->second_pattern
= false;
181 oprnds_info
.quick_push (oprnd_info
);
188 /* Free operands info. */
191 vect_free_oprnd_info (vec
<slp_oprnd_info
> &oprnds_info
)
194 slp_oprnd_info oprnd_info
;
196 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
198 oprnd_info
->def_stmts
.release ();
199 XDELETE (oprnd_info
);
202 oprnds_info
.release ();
206 /* Find the place of the data-ref in STMT in the interleaving chain that starts
207 from FIRST_STMT. Return -1 if the data-ref is not a part of the chain. */
210 vect_get_place_in_interleaving_chain (gimple stmt
, gimple first_stmt
)
212 gimple next_stmt
= first_stmt
;
215 if (first_stmt
!= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
220 if (next_stmt
== stmt
)
222 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
224 result
+= GROUP_GAP (vinfo_for_stmt (next_stmt
));
232 /* Get the defs for the rhs of STMT (collect them in OPRNDS_INFO), check that
233 they are of a valid type and that they match the defs of the first stmt of
234 the SLP group (stored in OPRNDS_INFO). If there was a fatal error
235 return -1, if the error could be corrected by swapping operands of the
236 operation return 1, if everything is ok return 0. */
239 vect_get_and_check_slp_defs (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
240 gimple stmt
, unsigned stmt_num
,
241 vec
<slp_oprnd_info
> *oprnds_info
)
244 unsigned int i
, number_of_oprnds
;
247 enum vect_def_type dt
= vect_uninitialized_def
;
248 struct loop
*loop
= NULL
;
249 bool pattern
= false;
250 slp_oprnd_info oprnd_info
;
251 int first_op_idx
= 1;
252 bool commutative
= false;
253 bool first_op_cond
= false;
254 bool first
= stmt_num
== 0;
255 bool second
= stmt_num
== 1;
258 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
260 if (is_gimple_call (stmt
))
262 number_of_oprnds
= gimple_call_num_args (stmt
);
265 else if (is_gimple_assign (stmt
))
267 enum tree_code code
= gimple_assign_rhs_code (stmt
);
268 number_of_oprnds
= gimple_num_ops (stmt
) - 1;
269 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
271 first_op_cond
= true;
276 commutative
= commutative_tree_code (code
);
281 bool swapped
= false;
282 for (i
= 0; i
< number_of_oprnds
; i
++)
287 if (i
== 0 || i
== 1)
288 oprnd
= TREE_OPERAND (gimple_op (stmt
, first_op_idx
),
291 oprnd
= gimple_op (stmt
, first_op_idx
+ i
- 1);
294 oprnd
= gimple_op (stmt
, first_op_idx
+ (swapped
? !i
: i
));
296 oprnd_info
= (*oprnds_info
)[i
];
298 if (!vect_is_simple_use (oprnd
, NULL
, loop_vinfo
, bb_vinfo
, &def_stmt
,
301 if (dump_enabled_p ())
303 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
304 "Build SLP failed: can't analyze def for ");
305 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
306 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
312 /* Check if DEF_STMT is a part of a pattern in LOOP and get the def stmt
313 from the pattern. Check that all the stmts of the node are in the
315 if (def_stmt
&& gimple_bb (def_stmt
)
316 && ((loop
&& flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
)))
317 || (!loop
&& gimple_bb (def_stmt
) == BB_VINFO_BB (bb_vinfo
)
318 && gimple_code (def_stmt
) != GIMPLE_PHI
))
319 && vinfo_for_stmt (def_stmt
)
320 && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (def_stmt
))
321 && !STMT_VINFO_RELEVANT (vinfo_for_stmt (def_stmt
))
322 && !STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt
)))
325 if (!first
&& !oprnd_info
->first_pattern
326 /* Allow different pattern state for the defs of the
327 first stmt in reduction chains. */
328 && (oprnd_info
->first_dt
!= vect_reduction_def
329 || (!second
&& !oprnd_info
->second_pattern
)))
339 if (dump_enabled_p ())
341 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
342 "Build SLP failed: some of the stmts"
343 " are in a pattern, and others are not ");
344 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
345 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
351 def_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
));
352 dt
= STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
));
354 if (dt
== vect_unknown_def_type
)
356 if (dump_enabled_p ())
357 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
358 "Unsupported pattern.\n");
362 switch (gimple_code (def_stmt
))
365 def
= gimple_phi_result (def_stmt
);
369 def
= gimple_assign_lhs (def_stmt
);
373 if (dump_enabled_p ())
374 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
375 "unsupported defining stmt:\n");
381 oprnd_info
->second_pattern
= pattern
;
385 oprnd_info
->first_dt
= dt
;
386 oprnd_info
->first_pattern
= pattern
;
387 oprnd_info
->first_op_type
= TREE_TYPE (oprnd
);
391 /* Not first stmt of the group, check that the def-stmt/s match
392 the def-stmt/s of the first stmt. Allow different definition
393 types for reduction chains: the first stmt must be a
394 vect_reduction_def (a phi node), and the rest
395 vect_internal_def. */
396 if (((oprnd_info
->first_dt
!= dt
397 && !(oprnd_info
->first_dt
== vect_reduction_def
398 && dt
== vect_internal_def
)
399 && !((oprnd_info
->first_dt
== vect_external_def
400 || oprnd_info
->first_dt
== vect_constant_def
)
401 && (dt
== vect_external_def
402 || dt
== vect_constant_def
)))
403 || !types_compatible_p (oprnd_info
->first_op_type
,
406 /* Try swapping operands if we got a mismatch. */
415 if (dump_enabled_p ())
416 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
417 "Build SLP failed: different types\n");
423 /* Check the types of the definitions. */
426 case vect_constant_def
:
427 case vect_external_def
:
428 case vect_reduction_def
:
431 case vect_internal_def
:
432 oprnd_info
->def_stmts
.quick_push (def_stmt
);
436 /* FORNOW: Not supported. */
437 if (dump_enabled_p ())
439 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
440 "Build SLP failed: illegal type of def ");
441 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, def
);
442 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
454 tree cond
= gimple_assign_rhs1 (stmt
);
455 swap_ssa_operands (stmt
, &TREE_OPERAND (cond
, 0),
456 &TREE_OPERAND (cond
, 1));
457 TREE_SET_CODE (cond
, swap_tree_comparison (TREE_CODE (cond
)));
460 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
461 gimple_assign_rhs2_ptr (stmt
));
468 /* Verify if the scalar stmts STMTS are isomorphic, require data
469 permutation or are of unsupported types of operation. Return
470 true if they are, otherwise return false and indicate in *MATCHES
471 which stmts are not isomorphic to the first one. If MATCHES[0]
472 is false then this indicates the comparison could not be
473 carried out or the stmts will never be vectorized by SLP. */
476 vect_build_slp_tree_1 (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
477 vec
<gimple
> stmts
, unsigned int group_size
,
478 unsigned nops
, unsigned int *max_nunits
,
479 unsigned int vectorization_factor
, bool *matches
,
483 gimple first_stmt
= stmts
[0], stmt
= stmts
[0];
484 enum tree_code first_stmt_code
= ERROR_MARK
;
485 enum tree_code alt_stmt_code
= ERROR_MARK
;
486 enum tree_code rhs_code
= ERROR_MARK
;
487 enum tree_code first_cond_code
= ERROR_MARK
;
489 bool need_same_oprnds
= false;
490 tree vectype
, scalar_type
, first_op1
= NULL_TREE
;
493 machine_mode optab_op2_mode
;
494 machine_mode vec_mode
;
495 struct data_reference
*first_dr
;
497 gimple first_load
= NULL
, prev_first_load
= NULL
, old_first_load
= NULL
;
500 /* For every stmt in NODE find its def stmt/s. */
501 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
505 if (dump_enabled_p ())
507 dump_printf_loc (MSG_NOTE
, vect_location
, "Build SLP for ");
508 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
509 dump_printf (MSG_NOTE
, "\n");
512 /* Fail to vectorize statements marked as unvectorizable. */
513 if (!STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt
)))
515 if (dump_enabled_p ())
517 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
518 "Build SLP failed: unvectorizable statement ");
519 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
520 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
522 /* Fatal mismatch. */
527 lhs
= gimple_get_lhs (stmt
);
528 if (lhs
== NULL_TREE
)
530 if (dump_enabled_p ())
532 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
533 "Build SLP failed: not GIMPLE_ASSIGN nor "
535 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
536 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
538 /* Fatal mismatch. */
543 if (is_gimple_assign (stmt
)
544 && gimple_assign_rhs_code (stmt
) == COND_EXPR
545 && (cond
= gimple_assign_rhs1 (stmt
))
546 && !COMPARISON_CLASS_P (cond
))
548 if (dump_enabled_p ())
550 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
551 "Build SLP failed: condition is not "
553 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
554 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
556 /* Fatal mismatch. */
561 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
, &dummy
);
562 vectype
= get_vectype_for_scalar_type (scalar_type
);
565 if (dump_enabled_p ())
567 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
568 "Build SLP failed: unsupported data-type ");
569 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
571 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
573 /* Fatal mismatch. */
578 /* If populating the vector type requires unrolling then fail
579 before adjusting *max_nunits for basic-block vectorization. */
581 && TYPE_VECTOR_SUBPARTS (vectype
) > group_size
)
583 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
584 "Build SLP failed: unrolling required "
585 "in basic block SLP\n");
586 /* Fatal mismatch. */
591 /* In case of multiple types we need to detect the smallest type. */
592 if (*max_nunits
< TYPE_VECTOR_SUBPARTS (vectype
))
594 *max_nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
596 vectorization_factor
= *max_nunits
;
599 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
601 rhs_code
= CALL_EXPR
;
602 if (gimple_call_internal_p (call_stmt
)
603 || gimple_call_tail_p (call_stmt
)
604 || gimple_call_noreturn_p (call_stmt
)
605 || !gimple_call_nothrow_p (call_stmt
)
606 || gimple_call_chain (call_stmt
))
608 if (dump_enabled_p ())
610 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
611 "Build SLP failed: unsupported call type ");
612 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
614 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
616 /* Fatal mismatch. */
622 rhs_code
= gimple_assign_rhs_code (stmt
);
624 /* Check the operation. */
627 first_stmt_code
= rhs_code
;
629 /* Shift arguments should be equal in all the packed stmts for a
630 vector shift with scalar shift operand. */
631 if (rhs_code
== LSHIFT_EXPR
|| rhs_code
== RSHIFT_EXPR
632 || rhs_code
== LROTATE_EXPR
633 || rhs_code
== RROTATE_EXPR
)
635 vec_mode
= TYPE_MODE (vectype
);
637 /* First see if we have a vector/vector shift. */
638 optab
= optab_for_tree_code (rhs_code
, vectype
,
642 || optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
644 /* No vector/vector shift, try for a vector/scalar shift. */
645 optab
= optab_for_tree_code (rhs_code
, vectype
,
650 if (dump_enabled_p ())
651 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
652 "Build SLP failed: no optab.\n");
653 /* Fatal mismatch. */
657 icode
= (int) optab_handler (optab
, vec_mode
);
658 if (icode
== CODE_FOR_nothing
)
660 if (dump_enabled_p ())
661 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
663 "op not supported by target.\n");
664 /* Fatal mismatch. */
668 optab_op2_mode
= insn_data
[icode
].operand
[2].mode
;
669 if (!VECTOR_MODE_P (optab_op2_mode
))
671 need_same_oprnds
= true;
672 first_op1
= gimple_assign_rhs2 (stmt
);
676 else if (rhs_code
== WIDEN_LSHIFT_EXPR
)
678 need_same_oprnds
= true;
679 first_op1
= gimple_assign_rhs2 (stmt
);
684 if (first_stmt_code
!= rhs_code
685 && alt_stmt_code
== ERROR_MARK
)
686 alt_stmt_code
= rhs_code
;
687 if (first_stmt_code
!= rhs_code
688 && (first_stmt_code
!= IMAGPART_EXPR
689 || rhs_code
!= REALPART_EXPR
)
690 && (first_stmt_code
!= REALPART_EXPR
691 || rhs_code
!= IMAGPART_EXPR
)
692 /* Handle mismatches in plus/minus by computing both
693 and merging the results. */
694 && !((first_stmt_code
== PLUS_EXPR
695 || first_stmt_code
== MINUS_EXPR
)
696 && (alt_stmt_code
== PLUS_EXPR
697 || alt_stmt_code
== MINUS_EXPR
)
698 && rhs_code
== alt_stmt_code
)
699 && !(STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
700 && (first_stmt_code
== ARRAY_REF
701 || first_stmt_code
== BIT_FIELD_REF
702 || first_stmt_code
== INDIRECT_REF
703 || first_stmt_code
== COMPONENT_REF
704 || first_stmt_code
== MEM_REF
)))
706 if (dump_enabled_p ())
708 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
709 "Build SLP failed: different operation "
711 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
712 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
714 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
722 && !operand_equal_p (first_op1
, gimple_assign_rhs2 (stmt
), 0))
724 if (dump_enabled_p ())
726 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
727 "Build SLP failed: different shift "
729 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
730 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
736 if (rhs_code
== CALL_EXPR
)
738 gimple first_stmt
= stmts
[0];
739 if (gimple_call_num_args (stmt
) != nops
740 || !operand_equal_p (gimple_call_fn (first_stmt
),
741 gimple_call_fn (stmt
), 0)
742 || gimple_call_fntype (first_stmt
)
743 != gimple_call_fntype (stmt
))
745 if (dump_enabled_p ())
747 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
748 "Build SLP failed: different calls in ");
749 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
751 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
759 /* Grouped store or load. */
760 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
762 if (REFERENCE_CLASS_P (lhs
))
770 unsigned unrolling_factor
771 = least_common_multiple
772 (*max_nunits
, group_size
) / group_size
;
773 /* FORNOW: Check that there is no gap between the loads
774 and no gap between the groups when we need to load
775 multiple groups at once. */
776 if (unrolling_factor
> 1
777 && ((GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) == stmt
778 && GROUP_GAP (vinfo_for_stmt (stmt
)) != 0)
779 /* If the group is split up then GROUP_GAP
780 isn't correct here, nor is GROUP_FIRST_ELEMENT. */
781 || GROUP_SIZE (vinfo_for_stmt (stmt
)) > group_size
))
783 if (dump_enabled_p ())
785 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
786 "Build SLP failed: grouped "
788 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
790 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
792 /* Fatal mismatch. */
797 /* Check that the size of interleaved loads group is not
798 greater than the SLP group size. */
800 = vectorization_factor
/ TYPE_VECTOR_SUBPARTS (vectype
);
802 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) == stmt
803 && ((GROUP_SIZE (vinfo_for_stmt (stmt
))
804 - GROUP_GAP (vinfo_for_stmt (stmt
)))
805 > ncopies
* group_size
))
807 if (dump_enabled_p ())
809 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
810 "Build SLP failed: the number "
811 "of interleaved loads is greater than "
812 "the SLP group size ");
813 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
815 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
817 /* Fatal mismatch. */
822 old_first_load
= first_load
;
823 first_load
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
));
826 /* Check that there are no loads from different interleaving
827 chains in the same node. */
828 if (prev_first_load
!= first_load
)
830 if (dump_enabled_p ())
832 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
834 "Build SLP failed: different "
835 "interleaving chains in one node ");
836 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
838 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
845 prev_first_load
= first_load
;
847 /* In some cases a group of loads is just the same load
848 repeated N times. Only analyze its cost once. */
849 if (first_load
== stmt
&& old_first_load
!= first_load
)
851 first_dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
));
852 if (vect_supportable_dr_alignment (first_dr
, false)
853 == dr_unaligned_unsupported
)
855 if (dump_enabled_p ())
857 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
859 "Build SLP failed: unsupported "
861 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
863 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
865 /* Fatal mismatch. */
871 } /* Grouped access. */
874 if (TREE_CODE_CLASS (rhs_code
) == tcc_reference
)
876 /* Not grouped load. */
877 if (dump_enabled_p ())
879 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
880 "Build SLP failed: not grouped load ");
881 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
882 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
885 /* FORNOW: Not grouped loads are not supported. */
886 /* Fatal mismatch. */
891 /* Not memory operation. */
892 if (TREE_CODE_CLASS (rhs_code
) != tcc_binary
893 && TREE_CODE_CLASS (rhs_code
) != tcc_unary
894 && TREE_CODE_CLASS (rhs_code
) != tcc_expression
895 && rhs_code
!= CALL_EXPR
)
897 if (dump_enabled_p ())
899 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
900 "Build SLP failed: operation");
901 dump_printf (MSG_MISSED_OPTIMIZATION
, " unsupported ");
902 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
903 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
905 /* Fatal mismatch. */
910 if (rhs_code
== COND_EXPR
)
912 tree cond_expr
= gimple_assign_rhs1 (stmt
);
915 first_cond_code
= TREE_CODE (cond_expr
);
916 else if (first_cond_code
!= TREE_CODE (cond_expr
))
918 if (dump_enabled_p ())
920 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
921 "Build SLP failed: different"
923 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
925 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
936 for (i
= 0; i
< group_size
; ++i
)
940 /* If we allowed a two-operation SLP node verify the target can cope
941 with the permute we are going to use. */
942 if (alt_stmt_code
!= ERROR_MARK
943 && TREE_CODE_CLASS (alt_stmt_code
) != tcc_reference
)
946 = XALLOCAVEC (unsigned char, TYPE_VECTOR_SUBPARTS (vectype
));
947 for (i
= 0; i
< TYPE_VECTOR_SUBPARTS (vectype
); ++i
)
950 if (gimple_assign_rhs_code (stmts
[i
% group_size
]) == alt_stmt_code
)
951 sel
[i
] += TYPE_VECTOR_SUBPARTS (vectype
);
953 if (!can_vec_perm_p (TYPE_MODE (vectype
), false, sel
))
955 for (i
= 0; i
< group_size
; ++i
)
956 if (gimple_assign_rhs_code (stmts
[i
]) == alt_stmt_code
)
959 if (dump_enabled_p ())
961 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
962 "Build SLP failed: different operation "
964 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
966 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
968 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
974 *two_operators
= true;
980 /* Recursively build an SLP tree starting from NODE.
981 Fail (and return a value not equal to zero) if def-stmts are not
982 isomorphic, require data permutation or are of unsupported types of
983 operation. Otherwise, return 0.
984 The value returned is the depth in the SLP tree where a mismatch
988 vect_build_slp_tree (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
989 slp_tree
*node
, unsigned int group_size
,
990 unsigned int *max_nunits
,
991 vec
<slp_tree
> *loads
,
992 unsigned int vectorization_factor
,
993 bool *matches
, unsigned *npermutes
, unsigned *tree_size
,
994 unsigned max_tree_size
)
996 unsigned nops
, i
, this_tree_size
= 0;
1001 stmt
= SLP_TREE_SCALAR_STMTS (*node
)[0];
1002 if (is_gimple_call (stmt
))
1003 nops
= gimple_call_num_args (stmt
);
1004 else if (is_gimple_assign (stmt
))
1006 nops
= gimple_num_ops (stmt
) - 1;
1007 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
1013 bool two_operators
= false;
1014 if (!vect_build_slp_tree_1 (loop_vinfo
, bb_vinfo
,
1015 SLP_TREE_SCALAR_STMTS (*node
), group_size
, nops
,
1016 max_nunits
, vectorization_factor
, matches
,
1019 SLP_TREE_TWO_OPERATORS (*node
) = two_operators
;
1021 /* If the SLP node is a load, terminate the recursion. */
1022 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
1023 && DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
1025 loads
->safe_push (*node
);
1029 /* Get at the operands, verifying they are compatible. */
1030 vec
<slp_oprnd_info
> oprnds_info
= vect_create_oprnd_info (nops
, group_size
);
1031 slp_oprnd_info oprnd_info
;
1032 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (*node
), i
, stmt
)
1034 switch (vect_get_and_check_slp_defs (loop_vinfo
, bb_vinfo
,
1035 stmt
, i
, &oprnds_info
))
1041 vect_free_oprnd_info (oprnds_info
);
1048 for (i
= 0; i
< group_size
; ++i
)
1051 vect_free_oprnd_info (oprnds_info
);
1055 stmt
= SLP_TREE_SCALAR_STMTS (*node
)[0];
1057 /* Create SLP_TREE nodes for the definition node/s. */
1058 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
1061 unsigned old_nloads
= loads
->length ();
1062 unsigned old_max_nunits
= *max_nunits
;
1064 if (oprnd_info
->first_dt
!= vect_internal_def
)
1067 if (++this_tree_size
> max_tree_size
)
1069 vect_free_oprnd_info (oprnds_info
);
1073 child
= vect_create_new_slp_node (oprnd_info
->def_stmts
);
1076 vect_free_oprnd_info (oprnds_info
);
1080 if (vect_build_slp_tree (loop_vinfo
, bb_vinfo
, &child
,
1081 group_size
, max_nunits
, loads
,
1082 vectorization_factor
, matches
,
1083 npermutes
, &this_tree_size
, max_tree_size
))
1085 /* If we have all children of child built up from scalars then just
1086 throw that away and build it up this node from scalars. */
1087 if (!SLP_TREE_CHILDREN (child
).is_empty ())
1090 slp_tree grandchild
;
1092 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1093 if (grandchild
!= NULL
)
1098 *max_nunits
= old_max_nunits
;
1099 loads
->truncate (old_nloads
);
1100 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1101 vect_free_slp_tree (grandchild
);
1102 SLP_TREE_CHILDREN (child
).truncate (0);
1104 dump_printf_loc (MSG_NOTE
, vect_location
,
1105 "Building parent vector operands from "
1106 "scalars instead\n");
1107 oprnd_info
->def_stmts
= vNULL
;
1108 vect_free_slp_tree (child
);
1109 SLP_TREE_CHILDREN (*node
).quick_push (NULL
);
1114 oprnd_info
->def_stmts
= vNULL
;
1115 SLP_TREE_CHILDREN (*node
).quick_push (child
);
1119 /* If the SLP build failed fatally and we analyze a basic-block
1120 simply treat nodes we fail to build as externally defined
1121 (and thus build vectors from the scalar defs).
1122 The cost model will reject outright expensive cases.
1123 ??? This doesn't treat cases where permutation ultimatively
1124 fails (or we don't try permutation below). Ideally we'd
1125 even compute a permutation that will end up with the maximum
1129 /* ??? Rejecting patterns this way doesn't work. We'd have to
1130 do extra work to cancel the pattern so the uses see the
1132 && !is_pattern_stmt_p (vinfo_for_stmt (stmt
)))
1135 slp_tree grandchild
;
1138 *max_nunits
= old_max_nunits
;
1139 loads
->truncate (old_nloads
);
1140 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1141 vect_free_slp_tree (grandchild
);
1142 SLP_TREE_CHILDREN (child
).truncate (0);
1144 dump_printf_loc (MSG_NOTE
, vect_location
,
1145 "Building vector operands from scalars\n");
1146 oprnd_info
->def_stmts
= vNULL
;
1147 vect_free_slp_tree (child
);
1148 SLP_TREE_CHILDREN (*node
).quick_push (NULL
);
1152 /* If the SLP build for operand zero failed and operand zero
1153 and one can be commutated try that for the scalar stmts
1154 that failed the match. */
1156 /* A first scalar stmt mismatch signals a fatal mismatch. */
1158 /* ??? For COND_EXPRs we can swap the comparison operands
1159 as well as the arms under some constraints. */
1161 && oprnds_info
[1]->first_dt
== vect_internal_def
1162 && is_gimple_assign (stmt
)
1163 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
1164 && !SLP_TREE_TWO_OPERATORS (*node
)
1165 /* Do so only if the number of not successful permutes was nor more
1166 than a cut-ff as re-trying the recursive match on
1167 possibly each level of the tree would expose exponential
1172 slp_tree grandchild
;
1175 *max_nunits
= old_max_nunits
;
1176 loads
->truncate (old_nloads
);
1177 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1178 vect_free_slp_tree (grandchild
);
1179 SLP_TREE_CHILDREN (child
).truncate (0);
1181 /* Swap mismatched definition stmts. */
1182 dump_printf_loc (MSG_NOTE
, vect_location
,
1183 "Re-trying with swapped operands of stmts ");
1184 for (j
= 0; j
< group_size
; ++j
)
1187 gimple tem
= oprnds_info
[0]->def_stmts
[j
];
1188 oprnds_info
[0]->def_stmts
[j
] = oprnds_info
[1]->def_stmts
[j
];
1189 oprnds_info
[1]->def_stmts
[j
] = tem
;
1190 dump_printf (MSG_NOTE
, "%d ", j
);
1192 dump_printf (MSG_NOTE
, "\n");
1193 /* And try again with scratch 'matches' ... */
1194 bool *tem
= XALLOCAVEC (bool, group_size
);
1195 if (vect_build_slp_tree (loop_vinfo
, bb_vinfo
, &child
,
1196 group_size
, max_nunits
, loads
,
1197 vectorization_factor
,
1198 tem
, npermutes
, &this_tree_size
,
1201 /* ... so if successful we can apply the operand swapping
1202 to the GIMPLE IL. This is necessary because for example
1203 vect_get_slp_defs uses operand indexes and thus expects
1204 canonical operand order. */
1205 for (j
= 0; j
< group_size
; ++j
)
1208 gimple stmt
= SLP_TREE_SCALAR_STMTS (*node
)[j
];
1209 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
1210 gimple_assign_rhs2_ptr (stmt
));
1212 oprnd_info
->def_stmts
= vNULL
;
1213 SLP_TREE_CHILDREN (*node
).quick_push (child
);
1220 oprnd_info
->def_stmts
= vNULL
;
1221 vect_free_slp_tree (child
);
1222 vect_free_oprnd_info (oprnds_info
);
1227 *tree_size
+= this_tree_size
;
1229 vect_free_oprnd_info (oprnds_info
);
1233 /* Dump a slp tree NODE using flags specified in DUMP_KIND. */
1236 vect_print_slp_tree (int dump_kind
, slp_tree node
)
1245 dump_printf (dump_kind
, "node ");
1246 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1248 dump_printf (dump_kind
, "\n\tstmt %d ", i
);
1249 dump_gimple_stmt (dump_kind
, TDF_SLIM
, stmt
, 0);
1251 dump_printf (dump_kind
, "\n");
1253 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1254 vect_print_slp_tree (dump_kind
, child
);
1258 /* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
1259 If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
1260 J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
1261 stmts in NODE are to be marked. */
1264 vect_mark_slp_stmts (slp_tree node
, enum slp_vect_type mark
, int j
)
1273 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1274 if (j
< 0 || i
== j
)
1275 STMT_SLP_TYPE (vinfo_for_stmt (stmt
)) = mark
;
1277 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1278 vect_mark_slp_stmts (child
, mark
, j
);
1282 /* Mark the statements of the tree rooted at NODE as relevant (vect_used). */
1285 vect_mark_slp_stmts_relevant (slp_tree node
)
1289 stmt_vec_info stmt_info
;
1295 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1297 stmt_info
= vinfo_for_stmt (stmt
);
1298 gcc_assert (!STMT_VINFO_RELEVANT (stmt_info
)
1299 || STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
);
1300 STMT_VINFO_RELEVANT (stmt_info
) = vect_used_in_scope
;
1303 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1304 vect_mark_slp_stmts_relevant (child
);
1308 /* Rearrange the statements of NODE according to PERMUTATION. */
1311 vect_slp_rearrange_stmts (slp_tree node
, unsigned int group_size
,
1312 vec
<unsigned> permutation
)
1315 vec
<gimple
> tmp_stmts
;
1319 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1320 vect_slp_rearrange_stmts (child
, group_size
, permutation
);
1322 gcc_assert (group_size
== SLP_TREE_SCALAR_STMTS (node
).length ());
1323 tmp_stmts
.create (group_size
);
1324 tmp_stmts
.quick_grow_cleared (group_size
);
1326 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1327 tmp_stmts
[permutation
[i
]] = stmt
;
1329 SLP_TREE_SCALAR_STMTS (node
).release ();
1330 SLP_TREE_SCALAR_STMTS (node
) = tmp_stmts
;
1334 /* Check if the required load permutations in the SLP instance
1335 SLP_INSTN are supported. */
1338 vect_supported_load_permutation_p (slp_instance slp_instn
)
1340 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1341 unsigned int i
, j
, k
, next
;
1344 gimple stmt
, load
, next_load
, first_load
;
1345 struct data_reference
*dr
;
1347 if (dump_enabled_p ())
1349 dump_printf_loc (MSG_NOTE
, vect_location
, "Load permutation ");
1350 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1351 if (node
->load_permutation
.exists ())
1352 FOR_EACH_VEC_ELT (node
->load_permutation
, j
, next
)
1353 dump_printf (MSG_NOTE
, "%d ", next
);
1355 for (k
= 0; k
< group_size
; ++k
)
1356 dump_printf (MSG_NOTE
, "%d ", k
);
1357 dump_printf (MSG_NOTE
, "\n");
1360 /* In case of reduction every load permutation is allowed, since the order
1361 of the reduction statements is not important (as opposed to the case of
1362 grouped stores). The only condition we need to check is that all the
1363 load nodes are of the same size and have the same permutation (and then
1364 rearrange all the nodes of the SLP instance according to this
1367 /* Check that all the load nodes are of the same size. */
1368 /* ??? Can't we assert this? */
1369 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1370 if (SLP_TREE_SCALAR_STMTS (node
).length () != (unsigned) group_size
)
1373 node
= SLP_INSTANCE_TREE (slp_instn
);
1374 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1376 /* Reduction (there are no data-refs in the root).
1377 In reduction chain the order of the loads is important. */
1378 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))
1379 && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1384 /* Compare all the permutation sequences to the first one. We know
1385 that at least one load is permuted. */
1386 node
= SLP_INSTANCE_LOADS (slp_instn
)[0];
1387 if (!node
->load_permutation
.exists ())
1389 for (i
= 1; SLP_INSTANCE_LOADS (slp_instn
).iterate (i
, &load
); ++i
)
1391 if (!load
->load_permutation
.exists ())
1393 FOR_EACH_VEC_ELT (load
->load_permutation
, j
, lidx
)
1394 if (lidx
!= node
->load_permutation
[j
])
1398 /* Check that the loads in the first sequence are different and there
1399 are no gaps between them. */
1400 load_index
= sbitmap_alloc (group_size
);
1401 bitmap_clear (load_index
);
1402 FOR_EACH_VEC_ELT (node
->load_permutation
, i
, lidx
)
1404 if (bitmap_bit_p (load_index
, lidx
))
1406 sbitmap_free (load_index
);
1409 bitmap_set_bit (load_index
, lidx
);
1411 for (i
= 0; i
< group_size
; i
++)
1412 if (!bitmap_bit_p (load_index
, i
))
1414 sbitmap_free (load_index
);
1417 sbitmap_free (load_index
);
1419 /* This permutation is valid for reduction. Since the order of the
1420 statements in the nodes is not important unless they are memory
1421 accesses, we can rearrange the statements in all the nodes
1422 according to the order of the loads. */
1423 vect_slp_rearrange_stmts (SLP_INSTANCE_TREE (slp_instn
), group_size
,
1424 node
->load_permutation
);
1426 /* We are done, no actual permutations need to be generated. */
1427 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1428 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1432 /* In basic block vectorization we allow any subchain of an interleaving
1434 FORNOW: not supported in loop SLP because of realignment compications. */
1435 if (STMT_VINFO_BB_VINFO (vinfo_for_stmt (stmt
)))
1437 /* Check whether the loads in an instance form a subchain and thus
1438 no permutation is necessary. */
1439 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1441 if (!SLP_TREE_LOAD_PERMUTATION (node
).exists ())
1443 bool subchain_p
= true;
1445 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), j
, load
)
1447 if (j
!= 0 && next_load
!= load
)
1452 next_load
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (load
));
1455 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1458 /* Verify the permutation can be generated. */
1460 if (!vect_transform_slp_perm_load (node
, tem
, NULL
,
1461 1, slp_instn
, true))
1463 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
1465 "unsupported load permutation\n");
1471 /* Check that the alignment of the first load in every subchain, i.e.,
1472 the first statement in every load node, is supported.
1473 ??? This belongs in alignment checking. */
1474 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1476 first_load
= SLP_TREE_SCALAR_STMTS (node
)[0];
1477 if (first_load
!= GROUP_FIRST_ELEMENT (vinfo_for_stmt (first_load
)))
1479 dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (first_load
));
1480 if (vect_supportable_dr_alignment (dr
, false)
1481 == dr_unaligned_unsupported
)
1483 if (dump_enabled_p ())
1485 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
1487 "unsupported unaligned load ");
1488 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
1490 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1500 /* FORNOW: the only supported permutation is 0..01..1.. of length equal to
1501 GROUP_SIZE and where each sequence of same drs is of GROUP_SIZE length as
1502 well (unless it's reduction). */
1503 if (SLP_INSTANCE_LOADS (slp_instn
).length () != group_size
)
1505 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1506 if (!node
->load_permutation
.exists ())
1509 load_index
= sbitmap_alloc (group_size
);
1510 bitmap_clear (load_index
);
1511 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1513 unsigned int lidx
= node
->load_permutation
[0];
1514 if (bitmap_bit_p (load_index
, lidx
))
1516 sbitmap_free (load_index
);
1519 bitmap_set_bit (load_index
, lidx
);
1520 FOR_EACH_VEC_ELT (node
->load_permutation
, j
, k
)
1523 sbitmap_free (load_index
);
1527 for (i
= 0; i
< group_size
; i
++)
1528 if (!bitmap_bit_p (load_index
, i
))
1530 sbitmap_free (load_index
);
1533 sbitmap_free (load_index
);
1535 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1536 if (node
->load_permutation
.exists ()
1537 && !vect_transform_slp_perm_load
1539 SLP_INSTANCE_UNROLLING_FACTOR (slp_instn
), slp_instn
, true))
1545 /* Find the last store in SLP INSTANCE. */
1548 vect_find_last_scalar_stmt_in_slp (slp_tree node
)
1550 gimple last
= NULL
, stmt
;
1552 for (int i
= 0; SLP_TREE_SCALAR_STMTS (node
).iterate (i
, &stmt
); i
++)
1554 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
1555 if (is_pattern_stmt_p (stmt_vinfo
))
1556 last
= get_later_stmt (STMT_VINFO_RELATED_STMT (stmt_vinfo
), last
);
1558 last
= get_later_stmt (stmt
, last
);
1564 /* Compute the cost for the SLP node NODE in the SLP instance INSTANCE. */
1567 vect_analyze_slp_cost_1 (slp_instance instance
, slp_tree node
,
1568 stmt_vector_for_cost
*prologue_cost_vec
,
1569 stmt_vector_for_cost
*body_cost_vec
,
1570 unsigned ncopies_for_cost
)
1575 stmt_vec_info stmt_info
;
1577 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1579 /* Recurse down the SLP tree. */
1580 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1582 vect_analyze_slp_cost_1 (instance
, child
, prologue_cost_vec
,
1583 body_cost_vec
, ncopies_for_cost
);
1585 /* Look at the first scalar stmt to determine the cost. */
1586 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1587 stmt_info
= vinfo_for_stmt (stmt
);
1588 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1590 if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info
)))
1591 vect_model_store_cost (stmt_info
, ncopies_for_cost
, false,
1592 vect_uninitialized_def
,
1593 node
, prologue_cost_vec
, body_cost_vec
);
1597 gcc_checking_assert (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)));
1598 vect_model_load_cost (stmt_info
, ncopies_for_cost
, false,
1599 node
, prologue_cost_vec
, body_cost_vec
);
1600 /* If the load is permuted record the cost for the permutation.
1601 ??? Loads from multiple chains are let through here only
1602 for a single special case involving complex numbers where
1603 in the end no permutation is necessary. */
1604 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, s
)
1605 if ((STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo_for_stmt (s
))
1606 == STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
))
1607 && vect_get_place_in_interleaving_chain
1608 (s
, STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
)) != i
)
1610 record_stmt_cost (body_cost_vec
, group_size
, vec_perm
,
1611 stmt_info
, 0, vect_body
);
1618 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1619 stmt_info
, 0, vect_body
);
1620 if (SLP_TREE_TWO_OPERATORS (node
))
1622 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1623 stmt_info
, 0, vect_body
);
1624 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vec_perm
,
1625 stmt_info
, 0, vect_body
);
1629 /* Scan operands and account for prologue cost of constants/externals.
1630 ??? This over-estimates cost for multiple uses and should be
1632 lhs
= gimple_get_lhs (stmt
);
1633 for (i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1635 tree def
, op
= gimple_op (stmt
, i
);
1637 enum vect_def_type dt
;
1638 if (!op
|| op
== lhs
)
1640 if (vect_is_simple_use (op
, NULL
, STMT_VINFO_LOOP_VINFO (stmt_info
),
1641 STMT_VINFO_BB_VINFO (stmt_info
),
1642 &def_stmt
, &def
, &dt
))
1644 /* Without looking at the actual initializer a vector of
1645 constants can be implemented as load from the constant pool.
1646 ??? We need to pass down stmt_info for a vector type
1647 even if it points to the wrong stmt. */
1648 if (dt
== vect_constant_def
)
1649 record_stmt_cost (prologue_cost_vec
, 1, vector_load
,
1650 stmt_info
, 0, vect_prologue
);
1651 else if (dt
== vect_external_def
)
1652 record_stmt_cost (prologue_cost_vec
, 1, vec_construct
,
1653 stmt_info
, 0, vect_prologue
);
1658 /* Compute the cost for the SLP instance INSTANCE. */
1661 vect_analyze_slp_cost (slp_instance instance
, void *data
)
1663 stmt_vector_for_cost body_cost_vec
, prologue_cost_vec
;
1664 unsigned ncopies_for_cost
;
1665 stmt_info_for_cost
*si
;
1668 /* Calculate the number of vector stmts to create based on the unrolling
1669 factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
1670 GROUP_SIZE / NUNITS otherwise. */
1671 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1672 slp_tree node
= SLP_INSTANCE_TREE (instance
);
1673 stmt_vec_info stmt_info
= vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node
)[0]);
1674 /* Adjust the group_size by the vectorization factor which is always one
1675 for basic-block vectorization. */
1676 if (STMT_VINFO_LOOP_VINFO (stmt_info
))
1677 group_size
*= LOOP_VINFO_VECT_FACTOR (STMT_VINFO_LOOP_VINFO (stmt_info
));
1678 unsigned nunits
= TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
1679 /* For reductions look at a reduction operand in case the reduction
1680 operation is widening like DOT_PROD or SAD. */
1681 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1683 gimple stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1684 switch (gimple_assign_rhs_code (stmt
))
1688 nunits
= TYPE_VECTOR_SUBPARTS (get_vectype_for_scalar_type
1689 (TREE_TYPE (gimple_assign_rhs1 (stmt
))));
1694 ncopies_for_cost
= least_common_multiple (nunits
, group_size
) / nunits
;
1696 prologue_cost_vec
.create (10);
1697 body_cost_vec
.create (10);
1698 vect_analyze_slp_cost_1 (instance
, SLP_INSTANCE_TREE (instance
),
1699 &prologue_cost_vec
, &body_cost_vec
,
1702 /* Record the prologue costs, which were delayed until we were
1703 sure that SLP was successful. */
1704 FOR_EACH_VEC_ELT (prologue_cost_vec
, i
, si
)
1706 struct _stmt_vec_info
*stmt_info
1707 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1708 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1709 si
->misalign
, vect_prologue
);
1712 /* Record the instance's instructions in the target cost model. */
1713 FOR_EACH_VEC_ELT (body_cost_vec
, i
, si
)
1715 struct _stmt_vec_info
*stmt_info
1716 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1717 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1718 si
->misalign
, vect_body
);
1721 prologue_cost_vec
.release ();
1722 body_cost_vec
.release ();
1725 /* Analyze an SLP instance starting from a group of grouped stores. Call
1726 vect_build_slp_tree to build a tree of packed stmts if possible.
1727 Return FALSE if it's impossible to SLP any stmt in the loop. */
1730 vect_analyze_slp_instance (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1731 gimple stmt
, unsigned max_tree_size
)
1733 slp_instance new_instance
;
1735 unsigned int group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1736 unsigned int unrolling_factor
= 1, nunits
;
1737 tree vectype
, scalar_type
= NULL_TREE
;
1739 unsigned int vectorization_factor
= 0;
1741 unsigned int max_nunits
= 0;
1742 vec
<slp_tree
> loads
;
1743 struct data_reference
*dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
));
1744 vec
<gimple
> scalar_stmts
;
1746 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1750 scalar_type
= TREE_TYPE (DR_REF (dr
));
1751 vectype
= get_vectype_for_scalar_type (scalar_type
);
1755 gcc_assert (loop_vinfo
);
1756 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1759 group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1763 gcc_assert (loop_vinfo
);
1764 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1765 group_size
= LOOP_VINFO_REDUCTIONS (loop_vinfo
).length ();
1770 if (dump_enabled_p ())
1772 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1773 "Build SLP failed: unsupported data-type ");
1774 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, scalar_type
);
1775 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1781 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
1783 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1785 vectorization_factor
= nunits
;
1787 /* Calculate the unrolling factor. */
1788 unrolling_factor
= least_common_multiple (nunits
, group_size
) / group_size
;
1789 if (unrolling_factor
!= 1 && !loop_vinfo
)
1791 if (dump_enabled_p ())
1792 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1793 "Build SLP failed: unrolling required in basic"
1799 /* Create a node (a root of the SLP tree) for the packed grouped stores. */
1800 scalar_stmts
.create (group_size
);
1802 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1804 /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
1807 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next
))
1808 && STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)))
1809 scalar_stmts
.safe_push (
1810 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)));
1812 scalar_stmts
.safe_push (next
);
1813 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
1815 /* Mark the first element of the reduction chain as reduction to properly
1816 transform the node. In the reduction analysis phase only the last
1817 element of the chain is marked as reduction. */
1818 if (!STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
1819 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_reduction_def
;
1823 /* Collect reduction statements. */
1824 vec
<gimple
> reductions
= LOOP_VINFO_REDUCTIONS (loop_vinfo
);
1825 for (i
= 0; reductions
.iterate (i
, &next
); i
++)
1826 scalar_stmts
.safe_push (next
);
1829 node
= vect_create_new_slp_node (scalar_stmts
);
1831 loads
.create (group_size
);
1833 /* Build the tree for the SLP instance. */
1834 bool *matches
= XALLOCAVEC (bool, group_size
);
1835 unsigned npermutes
= 0;
1836 if (vect_build_slp_tree (loop_vinfo
, bb_vinfo
, &node
, group_size
,
1837 &max_nunits
, &loads
,
1838 vectorization_factor
, matches
, &npermutes
, NULL
,
1841 /* Calculate the unrolling factor based on the smallest type. */
1842 if (max_nunits
> nunits
)
1843 unrolling_factor
= least_common_multiple (max_nunits
, group_size
)
1846 if (unrolling_factor
!= 1 && !loop_vinfo
)
1848 if (dump_enabled_p ())
1849 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1850 "Build SLP failed: unrolling required in basic"
1852 vect_free_slp_tree (node
);
1857 /* Create a new SLP instance. */
1858 new_instance
= XNEW (struct _slp_instance
);
1859 SLP_INSTANCE_TREE (new_instance
) = node
;
1860 SLP_INSTANCE_GROUP_SIZE (new_instance
) = group_size
;
1861 SLP_INSTANCE_UNROLLING_FACTOR (new_instance
) = unrolling_factor
;
1862 SLP_INSTANCE_LOADS (new_instance
) = loads
;
1864 /* Compute the load permutation. */
1866 bool loads_permuted
= false;
1867 FOR_EACH_VEC_ELT (loads
, i
, load_node
)
1869 vec
<unsigned> load_permutation
;
1871 gimple load
, first_stmt
;
1872 bool this_load_permuted
= false;
1873 load_permutation
.create (group_size
);
1874 first_stmt
= GROUP_FIRST_ELEMENT
1875 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node
)[0]));
1876 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node
), j
, load
)
1879 = vect_get_place_in_interleaving_chain (load
, first_stmt
);
1880 gcc_assert (load_place
!= -1);
1881 if (load_place
!= j
)
1882 this_load_permuted
= true;
1883 load_permutation
.safe_push (load_place
);
1885 if (!this_load_permuted
)
1887 load_permutation
.release ();
1890 SLP_TREE_LOAD_PERMUTATION (load_node
) = load_permutation
;
1891 loads_permuted
= true;
1896 if (!vect_supported_load_permutation_p (new_instance
))
1898 if (dump_enabled_p ())
1900 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1901 "Build SLP failed: unsupported load "
1903 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
1904 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1906 vect_free_slp_instance (new_instance
);
1913 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).safe_push (new_instance
);
1915 BB_VINFO_SLP_INSTANCES (bb_vinfo
).safe_push (new_instance
);
1917 if (dump_enabled_p ())
1918 vect_print_slp_tree (MSG_NOTE
, node
);
1923 /* Failed to SLP. */
1924 /* Free the allocated memory. */
1925 vect_free_slp_tree (node
);
1932 /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
1933 trees of packed scalar stmts if SLP is possible. */
1936 vect_analyze_slp (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
,
1937 unsigned max_tree_size
)
1940 vec
<gimple
> grouped_stores
;
1941 vec
<gimple
> reductions
= vNULL
;
1942 vec
<gimple
> reduc_chains
= vNULL
;
1943 gimple first_element
;
1946 if (dump_enabled_p ())
1947 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_analyze_slp ===\n");
1951 grouped_stores
= LOOP_VINFO_GROUPED_STORES (loop_vinfo
);
1952 reduc_chains
= LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
);
1953 reductions
= LOOP_VINFO_REDUCTIONS (loop_vinfo
);
1956 grouped_stores
= BB_VINFO_GROUPED_STORES (bb_vinfo
);
1958 /* Find SLP sequences starting from groups of grouped stores. */
1959 FOR_EACH_VEC_ELT (grouped_stores
, i
, first_element
)
1960 if (vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, first_element
,
1964 if (reduc_chains
.length () > 0)
1966 /* Find SLP sequences starting from reduction chains. */
1967 FOR_EACH_VEC_ELT (reduc_chains
, i
, first_element
)
1968 if (vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, first_element
,
1974 /* Don't try to vectorize SLP reductions if reduction chain was
1979 /* Find SLP sequences starting from groups of reductions. */
1980 if (reductions
.length () > 1
1981 && vect_analyze_slp_instance (loop_vinfo
, bb_vinfo
, reductions
[0],
1989 /* For each possible SLP instance decide whether to SLP it and calculate overall
1990 unrolling factor needed to SLP the loop. Return TRUE if decided to SLP at
1991 least one instance. */
1994 vect_make_slp_decision (loop_vec_info loop_vinfo
)
1996 unsigned int i
, unrolling_factor
= 1;
1997 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
1998 slp_instance instance
;
1999 int decided_to_slp
= 0;
2001 if (dump_enabled_p ())
2002 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_make_slp_decision ==="
2005 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2007 /* FORNOW: SLP if you can. */
2008 if (unrolling_factor
< SLP_INSTANCE_UNROLLING_FACTOR (instance
))
2009 unrolling_factor
= SLP_INSTANCE_UNROLLING_FACTOR (instance
);
2011 /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
2012 call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
2013 loop-based vectorization. Such stmts will be marked as HYBRID. */
2014 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2018 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
) = unrolling_factor
;
2020 if (decided_to_slp
&& dump_enabled_p ())
2021 dump_printf_loc (MSG_NOTE
, vect_location
,
2022 "Decided to SLP %d instances. Unrolling factor %d\n",
2023 decided_to_slp
, unrolling_factor
);
2025 return (decided_to_slp
> 0);
2029 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
2030 can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
2033 vect_detect_hybrid_slp_stmts (slp_tree node
, unsigned i
, slp_vect_type stype
)
2035 gimple stmt
= SLP_TREE_SCALAR_STMTS (node
)[i
];
2036 imm_use_iterator imm_iter
;
2038 stmt_vec_info use_vinfo
, stmt_vinfo
= vinfo_for_stmt (stmt
);
2040 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
2041 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2044 /* Propagate hybrid down the SLP tree. */
2045 if (stype
== hybrid
)
2047 else if (HYBRID_SLP_STMT (stmt_vinfo
))
2051 /* Check if a pure SLP stmt has uses in non-SLP stmts. */
2052 gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo
));
2053 /* We always get the pattern stmt here, but for immediate
2054 uses we have to use the LHS of the original stmt. */
2055 gcc_checking_assert (!STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
2056 if (STMT_VINFO_RELATED_STMT (stmt_vinfo
))
2057 stmt
= STMT_VINFO_RELATED_STMT (stmt_vinfo
);
2058 if (TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2059 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, gimple_op (stmt
, 0))
2061 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2063 use_vinfo
= vinfo_for_stmt (use_stmt
);
2064 if (STMT_VINFO_IN_PATTERN_P (use_vinfo
)
2065 && STMT_VINFO_RELATED_STMT (use_vinfo
))
2066 use_vinfo
= vinfo_for_stmt (STMT_VINFO_RELATED_STMT (use_vinfo
));
2067 if (!STMT_SLP_TYPE (use_vinfo
)
2068 && (STMT_VINFO_RELEVANT (use_vinfo
)
2069 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo
)))
2070 && !(gimple_code (use_stmt
) == GIMPLE_PHI
2071 && STMT_VINFO_DEF_TYPE (use_vinfo
) == vect_reduction_def
))
2076 if (stype
== hybrid
)
2078 if (dump_enabled_p ())
2080 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2081 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
2083 STMT_SLP_TYPE (stmt_vinfo
) = hybrid
;
2086 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2088 vect_detect_hybrid_slp_stmts (child
, i
, stype
);
2091 /* Helpers for vect_detect_hybrid_slp walking pattern stmt uses. */
2094 vect_detect_hybrid_slp_1 (tree
*tp
, int *, void *data
)
2096 walk_stmt_info
*wi
= (walk_stmt_info
*)data
;
2097 struct loop
*loopp
= (struct loop
*)wi
->info
;
2102 if (TREE_CODE (*tp
) == SSA_NAME
2103 && !SSA_NAME_IS_DEFAULT_DEF (*tp
))
2105 gimple def_stmt
= SSA_NAME_DEF_STMT (*tp
);
2106 if (flow_bb_inside_loop_p (loopp
, gimple_bb (def_stmt
))
2107 && PURE_SLP_STMT (vinfo_for_stmt (def_stmt
)))
2109 if (dump_enabled_p ())
2111 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2112 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2114 STMT_SLP_TYPE (vinfo_for_stmt (def_stmt
)) = hybrid
;
2122 vect_detect_hybrid_slp_2 (gimple_stmt_iterator
*gsi
, bool *handled
,
2125 /* If the stmt is in a SLP instance then this isn't a reason
2126 to mark use definitions in other SLP instances as hybrid. */
2127 if (STMT_SLP_TYPE (vinfo_for_stmt (gsi_stmt (*gsi
))) != loop_vect
)
2132 /* Find stmts that must be both vectorized and SLPed. */
2135 vect_detect_hybrid_slp (loop_vec_info loop_vinfo
)
2138 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2139 slp_instance instance
;
2141 if (dump_enabled_p ())
2142 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_detect_hybrid_slp ==="
2145 /* First walk all pattern stmt in the loop and mark defs of uses as
2146 hybrid because immediate uses in them are not recorded. */
2147 for (i
= 0; i
< LOOP_VINFO_LOOP (loop_vinfo
)->num_nodes
; ++i
)
2149 basic_block bb
= LOOP_VINFO_BBS (loop_vinfo
)[i
];
2150 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2153 gimple stmt
= gsi_stmt (gsi
);
2154 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2155 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
2158 memset (&wi
, 0, sizeof (wi
));
2159 wi
.info
= LOOP_VINFO_LOOP (loop_vinfo
);
2160 gimple_stmt_iterator gsi2
2161 = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info
));
2162 walk_gimple_stmt (&gsi2
, vect_detect_hybrid_slp_2
,
2163 vect_detect_hybrid_slp_1
, &wi
);
2164 walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
),
2165 vect_detect_hybrid_slp_2
,
2166 vect_detect_hybrid_slp_1
, &wi
);
2171 /* Then walk the SLP instance trees marking stmts with uses in
2172 non-SLP stmts as hybrid, also propagating hybrid down the
2173 SLP tree, collecting the above info on-the-fly. */
2174 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2176 for (unsigned i
= 0; i
< SLP_INSTANCE_GROUP_SIZE (instance
); ++i
)
2177 vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance
),
2183 /* Create and initialize a new bb_vec_info struct for BB, as well as
2184 stmt_vec_info structs for all the stmts in it. */
2187 new_bb_vec_info (basic_block bb
)
2189 bb_vec_info res
= NULL
;
2190 gimple_stmt_iterator gsi
;
2192 res
= (bb_vec_info
) xcalloc (1, sizeof (struct _bb_vec_info
));
2193 BB_VINFO_BB (res
) = bb
;
2195 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2197 gimple stmt
= gsi_stmt (gsi
);
2198 gimple_set_uid (stmt
, 0);
2199 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, NULL
, res
));
2202 BB_VINFO_GROUPED_STORES (res
).create (10);
2203 BB_VINFO_SLP_INSTANCES (res
).create (2);
2204 BB_VINFO_TARGET_COST_DATA (res
) = init_cost (NULL
);
2211 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
2212 stmts in the basic block. */
2215 destroy_bb_vec_info (bb_vec_info bb_vinfo
)
2217 vec
<slp_instance
> slp_instances
;
2218 slp_instance instance
;
2220 gimple_stmt_iterator si
;
2226 bb
= BB_VINFO_BB (bb_vinfo
);
2228 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2230 gimple stmt
= gsi_stmt (si
);
2231 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2234 /* Free stmt_vec_info. */
2235 free_stmt_vec_info (stmt
);
2238 vect_destroy_datarefs (NULL
, bb_vinfo
);
2239 free_dependence_relations (BB_VINFO_DDRS (bb_vinfo
));
2240 BB_VINFO_GROUPED_STORES (bb_vinfo
).release ();
2241 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2242 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2243 vect_free_slp_instance (instance
);
2244 BB_VINFO_SLP_INSTANCES (bb_vinfo
).release ();
2245 destroy_cost_data (BB_VINFO_TARGET_COST_DATA (bb_vinfo
));
2251 /* Analyze statements contained in SLP tree node after recursively analyzing
2252 the subtree. Return TRUE if the operations are supported. */
2255 vect_slp_analyze_node_operations (slp_tree node
)
2265 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2266 if (!vect_slp_analyze_node_operations (child
))
2269 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2271 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2272 gcc_assert (stmt_info
);
2273 gcc_assert (STMT_SLP_TYPE (stmt_info
) != loop_vect
);
2275 if (!vect_analyze_stmt (stmt
, &dummy
, node
))
2283 /* Analyze statements in SLP instances of the basic block. Return TRUE if the
2284 operations are supported. */
2287 vect_slp_analyze_operations (vec
<slp_instance
> slp_instances
, void *data
)
2289 slp_instance instance
;
2292 if (dump_enabled_p ())
2293 dump_printf_loc (MSG_NOTE
, vect_location
,
2294 "=== vect_slp_analyze_operations ===\n");
2296 for (i
= 0; slp_instances
.iterate (i
, &instance
); )
2298 if (!vect_slp_analyze_node_operations (SLP_INSTANCE_TREE (instance
)))
2300 dump_printf_loc (MSG_NOTE
, vect_location
,
2301 "removing SLP instance operations starting from: ");
2302 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
2303 SLP_TREE_SCALAR_STMTS
2304 (SLP_INSTANCE_TREE (instance
))[0], 0);
2305 vect_free_slp_instance (instance
);
2306 slp_instances
.ordered_remove (i
);
2310 /* Compute the costs of the SLP instance. */
2311 vect_analyze_slp_cost (instance
, data
);
2316 if (!slp_instances
.length ())
2323 /* Compute the scalar cost of the SLP node NODE and its children
2324 and return it. Do not account defs that are marked in LIFE and
2325 update LIFE according to uses of NODE. */
2328 vect_bb_slp_scalar_cost (basic_block bb
,
2329 slp_tree node
, vec
<bool, va_heap
> *life
)
2331 unsigned scalar_cost
= 0;
2336 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2339 ssa_op_iter op_iter
;
2340 def_operand_p def_p
;
2341 stmt_vec_info stmt_info
;
2346 /* If there is a non-vectorized use of the defs then the scalar
2347 stmt is kept live in which case we do not account it or any
2348 required defs in the SLP children in the scalar cost. This
2349 way we make the vectorization more costly when compared to
2351 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
2353 imm_use_iterator use_iter
;
2355 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, DEF_FROM_PTR (def_p
))
2356 if (!is_gimple_debug (use_stmt
)
2357 && (gimple_code (use_stmt
) == GIMPLE_PHI
2358 || gimple_bb (use_stmt
) != bb
2359 || !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (use_stmt
))))
2362 BREAK_FROM_IMM_USE_STMT (use_iter
);
2368 stmt_info
= vinfo_for_stmt (stmt
);
2369 if (STMT_VINFO_DATA_REF (stmt_info
))
2371 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)))
2372 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2374 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2377 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2379 scalar_cost
+= stmt_cost
;
2382 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2384 scalar_cost
+= vect_bb_slp_scalar_cost (bb
, child
, life
);
2389 /* Check if vectorization of the basic block is profitable. */
2392 vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo
)
2394 vec
<slp_instance
> slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2395 slp_instance instance
;
2397 unsigned int vec_inside_cost
= 0, vec_outside_cost
= 0, scalar_cost
= 0;
2398 unsigned int vec_prologue_cost
= 0, vec_epilogue_cost
= 0;
2400 /* Calculate scalar cost. */
2401 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2403 auto_vec
<bool, 20> life
;
2404 life
.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance
));
2405 scalar_cost
+= vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo
),
2406 SLP_INSTANCE_TREE (instance
),
2410 /* Complete the target-specific cost calculation. */
2411 finish_cost (BB_VINFO_TARGET_COST_DATA (bb_vinfo
), &vec_prologue_cost
,
2412 &vec_inside_cost
, &vec_epilogue_cost
);
2414 vec_outside_cost
= vec_prologue_cost
+ vec_epilogue_cost
;
2416 if (dump_enabled_p ())
2418 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2419 dump_printf (MSG_NOTE
, " Vector inside of basic block cost: %d\n",
2421 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n", vec_prologue_cost
);
2422 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n", vec_epilogue_cost
);
2423 dump_printf (MSG_NOTE
, " Scalar cost of basic block: %d\n", scalar_cost
);
2426 /* Vectorization is profitable if its cost is less than the cost of scalar
2428 if (vec_outside_cost
+ vec_inside_cost
>= scalar_cost
)
2434 /* Check if the basic block can be vectorized. */
2437 vect_slp_analyze_bb_1 (basic_block bb
)
2439 bb_vec_info bb_vinfo
;
2440 vec
<slp_instance
> slp_instances
;
2441 slp_instance instance
;
2444 unsigned n_stmts
= 0;
2446 bb_vinfo
= new_bb_vec_info (bb
);
2450 if (!vect_analyze_data_refs (NULL
, bb_vinfo
, &min_vf
, &n_stmts
))
2452 if (dump_enabled_p ())
2453 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2454 "not vectorized: unhandled data-ref in basic "
2457 destroy_bb_vec_info (bb_vinfo
);
2461 if (BB_VINFO_DATAREFS (bb_vinfo
).length () < 2)
2463 if (dump_enabled_p ())
2464 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2465 "not vectorized: not enough data-refs in "
2468 destroy_bb_vec_info (bb_vinfo
);
2472 if (!vect_analyze_data_ref_accesses (NULL
, bb_vinfo
))
2474 if (dump_enabled_p ())
2475 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2476 "not vectorized: unhandled data access in "
2479 destroy_bb_vec_info (bb_vinfo
);
2483 vect_pattern_recog (NULL
, bb_vinfo
);
2485 if (!vect_analyze_data_refs_alignment (NULL
, bb_vinfo
))
2487 if (dump_enabled_p ())
2488 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2489 "not vectorized: bad data alignment in basic "
2492 destroy_bb_vec_info (bb_vinfo
);
2496 /* Check the SLP opportunities in the basic block, analyze and build SLP
2498 if (!vect_analyze_slp (NULL
, bb_vinfo
, n_stmts
))
2500 if (dump_enabled_p ())
2502 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2503 "Failed to SLP the basic block.\n");
2504 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2505 "not vectorized: failed to find SLP opportunities "
2506 "in basic block.\n");
2509 destroy_bb_vec_info (bb_vinfo
);
2513 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2515 /* Mark all the statements that we want to vectorize as pure SLP and
2517 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2519 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2520 vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance
));
2523 /* Mark all the statements that we do not want to vectorize. */
2524 for (gimple_stmt_iterator gsi
= gsi_start_bb (BB_VINFO_BB (bb_vinfo
));
2525 !gsi_end_p (gsi
); gsi_next (&gsi
))
2527 stmt_vec_info vinfo
= vinfo_for_stmt (gsi_stmt (gsi
));
2528 if (STMT_SLP_TYPE (vinfo
) != pure_slp
)
2529 STMT_VINFO_VECTORIZABLE (vinfo
) = false;
2532 /* Analyze dependences. At this point all stmts not participating in
2533 vectorization have to be marked. Dependence analysis assumes
2534 that we either vectorize all SLP instances or none at all. */
2535 if (!vect_slp_analyze_data_ref_dependences (bb_vinfo
))
2537 if (dump_enabled_p ())
2538 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2539 "not vectorized: unhandled data dependence "
2540 "in basic block.\n");
2542 destroy_bb_vec_info (bb_vinfo
);
2546 if (!vect_verify_datarefs_alignment (NULL
, bb_vinfo
))
2548 if (dump_enabled_p ())
2549 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2550 "not vectorized: unsupported alignment in basic "
2552 destroy_bb_vec_info (bb_vinfo
);
2556 if (!vect_slp_analyze_operations (BB_VINFO_SLP_INSTANCES (bb_vinfo
),
2557 BB_VINFO_TARGET_COST_DATA (bb_vinfo
)))
2559 if (dump_enabled_p ())
2560 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2561 "not vectorized: bad operation in basic block.\n");
2563 destroy_bb_vec_info (bb_vinfo
);
2567 /* Cost model: check if the vectorization is worthwhile. */
2568 if (!unlimited_cost_model (NULL
)
2569 && !vect_bb_vectorization_profitable_p (bb_vinfo
))
2571 if (dump_enabled_p ())
2572 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2573 "not vectorized: vectorization is not "
2576 destroy_bb_vec_info (bb_vinfo
);
2580 if (dump_enabled_p ())
2581 dump_printf_loc (MSG_NOTE
, vect_location
,
2582 "Basic block will be vectorized using SLP\n");
2589 vect_slp_analyze_bb (basic_block bb
)
2591 bb_vec_info bb_vinfo
;
2593 gimple_stmt_iterator gsi
;
2594 unsigned int vector_sizes
;
2596 if (dump_enabled_p ())
2597 dump_printf_loc (MSG_NOTE
, vect_location
, "===vect_slp_analyze_bb===\n");
2599 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2601 gimple stmt
= gsi_stmt (gsi
);
2602 if (!is_gimple_debug (stmt
)
2603 && !gimple_nop_p (stmt
)
2604 && gimple_code (stmt
) != GIMPLE_LABEL
)
2608 if (insns
> PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB
))
2610 if (dump_enabled_p ())
2611 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2612 "not vectorized: too many instructions in "
2618 /* Autodetect first vector size we try. */
2619 current_vector_size
= 0;
2620 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2624 bb_vinfo
= vect_slp_analyze_bb_1 (bb
);
2628 destroy_bb_vec_info (bb_vinfo
);
2630 vector_sizes
&= ~current_vector_size
;
2631 if (vector_sizes
== 0
2632 || current_vector_size
== 0)
2635 /* Try the next biggest vector size. */
2636 current_vector_size
= 1 << floor_log2 (vector_sizes
);
2637 if (dump_enabled_p ())
2638 dump_printf_loc (MSG_NOTE
, vect_location
,
2639 "***** Re-trying analysis with "
2640 "vector size %d\n", current_vector_size
);
2645 /* For constant and loop invariant defs of SLP_NODE this function returns
2646 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
2647 OP_NUM determines if we gather defs for operand 0 or operand 1 of the RHS of
2648 scalar stmts. NUMBER_OF_VECTORS is the number of vector defs to create.
2649 REDUC_INDEX is the index of the reduction operand in the statements, unless
2653 vect_get_constant_vectors (tree op
, slp_tree slp_node
,
2654 vec
<tree
> *vec_oprnds
,
2655 unsigned int op_num
, unsigned int number_of_vectors
,
2658 vec
<gimple
> stmts
= SLP_TREE_SCALAR_STMTS (slp_node
);
2659 gimple stmt
= stmts
[0];
2660 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2664 unsigned j
, number_of_places_left_in_vector
;
2667 int group_size
= stmts
.length ();
2668 unsigned int vec_num
, i
;
2669 unsigned number_of_copies
= 1;
2671 voprnds
.create (number_of_vectors
);
2672 bool constant_p
, is_store
;
2673 tree neutral_op
= NULL
;
2674 enum tree_code code
= gimple_expr_code (stmt
);
2677 gimple_seq ctor_seq
= NULL
;
2679 vector_type
= get_vectype_for_scalar_type (TREE_TYPE (op
));
2680 nunits
= TYPE_VECTOR_SUBPARTS (vector_type
);
2682 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_reduction_def
2683 && reduc_index
!= -1)
2685 op_num
= reduc_index
;
2686 op
= gimple_op (stmt
, op_num
+ 1);
2687 /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
2688 we need either neutral operands or the original operands. See
2689 get_initial_def_for_reduction() for details. */
2692 case WIDEN_SUM_EXPR
:
2699 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2700 neutral_op
= build_real (TREE_TYPE (op
), dconst0
);
2702 neutral_op
= build_int_cst (TREE_TYPE (op
), 0);
2707 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2708 neutral_op
= build_real (TREE_TYPE (op
), dconst1
);
2710 neutral_op
= build_int_cst (TREE_TYPE (op
), 1);
2715 neutral_op
= build_int_cst (TREE_TYPE (op
), -1);
2718 /* For MIN/MAX we don't have an easy neutral operand but
2719 the initial values can be used fine here. Only for
2720 a reduction chain we have to force a neutral element. */
2723 if (!GROUP_FIRST_ELEMENT (stmt_vinfo
))
2727 def_stmt
= SSA_NAME_DEF_STMT (op
);
2728 loop
= (gimple_bb (stmt
))->loop_father
;
2729 neutral_op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2730 loop_preheader_edge (loop
));
2735 gcc_assert (!GROUP_FIRST_ELEMENT (stmt_vinfo
));
2740 if (STMT_VINFO_DATA_REF (stmt_vinfo
))
2743 op
= gimple_assign_rhs1 (stmt
);
2750 if (CONSTANT_CLASS_P (op
))
2755 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
2756 created vectors. It is greater than 1 if unrolling is performed.
2758 For example, we have two scalar operands, s1 and s2 (e.g., group of
2759 strided accesses of size two), while NUNITS is four (i.e., four scalars
2760 of this type can be packed in a vector). The output vector will contain
2761 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
2764 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
2765 containing the operands.
2767 For example, NUNITS is four as before, and the group size is 8
2768 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
2769 {s5, s6, s7, s8}. */
2771 number_of_copies
= nunits
* number_of_vectors
/ group_size
;
2773 number_of_places_left_in_vector
= nunits
;
2774 elts
= XALLOCAVEC (tree
, nunits
);
2775 bool place_after_defs
= false;
2776 for (j
= 0; j
< number_of_copies
; j
++)
2778 for (i
= group_size
- 1; stmts
.iterate (i
, &stmt
); i
--)
2781 op
= gimple_assign_rhs1 (stmt
);
2787 if (op_num
== 0 || op_num
== 1)
2789 tree cond
= gimple_assign_rhs1 (stmt
);
2790 op
= TREE_OPERAND (cond
, op_num
);
2795 op
= gimple_assign_rhs2 (stmt
);
2797 op
= gimple_assign_rhs3 (stmt
);
2802 op
= gimple_call_arg (stmt
, op_num
);
2809 op
= gimple_op (stmt
, op_num
+ 1);
2810 /* Unlike the other binary operators, shifts/rotates have
2811 the shift count being int, instead of the same type as
2812 the lhs, so make sure the scalar is the right type if
2813 we are dealing with vectors of
2814 long long/long/short/char. */
2815 if (op_num
== 1 && TREE_CODE (op
) == INTEGER_CST
)
2816 op
= fold_convert (TREE_TYPE (vector_type
), op
);
2820 op
= gimple_op (stmt
, op_num
+ 1);
2825 if (reduc_index
!= -1)
2827 loop
= (gimple_bb (stmt
))->loop_father
;
2828 def_stmt
= SSA_NAME_DEF_STMT (op
);
2832 /* Get the def before the loop. In reduction chain we have only
2833 one initial value. */
2834 if ((j
!= (number_of_copies
- 1)
2835 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
2840 op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2841 loop_preheader_edge (loop
));
2844 /* Create 'vect_ = {op0,op1,...,opn}'. */
2845 number_of_places_left_in_vector
--;
2847 if (!types_compatible_p (TREE_TYPE (vector_type
), TREE_TYPE (op
)))
2849 if (CONSTANT_CLASS_P (op
))
2851 op
= fold_unary (VIEW_CONVERT_EXPR
,
2852 TREE_TYPE (vector_type
), op
);
2853 gcc_assert (op
&& CONSTANT_CLASS_P (op
));
2857 tree new_temp
= make_ssa_name (TREE_TYPE (vector_type
));
2859 op
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (vector_type
), op
);
2861 = gimple_build_assign (new_temp
, VIEW_CONVERT_EXPR
, op
);
2862 gimple_seq_add_stmt (&ctor_seq
, init_stmt
);
2866 elts
[number_of_places_left_in_vector
] = op
;
2867 if (!CONSTANT_CLASS_P (op
))
2869 if (TREE_CODE (orig_op
) == SSA_NAME
2870 && !SSA_NAME_IS_DEFAULT_DEF (orig_op
)
2871 && STMT_VINFO_BB_VINFO (stmt_vinfo
)
2872 && (STMT_VINFO_BB_VINFO (stmt_vinfo
)->bb
2873 == gimple_bb (SSA_NAME_DEF_STMT (orig_op
))))
2874 place_after_defs
= true;
2876 if (number_of_places_left_in_vector
== 0)
2878 number_of_places_left_in_vector
= nunits
;
2881 vec_cst
= build_vector (vector_type
, elts
);
2884 vec
<constructor_elt
, va_gc
> *v
;
2886 vec_alloc (v
, nunits
);
2887 for (k
= 0; k
< nunits
; ++k
)
2888 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[k
]);
2889 vec_cst
= build_constructor (vector_type
, v
);
2892 gimple_stmt_iterator gsi
;
2893 if (place_after_defs
)
2896 (vect_find_last_scalar_stmt_in_slp (slp_node
));
2897 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, &gsi
);
2900 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, NULL
);
2901 if (ctor_seq
!= NULL
)
2903 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (init
));
2904 gsi_insert_seq_before_without_update (&gsi
, ctor_seq
,
2908 voprnds
.quick_push (init
);
2909 place_after_defs
= false;
2914 /* Since the vectors are created in the reverse order, we should invert
2916 vec_num
= voprnds
.length ();
2917 for (j
= vec_num
; j
!= 0; j
--)
2919 vop
= voprnds
[j
- 1];
2920 vec_oprnds
->quick_push (vop
);
2925 /* In case that VF is greater than the unrolling factor needed for the SLP
2926 group of stmts, NUMBER_OF_VECTORS to be created is greater than
2927 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
2928 to replicate the vectors. */
2929 while (number_of_vectors
> vec_oprnds
->length ())
2931 tree neutral_vec
= NULL
;
2936 neutral_vec
= build_vector_from_val (vector_type
, neutral_op
);
2938 vec_oprnds
->quick_push (neutral_vec
);
2942 for (i
= 0; vec_oprnds
->iterate (i
, &vop
) && i
< vec_num
; i
++)
2943 vec_oprnds
->quick_push (vop
);
2949 /* Get vectorized definitions from SLP_NODE that contains corresponding
2950 vectorized def-stmts. */
2953 vect_get_slp_vect_defs (slp_tree slp_node
, vec
<tree
> *vec_oprnds
)
2956 gimple vec_def_stmt
;
2959 gcc_assert (SLP_TREE_VEC_STMTS (slp_node
).exists ());
2961 FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (slp_node
), i
, vec_def_stmt
)
2963 gcc_assert (vec_def_stmt
);
2964 vec_oprnd
= gimple_get_lhs (vec_def_stmt
);
2965 vec_oprnds
->quick_push (vec_oprnd
);
2970 /* Get vectorized definitions for SLP_NODE.
2971 If the scalar definitions are loop invariants or constants, collect them and
2972 call vect_get_constant_vectors() to create vector stmts.
2973 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
2974 must be stored in the corresponding child of SLP_NODE, and we call
2975 vect_get_slp_vect_defs () to retrieve them. */
2978 vect_get_slp_defs (vec
<tree
> ops
, slp_tree slp_node
,
2979 vec
<vec
<tree
> > *vec_oprnds
, int reduc_index
)
2982 int number_of_vects
= 0, i
;
2983 unsigned int child_index
= 0;
2984 HOST_WIDE_INT lhs_size_unit
, rhs_size_unit
;
2985 slp_tree child
= NULL
;
2988 bool vectorized_defs
;
2990 first_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[0];
2991 FOR_EACH_VEC_ELT (ops
, i
, oprnd
)
2993 /* For each operand we check if it has vectorized definitions in a child
2994 node or we need to create them (for invariants and constants). We
2995 check if the LHS of the first stmt of the next child matches OPRND.
2996 If it does, we found the correct child. Otherwise, we call
2997 vect_get_constant_vectors (), and not advance CHILD_INDEX in order
2998 to check this child node for the next operand. */
2999 vectorized_defs
= false;
3000 if (SLP_TREE_CHILDREN (slp_node
).length () > child_index
)
3002 child
= SLP_TREE_CHILDREN (slp_node
)[child_index
];
3004 /* We have to check both pattern and original def, if available. */
3007 gimple first_def
= SLP_TREE_SCALAR_STMTS (child
)[0];
3009 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def
));
3011 if (operand_equal_p (oprnd
, gimple_get_lhs (first_def
), 0)
3013 && operand_equal_p (oprnd
, gimple_get_lhs (related
), 0)))
3015 /* The number of vector defs is determined by the number of
3016 vector statements in the node from which we get those
3018 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (child
);
3019 vectorized_defs
= true;
3027 if (!vectorized_defs
)
3031 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
3032 /* Number of vector stmts was calculated according to LHS in
3033 vect_schedule_slp_instance (), fix it by replacing LHS with
3034 RHS, if necessary. See vect_get_smallest_scalar_type () for
3036 vect_get_smallest_scalar_type (first_stmt
, &lhs_size_unit
,
3038 if (rhs_size_unit
!= lhs_size_unit
)
3040 number_of_vects
*= rhs_size_unit
;
3041 number_of_vects
/= lhs_size_unit
;
3046 /* Allocate memory for vectorized defs. */
3048 vec_defs
.create (number_of_vects
);
3050 /* For reduction defs we call vect_get_constant_vectors (), since we are
3051 looking for initial loop invariant values. */
3052 if (vectorized_defs
&& reduc_index
== -1)
3053 /* The defs are already vectorized. */
3054 vect_get_slp_vect_defs (child
, &vec_defs
);
3056 /* Build vectors from scalar defs. */
3057 vect_get_constant_vectors (oprnd
, slp_node
, &vec_defs
, i
,
3058 number_of_vects
, reduc_index
);
3060 vec_oprnds
->quick_push (vec_defs
);
3062 /* For reductions, we only need initial values. */
3063 if (reduc_index
!= -1)
3069 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
3070 building a vector of type MASK_TYPE from it) and two input vectors placed in
3071 DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
3072 shifting by STRIDE elements of DR_CHAIN for every copy.
3073 (STRIDE is the number of vectorized stmts for NODE divided by the number of
3075 VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
3076 the created stmts must be inserted. */
3079 vect_create_mask_and_perm (gimple stmt
, gimple next_scalar_stmt
,
3080 tree mask
, int first_vec_indx
, int second_vec_indx
,
3081 gimple_stmt_iterator
*gsi
, slp_tree node
,
3082 tree vectype
, vec
<tree
> dr_chain
,
3083 int ncopies
, int vect_stmts_counter
)
3086 gimple perm_stmt
= NULL
;
3087 stmt_vec_info next_stmt_info
;
3089 tree first_vec
, second_vec
, data_ref
;
3091 stride
= SLP_TREE_NUMBER_OF_VEC_STMTS (node
) / ncopies
;
3093 /* Initialize the vect stmts of NODE to properly insert the generated
3095 for (i
= SLP_TREE_VEC_STMTS (node
).length ();
3096 i
< (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node
); i
++)
3097 SLP_TREE_VEC_STMTS (node
).quick_push (NULL
);
3099 perm_dest
= vect_create_destination_var (gimple_assign_lhs (stmt
), vectype
);
3100 for (i
= 0; i
< ncopies
; i
++)
3102 first_vec
= dr_chain
[first_vec_indx
];
3103 second_vec
= dr_chain
[second_vec_indx
];
3105 /* Generate the permute statement. */
3106 perm_stmt
= gimple_build_assign (perm_dest
, VEC_PERM_EXPR
,
3107 first_vec
, second_vec
, mask
);
3108 data_ref
= make_ssa_name (perm_dest
, perm_stmt
);
3109 gimple_set_lhs (perm_stmt
, data_ref
);
3110 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
3112 /* Store the vector statement in NODE. */
3113 SLP_TREE_VEC_STMTS (node
)[stride
* i
+ vect_stmts_counter
] = perm_stmt
;
3115 first_vec_indx
+= stride
;
3116 second_vec_indx
+= stride
;
3119 /* Mark the scalar stmt as vectorized. */
3120 next_stmt_info
= vinfo_for_stmt (next_scalar_stmt
);
3121 STMT_VINFO_VEC_STMT (next_stmt_info
) = perm_stmt
;
3125 /* Given FIRST_MASK_ELEMENT - the mask element in element representation,
3126 return in CURRENT_MASK_ELEMENT its equivalent in target specific
3127 representation. Check that the mask is valid and return FALSE if not.
3128 Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
3129 the next vector, i.e., the current first vector is not needed. */
3132 vect_get_mask_element (gimple stmt
, int first_mask_element
, int m
,
3133 int mask_nunits
, bool only_one_vec
, int index
,
3134 unsigned char *mask
, int *current_mask_element
,
3135 bool *need_next_vector
, int *number_of_mask_fixes
,
3136 bool *mask_fixed
, bool *needs_first_vector
)
3140 /* Convert to target specific representation. */
3141 *current_mask_element
= first_mask_element
+ m
;
3142 /* Adjust the value in case it's a mask for second and third vectors. */
3143 *current_mask_element
-= mask_nunits
* (*number_of_mask_fixes
- 1);
3145 if (*current_mask_element
< 0)
3147 if (dump_enabled_p ())
3149 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3150 "permutation requires past vector ");
3151 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3152 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3157 if (*current_mask_element
< mask_nunits
)
3158 *needs_first_vector
= true;
3160 /* We have only one input vector to permute but the mask accesses values in
3161 the next vector as well. */
3162 if (only_one_vec
&& *current_mask_element
>= mask_nunits
)
3164 if (dump_enabled_p ())
3166 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3167 "permutation requires at least two vectors ");
3168 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3169 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3175 /* The mask requires the next vector. */
3176 while (*current_mask_element
>= mask_nunits
* 2)
3178 if (*needs_first_vector
|| *mask_fixed
)
3180 /* We either need the first vector too or have already moved to the
3181 next vector. In both cases, this permutation needs three
3183 if (dump_enabled_p ())
3185 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3186 "permutation requires at "
3187 "least three vectors ");
3188 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3189 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3195 /* We move to the next vector, dropping the first one and working with
3196 the second and the third - we need to adjust the values of the mask
3198 *current_mask_element
-= mask_nunits
* *number_of_mask_fixes
;
3200 for (i
= 0; i
< index
; i
++)
3201 mask
[i
] -= mask_nunits
* *number_of_mask_fixes
;
3203 (*number_of_mask_fixes
)++;
3207 *need_next_vector
= *mask_fixed
;
3209 /* This was the last element of this mask. Start a new one. */
3210 if (index
== mask_nunits
- 1)
3212 *number_of_mask_fixes
= 1;
3213 *mask_fixed
= false;
3214 *needs_first_vector
= false;
3221 /* Generate vector permute statements from a list of loads in DR_CHAIN.
3222 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
3223 permute statements for the SLP node NODE of the SLP instance
3224 SLP_NODE_INSTANCE. */
3227 vect_transform_slp_perm_load (slp_tree node
, vec
<tree
> dr_chain
,
3228 gimple_stmt_iterator
*gsi
, int vf
,
3229 slp_instance slp_node_instance
, bool analyze_only
)
3231 gimple stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3232 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3233 tree mask_element_type
= NULL_TREE
, mask_type
;
3234 int i
, j
, k
, nunits
, vec_index
= 0, scalar_index
;
3235 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3236 gimple next_scalar_stmt
;
3237 int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_node_instance
);
3238 int first_mask_element
;
3239 int index
, unroll_factor
, current_mask_element
, ncopies
;
3240 unsigned char *mask
;
3241 bool only_one_vec
= false, need_next_vector
= false;
3242 int first_vec_index
, second_vec_index
, orig_vec_stmts_num
, vect_stmts_counter
;
3243 int number_of_mask_fixes
= 1;
3244 bool mask_fixed
= false;
3245 bool needs_first_vector
= false;
3248 mode
= TYPE_MODE (vectype
);
3250 if (!can_vec_perm_p (mode
, false, NULL
))
3252 if (dump_enabled_p ())
3254 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3255 "no vect permute for ");
3256 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3257 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3262 /* The generic VEC_PERM_EXPR code always uses an integral type of the
3263 same size as the vector element being permuted. */
3264 mask_element_type
= lang_hooks
.types
.type_for_mode
3265 (int_mode_for_mode (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3266 mask_type
= get_vectype_for_scalar_type (mask_element_type
);
3267 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3268 mask
= XALLOCAVEC (unsigned char, nunits
);
3269 unroll_factor
= SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3271 /* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
3272 unrolling factor. */
3273 orig_vec_stmts_num
= group_size
*
3274 SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
) / nunits
;
3275 if (orig_vec_stmts_num
== 1)
3276 only_one_vec
= true;
3278 /* Number of copies is determined by the final vectorization factor
3279 relatively to SLP_NODE_INSTANCE unrolling factor. */
3280 ncopies
= vf
/ SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3282 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3285 /* Generate permutation masks for every NODE. Number of masks for each NODE
3286 is equal to GROUP_SIZE.
3287 E.g., we have a group of three nodes with three loads from the same
3288 location in each node, and the vector size is 4. I.e., we have a
3289 a0b0c0a1b1c1... sequence and we need to create the following vectors:
3290 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
3291 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
3294 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9}.
3295 The last mask is illegal since we assume two operands for permute
3296 operation, and the mask element values can't be outside that range.
3297 Hence, the last mask must be converted into {2,5,5,5}.
3298 For the first two permutations we need the first and the second input
3299 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
3300 we need the second and the third vectors: {b1,c1,a2,b2} and
3306 vect_stmts_counter
= 0;
3308 first_vec_index
= vec_index
++;
3310 second_vec_index
= first_vec_index
;
3312 second_vec_index
= vec_index
++;
3314 for (j
= 0; j
< unroll_factor
; j
++)
3316 for (k
= 0; k
< group_size
; k
++)
3318 i
= SLP_TREE_LOAD_PERMUTATION (node
)[k
];
3319 first_mask_element
= i
+ j
* group_size
;
3320 if (!vect_get_mask_element (stmt
, first_mask_element
, 0,
3321 nunits
, only_one_vec
, index
,
3322 mask
, ¤t_mask_element
,
3324 &number_of_mask_fixes
, &mask_fixed
,
3325 &needs_first_vector
))
3327 gcc_assert (current_mask_element
>= 0
3328 && current_mask_element
< 2 * nunits
);
3329 mask
[index
++] = current_mask_element
;
3331 if (index
== nunits
)
3334 if (!can_vec_perm_p (mode
, false, mask
))
3336 if (dump_enabled_p ())
3338 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
3340 "unsupported vect permute { ");
3341 for (i
= 0; i
< nunits
; ++i
)
3342 dump_printf (MSG_MISSED_OPTIMIZATION
, "%d ",
3344 dump_printf (MSG_MISSED_OPTIMIZATION
, "}\n");
3352 tree mask_vec
, *mask_elts
;
3353 mask_elts
= XALLOCAVEC (tree
, nunits
);
3354 for (l
= 0; l
< nunits
; ++l
)
3355 mask_elts
[l
] = build_int_cst (mask_element_type
,
3357 mask_vec
= build_vector (mask_type
, mask_elts
);
3359 if (need_next_vector
)
3361 first_vec_index
= second_vec_index
;
3362 second_vec_index
= vec_index
;
3366 = SLP_TREE_SCALAR_STMTS (node
)[scalar_index
++];
3368 vect_create_mask_and_perm (stmt
, next_scalar_stmt
,
3369 mask_vec
, first_vec_index
, second_vec_index
,
3370 gsi
, node
, vectype
, dr_chain
,
3371 ncopies
, vect_stmts_counter
++);
3383 /* Vectorize SLP instance tree in postorder. */
3386 vect_schedule_slp_instance (slp_tree node
, slp_instance instance
,
3387 unsigned int vectorization_factor
)
3390 bool grouped_store
, is_store
;
3391 gimple_stmt_iterator si
;
3392 stmt_vec_info stmt_info
;
3393 unsigned int vec_stmts_size
, nunits
, group_size
;
3401 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3402 vect_schedule_slp_instance (child
, instance
, vectorization_factor
);
3404 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3405 stmt_info
= vinfo_for_stmt (stmt
);
3407 /* VECTYPE is the type of the destination. */
3408 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3409 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (vectype
);
3410 group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
3412 /* For each SLP instance calculate number of vector stmts to be created
3413 for the scalar stmts in each node of the SLP tree. Number of vector
3414 elements in one vector iteration is the number of scalar elements in
3415 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
3417 Unless this is a SLP reduction in which case the number of vector
3418 stmts is equal to the number of vector stmts of the children. */
3419 if (GROUP_FIRST_ELEMENT (stmt_info
)
3420 && !STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3421 vec_stmts_size
= SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_CHILDREN (node
)[0]);
3423 vec_stmts_size
= (vectorization_factor
* group_size
) / nunits
;
3425 if (!SLP_TREE_VEC_STMTS (node
).exists ())
3427 SLP_TREE_VEC_STMTS (node
).create (vec_stmts_size
);
3428 SLP_TREE_NUMBER_OF_VEC_STMTS (node
) = vec_stmts_size
;
3431 if (dump_enabled_p ())
3433 dump_printf_loc (MSG_NOTE
,vect_location
,
3434 "------>vectorizing SLP node starting from: ");
3435 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3436 dump_printf (MSG_NOTE
, "\n");
3439 /* Vectorized stmts go before the last scalar stmt which is where
3440 all uses are ready. */
3441 si
= gsi_for_stmt (vect_find_last_scalar_stmt_in_slp (node
));
3443 /* Mark the first element of the reduction chain as reduction to properly
3444 transform the node. In the analysis phase only the last element of the
3445 chain is marked as reduction. */
3446 if (GROUP_FIRST_ELEMENT (stmt_info
) && !STMT_VINFO_GROUPED_ACCESS (stmt_info
)
3447 && GROUP_FIRST_ELEMENT (stmt_info
) == stmt
)
3449 STMT_VINFO_DEF_TYPE (stmt_info
) = vect_reduction_def
;
3450 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
3453 /* Handle two-operation SLP nodes by vectorizing the group with
3454 both operations and then performing a merge. */
3455 if (SLP_TREE_TWO_OPERATORS (node
))
3457 enum tree_code code0
= gimple_assign_rhs_code (stmt
);
3458 enum tree_code ocode
;
3460 unsigned char *mask
= XALLOCAVEC (unsigned char, group_size
);
3461 bool allsame
= true;
3462 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, ostmt
)
3463 if (gimple_assign_rhs_code (ostmt
) != code0
)
3467 ocode
= gimple_assign_rhs_code (ostmt
);
3476 tree tmask
= NULL_TREE
;
3477 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3478 v0
= SLP_TREE_VEC_STMTS (node
).copy ();
3479 SLP_TREE_VEC_STMTS (node
).truncate (0);
3480 gimple_assign_set_rhs_code (stmt
, ocode
);
3481 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3482 gimple_assign_set_rhs_code (stmt
, code0
);
3483 v1
= SLP_TREE_VEC_STMTS (node
).copy ();
3484 SLP_TREE_VEC_STMTS (node
).truncate (0);
3485 tree meltype
= build_nonstandard_integer_type
3486 (GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3487 tree mvectype
= get_same_sized_vectype (meltype
, vectype
);
3489 for (j
= 0; j
< v0
.length (); ++j
)
3491 tree
*melts
= XALLOCAVEC (tree
, TYPE_VECTOR_SUBPARTS (vectype
));
3492 for (l
= 0; l
< TYPE_VECTOR_SUBPARTS (vectype
); ++l
)
3494 if (k
>= group_size
)
3496 melts
[l
] = build_int_cst
3497 (meltype
, mask
[k
++] * TYPE_VECTOR_SUBPARTS (vectype
) + l
);
3499 tmask
= build_vector (mvectype
, melts
);
3501 /* ??? Not all targets support a VEC_PERM_EXPR with a
3502 constant mask that would translate to a vec_merge RTX
3503 (with their vec_perm_const_ok). We can either not
3504 vectorize in that case or let veclower do its job.
3505 Unfortunately that isn't too great and at least for
3506 plus/minus we'd eventually like to match targets
3507 vector addsub instructions. */
3509 vstmt
= gimple_build_assign (make_ssa_name (vectype
),
3511 gimple_assign_lhs (v0
[j
]),
3512 gimple_assign_lhs (v1
[j
]), tmask
);
3513 vect_finish_stmt_generation (stmt
, vstmt
, &si
);
3514 SLP_TREE_VEC_STMTS (node
).quick_push (vstmt
);
3521 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3525 /* Replace scalar calls from SLP node NODE with setting of their lhs to zero.
3526 For loop vectorization this is done in vectorizable_call, but for SLP
3527 it needs to be deferred until end of vect_schedule_slp, because multiple
3528 SLP instances may refer to the same scalar stmt. */
3531 vect_remove_slp_scalar_calls (slp_tree node
)
3533 gimple stmt
, new_stmt
;
3534 gimple_stmt_iterator gsi
;
3538 stmt_vec_info stmt_info
;
3543 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3544 vect_remove_slp_scalar_calls (child
);
3546 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
3548 if (!is_gimple_call (stmt
) || gimple_bb (stmt
) == NULL
)
3550 stmt_info
= vinfo_for_stmt (stmt
);
3551 if (stmt_info
== NULL
3552 || is_pattern_stmt_p (stmt_info
)
3553 || !PURE_SLP_STMT (stmt_info
))
3555 lhs
= gimple_call_lhs (stmt
);
3556 new_stmt
= gimple_build_assign (lhs
, build_zero_cst (TREE_TYPE (lhs
)));
3557 set_vinfo_for_stmt (new_stmt
, stmt_info
);
3558 set_vinfo_for_stmt (stmt
, NULL
);
3559 STMT_VINFO_STMT (stmt_info
) = new_stmt
;
3560 gsi
= gsi_for_stmt (stmt
);
3561 gsi_replace (&gsi
, new_stmt
, false);
3562 SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt
)) = new_stmt
;
3566 /* Generate vector code for all SLP instances in the loop/basic block. */
3569 vect_schedule_slp (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
)
3571 vec
<slp_instance
> slp_instances
;
3572 slp_instance instance
;
3574 bool is_store
= false;
3578 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
3579 vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3583 slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
3587 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3589 /* Schedule the tree of INSTANCE. */
3590 is_store
= vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance
),
3592 if (dump_enabled_p ())
3593 dump_printf_loc (MSG_NOTE
, vect_location
,
3594 "vectorizing stmts using SLP.\n");
3597 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3599 slp_tree root
= SLP_INSTANCE_TREE (instance
);
3602 gimple_stmt_iterator gsi
;
3604 /* Remove scalar call stmts. Do not do this for basic-block
3605 vectorization as not all uses may be vectorized.
3606 ??? Why should this be necessary? DCE should be able to
3607 remove the stmts itself.
3608 ??? For BB vectorization we can as well remove scalar
3609 stmts starting from the SLP tree root if they have no
3612 vect_remove_slp_scalar_calls (root
);
3614 for (j
= 0; SLP_TREE_SCALAR_STMTS (root
).iterate (j
, &store
)
3615 && j
< SLP_INSTANCE_GROUP_SIZE (instance
); j
++)
3617 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store
)))
3620 if (is_pattern_stmt_p (vinfo_for_stmt (store
)))
3621 store
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (store
));
3622 /* Free the attached stmt_vec_info and remove the stmt. */
3623 gsi
= gsi_for_stmt (store
);
3624 unlink_stmt_vdef (store
);
3625 gsi_remove (&gsi
, true);
3626 release_defs (store
);
3627 free_stmt_vec_info (store
);
3635 /* Vectorize the basic block. */
3638 vect_slp_transform_bb (basic_block bb
)
3640 bb_vec_info bb_vinfo
= vec_info_for_bb (bb
);
3641 gimple_stmt_iterator si
;
3643 gcc_assert (bb_vinfo
);
3645 if (dump_enabled_p ())
3646 dump_printf_loc (MSG_NOTE
, vect_location
, "SLPing BB\n");
3648 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
3650 gimple stmt
= gsi_stmt (si
);
3651 stmt_vec_info stmt_info
;
3653 if (dump_enabled_p ())
3655 dump_printf_loc (MSG_NOTE
, vect_location
,
3656 "------>SLPing statement: ");
3657 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3658 dump_printf (MSG_NOTE
, "\n");
3661 stmt_info
= vinfo_for_stmt (stmt
);
3662 gcc_assert (stmt_info
);
3664 /* Schedule all the SLP instances when the first SLP stmt is reached. */
3665 if (STMT_SLP_TYPE (stmt_info
))
3667 vect_schedule_slp (NULL
, bb_vinfo
);
3672 if (dump_enabled_p ())
3673 dump_printf_loc (MSG_NOTE
, vect_location
,
3674 "BASIC BLOCK VECTORIZED\n");
3676 destroy_bb_vec_info (bb_vinfo
);