2 Copyright (C) 2003-2018 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"
84 /* Loop or bb location. */
85 source_location vect_location
;
87 /* Vector mapping GIMPLE stmt to stmt_vec_info. */
88 vec
<stmt_vec_info
> *stmt_vec_info_vec
;
90 /* Dump a cost entry according to args to F. */
93 dump_stmt_cost (FILE *f
, void *data
, int count
, enum vect_cost_for_stmt kind
,
94 stmt_vec_info stmt_info
, int misalign
,
95 enum vect_cost_model_location where
)
97 fprintf (f
, "%p ", data
);
100 print_gimple_expr (f
, STMT_VINFO_STMT (stmt_info
), 0, TDF_SLIM
);
104 fprintf (f
, "<unknown> ");
105 fprintf (f
, "%d times ", count
);
106 const char *ks
= "unknown";
124 case vector_gather_load
:
125 ks
= "vector_gather_load";
128 ks
= "unaligned_load";
130 case unaligned_store
:
131 ks
= "unaligned_store";
134 ks
= "unaligned_store";
136 case vector_scatter_store
:
137 ks
= "unaligned_store";
140 ks
= "unaligned_store";
143 ks
= "unaligned_store";
145 case cond_branch_not_taken
:
146 ks
= "unaligned_store";
148 case cond_branch_taken
:
149 ks
= "unaligned_store";
152 ks
= "unaligned_store";
154 case vec_promote_demote
:
155 ks
= "unaligned_store";
158 ks
= "unaligned_store";
161 fprintf (f
, "%s ", ks
);
162 if (kind
== unaligned_load
|| kind
== unaligned_store
)
163 fprintf (f
, "(misalign %d) ", misalign
);
164 const char *ws
= "unknown";
177 fprintf (f
, "in %s\n", ws
);
180 /* For mapping simduid to vectorization factor. */
182 struct simduid_to_vf
: free_ptr_hash
<simduid_to_vf
>
184 unsigned int simduid
;
187 /* hash_table support. */
188 static inline hashval_t
hash (const simduid_to_vf
*);
189 static inline int equal (const simduid_to_vf
*, const simduid_to_vf
*);
193 simduid_to_vf::hash (const simduid_to_vf
*p
)
199 simduid_to_vf::equal (const simduid_to_vf
*p1
, const simduid_to_vf
*p2
)
201 return p1
->simduid
== p2
->simduid
;
204 /* This hash maps the OMP simd array to the corresponding simduid used
205 to index into it. Like thus,
207 _7 = GOMP_SIMD_LANE (simduid.0)
213 This hash maps from the OMP simd array (D.1737[]) to DECL_UID of
216 struct simd_array_to_simduid
: free_ptr_hash
<simd_array_to_simduid
>
219 unsigned int simduid
;
221 /* hash_table support. */
222 static inline hashval_t
hash (const simd_array_to_simduid
*);
223 static inline int equal (const simd_array_to_simduid
*,
224 const simd_array_to_simduid
*);
228 simd_array_to_simduid::hash (const simd_array_to_simduid
*p
)
230 return DECL_UID (p
->decl
);
234 simd_array_to_simduid::equal (const simd_array_to_simduid
*p1
,
235 const simd_array_to_simduid
*p2
)
237 return p1
->decl
== p2
->decl
;
240 /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LAST_LANE,
241 into their corresponding constants and remove
242 IFN_GOMP_SIMD_ORDERED_{START,END}. */
245 adjust_simduid_builtins (hash_table
<simduid_to_vf
> *htab
)
249 FOR_EACH_BB_FN (bb
, cfun
)
251 gimple_stmt_iterator i
;
253 for (i
= gsi_start_bb (bb
); !gsi_end_p (i
); )
256 enum internal_fn ifn
;
257 gimple
*stmt
= gsi_stmt (i
);
259 if (!is_gimple_call (stmt
)
260 || !gimple_call_internal_p (stmt
))
265 ifn
= gimple_call_internal_fn (stmt
);
268 case IFN_GOMP_SIMD_LANE
:
269 case IFN_GOMP_SIMD_VF
:
270 case IFN_GOMP_SIMD_LAST_LANE
:
272 case IFN_GOMP_SIMD_ORDERED_START
:
273 case IFN_GOMP_SIMD_ORDERED_END
:
274 if (integer_onep (gimple_call_arg (stmt
, 0)))
276 enum built_in_function bcode
277 = (ifn
== IFN_GOMP_SIMD_ORDERED_START
278 ? BUILT_IN_GOMP_ORDERED_START
279 : BUILT_IN_GOMP_ORDERED_END
);
281 = gimple_build_call (builtin_decl_explicit (bcode
), 0);
282 tree vdef
= gimple_vdef (stmt
);
283 gimple_set_vdef (g
, vdef
);
284 SSA_NAME_DEF_STMT (vdef
) = g
;
285 gimple_set_vuse (g
, gimple_vuse (stmt
));
286 gsi_replace (&i
, g
, true);
289 gsi_remove (&i
, true);
290 unlink_stmt_vdef (stmt
);
296 tree arg
= gimple_call_arg (stmt
, 0);
297 gcc_assert (arg
!= NULL_TREE
);
298 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
299 simduid_to_vf
*p
= NULL
, data
;
300 data
.simduid
= DECL_UID (SSA_NAME_VAR (arg
));
301 /* Need to nullify loop safelen field since it's value is not
302 valid after transformation. */
303 if (bb
->loop_father
&& bb
->loop_father
->safelen
> 0)
304 bb
->loop_father
->safelen
= 0;
307 p
= htab
->find (&data
);
313 case IFN_GOMP_SIMD_VF
:
314 t
= build_int_cst (unsigned_type_node
, vf
);
316 case IFN_GOMP_SIMD_LANE
:
317 t
= build_int_cst (unsigned_type_node
, 0);
319 case IFN_GOMP_SIMD_LAST_LANE
:
320 t
= gimple_call_arg (stmt
, 1);
325 tree lhs
= gimple_call_lhs (stmt
);
327 replace_uses_by (lhs
, t
);
329 gsi_remove (&i
, true);
334 /* Helper structure for note_simd_array_uses. */
336 struct note_simd_array_uses_struct
338 hash_table
<simd_array_to_simduid
> **htab
;
339 unsigned int simduid
;
342 /* Callback for note_simd_array_uses, called through walk_gimple_op. */
345 note_simd_array_uses_cb (tree
*tp
, int *walk_subtrees
, void *data
)
347 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
348 struct note_simd_array_uses_struct
*ns
349 = (struct note_simd_array_uses_struct
*) wi
->info
;
354 && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp
))
355 && DECL_CONTEXT (*tp
) == current_function_decl
)
357 simd_array_to_simduid data
;
359 *ns
->htab
= new hash_table
<simd_array_to_simduid
> (15);
361 data
.simduid
= ns
->simduid
;
362 simd_array_to_simduid
**slot
= (*ns
->htab
)->find_slot (&data
, INSERT
);
365 simd_array_to_simduid
*p
= XNEW (simd_array_to_simduid
);
369 else if ((*slot
)->simduid
!= ns
->simduid
)
370 (*slot
)->simduid
= -1U;
376 /* Find "omp simd array" temporaries and map them to corresponding
380 note_simd_array_uses (hash_table
<simd_array_to_simduid
> **htab
)
383 gimple_stmt_iterator gsi
;
384 struct walk_stmt_info wi
;
385 struct note_simd_array_uses_struct ns
;
387 memset (&wi
, 0, sizeof (wi
));
391 FOR_EACH_BB_FN (bb
, cfun
)
392 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
394 gimple
*stmt
= gsi_stmt (gsi
);
395 if (!is_gimple_call (stmt
) || !gimple_call_internal_p (stmt
))
397 switch (gimple_call_internal_fn (stmt
))
399 case IFN_GOMP_SIMD_LANE
:
400 case IFN_GOMP_SIMD_VF
:
401 case IFN_GOMP_SIMD_LAST_LANE
:
406 tree lhs
= gimple_call_lhs (stmt
);
407 if (lhs
== NULL_TREE
)
409 imm_use_iterator use_iter
;
411 ns
.simduid
= DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt
, 0)));
412 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, lhs
)
413 if (!is_gimple_debug (use_stmt
))
414 walk_gimple_op (use_stmt
, note_simd_array_uses_cb
, &wi
);
418 /* Shrink arrays with "omp simd array" attribute to the corresponding
419 vectorization factor. */
423 (hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
,
424 hash_table
<simduid_to_vf
> *simduid_to_vf_htab
)
426 for (hash_table
<simd_array_to_simduid
>::iterator iter
427 = simd_array_to_simduid_htab
->begin ();
428 iter
!= simd_array_to_simduid_htab
->end (); ++iter
)
429 if ((*iter
)->simduid
!= -1U)
431 tree decl
= (*iter
)->decl
;
433 if (simduid_to_vf_htab
)
435 simduid_to_vf
*p
= NULL
, data
;
436 data
.simduid
= (*iter
)->simduid
;
437 p
= simduid_to_vf_htab
->find (&data
);
442 = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl
)), vf
);
443 TREE_TYPE (decl
) = atype
;
444 relayout_decl (decl
);
447 delete simd_array_to_simduid_htab
;
450 /* Initialize the vec_info with kind KIND_IN and target cost data
451 TARGET_COST_DATA_IN. */
453 vec_info::vec_info (vec_info::vec_kind kind_in
, void *target_cost_data_in
)
457 target_cost_data (target_cost_data_in
)
459 stmt_vec_infos
.create (50);
460 set_stmt_vec_info_vec (&stmt_vec_infos
);
463 vec_info::~vec_info ()
465 slp_instance instance
;
466 struct data_reference
*dr
;
469 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
476 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
477 vect_free_slp_instance (instance
);
479 free_data_refs (datarefs
);
480 free_dependence_relations (ddrs
);
481 destroy_cost_data (target_cost_data
);
482 free_stmt_vec_infos (&stmt_vec_infos
);
485 /* A helper function to free scev and LOOP niter information, as well as
486 clear loop constraint LOOP_C_FINITE. */
489 vect_free_loop_info_assumptions (struct loop
*loop
)
492 /* We need to explicitly reset upper bound information since they are
493 used even after free_numbers_of_iterations_estimates. */
494 loop
->any_upper_bound
= false;
495 loop
->any_likely_upper_bound
= false;
496 free_numbers_of_iterations_estimates (loop
);
497 loop_constraint_clear (loop
, LOOP_C_FINITE
);
500 /* Return whether STMT is inside the region we try to vectorize. */
503 vect_stmt_in_region_p (vec_info
*vinfo
, gimple
*stmt
)
505 if (!gimple_bb (stmt
))
508 if (loop_vec_info loop_vinfo
= dyn_cast
<loop_vec_info
> (vinfo
))
510 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
511 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
516 bb_vec_info bb_vinfo
= as_a
<bb_vec_info
> (vinfo
);
517 if (gimple_bb (stmt
) != BB_VINFO_BB (bb_vinfo
)
518 || gimple_uid (stmt
) == -1U
519 || gimple_code (stmt
) == GIMPLE_PHI
)
527 /* If LOOP has been versioned during ifcvt, return the internal call
531 vect_loop_vectorized_call (struct loop
*loop
)
533 basic_block bb
= loop_preheader_edge (loop
)->src
;
540 if (!single_pred_p (bb
))
542 bb
= single_pred (bb
);
545 if (g
&& gimple_code (g
) == GIMPLE_COND
)
547 gimple_stmt_iterator gsi
= gsi_for_stmt (g
);
549 if (!gsi_end_p (gsi
))
552 if (gimple_call_internal_p (g
, IFN_LOOP_VECTORIZED
)
553 && (tree_to_shwi (gimple_call_arg (g
, 0)) == loop
->num
554 || tree_to_shwi (gimple_call_arg (g
, 1)) == loop
->num
))
561 /* If LOOP has been versioned during loop distribution, return the gurading
565 vect_loop_dist_alias_call (struct loop
*loop
)
569 struct loop
*outer
, *orig
;
570 gimple_stmt_iterator gsi
;
573 if (loop
->orig_loop_num
== 0)
576 orig
= get_loop (cfun
, loop
->orig_loop_num
);
579 /* The original loop is somehow destroyed. Clear the information. */
580 loop
->orig_loop_num
= 0;
585 bb
= nearest_common_dominator (CDI_DOMINATORS
, loop
->header
, orig
->header
);
587 bb
= loop_preheader_edge (loop
)->src
;
589 outer
= bb
->loop_father
;
590 entry
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
592 /* Look upward in dominance tree. */
593 for (; bb
!= entry
&& flow_bb_inside_loop_p (outer
, bb
);
594 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
597 if (g
== NULL
|| gimple_code (g
) != GIMPLE_COND
)
600 gsi
= gsi_for_stmt (g
);
606 /* The guarding internal function call must have the same distribution
608 if (gimple_call_internal_p (g
, IFN_LOOP_DIST_ALIAS
)
609 && (tree_to_shwi (gimple_call_arg (g
, 0)) == loop
->orig_loop_num
))
615 /* Set the uids of all the statements in basic blocks inside loop
616 represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal
617 call guarding the loop which has been if converted. */
619 set_uid_loop_bbs (loop_vec_info loop_vinfo
, gimple
*loop_vectorized_call
)
621 tree arg
= gimple_call_arg (loop_vectorized_call
, 1);
624 struct loop
*scalar_loop
= get_loop (cfun
, tree_to_shwi (arg
));
626 LOOP_VINFO_SCALAR_LOOP (loop_vinfo
) = scalar_loop
;
627 gcc_checking_assert (vect_loop_vectorized_call (scalar_loop
)
628 == loop_vectorized_call
);
629 /* If we are going to vectorize outer loop, prevent vectorization
630 of the inner loop in the scalar loop - either the scalar loop is
631 thrown away, so it is a wasted work, or is used only for
633 if (scalar_loop
->inner
)
635 gimple
*g
= vect_loop_vectorized_call (scalar_loop
->inner
);
638 arg
= gimple_call_arg (g
, 0);
639 get_loop (cfun
, tree_to_shwi (arg
))->dont_vectorize
= true;
640 fold_loop_internal_call (g
, boolean_false_node
);
643 bbs
= get_loop_body (scalar_loop
);
644 for (i
= 0; i
< scalar_loop
->num_nodes
; i
++)
646 basic_block bb
= bbs
[i
];
647 gimple_stmt_iterator gsi
;
648 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
650 gimple
*phi
= gsi_stmt (gsi
);
651 gimple_set_uid (phi
, 0);
653 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
655 gimple
*stmt
= gsi_stmt (gsi
);
656 gimple_set_uid (stmt
, 0);
662 /* Function vectorize_loops.
664 Entry point to loop vectorization phase. */
667 vectorize_loops (void)
670 unsigned int num_vectorized_loops
= 0;
671 unsigned int vect_loops_num
;
673 hash_table
<simduid_to_vf
> *simduid_to_vf_htab
= NULL
;
674 hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
= NULL
;
675 bool any_ifcvt_loops
= false;
677 struct loop
*new_loop
;
679 vect_loops_num
= number_of_loops (cfun
);
681 /* Bail out if there are no loops. */
682 if (vect_loops_num
<= 1)
685 if (cfun
->has_simduid_loops
)
686 note_simd_array_uses (&simd_array_to_simduid_htab
);
688 set_stmt_vec_info_vec (NULL
);
690 /* ----------- Analyze loops. ----------- */
692 /* If some loop was duplicated, it gets bigger number
693 than all previously defined loops. This fact allows us to run
694 only over initial loops skipping newly generated ones. */
695 FOR_EACH_LOOP (loop
, 0)
696 if (loop
->dont_vectorize
)
698 any_ifcvt_loops
= true;
699 /* If-conversion sometimes versions both the outer loop
700 (for the case when outer loop vectorization might be
701 desirable) as well as the inner loop in the scalar version
702 of the loop. So we have:
703 if (LOOP_VECTORIZED (1, 3))
709 loop3 (copy of loop1)
710 if (LOOP_VECTORIZED (4, 5))
711 loop4 (copy of loop2)
713 loop5 (copy of loop4)
714 If FOR_EACH_LOOP gives us loop3 first (which has
715 dont_vectorize set), make sure to process loop1 before loop4;
716 so that we can prevent vectorization of loop4 if loop1
717 is successfully vectorized. */
720 gimple
*loop_vectorized_call
721 = vect_loop_vectorized_call (loop
);
722 if (loop_vectorized_call
723 && vect_loop_vectorized_call (loop
->inner
))
725 tree arg
= gimple_call_arg (loop_vectorized_call
, 0);
726 struct loop
*vector_loop
727 = get_loop (cfun
, tree_to_shwi (arg
));
728 if (vector_loop
&& vector_loop
!= loop
)
731 /* Make sure we don't vectorize it twice. */
732 loop
->dont_vectorize
= true;
740 loop_vec_info loop_vinfo
, orig_loop_vinfo
;
741 gimple
*loop_vectorized_call
, *loop_dist_alias_call
;
743 if (!((flag_tree_loop_vectorize
744 && optimize_loop_nest_for_speed_p (loop
))
745 || loop
->force_vectorize
))
747 orig_loop_vinfo
= NULL
;
748 loop_vectorized_call
= vect_loop_vectorized_call (loop
);
749 loop_dist_alias_call
= vect_loop_dist_alias_call (loop
);
751 vect_location
= find_loop_location (loop
);
752 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOCATION
753 && dump_enabled_p ())
754 dump_printf (MSG_NOTE
, "\nAnalyzing loop at %s:%d\n",
755 LOCATION_FILE (vect_location
),
756 LOCATION_LINE (vect_location
));
758 loop_vinfo
= vect_analyze_loop (loop
, orig_loop_vinfo
);
759 loop
->aux
= loop_vinfo
;
761 if (!loop_vinfo
|| !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
))
763 /* Free existing information if loop is analyzed with some
765 if (loop_constraint_set_p (loop
, LOOP_C_FINITE
))
766 vect_free_loop_info_assumptions (loop
);
768 /* If we applied if-conversion then try to vectorize the
769 BB of innermost loops.
770 ??? Ideally BB vectorization would learn to vectorize
771 control flow by applying if-conversion on-the-fly, the
772 following retains the if-converted loop body even when
773 only non-if-converted parts took part in BB vectorization. */
774 if (flag_tree_slp_vectorize
!= 0
775 && loop_vectorized_call
778 basic_block bb
= loop
->header
;
779 bool has_mask_load_store
= false;
780 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
781 !gsi_end_p (gsi
); gsi_next (&gsi
))
783 gimple
*stmt
= gsi_stmt (gsi
);
784 if (is_gimple_call (stmt
)
785 && gimple_call_internal_p (stmt
)
786 && (gimple_call_internal_fn (stmt
) == IFN_MASK_LOAD
787 || gimple_call_internal_fn (stmt
) == IFN_MASK_STORE
))
789 has_mask_load_store
= true;
792 gimple_set_uid (stmt
, -1);
793 gimple_set_visited (stmt
, false);
795 if (! has_mask_load_store
&& vect_slp_bb (bb
))
797 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
798 "basic block vectorized\n");
799 fold_loop_internal_call (loop_vectorized_call
,
801 loop_vectorized_call
= NULL
;
802 ret
|= TODO_cleanup_cfg
;
805 /* If outer loop vectorization fails for LOOP_VECTORIZED guarded
806 loop, don't vectorize its inner loop; we'll attempt to
807 vectorize LOOP_VECTORIZED guarded inner loop of the scalar
809 if (loop_vectorized_call
&& loop
->inner
)
810 loop
->inner
->dont_vectorize
= true;
814 if (!dbg_cnt (vect_loop
))
816 /* We may miss some if-converted loops due to
817 debug counter. Set any_ifcvt_loops to visit
818 them at finalization. */
819 any_ifcvt_loops
= true;
820 /* Free existing information if loop is analyzed with some
822 if (loop_constraint_set_p (loop
, LOOP_C_FINITE
))
823 vect_free_loop_info_assumptions (loop
);
828 if (loop_vectorized_call
)
829 set_uid_loop_bbs (loop_vinfo
, loop_vectorized_call
);
830 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOCATION
831 && dump_enabled_p ())
832 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
833 "loop vectorized\n");
834 new_loop
= vect_transform_loop (loop_vinfo
);
835 num_vectorized_loops
++;
836 /* Now that the loop has been vectorized, allow it to be unrolled
838 loop
->force_vectorize
= false;
842 simduid_to_vf
*simduid_to_vf_data
= XNEW (simduid_to_vf
);
843 if (!simduid_to_vf_htab
)
844 simduid_to_vf_htab
= new hash_table
<simduid_to_vf
> (15);
845 simduid_to_vf_data
->simduid
= DECL_UID (loop
->simduid
);
846 simduid_to_vf_data
->vf
= loop_vinfo
->vectorization_factor
;
847 *simduid_to_vf_htab
->find_slot (simduid_to_vf_data
, INSERT
)
848 = simduid_to_vf_data
;
851 if (loop_vectorized_call
)
853 fold_loop_internal_call (loop_vectorized_call
, boolean_true_node
);
854 loop_vectorized_call
= NULL
;
855 ret
|= TODO_cleanup_cfg
;
857 if (loop_dist_alias_call
)
859 tree value
= gimple_call_arg (loop_dist_alias_call
, 1);
860 fold_loop_internal_call (loop_dist_alias_call
, value
);
861 loop_dist_alias_call
= NULL
;
862 ret
|= TODO_cleanup_cfg
;
867 /* Epilogue of vectorized loop must be vectorized too. */
868 vect_loops_num
= number_of_loops (cfun
);
870 orig_loop_vinfo
= loop_vinfo
; /* To pass vect_analyze_loop. */
871 goto vectorize_epilogue
;
875 vect_location
= UNKNOWN_LOCATION
;
877 statistics_counter_event (cfun
, "Vectorized loops", num_vectorized_loops
);
878 if (dump_enabled_p ()
879 || (num_vectorized_loops
> 0 && dump_enabled_p ()))
880 dump_printf_loc (MSG_NOTE
, vect_location
,
881 "vectorized %u loops in function.\n",
882 num_vectorized_loops
);
884 /* ----------- Finalize. ----------- */
887 for (i
= 1; i
< vect_loops_num
; i
++)
889 loop
= get_loop (cfun
, i
);
890 if (loop
&& loop
->dont_vectorize
)
892 gimple
*g
= vect_loop_vectorized_call (loop
);
895 fold_loop_internal_call (g
, boolean_false_node
);
896 ret
|= TODO_cleanup_cfg
;
900 g
= vect_loop_dist_alias_call (loop
);
904 fold_loop_internal_call (g
, boolean_false_node
);
905 ret
|= TODO_cleanup_cfg
;
910 for (i
= 1; i
< vect_loops_num
; i
++)
912 loop_vec_info loop_vinfo
;
915 loop
= get_loop (cfun
, i
);
918 loop_vinfo
= (loop_vec_info
) loop
->aux
;
919 has_mask_store
= false;
921 has_mask_store
= LOOP_VINFO_HAS_MASK_STORE (loop_vinfo
);
924 && targetm
.vectorize
.empty_mask_is_expensive (IFN_MASK_STORE
))
925 optimize_mask_stores (loop
);
929 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
930 if (cfun
->has_simduid_loops
)
931 adjust_simduid_builtins (simduid_to_vf_htab
);
933 /* Shrink any "omp array simd" temporary arrays to the
934 actual vectorization factors. */
935 if (simd_array_to_simduid_htab
)
936 shrink_simd_arrays (simd_array_to_simduid_htab
, simduid_to_vf_htab
);
937 delete simduid_to_vf_htab
;
938 cfun
->has_simduid_loops
= false;
940 if (num_vectorized_loops
> 0)
942 /* If we vectorized any loop only virtual SSA form needs to be updated.
943 ??? Also while we try hard to update loop-closed SSA form we fail
944 to properly do this in some corner-cases (see PR56286). */
945 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa_only_virtuals
);
946 return TODO_cleanup_cfg
;
953 /* Entry point to the simduid cleanup pass. */
957 const pass_data pass_data_simduid_cleanup
=
959 GIMPLE_PASS
, /* type */
960 "simduid", /* name */
961 OPTGROUP_NONE
, /* optinfo_flags */
963 ( PROP_ssa
| PROP_cfg
), /* properties_required */
964 0, /* properties_provided */
965 0, /* properties_destroyed */
966 0, /* todo_flags_start */
967 0, /* todo_flags_finish */
970 class pass_simduid_cleanup
: public gimple_opt_pass
973 pass_simduid_cleanup (gcc::context
*ctxt
)
974 : gimple_opt_pass (pass_data_simduid_cleanup
, ctxt
)
977 /* opt_pass methods: */
978 opt_pass
* clone () { return new pass_simduid_cleanup (m_ctxt
); }
979 virtual bool gate (function
*fun
) { return fun
->has_simduid_loops
; }
980 virtual unsigned int execute (function
*);
982 }; // class pass_simduid_cleanup
985 pass_simduid_cleanup::execute (function
*fun
)
987 hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
= NULL
;
989 note_simd_array_uses (&simd_array_to_simduid_htab
);
991 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
992 adjust_simduid_builtins (NULL
);
994 /* Shrink any "omp array simd" temporary arrays to the
995 actual vectorization factors. */
996 if (simd_array_to_simduid_htab
)
997 shrink_simd_arrays (simd_array_to_simduid_htab
, NULL
);
998 fun
->has_simduid_loops
= false;
1005 make_pass_simduid_cleanup (gcc::context
*ctxt
)
1007 return new pass_simduid_cleanup (ctxt
);
1011 /* Entry point to basic block SLP phase. */
1015 const pass_data pass_data_slp_vectorize
=
1017 GIMPLE_PASS
, /* type */
1019 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
1020 TV_TREE_SLP_VECTORIZATION
, /* tv_id */
1021 ( PROP_ssa
| PROP_cfg
), /* properties_required */
1022 0, /* properties_provided */
1023 0, /* properties_destroyed */
1024 0, /* todo_flags_start */
1025 TODO_update_ssa
, /* todo_flags_finish */
1028 class pass_slp_vectorize
: public gimple_opt_pass
1031 pass_slp_vectorize (gcc::context
*ctxt
)
1032 : gimple_opt_pass (pass_data_slp_vectorize
, ctxt
)
1035 /* opt_pass methods: */
1036 opt_pass
* clone () { return new pass_slp_vectorize (m_ctxt
); }
1037 virtual bool gate (function
*) { return flag_tree_slp_vectorize
!= 0; }
1038 virtual unsigned int execute (function
*);
1040 }; // class pass_slp_vectorize
1043 pass_slp_vectorize::execute (function
*fun
)
1047 bool in_loop_pipeline
= scev_initialized_p ();
1048 if (!in_loop_pipeline
)
1050 loop_optimizer_init (LOOPS_NORMAL
);
1054 /* Mark all stmts as not belonging to the current region and unvisited. */
1055 FOR_EACH_BB_FN (bb
, fun
)
1057 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1060 gimple
*stmt
= gsi_stmt (gsi
);
1061 gimple_set_uid (stmt
, -1);
1062 gimple_set_visited (stmt
, false);
1066 FOR_EACH_BB_FN (bb
, fun
)
1068 if (vect_slp_bb (bb
))
1069 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
1070 "basic block vectorized\n");
1073 if (!in_loop_pipeline
)
1076 loop_optimizer_finalize ();
1085 make_pass_slp_vectorize (gcc::context
*ctxt
)
1087 return new pass_slp_vectorize (ctxt
);
1091 /* Increase alignment of global arrays to improve vectorization potential.
1093 - Consider also structs that have an array field.
1094 - Use ipa analysis to prune arrays that can't be vectorized?
1095 This should involve global alignment analysis and in the future also
1098 static unsigned get_vec_alignment_for_type (tree
);
1099 static hash_map
<tree
, unsigned> *type_align_map
;
1101 /* Return alignment of array's vector type corresponding to scalar type.
1102 0 if no vector type exists. */
1104 get_vec_alignment_for_array_type (tree type
)
1106 gcc_assert (TREE_CODE (type
) == ARRAY_TYPE
);
1107 poly_uint64 array_size
, vector_size
;
1109 tree vectype
= get_vectype_for_scalar_type (strip_array_types (type
));
1111 || !poly_int_tree_p (TYPE_SIZE (type
), &array_size
)
1112 || !poly_int_tree_p (TYPE_SIZE (vectype
), &vector_size
)
1113 || maybe_lt (array_size
, vector_size
))
1116 return TYPE_ALIGN (vectype
);
1119 /* Return alignment of field having maximum alignment of vector type
1120 corresponding to it's scalar type. For now, we only consider fields whose
1121 offset is a multiple of it's vector alignment.
1122 0 if no suitable field is found. */
1124 get_vec_alignment_for_record_type (tree type
)
1126 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
);
1128 unsigned max_align
= 0, alignment
;
1129 HOST_WIDE_INT offset
;
1132 if (TYPE_PACKED (type
))
1135 unsigned *slot
= type_align_map
->get (type
);
1139 for (tree field
= first_field (type
);
1141 field
= DECL_CHAIN (field
))
1143 /* Skip if not FIELD_DECL or if alignment is set by user. */
1144 if (TREE_CODE (field
) != FIELD_DECL
1145 || DECL_USER_ALIGN (field
)
1146 || DECL_ARTIFICIAL (field
))
1149 /* We don't need to process the type further if offset is variable,
1150 since the offsets of remaining members will also be variable. */
1151 if (TREE_CODE (DECL_FIELD_OFFSET (field
)) != INTEGER_CST
1152 || TREE_CODE (DECL_FIELD_BIT_OFFSET (field
)) != INTEGER_CST
)
1155 /* Similarly stop processing the type if offset_tree
1156 does not fit in unsigned HOST_WIDE_INT. */
1157 offset_tree
= bit_position (field
);
1158 if (!tree_fits_uhwi_p (offset_tree
))
1161 offset
= tree_to_uhwi (offset_tree
);
1162 alignment
= get_vec_alignment_for_type (TREE_TYPE (field
));
1164 /* Get maximum alignment of vectorized field/array among those members
1165 whose offset is multiple of the vector alignment. */
1167 && (offset
% alignment
== 0)
1168 && (alignment
> max_align
))
1169 max_align
= alignment
;
1172 type_align_map
->put (type
, max_align
);
1176 /* Return alignment of vector type corresponding to decl's scalar type
1177 or 0 if it doesn't exist or the vector alignment is lesser than
1178 decl's alignment. */
1180 get_vec_alignment_for_type (tree type
)
1182 if (type
== NULL_TREE
)
1185 gcc_assert (TYPE_P (type
));
1187 static unsigned alignment
= 0;
1188 switch (TREE_CODE (type
))
1191 alignment
= get_vec_alignment_for_array_type (type
);
1194 alignment
= get_vec_alignment_for_record_type (type
);
1201 return (alignment
> TYPE_ALIGN (type
)) ? alignment
: 0;
1204 /* Entry point to increase_alignment pass. */
1206 increase_alignment (void)
1208 varpool_node
*vnode
;
1210 vect_location
= UNKNOWN_LOCATION
;
1211 type_align_map
= new hash_map
<tree
, unsigned>;
1213 /* Increase the alignment of all global arrays for vectorization. */
1214 FOR_EACH_DEFINED_VARIABLE (vnode
)
1216 tree decl
= vnode
->decl
;
1217 unsigned int alignment
;
1219 if ((decl_in_symtab_p (decl
)
1220 && !symtab_node::get (decl
)->can_increase_alignment_p ())
1221 || DECL_USER_ALIGN (decl
) || DECL_ARTIFICIAL (decl
))
1224 alignment
= get_vec_alignment_for_type (TREE_TYPE (decl
));
1225 if (alignment
&& vect_can_force_dr_alignment_p (decl
, alignment
))
1227 vnode
->increase_alignment (alignment
);
1228 dump_printf (MSG_NOTE
, "Increasing alignment of decl: ");
1229 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, decl
);
1230 dump_printf (MSG_NOTE
, "\n");
1234 delete type_align_map
;
1241 const pass_data pass_data_ipa_increase_alignment
=
1243 SIMPLE_IPA_PASS
, /* type */
1244 "increase_alignment", /* name */
1245 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
1246 TV_IPA_OPT
, /* tv_id */
1247 0, /* properties_required */
1248 0, /* properties_provided */
1249 0, /* properties_destroyed */
1250 0, /* todo_flags_start */
1251 0, /* todo_flags_finish */
1254 class pass_ipa_increase_alignment
: public simple_ipa_opt_pass
1257 pass_ipa_increase_alignment (gcc::context
*ctxt
)
1258 : simple_ipa_opt_pass (pass_data_ipa_increase_alignment
, ctxt
)
1261 /* opt_pass methods: */
1262 virtual bool gate (function
*)
1264 return flag_section_anchors
&& flag_tree_loop_vectorize
;
1267 virtual unsigned int execute (function
*) { return increase_alignment (); }
1269 }; // class pass_ipa_increase_alignment
1273 simple_ipa_opt_pass
*
1274 make_pass_ipa_increase_alignment (gcc::context
*ctxt
)
1276 return new pass_ipa_increase_alignment (ctxt
);