2 Copyright (C) 2003-2019 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"
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
, void *data
, int count
, enum vect_cost_for_stmt kind
,
102 stmt_vec_info stmt_info
, int misalign
, unsigned cost
,
103 enum vect_cost_model_location where
)
105 fprintf (f
, "%p ", data
);
108 print_gimple_expr (f
, STMT_VINFO_STMT (stmt_info
), 0, TDF_SLIM
);
112 fprintf (f
, "<unknown> ");
113 fprintf (f
, "%d times ", count
);
114 const char *ks
= "unknown";
132 case vector_gather_load
:
133 ks
= "vector_gather_load";
136 ks
= "unaligned_load";
138 case unaligned_store
:
139 ks
= "unaligned_store";
144 case vector_scatter_store
:
145 ks
= "vector_scatter_store";
148 ks
= "vec_to_scalar";
151 ks
= "scalar_to_vec";
153 case cond_branch_not_taken
:
154 ks
= "cond_branch_not_taken";
156 case cond_branch_taken
:
157 ks
= "cond_branch_taken";
162 case vec_promote_demote
:
163 ks
= "vec_promote_demote";
166 ks
= "vec_construct";
169 fprintf (f
, "%s ", ks
);
170 if (kind
== unaligned_load
|| kind
== unaligned_store
)
171 fprintf (f
, "(misalign %d) ", misalign
);
172 fprintf (f
, "costs %u ", cost
);
173 const char *ws
= "unknown";
186 fprintf (f
, "in %s\n", ws
);
189 /* For mapping simduid to vectorization factor. */
191 class simduid_to_vf
: public free_ptr_hash
<simduid_to_vf
>
194 unsigned int simduid
;
197 /* hash_table support. */
198 static inline hashval_t
hash (const simduid_to_vf
*);
199 static inline int equal (const simduid_to_vf
*, const simduid_to_vf
*);
203 simduid_to_vf::hash (const simduid_to_vf
*p
)
209 simduid_to_vf::equal (const simduid_to_vf
*p1
, const simduid_to_vf
*p2
)
211 return p1
->simduid
== p2
->simduid
;
214 /* This hash maps the OMP simd array to the corresponding simduid used
215 to index into it. Like thus,
217 _7 = GOMP_SIMD_LANE (simduid.0)
223 This hash maps from the OMP simd array (D.1737[]) to DECL_UID of
226 struct simd_array_to_simduid
: free_ptr_hash
<simd_array_to_simduid
>
229 unsigned int simduid
;
231 /* hash_table support. */
232 static inline hashval_t
hash (const simd_array_to_simduid
*);
233 static inline int equal (const simd_array_to_simduid
*,
234 const simd_array_to_simduid
*);
238 simd_array_to_simduid::hash (const simd_array_to_simduid
*p
)
240 return DECL_UID (p
->decl
);
244 simd_array_to_simduid::equal (const simd_array_to_simduid
*p1
,
245 const simd_array_to_simduid
*p2
)
247 return p1
->decl
== p2
->decl
;
250 /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LAST_LANE,
251 into their corresponding constants and remove
252 IFN_GOMP_SIMD_ORDERED_{START,END}. */
255 adjust_simduid_builtins (hash_table
<simduid_to_vf
> *htab
)
259 FOR_EACH_BB_FN (bb
, cfun
)
261 gimple_stmt_iterator i
;
263 for (i
= gsi_start_bb (bb
); !gsi_end_p (i
); )
266 enum internal_fn ifn
;
267 gimple
*stmt
= gsi_stmt (i
);
269 if (!is_gimple_call (stmt
)
270 || !gimple_call_internal_p (stmt
))
275 ifn
= gimple_call_internal_fn (stmt
);
278 case IFN_GOMP_SIMD_LANE
:
279 case IFN_GOMP_SIMD_VF
:
280 case IFN_GOMP_SIMD_LAST_LANE
:
282 case IFN_GOMP_SIMD_ORDERED_START
:
283 case IFN_GOMP_SIMD_ORDERED_END
:
284 if (integer_onep (gimple_call_arg (stmt
, 0)))
286 enum built_in_function bcode
287 = (ifn
== IFN_GOMP_SIMD_ORDERED_START
288 ? BUILT_IN_GOMP_ORDERED_START
289 : BUILT_IN_GOMP_ORDERED_END
);
291 = gimple_build_call (builtin_decl_explicit (bcode
), 0);
292 tree vdef
= gimple_vdef (stmt
);
293 gimple_set_vdef (g
, vdef
);
294 SSA_NAME_DEF_STMT (vdef
) = g
;
295 gimple_set_vuse (g
, gimple_vuse (stmt
));
296 gsi_replace (&i
, g
, true);
299 gsi_remove (&i
, true);
300 unlink_stmt_vdef (stmt
);
306 tree arg
= gimple_call_arg (stmt
, 0);
307 gcc_assert (arg
!= NULL_TREE
);
308 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
309 simduid_to_vf
*p
= NULL
, data
;
310 data
.simduid
= DECL_UID (SSA_NAME_VAR (arg
));
311 /* Need to nullify loop safelen field since it's value is not
312 valid after transformation. */
313 if (bb
->loop_father
&& bb
->loop_father
->safelen
> 0)
314 bb
->loop_father
->safelen
= 0;
317 p
= htab
->find (&data
);
323 case IFN_GOMP_SIMD_VF
:
324 t
= build_int_cst (unsigned_type_node
, vf
);
326 case IFN_GOMP_SIMD_LANE
:
327 t
= build_int_cst (unsigned_type_node
, 0);
329 case IFN_GOMP_SIMD_LAST_LANE
:
330 t
= gimple_call_arg (stmt
, 1);
335 tree lhs
= gimple_call_lhs (stmt
);
337 replace_uses_by (lhs
, t
);
339 gsi_remove (&i
, true);
344 /* Helper structure for note_simd_array_uses. */
346 struct note_simd_array_uses_struct
348 hash_table
<simd_array_to_simduid
> **htab
;
349 unsigned int simduid
;
352 /* Callback for note_simd_array_uses, called through walk_gimple_op. */
355 note_simd_array_uses_cb (tree
*tp
, int *walk_subtrees
, void *data
)
357 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
358 struct note_simd_array_uses_struct
*ns
359 = (struct note_simd_array_uses_struct
*) wi
->info
;
364 && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp
))
365 && DECL_CONTEXT (*tp
) == current_function_decl
)
367 simd_array_to_simduid data
;
369 *ns
->htab
= new hash_table
<simd_array_to_simduid
> (15);
371 data
.simduid
= ns
->simduid
;
372 simd_array_to_simduid
**slot
= (*ns
->htab
)->find_slot (&data
, INSERT
);
375 simd_array_to_simduid
*p
= XNEW (simd_array_to_simduid
);
379 else if ((*slot
)->simduid
!= ns
->simduid
)
380 (*slot
)->simduid
= -1U;
386 /* Find "omp simd array" temporaries and map them to corresponding
390 note_simd_array_uses (hash_table
<simd_array_to_simduid
> **htab
)
393 gimple_stmt_iterator gsi
;
394 struct walk_stmt_info wi
;
395 struct note_simd_array_uses_struct ns
;
397 memset (&wi
, 0, sizeof (wi
));
401 FOR_EACH_BB_FN (bb
, cfun
)
402 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
404 gimple
*stmt
= gsi_stmt (gsi
);
405 if (!is_gimple_call (stmt
) || !gimple_call_internal_p (stmt
))
407 switch (gimple_call_internal_fn (stmt
))
409 case IFN_GOMP_SIMD_LANE
:
410 case IFN_GOMP_SIMD_VF
:
411 case IFN_GOMP_SIMD_LAST_LANE
:
416 tree lhs
= gimple_call_lhs (stmt
);
417 if (lhs
== NULL_TREE
)
419 imm_use_iterator use_iter
;
421 ns
.simduid
= DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt
, 0)));
422 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, lhs
)
423 if (!is_gimple_debug (use_stmt
))
424 walk_gimple_op (use_stmt
, note_simd_array_uses_cb
, &wi
);
428 /* Shrink arrays with "omp simd array" attribute to the corresponding
429 vectorization factor. */
433 (hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
,
434 hash_table
<simduid_to_vf
> *simduid_to_vf_htab
)
436 for (hash_table
<simd_array_to_simduid
>::iterator iter
437 = simd_array_to_simduid_htab
->begin ();
438 iter
!= simd_array_to_simduid_htab
->end (); ++iter
)
439 if ((*iter
)->simduid
!= -1U)
441 tree decl
= (*iter
)->decl
;
443 if (simduid_to_vf_htab
)
445 simduid_to_vf
*p
= NULL
, data
;
446 data
.simduid
= (*iter
)->simduid
;
447 p
= simduid_to_vf_htab
->find (&data
);
452 = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl
)), vf
);
453 TREE_TYPE (decl
) = atype
;
454 relayout_decl (decl
);
457 delete simd_array_to_simduid_htab
;
460 /* Initialize the vec_info with kind KIND_IN and target cost data
461 TARGET_COST_DATA_IN. */
463 vec_info::vec_info (vec_info::vec_kind kind_in
, void *target_cost_data_in
,
464 vec_info_shared
*shared_
)
467 target_cost_data (target_cost_data_in
)
469 stmt_vec_infos
.create (50);
472 vec_info::~vec_info ()
474 slp_instance instance
;
477 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
478 vect_free_slp_instance (instance
, true);
480 destroy_cost_data (target_cost_data
);
481 free_stmt_vec_infos ();
484 vec_info_shared::vec_info_shared ()
486 datarefs_copy (vNULL
),
491 vec_info_shared::~vec_info_shared ()
493 free_data_refs (datarefs
);
494 free_dependence_relations (ddrs
);
495 datarefs_copy
.release ();
499 vec_info_shared::save_datarefs ()
503 datarefs_copy
.reserve_exact (datarefs
.length ());
504 for (unsigned i
= 0; i
< datarefs
.length (); ++i
)
505 datarefs_copy
.quick_push (*datarefs
[i
]);
509 vec_info_shared::check_datarefs ()
513 gcc_assert (datarefs
.length () == datarefs_copy
.length ());
514 for (unsigned i
= 0; i
< datarefs
.length (); ++i
)
515 if (memcmp (&datarefs_copy
[i
], datarefs
[i
], sizeof (data_reference
)) != 0)
519 /* Record that STMT belongs to the vectorizable region. Create and return
520 an associated stmt_vec_info. */
523 vec_info::add_stmt (gimple
*stmt
)
525 stmt_vec_info res
= new_stmt_vec_info (stmt
);
526 set_vinfo_for_stmt (stmt
, res
);
530 /* If STMT has an associated stmt_vec_info, return that vec_info, otherwise
531 return null. It is safe to call this function on any statement, even if
532 it might not be part of the vectorizable region. */
535 vec_info::lookup_stmt (gimple
*stmt
)
537 unsigned int uid
= gimple_uid (stmt
);
538 if (uid
> 0 && uid
- 1 < stmt_vec_infos
.length ())
540 stmt_vec_info res
= stmt_vec_infos
[uid
- 1];
541 if (res
&& res
->stmt
== stmt
)
547 /* If NAME is an SSA_NAME and its definition has an associated stmt_vec_info,
548 return that stmt_vec_info, otherwise return null. It is safe to call
549 this on arbitrary operands. */
552 vec_info::lookup_def (tree name
)
554 if (TREE_CODE (name
) == SSA_NAME
555 && !SSA_NAME_IS_DEFAULT_DEF (name
))
556 return lookup_stmt (SSA_NAME_DEF_STMT (name
));
560 /* See whether there is a single non-debug statement that uses LHS and
561 whether that statement has an associated stmt_vec_info. Return the
562 stmt_vec_info if so, otherwise return null. */
565 vec_info::lookup_single_use (tree lhs
)
569 if (single_imm_use (lhs
, &dummy
, &use_stmt
))
570 return lookup_stmt (use_stmt
);
574 /* Return vectorization information about DR. */
577 vec_info::lookup_dr (data_reference
*dr
)
579 stmt_vec_info stmt_info
= lookup_stmt (DR_STMT (dr
));
580 /* DR_STMT should never refer to a stmt in a pattern replacement. */
581 gcc_checking_assert (!is_pattern_stmt_p (stmt_info
));
582 return STMT_VINFO_DR_INFO (stmt_info
->dr_aux
.stmt
);
585 /* Record that NEW_STMT_INFO now implements the same data reference
589 vec_info::move_dr (stmt_vec_info new_stmt_info
, stmt_vec_info old_stmt_info
)
591 gcc_assert (!is_pattern_stmt_p (old_stmt_info
));
592 STMT_VINFO_DR_INFO (old_stmt_info
)->stmt
= new_stmt_info
;
593 new_stmt_info
->dr_aux
= old_stmt_info
->dr_aux
;
594 STMT_VINFO_DR_WRT_VEC_LOOP (new_stmt_info
)
595 = STMT_VINFO_DR_WRT_VEC_LOOP (old_stmt_info
);
596 STMT_VINFO_GATHER_SCATTER_P (new_stmt_info
)
597 = STMT_VINFO_GATHER_SCATTER_P (old_stmt_info
);
600 /* Permanently remove the statement described by STMT_INFO from the
604 vec_info::remove_stmt (stmt_vec_info stmt_info
)
606 gcc_assert (!stmt_info
->pattern_stmt_p
);
607 set_vinfo_for_stmt (stmt_info
->stmt
, NULL
);
608 gimple_stmt_iterator si
= gsi_for_stmt (stmt_info
->stmt
);
609 unlink_stmt_vdef (stmt_info
->stmt
);
610 gsi_remove (&si
, true);
611 release_defs (stmt_info
->stmt
);
612 free_stmt_vec_info (stmt_info
);
615 /* Replace the statement at GSI by NEW_STMT, both the vectorization
616 information and the function itself. STMT_INFO describes the statement
620 vec_info::replace_stmt (gimple_stmt_iterator
*gsi
, stmt_vec_info stmt_info
,
623 gimple
*old_stmt
= stmt_info
->stmt
;
624 gcc_assert (!stmt_info
->pattern_stmt_p
&& old_stmt
== gsi_stmt (*gsi
));
625 set_vinfo_for_stmt (old_stmt
, NULL
);
626 set_vinfo_for_stmt (new_stmt
, stmt_info
);
627 stmt_info
->stmt
= new_stmt
;
628 gsi_replace (gsi
, new_stmt
, true);
631 /* Create and initialize a new stmt_vec_info struct for STMT. */
634 vec_info::new_stmt_vec_info (gimple
*stmt
)
636 stmt_vec_info res
= XCNEW (class _stmt_vec_info
);
640 STMT_VINFO_TYPE (res
) = undef_vec_info_type
;
641 STMT_VINFO_RELEVANT (res
) = vect_unused_in_scope
;
642 STMT_VINFO_VECTORIZABLE (res
) = true;
643 STMT_VINFO_VEC_REDUCTION_TYPE (res
) = TREE_CODE_REDUCTION
;
644 STMT_VINFO_VEC_CONST_COND_REDUC_CODE (res
) = ERROR_MARK
;
645 STMT_VINFO_SLP_VECT_ONLY (res
) = false;
647 if (gimple_code (stmt
) == GIMPLE_PHI
648 && is_loop_header_bb_p (gimple_bb (stmt
)))
649 STMT_VINFO_DEF_TYPE (res
) = vect_unknown_def_type
;
651 STMT_VINFO_DEF_TYPE (res
) = vect_internal_def
;
653 STMT_VINFO_SAME_ALIGN_REFS (res
).create (0);
654 STMT_SLP_TYPE (res
) = loop_vect
;
656 /* This is really "uninitialized" until vect_compute_data_ref_alignment. */
657 res
->dr_aux
.misalignment
= DR_MISALIGNMENT_UNINITIALIZED
;
662 /* Associate STMT with INFO. */
665 vec_info::set_vinfo_for_stmt (gimple
*stmt
, stmt_vec_info info
)
667 unsigned int uid
= gimple_uid (stmt
);
670 gcc_checking_assert (info
);
671 uid
= stmt_vec_infos
.length () + 1;
672 gimple_set_uid (stmt
, uid
);
673 stmt_vec_infos
.safe_push (info
);
677 gcc_checking_assert (info
== NULL
);
678 stmt_vec_infos
[uid
- 1] = info
;
682 /* Free the contents of stmt_vec_infos. */
685 vec_info::free_stmt_vec_infos (void)
689 FOR_EACH_VEC_ELT (stmt_vec_infos
, i
, info
)
691 free_stmt_vec_info (info
);
692 stmt_vec_infos
.release ();
695 /* Free STMT_INFO. */
698 vec_info::free_stmt_vec_info (stmt_vec_info stmt_info
)
700 if (stmt_info
->pattern_stmt_p
)
702 gimple_set_bb (stmt_info
->stmt
, NULL
);
703 tree lhs
= gimple_get_lhs (stmt_info
->stmt
);
704 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
705 release_ssa_name (lhs
);
708 STMT_VINFO_SAME_ALIGN_REFS (stmt_info
).release ();
709 STMT_VINFO_SIMD_CLONE_INFO (stmt_info
).release ();
713 /* A helper function to free scev and LOOP niter information, as well as
714 clear loop constraint LOOP_C_FINITE. */
717 vect_free_loop_info_assumptions (class loop
*loop
)
720 /* We need to explicitly reset upper bound information since they are
721 used even after free_numbers_of_iterations_estimates. */
722 loop
->any_upper_bound
= false;
723 loop
->any_likely_upper_bound
= false;
724 free_numbers_of_iterations_estimates (loop
);
725 loop_constraint_clear (loop
, LOOP_C_FINITE
);
728 /* If LOOP has been versioned during ifcvt, return the internal call
732 vect_loop_vectorized_call (class loop
*loop
, gcond
**cond
)
734 basic_block bb
= loop_preheader_edge (loop
)->src
;
741 if (!single_pred_p (bb
))
743 bb
= single_pred (bb
);
746 if (g
&& gimple_code (g
) == GIMPLE_COND
)
749 *cond
= as_a
<gcond
*> (g
);
750 gimple_stmt_iterator gsi
= gsi_for_stmt (g
);
752 if (!gsi_end_p (gsi
))
755 if (gimple_call_internal_p (g
, IFN_LOOP_VECTORIZED
)
756 && (tree_to_shwi (gimple_call_arg (g
, 0)) == loop
->num
757 || tree_to_shwi (gimple_call_arg (g
, 1)) == loop
->num
))
764 /* If LOOP has been versioned during loop distribution, return the gurading
768 vect_loop_dist_alias_call (class loop
*loop
)
772 class loop
*outer
, *orig
;
773 gimple_stmt_iterator gsi
;
776 if (loop
->orig_loop_num
== 0)
779 orig
= get_loop (cfun
, loop
->orig_loop_num
);
782 /* The original loop is somehow destroyed. Clear the information. */
783 loop
->orig_loop_num
= 0;
788 bb
= nearest_common_dominator (CDI_DOMINATORS
, loop
->header
, orig
->header
);
790 bb
= loop_preheader_edge (loop
)->src
;
792 outer
= bb
->loop_father
;
793 entry
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
795 /* Look upward in dominance tree. */
796 for (; bb
!= entry
&& flow_bb_inside_loop_p (outer
, bb
);
797 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
800 if (g
== NULL
|| gimple_code (g
) != GIMPLE_COND
)
803 gsi
= gsi_for_stmt (g
);
809 /* The guarding internal function call must have the same distribution
811 if (gimple_call_internal_p (g
, IFN_LOOP_DIST_ALIAS
)
812 && (tree_to_shwi (gimple_call_arg (g
, 0)) == loop
->orig_loop_num
))
818 /* Set the uids of all the statements in basic blocks inside loop
819 represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal
820 call guarding the loop which has been if converted. */
822 set_uid_loop_bbs (loop_vec_info loop_vinfo
, gimple
*loop_vectorized_call
)
824 tree arg
= gimple_call_arg (loop_vectorized_call
, 1);
827 class loop
*scalar_loop
= get_loop (cfun
, tree_to_shwi (arg
));
829 LOOP_VINFO_SCALAR_LOOP (loop_vinfo
) = scalar_loop
;
830 gcc_checking_assert (vect_loop_vectorized_call (scalar_loop
)
831 == loop_vectorized_call
);
832 /* If we are going to vectorize outer loop, prevent vectorization
833 of the inner loop in the scalar loop - either the scalar loop is
834 thrown away, so it is a wasted work, or is used only for
836 if (scalar_loop
->inner
)
838 gimple
*g
= vect_loop_vectorized_call (scalar_loop
->inner
);
841 arg
= gimple_call_arg (g
, 0);
842 get_loop (cfun
, tree_to_shwi (arg
))->dont_vectorize
= true;
843 fold_loop_internal_call (g
, boolean_false_node
);
846 bbs
= get_loop_body (scalar_loop
);
847 for (i
= 0; i
< scalar_loop
->num_nodes
; i
++)
849 basic_block bb
= bbs
[i
];
850 gimple_stmt_iterator gsi
;
851 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
853 gimple
*phi
= gsi_stmt (gsi
);
854 gimple_set_uid (phi
, 0);
856 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
858 gimple
*stmt
= gsi_stmt (gsi
);
859 gimple_set_uid (stmt
, 0);
865 /* Try to vectorize LOOP. */
868 try_vectorize_loop_1 (hash_table
<simduid_to_vf
> *&simduid_to_vf_htab
,
869 unsigned *num_vectorized_loops
,
870 loop_p loop
, loop_vec_info orig_loop_vinfo
,
871 gimple
*loop_vectorized_call
,
872 gimple
*loop_dist_alias_call
)
875 vec_info_shared shared
;
876 auto_purge_vect_location sentinel
;
877 vect_location
= find_loop_location (loop
);
878 if (LOCATION_LOCUS (vect_location
.get_location_t ()) != UNKNOWN_LOCATION
879 && dump_enabled_p ())
880 dump_printf (MSG_NOTE
| MSG_PRIORITY_INTERNALS
,
881 "\nAnalyzing loop at %s:%d\n",
882 LOCATION_FILE (vect_location
.get_location_t ()),
883 LOCATION_LINE (vect_location
.get_location_t ()));
885 /* Try to analyze the loop, retaining an opt_problem if dump_enabled_p. */
886 opt_loop_vec_info loop_vinfo
887 = vect_analyze_loop (loop
, orig_loop_vinfo
, &shared
);
888 loop
->aux
= loop_vinfo
;
891 if (dump_enabled_p ())
892 if (opt_problem
*problem
= loop_vinfo
.get_problem ())
894 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
895 "couldn't vectorize loop\n");
896 problem
->emit_and_clear ();
899 if (!loop_vinfo
|| !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
))
901 /* Free existing information if loop is analyzed with some
903 if (loop_constraint_set_p (loop
, LOOP_C_FINITE
))
904 vect_free_loop_info_assumptions (loop
);
906 /* If we applied if-conversion then try to vectorize the
907 BB of innermost loops.
908 ??? Ideally BB vectorization would learn to vectorize
909 control flow by applying if-conversion on-the-fly, the
910 following retains the if-converted loop body even when
911 only non-if-converted parts took part in BB vectorization. */
912 if (flag_tree_slp_vectorize
!= 0
913 && loop_vectorized_call
916 basic_block bb
= loop
->header
;
917 bool require_loop_vectorize
= false;
918 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
919 !gsi_end_p (gsi
); gsi_next (&gsi
))
921 gimple
*stmt
= gsi_stmt (gsi
);
922 gcall
*call
= dyn_cast
<gcall
*> (stmt
);
923 if (call
&& gimple_call_internal_p (call
))
925 internal_fn ifn
= gimple_call_internal_fn (call
);
926 if (ifn
== IFN_MASK_LOAD
|| ifn
== IFN_MASK_STORE
927 /* Don't keep the if-converted parts when the ifn with
928 specifc type is not supported by the backend. */
929 || (direct_internal_fn_p (ifn
)
930 && !direct_internal_fn_supported_p
931 (call
, OPTIMIZE_FOR_SPEED
)))
933 require_loop_vectorize
= true;
937 gimple_set_uid (stmt
, -1);
938 gimple_set_visited (stmt
, false);
940 if (!require_loop_vectorize
&& vect_slp_bb (bb
))
942 if (dump_enabled_p ())
943 dump_printf_loc (MSG_NOTE
, vect_location
,
944 "basic block vectorized\n");
945 fold_loop_internal_call (loop_vectorized_call
,
947 loop_vectorized_call
= NULL
;
948 ret
|= TODO_cleanup_cfg
;
951 /* If outer loop vectorization fails for LOOP_VECTORIZED guarded
952 loop, don't vectorize its inner loop; we'll attempt to
953 vectorize LOOP_VECTORIZED guarded inner loop of the scalar
955 if (loop_vectorized_call
&& loop
->inner
)
956 loop
->inner
->dont_vectorize
= true;
960 if (!dbg_cnt (vect_loop
))
962 /* Free existing information if loop is analyzed with some
964 if (loop_constraint_set_p (loop
, LOOP_C_FINITE
))
965 vect_free_loop_info_assumptions (loop
);
969 if (loop_vectorized_call
)
970 set_uid_loop_bbs (loop_vinfo
, loop_vectorized_call
);
972 unsigned HOST_WIDE_INT bytes
;
973 if (dump_enabled_p ())
975 if (current_vector_size
.is_constant (&bytes
))
976 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
977 "loop vectorized using %wu byte vectors\n", bytes
);
979 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
980 "loop vectorized using variable length vectors\n");
983 loop_p new_loop
= vect_transform_loop (loop_vinfo
);
984 (*num_vectorized_loops
)++;
985 /* Now that the loop has been vectorized, allow it to be unrolled
987 loop
->force_vectorize
= false;
991 simduid_to_vf
*simduid_to_vf_data
= XNEW (simduid_to_vf
);
992 if (!simduid_to_vf_htab
)
993 simduid_to_vf_htab
= new hash_table
<simduid_to_vf
> (15);
994 simduid_to_vf_data
->simduid
= DECL_UID (loop
->simduid
);
995 simduid_to_vf_data
->vf
= loop_vinfo
->vectorization_factor
;
996 *simduid_to_vf_htab
->find_slot (simduid_to_vf_data
, INSERT
)
997 = simduid_to_vf_data
;
1000 if (loop_vectorized_call
)
1002 fold_loop_internal_call (loop_vectorized_call
, boolean_true_node
);
1003 loop_vectorized_call
= NULL
;
1004 ret
|= TODO_cleanup_cfg
;
1006 if (loop_dist_alias_call
)
1008 tree value
= gimple_call_arg (loop_dist_alias_call
, 1);
1009 fold_loop_internal_call (loop_dist_alias_call
, value
);
1010 loop_dist_alias_call
= NULL
;
1011 ret
|= TODO_cleanup_cfg
;
1014 /* Epilogue of vectorized loop must be vectorized too. */
1016 ret
|= try_vectorize_loop_1 (simduid_to_vf_htab
, num_vectorized_loops
,
1017 new_loop
, loop_vinfo
, NULL
, NULL
);
1022 /* Try to vectorize LOOP. */
1025 try_vectorize_loop (hash_table
<simduid_to_vf
> *&simduid_to_vf_htab
,
1026 unsigned *num_vectorized_loops
, loop_p loop
)
1028 if (!((flag_tree_loop_vectorize
1029 && optimize_loop_nest_for_speed_p (loop
))
1030 || loop
->force_vectorize
))
1033 return try_vectorize_loop_1 (simduid_to_vf_htab
, num_vectorized_loops
,
1035 vect_loop_vectorized_call (loop
),
1036 vect_loop_dist_alias_call (loop
));
1040 /* Function vectorize_loops.
1042 Entry point to loop vectorization phase. */
1045 vectorize_loops (void)
1048 unsigned int num_vectorized_loops
= 0;
1049 unsigned int vect_loops_num
;
1051 hash_table
<simduid_to_vf
> *simduid_to_vf_htab
= NULL
;
1052 hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
= NULL
;
1053 bool any_ifcvt_loops
= false;
1056 vect_loops_num
= number_of_loops (cfun
);
1058 /* Bail out if there are no loops. */
1059 if (vect_loops_num
<= 1)
1062 if (cfun
->has_simduid_loops
)
1063 note_simd_array_uses (&simd_array_to_simduid_htab
);
1065 /* ----------- Analyze loops. ----------- */
1067 /* If some loop was duplicated, it gets bigger number
1068 than all previously defined loops. This fact allows us to run
1069 only over initial loops skipping newly generated ones. */
1070 FOR_EACH_LOOP (loop
, 0)
1071 if (loop
->dont_vectorize
)
1073 any_ifcvt_loops
= true;
1074 /* If-conversion sometimes versions both the outer loop
1075 (for the case when outer loop vectorization might be
1076 desirable) as well as the inner loop in the scalar version
1077 of the loop. So we have:
1078 if (LOOP_VECTORIZED (1, 3))
1084 loop3 (copy of loop1)
1085 if (LOOP_VECTORIZED (4, 5))
1086 loop4 (copy of loop2)
1088 loop5 (copy of loop4)
1089 If FOR_EACH_LOOP gives us loop3 first (which has
1090 dont_vectorize set), make sure to process loop1 before loop4;
1091 so that we can prevent vectorization of loop4 if loop1
1092 is successfully vectorized. */
1095 gimple
*loop_vectorized_call
1096 = vect_loop_vectorized_call (loop
);
1097 if (loop_vectorized_call
1098 && vect_loop_vectorized_call (loop
->inner
))
1100 tree arg
= gimple_call_arg (loop_vectorized_call
, 0);
1101 class loop
*vector_loop
1102 = get_loop (cfun
, tree_to_shwi (arg
));
1103 if (vector_loop
&& vector_loop
!= loop
)
1105 /* Make sure we don't vectorize it twice. */
1106 vector_loop
->dont_vectorize
= true;
1107 ret
|= try_vectorize_loop (simduid_to_vf_htab
,
1108 &num_vectorized_loops
,
1115 ret
|= try_vectorize_loop (simduid_to_vf_htab
, &num_vectorized_loops
,
1118 vect_location
= dump_user_location_t ();
1120 statistics_counter_event (cfun
, "Vectorized loops", num_vectorized_loops
);
1121 if (dump_enabled_p ()
1122 || (num_vectorized_loops
> 0 && dump_enabled_p ()))
1123 dump_printf_loc (MSG_NOTE
, vect_location
,
1124 "vectorized %u loops in function.\n",
1125 num_vectorized_loops
);
1127 /* ----------- Finalize. ----------- */
1129 if (any_ifcvt_loops
)
1130 for (i
= 1; i
< number_of_loops (cfun
); i
++)
1132 loop
= get_loop (cfun
, i
);
1133 if (loop
&& loop
->dont_vectorize
)
1135 gimple
*g
= vect_loop_vectorized_call (loop
);
1138 fold_loop_internal_call (g
, boolean_false_node
);
1139 ret
|= TODO_cleanup_cfg
;
1143 g
= vect_loop_dist_alias_call (loop
);
1147 fold_loop_internal_call (g
, boolean_false_node
);
1148 ret
|= TODO_cleanup_cfg
;
1153 for (i
= 1; i
< number_of_loops (cfun
); i
++)
1155 loop_vec_info loop_vinfo
;
1156 bool has_mask_store
;
1158 loop
= get_loop (cfun
, i
);
1159 if (!loop
|| !loop
->aux
)
1161 loop_vinfo
= (loop_vec_info
) loop
->aux
;
1162 has_mask_store
= LOOP_VINFO_HAS_MASK_STORE (loop_vinfo
);
1165 && targetm
.vectorize
.empty_mask_is_expensive (IFN_MASK_STORE
))
1166 optimize_mask_stores (loop
);
1170 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
1171 if (cfun
->has_simduid_loops
)
1172 adjust_simduid_builtins (simduid_to_vf_htab
);
1174 /* Shrink any "omp array simd" temporary arrays to the
1175 actual vectorization factors. */
1176 if (simd_array_to_simduid_htab
)
1177 shrink_simd_arrays (simd_array_to_simduid_htab
, simduid_to_vf_htab
);
1178 delete simduid_to_vf_htab
;
1179 cfun
->has_simduid_loops
= false;
1181 if (num_vectorized_loops
> 0)
1183 /* If we vectorized any loop only virtual SSA form needs to be updated.
1184 ??? Also while we try hard to update loop-closed SSA form we fail
1185 to properly do this in some corner-cases (see PR56286). */
1186 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa_only_virtuals
);
1187 return TODO_cleanup_cfg
;
1194 /* Entry point to the simduid cleanup pass. */
1198 const pass_data pass_data_simduid_cleanup
=
1200 GIMPLE_PASS
, /* type */
1201 "simduid", /* name */
1202 OPTGROUP_NONE
, /* optinfo_flags */
1203 TV_NONE
, /* tv_id */
1204 ( PROP_ssa
| PROP_cfg
), /* properties_required */
1205 0, /* properties_provided */
1206 0, /* properties_destroyed */
1207 0, /* todo_flags_start */
1208 0, /* todo_flags_finish */
1211 class pass_simduid_cleanup
: public gimple_opt_pass
1214 pass_simduid_cleanup (gcc::context
*ctxt
)
1215 : gimple_opt_pass (pass_data_simduid_cleanup
, ctxt
)
1218 /* opt_pass methods: */
1219 opt_pass
* clone () { return new pass_simduid_cleanup (m_ctxt
); }
1220 virtual bool gate (function
*fun
) { return fun
->has_simduid_loops
; }
1221 virtual unsigned int execute (function
*);
1223 }; // class pass_simduid_cleanup
1226 pass_simduid_cleanup::execute (function
*fun
)
1228 hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
= NULL
;
1230 note_simd_array_uses (&simd_array_to_simduid_htab
);
1232 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
1233 adjust_simduid_builtins (NULL
);
1235 /* Shrink any "omp array simd" temporary arrays to the
1236 actual vectorization factors. */
1237 if (simd_array_to_simduid_htab
)
1238 shrink_simd_arrays (simd_array_to_simduid_htab
, NULL
);
1239 fun
->has_simduid_loops
= false;
1246 make_pass_simduid_cleanup (gcc::context
*ctxt
)
1248 return new pass_simduid_cleanup (ctxt
);
1252 /* Entry point to basic block SLP phase. */
1256 const pass_data pass_data_slp_vectorize
=
1258 GIMPLE_PASS
, /* type */
1260 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
1261 TV_TREE_SLP_VECTORIZATION
, /* tv_id */
1262 ( PROP_ssa
| PROP_cfg
), /* properties_required */
1263 0, /* properties_provided */
1264 0, /* properties_destroyed */
1265 0, /* todo_flags_start */
1266 TODO_update_ssa
, /* todo_flags_finish */
1269 class pass_slp_vectorize
: public gimple_opt_pass
1272 pass_slp_vectorize (gcc::context
*ctxt
)
1273 : gimple_opt_pass (pass_data_slp_vectorize
, ctxt
)
1276 /* opt_pass methods: */
1277 opt_pass
* clone () { return new pass_slp_vectorize (m_ctxt
); }
1278 virtual bool gate (function
*) { return flag_tree_slp_vectorize
!= 0; }
1279 virtual unsigned int execute (function
*);
1281 }; // class pass_slp_vectorize
1284 pass_slp_vectorize::execute (function
*fun
)
1286 auto_purge_vect_location sentinel
;
1289 bool in_loop_pipeline
= scev_initialized_p ();
1290 if (!in_loop_pipeline
)
1292 loop_optimizer_init (LOOPS_NORMAL
);
1296 /* Mark all stmts as not belonging to the current region and unvisited. */
1297 FOR_EACH_BB_FN (bb
, fun
)
1299 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1302 gimple
*stmt
= gsi_stmt (gsi
);
1303 gimple_set_uid (stmt
, -1);
1304 gimple_set_visited (stmt
, false);
1308 FOR_EACH_BB_FN (bb
, fun
)
1310 if (vect_slp_bb (bb
))
1311 if (dump_enabled_p ())
1312 dump_printf_loc (MSG_NOTE
, vect_location
, "basic block vectorized\n");
1315 if (!in_loop_pipeline
)
1318 loop_optimizer_finalize ();
1327 make_pass_slp_vectorize (gcc::context
*ctxt
)
1329 return new pass_slp_vectorize (ctxt
);
1333 /* Increase alignment of global arrays to improve vectorization potential.
1335 - Consider also structs that have an array field.
1336 - Use ipa analysis to prune arrays that can't be vectorized?
1337 This should involve global alignment analysis and in the future also
1340 static unsigned get_vec_alignment_for_type (tree
);
1341 static hash_map
<tree
, unsigned> *type_align_map
;
1343 /* Return alignment of array's vector type corresponding to scalar type.
1344 0 if no vector type exists. */
1346 get_vec_alignment_for_array_type (tree type
)
1348 gcc_assert (TREE_CODE (type
) == ARRAY_TYPE
);
1349 poly_uint64 array_size
, vector_size
;
1351 tree vectype
= get_vectype_for_scalar_type (strip_array_types (type
));
1353 || !poly_int_tree_p (TYPE_SIZE (type
), &array_size
)
1354 || !poly_int_tree_p (TYPE_SIZE (vectype
), &vector_size
)
1355 || maybe_lt (array_size
, vector_size
))
1358 return TYPE_ALIGN (vectype
);
1361 /* Return alignment of field having maximum alignment of vector type
1362 corresponding to it's scalar type. For now, we only consider fields whose
1363 offset is a multiple of it's vector alignment.
1364 0 if no suitable field is found. */
1366 get_vec_alignment_for_record_type (tree type
)
1368 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
);
1370 unsigned max_align
= 0, alignment
;
1371 HOST_WIDE_INT offset
;
1374 if (TYPE_PACKED (type
))
1377 unsigned *slot
= type_align_map
->get (type
);
1381 for (tree field
= first_field (type
);
1383 field
= DECL_CHAIN (field
))
1385 /* Skip if not FIELD_DECL or if alignment is set by user. */
1386 if (TREE_CODE (field
) != FIELD_DECL
1387 || DECL_USER_ALIGN (field
)
1388 || DECL_ARTIFICIAL (field
))
1391 /* We don't need to process the type further if offset is variable,
1392 since the offsets of remaining members will also be variable. */
1393 if (TREE_CODE (DECL_FIELD_OFFSET (field
)) != INTEGER_CST
1394 || TREE_CODE (DECL_FIELD_BIT_OFFSET (field
)) != INTEGER_CST
)
1397 /* Similarly stop processing the type if offset_tree
1398 does not fit in unsigned HOST_WIDE_INT. */
1399 offset_tree
= bit_position (field
);
1400 if (!tree_fits_uhwi_p (offset_tree
))
1403 offset
= tree_to_uhwi (offset_tree
);
1404 alignment
= get_vec_alignment_for_type (TREE_TYPE (field
));
1406 /* Get maximum alignment of vectorized field/array among those members
1407 whose offset is multiple of the vector alignment. */
1409 && (offset
% alignment
== 0)
1410 && (alignment
> max_align
))
1411 max_align
= alignment
;
1414 type_align_map
->put (type
, max_align
);
1418 /* Return alignment of vector type corresponding to decl's scalar type
1419 or 0 if it doesn't exist or the vector alignment is lesser than
1420 decl's alignment. */
1422 get_vec_alignment_for_type (tree type
)
1424 if (type
== NULL_TREE
)
1427 gcc_assert (TYPE_P (type
));
1429 static unsigned alignment
= 0;
1430 switch (TREE_CODE (type
))
1433 alignment
= get_vec_alignment_for_array_type (type
);
1436 alignment
= get_vec_alignment_for_record_type (type
);
1443 return (alignment
> TYPE_ALIGN (type
)) ? alignment
: 0;
1446 /* Entry point to increase_alignment pass. */
1448 increase_alignment (void)
1450 varpool_node
*vnode
;
1452 vect_location
= dump_user_location_t ();
1453 type_align_map
= new hash_map
<tree
, unsigned>;
1455 /* Increase the alignment of all global arrays for vectorization. */
1456 FOR_EACH_DEFINED_VARIABLE (vnode
)
1458 tree decl
= vnode
->decl
;
1459 unsigned int alignment
;
1461 if ((decl_in_symtab_p (decl
)
1462 && !symtab_node::get (decl
)->can_increase_alignment_p ())
1463 || DECL_USER_ALIGN (decl
) || DECL_ARTIFICIAL (decl
))
1466 alignment
= get_vec_alignment_for_type (TREE_TYPE (decl
));
1467 if (alignment
&& vect_can_force_dr_alignment_p (decl
, alignment
))
1469 vnode
->increase_alignment (alignment
);
1470 if (dump_enabled_p ())
1471 dump_printf (MSG_NOTE
, "Increasing alignment of decl: %T\n", decl
);
1475 delete type_align_map
;
1482 const pass_data pass_data_ipa_increase_alignment
=
1484 SIMPLE_IPA_PASS
, /* type */
1485 "increase_alignment", /* name */
1486 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
1487 TV_IPA_OPT
, /* tv_id */
1488 0, /* properties_required */
1489 0, /* properties_provided */
1490 0, /* properties_destroyed */
1491 0, /* todo_flags_start */
1492 0, /* todo_flags_finish */
1495 class pass_ipa_increase_alignment
: public simple_ipa_opt_pass
1498 pass_ipa_increase_alignment (gcc::context
*ctxt
)
1499 : simple_ipa_opt_pass (pass_data_ipa_increase_alignment
, ctxt
)
1502 /* opt_pass methods: */
1503 virtual bool gate (function
*)
1505 return flag_section_anchors
&& flag_tree_loop_vectorize
;
1508 virtual unsigned int execute (function
*) { return increase_alignment (); }
1510 }; // class pass_ipa_increase_alignment
1514 simple_ipa_opt_pass
*
1515 make_pass_ipa_increase_alignment (gcc::context
*ctxt
)
1517 return new pass_ipa_increase_alignment (ctxt
);