1 /* SLP - Basic Block Vectorization
2 Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
4 Contributed by Dorit Naishlos <dorit@il.ibm.com>
5 and Ira Rosen <irar@il.ibm.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
30 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
35 #include "cfglayout.h"
39 #include "tree-vectorizer.h"
41 /* Extract the location of the basic block in the source code.
42 Return the basic block location if succeed and NULL if not. */
45 find_bb_location (basic_block bb)
48 gimple_stmt_iterator si;
53 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
56 if (gimple_location (stmt) != UNKNOWN_LOC)
57 return gimple_location (stmt);
64 /* Recursively free the memory allocated for the SLP tree rooted at NODE. */
67 vect_free_slp_tree (slp_tree node)
72 if (SLP_TREE_LEFT (node))
73 vect_free_slp_tree (SLP_TREE_LEFT (node));
75 if (SLP_TREE_RIGHT (node))
76 vect_free_slp_tree (SLP_TREE_RIGHT (node));
78 VEC_free (gimple, heap, SLP_TREE_SCALAR_STMTS (node));
80 if (SLP_TREE_VEC_STMTS (node))
81 VEC_free (gimple, heap, SLP_TREE_VEC_STMTS (node));
87 /* Free the memory allocated for the SLP instance. */
90 vect_free_slp_instance (slp_instance instance)
92 vect_free_slp_tree (SLP_INSTANCE_TREE (instance));
93 VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (instance));
94 VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (instance));
98 /* Get the defs for the rhs of STMT (collect them in DEF_STMTS0/1), check that
99 they are of a legal type and that they match the defs of the first stmt of
100 the SLP group (stored in FIRST_STMT_...). */
103 vect_get_and_check_slp_defs (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
104 slp_tree slp_node, gimple stmt,
105 VEC (gimple, heap) **def_stmts0,
106 VEC (gimple, heap) **def_stmts1,
107 enum vect_def_type *first_stmt_dt0,
108 enum vect_def_type *first_stmt_dt1,
109 tree *first_stmt_def0_type,
110 tree *first_stmt_def1_type,
111 tree *first_stmt_const_oprnd,
112 int ncopies_for_cost,
113 bool *pattern0, bool *pattern1)
116 unsigned int i, number_of_oprnds;
119 enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
120 stmt_vec_info stmt_info =
121 vinfo_for_stmt (VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0));
122 enum gimple_rhs_class rhs_class;
123 struct loop *loop = NULL;
126 loop = LOOP_VINFO_LOOP (loop_vinfo);
128 rhs_class = get_gimple_rhs_class (gimple_assign_rhs_code (stmt));
129 number_of_oprnds = gimple_num_ops (stmt) - 1; /* RHS only */
131 for (i = 0; i < number_of_oprnds; i++)
133 oprnd = gimple_op (stmt, i + 1);
135 if (!vect_is_simple_use (oprnd, loop_vinfo, bb_vinfo, &def_stmt, &def,
137 || (!def_stmt && dt[i] != vect_constant_def))
139 if (vect_print_dump_info (REPORT_SLP))
141 fprintf (vect_dump, "Build SLP failed: can't find def for ");
142 print_generic_expr (vect_dump, oprnd, TDF_SLIM);
148 /* Check if DEF_STMT is a part of a pattern in LOOP and get the def stmt
149 from the pattern. Check that all the stmts of the node are in the
151 if (loop && def_stmt && gimple_bb (def_stmt)
152 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
153 && vinfo_for_stmt (def_stmt)
154 && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (def_stmt)))
156 if (!*first_stmt_dt0)
160 if (i == 1 && !*first_stmt_dt1)
162 else if ((i == 0 && !*pattern0) || (i == 1 && !*pattern1))
164 if (vect_print_dump_info (REPORT_DETAILS))
166 fprintf (vect_dump, "Build SLP failed: some of the stmts"
167 " are in a pattern, and others are not ");
168 print_generic_expr (vect_dump, oprnd, TDF_SLIM);
175 def_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
176 dt[i] = STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt));
178 if (*dt == vect_unknown_def_type)
180 if (vect_print_dump_info (REPORT_DETAILS))
181 fprintf (vect_dump, "Unsupported pattern.");
185 switch (gimple_code (def_stmt))
188 def = gimple_phi_result (def_stmt);
192 def = gimple_assign_lhs (def_stmt);
196 if (vect_print_dump_info (REPORT_DETAILS))
197 fprintf (vect_dump, "unsupported defining stmt: ");
202 if (!*first_stmt_dt0)
204 /* op0 of the first stmt of the group - store its info. */
205 *first_stmt_dt0 = dt[i];
207 *first_stmt_def0_type = TREE_TYPE (def);
209 *first_stmt_const_oprnd = oprnd;
211 /* Analyze costs (for the first stmt of the group only). */
212 if (rhs_class != GIMPLE_SINGLE_RHS)
213 /* Not memory operation (we don't call this functions for loads). */
214 vect_model_simple_cost (stmt_info, ncopies_for_cost, dt, slp_node);
217 vect_model_store_cost (stmt_info, ncopies_for_cost, dt[0], slp_node);
222 if (!*first_stmt_dt1 && i == 1)
224 /* op1 of the first stmt of the group - store its info. */
225 *first_stmt_dt1 = dt[i];
227 *first_stmt_def1_type = TREE_TYPE (def);
230 /* We assume that the stmt contains only one constant
231 operand. We fail otherwise, to be on the safe side. */
232 if (*first_stmt_const_oprnd)
234 if (vect_print_dump_info (REPORT_SLP))
235 fprintf (vect_dump, "Build SLP failed: two constant "
239 *first_stmt_const_oprnd = oprnd;
244 /* Not first stmt of the group, check that the def-stmt/s match
245 the def-stmt/s of the first stmt. */
247 && (*first_stmt_dt0 != dt[i]
248 || (*first_stmt_def0_type && def
249 && *first_stmt_def0_type != TREE_TYPE (def))))
251 && (*first_stmt_dt1 != dt[i]
252 || (*first_stmt_def1_type && def
253 && *first_stmt_def1_type != TREE_TYPE (def))))
255 && TREE_TYPE (*first_stmt_const_oprnd)
256 != TREE_TYPE (oprnd)))
258 if (vect_print_dump_info (REPORT_SLP))
259 fprintf (vect_dump, "Build SLP failed: different types ");
266 /* Check the types of the definitions. */
269 case vect_constant_def:
270 case vect_external_def:
273 case vect_internal_def:
275 VEC_safe_push (gimple, heap, *def_stmts0, def_stmt);
277 VEC_safe_push (gimple, heap, *def_stmts1, def_stmt);
281 /* FORNOW: Not supported. */
282 if (vect_print_dump_info (REPORT_SLP))
284 fprintf (vect_dump, "Build SLP failed: illegal type of def ");
285 print_generic_expr (vect_dump, def, TDF_SLIM);
296 /* Recursively build an SLP tree starting from NODE.
297 Fail (and return FALSE) if def-stmts are not isomorphic, require data
298 permutation or are of unsupported types of operation. Otherwise, return
302 vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
303 slp_tree *node, unsigned int group_size,
304 int *inside_cost, int *outside_cost,
305 int ncopies_for_cost, unsigned int *max_nunits,
306 VEC (int, heap) **load_permutation,
307 VEC (slp_tree, heap) **loads,
308 unsigned int vectorization_factor)
310 VEC (gimple, heap) *def_stmts0 = VEC_alloc (gimple, heap, group_size);
311 VEC (gimple, heap) *def_stmts1 = VEC_alloc (gimple, heap, group_size);
313 VEC (gimple, heap) *stmts = SLP_TREE_SCALAR_STMTS (*node);
314 gimple stmt = VEC_index (gimple, stmts, 0);
315 enum vect_def_type first_stmt_dt0 = vect_uninitialized_def;
316 enum vect_def_type first_stmt_dt1 = vect_uninitialized_def;
317 enum tree_code first_stmt_code = ERROR_MARK, rhs_code;
318 tree first_stmt_def1_type = NULL_TREE, first_stmt_def0_type = NULL_TREE;
320 bool stop_recursion = false, need_same_oprnds = false;
321 tree vectype, scalar_type, first_op1 = NULL_TREE;
322 unsigned int ncopies;
325 enum machine_mode optab_op2_mode;
326 enum machine_mode vec_mode;
327 tree first_stmt_const_oprnd = NULL_TREE;
328 struct data_reference *first_dr;
329 bool pattern0 = false, pattern1 = false;
331 bool permutation = false;
332 unsigned int load_place;
335 /* For every stmt in NODE find its def stmt/s. */
336 for (i = 0; VEC_iterate (gimple, stmts, i, stmt); i++)
338 if (vect_print_dump_info (REPORT_SLP))
340 fprintf (vect_dump, "Build SLP for ");
341 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
344 lhs = gimple_get_lhs (stmt);
345 if (lhs == NULL_TREE)
347 if (vect_print_dump_info (REPORT_SLP))
350 "Build SLP failed: not GIMPLE_ASSIGN nor GIMPLE_CALL");
351 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
357 scalar_type = vect_get_smallest_scalar_type (stmt, &dummy, &dummy);
358 vectype = get_vectype_for_scalar_type (scalar_type);
361 if (vect_print_dump_info (REPORT_SLP))
363 fprintf (vect_dump, "Build SLP failed: unsupported data-type ");
364 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
369 ncopies = vectorization_factor / TYPE_VECTOR_SUBPARTS (vectype);
372 if (vect_print_dump_info (REPORT_SLP))
373 fprintf (vect_dump, "SLP with multiple types ");
375 /* FORNOW: multiple types are unsupported in BB SLP. */
380 /* In case of multiple types we need to detect the smallest type. */
381 if (*max_nunits < TYPE_VECTOR_SUBPARTS (vectype))
382 *max_nunits = TYPE_VECTOR_SUBPARTS (vectype);
384 if (is_gimple_call (stmt))
385 rhs_code = CALL_EXPR;
387 rhs_code = gimple_assign_rhs_code (stmt);
389 /* Check the operation. */
392 first_stmt_code = rhs_code;
394 /* Shift arguments should be equal in all the packed stmts for a
395 vector shift with scalar shift operand. */
396 if (rhs_code == LSHIFT_EXPR || rhs_code == RSHIFT_EXPR
397 || rhs_code == LROTATE_EXPR
398 || rhs_code == RROTATE_EXPR)
400 vec_mode = TYPE_MODE (vectype);
402 /* First see if we have a vector/vector shift. */
403 optab = optab_for_tree_code (rhs_code, vectype,
407 || (optab->handlers[(int) vec_mode].insn_code
408 == CODE_FOR_nothing))
410 /* No vector/vector shift, try for a vector/scalar shift. */
411 optab = optab_for_tree_code (rhs_code, vectype,
416 if (vect_print_dump_info (REPORT_SLP))
417 fprintf (vect_dump, "Build SLP failed: no optab.");
420 icode = (int) optab->handlers[(int) vec_mode].insn_code;
421 if (icode == CODE_FOR_nothing)
423 if (vect_print_dump_info (REPORT_SLP))
424 fprintf (vect_dump, "Build SLP failed: "
425 "op not supported by target.");
428 optab_op2_mode = insn_data[icode].operand[2].mode;
429 if (!VECTOR_MODE_P (optab_op2_mode))
431 need_same_oprnds = true;
432 first_op1 = gimple_assign_rhs2 (stmt);
439 if (first_stmt_code != rhs_code
440 && (first_stmt_code != IMAGPART_EXPR
441 || rhs_code != REALPART_EXPR)
442 && (first_stmt_code != REALPART_EXPR
443 || rhs_code != IMAGPART_EXPR))
445 if (vect_print_dump_info (REPORT_SLP))
448 "Build SLP failed: different operation in stmt ");
449 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
456 && !operand_equal_p (first_op1, gimple_assign_rhs2 (stmt), 0))
458 if (vect_print_dump_info (REPORT_SLP))
461 "Build SLP failed: different shift arguments in ");
462 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
469 /* Strided store or load. */
470 if (STMT_VINFO_STRIDED_ACCESS (vinfo_for_stmt (stmt)))
472 if (REFERENCE_CLASS_P (lhs))
475 if (!vect_get_and_check_slp_defs (loop_vinfo, bb_vinfo, *node,
476 stmt, &def_stmts0, &def_stmts1,
479 &first_stmt_def0_type,
480 &first_stmt_def1_type,
481 &first_stmt_const_oprnd,
483 &pattern0, &pattern1))
489 /* FORNOW: Check that there is no gap between the loads. */
490 if ((DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) == stmt
491 && DR_GROUP_GAP (vinfo_for_stmt (stmt)) != 0)
492 || (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) != stmt
493 && DR_GROUP_GAP (vinfo_for_stmt (stmt)) != 1))
495 if (vect_print_dump_info (REPORT_SLP))
497 fprintf (vect_dump, "Build SLP failed: strided "
499 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
505 /* Check that the size of interleaved loads group is not
506 greater than the SLP group size. */
507 if (DR_GROUP_SIZE (vinfo_for_stmt (stmt))
508 > ncopies * group_size)
510 if (vect_print_dump_info (REPORT_SLP))
512 fprintf (vect_dump, "Build SLP failed: the number of "
513 "interleaved loads is greater than"
514 " the SLP group size ");
515 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
521 first_load = DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt));
523 if (first_load == stmt)
525 first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
526 if (vect_supportable_dr_alignment (first_dr)
527 == dr_unaligned_unsupported)
529 if (vect_print_dump_info (REPORT_SLP))
531 fprintf (vect_dump, "Build SLP failed: unsupported "
533 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
539 /* Analyze costs (for the first stmt in the group). */
540 vect_model_load_cost (vinfo_for_stmt (stmt),
541 ncopies_for_cost, *node);
544 /* Store the place of this load in the interleaving chain. In
545 case that permutation is needed we later decide if a specific
546 permutation is supported. */
547 load_place = vect_get_place_in_interleaving_chain (stmt,
552 VEC_safe_push (int, heap, *load_permutation, load_place);
554 /* We stop the tree when we reach a group of loads. */
555 stop_recursion = true;
558 } /* Strided access. */
561 if (TREE_CODE_CLASS (rhs_code) == tcc_reference)
563 /* Not strided load. */
564 if (vect_print_dump_info (REPORT_SLP))
566 fprintf (vect_dump, "Build SLP failed: not strided load ");
567 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
570 /* FORNOW: Not strided loads are not supported. */
574 /* Not memory operation. */
575 if (TREE_CODE_CLASS (rhs_code) != tcc_binary
576 && TREE_CODE_CLASS (rhs_code) != tcc_unary)
578 if (vect_print_dump_info (REPORT_SLP))
580 fprintf (vect_dump, "Build SLP failed: operation");
581 fprintf (vect_dump, " unsupported ");
582 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
588 /* Find the def-stmts. */
589 if (!vect_get_and_check_slp_defs (loop_vinfo, bb_vinfo, *node, stmt,
590 &def_stmts0, &def_stmts1,
591 &first_stmt_dt0, &first_stmt_dt1,
592 &first_stmt_def0_type,
593 &first_stmt_def1_type,
594 &first_stmt_const_oprnd,
596 &pattern0, &pattern1))
601 /* Add the costs of the node to the overall instance costs. */
602 *inside_cost += SLP_TREE_INSIDE_OF_LOOP_COST (*node);
603 *outside_cost += SLP_TREE_OUTSIDE_OF_LOOP_COST (*node);
605 /* Strided loads were reached - stop the recursion. */
610 VEC_safe_push (slp_tree, heap, *loads, *node);
611 *inside_cost += TARG_VEC_PERMUTE_COST * group_size;
617 /* Create SLP_TREE nodes for the definition node/s. */
618 if (first_stmt_dt0 == vect_internal_def)
620 slp_tree left_node = XNEW (struct _slp_tree);
621 SLP_TREE_SCALAR_STMTS (left_node) = def_stmts0;
622 SLP_TREE_VEC_STMTS (left_node) = NULL;
623 SLP_TREE_LEFT (left_node) = NULL;
624 SLP_TREE_RIGHT (left_node) = NULL;
625 SLP_TREE_OUTSIDE_OF_LOOP_COST (left_node) = 0;
626 SLP_TREE_INSIDE_OF_LOOP_COST (left_node) = 0;
627 if (!vect_build_slp_tree (loop_vinfo, bb_vinfo, &left_node, group_size,
628 inside_cost, outside_cost, ncopies_for_cost,
629 max_nunits, load_permutation, loads,
630 vectorization_factor))
633 SLP_TREE_LEFT (*node) = left_node;
636 if (first_stmt_dt1 == vect_internal_def)
638 slp_tree right_node = XNEW (struct _slp_tree);
639 SLP_TREE_SCALAR_STMTS (right_node) = def_stmts1;
640 SLP_TREE_VEC_STMTS (right_node) = NULL;
641 SLP_TREE_LEFT (right_node) = NULL;
642 SLP_TREE_RIGHT (right_node) = NULL;
643 SLP_TREE_OUTSIDE_OF_LOOP_COST (right_node) = 0;
644 SLP_TREE_INSIDE_OF_LOOP_COST (right_node) = 0;
645 if (!vect_build_slp_tree (loop_vinfo, bb_vinfo, &right_node, group_size,
646 inside_cost, outside_cost, ncopies_for_cost,
647 max_nunits, load_permutation, loads,
648 vectorization_factor))
651 SLP_TREE_RIGHT (*node) = right_node;
659 vect_print_slp_tree (slp_tree node)
667 fprintf (vect_dump, "node ");
668 for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
670 fprintf (vect_dump, "\n\tstmt %d ", i);
671 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
673 fprintf (vect_dump, "\n");
675 vect_print_slp_tree (SLP_TREE_LEFT (node));
676 vect_print_slp_tree (SLP_TREE_RIGHT (node));
680 /* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
681 If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
682 J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
683 stmts in NODE are to be marked. */
686 vect_mark_slp_stmts (slp_tree node, enum slp_vect_type mark, int j)
694 for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
696 STMT_SLP_TYPE (vinfo_for_stmt (stmt)) = mark;
698 vect_mark_slp_stmts (SLP_TREE_LEFT (node), mark, j);
699 vect_mark_slp_stmts (SLP_TREE_RIGHT (node), mark, j);
703 /* Mark the statements of the tree rooted at NODE as relevant (vect_used). */
706 vect_mark_slp_stmts_relevant (slp_tree node)
710 stmt_vec_info stmt_info;
715 for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
717 stmt_info = vinfo_for_stmt (stmt);
718 gcc_assert (!STMT_VINFO_RELEVANT (stmt_info)
719 || STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_scope);
720 STMT_VINFO_RELEVANT (stmt_info) = vect_used_in_scope;
723 vect_mark_slp_stmts_relevant (SLP_TREE_LEFT (node));
724 vect_mark_slp_stmts_relevant (SLP_TREE_RIGHT (node));
728 /* Check if the permutation required by the SLP INSTANCE is supported.
729 Reorganize the SLP nodes stored in SLP_INSTANCE_LOADS if needed. */
732 vect_supported_slp_permutation_p (slp_instance instance)
734 slp_tree node = VEC_index (slp_tree, SLP_INSTANCE_LOADS (instance), 0);
735 gimple stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
736 gimple first_load = DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt));
737 VEC (slp_tree, heap) *sorted_loads = NULL;
739 slp_tree *tmp_loads = NULL;
740 int group_size = SLP_INSTANCE_GROUP_SIZE (instance), i, j;
743 /* FORNOW: The only supported loads permutation is loads from the same
744 location in all the loads in the node, when the data-refs in
745 nodes of LOADS constitute an interleaving chain.
746 Sort the nodes according to the order of accesses in the chain. */
747 tmp_loads = (slp_tree *) xmalloc (sizeof (slp_tree) * group_size);
749 VEC_iterate (int, SLP_INSTANCE_LOAD_PERMUTATION (instance), i, index)
750 && VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), j, load);
751 i += group_size, j++)
753 gimple scalar_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (load), 0);
754 /* Check that the loads are all in the same interleaving chain. */
755 if (DR_GROUP_FIRST_DR (vinfo_for_stmt (scalar_stmt)) != first_load)
757 if (vect_print_dump_info (REPORT_DETAILS))
759 fprintf (vect_dump, "Build SLP failed: unsupported data "
761 print_gimple_stmt (vect_dump, scalar_stmt, 0, TDF_SLIM);
768 tmp_loads[index] = load;
771 sorted_loads = VEC_alloc (slp_tree, heap, group_size);
772 for (i = 0; i < group_size; i++)
773 VEC_safe_push (slp_tree, heap, sorted_loads, tmp_loads[i]);
775 VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (instance));
776 SLP_INSTANCE_LOADS (instance) = sorted_loads;
779 if (!vect_transform_slp_perm_load (stmt, NULL, NULL,
780 SLP_INSTANCE_UNROLLING_FACTOR (instance),
788 /* Check if the required load permutation is supported.
789 LOAD_PERMUTATION contains a list of indices of the loads.
790 In SLP this permutation is relative to the order of strided stores that are
791 the base of the SLP instance. */
794 vect_supported_load_permutation_p (slp_instance slp_instn, int group_size,
795 VEC (int, heap) *load_permutation)
797 int i = 0, j, prev = -1, next, k;
801 /* FORNOW: permutations are only supported in SLP. */
805 if (vect_print_dump_info (REPORT_SLP))
807 fprintf (vect_dump, "Load permutation ");
808 for (i = 0; VEC_iterate (int, load_permutation, i, next); i++)
809 fprintf (vect_dump, "%d ", next);
812 /* FORNOW: the only supported permutation is 0..01..1.. of length equal to
813 GROUP_SIZE and where each sequence of same drs is of GROUP_SIZE length as
815 if (VEC_length (int, load_permutation)
816 != (unsigned int) (group_size * group_size))
820 load_index = sbitmap_alloc (group_size);
821 sbitmap_zero (load_index);
822 for (j = 0; j < group_size; j++)
824 for (i = j * group_size, k = 0;
825 VEC_iterate (int, load_permutation, i, next) && k < group_size;
828 if (i != j * group_size && next != prev)
837 if (TEST_BIT (load_index, prev))
843 SET_BIT (load_index, prev);
846 sbitmap_free (load_index);
848 if (supported && i == group_size * group_size
849 && vect_supported_slp_permutation_p (slp_instn))
856 /* Find the first load in the loop that belongs to INSTANCE.
857 When loads are in several SLP nodes, there can be a case in which the first
858 load does not appear in the first SLP node to be transformed, causing
859 incorrect order of statements. Since we generate all the loads together,
860 they must be inserted before the first load of the SLP instance and not
861 before the first load of the first node of the instance. */
863 vect_find_first_load_in_slp_instance (slp_instance instance)
867 gimple first_load = NULL, load;
870 VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), i, load_node);
873 VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (load_node), j, load);
875 first_load = get_earlier_stmt (load, first_load);
881 /* Analyze an SLP instance starting from a group of strided stores. Call
882 vect_build_slp_tree to build a tree of packed stmts if possible.
883 Return FALSE if it's impossible to SLP any stmt in the loop. */
886 vect_analyze_slp_instance (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
889 slp_instance new_instance;
890 slp_tree node = XNEW (struct _slp_tree);
891 unsigned int group_size = DR_GROUP_SIZE (vinfo_for_stmt (stmt));
892 unsigned int unrolling_factor = 1, nunits;
893 tree vectype, scalar_type;
895 unsigned int vectorization_factor = 0;
896 int inside_cost = 0, outside_cost = 0, ncopies_for_cost;
897 unsigned int max_nunits = 0;
898 VEC (int, heap) *load_permutation;
899 VEC (slp_tree, heap) *loads;
901 scalar_type = TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (
902 vinfo_for_stmt (stmt))));
903 vectype = get_vectype_for_scalar_type (scalar_type);
906 if (vect_print_dump_info (REPORT_SLP))
908 fprintf (vect_dump, "Build SLP failed: unsupported data-type ");
909 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
914 nunits = TYPE_VECTOR_SUBPARTS (vectype);
916 vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
918 /* No multitypes in BB SLP. */
919 vectorization_factor = nunits;
921 /* Calculate the unrolling factor. */
922 unrolling_factor = least_common_multiple (nunits, group_size) / group_size;
923 if (unrolling_factor != 1 && !loop_vinfo)
925 if (vect_print_dump_info (REPORT_SLP))
926 fprintf (vect_dump, "Build SLP failed: unrolling required in basic"
932 /* Create a node (a root of the SLP tree) for the packed strided stores. */
933 SLP_TREE_SCALAR_STMTS (node) = VEC_alloc (gimple, heap, group_size);
935 /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
938 VEC_safe_push (gimple, heap, SLP_TREE_SCALAR_STMTS (node), next);
939 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
942 SLP_TREE_VEC_STMTS (node) = NULL;
943 SLP_TREE_NUMBER_OF_VEC_STMTS (node) = 0;
944 SLP_TREE_LEFT (node) = NULL;
945 SLP_TREE_RIGHT (node) = NULL;
946 SLP_TREE_OUTSIDE_OF_LOOP_COST (node) = 0;
947 SLP_TREE_INSIDE_OF_LOOP_COST (node) = 0;
949 /* Calculate the number of vector stmts to create based on the unrolling
950 factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
951 GROUP_SIZE / NUNITS otherwise. */
952 ncopies_for_cost = unrolling_factor * group_size / nunits;
954 load_permutation = VEC_alloc (int, heap, group_size * group_size);
955 loads = VEC_alloc (slp_tree, heap, group_size);
957 /* Build the tree for the SLP instance. */
958 if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &node, group_size,
959 &inside_cost, &outside_cost, ncopies_for_cost,
960 &max_nunits, &load_permutation, &loads,
961 vectorization_factor))
963 /* Create a new SLP instance. */
964 new_instance = XNEW (struct _slp_instance);
965 SLP_INSTANCE_TREE (new_instance) = node;
966 SLP_INSTANCE_GROUP_SIZE (new_instance) = group_size;
967 /* Calculate the unrolling factor based on the smallest type in the
969 if (max_nunits > nunits)
970 unrolling_factor = least_common_multiple (max_nunits, group_size)
973 SLP_INSTANCE_UNROLLING_FACTOR (new_instance) = unrolling_factor;
974 SLP_INSTANCE_OUTSIDE_OF_LOOP_COST (new_instance) = outside_cost;
975 SLP_INSTANCE_INSIDE_OF_LOOP_COST (new_instance) = inside_cost;
976 SLP_INSTANCE_LOADS (new_instance) = loads;
977 SLP_INSTANCE_FIRST_LOAD_STMT (new_instance) = NULL;
978 SLP_INSTANCE_LOAD_PERMUTATION (new_instance) = load_permutation;
979 if (VEC_length (slp_tree, loads))
981 if (!vect_supported_load_permutation_p (new_instance, group_size,
984 if (vect_print_dump_info (REPORT_SLP))
986 fprintf (vect_dump, "Build SLP failed: unsupported load "
988 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
991 vect_free_slp_instance (new_instance);
995 SLP_INSTANCE_FIRST_LOAD_STMT (new_instance)
996 = vect_find_first_load_in_slp_instance (new_instance);
999 VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (new_instance));
1002 VEC_safe_push (slp_instance, heap,
1003 LOOP_VINFO_SLP_INSTANCES (loop_vinfo),
1006 VEC_safe_push (slp_instance, heap, BB_VINFO_SLP_INSTANCES (bb_vinfo),
1009 if (vect_print_dump_info (REPORT_SLP))
1010 vect_print_slp_tree (node);
1015 /* Failed to SLP. */
1016 /* Free the allocated memory. */
1017 vect_free_slp_tree (node);
1018 VEC_free (int, heap, load_permutation);
1019 VEC_free (slp_tree, heap, loads);
1025 /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
1026 trees of packed scalar stmts if SLP is possible. */
1029 vect_analyze_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
1032 VEC (gimple, heap) *strided_stores;
1036 if (vect_print_dump_info (REPORT_SLP))
1037 fprintf (vect_dump, "=== vect_analyze_slp ===");
1040 strided_stores = LOOP_VINFO_STRIDED_STORES (loop_vinfo);
1042 strided_stores = BB_VINFO_STRIDED_STORES (bb_vinfo);
1044 for (i = 0; VEC_iterate (gimple, strided_stores, i, store); i++)
1045 if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, store))
1048 if (bb_vinfo && !ok)
1050 if (vect_print_dump_info (REPORT_SLP))
1051 fprintf (vect_dump, "Failed to SLP the basic block.");
1060 /* For each possible SLP instance decide whether to SLP it and calculate overall
1061 unrolling factor needed to SLP the loop. */
1064 vect_make_slp_decision (loop_vec_info loop_vinfo)
1066 unsigned int i, unrolling_factor = 1;
1067 VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
1068 slp_instance instance;
1069 int decided_to_slp = 0;
1071 if (vect_print_dump_info (REPORT_SLP))
1072 fprintf (vect_dump, "=== vect_make_slp_decision ===");
1074 for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
1076 /* FORNOW: SLP if you can. */
1077 if (unrolling_factor < SLP_INSTANCE_UNROLLING_FACTOR (instance))
1078 unrolling_factor = SLP_INSTANCE_UNROLLING_FACTOR (instance);
1080 /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
1081 call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
1082 loop-based vectorization. Such stmts will be marked as HYBRID. */
1083 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
1087 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo) = unrolling_factor;
1089 if (decided_to_slp && vect_print_dump_info (REPORT_SLP))
1090 fprintf (vect_dump, "Decided to SLP %d instances. Unrolling factor %d",
1091 decided_to_slp, unrolling_factor);
1095 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
1096 can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
1099 vect_detect_hybrid_slp_stmts (slp_tree node)
1103 imm_use_iterator imm_iter;
1105 stmt_vec_info stmt_vinfo;
1110 for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
1111 if (PURE_SLP_STMT (vinfo_for_stmt (stmt))
1112 && TREE_CODE (gimple_op (stmt, 0)) == SSA_NAME)
1113 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, gimple_op (stmt, 0))
1114 if ((stmt_vinfo = vinfo_for_stmt (use_stmt))
1115 && !STMT_SLP_TYPE (stmt_vinfo)
1116 && (STMT_VINFO_RELEVANT (stmt_vinfo)
1117 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_vinfo))))
1118 vect_mark_slp_stmts (node, hybrid, i);
1120 vect_detect_hybrid_slp_stmts (SLP_TREE_LEFT (node));
1121 vect_detect_hybrid_slp_stmts (SLP_TREE_RIGHT (node));
1125 /* Find stmts that must be both vectorized and SLPed. */
1128 vect_detect_hybrid_slp (loop_vec_info loop_vinfo)
1131 VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
1132 slp_instance instance;
1134 if (vect_print_dump_info (REPORT_SLP))
1135 fprintf (vect_dump, "=== vect_detect_hybrid_slp ===");
1137 for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
1138 vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance));
1142 /* Create and initialize a new bb_vec_info struct for BB, as well as
1143 stmt_vec_info structs for all the stmts in it. */
1146 new_bb_vec_info (basic_block bb)
1148 bb_vec_info res = NULL;
1149 gimple_stmt_iterator gsi;
1151 res = (bb_vec_info) xcalloc (1, sizeof (struct _bb_vec_info));
1152 BB_VINFO_BB (res) = bb;
1154 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1156 gimple stmt = gsi_stmt (gsi);
1157 gimple_set_uid (stmt, 0);
1158 set_vinfo_for_stmt (stmt, new_stmt_vec_info (stmt, NULL, res));
1161 BB_VINFO_STRIDED_STORES (res) = VEC_alloc (gimple, heap, 10);
1162 BB_VINFO_SLP_INSTANCES (res) = VEC_alloc (slp_instance, heap, 2);
1169 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
1170 stmts in the basic block. */
1173 destroy_bb_vec_info (bb_vec_info bb_vinfo)
1176 gimple_stmt_iterator si;
1181 bb = BB_VINFO_BB (bb_vinfo);
1183 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1185 gimple stmt = gsi_stmt (si);
1186 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1189 /* Free stmt_vec_info. */
1190 free_stmt_vec_info (stmt);
1193 VEC_free (gimple, heap, BB_VINFO_STRIDED_STORES (bb_vinfo));
1194 VEC_free (slp_instance, heap, BB_VINFO_SLP_INSTANCES (bb_vinfo));
1200 /* Analyze statements contained in SLP tree node after recursively analyzing
1201 the subtree. Return TRUE if the operations are supported. */
1204 vect_slp_analyze_node_operations (bb_vec_info bb_vinfo, slp_tree node)
1213 if (!vect_slp_analyze_node_operations (bb_vinfo, SLP_TREE_LEFT (node))
1214 || !vect_slp_analyze_node_operations (bb_vinfo, SLP_TREE_RIGHT (node)))
1217 for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
1219 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1220 gcc_assert (stmt_info);
1221 gcc_assert (PURE_SLP_STMT (stmt_info));
1223 if (!vect_analyze_stmt (stmt, &dummy, node))
1231 /* Analyze statements in SLP instances of the basic block. Return TRUE if the
1232 operations are supported. */
1235 vect_slp_analyze_operations (bb_vec_info bb_vinfo)
1237 VEC (slp_instance, heap) *slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
1238 slp_instance instance;
1241 for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); )
1243 if (!vect_slp_analyze_node_operations (bb_vinfo,
1244 SLP_INSTANCE_TREE (instance)))
1246 vect_free_slp_instance (instance);
1247 VEC_ordered_remove (slp_instance, slp_instances, i);
1253 if (!VEC_length (slp_instance, slp_instances))
1260 /* Cheick if the basic block can be vectorized. */
1263 vect_slp_analyze_bb (basic_block bb)
1265 bb_vec_info bb_vinfo;
1266 VEC (ddr_p, heap) *ddrs;
1267 VEC (slp_instance, heap) *slp_instances;
1268 slp_instance instance;
1270 gimple_stmt_iterator gsi;
1272 if (vect_print_dump_info (REPORT_DETAILS))
1273 fprintf (vect_dump, "===vect_slp_analyze_bb===\n");
1275 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1277 gimple stmt = gsi_stmt (gsi);
1278 if (!is_gimple_debug (stmt)
1279 && !gimple_nop_p (stmt)
1280 && !gimple_code (stmt) == GIMPLE_LABEL)
1284 if (insns > PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB))
1286 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1287 fprintf (vect_dump, "not vectorized: too many instructions in basic "
1293 bb_vinfo = new_bb_vec_info (bb);
1297 if (!vect_analyze_data_refs (NULL, bb_vinfo))
1299 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1300 fprintf (vect_dump, "not vectorized: unhandled data-ref in basic "
1303 destroy_bb_vec_info (bb_vinfo);
1307 ddrs = BB_VINFO_DDRS (bb_vinfo);
1308 if (!VEC_length (ddr_p, ddrs))
1310 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1311 fprintf (vect_dump, "not vectorized: not enough data-refs in basic "
1314 destroy_bb_vec_info (bb_vinfo);
1318 if (!vect_analyze_data_refs_alignment (NULL, bb_vinfo))
1320 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1321 fprintf (vect_dump, "not vectorized: bad data alignment in basic "
1324 destroy_bb_vec_info (bb_vinfo);
1328 if (!vect_analyze_data_ref_dependences (NULL, bb_vinfo))
1330 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1331 fprintf (vect_dump, "not vectorized: unhandled data dependence in basic"
1334 destroy_bb_vec_info (bb_vinfo);
1338 if (!vect_analyze_data_ref_accesses (NULL, bb_vinfo))
1340 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1341 fprintf (vect_dump, "not vectorized: unhandled data access in basic "
1344 destroy_bb_vec_info (bb_vinfo);
1348 if (!vect_verify_datarefs_alignment (NULL, bb_vinfo))
1350 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1351 fprintf (vect_dump, "not vectorized: unsupported alignment in basic "
1354 destroy_bb_vec_info (bb_vinfo);
1358 /* Check the SLP opportunities in the basic block, analyze and build SLP
1360 if (!vect_analyze_slp (NULL, bb_vinfo))
1362 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1363 fprintf (vect_dump, "not vectorized: failed to find SLP opportunities "
1364 "in basic block.\n");
1366 destroy_bb_vec_info (bb_vinfo);
1370 slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
1372 /* Mark all the statements that we want to vectorize as pure SLP and
1374 for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
1376 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
1377 vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance));
1380 if (!vect_slp_analyze_operations (bb_vinfo))
1382 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1383 fprintf (vect_dump, "not vectorized: bad operation in basic block.\n");
1385 destroy_bb_vec_info (bb_vinfo);
1389 if (vect_print_dump_info (REPORT_DETAILS))
1390 fprintf (vect_dump, "Basic block will be vectorized using SLP\n");
1396 /* SLP costs are calculated according to SLP instance unrolling factor (i.e.,
1397 the number of created vector stmts depends on the unrolling factor). However,
1398 the actual number of vector stmts for every SLP node depends on VF which is
1399 set later in vect_analyze_operations(). Hence, SLP costs should be updated.
1400 In this function we assume that the inside costs calculated in
1401 vect_model_xxx_cost are linear in ncopies. */
1404 vect_update_slp_costs_according_to_vf (loop_vec_info loop_vinfo)
1406 unsigned int i, vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1407 VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
1408 slp_instance instance;
1410 if (vect_print_dump_info (REPORT_SLP))
1411 fprintf (vect_dump, "=== vect_update_slp_costs_according_to_vf ===");
1413 for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
1414 /* We assume that costs are linear in ncopies. */
1415 SLP_INSTANCE_INSIDE_OF_LOOP_COST (instance) *= vf
1416 / SLP_INSTANCE_UNROLLING_FACTOR (instance);
1420 /* For constant and loop invariant defs of SLP_NODE this function returns
1421 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
1422 OP_NUM determines if we gather defs for operand 0 or operand 1 of the scalar
1423 stmts. NUMBER_OF_VECTORS is the number of vector defs to create. */
1426 vect_get_constant_vectors (slp_tree slp_node, VEC(tree,heap) **vec_oprnds,
1427 unsigned int op_num, unsigned int number_of_vectors)
1429 VEC (gimple, heap) *stmts = SLP_TREE_SCALAR_STMTS (slp_node);
1430 gimple stmt = VEC_index (gimple, stmts, 0);
1431 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
1435 int j, number_of_places_left_in_vector;
1438 int group_size = VEC_length (gimple, stmts);
1439 unsigned int vec_num, i;
1440 int number_of_copies = 1;
1441 VEC (tree, heap) *voprnds = VEC_alloc (tree, heap, number_of_vectors);
1442 bool constant_p, is_store;
1444 if (STMT_VINFO_DATA_REF (stmt_vinfo))
1447 op = gimple_assign_rhs1 (stmt);
1452 op = gimple_op (stmt, op_num + 1);
1455 if (CONSTANT_CLASS_P (op))
1460 vector_type = get_vectype_for_scalar_type (TREE_TYPE (op));
1461 gcc_assert (vector_type);
1463 nunits = TYPE_VECTOR_SUBPARTS (vector_type);
1465 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
1466 created vectors. It is greater than 1 if unrolling is performed.
1468 For example, we have two scalar operands, s1 and s2 (e.g., group of
1469 strided accesses of size two), while NUNITS is four (i.e., four scalars
1470 of this type can be packed in a vector). The output vector will contain
1471 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
1474 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
1475 containing the operands.
1477 For example, NUNITS is four as before, and the group size is 8
1478 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
1479 {s5, s6, s7, s8}. */
1481 number_of_copies = least_common_multiple (nunits, group_size) / group_size;
1483 number_of_places_left_in_vector = nunits;
1484 for (j = 0; j < number_of_copies; j++)
1486 for (i = group_size - 1; VEC_iterate (gimple, stmts, i, stmt); i--)
1489 op = gimple_assign_rhs1 (stmt);
1491 op = gimple_op (stmt, op_num + 1);
1493 /* Create 'vect_ = {op0,op1,...,opn}'. */
1494 t = tree_cons (NULL_TREE, op, t);
1496 number_of_places_left_in_vector--;
1498 if (number_of_places_left_in_vector == 0)
1500 number_of_places_left_in_vector = nunits;
1503 vec_cst = build_vector (vector_type, t);
1505 vec_cst = build_constructor_from_list (vector_type, t);
1506 VEC_quick_push (tree, voprnds,
1507 vect_init_vector (stmt, vec_cst, vector_type, NULL));
1513 /* Since the vectors are created in the reverse order, we should invert
1515 vec_num = VEC_length (tree, voprnds);
1516 for (j = vec_num - 1; j >= 0; j--)
1518 vop = VEC_index (tree, voprnds, j);
1519 VEC_quick_push (tree, *vec_oprnds, vop);
1522 VEC_free (tree, heap, voprnds);
1524 /* In case that VF is greater than the unrolling factor needed for the SLP
1525 group of stmts, NUMBER_OF_VECTORS to be created is greater than
1526 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
1527 to replicate the vectors. */
1528 while (number_of_vectors > VEC_length (tree, *vec_oprnds))
1530 for (i = 0; VEC_iterate (tree, *vec_oprnds, i, vop) && i < vec_num; i++)
1531 VEC_quick_push (tree, *vec_oprnds, vop);
1536 /* Get vectorized definitions from SLP_NODE that contains corresponding
1537 vectorized def-stmts. */
1540 vect_get_slp_vect_defs (slp_tree slp_node, VEC (tree,heap) **vec_oprnds)
1543 gimple vec_def_stmt;
1546 gcc_assert (SLP_TREE_VEC_STMTS (slp_node));
1549 VEC_iterate (gimple, SLP_TREE_VEC_STMTS (slp_node), i, vec_def_stmt);
1552 gcc_assert (vec_def_stmt);
1553 vec_oprnd = gimple_get_lhs (vec_def_stmt);
1554 VEC_quick_push (tree, *vec_oprnds, vec_oprnd);
1559 /* Get vectorized definitions for SLP_NODE.
1560 If the scalar definitions are loop invariants or constants, collect them and
1561 call vect_get_constant_vectors() to create vector stmts.
1562 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
1563 must be stored in the LEFT/RIGHT node of SLP_NODE, and we call
1564 vect_get_slp_vect_defs() to retrieve them.
1565 If VEC_OPRNDS1 is NULL, don't get vector defs for the second operand (from
1566 the right node. This is used when the second operand must remain scalar. */
1569 vect_get_slp_defs (slp_tree slp_node, VEC (tree,heap) **vec_oprnds0,
1570 VEC (tree,heap) **vec_oprnds1)
1573 enum tree_code code;
1574 int number_of_vects;
1575 HOST_WIDE_INT lhs_size_unit, rhs_size_unit;
1577 first_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0);
1578 /* The number of vector defs is determined by the number of vector statements
1579 in the node from which we get those statements. */
1580 if (SLP_TREE_LEFT (slp_node))
1581 number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_LEFT (slp_node));
1584 number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
1585 /* Number of vector stmts was calculated according to LHS in
1586 vect_schedule_slp_instance(), fix it by replacing LHS with RHS, if
1587 necessary. See vect_get_smallest_scalar_type() for details. */
1588 vect_get_smallest_scalar_type (first_stmt, &lhs_size_unit,
1590 if (rhs_size_unit != lhs_size_unit)
1592 number_of_vects *= rhs_size_unit;
1593 number_of_vects /= lhs_size_unit;
1597 /* Allocate memory for vectorized defs. */
1598 *vec_oprnds0 = VEC_alloc (tree, heap, number_of_vects);
1600 /* SLP_NODE corresponds either to a group of stores or to a group of
1601 unary/binary operations. We don't call this function for loads. */
1602 if (SLP_TREE_LEFT (slp_node))
1603 /* The defs are already vectorized. */
1604 vect_get_slp_vect_defs (SLP_TREE_LEFT (slp_node), vec_oprnds0);
1606 /* Build vectors from scalar defs. */
1607 vect_get_constant_vectors (slp_node, vec_oprnds0, 0, number_of_vects);
1609 if (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt)))
1610 /* Since we don't call this function with loads, this is a group of
1614 code = gimple_assign_rhs_code (first_stmt);
1615 if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS || !vec_oprnds1)
1618 /* The number of vector defs is determined by the number of vector statements
1619 in the node from which we get those statements. */
1620 if (SLP_TREE_RIGHT (slp_node))
1621 number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_RIGHT (slp_node));
1623 number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
1625 *vec_oprnds1 = VEC_alloc (tree, heap, number_of_vects);
1627 if (SLP_TREE_RIGHT (slp_node))
1628 /* The defs are already vectorized. */
1629 vect_get_slp_vect_defs (SLP_TREE_RIGHT (slp_node), vec_oprnds1);
1631 /* Build vectors from scalar defs. */
1632 vect_get_constant_vectors (slp_node, vec_oprnds1, 1, number_of_vects);
1636 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
1637 building a vector of type MASK_TYPE from it) and two input vectors placed in
1638 DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
1639 shifting by STRIDE elements of DR_CHAIN for every copy.
1640 (STRIDE is the number of vectorized stmts for NODE divided by the number of
1642 VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
1643 the created stmts must be inserted. */
1646 vect_create_mask_and_perm (gimple stmt, gimple next_scalar_stmt,
1647 tree mask, int first_vec_indx, int second_vec_indx,
1648 gimple_stmt_iterator *gsi, slp_tree node,
1649 tree builtin_decl, tree vectype,
1650 VEC(tree,heap) *dr_chain,
1651 int ncopies, int vect_stmts_counter)
1654 gimple perm_stmt = NULL;
1655 stmt_vec_info next_stmt_info;
1657 tree first_vec, second_vec, data_ref;
1658 VEC (tree, heap) *params = NULL;
1660 stride = SLP_TREE_NUMBER_OF_VEC_STMTS (node) / ncopies;
1662 /* Initialize the vect stmts of NODE to properly insert the generated
1664 for (i = VEC_length (gimple, SLP_TREE_VEC_STMTS (node));
1665 i < (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node); i++)
1666 VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (node), NULL);
1668 perm_dest = vect_create_destination_var (gimple_assign_lhs (stmt), vectype);
1669 for (i = 0; i < ncopies; i++)
1671 first_vec = VEC_index (tree, dr_chain, first_vec_indx);
1672 second_vec = VEC_index (tree, dr_chain, second_vec_indx);
1674 /* Build argument list for the vectorized call. */
1675 VEC_free (tree, heap, params);
1676 params = VEC_alloc (tree, heap, 3);
1677 VEC_quick_push (tree, params, first_vec);
1678 VEC_quick_push (tree, params, second_vec);
1679 VEC_quick_push (tree, params, mask);
1681 /* Generate the permute statement. */
1682 perm_stmt = gimple_build_call_vec (builtin_decl, params);
1683 data_ref = make_ssa_name (perm_dest, perm_stmt);
1684 gimple_call_set_lhs (perm_stmt, data_ref);
1685 vect_finish_stmt_generation (stmt, perm_stmt, gsi);
1687 /* Store the vector statement in NODE. */
1688 VEC_replace (gimple, SLP_TREE_VEC_STMTS (node),
1689 stride * i + vect_stmts_counter, perm_stmt);
1691 first_vec_indx += stride;
1692 second_vec_indx += stride;
1695 /* Mark the scalar stmt as vectorized. */
1696 next_stmt_info = vinfo_for_stmt (next_scalar_stmt);
1697 STMT_VINFO_VEC_STMT (next_stmt_info) = perm_stmt;
1701 /* Given FIRST_MASK_ELEMENT - the mask element in element representation,
1702 return in CURRENT_MASK_ELEMENT its equivalent in target specific
1703 representation. Check that the mask is valid and return FALSE if not.
1704 Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
1705 the next vector, i.e., the current first vector is not needed. */
1708 vect_get_mask_element (gimple stmt, int first_mask_element, int m,
1709 int mask_nunits, bool only_one_vec, int index,
1710 int *mask, int *current_mask_element,
1711 bool *need_next_vector)
1714 static int number_of_mask_fixes = 1;
1715 static bool mask_fixed = false;
1716 static bool needs_first_vector = false;
1718 /* Convert to target specific representation. */
1719 *current_mask_element = first_mask_element + m;
1720 /* Adjust the value in case it's a mask for second and third vectors. */
1721 *current_mask_element -= mask_nunits * (number_of_mask_fixes - 1);
1723 if (*current_mask_element < mask_nunits)
1724 needs_first_vector = true;
1726 /* We have only one input vector to permute but the mask accesses values in
1727 the next vector as well. */
1728 if (only_one_vec && *current_mask_element >= mask_nunits)
1730 if (vect_print_dump_info (REPORT_DETAILS))
1732 fprintf (vect_dump, "permutation requires at least two vectors ");
1733 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
1739 /* The mask requires the next vector. */
1740 if (*current_mask_element >= mask_nunits * 2)
1742 if (needs_first_vector || mask_fixed)
1744 /* We either need the first vector too or have already moved to the
1745 next vector. In both cases, this permutation needs three
1747 if (vect_print_dump_info (REPORT_DETAILS))
1749 fprintf (vect_dump, "permutation requires at "
1750 "least three vectors ");
1751 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
1757 /* We move to the next vector, dropping the first one and working with
1758 the second and the third - we need to adjust the values of the mask
1760 *current_mask_element -= mask_nunits * number_of_mask_fixes;
1762 for (i = 0; i < index; i++)
1763 mask[i] -= mask_nunits * number_of_mask_fixes;
1765 (number_of_mask_fixes)++;
1769 *need_next_vector = mask_fixed;
1771 /* This was the last element of this mask. Start a new one. */
1772 if (index == mask_nunits - 1)
1774 number_of_mask_fixes = 1;
1776 needs_first_vector = false;
1783 /* Generate vector permute statements from a list of loads in DR_CHAIN.
1784 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
1785 permute statements for SLP_NODE_INSTANCE. */
1787 vect_transform_slp_perm_load (gimple stmt, VEC (tree, heap) *dr_chain,
1788 gimple_stmt_iterator *gsi, int vf,
1789 slp_instance slp_node_instance, bool analyze_only)
1791 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1792 tree mask_element_type = NULL_TREE, mask_type;
1793 int i, j, k, m, scale, mask_nunits, nunits, vec_index = 0, scalar_index;
1795 tree vectype = STMT_VINFO_VECTYPE (stmt_info), builtin_decl;
1796 gimple next_scalar_stmt;
1797 int group_size = SLP_INSTANCE_GROUP_SIZE (slp_node_instance);
1798 int first_mask_element;
1799 int index, unroll_factor, *mask, current_mask_element, ncopies;
1800 bool only_one_vec = false, need_next_vector = false;
1801 int first_vec_index, second_vec_index, orig_vec_stmts_num, vect_stmts_counter;
1803 if (!targetm.vectorize.builtin_vec_perm)
1805 if (vect_print_dump_info (REPORT_DETAILS))
1807 fprintf (vect_dump, "no builtin for vect permute for ");
1808 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
1814 builtin_decl = targetm.vectorize.builtin_vec_perm (vectype,
1815 &mask_element_type);
1816 if (!builtin_decl || !mask_element_type)
1818 if (vect_print_dump_info (REPORT_DETAILS))
1820 fprintf (vect_dump, "no builtin for vect permute for ");
1821 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
1827 mask_type = get_vectype_for_scalar_type (mask_element_type);
1828 mask_nunits = TYPE_VECTOR_SUBPARTS (mask_type);
1829 mask = (int *) xmalloc (sizeof (int) * mask_nunits);
1830 nunits = TYPE_VECTOR_SUBPARTS (vectype);
1831 scale = mask_nunits / nunits;
1832 unroll_factor = SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance);
1834 /* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
1835 unrolling factor. */
1836 orig_vec_stmts_num = group_size *
1837 SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance) / nunits;
1838 if (orig_vec_stmts_num == 1)
1839 only_one_vec = true;
1841 /* Number of copies is determined by the final vectorization factor
1842 relatively to SLP_NODE_INSTANCE unrolling factor. */
1843 ncopies = vf / SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance);
1845 /* Generate permutation masks for every NODE. Number of masks for each NODE
1846 is equal to GROUP_SIZE.
1847 E.g., we have a group of three nodes with three loads from the same
1848 location in each node, and the vector size is 4. I.e., we have a
1849 a0b0c0a1b1c1... sequence and we need to create the following vectors:
1850 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
1851 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
1854 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9} (in target
1855 scpecific type, e.g., in bytes for Altivec.
1856 The last mask is illegal since we assume two operands for permute
1857 operation, and the mask element values can't be outside that range. Hence,
1858 the last mask must be converted into {2,5,5,5}.
1859 For the first two permutations we need the first and the second input
1860 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
1861 we need the second and the third vectors: {b1,c1,a2,b2} and
1865 VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (slp_node_instance),
1871 vect_stmts_counter = 0;
1873 first_vec_index = vec_index++;
1875 second_vec_index = first_vec_index;
1877 second_vec_index = vec_index++;
1879 for (j = 0; j < unroll_factor; j++)
1881 for (k = 0; k < group_size; k++)
1883 first_mask_element = (i + j * group_size) * scale;
1884 for (m = 0; m < scale; m++)
1886 if (!vect_get_mask_element (stmt, first_mask_element, m,
1887 mask_nunits, only_one_vec, index, mask,
1888 ¤t_mask_element, &need_next_vector))
1891 mask[index++] = current_mask_element;
1894 if (index == mask_nunits)
1896 tree mask_vec = NULL;
1898 while (--index >= 0)
1900 tree t = build_int_cst (mask_element_type, mask[index]);
1901 mask_vec = tree_cons (NULL, t, mask_vec);
1903 mask_vec = build_vector (mask_type, mask_vec);
1906 if (!targetm.vectorize.builtin_vec_perm_ok (vectype,
1909 if (vect_print_dump_info (REPORT_DETAILS))
1911 fprintf (vect_dump, "unsupported vect permute ");
1912 print_generic_expr (vect_dump, mask_vec, 0);
1920 if (need_next_vector)
1922 first_vec_index = second_vec_index;
1923 second_vec_index = vec_index;
1926 next_scalar_stmt = VEC_index (gimple,
1927 SLP_TREE_SCALAR_STMTS (node), scalar_index++);
1929 vect_create_mask_and_perm (stmt, next_scalar_stmt,
1930 mask_vec, first_vec_index, second_vec_index,
1931 gsi, node, builtin_decl, vectype, dr_chain,
1932 ncopies, vect_stmts_counter++);
1945 /* Vectorize SLP instance tree in postorder. */
1948 vect_schedule_slp_instance (slp_tree node, slp_instance instance,
1949 unsigned int vectorization_factor)
1952 bool strided_store, is_store;
1953 gimple_stmt_iterator si;
1954 stmt_vec_info stmt_info;
1955 unsigned int vec_stmts_size, nunits, group_size;
1958 slp_tree loads_node;
1963 vect_schedule_slp_instance (SLP_TREE_LEFT (node), instance,
1964 vectorization_factor);
1965 vect_schedule_slp_instance (SLP_TREE_RIGHT (node), instance,
1966 vectorization_factor);
1968 stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
1969 stmt_info = vinfo_for_stmt (stmt);
1971 /* VECTYPE is the type of the destination. */
1972 vectype = get_vectype_for_scalar_type (TREE_TYPE (gimple_assign_lhs (stmt)));
1973 nunits = (unsigned int) TYPE_VECTOR_SUBPARTS (vectype);
1974 group_size = SLP_INSTANCE_GROUP_SIZE (instance);
1976 /* For each SLP instance calculate number of vector stmts to be created
1977 for the scalar stmts in each node of the SLP tree. Number of vector
1978 elements in one vector iteration is the number of scalar elements in
1979 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
1981 vec_stmts_size = (vectorization_factor * group_size) / nunits;
1983 /* In case of load permutation we have to allocate vectorized statements for
1984 all the nodes that participate in that permutation. */
1985 if (SLP_INSTANCE_LOAD_PERMUTATION (instance))
1988 VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), i, loads_node);
1991 if (!SLP_TREE_VEC_STMTS (loads_node))
1993 SLP_TREE_VEC_STMTS (loads_node) = VEC_alloc (gimple, heap,
1995 SLP_TREE_NUMBER_OF_VEC_STMTS (loads_node) = vec_stmts_size;
2000 if (!SLP_TREE_VEC_STMTS (node))
2002 SLP_TREE_VEC_STMTS (node) = VEC_alloc (gimple, heap, vec_stmts_size);
2003 SLP_TREE_NUMBER_OF_VEC_STMTS (node) = vec_stmts_size;
2006 if (vect_print_dump_info (REPORT_DETAILS))
2008 fprintf (vect_dump, "------>vectorizing SLP node starting from: ");
2009 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
2012 /* Loads should be inserted before the first load. */
2013 if (SLP_INSTANCE_FIRST_LOAD_STMT (instance)
2014 && STMT_VINFO_STRIDED_ACCESS (stmt_info)
2015 && !REFERENCE_CLASS_P (gimple_get_lhs (stmt)))
2016 si = gsi_for_stmt (SLP_INSTANCE_FIRST_LOAD_STMT (instance));
2018 si = gsi_for_stmt (stmt);
2020 is_store = vect_transform_stmt (stmt, &si, &strided_store, node, instance);
2023 if (DR_GROUP_FIRST_DR (stmt_info))
2024 /* If IS_STORE is TRUE, the vectorization of the
2025 interleaving chain was completed - free all the stores in
2027 vect_remove_stores (DR_GROUP_FIRST_DR (stmt_info));
2029 /* FORNOW: SLP originates only from strided stores. */
2035 /* FORNOW: SLP originates only from strided stores. */
2041 vect_schedule_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
2043 VEC (slp_instance, heap) *slp_instances;
2044 slp_instance instance;
2046 bool is_store = false;
2050 slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
2051 vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2055 slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
2059 for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
2061 /* Schedule the tree of INSTANCE. */
2062 is_store = vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance),
2064 if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS)
2065 || vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
2066 fprintf (vect_dump, "vectorizing stmts using SLP.");
2073 /* Vectorize the basic block. */
2076 vect_slp_transform_bb (basic_block bb)
2078 bb_vec_info bb_vinfo = vec_info_for_bb (bb);
2079 gimple_stmt_iterator si;
2081 gcc_assert (bb_vinfo);
2083 if (vect_print_dump_info (REPORT_DETAILS))
2084 fprintf (vect_dump, "SLPing BB\n");
2086 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2088 gimple stmt = gsi_stmt (si);
2089 stmt_vec_info stmt_info;
2091 if (vect_print_dump_info (REPORT_DETAILS))
2093 fprintf (vect_dump, "------>SLPing statement: ");
2094 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
2097 stmt_info = vinfo_for_stmt (stmt);
2098 gcc_assert (stmt_info);
2100 /* Schedule all the SLP instances when the first SLP stmt is reached. */
2101 if (STMT_SLP_TYPE (stmt_info))
2103 vect_schedule_slp (NULL, bb_vinfo);
2108 mark_sym_for_renaming (gimple_vop (cfun));
2109 /* The memory tags and pointers in vectorized statements need to
2110 have their SSA forms updated. FIXME, why can't this be delayed
2111 until all the loops have been transformed? */
2112 update_ssa (TODO_update_ssa);
2114 if (vect_print_dump_info (REPORT_DETAILS))
2115 fprintf (vect_dump, "BASIC BLOCK VECTORIZED\n");
2117 destroy_bb_vec_info (bb_vinfo);