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"
83 /* Loop or bb location. */
84 source_location vect_location
;
86 /* Vector mapping GIMPLE stmt to stmt_vec_info. */
87 vec
<stmt_vec_info
> stmt_vec_info_vec
;
89 /* For mapping simduid to vectorization factor. */
91 struct simduid_to_vf
: free_ptr_hash
<simduid_to_vf
>
96 /* hash_table support. */
97 static inline hashval_t
hash (const simduid_to_vf
*);
98 static inline int equal (const simduid_to_vf
*, const simduid_to_vf
*);
102 simduid_to_vf::hash (const simduid_to_vf
*p
)
108 simduid_to_vf::equal (const simduid_to_vf
*p1
, const simduid_to_vf
*p2
)
110 return p1
->simduid
== p2
->simduid
;
113 /* This hash maps the OMP simd array to the corresponding simduid used
114 to index into it. Like thus,
116 _7 = GOMP_SIMD_LANE (simduid.0)
122 This hash maps from the OMP simd array (D.1737[]) to DECL_UID of
125 struct simd_array_to_simduid
: free_ptr_hash
<simd_array_to_simduid
>
128 unsigned int simduid
;
130 /* hash_table support. */
131 static inline hashval_t
hash (const simd_array_to_simduid
*);
132 static inline int equal (const simd_array_to_simduid
*,
133 const simd_array_to_simduid
*);
137 simd_array_to_simduid::hash (const simd_array_to_simduid
*p
)
139 return DECL_UID (p
->decl
);
143 simd_array_to_simduid::equal (const simd_array_to_simduid
*p1
,
144 const simd_array_to_simduid
*p2
)
146 return p1
->decl
== p2
->decl
;
149 /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LAST_LANE,
150 into their corresponding constants and remove
151 IFN_GOMP_SIMD_ORDERED_{START,END}. */
154 adjust_simduid_builtins (hash_table
<simduid_to_vf
> *htab
)
158 FOR_EACH_BB_FN (bb
, cfun
)
160 gimple_stmt_iterator i
;
162 for (i
= gsi_start_bb (bb
); !gsi_end_p (i
); )
165 enum internal_fn ifn
;
166 gimple
*stmt
= gsi_stmt (i
);
168 if (!is_gimple_call (stmt
)
169 || !gimple_call_internal_p (stmt
))
174 ifn
= gimple_call_internal_fn (stmt
);
177 case IFN_GOMP_SIMD_LANE
:
178 case IFN_GOMP_SIMD_VF
:
179 case IFN_GOMP_SIMD_LAST_LANE
:
181 case IFN_GOMP_SIMD_ORDERED_START
:
182 case IFN_GOMP_SIMD_ORDERED_END
:
183 if (integer_onep (gimple_call_arg (stmt
, 0)))
185 enum built_in_function bcode
186 = (ifn
== IFN_GOMP_SIMD_ORDERED_START
187 ? BUILT_IN_GOMP_ORDERED_START
188 : BUILT_IN_GOMP_ORDERED_END
);
190 = gimple_build_call (builtin_decl_explicit (bcode
), 0);
191 tree vdef
= gimple_vdef (stmt
);
192 gimple_set_vdef (g
, vdef
);
193 SSA_NAME_DEF_STMT (vdef
) = g
;
194 gimple_set_vuse (g
, gimple_vuse (stmt
));
195 gsi_replace (&i
, g
, true);
198 gsi_remove (&i
, true);
199 unlink_stmt_vdef (stmt
);
205 tree arg
= gimple_call_arg (stmt
, 0);
206 gcc_assert (arg
!= NULL_TREE
);
207 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
208 simduid_to_vf
*p
= NULL
, data
;
209 data
.simduid
= DECL_UID (SSA_NAME_VAR (arg
));
210 /* Need to nullify loop safelen field since it's value is not
211 valid after transformation. */
212 if (bb
->loop_father
&& bb
->loop_father
->safelen
> 0)
213 bb
->loop_father
->safelen
= 0;
216 p
= htab
->find (&data
);
222 case IFN_GOMP_SIMD_VF
:
223 t
= build_int_cst (unsigned_type_node
, vf
);
225 case IFN_GOMP_SIMD_LANE
:
226 t
= build_int_cst (unsigned_type_node
, 0);
228 case IFN_GOMP_SIMD_LAST_LANE
:
229 t
= gimple_call_arg (stmt
, 1);
234 tree lhs
= gimple_call_lhs (stmt
);
236 replace_uses_by (lhs
, t
);
238 gsi_remove (&i
, true);
243 /* Helper structure for note_simd_array_uses. */
245 struct note_simd_array_uses_struct
247 hash_table
<simd_array_to_simduid
> **htab
;
248 unsigned int simduid
;
251 /* Callback for note_simd_array_uses, called through walk_gimple_op. */
254 note_simd_array_uses_cb (tree
*tp
, int *walk_subtrees
, void *data
)
256 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
257 struct note_simd_array_uses_struct
*ns
258 = (struct note_simd_array_uses_struct
*) wi
->info
;
263 && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp
))
264 && DECL_CONTEXT (*tp
) == current_function_decl
)
266 simd_array_to_simduid data
;
268 *ns
->htab
= new hash_table
<simd_array_to_simduid
> (15);
270 data
.simduid
= ns
->simduid
;
271 simd_array_to_simduid
**slot
= (*ns
->htab
)->find_slot (&data
, INSERT
);
274 simd_array_to_simduid
*p
= XNEW (simd_array_to_simduid
);
278 else if ((*slot
)->simduid
!= ns
->simduid
)
279 (*slot
)->simduid
= -1U;
285 /* Find "omp simd array" temporaries and map them to corresponding
289 note_simd_array_uses (hash_table
<simd_array_to_simduid
> **htab
)
292 gimple_stmt_iterator gsi
;
293 struct walk_stmt_info wi
;
294 struct note_simd_array_uses_struct ns
;
296 memset (&wi
, 0, sizeof (wi
));
300 FOR_EACH_BB_FN (bb
, cfun
)
301 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
303 gimple
*stmt
= gsi_stmt (gsi
);
304 if (!is_gimple_call (stmt
) || !gimple_call_internal_p (stmt
))
306 switch (gimple_call_internal_fn (stmt
))
308 case IFN_GOMP_SIMD_LANE
:
309 case IFN_GOMP_SIMD_VF
:
310 case IFN_GOMP_SIMD_LAST_LANE
:
315 tree lhs
= gimple_call_lhs (stmt
);
316 if (lhs
== NULL_TREE
)
318 imm_use_iterator use_iter
;
320 ns
.simduid
= DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt
, 0)));
321 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, lhs
)
322 if (!is_gimple_debug (use_stmt
))
323 walk_gimple_op (use_stmt
, note_simd_array_uses_cb
, &wi
);
327 /* Shrink arrays with "omp simd array" attribute to the corresponding
328 vectorization factor. */
332 (hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
,
333 hash_table
<simduid_to_vf
> *simduid_to_vf_htab
)
335 for (hash_table
<simd_array_to_simduid
>::iterator iter
336 = simd_array_to_simduid_htab
->begin ();
337 iter
!= simd_array_to_simduid_htab
->end (); ++iter
)
338 if ((*iter
)->simduid
!= -1U)
340 tree decl
= (*iter
)->decl
;
342 if (simduid_to_vf_htab
)
344 simduid_to_vf
*p
= NULL
, data
;
345 data
.simduid
= (*iter
)->simduid
;
346 p
= simduid_to_vf_htab
->find (&data
);
351 = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl
)), vf
);
352 TREE_TYPE (decl
) = atype
;
353 relayout_decl (decl
);
356 delete simd_array_to_simduid_htab
;
359 /* Initialize the vec_info with kind KIND_IN and target cost data
360 TARGET_COST_DATA_IN. */
362 vec_info::vec_info (vec_info::vec_kind kind_in
, void *target_cost_data_in
)
366 target_cost_data (target_cost_data_in
)
370 vec_info::~vec_info ()
372 slp_instance instance
;
373 struct data_reference
*dr
;
376 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
383 FOR_EACH_VEC_ELT (slp_instances
, i
, instance
)
384 vect_free_slp_instance (instance
);
386 free_data_refs (datarefs
);
387 free_dependence_relations (ddrs
);
388 destroy_cost_data (target_cost_data
);
391 /* A helper function to free scev and LOOP niter information, as well as
392 clear loop constraint LOOP_C_FINITE. */
395 vect_free_loop_info_assumptions (struct loop
*loop
)
398 /* We need to explicitly reset upper bound information since they are
399 used even after free_numbers_of_iterations_estimates. */
400 loop
->any_upper_bound
= false;
401 loop
->any_likely_upper_bound
= false;
402 free_numbers_of_iterations_estimates (loop
);
403 loop_constraint_clear (loop
, LOOP_C_FINITE
);
406 /* Return whether STMT is inside the region we try to vectorize. */
409 vect_stmt_in_region_p (vec_info
*vinfo
, gimple
*stmt
)
411 if (!gimple_bb (stmt
))
414 if (loop_vec_info loop_vinfo
= dyn_cast
<loop_vec_info
> (vinfo
))
416 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
417 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
422 bb_vec_info bb_vinfo
= as_a
<bb_vec_info
> (vinfo
);
423 if (gimple_bb (stmt
) != BB_VINFO_BB (bb_vinfo
)
424 || gimple_uid (stmt
) == -1U
425 || gimple_code (stmt
) == GIMPLE_PHI
)
433 /* If LOOP has been versioned during ifcvt, return the internal call
437 vect_loop_vectorized_call (struct loop
*loop
)
439 basic_block bb
= loop_preheader_edge (loop
)->src
;
446 if (!single_pred_p (bb
))
448 bb
= single_pred (bb
);
451 if (g
&& gimple_code (g
) == GIMPLE_COND
)
453 gimple_stmt_iterator gsi
= gsi_for_stmt (g
);
455 if (!gsi_end_p (gsi
))
458 if (gimple_call_internal_p (g
, IFN_LOOP_VECTORIZED
)
459 && (tree_to_shwi (gimple_call_arg (g
, 0)) == loop
->num
460 || tree_to_shwi (gimple_call_arg (g
, 1)) == loop
->num
))
467 /* If LOOP has been versioned during loop distribution, return the gurading
471 vect_loop_dist_alias_call (struct loop
*loop
)
475 struct loop
*outer
, *orig
;
476 gimple_stmt_iterator gsi
;
479 if (loop
->orig_loop_num
== 0)
482 orig
= get_loop (cfun
, loop
->orig_loop_num
);
485 /* The original loop is somehow destroyed. Clear the information. */
486 loop
->orig_loop_num
= 0;
491 bb
= nearest_common_dominator (CDI_DOMINATORS
, loop
->header
, orig
->header
);
493 bb
= loop_preheader_edge (loop
)->src
;
495 outer
= bb
->loop_father
;
496 entry
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
498 /* Look upward in dominance tree. */
499 for (; bb
!= entry
&& flow_bb_inside_loop_p (outer
, bb
);
500 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
503 if (g
== NULL
|| gimple_code (g
) != GIMPLE_COND
)
506 gsi
= gsi_for_stmt (g
);
512 /* The guarding internal function call must have the same distribution
514 if (gimple_call_internal_p (g
, IFN_LOOP_DIST_ALIAS
)
515 && (tree_to_shwi (gimple_call_arg (g
, 0)) == loop
->orig_loop_num
))
521 /* Set the uids of all the statements in basic blocks inside loop
522 represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal
523 call guarding the loop which has been if converted. */
525 set_uid_loop_bbs (loop_vec_info loop_vinfo
, gimple
*loop_vectorized_call
)
527 tree arg
= gimple_call_arg (loop_vectorized_call
, 1);
530 struct loop
*scalar_loop
= get_loop (cfun
, tree_to_shwi (arg
));
532 LOOP_VINFO_SCALAR_LOOP (loop_vinfo
) = scalar_loop
;
533 gcc_checking_assert (vect_loop_vectorized_call (scalar_loop
)
534 == loop_vectorized_call
);
535 /* If we are going to vectorize outer loop, prevent vectorization
536 of the inner loop in the scalar loop - either the scalar loop is
537 thrown away, so it is a wasted work, or is used only for
539 if (scalar_loop
->inner
)
541 gimple
*g
= vect_loop_vectorized_call (scalar_loop
->inner
);
544 arg
= gimple_call_arg (g
, 0);
545 get_loop (cfun
, tree_to_shwi (arg
))->dont_vectorize
= true;
546 fold_loop_internal_call (g
, boolean_false_node
);
549 bbs
= get_loop_body (scalar_loop
);
550 for (i
= 0; i
< scalar_loop
->num_nodes
; i
++)
552 basic_block bb
= bbs
[i
];
553 gimple_stmt_iterator gsi
;
554 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
556 gimple
*phi
= gsi_stmt (gsi
);
557 gimple_set_uid (phi
, 0);
559 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
561 gimple
*stmt
= gsi_stmt (gsi
);
562 gimple_set_uid (stmt
, 0);
568 /* Function vectorize_loops.
570 Entry point to loop vectorization phase. */
573 vectorize_loops (void)
576 unsigned int num_vectorized_loops
= 0;
577 unsigned int vect_loops_num
;
579 hash_table
<simduid_to_vf
> *simduid_to_vf_htab
= NULL
;
580 hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
= NULL
;
581 bool any_ifcvt_loops
= false;
583 struct loop
*new_loop
;
585 vect_loops_num
= number_of_loops (cfun
);
587 /* Bail out if there are no loops. */
588 if (vect_loops_num
<= 1)
591 if (cfun
->has_simduid_loops
)
592 note_simd_array_uses (&simd_array_to_simduid_htab
);
594 init_stmt_vec_info_vec ();
596 /* ----------- Analyze loops. ----------- */
598 /* If some loop was duplicated, it gets bigger number
599 than all previously defined loops. This fact allows us to run
600 only over initial loops skipping newly generated ones. */
601 FOR_EACH_LOOP (loop
, 0)
602 if (loop
->dont_vectorize
)
604 any_ifcvt_loops
= true;
605 /* If-conversion sometimes versions both the outer loop
606 (for the case when outer loop vectorization might be
607 desirable) as well as the inner loop in the scalar version
608 of the loop. So we have:
609 if (LOOP_VECTORIZED (1, 3))
615 loop3 (copy of loop1)
616 if (LOOP_VECTORIZED (4, 5))
617 loop4 (copy of loop2)
619 loop5 (copy of loop4)
620 If FOR_EACH_LOOP gives us loop3 first (which has
621 dont_vectorize set), make sure to process loop1 before loop4;
622 so that we can prevent vectorization of loop4 if loop1
623 is successfully vectorized. */
626 gimple
*loop_vectorized_call
627 = vect_loop_vectorized_call (loop
);
628 if (loop_vectorized_call
629 && vect_loop_vectorized_call (loop
->inner
))
631 tree arg
= gimple_call_arg (loop_vectorized_call
, 0);
632 struct loop
*vector_loop
633 = get_loop (cfun
, tree_to_shwi (arg
));
634 if (vector_loop
&& vector_loop
!= loop
)
637 /* Make sure we don't vectorize it twice. */
638 loop
->dont_vectorize
= true;
646 loop_vec_info loop_vinfo
, orig_loop_vinfo
;
647 gimple
*loop_vectorized_call
, *loop_dist_alias_call
;
649 if (!((flag_tree_loop_vectorize
650 && optimize_loop_nest_for_speed_p (loop
))
651 || loop
->force_vectorize
))
653 orig_loop_vinfo
= NULL
;
654 loop_vectorized_call
= vect_loop_vectorized_call (loop
);
655 loop_dist_alias_call
= vect_loop_dist_alias_call (loop
);
657 vect_location
= find_loop_location (loop
);
658 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOCATION
659 && dump_enabled_p ())
660 dump_printf (MSG_NOTE
, "\nAnalyzing loop at %s:%d\n",
661 LOCATION_FILE (vect_location
),
662 LOCATION_LINE (vect_location
));
664 loop_vinfo
= vect_analyze_loop (loop
, orig_loop_vinfo
);
665 loop
->aux
= loop_vinfo
;
667 if (!loop_vinfo
|| !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
))
669 /* Free existing information if loop is analyzed with some
671 if (loop_constraint_set_p (loop
, LOOP_C_FINITE
))
672 vect_free_loop_info_assumptions (loop
);
674 /* If we applied if-conversion then try to vectorize the
675 BB of innermost loops.
676 ??? Ideally BB vectorization would learn to vectorize
677 control flow by applying if-conversion on-the-fly, the
678 following retains the if-converted loop body even when
679 only non-if-converted parts took part in BB vectorization. */
680 if (flag_tree_slp_vectorize
!= 0
681 && loop_vectorized_call
684 basic_block bb
= loop
->header
;
685 bool has_mask_load_store
= false;
686 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
687 !gsi_end_p (gsi
); gsi_next (&gsi
))
689 gimple
*stmt
= gsi_stmt (gsi
);
690 if (is_gimple_call (stmt
)
691 && gimple_call_internal_p (stmt
)
692 && (gimple_call_internal_fn (stmt
) == IFN_MASK_LOAD
693 || gimple_call_internal_fn (stmt
) == IFN_MASK_STORE
))
695 has_mask_load_store
= true;
698 gimple_set_uid (stmt
, -1);
699 gimple_set_visited (stmt
, false);
701 if (! has_mask_load_store
&& vect_slp_bb (bb
))
703 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
704 "basic block vectorized\n");
705 fold_loop_internal_call (loop_vectorized_call
,
707 loop_vectorized_call
= NULL
;
708 ret
|= TODO_cleanup_cfg
;
711 /* If outer loop vectorization fails for LOOP_VECTORIZED guarded
712 loop, don't vectorize its inner loop; we'll attempt to
713 vectorize LOOP_VECTORIZED guarded inner loop of the scalar
715 if (loop_vectorized_call
&& loop
->inner
)
716 loop
->inner
->dont_vectorize
= true;
720 if (!dbg_cnt (vect_loop
))
722 /* We may miss some if-converted loops due to
723 debug counter. Set any_ifcvt_loops to visit
724 them at finalization. */
725 any_ifcvt_loops
= true;
726 /* Free existing information if loop is analyzed with some
728 if (loop_constraint_set_p (loop
, LOOP_C_FINITE
))
729 vect_free_loop_info_assumptions (loop
);
734 if (loop_vectorized_call
)
735 set_uid_loop_bbs (loop_vinfo
, loop_vectorized_call
);
736 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOCATION
737 && dump_enabled_p ())
738 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
739 "loop vectorized\n");
740 new_loop
= vect_transform_loop (loop_vinfo
);
741 num_vectorized_loops
++;
742 /* Now that the loop has been vectorized, allow it to be unrolled
744 loop
->force_vectorize
= false;
748 simduid_to_vf
*simduid_to_vf_data
= XNEW (simduid_to_vf
);
749 if (!simduid_to_vf_htab
)
750 simduid_to_vf_htab
= new hash_table
<simduid_to_vf
> (15);
751 simduid_to_vf_data
->simduid
= DECL_UID (loop
->simduid
);
752 simduid_to_vf_data
->vf
= loop_vinfo
->vectorization_factor
;
753 *simduid_to_vf_htab
->find_slot (simduid_to_vf_data
, INSERT
)
754 = simduid_to_vf_data
;
757 if (loop_vectorized_call
)
759 fold_loop_internal_call (loop_vectorized_call
, boolean_true_node
);
760 loop_vectorized_call
= NULL
;
761 ret
|= TODO_cleanup_cfg
;
763 if (loop_dist_alias_call
)
765 tree value
= gimple_call_arg (loop_dist_alias_call
, 1);
766 fold_loop_internal_call (loop_dist_alias_call
, value
);
767 loop_dist_alias_call
= NULL
;
768 ret
|= TODO_cleanup_cfg
;
773 /* Epilogue of vectorized loop must be vectorized too. */
774 vect_loops_num
= number_of_loops (cfun
);
776 orig_loop_vinfo
= loop_vinfo
; /* To pass vect_analyze_loop. */
777 goto vectorize_epilogue
;
781 vect_location
= UNKNOWN_LOCATION
;
783 statistics_counter_event (cfun
, "Vectorized loops", num_vectorized_loops
);
784 if (dump_enabled_p ()
785 || (num_vectorized_loops
> 0 && dump_enabled_p ()))
786 dump_printf_loc (MSG_NOTE
, vect_location
,
787 "vectorized %u loops in function.\n",
788 num_vectorized_loops
);
790 /* ----------- Finalize. ----------- */
793 for (i
= 1; i
< vect_loops_num
; i
++)
795 loop
= get_loop (cfun
, i
);
796 if (loop
&& loop
->dont_vectorize
)
798 gimple
*g
= vect_loop_vectorized_call (loop
);
801 fold_loop_internal_call (g
, boolean_false_node
);
802 ret
|= TODO_cleanup_cfg
;
806 g
= vect_loop_dist_alias_call (loop
);
810 fold_loop_internal_call (g
, boolean_false_node
);
811 ret
|= TODO_cleanup_cfg
;
816 for (i
= 1; i
< vect_loops_num
; i
++)
818 loop_vec_info loop_vinfo
;
821 loop
= get_loop (cfun
, i
);
824 loop_vinfo
= (loop_vec_info
) loop
->aux
;
825 has_mask_store
= false;
827 has_mask_store
= LOOP_VINFO_HAS_MASK_STORE (loop_vinfo
);
830 optimize_mask_stores (loop
);
834 free_stmt_vec_info_vec ();
836 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
837 if (cfun
->has_simduid_loops
)
838 adjust_simduid_builtins (simduid_to_vf_htab
);
840 /* Shrink any "omp array simd" temporary arrays to the
841 actual vectorization factors. */
842 if (simd_array_to_simduid_htab
)
843 shrink_simd_arrays (simd_array_to_simduid_htab
, simduid_to_vf_htab
);
844 delete simduid_to_vf_htab
;
845 cfun
->has_simduid_loops
= false;
847 if (num_vectorized_loops
> 0)
849 /* If we vectorized any loop only virtual SSA form needs to be updated.
850 ??? Also while we try hard to update loop-closed SSA form we fail
851 to properly do this in some corner-cases (see PR56286). */
852 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa_only_virtuals
);
853 return TODO_cleanup_cfg
;
860 /* Entry point to the simduid cleanup pass. */
864 const pass_data pass_data_simduid_cleanup
=
866 GIMPLE_PASS
, /* type */
867 "simduid", /* name */
868 OPTGROUP_NONE
, /* optinfo_flags */
870 ( PROP_ssa
| PROP_cfg
), /* properties_required */
871 0, /* properties_provided */
872 0, /* properties_destroyed */
873 0, /* todo_flags_start */
874 0, /* todo_flags_finish */
877 class pass_simduid_cleanup
: public gimple_opt_pass
880 pass_simduid_cleanup (gcc::context
*ctxt
)
881 : gimple_opt_pass (pass_data_simduid_cleanup
, ctxt
)
884 /* opt_pass methods: */
885 opt_pass
* clone () { return new pass_simduid_cleanup (m_ctxt
); }
886 virtual bool gate (function
*fun
) { return fun
->has_simduid_loops
; }
887 virtual unsigned int execute (function
*);
889 }; // class pass_simduid_cleanup
892 pass_simduid_cleanup::execute (function
*fun
)
894 hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
= NULL
;
896 note_simd_array_uses (&simd_array_to_simduid_htab
);
898 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
899 adjust_simduid_builtins (NULL
);
901 /* Shrink any "omp array simd" temporary arrays to the
902 actual vectorization factors. */
903 if (simd_array_to_simduid_htab
)
904 shrink_simd_arrays (simd_array_to_simduid_htab
, NULL
);
905 fun
->has_simduid_loops
= false;
912 make_pass_simduid_cleanup (gcc::context
*ctxt
)
914 return new pass_simduid_cleanup (ctxt
);
918 /* Entry point to basic block SLP phase. */
922 const pass_data pass_data_slp_vectorize
=
924 GIMPLE_PASS
, /* type */
926 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
927 TV_TREE_SLP_VECTORIZATION
, /* tv_id */
928 ( PROP_ssa
| PROP_cfg
), /* properties_required */
929 0, /* properties_provided */
930 0, /* properties_destroyed */
931 0, /* todo_flags_start */
932 TODO_update_ssa
, /* todo_flags_finish */
935 class pass_slp_vectorize
: public gimple_opt_pass
938 pass_slp_vectorize (gcc::context
*ctxt
)
939 : gimple_opt_pass (pass_data_slp_vectorize
, ctxt
)
942 /* opt_pass methods: */
943 opt_pass
* clone () { return new pass_slp_vectorize (m_ctxt
); }
944 virtual bool gate (function
*) { return flag_tree_slp_vectorize
!= 0; }
945 virtual unsigned int execute (function
*);
947 }; // class pass_slp_vectorize
950 pass_slp_vectorize::execute (function
*fun
)
954 bool in_loop_pipeline
= scev_initialized_p ();
955 if (!in_loop_pipeline
)
957 loop_optimizer_init (LOOPS_NORMAL
);
961 /* Mark all stmts as not belonging to the current region and unvisited. */
962 FOR_EACH_BB_FN (bb
, fun
)
964 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
967 gimple
*stmt
= gsi_stmt (gsi
);
968 gimple_set_uid (stmt
, -1);
969 gimple_set_visited (stmt
, false);
973 init_stmt_vec_info_vec ();
975 FOR_EACH_BB_FN (bb
, fun
)
977 if (vect_slp_bb (bb
))
978 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
979 "basic block vectorized\n");
982 free_stmt_vec_info_vec ();
984 if (!in_loop_pipeline
)
987 loop_optimizer_finalize ();
996 make_pass_slp_vectorize (gcc::context
*ctxt
)
998 return new pass_slp_vectorize (ctxt
);
1002 /* Increase alignment of global arrays to improve vectorization potential.
1004 - Consider also structs that have an array field.
1005 - Use ipa analysis to prune arrays that can't be vectorized?
1006 This should involve global alignment analysis and in the future also
1009 static unsigned get_vec_alignment_for_type (tree
);
1010 static hash_map
<tree
, unsigned> *type_align_map
;
1012 /* Return alignment of array's vector type corresponding to scalar type.
1013 0 if no vector type exists. */
1015 get_vec_alignment_for_array_type (tree type
)
1017 gcc_assert (TREE_CODE (type
) == ARRAY_TYPE
);
1018 poly_uint64 array_size
, vector_size
;
1020 tree vectype
= get_vectype_for_scalar_type (strip_array_types (type
));
1022 || !poly_int_tree_p (TYPE_SIZE (type
), &array_size
)
1023 || !poly_int_tree_p (TYPE_SIZE (vectype
), &vector_size
)
1024 || maybe_lt (array_size
, vector_size
))
1027 return TYPE_ALIGN (vectype
);
1030 /* Return alignment of field having maximum alignment of vector type
1031 corresponding to it's scalar type. For now, we only consider fields whose
1032 offset is a multiple of it's vector alignment.
1033 0 if no suitable field is found. */
1035 get_vec_alignment_for_record_type (tree type
)
1037 gcc_assert (TREE_CODE (type
) == RECORD_TYPE
);
1039 unsigned max_align
= 0, alignment
;
1040 HOST_WIDE_INT offset
;
1043 if (TYPE_PACKED (type
))
1046 unsigned *slot
= type_align_map
->get (type
);
1050 for (tree field
= first_field (type
);
1052 field
= DECL_CHAIN (field
))
1054 /* Skip if not FIELD_DECL or if alignment is set by user. */
1055 if (TREE_CODE (field
) != FIELD_DECL
1056 || DECL_USER_ALIGN (field
)
1057 || DECL_ARTIFICIAL (field
))
1060 /* We don't need to process the type further if offset is variable,
1061 since the offsets of remaining members will also be variable. */
1062 if (TREE_CODE (DECL_FIELD_OFFSET (field
)) != INTEGER_CST
1063 || TREE_CODE (DECL_FIELD_BIT_OFFSET (field
)) != INTEGER_CST
)
1066 /* Similarly stop processing the type if offset_tree
1067 does not fit in unsigned HOST_WIDE_INT. */
1068 offset_tree
= bit_position (field
);
1069 if (!tree_fits_uhwi_p (offset_tree
))
1072 offset
= tree_to_uhwi (offset_tree
);
1073 alignment
= get_vec_alignment_for_type (TREE_TYPE (field
));
1075 /* Get maximum alignment of vectorized field/array among those members
1076 whose offset is multiple of the vector alignment. */
1078 && (offset
% alignment
== 0)
1079 && (alignment
> max_align
))
1080 max_align
= alignment
;
1083 type_align_map
->put (type
, max_align
);
1087 /* Return alignment of vector type corresponding to decl's scalar type
1088 or 0 if it doesn't exist or the vector alignment is lesser than
1089 decl's alignment. */
1091 get_vec_alignment_for_type (tree type
)
1093 if (type
== NULL_TREE
)
1096 gcc_assert (TYPE_P (type
));
1098 static unsigned alignment
= 0;
1099 switch (TREE_CODE (type
))
1102 alignment
= get_vec_alignment_for_array_type (type
);
1105 alignment
= get_vec_alignment_for_record_type (type
);
1112 return (alignment
> TYPE_ALIGN (type
)) ? alignment
: 0;
1115 /* Entry point to increase_alignment pass. */
1117 increase_alignment (void)
1119 varpool_node
*vnode
;
1121 vect_location
= UNKNOWN_LOCATION
;
1122 type_align_map
= new hash_map
<tree
, unsigned>;
1124 /* Increase the alignment of all global arrays for vectorization. */
1125 FOR_EACH_DEFINED_VARIABLE (vnode
)
1127 tree decl
= vnode
->decl
;
1128 unsigned int alignment
;
1130 if ((decl_in_symtab_p (decl
)
1131 && !symtab_node::get (decl
)->can_increase_alignment_p ())
1132 || DECL_USER_ALIGN (decl
) || DECL_ARTIFICIAL (decl
))
1135 alignment
= get_vec_alignment_for_type (TREE_TYPE (decl
));
1136 if (alignment
&& vect_can_force_dr_alignment_p (decl
, alignment
))
1138 vnode
->increase_alignment (alignment
);
1139 dump_printf (MSG_NOTE
, "Increasing alignment of decl: ");
1140 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, decl
);
1141 dump_printf (MSG_NOTE
, "\n");
1145 delete type_align_map
;
1152 const pass_data pass_data_ipa_increase_alignment
=
1154 SIMPLE_IPA_PASS
, /* type */
1155 "increase_alignment", /* name */
1156 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
1157 TV_IPA_OPT
, /* tv_id */
1158 0, /* properties_required */
1159 0, /* properties_provided */
1160 0, /* properties_destroyed */
1161 0, /* todo_flags_start */
1162 0, /* todo_flags_finish */
1165 class pass_ipa_increase_alignment
: public simple_ipa_opt_pass
1168 pass_ipa_increase_alignment (gcc::context
*ctxt
)
1169 : simple_ipa_opt_pass (pass_data_ipa_increase_alignment
, ctxt
)
1172 /* opt_pass methods: */
1173 virtual bool gate (function
*)
1175 return flag_section_anchors
&& flag_tree_loop_vectorize
;
1178 virtual unsigned int execute (function
*) { return increase_alignment (); }
1180 }; // class pass_ipa_increase_alignment
1184 simple_ipa_opt_pass
*
1185 make_pass_ipa_increase_alignment (gcc::context
*ctxt
)
1187 return new pass_ipa_increase_alignment (ctxt
);