2 Copyright (C) 2003-2015 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"
65 #include "fold-const.h"
66 #include "stor-layout.h"
67 #include "tree-pretty-print.h"
69 #include "hard-reg-set.h"
71 #include "dominance.h"
73 #include "basic-block.h"
74 #include "tree-ssa-alias.h"
75 #include "internal-fn.h"
76 #include "gimple-expr.h"
78 #include "gimple-iterator.h"
79 #include "gimple-walk.h"
80 #include "gimple-ssa.h"
81 #include "plugin-api.h"
84 #include "tree-phinodes.h"
85 #include "ssa-iterators.h"
86 #include "tree-ssa-loop-manip.h"
89 #include "tree-vectorizer.h"
90 #include "tree-pass.h"
91 #include "tree-ssa-propagate.h"
93 #include "gimple-fold.h"
94 #include "tree-scalar-evolution.h"
97 /* Loop or bb location. */
98 source_location vect_location
;
100 /* Vector mapping GIMPLE stmt to stmt_vec_info. */
101 vec
<vec_void_p
> stmt_vec_info_vec
;
103 /* For mapping simduid to vectorization factor. */
105 struct simduid_to_vf
: free_ptr_hash
<simduid_to_vf
>
107 unsigned int simduid
;
110 /* hash_table support. */
111 static inline hashval_t
hash (const simduid_to_vf
*);
112 static inline int equal (const simduid_to_vf
*, const simduid_to_vf
*);
116 simduid_to_vf::hash (const simduid_to_vf
*p
)
122 simduid_to_vf::equal (const simduid_to_vf
*p1
, const simduid_to_vf
*p2
)
124 return p1
->simduid
== p2
->simduid
;
127 /* This hash maps the OMP simd array to the corresponding simduid used
128 to index into it. Like thus,
130 _7 = GOMP_SIMD_LANE (simduid.0)
136 This hash maps from the OMP simd array (D.1737[]) to DECL_UID of
139 struct simd_array_to_simduid
: free_ptr_hash
<simd_array_to_simduid
>
142 unsigned int simduid
;
144 /* hash_table support. */
145 static inline hashval_t
hash (const simd_array_to_simduid
*);
146 static inline int equal (const simd_array_to_simduid
*,
147 const simd_array_to_simduid
*);
151 simd_array_to_simduid::hash (const simd_array_to_simduid
*p
)
153 return DECL_UID (p
->decl
);
157 simd_array_to_simduid::equal (const simd_array_to_simduid
*p1
,
158 const simd_array_to_simduid
*p2
)
160 return p1
->decl
== p2
->decl
;
163 /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF and IFN_GOMP_SIMD_LAST_LANE
164 into their corresponding constants. */
167 adjust_simduid_builtins (hash_table
<simduid_to_vf
> *htab
)
171 FOR_EACH_BB_FN (bb
, cfun
)
173 gimple_stmt_iterator i
;
175 for (i
= gsi_start_bb (bb
); !gsi_end_p (i
); gsi_next (&i
))
178 enum internal_fn ifn
;
179 gimple stmt
= gsi_stmt (i
);
181 if (!is_gimple_call (stmt
)
182 || !gimple_call_internal_p (stmt
))
184 ifn
= gimple_call_internal_fn (stmt
);
187 case IFN_GOMP_SIMD_LANE
:
188 case IFN_GOMP_SIMD_VF
:
189 case IFN_GOMP_SIMD_LAST_LANE
:
194 tree arg
= gimple_call_arg (stmt
, 0);
195 gcc_assert (arg
!= NULL_TREE
);
196 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
197 simduid_to_vf
*p
= NULL
, data
;
198 data
.simduid
= DECL_UID (SSA_NAME_VAR (arg
));
201 p
= htab
->find (&data
);
207 case IFN_GOMP_SIMD_VF
:
208 t
= build_int_cst (unsigned_type_node
, vf
);
210 case IFN_GOMP_SIMD_LANE
:
211 t
= build_int_cst (unsigned_type_node
, 0);
213 case IFN_GOMP_SIMD_LAST_LANE
:
214 t
= gimple_call_arg (stmt
, 1);
219 update_call_from_tree (&i
, t
);
224 /* Helper structure for note_simd_array_uses. */
226 struct note_simd_array_uses_struct
228 hash_table
<simd_array_to_simduid
> **htab
;
229 unsigned int simduid
;
232 /* Callback for note_simd_array_uses, called through walk_gimple_op. */
235 note_simd_array_uses_cb (tree
*tp
, int *walk_subtrees
, void *data
)
237 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
238 struct note_simd_array_uses_struct
*ns
239 = (struct note_simd_array_uses_struct
*) wi
->info
;
244 && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp
))
245 && DECL_CONTEXT (*tp
) == current_function_decl
)
247 simd_array_to_simduid data
;
249 *ns
->htab
= new hash_table
<simd_array_to_simduid
> (15);
251 data
.simduid
= ns
->simduid
;
252 simd_array_to_simduid
**slot
= (*ns
->htab
)->find_slot (&data
, INSERT
);
255 simd_array_to_simduid
*p
= XNEW (simd_array_to_simduid
);
259 else if ((*slot
)->simduid
!= ns
->simduid
)
260 (*slot
)->simduid
= -1U;
266 /* Find "omp simd array" temporaries and map them to corresponding
270 note_simd_array_uses (hash_table
<simd_array_to_simduid
> **htab
)
273 gimple_stmt_iterator gsi
;
274 struct walk_stmt_info wi
;
275 struct note_simd_array_uses_struct ns
;
277 memset (&wi
, 0, sizeof (wi
));
281 FOR_EACH_BB_FN (bb
, cfun
)
282 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
284 gimple stmt
= gsi_stmt (gsi
);
285 if (!is_gimple_call (stmt
) || !gimple_call_internal_p (stmt
))
287 switch (gimple_call_internal_fn (stmt
))
289 case IFN_GOMP_SIMD_LANE
:
290 case IFN_GOMP_SIMD_VF
:
291 case IFN_GOMP_SIMD_LAST_LANE
:
296 tree lhs
= gimple_call_lhs (stmt
);
297 if (lhs
== NULL_TREE
)
299 imm_use_iterator use_iter
;
301 ns
.simduid
= DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt
, 0)));
302 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, lhs
)
303 if (!is_gimple_debug (use_stmt
))
304 walk_gimple_op (use_stmt
, note_simd_array_uses_cb
, &wi
);
308 /* Shrink arrays with "omp simd array" attribute to the corresponding
309 vectorization factor. */
313 (hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
,
314 hash_table
<simduid_to_vf
> *simduid_to_vf_htab
)
316 for (hash_table
<simd_array_to_simduid
>::iterator iter
317 = simd_array_to_simduid_htab
->begin ();
318 iter
!= simd_array_to_simduid_htab
->end (); ++iter
)
319 if ((*iter
)->simduid
!= -1U)
321 tree decl
= (*iter
)->decl
;
323 if (simduid_to_vf_htab
)
325 simduid_to_vf
*p
= NULL
, data
;
326 data
.simduid
= (*iter
)->simduid
;
327 p
= simduid_to_vf_htab
->find (&data
);
332 = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl
)), vf
);
333 TREE_TYPE (decl
) = atype
;
334 relayout_decl (decl
);
337 delete simd_array_to_simduid_htab
;
340 /* A helper function to free data refs. */
343 vect_destroy_datarefs (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
)
345 vec
<data_reference_p
> datarefs
;
346 struct data_reference
*dr
;
350 datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
352 datarefs
= BB_VINFO_DATAREFS (bb_vinfo
);
354 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
361 free_data_refs (datarefs
);
365 /* If LOOP has been versioned during ifcvt, return the internal call
369 vect_loop_vectorized_call (struct loop
*loop
)
371 basic_block bb
= loop_preheader_edge (loop
)->src
;
378 if (!single_pred_p (bb
))
380 bb
= single_pred (bb
);
383 if (g
&& gimple_code (g
) == GIMPLE_COND
)
385 gimple_stmt_iterator gsi
= gsi_for_stmt (g
);
387 if (!gsi_end_p (gsi
))
390 if (is_gimple_call (g
)
391 && gimple_call_internal_p (g
)
392 && gimple_call_internal_fn (g
) == IFN_LOOP_VECTORIZED
393 && (tree_to_shwi (gimple_call_arg (g
, 0)) == loop
->num
394 || tree_to_shwi (gimple_call_arg (g
, 1)) == loop
->num
))
401 /* Fold LOOP_VECTORIZED internal call G to VALUE and
402 update any immediate uses of it's LHS. */
405 fold_loop_vectorized_call (gimple g
, tree value
)
407 tree lhs
= gimple_call_lhs (g
);
409 imm_use_iterator iter
;
411 gimple_stmt_iterator gsi
= gsi_for_stmt (g
);
413 update_call_from_tree (&gsi
, value
);
414 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
416 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
417 SET_USE (use_p
, value
);
418 update_stmt (use_stmt
);
421 /* Set the uids of all the statements in basic blocks inside loop
422 represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal
423 call guarding the loop which has been if converted. */
425 set_uid_loop_bbs (loop_vec_info loop_vinfo
, gimple loop_vectorized_call
)
427 tree arg
= gimple_call_arg (loop_vectorized_call
, 1);
430 struct loop
*scalar_loop
= get_loop (cfun
, tree_to_shwi (arg
));
432 LOOP_VINFO_SCALAR_LOOP (loop_vinfo
) = scalar_loop
;
433 gcc_checking_assert (vect_loop_vectorized_call
434 (LOOP_VINFO_SCALAR_LOOP (loop_vinfo
))
435 == loop_vectorized_call
);
436 bbs
= get_loop_body (scalar_loop
);
437 for (i
= 0; i
< scalar_loop
->num_nodes
; i
++)
439 basic_block bb
= bbs
[i
];
440 gimple_stmt_iterator gsi
;
441 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
443 gimple phi
= gsi_stmt (gsi
);
444 gimple_set_uid (phi
, 0);
446 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
448 gimple stmt
= gsi_stmt (gsi
);
449 gimple_set_uid (stmt
, 0);
455 /* Function vectorize_loops.
457 Entry point to loop vectorization phase. */
460 vectorize_loops (void)
463 unsigned int num_vectorized_loops
= 0;
464 unsigned int vect_loops_num
;
466 hash_table
<simduid_to_vf
> *simduid_to_vf_htab
= NULL
;
467 hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
= NULL
;
468 bool any_ifcvt_loops
= false;
471 vect_loops_num
= number_of_loops (cfun
);
473 /* Bail out if there are no loops. */
474 if (vect_loops_num
<= 1)
477 if (cfun
->has_simduid_loops
)
478 note_simd_array_uses (&simd_array_to_simduid_htab
);
480 init_stmt_vec_info_vec ();
482 /* ----------- Analyze loops. ----------- */
484 /* If some loop was duplicated, it gets bigger number
485 than all previously defined loops. This fact allows us to run
486 only over initial loops skipping newly generated ones. */
487 FOR_EACH_LOOP (loop
, 0)
488 if (loop
->dont_vectorize
)
489 any_ifcvt_loops
= true;
490 else if ((flag_tree_loop_vectorize
491 && optimize_loop_nest_for_speed_p (loop
))
492 || loop
->force_vectorize
)
494 loop_vec_info loop_vinfo
;
495 vect_location
= find_loop_location (loop
);
496 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOCATION
497 && dump_enabled_p ())
498 dump_printf (MSG_NOTE
, "\nAnalyzing loop at %s:%d\n",
499 LOCATION_FILE (vect_location
),
500 LOCATION_LINE (vect_location
));
502 loop_vinfo
= vect_analyze_loop (loop
);
503 loop
->aux
= loop_vinfo
;
505 if (!loop_vinfo
|| !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
))
508 if (!dbg_cnt (vect_loop
))
511 gimple loop_vectorized_call
= vect_loop_vectorized_call (loop
);
512 if (loop_vectorized_call
)
513 set_uid_loop_bbs (loop_vinfo
, loop_vectorized_call
);
514 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOCATION
515 && dump_enabled_p ())
516 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
517 "loop vectorized\n");
518 vect_transform_loop (loop_vinfo
);
519 num_vectorized_loops
++;
520 /* Now that the loop has been vectorized, allow it to be unrolled
522 loop
->force_vectorize
= false;
526 simduid_to_vf
*simduid_to_vf_data
= XNEW (simduid_to_vf
);
527 if (!simduid_to_vf_htab
)
528 simduid_to_vf_htab
= new hash_table
<simduid_to_vf
> (15);
529 simduid_to_vf_data
->simduid
= DECL_UID (loop
->simduid
);
530 simduid_to_vf_data
->vf
= loop_vinfo
->vectorization_factor
;
531 *simduid_to_vf_htab
->find_slot (simduid_to_vf_data
, INSERT
)
532 = simduid_to_vf_data
;
535 if (loop_vectorized_call
)
537 fold_loop_vectorized_call (loop_vectorized_call
, boolean_true_node
);
538 ret
|= TODO_cleanup_cfg
;
542 vect_location
= UNKNOWN_LOCATION
;
544 statistics_counter_event (cfun
, "Vectorized loops", num_vectorized_loops
);
545 if (dump_enabled_p ()
546 || (num_vectorized_loops
> 0 && dump_enabled_p ()))
547 dump_printf_loc (MSG_NOTE
, vect_location
,
548 "vectorized %u loops in function.\n",
549 num_vectorized_loops
);
551 /* ----------- Finalize. ----------- */
554 for (i
= 1; i
< vect_loops_num
; i
++)
556 loop
= get_loop (cfun
, i
);
557 if (loop
&& loop
->dont_vectorize
)
559 gimple g
= vect_loop_vectorized_call (loop
);
562 fold_loop_vectorized_call (g
, boolean_false_node
);
563 ret
|= TODO_cleanup_cfg
;
568 for (i
= 1; i
< vect_loops_num
; i
++)
570 loop_vec_info loop_vinfo
;
572 loop
= get_loop (cfun
, i
);
575 loop_vinfo
= (loop_vec_info
) loop
->aux
;
576 destroy_loop_vec_info (loop_vinfo
, true);
580 free_stmt_vec_info_vec ();
582 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE} builtins. */
583 if (cfun
->has_simduid_loops
)
584 adjust_simduid_builtins (simduid_to_vf_htab
);
586 /* Shrink any "omp array simd" temporary arrays to the
587 actual vectorization factors. */
588 if (simd_array_to_simduid_htab
)
589 shrink_simd_arrays (simd_array_to_simduid_htab
, simduid_to_vf_htab
);
590 delete simduid_to_vf_htab
;
591 cfun
->has_simduid_loops
= false;
593 if (num_vectorized_loops
> 0)
595 /* If we vectorized any loop only virtual SSA form needs to be updated.
596 ??? Also while we try hard to update loop-closed SSA form we fail
597 to properly do this in some corner-cases (see PR56286). */
598 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa_only_virtuals
);
599 return TODO_cleanup_cfg
;
606 /* Entry point to the simduid cleanup pass. */
610 const pass_data pass_data_simduid_cleanup
=
612 GIMPLE_PASS
, /* type */
613 "simduid", /* name */
614 OPTGROUP_NONE
, /* optinfo_flags */
616 ( PROP_ssa
| PROP_cfg
), /* properties_required */
617 0, /* properties_provided */
618 0, /* properties_destroyed */
619 0, /* todo_flags_start */
620 0, /* todo_flags_finish */
623 class pass_simduid_cleanup
: public gimple_opt_pass
626 pass_simduid_cleanup (gcc::context
*ctxt
)
627 : gimple_opt_pass (pass_data_simduid_cleanup
, ctxt
)
630 /* opt_pass methods: */
631 opt_pass
* clone () { return new pass_simduid_cleanup (m_ctxt
); }
632 virtual bool gate (function
*fun
) { return fun
->has_simduid_loops
; }
633 virtual unsigned int execute (function
*);
635 }; // class pass_simduid_cleanup
638 pass_simduid_cleanup::execute (function
*fun
)
640 hash_table
<simd_array_to_simduid
> *simd_array_to_simduid_htab
= NULL
;
642 note_simd_array_uses (&simd_array_to_simduid_htab
);
644 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE} builtins. */
645 adjust_simduid_builtins (NULL
);
647 /* Shrink any "omp array simd" temporary arrays to the
648 actual vectorization factors. */
649 if (simd_array_to_simduid_htab
)
650 shrink_simd_arrays (simd_array_to_simduid_htab
, NULL
);
651 fun
->has_simduid_loops
= false;
658 make_pass_simduid_cleanup (gcc::context
*ctxt
)
660 return new pass_simduid_cleanup (ctxt
);
664 /* Entry point to basic block SLP phase. */
668 const pass_data pass_data_slp_vectorize
=
670 GIMPLE_PASS
, /* type */
672 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
673 TV_TREE_SLP_VECTORIZATION
, /* tv_id */
674 ( PROP_ssa
| PROP_cfg
), /* properties_required */
675 0, /* properties_provided */
676 0, /* properties_destroyed */
677 0, /* todo_flags_start */
678 TODO_update_ssa
, /* todo_flags_finish */
681 class pass_slp_vectorize
: public gimple_opt_pass
684 pass_slp_vectorize (gcc::context
*ctxt
)
685 : gimple_opt_pass (pass_data_slp_vectorize
, ctxt
)
688 /* opt_pass methods: */
689 opt_pass
* clone () { return new pass_slp_vectorize (m_ctxt
); }
690 virtual bool gate (function
*) { return flag_tree_slp_vectorize
!= 0; }
691 virtual unsigned int execute (function
*);
693 }; // class pass_slp_vectorize
696 pass_slp_vectorize::execute (function
*fun
)
700 bool in_loop_pipeline
= scev_initialized_p ();
701 if (!in_loop_pipeline
)
703 loop_optimizer_init (LOOPS_NORMAL
);
707 init_stmt_vec_info_vec ();
709 FOR_EACH_BB_FN (bb
, fun
)
711 vect_location
= find_bb_location (bb
);
713 if (vect_slp_analyze_bb (bb
))
715 if (!dbg_cnt (vect_slp
))
718 vect_slp_transform_bb (bb
);
719 if (dump_enabled_p ())
720 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
721 "basic block vectorized\n");
725 free_stmt_vec_info_vec ();
727 if (!in_loop_pipeline
)
730 loop_optimizer_finalize ();
739 make_pass_slp_vectorize (gcc::context
*ctxt
)
741 return new pass_slp_vectorize (ctxt
);
745 /* Increase alignment of global arrays to improve vectorization potential.
747 - Consider also structs that have an array field.
748 - Use ipa analysis to prune arrays that can't be vectorized?
749 This should involve global alignment analysis and in the future also
753 increase_alignment (void)
757 vect_location
= UNKNOWN_LOCATION
;
759 /* Increase the alignment of all global arrays for vectorization. */
760 FOR_EACH_DEFINED_VARIABLE (vnode
)
762 tree vectype
, decl
= vnode
->decl
;
764 unsigned int alignment
;
766 t
= TREE_TYPE (decl
);
767 if (TREE_CODE (t
) != ARRAY_TYPE
)
769 vectype
= get_vectype_for_scalar_type (strip_array_types (t
));
772 alignment
= TYPE_ALIGN (vectype
);
773 if (DECL_ALIGN (decl
) >= alignment
)
776 if (vect_can_force_dr_alignment_p (decl
, alignment
))
778 vnode
->increase_alignment (TYPE_ALIGN (vectype
));
779 dump_printf (MSG_NOTE
, "Increasing alignment of decl: ");
780 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, decl
);
781 dump_printf (MSG_NOTE
, "\n");
790 const pass_data pass_data_ipa_increase_alignment
=
792 SIMPLE_IPA_PASS
, /* type */
793 "increase_alignment", /* name */
794 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
795 TV_IPA_OPT
, /* tv_id */
796 0, /* properties_required */
797 0, /* properties_provided */
798 0, /* properties_destroyed */
799 0, /* todo_flags_start */
800 0, /* todo_flags_finish */
803 class pass_ipa_increase_alignment
: public simple_ipa_opt_pass
806 pass_ipa_increase_alignment (gcc::context
*ctxt
)
807 : simple_ipa_opt_pass (pass_data_ipa_increase_alignment
, ctxt
)
810 /* opt_pass methods: */
811 virtual bool gate (function
*)
813 return flag_section_anchors
&& flag_tree_loop_vectorize
;
816 virtual unsigned int execute (function
*) { return increase_alignment (); }
818 }; // class pass_ipa_increase_alignment
822 simple_ipa_opt_pass
*
823 make_pass_ipa_increase_alignment (gcc::context
*ctxt
)
825 return new pass_ipa_increase_alignment (ctxt
);