1 /* SLP - Basic Block Vectorization
2 Copyright (C) 2007-2016 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
4 and Ira Rosen <irar@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
30 #include "tree-pass.h"
32 #include "optabs-tree.h"
33 #include "insn-config.h"
34 #include "recog.h" /* FIXME: for insn_data */
36 #include "fold-const.h"
37 #include "stor-layout.h"
38 #include "gimple-iterator.h"
40 #include "tree-vectorizer.h"
41 #include "langhooks.h"
42 #include "gimple-walk.h"
46 /* Recursively free the memory allocated for the SLP tree rooted at NODE. */
49 vect_free_slp_tree (slp_tree node
)
54 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
55 vect_free_slp_tree (child
);
58 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
59 /* After transform some stmts are removed and thus their vinfo is gone. */
60 if (vinfo_for_stmt (stmt
))
62 gcc_assert (STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmt
)) > 0);
63 STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmt
))--;
66 SLP_TREE_CHILDREN (node
).release ();
67 SLP_TREE_SCALAR_STMTS (node
).release ();
68 SLP_TREE_VEC_STMTS (node
).release ();
69 SLP_TREE_LOAD_PERMUTATION (node
).release ();
75 /* Free the memory allocated for the SLP instance. */
78 vect_free_slp_instance (slp_instance instance
)
80 vect_free_slp_tree (SLP_INSTANCE_TREE (instance
));
81 SLP_INSTANCE_LOADS (instance
).release ();
86 /* Create an SLP node for SCALAR_STMTS. */
89 vect_create_new_slp_node (vec
<gimple
*> scalar_stmts
)
92 gimple
*stmt
= scalar_stmts
[0];
95 if (is_gimple_call (stmt
))
96 nops
= gimple_call_num_args (stmt
);
97 else if (is_gimple_assign (stmt
))
99 nops
= gimple_num_ops (stmt
) - 1;
100 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
106 node
= XNEW (struct _slp_tree
);
107 SLP_TREE_SCALAR_STMTS (node
) = scalar_stmts
;
108 SLP_TREE_VEC_STMTS (node
).create (0);
109 SLP_TREE_CHILDREN (node
).create (nops
);
110 SLP_TREE_LOAD_PERMUTATION (node
) = vNULL
;
111 SLP_TREE_TWO_OPERATORS (node
) = false;
112 SLP_TREE_DEF_TYPE (node
) = vect_internal_def
;
115 FOR_EACH_VEC_ELT (scalar_stmts
, i
, stmt
)
116 STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmt
))++;
122 /* This structure is used in creation of an SLP tree. Each instance
123 corresponds to the same operand in a group of scalar stmts in an SLP
125 typedef struct _slp_oprnd_info
127 /* Def-stmts for the operands. */
128 vec
<gimple
*> def_stmts
;
129 /* Information about the first statement, its vector def-type, type, the
130 operand itself in case it's constant, and an indication if it's a pattern
132 enum vect_def_type first_dt
;
139 /* Allocate operands info for NOPS operands, and GROUP_SIZE def-stmts for each
141 static vec
<slp_oprnd_info
>
142 vect_create_oprnd_info (int nops
, int group_size
)
145 slp_oprnd_info oprnd_info
;
146 vec
<slp_oprnd_info
> oprnds_info
;
148 oprnds_info
.create (nops
);
149 for (i
= 0; i
< nops
; i
++)
151 oprnd_info
= XNEW (struct _slp_oprnd_info
);
152 oprnd_info
->def_stmts
.create (group_size
);
153 oprnd_info
->first_dt
= vect_uninitialized_def
;
154 oprnd_info
->first_op_type
= NULL_TREE
;
155 oprnd_info
->first_pattern
= false;
156 oprnd_info
->second_pattern
= false;
157 oprnds_info
.quick_push (oprnd_info
);
164 /* Free operands info. */
167 vect_free_oprnd_info (vec
<slp_oprnd_info
> &oprnds_info
)
170 slp_oprnd_info oprnd_info
;
172 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
174 oprnd_info
->def_stmts
.release ();
175 XDELETE (oprnd_info
);
178 oprnds_info
.release ();
182 /* Find the place of the data-ref in STMT in the interleaving chain that starts
183 from FIRST_STMT. Return -1 if the data-ref is not a part of the chain. */
186 vect_get_place_in_interleaving_chain (gimple
*stmt
, gimple
*first_stmt
)
188 gimple
*next_stmt
= first_stmt
;
191 if (first_stmt
!= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
196 if (next_stmt
== stmt
)
198 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
200 result
+= GROUP_GAP (vinfo_for_stmt (next_stmt
));
208 /* Get the defs for the rhs of STMT (collect them in OPRNDS_INFO), check that
209 they are of a valid type and that they match the defs of the first stmt of
210 the SLP group (stored in OPRNDS_INFO). This function tries to match stmts
211 by swapping operands of STMT when possible. Non-zero *SWAP indicates swap
212 is required for cond_expr stmts. Specifically, *SWAP is 1 if STMT is cond
213 and operands of comparison need to be swapped; *SWAP is 2 if STMT is cond
214 and code of comparison needs to be inverted. If there is any operand swap
215 in this function, *SWAP is set to non-zero value.
216 If there was a fatal error return -1; if the error could be corrected by
217 swapping operands of father node of this one, return 1; if everything is
221 vect_get_and_check_slp_defs (vec_info
*vinfo
, unsigned char *swap
,
222 gimple
*stmt
, unsigned stmt_num
,
223 vec
<slp_oprnd_info
> *oprnds_info
)
226 unsigned int i
, number_of_oprnds
;
228 enum vect_def_type dt
= vect_uninitialized_def
;
229 bool pattern
= false;
230 slp_oprnd_info oprnd_info
;
231 int first_op_idx
= 1;
232 bool commutative
= false;
233 bool first_op_cond
= false;
234 bool first
= stmt_num
== 0;
235 bool second
= stmt_num
== 1;
237 if (is_gimple_call (stmt
))
239 number_of_oprnds
= gimple_call_num_args (stmt
);
242 else if (is_gimple_assign (stmt
))
244 enum tree_code code
= gimple_assign_rhs_code (stmt
);
245 number_of_oprnds
= gimple_num_ops (stmt
) - 1;
246 /* Swap can only be done for cond_expr if asked to, otherwise we
247 could result in different comparison code to the first stmt. */
248 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
249 && COMPARISON_CLASS_P (gimple_assign_rhs1 (stmt
)))
251 first_op_cond
= true;
255 commutative
= commutative_tree_code (code
);
260 bool swapped
= (*swap
!= 0);
261 gcc_assert (!swapped
|| first_op_cond
);
262 for (i
= 0; i
< number_of_oprnds
; i
++)
267 /* Map indicating how operands of cond_expr should be swapped. */
268 int maps
[3][4] = {{0, 1, 2, 3}, {1, 0, 2, 3}, {0, 1, 3, 2}};
269 int *map
= maps
[*swap
];
272 oprnd
= TREE_OPERAND (gimple_op (stmt
, first_op_idx
), map
[i
]);
274 oprnd
= gimple_op (stmt
, map
[i
]);
277 oprnd
= gimple_op (stmt
, first_op_idx
+ (swapped
? !i
: i
));
279 oprnd_info
= (*oprnds_info
)[i
];
281 if (!vect_is_simple_use (oprnd
, vinfo
, &def_stmt
, &dt
))
283 if (dump_enabled_p ())
285 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
286 "Build SLP failed: can't analyze def for ");
287 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
288 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
294 /* Check if DEF_STMT is a part of a pattern in LOOP and get the def stmt
295 from the pattern. Check that all the stmts of the node are in the
297 if (def_stmt
&& gimple_bb (def_stmt
)
298 && vect_stmt_in_region_p (vinfo
, def_stmt
)
299 && vinfo_for_stmt (def_stmt
)
300 && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (def_stmt
))
301 && !STMT_VINFO_RELEVANT (vinfo_for_stmt (def_stmt
))
302 && !STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt
)))
305 if (!first
&& !oprnd_info
->first_pattern
306 /* Allow different pattern state for the defs of the
307 first stmt in reduction chains. */
308 && (oprnd_info
->first_dt
!= vect_reduction_def
309 || (!second
&& !oprnd_info
->second_pattern
)))
319 if (dump_enabled_p ())
321 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
322 "Build SLP failed: some of the stmts"
323 " are in a pattern, and others are not ");
324 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
325 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
331 def_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt
));
332 dt
= STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
));
334 if (dt
== vect_unknown_def_type
)
336 if (dump_enabled_p ())
337 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
338 "Unsupported pattern.\n");
342 switch (gimple_code (def_stmt
))
349 if (dump_enabled_p ())
350 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
351 "unsupported defining stmt:\n");
357 oprnd_info
->second_pattern
= pattern
;
361 oprnd_info
->first_dt
= dt
;
362 oprnd_info
->first_pattern
= pattern
;
363 oprnd_info
->first_op_type
= TREE_TYPE (oprnd
);
367 /* Not first stmt of the group, check that the def-stmt/s match
368 the def-stmt/s of the first stmt. Allow different definition
369 types for reduction chains: the first stmt must be a
370 vect_reduction_def (a phi node), and the rest
371 vect_internal_def. */
372 if (((oprnd_info
->first_dt
!= dt
373 && !(oprnd_info
->first_dt
== vect_reduction_def
374 && dt
== vect_internal_def
)
375 && !((oprnd_info
->first_dt
== vect_external_def
376 || oprnd_info
->first_dt
== vect_constant_def
)
377 && (dt
== vect_external_def
378 || dt
== vect_constant_def
)))
379 || !types_compatible_p (oprnd_info
->first_op_type
,
382 /* Try swapping operands if we got a mismatch. */
391 if (dump_enabled_p ())
392 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
393 "Build SLP failed: different types\n");
399 /* Check the types of the definitions. */
402 case vect_constant_def
:
403 case vect_external_def
:
404 case vect_reduction_def
:
407 case vect_internal_def
:
408 oprnd_info
->def_stmts
.quick_push (def_stmt
);
412 /* FORNOW: Not supported. */
413 if (dump_enabled_p ())
415 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
416 "Build SLP failed: illegal type of def ");
417 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, oprnd
);
418 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
428 /* If there are already uses of this stmt in a SLP instance then
429 we've committed to the operand order and can't swap it. */
430 if (STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmt
)) != 0)
432 if (dump_enabled_p ())
434 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
435 "Build SLP failed: cannot swap operands of "
437 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
444 tree cond
= gimple_assign_rhs1 (stmt
);
445 enum tree_code code
= TREE_CODE (cond
);
450 swap_ssa_operands (stmt
, &TREE_OPERAND (cond
, 0),
451 &TREE_OPERAND (cond
, 1));
452 TREE_SET_CODE (cond
, swap_tree_comparison (code
));
457 swap_ssa_operands (stmt
, gimple_assign_rhs2_ptr (stmt
),
458 gimple_assign_rhs3_ptr (stmt
));
459 bool honor_nans
= HONOR_NANS (TREE_OPERAND (cond
, 0));
460 code
= invert_tree_comparison (TREE_CODE (cond
), honor_nans
);
461 gcc_assert (code
!= ERROR_MARK
);
462 TREE_SET_CODE (cond
, code
);
466 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
467 gimple_assign_rhs2_ptr (stmt
));
468 if (dump_enabled_p ())
470 dump_printf_loc (MSG_NOTE
, vect_location
,
471 "swapped operands to match def types in ");
472 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
481 /* Verify if the scalar stmts STMTS are isomorphic, require data
482 permutation or are of unsupported types of operation. Return
483 true if they are, otherwise return false and indicate in *MATCHES
484 which stmts are not isomorphic to the first one. If MATCHES[0]
485 is false then this indicates the comparison could not be
486 carried out or the stmts will never be vectorized by SLP.
488 Note COND_EXPR is possibly ismorphic to another one after swapping its
489 operands. Set SWAP[i] to 1 if stmt I is COND_EXPR and isomorphic to
490 the first stmt by swapping the two operands of comparison; set SWAP[i]
491 to 2 if stmt I is isormorphic to the first stmt by inverting the code
492 of comparison. Take A1 >= B1 ? X1 : Y1 as an exmple, it can be swapped
493 to (B1 <= A1 ? X1 : Y1); or be inverted to (A1 < B1) ? Y1 : X1. */
496 vect_build_slp_tree_1 (vec_info
*vinfo
, unsigned char *swap
,
497 vec
<gimple
*> stmts
, unsigned int group_size
,
498 unsigned nops
, unsigned int *max_nunits
,
499 bool *matches
, bool *two_operators
)
502 gimple
*first_stmt
= stmts
[0], *stmt
= stmts
[0];
503 enum tree_code first_stmt_code
= ERROR_MARK
;
504 enum tree_code alt_stmt_code
= ERROR_MARK
;
505 enum tree_code rhs_code
= ERROR_MARK
;
506 enum tree_code first_cond_code
= ERROR_MARK
;
508 bool need_same_oprnds
= false;
509 tree vectype
= NULL_TREE
, scalar_type
, first_op1
= NULL_TREE
;
512 machine_mode optab_op2_mode
;
513 machine_mode vec_mode
;
515 gimple
*first_load
= NULL
, *prev_first_load
= NULL
;
517 /* For every stmt in NODE find its def stmt/s. */
518 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
523 if (dump_enabled_p ())
525 dump_printf_loc (MSG_NOTE
, vect_location
, "Build SLP for ");
526 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
529 /* Fail to vectorize statements marked as unvectorizable. */
530 if (!STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt
)))
532 if (dump_enabled_p ())
534 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
535 "Build SLP failed: unvectorizable statement ");
536 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
538 /* Fatal mismatch. */
543 lhs
= gimple_get_lhs (stmt
);
544 if (lhs
== NULL_TREE
)
546 if (dump_enabled_p ())
548 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
549 "Build SLP failed: not GIMPLE_ASSIGN nor "
551 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
553 /* Fatal mismatch. */
558 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
, &dummy
);
559 vectype
= get_vectype_for_scalar_type (scalar_type
);
562 if (dump_enabled_p ())
564 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
565 "Build SLP failed: unsupported data-type ");
566 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
568 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
570 /* Fatal mismatch. */
575 /* If populating the vector type requires unrolling then fail
576 before adjusting *max_nunits for basic-block vectorization. */
577 if (is_a
<bb_vec_info
> (vinfo
)
578 && TYPE_VECTOR_SUBPARTS (vectype
) > group_size
)
580 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
581 "Build SLP failed: unrolling required "
582 "in basic block SLP\n");
583 /* Fatal mismatch. */
588 /* In case of multiple types we need to detect the smallest type. */
589 if (*max_nunits
< TYPE_VECTOR_SUBPARTS (vectype
))
590 *max_nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
592 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
594 rhs_code
= CALL_EXPR
;
595 if (gimple_call_internal_p (call_stmt
)
596 || gimple_call_tail_p (call_stmt
)
597 || gimple_call_noreturn_p (call_stmt
)
598 || !gimple_call_nothrow_p (call_stmt
)
599 || gimple_call_chain (call_stmt
))
601 if (dump_enabled_p ())
603 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
604 "Build SLP failed: unsupported call type ");
605 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
608 /* Fatal mismatch. */
614 rhs_code
= gimple_assign_rhs_code (stmt
);
616 /* Check the operation. */
619 first_stmt_code
= rhs_code
;
621 /* Shift arguments should be equal in all the packed stmts for a
622 vector shift with scalar shift operand. */
623 if (rhs_code
== LSHIFT_EXPR
|| rhs_code
== RSHIFT_EXPR
624 || rhs_code
== LROTATE_EXPR
625 || rhs_code
== RROTATE_EXPR
)
627 vec_mode
= TYPE_MODE (vectype
);
629 /* First see if we have a vector/vector shift. */
630 optab
= optab_for_tree_code (rhs_code
, vectype
,
634 || optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
636 /* No vector/vector shift, try for a vector/scalar shift. */
637 optab
= optab_for_tree_code (rhs_code
, vectype
,
642 if (dump_enabled_p ())
643 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
644 "Build SLP failed: no optab.\n");
645 /* Fatal mismatch. */
649 icode
= (int) optab_handler (optab
, vec_mode
);
650 if (icode
== CODE_FOR_nothing
)
652 if (dump_enabled_p ())
653 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
655 "op not supported by target.\n");
656 /* Fatal mismatch. */
660 optab_op2_mode
= insn_data
[icode
].operand
[2].mode
;
661 if (!VECTOR_MODE_P (optab_op2_mode
))
663 need_same_oprnds
= true;
664 first_op1
= gimple_assign_rhs2 (stmt
);
668 else if (rhs_code
== WIDEN_LSHIFT_EXPR
)
670 need_same_oprnds
= true;
671 first_op1
= gimple_assign_rhs2 (stmt
);
676 if (first_stmt_code
!= rhs_code
677 && alt_stmt_code
== ERROR_MARK
)
678 alt_stmt_code
= rhs_code
;
679 if (first_stmt_code
!= rhs_code
680 && (first_stmt_code
!= IMAGPART_EXPR
681 || rhs_code
!= REALPART_EXPR
)
682 && (first_stmt_code
!= REALPART_EXPR
683 || rhs_code
!= IMAGPART_EXPR
)
684 /* Handle mismatches in plus/minus by computing both
685 and merging the results. */
686 && !((first_stmt_code
== PLUS_EXPR
687 || first_stmt_code
== MINUS_EXPR
)
688 && (alt_stmt_code
== PLUS_EXPR
689 || alt_stmt_code
== MINUS_EXPR
)
690 && rhs_code
== alt_stmt_code
)
691 && !(STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
692 && (first_stmt_code
== ARRAY_REF
693 || first_stmt_code
== BIT_FIELD_REF
694 || first_stmt_code
== INDIRECT_REF
695 || first_stmt_code
== COMPONENT_REF
696 || first_stmt_code
== MEM_REF
)))
698 if (dump_enabled_p ())
700 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
701 "Build SLP failed: different operation "
703 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
704 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
706 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
714 && !operand_equal_p (first_op1
, gimple_assign_rhs2 (stmt
), 0))
716 if (dump_enabled_p ())
718 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
719 "Build SLP failed: different shift "
721 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
727 if (rhs_code
== CALL_EXPR
)
729 gimple
*first_stmt
= stmts
[0];
730 if (gimple_call_num_args (stmt
) != nops
731 || !operand_equal_p (gimple_call_fn (first_stmt
),
732 gimple_call_fn (stmt
), 0)
733 || gimple_call_fntype (first_stmt
)
734 != gimple_call_fntype (stmt
))
736 if (dump_enabled_p ())
738 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
739 "Build SLP failed: different calls in ");
740 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
749 /* Grouped store or load. */
750 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
752 if (REFERENCE_CLASS_P (lhs
))
760 first_load
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
));
763 /* Check that there are no loads from different interleaving
764 chains in the same node. */
765 if (prev_first_load
!= first_load
)
767 if (dump_enabled_p ())
769 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
771 "Build SLP failed: different "
772 "interleaving chains in one node ");
773 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
781 prev_first_load
= first_load
;
783 } /* Grouped access. */
786 if (TREE_CODE_CLASS (rhs_code
) == tcc_reference
)
788 /* Not grouped load. */
789 if (dump_enabled_p ())
791 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
792 "Build SLP failed: not grouped load ");
793 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
796 /* FORNOW: Not grouped loads are not supported. */
797 /* Fatal mismatch. */
802 /* Not memory operation. */
803 if (TREE_CODE_CLASS (rhs_code
) != tcc_binary
804 && TREE_CODE_CLASS (rhs_code
) != tcc_unary
805 && TREE_CODE_CLASS (rhs_code
) != tcc_expression
806 && TREE_CODE_CLASS (rhs_code
) != tcc_comparison
807 && rhs_code
!= CALL_EXPR
)
809 if (dump_enabled_p ())
811 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
812 "Build SLP failed: operation");
813 dump_printf (MSG_MISSED_OPTIMIZATION
, " unsupported ");
814 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
816 /* Fatal mismatch. */
821 if (rhs_code
== COND_EXPR
)
823 tree cond_expr
= gimple_assign_rhs1 (stmt
);
824 enum tree_code cond_code
= TREE_CODE (cond_expr
);
825 enum tree_code swap_code
= ERROR_MARK
;
826 enum tree_code invert_code
= ERROR_MARK
;
829 first_cond_code
= TREE_CODE (cond_expr
);
830 else if (TREE_CODE_CLASS (cond_code
) == tcc_comparison
)
832 bool honor_nans
= HONOR_NANS (TREE_OPERAND (cond_expr
, 0));
833 swap_code
= swap_tree_comparison (cond_code
);
834 invert_code
= invert_tree_comparison (cond_code
, honor_nans
);
837 if (first_cond_code
== cond_code
)
839 /* Isomorphic can be achieved by swapping. */
840 else if (first_cond_code
== swap_code
)
842 /* Isomorphic can be achieved by inverting. */
843 else if (first_cond_code
== invert_code
)
847 if (dump_enabled_p ())
849 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
850 "Build SLP failed: different"
852 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
864 for (i
= 0; i
< group_size
; ++i
)
868 /* If we allowed a two-operation SLP node verify the target can cope
869 with the permute we are going to use. */
870 if (alt_stmt_code
!= ERROR_MARK
871 && TREE_CODE_CLASS (alt_stmt_code
) != tcc_reference
)
874 = XALLOCAVEC (unsigned char, TYPE_VECTOR_SUBPARTS (vectype
));
875 for (i
= 0; i
< TYPE_VECTOR_SUBPARTS (vectype
); ++i
)
878 if (gimple_assign_rhs_code (stmts
[i
% group_size
]) == alt_stmt_code
)
879 sel
[i
] += TYPE_VECTOR_SUBPARTS (vectype
);
881 if (!can_vec_perm_p (TYPE_MODE (vectype
), false, sel
))
883 for (i
= 0; i
< group_size
; ++i
)
884 if (gimple_assign_rhs_code (stmts
[i
]) == alt_stmt_code
)
887 if (dump_enabled_p ())
889 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
890 "Build SLP failed: different operation "
892 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
894 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
896 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
902 *two_operators
= true;
908 /* Recursively build an SLP tree starting from NODE.
909 Fail (and return a value not equal to zero) if def-stmts are not
910 isomorphic, require data permutation or are of unsupported types of
911 operation. Otherwise, return 0.
912 The value returned is the depth in the SLP tree where a mismatch
916 vect_build_slp_tree (vec_info
*vinfo
,
917 vec
<gimple
*> stmts
, unsigned int group_size
,
918 unsigned int *max_nunits
,
919 vec
<slp_tree
> *loads
,
920 bool *matches
, unsigned *npermutes
, unsigned *tree_size
,
921 unsigned max_tree_size
)
923 unsigned nops
, i
, this_tree_size
= 0, this_max_nunits
= *max_nunits
;
930 if (is_gimple_call (stmt
))
931 nops
= gimple_call_num_args (stmt
);
932 else if (is_gimple_assign (stmt
))
934 nops
= gimple_num_ops (stmt
) - 1;
935 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
941 bool two_operators
= false;
942 unsigned char *swap
= XALLOCAVEC (unsigned char, group_size
);
943 if (!vect_build_slp_tree_1 (vinfo
, swap
,
944 stmts
, group_size
, nops
,
945 &this_max_nunits
, matches
, &two_operators
))
948 /* If the SLP node is a load, terminate the recursion. */
949 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
))
950 && DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
952 *max_nunits
= this_max_nunits
;
953 node
= vect_create_new_slp_node (stmts
);
954 loads
->safe_push (node
);
958 /* Get at the operands, verifying they are compatible. */
959 vec
<slp_oprnd_info
> oprnds_info
= vect_create_oprnd_info (nops
, group_size
);
960 slp_oprnd_info oprnd_info
;
961 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
963 int res
= vect_get_and_check_slp_defs (vinfo
, &swap
[i
],
964 stmt
, i
, &oprnds_info
);
966 matches
[(res
== -1) ? 0 : i
] = false;
970 for (i
= 0; i
< group_size
; ++i
)
973 vect_free_oprnd_info (oprnds_info
);
977 auto_vec
<slp_tree
, 4> children
;
978 auto_vec
<slp_tree
> this_loads
;
982 /* Create SLP_TREE nodes for the definition node/s. */
983 FOR_EACH_VEC_ELT (oprnds_info
, i
, oprnd_info
)
986 unsigned old_nloads
= this_loads
.length ();
987 unsigned old_tree_size
= this_tree_size
;
990 if (oprnd_info
->first_dt
!= vect_internal_def
)
993 if (++this_tree_size
> max_tree_size
)
995 FOR_EACH_VEC_ELT (children
, j
, child
)
996 vect_free_slp_tree (child
);
997 vect_free_oprnd_info (oprnds_info
);
1001 if ((child
= vect_build_slp_tree (vinfo
, oprnd_info
->def_stmts
,
1002 group_size
, &this_max_nunits
,
1003 &this_loads
, matches
, npermutes
,
1005 max_tree_size
)) != NULL
)
1007 /* If we have all children of child built up from scalars then just
1008 throw that away and build it up this node from scalars. */
1009 if (!SLP_TREE_CHILDREN (child
).is_empty ()
1010 /* ??? Rejecting patterns this way doesn't work. We'd have to
1011 do extra work to cancel the pattern so the uses see the
1013 && !is_pattern_stmt_p
1014 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child
)[0])))
1016 slp_tree grandchild
;
1018 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1019 if (SLP_TREE_DEF_TYPE (grandchild
) == vect_internal_def
)
1024 this_loads
.truncate (old_nloads
);
1025 this_tree_size
= old_tree_size
;
1026 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1027 vect_free_slp_tree (grandchild
);
1028 SLP_TREE_CHILDREN (child
).truncate (0);
1030 dump_printf_loc (MSG_NOTE
, vect_location
,
1031 "Building parent vector operands from "
1032 "scalars instead\n");
1033 oprnd_info
->def_stmts
= vNULL
;
1034 SLP_TREE_DEF_TYPE (child
) = vect_external_def
;
1035 children
.safe_push (child
);
1040 oprnd_info
->def_stmts
= vNULL
;
1041 children
.safe_push (child
);
1045 /* If the SLP build failed fatally and we analyze a basic-block
1046 simply treat nodes we fail to build as externally defined
1047 (and thus build vectors from the scalar defs).
1048 The cost model will reject outright expensive cases.
1049 ??? This doesn't treat cases where permutation ultimatively
1050 fails (or we don't try permutation below). Ideally we'd
1051 even compute a permutation that will end up with the maximum
1053 if (is_a
<bb_vec_info
> (vinfo
)
1055 /* ??? Rejecting patterns this way doesn't work. We'd have to
1056 do extra work to cancel the pattern so the uses see the
1058 && !is_pattern_stmt_p (vinfo_for_stmt (stmt
)))
1060 dump_printf_loc (MSG_NOTE
, vect_location
,
1061 "Building vector operands from scalars\n");
1062 child
= vect_create_new_slp_node (oprnd_info
->def_stmts
);
1063 SLP_TREE_DEF_TYPE (child
) = vect_external_def
;
1064 children
.safe_push (child
);
1065 oprnd_info
->def_stmts
= vNULL
;
1069 /* If the SLP build for operand zero failed and operand zero
1070 and one can be commutated try that for the scalar stmts
1071 that failed the match. */
1073 /* A first scalar stmt mismatch signals a fatal mismatch. */
1075 /* ??? For COND_EXPRs we can swap the comparison operands
1076 as well as the arms under some constraints. */
1078 && oprnds_info
[1]->first_dt
== vect_internal_def
1079 && is_gimple_assign (stmt
)
1080 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
1082 /* Do so only if the number of not successful permutes was nor more
1083 than a cut-ff as re-trying the recursive match on
1084 possibly each level of the tree would expose exponential
1088 /* Verify if we can safely swap or if we committed to a specific
1089 operand order already. */
1090 for (j
= 0; j
< group_size
; ++j
)
1093 || STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmts
[j
]))))
1095 if (dump_enabled_p ())
1097 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1098 "Build SLP failed: cannot swap operands "
1100 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
1106 /* Swap mismatched definition stmts. */
1107 dump_printf_loc (MSG_NOTE
, vect_location
,
1108 "Re-trying with swapped operands of stmts ");
1109 for (j
= 0; j
< group_size
; ++j
)
1112 std::swap (oprnds_info
[0]->def_stmts
[j
],
1113 oprnds_info
[1]->def_stmts
[j
]);
1114 dump_printf (MSG_NOTE
, "%d ", j
);
1116 dump_printf (MSG_NOTE
, "\n");
1117 /* And try again with scratch 'matches' ... */
1118 bool *tem
= XALLOCAVEC (bool, group_size
);
1119 if ((child
= vect_build_slp_tree (vinfo
, oprnd_info
->def_stmts
,
1120 group_size
, &this_max_nunits
,
1121 &this_loads
, tem
, npermutes
,
1123 max_tree_size
)) != NULL
)
1125 /* ... so if successful we can apply the operand swapping
1126 to the GIMPLE IL. This is necessary because for example
1127 vect_get_slp_defs uses operand indexes and thus expects
1128 canonical operand order. This is also necessary even
1129 if we end up building the operand from scalars as
1130 we'll continue to process swapped operand two. */
1131 for (j
= 0; j
< group_size
; ++j
)
1133 gimple
*stmt
= stmts
[j
];
1134 gimple_set_plf (stmt
, GF_PLF_1
, false);
1136 for (j
= 0; j
< group_size
; ++j
)
1138 gimple
*stmt
= stmts
[j
];
1141 /* Avoid swapping operands twice. */
1142 if (gimple_plf (stmt
, GF_PLF_1
))
1144 swap_ssa_operands (stmt
, gimple_assign_rhs1_ptr (stmt
),
1145 gimple_assign_rhs2_ptr (stmt
));
1146 gimple_set_plf (stmt
, GF_PLF_1
, true);
1149 /* Verify we swap all duplicates or none. */
1151 for (j
= 0; j
< group_size
; ++j
)
1153 gimple
*stmt
= stmts
[j
];
1154 gcc_assert (gimple_plf (stmt
, GF_PLF_1
) == ! matches
[j
]);
1157 /* If we have all children of child built up from scalars then
1158 just throw that away and build it up this node from scalars. */
1159 if (!SLP_TREE_CHILDREN (child
).is_empty ()
1160 /* ??? Rejecting patterns this way doesn't work. We'd have
1161 to do extra work to cancel the pattern so the uses see the
1163 && !is_pattern_stmt_p
1164 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child
)[0])))
1167 slp_tree grandchild
;
1169 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child
), j
, grandchild
)
1170 if (SLP_TREE_DEF_TYPE (grandchild
) == vect_internal_def
)
1175 this_loads
.truncate (old_nloads
);
1176 this_tree_size
= old_tree_size
;
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 dump_printf_loc (MSG_NOTE
, vect_location
,
1182 "Building parent vector operands from "
1183 "scalars instead\n");
1184 oprnd_info
->def_stmts
= vNULL
;
1185 SLP_TREE_DEF_TYPE (child
) = vect_external_def
;
1186 children
.safe_push (child
);
1191 oprnd_info
->def_stmts
= vNULL
;
1192 children
.safe_push (child
);
1200 gcc_assert (child
== NULL
);
1201 FOR_EACH_VEC_ELT (children
, j
, child
)
1202 vect_free_slp_tree (child
);
1203 vect_free_oprnd_info (oprnds_info
);
1207 vect_free_oprnd_info (oprnds_info
);
1210 *tree_size
+= this_tree_size
;
1211 *max_nunits
= this_max_nunits
;
1212 loads
->safe_splice (this_loads
);
1214 node
= vect_create_new_slp_node (stmts
);
1215 SLP_TREE_TWO_OPERATORS (node
) = two_operators
;
1216 SLP_TREE_CHILDREN (node
).splice (children
);
1220 /* Dump a slp tree NODE using flags specified in DUMP_KIND. */
1223 vect_print_slp_tree (int dump_kind
, location_t loc
, slp_tree node
)
1229 dump_printf_loc (dump_kind
, loc
, "node%s\n",
1230 SLP_TREE_DEF_TYPE (node
) != vect_internal_def
1231 ? " (external)" : "");
1232 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1234 dump_printf_loc (dump_kind
, loc
, "\tstmt %d ", i
);
1235 dump_gimple_stmt (dump_kind
, TDF_SLIM
, stmt
, 0);
1237 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1238 vect_print_slp_tree (dump_kind
, loc
, child
);
1242 /* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
1243 If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
1244 J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
1245 stmts in NODE are to be marked. */
1248 vect_mark_slp_stmts (slp_tree node
, enum slp_vect_type mark
, int j
)
1254 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
1257 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1258 if (j
< 0 || i
== j
)
1259 STMT_SLP_TYPE (vinfo_for_stmt (stmt
)) = mark
;
1261 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1262 vect_mark_slp_stmts (child
, mark
, j
);
1266 /* Mark the statements of the tree rooted at NODE as relevant (vect_used). */
1269 vect_mark_slp_stmts_relevant (slp_tree node
)
1273 stmt_vec_info stmt_info
;
1276 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
1279 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1281 stmt_info
= vinfo_for_stmt (stmt
);
1282 gcc_assert (!STMT_VINFO_RELEVANT (stmt_info
)
1283 || STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
);
1284 STMT_VINFO_RELEVANT (stmt_info
) = vect_used_in_scope
;
1287 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1288 vect_mark_slp_stmts_relevant (child
);
1292 /* Rearrange the statements of NODE according to PERMUTATION. */
1295 vect_slp_rearrange_stmts (slp_tree node
, unsigned int group_size
,
1296 vec
<unsigned> permutation
)
1299 vec
<gimple
*> tmp_stmts
;
1303 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1304 vect_slp_rearrange_stmts (child
, group_size
, permutation
);
1306 gcc_assert (group_size
== SLP_TREE_SCALAR_STMTS (node
).length ());
1307 tmp_stmts
.create (group_size
);
1308 tmp_stmts
.quick_grow_cleared (group_size
);
1310 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
1311 tmp_stmts
[permutation
[i
]] = stmt
;
1313 SLP_TREE_SCALAR_STMTS (node
).release ();
1314 SLP_TREE_SCALAR_STMTS (node
) = tmp_stmts
;
1318 /* Attempt to reorder stmts in a reduction chain so that we don't
1319 require any load permutation. Return true if that was possible,
1320 otherwise return false. */
1323 vect_attempt_slp_rearrange_stmts (slp_instance slp_instn
)
1325 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1328 slp_tree node
, load
;
1330 /* Compare all the permutation sequences to the first one. We know
1331 that at least one load is permuted. */
1332 node
= SLP_INSTANCE_LOADS (slp_instn
)[0];
1333 if (!node
->load_permutation
.exists ())
1335 for (i
= 1; SLP_INSTANCE_LOADS (slp_instn
).iterate (i
, &load
); ++i
)
1337 if (!load
->load_permutation
.exists ())
1339 FOR_EACH_VEC_ELT (load
->load_permutation
, j
, lidx
)
1340 if (lidx
!= node
->load_permutation
[j
])
1344 /* Check that the loads in the first sequence are different and there
1345 are no gaps between them. */
1346 auto_sbitmap
load_index (group_size
);
1347 bitmap_clear (load_index
);
1348 FOR_EACH_VEC_ELT (node
->load_permutation
, i
, lidx
)
1350 if (lidx
>= group_size
)
1352 if (bitmap_bit_p (load_index
, lidx
))
1355 bitmap_set_bit (load_index
, lidx
);
1357 for (i
= 0; i
< group_size
; i
++)
1358 if (!bitmap_bit_p (load_index
, i
))
1361 /* This permutation is valid for reduction. Since the order of the
1362 statements in the nodes is not important unless they are memory
1363 accesses, we can rearrange the statements in all the nodes
1364 according to the order of the loads. */
1365 vect_slp_rearrange_stmts (SLP_INSTANCE_TREE (slp_instn
), group_size
,
1366 node
->load_permutation
);
1368 /* We are done, no actual permutations need to be generated. */
1369 unsigned int unrolling_factor
= SLP_INSTANCE_UNROLLING_FACTOR (slp_instn
);
1370 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1372 gimple
*first_stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1373 first_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (first_stmt
));
1374 /* But we have to keep those permutations that are required because
1375 of handling of gaps. */
1376 if (unrolling_factor
== 1
1377 || (group_size
== GROUP_SIZE (vinfo_for_stmt (first_stmt
))
1378 && GROUP_GAP (vinfo_for_stmt (first_stmt
)) == 0))
1379 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1381 for (j
= 0; j
< SLP_TREE_LOAD_PERMUTATION (node
).length (); ++j
)
1382 SLP_TREE_LOAD_PERMUTATION (node
)[j
] = j
;
1388 /* Check if the required load permutations in the SLP instance
1389 SLP_INSTN are supported. */
1392 vect_supported_load_permutation_p (slp_instance slp_instn
)
1394 unsigned int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_instn
);
1395 unsigned int i
, j
, k
, next
;
1397 gimple
*stmt
, *load
, *next_load
;
1399 if (dump_enabled_p ())
1401 dump_printf_loc (MSG_NOTE
, vect_location
, "Load permutation ");
1402 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1403 if (node
->load_permutation
.exists ())
1404 FOR_EACH_VEC_ELT (node
->load_permutation
, j
, next
)
1405 dump_printf (MSG_NOTE
, "%d ", next
);
1407 for (k
= 0; k
< group_size
; ++k
)
1408 dump_printf (MSG_NOTE
, "%d ", k
);
1409 dump_printf (MSG_NOTE
, "\n");
1412 /* In case of reduction every load permutation is allowed, since the order
1413 of the reduction statements is not important (as opposed to the case of
1414 grouped stores). The only condition we need to check is that all the
1415 load nodes are of the same size and have the same permutation (and then
1416 rearrange all the nodes of the SLP instance according to this
1419 /* Check that all the load nodes are of the same size. */
1420 /* ??? Can't we assert this? */
1421 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1422 if (SLP_TREE_SCALAR_STMTS (node
).length () != (unsigned) group_size
)
1425 node
= SLP_INSTANCE_TREE (slp_instn
);
1426 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1428 /* Reduction (there are no data-refs in the root).
1429 In reduction chain the order of the loads is not important. */
1430 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))
1431 && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1432 vect_attempt_slp_rearrange_stmts (slp_instn
);
1434 /* In basic block vectorization we allow any subchain of an interleaving
1436 FORNOW: not supported in loop SLP because of realignment compications. */
1437 if (STMT_VINFO_BB_VINFO (vinfo_for_stmt (stmt
)))
1439 /* Check whether the loads in an instance form a subchain and thus
1440 no permutation is necessary. */
1441 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1443 if (!SLP_TREE_LOAD_PERMUTATION (node
).exists ())
1445 bool subchain_p
= true;
1447 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), j
, load
)
1450 && (next_load
!= load
1451 || GROUP_GAP (vinfo_for_stmt (load
)) != 1))
1456 next_load
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (load
));
1459 SLP_TREE_LOAD_PERMUTATION (node
).release ();
1462 /* Verify the permutation can be generated. */
1465 if (!vect_transform_slp_perm_load (node
, tem
, NULL
,
1466 1, slp_instn
, true, &n_perms
))
1468 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
1470 "unsupported load permutation\n");
1478 /* For loop vectorization verify we can generate the permutation. */
1480 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn
), i
, node
)
1481 if (node
->load_permutation
.exists ()
1482 && !vect_transform_slp_perm_load
1484 SLP_INSTANCE_UNROLLING_FACTOR (slp_instn
), slp_instn
, true,
1492 /* Find the last store in SLP INSTANCE. */
1495 vect_find_last_scalar_stmt_in_slp (slp_tree node
)
1497 gimple
*last
= NULL
, *stmt
;
1499 for (int i
= 0; SLP_TREE_SCALAR_STMTS (node
).iterate (i
, &stmt
); i
++)
1501 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
1502 if (is_pattern_stmt_p (stmt_vinfo
))
1503 last
= get_later_stmt (STMT_VINFO_RELATED_STMT (stmt_vinfo
), last
);
1505 last
= get_later_stmt (stmt
, last
);
1511 /* Compute the cost for the SLP node NODE in the SLP instance INSTANCE. */
1514 vect_analyze_slp_cost_1 (slp_instance instance
, slp_tree node
,
1515 stmt_vector_for_cost
*prologue_cost_vec
,
1516 stmt_vector_for_cost
*body_cost_vec
,
1517 unsigned ncopies_for_cost
)
1522 stmt_vec_info stmt_info
;
1525 /* Recurse down the SLP tree. */
1526 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1527 if (SLP_TREE_DEF_TYPE (child
) == vect_internal_def
)
1528 vect_analyze_slp_cost_1 (instance
, child
, prologue_cost_vec
,
1529 body_cost_vec
, ncopies_for_cost
);
1531 /* Look at the first scalar stmt to determine the cost. */
1532 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1533 stmt_info
= vinfo_for_stmt (stmt
);
1534 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1536 vect_memory_access_type memory_access_type
1537 = (STMT_VINFO_STRIDED_P (stmt_info
)
1540 if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info
)))
1541 vect_model_store_cost (stmt_info
, ncopies_for_cost
,
1542 memory_access_type
, vect_uninitialized_def
,
1543 node
, prologue_cost_vec
, body_cost_vec
);
1546 gcc_checking_assert (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)));
1547 if (SLP_TREE_LOAD_PERMUTATION (node
).exists ())
1549 /* If the load is permuted then the alignment is determined by
1550 the first group element not by the first scalar stmt DR. */
1551 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
1552 stmt_info
= vinfo_for_stmt (stmt
);
1553 /* Record the cost for the permutation. */
1555 vect_transform_slp_perm_load (node
, vNULL
, NULL
,
1556 ncopies_for_cost
, instance
, true,
1558 record_stmt_cost (body_cost_vec
, n_perms
, vec_perm
,
1559 stmt_info
, 0, vect_body
);
1561 = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
1562 /* And adjust the number of loads performed. This handles
1563 redundancies as well as loads that are later dead. */
1564 auto_sbitmap
perm (GROUP_SIZE (stmt_info
));
1565 bitmap_clear (perm
);
1566 for (i
= 0; i
< SLP_TREE_LOAD_PERMUTATION (node
).length (); ++i
)
1567 bitmap_set_bit (perm
, SLP_TREE_LOAD_PERMUTATION (node
)[i
]);
1568 ncopies_for_cost
= 0;
1569 bool load_seen
= false;
1570 for (i
= 0; i
< GROUP_SIZE (stmt_info
); ++i
)
1572 if (i
% nunits
== 0)
1578 if (bitmap_bit_p (perm
, i
))
1583 gcc_assert (ncopies_for_cost
1584 <= (GROUP_SIZE (stmt_info
) - GROUP_GAP (stmt_info
)
1585 + nunits
- 1) / nunits
);
1586 ncopies_for_cost
*= SLP_INSTANCE_UNROLLING_FACTOR (instance
);
1588 /* Record the cost for the vector loads. */
1589 vect_model_load_cost (stmt_info
, ncopies_for_cost
,
1590 memory_access_type
, node
, prologue_cost_vec
,
1597 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1598 stmt_info
, 0, vect_body
);
1599 if (SLP_TREE_TWO_OPERATORS (node
))
1601 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vector_stmt
,
1602 stmt_info
, 0, vect_body
);
1603 record_stmt_cost (body_cost_vec
, ncopies_for_cost
, vec_perm
,
1604 stmt_info
, 0, vect_body
);
1608 /* Push SLP node def-type to stmts. */
1609 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1610 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
1611 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
1612 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = SLP_TREE_DEF_TYPE (child
);
1614 /* Scan operands and account for prologue cost of constants/externals.
1615 ??? This over-estimates cost for multiple uses and should be
1617 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1618 lhs
= gimple_get_lhs (stmt
);
1619 for (i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1621 tree op
= gimple_op (stmt
, i
);
1623 enum vect_def_type dt
;
1624 if (!op
|| op
== lhs
)
1626 if (vect_is_simple_use (op
, stmt_info
->vinfo
, &def_stmt
, &dt
))
1628 /* Without looking at the actual initializer a vector of
1629 constants can be implemented as load from the constant pool.
1630 ??? We need to pass down stmt_info for a vector type
1631 even if it points to the wrong stmt. */
1632 if (dt
== vect_constant_def
)
1633 record_stmt_cost (prologue_cost_vec
, 1, vector_load
,
1634 stmt_info
, 0, vect_prologue
);
1635 else if (dt
== vect_external_def
)
1636 record_stmt_cost (prologue_cost_vec
, 1, vec_construct
,
1637 stmt_info
, 0, vect_prologue
);
1641 /* Restore stmt def-types. */
1642 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
1643 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
1644 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
1645 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_internal_def
;
1648 /* Compute the cost for the SLP instance INSTANCE. */
1651 vect_analyze_slp_cost (slp_instance instance
, void *data
)
1653 stmt_vector_for_cost body_cost_vec
, prologue_cost_vec
;
1654 unsigned ncopies_for_cost
;
1655 stmt_info_for_cost
*si
;
1658 if (dump_enabled_p ())
1659 dump_printf_loc (MSG_NOTE
, vect_location
,
1660 "=== vect_analyze_slp_cost ===\n");
1662 /* Calculate the number of vector stmts to create based on the unrolling
1663 factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
1664 GROUP_SIZE / NUNITS otherwise. */
1665 unsigned group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
1666 slp_tree node
= SLP_INSTANCE_TREE (instance
);
1667 stmt_vec_info stmt_info
= vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node
)[0]);
1668 /* Adjust the group_size by the vectorization factor which is always one
1669 for basic-block vectorization. */
1670 if (STMT_VINFO_LOOP_VINFO (stmt_info
))
1671 group_size
*= LOOP_VINFO_VECT_FACTOR (STMT_VINFO_LOOP_VINFO (stmt_info
));
1672 unsigned nunits
= TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
1673 /* For reductions look at a reduction operand in case the reduction
1674 operation is widening like DOT_PROD or SAD. */
1675 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1677 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
1678 switch (gimple_assign_rhs_code (stmt
))
1682 nunits
= TYPE_VECTOR_SUBPARTS (get_vectype_for_scalar_type
1683 (TREE_TYPE (gimple_assign_rhs1 (stmt
))));
1688 ncopies_for_cost
= least_common_multiple (nunits
, group_size
) / nunits
;
1690 prologue_cost_vec
.create (10);
1691 body_cost_vec
.create (10);
1692 vect_analyze_slp_cost_1 (instance
, SLP_INSTANCE_TREE (instance
),
1693 &prologue_cost_vec
, &body_cost_vec
,
1696 /* Record the prologue costs, which were delayed until we were
1697 sure that SLP was successful. */
1698 FOR_EACH_VEC_ELT (prologue_cost_vec
, i
, si
)
1700 struct _stmt_vec_info
*stmt_info
1701 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1702 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1703 si
->misalign
, vect_prologue
);
1706 /* Record the instance's instructions in the target cost model. */
1707 FOR_EACH_VEC_ELT (body_cost_vec
, i
, si
)
1709 struct _stmt_vec_info
*stmt_info
1710 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1711 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1712 si
->misalign
, vect_body
);
1715 prologue_cost_vec
.release ();
1716 body_cost_vec
.release ();
1719 /* Splits a group of stores, currently beginning at FIRST_STMT, into two groups:
1720 one (still beginning at FIRST_STMT) of size GROUP1_SIZE (also containing
1721 the first GROUP1_SIZE stmts, since stores are consecutive), the second
1722 containing the remainder.
1723 Return the first stmt in the second group. */
1726 vect_split_slp_store_group (gimple
*first_stmt
, unsigned group1_size
)
1728 stmt_vec_info first_vinfo
= vinfo_for_stmt (first_stmt
);
1729 gcc_assert (GROUP_FIRST_ELEMENT (first_vinfo
) == first_stmt
);
1730 gcc_assert (group1_size
> 0);
1731 int group2_size
= GROUP_SIZE (first_vinfo
) - group1_size
;
1732 gcc_assert (group2_size
> 0);
1733 GROUP_SIZE (first_vinfo
) = group1_size
;
1735 gimple
*stmt
= first_stmt
;
1736 for (unsigned i
= group1_size
; i
> 1; i
--)
1738 stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
1739 gcc_assert (GROUP_GAP (vinfo_for_stmt (stmt
)) == 1);
1741 /* STMT is now the last element of the first group. */
1742 gimple
*group2
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
1743 GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
)) = 0;
1745 GROUP_SIZE (vinfo_for_stmt (group2
)) = group2_size
;
1746 for (stmt
= group2
; stmt
; stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
)))
1748 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = group2
;
1749 gcc_assert (GROUP_GAP (vinfo_for_stmt (stmt
)) == 1);
1752 /* For the second group, the GROUP_GAP is that before the original group,
1753 plus skipping over the first vector. */
1754 GROUP_GAP (vinfo_for_stmt (group2
)) =
1755 GROUP_GAP (first_vinfo
) + group1_size
;
1757 /* GROUP_GAP of the first group now has to skip over the second group too. */
1758 GROUP_GAP (first_vinfo
) += group2_size
;
1760 if (dump_enabled_p ())
1761 dump_printf_loc (MSG_NOTE
, vect_location
, "Split group into %d and %d\n",
1762 group1_size
, group2_size
);
1767 /* Analyze an SLP instance starting from a group of grouped stores. Call
1768 vect_build_slp_tree to build a tree of packed stmts if possible.
1769 Return FALSE if it's impossible to SLP any stmt in the loop. */
1772 vect_analyze_slp_instance (vec_info
*vinfo
,
1773 gimple
*stmt
, unsigned max_tree_size
)
1775 slp_instance new_instance
;
1777 unsigned int group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1778 unsigned int unrolling_factor
= 1, nunits
;
1779 tree vectype
, scalar_type
= NULL_TREE
;
1782 unsigned int max_nunits
= 0;
1783 vec
<slp_tree
> loads
;
1784 struct data_reference
*dr
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
));
1785 vec
<gimple
*> scalar_stmts
;
1787 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1791 scalar_type
= TREE_TYPE (DR_REF (dr
));
1792 vectype
= get_vectype_for_scalar_type (scalar_type
);
1796 gcc_assert (is_a
<loop_vec_info
> (vinfo
));
1797 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1800 group_size
= GROUP_SIZE (vinfo_for_stmt (stmt
));
1804 gcc_assert (is_a
<loop_vec_info
> (vinfo
));
1805 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1806 group_size
= as_a
<loop_vec_info
> (vinfo
)->reductions
.length ();
1811 if (dump_enabled_p ())
1813 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1814 "Build SLP failed: unsupported data-type ");
1815 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, scalar_type
);
1816 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1821 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
1823 /* Create a node (a root of the SLP tree) for the packed grouped stores. */
1824 scalar_stmts
.create (group_size
);
1826 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
1828 /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
1831 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next
))
1832 && STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)))
1833 scalar_stmts
.safe_push (
1834 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next
)));
1836 scalar_stmts
.safe_push (next
);
1837 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
1839 /* Mark the first element of the reduction chain as reduction to properly
1840 transform the node. In the reduction analysis phase only the last
1841 element of the chain is marked as reduction. */
1842 if (!STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
1843 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_reduction_def
;
1847 /* Collect reduction statements. */
1848 vec
<gimple
*> reductions
= as_a
<loop_vec_info
> (vinfo
)->reductions
;
1849 for (i
= 0; reductions
.iterate (i
, &next
); i
++)
1850 scalar_stmts
.safe_push (next
);
1853 loads
.create (group_size
);
1855 /* Build the tree for the SLP instance. */
1856 bool *matches
= XALLOCAVEC (bool, group_size
);
1857 unsigned npermutes
= 0;
1858 node
= vect_build_slp_tree (vinfo
, scalar_stmts
, group_size
,
1859 &max_nunits
, &loads
, matches
, &npermutes
,
1860 NULL
, max_tree_size
);
1863 /* Calculate the unrolling factor based on the smallest type. */
1865 = least_common_multiple (max_nunits
, group_size
) / group_size
;
1867 if (unrolling_factor
!= 1
1868 && is_a
<bb_vec_info
> (vinfo
))
1871 if (max_nunits
> group_size
)
1873 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1874 "Build SLP failed: store group "
1875 "size not a multiple of the vector size "
1876 "in basic block SLP\n");
1877 vect_free_slp_tree (node
);
1881 /* Fatal mismatch. */
1882 matches
[group_size
/max_nunits
* max_nunits
] = false;
1883 vect_free_slp_tree (node
);
1888 /* Create a new SLP instance. */
1889 new_instance
= XNEW (struct _slp_instance
);
1890 SLP_INSTANCE_TREE (new_instance
) = node
;
1891 SLP_INSTANCE_GROUP_SIZE (new_instance
) = group_size
;
1892 SLP_INSTANCE_UNROLLING_FACTOR (new_instance
) = unrolling_factor
;
1893 SLP_INSTANCE_LOADS (new_instance
) = loads
;
1895 /* Compute the load permutation. */
1897 bool loads_permuted
= false;
1898 FOR_EACH_VEC_ELT (loads
, i
, load_node
)
1900 vec
<unsigned> load_permutation
;
1902 gimple
*load
, *first_stmt
;
1903 bool this_load_permuted
= false;
1904 load_permutation
.create (group_size
);
1905 first_stmt
= GROUP_FIRST_ELEMENT
1906 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node
)[0]));
1907 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node
), j
, load
)
1909 int load_place
= vect_get_place_in_interleaving_chain
1911 gcc_assert (load_place
!= -1);
1912 if (load_place
!= j
)
1913 this_load_permuted
= true;
1914 load_permutation
.safe_push (load_place
);
1916 if (!this_load_permuted
1917 /* The load requires permutation when unrolling exposes
1918 a gap either because the group is larger than the SLP
1919 group-size or because there is a gap between the groups. */
1920 && (unrolling_factor
== 1
1921 || (group_size
== GROUP_SIZE (vinfo_for_stmt (first_stmt
))
1922 && GROUP_GAP (vinfo_for_stmt (first_stmt
)) == 0)))
1924 load_permutation
.release ();
1927 SLP_TREE_LOAD_PERMUTATION (load_node
) = load_permutation
;
1928 loads_permuted
= true;
1933 if (!vect_supported_load_permutation_p (new_instance
))
1935 if (dump_enabled_p ())
1937 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1938 "Build SLP failed: unsupported load "
1940 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
,
1943 vect_free_slp_instance (new_instance
);
1948 /* If the loads and stores can be handled with load/store-lan
1949 instructions do not generate this SLP instance. */
1950 if (is_a
<loop_vec_info
> (vinfo
)
1952 && dr
&& vect_store_lanes_supported (vectype
, group_size
))
1955 FOR_EACH_VEC_ELT (loads
, i
, load_node
)
1957 gimple
*first_stmt
= GROUP_FIRST_ELEMENT
1958 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node
)[0]));
1959 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (first_stmt
);
1960 /* Use SLP for strided accesses (or if we
1961 can't load-lanes). */
1962 if (STMT_VINFO_STRIDED_P (stmt_vinfo
)
1963 || ! vect_load_lanes_supported
1964 (STMT_VINFO_VECTYPE (stmt_vinfo
),
1965 GROUP_SIZE (stmt_vinfo
)))
1968 if (i
== loads
.length ())
1970 if (dump_enabled_p ())
1971 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1972 "Built SLP cancelled: can use "
1973 "load/store-lanes\n");
1974 vect_free_slp_instance (new_instance
);
1979 vinfo
->slp_instances
.safe_push (new_instance
);
1981 if (dump_enabled_p ())
1983 dump_printf_loc (MSG_NOTE
, vect_location
,
1984 "Final SLP tree for instance:\n");
1985 vect_print_slp_tree (MSG_NOTE
, vect_location
, node
);
1993 /* Failed to SLP. */
1994 /* Free the allocated memory. */
1995 scalar_stmts
.release ();
1999 /* For basic block SLP, try to break the group up into multiples of the
2001 if (is_a
<bb_vec_info
> (vinfo
)
2002 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
2003 && STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt
)))
2005 /* We consider breaking the group only on VF boundaries from the existing
2007 for (i
= 0; i
< group_size
; i
++)
2008 if (!matches
[i
]) break;
2010 if (i
>= nunits
&& i
< group_size
)
2012 /* Split into two groups at the first vector boundary before i. */
2013 gcc_assert ((nunits
& (nunits
- 1)) == 0);
2014 unsigned group1_size
= i
& ~(nunits
- 1);
2016 gimple
*rest
= vect_split_slp_store_group (stmt
, group1_size
);
2017 bool res
= vect_analyze_slp_instance (vinfo
, stmt
, max_tree_size
);
2018 /* If the first non-match was in the middle of a vector,
2019 skip the rest of that vector. */
2020 if (group1_size
< i
)
2022 i
= group1_size
+ nunits
;
2024 rest
= vect_split_slp_store_group (rest
, nunits
);
2027 res
|= vect_analyze_slp_instance (vinfo
, rest
, max_tree_size
);
2030 /* Even though the first vector did not all match, we might be able to SLP
2031 (some) of the remainder. FORNOW ignore this possibility. */
2038 /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
2039 trees of packed scalar stmts if SLP is possible. */
2042 vect_analyze_slp (vec_info
*vinfo
, unsigned max_tree_size
)
2045 gimple
*first_element
;
2048 if (dump_enabled_p ())
2049 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_analyze_slp ===\n");
2051 /* Find SLP sequences starting from groups of grouped stores. */
2052 FOR_EACH_VEC_ELT (vinfo
->grouped_stores
, i
, first_element
)
2053 if (vect_analyze_slp_instance (vinfo
, first_element
, max_tree_size
))
2056 if (loop_vec_info loop_vinfo
= dyn_cast
<loop_vec_info
> (vinfo
))
2058 if (loop_vinfo
->reduction_chains
.length () > 0)
2060 /* Find SLP sequences starting from reduction chains. */
2061 FOR_EACH_VEC_ELT (loop_vinfo
->reduction_chains
, i
, first_element
)
2062 if (vect_analyze_slp_instance (vinfo
, first_element
,
2068 /* Don't try to vectorize SLP reductions if reduction chain was
2073 /* Find SLP sequences starting from groups of reductions. */
2074 if (loop_vinfo
->reductions
.length () > 1
2075 && vect_analyze_slp_instance (vinfo
, loop_vinfo
->reductions
[0],
2084 /* For each possible SLP instance decide whether to SLP it and calculate overall
2085 unrolling factor needed to SLP the loop. Return TRUE if decided to SLP at
2086 least one instance. */
2089 vect_make_slp_decision (loop_vec_info loop_vinfo
)
2091 unsigned int i
, unrolling_factor
= 1;
2092 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2093 slp_instance instance
;
2094 int decided_to_slp
= 0;
2096 if (dump_enabled_p ())
2097 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_make_slp_decision ==="
2100 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2102 /* FORNOW: SLP if you can. */
2103 if (unrolling_factor
< SLP_INSTANCE_UNROLLING_FACTOR (instance
))
2104 unrolling_factor
= SLP_INSTANCE_UNROLLING_FACTOR (instance
);
2106 /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
2107 call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
2108 loop-based vectorization. Such stmts will be marked as HYBRID. */
2109 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2113 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
) = unrolling_factor
;
2115 if (decided_to_slp
&& dump_enabled_p ())
2116 dump_printf_loc (MSG_NOTE
, vect_location
,
2117 "Decided to SLP %d instances. Unrolling factor %d\n",
2118 decided_to_slp
, unrolling_factor
);
2120 return (decided_to_slp
> 0);
2124 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
2125 can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
2128 vect_detect_hybrid_slp_stmts (slp_tree node
, unsigned i
, slp_vect_type stype
)
2130 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[i
];
2131 imm_use_iterator imm_iter
;
2133 stmt_vec_info use_vinfo
, stmt_vinfo
= vinfo_for_stmt (stmt
);
2135 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
2136 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2139 /* Propagate hybrid down the SLP tree. */
2140 if (stype
== hybrid
)
2142 else if (HYBRID_SLP_STMT (stmt_vinfo
))
2146 /* Check if a pure SLP stmt has uses in non-SLP stmts. */
2147 gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo
));
2148 /* If we get a pattern stmt here we have to use the LHS of the
2149 original stmt for immediate uses. */
2150 if (! STMT_VINFO_IN_PATTERN_P (stmt_vinfo
)
2151 && STMT_VINFO_RELATED_STMT (stmt_vinfo
))
2152 stmt
= STMT_VINFO_RELATED_STMT (stmt_vinfo
);
2153 if (TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2154 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, gimple_op (stmt
, 0))
2156 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2158 use_vinfo
= vinfo_for_stmt (use_stmt
);
2159 if (STMT_VINFO_IN_PATTERN_P (use_vinfo
)
2160 && STMT_VINFO_RELATED_STMT (use_vinfo
))
2161 use_vinfo
= vinfo_for_stmt (STMT_VINFO_RELATED_STMT (use_vinfo
));
2162 if (!STMT_SLP_TYPE (use_vinfo
)
2163 && (STMT_VINFO_RELEVANT (use_vinfo
)
2164 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo
)))
2165 && !(gimple_code (use_stmt
) == GIMPLE_PHI
2166 && STMT_VINFO_DEF_TYPE (use_vinfo
) == vect_reduction_def
))
2168 if (dump_enabled_p ())
2170 dump_printf_loc (MSG_NOTE
, vect_location
, "use of SLP "
2171 "def in non-SLP stmt: ");
2172 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, use_stmt
, 0);
2180 && !HYBRID_SLP_STMT (stmt_vinfo
))
2182 if (dump_enabled_p ())
2184 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2185 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
2187 STMT_SLP_TYPE (stmt_vinfo
) = hybrid
;
2190 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2191 if (SLP_TREE_DEF_TYPE (child
) != vect_external_def
)
2192 vect_detect_hybrid_slp_stmts (child
, i
, stype
);
2195 /* Helpers for vect_detect_hybrid_slp walking pattern stmt uses. */
2198 vect_detect_hybrid_slp_1 (tree
*tp
, int *, void *data
)
2200 walk_stmt_info
*wi
= (walk_stmt_info
*)data
;
2201 struct loop
*loopp
= (struct loop
*)wi
->info
;
2206 if (TREE_CODE (*tp
) == SSA_NAME
2207 && !SSA_NAME_IS_DEFAULT_DEF (*tp
))
2209 gimple
*def_stmt
= SSA_NAME_DEF_STMT (*tp
);
2210 if (flow_bb_inside_loop_p (loopp
, gimple_bb (def_stmt
))
2211 && PURE_SLP_STMT (vinfo_for_stmt (def_stmt
)))
2213 if (dump_enabled_p ())
2215 dump_printf_loc (MSG_NOTE
, vect_location
, "marking hybrid: ");
2216 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2218 STMT_SLP_TYPE (vinfo_for_stmt (def_stmt
)) = hybrid
;
2226 vect_detect_hybrid_slp_2 (gimple_stmt_iterator
*gsi
, bool *handled
,
2229 /* If the stmt is in a SLP instance then this isn't a reason
2230 to mark use definitions in other SLP instances as hybrid. */
2231 if (STMT_SLP_TYPE (vinfo_for_stmt (gsi_stmt (*gsi
))) != loop_vect
)
2236 /* Find stmts that must be both vectorized and SLPed. */
2239 vect_detect_hybrid_slp (loop_vec_info loop_vinfo
)
2242 vec
<slp_instance
> slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2243 slp_instance instance
;
2245 if (dump_enabled_p ())
2246 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vect_detect_hybrid_slp ==="
2249 /* First walk all pattern stmt in the loop and mark defs of uses as
2250 hybrid because immediate uses in them are not recorded. */
2251 for (i
= 0; i
< LOOP_VINFO_LOOP (loop_vinfo
)->num_nodes
; ++i
)
2253 basic_block bb
= LOOP_VINFO_BBS (loop_vinfo
)[i
];
2254 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2257 gimple
*stmt
= gsi_stmt (gsi
);
2258 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2259 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
2262 memset (&wi
, 0, sizeof (wi
));
2263 wi
.info
= LOOP_VINFO_LOOP (loop_vinfo
);
2264 gimple_stmt_iterator gsi2
2265 = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info
));
2266 walk_gimple_stmt (&gsi2
, vect_detect_hybrid_slp_2
,
2267 vect_detect_hybrid_slp_1
, &wi
);
2268 walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
),
2269 vect_detect_hybrid_slp_2
,
2270 vect_detect_hybrid_slp_1
, &wi
);
2275 /* Then walk the SLP instance trees marking stmts with uses in
2276 non-SLP stmts as hybrid, also propagating hybrid down the
2277 SLP tree, collecting the above info on-the-fly. */
2278 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2280 for (unsigned i
= 0; i
< SLP_INSTANCE_GROUP_SIZE (instance
); ++i
)
2281 vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance
),
2287 /* Create and initialize a new bb_vec_info struct for BB, as well as
2288 stmt_vec_info structs for all the stmts in it. */
2291 new_bb_vec_info (gimple_stmt_iterator region_begin
,
2292 gimple_stmt_iterator region_end
)
2294 basic_block bb
= gsi_bb (region_begin
);
2295 bb_vec_info res
= NULL
;
2296 gimple_stmt_iterator gsi
;
2298 res
= (bb_vec_info
) xcalloc (1, sizeof (struct _bb_vec_info
));
2299 res
->kind
= vec_info::bb
;
2300 BB_VINFO_BB (res
) = bb
;
2301 res
->region_begin
= region_begin
;
2302 res
->region_end
= region_end
;
2304 for (gsi
= region_begin
; gsi_stmt (gsi
) != gsi_stmt (region_end
);
2307 gimple
*stmt
= gsi_stmt (gsi
);
2308 gimple_set_uid (stmt
, 0);
2309 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
));
2312 BB_VINFO_GROUPED_STORES (res
).create (10);
2313 BB_VINFO_SLP_INSTANCES (res
).create (2);
2314 BB_VINFO_TARGET_COST_DATA (res
) = init_cost (NULL
);
2321 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
2322 stmts in the basic block. */
2325 destroy_bb_vec_info (bb_vec_info bb_vinfo
)
2327 slp_instance instance
;
2333 vect_destroy_datarefs (bb_vinfo
);
2334 free_dependence_relations (BB_VINFO_DDRS (bb_vinfo
));
2335 BB_VINFO_GROUPED_STORES (bb_vinfo
).release ();
2336 FOR_EACH_VEC_ELT (BB_VINFO_SLP_INSTANCES (bb_vinfo
), i
, instance
)
2337 vect_free_slp_instance (instance
);
2338 BB_VINFO_SLP_INSTANCES (bb_vinfo
).release ();
2339 destroy_cost_data (BB_VINFO_TARGET_COST_DATA (bb_vinfo
));
2341 for (gimple_stmt_iterator si
= bb_vinfo
->region_begin
;
2342 gsi_stmt (si
) != gsi_stmt (bb_vinfo
->region_end
); gsi_next (&si
))
2344 gimple
*stmt
= gsi_stmt (si
);
2345 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2348 /* Free stmt_vec_info. */
2349 free_stmt_vec_info (stmt
);
2351 /* Reset region marker. */
2352 gimple_set_uid (stmt
, -1);
2355 BB_VINFO_BB (bb_vinfo
)->aux
= NULL
;
2360 /* Analyze statements contained in SLP tree node after recursively analyzing
2361 the subtree. Return TRUE if the operations are supported. */
2364 vect_slp_analyze_node_operations (slp_tree node
)
2371 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
2374 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2375 if (!vect_slp_analyze_node_operations (child
))
2379 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2381 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2382 gcc_assert (stmt_info
);
2383 gcc_assert (STMT_SLP_TYPE (stmt_info
) != loop_vect
);
2385 /* Push SLP node def-type to stmt operands. */
2386 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2387 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
2388 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child
)[i
]))
2389 = SLP_TREE_DEF_TYPE (child
);
2390 res
= vect_analyze_stmt (stmt
, &dummy
, node
);
2391 /* Restore def-types. */
2392 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), j
, child
)
2393 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
2394 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child
)[i
]))
2395 = vect_internal_def
;
2404 /* Analyze statements in SLP instances of the basic block. Return TRUE if the
2405 operations are supported. */
2408 vect_slp_analyze_operations (vec
<slp_instance
> slp_instances
, void *data
)
2410 slp_instance instance
;
2413 if (dump_enabled_p ())
2414 dump_printf_loc (MSG_NOTE
, vect_location
,
2415 "=== vect_slp_analyze_operations ===\n");
2417 for (i
= 0; slp_instances
.iterate (i
, &instance
); )
2419 if (!vect_slp_analyze_node_operations (SLP_INSTANCE_TREE (instance
)))
2421 dump_printf_loc (MSG_NOTE
, vect_location
,
2422 "removing SLP instance operations starting from: ");
2423 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
2424 SLP_TREE_SCALAR_STMTS
2425 (SLP_INSTANCE_TREE (instance
))[0], 0);
2426 vect_free_slp_instance (instance
);
2427 slp_instances
.ordered_remove (i
);
2431 /* Compute the costs of the SLP instance. */
2432 vect_analyze_slp_cost (instance
, data
);
2437 if (!slp_instances
.length ())
2444 /* Compute the scalar cost of the SLP node NODE and its children
2445 and return it. Do not account defs that are marked in LIFE and
2446 update LIFE according to uses of NODE. */
2449 vect_bb_slp_scalar_cost (basic_block bb
,
2450 slp_tree node
, vec
<bool, va_heap
> *life
)
2452 unsigned scalar_cost
= 0;
2457 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
2460 ssa_op_iter op_iter
;
2461 def_operand_p def_p
;
2462 stmt_vec_info stmt_info
;
2467 /* If there is a non-vectorized use of the defs then the scalar
2468 stmt is kept live in which case we do not account it or any
2469 required defs in the SLP children in the scalar cost. This
2470 way we make the vectorization more costly when compared to
2472 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
2474 imm_use_iterator use_iter
;
2476 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, DEF_FROM_PTR (def_p
))
2477 if (!is_gimple_debug (use_stmt
)
2478 && (! vect_stmt_in_region_p (vinfo_for_stmt (stmt
)->vinfo
,
2480 || ! PURE_SLP_STMT (vinfo_for_stmt (use_stmt
))))
2483 BREAK_FROM_IMM_USE_STMT (use_iter
);
2489 /* Count scalar stmts only once. */
2490 if (gimple_visited_p (stmt
))
2492 gimple_set_visited (stmt
, true);
2494 stmt_info
= vinfo_for_stmt (stmt
);
2495 if (STMT_VINFO_DATA_REF (stmt_info
))
2497 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)))
2498 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2500 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2503 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2505 scalar_cost
+= stmt_cost
;
2508 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
2509 if (SLP_TREE_DEF_TYPE (child
) == vect_internal_def
)
2510 scalar_cost
+= vect_bb_slp_scalar_cost (bb
, child
, life
);
2515 /* Check if vectorization of the basic block is profitable. */
2518 vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo
)
2520 vec
<slp_instance
> slp_instances
= BB_VINFO_SLP_INSTANCES (bb_vinfo
);
2521 slp_instance instance
;
2523 unsigned int vec_inside_cost
= 0, vec_outside_cost
= 0, scalar_cost
= 0;
2524 unsigned int vec_prologue_cost
= 0, vec_epilogue_cost
= 0;
2526 /* Calculate scalar cost. */
2527 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
2529 auto_vec
<bool, 20> life
;
2530 life
.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance
));
2531 scalar_cost
+= vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo
),
2532 SLP_INSTANCE_TREE (instance
),
2536 /* Unset visited flag. */
2537 for (gimple_stmt_iterator gsi
= bb_vinfo
->region_begin
;
2538 gsi_stmt (gsi
) != gsi_stmt (bb_vinfo
->region_end
); gsi_next (&gsi
))
2539 gimple_set_visited (gsi_stmt (gsi
), false);
2541 /* Complete the target-specific cost calculation. */
2542 finish_cost (BB_VINFO_TARGET_COST_DATA (bb_vinfo
), &vec_prologue_cost
,
2543 &vec_inside_cost
, &vec_epilogue_cost
);
2545 vec_outside_cost
= vec_prologue_cost
+ vec_epilogue_cost
;
2547 if (dump_enabled_p ())
2549 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2550 dump_printf (MSG_NOTE
, " Vector inside of basic block cost: %d\n",
2552 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n", vec_prologue_cost
);
2553 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n", vec_epilogue_cost
);
2554 dump_printf (MSG_NOTE
, " Scalar cost of basic block: %d\n", scalar_cost
);
2557 /* Vectorization is profitable if its cost is more than the cost of scalar
2558 version. Note that we err on the vector side for equal cost because
2559 the cost estimate is otherwise quite pessimistic (constant uses are
2560 free on the scalar side but cost a load on the vector side for
2562 if (vec_outside_cost
+ vec_inside_cost
> scalar_cost
)
2568 /* Check if the basic block can be vectorized. Returns a bb_vec_info
2569 if so and sets fatal to true if failure is independent of
2570 current_vector_size. */
2573 vect_slp_analyze_bb_1 (gimple_stmt_iterator region_begin
,
2574 gimple_stmt_iterator region_end
,
2575 vec
<data_reference_p
> datarefs
, int n_stmts
,
2578 bb_vec_info bb_vinfo
;
2579 slp_instance instance
;
2583 /* The first group of checks is independent of the vector size. */
2586 if (n_stmts
> PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB
))
2588 if (dump_enabled_p ())
2589 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2590 "not vectorized: too many instructions in "
2592 free_data_refs (datarefs
);
2596 bb_vinfo
= new_bb_vec_info (region_begin
, region_end
);
2600 BB_VINFO_DATAREFS (bb_vinfo
) = datarefs
;
2602 /* Analyze the data references. */
2604 if (!vect_analyze_data_refs (bb_vinfo
, &min_vf
))
2606 if (dump_enabled_p ())
2607 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2608 "not vectorized: unhandled data-ref in basic "
2611 destroy_bb_vec_info (bb_vinfo
);
2615 if (BB_VINFO_DATAREFS (bb_vinfo
).length () < 2)
2617 if (dump_enabled_p ())
2618 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2619 "not vectorized: not enough data-refs in "
2622 destroy_bb_vec_info (bb_vinfo
);
2626 if (!vect_analyze_data_ref_accesses (bb_vinfo
))
2628 if (dump_enabled_p ())
2629 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2630 "not vectorized: unhandled data access in "
2633 destroy_bb_vec_info (bb_vinfo
);
2637 /* If there are no grouped stores in the region there is no need
2638 to continue with pattern recog as vect_analyze_slp will fail
2640 if (bb_vinfo
->grouped_stores
.is_empty ())
2642 if (dump_enabled_p ())
2643 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2644 "not vectorized: no grouped stores in "
2647 destroy_bb_vec_info (bb_vinfo
);
2651 /* While the rest of the analysis below depends on it in some way. */
2654 vect_pattern_recog (bb_vinfo
);
2656 /* Check the SLP opportunities in the basic block, analyze and build SLP
2658 if (!vect_analyze_slp (bb_vinfo
, n_stmts
))
2660 if (dump_enabled_p ())
2662 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2663 "Failed to SLP the basic block.\n");
2664 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2665 "not vectorized: failed to find SLP opportunities "
2666 "in basic block.\n");
2669 destroy_bb_vec_info (bb_vinfo
);
2673 /* Analyze and verify the alignment of data references and the
2674 dependence in the SLP instances. */
2675 for (i
= 0; BB_VINFO_SLP_INSTANCES (bb_vinfo
).iterate (i
, &instance
); )
2677 if (! vect_slp_analyze_and_verify_instance_alignment (instance
)
2678 || ! vect_slp_analyze_instance_dependence (instance
))
2680 dump_printf_loc (MSG_NOTE
, vect_location
,
2681 "removing SLP instance operations starting from: ");
2682 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
2683 SLP_TREE_SCALAR_STMTS
2684 (SLP_INSTANCE_TREE (instance
))[0], 0);
2685 vect_free_slp_instance (instance
);
2686 BB_VINFO_SLP_INSTANCES (bb_vinfo
).ordered_remove (i
);
2690 /* Mark all the statements that we want to vectorize as pure SLP and
2692 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance
), pure_slp
, -1);
2693 vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance
));
2697 if (! BB_VINFO_SLP_INSTANCES (bb_vinfo
).length ())
2699 destroy_bb_vec_info (bb_vinfo
);
2703 if (!vect_slp_analyze_operations (BB_VINFO_SLP_INSTANCES (bb_vinfo
),
2704 BB_VINFO_TARGET_COST_DATA (bb_vinfo
)))
2706 if (dump_enabled_p ())
2707 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2708 "not vectorized: bad operation in basic block.\n");
2710 destroy_bb_vec_info (bb_vinfo
);
2714 /* Cost model: check if the vectorization is worthwhile. */
2715 if (!unlimited_cost_model (NULL
)
2716 && !vect_bb_vectorization_profitable_p (bb_vinfo
))
2718 if (dump_enabled_p ())
2719 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2720 "not vectorized: vectorization is not "
2723 destroy_bb_vec_info (bb_vinfo
);
2727 if (dump_enabled_p ())
2728 dump_printf_loc (MSG_NOTE
, vect_location
,
2729 "Basic block will be vectorized using SLP\n");
2735 /* Main entry for the BB vectorizer. Analyze and transform BB, returns
2736 true if anything in the basic-block was vectorized. */
2739 vect_slp_bb (basic_block bb
)
2741 bb_vec_info bb_vinfo
;
2742 gimple_stmt_iterator gsi
;
2743 unsigned int vector_sizes
;
2744 bool any_vectorized
= false;
2746 if (dump_enabled_p ())
2747 dump_printf_loc (MSG_NOTE
, vect_location
, "===vect_slp_analyze_bb===\n");
2749 /* Autodetect first vector size we try. */
2750 current_vector_size
= 0;
2751 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2753 gsi
= gsi_start_bb (bb
);
2757 if (gsi_end_p (gsi
))
2760 gimple_stmt_iterator region_begin
= gsi
;
2761 vec
<data_reference_p
> datarefs
= vNULL
;
2764 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
2766 gimple
*stmt
= gsi_stmt (gsi
);
2767 if (is_gimple_debug (stmt
))
2771 if (gimple_location (stmt
) != UNKNOWN_LOCATION
)
2772 vect_location
= gimple_location (stmt
);
2774 if (!find_data_references_in_stmt (NULL
, stmt
, &datarefs
))
2778 /* Skip leading unhandled stmts. */
2779 if (gsi_stmt (region_begin
) == gsi_stmt (gsi
))
2785 gimple_stmt_iterator region_end
= gsi
;
2787 bool vectorized
= false;
2789 bb_vinfo
= vect_slp_analyze_bb_1 (region_begin
, region_end
,
2790 datarefs
, insns
, fatal
);
2792 && dbg_cnt (vect_slp
))
2794 if (dump_enabled_p ())
2795 dump_printf_loc (MSG_NOTE
, vect_location
, "SLPing BB part\n");
2797 vect_schedule_slp (bb_vinfo
);
2799 if (dump_enabled_p ())
2800 dump_printf_loc (MSG_NOTE
, vect_location
,
2801 "basic block part vectorized\n");
2803 destroy_bb_vec_info (bb_vinfo
);
2808 destroy_bb_vec_info (bb_vinfo
);
2810 any_vectorized
|= vectorized
;
2812 vector_sizes
&= ~current_vector_size
;
2814 || vector_sizes
== 0
2815 || current_vector_size
== 0
2816 /* If vect_slp_analyze_bb_1 signaled that analysis for all
2817 vector sizes will fail do not bother iterating. */
2820 if (gsi_end_p (region_end
))
2823 /* Skip the unhandled stmt. */
2826 /* And reset vector sizes. */
2827 current_vector_size
= 0;
2828 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2832 /* Try the next biggest vector size. */
2833 current_vector_size
= 1 << floor_log2 (vector_sizes
);
2834 if (dump_enabled_p ())
2835 dump_printf_loc (MSG_NOTE
, vect_location
,
2836 "***** Re-trying analysis with "
2837 "vector size %d\n", current_vector_size
);
2844 return any_vectorized
;
2848 /* Return 1 if vector type of boolean constant which is OPNUM
2849 operand in statement STMT is a boolean vector. */
2852 vect_mask_constant_operand_p (gimple
*stmt
, int opnum
)
2854 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2855 enum tree_code code
= gimple_expr_code (stmt
);
2858 enum vect_def_type dt
;
2860 /* For comparison and COND_EXPR type is chosen depending
2861 on the other comparison operand. */
2862 if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2865 op
= gimple_assign_rhs1 (stmt
);
2867 op
= gimple_assign_rhs2 (stmt
);
2869 if (!vect_is_simple_use (op
, stmt_vinfo
->vinfo
, &def_stmt
,
2873 return !vectype
|| VECTOR_BOOLEAN_TYPE_P (vectype
);
2876 if (code
== COND_EXPR
)
2878 tree cond
= gimple_assign_rhs1 (stmt
);
2880 if (TREE_CODE (cond
) == SSA_NAME
)
2884 op
= TREE_OPERAND (cond
, 1);
2886 op
= TREE_OPERAND (cond
, 0);
2888 if (!vect_is_simple_use (op
, stmt_vinfo
->vinfo
, &def_stmt
,
2892 return !vectype
|| VECTOR_BOOLEAN_TYPE_P (vectype
);
2895 return VECTOR_BOOLEAN_TYPE_P (STMT_VINFO_VECTYPE (stmt_vinfo
));
2899 /* For constant and loop invariant defs of SLP_NODE this function returns
2900 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
2901 OP_NUM determines if we gather defs for operand 0 or operand 1 of the RHS of
2902 scalar stmts. NUMBER_OF_VECTORS is the number of vector defs to create.
2903 REDUC_INDEX is the index of the reduction operand in the statements, unless
2907 vect_get_constant_vectors (tree op
, slp_tree slp_node
,
2908 vec
<tree
> *vec_oprnds
,
2909 unsigned int op_num
, unsigned int number_of_vectors
,
2912 vec
<gimple
*> stmts
= SLP_TREE_SCALAR_STMTS (slp_node
);
2913 gimple
*stmt
= stmts
[0];
2914 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2918 unsigned j
, number_of_places_left_in_vector
;
2921 int group_size
= stmts
.length ();
2922 unsigned int vec_num
, i
;
2923 unsigned number_of_copies
= 1;
2925 voprnds
.create (number_of_vectors
);
2926 bool constant_p
, is_store
;
2927 tree neutral_op
= NULL
;
2928 enum tree_code code
= gimple_expr_code (stmt
);
2931 gimple_seq ctor_seq
= NULL
;
2933 /* Check if vector type is a boolean vector. */
2934 if (TREE_CODE (TREE_TYPE (op
)) == BOOLEAN_TYPE
2935 && vect_mask_constant_operand_p (stmt
, op_num
))
2937 = build_same_sized_truth_vector_type (STMT_VINFO_VECTYPE (stmt_vinfo
));
2939 vector_type
= get_vectype_for_scalar_type (TREE_TYPE (op
));
2940 nunits
= TYPE_VECTOR_SUBPARTS (vector_type
);
2942 if (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_reduction_def
2943 && reduc_index
!= -1)
2945 op_num
= reduc_index
;
2946 op
= gimple_op (stmt
, op_num
+ 1);
2947 /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
2948 we need either neutral operands or the original operands. See
2949 get_initial_def_for_reduction() for details. */
2952 case WIDEN_SUM_EXPR
:
2959 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2960 neutral_op
= build_real (TREE_TYPE (op
), dconst0
);
2962 neutral_op
= build_int_cst (TREE_TYPE (op
), 0);
2967 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
2968 neutral_op
= build_real (TREE_TYPE (op
), dconst1
);
2970 neutral_op
= build_int_cst (TREE_TYPE (op
), 1);
2975 neutral_op
= build_int_cst (TREE_TYPE (op
), -1);
2978 /* For MIN/MAX we don't have an easy neutral operand but
2979 the initial values can be used fine here. Only for
2980 a reduction chain we have to force a neutral element. */
2983 if (!GROUP_FIRST_ELEMENT (stmt_vinfo
))
2987 def_stmt
= SSA_NAME_DEF_STMT (op
);
2988 loop
= (gimple_bb (stmt
))->loop_father
;
2989 neutral_op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
2990 loop_preheader_edge (loop
));
2995 gcc_assert (!GROUP_FIRST_ELEMENT (stmt_vinfo
));
3000 if (STMT_VINFO_DATA_REF (stmt_vinfo
))
3003 op
= gimple_assign_rhs1 (stmt
);
3010 if (CONSTANT_CLASS_P (op
))
3015 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
3016 created vectors. It is greater than 1 if unrolling is performed.
3018 For example, we have two scalar operands, s1 and s2 (e.g., group of
3019 strided accesses of size two), while NUNITS is four (i.e., four scalars
3020 of this type can be packed in a vector). The output vector will contain
3021 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
3024 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
3025 containing the operands.
3027 For example, NUNITS is four as before, and the group size is 8
3028 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
3029 {s5, s6, s7, s8}. */
3031 number_of_copies
= nunits
* number_of_vectors
/ group_size
;
3033 number_of_places_left_in_vector
= nunits
;
3034 elts
= XALLOCAVEC (tree
, nunits
);
3035 bool place_after_defs
= false;
3036 for (j
= 0; j
< number_of_copies
; j
++)
3038 for (i
= group_size
- 1; stmts
.iterate (i
, &stmt
); i
--)
3041 op
= gimple_assign_rhs1 (stmt
);
3048 tree cond
= gimple_assign_rhs1 (stmt
);
3049 if (TREE_CODE (cond
) == SSA_NAME
)
3050 op
= gimple_op (stmt
, op_num
+ 1);
3051 else if (op_num
== 0 || op_num
== 1)
3052 op
= TREE_OPERAND (cond
, op_num
);
3056 op
= gimple_assign_rhs2 (stmt
);
3058 op
= gimple_assign_rhs3 (stmt
);
3064 op
= gimple_call_arg (stmt
, op_num
);
3071 op
= gimple_op (stmt
, op_num
+ 1);
3072 /* Unlike the other binary operators, shifts/rotates have
3073 the shift count being int, instead of the same type as
3074 the lhs, so make sure the scalar is the right type if
3075 we are dealing with vectors of
3076 long long/long/short/char. */
3077 if (op_num
== 1 && TREE_CODE (op
) == INTEGER_CST
)
3078 op
= fold_convert (TREE_TYPE (vector_type
), op
);
3082 op
= gimple_op (stmt
, op_num
+ 1);
3087 if (reduc_index
!= -1)
3089 loop
= (gimple_bb (stmt
))->loop_father
;
3090 def_stmt
= SSA_NAME_DEF_STMT (op
);
3094 /* Get the def before the loop. In reduction chain we have only
3095 one initial value. */
3096 if ((j
!= (number_of_copies
- 1)
3097 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
))
3102 op
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
3103 loop_preheader_edge (loop
));
3106 /* Create 'vect_ = {op0,op1,...,opn}'. */
3107 number_of_places_left_in_vector
--;
3109 if (!types_compatible_p (TREE_TYPE (vector_type
), TREE_TYPE (op
)))
3111 if (CONSTANT_CLASS_P (op
))
3113 if (VECTOR_BOOLEAN_TYPE_P (vector_type
))
3115 /* Can't use VIEW_CONVERT_EXPR for booleans because
3116 of possibly different sizes of scalar value and
3118 if (integer_zerop (op
))
3119 op
= build_int_cst (TREE_TYPE (vector_type
), 0);
3120 else if (integer_onep (op
))
3121 op
= build_all_ones_cst (TREE_TYPE (vector_type
));
3126 op
= fold_unary (VIEW_CONVERT_EXPR
,
3127 TREE_TYPE (vector_type
), op
);
3128 gcc_assert (op
&& CONSTANT_CLASS_P (op
));
3132 tree new_temp
= make_ssa_name (TREE_TYPE (vector_type
));
3134 if (VECTOR_BOOLEAN_TYPE_P (vector_type
))
3137 = build_all_ones_cst (TREE_TYPE (vector_type
));
3139 = build_zero_cst (TREE_TYPE (vector_type
));
3140 gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (op
)));
3141 init_stmt
= gimple_build_assign (new_temp
, COND_EXPR
,
3147 op
= build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (vector_type
),
3150 = gimple_build_assign (new_temp
, VIEW_CONVERT_EXPR
,
3153 gimple_seq_add_stmt (&ctor_seq
, init_stmt
);
3157 elts
[number_of_places_left_in_vector
] = op
;
3158 if (!CONSTANT_CLASS_P (op
))
3160 if (TREE_CODE (orig_op
) == SSA_NAME
3161 && !SSA_NAME_IS_DEFAULT_DEF (orig_op
)
3162 && STMT_VINFO_BB_VINFO (stmt_vinfo
)
3163 && (STMT_VINFO_BB_VINFO (stmt_vinfo
)->bb
3164 == gimple_bb (SSA_NAME_DEF_STMT (orig_op
))))
3165 place_after_defs
= true;
3167 if (number_of_places_left_in_vector
== 0)
3169 number_of_places_left_in_vector
= nunits
;
3172 vec_cst
= build_vector (vector_type
, elts
);
3175 vec
<constructor_elt
, va_gc
> *v
;
3177 vec_alloc (v
, nunits
);
3178 for (k
= 0; k
< nunits
; ++k
)
3179 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[k
]);
3180 vec_cst
= build_constructor (vector_type
, v
);
3183 gimple_stmt_iterator gsi
;
3184 if (place_after_defs
)
3187 (vect_find_last_scalar_stmt_in_slp (slp_node
));
3188 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, &gsi
);
3191 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, NULL
);
3192 if (ctor_seq
!= NULL
)
3194 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (init
));
3195 gsi_insert_seq_before_without_update (&gsi
, ctor_seq
,
3199 voprnds
.quick_push (init
);
3200 place_after_defs
= false;
3205 /* Since the vectors are created in the reverse order, we should invert
3207 vec_num
= voprnds
.length ();
3208 for (j
= vec_num
; j
!= 0; j
--)
3210 vop
= voprnds
[j
- 1];
3211 vec_oprnds
->quick_push (vop
);
3216 /* In case that VF is greater than the unrolling factor needed for the SLP
3217 group of stmts, NUMBER_OF_VECTORS to be created is greater than
3218 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
3219 to replicate the vectors. */
3220 while (number_of_vectors
> vec_oprnds
->length ())
3222 tree neutral_vec
= NULL
;
3227 neutral_vec
= build_vector_from_val (vector_type
, neutral_op
);
3229 vec_oprnds
->quick_push (neutral_vec
);
3233 for (i
= 0; vec_oprnds
->iterate (i
, &vop
) && i
< vec_num
; i
++)
3234 vec_oprnds
->quick_push (vop
);
3240 /* Get vectorized definitions from SLP_NODE that contains corresponding
3241 vectorized def-stmts. */
3244 vect_get_slp_vect_defs (slp_tree slp_node
, vec
<tree
> *vec_oprnds
)
3247 gimple
*vec_def_stmt
;
3250 gcc_assert (SLP_TREE_VEC_STMTS (slp_node
).exists ());
3252 FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (slp_node
), i
, vec_def_stmt
)
3254 gcc_assert (vec_def_stmt
);
3255 vec_oprnd
= gimple_get_lhs (vec_def_stmt
);
3256 vec_oprnds
->quick_push (vec_oprnd
);
3261 /* Get vectorized definitions for SLP_NODE.
3262 If the scalar definitions are loop invariants or constants, collect them and
3263 call vect_get_constant_vectors() to create vector stmts.
3264 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
3265 must be stored in the corresponding child of SLP_NODE, and we call
3266 vect_get_slp_vect_defs () to retrieve them. */
3269 vect_get_slp_defs (vec
<tree
> ops
, slp_tree slp_node
,
3270 vec
<vec
<tree
> > *vec_oprnds
, int reduc_index
)
3273 int number_of_vects
= 0, i
;
3274 HOST_WIDE_INT lhs_size_unit
, rhs_size_unit
;
3275 slp_tree child
= NULL
;
3278 bool first_iteration
= true;
3280 first_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[0];
3281 FOR_EACH_VEC_ELT (ops
, i
, oprnd
)
3283 bool vectorized_defs
= false;
3288 vec_defs
.create (0);
3289 vec_oprnds
->quick_push (vec_defs
);
3293 /* For each operand we check if it has vectorized definitions in a child
3294 node or we need to create them (for invariants and constants). We
3295 check if the LHS of the first stmt of the next child matches OPRND.
3296 If it does, we found the correct child. Otherwise, we call
3297 vect_get_constant_vectors (). */
3298 for (unsigned int child_index
= 0;
3299 child_index
< SLP_TREE_CHILDREN (slp_node
).length (); child_index
++)
3301 child
= SLP_TREE_CHILDREN (slp_node
)[child_index
];
3303 /* We have to check both pattern and original def, if available. */
3304 if (SLP_TREE_DEF_TYPE (child
) == vect_internal_def
)
3306 gimple
*first_def
= SLP_TREE_SCALAR_STMTS (child
)[0];
3308 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def
));
3310 if (operand_equal_p (oprnd
, gimple_get_lhs (first_def
), 0)
3312 && operand_equal_p (oprnd
, gimple_get_lhs (related
), 0)))
3314 /* The number of vector defs is determined by the number of
3315 vector statements in the node from which we get those
3317 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (child
);
3318 vectorized_defs
= true;
3324 if (!vectorized_defs
&& first_iteration
)
3326 number_of_vects
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
3327 /* Number of vector stmts was calculated according to LHS in
3328 vect_schedule_slp_instance (), fix it by replacing LHS with
3329 RHS, if necessary. See vect_get_smallest_scalar_type () for
3331 vect_get_smallest_scalar_type (first_stmt
, &lhs_size_unit
,
3333 if (rhs_size_unit
!= lhs_size_unit
)
3335 number_of_vects
*= rhs_size_unit
;
3336 number_of_vects
/= lhs_size_unit
;
3340 /* Allocate memory for vectorized defs. */
3342 vec_defs
.create (number_of_vects
);
3344 /* For reduction defs we call vect_get_constant_vectors (), since we are
3345 looking for initial loop invariant values. */
3346 if (vectorized_defs
&& reduc_index
== -1)
3347 /* The defs are already vectorized. */
3348 vect_get_slp_vect_defs (child
, &vec_defs
);
3350 /* Build vectors from scalar defs. */
3351 vect_get_constant_vectors (oprnd
, slp_node
, &vec_defs
, i
,
3352 number_of_vects
, reduc_index
);
3354 vec_oprnds
->quick_push (vec_defs
);
3356 /* For reductions, we only need initial values. */
3357 if (reduc_index
!= -1)
3360 first_iteration
= false;
3365 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
3366 building a vector of type MASK_TYPE from it) and two input vectors placed in
3367 DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
3368 shifting by STRIDE elements of DR_CHAIN for every copy.
3369 (STRIDE is the number of vectorized stmts for NODE divided by the number of
3371 VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
3372 the created stmts must be inserted. */
3375 vect_create_mask_and_perm (gimple
*stmt
,
3376 tree mask
, int first_vec_indx
, int second_vec_indx
,
3377 gimple_stmt_iterator
*gsi
, slp_tree node
,
3378 tree vectype
, vec
<tree
> dr_chain
,
3379 int ncopies
, int vect_stmts_counter
)
3382 gimple
*perm_stmt
= NULL
;
3383 int i
, stride_in
, stride_out
;
3384 tree first_vec
, second_vec
, data_ref
;
3386 stride_out
= SLP_TREE_NUMBER_OF_VEC_STMTS (node
) / ncopies
;
3387 stride_in
= dr_chain
.length () / ncopies
;
3389 /* Initialize the vect stmts of NODE to properly insert the generated
3391 for (i
= SLP_TREE_VEC_STMTS (node
).length ();
3392 i
< (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node
); i
++)
3393 SLP_TREE_VEC_STMTS (node
).quick_push (NULL
);
3395 perm_dest
= vect_create_destination_var (gimple_assign_lhs (stmt
), vectype
);
3396 for (i
= 0; i
< ncopies
; i
++)
3398 first_vec
= dr_chain
[first_vec_indx
];
3399 second_vec
= dr_chain
[second_vec_indx
];
3401 /* Generate the permute statement if necessary. */
3404 perm_stmt
= gimple_build_assign (perm_dest
, VEC_PERM_EXPR
,
3405 first_vec
, second_vec
, mask
);
3406 data_ref
= make_ssa_name (perm_dest
, perm_stmt
);
3407 gimple_set_lhs (perm_stmt
, data_ref
);
3408 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
3411 /* If mask was NULL_TREE generate the requested identity transform. */
3412 perm_stmt
= SSA_NAME_DEF_STMT (first_vec
);
3414 /* Store the vector statement in NODE. */
3415 SLP_TREE_VEC_STMTS (node
)[stride_out
* i
+ vect_stmts_counter
]
3418 first_vec_indx
+= stride_in
;
3419 second_vec_indx
+= stride_in
;
3424 /* Generate vector permute statements from a list of loads in DR_CHAIN.
3425 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
3426 permute statements for the SLP node NODE of the SLP instance
3427 SLP_NODE_INSTANCE. */
3430 vect_transform_slp_perm_load (slp_tree node
, vec
<tree
> dr_chain
,
3431 gimple_stmt_iterator
*gsi
, int vf
,
3432 slp_instance slp_node_instance
, bool analyze_only
,
3435 gimple
*stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3436 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3437 tree mask_element_type
= NULL_TREE
, mask_type
;
3438 int nunits
, vec_index
= 0;
3439 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3440 int group_size
= SLP_INSTANCE_GROUP_SIZE (slp_node_instance
);
3441 int unroll_factor
, mask_element
, ncopies
;
3442 unsigned char *mask
;
3445 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3448 stmt_info
= vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info
));
3450 mode
= TYPE_MODE (vectype
);
3452 /* The generic VEC_PERM_EXPR code always uses an integral type of the
3453 same size as the vector element being permuted. */
3454 mask_element_type
= lang_hooks
.types
.type_for_mode
3455 (int_mode_for_mode (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3456 mask_type
= get_vectype_for_scalar_type (mask_element_type
);
3457 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3458 mask
= XALLOCAVEC (unsigned char, nunits
);
3459 unroll_factor
= SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3461 /* Number of copies is determined by the final vectorization factor
3462 relatively to SLP_NODE_INSTANCE unrolling factor. */
3463 ncopies
= vf
/ SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance
);
3465 /* Generate permutation masks for every NODE. Number of masks for each NODE
3466 is equal to GROUP_SIZE.
3467 E.g., we have a group of three nodes with three loads from the same
3468 location in each node, and the vector size is 4. I.e., we have a
3469 a0b0c0a1b1c1... sequence and we need to create the following vectors:
3470 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
3471 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
3474 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9}.
3475 The last mask is illegal since we assume two operands for permute
3476 operation, and the mask element values can't be outside that range.
3477 Hence, the last mask must be converted into {2,5,5,5}.
3478 For the first two permutations we need the first and the second input
3479 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
3480 we need the second and the third vectors: {b1,c1,a2,b2} and
3483 int vect_stmts_counter
= 0;
3485 int first_vec_index
= -1;
3486 int second_vec_index
= -1;
3490 for (int j
= 0; j
< unroll_factor
; j
++)
3492 for (int k
= 0; k
< group_size
; k
++)
3494 int i
= (SLP_TREE_LOAD_PERMUTATION (node
)[k
]
3495 + j
* STMT_VINFO_GROUP_SIZE (stmt_info
));
3496 vec_index
= i
/ nunits
;
3497 mask_element
= i
% nunits
;
3498 if (vec_index
== first_vec_index
3499 || first_vec_index
== -1)
3501 first_vec_index
= vec_index
;
3503 else if (vec_index
== second_vec_index
3504 || second_vec_index
== -1)
3506 second_vec_index
= vec_index
;
3507 mask_element
+= nunits
;
3511 if (dump_enabled_p ())
3513 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3514 "permutation requires at "
3515 "least three vectors ");
3516 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
3522 gcc_assert (mask_element
>= 0
3523 && mask_element
< 2 * nunits
);
3524 if (mask_element
!= index
)
3526 mask
[index
++] = mask_element
;
3528 if (index
== nunits
)
3531 && ! can_vec_perm_p (mode
, false, mask
))
3533 if (dump_enabled_p ())
3535 dump_printf_loc (MSG_MISSED_OPTIMIZATION
,
3537 "unsupported vect permute { ");
3538 for (i
= 0; i
< nunits
; ++i
)
3539 dump_printf (MSG_MISSED_OPTIMIZATION
, "%d ", mask
[i
]);
3540 dump_printf (MSG_MISSED_OPTIMIZATION
, "}\n");
3550 tree mask_vec
= NULL_TREE
;
3554 tree
*mask_elts
= XALLOCAVEC (tree
, nunits
);
3555 for (int l
= 0; l
< nunits
; ++l
)
3556 mask_elts
[l
] = build_int_cst (mask_element_type
,
3558 mask_vec
= build_vector (mask_type
, mask_elts
);
3561 if (second_vec_index
== -1)
3562 second_vec_index
= first_vec_index
;
3563 vect_create_mask_and_perm (stmt
, mask_vec
, first_vec_index
,
3565 gsi
, node
, vectype
, dr_chain
,
3566 ncopies
, vect_stmts_counter
++);
3570 first_vec_index
= -1;
3571 second_vec_index
= -1;
3582 /* Vectorize SLP instance tree in postorder. */
3585 vect_schedule_slp_instance (slp_tree node
, slp_instance instance
,
3586 unsigned int vectorization_factor
)
3589 bool grouped_store
, is_store
;
3590 gimple_stmt_iterator si
;
3591 stmt_vec_info stmt_info
;
3592 unsigned int vec_stmts_size
, nunits
, group_size
;
3597 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
3600 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3601 vect_schedule_slp_instance (child
, instance
, vectorization_factor
);
3603 /* Push SLP node def-type to stmts. */
3604 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3605 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
3606 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
3607 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = SLP_TREE_DEF_TYPE (child
);
3609 stmt
= SLP_TREE_SCALAR_STMTS (node
)[0];
3610 stmt_info
= vinfo_for_stmt (stmt
);
3612 /* VECTYPE is the type of the destination. */
3613 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3614 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (vectype
);
3615 group_size
= SLP_INSTANCE_GROUP_SIZE (instance
);
3617 /* For each SLP instance calculate number of vector stmts to be created
3618 for the scalar stmts in each node of the SLP tree. Number of vector
3619 elements in one vector iteration is the number of scalar elements in
3620 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
3622 Unless this is a SLP reduction in which case the number of vector
3623 stmts is equal to the number of vector stmts of the children. */
3624 if (GROUP_FIRST_ELEMENT (stmt_info
)
3625 && !STMT_VINFO_GROUPED_ACCESS (stmt_info
))
3626 vec_stmts_size
= SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_CHILDREN (node
)[0]);
3628 vec_stmts_size
= (vectorization_factor
* group_size
) / nunits
;
3630 if (!SLP_TREE_VEC_STMTS (node
).exists ())
3632 SLP_TREE_VEC_STMTS (node
).create (vec_stmts_size
);
3633 SLP_TREE_NUMBER_OF_VEC_STMTS (node
) = vec_stmts_size
;
3636 if (dump_enabled_p ())
3638 dump_printf_loc (MSG_NOTE
,vect_location
,
3639 "------>vectorizing SLP node starting from: ");
3640 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3643 /* Vectorized stmts go before the last scalar stmt which is where
3644 all uses are ready. */
3645 si
= gsi_for_stmt (vect_find_last_scalar_stmt_in_slp (node
));
3647 /* Mark the first element of the reduction chain as reduction to properly
3648 transform the node. In the analysis phase only the last element of the
3649 chain is marked as reduction. */
3650 if (GROUP_FIRST_ELEMENT (stmt_info
) && !STMT_VINFO_GROUPED_ACCESS (stmt_info
)
3651 && GROUP_FIRST_ELEMENT (stmt_info
) == stmt
)
3653 STMT_VINFO_DEF_TYPE (stmt_info
) = vect_reduction_def
;
3654 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
3657 /* Handle two-operation SLP nodes by vectorizing the group with
3658 both operations and then performing a merge. */
3659 if (SLP_TREE_TWO_OPERATORS (node
))
3661 enum tree_code code0
= gimple_assign_rhs_code (stmt
);
3662 enum tree_code ocode
= ERROR_MARK
;
3664 unsigned char *mask
= XALLOCAVEC (unsigned char, group_size
);
3665 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, ostmt
)
3666 if (gimple_assign_rhs_code (ostmt
) != code0
)
3669 ocode
= gimple_assign_rhs_code (ostmt
);
3673 if (ocode
!= ERROR_MARK
)
3678 tree tmask
= NULL_TREE
;
3679 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3680 v0
= SLP_TREE_VEC_STMTS (node
).copy ();
3681 SLP_TREE_VEC_STMTS (node
).truncate (0);
3682 gimple_assign_set_rhs_code (stmt
, ocode
);
3683 vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3684 gimple_assign_set_rhs_code (stmt
, code0
);
3685 v1
= SLP_TREE_VEC_STMTS (node
).copy ();
3686 SLP_TREE_VEC_STMTS (node
).truncate (0);
3687 tree meltype
= build_nonstandard_integer_type
3688 (GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (vectype
))), 1);
3689 tree mvectype
= get_same_sized_vectype (meltype
, vectype
);
3691 for (j
= 0; j
< v0
.length (); ++j
)
3693 tree
*melts
= XALLOCAVEC (tree
, TYPE_VECTOR_SUBPARTS (vectype
));
3694 for (l
= 0; l
< TYPE_VECTOR_SUBPARTS (vectype
); ++l
)
3696 if (k
>= group_size
)
3698 melts
[l
] = build_int_cst
3699 (meltype
, mask
[k
++] * TYPE_VECTOR_SUBPARTS (vectype
) + l
);
3701 tmask
= build_vector (mvectype
, melts
);
3703 /* ??? Not all targets support a VEC_PERM_EXPR with a
3704 constant mask that would translate to a vec_merge RTX
3705 (with their vec_perm_const_ok). We can either not
3706 vectorize in that case or let veclower do its job.
3707 Unfortunately that isn't too great and at least for
3708 plus/minus we'd eventually like to match targets
3709 vector addsub instructions. */
3711 vstmt
= gimple_build_assign (make_ssa_name (vectype
),
3713 gimple_assign_lhs (v0
[j
]),
3714 gimple_assign_lhs (v1
[j
]), tmask
);
3715 vect_finish_stmt_generation (stmt
, vstmt
, &si
);
3716 SLP_TREE_VEC_STMTS (node
).quick_push (vstmt
);
3723 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, node
, instance
);
3725 /* Restore stmt def-types. */
3726 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3727 if (SLP_TREE_DEF_TYPE (child
) != vect_internal_def
)
3728 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child
), j
, stmt
)
3729 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) = vect_internal_def
;
3734 /* Replace scalar calls from SLP node NODE with setting of their lhs to zero.
3735 For loop vectorization this is done in vectorizable_call, but for SLP
3736 it needs to be deferred until end of vect_schedule_slp, because multiple
3737 SLP instances may refer to the same scalar stmt. */
3740 vect_remove_slp_scalar_calls (slp_tree node
)
3742 gimple
*stmt
, *new_stmt
;
3743 gimple_stmt_iterator gsi
;
3747 stmt_vec_info stmt_info
;
3749 if (SLP_TREE_DEF_TYPE (node
) != vect_internal_def
)
3752 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node
), i
, child
)
3753 vect_remove_slp_scalar_calls (child
);
3755 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node
), i
, stmt
)
3757 if (!is_gimple_call (stmt
) || gimple_bb (stmt
) == NULL
)
3759 stmt_info
= vinfo_for_stmt (stmt
);
3760 if (stmt_info
== NULL
3761 || is_pattern_stmt_p (stmt_info
)
3762 || !PURE_SLP_STMT (stmt_info
))
3764 lhs
= gimple_call_lhs (stmt
);
3765 new_stmt
= gimple_build_assign (lhs
, build_zero_cst (TREE_TYPE (lhs
)));
3766 set_vinfo_for_stmt (new_stmt
, stmt_info
);
3767 set_vinfo_for_stmt (stmt
, NULL
);
3768 STMT_VINFO_STMT (stmt_info
) = new_stmt
;
3769 gsi
= gsi_for_stmt (stmt
);
3770 gsi_replace (&gsi
, new_stmt
, false);
3771 SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt
)) = new_stmt
;
3775 /* Generate vector code for all SLP instances in the loop/basic block. */
3778 vect_schedule_slp (vec_info
*vinfo
)
3780 vec
<slp_instance
> slp_instances
;
3781 slp_instance instance
;
3783 bool is_store
= false;
3785 slp_instances
= vinfo
->slp_instances
;
3786 if (is_a
<loop_vec_info
> (vinfo
))
3787 vf
= as_a
<loop_vec_info
> (vinfo
)->vectorization_factor
;
3791 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3793 /* Schedule the tree of INSTANCE. */
3794 is_store
= vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance
),
3796 if (dump_enabled_p ())
3797 dump_printf_loc (MSG_NOTE
, vect_location
,
3798 "vectorizing stmts using SLP.\n");
3801 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
3803 slp_tree root
= SLP_INSTANCE_TREE (instance
);
3806 gimple_stmt_iterator gsi
;
3808 /* Remove scalar call stmts. Do not do this for basic-block
3809 vectorization as not all uses may be vectorized.
3810 ??? Why should this be necessary? DCE should be able to
3811 remove the stmts itself.
3812 ??? For BB vectorization we can as well remove scalar
3813 stmts starting from the SLP tree root if they have no
3815 if (is_a
<loop_vec_info
> (vinfo
))
3816 vect_remove_slp_scalar_calls (root
);
3818 for (j
= 0; SLP_TREE_SCALAR_STMTS (root
).iterate (j
, &store
)
3819 && j
< SLP_INSTANCE_GROUP_SIZE (instance
); j
++)
3821 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store
)))
3824 if (is_pattern_stmt_p (vinfo_for_stmt (store
)))
3825 store
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (store
));
3826 /* Free the attached stmt_vec_info and remove the stmt. */
3827 gsi
= gsi_for_stmt (store
);
3828 unlink_stmt_vdef (store
);
3829 gsi_remove (&gsi
, true);
3830 release_defs (store
);
3831 free_stmt_vec_info (store
);