1 /* Data References Analysis and Manipulation Utilities for Vectorization.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
4 and Ira Rosen <irar@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
31 #include "basic-block.h"
32 #include "gimple-pretty-print.h"
33 #include "tree-flow.h"
36 #include "tree-chrec.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-vectorizer.h"
39 #include "diagnostic-core.h"
41 /* Need to include rtl.h, expr.h, etc. for optabs. */
45 /* Return true if load- or store-lanes optab OPTAB is implemented for
46 COUNT vectors of type VECTYPE. NAME is the name of OPTAB. */
49 vect_lanes_optab_supported_p (const char *name, convert_optab optab,
50 tree vectype, unsigned HOST_WIDE_INT count)
52 enum machine_mode mode, array_mode;
55 mode = TYPE_MODE (vectype);
56 limit_p = !targetm.array_mode_supported_p (mode, count);
57 array_mode = mode_for_size (count * GET_MODE_BITSIZE (mode),
60 if (array_mode == BLKmode)
62 if (dump_enabled_p ())
63 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
64 "no array mode for %s[" HOST_WIDE_INT_PRINT_DEC "]",
65 GET_MODE_NAME (mode), count);
69 if (convert_optab_handler (optab, array_mode, mode) == CODE_FOR_nothing)
71 if (dump_enabled_p ())
72 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
73 "cannot use %s<%s><%s>", name,
74 GET_MODE_NAME (array_mode), GET_MODE_NAME (mode));
78 if (dump_enabled_p ())
79 dump_printf_loc (MSG_NOTE, vect_location,
80 "can use %s<%s><%s>", name, GET_MODE_NAME (array_mode),
81 GET_MODE_NAME (mode));
87 /* Return the smallest scalar part of STMT.
88 This is used to determine the vectype of the stmt. We generally set the
89 vectype according to the type of the result (lhs). For stmts whose
90 result-type is different than the type of the arguments (e.g., demotion,
91 promotion), vectype will be reset appropriately (later). Note that we have
92 to visit the smallest datatype in this function, because that determines the
93 VF. If the smallest datatype in the loop is present only as the rhs of a
94 promotion operation - we'd miss it.
95 Such a case, where a variable of this datatype does not appear in the lhs
96 anywhere in the loop, can only occur if it's an invariant: e.g.:
97 'int_x = (int) short_inv', which we'd expect to have been optimized away by
98 invariant motion. However, we cannot rely on invariant motion to always
99 take invariants out of the loop, and so in the case of promotion we also
100 have to check the rhs.
101 LHS_SIZE_UNIT and RHS_SIZE_UNIT contain the sizes of the corresponding
105 vect_get_smallest_scalar_type (gimple stmt, HOST_WIDE_INT *lhs_size_unit,
106 HOST_WIDE_INT *rhs_size_unit)
108 tree scalar_type = gimple_expr_type (stmt);
109 HOST_WIDE_INT lhs, rhs;
111 lhs = rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
113 if (is_gimple_assign (stmt)
114 && (gimple_assign_cast_p (stmt)
115 || gimple_assign_rhs_code (stmt) == WIDEN_MULT_EXPR
116 || gimple_assign_rhs_code (stmt) == WIDEN_LSHIFT_EXPR
117 || gimple_assign_rhs_code (stmt) == FLOAT_EXPR))
119 tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
121 rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (rhs_type));
123 scalar_type = rhs_type;
126 *lhs_size_unit = lhs;
127 *rhs_size_unit = rhs;
132 /* Find the place of the data-ref in STMT in the interleaving chain that starts
133 from FIRST_STMT. Return -1 if the data-ref is not a part of the chain. */
136 vect_get_place_in_interleaving_chain (gimple stmt, gimple first_stmt)
138 gimple next_stmt = first_stmt;
141 if (first_stmt != GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
144 while (next_stmt && next_stmt != stmt)
147 next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
157 /* Function vect_insert_into_interleaving_chain.
159 Insert DRA into the interleaving chain of DRB according to DRA's INIT. */
162 vect_insert_into_interleaving_chain (struct data_reference *dra,
163 struct data_reference *drb)
167 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
168 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
170 prev = GROUP_FIRST_ELEMENT (stmtinfo_b);
171 next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
174 next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
175 if (tree_int_cst_compare (next_init, DR_INIT (dra)) > 0)
178 GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = DR_STMT (dra);
179 GROUP_NEXT_ELEMENT (stmtinfo_a) = next;
183 next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
186 /* We got to the end of the list. Insert here. */
187 GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = DR_STMT (dra);
188 GROUP_NEXT_ELEMENT (stmtinfo_a) = NULL;
192 /* Function vect_update_interleaving_chain.
194 For two data-refs DRA and DRB that are a part of a chain interleaved data
195 accesses, update the interleaving chain. DRB's INIT is smaller than DRA's.
197 There are four possible cases:
198 1. New stmts - both DRA and DRB are not a part of any chain:
201 2. DRB is a part of a chain and DRA is not:
202 no need to update FIRST_DR
203 no need to insert DRB
204 insert DRA according to init
205 3. DRA is a part of a chain and DRB is not:
206 if (init of FIRST_DR > init of DRB)
208 NEXT(FIRST_DR) = previous FIRST_DR
210 insert DRB according to its init
211 4. both DRA and DRB are in some interleaving chains:
212 choose the chain with the smallest init of FIRST_DR
213 insert the nodes of the second chain into the first one. */
216 vect_update_interleaving_chain (struct data_reference *drb,
217 struct data_reference *dra)
219 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
220 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
221 tree next_init, init_dra_chain, init_drb_chain;
222 gimple first_a, first_b;
224 gimple node, prev, next, first_stmt;
226 /* 1. New stmts - both DRA and DRB are not a part of any chain. */
227 if (!GROUP_FIRST_ELEMENT (stmtinfo_a) && !GROUP_FIRST_ELEMENT (stmtinfo_b))
229 GROUP_FIRST_ELEMENT (stmtinfo_a) = DR_STMT (drb);
230 GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (drb);
231 GROUP_NEXT_ELEMENT (stmtinfo_b) = DR_STMT (dra);
235 /* 2. DRB is a part of a chain and DRA is not. */
236 if (!GROUP_FIRST_ELEMENT (stmtinfo_a) && GROUP_FIRST_ELEMENT (stmtinfo_b))
238 GROUP_FIRST_ELEMENT (stmtinfo_a) = GROUP_FIRST_ELEMENT (stmtinfo_b);
239 /* Insert DRA into the chain of DRB. */
240 vect_insert_into_interleaving_chain (dra, drb);
244 /* 3. DRA is a part of a chain and DRB is not. */
245 if (GROUP_FIRST_ELEMENT (stmtinfo_a) && !GROUP_FIRST_ELEMENT (stmtinfo_b))
247 gimple old_first_stmt = GROUP_FIRST_ELEMENT (stmtinfo_a);
248 tree init_old = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (
252 if (tree_int_cst_compare (init_old, DR_INIT (drb)) > 0)
254 /* DRB's init is smaller than the init of the stmt previously marked
255 as the first stmt of the interleaving chain of DRA. Therefore, we
256 update FIRST_STMT and put DRB in the head of the list. */
257 GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (drb);
258 GROUP_NEXT_ELEMENT (stmtinfo_b) = old_first_stmt;
260 /* Update all the stmts in the list to point to the new FIRST_STMT. */
261 tmp = old_first_stmt;
264 GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp)) = DR_STMT (drb);
265 tmp = GROUP_NEXT_ELEMENT (vinfo_for_stmt (tmp));
270 /* Insert DRB in the list of DRA. */
271 vect_insert_into_interleaving_chain (drb, dra);
272 GROUP_FIRST_ELEMENT (stmtinfo_b) = GROUP_FIRST_ELEMENT (stmtinfo_a);
277 /* 4. both DRA and DRB are in some interleaving chains. */
278 first_a = GROUP_FIRST_ELEMENT (stmtinfo_a);
279 first_b = GROUP_FIRST_ELEMENT (stmtinfo_b);
280 if (first_a == first_b)
282 init_dra_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_a)));
283 init_drb_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_b)));
285 if (tree_int_cst_compare (init_dra_chain, init_drb_chain) > 0)
287 /* Insert the nodes of DRA chain into the DRB chain.
288 After inserting a node, continue from this node of the DRB chain (don't
289 start from the beginning. */
290 node = GROUP_FIRST_ELEMENT (stmtinfo_a);
291 prev = GROUP_FIRST_ELEMENT (stmtinfo_b);
292 first_stmt = first_b;
296 /* Insert the nodes of DRB chain into the DRA chain.
297 After inserting a node, continue from this node of the DRA chain (don't
298 start from the beginning. */
299 node = GROUP_FIRST_ELEMENT (stmtinfo_b);
300 prev = GROUP_FIRST_ELEMENT (stmtinfo_a);
301 first_stmt = first_a;
306 node_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (node)));
307 next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
310 next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
311 if (tree_int_cst_compare (next_init, node_init) > 0)
314 GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = node;
315 GROUP_NEXT_ELEMENT (vinfo_for_stmt (node)) = next;
320 next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
324 /* We got to the end of the list. Insert here. */
325 GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = node;
326 GROUP_NEXT_ELEMENT (vinfo_for_stmt (node)) = NULL;
329 GROUP_FIRST_ELEMENT (vinfo_for_stmt (node)) = first_stmt;
330 node = GROUP_NEXT_ELEMENT (vinfo_for_stmt (node));
334 /* Check dependence between DRA and DRB for basic block vectorization.
335 If the accesses share same bases and offsets, we can compare their initial
336 constant offsets to decide whether they differ or not. In case of a read-
337 write dependence we check that the load is before the store to ensure that
338 vectorization will not change the order of the accesses. */
341 vect_drs_dependent_in_basic_block (struct data_reference *dra,
342 struct data_reference *drb)
344 HOST_WIDE_INT type_size_a, type_size_b, init_a, init_b;
347 /* We only call this function for pairs of loads and stores, but we verify
349 if (DR_IS_READ (dra) == DR_IS_READ (drb))
351 if (DR_IS_READ (dra))
357 /* Check that the data-refs have same bases and offsets. If not, we can't
358 determine if they are dependent. */
359 if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
360 || !dr_equal_offsets_p (dra, drb))
363 /* Check the types. */
364 type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
365 type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
367 if (type_size_a != type_size_b
368 || !types_compatible_p (TREE_TYPE (DR_REF (dra)),
369 TREE_TYPE (DR_REF (drb))))
372 init_a = TREE_INT_CST_LOW (DR_INIT (dra));
373 init_b = TREE_INT_CST_LOW (DR_INIT (drb));
375 /* Two different locations - no dependence. */
376 if (init_a != init_b)
379 /* We have a read-write dependence. Check that the load is before the store.
380 When we vectorize basic blocks, vector load can be only before
381 corresponding scalar load, and vector store can be only after its
382 corresponding scalar store. So the order of the acceses is preserved in
383 case the load is before the store. */
384 earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
385 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
392 /* Function vect_check_interleaving.
394 Check if DRA and DRB are a part of interleaving. In case they are, insert
395 DRA and DRB in an interleaving chain. */
398 vect_check_interleaving (struct data_reference *dra,
399 struct data_reference *drb)
401 HOST_WIDE_INT type_size_a, type_size_b, diff_mod_size, step, init_a, init_b;
403 /* Check that the data-refs have same first location (except init) and they
404 are both either store or load (not load and store). */
405 if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
406 || !dr_equal_offsets_p (dra, drb)
407 || !tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb))
408 || DR_IS_READ (dra) != DR_IS_READ (drb))
412 1. data-refs are of the same type
413 2. their steps are equal
414 3. the step (if greater than zero) is greater than the difference between
416 type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
417 type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
419 if (type_size_a != type_size_b
420 || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb))
421 || !types_compatible_p (TREE_TYPE (DR_REF (dra)),
422 TREE_TYPE (DR_REF (drb))))
425 init_a = TREE_INT_CST_LOW (DR_INIT (dra));
426 init_b = TREE_INT_CST_LOW (DR_INIT (drb));
427 step = TREE_INT_CST_LOW (DR_STEP (dra));
431 /* If init_a == init_b + the size of the type * k, we have an interleaving,
432 and DRB is accessed before DRA. */
433 diff_mod_size = (init_a - init_b) % type_size_a;
435 if (step && (init_a - init_b) > step)
438 if (diff_mod_size == 0)
440 vect_update_interleaving_chain (drb, dra);
441 if (dump_enabled_p ())
443 dump_printf_loc (MSG_NOTE, vect_location,
444 "Detected interleaving ");
445 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
446 dump_printf (MSG_NOTE, " and ");
447 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
454 /* If init_b == init_a + the size of the type * k, we have an
455 interleaving, and DRA is accessed before DRB. */
456 diff_mod_size = (init_b - init_a) % type_size_a;
458 if (step && (init_b - init_a) > step)
461 if (diff_mod_size == 0)
463 vect_update_interleaving_chain (dra, drb);
464 if (dump_enabled_p ())
466 dump_printf_loc (MSG_NOTE, vect_location,
467 "Detected interleaving ");
468 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
469 dump_printf (MSG_NOTE, " and ");
470 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
479 /* Check if data references pointed by DR_I and DR_J are same or
480 belong to same interleaving group. Return FALSE if drs are
481 different, otherwise return TRUE. */
484 vect_same_range_drs (data_reference_p dr_i, data_reference_p dr_j)
486 gimple stmt_i = DR_STMT (dr_i);
487 gimple stmt_j = DR_STMT (dr_j);
489 if (operand_equal_p (DR_REF (dr_i), DR_REF (dr_j), 0)
490 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_i))
491 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_j))
492 && (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_i))
493 == GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_j)))))
499 /* If address ranges represented by DDR_I and DDR_J are equal,
500 return TRUE, otherwise return FALSE. */
503 vect_vfa_range_equal (ddr_p ddr_i, ddr_p ddr_j)
505 if ((vect_same_range_drs (DDR_A (ddr_i), DDR_A (ddr_j))
506 && vect_same_range_drs (DDR_B (ddr_i), DDR_B (ddr_j)))
507 || (vect_same_range_drs (DDR_A (ddr_i), DDR_B (ddr_j))
508 && vect_same_range_drs (DDR_B (ddr_i), DDR_A (ddr_j))))
514 /* Insert DDR into LOOP_VINFO list of ddrs that may alias and need to be
515 tested at run-time. Return TRUE if DDR was successfully inserted.
516 Return false if versioning is not supported. */
519 vect_mark_for_runtime_alias_test (ddr_p ddr, loop_vec_info loop_vinfo)
521 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
523 if ((unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS) == 0)
526 if (dump_enabled_p ())
528 dump_printf_loc (MSG_NOTE, vect_location,
529 "mark for run-time aliasing test between ");
530 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_A (ddr)));
531 dump_printf (MSG_NOTE, " and ");
532 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_B (ddr)));
535 if (optimize_loop_nest_for_size_p (loop))
537 if (dump_enabled_p ())
538 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
539 "versioning not supported when optimizing for size.");
543 /* FORNOW: We don't support versioning with outer-loop vectorization. */
546 if (dump_enabled_p ())
547 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
548 "versioning not yet supported for outer-loops.");
552 /* FORNOW: We don't support creating runtime alias tests for non-constant
554 if (TREE_CODE (DR_STEP (DDR_A (ddr))) != INTEGER_CST
555 || TREE_CODE (DR_STEP (DDR_B (ddr))) != INTEGER_CST)
557 if (dump_enabled_p ())
558 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
559 "versioning not yet supported for non-constant "
564 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo).safe_push (ddr);
569 /* Function vect_analyze_data_ref_dependence.
571 Return TRUE if there (might) exist a dependence between a memory-reference
572 DRA and a memory-reference DRB. When versioning for alias may check a
573 dependence at run-time, return FALSE. Adjust *MAX_VF according to
574 the data dependence. */
577 vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr,
578 loop_vec_info loop_vinfo, int *max_vf)
581 struct loop *loop = NULL;
582 struct data_reference *dra = DDR_A (ddr);
583 struct data_reference *drb = DDR_B (ddr);
584 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
585 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
586 lambda_vector dist_v;
587 unsigned int loop_depth;
589 /* Don't bother to analyze statements marked as unvectorizable. */
590 if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a)
591 || !STMT_VINFO_VECTORIZABLE (stmtinfo_b))
594 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
596 /* Independent data accesses. */
597 vect_check_interleaving (dra, drb);
602 loop = LOOP_VINFO_LOOP (loop_vinfo);
604 if ((DR_IS_READ (dra) && DR_IS_READ (drb) && loop_vinfo) || dra == drb)
607 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
613 if (dump_enabled_p ())
615 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
616 "versioning for alias required: "
617 "can't determine dependence between ");
618 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
620 dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
621 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
625 /* Add to list of ddrs that need to be tested at run-time. */
626 return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
629 /* When vectorizing a basic block unknown depnedence can still mean
631 if (vect_check_interleaving (dra, drb))
634 /* Read-read is OK (we need this check here, after checking for
636 if (DR_IS_READ (dra) && DR_IS_READ (drb))
639 if (dump_enabled_p ())
641 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
642 "can't determine dependence between ");
643 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dra));
644 dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
645 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (drb));
648 /* We do not vectorize basic blocks with write-write dependencies. */
649 if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
652 /* Check that it's not a load-after-store dependence. */
653 earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
654 if (DR_IS_WRITE (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
660 /* Versioning for alias is not yet supported for basic block SLP, and
661 dependence distance is unapplicable, hence, in case of known data
662 dependence, basic block vectorization is impossible for now. */
665 if (dra != drb && vect_check_interleaving (dra, drb))
668 if (dump_enabled_p ())
670 dump_printf_loc (MSG_NOTE, vect_location,
671 "determined dependence between ");
672 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
673 dump_printf (MSG_NOTE, " and ");
674 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
677 /* Do not vectorize basic blcoks with write-write dependences. */
678 if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
681 /* Check if this dependence is allowed in basic block vectorization. */
682 return vect_drs_dependent_in_basic_block (dra, drb);
685 /* Loop-based vectorization and known data dependence. */
686 if (DDR_NUM_DIST_VECTS (ddr) == 0)
688 if (dump_enabled_p ())
690 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
691 "versioning for alias required: "
692 "bad dist vector for ");
693 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dra));
694 dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
695 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (drb));
697 /* Add to list of ddrs that need to be tested at run-time. */
698 return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
701 loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
702 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
704 int dist = dist_v[loop_depth];
706 if (dump_enabled_p ())
707 dump_printf_loc (MSG_NOTE, vect_location,
708 "dependence distance = %d.", dist);
712 if (dump_enabled_p ())
714 dump_printf_loc (MSG_NOTE, vect_location,
715 "dependence distance == 0 between ");
716 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
717 dump_printf (MSG_NOTE, " and ");
718 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
721 /* For interleaving, mark that there is a read-write dependency if
722 necessary. We check before that one of the data-refs is store. */
723 if (DR_IS_READ (dra))
724 GROUP_READ_WRITE_DEPENDENCE (stmtinfo_a) = true;
727 if (DR_IS_READ (drb))
728 GROUP_READ_WRITE_DEPENDENCE (stmtinfo_b) = true;
734 if (dist > 0 && DDR_REVERSED_P (ddr))
736 /* If DDR_REVERSED_P the order of the data-refs in DDR was
737 reversed (to make distance vector positive), and the actual
738 distance is negative. */
739 if (dump_enabled_p ())
740 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
741 "dependence distance negative.");
746 && abs (dist) < *max_vf)
748 /* The dependence distance requires reduction of the maximal
749 vectorization factor. */
750 *max_vf = abs (dist);
751 if (dump_enabled_p ())
752 dump_printf_loc (MSG_NOTE, vect_location,
753 "adjusting maximal vectorization factor to %i",
757 if (abs (dist) >= *max_vf)
759 /* Dependence distance does not create dependence, as far as
760 vectorization is concerned, in this case. */
761 if (dump_enabled_p ())
762 dump_printf_loc (MSG_NOTE, vect_location,
763 "dependence distance >= VF.");
767 if (dump_enabled_p ())
769 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
770 "not vectorized, possible dependence "
771 "between data-refs ");
772 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
773 dump_printf (MSG_NOTE, " and ");
774 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
783 /* Function vect_analyze_data_ref_dependences.
785 Examine all the data references in the loop, and make sure there do not
786 exist any data dependences between them. Set *MAX_VF according to
787 the maximum vectorization factor the data dependences allow. */
790 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo,
791 bb_vec_info bb_vinfo, int *max_vf)
794 vec<ddr_p> ddrs = vNULL;
795 struct data_dependence_relation *ddr;
797 if (dump_enabled_p ())
798 dump_printf_loc (MSG_NOTE, vect_location,
799 "=== vect_analyze_dependences ===");
801 ddrs = LOOP_VINFO_DDRS (loop_vinfo);
803 ddrs = BB_VINFO_DDRS (bb_vinfo);
805 FOR_EACH_VEC_ELT (ddrs, i, ddr)
806 if (vect_analyze_data_ref_dependence (ddr, loop_vinfo, max_vf))
813 /* Function vect_compute_data_ref_alignment
815 Compute the misalignment of the data reference DR.
818 1. If during the misalignment computation it is found that the data reference
819 cannot be vectorized then false is returned.
820 2. DR_MISALIGNMENT (DR) is defined.
822 FOR NOW: No analysis is actually performed. Misalignment is calculated
823 only for trivial cases. TODO. */
826 vect_compute_data_ref_alignment (struct data_reference *dr)
828 gimple stmt = DR_STMT (dr);
829 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
830 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
831 struct loop *loop = NULL;
832 tree ref = DR_REF (dr);
834 tree base, base_addr;
837 tree aligned_to, alignment;
839 if (dump_enabled_p ())
840 dump_printf_loc (MSG_NOTE, vect_location,
841 "vect_compute_data_ref_alignment:");
844 loop = LOOP_VINFO_LOOP (loop_vinfo);
846 /* Initialize misalignment to unknown. */
847 SET_DR_MISALIGNMENT (dr, -1);
849 /* Strided loads perform only component accesses, misalignment information
850 is irrelevant for them. */
851 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
854 misalign = DR_INIT (dr);
855 aligned_to = DR_ALIGNED_TO (dr);
856 base_addr = DR_BASE_ADDRESS (dr);
857 vectype = STMT_VINFO_VECTYPE (stmt_info);
859 /* In case the dataref is in an inner-loop of the loop that is being
860 vectorized (LOOP), we use the base and misalignment information
861 relative to the outer-loop (LOOP). This is ok only if the misalignment
862 stays the same throughout the execution of the inner-loop, which is why
863 we have to check that the stride of the dataref in the inner-loop evenly
864 divides by the vector size. */
865 if (loop && nested_in_vect_loop_p (loop, stmt))
867 tree step = DR_STEP (dr);
868 HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
870 if (dr_step % GET_MODE_SIZE (TYPE_MODE (vectype)) == 0)
872 if (dump_enabled_p ())
873 dump_printf_loc (MSG_NOTE, vect_location,
874 "inner step divides the vector-size.");
875 misalign = STMT_VINFO_DR_INIT (stmt_info);
876 aligned_to = STMT_VINFO_DR_ALIGNED_TO (stmt_info);
877 base_addr = STMT_VINFO_DR_BASE_ADDRESS (stmt_info);
881 if (dump_enabled_p ())
882 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
883 "inner step doesn't divide the vector-size.");
884 misalign = NULL_TREE;
888 /* Similarly, if we're doing basic-block vectorization, we can only use
889 base and misalignment information relative to an innermost loop if the
890 misalignment stays the same throughout the execution of the loop.
891 As above, this is the case if the stride of the dataref evenly divides
892 by the vector size. */
895 tree step = DR_STEP (dr);
896 HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
898 if (dr_step % GET_MODE_SIZE (TYPE_MODE (vectype)) != 0)
900 if (dump_enabled_p ())
901 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
902 "SLP: step doesn't divide the vector-size.");
903 misalign = NULL_TREE;
907 base = build_fold_indirect_ref (base_addr);
908 alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
910 if ((aligned_to && tree_int_cst_compare (aligned_to, alignment) < 0)
913 if (dump_enabled_p ())
915 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
916 "Unknown alignment for access: ");
917 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, base);
923 && tree_int_cst_compare (ssize_int (DECL_ALIGN_UNIT (base)),
925 || (TREE_CODE (base_addr) == SSA_NAME
926 && tree_int_cst_compare (ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (
927 TREE_TYPE (base_addr)))),
929 || (get_pointer_alignment (base_addr) >= TYPE_ALIGN (vectype)))
932 base_aligned = false;
936 /* Do not change the alignment of global variables here if
937 flag_section_anchors is enabled as we already generated
938 RTL for other functions. Most global variables should
939 have been aligned during the IPA increase_alignment pass. */
940 if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype))
941 || (TREE_STATIC (base) && flag_section_anchors))
943 if (dump_enabled_p ())
945 dump_printf_loc (MSG_NOTE, vect_location,
946 "can't force alignment of ref: ");
947 dump_generic_expr (MSG_NOTE, TDF_SLIM, ref);
952 /* Force the alignment of the decl.
953 NOTE: This is the only change to the code we make during
954 the analysis phase, before deciding to vectorize the loop. */
955 if (dump_enabled_p ())
957 dump_printf_loc (MSG_NOTE, vect_location, "force alignment of ");
958 dump_generic_expr (MSG_NOTE, TDF_SLIM, ref);
961 DECL_ALIGN (base) = TYPE_ALIGN (vectype);
962 DECL_USER_ALIGN (base) = 1;
965 /* At this point we assume that the base is aligned. */
966 gcc_assert (base_aligned
967 || (TREE_CODE (base) == VAR_DECL
968 && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
970 /* If this is a backward running DR then first access in the larger
971 vectype actually is N-1 elements before the address in the DR.
972 Adjust misalign accordingly. */
973 if (tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0)
975 tree offset = ssize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
976 /* DR_STEP(dr) is the same as -TYPE_SIZE of the scalar type,
977 otherwise we wouldn't be here. */
978 offset = fold_build2 (MULT_EXPR, ssizetype, offset, DR_STEP (dr));
979 /* PLUS because DR_STEP was negative. */
980 misalign = size_binop (PLUS_EXPR, misalign, offset);
983 /* Modulo alignment. */
984 misalign = size_binop (FLOOR_MOD_EXPR, misalign, alignment);
986 if (!host_integerp (misalign, 1))
988 /* Negative or overflowed misalignment value. */
989 if (dump_enabled_p ())
990 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
991 "unexpected misalign value");
995 SET_DR_MISALIGNMENT (dr, TREE_INT_CST_LOW (misalign));
997 if (dump_enabled_p ())
999 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1000 "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr));
1001 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, ref);
1008 /* Function vect_compute_data_refs_alignment
1010 Compute the misalignment of data references in the loop.
1011 Return FALSE if a data reference is found that cannot be vectorized. */
1014 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo,
1015 bb_vec_info bb_vinfo)
1017 vec<data_reference_p> datarefs;
1018 struct data_reference *dr;
1022 datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1024 datarefs = BB_VINFO_DATAREFS (bb_vinfo);
1026 FOR_EACH_VEC_ELT (datarefs, i, dr)
1027 if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr)))
1028 && !vect_compute_data_ref_alignment (dr))
1032 /* Mark unsupported statement as unvectorizable. */
1033 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
1044 /* Function vect_update_misalignment_for_peel
1046 DR - the data reference whose misalignment is to be adjusted.
1047 DR_PEEL - the data reference whose misalignment is being made
1048 zero in the vector loop by the peel.
1049 NPEEL - the number of iterations in the peel loop if the misalignment
1050 of DR_PEEL is known at compile time. */
1053 vect_update_misalignment_for_peel (struct data_reference *dr,
1054 struct data_reference *dr_peel, int npeel)
1057 vec<dr_p> same_align_drs;
1058 struct data_reference *current_dr;
1059 int dr_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
1060 int dr_peel_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr_peel))));
1061 stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
1062 stmt_vec_info peel_stmt_info = vinfo_for_stmt (DR_STMT (dr_peel));
1064 /* For interleaved data accesses the step in the loop must be multiplied by
1065 the size of the interleaving group. */
1066 if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
1067 dr_size *= GROUP_SIZE (vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info)));
1068 if (STMT_VINFO_GROUPED_ACCESS (peel_stmt_info))
1069 dr_peel_size *= GROUP_SIZE (peel_stmt_info);
1071 /* It can be assumed that the data refs with the same alignment as dr_peel
1072 are aligned in the vector loop. */
1074 = STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr_peel)));
1075 FOR_EACH_VEC_ELT (same_align_drs, i, current_dr)
1077 if (current_dr != dr)
1079 gcc_assert (DR_MISALIGNMENT (dr) / dr_size ==
1080 DR_MISALIGNMENT (dr_peel) / dr_peel_size);
1081 SET_DR_MISALIGNMENT (dr, 0);
1085 if (known_alignment_for_access_p (dr)
1086 && known_alignment_for_access_p (dr_peel))
1088 bool negative = tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0;
1089 int misal = DR_MISALIGNMENT (dr);
1090 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1091 misal += negative ? -npeel * dr_size : npeel * dr_size;
1092 misal &= (TYPE_ALIGN (vectype) / BITS_PER_UNIT) - 1;
1093 SET_DR_MISALIGNMENT (dr, misal);
1097 if (dump_enabled_p ())
1098 dump_printf_loc (MSG_NOTE, vect_location, "Setting misalignment to -1.");
1099 SET_DR_MISALIGNMENT (dr, -1);
1103 /* Function vect_verify_datarefs_alignment
1105 Return TRUE if all data references in the loop can be
1106 handled with respect to alignment. */
1109 vect_verify_datarefs_alignment (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
1111 vec<data_reference_p> datarefs;
1112 struct data_reference *dr;
1113 enum dr_alignment_support supportable_dr_alignment;
1117 datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1119 datarefs = BB_VINFO_DATAREFS (bb_vinfo);
1121 FOR_EACH_VEC_ELT (datarefs, i, dr)
1123 gimple stmt = DR_STMT (dr);
1124 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1126 if (!STMT_VINFO_RELEVANT_P (stmt_info))
1129 /* For interleaving, only the alignment of the first access matters.
1130 Skip statements marked as not vectorizable. */
1131 if ((STMT_VINFO_GROUPED_ACCESS (stmt_info)
1132 && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
1133 || !STMT_VINFO_VECTORIZABLE (stmt_info))
1136 /* Strided loads perform only component accesses, alignment is
1137 irrelevant for them. */
1138 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
1141 supportable_dr_alignment = vect_supportable_dr_alignment (dr, false);
1142 if (!supportable_dr_alignment)
1144 if (dump_enabled_p ())
1146 if (DR_IS_READ (dr))
1147 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1148 "not vectorized: unsupported unaligned load.");
1150 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1151 "not vectorized: unsupported unaligned "
1154 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
1159 if (supportable_dr_alignment != dr_aligned && dump_enabled_p ())
1160 dump_printf_loc (MSG_NOTE, vect_location,
1161 "Vectorizing an unaligned access.");
1166 /* Given an memory reference EXP return whether its alignment is less
1170 not_size_aligned (tree exp)
1172 if (!host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1))
1175 return (TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp)))
1176 > get_object_alignment (exp));
1179 /* Function vector_alignment_reachable_p
1181 Return true if vector alignment for DR is reachable by peeling
1182 a few loop iterations. Return false otherwise. */
1185 vector_alignment_reachable_p (struct data_reference *dr)
1187 gimple stmt = DR_STMT (dr);
1188 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1189 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1191 if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
1193 /* For interleaved access we peel only if number of iterations in
1194 the prolog loop ({VF - misalignment}), is a multiple of the
1195 number of the interleaved accesses. */
1196 int elem_size, mis_in_elements;
1197 int nelements = TYPE_VECTOR_SUBPARTS (vectype);
1199 /* FORNOW: handle only known alignment. */
1200 if (!known_alignment_for_access_p (dr))
1203 elem_size = GET_MODE_SIZE (TYPE_MODE (vectype)) / nelements;
1204 mis_in_elements = DR_MISALIGNMENT (dr) / elem_size;
1206 if ((nelements - mis_in_elements) % GROUP_SIZE (stmt_info))
1210 /* If misalignment is known at the compile time then allow peeling
1211 only if natural alignment is reachable through peeling. */
1212 if (known_alignment_for_access_p (dr) && !aligned_access_p (dr))
1214 HOST_WIDE_INT elmsize =
1215 int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype)));
1216 if (dump_enabled_p ())
1218 dump_printf_loc (MSG_NOTE, vect_location,
1219 "data size =" HOST_WIDE_INT_PRINT_DEC, elmsize);
1220 dump_printf (MSG_NOTE,
1221 ". misalignment = %d. ", DR_MISALIGNMENT (dr));
1223 if (DR_MISALIGNMENT (dr) % elmsize)
1225 if (dump_enabled_p ())
1226 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1227 "data size does not divide the misalignment.\n");
1232 if (!known_alignment_for_access_p (dr))
1234 tree type = TREE_TYPE (DR_REF (dr));
1235 bool is_packed = not_size_aligned (DR_REF (dr));
1236 if (dump_enabled_p ())
1237 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1238 "Unknown misalignment, is_packed = %d",is_packed);
1239 if (targetm.vectorize.vector_alignment_reachable (type, is_packed))
1249 /* Calculate the cost of the memory access represented by DR. */
1252 vect_get_data_access_cost (struct data_reference *dr,
1253 unsigned int *inside_cost,
1254 unsigned int *outside_cost,
1255 stmt_vector_for_cost *body_cost_vec)
1257 gimple stmt = DR_STMT (dr);
1258 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1259 int nunits = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
1260 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1261 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1262 int ncopies = vf / nunits;
1264 if (DR_IS_READ (dr))
1265 vect_get_load_cost (dr, ncopies, true, inside_cost, outside_cost,
1266 NULL, body_cost_vec, false);
1268 vect_get_store_cost (dr, ncopies, inside_cost, body_cost_vec);
1270 if (dump_enabled_p ())
1271 dump_printf_loc (MSG_NOTE, vect_location,
1272 "vect_get_data_access_cost: inside_cost = %d, "
1273 "outside_cost = %d.", *inside_cost, *outside_cost);
1278 vect_peeling_hash (const void *elem)
1280 const struct _vect_peel_info *peel_info;
1282 peel_info = (const struct _vect_peel_info *) elem;
1283 return (hashval_t) peel_info->npeel;
1288 vect_peeling_hash_eq (const void *elem1, const void *elem2)
1290 const struct _vect_peel_info *a, *b;
1292 a = (const struct _vect_peel_info *) elem1;
1293 b = (const struct _vect_peel_info *) elem2;
1294 return (a->npeel == b->npeel);
1298 /* Insert DR into peeling hash table with NPEEL as key. */
1301 vect_peeling_hash_insert (loop_vec_info loop_vinfo, struct data_reference *dr,
1304 struct _vect_peel_info elem, *slot;
1306 bool supportable_dr_alignment = vect_supportable_dr_alignment (dr, true);
1309 slot = (vect_peel_info) htab_find (LOOP_VINFO_PEELING_HTAB (loop_vinfo),
1315 slot = XNEW (struct _vect_peel_info);
1316 slot->npeel = npeel;
1319 new_slot = htab_find_slot (LOOP_VINFO_PEELING_HTAB (loop_vinfo), slot,
1324 if (!supportable_dr_alignment && !flag_vect_cost_model)
1325 slot->count += VECT_MAX_COST;
1329 /* Traverse peeling hash table to find peeling option that aligns maximum
1330 number of data accesses. */
1333 vect_peeling_hash_get_most_frequent (void **slot, void *data)
1335 vect_peel_info elem = (vect_peel_info) *slot;
1336 vect_peel_extended_info max = (vect_peel_extended_info) data;
1338 if (elem->count > max->peel_info.count
1339 || (elem->count == max->peel_info.count
1340 && max->peel_info.npeel > elem->npeel))
1342 max->peel_info.npeel = elem->npeel;
1343 max->peel_info.count = elem->count;
1344 max->peel_info.dr = elem->dr;
1351 /* Traverse peeling hash table and calculate cost for each peeling option.
1352 Find the one with the lowest cost. */
1355 vect_peeling_hash_get_lowest_cost (void **slot, void *data)
1357 vect_peel_info elem = (vect_peel_info) *slot;
1358 vect_peel_extended_info min = (vect_peel_extended_info) data;
1359 int save_misalignment, dummy;
1360 unsigned int inside_cost = 0, outside_cost = 0, i;
1361 gimple stmt = DR_STMT (elem->dr);
1362 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1363 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1364 vec<data_reference_p> datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1365 struct data_reference *dr;
1366 stmt_vector_for_cost prologue_cost_vec, body_cost_vec, epilogue_cost_vec;
1367 int single_iter_cost;
1369 prologue_cost_vec.create (2);
1370 body_cost_vec.create (2);
1371 epilogue_cost_vec.create (2);
1373 FOR_EACH_VEC_ELT (datarefs, i, dr)
1375 stmt = DR_STMT (dr);
1376 stmt_info = vinfo_for_stmt (stmt);
1377 /* For interleaving, only the alignment of the first access
1379 if (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1380 && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
1383 save_misalignment = DR_MISALIGNMENT (dr);
1384 vect_update_misalignment_for_peel (dr, elem->dr, elem->npeel);
1385 vect_get_data_access_cost (dr, &inside_cost, &outside_cost,
1387 SET_DR_MISALIGNMENT (dr, save_misalignment);
1390 single_iter_cost = vect_get_single_scalar_iteration_cost (loop_vinfo);
1391 outside_cost += vect_get_known_peeling_cost (loop_vinfo, elem->npeel,
1392 &dummy, single_iter_cost,
1394 &epilogue_cost_vec);
1396 /* Prologue and epilogue costs are added to the target model later.
1397 These costs depend only on the scalar iteration cost, the
1398 number of peeling iterations finally chosen, and the number of
1399 misaligned statements. So discard the information found here. */
1400 prologue_cost_vec.release ();
1401 epilogue_cost_vec.release ();
1403 if (inside_cost < min->inside_cost
1404 || (inside_cost == min->inside_cost && outside_cost < min->outside_cost))
1406 min->inside_cost = inside_cost;
1407 min->outside_cost = outside_cost;
1408 min->body_cost_vec.release ();
1409 min->body_cost_vec = body_cost_vec;
1410 min->peel_info.dr = elem->dr;
1411 min->peel_info.npeel = elem->npeel;
1414 body_cost_vec.release ();
1420 /* Choose best peeling option by traversing peeling hash table and either
1421 choosing an option with the lowest cost (if cost model is enabled) or the
1422 option that aligns as many accesses as possible. */
1424 static struct data_reference *
1425 vect_peeling_hash_choose_best_peeling (loop_vec_info loop_vinfo,
1426 unsigned int *npeel,
1427 stmt_vector_for_cost *body_cost_vec)
1429 struct _vect_peel_extended_info res;
1431 res.peel_info.dr = NULL;
1432 res.body_cost_vec = stmt_vector_for_cost();
1434 if (flag_vect_cost_model)
1436 res.inside_cost = INT_MAX;
1437 res.outside_cost = INT_MAX;
1438 htab_traverse (LOOP_VINFO_PEELING_HTAB (loop_vinfo),
1439 vect_peeling_hash_get_lowest_cost, &res);
1443 res.peel_info.count = 0;
1444 htab_traverse (LOOP_VINFO_PEELING_HTAB (loop_vinfo),
1445 vect_peeling_hash_get_most_frequent, &res);
1448 *npeel = res.peel_info.npeel;
1449 *body_cost_vec = res.body_cost_vec;
1450 return res.peel_info.dr;
1454 /* Function vect_enhance_data_refs_alignment
1456 This pass will use loop versioning and loop peeling in order to enhance
1457 the alignment of data references in the loop.
1459 FOR NOW: we assume that whatever versioning/peeling takes place, only the
1460 original loop is to be vectorized. Any other loops that are created by
1461 the transformations performed in this pass - are not supposed to be
1462 vectorized. This restriction will be relaxed.
1464 This pass will require a cost model to guide it whether to apply peeling
1465 or versioning or a combination of the two. For example, the scheme that
1466 intel uses when given a loop with several memory accesses, is as follows:
1467 choose one memory access ('p') which alignment you want to force by doing
1468 peeling. Then, either (1) generate a loop in which 'p' is aligned and all
1469 other accesses are not necessarily aligned, or (2) use loop versioning to
1470 generate one loop in which all accesses are aligned, and another loop in
1471 which only 'p' is necessarily aligned.
1473 ("Automatic Intra-Register Vectorization for the Intel Architecture",
1474 Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
1475 Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
1477 Devising a cost model is the most critical aspect of this work. It will
1478 guide us on which access to peel for, whether to use loop versioning, how
1479 many versions to create, etc. The cost model will probably consist of
1480 generic considerations as well as target specific considerations (on
1481 powerpc for example, misaligned stores are more painful than misaligned
1484 Here are the general steps involved in alignment enhancements:
1486 -- original loop, before alignment analysis:
1487 for (i=0; i<N; i++){
1488 x = q[i]; # DR_MISALIGNMENT(q) = unknown
1489 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1492 -- After vect_compute_data_refs_alignment:
1493 for (i=0; i<N; i++){
1494 x = q[i]; # DR_MISALIGNMENT(q) = 3
1495 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1498 -- Possibility 1: we do loop versioning:
1500 for (i=0; i<N; i++){ # loop 1A
1501 x = q[i]; # DR_MISALIGNMENT(q) = 3
1502 p[i] = y; # DR_MISALIGNMENT(p) = 0
1506 for (i=0; i<N; i++){ # loop 1B
1507 x = q[i]; # DR_MISALIGNMENT(q) = 3
1508 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1512 -- Possibility 2: we do loop peeling:
1513 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1517 for (i = 3; i < N; i++){ # loop 2A
1518 x = q[i]; # DR_MISALIGNMENT(q) = 0
1519 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1522 -- Possibility 3: combination of loop peeling and versioning:
1523 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1528 for (i = 3; i<N; i++){ # loop 3A
1529 x = q[i]; # DR_MISALIGNMENT(q) = 0
1530 p[i] = y; # DR_MISALIGNMENT(p) = 0
1534 for (i = 3; i<N; i++){ # loop 3B
1535 x = q[i]; # DR_MISALIGNMENT(q) = 0
1536 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1540 These loops are later passed to loop_transform to be vectorized. The
1541 vectorizer will use the alignment information to guide the transformation
1542 (whether to generate regular loads/stores, or with special handling for
1546 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
1548 vec<data_reference_p> datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1549 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1550 enum dr_alignment_support supportable_dr_alignment;
1551 struct data_reference *dr0 = NULL, *first_store = NULL;
1552 struct data_reference *dr;
1554 bool do_peeling = false;
1555 bool do_versioning = false;
1558 stmt_vec_info stmt_info;
1559 int vect_versioning_for_alias_required;
1560 unsigned int npeel = 0;
1561 bool all_misalignments_unknown = true;
1562 unsigned int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1563 unsigned possible_npeel_number = 1;
1565 unsigned int nelements, mis, same_align_drs_max = 0;
1566 stmt_vector_for_cost body_cost_vec = stmt_vector_for_cost();
1568 if (dump_enabled_p ())
1569 dump_printf_loc (MSG_NOTE, vect_location,
1570 "=== vect_enhance_data_refs_alignment ===");
1572 /* While cost model enhancements are expected in the future, the high level
1573 view of the code at this time is as follows:
1575 A) If there is a misaligned access then see if peeling to align
1576 this access can make all data references satisfy
1577 vect_supportable_dr_alignment. If so, update data structures
1578 as needed and return true.
1580 B) If peeling wasn't possible and there is a data reference with an
1581 unknown misalignment that does not satisfy vect_supportable_dr_alignment
1582 then see if loop versioning checks can be used to make all data
1583 references satisfy vect_supportable_dr_alignment. If so, update
1584 data structures as needed and return true.
1586 C) If neither peeling nor versioning were successful then return false if
1587 any data reference does not satisfy vect_supportable_dr_alignment.
1589 D) Return true (all data references satisfy vect_supportable_dr_alignment).
1591 Note, Possibility 3 above (which is peeling and versioning together) is not
1592 being done at this time. */
1594 /* (1) Peeling to force alignment. */
1596 /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1598 + How many accesses will become aligned due to the peeling
1599 - How many accesses will become unaligned due to the peeling,
1600 and the cost of misaligned accesses.
1601 - The cost of peeling (the extra runtime checks, the increase
1604 FOR_EACH_VEC_ELT (datarefs, i, dr)
1606 stmt = DR_STMT (dr);
1607 stmt_info = vinfo_for_stmt (stmt);
1609 if (!STMT_VINFO_RELEVANT_P (stmt_info))
1612 /* For interleaving, only the alignment of the first access
1614 if (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1615 && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
1618 /* For invariant accesses there is nothing to enhance. */
1619 if (integer_zerop (DR_STEP (dr)))
1622 /* Strided loads perform only component accesses, alignment is
1623 irrelevant for them. */
1624 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
1627 supportable_dr_alignment = vect_supportable_dr_alignment (dr, true);
1628 do_peeling = vector_alignment_reachable_p (dr);
1631 if (known_alignment_for_access_p (dr))
1633 unsigned int npeel_tmp;
1634 bool negative = tree_int_cst_compare (DR_STEP (dr),
1635 size_zero_node) < 0;
1637 /* Save info about DR in the hash table. */
1638 if (!LOOP_VINFO_PEELING_HTAB (loop_vinfo))
1639 LOOP_VINFO_PEELING_HTAB (loop_vinfo) =
1640 htab_create (1, vect_peeling_hash,
1641 vect_peeling_hash_eq, free);
1643 vectype = STMT_VINFO_VECTYPE (stmt_info);
1644 nelements = TYPE_VECTOR_SUBPARTS (vectype);
1645 mis = DR_MISALIGNMENT (dr) / GET_MODE_SIZE (TYPE_MODE (
1646 TREE_TYPE (DR_REF (dr))));
1647 npeel_tmp = (negative
1648 ? (mis - nelements) : (nelements - mis))
1651 /* For multiple types, it is possible that the bigger type access
1652 will have more than one peeling option. E.g., a loop with two
1653 types: one of size (vector size / 4), and the other one of
1654 size (vector size / 8). Vectorization factor will 8. If both
1655 access are misaligned by 3, the first one needs one scalar
1656 iteration to be aligned, and the second one needs 5. But the
1657 the first one will be aligned also by peeling 5 scalar
1658 iterations, and in that case both accesses will be aligned.
1659 Hence, except for the immediate peeling amount, we also want
1660 to try to add full vector size, while we don't exceed
1661 vectorization factor.
1662 We do this automtically for cost model, since we calculate cost
1663 for every peeling option. */
1664 if (!flag_vect_cost_model)
1665 possible_npeel_number = vf /nelements;
1667 /* Handle the aligned case. We may decide to align some other
1668 access, making DR unaligned. */
1669 if (DR_MISALIGNMENT (dr) == 0)
1672 if (!flag_vect_cost_model)
1673 possible_npeel_number++;
1676 for (j = 0; j < possible_npeel_number; j++)
1678 gcc_assert (npeel_tmp <= vf);
1679 vect_peeling_hash_insert (loop_vinfo, dr, npeel_tmp);
1680 npeel_tmp += nelements;
1683 all_misalignments_unknown = false;
1684 /* Data-ref that was chosen for the case that all the
1685 misalignments are unknown is not relevant anymore, since we
1686 have a data-ref with known alignment. */
1691 /* If we don't know all the misalignment values, we prefer
1692 peeling for data-ref that has maximum number of data-refs
1693 with the same alignment, unless the target prefers to align
1694 stores over load. */
1695 if (all_misalignments_unknown)
1697 if (same_align_drs_max
1698 < STMT_VINFO_SAME_ALIGN_REFS (stmt_info).length ()
1702 = STMT_VINFO_SAME_ALIGN_REFS (stmt_info).length ();
1706 if (!first_store && DR_IS_WRITE (dr))
1710 /* If there are both known and unknown misaligned accesses in the
1711 loop, we choose peeling amount according to the known
1715 if (!supportable_dr_alignment)
1718 if (!first_store && DR_IS_WRITE (dr))
1725 if (!aligned_access_p (dr))
1727 if (dump_enabled_p ())
1728 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1729 "vector alignment may not be reachable");
1735 vect_versioning_for_alias_required
1736 = LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo);
1738 /* Temporarily, if versioning for alias is required, we disable peeling
1739 until we support peeling and versioning. Often peeling for alignment
1740 will require peeling for loop-bound, which in turn requires that we
1741 know how to adjust the loop ivs after the loop. */
1742 if (vect_versioning_for_alias_required
1743 || !vect_can_advance_ivs_p (loop_vinfo)
1744 || !slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
1747 if (do_peeling && all_misalignments_unknown
1748 && vect_supportable_dr_alignment (dr0, false))
1751 /* Check if the target requires to prefer stores over loads, i.e., if
1752 misaligned stores are more expensive than misaligned loads (taking
1753 drs with same alignment into account). */
1754 if (first_store && DR_IS_READ (dr0))
1756 unsigned int load_inside_cost = 0, load_outside_cost = 0;
1757 unsigned int store_inside_cost = 0, store_outside_cost = 0;
1758 unsigned int load_inside_penalty = 0, load_outside_penalty = 0;
1759 unsigned int store_inside_penalty = 0, store_outside_penalty = 0;
1760 stmt_vector_for_cost dummy;
1763 vect_get_data_access_cost (dr0, &load_inside_cost, &load_outside_cost,
1765 vect_get_data_access_cost (first_store, &store_inside_cost,
1766 &store_outside_cost, &dummy);
1770 /* Calculate the penalty for leaving FIRST_STORE unaligned (by
1771 aligning the load DR0). */
1772 load_inside_penalty = store_inside_cost;
1773 load_outside_penalty = store_outside_cost;
1775 STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (
1776 DR_STMT (first_store))).iterate (i, &dr);
1778 if (DR_IS_READ (dr))
1780 load_inside_penalty += load_inside_cost;
1781 load_outside_penalty += load_outside_cost;
1785 load_inside_penalty += store_inside_cost;
1786 load_outside_penalty += store_outside_cost;
1789 /* Calculate the penalty for leaving DR0 unaligned (by
1790 aligning the FIRST_STORE). */
1791 store_inside_penalty = load_inside_cost;
1792 store_outside_penalty = load_outside_cost;
1794 STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (
1795 DR_STMT (dr0))).iterate (i, &dr);
1797 if (DR_IS_READ (dr))
1799 store_inside_penalty += load_inside_cost;
1800 store_outside_penalty += load_outside_cost;
1804 store_inside_penalty += store_inside_cost;
1805 store_outside_penalty += store_outside_cost;
1808 if (load_inside_penalty > store_inside_penalty
1809 || (load_inside_penalty == store_inside_penalty
1810 && load_outside_penalty > store_outside_penalty))
1814 /* In case there are only loads with different unknown misalignments, use
1815 peeling only if it may help to align other accesses in the loop. */
1817 && !STMT_VINFO_SAME_ALIGN_REFS (
1818 vinfo_for_stmt (DR_STMT (dr0))).length ()
1819 && vect_supportable_dr_alignment (dr0, false)
1820 != dr_unaligned_supported)
1824 if (do_peeling && !dr0)
1826 /* Peeling is possible, but there is no data access that is not supported
1827 unless aligned. So we try to choose the best possible peeling. */
1829 /* We should get here only if there are drs with known misalignment. */
1830 gcc_assert (!all_misalignments_unknown);
1832 /* Choose the best peeling from the hash table. */
1833 dr0 = vect_peeling_hash_choose_best_peeling (loop_vinfo, &npeel,
1841 stmt = DR_STMT (dr0);
1842 stmt_info = vinfo_for_stmt (stmt);
1843 vectype = STMT_VINFO_VECTYPE (stmt_info);
1844 nelements = TYPE_VECTOR_SUBPARTS (vectype);
1846 if (known_alignment_for_access_p (dr0))
1848 bool negative = tree_int_cst_compare (DR_STEP (dr0),
1849 size_zero_node) < 0;
1852 /* Since it's known at compile time, compute the number of
1853 iterations in the peeled loop (the peeling factor) for use in
1854 updating DR_MISALIGNMENT values. The peeling factor is the
1855 vectorization factor minus the misalignment as an element
1857 mis = DR_MISALIGNMENT (dr0);
1858 mis /= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0))));
1859 npeel = ((negative ? mis - nelements : nelements - mis)
1863 /* For interleaved data access every iteration accesses all the
1864 members of the group, therefore we divide the number of iterations
1865 by the group size. */
1866 stmt_info = vinfo_for_stmt (DR_STMT (dr0));
1867 if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
1868 npeel /= GROUP_SIZE (stmt_info);
1870 if (dump_enabled_p ())
1871 dump_printf_loc (MSG_NOTE, vect_location,
1872 "Try peeling by %d", npeel);
1875 /* Ensure that all data refs can be vectorized after the peel. */
1876 FOR_EACH_VEC_ELT (datarefs, i, dr)
1878 int save_misalignment;
1883 stmt = DR_STMT (dr);
1884 stmt_info = vinfo_for_stmt (stmt);
1885 /* For interleaving, only the alignment of the first access
1887 if (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1888 && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
1891 /* Strided loads perform only component accesses, alignment is
1892 irrelevant for them. */
1893 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
1896 save_misalignment = DR_MISALIGNMENT (dr);
1897 vect_update_misalignment_for_peel (dr, dr0, npeel);
1898 supportable_dr_alignment = vect_supportable_dr_alignment (dr, false);
1899 SET_DR_MISALIGNMENT (dr, save_misalignment);
1901 if (!supportable_dr_alignment)
1908 if (do_peeling && known_alignment_for_access_p (dr0) && npeel == 0)
1910 stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
1915 body_cost_vec.release ();
1922 stmt_info_for_cost *si;
1923 void *data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
1925 /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i.
1926 If the misalignment of DR_i is identical to that of dr0 then set
1927 DR_MISALIGNMENT (DR_i) to zero. If the misalignment of DR_i and
1928 dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i)
1929 by the peeling factor times the element size of DR_i (MOD the
1930 vectorization factor times the size). Otherwise, the
1931 misalignment of DR_i must be set to unknown. */
1932 FOR_EACH_VEC_ELT (datarefs, i, dr)
1934 vect_update_misalignment_for_peel (dr, dr0, npeel);
1936 LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr0;
1938 LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) = npeel;
1940 LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) = DR_MISALIGNMENT (dr0);
1941 SET_DR_MISALIGNMENT (dr0, 0);
1942 if (dump_enabled_p ())
1944 dump_printf_loc (MSG_NOTE, vect_location,
1945 "Alignment of access forced using peeling.");
1946 dump_printf_loc (MSG_NOTE, vect_location,
1947 "Peeling for alignment will be applied.");
1949 /* We've delayed passing the inside-loop peeling costs to the
1950 target cost model until we were sure peeling would happen.
1952 if (body_cost_vec.exists ())
1954 FOR_EACH_VEC_ELT (body_cost_vec, i, si)
1956 struct _stmt_vec_info *stmt_info
1957 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
1958 (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
1959 si->misalign, vect_body);
1961 body_cost_vec.release ();
1964 stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
1970 body_cost_vec.release ();
1972 /* (2) Versioning to force alignment. */
1974 /* Try versioning if:
1975 1) flag_tree_vect_loop_version is TRUE
1976 2) optimize loop for speed
1977 3) there is at least one unsupported misaligned data ref with an unknown
1979 4) all misaligned data refs with a known misalignment are supported, and
1980 5) the number of runtime alignment checks is within reason. */
1983 flag_tree_vect_loop_version
1984 && optimize_loop_nest_for_speed_p (loop)
1985 && (!loop->inner); /* FORNOW */
1989 FOR_EACH_VEC_ELT (datarefs, i, dr)
1991 stmt = DR_STMT (dr);
1992 stmt_info = vinfo_for_stmt (stmt);
1994 /* For interleaving, only the alignment of the first access
1996 if (aligned_access_p (dr)
1997 || (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1998 && GROUP_FIRST_ELEMENT (stmt_info) != stmt))
2001 /* Strided loads perform only component accesses, alignment is
2002 irrelevant for them. */
2003 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
2006 supportable_dr_alignment = vect_supportable_dr_alignment (dr, false);
2008 if (!supportable_dr_alignment)
2014 if (known_alignment_for_access_p (dr)
2015 || LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).length ()
2016 >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS))
2018 do_versioning = false;
2022 stmt = DR_STMT (dr);
2023 vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
2024 gcc_assert (vectype);
2026 /* The rightmost bits of an aligned address must be zeros.
2027 Construct the mask needed for this test. For example,
2028 GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the
2029 mask must be 15 = 0xf. */
2030 mask = GET_MODE_SIZE (TYPE_MODE (vectype)) - 1;
2032 /* FORNOW: use the same mask to test all potentially unaligned
2033 references in the loop. The vectorizer currently supports
2034 a single vector size, see the reference to
2035 GET_MODE_NUNITS (TYPE_MODE (vectype)) where the
2036 vectorization factor is computed. */
2037 gcc_assert (!LOOP_VINFO_PTR_MASK (loop_vinfo)
2038 || LOOP_VINFO_PTR_MASK (loop_vinfo) == mask);
2039 LOOP_VINFO_PTR_MASK (loop_vinfo) = mask;
2040 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).safe_push (
2045 /* Versioning requires at least one misaligned data reference. */
2046 if (!LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
2047 do_versioning = false;
2048 else if (!do_versioning)
2049 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).truncate (0);
2054 vec<gimple> may_misalign_stmts
2055 = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
2058 /* It can now be assumed that the data references in the statements
2059 in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version
2060 of the loop being vectorized. */
2061 FOR_EACH_VEC_ELT (may_misalign_stmts, i, stmt)
2063 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2064 dr = STMT_VINFO_DATA_REF (stmt_info);
2065 SET_DR_MISALIGNMENT (dr, 0);
2066 if (dump_enabled_p ())
2067 dump_printf_loc (MSG_NOTE, vect_location,
2068 "Alignment of access forced using versioning.");
2071 if (dump_enabled_p ())
2072 dump_printf_loc (MSG_NOTE, vect_location,
2073 "Versioning for alignment will be applied.");
2075 /* Peeling and versioning can't be done together at this time. */
2076 gcc_assert (! (do_peeling && do_versioning));
2078 stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
2083 /* This point is reached if neither peeling nor versioning is being done. */
2084 gcc_assert (! (do_peeling || do_versioning));
2086 stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
2091 /* Function vect_find_same_alignment_drs.
2093 Update group and alignment relations according to the chosen
2094 vectorization factor. */
2097 vect_find_same_alignment_drs (struct data_dependence_relation *ddr,
2098 loop_vec_info loop_vinfo)
2101 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2102 int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2103 struct data_reference *dra = DDR_A (ddr);
2104 struct data_reference *drb = DDR_B (ddr);
2105 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
2106 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
2107 int dra_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dra))));
2108 int drb_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (drb))));
2109 lambda_vector dist_v;
2110 unsigned int loop_depth;
2112 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
2118 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
2121 /* Loop-based vectorization and known data dependence. */
2122 if (DDR_NUM_DIST_VECTS (ddr) == 0)
2125 /* Data-dependence analysis reports a distance vector of zero
2126 for data-references that overlap only in the first iteration
2127 but have different sign step (see PR45764).
2128 So as a sanity check require equal DR_STEP. */
2129 if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
2132 loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
2133 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
2135 int dist = dist_v[loop_depth];
2137 if (dump_enabled_p ())
2138 dump_printf_loc (MSG_NOTE, vect_location,
2139 "dependence distance = %d.", dist);
2141 /* Same loop iteration. */
2143 || (dist % vectorization_factor == 0 && dra_size == drb_size))
2145 /* Two references with distance zero have the same alignment. */
2146 STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a).safe_push (drb);
2147 STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b).safe_push (dra);
2148 if (dump_enabled_p ())
2150 dump_printf_loc (MSG_NOTE, vect_location,
2151 "accesses have the same alignment.");
2152 dump_printf (MSG_NOTE,
2153 "dependence distance modulo vf == 0 between ");
2154 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
2155 dump_printf (MSG_NOTE, " and ");
2156 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
2163 /* Function vect_analyze_data_refs_alignment
2165 Analyze the alignment of the data-references in the loop.
2166 Return FALSE if a data reference is found that cannot be vectorized. */
2169 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo,
2170 bb_vec_info bb_vinfo)
2172 if (dump_enabled_p ())
2173 dump_printf_loc (MSG_NOTE, vect_location,
2174 "=== vect_analyze_data_refs_alignment ===");
2176 /* Mark groups of data references with same alignment using
2177 data dependence information. */
2180 vec<ddr_p> ddrs = LOOP_VINFO_DDRS (loop_vinfo);
2181 struct data_dependence_relation *ddr;
2184 FOR_EACH_VEC_ELT (ddrs, i, ddr)
2185 vect_find_same_alignment_drs (ddr, loop_vinfo);
2188 if (!vect_compute_data_refs_alignment (loop_vinfo, bb_vinfo))
2190 if (dump_enabled_p ())
2191 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2192 "not vectorized: can't calculate alignment "
2201 /* Analyze groups of accesses: check that DR belongs to a group of
2202 accesses of legal size, step, etc. Detect gaps, single element
2203 interleaving, and other special cases. Set grouped access info.
2204 Collect groups of strided stores for further use in SLP analysis. */
2207 vect_analyze_group_access (struct data_reference *dr)
2209 tree step = DR_STEP (dr);
2210 tree scalar_type = TREE_TYPE (DR_REF (dr));
2211 HOST_WIDE_INT type_size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
2212 gimple stmt = DR_STMT (dr);
2213 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2214 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2215 bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
2216 HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
2217 HOST_WIDE_INT groupsize, last_accessed_element = 1;
2218 bool slp_impossible = false;
2219 struct loop *loop = NULL;
2222 loop = LOOP_VINFO_LOOP (loop_vinfo);
2224 /* For interleaving, GROUPSIZE is STEP counted in elements, i.e., the
2225 size of the interleaving group (including gaps). */
2226 groupsize = dr_step / type_size;
2228 /* Not consecutive access is possible only if it is a part of interleaving. */
2229 if (!GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
2231 /* Check if it this DR is a part of interleaving, and is a single
2232 element of the group that is accessed in the loop. */
2234 /* Gaps are supported only for loads. STEP must be a multiple of the type
2235 size. The size of the group must be a power of 2. */
2237 && (dr_step % type_size) == 0
2239 && exact_log2 (groupsize) != -1)
2241 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = stmt;
2242 GROUP_SIZE (vinfo_for_stmt (stmt)) = groupsize;
2243 if (dump_enabled_p ())
2245 dump_printf_loc (MSG_NOTE, vect_location,
2246 "Detected single element interleaving ");
2247 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr));
2248 dump_printf (MSG_NOTE, " step ");
2249 dump_generic_expr (MSG_NOTE, TDF_SLIM, step);
2254 if (dump_enabled_p ())
2255 dump_printf_loc (MSG_NOTE, vect_location,
2256 "Data access with gaps requires scalar "
2260 if (dump_enabled_p ())
2261 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2262 "Peeling for outer loop is not"
2267 LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) = true;
2273 if (dump_enabled_p ())
2275 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2276 "not consecutive access ");
2277 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
2282 /* Mark the statement as unvectorizable. */
2283 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
2290 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) == stmt)
2292 /* First stmt in the interleaving chain. Check the chain. */
2293 gimple next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt));
2294 struct data_reference *data_ref = dr;
2295 unsigned int count = 1;
2297 tree prev_init = DR_INIT (data_ref);
2299 HOST_WIDE_INT diff, count_in_bytes, gaps = 0;
2303 /* Skip same data-refs. In case that two or more stmts share
2304 data-ref (supported only for loads), we vectorize only the first
2305 stmt, and the rest get their vectorized loads from the first
2307 if (!tree_int_cst_compare (DR_INIT (data_ref),
2308 DR_INIT (STMT_VINFO_DATA_REF (
2309 vinfo_for_stmt (next)))))
2311 if (DR_IS_WRITE (data_ref))
2313 if (dump_enabled_p ())
2314 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2315 "Two store stmts share the same dr.");
2319 /* Check that there is no load-store dependencies for this loads
2320 to prevent a case of load-store-load to the same location. */
2321 if (GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (next))
2322 || GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (prev)))
2324 if (dump_enabled_p ())
2325 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2326 "READ_WRITE dependence in interleaving.");
2330 /* For load use the same data-ref load. */
2331 GROUP_SAME_DR_STMT (vinfo_for_stmt (next)) = prev;
2334 next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next));
2340 /* Check that all the accesses have the same STEP. */
2341 next_step = DR_STEP (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
2342 if (tree_int_cst_compare (step, next_step))
2344 if (dump_enabled_p ())
2345 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2346 "not consecutive access in interleaving");
2350 data_ref = STMT_VINFO_DATA_REF (vinfo_for_stmt (next));
2351 /* Check that the distance between two accesses is equal to the type
2352 size. Otherwise, we have gaps. */
2353 diff = (TREE_INT_CST_LOW (DR_INIT (data_ref))
2354 - TREE_INT_CST_LOW (prev_init)) / type_size;
2357 /* FORNOW: SLP of accesses with gaps is not supported. */
2358 slp_impossible = true;
2359 if (DR_IS_WRITE (data_ref))
2361 if (dump_enabled_p ())
2362 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2363 "interleaved store with gaps");
2370 last_accessed_element += diff;
2372 /* Store the gap from the previous member of the group. If there is no
2373 gap in the access, GROUP_GAP is always 1. */
2374 GROUP_GAP (vinfo_for_stmt (next)) = diff;
2376 prev_init = DR_INIT (data_ref);
2377 next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next));
2378 /* Count the number of data-refs in the chain. */
2382 /* COUNT is the number of accesses found, we multiply it by the size of
2383 the type to get COUNT_IN_BYTES. */
2384 count_in_bytes = type_size * count;
2386 /* Check that the size of the interleaving (including gaps) is not
2387 greater than STEP. */
2388 if (dr_step && dr_step < count_in_bytes + gaps * type_size)
2390 if (dump_enabled_p ())
2392 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2393 "interleaving size is greater than step for ");
2394 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dr));
2399 /* Check that the size of the interleaving is equal to STEP for stores,
2400 i.e., that there are no gaps. */
2401 if (dr_step && dr_step != count_in_bytes)
2403 if (DR_IS_READ (dr))
2405 slp_impossible = true;
2406 /* There is a gap after the last load in the group. This gap is a
2407 difference between the groupsize and the number of elements.
2408 When there is no gap, this difference should be 0. */
2409 GROUP_GAP (vinfo_for_stmt (stmt)) = groupsize - count;
2413 if (dump_enabled_p ())
2414 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2415 "interleaved store with gaps");
2420 /* Check that STEP is a multiple of type size. */
2421 if (dr_step && (dr_step % type_size) != 0)
2423 if (dump_enabled_p ())
2425 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2426 "step is not a multiple of type size: step ");
2427 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, step);
2428 dump_printf (MSG_MISSED_OPTIMIZATION, " size ");
2429 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
2430 TYPE_SIZE_UNIT (scalar_type));
2438 GROUP_SIZE (vinfo_for_stmt (stmt)) = groupsize;
2439 if (dump_enabled_p ())
2440 dump_printf_loc (MSG_NOTE, vect_location,
2441 "Detected interleaving of size %d", (int)groupsize);
2443 /* SLP: create an SLP data structure for every interleaving group of
2444 stores for further analysis in vect_analyse_slp. */
2445 if (DR_IS_WRITE (dr) && !slp_impossible)
2448 LOOP_VINFO_GROUPED_STORES (loop_vinfo).safe_push (stmt);
2450 BB_VINFO_GROUPED_STORES (bb_vinfo).safe_push (stmt);
2453 /* There is a gap in the end of the group. */
2454 if (groupsize - last_accessed_element > 0 && loop_vinfo)
2456 if (dump_enabled_p ())
2457 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2458 "Data access with gaps requires scalar "
2462 if (dump_enabled_p ())
2463 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2464 "Peeling for outer loop is not supported");
2468 LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) = true;
2476 /* Analyze the access pattern of the data-reference DR.
2477 In case of non-consecutive accesses call vect_analyze_group_access() to
2478 analyze groups of accesses. */
2481 vect_analyze_data_ref_access (struct data_reference *dr)
2483 tree step = DR_STEP (dr);
2484 tree scalar_type = TREE_TYPE (DR_REF (dr));
2485 gimple stmt = DR_STMT (dr);
2486 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2487 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2488 struct loop *loop = NULL;
2491 loop = LOOP_VINFO_LOOP (loop_vinfo);
2493 if (loop_vinfo && !step)
2495 if (dump_enabled_p ())
2496 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2497 "bad data-ref access in loop");
2501 /* Allow invariant loads in not nested loops. */
2502 if (loop_vinfo && integer_zerop (step))
2504 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = NULL;
2505 if (nested_in_vect_loop_p (loop, stmt))
2507 if (dump_enabled_p ())
2508 dump_printf_loc (MSG_NOTE, vect_location,
2509 "zero step in inner loop of nest");
2512 return DR_IS_READ (dr);
2515 if (loop && nested_in_vect_loop_p (loop, stmt))
2517 /* Interleaved accesses are not yet supported within outer-loop
2518 vectorization for references in the inner-loop. */
2519 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = NULL;
2521 /* For the rest of the analysis we use the outer-loop step. */
2522 step = STMT_VINFO_DR_STEP (stmt_info);
2523 if (integer_zerop (step))
2525 if (dump_enabled_p ())
2526 dump_printf_loc (MSG_NOTE, vect_location,
2527 "zero step in outer loop.");
2528 if (DR_IS_READ (dr))
2536 if (TREE_CODE (step) == INTEGER_CST)
2538 HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
2539 if (!tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type))
2541 && !compare_tree_int (TYPE_SIZE_UNIT (scalar_type), -dr_step)))
2543 /* Mark that it is not interleaving. */
2544 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = NULL;
2549 if (loop && nested_in_vect_loop_p (loop, stmt))
2551 if (dump_enabled_p ())
2552 dump_printf_loc (MSG_NOTE, vect_location,
2553 "grouped access in outer loop.");
2557 /* Assume this is a DR handled by non-constant strided load case. */
2558 if (TREE_CODE (step) != INTEGER_CST)
2559 return STMT_VINFO_STRIDE_LOAD_P (stmt_info);
2561 /* Not consecutive access - check if it's a part of interleaving group. */
2562 return vect_analyze_group_access (dr);
2566 /* Function vect_analyze_data_ref_accesses.
2568 Analyze the access pattern of all the data references in the loop.
2570 FORNOW: the only access pattern that is considered vectorizable is a
2571 simple step 1 (consecutive) access.
2573 FORNOW: handle only arrays and pointer accesses. */
2576 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
2579 vec<data_reference_p> datarefs;
2580 struct data_reference *dr;
2582 if (dump_enabled_p ())
2583 dump_printf_loc (MSG_NOTE, vect_location,
2584 "=== vect_analyze_data_ref_accesses ===");
2587 datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2589 datarefs = BB_VINFO_DATAREFS (bb_vinfo);
2591 FOR_EACH_VEC_ELT (datarefs, i, dr)
2592 if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr)))
2593 && !vect_analyze_data_ref_access (dr))
2595 if (dump_enabled_p ())
2596 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2597 "not vectorized: complicated access pattern.");
2601 /* Mark the statement as not vectorizable. */
2602 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
2612 /* Function vect_prune_runtime_alias_test_list.
2614 Prune a list of ddrs to be tested at run-time by versioning for alias.
2615 Return FALSE if resulting list of ddrs is longer then allowed by
2616 PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS, otherwise return TRUE. */
2619 vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo)
2622 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo);
2625 if (dump_enabled_p ())
2626 dump_printf_loc (MSG_NOTE, vect_location,
2627 "=== vect_prune_runtime_alias_test_list ===");
2629 for (i = 0; i < ddrs.length (); )
2637 for (j = 0; j < i; j++)
2639 ddr_p ddr_j = ddrs[j];
2641 if (vect_vfa_range_equal (ddr_i, ddr_j))
2643 if (dump_enabled_p ())
2645 dump_printf_loc (MSG_NOTE, vect_location,
2646 "found equal ranges ");
2647 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_A (ddr_i)));
2648 dump_printf (MSG_NOTE, ", ");
2649 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_B (ddr_i)));
2650 dump_printf (MSG_NOTE, " and ");
2651 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_A (ddr_j)));
2652 dump_printf (MSG_NOTE, ", ");
2653 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_B (ddr_j)));
2662 ddrs.ordered_remove (i);
2668 if (ddrs.length () >
2669 (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS))
2671 if (dump_enabled_p ())
2673 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2674 "disable versioning for alias - max number of "
2675 "generated checks exceeded.");
2678 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo).truncate (0);
2686 /* Check whether a non-affine read in stmt is suitable for gather load
2687 and if so, return a builtin decl for that operation. */
2690 vect_check_gather (gimple stmt, loop_vec_info loop_vinfo, tree *basep,
2691 tree *offp, int *scalep)
2693 HOST_WIDE_INT scale = 1, pbitpos, pbitsize;
2694 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2695 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2696 struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
2697 tree offtype = NULL_TREE;
2698 tree decl, base, off;
2699 enum machine_mode pmode;
2700 int punsignedp, pvolatilep;
2702 /* The gather builtins need address of the form
2703 loop_invariant + vector * {1, 2, 4, 8}
2705 loop_invariant + sign_extend (vector) * { 1, 2, 4, 8 }.
2706 Unfortunately DR_BASE_ADDRESS/DR_OFFSET can be a mixture
2707 of loop invariants/SSA_NAMEs defined in the loop, with casts,
2708 multiplications and additions in it. To get a vector, we need
2709 a single SSA_NAME that will be defined in the loop and will
2710 contain everything that is not loop invariant and that can be
2711 vectorized. The following code attempts to find such a preexistng
2712 SSA_NAME OFF and put the loop invariants into a tree BASE
2713 that can be gimplified before the loop. */
2714 base = get_inner_reference (DR_REF (dr), &pbitsize, &pbitpos, &off,
2715 &pmode, &punsignedp, &pvolatilep, false);
2716 gcc_assert (base != NULL_TREE && (pbitpos % BITS_PER_UNIT) == 0);
2718 if (TREE_CODE (base) == MEM_REF)
2720 if (!integer_zerop (TREE_OPERAND (base, 1)))
2722 if (off == NULL_TREE)
2724 double_int moff = mem_ref_offset (base);
2725 off = double_int_to_tree (sizetype, moff);
2728 off = size_binop (PLUS_EXPR, off,
2729 fold_convert (sizetype, TREE_OPERAND (base, 1)));
2731 base = TREE_OPERAND (base, 0);
2734 base = build_fold_addr_expr (base);
2736 if (off == NULL_TREE)
2737 off = size_zero_node;
2739 /* If base is not loop invariant, either off is 0, then we start with just
2740 the constant offset in the loop invariant BASE and continue with base
2741 as OFF, otherwise give up.
2742 We could handle that case by gimplifying the addition of base + off
2743 into some SSA_NAME and use that as off, but for now punt. */
2744 if (!expr_invariant_in_loop_p (loop, base))
2746 if (!integer_zerop (off))
2749 base = size_int (pbitpos / BITS_PER_UNIT);
2751 /* Otherwise put base + constant offset into the loop invariant BASE
2752 and continue with OFF. */
2755 base = fold_convert (sizetype, base);
2756 base = size_binop (PLUS_EXPR, base, size_int (pbitpos / BITS_PER_UNIT));
2759 /* OFF at this point may be either a SSA_NAME or some tree expression
2760 from get_inner_reference. Try to peel off loop invariants from it
2761 into BASE as long as possible. */
2763 while (offtype == NULL_TREE)
2765 enum tree_code code;
2766 tree op0, op1, add = NULL_TREE;
2768 if (TREE_CODE (off) == SSA_NAME)
2770 gimple def_stmt = SSA_NAME_DEF_STMT (off);
2772 if (expr_invariant_in_loop_p (loop, off))
2775 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2778 op0 = gimple_assign_rhs1 (def_stmt);
2779 code = gimple_assign_rhs_code (def_stmt);
2780 op1 = gimple_assign_rhs2 (def_stmt);
2784 if (get_gimple_rhs_class (TREE_CODE (off)) == GIMPLE_TERNARY_RHS)
2786 code = TREE_CODE (off);
2787 extract_ops_from_tree (off, &code, &op0, &op1);
2791 case POINTER_PLUS_EXPR:
2793 if (expr_invariant_in_loop_p (loop, op0))
2798 add = fold_convert (sizetype, add);
2800 add = size_binop (MULT_EXPR, add, size_int (scale));
2801 base = size_binop (PLUS_EXPR, base, add);
2804 if (expr_invariant_in_loop_p (loop, op1))
2812 if (expr_invariant_in_loop_p (loop, op1))
2814 add = fold_convert (sizetype, op1);
2815 add = size_binop (MINUS_EXPR, size_zero_node, add);
2821 if (scale == 1 && host_integerp (op1, 0))
2823 scale = tree_low_cst (op1, 0);
2832 if (!POINTER_TYPE_P (TREE_TYPE (op0))
2833 && !INTEGRAL_TYPE_P (TREE_TYPE (op0)))
2835 if (TYPE_PRECISION (TREE_TYPE (op0))
2836 == TYPE_PRECISION (TREE_TYPE (off)))
2841 if (TYPE_PRECISION (TREE_TYPE (op0))
2842 < TYPE_PRECISION (TREE_TYPE (off)))
2845 offtype = TREE_TYPE (off);
2856 /* If at the end OFF still isn't a SSA_NAME or isn't
2857 defined in the loop, punt. */
2858 if (TREE_CODE (off) != SSA_NAME
2859 || expr_invariant_in_loop_p (loop, off))
2862 if (offtype == NULL_TREE)
2863 offtype = TREE_TYPE (off);
2865 decl = targetm.vectorize.builtin_gather (STMT_VINFO_VECTYPE (stmt_info),
2867 if (decl == NULL_TREE)
2879 /* Check wether a non-affine load in STMT (being in the loop referred to
2880 in LOOP_VINFO) is suitable for handling as strided load. That is the case
2881 if its address is a simple induction variable. If so return the base
2882 of that induction variable in *BASEP and the (loop-invariant) step
2883 in *STEPP, both only when that pointer is non-zero.
2885 This handles ARRAY_REFs (with variant index) and MEM_REFs (with variant
2886 base pointer) only. */
2889 vect_check_strided_load (gimple stmt, loop_vec_info loop_vinfo)
2891 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2892 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2893 struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
2897 if (!DR_IS_READ (dr))
2902 if (TREE_CODE (base) == ARRAY_REF)
2904 off = TREE_OPERAND (base, 1);
2905 base = TREE_OPERAND (base, 0);
2907 else if (TREE_CODE (base) == MEM_REF)
2909 off = TREE_OPERAND (base, 0);
2910 base = TREE_OPERAND (base, 1);
2915 if (TREE_CODE (off) != SSA_NAME)
2918 if (!expr_invariant_in_loop_p (loop, base)
2919 || !simple_iv (loop, loop_containing_stmt (stmt), off, &iv, true))
2925 /* Function vect_analyze_data_refs.
2927 Find all the data references in the loop or basic block.
2929 The general structure of the analysis of data refs in the vectorizer is as
2931 1- vect_analyze_data_refs(loop/bb): call
2932 compute_data_dependences_for_loop/bb to find and analyze all data-refs
2933 in the loop/bb and their dependences.
2934 2- vect_analyze_dependences(): apply dependence testing using ddrs.
2935 3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
2936 4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
2941 vect_analyze_data_refs (loop_vec_info loop_vinfo,
2942 bb_vec_info bb_vinfo,
2945 struct loop *loop = NULL;
2946 basic_block bb = NULL;
2948 vec<data_reference_p> datarefs;
2949 struct data_reference *dr;
2951 bool res, stop_bb_analysis = false;
2953 if (dump_enabled_p ())
2954 dump_printf_loc (MSG_NOTE, vect_location,
2955 "=== vect_analyze_data_refs ===\n");
2959 loop = LOOP_VINFO_LOOP (loop_vinfo);
2960 res = compute_data_dependences_for_loop
2962 &LOOP_VINFO_LOOP_NEST (loop_vinfo),
2963 &LOOP_VINFO_DATAREFS (loop_vinfo),
2964 &LOOP_VINFO_DDRS (loop_vinfo));
2968 if (dump_enabled_p ())
2969 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2970 "not vectorized: loop contains function calls"
2971 " or data references that cannot be analyzed");
2975 datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2979 gimple_stmt_iterator gsi;
2981 bb = BB_VINFO_BB (bb_vinfo);
2982 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2984 gimple stmt = gsi_stmt (gsi);
2985 if (!find_data_references_in_stmt (NULL, stmt,
2986 &BB_VINFO_DATAREFS (bb_vinfo)))
2988 /* Mark the rest of the basic-block as unvectorizable. */
2989 for (; !gsi_end_p (gsi); gsi_next (&gsi))
2991 stmt = gsi_stmt (gsi);
2992 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt)) = false;
2997 if (!compute_all_dependences (BB_VINFO_DATAREFS (bb_vinfo),
2998 &BB_VINFO_DDRS (bb_vinfo),
3001 if (dump_enabled_p ())
3002 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3003 "not vectorized: basic block contains function"
3004 " calls or data references that cannot be"
3009 datarefs = BB_VINFO_DATAREFS (bb_vinfo);
3012 /* Go through the data-refs, check that the analysis succeeded. Update
3013 pointer from stmt_vec_info struct to DR and vectype. */
3015 FOR_EACH_VEC_ELT (datarefs, i, dr)
3018 stmt_vec_info stmt_info;
3019 tree base, offset, init;
3020 bool gather = false;
3023 if (!dr || !DR_REF (dr))
3025 if (dump_enabled_p ())
3026 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3027 "not vectorized: unhandled data-ref ");
3031 stmt = DR_STMT (dr);
3032 stmt_info = vinfo_for_stmt (stmt);
3034 if (stop_bb_analysis)
3036 STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3040 /* Check that analysis of the data-ref succeeded. */
3041 if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr) || !DR_INIT (dr)
3044 /* If target supports vector gather loads, see if they can't
3048 && !TREE_THIS_VOLATILE (DR_REF (dr))
3049 && targetm.vectorize.builtin_gather != NULL
3050 && !nested_in_vect_loop_p (loop, stmt))
3052 struct data_reference *newdr
3053 = create_data_ref (NULL, loop_containing_stmt (stmt),
3054 DR_REF (dr), stmt, true);
3055 gcc_assert (newdr != NULL && DR_REF (newdr));
3056 if (DR_BASE_ADDRESS (newdr)
3057 && DR_OFFSET (newdr)
3060 && integer_zerop (DR_STEP (newdr)))
3066 free_data_ref (newdr);
3071 if (dump_enabled_p ())
3073 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3074 "not vectorized: data ref analysis "
3076 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3081 STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3082 stop_bb_analysis = true;
3090 if (TREE_CODE (DR_BASE_ADDRESS (dr)) == INTEGER_CST)
3092 if (dump_enabled_p ())
3093 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3094 "not vectorized: base addr of dr is a "
3099 STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3100 stop_bb_analysis = true;
3109 if (TREE_THIS_VOLATILE (DR_REF (dr)))
3111 if (dump_enabled_p ())
3113 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3114 "not vectorized: volatile type ");
3115 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3120 STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3121 stop_bb_analysis = true;
3128 if (stmt_can_throw_internal (stmt))
3130 if (dump_enabled_p ())
3132 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3133 "not vectorized: statement can throw an "
3135 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3140 STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3141 stop_bb_analysis = true;
3150 if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
3151 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
3153 if (dump_enabled_p ())
3155 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3156 "not vectorized: statement is bitfield "
3158 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3163 STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3164 stop_bb_analysis = true;
3173 base = unshare_expr (DR_BASE_ADDRESS (dr));
3174 offset = unshare_expr (DR_OFFSET (dr));
3175 init = unshare_expr (DR_INIT (dr));
3177 if (is_gimple_call (stmt))
3179 if (dump_enabled_p ())
3181 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3182 "not vectorized: dr in a call ");
3183 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3188 STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3189 stop_bb_analysis = true;
3198 /* Update DR field in stmt_vec_info struct. */
3200 /* If the dataref is in an inner-loop of the loop that is considered for
3201 for vectorization, we also want to analyze the access relative to
3202 the outer-loop (DR contains information only relative to the
3203 inner-most enclosing loop). We do that by building a reference to the
3204 first location accessed by the inner-loop, and analyze it relative to
3206 if (loop && nested_in_vect_loop_p (loop, stmt))
3208 tree outer_step, outer_base, outer_init;
3209 HOST_WIDE_INT pbitsize, pbitpos;
3211 enum machine_mode pmode;
3212 int punsignedp, pvolatilep;
3213 affine_iv base_iv, offset_iv;
3216 /* Build a reference to the first location accessed by the
3217 inner-loop: *(BASE+INIT). (The first location is actually
3218 BASE+INIT+OFFSET, but we add OFFSET separately later). */
3219 tree inner_base = build_fold_indirect_ref
3220 (fold_build_pointer_plus (base, init));
3222 if (dump_enabled_p ())
3224 dump_printf_loc (MSG_NOTE, vect_location,
3225 "analyze in outer-loop: ");
3226 dump_generic_expr (MSG_NOTE, TDF_SLIM, inner_base);
3229 outer_base = get_inner_reference (inner_base, &pbitsize, &pbitpos,
3230 &poffset, &pmode, &punsignedp, &pvolatilep, false);
3231 gcc_assert (outer_base != NULL_TREE);
3233 if (pbitpos % BITS_PER_UNIT != 0)
3235 if (dump_enabled_p ())
3236 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3237 "failed: bit offset alignment.\n");
3241 outer_base = build_fold_addr_expr (outer_base);
3242 if (!simple_iv (loop, loop_containing_stmt (stmt), outer_base,
3245 if (dump_enabled_p ())
3246 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3247 "failed: evolution of base is not affine.\n");
3254 poffset = fold_build2 (PLUS_EXPR, TREE_TYPE (offset), offset,
3262 offset_iv.base = ssize_int (0);
3263 offset_iv.step = ssize_int (0);
3265 else if (!simple_iv (loop, loop_containing_stmt (stmt), poffset,
3268 if (dump_enabled_p ())
3269 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3270 "evolution of offset is not affine.\n");
3274 outer_init = ssize_int (pbitpos / BITS_PER_UNIT);
3275 split_constant_offset (base_iv.base, &base_iv.base, &dinit);
3276 outer_init = size_binop (PLUS_EXPR, outer_init, dinit);
3277 split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
3278 outer_init = size_binop (PLUS_EXPR, outer_init, dinit);
3280 outer_step = size_binop (PLUS_EXPR,
3281 fold_convert (ssizetype, base_iv.step),
3282 fold_convert (ssizetype, offset_iv.step));
3284 STMT_VINFO_DR_STEP (stmt_info) = outer_step;
3285 /* FIXME: Use canonicalize_base_object_address (base_iv.base); */
3286 STMT_VINFO_DR_BASE_ADDRESS (stmt_info) = base_iv.base;
3287 STMT_VINFO_DR_INIT (stmt_info) = outer_init;
3288 STMT_VINFO_DR_OFFSET (stmt_info) =
3289 fold_convert (ssizetype, offset_iv.base);
3290 STMT_VINFO_DR_ALIGNED_TO (stmt_info) =
3291 size_int (highest_pow2_factor (offset_iv.base));
3293 if (dump_enabled_p ())
3295 dump_printf_loc (MSG_NOTE, vect_location,
3296 "\touter base_address: ");
3297 dump_generic_expr (MSG_NOTE, TDF_SLIM,
3298 STMT_VINFO_DR_BASE_ADDRESS (stmt_info));
3299 dump_printf (MSG_NOTE, "\n\touter offset from base address: ");
3300 dump_generic_expr (MSG_NOTE, TDF_SLIM,
3301 STMT_VINFO_DR_OFFSET (stmt_info));
3302 dump_printf (MSG_NOTE,
3303 "\n\touter constant offset from base address: ");
3304 dump_generic_expr (MSG_NOTE, TDF_SLIM,
3305 STMT_VINFO_DR_INIT (stmt_info));
3306 dump_printf (MSG_NOTE, "\n\touter step: ");
3307 dump_generic_expr (MSG_NOTE, TDF_SLIM,
3308 STMT_VINFO_DR_STEP (stmt_info));
3309 dump_printf (MSG_NOTE, "\n\touter aligned to: ");
3310 dump_generic_expr (MSG_NOTE, TDF_SLIM,
3311 STMT_VINFO_DR_ALIGNED_TO (stmt_info));
3315 if (STMT_VINFO_DATA_REF (stmt_info))
3317 if (dump_enabled_p ())
3319 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3320 "not vectorized: more than one data ref "
3322 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3327 STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3328 stop_bb_analysis = true;
3337 STMT_VINFO_DATA_REF (stmt_info) = dr;
3339 /* Set vectype for STMT. */
3340 scalar_type = TREE_TYPE (DR_REF (dr));
3341 STMT_VINFO_VECTYPE (stmt_info) =
3342 get_vectype_for_scalar_type (scalar_type);
3343 if (!STMT_VINFO_VECTYPE (stmt_info))
3345 if (dump_enabled_p ())
3347 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3348 "not vectorized: no vectype for stmt: ");
3349 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3350 dump_printf (MSG_MISSED_OPTIMIZATION, " scalar_type: ");
3351 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_DETAILS,
3357 /* Mark the statement as not vectorizable. */
3358 STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3359 stop_bb_analysis = true;
3365 STMT_VINFO_DATA_REF (stmt_info) = NULL;
3371 /* Adjust the minimal vectorization factor according to the
3373 vf = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
3379 unsigned int j, k, n;
3380 struct data_reference *olddr
3382 vec<ddr_p> ddrs = LOOP_VINFO_DDRS (loop_vinfo);
3383 struct data_dependence_relation *ddr, *newddr;
3386 vec<loop_p> nest = LOOP_VINFO_LOOP_NEST (loop_vinfo);
3388 gather = 0 != vect_check_gather (stmt, loop_vinfo, NULL, &off, NULL);
3390 && get_vectype_for_scalar_type (TREE_TYPE (off)) == NULL_TREE)
3394 STMT_VINFO_DATA_REF (stmt_info) = NULL;
3396 if (dump_enabled_p ())
3398 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3399 "not vectorized: not suitable for gather "
3401 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3406 n = datarefs.length () - 1;
3407 for (j = 0, k = i - 1; j < i; j++)
3410 gcc_assert (DDR_B (ddr) == olddr);
3411 newddr = initialize_data_dependence_relation (DDR_A (ddr), dr,
3414 free_dependence_relation (ddr);
3416 && DR_IS_WRITE (DDR_A (newddr))
3417 && DDR_ARE_DEPENDENT (newddr) != chrec_known)
3423 n = k + datarefs.length () - i - 1;
3427 gcc_assert (DDR_A (ddr) == olddr);
3428 newddr = initialize_data_dependence_relation (dr, DDR_B (ddr),
3431 free_dependence_relation (ddr);
3433 && DR_IS_WRITE (DDR_B (newddr))
3434 && DDR_ARE_DEPENDENT (newddr) != chrec_known)
3439 - datarefs.length () + i;
3441 gcc_assert (DDR_A (ddr) == olddr && DDR_B (ddr) == olddr);
3442 newddr = initialize_data_dependence_relation (dr, dr, nest);
3444 free_dependence_relation (ddr);
3449 if (dump_enabled_p ())
3451 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3452 "not vectorized: data dependence conflict"
3453 " prevents gather load");
3454 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3459 STMT_VINFO_GATHER_P (stmt_info) = true;
3462 && TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
3464 bool strided_load = false;
3465 if (!nested_in_vect_loop_p (loop, stmt))
3466 strided_load = vect_check_strided_load (stmt, loop_vinfo);
3469 if (dump_enabled_p ())
3471 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3472 "not vectorized: not suitable for strided "
3474 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3478 STMT_VINFO_STRIDE_LOAD_P (stmt_info) = true;
3486 /* Function vect_get_new_vect_var.
3488 Returns a name for a new variable. The current naming scheme appends the
3489 prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
3490 the name of vectorizer generated variables, and appends that to NAME if
3494 vect_get_new_vect_var (tree type, enum vect_var_kind var_kind, const char *name)
3501 case vect_simple_var:
3504 case vect_scalar_var:
3507 case vect_pointer_var:
3516 char* tmp = concat (prefix, name, NULL);
3517 new_vect_var = create_tmp_reg (type, tmp);
3521 new_vect_var = create_tmp_reg (type, prefix);
3523 return new_vect_var;
3527 /* Function vect_create_addr_base_for_vector_ref.
3529 Create an expression that computes the address of the first memory location
3530 that will be accessed for a data reference.
3533 STMT: The statement containing the data reference.
3534 NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
3535 OFFSET: Optional. If supplied, it is be added to the initial address.
3536 LOOP: Specify relative to which loop-nest should the address be computed.
3537 For example, when the dataref is in an inner-loop nested in an
3538 outer-loop that is now being vectorized, LOOP can be either the
3539 outer-loop, or the inner-loop. The first memory location accessed
3540 by the following dataref ('in' points to short):
3547 if LOOP=i_loop: &in (relative to i_loop)
3548 if LOOP=j_loop: &in+i*2B (relative to j_loop)
3551 1. Return an SSA_NAME whose value is the address of the memory location of
3552 the first vector of the data reference.
3553 2. If new_stmt_list is not NULL_TREE after return then the caller must insert
3554 these statement(s) which define the returned SSA_NAME.
3556 FORNOW: We are only handling array accesses with step 1. */
3559 vect_create_addr_base_for_vector_ref (gimple stmt,
3560 gimple_seq *new_stmt_list,
3564 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3565 struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
3566 tree data_ref_base = unshare_expr (DR_BASE_ADDRESS (dr));
3567 const char *base_name;
3568 tree data_ref_base_var;
3570 tree addr_base, addr_expr;
3572 gimple_seq seq = NULL;
3573 tree base_offset = unshare_expr (DR_OFFSET (dr));
3574 tree init = unshare_expr (DR_INIT (dr));
3576 tree step = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)));
3577 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3580 if (loop_vinfo && loop && loop != (gimple_bb (stmt))->loop_father)
3582 struct loop *outer_loop = LOOP_VINFO_LOOP (loop_vinfo);
3584 gcc_assert (nested_in_vect_loop_p (outer_loop, stmt));
3586 data_ref_base = unshare_expr (STMT_VINFO_DR_BASE_ADDRESS (stmt_info));
3587 base_offset = unshare_expr (STMT_VINFO_DR_OFFSET (stmt_info));
3588 init = unshare_expr (STMT_VINFO_DR_INIT (stmt_info));
3592 base_name = get_name (data_ref_base);
3595 base_offset = ssize_int (0);
3596 init = ssize_int (0);
3597 base_name = get_name (DR_REF (dr));
3600 data_ref_base_var = create_tmp_var (TREE_TYPE (data_ref_base), "batmp");
3601 data_ref_base = force_gimple_operand (data_ref_base, &seq, true,
3603 gimple_seq_add_seq (new_stmt_list, seq);
3605 /* Create base_offset */
3606 base_offset = size_binop (PLUS_EXPR,
3607 fold_convert (sizetype, base_offset),
3608 fold_convert (sizetype, init));
3609 dest = create_tmp_var (sizetype, "base_off");
3610 base_offset = force_gimple_operand (base_offset, &seq, true, dest);
3611 gimple_seq_add_seq (new_stmt_list, seq);
3615 tree tmp = create_tmp_var (sizetype, "offset");
3617 offset = fold_build2 (MULT_EXPR, sizetype,
3618 fold_convert (sizetype, offset), step);
3619 base_offset = fold_build2 (PLUS_EXPR, sizetype,
3620 base_offset, offset);
3621 base_offset = force_gimple_operand (base_offset, &seq, false, tmp);
3622 gimple_seq_add_seq (new_stmt_list, seq);
3625 /* base + base_offset */
3627 addr_base = fold_build_pointer_plus (data_ref_base, base_offset);
3630 addr_base = build1 (ADDR_EXPR,
3631 build_pointer_type (TREE_TYPE (DR_REF (dr))),
3632 unshare_expr (DR_REF (dr)));
3635 vect_ptr_type = build_pointer_type (STMT_VINFO_VECTYPE (stmt_info));
3636 base = get_base_address (DR_REF (dr));
3638 && TREE_CODE (base) == MEM_REF)
3640 = build_qualified_type (vect_ptr_type,
3641 TYPE_QUALS (TREE_TYPE (TREE_OPERAND (base, 0))));
3643 vec_stmt = fold_convert (vect_ptr_type, addr_base);
3644 addr_expr = vect_get_new_vect_var (vect_ptr_type, vect_pointer_var,
3646 vec_stmt = force_gimple_operand (vec_stmt, &seq, false, addr_expr);
3647 gimple_seq_add_seq (new_stmt_list, seq);
3649 if (DR_PTR_INFO (dr)
3650 && TREE_CODE (vec_stmt) == SSA_NAME)
3652 duplicate_ssa_name_ptr_info (vec_stmt, DR_PTR_INFO (dr));
3654 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (vec_stmt));
3657 if (dump_enabled_p ())
3659 dump_printf_loc (MSG_NOTE, vect_location, "created ");
3660 dump_generic_expr (MSG_NOTE, TDF_SLIM, vec_stmt);
3667 /* Function vect_create_data_ref_ptr.
3669 Create a new pointer-to-AGGR_TYPE variable (ap), that points to the first
3670 location accessed in the loop by STMT, along with the def-use update
3671 chain to appropriately advance the pointer through the loop iterations.
3672 Also set aliasing information for the pointer. This pointer is used by
3673 the callers to this function to create a memory reference expression for
3674 vector load/store access.
3677 1. STMT: a stmt that references memory. Expected to be of the form
3678 GIMPLE_ASSIGN <name, data-ref> or
3679 GIMPLE_ASSIGN <data-ref, name>.
3680 2. AGGR_TYPE: the type of the reference, which should be either a vector
3682 3. AT_LOOP: the loop where the vector memref is to be created.
3683 4. OFFSET (optional): an offset to be added to the initial address accessed
3684 by the data-ref in STMT.
3685 5. BSI: location where the new stmts are to be placed if there is no loop
3686 6. ONLY_INIT: indicate if ap is to be updated in the loop, or remain
3687 pointing to the initial address.
3690 1. Declare a new ptr to vector_type, and have it point to the base of the
3691 data reference (initial addressed accessed by the data reference).
3692 For example, for vector of type V8HI, the following code is generated:
3695 ap = (v8hi *)initial_address;
3697 if OFFSET is not supplied:
3698 initial_address = &a[init];
3699 if OFFSET is supplied:
3700 initial_address = &a[init + OFFSET];
3702 Return the initial_address in INITIAL_ADDRESS.
3704 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
3705 update the pointer in each iteration of the loop.
3707 Return the increment stmt that updates the pointer in PTR_INCR.
3709 3. Set INV_P to true if the access pattern of the data reference in the
3710 vectorized loop is invariant. Set it to false otherwise.
3712 4. Return the pointer. */
3715 vect_create_data_ref_ptr (gimple stmt, tree aggr_type, struct loop *at_loop,
3716 tree offset, tree *initial_address,
3717 gimple_stmt_iterator *gsi, gimple *ptr_incr,
3718 bool only_init, bool *inv_p)
3720 const char *base_name;
3721 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3722 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3723 struct loop *loop = NULL;
3724 bool nested_in_vect_loop = false;
3725 struct loop *containing_loop = NULL;
3730 gimple_seq new_stmt_list = NULL;
3734 struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
3736 gimple_stmt_iterator incr_gsi;
3739 tree indx_before_incr, indx_after_incr;
3742 bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
3745 gcc_assert (TREE_CODE (aggr_type) == ARRAY_TYPE
3746 || TREE_CODE (aggr_type) == VECTOR_TYPE);
3750 loop = LOOP_VINFO_LOOP (loop_vinfo);
3751 nested_in_vect_loop = nested_in_vect_loop_p (loop, stmt);
3752 containing_loop = (gimple_bb (stmt))->loop_father;
3753 pe = loop_preheader_edge (loop);
3757 gcc_assert (bb_vinfo);
3762 /* Check the step (evolution) of the load in LOOP, and record
3763 whether it's invariant. */
3764 if (nested_in_vect_loop)
3765 step = STMT_VINFO_DR_STEP (stmt_info);
3767 step = DR_STEP (STMT_VINFO_DATA_REF (stmt_info));
3769 if (tree_int_cst_compare (step, size_zero_node) == 0)
3773 negative = tree_int_cst_compare (step, size_zero_node) < 0;
3775 /* Create an expression for the first address accessed by this load
3777 base_name = get_name (DR_BASE_ADDRESS (dr));
3779 if (dump_enabled_p ())
3781 tree dr_base_type = TREE_TYPE (DR_BASE_OBJECT (dr));
3782 dump_printf_loc (MSG_NOTE, vect_location,
3783 "create %s-pointer variable to type: ",
3784 tree_code_name[(int) TREE_CODE (aggr_type)]);
3785 dump_generic_expr (MSG_NOTE, TDF_SLIM, aggr_type);
3786 if (TREE_CODE (dr_base_type) == ARRAY_TYPE)
3787 dump_printf (MSG_NOTE, " vectorizing an array ref: ");
3788 else if (TREE_CODE (dr_base_type) == RECORD_TYPE)
3789 dump_printf (MSG_NOTE, " vectorizing a record based array ref: ");
3791 dump_printf (MSG_NOTE, " vectorizing a pointer ref: ");
3792 dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_BASE_OBJECT (dr));
3795 /* (1) Create the new aggregate-pointer variable. */
3796 aggr_ptr_type = build_pointer_type (aggr_type);
3797 base = get_base_address (DR_REF (dr));
3799 && TREE_CODE (base) == MEM_REF)
3801 = build_qualified_type (aggr_ptr_type,
3802 TYPE_QUALS (TREE_TYPE (TREE_OPERAND (base, 0))));
3803 aggr_ptr = vect_get_new_vect_var (aggr_ptr_type, vect_pointer_var, base_name);
3805 /* Vector and array types inherit the alias set of their component
3806 type by default so we need to use a ref-all pointer if the data
3807 reference does not conflict with the created aggregated data
3808 reference because it is not addressable. */
3809 if (!alias_sets_conflict_p (get_deref_alias_set (aggr_ptr),
3810 get_alias_set (DR_REF (dr))))
3813 = build_pointer_type_for_mode (aggr_type,
3814 TYPE_MODE (aggr_ptr_type), true);
3815 aggr_ptr = vect_get_new_vect_var (aggr_ptr_type, vect_pointer_var,
3819 /* Likewise for any of the data references in the stmt group. */
3820 else if (STMT_VINFO_GROUP_SIZE (stmt_info) > 1)
3822 gimple orig_stmt = STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info);
3825 tree lhs = gimple_assign_lhs (orig_stmt);
3826 if (!alias_sets_conflict_p (get_deref_alias_set (aggr_ptr),
3827 get_alias_set (lhs)))
3830 = build_pointer_type_for_mode (aggr_type,
3831 TYPE_MODE (aggr_ptr_type), true);
3833 = vect_get_new_vect_var (aggr_ptr_type, vect_pointer_var,
3838 orig_stmt = STMT_VINFO_GROUP_NEXT_ELEMENT (vinfo_for_stmt (orig_stmt));
3843 /* Note: If the dataref is in an inner-loop nested in LOOP, and we are
3844 vectorizing LOOP (i.e., outer-loop vectorization), we need to create two
3845 def-use update cycles for the pointer: one relative to the outer-loop
3846 (LOOP), which is what steps (3) and (4) below do. The other is relative
3847 to the inner-loop (which is the inner-most loop containing the dataref),
3848 and this is done be step (5) below.
3850 When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
3851 inner-most loop, and so steps (3),(4) work the same, and step (5) is
3852 redundant. Steps (3),(4) create the following:
3855 LOOP: vp1 = phi(vp0,vp2)
3861 If there is an inner-loop nested in loop, then step (5) will also be
3862 applied, and an additional update in the inner-loop will be created:
3865 LOOP: vp1 = phi(vp0,vp2)
3867 inner: vp3 = phi(vp1,vp4)
3868 vp4 = vp3 + inner_step
3874 /* (2) Calculate the initial address of the aggregate-pointer, and set
3875 the aggregate-pointer to point to it before the loop. */
3877 /* Create: (&(base[init_val+offset]) in the loop preheader. */
3879 new_temp = vect_create_addr_base_for_vector_ref (stmt, &new_stmt_list,
3885 new_bb = gsi_insert_seq_on_edge_immediate (pe, new_stmt_list);
3886 gcc_assert (!new_bb);
3889 gsi_insert_seq_before (gsi, new_stmt_list, GSI_SAME_STMT);
3892 *initial_address = new_temp;
3894 /* Create: p = (aggr_type *) initial_base */
3895 if (TREE_CODE (new_temp) != SSA_NAME
3896 || !useless_type_conversion_p (aggr_ptr_type, TREE_TYPE (new_temp)))
3898 vec_stmt = gimple_build_assign (aggr_ptr,
3899 fold_convert (aggr_ptr_type, new_temp));
3900 aggr_ptr_init = make_ssa_name (aggr_ptr, vec_stmt);
3901 /* Copy the points-to information if it exists. */
3902 if (DR_PTR_INFO (dr))
3903 duplicate_ssa_name_ptr_info (aggr_ptr_init, DR_PTR_INFO (dr));
3904 gimple_assign_set_lhs (vec_stmt, aggr_ptr_init);
3907 new_bb = gsi_insert_on_edge_immediate (pe, vec_stmt);
3908 gcc_assert (!new_bb);
3911 gsi_insert_before (gsi, vec_stmt, GSI_SAME_STMT);
3914 aggr_ptr_init = new_temp;
3916 /* (3) Handle the updating of the aggregate-pointer inside the loop.
3917 This is needed when ONLY_INIT is false, and also when AT_LOOP is the
3918 inner-loop nested in LOOP (during outer-loop vectorization). */
3920 /* No update in loop is required. */
3921 if (only_init && (!loop_vinfo || at_loop == loop))
3922 aptr = aggr_ptr_init;
3925 /* The step of the aggregate pointer is the type size. */
3926 tree step = TYPE_SIZE_UNIT (aggr_type);
3927 /* One exception to the above is when the scalar step of the load in
3928 LOOP is zero. In this case the step here is also zero. */
3930 step = size_zero_node;
3932 step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
3934 standard_iv_increment_position (loop, &incr_gsi, &insert_after);
3936 create_iv (aggr_ptr_init,
3937 fold_convert (aggr_ptr_type, step),
3938 aggr_ptr, loop, &incr_gsi, insert_after,
3939 &indx_before_incr, &indx_after_incr);
3940 incr = gsi_stmt (incr_gsi);
3941 set_vinfo_for_stmt (incr, new_stmt_vec_info (incr, loop_vinfo, NULL));
3943 /* Copy the points-to information if it exists. */
3944 if (DR_PTR_INFO (dr))
3946 duplicate_ssa_name_ptr_info (indx_before_incr, DR_PTR_INFO (dr));
3947 duplicate_ssa_name_ptr_info (indx_after_incr, DR_PTR_INFO (dr));
3952 aptr = indx_before_incr;
3955 if (!nested_in_vect_loop || only_init)
3959 /* (4) Handle the updating of the aggregate-pointer inside the inner-loop
3960 nested in LOOP, if exists. */
3962 gcc_assert (nested_in_vect_loop);
3965 standard_iv_increment_position (containing_loop, &incr_gsi,
3967 create_iv (aptr, fold_convert (aggr_ptr_type, DR_STEP (dr)), aggr_ptr,
3968 containing_loop, &incr_gsi, insert_after, &indx_before_incr,
3970 incr = gsi_stmt (incr_gsi);
3971 set_vinfo_for_stmt (incr, new_stmt_vec_info (incr, loop_vinfo, NULL));
3973 /* Copy the points-to information if it exists. */
3974 if (DR_PTR_INFO (dr))
3976 duplicate_ssa_name_ptr_info (indx_before_incr, DR_PTR_INFO (dr));
3977 duplicate_ssa_name_ptr_info (indx_after_incr, DR_PTR_INFO (dr));
3982 return indx_before_incr;
3989 /* Function bump_vector_ptr
3991 Increment a pointer (to a vector type) by vector-size. If requested,
3992 i.e. if PTR-INCR is given, then also connect the new increment stmt
3993 to the existing def-use update-chain of the pointer, by modifying
3994 the PTR_INCR as illustrated below:
3996 The pointer def-use update-chain before this function:
3997 DATAREF_PTR = phi (p_0, p_2)
3999 PTR_INCR: p_2 = DATAREF_PTR + step
4001 The pointer def-use update-chain after this function:
4002 DATAREF_PTR = phi (p_0, p_2)
4004 NEW_DATAREF_PTR = DATAREF_PTR + BUMP
4006 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
4009 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
4011 PTR_INCR - optional. The stmt that updates the pointer in each iteration of
4012 the loop. The increment amount across iterations is expected
4014 BSI - location where the new update stmt is to be placed.
4015 STMT - the original scalar memory-access stmt that is being vectorized.
4016 BUMP - optional. The offset by which to bump the pointer. If not given,
4017 the offset is assumed to be vector_size.
4019 Output: Return NEW_DATAREF_PTR as illustrated above.
4024 bump_vector_ptr (tree dataref_ptr, gimple ptr_incr, gimple_stmt_iterator *gsi,
4025 gimple stmt, tree bump)
4027 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4028 struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
4029 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
4030 tree update = TYPE_SIZE_UNIT (vectype);
4033 use_operand_p use_p;
4034 tree new_dataref_ptr;
4039 new_dataref_ptr = copy_ssa_name (dataref_ptr, NULL);
4040 incr_stmt = gimple_build_assign_with_ops (POINTER_PLUS_EXPR, new_dataref_ptr,
4041 dataref_ptr, update);
4042 vect_finish_stmt_generation (stmt, incr_stmt, gsi);
4044 /* Copy the points-to information if it exists. */
4045 if (DR_PTR_INFO (dr))
4047 duplicate_ssa_name_ptr_info (new_dataref_ptr, DR_PTR_INFO (dr));
4048 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (new_dataref_ptr));
4052 return new_dataref_ptr;
4054 /* Update the vector-pointer's cross-iteration increment. */
4055 FOR_EACH_SSA_USE_OPERAND (use_p, ptr_incr, iter, SSA_OP_USE)
4057 tree use = USE_FROM_PTR (use_p);
4059 if (use == dataref_ptr)
4060 SET_USE (use_p, new_dataref_ptr);
4062 gcc_assert (tree_int_cst_compare (use, update) == 0);
4065 return new_dataref_ptr;
4069 /* Function vect_create_destination_var.
4071 Create a new temporary of type VECTYPE. */
4074 vect_create_destination_var (tree scalar_dest, tree vectype)
4077 const char *new_name;
4079 enum vect_var_kind kind;
4081 kind = vectype ? vect_simple_var : vect_scalar_var;
4082 type = vectype ? vectype : TREE_TYPE (scalar_dest);
4084 gcc_assert (TREE_CODE (scalar_dest) == SSA_NAME);
4086 new_name = get_name (scalar_dest);
4089 vec_dest = vect_get_new_vect_var (type, kind, new_name);
4094 /* Function vect_grouped_store_supported.
4096 Returns TRUE if interleave high and interleave low permutations
4097 are supported, and FALSE otherwise. */
4100 vect_grouped_store_supported (tree vectype, unsigned HOST_WIDE_INT count)
4102 enum machine_mode mode = TYPE_MODE (vectype);
4104 /* vect_permute_store_chain requires the group size to be a power of two. */
4105 if (exact_log2 (count) == -1)
4107 if (dump_enabled_p ())
4108 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
4109 "the size of the group of accesses"
4110 " is not a power of 2");
4114 /* Check that the permutation is supported. */
4115 if (VECTOR_MODE_P (mode))
4117 unsigned int i, nelt = GET_MODE_NUNITS (mode);
4118 unsigned char *sel = XALLOCAVEC (unsigned char, nelt);
4119 for (i = 0; i < nelt / 2; i++)
4122 sel[i * 2 + 1] = i + nelt;
4124 if (can_vec_perm_p (mode, false, sel))
4126 for (i = 0; i < nelt; i++)
4128 if (can_vec_perm_p (mode, false, sel))
4133 if (dump_enabled_p ())
4134 dump_printf (MSG_MISSED_OPTIMIZATION,
4135 "interleave op not supported by target.");
4140 /* Return TRUE if vec_store_lanes is available for COUNT vectors of
4144 vect_store_lanes_supported (tree vectype, unsigned HOST_WIDE_INT count)
4146 return vect_lanes_optab_supported_p ("vec_store_lanes",
4147 vec_store_lanes_optab,
4152 /* Function vect_permute_store_chain.
4154 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
4155 a power of 2, generate interleave_high/low stmts to reorder the data
4156 correctly for the stores. Return the final references for stores in
4159 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4160 The input is 4 vectors each containing 8 elements. We assign a number to
4161 each element, the input sequence is:
4163 1st vec: 0 1 2 3 4 5 6 7
4164 2nd vec: 8 9 10 11 12 13 14 15
4165 3rd vec: 16 17 18 19 20 21 22 23
4166 4th vec: 24 25 26 27 28 29 30 31
4168 The output sequence should be:
4170 1st vec: 0 8 16 24 1 9 17 25
4171 2nd vec: 2 10 18 26 3 11 19 27
4172 3rd vec: 4 12 20 28 5 13 21 30
4173 4th vec: 6 14 22 30 7 15 23 31
4175 i.e., we interleave the contents of the four vectors in their order.
4177 We use interleave_high/low instructions to create such output. The input of
4178 each interleave_high/low operation is two vectors:
4181 the even elements of the result vector are obtained left-to-right from the
4182 high/low elements of the first vector. The odd elements of the result are
4183 obtained left-to-right from the high/low elements of the second vector.
4184 The output of interleave_high will be: 0 4 1 5
4185 and of interleave_low: 2 6 3 7
4188 The permutation is done in log LENGTH stages. In each stage interleave_high
4189 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
4190 where the first argument is taken from the first half of DR_CHAIN and the
4191 second argument from it's second half.
4194 I1: interleave_high (1st vec, 3rd vec)
4195 I2: interleave_low (1st vec, 3rd vec)
4196 I3: interleave_high (2nd vec, 4th vec)
4197 I4: interleave_low (2nd vec, 4th vec)
4199 The output for the first stage is:
4201 I1: 0 16 1 17 2 18 3 19
4202 I2: 4 20 5 21 6 22 7 23
4203 I3: 8 24 9 25 10 26 11 27
4204 I4: 12 28 13 29 14 30 15 31
4206 The output of the second stage, i.e. the final result is:
4208 I1: 0 8 16 24 1 9 17 25
4209 I2: 2 10 18 26 3 11 19 27
4210 I3: 4 12 20 28 5 13 21 30
4211 I4: 6 14 22 30 7 15 23 31. */
4214 vect_permute_store_chain (vec<tree> dr_chain,
4215 unsigned int length,
4217 gimple_stmt_iterator *gsi,
4218 vec<tree> *result_chain)
4220 tree vect1, vect2, high, low;
4222 tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
4223 tree perm_mask_low, perm_mask_high;
4225 unsigned int j, nelt = TYPE_VECTOR_SUBPARTS (vectype);
4226 unsigned char *sel = XALLOCAVEC (unsigned char, nelt);
4228 result_chain->quick_grow (length);
4229 memcpy (result_chain->address (), dr_chain.address (),
4230 length * sizeof (tree));
4232 for (i = 0, n = nelt / 2; i < n; i++)
4235 sel[i * 2 + 1] = i + nelt;
4237 perm_mask_high = vect_gen_perm_mask (vectype, sel);
4238 gcc_assert (perm_mask_high != NULL);
4240 for (i = 0; i < nelt; i++)
4242 perm_mask_low = vect_gen_perm_mask (vectype, sel);
4243 gcc_assert (perm_mask_low != NULL);
4245 for (i = 0, n = exact_log2 (length); i < n; i++)
4247 for (j = 0; j < length/2; j++)
4249 vect1 = dr_chain[j];
4250 vect2 = dr_chain[j+length/2];
4252 /* Create interleaving stmt:
4253 high = VEC_PERM_EXPR <vect1, vect2, {0, nelt, 1, nelt+1, ...}> */
4254 high = make_temp_ssa_name (vectype, NULL, "vect_inter_high");
4256 = gimple_build_assign_with_ops (VEC_PERM_EXPR, high,
4257 vect1, vect2, perm_mask_high);
4258 vect_finish_stmt_generation (stmt, perm_stmt, gsi);
4259 (*result_chain)[2*j] = high;
4261 /* Create interleaving stmt:
4262 low = VEC_PERM_EXPR <vect1, vect2, {nelt/2, nelt*3/2, nelt/2+1,
4263 nelt*3/2+1, ...}> */
4264 low = make_temp_ssa_name (vectype, NULL, "vect_inter_low");
4266 = gimple_build_assign_with_ops (VEC_PERM_EXPR, low,
4267 vect1, vect2, perm_mask_low);
4268 vect_finish_stmt_generation (stmt, perm_stmt, gsi);
4269 (*result_chain)[2*j+1] = low;
4271 memcpy (dr_chain.address (), result_chain->address (),
4272 length * sizeof (tree));
4276 /* Function vect_setup_realignment
4278 This function is called when vectorizing an unaligned load using
4279 the dr_explicit_realign[_optimized] scheme.
4280 This function generates the following code at the loop prolog:
4283 x msq_init = *(floor(p)); # prolog load
4284 realignment_token = call target_builtin;
4286 x msq = phi (msq_init, ---)
4288 The stmts marked with x are generated only for the case of
4289 dr_explicit_realign_optimized.
4291 The code above sets up a new (vector) pointer, pointing to the first
4292 location accessed by STMT, and a "floor-aligned" load using that pointer.
4293 It also generates code to compute the "realignment-token" (if the relevant
4294 target hook was defined), and creates a phi-node at the loop-header bb
4295 whose arguments are the result of the prolog-load (created by this
4296 function) and the result of a load that takes place in the loop (to be
4297 created by the caller to this function).
4299 For the case of dr_explicit_realign_optimized:
4300 The caller to this function uses the phi-result (msq) to create the
4301 realignment code inside the loop, and sets up the missing phi argument,
4304 msq = phi (msq_init, lsq)
4305 lsq = *(floor(p')); # load in loop
4306 result = realign_load (msq, lsq, realignment_token);
4308 For the case of dr_explicit_realign:
4310 msq = *(floor(p)); # load in loop
4312 lsq = *(floor(p')); # load in loop
4313 result = realign_load (msq, lsq, realignment_token);
4316 STMT - (scalar) load stmt to be vectorized. This load accesses
4317 a memory location that may be unaligned.
4318 BSI - place where new code is to be inserted.
4319 ALIGNMENT_SUPPORT_SCHEME - which of the two misalignment handling schemes
4323 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
4324 target hook, if defined.
4325 Return value - the result of the loop-header phi node. */
4328 vect_setup_realignment (gimple stmt, gimple_stmt_iterator *gsi,
4329 tree *realignment_token,
4330 enum dr_alignment_support alignment_support_scheme,
4332 struct loop **at_loop)
4334 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4335 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
4336 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4337 struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
4338 struct loop *loop = NULL;
4340 tree scalar_dest = gimple_assign_lhs (stmt);
4347 tree msq_init = NULL_TREE;
4350 tree msq = NULL_TREE;
4351 gimple_seq stmts = NULL;
4353 bool compute_in_loop = false;
4354 bool nested_in_vect_loop = false;
4355 struct loop *containing_loop = (gimple_bb (stmt))->loop_father;
4356 struct loop *loop_for_initial_load = NULL;
4360 loop = LOOP_VINFO_LOOP (loop_vinfo);
4361 nested_in_vect_loop = nested_in_vect_loop_p (loop, stmt);
4364 gcc_assert (alignment_support_scheme == dr_explicit_realign
4365 || alignment_support_scheme == dr_explicit_realign_optimized);
4367 /* We need to generate three things:
4368 1. the misalignment computation
4369 2. the extra vector load (for the optimized realignment scheme).
4370 3. the phi node for the two vectors from which the realignment is
4371 done (for the optimized realignment scheme). */
4373 /* 1. Determine where to generate the misalignment computation.
4375 If INIT_ADDR is NULL_TREE, this indicates that the misalignment
4376 calculation will be generated by this function, outside the loop (in the
4377 preheader). Otherwise, INIT_ADDR had already been computed for us by the
4378 caller, inside the loop.
4380 Background: If the misalignment remains fixed throughout the iterations of
4381 the loop, then both realignment schemes are applicable, and also the
4382 misalignment computation can be done outside LOOP. This is because we are
4383 vectorizing LOOP, and so the memory accesses in LOOP advance in steps that
4384 are a multiple of VS (the Vector Size), and therefore the misalignment in
4385 different vectorized LOOP iterations is always the same.
4386 The problem arises only if the memory access is in an inner-loop nested
4387 inside LOOP, which is now being vectorized using outer-loop vectorization.
4388 This is the only case when the misalignment of the memory access may not
4389 remain fixed throughout the iterations of the inner-loop (as explained in
4390 detail in vect_supportable_dr_alignment). In this case, not only is the
4391 optimized realignment scheme not applicable, but also the misalignment
4392 computation (and generation of the realignment token that is passed to
4393 REALIGN_LOAD) have to be done inside the loop.
4395 In short, INIT_ADDR indicates whether we are in a COMPUTE_IN_LOOP mode
4396 or not, which in turn determines if the misalignment is computed inside
4397 the inner-loop, or outside LOOP. */
4399 if (init_addr != NULL_TREE || !loop_vinfo)
4401 compute_in_loop = true;
4402 gcc_assert (alignment_support_scheme == dr_explicit_realign);
4406 /* 2. Determine where to generate the extra vector load.
4408 For the optimized realignment scheme, instead of generating two vector
4409 loads in each iteration, we generate a single extra vector load in the
4410 preheader of the loop, and in each iteration reuse the result of the
4411 vector load from the previous iteration. In case the memory access is in
4412 an inner-loop nested inside LOOP, which is now being vectorized using
4413 outer-loop vectorization, we need to determine whether this initial vector
4414 load should be generated at the preheader of the inner-loop, or can be
4415 generated at the preheader of LOOP. If the memory access has no evolution
4416 in LOOP, it can be generated in the preheader of LOOP. Otherwise, it has
4417 to be generated inside LOOP (in the preheader of the inner-loop). */
4419 if (nested_in_vect_loop)
4421 tree outerloop_step = STMT_VINFO_DR_STEP (stmt_info);
4422 bool invariant_in_outerloop =
4423 (tree_int_cst_compare (outerloop_step, size_zero_node) == 0);
4424 loop_for_initial_load = (invariant_in_outerloop ? loop : loop->inner);
4427 loop_for_initial_load = loop;
4429 *at_loop = loop_for_initial_load;
4431 if (loop_for_initial_load)
4432 pe = loop_preheader_edge (loop_for_initial_load);
4434 /* 3. For the case of the optimized realignment, create the first vector
4435 load at the loop preheader. */
4437 if (alignment_support_scheme == dr_explicit_realign_optimized)
4439 /* Create msq_init = *(floor(p1)) in the loop preheader */
4441 gcc_assert (!compute_in_loop);
4442 vec_dest = vect_create_destination_var (scalar_dest, vectype);
4443 ptr = vect_create_data_ref_ptr (stmt, vectype, loop_for_initial_load,
4444 NULL_TREE, &init_addr, NULL, &inc,
4446 new_temp = copy_ssa_name (ptr, NULL);
4447 new_stmt = gimple_build_assign_with_ops
4448 (BIT_AND_EXPR, new_temp, ptr,
4449 build_int_cst (TREE_TYPE (ptr),
4450 -(HOST_WIDE_INT)TYPE_ALIGN_UNIT (vectype)));
4451 new_bb = gsi_insert_on_edge_immediate (pe, new_stmt);
4452 gcc_assert (!new_bb);
4454 = build2 (MEM_REF, TREE_TYPE (vec_dest), new_temp,
4455 build_int_cst (reference_alias_ptr_type (DR_REF (dr)), 0));
4456 new_stmt = gimple_build_assign (vec_dest, data_ref);
4457 new_temp = make_ssa_name (vec_dest, new_stmt);
4458 gimple_assign_set_lhs (new_stmt, new_temp);
4461 new_bb = gsi_insert_on_edge_immediate (pe, new_stmt);
4462 gcc_assert (!new_bb);
4465 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
4467 msq_init = gimple_assign_lhs (new_stmt);
4470 /* 4. Create realignment token using a target builtin, if available.
4471 It is done either inside the containing loop, or before LOOP (as
4472 determined above). */
4474 if (targetm.vectorize.builtin_mask_for_load)
4478 /* Compute INIT_ADDR - the initial addressed accessed by this memref. */
4481 /* Generate the INIT_ADDR computation outside LOOP. */
4482 init_addr = vect_create_addr_base_for_vector_ref (stmt, &stmts,
4486 pe = loop_preheader_edge (loop);
4487 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
4488 gcc_assert (!new_bb);
4491 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
4494 builtin_decl = targetm.vectorize.builtin_mask_for_load ();
4495 new_stmt = gimple_build_call (builtin_decl, 1, init_addr);
4497 vect_create_destination_var (scalar_dest,
4498 gimple_call_return_type (new_stmt));
4499 new_temp = make_ssa_name (vec_dest, new_stmt);
4500 gimple_call_set_lhs (new_stmt, new_temp);
4502 if (compute_in_loop)
4503 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
4506 /* Generate the misalignment computation outside LOOP. */
4507 pe = loop_preheader_edge (loop);
4508 new_bb = gsi_insert_on_edge_immediate (pe, new_stmt);
4509 gcc_assert (!new_bb);
4512 *realignment_token = gimple_call_lhs (new_stmt);
4514 /* The result of the CALL_EXPR to this builtin is determined from
4515 the value of the parameter and no global variables are touched
4516 which makes the builtin a "const" function. Requiring the
4517 builtin to have the "const" attribute makes it unnecessary
4518 to call mark_call_clobbered. */
4519 gcc_assert (TREE_READONLY (builtin_decl));
4522 if (alignment_support_scheme == dr_explicit_realign)
4525 gcc_assert (!compute_in_loop);
4526 gcc_assert (alignment_support_scheme == dr_explicit_realign_optimized);
4529 /* 5. Create msq = phi <msq_init, lsq> in loop */
4531 pe = loop_preheader_edge (containing_loop);
4532 vec_dest = vect_create_destination_var (scalar_dest, vectype);
4533 msq = make_ssa_name (vec_dest, NULL);
4534 phi_stmt = create_phi_node (msq, containing_loop->header);
4535 add_phi_arg (phi_stmt, msq_init, pe, UNKNOWN_LOCATION);
4541 /* Function vect_grouped_load_supported.
4543 Returns TRUE if even and odd permutations are supported,
4544 and FALSE otherwise. */
4547 vect_grouped_load_supported (tree vectype, unsigned HOST_WIDE_INT count)
4549 enum machine_mode mode = TYPE_MODE (vectype);
4551 /* vect_permute_load_chain requires the group size to be a power of two. */
4552 if (exact_log2 (count) == -1)
4554 if (dump_enabled_p ())
4555 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
4556 "the size of the group of accesses"
4557 " is not a power of 2");
4561 /* Check that the permutation is supported. */
4562 if (VECTOR_MODE_P (mode))
4564 unsigned int i, nelt = GET_MODE_NUNITS (mode);
4565 unsigned char *sel = XALLOCAVEC (unsigned char, nelt);
4567 for (i = 0; i < nelt; i++)
4569 if (can_vec_perm_p (mode, false, sel))
4571 for (i = 0; i < nelt; i++)
4573 if (can_vec_perm_p (mode, false, sel))
4578 if (dump_enabled_p ())
4579 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
4580 "extract even/odd not supported by target");
4584 /* Return TRUE if vec_load_lanes is available for COUNT vectors of
4588 vect_load_lanes_supported (tree vectype, unsigned HOST_WIDE_INT count)
4590 return vect_lanes_optab_supported_p ("vec_load_lanes",
4591 vec_load_lanes_optab,
4595 /* Function vect_permute_load_chain.
4597 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
4598 a power of 2, generate extract_even/odd stmts to reorder the input data
4599 correctly. Return the final references for loads in RESULT_CHAIN.
4601 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4602 The input is 4 vectors each containing 8 elements. We assign a number to each
4603 element, the input sequence is:
4605 1st vec: 0 1 2 3 4 5 6 7
4606 2nd vec: 8 9 10 11 12 13 14 15
4607 3rd vec: 16 17 18 19 20 21 22 23
4608 4th vec: 24 25 26 27 28 29 30 31
4610 The output sequence should be:
4612 1st vec: 0 4 8 12 16 20 24 28
4613 2nd vec: 1 5 9 13 17 21 25 29
4614 3rd vec: 2 6 10 14 18 22 26 30
4615 4th vec: 3 7 11 15 19 23 27 31
4617 i.e., the first output vector should contain the first elements of each
4618 interleaving group, etc.
4620 We use extract_even/odd instructions to create such output. The input of
4621 each extract_even/odd operation is two vectors
4625 and the output is the vector of extracted even/odd elements. The output of
4626 extract_even will be: 0 2 4 6
4627 and of extract_odd: 1 3 5 7
4630 The permutation is done in log LENGTH stages. In each stage extract_even
4631 and extract_odd stmts are created for each pair of vectors in DR_CHAIN in
4632 their order. In our example,
4634 E1: extract_even (1st vec, 2nd vec)
4635 E2: extract_odd (1st vec, 2nd vec)
4636 E3: extract_even (3rd vec, 4th vec)
4637 E4: extract_odd (3rd vec, 4th vec)
4639 The output for the first stage will be:
4641 E1: 0 2 4 6 8 10 12 14
4642 E2: 1 3 5 7 9 11 13 15
4643 E3: 16 18 20 22 24 26 28 30
4644 E4: 17 19 21 23 25 27 29 31
4646 In order to proceed and create the correct sequence for the next stage (or
4647 for the correct output, if the second stage is the last one, as in our
4648 example), we first put the output of extract_even operation and then the
4649 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
4650 The input for the second stage is:
4652 1st vec (E1): 0 2 4 6 8 10 12 14
4653 2nd vec (E3): 16 18 20 22 24 26 28 30
4654 3rd vec (E2): 1 3 5 7 9 11 13 15
4655 4th vec (E4): 17 19 21 23 25 27 29 31
4657 The output of the second stage:
4659 E1: 0 4 8 12 16 20 24 28
4660 E2: 2 6 10 14 18 22 26 30
4661 E3: 1 5 9 13 17 21 25 29
4662 E4: 3 7 11 15 19 23 27 31
4664 And RESULT_CHAIN after reordering:
4666 1st vec (E1): 0 4 8 12 16 20 24 28
4667 2nd vec (E3): 1 5 9 13 17 21 25 29
4668 3rd vec (E2): 2 6 10 14 18 22 26 30
4669 4th vec (E4): 3 7 11 15 19 23 27 31. */
4672 vect_permute_load_chain (vec<tree> dr_chain,
4673 unsigned int length,
4675 gimple_stmt_iterator *gsi,
4676 vec<tree> *result_chain)
4678 tree data_ref, first_vect, second_vect;
4679 tree perm_mask_even, perm_mask_odd;
4681 tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
4682 unsigned int i, j, log_length = exact_log2 (length);
4683 unsigned nelt = TYPE_VECTOR_SUBPARTS (vectype);
4684 unsigned char *sel = XALLOCAVEC (unsigned char, nelt);
4686 result_chain->quick_grow (length);
4687 memcpy (result_chain->address (), dr_chain.address (),
4688 length * sizeof (tree));
4690 for (i = 0; i < nelt; ++i)
4692 perm_mask_even = vect_gen_perm_mask (vectype, sel);
4693 gcc_assert (perm_mask_even != NULL);
4695 for (i = 0; i < nelt; ++i)
4697 perm_mask_odd = vect_gen_perm_mask (vectype, sel);
4698 gcc_assert (perm_mask_odd != NULL);
4700 for (i = 0; i < log_length; i++)
4702 for (j = 0; j < length; j += 2)
4704 first_vect = dr_chain[j];
4705 second_vect = dr_chain[j+1];
4707 /* data_ref = permute_even (first_data_ref, second_data_ref); */
4708 data_ref = make_temp_ssa_name (vectype, NULL, "vect_perm_even");
4709 perm_stmt = gimple_build_assign_with_ops (VEC_PERM_EXPR, data_ref,
4710 first_vect, second_vect,
4712 vect_finish_stmt_generation (stmt, perm_stmt, gsi);
4713 (*result_chain)[j/2] = data_ref;
4715 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
4716 data_ref = make_temp_ssa_name (vectype, NULL, "vect_perm_odd");
4717 perm_stmt = gimple_build_assign_with_ops (VEC_PERM_EXPR, data_ref,
4718 first_vect, second_vect,
4720 vect_finish_stmt_generation (stmt, perm_stmt, gsi);
4721 (*result_chain)[j/2+length/2] = data_ref;
4723 memcpy (dr_chain.address (), result_chain->address (),
4724 length * sizeof (tree));
4729 /* Function vect_transform_grouped_load.
4731 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
4732 to perform their permutation and ascribe the result vectorized statements to
4733 the scalar statements.
4737 vect_transform_grouped_load (gimple stmt, vec<tree> dr_chain, int size,
4738 gimple_stmt_iterator *gsi)
4740 vec<tree> result_chain = vNULL;
4742 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
4743 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
4744 vectors, that are ready for vector computation. */
4745 result_chain.create (size);
4746 vect_permute_load_chain (dr_chain, size, stmt, gsi, &result_chain);
4747 vect_record_grouped_load_vectors (stmt, result_chain);
4748 result_chain.release ();
4751 /* RESULT_CHAIN contains the output of a group of grouped loads that were
4752 generated as part of the vectorization of STMT. Assign the statement
4753 for each vector to the associated scalar statement. */
4756 vect_record_grouped_load_vectors (gimple stmt, vec<tree> result_chain)
4758 gimple first_stmt = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt));
4759 gimple next_stmt, new_stmt;
4760 unsigned int i, gap_count;
4763 /* Put a permuted data-ref in the VECTORIZED_STMT field.
4764 Since we scan the chain starting from it's first node, their order
4765 corresponds the order of data-refs in RESULT_CHAIN. */
4766 next_stmt = first_stmt;
4768 FOR_EACH_VEC_ELT (result_chain, i, tmp_data_ref)
4773 /* Skip the gaps. Loads created for the gaps will be removed by dead
4774 code elimination pass later. No need to check for the first stmt in
4775 the group, since it always exists.
4776 GROUP_GAP is the number of steps in elements from the previous
4777 access (if there is no gap GROUP_GAP is 1). We skip loads that
4778 correspond to the gaps. */
4779 if (next_stmt != first_stmt
4780 && gap_count < GROUP_GAP (vinfo_for_stmt (next_stmt)))
4788 new_stmt = SSA_NAME_DEF_STMT (tmp_data_ref);
4789 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
4790 copies, and we put the new vector statement in the first available
4792 if (!STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt)))
4793 STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt)) = new_stmt;
4796 if (!GROUP_SAME_DR_STMT (vinfo_for_stmt (next_stmt)))
4799 STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt));
4801 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (prev_stmt));
4804 prev_stmt = rel_stmt;
4806 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (rel_stmt));
4809 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (prev_stmt)) =
4814 next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
4816 /* If NEXT_STMT accesses the same DR as the previous statement,
4817 put the same TMP_DATA_REF as its vectorized statement; otherwise
4818 get the next data-ref from RESULT_CHAIN. */
4819 if (!next_stmt || !GROUP_SAME_DR_STMT (vinfo_for_stmt (next_stmt)))
4825 /* Function vect_force_dr_alignment_p.
4827 Returns whether the alignment of a DECL can be forced to be aligned
4828 on ALIGNMENT bit boundary. */
4831 vect_can_force_dr_alignment_p (const_tree decl, unsigned int alignment)
4833 if (TREE_CODE (decl) != VAR_DECL)
4836 /* We cannot change alignment of common or external symbols as another
4837 translation unit may contain a definition with lower alignment.
4838 The rules of common symbol linking mean that the definition
4839 will override the common symbol. The same is true for constant
4840 pool entries which may be shared and are not properly merged
4842 if (DECL_EXTERNAL (decl)
4843 || DECL_COMMON (decl)
4844 || DECL_IN_CONSTANT_POOL (decl))
4847 if (TREE_ASM_WRITTEN (decl))
4850 /* Do not override the alignment as specified by the ABI when the used
4851 attribute is set. */
4852 if (DECL_PRESERVE_P (decl))
4855 /* Do not override explicit alignment set by the user when an explicit
4856 section name is also used. This is a common idiom used by many
4857 software projects. */
4858 if (DECL_SECTION_NAME (decl) != NULL_TREE
4859 && !DECL_HAS_IMPLICIT_SECTION_NAME_P (decl))
4862 if (TREE_STATIC (decl))
4863 return (alignment <= MAX_OFILE_ALIGNMENT);
4865 return (alignment <= MAX_STACK_ALIGNMENT);
4869 /* Return whether the data reference DR is supported with respect to its
4871 If CHECK_ALIGNED_ACCESSES is TRUE, check if the access is supported even
4872 it is aligned, i.e., check if it is possible to vectorize it with different
4875 enum dr_alignment_support
4876 vect_supportable_dr_alignment (struct data_reference *dr,
4877 bool check_aligned_accesses)
4879 gimple stmt = DR_STMT (dr);
4880 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4881 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
4882 enum machine_mode mode = TYPE_MODE (vectype);
4883 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4884 struct loop *vect_loop = NULL;
4885 bool nested_in_vect_loop = false;
4887 if (aligned_access_p (dr) && !check_aligned_accesses)
4892 vect_loop = LOOP_VINFO_LOOP (loop_vinfo);
4893 nested_in_vect_loop = nested_in_vect_loop_p (vect_loop, stmt);
4896 /* Possibly unaligned access. */
4898 /* We can choose between using the implicit realignment scheme (generating
4899 a misaligned_move stmt) and the explicit realignment scheme (generating
4900 aligned loads with a REALIGN_LOAD). There are two variants to the
4901 explicit realignment scheme: optimized, and unoptimized.
4902 We can optimize the realignment only if the step between consecutive
4903 vector loads is equal to the vector size. Since the vector memory
4904 accesses advance in steps of VS (Vector Size) in the vectorized loop, it
4905 is guaranteed that the misalignment amount remains the same throughout the
4906 execution of the vectorized loop. Therefore, we can create the
4907 "realignment token" (the permutation mask that is passed to REALIGN_LOAD)
4908 at the loop preheader.
4910 However, in the case of outer-loop vectorization, when vectorizing a
4911 memory access in the inner-loop nested within the LOOP that is now being
4912 vectorized, while it is guaranteed that the misalignment of the
4913 vectorized memory access will remain the same in different outer-loop
4914 iterations, it is *not* guaranteed that is will remain the same throughout
4915 the execution of the inner-loop. This is because the inner-loop advances
4916 with the original scalar step (and not in steps of VS). If the inner-loop
4917 step happens to be a multiple of VS, then the misalignment remains fixed
4918 and we can use the optimized realignment scheme. For example:
4924 When vectorizing the i-loop in the above example, the step between
4925 consecutive vector loads is 1, and so the misalignment does not remain
4926 fixed across the execution of the inner-loop, and the realignment cannot
4927 be optimized (as illustrated in the following pseudo vectorized loop):
4929 for (i=0; i<N; i+=4)
4930 for (j=0; j<M; j++){
4931 vs += vp[i+j]; // misalignment of &vp[i+j] is {0,1,2,3,0,1,2,3,...}
4932 // when j is {0,1,2,3,4,5,6,7,...} respectively.
4933 // (assuming that we start from an aligned address).
4936 We therefore have to use the unoptimized realignment scheme:
4938 for (i=0; i<N; i+=4)
4939 for (j=k; j<M; j+=4)
4940 vs += vp[i+j]; // misalignment of &vp[i+j] is always k (assuming
4941 // that the misalignment of the initial address is
4944 The loop can then be vectorized as follows:
4946 for (k=0; k<4; k++){
4947 rt = get_realignment_token (&vp[k]);
4948 for (i=0; i<N; i+=4){
4950 for (j=k; j<M; j+=4){
4952 va = REALIGN_LOAD <v1,v2,rt>;
4959 if (DR_IS_READ (dr))
4961 bool is_packed = false;
4962 tree type = (TREE_TYPE (DR_REF (dr)));
4964 if (optab_handler (vec_realign_load_optab, mode) != CODE_FOR_nothing
4965 && (!targetm.vectorize.builtin_mask_for_load
4966 || targetm.vectorize.builtin_mask_for_load ()))
4968 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
4969 if ((nested_in_vect_loop
4970 && (TREE_INT_CST_LOW (DR_STEP (dr))
4971 != GET_MODE_SIZE (TYPE_MODE (vectype))))
4973 return dr_explicit_realign;
4975 return dr_explicit_realign_optimized;
4977 if (!known_alignment_for_access_p (dr))
4978 is_packed = not_size_aligned (DR_REF (dr));
4980 if (targetm.vectorize.
4981 support_vector_misalignment (mode, type,
4982 DR_MISALIGNMENT (dr), is_packed))
4983 /* Can't software pipeline the loads, but can at least do them. */
4984 return dr_unaligned_supported;
4988 bool is_packed = false;
4989 tree type = (TREE_TYPE (DR_REF (dr)));
4991 if (!known_alignment_for_access_p (dr))
4992 is_packed = not_size_aligned (DR_REF (dr));
4994 if (targetm.vectorize.
4995 support_vector_misalignment (mode, type,
4996 DR_MISALIGNMENT (dr), is_packed))
4997 return dr_unaligned_supported;
5001 return dr_unaligned_unsupported;