2 Copyright (C) 2003-2013 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-pretty-print.h"
67 #include "tree-vectorizer.h"
68 #include "tree-pass.h"
69 #include "hash-table.h"
70 #include "tree-ssa-propagate.h"
73 /* Loop or bb location. */
76 /* Vector mapping GIMPLE stmt to stmt_vec_info. */
77 vec
<vec_void_p
> stmt_vec_info_vec
;
79 /* For mapping simduid to vectorization factor. */
81 struct simduid_to_vf
: typed_free_remove
<simduid_to_vf
>
86 /* hash_table support. */
87 typedef simduid_to_vf value_type
;
88 typedef simduid_to_vf compare_type
;
89 static inline hashval_t
hash (const value_type
*);
90 static inline int equal (const value_type
*, const compare_type
*);
94 simduid_to_vf::hash (const value_type
*p
)
100 simduid_to_vf::equal (const value_type
*p1
, const value_type
*p2
)
102 return p1
->simduid
== p2
->simduid
;
105 /* This hash maps the OMP simd array to the corresponding simduid used
106 to index into it. Like thus,
108 _7 = GOMP_SIMD_LANE (simduid.0)
114 This hash maps from the OMP simd array (D.1737[]) to DECL_UID of
117 struct simd_array_to_simduid
: typed_free_remove
<simd_array_to_simduid
>
120 unsigned int simduid
;
122 /* hash_table support. */
123 typedef simd_array_to_simduid value_type
;
124 typedef simd_array_to_simduid compare_type
;
125 static inline hashval_t
hash (const value_type
*);
126 static inline int equal (const value_type
*, const compare_type
*);
130 simd_array_to_simduid::hash (const value_type
*p
)
132 return DECL_UID (p
->decl
);
136 simd_array_to_simduid::equal (const value_type
*p1
, const value_type
*p2
)
138 return p1
->decl
== p2
->decl
;
141 /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF and IFN_GOMP_SIMD_LAST_LANE
142 into their corresponding constants. */
145 adjust_simduid_builtins (hash_table
<simduid_to_vf
> &htab
)
151 gimple_stmt_iterator i
;
153 for (i
= gsi_start_bb (bb
); !gsi_end_p (i
); gsi_next (&i
))
156 enum internal_fn ifn
;
157 gimple stmt
= gsi_stmt (i
);
159 if (!is_gimple_call (stmt
)
160 || !gimple_call_internal_p (stmt
))
162 ifn
= gimple_call_internal_fn (stmt
);
165 case IFN_GOMP_SIMD_LANE
:
166 case IFN_GOMP_SIMD_VF
:
167 case IFN_GOMP_SIMD_LAST_LANE
:
172 tree arg
= gimple_call_arg (stmt
, 0);
173 gcc_assert (arg
!= NULL_TREE
);
174 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
175 simduid_to_vf
*p
= NULL
, data
;
176 data
.simduid
= DECL_UID (SSA_NAME_VAR (arg
));
177 if (htab
.is_created ())
178 p
= htab
.find (&data
);
183 case IFN_GOMP_SIMD_VF
:
184 t
= build_int_cst (unsigned_type_node
, vf
);
186 case IFN_GOMP_SIMD_LANE
:
187 t
= build_int_cst (unsigned_type_node
, 0);
189 case IFN_GOMP_SIMD_LAST_LANE
:
190 t
= gimple_call_arg (stmt
, 1);
195 update_call_from_tree (&i
, t
);
200 /* Helper structure for note_simd_array_uses. */
202 struct note_simd_array_uses_struct
204 hash_table
<simd_array_to_simduid
> *htab
;
205 unsigned int simduid
;
208 /* Callback for note_simd_array_uses, called through walk_gimple_op. */
211 note_simd_array_uses_cb (tree
*tp
, int *walk_subtrees
, void *data
)
213 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
214 struct note_simd_array_uses_struct
*ns
215 = (struct note_simd_array_uses_struct
*) wi
->info
;
220 && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp
))
221 && DECL_CONTEXT (*tp
) == current_function_decl
)
223 simd_array_to_simduid data
;
224 if (!ns
->htab
->is_created ())
225 ns
->htab
->create (15);
227 data
.simduid
= ns
->simduid
;
228 simd_array_to_simduid
**slot
= ns
->htab
->find_slot (&data
, INSERT
);
231 simd_array_to_simduid
*p
= XNEW (simd_array_to_simduid
);
235 else if ((*slot
)->simduid
!= ns
->simduid
)
236 (*slot
)->simduid
= -1U;
242 /* Find "omp simd array" temporaries and map them to corresponding
246 note_simd_array_uses (hash_table
<simd_array_to_simduid
> *htab
)
249 gimple_stmt_iterator gsi
;
250 struct walk_stmt_info wi
;
251 struct note_simd_array_uses_struct ns
;
253 memset (&wi
, 0, sizeof (wi
));
258 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
260 gimple stmt
= gsi_stmt (gsi
);
261 if (!is_gimple_call (stmt
) || !gimple_call_internal_p (stmt
))
263 switch (gimple_call_internal_fn (stmt
))
265 case IFN_GOMP_SIMD_LANE
:
266 case IFN_GOMP_SIMD_VF
:
267 case IFN_GOMP_SIMD_LAST_LANE
:
272 tree lhs
= gimple_call_lhs (stmt
);
273 if (lhs
== NULL_TREE
)
275 imm_use_iterator use_iter
;
277 ns
.simduid
= DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt
, 0)));
278 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, lhs
)
279 if (!is_gimple_debug (use_stmt
))
280 walk_gimple_op (use_stmt
, note_simd_array_uses_cb
, &wi
);
284 /* A helper function to free data refs. */
287 vect_destroy_datarefs (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
)
289 vec
<data_reference_p
> datarefs
;
290 struct data_reference
*dr
;
294 datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
296 datarefs
= BB_VINFO_DATAREFS (bb_vinfo
);
298 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
305 free_data_refs (datarefs
);
309 /* Function vectorize_loops.
311 Entry point to loop vectorization phase. */
314 vectorize_loops (void)
317 unsigned int num_vectorized_loops
= 0;
318 unsigned int vect_loops_num
;
321 hash_table
<simduid_to_vf
> simduid_to_vf_htab
;
322 hash_table
<simd_array_to_simduid
> simd_array_to_simduid_htab
;
324 vect_loops_num
= number_of_loops (cfun
);
326 /* Bail out if there are no loops. */
327 if (vect_loops_num
<= 1)
329 if (cfun
->has_simduid_loops
)
330 adjust_simduid_builtins (simduid_to_vf_htab
);
334 if (cfun
->has_simduid_loops
)
335 note_simd_array_uses (&simd_array_to_simduid_htab
);
337 init_stmt_vec_info_vec ();
339 /* ----------- Analyze loops. ----------- */
341 /* If some loop was duplicated, it gets bigger number
342 than all previously defined loops. This fact allows us to run
343 only over initial loops skipping newly generated ones. */
344 FOR_EACH_LOOP (li
, loop
, 0)
345 if ((flag_tree_loop_vectorize
&& optimize_loop_nest_for_speed_p (loop
))
348 loop_vec_info loop_vinfo
;
349 vect_location
= find_loop_location (loop
);
350 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOC
351 && dump_enabled_p ())
352 dump_printf (MSG_NOTE
, "\nAnalyzing loop at %s:%d\n",
353 LOC_FILE (vect_location
), LOC_LINE (vect_location
));
355 loop_vinfo
= vect_analyze_loop (loop
);
356 loop
->aux
= loop_vinfo
;
358 if (!loop_vinfo
|| !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
))
361 if (!dbg_cnt (vect_loop
))
364 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOC
365 && dump_enabled_p ())
366 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
367 "loop vectorized\n");
368 vect_transform_loop (loop_vinfo
);
369 num_vectorized_loops
++;
370 /* Now that the loop has been vectorized, allow it to be unrolled
372 loop
->force_vect
= false;
376 simduid_to_vf
*simduid_to_vf_data
= XNEW (simduid_to_vf
);
377 if (!simduid_to_vf_htab
.is_created ())
378 simduid_to_vf_htab
.create (15);
379 simduid_to_vf_data
->simduid
= DECL_UID (loop
->simduid
);
380 simduid_to_vf_data
->vf
= loop_vinfo
->vectorization_factor
;
381 *simduid_to_vf_htab
.find_slot (simduid_to_vf_data
, INSERT
)
382 = simduid_to_vf_data
;
386 vect_location
= UNKNOWN_LOC
;
388 statistics_counter_event (cfun
, "Vectorized loops", num_vectorized_loops
);
389 if (dump_enabled_p ()
390 || (num_vectorized_loops
> 0 && dump_enabled_p ()))
391 dump_printf_loc (MSG_NOTE
, vect_location
,
392 "vectorized %u loops in function.\n",
393 num_vectorized_loops
);
395 /* ----------- Finalize. ----------- */
397 for (i
= 1; i
< vect_loops_num
; i
++)
399 loop_vec_info loop_vinfo
;
401 loop
= get_loop (cfun
, i
);
404 loop_vinfo
= (loop_vec_info
) loop
->aux
;
405 destroy_loop_vec_info (loop_vinfo
, true);
409 free_stmt_vec_info_vec ();
411 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE} builtins. */
412 if (cfun
->has_simduid_loops
)
413 adjust_simduid_builtins (simduid_to_vf_htab
);
415 /* Shrink any "omp array simd" temporary arrays to the
416 actual vectorization factors. */
417 if (simd_array_to_simduid_htab
.is_created ())
419 for (hash_table
<simd_array_to_simduid
>::iterator iter
420 = simd_array_to_simduid_htab
.begin ();
421 iter
!= simd_array_to_simduid_htab
.end (); ++iter
)
422 if ((*iter
).simduid
!= -1U)
424 tree decl
= (*iter
).decl
;
426 if (simduid_to_vf_htab
.is_created ())
428 simduid_to_vf
*p
= NULL
, data
;
429 data
.simduid
= (*iter
).simduid
;
430 p
= simduid_to_vf_htab
.find (&data
);
435 = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl
)), vf
);
436 TREE_TYPE (decl
) = atype
;
437 relayout_decl (decl
);
440 simd_array_to_simduid_htab
.dispose ();
442 if (simduid_to_vf_htab
.is_created ())
443 simduid_to_vf_htab
.dispose ();
445 if (num_vectorized_loops
> 0)
447 /* If we vectorized any loop only virtual SSA form needs to be updated.
448 ??? Also while we try hard to update loop-closed SSA form we fail
449 to properly do this in some corner-cases (see PR56286). */
450 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa_only_virtuals
);
451 return TODO_cleanup_cfg
;
458 /* Entry point to basic block SLP phase. */
461 execute_vect_slp (void)
465 init_stmt_vec_info_vec ();
469 vect_location
= find_bb_location (bb
);
471 if (vect_slp_analyze_bb (bb
))
473 if (!dbg_cnt (vect_slp
))
476 vect_slp_transform_bb (bb
);
477 if (dump_enabled_p ())
478 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
479 "basic block vectorized\n");
483 free_stmt_vec_info_vec ();
490 return flag_tree_slp_vectorize
!= 0;
495 const pass_data pass_data_slp_vectorize
=
497 GIMPLE_PASS
, /* type */
499 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
501 true, /* has_execute */
502 TV_TREE_SLP_VECTORIZATION
, /* tv_id */
503 ( PROP_ssa
| PROP_cfg
), /* properties_required */
504 0, /* properties_provided */
505 0, /* properties_destroyed */
506 0, /* todo_flags_start */
507 ( TODO_verify_ssa
| TODO_update_ssa
508 | TODO_verify_stmts
), /* todo_flags_finish */
511 class pass_slp_vectorize
: public gimple_opt_pass
514 pass_slp_vectorize (gcc::context
*ctxt
)
515 : gimple_opt_pass (pass_data_slp_vectorize
, ctxt
)
518 /* opt_pass methods: */
519 bool gate () { return gate_vect_slp (); }
520 unsigned int execute () { return execute_vect_slp (); }
522 }; // class pass_slp_vectorize
527 make_pass_slp_vectorize (gcc::context
*ctxt
)
529 return new pass_slp_vectorize (ctxt
);
533 /* Increase alignment of global arrays to improve vectorization potential.
535 - Consider also structs that have an array field.
536 - Use ipa analysis to prune arrays that can't be vectorized?
537 This should involve global alignment analysis and in the future also
541 increase_alignment (void)
543 struct varpool_node
*vnode
;
545 vect_location
= UNKNOWN_LOC
;
547 /* Increase the alignment of all global arrays for vectorization. */
548 FOR_EACH_DEFINED_VARIABLE (vnode
)
550 tree vectype
, decl
= vnode
->symbol
.decl
;
552 unsigned int alignment
;
554 t
= TREE_TYPE (decl
);
555 if (TREE_CODE (t
) != ARRAY_TYPE
)
557 vectype
= get_vectype_for_scalar_type (strip_array_types (t
));
560 alignment
= TYPE_ALIGN (vectype
);
561 if (DECL_ALIGN (decl
) >= alignment
)
564 if (vect_can_force_dr_alignment_p (decl
, alignment
))
566 DECL_ALIGN (decl
) = TYPE_ALIGN (vectype
);
567 DECL_USER_ALIGN (decl
) = 1;
568 dump_printf (MSG_NOTE
, "Increasing alignment of decl: ");
569 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, decl
);
570 dump_printf (MSG_NOTE
, "\n");
578 gate_increase_alignment (void)
580 return flag_section_anchors
&& flag_tree_loop_vectorize
;
586 const pass_data pass_data_ipa_increase_alignment
=
588 SIMPLE_IPA_PASS
, /* type */
589 "increase_alignment", /* name */
590 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
592 true, /* has_execute */
593 TV_IPA_OPT
, /* tv_id */
594 0, /* properties_required */
595 0, /* properties_provided */
596 0, /* properties_destroyed */
597 0, /* todo_flags_start */
598 0, /* todo_flags_finish */
601 class pass_ipa_increase_alignment
: public simple_ipa_opt_pass
604 pass_ipa_increase_alignment (gcc::context
*ctxt
)
605 : simple_ipa_opt_pass (pass_data_ipa_increase_alignment
, ctxt
)
608 /* opt_pass methods: */
609 bool gate () { return gate_increase_alignment (); }
610 unsigned int execute () { return increase_alignment (); }
612 }; // class pass_ipa_increase_alignment
616 simple_ipa_opt_pass
*
617 make_pass_ipa_increase_alignment (gcc::context
*ctxt
)
619 return new pass_ipa_increase_alignment (ctxt
);