2017-06-02 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / tree-vect-slp.c
blobd221fc63873c10edbf65d35009a1522e8cad44bf
1 /* SLP - Basic Block Vectorization
2 Copyright (C) 2007-2017 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
11 version.
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
16 for more details.
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/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "backend.h"
26 #include "target.h"
27 #include "rtl.h"
28 #include "tree.h"
29 #include "gimple.h"
30 #include "tree-pass.h"
31 #include "ssa.h"
32 #include "optabs-tree.h"
33 #include "insn-config.h"
34 #include "recog.h" /* FIXME: for insn_data */
35 #include "params.h"
36 #include "fold-const.h"
37 #include "stor-layout.h"
38 #include "gimple-iterator.h"
39 #include "cfgloop.h"
40 #include "tree-vectorizer.h"
41 #include "langhooks.h"
42 #include "gimple-walk.h"
43 #include "dbgcnt.h"
46 /* Recursively free the memory allocated for the SLP tree rooted at NODE. */
48 static void
49 vect_free_slp_tree (slp_tree node)
51 int i;
52 slp_tree child;
54 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
55 vect_free_slp_tree (child);
57 gimple *stmt;
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 ();
71 free (node);
75 /* Free the memory allocated for the SLP instance. */
77 void
78 vect_free_slp_instance (slp_instance instance)
80 vect_free_slp_tree (SLP_INSTANCE_TREE (instance));
81 SLP_INSTANCE_LOADS (instance).release ();
82 free (instance);
86 /* Create an SLP node for SCALAR_STMTS. */
88 static slp_tree
89 vect_create_new_slp_node (vec<gimple *> scalar_stmts)
91 slp_tree node;
92 gimple *stmt = scalar_stmts[0];
93 unsigned int nops;
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)
101 nops++;
103 else
104 return NULL;
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;
114 unsigned i;
115 FOR_EACH_VEC_ELT (scalar_stmts, i, stmt)
116 STMT_VINFO_NUM_SLP_USES (vinfo_for_stmt (stmt))++;
118 return node;
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
124 node. */
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
131 stmt. */
132 tree first_op_type;
133 enum vect_def_type first_dt;
134 bool first_pattern;
135 bool second_pattern;
136 } *slp_oprnd_info;
139 /* Allocate operands info for NOPS operands, and GROUP_SIZE def-stmts for each
140 operand. */
141 static vec<slp_oprnd_info>
142 vect_create_oprnd_info (int nops, int group_size)
144 int i;
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);
160 return oprnds_info;
164 /* Free operands info. */
166 static void
167 vect_free_oprnd_info (vec<slp_oprnd_info> &oprnds_info)
169 int i;
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. */
185 static int
186 vect_get_place_in_interleaving_chain (gimple *stmt, gimple *first_stmt)
188 gimple *next_stmt = first_stmt;
189 int result = 0;
191 if (first_stmt != GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
192 return -1;
196 if (next_stmt == stmt)
197 return result;
198 next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
199 if (next_stmt)
200 result += GROUP_GAP (vinfo_for_stmt (next_stmt));
202 while (next_stmt);
204 return -1;
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
218 ok return 0. */
220 static int
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)
225 tree oprnd;
226 unsigned int i, number_of_oprnds;
227 gimple *def_stmt;
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);
240 first_op_idx = 3;
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;
252 number_of_oprnds++;
254 else
255 commutative = commutative_tree_code (code);
257 else
258 return -1;
260 bool swapped = (*swap != 0);
261 gcc_assert (!swapped || first_op_cond);
262 for (i = 0; i < number_of_oprnds; i++)
264 again:
265 if (first_op_cond)
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];
271 if (i < 2)
272 oprnd = TREE_OPERAND (gimple_op (stmt, first_op_idx), map[i]);
273 else
274 oprnd = gimple_op (stmt, map[i]);
276 else
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");
291 return -1;
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
296 pattern. */
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)))
304 pattern = true;
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)))
311 if (i == 0
312 && !swapped
313 && commutative)
315 swapped = true;
316 goto again;
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");
328 return 1;
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");
339 return -1;
342 switch (gimple_code (def_stmt))
344 case GIMPLE_PHI:
345 case GIMPLE_ASSIGN:
346 break;
348 default:
349 if (dump_enabled_p ())
350 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
351 "unsupported defining stmt:\n");
352 return -1;
356 if (second)
357 oprnd_info->second_pattern = pattern;
359 if (first)
361 oprnd_info->first_dt = dt;
362 oprnd_info->first_pattern = pattern;
363 oprnd_info->first_op_type = TREE_TYPE (oprnd);
365 else
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,
380 TREE_TYPE (oprnd))))
382 /* Try swapping operands if we got a mismatch. */
383 if (i == 0
384 && !swapped
385 && commutative)
387 swapped = true;
388 goto again;
391 if (dump_enabled_p ())
392 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
393 "Build SLP failed: different types\n");
395 return 1;
399 /* Check the types of the definitions. */
400 switch (dt)
402 case vect_constant_def:
403 case vect_external_def:
404 case vect_reduction_def:
405 break;
407 case vect_internal_def:
408 oprnd_info->def_stmts.quick_push (def_stmt);
409 break;
411 default:
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");
421 return -1;
425 /* Swap operands. */
426 if (swapped)
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 "
436 "shared stmt ");
437 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
439 return -1;
442 if (first_op_cond)
444 tree cond = gimple_assign_rhs1 (stmt);
445 enum tree_code code = TREE_CODE (cond);
447 /* Swap. */
448 if (*swap == 1)
450 swap_ssa_operands (stmt, &TREE_OPERAND (cond, 0),
451 &TREE_OPERAND (cond, 1));
452 TREE_SET_CODE (cond, swap_tree_comparison (code));
454 /* Invert. */
455 else
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);
465 else
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);
476 *swap = swapped;
477 return 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. */
495 static bool
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)
501 unsigned int i;
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;
507 tree lhs;
508 bool need_same_oprnds = false;
509 tree vectype = NULL_TREE, scalar_type, first_op1 = NULL_TREE;
510 optab optab;
511 int icode;
512 machine_mode optab_op2_mode;
513 machine_mode vec_mode;
514 HOST_WIDE_INT dummy;
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)
520 swap[i] = 0;
521 matches[i] = false;
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. */
539 matches[0] = false;
540 return false;
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 "
550 "GIMPLE_CALL ");
551 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
553 /* Fatal mismatch. */
554 matches[0] = false;
555 return false;
558 scalar_type = vect_get_smallest_scalar_type (stmt, &dummy, &dummy);
559 vectype = get_vectype_for_scalar_type (scalar_type);
560 if (!vectype)
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,
567 scalar_type);
568 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
570 /* Fatal mismatch. */
571 matches[0] = false;
572 return false;
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. */
584 matches[0] = false;
585 return false;
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,
606 call_stmt, 0);
608 /* Fatal mismatch. */
609 matches[0] = false;
610 return false;
613 else
614 rhs_code = gimple_assign_rhs_code (stmt);
616 /* Check the operation. */
617 if (i == 0)
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,
631 optab_vector);
633 if (!optab
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,
638 optab_scalar);
640 if (!optab)
642 if (dump_enabled_p ())
643 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
644 "Build SLP failed: no optab.\n");
645 /* Fatal mismatch. */
646 matches[0] = false;
647 return false;
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,
654 "Build SLP failed: "
655 "op not supported by target.\n");
656 /* Fatal mismatch. */
657 matches[0] = false;
658 return false;
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);
674 else
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 "
702 "in stmt ");
703 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
704 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
705 "original stmt ");
706 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
707 first_stmt, 0);
709 /* Mismatch. */
710 continue;
713 if (need_same_oprnds
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 "
720 "arguments in ");
721 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
723 /* Mismatch. */
724 continue;
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,
741 stmt, 0);
743 /* Mismatch. */
744 continue;
749 /* Grouped store or load. */
750 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt)))
752 if (REFERENCE_CLASS_P (lhs))
754 /* Store. */
757 else
759 /* Load. */
760 first_load = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt));
761 if (prev_first_load)
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,
770 vect_location,
771 "Build SLP failed: different "
772 "interleaving chains in one node ");
773 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
774 stmt, 0);
776 /* Mismatch. */
777 continue;
780 else
781 prev_first_load = first_load;
783 } /* Grouped access. */
784 else
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. */
798 matches[0] = false;
799 return false;
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. */
817 matches[0] = false;
818 return false;
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;
828 if (i == 0)
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)
841 swap[i] = 1;
842 /* Isomorphic can be achieved by inverting. */
843 else if (first_cond_code == invert_code)
844 swap[i] = 2;
845 else
847 if (dump_enabled_p ())
849 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
850 "Build SLP failed: different"
851 " operation");
852 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
853 stmt, 0);
855 /* Mismatch. */
856 continue;
861 matches[i] = true;
864 for (i = 0; i < group_size; ++i)
865 if (!matches[i])
866 return false;
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)
873 unsigned char *sel
874 = XALLOCAVEC (unsigned char, TYPE_VECTOR_SUBPARTS (vectype));
875 for (i = 0; i < TYPE_VECTOR_SUBPARTS (vectype); ++i)
877 sel[i] = 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)
886 matches[i] = false;
887 if (dump_enabled_p ())
889 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
890 "Build SLP failed: different operation "
891 "in stmt ");
892 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
893 stmts[i], 0);
894 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
895 "original stmt ");
896 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
897 first_stmt, 0);
900 return false;
902 *two_operators = true;
905 return 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
913 was found. */
915 static slp_tree
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;
924 gimple *stmt;
925 slp_tree node;
927 matches[0] = false;
929 stmt = stmts[0];
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)
936 nops++;
938 else
939 return NULL;
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))
946 return NULL;
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);
955 return 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);
965 if (res != 0)
966 matches[(res == -1) ? 0 : i] = false;
967 if (!matches[0])
968 break;
970 for (i = 0; i < group_size; ++i)
971 if (!matches[i])
973 vect_free_oprnd_info (oprnds_info);
974 return NULL;
977 auto_vec<slp_tree, 4> children;
978 auto_vec<slp_tree> this_loads;
980 stmt = stmts[0];
982 /* Create SLP_TREE nodes for the definition node/s. */
983 FOR_EACH_VEC_ELT (oprnds_info, i, oprnd_info)
985 slp_tree child;
986 unsigned old_nloads = this_loads.length ();
987 unsigned old_tree_size = this_tree_size;
988 unsigned int j;
990 if (oprnd_info->first_dt != vect_internal_def)
991 continue;
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);
998 return NULL;
1001 if ((child = vect_build_slp_tree (vinfo, oprnd_info->def_stmts,
1002 group_size, &this_max_nunits,
1003 &this_loads, matches, npermutes,
1004 &this_tree_size,
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
1012 scalar version. */
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)
1020 break;
1021 if (!grandchild)
1023 /* Roll back. */
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);
1036 continue;
1040 oprnd_info->def_stmts = vNULL;
1041 children.safe_push (child);
1042 continue;
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
1052 SLP tree size... */
1053 if (is_a <bb_vec_info> (vinfo)
1054 && !matches[0]
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
1057 scalar version. */
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;
1066 continue;
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. */
1072 if (i == 0
1073 /* A first scalar stmt mismatch signals a fatal mismatch. */
1074 && matches[0]
1075 /* ??? For COND_EXPRs we can swap the comparison operands
1076 as well as the arms under some constraints. */
1077 && nops == 2
1078 && oprnds_info[1]->first_dt == vect_internal_def
1079 && is_gimple_assign (stmt)
1080 && commutative_tree_code (gimple_assign_rhs_code (stmt))
1081 && ! two_operators
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
1085 behavior. */
1086 && *npermutes < 4)
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)
1091 if (!matches[j]
1092 && (swap[j] != 0
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 "
1099 "of shared stmt ");
1100 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
1101 stmts[j], 0);
1103 goto fail;
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)
1110 if (!matches[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,
1122 &this_tree_size,
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];
1139 if (!matches[j])
1141 /* Avoid swapping operands twice. */
1142 if (gimple_plf (stmt, GF_PLF_1))
1143 continue;
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. */
1150 if (flag_checking)
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
1162 scalar version. */
1163 && !is_pattern_stmt_p
1164 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child)[0])))
1166 unsigned int j;
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)
1171 break;
1172 if (!grandchild)
1174 /* Roll back. */
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);
1187 continue;
1191 oprnd_info->def_stmts = vNULL;
1192 children.safe_push (child);
1193 continue;
1196 ++*npermutes;
1199 fail:
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);
1204 return NULL;
1207 vect_free_oprnd_info (oprnds_info);
1209 if (tree_size)
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);
1217 return node;
1220 /* Dump a slp tree NODE using flags specified in DUMP_KIND. */
1222 static void
1223 vect_print_slp_tree (dump_flags_t dump_kind, location_t loc, slp_tree node)
1225 int i;
1226 gimple *stmt;
1227 slp_tree child;
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. */
1247 static void
1248 vect_mark_slp_stmts (slp_tree node, enum slp_vect_type mark, int j)
1250 int i;
1251 gimple *stmt;
1252 slp_tree child;
1254 if (SLP_TREE_DEF_TYPE (node) != vect_internal_def)
1255 return;
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). */
1268 static void
1269 vect_mark_slp_stmts_relevant (slp_tree node)
1271 int i;
1272 gimple *stmt;
1273 stmt_vec_info stmt_info;
1274 slp_tree child;
1276 if (SLP_TREE_DEF_TYPE (node) != vect_internal_def)
1277 return;
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. */
1294 static void
1295 vect_slp_rearrange_stmts (slp_tree node, unsigned int group_size,
1296 vec<unsigned> permutation)
1298 gimple *stmt;
1299 vec<gimple *> tmp_stmts;
1300 unsigned int i;
1301 slp_tree child;
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. */
1322 static bool
1323 vect_attempt_slp_rearrange_stmts (slp_instance slp_instn)
1325 unsigned int group_size = SLP_INSTANCE_GROUP_SIZE (slp_instn);
1326 unsigned int i, j;
1327 unsigned int lidx;
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 ())
1334 return false;
1335 for (i = 1; SLP_INSTANCE_LOADS (slp_instn).iterate (i, &load); ++i)
1337 if (!load->load_permutation.exists ())
1338 return false;
1339 FOR_EACH_VEC_ELT (load->load_permutation, j, lidx)
1340 if (lidx != node->load_permutation[j])
1341 return false;
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)
1351 return false;
1352 if (bitmap_bit_p (load_index, lidx))
1353 return false;
1355 bitmap_set_bit (load_index, lidx);
1357 for (i = 0; i < group_size; i++)
1358 if (!bitmap_bit_p (load_index, i))
1359 return false;
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 ();
1380 else
1381 for (j = 0; j < SLP_TREE_LOAD_PERMUTATION (node).length (); ++j)
1382 SLP_TREE_LOAD_PERMUTATION (node)[j] = j;
1385 return true;
1388 /* Check if the required load permutations in the SLP instance
1389 SLP_INSTN are supported. */
1391 static bool
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;
1396 slp_tree node;
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);
1406 else
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
1417 permutation). */
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)
1423 return false;
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
1435 chain.
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 ())
1444 continue;
1445 bool subchain_p = true;
1446 next_load = NULL;
1447 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), j, load)
1449 if (j != 0
1450 && (next_load != load
1451 || GROUP_GAP (vinfo_for_stmt (load)) != 1))
1453 subchain_p = false;
1454 break;
1456 next_load = GROUP_NEXT_ELEMENT (vinfo_for_stmt (load));
1458 if (subchain_p)
1459 SLP_TREE_LOAD_PERMUTATION (node).release ();
1460 else
1462 stmt_vec_info group_info
1463 = vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node)[0]);
1464 group_info = vinfo_for_stmt (GROUP_FIRST_ELEMENT (group_info));
1465 unsigned nunits
1466 = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (group_info));
1467 unsigned k, maxk = 0;
1468 FOR_EACH_VEC_ELT (SLP_TREE_LOAD_PERMUTATION (node), j, k)
1469 if (k > maxk)
1470 maxk = k;
1471 /* In BB vectorization we may not actually use a loaded vector
1472 accessing elements in excess of GROUP_SIZE. */
1473 if (maxk >= (GROUP_SIZE (group_info) & ~(nunits - 1)))
1475 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1476 "BB vectorization with gaps at the end of "
1477 "a load is not supported\n");
1478 return false;
1481 /* Verify the permutation can be generated. */
1482 vec<tree> tem;
1483 unsigned n_perms;
1484 if (!vect_transform_slp_perm_load (node, tem, NULL,
1485 1, slp_instn, true, &n_perms))
1487 dump_printf_loc (MSG_MISSED_OPTIMIZATION,
1488 vect_location,
1489 "unsupported load permutation\n");
1490 return false;
1494 return true;
1497 /* For loop vectorization verify we can generate the permutation. */
1498 unsigned n_perms;
1499 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
1500 if (node->load_permutation.exists ()
1501 && !vect_transform_slp_perm_load
1502 (node, vNULL, NULL,
1503 SLP_INSTANCE_UNROLLING_FACTOR (slp_instn), slp_instn, true,
1504 &n_perms))
1505 return false;
1507 return true;
1511 /* Find the last store in SLP INSTANCE. */
1513 gimple *
1514 vect_find_last_scalar_stmt_in_slp (slp_tree node)
1516 gimple *last = NULL, *stmt;
1518 for (int i = 0; SLP_TREE_SCALAR_STMTS (node).iterate (i, &stmt); i++)
1520 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
1521 if (is_pattern_stmt_p (stmt_vinfo))
1522 last = get_later_stmt (STMT_VINFO_RELATED_STMT (stmt_vinfo), last);
1523 else
1524 last = get_later_stmt (stmt, last);
1527 return last;
1530 /* Compute the cost for the SLP node NODE in the SLP instance INSTANCE. */
1532 static void
1533 vect_analyze_slp_cost_1 (slp_instance instance, slp_tree node,
1534 stmt_vector_for_cost *prologue_cost_vec,
1535 stmt_vector_for_cost *body_cost_vec,
1536 unsigned ncopies_for_cost)
1538 unsigned i, j;
1539 slp_tree child;
1540 gimple *stmt;
1541 stmt_vec_info stmt_info;
1542 tree lhs;
1544 /* Recurse down the SLP tree. */
1545 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
1546 if (SLP_TREE_DEF_TYPE (child) == vect_internal_def)
1547 vect_analyze_slp_cost_1 (instance, child, prologue_cost_vec,
1548 body_cost_vec, ncopies_for_cost);
1550 /* Look at the first scalar stmt to determine the cost. */
1551 stmt = SLP_TREE_SCALAR_STMTS (node)[0];
1552 stmt_info = vinfo_for_stmt (stmt);
1553 if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
1555 vect_memory_access_type memory_access_type
1556 = (STMT_VINFO_STRIDED_P (stmt_info)
1557 ? VMAT_STRIDED_SLP
1558 : VMAT_CONTIGUOUS);
1559 if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info)))
1560 vect_model_store_cost (stmt_info, ncopies_for_cost,
1561 memory_access_type, vect_uninitialized_def,
1562 node, prologue_cost_vec, body_cost_vec);
1563 else
1565 gcc_checking_assert (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info)));
1566 if (SLP_TREE_LOAD_PERMUTATION (node).exists ())
1568 /* If the load is permuted then the alignment is determined by
1569 the first group element not by the first scalar stmt DR. */
1570 stmt = GROUP_FIRST_ELEMENT (stmt_info);
1571 stmt_info = vinfo_for_stmt (stmt);
1572 /* Record the cost for the permutation. */
1573 unsigned n_perms;
1574 vect_transform_slp_perm_load (node, vNULL, NULL,
1575 ncopies_for_cost, instance, true,
1576 &n_perms);
1577 record_stmt_cost (body_cost_vec, n_perms, vec_perm,
1578 stmt_info, 0, vect_body);
1579 unsigned nunits
1580 = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
1581 /* And adjust the number of loads performed. This handles
1582 redundancies as well as loads that are later dead. */
1583 auto_sbitmap perm (GROUP_SIZE (stmt_info));
1584 bitmap_clear (perm);
1585 for (i = 0; i < SLP_TREE_LOAD_PERMUTATION (node).length (); ++i)
1586 bitmap_set_bit (perm, SLP_TREE_LOAD_PERMUTATION (node)[i]);
1587 ncopies_for_cost = 0;
1588 bool load_seen = false;
1589 for (i = 0; i < GROUP_SIZE (stmt_info); ++i)
1591 if (i % nunits == 0)
1593 if (load_seen)
1594 ncopies_for_cost++;
1595 load_seen = false;
1597 if (bitmap_bit_p (perm, i))
1598 load_seen = true;
1600 if (load_seen)
1601 ncopies_for_cost++;
1602 gcc_assert (ncopies_for_cost
1603 <= (GROUP_SIZE (stmt_info) - GROUP_GAP (stmt_info)
1604 + nunits - 1) / nunits);
1605 ncopies_for_cost *= SLP_INSTANCE_UNROLLING_FACTOR (instance);
1607 /* Record the cost for the vector loads. */
1608 vect_model_load_cost (stmt_info, ncopies_for_cost,
1609 memory_access_type, node, prologue_cost_vec,
1610 body_cost_vec);
1611 return;
1614 else
1616 record_stmt_cost (body_cost_vec, ncopies_for_cost, vector_stmt,
1617 stmt_info, 0, vect_body);
1618 if (SLP_TREE_TWO_OPERATORS (node))
1620 record_stmt_cost (body_cost_vec, ncopies_for_cost, vector_stmt,
1621 stmt_info, 0, vect_body);
1622 record_stmt_cost (body_cost_vec, ncopies_for_cost, vec_perm,
1623 stmt_info, 0, vect_body);
1627 /* Push SLP node def-type to stmts. */
1628 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
1629 if (SLP_TREE_DEF_TYPE (child) != vect_internal_def)
1630 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child), j, stmt)
1631 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt)) = SLP_TREE_DEF_TYPE (child);
1633 /* Scan operands and account for prologue cost of constants/externals.
1634 ??? This over-estimates cost for multiple uses and should be
1635 re-engineered. */
1636 stmt = SLP_TREE_SCALAR_STMTS (node)[0];
1637 lhs = gimple_get_lhs (stmt);
1638 for (i = 0; i < gimple_num_ops (stmt); ++i)
1640 tree op = gimple_op (stmt, i);
1641 gimple *def_stmt;
1642 enum vect_def_type dt;
1643 if (!op || op == lhs)
1644 continue;
1645 if (vect_is_simple_use (op, stmt_info->vinfo, &def_stmt, &dt))
1647 /* Without looking at the actual initializer a vector of
1648 constants can be implemented as load from the constant pool.
1649 ??? We need to pass down stmt_info for a vector type
1650 even if it points to the wrong stmt. */
1651 if (dt == vect_constant_def)
1652 record_stmt_cost (prologue_cost_vec, 1, vector_load,
1653 stmt_info, 0, vect_prologue);
1654 else if (dt == vect_external_def)
1655 record_stmt_cost (prologue_cost_vec, 1, vec_construct,
1656 stmt_info, 0, vect_prologue);
1660 /* Restore stmt def-types. */
1661 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
1662 if (SLP_TREE_DEF_TYPE (child) != vect_internal_def)
1663 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child), j, stmt)
1664 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt)) = vect_internal_def;
1667 /* Compute the cost for the SLP instance INSTANCE. */
1669 static void
1670 vect_analyze_slp_cost (slp_instance instance, void *data)
1672 stmt_vector_for_cost body_cost_vec, prologue_cost_vec;
1673 unsigned ncopies_for_cost;
1674 stmt_info_for_cost *si;
1675 unsigned i;
1677 if (dump_enabled_p ())
1678 dump_printf_loc (MSG_NOTE, vect_location,
1679 "=== vect_analyze_slp_cost ===\n");
1681 /* Calculate the number of vector stmts to create based on the unrolling
1682 factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
1683 GROUP_SIZE / NUNITS otherwise. */
1684 unsigned group_size = SLP_INSTANCE_GROUP_SIZE (instance);
1685 slp_tree node = SLP_INSTANCE_TREE (instance);
1686 stmt_vec_info stmt_info = vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node)[0]);
1687 /* Adjust the group_size by the vectorization factor which is always one
1688 for basic-block vectorization. */
1689 if (STMT_VINFO_LOOP_VINFO (stmt_info))
1690 group_size *= LOOP_VINFO_VECT_FACTOR (STMT_VINFO_LOOP_VINFO (stmt_info));
1691 unsigned nunits = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
1692 /* For reductions look at a reduction operand in case the reduction
1693 operation is widening like DOT_PROD or SAD. */
1694 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info))
1696 gimple *stmt = SLP_TREE_SCALAR_STMTS (node)[0];
1697 switch (gimple_assign_rhs_code (stmt))
1699 case DOT_PROD_EXPR:
1700 case SAD_EXPR:
1701 nunits = TYPE_VECTOR_SUBPARTS (get_vectype_for_scalar_type
1702 (TREE_TYPE (gimple_assign_rhs1 (stmt))));
1703 break;
1704 default:;
1707 ncopies_for_cost = least_common_multiple (nunits, group_size) / nunits;
1709 prologue_cost_vec.create (10);
1710 body_cost_vec.create (10);
1711 vect_analyze_slp_cost_1 (instance, SLP_INSTANCE_TREE (instance),
1712 &prologue_cost_vec, &body_cost_vec,
1713 ncopies_for_cost);
1715 /* Record the prologue costs, which were delayed until we were
1716 sure that SLP was successful. */
1717 FOR_EACH_VEC_ELT (prologue_cost_vec, i, si)
1719 struct _stmt_vec_info *stmt_info
1720 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
1721 (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
1722 si->misalign, vect_prologue);
1725 /* Record the instance's instructions in the target cost model. */
1726 FOR_EACH_VEC_ELT (body_cost_vec, i, si)
1728 struct _stmt_vec_info *stmt_info
1729 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
1730 (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
1731 si->misalign, vect_body);
1734 prologue_cost_vec.release ();
1735 body_cost_vec.release ();
1738 /* Splits a group of stores, currently beginning at FIRST_STMT, into two groups:
1739 one (still beginning at FIRST_STMT) of size GROUP1_SIZE (also containing
1740 the first GROUP1_SIZE stmts, since stores are consecutive), the second
1741 containing the remainder.
1742 Return the first stmt in the second group. */
1744 static gimple *
1745 vect_split_slp_store_group (gimple *first_stmt, unsigned group1_size)
1747 stmt_vec_info first_vinfo = vinfo_for_stmt (first_stmt);
1748 gcc_assert (GROUP_FIRST_ELEMENT (first_vinfo) == first_stmt);
1749 gcc_assert (group1_size > 0);
1750 int group2_size = GROUP_SIZE (first_vinfo) - group1_size;
1751 gcc_assert (group2_size > 0);
1752 GROUP_SIZE (first_vinfo) = group1_size;
1754 gimple *stmt = first_stmt;
1755 for (unsigned i = group1_size; i > 1; i--)
1757 stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt));
1758 gcc_assert (GROUP_GAP (vinfo_for_stmt (stmt)) == 1);
1760 /* STMT is now the last element of the first group. */
1761 gimple *group2 = GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt));
1762 GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt)) = 0;
1764 GROUP_SIZE (vinfo_for_stmt (group2)) = group2_size;
1765 for (stmt = group2; stmt; stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt)))
1767 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = group2;
1768 gcc_assert (GROUP_GAP (vinfo_for_stmt (stmt)) == 1);
1771 /* For the second group, the GROUP_GAP is that before the original group,
1772 plus skipping over the first vector. */
1773 GROUP_GAP (vinfo_for_stmt (group2)) =
1774 GROUP_GAP (first_vinfo) + group1_size;
1776 /* GROUP_GAP of the first group now has to skip over the second group too. */
1777 GROUP_GAP (first_vinfo) += group2_size;
1779 if (dump_enabled_p ())
1780 dump_printf_loc (MSG_NOTE, vect_location, "Split group into %d and %d\n",
1781 group1_size, group2_size);
1783 return group2;
1786 /* Analyze an SLP instance starting from a group of grouped stores. Call
1787 vect_build_slp_tree to build a tree of packed stmts if possible.
1788 Return FALSE if it's impossible to SLP any stmt in the loop. */
1790 static bool
1791 vect_analyze_slp_instance (vec_info *vinfo,
1792 gimple *stmt, unsigned max_tree_size)
1794 slp_instance new_instance;
1795 slp_tree node;
1796 unsigned int group_size = GROUP_SIZE (vinfo_for_stmt (stmt));
1797 unsigned int unrolling_factor = 1, nunits;
1798 tree vectype, scalar_type = NULL_TREE;
1799 gimple *next;
1800 unsigned int i;
1801 unsigned int max_nunits = 0;
1802 vec<slp_tree> loads;
1803 struct data_reference *dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
1804 vec<gimple *> scalar_stmts;
1806 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
1808 if (dr)
1810 scalar_type = TREE_TYPE (DR_REF (dr));
1811 vectype = get_vectype_for_scalar_type (scalar_type);
1813 else
1815 gcc_assert (is_a <loop_vec_info> (vinfo));
1816 vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
1819 group_size = GROUP_SIZE (vinfo_for_stmt (stmt));
1821 else
1823 gcc_assert (is_a <loop_vec_info> (vinfo));
1824 vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
1825 group_size = as_a <loop_vec_info> (vinfo)->reductions.length ();
1828 if (!vectype)
1830 if (dump_enabled_p ())
1832 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1833 "Build SLP failed: unsupported data-type ");
1834 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, scalar_type);
1835 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
1838 return false;
1840 nunits = TYPE_VECTOR_SUBPARTS (vectype);
1842 /* Create a node (a root of the SLP tree) for the packed grouped stores. */
1843 scalar_stmts.create (group_size);
1844 next = stmt;
1845 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
1847 /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
1848 while (next)
1850 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next))
1851 && STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next)))
1852 scalar_stmts.safe_push (
1853 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next)));
1854 else
1855 scalar_stmts.safe_push (next);
1856 next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next));
1858 /* Mark the first element of the reduction chain as reduction to properly
1859 transform the node. In the reduction analysis phase only the last
1860 element of the chain is marked as reduction. */
1861 if (!STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt)))
1862 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt)) = vect_reduction_def;
1864 else
1866 /* Collect reduction statements. */
1867 vec<gimple *> reductions = as_a <loop_vec_info> (vinfo)->reductions;
1868 for (i = 0; reductions.iterate (i, &next); i++)
1869 scalar_stmts.safe_push (next);
1872 loads.create (group_size);
1874 /* Build the tree for the SLP instance. */
1875 bool *matches = XALLOCAVEC (bool, group_size);
1876 unsigned npermutes = 0;
1877 node = vect_build_slp_tree (vinfo, scalar_stmts, group_size,
1878 &max_nunits, &loads, matches, &npermutes,
1879 NULL, max_tree_size);
1880 if (node != NULL)
1882 /* Calculate the unrolling factor based on the smallest type. */
1883 unrolling_factor
1884 = least_common_multiple (max_nunits, group_size) / group_size;
1886 if (unrolling_factor != 1
1887 && is_a <bb_vec_info> (vinfo))
1890 if (max_nunits > group_size)
1892 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1893 "Build SLP failed: store group "
1894 "size not a multiple of the vector size "
1895 "in basic block SLP\n");
1896 vect_free_slp_tree (node);
1897 loads.release ();
1898 return false;
1900 /* Fatal mismatch. */
1901 matches[group_size/max_nunits * max_nunits] = false;
1902 vect_free_slp_tree (node);
1903 loads.release ();
1905 else
1907 /* Create a new SLP instance. */
1908 new_instance = XNEW (struct _slp_instance);
1909 SLP_INSTANCE_TREE (new_instance) = node;
1910 SLP_INSTANCE_GROUP_SIZE (new_instance) = group_size;
1911 SLP_INSTANCE_UNROLLING_FACTOR (new_instance) = unrolling_factor;
1912 SLP_INSTANCE_LOADS (new_instance) = loads;
1914 /* Compute the load permutation. */
1915 slp_tree load_node;
1916 bool loads_permuted = false;
1917 FOR_EACH_VEC_ELT (loads, i, load_node)
1919 vec<unsigned> load_permutation;
1920 int j;
1921 gimple *load, *first_stmt;
1922 bool this_load_permuted = false;
1923 load_permutation.create (group_size);
1924 first_stmt = GROUP_FIRST_ELEMENT
1925 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node)[0]));
1926 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node), j, load)
1928 int load_place = vect_get_place_in_interleaving_chain
1929 (load, first_stmt);
1930 gcc_assert (load_place != -1);
1931 if (load_place != j)
1932 this_load_permuted = true;
1933 load_permutation.safe_push (load_place);
1935 if (!this_load_permuted
1936 /* The load requires permutation when unrolling exposes
1937 a gap either because the group is larger than the SLP
1938 group-size or because there is a gap between the groups. */
1939 && (unrolling_factor == 1
1940 || (group_size == GROUP_SIZE (vinfo_for_stmt (first_stmt))
1941 && GROUP_GAP (vinfo_for_stmt (first_stmt)) == 0)))
1943 load_permutation.release ();
1944 continue;
1946 SLP_TREE_LOAD_PERMUTATION (load_node) = load_permutation;
1947 loads_permuted = true;
1950 if (loads_permuted)
1952 if (!vect_supported_load_permutation_p (new_instance))
1954 if (dump_enabled_p ())
1956 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1957 "Build SLP failed: unsupported load "
1958 "permutation ");
1959 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION,
1960 TDF_SLIM, stmt, 0);
1962 vect_free_slp_instance (new_instance);
1963 return false;
1967 /* If the loads and stores can be handled with load/store-lan
1968 instructions do not generate this SLP instance. */
1969 if (is_a <loop_vec_info> (vinfo)
1970 && loads_permuted
1971 && dr && vect_store_lanes_supported (vectype, group_size))
1973 slp_tree load_node;
1974 FOR_EACH_VEC_ELT (loads, i, load_node)
1976 gimple *first_stmt = GROUP_FIRST_ELEMENT
1977 (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node)[0]));
1978 stmt_vec_info stmt_vinfo = vinfo_for_stmt (first_stmt);
1979 /* Use SLP for strided accesses (or if we
1980 can't load-lanes). */
1981 if (STMT_VINFO_STRIDED_P (stmt_vinfo)
1982 || ! vect_load_lanes_supported
1983 (STMT_VINFO_VECTYPE (stmt_vinfo),
1984 GROUP_SIZE (stmt_vinfo)))
1985 break;
1987 if (i == loads.length ())
1989 if (dump_enabled_p ())
1990 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1991 "Built SLP cancelled: can use "
1992 "load/store-lanes\n");
1993 vect_free_slp_instance (new_instance);
1994 return false;
1998 vinfo->slp_instances.safe_push (new_instance);
2000 if (dump_enabled_p ())
2002 dump_printf_loc (MSG_NOTE, vect_location,
2003 "Final SLP tree for instance:\n");
2004 vect_print_slp_tree (MSG_NOTE, vect_location, node);
2007 return true;
2010 else
2012 /* Failed to SLP. */
2013 /* Free the allocated memory. */
2014 scalar_stmts.release ();
2015 loads.release ();
2018 /* For basic block SLP, try to break the group up into multiples of the
2019 vector size. */
2020 if (is_a <bb_vec_info> (vinfo)
2021 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt))
2022 && STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt)))
2024 /* We consider breaking the group only on VF boundaries from the existing
2025 start. */
2026 for (i = 0; i < group_size; i++)
2027 if (!matches[i]) break;
2029 if (i >= nunits && i < group_size)
2031 /* Split into two groups at the first vector boundary before i. */
2032 gcc_assert ((nunits & (nunits - 1)) == 0);
2033 unsigned group1_size = i & ~(nunits - 1);
2035 gimple *rest = vect_split_slp_store_group (stmt, group1_size);
2036 bool res = vect_analyze_slp_instance (vinfo, stmt, max_tree_size);
2037 /* If the first non-match was in the middle of a vector,
2038 skip the rest of that vector. */
2039 if (group1_size < i)
2041 i = group1_size + nunits;
2042 if (i < group_size)
2043 rest = vect_split_slp_store_group (rest, nunits);
2045 if (i < group_size)
2046 res |= vect_analyze_slp_instance (vinfo, rest, max_tree_size);
2047 return res;
2049 /* Even though the first vector did not all match, we might be able to SLP
2050 (some) of the remainder. FORNOW ignore this possibility. */
2053 return false;
2057 /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
2058 trees of packed scalar stmts if SLP is possible. */
2060 bool
2061 vect_analyze_slp (vec_info *vinfo, unsigned max_tree_size)
2063 unsigned int i;
2064 gimple *first_element;
2065 bool ok = false;
2067 if (dump_enabled_p ())
2068 dump_printf_loc (MSG_NOTE, vect_location, "=== vect_analyze_slp ===\n");
2070 /* Find SLP sequences starting from groups of grouped stores. */
2071 FOR_EACH_VEC_ELT (vinfo->grouped_stores, i, first_element)
2072 if (vect_analyze_slp_instance (vinfo, first_element, max_tree_size))
2073 ok = true;
2075 if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo))
2077 if (loop_vinfo->reduction_chains.length () > 0)
2079 /* Find SLP sequences starting from reduction chains. */
2080 FOR_EACH_VEC_ELT (loop_vinfo->reduction_chains, i, first_element)
2081 if (vect_analyze_slp_instance (vinfo, first_element,
2082 max_tree_size))
2083 ok = true;
2084 else
2085 return false;
2087 /* Don't try to vectorize SLP reductions if reduction chain was
2088 detected. */
2089 return ok;
2092 /* Find SLP sequences starting from groups of reductions. */
2093 if (loop_vinfo->reductions.length () > 1
2094 && vect_analyze_slp_instance (vinfo, loop_vinfo->reductions[0],
2095 max_tree_size))
2096 ok = true;
2099 return true;
2103 /* For each possible SLP instance decide whether to SLP it and calculate overall
2104 unrolling factor needed to SLP the loop. Return TRUE if decided to SLP at
2105 least one instance. */
2107 bool
2108 vect_make_slp_decision (loop_vec_info loop_vinfo)
2110 unsigned int i, unrolling_factor = 1;
2111 vec<slp_instance> slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
2112 slp_instance instance;
2113 int decided_to_slp = 0;
2115 if (dump_enabled_p ())
2116 dump_printf_loc (MSG_NOTE, vect_location, "=== vect_make_slp_decision ==="
2117 "\n");
2119 FOR_EACH_VEC_ELT (slp_instances, i, instance)
2121 /* FORNOW: SLP if you can. */
2122 if (unrolling_factor < SLP_INSTANCE_UNROLLING_FACTOR (instance))
2123 unrolling_factor = SLP_INSTANCE_UNROLLING_FACTOR (instance);
2125 /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
2126 call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
2127 loop-based vectorization. Such stmts will be marked as HYBRID. */
2128 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
2129 decided_to_slp++;
2132 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo) = unrolling_factor;
2134 if (decided_to_slp && dump_enabled_p ())
2135 dump_printf_loc (MSG_NOTE, vect_location,
2136 "Decided to SLP %d instances. Unrolling factor %d\n",
2137 decided_to_slp, unrolling_factor);
2139 return (decided_to_slp > 0);
2143 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
2144 can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
2146 static void
2147 vect_detect_hybrid_slp_stmts (slp_tree node, unsigned i, slp_vect_type stype)
2149 gimple *stmt = SLP_TREE_SCALAR_STMTS (node)[i];
2150 imm_use_iterator imm_iter;
2151 gimple *use_stmt;
2152 stmt_vec_info use_vinfo, stmt_vinfo = vinfo_for_stmt (stmt);
2153 slp_tree child;
2154 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
2155 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2156 int j;
2158 /* Propagate hybrid down the SLP tree. */
2159 if (stype == hybrid)
2161 else if (HYBRID_SLP_STMT (stmt_vinfo))
2162 stype = hybrid;
2163 else
2165 /* Check if a pure SLP stmt has uses in non-SLP stmts. */
2166 gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo));
2167 /* If we get a pattern stmt here we have to use the LHS of the
2168 original stmt for immediate uses. */
2169 if (! STMT_VINFO_IN_PATTERN_P (stmt_vinfo)
2170 && STMT_VINFO_RELATED_STMT (stmt_vinfo))
2171 stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
2172 if (TREE_CODE (gimple_op (stmt, 0)) == SSA_NAME)
2173 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, gimple_op (stmt, 0))
2175 if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
2176 continue;
2177 use_vinfo = vinfo_for_stmt (use_stmt);
2178 if (STMT_VINFO_IN_PATTERN_P (use_vinfo)
2179 && STMT_VINFO_RELATED_STMT (use_vinfo))
2180 use_vinfo = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (use_vinfo));
2181 if (!STMT_SLP_TYPE (use_vinfo)
2182 && (STMT_VINFO_RELEVANT (use_vinfo)
2183 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo)))
2184 && !(gimple_code (use_stmt) == GIMPLE_PHI
2185 && STMT_VINFO_DEF_TYPE (use_vinfo) == vect_reduction_def))
2187 if (dump_enabled_p ())
2189 dump_printf_loc (MSG_NOTE, vect_location, "use of SLP "
2190 "def in non-SLP stmt: ");
2191 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, use_stmt, 0);
2193 stype = hybrid;
2198 if (stype == hybrid
2199 && !HYBRID_SLP_STMT (stmt_vinfo))
2201 if (dump_enabled_p ())
2203 dump_printf_loc (MSG_NOTE, vect_location, "marking hybrid: ");
2204 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
2206 STMT_SLP_TYPE (stmt_vinfo) = hybrid;
2209 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), j, child)
2210 if (SLP_TREE_DEF_TYPE (child) != vect_external_def)
2211 vect_detect_hybrid_slp_stmts (child, i, stype);
2214 /* Helpers for vect_detect_hybrid_slp walking pattern stmt uses. */
2216 static tree
2217 vect_detect_hybrid_slp_1 (tree *tp, int *, void *data)
2219 walk_stmt_info *wi = (walk_stmt_info *)data;
2220 struct loop *loopp = (struct loop *)wi->info;
2222 if (wi->is_lhs)
2223 return NULL_TREE;
2225 if (TREE_CODE (*tp) == SSA_NAME
2226 && !SSA_NAME_IS_DEFAULT_DEF (*tp))
2228 gimple *def_stmt = SSA_NAME_DEF_STMT (*tp);
2229 if (flow_bb_inside_loop_p (loopp, gimple_bb (def_stmt))
2230 && PURE_SLP_STMT (vinfo_for_stmt (def_stmt)))
2232 if (dump_enabled_p ())
2234 dump_printf_loc (MSG_NOTE, vect_location, "marking hybrid: ");
2235 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, def_stmt, 0);
2237 STMT_SLP_TYPE (vinfo_for_stmt (def_stmt)) = hybrid;
2241 return NULL_TREE;
2244 static tree
2245 vect_detect_hybrid_slp_2 (gimple_stmt_iterator *gsi, bool *handled,
2246 walk_stmt_info *)
2248 /* If the stmt is in a SLP instance then this isn't a reason
2249 to mark use definitions in other SLP instances as hybrid. */
2250 if (STMT_SLP_TYPE (vinfo_for_stmt (gsi_stmt (*gsi))) != loop_vect)
2251 *handled = true;
2252 return NULL_TREE;
2255 /* Find stmts that must be both vectorized and SLPed. */
2257 void
2258 vect_detect_hybrid_slp (loop_vec_info loop_vinfo)
2260 unsigned int i;
2261 vec<slp_instance> slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
2262 slp_instance instance;
2264 if (dump_enabled_p ())
2265 dump_printf_loc (MSG_NOTE, vect_location, "=== vect_detect_hybrid_slp ==="
2266 "\n");
2268 /* First walk all pattern stmt in the loop and mark defs of uses as
2269 hybrid because immediate uses in them are not recorded. */
2270 for (i = 0; i < LOOP_VINFO_LOOP (loop_vinfo)->num_nodes; ++i)
2272 basic_block bb = LOOP_VINFO_BBS (loop_vinfo)[i];
2273 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
2274 gsi_next (&gsi))
2276 gimple *stmt = gsi_stmt (gsi);
2277 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2278 if (STMT_VINFO_IN_PATTERN_P (stmt_info))
2280 walk_stmt_info wi;
2281 memset (&wi, 0, sizeof (wi));
2282 wi.info = LOOP_VINFO_LOOP (loop_vinfo);
2283 gimple_stmt_iterator gsi2
2284 = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info));
2285 walk_gimple_stmt (&gsi2, vect_detect_hybrid_slp_2,
2286 vect_detect_hybrid_slp_1, &wi);
2287 walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info),
2288 vect_detect_hybrid_slp_2,
2289 vect_detect_hybrid_slp_1, &wi);
2294 /* Then walk the SLP instance trees marking stmts with uses in
2295 non-SLP stmts as hybrid, also propagating hybrid down the
2296 SLP tree, collecting the above info on-the-fly. */
2297 FOR_EACH_VEC_ELT (slp_instances, i, instance)
2299 for (unsigned i = 0; i < SLP_INSTANCE_GROUP_SIZE (instance); ++i)
2300 vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance),
2301 i, pure_slp);
2306 /* Create and initialize a new bb_vec_info struct for BB, as well as
2307 stmt_vec_info structs for all the stmts in it. */
2309 static bb_vec_info
2310 new_bb_vec_info (gimple_stmt_iterator region_begin,
2311 gimple_stmt_iterator region_end)
2313 basic_block bb = gsi_bb (region_begin);
2314 bb_vec_info res = NULL;
2315 gimple_stmt_iterator gsi;
2317 res = (bb_vec_info) xcalloc (1, sizeof (struct _bb_vec_info));
2318 res->kind = vec_info::bb;
2319 BB_VINFO_BB (res) = bb;
2320 res->region_begin = region_begin;
2321 res->region_end = region_end;
2323 for (gsi = region_begin; gsi_stmt (gsi) != gsi_stmt (region_end);
2324 gsi_next (&gsi))
2326 gimple *stmt = gsi_stmt (gsi);
2327 gimple_set_uid (stmt, 0);
2328 set_vinfo_for_stmt (stmt, new_stmt_vec_info (stmt, res));
2331 BB_VINFO_GROUPED_STORES (res).create (10);
2332 BB_VINFO_SLP_INSTANCES (res).create (2);
2333 BB_VINFO_TARGET_COST_DATA (res) = init_cost (NULL);
2335 bb->aux = res;
2336 return res;
2340 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
2341 stmts in the basic block. */
2343 static void
2344 destroy_bb_vec_info (bb_vec_info bb_vinfo)
2346 slp_instance instance;
2347 unsigned i;
2349 if (!bb_vinfo)
2350 return;
2352 vect_destroy_datarefs (bb_vinfo);
2353 free_dependence_relations (BB_VINFO_DDRS (bb_vinfo));
2354 BB_VINFO_GROUPED_STORES (bb_vinfo).release ();
2355 FOR_EACH_VEC_ELT (BB_VINFO_SLP_INSTANCES (bb_vinfo), i, instance)
2356 vect_free_slp_instance (instance);
2357 BB_VINFO_SLP_INSTANCES (bb_vinfo).release ();
2358 destroy_cost_data (BB_VINFO_TARGET_COST_DATA (bb_vinfo));
2360 for (gimple_stmt_iterator si = bb_vinfo->region_begin;
2361 gsi_stmt (si) != gsi_stmt (bb_vinfo->region_end); gsi_next (&si))
2363 gimple *stmt = gsi_stmt (si);
2364 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2366 if (stmt_info)
2367 /* Free stmt_vec_info. */
2368 free_stmt_vec_info (stmt);
2370 /* Reset region marker. */
2371 gimple_set_uid (stmt, -1);
2374 BB_VINFO_BB (bb_vinfo)->aux = NULL;
2375 free (bb_vinfo);
2379 /* Analyze statements contained in SLP tree node after recursively analyzing
2380 the subtree. Return TRUE if the operations are supported. */
2382 static bool
2383 vect_slp_analyze_node_operations (slp_tree node)
2385 bool dummy;
2386 int i, j;
2387 gimple *stmt;
2388 slp_tree child;
2390 if (SLP_TREE_DEF_TYPE (node) != vect_internal_def)
2391 return true;
2393 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
2394 if (!vect_slp_analyze_node_operations (child))
2395 return false;
2397 bool res = true;
2398 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
2400 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2401 gcc_assert (stmt_info);
2402 gcc_assert (STMT_SLP_TYPE (stmt_info) != loop_vect);
2404 /* Push SLP node def-type to stmt operands. */
2405 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), j, child)
2406 if (SLP_TREE_DEF_TYPE (child) != vect_internal_def)
2407 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child)[i]))
2408 = SLP_TREE_DEF_TYPE (child);
2409 res = vect_analyze_stmt (stmt, &dummy, node);
2410 /* Restore def-types. */
2411 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), j, child)
2412 if (SLP_TREE_DEF_TYPE (child) != vect_internal_def)
2413 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (child)[i]))
2414 = vect_internal_def;
2415 if (! res)
2416 break;
2419 return res;
2423 /* Analyze statements in SLP instances of the basic block. Return TRUE if the
2424 operations are supported. */
2426 bool
2427 vect_slp_analyze_operations (vec<slp_instance> slp_instances, void *data)
2429 slp_instance instance;
2430 int i;
2432 if (dump_enabled_p ())
2433 dump_printf_loc (MSG_NOTE, vect_location,
2434 "=== vect_slp_analyze_operations ===\n");
2436 for (i = 0; slp_instances.iterate (i, &instance); )
2438 if (!vect_slp_analyze_node_operations (SLP_INSTANCE_TREE (instance)))
2440 dump_printf_loc (MSG_NOTE, vect_location,
2441 "removing SLP instance operations starting from: ");
2442 dump_gimple_stmt (MSG_NOTE, TDF_SLIM,
2443 SLP_TREE_SCALAR_STMTS
2444 (SLP_INSTANCE_TREE (instance))[0], 0);
2445 vect_free_slp_instance (instance);
2446 slp_instances.ordered_remove (i);
2448 else
2450 /* Compute the costs of the SLP instance. */
2451 vect_analyze_slp_cost (instance, data);
2452 i++;
2456 if (!slp_instances.length ())
2457 return false;
2459 return true;
2463 /* Compute the scalar cost of the SLP node NODE and its children
2464 and return it. Do not account defs that are marked in LIFE and
2465 update LIFE according to uses of NODE. */
2467 static unsigned
2468 vect_bb_slp_scalar_cost (basic_block bb,
2469 slp_tree node, vec<bool, va_heap> *life)
2471 unsigned scalar_cost = 0;
2472 unsigned i;
2473 gimple *stmt;
2474 slp_tree child;
2476 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
2478 unsigned stmt_cost;
2479 ssa_op_iter op_iter;
2480 def_operand_p def_p;
2481 stmt_vec_info stmt_info;
2483 if ((*life)[i])
2484 continue;
2486 /* If there is a non-vectorized use of the defs then the scalar
2487 stmt is kept live in which case we do not account it or any
2488 required defs in the SLP children in the scalar cost. This
2489 way we make the vectorization more costly when compared to
2490 the scalar cost. */
2491 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_DEF)
2493 imm_use_iterator use_iter;
2494 gimple *use_stmt;
2495 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, DEF_FROM_PTR (def_p))
2496 if (!is_gimple_debug (use_stmt)
2497 && (! vect_stmt_in_region_p (vinfo_for_stmt (stmt)->vinfo,
2498 use_stmt)
2499 || ! PURE_SLP_STMT (vinfo_for_stmt (use_stmt))))
2501 (*life)[i] = true;
2502 BREAK_FROM_IMM_USE_STMT (use_iter);
2505 if ((*life)[i])
2506 continue;
2508 /* Count scalar stmts only once. */
2509 if (gimple_visited_p (stmt))
2510 continue;
2511 gimple_set_visited (stmt, true);
2513 stmt_info = vinfo_for_stmt (stmt);
2514 if (STMT_VINFO_DATA_REF (stmt_info))
2516 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info)))
2517 stmt_cost = vect_get_stmt_cost (scalar_load);
2518 else
2519 stmt_cost = vect_get_stmt_cost (scalar_store);
2521 else
2522 stmt_cost = vect_get_stmt_cost (scalar_stmt);
2524 scalar_cost += stmt_cost;
2527 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
2528 if (SLP_TREE_DEF_TYPE (child) == vect_internal_def)
2529 scalar_cost += vect_bb_slp_scalar_cost (bb, child, life);
2531 return scalar_cost;
2534 /* Check if vectorization of the basic block is profitable. */
2536 static bool
2537 vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo)
2539 vec<slp_instance> slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
2540 slp_instance instance;
2541 int i;
2542 unsigned int vec_inside_cost = 0, vec_outside_cost = 0, scalar_cost = 0;
2543 unsigned int vec_prologue_cost = 0, vec_epilogue_cost = 0;
2545 /* Calculate scalar cost. */
2546 FOR_EACH_VEC_ELT (slp_instances, i, instance)
2548 auto_vec<bool, 20> life;
2549 life.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance));
2550 scalar_cost += vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo),
2551 SLP_INSTANCE_TREE (instance),
2552 &life);
2555 /* Unset visited flag. */
2556 for (gimple_stmt_iterator gsi = bb_vinfo->region_begin;
2557 gsi_stmt (gsi) != gsi_stmt (bb_vinfo->region_end); gsi_next (&gsi))
2558 gimple_set_visited (gsi_stmt (gsi), false);
2560 /* Complete the target-specific cost calculation. */
2561 finish_cost (BB_VINFO_TARGET_COST_DATA (bb_vinfo), &vec_prologue_cost,
2562 &vec_inside_cost, &vec_epilogue_cost);
2564 vec_outside_cost = vec_prologue_cost + vec_epilogue_cost;
2566 if (dump_enabled_p ())
2568 dump_printf_loc (MSG_NOTE, vect_location, "Cost model analysis: \n");
2569 dump_printf (MSG_NOTE, " Vector inside of basic block cost: %d\n",
2570 vec_inside_cost);
2571 dump_printf (MSG_NOTE, " Vector prologue cost: %d\n", vec_prologue_cost);
2572 dump_printf (MSG_NOTE, " Vector epilogue cost: %d\n", vec_epilogue_cost);
2573 dump_printf (MSG_NOTE, " Scalar cost of basic block: %d\n", scalar_cost);
2576 /* Vectorization is profitable if its cost is more than the cost of scalar
2577 version. Note that we err on the vector side for equal cost because
2578 the cost estimate is otherwise quite pessimistic (constant uses are
2579 free on the scalar side but cost a load on the vector side for
2580 example). */
2581 if (vec_outside_cost + vec_inside_cost > scalar_cost)
2582 return false;
2584 return true;
2587 /* Check if the basic block can be vectorized. Returns a bb_vec_info
2588 if so and sets fatal to true if failure is independent of
2589 current_vector_size. */
2591 static bb_vec_info
2592 vect_slp_analyze_bb_1 (gimple_stmt_iterator region_begin,
2593 gimple_stmt_iterator region_end,
2594 vec<data_reference_p> datarefs, int n_stmts,
2595 bool &fatal)
2597 bb_vec_info bb_vinfo;
2598 slp_instance instance;
2599 int i;
2600 int min_vf = 2;
2602 /* The first group of checks is independent of the vector size. */
2603 fatal = true;
2605 if (n_stmts > PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB))
2607 if (dump_enabled_p ())
2608 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2609 "not vectorized: too many instructions in "
2610 "basic block.\n");
2611 free_data_refs (datarefs);
2612 return NULL;
2615 bb_vinfo = new_bb_vec_info (region_begin, region_end);
2616 if (!bb_vinfo)
2617 return NULL;
2619 BB_VINFO_DATAREFS (bb_vinfo) = datarefs;
2621 /* Analyze the data references. */
2623 if (!vect_analyze_data_refs (bb_vinfo, &min_vf))
2625 if (dump_enabled_p ())
2626 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2627 "not vectorized: unhandled data-ref in basic "
2628 "block.\n");
2630 destroy_bb_vec_info (bb_vinfo);
2631 return NULL;
2634 if (BB_VINFO_DATAREFS (bb_vinfo).length () < 2)
2636 if (dump_enabled_p ())
2637 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2638 "not vectorized: not enough data-refs in "
2639 "basic block.\n");
2641 destroy_bb_vec_info (bb_vinfo);
2642 return NULL;
2645 if (!vect_analyze_data_ref_accesses (bb_vinfo))
2647 if (dump_enabled_p ())
2648 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2649 "not vectorized: unhandled data access in "
2650 "basic block.\n");
2652 destroy_bb_vec_info (bb_vinfo);
2653 return NULL;
2656 /* If there are no grouped stores in the region there is no need
2657 to continue with pattern recog as vect_analyze_slp will fail
2658 anyway. */
2659 if (bb_vinfo->grouped_stores.is_empty ())
2661 if (dump_enabled_p ())
2662 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2663 "not vectorized: no grouped stores in "
2664 "basic block.\n");
2666 destroy_bb_vec_info (bb_vinfo);
2667 return NULL;
2670 /* While the rest of the analysis below depends on it in some way. */
2671 fatal = false;
2673 vect_pattern_recog (bb_vinfo);
2675 /* Check the SLP opportunities in the basic block, analyze and build SLP
2676 trees. */
2677 if (!vect_analyze_slp (bb_vinfo, n_stmts))
2679 if (dump_enabled_p ())
2681 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2682 "Failed to SLP the basic block.\n");
2683 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2684 "not vectorized: failed to find SLP opportunities "
2685 "in basic block.\n");
2688 destroy_bb_vec_info (bb_vinfo);
2689 return NULL;
2692 /* Analyze and verify the alignment of data references and the
2693 dependence in the SLP instances. */
2694 for (i = 0; BB_VINFO_SLP_INSTANCES (bb_vinfo).iterate (i, &instance); )
2696 if (! vect_slp_analyze_and_verify_instance_alignment (instance)
2697 || ! vect_slp_analyze_instance_dependence (instance))
2699 dump_printf_loc (MSG_NOTE, vect_location,
2700 "removing SLP instance operations starting from: ");
2701 dump_gimple_stmt (MSG_NOTE, TDF_SLIM,
2702 SLP_TREE_SCALAR_STMTS
2703 (SLP_INSTANCE_TREE (instance))[0], 0);
2704 vect_free_slp_instance (instance);
2705 BB_VINFO_SLP_INSTANCES (bb_vinfo).ordered_remove (i);
2706 continue;
2709 /* Mark all the statements that we want to vectorize as pure SLP and
2710 relevant. */
2711 vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
2712 vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance));
2714 i++;
2716 if (! BB_VINFO_SLP_INSTANCES (bb_vinfo).length ())
2718 destroy_bb_vec_info (bb_vinfo);
2719 return NULL;
2722 if (!vect_slp_analyze_operations (BB_VINFO_SLP_INSTANCES (bb_vinfo),
2723 BB_VINFO_TARGET_COST_DATA (bb_vinfo)))
2725 if (dump_enabled_p ())
2726 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2727 "not vectorized: bad operation in basic block.\n");
2729 destroy_bb_vec_info (bb_vinfo);
2730 return NULL;
2733 /* Cost model: check if the vectorization is worthwhile. */
2734 if (!unlimited_cost_model (NULL)
2735 && !vect_bb_vectorization_profitable_p (bb_vinfo))
2737 if (dump_enabled_p ())
2738 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2739 "not vectorized: vectorization is not "
2740 "profitable.\n");
2742 destroy_bb_vec_info (bb_vinfo);
2743 return NULL;
2746 if (dump_enabled_p ())
2747 dump_printf_loc (MSG_NOTE, vect_location,
2748 "Basic block will be vectorized using SLP\n");
2750 return bb_vinfo;
2754 /* Main entry for the BB vectorizer. Analyze and transform BB, returns
2755 true if anything in the basic-block was vectorized. */
2757 bool
2758 vect_slp_bb (basic_block bb)
2760 bb_vec_info bb_vinfo;
2761 gimple_stmt_iterator gsi;
2762 unsigned int vector_sizes;
2763 bool any_vectorized = false;
2765 if (dump_enabled_p ())
2766 dump_printf_loc (MSG_NOTE, vect_location, "===vect_slp_analyze_bb===\n");
2768 /* Autodetect first vector size we try. */
2769 current_vector_size = 0;
2770 vector_sizes = targetm.vectorize.autovectorize_vector_sizes ();
2772 gsi = gsi_start_bb (bb);
2774 while (1)
2776 if (gsi_end_p (gsi))
2777 break;
2779 gimple_stmt_iterator region_begin = gsi;
2780 vec<data_reference_p> datarefs = vNULL;
2781 int insns = 0;
2783 for (; !gsi_end_p (gsi); gsi_next (&gsi))
2785 gimple *stmt = gsi_stmt (gsi);
2786 if (is_gimple_debug (stmt))
2787 continue;
2788 insns++;
2790 if (gimple_location (stmt) != UNKNOWN_LOCATION)
2791 vect_location = gimple_location (stmt);
2793 if (!find_data_references_in_stmt (NULL, stmt, &datarefs))
2794 break;
2797 /* Skip leading unhandled stmts. */
2798 if (gsi_stmt (region_begin) == gsi_stmt (gsi))
2800 gsi_next (&gsi);
2801 continue;
2804 gimple_stmt_iterator region_end = gsi;
2806 bool vectorized = false;
2807 bool fatal = false;
2808 bb_vinfo = vect_slp_analyze_bb_1 (region_begin, region_end,
2809 datarefs, insns, fatal);
2810 if (bb_vinfo
2811 && dbg_cnt (vect_slp))
2813 if (dump_enabled_p ())
2814 dump_printf_loc (MSG_NOTE, vect_location, "SLPing BB part\n");
2816 vect_schedule_slp (bb_vinfo);
2818 if (dump_enabled_p ())
2819 dump_printf_loc (MSG_NOTE, vect_location,
2820 "basic block part vectorized\n");
2822 destroy_bb_vec_info (bb_vinfo);
2824 vectorized = true;
2826 else
2827 destroy_bb_vec_info (bb_vinfo);
2829 any_vectorized |= vectorized;
2831 vector_sizes &= ~current_vector_size;
2832 if (vectorized
2833 || vector_sizes == 0
2834 || current_vector_size == 0
2835 /* If vect_slp_analyze_bb_1 signaled that analysis for all
2836 vector sizes will fail do not bother iterating. */
2837 || fatal)
2839 if (gsi_end_p (region_end))
2840 break;
2842 /* Skip the unhandled stmt. */
2843 gsi_next (&gsi);
2845 /* And reset vector sizes. */
2846 current_vector_size = 0;
2847 vector_sizes = targetm.vectorize.autovectorize_vector_sizes ();
2849 else
2851 /* Try the next biggest vector size. */
2852 current_vector_size = 1 << floor_log2 (vector_sizes);
2853 if (dump_enabled_p ())
2854 dump_printf_loc (MSG_NOTE, vect_location,
2855 "***** Re-trying analysis with "
2856 "vector size %d\n", current_vector_size);
2858 /* Start over. */
2859 gsi = region_begin;
2863 return any_vectorized;
2867 /* Return 1 if vector type of boolean constant which is OPNUM
2868 operand in statement STMT is a boolean vector. */
2870 static bool
2871 vect_mask_constant_operand_p (gimple *stmt, int opnum)
2873 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
2874 enum tree_code code = gimple_expr_code (stmt);
2875 tree op, vectype;
2876 gimple *def_stmt;
2877 enum vect_def_type dt;
2879 /* For comparison and COND_EXPR type is chosen depending
2880 on the other comparison operand. */
2881 if (TREE_CODE_CLASS (code) == tcc_comparison)
2883 if (opnum)
2884 op = gimple_assign_rhs1 (stmt);
2885 else
2886 op = gimple_assign_rhs2 (stmt);
2888 if (!vect_is_simple_use (op, stmt_vinfo->vinfo, &def_stmt,
2889 &dt, &vectype))
2890 gcc_unreachable ();
2892 return !vectype || VECTOR_BOOLEAN_TYPE_P (vectype);
2895 if (code == COND_EXPR)
2897 tree cond = gimple_assign_rhs1 (stmt);
2899 if (TREE_CODE (cond) == SSA_NAME)
2900 op = cond;
2901 else if (opnum)
2902 op = TREE_OPERAND (cond, 1);
2903 else
2904 op = TREE_OPERAND (cond, 0);
2906 if (!vect_is_simple_use (op, stmt_vinfo->vinfo, &def_stmt,
2907 &dt, &vectype))
2908 gcc_unreachable ();
2910 return !vectype || VECTOR_BOOLEAN_TYPE_P (vectype);
2913 return VECTOR_BOOLEAN_TYPE_P (STMT_VINFO_VECTYPE (stmt_vinfo));
2917 /* For constant and loop invariant defs of SLP_NODE this function returns
2918 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
2919 OP_NUM determines if we gather defs for operand 0 or operand 1 of the RHS of
2920 scalar stmts. NUMBER_OF_VECTORS is the number of vector defs to create.
2921 REDUC_INDEX is the index of the reduction operand in the statements, unless
2922 it is -1. */
2924 static void
2925 vect_get_constant_vectors (tree op, slp_tree slp_node,
2926 vec<tree> *vec_oprnds,
2927 unsigned int op_num, unsigned int number_of_vectors,
2928 int reduc_index)
2930 vec<gimple *> stmts = SLP_TREE_SCALAR_STMTS (slp_node);
2931 gimple *stmt = stmts[0];
2932 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
2933 unsigned nunits;
2934 tree vec_cst;
2935 tree *elts;
2936 unsigned j, number_of_places_left_in_vector;
2937 tree vector_type;
2938 tree vop;
2939 int group_size = stmts.length ();
2940 unsigned int vec_num, i;
2941 unsigned number_of_copies = 1;
2942 vec<tree> voprnds;
2943 voprnds.create (number_of_vectors);
2944 bool constant_p, is_store;
2945 tree neutral_op = NULL;
2946 enum tree_code code = gimple_expr_code (stmt);
2947 gimple *def_stmt;
2948 struct loop *loop;
2949 gimple_seq ctor_seq = NULL;
2951 /* Check if vector type is a boolean vector. */
2952 if (VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (op))
2953 && vect_mask_constant_operand_p (stmt, op_num))
2954 vector_type
2955 = build_same_sized_truth_vector_type (STMT_VINFO_VECTYPE (stmt_vinfo));
2956 else
2957 vector_type = get_vectype_for_scalar_type (TREE_TYPE (op));
2958 nunits = TYPE_VECTOR_SUBPARTS (vector_type);
2960 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
2961 && reduc_index != -1)
2963 op_num = reduc_index;
2964 op = gimple_op (stmt, op_num + 1);
2965 /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
2966 we need either neutral operands or the original operands. See
2967 get_initial_def_for_reduction() for details. */
2968 switch (code)
2970 case WIDEN_SUM_EXPR:
2971 case DOT_PROD_EXPR:
2972 case SAD_EXPR:
2973 case PLUS_EXPR:
2974 case MINUS_EXPR:
2975 case BIT_IOR_EXPR:
2976 case BIT_XOR_EXPR:
2977 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op)))
2978 neutral_op = build_real (TREE_TYPE (op), dconst0);
2979 else
2980 neutral_op = build_int_cst (TREE_TYPE (op), 0);
2982 break;
2984 case MULT_EXPR:
2985 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op)))
2986 neutral_op = build_real (TREE_TYPE (op), dconst1);
2987 else
2988 neutral_op = build_int_cst (TREE_TYPE (op), 1);
2990 break;
2992 case BIT_AND_EXPR:
2993 neutral_op = build_int_cst (TREE_TYPE (op), -1);
2994 break;
2996 /* For MIN/MAX we don't have an easy neutral operand but
2997 the initial values can be used fine here. Only for
2998 a reduction chain we have to force a neutral element. */
2999 case MAX_EXPR:
3000 case MIN_EXPR:
3001 if (!GROUP_FIRST_ELEMENT (stmt_vinfo))
3002 neutral_op = NULL;
3003 else
3005 def_stmt = SSA_NAME_DEF_STMT (op);
3006 loop = (gimple_bb (stmt))->loop_father;
3007 neutral_op = PHI_ARG_DEF_FROM_EDGE (def_stmt,
3008 loop_preheader_edge (loop));
3010 break;
3012 default:
3013 gcc_assert (!GROUP_FIRST_ELEMENT (stmt_vinfo));
3014 neutral_op = NULL;
3018 if (STMT_VINFO_DATA_REF (stmt_vinfo))
3020 is_store = true;
3021 op = gimple_assign_rhs1 (stmt);
3023 else
3024 is_store = false;
3026 gcc_assert (op);
3028 if (CONSTANT_CLASS_P (op))
3029 constant_p = true;
3030 else
3031 constant_p = false;
3033 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
3034 created vectors. It is greater than 1 if unrolling is performed.
3036 For example, we have two scalar operands, s1 and s2 (e.g., group of
3037 strided accesses of size two), while NUNITS is four (i.e., four scalars
3038 of this type can be packed in a vector). The output vector will contain
3039 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
3040 will be 2).
3042 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
3043 containing the operands.
3045 For example, NUNITS is four as before, and the group size is 8
3046 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
3047 {s5, s6, s7, s8}. */
3049 number_of_copies = nunits * number_of_vectors / group_size;
3051 number_of_places_left_in_vector = nunits;
3052 elts = XALLOCAVEC (tree, nunits);
3053 bool place_after_defs = false;
3054 for (j = 0; j < number_of_copies; j++)
3056 for (i = group_size - 1; stmts.iterate (i, &stmt); i--)
3058 if (is_store)
3059 op = gimple_assign_rhs1 (stmt);
3060 else
3062 switch (code)
3064 case COND_EXPR:
3066 tree cond = gimple_assign_rhs1 (stmt);
3067 if (TREE_CODE (cond) == SSA_NAME)
3068 op = gimple_op (stmt, op_num + 1);
3069 else if (op_num == 0 || op_num == 1)
3070 op = TREE_OPERAND (cond, op_num);
3071 else
3073 if (op_num == 2)
3074 op = gimple_assign_rhs2 (stmt);
3075 else
3076 op = gimple_assign_rhs3 (stmt);
3079 break;
3081 case CALL_EXPR:
3082 op = gimple_call_arg (stmt, op_num);
3083 break;
3085 case LSHIFT_EXPR:
3086 case RSHIFT_EXPR:
3087 case LROTATE_EXPR:
3088 case RROTATE_EXPR:
3089 op = gimple_op (stmt, op_num + 1);
3090 /* Unlike the other binary operators, shifts/rotates have
3091 the shift count being int, instead of the same type as
3092 the lhs, so make sure the scalar is the right type if
3093 we are dealing with vectors of
3094 long long/long/short/char. */
3095 if (op_num == 1 && TREE_CODE (op) == INTEGER_CST)
3096 op = fold_convert (TREE_TYPE (vector_type), op);
3097 break;
3099 default:
3100 op = gimple_op (stmt, op_num + 1);
3101 break;
3105 if (reduc_index != -1)
3107 loop = (gimple_bb (stmt))->loop_father;
3108 def_stmt = SSA_NAME_DEF_STMT (op);
3110 gcc_assert (loop);
3112 /* Get the def before the loop. In reduction chain we have only
3113 one initial value. */
3114 if ((j != (number_of_copies - 1)
3115 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt))
3116 && i != 0))
3117 && neutral_op)
3118 op = neutral_op;
3119 else
3120 op = PHI_ARG_DEF_FROM_EDGE (def_stmt,
3121 loop_preheader_edge (loop));
3124 /* Create 'vect_ = {op0,op1,...,opn}'. */
3125 number_of_places_left_in_vector--;
3126 tree orig_op = op;
3127 if (!types_compatible_p (TREE_TYPE (vector_type), TREE_TYPE (op)))
3129 if (CONSTANT_CLASS_P (op))
3131 if (VECTOR_BOOLEAN_TYPE_P (vector_type))
3133 /* Can't use VIEW_CONVERT_EXPR for booleans because
3134 of possibly different sizes of scalar value and
3135 vector element. */
3136 if (integer_zerop (op))
3137 op = build_int_cst (TREE_TYPE (vector_type), 0);
3138 else if (integer_onep (op))
3139 op = build_all_ones_cst (TREE_TYPE (vector_type));
3140 else
3141 gcc_unreachable ();
3143 else
3144 op = fold_unary (VIEW_CONVERT_EXPR,
3145 TREE_TYPE (vector_type), op);
3146 gcc_assert (op && CONSTANT_CLASS_P (op));
3148 else
3150 tree new_temp = make_ssa_name (TREE_TYPE (vector_type));
3151 gimple *init_stmt;
3152 if (VECTOR_BOOLEAN_TYPE_P (vector_type))
3154 tree true_val
3155 = build_all_ones_cst (TREE_TYPE (vector_type));
3156 tree false_val
3157 = build_zero_cst (TREE_TYPE (vector_type));
3158 gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (op)));
3159 init_stmt = gimple_build_assign (new_temp, COND_EXPR,
3160 op, true_val,
3161 false_val);
3163 else
3165 op = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (vector_type),
3166 op);
3167 init_stmt
3168 = gimple_build_assign (new_temp, VIEW_CONVERT_EXPR,
3169 op);
3171 gimple_seq_add_stmt (&ctor_seq, init_stmt);
3172 op = new_temp;
3175 elts[number_of_places_left_in_vector] = op;
3176 if (!CONSTANT_CLASS_P (op))
3177 constant_p = false;
3178 if (TREE_CODE (orig_op) == SSA_NAME
3179 && !SSA_NAME_IS_DEFAULT_DEF (orig_op)
3180 && STMT_VINFO_BB_VINFO (stmt_vinfo)
3181 && (STMT_VINFO_BB_VINFO (stmt_vinfo)->bb
3182 == gimple_bb (SSA_NAME_DEF_STMT (orig_op))))
3183 place_after_defs = true;
3185 if (number_of_places_left_in_vector == 0)
3187 number_of_places_left_in_vector = nunits;
3189 if (constant_p)
3190 vec_cst = build_vector (vector_type, elts);
3191 else
3193 vec<constructor_elt, va_gc> *v;
3194 unsigned k;
3195 vec_alloc (v, nunits);
3196 for (k = 0; k < nunits; ++k)
3197 CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, elts[k]);
3198 vec_cst = build_constructor (vector_type, v);
3200 tree init;
3201 gimple_stmt_iterator gsi;
3202 if (place_after_defs)
3204 gsi = gsi_for_stmt
3205 (vect_find_last_scalar_stmt_in_slp (slp_node));
3206 init = vect_init_vector (stmt, vec_cst, vector_type, &gsi);
3208 else
3209 init = vect_init_vector (stmt, vec_cst, vector_type, NULL);
3210 if (ctor_seq != NULL)
3212 gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (init));
3213 gsi_insert_seq_before_without_update (&gsi, ctor_seq,
3214 GSI_SAME_STMT);
3215 ctor_seq = NULL;
3217 voprnds.quick_push (init);
3218 place_after_defs = false;
3223 /* Since the vectors are created in the reverse order, we should invert
3224 them. */
3225 vec_num = voprnds.length ();
3226 for (j = vec_num; j != 0; j--)
3228 vop = voprnds[j - 1];
3229 vec_oprnds->quick_push (vop);
3232 voprnds.release ();
3234 /* In case that VF is greater than the unrolling factor needed for the SLP
3235 group of stmts, NUMBER_OF_VECTORS to be created is greater than
3236 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
3237 to replicate the vectors. */
3238 while (number_of_vectors > vec_oprnds->length ())
3240 tree neutral_vec = NULL;
3242 if (neutral_op)
3244 if (!neutral_vec)
3245 neutral_vec = build_vector_from_val (vector_type, neutral_op);
3247 vec_oprnds->quick_push (neutral_vec);
3249 else
3251 for (i = 0; vec_oprnds->iterate (i, &vop) && i < vec_num; i++)
3252 vec_oprnds->quick_push (vop);
3258 /* Get vectorized definitions from SLP_NODE that contains corresponding
3259 vectorized def-stmts. */
3261 static void
3262 vect_get_slp_vect_defs (slp_tree slp_node, vec<tree> *vec_oprnds)
3264 tree vec_oprnd;
3265 gimple *vec_def_stmt;
3266 unsigned int i;
3268 gcc_assert (SLP_TREE_VEC_STMTS (slp_node).exists ());
3270 FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (slp_node), i, vec_def_stmt)
3272 gcc_assert (vec_def_stmt);
3273 vec_oprnd = gimple_get_lhs (vec_def_stmt);
3274 vec_oprnds->quick_push (vec_oprnd);
3279 /* Get vectorized definitions for SLP_NODE.
3280 If the scalar definitions are loop invariants or constants, collect them and
3281 call vect_get_constant_vectors() to create vector stmts.
3282 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
3283 must be stored in the corresponding child of SLP_NODE, and we call
3284 vect_get_slp_vect_defs () to retrieve them. */
3286 void
3287 vect_get_slp_defs (vec<tree> ops, slp_tree slp_node,
3288 vec<vec<tree> > *vec_oprnds, int reduc_index)
3290 gimple *first_stmt;
3291 int number_of_vects = 0, i;
3292 HOST_WIDE_INT lhs_size_unit, rhs_size_unit;
3293 slp_tree child = NULL;
3294 vec<tree> vec_defs;
3295 tree oprnd;
3296 bool first_iteration = true;
3298 first_stmt = SLP_TREE_SCALAR_STMTS (slp_node)[0];
3299 FOR_EACH_VEC_ELT (ops, i, oprnd)
3301 bool vectorized_defs = false;
3303 if (oprnd == NULL)
3305 vec_defs = vNULL;
3306 vec_defs.create (0);
3307 vec_oprnds->quick_push (vec_defs);
3308 continue;
3311 /* For each operand we check if it has vectorized definitions in a child
3312 node or we need to create them (for invariants and constants). We
3313 check if the LHS of the first stmt of the next child matches OPRND.
3314 If it does, we found the correct child. Otherwise, we call
3315 vect_get_constant_vectors (). */
3316 for (unsigned int child_index = 0;
3317 child_index < SLP_TREE_CHILDREN (slp_node).length (); child_index++)
3319 child = SLP_TREE_CHILDREN (slp_node)[child_index];
3321 /* We have to check both pattern and original def, if available. */
3322 if (SLP_TREE_DEF_TYPE (child) == vect_internal_def)
3324 gimple *first_def = SLP_TREE_SCALAR_STMTS (child)[0];
3325 gimple *related
3326 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def));
3328 if (operand_equal_p (oprnd, gimple_get_lhs (first_def), 0)
3329 || (related
3330 && operand_equal_p (oprnd, gimple_get_lhs (related), 0)))
3332 /* The number of vector defs is determined by the number of
3333 vector statements in the node from which we get those
3334 statements. */
3335 number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (child);
3336 vectorized_defs = true;
3337 break;
3342 if (!vectorized_defs && first_iteration)
3344 number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
3345 /* Number of vector stmts was calculated according to LHS in
3346 vect_schedule_slp_instance (), fix it by replacing LHS with
3347 RHS, if necessary. See vect_get_smallest_scalar_type () for
3348 details. */
3349 vect_get_smallest_scalar_type (first_stmt, &lhs_size_unit,
3350 &rhs_size_unit);
3351 if (rhs_size_unit != lhs_size_unit)
3353 number_of_vects *= rhs_size_unit;
3354 number_of_vects /= lhs_size_unit;
3358 /* Allocate memory for vectorized defs. */
3359 vec_defs = vNULL;
3360 vec_defs.create (number_of_vects);
3362 /* For reduction defs we call vect_get_constant_vectors (), since we are
3363 looking for initial loop invariant values. */
3364 if (vectorized_defs && reduc_index == -1)
3365 /* The defs are already vectorized. */
3366 vect_get_slp_vect_defs (child, &vec_defs);
3367 else
3368 /* Build vectors from scalar defs. */
3369 vect_get_constant_vectors (oprnd, slp_node, &vec_defs, i,
3370 number_of_vects, reduc_index);
3372 vec_oprnds->quick_push (vec_defs);
3374 /* For reductions, we only need initial values. */
3375 if (reduc_index != -1)
3376 return;
3378 first_iteration = false;
3382 /* Generate vector permute statements from a list of loads in DR_CHAIN.
3383 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
3384 permute statements for the SLP node NODE of the SLP instance
3385 SLP_NODE_INSTANCE. */
3387 bool
3388 vect_transform_slp_perm_load (slp_tree node, vec<tree> dr_chain,
3389 gimple_stmt_iterator *gsi, int vf,
3390 slp_instance slp_node_instance, bool analyze_only,
3391 unsigned *n_perms)
3393 gimple *stmt = SLP_TREE_SCALAR_STMTS (node)[0];
3394 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3395 tree mask_element_type = NULL_TREE, mask_type;
3396 int nunits, vec_index = 0;
3397 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
3398 int group_size = SLP_INSTANCE_GROUP_SIZE (slp_node_instance);
3399 int mask_element;
3400 unsigned char *mask;
3401 machine_mode mode;
3403 if (!STMT_VINFO_GROUPED_ACCESS (stmt_info))
3404 return false;
3406 stmt_info = vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info));
3408 mode = TYPE_MODE (vectype);
3410 /* The generic VEC_PERM_EXPR code always uses an integral type of the
3411 same size as the vector element being permuted. */
3412 mask_element_type = lang_hooks.types.type_for_mode
3413 (int_mode_for_mode (TYPE_MODE (TREE_TYPE (vectype))), 1);
3414 mask_type = get_vectype_for_scalar_type (mask_element_type);
3415 nunits = TYPE_VECTOR_SUBPARTS (vectype);
3416 mask = XALLOCAVEC (unsigned char, nunits);
3418 /* Initialize the vect stmts of NODE to properly insert the generated
3419 stmts later. */
3420 if (! analyze_only)
3421 for (unsigned i = SLP_TREE_VEC_STMTS (node).length ();
3422 i < SLP_TREE_NUMBER_OF_VEC_STMTS (node); i++)
3423 SLP_TREE_VEC_STMTS (node).quick_push (NULL);
3425 /* Generate permutation masks for every NODE. Number of masks for each NODE
3426 is equal to GROUP_SIZE.
3427 E.g., we have a group of three nodes with three loads from the same
3428 location in each node, and the vector size is 4. I.e., we have a
3429 a0b0c0a1b1c1... sequence and we need to create the following vectors:
3430 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
3431 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
3434 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9}.
3435 The last mask is illegal since we assume two operands for permute
3436 operation, and the mask element values can't be outside that range.
3437 Hence, the last mask must be converted into {2,5,5,5}.
3438 For the first two permutations we need the first and the second input
3439 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
3440 we need the second and the third vectors: {b1,c1,a2,b2} and
3441 {c2,a3,b3,c3}. */
3443 int vect_stmts_counter = 0;
3444 int index = 0;
3445 int first_vec_index = -1;
3446 int second_vec_index = -1;
3447 bool noop_p = true;
3448 *n_perms = 0;
3450 for (int j = 0; j < vf; j++)
3452 for (int k = 0; k < group_size; k++)
3454 int i = (SLP_TREE_LOAD_PERMUTATION (node)[k]
3455 + j * STMT_VINFO_GROUP_SIZE (stmt_info));
3456 vec_index = i / nunits;
3457 mask_element = i % nunits;
3458 if (vec_index == first_vec_index
3459 || first_vec_index == -1)
3461 first_vec_index = vec_index;
3463 else if (vec_index == second_vec_index
3464 || second_vec_index == -1)
3466 second_vec_index = vec_index;
3467 mask_element += nunits;
3469 else
3471 if (dump_enabled_p ())
3473 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3474 "permutation requires at "
3475 "least three vectors ");
3476 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
3477 stmt, 0);
3479 return false;
3482 gcc_assert (mask_element >= 0
3483 && mask_element < 2 * nunits);
3484 if (mask_element != index)
3485 noop_p = false;
3486 mask[index++] = mask_element;
3488 if (index == nunits)
3490 if (! noop_p
3491 && ! can_vec_perm_p (mode, false, mask))
3493 if (dump_enabled_p ())
3495 dump_printf_loc (MSG_MISSED_OPTIMIZATION,
3496 vect_location,
3497 "unsupported vect permute { ");
3498 for (i = 0; i < nunits; ++i)
3499 dump_printf (MSG_MISSED_OPTIMIZATION, "%d ", mask[i]);
3500 dump_printf (MSG_MISSED_OPTIMIZATION, "}\n");
3502 return false;
3505 if (! noop_p)
3506 ++*n_perms;
3508 if (!analyze_only)
3510 tree mask_vec = NULL_TREE;
3512 if (! noop_p)
3514 tree *mask_elts = XALLOCAVEC (tree, nunits);
3515 for (int l = 0; l < nunits; ++l)
3516 mask_elts[l] = build_int_cst (mask_element_type,
3517 mask[l]);
3518 mask_vec = build_vector (mask_type, mask_elts);
3521 if (second_vec_index == -1)
3522 second_vec_index = first_vec_index;
3524 /* Generate the permute statement if necessary. */
3525 tree first_vec = dr_chain[first_vec_index];
3526 tree second_vec = dr_chain[second_vec_index];
3527 gimple *perm_stmt;
3528 if (! noop_p)
3530 tree perm_dest
3531 = vect_create_destination_var (gimple_assign_lhs (stmt),
3532 vectype);
3533 perm_dest = make_ssa_name (perm_dest);
3534 perm_stmt = gimple_build_assign (perm_dest,
3535 VEC_PERM_EXPR,
3536 first_vec, second_vec,
3537 mask_vec);
3538 vect_finish_stmt_generation (stmt, perm_stmt, gsi);
3540 else
3541 /* If mask was NULL_TREE generate the requested
3542 identity transform. */
3543 perm_stmt = SSA_NAME_DEF_STMT (first_vec);
3545 /* Store the vector statement in NODE. */
3546 SLP_TREE_VEC_STMTS (node)[vect_stmts_counter++] = perm_stmt;
3549 index = 0;
3550 first_vec_index = -1;
3551 second_vec_index = -1;
3552 noop_p = true;
3557 return true;
3562 /* Vectorize SLP instance tree in postorder. */
3564 static bool
3565 vect_schedule_slp_instance (slp_tree node, slp_instance instance,
3566 unsigned int vectorization_factor)
3568 gimple *stmt;
3569 bool grouped_store, is_store;
3570 gimple_stmt_iterator si;
3571 stmt_vec_info stmt_info;
3572 unsigned int vec_stmts_size, nunits, group_size;
3573 tree vectype;
3574 int i, j;
3575 slp_tree child;
3577 if (SLP_TREE_DEF_TYPE (node) != vect_internal_def)
3578 return false;
3580 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
3581 vect_schedule_slp_instance (child, instance, vectorization_factor);
3583 /* Push SLP node def-type to stmts. */
3584 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
3585 if (SLP_TREE_DEF_TYPE (child) != vect_internal_def)
3586 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child), j, stmt)
3587 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt)) = SLP_TREE_DEF_TYPE (child);
3589 stmt = SLP_TREE_SCALAR_STMTS (node)[0];
3590 stmt_info = vinfo_for_stmt (stmt);
3592 /* VECTYPE is the type of the destination. */
3593 vectype = STMT_VINFO_VECTYPE (stmt_info);
3594 nunits = (unsigned int) TYPE_VECTOR_SUBPARTS (vectype);
3595 group_size = SLP_INSTANCE_GROUP_SIZE (instance);
3597 /* For each SLP instance calculate number of vector stmts to be created
3598 for the scalar stmts in each node of the SLP tree. Number of vector
3599 elements in one vector iteration is the number of scalar elements in
3600 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
3601 size.
3602 Unless this is a SLP reduction in which case the number of vector
3603 stmts is equal to the number of vector stmts of the children. */
3604 if (GROUP_FIRST_ELEMENT (stmt_info)
3605 && !STMT_VINFO_GROUPED_ACCESS (stmt_info))
3606 vec_stmts_size = SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_CHILDREN (node)[0]);
3607 else
3608 vec_stmts_size = (vectorization_factor * group_size) / nunits;
3610 if (!SLP_TREE_VEC_STMTS (node).exists ())
3612 SLP_TREE_VEC_STMTS (node).create (vec_stmts_size);
3613 SLP_TREE_NUMBER_OF_VEC_STMTS (node) = vec_stmts_size;
3616 if (dump_enabled_p ())
3618 dump_printf_loc (MSG_NOTE,vect_location,
3619 "------>vectorizing SLP node starting from: ");
3620 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
3623 /* Vectorized stmts go before the last scalar stmt which is where
3624 all uses are ready. */
3625 si = gsi_for_stmt (vect_find_last_scalar_stmt_in_slp (node));
3627 /* Mark the first element of the reduction chain as reduction to properly
3628 transform the node. In the analysis phase only the last element of the
3629 chain is marked as reduction. */
3630 if (GROUP_FIRST_ELEMENT (stmt_info) && !STMT_VINFO_GROUPED_ACCESS (stmt_info)
3631 && GROUP_FIRST_ELEMENT (stmt_info) == stmt)
3633 STMT_VINFO_DEF_TYPE (stmt_info) = vect_reduction_def;
3634 STMT_VINFO_TYPE (stmt_info) = reduc_vec_info_type;
3637 /* Handle two-operation SLP nodes by vectorizing the group with
3638 both operations and then performing a merge. */
3639 if (SLP_TREE_TWO_OPERATORS (node))
3641 enum tree_code code0 = gimple_assign_rhs_code (stmt);
3642 enum tree_code ocode = ERROR_MARK;
3643 gimple *ostmt;
3644 unsigned char *mask = XALLOCAVEC (unsigned char, group_size);
3645 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, ostmt)
3646 if (gimple_assign_rhs_code (ostmt) != code0)
3648 mask[i] = 1;
3649 ocode = gimple_assign_rhs_code (ostmt);
3651 else
3652 mask[i] = 0;
3653 if (ocode != ERROR_MARK)
3655 vec<gimple *> v0;
3656 vec<gimple *> v1;
3657 unsigned j;
3658 tree tmask = NULL_TREE;
3659 vect_transform_stmt (stmt, &si, &grouped_store, node, instance);
3660 v0 = SLP_TREE_VEC_STMTS (node).copy ();
3661 SLP_TREE_VEC_STMTS (node).truncate (0);
3662 gimple_assign_set_rhs_code (stmt, ocode);
3663 vect_transform_stmt (stmt, &si, &grouped_store, node, instance);
3664 gimple_assign_set_rhs_code (stmt, code0);
3665 v1 = SLP_TREE_VEC_STMTS (node).copy ();
3666 SLP_TREE_VEC_STMTS (node).truncate (0);
3667 tree meltype = build_nonstandard_integer_type
3668 (GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (vectype))), 1);
3669 tree mvectype = get_same_sized_vectype (meltype, vectype);
3670 unsigned k = 0, l;
3671 for (j = 0; j < v0.length (); ++j)
3673 tree *melts = XALLOCAVEC (tree, TYPE_VECTOR_SUBPARTS (vectype));
3674 for (l = 0; l < TYPE_VECTOR_SUBPARTS (vectype); ++l)
3676 if (k >= group_size)
3677 k = 0;
3678 melts[l] = build_int_cst
3679 (meltype, mask[k++] * TYPE_VECTOR_SUBPARTS (vectype) + l);
3681 tmask = build_vector (mvectype, melts);
3683 /* ??? Not all targets support a VEC_PERM_EXPR with a
3684 constant mask that would translate to a vec_merge RTX
3685 (with their vec_perm_const_ok). We can either not
3686 vectorize in that case or let veclower do its job.
3687 Unfortunately that isn't too great and at least for
3688 plus/minus we'd eventually like to match targets
3689 vector addsub instructions. */
3690 gimple *vstmt;
3691 vstmt = gimple_build_assign (make_ssa_name (vectype),
3692 VEC_PERM_EXPR,
3693 gimple_assign_lhs (v0[j]),
3694 gimple_assign_lhs (v1[j]), tmask);
3695 vect_finish_stmt_generation (stmt, vstmt, &si);
3696 SLP_TREE_VEC_STMTS (node).quick_push (vstmt);
3698 v0.release ();
3699 v1.release ();
3700 return false;
3703 is_store = vect_transform_stmt (stmt, &si, &grouped_store, node, instance);
3705 /* Restore stmt def-types. */
3706 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
3707 if (SLP_TREE_DEF_TYPE (child) != vect_internal_def)
3708 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (child), j, stmt)
3709 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt)) = vect_internal_def;
3711 return is_store;
3714 /* Replace scalar calls from SLP node NODE with setting of their lhs to zero.
3715 For loop vectorization this is done in vectorizable_call, but for SLP
3716 it needs to be deferred until end of vect_schedule_slp, because multiple
3717 SLP instances may refer to the same scalar stmt. */
3719 static void
3720 vect_remove_slp_scalar_calls (slp_tree node)
3722 gimple *stmt, *new_stmt;
3723 gimple_stmt_iterator gsi;
3724 int i;
3725 slp_tree child;
3726 tree lhs;
3727 stmt_vec_info stmt_info;
3729 if (SLP_TREE_DEF_TYPE (node) != vect_internal_def)
3730 return;
3732 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
3733 vect_remove_slp_scalar_calls (child);
3735 FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
3737 if (!is_gimple_call (stmt) || gimple_bb (stmt) == NULL)
3738 continue;
3739 stmt_info = vinfo_for_stmt (stmt);
3740 if (stmt_info == NULL
3741 || is_pattern_stmt_p (stmt_info)
3742 || !PURE_SLP_STMT (stmt_info))
3743 continue;
3744 lhs = gimple_call_lhs (stmt);
3745 new_stmt = gimple_build_assign (lhs, build_zero_cst (TREE_TYPE (lhs)));
3746 set_vinfo_for_stmt (new_stmt, stmt_info);
3747 set_vinfo_for_stmt (stmt, NULL);
3748 STMT_VINFO_STMT (stmt_info) = new_stmt;
3749 gsi = gsi_for_stmt (stmt);
3750 gsi_replace (&gsi, new_stmt, false);
3751 SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt)) = new_stmt;
3755 /* Generate vector code for all SLP instances in the loop/basic block. */
3757 bool
3758 vect_schedule_slp (vec_info *vinfo)
3760 vec<slp_instance> slp_instances;
3761 slp_instance instance;
3762 unsigned int i, vf;
3763 bool is_store = false;
3765 slp_instances = vinfo->slp_instances;
3766 if (is_a <loop_vec_info> (vinfo))
3767 vf = as_a <loop_vec_info> (vinfo)->vectorization_factor;
3768 else
3769 vf = 1;
3771 FOR_EACH_VEC_ELT (slp_instances, i, instance)
3773 /* Schedule the tree of INSTANCE. */
3774 is_store = vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance),
3775 instance, vf);
3776 if (dump_enabled_p ())
3777 dump_printf_loc (MSG_NOTE, vect_location,
3778 "vectorizing stmts using SLP.\n");
3781 FOR_EACH_VEC_ELT (slp_instances, i, instance)
3783 slp_tree root = SLP_INSTANCE_TREE (instance);
3784 gimple *store;
3785 unsigned int j;
3786 gimple_stmt_iterator gsi;
3788 /* Remove scalar call stmts. Do not do this for basic-block
3789 vectorization as not all uses may be vectorized.
3790 ??? Why should this be necessary? DCE should be able to
3791 remove the stmts itself.
3792 ??? For BB vectorization we can as well remove scalar
3793 stmts starting from the SLP tree root if they have no
3794 uses. */
3795 if (is_a <loop_vec_info> (vinfo))
3796 vect_remove_slp_scalar_calls (root);
3798 for (j = 0; SLP_TREE_SCALAR_STMTS (root).iterate (j, &store)
3799 && j < SLP_INSTANCE_GROUP_SIZE (instance); j++)
3801 if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store)))
3802 break;
3804 if (is_pattern_stmt_p (vinfo_for_stmt (store)))
3805 store = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (store));
3806 /* Free the attached stmt_vec_info and remove the stmt. */
3807 gsi = gsi_for_stmt (store);
3808 unlink_stmt_vdef (store);
3809 gsi_remove (&gsi, true);
3810 release_defs (store);
3811 free_stmt_vec_info (store);
3815 return is_store;