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 simduid.0 to OMP simd array (D.1737[]). */
116 struct simd_array_to_simduid
: typed_free_remove
<simd_array_to_simduid
>
119 unsigned int simduid
;
121 /* hash_table support. */
122 typedef simd_array_to_simduid value_type
;
123 typedef simd_array_to_simduid compare_type
;
124 static inline hashval_t
hash (const value_type
*);
125 static inline int equal (const value_type
*, const compare_type
*);
129 simd_array_to_simduid::hash (const value_type
*p
)
131 return DECL_UID (p
->decl
);
135 simd_array_to_simduid::equal (const value_type
*p1
, const value_type
*p2
)
137 return p1
->decl
== p2
->decl
;
140 /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF and IFN_GOMP_SIMD_LAST_LANE
141 into their corresponding constants. */
144 adjust_simduid_builtins (hash_table
<simduid_to_vf
> &htab
)
150 gimple_stmt_iterator i
;
152 for (i
= gsi_start_bb (bb
); !gsi_end_p (i
); gsi_next (&i
))
155 enum internal_fn ifn
;
156 gimple stmt
= gsi_stmt (i
);
158 if (!is_gimple_call (stmt
)
159 || !gimple_call_internal_p (stmt
))
161 ifn
= gimple_call_internal_fn (stmt
);
164 case IFN_GOMP_SIMD_LANE
:
165 case IFN_GOMP_SIMD_VF
:
166 case IFN_GOMP_SIMD_LAST_LANE
:
171 tree arg
= gimple_call_arg (stmt
, 0);
172 gcc_assert (arg
!= NULL_TREE
);
173 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
174 simduid_to_vf
*p
= NULL
, data
;
175 data
.simduid
= DECL_UID (SSA_NAME_VAR (arg
));
176 if (htab
.is_created ())
177 p
= htab
.find (&data
);
182 case IFN_GOMP_SIMD_VF
:
183 t
= build_int_cst (unsigned_type_node
, vf
);
185 case IFN_GOMP_SIMD_LANE
:
186 t
= build_int_cst (unsigned_type_node
, 0);
188 case IFN_GOMP_SIMD_LAST_LANE
:
189 t
= gimple_call_arg (stmt
, 1);
194 update_call_from_tree (&i
, t
);
199 /* Helper structure for note_simd_array_uses. */
201 struct note_simd_array_uses_struct
203 hash_table
<simd_array_to_simduid
> *htab
;
204 unsigned int simduid
;
207 /* Callback for note_simd_array_uses, called through walk_gimple_op. */
210 note_simd_array_uses_cb (tree
*tp
, int *walk_subtrees
, void *data
)
212 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
213 struct note_simd_array_uses_struct
*ns
214 = (struct note_simd_array_uses_struct
*) wi
->info
;
219 && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp
))
220 && DECL_CONTEXT (*tp
) == current_function_decl
)
222 simd_array_to_simduid data
;
223 if (!ns
->htab
->is_created ())
224 ns
->htab
->create (15);
226 data
.simduid
= ns
->simduid
;
227 simd_array_to_simduid
**slot
= ns
->htab
->find_slot (&data
, INSERT
);
230 simd_array_to_simduid
*p
= XNEW (simd_array_to_simduid
);
234 else if ((*slot
)->simduid
!= ns
->simduid
)
235 (*slot
)->simduid
= -1U;
241 /* Find "omp simd array" temporaries and map them to corresponding
245 note_simd_array_uses (hash_table
<simd_array_to_simduid
> *htab
)
248 gimple_stmt_iterator gsi
;
249 struct walk_stmt_info wi
;
250 struct note_simd_array_uses_struct ns
;
252 memset (&wi
, 0, sizeof (wi
));
257 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
259 gimple stmt
= gsi_stmt (gsi
);
260 if (!is_gimple_call (stmt
) || !gimple_call_internal_p (stmt
))
262 switch (gimple_call_internal_fn (stmt
))
264 case IFN_GOMP_SIMD_LANE
:
265 case IFN_GOMP_SIMD_VF
:
266 case IFN_GOMP_SIMD_LAST_LANE
:
271 tree lhs
= gimple_call_lhs (stmt
);
272 if (lhs
== NULL_TREE
)
274 imm_use_iterator use_iter
;
276 ns
.simduid
= DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt
, 0)));
277 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, lhs
)
278 if (!is_gimple_debug (use_stmt
))
279 walk_gimple_op (use_stmt
, note_simd_array_uses_cb
, &wi
);
283 /* A helper function to free data refs. */
286 vect_destroy_datarefs (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
)
288 vec
<data_reference_p
> datarefs
;
289 struct data_reference
*dr
;
293 datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
295 datarefs
= BB_VINFO_DATAREFS (bb_vinfo
);
297 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
304 free_data_refs (datarefs
);
308 /* Function vectorize_loops.
310 Entry point to loop vectorization phase. */
313 vectorize_loops (void)
316 unsigned int num_vectorized_loops
= 0;
317 unsigned int vect_loops_num
;
320 hash_table
<simduid_to_vf
> simduid_to_vf_htab
;
321 hash_table
<simd_array_to_simduid
> simd_array_to_simduid_htab
;
323 vect_loops_num
= number_of_loops (cfun
);
325 /* Bail out if there are no loops. */
326 if (vect_loops_num
<= 1)
328 if (cfun
->has_simduid_loops
)
329 adjust_simduid_builtins (simduid_to_vf_htab
);
333 if (cfun
->has_simduid_loops
)
334 note_simd_array_uses (&simd_array_to_simduid_htab
);
336 init_stmt_vec_info_vec ();
338 /* ----------- Analyze loops. ----------- */
340 /* If some loop was duplicated, it gets bigger number
341 than all previously defined loops. This fact allows us to run
342 only over initial loops skipping newly generated ones. */
343 FOR_EACH_LOOP (li
, loop
, 0)
344 if ((flag_tree_loop_vectorize
&& optimize_loop_nest_for_speed_p (loop
))
347 loop_vec_info loop_vinfo
;
348 vect_location
= find_loop_location (loop
);
349 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOC
350 && dump_enabled_p ())
351 dump_printf (MSG_NOTE
, "\nAnalyzing loop at %s:%d\n",
352 LOC_FILE (vect_location
), LOC_LINE (vect_location
));
354 loop_vinfo
= vect_analyze_loop (loop
);
355 loop
->aux
= loop_vinfo
;
357 if (!loop_vinfo
|| !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
))
360 if (!dbg_cnt (vect_loop
))
363 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOC
364 && dump_enabled_p ())
365 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
366 "loop vectorized\n");
367 vect_transform_loop (loop_vinfo
);
368 num_vectorized_loops
++;
369 /* Now that the loop has been vectorized, allow it to be unrolled
371 loop
->force_vect
= false;
375 simduid_to_vf
*simduid_to_vf_data
= XNEW (simduid_to_vf
);
376 if (!simduid_to_vf_htab
.is_created ())
377 simduid_to_vf_htab
.create (15);
378 simduid_to_vf_data
->simduid
= DECL_UID (loop
->simduid
);
379 simduid_to_vf_data
->vf
= loop_vinfo
->vectorization_factor
;
380 *simduid_to_vf_htab
.find_slot (simduid_to_vf_data
, INSERT
)
381 = simduid_to_vf_data
;
385 vect_location
= UNKNOWN_LOC
;
387 statistics_counter_event (cfun
, "Vectorized loops", num_vectorized_loops
);
388 if (dump_enabled_p ()
389 || (num_vectorized_loops
> 0 && dump_enabled_p ()))
390 dump_printf_loc (MSG_NOTE
, vect_location
,
391 "vectorized %u loops in function.\n",
392 num_vectorized_loops
);
394 /* ----------- Finalize. ----------- */
396 for (i
= 1; i
< vect_loops_num
; i
++)
398 loop_vec_info loop_vinfo
;
400 loop
= get_loop (cfun
, i
);
403 loop_vinfo
= (loop_vec_info
) loop
->aux
;
404 destroy_loop_vec_info (loop_vinfo
, true);
408 free_stmt_vec_info_vec ();
410 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE} builtins. */
411 if (cfun
->has_simduid_loops
)
412 adjust_simduid_builtins (simduid_to_vf_htab
);
414 /* Shrink any "omp array simd" temporary arrays to the
415 actual vectorization factors. */
416 if (simd_array_to_simduid_htab
.is_created ())
418 for (hash_table
<simd_array_to_simduid
>::iterator iter
419 = simd_array_to_simduid_htab
.begin ();
420 iter
!= simd_array_to_simduid_htab
.end (); ++iter
)
421 if ((*iter
).simduid
!= -1U)
423 tree decl
= (*iter
).decl
;
425 if (simduid_to_vf_htab
.is_created ())
427 simduid_to_vf
*p
= NULL
, data
;
428 data
.simduid
= (*iter
).simduid
;
429 p
= simduid_to_vf_htab
.find (&data
);
434 = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl
)), vf
);
435 TREE_TYPE (decl
) = atype
;
436 relayout_decl (decl
);
439 simd_array_to_simduid_htab
.dispose ();
441 if (simduid_to_vf_htab
.is_created ())
442 simduid_to_vf_htab
.dispose ();
444 if (num_vectorized_loops
> 0)
446 /* If we vectorized any loop only virtual SSA form needs to be updated.
447 ??? Also while we try hard to update loop-closed SSA form we fail
448 to properly do this in some corner-cases (see PR56286). */
449 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa_only_virtuals
);
450 return TODO_cleanup_cfg
;
457 /* Entry point to basic block SLP phase. */
460 execute_vect_slp (void)
464 init_stmt_vec_info_vec ();
468 vect_location
= find_bb_location (bb
);
470 if (vect_slp_analyze_bb (bb
))
472 if (!dbg_cnt (vect_slp
))
475 vect_slp_transform_bb (bb
);
476 if (dump_enabled_p ())
477 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
478 "basic block vectorized\n");
482 free_stmt_vec_info_vec ();
489 return flag_tree_slp_vectorize
!= 0;
494 const pass_data pass_data_slp_vectorize
=
496 GIMPLE_PASS
, /* type */
498 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
500 true, /* has_execute */
501 TV_TREE_SLP_VECTORIZATION
, /* tv_id */
502 ( PROP_ssa
| PROP_cfg
), /* properties_required */
503 0, /* properties_provided */
504 0, /* properties_destroyed */
505 0, /* todo_flags_start */
506 ( TODO_verify_ssa
| TODO_update_ssa
507 | TODO_verify_stmts
), /* todo_flags_finish */
510 class pass_slp_vectorize
: public gimple_opt_pass
513 pass_slp_vectorize(gcc::context
*ctxt
)
514 : gimple_opt_pass(pass_data_slp_vectorize
, ctxt
)
517 /* opt_pass methods: */
518 bool gate () { return gate_vect_slp (); }
519 unsigned int execute () { return execute_vect_slp (); }
521 }; // class pass_slp_vectorize
526 make_pass_slp_vectorize (gcc::context
*ctxt
)
528 return new pass_slp_vectorize (ctxt
);
532 /* Increase alignment of global arrays to improve vectorization potential.
534 - Consider also structs that have an array field.
535 - Use ipa analysis to prune arrays that can't be vectorized?
536 This should involve global alignment analysis and in the future also
540 increase_alignment (void)
542 struct varpool_node
*vnode
;
544 vect_location
= UNKNOWN_LOC
;
546 /* Increase the alignment of all global arrays for vectorization. */
547 FOR_EACH_DEFINED_VARIABLE (vnode
)
549 tree vectype
, decl
= vnode
->symbol
.decl
;
551 unsigned int alignment
;
554 if (TREE_CODE (t
) != ARRAY_TYPE
)
556 vectype
= get_vectype_for_scalar_type (strip_array_types (t
));
559 alignment
= TYPE_ALIGN (vectype
);
560 if (DECL_ALIGN (decl
) >= alignment
)
563 if (vect_can_force_dr_alignment_p (decl
, alignment
))
565 DECL_ALIGN (decl
) = TYPE_ALIGN (vectype
);
566 DECL_USER_ALIGN (decl
) = 1;
567 dump_printf (MSG_NOTE
, "Increasing alignment of decl: ");
568 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, decl
);
569 dump_printf (MSG_NOTE
, "\n");
577 gate_increase_alignment (void)
579 return flag_section_anchors
&& flag_tree_loop_vectorize
;
585 const pass_data pass_data_ipa_increase_alignment
=
587 SIMPLE_IPA_PASS
, /* type */
588 "increase_alignment", /* name */
589 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
591 true, /* has_execute */
592 TV_IPA_OPT
, /* tv_id */
593 0, /* properties_required */
594 0, /* properties_provided */
595 0, /* properties_destroyed */
596 0, /* todo_flags_start */
597 0, /* todo_flags_finish */
600 class pass_ipa_increase_alignment
: public simple_ipa_opt_pass
603 pass_ipa_increase_alignment(gcc::context
*ctxt
)
604 : simple_ipa_opt_pass(pass_data_ipa_increase_alignment
, ctxt
)
607 /* opt_pass methods: */
608 bool gate () { return gate_increase_alignment (); }
609 unsigned int execute () { return increase_alignment (); }
611 }; // class pass_ipa_increase_alignment
615 simple_ipa_opt_pass
*
616 make_pass_ipa_increase_alignment (gcc::context
*ctxt
)
618 return new pass_ipa_increase_alignment (ctxt
);