2 Copyright (C) 2003-2021 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Loop and basic block vectorizer.
23 This file contains drivers for the three vectorizers:
24 (1) loop vectorizer (inter-iteration parallelism),
25 (2) loop-aware SLP (intra-iteration parallelism) (invoked by the loop
27 (3) BB vectorizer (out-of-loops), aka SLP
29 The rest of the vectorizer's code is organized as follows:
30 - tree-vect-loop.c - loop specific parts such as reductions, etc. These are
31 used by drivers (1) and (2).
32 - tree-vect-loop-manip.c - vectorizer's loop control-flow utilities, used by
34 - tree-vect-slp.c - BB vectorization specific analysis and transformation,
35 used by drivers (2) and (3).
36 - tree-vect-stmts.c - statements analysis and transformation (used by all).
37 - tree-vect-data-refs.c - vectorizer specific data-refs analysis and
38 manipulations (used by all).
39 - tree-vect-patterns.c - vectorizable code patterns detector (used by all)
41 Here's a poor attempt at illustrating that:
44 loop_vect() loop_aware_slp() slp_vect()
47 tree-vect-loop.c tree-vect-slp.c
52 tree-vect-stmts.c tree-vect-data-refs.c
59 #include "coretypes.h"
64 #include "tree-pass.h"
67 #include "fold-const.h"
68 #include "stor-layout.h"
69 #include "gimple-iterator.h"
70 #include "gimple-walk.h"
71 #include "tree-ssa-loop-manip.h"
72 #include "tree-ssa-loop-niter.h"
75 #include "tree-vectorizer.h"
76 #include "tree-ssa-propagate.h"
78 #include "tree-scalar-evolution.h"
79 #include "stringpool.h"
81 #include "gimple-pretty-print.h"
82 #include "opt-problem.h"
83 #include "internal-fn.h"
84 #include "tree-ssa-sccvn.h"
86 /* Loop or bb location, with hotness information. */
87 dump_user_location_t vect_location
;
89 /* auto_purge_vect_location's dtor: reset the vect_location
90 global, to avoid stale location_t values that could reference
93 auto_purge_vect_location::~auto_purge_vect_location ()
95 vect_location
= dump_user_location_t ();
98 /* Dump a cost entry according to args to F. */
101 dump_stmt_cost (FILE *f
, int count
, enum vect_cost_for_stmt kind
,
102 stmt_vec_info stmt_info
, tree
, int misalign
, unsigned cost
,
103 enum vect_cost_model_location where
)
107 print_gimple_expr (f
, STMT_VINFO_STMT (stmt_info
), 0, TDF_SLIM
);
111 fprintf (f
, "<unknown> ");
112 fprintf (f
, "%d times ", count
);
113 const char *ks
= "unknown";
131 case vector_gather_load
:
132 ks
= "vector_gather_load";
135 ks
= "unaligned_load";
137 case unaligned_store
:
138 ks
= "unaligned_store";
143 case vector_scatter_store
:
144 ks
= "vector_scatter_store";
147 ks
= "vec_to_scalar";
150 ks
= "scalar_to_vec";
152 case cond_branch_not_taken
:
153 ks
= "cond_branch_not_taken";
155 case cond_branch_taken
:
156 ks
= "cond_branch_taken";
161 case vec_promote_demote
:
162 ks
= "vec_promote_demote";
165 ks
= "vec_construct";
168 fprintf (f
, "%s ", ks
);
169 if (kind
== unaligned_load
|| kind
== unaligned_store
)
170 fprintf (f
, "(misalign %d) ", misalign
);
171 fprintf (f
, "costs %u ", cost
);
172 const char *ws
= "unknown";
185 fprintf (f
, "in %s\n", ws
);
188 /* For mapping simduid to vectorization factor. */
190 class simduid_to_vf
: public free_ptr_hash
<simduid_to_vf
>
193 unsigned int simduid
;
196 /* hash_table support. */
197 static inline hashval_t
hash (const simduid_to_vf
*);
198 static inline int equal (const simduid_to_vf
*, const simduid_to_vf
*);
202 simduid_to_vf::hash (const simduid_to_vf
*p
)
208 simduid_to_vf::equal (const simduid_to_vf
*p1
, const simduid_to_vf
*p2
)
210 return p1
->simduid
== p2
->simduid
;
213 /* This hash maps the OMP simd array to the corresponding simduid used
214 to index into it. Like thus,
216 _7 = GOMP_SIMD_LANE (simduid.0)
222 This hash maps from the OMP simd array (D.1737[]) to DECL_UID of
225 struct simd_array_to_simduid
: free_ptr_hash
<simd_array_to_simduid
>
228 unsigned int simduid
;
230 /* hash_table support. */
231 static inline hashval_t
hash (const simd_array_to_simduid
*);
232 static inline int equal (const simd_array_to_simduid
*,
233 const simd_array_to_simduid
*);
237 simd_array_to_simduid::hash (const simd_array_to_simduid
*p
)
239 return DECL_UID (p
->decl
);
243 simd_array_to_simduid::equal (const simd_array_to_simduid
*p1
,
244 const simd_array_to_simduid
*p2
)
246 return p1
->decl
== p2
->decl
;
249 /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LAST_LANE,
250 into their corresponding constants and remove
251 IFN_GOMP_SIMD_ORDERED_{START,END}. */
254 adjust_simduid_builtins (hash_table
<simduid_to_vf
> *htab
)
258 FOR_EACH_BB_FN (bb
, cfun
)
260 gimple_stmt_iterator i
;
262 for (i
= gsi_start_bb (bb
); !gsi_end_p (i
); )
265 enum internal_fn ifn
;
266 gimple
*stmt
= gsi_stmt (i
);
268 if (!is_gimple_call (stmt
)
269 || !gimple_call_internal_p (stmt
))
274 ifn
= gimple_call_internal_fn (stmt
);
277 case IFN_GOMP_SIMD_LANE
:
278 case IFN_GOMP_SIMD_VF
:
279 case IFN_GOMP_SIMD_LAST_LANE
:
281 case IFN_GOMP_SIMD_ORDERED_START
:
282 case IFN_GOMP_SIMD_ORDERED_END
:
283 if (integer_onep (gimple_call_arg (stmt
, 0)))
285 enum built_in_function bcode
286 = (ifn
== IFN_GOMP_SIMD_ORDERED_START
287 ? BUILT_IN_GOMP_ORDERED_START
288 : BUILT_IN_GOMP_ORDERED_END
);
290 = gimple_build_call (builtin_decl_explicit (bcode
), 0);
291 gimple_move_vops (g
, stmt
);
292 gsi_replace (&i
, g
, true);
295 gsi_remove (&i
, true);
296 unlink_stmt_vdef (stmt
);
302 tree arg
= gimple_call_arg (stmt
, 0);
303 gcc_assert (arg
!= NULL_TREE
);
304 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
305 simduid_to_vf
*p
= NULL
, data
;
306 data
.simduid
= DECL_UID (SSA_NAME_VAR (arg
));
307 /* Need to nullify loop safelen field since it's value is not
308 valid after transformation. */
309 if (bb
->loop_father
&& bb
->loop_father
->safelen
> 0)
310 bb
->loop_father
->safelen
= 0;
313 p
= htab
->find (&data
);
319 case IFN_GOMP_SIMD_VF
:
320 t
= build_int_cst (unsigned_type_node
, vf
);
322 case IFN_GOMP_SIMD_LANE
:
323 t
= build_int_cst (unsigned_type_node
, 0);
325 case IFN_GOMP_SIMD_LAST_LANE
:
326 t
= gimple_call_arg (stmt
, 1);
331 tree lhs
= gimple_call_lhs (stmt
);
333 replace_uses_by (lhs
, t
);
335 gsi_remove (&i
, true);
340 /* Helper structure for note_simd_array_uses. */
342 struct note_simd_array_uses_struct
344 hash_table
<simd_array_to_simduid
> **htab
;
345 unsigned int simduid
;
348 /* Callback for note_simd_array_uses, called through walk_gimple_op. */
351 note_simd_array_uses_cb (tree
*tp
, int *walk_subtrees
, void *data
)
353 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
354 struct note_simd_array_uses_struct
*ns
355 = (struct note_simd_array_uses_struct
*) wi
->info
;
360 && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp
))
361 && DECL_CONTEXT (*tp
) == current_function_decl
)
363 simd_array_to_simduid data
;
365 *ns
->htab
= new hash_table
<simd_array_to_simduid
> (15);
367 data
.simduid
= ns
->simduid
;
368 simd_array_to_simduid
**slot
= (*ns
->htab
)->find_slot (&data
, INSERT
);
371 simd_array_to_simduid
*p
= XNEW (simd_array_to_simduid
);
375 else if ((*slot
)->simduid
!= ns
->simduid
)
376 (*slot
)->simduid
= -1U;
382 /* Find "omp simd array" temporaries and map them to corresponding
386 note_simd_array_uses (hash_table
<simd_array_to_simduid
> **htab
)
389 gimple_stmt_iterator gsi
;
390 struct walk_stmt_info wi
;
391 struct note_simd_array_uses_struct ns
;
393 memset (&wi
, 0, sizeof (wi
));
397 FOR_EACH_BB_FN (bb
, cfun
)
398 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
400 gimple
*stmt
= gsi_stmt (gsi
);
401 if (!is_gimple_call (stmt
) || !gimple_call_internal_p (stmt
))
403 switch (gimple_call_internal_fn (stmt
))
405 case IFN_GOMP_SIMD_LANE
:
406 case IFN_GOMP_SIMD_VF
:
407 case IFN_GOMP_SIMD_LAST_LANE
:
412 tree lhs
= gimple_call_lhs (stmt
);
413 if (lhs
== NULL_TREE
)
415 imm_use_iterator use_iter
;
417 ns
.simduid
= DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt
, 0)));
418 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, lhs
)
419 if (!is_gimple_debug (use_stmt
))
420 walk_gimple_op (use_stmt
, note_simd_array_uses_cb
, &wi
);
424 /* Shrink arrays with "omp simd array" attribute to the corresponding
425 vectorization factor. */
429 (hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
,
430 hash_table
<simduid_to_vf
> *simduid_to_vf_htab
)
432 for (hash_table
<simd_array_to_simduid
>::iterator iter
433 = simd_array_to_simduid_htab
->begin ();
434 iter
!= simd_array_to_simduid_htab
->end (); ++iter
)
435 if ((*iter
)->simduid
!= -1U)
437 tree decl
= (*iter
)->decl
;
439 if (simduid_to_vf_htab
)
441 simduid_to_vf
*p
= NULL
, data
;
442 data
.simduid
= (*iter
)->simduid
;
443 p
= simduid_to_vf_htab
->find (&data
);
448 = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl
)), vf
);
449 TREE_TYPE (decl
) = atype
;
450 relayout_decl (decl
);
453 delete simd_array_to_simduid_htab
;
456 /* Initialize the vec_info with kind KIND_IN and target cost data
457 TARGET_COST_DATA_IN. */
459 vec_info::vec_info (vec_info::vec_kind kind_in
, vec_info_shared
*shared_
)
462 stmt_vec_info_ro (false)
464 stmt_vec_infos
.create (50);
467 vec_info::~vec_info ()
469 for (slp_instance
&instance
: slp_instances
)
470 vect_free_slp_instance (instance
);
472 free_stmt_vec_infos ();
475 vec_info_shared::vec_info_shared ()
478 datarefs_copy (vNULL
),
483 vec_info_shared::~vec_info_shared ()
485 free_data_refs (datarefs
);
486 free_dependence_relations (ddrs
);
487 datarefs_copy
.release ();
491 vec_info_shared::save_datarefs ()
495 datarefs_copy
.reserve_exact (datarefs
.length ());
496 for (unsigned i
= 0; i
< datarefs
.length (); ++i
)
497 datarefs_copy
.quick_push (*datarefs
[i
]);
501 vec_info_shared::check_datarefs ()
505 gcc_assert (datarefs
.length () == datarefs_copy
.length ());
506 for (unsigned i
= 0; i
< datarefs
.length (); ++i
)
507 if (memcmp (&datarefs_copy
[i
], datarefs
[i
],
508 offsetof (data_reference
, alt_indices
)) != 0)
512 /* Record that STMT belongs to the vectorizable region. Create and return
513 an associated stmt_vec_info. */
516 vec_info::add_stmt (gimple
*stmt
)
518 stmt_vec_info res
= new_stmt_vec_info (stmt
);
519 set_vinfo_for_stmt (stmt
, res
);
523 /* Record that STMT belongs to the vectorizable region. Create a new
524 stmt_vec_info and mark VECINFO as being related and return the new
528 vec_info::add_pattern_stmt (gimple
*stmt
, stmt_vec_info stmt_info
)
530 stmt_vec_info res
= new_stmt_vec_info (stmt
);
531 set_vinfo_for_stmt (stmt
, res
, false);
532 STMT_VINFO_RELATED_STMT (res
) = stmt_info
;
536 /* If STMT has an associated stmt_vec_info, return that vec_info, otherwise
537 return null. It is safe to call this function on any statement, even if
538 it might not be part of the vectorizable region. */
541 vec_info::lookup_stmt (gimple
*stmt
)
543 unsigned int uid
= gimple_uid (stmt
);
544 if (uid
> 0 && uid
- 1 < stmt_vec_infos
.length ())
546 stmt_vec_info res
= stmt_vec_infos
[uid
- 1];
547 if (res
&& res
->stmt
== stmt
)
553 /* If NAME is an SSA_NAME and its definition has an associated stmt_vec_info,
554 return that stmt_vec_info, otherwise return null. It is safe to call
555 this on arbitrary operands. */
558 vec_info::lookup_def (tree name
)
560 if (TREE_CODE (name
) == SSA_NAME
561 && !SSA_NAME_IS_DEFAULT_DEF (name
))
562 return lookup_stmt (SSA_NAME_DEF_STMT (name
));
566 /* See whether there is a single non-debug statement that uses LHS and
567 whether that statement has an associated stmt_vec_info. Return the
568 stmt_vec_info if so, otherwise return null. */
571 vec_info::lookup_single_use (tree lhs
)
575 if (single_imm_use (lhs
, &dummy
, &use_stmt
))
576 return lookup_stmt (use_stmt
);
580 /* Return vectorization information about DR. */
583 vec_info::lookup_dr (data_reference
*dr
)
585 stmt_vec_info stmt_info
= lookup_stmt (DR_STMT (dr
));
586 /* DR_STMT should never refer to a stmt in a pattern replacement. */
587 gcc_checking_assert (!is_pattern_stmt_p (stmt_info
));
588 return STMT_VINFO_DR_INFO (stmt_info
->dr_aux
.stmt
);
591 /* Record that NEW_STMT_INFO now implements the same data reference
595 vec_info::move_dr (stmt_vec_info new_stmt_info
, stmt_vec_info old_stmt_info
)
597 gcc_assert (!is_pattern_stmt_p (old_stmt_info
));
598 STMT_VINFO_DR_INFO (old_stmt_info
)->stmt
= new_stmt_info
;
599 new_stmt_info
->dr_aux
= old_stmt_info
->dr_aux
;
600 STMT_VINFO_DR_WRT_VEC_LOOP (new_stmt_info
)
601 = STMT_VINFO_DR_WRT_VEC_LOOP (old_stmt_info
);
602 STMT_VINFO_GATHER_SCATTER_P (new_stmt_info
)
603 = STMT_VINFO_GATHER_SCATTER_P (old_stmt_info
);
606 /* Permanently remove the statement described by STMT_INFO from the
610 vec_info::remove_stmt (stmt_vec_info stmt_info
)
612 gcc_assert (!stmt_info
->pattern_stmt_p
);
613 set_vinfo_for_stmt (stmt_info
->stmt
, NULL
);
614 unlink_stmt_vdef (stmt_info
->stmt
);
615 gimple_stmt_iterator si
= gsi_for_stmt (stmt_info
->stmt
);
616 gsi_remove (&si
, true);
617 release_defs (stmt_info
->stmt
);
618 free_stmt_vec_info (stmt_info
);
621 /* Replace the statement at GSI by NEW_STMT, both the vectorization
622 information and the function itself. STMT_INFO describes the statement
626 vec_info::replace_stmt (gimple_stmt_iterator
*gsi
, stmt_vec_info stmt_info
,
629 gimple
*old_stmt
= stmt_info
->stmt
;
630 gcc_assert (!stmt_info
->pattern_stmt_p
&& old_stmt
== gsi_stmt (*gsi
));
631 gimple_set_uid (new_stmt
, gimple_uid (old_stmt
));
632 stmt_info
->stmt
= new_stmt
;
633 gsi_replace (gsi
, new_stmt
, true);
636 /* Insert stmts in SEQ on the VEC_INFO region entry. If CONTEXT is
637 not NULL it specifies whether to use the sub-region entry
638 determined by it, currently used for loop vectorization to insert
639 on the inner loop entry vs. the outer loop entry. */
642 vec_info::insert_seq_on_entry (stmt_vec_info context
, gimple_seq seq
)
644 if (loop_vec_info loop_vinfo
= dyn_cast
<loop_vec_info
> (this))
646 class loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
650 if (context
&& nested_in_vect_loop_p (loop
, context
))
653 pe
= loop_preheader_edge (loop
);
654 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, seq
);
655 gcc_assert (!new_bb
);
659 bb_vec_info bb_vinfo
= as_a
<bb_vec_info
> (this);
660 gimple_stmt_iterator gsi_region_begin
661 = gsi_after_labels (bb_vinfo
->bbs
[0]);
662 gsi_insert_seq_before (&gsi_region_begin
, seq
, GSI_SAME_STMT
);
666 /* Like insert_seq_on_entry but just inserts the single stmt NEW_STMT. */
669 vec_info::insert_on_entry (stmt_vec_info context
, gimple
*new_stmt
)
671 gimple_seq seq
= NULL
;
672 gimple_stmt_iterator gsi
= gsi_start (seq
);
673 gsi_insert_before_without_update (&gsi
, new_stmt
, GSI_SAME_STMT
);
674 insert_seq_on_entry (context
, seq
);
677 /* Create and initialize a new stmt_vec_info struct for STMT. */
680 vec_info::new_stmt_vec_info (gimple
*stmt
)
682 stmt_vec_info res
= XCNEW (class _stmt_vec_info
);
685 STMT_VINFO_TYPE (res
) = undef_vec_info_type
;
686 STMT_VINFO_RELEVANT (res
) = vect_unused_in_scope
;
687 STMT_VINFO_VECTORIZABLE (res
) = true;
688 STMT_VINFO_REDUC_TYPE (res
) = TREE_CODE_REDUCTION
;
689 STMT_VINFO_REDUC_CODE (res
) = ERROR_MARK
;
690 STMT_VINFO_REDUC_FN (res
) = IFN_LAST
;
691 STMT_VINFO_REDUC_IDX (res
) = -1;
692 STMT_VINFO_SLP_VECT_ONLY (res
) = false;
693 STMT_VINFO_SLP_VECT_ONLY_PATTERN (res
) = false;
694 STMT_VINFO_VEC_STMTS (res
) = vNULL
;
695 res
->reduc_initial_values
= vNULL
;
696 res
->reduc_scalar_results
= vNULL
;
698 if (is_a
<loop_vec_info
> (this)
699 && gimple_code (stmt
) == GIMPLE_PHI
700 && is_loop_header_bb_p (gimple_bb (stmt
)))
701 STMT_VINFO_DEF_TYPE (res
) = vect_unknown_def_type
;
703 STMT_VINFO_DEF_TYPE (res
) = vect_internal_def
;
705 STMT_SLP_TYPE (res
) = loop_vect
;
707 /* This is really "uninitialized" until vect_compute_data_ref_alignment. */
708 res
->dr_aux
.misalignment
= DR_MISALIGNMENT_UNINITIALIZED
;
713 /* Associate STMT with INFO. */
716 vec_info::set_vinfo_for_stmt (gimple
*stmt
, stmt_vec_info info
, bool check_ro
)
718 unsigned int uid
= gimple_uid (stmt
);
721 gcc_assert (!check_ro
|| !stmt_vec_info_ro
);
722 gcc_checking_assert (info
);
723 uid
= stmt_vec_infos
.length () + 1;
724 gimple_set_uid (stmt
, uid
);
725 stmt_vec_infos
.safe_push (info
);
729 gcc_checking_assert (info
== NULL
);
730 stmt_vec_infos
[uid
- 1] = info
;
734 /* Free the contents of stmt_vec_infos. */
737 vec_info::free_stmt_vec_infos (void)
739 for (stmt_vec_info
&info
: stmt_vec_infos
)
741 free_stmt_vec_info (info
);
742 stmt_vec_infos
.release ();
745 /* Free STMT_INFO. */
748 vec_info::free_stmt_vec_info (stmt_vec_info stmt_info
)
750 if (stmt_info
->pattern_stmt_p
)
752 gimple_set_bb (stmt_info
->stmt
, NULL
);
753 tree lhs
= gimple_get_lhs (stmt_info
->stmt
);
754 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
755 release_ssa_name (lhs
);
758 stmt_info
->reduc_initial_values
.release ();
759 stmt_info
->reduc_scalar_results
.release ();
760 STMT_VINFO_SIMD_CLONE_INFO (stmt_info
).release ();
761 STMT_VINFO_VEC_STMTS (stmt_info
).release ();
765 /* Returns true if S1 dominates S2. */
768 vect_stmt_dominates_stmt_p (gimple
*s1
, gimple
*s2
)
770 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
772 /* If bb1 is NULL, it should be a GIMPLE_NOP def stmt of an (D)
773 SSA_NAME. Assume it lives at the beginning of function and
774 thus dominates everything. */
775 if (!bb1
|| s1
== s2
)
778 /* If bb2 is NULL, it doesn't dominate any stmt with a bb. */
783 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
785 /* PHIs in the same basic block are assumed to be
786 executed all in parallel, if only one stmt is a PHI,
787 it dominates the other stmt in the same basic block. */
788 if (gimple_code (s1
) == GIMPLE_PHI
)
791 if (gimple_code (s2
) == GIMPLE_PHI
)
794 /* Inserted vectorized stmts all have UID 0 while the original stmts
795 in the IL have UID increasing within a BB. Walk from both sides
796 until we find the other stmt or a stmt with UID != 0. */
797 gimple_stmt_iterator gsi1
= gsi_for_stmt (s1
);
798 while (gimple_uid (gsi_stmt (gsi1
)) == 0)
801 if (gsi_end_p (gsi1
))
803 if (gsi_stmt (gsi1
) == s2
)
806 if (gimple_uid (gsi_stmt (gsi1
)) == -1u)
809 gimple_stmt_iterator gsi2
= gsi_for_stmt (s2
);
810 while (gimple_uid (gsi_stmt (gsi2
)) == 0)
813 if (gsi_end_p (gsi2
))
815 if (gsi_stmt (gsi2
) == s1
)
818 if (gimple_uid (gsi_stmt (gsi2
)) == -1u)
821 if (gimple_uid (gsi_stmt (gsi1
)) <= gimple_uid (gsi_stmt (gsi2
)))
826 /* A helper function to free scev and LOOP niter information, as well as
827 clear loop constraint LOOP_C_FINITE. */
830 vect_free_loop_info_assumptions (class loop
*loop
)
833 /* We need to explicitly reset upper bound information since they are
834 used even after free_numbers_of_iterations_estimates. */
835 loop
->any_upper_bound
= false;
836 loop
->any_likely_upper_bound
= false;
837 free_numbers_of_iterations_estimates (loop
);
838 loop_constraint_clear (loop
, LOOP_C_FINITE
);
841 /* If LOOP has been versioned during ifcvt, return the internal call
845 vect_loop_vectorized_call (class loop
*loop
, gcond
**cond
)
847 basic_block bb
= loop_preheader_edge (loop
)->src
;
852 if ((g
&& gimple_code (g
) == GIMPLE_COND
)
853 || !single_succ_p (bb
))
855 if (!single_pred_p (bb
))
857 bb
= single_pred (bb
);
860 if (g
&& gimple_code (g
) == GIMPLE_COND
)
863 *cond
= as_a
<gcond
*> (g
);
864 gimple_stmt_iterator gsi
= gsi_for_stmt (g
);
866 if (!gsi_end_p (gsi
))
869 if (gimple_call_internal_p (g
, IFN_LOOP_VECTORIZED
)
870 && (tree_to_shwi (gimple_call_arg (g
, 0)) == loop
->num
871 || tree_to_shwi (gimple_call_arg (g
, 1)) == loop
->num
))
878 /* If LOOP has been versioned during loop distribution, return the gurading
882 vect_loop_dist_alias_call (class loop
*loop
)
886 class loop
*outer
, *orig
;
887 gimple_stmt_iterator gsi
;
890 if (loop
->orig_loop_num
== 0)
893 orig
= get_loop (cfun
, loop
->orig_loop_num
);
896 /* The original loop is somehow destroyed. Clear the information. */
897 loop
->orig_loop_num
= 0;
902 bb
= nearest_common_dominator (CDI_DOMINATORS
, loop
->header
, orig
->header
);
904 bb
= loop_preheader_edge (loop
)->src
;
906 outer
= bb
->loop_father
;
907 entry
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
909 /* Look upward in dominance tree. */
910 for (; bb
!= entry
&& flow_bb_inside_loop_p (outer
, bb
);
911 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
914 if (g
== NULL
|| gimple_code (g
) != GIMPLE_COND
)
917 gsi
= gsi_for_stmt (g
);
923 /* The guarding internal function call must have the same distribution
925 if (gimple_call_internal_p (g
, IFN_LOOP_DIST_ALIAS
)
926 && (tree_to_shwi (gimple_call_arg (g
, 0)) == loop
->orig_loop_num
))
932 /* Set the uids of all the statements in basic blocks inside loop
933 represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal
934 call guarding the loop which has been if converted. */
936 set_uid_loop_bbs (loop_vec_info loop_vinfo
, gimple
*loop_vectorized_call
)
938 tree arg
= gimple_call_arg (loop_vectorized_call
, 1);
941 class loop
*scalar_loop
= get_loop (cfun
, tree_to_shwi (arg
));
943 LOOP_VINFO_SCALAR_LOOP (loop_vinfo
) = scalar_loop
;
944 gcc_checking_assert (vect_loop_vectorized_call (scalar_loop
)
945 == loop_vectorized_call
);
946 /* If we are going to vectorize outer loop, prevent vectorization
947 of the inner loop in the scalar loop - either the scalar loop is
948 thrown away, so it is a wasted work, or is used only for
950 if (scalar_loop
->inner
)
952 gimple
*g
= vect_loop_vectorized_call (scalar_loop
->inner
);
955 arg
= gimple_call_arg (g
, 0);
956 get_loop (cfun
, tree_to_shwi (arg
))->dont_vectorize
= true;
957 fold_loop_internal_call (g
, boolean_false_node
);
960 bbs
= get_loop_body (scalar_loop
);
961 for (i
= 0; i
< scalar_loop
->num_nodes
; i
++)
963 basic_block bb
= bbs
[i
];
964 gimple_stmt_iterator gsi
;
965 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
967 gimple
*phi
= gsi_stmt (gsi
);
968 gimple_set_uid (phi
, 0);
970 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
972 gimple
*stmt
= gsi_stmt (gsi
);
973 gimple_set_uid (stmt
, 0);
979 /* Generate vectorized code for LOOP and its epilogues. */
982 vect_transform_loops (hash_table
<simduid_to_vf
> *&simduid_to_vf_htab
,
983 loop_p loop
, gimple
*loop_vectorized_call
)
985 loop_vec_info loop_vinfo
= loop_vec_info_for_loop (loop
);
987 if (loop_vectorized_call
)
988 set_uid_loop_bbs (loop_vinfo
, loop_vectorized_call
);
990 unsigned HOST_WIDE_INT bytes
;
991 if (dump_enabled_p ())
993 if (GET_MODE_SIZE (loop_vinfo
->vector_mode
).is_constant (&bytes
))
994 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
995 "loop vectorized using %wu byte vectors\n", bytes
);
997 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
998 "loop vectorized using variable length vectors\n");
1001 loop_p new_loop
= vect_transform_loop (loop_vinfo
,
1002 loop_vectorized_call
);
1003 /* Now that the loop has been vectorized, allow it to be unrolled
1005 loop
->force_vectorize
= false;
1009 simduid_to_vf
*simduid_to_vf_data
= XNEW (simduid_to_vf
);
1010 if (!simduid_to_vf_htab
)
1011 simduid_to_vf_htab
= new hash_table
<simduid_to_vf
> (15);
1012 simduid_to_vf_data
->simduid
= DECL_UID (loop
->simduid
);
1013 simduid_to_vf_data
->vf
= loop_vinfo
->vectorization_factor
;
1014 *simduid_to_vf_htab
->find_slot (simduid_to_vf_data
, INSERT
)
1015 = simduid_to_vf_data
;
1018 /* Epilogue of vectorized loop must be vectorized too. */
1020 vect_transform_loops (simduid_to_vf_htab
, new_loop
, NULL
);
1023 /* Try to vectorize LOOP. */
1026 try_vectorize_loop_1 (hash_table
<simduid_to_vf
> *&simduid_to_vf_htab
,
1027 unsigned *num_vectorized_loops
, loop_p loop
,
1028 gimple
*loop_vectorized_call
,
1029 gimple
*loop_dist_alias_call
)
1032 vec_info_shared shared
;
1033 auto_purge_vect_location sentinel
;
1034 vect_location
= find_loop_location (loop
);
1036 if (LOCATION_LOCUS (vect_location
.get_location_t ()) != UNKNOWN_LOCATION
1037 && dump_enabled_p ())
1038 dump_printf (MSG_NOTE
| MSG_PRIORITY_INTERNALS
,
1039 "\nAnalyzing loop at %s:%d\n",
1040 LOCATION_FILE (vect_location
.get_location_t ()),
1041 LOCATION_LINE (vect_location
.get_location_t ()));
1043 /* Try to analyze the loop, retaining an opt_problem if dump_enabled_p. */
1044 opt_loop_vec_info loop_vinfo
= vect_analyze_loop (loop
, &shared
);
1045 loop
->aux
= loop_vinfo
;
1048 if (dump_enabled_p ())
1049 if (opt_problem
*problem
= loop_vinfo
.get_problem ())
1051 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1052 "couldn't vectorize loop\n");
1053 problem
->emit_and_clear ();
1056 if (!loop_vinfo
|| !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
))
1058 /* Free existing information if loop is analyzed with some
1060 if (loop_constraint_set_p (loop
, LOOP_C_FINITE
))
1061 vect_free_loop_info_assumptions (loop
);
1063 /* If we applied if-conversion then try to vectorize the
1064 BB of innermost loops.
1065 ??? Ideally BB vectorization would learn to vectorize
1066 control flow by applying if-conversion on-the-fly, the
1067 following retains the if-converted loop body even when
1068 only non-if-converted parts took part in BB vectorization. */
1069 if (flag_tree_slp_vectorize
!= 0
1070 && loop_vectorized_call
1073 basic_block bb
= loop
->header
;
1074 bool require_loop_vectorize
= false;
1075 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
1076 !gsi_end_p (gsi
); gsi_next (&gsi
))
1078 gimple
*stmt
= gsi_stmt (gsi
);
1079 gcall
*call
= dyn_cast
<gcall
*> (stmt
);
1080 if (call
&& gimple_call_internal_p (call
))
1082 internal_fn ifn
= gimple_call_internal_fn (call
);
1083 if (ifn
== IFN_MASK_LOAD
|| ifn
== IFN_MASK_STORE
1084 /* Don't keep the if-converted parts when the ifn with
1085 specifc type is not supported by the backend. */
1086 || (direct_internal_fn_p (ifn
)
1087 && !direct_internal_fn_supported_p
1088 (call
, OPTIMIZE_FOR_SPEED
)))
1090 require_loop_vectorize
= true;
1094 gimple_set_uid (stmt
, -1);
1095 gimple_set_visited (stmt
, false);
1097 if (!require_loop_vectorize
)
1099 tree arg
= gimple_call_arg (loop_vectorized_call
, 1);
1100 class loop
*scalar_loop
= get_loop (cfun
, tree_to_shwi (arg
));
1101 if (vect_slp_if_converted_bb (bb
, scalar_loop
))
1103 fold_loop_internal_call (loop_vectorized_call
,
1105 loop_vectorized_call
= NULL
;
1106 ret
|= TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
;
1110 /* If outer loop vectorization fails for LOOP_VECTORIZED guarded
1111 loop, don't vectorize its inner loop; we'll attempt to
1112 vectorize LOOP_VECTORIZED guarded inner loop of the scalar
1114 if (loop_vectorized_call
&& loop
->inner
)
1115 loop
->inner
->dont_vectorize
= true;
1119 if (!dbg_cnt (vect_loop
))
1121 /* Free existing information if loop is analyzed with some
1123 if (loop_constraint_set_p (loop
, LOOP_C_FINITE
))
1124 vect_free_loop_info_assumptions (loop
);
1128 (*num_vectorized_loops
)++;
1129 /* Transform LOOP and its epilogues. */
1130 vect_transform_loops (simduid_to_vf_htab
, loop
, loop_vectorized_call
);
1132 if (loop_vectorized_call
)
1134 fold_loop_internal_call (loop_vectorized_call
, boolean_true_node
);
1135 ret
|= TODO_cleanup_cfg
;
1137 if (loop_dist_alias_call
)
1139 tree value
= gimple_call_arg (loop_dist_alias_call
, 1);
1140 fold_loop_internal_call (loop_dist_alias_call
, value
);
1141 ret
|= TODO_cleanup_cfg
;
1147 /* Try to vectorize LOOP. */
1150 try_vectorize_loop (hash_table
<simduid_to_vf
> *&simduid_to_vf_htab
,
1151 unsigned *num_vectorized_loops
, loop_p loop
)
1153 if (!((flag_tree_loop_vectorize
1154 && optimize_loop_nest_for_speed_p (loop
))
1155 || loop
->force_vectorize
))
1158 return try_vectorize_loop_1 (simduid_to_vf_htab
, num_vectorized_loops
, loop
,
1159 vect_loop_vectorized_call (loop
),
1160 vect_loop_dist_alias_call (loop
));
1164 /* Function vectorize_loops.
1166 Entry point to loop vectorization phase. */
1169 vectorize_loops (void)
1172 unsigned int num_vectorized_loops
= 0;
1173 unsigned int vect_loops_num
;
1175 hash_table
<simduid_to_vf
> *simduid_to_vf_htab
= NULL
;
1176 hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
= NULL
;
1177 bool any_ifcvt_loops
= false;
1180 vect_loops_num
= number_of_loops (cfun
);
1182 /* Bail out if there are no loops. */
1183 if (vect_loops_num
<= 1)
1188 if (cfun
->has_simduid_loops
)
1189 note_simd_array_uses (&simd_array_to_simduid_htab
);
1191 /* ----------- Analyze loops. ----------- */
1193 /* If some loop was duplicated, it gets bigger number
1194 than all previously defined loops. This fact allows us to run
1195 only over initial loops skipping newly generated ones. */
1196 for (auto loop
: loops_list (cfun
, 0))
1197 if (loop
->dont_vectorize
)
1199 any_ifcvt_loops
= true;
1200 /* If-conversion sometimes versions both the outer loop
1201 (for the case when outer loop vectorization might be
1202 desirable) as well as the inner loop in the scalar version
1203 of the loop. So we have:
1204 if (LOOP_VECTORIZED (1, 3))
1210 loop3 (copy of loop1)
1211 if (LOOP_VECTORIZED (4, 5))
1212 loop4 (copy of loop2)
1214 loop5 (copy of loop4)
1215 If loops' iteration gives us loop3 first (which has
1216 dont_vectorize set), make sure to process loop1 before loop4;
1217 so that we can prevent vectorization of loop4 if loop1
1218 is successfully vectorized. */
1221 gimple
*loop_vectorized_call
1222 = vect_loop_vectorized_call (loop
);
1223 if (loop_vectorized_call
1224 && vect_loop_vectorized_call (loop
->inner
))
1226 tree arg
= gimple_call_arg (loop_vectorized_call
, 0);
1227 class loop
*vector_loop
1228 = get_loop (cfun
, tree_to_shwi (arg
));
1229 if (vector_loop
&& vector_loop
!= loop
)
1231 /* Make sure we don't vectorize it twice. */
1232 vector_loop
->dont_vectorize
= true;
1233 ret
|= try_vectorize_loop (simduid_to_vf_htab
,
1234 &num_vectorized_loops
,
1241 ret
|= try_vectorize_loop (simduid_to_vf_htab
, &num_vectorized_loops
,
1244 vect_location
= dump_user_location_t ();
1246 statistics_counter_event (cfun
, "Vectorized loops", num_vectorized_loops
);
1247 if (dump_enabled_p ()
1248 || (num_vectorized_loops
> 0 && dump_enabled_p ()))
1249 dump_printf_loc (MSG_NOTE
, vect_location
,
1250 "vectorized %u loops in function.\n",
1251 num_vectorized_loops
);
1253 /* ----------- Finalize. ----------- */
1255 if (any_ifcvt_loops
)
1256 for (i
= 1; i
< number_of_loops (cfun
); i
++)
1258 loop
= get_loop (cfun
, i
);
1259 if (loop
&& loop
->dont_vectorize
)
1261 gimple
*g
= vect_loop_vectorized_call (loop
);
1264 fold_loop_internal_call (g
, boolean_false_node
);
1265 ret
|= TODO_cleanup_cfg
;
1269 g
= vect_loop_dist_alias_call (loop
);
1273 fold_loop_internal_call (g
, boolean_false_node
);
1274 ret
|= TODO_cleanup_cfg
;
1279 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
1280 if (cfun
->has_simduid_loops
)
1282 adjust_simduid_builtins (simduid_to_vf_htab
);
1283 /* Avoid stale SCEV cache entries for the SIMD_LANE defs. */
1286 /* Shrink any "omp array simd" temporary arrays to the
1287 actual vectorization factors. */
1288 if (simd_array_to_simduid_htab
)
1289 shrink_simd_arrays (simd_array_to_simduid_htab
, simduid_to_vf_htab
);
1290 delete simduid_to_vf_htab
;
1291 cfun
->has_simduid_loops
= false;
1293 if (num_vectorized_loops
> 0)
1295 /* If we vectorized any loop only virtual SSA form needs to be updated.
1296 ??? Also while we try hard to update loop-closed SSA form we fail
1297 to properly do this in some corner-cases (see PR56286). */
1298 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa_only_virtuals
);
1299 ret
|= TODO_cleanup_cfg
;
1302 for (i
= 1; i
< number_of_loops (cfun
); i
++)
1304 loop_vec_info loop_vinfo
;
1305 bool has_mask_store
;
1307 loop
= get_loop (cfun
, i
);
1308 if (!loop
|| !loop
->aux
)
1310 loop_vinfo
= (loop_vec_info
) loop
->aux
;
1311 has_mask_store
= LOOP_VINFO_HAS_MASK_STORE (loop_vinfo
);
1314 && targetm
.vectorize
.empty_mask_is_expensive (IFN_MASK_STORE
))
1315 optimize_mask_stores (loop
);
1317 auto_bitmap exit_bbs
;
1318 /* Perform local CSE, this esp. helps because we emit code for
1319 predicates that need to be shared for optimal predicate usage.
1320 However reassoc will re-order them and prevent CSE from working
1321 as it should. CSE only the loop body, not the entry. */
1322 bitmap_set_bit (exit_bbs
, single_exit (loop
)->dest
->index
);
1324 edge entry
= EDGE_PRED (loop_preheader_edge (loop
)->src
, 0);
1325 do_rpo_vn (cfun
, entry
, exit_bbs
);
1336 /* Entry point to the simduid cleanup pass. */
1340 const pass_data pass_data_simduid_cleanup
=
1342 GIMPLE_PASS
, /* type */
1343 "simduid", /* name */
1344 OPTGROUP_NONE
, /* optinfo_flags */
1345 TV_NONE
, /* tv_id */
1346 ( PROP_ssa
| PROP_cfg
), /* properties_required */
1347 0, /* properties_provided */
1348 0, /* properties_destroyed */
1349 0, /* todo_flags_start */
1350 0, /* todo_flags_finish */
1353 class pass_simduid_cleanup
: public gimple_opt_pass
1356 pass_simduid_cleanup (gcc::context
*ctxt
)
1357 : gimple_opt_pass (pass_data_simduid_cleanup
, ctxt
)
1360 /* opt_pass methods: */
1361 opt_pass
* clone () { return new pass_simduid_cleanup (m_ctxt
); }
1362 virtual bool gate (function
*fun
) { return fun
->has_simduid_loops
; }
1363 virtual unsigned int execute (function
*);
1365 }; // class pass_simduid_cleanup
1368 pass_simduid_cleanup::execute (function
*fun
)
1370 hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
= NULL
;
1372 note_simd_array_uses (&simd_array_to_simduid_htab
);
1374 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
1375 adjust_simduid_builtins (NULL
);
1377 /* Shrink any "omp array simd" temporary arrays to the
1378 actual vectorization factors. */
1379 if (simd_array_to_simduid_htab
)
1380 shrink_simd_arrays (simd_array_to_simduid_htab
, NULL
);
1381 fun
->has_simduid_loops
= false;
1388 make_pass_simduid_cleanup (gcc::context
*ctxt
)
1390 return new pass_simduid_cleanup (ctxt
);
1394 /* Entry point to basic block SLP phase. */
1398 const pass_data pass_data_slp_vectorize
=
1400 GIMPLE_PASS
, /* type */
1402 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
1403 TV_TREE_SLP_VECTORIZATION
, /* tv_id */
1404 ( PROP_ssa
| PROP_cfg
), /* properties_required */
1405 0, /* properties_provided */
1406 0, /* properties_destroyed */
1407 0, /* todo_flags_start */
1408 TODO_update_ssa
, /* todo_flags_finish */
1411 class pass_slp_vectorize
: public gimple_opt_pass
1414 pass_slp_vectorize (gcc::context
*ctxt
)
1415 : gimple_opt_pass (pass_data_slp_vectorize
, ctxt
)
1418 /* opt_pass methods: */
1419 opt_pass
* clone () { return new pass_slp_vectorize (m_ctxt
); }
1420 virtual bool gate (function
*) { return flag_tree_slp_vectorize
!= 0; }
1421 virtual unsigned int execute (function
*);
1423 }; // class pass_slp_vectorize
1426 pass_slp_vectorize::execute (function
*fun
)
1428 auto_purge_vect_location sentinel
;
1431 bool in_loop_pipeline
= scev_initialized_p ();
1432 if (!in_loop_pipeline
)
1434 loop_optimizer_init (LOOPS_NORMAL
);
1438 /* Mark all stmts as not belonging to the current region and unvisited. */
1439 FOR_EACH_BB_FN (bb
, fun
)
1441 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1444 gphi
*stmt
= gsi
.phi ();
1445 gimple_set_uid (stmt
, -1);
1446 gimple_set_visited (stmt
, false);
1448 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1451 gimple
*stmt
= gsi_stmt (gsi
);
1452 gimple_set_uid (stmt
, -1);
1453 gimple_set_visited (stmt
, false);
1459 vect_slp_function (fun
);
1463 if (!in_loop_pipeline
)
1466 loop_optimizer_finalize ();
1475 make_pass_slp_vectorize (gcc::context
*ctxt
)
1477 return new pass_slp_vectorize (ctxt
);
1481 /* Increase alignment of global arrays to improve vectorization potential.
1483 - Consider also structs that have an array field.
1484 - Use ipa analysis to prune arrays that can't be vectorized?
1485 This should involve global alignment analysis and in the future also
1488 static unsigned get_vec_alignment_for_type (tree
);
1489 static hash_map
<tree
, unsigned> *type_align_map
;
1491 /* Return alignment of array's vector type corresponding to scalar type.
1492 0 if no vector type exists. */
1494 get_vec_alignment_for_array_type (tree type
)
1496 gcc_assert (TREE_CODE (type
) == ARRAY_TYPE
);
1497 poly_uint64 array_size
, vector_size
;
1499 tree scalar_type
= strip_array_types (type
);
1500 tree vectype
= get_related_vectype_for_scalar_type (VOIDmode
, scalar_type
);
1502 || !poly_int_tree_p (TYPE_SIZE (type
), &array_size
)
1503 || !poly_int_tree_p (TYPE_SIZE (vectype
), &vector_size
)
1504 || maybe_lt (array_size
, vector_size
))
1507 return TYPE_ALIGN (vectype
);
1510 /* Return alignment of field having maximum alignment of vector type
1511 corresponding to it's scalar type. For now, we only consider fields whose
1512 offset is a multiple of it's vector alignment.
1513 0 if no suitable field is found. */
1515 get_vec_alignment_for_record_type (tree type
)
1517 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
);
1519 unsigned max_align
= 0, alignment
;
1520 HOST_WIDE_INT offset
;
1523 if (TYPE_PACKED (type
))
1526 unsigned *slot
= type_align_map
->get (type
);
1530 for (tree field
= first_field (type
);
1532 field
= DECL_CHAIN (field
))
1534 /* Skip if not FIELD_DECL or if alignment is set by user. */
1535 if (TREE_CODE (field
) != FIELD_DECL
1536 || DECL_USER_ALIGN (field
)
1537 || DECL_ARTIFICIAL (field
))
1540 /* We don't need to process the type further if offset is variable,
1541 since the offsets of remaining members will also be variable. */
1542 if (TREE_CODE (DECL_FIELD_OFFSET (field
)) != INTEGER_CST
1543 || TREE_CODE (DECL_FIELD_BIT_OFFSET (field
)) != INTEGER_CST
)
1546 /* Similarly stop processing the type if offset_tree
1547 does not fit in unsigned HOST_WIDE_INT. */
1548 offset_tree
= bit_position (field
);
1549 if (!tree_fits_uhwi_p (offset_tree
))
1552 offset
= tree_to_uhwi (offset_tree
);
1553 alignment
= get_vec_alignment_for_type (TREE_TYPE (field
));
1555 /* Get maximum alignment of vectorized field/array among those members
1556 whose offset is multiple of the vector alignment. */
1558 && (offset
% alignment
== 0)
1559 && (alignment
> max_align
))
1560 max_align
= alignment
;
1563 type_align_map
->put (type
, max_align
);
1567 /* Return alignment of vector type corresponding to decl's scalar type
1568 or 0 if it doesn't exist or the vector alignment is lesser than
1569 decl's alignment. */
1571 get_vec_alignment_for_type (tree type
)
1573 if (type
== NULL_TREE
)
1576 gcc_assert (TYPE_P (type
));
1578 static unsigned alignment
= 0;
1579 switch (TREE_CODE (type
))
1582 alignment
= get_vec_alignment_for_array_type (type
);
1585 alignment
= get_vec_alignment_for_record_type (type
);
1592 return (alignment
> TYPE_ALIGN (type
)) ? alignment
: 0;
1595 /* Entry point to increase_alignment pass. */
1597 increase_alignment (void)
1599 varpool_node
*vnode
;
1601 vect_location
= dump_user_location_t ();
1602 type_align_map
= new hash_map
<tree
, unsigned>;
1604 /* Increase the alignment of all global arrays for vectorization. */
1605 FOR_EACH_DEFINED_VARIABLE (vnode
)
1607 tree decl
= vnode
->decl
;
1608 unsigned int alignment
;
1610 if ((decl_in_symtab_p (decl
)
1611 && !symtab_node::get (decl
)->can_increase_alignment_p ())
1612 || DECL_USER_ALIGN (decl
) || DECL_ARTIFICIAL (decl
))
1615 alignment
= get_vec_alignment_for_type (TREE_TYPE (decl
));
1616 if (alignment
&& vect_can_force_dr_alignment_p (decl
, alignment
))
1618 vnode
->increase_alignment (alignment
);
1619 if (dump_enabled_p ())
1620 dump_printf (MSG_NOTE
, "Increasing alignment of decl: %T\n", decl
);
1624 delete type_align_map
;
1631 const pass_data pass_data_ipa_increase_alignment
=
1633 SIMPLE_IPA_PASS
, /* type */
1634 "increase_alignment", /* name */
1635 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
1636 TV_IPA_OPT
, /* tv_id */
1637 0, /* properties_required */
1638 0, /* properties_provided */
1639 0, /* properties_destroyed */
1640 0, /* todo_flags_start */
1641 0, /* todo_flags_finish */
1644 class pass_ipa_increase_alignment
: public simple_ipa_opt_pass
1647 pass_ipa_increase_alignment (gcc::context
*ctxt
)
1648 : simple_ipa_opt_pass (pass_data_ipa_increase_alignment
, ctxt
)
1651 /* opt_pass methods: */
1652 virtual bool gate (function
*)
1654 return flag_section_anchors
&& flag_tree_loop_vectorize
;
1657 virtual unsigned int execute (function
*) { return increase_alignment (); }
1659 }; // class pass_ipa_increase_alignment
1663 simple_ipa_opt_pass
*
1664 make_pass_ipa_increase_alignment (gcc::context
*ctxt
)
1666 return new pass_ipa_increase_alignment (ctxt
);
1669 /* If the condition represented by T is a comparison or the SSA name
1670 result of a comparison, extract the comparison's operands. Represent
1671 T as NE_EXPR <T, 0> otherwise. */
1674 scalar_cond_masked_key::get_cond_ops_from_tree (tree t
)
1676 if (TREE_CODE_CLASS (TREE_CODE (t
)) == tcc_comparison
)
1678 this->code
= TREE_CODE (t
);
1679 this->op0
= TREE_OPERAND (t
, 0);
1680 this->op1
= TREE_OPERAND (t
, 1);
1681 this->inverted_p
= false;
1685 if (TREE_CODE (t
) == SSA_NAME
)
1686 if (gassign
*stmt
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (t
)))
1688 tree_code code
= gimple_assign_rhs_code (stmt
);
1689 if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1692 this->op0
= gimple_assign_rhs1 (stmt
);
1693 this->op1
= gimple_assign_rhs2 (stmt
);
1694 this->inverted_p
= false;
1697 else if (code
== BIT_NOT_EXPR
)
1699 tree n_op
= gimple_assign_rhs1 (stmt
);
1700 if ((stmt
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (n_op
))))
1702 code
= gimple_assign_rhs_code (stmt
);
1703 if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1706 this->op0
= gimple_assign_rhs1 (stmt
);
1707 this->op1
= gimple_assign_rhs2 (stmt
);
1708 this->inverted_p
= true;
1715 this->code
= NE_EXPR
;
1717 this->op1
= build_zero_cst (TREE_TYPE (t
));
1718 this->inverted_p
= false;
1721 /* See the comment above the declaration for details. */
1724 vector_costs::add_stmt_cost (int count
, vect_cost_for_stmt kind
,
1725 stmt_vec_info stmt_info
, tree vectype
,
1726 int misalign
, vect_cost_model_location where
)
1729 = builtin_vectorization_cost (kind
, vectype
, misalign
) * count
;
1730 return record_stmt_cost (stmt_info
, where
, cost
);
1733 /* See the comment above the declaration for details. */
1736 vector_costs::finish_cost (const vector_costs
*)
1738 gcc_assert (!m_finished
);
1742 /* Record a base cost of COST units against WHERE. If STMT_INFO is
1743 nonnull, use it to adjust the cost based on execution frequency
1744 (where appropriate). */
1747 vector_costs::record_stmt_cost (stmt_vec_info stmt_info
,
1748 vect_cost_model_location where
,
1751 cost
= adjust_cost_for_freq (stmt_info
, where
, cost
);
1752 m_costs
[where
] += cost
;
1756 /* COST is the base cost we have calculated for an operation in location WHERE.
1757 If STMT_INFO is nonnull, use it to adjust the cost based on execution
1758 frequency (where appropriate). Return the adjusted cost. */
1761 vector_costs::adjust_cost_for_freq (stmt_vec_info stmt_info
,
1762 vect_cost_model_location where
,
1765 /* Statements in an inner loop relative to the loop being
1766 vectorized are weighted more heavily. The value here is
1767 arbitrary and could potentially be improved with analysis. */
1768 if (where
== vect_body
1770 && stmt_in_inner_loop_p (m_vinfo
, stmt_info
))
1772 loop_vec_info loop_vinfo
= as_a
<loop_vec_info
> (m_vinfo
);
1773 cost
*= LOOP_VINFO_INNER_LOOP_COST_FACTOR (loop_vinfo
);
1778 /* See the comment above the declaration for details. */
1781 vector_costs::better_main_loop_than_p (const vector_costs
*other
) const
1783 int diff
= compare_inside_loop_cost (other
);
1787 /* If there's nothing to choose between the loop bodies, see whether
1788 there's a difference in the prologue and epilogue costs. */
1789 diff
= compare_outside_loop_cost (other
);
1797 /* See the comment above the declaration for details. */
1800 vector_costs::better_epilogue_loop_than_p (const vector_costs
*other
,
1801 loop_vec_info main_loop
) const
1803 loop_vec_info this_loop_vinfo
= as_a
<loop_vec_info
> (this->m_vinfo
);
1804 loop_vec_info other_loop_vinfo
= as_a
<loop_vec_info
> (other
->m_vinfo
);
1806 poly_int64 this_vf
= LOOP_VINFO_VECT_FACTOR (this_loop_vinfo
);
1807 poly_int64 other_vf
= LOOP_VINFO_VECT_FACTOR (other_loop_vinfo
);
1809 poly_uint64 main_poly_vf
= LOOP_VINFO_VECT_FACTOR (main_loop
);
1810 unsigned HOST_WIDE_INT main_vf
;
1811 unsigned HOST_WIDE_INT other_factor
, this_factor
, other_cost
, this_cost
;
1812 /* If we can determine how many iterations are left for the epilogue
1813 loop, that is if both the main loop's vectorization factor and number
1814 of iterations are constant, then we use them to calculate the cost of
1815 the epilogue loop together with a 'likely value' for the epilogues
1816 vectorization factor. Otherwise we use the main loop's vectorization
1817 factor and the maximum poly value for the epilogue's. If the target
1818 has not provided with a sensible upper bound poly vectorization
1819 factors are likely to be favored over constant ones. */
1820 if (main_poly_vf
.is_constant (&main_vf
)
1821 && LOOP_VINFO_NITERS_KNOWN_P (main_loop
))
1823 unsigned HOST_WIDE_INT niters
1824 = LOOP_VINFO_INT_NITERS (main_loop
) % main_vf
;
1825 HOST_WIDE_INT other_likely_vf
1826 = estimated_poly_value (other_vf
, POLY_VALUE_LIKELY
);
1827 HOST_WIDE_INT this_likely_vf
1828 = estimated_poly_value (this_vf
, POLY_VALUE_LIKELY
);
1830 /* If the epilogue is using partial vectors we account for the
1831 partial iteration here too. */
1832 other_factor
= niters
/ other_likely_vf
;
1833 if (LOOP_VINFO_USING_PARTIAL_VECTORS_P (other_loop_vinfo
)
1834 && niters
% other_likely_vf
!= 0)
1837 this_factor
= niters
/ this_likely_vf
;
1838 if (LOOP_VINFO_USING_PARTIAL_VECTORS_P (this_loop_vinfo
)
1839 && niters
% this_likely_vf
!= 0)
1844 unsigned HOST_WIDE_INT main_vf_max
1845 = estimated_poly_value (main_poly_vf
, POLY_VALUE_MAX
);
1847 other_factor
= main_vf_max
/ estimated_poly_value (other_vf
,
1849 this_factor
= main_vf_max
/ estimated_poly_value (this_vf
,
1852 /* If the loop is not using partial vectors then it will iterate one
1853 time less than one that does. It is safe to subtract one here,
1854 because the main loop's vf is always at least 2x bigger than that
1856 if (!LOOP_VINFO_USING_PARTIAL_VECTORS_P (other_loop_vinfo
))
1858 if (!LOOP_VINFO_USING_PARTIAL_VECTORS_P (this_loop_vinfo
))
1862 /* Compute the costs by multiplying the inside costs with the factor and
1863 add the outside costs for a more complete picture. The factor is the
1864 amount of times we are expecting to iterate this epilogue. */
1865 other_cost
= other
->body_cost () * other_factor
;
1866 this_cost
= this->body_cost () * this_factor
;
1867 other_cost
+= other
->outside_cost ();
1868 this_cost
+= this->outside_cost ();
1869 return this_cost
< other_cost
;
1872 /* A <=>-style subroutine of better_main_loop_than_p. Check whether we can
1873 determine the return value of better_main_loop_than_p by comparing the
1874 inside (loop body) costs of THIS and OTHER. Return:
1876 * -1 if better_main_loop_than_p should return true.
1877 * 1 if better_main_loop_than_p should return false.
1878 * 0 if we can't decide. */
1881 vector_costs::compare_inside_loop_cost (const vector_costs
*other
) const
1883 loop_vec_info this_loop_vinfo
= as_a
<loop_vec_info
> (this->m_vinfo
);
1884 loop_vec_info other_loop_vinfo
= as_a
<loop_vec_info
> (other
->m_vinfo
);
1886 struct loop
*loop
= LOOP_VINFO_LOOP (this_loop_vinfo
);
1887 gcc_assert (LOOP_VINFO_LOOP (other_loop_vinfo
) == loop
);
1889 poly_int64 this_vf
= LOOP_VINFO_VECT_FACTOR (this_loop_vinfo
);
1890 poly_int64 other_vf
= LOOP_VINFO_VECT_FACTOR (other_loop_vinfo
);
1892 /* Limit the VFs to what is likely to be the maximum number of iterations,
1893 to handle cases in which at least one loop_vinfo is fully-masked. */
1894 HOST_WIDE_INT estimated_max_niter
= likely_max_stmt_executions_int (loop
);
1895 if (estimated_max_niter
!= -1)
1897 if (known_le (estimated_max_niter
, this_vf
))
1898 this_vf
= estimated_max_niter
;
1899 if (known_le (estimated_max_niter
, other_vf
))
1900 other_vf
= estimated_max_niter
;
1903 /* Check whether the (fractional) cost per scalar iteration is lower or
1904 higher: this_inside_cost / this_vf vs. other_inside_cost / other_vf. */
1905 poly_int64 rel_this
= this_loop_vinfo
->vector_costs
->body_cost () * other_vf
;
1906 poly_int64 rel_other
1907 = other_loop_vinfo
->vector_costs
->body_cost () * this_vf
;
1909 HOST_WIDE_INT est_rel_this_min
1910 = estimated_poly_value (rel_this
, POLY_VALUE_MIN
);
1911 HOST_WIDE_INT est_rel_this_max
1912 = estimated_poly_value (rel_this
, POLY_VALUE_MAX
);
1914 HOST_WIDE_INT est_rel_other_min
1915 = estimated_poly_value (rel_other
, POLY_VALUE_MIN
);
1916 HOST_WIDE_INT est_rel_other_max
1917 = estimated_poly_value (rel_other
, POLY_VALUE_MAX
);
1919 /* Check first if we can make out an unambigous total order from the minimum
1920 and maximum estimates. */
1921 if (est_rel_this_min
< est_rel_other_min
1922 && est_rel_this_max
< est_rel_other_max
)
1925 if (est_rel_other_min
< est_rel_this_min
1926 && est_rel_other_max
< est_rel_this_max
)
1929 /* When other_loop_vinfo uses a variable vectorization factor,
1930 we know that it has a lower cost for at least one runtime VF.
1931 However, we don't know how likely that VF is.
1933 One option would be to compare the costs for the estimated VFs.
1934 The problem is that that can put too much pressure on the cost
1935 model. E.g. if the estimated VF is also the lowest possible VF,
1936 and if other_loop_vinfo is 1 unit worse than this_loop_vinfo
1937 for the estimated VF, we'd then choose this_loop_vinfo even
1938 though (a) this_loop_vinfo might not actually be better than
1939 other_loop_vinfo for that VF and (b) it would be significantly
1940 worse at larger VFs.
1942 Here we go for a hacky compromise: pick this_loop_vinfo if it is
1943 no more expensive than other_loop_vinfo even after doubling the
1944 estimated other_loop_vinfo VF. For all but trivial loops, this
1945 ensures that we only pick this_loop_vinfo if it is significantly
1946 better than other_loop_vinfo at the estimated VF. */
1947 if (est_rel_other_min
!= est_rel_this_min
1948 || est_rel_other_max
!= est_rel_this_max
)
1950 HOST_WIDE_INT est_rel_this_likely
1951 = estimated_poly_value (rel_this
, POLY_VALUE_LIKELY
);
1952 HOST_WIDE_INT est_rel_other_likely
1953 = estimated_poly_value (rel_other
, POLY_VALUE_LIKELY
);
1955 return est_rel_this_likely
* 2 <= est_rel_other_likely
? -1 : 1;
1961 /* A <=>-style subroutine of better_main_loop_than_p, used when there is
1962 nothing to choose between the inside (loop body) costs of THIS and OTHER.
1963 Check whether we can determine the return value of better_main_loop_than_p
1964 by comparing the outside (prologue and epilogue) costs of THIS and OTHER.
1967 * -1 if better_main_loop_than_p should return true.
1968 * 1 if better_main_loop_than_p should return false.
1969 * 0 if we can't decide. */
1972 vector_costs::compare_outside_loop_cost (const vector_costs
*other
) const
1974 auto this_outside_cost
= this->outside_cost ();
1975 auto other_outside_cost
= other
->outside_cost ();
1976 if (this_outside_cost
!= other_outside_cost
)
1977 return this_outside_cost
< other_outside_cost
? -1 : 1;